X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=tests%2Fseq.impure.lisp;h=2570a734cd35e690d09bf79239063f1240b33862;hb=dc4be57ff0baeee18d43fbee1bfc1af4af50e522;hp=b298f7872d7bc69051125799961fdd11a9c9f294;hpb=58084279740fc96c6ffcd14e86dca73b71b7c288;p=sbcl.git diff --git a/tests/seq.impure.lisp b/tests/seq.impure.lisp index b298f78..2570a73 100644 --- a/tests/seq.impure.lisp +++ b/tests/seq.impure.lisp @@ -13,10 +13,12 @@ ;;;; absolutely no warranty. See the COPYING and CREDITS files for ;;;; more information. -(in-package :cl-user) - (load "assertoid.lisp") -(use-package "ASSERTOID") + +(defpackage :seq-test + (:use :cl :assertoid)) + +(in-package :seq-test) ;;; helper functions for exercising SEQUENCE code on data of many ;;; specialized types, and in many different optimization scenarios @@ -299,31 +301,41 @@ ;; MAKE-SEQUENCE (assert-type-error (make-sequence 'cons 0)) (assert-type-error (make-sequence 'null 1)) + (assert-type-error (make-sequence '(cons t null) 0)) + (assert-type-error (make-sequence '(cons t null) 2)) ;; KLUDGE: I'm not certain that this test actually tests for what ;; it should test, in that the type deriver and optimizers might ;; be too smart for the good of an exhaustive test system. ;; However, it makes me feel good. -- CSR, 2002-10-18 (assert (null (make-sequence 'null 0))) (assert (= (length (make-sequence 'cons 3)) 3)) + (assert (= (length (make-sequence '(cons t null) 1)) 1)) ;; and NIL is not a valid type for MAKE-SEQUENCE (assert-type-error (make-sequence 'nil 0)) ;; COERCE (assert-type-error (coerce #(1) 'null)) (assert-type-error (coerce #() 'cons)) + (assert-type-error (coerce #() '(cons t null))) + (assert-type-error (coerce #(1 2) '(cons t null))) (assert (null (coerce #() 'null))) (assert (= (length (coerce #(1) 'cons)) 1)) + (assert (= (length (coerce #(1) '(cons t null))) 1)) (assert-type-error (coerce #() 'nil)) ;; MERGE (assert-type-error (merge 'null '(1 3) '(2 4) '<)) (assert-type-error (merge 'cons () () '<)) (assert (null (merge 'null () () '<))) (assert (= (length (merge 'cons '(1 3) '(2 4) '<)) 4)) + (assert (= (length (merge '(cons t (cons t (cons t (cons t null)))) + '(1 3) '(2 4) '<)) 4)) (assert-type-error (merge 'nil () () '<)) ;; CONCATENATE (assert-type-error (concatenate 'null '(1) "2")) (assert-type-error (concatenate 'cons #() ())) + (assert-type-error (concatenate '(cons t null) #(1 2 3) #(4 5 6))) (assert (null (concatenate 'null () #()))) (assert (= (length (concatenate 'cons #() '(1) "2 3")) 4)) + (assert (= (length (concatenate '(cons t cons) '(1) "34")) 3)) (assert-type-error (concatenate 'nil '(3))) ;; FIXME: tests for MAP to come when some brave soul implements ;; the analogous type checking for MAP/%MAP. @@ -339,29 +351,56 @@ (declare (optimize (safety 3))) (assert (raises-error? (elt (list 1 2 3) 3) type-error))) +;;; confusion in the refactoring led to this signalling an unbound +;;; variable, not a type error. +(defun svrefalike (x) + (svref x 0)) +(assert (raises-error? (svrefalike #*0) type-error)) + ;;; checks for uniform bounding index handling under SAFETY 3 code. ;;; ;;; KLUDGE: not all in one big form because that causes SBCL to spend ;;; an absolute age trying to compile it. (defmacro sequence-bounding-indices-test (&body body) - `(locally + `(progn + (locally ;; See Issues 332 [and 333(!)] in the CLHS (declare (optimize (safety 3))) (let ((string (make-array 10 :fill-pointer 5 :initial-element #\a :element-type 'base-char))) + ,(car body) + (format t "... BASE-CHAR") + (finish-output) + (flet ((reset () + (setf (fill-pointer string) 10) + (fill string #\a) + (setf (fill-pointer string) 5))) + (declare (ignorable #'reset)) + ,@(cdr body)))) + (locally + ;; See Issues 332 [and 333(!)] in the CLHS + (declare (optimize (safety 3))) + (let ((string (make-array 10 + :fill-pointer 5 + :initial-element #\a + :element-type 'character))) + ,(car body) + (format t "... CHARACTER") + (finish-output) (flet ((reset () (setf (fill-pointer string) 10) (fill string #\a) (setf (fill-pointer string) 5))) (declare (ignorable #'reset)) - ,@body)))) + ,@(cdr body)))))) + (declaim (notinline opaque-identity)) (defun opaque-identity (x) x) ;;; Accessor SUBSEQ (sequence-bounding-indices-test - (format t "~&/Accessor SUBSEQ~%") + (format t "~&/Accessor SUBSEQ") (assert (string= (subseq string 0 5) "aaaaa")) (assert (raises-error? (subseq string 0 6))) (assert (raises-error? (subseq string (opaque-identity -1) 5))) @@ -377,7 +416,7 @@ ;;; Function COUNT, COUNT-IF, COUNT-IF-NOT (sequence-bounding-indices-test - (format t "~&/Function COUNT, COUNT-IF, COUNT-IF-NOT") + (format t "~&/Function COUNT, COUNT-IF, COUNT-IF-NOT") (assert (= (count #\a string :start 0 :end nil) 5)) (assert (= (count #\a string :start 0 :end 5) 5)) (assert (raises-error? (count #\a string :start 0 :end 6))) @@ -407,7 +446,7 @@ ;;; Function FILL (sequence-bounding-indices-test - (format t "~&/Function FILL~%") + (format t "~&/Function FILL") (assert (string= (fill string #\b :start 0 :end 5) "bbbbb")) (assert (string= (fill string #\c :start 0 :end nil) "ccccc")) (assert (raises-error? (fill string #\d :start 0 :end 6))) @@ -417,7 +456,7 @@ ;;; Function FIND, FIND-IF, FIND-IF-NOT (sequence-bounding-indices-test - (format t "~&/Function FIND, FIND-IF, FIND-IF-NOT~%") + (format t "~&/Function FIND, FIND-IF, FIND-IF-NOT") (assert (char= (find #\a string :start 0 :end nil) #\a)) (assert (char= (find #\a string :start 0 :end 5) #\a)) (assert (raises-error? (find #\a string :start 0 :end 6))) @@ -447,7 +486,7 @@ ;;; Function MISMATCH (sequence-bounding-indices-test - (format t "~&/Function MISMATCH~%") + (format t "~&/Function MISMATCH") (assert (null (mismatch string "aaaaa" :start1 0 :end1 nil))) (assert (= (mismatch "aaab" string :start2 0 :end2 4) 3)) (assert (raises-error? (mismatch "aaaaaa" string :start2 0 :end2 6))) @@ -457,7 +496,7 @@ ;;; Function PARSE-INTEGER (sequence-bounding-indices-test - (format t "~&/Function PARSE-INTEGER~%") + (format t "~&/Function PARSE-INTEGER") (setf (fill-pointer string) 10) (setf (subseq string 0 10) "1234567890") (setf (fill-pointer string) 5) @@ -470,7 +509,7 @@ ;;; Function PARSE-NAMESTRING (sequence-bounding-indices-test - (format t "~&/Function PARSE-NAMESTRING~%") + (format t "~&/Function PARSE-NAMESTRING") (setf (fill-pointer string) 10) (setf (subseq string 0 10) "/dev/ /tmp") (setf (fill-pointer string) 5) @@ -493,7 +532,8 @@ ;;; Function POSITION, POSITION-IF, POSITION-IF-NOT (sequence-bounding-indices-test - (format t "~&/Function POSITION, POSITION-IF, POSITION-IF-NOT~%") + (format t "~&/Function POSITION, POSITION-IF, POSITION-IF-NOT") + (assert (= (position #\a string :start 0 :end nil) 0)) (assert (= (position #\a string :start 0 :end 5) 0)) (assert (raises-error? (position #\a string :start 0 :end 6))) @@ -523,7 +563,7 @@ ;;; Function READ-FROM-STRING (sequence-bounding-indices-test - (format t "~&/Function READ-FROM-STRING~%") + (format t "~&/Function READ-FROM-STRING") (setf (subseq string 0 5) "(a b)") (assert (equal (read-from-string string nil nil :start 0 :end 5) '(a b))) (assert (equal (read-from-string string nil nil :start 0 :end nil) '(a b))) @@ -534,7 +574,7 @@ ;;; Function REDUCE (sequence-bounding-indices-test - (format t "~&/Function REDUCE~%") + (format t "~&/Function REDUCE") (setf (subseq string 0 5) "abcde") (assert (equal (reduce #'list* string :from-end t :start 0 :end nil) '(#\a #\b #\c #\d . #\e))) @@ -548,7 +588,7 @@ ;;; Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, ;;; DELETE-IF-NOT (sequence-bounding-indices-test - (format t "~&/Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, ...~%") + (format t "~&/Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, ...") (assert (equal (remove #\a string :start 0 :end nil) "")) (assert (equal (remove #\a string :start 0 :end 5) "")) (assert (raises-error? (remove #\a string :start 0 :end 6))) @@ -578,7 +618,7 @@ (assert (raises-error? (remove-if-not #'alpha-char-p string :start 6 :end 9)))) (sequence-bounding-indices-test - (format t "~&/... DELETE, DELETE-IF, DELETE-IF-NOT") + (format t "~&/... DELETE, DELETE-IF, DELETE-IF-NOT") (assert (equal (delete #\a string :start 0 :end nil) "")) (reset) (assert (equal (delete #\a string :start 0 :end 5) "")) @@ -627,7 +667,7 @@ ;;; Function REMOVE-DUPLICATES, DELETE-DUPLICATES (sequence-bounding-indices-test - (format t "~&/Function REMOVE-DUPLICATES, DELETE-DUPLICATES~%") + (format t "~&/Function REMOVE-DUPLICATES, DELETE-DUPLICATES") (assert (string= (remove-duplicates string :start 0 :end 5) "a")) (assert (string= (remove-duplicates string :start 0 :end nil) "a")) (assert (raises-error? (remove-duplicates string :start 0 :end 6))) @@ -648,7 +688,7 @@ ;;; Function REPLACE (sequence-bounding-indices-test - (format t "~&/Function REPLACE~%") + (format t "~&/Function REPLACE") (assert (string= (replace string "bbbbb" :start1 0 :end1 5) "bbbbb")) (assert (string= (replace (copy-seq "ccccc") string @@ -660,7 +700,7 @@ ;;; Function SEARCH (sequence-bounding-indices-test - (format t "~&/Function SEARCH~%") + (format t "~&/Function SEARCH") (assert (= (search "aa" string :start2 0 :end2 5) 0)) (assert (null (search string "aa" :start1 0 :end2 nil))) (assert (raises-error? (search "aa" string :start2 0 :end2 6))) @@ -678,11 +718,11 @@ (assert (raises-error? (,fn string :start 6 :end 9))))) (sequence-bounding-indices-test - (format t "~&/Function STRING-UPCASE, STRING-DOWNCASE, STRING-CAPITALIZE, ...~%") + (format t "~&/Function STRING-UPCASE, STRING-DOWNCASE, STRING-CAPITALIZE, ...") (string-case-frob string-upcase) (string-case-frob string-downcase) (string-case-frob string-capitalize) - (format t "~&/... NSTRING-UPCASE, NSTRING-DOWNCASE, NSTRING-CAPITALIZE~%") + (format t "~&/... NSTRING-UPCASE, NSTRING-DOWNCASE, NSTRING-CAPITALIZE") (string-case-frob nstring-upcase) (string-case-frob nstring-downcase) (string-case-frob nstring-capitalize)) @@ -710,12 +750,12 @@ (string-predicate-frob string<=) (string-predicate-frob string>=)) (sequence-bounding-indices-test - (format t "~&/... STRING-EQUAL, STRING-NOT-EQUAL, STRING-LESSP, ...~%") + (format t "~&/... STRING-EQUAL, STRING-NOT-EQUAL, STRING-LESSP, ...") (string-predicate-frob string-equal) (string-predicate-frob string-not-equal) (string-predicate-frob string-lessp)) (sequence-bounding-indices-test - (format t "~&/... STRING-GREATERP, STRING-NOT-GREATERP, STRING-NOT-LESSP~%") + (format t "~&/... STRING-GREATERP, STRING-NOT-GREATERP, STRING-NOT-LESSP") (string-predicate-frob string-greaterp) (string-predicate-frob string-not-greaterp) (string-predicate-frob string-not-lessp)) @@ -723,7 +763,7 @@ ;;; Function SUBSTITUTE, SUBSTITUTE-IF, SUBSTITUTE-IF-NOT, ;;; NSUBSTITUTE, NSUBSTITUTE-IF, NSUBSTITUTE-IF-NOT (sequence-bounding-indices-test - (format t "~&/Function SUBSTITUTE, SUBSTITUTE-IF, SUBSTITUTE-IF-NOT, ...~%") + (format t "~&/Function SUBSTITUTE, SUBSTITUTE-IF, SUBSTITUTE-IF-NOT, ...") (assert (string= (substitute #\b #\a string :start 0 :end 5) "bbbbb")) (assert (string= (substitute #\c #\a string :start 0 :end nil) "ccccc")) @@ -760,7 +800,7 @@ (assert (raises-error? (substitute-if-not #\b #'alpha-char-p string :start 6 :end 9)))) (sequence-bounding-indices-test - (format t "~&/... NSUBSTITUTE, NSUBSTITUTE-IF, NSUBSTITUTE-IF-NOT~%") + (format t "~&/... NSUBSTITUTE, NSUBSTITUTE-IF, NSUBSTITUTE-IF-NOT") (assert (string= (nsubstitute #\b #\a string :start 0 :end 5) "bbbbb")) (reset) (assert (string= (nsubstitute #\c #\a string :start 0 :end nil) @@ -815,7 +855,7 @@ :start 6 :end 9)))) ;;; Function WRITE-STRING, WRITE-LINE (sequence-bounding-indices-test - (format t "~&/Function WRITE-STRING, WRITE-LINE~%") + (format t "~&/Function WRITE-STRING, WRITE-LINE") (write-string string *standard-output* :start 0 :end 5) (write-string string *standard-output* :start 0 :end nil) (assert (raises-error? (write-string string *standard-output* @@ -839,7 +879,7 @@ ;;; Macro WITH-INPUT-FROM-STRING (sequence-bounding-indices-test - (format t "~&/Macro WITH-INPUT-FROM-STRING~%") + (format t "~&/Macro WITH-INPUT-FROM-STRING") (with-input-from-string (s string :start 0 :end 5) (assert (char= (read-char s) #\a))) (with-input-from-string (s string :start 0 :end nil) @@ -857,5 +897,101 @@ (with-input-from-string (s string :start 6 :end 9) (read-char s))))) +;;; testing bit-bashing according to _The Practice of Programming_ +(defun fill-bytes-for-testing (bitsize) + "Return a list of 'bytes' of type (MOD BITSIZE)." + (remove-duplicates (list 0 + (1- (ash 1 (1- bitsize))) + (ash 1 (1- bitsize)) + (1- (ash 1 bitsize))))) + +(defun fill-with-known-value (value size &rest vectors) + (dolist (vec vectors) + (dotimes (i size) + (setf (aref vec i) value)))) + +(defun collect-fill-amounts (n-power) + (remove-duplicates + (loop for i from 0 upto n-power + collect (1- (expt 2 i)) + collect (expt 2 i) + collect (1+ (expt 2 i))))) + +(defun test-fill-bashing (bitsize padding-amount n-power) + (let* ((size (+ (* padding-amount 2) (expt 2 n-power) (* padding-amount 2))) + (standard (make-array size :element-type `(unsigned-byte ,bitsize))) + (bashed (make-array size :element-type `(unsigned-byte ,bitsize))) + (fill-amounts (collect-fill-amounts n-power)) + (bash-function (intern (format nil "UB~A-BASH-FILL" bitsize) + (find-package "SB-KERNEL")))) + (loop for offset from padding-amount below (* 2 padding-amount) do + (dolist (c (fill-bytes-for-testing bitsize)) + (dolist (n fill-amounts) + (fill-with-known-value (mod (lognot c) (ash 1 bitsize)) n + standard bashed) + ;; fill vectors + ;; a) the standard slow way + (fill standard c :start offset :end (+ offset n)) + ;; b) the blazingly fast way + (let ((value (loop for i from 0 by bitsize + until (= i sb-vm:n-word-bits) + sum (ash c i)))) + (funcall bash-function value bashed offset n)) + ;; check for errors + (when (mismatch standard bashed) + (format t "Test with offset ~A, fill ~A and length ~A failed.~%" + offset c n) + (format t "Mismatch: ~A ~A~%" + (subseq standard 0 (+ offset n 1)) + (subseq bashed 0 (+ offset n 1))) + (return-from test-fill-bashing nil)))) + finally (return t)))) + +(defun test-copy-bashing (bitsize padding-amount n-power) + (let* ((size (+ (* padding-amount 2) (expt 2 n-power) (* padding-amount 2))) + (standard-dst (make-array size :element-type `(unsigned-byte ,bitsize))) + (bashed-dst (make-array size :element-type `(unsigned-byte ,bitsize))) + (source (make-array size :element-type `(unsigned-byte ,bitsize))) + (fill-amounts (collect-fill-amounts n-power)) + (bash-function (intern (format nil "UB~A-BASH-COPY" bitsize) + (find-package "SB-KERNEL")))) + (do ((source-offset padding-amount (1+ source-offset))) + ((>= source-offset (* padding-amount 2)) + ;; success! + t) + (do ((target-offset padding-amount (1+ target-offset))) + ((>= target-offset (* padding-amount 2))) + (dolist (c (fill-bytes-for-testing bitsize)) + (dolist (n fill-amounts) + (fill-with-known-value (mod (lognot c) (ash 1 bitsize)) size + source standard-dst bashed-dst) + ;; fill with test data + (fill source c :start source-offset :end (+ source-offset n)) + ;; copy filled test data to test vectors + ;; a) the slow way + (replace standard-dst source + :start1 target-offset :end1 (+ target-offset n) + :start2 source-offset :end2 (+ source-offset n)) + ;; b) the blazingly fast way + (funcall bash-function source source-offset + bashed-dst target-offset n) + ;; check for errors + (when (mismatch standard-dst bashed-dst) + (format t "Test with target-offset ~A, source-offset ~A, fill ~A, and length ~A failed.~%" + target-offset source-offset c n) + (format t "Mismatch:~% correct ~A~% actual ~A~%" + standard-dst + bashed-dst) + (return-from test-copy-bashing nil)))))))) + +(loop for i = 1 then (* i 2) do + ;; the bare '32' here is fairly arbitrary; '8' provides a good + ;; range of lengths over which to fill and copy, which should tease + ;; out most errors in the code (if any exist). (It also makes this + ;; part of the test suite finish reasonably quickly.) + (assert (test-fill-bashing i 32 8)) + (assert (test-copy-bashing i 32 8)) + until (= i sb-vm:n-word-bits)) + ;;; success -(quit :unix-status 104) +(sb-ext:quit :unix-status 104)