Repository: Kindelia/HVM
File: src/ast.rs (Rust)

Code before:
  ///
  /// When calling this function, it is expected that definitions that are directly
  /// unsafe are already marked as such in the `compiled_book`.
  /// 
  /// This does not completely solve the cloning safety in HVM. It only stops invalid
  /// **global** definitions from being cloned, but local unsafe code can still be
  /// cloned and can generate seemingly unexpected results, such as placing eraser
  /// nodes in weird places. See HVM issue [#362](https://github.com/HigherOrderCO/HVM/issues/362)
  /// for an example.
  fn propagate_safety(&self, compiled_book: &mut hvm::Book, lookup: &BTreeMap<String, usize>) {
    let rev_dependencies = self.direct_dependencies_reversed();
    let mut visited: BTreeSet<&str> = BTreeSet::new();
    let mut stack: Vec<&str> = Vec::new();

    for (name, _) in self.defs.iter() {
      let def = &compiled_book.defs[lookup[name]];
      if !def.safe {
        stack.push(&name);
      }
    }

    while let Some(curr) = stack.pop() {
      if visited.contains(curr) {
        continue;
      }
      visited.insert(curr);

      let def = &mut compiled_book.defs[lookup[curr]];
      def.safe = false;

      for &next in rev_dependencies[curr].iter() {
        stack.push(next);
      }
    }
  }

  /// Calculates the dependencies of each definition but stores them reversed,
  /// that is, if definition `A` requires `B`, `B: A` is in the return map.
  /// This is used to propagate unsafe definitions to others that depend on them.
  /// 
  /// This solution has linear complexity on the number of definitions in the
  /// book and the number of direct references in each definition, but it also
  /// traverses each definition's trees entirely once.
  ///
  /// Complexity: O(d*t + r)
  /// - `d` is the number of definitions in the book
  /// - `r` is the number of direct references in each definition
  /// - `t` is the number of nodes in each tree
  fn direct_dependencies_reversed<'name>(&'name self) -> BTreeMap<&'name str, BTreeSet<&'name str>> {
    let mut result = BTreeMap::new();
    for (name, _) in self.defs.iter() {

Review comment (suggestion):
```suggestion
      if !visited.insert(curr) {
        continue;
      }
```

Code after:
    return book;
  }

  /// Propagate unsafe definitions to those that reference them.
  ///
  /// When calling this function, it is expected that definitions that are directly
  /// unsafe are already marked as such in the `compiled_book`.
  /// 
  /// This does not completely solve the cloning safety in HVM. It only stops invalid
  /// **global** definitions from being cloned, but local unsafe code can still be
  /// cloned and can generate seemingly unexpected results, such as placing eraser
  /// nodes in weird places. See HVM issue [#362](https://github.com/HigherOrderCO/HVM/issues/362)
  /// for an example.
  fn propagate_safety(&self, compiled_book: &mut hvm::Book, lookup: &BTreeMap<String, u32>) {
    let dependents = self.direct_dependents();
    let mut stack: Vec<&str> = Vec::new();

    for (name, _) in self.defs.iter() {
      let def = &mut compiled_book.defs[lookup[name] as usize];
      if !def.safe {
        for next in dependents[name.as_str()].iter() {
          stack.push(next);
        }
      }
    }

    while let Some(curr) = stack.pop() {
      let def = &mut compiled_book.defs[lookup[curr] as usize];
      if !def.safe {
        // Already visited, skip this
        continue;
      }

      def.safe = false;

      for &next in dependents[curr].iter() {
        stack.push(next);
      }
    }
  }

  /// Calculates the dependents of each definition, that is, if definition `A`
  /// requires `B`, `B: A` is in the return map. This is used to propagate unsafe
  /// definitions to others that depend on them.
  /// 
  /// This solution has linear complexity on the number of definitions in the
  /// book and the number of direct references in each definition, but it also
  /// traverses each definition's trees entirely once.
  ///
  /// Complexity: O(d*t + r)
  /// - `d` is the number of definitions in the book