portdiff 0.3.1

Data structure for fast local graph rewriting.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

use std::collections::{BTreeMap, BTreeSet};

use itertools::Itertools;

use crate::{
    port::{Port, Site},
    Graph, PortDiff,
};

use super::{EdgeData, PortDiffPtr, UniqueNodeId};

impl<G: Graph> PortDiff<G> {
    fn all_ports<'a>(
        &'a self,
        unbound_port: &'a Site<G::Node, G::PortLabel>,
    ) -> impl Iterator<Item = Port<G>> + 'a {
        let internal = self
            .graph
            .get_bound_ports(unbound_port)
            .map(|port| Port::Bound {
                port,
                owner: self.clone(),
            });
        let boundary = self
            .boundary
            .contains_key(unbound_port)
            .then_some(Port::Unbound {
                port: unbound_port.clone(),
                owner: self.clone(),
            });
        internal.chain(boundary)
    }
}

pub struct DiffTraverser<G: Graph> {
    exclude_nodes: BTreeMap<PortDiffPtr<G>, BTreeSet<G::Node>>,
}

impl<G: Graph> Clone for DiffTraverser<G> {
    fn clone(&self) -> Self {
        Self {
            exclude_nodes: self.exclude_nodes.clone(),
        }
    }
}

impl<G: Graph> Default for DiffTraverser<G> {
    fn default() -> Self {
        Self {
            exclude_nodes: BTreeMap::new(),
        }
    }
}

impl<G: Graph> PortDiff<G> {
    pub fn traverse<'a>(
        node: UniqueNodeId<G>,
        port_label: G::PortLabel,
        known_edges: &[EdgeData<G>],
    ) -> Vec<EdgeData<G>>
    where
        G: 'a,
    {
        let diff = node.owner;
        let unbound_port = Site {
            node: node.node,
            port: port_label,
        };
        diff.all_ports(&unbound_port)
            .flat_map(|port| PortDiff::opposite_ports(port))
            // TODO: This should be awfully slow
            .filter(|edge| {
                PortDiff::are_compatible(edge_diffs(known_edges.iter().chain(Some(edge))))
            })
            .collect_vec()
    }
}

fn edge_diffs<'d, G: Graph>(
    edges: impl IntoIterator<Item = &'d EdgeData<G>>,
) -> impl Iterator<Item = &'d PortDiff<G>>
where
    G: 'd,
{
    edges
        .into_iter()
        .flat_map(|edge| match edge {
            EdgeData::Internal { owner, .. } => vec![owner],
            EdgeData::Boundary { left, right } => vec![left.owner(), right.owner()],
        })
        .unique()
}

#[cfg(test)]
mod tests {
    use rstest::rstest;

    use crate::port_diff::tests::{root_diff, TestPortDiff};

    use super::*;

    #[rstest]
    fn test_traverse(root_diff: TestPortDiff) {
        let (n0, n1, n2, n3) = root_diff.nodes().collect_tuple().unwrap();
        let child_a = root_diff.identity_subgraph([n0, n1]);
        let child_b = root_diff.identity_subgraph([n2, n3]);

        let edges = child_a.traverse(n0, 0, &[]);
        assert_eq!(edges.len(), 1);
        assert_eq!(edges[0].right().node(), n1);
    }
}