urbit · pkova · Jun 18, 2025 · May 9, 2025 · May 9, 2025 · May 9, 2025
diff --git a/.github/workflows/shared.yml b/.github/workflows/shared.yml
@@ -97,7 +97,7 @@ jobs:
             hashtable-test jets-test   \
             nock-test retrieve-test    \
             serial-test ames-test      \
-            pact-test                  \
+            pact-test equality-test    \
             boot-test newt-test        \
             vere-noun-test unix-test   \
             benchmarks                 \

diff --git a/build.zig b/build.zig
@@ -509,6 +509,11 @@ fn buildBinary(
                 .deps = &.{pkg_ent.artifact("ent")},
             },
             // pkg_noun
+            .{
+                .name = "equality-test",
+                .file = "pkg/noun/equality_tests.c",
+                .deps = noun_test_deps,
+            },
             .{
                 .name = "hashtable-test",
                 .file = "pkg/noun/hashtable_tests.c",

diff --git a/pkg/noun/allocate.c b/pkg/noun/allocate.c
@@ -1547,100 +1547,123 @@ u3a_use(u3_noun som)
   }
 }
 
-/* _ca_wed_who(): unify [a] and [b] on [rod_u], keeping the senior
-**
-** NB: this leaks a reference when it unifies in a senior road
+#define SWAP(l, r)    \
+  do { typeof(l) t = l; l = r; r = t; } while (0)
+
+/* _ca_wed_our(): unify [a] and [b] on u3R.
+*/
+static inline c3_o
+_ca_wed_our(u3_noun *restrict a, u3_noun *restrict b)
+{
+  c3_t asr_t = ( c3y == u3a_is_senior(u3R, *a) );
+  c3_t bsr_t = ( c3y == u3a_is_senior(u3R, *b) );
+
+  if ( asr_t == bsr_t ) {
+    //  both [a] and [b] are senior; we can't unify on u3R
+    //
+    if ( asr_t ) return c3n;
+
+    //  both are on u3R; keep the deeper address
+    //  (and gain a reference)
+    //
+    //    (N && <) || (S && >)
+    //    XX consider keeping higher refcount instead
+    //
+    if ( (*a > *b) == (c3y == u3a_is_north(u3R)) ) SWAP(a, b);
+
+    _me_gain_use(*a);
+  }
+  //  one of [a] or [b] are senior; keep it
+  //
+  else if ( !asr_t ) SWAP(a, b);
+
+  u3z(*b);
+  *b = *a;
+  return c3y;
+}
+
+/* _ca_wed_you(): unify [a] and [b] on senior [rod_u]. leaks
 */
 static c3_o
