Can't compile `or' pcase pattern

Can't compile `or' pcase pattern

[Michael Heerdegen]

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

Hello,

Stefan, probably,

I have found a problem while working on el-search:

The following form F:

#+begin_src emacs-lisp
(el-search--matcher
 '(or (l ^ defstruct object)
      (l ^ (and (symbol "def") (or (pred macrop) (pred special-form-p))) object))) 
#+end_src

should compile a lambda which contains a pcase form containing the given
`or' pattern:

#+begin_src emacs-lisp
(defun el-search--matcher (pattern &optional result)
  (eval
   (let ((expression (make-symbol "expression")))
     `(el-search--with-additional-pcase-macros
       (let ((byte-compile-debug t) ;make undefined pattern types raise an error
             (warning-suppress-log-types '((bytecomp)))
             (pcase--dontwarn-upats (cons '_ pcase--dontwarn-upats)))
         (byte-compile (lambda (,expression)
                         (pcase ,expression
                           (,pattern ,(or result t))
                           (_        nil)))))))))
#+end_src

where `el-search--with-additional-pcase-macros' just temporarily adds
some pattern definitions to the pcase macro environment.

The problem is that the call of `el-search--matcher' in F takes over one
minute of time and then gives up with

|  byte-compile-lapcode: Bytecode overflow

Similar cases also take extremely long also but don't cause an overflow.
AFAICT the expansion of the pattern does not produce extraordinarily
dumb code.

Even stranger: Calling `el-search--matcher' with any of the 2 patterns
inside the `or', i.e.,

#+begin_src emacs-lisp
(el-search--matcher
 '(l ^ defstruct object))
#+end_src

and

#+begin_src emacs-lisp
(el-search--macroexpand
 '(l ^ (and (symbol "def") (or (pred macrop) (pred special-form-p))) object))
#+end_src

instantly succeed.

Have I hit some weak point in the implementation of `pcase's `or'?  Is
there some way to avoid this problem?  Simplifying the semantics of `l'
seems to help a bit.  But I would like to understand what the problem is
and how I could avoid it.

This is on master, but with emacs-25 I see same issue.

Quitting with debug-on-quit -> t doesn't look like there is an infinite
recursion while compiling or code walking (though the recursion depth is
not small).

For reference I attach the macroexpansion of the pattern in F.  


Thanks,

Michael.



[-- Attachment #2: bug.el --]
[-- Type: application/emacs-lisp, Size: 11157 bytes --]

Re: Can't compile `or' pcase pattern

[Stefan Monnier]

> #+begin_src emacs-lisp
> (el-search--matcher
>  '(or (l ^ defstruct object)
>       (l ^ (and (symbol "def") (or (pred macrop) (pred special-form-p))) object)))
> #+end_src

Looking at the definition of `l` I think you're pushing pcase a bit
further than it can go.

A bit like a DFA representation of a regexp can explode, a pcase's
expansion can explode in some cases, and your `l` has all the tools
needed to triggger such explosions.

Maybe you can reduce the pain, by looking at the expansion and
trying to see how pcase-mutually-exclusive-p could be improved to get
a better result.


        Stefan

Re: Can't compile `or' pcase pattern

[Michael Heerdegen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Looking at the definition of `l` I think you're pushing pcase a bit
> further than it can go.
>
> A bit like a DFA representation of a regexp can explode, a pcase's
> expansion can explode in some cases, and your `l` has all the tools
> needed to triggger such explosions.

Hmm, somehow I expected the technical term "explode" in your answer.

> Maybe you can reduce the pain, by looking at the expansion and trying
> to see how pcase-mutually-exclusive-p could be improved to get a
> better result.

I guess you mean `pcase--mutually-exclusive-p'.  When I get the time
I'll try to learn how that works.  For now, I have narrowed the
semantics of the lpats so that they don't automatically also try quoted
and function-quoted symbols.

Thanks,

Michael.