Subject: [clisp-list] regexp-exec filters too much

From: "Hoehle, Joerg-Cyril" <[email-masked]>
Date: Fri Apr 12 08:06:07 2002

Hi,

regexp-exec fails to correctly handle results of ()-grouping in
regular expressions, as in e.g.: b\(o\([hi]\)\|h\([a-z]\)\). This
affects OR (i.e. optional) groups.

2 Testcases (in .tst format):
(regexp:match-end (nth-value 2
 (regexp:match "\\(/[a-z]*\\)*\\([a-z]\\+\\)" "foo#bar") ))
3

The values returned by match should be:
#S(REGMATCH_T :RM_SO 0 :RM_EO 3) ;
NIL ; <- filtered (-1,-1): no path
#S(REGMATCH_T :RM_SO 0 :RM_EO 3)

But not
#S(REGMATCH_T :RM_SO 0 :RM_EO 3) ;
#S(REGMATCH_T :RM_SO 0 :RM_EO 3) ;
... !!!
as the positioning of groups, as documented by regexp, is broken.

(regexp:match-end (nth-value 2
 (regexp:match "\\(/[a-z]*\\)*\\([a-z]\\+\\)" "/path/to/foo#bar") ))
12
The returned values should be:
#S(REGMATCH_T :RM_SO 0 :RM_EO 12) ;
#S(REGMATCH_T :RM_SO 8 :RM_EO 11) ;
#S(REGMATCH_T :RM_SO 11 :RM_EO 12)

BTW, is it normal that the + must be escaped?

When reformatting the result array, regexp-exec contains a line:
   (delete-if #'minusp matches :key #'match-start)))
This is buggy, as it doesn't handle OR (or optional) expressions correctly.

I believe the intent was to remove *trailing* (-1;-1) pairs left from
the probably too large array that holds the results (always
NUM-MATCHES =10 elements).

However, even doing this is buggy, as without parsing the regex,
there's no way telling how many parentheses groups there are and so
how many array elements will be needed. Consider the pattern b\(ar\)*g:

;(rtest2 "b\\(ar\\)*g" "abg")
0 ;
#(#S(REGEXP::REGMATCH_T :RM_SO 1 :RM_EO 3)
  #S(REGEXP::REGMATCH_T :RM_SO -1 :RM_EO -1) ;<- normal, * matched nothing
  #S(REGEXP::REGMATCH_T :RM_SO -1 :RM_EO -1) ; 
  #S...
;(rtest "b\\(ar\\)*g" "abg")
#S(REGEXP::REGMATCH_T :RM_SO 1 :RM_EO 3)
 <- missing empty match indication as NTH-VALUE 1
The interface doesn't tell, but 2 of the array slots were needed.

Actually, the C interface can give the number of (). That's the re_nsub slot.

A 100% solution would have the FFI code call regexec with a variable
size array instead of being able to handle only at most 10 entries
(as typical for ancient C programming). This is not yet possible
in CLISP. The number of arguments would be determined by the structure
returned from regcomp() (or an extra FFI call).

Instead of having a fixed size
(def-c-call-out regexec
    (:arguments [...]
          (nmatch size_t)
          (pmatch (c-ptr (c-array regmatch_t #.num-matches)) :out)
          ... )
    (:return-type int))

We'd write
          (nmatch size_t)
          (pmatch (c-ptr (c-array regmatch_t is_size(nmatch))) :out)
and call via
 (regexec cpattern (cpattern->nsub cpattern)) -> array of size nsub

I don't know if variable size arrays will ever be implemented for the FFI.
That's "Worse is better" at work!

The bug has been there since day 1 of the regexp module (1996?), which
shows how much some regex functionality is used.

Proposed fix:
a) return positional NIL argument when submatch was not found
b) and always return NUM-MATCHES (10) values as interface doesn't tell
how many () groups the regex actually contains,
b2) or rely on multiple-value-bind NIL behaviour and filter trailing
NIL, so as not to always stupidly return 10 VALUES: if the programmer
requests a value of index larger than retured, s/he will get NIL as
well.
b3) "100% better solution": revisit interface so as to not stupidly
impose NUM-MATCH=10 but obtain number of actual groups via
regexp-compile. Be dynamic!

c) what should be the behaviour of MATCH-STRING be on a failed
optional match?
c1) leave code as is, don't call it on NIL match value.
c2) or return the empty string ""?

Fix a+b2) is appended. c1 means status quo.

Regards,
	Jörg Höhle

(in-package "REGEXP")

(defun regexp-exec (compiled-pattern string &key (start 0) (end nil))
  (assert (stringp string) (string)
          "~s: the second argument must be a string, not ~s"
          'regexp-exec string)
  (let* ((len (length string))
         (end (cond ((null end) len)
                    ((>= end len) len)
                    ((minusp end) (+ len end))
                    (t end)))
         ;; Prepare the string.
         (string
           (if (and (eql start 0) (eql end len))
             string
             (make-array (- end start)
                         :element-type 'character
                         :displaced-to string
                         :displaced-index-offset start))))
    (declare (string string))
    (multiple-value-bind (errcode matches)
        (regexec compiled-pattern string #.num-matches 0)
      ;; Compute return values.
      (if (zerop errcode)
        (values-list          ; the first value will be non-NIL
         (do ((n (position-if-not #'minusp matches :key #'match-start :from-end t) (1- n))
              (result '()))
             ((minusp n) result)
           (let ((match (svref matches n)))
             (push (cond ((= (match-start match) -1) nil)
                         ( t (unless (eql start 0)
                               (incf (match-start match) start)
                               (incf (match-end match) start))
                             match))
                   result))))
        nil))))

---

From: Sam Steingold <[email-masked]>
Date: Fri Apr 12 11:57:04 2002

> * In message <[email-masked]>
> * On the subject of "[clisp-list] regexp-exec filters too much"
> * Sent on Fri, 12 Apr 2002 17:04:56 +0200
> * Honorable "Hoehle, Joerg-Cyril" <[email-masked]> writes:
>

I thought you were working on that!

> Fix a+b2) is appended. c1 means status quo.

thanks.  are you sure you b3 is out of reach?

-- 
Sam Steingold (http://www.podval.org/~sds) running RedHat7.2 GNU/Linux
Read, think and remember! <http://www.iris.org.il> <http://www.memri.org/>
<http://www.palestine-central.com/> <http://www.mideasttruth.com/>
Stupidity, like virtue, is its own reward.