Steel Bank Common Lisp

find-if does not stop searching when item found

Reported by Alec Berryman on 2010-04-03
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Undecided
Unassigned

Bug Description

1.0.36.24 ("FIND/POSITION bounds checking on lists") introduced a regression: find-if now iterates through the entire list. Example:

* (find-if #'evenp '(1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 :foo))

debugger invoked on a SIMPLE-TYPE-ERROR in thread #<THREAD
                                                    "initial thread" RUNNING
                                                    {1002871AC1}>:
  Argument X is not a INTEGER: :FOO

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [ABORT] Exit debugger, returning to top level.

(SB-KERNEL:TWO-ARG-AND :FOO 1)
0]

Since 2 is even, the test function should never be run on :foo.

A fix and test case are attached. Someone will probably want to adjust the test case name.

I changed two tests from 1.0.36.24/bug 452008. If find or position locates the element before it realizes that :end is past the end of the list, I see no problem just returning that element: failing to check the bounds doesn't lead to an incorrect result.

Alec Berryman (alec-thened) wrote :
Nikodemus Siivola (nikodemus) wrote :

In SBCL 1.0.37.36, thanks for the patch!

(Though for FIND on lists you might want to make a performance comparison to MEMBER[-IF[-NOT]] -- since the predicate you use is unlikely to be inlined usefully for FIND-IF on a list anyways (can't know the type of objects to compare), the out-of-line %MEMBER-IF &co should be doing a pretty good job.)

Changed in sbcl:
status: New → Fix Committed
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers