<commit_before>/* g/r.c
**
*/
#include "all.h"
#include <murmur3.h>

/* _frag_word(): fast fragment/branch prediction for top word.
*/
static u3_weak
_frag_word(c3_w a_w, u3_noun b)
{
  c3_assert(0 != a_w);

  {
    c3_w dep_w = u3x_dep(a_w);

    while ( dep_w ) {
      if ( c3n == u3a_is_cell(b) ) {
        return u3_none;
      }
      else {
        u3a_cell* b_u = u3a_to_ptr(b);

        b = *(((u3_noun*)&(b_u->hed)) + (1 & (a_w >> (dep_w - 1))));
        dep_w--;
      }
    }
    return b;
  }
}

/* _frag_deep(): fast fragment/branch for deep words.
*/
static u3_weak
_frag_deep(c3_w a_w, u3_noun b)
{
  c3_w dep_w = 32;

  while ( dep_w ) {
    if ( c3n == u3a_is_cell(b) ) {
      return u3_none;
    }
    else {
      u3a_cell* b_u = u3a_to_ptr(b);

      b = *(((u3_noun*)&(b_u->hed)) + (1 & (a_w >> (dep_w - 1))));
      dep_w--;
    }
  }
  return b;
}

/* u3r_at():
**
**   Return fragment (a) of (b), or u3_none if not applicable.
*/
u3_weak
u3r_at(u3_atom a, u3_noun b)
{
  c3_assert(u3_none != a);
  c3_assert(u3_none != b);

  u3t_on(far_o);

  if ( 0 == a ) {
    u3t_off(far_o);
    return u3_none;
  }

  if ( _(u3a_is_cat(a)) ) {
    u3t_off(far_o);
    return _frag_word(a, b);
  }
  else {
    if ( !_(u3a_is_pug(a)) ) {
      u3t_off(far_o);
      return u3_none;
    }
    else {
      u3a_atom* a_u = u3a_to_ptr(a);
      c3_w len_w      = a_u->len_w;

      b = _frag_word(a_u->buf_w[len_w - 1], b);
      len_w -= 1;

      if ( u3_none == b ) {
        u3t_off(far_o);
        return b;
      }

      while ( len_w ) {
        b = _frag_deep(a_u->buf_w[len_w - 1], b);

        if ( u3_none == b ) {
          u3t_off(far_o);

          return b;
        } else {
          len_w--;
        }
      }
      u3t_off(far_o);

      return b;
    }
  }
}

/* u3r_mean():
**
**   Attempt to deconstruct `a` by axis, noun pairs; 0 terminates.
**   Axes must be sorted in tree order.
*/
  struct _mean_pair {
    c3_w    axe_w;
    u3_noun* som;
  };

  static c3_w
  _mean_cut(c3_w               len_w,
            struct _mean_pair* prs_m)
  {
    c3_w i_w, cut_t, cut_w;

    cut_t = 0;
    cut_w = 0;
    for ( i_w = 0; i_w < len_w; i_w++ ) {
      c3_w axe_w = prs_m[i_w].axe_w;

      if ( (cut_t == 0) && (3 == u3x_cap(axe_w)) ) {
        cut_t = 1;
        cut_w = i_w;
      }
      prs_m[i_w].axe_w = u3x_mas(axe_w);
    }
    return cut_t ? cut_w : i_w;
  }

  static c3_o
  _mean_extract(u3_noun            som,
                c3_w               len_w,
                struct _mean_pair* prs_m)
  {
    if ( len_w == 0 ) {
      return c3y;
    }
    else if ( (len_w == 1) && (1 == prs_m[0].axe_w) ) {
      *prs_m->som = som;
      return c3y;
    }
    else {
      if ( c3n == u3a_is_cell(som) ) {
        return c3n;
      } else {
        c3_w cut_w = _mean_cut(len_w, prs_m);

        return c3a
          (_mean_extract(u3a_h(som), cut_w, prs_m),
           _mean_extract(u3a_t(som), (len_w - cut_w), (prs_m + cut_w)));
      }
    }
  }

c3_o
u3r_vmean(u3_noun som, va_list ap)
{
  va_list            aq;
  c3_w               len_w;
  struct _mean_pair* prs_m;

  c3_assert(u3_none != som);

  //  traverse copy of va_list for alloca
  //
  va_copy(aq, ap);
  len_w = 0;

  while ( 1 ) {
    if ( 0 == va_arg(aq, c3_w) ) {
      break;
    }
    va_arg(aq, u3_noun*);
    len_w++;
  }

  va_end(aq);

  c3_assert( 0 != len_w );
  prs_m = alloca(len_w * sizeof(struct _mean_pair));

  //  traverse va_list and extract args
  //
  {
    c3_w i_w;

    for ( i_w = 0; i_w < len_w; i_w++ ) {
      prs_m[i_w].axe_w = va_arg(ap, c3_w);
      prs_m[i_w].som = va_arg(ap, u3_noun*);
    }

    va_end(ap);
  }

  //  extract axis from som
  //
  return _mean_extract(som, len_w, prs_m);
}

c3_o
u3r_mean(u3_noun som, ...)
{
  c3_o    ret_o;
  va_list ap;

  va_start(ap, som);
  ret_o = u3r_vmean(som, ap);
  va_end(ap);

  return ret_o;
}

//  stack frame for tracking noun comparison and unification
//
//    we always compare arbitrary nouns in a none-frame.
//    when we compare two cells, we change the none-frame to a head-frame
//    and push a new none-frame for their heads. if the heads are equal,
//    we get the cells from the head-frame and unify their head pointers.
//    then, we convert the head-frame to a tail-frame and repeat with
//    the tails, mutatis mutandis.
//
//    in Hoon, this structure would be:
//
//    $%  [%none a=* b=*]
//        [%head a=^ b=^]
//        [%tail a=^ b=^]
//    ==
//
#define SING_NONE 0
#define SING_HEAD 1
#define SING_TAIL 2

typedef struct {
  c3_y     sat_y;
  u3_noun  a;
  u3_noun  b;
} eqframe;

/* _cr_sing_push(): push a new stack frame, initialized as SING_NONE.
*/
static inline eqframe*
_cr_sing_push(u3a_pile* pil_u, u3_noun a, u3_noun b)
{
  eqframe* fam_u = u3a_push(pil_u);
  fam_u->sat_y   = SING_NONE;
  fam_u->a       = a;
  fam_u->b       = b;
  return fam_u;
}

/* _cr_sing_mug(): short-circuit comparison if mugs are present and not equal.
*/
static inline c3_o
_cr_sing_mug(u3a_noun* a_u, u3a_noun* b_u)
{
  //  XX add debug assertions that both mugs are 31-bit
  //  (ie, not u3a_take() relocation references)
  //
  if ( a_u->mug_w && b_u->mug_w && (a_u->mug_w != b_u->mug_w) ) {
    return c3n;
  }

  return c3y;
}

/* _cr_sing_atom(): check if atom [a] is indirect and equal to noun [b]
*/
static inline c3_o
_cr_sing_atom(u3_atom a, u3_noun b)
{
  //  [a] is an atom, not pointer-equal to noun [b].
  //  if they're not both indirect atoms, they can't be equal.
  //
  if (  (c3n == u3a_is_pug(a))
     || (c3n == u3a_is_pug(b)) )
  {
    return c3n;
  }
  else {
    u3a_atom* a_u = u3a_to_ptr(a);
    u3a_atom* b_u = u3a_to_ptr(b);

    //  [a] and [b] are not equal if their mugs are present and not equal.
    //
    if ( c3n == _cr_sing_mug((u3a_noun*)a_u, (u3a_noun*)b_u) ) {
      return c3n;
    }
    else {
      c3_w a_w = a_u->len_w;
      c3_w b_w = b_u->len_w;

      //  [a] and [b] are not equal if their lengths are not equal
      //
      if ( a_w != b_w ) {
        return c3n;
      }
      else {
        c3_w i_w;

        //  XX memcmp
        //
        for ( i_w = 0; i_w < a_w; i_w++ ) {
          if ( a_u->buf_w[i_w] != b_u->buf_w[i_w] ) {
            return c3n;
          }
        }
      }
    }
  }

  return c3y;
}

/* _cr_sing_cape_test(): check for previous comparison of [a] and [b].
*/
static inline c3_o
_cr_sing_cape_test(u3p(u3h_root) har_p, u3_noun a, u3_noun b)
{
  u3_noun key = u3nc(u3a_to_off(a), u3a_to_off(b));
  u3_noun val;

  u3t_off(euq_o);
  val = u3h_git(har_p, key);
  u3t_on(euq_o);

  u3z(key);
  return ( u3_none != val ) ? c3y : c3n;
}

/* _cr_sing_cape_keep(): store [a] and [b] to short-circuit subsequent tests.
**                   NB: [a] and [b] (which MUST be equal nouns)
**                       are cons'd as offsets (direct atoms) to avoid refcount churn.
*/
static inline void
_cr_sing_cape_keep(u3p(u3h_root) har_p, u3_noun a, u3_noun b)
{
  //  only store if [a] and [b] are copies of each other
  //
  if ( a != b ) {
    u3_noun key = u3nc(u3a_to_off(a), u3a_to_off(b));
    u3t_off(euq_o);
    u3h_put(har_p, key, c3y);
    u3t_on(euq_o);
    u3z(key);
  }
}

/* _cr_sing_cape(): unifying equality with comparison deduplication
 *                  (tightly coupled to _cr_sing)
 */
static c3_o
_cr_sing_cape(u3a_pile* pil_u, u3p(u3h_root) har_p)
{
  eqframe* fam_u = u3a_peek(pil_u);
  u3_noun   a, b, key;
  u3_weak   got;
  u3a_cell* a_u;
  u3a_cell* b_u;

  //  loop while arguments remain on the stack
  //
  do {
    a = fam_u->a;
    b = fam_u->b;

    switch ( fam_u->sat_y ) {

      //  [a] and [b] are arbitrary nouns
      //
      case SING_NONE: {
        if ( a == b ) {
          break;
        }
        else if ( c3y == u3a_is_atom(a) ) {
          if ( c3n == _cr_sing_atom(a, b) ) {
            return c3n;
          }
          else {
            break;
          }
        }
        else if ( c3y == u3a_is_atom(b) ) {
          return c3n;
        }
        //  [a] and [b] are cells
        //
        else {
          a_u = u3a_to_ptr(a);
          b_u = u3a_to_ptr(b);

          //  short-circuiting mug check
          //
          if ( c3n == _cr_sing_mug((u3a_noun*)a_u, (u3a_noun*)b_u) ) {
            return c3n;
          }
          //  short-circuiting re-comparison check
          //
          else if ( c3y == _cr_sing_cape_test(har_p, a, b) ) {
            fam_u = u3a_pop(pil_u);
            continue;
          }
          //  upgrade none-frame to head-frame, check heads
          //
          else {
            fam_u->sat_y = SING_HEAD;
            fam_u = _cr_sing_push(pil_u, a_u->hed, b_u->hed);
            continue;
          }
        }
      } break;

      //  cells [a] and [b] have equal heads
      //
      case SING_HEAD: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->hed), &(b_u->hed));

        //  upgrade head-frame to tail-frame, check tails
        //
        fam_u->sat_y = SING_TAIL;
        fam_u = _cr_sing_push(pil_u, a_u->tel, b_u->tel);
        continue;
      }

      //  cells [a] and [b] are equal
      //
      case SING_TAIL: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->tel), &(b_u->tel));
      } break;

      default: {
        c3_assert(0);
      } break;
    }

    //  track equal pairs to short-circuit possible (re-)comparison
    //
    _cr_sing_cape_keep(har_p, a, b);

    fam_u = u3a_pop(pil_u);
  }
  while ( c3n == u3a_pile_done(pil_u) );

  return c3y;
}

/* _cr_sing(): unifying equality.
*/
static c3_o
_cr_sing(u3_noun a, u3_noun b)
{
  c3_s     ovr_s = 0;
  u3a_cell*  a_u;
  u3a_cell*  b_u;
  eqframe* fam_u;
  u3a_pile pil_u;

  //  initialize stack control, push arguments onto the stack (none-frame)
  //
  u3a_pile_prep(&pil_u, sizeof(eqframe));
  fam_u = _cr_sing_push(&pil_u, a, b);

  //  loop while arguments are on the stack
  //
  while ( c3n == u3a_pile_done(&pil_u) ) {
    a = fam_u->a;
    b = fam_u->b;

    switch ( fam_u->sat_y ) {

      //  [a] and [b] are arbitrary nouns
      //
      case SING_NONE: {
        if ( a == b ) {
          break;
        }
        else if ( c3y == u3a_is_atom(a) ) {
          if ( c3n == _cr_sing_atom(a, b) ) {
            u3R->cap_p = pil_u.top_p;
            return c3n;
          }
          else {
            break;
          }
        }
        else if ( c3y == u3a_is_atom(b) ) {
          u3R->cap_p = pil_u.top_p;
          return c3n;
        }
        //  [a] and [b] are cells
        //
        else {
          a_u = u3a_to_ptr(a);
          b_u = u3a_to_ptr(b);

          //  short-circuiting mug check
          //
          if ( c3n == _cr_sing_mug((u3a_noun*)a_u, (u3a_noun*)b_u) ) {
            u3R->cap_p = pil_u.top_p;
            return c3n;
          }
          //  upgrade none-frame to head-frame, check heads
          //
          else {
            fam_u->sat_y = SING_HEAD;
            fam_u = _cr_sing_push(&pil_u, a_u->hed, b_u->hed);
            continue;
          }
        }
      } break;

      //  cells [a] and [b] have equal heads
      //
      case SING_HEAD: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->hed), &(b_u->hed));

        //  upgrade head-frame to tail-frame, check tails
        //
        fam_u->sat_y = SING_TAIL;
        fam_u = _cr_sing_push(&pil_u, a_u->tel, b_u->tel);
        continue;
      }

      //  cells [a] and [b] are equal
      //
      case SING_TAIL: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->tel), &(b_u->tel));
      } break;

      default: {
        c3_assert(0);
      } break;
    }

    //  [ovr_s] counts comparisons, if it overflows, we've likely hit
    //  a pathological case (highly duplicated tree), so we de-duplicate
    //  subsequent comparisons by maintaining a set of equal pairs.
    //
    if ( 0 == ++ovr_s ) {
      u3p(u3h_root) har_p = u3h_new();
      c3_o ret_o = _cr_sing_cape(&pil_u, har_p);
      u3h_free(har_p);
      u3R->cap_p = pil_u.top_p;
      return ret_o;
    }

    fam_u = u3a_pop(&pil_u);
  }

  return c3y;
}

/* u3r_sing(): Yes iff [a] and [b] are the same noun.
*/
c3_o
u3r_sing(u3_noun a, u3_noun b)
{
  c3_o ret_o;
  u3t_on(euq_o);
  ret_o = _cr_sing(a, b);
  u3t_off(euq_o);
  return ret_o;
}

c3_o
u3r_fing(u3_noun a,
           u3_noun b)
{
  return (a == b) ? c3y : c3n;
}

/* u3r_sing_cell():
**
**   Yes iff `[p q]` and `b` are the same noun.
*/
c3_o
u3r_sing_cell(u3_noun p,
                u3_noun q,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing(p, u3a_h(b)),
                       u3r_sing(q, u3a_t(b))));
}
c3_o
u3r_fing_cell(u3_noun p,
                u3_noun q,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_fing(p, u3a_h(b)),
                       u3r_fing(q, u3a_t(b))));
}

/* u3r_sing_mixt():
**
**   Yes iff `[p q]` and `b` are the same noun.
*/
c3_o
u3r_sing_mixt(const c3_c* p_c,
                u3_noun     q,
                u3_noun     b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing_c(p_c, u3a_h(b)),
                       u3r_sing(q, u3a_t(b))));
}
c3_o
u3r_fing_mixt(const c3_c* p_c,
                u3_noun     q,
                u3_noun     b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing_c(p_c, u3a_h(b)),
                       u3r_fing(q, u3a_t(b))));
}

/* u3r_sing_trel():
**
**   Yes iff `[p q r]` and `b` are the same noun.
*/
c3_o
u3r_sing_trel(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing(p, u3a_h(b)),
                       u3r_sing_cell(q, r, u3a_t(b))));
}
c3_o
u3r_fing_trel(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_fing(p, u3a_h(b)),
                       u3r_fing_cell(q, r, u3a_t(b))));
}

