cfg_history/
lib.rs

1//! Any data carried alongside a grammar rule can be its _history_. Rule histories may contain
2//! more than semantic actions.
3
4#![deny(unsafe_code)]
5#![warn(missing_docs)]
6
7use std::ops;
8
9use cfg_symbol::Symbol;
10use earley::{History, process_linked};
11
12use self::BinarizedRhsRange::*;
13
14pub mod earley;
15
16/// A history update to an existing history value,
17/// used with grammar transformations.
18#[derive(Clone, Debug)]
19pub enum LinkedHistoryNode {
20    /// Updates history during binarization of a rule.
21    /// Binarization is the process of making a rule with
22    /// any number of RHS symbols become a rule with
23    /// only one or two symbols on the RHS.
24    Binarize {
25        /// Tells us how high we are in a chain of binarized rules.
26        /// For example, when binarizing a rule A ::= B C D E, we get:
27        ///
28        /// - g0 ::= B C -- this is at height 0
29        ///
30        /// - g1 ::= g0 D -- this is at height 1
31        ///
32        /// - A ::= g1 E -- this is at height 2
33        height: u32,
34        /// Original length of the rule before binarization.
35        full_len: usize,
36        /// Whether we are at the highest rule.
37        is_top: bool,
38    },
39    /// Updates history after nulling rule elimination.
40    EliminateNulling {
41        /// The symbol at the first place in the RHS of the binarized rule
42        /// we are de-nulling, or `None` if the rule has zero symbols
43        /// to begin with.
44        rhs0: Option<Symbol>,
45        /// The symbol at the second place in the RHS of the binarized rule
46        /// we are de-nulling, or `None` if the rule has zero or one symbol
47        /// to begin with.
48        rhs1: Option<Symbol>,
49        /// Range of eliminated RHS symbols of the binary rule.
50        which: BinarizedRhsRange,
51    },
52    /// Updates history for rules built with the precedenced rule
53    /// builder.
54    AssignPrecedence {
55        /// Operator precedence, starting with highest
56        /// and loosening with increase.
57        looseness: u32,
58    },
59    /// Updates history of a rule made from a sequence rule.
60    RewriteSequence {
61        /// Whether this is the outermost level of derivation
62        /// among rules built by the sequence rewrite.
63        top: bool,
64        /// The symbol we are repeating.
65        rhs: Symbol,
66        /// Separator.
67        sep: Option<Symbol>,
68    },
69    /// The RHS as computed by the sequence rewrite.
70    /// The rule with this history was made from a sequence
71    /// rule.
72    SequenceRhs {
73        /// The RHS as computed by the sequence rewrite.
74        /// Up to three symbols may appear on the RHS.
75        rhs: [Option<Symbol>; 3],
76    },
77    /// Weight for generation for Probabilistic CFGs.
78    /// 
79    /// We generate by picking one of the alternatives
80    /// at random or from seed.
81    Weight {
82        /// Floating point weight.
83        weight: f64,
84    },
85    // Distances {
86    //     events: Vec<u32>,
87    // },
88}
89
90/// The basic semantics. They may receive further updates.
91#[derive(Clone, Copy, Debug)]
92pub enum RootHistoryNode {
93    /// Empty semantics.
94    NoOp,
95    /// This is a plain rule.
96    Rule {
97        /// Only the LHS is given. The RHS may be updated
98        /// through [`HistoryNodeRhs`].
99        lhs: Symbol,
100    },
101    /// This is a plain rule.
102    Origin {
103        /// Original rule ID is given.
104        origin: usize,
105    },
106}
107
108/// Provides information about the RHS of the rule
109/// we have semantics for.
110pub struct HistoryNodeRhs {
111    /// The history we are updating.
112    pub prev: History,
113    /// The rule RHS.
114    pub rhs: Vec<Symbol>,
115}
116
117/// Updates history during binarization of a rule.
118/// Binarization is the process of making a rule with
119/// any number of RHS symbols become a rule with
120/// only one or two symbols on the RHS.
121#[derive(Clone, Copy)]
122pub struct HistoryNodeBinarize {
123    /// The history we are updating.
124    pub prev: History,
125    /// Tells us how high we are in a chain of binarized rules.
126    /// For example, when binarizing a rule A ::= B C D E, we get:
127    ///
128    /// - g0 ::= B C -- this is at height 0
129    ///
130    /// - g1 ::= g0 D -- this is at height 1
131    ///
132    /// - A ::= g1 E -- this is at height 2
133    pub height: u32,
134    /// Original length of the rule before binarization.
135    pub full_len: usize,
136    /// Whether we are at the highest rule.
137    pub is_top: bool,
138}
139
140///
141#[derive(Clone, Copy)]
142pub struct HistoryNodeWeight {
143    /// The history we are updating.
144    pub prev: History,
145    /// Floating-point weight for generation for PCFGs.
146    pub weight: f64,
147}
148
149/// Updates history after nulling rule elimination.
150#[derive(Clone, Copy)]
151pub struct HistoryNodeEliminateNulling {
152    /// The history we are updating.
153    pub prev: History,
154    /// The symbol at the first place in the RHS of the binarized rule
155    /// we are de-nulling, or `None` if the rule has zero symbols
156    /// to begin with.
157    pub rhs0: Option<Symbol>,
158    /// The symbol at the secong place in the RHS of the binarized rule
159    /// we are de-nulling, or `None` if the rule has zero or one symbol
160    /// to begin with.
161    pub rhs1: Option<Symbol>,
162    /// Range of eliminated RHS symbols of the binary rule.
163    pub which: BinarizedRhsRange,
164}
165
166/// This is built with the precedenced rule builder.
167#[derive(Clone, Copy)]
168pub struct HistoryNodeAssignPrecedence {
169    /// The history we are updating.
170    pub prev: History,
171    /// Operator precedence, starting with highest
172    /// and loosening with increase.
173    pub looseness: u32,
174}
175
176/// This is built with the sequence rewrite.
177#[derive(Clone, Copy)]
178pub struct HistoryNodeRewriteSequence {
179    /// The history we are updating.
180    pub prev: History,
181    /// Whether this is the outermost level of derivation.
182    pub top: bool,
183    /// Symbol we are repating.
184    pub rhs: Symbol,
185    /// Our separator, or `None` for no separation.
186    pub sep: Option<Symbol>,
187}
188
189/// The RHS as computed by the sequence rewrite.
190#[derive(Clone, Copy)]
191pub struct HistoryNodeSequenceRhs {
192    /// The history we are updating.
193    pub prev: History,
194    /// The RHS as computed by the sequence rewrite.
195    /// Up to three symbols may appear on the RHS.
196    pub rhs: [Option<Symbol>; 3],
197}
198
199// impl From<HistoryNodeRhs> for HistoryNode {
200//     fn from(value: HistoryNodeRhs) -> Self {
201//         HistoryNode::Linked {
202//             prev: value.prev,
203//             node: LinkedHistoryNode::Rhs { rhs: value.rhs },
204//         }
205//     }
206// }
207
208impl From<HistoryNodeBinarize> for History {
209    fn from(value: HistoryNodeBinarize) -> Self {
210        process_linked(
211            &LinkedHistoryNode::Binarize {
212                height: value.height,
213                full_len: value.full_len,
214                is_top: value.is_top,
215            },
216            value.prev,
217        )
218    }
219}
220
221impl From<HistoryNodeWeight> for History {
222    fn from(value: HistoryNodeWeight) -> Self {
223        process_linked(
224            &LinkedHistoryNode::Weight {
225                weight: value.weight,
226            },
227            value.prev,
228        )
229    }
230}
231
232impl From<HistoryNodeEliminateNulling> for History {
233    fn from(value: HistoryNodeEliminateNulling) -> Self {
234        process_linked(
235            &LinkedHistoryNode::EliminateNulling {
236                rhs0: value.rhs0,
237                rhs1: value.rhs1,
238                which: value.which,
239            },
240            value.prev,
241        )
242    }
243}
244
245impl From<HistoryNodeAssignPrecedence> for History {
246    fn from(value: HistoryNodeAssignPrecedence) -> Self {
247        process_linked(
248            &LinkedHistoryNode::AssignPrecedence {
249                looseness: value.looseness,
250            },
251            value.prev,
252        )
253    }
254}
255
256impl From<HistoryNodeRewriteSequence> for History {
257    fn from(value: HistoryNodeRewriteSequence) -> Self {
258        process_linked(
259            &LinkedHistoryNode::RewriteSequence {
260                top: value.top,
261                rhs: value.rhs,
262                sep: value.sep,
263            },
264            value.prev,
265        )
266    }
267}
268
269impl From<HistoryNodeSequenceRhs> for History {
270    fn from(value: HistoryNodeSequenceRhs) -> Self {
271        process_linked(
272            &LinkedHistoryNode::SequenceRhs { rhs: value.rhs },
273            value.prev,
274        )
275    }
276}
277
278/// Used to inform history about which symbols on a rule's
279/// Symbol RHS are nullable, and will be eliminated.
280#[derive(Clone, Copy, Eq, PartialEq, Debug)]
281pub enum BinarizedRhsRange {
282    /// The first of two symbols.
283    Left,
284    /// The second of two symbols.
285    Right,
286    /// All 0, 1 or 2 symbols. The rule is nullable.
287    All(usize),
288}
289
290impl BinarizedRhsRange {
291    /// Turns this into a Rust `Range` of dot positions in a rule.
292    pub fn as_range(self) -> ops::Range<usize> {
293        match self {
294            Left => 0..1,
295            Right => 1..2,
296            All(num) => 0..num,
297        }
298    }
299
300    /// Flips the range to cover the rest of the rule RHS.
301    ///
302    /// # Panics
303    ///
304    /// Does not work with `All`.
305    pub fn negate(self) -> Self {
306        match self {
307            Left => Right,
308            Right => Left,
309            All(_) => unreachable!(),
310        }
311    }
312}
cfg_history/lib.rs

cfg_history/
lib.rs
