[Sbcl-devel] [PATCH] Add improper list check to SEARCH transform

[nath...@desktopxpressions.com]

This patch partially addresses bug #1768652. It doesn't check start1 and end1 to determine if the bounded sequence is proper, so instead of an error, a warning is shown.

--------------------------------
From e71e769bad2608522bd122bd644e37674a2912be Mon Sep 17 00:00:00 2001
From: Nathaniel Berch <nath...@desktopxpressions.com>
Date: Sat, 12 May 2018 03:40:18 -0400
Subject: [PATCH] Add improper list check to SEARCH transform

---
 src/compiler/seqtran.lisp | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/src/compiler/seqtran.lisp b/src/compiler/seqtran.lisp
index 24ab87577..20785ddd9 100644
--- a/src/compiler/seqtran.lisp
+++ b/src/compiler/seqtran.lisp
@@ -1273,6 +1273,13 @@
 (deftransform search ((pattern text &key start1 start2 end1 end2 test test-not
                                key from-end)
                       ((constant-arg sequence) * &rest *))
+  ;;; FIXME: This does not check if the bounded sequence
+  ;;; specified by start1 to end1 is proper.
+  (let ((pattern (lvar-value pattern)))
+    (when (and (listp pattern)
+               (not (sb!impl::proper-list-p pattern)))
+      (compiler-warn "~S is not a proper sequence." pattern)
+      (give-up-ir1-transform)))
   (if key
       (give-up-ir1-transform)
       (let* ((pattern (lvar-value pattern))
-- 
2.11.0

[Stas Boukarev]

That works, although abort-ir1-transform should be used instead, but I paused fixing the improper list tickets because a better solution is needed. The one that involves specifying in fndb that an argument should be proper, which would be checked for any combination, whether it has a transform that breaks down on improper lists or not.

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot_______________________________________________
Sbcl-devel mailing list
Sbcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel

[Christophe Rhodes]

nath...@desktopxpressions.com writes:

> This patch partially addresses bug #1768652. It doesn't check start1
> and end1 to determine if the bounded sequence is proper, so instead of
> an error, a warning is shown.

I wouldn't mind taking a patch like this, as a stopgap, while Stas'
better solution is found.

I think you'd need to address the FIXME; this transform only actually
does anything if :start1 and :end1 are known at compile-time, so it
should be possible to rearrange things to do that check. You could use
LIST-OF-LENGTH-AT-LEAST-P or SEQUENCE-OF-LENGTH-AT-LEAST-P to perform
that check once you know the value of end1. (and PROPER-LIST-P, if END1
is null).

The other thing that the patch needs is: tests! Finding somewhere to
add the test case from the bug, and probably other tests to check the
cases you have fixed along the path. (Since this is a compiler bug more
than a correctness bug, probably one of the tests/compiler* files is an
appropriate place.

Cheers,

Christophe

[Jan Moringen]

On Sat, 2018-05-12 at 11:56 +0100, Christophe Rhodes wrote:

> Finding somewhere to
> add the test case from the bug, and probably other tests to check the
> cases you have fixed along the path. (Since this is a compiler bug more
> than a correctness bug, probably one of the tests/compiler* files is an
> appropriate place.

In addition, the output of the find-tests.sh script can provide some
hints:

$ sh find-tests.sh search
WARNING: Skipped 13 WITH-TEST forms
seq.pure.lisp: (SEARCH :EMPTY-SEQ)
seq.pure.lisp: (SEARCH :TRANSFORM-NOTES)
seq.pure.lisp: (SEARCH :SINGLETON-TRANSFORM)

$ sh find-tests.sh --fuzzy search
WARNING: Skipped 13 WITH-TEST forms
bad-code.pure.lisp: :SEARCH-TRANSFORM-BAD-INDEX
seq.pure.lisp: (SEARCH :EMPTY-SEQ)
seq.pure.lisp: (SEARCH :TRANSFORM-NOTES)
seq.pure.lisp: (SEARCH :SINGLETON-TRANSFORM)

Kind regards,
Jan

[nath...@desktopxpressions.com]

I've address some of the issues and attached a revision of the patch.

Right now, SEARCH doesn't work when either sequence is improper. For example, (search '(1 . 2) '(1 2 3 4) :end1 1) fails with a type error of "the value 2 is not of type list". I believe this is due to DEFINE-SEQUENCE-TRAVERSER evaluating length, length1, and length2 before they are actually needed. I'm not sure if this is a bug or intended behavior; though if it is intended behavior, a warning would need to be provided regardless of the end1 bound.

----------------

From bf121ad87143301330cc1cd4959ab7f20efbf248 Mon Sep 17 00:00:00 2001

From: Nathaniel Berch <nath...@desktopxpressions.com>
Date: Sat, 12 May 2018 03:40:18 -0400
Subject: [PATCH] Add improper list check to SEARCH transform

This addresses lp#1768652
---
 src/compiler/seqtran.lisp |  7 +++++++
 tests/seq.pure.lisp       | 29 +++++++++++++++++++++++++++++
 2 files changed, 36 insertions(+)

diff --git a/src/compiler/seqtran.lisp b/src/compiler/seqtran.lisp
index 24ab87577..6fc0024e4 100644

--- a/src/compiler/seqtran.lisp
+++ b/src/compiler/seqtran.lisp
@@ -1273,6 +1273,13 @@
 (deftransform search ((pattern text &key start1 start2 end1 end2 test test-not
                                key from-end)
                       ((constant-arg sequence) * &rest *))

+  (let ((pattern (lvar-value pattern))
+        (end1 (when (constant-lvar-p end1)
+                (lvar-value end1))))

+    (when (and (listp pattern)

+               (not (proper-list-p pattern))
+               (not (and end1 (list-of-length-at-least-p pattern end1))))
+      (abort-ir1-transform "~S is not a proper sequence." pattern)))

   (if key
       (give-up-ir1-transform)
       (let* ((pattern (lvar-value pattern))

diff --git a/tests/seq.pure.lisp b/tests/seq.pure.lisp
index d554a376a..389a187f6 100644
--- a/tests/seq.pure.lisp
+++ b/tests/seq.pure.lisp
@@ -458,3 +458,32 @@
               (count 1 x)))))
     (ctu:assert-no-consing (funcall f #(1 2 3 4)))
     (ctu:assert-no-consing (funcall f '(1 2 3 4)))))
+
+(with-test (:name (search :improper-list-transformation-warning))
+  ;; A warning is provided when
+  ;; an unbounded improper list is used.
+  (multiple-value-bind (func failure-p warnings)
+      (checked-compile
+       `(lambda (x) (search '(1 . 2) x))
+       :allow-warnings t)
+    (declare (ignore func failure-p))
+    (assert (some #'(lambda (warning)
+                      (search "is not a proper sequence." (princ-to-string warning)))
+                 warnings)))
+  ;; A warning is provided when
+  ;; an improper subsequence of an
+  ;; improper list is used.
+  (multiple-value-bind (func failure-p warnings)
+      (checked-compile
+       `(lambda (x) (search '(1 . 2) x :end1 2))
+       :allow-warnings t)
+    (declare (ignore func failure-p))
+    (assert (some #'(lambda (warning)
+                      (search "is not a proper sequence." (princ-to-string warning)))
+                  warnings)))
+  ;; A warning isn't provided when
+  ;; a proper subsequence of an improper list is used.
+  (multiple-value-bind (func failure-p)
+      (checked-compile
+       `(lambda (x) (search '(1 . 2) x :end1 0)))
+    (declare (ignore func failure-p))))
-- 
2.11.0

 

[Christophe Rhodes]

nath...@desktopxpressions.com writes:

> I've address some of the issues and attached a revision of the patch.
>
> Right now, SEARCH doesn't work when either sequence is improper. For
> example, (search '(1 . 2) '(1 2 3 4) :end1 1) fails with a type error
> of "the value 2 is not of type list". I believe this is due to
> DEFINE-SEQUENCE-TRAVERSER evaluating length, length1, and length2
> before they are actually needed. I'm not sure if this is a bug or
> intended behavior; though if it is intended behavior, a warning would
> need to be provided regardless of the end1 bound.

It's probably intended behaviour, in that CLHS 17.1.1 mandates that
list arguments to sequence functions should be proper lists,
independently of bounding index designators -- and certainly the easy
way of checking that the bounding indices are valid is to check them
against the lengths of sequence arguments.

We could save some time in sequence functions by using this requirement,
and checking only the list structure up to any explicitly-provided end,
but that's not really the SBCL way, which checks somewhat pedantically.
You might argue that this is wasted work, but probably no-one is using
sequence functions like SEARCH on lists and expecting them to be fast
anyway...

Cheers,

Christophe