gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/atn/PredictionMode.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 "atn/RuleStopState.h"
   7 #include "atn/ATNConfigSet.h"
   8 #include "atn/ATNConfig.h"
   9 #include "misc/MurmurHash.h"
  10 #include "SemanticContext.h"
  11
  12 #include "PredictionMode.h"
  13
  14 using namespace antlr4;
  15 using namespace antlr4::atn;
  16 using namespace antlrcpp;
  17
  18 struct AltAndContextConfigHasher
  19 {
  20   /**
  21    * The hash code is only a function of the {@link ATNState#stateNumber}
  22    * and {@link ATNConfig#context}.
  23    */
  24   size_t operator () (ATNConfig *o) const {
  25     size_t hashCode = misc::MurmurHash::initialize(7);
  26     hashCode = misc::MurmurHash::update(hashCode, o->state->stateNumber);
  27     hashCode = misc::MurmurHash::update(hashCode, o->context);
  28     return misc::MurmurHash::finish(hashCode, 2);
  29   }
  30 };
  31
  32 struct AltAndContextConfigComparer {
  33   bool operator()(ATNConfig *a, ATNConfig *b) const
  34   {
  35     if (a == b) {
  36       return true;
  37     }
  38     return a->state->stateNumber == b->state->stateNumber && *a->context == *b->context;
  39   }
  40 };
  41
  42 bool PredictionModeClass::hasSLLConflictTerminatingPrediction(PredictionMode mode, ATNConfigSet *configs) {
  43   /* Configs in rule stop states indicate reaching the end of the decision
  44    * rule (local context) or end of start rule (full context). If all
  45    * configs meet this condition, then none of the configurations is able
  46    * to match additional input so we terminate prediction.
  47    */
  48   if (allConfigsInRuleStopStates(configs)) {
  49     return true;
  50   }
  51
  52   bool heuristic;
  53
  54   // Pure SLL mode parsing or SLL+LL if:
  55   // Don't bother with combining configs from different semantic
  56   // contexts if we can fail over to full LL; costs more time
  57   // since we'll often fail over anyway.
  58   if (mode == PredictionMode::SLL || !configs->hasSemanticContext) {
  59     std::vector<antlrcpp::BitSet> altsets = getConflictingAltSubsets(configs);
  60     heuristic = hasConflictingAltSet(altsets) && !hasStateAssociatedWithOneAlt(configs);
  61   } else {
  62     // dup configs, tossing out semantic predicates
  63     ATNConfigSet dup(true);
  64     for (auto &config : configs->configs) {
  65       Ref<ATNConfig> c = std::make_shared<ATNConfig>(config, SemanticContext::NONE);
  66       dup.add(c);
  67     }
  68     std::vector<antlrcpp::BitSet> altsets = getConflictingAltSubsets(&dup);
  69     heuristic = hasConflictingAltSet(altsets) && !hasStateAssociatedWithOneAlt(&dup);
  70   }
  71
  72   return heuristic;
  73 }
  74
  75 bool PredictionModeClass::hasConfigInRuleStopState(ATNConfigSet *configs) {
  76   for (auto &c : configs->configs) {
  77     if (is<RuleStopState *>(c->state)) {
  78       return true;
  79     }
  80   }
  81
  82   return false;
  83 }
  84
  85 bool PredictionModeClass::allConfigsInRuleStopStates(ATNConfigSet *configs) {
  86   for (auto &config : configs->configs) {
  87     if (!is<RuleStopState*>(config->state)) {
  88       return false;
  89     }
  90   }
  91
  92   return true;
  93 }
  94
  95 size_t PredictionModeClass::resolvesToJustOneViableAlt(const std::vector<antlrcpp::BitSet>& altsets) {
  96   return getSingleViableAlt(altsets);
  97 }
  98
  99 bool PredictionModeClass::allSubsetsConflict(const std::vector<antlrcpp::BitSet>& altsets) {
 100   return !hasNonConflictingAltSet(altsets);
 101 }
 102
 103 bool PredictionModeClass::hasNonConflictingAltSet(const std::vector<antlrcpp::BitSet>& altsets) {
 104   for (antlrcpp::BitSet alts : altsets) {
 105     if (alts.count() == 1) {
 106       return true;
 107     }
 108   }
 109   return false;
 110 }
 111
 112 bool PredictionModeClass::hasConflictingAltSet(const std::vector<antlrcpp::BitSet>& altsets) {
 113   for (antlrcpp::BitSet alts : altsets) {
 114     if (alts.count() > 1) {
 115       return true;
 116     }
 117   }
 118   return false;
 119 }
 120
 121 bool PredictionModeClass::allSubsetsEqual(const std::vector<antlrcpp::BitSet>& altsets) {
 122   if (altsets.empty()) {
 123     return true;
 124   }
 125
 126   const antlrcpp::BitSet& first = *altsets.begin();
 127   for (const antlrcpp::BitSet& alts : altsets) {
 128     if (alts != first) {
 129       return false;
 130     }
 131   }
 132   return true;
 133 }
 134
 135 size_t PredictionModeClass::getUniqueAlt(const std::vector<antlrcpp::BitSet>& altsets) {
 136   antlrcpp::BitSet all = getAlts(altsets);
 137   if (all.count() == 1) {
 138     return all.nextSetBit(0);
 139   }
 140   return ATN::INVALID_ALT_NUMBER;
 141 }
 142
 143 antlrcpp::BitSet PredictionModeClass::getAlts(const std::vector<antlrcpp::BitSet>& altsets) {
 144   antlrcpp::BitSet all;
 145   for (antlrcpp::BitSet alts : altsets) {
 146     all |= alts;
 147   }
 148
 149   return all;
 150 }
 151
 152 antlrcpp::BitSet PredictionModeClass::getAlts(ATNConfigSet *configs) {
 153   antlrcpp::BitSet alts;
 154   for (auto &config : configs->configs) {
 155     alts.set(config->alt);
 156   }
 157   return alts;
 158 }
 159
 160 std::vector<antlrcpp::BitSet> PredictionModeClass::getConflictingAltSubsets(ATNConfigSet *configs) {
 161   std::unordered_map<ATNConfig *, antlrcpp::BitSet, AltAndContextConfigHasher, AltAndContextConfigComparer> configToAlts;
 162   for (auto &config : configs->configs) {
 163     configToAlts[config.get()].set(config->alt);
 164   }
 165   std::vector<antlrcpp::BitSet> values;
 166   for (auto it : configToAlts) {
 167     values.push_back(it.second);
 168   }
 169   return values;
 170 }
 171
 172 std::map<ATNState*, antlrcpp::BitSet> PredictionModeClass::getStateToAltMap(ATNConfigSet *configs) {
 173   std::map<ATNState*, antlrcpp::BitSet> m;
 174   for (auto &c : configs->configs) {
 175     m[c->state].set(c->alt);
 176   }
 177   return m;
 178 }
 179
 180 bool PredictionModeClass::hasStateAssociatedWithOneAlt(ATNConfigSet *configs) {
 181   std::map<ATNState*, antlrcpp::BitSet> x = getStateToAltMap(configs);
 182   for (std::map<ATNState*, antlrcpp::BitSet>::iterator it = x.begin(); it != x.end(); it++){
 183     if (it->second.count() == 1) return true;
 184   }
 185   return false;
 186 }
 187
 188 size_t PredictionModeClass::getSingleViableAlt(const std::vector<antlrcpp::BitSet>& altsets) {
 189   antlrcpp::BitSet viableAlts;
 190   for (antlrcpp::BitSet alts : altsets) {
 191     size_t minAlt = alts.nextSetBit(0);
 192
 193     viableAlts.set(minAlt);
 194     if (viableAlts.count() > 1)  // more than 1 viable alt
 195     {
 196       return ATN::INVALID_ALT_NUMBER;
 197     }
 198   }
 199
 200   return viableAlts.nextSetBit(0);
 201 }