hash-table bug

Skip to first unread message

Arthur Gleckler

Aug 3, 2020, 11:36:34 AM8/3/20
to chibi-scheme
I haven't been able to track down the source of this bug:

> chibi-scheme -V
chibi-scheme 0.9.0 "fluorine" (chibi r7rs ratios complex uvector threads full-unicode modules dynamic-loading linux little-endian)
> chibi-scheme
> (import (srfi 69))
> (define foo (make-hash-table))
> (hash-table-set! foo "bar" #t)
> (hash-table-exists? foo "bar")
#f     ; expected #t
> (hash-table->alist foo)
(("bar" . #t))

However, it seems to be due to string identity:

> chibi-scheme
> (import (srfi 69))
> (define foo (make-hash-table))
> (define bar "bar")
> (hash-table-set! foo bar #t)
> (hash-table-exists? foo bar)
#t     ; expected result

Please forgive me if I'm missing something obvious.


Alex Shinn

Aug 3, 2020, 11:33:17 PM8/3/20
to chibi-...@googlegroups.com
Thanks for the report!

This was definitely a bug, and a very stupid one.  Tracking it down
was a pain because it's not deterministic - there are of course unit
tests for this and they don't trigger if the tests are run in full, but
strangely do if only the (srfi 69) tests are run in isolation.  In
conjunction with the fact that Chibi exclusively uses eq? tables
internally, this somehow never showed up.

The problem was in hashing trailing non-Scheme object data in
objects.  There was a mis-calculation in the bounds for this, likely
aggravated by the recent shuffling of field order.

Fixed by simply not hashing this data.


You received this message because you are subscribed to the Google Groups "chibi-scheme" group.
To unsubscribe from this group and stop receiving emails from it, send an email to chibi-scheme...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/chibi-scheme/a457564f-d4c3-42d2-873a-7053c158d18bo%40googlegroups.com.

Alex Shinn

Aug 4, 2020, 6:03:27 AM8/4/20
to chibi-...@googlegroups.com
On Tue, Aug 4, 2020 at 12:33 PM Alex Shinn <alex...@gmail.com> wrote:
Fixed by simply not hashing this data.

... which was the quickest fix I could provide while making sure
my kids didn't drown each other in the wading pool.  If you were
wondering what "trailing non-Scheme object data" was, that's the
bytes of the strings.  I restored for strings (or rather the underlying
uvectors), otherwise they would all hash to the same value (which
is correct but inefficient).

It's a shame to have to special case strings in `hash', but I foresee
too many problems otherwise in the original logic (even fixed).


Reply all
Reply to author
0 new messages