Index: java/net/deterlab/abac/Query.java
===================================================================
--- java/net/deterlab/abac/Query.java	(revision 736a573a8d795e77fe8af7b59b2187b5f75c0bca)
+++ java/net/deterlab/abac/Query.java	(revision 2d45fd4ba3d87e386e713d0ef67715d3f6ae381b)
@@ -17,6 +17,6 @@
     /** Internal graph representation */
     private Graph<Role,Credential> g;
-    /** Count of vertices in g */
-    private int vertex_count;
+    /** Count of vertices in the most recent calculate path */
+    private boolean valid;
 
     /**
@@ -26,4 +26,5 @@
     public Query(Graph<Role,Credential> g) {
         this.g = g;
+	valid = false;
     }
 
@@ -38,41 +39,80 @@
      */
     public Graph<Role,Credential> run(String attr, String prin) {
-        Role attribute = null, principal = null;;
-
-        if (!attr.isEmpty()) attribute = new Role(attr);
-        if (!prin.isEmpty()) principal = new Role(prin);
-
+	Role attribute = (!attr.isEmpty()) ? new Role(attr) : null;
+	Role principal = (!prin.isEmpty()) ? new Role(prin) : null;
         Graph<Role,Credential> ret =
             Graphs.<Role,Credential>synchronizedDirectedGraph(
                     new DirectedSparseGraph<Role,Credential>());
-
-	/* empty attribute, non-empty principal: find everywhere the principal
-	 * can go */
-        if (attr.isEmpty() && !prin.isEmpty()) {
-            if (g.containsVertex(principal)) {
-                CollectReversePath collect = new CollectReversePath(ret);
-                forward_dfs(principal, collect);
-            }
-        }
-
-        /* otherwise we're going to do some kind of a reverse dfs */
-        else if (g.containsVertex(attribute)) { 
-            if ( prin == null || prin.isEmpty()) {
-                CollectQueryGraph  collect = new CollectQueryGraph(ret);
-                reverse_dfs(attribute, collect);
-            }
-            else {
-                if ( g.containsVertex(principal)) {
-                    CollectQueryPath  collect = new CollectQueryPath(ret,
-			    principal);
-                    reverse_dfs(attribute, collect);
-                }
-            }
-        }
-
-        vertex_count = ret.getVertexCount();
-
+	ArrayList<Graph<Role, Credential> > subs = 
+	    new ArrayList<Graph<Role, Credential> >();
+	Set<Role> hasAttr = null;
+
+	// System.out.println("In run " + attr + " " + prin);
+
+	if (attribute == null && principal == null ) {
+	    valid = false;
+	    return ret;
+	}
+	else if (principal != null ) {
+	    /* This branch happens if attribute is null or not, and either is
+	     * fine for the bfs routine. */
+	    valid = bfs(principal, attribute, ret, 
+		    new forwardSearch<Role, Credential>());
+	} else {
+	    /* attribute is != null here */
+	    valid = bfs(attribute, principal, ret, 
+		    new reverseSearch<Role, Credential>());
+	} 
+
+	if ( principal == null ) hasAttr = find_principals(attribute);
+	else {
+	    hasAttr =new HashSet<Role>();
+	    hasAttr.add(principal);
+	}
+
+	/* Now ret contains the primary path of the proof, for each linking
+	 * role or intersection on that path, we construct a Query object to
+	 * make that subproof. */
+	for (Credential c: ret.getEdges() ) {
+	    Role head = c.head();
+	    Role tail = c.tail();
+
+	    if ( head.is_linking()) {
+		Query subq = new Query(g);
+		subs.add(subq.run(head.linked_role(), tail.principal()));
+		if ( !subq.successful()) 
+		    throw new RuntimeException("Cannot prove sub-proof: " + 
+			    head.linked_role() + " <- " + tail.principal() +
+			    " something is very wrong!");
+	    } else if ( head.is_intersection() ) {
+		try {
+		    for (Role r: head.prereqs()) {
+			for (Role p : hasAttr) {
+			    Query subq = new Query(g);
+			    subs.add(subq.run(r.toString(), p.toString()));
+			    if ( !subq.successful()) 
+				throw new RuntimeException(
+					"Cannot prove sub-proof: " + 
+					r.toString() + " <- " +  p + 
+					" something is very wrong!");
+			}
+		    }
+		}
+		catch (ABACException ignored) { }
+	    }
+	}
+	/* Now subs has all the subsidiary proofs in it, merge 'em */
+	for (Graph<Role, Credential> sg: subs) {
+	    for (Role r: sg.getVertices()) 
+		if (!ret.containsVertex(r))
+		    ret.addVertex(r);
+	    for (Credential c: sg.getEdges() )
+		if ( !ret.containsEdge(c)) 
+		    ret.addEdge(c, c.head(), c.tail());
+	}
         return ret;
     }
