path: root/src/iter.c

/*
 *  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>
#include "internal.h"

#define true 1
#define false 0

void colm_init_list_iter( GenericIter *listIter, Tree **stackRoot,
		long argSize, long rootSize, const Ref *rootRef, int genericId )
{
	listIter->type = IT_Tree;
	listIter->rootRef = *rootRef;
	listIter->stackRoot = stackRoot;
	listIter->yieldSize = 0;
	listIter->rootSize = rootSize;
	listIter->ref.kid = 0;
	listIter->ref.next = 0;
	listIter->argSize = argSize;
	listIter->genericId = genericId;
}

void colm_list_iter_destroy( Program *prg, Tree ***psp, GenericIter *iter )
{
	if ( (int)iter->type != 0 ) {
		int i;
		Tree **sp = *psp;
		long curStackSize = vm_ssize() - iter->rootSize;
		assert( iter->yieldSize == curStackSize );
		vm_popn( iter->yieldSize );
		for ( i = 0; i < iter->argSize; i++ )
			treeDownref( prg, sp, vm_pop_tree() );
		iter->type = 0;
		*psp = sp;
	}
}

Tree *colm_list_iter_advance( Program *prg, Tree ***psp, GenericIter *iter )
{
	Tree **sp = *psp;
	assert( iter->yieldSize == (vm_ssize() - iter->rootSize) );

	if ( iter->ref.kid == 0 ) {
		/* Kid is zero, start from the root. */
		List *list = *((List**)iter->rootRef.kid);
		iter->ref.kid = (Kid*)list->head;
		iter->ref.next = 0;

		//= iter->rootRef;
		//iter
		//iterFind( prg, psp, iter, true );
	}
	else {
		/* Have a previous item, continue searching from there. */
		//iterFind( prg, psp, iter, false );

		ListEl *listEl = (ListEl*)iter->ref.kid;
		listEl = listEl->list_next;
		iter->ref.kid = (Kid*)listEl;
		iter->ref.next = 0;
	}

	sp = *psp;
	iter->yieldSize = vm_ssize() - iter->rootSize;

	return (iter->ref.kid ? prg->trueVal : prg->falseVal );
}

Tree *colm_map_iter_advance( Program *prg, Tree ***psp, GenericIter *iter )
{
	Tree **sp = *psp;
	assert( iter->yieldSize == (vm_ssize() - iter->rootSize) );

	if ( iter->ref.kid == 0 ) {
		/* Kid is zero, start from the root. */
		Map *map = *((Map**)iter->rootRef.kid);
		iter->ref.kid = (Kid*)map->head;
		iter->ref.next = 0;

		//= iter->rootRef;
		//iter
		//iterFind( prg, psp, iter, true );
	}
	else {
		/* Have a previous item, continue searching from there. */
		//iterFind( prg, psp, iter, false );

		MapEl *mapEl = (MapEl*)iter->ref.kid;
		mapEl = mapEl->next;
		iter->ref.kid = (Kid*)mapEl;
		iter->ref.next = 0;
	}

	sp = *psp;
	iter->yieldSize = vm_ssize() - iter->rootSize;

	return (iter->ref.kid ? prg->trueVal : prg->falseVal );
}

Tree *colm_list_iter_deref_cur( Program *prg, GenericIter *iter )
{
	struct generic_info *gi = &prg->rtd->genericInfo[iter->genericId];
	ListEl *el = (ListEl*)iter->ref.kid;
	struct colm_struct *s = el != 0 ?
			colm_struct_container( el, gi->elOffset ) : 0;
	return (Tree*)s;
}

Value colm_viter_deref_cur( Program *prg, GenericIter *iter )
{
	struct generic_info *gi = &prg->rtd->genericInfo[iter->genericId];
	ListEl *el = (ListEl*)iter->ref.kid;
	struct colm_struct *s = el != 0 ?
			colm_struct_container( el, gi->elOffset ) : 0;

	Value value = colm_struct_get_field( s, Value, 0 );
	if ( gi->valueType == TYPE_TREE )
		treeUpref( (Tree*)value );

	return value;
}

void colm_init_tree_iter( TreeIter *treeIter, Tree **stackRoot,
		long argSize, long rootSize,
		const Ref *rootRef, int searchId )
{
	treeIter->type = IT_Tree;
	treeIter->rootRef = *rootRef;
	treeIter->searchId = searchId;
	treeIter->stackRoot = stackRoot;
	treeIter->yieldSize = 0;
	treeIter->rootSize = rootSize;
	treeIter->ref.kid = 0;
	treeIter->ref.next = 0;
	treeIter->argSize = argSize;
}

