gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/atn/PredictionContext.h

   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 #pragma once
   7
   8 #include "Recognizer.h"
   9 #include "atn/ATN.h"
  10 #include "atn/ATNState.h"
  11
  12 namespace antlr4 {
  13 namespace atn {
  14
  15   struct PredictionContextHasher;
  16   struct PredictionContextComparer;
  17   class PredictionContextMergeCache;
  18
  19   typedef std::unordered_set<Ref<PredictionContext>, PredictionContextHasher, PredictionContextComparer> PredictionContextCache;
  20
  21   class ANTLR4CPP_PUBLIC PredictionContext {
  22   public:
  23     /// Represents $ in local context prediction, which means wildcard.
  24     /// *+x = *.
  25     static const Ref<PredictionContext> EMPTY;
  26
  27     /// Represents $ in an array in full context mode, when $
  28     /// doesn't mean wildcard: $ + x = [$,x]. Here,
  29     /// $ = EMPTY_RETURN_STATE.
  30     // ml: originally Integer.MAX_VALUE, which would be -1 for us, but this is already used in places where
  31     //     -1 is converted to unsigned, so we use a different value here. Any value does the job provided it doesn't
  32     //     conflict with real return states.
  33 #if __cplusplus >= 201703L
  34     static constexpr size_t EMPTY_RETURN_STATE = std::numeric_limits<size_t>::max() - 9;
  35 #else
  36     enum : size_t {
  37       EMPTY_RETURN_STATE = static_cast<size_t>(-10), // std::numeric_limits<size_t>::max() - 9; doesn't work in VS 2013
  38     };
  39 #endif
  40
  41   private:
  42 #if __cplusplus >= 201703L
  43     static constexpr size_t INITIAL_HASH = 1;
  44 #else
  45     enum : size_t {
  46       INITIAL_HASH = 1,
  47     };
  48 #endif
  49
  50   public:
  51     static size_t globalNodeCount;
  52     const size_t id;
  53
  54     /// <summary>
  55     /// Stores the computed hash code of this <seealso cref="PredictionContext"/>. The hash
  56     /// code is computed in parts to match the following reference algorithm.
  57     ///
  58     /// <pre>
  59     ///  private int referenceHashCode() {
  60     ///      int hash = <seealso cref="MurmurHash#initialize"/>(<seealso cref="#INITIAL_HASH"/>);
  61     ///
  62     ///      for (int i = 0; i < <seealso cref="#size()"/>; i++) {
  63     ///          hash = <seealso cref="MurmurHash#update"/>(hash, <seealso cref="#getParent"/>(i));
  64     ///      }
  65     ///
  66     ///      for (int i = 0; i < <seealso cref="#size()"/>; i++) {
  67     ///          hash = <seealso cref="MurmurHash#update"/>(hash, <seealso cref="#getReturnState"/>(i));
  68     ///      }
  69     ///
  70     ///      hash = <seealso cref="MurmurHash#finish"/>(hash, 2 * <seealso cref="#size()"/>);
  71     ///      return hash;
  72     ///  }
  73     /// </pre>
  74     /// </summary>
  75     const size_t cachedHashCode;
  76
  77   protected:
  78     PredictionContext(size_t cachedHashCode);
  79     ~PredictionContext();
  80
  81   public:
  82     /// Convert a RuleContext tree to a PredictionContext graph.
  83     /// Return EMPTY if outerContext is empty.
  84     static Ref<PredictionContext> fromRuleContext(const ATN &atn, RuleContext *outerContext);
  85
  86     virtual size_t size() const = 0;
  87     virtual Ref<PredictionContext> getParent(size_t index) const = 0;
  88     virtual size_t getReturnState(size_t index) const = 0;
  89
  90     virtual bool operator == (const PredictionContext &o) const = 0;
  91
  92     /// This means only the EMPTY (wildcard? not sure) context is in set.
  93     virtual bool isEmpty() const;
  94     virtual bool hasEmptyPath() const;
  95     virtual size_t hashCode() const;
  96
  97   protected:
  98     static size_t calculateEmptyHashCode();
  99     static size_t calculateHashCode(Ref<PredictionContext> parent, size_t returnState);
 100     static size_t calculateHashCode(const std::vector<Ref<PredictionContext>> &parents,
 101                                     const std::vector<size_t> &returnStates);
 102
 103   public:
 104     // dispatch
 105     static Ref<PredictionContext> merge(const Ref<PredictionContext> &a, const Ref<PredictionContext> &b,
 106                                         bool rootIsWildcard, PredictionContextMergeCache *mergeCache);
 107
 108     /// <summary>
 109     /// Merge two <seealso cref="SingletonPredictionContext"/> instances.
 110     ///
 111     /// <p/>
 112     ///
 113     /// Stack tops equal, parents merge is same; return left graph.<br/>
 114     /// <embed src="images/SingletonMerge_SameRootSamePar.svg" type="image/svg+xml"/>
 115     ///
 116     /// <p/>
 117     ///
 118     /// Same stack top, parents differ; merge parents giving array node, then
 119     /// remainders of those graphs. A new root node is created to point to the
 120     /// merged parents.<br/>
 121     /// <embed src="images/SingletonMerge_SameRootDiffPar.svg" type="image/svg+xml"/>
 122     ///
 123     /// <p/>
 124     ///
 125     /// Different stack tops pointing to same parent. Make array node for the
 126     /// root where both element in the root point to the same (original)
 127     /// parent.<br/>
 128     /// <embed src="images/SingletonMerge_DiffRootSamePar.svg" type="image/svg+xml"/>
 129     ///
 130     /// <p/>
 131     ///
 132     /// Different stack tops pointing to different parents. Make array node for
 133     /// the root where each element points to the corresponding original
 134     /// parent.<br/>
 135     /// <embed src="images/SingletonMerge_DiffRootDiffPar.svg" type="image/svg+xml"/>
 136     /// </summary>
 137     /// <param name="a"> the first <seealso cref="SingletonPredictionContext"/> </param>
 138     /// <param name="b"> the second <seealso cref="SingletonPredictionContext"/> </param>
 139     /// <param name="rootIsWildcard"> {@code true} if this is a local-context merge,
 140     /// otherwise false to indicate a full-context merge </param>
 141     /// <param name="mergeCache"> </param>
 142     static Ref<PredictionContext> mergeSingletons(const Ref<SingletonPredictionContext> &a,
 143       const Ref<SingletonPredictionContext> &b, bool rootIsWildcard, PredictionContextMergeCache *mergeCache);
 144
 145     /**
 146      * Handle case where at least one of {@code a} or {@code b} is
 147      * {@link #EMPTY}. In the following diagrams, the symbol {@code $} is used
 148      * to represent {@link #EMPTY}.
 149      *
 150      * <h2>Local-Context Merges</h2>
 151      *
 152      * <p>These local-context merge operations are used when {@code rootIsWildcard}
 153      * is true.</p>
 154      *
 155      * <p>{@link #EMPTY} is superset of any graph; return {@link #EMPTY}.<br>
 156      * <embed src="images/LocalMerge_EmptyRoot.svg" type="image/svg+xml"/></p>
 157      *
 158      * <p>{@link #EMPTY} and anything is {@code #EMPTY}, so merged parent is
 159      * {@code #EMPTY}; return left graph.<br>
 160      * <embed src="images/LocalMerge_EmptyParent.svg" type="image/svg+xml"/></p>
 161      *
 162      * <p>Special case of last merge if local context.<br>
 163      * <embed src="images/LocalMerge_DiffRoots.svg" type="image/svg+xml"/></p>
 164      *
 165      * <h2>Full-Context Merges</h2>
 166      *
 167      * <p>These full-context merge operations are used when {@code rootIsWildcard}
 168      * is false.</p>
 169      *
 170      * <p><embed src="images/FullMerge_EmptyRoots.svg" type="image/svg+xml"/></p>
 171      *
 172      * <p>Must keep all contexts; {@link #EMPTY} in array is a special value (and
 173      * null parent).<br>
 174      * <embed src="images/FullMerge_EmptyRoot.svg" type="image/svg+xml"/></p>
 175      *
 176      * <p><embed src="images/FullMerge_SameRoot.svg" type="image/svg+xml"/></p>
 177      *
 178      * @param a the first {@link SingletonPredictionContext}
 179      * @param b the second {@link SingletonPredictionContext}
 180      * @param rootIsWildcard {@code true} if this is a local-context merge,
 181      * otherwise false to indicate a full-context merge
 182      */
 183     static Ref<PredictionContext> mergeRoot(const Ref<SingletonPredictionContext> &a,
 184       const Ref<SingletonPredictionContext> &b, bool rootIsWildcard);
 185
 186     /**
 187      * Merge two {@link ArrayPredictionContext} instances.
 188      *
 189      * <p>Different tops, different parents.<br>
 190      * <embed src="images/ArrayMerge_DiffTopDiffPar.svg" type="image/svg+xml"/></p>
 191      *
 192      * <p>Shared top, same parents.<br>
 193      * <embed src="images/ArrayMerge_ShareTopSamePar.svg" type="image/svg+xml"/></p>
 194      *
 195      * <p>Shared top, different parents.<br>
 196      * <embed src="images/ArrayMerge_ShareTopDiffPar.svg" type="image/svg+xml"/></p>
 197      *
 198      * <p>Shared top, all shared parents.<br>
 199      * <embed src="images/ArrayMerge_ShareTopSharePar.svg" type="image/svg+xml"/></p>
 200      *
 201      * <p>Equal tops, merge parents and reduce top to
 202      * {@link SingletonPredictionContext}.<br>
 203      * <embed src="images/ArrayMerge_EqualTop.svg" type="image/svg+xml"/></p>
 204      */
 205     static Ref<PredictionContext> mergeArrays(const Ref<ArrayPredictionContext> &a,
 206       const Ref<ArrayPredictionContext> &b, bool rootIsWildcard, PredictionContextMergeCache *mergeCache);
 207
 208   protected:
 209     /// Make pass over all M parents; merge any equal() ones.
 210     /// @returns true if the list has been changed (i.e. duplicates where found).
 211     static bool combineCommonParents(std::vector<Ref<PredictionContext>> &parents);
 212
 213   public:
 214     static std::string toDOTString(const Ref<PredictionContext> &context);
 215
 216     static Ref<PredictionContext> getCachedContext(const Ref<PredictionContext> &context,
 217       PredictionContextCache &contextCache,
 218       std::map<Ref<PredictionContext>, Ref<PredictionContext>> &visited);
 219
 220     // ter's recursive version of Sam's getAllNodes()
 221     static std::vector<Ref<PredictionContext>> getAllContextNodes(const Ref<PredictionContext> &context);
 222     static void getAllContextNodes_(const Ref<PredictionContext> &context,
 223       std::vector<Ref<PredictionContext>> &nodes, std::set<PredictionContext *> &visited);
 224
 225     virtual std::string toString() const;
 226     virtual std::string toString(Recognizer *recog) const;
 227
 228     std::vector<std::string> toStrings(Recognizer *recognizer, int currentState);
 229     std::vector<std::string> toStrings(Recognizer *recognizer, const Ref<PredictionContext> &stop, int currentState);
 230   };
 231
 232   struct PredictionContextHasher {
 233     size_t operator () (const Ref<PredictionContext> &k) const {
 234       return k->hashCode();
 235     }
 236   };
 237
 238   struct PredictionContextComparer {
 239     bool operator () (const Ref<PredictionContext> &lhs, const Ref<PredictionContext> &rhs) const
 240     {
 241       if (lhs == rhs) // Object identity.
 242         return true;
 243       return (lhs->hashCode() == rhs->hashCode()) && (*lhs == *rhs);
 244     }
 245   };
 246
 247   class PredictionContextMergeCache {
 248   public:
 249     Ref<PredictionContext> put(Ref<PredictionContext> const& key1, Ref<PredictionContext> const& key2,
 250                                Ref<PredictionContext> const& value);
 251     Ref<PredictionContext> get(Ref<PredictionContext> const& key1, Ref<PredictionContext> const& key2);
 252
 253     void clear();
 254     std::string toString() const;
 255     size_t count() const;
 256
 257   private:
 258     std::unordered_map<Ref<PredictionContext>,
 259       std::unordered_map<Ref<PredictionContext>, Ref<PredictionContext>, PredictionContextHasher, PredictionContextComparer>,
 260       PredictionContextHasher, PredictionContextComparer> _data;
 261
 262   };
 263
 264 } // namespace atn
 265 } // namespace antlr4
 266