diff options
Diffstat (limited to 'antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h')
| -rw-r--r-- | antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h | 266 |
1 files changed, 266 insertions, 0 deletions
diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h new file mode 100644 index 0000000..e8dfc23 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h @@ -0,0 +1,266 @@ +/* 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. + */ + +#pragma once + +#include "Recognizer.h" +#include "atn/ATN.h" +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + struct PredictionContextHasher; + struct PredictionContextComparer; + class PredictionContextMergeCache; + + typedef std::unordered_set<Ref<PredictionContext>, PredictionContextHasher, PredictionContextComparer> PredictionContextCache; + + class ANTLR4CPP_PUBLIC PredictionContext { + public: + /// Represents $ in local context prediction, which means wildcard. + /// *+x = *. + static const Ref<PredictionContext> EMPTY; + + /// Represents $ in an array in full context mode, when $ + /// doesn't mean wildcard: $ + x = [$,x]. Here, + /// $ = EMPTY_RETURN_STATE. + // ml: originally Integer.MAX_VALUE, which would be -1 for us, but this is already used in places where + // -1 is converted to unsigned, so we use a different value here. Any value does the job provided it doesn't + // conflict with real return states. +#if __cplusplus >= 201703L + static constexpr size_t EMPTY_RETURN_STATE = std::numeric_limits<size_t>::max() - 9; +#else + enum : size_t { + EMPTY_RETURN_STATE = static_cast<size_t>(-10), // std::numeric_limits<size_t>::max() - 9; doesn't work in VS 2013 + }; +#endif + + private: +#if __cplusplus >= 201703L + static constexpr size_t INITIAL_HASH = 1; +#else + enum : size_t { + INITIAL_HASH = 1, + }; +#endif + + public: + static size_t globalNodeCount; + const size_t id; + + /// <summary> + /// Stores the computed hash code of this <seealso cref="PredictionContext"/>. The hash + /// code is computed in parts to match the following reference algorithm. + /// + /// <pre> + /// private int referenceHashCode() { + /// int hash = <seealso cref="MurmurHash#initialize"/>(<seealso cref="#INITIAL_HASH"/>); + /// + /// for (int i = 0; i < <seealso cref="#size()"/>; i++) { + /// hash = <seealso cref="MurmurHash#update"/>(hash, <seealso cref="#getParent"/>(i)); + /// } + /// + /// for (int i = 0; i < <seealso cref="#size()"/>; i++) { + /// hash = <seealso cref="MurmurHash#update"/>(hash, <seealso cref="#getReturnState"/>(i)); + /// } + /// + /// hash = <seealso cref="MurmurHash#finish"/>(hash, 2 * <seealso cref="#size()"/>); + /// return hash; + /// } + /// </pre> + /// </summary> + const size_t cachedHashCode; + + protected: + PredictionContext(size_t cachedHashCode); + ~PredictionContext(); + + public: + /// Convert a RuleContext tree to a PredictionContext graph. + /// Return EMPTY if outerContext is empty. + static Ref<PredictionContext> fromRuleContext(const ATN &atn, RuleContext *outerContext); + + virtual size_t size() const = 0; + virtual Ref<PredictionContext> getParent(size_t index) const = 0; + virtual size_t getReturnState(size_t index) const = 0; + + virtual bool operator == (const PredictionContext &o) const = 0; + + /// This means only the EMPTY (wildcard? not sure) context is in set. + virtual bool isEmpty() const; + virtual bool hasEmptyPath() const; + virtual size_t hashCode() const; + + protected: + static size_t calculateEmptyHashCode(); + static size_t calculateHashCode(Ref<PredictionContext> parent, size_t returnState); + static size_t calculateHashCode(const std::vector<Ref<PredictionContext>> &parents, + const std::vector<size_t> &returnStates); + + public: + // dispatch + static Ref<PredictionContext> merge(const Ref<PredictionContext> &a, const Ref<PredictionContext> &b, + bool rootIsWildcard, PredictionContextMergeCache *mergeCache); + + /// <summary> + /// Merge two <seealso cref="SingletonPredictionContext"/> instances. + /// + /// <p/> + /// + /// Stack tops equal, parents merge is same; return left graph.<br/> + /// <embed src="images/SingletonMerge_SameRootSamePar.svg" type="image/svg+xml"/> + /// + /// <p/> + /// + /// Same stack top, parents differ; merge parents giving array node, then + /// remainders of those graphs. A new root node is created to point to the + /// merged parents.<br/> + /// <embed src="images/SingletonMerge_SameRootDiffPar.svg" type="image/svg+xml"/> + /// + /// <p/> + /// + /// Different stack tops pointing to same parent. Make array node for the + /// root where both element in the root point to the same (original) + /// parent.<br/> + /// <embed src="images/SingletonMerge_DiffRootSamePar.svg" type="image/svg+xml"/> + /// + /// <p/> + /// + /// Different stack tops pointing to different parents. Make array node for + /// the root where each element points to the corresponding original + /// parent.<br/> + /// <embed src="images/SingletonMerge_DiffRootDiffPar.svg" type="image/svg+xml"/> + /// </summary> + /// <param name="a"> the first <seealso cref="SingletonPredictionContext"/> </param> + /// <param name="b"> the second <seealso cref="SingletonPredictionContext"/> </param> + /// <param name="rootIsWildcard"> {@code true} if this is a local-context merge, + /// otherwise false to indicate a full-context merge </param> + /// <param name="mergeCache"> </param> + static Ref<PredictionContext> mergeSingletons(const Ref<SingletonPredictionContext> &a, + const Ref<SingletonPredictionContext> &b, bool rootIsWildcard, PredictionContextMergeCache *mergeCache); + + /** + * Handle case where at least one of {@code a} or {@code b} is + * {@link #EMPTY}. In the following diagrams, the symbol {@code $} is used + * to represent {@link #EMPTY}. + * + * <h2>Local-Context Merges</h2> + * + * <p>These local-context merge operations are used when {@code rootIsWildcard} + * is true.</p> + * + * <p>{@link #EMPTY} is superset of any graph; return {@link #EMPTY}.<br> + * <embed src="images/LocalMerge_EmptyRoot.svg" type="image/svg+xml"/></p> + * + * <p>{@link #EMPTY} and anything is {@code #EMPTY}, so merged parent is + * {@code #EMPTY}; return left graph.<br> + * <embed src="images/LocalMerge_EmptyParent.svg" type="image/svg+xml"/></p> + * + * <p>Special case of last merge if local context.<br> + * <embed src="images/LocalMerge_DiffRoots.svg" type="image/svg+xml"/></p> + * + * <h2>Full-Context Merges</h2> + * + * <p>These full-context merge operations are used when {@code rootIsWildcard} + * is false.</p> + * + * <p><embed src="images/FullMerge_EmptyRoots.svg" type="image/svg+xml"/></p> + * + * <p>Must keep all contexts; {@link #EMPTY} in array is a special value (and + * null parent).<br> + * <embed src="images/FullMerge_EmptyRoot.svg" type="image/svg+xml"/></p> + * + * <p><embed src="images/FullMerge_SameRoot.svg" type="image/svg+xml"/></p> + * + * @param a the first {@link SingletonPredictionContext} + * @param b the second {@link SingletonPredictionContext} + * @param rootIsWildcard {@code true} if this is a local-context merge, + * otherwise false to indicate a full-context merge + */ + static Ref<PredictionContext> mergeRoot(const Ref<SingletonPredictionContext> &a, + const Ref<SingletonPredictionContext> &b, bool rootIsWildcard); + + /** + * Merge two {@link ArrayPredictionContext} instances. + * + * <p>Different tops, different parents.<br> + * <embed src="images/ArrayMerge_DiffTopDiffPar.svg" type="image/svg+xml"/></p> + * + * <p>Shared top, same parents.<br> + * <embed src="images/ArrayMerge_ShareTopSamePar.svg" type="image/svg+xml"/></p> + * + * <p>Shared top, different parents.<br> + * <embed src="images/ArrayMerge_ShareTopDiffPar.svg" type="image/svg+xml"/></p> + * + * <p>Shared top, all shared parents.<br> + * <embed src="images/ArrayMerge_ShareTopSharePar.svg" type="image/svg+xml"/></p> + * + * <p>Equal tops, merge parents and reduce top to + * {@link SingletonPredictionContext}.<br> + * <embed src="images/ArrayMerge_EqualTop.svg" type="image/svg+xml"/></p> + */ + static Ref<PredictionContext> mergeArrays(const Ref<ArrayPredictionContext> &a, + const Ref<ArrayPredictionContext> &b, bool rootIsWildcard, PredictionContextMergeCache *mergeCache); + + protected: + /// Make pass over all M parents; merge any equal() ones. + /// @returns true if the list has been changed (i.e. duplicates where found). + static bool combineCommonParents(std::vector<Ref<PredictionContext>> &parents); + + public: + static std::string toDOTString(const Ref<PredictionContext> &context); + + static Ref<PredictionContext> getCachedContext(const Ref<PredictionContext> &context, + PredictionContextCache &contextCache, + std::map<Ref<PredictionContext>, Ref<PredictionContext>> &visited); + + // ter's recursive version of Sam's getAllNodes() + static std::vector<Ref<PredictionContext>> getAllContextNodes(const Ref<PredictionContext> &context); + static void getAllContextNodes_(const Ref<PredictionContext> &context, + std::vector<Ref<PredictionContext>> &nodes, std::set<PredictionContext *> &visited); + + virtual std::string toString() const; + virtual std::string toString(Recognizer *recog) const; + + std::vector<std::string> toStrings(Recognizer *recognizer, int currentState); + std::vector<std::string> toStrings(Recognizer *recognizer, const Ref<PredictionContext> &stop, int currentState); + }; + + struct PredictionContextHasher { + size_t operator () (const Ref<PredictionContext> &k) const { + return k->hashCode(); + } + }; + + struct PredictionContextComparer { + bool operator () (const Ref<PredictionContext> &lhs, const Ref<PredictionContext> &rhs) const + { + if (lhs == rhs) // Object identity. + return true; + return (lhs->hashCode() == rhs->hashCode()) && (*lhs == *rhs); + } + }; + + class PredictionContextMergeCache { + public: + Ref<PredictionContext> put(Ref<PredictionContext> const& key1, Ref<PredictionContext> const& key2, + Ref<PredictionContext> const& value); + Ref<PredictionContext> get(Ref<PredictionContext> const& key1, Ref<PredictionContext> const& key2); + + void clear(); + std::string toString() const; + size_t count() const; + + private: + std::unordered_map<Ref<PredictionContext>, + std::unordered_map<Ref<PredictionContext>, Ref<PredictionContext>, PredictionContextHasher, PredictionContextComparer>, + PredictionContextHasher, PredictionContextComparer> _data; + + }; + +} // namespace atn +} // namespace antlr4 + |