Re: Make peg.el a built-in library?

[Adam Porter]

On Fri, Oct 1, 2021 at 1:05 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>
> > In org-ql, the PEX is redefined at load time and/or run time, being
> > derived from search keywords that are defined by the package and
> > possibly by the user.  So the PEX can't be defined in advance, at
> > compile time.  So having to use `with-peg-rules' means having to use
> > `eval'.
>
> If the grammar changes radically at run time, based on external/user
> data there's probably no better way than via `eval` or similar (`load`,
> `byte-compile`, you name it).
>
> But if the changes are sufficiently limited (e.g. have an (or "foo"
> "bar" ....) with a variable set of strings that can match), then we can
> do better.

In org-ql's case, it's the latter: the grammar doesn't fundamentally
change, only the list of strings that can be matched in a certain
expression:

https://github.com/alphapapa/org-ql/blob/31aeb0a2505acf8044c07824888ddec7f3e529c1/org-ql.el#L869

> E.g. we could have a PEX of the form (re FORM) where FORM can be any
> ELisp expression that returns a regular expression.  Then `org-ql.el`
> could do
>
>     (let ((predicate-re (regexp-opt predicate-names)))
>       (peg-parse
>           ((query (+ term
>                      (opt (+ (syntax-class whitespace) (any)))))
>            [...]
>            (predicate (re predicate-re))
>            [...])))

That would be helpful, yes.

> PS: BTW, regarding your comment:
>
>         ;; Sort the keywords longest-first to work around what seems to be an
>         ;; obscure bug in `peg': when one keyword is a substring of another,
>         ;; and the shorter one is listed first, the shorter one fails to 
> match.
>
> The behavior you describe indeed seems like a bug, but maybe what you
> see is slightly different (and not a bug): if you have a PEX like
> (and (or "foo" "foobar") "X")
> the "foo" will match when faced with "foobarX" and the parser won't
> backtrack to try and match the "foobar" when the "X" fails to match.

Hmm, thanks.  I think an example of the problem is that a predicate in
org-ql might have a shorter alias, e.g. "heading" is has the alias
"h", and predicates are followed by arguments, like "heading:foo", so
IIRC, without sorting them there, "heading:foo" would work, while
"h:foo" wouldn't.  (Or maybe a better example is predicates that
optionally accept keyword-style arguments, like
"ts-active:from=2021-10-01", which has the alias "ts-a", and could
also be called without arguments, like "ts-a:".)

> It's one of those differences between BNF and PEG grammars.
> So indeed you do want to sort from longest to shortest to avoid
> this problem.

Thanks, I didn't realize that.