packages/deriver/tests/Unit/Deriver/Lowerer/Control/GotoLoweringTest.php

1<?php
2
3declare (strict_types=1);
4
5namespace Tests\Unit\Deriver\Lowerer\Control;
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\Constraints;
28use Deriver\Deriver\Evaluator\Execution\Context;
29use Deriver\Deriver\Evaluator\Execution\Control\ObservationLimit;
30use Deriver\Deriver\Evaluator\Execution\Control\StateJoin;
31use Deriver\Deriver\Evaluator\Execution\Control\Unwinding;
32use Deriver\Deriver\Evaluator\Execution\Demand\Cell;
33use Deriver\Deriver\Evaluator\Execution\Demand\Components;
34use Deriver\Deriver\Evaluator\Execution\Demand\Discovery;
35use Deriver\Deriver\Evaluator\Execution\Demand\Key;
36use Deriver\Deriver\Evaluator\Execution\Demand\Table;
37use Deriver\Deriver\Evaluator\Execution\Dependencies;
38use Deriver\Deriver\Evaluator\Execution\Evaluator;
39use Deriver\Deriver\Evaluator\Execution\EvaluatorConfig as ExecutionEvaluatorConfig;
40use Deriver\Deriver\Evaluator\Execution\InstructionTransfer;
41use Deriver\Deriver\Evaluator\Execution\Memory\Location;
42use Deriver\Deriver\Evaluator\Execution\Memory\Materialization;
43use Deriver\Deriver\Evaluator\Execution\Memory\Memory;
44use Deriver\Deriver\Evaluator\Execution\Memory\ReferenceConstraint;
45use Deriver\Deriver\Evaluator\Execution\Memory\Slots\SlotReference;
46use Deriver\Deriver\Evaluator\Execution\Memory\StorageCapture;
47use Deriver\Deriver\Evaluator\Execution\ObservationCollector;
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\CompletionRecord;
52use Deriver\Deriver\Evaluator\Execution\Summary\Evaluation;
53use Deriver\Deriver\Evaluator\Execution\Summary\Invocation;
54use Deriver\Deriver\Evaluator\Execution\Summary\Isolation;
55use Deriver\Deriver\Evaluator\Execution\Trace\Derivation;
56use Deriver\Deriver\Evaluator\Execution\Transfer\CompoundAssignment;
57use Deriver\Deriver\Evaluator\Execution\Transfer\MemoryStep;
58use Deriver\Deriver\Evaluator\Execution\Transfer\PureStep;
59use Deriver\Deriver\Evaluator\Execution\Transfer\ReferenceAssignment;
60use Deriver\Deriver\Evaluator\Request\Budget;
61use Deriver\Deriver\Evaluator\Request\EntryPoint;
62use Deriver\Deriver\Evaluator\Request\QueryScope;
63use Deriver\Deriver\Evaluator\Request\ReturnQuery;
64use Deriver\Deriver\Evaluator\Scalar\Arithmetic;
65use Deriver\Deriver\Evaluator\Scalar\Comparison;
66use Deriver\Deriver\Evaluator\Scalar\Identity;
67use Deriver\Deriver\Evaluator\Scalar\Operations;
68use Deriver\Deriver\Evaluator\TargetProfile;
69use Deriver\Deriver\Evaluator\Term;
70use Deriver\Deriver\Execution\DerivationResult;
71use Deriver\Deriver\Execution\QueryExecution;
72use Deriver\Deriver\Execution\ResultAssessment;
73use Deriver\Deriver\Identity\QueryEncoding;
74use Deriver\Deriver\Identity\ValueGraph;
75use Deriver\Deriver\Lowerer\AggregateLowering;
76use Deriver\Deriver\Lowerer\AssignmentLowering;
77use Deriver\Deriver\Lowerer\Control\ConditionalLowering;
78use Deriver\Deriver\Lowerer\Control\DestructuringLowering;
79use Deriver\Deriver\Lowerer\Control\ExceptionLowering;
80use Deriver\Deriver\Lowerer\Control\GotoLowering;
81use Deriver\Deriver\Lowerer\Control\LoopLowering;
82use Deriver\Deriver\Lowerer\Control\ScopeKind;
83use Deriver\Deriver\Lowerer\Declaration\CallableIdentity;
84use Deriver\Deriver\Lowerer\Declaration\CallableSource;
85use Deriver\Deriver\Lowerer\Declaration\Index;
86use Deriver\Deriver\Lowerer\Declaration\Indexer;
87use Deriver\Deriver\Lowerer\Declaration\Traits\Composition;
88use Deriver\Deriver\Lowerer\EffectInspection;
89use Deriver\Deriver\Lowerer\ExpressionLowering;
90use Deriver\Deriver\Lowerer\Graph\BasicBlock;
91use Deriver\Deriver\Lowerer\Graph\CallableGraph;
92use Deriver\Deriver\Lowerer\Graph\ExceptionRegion;
93use Deriver\Deriver\Lowerer\Graph\Instruction;
94use Deriver\Deriver\Lowerer\Graph\Literal;
95use Deriver\Deriver\Lowerer\Graph\Terminator;
96use Deriver\Deriver\Lowerer\Graph\TerminatorKind;
97use Deriver\Deriver\Lowerer\Hierarchy\Dispatch;
98use Deriver\Deriver\Lowerer\InstructionEmitter;
99use Deriver\Deriver\Lowerer\Lowerer;
100use Deriver\Deriver\Lowerer\LoweringScope;
101use Deriver\Deriver\Lowerer\StatementLowering;
102use Deriver\Deriver\MicroEvaluatorConversion;
103use Deriver\Deriver\Parser\Node\File;
104use Deriver\Deriver\Parser\Parser;
105use Deriver\Deriver\Parser\ParserConfig;
106use Deriver\Deriver\Parser\TargetSyntax;
107use Deriver\Deriver\Providers\ProviderExpansion;
108use Deriver\Deriver\Resolver\AssignmentPatterns;
109use Deriver\Deriver\Resolver\ClassScope;
110use Deriver\Deriver\Resolver\ExpressionValidation;
111use Deriver\Deriver\Resolver\MagicContext;
112use Deriver\Deriver\Resolver\Resolver;
113use Deriver\Deriver\Selection\QueryValidation;
114use Deriver\Deriver\SnapshotIdentity;
115use Deriver\Deriver\Sources\LineMap;
116use Deriver\Deriver\Sources\Path;
117use Deriver\Deriver\Sources\Source;
118use Deriver\Deriver\Sources\SourceRef;
119use Deriver\Deriver\Sources\Sources;
120use Deriver\Exception\ParserException;
121use Deriver\Exception\ResolutionException;
122use PhpParser\Node\Stmt\Goto_;
123use PHPUnit\Framework\Attributes\CoversClass;
124use PHPUnit\Framework\Attributes\Small;
125use PHPUnit\Framework\Attributes\UsesClass;
126use PHPUnit\Framework\TestCase;
127
128#[UsesClass(Resolver::class)]
129#[UsesClass(ExpressionValidation::class)]
130#[UsesClass(ResolutionException::class)]
131#[UsesClass(ParserConfig::class)]
132#[UsesClass(ParserException::class)]
133#[CoversClass(GotoLowering::class)]
134#[UsesClass(QueryExecution::class)]
135#[UsesClass(QueryValidation::class)]
136#[UsesClass(ResultAssessment::class)]
137#[UsesClass(Deriver::class)]
138#[UsesClass(Constraints::class)]
139#[UsesClass(BasicBlock::class)]
140#[UsesClass(CallableGraph::class)]
141#[UsesClass(CallableIdentity::class)]
142#[UsesClass(Instruction::class)]
143#[UsesClass(Terminator::class)]
144#[UsesClass(ArgumentBinding::class)]
145#[UsesClass(ArgumentOrder::class)]
146#[UsesClass(Dispatch::class)]
147#[UsesClass(TypeBinding::class)]
148#[UsesClass(TypeCheck::class)]
149#[UsesClass(Completion::class)]
150#[UsesClass(Context::class)]
151#[UsesClass(ObservationLimit::class)]
152#[UsesClass(StateJoin::class)]
153#[UsesClass(Unwinding::class)]
154#[UsesClass(Cell::class)]
155#[UsesClass(Components::class)]
156#[UsesClass(Discovery::class)]
157#[UsesClass(Key::class)]
158#[UsesClass(Table::class)]
159#[UsesClass(Dependencies::class)]
160#[UsesClass(InstructionTransfer::class)]
161#[UsesClass(Evaluator::class)]
162#[UsesClass(SlotReference::class)]
163#[UsesClass(ObservationCollector::class)]
164#[UsesClass(Conversions::class)]
165#[UsesClass(ScalarErrors::class)]
166#[UsesClass(State::class)]
167#[UsesClass(CompletionRecord::class)]
168#[UsesClass(Evaluation::class)]
169#[UsesClass(Invocation::class)]
170#[UsesClass(Isolation::class)]
171#[UsesClass(CompoundAssignment::class)]
172#[UsesClass(MemoryStep::class)]
173#[UsesClass(PureStep::class)]
174#[UsesClass(ReferenceAssignment::class)]
175#[UsesClass(Location::class)]
176#[UsesClass(Materialization::class)]
177#[UsesClass(Memory::class)]
178#[UsesClass(ReferenceConstraint::class)]
179#[UsesClass(StorageCapture::class)]
180#[UsesClass(Extensions::class)]
181#[UsesClass(ProviderExpansion::class)]
182#[UsesClass(Evaluators::class)]
183#[UsesClass(StateRegistry::class)]
184#[UsesClass(DeriverConfig::class)]
185#[UsesClass(EntryPoint::class)]
186#[UsesClass(Sources::class)]
187#[UsesClass(Path::class)]
188#[UsesClass(Snapshot::class)]
189#[UsesClass(Source::class)]
190#[UsesClass(TargetProfile::class)]
191#[UsesClass(Budget::class)]
192#[UsesClass(QueryScope::class)]
193#[UsesClass(ReturnQuery::class)]
194#[UsesClass(ResultRef::class)]
195#[UsesClass(SourceRef::class)]
196#[UsesClass(Alternative::class)]
197#[UsesClass(Assessment::class)]
198#[UsesClass(Derivation::class)]
199#[UsesClass(DerivationResult::class)]
200#[UsesClass(QueryEncoding::class)]
201#[UsesClass(ValueGraph::class)]
202#[UsesClass(Statistics::class)]
203#[UsesClass(StorageSnapshot::class)]
204#[UsesClass(Parser::class)]
205#[UsesClass(File::class)]
206#[UsesClass(AssignmentLowering::class)]
207#[UsesClass(Lowerer::class)]
208#[UsesClass(DestructuringLowering::class)]
209#[UsesClass(LoopLowering::class)]
210#[UsesClass(ExpressionLowering::class)]
211#[UsesClass(InstructionEmitter::class)]
212#[UsesClass(LoweringScope::class)]
213#[UsesClass(StatementLowering::class)]
214#[UsesClass(CallableSource::class)]
215#[UsesClass(Indexer::class)]
216#[UsesClass(Index::class)]
217#[UsesClass(Composition::class)]
218#[UsesClass(LineMap::class)]
219#[UsesClass(MagicContext::class)]
220#[UsesClass(AssignmentPatterns::class)]
221#[UsesClass(ClassScope::class)]
222#[UsesClass(TargetSyntax::class)]
223#[UsesClass(Arithmetic::class)]
224#[UsesClass(Comparison::class)]
225#[UsesClass(Identity::class)]
226#[UsesClass(Operations::class)]
227#[UsesClass(Literal::class)]
228#[UsesClass(ExceptionLowering::class)]
229#[UsesClass(ExceptionRegion::class)]
230#[UsesClass(AggregateLowering::class)]
231#[UsesClass(EffectInspection::class)]
232#[UsesClass(LoopLowering::class)]
233#[UsesClass(ConditionalLowering::class)]
234#[Small]
235final class GotoLoweringTest extends TestCase
236{
237    public function testResolveJumpsBackwardToALoopHeaderLabel(): void
238    {
239        $source = '<?php function target(){$i=0;again:$i++;if($i<2)goto again;return $i;}';
240        $snapshotId = 'test';
241        $input = new Sources([new Source('fixture.php', $source)]);
242        $profile = new TargetProfile();
243        $parser = new Parser(new ParserConfig($profile->version));
244        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input, false));
245        $graph = (new Index($snapshotId, $trees))->callable('target');
246        self::assertNotNull($graph);
247        $jumps = array_values(array_filter($graph->blocks, static fn ($block) => $block->terminator->kind === TerminatorKind::CompleteJump));
248        self::assertCount(1, $jumps);
249        $label = $jumps[0]->terminator->targets[0];
250        self::assertTrue($graph->blocks[$label]->loopHeader);
251        self::assertSame(0, $jumps[0]->terminator->handlerDepth);
252    }
253    public function testResolveLeavesForwardLabelsOutOfLoopWidening(): void
254    {
255        $source = '<?php function target(){goto done;$x=1;done:return 2;}';
256        $snapshotId = 'test';
257        $input = new Sources([new Source('fixture.php', $source)]);
258        $profile = new TargetProfile();
259        $parser = new Parser(new ParserConfig($profile->version));
260        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input, false));
261        $graph = (new Index($snapshotId, $trees))->callable('target');
262        self::assertNotNull($graph);
263        self::assertSame([], array_filter($graph->blocks, static fn ($block) => $block->loopHeader));
264    }
265    public function testResolveReleasesForeachIteratorsAfterNestedFinallyBlocks(): void
266    {
267        $source = '<?php function target(){foreach([1] as $v){try{goto out;}finally{$v=2;}}out:return 1;}';
268        $snapshotId = 'test';
269        $input = new Sources([new Source('fixture.php', $source)]);
270        $profile = new TargetProfile();
271        $parser = new Parser(new ParserConfig($profile->version));
272        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input, false));
273        $graph = (new Index($snapshotId, $trees))->callable('target');
274        self::assertNotNull($graph);
275        $jumps = array_values(array_filter($graph->blocks, static fn ($block) => $block->terminator->kind === TerminatorKind::CompleteJump));
276        self::assertCount(2, $jumps);
277        self::assertSame(0, $jumps[0]->terminator->handlerDepth);
278        $release = $graph->blocks[$jumps[0]->terminator->targets[0]];
279        self::assertSame(['iterator-release'], array_column($release->instructions, 'operation'));
280        self::assertSame(TerminatorKind::CompleteJump, $release->terminator->kind);
281    }
282    public function testResolveSealsJumpsIntoLoopsAsExplicitBoundaries(): void
283    {
284        $source = '<?php function target(){goto inside;while(true){inside:return 1;}}';
285        $snapshotId = 'test';
286        $input = new Sources([new Source('fixture.php', $source)]);
287        $profile = new TargetProfile();
288        $parser = new Parser(new ParserConfig($profile->version));
289        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input, false));
290        $graph = (new Index($snapshotId, $trees))->callable('target');
291        self::assertNotNull($graph);
292        $boundary = $graph->blocks[0];
293        self::assertSame(TerminatorKind::Residual, $boundary->terminator->kind);
294        self::assertSame('unsupported', $boundary->instructions[count($boundary->instructions) - 1]->operation);
295        self::assertSame('Stmt_Goto', $boundary->instructions[count($boundary->instructions) - 1]->name);
296    }
297    public function testJumpEndsTheBlockUntilResolution(): void
298    {
299        $source = '<?php function target(){return 1;}';
300        $snapshotId = 'test';
301        $input = new Sources([new Source('fixture.php', $source)]);
302        $profile = new TargetProfile();
303        $parser = new Parser(new ParserConfig($profile->version));
304        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input, false));
305        $index = new Index($snapshotId, $trees);
306        $lowering = new LoweringScope($index->builder('fixture.php'), $index, 'target');
307        (new GotoLowering($lowering))->jump(new Goto_('later'));
308        self::assertSame(TerminatorKind::Residual, $lowering->graph->terminators[0]->kind);
309        self::assertSame(0, $lowering->graph->gotos[0]['block']);
310        self::assertSame([], $lowering->graph->instructions[0]);
311    }
312    public function testUnwindSplitsTheJumpOnlyWhenAFinallyMustRunBeforeARelease(): void
313    {
314        $source = '<?php function target(){return 1;}';
315        $snapshotId = 'test';
316        $input = new Sources([new Source('fixture.php', $source)]);
317        $profile = new TargetProfile();
318        $parser = new Parser(new ParserConfig($profile->version));
319        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input, false));
320        $index = new Index($snapshotId, $trees);
321        $lowering = new LoweringScope($index->builder('fixture.php'), $index, 'target');
322        $node = new Goto_('out');
323        $loop = ['key' => 'loop:1', 'kind' => ScopeKind::Loop, 'iterator' => 'r1', 'depth' => 0];
324        $try = ['key' => 'region:0:try', 'kind' => ScopeKind::Try, 'iterator' => '', 'depth' => 0];
325        (new GotoLowering($lowering))->unwind($node, [$loop]);
326        self::assertSame(['iterator-release'], array_column($lowering->graph->instructions[0], 'operation'));
327        self::assertSame([], $lowering->graph->terminators);
328        $source2 = '<?php function target(){return 1;}';
329        $snapshotId1 = 'test';
330        $input1 = new Sources([new Source('fixture.php', $source2)]);
331        $profile1 = new TargetProfile();
332        $parser1 = new Parser(new ParserConfig($profile1->version));
333        $trees1 = array_map(static fn (Source $source3): File => (new Resolver())->resolve($parser1->parse(new Source(Path::normalize($source3->path), $source3->contents, $source3->declarationsOnly))), iterator_to_array($input1, false));
334        $index1 = new Index($snapshotId1, $trees1);
335        $split = new LoweringScope($index1->builder('fixture.php'), $index1, 'target');
336        (new GotoLowering($split))->unwind($node, [$try, $loop]);
337        self::assertSame([TerminatorKind::CompleteJump, [1]], [$split->graph->terminators[0]->kind ?? '', $split->graph->terminators[0]->targets ?? []]);
338        self::assertSame(['iterator-release'], array_column($split->graph->instructions[1], 'operation'));
339    }
340    public function testExitedListsInnermostScopesFirstAndRejectsUnmodeledJumps(): void
341    {
342        $source = '<?php function target(){return 1;}';
343        $snapshotId = 'test';
344        $input = new Sources([new Source('fixture.php', $source)]);
345        $profile = new TargetProfile();
346        $parser = new Parser(new ParserConfig($profile->version));
347        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input, false));
348        $index = new Index($snapshotId, $trees);
349        $goto = new GotoLowering(new LoweringScope($index->builder('fixture.php'), $index, 'target'));
350        $loop = ['key' => 'loop:1', 'kind' => ScopeKind::Loop, 'iterator' => 'r1', 'depth' => 0];
351        $try = ['key' => 'region:0:try', 'kind' => ScopeKind::Try, 'iterator' => '', 'depth' => 0];
352        $finally = ['key' => 'region:0:finally', 'kind' => ScopeKind::Finally, 'iterator' => '', 'depth' => 0];
353        self::assertSame([$try, $loop], $goto->exited([$loop, $try], []));
354        self::assertSame([], $goto->exited([$loop], [$loop]));
355        self::assertNull($goto->exited([], [$loop]));
356        self::assertNull($goto->exited([$finally], []));
357    }
358    public function testLabelAloneDoesNotDisturbState(): void
359    {
360        $source = '<?php function target(){$x="a";here:return $x;}';
361        $symbol = 'target';
362        $input = new Sources([new Source('fixture.php', $source)]);
363        $configuration = new DeriverConfig();
364        $contributions = new Contributions();
365        $target = new TargetProfile($configuration->phpVersion, $configuration->integerBits, $configuration->floatPrecision);
366        $providers = new ProviderExpansion($input, array_map(Term::fromNative(...), $configuration->environment), $contributions);
367        $contributions1 = $providers->contributions;
368        $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);
369        $settings = new EvaluatorConfig($target, $providers->environment, $configuration->standardEvaluators, array_map((new MicroEvaluatorConversion())->convert(...), $configuration->evaluators));
370        $identity = new SnapshotIdentity($providers->input, $settings, $evaluators, $providers->manifest);
371        $snapshotId = $identity->id;
372        $input1 = $providers->input;
373        $parser = new Parser(new ParserConfig($target->version));
374        $trees = array_map(static fn (Source $source1): File => (new Resolver())->resolve($parser->parse(new Source(Path::normalize($source1->path), $source1->contents, $source1->declarationsOnly))), iterator_to_array($input1, false));
375        $program = new Index($snapshotId, $trees);
376        $result = (new QueryExecution($program, new ExecutionEvaluatorConfig($target, $providers->environment, $configuration->standardEvaluators), $evaluators, $identity->snapshot(array_map(Frontier::fromDiagnostic(...), $program->diagnostics()))))->derive(new ReturnQuery($symbol));
377        self::assertSame(['a'], array_map(static fn ($outcome) => $outcome->values['return']->native(), $result->normalOutcomes));
378        self::assertSame([], $result->frontiers);
379    }
380}
381