1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

use crate::maybe_grow;
use hvmc::ast::{Book, Net, Tree};
use std::collections::{HashMap, HashSet};

pub fn add_recursive_priority(book: &mut Book) {
  // Direct dependencies
  let deps = book.iter().map(|(nam, net)| (nam.clone(), dependencies(net))).collect::<HashMap<_, _>>();
  // Recursive cycles
  let cycles = cycles(&deps);

  for cycle in cycles {
    // For each function in the cycle, if there are redexes with the
    // next ref in the cycle, add a priority to one of those redexes.
    for i in 0 .. cycle.len() {
      let cur = book.get_mut(&cycle[i]).unwrap();
      let nxt = &cycle[(i + 1) % cycle.len()];
      add_priority_next_in_cycle(cur, nxt);
    }
  }
}

fn add_priority_next_in_cycle(net: &mut Net, nxt: &String) {
  let mut count = 0;

  // Count the number of recursive refs
  for (_, a, b) in net.redexes.iter() {
    if let Tree::Ref { nam } = a {
      if nam == nxt {
        count += 1;
      }
    }
    if let Tree::Ref { nam } = b {
      if nam == nxt {
        count += 1;
      }
    }
  }

  // If there are more than one recursive ref, add a priority to the last (first to execute).
  if count > 1 {
    for (pri, a, b) in net.redexes.iter_mut().rev() {
      if let Tree::Ref { nam } = a {
        if nam == nxt {
          *pri = true;
        }
      }
      if let Tree::Ref { nam } = b {
        if nam == nxt {
          *pri = true;
        }
      }
    }
  }
}

type DepGraph = HashMap<String, HashSet<String>>;
type Cycles = Vec<Vec<String>>;

/// Find all cycles in the dependency graph.
pub fn cycles(deps: &DepGraph) -> Cycles {
  let mut cycles = vec![];
  let mut stack = vec![];
  let mut visited = HashSet::new();
  for nam in deps.keys() {
    if !visited.contains(nam) {
      find_cycles(deps, nam, &mut visited, &mut stack, &mut cycles);
    }
  }
  cycles
}

fn find_cycles(
  deps: &DepGraph,
  nam: &String,
  visited: &mut HashSet<String>,
  stack: &mut Vec<String>,
  cycles: &mut Cycles,
) {
  maybe_grow(|| {
    // Check if the current ref is already in the stack, which indicates a cycle.
    if let Some(cycle_start) = stack.iter().position(|n| n == nam) {
      // If found, add the cycle to the cycles vector.
      cycles.push(stack[cycle_start ..].to_vec());
      return;
    }
    // If the ref has not been visited yet, mark it as visited.
    if visited.insert(nam.clone()) {
      // Add the current ref to the stack to keep track of the path.
      stack.push(nam.clone());
      // Get the dependencies of the current ref.
      if let Some(dependencies) = deps.get(nam) {
        // Search for cycles from each dependency.
        for dep in dependencies {
          find_cycles(deps, dep, visited, stack, cycles);
        }
      }
      stack.pop();
    }
  })
}

/// Gather the set of net that this net directly depends on (has a ref in the net).
fn dependencies(net: &Net) -> HashSet<String> {
  let mut deps = HashSet::new();
  dependencies_tree(&net.root, &mut deps);
  for (_, a, b) in &net.redexes {
    dependencies_tree(a, &mut deps);
    dependencies_tree(b, &mut deps);
  }
  deps
}

fn dependencies_tree(tree: &Tree, deps: &mut HashSet<String>) {
  if let Tree::Ref { nam, .. } = tree {
    deps.insert(nam.clone());
  } else {
    for subtree in tree.children() {
      dependencies_tree(subtree, deps);
    }
  }
}