antlr3commontreenodestream.c

ANTLR(ANother Tool for Language Recognition)它是这样的一种工具

static	void		    
release	(pANTLR3_INT_STREAM is, ANTLR3_UINT64 marker)
{
    fprintf(stderr, "Cannot release a tree parse\n");
}

/** Rewind the current state of the tree walk to the state it
 *  was in when mark() was called and it returned marker.  Also,
 *  wipe out the lookahead which will force reloading a few nodes
 *  but it is better than making a copy of the lookahead buffer
 *  upon mark().
 */
static	void		    
rewindMark	    (pANTLR3_INT_STREAM is, ANTLR3_UINT64 marker)
{
    pANTLR3_TREE_NODE_STREAM		tns;
    pANTLR3_COMMON_TREE_NODE_STREAM	ctns;
    pANTLR3_TREE_WALK_STATE		state;
    ANTLR3_UINT64			m;

    tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    ctns    = tns->ctns;

    if	(ctns->markers == NULL || ctns->markers->size(ctns->markers) < marker)
    {
	return;	    /* No such marker - do nothing */
    }

    /* Retrieve the marker at the specified mark
     */
    state   = (pANTLR3_TREE_WALK_STATE) ctns->markers->get(ctns->markers, marker);

    /* Now reset the current state
     */
    ctns->absoluteNodeIndex	= state->absoluteNodeIndex;
    ctns->currentChildIndex	= state->currentChildIndex;
    ctns->currentNode		= state->currentNode;
    ctns->previousNode		= state->previousNode;

    /* Drop the current node stack back to the size it was when 
     * we set the mark.
     */
    for	(m = ctns->nodeStack->size(ctns->nodeStack); m > state->nodeStackSize; m--)
    {
	ctns->nodeStack->pop(ctns->nodeStack);
    }

    /* Now we can throw away the current look ahead stack (because we allocated a new one
     * when we mark()ed this, and reinstate the one we saved.
     */
    ANTLR3_FREE(ctns->lookAhead);
    ctns->lookAheadLength   = state->lookAheadLength;
    ctns->head		    = state->head;
    ctns->tail		    = state->tail;
    ctns->lookAhead	    = state->lookAhead;

    /* We now need to remove any markers that were added after this marker and
     * this marker itself. The remove will cuase any space allocated to be returned
     * to the system.
     */
    for	(m = ctns->markers->size(ctns->markers); m >= marker; m--)
    {
	ctns->markers->remove(ctns->markers, m);
    }
}

static	void		    
rewindLast	(pANTLR3_INT_STREAM is)
{
   is->rewind(is, is->lastMarker);
}

/** consume() ahead until we hit index.  Can't just jump ahead--must
 *  spit out the navigation nodes.
 */
static	void		    
seek	(pANTLR3_INT_STREAM is, ANTLR3_UINT64 index)
{
    pANTLR3_TREE_NODE_STREAM		tns;
    pANTLR3_COMMON_TREE_NODE_STREAM	ctns;

    tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    ctns    = tns->ctns;

    /* Check for trying to seek in reverse
     */
    if	((ANTLR3_INT64)index < is->index(is))
    {
	fprintf(stderr, "Can't seek backwards in a node stream\n");
    }

    /* Seek forwards, so we consume nodes until we arrive at the
     * index.
     */
    while   (is->index(is) < (ANTLR3_INT64)index)
    {
	is->consume(is);
    }
}

static	ANTLR3_INT64		    
tindex	(pANTLR3_INT_STREAM is)
{
    pANTLR3_TREE_NODE_STREAM		tns;
    pANTLR3_COMMON_TREE_NODE_STREAM	ctns;

    tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    ctns    = tns->ctns;

    return ctns->absoluteNodeIndex + 1;
}

/** Expensive to compute the size of the whole tree while parsing.
 *  This method only returns how much input has been seen so far.  So
 *  after parsing it returns true size.
 */
static	ANTLR3_UINT64		    
size	(pANTLR3_INT_STREAM is)
{
    pANTLR3_TREE_NODE_STREAM		tns;
    pANTLR3_COMMON_TREE_NODE_STREAM	ctns;

    tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    ctns    = tns->ctns;

    return ctns->absoluteNodeIndex + 1;
}

static	ANTLR3_BOOLEAN	    
hasNext	(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    return (ctns->currentNode != NULL);
}

/** Return the next node found during a depth-first walk of root.
 *  Also, add these nodes and DOWN/UP imaginary nodes into the lokoahead
 *  buffer as a side-effect.  Normally side-effects are bad, but because
 *  we can emit many tokens for every next() call, it's pretty hard to
 *  use a single return value for that.  We must add these tokens to
 *  the lookahead buffer.
 *
 *  This does *not* return the DOWN/UP nodes; those are only returned
 *  by the LT() method.
 *
 *  Ugh.  This mechanism is much more complicated than a recursive
 *  solution, but it's the only way to provide nodes on-demand instead
 *  of walking once completely through and buffering up the nodes. :(
 */
