1.0.23.21: Stack allocated conses for MIPS.
[sbcl.git] / tests / hash.impure.lisp
1 ;;;; This software is part of the SBCL system. See the README file for
2 ;;;; more information.
3 ;;;;
4 ;;;; While most of SBCL is derived from the CMU CL system, the test
5 ;;;; files (like this one) were written from scratch after the fork
6 ;;;; from CMU CL.
7 ;;;;
8 ;;;; This software is in the public domain and is provided with
9 ;;;; absolutely no warranty. See the COPYING and CREDITS files for
10 ;;;; more information.
11
12 (in-package :cl-user)
13
14 (use-package :test-util)
15 (use-package :assertoid)
16
17 (defstruct foo)
18 (defstruct bar x y)
19
20 ;;; SXHASH and PSXHASH should distribute hash values well over the
21 ;;; space of possible values, so that collisions between the hash
22 ;;; values of unequal objects should be very uncommon. (Except of
23 ;;; course the hash values must collide when the objects are EQUAL or
24 ;;; EQUALP respectively!)
25 (locally
26   ;; In order to better test not-EQ-but-EQUAL and not-EQ-but-EQUALP,
27   ;; we'd like to suppress some optimizations.
28   (declare (notinline complex float coerce + - expt))
29   (flet ((make-sxhash-subtests ()
30            (list (cons 0 1)
31                  (list 0 1)
32                  (cons 1 0)
33                  (cons (cons 1 0) (cons 0 0))
34                  (cons (list 1 0) (list 0 0))
35                  (list (cons 1 0) (list 0 0))
36                  (list (cons 0 1) (list 0 0))
37                  (list (cons 0 0) (cons 1 0))
38                  (list (cons 0 0) (cons 0 1))
39
40                  44     (float 44)     (coerce 44 'double-float)
41                  -44    (float -44)    (coerce -44 'double-float)
42                  0      (float 0)      (coerce 0 'double-float)
43                  -0     (- (float 0))  (- (coerce 0 'double-float))
44                  -121   (float -121)   (coerce -121 'double-float)
45                  3/4    (float 3/4)    (coerce 3/4 'double-float)
46                  -3/4   (float -3/4)   (coerce -3/4 'double-float)
47                  45     (float 45)     (coerce 45 'double-float)
48                  441/10 (float 441/10) (coerce (float 441/10) 'double-float)
49
50                  (expt 2 33) (expt 2.0 33) (expt 2.0d0 33)
51                  (- (expt 1/2 50)) (- (expt 0.5 50)) (- (expt 0.5d0 50))
52                  (+ (expt 1/2 50)) (+ (expt 0.5 50)) (+ (expt 0.5d0 50))
53
54                  (complex 1.0 2.0) (complex 1.0d0 2.0)
55                  (complex 1.5 -3/2) (complex 1.5 -1.5d0)
56
57                  #\x #\X #\*
58
59                  (copy-seq "foo") (copy-seq "foobar") (copy-seq "foobarbaz")
60
61                  (copy-seq #*)
62                  (copy-seq #*0) (copy-seq #*1)
63                  (copy-seq #*00) (copy-seq #*10)
64                  (copy-seq #*01) (copy-seq #*11)
65                  (copy-seq #*10010) (copy-seq #*100101) (bit-not #*01101)
66                  (make-array 6 :fill-pointer 6
67                              :element-type 'bit :initial-contents #*100101)
68
69                  #'allocate-instance #'no-applicable-method))
70          (make-psxhash-extra-subtests ()
71            (list (copy-seq "")
72                  (copy-seq #*)
73                  (copy-seq #())
74                  (copy-seq ())
75                  (copy-seq '(()))
76                  (copy-seq #(()))
77                  (copy-seq '(#()))
78                  (make-array 3 :fill-pointer 0)
79                  (make-array 7 :fill-pointer 0 :element-type 'bit)
80                  (make-array 8 :fill-pointer 0 :element-type 'character)
81                  (vector (cons 1 0) (cons 0 0))
82                  (vector (cons 0 1) (cons 0 0))
83                  (vector (cons 0 0) (cons 1 0))
84                  (vector (cons 0 0) (cons 0 1))
85                  (vector (cons 1 0) (cons 0 0))
86                  (vector (cons 0 1) (cons 0 0))
87                  (vector (list 0 0) (cons 1 0))
88                  (vector (list 0 0) (list 0 1))
89                  (vector (vector 1 0) (list 0 0))
90                  (vector (vector 0 1) (list 0 0))
91                  (vector (vector 0 0) (list 1 0))
92                  (vector (vector 0 0) (list 0 1))
93                  (vector #*00 #*10)
94                  (vector (vector 0 0) (list 0 1.0d0))
95                  (vector (vector -0.0d0 0) (list 1.0 0))
96                  (vector 1 0 1 0)
97                  (vector 0 0 0)
98                  (copy-seq #*1010)
99                  (copy-seq #*000)
100                  (replace (make-array 101
101                                       :element-type 'bit
102                                       :fill-pointer 4)
103                           #*1010)
104                  (replace (make-array 14
105                                       :element-type '(unsigned-byte 8)
106                                       :fill-pointer 3)
107                           #*000)
108                  (replace (make-array 14
109                                       :element-type t
110                                       :fill-pointer 3)
111                           #*000)
112                  (copy-seq "abc")
113                  (copy-seq "ABC")
114                  (copy-seq "aBc")
115                  (copy-seq "abcc")
116                  (copy-seq "1001")
117                  'abc
118                  (vector #\a #\b #\c)
119                  (vector 'a 'b 'c)
120                  (vector "A" 'b 'c)
121                  (replace (make-array 14
122                                       :element-type 'character
123                                       :fill-pointer 3)
124                           "aBc")
125                  (replace (make-array 11
126                                       :element-type 'character
127                                       :fill-pointer 4)
128                           "1001")
129                  (replace (make-array 12
130                                       :element-type 'bit
131                                       :fill-pointer 4)
132                           #*1001)
133                  (replace (make-array 13
134                                       :element-type t
135                                       :fill-pointer 4)
136                           "1001")
137                  (replace (make-array 13
138                                       :element-type t
139                                       :fill-pointer 4)
140                           #*1001)
141                  ;; FIXME: What about multi-dimensional arrays, hmm?
142
143                  (make-hash-table)
144                  (make-hash-table :test 'equal)
145
146                  (make-foo)
147                  (make-bar)
148                  (make-bar :x (list 1))
149                  (make-bar :y (list 1))))
150          (t->boolean (x) (if x t nil)))
151     (let* (;; Note:
152            ;;   * The APPEND noise here is to help more strenuously test
153            ;;     not-EQ-but-EQUAL and not-EQ-but-EQUALP cases.
154            ;;   * It seems not to be worth the hassle testing SXHASH on
155            ;;     values whose structure isn't understood by EQUAL, since
156            ;;     we get too many false positives "SXHASHes are equal even
157            ;;     though values aren't EQUAL, what a crummy hash function!"
158            ;;     FIXME: Or am I misunderstanding the intent of the
159            ;;     the SXHASH specification? Perhaps SXHASH is supposed to
160            ;;     descend into the structure of objects even when EQUAL
161            ;;     doesn't, in order to avoid hashing together things which
162            ;;     are guaranteed not to be EQUAL? The definition of SXHASH
163            ;;     seems to leave this completely unspecified: should
164            ;;     "well-distributed" depend on substructure that EQUAL
165            ;;     ignores? For our internal hash tables, the stricter
166            ;;     descend-into-the-structure behavior might improve
167            ;;     performance even though it's not specified by ANSI. But
168            ;;     is it reasonable for users to expect it? Hmm..
169            (sxhash-tests (append (make-sxhash-subtests)
170                                  (make-sxhash-subtests)))
171            (psxhash-tests (append sxhash-tests
172                                   (make-psxhash-extra-subtests)
173                                   (make-psxhash-extra-subtests))))
174       ;; Check that SXHASH compiler transforms give the same results
175       ;; as the out-of-line version of SXHASH.
176       (let* ((fundef `(lambda ()
177                         (list ,@(mapcar (lambda (value)
178                                           `(sxhash ',value))
179                                         sxhash-tests))))
180              (fun (compile nil fundef)))
181         (assert (equal (funcall fun)
182                        (mapcar #'sxhash sxhash-tests))))
183       ;; Note: The tests for SXHASH-equality iff EQUAL and
184       ;; PSXHASH-equality iff EQUALP could fail because of an unlucky
185       ;; random collision. That's not very likely (since there are
186       ;; (EXPT 2 29) possible hash values and only on the order of 100
187       ;; test cases, so even with the birthday paradox a collision has
188       ;; probability only (/ (EXPT 100 2) (EXPT 2 29)), but it's
189       ;; probably worth checking if you are getting a mystifying error
190       ;; from this test. (SXHASH values and PSXHASH values don't
191       ;; change from run to run, so the random chance of bogus failure
192       ;; happens once every time the code is changed in such a way
193       ;; that the SXHASH distribution changes, not once every time the
194       ;; tests are run.)
195       (dolist (i sxhash-tests)
196         (declare (notinline funcall))
197         (unless (typep (funcall #'sxhash i) '(and fixnum unsigned-byte))
198           (error "bad SXHASH behavior for ~S" i))
199         (dolist (j sxhash-tests)
200           (unless (or (eq (t->boolean (equal i j))
201                           (t->boolean (= (sxhash i) (sxhash j))))
202                       (and (typep i 'number)
203                            (typep j 'number)
204                            (= i j)
205                            (subtypep (type-of i) (type-of j))
206                            (subtypep (type-of j) (type-of i))))
207             ;; (If you get a surprising failure here, maybe you were
208             ;; just very unlucky; see the notes above.)
209             (error "bad SXHASH behavior for ~S ~S" i j))))
210       (dolist (i psxhash-tests)
211         (unless (typep (sb-int:psxhash i) '(and fixnum unsigned-byte))
212           (error "bad PSXHASH behavior for ~S" i))
213         (dolist (j psxhash-tests)
214           (unless (eq (t->boolean (equalp i j))
215                       (t->boolean (= (sb-int:psxhash i) (sb-int:psxhash j))))
216             ;; (If you get a surprising failure here, maybe you were
217             ;; just very unlucky; see the notes above.)
218             (error "bad PSXHASH behavior for ~S ~S" i j))))
219       )))
220
221 ;;; As of sbcl-0.6.12.10, writing hash tables readably should work.
222 ;;; This isn't required by the ANSI standard, but it should be, since
223 ;;; it's well-defined useful behavior which ANSI prohibits the users
224 ;;; from implementing themselves. (ANSI says the users can't define
225 ;;; their own their own PRINT-OBJECT (HASH-TABLE T) methods, and they
226 ;;; can't even wiggle out of it by subclassing HASH-TABLE or STREAM.)
227 (let ((original-ht (make-hash-table :test 'equal :size 111))
228       (original-keys '(1 10 11 400030002 -100000000)))
229   (dolist (key original-keys)
230     (setf (gethash key original-ht)
231           (expt key 4)))
232   (let* ((written-ht (with-output-to-string (s)
233                        (write original-ht :stream s :readably t)))
234          (read-ht (with-input-from-string (s written-ht)
235                     (read s))))
236     (assert (= (hash-table-count read-ht)
237                (hash-table-count original-ht)
238                (length original-keys)))
239     (assert (eql (hash-table-test original-ht) (hash-table-test read-ht)))
240     (assert (eql (hash-table-size original-ht) (hash-table-size read-ht)))
241     (dolist (key original-keys)
242       (assert (eql (gethash key read-ht)
243                    (gethash key original-ht))))))
244
245 ;;; NIL is both SYMBOL and LIST
246 (dolist (fun '(sxhash sb-impl::psxhash))
247   (assert (= (eval `(,fun nil))
248              (funcall fun nil)
249              (funcall (compile nil `(lambda (x)
250                                       (declare (symbol x))
251                                       (,fun x)))
252                       nil)
253              (funcall (compile nil `(lambda (x)
254                                       (declare (list x))
255                                       (,fun x)))
256                       nil)
257              (funcall (compile nil `(lambda (x)
258                                       (declare (null x))
259                                       (,fun x)))
260                       nil))))
261
262 ;;; This test works reliably on non-conservative platforms and
263 ;;; somewhat reliably on conservative platforms with threads.
264 #+(or (not (or x86 x86-64)) sb-thread)
265 (progn
266
267 (defparameter *ht* nil)
268
269 (defvar *cons-here*)
270
271 (declaim (notinline args))
272 (defun take (&rest args)
273   (declare (ignore args)))
274
275 (defmacro alloc (&body body)
276   "Execute BODY and try to reduce the chance of leaking a conservative root."
277   #-sb-thread
278   `(multiple-value-prog1
279        (progn ,@body)
280      (loop repeat 20000 do (setq *cons-here* (cons nil nil)))
281      ;; KLUDGE: Clean the argument passing regs.
282      (apply #'take (loop repeat 36 collect #'cons)))
283   #+sb-thread
284   (let ((values (gensym))
285         (sem (gensym)))
286     `(let ((,sem (sb-thread::make-semaphore))
287            ,values)
288        (sb-thread:make-thread (lambda ()
289                                 (setq ,values
290                                       (multiple-value-list (progn ,@body)))
291                                 (sb-thread::signal-semaphore ,sem)))
292        (sb-thread::wait-on-semaphore ,sem)
293        (values-list ,values))))
294
295 (with-test (:name (:hash-table :weakness :eql :numbers))
296   (flet ((random-number ()
297            (random 1000)))
298     (loop for weakness in '(nil :key :value :key-and-value :key-or-value) do
299           (let* ((ht (make-hash-table :weakness weakness))
300                  (n (alloc (loop repeat 1000
301                                  count (let ((key (random-number)))
302                                          (if (gethash key ht)
303                                              (setf (gethash key ht)
304                                                    (random-number))))))))
305             (gc :full t)
306             (gc :full t)
307             (assert (= n (hash-table-count ht)))))))
308
309 (defun add-removable-stuff (ht &key (n 100) (size 10))
310   (flet ((unique-object ()
311            (make-array size :fill-pointer 0)))
312     (loop for i below n do
313           (multiple-value-bind (key value)
314               (ecase (hash-table-weakness ht)
315                 ((:key) (values (unique-object) i))
316                 ((:value) (values i (unique-object)))
317                 ((:key-and-value)
318                  (if (zerop (random 2))
319                      (values (unique-object) i)
320                      (values i (unique-object))))
321                 ((:key-or-value)
322                  (values (unique-object) (unique-object))))
323             (setf (gethash key ht) value)))
324     (values)))
325
326 (defun print-ht (ht &optional (stream t))
327   (format stream "Weakness: ~S~%" (sb-impl::hash-table-weakness ht))
328   (format stream "Table: ~S~%" (sb-impl::hash-table-table ht))
329   (format stream "Next: ~S~%" (sb-impl::hash-table-next-vector ht))
330   (format stream "Index: ~S~%" (sb-impl::hash-table-index-vector ht))
331   (format stream "Hash: ~S~%" (sb-impl::hash-table-hash-vector ht))
332   (force-output stream))
333
334 (with-test (:name (:hash-table :weakness :removal))
335   (loop for test in '(eq eql equal equalp) do
336         (format t "test: ~A~%" test)
337         (loop for weakness in '(:key :value :key-and-value :key-or-value)
338               do
339               (format t "weakness: ~A~%" weakness)
340               (let ((ht (make-hash-table :test 'equal :weakness weakness)))
341                 (alloc (add-removable-stuff ht :n 117 :size 1))
342                 (loop for i upfrom 0
343                       do (format t "~A. count: ~A~%" i (hash-table-count ht))
344                       (force-output)
345                       until (zerop (hash-table-count ht))
346                       do
347                       (when (= i 10)
348                         (print-ht ht)
349                         #-(or x86 x86-64)
350                         (assert nil)
351                         ;; With conservative gc the test may not be
352                         ;; bullet-proof so it's not an outright
353                         ;; failure but a warning.
354                         #+(or x86 x86-64)
355                         (progn
356                           (warn "Weak hash removal test failed for weakness ~A"
357                                 weakness)
358                           (return)))
359                       (gc :full t))))))
360
361 (with-test (:name (:hash-table :weakness :string-interning))
362   (let ((ht (make-hash-table :test 'equal :weakness :key))
363         (s "a"))
364     (setf (gethash s ht) s)
365     (assert (eq (gethash s ht) s))
366     (assert (eq (gethash (copy-seq s) ht) s))))
367
368 ;;; see if hash_vector is not written when there is none ...
369 (with-test (:name (:hash-table :weakness :eq))
370   (loop repeat 10 do
371         (let ((index (random 2000)))
372           (let ((first (+ most-positive-fixnum (mod (* index 31) 9)))
373                 (n 50000))
374             (let ((hash-table (make-hash-table :weakness :key :test 'eq)))
375               (dotimes (i n)
376                 (setf (gethash (+ first i) hash-table) i))
377               hash-table)))))
378
379 ;; used to crash in gc
380 (with-test (:name (:hash-table :weakness :keep))
381   (loop repeat 2 do
382         (let ((h1 (make-hash-table :weakness :key :test #'equal))
383               (keep ()))
384           (loop for i from 0 to 1000
385                 for key = i
386                 for value = (make-array 10000 :fill-pointer 0)
387                 do
388                 (push value keep)
389                 (setf (gethash key h1) value))
390           (sb-ext:gc :full t))))
391
392 )
393
394 ;;; success