packages/deriver/tests/Integration/LoopPruningTest.php
1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Integration;
6
7use Deriver\Deriver\BranchEvaluators;
8use Deriver\Deriver\Candidate\Snapshot;
9use Deriver\Deriver\EvaluationOperation;
10use Deriver\Deriver\Evaluator\Call\Evaluators;
11use Deriver\Deriver\Evaluator\EvaluatorConfig;
12use Deriver\Deriver\Evaluator\Index\DefinitionIndex;
13use Deriver\Deriver\Evaluator\Request\ReturnQuery;
14use Deriver\Deriver\Evaluator\TargetProfile;
15use Deriver\Deriver\Evaluator\Term;
16use Deriver\Deriver\Lowerer\Declaration\Index;
17use Deriver\Deriver\MicroEvaluator;
18use Deriver\Deriver\MicroEvaluatorConversion;
19use Deriver\Deriver\Parser\Parser;
20use Deriver\Deriver\Parser\ParserConfig;
21use Deriver\Deriver\Publication\CandidateQuery;
22use Deriver\Deriver\Resolver\Resolver;
23use Deriver\Deriver\Sources\Source;
24use PHPUnit\Framework\Attributes\CoversNothing;
25use PHPUnit\Framework\Attributes\DataProvider;
26use PHPUnit\Framework\TestCase;
27
28#[CoversNothing]
29final class LoopPruningTest extends TestCase
30{
31 /**
32 * @return iterable<string, array{string, list<int>}>
33 */
34 public static function providerLoops(): iterable
35 {
36 yield 'zero while' => ['function subject(){$v=0;while(false){$v=expensive();}return $v;}', [0]];
37 yield 'zero for' => ['function subject(){$v=0;for($i=0;$i<0;$i++){$v=expensive();}return $v;}', [0]];
38 yield 'one for' => ['function subject(){$v=0;for($i=0;$i<1;$i++){$v=$i===0?11:expensive();}return $v;}', [11]];
39 yield 'one while' => ['function subject(){$v=0;$i=0;while($i<1){$v=$i===0?11:expensive();$i++;}return $v;}', [11]];
40 yield 'one do' => ['function subject(){$v=0;$i=0;do{$v=$i===0?11:expensive();$i++;}while($i<1);return $v;}', [11]];
41 yield 'one boolean loop' => ['function subject(){$v=0;$run=true;while($run){$v=$run?11:expensive();$run=false;}return $v;}', [11]];
42 yield 'empty foreach' => ['function subject(){$v=0;foreach([] as $x){$v=expensive();}return $v;}', [0]];
43 yield 'one foreach' => ['function subject(){$v=0;foreach([5] as $x){$v=$x===5?11:expensive();}return $v;}', [11]];
44 yield 'body return' => ['function subject(){for($i=0;$i<1;$i++){return $i===0?11:expensive();}return 0;}', [11]];
45 yield 'conditional body return' => ['function subject($x){for($i=0;$i<1;$i++){if($x){return $i===0?11:expensive();}}return 0;}', [0,11]];
46 yield 'unknown count' => ['function subject($x){$v=0;while(condition()){$v=$x?11:27;}return $v;}', [0,11,27]];
47 yield 'independent expressions' => ['function subject($x):int{$a=$x>0?11:27;$b=$x>13?1:4;return $a+$b;}', [12,15,28,31]];
48 }
49
50 /**
51 * @param list<int> $expected
52 */
53 #[DataProvider('providerLoops')]
54 public function testPrunesWithoutOpeningDiscardedCandidates(string $source, array $expected): void
55 {
56 $derive = static function (string $source, MicroEvaluator ...$evaluators): \Deriver\Deriver\Candidate\CandidateCollection {
57 $tree = (new Resolver())->resolve((new Parser(new ParserConfig('8.3')))->parse(new Source('fixture.php', '<?php ' . $source)));
58 $program = new Index('fixture', [$tree]);
59 $target = new TargetProfile();
60 $settings = new EvaluatorConfig($target, evaluators: array_map((new MicroEvaluatorConversion())->convert(...), array_values($evaluators)));
61 return (new CandidateQuery(new DefinitionIndex($program), $settings, new Evaluators($target), new Snapshot('fixture', [], [], $target, 'environment')))->derive(new ReturnQuery('subject'));
62 };
63 $opened = 0;
64 $result = $derive($source, ...[...BranchEvaluators::truth(), new MicroEvaluator('expensive', '1', EvaluationOperation::Function, 'expensive', static function () use (&$opened): Term {
65 ++$opened;
66 return Term::constant(27);
67 })]);
68 self::assertEqualsCanonicalizing($expected, array_map(static fn ($candidate) => $candidate->result, iterator_to_array($result)));
69 self::assertSame(0, $opened);
70 self::assertFalse($result->interrupted);
71 }
72
73 public function testLoopCountDoesNotMultiplyCandidateExpansion(): void
74 {
75 $derive = static function (string $source, MicroEvaluator ...$evaluators): \Deriver\Deriver\Candidate\CandidateCollection {
76 $tree = (new Resolver())->resolve((new Parser(new ParserConfig('8.3')))->parse(new Source('fixture.php', '<?php ' . $source)));
77 $program = new Index('fixture', [$tree]);
78 $target = new TargetProfile();
79 $settings = new EvaluatorConfig($target, evaluators: array_map((new MicroEvaluatorConversion())->convert(...), array_values($evaluators)));
80 return (new CandidateQuery(new DefinitionIndex($program), $settings, new Evaluators($target), new Snapshot('fixture', [], [], $target, 'environment')))->derive(new ReturnQuery('subject'));
81 };
82 $short = $derive('function subject(){$v=0;for($i=0;$i<2;$i++){$v=$i===0?11:27;}return $v;}', ...BranchEvaluators::truth());
83 $long = $derive('function subject(){$v=0;for($i=0;$i<10000;$i++){$v=$i===0?11:27;}return $v;}', ...BranchEvaluators::truth());
84 self::assertEqualsCanonicalizing([11,27], array_map(static fn ($candidate) => $candidate->result, iterator_to_array($short)));
85 self::assertEqualsCanonicalizing([11,27], array_map(static fn ($candidate) => $candidate->result, iterator_to_array($long)));
86 self::assertSame($short->statistics->constructedNodes, $long->statistics->constructedNodes);
87 self::assertSame($short->statistics->referenceExpansions, $long->statistics->referenceExpansions);
88 }
89
90 public function testDefaultCandidatesDoNotInspectLoopBounds(): void
91 {
92 $derive = static function (string $source, MicroEvaluator ...$evaluators): \Deriver\Deriver\Candidate\CandidateCollection {
93 $tree = (new Resolver())->resolve((new Parser(new ParserConfig('8.3')))->parse(new Source('fixture.php', '<?php ' . $source)));
94 $program = new Index('fixture', [$tree]);
95 $target = new TargetProfile();
96 $settings = new EvaluatorConfig($target, evaluators: array_map((new MicroEvaluatorConversion())->convert(...), array_values($evaluators)));
97 return (new CandidateQuery(new DefinitionIndex($program), $settings, new Evaluators($target), new Snapshot('fixture', [], [], $target, 'environment')))->derive(new ReturnQuery('subject'));
98 };
99 $result = $derive('function subject(){$v=0;for($i=0;$i<1;$i++){$v=$i===0?11:27;}return $v;}');
100 self::assertEqualsCanonicalizing([0,11,27], array_map(static fn ($candidate) => $candidate->result, iterator_to_array($result)));
101 self::assertSame(1, $result->statistics->referenceExpansions);
102 }
103 public function testDefaultLoopCandidatesRetainConditionalBodyReturns(): void
104 {
105 $derive = static function (string $source, MicroEvaluator ...$evaluators): \Deriver\Deriver\Candidate\CandidateCollection {
106 $tree = (new Resolver())->resolve((new Parser(new ParserConfig('8.3')))->parse(new Source('fixture.php', '<?php ' . $source)));
107 $program = new Index('fixture', [$tree]);
108 $target = new TargetProfile();
109 $settings = new EvaluatorConfig($target, evaluators: array_map((new MicroEvaluatorConversion())->convert(...), array_values($evaluators)));
110 return (new CandidateQuery(new DefinitionIndex($program), $settings, new Evaluators($target), new Snapshot('fixture', [], [], $target, 'environment')))->derive(new ReturnQuery('subject'));
111 };
112 $result = $derive('function subject($x){for($i=0;$i<1;$i++){if($x){return $i===0?11:27;}}return 0;}');
113 self::assertEqualsCanonicalizing([0,11,27], array_map(static fn ($candidate) => $candidate->result, iterator_to_array($result)));
114 self::assertFalse($result->interrupted);
115 }
116
117}
118