package edu.neu.ccs.demeter.dj;

import edu.neu.ccs.demeter.aplib.EdgeI;
import edu.neu.ccs.demeter.aplib.NoSuchClassGraphNodeException;

import java.util.*;
import java.lang.reflect.*;

/** A subgraph of an object graph, rooted at the object graph's root,
    determined by a strategy. */
public class ObjectGraphSlice {
  protected Traversal tg;
  protected ObjectGraph og;
  protected Object root;
  protected Traversal.NodeSet startSet;
  public boolean debug;
  /** The subgraph of o determined by t. */
  public ObjectGraphSlice(ObjectGraph o, Traversal t) {
    if (o.getClassGraph() != t.getClassGraph())
      throw new IncompatibleClassGraphsException(o, t);
    tg = t;
    og = o;
    root = o.getRoot();
    // FIXME: should either disallow root == null,
    // or handle it in Traverser.traverse()
    startSet = getStartSet(root.getClass());
    if (startSet == null)
      throw new TraversalSourceException(root, tg);
  }
  /** The subgraph of the object graph rooted at o determined by t. */
  public ObjectGraphSlice(Object o, Traversal t)
  { this(new ObjectGraph(o, (ClassGraph) t.getClassGraph()), t); }
  /** The subgraph of o determined by s. */
  public ObjectGraphSlice(ObjectGraph o, Strategy s)
    throws TraversalException
  { this(o, new Traversal(s, o.getClassGraph())); }
  /** The subgraph of o determined by strategy s. */
  public ObjectGraphSlice(ObjectGraph o, String s)
    throws TraversalException
  { this(o, new Strategy(s)); }

  /** The traversal that determines the slice. */
  public Traversal getTraversal() { return tg; }

  /** The object graph that this is a slice of. */
  public ObjectGraph getObjectGraph() { return og; }

  /** The root of the object graph slice. */
  public Object getRoot() { return root; }

  /** The class graph that the object graph slice is an instance of. */
  public ClassGraph getClassGraph() { return (ClassGraph) tg.getClassGraph(); }

  /** The strategy expression that was used to build the traversal. */
  public Strategy getStrategy() { return (Strategy) tg.getStrategy(); }

  /** Compare the traversals and roots with equals(). */
  public boolean equals(Object ogs) {
    if (ogs == this) return true;
    if (!(ogs instanceof ObjectGraphSlice)) return false;
    return (((ObjectGraphSlice) ogs).tg.equals(tg) &&
	    ((ObjectGraphSlice) ogs).root.equals(root));
  }

  /** Visit the object graph slice with <code>v</code>, returning
      <code>v.getReturnValue()</code>. */
  public Object traverse(Visitor v) {
    return traverse(new Visitor[] { v }, true);
  }

  /** Visit the object graph slice with <code>v</code>, returning
      <code>v.getReturnValue()</code>.  Traverse edges in left-to-right
      order if <code>forward</code> is true, otherwise traverse in
      right-to-left order. */
  public Object traverse(Visitor v, boolean forward) {
    return traverse(new Visitor[] { v }, forward);
  }

  /** Visit the object graph slice with the visitors in <code>v</code>,
      returning <code>v[0].getReturnValue()</code>. */
  public Object traverse(Visitor[] v) {
    return traverse(v, true);
  }

  /** Visit the object graph slice with the visitors in v, returning
      v[0].getReturnValue().  Traverse edges in left-to-right order if
      <code>forward</code> is true, otherwise traverse in right-to-left
      order. */
  public Object traverse(Visitor[] v, boolean forward) {
    for (int i = 0; i < v.length; i++) v[i].start();
    Object ret = new VisitorTraverser(v, forward).traverse(root, startSet);
    for (int i = v.length-1; i >= 0; i--) v[i].finish();
    return ret;
  }

  /** Return the target object in the object graph slice reachable by
      following the strategy.  There must be a unique path to it, or else
      a FetchException is thrown. */
  public Object fetch() throws FetchException {
    List t = getTraversal().getFinishSet();
    if (t.isEmpty()) {
      throw new FetchException("Cannot fetch without a target.");
    }
    if (t.size() > 1) {
      throw new FetchException("Cannot fetch multiple targets.");
    }

    return new Fetcher().traverse(root, startSet);
  }

  /** Return a list of all target objects in the object graph slice
      reachable by following the strategy.  Traverse the graph in
      left-to-right prefix order. */
  public List gather() { return gather(true); }

  /** Return a list of all target objects in the object graph slice
      reachable by following the strategy.  Traverse the graph in
      left-to-right prefix order if <code>forward</code> is true,
      otherwise traverse in right-to-left postfix order. */
  public List gather(boolean forward) {
    return (List) new Gatherer(forward).traverse(root, startSet);
  }

  /** A fixed-size List backed by the object graph slice.  The
      elements of the list are the target objects reachable by following
      the strategy through the graph in left-to-right prefix order.  Note
      that this list (like the List returned by {@link Arrays#asList},
      but unlike the Vector returned by {@link #gather()}) is
      write-through, i.e. modifying it will modify the underlying object
      graph, and vice versa. */
  public List asList() { return asList(true); }

  /** A fixed-size List backed by the object graph slice.  The
      elements of the list are the target objects reachable by following
      the strategy through the graph.  If <code>forward</code> is true,
      the graph is traversed in left-to-right prefix order, otherwise it
      is traversed in right-to-left postfix order.  Note that this list
      (like the List returned by {@link Arrays#asList}, but unlike the
      Vector returned by {@link #gather()}) is write-through,
      i.e. modifying it will modify the underlying object graph, and vice
      versa. */
  public List asList(boolean forward) {
    return new APCollection(forward);
  }

