EQUAL hash tables do not work properly with strings with fill-pointers as keys

[sjl]

trafficstars

Sorry for the awkward title. The spec for gethash says:

Value is the object in hash-table whose key is the same as key under the hash-table's equivalence test.

The spec for equal says:

Two arrays are equal only if they are eq, with one exception: strings and bit vectors are compared element-by-element (using eql). If either x or y has a fill pointer, the fill pointer limits the number of elements examined by equal.

If I'm reading the spec correctly, then if a hash table has a key of (make-array 10 :fill-pointer 0 :element-type 'character), you should be able to look up the value with a vanilla "" (no fill pointer) and vice versa. But ABCL seems to treat these as different keys when calling gethash:

Armed Bear Common Lisp 1.7.1 
Java 11.0.8 Ubuntu 
OpenJDK 64-Bit Server VM 
Low-level initialization completed in 0.162 seconds. 
Startup completed in 0.779 seconds. 
Loading /home/sjl/.abclrc completed in 4.819 seconds. 
Type ":help" for a list of available commands. 
 
 
[Armed Bear] CL-USER> (defparameter *h* (make-hash-table :test #'equal)) 
*H* 
 
[Armed Bear] CL-USER> (defparameter *s* (make-array 10 :fill-pointer 0 :element-type 'character)) 
*S* 
 
[Armed Bear] CL-USER> (setf (gethash *s* *h*) 1) 
1 
 
[Armed Bear] CL-USER> (assert (equal "" *s*)) 
NIL 
 
[Armed Bear] CL-USER> (assert (eql 1 (gethash *s* *h*))) 
NIL 
 
[Armed Bear] CL-USER> (assert (eql 1 (gethash "" *h*))) 
#<THREAD "interpreter" {2112507D}>: Debugger invoked on condition of type SIMPLE-ERROR 
  The assertion (EQL 1 (GETHASH "" *H*)) failed. 
Restarts: 
  0: CONTINUE  Retry assertion. 
  1: TOP-LEVEL Return to top level. 
[1] > 1 
 
[Armed Bear] CL-USER>
(maphash 
  (lambda (k v) 
    (when (equal k "") 
      (format t "The empty string is definitely in this hash table, with a value of ~S.~%" v))) 
  *h*) 
The empty string is definitely in this hash table, with a value of 1. 
NIL 
 
[Armed Bear] CL-USER> (inspect *h*) 
An object of type HASH-TABLE at #x31BE4231 
   0 KEY [bucket 10] --> "" 
   1 VALUE ------------> 1 
[1] > 

SBCL, CCL, and ECL all work as I expect ("" will retrieve the expected value from the hash table). So I think this is a bug in ABCL.

[alanruttenberg]

It's a bit of an odd case, as s fill-pointer is mutable. By the rule you can change the contents of s and no longer be able to use it as a key.

(setq fp (make-array 2 :fill-pointer 1 :element-type 'character :initial-contents (list #\a #\b))) (setq tab (make-hash-table :test 'equalp)) (setf (gethash fp tab) 3) (gethash fp tab) -> 3 (setf (gethash "ab" tab) 2) (gethash "ab" tab) -> 2 (setf (fill-pointer fp) 2) (gethash fp tab) -> 2

But then there's this https://stackoverflow.com/questions/53363008/using-mutable-data-as-hash-table-keys-in-common-lisp which says if you change a mutable key the behavior is undefined. However, it's not clear to me whether it matters since you aren't mutating s. Still, it seems like a bad idea to use mutable keys in an equal hash table.

But then, when I tried to compare to an eq table I got something that doesn't make sense to me, so there's clearly something odd going on.

(setq tab (make-hash-table :test 'eq)) (setf (fill-pointer fp) 2) (setq fp2 fp) (setf (gethash fp tab) fp) (setf (fill-pointer fp) 1) (eq fp2 fp) -> t (eq (gethash fp tab) fp) -> nil (whoops!)

Ok, so what I was trying to get at was that in the case of an eq hash table, you should be able to change the fill pointer and get the same value back, which would differ from the equal hash table and not having consistent behavior would be odd, since the intuition is that if two things are eq, they are equal.

Alan

On Tue, Aug 25, 2020 at 9:52 PM Steve Losh [email protected] wrote:

Sorry for the awkward title. The spec for gethash says http://clhs.lisp.se/Body/f_gethas.htm#gethash:

Value is the object in hash-table whose key is the same as key under the hash-table's equivalence test.

The spec for equal says http://clhs.lisp.se/Body/f_equal.htm#equal:

Two arrays are equal only if they are eq, with one exception: strings and bit vectors are compared element-by-element (using eql). If either x or y has a fill pointer, the fill pointer limits the number of elements examined by equal.

If I'm reading the spec correctly, then if a hash table has a key of (make-array 10 :fill-pointer 0 :element-type 'character), you should be able to look up the value with a vanilla "" (no fill pointer) and vice versa. But ABCL seems to treat these as different keys when calling gethash:

Armed Bear Common Lisp 1.7.1 Java 11.0.8 Ubuntu OpenJDK 64-Bit Server VM Low-level initialization completed in 0.162 seconds. Startup completed in 0.779 seconds. Loading /home/sjl/.abclrc completed in 4.819 seconds. Type ":help" for a list of available commands.

[Armed Bear] CL-USER> (defparameter h (make-hash-table :test #'equal)) H

[Armed Bear] CL-USER> (defparameter s (make-array 10 :fill-pointer 0 :element-type 'character)) S

[Armed Bear] CL-USER> (setf (gethash s h) 1) 1

[Armed Bear] CL-USER> (assert (equal "" s)) NIL

[Armed Bear] CL-USER> (assert (eql 1 (gethash s h))) NIL

[Armed Bear] CL-USER> (assert (eql 1 (gethash "" h))) #<THREAD "interpreter" {2112507D}>: Debugger invoked on condition of type SIMPLE-ERROR The assertion (EQL 1 (GETHASH "" H)) failed. Restarts: 0: CONTINUE Retry assertion. 1: TOP-LEVEL Return to top level. [1] > 1

[Armed Bear] CL-USER> (maphash (lambda (k v) (when (equal k "") (format t "The empty string is definitely in this hash table, with a value of ~S.~%" v))) h) The empty string is definitely in this hash table, with a value of 1. NIL

[Armed Bear] CL-USER> (inspect h) An object of type HASH-TABLE at #x31BE4231 0 KEY [bucket 10] --> "" 1 VALUE ------------> 1 [1] >

SBCL, CCL, and ECL all work as I expect ("" will retrieve the expected value from the hash table). So I think this is a bug in ABCL.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/armedbear/abcl/issues/275, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAB3CDUW3J4FUOBNZVC2J4TSCRTEPANCNFSM4QLI4J6A .

[sjl]

Still, it seems like a bad idea to use mutable keys in an equal hash table.

All strings are mutable, even those without fill pointers. Yeah, if you actually mutate the data in a way that matters for the test, all bets are off. But this code isn't doing any mutation of the strings.

But then, when I tried to compare to an eq table I got something that doesn't make sense to me, so there's clearly something odd going on.

This also seems like a second (related) bug to me.