From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/gsgdt/src/diff/diff.rs | 106 ++++++++++++++ vendor/gsgdt/src/diff/diff_graph.rs | 57 ++++++++ vendor/gsgdt/src/diff/match_graph.rs | 184 +++++++++++++++++++++++ vendor/gsgdt/src/diff/mod.rs | 7 + vendor/gsgdt/src/graph.rs | 273 +++++++++++++++++++++++++++++++++++ vendor/gsgdt/src/levenshtein.rs | 70 +++++++++ vendor/gsgdt/src/lib.rs | 12 ++ vendor/gsgdt/src/multi_graph.rs | 33 +++++ vendor/gsgdt/src/node.rs | 118 +++++++++++++++ vendor/gsgdt/src/util.rs | 6 + 10 files changed, 866 insertions(+) create mode 100644 vendor/gsgdt/src/diff/diff.rs create mode 100644 vendor/gsgdt/src/diff/diff_graph.rs create mode 100644 vendor/gsgdt/src/diff/match_graph.rs create mode 100644 vendor/gsgdt/src/diff/mod.rs create mode 100644 vendor/gsgdt/src/graph.rs create mode 100644 vendor/gsgdt/src/levenshtein.rs create mode 100644 vendor/gsgdt/src/lib.rs create mode 100644 vendor/gsgdt/src/multi_graph.rs create mode 100644 vendor/gsgdt/src/node.rs create mode 100644 vendor/gsgdt/src/util.rs (limited to 'vendor/gsgdt/src') 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 = d1 + .graph + .edges + .iter() + .map(|e| { + Edge::new( + format!("{}_diff1", e.from), + format!("{}_diff1", e.to), + e.label.clone(), + ) + }) + .collect(); + let edges2: Vec = 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> { + let mut mapping: BTreeMap<&str, &str> = get_initial_mapping(d1, d2); + + // TODO: This mapping may have duplicate mappings, remove them + + let mut matches: Vec = 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 { + 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> { + 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, + + /// The Vector containing the Edges + pub edges: Vec, +} + +#[derive(Clone)] +pub struct GraphvizSettings { + /// The attributes of the graph in graphviz. + pub graph_attrs: Option, + + /// The attributes of the nodes in graphviz. + pub node_attrs: Option, + + /// The attributes of the edges in graphviz. + pub edge_attrs: Option, + + /// Label of the graph + pub graph_label: Option, +} + +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, edges: Vec) -> 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( + &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 = 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 = 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 = s1.chars().collect(); + let v2: Vec = 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 = (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, +} + +impl MultiGraph { + pub fn new(name: String, graphs: Vec) -> MultiGraph { + MultiGraph { name, graphs } + } + + pub fn to_dot(&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, + + /// 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, + + /// 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, label: String, title: String, style: NodeStyle) -> Node { + Node { + stmts, + label, + title, + style, + } + } + + pub fn to_dot(&self, w: &mut W) -> io::Result<()> { + write!(w, r#""#)?; + + let bg_attr = match &self.style.title_bg { + Some(color) => format!(r#"bgcolor="{}""#, color), + None => "".into(), + }; + write!( + w, + r#""#, + 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#"")?; + } + + if !self.style.last_stmt_sep { + write!(w, r#"")?; + } + + write!(w, "
{blk}
"#)?; + for statement in &self.stmts[..stmts_len - 1] { + write!(w, "{}
", escape_html(statement))?; + } + write!(w, "
"#)?; + write!(w, "{}", escape_html(&self.stmts[stmts_len - 1]))?; + } else { + write!(w, r#"
"#)?; + write!(w, "{}", escape_html(&self.stmts[stmts_len - 1]))?; + } + write!(w, "
") + } +} + +/// 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(&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(">", ">") +} -- cgit v1.2.3