app.js

/* ===========================================================
   DFA Security Lab — Core JS
   - Tabs
   - Regex Parser (subset) → Postfix (Shunting Yard)
   - Thompson NFA
   - Subset Construction DFA
   - Drawing helpers (NFA, DFA)
   - Playground (drag & drop DFA)
   - Exporters (JSON, C++, Python)
   - Performance Bench
   No external libs. Teaching-friendly, robust enough for demos.
=========================================================== */

/* ---------------- Tabs ---------------- */
document.querySelectorAll('.tab').forEach(btn=>{
  btn.addEventListener('click', ()=>{
    document.querySelectorAll('.tab').forEach(b=>b.classList.remove('active'));
    document.querySelectorAll('.panel').forEach(p=>p.classList.remove('active'));
    btn.classList.add('active');
    document.getElementById(btn.dataset.tab).classList.add('active');
  });
});

/* ---------------- Utilities ---------------- */
const EPS = 'ε';
const randId = (p='n')=> p + Math.random().toString(36).slice(2,8);
const text = (id)=>document.getElementById(id).value;
const setText = (id,val)=>{document.getElementById(id).value = val;}
const showChip = (id, cls, msg)=>{
  const el = document.getElementById(id);
  el.className = 'chip ' + cls;
  el.textContent = msg;
};
const clamp = (x,a,b)=>Math.max(a,Math.min(b,x));

/* ---------------- Regex tokenization (subset) ----------------
   Supports: (), |, *, +, ?, char classes [..], escapes \, and
   implicit concatenation via inserting '.' operator.
--------------------------------------------------------------*/
function tokenizeRegex(pattern){
  const tokens = [];
  let i=0;
  const push = (t)=>tokens.push(t);

  const isMeta = c => '()*+?|.'.includes(c);
  const isClassChar = c => c !== ']' && i < pattern.length;

  while(i<pattern.length){
    let c = pattern[i];

    if (c === '\\' && i+1 < pattern.length){
      push({type:'lit', val: pattern[i+1]});
      i+=2; continue;
    }
    if (c === '['){
      // character class [...] supports ranges like a-z and explicit sets
      let j = i+1, s = '';
      while(j<pattern.length && pattern[j]!==']'){ s += pattern[j++]; }
      if (j>=pattern.length) throw new Error('Unterminated character class');
      push({type:'class', val:s});
      i = j+1; continue;
    }
    if ('()*+?|'.includes(c)){ push({type:c}); i++; continue; }
    if (c.trim()===''){ i++; continue; }
    // literal
    push({type:'lit', val:c});
    i++;
  }

  // insert explicit concatenation operator '.'
  const out = [];
  for(let k=0;k<tokens.length;k++){
    const t = tokens[k];
    out.push(t);
    if (k<tokens.length-1){
      const a = t.type, b = tokens[k+1].type;
      const isAConcatEnd = (a==='lit'||a==='class'||a===')'||a==='*'||a==='+'||a==='?');
      const isBConcatStart= (b==='lit'||b==='class'||b==='(');
      if (isAConcatEnd && isBConcatStart) out.push({type:'.'});
    }
  }
  return out;
}

/* ---------------- Shunting-Yard to postfix ---------------- */
const prec = {'|':1, '.':2, '*':3, '+':3, '?':3};
const rightAssoc = new Set(['*','+','?']);
function toPostfix(tokens){
  const out=[], st=[];
  for(const t of tokens){
    if (t.type==='lit' || t.type==='class') out.push(t);
    else if (t.type==='(') st.push(t.type);
    else if (t.type===')'){
      while(st.length && st.at(-1)!=='(') out.push({type:st.pop()});
      if (!st.length) throw new Error('Mismatched parentheses');
      st.pop();
    } else if (['|','.','*','+','?'].includes(t.type)){
      if (['*','+','?'].includes(t.type)){
        // unary postfix: pop while higher precedence at top if needed
        while(st.length && prec[st.at(-1)]>prec[t.type]) out.push({type:st.pop()});
        st.push(t.type);
      } else {
        while(st.length && st.at(-1)!=='(' &&
              (prec[st.at(-1)]>prec[t.type] ||
              (prec[st.at(-1)]===prec[t.type] && !rightAssoc.has(t.type)))){
          out.push({type:st.pop()});
        }
        st.push(t.type);
      }
    } else {
      throw new Error('Unknown token: ' + JSON.stringify(t));
    }
  }
  while(st.length){
    const op=st.pop();
    if (op==='(') throw new Error('Mismatched parentheses');
    out.push({type:op});
  }
  return out;
}