  // Here ends the public interface of ObjectGraphSlice.

  class MutableFlag {
    boolean flag; 
    MutableFlag(boolean f) { flag = f; }
  }

  // FIXME: explain this...
  abstract class Traverser {
    boolean forward = true;
    Traverser() { }
    Traverser(boolean f) { forward = f; }

    Object traverse(Object o, Traversal.NodeSet tokens) {
      traverseNode(o, getTokensClass(tokens), tokens,
		   false, new MutableFlag(false));
      return getReturnValue();
    }

    int nest = 0;
    void indent(Object msg) {
      for (int i = 0; i < nest; i++) System.out.print(" ");
      System.out.println(msg);
    }

    void traverseNode(Object o, Class nodeClass,
		      Traversal.NodeSet tokens,
		      boolean lastWasInheritance,
		      MutableFlag traversedCollection)
    {
      Class cl = o.getClass();
      List ancestors = null;

      if (debug) indent("object type = " + cl + ", tokens = " + tokens);

      if (cl.equals(nodeClass) ||
	  // Primitive member values get wrapped, so the class might not
	  // match the member type; however, we don't have to actually
	  // check that the wrapper is the right type, since the value
	  // of a primitive member can't be any other type anyway.
	  nodeClass.isPrimitive())
      {
	before(o, ancestors = getAncestors(nodeClass));
      }

      // FIXME: around methods?

      nest++;
      if (cl.isArray()) {
	traverseArray(o, nodeClass, tokens);
      } else {
	traverseEdges(o, nodeClass, tokens.getOutgoingEdgeSets(),
		      lastWasInheritance, traversedCollection);
      }
      nest--;

      if (ancestors != null) {
	after(o, ancestors);
      }
    }

    void before(Object o, List ancestors) {
      ListIterator it = ancestors.listIterator();
      while (it.hasNext())
	before(o, (Class) it.next());
    }

    void before(Object o, Class cl) {
      // FIXME: compare token set with finish set
      if (forward && isTargetClass(cl))
	atTarget(o, cl);
    }

    void after(Object o, List ancestors) {
      ListIterator it = ancestors.listIterator(ancestors.size());
      while (it.hasPrevious())
	after(o, (Class) it.previous());
    }

    void after(Object o, Class cl) {
      // FIXME: compare token set with finish set
      if (!forward && isTargetClass(cl))
	atTarget(o, cl);
    }

    void atTarget(Object o, Class cl) {
      if (debug) indent("at " + cl);
    }

    void traverseArray(Object o, Class cl, Traversal.NodeSet tokens) {
      int l = Array.getLength(o);
      int i = (forward ? 0 : l - 1);
      while (forward ? i < l : i >= 0) {
	traverseArrayElement(o, i, cl, tokens);
	if (forward) i++; else i--;
      }
    }

    void traverseArrayElement(Object o, int i, Class cl,
			      Traversal.NodeSet tokens)
    {
      Object target = Array.get(o, i);
      if (target != null) {
	// FIXME: repetition edge wrappers
	traverseNode(target, cl, tokens, false, new MutableFlag(false));
      }
    }

    void traverseEdges(Object o, Class cl, List edgeSets,
		       boolean lastWasInheritance,
		       MutableFlag traversedCollection) {
      // FIXME: does this traverse the edges in the "right" order?
      int i = (forward ? 0 : edgeSets.size());
      ListIterator it = edgeSets.listIterator(i);
      while (forward ? it.hasNext() : it.hasPrevious()) {
	Traversal.EdgeSet edgeTokens
	  = (Traversal.EdgeSet) (forward ? it.next() : it.previous());
	traverseEdge(o, cl, edgeTokens,
		     lastWasInheritance, traversedCollection);
      }
    }

    void traverseEdge(Object o, Class cl, Traversal.EdgeSet tokens, 
		      boolean lastWasInheritance,
		      MutableFlag traversedCollection)
    {
      Traversal.NodeSet nextTokens = tokens.getTargetNodeSet();
      Class nextClass = getTokensClass(nextTokens);
      EdgeI edge = tokens.getEdge();
      if (lastWasInheritance || o.getClass().equals(cl)) {
	if (edge.isConstructionEdge()) {
	  if (isRepetitionEdge(edge)) {
	    if (debug) indent(Traversal.edgeKey(edge));
	    traverseCollection(o, nextClass, nextTokens, traversedCollection);
	  } else {
	    if (debug) indent(Traversal.edgeKey(edge));
	    traverseConstructionEdge(o, cl, edge, nextClass, nextTokens);
	  }
	} else if (edge.isInheritanceEdge()) {
	  if (debug) indent(Traversal.edgeKey(edge));
	  traverseSuperclass(o, nextClass, nextTokens, traversedCollection);	
	}
      } else if (edge.isAlternationEdge()) {
	if (!lastWasInheritance &&   // knowledge path constraint
	    nextClass.isInstance(o)) // premature termination
	{
	  if (debug) indent(Traversal.edgeKey(edge));
	  traverseSubclass(o, nextClass, nextTokens, traversedCollection);
	}
      }
    }

    void traverseCollection(Object o, Class nextClass,
			    Traversal.NodeSet nextTokens,
			    MutableFlag traversedCollection)
    {
      if (!traversedCollection.flag) {
	// Make sure we don't traverse a collection more than once
	// due to multiple inheritance paths to the collection
	// interface.
	traversedCollection.flag = true;
	ListIterator it = getListIterator(o);
	while (forward ? it.hasNext() : it.hasPrevious())
	  traverseCollectionElement(it, forward ? it.next() : it.previous(),
				    nextClass, nextTokens, traversedCollection);
      }
    }

    void traverseCollectionElement(ListIterator it, Object o, Class cl,
				   Traversal.NodeSet tokens,
				   MutableFlag traversedCollection)
    {
      if (o != null) {
	// FIXME: repetition edge wrappers
	traverseNode(o, cl, tokens, false, traversedCollection);
      }
    }

    void traverseConstructionEdge(Object o, Class cl, EdgeI edge,
				  Class targetClass,
				  Traversal.NodeSet tokens)
    {
      Object target = getTargetObject(o, cl, edge);
      if (target != null) {
	before(o, cl, edge, target, targetClass);
	traverseNode(target, targetClass, tokens, false,
		     new MutableFlag(false));
	after(o, cl, edge, target, targetClass);
      }
    }

    void traverseSubclass(Object o, Class subclass,
			  Traversal.NodeSet tokens,
			  MutableFlag traversedCollection)
    {
      // FIXME: alternation edge wrappers
      traverseNode(o, subclass, tokens, false, traversedCollection);
    }

    void traverseSuperclass(Object o, Class superclass,
			    Traversal.NodeSet tokens,
			    MutableFlag traversedCollection)
    {
      // FIXME: inheritance edge wrappers
      traverseNode(o, superclass, tokens, true, traversedCollection);
    }

    void before(Object source, Class sourceClass, EdgeI edge,
		Object target, Class targetClass) {
    }

    void after(Object source, Class sourceClass, EdgeI edge,
	       Object target, Class targetClass) {
    }

    Object returnValue;
    Object getReturnValue() { return returnValue; }
  }

  class VisitorTraverser extends Traverser {
    Visitor visitors[];
    VisitorTraverser(Visitor v[], boolean f) {
      super(f);
      visitors = v;
    }

    void before(Object o, Class cl) {
      for (int i = 0; i < visitors.length; i++)
	visitors[i].before(o, cl);
    }

    void before(Object source, Class sourceClass, EdgeI edge,
		Object target, Class targetClass) {
      for (int i = 0; i < visitors.length; i++)
	visitors[i].before(source, sourceClass, edge, target, targetClass);
    }

    void after(Object o, Class cl) {
      for (int i = visitors.length - 1; i >= 0; i--)
	visitors[i].after(o, cl);
    }

    void after(Object source, Class sourceClass, EdgeI edge,
	       Object target, Class targetClass) {
      for (int i = visitors.length - 1; i >= 0; i--)
	visitors[i].after(source, sourceClass, edge, target, targetClass);
    }

    Object getReturnValue() { return visitors[0].getReturnValue(); }
  }

  class Fetcher extends Traverser {
    void atTarget(Object o, Class cl) {
      // if (returnValue != null)
      // throw new FetchException("Non-unique path.");
      returnValue = o;
      super.atTarget(o, cl);
    }

    void traverseArray(Object o, Class cl, Traversal.NodeSet tokens) {
      throw new FetchException("Cannot fetch through arrays: " + o.getClass());
    }

    void traverseEdges(Object o, Class cl, List edgeSets,
		       boolean lastWasInheritance,
		       MutableFlag traversedCollection)
    {
      if (edgeSets.size() > 1) {
	Iterator it = edgeSets.iterator();
	int i = 0;
	while (it.hasNext()) {
	  Traversal.EdgeSet edgeSet = (Traversal.EdgeSet) it.next();
	  if (edgeSet.getEdge().isConstructionEdge())
	    if (i++ == 1)
	      throw new FetchException("Non-unique path.");
	}
      }
      super.traverseEdges(o, cl, edgeSets,
			  lastWasInheritance, traversedCollection);
    }

    void traverseCollection(Object o, Class nextClass,
			    Traversal.NodeSet nextTokens,
			    MutableFlag traversedCollection)
    {
      throw new FetchException("Cannot fetch through collections: "
			       + o.getClass());
    }
  }

  class Gatherer extends Traverser {
    Gatherer(boolean f) {
      super(f);
      returnValue = new ArrayList();
    }

    Object last;

    void atTarget(Object o, Class cl) {
      // Don't add the same object multiple times in a row, because
      // multiple classes in its hierarchy might be target classes.
      if (o != last) ((List) returnValue).add(o);
      last = o;
      super.atTarget(o, cl);
    }
  }

  class ConcurrentTraverser extends Traverser {
    ConcurrentTraverser(boolean f) { super(f); }

    abstract class Pointer { abstract void set(Object o); }
    Pointer pointer;

    void traverseArrayElement(final Object o, final int i, Class cl,
			      Traversal.NodeSet tokens)
    {
      pointer = new Pointer() {
	  public void set(Object o2) {
	    Array.set(o, i, o2);
	  }
	};
      super.traverseArrayElement(o, i, cl, tokens);
    }

    void traverseCollectionElement(final ListIterator it, Object o, Class cl,
				   Traversal.NodeSet tokens,
				   MutableFlag traversedCollection)
    {
      pointer = new Pointer() {
	  // Remember where we are now...
	  int i = it.nextIndex();

	  public void set(Object o2) {
	    int j = it.nextIndex();

	    // ...so we can go back to it if we need to replace.
	    while (forward ? it.nextIndex() >= i : it.nextIndex() <= i)
	      if (forward) it.previous(); else it.next();

	    // We need to set through this iterator because if the collection
	    // changes by some other method, the iterator might fail-fast.
	    it.set(o2);

	    while (forward ? it.nextIndex() < j : it.nextIndex() > j)
	      if (forward) it.next(); else it.previous();
	  }
	};
      super.traverseCollectionElement(it, o, cl, tokens, traversedCollection);
    }

    void traverseConstructionEdge(final Object o, final Class cl,
				  final EdgeI edge, Class targetClass,
				  Traversal.NodeSet tokens)
    {
      pointer = new Pointer() {
	  public void set(Object o2) {
	    setTargetObject(o, cl, edge, o2);
	  }
	};
      super.traverseConstructionEdge(o, cl, edge, targetClass, tokens);
    }

    Pointer returnValuePointer;

    void atTarget(Object o, Class cl) {
      super.atTarget(o, cl);
      returnValue = o;
      this.notify();		// signal that the return value is ready
      try {
	this.wait();		// wait for return value to be read
      } catch (InterruptedException e) {
	// FIXME: exit more gracefully?
	throw new RuntimeException(e.toString());
      }
      returnValuePointer = pointer; // don't allow set until the return
				    // value has actually been read 
    }

    void set(Object o) {
      returnValuePointer.set(o);
    }
  }

  class APCollection extends AbstractSequentialList
  {
    boolean forward = true;

    /** Construct a collection-view of the target objects in the
	enclosing object graph slice reachable by following the
	strategy. */
    APCollection(boolean f) { forward = f; }

    /** No way to get the enclosing object from outside this... */
    ObjectGraphSlice getOGS() { return ObjectGraphSlice.this; }

    List gather() { return ObjectGraphSlice.this.gather(forward); }

    /** The number of target objects in the collection view.
	Unfortunately this has to be linear time-- we can't even cache the
	result, because the structure is mutable behind our back. */
    public int size() {
      return gather().size();
    }

    /** The maximum size of this container, or Integer.MAX_VALUE,
	whichever is smaller. */
    public int maxSize() {
      // Use this if add() is implemented.
      // return Integer.MAX_VALUE;
      return size();
    }

    // Override the AbstractCollection/AbstractList implementations of
    // this stuff to improve performance-- gather() is faster than
    // stepping through the iterator.

    public boolean contains(Object obj) { return gather().contains(obj); }
    public boolean isEmpty() { return !iterator().hasNext(); }
    public Object[] toArray() { return gather().toArray(); }
    public Object[] toArray(Object[] a) { return gather().toArray(a); }
    public String toString() { return gather().toString(); }
    public int hashCode() { return gather().hashCode(); }
    public boolean equals(Object obj) {
      if (obj == this) return true;
      if (!(obj instanceof List)) return false;
      if (obj instanceof APCollection) {
	if (((APCollection) obj).getOGS().equals(getOGS()))
	  return true;
      }
      return super.equals(obj); // Go ahead and iterate...
    }

    /** A ListIterator for traversing the object graph. */
    public ListIterator listIterator() {
      return new Itr();
    }

    /** A ListIterator for traversing the object graph, starting at
	the nth element.  Why is this abstract on
	AbstractSequentialList?? */
    public ListIterator listIterator(int n) {
      ListIterator i = listIterator();
      while (n-- > 0) i.next();
      return i;
    }

    /** A class that implements ListIterator.  It iterates over all
	objects in an object graph which are targets of the strategy. */
    class Itr implements ListIterator {
      ConcurrentTraverser traverser;
      volatile Thread gatherThread;
      Itr() {
	traverser = new ConcurrentTraverser(forward);
	gatherThread = new Thread() {
	    public void run() {
	      synchronized (traverser) { // wait for the parent to be waiting
		traverser.traverse(root, startSet);
		gatherThread = null;
		traverser.notify(); // signal that we fell off the end
	      }
	    }
	  };
	gatherThread.setDaemon(true);
	synchronized (traverser) { // don't let the child start
				   // until we're waiting	
	  gatherThread.start();
	  try {
	    traverser.wait();	// wait for a return value to be ready
	  } catch (InterruptedException e) {
	    // FIXME: exit more gracefully?
	    throw new RuntimeException(e.toString());
	  }
	}
      }

      public boolean hasNext() {
	synchronized (traverser) {
	  return gatherThread != null;
	}
      }
      public Object next() {
	synchronized (traverser) {
	  // FIXME: check forward
	  Object ret = traverser.getReturnValue();
	  traverser.notify();	// signal that the return value was read
	  try {
	    traverser.wait();	// wait for the next return value to be ready
	  } catch (InterruptedException e) {
	    // FIXME: exit more gracefully?
	    throw new RuntimeException(e.toString());
	  }
	  return ret;
	}
      }
      public void set(Object o) {
	traverser.set(o);
      }

      UnsupportedOperationException bomb() {
	return new UnsupportedOperationException();
      }

      public boolean hasPrevious() { throw bomb(); }
      public Object previous() { throw bomb(); }
      public void add(Object o) { throw bomb(); }
      public void remove() { throw bomb(); }
      public int nextIndex() { throw bomb(); }
      public int previousIndex() { throw bomb(); }
    }
	