void colm_init_rev_tree_iter( RevTreeIter *revTriter, Tree **stackRoot,
		long argSize, long rootSize,
		const Ref *rootRef, int searchId, int children )
{
	revTriter->type = IT_RevTree;
	revTriter->rootRef = *rootRef;
	revTriter->searchId = searchId;
	revTriter->stackRoot = stackRoot;
	revTriter->yieldSize = children;
	revTriter->rootSize = rootSize;
	revTriter->kidAtYield = 0;
	revTriter->children = children;
	revTriter->ref.kid = 0;
	revTriter->ref.next = 0;
	revTriter->argSize = argSize;
}

void initUserIter( UserIter *userIter, Tree **stackRoot, long rootSize,
		long argSize, long searchId )
{
	userIter->type = IT_User;
	userIter->stackRoot = stackRoot;
	userIter->argSize = argSize;
	userIter->yieldSize = 0;
	userIter->rootSize = rootSize;
	userIter->resume = 0;
	userIter->frame = 0;
	userIter->searchId = searchId;

	userIter->ref.kid = 0;
	userIter->ref.next = 0;
}


UserIter *colm_uiter_create( Program *prg, Tree ***psp, struct function_info *fi, long searchId )
{
	Tree **sp = *psp;

	vm_pushn( sizeof(UserIter) / sizeof(Word) );
	void *mem = vm_ptop();
	UserIter *uiter = mem;

	Tree **stackRoot = vm_ptop();
	long rootSize = vm_ssize();

	initUserIter( uiter, stackRoot, rootSize, fi->argSize, searchId );

	*psp = sp;
	return uiter;
}

void uiterInit( Program *prg, Tree **sp, UserIter *uiter, 
		struct function_info *fi, int revertOn )
{
	/* Set up the first yeild so when we resume it starts at the beginning. */
	uiter->ref.kid = 0;
	uiter->yieldSize = vm_ssize() - uiter->rootSize;
	//	uiter->frame = &uiter->stackRoot[-IFR_AA];

	if ( revertOn )
		uiter->resume = prg->rtd->frameInfo[fi->frameId].codeWV;
	else
		uiter->resume = prg->rtd->frameInfo[fi->frameId].codeWC;
}


void colm_tree_iter_destroy( Program *prg, Tree ***psp, TreeIter *iter )
{
	if ( (int)iter->type != 0 ) {
		int i;
		Tree **sp = *psp;
		long curStackSize = vm_ssize() - iter->rootSize;
		assert( iter->yieldSize == curStackSize );
		vm_popn( iter->yieldSize );
		for ( i = 0; i < iter->argSize; i++ )
			treeDownref( prg, sp, vm_pop_tree() );
		iter->type = 0;
		*psp = sp;
	}
}

void colm_rev_tree_iter_destroy( struct colm_program *prg, Tree ***psp, RevTreeIter *riter )
{
	if ( (int)riter->type != 0 ) {
		int i;
		Tree **sp = *psp;
		long curStackSize = vm_ssize() - riter->rootSize;
		assert( riter->yieldSize == curStackSize );
		vm_popn( riter->yieldSize );
		for ( i = 0; i < riter->argSize; i++ )
			treeDownref( prg, sp, vm_pop_tree() );
		riter->type = 0;
		*psp = sp;
	}
}

void colm_uiter_destroy( Program *prg, Tree ***psp, UserIter *uiter )
{
	if ( uiter != 0 && (int)uiter->type != 0 ) {
		Tree **sp = *psp;

		/* We should always be coming from a yield. The current stack size will be
		 * nonzero and the stack size in the iterator will be correct. */
		long curStackSize = vm_ssize() - uiter->rootSize;
		assert( uiter->yieldSize == curStackSize );

		vm_popn( uiter->yieldSize );
		vm_popn( sizeof(UserIter) / sizeof(Word) );

		uiter->type = 0;

		*psp = sp;
	}
}

void colm_uiter_unwind( Program *prg, Tree ***psp, UserIter *uiter )
{
	if ( uiter != 0 && (int)uiter->type != 0 ) {
		Tree **sp = *psp;

		/* We should always be coming from a yield. The current stack size will be
		 * nonzero and the stack size in the iterator will be correct. */
		long curStackSize = vm_ssize() - uiter->rootSize;
		assert( uiter->yieldSize == curStackSize );

		long argSize = uiter->argSize;

		vm_popn( uiter->yieldSize );
		vm_popn( sizeof(UserIter) / sizeof(Word) );

		/* The IN_PREP_ARGS stack data. */
		vm_popn( argSize );
		vm_pop_value();

		uiter->type = 0;

		*psp = sp;
	}
}

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_ref( iter->ref.next );
			vm_push_kid( 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 = vm_pop_kid();
			iter->ref.next = vm_pop_ref();
		}
	}

	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_ref( iter->rootRef.next );
			vm_push_kid( 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_kid( 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_ref( iter->ref.next );
				vm_push_kid( 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 = vm_pop_kid();
				iter->ref.next = vm_pop_ref();
			}
		}
	}

	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_ref( iter->ref.next );
				vm_push_kid( 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 = vm_pop_kid();
			iter->ref.next = vm_pop_ref();
		}
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 );
}