/* u3r_sing_qual():
**
**   Yes iff `[p q r]` and `b` are the same noun.
*/
c3_o
u3r_sing_qual(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun s,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing(p, u3a_h(b)),
                       u3r_sing_trel(q, r, s, u3a_t(b))));
}
c3_o
u3r_fing_qual(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun s,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_fing(p, u3a_h(b)),
                       u3r_fing_trel(q, r, s, u3a_t(b))));
}

/* u3r_nord():
**
**   Return 0, 1 or 2 if `a` is below, equal to, or above `b`.
*/
u3_atom
u3r_nord(u3_noun a,
        u3_noun b)
{
  c3_assert(u3_none != a);
  c3_assert(u3_none != b);

  if ( a == b ) {
    return 1;
  }
  else {
    if ( _(u3a_is_atom(a)) ) {
      if ( !_(u3a_is_atom(b)) ) {
        return 0;
      } else {
        if ( _(u3a_is_cat(a)) ) {
          if ( _(u3a_is_cat(b)) ) {
            return (a < b) ? 0 : 2;
          }
          else return 0;
        }
        else if ( _(u3a_is_cat(b)) ) {
          return 2;
        }
        else {
          u3a_atom* a_u = u3a_to_ptr(a);
          u3a_atom* b_u = u3a_to_ptr(b);

          c3_w w_rez = a_u->len_w;
          c3_w w_mox = b_u->len_w;

          if ( w_rez != w_mox ) {
            return (w_rez < w_mox) ? 0 : 2;
          }
          else {
            c3_w i_w;

            for ( i_w = 0; i_w < w_rez; i_w++ ) {
              c3_w ai_w = a_u->buf_w[i_w];
              c3_w bi_w = b_u->buf_w[i_w];

              if ( ai_w != bi_w ) {
                return (ai_w < bi_w) ? 0 : 2;
              }
            }
            return 1;
          }
        }
      }
    } else {
      if ( _(u3a_is_atom(b)) ) {
        return 2;
      } else {
        u3_atom c = u3r_nord(u3a_h(a), u3a_h(b));

        if ( 1 == c ) {
          return u3r_nord(u3a_t(a), u3a_t(b));
        } else {
          return c;
        }
      }
    }
  }
}

/* u3r_sing_c(): cord/C-string value equivalence.
*/
c3_o
u3r_sing_c(const c3_c* a_c,
           u3_noun     b)
{
  c3_assert(u3_none != b);

  if ( !_(u3a_is_atom(b)) ) {
    return c3n;
  }
  else {
    c3_w w_sof = strlen(a_c);
    c3_w i_w;

    if ( w_sof != u3r_met(3, b) ) {
      return c3n;
    }
    for ( i_w = 0; i_w < w_sof; i_w++ ) {
      if ( u3r_byte(i_w, b) != a_c[i_w] ) {
        return c3n;
      }
    }
    return c3y;
  }
}

/* u3r_bush():
**
**   Factor [a] as a bush [b.[p q] c].
*/
c3_o
u3r_bush(u3_noun  a,
           u3_noun* b,
           u3_noun* c)
{
  c3_assert(u3_none != a);

  if ( _(u3a_is_atom(a)) ) {
    return c3n;
  }
  else {
    *b = u3a_h(a);

    if ( _(u3a_is_atom(*b)) ) {
      return c3n;
    } else {
      *c = u3a_t(a);
      return c3y;
    }
  }
}

/* u3r_bite(): retrieve/default $bloq and $step from $bite.
*/
c3_o
u3r_bite(u3_noun bite, u3_atom* bloq, u3_atom *step)
{
  u3_noun hed, tal;

  if ( c3n == u3r_cell(bite, &hed, &tal) ) {
    *bloq = bite;
    *step = 1;
    return c3y;
  }
  else if (  (c3n == u3a_is_atom(hed))
          || (c3n == u3a_is_atom(tal)) )
  {
    return c3n;
  }
  else {
    *bloq = hed;
    *step = tal;
    return c3y;
  }
}

/* u3r_cell():
**
**   Factor (a) as a cell (b c).
*/
c3_o
u3r_cell(u3_noun  a,
           u3_noun* b,
           u3_noun* c)
{
  c3_assert(u3_none != a);

  if ( _(u3a_is_atom(a)) ) {
    return c3n;
  }
  else {
    if ( b ) *b = u3a_h(a);
    if ( c ) *c = u3a_t(a);
    return c3y;
  }
}

/* u3r_p():
**
**   & [0] if [a] is of the form [b *c].
*/
c3_o
u3r_p(u3_noun  a,
        u3_noun  b,
        u3_noun* c)
{
  u3_noun feg, nux;

  if ( (c3y == u3r_cell(a, &feg, &nux)) &&
       (c3y == u3r_sing(feg, b)) )
  {
    *c = nux;
    return c3y;
  }
  else return c3n;
}

/* u3r_pq():
**
**   & [0] if [a] is of the form [b *c d].
*/
c3_o
u3r_pq(u3_noun  a,
         u3_noun  b,
         u3_noun* c,
         u3_noun* d)
{
  u3_noun nux;

  if ( (c3y == u3r_p(a, b, &nux)) &&
       (c3y == u3r_cell(nux, c, d)) )
  {
    return c3y;
  }
  else return c3n;
}
<commit_msg>u3: make output pointer optional in u3r_p()<commit_after>/* g/r.c
**
*/
#include "all.h"
#include <murmur3.h>

/* _frag_word(): fast fragment/branch prediction for top word.
*/
static u3_weak
_frag_word(c3_w a_w, u3_noun b)
{
  c3_assert(0 != a_w);

  {
    c3_w dep_w = u3x_dep(a_w);

    while ( dep_w ) {
      if ( c3n == u3a_is_cell(b) ) {
        return u3_none;
      }
      else {
        u3a_cell* b_u = u3a_to_ptr(b);

        b = *(((u3_noun*)&(b_u->hed)) + (1 & (a_w >> (dep_w - 1))));
        dep_w--;
      }
    }
    return b;
  }
}

/* _frag_deep(): fast fragment/branch for deep words.
*/
static u3_weak
_frag_deep(c3_w a_w, u3_noun b)
{
  c3_w dep_w = 32;

  while ( dep_w ) {
    if ( c3n == u3a_is_cell(b) ) {
      return u3_none;
    }
    else {
      u3a_cell* b_u = u3a_to_ptr(b);

      b = *(((u3_noun*)&(b_u->hed)) + (1 & (a_w >> (dep_w - 1))));
      dep_w--;
    }
  }
  return b;
}

/* u3r_at():
**
**   Return fragment (a) of (b), or u3_none if not applicable.
*/
u3_weak
u3r_at(u3_atom a, u3_noun b)
{
  c3_assert(u3_none != a);
  c3_assert(u3_none != b);

  u3t_on(far_o);

  if ( 0 == a ) {
    u3t_off(far_o);
    return u3_none;
  }

  if ( _(u3a_is_cat(a)) ) {
    u3t_off(far_o);
    return _frag_word(a, b);
  }
  else {
    if ( !_(u3a_is_pug(a)) ) {
      u3t_off(far_o);
      return u3_none;
    }
    else {
      u3a_atom* a_u = u3a_to_ptr(a);
      c3_w len_w      = a_u->len_w;

      b = _frag_word(a_u->buf_w[len_w - 1], b);
      len_w -= 1;

      if ( u3_none == b ) {
        u3t_off(far_o);
        return b;
      }

      while ( len_w ) {
        b = _frag_deep(a_u->buf_w[len_w - 1], b);

        if ( u3_none == b ) {
          u3t_off(far_o);

          return b;
        } else {
          len_w--;
        }
      }
      u3t_off(far_o);

      return b;
    }
  }
}

/* u3r_mean():
**
**   Attempt to deconstruct `a` by axis, noun pairs; 0 terminates.
**   Axes must be sorted in tree order.
*/
  struct _mean_pair {
    c3_w    axe_w;
    u3_noun* som;
  };

  static c3_w
  _mean_cut(c3_w               len_w,
            struct _mean_pair* prs_m)
  {
    c3_w i_w, cut_t, cut_w;

    cut_t = 0;
    cut_w = 0;
    for ( i_w = 0; i_w < len_w; i_w++ ) {
      c3_w axe_w = prs_m[i_w].axe_w;

      if ( (cut_t == 0) && (3 == u3x_cap(axe_w)) ) {
        cut_t = 1;
        cut_w = i_w;
      }
      prs_m[i_w].axe_w = u3x_mas(axe_w);
    }
    return cut_t ? cut_w : i_w;
  }

  static c3_o
  _mean_extract(u3_noun            som,
                c3_w               len_w,
                struct _mean_pair* prs_m)
  {
    if ( len_w == 0 ) {
      return c3y;
    }
    else if ( (len_w == 1) && (1 == prs_m[0].axe_w) ) {
      *prs_m->som = som;
      return c3y;
    }
    else {
      if ( c3n == u3a_is_cell(som) ) {
        return c3n;
      } else {
        c3_w cut_w = _mean_cut(len_w, prs_m);

        return c3a
          (_mean_extract(u3a_h(som), cut_w, prs_m),
           _mean_extract(u3a_t(som), (len_w - cut_w), (prs_m + cut_w)));
      }
    }
  }

c3_o
u3r_vmean(u3_noun som, va_list ap)
{
  va_list            aq;
  c3_w               len_w;
  struct _mean_pair* prs_m;

  c3_assert(u3_none != som);

  //  traverse copy of va_list for alloca
  //
  va_copy(aq, ap);
  len_w = 0;

  while ( 1 ) {
    if ( 0 == va_arg(aq, c3_w) ) {
      break;
    }
    va_arg(aq, u3_noun*);
    len_w++;
  }

  va_end(aq);

  c3_assert( 0 != len_w );
  prs_m = alloca(len_w * sizeof(struct _mean_pair));

  //  traverse va_list and extract args
  //
  {
    c3_w i_w;

    for ( i_w = 0; i_w < len_w; i_w++ ) {
      prs_m[i_w].axe_w = va_arg(ap, c3_w);
      prs_m[i_w].som = va_arg(ap, u3_noun*);
    }

    va_end(ap);
  }

  //  extract axis from som
  //
  return _mean_extract(som, len_w, prs_m);
}

c3_o
u3r_mean(u3_noun som, ...)
{
  c3_o    ret_o;
  va_list ap;

  va_start(ap, som);
  ret_o = u3r_vmean(som, ap);
  va_end(ap);

  return ret_o;
}

//  stack frame for tracking noun comparison and unification
//
//    we always compare arbitrary nouns in a none-frame.
//    when we compare two cells, we change the none-frame to a head-frame
//    and push a new none-frame for their heads. if the heads are equal,
//    we get the cells from the head-frame and unify their head pointers.
//    then, we convert the head-frame to a tail-frame and repeat with
//    the tails, mutatis mutandis.
//
//    in Hoon, this structure would be:
//
//    $%  [%none a=* b=*]
//        [%head a=^ b=^]
//        [%tail a=^ b=^]
//    ==
//
#define SING_NONE 0
#define SING_HEAD 1
#define SING_TAIL 2

typedef struct {
  c3_y     sat_y;
  u3_noun  a;
  u3_noun  b;
} eqframe;

/* _cr_sing_push(): push a new stack frame, initialized as SING_NONE.
*/
static inline eqframe*
_cr_sing_push(u3a_pile* pil_u, u3_noun a, u3_noun b)
{
  eqframe* fam_u = u3a_push(pil_u);
  fam_u->sat_y   = SING_NONE;
  fam_u->a       = a;
  fam_u->b       = b;
  return fam_u;
}

/* _cr_sing_mug(): short-circuit comparison if mugs are present and not equal.
*/
static inline c3_o
_cr_sing_mug(u3a_noun* a_u, u3a_noun* b_u)
{
  //  XX add debug assertions that both mugs are 31-bit
  //  (ie, not u3a_take() relocation references)
  //
  if ( a_u->mug_w && b_u->mug_w && (a_u->mug_w != b_u->mug_w) ) {
    return c3n;
  }

  return c3y;
}

/* _cr_sing_atom(): check if atom [a] is indirect and equal to noun [b]
*/
static inline c3_o
_cr_sing_atom(u3_atom a, u3_noun b)
{
  //  [a] is an atom, not pointer-equal to noun [b].
  //  if they're not both indirect atoms, they can't be equal.
  //
  if (  (c3n == u3a_is_pug(a))
     || (c3n == u3a_is_pug(b)) )
  {
    return c3n;
  }
  else {
    u3a_atom* a_u = u3a_to_ptr(a);
    u3a_atom* b_u = u3a_to_ptr(b);

    //  [a] and [b] are not equal if their mugs are present and not equal.
    //
    if ( c3n == _cr_sing_mug((u3a_noun*)a_u, (u3a_noun*)b_u) ) {
      return c3n;
    }
    else {
      c3_w a_w = a_u->len_w;
      c3_w b_w = b_u->len_w;

      //  [a] and [b] are not equal if their lengths are not equal
      //
      if ( a_w != b_w ) {
        return c3n;
      }
      else {
        c3_w i_w;

        //  XX memcmp
        //
        for ( i_w = 0; i_w < a_w; i_w++ ) {
          if ( a_u->buf_w[i_w] != b_u->buf_w[i_w] ) {
            return c3n;
          }
        }
      }
    }
  }

  return c3y;
}

/* _cr_sing_cape_test(): check for previous comparison of [a] and [b].
*/
static inline c3_o
_cr_sing_cape_test(u3p(u3h_root) har_p, u3_noun a, u3_noun b)
{
  u3_noun key = u3nc(u3a_to_off(a), u3a_to_off(b));
  u3_noun val;

  u3t_off(euq_o);
  val = u3h_git(har_p, key);
  u3t_on(euq_o);

  u3z(key);
  return ( u3_none != val ) ? c3y : c3n;
}

/* _cr_sing_cape_keep(): store [a] and [b] to short-circuit subsequent tests.
**                   NB: [a] and [b] (which MUST be equal nouns)
**                       are cons'd as offsets (direct atoms) to avoid refcount churn.
*/
static inline void
_cr_sing_cape_keep(u3p(u3h_root) har_p, u3_noun a, u3_noun b)
{
  //  only store if [a] and [b] are copies of each other
  //
  if ( a != b ) {
    u3_noun key = u3nc(u3a_to_off(a), u3a_to_off(b));
    u3t_off(euq_o);
    u3h_put(har_p, key, c3y);
    u3t_on(euq_o);
    u3z(key);
  }
}

/* _cr_sing_cape(): unifying equality with comparison deduplication
 *                  (tightly coupled to _cr_sing)
 */
static c3_o
_cr_sing_cape(u3a_pile* pil_u, u3p(u3h_root) har_p)
{
  eqframe* fam_u = u3a_peek(pil_u);
  u3_noun   a, b, key;
  u3_weak   got;
  u3a_cell* a_u;
  u3a_cell* b_u;

  //  loop while arguments remain on the stack
  //
  do {
    a = fam_u->a;
    b = fam_u->b;

    switch ( fam_u->sat_y ) {

      //  [a] and [b] are arbitrary nouns
      //
      case SING_NONE: {
        if ( a == b ) {
          break;
        }
        else if ( c3y == u3a_is_atom(a) ) {
          if ( c3n == _cr_sing_atom(a, b) ) {
            return c3n;
          }
          else {
            break;
          }
        }
        else if ( c3y == u3a_is_atom(b) ) {
          return c3n;
        }
        //  [a] and [b] are cells
        //
        else {
          a_u = u3a_to_ptr(a);
          b_u = u3a_to_ptr(b);

          //  short-circuiting mug check
          //
          if ( c3n == _cr_sing_mug((u3a_noun*)a_u, (u3a_noun*)b_u) ) {
            return c3n;
          }
          //  short-circuiting re-comparison check
          //
          else if ( c3y == _cr_sing_cape_test(har_p, a, b) ) {
            fam_u = u3a_pop(pil_u);
            continue;
          }
          //  upgrade none-frame to head-frame, check heads
          //
          else {
            fam_u->sat_y = SING_HEAD;
            fam_u = _cr_sing_push(pil_u, a_u->hed, b_u->hed);
            continue;
          }
        }
      } break;

      //  cells [a] and [b] have equal heads
      //
      case SING_HEAD: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->hed), &(b_u->hed));

        //  upgrade head-frame to tail-frame, check tails
        //
        fam_u->sat_y = SING_TAIL;
        fam_u = _cr_sing_push(pil_u, a_u->tel, b_u->tel);
        continue;
      }

      //  cells [a] and [b] are equal
      //
      case SING_TAIL: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->tel), &(b_u->tel));
      } break;

      default: {
        c3_assert(0);
      } break;
    }

    //  track equal pairs to short-circuit possible (re-)comparison
    //
    _cr_sing_cape_keep(har_p, a, b);

    fam_u = u3a_pop(pil_u);
  }
  while ( c3n == u3a_pile_done(pil_u) );

  return c3y;
}

/* _cr_sing(): unifying equality.
*/
static c3_o
_cr_sing(u3_noun a, u3_noun b)
{
  c3_s     ovr_s = 0;
  u3a_cell*  a_u;
  u3a_cell*  b_u;
  eqframe* fam_u;
  u3a_pile pil_u;

  //  initialize stack control, push arguments onto the stack (none-frame)
  //
  u3a_pile_prep(&pil_u, sizeof(eqframe));
  fam_u = _cr_sing_push(&pil_u, a, b);

  //  loop while arguments are on the stack
  //
  while ( c3n == u3a_pile_done(&pil_u) ) {
    a = fam_u->a;
    b = fam_u->b;

    switch ( fam_u->sat_y ) {

      //  [a] and [b] are arbitrary nouns
      //
      case SING_NONE: {
        if ( a == b ) {
          break;
        }
        else if ( c3y == u3a_is_atom(a) ) {
          if ( c3n == _cr_sing_atom(a, b) ) {
            u3R->cap_p = pil_u.top_p;
            return c3n;
          }
          else {
            break;
          }
        }
        else if ( c3y == u3a_is_atom(b) ) {
          u3R->cap_p = pil_u.top_p;
          return c3n;
        }
        //  [a] and [b] are cells
        //
        else {
          a_u = u3a_to_ptr(a);
          b_u = u3a_to_ptr(b);

          //  short-circuiting mug check
          //
          if ( c3n == _cr_sing_mug((u3a_noun*)a_u, (u3a_noun*)b_u) ) {
            u3R->cap_p = pil_u.top_p;
            return c3n;
          }
          //  upgrade none-frame to head-frame, check heads
          //
          else {
            fam_u->sat_y = SING_HEAD;
            fam_u = _cr_sing_push(&pil_u, a_u->hed, b_u->hed);
            continue;
          }
        }
      } break;

      //  cells [a] and [b] have equal heads
      //
      case SING_HEAD: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->hed), &(b_u->hed));

        //  upgrade head-frame to tail-frame, check tails
        //
        fam_u->sat_y = SING_TAIL;
        fam_u = _cr_sing_push(&pil_u, a_u->tel, b_u->tel);
        continue;
      }

      //  cells [a] and [b] are equal
      //
      case SING_TAIL: {
        a_u = u3a_to_ptr(a);
        b_u = u3a_to_ptr(b);
        u3a_wed(&(a_u->tel), &(b_u->tel));
      } break;

      default: {
        c3_assert(0);
      } break;
    }

    //  [ovr_s] counts comparisons, if it overflows, we've likely hit
    //  a pathological case (highly duplicated tree), so we de-duplicate
    //  subsequent comparisons by maintaining a set of equal pairs.
    //
    if ( 0 == ++ovr_s ) {
      u3p(u3h_root) har_p = u3h_new();
      c3_o ret_o = _cr_sing_cape(&pil_u, har_p);
      u3h_free(har_p);
      u3R->cap_p = pil_u.top_p;
      return ret_o;
    }

    fam_u = u3a_pop(&pil_u);
  }

  return c3y;
}

/* u3r_sing(): Yes iff [a] and [b] are the same noun.
*/
c3_o
u3r_sing(u3_noun a, u3_noun b)
{
  c3_o ret_o;
  u3t_on(euq_o);
  ret_o = _cr_sing(a, b);
  u3t_off(euq_o);
  return ret_o;
}

c3_o
u3r_fing(u3_noun a,
           u3_noun b)
{
  return (a == b) ? c3y : c3n;
}

/* u3r_sing_cell():
**
**   Yes iff `[p q]` and `b` are the same noun.
*/
c3_o
u3r_sing_cell(u3_noun p,
                u3_noun q,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing(p, u3a_h(b)),
                       u3r_sing(q, u3a_t(b))));
}
c3_o
u3r_fing_cell(u3_noun p,
                u3_noun q,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_fing(p, u3a_h(b)),
                       u3r_fing(q, u3a_t(b))));
}

/* u3r_sing_mixt():
**
**   Yes iff `[p q]` and `b` are the same noun.
*/
c3_o
u3r_sing_mixt(const c3_c* p_c,
                u3_noun     q,
                u3_noun     b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing_c(p_c, u3a_h(b)),
                       u3r_sing(q, u3a_t(b))));
}
c3_o
u3r_fing_mixt(const c3_c* p_c,
                u3_noun     q,
                u3_noun     b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing_c(p_c, u3a_h(b)),
                       u3r_fing(q, u3a_t(b))));
}

/* u3r_sing_trel():
**
**   Yes iff `[p q r]` and `b` are the same noun.
*/
c3_o
u3r_sing_trel(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing(p, u3a_h(b)),
                       u3r_sing_cell(q, r, u3a_t(b))));
}
c3_o
u3r_fing_trel(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_fing(p, u3a_h(b)),
                       u3r_fing_cell(q, r, u3a_t(b))));
}

/* u3r_sing_qual():
**
**   Yes iff `[p q r]` and `b` are the same noun.
*/
c3_o
u3r_sing_qual(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun s,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_sing(p, u3a_h(b)),
                       u3r_sing_trel(q, r, s, u3a_t(b))));
}
c3_o
u3r_fing_qual(u3_noun p,
                u3_noun q,
                u3_noun r,
                u3_noun s,
                u3_noun b)
{
  return c3a(_(u3a_is_cell(b)),
                c3a(u3r_fing(p, u3a_h(b)),
                       u3r_fing_trel(q, r, s, u3a_t(b))));
}

/* u3r_nord():
**
**   Return 0, 1 or 2 if `a` is below, equal to, or above `b`.
*/
u3_atom
u3r_nord(u3_noun a,
        u3_noun b)
{
  c3_assert(u3_none != a);
  c3_assert(u3_none != b);

  if ( a == b ) {
    return 1;
  }
  else {
    if ( _(u3a_is_atom(a)) ) {
      if ( !_(u3a_is_atom(b)) ) {
        return 0;
      } else {
        if ( _(u3a_is_cat(a)) ) {
          if ( _(u3a_is_cat(b)) ) {
            return (a < b) ? 0 : 2;
          }
          else return 0;
        }
        else if ( _(u3a_is_cat(b)) ) {
          return 2;
        }
        else {
          u3a_atom* a_u = u3a_to_ptr(a);
          u3a_atom* b_u = u3a_to_ptr(b);

          c3_w w_rez = a_u->len_w;
          c3_w w_mox = b_u->len_w;

          if ( w_rez != w_mox ) {
            return (w_rez < w_mox) ? 0 : 2;
          }
          else {
            c3_w i_w;

            for ( i_w = 0; i_w < w_rez; i_w++ ) {
              c3_w ai_w = a_u->buf_w[i_w];
              c3_w bi_w = b_u->buf_w[i_w];

              if ( ai_w != bi_w ) {
                return (ai_w < bi_w) ? 0 : 2;
              }
            }
            return 1;
          }
        }
      }
    } else {
      if ( _(u3a_is_atom(b)) ) {
        return 2;
      } else {
        u3_atom c = u3r_nord(u3a_h(a), u3a_h(b));

        if ( 1 == c ) {
          return u3r_nord(u3a_t(a), u3a_t(b));
        } else {
          return c;
        }
      }
    }
  }
}

/* u3r_sing_c(): cord/C-string value equivalence.
*/
c3_o
u3r_sing_c(const c3_c* a_c,
           u3_noun     b)
{
  c3_assert(u3_none != b);

  if ( !_(u3a_is_atom(b)) ) {
    return c3n;
  }
  else {
    c3_w w_sof = strlen(a_c);
    c3_w i_w;

    if ( w_sof != u3r_met(3, b) ) {
      return c3n;
    }
    for ( i_w = 0; i_w < w_sof; i_w++ ) {
      if ( u3r_byte(i_w, b) != a_c[i_w] ) {
        return c3n;
      }
    }
    return c3y;
  }
}

/* u3r_bush():
**
**   Factor [a] as a bush [b.[p q] c].
*/
c3_o
u3r_bush(u3_noun  a,
           u3_noun* b,
           u3_noun* c)
{
  c3_assert(u3_none != a);

  if ( _(u3a_is_atom(a)) ) {
    return c3n;
  }
  else {
    *b = u3a_h(a);

    if ( _(u3a_is_atom(*b)) ) {
      return c3n;
    } else {
      *c = u3a_t(a);
      return c3y;
    }
  }
}

/* u3r_bite(): retrieve/default $bloq and $step from $bite.
*/
c3_o
u3r_bite(u3_noun bite, u3_atom* bloq, u3_atom *step)
{
  u3_noun hed, tal;

  if ( c3n == u3r_cell(bite, &hed, &tal) ) {
    *bloq = bite;
    *step = 1;
    return c3y;
  }
  else if (  (c3n == u3a_is_atom(hed))
          || (c3n == u3a_is_atom(tal)) )
  {
    return c3n;
  }
  else {
    *bloq = hed;
    *step = tal;
    return c3y;
  }
}

/* u3r_cell():
**
**   Factor (a) as a cell (b c).
*/
c3_o
u3r_cell(u3_noun  a,
           u3_noun* b,
           u3_noun* c)
{
  c3_assert(u3_none != a);

  if ( _(u3a_is_atom(a)) ) {
    return c3n;
  }
  else {
    if ( b ) *b = u3a_h(a);
    if ( c ) *c = u3a_t(a);
    return c3y;
  }
}

/* u3r_p():
**
**   & [0] if [a] is of the form [b *c].
*/
c3_o
u3r_p(u3_noun  a,
        u3_noun  b,
        u3_noun* c)
{
  u3_noun feg, nux;

  if ( (c3y == u3r_cell(a, &feg, &nux)) &&
       (c3y == u3r_sing(feg, b)) )
  {
    if ( c ) *c = nux;
    return c3y;
  }
  else return c3n;
}

/* u3r_pq():
**
**   & [0] if [a] is of the form [b *c d].
*/
c3_o
u3r_pq(u3_noun  a,
         u3_noun  b,
         u3_noun* c,
         u3_noun* d)
{
  u3_noun nux;

  if ( (c3y == u3r_p(a, b, &nux)) &&
       (c3y == u3r_cell(nux, c, d)) )
  {
    return c3y;
  }
  else return c3n;
}

{'fraction_non_alphanumeric': 0.1434700107251877, 'fraction_numerical': 0.02893050628385997, 'mean_word_length': 1.6607155923026267, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 115, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5363612', 'n_tokens_mistral': 17126, 'n_tokens_neox': 16651, 'n_words': 3342}