reups_lib/db/
graph.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
4 * Copyright Nate Lust 2018*/
5
6pub extern crate petgraph;
7use fnv::FnvHashMap;
8
9use std::collections::HashSet;
10
11use crate::db::graph::petgraph::visit::Walker;
12use crate::db::table;
13use crate::db::DB;
14use std::fmt;
15
16/**!
17  The module graph contains all the machinery for turning products described
18  by table files into a relational graph of those products.
19 */
20
21/// Describes if a node in the graph represents an optional dependency, or
22/// a required dependency
23#[derive(Clone)]
24pub enum NodeType {
25    Required,
26    Optional,
27}
28
29/// A string representation of a node in the graph
30impl fmt::Debug for NodeType {
31    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
32        match self {
33            NodeType::Required => write!(f, "Required Node"),
34            NodeType::Optional => write!(f, "Optional Node"),
35        }
36    }
37}
38
39/// Graph is a structure that holds the relational information between products, and
40/// has methods to add products to the relational graph
41#[derive(Debug)]
42pub struct Graph<'a> {
43    _graph: petgraph::Graph<NodeType, String>,
44    _name_map: FnvHashMap<String, petgraph::graph::NodeIndex<petgraph::graph::DefaultIx>>,
45    _index_map: FnvHashMap<petgraph::graph::NodeIndex<petgraph::graph::DefaultIx>, String>,
46    _db: &'a DB,
47    _processed: HashSet<String>,
48}
49
50impl<'a> Graph<'a> {
51    /// Created a new graph that will be associated with the specified database
52    pub fn new(db: &'a DB) -> Graph {
53        Graph {
54            _graph: petgraph::Graph::<NodeType, String>::new(),
55            _name_map: FnvHashMap::default(),
56            _index_map: FnvHashMap::default(),
57            _db: db,
58            _processed: HashSet::new(),
59        }
60    }
61    /// Resolves the index of a graph node into a string of the product name at that node
62    pub fn get_name(
63        &self,
64        number: petgraph::graph::NodeIndex<petgraph::graph::DefaultIx>,
65    ) -> String {
66        return self._index_map[&number].clone();
67    }
68
69    /// Add a product to the graph, or update the node type of that product if it already exists
70    pub fn add_or_update_product(&mut self, name: String, node_type: NodeType) {
71        match self.has_product(&name) {
72            true => {
73                let name_index = self._name_map[&name];
74                if let (&NodeType::Optional, NodeType::Required) =
75                    (self._graph.node_weight(name_index).unwrap(), node_type)
76                {
77                    self._graph[name_index] = NodeType::Required;
78                }
79            }
80            false => {
81                let index = self._graph.add_node(node_type);
82                self._name_map.insert(name.clone(), index);
83                self._index_map.insert(index, name);
84            }
85        }
86    }
87
88    /// Checks if the graph contains a given product
89    pub fn has_product(&self, name: &String) -> bool {
90        self._name_map.contains_key(name)
91    }
92
93    /// Returns all the different versions of a product that the graph describes.
94    /// I.E. different nodes in the graph may point to a given product as a dependency
95    /// with different version of that dependency listed as a requirement
96    pub fn product_versions(&self, name: &String) -> Vec<&String> {
97        let mut products = Vec::new();
98        let index = self._name_map[name];
99        let direction = petgraph::Direction::Incoming;
100        for edge in self._graph.edges_directed(index, direction) {
101            products.push(edge.weight());
102        }
103        products
104    }
105
106    /// Determines if a given node is listed as an optional node in the graph
107    pub fn is_optional(&self, name: &String) -> bool {
108        let node = self._name_map[name];
109        let weight = self._graph.node_weight(node);
110        match weight {
111            Some(NodeType::Optional) => true,
112            _ => false,
113        }
114    }
115
116    /// Connects two products (nodes) in the graph together with a specific version. Note that this
117    /// is a directional graph so the version requirement will point from the source to the target
118    /// node
119    pub fn connect_products(
120        &mut self,
121        source: &String,
122        target: &String,
123        version: String,
124    ) -> Result<(), &str> {
125        if !self.has_product(source) {
126            return Err("The specified source is not in the graph");
127        }
128        if !self.has_product(target) {
129            return Err("The specified target is not in the graph");
130        }
131        let source_index = self._name_map[source];
132        let target_index = self._name_map[target];
133        self._graph.add_edge(source_index, target_index, version);
134        Ok(())
135    }
136
137    /// Add a product to the graph specified by a given tag. This tag is looked up in the database
138    /// associated with this graph and resolved into a table file. Optionally add in the dependencies from the table file if recurse is true
139    pub fn add_product_by_tag(
140        &mut self,
141        product: String,
142        tag: &Vec<&String>,
143        version_type: table::VersionType,
144        node_type: NodeType,
145        recurse: bool,
146    ) {
147        if !self._processed.contains(&product) {
148            let result = self._db.get_table_from_tag(&product, tag.clone());
149            if let Some(table) = result {
150                self.add_table(&table, version_type, node_type, Some(tag), recurse);
151            }
152        }
153    }
154
155    /// Add a product to the graph specified by a given version. This version is looked up in the database
156    /// associated with this graph and resolved into a table file. Optionally add in the
157    /// dependencies from the table file if recurse is true
158    pub fn add_product_by_version(
159        &mut self,
160        product: String,
161        version: String,
162        version_type: table::VersionType,
163        node_type: NodeType,
164        recurse: bool,
165    ) {
166        if !self._processed.contains(&product) {
167            let result = self._db.get_table_from_version(&product, &version);
168            if let Some(table) = result {
169                self.add_table(&table, version_type, node_type, None, recurse);
170            }
171        }
172    }
173
174    /// Add a specific table into the graph of products. Optionally add in the
175    /// dependencies from the table file if recurse is true
176    pub fn add_table(
177        &mut self,
178        table: &table::Table,
179        version_type: table::VersionType,
180        node_type: NodeType,
181        tag: Option<&Vec<&String>>,
182        recurse: bool,
183    ) {
184        let top = &table.name;
185
186        self.add_or_update_product(top.clone(), node_type);
187
188        let dependencies = match version_type {
189            table::VersionType::Exact => table.exact.as_ref(),
190            table::VersionType::Inexact => table.inexact.as_ref(),
191        };
192        // This means that there are no dependencies of the required type, and so the function
193        // should return.
194        if let None = dependencies {
195            return;
196        }
197        // If there are dependencies for the version type, loop over the required and optional
198        // dependencies
199        let dep_unwrap = dependencies.unwrap();
200        for (dep_vec, node_type) in vec![&dep_unwrap.required, &dep_unwrap.optional]
201            .iter()
202            .zip(vec![NodeType::Required, NodeType::Optional])
203        {
204            for (k, v) in dep_vec.iter() {
205                self.add_or_update_product(k.clone(), node_type.clone());
206                if let Err(_) = self.connect_products(top, &k, v.clone()) {
207                    eprintln!("There was an issue connecting products in the graph, topological walks my be incorrect");
208                }
209
210                match (&version_type, tag, recurse) {
211                    (table::VersionType::Inexact, Some(tag_vec), true) => self.add_product_by_tag(
212                        k.clone(),
213                        tag_vec,
214                        table::VersionType::Inexact,
215                        node_type.clone(),
216                        recurse,
217                    ),
218                    (table::VersionType::Exact, _, true) => self.add_product_by_version(
219                        k.clone(),
220                        v.clone(),
221                        table::VersionType::Exact,
222                        node_type.clone(),
223                        recurse,
224                    ),
225                    _ => {}
226                }
227            }
228        }
229        self._processed.insert(top.clone());
230    }
231
232    /// Iterates though the nodes of the graph
233    pub fn iter(
234        &self,
235    ) -> petgraph::visit::WalkerIter<
236        petgraph::visit::Topo<
237            <petgraph::Graph<NodeType, String> as petgraph::visit::GraphBase>::NodeId,
238            <petgraph::Graph<NodeType, String> as petgraph::visit::Visitable>::Map,
239        >,
240        &petgraph::Graph<NodeType, String>,
241    > {
242        let topo = petgraph::visit::Topo::new(&self._graph);
243        return topo.iter(&self._graph);
244    }
245}
reups_lib/db/graph.rs

reups_lib/db/
graph.rs
