hash: and-semantics: add missing nuance in marking.

A weak table with and-semantics expires entries only when both
their key and value is unreachable. When this condition is not
met, therefore, the hash table generates a reference to both
the key and value.  This gives rise to a subtlety that must
be be correctly handles in the marking phase.

* hash.c (hash_mark): When marking an and-semantics table,
whenever we find a reachable key or value, we know that the
entry is staying. Therefore we mark it: if the key is
unreachable, we mark the value and vice versa. This is
important because these unreachable objects may be the only
references for reaching reach some other objects via one or
more weak hash tables. Those secondary objects may
spontaneously disappear due to those other hash tables
removing their entries.  E.g suppose H0 has and-semantics, and
some K-V entry in H1 has a reachable K, but unreachable V.
Therefore the entry is not eligible for removal, and thus
maintains references to K and V. Suppose V happens to be a key
in a weak-key hash table H1.  If, while marking H0, we do not
mark V, then there is a risk that H1 will be processed first
during the later weak procesing stage, and H1 will wrongly
expire its V entry due to the key V being unreachable.  Then
when H0 is processed, it will mark V, making it reachable, but
too late: the V entry in H1 is already spuriously gone.
The main principle at play is that an entry in an
and-semantics table strongly holds on to a key if the value is
reachable and vice versa. Only if both are simultaneously
unreachable does it relinquish its references.

1 files changed, 12 insertions, 1 deletions

diff --git a/hash.c b/hash.c
index 280d47ea..00d5764e 100644
--- a/hash.c
+++ b/hash.c
@@ -631,9 +631,20 @@ static void hash_mark(val hash)
     }
     break;
   case hash_weak_or:
-  case hash_weak_and:
     /* mark nothing */
     break;
+  case hash_weak_and:
+    /* Mark key if value is reachable and vice versa. */
+    for (i = 0; i < h->modulus; i++) {
+      for (iter = h->table->v.vec[i]; iter; iter = us_cdr(iter)) {
+        val entry = us_car(iter);
+        if (gc_is_reachable(us_car(entry)))
+          gc_mark(us_cdr(entry));
+        else if (gc_is_reachable(us_cdr(entry)))
+          gc_mark(us_car(entry));
+      }
+    }
+    break;
   }
 
   h->next = reachable_weak_hashes;