flowgraph: control-flow graphs from the compiler IR

# =============================================================================
# flowgraph: control-flow graph visualizer (concatenate after the compiler
# libs + lib/html.patlang). Lowers a PatLang program with the self-hosted
# compiler, splits each function's IR into basic blocks, and renders the
# blocks and jump edges as SVG in an HTML page.
# =============================================================================

make a function called contains_num takes xs, v returns r
  let i = 0
  while i < xs.length do
    if xs[i] == v then
      return true
    end
    let i = i + 1
  end
  return false
end

make a function called instr_text takes ins returns s
  let s = ins[0]
  if ins.length > 1 then
    let s = s + " " + ins[1]
  end
  if ins.length > 2 then
    let s = s + " " + ins[2]
  end
  return s
end

make a function called is_jump takes tag returns r
  return (tag == "Jump") or (tag == "JumpIfFalse") or (tag == "Return")
end

# Render one function's CFG as SVG appended to builder b; returns block count
make a function called render_func takes b, f returns blocks
  let instrs = f[3]
  let n = instrs.length
  # block starts: 0, every jump target, and every instr after a jump
  let starts = [0]
  let i = 0
  while i < n do
    let ins = instrs[i]
    let tag = ins[0]
    if (tag == "Jump") or (tag == "JumpIfFalse") then
      if not contains_num(starts, ins[1]) then
        let starts = list_push(starts, ins[1])
      end
      if not contains_num(starts, i + 1) then
        let starts = list_push(starts, i + 1)
      end
    end
    let i = i + 1
  end
  # block index for an instruction = count of starts <= idx that we pass
  # build blocks in order by scanning
  let rowh = 26
  let y = 10
  sb_push(b, "<h3>" + html_escape(f[1]) + "</h3>" + nl())
  let blockTops = []
  let blockIds = []
  let i = 0
  let bod = sb_new()
  let edges = sb_new()
  let blocks = 0
  while i < n do
    if contains_num(starts, i) then
      let blocks = blocks + 1
      let blockTops = list_push(blockTops, y)
      let blockIds = list_push(blockIds, i)
      sb_push(bod, "<text x='16' y='" + (y + 16) + "' class='bh'>B@" + i + "</text>" + nl())
      let y = y + rowh
    end
    let ins = instrs[i]
    sb_push(bod, "<text x='28' y='" + (y + 14) + "'>" + html_escape(instr_text(ins)) + "</text>" + nl())
    let tag = ins[0]
    if (tag == "Jump") or (tag == "JumpIfFalse") then
      # edge from this row to the target block header (drawn after layout)
      let edges = edges
      sb_push(edges, "" + (y + 8) + " " + ins[1] + " " + tag + "\n")
    end
    let y = y + rowh
    let i = i + 1
  end
  let height = y + 20
  sb_push(b, "<svg viewBox='0 0 560 " + height + "' width='560' height='" + height + "' xmlns='http://www.w3.org/2000/svg'>" + nl())
  # draw jump edges as curves on the right margin
  let elist = sb_str(edges)
  let eh = str_intern(elist)
  let elen = sc_len(eh)
  let k = 0
  let word = sb_new()
  let fields = []
  while k <= elen do
    let c = sc_code(eh, k)
    if (c == 32) or (c == 10) or (c == -1) then
      let w = sb_str(word)
      let word = sb_new()
      if w != "" then
        let fields = list_push(fields, w)
      end
      if (c == 10) and (fields.length == 3) then
        # fields: fromY targetInstr tag
        let fromY = to_num(fields[0])
        let tIdx = to_num(fields[1])
        # find target block top
        let ti = 0
        let tY = 10
        while ti < blockIds.length do
          if blockIds[ti] == tIdx then
            let tY = blockTops[ti]
          end
          let ti = ti + 1
        end
        let color = "#d64"
        if fields[2] == "Jump" then
          let color = "#48c"
        end
        sb_push(b, "<path d='M 330 " + fromY + " C 520 " + fromY + ", 520 " + (tY + 10) + ", 335 " + (tY + 10) + "' fill='none' stroke='" + color + "' marker-end='url(#arr)'/>" + nl())
        let fields = []
      end
    else
      sb_push(word, sc_char(eh, k))
    end
    let k = k + 1
  end
  sb_push(b, "<defs><marker id='arr' viewBox='0 0 8 8' refX='7' refY='4' markerWidth='6' markerHeight='6' orient='auto'><path d='M 0 0 L 8 4 L 0 8 z' fill='#888'/></marker></defs>" + nl())
  sb_push(b, sb_str(bod))
  sb_push(b, "</svg>" + nl())
  return blocks
