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