[Bug-mit-scheme] Hash table wart

[Gerald Jay Sussman]

There is a minor wart in hash-table/clean! for weak hash tables.  The
bug is that hash-table/clean! removes associations whose key is the #f
object, even though it should not because #f never gets garbage
collected.  For example:

1 ]=> (define frotz (make-eq-hash-table))

;Value: frotz

1 ]=> (hash-table/put! frotz #f 4)

;Unspecified return value

1 ]=> (hash-table/get frotz #f 'gone)

;Value: 4 <-- This is what I expect

1 ]=> (hash-table/clean! frotz)

;Unspecified return value

1 ]=> (hash-table/get frotz #f 'gone)

;Value: gone <-- Oops!


This problem can be solved by changing all three occurrences of
%weak-entry-key to %weak-entry-valid? in the definition of
weak-method:clean! in runtime/hashtb.scm, that is, from

(define (weak-method:clean! table)
  (let ((buckets (table-buckets table)))
    (let ((n-buckets (vector-length buckets)))
      (do ((i 0 (fix:+ i 1)))
          ((not (fix:< i n-buckets)))
        (letrec
            ((scan-head
              (lambda (p)
                (if (pair? p)
                    (if (%weak-entry-key (car p))
                        (begin
                          (vector-set! buckets i p)
                          (scan-tail (cdr p) p))
                        (begin
                          (decrement-table-count! table)
                          (scan-head (cdr p))))
                    (vector-set! buckets i p))))
             (scan-tail
              (lambda (p q)
                (if (pair? p)
                    (if (%weak-entry-key (car p))
                        (scan-tail (cdr p) p)
                        (begin
                          (decrement-table-count! table)
                          (let loop ((p (cdr p)))
                            (if (pair? p)
                                (if (%weak-entry-key (car p))
                                    (begin
                                      (set-cdr! q p)
                                      (scan-tail (cdr p) p))
                                    (begin
                                      (decrement-table-count! table)
                                      (loop (cdr p))))
                                (set-cdr! q p)))))))))
          (scan-head (vector-ref buckets i)))))))

to 

(define (weak-method:clean! table)
  (let ((buckets (table-buckets table)))
    (let ((n-buckets (vector-length buckets)))
      (do ((i 0 (fix:+ i 1)))
          ((not (fix:< i n-buckets)))
        (letrec
            ((scan-head
              (lambda (p)
                (if (pair? p)
                    (if (%weak-entry-valid? (car p))
                        (begin
                          (vector-set! buckets i p)
                          (scan-tail (cdr p) p))
                        (begin
                          (decrement-table-count! table)
                          (scan-head (cdr p))))
                    (vector-set! buckets i p))))
             (scan-tail
              (lambda (p q)
                (if (pair? p)
                    (if (%weak-entry-valid? (car p))
                        (scan-tail (cdr p) p)
                        (begin
                          (decrement-table-count! table)
                          (let loop ((p (cdr p)))
                            (if (pair? p)
                                (if (%weak-entry-valid? (car p))
                                    (begin
                                      (set-cdr! q p)
                                      (scan-tail (cdr p) p))
                                    (begin
                                      (decrement-table-count! table)
                                      (loop (cdr p))))
                                (set-cdr! q p)))))))))
          (scan-head (vector-ref buckets i)))))))


It appears that this offers an opportunity for a slight increase of
elegance.  The %weak-entry-valid? predicate can be abstracted from
this code, making cleaning of weak tables into a method like all the
other hash table operations.  This has the further advantage that it
becomes easier to add more kinds of hash tables with key structures
that are not anticipated by the current system.  For example, a table
whose keys are pairs, such that the pairs themselves should be held
strongly, but each component of the pair should be held weakly, and
such that the associations should be cleaned if either component gets
garbage collected.

GJS and AXCH