evmil/util/
digraph.rs

1// Licensed under the Apache License, Version 2.0 (the "License");
2// you may not use this file except in compliance with the License.
3// You may obtain a copy of the License at
4//
5//    http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS,
9// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
10// See the License for the specific language governing permissions and
11// limitations under the License.
12use crate::util::{Seq,SortedVec};
13
14pub type EdgeSet = SortedVec<usize>;
15
16/// Represents a _bidirectional_ directed graph over a sequence of
17/// _nodes_.  Edges can be added/removed, and iterated over in the
18/// _forwards_ or _backwards_ direction.  The underlying datastructure
19/// is that of an adjacency list.
20pub struct Digraph<T>
21where T:Seq {
22    /// Node sequence underlying this representation.
23    nodes: T,
24    /// For each block, the corresponding set of incoming edges
25    /// (i.e. edges which transfer control into this block).
26    incoming: Vec<EdgeSet>,
27    /// For each block, the corresponding set of outgoing edges
28    /// (i.e. edges which transfer control out of this block).
29    outgoing: Vec<EdgeSet>    
30}
31
32impl<T> Digraph<T>
33where T:Seq {
34    pub fn new(n: usize, nodes: T) -> Self {
35        let incoming = vec![SortedVec::new();n];
36        let outgoing = vec![SortedVec::new();n];
37        Self{nodes,incoming,outgoing}
38    }
39    
40    /// Returns the number of nodes stored within this graph.    
41    pub fn len(&self) -> usize {
42        self.nodes.len()
43    }
44
45    /// Returns `true` if the node set for this graph is empty.
46    pub fn is_empty(&self) -> bool {
47        self.nodes.is_empty()
48    }
49
50    /// Returns `true` if there is an edge from node `from` to node
51    /// `to`.
52    pub fn is_connected(&self, from: usize, to: usize) -> bool {
53        self.outgoing[from].contains(to)
54    }
55    
56    /// Returns the ith block within this graph.    
57    pub fn get(&self, index: usize) -> T::Output {
58        self.nodes.get(index).unwrap()
59    }
60    
61    /// Get the underlying nodes of this graph (in whatever form they
62    /// are provided).
63    pub fn nodes(&self) -> &T {
64        &self.nodes
65    }
66    
67    /// Returns the set of blocks which can transfer control _into_ a
68    /// given block (`blk`).    
69    pub fn incoming(&self, blk: usize) -> &EdgeSet {
70        &self.incoming[blk]        
71    }
72
73    /// Returns the set of blocks to which a given block (`blk`) can
74    /// transfer control.    
75    pub fn outgoing(&self, blk: usize) -> &EdgeSet {
76        &self.outgoing[blk]
77    }
78
79    /// Returns an iterator over the _outgoing edges_ in this graph
80    pub fn out_iter(&self) -> DigraphIterator {
81        DigraphIterator::new(true,&self.outgoing)
82    }
83
84    /// Returns an iterator over the _incoming edges_ in this graph
85    pub fn in_iter(&self) -> DigraphIterator {
86        DigraphIterator::new(false,&self.incoming)
87    }    
88    
89    /// Connect one basic block to another which forms a directed edge
90    /// in the graph.  Returns `true` if a connection was added.
91    pub fn connect(&mut self, from: usize, to: usize) -> bool {
92        self.incoming[to].insert(from);
93        self.outgoing[from].insert(to)
94    }
95
96    /// Remove a connection between two basic blocks from the graph.
97    /// Returns `true` if a connection was removed.
98    pub fn disconnect(&mut self, from: usize, to: usize) -> bool {
99        self.incoming[to].remove(&from);
100        self.outgoing[from].remove(&to)
101    }
102}
103
104/// An iterator over the edges of a graph which iterates over the
105/// incoming or outgoing edges of the graph.
106pub struct DigraphIterator<'a> {
107    // Direction of edges which is either `true` (i.e. outgoing) or
108    // `false` (i.e. incoming).
109    dir: bool,
110    // Edge sets being iterated over.
111    items: &'a [EdgeSet],
112    // Current edgeset being considered.
113    i: usize,
114    // Current position within edgeset being considered.
115    j: usize 
116}
117
118impl<'a> DigraphIterator<'a> {
119    pub fn new(dir: bool, items: &'a [EdgeSet]) -> Self {
120        Self{dir,items,i:0,j:0}
121    }
122}
123
124impl<'a> Iterator for DigraphIterator<'a> {
125    // An edge
126    type Item = (usize,usize);
127
128    fn next(&mut self) -> Option<Self::Item> {
129        //
130        while self.i < self.items.len() {
131            let head = &self.items[self.i];
132            // sanity check position
133            if self.j >= head.len() {
134                self.j = 0;
135                self.i += 1;
136            } else {
137                // Found an edge
138                let k = head[self.j];
139                self.j += 1;
140                // Construct edge
141                let edge = if self.dir { (self.i,k) } else { (k,self.i) };
142                // Done
143                return Some(edge);
144            }
145        }
146        // Empty
147        None
148    }
149}
evmil/util/digraph.rs

evmil/util/
digraph.rs
