gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/atn/SemanticContext.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 "misc/MurmurHash.h"
   7 #include "support/CPPUtils.h"
   8 #include "support/Arrays.h"
   9
  10 #include "SemanticContext.h"
  11
  12 using namespace antlr4;
  13 using namespace antlr4::atn;
  14 using namespace antlrcpp;
  15
  16 //------------------ Predicate -----------------------------------------------------------------------------------------
  17
  18 SemanticContext::Predicate::Predicate() : Predicate(INVALID_INDEX, INVALID_INDEX, false) {
  19 }
  20
  21 SemanticContext::Predicate::Predicate(size_t ruleIndex, size_t predIndex, bool isCtxDependent)
  22 : ruleIndex(ruleIndex), predIndex(predIndex), isCtxDependent(isCtxDependent) {
  23 }
  24
  25
  26 bool SemanticContext::Predicate::eval(Recognizer *parser, RuleContext *parserCallStack) {
  27   RuleContext *localctx = nullptr;
  28   if (isCtxDependent)
  29     localctx = parserCallStack;
  30   return parser->sempred(localctx, ruleIndex, predIndex);
  31 }
  32
  33 size_t SemanticContext::Predicate::hashCode() const {
  34   size_t hashCode = misc::MurmurHash::initialize();
  35   hashCode = misc::MurmurHash::update(hashCode, ruleIndex);
  36   hashCode = misc::MurmurHash::update(hashCode, predIndex);
  37   hashCode = misc::MurmurHash::update(hashCode, isCtxDependent ? 1 : 0);
  38   hashCode = misc::MurmurHash::finish(hashCode, 3);
  39   return hashCode;
  40 }
  41
  42 bool SemanticContext::Predicate::operator == (const SemanticContext &other) const {
  43   if (this == &other)
  44     return true;
  45
  46   const Predicate *p = dynamic_cast<const Predicate*>(&other);
  47   if (p == nullptr)
  48     return false;
  49
  50   return ruleIndex == p->ruleIndex && predIndex == p->predIndex && isCtxDependent == p->isCtxDependent;
  51 }
  52
  53 std::string SemanticContext::Predicate::toString() const {
  54   return std::string("{") + std::to_string(ruleIndex) + std::string(":") + std::to_string(predIndex) + std::string("}?");
  55 }
  56
  57 //------------------ PrecedencePredicate -------------------------------------------------------------------------------
  58
  59 SemanticContext::PrecedencePredicate::PrecedencePredicate() : precedence(0) {
  60 }
  61
  62 SemanticContext::PrecedencePredicate::PrecedencePredicate(int precedence) : precedence(precedence) {
  63 }
  64
  65 bool SemanticContext::PrecedencePredicate::eval(Recognizer *parser, RuleContext *parserCallStack) {
  66   return parser->precpred(parserCallStack, precedence);
  67 }
  68
  69 Ref<SemanticContext> SemanticContext::PrecedencePredicate::evalPrecedence(Recognizer *parser,
  70   RuleContext *parserCallStack) {
  71   if (parser->precpred(parserCallStack, precedence)) {
  72     return SemanticContext::NONE;
  73   }
  74   else {
  75     return nullptr;
  76   }
  77 }
  78
  79 int SemanticContext::PrecedencePredicate::compareTo(PrecedencePredicate *o) {
  80   return precedence - o->precedence;
  81 }
  82
  83 size_t SemanticContext::PrecedencePredicate::hashCode() const {
  84   size_t hashCode = 1;
  85   hashCode = 31 * hashCode + static_cast<size_t>(precedence);
  86   return hashCode;
  87 }
  88
  89 bool SemanticContext::PrecedencePredicate::operator == (const SemanticContext &other) const {
  90   if (this == &other)
  91     return true;
  92
  93   const PrecedencePredicate *predicate = dynamic_cast<const PrecedencePredicate *>(&other);
  94   if (predicate == nullptr)
  95     return false;
  96
  97   return precedence == predicate->precedence;
  98 }
  99
 100 std::string SemanticContext::PrecedencePredicate::toString() const {
 101   return "{" + std::to_string(precedence) + ">=prec}?";
 102 }
 103
 104 //------------------ AND -----------------------------------------------------------------------------------------------
 105
 106 SemanticContext::AND::AND(Ref<SemanticContext> const& a, Ref<SemanticContext> const& b) {
 107   Set operands;
 108
 109   if (is<AND>(a)) {
 110     for (auto operand : std::dynamic_pointer_cast<AND>(a)->opnds) {
 111       operands.insert(operand);
 112     }
 113   } else {
 114     operands.insert(a);
 115   }
 116
 117   if (is<AND>(b)) {
 118     for (auto operand : std::dynamic_pointer_cast<AND>(b)->opnds) {
 119       operands.insert(operand);
 120     }
 121   } else {
 122     operands.insert(b);
 123   }
 124
 125   std::vector<Ref<PrecedencePredicate>> precedencePredicates = filterPrecedencePredicates(operands);
 126
 127   if (!precedencePredicates.empty()) {
 128     // interested in the transition with the lowest precedence
 129     auto predicate = [](Ref<PrecedencePredicate> const& a, Ref<PrecedencePredicate> const& b) {
 130       return a->precedence < b->precedence;
 131     };
 132
 133     auto reduced = std::min_element(precedencePredicates.begin(), precedencePredicates.end(), predicate);
 134     operands.insert(*reduced);
 135   }
 136
 137   std::copy(operands.begin(), operands.end(), std::back_inserter(opnds));
 138 }
 139
 140 std::vector<Ref<SemanticContext>> SemanticContext::AND::getOperands() const {
 141   return opnds;
 142 }
 143
 144 bool SemanticContext::AND::operator == (const SemanticContext &other) const {
 145   if (this == &other)
 146     return true;
 147
 148   const AND *context = dynamic_cast<const AND *>(&other);
 149   if (context == nullptr)
 150     return false;
 151
 152   return Arrays::equals(opnds, context->opnds);
 153 }
 154
 155 size_t SemanticContext::AND::hashCode() const {
 156   return misc::MurmurHash::hashCode(opnds, typeid(AND).hash_code());
 157 }
 158
 159 bool SemanticContext::AND::eval(Recognizer *parser, RuleContext *parserCallStack) {
 160   for (auto opnd : opnds) {
 161     if (!opnd->eval(parser, parserCallStack)) {
 162       return false;
 163     }
 164   }
 165   return true;
 166 }
 167
 168 Ref<SemanticContext> SemanticContext::AND::evalPrecedence(Recognizer *parser, RuleContext *parserCallStack) {
 169   bool differs = false;
 170   std::vector<Ref<SemanticContext>> operands;
 171   for (auto context : opnds) {
 172     Ref<SemanticContext> evaluated = context->evalPrecedence(parser, parserCallStack);
 173     differs |= (evaluated != context);
 174     if (evaluated == nullptr) {
 175       // The AND context is false if any element is false.
 176       return nullptr;
 177     } else if (evaluated != NONE) {
 178       // Reduce the result by skipping true elements.
 179       operands.push_back(evaluated);
 180     }
 181   }
 182
 183   if (!differs) {
 184     return shared_from_this();
 185   }
 186
 187   if (operands.empty()) {
 188     // All elements were true, so the AND context is true.
 189     return NONE;
 190   }
 191
 192   Ref<SemanticContext> result = operands[0];
 193   for (size_t i = 1; i < operands.size(); ++i) {
 194     result = SemanticContext::And(result, operands[i]);
 195   }
 196
 197   return result;
 198 }
 199
 200 std::string SemanticContext::AND::toString() const {
 201   std::string tmp;
 202   for (auto var : opnds) {
 203     tmp += var->toString() + " && ";
 204   }
 205   return tmp;
 206 }
 207
 208 //------------------ OR ------------------------------------------------------------------------------------------------
 209
 210 SemanticContext::OR::OR(Ref<SemanticContext> const& a, Ref<SemanticContext> const& b) {
 211   Set operands;
 212
 213   if (is<OR>(a)) {
 214     for (auto operand : std::dynamic_pointer_cast<OR>(a)->opnds) {
 215       operands.insert(operand);
 216     }
 217   } else {
 218     operands.insert(a);
 219   }
 220
 221   if (is<OR>(b)) {
 222     for (auto operand : std::dynamic_pointer_cast<OR>(b)->opnds) {
 223       operands.insert(operand);
 224     }
 225   } else {
 226     operands.insert(b);
 227   }
 228
 229   std::vector<Ref<PrecedencePredicate>> precedencePredicates = filterPrecedencePredicates(operands);
 230   if (!precedencePredicates.empty()) {
 231     // interested in the transition with the highest precedence
 232     auto predicate = [](Ref<PrecedencePredicate> const& a, Ref<PrecedencePredicate> const& b) {
 233       return a->precedence < b->precedence;
 234     };
 235     auto reduced = std::max_element(precedencePredicates.begin(), precedencePredicates.end(), predicate);
 236     operands.insert(*reduced);
 237   }
 238
 239   std::copy(operands.begin(), operands.end(), std::back_inserter(opnds));
 240 }
 241
 242 std::vector<Ref<SemanticContext>> SemanticContext::OR::getOperands() const {
 243   return opnds;
 244 }
 245
 246 bool SemanticContext::OR::operator == (const SemanticContext &other) const {
 247   if (this == &other)
 248     return true;
 249
 250   const OR *context = dynamic_cast<const OR *>(&other);
 251   if (context == nullptr)
 252     return false;
 253
 254   return Arrays::equals(opnds, context->opnds);
 255 }
 256
 257 size_t SemanticContext::OR::hashCode() const {
 258   return misc::MurmurHash::hashCode(opnds, typeid(OR).hash_code());
 259 }
 260
 261 bool SemanticContext::OR::eval(Recognizer *parser, RuleContext *parserCallStack) {
 262   for (auto opnd : opnds) {
 263     if (opnd->eval(parser, parserCallStack)) {
 264       return true;
 265     }
 266   }
 267   return false;
 268 }
 269
 270 Ref<SemanticContext> SemanticContext::OR::evalPrecedence(Recognizer *parser, RuleContext *parserCallStack) {
 271   bool differs = false;
 272   std::vector<Ref<SemanticContext>> operands;
 273   for (auto context : opnds) {
 274     Ref<SemanticContext> evaluated = context->evalPrecedence(parser, parserCallStack);
 275     differs |= (evaluated != context);
 276     if (evaluated == NONE) {
 277       // The OR context is true if any element is true.
 278       return NONE;
 279     } else if (evaluated != nullptr) {
 280       // Reduce the result by skipping false elements.
 281       operands.push_back(evaluated);
 282     }
 283   }
 284
 285   if (!differs) {
 286     return shared_from_this();
 287   }
 288
 289   if (operands.empty()) {
 290     // All elements were false, so the OR context is false.
 291     return nullptr;
 292   }
 293
 294   Ref<SemanticContext> result = operands[0];
 295   for (size_t i = 1; i < operands.size(); ++i) {
 296     result = SemanticContext::Or(result, operands[i]);
 297   }
 298
 299   return result;
 300 }
 301
 302 std::string SemanticContext::OR::toString() const {
 303   std::string tmp;
 304   for(auto var : opnds) {
 305     tmp += var->toString() + " || ";
 306   }
 307   return tmp;
 308 }
 309
 310 //------------------ SemanticContext -----------------------------------------------------------------------------------
 311
 312 const Ref<SemanticContext> SemanticContext::NONE = std::make_shared<Predicate>(INVALID_INDEX, INVALID_INDEX, false);
 313
 314 SemanticContext::~SemanticContext() {
 315 }
 316
 317 bool SemanticContext::operator != (const SemanticContext &other) const {
 318   return !(*this == other);
 319 }
 320
 321 Ref<SemanticContext> SemanticContext::evalPrecedence(Recognizer * /*parser*/, RuleContext * /*parserCallStack*/) {
 322   return shared_from_this();
 323 }
 324
 325 Ref<SemanticContext> SemanticContext::And(Ref<SemanticContext> const& a, Ref<SemanticContext> const& b) {
 326   if (!a || a == NONE) {
 327     return b;
 328   }
 329
 330   if (!b || b == NONE) {
 331     return a;
 332   }
 333
 334   Ref<AND> result = std::make_shared<AND>(a, b);
 335   if (result->opnds.size() == 1) {
 336     return result->opnds[0];
 337   }
 338
 339   return result;
 340 }
 341
 342 Ref<SemanticContext> SemanticContext::Or(Ref<SemanticContext> const& a, Ref<SemanticContext> const& b) {
 343   if (!a) {
 344     return b;
 345   }
 346   if (!b) {
 347     return a;
 348   }
 349
 350   if (a == NONE || b == NONE) {
 351     return NONE;
 352   }
 353
 354   Ref<OR> result = std::make_shared<OR>(a, b);
 355   if (result->opnds.size() == 1) {
 356     return result->opnds[0];
 357   }
 358
 359   return result;
 360 }
 361
 362 std::vector<Ref<SemanticContext::PrecedencePredicate>> SemanticContext::filterPrecedencePredicates(const Set &collection) {
 363   std::vector<Ref<SemanticContext::PrecedencePredicate>> result;
 364   for (auto context : collection) {
 365     if (antlrcpp::is<PrecedencePredicate>(context)) {
 366       result.push_back(std::dynamic_pointer_cast<PrecedencePredicate>(context));
 367     }
 368   }
 369
 370   return result;
 371 }
 372
 373
 374 //------------------ Operator -----------------------------------------------------------------------------------------
 375
 376 SemanticContext::Operator::~Operator() {
 377 }