1 /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
2 * Use of this file is governed by the BSD 3-clause license that
3 * can be found in the LICENSE.txt file in the project root.
4 */
5
6 #include "dfa/DFA.h"
7 #include "NoViableAltException.h"
8 #include "atn/DecisionState.h"
9 #include "ParserRuleContext.h"
10 #include "misc/IntervalSet.h"
11 #include "Parser.h"
12 #include "CommonTokenStream.h"
13 #include "atn/EmptyPredictionContext.h"
14 #include "atn/NotSetTransition.h"
15 #include "atn/AtomTransition.h"
16 #include "atn/RuleTransition.h"
17 #include "atn/PredicateTransition.h"
18 #include "atn/PrecedencePredicateTransition.h"
19 #include "atn/ActionTransition.h"
20 #include "atn/EpsilonTransition.h"
21 #include "atn/RuleStopState.h"
22 #include "atn/ATNConfigSet.h"
23 #include "atn/ATNConfig.h"
24
25 #include "atn/StarLoopEntryState.h"
26 #include "atn/BlockStartState.h"
27 #include "atn/BlockEndState.h"
28
29 #include "misc/Interval.h"
30 #include "ANTLRErrorListener.h"
31
32 #include "Vocabulary.h"
33 #include "support/Arrays.h"
34
35 #include "atn/ParserATNSimulator.h"
36
37 #define DEBUG_ATN 0
38 #define DEBUG_LIST_ATN_DECISIONS 0
39 #define DEBUG_DFA 0
40 #define RETRY_DEBUG 0
41
42 using namespace antlr4;
43 using namespace antlr4::atn;
44
45 using namespace antlrcpp;
46
47 const bool ParserATNSimulator::TURN_OFF_LR_LOOP_ENTRY_BRANCH_OPT = ParserATNSimulator::getLrLoopSetting();
48
ParserATNSimulator(const ATN & atn,std::vector<dfa::DFA> & decisionToDFA,PredictionContextCache & sharedContextCache)49 ParserATNSimulator::ParserATNSimulator(const ATN &atn, std::vector<dfa::DFA> &decisionToDFA,
50 PredictionContextCache &sharedContextCache)
51 : ParserATNSimulator(nullptr, atn, decisionToDFA, sharedContextCache) {
52 }
53
ParserATNSimulator(Parser * parser,const ATN & atn,std::vector<dfa::DFA> & decisionToDFA,PredictionContextCache & sharedContextCache)54 ParserATNSimulator::ParserATNSimulator(Parser *parser, const ATN &atn, std::vector<dfa::DFA> &decisionToDFA,
55 PredictionContextCache &sharedContextCache)
56 : ATNSimulator(atn, sharedContextCache), decisionToDFA(decisionToDFA), parser(parser) {
57 InitializeInstanceFields();
58 }
59
reset()60 void ParserATNSimulator::reset() {
61 }
62
clearDFA()63 void ParserATNSimulator::clearDFA() {
64 int size = (int)decisionToDFA.size();
65 decisionToDFA.clear();
66 for (int d = 0; d < size; ++d) {
67 decisionToDFA.push_back(dfa::DFA(atn.getDecisionState(d), d));
68 }
69 }
70
adaptivePredict(TokenStream * input,size_t decision,ParserRuleContext * outerContext)71 size_t ParserATNSimulator::adaptivePredict(TokenStream *input, size_t decision, ParserRuleContext *outerContext) {
72
73 #if DEBUG_ATN == 1 || DEBUG_LIST_ATN_DECISIONS == 1
74 std::cout << "adaptivePredict decision " << decision << " exec LA(1)==" << getLookaheadName(input) << " line "
75 << input->LT(1)->getLine() << ":" << input->LT(1)->getCharPositionInLine() << std::endl;
76 #endif
77
78 _input = input;
79 _startIndex = input->index();
80 _outerContext = outerContext;
81 dfa::DFA &dfa = decisionToDFA[decision];
82 _dfa = &dfa;
83
84 ssize_t m = input->mark();
85 size_t index = _startIndex;
86
87 // Now we are certain to have a specific decision's DFA
88 // But, do we still need an initial state?
89 auto onExit = finally([this, input, index, m] {
90 mergeCache.clear(); // wack cache after each prediction
91 _dfa = nullptr;
92 input->seek(index);
93 input->release(m);
94 });
95
96 dfa::DFAState *s0;
97 if (dfa.isPrecedenceDfa()) {
98 // the start state for a precedence DFA depends on the current
99 // parser precedence, and is provided by a DFA method.
100 s0 = dfa.getPrecedenceStartState(parser->getPrecedence());
101 } else {
102 // the start state for a "regular" DFA is just s0
103 s0 = dfa.s0;
104 }
105
106 if (s0 == nullptr) {
107 bool fullCtx = false;
108 std::unique_ptr<ATNConfigSet> s0_closure = computeStartState(dynamic_cast<ATNState *>(dfa.atnStartState),
109 &ParserRuleContext::EMPTY, fullCtx);
110
111 _stateLock.writeLock();
112 if (dfa.isPrecedenceDfa()) {
113 /* If this is a precedence DFA, we use applyPrecedenceFilter
114 * to convert the computed start state to a precedence start
115 * state. We then use DFA.setPrecedenceStartState to set the
116 * appropriate start state for the precedence level rather
117 * than simply setting DFA.s0.
118 */
119 dfa.s0->configs = std::move(s0_closure); // not used for prediction but useful to know start configs anyway
120 dfa::DFAState *newState = new dfa::DFAState(applyPrecedenceFilter(dfa.s0->configs.get())); /* mem-check: managed by the DFA or deleted below */
121 s0 = addDFAState(dfa, newState);
122 dfa.setPrecedenceStartState(parser->getPrecedence(), s0, _edgeLock);
123 if (s0 != newState) {
124 delete newState; // If there was already a state with this config set we don't need the new one.
125 }
126 } else {
127 dfa::DFAState *newState = new dfa::DFAState(std::move(s0_closure)); /* mem-check: managed by the DFA or deleted below */
128 s0 = addDFAState(dfa, newState);
129
130 if (dfa.s0 != s0) {
131 delete dfa.s0; // Delete existing s0 DFA state, if there's any.
132 dfa.s0 = s0;
133 }
134 if (s0 != newState) {
135 delete newState; // If there was already a state with this config set we don't need the new one.
136 }
137 }
138 _stateLock.writeUnlock();
139 }
140
141 // We can start with an existing DFA.
142 size_t alt = execATN(dfa, s0, input, index, outerContext != nullptr ? outerContext : &ParserRuleContext::EMPTY);
143
144 return alt;
145 }
146
execATN(dfa::DFA & dfa,dfa::DFAState * s0,TokenStream * input,size_t startIndex,ParserRuleContext * outerContext)147 size_t ParserATNSimulator::execATN(dfa::DFA &dfa, dfa::DFAState *s0, TokenStream *input, size_t startIndex,
148 ParserRuleContext *outerContext) {
149
150 #if DEBUG_ATN == 1 || DEBUG_LIST_ATN_DECISIONS == 1
151 std::cout << "execATN decision " << dfa.decision << " exec LA(1)==" << getLookaheadName(input) <<
152 " line " << input->LT(1)->getLine() << ":" << input->LT(1)->getCharPositionInLine() << std::endl;
153 #endif
154
155 dfa::DFAState *previousD = s0;
156
157 #if DEBUG_ATN == 1
158 std::cout << "s0 = " << s0 << std::endl;
159 #endif
160
161 size_t t = input->LA(1);
162
163 while (true) { // while more work
164 dfa::DFAState *D = getExistingTargetState(previousD, t);
165 if (D == nullptr) {
166 D = computeTargetState(dfa, previousD, t);
167 }
168
169 if (D == ERROR.get()) {
170 // if any configs in previous dipped into outer context, that
171 // means that input up to t actually finished entry rule
172 // at least for SLL decision. Full LL doesn't dip into outer
173 // so don't need special case.
174 // We will get an error no matter what so delay until after
175 // decision; better error message. Also, no reachable target
176 // ATN states in SLL implies LL will also get nowhere.
177 // If conflict in states that dip out, choose min since we
178 // will get error no matter what.
179 NoViableAltException e = noViableAlt(input, outerContext, previousD->configs.get(), startIndex, false);
180 input->seek(startIndex);
181 size_t alt = getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule(previousD->configs.get(), outerContext);
182 if (alt != ATN::INVALID_ALT_NUMBER) {
183 return alt;
184 }
185
186 throw e;
187 }
188
189 if (D->requiresFullContext && _mode != PredictionMode::SLL) {
190 // IF PREDS, MIGHT RESOLVE TO SINGLE ALT => SLL (or syntax error)
191 BitSet conflictingAlts;
192 if (D->predicates.size() != 0) {
193 #if DEBUG_ATN == 1
194 std::cout << "DFA state has preds in DFA sim LL failover" << std::endl;
195 #endif
196
197 size_t conflictIndex = input->index();
198 if (conflictIndex != startIndex) {
199 input->seek(startIndex);
200 }
201
202 conflictingAlts = evalSemanticContext(D->predicates, outerContext, true);
203 if (conflictingAlts.count() == 1) {
204 #if DEBUG_ATN == 1
205 std::cout << "Full LL avoided" << std::endl;
206 #endif
207
208 return conflictingAlts.nextSetBit(0);
209 }
210
211 if (conflictIndex != startIndex) {
212 // restore the index so reporting the fallback to full
213 // context occurs with the index at the correct spot
214 input->seek(conflictIndex);
215 }
216 }
217
218 #if DEBUG_DFA == 1
219 std::cout << "ctx sensitive state " << outerContext << " in " << D << std::endl;
220 #endif
221
222 bool fullCtx = true;
223 Ref<ATNConfigSet> s0_closure = computeStartState(dfa.atnStartState, outerContext, fullCtx);
224 reportAttemptingFullContext(dfa, conflictingAlts, D->configs.get(), startIndex, input->index());
225 size_t alt = execATNWithFullContext(dfa, D, s0_closure.get(), input, startIndex, outerContext);
226 return alt;
227 }
228
229 if (D->isAcceptState) {
230 if (D->predicates.empty()) {
231 return D->prediction;
232 }
233
234 size_t stopIndex = input->index();
235 input->seek(startIndex);
236 BitSet alts = evalSemanticContext(D->predicates, outerContext, true);
237 switch (alts.count()) {
238 case 0:
239 throw noViableAlt(input, outerContext, D->configs.get(), startIndex, false);
240
241 case 1:
242 return alts.nextSetBit(0);
243
244 default:
245 // report ambiguity after predicate evaluation to make sure the correct
246 // set of ambig alts is reported.
247 reportAmbiguity(dfa, D, startIndex, stopIndex, false, alts, D->configs.get());
248 return alts.nextSetBit(0);
249 }
250 }
251
252 previousD = D;
253
254 if (t != Token::EOF) {
255 input->consume();
256 t = input->LA(1);
257 }
258 }
259 }
260
getExistingTargetState(dfa::DFAState * previousD,size_t t)261 dfa::DFAState *ParserATNSimulator::getExistingTargetState(dfa::DFAState *previousD, size_t t) {
262 dfa::DFAState* retval;
263 _edgeLock.readLock();
264 auto iterator = previousD->edges.find(t);
265 retval = (iterator == previousD->edges.end()) ? nullptr : iterator->second;
266 _edgeLock.readUnlock();
267 return retval;
268 }
269
computeTargetState(dfa::DFA & dfa,dfa::DFAState * previousD,size_t t)270 dfa::DFAState *ParserATNSimulator::computeTargetState(dfa::DFA &dfa, dfa::DFAState *previousD, size_t t) {
271 std::unique_ptr<ATNConfigSet> reach = computeReachSet(previousD->configs.get(), t, false);
272 if (reach == nullptr) {
273 addDFAEdge(dfa, previousD, t, ERROR.get());
274 return ERROR.get();
275 }
276
277 // create new target state; we'll add to DFA after it's complete
278 dfa::DFAState *D = new dfa::DFAState(std::move(reach)); /* mem-check: managed by the DFA or deleted below, "reach" is no longer valid now. */
279 size_t predictedAlt = getUniqueAlt(D->configs.get());
280
281 if (predictedAlt != ATN::INVALID_ALT_NUMBER) {
282 // NO CONFLICT, UNIQUELY PREDICTED ALT
283 D->isAcceptState = true;
284 D->configs->uniqueAlt = predictedAlt;
285 D->prediction = predictedAlt;
286 } else if (PredictionModeClass::hasSLLConflictTerminatingPrediction(_mode, D->configs.get())) {
287 // MORE THAN ONE VIABLE ALTERNATIVE
288 D->configs->conflictingAlts = getConflictingAlts(D->configs.get());
289 D->requiresFullContext = true;
290 // in SLL-only mode, we will stop at this state and return the minimum alt
291 D->isAcceptState = true;
292 D->prediction = D->configs->conflictingAlts.nextSetBit(0);
293 }
294
295 if (D->isAcceptState && D->configs->hasSemanticContext) {
296 predicateDFAState(D, atn.getDecisionState(dfa.decision));
297 if (D->predicates.size() != 0) {
298 D->prediction = ATN::INVALID_ALT_NUMBER;
299 }
300 }
301
302 // all adds to dfa are done after we've created full D state
303 dfa::DFAState *state = addDFAEdge(dfa, previousD, t, D);
304 if (state != D) {
305 delete D; // If the new state exists already we don't need it and use the existing one instead.
306 }
307 return state;
308 }
309
predicateDFAState(dfa::DFAState * dfaState,DecisionState * decisionState)310 void ParserATNSimulator::predicateDFAState(dfa::DFAState *dfaState, DecisionState *decisionState) {
311 // We need to test all predicates, even in DFA states that
312 // uniquely predict alternative.
313 size_t nalts = decisionState->transitions.size();
314
315 // Update DFA so reach becomes accept state with (predicate,alt)
316 // pairs if preds found for conflicting alts
317 BitSet altsToCollectPredsFrom = getConflictingAltsOrUniqueAlt(dfaState->configs.get());
318 std::vector<Ref<SemanticContext>> altToPred = getPredsForAmbigAlts(altsToCollectPredsFrom, dfaState->configs.get(), nalts);
319 if (!altToPred.empty()) {
320 dfaState->predicates = getPredicatePredictions(altsToCollectPredsFrom, altToPred);
321 dfaState->prediction = ATN::INVALID_ALT_NUMBER; // make sure we use preds
322 } else {
323 // There are preds in configs but they might go away
324 // when OR'd together like {p}? || NONE == NONE. If neither
325 // alt has preds, resolve to min alt
326 dfaState->prediction = altsToCollectPredsFrom.nextSetBit(0);
327 }
328 }
329
execATNWithFullContext(dfa::DFA & dfa,dfa::DFAState * D,ATNConfigSet * s0,TokenStream * input,size_t startIndex,ParserRuleContext * outerContext)330 size_t ParserATNSimulator::execATNWithFullContext(dfa::DFA &dfa, dfa::DFAState *D, ATNConfigSet *s0,
331 TokenStream *input, size_t startIndex, ParserRuleContext *outerContext) {
332
333 bool fullCtx = true;
334 bool foundExactAmbig = false;
335
336 std::unique_ptr<ATNConfigSet> reach;
337 ATNConfigSet *previous = s0;
338 input->seek(startIndex);
339 size_t t = input->LA(1);
340 size_t predictedAlt;
341
342 while (true) {
343 reach = computeReachSet(previous, t, fullCtx);
344 if (reach == nullptr) {
345 // if any configs in previous dipped into outer context, that
346 // means that input up to t actually finished entry rule
347 // at least for LL decision. Full LL doesn't dip into outer
348 // so don't need special case.
349 // We will get an error no matter what so delay until after
350 // decision; better error message. Also, no reachable target
351 // ATN states in SLL implies LL will also get nowhere.
352 // If conflict in states that dip out, choose min since we
353 // will get error no matter what.
354 NoViableAltException e = noViableAlt(input, outerContext, previous, startIndex, previous != s0);
355 input->seek(startIndex);
356 size_t alt = getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule(previous, outerContext);
357 if (alt != ATN::INVALID_ALT_NUMBER) {
358 return alt;
359 }
360 throw e;
361 }
362 if (previous != s0) // Don't delete the start set.
363 delete previous;
364 previous = nullptr;
365
366 std::vector<BitSet> altSubSets = PredictionModeClass::getConflictingAltSubsets(reach.get());
367 reach->uniqueAlt = getUniqueAlt(reach.get());
368 // unique prediction?
369 if (reach->uniqueAlt != ATN::INVALID_ALT_NUMBER) {
370 predictedAlt = reach->uniqueAlt;
371 break;
372 }
373 if (_mode != PredictionMode::LL_EXACT_AMBIG_DETECTION) {
374 predictedAlt = PredictionModeClass::resolvesToJustOneViableAlt(altSubSets);
375 if (predictedAlt != ATN::INVALID_ALT_NUMBER) {
376 break;
377 }
378 } else {
379 // In exact ambiguity mode, we never try to terminate early.
380 // Just keeps scarfing until we know what the conflict is
381 if (PredictionModeClass::allSubsetsConflict(altSubSets) && PredictionModeClass::allSubsetsEqual(altSubSets)) {
382 foundExactAmbig = true;
383 predictedAlt = PredictionModeClass::getSingleViableAlt(altSubSets);
384 break;
385 }
386 // else there are multiple non-conflicting subsets or
387 // we're not sure what the ambiguity is yet.
388 // So, keep going.
389 }
390 previous = reach.release();
391
392 if (t != Token::EOF) {
393 input->consume();
394 t = input->LA(1);
395 }
396 }
397
398 // If the configuration set uniquely predicts an alternative,
399 // without conflict, then we know that it's a full LL decision
400 // not SLL.
401 if (reach->uniqueAlt != ATN::INVALID_ALT_NUMBER) {
402 reportContextSensitivity(dfa, predictedAlt, reach.get(), startIndex, input->index());
403 return predictedAlt;
404 }
405
406 // We do not check predicates here because we have checked them
407 // on-the-fly when doing full context prediction.
408
409 /*
410 In non-exact ambiguity detection mode, we might actually be able to
411 detect an exact ambiguity, but I'm not going to spend the cycles
412 needed to check. We only emit ambiguity warnings in exact ambiguity
413 mode.
414
415 For example, we might know that we have conflicting configurations.
416 But, that does not mean that there is no way forward without a
417 conflict. It's possible to have nonconflicting alt subsets as in:
418
419 LL altSubSets=[{1, 2}, {1, 2}, {1}, {1, 2}]
420
421 from
422
423 [(17,1,[5 $]), (13,1,[5 10 $]), (21,1,[5 10 $]), (11,1,[$]),
424 (13,2,[5 10 $]), (21,2,[5 10 $]), (11,2,[$])]
425
426 In this case, (17,1,[5 $]) indicates there is some next sequence that
427 would resolve this without conflict to alternative 1. Any other viable
428 next sequence, however, is associated with a conflict. We stop
429 looking for input because no amount of further lookahead will alter
430 the fact that we should predict alternative 1. We just can't say for
431 sure that there is an ambiguity without looking further.
432 */
433 reportAmbiguity(dfa, D, startIndex, input->index(), foundExactAmbig, reach->getAlts(), reach.get());
434
435 return predictedAlt;
436 }
437
computeReachSet(ATNConfigSet * closure_,size_t t,bool fullCtx)438 std::unique_ptr<ATNConfigSet> ParserATNSimulator::computeReachSet(ATNConfigSet *closure_, size_t t, bool fullCtx) {
439
440 std::unique_ptr<ATNConfigSet> intermediate(new ATNConfigSet(fullCtx));
441
442 /* Configurations already in a rule stop state indicate reaching the end
443 * of the decision rule (local context) or end of the start rule (full
444 * context). Once reached, these configurations are never updated by a
445 * closure operation, so they are handled separately for the performance
446 * advantage of having a smaller intermediate set when calling closure.
447 *
448 * For full-context reach operations, separate handling is required to
449 * ensure that the alternative matching the longest overall sequence is
450 * chosen when multiple such configurations can match the input.
451 */
452 std::vector<Ref<ATNConfig>> skippedStopStates;
453
454 // First figure out where we can reach on input t
455 for (auto &c : closure_->configs) {
456 if (is<RuleStopState *>(c->state)) {
457 assert(c->context->isEmpty());
458
459 if (fullCtx || t == Token::EOF) {
460 skippedStopStates.push_back(c);
461 }
462
463 continue;
464 }
465
466 size_t n = c->state->transitions.size();
467 for (size_t ti = 0; ti < n; ti++) { // for each transition
468 Transition *trans = c->state->transitions[ti];
469 ATNState *target = getReachableTarget(trans, (int)t);
470 if (target != nullptr) {
471 intermediate->add(std::make_shared<ATNConfig>(c, target), &mergeCache);
472 }
473 }
474 }
475
476 // Now figure out where the reach operation can take us...
477 std::unique_ptr<ATNConfigSet> reach;
478
479 /* This block optimizes the reach operation for intermediate sets which
480 * trivially indicate a termination state for the overall
481 * adaptivePredict operation.
482 *
483 * The conditions assume that intermediate
484 * contains all configurations relevant to the reach set, but this
485 * condition is not true when one or more configurations have been
486 * withheld in skippedStopStates, or when the current symbol is EOF.
487 */
488 if (skippedStopStates.empty() && t != Token::EOF) {
489 if (intermediate->size() == 1) {
490 // Don't pursue the closure if there is just one state.
491 // It can only have one alternative; just add to result
492 // Also don't pursue the closure if there is unique alternative
493 // among the configurations.
494 reach = std::move(intermediate);
495 } else if (getUniqueAlt(intermediate.get()) != ATN::INVALID_ALT_NUMBER) {
496 // Also don't pursue the closure if there is unique alternative
497 // among the configurations.
498 reach = std::move(intermediate);
499 }
500 }
501
502 /* If the reach set could not be trivially determined, perform a closure
503 * operation on the intermediate set to compute its initial value.
504 */
505 if (reach == nullptr) {
506 reach.reset(new ATNConfigSet(fullCtx));
507 ATNConfig::Set closureBusy;
508
509 bool treatEofAsEpsilon = t == Token::EOF;
510 for (auto c : intermediate->configs) {
511 closure(c, reach.get(), closureBusy, false, fullCtx, treatEofAsEpsilon);
512 }
513 }
514
515 if (t == IntStream::EOF) {
516 /* After consuming EOF no additional input is possible, so we are
517 * only interested in configurations which reached the end of the
518 * decision rule (local context) or end of the start rule (full
519 * context). Update reach to contain only these configurations. This
520 * handles both explicit EOF transitions in the grammar and implicit
521 * EOF transitions following the end of the decision or start rule.
522 *
523 * When reach==intermediate, no closure operation was performed. In
524 * this case, removeAllConfigsNotInRuleStopState needs to check for
525 * reachable rule stop states as well as configurations already in
526 * a rule stop state.
527 *
528 * This is handled before the configurations in skippedStopStates,
529 * because any configurations potentially added from that list are
530 * already guaranteed to meet this condition whether or not it's
531 * required.
532 */
533 ATNConfigSet *temp = removeAllConfigsNotInRuleStopState(reach.get(), *reach == *intermediate);
534 if (temp != reach.get())
535 reach.reset(temp); // We got a new set, so use that.
536 }
537
538 /* If skippedStopStates is not null, then it contains at least one
539 * configuration. For full-context reach operations, these
540 * configurations reached the end of the start rule, in which case we
541 * only add them back to reach if no configuration during the current
542 * closure operation reached such a state. This ensures adaptivePredict
543 * chooses an alternative matching the longest overall sequence when
544 * multiple alternatives are viable.
545 */
546 if (skippedStopStates.size() > 0 && (!fullCtx || !PredictionModeClass::hasConfigInRuleStopState(reach.get()))) {
547 assert(!skippedStopStates.empty());
548
549 for (auto c : skippedStopStates) {
550 reach->add(c, &mergeCache);
551 }
552 }
553
554 if (reach->isEmpty()) {
555 return nullptr;
556 }
557 return reach;
558 }
559
removeAllConfigsNotInRuleStopState(ATNConfigSet * configs,bool lookToEndOfRule)560 ATNConfigSet* ParserATNSimulator::removeAllConfigsNotInRuleStopState(ATNConfigSet *configs,
561 bool lookToEndOfRule) {
562 if (PredictionModeClass::allConfigsInRuleStopStates(configs)) {
563 return configs;
564 }
565
566 ATNConfigSet *result = new ATNConfigSet(configs->fullCtx); /* mem-check: released by caller */
567
568 for (auto &config : configs->configs) {
569 if (is<RuleStopState*>(config->state)) {
570 result->add(config, &mergeCache);
571 continue;
572 }
573
574 if (lookToEndOfRule && config->state->epsilonOnlyTransitions) {
575 misc::IntervalSet nextTokens = atn.nextTokens(config->state);
576 if (nextTokens.contains(Token::EPSILON)) {
577 ATNState *endOfRuleState = atn.ruleToStopState[config->state->ruleIndex];
578 result->add(std::make_shared<ATNConfig>(config, endOfRuleState), &mergeCache);
579 }
580 }
581 }
582
583 return result;
584 }
585
computeStartState(ATNState * p,RuleContext * ctx,bool fullCtx)586 std::unique_ptr<ATNConfigSet> ParserATNSimulator::computeStartState(ATNState *p, RuleContext *ctx, bool fullCtx) {
587 // always at least the implicit call to start rule
588 Ref<PredictionContext> initialContext = PredictionContext::fromRuleContext(atn, ctx);
589 std::unique_ptr<ATNConfigSet> configs(new ATNConfigSet(fullCtx));
590
591 for (size_t i = 0; i < p->transitions.size(); i++) {
592 ATNState *target = p->transitions[i]->target;
593 Ref<ATNConfig> c = std::make_shared<ATNConfig>(target, (int)i + 1, initialContext);
594 ATNConfig::Set closureBusy;
595 closure(c, configs.get(), closureBusy, true, fullCtx, false);
596 }
597
598 return configs;
599 }
600
applyPrecedenceFilter(ATNConfigSet * configs)601 std::unique_ptr<ATNConfigSet> ParserATNSimulator::applyPrecedenceFilter(ATNConfigSet *configs) {
602 std::map<size_t, Ref<PredictionContext>> statesFromAlt1;
603 std::unique_ptr<ATNConfigSet> configSet(new ATNConfigSet(configs->fullCtx));
604 for (Ref<ATNConfig> &config : configs->configs) {
605 // handle alt 1 first
606 if (config->alt != 1) {
607 continue;
608 }
609
610 Ref<SemanticContext> updatedContext = config->semanticContext->evalPrecedence(parser, _outerContext);
611 if (updatedContext == nullptr) {
612 // the configuration was eliminated
613 continue;
614 }
615
616 statesFromAlt1[config->state->stateNumber] = config->context;
617 if (updatedContext != config->semanticContext) {
618 configSet->add(std::make_shared<ATNConfig>(config, updatedContext), &mergeCache);
619 }
620 else {
621 configSet->add(config, &mergeCache);
622 }
623 }
624
625 for (Ref<ATNConfig> &config : configs->configs) {
626 if (config->alt == 1) {
627 // already handled
628 continue;
629 }
630
631 if (!config->isPrecedenceFilterSuppressed()) {
632 /* In the future, this elimination step could be updated to also
633 * filter the prediction context for alternatives predicting alt>1
634 * (basically a graph subtraction algorithm).
635 */
636 auto iterator = statesFromAlt1.find(config->state->stateNumber);
637 if (iterator != statesFromAlt1.end() && *iterator->second == *config->context) {
638 // eliminated
639 continue;
640 }
641 }
642
643 configSet->add(config, &mergeCache);
644 }
645
646 return configSet;
647 }
648
getReachableTarget(Transition * trans,size_t ttype)649 atn::ATNState* ParserATNSimulator::getReachableTarget(Transition *trans, size_t ttype) {
650 if (trans->matches(ttype, 0, atn.maxTokenType)) {
651 return trans->target;
652 }
653
654 return nullptr;
655 }
656
657 // Note that caller must memory manage the returned value from this function
getPredsForAmbigAlts(const BitSet & ambigAlts,ATNConfigSet * configs,size_t nalts)658 std::vector<Ref<SemanticContext>> ParserATNSimulator::getPredsForAmbigAlts(const BitSet &ambigAlts,
659 ATNConfigSet *configs, size_t nalts) {
660 // REACH=[1|1|[]|0:0, 1|2|[]|0:1]
661 /* altToPred starts as an array of all null contexts. The entry at index i
662 * corresponds to alternative i. altToPred[i] may have one of three values:
663 * 1. null: no ATNConfig c is found such that c.alt==i
664 * 2. SemanticContext.NONE: At least one ATNConfig c exists such that
665 * c.alt==i and c.semanticContext==SemanticContext.NONE. In other words,
666 * alt i has at least one un-predicated config.
667 * 3. Non-NONE Semantic Context: There exists at least one, and for all
668 * ATNConfig c such that c.alt==i, c.semanticContext!=SemanticContext.NONE.
669 *
670 * From this, it is clear that NONE||anything==NONE.
671 */
672 std::vector<Ref<SemanticContext>> altToPred(nalts + 1);
673
674 for (auto &c : configs->configs) {
675 if (ambigAlts.test(c->alt)) {
676 altToPred[c->alt] = SemanticContext::Or(altToPred[c->alt], c->semanticContext);
677 }
678 }
679
680 size_t nPredAlts = 0;
681 for (size_t i = 1; i <= nalts; i++) {
682 if (altToPred[i] == nullptr) {
683 altToPred[i] = SemanticContext::NONE;
684 } else if (altToPred[i] != SemanticContext::NONE) {
685 nPredAlts++;
686 }
687 }
688
689 // nonambig alts are null in altToPred
690 if (nPredAlts == 0) {
691 altToPred.clear();
692 }
693 #if DEBUG_ATN == 1
694 std::cout << "getPredsForAmbigAlts result " << Arrays::toString(altToPred) << std::endl;
695 #endif
696
697 return altToPred;
698 }
699
getPredicatePredictions(const antlrcpp::BitSet & ambigAlts,std::vector<Ref<SemanticContext>> const & altToPred)700 std::vector<dfa::DFAState::PredPrediction *> ParserATNSimulator::getPredicatePredictions(const antlrcpp::BitSet &ambigAlts,
701 std::vector<Ref<SemanticContext>> const& altToPred) {
702 bool containsPredicate = std::find_if(altToPred.begin(), altToPred.end(), [](Ref<SemanticContext> const context) {
703 return context != SemanticContext::NONE;
704 }) != altToPred.end();
705 if (!containsPredicate)
706 return {};
707
708 std::vector<dfa::DFAState::PredPrediction*> pairs;
709 for (size_t i = 1; i < altToPred.size(); ++i) {
710 Ref<SemanticContext> const& pred = altToPred[i];
711 assert(pred != nullptr); // unpredicted is indicated by SemanticContext.NONE
712
713 if (ambigAlts.test(i)) {
714 pairs.push_back(new dfa::DFAState::PredPrediction(pred, (int)i)); /* mem-check: managed by the DFAState it will be assigned to after return */
715 }
716 }
717 return pairs;
718 }
719
getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule(ATNConfigSet * configs,ParserRuleContext * outerContext)720 size_t ParserATNSimulator::getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule(ATNConfigSet *configs,
721 ParserRuleContext *outerContext)
722 {
723 std::pair<ATNConfigSet *, ATNConfigSet *> sets = splitAccordingToSemanticValidity(configs, outerContext);
724 std::unique_ptr<ATNConfigSet> semValidConfigs(sets.first);
725 std::unique_ptr<ATNConfigSet> semInvalidConfigs(sets.second);
726 size_t alt = getAltThatFinishedDecisionEntryRule(semValidConfigs.get());
727 if (alt != ATN::INVALID_ALT_NUMBER) { // semantically/syntactically viable path exists
728 return alt;
729 }
730 // Is there a syntactically valid path with a failed pred?
731 if (!semInvalidConfigs->configs.empty()) {
732 alt = getAltThatFinishedDecisionEntryRule(semInvalidConfigs.get());
733 if (alt != ATN::INVALID_ALT_NUMBER) { // syntactically viable path exists
734 return alt;
735 }
736 }
737 return ATN::INVALID_ALT_NUMBER;
738 }
739
getAltThatFinishedDecisionEntryRule(ATNConfigSet * configs)740 size_t ParserATNSimulator::getAltThatFinishedDecisionEntryRule(ATNConfigSet *configs) {
741 misc::IntervalSet alts;
742 for (auto &c : configs->configs) {
743 if (c->getOuterContextDepth() > 0 || (is<RuleStopState *>(c->state) && c->context->hasEmptyPath())) {
744 alts.add(c->alt);
745 }
746 }
747 if (alts.size() == 0) {
748 return ATN::INVALID_ALT_NUMBER;
749 }
750 return alts.getMinElement();
751 }
752
splitAccordingToSemanticValidity(ATNConfigSet * configs,ParserRuleContext * outerContext)753 std::pair<ATNConfigSet *, ATNConfigSet *> ParserATNSimulator::splitAccordingToSemanticValidity(ATNConfigSet *configs,
754 ParserRuleContext *outerContext) {
755
756 // mem-check: both pointers must be freed by the caller.
757 ATNConfigSet *succeeded(new ATNConfigSet(configs->fullCtx));
758 ATNConfigSet *failed(new ATNConfigSet(configs->fullCtx));
759 for (Ref<ATNConfig> &c : configs->configs) {
760 if (c->semanticContext != SemanticContext::NONE) {
761 bool predicateEvaluationResult = evalSemanticContext(c->semanticContext, outerContext, c->alt, configs->fullCtx);
762 if (predicateEvaluationResult) {
763 succeeded->add(c);
764 } else {
765 failed->add(c);
766 }
767 } else {
768 succeeded->add(c);
769 }
770 }
771 return { succeeded, failed };
772 }
773
evalSemanticContext(std::vector<dfa::DFAState::PredPrediction * > predPredictions,ParserRuleContext * outerContext,bool complete)774 BitSet ParserATNSimulator::evalSemanticContext(std::vector<dfa::DFAState::PredPrediction*> predPredictions,
775 ParserRuleContext *outerContext, bool complete) {
776 BitSet predictions;
777 for (auto prediction : predPredictions) {
778 if (prediction->pred == SemanticContext::NONE) {
779 predictions.set(prediction->alt);
780 if (!complete) {
781 break;
782 }
783 continue;
784 }
785
786 bool fullCtx = false; // in dfa
787 bool predicateEvaluationResult = evalSemanticContext(prediction->pred, outerContext, prediction->alt, fullCtx);
788 #if DEBUG_ATN == 1 || DEBUG_DFA == 1
789 std::cout << "eval pred " << prediction->toString() << " = " << predicateEvaluationResult << std::endl;
790 #endif
791
792 if (predicateEvaluationResult) {
793 #if DEBUG_ATN == 1 || DEBUG_DFA == 1
794 std::cout << "PREDICT " << prediction->alt << std::endl;
795 #endif
796
797 predictions.set(prediction->alt);
798 if (!complete) {
799 break;
800 }
801 }
802 }
803
804 return predictions;
805 }
806
evalSemanticContext(Ref<SemanticContext> const & pred,ParserRuleContext * parserCallStack,size_t,bool)807 bool ParserATNSimulator::evalSemanticContext(Ref<SemanticContext> const& pred, ParserRuleContext *parserCallStack,
808 size_t /*alt*/, bool /*fullCtx*/) {
809 return pred->eval(parser, parserCallStack);
810 }
811
closure(Ref<ATNConfig> const & config,ATNConfigSet * configs,ATNConfig::Set & closureBusy,bool collectPredicates,bool fullCtx,bool treatEofAsEpsilon)812 void ParserATNSimulator::closure(Ref<ATNConfig> const& config, ATNConfigSet *configs, ATNConfig::Set &closureBusy,
813 bool collectPredicates, bool fullCtx, bool treatEofAsEpsilon) {
814 const int initialDepth = 0;
815 closureCheckingStopState(config, configs, closureBusy, collectPredicates, fullCtx, initialDepth, treatEofAsEpsilon);
816
817 assert(!fullCtx || !configs->dipsIntoOuterContext);
818 }
819
closureCheckingStopState(Ref<ATNConfig> const & config,ATNConfigSet * configs,ATNConfig::Set & closureBusy,bool collectPredicates,bool fullCtx,int depth,bool treatEofAsEpsilon)820 void ParserATNSimulator::closureCheckingStopState(Ref<ATNConfig> const& config, ATNConfigSet *configs,
821 ATNConfig::Set &closureBusy, bool collectPredicates, bool fullCtx, int depth, bool treatEofAsEpsilon) {
822
823 #if DEBUG_ATN == 1
824 std::cout << "closure(" << config->toString(true) << ")" << std::endl;
825 #endif
826
827 if (is<RuleStopState *>(config->state)) {
828 // We hit rule end. If we have context info, use it
829 // run thru all possible stack tops in ctx
830 if (!config->context->isEmpty()) {
831 for (size_t i = 0; i < config->context->size(); i++) {
832 if (config->context->getReturnState(i) == PredictionContext::EMPTY_RETURN_STATE) {
833 if (fullCtx) {
834 configs->add(std::make_shared<ATNConfig>(config, config->state, PredictionContext::EMPTY), &mergeCache);
835 continue;
836 } else {
837 // we have no context info, just chase follow links (if greedy)
838 #if DEBUG_ATN == 1
839 std::cout << "FALLING off rule " << getRuleName(config->state->ruleIndex) << std::endl;
840 #endif
841 closure_(config, configs, closureBusy, collectPredicates, fullCtx, depth, treatEofAsEpsilon);
842 }
843 continue;
844 }
845 ATNState *returnState = atn.states[config->context->getReturnState(i)];
846 std::weak_ptr<PredictionContext> newContext = config->context->getParent(i); // "pop" return state
847 Ref<ATNConfig> c = std::make_shared<ATNConfig>(returnState, config->alt, newContext.lock(), config->semanticContext);
848 // While we have context to pop back from, we may have
849 // gotten that context AFTER having falling off a rule.
850 // Make sure we track that we are now out of context.
851 //
852 // This assignment also propagates the
853 // isPrecedenceFilterSuppressed() value to the new
854 // configuration.
855 c->reachesIntoOuterContext = config->reachesIntoOuterContext;
856 assert(depth > INT_MIN);
857
858 closureCheckingStopState(c, configs, closureBusy, collectPredicates, fullCtx, depth - 1, treatEofAsEpsilon);
859 }
860 return;
861 } else if (fullCtx) {
862 // reached end of start rule
863 configs->add(config, &mergeCache);
864 return;
865 } else {
866 // else if we have no context info, just chase follow links (if greedy)
867 }
868 }
869
870 closure_(config, configs, closureBusy, collectPredicates, fullCtx, depth, treatEofAsEpsilon);
871 }
872
closure_(Ref<ATNConfig> const & config,ATNConfigSet * configs,ATNConfig::Set & closureBusy,bool collectPredicates,bool fullCtx,int depth,bool treatEofAsEpsilon)873 void ParserATNSimulator::closure_(Ref<ATNConfig> const& config, ATNConfigSet *configs, ATNConfig::Set &closureBusy,
874 bool collectPredicates, bool fullCtx, int depth, bool treatEofAsEpsilon) {
875 ATNState *p = config->state;
876 // optimization
877 if (!p->epsilonOnlyTransitions) {
878 // make sure to not return here, because EOF transitions can act as
879 // both epsilon transitions and non-epsilon transitions.
880 configs->add(config, &mergeCache);
881 }
882
883 for (size_t i = 0; i < p->transitions.size(); i++) {
884 if (i == 0 && canDropLoopEntryEdgeInLeftRecursiveRule(config.get()))
885 continue;
886
887 Transition *t = p->transitions[i];
888 bool continueCollecting = !is<ActionTransition*>(t) && collectPredicates;
889 Ref<ATNConfig> c = getEpsilonTarget(config, t, continueCollecting, depth == 0, fullCtx, treatEofAsEpsilon);
890 if (c != nullptr) {
891 int newDepth = depth;
892 if (is<RuleStopState*>(config->state)) {
893 assert(!fullCtx);
894
895 // target fell off end of rule; mark resulting c as having dipped into outer context
896 // We can't get here if incoming config was rule stop and we had context
897 // track how far we dip into outer context. Might
898 // come in handy and we avoid evaluating context dependent
899 // preds if this is > 0.
900
901 if (closureBusy.count(c) > 0) {
902 // avoid infinite recursion for right-recursive rules
903 continue;
904 }
905 closureBusy.insert(c);
906
907 if (_dfa != nullptr && _dfa->isPrecedenceDfa()) {
908 size_t outermostPrecedenceReturn = dynamic_cast<EpsilonTransition *>(t)->outermostPrecedenceReturn();
909 if (outermostPrecedenceReturn == _dfa->atnStartState->ruleIndex) {
910 c->setPrecedenceFilterSuppressed(true);
911 }
912 }
913
914 c->reachesIntoOuterContext++;
915
916 if (!t->isEpsilon()) {
917 // avoid infinite recursion for EOF* and EOF+
918 if (closureBusy.count(c) == 0) {
919 closureBusy.insert(c);
920 } else {
921 continue;
922 }
923 }
924
925 configs->dipsIntoOuterContext = true; // TODO: can remove? only care when we add to set per middle of this method
926 assert(newDepth > INT_MIN);
927
928 newDepth--;
929 #if DEBUG_DFA == 1
930 std::cout << "dips into outer ctx: " << c << std::endl;
931 #endif
932
933 } else if (!t->isEpsilon()) {
934 // avoid infinite recursion for EOF* and EOF+
935 if (closureBusy.count(c) == 0) {
936 closureBusy.insert(c);
937 } else {
938 continue;
939 }
940 }
941
942 if (is<RuleTransition*>(t)) {
943 // latch when newDepth goes negative - once we step out of the entry context we can't return
944 if (newDepth >= 0) {
945 newDepth++;
946 }
947 }
948
949 closureCheckingStopState(c, configs, closureBusy, continueCollecting, fullCtx, newDepth, treatEofAsEpsilon);
950 }
951 }
952 }
953
canDropLoopEntryEdgeInLeftRecursiveRule(ATNConfig * config) const954 bool ParserATNSimulator::canDropLoopEntryEdgeInLeftRecursiveRule(ATNConfig *config) const {
955 if (TURN_OFF_LR_LOOP_ENTRY_BRANCH_OPT)
956 return false;
957
958 ATNState *p = config->state;
959
960 // First check to see if we are in StarLoopEntryState generated during
961 // left-recursion elimination. For efficiency, also check if
962 // the context has an empty stack case. If so, it would mean
963 // global FOLLOW so we can't perform optimization
964 if (p->getStateType() != ATNState::STAR_LOOP_ENTRY ||
965 !((StarLoopEntryState *)p)->isPrecedenceDecision || // Are we the special loop entry/exit state?
966 config->context->isEmpty() || // If SLL wildcard
967 config->context->hasEmptyPath())
968 {
969 return false;
970 }
971
972 // Require all return states to return back to the same rule
973 // that p is in.
974 size_t numCtxs = config->context->size();
975 for (size_t i = 0; i < numCtxs; i++) { // for each stack context
976 ATNState *returnState = atn.states[config->context->getReturnState(i)];
977 if (returnState->ruleIndex != p->ruleIndex)
978 return false;
979 }
980
981 BlockStartState *decisionStartState = (BlockStartState *)p->transitions[0]->target;
982 size_t blockEndStateNum = decisionStartState->endState->stateNumber;
983 BlockEndState *blockEndState = (BlockEndState *)atn.states[blockEndStateNum];
984
985 // Verify that the top of each stack context leads to loop entry/exit
986 // state through epsilon edges and w/o leaving rule.
987 for (size_t i = 0; i < numCtxs; i++) { // for each stack context
988 size_t returnStateNumber = config->context->getReturnState(i);
989 ATNState *returnState = atn.states[returnStateNumber];
990 // All states must have single outgoing epsilon edge.
991 if (returnState->transitions.size() != 1 || !returnState->transitions[0]->isEpsilon())
992 {
993 return false;
994 }
995
996 // Look for prefix op case like 'not expr', (' type ')' expr
997 ATNState *returnStateTarget = returnState->transitions[0]->target;
998 if (returnState->getStateType() == ATNState::BLOCK_END && returnStateTarget == p) {
999 continue;
1000 }
1001
1002 // Look for 'expr op expr' or case where expr's return state is block end
1003 // of (...)* internal block; the block end points to loop back
1004 // which points to p but we don't need to check that
1005 if (returnState == blockEndState) {
1006 continue;
1007 }
1008
1009 // Look for ternary expr ? expr : expr. The return state points at block end,
1010 // which points at loop entry state
1011 if (returnStateTarget == blockEndState) {
1012 continue;
1013 }
1014
1015 // Look for complex prefix 'between expr and expr' case where 2nd expr's
1016 // return state points at block end state of (...)* internal block
1017 if (returnStateTarget->getStateType() == ATNState::BLOCK_END &&
1018 returnStateTarget->transitions.size() == 1 &&
1019 returnStateTarget->transitions[0]->isEpsilon() &&
1020 returnStateTarget->transitions[0]->target == p)
1021 {
1022 continue;
1023 }
1024
1025 // Anything else ain't conforming.
1026 return false;
1027 }
1028
1029 return true;
1030 }
1031
getRuleName(size_t index)1032 std::string ParserATNSimulator::getRuleName(size_t index) {
1033 if (parser != nullptr) {
1034 return parser->getRuleNames()[index];
1035 }
1036 return "<rule " + std::to_string(index) + ">";
1037 }
1038
getEpsilonTarget(Ref<ATNConfig> const & config,Transition * t,bool collectPredicates,bool inContext,bool fullCtx,bool treatEofAsEpsilon)1039 Ref<ATNConfig> ParserATNSimulator::getEpsilonTarget(Ref<ATNConfig> const& config, Transition *t, bool collectPredicates,
1040 bool inContext, bool fullCtx, bool treatEofAsEpsilon) {
1041 switch (t->getSerializationType()) {
1042 case Transition::RULE:
1043 return ruleTransition(config, static_cast<RuleTransition*>(t));
1044
1045 case Transition::PRECEDENCE:
1046 return precedenceTransition(config, static_cast<PrecedencePredicateTransition*>(t), collectPredicates, inContext, fullCtx);
1047
1048 case Transition::PREDICATE:
1049 return predTransition(config, static_cast<PredicateTransition*>(t), collectPredicates, inContext, fullCtx);
1050
1051 case Transition::ACTION:
1052 return actionTransition(config, static_cast<ActionTransition*>(t));
1053
1054 case Transition::EPSILON:
1055 return std::make_shared<ATNConfig>(config, t->target);
1056
1057 case Transition::ATOM:
1058 case Transition::RANGE:
1059 case Transition::SET:
1060 // EOF transitions act like epsilon transitions after the first EOF
1061 // transition is traversed
1062 if (treatEofAsEpsilon) {
1063 if (t->matches(Token::EOF, 0, 1)) {
1064 return std::make_shared<ATNConfig>(config, t->target);
1065 }
1066 }
1067
1068 return nullptr;
1069
1070 default:
1071 return nullptr;
1072 }
1073 }
1074
actionTransition(Ref<ATNConfig> const & config,ActionTransition * t)1075 Ref<ATNConfig> ParserATNSimulator::actionTransition(Ref<ATNConfig> const& config, ActionTransition *t) {
1076 #if DEBUG_DFA == 1
1077 std::cout << "ACTION edge " << t->ruleIndex << ":" << t->actionIndex << std::endl;
1078 #endif
1079
1080 return std::make_shared<ATNConfig>(config, t->target);
1081 }
1082
precedenceTransition(Ref<ATNConfig> const & config,PrecedencePredicateTransition * pt,bool collectPredicates,bool inContext,bool fullCtx)1083 Ref<ATNConfig> ParserATNSimulator::precedenceTransition(Ref<ATNConfig> const& config, PrecedencePredicateTransition *pt,
1084 bool collectPredicates, bool inContext, bool fullCtx) {
1085 #if DEBUG_DFA == 1
1086 std::cout << "PRED (collectPredicates=" << collectPredicates << ") " << pt->precedence << ">=_p" << ", ctx dependent=true" << std::endl;
1087 if (parser != nullptr) {
1088 std::cout << "context surrounding pred is " << Arrays::listToString(parser->getRuleInvocationStack(), ", ") << std::endl;
1089 }
1090 #endif
1091
1092 Ref<ATNConfig> c;
1093 if (collectPredicates && inContext) {
1094 Ref<SemanticContext::PrecedencePredicate> predicate = pt->getPredicate();
1095
1096 if (fullCtx) {
1097 // In full context mode, we can evaluate predicates on-the-fly
1098 // during closure, which dramatically reduces the size of
1099 // the config sets. It also obviates the need to test predicates
1100 // later during conflict resolution.
1101 size_t currentPosition = _input->index();
1102 _input->seek(_startIndex);
1103 bool predSucceeds = evalSemanticContext(pt->getPredicate(), _outerContext, config->alt, fullCtx);
1104 _input->seek(currentPosition);
1105 if (predSucceeds) {
1106 c = std::make_shared<ATNConfig>(config, pt->target); // no pred context
1107 }
1108 } else {
1109 Ref<SemanticContext> newSemCtx = SemanticContext::And(config->semanticContext, predicate);
1110 c = std::make_shared<ATNConfig>(config, pt->target, newSemCtx);
1111 }
1112 } else {
1113 c = std::make_shared<ATNConfig>(config, pt->target);
1114 }
1115
1116 #if DEBUG_DFA == 1
1117 std::cout << "config from pred transition=" << c << std::endl;
1118 #endif
1119
1120 return c;
1121 }
1122
predTransition(Ref<ATNConfig> const & config,PredicateTransition * pt,bool collectPredicates,bool inContext,bool fullCtx)1123 Ref<ATNConfig> ParserATNSimulator::predTransition(Ref<ATNConfig> const& config, PredicateTransition *pt,
1124 bool collectPredicates, bool inContext, bool fullCtx) {
1125 #if DEBUG_DFA == 1
1126 std::cout << "PRED (collectPredicates=" << collectPredicates << ") " << pt->ruleIndex << ":" << pt->predIndex << ", ctx dependent=" << pt->isCtxDependent << std::endl;
1127 if (parser != nullptr) {
1128 std::cout << "context surrounding pred is " << Arrays::listToString(parser->getRuleInvocationStack(), ", ") << std::endl;
1129 }
1130 #endif
1131
1132 Ref<ATNConfig> c = nullptr;
1133 if (collectPredicates && (!pt->isCtxDependent || (pt->isCtxDependent && inContext))) {
1134 Ref<SemanticContext::Predicate> predicate = pt->getPredicate();
1135 if (fullCtx) {
1136 // In full context mode, we can evaluate predicates on-the-fly
1137 // during closure, which dramatically reduces the size of
1138 // the config sets. It also obviates the need to test predicates
1139 // later during conflict resolution.
1140 size_t currentPosition = _input->index();
1141 _input->seek(_startIndex);
1142 bool predSucceeds = evalSemanticContext(pt->getPredicate(), _outerContext, config->alt, fullCtx);
1143 _input->seek(currentPosition);
1144 if (predSucceeds) {
1145 c = std::make_shared<ATNConfig>(config, pt->target); // no pred context
1146 }
1147 } else {
1148 Ref<SemanticContext> newSemCtx = SemanticContext::And(config->semanticContext, predicate);
1149 c = std::make_shared<ATNConfig>(config, pt->target, newSemCtx);
1150 }
1151 } else {
1152 c = std::make_shared<ATNConfig>(config, pt->target);
1153 }
1154
1155 #if DEBUG_DFA == 1
1156 std::cout << "config from pred transition=" << c << std::endl;
1157 #endif
1158
1159 return c;
1160 }
1161
ruleTransition(Ref<ATNConfig> const & config,RuleTransition * t)1162 Ref<ATNConfig> ParserATNSimulator::ruleTransition(Ref<ATNConfig> const& config, RuleTransition *t) {
1163 #if DEBUG_DFA == 1
1164 std::cout << "CALL rule " << getRuleName(t->target->ruleIndex) << ", ctx=" << config->context << std::endl;
1165 #endif
1166
1167 atn::ATNState *returnState = t->followState;
1168 Ref<PredictionContext> newContext = SingletonPredictionContext::create(config->context, returnState->stateNumber);
1169 return std::make_shared<ATNConfig>(config, t->target, newContext);
1170 }
1171
getConflictingAlts(ATNConfigSet * configs)1172 BitSet ParserATNSimulator::getConflictingAlts(ATNConfigSet *configs) {
1173 std::vector<BitSet> altsets = PredictionModeClass::getConflictingAltSubsets(configs);
1174 return PredictionModeClass::getAlts(altsets);
1175 }
1176
getConflictingAltsOrUniqueAlt(ATNConfigSet * configs)1177 BitSet ParserATNSimulator::getConflictingAltsOrUniqueAlt(ATNConfigSet *configs) {
1178 BitSet conflictingAlts;
1179 if (configs->uniqueAlt != ATN::INVALID_ALT_NUMBER) {
1180 conflictingAlts.set(configs->uniqueAlt);
1181 } else {
1182 conflictingAlts = configs->conflictingAlts;
1183 }
1184 return conflictingAlts;
1185 }
1186
getTokenName(size_t t)1187 std::string ParserATNSimulator::getTokenName(size_t t) {
1188 if (t == Token::EOF) {
1189 return "EOF";
1190 }
1191
1192 const dfa::Vocabulary &vocabulary = parser != nullptr ? parser->getVocabulary() : dfa::Vocabulary::EMPTY_VOCABULARY;
1193 std::string displayName = vocabulary.getDisplayName(t);
1194 if (displayName == std::to_string(t)) {
1195 return displayName;
1196 }
1197
1198 return displayName + "<" + std::to_string(t) + ">";
1199 }
1200
getLookaheadName(TokenStream * input)1201 std::string ParserATNSimulator::getLookaheadName(TokenStream *input) {
1202 return getTokenName(input->LA(1));
1203 }
1204
dumpDeadEndConfigs(NoViableAltException & nvae)1205 void ParserATNSimulator::dumpDeadEndConfigs(NoViableAltException &nvae) {
1206 std::cerr << "dead end configs: ";
1207 for (auto c : nvae.getDeadEndConfigs()->configs) {
1208 std::string trans = "no edges";
1209 if (c->state->transitions.size() > 0) {
1210 Transition *t = c->state->transitions[0];
1211 if (is<AtomTransition*>(t)) {
1212 AtomTransition *at = static_cast<AtomTransition*>(t);
1213 trans = "Atom " + getTokenName(at->_label);
1214 } else if (is<SetTransition*>(t)) {
1215 SetTransition *st = static_cast<SetTransition*>(t);
1216 bool is_not = is<NotSetTransition*>(st);
1217 trans = (is_not ? "~" : "");
1218 trans += "Set ";
1219 trans += st->set.toString();
1220 }
1221 }
1222 std::cerr << c->toString(true) + ":" + trans;
1223 }
1224 }
1225
noViableAlt(TokenStream * input,ParserRuleContext * outerContext,ATNConfigSet * configs,size_t startIndex,bool deleteConfigs)1226 NoViableAltException ParserATNSimulator::noViableAlt(TokenStream *input, ParserRuleContext *outerContext,
1227 ATNConfigSet *configs, size_t startIndex, bool deleteConfigs) {
1228 return NoViableAltException(parser, input, input->get(startIndex), input->LT(1), configs, outerContext, deleteConfigs);
1229 }
1230
getUniqueAlt(ATNConfigSet * configs)1231 size_t ParserATNSimulator::getUniqueAlt(ATNConfigSet *configs) {
1232 size_t alt = ATN::INVALID_ALT_NUMBER;
1233 for (auto &c : configs->configs) {
1234 if (alt == ATN::INVALID_ALT_NUMBER) {
1235 alt = c->alt; // found first alt
1236 } else if (c->alt != alt) {
1237 return ATN::INVALID_ALT_NUMBER;
1238 }
1239 }
1240 return alt;
1241 }
1242
addDFAEdge(dfa::DFA & dfa,dfa::DFAState * from,ssize_t t,dfa::DFAState * to)1243 dfa::DFAState *ParserATNSimulator::addDFAEdge(dfa::DFA &dfa, dfa::DFAState *from, ssize_t t, dfa::DFAState *to) {
1244 #if DEBUG_DFA == 1
1245 std::cout << "EDGE " << from << " -> " << to << " upon " << getTokenName(t) << std::endl;
1246 #endif
1247
1248 if (to == nullptr) {
1249 return nullptr;
1250 }
1251
1252 _stateLock.writeLock();
1253 to = addDFAState(dfa, to); // used existing if possible not incoming
1254 _stateLock.writeUnlock();
1255 if (from == nullptr || t > (int)atn.maxTokenType) {
1256 return to;
1257 }
1258
1259 {
1260 _edgeLock.writeLock();
1261 from->edges[t] = to; // connect
1262 _edgeLock.writeUnlock();
1263 }
1264
1265 #if DEBUG_DFA == 1
1266 std::string dfaText;
1267 if (parser != nullptr) {
1268 dfaText = dfa.toString(parser->getVocabulary());
1269 } else {
1270 dfaText = dfa.toString(dfa::Vocabulary::EMPTY_VOCABULARY);
1271 }
1272 std::cout << "DFA=\n" << dfaText << std::endl;
1273 #endif
1274
1275 return to;
1276 }
1277
addDFAState(dfa::DFA & dfa,dfa::DFAState * D)1278 dfa::DFAState *ParserATNSimulator::addDFAState(dfa::DFA &dfa, dfa::DFAState *D) {
1279 if (D == ERROR.get()) {
1280 return D;
1281 }
1282
1283 auto existing = dfa.states.find(D);
1284 if (existing != dfa.states.end()) {
1285 return *existing;
1286 }
1287
1288 D->stateNumber = (int)dfa.states.size();
1289 if (!D->configs->isReadonly()) {
1290 D->configs->optimizeConfigs(this);
1291 D->configs->setReadonly(true);
1292 }
1293
1294 dfa.states.insert(D);
1295
1296 #if DEBUG_DFA == 1
1297 std::cout << "adding new DFA state: " << D << std::endl;
1298 #endif
1299
1300 return D;
1301 }
1302
reportAttemptingFullContext(dfa::DFA & dfa,const antlrcpp::BitSet & conflictingAlts,ATNConfigSet * configs,size_t startIndex,size_t stopIndex)1303 void ParserATNSimulator::reportAttemptingFullContext(dfa::DFA &dfa, const antlrcpp::BitSet &conflictingAlts,
1304 ATNConfigSet *configs, size_t startIndex, size_t stopIndex) {
1305 #if DEBUG_DFA == 1 || RETRY_DEBUG == 1
1306 misc::Interval interval = misc::Interval((int)startIndex, (int)stopIndex);
1307 std::cout << "reportAttemptingFullContext decision=" << dfa.decision << ":" << configs << ", input=" << parser->getTokenStream()->getText(interval) << std::endl;
1308 #endif
1309
1310 if (parser != nullptr) {
1311 parser->getErrorListenerDispatch().reportAttemptingFullContext(parser, dfa, startIndex, stopIndex, conflictingAlts, configs);
1312 }
1313 }
1314
reportContextSensitivity(dfa::DFA & dfa,size_t prediction,ATNConfigSet * configs,size_t startIndex,size_t stopIndex)1315 void ParserATNSimulator::reportContextSensitivity(dfa::DFA &dfa, size_t prediction, ATNConfigSet *configs,
1316 size_t startIndex, size_t stopIndex) {
1317 #if DEBUG_DFA == 1 || RETRY_DEBUG == 1
1318 misc::Interval interval = misc::Interval(startIndex, stopIndex);
1319 std::cout << "reportContextSensitivity decision=" << dfa.decision << ":" << configs << ", input=" << parser->getTokenStream()->getText(interval) << std::endl;
1320 #endif
1321
1322 if (parser != nullptr) {
1323 parser->getErrorListenerDispatch().reportContextSensitivity(parser, dfa, startIndex, stopIndex, prediction, configs);
1324 }
1325 }
1326
reportAmbiguity(dfa::DFA & dfa,dfa::DFAState *,size_t startIndex,size_t stopIndex,bool exact,const antlrcpp::BitSet & ambigAlts,ATNConfigSet * configs)1327 void ParserATNSimulator::reportAmbiguity(dfa::DFA &dfa, dfa::DFAState * /*D*/, size_t startIndex, size_t stopIndex,
1328 bool exact, const antlrcpp::BitSet &ambigAlts, ATNConfigSet *configs) {
1329 #if DEBUG_DFA == 1 || RETRY_DEBUG == 1
1330 misc::Interval interval = misc::Interval((int)startIndex, (int)stopIndex);
1331 std::cout << "reportAmbiguity " << ambigAlts << ":" << configs << ", input=" << parser->getTokenStream()->getText(interval) << std::endl;
1332 #endif
1333
1334 if (parser != nullptr) {
1335 parser->getErrorListenerDispatch().reportAmbiguity(parser, dfa, startIndex, stopIndex, exact, ambigAlts, configs);
1336 }
1337 }
1338
setPredictionMode(PredictionMode newMode)1339 void ParserATNSimulator::setPredictionMode(PredictionMode newMode) {
1340 _mode = newMode;
1341 }
1342
getPredictionMode()1343 atn::PredictionMode ParserATNSimulator::getPredictionMode() {
1344 return _mode;
1345 }
1346
getParser()1347 Parser* ParserATNSimulator::getParser() {
1348 return parser;
1349 }
1350
1351 #pragma warning (disable:4996) // 'getenv': This function or variable may be unsafe. Consider using _dupenv_s instead.
1352
getLrLoopSetting()1353 bool ParserATNSimulator::getLrLoopSetting() {
1354 char *var = std::getenv("TURN_OFF_LR_LOOP_ENTRY_BRANCH_OPT");
1355 if (var == nullptr)
1356 return false;
1357 std::string value(var);
1358 return value == "true" || value == "1";
1359 }
1360
1361 #pragma warning (default:4996)
1362
InitializeInstanceFields()1363 void ParserATNSimulator::InitializeInstanceFields() {
1364 _mode = PredictionMode::LL;
1365 _startIndex = 0;
1366 }
1367