simple_mark.ml

type value =
  | Block of block
  | Value of int
and block = {
  mutable marked : bool;
  fields : value array;
}

(* this doesn't work, fails when there is cycle and no progress *)
(* The idea here is that on each step we will be always traversing unmarked
   nodes and marking only one of the branches, then starting again until
   all the reachable nodes are marked *)
let rec mark_block_step block =
  let fields = block.fields in
  let length = Array.length fields in

  let rec loop index =
    let next () = loop (index + 1) in

    if index >= length - 1 then
      block.marked <- true
    else
      let field = Array.unsafe_get fields index in
      match field with
      | Block { marked = true; fields = _ }
      | Value _ ->
        next ()
      | Block block -> mark_block_step block in

  loop 0

let rec mark_block block =
  if not block.marked then (
    mark_block_step block;
    mark_block block)