HigherOrderCO/Bend

Auto-reconstructed constructors not being linearized properly when there's nested matches

Closed this issue · 1 comments

Map/get2 map key =
  match map {
    Map/Leaf: (*, map)
    Map/Node:
      switch _ = (== 0 key) {
        0: switch _ = (% key 2) {
          0:
            let (got, rest) = (Map/get2 map.left (/ key 2))
            (got, (Map/Node map.value rest map.right))
          _:
            let (got, rest) = (Map/get2 map.right (/ key 2))
            (got, (Map/Node map.value map.left rest))
        }
        _: (map.value, map)
      }
  }

  main = *

The use of map inside the switch is accidentally causing it to be duplicated.
We already have an optimization that is supposed to prevent this: we insert after each branch the matched variable as an alias to its reconstruction (eg. use map = Map/Node(map.value, map.left, map.right) is added wrapping this match case).

However, because aliases are resolved very late in compilation, after linearization, map is incorrectly treated as if it were a normal variable.

This is happening in Bend version 0.2.36 with the builtin Map/get. I could do a simpler example.

Fixed #591