    // DEAD CODE.  Kept for historical/educational/entertainment purposes...
    class Itr2 implements ListIterator {
      Frame next, prev;
      int index;
      boolean lastMoveWasForward;

      /** Traverse the collection view. */
      Itr2() { moveToBegin(); }

      void moveToBegin() {
	next = new Frame(true, root, startSet, null, null);
	move(true);
	index = 0;
      }

      /** No way to get the enclosing object from outside this... */
      ObjectGraphSlice getOGS() { return ObjectGraphSlice.this; }

      // ListIterator stuff.
      public boolean hasNext() { return next != null; }
      public boolean hasPrevious() { return prev != null; }
      public Object next() {
	if (debug) System.out.println("** next() **");
	if (!hasNext()) throw new NoSuchElementException();
	prev = (Frame) next.clone();
	next = move(true);
	return prev.obj;
      }
      public Object previous() {
	if (debug) System.out.println("** previous() **");
	if (!hasPrevious()) throw new NoSuchElementException();
	next = (Frame) prev.clone();
	prev = move(false);
	return next.obj;
      }
      public int nextIndex() { return index; }
      public int previousIndex() { return index-1; }

      UnsupportedOperationException bomb()
      { return new UnsupportedOperationException(); }

      // Unsupported stuff.
      public void add(Object o) { throw bomb(); }
      public void remove() { throw bomb(); }

      /** Is the iterator equal to this?  Only if it has the same slice and
	  continuation. */
      public boolean equals(Object iterator) {
	if (!(iterator instanceof Itr2)) return false;
	Itr2 tgi = (Itr2) iterator;
	if (!tgi.getOGS().equals(getOGS())) return false;
	if (!(tgi.next == null && next == null) &&
	    (tgi.next == null || next == null)) return false;
	if (!tgi.next.equals(next)) return false;
	// FIXME: do we need to compare prev and lastMoveWasForward too?
	return true;
      }

      /** Replace the last returned object in the object graph.  Throws
	  IllegalAccessException if we haven't returned anything yet.
	  Throws UnsupportedOperationException if:
	    * the current object is the root of the object graph
	    * we're in the middle of an unmodifiable enumeration
	    * obj is of the wrong type
      */
      public void set(Object obj) {
	if (debug) System.out.println("** set(" + obj + ") **");
	Frame frame = lastMoveWasForward ? prev : next;
	if (frame == null)
	  throw new IllegalStateException();
	Frame p = frame.parent;
	if (p == null)
	  throw new UnsupportedOperationException(
	    "Cannot replace the root of the object graph.");
	p.it.set(obj);
	// FIXME: go up/down alt/inh links?
	frame.obj = obj;
      }

      /** Move one position, to the next element if forward is true,
	  otherwise to the previous element.  Return the current frame. */
      Frame move(boolean forward) {
	lastMoveWasForward = forward;
	if (forward) index++; else index--;
	Frame frame = forward ? next : prev;
	boolean moved = false;
	do {
	  if (debug) System.out.println(frame);
	  if (frame.atBegin) {
	    if (moved && isTarget(frame.tokens)) {
	      return frame;
	    }
	    if (forward) {
	      frame.atBegin = false;
	      moved = true;
	    } else {
	      frame = frame.parent;
	      moved = false;
	    }
	    continue;
	  }
	  Frame.SuccessorIterator it = frame.it;
	  if (it == null) {
	    it = frame.setupSuccessorIterator(forward);
	  }
	  Object succ;
	  if (!forward) {
	    if (!it.hasPrevious()) {
	      frame.atBegin = true;
	      moved = true;
	      continue;
	    }
	    succ = it.previous();
	    moved = true;
	  } else {
	    if (!it.hasNext()) {
	      frame = frame.parent;
	      moved = false;
	      continue;
	    }
	    succ = it.next();
	    moved = true;
	  }
	  if (succ != null) {
	    frame = new Frame(forward, succ, it.getTokens(), null, frame);
	    continue;
	  }
	} while (frame != null);
	return frame;
      }

      /** Emulate the current continuation as a stack of frames. */
      class Frame implements Cloneable {
	boolean atBegin; Object obj; Traversal.NodeSet tokens;
	SuccessorIterator it; Frame parent;
	Frame(boolean a, Object o, Traversal.NodeSet n,
	      SuccessorIterator t, Frame p)
	  { atBegin = a; obj = o; tokens = n; it = t; parent = p; }
	public Object clone() {
	  return new Frame(atBegin, obj, tokens,
			   (SuccessorIterator) (it == null ? null : it.clone()),
			   (Frame) (parent == null ? null : parent.clone()));
	}
	public boolean equals(Object o) {
	  if (!(o instanceof Frame)) return false;
	  Frame frame = (Frame) o;
	  return atBegin == frame.atBegin
	      && obj == frame.obj
	      && tokens.equals(frame.tokens)
	      && ((it == null && frame.it == null) || it.equals(frame.it))
	      && ((parent == null && frame.parent == null)
		  || parent.equals(frame.parent));
	}
	public String toString() {
	  return "<" + (atBegin ? "begin " : "") + obj +
	         " " + tokens + " (" + it + ")>\n" +
		 (parent == null ? "" : parent.toString());
	}

	SuccessorIterator setupSuccessorIterator(boolean atBegin) {
	  if (obj.getClass().isArray())
	    it = new ArrayIterator(atBegin);
	  else
	    it = new EdgeIterator(atBegin);
	  return it;
	}