/* ---------------- Thompson NFA ---------------- */
function makeState(){ return { id: randId('s'), edges: new Map(), eps: new Set(), accept:false }; }
function addEdge(s, sym, t){
  if (sym===EPS){ s.eps.add(t.id); return; }
  if (!s.edges.has(sym)) s.edges.set(sym, new Set());
  s.edges.get(sym).add(t.id);
}
function expandClass(cls){
  // cls like "a-zA-Z0-9@#_"
  const chars = new Set();
  for(let i=0;i<cls.length;i++){
    if (i+2<cls.length && cls[i+1]==='-'){
      const a=cls.charCodeAt(i), b=cls.charCodeAt(i+2);
      for(let c=a;c<=b;c++) chars.add(String.fromCharCode(c));
      i+=2;
    } else {
      chars.add(cls[i]);
    }
  }
  return [...chars];
}

function thompsonFromPostfix(post){
  // Stack of fragments: {start, accept}
  const stack=[];
  const states = new Map();
  const newState = ()=>{ const s=makeState(); states.set(s.id,s); return s; };

  for(const t of post){
    if (t.type==='lit' || t.type==='class'){
      const s = newState(), m = newState();
      m.accept=true;
      if (t.type==='lit'){
        addEdge(s, t.val, m);
      } else {
        for(const ch of expandClass(t.val)) addEdge(s, ch, m);
      }
      stack.push({start:s.id, accept:m.id});
    } else if (t.type==='.') {
      const b=stack.pop(), a=stack.pop();
      // a.accept ε-> b.start, and remove accept flag from a.accept
      states.get(a.accept).accept=false;
      addEdge(states.get(a.accept), EPS, states.get(b.start));
      stack.push({start:a.start, accept:b.accept});
    } else if (t.type==='|') {
      const b=stack.pop(), a=stack.pop();
      const s=newState(), m=newState(); m.accept=true;
      addEdge(s, EPS, states.get(a.start));
      addEdge(s, EPS, states.get(b.start));
      states.get(a.accept).accept=false; addEdge(states.get(a.accept), EPS, m);
      states.get(b.accept).accept=false; addEdge(states.get(b.accept), EPS, m);
      stack.push({start:s.id, accept:m.id});
    } else if (t.type==='*') {
      const a=stack.pop();
      const s=newState(), m=newState(); m.accept=true;
      addEdge(s, EPS, states.get(a.start));
      addEdge(s, EPS, m);
      states.get(a.accept).accept=false;
      addEdge(states.get(a.accept), EPS, m);
      addEdge(states.get(a.accept), EPS, states.get(a.start));
      stack.push({start:s.id, accept:m.id});
    } else if (t.type==='+') {
      const a=stack.pop();
      const s=newState(), m=newState(); m.accept=true;
      addEdge(s, EPS, states.get(a.start));
      states.get(a.accept).accept=false;
      addEdge(states.get(a.accept), EPS, m);
      addEdge(states.get(a.accept), EPS, states.get(a.start));
      stack.push({start:s.id, accept:m.id});
    } else if (t.type==='?') {
      const a=stack.pop();
      const s=newState(), m=newState(); m.accept=true;
      addEdge(s, EPS, states.get(a.start));
      addEdge(s, EPS, m);
      states.get(a.accept).accept=false; addEdge(states.get(a.accept), EPS, m);
      stack.push({start:s.id, accept:m.id});
    } else {
      throw new Error('Unsupported op: '+t.type);
    }
  }

  if (stack.length!==1) throw new Error('Invalid postfix');
  const frag = stack[0];
  return { states, start: frag.start, accepts: [...states.values()].filter(s=>s.accept).map(s=>s.id) };
}

