let diff s t =
  let rec loop ans s t =
    match (s,t) with
      | (_,[]) -> ans @ (List.rev s)
      | ([],_) -> ans
      | ((u::s as ul), (v::t as vl)) ->
          if u.Range.lo > v.Range.hi then
            loop ans ul t
          else if u.Range.hi < v.Range.lo then
            loop (u::ans) s vl
          else
            match Range.intersect u v with
              | None -> invalid_arg "impossible to get here"
              | Some w ->
                  let u_pre = Range.make u.Range.lo (w.Range.lo - 1) |> Result.ok in
                  let u_post = Range.make (w.Range.hi + 1) u.Range.hi |> Result.ok in
                  (* v_pre = Range.make_opt v.Range.lo (w.Range.lo - 1)
                   ** v_pre not needed, note also that u_pre and v_pre cannot both be None *)
                  let v_post = Range.make (w.Range.hi + 1) v.Range.hi |> Result.ok in
                  let ans = match u_pre with None -> ans | Some x -> x::ans in
                  let s = match u_post with None -> s | Some x -> x::s in
                  let t = match v_post with None -> t | Some x -> x::t in
                  loop ans s t
  in
  to_canonical (loop [] s t)