Skip to content

FirstSet computation uses a naive full-rescan fixed-point instead of a worklist algorithm #486

Description

@halotukozak

Found during an algorithmic-complexity / collections audit ahead of 1.0.0.

`src/halotukozak/alpaca/internal/parser/FirstSet.scala:32-36`:

```scala
@tailrec
private def loop(productions: List[Production], firstSet: FirstSet): FirstSet =
val newFirstSet = productions.foldLeft(firstSet)(addImports)
if firstSet == newFirstSet then newFirstSet
else loop(productions, newFirstSet)
```

This is the textbook fixed-point algorithm for computing FIRST sets, but it re-scans every production on every iteration until nothing changes, rather than a worklist that only reprocesses productions whose relevant non-terminal's FIRST set actually changed on the last pass. Correct, but not asymptotically optimal -- worst case is O(iterations × productions) where a worklist version would do meaningfully less redundant work on grammars with many independent non-terminals.

This only affects compile-time (macro-time grammar table construction), not anything a user's program pays at runtime. Not a problem for the grammar sizes exercised by the current test suite/benchmarks, but worth tracking as a known optimization opportunity if large user grammars ever show up as slow to compile -- same theme as #465/#466/#462.

Suggested fix: switch to a worklist-based fixed-point (e.g. seed the worklist with all productions, and after updating a non-terminal's FIRST set, only re-enqueue productions whose RHS starts with that non-terminal).

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions