FIND / POSITION on lists does not signal bounding-indices-bad-error

[Attila Lendvai]

 TEST> (count :foo '(1 2 3 :foo) :start 4 :end 0)
 ; Evaluation aborted

 TEST> (find :foo '(1 2 3 :foo) :start 4 :end 0)
 NIL

 TEST> (position :foo '(1 2 3 :foo) :start 4 :end 0)
 NIL

as reported by Tobias C. Rittweiler on sbcl-devel.

[Jorge Tavares (jorgetavares)]

Hi,

I send in attach a patch that fixes this issue. I've tested with some examples and it works as required (unless I forgot some special case). In short, the macrolet in src/compiler/seqtran.lisp for these functions was just checking the indices in the result part of dolist. This allowed the error to occur since it did not catch all the possibilities. The patch makes the indices check before the dolist is executed.

This is the first time I've looked at the SBCL source code and made a patch. If I am doing something wrong or not the correct way, I apologize in advance.

Cheers,

[Nikodemus Siivola (nikodemus)]

Thanks for the patch! However:

+ (if (and end (or (> start end)
+ (> end (length sequence))))
+ (sequence-bounding-indices-bad-error
+ sequence start end)

is not good: LENGTH is O(N), and doesn't work at all on circular lists -- but FIND and POSITION should work fine on circular lists as long as the item _is_ in the list, and we'd rather not walk the entire list twice even if is is not circular.

The correct way to do this is to write the list walking using eg. DO instead of DOLIST, and check the bounds on the fly.

[Jorge Tavares (jorgetavares)]

Hi,
Hi,

Thanks for the quick reply and for pointing out the mistakes. I didn't think about all the issues.

I rewrote the fix using DO as suggested and removed the use of LENGTH. I start to check if :start is bigger than :end. The rest is done within the DO. However, the patch does not work with circular lists. This happens because to signal an error when :end is larger than the list length, we need to walk the entire list to compare both values (since we don't know the length at the beginning). I went to check the HyperSpec and it states that the sequences for FIND/POSITION must be proper sequences. As such, should FIND/POSITION really work with circular lists since these are improper lists? I also checked ClozureCL and FIND/POSITION do not work with circular lists (signals an error).

Well, I hope the patch is more useful now :-)

Cheers,

[Nikodemus Siivola (nikodemus)]

CLHS says "Should be prepared to signal an error of type type-error if sequence is not a proper sequence." which in then means (see 1.4.2) "This is similar to ``should be signaled'' except that it does not imply that `extra effort' has to be taken on the part of an operator to discover an erroneous situation if the normal action of that operator can be performed successfully with only `lazy' checking. An implementation is always permitted to signal an error, but even in safe code, it is only required to signal the error when failing to signal it might lead to incorrect results. In unsafe code, the consequences are undefined."

(Translation: I'm thinking about what we want to do.)

Thanks again for the patch!

[Nikodemus Siivola (nikodemus)]

In SBCL 1.0.36.24.