/* ---------------- ε-closure and move ---------------- */
function eClosure(statesMap, setIds){
  const stack=[...setIds]; const out=new Set(setIds);
  while(stack.length){
    const sid = stack.pop();
    const s = statesMap.get(sid);
    for(const t of s.eps){
      if(!out.has(t)){ out.add(t); stack.push(t); }
    }
  }
  return out;
}
function moveOn(statesMap, setIds, sym){
  const out = new Set();
  for(const sid of setIds){
    const s = statesMap.get(sid);
    const edges = s.edges.get(sym);
    if (edges) for(const t of edges) out.add(t);
  }
  return out;
}
function nfaAlphabet(statesMap){
  const set = new Set();
  for(const s of statesMap.values()){
    for(const sym of s.edges.keys()) if (sym!==EPS) set.add(sym);
  }
  return [...set].sort();
}

/* ---------------- Subset construction (with snapshots) ---------------- */
function nfaToDfa(nfa){
  const alphabet = nfaAlphabet(nfa.states);
  const startSet = eClosure(nfa.states, new Set([nfa.start]));
  const key = (S)=>[...S].sort().join(',');
  const queue = [startSet];
  const dfaStates = new Map();  // key -> id
  const dfaAccepts = new Set();
  const dfaTrans = new Map();   // id -> Map(sym -> id)
  const snapshots = [];         // for animation

  let idCounter=0;
  const idOf = (S)=>{
    const k=key(S);
    if (!dfaStates.has(k)) dfaStates.set(k, 'q'+(idCounter++));
    return dfaStates.get(k);
  };

  const startId = idOf(startSet);
  if ([...startSet].some(sid => nfa.states.get(sid).accept)) dfaAccepts.add(startId);

  const seen = new Set([key(startSet)]);
  while(queue.length){
    const S = queue.shift();
    const sid = idOf(S);
    dfaTrans.set(sid, new Map());

    for(const a of alphabet){
      const U = eClosure(nfa.states, moveOn(nfa.states, S, a));
      if (!U.size) continue;
      const uid = idOf(U);
      dfaTrans.get(sid).set(a, uid);
      snapshots.push({from:sid, sym:a, to:uid, subset:[...U]});

      const k=key(U);
      if (!seen.has(k)){
        seen.add(k);
        queue.push(U);
        if ([...U].some(x=>nfa.states.get(x).accept)) dfaAccepts.add(uid);
      }
    }
  }

  const dfa = {
    states: [...new Set([...dfaTrans.keys(), ...[...dfaTrans.values()].flatMap(m=>[...m.values()])])],
    alphabet,
    start: startId,
    accept: [...dfaAccepts],
    transitions: Object.fromEntries(
      [...dfaTrans.entries()].map(([sid, m]) => [sid, Object.fromEntries([...m.entries()])])
    ),
    snapshots
  };
  return dfa;
}