static	pANTLR3_BASE_TREE	    
next	(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    /* Already walked the tree?
     */
    if	(ctns->currentNode == NULL)
    {
	ctns->addLookahead(ctns, &(ctns->EOF_NODE.baseTree));
	return	NULL;
    }

    /* Initial conditions? (First time this has been called)
     */
    if	(ctns->currentChildIndex == -1)
    {
	return ctns->handleRootnode(ctns);
    }

    /* Index is in the child list?
     */
    if	(ctns->currentChildIndex < (ANTLR3_INT64)(ctns->currentNode->getChildCount(ctns->currentNode)) )
    {
	return	ctns->visitChild(ctns, ctns->currentChildIndex);
    }

    /* We must have hit the end of the child list, so we return to the
     * parent node, or it's parent, or it's and so on...
     */
    ctns->walkBackToMostRecentNodeWithUnvisitedChildren(ctns);

    if	(ctns->currentNode != NULL)
    {
	return ctns->visitChild(ctns, ctns->currentChildIndex);
    }

    /* Well, nothing left to do...
     */
    return  NULL;
}

static	pANTLR3_BASE_TREE	    
handleRootnode	(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    pANTLR3_BASE_TREE	node;

    /* Start with the current node in the stream
     */
    node    = ctns->currentNode;

    /* We start with the first child of the current node ready
     * to perform a next.
     */
    ctns->currentChildIndex = 0;

    if	(node->isNil(node))
    {
	/* We don;t want to count this root nil node so move on
	 */
	node	= ctns->visitChild(ctns, ctns->currentChildIndex);
    }
    else
    {
	/* Root node is not nil, so add it to lookahead and see if there are
	 * children.
	 */
	ctns->addLookahead(ctns, node);
	
	if  ( ctns->currentNode->getChildCount(ctns->currentNode) == 0)
	{
	    /* This is a single node with no children
	     */
	    ctns->currentNode = NULL;
	}
    }

    /* Return the node we arrived at one way or another.
     */
    return node;
}

/** Push the current node and descend to the child nodes.
 */
static	pANTLR3_BASE_TREE	    
visitChild	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_UINT64 child)
{
    pANTLR3_BASE_TREE	node;

    node = NULL;

    /* Save the current state of nodes. The specified child index is stored
     * so we can travese from this point after the children are all traversed.
     */
    ctns->currentNode->savedIndex = child;
    ctns->nodeStack->push(ctns->nodeStack, ctns->currentNode, NULL);

    /* Add the DOWN navigation node as we descend
     */
    if	(child == 0 && !ctns->currentNode->isNil(ctns->currentNode))
    {
	ctns->addNavigationNode(ctns, ANTLR3_TOKEN_DOWN);
    }
    
    /* Now visit the child
     */	
    ctns->currentNode		= ctns->currentNode->getChild(ctns->currentNode, child);
    ctns->currentChildIndex	= 0;
    node			= ctns->currentNode;
    ctns->addLookahead(ctns, node);

    ctns->walkBackToMostRecentNodeWithUnvisitedChildren(ctns);

    return node;
}

/** 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.
 */
static	void		    
addNavigationNode	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_UINT32 ttype)
{
    pANTLR3_BASE_TREE	    node;

    node = NULL;

    if	(ttype == ANTLR3_TOKEN_DOWN)
    {
	if  (ctns->hasUniqueNavigationNodes(ctns))
	{
	    node    = ctns->newDownNode(ctns);
	}
	else
	{
	    node    = &(ctns->DOWN.baseTree);
	}
    }
    else
    {
	if  (ctns->hasUniqueNavigationNodes(ctns))
	{
	    node    = ctns->newUpNode(ctns);
	}
	else
	{
	    node    = &(ctns->UP.baseTree);
	}
    }

    /* Now add the node we decided upon.
     */
    ctns->addLookahead(ctns, node);
}

/** Walk upwards looking for a node with more children to walk
 *  using a function with a name almost as long as this sentence
 */
static	void		    
walkBackToMostRecentNodeWithUnvisitedChildren	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    while   (	    (ctns->currentNode != NULL)
		&&  ctns->currentChildIndex >= (ANTLR3_INT64)(ctns->currentNode->getChildCount(ctns->currentNode))
	    )
    {
	ctns->currentNode	= (pANTLR3_BASE_TREE) (ctns->nodeStack->top);
	ctns->nodeStack->pop(ctns->nodeStack);		/* Remove top element now */

	/* Move to the next child after the one the we just traversed. The index of the one we just traversed
	 * was stored in the current node we saved upon our stack.
	 */
	ctns->currentChildIndex	= ctns->currentNode->savedIndex + 1;

	if  (ctns->currentChildIndex >= (ANTLR3_INT64)(ctns->currentNode->getChildCount(ctns->currentNode)) )
	{
	    if	( ! ctns->currentNode->isNil(ctns->currentNode) )
	    {
		ctns->addNavigationNode(ctns, ANTLR3_TOKEN_UP);
	    }

	    /* Are we there yet?
	     */
	    if	(ctns->currentNode == ctns->root)
	    {
		/* We arrived all the way back at the root node, so our depth first walk
		 * must be finished.
		 */
		ctns->currentNode   = NULL;
	    }
	}
    }
}

