Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to 'tamer/src/ir/asg/base.rs')
-rw-r--r--tamer/src/ir/asg/base.rs119
1 files changed, 43 insertions, 76 deletions
diff --git a/tamer/src/ir/asg/base.rs b/tamer/src/ir/asg/base.rs
index 637c892..6dc690c 100644
--- a/tamer/src/ir/asg/base.rs
+++ b/tamer/src/ir/asg/base.rs
@@ -20,7 +20,7 @@
//! Base concrete [`Asg`] implementation.
use super::graph::{
- Asg, AsgEdge, AsgError, AsgResult, Node, ObjectRef, SortableAsg,
+ Asg, AsgEdge, AsgError, AsgResult, IndexType, Node, ObjectRef, SortableAsg,
};
use super::ident::IdentKind;
use super::object::{
@@ -28,11 +28,8 @@ use super::object::{
};
use super::Sections;
use crate::sym::Symbol;
-use fixedbitset::FixedBitSet;
-use petgraph::graph::{
- DiGraph, EdgeIndex, Graph, IndexType, Neighbors, NodeIndex,
-};
-use petgraph::visit::{DfsPostOrder, GraphBase, IntoNeighbors, Visitable};
+use petgraph::graph::{DiGraph, Graph, NodeIndex};
+use petgraph::visit::DfsPostOrder;
/// Concrete ASG.
///
@@ -68,6 +65,13 @@ where
Ix: IndexType,
O: IdentObjectState<'i, O> + IdentObjectData<'i>,
{
+ /// Create a new ASG.
+ ///
+ /// See also [`with_capacity`](BaseAsg::with_capacity).
+ pub fn new() -> Self {
+ Self::with_capacity(0, 0)
+ }
+
/// Create an ASG with the provided initial capacity.
///
/// The value for `objects` will be used as the capacity for the nodes
@@ -78,10 +82,6 @@ where
/// different types of objects,
/// but it's safe to say that each object will have at least one
/// edge to another object.
- ///
- /// A basic `new` method is not provided to ensure that callers consider
- /// capacity during construction,
- /// since graphs can get quite large.
pub fn with_capacity(objects: usize, edges: usize) -> Self {
let mut graph = Graph::with_capacity(objects, edges);
let mut index = Vec::with_capacity(objects);
@@ -136,7 +136,7 @@ where
let index = self.graph.add_node(Some(O::declare(ident)));
self.index_identifier(ident, index);
- ObjectRef(index)
+ ObjectRef::new(index)
})
}
@@ -176,7 +176,7 @@ where
where
F: FnOnce(O) -> TransitionResult<O>,
{
- let node = self.graph.node_weight_mut(identi.0).unwrap();
+ let node = self.graph.node_weight_mut(identi.into()).unwrap();
let obj = node
.take()
@@ -277,7 +277,7 @@ where
#[inline]
fn get<I: Into<ObjectRef<Ix>>>(&self, index: I) -> Option<&O> {
- self.graph.node_weight(index.into().0).map(|node| {
+ self.graph.node_weight(index.into().into()).map(|node| {
node.as_ref()
.expect("internal error: BaseAsg::get missing Node data")
})
@@ -290,16 +290,17 @@ where
self.index
.get(i)
.filter(|ni| ni.index() > 0)
- .map(|ni| ObjectRef(*ni))
+ .map(|ni| ObjectRef::new(*ni))
}
fn add_dep(&mut self, identi: ObjectRef<Ix>, depi: ObjectRef<Ix>) {
- self.graph.update_edge(identi.0, depi.0, Default::default());
+ self.graph
+ .update_edge(identi.into(), depi.into(), Default::default());
}
#[inline]
fn has_dep(&self, ident: ObjectRef<Ix>, dep: ObjectRef<Ix>) -> bool {
- self.graph.contains_edge(ident.0, dep.0)
+ self.graph.contains_edge(ident.into(), dep.into())
}
fn add_dep_lookup(
@@ -310,7 +311,8 @@ where
let identi = self.lookup_or_missing(ident);
let depi = self.lookup_or_missing(dep);
- self.graph.update_edge(identi.0, depi.0, Default::default());
+ self.graph
+ .update_edge(identi.into(), depi.into(), Default::default());
(identi, depi)
}
@@ -367,41 +369,6 @@ where
}
}
-// TODO: encapsulate Petgraph API (N.B. this is untested!)
-impl<'i, O, Ix> Visitable for BaseAsg<O, Ix>
-where
- Ix: IndexType,
-{
- type Map = FixedBitSet;
-
- fn visit_map(&self) -> Self::Map {
- self.graph.visit_map()
- }
-
- fn reset_map(&self, map: &mut Self::Map) {
- self.graph.reset_map(map)
- }
-}
-
-impl<'i, O, Ix> GraphBase for BaseAsg<O, Ix>
-where
- Ix: IndexType,
-{
- type NodeId = NodeIndex<Ix>;
- type EdgeId = EdgeIndex<Ix>;
-}
-
-impl<'a, 'i, O, Ix> IntoNeighbors for &'a BaseAsg<O, Ix>
-where
- Ix: IndexType,
-{
- type Neighbors = Neighbors<'a, AsgEdge, Ix>;
-
- fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
- self.graph.neighbors(n)
- }
-}
-
#[cfg(test)]
mod test {
use super::super::graph::AsgError;
@@ -513,7 +480,7 @@ mod test {
#[test]
fn declare_new_unique_idents() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
// NB: The index ordering is important! We first use a larger
// index to create a gap, and then use an index within that gap
@@ -571,7 +538,7 @@ mod test {
#[test]
fn lookup_by_symbol() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "lookup");
let node = sut.declare(
@@ -590,7 +557,7 @@ mod test {
#[test]
fn declare_returns_existing() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "symdup");
let src = Source::default();
@@ -616,7 +583,7 @@ mod test {
// Builds upon declare_returns_existing.
#[test]
fn declare_fails_if_transition_fails() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "symdup");
let src = Source {
@@ -652,7 +619,7 @@ mod test {
#[test]
fn declare_extern_returns_existing() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "symext");
let src = Source::default();
@@ -678,7 +645,7 @@ mod test {
// Builds upon declare_returns_existing.
#[test]
fn declare_extern_fails_if_transition_fails() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "symdup");
let src = Source {
@@ -718,7 +685,7 @@ mod test {
#[test]
fn add_fragment_to_ident() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "tofrag");
let src = Source {
@@ -748,7 +715,7 @@ mod test {
#[test]
fn add_fragment_to_ident_fails_if_transition_fails() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "failfrag");
let src = Source {
@@ -782,7 +749,7 @@ mod test {
#[test]
fn add_ident_dep_to_ident() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "sym");
let dep = symbol_dummy!(2, "dep");
@@ -803,7 +770,7 @@ mod test {
// same as above test
#[test]
fn add_dep_lookup_existing() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "sym");
let dep = symbol_dummy!(2, "dep");
@@ -819,7 +786,7 @@ mod test {
#[test]
fn add_dep_lookup_missing() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "sym");
let dep = symbol_dummy!(2, "dep");
@@ -836,7 +803,7 @@ mod test {
#[test]
fn declare_return_missing_symbol() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "sym");
let dep = symbol_dummy!(2, "dep");
@@ -893,7 +860,7 @@ mod test {
#[test]
fn graph_sort() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let mut meta = vec![];
let mut worksheet = vec![];
@@ -937,7 +904,7 @@ mod test {
#[test]
fn graph_sort_missing_node() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "sym");
let dep = symbol_dummy!(2, "dep");
@@ -968,7 +935,7 @@ mod test {
#[test]
fn graph_sort_no_roots() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = symbol_dummy!(1, "sym");
let dep = symbol_dummy!(2, "dep");
@@ -984,7 +951,7 @@ mod test {
#[test]
fn graph_sort_simple_cycle() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym");
let dep = Symbol::new_dummy(SymbolIndex::from_u32(3), "dep");
@@ -1028,7 +995,7 @@ mod test {
#[test]
fn graph_sort_two_simple_cycles() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym");
let sym2 = Symbol::new_dummy(SymbolIndex::from_u32(3), "sym2");
@@ -1098,7 +1065,7 @@ mod test {
#[test]
fn graph_sort_no_cycle_with_edge_to_same_node() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym");
let dep = Symbol::new_dummy(SymbolIndex::from_u32(3), "dep");
@@ -1139,7 +1106,7 @@ mod test {
#[test]
fn graph_sort_cycle_with_a_few_steps() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym1 = Symbol::new_dummy(SymbolIndex::from_u32(1), "sym1");
let sym2 = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym2");
@@ -1196,7 +1163,7 @@ mod test {
#[test]
fn graph_sort_cyclic_function_with_non_function_with_a_few_steps(
) -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym1 = Symbol::new_dummy(SymbolIndex::from_u32(1), "sym1");
let sym2 = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym2");
@@ -1252,7 +1219,7 @@ mod test {
#[test]
fn graph_sort_cyclic_bookended_by_functions() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym1 = Symbol::new_dummy(SymbolIndex::from_u32(1), "sym1");
let sym2 = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym2");
@@ -1308,7 +1275,7 @@ mod test {
#[test]
fn graph_sort_cyclic_function_ignored() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym");
let dep = Symbol::new_dummy(SymbolIndex::from_u32(3), "dep");
@@ -1349,7 +1316,7 @@ mod test {
#[test]
fn graph_sort_cyclic_function_is_bookended() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym1 = Symbol::new_dummy(SymbolIndex::from_u32(1), "sym1");
let sym2 = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym2");
@@ -1405,7 +1372,7 @@ mod test {
#[test]
fn graph_sort_ignore_non_linked() -> AsgResult<(), u8> {
- let mut sut = Sut::with_capacity(0, 0);
+ let mut sut = Sut::new();
let sym = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym");
let dep = Symbol::new_dummy(SymbolIndex::from_u32(3), "dep");