/* ---------------- Drawing: simple force layout-ish ---------------- */
function drawAutomaton(canvas, automaton, opts={}){
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0,0,canvas.width,canvas.height);
  if (!automaton) return;

  const states = automaton.states || [];
  const pos = new Map();
  const n = states.length || (automaton.statesMap ? automaton.statesMap.size : 0);
  const cx = canvas.width/2, cy = canvas.height/2;
  const R = Math.min(cx,cy) - 40;

  // positions on circle
  states.forEach((q, i)=>{
    const angle = 2*Math.PI*i/Math.max(1,n);
    pos.set(q, {x: cx + R*Math.cos(angle), y: cy + R*Math.sin(angle)});
  });

  // edges
  ctx.lineWidth = 1.5;
  ctx.strokeStyle = '#ffb36b';
  ctx.fillStyle = '#ffb36b';
  const drawArrow = (x1,y1,x2,y2,label)=>{
    const ang = Math.atan2(y2-y1, x2-x1);
    const r = 22;
    const sx = x1 + r*Math.cos(ang);
    const sy = y1 + r*Math.sin(ang);
    const tx = x2 - r*Math.cos(ang);
    const ty = y2 - r*Math.sin(ang);

    ctx.beginPath();
    ctx.moveTo(sx,sy);
    ctx.lineTo(tx,ty);
    ctx.stroke();

    // arrow head
    // arrow head
    ctx.beginPath();
    ctx.moveTo(tx, ty);
    ctx.lineTo(tx - 8 * Math.cos(ang - Math.PI / 6), ty - 8 * Math.sin(ang - Math.PI / 6));
    ctx.lineTo(tx - 8 * Math.cos(ang + Math.PI / 6), ty - 8 * Math.sin(ang + Math.PI / 6));
    ctx.closePath();
    ctx.fill();


    // label
    ctx.fillStyle = '#ffd9bd';
    ctx.font = '12px system-ui';
    ctx.fillText(label, (sx+tx)/2 + 4, (sy+ty)/2 - 4);
    ctx.fillStyle = '#ffb36b';
  };

  // transitions
  if (automaton.transitions){
    for(const [from, map] of Object.entries(automaton.transitions)){
      for(const [sym, to] of Object.entries(map)){
        if (!pos.has(from) || !pos.has(to)) continue;
        const p1 = pos.get(from), p2 = pos.get(to);
        drawArrow(p1.x,p1.y,p2.x,p2.y,sym);
      }
    }
  } else if (automaton.statesMap){
    // NFA drawing (statesMap: id->state)
    for(const s of automaton.statesMap.values()){
      for(const [sym, set] of s.edges.entries()){
        for(const t of set){
          const a = pos.get(s.id), b = pos.get(t);
          if (a && b) drawArrow(a.x,a.y,b.x,b.y,sym);
        }
      }
      for(const t of s.eps){
        const a = pos.get(s.id), b = pos.get(t);
        if (a && b){
          ctx.strokeStyle = '#ffd36b';
          ctx.fillStyle = '#ffd36b';
          drawArrow(a.x,a.y,b.x,b.y,EPS);
          ctx.strokeStyle = '#ffb36b';
          ctx.fillStyle = '#ffb36b';
        }
      }
    }
  }

  // nodes
  for(const q of states){
    const p = pos.get(q); if (!p) continue;
    ctx.beginPath();
    ctx.fillStyle = '#261c1c';
    ctx.strokeStyle = '#5a4038';
    ctx.lineWidth = 2;
    ctx.arc(p.x,p.y,20,0,Math.PI*2);
    ctx.fill(); ctx.stroke();

    // accept double circle
    if (automaton.accept && automaton.accept.includes(q)){
      ctx.beginPath();
      ctx.arc(p.x,p.y,24,0,Math.PI*2);
      ctx.strokeStyle = '#63ffa1';
      ctx.stroke();
    }

    // start arrow
    if (automaton.start===q){
      ctx.beginPath();
      ctx.moveTo(p.x-44,p.y);
      ctx.lineTo(p.x-22,p.y);
      ctx.strokeStyle = '#ffd36b'; ctx.stroke();
    }

    ctx.fillStyle = '#fdeee7';
    ctx.font='bold 13px system-ui';
    ctx.fillText(q, p.x-12, p.y+4);
  }
}

/* ---------------- Build & visualize ---------------- */
let currentNFA=null, currentDFA=null;
const nfaCanvas = document.getElementById('nfaCanvas');
const dfaCanvas = document.getElementById('dfaCanvas');

function buildFromRegex(){
  const outErr = document.getElementById('vizErrors');
  outErr.textContent = '';
  try{
    const pat = text('vizRegex');
    const tokens = tokenizeRegex(pat);
    const post = toPostfix(tokens);
    const nfa = thompsonFromPostfix(post);

    // prepare for drawing
    currentNFA = { statesMap: nfa.states, start: nfa.start, accepts: nfa.accepts, states: [...nfa.states.keys()] };
    drawAutomaton(nfaCanvas, currentNFA);

    currentDFA = nfaToDfa({states:nfa.states, start:nfa.start});
    drawAutomaton(dfaCanvas, currentDFA);
  } catch (e){
    outErr.textContent = e.message;
  }
}

document.getElementById('btnBuild').addEventListener('click', buildFromRegex);

