rusty_alto/algebras/
feature.rs

1//! General-purpose feature structures and their evaluation algebra.
2//!
3//! Values are immutable graphs. Repeated variables in a parsed literal denote
4//! reentrant nodes; unification preserves this sharing. The algebra implements
5//! Alto's `unify`, `proj_*`, and `emb_*` operations, plus a general `remap_*`
6//! operation for selecting several top-level attributes in a single linear
7//! term. Higher-level formalisms compose these primitives without adding
8//! domain-specific attributes or operations to this algebra.
9
10use super::Algebra;
11use crate::{
12    BottomUpTa, FeatureStructureVisualizationCodec, FxHashMap, OutputCodec, Signature, Symbol,
13    VisualRepresentation,
14};
15use std::{
16    collections::{BTreeMap, HashMap},
17    fmt,
18};
19
20/// Binary feature-structure unification operation.
21pub const FS_UNIFY: &str = "unify";
22/// Prefix for unary projection operations such as `proj_root`.
23pub const FS_PROJECT_PREFIX: &str = "proj_";
24/// Prefix for unary embedding operations such as `emb_n1`.
25pub const FS_EMBED_PREFIX: &str = "emb_";
26/// Prefix for unary multi-attribute remapping operations.
27///
28/// A label such as `remap_left=first,right=second` selects `left` and `right`
29/// from its argument and returns them under `first` and `second`.
30pub const FS_REMAP_PREFIX: &str = "remap_";
31
32#[derive(Clone, Debug, PartialEq, Eq, Hash)]
33enum Node {
34    Variable,
35    Atom(String),
36    Map(Vec<(String, usize)>),
37}
38
39/// Immutable canonical feature structure with explicit reentrancies.
40#[derive(Clone, Debug, PartialEq, Eq, Hash)]
41pub struct FeatureStructure {
42    nodes: Vec<Node>,
43}
44
45/// Stable identifier for a node in a [`FeatureStructure`].
46#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
47pub struct FeatureStructureNodeId(usize);
48
49/// Read-only kind of a feature-structure node.
50#[derive(Clone, Copy, Debug, PartialEq, Eq)]
51pub enum FeatureStructureNode<'a> {
52    /// An unconstrained variable.
53    Variable,
54    /// An atomic value.
55    Atom(&'a str),
56    /// An attribute-value map. Use [`FeatureStructure::attributes`] to inspect its entries.
57    Map,
58}
59
60/// One read-only attribute edge in a feature structure.
61#[derive(Clone, Copy, Debug, PartialEq, Eq)]
62pub struct FeatureStructureAttribute<'a> {
63    /// Attribute name.
64    pub name: &'a str,
65    /// Node containing the attribute value.
66    pub value: FeatureStructureNodeId,
67}
68
69impl FeatureStructure {
70    /// Return the root node.
71    pub fn root(&self) -> FeatureStructureNodeId {
72        FeatureStructureNodeId(0)
73    }
74
75    /// Inspect a node without exposing the mutable graph representation.
76    pub fn node(&self, id: FeatureStructureNodeId) -> Option<FeatureStructureNode<'_>> {
77        self.nodes.get(id.0).map(|node| match node {
78            Node::Variable => FeatureStructureNode::Variable,
79            Node::Atom(atom) => FeatureStructureNode::Atom(atom),
80            Node::Map(_) => FeatureStructureNode::Map,
81        })
82    }
83
84    /// Return the ordered attributes of a map node.
85    pub fn attributes(
86        &self,
87        id: FeatureStructureNodeId,
88    ) -> Option<impl ExactSizeIterator<Item = FeatureStructureAttribute<'_>> + '_> {
89        let Node::Map(attributes) = self.nodes.get(id.0)? else {
90            return None;
91        };
92        Some(attributes.iter().map(|(name, value)| FeatureStructureAttribute {
93            name,
94            value: FeatureStructureNodeId(*value),
95        }))
96    }
97
98    /// Construct an empty attribute-value matrix.
99    pub fn empty() -> Self {
100        Self {
101            nodes: vec![Node::Map(Vec::new())],
102        }
103    }
104
105    /// Parse Alto feature-structure syntax.
106    ///
107    /// Attribute-value matrices use `[attribute: value]`; `#name` introduces
108    /// or refers to a reentrant variable.
109    pub fn parse(input: &str) -> Result<Self, FeatureStructureParseError> {
110        Parser::new(input).parse()
111    }
112
113    /// Compute non-destructive unification, or return `None` on a clash.
114    pub fn unify(&self, other: &Self) -> Option<Self> {
115        let mut graph = Graph::default();
116        let left = graph.append(self);
117        let right = graph.append(other);
118        graph.unify(left, right)?;
119        Some(graph.freeze(left))
120    }
121
122    /// Return the value stored under a top-level attribute.
123    pub fn project(&self, attribute: &str) -> Option<Self> {
124        let Node::Map(attributes) = &self.nodes[0] else {
125            return None;
126        };
127        let child = attributes
128            .binary_search_by(|(candidate, _)| candidate.as_str().cmp(attribute))
129            .ok()
130            .map(|index| attributes[index].1)?;
131        Some(self.subgraph(child))
132    }
133
134    /// Wrap this value in a new one-attribute feature structure.
135    pub fn embed(&self, attribute: &str) -> Self {
136        self.with_new_root(vec![(attribute.to_owned(), 1)])
137    }
138
139    /// Select and rename several top-level attributes.
140    ///
141    /// Each pair is `(source, target)`. The operation returns `None` when a
142    /// source attribute is absent or two mappings use the same target.
143    /// Reentrancies among selected values are preserved.
144    pub fn remap(&self, mappings: &[(&str, &str)]) -> Option<Self> {
145        let Node::Map(source_attributes) = &self.nodes[0] else {
146            return None;
147        };
148        let mut selected = Vec::with_capacity(mappings.len());
149        for &(source, target) in mappings {
150            let child = source_attributes
151                .binary_search_by(|(candidate, _)| candidate.as_str().cmp(source))
152                .ok()
153                .map(|index| source_attributes[index].1)?;
154            selected.push((target.to_owned(), child));
155        }
156        selected.sort_by(|left, right| left.0.cmp(&right.0));
157        if selected.windows(2).any(|pair| pair[0].0 == pair[1].0) {
158            return None;
159        }
160
161        fn copy(
162            source: &FeatureStructure,
163            node: usize,
164            remap: &mut HashMap<usize, usize>,
165            target: &mut Vec<Node>,
166        ) -> usize {
167            if let Some(&mapped) = remap.get(&node) {
168                return mapped;
169            }
170            let mapped = target.len();
171            remap.insert(node, mapped);
172            target.push(Node::Variable);
173            target[mapped] = match &source.nodes[node] {
174                Node::Variable => Node::Variable,
175                Node::Atom(atom) => Node::Atom(atom.clone()),
176                Node::Map(attributes) => Node::Map(
177                    attributes
178                        .iter()
179                        .map(|(attribute, child)| {
180                            (attribute.clone(), copy(source, *child, remap, target))
181                        })
182                        .collect(),
183                ),
184            };
185            mapped
186        }
187
188        let mut nodes = vec![Node::Map(Vec::new())];
189        let mut remap = HashMap::new();
190        let attributes = selected
191            .into_iter()
192            .map(|(target, child)| (target, copy(self, child, &mut remap, &mut nodes)))
193            .collect();
194        nodes[0] = Node::Map(attributes);
195        Some(Self { nodes })
196    }
197
198    fn with_new_root(&self, attributes: Vec<(String, usize)>) -> Self {
199        let mut nodes = vec![Node::Map(attributes)];
200        nodes.extend(self.nodes.iter().map(|node| shift(node, 1)));
201        Self { nodes }
202    }
203
204    fn subgraph(&self, root: usize) -> Self {
205        fn copy(
206            source: &FeatureStructure,
207            node: usize,
208            remap: &mut HashMap<usize, usize>,
209            target: &mut Vec<Node>,
210        ) -> usize {
211            if let Some(&mapped) = remap.get(&node) {
212                return mapped;
213            }
214            let mapped = target.len();
215            remap.insert(node, mapped);
216            target.push(Node::Variable);
217            target[mapped] = match &source.nodes[node] {
218                Node::Variable => Node::Variable,
219                Node::Atom(atom) => Node::Atom(atom.clone()),
220                Node::Map(attributes) => Node::Map(
221                    attributes
222                        .iter()
223                        .map(|(attribute, child)| {
224                            (attribute.clone(), copy(source, *child, remap, target))
225                        })
226                        .collect(),
227                ),
228            };
229            mapped
230        }
231        let mut nodes = Vec::new();
232        copy(self, root, &mut HashMap::new(), &mut nodes);
233        Self { nodes }
234    }
235}
236
237fn shift(node: &Node, offset: usize) -> Node {
238    match node {
239        Node::Variable => Node::Variable,
240        Node::Atom(atom) => Node::Atom(atom.clone()),
241        Node::Map(attributes) => Node::Map(
242            attributes
243                .iter()
244                .map(|(attribute, child)| (attribute.clone(), child + offset))
245                .collect(),
246        ),
247    }
248}
249
250impl fmt::Display for FeatureStructure {
251    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
252        fn write_node(
253            value: &FeatureStructure,
254            node: usize,
255            f: &mut fmt::Formatter<'_>,
256        ) -> fmt::Result {
257            match &value.nodes[node] {
258                Node::Variable => f.write_str("[]"),
259                Node::Atom(atom) => f.write_str(atom),
260                Node::Map(attributes) => {
261                    f.write_str("[")?;
262                    for (index, (attribute, child)) in attributes.iter().enumerate() {
263                        if index > 0 {
264                            f.write_str(", ")?;
265                        }
266                        write!(f, "{attribute}: ")?;
267                        write_node(value, *child, f)?;
268                    }
269                    f.write_str("]")
270                }
271            }
272        }
273        write_node(self, 0, f)
274    }
275}
276
277#[derive(Clone, Debug)]
278enum WorkNode {
279    Variable,
280    Atom(String),
281    Map(BTreeMap<String, usize>),
282}
283
284#[derive(Default)]
285struct Graph {
286    nodes: Vec<WorkNode>,
287    parents: Vec<usize>,
288}
289
290impl Graph {
291    fn add(&mut self, node: WorkNode) -> usize {
292        let id = self.nodes.len();
293        self.nodes.push(node);
294        self.parents.push(id);
295        id
296    }
297
298    fn append(&mut self, value: &FeatureStructure) -> usize {
299        let offset = self.nodes.len();
300        for node in &value.nodes {
301            self.add(match node {
302                Node::Variable => WorkNode::Variable,
303                Node::Atom(atom) => WorkNode::Atom(atom.clone()),
304                Node::Map(attributes) => WorkNode::Map(
305                    attributes
306                        .iter()
307                        .map(|(attribute, child)| (attribute.clone(), child + offset))
308                        .collect(),
309                ),
310            });
311        }
312        offset
313    }
314
315    fn find(&mut self, node: usize) -> usize {
316        if self.parents[node] == node {
317            node
318        } else {
319            let root = self.find(self.parents[node]);
320            self.parents[node] = root;
321            root
322        }
323    }
324
325    fn unify(&mut self, left: usize, right: usize) -> Option<usize> {
326        let left = self.find(left);
327        let right = self.find(right);
328        if left == right {
329            return Some(left);
330        }
331        match (self.nodes[left].clone(), self.nodes[right].clone()) {
332            (WorkNode::Variable, _) => {
333                self.parents[left] = right;
334                Some(right)
335            }
336            (_, WorkNode::Variable) => {
337                self.parents[right] = left;
338                Some(left)
339            }
340            (WorkNode::Atom(left_atom), WorkNode::Atom(right_atom)) => {
341                if left_atom != right_atom {
342                    None
343                } else {
344                    self.parents[right] = left;
345                    Some(left)
346                }
347            }
348            (WorkNode::Map(mut left_map), WorkNode::Map(right_map)) => {
349                self.parents[right] = left;
350                for (attribute, right_child) in right_map {
351                    if let Some(&left_child) = left_map.get(&attribute) {
352                        let child = self.unify(left_child, right_child)?;
353                        left_map.insert(attribute, child);
354                    } else {
355                        left_map.insert(attribute, right_child);
356                    }
357                }
358                self.nodes[left] = WorkNode::Map(left_map);
359                Some(left)
360            }
361            _ => None,
362        }
363    }
364
365    fn freeze(mut self, root: usize) -> FeatureStructure {
366        fn copy(
367            graph: &mut Graph,
368            node: usize,
369            remap: &mut HashMap<usize, usize>,
370            target: &mut Vec<Node>,
371        ) -> usize {
372            let node = graph.find(node);
373            if let Some(&mapped) = remap.get(&node) {
374                return mapped;
375            }
376            let mapped = target.len();
377            remap.insert(node, mapped);
378            target.push(Node::Variable);
379            let work = graph.nodes[node].clone();
380            target[mapped] = match work {
381                WorkNode::Variable => Node::Variable,
382                WorkNode::Atom(atom) => Node::Atom(atom),
383                WorkNode::Map(attributes) => Node::Map(
384                    attributes
385                        .into_iter()
386                        .map(|(attribute, child)| (attribute, copy(graph, child, remap, target)))
387                        .collect(),
388                ),
389            };
390            mapped
391        }
392        let mut nodes = Vec::new();
393        copy(&mut self, root, &mut HashMap::new(), &mut nodes);
394        FeatureStructure { nodes }
395    }
396}
397
398#[derive(Clone, Debug)]
399enum Operation {
400    Unify,
401    Project(String),
402    Embed(String),
403    Remap(Vec<(String, String)>),
404    Literal(FeatureStructure),
405    InvalidLiteral,
406}
407
408/// Feature-structure algebra compatible with Alto's general operations.
409///
410/// Literal operation symbols parse to [`FeatureStructure`] values. Malformed
411/// literals and failed operations make evaluation undefined. The `remap_*`
412/// extension keeps multi-attribute selection linear, so it can be used in
413/// inverse homomorphisms without repeating a source variable.
414#[derive(Clone, Debug)]
415pub struct FeatureStructureAlgebra {
416    signature: Signature,
417    operations: FxHashMap<Symbol, Operation>,
418    display_codec: FeatureStructureVisualizationCodec,
419}
420
421impl FeatureStructureAlgebra {
422    /// Build an algebra by classifying every operation in `signature`.
423    pub fn with_signature(signature: Signature) -> Self {
424        let mut operations = FxHashMap::default();
425        for raw in 0..signature.len() {
426            let symbol = Symbol(raw as u32);
427            let label = signature.resolve(symbol);
428            let operation = if label == FS_UNIFY {
429                Operation::Unify
430            } else if let Some(attribute) = label.strip_prefix(FS_PROJECT_PREFIX) {
431                Operation::Project(attribute.to_owned())
432            } else if let Some(specification) = label.strip_prefix(FS_REMAP_PREFIX) {
433                parse_remappings(specification)
434                    .map(Operation::Remap)
435                    .unwrap_or(Operation::InvalidLiteral)
436            } else if let Some(attribute) = label.strip_prefix(FS_EMBED_PREFIX) {
437                Operation::Embed(attribute.to_owned())
438            } else {
439                match FeatureStructure::parse(label) {
440                    Ok(value) => Operation::Literal(value),
441                    Err(_) => Operation::InvalidLiteral,
442                }
443            };
444            operations.insert(symbol, operation);
445        }
446        Self {
447            signature,
448            operations,
449            display_codec: FeatureStructureVisualizationCodec,
450        }
451    }
452
453    /// Return an automaton accepting successfully evaluated feature terms.
454    pub fn filter(&self) -> FeatureStructureFilter<'_> {
455        FeatureStructureFilter { algebra: self }
456    }
457}
458
459impl Algebra for FeatureStructureAlgebra {
460    type InternalValue = FeatureStructure;
461    type Value = FeatureStructure;
462    type ParseError = FeatureStructureParseError;
463
464    fn signature(&self) -> &Signature {
465        &self.signature
466    }
467
468    fn evaluate(
469        &self,
470        symbol: Symbol,
471        children: &[Self::InternalValue],
472    ) -> Option<Self::InternalValue> {
473        match (self.operations.get(&symbol)?, children) {
474            (Operation::Unify, [left, right]) => left.unify(right),
475            (Operation::Project(attribute), [value]) => value.project(attribute),
476            (Operation::Embed(attribute), [value]) => Some(value.embed(attribute)),
477            (Operation::Remap(mappings), [value]) => {
478                let mappings = mappings
479                    .iter()
480                    .map(|(source, target)| (source.as_str(), target.as_str()))
481                    .collect::<Vec<_>>();
482                value.remap(&mappings)
483            }
484            (Operation::Literal(value), []) => Some(value.clone()),
485            (Operation::InvalidLiteral, _) => None,
486            _ => None,
487        }
488    }
489
490    fn parse_object(&mut self, input: &str) -> Result<Self::InternalValue, Self::ParseError> {
491        FeatureStructure::parse(input)
492    }
493
494    fn to_external(&self, value: &Self::InternalValue) -> Self::Value {
495        value.clone()
496    }
497
498    fn visualize(&self, value: &Self::Value) -> VisualRepresentation {
499        self.display_codec.encode(value)
500    }
501}
502
503fn parse_remappings(specification: &str) -> Option<Vec<(String, String)>> {
504    if specification.is_empty() {
505        return None;
506    }
507    specification
508        .split(',')
509        .map(|mapping| {
510            let (source, target) = mapping.split_once('=')?;
511            if source.is_empty() || target.is_empty() || target.contains('=') {
512                None
513            } else {
514                Some((source.to_owned(), target.to_owned()))
515            }
516        })
517        .collect()
518}
519
520/// Bottom-up evaluator that rejects failed feature-structure operations.
521pub struct FeatureStructureFilter<'a> {
522    algebra: &'a FeatureStructureAlgebra,
523}
524
525impl BottomUpTa for FeatureStructureFilter<'_> {
526    type State = FeatureStructure;
527
528    fn step(&self, symbol: Symbol, children: &[Self::State], out: &mut dyn FnMut(Self::State)) {
529        if let Some(value) = self.algebra.evaluate(symbol, children) {
530            out(value);
531        }
532    }
533
534    fn is_accepting(&self, _state: &Self::State) -> bool {
535        true
536    }
537}
538
539#[derive(Clone, Debug, PartialEq, Eq)]
540/// Error produced while parsing a feature-structure literal.
541pub struct FeatureStructureParseError {
542    offset: usize,
543    message: String,
544}
545
546impl fmt::Display for FeatureStructureParseError {
547    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
548        write!(
549            f,
550            "feature-structure syntax error at byte {}: {}",
551            self.offset, self.message
552        )
553    }
554}
555
556impl std::error::Error for FeatureStructureParseError {}
557
558struct Parser<'a> {
559    input: &'a str,
560    position: usize,
561    graph: Graph,
562    indices: HashMap<String, usize>,
563}
564
565impl<'a> Parser<'a> {
566    fn new(input: &'a str) -> Self {
567        Self {
568            input,
569            position: 0,
570            graph: Graph::default(),
571            indices: HashMap::new(),
572        }
573    }
574
575    fn parse(mut self) -> Result<FeatureStructure, FeatureStructureParseError> {
576        let root = self.value()?;
577        self.ws();
578        if self.position != self.input.len() {
579            return self.error("trailing input");
580        }
581        Ok(self.graph.freeze(root))
582    }
583
584    fn value(&mut self) -> Result<usize, FeatureStructureParseError> {
585        self.ws();
586        if self.consume('#') {
587            let name = self.word()?;
588            if let Some(&existing) = self.indices.get(&name) {
589                return Ok(existing);
590            }
591            let placeholder = self.graph.add(WorkNode::Variable);
592            self.indices.insert(name, placeholder);
593            self.ws();
594            if self.peek().is_some_and(|next| !matches!(next, ']' | ',')) {
595                let value = self.value()?;
596                self.graph
597                    .unify(placeholder, value)
598                    .ok_or_else(|| self.make_error("incompatible indexed values"))?;
599            }
600            return Ok(placeholder);
601        }
602        if self.consume('[') {
603            let mut attributes = BTreeMap::new();
604            self.ws();
605            if self.consume(']') {
606                return Ok(self.graph.add(WorkNode::Map(attributes)));
607            }
608            loop {
609                let attribute = self.word()?;
610                self.ws();
611                if !self.consume(':') {
612                    return self.error("expected ':'");
613                }
614                let child = self.value()?;
615                attributes.insert(attribute, child);
616                self.ws();
617                if self.consume(']') {
618                    break;
619                }
620                if !self.consume(',') {
621                    return self.error("expected ',' or ']'");
622                }
623            }
624            return Ok(self.graph.add(WorkNode::Map(attributes)));
625        }
626        let atom = self.word()?;
627        Ok(self.graph.add(WorkNode::Atom(atom)))
628    }
629
630    fn word(&mut self) -> Result<String, FeatureStructureParseError> {
631        self.ws();
632        let start = self.position;
633        while let Some(ch) = self.peek() {
634            if ch.is_whitespace() || matches!(ch, '[' | ']' | ':' | ',') {
635                break;
636            }
637            self.position += ch.len_utf8();
638        }
639        if start == self.position {
640            self.error("expected value")
641        } else {
642            Ok(self.input[start..self.position].to_owned())
643        }
644    }
645
646    fn ws(&mut self) {
647        while self.peek().is_some_and(char::is_whitespace) {
648            self.position += self.peek().unwrap().len_utf8();
649        }
650    }
651
652    fn peek(&self) -> Option<char> {
653        self.input[self.position..].chars().next()
654    }
655
656    fn consume(&mut self, expected: char) -> bool {
657        if self.peek() == Some(expected) {
658            self.position += expected.len_utf8();
659            true
660        } else {
661            false
662        }
663    }
664
665    fn make_error(&self, message: &str) -> FeatureStructureParseError {
666        FeatureStructureParseError {
667            offset: self.position,
668            message: message.to_owned(),
669        }
670    }
671
672    fn error<T>(&self, message: &str) -> Result<T, FeatureStructureParseError> {
673        Err(self.make_error(message))
674    }
675}
676
677#[cfg(test)]
678mod tests {
679    use super::*;
680
681    // Ported from Alto's FeatureStructureAlgebraTest.testProj.
682    #[test]
683    fn alto_projection_test() {
684        let source = FeatureStructure::parse("[root: [num: sg]]").unwrap();
685        assert_eq!(
686            source.project("root").unwrap(),
687            FeatureStructure::parse("[num: sg]").unwrap()
688        );
689    }
690
691    // Ported from Alto's FeatureStructureTest equality cases.
692    #[test]
693    fn alto_equality_is_order_independent_and_reentrancy_sensitive() {
694        assert_eq!(
695            FeatureStructure::parse("[num: sg, gen: masc]").unwrap(),
696            FeatureStructure::parse("[gen: masc, num: sg]").unwrap()
697        );
698        assert_ne!(
699            FeatureStructure::parse("[num: #1 sg, gen: #1]").unwrap(),
700            FeatureStructure::parse("[num: sg, gen: sg]").unwrap()
701        );
702        assert_ne!(
703            FeatureStructure::parse("[num: [foo: sg], gen: masc]").unwrap(),
704            FeatureStructure::parse("[gen: masc, num: sg]").unwrap()
705        );
706    }
707
708    #[test]
709    fn unification_detects_clashes() {
710        let nom = FeatureStructure::parse("[case: nom]").unwrap();
711        let acc = FeatureStructure::parse("[case: acc]").unwrap();
712        assert!(nom.unify(&acc).is_none());
713    }
714
715    #[test]
716    fn projection_embedding_and_unification_are_attribute_agnostic() {
717        let source = FeatureStructure::parse("[left: [gen: #g], right: [gen: masc]]").unwrap();
718        let left = source.project("left").unwrap().embed("target_a");
719        let right = source.project("right").unwrap().embed("target_b");
720        let embedded = left.unify(&right).unwrap();
721        let core = FeatureStructure::parse("[target_a: [gen: #g], target_b: [gen: masc]]").unwrap();
722        assert!(core.unify(&embedded).is_some());
723    }
724
725    #[test]
726    fn remapping_selects_multiple_attributes_and_preserves_reentrancy() {
727        let source = FeatureStructure::parse("[left: #x [gen: masc], right: #x]").unwrap();
728        let remapped = source
729            .remap(&[("left", "first"), ("right", "second")])
730            .unwrap();
731        assert_eq!(
732            remapped,
733            FeatureStructure::parse("[first: #x [gen: masc], second: #x]").unwrap()
734        );
735        assert!(source.remap(&[("missing", "target")]).is_none());
736        assert!(
737            source
738                .remap(&[("left", "same"), ("right", "same")])
739                .is_none()
740        );
741    }
742
743    #[test]
744    fn public_graph_access_preserves_nesting_and_reentrancy() {
745        let value =
746            FeatureStructure::parse("[left: #x [case: nom], right: #x, open: #y]").unwrap();
747        let root = value.root();
748        assert_eq!(value.node(root), Some(FeatureStructureNode::Map));
749        let attributes = value.attributes(root).unwrap().collect::<Vec<_>>();
750        assert_eq!(
751            attributes.iter().map(|attribute| attribute.name).collect::<Vec<_>>(),
752            vec!["left", "open", "right"]
753        );
754        assert_eq!(attributes[0].value, attributes[2].value);
755        assert_eq!(
756            value.node(attributes[1].value),
757            Some(FeatureStructureNode::Variable)
758        );
759        let nested = value
760            .attributes(attributes[0].value)
761            .unwrap()
762            .collect::<Vec<_>>();
763        assert_eq!(nested[0].name, "case");
764        assert_eq!(
765            value.node(nested[0].value),
766            Some(FeatureStructureNode::Atom("nom"))
767        );
768    }
769}
rusty_alto/algebras/feature.rs

rusty_alto/algebras/
feature.rs
