packages/sql-faker/tests/Unit/Generation/Derivation/ConstrainedCompletionTest.php
1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Unit\SqlFaker\Generation\Derivation;
6
7use PHPUnit\Framework\Attributes\CoversClass;
8use PHPUnit\Framework\Attributes\DataProvider;
9use PHPUnit\Framework\Attributes\UsesClass;
10use PHPUnit\Framework\TestCase;
11use SqlFaker\Generation\Derivation\CompletionCosts;
12use SqlFaker\Generation\Derivation\CompletionState;
13use SqlFaker\Generation\Derivation\ConstrainedCompletion;
14use SqlFaker\Generation\Plan\GenerationPlan;
15use SqlFaker\Generation\Plan\ProductionPattern;
16use SqlFaker\Grammar\Model\Grammar;
17use SqlFaker\Grammar\Model\NonTerminal;
18use SqlFaker\Grammar\Model\Production;
19use SqlFaker\Grammar\Model\ProductionRule;
20use SqlFaker\Grammar\Model\Terminal;
21
22#[CoversClass(ConstrainedCompletion::class)]
23#[UsesClass(CompletionCosts::class)]
24#[UsesClass(CompletionState::class)]
25#[UsesClass(GenerationPlan::class)]
26#[UsesClass(ProductionPattern::class)]
27#[UsesClass(Grammar::class)]
28#[UsesClass(NonTerminal::class)]
29#[UsesClass(Production::class)]
30#[UsesClass(ProductionRule::class)]
31#[UsesClass(Terminal::class)]
32#[UsesClass(\SqlFaker\Generation\Derivation\CompletionFrontier::class)]
33#[UsesClass(\SqlFaker\Generation\Derivation\CompletionMemo::class)]
34#[UsesClass(\SqlFaker\Generation\Derivation\CompletionReduction::class)]
35#[UsesClass(\SqlFaker\Generation\Derivation\ConstraintDependencies::class)]
36#[UsesClass(\SqlFaker\Generation\Choice\BytePlanCompiler::class)]
37#[UsesClass(\SqlFaker\Generation\Derivation\Completion\PatternProductions::class)]
38#[UsesClass(\SqlFaker\Generation\Derivation\Completion\CompletionWitness::class)]
39final class ConstrainedCompletionTest extends TestCase
40{
41 /**
42 * @param GenerationPlan<bool> $plan
43 */
44 #[DataProvider('providerConstraints')]
45 public function testMinimumIncludesDescendantsSiblingsAndRecursiveOccurrenceConstraints(GenerationPlan $plan, int $budget, bool $nonEmpty, int $expected): void
46 {
47 $grammar = new Grammar('root', [
48 'root' => new ProductionRule('root', [new Production([new NonTerminal('leaf'), new NonTerminal('leaf')])]),
49 'leaf' => new ProductionRule('leaf', [new Production([]), new Production([new NonTerminal('end')]), new Production([new NonTerminal('leaf')])]),
50 'end' => new ProductionRule('end', [new Production([new Terminal('T')])]),
51 ]);
52 $completion = new ConstrainedCompletion($grammar, new CompletionCosts($grammar, static fn (string $name): bool => false));
53 self::assertSame($expected, $completion->minimum([new NonTerminal('root')], $plan, [], $nonEmpty, $budget));
54 }
55
56 /**
57 * @return iterable<array{GenerationPlan<bool>, int, bool, int}>
58 */
59 public static function providerConstraints(): iterable
60 {
61 yield [GenerationPlan::all(), 10, false, 3];
62 yield [GenerationPlan::all(), 10, true, 4];
63 $second = GenerationPlan::constrained('root', ['leaf' => [ProductionPattern::at(0), ProductionPattern::at(1)]]);
64 yield [$second, 4, true, 4];
65 yield [$second, 3, true, PHP_INT_MAX];
66 $recursive = GenerationPlan::constrained('root', ['leaf' => [ProductionPattern::at(2), ProductionPattern::at(1), ProductionPattern::at(1)]]);
67 yield [$recursive, 6, true, 6];
68 yield [$recursive, 5, true, PHP_INT_MAX];
69 yield [GenerationPlan::all()->withPatternForEveryOccurrence('leaf', ProductionPattern::at(2)), 20, true, PHP_INT_MAX];
70 yield [GenerationPlan::all()->withPatternForEveryOccurrence('leaf', ProductionPattern::at(0)), 3, false, 3];
71 yield [GenerationPlan::all()->withPatternForEveryOccurrence('leaf', ProductionPattern::at(0)), 3, true, PHP_INT_MAX];
72 yield [GenerationPlan::constrained('root', ['unused' => [ProductionPattern::at(9)]]), 4, true, 4];
73 }
74
75 public function testMinimumCountsOnlyTheUnconsumedPatternSuffix(): void
76 {
77 $grammar = new Grammar('leaf', [
78 'leaf' => new ProductionRule('leaf', [new Production([]), new Production([new Terminal('T')])]),
79 ]);
80 $plan = GenerationPlan::constrained('leaf', ['leaf' => [ProductionPattern::at(0), ProductionPattern::at(1)]]);
81 $completion = new ConstrainedCompletion($grammar, new CompletionCosts($grammar, static fn (string $name): bool => false));
82 self::assertSame(1, $completion->minimum([new NonTerminal('leaf')], $plan, ['leaf' => 1], true, 1));
83 self::assertSame(PHP_INT_MAX, $completion->minimum([new NonTerminal('leaf')], $plan, [], true, 1));
84 }
85
86 public function testWithinRejectsARequiredOutputThatIndependentEmptySubtreesCannotSupply(): void
87 {
88 $grammar = new Grammar('root', [
89 'root' => new ProductionRule('root', [new Production([new NonTerminal('free'), new NonTerminal('fixed')])]),
90 'free' => new ProductionRule('free', [new Production([]), new Production([new NonTerminal('end')])]),
91 'fixed' => new ProductionRule('fixed', [new Production([])]),
92 'end' => new ProductionRule('end', [new Production([new Terminal('T')])]),
93 ]);
94 $completion = new ConstrainedCompletion($grammar, new CompletionCosts($grammar, static fn (string $name): bool => false));
95 $plan = GenerationPlan::all()->withPatternForEveryOccurrence('fixed', ProductionPattern::at(0));
96 self::assertFalse($completion->within([new NonTerminal('root')], $plan, [], true, 3));
97 self::assertTrue($completion->within([new NonTerminal('root')], $plan, [], true, 4));
98 self::assertTrue($completion->within([new NonTerminal('root')], $plan, [], false, 3));
99 }
100
101 public function testCompleteCachesNormalizedPendingFormsWithoutLosingAlreadyEmittedOutput(): void
102 {
103 $grammar = new Grammar('leaf', ['leaf' => new ProductionRule('leaf', [new Production([])])]);
104 $completion = new ConstrainedCompletion($grammar, new CompletionCosts($grammar, static fn (string $name): bool => false));
105 $plan = GenerationPlan::all();
106 self::assertSame(1, $completion->complete([new Terminal('T'), new NonTerminal('leaf')], $plan, [], true, 1, true));
107 self::assertSame(1, $completion->complete([new NonTerminal('leaf')], $plan, [], false, 1, true));
108 self::assertSame(PHP_INT_MAX, $completion->complete([new NonTerminal('leaf')], $plan, [], true, 1, true));
109 }
110
111 public function testSearchRetainsAFirstWitnessAsFeasibilityInsteadOfAMinimumProof(): void
112 {
113 $grammar = new Grammar('leaf', ['leaf' => new ProductionRule('leaf', [new Production([new Terminal('T')])])]);
114 $completion = new ConstrainedCompletion($grammar, new CompletionCosts($grammar, static fn (string $name): bool => false));
115 self::assertSame(1, $completion->search([new NonTerminal('leaf')], GenerationPlan::all(), [], true, 1, false));
116 }
117
118 public function testWitnessCachesOnlyTheChosenSuffixAndKeepsMinimumQueriesIndependent(): void
119 {
120 $grammar = new Grammar('leaf', ['leaf' => new ProductionRule('leaf', [new Production([new Terminal('T')])])]);
121 $completion = new ConstrainedCompletion($grammar, new CompletionCosts($grammar, static fn (string $name): bool => false));
122 $plan = GenerationPlan::all();
123 $state = new CompletionState([new NonTerminal('leaf')], [], true, 0);
124 self::assertSame(3, $completion->witness(new CompletionState([], [], false, 3, $state), $plan, 3, 5));
125 self::assertSame(3, $completion->complete([new NonTerminal('leaf')], $plan, [], true, 5, false));
126 self::assertSame(1, $completion->minimum([new NonTerminal('leaf')], $plan, [], true, 5));
127 }
128}
129