bend/hvm/
add_recursive_priority.rs

1use super::tree_children;
2use crate::maybe_grow;
3use hvm::ast::{Book, Net, Tree};
4use std::collections::{HashMap, HashSet};
5
6pub fn add_recursive_priority(book: &mut Book) {
7  // Direct dependencies
8  let deps = book.defs.iter().map(|(nam, net)| (nam.clone(), dependencies(net))).collect::<HashMap<_, _>>();
9  // Recursive cycles
10  let cycles = cycles(&deps);
11
12  for cycle in cycles {
13    // For each function in the cycle, if there are redexes with the
14    // next ref in the cycle, add a priority to one of those redexes.
15    for i in 0..cycle.len() {
16      let cur = book.defs.get_mut(&cycle[i]).unwrap();
17      let nxt = &cycle[(i + 1) % cycle.len()];
18      add_priority_next_in_cycle(cur, nxt);
19    }
20  }
21}
22
23fn add_priority_next_in_cycle(net: &mut Net, nxt: &String) {
24  let mut count = 0;
25
26  // Count the number of recursive refs
27  for (_, a, b) in net.rbag.iter() {
28    if let Tree::Ref { nam } = a {
29      if nam == nxt {
30        count += 1;
31      }
32    }
33    if let Tree::Ref { nam } = b {
34      if nam == nxt {
35        count += 1;
36      }
37    }
38  }
39
40  // If there are more than one recursive ref, add a priority to them.
41  if count > 1 {
42    for (pri, a, b) in net.rbag.iter_mut().rev() {
43      if let Tree::Ref { nam } = a {
44        if nam == nxt {
45          *pri = true;
46        }
47      }
48      if let Tree::Ref { nam } = b {
49        if nam == nxt {
50          *pri = true;
51        }
52      }
53    }
54  }
55}
56
57type DepGraph = HashMap<String, HashSet<String>>;
58type Cycles = Vec<Vec<String>>;
59
60/// Find all cycles in the dependency graph.
61pub fn cycles(deps: &DepGraph) -> Cycles {
62  let mut cycles = vec![];
63  let mut stack = vec![];
64  let mut visited = HashSet::new();
65  for nam in deps.keys() {
66    if !visited.contains(nam) {
67      find_cycles(deps, nam, &mut visited, &mut stack, &mut cycles);
68    }
69  }
70  cycles
71}
72
73fn find_cycles(
74  deps: &DepGraph,
75  nam: &String,
76  visited: &mut HashSet<String>,
77  stack: &mut Vec<String>,
78  cycles: &mut Cycles,
79) {
80  maybe_grow(|| {
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 == nam) {
83      // If found, add the cycle to the cycles vector.
84      cycles.push(stack[cycle_start..].to_vec());
85      return;
86    }
87    // If the ref has not been visited yet, mark it as visited.
88    if visited.insert(nam.clone()) {
89      // Add the current ref to the stack to keep track of the path.
90      stack.push(nam.clone());
91      // Get the dependencies of the current ref.
92      if let Some(dependencies) = deps.get(nam) {
93        // Search for cycles from each dependency.
94        for dep in dependencies {
95          find_cycles(deps, dep, visited, stack, cycles);
96        }
97      }
98      stack.pop();
99    }
100  })
101}
102
103/// Gather the set of net that this net directly depends on (has a ref in the net).
104fn dependencies(net: &Net) -> HashSet<String> {
105  let mut deps = HashSet::new();
106  dependencies_tree(&net.root, &mut deps);
107  for (_, a, b) in &net.rbag {
108    dependencies_tree(a, &mut deps);
109    dependencies_tree(b, &mut deps);
110  }
111  deps
112}
113
114fn dependencies_tree(tree: &Tree, deps: &mut HashSet<String>) {
115  if let Tree::Ref { nam, .. } = tree {
116    deps.insert(nam.clone());
117  } else {
118    for subtree in tree_children(tree) {
119      dependencies_tree(subtree, deps);
120    }
121  }
122}
bend/hvm/add_recursive_priority.rs

bend/hvm/
add_recursive_priority.rs