-_ca_wed_who(u3a_road* rod_u, u3_noun* a, u3_noun* b)
+_ca_wed_you(u3a_road* rod_u, u3_noun *restrict a, u3_noun *restrict b)
 {
+  //  XX assume( rod_u != u3R )
   c3_t asr_t = ( c3y == u3a_is_senior(rod_u, *a) );
   c3_t bsr_t = ( c3y == u3a_is_senior(rod_u, *b) );
-  c3_t nor_t = ( c3y == u3a_is_north(rod_u) );
-  c3_t own_t = ( rod_u == u3R );
 
-  //  both are on [rod_u]; gain a reference to whichever we keep
-  //
-  if ( !asr_t && !bsr_t ) {
-    //  keep [a]; it's deeper in the heap
+  if ( asr_t == bsr_t ) {
+    //  both [a] and [b] are senior; we can't unify on [rod_u]
     //
-    //    (N && >) || (S && <)
+    if ( asr_t ) return c3n;
+
+    //  both are on [rod_u]; keep the deeper address
+    //  (and gain a reference)
     //
-    if ( (*a > *b) == nor_t ) {
-      _me_gain_use(*a);
-      if ( own_t ) { u3z(*b); }
-      *b = *a;
-    }
-    //  keep [b]; it's deeper in the heap
+    //    (N && <) || (S && >)
+    //    XX consider keeping higher refcount instead
     //
-    else {
-      _me_gain_use(*b);
-      if ( own_t ) { u3z(*a); }
-      *a = *b;
-    }
+    if ( (*a > *b) == (c3y == u3a_is_north(rod_u)) ) SWAP(a, b);
 
-    return c3y;
-  }
-  //  keep [a]; it's senior
-  //
-  else if ( asr_t && !bsr_t ) {
-    if ( own_t ) { u3z(*b); }
-    *b = *a;
-    return c3y;
+    _me_gain_use(*a);
   }
-  //  keep [b]; it's senior
+  //  one of [a] or [b] are senior; keep it
   //
-  else if ( !asr_t && bsr_t ) {
-    if ( own_t ) { u3z(*a); }
-    *a = *b;
-    return c3y;
-  }
+  else if ( !asr_t ) SWAP(a, b);
 
-  //  both [a] and [b] are senior; we can't unify on [rod_u]
-  //
-  return c3n;
+  *b = *a;
+  return c3y;
 }
 
+#undef SWAP
+
 /* u3a_wed(): unify noun references.
 */
 void
-u3a_wed(u3_noun* a, u3_noun* b)
+u3a_wed(u3_noun *restrict a, u3_noun *restrict b)
 {
-  if ( *a != *b ) {
-    u3_road* rod_u = u3R;
+  //  XX assume( *a != *b )
+  u3_road* rod_u = u3R;
+  c3_o     wed_o;
+
+  if ( rod_u->kid_p ) return;
+
+  wed_o = _ca_wed_our(a, b);
 
-    //  while not at home, attempt to unify
-    //
-    //    we try to unify on our road, and retry on senior roads
-    //    until we succeed or reach the home road.
-    //
-    //    we can't perform this kind of butchery on the home road,
-    //    where asynchronous things can allocate.
-    //    (XX anything besides u3t_samp?)
-    //
-    //    when unifying on a higher road, we can't free nouns,
-    //    because we can't track junior nouns that point into
-    //    that road.
-    //
-    //    this is just an implementation issue -- we could set use
-    //    counts to 0 without actually freeing.  but the allocator
-    //    would have to be actually designed for this.
-    //    (alternately, we could keep a deferred free-list)
-    //
-    //    not freeing may generate spurious leaks, so we disable
-    //    senior unification when debugging memory.  this will
-    //    cause a very slow boot process as the compiler compiles
-    //    itself, constantly running into duplicates.
-    //
-    while ( (rod_u != &u3H->rod_u) &&
-            (c3n == _ca_wed_who(rod_u, a, b)) )
-    {
 #ifdef U3_MEMORY_DEBUG
-      break;
+  return;
 #else
-      rod_u = u3to(u3_road, rod_u->par_p);
+  if ( u3C.wag_w & u3o_debug_ram ) return;
 #endif
-    }
+
+  //  while not at home, attempt to unify
+  //
+  //    we try to unify on our road, and retry on senior roads
+  //    until we succeed or reach the home road.
+  //
+  //    we can't perform this kind of butchery on the home road,
+  //    where asynchronous things can allocate.
+  //    (XX anything besides u3t_samp?)
+  //
+  //    when unifying on a higher road, we can't free nouns,
+  //    because we can't track junior nouns that point into
+  //    that road.
+  //
+  //    this is just an implementation issue -- we could set use
+  //    counts to 0 without actually freeing.  but the allocator
+  //    would have to be actually designed for this.
+  //    (alternately, we could keep a deferred free-list)
+  //
+  //    not freeing may generate spurious leaks, so we disable
+  //    senior unification when debugging memory.  this will
+  //    cause a very slow boot process as the compiler compiles
+  //    itself, constantly running into duplicates.
+  //
+
+  while (  (c3n == wed_o)
+        && rod_u->par_p
+        && (&u3H->rod_u != (rod_u = u3to(u3_road, rod_u->par_p))) )
+  {
+    wed_o = _ca_wed_you(rod_u, a, b);
   }
 }
 

diff --git a/pkg/noun/allocate.h b/pkg/noun/allocate.h
@@ -585,7 +585,7 @@
         /* u3a_wed(): unify noun references.
         */
           void
-          u3a_wed(u3_noun* a, u3_noun* b);
+          u3a_wed(u3_noun *restrict a, u3_noun *restrict b);
 
         /* u3a_luse(): check refcount sanity.
         */

diff --git a/pkg/noun/equality_tests.c b/pkg/noun/equality_tests.c
@@ -0,0 +1,164 @@
+/// @file
+
+#include "noun.h"
+
+/* _setup(): prepare for tests.
+*/
+static void
+_setup(void)
+{
+  u3m_boot_lite(1 << 24);
+}
+
+static c3_i
+_test_unify_home(void)
+{
+  c3_i ret_i = 1;
+
+  u3_noun  a = u3nt(0, 0, 0);
+  u3_noun  b = u3nt(0, 0, 0);
+  c3_w kep_w;
+
+  u3_assert( u3t(a) < u3t(b) );
+  kep_w = u3t(a);
+
+  (void)u3r_sing(a, b);
+
+  if ( u3t(a) != u3t(b) ) {
+    fprintf(stderr, "test: unify home: failed\r\n");
+    ret_i = 0;
+  }
+  else if ( kep_w != u3t(b) ) {
+    fprintf(stderr, "test: unify home: deeper failed\r\n");
+    ret_i = 0;
+  }
+
+  u3z(a); u3z(b);
+
+  return ret_i;
+}
+
+static c3_i
+_test_unify_inner(void)
+{
+  c3_i   ret_i = 1;
+  c3_w   kep_w;
+  u3_noun a, b;
+
+  a = u3nt(0, 0, 0);
+  kep_w = u3t(a);
+
+  u3m_hate(0);
+
+  b = u3nt(0, 0, 0);
+
+  (void)u3r_sing(a, b);
+
+  if ( u3t(a) != u3t(b) ) {
+    fprintf(stderr, "test: unify inner 1: failed\r\n");
+    ret_i = 0;
+  }
+  else if ( kep_w != u3t(b) ) {
+    fprintf(stderr, "test: unify inner 1: deeper failed\r\n");
+    ret_i = 0;
+  }
+
+  b = u3m_love(0);
+
+  u3z(a); u3z(b);
+
+  //  --------
+
+  b = u3nt(0, 0, 0);
+  kep_w = u3t(b);
+
+  u3m_hate(0);
+
+  a = u3nt(0, 0, 0);
+
+  u3m_hate(0);
+
+  (void)u3r_sing(a, b);
+
+  if ( u3t(a) != u3t(b) ) {
+    fprintf(stderr, "test: unify inner 2: failed\r\n");
+    ret_i = 0;
+  }
+  else if ( kep_w != u3t(a) ) {
+    fprintf(stderr, "test: unify inner 2: deeper failed\r\n");
+    ret_i = 0;
+  }
+
+  a = u3m_love(u3m_love(0));
+
+  u3z(a); u3z(b);
+
+  return ret_i;
+}
+
+static c3_i
+_test_unify_inner_home(void)
+{
+  c3_i ret_i = 1;
+
+  u3_noun  a = u3nt(0, 0, 0);
+  u3_noun  b = u3nt(0, 0, 0);
+
+  u3m_hate(0);
+
+  (void)u3r_sing(a, b);
+
+  if ( u3t(a) == u3t(b) ) {
+    fprintf(stderr, "test: unify inner-home: succeeded?\r\n");
+    ret_i = 0;
+  }
+
+  u3m_love(0);
+
+  u3z(a); u3z(b);
+
+  return ret_i;
+}
+
+static c3_i
+_test_equality(void)
+{
+  c3_i ret_i = 1;
+
+  if ( !_test_unify_home() ) {
+    fprintf(stderr, "test: equality: unify home: failed\r\n");
+    ret_i = 0;
+  }
+
+  if ( !_test_unify_inner() ) {
+    fprintf(stderr, "test: equality: unify inner: failed\r\n");
+    ret_i = 0;
+  }
+
+  if ( !_test_unify_inner_home() ) {
+    fprintf(stderr, "test: equality: unify inner-home: failed\r\n");
+    ret_i = 0;
+  }
+
+  return ret_i;
+}
+
+/* main(): run all test cases.
+*/
+int
+main(int argc, char* argv[])
+{
+  _setup();
+
+  if ( !_test_equality() ) {
+    fprintf(stderr, "test equality: failed\r\n");
+    exit(1);
+  }
+
+  //  GC
+  //
+  u3m_grab(u3_none);
+
+  fprintf(stderr, "test equality: ok\r\n");
+  return 0;
+}