end

# Reads a source spec, supporting "lib.patlang+demo.patlang" bundling for
# programs that need a library concatenated ahead of their driver (mirrors
# patbuild's manifest convention, kept independent to avoid file coupling).
make a function called read_maybe_bundle takes spec returns source
  let b = sb_new()
  let cur = sb_new()
  let i = 0
  let first = true
  while i <= spec.length do
    let c = char_code(spec, i)
    if (c == 43) or (c == -1) then
      let piece = sb_str(cur)
      let cur = sb_new()
      if piece != "" then
        if not first then
          sb_push(b, chr(10))
        end
        sb_push(b, read_file(piece))
        let first = false
      end
    else
      sb_push(cur, spec[i])
    end
    let i = i + 1
  end
  return sb_str(b)
end

# Renders one program's functions as a labelled section; returns block count.
make a function called render_program_section takes b, label, spec returns blocks
  let source = read_maybe_bundle(spec)
  let toks = tokenize(source)
  let ast = parse_program(toks)
  let ir = lower_program(ast)
  let funcs = ir[2]
  sb_push(b, "<h2 id='" + label + "'>" + html_escape(label) + "</h2>" + nl())
  sb_push(b, "<p class='label'><code>" + html_escape(spec) + "</code> &mdash; " + funcs.length + " function(s)</p>" + nl())
  let i = 0
  let total = 0
  while i < funcs.length do
    let total = total + render_func(b, funcs[i])
    let i = i + 1
  end
  return total
end

# ---- driver ----
# Usage: flowgraph <output.html> [input1] [input2] ...
# With no inputs, renders a curated set of the portfolio's example programs
# into one navigable page (this is how the portfolio card invokes it).
let args = argv()
let output = "portfolio/flowgraph.html"
let specs = []
if args.length >= 1 then
  let output = args[0]
end
if args.length >= 2 then
  let k = 1
  while k < args.length do
    let specs = list_push(specs, args[k])
    let k = k + 1
  end
end
if specs.length == 0 then
  let specs = [
    "self_hosting/examples/fib_bench.patlang",
    "self_hosting/examples/contracts_demo.patlang",
    "self_hosting/lib/pos.patlang+self_hosting/examples/pos_demo.patlang",
    "self_hosting/examples/feature_demo.patlang"
  ]
end

let nav = sb_new()
sb_push(nav, "<p>")
let i = 0
while i < specs.length do
  if i > 0 then
    sb_push(nav, " &middot; ")
  end
  sb_push(nav, "<a href='#" + specs[i] + "'>" + html_escape(specs[i]) + "</a>")
  let i = i + 1
end
sb_push(nav, "</p>" + nl())

let body = sb_new()
sb_push(body, "<h1>PatLang control-flow graphs</h1>" + nl())
sb_push(body, "<p>Basic blocks and jump edges recovered from the self-hosted compiler's own IR, one section per program. Red curves are conditional (JumpIfFalse), blue are unconditional.</p>" + nl())
sb_push(body, "<style>svg text { font: 12px monospace; fill: currentColor; } svg .bh { font-weight: bold; }</style>" + nl())
sb_push(body, sb_str(nav))

let total_funcs = 0
let total_blocks = 0
let i = 0
while i < specs.length do
  let total_blocks = total_blocks + render_program_section(body, specs[i], specs[i])
  let i = i + 1
end

let page = html_page("PatLang flow graphs", sb_str(body), "")
write_file(output, page)
print("[flowgraph] " + specs.length + " program(s), " + total_blocks + " basic blocks -> " + output)