bend/fun/transform/
expand_generated.rs

1use std::collections::{BTreeSet, HashMap, HashSet};
2
3use crate::{
4  fun::{Book, Name, Term},
5  maybe_grow,
6};
7
8/// Dereferences any non recursive generated definitions in the term.
9/// Used after readback.
10impl Term {
11  pub fn expand_generated(&mut self, book: &Book, recursive_defs: &RecursiveDefs) {
12    maybe_grow(|| {
13      if let Term::Ref { nam } = &*self {
14        if nam.is_generated() && !recursive_defs.contains(nam) {
15          *self = book.defs.get(nam).unwrap().rule().body.clone();
16        }
17      }
18
19      for child in self.children_mut() {
20        child.expand_generated(book, recursive_defs);
21      }
22    })
23  }
24}
25
26type DepGraph = HashMap<Name, HashSet<Name>>;
27type Cycles = Vec<Vec<Name>>;
28type RecursiveDefs = BTreeSet<Name>;
29
30impl Book {
31  pub fn recursive_defs(&self) -> RecursiveDefs {
32    let mut cycle_map = BTreeSet::new();
33    let deps = book_def_deps(self);
34    let cycles = cycles(&deps);
35
36    for cycle in cycles {
37      for name in cycle {
38        cycle_map.insert(name);
39      }
40    }
41
42    cycle_map
43  }
44}
45
46/// Find all cycles in the dependency graph.
47fn cycles(deps: &DepGraph) -> Cycles {
48  let mut cycles = vec![];
49  let mut visited = HashSet::new();
50  // let mut stack = vec![];
51  for nam in deps.keys() {
52    if !visited.contains(nam) {
53      find_cycles(deps, nam, &mut visited, &mut cycles);
54    }
55  }
56  cycles
57}
58
59fn find_cycles(deps: &DepGraph, nam: &Name, visited: &mut HashSet<Name>, cycles: &mut Cycles) {
60  let mut stack = vec![(nam.clone(), vec![])];
61  while let Some((current, path)) = stack.pop() {
62    if visited.contains(&current) {
63      // Check if the current ref is already in the stack, which indicates a cycle.
64      if let Some(cycle_start) = path.iter().position(|n| n == &current) {
65        // If found, add the cycle to the cycles vector.
66        cycles.push(path[cycle_start..].to_vec());
67      }
68      continue;
69    }
70
71    // If the ref has not been visited yet, mark it as visited.
72    visited.insert(current.clone());
73    // Add the current ref to the stack to keep track of the path.
74    let mut new_path = path.clone();
75    new_path.push(current.clone());
76
77    // Search for cycles from each dependency.
78    if let Some(deps) = deps.get(&current) {
79      for dep in deps {
80        stack.push((dep.clone(), new_path.clone()));
81      }
82    }
83  }
84}
85
86fn book_def_deps(book: &Book) -> DepGraph {
87  book.defs.iter().map(|(nam, def)| (nam.clone(), def_deps(def))).collect()
88}
89
90fn def_deps(def: &crate::fun::Definition) -> HashSet<Name> {
91  fn collect_refs(term: &Term, set: &mut HashSet<Name>) {
92    if let Term::Ref { nam } = term {
93      set.insert(nam.clone());
94    }
95    for children in term.children() {
96      collect_refs(children, set);
97    }
98  }
99
100  let mut set = HashSet::new();
101  let term = &def.rule().body;
102
103  collect_refs(term, &mut set);
104
105  set
106}
bend/fun/transform/expand_generated.rs

bend/fun/transform/
expand_generated.rs
