solidity-lean/SolidCore/Witness/RecursiveStructMemConstruct.lean
Dan Robinson c027a5f67d Fix #160 RECURSIVE-STRUCT-MEM-CONSTRUCT: memory-construct a self-referential struct
solc 0.8.35 accepts and executes memory-constructing a self-referential
struct (`struct Node { uint256 v; Node[] kids; } ... Node memory n =
Node(1, new Node[](0)); return n.v;` => 1). The model's CHECKER accepted the
program (`importedContractAccepted = true`) but the executable lowering could
not build the memory construction, so `toCoreContractFor?` returned none and
`f()` errored with `TypeError.unsupported "checked executable ..."` — an
over-reject / unimplemented that is replay-reachable.

Root cause: `Ty.resolveStructs` inlines a struct `Ty.user` path into
`Ty.struct path <fields>` down to a fixed fuel budget. For a self-referential
struct that expansion never terminates, so resolution bottoms out at a
fuel-dependent depth, leaving a residual `Ty.user Node` wherever the budget
ran out. The constructor-argument cast (resolved as the surface pass descends
the expression tree) and the declared memory-variable type (resolved from the
top of the type) therefore bottom out at DIFFERENT residual depths. The
`Ty.tuple actualFields == Ty.struct _ expectedFields` check in the
Executable-side `Ty.canImplicitlyConvert` then compared two structurally
different multi-megabyte trees, reported a spurious type mismatch, and the
whole contract failed to lower. Non-recursive structs resolve fully (no
residual), so H1 (value-type dyn-array member) and H2 (dyn-array of a
different struct) always compared equal and already lowered.

Fix (SolidCore/Solidity/Interface.lean): compare the two `resolveStructs`
expansions with `Ty.sameNominalType`, a fuel-tolerant nominal equality that
matches struct/user nodes by PATH and STOPS at each struct boundary — sound
(the inlined fields are redundant given the path + struct env) and
fuel-independent (a residual `Ty.user p` matches a further-expanded
`Ty.struct p _`). Used in the tuple<->struct arms of the Executable-side
`Ty.canImplicitlyConvert` and `Ty.commonImplicit?`. Only the lowering
predicate changed; the acceptance predicate (TypeCheck namespace) is untouched,
so nothing becomes over-accepted, and non-recursive struct behaviour is
unchanged.

Isolation ladder preserved and pinned (Lean execution + real solc/EVM Forge
lane): G3 construct => 1 (the fix), H1 => 2, H2 => 3, G1 storage write => 5.

- SolidCore/Witness/RecursiveStructMemConstruct.lean: witness exercising G3 +
  the isolation ladder end-to-end (imported in SolidCore.lean).
- tests/forge-harness/recursive-struct-mem-construct/: Forge lane (real solc
  0.8.35 + EVM ground truth) + manifest.json case (replay-gated).

Full `lake build` green (1120 jobs), FuelMonotonicity + witnesses included.

Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
(cherry picked from commit d2da349d539adde66bb9d2ef919099684b97f25a)
2026-07-10 19:11:07 -07:00

179 lines
8.9 KiB