close
Skip to content

[Enhancement]: Consider BFS worklist order for more predictable coverage #66

@forketyfork

Description

@forketyfork

Description

The analysis worklist uses ArrayList.pop() (LIFO) and ArrayList.append() (adds to end), giving DFS traversal order. While DFS is fine for most analyses and can be more cache-friendly, it can pathologically explore deep paths before wide fan-outs, potentially hitting the step limit before discovering all reachable nodes at shallow depths. BFS (using a deque or ring buffer) would provide more predictable coverage when the step limit is tight.

This is a design choice rather than a bug, but worth being intentional about — especially as analysis complexity grows.

Suspected Area

src/engine/analysis/engine.zig — lines 287 (append) and 291 (pop).

Acceptance Criteria

  • Document the traversal order choice explicitly (if keeping DFS)
  • Or switch to BFS/configurable order with benchmarks showing impact
  • The change does not break existing tests

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions