Module type_solver 

Type-resolution pass — bipartite worklist solver following TVM Relay’s type_solver.h design, adapted to Rust.

Shape

Two arenas: type nodes (one per value position) and relation nodes (one per TypeRelation instance on each [AtomicOpDecl]). Cross-linked via rel_set back-edges. The worklist holds relations ready to (re)run.

Algorithm

1. Seed. Allocate a type node for every value name in the graph (function inputs, op outputs). Mark each with its declared bound (TYPE_ANY if none).
2. Instantiate relations. For each NodeProto in the graph, look up its AtomicOpDecl.type_relations and allocate a relation node per declared TypeRelation. Each relation points at the type nodes for the ports it participates in. Type nodes track back-edges via rel_set.
3. Drain. Pop a relation from the worklist, run it. RelationResult dictates the next move:
   • Refined → requeue every relation in the refined type nodes’ rel_set.
   • Satisfied → remove from the worklist permanently.
   • Defer → leave in the worklist (will retry only when something else refines a participating type).
   • Failed → abort with a TypeError.
4. Fixpoint. When the worklist is empty (or only Defers remain that no new refinement could activate), check the post-condition: every type node resolves to a concrete leaf. Otherwise → UnresolvedType.

Scope

Currently handles TypeRelation::SameElementType and TypeRelation::Elementwise — the two highest-frequency relations covering most arithmetic + reduction ops. Other variants (BroadcastShape, SameType, ReduceOver, Custom) plug in by extending the per-variant handler match inside the solver’s internal run_relation dispatch.

Structs

TypeSolution

Solver output: every value name in the graph maps to its resolved concrete TypeNode.

TypeSolver

Bipartite type-resolution solver.

Enums

TypeError

Errors the solver may report.