packages/sql-parser/tests/Unit/Automaton/ConflictResolverTest.php
1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Unit\Automaton;
6
7use PHPUnit\Framework\Attributes\CoversClass;
8use PHPUnit\Framework\Attributes\Small;
9use PHPUnit\Framework\Attributes\UsesClass;
10use PHPUnit\Framework\TestCase;
11use SqlParser\Automaton\Bitset;
12use SqlParser\Automaton\ConflictResolver;
13use SqlParser\Automaton\ResolvedState;
14use SqlParser\Grammar\Associativity;
15use SqlParser\Grammar\Grammar;
16use SqlParser\Grammar\Precedence;
17use SqlParser\Grammar\PrecedencePolicy;
18use SqlParser\Grammar\Rule;
19use SqlParser\Grammar\SymbolTable;
20use SqlParser\Table\ActionCode;
21
22#[CoversClass(ConflictResolver::class)]
23#[UsesClass(ActionCode::class)]
24#[UsesClass(Bitset::class)]
25#[UsesClass(ResolvedState::class)]
26#[UsesClass(Grammar::class)]
27#[UsesClass(Precedence::class)]
28#[UsesClass(Rule::class)]
29#[UsesClass(SymbolTable::class)]
30#[Small]
31final class ConflictResolverTest extends TestCase
32{
33 public function testResolveKeepsPlainShiftsAndReductions(): void
34 {
35 $symbols = new SymbolTable(['$end', 'NUM', '+'], ['$accept', 'expr']);
36 $grammar = new Grammar($symbols, [new Rule(0, 3, [4, 0], 0), new Rule(1, 4, [1], 0)]);
37 $set = Bitset::empty(3);
38 Bitset::add($set, 0);
39 $resolved = (new ConflictResolver($grammar))->resolve([1 => 5], [1 => $set]);
40
41 self::assertSame([1 => 5, 0 => ActionCode::reduce(1)], $resolved->actions);
42 self::assertSame([1 => 1], $resolved->reductionCounts);
43 self::assertSame(0, $resolved->shiftReduceConflicts);
44 }
45
46 public function testResolveCountsAnUnrankedShiftReduceConflictAndShifts(): void
47 {
48 $symbols = new SymbolTable(['$end', 'NUM', '+'], ['$accept', 'expr']);
49 $grammar = new Grammar($symbols, [new Rule(0, 3, [4, 0], 0), new Rule(1, 4, [4, 2, 4], 0)]);
50 $set = Bitset::empty(3);
51 Bitset::add($set, 2);
52 $resolved = (new ConflictResolver($grammar))->resolve([2 => 5], [1 => $set]);
53
54 self::assertSame([2 => 5], $resolved->actions);
55 self::assertSame(1, $resolved->shiftReduceConflicts);
56 self::assertSame([1 => 0], $resolved->reductionCounts);
57 }
58
59 public function testResolveCountsAReduceReduceConflictAndKeepsTheEarlierRule(): void
60 {
61 $symbols = new SymbolTable(['$end', 'NUM'], ['$accept', 'a', 'b']);
62 $grammar = new Grammar($symbols, [new Rule(0, 2, [3, 0], 0), new Rule(1, 3, [1], 0), new Rule(2, 4, [1], 0)]);
63 $set = Bitset::empty(2);
64 Bitset::add($set, 0);
65 $resolved = (new ConflictResolver($grammar))->resolve([], [2 => $set, 1 => $set]);
66
67 self::assertSame([0 => ActionCode::reduce(1)], $resolved->actions);
68 self::assertSame(1, $resolved->reduceReduceConflicts);
69 }
70
71 public function testResolveLetsAHigherRankedLaterRuleWinUnderLemonsPolicy(): void
72 {
73 $symbols = new SymbolTable(['$end', 'NOT', 'IS'], ['$accept', 'expr']);
74 $precedences = [1 => new Precedence(1, Associativity::Right), 2 => new Precedence(2, Associativity::Left)];
75 $grammar = new Grammar($symbols, [new Rule(0, 3, [4, 0], 0), new Rule(1, 4, [1, 4], 0), new Rule(2, 4, [4, 2, 1, 4], 1)], $precedences, PrecedencePolicy::FirstRankedTerminal);
76 $set = Bitset::empty(3);
77 Bitset::add($set, 0);
78 $resolved = (new ConflictResolver($grammar))->resolve([], [1 => $set, 2 => $set]);
79
80 self::assertSame([0 => ActionCode::reduce(2)], $resolved->actions);
81 self::assertSame(0, $resolved->reduceReduceConflicts);
82 self::assertSame([1 => 0, 2 => 1], $resolved->reductionCounts);
83 }
84
85 public function testShiftOrReduce(): void
86 {
87 $symbols = new SymbolTable(['$end', 'NUM', '+', '*', '=', '^'], ['$accept', 'expr']);
88 $precedences = [2 => new Precedence(1, Associativity::Left), 3 => new Precedence(2, Associativity::Left), 4 => new Precedence(3, Associativity::NonAssoc), 5 => new Precedence(4, Associativity::Right)];
89 $rules = [new Rule(0, 6, [7, 0], 0), new Rule(1, 7, [7, 2, 7], 0), new Rule(2, 7, [7, 3, 7], 1), new Rule(3, 7, [7, 4, 7], 2), new Rule(4, 7, [7, 5, 7], 3), new Rule(5, 7, [1], 4)];
90 $resolver = new ConflictResolver(new Grammar($symbols, $rules, $precedences));
91
92 self::assertSame(ActionCode::reduce(1), $resolver->shiftOrReduce(2, 1));
93 self::assertSame(ActionCode::shift(0), $resolver->shiftOrReduce(3, 1));
94 self::assertSame(ActionCode::reduce(2), $resolver->shiftOrReduce(2, 2));
95 self::assertSame(ActionCode::ERROR, $resolver->shiftOrReduce(4, 3));
96 self::assertSame(ActionCode::shift(0), $resolver->shiftOrReduce(5, 4));
97 self::assertNull($resolver->shiftOrReduce(2, 5));
98 }
99
100 public function testShiftOrReduceLeavesABareRankUnresolved(): void
101 {
102 $symbols = new SymbolTable(['$end', 'NUM', 'IF'], ['$accept', 'expr']);
103 $grammar = new Grammar($symbols, [new Rule(0, 3, [4, 0], 0), new Rule(1, 4, [2, 4], 0)], [2 => new Precedence(1, Associativity::Precedence)]);
104
105 self::assertNull((new ConflictResolver($grammar))->shiftOrReduce(2, 1));
106 }
107
108 public function testReduceOrReduce(): void
109 {
110 $symbols = new SymbolTable(['$end', 'A', 'B'], ['$accept', 'x']);
111 $precedences = [1 => new Precedence(1, Associativity::Left), 2 => new Precedence(2, Associativity::Left)];
112 $rules = [new Rule(0, 3, [4, 0], 0), new Rule(1, 4, [1], 0), new Rule(2, 4, [2], 1), new Rule(3, 4, [], 2)];
113 $lemon = new ConflictResolver(new Grammar($symbols, $rules, $precedences, PrecedencePolicy::FirstRankedTerminal));
114 $bison = new ConflictResolver(new Grammar($symbols, $rules, $precedences));
115
116 self::assertSame(2, $lemon->reduceOrReduce(1, 2));
117 self::assertSame(2, $lemon->reduceOrReduce(2, 1));
118 self::assertNull($lemon->reduceOrReduce(1, 3));
119 self::assertNull($lemon->reduceOrReduce(1, 1));
120 self::assertNull($bison->reduceOrReduce(1, 2));
121 }
122}
123