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