/* --------------- Animate subset construction ---------------- */
document.getElementById('btnAnimateSubset').addEventListener('click', ()=>{
  if (!currentDFA) { buildFromRegex(); if (!currentDFA) return; }
  const snaps = currentDFA.snapshots;
  let i=0;
  const ctx = dfaCanvas.getContext('2d');
  const saveDFA = JSON.parse(JSON.stringify(currentDFA));
  const timer = setInterval(()=>{
    drawAutomaton(dfaCanvas, saveDFA);
    if (i>=snaps.length){ clearInterval(timer); return; }
    const s = snaps[i++];
    // flash edge text
    ctx.fillStyle = '#ffd36b';
    ctx.font='bold 14px system-ui';
    ctx.fillText(`Processing: ${s.from} --${s.sym}→ ${s.to}  subset = {${s.subset.join(',')}}`, 10, 20);
  }, 700);
});

/* --------------- DFA simulation ---------------- */
function simulateDFA(dfa, str){
  let q = dfa.start;
  for(const ch of str){
    const row = dfa.transitions[q] || {};
    const next = row[ch] ?? row['.'] /* fallback */;

    if (next==null){
      // try matching via character class collapse: any transition whose key includes ch
      let found=null;
      for(const [k,v] of Object.entries(row)){
        if (k.length>1 && k.includes('-')){ // e.g., "a-z"
          // expand quick check
          const [a,_,b]=k;
          if (ch>=a && ch<=b){ found=v; break; }
        } else if (k.length>1){ // small set like @#_
          if (k.includes(ch)) { found=v; break; }
        }
      }
      if (found==null) return false;
      q = found;
    } else q = next;
  }
  return (dfa.accept||[]).includes(q);
}

document.getElementById('btnTestRegex').addEventListener('click', ()=>{
  if (!currentDFA) { buildFromRegex(); if (!currentDFA) return; }
  const ok = simulateDFA(currentDFA, text('vizTest'));
  showChip('vizTestResult', ok?'ok':'bad', ok?'ACCEPT':'REJECT');
});

/* --------------- Exporters ---------------- */
function exportJSON(dfa){
  return JSON.stringify({
    states: dfa.states,
    alphabet: dfa.alphabet || [],
    transitions: dfa.transitions,
    accept: dfa.accept,
    start: dfa.start
  }, null, 2);
}
function exportCPP(dfa){
  return `// DFA export
#include <bits/stdc++.h>
using namespace std;
struct DFA {
  vector<string> states = { ${dfa.states.map(s=>`"${s}"`).join(', ')} };
  string start = "${dfa.start}";
  unordered_set<string> accept = { ${dfa.accept.map(s=>`"${s}"`).join(', ')} };
  unordered_map<string, unordered_map<string,string>> trans = {
${Object.entries(dfa.transitions).map(([from,row])=>{
  return `    {"${from}", { ${Object.entries(row).map(([sym,to])=>`{"${sym}","${to}"}`).join(', ')} }}`;
}).join(',\n')}
  };
  bool run(const string &s){
    string q = start;
    for(char ch : s){
      auto it = trans[q].find(string(1,ch));
      if (it == trans[q].end()) {
        bool found=false;
        for (auto &kv : trans[q]) {
          const string &k = kv.first;
          if (k.size()==3 && k[1]=='-' && ch>=k[0] && ch<=k[2]) { q=kv.second; found=true; break; }
          else if (k.size()>1 && k.find(ch)!=string::npos) { q=kv.second; found=true; break; }
        }
        if (!found) return false;
      } else q = it->second;
    }
    return accept.count(q);
  }
};`;
}
function exportPy(dfa){
  return `# DFA export
class DFA:
    def __init__(self):
        self.states = ${JSON.stringify(dfa.states)}
        self.start = "${dfa.start}"
        self.accept = set(${JSON.stringify(dfa.accept)})
        self.trans = ${JSON.stringify(dfa.transitions, null, 2)}
    def run(self, s: str) -> bool:
        q = self.start
        for ch in s:
            row = self.trans.get(q, {})
            if ch in row:
                q = row[ch]
                continue
            found = None
            for k, v in row.items():
                if len(k)==3 and k[1]=='-' and k[0] <= ch <= k[2]:
                    found = v; break
                elif len(k)>1 and ch in k:
                    found = v; break
            if found is None: return False
            q = found
        return q in self.accept`;
}

