cfg_predict/
distance.rs

1//! Calculation of minimum distance from one part of the grammar to another.
2
3use cfg_grammar::history::node::LinkedHistoryNode;
4use cfg_grammar::rhs_closure::RhsClosure;
5// use cfg_grammar::rule::GrammarRule;
6use cfg_grammar::symbol::set::SymbolBitSet;
7use cfg_grammar::*;
8
9/// Calculation of minimum distance from one part of the grammar to another.
10/// Similar to multi-source shortest path search in a graph.
11pub struct MinimalDistance<'a, G: 'a> {
12    grammar: &'a G,
13    distances: Vec<(HistoryId, Vec<Option<u32>>)>,
14    prediction_distances: Vec<Option<u32>>,
15    completion_distances: Vec<Option<u32>>,
16    min_of: Vec<Option<u32>>,
17}
18
19impl<'a, G> MinimalDistance<'a, G>
20where
21    G: RuleContainer,
22{
23    /// Returns a new `MinimalDistance` for a grammar.
24    pub fn new(grammar: &'a G) -> Self {
25        let distances = grammar
26            .rules()
27            .map(|rule| (rule.history_id, vec![None; rule.rhs.len() + 1]))
28            .collect();
29        MinimalDistance {
30            grammar: grammar,
31            distances: distances,
32            prediction_distances: vec![None; grammar.num_syms()],
33            completion_distances: vec![None; grammar.num_syms()],
34            min_of: vec![None; grammar.num_syms()],
35        }
36    }
37
38    /// Returns distances in order respective to the order of rule iteration.
39    pub fn distances(&self) -> &[(HistoryId, Vec<Option<u32>>)] {
40        &self.distances[..]
41    }
42
43    /// Calculates minimal distance from one parts of the grammar to others.
44    /// Returns distances in order respective to the order of rule iteration.
45    pub fn minimal_distances(&mut self) -> &[(HistoryId, Vec<Option<u32>>)] {
46        self.minimal_sentence_lengths();
47        self.immediate_minimal_distances();
48        self.transitive_minimal_distances();
49        self.distances()
50    }
51
52    fn minimal_sentence_lengths(&mut self) {
53        // The distance for terminals is 1.
54        let terminal_set = SymbolBitSet::terminal_set(self.grammar);
55        for terminal in terminal_set.iter() {
56            self.min_of[terminal.usize()] = Some(1);
57        }
58        // The distance for nullable symbols is 0.
59        for rule in self.grammar.rules() {
60            if rule.rhs.is_empty() {
61                self.min_of[rule.lhs.usize()] = Some(0);
62            }
63        }
64        // Calculate minimal lengths for nonterminals.
65        RhsClosure::new(self.grammar).rhs_closure_with_values(&mut self.min_of);
66    }
67
68    fn immediate_minimal_distances(&mut self) {
69        // Calculates distances within rules.
70        for (idx, rule) in self.grammar.rules().enumerate() {
71            let mut history = &self.grammar.history_graph()[rule.history_id.get()];
72            let mut positions = &[][..];
73            while let &HistoryNode::Linked { prev, ref node } = history {
74                if let &LinkedHistoryNode::Distances { ref events } = node {
75                    positions = &events[..];
76                }
77                history = &self.grammar.history_graph()[prev.get()];
78            }
79            for &position in positions {
80                let (min, _) = self.update_rule_distances(0, &rule.rhs[..position as usize], idx);
81                set_min(&mut self.prediction_distances[rule.lhs.usize()], min);
82            }
83        }
84    }
85
86    /// Calculates lengths of shortest paths that cross transitions (predictions and completions).
87    fn transitive_minimal_distances(&mut self) {
88        let mut changed = true;
89        while changed {
90            // Keep going for as long as any completion distances were lowered in the last pass.
91            changed = false;
92            for (idx, rule) in self.grammar.rules().enumerate() {
93                if let Some(distance) = self.completion_distances[rule.lhs.usize()] {
94                    let (_, changed_now) = self.update_rule_distances(distance, rule.rhs, idx);
95                    changed |= changed_now;
96                }
97            }
98        }
99    }
100
101    // Update distances in a rule.
102    fn update_rule_distances(&mut self, mut cur: u32, rhs: &[Symbol], idx: usize) -> (u32, bool) {
103        let &mut (_, ref mut set) = &mut self.distances[idx];
104        for (dot, sym) in rhs.iter().enumerate().rev() {
105            set_min(&mut self.completion_distances[sym.usize()], cur);
106            set_min(&mut set[dot + 1], cur);
107            cur += self.min_of[sym.usize()].unwrap();
108            if let Some(sym_predicted) = self.prediction_distances[sym.usize()] {
109                cur = cur.min(sym_predicted);
110            }
111        }
112        let changed = set_min(&mut set[0], cur);
113        (cur, changed)
114    }
115}
116
117/// Updates a value with a minimum of two values.
118fn set_min(current: &mut Option<u32>, new: u32) -> bool {
119    if let Some(ref mut current) = *current {
120        if *current > new {
121            *current = new;
122            true
123        } else {
124            false
125        }
126    } else {
127        *current = Some(new);
128        true
129    }
130}
cfg_predict/distance.rs

cfg_predict/
distance.rs
