Index: libabac/abac_graph.c
===================================================================
--- libabac/abac_graph.c	(revision 342e28fe01e337ed4bef82e454ff69e7c9a80067)
+++ libabac/abac_graph.c	(revision 0eb4a8e20d9a64cbbd60a78e405919407e895a6c)
@@ -15,4 +15,7 @@
 
     abac_list_t *edges;
+
+    // only relevant to intersection edges
+    abac_list_t *prereqs;
 
     UT_hash_handle hh;
@@ -42,4 +45,14 @@
     int dirty;
 };
+
+// ugghhhghhhghh need this for intersections
+abac_list_t *abac_credential_prereqs(abac_credential_t *);
+
+/**
+ * True iff a vertex is linking.
+ */
+static inline int _vertex_is_intersection(abac_vertex_t *vertex) {
+    return vertex->role == NULL;
+}
 
 /**
@@ -95,4 +108,7 @@
         vertex->edges = abac_list_new();
 
+        // for intersections, always NULL on normal vertices
+        vertex->prereqs = NULL;
+
         // add it to the vertices
         HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
@@ -100,4 +116,73 @@
 
     return vertex;
+}
+
+/**
+ * convert a list of prereqs to a string suitable for use as a hash key
+ * format: role & role & ... & role
+ */
+static char *_prereq_key(abac_list_t *prereqs) {
+    abac_role_t *role;
+    char *string;
+    int i = 0, size;
+    size_t len = 0;
+
+    // find the required size
+    abac_list_foreach(prereqs, role,
+        len += strlen(abac_role_string(role)) + 3;
+    );
+
+    string = abac_xmalloc(len);
+    string[0] = '\0';
+
+    size = abac_list_size(prereqs);
+
+    // concat the names
+    abac_list_foreach(prereqs, role,
+        strcat(string, abac_role_string(role));
+        if (i++ < size - 1)
+            strcat(string, " & ");
+    );
+
+    return string;
+}
+
+/**
+ * Find/create intersection vertex. Only called by abac_graph_add_credential.
+ */
+static abac_vertex_t *_get_intersection_vertex(abac_graph_t *graph, abac_credential_t *cred) {
+    abac_role_t *role, *tail_role;
+    abac_vertex_t *vertex;
+
+    abac_list_t *prereqs = abac_credential_prereqs(cred);
+    char *string = _prereq_key(prereqs);
+    HASH_FIND_STR(graph->vertices, string, vertex);
+
+    // add the vertex if it doesn't exist
+    if (vertex == NULL) {
+        vertex = abac_xmalloc(sizeof(abac_vertex_t));
+        vertex->role = NULL;
+        vertex->name = string;
+
+        // create the list of edges
+        vertex->edges = abac_list_new();
+
+        // for intersections, will be populated first time it's created
+        vertex->prereqs = abac_list_new();
+
+        // add each prereq to the vertex
+        abac_list_foreach(prereqs, tail_role,
+            abac_vertex_t *tail_vertex = _get_vertex(graph, tail_role);
+            abac_list_add(vertex->prereqs, tail_vertex);
+        );
+
+        // add it to the vertices
+        HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
+    }
+    else
+        free(string); // already exists, get rid of useless memory
+
+    return vertex;
+
 }
 
@@ -114,13 +199,16 @@
     abac_role_t *tail = abac_credential_tail(cred);
 
-    // TODO: handle intersections properly
-    if (tail == NULL)
-        return 0;
-
     // a valid credential must have a role for the head
     if (!abac_role_is_role(head)) return 0;
 
     head_vertex = _get_vertex(graph, head);
-    tail_vertex = _get_vertex(graph, tail);
+
+    // tail is a normal role
+    if (tail != NULL)
+        tail_vertex = _get_vertex(graph, tail);
+
+    // intersection
+    else
+        tail_vertex = _get_intersection_vertex(graph, cred);
 
     // make sure we don't insert the same edge twice (ugh)
@@ -187,67 +275,76 @@
 
     for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
