You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
318 lines
11 KiB
318 lines
11 KiB
/// \file
|
|
/// Definition of the ANTLR3 common tree node stream.
|
|
///
|
|
|
|
#ifndef _ANTLR_COMMON_TREE_NODE_STREAM__HPP
|
|
#define _ANTLR_COMMON_TREE_NODE_STREAM__HPP
|
|
|
|
// [The "BSD licence"]
|
|
// Copyright (c) 2005-2009 Gokulakannan Somasundaram, ElectronDB
|
|
|
|
//
|
|
// All rights reserved.
|
|
//
|
|
// Redistribution and use in source and binary forms, with or without
|
|
// modification, are permitted provided that the following conditions
|
|
// are met:
|
|
// 1. Redistributions of source code must retain the above copyright
|
|
// notice, this list of conditions and the following disclaimer.
|
|
// 2. Redistributions in binary form must reproduce the above copyright
|
|
// notice, this list of conditions and the following disclaimer in the
|
|
// documentation and/or other materials provided with the distribution.
|
|
// 3. The name of the author may not be used to endorse or promote products
|
|
// derived from this software without specific prior written permission.
|
|
//
|
|
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
|
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
|
|
// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
|
|
// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
|
|
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
|
|
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
|
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
|
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
|
|
// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
#include "antlr3defs.hpp"
|
|
|
|
ANTLR_BEGIN_NAMESPACE()
|
|
|
|
template<class ImplTraits>
|
|
class CommonTreeNodeStream : public ImplTraits::TreeNodeIntStreamType
|
|
{
|
|
public:
|
|
enum Constants
|
|
{
|
|
/// Token buffer initial size settings ( will auto increase)
|
|
///
|
|
DEFAULT_INITIAL_BUFFER_SIZE = 100
|
|
, INITIAL_CALL_STACK_SIZE = 10
|
|
};
|
|
|
|
typedef typename ImplTraits::TreeType TreeType;
|
|
typedef TreeType UnitType;
|
|
typedef typename ImplTraits::StringType StringType;
|
|
typedef typename ImplTraits::StringStreamType StringStreamType;
|
|
typedef typename ImplTraits::TreeAdaptorType TreeAdaptorType;
|
|
typedef typename ImplTraits::TreeNodeIntStreamType IntStreamType;
|
|
typedef typename ImplTraits::AllocPolicyType AllocPolicyType;
|
|
typedef typename AllocPolicyType::template VectorType<TreeType*> NodesType;
|
|
typedef typename AllocPolicyType::template VectorType< TreeWalkState<ImplTraits> > MarkersType;
|
|
typedef typename AllocPolicyType::template StackType< ANTLR_INT32 > NodeStackType;
|
|
typedef typename ImplTraits::TreeParserType ComponentType;
|
|
typedef typename ImplTraits::CommonTokenType CommonTokenType;
|
|
typedef typename ImplTraits::TreeNodeIntStreamType BaseType;
|
|
|
|
public:
|
|
/// Dummy tree node that indicates a descent into a child
|
|
/// tree. Initialized by a call to create a new interface.
|
|
///
|
|
TreeType m_DOWN;
|
|
|
|
/// Dummy tree node that indicates a descent up to a parent
|
|
/// tree. Initialized by a call to create a new interface.
|
|
///
|
|
TreeType m_UP;
|
|
|
|
/// Dummy tree node that indicates the termination point of the
|
|
/// tree. Initialized by a call to create a new interface.
|
|
///
|
|
TreeType m_EOF_NODE;
|
|
|
|
/// Dummy node that is returned if we need to indicate an invalid node
|
|
/// for any reason.
|
|
///
|
|
TreeType m_INVALID_NODE;
|
|
|
|
/// The complete mapping from stream index to tree node.
|
|
/// This buffer includes pointers to DOWN, UP, and EOF nodes.
|
|
/// It is built upon ctor invocation. The elements are type
|
|
/// Object as we don't what the trees look like.
|
|
///
|
|
/// Load upon first need of the buffer so we can set token types
|
|
/// of interest for reverseIndexing. Slows us down a wee bit to
|
|
/// do all of the if p==-1 testing everywhere though, though in C
|
|
/// you won't really be able to measure this.
|
|
///
|
|
/// Must be freed when the tree node stream is torn down.
|
|
///
|
|
NodesType m_nodes;
|
|
|
|
/// Which tree are we navigating ?
|
|
///
|
|
TreeType* m_root;
|
|
|
|
/// Pointer to tree adaptor interface that manipulates/builds
|
|
/// the tree.
|
|
///
|
|
TreeAdaptorType* m_adaptor;
|
|
|
|
/// As we walk down the nodes, we must track parent nodes so we know
|
|
/// where to go after walking the last child of a node. When visiting
|
|
/// a child, push current node and current index (current index
|
|
/// is first stored in the tree node structure to avoid two stacks.
|
|
///
|
|
NodeStackType m_nodeStack;
|
|
|
|
/// The current index into the nodes vector of the current tree
|
|
/// we are parsing and possibly rewriting.
|
|
///
|
|
ANTLR_INT32 m_p;
|
|
|
|
/// Which node are we currently visiting?
|
|
///
|
|
TreeType* m_currentNode;
|
|
|
|
/// Which node did we last visit? Used for LT(-1)
|
|
///
|
|
TreeType* m_previousNode;
|
|
|
|
/// Which child are we currently visiting? If -1 we have not visited
|
|
/// this node yet; next consume() request will set currentIndex to 0.
|
|
///
|
|
ANTLR_INT32 m_currentChildIndex;
|
|
|
|
/// What node index did we just consume? i=0..n-1 for n node trees.
|
|
/// IntStream.next is hence 1 + this value. Size will be same.
|
|
///
|
|
ANTLR_MARKER m_absoluteNodeIndex;
|
|
|
|
/// Buffer tree node stream for use with LT(i). This list grows
|
|
/// to fit new lookahead depths, but consume() wraps like a circular
|
|
/// buffer.
|
|
///
|
|
TreeType** m_lookAhead;
|
|
|
|
/// Number of elements available in the lookahead buffer at any point in
|
|
/// time. This is the current size of the array.
|
|
///
|
|
ANTLR_UINT32 m_lookAheadLength;
|
|
|
|
/// lookAhead[head] is the first symbol of lookahead, LT(1).
|
|
///
|
|
ANTLR_UINT32 m_head;
|
|
|
|
/// Add new lookahead at lookahead[tail]. tail wraps around at the
|
|
/// end of the lookahead buffer so tail could be less than head.
|
|
///
|
|
ANTLR_UINT32 m_tail;
|
|
|
|
/// Calls to mark() may be nested so we have to track a stack of
|
|
/// them. The marker is an index into this stack. Index 0 is
|
|
/// the first marker. This is a List<TreeWalkState>
|
|
///
|
|
MarkersType m_markers;
|
|
|
|
/// Indicates whether this node stream was derived from a prior
|
|
/// node stream to be used by a rewriting tree parser for instance.
|
|
/// If this flag is set to ANTLR_TRUE, then when this stream is
|
|
/// closed it will not free the root tree as this tree always
|
|
/// belongs to the origniating node stream.
|
|
///
|
|
bool m_isRewriter;
|
|
|
|
/// If set to ANTLR_TRUE then the navigation nodes UP, DOWN are
|
|
/// duplicated rather than reused within the tree.
|
|
///
|
|
bool m_uniqueNavigationNodes;
|
|
|
|
public:
|
|
// INTERFACE
|
|
//
|
|
CommonTreeNodeStream( ANTLR_UINT32 hint );
|
|
CommonTreeNodeStream( const CommonTreeNodeStream& ctn );
|
|
CommonTreeNodeStream( TreeType* tree, ANTLR_UINT32 hint );
|
|
|
|
void init( ANTLR_UINT32 hint );
|
|
~CommonTreeNodeStream();
|
|
|
|
/// Get tree node at current input pointer + i ahead where i=1 is next node.
|
|
/// i<0 indicates nodes in the past. So LT(-1) is previous node, but
|
|
/// implementations are not required to provide results for k < -1.
|
|
/// LT(0) is undefined. For i>=n, return null.
|
|
/// Return NULL for LT(0) and any index that results in an absolute address
|
|
/// that is negative (beyond the start of the list).
|
|
///
|
|
/// This is analogous to the LT() method of the TokenStream, but this
|
|
/// returns a tree node instead of a token. Makes code gen identical
|
|
/// for both parser and tree grammars. :)
|
|
///
|
|
TreeType* _LT(ANTLR_INT32 k);
|
|
|
|
/// Where is this stream pulling nodes from? This is not the name, but
|
|
/// the object that provides node objects.
|
|
///
|
|
TreeType* getTreeSource();
|
|
|
|
/// What adaptor can tell me how to interpret/navigate nodes and
|
|
/// trees. E.g., get text of a node.
|
|
///
|
|
TreeAdaptorType* getTreeAdaptor();
|
|
|
|
/// As we flatten the tree, we use UP, DOWN nodes to represent
|
|
/// the tree structure. When debugging we need unique nodes
|
|
/// so we have to instantiate new ones. When doing normal tree
|
|
/// parsing, it's slow and a waste of memory to create unique
|
|
/// navigation nodes. Default should be false;
|
|
///
|
|
void set_uniqueNavigationNodes(bool uniqueNavigationNodes);
|
|
|
|
StringType toString();
|
|
|
|
/// Return the text of all nodes from start to stop, inclusive.
|
|
/// If the stream does not buffer all the nodes then it can still
|
|
/// walk recursively from start until stop. You can always return
|
|
/// null or "" too, but users should not access $ruleLabel.text in
|
|
/// an action of course in that case.
|
|
///
|
|
StringType toStringSS(TreeType* start, TreeType* stop);
|
|
|
|
/// Return the text of all nodes from start to stop, inclusive, into the
|
|
/// supplied buffer.
|
|
/// If the stream does not buffer all the nodes then it can still
|
|
/// walk recursively from start until stop. You can always return
|
|
/// null or "" too, but users should not access $ruleLabel.text in
|
|
/// an action of course in that case.
|
|
///
|
|
void toStringWork(TreeType* start, TreeType* stop, StringType& buf);
|
|
|
|
/// Get a tree node at an absolute index i; 0..n-1.
|
|
/// If you don't want to buffer up nodes, then this method makes no
|
|
/// sense for you.
|
|
///
|
|
TreeType* get(ANTLR_INT32 i);
|
|
|
|
// REWRITING TREES (used by tree parser)
|
|
|
|
/// Replace from start to stop child index of parent with t, which might
|
|
/// be a list. Number of children may be different
|
|
/// after this call. The stream is notified because it is walking the
|
|
/// tree and might need to know you are monkeying with the underlying
|
|
/// tree. Also, it might be able to modify the node stream to avoid
|
|
/// restreaming for future phases.
|
|
///
|
|
/// If parent is null, don't do anything; must be at root of overall tree.
|
|
/// Can't replace whatever points to the parent externally. Do nothing.
|
|
///
|
|
void replaceChildren(TreeType* parent, ANTLR_INT32 startChildIndex,
|
|
ANTLR_INT32 stopChildIndex, TreeType* t);
|
|
|
|
TreeType* LB(ANTLR_INT32 k);
|
|
|
|
/// As we flatten the tree, we use UP, DOWN nodes to represent
|
|
/// the tree structure. When debugging we need unique nodes
|
|
/// so instantiate new ones when uniqueNavigationNodes is true.
|
|
///
|
|
void addNavigationNode(ANTLR_UINT32 ttype);
|
|
|
|
TreeType* newDownNode();
|
|
|
|
TreeType* newUpNode();
|
|
|
|
bool hasUniqueNavigationNodes() const;
|
|
|
|
ANTLR_UINT32 getLookaheadSize();
|
|
|
|
void push(ANTLR_INT32 index);
|
|
|
|
ANTLR_INT32 pop();
|
|
|
|
void reset();
|
|
|
|
void fillBufferRoot();
|
|
void fillBuffer(TreeType* t);
|
|
|
|
};
|
|
|
|
/** This structure is used to save the state information in the treenodestream
|
|
* when walking ahead with cyclic DFA or for syntactic predicates,
|
|
* we need to record the state of the tree node stream. This
|
|
* class wraps up the current state of the CommonTreeNodeStream.
|
|
* Calling mark() will push another of these on the markers stack.
|
|
*/
|
|
template<class ImplTraits>
|
|
class TreeWalkState : public ImplTraits::AllocPolicyType
|
|
{
|
|
public:
|
|
typedef typename ImplTraits::TreeType TreeType;
|
|
|
|
private:
|
|
ANTLR_UINT32 m_currentChildIndex;
|
|
ANTLR_MARKER m_absoluteNodeIndex;
|
|
TreeType* m_currentNode;
|
|
TreeType* m_previousNode;
|
|
ANTLR_UINT32 m_nodeStackSize;
|
|
TreeType* m_lookAhead;
|
|
ANTLR_UINT32 m_lookAheadLength;
|
|
ANTLR_UINT32 m_tail;
|
|
ANTLR_UINT32 m_head;
|
|
|
|
|
|
};
|
|
|
|
ANTLR_END_NAMESPACE()
|
|
|
|
#include "antlr3commontreenodestream.inl"
|
|
|
|
#endif
|