src/librustc/middle/graph.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A graph module for use in dataflow, region resolution, and elsewhere.
  12 //!
  13 //! # Interface details
  14 //!
  15 //! You customize the graph by specifying a "node data" type `N` and an
  16 //! "edge data" type `E`. You can then later gain access (mutable or
  17 //! immutable) to these "user-data" bits. Currently, you can only add
  18 //! nodes or edges to the graph. You cannot remove or modify them once
  19 //! added. This could be changed if we have a need.
  20 //!
  21 //! # Implementation details
  22 //!
  23 //! The main tricky thing about this code is the way that edges are
  24 //! stored. The edges are stored in a central array, but they are also
  25 //! threaded onto two linked lists for each node, one for incoming edges
  26 //! and one for outgoing edges. Note that every edge is a member of some
  27 //! incoming list and some outgoing list.  Basically you can load the
  28 //! first index of the linked list from the node data structures (the
  29 //! field `first_edge`) and then, for each edge, load the next index from
  30 //! the field `next_edge`). Each of those fields is an array that should
  31 //! be indexed by the direction (see the type `Direction`).
  32
  33 #![allow(dead_code)] // still WIP
  34
  35 use std::fmt::{Formatter, Error, Show};
  36 use std::uint;
  37 use std::collections::BitvSet;
  38
  39 pub struct Graph<N,E> {
  40     nodes: Vec<Node<N>> ,
  41     edges: Vec<Edge<E>> ,
  42 }
  43
  44 pub struct Node<N> {
  45     first_edge: [EdgeIndex; 2], // see module comment
  46     pub data: N,
  47 }
  48
  49 pub struct Edge<E> {
  50     next_edge: [EdgeIndex; 2], // see module comment
  51     source: NodeIndex,
  52     target: NodeIndex,
  53     pub data: E,
  54 }
  55
  56 impl<E: Show> Show for Edge<E> {
  57     fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
  58         write!(f, "Edge {{ next_edge: [{}, {}], source: {}, target: {}, data: {} }}",
  59                self.next_edge[0], self.next_edge[1], self.source,
  60                self.target, self.data)
  61     }
  62 }
  63
  64 #[deriving(Clone, Copy, PartialEq, Show)]
  65 pub struct NodeIndex(pub uint);
  66 #[allow(non_upper_case_globals)]
  67 pub const InvalidNodeIndex: NodeIndex = NodeIndex(uint::MAX);
  68
  69 #[deriving(Copy, PartialEq, Show)]
  70 pub struct EdgeIndex(pub uint);
  71 #[allow(non_upper_case_globals)]
  72 pub const InvalidEdgeIndex: EdgeIndex = EdgeIndex(uint::MAX);
  73
  74 // Use a private field here to guarantee no more instances are created:
  75 #[deriving(Copy, Show)]
  76 pub struct Direction { repr: uint }
  77 #[allow(non_upper_case_globals)]
  78 pub const Outgoing: Direction = Direction { repr: 0 };
  79 #[allow(non_upper_case_globals)]
  80 pub const Incoming: Direction = Direction { repr: 1 };
  81
  82 impl NodeIndex {
  83     fn get(&self) -> uint { let NodeIndex(v) = *self; v }
  84     /// Returns unique id (unique with respect to the graph holding associated node).
  85     pub fn node_id(&self) -> uint { self.get() }
  86 }
  87
  88 impl EdgeIndex {
  89     fn get(&self) -> uint { let EdgeIndex(v) = *self; v }
  90     /// Returns unique id (unique with respect to the graph holding associated edge).
  91     pub fn edge_id(&self) -> uint { self.get() }
  92 }
  93
  94 impl<N,E> Graph<N,E> {
  95     pub fn new() -> Graph<N,E> {
  96         Graph {
  97             nodes: Vec::new(),
  98             edges: Vec::new(),
  99         }
 100     }
 101
 102     pub fn with_capacity(num_nodes: uint,
 103                          num_edges: uint) -> Graph<N,E> {
 104         Graph {
 105             nodes: Vec::with_capacity(num_nodes),
 106             edges: Vec::with_capacity(num_edges),
 107         }
 108     }
 109
 110     ///////////////////////////////////////////////////////////////////////////
 111     // Simple accessors
 112
 113     #[inline]
 114     pub fn all_nodes<'a>(&'a self) -> &'a [Node<N>] {
 115         let nodes: &'a [Node<N>] = self.nodes.as_slice();
 116         nodes
 117     }
 118
 119     #[inline]
 120     pub fn all_edges<'a>(&'a self) -> &'a [Edge<E>] {
 121         let edges: &'a [Edge<E>] = self.edges.as_slice();
 122         edges
 123     }
 124
 125     ///////////////////////////////////////////////////////////////////////////
 126     // Node construction
 127
 128     pub fn next_node_index(&self) -> NodeIndex {
 129         NodeIndex(self.nodes.len())
 130     }
 131
 132     pub fn add_node(&mut self, data: N) -> NodeIndex {
 133         let idx = self.next_node_index();
 134         self.nodes.push(Node {
 135             first_edge: [InvalidEdgeIndex, InvalidEdgeIndex],
 136             data: data
 137         });
 138         idx
 139     }
 140
 141     pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N {
 142         &mut self.nodes[idx.get()].data
 143     }
 144
 145     pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N {
 146         &self.nodes[idx.get()].data
 147     }
 148
 149     pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node<N> {
 150         &self.nodes[idx.get()]
 151     }
 152
 153     ///////////////////////////////////////////////////////////////////////////
 154     // Edge construction and queries
 155
 156     pub fn next_edge_index(&self) -> EdgeIndex {
 157         EdgeIndex(self.edges.len())
 158     }
 159
 160     pub fn add_edge(&mut self,
 161                     source: NodeIndex,
 162                     target: NodeIndex,
 163                     data: E) -> EdgeIndex {
 164         let idx = self.next_edge_index();
 165
 166         // read current first of the list of edges from each node
 167         let source_first = self.nodes[source.get()]
 168                                      .first_edge[Outgoing.repr];
 169         let target_first = self.nodes[target.get()]
 170                                      .first_edge[Incoming.repr];
 171
 172         // create the new edge, with the previous firsts from each node
 173         // as the next pointers
 174         self.edges.push(Edge {
 175             next_edge: [source_first, target_first],
 176             source: source,
 177             target: target,
 178             data: data
 179         });
 180
 181         // adjust the firsts for each node target be the next object.
 182         self.nodes[source.get()].first_edge[Outgoing.repr] = idx;
 183         self.nodes[target.get()].first_edge[Incoming.repr] = idx;
 184
 185         return idx;
 186     }
 187
 188     pub fn mut_edge_data<'a>(&'a mut self, idx: EdgeIndex) -> &'a mut E {
 189         &mut self.edges[idx.get()].data
 190     }
 191
 192     pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E {
 193         &self.edges[idx.get()].data
 194     }
 195
 196     pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge<E> {
 197         &self.edges[idx.get()]
 198     }
 199
 200     pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex {
 201         //! Accesses the index of the first edge adjacent to `node`.
 202         //! This is useful if you wish to modify the graph while walking
 203         //! the linked list of edges.
 204
 205         self.nodes[node.get()].first_edge[dir.repr]
 206     }
 207
 208     pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex {
 209         //! Accesses the next edge in a given direction.
 210         //! This is useful if you wish to modify the graph while walking
 211         //! the linked list of edges.
 212
 213         self.edges[edge.get()].next_edge[dir.repr]
 214     }
 215
 216     ///////////////////////////////////////////////////////////////////////////
 217     // Iterating over nodes, edges
 218
 219     pub fn each_node<'a, F>(&'a self, mut f: F) -> bool where
 220         F: FnMut(NodeIndex, &'a Node<N>) -> bool,
 221     {
 222         //! Iterates over all edges defined in the graph.
 223         self.nodes.iter().enumerate().all(|(i, node)| f(NodeIndex(i), node))
 224     }
 225
 226     pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool where
 227         F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
 228     {
 229         //! Iterates over all edges defined in the graph
 230         self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge))
 231     }
 232
 233     pub fn each_outgoing_edge<'a, F>(&'a self, source: NodeIndex, f: F) -> bool where
 234         F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
 235     {
 236         //! Iterates over all outgoing edges from the node `from`
 237
 238         self.each_adjacent_edge(source, Outgoing, f)
 239     }
 240
 241     pub fn each_incoming_edge<'a, F>(&'a self, target: NodeIndex, f: F) -> bool where
 242         F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
 243     {
 244         //! Iterates over all incoming edges to the node `target`
 245
 246         self.each_adjacent_edge(target, Incoming, f)
 247     }
 248
 249     pub fn each_adjacent_edge<'a, F>(&'a self,
 250                                      node: NodeIndex,
 251                                      dir: Direction,
 252                                      mut f: F)
 253                                      -> bool where
 254         F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
 255     {
 256         //! Iterates over all edges adjacent to the node `node`
 257         //! in the direction `dir` (either `Outgoing` or `Incoming)
 258
 259         let mut edge_idx = self.first_adjacent(node, dir);
 260         while edge_idx != InvalidEdgeIndex {
 261             let edge = &self.edges[edge_idx.get()];
 262             if !f(edge_idx, edge) {
 263                 return false;
 264             }
 265             edge_idx = edge.next_edge[dir.repr];
 266         }
 267         return true;
 268     }
 269
 270     ///////////////////////////////////////////////////////////////////////////
 271     // Fixed-point iteration
 272     //
 273     // A common use for graphs in our compiler is to perform
 274     // fixed-point iteration. In this case, each edge represents a
 275     // constraint, and the nodes themselves are associated with
 276     // variables or other bitsets. This method facilitates such a
 277     // computation.
 278
 279     pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) where
 280         F: FnMut(uint, EdgeIndex, &'a Edge<E>) -> bool,
 281     {
 282         let mut iteration = 0;
 283         let mut changed = true;
 284         while changed {
 285             changed = false;
 286             iteration += 1;
 287             for (i, edge) in self.edges.iter().enumerate() {
 288                 changed |= op(iteration, EdgeIndex(i), edge);
 289             }
 290         }
 291     }
 292
 293     pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E>  {
 294         DepthFirstTraversal {
 295             graph: self,
 296             stack: vec![start],
 297             visited: BitvSet::new()
 298         }
 299     }
 300 }
 301
 302 pub struct DepthFirstTraversal<'g, N:'g, E:'g> {
 303     graph: &'g Graph<N, E>,
 304     stack: Vec<NodeIndex>,
 305     visited: BitvSet
 306 }
 307
 308 impl<'g, N, E> Iterator<&'g N> for DepthFirstTraversal<'g, N, E> {
 309     fn next(&mut self) -> Option<&'g N> {
 310         while let Some(idx) = self.stack.pop() {
 311             if !self.visited.insert(idx.node_id()) {
 312                 continue;
 313             }
 314             self.graph.each_outgoing_edge(idx, |_, e| -> bool {
 315                 if !self.visited.contains(&e.target().node_id()) {
 316                     self.stack.push(e.target());
 317                 }
 318                 true
 319             });
 320
 321             return Some(self.graph.node_data(idx));
 322         }
 323
 324         return None;
 325     }
 326 }
 327
 328 pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F) where
 329     F: FnMut(EdgeIndex) -> bool,
 330 {
 331     let mut i = 0;
 332     let n = max_edge_index.get();
 333     while i < n {
 334         if !f(EdgeIndex(i)) {
 335             return;
 336         }
 337         i += 1;
 338     }
 339 }
 340
 341 impl<E> Edge<E> {
 342     pub fn source(&self) -> NodeIndex {
 343         self.source
 344     }
 345
 346     pub fn target(&self) -> NodeIndex {
 347         self.target
 348     }
 349 }
 350
 351 #[cfg(test)]
 352 mod test {
 353     use middle::graph::*;
 354     use std::fmt::Show;
 355
 356     type TestNode = Node<&'static str>;
 357     type TestEdge = Edge<&'static str>;
 358     type TestGraph = Graph<&'static str, &'static str>;
 359
 360     fn create_graph() -> TestGraph {
 361         let mut graph = Graph::new();
 362
 363         // Create a simple graph
 364         //
 365         //    A -+> B --> C
 366         //       |  |     ^
 367         //       |  v     |
 368         //       F  D --> E
 369
 370         let a = graph.add_node("A");
 371         let b = graph.add_node("B");
 372         let c = graph.add_node("C");
 373         let d = graph.add_node("D");
 374         let e = graph.add_node("E");
 375         let f = graph.add_node("F");
 376
 377         graph.add_edge(a, b, "AB");
 378         graph.add_edge(b, c, "BC");
 379         graph.add_edge(b, d, "BD");
 380         graph.add_edge(d, e, "DE");
 381         graph.add_edge(e, c, "EC");
 382         graph.add_edge(f, b, "FB");
 383
 384         return graph;
 385     }
 386
 387     #[test]
 388     fn each_node() {
 389         let graph = create_graph();
 390         let expected = ["A", "B", "C", "D", "E", "F"];
 391         graph.each_node(|idx, node| {
 392             assert_eq!(&expected[idx.get()], graph.node_data(idx));
 393             assert_eq!(expected[idx.get()], node.data);
 394             true
 395         });
 396     }
 397
 398     #[test]
 399     fn each_edge() {
 400         let graph = create_graph();
 401         let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
 402         graph.each_edge(|idx, edge| {
 403             assert_eq!(&expected[idx.get()], graph.edge_data(idx));
 404             assert_eq!(expected[idx.get()], edge.data);
 405             true
 406         });
 407     }
 408
 409     fn test_adjacent_edges<N:PartialEq+Show,E:PartialEq+Show>(graph: &Graph<N,E>,
 410                                       start_index: NodeIndex,
 411                                       start_data: N,
 412                                       expected_incoming: &[(E,N)],
 413                                       expected_outgoing: &[(E,N)]) {
 414         assert!(graph.node_data(start_index) == &start_data);
 415
 416         let mut counter = 0;
 417         graph.each_incoming_edge(start_index, |edge_index, edge| {
 418             assert!(graph.edge_data(edge_index) == &edge.data);
 419             assert!(counter < expected_incoming.len());
 420             debug!("counter={} expected={} edge_index={} edge={}",
 421                    counter, expected_incoming[counter], edge_index, edge);
 422             match expected_incoming[counter] {
 423                 (ref e, ref n) => {
 424                     assert!(e == &edge.data);
 425                     assert!(n == graph.node_data(edge.source));
 426                     assert!(start_index == edge.target);
 427                 }
 428             }
 429             counter += 1;
 430             true
 431         });
 432         assert_eq!(counter, expected_incoming.len());
 433
 434         let mut counter = 0;
 435         graph.each_outgoing_edge(start_index, |edge_index, edge| {
 436             assert!(graph.edge_data(edge_index) == &edge.data);
 437             assert!(counter < expected_outgoing.len());
 438             debug!("counter={} expected={} edge_index={} edge={}",
 439                    counter, expected_outgoing[counter], edge_index, edge);
 440             match expected_outgoing[counter] {
 441                 (ref e, ref n) => {
 442                     assert!(e == &edge.data);
 443                     assert!(start_index == edge.source);
 444                     assert!(n == graph.node_data(edge.target));
 445                 }
 446             }
 447             counter += 1;
 448             true
 449         });
 450         assert_eq!(counter, expected_outgoing.len());
 451     }
 452
 453     #[test]
 454     fn each_adjacent_from_a() {
 455         let graph = create_graph();
 456         test_adjacent_edges(&graph, NodeIndex(0), "A",
 457                             &[],
 458                             &[("AB", "B")]);
 459     }
 460
 461     #[test]
 462     fn each_adjacent_from_b() {
 463         let graph = create_graph();
 464         test_adjacent_edges(&graph, NodeIndex(1), "B",
 465                             &[("FB", "F"), ("AB", "A"),],
 466                             &[("BD", "D"), ("BC", "C"),]);
 467     }
 468
 469     #[test]
 470     fn each_adjacent_from_c() {
 471         let graph = create_graph();
 472         test_adjacent_edges(&graph, NodeIndex(2), "C",
 473                             &[("EC", "E"), ("BC", "B")],
 474                             &[]);
 475     }
 476
 477     #[test]
 478     fn each_adjacent_from_d() {
 479         let graph = create_graph();
 480         test_adjacent_edges(&graph, NodeIndex(3), "D",
 481                             &[("BD", "B")],
 482                             &[("DE", "E")]);
 483     }
 484 }