bend/hvm/
mutual_recursion.rs

1use super::tree_children;
2use crate::{
3  diagnostics::{Diagnostics, WarningType, ERR_INDENT_SIZE},
4  fun::transform::definition_merge::MERGE_SEPARATOR,
5  maybe_grow,
6};
7use hvm::ast::{Book, Tree};
8use indexmap::{IndexMap, IndexSet};
9use std::fmt::Debug;
10
11type Ref = String;
12type Stack<T> = Vec<T>;
13type RefSet = IndexSet<Ref>;
14
15#[derive(Default)]
16pub struct Graph(IndexMap<Ref, RefSet>);
17
18pub fn check_cycles(book: &Book, diagnostics: &mut Diagnostics) -> Result<(), Diagnostics> {
19  let graph = Graph::from(book);
20  let cycles = graph.cycles();
21
22  if !cycles.is_empty() {
23    let msg = format!(include_str!("mutual_recursion.message"), cycles = show_cycles(cycles));
24    diagnostics.add_book_warning(msg.as_str(), WarningType::RecursionCycle);
25  }
26
27  diagnostics.fatal(())
28}
29fn show_cycles(mut cycles: Vec<Vec<Ref>>) -> String {
30  let tail = if cycles.len() > 5 {
31    format!("\n{:ERR_INDENT_SIZE$}and {} other cycles...", "", cycles.len() - 5)
32  } else {
33    String::new()
34  };
35
36  cycles = cycles.into_iter().flat_map(combinations_from_merges).collect::<Vec<_>>();
37
38  let mut cycles = cycles
39    .iter()
40    .take(5)
41    .map(|cycle| {
42      let cycle_str = cycle
43        .iter()
44        .filter(|nam| !nam.contains("__C"))
45        .chain(cycle.first())
46        .cloned()
47        .collect::<Vec<_>>()
48        .join(" -> ");
49      format!("{:ERR_INDENT_SIZE$}* {}", "", cycle_str)
50    })
51    .collect::<Vec<String>>()
52    .join("\n");
53
54  cycles.push_str(&tail);
55
56  cycles
57}
58
59impl Graph {
60  pub fn cycles(&self) -> Vec<Vec<Ref>> {
61    let mut cycles = Vec::new();
62    let mut stack = Stack::new();
63    let mut visited = RefSet::new();
64
65    for r#ref in self.0.keys() {
66      if !visited.contains(r#ref) {
67        self.find_cycles(r#ref, &mut visited, &mut stack, &mut cycles);
68      }
69    }
70
71    cycles
72  }
73
74  fn find_cycles(
75    &self,
76    r#ref: &Ref,
77    visited: &mut RefSet,
78    stack: &mut Stack<Ref>,
79    cycles: &mut Vec<Vec<Ref>>,
80  ) {
81    // Check if the current ref is already in the stack, which indicates a cycle.
82    if let Some(cycle_start) = stack.iter().position(|n| n == r#ref) {
83      // If found, add the cycle to the cycles vector.
84      cycles.push(stack[cycle_start..].to_vec());
85      return;
86    }
87
88    // If the ref has not been visited yet, mark it as visited.
89    if visited.insert(r#ref.clone()) {
90      // Add the current ref to the stack to keep track of the path.
91      stack.push(r#ref.clone());
92
93      // Get the dependencies of the current ref.
94      if let Some(dependencies) = self.get(r#ref) {
95        // Search for cycles from each dependency.
96        for dep in dependencies {
97          self.find_cycles(dep, visited, stack, cycles);
98        }
99      }
100
101      stack.pop();
102    }
103  }
104}
105
106/// Collect active refs from the tree.
107fn collect_refs(current: Ref, tree: &Tree, graph: &mut Graph) {
108  maybe_grow(|| match tree {
109    Tree::Ref { nam, .. } => graph.add(current, nam.clone()),
110    Tree::Con { fst: _, snd } => collect_refs(current.clone(), snd, graph),
111    tree => {
112      for subtree in tree_children(tree) {
113        collect_refs(current.clone(), subtree, graph);
114      }
115    }
116  });
117}
118
119impl From<&Book> for Graph {
120  fn from(book: &Book) -> Self {
121    let mut graph = Self::new();
122
123    for (r#ref, net) in book.defs.iter() {
124      // Collect active refs from the root.
125      collect_refs(r#ref.clone(), &net.root, &mut graph);
126
127      // Collect active refs from redexes.
128      for (_, left, right) in net.rbag.iter() {
129        if let Tree::Ref { nam, .. } = left {
130          graph.add(r#ref.clone(), nam.clone());
131        }
132        if let Tree::Ref { nam, .. } = right {
133          graph.add(r#ref.clone(), nam.clone());
134        }
135      }
136    }
137
138    graph
139  }
140}
141
142impl Graph {
143  pub fn new() -> Self {
144    Self::default()
145  }
146
147  pub fn add(&mut self, r#ref: Ref, dependency: Ref) {
148    self.0.entry(r#ref).or_default().insert(dependency.clone());
149    self.0.entry(dependency).or_default();
150  }
151
152  pub fn get(&self, r#ref: &Ref) -> Option<&RefSet> {
153    self.0.get(r#ref)
154  }
155}
156
157impl Debug for Graph {
158  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
159    write!(f, "Graph{:?}", self.0)
160  }
161}
162
163fn combinations_from_merges(cycle: Vec<Ref>) -> Vec<Vec<Ref>> {
164  let mut combinations: Vec<Vec<Ref>> = vec![vec![]];
165  for r#ref in cycle {
166    if let Some(index) = r#ref.find(MERGE_SEPARATOR) {
167      let (left, right) = r#ref.split_at(index);
168      let right = &right[MERGE_SEPARATOR.len()..]; // skip merge separator
169      let mut new_combinations = Vec::new();
170      for combination in &combinations {
171        let mut left_comb = combination.clone();
172        left_comb.push(left.to_string());
173        new_combinations.push(left_comb);
174
175        let mut right_comb = combination.clone();
176        right_comb.push(right.to_string());
177        new_combinations.push(right_comb);
178      }
179      combinations = new_combinations;
180    } else {
181      for combination in &mut combinations {
182        combination.push(r#ref.clone());
183      }
184    }
185  }
186  combinations
187}
bend/hvm/mutual_recursion.rs

bend/hvm/
mutual_recursion.rs
