cpp/third_party/antlr4-cpp-runtime-4/runtime/src/atn/PredictionContext.h - tsfile - Git at Google

 /* 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 <atomic>

 #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 std::atomic<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
	/* 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 <atomic>

	#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 std::atomic<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