Re: Pattern matching on match-string groups #elisp #question

["Mattias Engdegård" <mattiase@acm.org>]

[-- Attachment #1: Type: text/plain, Size: 2612 bytes --]

27 feb. 2021 kl. 15.39 skrev Stefan Monnier <monnier@iro.umontreal.ca>:

> Nevertheless, I went ahead with this change (after remembering that
> wrapping the code in `ignore` should eliminate the extra warnings).

So where does that leave us with the rx pattern? There's still the interleaved match data problem, which I've tried to address below.

> It's clearly The Right Thing™.

Perhaps it is; a proposed diff is attached below which treats zero and one variable specially and uses a list followed by immediate destructuring for >1 variables. (By the way, using a backquote form to generate backquote forms is annoying.)

My guess is that a vector may be faster than a list if there are more than N elements, for some N.

>> My guess is that a vector may be faster than a list if there are more than N elements, for some N.
> 
> I'll let you benchmark it to determine the N.

I now have, and am sad to say that a list is always faster for any practical number of N (I didn't bother trying more than 30) although the difference narrows as N grows. This is despite the destructuring code becoming considerably bigger for lists (as we get a long chain of tests and branches) than for vectors. It all boils down to vector construction being more expensive than lists.

Maybe we should pack N>1 variables into N-1 cons cells by using the last cdr (improper list), but list* is no primitive so it may be a loss for N>M, for some M>2.

> currently `string-match-p` is ever so slightly
> slower than `string-match` and since we clobber the match data in other
> cases, we might as well clobber the match data in this case as well: any
> code which presumes the match data isn't affected by some other code
> which uses regular expressions is quite confused.

Right; I'm sticking to string-match for the time being.

> I don't think it's much more complicated than your current constant
> folding: when you see a let-binding of a variable to a *constructor*,
> stash that expression in your context as a "partially known constant"
> and then do the constant folding when you see a matching *destructor*.

Doable, but definitely not low-hanging fruit. Since pcase has made a dog's breakfast of the destructuring code it's not straightforward to recognise it as such in the optimiser. Efforts needed elsewhere first!

> go back to the last option it tried and accept it even though it failed
> to match.  It still sucks, but maybe it'll give someone else a better idea?

Sounds like pcase--dead-end would fit then, at least as an internal name.

Or pcase--Sherlock-Holmes.


[-- Attachment #2: rx-pcase-list-destructure.diff --]
[-- Type: application/octet-stream, Size: 2401 bytes --]

diff --git a/lisp/emacs-lisp/rx.el b/lisp/emacs-lisp/rx.el
index ffc21951b6..736758d01f 100644
--- a/lisp/emacs-lisp/rx.el
+++ b/lisp/emacs-lisp/rx.el
@@ -1436,17 +1436,31 @@ rx
                    introduced by a previous (let REF ...)
                    construct."
   (let* ((rx--pcase-vars nil)
-         (regexp (rx--to-expr (rx--pcase-transform (cons 'seq regexps)))))
+         (regexp (rx--to-expr (rx--pcase-transform (cons 'seq regexps))))
+         (nvars (length rx--pcase-vars)))
     `(and (pred stringp)
-          ;; `pcase-let' takes a match for granted and discards all unnecessary
-          ;; conditions, which means that a `pred' clause cannot be used for
-          ;; the match condition.  The following construct seems to survive.
-          (app (lambda (s) (string-match ,regexp s)) (pred identity))
-          ,@(let ((i 0))
-              (mapcar (lambda (name)
-                        (setq i (1+ i))
-                        `(app (match-string ,i) ,name))
-                      (reverse rx--pcase-vars))))))
+          ,(cond ((= nvars 0)
+                  ;; No variables bound: a single predicate suffices.
+                  `(pred (string-match ,regexp)))
+                 ((= nvars 1)
+                  ;; Single variable: bind it to the result of the
+                  ;; lambda function below.
+                  `(app (lambda (s)
+                          (and (string-match ,regexp s)
+                               (match-string 1 s)))
+                        ,(car rx--pcase-vars)))
+                 (t
+                  ;; Multiple variables: pack the submatches into a list
+                  ;; which is then immediately destructured into individual
+                  ;; variables again.  This is of course slightly inefficient.
+                  `(app (lambda (s)
+                          (and (string-match ,regexp s)
+                               (list
+                                ,@(mapcar (lambda (i) `(match-string ,i s))
+                                          (number-sequence 1 nvars)))))
+                        ,(list '\`
+                               (mapcar (lambda (name) (list '\, name))
+                                       (reverse rx--pcase-vars)))))))))
 
 ;; Obsolete internal symbol, used in old versions of the `flycheck' package.
 (define-obsolete-function-alias 'rx-submatch-n 'rx-to-string "27.1")