1<?php
2
3declare(strict_types=1);
4
5namespace Antlr\Antlr4\Runtime\Atn;
6
7use Antlr\Antlr4\Runtime\Atn\SemanticContexts\SemanticContext;
8use Antlr\Antlr4\Runtime\Comparison\Equality;
9use Antlr\Antlr4\Runtime\Comparison\Equivalence;
10use Antlr\Antlr4\Runtime\Comparison\Hashable;
11use Antlr\Antlr4\Runtime\Comparison\Hasher;
12use Antlr\Antlr4\Runtime\PredictionContexts\PredictionContext;
13use Antlr\Antlr4\Runtime\Utils\BitSet;
14use Antlr\Antlr4\Runtime\Utils\DoubleKeyMap;
15use Antlr\Antlr4\Runtime\Utils\Set;
16
17/**
18 * Specialized {@see Set} of `{@see ATNConfig}`s that can track info
19 * about the set, with support for combining similar configurations using
20 * a graph-structured stack.
21 */
22class ATNConfigSet implements Hashable
23{
24    /**
25     * Indicates that the set of configurations is read-only. Do not
26     * allow any code to manipulate the set; DFA states will point at
27     * the sets and they must not change. This does not protect the other
28     * fields; in particular, conflictingAlts is set after
29     * we've made this readonly.
30     *
31     * @var bool
32     */
33    protected $readOnly = false;
34
35    /**
36     * All configs but hashed by (s, i, _, pi) not including context. Wiped out
37     * when we go readonly as this set becomes a DFA state.
38     *
39     * @var Set|null
40     */
41    public $configLookup;
42
43    /**
44     * Track the elements as they are added to the set; supports get(i).
45     *
46     * @var array<ATNConfig>
47     */
48    public $configs = [];
49
50    /** @var int */
51    public $uniqueAlt = 0;
52
53    /**
54     * Currently this is only used when we detect SLL conflict; this does
55     * not necessarily represent the ambiguous alternatives. In fact, I should
56     * also point out that this seems to include predicated alternatives that
57     * have predicates that evaluate to false. Computed in computeTargetState().
58     *
59     * @var BitSet|null
60     */
61    protected $conflictingAlts;
62
63    /**
64     * Used in parser and lexer. In lexer, it indicates we hit a pred
65     * while computing a closure operation. Don't make a DFA state from this.
66     *
67     * @var bool
68     */
69    public $hasSemanticContext = false;
70
71    /** @var bool */
72    public $dipsIntoOuterContext = false;
73
74    /**
75     * Indicates that this configuration set is part of a full context LL
76     * prediction. It will be used to determine how to merge $. With SLL it's
77     * a wildcard whereas it is not for LL context merge.
78     *
79     * @var bool
80     */
81    public $fullCtx;
82
83    /** @var int|null */
84    private $cachedHashCode;
85
86    public function __construct(bool $fullCtx = true)
87    {
88        /*
89         * The reason that we need this is because we don't want the hash map to
90         * use the standard hash code and equals. We need all configurations with
91         * the same `(s,i,_,semctx)` to be equal. Unfortunately, this key
92         * effectively doubles the number of objects associated with ATNConfigs.
93         * The other solution is to use a hash table that lets us specify the
94         * equals/hashcode operation. All configs but hashed by (s, i, _, pi)
95         * not including context. Wiped out when we go readonly as this se
96         * becomes a DFA state.
97         */
98        $this->configLookup = new Set(new class implements Equivalence {
99            public function equivalent(Hashable $left, Hashable $right) : bool
100            {
101                if ($left === $right) {
102                    return true;
103                }
104
105                if (!$left instanceof ATNConfig || !$right instanceof ATNConfig) {
106                    return false;
107                }
108
109                return $left->alt === $right->alt
110                    && $left->semanticContext->equals($right->semanticContext)
111                    && Equality::equals($left->state, $right->state);
112            }
113
114            public function hash(Hashable $value) : int
115            {
116                return $value->hashCode();
117            }
118
119            public function equals(object $other) : bool
120            {
121                return $other instanceof self;
122            }
123        });
124
125        $this->fullCtx = $fullCtx;
126    }
127
128    /**
129     * Adding a new config means merging contexts with existing configs for
130     * `(s, i, pi, _)`, where `s` is the {@see ATNConfig::$state}, `i` is the
131     * {@see ATNConfig::$alt}, and `pi` is the {@see ATNConfig::$semanticContext}.
132     * We use `(s,i,pi)` as key.
133     *
134     * This method updates {@see ATNConfigSet::$dipsIntoOuterContext} and
135     * {@see ATNConfigSet::$hasSemanticContext} when necessary.
136     *
137     * @throws \InvalidArgumentException
138     */
139    public function add(ATNConfig $config, ?DoubleKeyMap $mergeCache = null) : bool
140    {
141        if ($this->readOnly || $this->configLookup === null) {
142            throw new \InvalidArgumentException('This set is readonly.');
143        }
144
145        if ($config->semanticContext !== SemanticContext::none()) {
146            $this->hasSemanticContext = true;
147        }
148
149        if ($config->reachesIntoOuterContext > 0) {
150            $this->dipsIntoOuterContext = true;
151        }
152
153        if ($this->configLookup === null) {
154            throw new \RuntimeException('This set is readonly.');
155        }
156
157        /** @var ATNConfig $existing */
158        $existing = $this->configLookup->getOrAdd($config);
159
160        if ($existing->equals($config)) {
161            $this->cachedHashCode = null;
162
163            $this->configs[] = $config; // track order here
164
165            return true;
166        }
167
168        // A previous (s,i,pi,_), merge with it and save result
169        $rootIsWildcard = !$this->fullCtx;
170
171        if ($existing->context === null || $config->context === null) {
172            throw new \RuntimeException('Unexpected null context.');
173        }
174
175        $merged = PredictionContext::merge($existing->context, $config->context, $rootIsWildcard, $mergeCache);
176
177        // No need to check for existing->context, config->context in cache
178        // since only way to create new graphs is "call rule" and here. We
179        // cache at both places.
180        $existing->reachesIntoOuterContext = \max(
181            $existing->reachesIntoOuterContext,
182            $config->reachesIntoOuterContext
183        );
184
185        // Make sure to preserve the precedence filter suppression during the merge
186        if ($config->isPrecedenceFilterSuppressed()) {
187            $existing->setPrecedenceFilterSuppressed(true);
188        }
189
190        // Replace context; no need to alt mapping
191        $existing->context = $merged;
192
193        return true;
194    }
195
196    /**
197     * Return a List holding list of configs.
198     *
199     * @return array<ATNConfig>
200     */
201    public function elements() : array
202    {
203        return $this->configs;
204    }
205
206    public function getStates() : Set
207    {
208        $states = new Set();
209        foreach ($this->configs as $config) {
210            if ($config !== null) {
211                $states->add($config->state);
212            }
213        }
214
215        return $states;
216    }
217
218    /**
219     * Gets the complete set of represented alternatives for the configurationc set.
220     *
221     * @return BitSet The set of represented alternatives in this configuration set.
222     */
223    public function getAlts() : BitSet
224    {
225        $alts = new BitSet();
226        foreach ($this->configs as $config) {
227            if ($config !== null) {
228                $alts->add($config->alt);
229            }
230        }
231
232        return $alts;
233    }
234
235    /**
236     * @return array<SemanticContext>
237     */
238    public function getPredicates() : array
239    {
240        $predicates = [];
241        foreach ($this->configs as $config) {
242            if ($config->semanticContext !== SemanticContext::none()) {
243                $predicates[] = $config->semanticContext;
244            }
245        }
246
247        return $predicates;
248    }
249
250    public function get(int $index) : ATNConfig
251    {
252        return $this->configs[$index];
253    }
254
255    public function optimizeConfigs(ATNSimulator $interpreter) : void
256    {
257        if ($this->readOnly || $this->configLookup === null) {
258            throw new \InvalidArgumentException('This set is readonly');
259        }
260
261        if ($this->configLookup->isEmpty()) {
262            return;
263        }
264
265        foreach ($this->configs as $config) {
266            if ($config !== null && $config->context !== null) {
267                $config->context = $interpreter->getCachedContext($config->context);
268            }
269        }
270    }
271
272    /**
273     * @param array<ATNConfig> $configs
274     */
275    public function addAll(array $configs) : void
276    {
277        foreach ($configs as $config) {
278            $this->add($config);
279        }
280    }
281
282    public function equals(object $other) : bool
283    {
284        if ($this === $other) {
285            return true;
286        }
287
288        if (!$other instanceof self) {
289            return false;
290        }
291
292        return $this->fullCtx === $other->fullCtx
293            && $this->uniqueAlt === $other->uniqueAlt
294            && $this->hasSemanticContext === $other->hasSemanticContext
295            && $this->dipsIntoOuterContext === $other->dipsIntoOuterContext
296            && Equality::equals($this->configs, $other->configs)
297            && Equality::equals($this->conflictingAlts, $other->conflictingAlts);
298    }
299
300    public function hashCode() : int
301    {
302        if (!$this->isReadOnly()) {
303            return Hasher::hash($this->configs);
304        }
305
306        if ($this->cachedHashCode === null) {
307            $this->cachedHashCode = Hasher::hash($this->configs);
308        }
309
310        return $this->cachedHashCode;
311    }
312
313    public function getLength() : int
314    {
315        return \count($this->configs);
316    }
317
318    public function isEmpty() : bool
319    {
320        return $this->getLength() === 0;
321    }
322
323    public function contains(object $item) : bool
324    {
325        if ($this->configLookup === null) {
326            throw new \InvalidArgumentException('This method is not implemented for readonly sets.');
327        }
328
329        return $this->configLookup->contains($item);
330    }
331
332    public function containsFast(ATNConfig $item) : bool
333    {
334        return $this->contains($item);
335    }
336
337    public function getIterator() : \Iterator
338    {
339        return new \ArrayIterator($this->configs);
340    }
341
342    public function clear() : void
343    {
344        if ($this->readOnly) {
345            throw new \InvalidArgumentException('This set is readonly');
346        }
347
348        $this->configs = [];
349        $this->cachedHashCode = -1;
350        $this->configLookup = new Set();
351    }
352
353    public function isReadOnly() : bool
354    {
355        return $this->readOnly;
356    }
357
358    public function setReadonly(bool $readOnly) : void
359    {
360        $this->readOnly = $readOnly;
361
362        if ($readOnly) {
363            $this->configLookup = null; // can't mod, no need for lookup cache
364        }
365    }
366
367    public function getConflictingAlts() : ?BitSet
368    {
369        return $this->conflictingAlts;
370    }
371
372    public function setConflictingAlts(BitSet $conflictingAlts) : void
373    {
374        $this->conflictingAlts = $conflictingAlts;
375    }
376
377    public function __toString() : string
378    {
379        return \sprintf(
380            '[%s]%s%s%s%s',
381            \implode(', ', $this->configs),
382            $this->hasSemanticContext ? ',hasSemanticContext=' . $this->hasSemanticContext : '',
383            $this->uniqueAlt !== ATN::INVALID_ALT_NUMBER ? ',uniqueAlt=' . $this->uniqueAlt : '',
384            $this->conflictingAlts !== null ? ',conflictingAlts=' . $this->conflictingAlts : '',
385            $this->dipsIntoOuterContext ? ',dipsIntoOuterContext' : ''
386        );
387    }
388}
389