diff options
Diffstat (limited to 'vendor/gsgdt')
| -rw-r--r-- | vendor/gsgdt/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | vendor/gsgdt/Cargo.toml | 26 | ||||
| -rw-r--r-- | vendor/gsgdt/LICENSE | 21 | ||||
| -rw-r--r-- | vendor/gsgdt/README.md | 33 | ||||
| -rw-r--r-- | vendor/gsgdt/src/diff/diff.rs | 106 | ||||
| -rw-r--r-- | vendor/gsgdt/src/diff/diff_graph.rs | 57 | ||||
| -rw-r--r-- | vendor/gsgdt/src/diff/match_graph.rs | 184 | ||||
| -rw-r--r-- | vendor/gsgdt/src/diff/mod.rs | 7 | ||||
| -rw-r--r-- | vendor/gsgdt/src/graph.rs | 273 | ||||
| -rw-r--r-- | vendor/gsgdt/src/levenshtein.rs | 70 | ||||
| -rw-r--r-- | vendor/gsgdt/src/lib.rs | 12 | ||||
| -rw-r--r-- | vendor/gsgdt/src/multi_graph.rs | 33 | ||||
| -rw-r--r-- | vendor/gsgdt/src/node.rs | 118 | ||||
| -rw-r--r-- | vendor/gsgdt/src/util.rs | 6 | ||||
| -rw-r--r-- | vendor/gsgdt/tests/graph1.json | 513 | ||||
| -rw-r--r-- | vendor/gsgdt/tests/graph2.json | 297 | ||||
| -rw-r--r-- | vendor/gsgdt/tests/helpers.rs | 14 | ||||
| -rw-r--r-- | vendor/gsgdt/tests/small_graph.json | 36 | ||||
| -rw-r--r-- | vendor/gsgdt/tests/test_diff.rs | 57 | ||||
| -rw-r--r-- | vendor/gsgdt/tests/test_graph.rs | 18 | ||||
| -rw-r--r-- | vendor/gsgdt/tests/test_multigraph.rs | 28 |
21 files changed, 1910 insertions, 0 deletions
diff --git a/vendor/gsgdt/.cargo-checksum.json b/vendor/gsgdt/.cargo-checksum.json new file mode 100644 index 000000000..8958e894b --- /dev/null +++ b/vendor/gsgdt/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"40dc18042039b34017b8bda7fc5691dd542fc46878de141645719af58c04662c","LICENSE":"8c5c5319720056c06aa9be4cbf4deeb07a929022862a457cf12d73c7072204d9","README.md":"d2b14f3be64777a3081dbee452eb719e1349c882418791ac4e21f24805ff914a","src/diff/diff.rs":"9a6d2aa5c770e8205b3d401c073dc790a4038ad23f2711b283d9c378f1748f52","src/diff/diff_graph.rs":"9f4d0ddd196e14f7001264d6f720e8b7d6abaa44b11c2477e05c6c2228982608","src/diff/match_graph.rs":"45de7188e76c79e55ffb31c372192969eb13f4a7f5d5b6f352ff3be5c3d02723","src/diff/mod.rs":"d94a9f63cff74c1b6268d074a7c9e13545b105f6707da34936c09fdcd3b5b5ff","src/graph.rs":"baaac14fc6648d6adc237a3dc8eb0bfd54b41ae278e7f091a097c8b4fa179da5","src/levenshtein.rs":"ceeef56f2a6740888d4d54cd1c004f7f6e754d22473478a202bbaa2625ec6050","src/lib.rs":"b97c5fe8d4c473d2596e940659b9a85f94cda173b7f52ccd39b03df683f22d37","src/multi_graph.rs":"971a90d5bf535ec0ce68dac94412c6a71119f3fff955c68379fda38b83e3beb2","src/node.rs":"5478d0a321c11481c2a34fa9ae0ed2dc536071c9cebafc4aab608989a8a7a335","src/util.rs":"c3d447897068b546665dd4bf205a96e858bf2d5455cfbc379982243955b6b9e5","tests/graph1.json":"06f57d4ac2780e463597130d5702567609b188a003321e2c1c669331c5af55fe","tests/graph2.json":"38e01443b996448f1b9b90eaaa1514fbf1f727ad81a94ad9f9455dff599556b2","tests/helpers.rs":"6e9b54931b341540c1fa6b4521525ec663938f62994e9dc8a6ffe488c7a3d0b5","tests/small_graph.json":"38479f33f59062c3629a6ecee491859c639d71310f4c98569eccb7bb818aa338","tests/test_diff.rs":"649cbfadaa4f43f714458ec7a11b2117aade8acfba32ba168b60fe79e93ae29e","tests/test_graph.rs":"76de7a06f06662d947fb37dbdb1c0165fd7c39249a18f660e862910d539dec1e","tests/test_multigraph.rs":"5435f8da3b669a908272ab245b2c4f724fa9add9bd73c63c455a37d359a0c280"},"package":"a0d876ce7262df96262a2a19531da6ff9a86048224d49580a585fc5c04617825"}
\ No newline at end of file diff --git a/vendor/gsgdt/Cargo.toml b/vendor/gsgdt/Cargo.toml new file mode 100644 index 000000000..2a25aa06f --- /dev/null +++ b/vendor/gsgdt/Cargo.toml @@ -0,0 +1,26 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies +# +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +edition = "2018" +name = "gsgdt" +version = "0.1.2" +authors = ["Vishnunarayan K I <appukuttancr@gmail.com>"] +description = "Generic Stringly Typed Graph Datatype" +readme = "README.md" +license = "MIT OR Apache-2.0" +repository = "https://github.com/vn-ki/gsgdt-rs" +[dependencies.serde] +version = "1.0" +features = ["derive"] +[dev-dependencies.serde_json] +version = "1.0" diff --git a/vendor/gsgdt/LICENSE b/vendor/gsgdt/LICENSE new file mode 100644 index 000000000..ead4a7322 --- /dev/null +++ b/vendor/gsgdt/LICENSE @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2020 Vishnunarayan K I + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/vendor/gsgdt/README.md b/vendor/gsgdt/README.md new file mode 100644 index 000000000..a7cb4c6b9 --- /dev/null +++ b/vendor/gsgdt/README.md @@ -0,0 +1,33 @@ +# gsgdt + +**G**eneric **S**tringly typed **G**raph **D**ata**T**ype + +```rust +fn main() { + let label1: String = "bb0__0_3".into(); + let label2: String = "bb0__1_3".into(); + let style: NodeStyle = Default::default(); + + let nodes = vec![ + Node::new( + vec!["_1 = const 1_i32".into(), "_2 = const 2_i32".into()], + label1.clone(), + "0".into(), + style.clone(), + ), + Node::new( + vec!["return".into()], + label2.clone(), + "1".into(), + style.clone(), + ), + ]; + + let g = Graph::new( + "Mir_0_3".into(), + GraphKind::Digraph, + nodes, + vec![Edge::new(label1, label2, "return".into())], + ); +} +``` diff --git a/vendor/gsgdt/src/diff/diff.rs b/vendor/gsgdt/src/diff/diff.rs new file mode 100644 index 000000000..7a85a53c5 --- /dev/null +++ b/vendor/gsgdt/src/diff/diff.rs @@ -0,0 +1,106 @@ +use crate::diff::{match_graphs, DiffGraph, Match}; +use crate::{MultiGraph, Edge, Graph, NodeStyle}; +use std::collections::HashSet; + +/// Returns a MultiGraph containing the diff of the two graphs. +/// To be visualized with dot. +pub fn visualize_diff(d1: &DiffGraph, d2: &DiffGraph) -> MultiGraph { + let matches = match_graphs(d1, d2); + + let mut matched1 = HashSet::new(); + let mut matched2 = HashSet::new(); + let mut partial1 = HashSet::new(); + let mut partial2 = HashSet::new(); + + for mch in matches { + match mch { + Match::Full(m) => { + matched1.insert(m.from); + matched2.insert(m.to); + } + Match::Partial(m) => { + partial1.insert(m.from); + partial2.insert(m.to); + } + } + } + + let added_style = NodeStyle { + title_bg: Some("green".into()), + ..Default::default() + }; + let removed_style = NodeStyle { + title_bg: Some("red".into()), + ..Default::default() + }; + let changed_style = NodeStyle { + title_bg: Some("yellow".into()), + ..Default::default() + }; + let default_style = NodeStyle { + ..Default::default() + }; + + let edges1: Vec<Edge> = d1 + .graph + .edges + .iter() + .map(|e| { + Edge::new( + format!("{}_diff1", e.from), + format!("{}_diff1", e.to), + e.label.clone(), + ) + }) + .collect(); + let edges2: Vec<Edge> = d2 + .graph + .edges + .iter() + .map(|e| { + Edge::new( + format!("{}_diff2", e.from), + format!("{}_diff2", e.to), + e.label.clone(), + ) + }) + .collect(); + + let mut nodes1 = Vec::new(); + for node in &d1.graph.nodes { + let label = node.label.as_str(); + let mut node_cloned = node.clone(); + node_cloned.label = format!("{}_diff1", node.label); + if matched1.contains(label) { + node_cloned.style = default_style.clone(); + nodes1.push(node_cloned); + } else if partial1.contains(label) { + node_cloned.style = changed_style.clone(); + nodes1.push(node_cloned); + } else { + node_cloned.style = removed_style.clone(); + nodes1.push(node_cloned); + } + } + + let mut nodes2 = Vec::new(); + for node in &d2.graph.nodes { + let label = node.label.as_str(); + let mut node_cloned = node.clone(); + node_cloned.label = format!("{}_diff2", node.label); + if matched2.contains(label) { + node_cloned.style = default_style.clone(); + nodes2.push(node_cloned); + } else if partial2.contains(label) { + node_cloned.style = changed_style.clone(); + nodes2.push(node_cloned); + } else { + node_cloned.style = added_style.clone(); + nodes2.push(node_cloned); + } + } + let newg1 = Graph::new("diff1".to_owned(), nodes1, edges1); + let newg2 = Graph::new("diff2".to_owned(), nodes2, edges2); + + MultiGraph::new("diff".to_owned(), vec![newg1, newg2]) +} diff --git a/vendor/gsgdt/src/diff/diff_graph.rs b/vendor/gsgdt/src/diff/diff_graph.rs new file mode 100644 index 000000000..8e1e2c837 --- /dev/null +++ b/vendor/gsgdt/src/diff/diff_graph.rs @@ -0,0 +1,57 @@ +use crate::*; +use std::collections::{HashMap, HashSet, VecDeque}; + +/// A wrapper around [Graph](struct.Graph.html) to assist diffing. +pub struct DiffGraph<'a> { + pub(crate) graph: &'a Graph, + pub(crate) dist_start: HashMap<&'a str, usize>, + pub(crate) dist_end: HashMap<&'a str, usize>, +} + +impl<'a> DiffGraph<'a> { + pub fn new(graph: &'a Graph) -> Self { + let adj_list = graph.adj_list(); + let rev_adj_list = graph.rev_adj_list(); + let start_nodes = Self::get_source_labels(&adj_list); + let end_nodes = Self::get_source_labels(&rev_adj_list); + DiffGraph { + graph, + dist_start: Self::bfs_shortest_dist(rev_adj_list, start_nodes), + dist_end: Self::bfs_shortest_dist(adj_list, end_nodes), + } + } + + /// Calculate the shortest distance to the end from the given sources nodes using bfs. + fn bfs_shortest_dist(adj_list: AdjList<'a>, source: Vec<&'a str>) -> HashMap<&'a str, usize> { + let mut dist = HashMap::new(); + for k in source.iter() { + dist.insert(*k, 0); + } + let mut visited = HashSet::new(); + let mut queue: VecDeque<&str> = source.into(); + while let Some(node) = queue.pop_front() { + let neighbours = adj_list.get(node).unwrap(); + let curr_dist = *dist.get(&node).unwrap(); + + for neighbour in neighbours { + if !visited.contains(neighbour) { + dist.insert(neighbour, curr_dist + 1); + queue.push_back(neighbour); + visited.insert(neighbour); + } + } + } + + dist + } + + /// Get the source labels for a given adjacency list. The source labels will the + // TODO: This is sink labels, not source labels + fn get_source_labels(adj_list: &AdjList<'a>) -> Vec<&'a str> { + adj_list + .iter() + .filter(|(_, v)| v.is_empty()) + .map(|(k, _)| *k) + .collect() + } +} diff --git a/vendor/gsgdt/src/diff/match_graph.rs b/vendor/gsgdt/src/diff/match_graph.rs new file mode 100644 index 000000000..a75545ef7 --- /dev/null +++ b/vendor/gsgdt/src/diff/match_graph.rs @@ -0,0 +1,184 @@ +use crate::diff::*; +use crate::levenshtein::distance; +use std::collections::{BTreeMap, HashSet}; + +pub type Mapping<'a> = BTreeMap<&'a str, &'a str>; + +// TODO: Is it better to return a list of matches or a hashmap +// It might be better to do former because we may need to distinguise +// b/w full and partial match +#[derive(Debug, PartialEq)] +pub struct Matching<'a> { + pub from: &'a str, + pub to: &'a str, +} + +impl<'a> Matching<'a> { + pub fn new(from: &'a str, to: &'a str) -> Matching<'a> { + Matching { from, to } + } +} + +#[derive(Debug, PartialEq)] +pub enum Match<'a> { + Full(Matching<'a>), + Partial(Matching<'a>), +} +// +// impl<'a> Match<'a> { +// fn is_full(&self) -> bool { +// match self { +// Match::Full(_) => true, +// _ => false +// } +// } +// } + +/// Matches both graphs and returns the mapping of nodes from g1 to g2 +pub fn match_graphs<'a>(d1: &'a DiffGraph<'_>, d2: &'a DiffGraph<'_>) -> Vec<Match<'a>> { + let mut mapping: BTreeMap<&str, &str> = get_initial_mapping(d1, d2); + + // TODO: This mapping may have duplicate mappings, remove them + + let mut matches: Vec<Match> = mapping + .iter() + .map(|(from, to)| Match::Full(Matching { from, to })) + .collect(); + + // we use rev adjacency list because we are going to compare the parents + let rev_adj_list1 = d1.graph.rev_adj_list(); + let rev_adj_list2 = d2.graph.rev_adj_list(); + + let mut matched_labels_in_2: HashSet<&str> = mapping.iter().map(|(_, v)| *v).collect(); + + let mut prev_mapping = mapping.clone(); + loop { + let mut new_mapping: Mapping = BTreeMap::new(); + for (k, v) in prev_mapping.iter() { + let parents_in_1 = rev_adj_list1.get(k).unwrap(); + let parents_in_2 = rev_adj_list2.get(v).unwrap(); + + for n in parents_in_1.iter() { + // don't bother selecting if the node in 1 is already matched + // as we use a stricter selection for the initial matching + if mapping.contains_key(n) { + continue; + } + if let Some(lab) = select(d1, d2, n, &parents_in_2, false) { + // if the matched label is already matched to some node in 1, skip + if !matched_labels_in_2.contains(lab) { + matched_labels_in_2.insert(lab); + new_mapping.insert(n, lab); + } + } + } + } + // println!("{:?}", new_mapping); + // merge + let new_matches = get_new_matches(&mapping, &new_mapping); + if new_matches.len() == 0 { + break; + } + for mch in new_matches { + mapping.insert(mch.from, mch.to); + matches.push(Match::Partial(mch)); + } + prev_mapping = new_mapping; + } + + matches +} + +fn get_initial_mapping<'a>(d1: &'a DiffGraph<'_>, d2: &'a DiffGraph<'_>) -> Mapping<'a> { + let mut mapping: BTreeMap<&str, &str> = BTreeMap::new(); + let mut reverse_mapping: BTreeMap<&str, &str> = BTreeMap::new(); + let g2_labels: Vec<&str> = d2.graph.nodes.iter().map(|n| n.label.as_str()).collect(); + + // TODO: this can be functional + for node in d1.graph.nodes.iter() { + if let Some(matched_lab) = select(d1, d2, &node.label, &g2_labels, true) { + if let Some(lab_in_1) = reverse_mapping.get(matched_lab) { + // matched_lab was already matched + // select the one with the lowest cost + // this is done so that no duplicate matching will occur + let dist_already = dist_bw_nodes(d1, d2, lab_in_1, matched_lab); + let dist_new = dist_bw_nodes(d1, d2, &node.label, matched_lab); + if dist_new > dist_already { + continue; + } + mapping.remove(lab_in_1); + } + mapping.insert(&node.label, matched_lab); + reverse_mapping.insert(matched_lab, &node.label); + } + } + + mapping +} + +fn dist_bw_nodes(d1: &DiffGraph<'_>, d2: &DiffGraph<'_>, n1: &str, n2: &str) -> Option<usize> { + let node1 = d1.graph.get_node_by_label(n1).unwrap(); + let node2 = d2.graph.get_node_by_label(n2).unwrap(); + + let tup1 = ( + d1.dist_start[n1] as i64, + d1.dist_end[n1] as i64, + node1.stmts.len() as i64, + ); + let tup2 = ( + d2.dist_start[n2] as i64, + d2.dist_end[n2] as i64, + node2.stmts.len() as i64, + ); + + let s1 = node1.stmts.join(""); + let s2 = node2.stmts.join(""); + let dist = distance(&s1, &s2); + + Some( + ((tup1.0 - tup2.0).pow(2) + (tup1.1 - tup2.1).pow(2) + (tup1.2 - tup2.2).pow(2)) as usize + + dist, + ) +} + +/// Selects the most suitable match for n from L +fn select<'a>( + d1: &'a DiffGraph<'_>, + d2: &'a DiffGraph<'_>, + n: &'a str, + list_of_labs: &[&'a str], + use_text_dist_filter: bool, +) -> Option<&'a str> { + let node = d1.graph.get_node_by_label(n).unwrap(); + let node_stmt_len = node.stmts.len(); + let node_stmts = node.stmts.join(""); + list_of_labs + .iter() + .filter(|lab| { + let other_node = d2.graph.get_node_by_label(lab).unwrap(); + // filter out nodes that may differ by more than 2 lines + (other_node.stmts.len() as i64 - node.stmts.len() as i64).abs() <= 2 + }) + .filter(|lab| { + if !use_text_dist_filter { + return true; + } + let other_node_stmts = d2.graph.get_node_by_label(lab).unwrap().stmts.join(""); + // allow bigger basic blocks have more edits + // 2 here is arbitary + distance(&node_stmts, &other_node_stmts) < 2 * node_stmt_len + }) + .min_by_key(|x| dist_bw_nodes(d1, d2, n, x)) + .map(|x| *x) +} + +fn get_new_matches<'a>(mapping: &Mapping<'a>, new_mapping: &Mapping<'a>) -> Vec<Matching<'a>> { + let mut changed = Vec::new(); + for (k, v) in new_mapping.iter() { + if !mapping.contains_key(k) { + changed.push(Matching { from: k, to: v }) + } + } + + changed +} diff --git a/vendor/gsgdt/src/diff/mod.rs b/vendor/gsgdt/src/diff/mod.rs new file mode 100644 index 000000000..5e3d95529 --- /dev/null +++ b/vendor/gsgdt/src/diff/mod.rs @@ -0,0 +1,7 @@ +mod diff_graph; +mod match_graph; +mod diff; + +pub use match_graph::*; +pub use diff_graph::*; +pub use diff::*; diff --git a/vendor/gsgdt/src/graph.rs b/vendor/gsgdt/src/graph.rs new file mode 100644 index 000000000..17c859774 --- /dev/null +++ b/vendor/gsgdt/src/graph.rs @@ -0,0 +1,273 @@ +use serde::{Deserialize, Serialize}; +use std::collections::HashMap; +use std::io::{self, Write}; + +use crate::node::*; + +#[derive(Clone, Serialize, Deserialize)] +pub enum GraphKind { + Digraph, + Subgraph, +} + +pub type AdjList<'a> = HashMap<&'a str, Vec<&'a str>>; + +/// Graph represents a directed graph as a list of nodes and list of edges. +#[derive(Serialize, Deserialize)] +pub struct Graph { + /// Identifier for the graph + pub name: String, + + /// The Vector containing the Nodes + pub nodes: Vec<Node>, + + /// The Vector containing the Edges + pub edges: Vec<Edge>, +} + +#[derive(Clone)] +pub struct GraphvizSettings { + /// The attributes of the graph in graphviz. + pub graph_attrs: Option<String>, + + /// The attributes of the nodes in graphviz. + pub node_attrs: Option<String>, + + /// The attributes of the edges in graphviz. + pub edge_attrs: Option<String>, + + /// Label of the graph + pub graph_label: Option<String>, +} + +impl Default for GraphvizSettings { + fn default() -> GraphvizSettings { + GraphvizSettings { + graph_attrs: None, + node_attrs: None, + edge_attrs: None, + graph_label: None, + } + } +} + +impl Graph { + pub fn new(name: String, nodes: Vec<Node>, edges: Vec<Edge>) -> Graph { + Graph { name, nodes, edges } + } + + /// Returns the adjacency list representation of the graph. + /// Adjacency list can be used to easily find the childern of a given node. + /// If the a node does not have any childern, then the list correspoding to that node + /// will be empty. + pub fn adj_list(&self) -> AdjList<'_> { + let mut m: AdjList<'_> = HashMap::new(); + for node in &self.nodes { + m.insert(&node.label, Vec::new()); + } + for edge in &self.edges { + m.entry(&edge.from).or_insert_with(Vec::new).push(&edge.to); + } + m + } + + /// Returns the reverse adjacency list representation of the graph. + /// Reverse adjacency list represents the adjacency list of a directed graph where + /// the edges have been reversed. + /// Reverse adjacency list can be used to easily find the parents of a given node. + /// If the a node does not have any childern, then the list correspoding to that node + /// will be empty. + pub fn rev_adj_list(&self) -> AdjList<'_> { + let mut m: AdjList<'_> = HashMap::new(); + for node in &self.nodes { + m.insert(&node.label, Vec::new()); + } + for edge in &self.edges { + m.entry(&edge.to).or_insert_with(Vec::new).push(&edge.from); + } + m + } + + /// Returns the node with the given label, if found. + pub fn get_node_by_label(&self, label: &str) -> Option<&Node> { + self.nodes.iter().find(|node| node.label == *label) + } + + /// Returns the dot representation of the given graph. + /// This can rendered using the graphviz program. + pub fn to_dot<W: Write>( + &self, + w: &mut W, + settings: &GraphvizSettings, + as_subgraph: bool, + ) -> io::Result<()> { + if as_subgraph { + write!(w, "subgraph cluster_{}", self.name)?; + } else { + write!(w, "digraph {}", self.name)?; + } + + writeln!(w, " {{")?; + + if let Some(graph_attrs) = &settings.graph_attrs { + writeln!(w, r#" graph [{}];"#, graph_attrs)?; + } + if let Some(node_attrs) = &settings.node_attrs { + writeln!(w, r#" node [{}];"#, node_attrs)?; + } + if let Some(edge_attrs) = &settings.edge_attrs { + writeln!(w, r#" edge [{}];"#, edge_attrs)?; + } + if let Some(label) = &settings.graph_label { + writeln!(w, r#" label=<{}>;"#, label)?; + } + + for node in self.nodes.iter() { + write!(w, r#" {} [shape="none", label=<"#, node.label)?; + node.to_dot(w)?; + writeln!(w, ">];")?; + } + + for edge in self.edges.iter() { + edge.to_dot(w)?; + } + + writeln!(w, "}}") + } +} + +#[cfg(test)] +mod tests { + use crate::*; + fn get_test_graph() -> Graph { + let stmts: Vec<String> = vec!["hi".into(), "hell".into()]; + let label1: String = "bb0__0_3".into(); + let style: NodeStyle = Default::default(); + let node1 = Node::new(stmts, label1.clone(), "0".into(), style.clone()); + + let stmts: Vec<String> = vec!["_1 = const 1_i32".into(), "_2 = const 2_i32".into()]; + let label2: String = "bb0__1_3".into(); + let node2 = Node::new(stmts, label2.clone(), "1".into(), style.clone()); + + Graph::new( + "Mir_0_3".into(), + vec![node1, node2], + vec![Edge::new(label1, label2, "return".into())], + ) + } + + #[test] + fn test_adj_list() { + let g = get_test_graph(); + let adj_list = g.adj_list(); + let expected: AdjList = [("bb0__0_3", vec!["bb0__1_3"]), (&"bb0__1_3", vec![])] + .iter() + .cloned() + .collect(); + assert_eq!(adj_list, expected); + } + + #[test] + fn test_json_ser() { + let g = get_test_graph(); + let json = serde_json::to_string(&g).unwrap(); + let expected_json: String = "\ + {\ + \"name\":\"Mir_0_3\",\ + \"nodes\":[\ + {\ + \"stmts\":[\ + \"hi\",\ + \"hell\"\ + ],\ + \"label\":\"bb0__0_3\",\ + \"title\":\"0\",\ + \"style\":{\ + \"title_bg\":null,\ + \"last_stmt_sep\":false\ + }\ + },\ + {\ + \"stmts\":[\ + \"_1 = const 1_i32\",\ + \"_2 = const 2_i32\"\ + ],\ + \"label\":\"bb0__1_3\",\ + \"title\":\"1\",\ + \"style\":{\ + \"title_bg\":null,\ + \"last_stmt_sep\":false\ + }\ + }\ + ],\ + \"edges\":[\ + {\ + \"from\":\"bb0__0_3\",\ + \"to\":\"bb0__1_3\",\ + \"label\":\"return\"\ + }\ + ]\ + }" + .into(); + assert_eq!(json, expected_json) + } + + #[test] + fn test_json_deser() { + let expected = get_test_graph(); + let struct_json: String = "\ + {\ + \"name\":\"Mir_0_3\",\ + \"nodes\":[\ + {\ + \"stmts\":[\ + \"hi\",\ + \"hell\"\ + ],\ + \"label\":\"bb0__0_3\",\ + \"title\":\"0\",\ + \"style\":{\ + \"title_bg\":null,\ + \"last_stmt_sep\":false\ + }\ + },\ + {\ + \"stmts\":[\ + \"_1 = const 1_i32\",\ + \"_2 = const 2_i32\"\ + ],\ + \"label\":\"bb0__1_3\",\ + \"title\":\"1\",\ + \"style\":{\ + \"title_bg\":null,\ + \"last_stmt_sep\":false\ + }\ + }\ + ],\ + \"edges\":[\ + {\ + \"from\":\"bb0__0_3\",\ + \"to\":\"bb0__1_3\",\ + \"label\":\"return\"\ + }\ + ]\ + }" + .into(); + let got: Graph = serde_json::from_str(&struct_json).unwrap(); + + assert_eq!(expected.nodes.len(), got.nodes.len()); + assert_eq!(expected.edges.len(), got.edges.len()); + + for (n1, n2) in expected.nodes.iter().zip(got.nodes.iter()) { + assert_eq!(n1.stmts, n2.stmts); + assert_eq!(n1.label, n2.label); + assert_eq!(n1.title, n2.title); + } + + for (e1, e2) in expected.edges.iter().zip(got.edges.iter()) { + assert_eq!(e1.from, e2.from); + assert_eq!(e1.to, e2.to); + assert_eq!(e1.label, e2.label); + } + } +} diff --git a/vendor/gsgdt/src/levenshtein.rs b/vendor/gsgdt/src/levenshtein.rs new file mode 100644 index 000000000..8acfefc83 --- /dev/null +++ b/vendor/gsgdt/src/levenshtein.rs @@ -0,0 +1,70 @@ +use std::cmp::min; + +/// Calculate the levenshtein distance between two strings. +pub(crate) fn distance(s1: &str, s2: &str) -> usize { + let v1: Vec<char> = s1.chars().collect(); + let v2: Vec<char> = s2.chars().collect(); + + let l_v1 = v1.len(); + let l_v2 = v2.len(); + + if l_v1 == 0 { + return l_v2; + } + if l_v2 == 0 { + return l_v1; + } + if l_v1 > l_v2 { + return distance(s2, s1); + } + + let mut col: Vec<usize> = (0..=l_v1).collect(); + + for i in 1..=l_v2 { + let mut last_diag = col[0]; + col[0] += 1; + for j in 1..=l_v1 { + let last_diag_temp = col[j]; + if v1[j-1] == v2[i-1] { + col[j] = last_diag; + } else { + col[j] = min(last_diag, min(col[j-1], col[j])) + 1; + } + last_diag = last_diag_temp; + } + } + + col[l_v1] +} + + +#[cfg(test)] +mod tests { + use crate::levenshtein::*; + #[test] + fn test1() { + assert_eq!(distance("kitten", "sitting"), 3); + } + + #[test] + fn test_diff_len() { + assert_eq!(distance("kit", "kitten"), 3); + } + + #[test] + fn test_equal() { + assert_eq!(distance("test", "test"), 0); + assert_eq!(distance("", ""), 0); + assert_eq!(distance("long string with space", "long string with space"), 0); + assert_eq!(distance("unicode 😀", "unicode 😀"), 0); + } + + #[test] + fn test_one_empty() { + assert_eq!(distance("test", ""), 4); + assert_eq!(distance("", "test"), 4); + assert_eq!(distance("", ""), 0); + assert_eq!(distance("long string", ""), 11); + assert_eq!(distance("😀", ""), 1); + } +} diff --git a/vendor/gsgdt/src/lib.rs b/vendor/gsgdt/src/lib.rs new file mode 100644 index 000000000..a361e4979 --- /dev/null +++ b/vendor/gsgdt/src/lib.rs @@ -0,0 +1,12 @@ +#![allow(rustc::default_hash_types)] +mod diff; +mod graph; +mod multi_graph; +mod levenshtein; +mod node; +mod util; + +pub use diff::*; +pub use graph::*; +pub use multi_graph::*; +pub use node::*; diff --git a/vendor/gsgdt/src/multi_graph.rs b/vendor/gsgdt/src/multi_graph.rs new file mode 100644 index 000000000..f0200a318 --- /dev/null +++ b/vendor/gsgdt/src/multi_graph.rs @@ -0,0 +1,33 @@ +use crate::graph::*; +use std::io::{self, Write}; +use serde::{Deserialize, Serialize}; + +/// A collection of graphs. +#[derive(Deserialize, Serialize)] +pub struct MultiGraph { + name: String, + graphs: Vec<Graph>, +} + +impl MultiGraph { + pub fn new(name: String, graphs: Vec<Graph>) -> MultiGraph { + MultiGraph { name, graphs } + } + + pub fn to_dot<W: Write>(&self, w: &mut W, settings: &GraphvizSettings) -> io::Result<()> { + let subgraphs = self.graphs.len() > 1; + if subgraphs { + writeln!(w, "digraph {} {{", self.name)?; + } + + for graph in &self.graphs { + graph.to_dot(w, settings, subgraphs)?; + } + + if subgraphs { + writeln!(w, "}}")?; + } + + Ok(()) + } +} diff --git a/vendor/gsgdt/src/node.rs b/vendor/gsgdt/src/node.rs new file mode 100644 index 000000000..c72925b7a --- /dev/null +++ b/vendor/gsgdt/src/node.rs @@ -0,0 +1,118 @@ +use crate::util::escape_html; +use std::io::{self, Write}; +use serde::{Deserialize, Serialize}; + +/// NodeStyle defines some style of [Node](struct.Node.html) +#[derive(Clone, Serialize, Deserialize)] +pub struct NodeStyle { + /// Override the title color of the title + /// To color the title of the node differently in graphviz + pub title_bg: Option<String>, + + /// Print a seperator b/w the rest of the statements and the last one + pub last_stmt_sep: bool, +} + +impl Default for NodeStyle { + fn default() -> NodeStyle { + NodeStyle { + title_bg: None, + last_stmt_sep: false, + } + } +} + +/// A graph node +#[derive(Clone, Serialize, Deserialize)] +pub struct Node { + /// A list of statements. + pub stmts: Vec<String>, + + /// A unique identifier for the given node. + pub label: String, + + /// The title is printed on the top of BB, the index of the basic block + pub(crate) title: String, + + /// Can be used to override the default styles + pub(crate) style: NodeStyle, +} + +impl Node { + pub fn new(stmts: Vec<String>, label: String, title: String, style: NodeStyle) -> Node { + Node { + stmts, + label, + title, + style, + } + } + + pub fn to_dot<W: Write>(&self, w: &mut W) -> io::Result<()> { + write!(w, r#"<table border="0" cellborder="1" cellspacing="0">"#)?; + + let bg_attr = match &self.style.title_bg { + Some(color) => format!(r#"bgcolor="{}""#, color), + None => "".into(), + }; + write!( + w, + r#"<tr><td {bg_attr} {attrs} colspan="{colspan}">{blk}</td></tr>"#, + attrs = r#"align="center""#, + // TODO: Not sure what this is for + colspan = 1, + blk = self.title, + bg_attr = bg_attr + )?; + + let stmts_len = self.stmts.len(); + if !self.stmts.is_empty() { + if self.stmts.len() > 1 { + write!(w, r#"<tr><td align="left" balign="left">"#)?; + for statement in &self.stmts[..stmts_len - 1] { + write!(w, "{}<br/>", escape_html(statement))?; + } + write!(w, "</td></tr>")?; + } + + if !self.style.last_stmt_sep { + write!(w, r#"<tr><td align="left">"#)?; + write!(w, "{}", escape_html(&self.stmts[stmts_len - 1]))?; + } else { + write!(w, r#"<tr><td align="left" balign="left">"#)?; + write!(w, "{}", escape_html(&self.stmts[stmts_len - 1]))?; + } + write!(w, "</td></tr>")?; + } + + write!(w, "</table>") + } +} + +/// A directed graph edge +#[derive(Clone, Serialize, Deserialize, Debug)] +pub struct Edge { + /// The label of the source node of the edge. + pub from: String, + + /// The label of the target node of the edge. + pub to: String, + + /// The label (title) of the edge. This doesn't have to unique. + // TODO: Rename this to title? + pub label: String, +} + +impl Edge { + pub fn new(from: String, to: String, label: String) -> Edge { + Edge { from, to, label } + } + + pub fn to_dot<W: Write>(&self, w: &mut W) -> io::Result<()> { + writeln!( + w, + r#" {} -> {} [label="{}"];"#, + self.from, self.to, self.label + ) + } +} diff --git a/vendor/gsgdt/src/util.rs b/vendor/gsgdt/src/util.rs new file mode 100644 index 000000000..f6fcf08f6 --- /dev/null +++ b/vendor/gsgdt/src/util.rs @@ -0,0 +1,6 @@ +pub fn escape_html(s: &str) -> String { + s.replace("&", "&") + .replace("\"", """) + .replace("<", "<") + .replace(">", ">") +} diff --git a/vendor/gsgdt/tests/graph1.json b/vendor/gsgdt/tests/graph1.json new file mode 100644 index 000000000..f6381d78a --- /dev/null +++ b/vendor/gsgdt/tests/graph1.json @@ -0,0 +1,513 @@ +{ + "name": "Mir_0_3", + "kind": "Digraph", + "nodes": [ + { + "label": "bb0", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb0", + "stmts": [ + "StorageLive(_1)", + "_1 = Vec::<i32>::new()" + ] + }, + { + "label": "bb1", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb1", + "stmts": [ + "resume" + ] + }, + { + "label": "bb2", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb2", + "stmts": [ + "StorageLive(_2)", "StorageLive(_3)", "(_3.0: i32) = const 1_i32", "(_3.1: i32) = const 10_i32", + "_2 = <std::ops::Range<i32> as IntoIterator>::into_iter(move _3)" + ] + }, + { + "label": "bb3", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb3", + "stmts": [ + "StorageDead(_3)", "StorageLive(_4)", "_4 = move _2", + "goto" + ] + }, + { + "label": "bb4", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb4", + "stmts": [ + "drop(_1)" + ] + }, + { + "label": "bb5", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb5", + "stmts": [ + "StorageLive(_5)", "StorageLive(_6)", "StorageLive(_7)", "StorageLive(_8)", "_8 = &mut _4", "_7 = &mut (*_8)", + "_6 = <std::ops::Range<i32> as Iterator>::next(move _7)" + ] + }, + { + "label": "bb6", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb6", + "stmts": [ + "StorageDead(_7)", "_9 = discriminant(_6)", + "switchInt(move _9)" + ] + }, + { + "label": "bb7", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb7", + "stmts": [ + "StorageDead(_8)", "StorageDead(_6)", "StorageDead(_5)", "StorageDead(_4)", "StorageDead(_2)", "StorageLive(_21)", "StorageLive(_22)", "(_22.0: i32) = const 1_i32", "(_22.1: i32) = const 10_i32", + "_21 = <std::ops::Range<i32> as IntoIterator>::into_iter(move _22)" + ] + }, + { + "label": "bb8", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb8", + "stmts": [ + "unreachable" + ] + }, + { + "label": "bb9", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb9", + "stmts": [ + "StorageLive(_10)", "_10 = ((_6 as Some).0: i32)", "StorageLive(_11)", "_11 = _10", "_5 = move _11", "StorageDead(_11)", "StorageDead(_10)", "StorageDead(_8)", "StorageDead(_6)", "StorageLive(_12)", "_12 = _5", "StorageLive(_13)", "StorageLive(_14)", "_14 = _12", "_15 = const false", "_16 = Eq(_14, const i32::MIN)", "_17 = BitAnd(move _15, move _16)", + "assert(!move _17, \"attempt to compute the remainder of `{} % {}` which would overflow\", _14, const 2_i32)" + ] + }, + { + "label": "bb10", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb10", + "stmts": [ + "_13 = Rem(move _14, const 2_i32)", "StorageDead(_14)", + "switchInt(move _13)" + ] + }, + { + "label": "bb11", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb11", + "stmts": [ + "StorageDead(_13)", + "goto" + ] + }, + { + "label": "bb12", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb12", + "stmts": [ + "StorageDead(_13)", "StorageLive(_18)", "StorageLive(_19)", "_19 = &mut _1", "StorageLive(_20)", "_20 = _12", + "_18 = Vec::<i32>::push(move _19, move _20)" + ] + }, + { + "label": "bb13", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb13", + "stmts": [ + "StorageDead(_20)", "StorageDead(_19)", "StorageDead(_18)", + "goto" + ] + }, + { + "label": "bb14", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb14", + "stmts": [ + "StorageDead(_12)", "StorageDead(_5)", + "goto" + ] + }, + { + "label": "bb15", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb15", + "stmts": [ + "StorageDead(_22)", "StorageLive(_23)", "_23 = move _21", + "goto" + ] + }, + { + "label": "bb16", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb16", + "stmts": [ + "StorageLive(_24)", "StorageLive(_25)", "StorageLive(_26)", "StorageLive(_27)", "_27 = &mut _23", "_26 = &mut (*_27)", + "_25 = <std::ops::Range<i32> as Iterator>::next(move _26)" + ] + }, + { + "label": "bb17", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb17", + "stmts": [ + "StorageDead(_26)", "_28 = discriminant(_25)", + "switchInt(move _28)" + ] + }, + { + "label": "bb18", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb18", + "stmts": [ + "_0 = const ()", "StorageDead(_27)", "StorageDead(_25)", "StorageDead(_24)", "StorageDead(_23)", "StorageDead(_21)", + "drop(_1)" + ] + }, + { + "label": "bb19", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb19", + "stmts": [ + "unreachable" + ] + }, + { + "label": "bb20", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb20", + "stmts": [ + "StorageLive(_29)", "_29 = ((_25 as Some).0: i32)", "StorageLive(_30)", "_30 = _29", "_24 = move _30", "StorageDead(_30)", "StorageDead(_29)", "StorageDead(_27)", "StorageDead(_25)", "StorageLive(_31)", "_31 = _24", "StorageLive(_32)", "StorageLive(_33)", "_33 = _31", "_34 = const false", "_35 = Eq(_33, const i32::MIN)", "_36 = BitAnd(move _34, move _35)", + "assert(!move _36, \"attempt to compute the remainder of `{} % {}` which would overflow\", _33, const 3_i32)" + ] + }, + { + "label": "bb21", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb21", + "stmts": [ + "_32 = Rem(move _33, const 3_i32)", "StorageDead(_33)", + "switchInt(move _32)" + ] + }, + { + "label": "bb22", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb22", + "stmts": [ + "StorageDead(_32)", + "goto" + ] + }, + { + "label": "bb23", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb23", + "stmts": [ + "StorageDead(_32)", "StorageLive(_37)", "StorageLive(_38)", "_38 = &mut _1", "StorageLive(_39)", "_39 = _31", + "_37 = Vec::<i32>::push(move _38, move _39)" + ] + }, + { + "label": "bb24", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb24", + "stmts": [ + "StorageDead(_39)", "StorageDead(_38)", "StorageDead(_37)", + "goto" + ] + }, + { + "label": "bb25", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb25", + "stmts": [ + "StorageDead(_31)", "StorageDead(_24)", + "goto" + ] + }, + { + "label": "bb26", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb26", + "stmts": [ + "StorageDead(_1)", + "return" + ] + } + ], + "edges": [ + { + "from": "bb0", + "to": "bb2", + "label": "return" + }, + { + "from": "bb2", + "to": "bb3", + "label": "return" + }, + { + "from": "bb2", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb3", + "to": "bb5", + "label": "" + }, + { + "from": "bb4", + "to": "bb1", + "label": "return" + }, + { + "from": "bb5", + "to": "bb6", + "label": "return" + }, + { + "from": "bb5", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb6", + "to": "bb7", + "label": "0_isize" + }, + { + "from": "bb6", + "to": "bb9", + "label": "1_isize" + }, + { + "from": "bb6", + "to": "bb8", + "label": "otherwise" + }, + { + "from": "bb7", + "to": "bb15", + "label": "return" + }, + { + "from": "bb7", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb9", + "to": "bb10", + "label": "success" + }, + { + "from": "bb9", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb10", + "to": "bb12", + "label": "0_i32" + }, + { + "from": "bb10", + "to": "bb11", + "label": "otherwise" + }, + { + "from": "bb11", + "to": "bb14", + "label": "" + }, + { + "from": "bb12", + "to": "bb13", + "label": "return" + }, + { + "from": "bb12", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb13", + "to": "bb14", + "label": "" + }, + { + "from": "bb14", + "to": "bb5", + "label": "" + }, + { + "from": "bb15", + "to": "bb16", + "label": "" + }, + { + "from": "bb16", + "to": "bb17", + "label": "return" + }, + { + "from": "bb16", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb17", + "to": "bb18", + "label": "0_isize" + }, + { + "from": "bb17", + "to": "bb20", + "label": "1_isize" + }, + { + "from": "bb17", + "to": "bb19", + "label": "otherwise" + }, + { + "from": "bb18", + "to": "bb26", + "label": "return" + }, + { + "from": "bb20", + "to": "bb21", + "label": "success" + }, + { + "from": "bb20", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb21", + "to": "bb23", + "label": "0_i32" + }, + { + "from": "bb21", + "to": "bb22", + "label": "otherwise" + }, + { + "from": "bb22", + "to": "bb25", + "label": "" + }, + { + "from": "bb23", + "to": "bb24", + "label": "return" + }, + { + "from": "bb23", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb24", + "to": "bb25", + "label": "" + }, + { + "from": "bb25", + "to": "bb16", + "label": "" + } + ] +} diff --git a/vendor/gsgdt/tests/graph2.json b/vendor/gsgdt/tests/graph2.json new file mode 100644 index 000000000..3ca1cac2e --- /dev/null +++ b/vendor/gsgdt/tests/graph2.json @@ -0,0 +1,297 @@ +{ + "name": "Mir_0_3", + "kind": "Digraph", + "nodes": [ + { + "label": "bb0", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb0", + "stmts": [ + "StorageLive(_1)", + "_1 = Vec::<i32>::new()" + ] + }, + { + "label": "bb1", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb1", + "stmts": [ + "resume" + ] + }, + { + "label": "bb2", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb2", + "stmts": [ + "StorageLive(_2)", "StorageLive(_3)", "(_3.0: i32) = const 1_i32", "(_3.1: i32) = const 10_i32", + "_2 = <std::ops::Range<i32> as IntoIterator>::into_iter(move _3)" + ] + }, + { + "label": "bb3", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb3", + "stmts": [ + "StorageDead(_3)", "StorageLive(_4)", "_4 = move _2", + "goto" + ] + }, + { + "label": "bb4", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb4", + "stmts": [ + "drop(_1)" + ] + }, + { + "label": "bb5", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb5", + "stmts": [ + "StorageLive(_5)", "StorageLive(_6)", "StorageLive(_7)", "StorageLive(_8)", "_8 = &mut _4", "_7 = &mut (*_8)", + "_6 = <std::ops::Range<i32> as Iterator>::next(move _7)" + ] + }, + { + "label": "bb6", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb6", + "stmts": [ + "StorageDead(_7)", "_9 = discriminant(_6)", + "switchInt(move _9)" + ] + }, + { + "label": "bb7", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb7", + "stmts": [ + "_0 = const ()", "StorageDead(_8)", "StorageDead(_6)", "StorageDead(_5)", "StorageDead(_4)", "StorageDead(_2)", + "drop(_1)" + ] + }, + { + "label": "bb8", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb8", + "stmts": [ + "unreachable" + ] + }, + { + "label": "bb9", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb9", + "stmts": [ + "StorageLive(_10)", "_10 = ((_6 as Some).0: i32)", "StorageLive(_11)", "_11 = _10", "_5 = move _11", "StorageDead(_11)", "StorageDead(_10)", "StorageDead(_8)", "StorageDead(_6)", "StorageLive(_12)", "_12 = _5", "StorageLive(_13)", "StorageLive(_14)", "_14 = _12", "_15 = const false", "_16 = Eq(_14, const i32::MIN)", "_17 = BitAnd(move _15, move _16)", + "assert(!move _17, \"attempt to compute the remainder of `{} % {}` which would overflow\", _14, const 3_i32)" + ] + }, + { + "label": "bb10", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb10", + "stmts": [ + "_13 = Rem(move _14, const 3_i32)", "StorageDead(_14)", + "switchInt(move _13)" + ] + }, + { + "label": "bb11", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb11", + "stmts": [ + "StorageDead(_13)", + "goto" + ] + }, + { + "label": "bb12", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb12", + "stmts": [ + "StorageDead(_13)", "StorageLive(_18)", "StorageLive(_19)", "_19 = &mut _1", "StorageLive(_20)", "_20 = _12", + "_18 = Vec::<i32>::push(move _19, move _20)" + ] + }, + { + "label": "bb13", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb13", + "stmts": [ + "StorageDead(_20)", "StorageDead(_19)", "StorageDead(_18)", + "goto" + ] + }, + { + "label": "bb14", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb14", + "stmts": [ + "StorageDead(_12)", "StorageDead(_5)", + "goto" + ] + }, + { + "label": "bb15", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb15", + "stmts": [ + "StorageDead(_1)", + "return" + ] + } + ], + "edges": [ + { + "from": "bb0", + "to": "bb2", + "label": "return" + }, + { + "from": "bb2", + "to": "bb3", + "label": "return" + }, + { + "from": "bb2", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb3", + "to": "bb5", + "label": "" + }, + { + "from": "bb4", + "to": "bb1", + "label": "return" + }, + { + "from": "bb5", + "to": "bb6", + "label": "return" + }, + { + "from": "bb5", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb6", + "to": "bb7", + "label": "0_isize" + }, + { + "from": "bb6", + "to": "bb9", + "label": "1_isize" + }, + { + "from": "bb6", + "to": "bb8", + "label": "otherwise" + }, + { + "from": "bb7", + "to": "bb15", + "label": "return" + }, + { + "from": "bb9", + "to": "bb10", + "label": "success" + }, + { + "from": "bb9", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb10", + "to": "bb12", + "label": "0_i32" + }, + { + "from": "bb10", + "to": "bb11", + "label": "otherwise" + }, + { + "from": "bb11", + "to": "bb14", + "label": "" + }, + { + "from": "bb12", + "to": "bb13", + "label": "return" + }, + { + "from": "bb12", + "to": "bb4", + "label": "unwind" + }, + { + "from": "bb13", + "to": "bb14", + "label": "" + }, + { + "from": "bb14", + "to": "bb5", + "label": "" + } + ] +} diff --git a/vendor/gsgdt/tests/helpers.rs b/vendor/gsgdt/tests/helpers.rs new file mode 100644 index 000000000..2184e1c88 --- /dev/null +++ b/vendor/gsgdt/tests/helpers.rs @@ -0,0 +1,14 @@ +use gsgdt; +use serde_json; + +use std::fs::File; +use std::io::prelude::*; + +use gsgdt::*; + +pub fn read_graph_from_file(file: &str) -> Graph{ + let mut file = File::open(file).unwrap(); + let mut contents = String::new(); + file.read_to_string(&mut contents).unwrap(); + serde_json::from_str(&contents).unwrap() +} diff --git a/vendor/gsgdt/tests/small_graph.json b/vendor/gsgdt/tests/small_graph.json new file mode 100644 index 000000000..c12b2f351 --- /dev/null +++ b/vendor/gsgdt/tests/small_graph.json @@ -0,0 +1,36 @@ +{ + "name": "small", + "kind": "Digraph", + "nodes": [ + { + "label": "bb0", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb0", + "stmts": [ + "StorageLive(_1)", + "_1 = Vec::<i32>::new()" + ] + }, + { + "label": "bb1", + "style": { + "title_bg": null, + "last_stmt_sep": false + }, + "title": "bb1", + "stmts": [ + "resume" + ] + } + ], + "edges": [ + { + "from": "bb0", + "to": "bb1", + "label": "return" + } + ] +} diff --git a/vendor/gsgdt/tests/test_diff.rs b/vendor/gsgdt/tests/test_diff.rs new file mode 100644 index 000000000..cdca5609a --- /dev/null +++ b/vendor/gsgdt/tests/test_diff.rs @@ -0,0 +1,57 @@ +use gsgdt; +mod helpers; +use helpers::*; + +use gsgdt::*; + +#[test] +fn test_diff_2() { + let g1 = read_graph_from_file("tests/graph1.json"); + let g2 = read_graph_from_file("tests/graph2.json"); + + let d1 = DiffGraph::new(&g1); + let d2 = DiffGraph::new(&g2); + let mapping = match_graphs(&d1, &d2); + let expected = vec![ + Match::Full(Matching::new("bb0", "bb0")), + Match::Full(Matching::new("bb1", "bb1")), + Match::Full(Matching::new("bb10", "bb10")), + Match::Full(Matching::new("bb11", "bb11")), + Match::Full(Matching::new("bb12", "bb12")), + Match::Full(Matching::new("bb13", "bb13")), + Match::Full(Matching::new("bb14", "bb14")), + Match::Full(Matching::new("bb18", "bb7")), + Match::Full(Matching::new("bb2", "bb2")), + Match::Full(Matching::new("bb26", "bb15")), + Match::Full(Matching::new("bb3", "bb3")), + Match::Full(Matching::new("bb4", "bb4")), + Match::Full(Matching::new("bb5", "bb5")), + Match::Full(Matching::new("bb6", "bb6")), + Match::Full(Matching::new("bb8", "bb8")), + Match::Full(Matching::new("bb9", "bb9")), + ]; + + // dbg!("{:#?}", mapping); + assert_eq!(mapping, expected); + + let settings: GraphvizSettings = Default::default(); + let mut f1 = std::fs::File::create("test1.dot").expect("create failed"); + let mut f2 = std::fs::File::create("test2.dot").expect("create failed"); + g1.to_dot(&mut f1, &settings, false).expect("can't fail"); + g2.to_dot(&mut f2, &settings, false).expect("can't fail"); +} + +#[test] +fn test_diff_vis() { + let g1 = read_graph_from_file("tests/graph1.json"); + let g2 = read_graph_from_file("tests/graph2.json"); + + let d1 = DiffGraph::new(&g1); + let d2 = DiffGraph::new(&g2); + let settings: GraphvizSettings = Default::default(); + + let mut f1 = std::fs::File::create("test1.dot").expect("create failed"); + let mg = visualize_diff(&d2, &d1); + + mg.to_dot(&mut f1, &settings).unwrap(); +} diff --git a/vendor/gsgdt/tests/test_graph.rs b/vendor/gsgdt/tests/test_graph.rs new file mode 100644 index 000000000..afd21c622 --- /dev/null +++ b/vendor/gsgdt/tests/test_graph.rs @@ -0,0 +1,18 @@ +use gsgdt::*; +mod helpers; +use helpers::*; + +#[test] +fn test_graph_render() { + let g1 = read_graph_from_file("tests/small_graph.json"); + let settings: GraphvizSettings = Default::default(); + let mut buf = Vec::new(); + let expected = r#"digraph small { + bb0 [shape="none", label=<<table border="0" cellborder="1" cellspacing="0"><tr><td align="center" colspan="1">bb0</td></tr><tr><td align="left" balign="left">StorageLive(_1)<br/></td></tr><tr><td align="left">_1 = Vec::<i32>::new()</td></tr></table>>]; + bb1 [shape="none", label=<<table border="0" cellborder="1" cellspacing="0"><tr><td align="center" colspan="1">bb1</td></tr><tr><td align="left">resume</td></tr></table>>]; + bb0 -> bb1 [label="return"]; +} +"#; + g1.to_dot(&mut buf, &settings, false).unwrap(); + assert_eq!(String::from_utf8(buf).unwrap(), expected); +} diff --git a/vendor/gsgdt/tests/test_multigraph.rs b/vendor/gsgdt/tests/test_multigraph.rs new file mode 100644 index 000000000..a46a18423 --- /dev/null +++ b/vendor/gsgdt/tests/test_multigraph.rs @@ -0,0 +1,28 @@ +use gsgdt::*; +mod helpers; +use helpers::*; + +#[test] +fn test_multigraph_render() { + let g1 = read_graph_from_file("tests/small_graph.json"); + let g2 = read_graph_from_file("tests/small_graph.json"); + let settings: GraphvizSettings = Default::default(); + + let mg = MultiGraph::new("testgraph".into(), vec![g1, g2]); + let mut buf = Vec::new(); + let expected = r#"digraph testgraph { +subgraph cluster_small { + bb0 [shape="none", label=<<table border="0" cellborder="1" cellspacing="0"><tr><td align="center" colspan="1">bb0</td></tr><tr><td align="left" balign="left">StorageLive(_1)<br/></td></tr><tr><td align="left">_1 = Vec::<i32>::new()</td></tr></table>>]; + bb1 [shape="none", label=<<table border="0" cellborder="1" cellspacing="0"><tr><td align="center" colspan="1">bb1</td></tr><tr><td align="left">resume</td></tr></table>>]; + bb0 -> bb1 [label="return"]; +} +subgraph cluster_small { + bb0 [shape="none", label=<<table border="0" cellborder="1" cellspacing="0"><tr><td align="center" colspan="1">bb0</td></tr><tr><td align="left" balign="left">StorageLive(_1)<br/></td></tr><tr><td align="left">_1 = Vec::<i32>::new()</td></tr></table>>]; + bb1 [shape="none", label=<<table border="0" cellborder="1" cellspacing="0"><tr><td align="center" colspan="1">bb1</td></tr><tr><td align="left">resume</td></tr></table>>]; + bb0 -> bb1 [label="return"]; +} +} +"#; + mg.to_dot(&mut buf, &settings).unwrap(); + assert_eq!(String::from_utf8(buf).unwrap(), expected); +} |