treebender/
featurestructure.rs

1use std::cell::{Ref, RefCell, RefMut};
2use std::collections::HashMap;
3use std::fmt;
4use std::hash::{Hash, Hasher};
5use std::rc::Rc;
6
7use crate::utils::Err;
8
9/// Unpacked representation of a feature, that NodeRef::new_from_paths can turn into a Node
10#[derive(Debug)]
11pub struct Feature {
12  /// Dotted path where each segment will be a node: "a.b.c" -> [a: [b: [c: ...]]]
13  pub path: String,
14  /// Unique string that will link features into a reentrant node, or None
15  pub tag: Option<String>,
16  /// What will end up at `path`. Will be unified with any other feature values with the same tag.
17  pub value: NodeRef,
18}
19
20/// A raw node. Shouldn't be used, should always be wrapped in a NodeRef.
21#[derive(Debug)]
22enum Node {
23  /// Top can unify with anything
24  Top,
25  /// A string-valued feature, such as "nom" in [case: nom]. Unifies with eq. Str nodes
26  Str(String),
27  /// An arc-containing node with arcs to other NodeRefs
28  Edged(HashMap<String, NodeRef>),
29  /// A node that has been forwarded to another node through unification.
30  /// Before using a node, it should be dereferenced with Node::dereference to resolve its forward
31  Forwarded(NodeRef),
32}
33
34/// An interior-ly mutable ref to a Node.
35#[derive(Debug)]
36pub struct NodeRef(Rc<RefCell<Node>>);
37
38impl NodeRef {
39  pub fn new_top() -> Self {
40    Node::Top.into()
41  }
42
43  pub fn new_str(s: String) -> Self {
44    Node::new_str(s).into()
45  }
46
47  /// Creates a NodeRef from a list of (name, noderef) features. Names CANNOT be dotted!
48  pub fn new_with_edges<I>(edges: I) -> Result<Self, Err>
49  where
50    I: IntoIterator<Item = (String, NodeRef)>,
51  {
52    let mut n = Node::new_edged();
53    for (label, target) in edges {
54      assert!(
55        !label.contains('.'),
56        "new_with_edges cannot take dotted paths!"
57      );
58
59      n.push_edge(label, target)?;
60    }
61    Ok(n.into())
62  }
63
64  // List of (name, value, tag) triples
65  pub fn new_from_paths<I>(paths: I) -> Result<NodeRef, Err>
66  where
67    I: IntoIterator<Item = Feature>,
68  {
69    let this: NodeRef = Node::new_edged().into();
70
71    let mut tags: HashMap<String, NodeRef> = HashMap::new();
72    for Feature { value, tag, path } in paths {
73      if let Some(tag) = tag {
74        if tags.contains_key(&tag) {
75          let tagged = tags.get(&tag).unwrap();
76          NodeRef::unify(value.clone(), tagged.clone())?;
77        } else {
78          tags.insert(tag.to_string(), value.clone());
79        }
80      }
81
82      let mut current = this.clone();
83      let mut parts = path.split('.').peekable();
84      loop {
85        let next = parts.next().expect("shouldn't be empty b/c path.len() > 0");
86        let is_last = parts.peek().is_none();
87
88        if is_last {
89          current
90            .borrow_mut()
91            .push_edge(next.to_string(), value.clone())?;
92          break;
93        } else {
94          let new: NodeRef = Node::new_edged().into();
95          current
96            .borrow_mut()
97            .push_edge(next.to_string(), new.clone())?;
98          current = new;
99        }
100      }
101    }
102
103    Ok(this)
104  }
105
106  pub fn deep_clone(&self) -> NodeRef {
107    let mut map = HashMap::new();
108    self._deep_clone(&mut map);
109    map.get(self).unwrap().clone()
110  }
111
112  pub fn dereference(self: NodeRef) -> NodeRef {
113    if let Node::Forwarded(r) = &*self.borrow() {
114      return Self::dereference(r.clone());
115    }
116    self
117  }
118
119  /// Unify two feature structures. Both will be mutated. Use deep_clone() if one needs to be preserved.
120  pub fn unify(n1: NodeRef, n2: NodeRef) -> Result<(), Err> {
121    let n1 = n1.dereference();
122    let n2 = n2.dereference();
123
124    // quick check reference equality if the og nodes were forwarded to each other
125    if n1 == n2 {
126      return Ok(());
127    }
128
129    // if either is top forward to the other one w/o checking
130    if n1.borrow().is_top() {
131      n1.replace(Node::Forwarded(n2));
132      return Ok(());
133    } else if n2.borrow().is_top() {
134      n2.replace(Node::Forwarded(n1));
135      return Ok(());
136    }
137
138    // try to unify string values
139    if n1.borrow().is_str() && n2.borrow().is_str() {
140      let strs_equal = {
141        let n1 = n1.borrow();
142        let n2 = n2.borrow();
143        n1.str().unwrap() == n2.str().unwrap()
144      };
145      if strs_equal {
146        n1.replace(Node::Forwarded(n2));
147        return Ok(());
148      } else {
149        return Err(
150          format!(
151            "unification failure: {} & {}",
152            n1.borrow().str().unwrap(),
153            n2.borrow().str().unwrap()
154          )
155          .into(),
156        );
157      }
158    }
159
160    if n1.borrow().is_edged() && n2.borrow().is_edged() {
161      let n1 = n1.replace(Node::Forwarded(n2.clone()));
162      let n2 = &mut *n2.borrow_mut();
163
164      let n1arcs = n1.edged().unwrap();
165      let n2arcs = n2.edged_mut().unwrap();
166
167      for (label, value) in n1arcs.iter() {
168        if n2arcs.contains_key(label) {
169          // shared arc
170          let other = n2arcs.get(label).unwrap();
171          Self::unify(value.clone(), other.clone())?;
172        } else {
173          // complement arc
174          n2arcs.insert(label.clone(), value.clone());
175        }
176      }
177
178      return Ok(());
179    }
180
181    Err(format!("unification failure: {:#?} & {:#?}", n1, n2).into())
182  }
183}
184
185impl NodeRef {
186  fn new(n: Node) -> Self {
187    Self(Rc::new(RefCell::new(n)))
188  }
189
190  fn borrow(&self) -> Ref<Node> {
191    self.0.borrow()
192  }
193
194  fn borrow_mut(&self) -> RefMut<Node> {
195    self.0.borrow_mut()
196  }
197
198  fn replace(&self, n: Node) -> Node {
199    self.0.replace(n)
200  }
201
202  fn _deep_clone(&self, seen: &mut HashMap<NodeRef, NodeRef>) -> NodeRef {
203    if seen.contains_key(self) {
204      return seen.get(self).unwrap().clone();
205    }
206
207    let n = self.borrow();
208    let cloned = match &*n {
209      Node::Forwarded(n1) => {
210        let n1 = n1._deep_clone(seen);
211        Self::new(Node::Forwarded(n1))
212      }
213      Node::Top => Self::new_top(),
214      Node::Str(s) => Self::new_str(s.to_string()),
215      Node::Edged(edges) => Self::new(Node::Edged(
216        edges
217          .iter()
218          .map(|(k, v)| (k.clone(), v._deep_clone(seen)))
219          .collect(),
220      )),
221    };
222    seen.insert(self.clone(), cloned.clone());
223    cloned
224  }
225
226  fn insert_into_hashmap(&self, prefix: &str, map: &mut HashMap<String, String>) {
227    let n = self.borrow();
228    match &*n {
229      Node::Forwarded(n1) => n1.insert_into_hashmap(prefix, map),
230      Node::Top => {
231        map.insert(prefix.to_string(), "**top**".to_string());
232      }
233      Node::Str(s) => {
234        map.insert(prefix.to_string(), s.clone());
235      }
236      Node::Edged(edges) => {
237        for (k, v) in edges.iter() {
238          let new_prefix = if prefix.len() == 0 {
239            k.to_string()
240          } else {
241            let mut new_prefix = String::with_capacity(prefix.len() + 1 + k.len());
242            new_prefix.push_str(prefix);
243            new_prefix.push('.');
244            new_prefix.push_str(k);
245            new_prefix
246          };
247
248          v.insert_into_hashmap(&new_prefix, map);
249        }
250      }
251    }
252  }
253}
254
255impl From<NodeRef> for HashMap<String, String> {
256  fn from(nr: NodeRef) -> Self {
257    let mut map = HashMap::new();
258    nr.insert_into_hashmap("", &mut map);
259    return map;
260  }
261}
262
263impl Clone for NodeRef {
264  /// Clones the ***rc*** of this NodeRef. Use deep_clone to clone the actual feature structure.
265  fn clone(&self) -> Self {
266    Self(self.0.clone())
267  }
268}
269
270impl PartialEq for NodeRef {
271  /// Compares NodeRefs via pointer equality. Does not dereference forwarding chains.
272  fn eq(&self, other: &Self) -> bool {
273    Rc::ptr_eq(&self.0, &other.0)
274  }
275}
276
277impl Eq for NodeRef {}
278
279impl Hash for NodeRef {
280  /// Hashes NodeRefs via pointer equality. Does not dereference forwarding chains.
281  fn hash<H: Hasher>(&self, hasher: &mut H) {
282    self.0.as_ptr().hash(hasher)
283  }
284}
285
286impl From<Node> for NodeRef {
287  fn from(node: Node) -> Self {
288    Self::new(node)
289  }
290}
291
292impl Node {
293  fn new_str(s: String) -> Self {
294    Self::Str(s)
295  }
296
297  fn new_edged() -> Self {
298    Self::Edged(HashMap::new())
299  }
300
301  fn is_top(&self) -> bool {
302    match self {
303      Self::Top => true,
304      _ => false,
305    }
306  }
307
308  fn str(&self) -> Option<&str> {
309    match self {
310      Self::Str(s) => Some(s),
311      _ => None,
312    }
313  }
314
315  fn is_str(&self) -> bool {
316    self.str().is_some()
317  }
318
319  fn edged(&self) -> Option<&HashMap<String, NodeRef>> {
320    match self {
321      Self::Edged(v) => Some(v),
322      _ => None,
323    }
324  }
325
326  fn edged_mut(&mut self) -> Option<&mut HashMap<String, NodeRef>> {
327    match self {
328      Self::Edged(v) => Some(v),
329      _ => None,
330    }
331  }
332
333  fn is_edged(&self) -> bool {
334    self.edged().is_some()
335  }
336
337  #[allow(clippy::map_entry)]
338  fn push_edge(&mut self, label: String, target: NodeRef) -> Result<(), Err> {
339    if self.is_top() {
340      *self = Self::new_edged();
341    }
342
343    if let Some(arcs) = self.edged_mut() {
344      if arcs.contains_key(&label) {
345        let existing = arcs[&label].clone();
346        NodeRef::unify(existing, target)
347      } else {
348        arcs.insert(label, target);
349        Ok(())
350      }
351    } else {
352      Err(format!("unification failure: {}", label).into())
353    }
354  }
355}
356
357// for fmt::Display impl
358fn count_in_pointers(nref: NodeRef, seen: &mut HashMap<NodeRef, usize>) {
359  let nref = nref.dereference();
360  if seen.contains_key(&nref) {
361    seen.entry(nref).and_modify(|cnt| *cnt += 1);
362  } else {
363    seen.insert(nref.clone(), 1);
364    if let Some(arcs) = nref.borrow().edged() {
365      for value in arcs.values() {
366        count_in_pointers(value.clone(), seen);
367      }
368    }
369  }
370}
371
372// for fmt::Display impl
373fn format_noderef(
374  self_: NodeRef,
375  counts: &HashMap<NodeRef, usize>,
376  has_printed: &mut HashMap<NodeRef, usize>,
377  indent: usize,
378  f: &mut fmt::Formatter<'_>,
379) -> fmt::Result {
380  let self_ = self_.dereference();
381
382  if counts[&self_] > 1 && has_printed.contains_key(&self_) {
383    return write!(f, "#{}", has_printed[&self_]);
384  }
385
386  if counts[&self_] > 1 {
387    let id = has_printed.len();
388    has_printed.insert(self_.clone(), id);
389    write!(f, "#{} ", id)?;
390  }
391
392  let r = &*self_.borrow();
393  match r {
394    Node::Top => write!(f, "**top**"),
395    Node::Str(s) => write!(f, "{}", s),
396    Node::Edged(arcs) => {
397      if arcs.is_empty() {
398        write!(f, "[]")
399      } else if arcs.len() == 1 {
400        let (label, value) = arcs.iter().next().unwrap();
401        write!(f, "[ {}: ", label)?;
402        format_noderef(value.clone(), counts, has_printed, 0, f)?;
403        write!(f, " ]")
404      } else {
405        writeln!(f, "[")?;
406        for (label, value) in arcs.iter() {
407          write!(f, "{:indent$}{}: ", "", label, indent = indent + 2)?;
408          format_noderef(value.clone(), counts, has_printed, indent + 2, f)?;
409          writeln!(f)?;
410        }
411        write!(f, "{:indent$}]", "", indent = indent)
412      }
413    }
414    Node::Forwarded(_) => panic!("unexpected forward"),
415  }
416}
417
418impl fmt::Display for NodeRef {
419  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
420    let mut counts = HashMap::new();
421    count_in_pointers(self.clone(), &mut counts);
422    let mut has_printed = HashMap::new();
423    format_noderef(self.clone(), &counts, &mut has_printed, 0, f)
424  }
425}
426
427#[cfg(test)]
428mod tests {
429  use super::*;
430
431  fn hashmap_is(a: HashMap<String, String>, gold: &[(&str, &str)]) -> bool {
432    let gold = gold
433      .iter()
434      .map(|(k, v)| (k.to_string(), v.to_string()))
435      .collect::<HashMap<_, _>>();
436
437    let mut same = true;
438
439    // additions
440    for (k, v) in a.iter() {
441      if gold.get(k).is_none() {
442        same = false;
443        eprintln!("+ Unexpected key {}: {}", k, v);
444      }
445    }
446
447    // different
448    for (k, v) in a.iter() {
449      if let Some(gv) = gold.get(k) {
450        if gv != v {
451          same = false;
452          eprintln!("~ Different key {}: given {} != gold {}", k, v, gv);
453        }
454      }
455    }
456
457    // missing
458    for (k, v) in gold.iter() {
459      if a.get(k).is_none() {
460        same = false;
461        eprintln!("- Missing key {}: {}", k, v);
462      }
463    }
464
465    same
466  }
467
468  #[test]
469  fn test_construct_fs() {
470    let root = NodeRef::new_from_paths(vec![
471      Feature {
472        path: "a.b".to_string(),
473        tag: Some("1".to_string()),
474        value: NodeRef::new_top(),
475      },
476      Feature {
477        path: "a.b.c".to_string(),
478        tag: None,
479        value: NodeRef::new_str("foo".to_string()),
480      },
481      Feature {
482        path: "a.b.d".to_string(),
483        tag: None,
484        value: NodeRef::new_str("bar".to_string()),
485      },
486      Feature {
487        path: "e".to_string(),
488        tag: Some("1".to_string()),
489        value: NodeRef::new_top(),
490      },
491    ])
492    .unwrap();
493
494    println!("{}", root);
495  }
496
497  #[test]
498  fn test_unify_tags() {
499    let fs1 = NodeRef::new_from_paths(vec![
500      Feature {
501        path: "a.b".to_string(),
502        tag: Some("1".to_string()),
503        value: NodeRef::new_top(),
504      },
505      Feature {
506        path: "c".to_string(),
507        tag: Some("1".to_string()),
508        value: NodeRef::new_top(),
509      },
510    ])
511    .unwrap();
512
513    let fs2 = NodeRef::new_from_paths(vec![Feature {
514      path: "c".to_string(),
515      tag: None,
516      value: NodeRef::new_str("foo".to_string()),
517    }])
518    .unwrap();
519
520    assert!(hashmap_is(
521      HashMap::from(fs1.clone()),
522      &[("a.b", "**top**"), ("c", "**top**")]
523    ));
524
525    assert!(hashmap_is(HashMap::from(fs2.clone()), &[("c", "foo")]));
526
527    NodeRef::unify(fs1.clone(), fs2.clone()).unwrap();
528
529    assert!(hashmap_is(
530      HashMap::from(fs1.clone()),
531      &[("a.b", "foo"), ("c", "foo")]
532    ));
533
534    assert!(hashmap_is(
535      HashMap::from(fs2.clone()),
536      &[("a.b", "foo"), ("c", "foo")]
537    ));
538  }
539}
treebender/featurestructure.rs

treebender/
featurestructure.rs