document.getElementById('btnExportJSON').addEventListener('click', ()=>{
  if (!currentDFA) return;
  setText('exportArea', exportJSON(currentDFA));
});
document.getElementById('btnExportCPP').addEventListener('click', ()=>{
  if (!currentDFA) return;
  setText('exportArea', exportCPP(currentDFA));
});
document.getElementById('btnExportPy').addEventListener('click', ()=>{
  if (!currentDFA) return;
  setText('exportArea', exportPy(currentDFA));
});

/* ===========================================================
   PLAYGROUND: build DFA manually (drag & drop)
=========================================================== */
const pg = {
  canvas: document.getElementById('pgCanvas'),
  ctx: null,
  states: [], // {id, x,y, accept, start}
  edges: [],  // {from, to, label}
  selected: null,
  mode: 'select',
  edgeStart: null
};
pg.ctx = pg.canvas.getContext('2d');

function pgDraw(){
  const ctx = pg.ctx;
  ctx.clearRect(0,0,pg.canvas.width, pg.canvas.height);
  // edges
  ctx.strokeStyle = '#ffb36b'; ctx.fillStyle='#ffb36b'; ctx.lineWidth=1.5;
  pg.edges.forEach(e=>{
    const a = pg.states.find(s=>s.id===e.from);
    const b = pg.states.find(s=>s.id===e.to);
    if (!a||!b) return;
    const ang=Math.atan2(b.y-a.y,b.x-a.x);
    const r=22;
    const sx=a.x+r*Math.cos(ang), sy=a.y+r*Math.sin(ang);
    const tx=b.x-r*Math.cos(ang), ty=b.y-r*Math.sin(ang);
    ctx.beginPath(); ctx.moveTo(sx,sy); ctx.lineTo(tx,ty); ctx.stroke();
    ctx.beginPath();
    ctx.moveTo(tx,ty);
    ctx.lineTo(tx-8*Math.cos(ang-Math.PI/6), ty-8*Math.sin(ang-Math.PI/6));
    ctx.lineTo(tx-8*Math.cos(ang+Math.PI/6), ty-8*Math.sin(ang+Math.PI/6));
    ctx.closePath(); ctx.fill();
    ctx.fillStyle='#ffd9bd'; ctx.font='12px system-ui';
    ctx.fillText(e.label,(sx+tx)/2+4,(sy+ty)/2-4);
    ctx.fillStyle='#ffb36b';
  });

  // nodes
  pg.states.forEach(s=>{
    ctx.beginPath();
    ctx.fillStyle = pg.selected===s.id ? '#332020' : '#261c1c';
    ctx.strokeStyle = '#5a4038';
    ctx.lineWidth = 2;
    ctx.arc(s.x,s.y,20,0,Math.PI*2);
    ctx.fill(); ctx.stroke();

    if (s.accept){
      ctx.beginPath();
      ctx.arc(s.x,s.y,24,0,Math.PI*2);
      ctx.strokeStyle='#63ffa1'; ctx.stroke();
    }
    if (s.start){
      ctx.beginPath();
      ctx.moveTo(s.x-44,s.y);
      ctx.lineTo(s.x-22,s.y);
      ctx.strokeStyle='#ffd36b'; ctx.stroke();
    }
    ctx.fillStyle='#fdeee7'; ctx.font='bold 13px system-ui';
    ctx.fillText(s.id, s.x-12, s.y+4);
  });
}
pgDraw();

