gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/atn/ParserATNSimulator.cpp

   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
  49 ParserATNSimulator::ParserATNSimulator(const ATN &atn, std::vector<dfa::DFA> &decisionToDFA,
  50                                        PredictionContextCache &sharedContextCache)
  51 : ParserATNSimulator(nullptr, atn, decisionToDFA, sharedContextCache) {
  52 }
  53
  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
  60 void ParserATNSimulator::reset() {
  61 }
  62
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 807 bool ParserATNSimulator::evalSemanticContext(Ref<SemanticContext> const& pred, ParserRuleContext *parserCallStack,
 808                                              size_t /*alt*/, bool /*fullCtx*/) {
 809   return pred->eval(parser, parserCallStack);
 810 }
 811
 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
 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
 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
 954 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
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
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
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
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
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
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
1172 BitSet ParserATNSimulator::getConflictingAlts(ATNConfigSet *configs) {
1173   std::vector<BitSet> altsets = PredictionModeClass::getConflictingAltSubsets(configs);
1174   return PredictionModeClass::getAlts(altsets);
1175 }
1176
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
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
1201 std::string ParserATNSimulator::getLookaheadName(TokenStream *input) {
1202   return getTokenName(input->LA(1));
1203 }
1204
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
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
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
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
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
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
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
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
1339 void ParserATNSimulator::setPredictionMode(PredictionMode newMode) {
1340   _mode = newMode;
1341 }
1342
1343 atn::PredictionMode ParserATNSimulator::getPredictionMode() {
1344   return _mode;
1345 }
1346
1347 Parser* ParserATNSimulator::getParser() {
1348   return parser;
1349 }
1350
1351 #ifdef _MSC_VER
1352 #pragma warning (disable:4996) // 'getenv': This function or variable may be unsafe. Consider using _dupenv_s instead.
1353 #endif
1354
1355 bool ParserATNSimulator::getLrLoopSetting() {
1356   char *var = std::getenv("TURN_OFF_LR_LOOP_ENTRY_BRANCH_OPT");
1357   if (var == nullptr)
1358     return false;
1359   std::string value(var);
1360   return value == "true" || value == "1";
1361 }
1362
1363 #ifdef _MSC_VER
1364 #pragma warning (default:4996)
1365 #endif
1366
1367 void ParserATNSimulator::InitializeInstanceFields() {
1368   _mode = PredictionMode::LL;
1369   _startIndex = 0;
1370 }