cpp/third_party/antlr4-cpp-runtime-4/runtime/src/atn/LL1Analyzer.cpp

/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
 * Use of this file is governed by the BSD 3-clause license that
 * can be found in the LICENSE.txt file in the project root.
 */

#include "atn/RuleStopState.h"
#include "atn/Transition.h"
#include "atn/RuleTransition.h"
#include "atn/SingletonPredictionContext.h"
#include "atn/AbstractPredicateTransition.h"
#include "atn/WildcardTransition.h"
#include "atn/NotSetTransition.h"
#include "misc/IntervalSet.h"
#include "atn/ATNConfig.h"
#include "atn/EmptyPredictionContext.h"

#include "support/CPPUtils.h"

#include "atn/LL1Analyzer.h"

using namespace antlr4;
using namespace antlr4::atn;
using namespace antlrcpp;

LL1Analyzer::LL1Analyzer(const ATN &atn) : _atn(atn) {
}

LL1Analyzer::~LL1Analyzer() {
}

std::vector<misc::IntervalSet> LL1Analyzer::getDecisionLookahead(ATNState *s) const {
  std::vector<misc::IntervalSet> look;

  if (s == nullptr) {
    return look;
  }

  look.resize(s->transitions.size()); // Fills all interval sets with defaults.
  for (size_t alt = 0; alt < s->transitions.size(); alt++) {
    bool seeThruPreds = false; // fail to get lookahead upon pred

    ATNConfig::Set lookBusy;
    antlrcpp::BitSet callRuleStack;
    _LOOK(s->transitions[alt]->target, nullptr, PredictionContext::EMPTY,
          look[alt], lookBusy, callRuleStack, seeThruPreds, false);

    // Wipe out lookahead for this alternative if we found nothing
    // or we had a predicate when we !seeThruPreds
    if (look[alt].size() == 0 || look[alt].contains(HIT_PRED)) {
      look[alt].clear();
    }
  }
  return look;
}

misc::IntervalSet LL1Analyzer::LOOK(ATNState *s, RuleContext *ctx) const {
  return LOOK(s, nullptr, ctx);
}

misc::IntervalSet LL1Analyzer::LOOK(ATNState *s, ATNState *stopState, RuleContext *ctx) const {
  misc::IntervalSet r;
  bool seeThruPreds = true; // ignore preds; get all lookahead
  Ref<PredictionContext> lookContext = ctx != nullptr ? PredictionContext::fromRuleContext(_atn, ctx) : nullptr;

  ATNConfig::Set lookBusy;
  antlrcpp::BitSet callRuleStack;
  _LOOK(s, stopState, lookContext, r, lookBusy, callRuleStack, seeThruPreds, true);

  return r;
}

void LL1Analyzer::_LOOK(ATNState *s, ATNState *stopState, Ref<PredictionContext> const& ctx, misc::IntervalSet &look,
  ATNConfig::Set &lookBusy, antlrcpp::BitSet &calledRuleStack, bool seeThruPreds, bool addEOF) const {

  Ref<ATNConfig> c = std::make_shared<ATNConfig>(s, 0, ctx);

  if (lookBusy.count(c) > 0) // Keep in mind comparison is based on members of the class, not the actual instance.
    return;

  lookBusy.insert(c);

  // ml: s can never be null, hence no need to check if stopState is != null.
  if (s == stopState) {
    if (ctx == nullptr) {
      look.add(static_cast<int>(Token::EPSILON));
      return;
    } else if (ctx->isEmpty() && addEOF) {
      look.add(static_cast<int>(Token::EOF));
      return;
    }
  }

  if (s->getStateType() == ATNState::RULE_STOP) {
    if (ctx == nullptr) {
      look.add(static_cast<int>(Token::EPSILON));
      return;
    } else if (ctx->isEmpty() && addEOF) {
      look.add(static_cast<int>(Token::EOF));
      return;
    }

    if (ctx != PredictionContext::EMPTY) {
      bool removed = calledRuleStack.test(s->ruleIndex);
      calledRuleStack[s->ruleIndex] = false;
       auto onExit = finally([removed, &calledRuleStack, s] {
                if (removed) {
                  calledRuleStack.set(s->ruleIndex);
                }
              });
       // run thru all possible stack tops in ctx
      for (size_t i = 0; i < ctx->size(); i++) {
        ATNState *returnState = _atn.states[ctx->getReturnState(i)];
        _LOOK(returnState, stopState, ctx->getParent(i), look, lookBusy, calledRuleStack, seeThruPreds, addEOF);
      }
      return;
    }
  }

  size_t n = s->transitions.size();
  for (size_t i = 0; i < n; i++) {
    Transition *t = s->transitions[i];

    if (t->getSerializationType() == Transition::RULE) {
      if (calledRuleStack[(static_cast<RuleTransition*>(t))->target->ruleIndex]) {
        continue;
      }

      Ref<PredictionContext> newContext = SingletonPredictionContext::create(ctx, (static_cast<RuleTransition*>(t))->followState->stateNumber);
      auto onExit = finally([t, &calledRuleStack] {
        calledRuleStack[(static_cast<RuleTransition*>(t))->target->ruleIndex] = false;
      });

      calledRuleStack.set((static_cast<RuleTransition*>(t))->target->ruleIndex);
      _LOOK(t->target, stopState, newContext, look, lookBusy, calledRuleStack, seeThruPreds, addEOF);

    } else if (is<AbstractPredicateTransition *>(t)) {
      if (seeThruPreds) {
        _LOOK(t->target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF);
      } else {
        look.add(HIT_PRED);
      }
    } else if (t->isEpsilon()) {
      _LOOK(t->target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF);
    } else if (t->getSerializationType() == Transition::WILDCARD) {
      look.addAll(misc::IntervalSet::of(Token::MIN_USER_TOKEN_TYPE, static_cast<ssize_t>(_atn.maxTokenType)));
    } else {
      misc::IntervalSet set = t->label();
      if (!set.isEmpty()) {
        if (is<NotSetTransition*>(t)) {
          set = set.complement(misc::IntervalSet::of(Token::MIN_USER_TOKEN_TYPE, static_cast<ssize_t>(_atn.maxTokenType)));
        }
        look.addAll(set);
      }
    }
  }
}