all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* Can't compile `or' pcase pattern
@ 2017-05-11 16:04 Michael Heerdegen
  2017-05-12  2:29 ` Stefan Monnier
  0 siblings, 1 reply; 3+ messages in thread
From: Michael Heerdegen @ 2017-05-11 16:04 UTC (permalink / raw)
  To: Emacs Development

[-- 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 --]

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: Can't compile `or' pcase pattern
  2017-05-11 16:04 Can't compile `or' pcase pattern Michael Heerdegen
@ 2017-05-12  2:29 ` Stefan Monnier
  2017-05-13 14:14   ` Michael Heerdegen
  0 siblings, 1 reply; 3+ messages in thread
From: Stefan Monnier @ 2017-05-12  2:29 UTC (permalink / raw)
  To: emacs-devel

> #+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




^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: Can't compile `or' pcase pattern
  2017-05-12  2:29 ` Stefan Monnier
@ 2017-05-13 14:14   ` Michael Heerdegen
  0 siblings, 0 replies; 3+ messages in thread
From: Michael Heerdegen @ 2017-05-13 14:14 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: emacs-devel

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.



^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2017-05-13 14:14 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-05-11 16:04 Can't compile `or' pcase pattern Michael Heerdegen
2017-05-12  2:29 ` Stefan Monnier
2017-05-13 14:14   ` Michael Heerdegen

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.