hash: revert bad fix in weak processing.

This commit reverts the April 11, 2020 commit
a4c376979d15323ad729e92e41ba43768e8dc163, subject line
"hash: bugfix: spurious retention in weak processing".
That commit is a regression.

This revert requires a follow-up; the commit was trying to
fix an issue which now reappears. It will have to be
fixed differently.

The regression is that in a situation in which data is
referenced through two or more dependent weak tables, entries
that are reachable can spontaneously disappear from downstream
tables.

Suppose H0 and H1 are weak-key tables. Suppose the program
holds a datum K0, which is the only reference through which
D1 is reached, in the following chain:

  K0 -> [H0] -> K1 -> [H1] -> D1

K0 is a key in hash table H0, which has weak keys.
The the associated value K1 is a key in H1, which then
references D1. H0 holds the only reference to K1,
and H1 holds the only reference to D1.

During the first GC marking phase, because we do not mark any
part of a table which has weak keys, when we process H0
we do not mark the value K1. Thus K1 looks unreachable.

In the second weak hash processing pass, because K1 was
treated as unreachable, the <K1, D1> entry in H1 is
incorrectly expired.

This issue affects TXR's origin_hash and form_to_ln_hash,
which are in this relationship. The problem was uncovered in
recent tags.tl work, manifesting as a spurious disappearance
of line number info when processing .txr files. The line
number info disappeared for entries which were traced through
the origin_hash via the macro-ancestor function (see the
unexpand function in tags.tl).

* hash.c (hash_mark): Only skip marking tables that have
both weak keys and values. For weak key tables, mark all the
values and vice versa: for weak value tables, mark the keys.

* txr.1: Text resembling original text restored.

1 files changed, 29 insertions, 13 deletions

diff --git a/hash.c b/hash.c
index f900806e..b1d4f748 100644
--- a/hash.c
+++ b/hash.c
@@ -601,30 +601,46 @@ static void hash_mark(val hash)
 
   gc_mark(h->userdata);
 
+  if (h->count == 0) {
+    gc_mark(h->table);
+    return;
+  }
+
   /* Use counts will be re-calculated by a scan of the
      hash iterators which are still reachable. */
   h->usecount = 0;
 
   switch (h->flags) {
+    cnum i;
+    val iter;
   case hash_weak_none:
-    /* If the hash is not weak, we can simply mark the table
-       vector and we are done. */
     gc_mark(h->table);
-    break;
+    return;
   case hash_weak_keys:
+    /* Mark values only. Don't mark the table. */
+    for (i = 0; i < h->modulus; i++) {
+      for (iter = h->table->v.vec[i]; iter; iter = us_cdr(iter)) {
+        val entry = us_car(iter);
+        gc_mark(us_cdr(entry));
+      }
+    }
+    break;
   case hash_weak_vals:
-  case hash_weak_both:
-    /* If the hash is weak, we don't touch it at this time,
-       but add it to the list of reachable weak hashes,
-       unless it is empty. */
-    if (h->count > 0) {
-      h->next = reachable_weak_hashes;
-      reachable_weak_hashes = h;
-    } else {
-      gc_mark(h->table);
-      break;
+    /* Mark keys only. Don't mark the table. */
+    for (i = 0; i < h->modulus; i++) {
+      for (iter = h->table->v.vec[i]; iter; iter = us_cdr(iter)) {
+        val entry = us_car(iter);
+        gc_mark(us_car(entry));
+      }
     }
+    break;
+  case hash_weak_both:
+    /* mark nothing */
+    break;
   }
+
+  h->next = reachable_weak_hashes;
+  reachable_weak_hashes = h;
 }
 
 static struct cobj_ops hash_ops = cobj_ops_init(hash_equal_op,