source: fedd/abac-src/rbtm/engine/GraphEngine.java @ df783c1

package edu.stanford.peer.rbtm.engine;

import java.util.*;

import edu.stanford.peer.rbtm.RBTMConstants;
import edu.stanford.peer.rbtm.credential.*;
import edu.stanford.peer.rbtm.util.*;

/**
 * A graph engine is a proof graph which may optionally contain a predicate
 * function. This implementation is a tightly coupled directed credential
 * graph and credential index. 
 */
public class GraphEngine
    implements java.io.Serializable, ProofGraph, RBTMConstants
{
    static final public Iterator emptyIt = new ArrayList(1).iterator();
    static final public Collection emptyCollection = new ArrayList(1);

    /** stores all the credentials */
    private HashSet credentials = new HashSet();

    /** an index from issuers to credential collections */
    private HashMap indexByIssuer = new HashMap();

    /** an index from roles to credential collections */
    private HashMap indexByRole = new HashMap();

    /** an index from role name to credential collections */
    private HashMap indexByRoleName = new HashMap();

    /** an index from subjects to collections of credentials */
    private HashMap indexBySubject = new HashMap();

    /** predicate function which could be null */
    private Predicate pred = null;

    private int track;
    
    private SolutionFilter solutionFilter;

    // a proof queue
    transient private ProofQueue proofQueue = new SimpleProofQueue();
    
    transient private HashMap    nodeTable = new HashMap();


    public GraphEngine(Set creds, int tt, SolutionFilter filter, Predicate p) {
        this(creds, tt, filter);
        pred = p;
    }
    
    public GraphEngine(Set creds, int trackType, SolutionFilter filter)
    {
        this(trackType, filter);
        addCredentials(creds);
    }

    public GraphEngine(int trackType, SolutionFilter filter) {
        track = trackType;
        solutionFilter = (filter == null)? new DefaultSolutionFilter(): filter;
    }

    public GraphEngine(Predicate p) {
        this();
        pred = p;
    }

    public GraphEngine() {
        this(TRACK_ALL, null);
    }
    

        public void reinit() {
                proofQueue = new SimpleProofQueue();
                nodeTable = new HashMap();
        }

        synchronized public void addCredentials(Collection credentials) {
                reinit();
                Iterator credIt = credentials.iterator();
                while (credIt.hasNext()) {
                        addCredential((StaticCredential)credIt.next());
                }
        }

        synchronized public void removeCredentials(Collection credentials) {
                reinit();
                Iterator credIt = credentials.iterator();
                while (credIt.hasNext()) {
                        removeCredential((StaticCredential)credIt.next());
                }
        }

    synchronized public boolean addCredential(StaticCredential cred) {
        // Make sure that no duplicate Credential exists
        if (credentials.contains(cred)) {
                Debug.debugInfo("trying to add existing credential: " + cred);
            return false;
        }
        Debug.debugInfo("adding credential: " + cred);
        credentials.add(cred);
                addIndexFor(cred);
                ProofNode node = getNode(cred.getDefinedRole());
                if (node != null) {
                        node.invalidateBackward();
                }
                node = getNode(cred.getSubject());
                if (node != null) {
                        node.invalidateForward();
                }
            return true;
    }

        synchronized public void removeCredential(StaticCredential cred) {
                if (credentials.contains(cred)) {
                        Debug.debugInfo("removing credential: " + cred);
                        reinit();
                        credentials.remove(cred);
                        removeIndexFor(cred);
                } else {
                        Debug.debugInfo("trying to remove nonexistent credential: " + cred);
                        //// throw Exception
                }
        }

        private void addIndexFor(StaticCredential cred) 
        {
                Entity e = cred.getIssuer();
                ArrayList credList = (ArrayList)indexByIssuer.get(e);
                if (credList == null) {
                        credList = new ArrayList(40);
                        indexByIssuer.put(e, credList);
                }
                credList.add(cred);

        // Code to deal with indexByRole
        Role r = cred.getDefinedRole();
        credList = (ArrayList) indexByRole.get(r);
        if (credList == null) {
            credList = new ArrayList(10);
            indexByRole.put(r, credList);
        }
        credList.add(cred);

        // Code to deal with indexByRoleName
        RoleName name = r.getName();
        credList = (ArrayList) indexByRoleName.get(name);
        if (credList == null) {
            credList = new ArrayList(10);
            indexByRoleName.put(name, credList);
        }
        credList.add(cred);

        EntityExpression subject = cred.getSubject();
                  if(subject instanceof Intersection) {
                                Iterator parts = ((Intersection)subject).getParts();
                                while(parts.hasNext()) {
                                         EntityExpression partialSolution = 
                                                  (EntityExpression)parts.next();
                                         credList = (ArrayList) indexBySubject.get(subject);
                                         if (credList == null) {
                                                  credList = new ArrayList(10);
                                                  indexBySubject.put(partialSolution, credList);
                                         }
                                         credList.add(cred);
                                }
                  } else {
                                credList = (ArrayList) indexBySubject.get(subject);
                                if (credList == null) {
                                         credList = new ArrayList(10);
                                         indexBySubject.put(subject, credList);
                                }
                                credList.add(cred);
                  }
    }

        private void removeIndexFor(StaticCredential cred) 
        {
                ((ArrayList)indexByIssuer.get(cred.getIssuer())).remove(cred);
                ((ArrayList)indexByRole.get(cred.getDefinedRole())).remove(cred);
                ((ArrayList)indexBySubject.get(cred.getSubject())).remove(cred);
        }

        /*
        public void addRole(Role role) {
                if (! indexByRole.containsKey(role)) {
                        indexByRole.put(role, new ArrayList());
                }
        }
        */

         /**
          * Repository function: finds all credentials issued by entity e.
          */
    synchronized public Collection getCredentialsIssuedBy(Entity e) {
        Collection credentials = (Collection)indexByIssuer.get(e);
                if (credentials == null) {
                        return emptyCollection;
                } else {
                return credentials;
                }
    }


    synchronized public Iterator findCredentialsDefiningRole(RoleName r) 
    {
        ArrayList credList = (ArrayList) indexByRoleName.get(r);
        if (credList == null) {
            return emptyIt;
        } else {
            return credList.iterator();
        }
    }

    synchronized public Iterator findCredentialsDefiningRole(Role r) 
    {
        ArrayList credList = (ArrayList) indexByRole.get(r);
        if (credList == null) {
            return emptyIt;
        } else {
            return credList.iterator();
        }
    }

    synchronized public Iterator findCredentialsBySubject(EntityExpression subject)
    {
        ArrayList credList = (ArrayList) indexBySubject.get(subject);
        if (credList == null) {
            return emptyIt;
        } else {
            return credList.iterator();
        }
    }

         synchronized public Iterator findCredentialsByPartialSubject(EntityExpression subject) 
         {
                  // Using a vector copies the arraylist so we don't remove from it
        ArrayList credList = (ArrayList)indexBySubject.get(subject);
        if (credList == null) {
            return emptyIt;
        }
                  credList = (ArrayList)credList.clone();
                  Iterator i = credList.iterator(); 
                  while(i.hasNext()) {  // remove credential which aren't intersections
                                StaticCredential cred = (StaticCredential)i.next();
                                if(!(cred.getSubject() instanceof Intersection)) {
                                         i.remove();
                                         //System.out.println("Removing " + cred.getSubject());
                                } else {
                                         //System.out.println("Not Removing " + cred.getSubject());
                                }
                  }
                  return credList.iterator();
         }

        /*    
    boolean hasCredentialsForSubject(EntityExpression re) {
        return findCredentialsBySubject(re).hasNext();
    }
        */

    // Find out all Roles that roleExp belongs to
    synchronized public ResultEvidenceMap forwardSearch(EntityExpression roleExp) {
        ProofNode goalNode = addForwardNode(roleExp);
        while (proofQueue.hasUnexploredForwardNodes()) {
            proofQueue.nextUnexploredForwardNode().forwardProcess();
        }
        return goalNode.getForwardSolutions();
    }

    // Find out all members of roleExp
    synchronized public ResultEvidenceMap backwardSearch(EntityExpression roleExp) {
        ProofNode goalNode = addBackwardNode(roleExp);
        while (proofQueue.hasUnexploredBackwardNodes()) {
            proofQueue.nextUnexploredBackwardNode().backwardProcess();
        }
        return goalNode.getBackwardSolutions();
    }

    public ProofNode addForwardNode(EntityExpression roleExp) {
        ProofNode node = addNode(roleExp);
        proofQueue.addForwardNode(node);
        return node;
    }

    public ProofNode addBackwardNode (EntityExpression roleExp) {
        ProofNode node = addNode(roleExp);
        proofQueue.addBackwardNode(node);
        return node;
    }

    /**
     * Add a node corresponding to a role expression, make sure that the 
     * node is not added twice.
     */
    private ProofNode addNode (EntityExpression roleExp) {
        ProofNode node = (ProofNode)nodeTable.get(roleExp);
        if (node == null) {
            node = createProofNode(roleExp);
            nodeTable.put(roleExp, node);
        }
        return node;
    }

    private ProofNode getNode(EntityExpression roleExp) {
        return (ProofNode)nodeTable.get(roleExp);
    }

    private ProofNode createProofNode (EntityExpression roleExp) {
        if (roleExp instanceof Role) {
            return new RoleProofNode(this, (Role)roleExp, track);
        } else if (roleExp instanceof LinkedRole) {
            return new LinkedRoleProofNode(this, (LinkedRole)roleExp, track);
        } else if (roleExp instanceof Intersection) {
            return new IntersectionProofNode(this,(Intersection)roleExp,track);
        } else {
            return new EntityProofNode(this, (Entity)roleExp, track);
        }
    }

    public ForwardSolution getForwardSolution(EntityExpression re) {
                return solutionFilter.getForwardSolution(re);
    }

    public BackwardSolution getBackwardSolution(EntityExpression re) {
            return solutionFilter.getBackwardSolution(re);
    }

    public String toString() {
        return "credentials=" + credentials.toString() + "\n" +
                           "indexByIssuer=" + indexByIssuer.toString() + "\n" +
               "indexByRole=" + indexByRole.toString() + "\n" +
                   "indexBySubject=" + indexBySubject.toString();
    }
        
        private String getSubjectIndexs()
        {
                StringBuffer outBuf = new StringBuffer();
                Iterator keyIt = indexBySubject.keySet().iterator();
                while (keyIt.hasNext()) {
                        Object o = keyIt.next();
                        if (o instanceof Role) {
                                outBuf.append("Role ").append(o.toString()).append("\n");
                                Role r = (Role) o;
                                outBuf.append("Base is ").append(r.getBase().getClass()).append("\n");
                                outBuf.append("RoleName is ").append(r.getName().getClass()).append("\n");
                        }
                }
                return outBuf.toString();
        }
    
    public Predicate getPredicate() { return pred; }

    public HashSet getChain(EntityExpression source, EntityExpression target) {
        System.out.println("source = " + source);
        System.out.println("target = " + target);    
        ProofNode sourceNode = getNode(source);
        System.out.println("node table = " + nodeTable);
        if(sourceNode != null) {
            return sourceNode.getChain(0, target);
    }
        return null;
    }
    
    /** accessor method added to support distributed discovery */
    protected HashSet getCredentials() { return credentials; }
}