// interactions
let dragOff=null;
pg.canvas.addEventListener('mousedown', (e)=>{
  const rect=pg.canvas.getBoundingClientRect();
  const x=e.clientX-rect.left, y=e.clientY-rect.top;
  const hit = pg.states.find(s=>(x-s.x)**2+(y-s.y)**2<=20**2);
  if (pg.mode==='select'){
    pg.selected = hit? hit.id : null;
    if (hit) dragOff={dx:x-hit.x, dy:y-hit.y}; else dragOff=null;
    pgDraw();
  } else if (pg.mode==='edge'){
    if (hit){ pg.edgeStart = hit.id; }
  }
});
pg.canvas.addEventListener('mousemove', (e)=>{
  if (!dragOff || !pg.selected) return;
  const rect=pg.canvas.getBoundingClientRect();
  let x=e.clientX-rect.left, y=e.clientY-rect.top;
  const s = pg.states.find(z=>z.id===pg.selected);
  s.x = clamp(x - dragOff.dx, 30, pg.canvas.width-30);
  s.y = clamp(y - dragOff.dy, 30, pg.canvas.height-30);
  pgDraw();
});
pg.canvas.addEventListener('mouseup', (e)=>{
  if (pg.mode==='edge' && pg.edgeStart){
    const rect=pg.canvas.getBoundingClientRect();
    const x=e.clientX-rect.left, y=e.clientY-rect.top;
    const hit = pg.states.find(s=>(x-s.x)**2+(y-s.y)**2<=20**2);
    if (hit && hit.id!==pg.edgeStart){
      const label = text('pgEdgeLabel') || '.';
      pg.edges.push({from:pg.edgeStart, to:hit.id, label});
      pg.edgeStart=null; pg.mode='select';
      pgDraw();
    }
  }
  dragOff=null;
});

document.getElementById('pgAddState').addEventListener('click', ()=>{
  const id = 'q'+pg.states.length;
  pg.states.push({id, x: 80+pg.states.length*60, y: 80+((pg.states.length%2)*80), accept:false, start: pg.states.length===0});
  pgDraw();
});
document.getElementById('pgSetStart').addEventListener('click', ()=>{
  if (!pg.selected) return;
  pg.states.forEach(s=>s.start=false);
  pg.states.find(s=>s.id===pg.selected).start=true;
  pgDraw();
});
document.getElementById('pgToggleAccept').addEventListener('click', ()=>{
  if (!pg.selected) return;
  const s = pg.states.find(s=>s.id===pg.selected);
  s.accept=!s.accept; pgDraw();
});
document.getElementById('pgAddEdge').addEventListener('click', ()=>{
  pg.mode='edge';
});
document.getElementById('pgDelete').addEventListener('click', ()=>{
  if (!pg.selected) return;
  const id=pg.selected;
  pg.edges = pg.edges.filter(e=>e.from!==id && e.to!==id);
  pg.states = pg.states.filter(s=>s.id!==id);
  pg.selected=null; pgDraw();
});

function pgToDFA(){
  // convert playground graph into DFA structure
  const states = pg.states.map(s=>s.id);
  const startObj = pg.states.find(s=>s.start);
  const start = startObj? startObj.id : (states[0]||null);
  const accept = pg.states.filter(s=>s.accept).map(s=>s.id);
  const transitions = {};
  states.forEach(s=>transitions[s]={});
  pg.edges.forEach(e=>{
    transitions[e.from][e.label] = e.to;
  });
  const alpha = [...new Set(pg.edges.map(e=>e.label))];
  return { states, start, accept, transitions, alphabet: alpha };
}

document.getElementById('pgRun').addEventListener('click', ()=>{
  const dfa = pgToDFA();
  const ok = simulateDFA(dfa, text('pgPassword'));
  showChip('pgResult', ok?'ok':'bad', ok?'ACCEPT':'REJECT');
});

document.getElementById('pgExportJSON').addEventListener('click', ()=>{
  setText('pgExportArea', exportJSON(pgToDFA()));
});
document.getElementById('pgExportCPP').addEventListener('click', ()=>{
  setText('pgExportArea', exportCPP(pgToDFA()));
});
document.getElementById('pgExportPy').addEventListener('click', ()=>{
  setText('pgExportArea', exportPy(pgToDFA()));
});

/* ===========================================================
   PERFORMANCE LAB
=========================================================== */
const perfCanvas = document.getElementById('perfPlot');
const pctx = perfCanvas.getContext('2d');
let perfData = { x:[], regex:[], dfa:[] };

