bug in reference implementation of string-contains Matthias Radestock (10 Dec 2003 20:05 UTC)
Re: bug in reference implementation of string-contains Michael Sperber (09 Apr 2005 14:56 UTC)

Re: bug in reference implementation of string-contains Michael Sperber 09 Apr 2005 14:55 UTC

>>>>> "Matthias" == Matthias Radestock <xxxxxx@sorted.org> writes:

Matthias> Chris Double has found the following bug in the reference implementation:

Matthias> (string-contains "xabc" "ab")
Matthias> ; => 1 ;;good
Matthias> (string-contains "aabc" "ab")
Matthias> ; => #f ;;bad

Matthias> This behaviour has been observed on two systems using the reference
Matthias> implementation - SISC and scsh.

I finally figured out a fix:

Index: scheme/srfi/srfi-13.scm
===================================================================
*** scheme/srfi/srfi-13.scm	(revision 1140)
--- scheme/srfi/srfi-13.scm	(revision 1141)
***************
*** 1474,1499 ****
  	    ;; K = I + START -- it is the corresponding index into PATTERN.
  	    (let lp1 ((i 0) (j -1) (k start))
  	      (if (< i rvlen-1)
-
- 		  (let ((ck (string-ref pattern k)))
  		    ;; lp2 invariant:
  		    ;;   pat[(k-j) .. k-1] matches pat[start .. start+j-1]
  		    ;;   or j = -1.
  		    (let lp2 ((j j))
-
  		      (cond ((= j -1)
! 			     (let ((i1 (+ i 1)))
! 			       (vector-set! rv i1 (if (c= ck c0) -1 0))
  			       (lp1 i1 0 (+ k 1))))
-
  			    ;; pat[(k-j) .. k] matches pat[start..start+j].
! 			    ((c= ck (string-ref pattern (+ j start)))
  			     (let* ((i1 (+ 1 i))
  				    (j1 (+ 1 j)))
  			       (vector-set! rv i1 j1)
  			       (lp1 i1 j1 (+ k 1))))

! 			    (else (lp2 (vector-ref rv j))))))))))
        rv)))

--- 1473,1495 ----
  	    ;; K = I + START -- it is the corresponding index into PATTERN.
  	    (let lp1 ((i 0) (j -1) (k start))
  	      (if (< i rvlen-1)
  		  ;; lp2 invariant:
  		  ;;   pat[(k-j) .. k-1] matches pat[start .. start+j-1]
  		  ;;   or j = -1.
  		  (let lp2 ((j j))
  		    (cond ((= j -1)
! 			   (let ((i1 (+ 1 i)))
! 			     (if (not (c= (string-ref pattern (+ k 1)) c0))
! 				 (vector-set! rv i1 0))
  			     (lp1 i1 0 (+ k 1))))
  			  ;; pat[(k-j) .. k] matches pat[start..start+j].
! 			  ((c= (string-ref pattern k) (string-ref pattern (+ j start)))
  			   (let* ((i1 (+ 1 i))
  				  (j1 (+ 1 j)))
  			     (vector-set! rv i1 j1)
  			     (lp1 i1 j1 (+ k 1))))

! 			  (else (lp2 (vector-ref rv j)))))))))
        rv)))

--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla