packages/deriver/tests/Unit/Deriver/Evaluator/Execution/Memory/MemoryTest.php

1<?php
2
3declare (strict_types=1);
4
5namespace Tests\Unit\Deriver\Evaluator\Execution\Memory;
6
7use Deriver\Deriver;
8use Deriver\Deriver\Candidate\ResultRef;
9use Deriver\Deriver\Candidate\Snapshot;
10use Deriver\Deriver\Candidate\Statistics;
11use Deriver\Deriver\Contributions;
12use Deriver\Deriver\DeriverConfig;
13use Deriver\Deriver\Evaluator\Call\Evaluators;
14use Deriver\Deriver\Evaluator\Call\Extensions;
15use Deriver\Deriver\Evaluator\Call\Registrations;
16use Deriver\Deriver\Evaluator\Call\StateRegistry;
17use Deriver\Deriver\Evaluator\EvaluatorConfig;
18use Deriver\Deriver\Evaluator\Evidence\Frontier;
19use Deriver\Deriver\Evaluator\Execution\Call\ArgumentBinding;
20use Deriver\Deriver\Evaluator\Execution\Call\ArgumentOrder;
21use Deriver\Deriver\Evaluator\Execution\Call\TypeBinding;
22use Deriver\Deriver\Evaluator\Execution\Call\TypeCheck;
23use Deriver\Deriver\Evaluator\Execution\Completion\Alternative;
24use Deriver\Deriver\Evaluator\Execution\Completion\Assessment;
25use Deriver\Deriver\Evaluator\Execution\Completion\Completion;
26use Deriver\Deriver\Evaluator\Execution\Completion\StorageSnapshot;
27use Deriver\Deriver\Evaluator\Execution\Context;
28use Deriver\Deriver\Evaluator\Execution\Control\ObservationLimit;
29use Deriver\Deriver\Evaluator\Execution\Control\StateJoin;
30use Deriver\Deriver\Evaluator\Execution\Control\Unwinding;
31use Deriver\Deriver\Evaluator\Execution\Demand\Discovery;
32use Deriver\Deriver\Evaluator\Execution\Dependencies;
33use Deriver\Deriver\Evaluator\Execution\Evaluator;
34use Deriver\Deriver\Evaluator\Execution\EvaluatorConfig as ExecutionEvaluatorConfig;
35use Deriver\Deriver\Evaluator\Execution\InstructionTransfer;
36use Deriver\Deriver\Evaluator\Execution\Memory\LiveArray;
37use Deriver\Deriver\Evaluator\Execution\Memory\Location;
38use Deriver\Deriver\Evaluator\Execution\Memory\Materialization;
39use Deriver\Deriver\Evaluator\Execution\Memory\Memory;
40use Deriver\Deriver\Evaluator\Execution\Memory\ReferenceConstraint;
41use Deriver\Deriver\Evaluator\Execution\Memory\Slots\SlotReference;
42use Deriver\Deriver\Evaluator\Execution\Memory\StorageCapture;
43use Deriver\Deriver\Evaluator\Execution\ObservationCollector;
44use Deriver\Deriver\Evaluator\Execution\Offset\Address;
45use Deriver\Deriver\Evaluator\Execution\Offset\Path;
46use Deriver\Deriver\Evaluator\Execution\Offset\Reader;
47use Deriver\Deriver\Evaluator\Execution\Offset\Transfer;
48use Deriver\Deriver\Evaluator\Execution\Operation\Conversions;
49use Deriver\Deriver\Evaluator\Execution\Operation\ScalarErrors;
50use Deriver\Deriver\Evaluator\Execution\State;
51use Deriver\Deriver\Evaluator\Execution\Summary\Evaluation;
52use Deriver\Deriver\Evaluator\Execution\Summary\Isolation;
53use Deriver\Deriver\Evaluator\Execution\Trace\Derivation;
54use Deriver\Deriver\Evaluator\Execution\Transfer\MemoryStep;
55use Deriver\Deriver\Evaluator\Execution\Transfer\PureStep;
56use Deriver\Deriver\Evaluator\Execution\Transfer\ReferenceAssignment;
57use Deriver\Deriver\Evaluator\Request\Budget;
58use Deriver\Deriver\Evaluator\Request\EntryPoint;
59use Deriver\Deriver\Evaluator\Request\QueryScope;
60use Deriver\Deriver\Evaluator\Request\ReturnQuery;
61use Deriver\Deriver\Evaluator\Scalar\Arrays;
62use Deriver\Deriver\Evaluator\Scalar\Identity;
63use Deriver\Deriver\Evaluator\Scalar\Operations;
64use Deriver\Deriver\Evaluator\TargetProfile;
65use Deriver\Deriver\Evaluator\Term;
66use Deriver\Deriver\Evaluator\TermKind;
67use Deriver\Deriver\Execution\DerivationResult;
68use Deriver\Deriver\Execution\QueryExecution;
69use Deriver\Deriver\Execution\ResultAssessment;
70use Deriver\Deriver\Identity\QueryEncoding;
71use Deriver\Deriver\Identity\ValueGraph;
72use Deriver\Deriver\Lowerer\AggregateLowering;
73use Deriver\Deriver\Lowerer\AssignmentLowering;
74use Deriver\Deriver\Lowerer\Control\DestructuringLowering;
75use Deriver\Deriver\Lowerer\Declaration\CallableIdentity;
76use Deriver\Deriver\Lowerer\Declaration\CallableSource;
77use Deriver\Deriver\Lowerer\Declaration\Index;
78use Deriver\Deriver\Lowerer\Declaration\Indexer;
79use Deriver\Deriver\Lowerer\Declaration\Traits\Composition;
80use Deriver\Deriver\Lowerer\ExpressionLowering;
81use Deriver\Deriver\Lowerer\Graph\BasicBlock;
82use Deriver\Deriver\Lowerer\Graph\CallableGraph;
83use Deriver\Deriver\Lowerer\Graph\Instruction;
84use Deriver\Deriver\Lowerer\Graph\Terminator;
85use Deriver\Deriver\Lowerer\Hierarchy\Dispatch;
86use Deriver\Deriver\Lowerer\InstructionEmitter;
87use Deriver\Deriver\Lowerer\Lowerer;
88use Deriver\Deriver\Lowerer\LoweringScope;
89use Deriver\Deriver\Lowerer\StatementLowering;
90use Deriver\Deriver\MicroEvaluatorConversion;
91use Deriver\Deriver\Parser\Node\File;
92use Deriver\Deriver\Parser\Parser;
93use Deriver\Deriver\Parser\ParserConfig;
94use Deriver\Deriver\Parser\TargetSyntax;
95use Deriver\Deriver\Providers\ProviderExpansion;
96use Deriver\Deriver\Resolver\AssignmentPatterns;
97use Deriver\Deriver\Resolver\ClassScope;
98use Deriver\Deriver\Resolver\ExpressionValidation;
99use Deriver\Deriver\Resolver\MagicContext;
100use Deriver\Deriver\Resolver\Resolver;
101use Deriver\Deriver\Selection\QueryValidation;
102use Deriver\Deriver\SnapshotIdentity;
103use Deriver\Deriver\Sources\LineMap;
104use Deriver\Deriver\Sources\Path as SourcesPath;
105use Deriver\Deriver\Sources\Source;
106use Deriver\Deriver\Sources\SourceRef;
107use Deriver\Deriver\Sources\Sources;
108use Deriver\Exception\ParserException;
109use Deriver\Exception\ResolutionException;
110use PHPUnit\Framework\Attributes\CoversClass;
111use PHPUnit\Framework\Attributes\DataProvider;
112use PHPUnit\Framework\Attributes\Small;
113use PHPUnit\Framework\Attributes\UsesClass;
114use PHPUnit\Framework\TestCase;
115
116#[UsesClass(Resolver::class)]
117#[UsesClass(ExpressionValidation::class)]
118#[UsesClass(ResolutionException::class)]
119#[UsesClass(ParserConfig::class)]
120#[UsesClass(ParserException::class)]
121#[CoversClass(Memory::class)]
122#[UsesClass(QueryExecution::class)]
123#[UsesClass(QueryValidation::class)]
124#[UsesClass(ResultAssessment::class)]
125#[UsesClass(Deriver::class)]
126#[UsesClass(BasicBlock::class)]
127#[UsesClass(CallableGraph::class)]
128#[UsesClass(CallableIdentity::class)]
129#[UsesClass(Instruction::class)]
130#[UsesClass(Terminator::class)]
131#[UsesClass(ArgumentBinding::class)]
132#[UsesClass(ArgumentOrder::class)]
133#[UsesClass(Dispatch::class)]
134#[UsesClass(TypeBinding::class)]
135#[UsesClass(TypeCheck::class)]
136#[UsesClass(Completion::class)]
137#[UsesClass(Context::class)]
138#[UsesClass(ObservationLimit::class)]
139#[UsesClass(StateJoin::class)]
140#[UsesClass(Unwinding::class)]
141#[UsesClass(Discovery::class)]
142#[UsesClass(Dependencies::class)]
143#[UsesClass(InstructionTransfer::class)]
144#[UsesClass(Evaluator::class)]
145#[UsesClass(SlotReference::class)]
146#[UsesClass(ObservationCollector::class)]
147#[UsesClass(Address::class)]
148#[UsesClass(Path::class)]
149#[UsesClass(Reader::class)]
150#[UsesClass(Transfer::class)]
151#[UsesClass(Conversions::class)]
152#[UsesClass(ScalarErrors::class)]
153#[UsesClass(State::class)]
154#[UsesClass(Evaluation::class)]
155#[UsesClass(Isolation::class)]
156#[UsesClass(MemoryStep::class)]
157#[UsesClass(PureStep::class)]
158#[UsesClass(ReferenceAssignment::class)]
159#[UsesClass(LiveArray::class)]
160#[UsesClass(Location::class)]
161#[UsesClass(Materialization::class)]
162#[UsesClass(ReferenceConstraint::class)]
163#[UsesClass(StorageCapture::class)]
164#[UsesClass(Extensions::class)]
165#[UsesClass(ProviderExpansion::class)]
166#[UsesClass(Evaluators::class)]
167#[UsesClass(StateRegistry::class)]
168#[UsesClass(DeriverConfig::class)]
169#[UsesClass(EntryPoint::class)]
170#[UsesClass(Sources::class)]
171#[UsesClass(SourcesPath::class)]
172#[UsesClass(Snapshot::class)]
173#[UsesClass(Source::class)]
174#[UsesClass(TargetProfile::class)]
175#[UsesClass(Budget::class)]
176#[UsesClass(QueryScope::class)]
177#[UsesClass(ReturnQuery::class)]
178#[UsesClass(ResultRef::class)]
179#[UsesClass(SourceRef::class)]
180#[UsesClass(Alternative::class)]
181#[UsesClass(Assessment::class)]
182#[UsesClass(Derivation::class)]
183#[UsesClass(DerivationResult::class)]
184#[UsesClass(QueryEncoding::class)]
185#[UsesClass(ValueGraph::class)]
186#[UsesClass(Statistics::class)]
187#[UsesClass(StorageSnapshot::class)]
188#[UsesClass(Parser::class)]
189#[UsesClass(File::class)]
190#[UsesClass(AggregateLowering::class)]
191#[UsesClass(AssignmentLowering::class)]
192#[UsesClass(Lowerer::class)]
193#[UsesClass(DestructuringLowering::class)]
194#[UsesClass(ExpressionLowering::class)]
195#[UsesClass(InstructionEmitter::class)]
196#[UsesClass(LoweringScope::class)]
197#[UsesClass(StatementLowering::class)]
198#[UsesClass(CallableSource::class)]
199#[UsesClass(Indexer::class)]
200#[UsesClass(Index::class)]
201#[UsesClass(Composition::class)]
202#[UsesClass(LineMap::class)]
203#[UsesClass(MagicContext::class)]
204#[UsesClass(AssignmentPatterns::class)]
205#[UsesClass(ClassScope::class)]
206#[UsesClass(TargetSyntax::class)]
207#[UsesClass(Arrays::class)]
208#[UsesClass(Identity::class)]
209#[UsesClass(Operations::class)]
210#[UsesClass(Term::class)]
211#[Small]
212final class MemoryTest extends TestCase
213{
214    public function testFreshPreservesTheSemanticContract(): void
215    {
216        $source = '<?php function target(){$x=1;$a=[&$x];$b=$a;$b[0]=2;return [$x,$a,$b];}';
217        $symbol = 'target';
218        $input = new Sources([new Source('fixture.php', $source)]);
219        $configuration = new DeriverConfig();
220        $contributions = new Contributions();
221        $target = new TargetProfile($configuration->phpVersion, $configuration->integerBits, $configuration->floatPrecision);
222        $providers = new ProviderExpansion($input, array_map(Term::fromNative(...), $configuration->environment), $contributions);
223        $contributions1 = $providers->contributions;
224        $evaluators = new Evaluators(new TargetProfile($configuration->phpVersion, $configuration->integerBits, $configuration->floatPrecision), new Registrations($contributions1->evaluators, $contributions1->providers, $contributions1->domains, $contributions1->intrinsics, $contributions1->stateSlots), $configuration->standardEvaluators);
225        $settings = new EvaluatorConfig($target, $providers->environment, $configuration->standardEvaluators, array_map((new MicroEvaluatorConversion())->convert(...), $configuration->evaluators));
226        $identity = new SnapshotIdentity($providers->input, $settings, $evaluators, $providers->manifest);
227        $snapshotId = $identity->id;
228        $input1 = $providers->input;
229        $parser = new Parser(new ParserConfig($target->version));
230        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(SourcesPath::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input1, false));
231        $program = new Index($snapshotId, $trees);
232        $result = (new QueryExecution($program, new ExecutionEvaluatorConfig($target, $providers->environment, $configuration->standardEvaluators), $evaluators, $identity->snapshot(array_map(Frontier::fromDiagnostic(...), $program->diagnostics()))))->derive(new ReturnQuery($symbol));
233        self::assertSame([2, [2], [2]], $result->normalOutcomes[0]->values['return']->native());
234        self::assertSame([], $result->frontiers);
235        self::assertSame([], $result->exceptionalOutcomes);
236    }
237    public function testAllocateCreatesIndependentCells(): void
238    {
239        $memory = new Memory();
240        $a = $memory->allocate(Term::constant(1));
241        $b = $memory->allocate(Term::constant(1));
242        $memory->write($b, Term::constant(2));
243        self::assertNotSame($a->root, $b->root);
244        self::assertSame(1, $memory->read($a)->native());
245        self::assertSame(2, $memory->read($b)->native());
246    }
247    public function testReadDistinguishesUninitializedFromNull(): void
248    {
249        $memory = new Memory();
250        $null = $memory->allocate(Term::constant(null));
251        self::assertSame(TermKind::Uninitialized, $memory->read(new Location('missing'))->kind);
252        self::assertSame(TermKind::Constant, $memory->read($null)->kind);
253    }
254    public function testDereferenceStopsAtReferenceCycles(): void
255    {
256        $memory = new Memory();
257        $memory->cells['a'] = new Term(TermKind::Cell, 'b');
258        $memory->cells['b'] = new Term(TermKind::Cell, 'a');
259        self::assertSame('CYCLIC_REFERENCE', $memory->dereference(new Term(TermKind::Cell, 'a'))->literal);
260    }
261    public function testWritePreservesUnrelatedArrayFields(): void
262    {
263        $memory = new Memory();
264        $a = $memory->allocate(Term::fromNative(['a' => 1, 'b' => 2]));
265        $memory->write(new Location($a->root, ['a']), Term::constant(3));
266        self::assertSame(['a' => 3, 'b' => 2], $memory->read($a)->native());
267        self::assertSame(1, $memory->versions[$a->root]);
268    }
269    public function testWritePathRebindsOnlyTheFinalReferenceSlot(): void
270    {
271        $memory = new Memory();
272        $a = $memory->allocate(Term::constant(1));
273        $b = $memory->allocate(Term::constant(2));
274        $record = $memory->allocate(Term::array([new Term(TermKind::Cell, $a->root)]));
275        $memory->writePath($record->root, [0], new Term(TermKind::Cell, $b->root), true);
276        $memory->write(new Location($record->root, [0]), Term::constant(3));
277        self::assertSame(1, $memory->read($a)->native());
278        self::assertSame(3, $memory->read($b)->native());
279    }
280    public function testReplacePreservesNestedStructure(): void
281    {
282        $memory = new Memory();
283        $result = $memory->replace(Term::fromNative(['a' => ['x' => 1, 'y' => 2]]), ['a', 'x'], Term::constant(3));
284        self::assertSame(['a' => ['x' => 3, 'y' => 2]], $result->native());
285    }
286    public function testReferenceMaterializesOneSharedCell(): void
287    {
288        $memory = new Memory();
289        $array = $memory->allocate(Term::fromNative([1]));
290        $element = new Location($array->root, [0]);
291        $first = $memory->reference($element);
292        $second = $memory->reference($element);
293        self::assertSame($first, $second);
294        $memory->write(new Location($first), Term::constant(2));
295        self::assertSame(2, $memory->read($element)->native());
296    }
297    public function testRawKeepsTheReferenceIdentity(): void
298    {
299        $memory = new Memory();
300        $cell = $memory->allocate(Term::constant(1));
301        $array = $memory->allocate(Term::array([new Term(TermKind::Cell, $cell->root)]));
302        self::assertSame(TermKind::Cell, $memory->raw(new Location($array->root, [0]))->kind);
303        self::assertSame(1, $memory->read(new Location($array->root, [0]))->native());
304    }
305    public function testRemoveKeepsTheNextAppendIndex(): void
306    {
307        $memory = new Memory();
308        $array = $memory->allocate(Term::fromNative([5 => 'a']));
309        $memory->remove(new Location($array->root, [5]));
310        self::assertSame(6, (new Arrays())->next($memory->read($array)));
311        self::assertSame([], $memory->read($array)->native());
312    }
313    public function testMaterializeReadsReferencedArrayElements(): void
314    {
315        $memory = new Memory();
316        $cell = $memory->allocate(Term::constant('shared'));
317        self::assertSame(['shared'], $memory->materialize(Term::array([new Term(TermKind::Cell, $cell->root)]))->native());
318    }
319    public function testSynchronizeKeepsLiveTraversalThroughElementDeletion(): void
320    {
321        $memory = new Memory();
322        $memory->cells['a'] = Term::fromNative([10, 20, 30]);
323        $memory->liveArrays['i'] = new LiveArray(new Location('a'), [1, 2], 0);
324        $memory->remove(new Location('a', [0]));
325        self::assertSame([1, 2], $memory->liveArrays['i']->remaining);
326        $memory->write(new Location('a'), Term::fromNative([40, 50]));
327        self::assertSame([0, 1], $memory->liveArrays['i']->remaining);
328    }
329    public function testRemovePreservesUnrelatedArrayEntries(): void
330    {
331        $memory = new Memory();
332        $value = new Term(TermKind::Array, operands: ['private' => Term::constant('derived'), 'drop' => Term::constant(1)], attributes: ['open' => false]);
333        $location = $memory->allocate($value);
334        $memory->remove(new Location($location->root, ['drop']));
335        $remaining = $memory->read($location);
336        self::assertSame(['private' => 'derived'], $remaining->native());
337    }
338    public function testElementPreservesOpenAndClosedAbsenceAndReferenceIdentity(): void
339    {
340        $memory = new Memory();
341        $object = new Term(TermKind::Object, 'one', attributes: ['class' => 'Box']);
342        $location = $memory->allocate($object);
343        $array = new Term(TermKind::Array, operands: ['object' => new Term(TermKind::Cell, $location->root)], attributes: ['open' => false]);
344        $entry = $memory->element($array, 'object');
345        self::assertSame('one', $entry->literal);
346        self::assertSame(['class' => 'Box'], $entry->attributes);
347        self::assertSame(TermKind::Uninitialized, $memory->element($array, 'missing')->kind);
348        self::assertSame('UNKNOWN_ARRAY_KEY', $memory->element(Term::array([], true), 'missing')->literal);
349        self::assertSame($object, $memory->read($location));
350    }
351    public function testReadSelectsNestedArrayEntries(): void
352    {
353        $memory = new Memory();
354        $array = new Term(TermKind::Array, operands: ['outer' => Term::fromNative(['inner' => 'private-value'])], attributes: ['open' => false]);
355        $location = $memory->allocate($array);
356        $result = $memory->read(new Location($location->root, ['outer', 'inner']));
357        self::assertSame('private-value', $result->native());
358        self::assertSame($array, $memory->read($location));
359    }
360    public function testDereferenceResolvesCellChainsAndDetectsCycles(): void
361    {
362        $memory = new Memory();
363        $memory->cells['first'] = new Term(TermKind::Cell, 'second');
364        $memory->cells['second'] = Term::constant('private-value');
365        $value = $memory->dereference(new Term(TermKind::Cell, 'first'));
366        $memory->cells['second'] = new Term(TermKind::Cell, 'first');
367        $cycle = $memory->dereference(new Term(TermKind::Cell, 'first'));
368        self::assertSame('private-value', $value->native());
369        self::assertSame('CYCLIC_REFERENCE', $cycle->literal);
370    }
371    public function testReferenceReusesAnExistingArrayCell(): void
372    {
373        $memory = new Memory();
374        $value = $memory->allocate(Term::constant('private-value'));
375        $link = $memory->allocate(new Term(TermKind::Cell, $value->root));
376        $array = $memory->allocate(new Term(TermKind::Array, operands: ['value' => new Term(TermKind::Cell, $link->root)], attributes: ['open' => false]));
377        $reference = $memory->reference(new Location($array->root, ['value']));
378        self::assertSame($link->root, $reference);
379        self::assertSame('private-value', $memory->read(new Location($reference))->native());
380        $memory->write($value, Term::constant('updated'));
381        self::assertSame('updated', $memory->read(new Location($reference))->native());
382    }
383    public function testFreshSeparatesAllocationCategoriesAcrossOneMonotonicSequence(): void
384    {
385        $memory = new Memory();
386        self::assertSame('object:0', $memory->fresh('object'));
387        self::assertSame('cell:1', $memory->fresh('cell'));
388        self::assertSame('object:2', $memory->fresh('object'));
389        self::assertSame(3, $memory->sequence);
390    }
391    public function testReadKeepsUnknownAddressesOpaqueEvenWhenTheirRootContainsAKnownValue(): void
392    {
393        $memory = new Memory();
394        $memory->cells['a'] = Term::constant(1);
395        $value = $memory->read(new Location('a', unknown: true));
396        self::assertSame(TermKind::Opaque, $value->kind);
397        self::assertSame('UNKNOWN_LOCATION', $value->literal);
398        self::assertSame('partial', $value->attributes['dependencyCoverage']);
399    }
400    public function testReadRetainsAResidualArrayAccessAndMissingStorage(): void
401    {
402        $memory = new Memory();
403        $parameter = Term::parameter('value');
404        $memory->cells['a'] = $parameter;
405        $value = $memory->read(new Location('a', ['key']));
406        self::assertSame(TermKind::ArrayRead, $value->kind);
407        self::assertSame($parameter, $value->operands[0]);
408        self::assertSame('key', $value->operands[1]->literal);
409        self::assertSame(TermKind::Uninitialized, $memory->read(new Location('missing', ['nested', 'key']))->kind);
410    }
411    public function testElementTreatsAnUnmarkedShapeAsClosed(): void
412    {
413        $memory = new Memory();
414        $array = new Term(TermKind::Array, operands: ['key' => Term::constant(1)]);
415        self::assertSame(TermKind::Uninitialized, $memory->element($array, 'missing')->kind);
416    }
417    public function testDereferenceResolvesReferencesAndMarksCyclesAsIncomplete(): void
418    {
419        $memory = new Memory();
420        $value = Term::constant('public');
421        $memory->cells['a'] = new Term(TermKind::Cell, 'b');
422        $memory->cells['b'] = $value;
423        self::assertSame($value, $memory->dereference(new Term(TermKind::Cell, 'a')));
424        $memory->cells['b'] = new Term(TermKind::Cell, 'a');
425        $cycle = $memory->dereference(new Term(TermKind::Cell, 'a'));
426        self::assertSame(TermKind::Opaque, $cycle->kind);
427        self::assertSame('CYCLIC_REFERENCE', $cycle->literal);
428        self::assertSame(['type' => 'mixed', 'dependencyCoverage' => 'partial'], $cycle->attributes);
429        self::assertSame(TermKind::Uninitialized, $memory->dereference(new Term(TermKind::Cell, 'missing'))->kind);
430    }
431    public function testWriteTracksEveryVersionAndRetainsUnknownWriteDependencies(): void
432    {
433        $memory = new Memory();
434        $location = new Location('new');
435        $memory->write($location, Term::constant(1));
436        $first = $memory->versions['new'];
437        $memory->write($location, Term::constant(2));
438        $second = $memory->versions['new'];
439        $dependency = Term::constant('private');
440        $memory->write(new Location('new', unknown: true), $dependency);
441        self::assertSame(1, $first);
442        self::assertSame(2, $second);
443        self::assertSame(3, $memory->versions['new']);
444        self::assertSame('UNKNOWN_WRITE', $memory->cells['new']->literal);
445        self::assertSame([$dependency], $memory->cells['new']->operands);
446    }
447    public function testWritePathFollowsRootAliasesAndUpdatesTheirLiveArrayCursor(): void
448    {
449        $memory = new Memory();
450        $memory->cells['alias'] = new Term(TermKind::Cell, 'array');
451        $memory->cells['array'] = Term::fromNative([10, 20]);
452        $memory->liveArrays['cursor'] = new LiveArray(new Location('array'), [1], 0);
453        $memory->writePath('alias', [0], Term::constant(30));
454        $afterElement = $memory->liveArrays['cursor']->remaining;
455        $memory->writePath('alias', [], Term::fromNative([40, 50]));
456        self::assertSame([1], $afterElement);
457        self::assertSame([0, 1], $memory->liveArrays['cursor']->remaining);
458        self::assertSame([40, 50], $memory->read(new Location('alias'))->native());
459        self::assertSame(TermKind::Cell, $memory->cells['alias']->kind);
460        self::assertSame('array', $memory->cells['alias']->literal);
461    }
462    public function testReplaceKeepsAReferenceWrapperAndReplacesTheReferencedArray(): void
463    {
464        $memory = new Memory();
465        $memory->cells['array'] = Term::fromNative([10, 20]);
466        $memory->liveArrays['cursor'] = new LiveArray(new Location('array'), [1], 0);
467        $reference = new Term(TermKind::Cell, 'array');
468        $result = $memory->replace($reference, [], Term::fromNative([30, 40]));
469        self::assertSame($reference, $result);
470        self::assertSame([30, 40], $memory->cells['array']->native());
471        self::assertSame([0, 1], $memory->liveArrays['cursor']->remaining);
472    }
473    #[DataProvider('providerReplacementBases')]
474    public function testReplaceDistinguishesEmptyStorageFromUnknownExistingKeys(Term $before, bool $open): void
475    {
476        $result = (new Memory())->replace($before, ['nested', 'key'], Term::constant(7));
477        self::assertSame(TermKind::Array, $result->kind);
478        self::assertSame($open, $result->attributes['open']);
479        self::assertSame(false, $result->operands['nested']->attributes['open']);
480        self::assertSame(7, $result->operands['nested']->operands['key']->literal);
481    }
482    /**
483     * @return iterable<string,array{Term,bool}>
484     */
485    public static function providerReplacementBases(): iterable
486    {
487        yield 'uninitialized' => [new Term(TermKind::Uninitialized), false];
488        yield 'null' => [Term::constant(null), false];
489        yield 'unknown parameter' => [Term::parameter('x'), true];
490        yield 'known closed array' => [Term::fromNative(['other' => 1]), false];
491        yield 'open array' => [Term::array([], true), true];
492    }
493    public function testReferenceInitializesMissingStorageAndFollowsExistingRootAliases(): void
494    {
495        $memory = new Memory();
496        $memory->cells['alias'] = new Term(TermKind::Cell, 'target');
497        $root = $memory->reference(new Location('alias'));
498        self::assertSame('target', $root);
499        self::assertSame(TermKind::Constant, $memory->cells['target']->kind);
500        self::assertNull($memory->cells['target']->literal);
501        self::assertSame('target', $memory->cells['alias']->literal);
502        self::assertSame('unseen', $memory->reference(new Location('unseen', unknown: true)));
503        self::assertArrayNotHasKey('unseen', $memory->cells);
504    }
505    public function testReferenceTerminatesForCyclesAndDoesNotMistakeStringsForCellLinks(): void
506    {
507        $memory = new Memory();
508        $memory->cells['a'] = new Term(TermKind::Cell, 'b');
509        $memory->cells['b'] = new Term(TermKind::Cell, 'a');
510        $memory->cells['text'] = Term::constant('a');
511        self::assertSame('a', $memory->reference(new Location('a')));
512        self::assertSame('text', $memory->reference(new Location('text')));
513    }
514    public function testReferenceMaterializesStringElements(): void
515    {
516        $memory = new Memory();
517        $array = $memory->allocate(Term::fromNative(['key' => 'text']));
518        $location = new Location($array->root, ['key']);
519        $first = $memory->reference($location);
520        $second = $memory->reference($location);
521        self::assertSame($first, $second);
522        self::assertSame('text', $memory->cells[$first]->literal);
523        self::assertSame(TermKind::Constant, $memory->cells[$first]->kind);
524        self::assertSame(TermKind::Cell, $memory->raw($location)->kind);
525    }
526    public function testRemoveRootLeavesOtherCellsUntouched(): void
527    {
528        $memory = new Memory();
529        $memory->cells['a'] = Term::constant(1);
530        $memory->cells['b'] = Term::constant(2);
531        $memory->remove(new Location('a'));
532        self::assertSame(['b'], array_keys($memory->cells));
533        self::assertSame(2, $memory->cells['b']->literal);
534    }
535    public function testRemoveRetainsOpenShapeMetadataAndDoesNotRestartLiveIteration(): void
536    {
537        $memory = new Memory();
538        $memory->cells['a'] = new Term(TermKind::Array, operands: [0 => Term::constant(10), 1 => Term::constant(20), 2 => Term::constant(30)], attributes: ['open' => true, 'next' => 8]);
539        $memory->liveArrays['cursor'] = new LiveArray(new Location('a'), [2], 1);
540        $memory->remove(new Location('a', [1]));
541        self::assertSame(['open' => true, 'next' => null], $memory->cells['a']->attributes);
542        self::assertSame([0, 2], array_keys($memory->cells['a']->operands));
543        self::assertSame([2], $memory->liveArrays['cursor']->remaining);
544    }
545    public function testSynchronizeChangesOnlyCursorsBoundToTheMutatedRoot(): void
546    {
547        $memory = new Memory();
548        $before = Term::fromNative([1, 2]);
549        $after = Term::fromNative([3, 4, 5]);
550        $cursor = new LiveArray(new Location('a'), [1], 0);
551        $other = new LiveArray(new Location('b'), [1], 0);
552        $memory->liveArrays = ['chosen' => $cursor, 'other' => $other];
553        $memory->synchronize('a', $before, $after, false);
554        self::assertSame([1, 2], $memory->liveArrays['chosen']->remaining);
555        self::assertSame($other, $memory->liveArrays['other']);
556        self::assertSame([1], $cursor->remaining);
557    }
558    public function testReadKeepsEveryKeyInAnUnresolvedNestedPath(): void
559    {
560        $memory = new Memory();
561        $input = Term::parameter('record');
562        $memory->cells['a'] = $input;
563        $value = $memory->read(new Location('a', ['outer', 'inner']));
564        self::assertSame(TermKind::ArrayRead, $value->kind);
565        self::assertSame('inner', $value->operands[1]->literal);
566        self::assertSame(TermKind::ArrayRead, $value->operands[0]->kind);
567        self::assertSame('outer', $value->operands[0]->operands[1]->literal);
568        self::assertSame($input, $value->operands[0]->operands[0]);
569    }
570    public function testReferenceMovesAGlobalValueIntoASharedCellBehindTheSlot(): void
571    {
572        $memory = new Memory();
573        $memory->cells['global:x'] = Term::constant(1);
574        $shared = $memory->reference(new Location('global:x'));
575        self::assertNotSame('global:x', $shared);
576        self::assertSame(['cell', $shared], [$memory->cells['global:x']->kind->value, $memory->cells['global:x']->literal]);
577        self::assertSame($shared, $memory->reference(new Location('global:x')));
578        $memory->cells['global:x'] = new Term(TermKind::Uninitialized);
579        self::assertSame(1, $memory->read(new Location($shared))->native());
580    }
581}
582