Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

10 files changed, 866 insertions, 0 deletions

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;")
+}