From 7ab0d1ab675a07a5bb1eae4d41a2e1cbccae113d Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Tue, 7 Apr 2015 06:12:13 -0400 Subject: Port to using the newer graph, which offers iterators instead of the older `each` method, but is otherwise identical. --- src/librustc/lib.rs | 1 - src/librustc/middle/cfg/construct.rs | 2 +- src/librustc/middle/cfg/mod.rs | 5 +- src/librustc/middle/dataflow.rs | 5 +- src/librustc/middle/graph.rs | 484 ---------------------- src/librustc/middle/infer/region_inference/mod.rs | 30 +- src/librustc_data_structures/bitvec.rs | 32 ++ src/librustc_data_structures/graph/mod.rs | 403 ++++++++++++++++++ src/librustc_data_structures/graph/test.rs | 129 ++++++ src/librustc_data_structures/lib.rs | 2 + src/librustc_lint/builtin.rs | 5 +- 11 files changed, 587 insertions(+), 511 deletions(-) delete mode 100644 src/librustc/middle/graph.rs create mode 100644 src/librustc_data_structures/bitvec.rs create mode 100644 src/librustc_data_structures/graph/mod.rs create mode 100644 src/librustc_data_structures/graph/test.rs diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index 6837483a422..ab5c4e76966 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -104,7 +104,6 @@ pub mod middle { pub mod entry; pub mod expr_use_visitor; pub mod fast_reject; - pub mod graph; pub mod intrinsicck; pub mod infer; pub mod lang_items; diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs index cbc2ef1535e..359a1a486c9 100644 --- a/src/librustc/middle/cfg/construct.rs +++ b/src/librustc/middle/cfg/construct.rs @@ -8,9 +8,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +use rustc_data_structures::graph; use middle::cfg::*; use middle::def; -use middle::graph; use middle::pat_util; use middle::region::CodeExtent; use middle::ty; diff --git a/src/librustc/middle/cfg/mod.rs b/src/librustc/middle/cfg/mod.rs index ad4fdcd7b83..3ca221c9630 100644 --- a/src/librustc/middle/cfg/mod.rs +++ b/src/librustc/middle/cfg/mod.rs @@ -11,7 +11,7 @@ //! Module that constructs a control-flow graph representing an item. //! Uses `Graph` as the underlying representation. -use middle::graph; +use rustc_data_structures::graph; use middle::ty; use syntax::ast; @@ -24,7 +24,7 @@ pub struct CFG { pub exit: CFGIndex, } -#[derive(Copy, Clone, PartialEq)] +#[derive(Copy, Clone, Debug, PartialEq)] pub enum CFGNodeData { AST(ast::NodeId), Entry, @@ -43,6 +43,7 @@ impl CFGNodeData { } } +#[derive(Debug)] pub struct CFGEdgeData { pub exiting_scopes: Vec } diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs index 41b4495c5f0..1d5d4f72fc2 100644 --- a/src/librustc/middle/dataflow.rs +++ b/src/librustc/middle/dataflow.rs @@ -576,10 +576,9 @@ impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> { pred_bits: &[usize], cfg: &cfg::CFG, cfgidx: CFGIndex) { - cfg.graph.each_outgoing_edge(cfgidx, |_e_idx, edge| { + for (_, edge) in cfg.graph.outgoing_edges(cfgidx) { self.propagate_bits_into_entry_set_for(pred_bits, edge); - true - }); + } } fn propagate_bits_into_entry_set_for(&mut self, diff --git a/src/librustc/middle/graph.rs b/src/librustc/middle/graph.rs deleted file mode 100644 index a9ac61b49ec..00000000000 --- a/src/librustc/middle/graph.rs +++ /dev/null @@ -1,484 +0,0 @@ -// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! A graph module for use in dataflow, region resolution, and elsewhere. -//! -//! # Interface details -//! -//! You customize the graph by specifying a "node data" type `N` and an -//! "edge data" type `E`. You can then later gain access (mutable or -//! immutable) to these "user-data" bits. Currently, you can only add -//! nodes or edges to the graph. You cannot remove or modify them once -//! added. This could be changed if we have a need. -//! -//! # Implementation details -//! -//! The main tricky thing about this code is the way that edges are -//! stored. The edges are stored in a central array, but they are also -//! threaded onto two linked lists for each node, one for incoming edges -//! and one for outgoing edges. Note that every edge is a member of some -//! incoming list and some outgoing list. Basically you can load the -//! first index of the linked list from the node data structures (the -//! field `first_edge`) and then, for each edge, load the next index from -//! the field `next_edge`). Each of those fields is an array that should -//! be indexed by the direction (see the type `Direction`). - -#![allow(dead_code)] // still WIP - -use std::fmt::{Formatter, Error, Debug}; -use std::usize; -use std::collections::BitSet; - -pub struct Graph { - nodes: Vec> , - edges: Vec> , -} - -pub struct Node { - first_edge: [EdgeIndex; 2], // see module comment - pub data: N, -} - -pub struct Edge { - next_edge: [EdgeIndex; 2], // see module comment - source: NodeIndex, - target: NodeIndex, - pub data: E, -} - -impl Debug for Edge { - fn fmt(&self, f: &mut Formatter) -> Result<(), Error> { - write!(f, "Edge {{ next_edge: [{:?}, {:?}], source: {:?}, target: {:?}, data: {:?} }}", - self.next_edge[0], self.next_edge[1], self.source, - self.target, self.data) - } -} - -#[derive(Clone, Copy, PartialEq, Debug)] -pub struct NodeIndex(pub usize); -#[allow(non_upper_case_globals)] -pub const InvalidNodeIndex: NodeIndex = NodeIndex(usize::MAX); - -#[derive(Copy, Clone, PartialEq, Debug)] -pub struct EdgeIndex(pub usize); -#[allow(non_upper_case_globals)] -pub const InvalidEdgeIndex: EdgeIndex = EdgeIndex(usize::MAX); - -// Use a private field here to guarantee no more instances are created: -#[derive(Copy, Clone, Debug)] -pub struct Direction { repr: usize } -#[allow(non_upper_case_globals)] -pub const Outgoing: Direction = Direction { repr: 0 }; -#[allow(non_upper_case_globals)] -pub const Incoming: Direction = Direction { repr: 1 }; - -impl NodeIndex { - fn get(&self) -> usize { let NodeIndex(v) = *self; v } - /// Returns unique id (unique with respect to the graph holding associated node). - pub fn node_id(&self) -> usize { self.get() } -} - -impl EdgeIndex { - fn get(&self) -> usize { let EdgeIndex(v) = *self; v } - /// Returns unique id (unique with respect to the graph holding associated edge). - pub fn edge_id(&self) -> usize { self.get() } -} - -impl Graph { - pub fn new() -> Graph { - Graph { - nodes: Vec::new(), - edges: Vec::new(), - } - } - - pub fn with_capacity(num_nodes: usize, - num_edges: usize) -> Graph { - Graph { - nodes: Vec::with_capacity(num_nodes), - edges: Vec::with_capacity(num_edges), - } - } - - /////////////////////////////////////////////////////////////////////////// - // Simple accessors - - #[inline] - pub fn all_nodes<'a>(&'a self) -> &'a [Node] { - &self.nodes - } - - #[inline] - pub fn all_edges<'a>(&'a self) -> &'a [Edge] { - &self.edges - } - - /////////////////////////////////////////////////////////////////////////// - // Node construction - - pub fn next_node_index(&self) -> NodeIndex { - NodeIndex(self.nodes.len()) - } - - pub fn add_node(&mut self, data: N) -> NodeIndex { - let idx = self.next_node_index(); - self.nodes.push(Node { - first_edge: [InvalidEdgeIndex, InvalidEdgeIndex], - data: data - }); - idx - } - - pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N { - &mut self.nodes[idx.get()].data - } - - pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N { - &self.nodes[idx.get()].data - } - - pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node { - &self.nodes[idx.get()] - } - - /////////////////////////////////////////////////////////////////////////// - // Edge construction and queries - - pub fn next_edge_index(&self) -> EdgeIndex { - EdgeIndex(self.edges.len()) - } - - pub fn add_edge(&mut self, - source: NodeIndex, - target: NodeIndex, - data: E) -> EdgeIndex { - let idx = self.next_edge_index(); - - // read current first of the list of edges from each node - let source_first = self.nodes[source.get()] - .first_edge[Outgoing.repr]; - let target_first = self.nodes[target.get()] - .first_edge[Incoming.repr]; - - // create the new edge, with the previous firsts from each node - // as the next pointers - self.edges.push(Edge { - next_edge: [source_first, target_first], - source: source, - target: target, - data: data - }); - - // adjust the firsts for each node target be the next object. - self.nodes[source.get()].first_edge[Outgoing.repr] = idx; - self.nodes[target.get()].first_edge[Incoming.repr] = idx; - - return idx; - } - - pub fn mut_edge_data<'a>(&'a mut self, idx: EdgeIndex) -> &'a mut E { - &mut self.edges[idx.get()].data - } - - pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E { - &self.edges[idx.get()].data - } - - pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge { - &self.edges[idx.get()] - } - - pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex { - //! Accesses the index of the first edge adjacent to `node`. - //! This is useful if you wish to modify the graph while walking - //! the linked list of edges. - - self.nodes[node.get()].first_edge[dir.repr] - } - - pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex { - //! Accesses the next edge in a given direction. - //! This is useful if you wish to modify the graph while walking - //! the linked list of edges. - - self.edges[edge.get()].next_edge[dir.repr] - } - - /////////////////////////////////////////////////////////////////////////// - // Iterating over nodes, edges - - pub fn each_node<'a, F>(&'a self, mut f: F) -> bool where - F: FnMut(NodeIndex, &'a Node) -> bool, - { - //! Iterates over all edges defined in the graph. - self.nodes.iter().enumerate().all(|(i, node)| f(NodeIndex(i), node)) - } - - pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool where - F: FnMut(EdgeIndex, &'a Edge) -> bool, - { - //! Iterates over all edges defined in the graph - self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge)) - } - - pub fn each_outgoing_edge<'a, F>(&'a self, source: NodeIndex, f: F) -> bool where - F: FnMut(EdgeIndex, &'a Edge) -> bool, - { - //! Iterates over all outgoing edges from the node `from` - - self.each_adjacent_edge(source, Outgoing, f) - } - - pub fn each_incoming_edge<'a, F>(&'a self, target: NodeIndex, f: F) -> bool where - F: FnMut(EdgeIndex, &'a Edge) -> bool, - { - //! Iterates over all incoming edges to the node `target` - - self.each_adjacent_edge(target, Incoming, f) - } - - pub fn each_adjacent_edge<'a, F>(&'a self, - node: NodeIndex, - dir: Direction, - mut f: F) - -> bool where - F: FnMut(EdgeIndex, &'a Edge) -> bool, - { - //! Iterates over all edges adjacent to the node `node` - //! in the direction `dir` (either `Outgoing` or `Incoming) - - let mut edge_idx = self.first_adjacent(node, dir); - while edge_idx != InvalidEdgeIndex { - let edge = &self.edges[edge_idx.get()]; - if !f(edge_idx, edge) { - return false; - } - edge_idx = edge.next_edge[dir.repr]; - } - return true; - } - - /////////////////////////////////////////////////////////////////////////// - // Fixed-point iteration - // - // A common use for graphs in our compiler is to perform - // fixed-point iteration. In this case, each edge represents a - // constraint, and the nodes themselves are associated with - // variables or other bitsets. This method facilitates such a - // computation. - - pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) where - F: FnMut(usize, EdgeIndex, &'a Edge) -> bool, - { - let mut iteration = 0; - let mut changed = true; - while changed { - changed = false; - iteration += 1; - for (i, edge) in self.edges.iter().enumerate() { - changed |= op(iteration, EdgeIndex(i), edge); - } - } - } - - pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E> { - DepthFirstTraversal { - graph: self, - stack: vec![start], - visited: BitSet::new() - } - } -} - -pub struct DepthFirstTraversal<'g, N:'g, E:'g> { - graph: &'g Graph, - stack: Vec, - visited: BitSet -} - -impl<'g, N, E> Iterator for DepthFirstTraversal<'g, N, E> { - type Item = &'g N; - - fn next(&mut self) -> Option<&'g N> { - while let Some(idx) = self.stack.pop() { - if !self.visited.insert(idx.node_id()) { - continue; - } - self.graph.each_outgoing_edge(idx, |_, e| -> bool { - if !self.visited.contains(&e.target().node_id()) { - self.stack.push(e.target()); - } - true - }); - - return Some(self.graph.node_data(idx)); - } - - return None; - } -} - -pub fn each_edge_index(max_edge_index: EdgeIndex, mut f: F) where - F: FnMut(EdgeIndex) -> bool, -{ - let mut i = 0; - let n = max_edge_index.get(); - while i < n { - if !f(EdgeIndex(i)) { - return; - } - i += 1; - } -} - -impl Edge { - pub fn source(&self) -> NodeIndex { - self.source - } - - pub fn target(&self) -> NodeIndex { - self.target - } -} - -#[cfg(test)] -mod test { - use middle::graph::*; - use std::fmt::Debug; - - type TestNode = Node<&'static str>; - type TestEdge = Edge<&'static str>; - type TestGraph = Graph<&'static str, &'static str>; - - fn create_graph() -> TestGraph { - let mut graph = Graph::new(); - - // Create a simple graph - // - // A -+> B --> C - // | | ^ - // | v | - // F D --> E - - let a = graph.add_node("A"); - let b = graph.add_node("B"); - let c = graph.add_node("C"); - let d = graph.add_node("D"); - let e = graph.add_node("E"); - let f = graph.add_node("F"); - - graph.add_edge(a, b, "AB"); - graph.add_edge(b, c, "BC"); - graph.add_edge(b, d, "BD"); - graph.add_edge(d, e, "DE"); - graph.add_edge(e, c, "EC"); - graph.add_edge(f, b, "FB"); - - return graph; - } - - #[test] - fn each_node() { - let graph = create_graph(); - let expected = ["A", "B", "C", "D", "E", "F"]; - graph.each_node(|idx, node| { - assert_eq!(&expected[idx.get()], graph.node_data(idx)); - assert_eq!(expected[idx.get()], node.data); - true - }); - } - - #[test] - fn each_edge() { - let graph = create_graph(); - let expected = ["AB", "BC", "BD", "DE", "EC", "FB"]; - graph.each_edge(|idx, edge| { - assert_eq!(&expected[idx.get()], graph.edge_data(idx)); - assert_eq!(expected[idx.get()], edge.data); - true - }); - } - - fn test_adjacent_edges(graph: &Graph, - start_index: NodeIndex, - start_data: N, - expected_incoming: &[(E,N)], - expected_outgoing: &[(E,N)]) { - assert!(graph.node_data(start_index) == &start_data); - - let mut counter = 0; - graph.each_incoming_edge(start_index, |edge_index, edge| { - assert!(graph.edge_data(edge_index) == &edge.data); - assert!(counter < expected_incoming.len()); - debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}", - counter, expected_incoming[counter], edge_index, edge); - match expected_incoming[counter] { - (ref e, ref n) => { - assert!(e == &edge.data); - assert!(n == graph.node_data(edge.source)); - assert!(start_index == edge.target); - } - } - counter += 1; - true - }); - assert_eq!(counter, expected_incoming.len()); - - let mut counter = 0; - graph.each_outgoing_edge(start_index, |edge_index, edge| { - assert!(graph.edge_data(edge_index) == &edge.data); - assert!(counter < expected_outgoing.len()); - debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}", - counter, expected_outgoing[counter], edge_index, edge); - match expected_outgoing[counter] { - (ref e, ref n) => { - assert!(e == &edge.data); - assert!(start_index == edge.source); - assert!(n == graph.node_data(edge.target)); - } - } - counter += 1; - true - }); - assert_eq!(counter, expected_outgoing.len()); - } - - #[test] - fn each_adjacent_from_a() { - let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(0), "A", - &[], - &[("AB", "B")]); - } - - #[test] - fn each_adjacent_from_b() { - let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(1), "B", - &[("FB", "F"), ("AB", "A"),], - &[("BD", "D"), ("BC", "C"),]); - } - - #[test] - fn each_adjacent_from_c() { - let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(2), "C", - &[("EC", "E"), ("BC", "B")], - &[]); - } - - #[test] - fn each_adjacent_from_d() { - let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(3), "D", - &[("BD", "B")], - &[("DE", "E")]); - } -} diff --git a/src/librustc/middle/infer/region_inference/mod.rs b/src/librustc/middle/infer/region_inference/mod.rs index c6be97e6dbe..e76468131e0 100644 --- a/src/librustc/middle/infer/region_inference/mod.rs +++ b/src/librustc/middle/infer/region_inference/mod.rs @@ -20,14 +20,13 @@ use self::Classification::*; use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable}; +use rustc_data_structures::graph::{self, Direction, NodeIndex}; use middle::region; use middle::ty::{self, Ty}; use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid}; use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound}; use middle::ty::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh}; use middle::ty_relate::RelateResult; -use middle::graph; -use middle::graph::{Direction, NodeIndex}; use util::common::indenter; use util::nodemap::{FnvHashMap, FnvHashSet}; use util::ppaux::{Repr, UserString}; @@ -1325,10 +1324,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> { let num_vars = self.num_vars(); let constraints = self.constraints.borrow(); - let num_edges = constraints.len(); - let mut graph = graph::Graph::with_capacity(num_vars as usize + 1, - num_edges); + let mut graph = graph::Graph::new(); for _ in 0..num_vars { graph.add_node(()); @@ -1370,10 +1367,10 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> { // not contained by an upper-bound. let (mut lower_bounds, lower_dup) = self.collect_concrete_regions(graph, var_data, node_idx, - graph::Incoming, dup_vec); + graph::INCOMING, dup_vec); let (mut upper_bounds, upper_dup) = self.collect_concrete_regions(graph, var_data, node_idx, - graph::Outgoing, dup_vec); + graph::OUTGOING, dup_vec); if lower_dup || upper_dup { return; @@ -1433,7 +1430,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> { // that have no intersection. let (upper_bounds, dup_found) = self.collect_concrete_regions(graph, var_data, node_idx, - graph::Outgoing, dup_vec); + graph::OUTGOING, dup_vec); if dup_found { return; @@ -1508,8 +1505,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> { // figure out the direction from which this node takes its // values, and search for concrete regions etc in that direction let dir = match classification { - Expanding => graph::Incoming, - Contracting => graph::Outgoing, + Expanding => graph::INCOMING, + Contracting => graph::OUTGOING, }; process_edges(self, &mut state, graph, node_idx, dir); @@ -1519,14 +1516,14 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> { return (result, dup_found); fn process_edges<'a, 'tcx>(this: &RegionVarBindings<'a, 'tcx>, - state: &mut WalkState<'tcx>, - graph: &RegionGraph, - source_vid: RegionVid, - dir: Direction) { + state: &mut WalkState<'tcx>, + graph: &RegionGraph, + source_vid: RegionVid, + dir: Direction) { debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir); let source_node_index = NodeIndex(source_vid.index as usize); - graph.each_adjacent_edge(source_node_index, dir, |_, edge| { + for (_, edge) in graph.adjacent_edges(source_node_index, dir) { match edge.data { ConstrainVarSubVar(from_vid, to_vid) => { let opp_vid = @@ -1544,8 +1541,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> { }); } } - true - }); + } } } diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs new file mode 100644 index 00000000000..f5924ef5a3f --- /dev/null +++ b/src/librustc_data_structures/bitvec.rs @@ -0,0 +1,32 @@ +use std::iter; + +/// A very simple BitVector type. +pub struct BitVector { + data: Vec +} + +impl BitVector { + pub fn new(num_bits: usize) -> BitVector { + let num_words = (num_bits + 63) / 64; + BitVector { data: iter::repeat(0).take(num_words).collect() } + } + + fn word_mask(&self, bit: usize) -> (usize, u64) { + let word = bit / 64; + let mask = 1 << (bit % 64); + (word, mask) + } + + pub fn contains(&self, bit: usize) -> bool { + let (word, mask) = self.word_mask(bit); + (self.data[word] & mask) != 0 + } + + pub fn insert(&mut self, bit: usize) -> bool { + let (word, mask) = self.word_mask(bit); + let data = &mut self.data[word]; + let value = *data; + *data = value | mask; + (value | mask) != value + } +} diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs new file mode 100644 index 00000000000..5741544fe54 --- /dev/null +++ b/src/librustc_data_structures/graph/mod.rs @@ -0,0 +1,403 @@ +// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! A graph module for use in dataflow, region resolution, and elsewhere. +//! +//! # Interface details +//! +//! You customize the graph by specifying a "node data" type `N` and an +//! "edge data" type `E`. You can then later gain access (mutable or +//! immutable) to these "user-data" bits. Currently, you can only add +//! nodes or edges to the graph. You cannot remove or modify them once +//! added. This could be changed if we have a need. +//! +//! # Implementation details +//! +//! The main tricky thing about this code is the way that edges are +//! stored. The edges are stored in a central array, but they are also +//! threaded onto two linked lists for each node, one for incoming edges +//! and one for outgoing edges. Note that every edge is a member of some +//! incoming list and some outgoing list. Basically you can load the +//! first index of the linked list from the node data structures (the +//! field `first_edge`) and then, for each edge, load the next index from +//! the field `next_edge`). Each of those fields is an array that should +//! be indexed by the direction (see the type `Direction`). + +use bitvec::BitVector; +use std::fmt::{Formatter, Error, Debug}; +use std::usize; +use snapshot_vec::{SnapshotVec, SnapshotVecDelegate}; + +#[cfg(test)] +mod test; + +pub struct Graph { + nodes: SnapshotVec> , + edges: SnapshotVec> , +} + +pub struct Node { + first_edge: [EdgeIndex; 2], // see module comment + pub data: N, +} + +pub struct Edge { + next_edge: [EdgeIndex; 2], // see module comment + source: NodeIndex, + target: NodeIndex, + pub data: E, +} + +impl SnapshotVecDelegate for Node { + type Value = Node; + type Undo = (); + + fn reverse(_: &mut Vec>, _: ()) {} +} + +impl SnapshotVecDelegate for Edge { + type Value = Edge; + type Undo = (); + + fn reverse(_: &mut Vec>, _: ()) {} +} + +impl Debug for Edge { + fn fmt(&self, f: &mut Formatter) -> Result<(), Error> { + write!(f, "Edge {{ next_edge: [{:?}, {:?}], source: {:?}, target: {:?}, data: {:?} }}", + self.next_edge[0], self.next_edge[1], self.source, + self.target, self.data) + } +} + +#[derive(Copy, Clone, PartialEq, Debug)] +pub struct NodeIndex(pub usize); + +#[derive(Copy, Clone, PartialEq, Debug)] +pub struct EdgeIndex(pub usize); + +pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX); + +// Use a private field here to guarantee no more instances are created: +#[derive(Copy, Clone, Debug)] +pub struct Direction { repr: usize } + +pub const OUTGOING: Direction = Direction { repr: 0 }; + +pub const INCOMING: Direction = Direction { repr: 1 }; + +impl NodeIndex { + /// Returns unique id (unique with respect to the graph holding associated node). + pub fn node_id(&self) -> usize { self.0 } +} + +impl EdgeIndex { + /// Returns unique id (unique with respect to the graph holding associated edge). + pub fn edge_id(&self) -> usize { self.0 } +} + +impl Graph { + pub fn new() -> Graph { + Graph { + nodes: SnapshotVec::new(), + edges: SnapshotVec::new(), + } + } + + /////////////////////////////////////////////////////////////////////////// + // Simple accessors + + #[inline] + pub fn all_nodes<'a>(&'a self) -> &'a [Node] { + &self.nodes + } + + #[inline] + pub fn all_edges<'a>(&'a self) -> &'a [Edge] { + &self.edges + } + + /////////////////////////////////////////////////////////////////////////// + // Node construction + + pub fn next_node_index(&self) -> NodeIndex { + NodeIndex(self.nodes.len()) + } + + pub fn add_node(&mut self, data: N) -> NodeIndex { + let idx = self.next_node_index(); + self.nodes.push(Node { + first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX], + data: data + }); + idx + } + + pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N { + &mut self.nodes[idx.0].data + } + + pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N { + &self.nodes[idx.0].data + } + + pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node { + &self.nodes[idx.0] + } + + /////////////////////////////////////////////////////////////////////////// + // Edge construction and queries + + pub fn next_edge_index(&self) -> EdgeIndex { + EdgeIndex(self.edges.len()) + } + + pub fn add_edge(&mut self, + source: NodeIndex, + target: NodeIndex, + data: E) -> EdgeIndex { + debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data); + + let idx = self.next_edge_index(); + + // read current first of the list of edges from each node + let source_first = self.nodes[source.0] + .first_edge[OUTGOING.repr]; + let target_first = self.nodes[target.0] + .first_edge[INCOMING.repr]; + + // create the new edge, with the previous firsts from each node + // as the next pointers + self.edges.push(Edge { + next_edge: [source_first, target_first], + source: source, + target: target, + data: data + }); + + // adjust the firsts for each node target be the next object. + self.nodes[source.0].first_edge[OUTGOING.repr] = idx; + self.nodes[target.0].first_edge[INCOMING.repr] = idx; + + return idx; + } + + pub fn mut_edge_data<'a>(&'a mut self, idx: EdgeIndex) -> &'a mut E { + &mut self.edges[idx.0].data + } + + pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E { + &self.edges[idx.0].data + } + + pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge { + &self.edges[idx.0] + } + + pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex { + //! Accesses the index of the first edge adjacent to `node`. + //! This is useful if you wish to modify the graph while walking + //! the linked list of edges. + + self.nodes[node.0].first_edge[dir.repr] + } + + pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex { + //! Accesses the next edge in a given direction. + //! This is useful if you wish to modify the graph while walking + //! the linked list of edges. + + self.edges[edge.0].next_edge[dir.repr] + } + + /////////////////////////////////////////////////////////////////////////// + // Iterating over nodes, edges + + pub fn each_node<'a, F>(&'a self, mut f: F) -> bool where + F: FnMut(NodeIndex, &'a Node) -> bool, + { + //! Iterates over all edges defined in the graph. + self.nodes.iter().enumerate().all(|(i, node)| f(NodeIndex(i), node)) + } + + pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool where + F: FnMut(EdgeIndex, &'a Edge) -> bool, + { + //! Iterates over all edges defined in the graph + self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge)) + } + + pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges { + self.adjacent_edges(source, OUTGOING) + } + + pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges { + self.adjacent_edges(source, INCOMING) + } + + pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges { + let first_edge = self.node(source).first_edge[direction.repr]; + AdjacentEdges { graph: self, direction: direction, next: first_edge } + } + + pub fn successor_nodes<'a>(&'a self, source: NodeIndex) -> AdjacentTargets { + self.outgoing_edges(source).targets() + } + + pub fn predecessor_nodes<'a>(&'a self, target: NodeIndex) -> AdjacentSources { + self.incoming_edges(target).sources() + } + + /////////////////////////////////////////////////////////////////////////// + // Fixed-point iteration + // + // A common use for graphs in our compiler is to perform + // fixed-point iteration. In this case, each edge represents a + // constraint, and the nodes themselves are associated with + // variables or other bitsets. This method facilitates such a + // computation. + + pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) where + F: FnMut(usize, EdgeIndex, &'a Edge) -> bool, + { + let mut iteration = 0; + let mut changed = true; + while changed { + changed = false; + iteration += 1; + for (i, edge) in self.edges.iter().enumerate() { + changed |= op(iteration, EdgeIndex(i), edge); + } + } + } + + pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E> { + DepthFirstTraversal { + graph: self, + stack: vec![start], + visited: BitVector::new(self.nodes.len()), + } + } +} + +/////////////////////////////////////////////////////////////////////////// +// Iterators + +pub struct AdjacentEdges<'g,N,E> + where N:'g, E:'g +{ + graph: &'g Graph, + direction: Direction, + next: EdgeIndex, +} + +impl<'g,N,E> AdjacentEdges<'g,N,E> { + fn targets(self) -> AdjacentTargets<'g,N,E> { + AdjacentTargets { edges: self } + } + + fn sources(self) -> AdjacentSources<'g,N,E> { + AdjacentSources { edges: self } + } +} + +impl<'g, N:Debug, E:Debug> Iterator for AdjacentEdges<'g, N, E> { + type Item = (EdgeIndex, &'g Edge); + + fn next(&mut self) -> Option<(EdgeIndex, &'g Edge)> { + let edge_index = self.next; + if edge_index == INVALID_EDGE_INDEX { + return None; + } + + let edge = self.graph.edge(edge_index); + self.next = edge.next_edge[self.direction.repr]; + Some((edge_index, edge)) + } +} + +pub struct AdjacentTargets<'g,N:'g,E:'g> + where N:'g, E:'g +{ + edges: AdjacentEdges<'g,N,E>, +} + +impl<'g, N:Debug, E:Debug> Iterator for AdjacentTargets<'g, N, E> { + type Item = NodeIndex; + + fn next(&mut self) -> Option { + self.edges.next().map(|(_, edge)| edge.target) + } +} + +pub struct AdjacentSources<'g,N:'g,E:'g> + where N:'g, E:'g +{ + edges: AdjacentEdges<'g,N,E>, +} + +impl<'g, N:Debug, E:Debug> Iterator for AdjacentSources<'g, N, E> { + type Item = NodeIndex; + + fn next(&mut self) -> Option { + self.edges.next().map(|(_, edge)| edge.source) + } +} + +pub struct DepthFirstTraversal<'g, N:'g, E:'g> { + graph: &'g Graph, + stack: Vec, + visited: BitVector +} + +impl<'g, N:Debug, E:Debug> Iterator for DepthFirstTraversal<'g, N, E> { + type Item = &'g N; + + fn next(&mut self) -> Option<&'g N> { + while let Some(idx) = self.stack.pop() { + if !self.visited.insert(idx.node_id()) { + continue; + } + + for (_, edge) in self.graph.outgoing_edges(idx) { + if !self.visited.contains(edge.target().node_id()) { + self.stack.push(edge.target()); + } + } + + return Some(self.graph.node_data(idx)); + } + + return None; + } +} + +pub fn each_edge_index(max_edge_index: EdgeIndex, mut f: F) where + F: FnMut(EdgeIndex) -> bool, +{ + let mut i = 0; + let n = max_edge_index.0; + while i < n { + if !f(EdgeIndex(i)) { + return; + } + i += 1; + } +} + +impl Edge { + pub fn source(&self) -> NodeIndex { + self.source + } + + pub fn target(&self) -> NodeIndex { + self.target + } +} diff --git a/src/librustc_data_structures/graph/test.rs b/src/librustc_data_structures/graph/test.rs new file mode 100644 index 00000000000..a26d1d2fbd9 --- /dev/null +++ b/src/librustc_data_structures/graph/test.rs @@ -0,0 +1,129 @@ +use graph::*; +use std::fmt::Debug; + +type TestNode = Node<&'static str>; +type TestEdge = Edge<&'static str>; +type TestGraph = Graph<&'static str, &'static str>; + +fn create_graph() -> TestGraph { + let mut graph = Graph::new(); + + // Create a simple graph + // + // A -+> B --> C + // | | ^ + // | v | + // F D --> E + + let a = graph.add_node("A"); + let b = graph.add_node("B"); + let c = graph.add_node("C"); + let d = graph.add_node("D"); + let e = graph.add_node("E"); + let f = graph.add_node("F"); + + graph.add_edge(a, b, "AB"); + graph.add_edge(b, c, "BC"); + graph.add_edge(b, d, "BD"); + graph.add_edge(d, e, "DE"); + graph.add_edge(e, c, "EC"); + graph.add_edge(f, b, "FB"); + + return graph; +} + +#[test] +fn each_node() { + let graph = create_graph(); + let expected = ["A", "B", "C", "D", "E", "F"]; + graph.each_node(|idx, node| { + assert_eq!(&expected[idx.0], graph.node_data(idx)); + assert_eq!(expected[idx.0], node.data); + true + }); +} + +#[test] +fn each_edge() { + let graph = create_graph(); + let expected = ["AB", "BC", "BD", "DE", "EC", "FB"]; + graph.each_edge(|idx, edge| { + assert_eq!(&expected[idx.0], graph.edge_data(idx)); + assert_eq!(expected[idx.0], edge.data); + true + }); +} + +fn test_adjacent_edges(graph: &Graph, + start_index: NodeIndex, + start_data: N, + expected_incoming: &[(E,N)], + expected_outgoing: &[(E,N)]) { + assert!(graph.node_data(start_index) == &start_data); + + let mut counter = 0; + for (edge_index, edge) in graph.incoming_edges(start_index) { + assert!(graph.edge_data(edge_index) == &edge.data); + assert!(counter < expected_incoming.len()); + debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}", + counter, expected_incoming[counter], edge_index, edge); + match expected_incoming[counter] { + (ref e, ref n) => { + assert!(e == &edge.data); + assert!(n == graph.node_data(edge.source())); + assert!(start_index == edge.target); + } + } + counter += 1; + } + assert_eq!(counter, expected_incoming.len()); + + let mut counter = 0; + for (edge_index, edge) in graph.outgoing_edges(start_index) { + assert!(graph.edge_data(edge_index) == &edge.data); + assert!(counter < expected_outgoing.len()); + debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}", + counter, expected_outgoing[counter], edge_index, edge); + match expected_outgoing[counter] { + (ref e, ref n) => { + assert!(e == &edge.data); + assert!(start_index == edge.source); + assert!(n == graph.node_data(edge.target)); + } + } + counter += 1; + } + assert_eq!(counter, expected_outgoing.len()); +} + +#[test] +fn each_adjacent_from_a() { + let graph = create_graph(); + test_adjacent_edges(&graph, NodeIndex(0), "A", + &[], + &[("AB", "B")]); +} + +#[test] +fn each_adjacent_from_b() { + let graph = create_graph(); + test_adjacent_edges(&graph, NodeIndex(1), "B", + &[("FB", "F"), ("AB", "A"),], + &[("BD", "D"), ("BC", "C"),]); +} + +#[test] +fn each_adjacent_from_c() { + let graph = create_graph(); + test_adjacent_edges(&graph, NodeIndex(2), "C", + &[("EC", "E"), ("BC", "B")], + &[]); +} + +#[test] +fn each_adjacent_from_d() { + let graph = create_graph(); + test_adjacent_edges(&graph, NodeIndex(3), "D", + &[("BD", "B")], + &[("DE", "E")]); +} diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs index 5f2f430df50..d90a40941cb 100644 --- a/src/librustc_data_structures/lib.rs +++ b/src/librustc_data_structures/lib.rs @@ -33,3 +33,5 @@ extern crate serialize as rustc_serialize; // used by deriving pub mod snapshot_vec; +pub mod graph; +pub mod bitvec; diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs index bdc3fdcfc14..33a817cfedb 100644 --- a/src/librustc_lint/builtin.rs +++ b/src/librustc_lint/builtin.rs @@ -1886,14 +1886,13 @@ impl LintPass for UnconditionalRecursion { continue; } // add the successors of this node to explore the graph further. - cfg.graph.each_outgoing_edge(idx, |_, edge| { + for (_, edge) in cfg.graph.outgoing_edges(idx) { let target_idx = edge.target(); let target_cfg_id = target_idx.node_id(); if !visited.contains(&target_cfg_id) { work_queue.push(target_idx) } - true - }); + } } // Check the number of self calls because a function that -- cgit 1.4.1-3-g733a5