Function merge

crates/kernel/src/canonical_check.rs:545–576

Merge two sorted slices of `(KId, &KConst)` pairs. Mirrors `merge` (`src/ix/compile.rs:2671`).

(
  left: Vec<(KId<M>, &'a KConst<M>)>,
  right: Vec<(KId<M>, &'a KConst<M>)>,
  ctx: &KMutCtx,
  resolve_ctor: &dyn Fn(&KId<M>) -> Option<KConst<M>>,
)

) -> Result<Vec<(KId<M>, &'a KConst<M>)>, TcError<M>> {
  let mut result = Vec::with_capacity(left.len() + right.len());
  let mut left_iter = left.into_iter();
  let mut right_iter = right.into_iter();
  let mut left_item = left_iter.next();
  let mut right_item = right_iter.next();

  while let (Some(l), Some(r)) = (&left_item, &right_item) {
    let cmp = compare_kconst(l.1, r.1, ctx, resolve_ctor)?.ordering;
    if cmp == Ordering::Greater {
      result.push(right_item.take().unwrap());
      right_item = right_iter.next();
    } else {
      result.push(left_item.take().unwrap());
      left_item = left_iter.next();
    }
  }
  if let Some(l) = left_item {
    result.push(l);
    result.extend(left_iter);
  }
  if let Some(r) = right_item {
    result.push(r);
    result.extend(right_iter);
  }
  Ok(result)
}

/// Merge-sort a class of `(KId, &KConst)` pairs by structural comparison.
/// Mirrors `sort_by_compare` (`src/ix/compile.rs:2708`).
fn sort_by_compare<'a, M: KernelMode>(
  items: &[(KId<M>, &'a KConst<M>)],
  ctx: &KMutCtx,
  resolve_ctor: &dyn Fn(&KId<M>) -> Option<KConst<M>>,
) -> Result<Vec<(KId<M>, &'a KConst<M>)>, TcError<M>> {
  if items.len() <= 1 {
    return Ok(items.to_vec());