	/** This is an abstraction for iterating through the successors
	    of the object in this frame (i.e. the targets of outgoing edges,
	    or the elements of the array). */
	abstract class SuccessorIterator implements Cloneable {
	  abstract boolean hasNext();
	  abstract boolean hasPrevious();
	  abstract Object next();
	  abstract Object previous();
	  abstract Traversal.NodeSet getTokens();
	  abstract void set(Object o);
	  abstract public Object clone();
	}

	class ArrayIterator extends SuccessorIterator {
	  int i;
	  ArrayIterator(boolean atBegin) {
	    i = atBegin ? 0 : Array.getLength(obj);
	  }
	  boolean hasNext() { return i < Array.getLength(obj); }
	  boolean hasPrevious() { return i > 0; }
	  Object next() { return Array.get(obj, i++); }
	  Object previous() { return Array.get(obj, --i); }
	  Traversal.NodeSet getTokens() { return tokens; }
	  void set(Object o) { Array.set(obj, i, o); }

	  protected ArrayIterator() { }
	  public Object clone() {
	    ArrayIterator ret = new ArrayIterator();
	    ret.i = i;
	    return ret;
	  }
	  public boolean equals(Object o) {
	    return o instanceof ArrayIterator && ((ArrayIterator) o).i == i;
	  }
	  public String toString() { return i + ""; }
	}

	class EdgeIterator extends SuccessorIterator {
	  ListIterator edgeIt;		    // outgoing EdgeSet objects
	  Traversal.EdgeSet edgeSet;   // current EdgeSet
	  RepetitionIterator it;	    // (if current edge is repetition)
	  EdgeIterator(boolean atBegin) {
	    List edgeSets = tokens.getOutgoingEdgeSets();
	    if (atBegin) {
	      edgeIt = edgeSets.listIterator();
	    } else {
	      edgeIt = edgeSets.listIterator(edgeSets.size());
	    }
	  }
	  boolean hasNext() {
	    return it != null && it.hasNext() || edgeIt.hasNext();
	  }
	  boolean hasPrevious() {
	    return it != null && it.hasPrevious() || edgeIt.hasPrevious();
	  }
	  Object next() { return move(true); }
	  Object previous() { return move(false); }
	  Object move(boolean forward) {
	    if (it != null) {
	      if (forward ? it.hasNext() : it.hasPrevious())
		return (forward ? it.next() : it.previous());
	      it = null;
	    }
	    edgeSet = (Traversal.EdgeSet)
	      (forward ? edgeIt.next() : edgeIt.previous());
	    EdgeI edge = edgeSet.getEdge();
	    if (edge.isConstructionEdge()) {
	      if (isRepetitionEdge(edge)) {
		// FIXME: don't traverse same collection twice
		if (obj instanceof List)
		  it = new ListRepetitionIterator(forward);
		else
		  it = new RepetitionIterator(forward);
	      } else {
		Member member = getMember(getTokensClass(tokens), edge);
		Class type = getTargetClass(member);
		// FIXME: allow traversal to primitive types
		// need to add them to the class graph; also need to
		// remember that they're primitive values and not
		// wrapper objects.
		if (!type.isPrimitive())
		  return getTargetObject(obj, member);
	      }
	    } else if (edge.isAlternationEdge()) {
	      // FIXME: knowledge path
	      if (forward &&
		  // !lastWasInheritance &&     // knowledge path constraint
		  // premature termination:
		  getTokensClass(tokens).isInstance(obj)) {
		if (debug) System.out.println(obj + " isa " + getTokensClass(tokens));
		return obj;
	      }
	    } else if (edge.isInheritanceEdge()) {
	      // FIXME: knowledge path
	      return obj;
	    }
	    return null;
	  }
	  Traversal.NodeSet getTokens() {
	    return edgeSet.getTargetNodeSet();
	  }
	  void set(Object o) {
	    if (it != null) it.set(o);
	    EdgeI edge = edgeSet.getEdge();
	    if (getNodeClass(edge.getTarget())
		.isAssignableFrom(o.getClass()))
	      throw new UnsupportedOperationException(
		"Incompatible object.");
	    setTargetObject(obj, getTokensClass(tokens), edge, o);
	    // FIXME: go up or down alt/inh edges?
	  }

	  protected EdgeIterator() { }
	  public Object clone() {
	    EdgeIterator ret = new EdgeIterator();
	    ret.edgeIt = cloneListIterator(); // edgeIt.clone();
	    ret.edgeSet = edgeSet;
	    if (it != null) ret.it = (RepetitionIterator) it.clone();
	    return ret;
	  }
	  protected ListIterator cloneListIterator() {
	    ListIterator ret = null;
	    if (edgeIt instanceof Cloneable) {
	      try {
		ret = (ListIterator)
		  edgeIt
		  .getClass()
		  .getMethod("clone", null)
		  .invoke(edgeIt, null);
	      } catch (Exception e) {
		throw new RuntimeException("\n" + e);
	      }
	    } else {
	      List edgeSets = tokens.getOutgoingEdgeSets();
	      ret = edgeSets.listIterator(edgeIt.nextIndex());
	    }
	    return ret;
	  }
	  public boolean equals(Object o) {
	    if (!(o instanceof EdgeIterator)) return false;
	    EdgeIterator eit = (EdgeIterator) o;
	    return
	      eit.edgeIt.equals(edgeIt) && 
	      eit.edgeSet.equals(edgeSet) &&
	      (eit.it == null && it == null ||
	       eit.it != null && it != null && eit.it.equals(it));
	  }
	  public String toString() {
	    return edgeSet + ": " + String.valueOf(it);
	  }
	}