function drawPerf(){
  pctx.clearRect(0,0,perfCanvas.width,perfCanvas.height);
  const W=perfCanvas.width, H=perfCanvas.height;
  // axes
  pctx.strokeStyle = '#5a4038'; pctx.lineWidth=1.2;
  pctx.beginPath(); pctx.moveTo(50,H-40); pctx.lineTo(W-20,H-40); pctx.stroke();
  pctx.beginPath(); pctx.moveTo(50,20); pctx.lineTo(50,H-40); pctx.stroke();

  if (!perfData.x.length) return;

  const maxX = Math.max(...perfData.x);
  const maxY = Math.max(1, ...perfData.regex, ...perfData.dfa);
  const sx = (x)=> 50 + (W-80)*(x/maxX);
  const sy = (y)=> (H-40) - (H-80)*(y/maxY);

  // grid
  pctx.strokeStyle='#3a2b2b';
  for(let g=0; g<=5; g++){
    const yy = (H-40) - (H-80)*(g/5);
    pctx.beginPath(); pctx.moveTo(50,yy); pctx.lineTo(W-20,yy); pctx.stroke();
  }

  // lines
  const drawLine = (arr, color)=>{
    pctx.strokeStyle = color; pctx.lineWidth=2;
    pctx.beginPath();
    arr.forEach((y,i)=>{
      const x = perfData.x[i];
      const X = sx(x), Y = sy(y);
      if (i===0) pctx.moveTo(X,Y); else pctx.lineTo(X,Y);
    });
    pctx.stroke();
  };
  drawLine(perfData.regex, '#ff875f');
  drawLine(perfData.dfa,   '#63ffa1');

  // labels
  pctx.fillStyle = '#ffd9bd'; pctx.font='12px system-ui';
  pctx.fillText('Length', W/2-20, H-16);
  pctx.save(); pctx.translate(16,H/2); pctx.rotate(-Math.PI/2); pctx.fillText('Time (ms)', -24, 0); pctx.restore();

  // points
  const drawPts=(arr,color)=>{
    pctx.fillStyle=color;
    arr.forEach((y,i)=>{
      const x = perfData.x[i];
      pctx.beginPath(); pctx.arc(sx(x), sy(y), 3, 0, Math.PI*2); pctx.fill();
    });
  };
  drawPts(perfData.regex,'#ffb36b');
  drawPts(perfData.dfa,'#b8ffdb');
}

function genInput(seed, len){
  const out = [];
  for(let i=0;i<len;i++) out.push(seed[i%seed.length]);
  return out.join('');
}

document.getElementById('btnRunPerf').addEventListener('click', ()=>{
  document.getElementById('perfErrors').textContent='';
  perfData = {x:[], regex:[], dfa:[]};
  drawPerf();

  try{
    const jsRegex = new RegExp(text('perfRegex'));
    const dfaRegex = text('perfDFARegex');
    // build DFA once
    const tokens = tokenizeRegex(dfaRegex);
    const post = toPostfix(tokens);
    const nfa = thompsonFromPostfix(post);
    const dfa = nfaToDfa({states:nfa.states, start:nfa.start});

    const maxLen = parseInt(text('perfMax'),10);
    const step = parseInt(text('perfStep'),10);
    const seed = text('perfSeed') || 'aA0@';

    for(let L=step; L<=maxLen; L+=step){
      const s = genInput(seed, L);

      const t0 = performance.now();
      const ok1 = jsRegex.test(s);
      const t1 = performance.now();

      const t2 = performance.now();
      const ok2 = simulateDFA(dfa, s);
      const t3 = performance.now();

      perfData.x.push(L);
      perfData.regex.push(t1-t0);
      perfData.dfa.push(t3-t2);
    }
    drawPerf();

    // table
    const lines = ['Length\tRegex(ms)\tDFA(ms)'];
    for(let i=0;i<perfData.x.length;i++){
      lines.push(`${perfData.x[i]}\t${perfData.regex[i].toFixed(3)}\t${perfData.dfa[i].toFixed(3)}`);
    }
    document.getElementById('perfTable').textContent = lines.join('\n');

  } catch(e){
    document.getElementById('perfErrors').textContent = e.message;
  }
});

document.getElementById('btnClearPerf').addEventListener('click', ()=>{
  perfData = {x:[], regex:[], dfa:[]};
  document.getElementById('perfTable').textContent = '';
  drawPerf();
});

/* ===========================================================
   Wire basic actions
=========================================================== */
document.getElementById('vizRegex').value = '[A-Za-z0-9@#]+';
document.getElementById('vizTest').value = 'Welcome2025@';

buildFromRegex(); // initial render
drawPerf();