cpp/third_party/antlr4-cpp-runtime-4/runtime/src/atn/PredictionMode.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/ATNConfigSet.h"
#include "atn/ATNConfig.h"
#include "misc/MurmurHash.h"
#include "SemanticContext.h"

#include "PredictionMode.h"

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

struct AltAndContextConfigHasher
{
  /**
   * The hash code is only a function of the {@link ATNState#stateNumber}
   * and {@link ATNConfig#context}.
   */
  size_t operator () (ATNConfig *o) const {
    size_t hashCode = misc::MurmurHash::initialize(7);
    hashCode = misc::MurmurHash::update(hashCode, o->state->stateNumber);
    hashCode = misc::MurmurHash::update(hashCode, o->context);
    return misc::MurmurHash::finish(hashCode, 2);
  }
};

struct AltAndContextConfigComparer {
  bool operator()(ATNConfig *a, ATNConfig *b) const
  {
    if (a == b) {
      return true;
    }
    return a->state->stateNumber == b->state->stateNumber && *a->context == *b->context;
  }
};

bool PredictionModeClass::hasSLLConflictTerminatingPrediction(PredictionMode mode, ATNConfigSet *configs) {
  /* Configs in rule stop states indicate reaching the end of the decision
   * rule (local context) or end of start rule (full context). If all
   * configs meet this condition, then none of the configurations is able
   * to match additional input so we terminate prediction.
   */
  if (allConfigsInRuleStopStates(configs)) {
    return true;
  }

  bool heuristic;

  // Pure SLL mode parsing or SLL+LL if:
  // Don't bother with combining configs from different semantic
  // contexts if we can fail over to full LL; costs more time
  // since we'll often fail over anyway.
  if (mode == PredictionMode::SLL || !configs->hasSemanticContext) {
    std::vector<antlrcpp::BitSet> altsets = getConflictingAltSubsets(configs);
    heuristic = hasConflictingAltSet(altsets) && !hasStateAssociatedWithOneAlt(configs);
  } else {
    // dup configs, tossing out semantic predicates
    ATNConfigSet dup(true);
    for (auto &config : configs->configs) {
      Ref<ATNConfig> c = std::make_shared<ATNConfig>(config, SemanticContext::NONE);
      dup.add(c);
    }
    std::vector<antlrcpp::BitSet> altsets = getConflictingAltSubsets(&dup);
    heuristic = hasConflictingAltSet(altsets) && !hasStateAssociatedWithOneAlt(&dup);
  }

  return heuristic;
}

bool PredictionModeClass::hasConfigInRuleStopState(ATNConfigSet *configs) {
  for (auto &c : configs->configs) {
    if (is<RuleStopState *>(c->state)) {
      return true;
    }
  }

  return false;
}

bool PredictionModeClass::allConfigsInRuleStopStates(ATNConfigSet *configs) {
  for (auto &config : configs->configs) {
    if (!is<RuleStopState*>(config->state)) {
      return false;
    }
  }

  return true;
}

size_t PredictionModeClass::resolvesToJustOneViableAlt(const std::vector<antlrcpp::BitSet>& altsets) {
  return getSingleViableAlt(altsets);
}

bool PredictionModeClass::allSubsetsConflict(const std::vector<antlrcpp::BitSet>& altsets) {
  return !hasNonConflictingAltSet(altsets);
}

bool PredictionModeClass::hasNonConflictingAltSet(const std::vector<antlrcpp::BitSet>& altsets) {
  for (antlrcpp::BitSet alts : altsets) {
    if (alts.count() == 1) {
      return true;
    }
  }
  return false;
}

bool PredictionModeClass::hasConflictingAltSet(const std::vector<antlrcpp::BitSet>& altsets) {
  for (antlrcpp::BitSet alts : altsets) {
    if (alts.count() > 1) {
      return true;
    }
  }
  return false;
}

bool PredictionModeClass::allSubsetsEqual(const std::vector<antlrcpp::BitSet>& altsets) {
  if (altsets.empty()) {
    return true;
  }

  const antlrcpp::BitSet& first = *altsets.begin();
  for (const antlrcpp::BitSet& alts : altsets) {
    if (alts != first) {
      return false;
    }
  }
  return true;
}

size_t PredictionModeClass::getUniqueAlt(const std::vector<antlrcpp::BitSet>& altsets) {
  antlrcpp::BitSet all = getAlts(altsets);
  if (all.count() == 1) {
    return all.nextSetBit(0);
  }
  return ATN::INVALID_ALT_NUMBER;
}

antlrcpp::BitSet PredictionModeClass::getAlts(const std::vector<antlrcpp::BitSet>& altsets) {
  antlrcpp::BitSet all;
  for (antlrcpp::BitSet alts : altsets) {
    all |= alts;
  }

  return all;
}

antlrcpp::BitSet PredictionModeClass::getAlts(ATNConfigSet *configs) {
  antlrcpp::BitSet alts;
  for (auto &config : configs->configs) {
    alts.set(config->alt);
  }
  return alts;
}

std::vector<antlrcpp::BitSet> PredictionModeClass::getConflictingAltSubsets(ATNConfigSet *configs) {
  std::unordered_map<ATNConfig *, antlrcpp::BitSet, AltAndContextConfigHasher, AltAndContextConfigComparer> configToAlts;
  for (auto &config : configs->configs) {
    configToAlts[config.get()].set(config->alt);
  }
  std::vector<antlrcpp::BitSet> values;
  for (auto it : configToAlts) {
    values.push_back(it.second);
  }
  return values;
}

std::map<ATNState*, antlrcpp::BitSet> PredictionModeClass::getStateToAltMap(ATNConfigSet *configs) {
  std::map<ATNState*, antlrcpp::BitSet> m;
  for (auto &c : configs->configs) {
    m[c->state].set(c->alt);
  }
  return m;
}

bool PredictionModeClass::hasStateAssociatedWithOneAlt(ATNConfigSet *configs) {
  std::map<ATNState*, antlrcpp::BitSet> x = getStateToAltMap(configs);
  for (std::map<ATNState*, antlrcpp::BitSet>::iterator it = x.begin(); it != x.end(); it++){
    if (it->second.count() == 1) return true;
  }
  return false;
}

size_t PredictionModeClass::getSingleViableAlt(const std::vector<antlrcpp::BitSet>& altsets) {
  antlrcpp::BitSet viableAlts;
  for (antlrcpp::BitSet alts : altsets) {
    size_t minAlt = alts.nextSetBit(0);

    viableAlts.set(minAlt);
    if (viableAlts.count() > 1)  // more than 1 viable alt
    {
      return ATN::INVALID_ALT_NUMBER;
    }
  }

  return viableAlts.nextSetBit(0);
}