	class RepetitionIterator {
	  Iterator iter;
	  int i;
	  RepetitionIterator(boolean atBegin) {	    
	    if (!atBegin)
	      throw new UnsupportedOperationException(
		"Don't know how to iterate backward over "
		+ getTokensClass(tokens));
	    iter = getIterator(obj);
	  }
	  boolean hasNext() { return iter.hasNext(); }
	  boolean hasPrevious() { return i > 0; }
	  Object next() {
	    i++;
	    return iter.next();
	  }
	  Object previous() {
	    throw new UnsupportedOperationException(
	      "Don't know how to iterate backward over "
	      + getTokensClass(tokens));
	  }
	  void set(Object o) {
	    throw new UnsupportedOperationException(
	      "Don't know how to modify " + iter.getClass());
	  }

	  protected RepetitionIterator() { }
	  protected RepetitionIterator make() {
	    return new RepetitionIterator();
	  }
	  public Object clone() {
	    RepetitionIterator o = make();
	    o.iter = cloneIterator();
	    o.i = i;
	    return o;
	  }
	  protected Iterator cloneIterator() {
	    Iterator copy_of_iter;
	    if (iter instanceof Cloneable) {
    /*
	      // Iterator is not a subinterface of Cloneable, so we
	      // have to go through this rigamarole...
	      try {
		copy_of_iter = (Iterator) ((Cloneable) iter).clone();
	      } catch (CloneNotSupportedException e) {
	      }
    */
    // that doesn't work, clone() is not on Cloneable and
    // Object.clone() is not public!
    // see: http://developer.java.sun.com/developer/bugParade/bugs/4098033.html
    // Instead, use reflection, which is slooow...
	      try {
		copy_of_iter = (Iterator)
		  iter
		  .getClass()
		  .getMethod("clone", null)
		  .invoke(iter, null);
	      } catch (Exception e) {
		throw new RuntimeException("\n" + e);
	      }
	    } else {
	      // FIXME
	      // It's not cloneable, so we have to find our way back
	      // here manually... ugh.  Hope nothing got removed in
	      // the meanwhile!
	      copy_of_iter = getIterator(obj);
	      for (int j = 0; j <= i; j++)
		copy_of_iter.next();
	    }
	    return copy_of_iter;
	  }
	  public boolean equals(Object o) {
	    if (!(o instanceof RepetitionIterator)) return false;
	    RepetitionIterator c = (RepetitionIterator) o;
	    // Iterators aren't likely to have a useful equals(), so
	    // just hope that comparing the index is enough.
	    return c.i == i;
	  }
	  public String toString() { return i + ""; }
	}

	class ListRepetitionIterator extends RepetitionIterator {
	  ListRepetitionIterator(boolean atBegin) {
	    List l = (List) obj;
	    iter = l.listIterator(atBegin ? 0 : (i = l.size()-1));
	  }
	  boolean hasPrevious() { return ((ListIterator) iter).hasPrevious(); }
	  Object previous() { return ((ListIterator) iter).previous(); }
	  void set(Object o) { ((ListIterator) iter).set(o); }

	  protected ListRepetitionIterator() { }
	  protected RepetitionIterator make() {
	    return new ListRepetitionIterator();
	  }
	  protected Iterator cloneIterator() {
	    if (iter instanceof Cloneable) return super.cloneIterator();
	    return ((List) obj).listIterator(i);
	  }
	  public boolean equals(Object o) {
	    return o instanceof ListRepetitionIterator && super.equals(o);
	  }
	} // end class ListRepetitionIterator
      } // end class Frame
    } // end class Itr2
  } // end class APCollection

  /** A NodeSet representing the start set of tokens (copy indices)
      for class cl, or null if cl has no start copies in
      the traversal. */
  Traversal.NodeSet getStartSet(Class cl) {
    // FIXME: is it better to search the ancestors of cl or to search
    // the list of start sets?  Do the former, for now.
    Traversal.NodeSet startSet = null;
    for (Iterator it = getAncestors(cl).iterator(); it.hasNext();)
      try {
	Object v = getNode((Class) it.next());
	if ((startSet = tg.getStartSet(v)) != null) break;
      } catch (NoSuchClassGraphNodeException e) {
      }
    return startSet;
  }

  /** Does the node set include a target of the traversal? */
  boolean isTarget(Traversal.NodeSet nodes) {
    // FIXME: check the indices
    return isTargetNode(nodes.getNode());
  }

  /** Is the class a target of the traversal? */
  boolean isTargetClass(Class cl) {
    try {
      return isTargetNode(getNode(cl));
    } catch (NoSuchClassGraphNodeException e) {
      return false;
    }
  }

  /** Is the class graph node a target of the traversal? */
  boolean isTargetNode(Object v) {
    Traversal.NodeSet finish = getTraversal().getFinishSet(v);
    return finish != null;
  }