static	pANTLR3_BASE_TREE_ADAPTOR			    
getTreeAdaptor	(pANTLR3_TREE_NODE_STREAM tns)
{
    return  tns->ctns->adaptor;
}

static	ANTLR3_BOOLEAN	    
hasUniqueNavigationNodes	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    return  ctns->uniqueNavigationNodes;
}

static	void		    
setUniqueNavigationNodes	    (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_BOOLEAN uniqueNavigationNodes)
{
    tns->ctns->uniqueNavigationNodes = uniqueNavigationNodes;
}

/** Using the Iterator interface, return a list of all the token types
 *  as text.  Used for testing.
 */
static	pANTLR3_STRING	    
toNodesOnlyString	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    pANTLR3_STRING  buf;

    buf = ctns->stringFactory->newRaw(ctns->stringFactory);

    while   (ctns->hasNext(ctns))
    {
	pANTLR3_BASE_TREE   t;

	t = ctns->next(ctns);

	buf->append8(buf, " ");
	buf->addi   (buf, t->getType(t));
    }

    return  buf;
}

/** Print out the entire tree including DOWN/UP nodes.  Uses
 *  a recursive walk.  Mostly useful for testing as it yields
 *  the token types not text.
 */
static	pANTLR3_STRING	    
toString	    (pANTLR3_TREE_NODE_STREAM tns)
{
    return  tns->toStringSS(tns, tns->ctns->root, NULL);
}

static	pANTLR3_STRING	    
toStringSS	    (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop)
{
    pANTLR3_STRING  buf;

    buf = tns->ctns->stringFactory->newRaw(tns->ctns->stringFactory);

    tns->toStringWork(tns, start, stop, buf);

    return  buf;
}

static	void	    
toStringWork	(pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE p, pANTLR3_BASE_TREE stop, pANTLR3_STRING buf)
{

    ANTLR3_UINT64   n;
    ANTLR3_UINT64   c;

    if	(!p->isNil(p) )
    {
	pANTLR3_STRING	text;

	text	= p->toString(p);

	if  (text == NULL)
	{
	    text = tns->ctns->stringFactory->newRaw(tns->ctns->stringFactory);

	    text->addc	(text, ' ');
	    text->addi	(text, p->getType(p));
	}

	buf->appendS(buf, text);
    }

    if	(p == stop)
    {
	return;		/* Finished */
    }

    n = p->getChildCount(p);

    if	(n > 0 && ! p->isNil(p) )
    {
	buf->addc   (buf, ' ');
	buf->addi   (buf, ANTLR3_TOKEN_DOWN);
    }

    for	(c = 0; c<n ; c++)
    {
	pANTLR3_BASE_TREE   child;

	child = p->getChild(p, c);
	tns->toStringWork(tns, child, stop, buf);
    }

    if	(n > 0 && ! p->isNil(p) )
    {
	buf->addc   (buf, ' ');
	buf->addi   (buf, ANTLR3_TOKEN_UP);
    }
}

static	ANTLR3_UINT32	    
getLookaheadSize	(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    return	ctns->tail < ctns->head 
	    ?	(ctns->lookAheadLength - ctns->head + ctns->tail)
	    :	(ctns->tail - ctns->head);
}

static	pANTLR3_BASE_TREE	    
newDownNode		(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    pANTLR3_COMMON_TREE	    dNode;
    pANTLR3_COMMON_TOKEN    token;

    token	= antlr3CommonTokenNew(ANTLR3_TOKEN_DOWN);
    token->text	= ctns->stringFactory->newPtr(ctns->stringFactory, (pANTLR3_UINT8)"DOWN", 4);
    dNode	= antlr3CommonTreeNewFromToken(token);

    return  &(dNode->baseTree);
}

static	pANTLR3_BASE_TREE	    
newUpNode		(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
{
    pANTLR3_COMMON_TREE	    uNode;
    pANTLR3_COMMON_TOKEN    token;

    token	= antlr3CommonTokenNew(ANTLR3_TOKEN_UP);
    token->text	= ctns->stringFactory->newPtr(ctns->stringFactory, (pANTLR3_UINT8)"UP", 2);
    uNode	= antlr3CommonTreeNewFromToken(token);

    return  &(uNode->baseTree);
}