diff options
Diffstat (limited to '')
| -rw-r--r-- | crates/secd/src/auth/z/graph.rs | 209 |
1 files changed, 209 insertions, 0 deletions
diff --git a/crates/secd/src/auth/z/graph.rs b/crates/secd/src/auth/z/graph.rs new file mode 100644 index 0000000..9ca045b --- /dev/null +++ b/crates/secd/src/auth/z/graph.rs @@ -0,0 +1,209 @@ +use std::collections::{HashSet, VecDeque}; + +type NodeIdx = usize; +type EdgeIdx = usize; + +struct RelationGraph { + nodes: Vec<Node>, + edges: Vec<Edge>, +} + +#[derive(Hash, PartialEq, Eq)] +struct Node { + id: u64, + is_namespace: bool, + edge_list_head: Option<EdgeIdx>, +} + +struct Edge { + dst: NodeIdx, + op: Option<Operator>, + next_edge: Option<EdgeIdx>, +} + +enum Operator { + And, + Or, + Difference, + Complement, + AndAll, + OrAll, + DifferenceAll, + ComplementAll, +} + +impl RelationGraph { + pub fn new() -> Self { + // As I think about how to serialize this graph, when reading from the DB + // I should chunk up the namespaces so that I can read-on-demand when I + // encounter a namespace that has not yet been loaded, and in this way + // I don't need to deal with the entire graph... + // + // but that's a totally unnecessary fun optimization. + RelationGraph { + nodes: vec![], + edges: vec![], + } + } + + pub fn add_node(&mut self, id: u64, is_namespace: bool) -> NodeIdx { + let idx = self.nodes.len(); + self.nodes.push(Node { + id, + is_namespace, + edge_list_head: None, + }); + idx + } + + pub fn add_edge( + &mut self, + src: NodeIdx, + dst: NodeIdx, + op: Option<Operator>, + follow: Option<NodeIdx>, + ) { + let edge_idx = self.edges.len(); + let node = &mut self.nodes[src]; + // TODO: dupe check + self.edges.push(Edge { + dst, + op, + next_edge: node.edge_list_head, + }); + node.edge_list_head = Some(edge_idx); + } + + // doc:2#viewer@user:1 + pub fn find_leaves(&self, src: NodeIdx, filterIdx: Option<NodeIdx>) -> Vec<NodeIdx> { + let mut all_leaves = vec![]; + // let mut and_leaves = vec![]; + // let mut exc_leaves = vec![]; + + // the output should basically be leaves to look up + // for example + // the leaves of doc might be (user), <(organization, admin)>, <(role, foo)> + // and since (organization, admin) has leaves (user) as well + // if the user is in that final set, then they are valid + // and those leaves would be queried as relation tuples saved in the DB + + println!("HERE I AM"); + + let start = self.nodes.get(src); + let mut seen = HashSet::new(); + let mut q = VecDeque::new(); + + seen.insert(start); + q.push_back(start); + + // I need to build a chain of ops + // [AND, OR, OR, AND, OR, ...] + // at each stage, I need to apply the operator chain + while let Some(&Some(node)) = q.iter().next() { + if node.is_namespace { + all_leaves.push(node); + } + + // for edge in edge list + + println!("IN QUEUE\n"); + println!("node: {:?}\n", node.id); + q.pop_front(); + } + println!("DONE"); + + // task...starting at doc_viewer, return all leaf nodes + // to do this.... + // check all children + // if child is OR + // if child is leaf, return child + // else return all of these children + // if child is AND + // if child is leaf, return if also present in all other nodes + // else return all children which are also present in other nodes + // if child is Difference + // if child is leaf, do not include and remove if it part of the user set + // else remove all of these children + + // TOTAL pool of leafs + // Intersection leaves (i.e. ONLY leaves which MUST exist) + // exclusion leaves (i.e. leaves which CANNOT exist) + + // bfs build query... + // execute query + + // start at nodeIdx: doc_viewer + // expand until I find all leaf nodes. + // we are interested in leaf nodes with nodeIdx: user + // return all leaf nodeIdx that match the filter. If no filter provided, return all leaf idx. + + // TODO: optionally build the expansion path by pushing every intermediate step as the bfs is walked. + + // with each step of the bfs, perform the operator. + // e.g. if first step is doc_viewer -> user with operator OR then we have leaf user with operator chain [OR] + // the next step might be doc_viewer -> doc_editor with step OR and doc_editor -> user with step OR, so we have leaf user with chain [OR, OR] + // the next step might be doc_viewer -> doc_auditor with OR + // then doc_auditor -> doc_editor with OR + // then doc_editor -> doc_user with OR + // then doc_editor -> doc_owner + // then doc_auditor -> doc_owner with Difference + // + + todo!() + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn build_graph_test() { + let mut g = RelationGraph::new(); + let user = g.add_node(1, true); + let role = g.add_node(2, true); + let group = g.add_node(3, true); + let doc = g.add_node(4, true); + + let role_member = g.add_node(5, false); + + let group_member = g.add_node(6, false); + let group_admin = g.add_node(7, false); + + let doc_owner = g.add_node(8, false); + let doc_editor = g.add_node(9, false); + let doc_viewer = g.add_node(10, false); + let doc_auditor = g.add_node(11, false); + let doc_parent = g.add_node(12, false); + + g.add_edge(role, role_member, None, None); + g.add_edge(role_member, user, Some(Operator::Or), None); + g.add_edge(role_member, group_member, Some(Operator::Or), None); + + g.add_edge(group, group_member, None, None); + g.add_edge(group, group_admin, None, None); + + g.add_edge(group_member, user, Some(Operator::Or), None); + g.add_edge(group_member, group_admin, Some(Operator::Or), None); + g.add_edge(group_admin, user, Some(Operator::Or), None); + + g.add_edge(doc, doc_owner, None, None); + g.add_edge(doc, doc_editor, None, None); + g.add_edge(doc, doc_viewer, None, None); + g.add_edge(doc, doc_auditor, None, None); + g.add_edge(doc, doc_parent, None, None); + + g.add_edge(doc_owner, user, Some(Operator::Or), None); + g.add_edge(doc_editor, user, Some(Operator::Or), None); + g.add_edge(doc_editor, doc_owner, Some(Operator::Or), None); + g.add_edge(doc_viewer, user, Some(Operator::Or), None); + g.add_edge(doc_viewer, doc_editor, Some(Operator::Or), None); + g.add_edge(doc_viewer, doc_parent, Some(Operator::Or), Some(doc_viewer)); + g.add_edge(doc_viewer, user, Some(Operator::OrAll), None); + g.add_edge(doc_viewer, doc_auditor, Some(Operator::Or), None); + g.add_edge(doc_auditor, doc_editor, Some(Operator::Difference), None); + + g.find_leaves(doc_viewer, None); + assert_eq!(1, 2); + } +} |