  /** The method or field on cl representing the edge, or null if edge
      is not a construction edge. */
  Member getMember(Class cl, EdgeI edge) {
    Member member = null;
    if (members.containsKey(edge))
      return (Member) members.get(edge);
    ClassGraph cg = getClassGraph();
    if (edge.isConstructionEdge()) {
      String name = cg.memberName(edge);
      if (cg.isDerivedEdge(edge))
	try {
	  member = cl.getDeclaredMethod(name, null);
	} catch (NoSuchMethodException e) {
	  throw new RuntimeException("\n" + name + ": " + e);
	}
      else
	try {
	  member = cl.getDeclaredField(name);
	} catch (NoSuchFieldException e) {
	  throw new RuntimeException("\n" + name + ": " + e);
	}
    }
    members.put(edge, member);
    return member;
  }
  static Map members = new HashMap();

  /** The target class of the edge. */
  Class getTargetClass(Class src, EdgeI edge) {
    if (edge.isAlternationEdge())
      throw new RuntimeException("Can't get subclass");
    else if (edge.isInheritanceEdge())
      return src.getSuperclass();
    else if (edge.isConstructionEdge())
      return getTargetClass(getMember(src, edge));
    else
      return null;
  }

  static Class getTargetClass(Member member) {
    if (member instanceof Field)
      return ((Field) member).getType();
    else
      return ((Method) member).getReturnType();
  }

  /** The target object of the edge in the object graph outgoing from the
      source object, or null if we can't access it. */
  Object getTargetObject(Object source, Class cl, EdgeI edge) {
    if (edge.isAlternationEdge() || edge.isInheritanceEdge())
      // Same object, different class.
      return source;
    else if (edge.isConstructionEdge())
      return getTargetObject(source, getMember(cl, edge));
    else
      return null;
  }

  Object getTargetObject(Object source, Member member) {
    try {
      ((AccessibleObject) member).setAccessible(true);
      if (member instanceof Field)
	return ((Field) member).get(source);
      else
	return ((Method) member).invoke(source, null);
    } catch (SecurityException e) {
      if (debug) System.out.println("Couldn't set accessible " + member);
    } catch (IllegalAccessException e) {
      if (debug) System.out.println("Couldn't access " + member);
    } catch (InvocationTargetException e) {
      throw new RuntimeException("\n" + e.getTargetException());
    }
    return null;
  }

  /** Set the target object of the edge in the object graph outgoing
      from the source object.  Throws a RuntimeException if the edge
      is derived or is not a construction edge. */
  void setTargetObject(Object source, Class cl, EdgeI edge,
		       Object target)
  {
    if (!edge.isConstructionEdge())
      throw new RuntimeException("Not a construction edge: " + edge);
    setTargetObject(source, getMember(cl, edge), target);
  }

  void setTargetObject(Object source, Member member, Object target)
  {
    if (member instanceof Field)
      try {
	((AccessibleObject) member).setAccessible(true);
	((Field) member).set(source, target);
      } catch (SecurityException e) {
	if (debug) System.out.println("Couldn't set accessible " + member);
      } catch (IllegalAccessException e) {
	if (debug) System.out.println("Couldn't access " + member);
      } catch (Exception e) {
	// Shouldn't happen...
	throw new RuntimeException("\n" + member + ": " + e);
      }
    else
      // FIXME: find the setter method
      throw new RuntimeException("Derived edge: " + member);
  }

  /** The class corresponding to a traversal node set. */
  Class getTokensClass(Traversal.NodeSet nodes) {
    return getNodeClass(nodes.getNode());
  }

  /** The class corresponding to a class graph node. */
  Class getNodeClass(Object node) {
    return getClassGraph().getNodeClass(node);
  }

  /** The class graph node corresponding to a class. */
  Object getNode(Class cl) throws NoSuchClassGraphNodeException {
    return getClassGraph().getNode(cl.getName());
  }

  boolean isRepetitionEdge(EdgeI edge) {
    return getClassGraph().isRepetitionEdge(edge);
  }

  boolean isCollection(Object obj) {
    return getClassGraph().isCollectionClass(obj.getClass());
  }

  static Iterator getIterator(Object obj) {
    if (obj instanceof java.util.Collection)
      return ((java.util.Collection) obj).iterator();
    final Enumeration e = ((edu.neu.ccs.demeter.dj.Collection) obj).elements();
    return new Iterator() {
	public boolean hasNext() { return e.hasMoreElements(); }
	public Object next() { return e.nextElement(); }
	public void remove() { throw new UnsupportedOperationException(); }
      };
  }

  static ListIterator getListIterator(Object obj) {
    if (obj instanceof java.util.List)
      return ((java.util.List) obj).listIterator();
    final Iterator it = getIterator(obj);
    return new ListIterator() {
	int i = 0;
	public boolean hasNext() { return it.hasNext(); }
	public boolean hasPrevious() { return i > 0; }
	public Object next() { i++; return it.next(); }
	public void remove() { i--; it.remove(); }
	public int nextIndex() { return i; }
	public int previousIndex() { return i-1; }

	UnsupportedOperationException bomb()
	{ return new UnsupportedOperationException(); }

	public Object previous() { throw bomb(); }
	public void add(Object o) { throw bomb(); }
	public void set(Object o) { throw bomb(); }
      };
  }

  // FIXME: memoize?
  static List getAncestors(Class cl) {
    List l = new ArrayList();
    addAncestors(cl, l);
    return l;
  }
  static void addAncestors(Class cl, List l) {
    if (cl == null || l.contains(cl)) return;
    addAncestors(cl.getSuperclass(), l);
    Class ifs[] = cl.getInterfaces();
    for (int i = 0; i < ifs.length; i++) 
      addAncestors(ifs[i], l);
    l.add(cl);
  }
}