gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/atn/ATNConfigSet.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/PredictionContext.h"
   7 #include "atn/ATNConfig.h"
   8 #include "atn/ATNSimulator.h"
   9 #include "Exceptions.h"
  10 #include "atn/SemanticContext.h"
  11 #include "support/Arrays.h"
  12
  13 #include "atn/ATNConfigSet.h"
  14
  15 using namespace antlr4::atn;
  16 using namespace antlrcpp;
  17
  18 ATNConfigSet::ATNConfigSet(bool fullCtx) : fullCtx(fullCtx) {
  19   InitializeInstanceFields();
  20 }
  21
  22 ATNConfigSet::ATNConfigSet(const Ref<ATNConfigSet> &old) : ATNConfigSet(old->fullCtx) {
  23   addAll(old);
  24   uniqueAlt = old->uniqueAlt;
  25   conflictingAlts = old->conflictingAlts;
  26   hasSemanticContext = old->hasSemanticContext;
  27   dipsIntoOuterContext = old->dipsIntoOuterContext;
  28 }
  29
  30 ATNConfigSet::~ATNConfigSet() {
  31 }
  32
  33 bool ATNConfigSet::add(const Ref<ATNConfig> &config) {
  34   return add(config, nullptr);
  35 }
  36
  37 bool ATNConfigSet::add(const Ref<ATNConfig> &config, PredictionContextMergeCache *mergeCache) {
  38   if (_readonly) {
  39     throw IllegalStateException("This set is readonly");
  40   }
  41   if (config->semanticContext != SemanticContext::NONE) {
  42     hasSemanticContext = true;
  43   }
  44   if (config->getOuterContextDepth() > 0) {
  45     dipsIntoOuterContext = true;
  46   }
  47
  48   size_t hash = getHash(config.get());
  49   ATNConfig *existing = _configLookup[hash];
  50   if (existing == nullptr) {
  51     _configLookup[hash] = config.get();
  52     _cachedHashCode = 0;
  53     configs.push_back(config); // track order here
  54
  55     return true;
  56   }
  57
  58   // a previous (s,i,pi,_), merge with it and save result
  59   bool rootIsWildcard = !fullCtx;
  60   Ref<PredictionContext> merged = PredictionContext::merge(existing->context, config->context, rootIsWildcard, mergeCache);
  61   // no need to check for existing.context, config.context in cache
  62   // since only way to create new graphs is "call rule" and here. We
  63   // cache at both places.
  64   existing->reachesIntoOuterContext = std::max(existing->reachesIntoOuterContext, config->reachesIntoOuterContext);
  65
  66   // make sure to preserve the precedence filter suppression during the merge
  67   if (config->isPrecedenceFilterSuppressed()) {
  68     existing->setPrecedenceFilterSuppressed(true);
  69   }
  70
  71   existing->context = merged; // replace context; no need to alt mapping
  72
  73   return true;
  74 }
  75
  76 bool ATNConfigSet::addAll(const Ref<ATNConfigSet> &other) {
  77   for (auto &c : other->configs) {
  78     add(c);
  79   }
  80   return false;
  81 }
  82
  83 std::vector<ATNState*> ATNConfigSet::getStates() {
  84   std::vector<ATNState*> states;
  85   for (auto c : configs) {
  86     states.push_back(c->state);
  87   }
  88   return states;
  89 }
  90
  91 /**
  92  * Gets the complete set of represented alternatives for the configuration
  93  * set.
  94  *
  95  * @return the set of represented alternatives in this configuration set
  96  *
  97  * @since 4.3
  98  */
  99
 100 BitSet ATNConfigSet::getAlts() {
 101   BitSet alts;
 102   for (ATNConfig config : configs) {
 103     alts.set(config.alt);
 104   }
 105   return alts;
 106 }
 107
 108 std::vector<Ref<SemanticContext>> ATNConfigSet::getPredicates() {
 109   std::vector<Ref<SemanticContext>> preds;
 110   for (auto c : configs) {
 111     if (c->semanticContext != SemanticContext::NONE) {
 112       preds.push_back(c->semanticContext);
 113     }
 114   }
 115   return preds;
 116 }
 117
 118 Ref<ATNConfig> ATNConfigSet::get(size_t i) const {
 119   return configs[i];
 120 }
 121
 122 void ATNConfigSet::optimizeConfigs(ATNSimulator *interpreter) {
 123   if (_readonly) {
 124     throw IllegalStateException("This set is readonly");
 125   }
 126   if (_configLookup.empty())
 127     return;
 128
 129   for (auto &config : configs) {
 130     config->context = interpreter->getCachedContext(config->context);
 131   }
 132 }
 133
 134 bool ATNConfigSet::operator == (const ATNConfigSet &other) {
 135   if (&other == this) {
 136     return true;
 137   }
 138
 139   if (configs.size() != other.configs.size())
 140     return false;
 141
 142   if (fullCtx != other.fullCtx || uniqueAlt != other.uniqueAlt ||
 143       conflictingAlts != other.conflictingAlts || hasSemanticContext != other.hasSemanticContext ||
 144       dipsIntoOuterContext != other.dipsIntoOuterContext) // includes stack context
 145     return false;
 146
 147   return Arrays::equals(configs, other.configs);
 148 }
 149
 150 size_t ATNConfigSet::hashCode() {
 151   if (!isReadonly() || _cachedHashCode == 0) {
 152     _cachedHashCode = 1;
 153     for (auto &i : configs) {
 154       _cachedHashCode = 31 * _cachedHashCode + i->hashCode(); // Same as Java's list hashCode impl.
 155     }
 156   }
 157
 158   return _cachedHashCode;
 159 }
 160
 161 size_t ATNConfigSet::size() {
 162   return configs.size();
 163 }
 164
 165 bool ATNConfigSet::isEmpty() {
 166   return configs.empty();
 167 }
 168
 169 void ATNConfigSet::clear() {
 170   if (_readonly) {
 171     throw IllegalStateException("This set is readonly");
 172   }
 173   configs.clear();
 174   _cachedHashCode = 0;
 175   _configLookup.clear();
 176 }
 177
 178 bool ATNConfigSet::isReadonly() {
 179   return _readonly;
 180 }
 181
 182 void ATNConfigSet::setReadonly(bool readonly) {
 183   _readonly = readonly;
 184   _configLookup.clear();
 185 }
 186
 187 std::string ATNConfigSet::toString() {
 188   std::stringstream ss;
 189   ss << "[";
 190   for (size_t i = 0; i < configs.size(); i++) {
 191     ss << configs[i]->toString();
 192   }
 193   ss << "]";
 194
 195   if (hasSemanticContext) {
 196     ss << ",hasSemanticContext = " <<  hasSemanticContext;
 197   }
 198   if (uniqueAlt != ATN::INVALID_ALT_NUMBER) {
 199     ss << ",uniqueAlt = " << uniqueAlt;
 200   }
 201
 202   if (conflictingAlts.size() > 0) {
 203     ss << ",conflictingAlts = ";
 204     ss << conflictingAlts.toString();
 205   }
 206
 207   if (dipsIntoOuterContext) {
 208     ss << ", dipsIntoOuterContext";
 209   }
 210   return ss.str();
 211 }
 212
 213 size_t ATNConfigSet::getHash(ATNConfig *c) {
 214   size_t hashCode = 7;
 215   hashCode = 31 * hashCode + c->state->stateNumber;
 216   hashCode = 31 * hashCode + c->alt;
 217   hashCode = 31 * hashCode + c->semanticContext->hashCode();
 218   return hashCode;
 219 }
 220
 221 void ATNConfigSet::InitializeInstanceFields() {
 222   uniqueAlt = 0;
 223   hasSemanticContext = false;
 224   dipsIntoOuterContext = false;
 225
 226   _readonly = false;
 227   _cachedHashCode = 0;
 228 }