+
+
 
     /**
@@ -83,5 +123,5 @@
      */
     public boolean successful() {
-        return vertex_count > 0;
+        return valid;
     }
 
@@ -94,299 +134,274 @@
     public Set<Role> find_principals(Role n) {
         Set<Role> principals = new HashSet<Role>();
-    
-        GetPrincipals f = new GetPrincipals(principals);
-        reverse_dfs(n, f);
+	bfs(n, null, null, new principalSearch(principals));
         return principals;
     }
 
-
-    /**
-     * Interface to pass to the reverse_dfs class that operates on nodes in the
-     * graph as part of the depth first search (DFS).
-     */
-    interface DfsFcn {
-	/**
-	 * Called when the node is first encountered on the DFS.
-	 * @param x the Role being visited
-	 */
-        public void node(Role x);
-	/**
-	 * Called when all the node's children have been visited on the DFS.
-	 * @param x the Role being visited
-	 */
-        public void node_after(Role x);
-    }
-
-    /**
-     * Class used to pull all the principals out of a reverse_dfs searched
-     * graph.  It takes a collection to the constructor and adds all principals
-     * it sees to that collection.  In no collection is passed in, it creates a
-     * local HashSet of vertices.  The collection is accessible via the p
-     * (i.e., principals) member.
-     */
-    private class GetPrincipals implements DfsFcn {
-	/** The principals collected */
-        public Collection<Role> p;
-
-	/**
-	 * Initialize the principals collection.
-	 * @param vc the initial collection.  May be null.
-	 */
-        public GetPrincipals(Collection<Role> vc) {
-            if ( vc != null) { p =vc;}
-            else { p = new HashSet<Role>(); }
-        }
-
-	/**
-	 * Adds principals to the collection, called by the DFS.
-	 * @param r the Role visited.
-	 */
-        public void node(Role r) {
-            if ( r.is_principal() ) p.add(r);
-        }
-	/**
-	 * Does nothing.
-	 * @param r a Role, a dummy
-	 */
-        public void node_after(Role r) { }
-    }
-
-    /**
-     * Collect a subgraph. Add every node and outgoing arc we encounter, and
-     * pull in the linking node and intersection subtrees as well. Because it's
-     * possible that these subtrees have been encountered more than once, we're
-     * careful not to pull them in twice. The created graph is found in the
-     * public ng member.
-     */
-    private class CollectQueryGraph implements DfsFcn {
-	/** The subgraph being collected */
-        public Graph<Role, Credential> ng;
-	/** The linking roles already added to the sub-graph */
-        protected HashSet<Role> linking_roles_seen;
-	/** The intersection roles already added to the sub-graph */
-        protected HashSet<Role> intersection_roles_seen;
-
-	/**
-	 * Initialize the graph into which to gather nodes/edges.
-	 * @param g A graph to collect
-	 */
-        public CollectQueryGraph(Graph<Role,Credential> g) {
-            ng = g;
-            linking_roles_seen = new HashSet<Role>();
-            intersection_roles_seen = new HashSet<Role>();
-        }
-
-
-	/**
-	 * Do the collection on each node we visit.
-	 * @param r a Role, the current node in the DFS.
-	 */
-        public void node(Role r) {
-            if (r.is_linking() && !linking_roles_seen.contains(r)) {
-                // Collect this linking role subgraph
-                reverse_dfs(new Role(r.principal_part()), this);
-                linking_roles_seen.add(r);
-            }
-
-            // collect subgraph for each intersection prereq
-            if (r.is_intersection() && !intersection_roles_seen.contains(r)) {
-		try {
-		    for (Role prereq : r.prereqs())
-			reverse_dfs(prereq, this);
+    /**
+     * Class extended to specialize the behavior of the bfs routine at the core
+     * of the query system.  There are two ways to customize - the traversal
+     * order which controls if edges are followed in the orientation of the
+     * graph or in the reverse orientation and a member called when an edge is
+     * added to an output graph.
+     */
+    private abstract class bfsSearchDirection<V,E> {
+	/**
+	 * Return a collection of outgoing edges under the search direction's
+	 * interpretation.
+	 * @param g the Graph<V, E> being traversed
+	 * @param v a V, the vertex from which the edges come
+	 * @return a collection of outgoing edges under the search direction's
+	 * interpretation.
+	 */
+	public abstract Collection<E> forwardEdges(Graph<V, E> g, V v);
+	/**
+	 * Return a collection of incoming edges under the search direction's
+	 * interpretation.
+	 * @param g the Graph<V, E> being traversed
+	 * @param v a V, the vertex into which the edges come
+	 * @return a collection of outgoing edges under the search direction's
+	 * interpretation.
+	 */
+	public abstract Collection<E> backwardEdges(Graph<V, E> g, V v);
+	/**
+	 * Return the source of this edge under the search direction's
+	 * interpretation.
+	 * @param g the Graph<V, E> being traversed
+	 * @param e an E, the edge being considered
+	 * @return the source of this edge under the search direction's
+	 * interpretation.
+	 **/
+	public abstract V getSource(Graph<V, E> g, E e);
+	/**
+	 * Return the destination of this edge under the search direction's
+	 * interpretation.
+	 * @param g the Graph<V, E> being traversed
+	 * @param e an E, the edge being considered
+	 * @return the destination of this edge under the search direction's
+	 * interpretation.
+	 **/
+	public abstract V getDest(Graph<V, E> g, E e);
+	/**
+	 * Called when an edge is added; do nothing.
+	 * @param e an E edge being added.
+	 */
+	public void keptEdge(E e) { }
+    }
+
+    /**
+     * Class that runs the BFS along the graph as defined.
+     */
+    private class forwardSearch<V,E> extends bfsSearchDirection<V,E> {
+	/**
+	 * Return a collection of outgoing edges; outgoing is defined by the
+	 * graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param v a V, the vertex from which the edges come
+	 * @return a collection of outgoing edges
+	 */
+	public Collection<E> forwardEdges(Graph<V, E> g, V v) {
+	    return g.getOutEdges(v);
+	}
+	/**
+	 * Return a collection of incoming edges; incoming is defined by the
+	 * graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param v a V, the vertex into which the edges come
+	 * @return a collection of outgoing edges
+	 */
+	public Collection<E> backwardEdges(Graph<V, E> g, V v) {
+	    return g.getInEdges(v);
+	}
+	/**
+	 * Return the source of this edge as defined by the underlying graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param e an E, the edge being considered
+	 * @return the source of this edge 
+	 */
+	public V getSource(Graph<V, E> g, E e) {
+	    return g.getSource(e);
+	}
+	/**
+	 * Return the destination of this edge as defined by the underlying
+	 * graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param e an E, the edge being considered
+	 * @return the destination of this edge 
+	 */
+	public V getDest(Graph<V, E> g, E e) {
+	    return g.getDest(e);
+	}
+	/**
+	 * Called when an edge is added; do nothing.
+	 * @param e an E edge being added.
+	 */
+	public void keptEdge(E e) { }
+    }
+
+    /**
+     * Class that runs the BFS along reversed links.
+     */
+    private class reverseSearch<V,E> extends bfsSearchDirection<V,E> {
+	/**
+	 * Return a collection of outgoing edges; outgoing is reversed with
+	 * respect to the graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param v a V, the vertex from which the edges come
+	 * @return a collection of outgoing edges
+	 */
+	public Collection<E> forwardEdges(Graph<V, E> g, V v) {
+	    return g.getInEdges(v);
+	}
+	/**
+	 * Return a collection of incoming edges; incoming is reversed with
+	 * respect to the graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param v a V, the vertex into which the edges come
+	 * @return a collection of outgoing edges
+	 */
+	public Collection<E> backwardEdges(Graph<V, E> g, V v) {
+	    return g.getOutEdges(v);
+	}
+	/**
+	 * Return the source of this edge in the reverse of the underlying
+	 * graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param e an E, the edge being considered
+	 * @return the source of this edge 
+	 */
+	public V getSource(Graph<V, E> g, E e) {
+	    return g.getDest(e);
+	}
+	/**
+	 * Return the destination of this edge in the reverse of the underlying
+	 * graph.
+	 * @param g the Graph<V, E> being traversed
+	 * @param e an E, the edge being considered
+	 * @return the destination of this edge 
+	 */
+	public V getDest(Graph<V, E> g, E e) {
+	    return g.getSource(e);
+	}
+    }
+
+    /**
+     * Class that traverses the graph in reverse asd collects all principal
+     * nodes found.
+     */
+    private class principalSearch<V, E> 
+	    extends reverseSearch<V, E> {
+	/** This collects the principals */
+	private Set<Role> p;
+	/**
+	 * Create a principalSearch that inserts into s
+	 * @param s a Set of Roles to update (may be null).
+	 */
+	public principalSearch(Set<Role> s) { 
+	    if ( (p = s) == null ) p = new HashSet<Role>();
+	}
+	/**
+	 * Put principals on valid edges into the attached set.
+	 * @param e an E (edge) being inserted into the final proof graph
+	 */
+	public void keptEdge(E e) {
+	    if ( !(e instanceof Credential) ) return;
+
+	    Credential c = (Credential) e;
+	    if (c.tail().is_principal()) p.add(c.tail());
+	}
+    }
+
+    /**
+     * Conduct a breadth first search along the underlying graph from src to
+     * dest.  If a valid path is found, add it to path (which mat be null).
+     * The dir parameter controls the direction of the traversal and may invoke
+     * a side effect when an edge is added to path.  Though the graph may be
+     * traversed in either direction, path is always in the same sense as the
+     * underlying graph.  If dest is null the bfs runs until all
+     * reachable nodes have been visited and that graph is returned as a
+     * success. 
+     * @param src the Role to start the search from 
+     * @param dest the Role to find a path to
+     * @param path a Graph<Role, Credential> in which the result path is
+     * returned
+     * @param dir a bfsSearchDirection<Role, Credential> that defines direction
+     * of search and side effects
+     * @return true if the path is found
+     */
+    private boolean bfs(Role src, Role dest, 
+	    Graph<Role, Credential> path, 
+	    bfsSearchDirection<Role, Credential> dir) {
+	Queue<Role> q = new ArrayDeque<Role>();
+	DirectedGraph<Role, Credential> bfs = 
+	    new DirectedSparseGraph<Role, Credential>();
+	HashSet<Role> visited = new HashSet<Role>();
+	boolean foundDest = false;
+
+	if (src == null || !g.containsVertex(src))
+	    return false;
+
+	q.add(src);
+	visited.add(src);
+	bfs.addVertex(src);
+
+	while ( q.size() > 0 && !foundDest) {
+	    Role x = q.remove();
+	    for (Credential e: dir.forwardEdges(g, x)) {
+		Role y = dir.getDest(g, e);
+		if ( !visited.contains(y)) {
+		    visited.add(y);
+		    bfs.addVertex(y);
+		    bfs.addEdge(e, e.tail(), e.head());
+		    if ( dest != null && y.equals(dest)) {
+			foundDest = true;
+			break;
+		    }
+		    q.add(y);
 		}
-		catch (ABACException ignored) { }
-                intersection_roles_seen.add(r);
-            }
-
-            // Add this node's children
-            for (Credential c : g.getInEdges(r) ) {
-                Role tail = g.getSource(c);
-                ng.addEdge(c, tail, r); // FIXME tail and r can come from c [?]
-            }
-        }
-	/**
-	 * Does nothing.
-	 * @param r a Role, a dummy
-	 */
-        public void node_after(Role r) { }
-
-    }
-
-    /**
-     * Collect the path from one node to another. It includes vertices that
-     * are traversed to reach the node. It also includes subgraphs that imply
-     * the linking/intersection edges traversed.
-     */
-    private class CollectQueryPath extends CollectQueryGraph {
-	/** Vertices on the path to the principal */
-        HashSet<Role> onPath;
-	/**
-	 * Establish the collection graph and the destination.
-	 * @param g the graph that collects the result
-	 * @param dest the Role to find
-	 */
-        public CollectQueryPath(Graph<Role,Credential> g, Role dest) {
-            super(g);
-            onPath = new HashSet<Role>();
-            onPath.add(dest);
-        }
-
-	/**
-	 * Does nothing.
-	 * @param r a Role, a dummy
-	 */
-        public void node(Role r) { }
-
-	/**
-	 * Do the collection on each node we visit.
-	 * @param r a Role, the current node in the DFS.
-	 */
-        public void node_after(Role r) {
-            for (Credential c : g.getInEdges(r)) {
-                Role child = c.tail();
-
-                if (onPath.contains(child)) {
-                    Credential edge = g.findEdge(child, r);
-                    if (edge == null)
-                        throw new RuntimeException("Credential missing from " +
-				"parent graph, state is messed up");
-
-                    ng.addEdge(edge, child, r);
-                    onPath.add(r);
-
-                    // For linking roles, collect the whole subgraph of the
-                    // authorizer
-                    if (r.is_linking()) {
-                        CollectQueryPath link = new CollectQueryPath(ng, 
-				new Role(child.principal_part()));
-                        reverse_dfs(new Role(r.principal_part()), link);
-                    }
-
-                    // intersection: collect the subgraph of each prereq
-                    else if (r.is_intersection()) {
-                        CollectQueryPath prereq_finder = 
-			    new CollectQueryPath(ng, child);
-			try {
-			    for (Role prereq : r.prereqs())
-				reverse_dfs(prereq, prereq_finder);
-			}
-			catch (ABACException ignored ) { }
-                    }
-                }
-            }
-        }
-    }
-
-    /**
-     * Collect the path that a node can reach. It includes subgraphs that imply
-     * the linked/intersection edges traversed.
-     */
-    private class CollectReversePath extends CollectQueryGraph {
-	/**
-	 * Initialize the collection graph.
-	 * @param g a Graph that collects the results.
-	 */
-        public CollectReversePath(Graph<Role,Credential> g) {
-            super(g);
-        }
-
-        /**
-	 * add all of the node's parents
-	 * @param r a Role, the current node being visited
-	 */
-        public void node(Role r) {
-            for (Credential c : g.getOutEdges(r)) {
-                Role head = g.getDest(c);
-                Credential cred = g.findEdge(r, head);
-                if (cred == null)
-                    throw new RuntimeException("Credential missing from " + 
-			    "parent graph, state is messed up");
-
-                ng.addEdge(cred, r, head);
-            }
-        }
-
-	/**
-	 * Do the collection on each node we visit.
-	 * @param r a Role, the current node in the DFS.
-	 */
-        public void node_after(Role r) {
-            for (Credential c : g.getOutEdges(r)) {
-                Role parent = g.getDest(c);
-
-                // if any of the links we follow is from a linking node, copy
-                // the subgraph that implies said link
-                if (parent.is_linking()) {
-                    CollectQueryPath link = new CollectQueryPath(ng, 
-			    new Role(r.principal_part()));
-                    reverse_dfs(new Role(parent.principal_part()), link);
-                }
-
-                // intersection roles do not need to be treated specially
-                // because the forward path from the principal will traverse all
-                // edges that imply the edge to the intersection node
-            }
-        }
-    }
-
-    /**
-     * Interface to the reverse_dfs member that does allocates the visited map
-     * so the user doesn't have to.
-     * @param r a Role from which to start the search
-     * @param f a DfsFcn that customizes the search operation
-     */
-    private void reverse_dfs(Role r, DfsFcn f) {
-        reverse_dfs(r, new HashSet<Role>(), f);
-    }
-
-    /**
-     * Member function to walk the edges in reverse from a given Role.  Each
-     * Role is visited once and has the node() function of the dfs_fcn called
-     * on it.  Order is not guaranteed.
-     * @param r a Role from which to start the search
-     * @param visited a HashSet of Roles that tells which nodes have been
-     * visited.
-     * @param f a DfsFcn that customizes the search operation
-     */
-    private void reverse_dfs(Role r, HashSet<Role> visited,
-            DfsFcn f) {
-        if (visited.contains(r)) return;
-
-        f.node(r);
-        visited.add(r);
-
-        for (Credential c : g.getInEdges(r)) 
-            reverse_dfs(g.getSource(c), visited, f);
-        f.node_after(r);
-    }
-
-    /**
-     * Interface to the forward_dfs member that allocates the visited map so
-     * the user doesn't have to.
-     * @param r a Role from which to start the search
-     * @param f a DfsFcn that customizes the search operation
-     */
-    private void forward_dfs(Role r, DfsFcn f) {
-        forward_dfs(r, new HashSet<Role>(), f);
-    }
-
-    /**
-     * Member function to walk the edges from a given Role. Each Role is
-     * visited once and has the node() function of the dfs_fcn called on it.
-     * Order is not guaranteed
-     * @param r a Role from which to start the search
-     * @param visited a HashSet of Roles that tells which nodes have been
-     * visited.
-     * @param f a DfsFcn that customizes the search operation
-     */
-    private void forward_dfs(Role r, Set<Role> visited, DfsFcn f) {
-        if (visited.contains(r)) return;
-
-        f.node(r);
-        visited.add(r);
-
-        for (Credential c : g.getOutEdges(r))
-            forward_dfs(g.getDest(c), visited, f);
-        f.node_after(r);
+	    }
+	}
+	/* If foundDest is true, we know that the path from src to dest is
+	 * there, so backtrack from dest to source, adding to path as we go.
+	 * If we didn't find anything return the BFS as a partial proof.  Note
+	 * that whatever direction the search progresses, this builds a return
+	 * graph that has edges directed the same way as edges in g.
+	 *
+	 * If path is null, don't add the nodes to it (duh) but do decide which
+	 * nodes would be kept in case dir needs that info.  E.g.
+	 * findPrincipals does not need the path to the principals, just their
+	 * identity.
+	 */
+	if ( foundDest ) {
+	    Role v = dest;
+	    if (path != null && !path.containsVertex(dest)) 
+		path.addVertex(dest);
+
+	    while (!v.equals(src)) {
+		Collection<Credential> backEdges = dir.backwardEdges(bfs, v);
+
+		if (backEdges.size() != 1 )
+		    System.err.println("What!?");
+		for (Credential e: backEdges) {
+		    Role u = dir.getSource(bfs, e);
+
+		    if ( path != null && !path.containsVertex(u)) 
+			path.addVertex(u);
+		    if ( path != null && !path.containsEdge(e)) 
+			path.addEdge(e, e.tail(), e.head());
+		    dir.keptEdge(e);
+		    v = u;
+		}
+	    }
+	} else {
+	    for (Role v: bfs.getVertices() )
+		if (path != null && !path.containsVertex(v)) 
+		    path.addVertex(v);
+	    for (Credential e: bfs.getEdges()) {
+		if ( path != null && !path.containsEdge(e)) 
+		    path.addEdge(e, e.tail(), e.head());
+		dir.keptEdge(e);
+	    }
+	}
+	return foundDest || dest == null;
     }
 }
