bend/hvm/
inline.rs

1use super::{net_trees_mut, tree_children, tree_children_mut};
2use crate::maybe_grow;
3use core::ops::BitOr;
4use hvm::ast::{Book, Net, Tree};
5use std::collections::{HashMap, HashSet};
6
7pub fn inline_hvm_book(book: &mut Book) -> Result<HashSet<String>, String> {
8  let mut state = InlineState::default();
9  state.populate_inlinees(book)?;
10  let mut all_changed = HashSet::new();
11  for (name, net) in &mut book.defs {
12    let mut inlined = false;
13    for tree in net_trees_mut(net) {
14      inlined |= state.inline_into(tree);
15    }
16    if inlined {
17      all_changed.insert(name.to_owned());
18    }
19  }
20  Ok(all_changed)
21}
22
23#[derive(Debug, Default)]
24struct InlineState {
25  inlinees: HashMap<String, Tree>,
26}
27
28impl InlineState {
29  fn populate_inlinees(&mut self, book: &Book) -> Result<(), String> {
30    for (name, net) in &book.defs {
31      if should_inline(net) {
32        // Detect cycles with tortoise and hare algorithm
33        let mut hare = &net.root;
34        let mut tortoise = &net.root;
35        // Whether or not the tortoise should take a step
36        let mut parity = false;
37        while let Tree::Ref { nam, .. } = hare {
38          let Some(net) = &book.defs.get(nam) else { break };
39          if should_inline(net) {
40            hare = &net.root;
41          } else {
42            break;
43          }
44          if parity {
45            let Tree::Ref { nam: tortoise_nam, .. } = tortoise else { unreachable!() };
46            if tortoise_nam == nam {
47              Err(format!("infinite reference cycle in `@{nam}`"))?;
48            }
49            tortoise = &book.defs[tortoise_nam].root;
50          }
51          parity = !parity;
52        }
53        self.inlinees.insert(name.to_owned(), hare.clone());
54      }
55    }
56    Ok(())
57  }
58  fn inline_into(&self, tree: &mut Tree) -> bool {
59    maybe_grow(|| {
60      let Tree::Ref { nam, .. } = &*tree else {
61        return tree_children_mut(tree).map(|t| self.inline_into(t)).fold(false, bool::bitor);
62      };
63      if let Some(inlined) = self.inlinees.get(nam) {
64        *tree = inlined.clone();
65        true
66      } else {
67        false
68      }
69    })
70  }
71}
72
73fn should_inline(net: &Net) -> bool {
74  net.rbag.is_empty() && tree_children(&net.root).next().is_none()
75}
bend/hvm/inline.rs

bend/hvm/
inline.rs
