pattern_compiler/
lib.rs

1// Implements a variant of
2// http://www.cs.tufts.edu/~nr/cs257/archive/luc-maranget/jun08.pdf
3
4extern crate petgraph;
5extern crate prettytable;
6extern crate either;
7//extern crate util;
8#[macro_use] extern crate derivative;
9
10use ::std::collections::HashMap;
11
12mod pattern;
13pub use self::pattern::{ PatternProvider, ExpandedClauseNodes };
14
15mod cfg;
16pub use self::cfg::{ PatternCfg, CfgEdge };
17
18mod matrix;
19
20pub mod simple_pattern;
21
22use ::petgraph::graph::NodeIndex;
23
24#[derive(Debug)]
25pub struct MatchCompileContext<'a, P> where P: pattern::PatternProvider + 'a {
26    pattern: &'a mut P,
27
28    cfg: cfg::PatternCfg<P>,
29    leaf_bindings: HashMap<NodeIndex, HashMap<P::CfgVariable, P::PatternNodeKey>>,
30
31    root_matrix: matrix::MatchMatrix<P>,
32    fail_leaf: NodeIndex,
33}
34impl<'a, P> MatchCompileContext<'a, P> where P: PatternProvider {
35
36    pub fn new(pattern: &'a mut P) -> Self {
37        let root = pattern.get_root();
38
39        let mut cfg = cfg::PatternCfg::new();
40        let fail_leaf = cfg.add_fail();
41        let leaves: Vec<NodeIndex> = (0..(root.clauses))
42            .map(|idx| cfg.add_leaf(idx))
43            .collect();
44
45        let leaf_bindings = leaves.iter()
46            .map(|leaf| {
47                let bindings: HashMap<P::CfgVariable, P::PatternNodeKey> = HashMap::new();
48                (*leaf, bindings)
49            })
50            .collect();
51
52        let root_matrix = matrix::MatchMatrix::new(
53            &root.nodes, leaves, root.variables);
54
55        MatchCompileContext {
56            pattern: pattern,
57
58            cfg: cfg,
59            leaf_bindings: leaf_bindings,
60
61            root_matrix: root_matrix,
62            fail_leaf: fail_leaf,
63        }
64    }
65
66    pub fn root_matrix(&self) -> &matrix::MatchMatrix<P> {
67        &self.root_matrix
68    }
69
70}
71
72fn matrix_to_decision_tree<P>(parent: cfg::CfgNodeIndex,
73                              ctx: &mut MatchCompileContext<P>,
74                              spec: P::PatternNodeKind,
75                              matrix: &matrix::MatchMatrix<P>,
76                              introduced_vars: Vec<P::CfgVariable>)
77    where P: PatternProvider
78{
79    let edge = cfg::CfgEdge {
80        kind: spec.clone(),
81        variable_binds: introduced_vars,
82    };
83
84    // Matrix is empty, no specializations can be done.
85    if matrix.is_empty() {
86        ctx.cfg.add_edge(parent, ctx.fail_leaf, edge);
87        return;
88    }
89
90    // If the head of the matrix has only wildcards, none of the other rows
91    // can happen.
92    if let Some(node) = matrix.has_wildcard_head(&ctx.pattern) {
93        ctx.cfg.add_edge(parent, node, edge);
94        return;
95    }
96
97
98    // Select the variable we should specialize on.
99    // This will be the column with the most consecutive non-wildcards
100    // at the head.
101    let specialize_variable = matrix.select_specialize_variable(&ctx.pattern);
102    let specialize_variable_cfg_var = matrix.get_var(specialize_variable);
103
104    // Add new CFG node for current
105    let cfg_node = ctx.cfg.add_child(parent, edge, specialize_variable_cfg_var);
106
107    // Find what pattern types we have as children, so that we can
108    // specialize and branch to them in the CFG
109    let specialization_types = matrix.collect_specialization_types(
110        &ctx.pattern, specialize_variable);
111
112    // Specialize on specific matrices
113    for specialization in specialization_types.iter() {
114        let (introduced, specialized) = matrix.specialize(ctx, specialize_variable,
115                                                          *specialization);
116
117        // TODO: Dedup
118        // Add variable bindings to the current specializations
119        for (leaf, clause) in specialized.iterate_clauses() {
120            let leaf_bindings = ctx.leaf_bindings.get_mut(&leaf).unwrap();
121            for (variable_num, variable_node) in clause.iter().enumerate() {
122                leaf_bindings.insert(specialized.get_var(variable_num), variable_node.node);
123            }
124        }
125
126        matrix_to_decision_tree(
127            cfg_node, ctx, *specialization,
128            &specialized, introduced);
129    }
130
131    // Specialize on default matrix
132    let (introduced, default) = matrix.default(ctx, specialize_variable);
133
134    // TODO: Dedup
135    // Add variable bindings to the current specializations
136    for (leaf, clause) in default.iterate_clauses() {
137        let leaf_bindings = ctx.leaf_bindings.get_mut(&leaf).unwrap();
138        for (variable_num, variable_node) in clause.iter().enumerate() {
139            leaf_bindings.insert(default.get_var(variable_num), variable_node.node);
140        }
141    }
142
143    let wildcard = ctx.pattern.get_wildcard();
144    matrix_to_decision_tree(
145        cfg_node, ctx,
146        wildcard,
147        &default, introduced);
148
149}
150
151pub fn to_decision_tree<P>(pattern: &mut P) -> cfg::PatternCfg<P>
152    where P: PatternProvider
153{
154    let mut context = MatchCompileContext::new(pattern);
155
156    let root: matrix::MatchMatrix<P> = (*context.root_matrix()).clone();
157
158    let root_cfg = context.cfg.get_entry();
159    let wildcard = context.pattern.get_wildcard();
160
161    matrix_to_decision_tree(root_cfg, &mut context,
162                            wildcard,
163                            &root,
164                            root.variables.clone());
165
166    let mut cfg = context.cfg;
167    cfg.leaf_bindings = context.leaf_bindings;
168
169    assert!(!::petgraph::algo::is_cyclic_directed(&cfg.graph));
170    cfg
171}
pattern_compiler/lib.rs

pattern_compiler/
lib.rs
