summaryrefslogtreecommitdiffstats
path: root/vendor/gsgdt
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/gsgdt')
-rw-r--r--vendor/gsgdt/.cargo-checksum.json1
-rw-r--r--vendor/gsgdt/Cargo.toml26
-rw-r--r--vendor/gsgdt/LICENSE21
-rw-r--r--vendor/gsgdt/README.md33
-rw-r--r--vendor/gsgdt/src/diff/diff.rs106
-rw-r--r--vendor/gsgdt/src/diff/diff_graph.rs57
-rw-r--r--vendor/gsgdt/src/diff/match_graph.rs184
-rw-r--r--vendor/gsgdt/src/diff/mod.rs7
-rw-r--r--vendor/gsgdt/src/graph.rs273
-rw-r--r--vendor/gsgdt/src/levenshtein.rs70
-rw-r--r--vendor/gsgdt/src/lib.rs12
-rw-r--r--vendor/gsgdt/src/multi_graph.rs33
-rw-r--r--vendor/gsgdt/src/node.rs118
-rw-r--r--vendor/gsgdt/src/util.rs6
-rw-r--r--vendor/gsgdt/tests/graph1.json513
-rw-r--r--vendor/gsgdt/tests/graph2.json297
-rw-r--r--vendor/gsgdt/tests/helpers.rs14
-rw-r--r--vendor/gsgdt/tests/small_graph.json36
-rw-r--r--vendor/gsgdt/tests/test_diff.rs57
-rw-r--r--vendor/gsgdt/tests/test_graph.rs18
-rw-r--r--vendor/gsgdt/tests/test_multigraph.rs28
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("&", "&amp;")
+ .replace("\"", "&quot;")
+ .replace("<", "&lt;")
+ .replace(">", "&gt;")
+}
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::&lt;i32&gt;::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::&lt;i32&gt;::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::&lt;i32&gt;::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);
+}