// use std::collections::{HashSet, VecDeque}; // type NodeIdx = usize; // type EdgeIdx = usize; // struct RelationGraph { // nodes: Vec, // edges: Vec, // } // #[derive(Hash, PartialEq, Eq)] // struct Node { // id: u64, // is_namespace: bool, // edge_list_head: Option, // } // struct Edge { // dst: NodeIdx, // op: Option, // next_edge: Option, // } // 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, // follow: Option, // ) { // 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) -> Vec { // 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 // 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); // } // }