gauge — a tiny OCaml static complexity estimator

What it is

Gauge is a prototype static analyzer that inspects OCaml source and produces conservative asymptotic complexity estimates for top-level code and functions.

Key components

• Frontend: ppxlib-based parsing of OCaml source (uses the same Parsetree types).
• Inference: a small AST walker with a cost algebra (polynomial degree + log-power).
• Contracts: simple inline annotations in comments (* @complexity O(n) *).
• Reporter: compares declared vs inferred complexities and prints OK/MISMATCH.

Cost model

• Represented as type cost = { degree : int; log : int }.
• Constants: o1, on, on2, olog, ounk.
• Operations: max_cost, mul_cost, seq_cost.

Inference strategy

• Walk the AST and combine child costs with seq_cost (max).
• Treat loops and List.* traversals as multiplicative by O(n).
• Detect let rec groups (top-level and local) and conservatively map their names to O(n) when they may be called recursively.
• Propagate callee costs to callers via a simple fixed-point iteration across top-level functions.
• Heuristics: AST-based collection of local let rec names, with a printed-expression fallback when needed.
• Enhanced recursive analysis: Distinguishes tree-like recursion (e.g., traversals) from overlapping (e.g., Fibonacci), yielding more accurate O(n) vs O(n²) results.
• Option/Result module support: Recognizes and infers O(1) for all standard Option/Result operations.

Why conservative?

Gauge prefers sound, conservative over-approximation. Where the analyzer cannot be sure, it reports a higher cost.

How to build & run tests

Requirements: dune, OCaml toolchain (same version used by the project).

Build and run all expect tests:

dune build
dune runtest

Developer notes

• The main inference logic is in lib/infer.ml.
• Tests are under test/ and use ppx_expect style expect tests.
• To add more patterns, update expr_cost_with_env_with and the local-rec name collection.
• See docs/ENHANCED_RECURSIVE_ANALYSIS.md for details on the improved recursion heuristics.

Next steps / Improvements

• Implement a basic name-resolution pass to resolve call-sites to their bindings (will improve precision).
• Handle higher-order patterns and known library traversals more precisely.
• Add more tests (tail recursion, higher-order use, nested modules).
• Improve accumulated cost tracking for nested loops and list concatenations.

License

MIT