Skip to content

armgit / bento

Public Imported from GitHub
0

Bento, the office suite that fits in a file

15.8 KB
Raw Blame
// SPDX-License-Identifier: MIT
// Copyright (c) 2026 The Bento authors

// Tokens come from the kernel tokenizer — the zero-cost tier. The format still
// carries the grammar/theme asset seam (CodeElement.grammarAssetId/themeAssetId)
// for a future signed-extension tier with real TextMate grammars; the diff
// below never cared where tokens come from, which is what makes both tiers
// share one engine.
// import type, deliberately: only type names are used, and the erased import
// is what lets scripts/test-codediff.ts run this file under plain node
// (extensionless runtime imports do not resolve there).
import type { BentoDoc, Slide } from "./model.ts"
import { tokenize, type Tok } from "../../kernel/src/tokenize.ts"

// Tokens that usually occur in pairs are related to each other.
// This way, if one is matched then the other is also matched automatically.
const RELATED_TOKENS_BEGIN = new Set<string>(['{', '[', '('])
const RELATED_TOKENS_END = new Set<string>(['}', ']', ')'])
const RELATED_SEARCH_LIMIT = 2

// The stable token that we can diff between slides.

export class Token {

  /* The morph id. */
  _id: string | undefined
  // Explicit fields, not constructor parameter properties: the repo's test
  // rigs run TypeScript sources under plain node, whose type stripping cannot
  // execute parameter properties (scripts/test-codediff.ts imports this file).
  readonly content: string
  readonly scopes: Array<string>
  readonly lineNumber: number
  readonly offset: number
  // Related tokens when applicable.
  // This is only populated when the content is in the `RELATED_TOKENS_*` set.
  _related: Token|undefined
  _relatedIndex: number|undefined

  constructor(content: string, scopes: Array<string>, lineNumber: number, offset: number) {
    this.content = content
    this.scopes = scopes
    this.lineNumber = lineNumber
    this.offset = offset
    this._id = undefined
    this._related = undefined
    this._relatedIndex = undefined
  }

  morphId(): string {
    return this._id!
  }

  setMorphId(id: string) {
    this._id = id
  }

  depth(): number {
    return this.scopes.length
  }

  key(): string {
    // Calls and plain identifiers share an identity bucket. The tokenizer
    // classes a word by its role — `render(` is a call, `.then(render)` a
    // plain reference — so the SAME word flips class exactly when a refactor
    // changes style (callback -> point-free -> await). Keying on the class
    // made such a word die and respawn instead of travelling; the audience
    // pairs tokens by their glyphs, not their colour, so identity does too.
    // Rendering still uses the true class — a paired token recolours at rest.
    const buckets = this.scopes.map((sc) => (sc === 'f' ? 'x' : sc))
    const json = {
      content: this.content,
      scopes: buckets
    }
    return JSON.stringify(json)
  }

  assignRelated(related: Token, relatedIndex: number) {
    this._related = related
    this._relatedIndex = relatedIndex
  }

  /**
   * Adapt one kernel token, splitting multiline tokens at newlines FIRST.
   *
   * The tokenizer's contract allows block comments, triple-quoted strings and
   * whitespace runs to carry newlines. Rendered tokens with ink must become
   * atomic inline-level boxes to be animatable (a transform does nothing to a
   * non-replaced inline element), and a newline inside an atomic box stops
   * breaking the line under `white-space: pre` — a Python docstring would
   * collapse its whole block to one rendered line. Splitting HERE, before
   * identity assignment, keeps one diff token per rendered span; splitting in
   * the renderer instead would put one morph id on several spans and corrupt
   * the offset map. Concatenating the split pieces reproduces the original
   * token exactly, so the tokenizer's lossless guarantee survives.
   */
  static fromTok(tok: Tok, lineNumber: number, offset: number): Token[] {
    const out: Token[] = []
    let line = lineNumber
    let off = offset
    for (const piece of tok.v.split(/(\n)/)) {
      if (!piece) continue
      out.push(new Token(piece, [tok.t], line, off))
      if (piece === '\n') { line += 1; off = 0 } else off += piece.length
    }
    return out
  }
}

// Diff states

/** Initial diff state. */
export const Empty = { kind: 'empty' }

/** Match */

export type Match = {
  kind: 'match',
  previousIdx: number,
  previous: Token,
  current: Token,
  currentIdx: number,
}

/** Insert */

export type Insert = {
  kind: 'insert',
  token: Token,
  index: number,
}

/** Delete */

export type Delete = {
  kind: 'delete',
  token: Token,
  index: number,
}

/** Discriminated Union of all diff states. */

export type State = typeof Empty | Match | Insert | Delete

/** Diff algorithm. */

export class HeckelDiff {

  /** A counter for morph ids. */
  static count: number = 0

  private readonly doc: BentoDoc

  constructor(doc: BentoDoc) {
    this.doc = doc
  }

  /**
   * @returns a `Map` of `states` grouped by `slideIdx` for a given morph id (`mid`).
   */
  public computeDiffs(mid: string | undefined): Map<number, State[]> {
    // Output
    let states: Map<number, State[]> = new Map<number, State[]>()
    const slides = this.doc.slides
    // Parse the slides only once
    // Parsed is a 2-D array. First indexed by the slideIndex, then flattened tokens.
    const parsed: Array<Token[]> = []
    for (const slide of slides) {
      const tokens = HeckelDiff.parse(this.doc, slide, mid)
      parsed.push(tokens)
    }
    // For all the tokens in the first code slide, assign them stable ids.
    const firstIdx = HeckelDiff.zipIndex(0, parsed)
    let tokens: Token[] = []
    // !== undefined, not truthiness: slide index 0 is falsy, and a morph group
    // whose first code slide is the deck's first slide got no ids at all.
    if (firstIdx !== undefined) {
      // Reset counts before recomputing stable ids
      HeckelDiff.count = 0
      tokens = parsed[firstIdx]
      for (const token of tokens) {
        token.setMorphId(HeckelDiff.generateMorphId())
      }
      states.set(firstIdx, HeckelDiff.tokensAsState(tokens))
    }
    // Find slide pairs to diff.
    const zipped = HeckelDiff.zip(parsed)
    if (zipped.length > 0) {
      for (const entry of zipped) {
        // Flatten to 1-D to make the diffing easier
        const previous = parsed[entry[0]]
        const current = parsed[entry[1]]
        const [_, statesC] = HeckelDiff.computeDiff(previous, current)
        states.set(entry[1], statesC)
      }
    }
    return states
  }

  static generateMorphId(): string {
    this.count += 1
    return `m-code-token-${this.count}`
  }

  private static parse(_doc: BentoDoc, slide: Slide, mid: string|undefined): Token[] {
    const tokens: Token[] = []
    for (const el of slide.elements) {
      // The effective morph key is morphId || id, matching render.ts — a lone
      // code element with no explicit morphId still diffs against its
      // duplicate-a-slide twins (the duplicate idiom shares ids).
      if (el.type === 'code' && (el.morphId ?? el.id) === mid) {
        let line = 0
        let off = 0
        for (const tok of tokenize(el.content ?? '', el.grammarName ?? 'js')) {
          const split = Token.fromTok(tok, line, off)
          tokens.push(...split)
          const last = split[split.length - 1]
          if (last) {
            if (last.content === '\n') { line = last.lineNumber + 1; off = 0 }
            else { line = last.lineNumber; off = last.offset + last.content.length }
          }
        }
      }
    }
    return tokens
  }

  private static computeDiff(previous: Token[], current: Token[]): [Array<State>, Array<State>] {
    const anchMapP = HeckelDiff.anchors(previous)
    const anchMapC = HeckelDiff.anchors(current)
    // Symbol Tables
    const statesP: Array<State> = Array(previous.length).fill(Empty)
    const statesC: Array<State> = Array(current.length).fill(Empty)
    // Phase 1: Find unique anchors such that frequency = 1 in both lists.
    // That is a match.
    for (let i = 0; i < current.length; i += 1) {
      const token = current[i]
      if (anchMapP.has(token.key()) && anchMapC.has(token.key())) {
        const anchP = anchMapP.get(token.key())!
        const anchC = anchMapC.get(token.key())!
        const match: Match = {
          kind: 'match',
          previousIdx: anchP.index,
          previous: previous[anchP.index],
          currentIdx: anchC.index,
          current: current[anchC.index]
        }
        // Propagate morph id
        current[anchC.index].setMorphId(previous[anchP.index].morphId())
        statesP[anchP.index] = match
        statesC[anchC.index] = match
      }
    }
    // Phases 2 & 3 — spread from every anchor, breadth-first. One ring per
    // round: each match may claim ONE neighbour per direction per round, so a
    // token is claimed by its NEAREST anchor, not by whichever cascade happens
    // to run first. The previous greedy sweeps lost the shared-prefix swap:
    //
    //   const a = one()          const b = two()
    //   const b = two()    ->    const a = one()
    //
    // The header cascade (function f() { ...) walked forward straight into the
    // first `const` and paired it top-to-top, three steps from its anchor —
    // while `b`, only two steps away, was still waiting for the backward
    // sweep. Its own `const` then found the previous side already claimed and
    // was minted fresh: it vanished for 40% of the morph and faded back in,
    // on screen, in a deck. Distance-first, each `const` is claimed by the
    // anchor on its own line and travels with it. Claims never overwrite
    // (both sides must be unclaimed), so equal-distance conflicts — the
    // genuinely ambiguous ones — resolve deterministically to the earlier
    // token, and everything a cascade could reach is still reached.
    let frontier: number[] = []
    for (let i = 0; i < statesC.length; i += 1) {
      if (statesC[i].kind === 'match') frontier.push(i)
    }
    while (frontier.length > 0) {
      const next: number[] = []
      for (const ci of frontier) {
        const m = statesC[ci] as Match
        for (const step of [1, -1]) {
          const nc = ci + step
          const np = m.previousIdx + step
          if (nc < 0 || nc >= statesC.length || statesC[nc].kind !== 'empty') continue
          if (np < 0 || np >= previous.length || statesP[np].kind !== 'empty') continue
          if (current[nc].key() !== previous[np].key()) continue
          const match: Match = {
            kind: 'match',
            previousIdx: np,
            previous: previous[np],
            currentIdx: nc,
            current: current[nc]
          }
          // Propagate morph id
          current[nc].setMorphId(previous[np].morphId())
          statesP[np] = match
          statesC[nc] = match
          next.push(nc)
          // Check for related tokens
          const rp = previous[np]._relatedIndex
          const rc = current[nc]._relatedIndex
          if (current[nc]._related && previous[np]._related && rc !== undefined && rp !== undefined) {
            if (statesP[rp].kind !== 'empty') continue
            if (statesC[rc].kind !== 'empty') continue
            const related: Match = {
              kind: 'match',
              previousIdx: rp,
              previous: previous[np]._related,
              currentIdx: rc,
              current: current[nc]._related
            }
            // Propagate morph id
            related.current.setMorphId(related.previous.morphId())
            statesP[rp] = related
            statesC[rc] = related
            next.push(rc)
          }
        }
      }
      frontier = next
    }
    // Phase 4: Final pass.
    // Anything that did not match in:
    // - statesP = Delete
    // - statesC = Insert
    for (let i = 0; i < statesP.length; i += 1) {
      if (statesP[i].kind === 'empty') {
        const del: Delete = {
          kind: 'delete',
          index: i,
          token: previous[i]
        }
        statesP[i] = del
      }
    }
    for (let i = 0; i < statesC.length; i += 1) {
      if (statesC[i].kind === 'empty') {
        const insert: Insert = {
          kind: 'insert',
          index: i,
          token: current[i]
        }
        // For inserts generate a new morph id
        current[i].setMorphId(HeckelDiff.generateMorphId())
        statesC[i] = insert
      }
    }
    return [statesP, statesC]
  }

  /**
   * Keys occurring EXACTLY once, with their index. Counted over the full list:
   * the previous add-then-delete dance re-added a key on its third occurrence,
   * so any token repeating an odd number of times — a third `)` is enough —
   * became a false "unique" anchor and Phase 1 paired wrong positions.
   *
   * We also use this opportunity to relate tokens that ought to occur in matching pairs.
   * Punctuation tokens like `{`, `(`, and `[` have a matching `}`, `)`, and `]` respectively.
   * Comments are always prefixed by a comment preamble, so we don't have to worry about scopes.
   * Regression: scripts/test-codediff.ts.
   */
  private static anchors(tokens: Token[]): Map<string, { frequency: number, index: number }> {
    // Keep track of related tokens.
    // Useful to track matching pairs of tokens so we can consume them cleanly.
    const stack = new Array<{token: Token, index: number}>()
    const freq = new Map<string, { frequency: number, index: number }>()
    for (let i = 0; i < tokens.length; i += 1) {
      const token = tokens[i]
      const key = token.key()
      const content = token.content
      if (RELATED_TOKENS_BEGIN.has(content)) {
        stack.push({token: token, index: i})
      }
      if (RELATED_TOKENS_END.has(content)) {
        var j = 0
        while(j < RELATED_SEARCH_LIMIT) {
          const begin = stack.pop()
          if (!begin) break
          if (HeckelDiff.areRelated(begin.token, token)) {
            // Relate the tokens to each other.
            begin.token.assignRelated(token, i)
            token.assignRelated(begin.token, begin.index)
            break
          }
          j += 1
        }
      }
      const e = freq.get(key)
      if (e) e.frequency += 1
      else freq.set(key, { frequency: 1, index: i })
    }
    for (const [key, e] of freq) if (e.frequency !== 1) freq.delete(key)
    return freq
  }

  private static areRelated(first: Token, second: Token): boolean {
    // It's enough to only check for the content here.
    // We are intentionally not making too many assumptions around the Token
    // scopes here, to keep the Tokenizer open-ended. We are also intentionally
    // skipping over `<` and `>` because without suitable scopes we might confuse
    // them with comparison operators.
    if (first.content === '{' && second.content === '}') return true
    if (first.content === '[' && second.content === ']') return true
    if (first.content === '(' && second.content === ')') return true
    return false
  }

  private static zip(parsed: Array<Token[]>): Array<number[]> {
    const pairs: Array<number[]> = []
    let index = 0
    let previousIdx = HeckelDiff.zipIndex(index, parsed)
    if (previousIdx === undefined) return pairs
    let i = previousIdx + 1
    while (i < parsed.length) {
      let currentIdx = HeckelDiff.zipIndex(i, parsed)
      if (currentIdx === undefined) break
      else {
        pairs.push([previousIdx, currentIdx])
        previousIdx = currentIdx
        i = currentIdx + 1
      }
    }
    return pairs
  }

  private static zipIndex(start: number, parsed: Array<Token[]>): number | undefined {
    for (let i = start; i < parsed.length; i += 1) {
      const lineTokens = parsed[i]
      if (lineTokens && lineTokens.length > 0) return i
    }
    return undefined
  }

  private static tokensAsState(tokens: Token[]): State[] {
    const inserts: State[] = []
    for (let i = 0; i < tokens.length; i += 1) {
      const token = tokens[i]
      const insert: Insert = {
        kind: 'insert',
        index: i,
        token: token
      }
      inserts.push(insert)
    }
    return inserts
  }
}