movement of code from tree.c to iter.c

1 files changed, 339 insertions, 1 deletions

diff --git a/src/iter.c b/src/iter.c
index ac877be6..3d38fa3a 100644
--- a/src/iter.c
+++ b/src/iter.c
@@ -1,9 +1,32 @@
+/*
+ *  Copyright 2007-2014 Adrian Thurston <thurston@complang.org>
+ */
+
+/*  This file is part of Colm.
+ *
+ *  Colm is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ * 
+ *  Colm is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ * 
+ *  You should have received a copy of the GNU General Public License
+ *  along with Colm; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
+ */
+
 #include <colm/tree.h>
 #include <colm/bytecode.h>
 #include <colm/program.h>
-
 #include <assert.h>
 
+#define true 1
+#define false 0
+
 void initTreeIter( TreeIter *treeIter, Tree **stackRoot, long rootSize,
 		const Ref *rootRef, int searchId )
 {
@@ -149,3 +172,318 @@ void userIterDestroy2( Program *prg, Tree ***psp, UserIter *uiter )
 	}
 }
 
+Tree *treeIterDerefCur( TreeIter *iter )
+{
+	return iter->ref.kid == 0 ? 0 : iter->ref.kid->tree;
+}
+
+void setTriterCur( Program *prg, TreeIter *iter, Tree *tree )
+{
+	iter->ref.kid->tree = tree;
+}
+
+void setUiterCur( Program *prg, UserIter *uiter, Tree *tree )
+{
+	uiter->ref.kid->tree = tree;
+}
+
+void splitIterCur( Program *prg, Tree ***psp, TreeIter *iter )
+{
+	if ( iter->ref.kid == 0 )
+		return;
+	
+	splitRef( prg, psp, &iter->ref );
+}
+
+void iterFind( Program *prg, Tree ***psp, TreeIter *iter, int tryFirst )
+{
+	int anyTree = iter->searchId == prg->rtd->anyId;
+	Tree **top = iter->stackRoot;
+	Kid *child;
+	Tree **sp = *psp;
+
+rec_call:
+	if ( tryFirst && ( iter->ref.kid->tree->id == iter->searchId || anyTree ) ) {
+		*psp = sp;
+		return;
+	}
+	else {
+		child = treeChild( prg, iter->ref.kid->tree );
+		if ( child != 0 ) {
+			vm_contiguous( 2 );
+			vm_push( (SW) iter->ref.next );
+			vm_push( (SW) iter->ref.kid );
+			iter->ref.kid = child;
+			iter->ref.next = (Ref*)vm_ptop();
+			while ( iter->ref.kid != 0 ) {
+				tryFirst = true;
+				goto rec_call;
+				rec_return:
+				iter->ref.kid = iter->ref.kid->next;
+			}
+			iter->ref.kid = (Kid*)vm_pop();
+			iter->ref.next = (Ref*)vm_pop();
+		}
+	}
+
+	if ( top != vm_ptop() )
+		goto rec_return;
+	
+	iter->ref.kid = 0;
+	*psp = sp;
+}
+
+Tree *treeIterAdvance( Program *prg, Tree ***psp, TreeIter *iter )
+{
+	Tree **sp = *psp;
+	assert( iter->yieldSize == (vm_ssize() - iter->rootSize) );
+
+	if ( iter->ref.kid == 0 ) {
+		/* Kid is zero, start from the root. */
+		iter->ref = iter->rootRef;
+		iterFind( prg, psp, iter, true );
+	}
+	else {
+		/* Have a previous item, continue searching from there. */
+		iterFind( prg, psp, iter, false );
+	}
+
+	sp = *psp;
+	iter->yieldSize = vm_ssize() - iter->rootSize;
+
+	return (iter->ref.kid ? prg->trueVal : prg->falseVal );
+}
+
+Tree *treeIterNextChild( Program *prg, Tree ***psp, TreeIter *iter )
+{
+	Tree **sp = *psp;
+	assert( iter->yieldSize == (vm_ssize() - iter->rootSize) );
+	Kid *kid = 0;
+
+	if ( iter->ref.kid == 0 ) {
+		/* Kid is zero, start from the first child. */
+		Kid *child = treeChild( prg, iter->rootRef.kid->tree );
+
+		if ( child == 0 )
+			iter->ref.next = 0;
+		else {
+			/* Make a reference to the root. */
+			vm_contiguous( 2 );
+			vm_push( (SW) iter->rootRef.next );
+			vm_push( (SW) iter->rootRef.kid );
+			iter->ref.next = (Ref*)vm_ptop();
+
+			kid = child;
+		}
+	}
+	else {
+		/* Start at next. */
+		kid = iter->ref.kid->next;
+	}
+
+	if ( iter->searchId != prg->rtd->anyId ) {
+		/* Have a previous item, go to the next sibling. */
+		while ( kid != 0 && kid->tree->id != iter->searchId )
+			kid = kid->next;
+	}
+
+	iter->ref.kid = kid;
+	iter->yieldSize = vm_ssize() - iter->rootSize;
+	*psp = sp;
+	return ( iter->ref.kid ? prg->trueVal : prg->falseVal );
+}
+
+Tree *treeRevIterPrevChild( Program *prg, Tree ***psp, RevTreeIter *iter )
+{
+	Tree **sp = *psp;
+	assert( iter->yieldSize == ( vm_ssize() - iter->rootSize ) );
+
+	if ( iter->kidAtYield != iter->ref.kid ) {
+		/* Need to reload the kids. */
+		vm_popn( iter->children );
+
+		int c;
+		Kid *kid = treeChild( prg, iter->rootRef.kid->tree );
+		for ( c = 0; c < iter->children; c++ ) {
+			vm_push( (SW)kid );
+			kid = kid->next;
+		}
+	}
+
+	if ( iter->ref.kid != 0 ) {
+		vm_pop_ignore();
+		iter->children -= 1;
+	}
+
+	if ( iter->searchId != prg->rtd->anyId ) {
+		/* Have a previous item, go to the next sibling. */
+		while ( iter->children > 0 && ((Kid*)(vm_top()))->tree->id != iter->searchId ) {
+			iter->children -= 1;
+			vm_pop_ignore();
+		}
+	}
+
+	if ( iter->children == 0 ) {
+		iter->ref.next = 0;
+		iter->ref.kid = 0;
+	}
+	else {
+		iter->ref.next = &iter->rootRef;
+		iter->ref.kid = (Kid*)vm_top();
+	}
+
+	/* We will use this to detect a split above the iterated tree. */
+	iter->kidAtYield = iter->ref.kid;
+
+	iter->yieldSize = vm_ssize() - iter->rootSize;
+
+	*psp = sp;
+
+	return (iter->ref.kid ? prg->trueVal : prg->falseVal );
+}
+
+void iterFindRepeat( Program *prg, Tree ***psp, TreeIter *iter, int tryFirst )
+{
+	Tree **sp = *psp;
+	int anyTree = iter->searchId == prg->rtd->anyId;
+	Tree **top = iter->stackRoot;
+	Kid *child;
+
+rec_call:
+	if ( tryFirst && ( iter->ref.kid->tree->id == iter->searchId || anyTree ) ) {
+		*psp = sp;
+		return;
+	}
+	else {
+		/* The repeat iterator is just like the normal top-down-left-right,
+		 * execept it only goes into the children of a node if the node is the
+		 * root of the iteration, or if does not have any neighbours to the
+		 * right. */
+		if ( top == vm_ptop() || iter->ref.kid->next == 0  ) {
+			child = treeChild( prg, iter->ref.kid->tree );
+			if ( child != 0 ) {
+				vm_contiguous( 2 );
+				vm_push( (SW) iter->ref.next );
+				vm_push( (SW) iter->ref.kid );
+				iter->ref.kid = child;
+				iter->ref.next = (Ref*)vm_ptop();
+				while ( iter->ref.kid != 0 ) {
+					tryFirst = true;
+					goto rec_call;
+					rec_return:
+					iter->ref.kid = iter->ref.kid->next;
+				}
+				iter->ref.kid = (Kid*)vm_pop();
+				iter->ref.next = (Ref*)vm_pop();
+			}
+		}
+	}
+
+	if ( top != vm_ptop() )
+		goto rec_return;
+	
+	iter->ref.kid = 0;
+	*psp = sp;
+}
+
+Tree *treeIterNextRepeat( Program *prg, Tree ***psp, TreeIter *iter )
+{
+	Tree **sp = *psp;
+	assert( iter->yieldSize == ( vm_ssize() - iter->rootSize ) );
+
+	if ( iter->ref.kid == 0 ) {
+		/* Kid is zero, start from the root. */
+		iter->ref = iter->rootRef;
+		iterFindRepeat( prg, psp, iter, true );
+	}
+	else {
+		/* Have a previous item, continue searching from there. */
+		iterFindRepeat( prg, psp, iter, false );
+	}
+
+	sp = *psp;
+	iter->yieldSize = vm_ssize() - iter->rootSize;
+
+	return (iter->ref.kid ? prg->trueVal : prg->falseVal );
+}
+
+void iterFindRevRepeat( Program *prg, Tree ***psp, TreeIter *iter, int tryFirst )
+{
+	Tree **sp = *psp;
+	int anyTree = iter->searchId == prg->rtd->anyId;
+	Tree **top = iter->stackRoot;
+	Kid *child;
+
+	if ( tryFirst ) {
+		while ( true ) {
+			if ( top == vm_ptop() || iter->ref.kid->next == 0 ) {
+				child = treeChild( prg, iter->ref.kid->tree );
+
+				if ( child == 0 )
+					break;
+				vm_contiguous( 2 );
+				vm_push( (SW) iter->ref.next );
+				vm_push( (SW) iter->ref.kid );
+				iter->ref.kid = child;
+				iter->ref.next = (Ref*)vm_ptop();
+			}
+			else {
+				/* Not the top and not there is a next, go over to it. */
+				iter->ref.kid = iter->ref.kid->next;
+			}
+		}
+
+		goto first;
+	}
+
+	while ( true ) {
+		if ( top == vm_ptop() ) {
+			iter->ref.kid = 0;
+			return;
+		}
+		
+		if ( iter->ref.kid->next == 0 ) {
+			/* Go up one and then down. Remember we can't use iter->ref.next
+			 * because the chain may have been split, setting it null (to
+			 * prevent repeated walks up). */
+			Ref *ref = (Ref*)vm_ptop();
+			iter->ref.kid = treeChild( prg, ref->kid->tree );
+		}
+		else {
+			iter->ref.kid = (Kid*)vm_pop();
+			iter->ref.next = (Ref*)vm_pop();
+		}
+first:
+		if ( iter->ref.kid->tree->id == iter->searchId || anyTree ) {
+			*psp = sp;
+			return;
+		}
+	}
+	*psp = sp;
+	return;
+}
+
+
+Tree *treeIterPrevRepeat( Program *prg, Tree ***psp, TreeIter *iter )
+{
+	Tree **sp = *psp;
+	assert( iter->yieldSize == (vm_ssize() - iter->rootSize) );
+
+	if ( iter->ref.kid == 0 ) {
+		/* Kid is zero, start from the root. */
+		iter->ref = iter->rootRef;
+		iterFindRevRepeat( prg, psp, iter, true );
+	}
+	else {
+		/* Have a previous item, continue searching from there. */
+		iterFindRevRepeat( prg, psp, iter, false );
+	}
+
+	sp = *psp;
+	iter->yieldSize = vm_ssize() - iter->rootSize;
+
+	return (iter->ref.kid ? prg->trueVal : prg->falseVal );
+}
+
+
+