-        // we only care about linking roles
-        if (!abac_role_is_linking(vertex->role))
-            continue;
-
-        // linking roles take the form A.r1.r2
-        char *A_r1 = abac_role_linked_role(vertex->role);
-        char *r2 = abac_role_role_name(vertex->role);
-
-        // find the linked role in the graph
-        abac_vertex_t *A_r1_vertex;
-        HASH_FIND_STR(graph->vertices, A_r1, A_r1_vertex);
-        if (A_r1_vertex == NULL)
-            continue;
-
-        // find the principals that have A.r1
-        abac_set_t *principals = _find_principals(graph, A_r1_vertex);
-        char *B;
-
-        abac_list_t *elts = abac_set_elements(principals);
-
-        // and add a link for each B.r2 to A.r1.r2
-        abac_list_foreach(elts, B,
-            int B_len = strlen(B);
-            int r2_len = strlen(r2);
-
-            // create the string B.r2, thx C
-            char *B_r2 = malloc(B_len + r2_len + 2);
-            memcpy(B_r2, B, B_len);
-            B_r2[B_len] = '.';
-            memcpy(B_r2 + B_len + 1, r2, r2_len);
-            B_r2[B_len + r2_len + 1] = 0;
-
-            abac_vertex_t *B_r2_vertex;
-            HASH_FIND_STR(graph->vertices, B_r2, B_r2_vertex);
-
-            // add an edge if the principal's granted it to someone
-            if (B_r2_vertex) {
-                debug_printf("adding edge from %s to %s\n", B_r2, abac_role_string(vertex->role));
-                abac_edge_t *edge = abac_xmalloc(sizeof(abac_edge_t));
-                edge->vertex = B_r2_vertex;
-                edge->credential = NULL;
-                abac_list_add(vertex->edges, edge);
-
-                // add to list of derived edges
-                abac_derived_t *derived = abac_xmalloc(sizeof(abac_derived_t));
-                derived->key.head = vertex;
-                derived->key.tail = edge;
-                HASH_ADD(hh, graph->derived, key, sizeof(abac_derived_key_t), derived);
-            }
+        // intersection
+        if (_vertex_is_intersection(vertex)) {
+            // TODO:
+            // for each prereq edge:
+            //     find principals that have the edge
+            // find intersection of all sets
+            // for each principal B in intersection:
+            //     add link
+        }
+
+        // linking role
+        else if (abac_role_is_linking(vertex->role)) {
+            // linking roles take the form A.r1.r2
+            char *A_r1 = abac_role_linked_role(vertex->role);
+            char *r2 = abac_role_role_name(vertex->role);
+
+            // find the linked role in the graph
+            abac_vertex_t *A_r1_vertex;
+            HASH_FIND_STR(graph->vertices, A_r1, A_r1_vertex);
+            if (A_r1_vertex == NULL)
+                continue;
+
+            // find the principals that have A.r1
+            abac_set_t *principals = _find_principals(graph, A_r1_vertex);
+            char *B;
+
+            abac_list_t *elts = abac_set_elements(principals);
+
+            // and add a link for each B.r2 to A.r1.r2
+            abac_list_foreach(elts, B,
+                int B_len = strlen(B);
+                int r2_len = strlen(r2);
+
+                // create the string B.r2, thx C
+                char *B_r2 = malloc(B_len + r2_len + 2);
+                memcpy(B_r2, B, B_len);
+                B_r2[B_len] = '.';
+                memcpy(B_r2 + B_len + 1, r2, r2_len);
+                B_r2[B_len + r2_len + 1] = 0;
+
+                abac_vertex_t *B_r2_vertex;
+                HASH_FIND_STR(graph->vertices, B_r2, B_r2_vertex);
+
+                // add an edge if the principal's granted it to someone
+                if (B_r2_vertex) {
+                    debug_printf("adding edge from %s to %s\n", B_r2, abac_role_string(vertex->role));
+                    abac_edge_t *edge = abac_xmalloc(sizeof(abac_edge_t));
+                    edge->vertex = B_r2_vertex;
+                    edge->credential = NULL;
+                    abac_list_add(vertex->edges, edge);
+
+                    // add to list of derived edges
+                    abac_derived_t *derived = abac_xmalloc(sizeof(abac_derived_t));
+                    derived->key.head = vertex;
+                    derived->key.tail = edge;
+                    HASH_ADD(hh, graph->derived, key, sizeof(abac_derived_key_t), derived);
+                }
 
 #ifdef DEBUG
-            debug_printf("    incoming edges for %s\n", abac_role_string(vertex->role));
-            abac_edge_t *cur;
-            abac_list_foreach(vertex->edges, cur,
-                debug_printf("        %s (%s)\n", abac_role_string(cur->vertex->role), cur->vertex->name);
+                debug_printf("    incoming edges for %s\n", abac_role_string(vertex->role));
+                abac_edge_t *cur;
+                abac_list_foreach(vertex->edges, cur,
+                    debug_printf("        %s (%s)\n", abac_role_string(cur->vertex->role), cur->vertex->name);
+                );
+#endif
+
+                free(B_r2);
             );
-#endif
-
-            free(B_r2);
-        );
-
-        abac_list_free(elts);
-        abac_set_free(principals);
+
+            abac_list_free(elts);
+            abac_set_free(principals);
+        }
     }
 
