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