packages/sql-faker/tests/Unit/Generation/Derivation/CompletionCostsTest.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\Grammar\Model\Grammar;
13use SqlFaker\Grammar\Model\NonTerminal;
14use SqlFaker\Grammar\Model\Production;
15use SqlFaker\Grammar\Model\ProductionRule;
16use SqlFaker\Grammar\Model\Terminal;
17
18#[CoversClass(CompletionCosts::class)]
19#[UsesClass(Grammar::class)]
20#[UsesClass(NonTerminal::class)]
21#[UsesClass(Production::class)]
22#[UsesClass(ProductionRule::class)]
23#[UsesClass(Terminal::class)]
24final class CompletionCostsTest extends TestCase
25{
26    public function testRuleFindsFiniteCompletionsThroughNullableRecursion(): void
27    {
28        $grammar = new Grammar('s', ['s' => new ProductionRule('s', [new Production([]), new Production([new NonTerminal('s'), new Terminal('X')])])]);
29        $costs = new CompletionCosts($grammar, static fn (string $name): bool => false);
30        self::assertSame(1, $costs->rule('s', false));
31        self::assertSame(2, $costs->rule('s', true));
32        self::assertSame(PHP_INT_MAX, $costs->rule('missing', true));
33    }
34
35    public function testSequenceCountsMarkersAsEmptyAndReservesAllSiblings(): void
36    {
37        $grammar = new Grammar('s', ['s' => new ProductionRule('s', [new Production([new Terminal('X')])])]);
38        $costs = new CompletionCosts($grammar, static fn (string $name): bool => $name === 'EOF');
39        self::assertSame([0, PHP_INT_MAX], $costs->sequence([new Terminal('EOF')]));
40        self::assertSame([PHP_INT_MAX, 2], $costs->sequence([new NonTerminal('s'), new NonTerminal('s')]));
41    }
42
43    public function testCompletionAllowsAnEmptyProductionWhenItsSiblingEmitsOutput(): void
44    {
45        $costs = new CompletionCosts(new Grammar('s', []), static fn (string $name): bool => false);
46        self::assertSame(0, $costs->completion(new Production([]), [new Terminal('X')], true));
47        self::assertSame(PHP_INT_MAX, $costs->completion(new Production([]), [], true));
48    }
49
50    public function testAffordableRetainsExactlyTheAlternativesThatCanFinishWithinBudget(): void
51    {
52        $empty = new Production([]);
53        $nested = new Production([new NonTerminal('s')]);
54        $grammar = new Grammar('s', ['s' => new ProductionRule('s', [new Production([new Terminal('X')])])]);
55        $costs = new CompletionCosts($grammar, static fn (string $name): bool => false);
56        self::assertSame([$empty], $costs->affordable([$empty, $nested], [new Terminal('X')], true, 0));
57        self::assertSame([$nested], $costs->affordable([$empty, $nested], [], true, 1));
58    }
59
60    public function testAddSaturatesUnreachableCostsWithoutIntegerOverflow(): void
61    {
62        self::assertSame(PHP_INT_MAX, CompletionCosts::add(PHP_INT_MAX, 1));
63        self::assertSame(7, CompletionCosts::add(3, 4));
64    }
65
66    /**
67     * @param array{int, int} $left
68     * @param array{int, int} $right
69     * @param array{int, int} $expected
70     */
71    #[DataProvider('providerCosts')]
72    public function testCombinePreservesEmptyAndNonEmptyCompletions(array $left, array $right, array $expected): void
73    {
74        self::assertSame($expected, CompletionCosts::combine($left, $right));
75        self::assertSame($expected, CompletionCosts::combine($right, $left));
76    }
77
78    /**
79     * @return iterable<string, array{array{int, int}, array{int, int}, array{int, int}}>
80     */
81    public static function providerCosts(): iterable
82    {
83        yield 'empty pair' => [[0, PHP_INT_MAX], [0, PHP_INT_MAX], [0, PHP_INT_MAX]];
84        yield 'empty plus output' => [[2, PHP_INT_MAX], [PHP_INT_MAX, 3], [PHP_INT_MAX, 5]];
85        yield 'nullable pair' => [[2, 5], [7, 3], [9, 5]];
86        yield 'cheaper nonempty left' => [[8, 2], [1, 9], [9, 3]];
87        yield 'unreachable' => [[PHP_INT_MAX, PHP_INT_MAX], [0, 1], [PHP_INT_MAX, PHP_INT_MAX]];
88        yield 'saturating' => [[PHP_INT_MAX - 1, PHP_INT_MAX - 1], [2, 3], [PHP_INT_MAX, PHP_INT_MAX]];
89    }
90
91    public function testHasTerminalOutputDistinguishesEmittedTerminalsFromMarkersAndPendingRules(): void
92    {
93        $costs = new CompletionCosts(new Grammar('s', ['s' => new ProductionRule('s', [new Production([new Terminal('X')])])]), static fn (string $name): bool => $name === 'EOF');
94        self::assertFalse($costs->hasTerminalOutput([]));
95        self::assertFalse($costs->hasTerminalOutput([new Terminal('EOF')]));
96        self::assertFalse($costs->hasTerminalOutput([new NonTerminal('s')]));
97        self::assertTrue($costs->hasTerminalOutput([new Terminal('EOF'), new Terminal('X')]));
98        self::assertTrue($costs->hasTerminalOutput([new Terminal('X'), new Terminal('EOF')]));
99    }
100}
101