Creating this issue to preserve links to our discussion on this topic in #7:

• #43 (comment)
• #43 (comment)

When do you think is a good time to post the PEP on python-dev?

On python-dev, Nathaniel just suggested that we could run both the old and the new parser and compare the trees, at least during the alpha/beta period. This would help us trust that the new compiler fulfills its promise. (When selecting the old parser we should not do this, of course. Some people may be testing for startup speed, for example.)

Is it up to people to step up to review our PR or should we explicitly ask for it? Maybe on python-dev?

From @apalala:

The new parser should compute its performance stats (even at a performance hit) while it is in beta. A switch would make the parser output those stats.

With that, the parser can issue a Python WARNING for any code with LOC/sec outside of a given threshold (successful or failed parse).

The developer who sees the warning will likely know how to follow through (specially if the warning points to a web page).

Thus we can gather a meaningful case of test cases.

It's an easy and nice way to go safe about it.

Tricky thing of course is to know what a reasonable speed is for the current computer. Also what timer should we use to avoid mistaking a suspended process for taking so long? ^Z is still a thing. :-)

The ast.parse() function has two barely documented features, type_comments= and feature_version=, which modify the tokenizer and parser for the benefit of (primarily) mypy. type_comments=True changes the tokenizer to return TYPE_COMMENT tokens when it detects a type comment (a comment starting with 'type:'), and the old Grammar file has [TYPE_COMMENT] sprinkled throughout to support these.

In addition, feature_version=(3, N) enables a few changes in the tokenizer and ast.c to support older Python versions (mostly related to the three different stages of support for async and await keywords). [moved to #124]

We'll have to support these. I think it won't be very difficult since most of the logic is part of the tokenizer, but we'll have to check ast.c for other tests for feature_version. Note that these flags are passed in different forms to compile(), which has the actual support, but undocumented. See the source of ast.py.

Tentatively the plan could just be:

• Add a non-functional command-line flag that can enable and disable the new parser
• Add a PYTHON{SOMETHING} env variable to do the same
• Add an API that invokes the new parser explicitly (and another that invokes the old parser)
• Make the flag have the desired effect

When investigating what is the current maximum nesting with the current grammar, I found this:

where test_case is this function:

def test_case(n):
    parser.parse_string("("*n + "1+1" + ")"*n)

This means that the parser will appear to hang if the nesting is >>25 as the timings grow exponentially.

What do you think we should do about this?

Would it be too much to add a cf_use_peg_parser field to PyCompilerFlags? I think it'd make things simpler for #93 and we wouldn't need the not so pretty _PyInterpreterState_GET()->config assignment in pythonrun.c.

Both of the related fields get initialised to NULL and -1 respectively in Parser_New().

In upstream CPython, the Travis configuration uses Python 3.5 (for real) when running regeneration steps (PYTHON_FOR_REGEN) and that fails due to f-strings and other stuff in our generator. We need to upgrade the Travis file to use something more modern so the ci does not fail when merging upstream.

We should also restore all ci files that are used upstream so we know we are not missing something more.

See #42 (comment).

How exactly should these be named? _PyPegen_*? And should we wrap each declaration with PyAPI_FUNC?

Especially now that PyCon has been cancelled I expect that the best way to present our case to the core developers is through a PEP.

Based on SC feedback this will be easier to remove in 3.10.

Example:

import peg_parser
n=201
peg_parser.parse_string(n*'(' + ')'*n)

If n is 200 or less this produces no output; but for 201 or higher (up to 218) you get

SyntaxError: unmatched ')'

We are not throwing any error when parsing f(**kwargs, *args) while the old parser raises:

>>> f(**kwargs, *args)
  File "<stdin>", line 1
SyntaxError: iterable argument unpacking follows keyword argument unpacking

(v38) ~/cpygen$ echo pass | ./python.exe -pnew
FileNotFoundError: [Errno 2] No such file or directory: '<stdin>'
(v38) ~/cpygen$ 

With -pold it works (printing nothing).

How would you go about moving all the pegen code into cpython? What I have done so far is the following.

1. Copy the pegen directory into cpython/Parser (and remove all the stuff that's not needed).
2. Move pegen.c and parse_string.c from cpython/Parser/pegen into cpython/Parser.
3. Move pegen.h and parse_string.h from cpython/Parser/pegen into cpython/Include.
4. Generate two new functions that call run_parser_* and can be called from C.
5. Add a parse.h in cpython/Include that exports both the new generated functions.
6. Generate the parser into Parser/parse.c.

All the names are just dummy names that I didn't give much thought, but do you think something like this would work?

These were disabled temporarily in #19 but it's still unclear why they would fail.

There are two fstring-related types of SyntaxErrors, where pegen produces a different kind of error message:

1. Invalid string prefixes: For invalid string prefixes we output invalid syntax, while the old parser outputs unexpected EOF while parsing, which is arguably wrong.

2. For lambdas inside fstring expressions it's exactly the same. Pegen outputs invalid syntax, while the old parser prints unexpected EOF while parsing, which again is arguably wrong.

For some reason, I can't reproduce these error messages in an interactive session, but the tests pass with the old parser and fail with pegen, both on my systam and on Github Actions.

Given the response to this proposal in the Language Summit, I think it makes sense to update the PEP.

Current parser:

╰─ ./python       
Python 3.9.0a5+ (heads/errors:df51e29ce4, Apr  5 2020, 21:29:10) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> eval(r""" b'\x0' """)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1
SyntaxError: (value error) invalid \x escape at position 0
>>> eval(r"f'\N'")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1
SyntaxError: (unicode error) 'unicodeescape' codec can't decode bytes in position 0-1: malformed \N character escape

Pegen:

╰─ ./python -p new                                 
Python 3.9.0a5+ (heads/errors:df51e29ce4, Apr  5 2020, 21:29:10) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> eval(r""" b'\x0' """)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid \x escape at position 0
>>> eval(r"f'\N'")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeDecodeError: 'unicodeescape' codec can't decode bytes in position 0-1: malformed \N character escape

Do we want to do that?

Running make time in Tools/peg_generator on my Linux machine errors, because /usr/bin/time does not have a -l option. After a quick search, I didn't really find what that's supposed to do, in order to fix it.

Currently __debug__ = 1 segfaults, because with the current parser __debug__ gets parsed as a NAME and gets disallowed in ast.c.

Current Parser:

╰─ ./python       
Python 3.9.0a5+ (heads/pegen:99a8e2fa08, Apr  9 2020, 16:19:04) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import warnings
>>> with warnings.catch_warnings(record=True) as w:
...     warnings.simplefilter('always', category=DeprecationWarning)
...     eval("'''\n\\z'''")
... 
'\n\\z'
>>> len(w)
1

Pegen:

╰─ ./python -p new
Python 3.9.0a5+ (heads/pegen:99a8e2fa08, Apr  9 2020, 16:19:04) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import warnings
>>> with warnings.catch_warnings(record=True) as w:
...     warnings.simplefilter('always', category=DeprecationWarning)
...     eval("'''\n\\z'''")
... 
'\n\\z'
>>> len(w)
2

When, for example, parsing f(1, x=2, *(3, 4), x=5) the behaviour of the current parse is this:

>>> t = 'f(1, x=2, *(3, 4), x=5)'
>>> ast.parse(t)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/lysnikolaou/Repositories/pegen-cpython/Lib/ast.py", line 50, in parse
    return compile(source, filename, mode, flags,
  File "<unknown>", line 1
SyntaxError: keyword argument repeated

Pegen currently accepts this.

I don't think this should be a SyntaxError at all, but it is and there is a test that tests it as well in test_grammar.py.

I'm gonna take a short break, so I'm writing down what we left out of #11, now that I still got everything fresh.

_peg_parser.parse_string('hello\nworld', mode='single') currently succeeds with pegen. The current parser checks for multiline single statements in parsetok.c. We probably need to somehow do so as well.

PEP 614 relaxed the grammar on decorators -- you can now use any expression (even walrus) after the @ sign. It should be a simple fix.

This is on me (and I haven't found the perfect argument yet -- it started as a gut feeling).

Now that we use pegen by default, test_peg_parser is not using the old parser to compare the produced AST trees (because ast.parse also uses the new parser). We need to make sure that the test always compares both parsers against each other (maybe exposing the old parser also in the new _peg_parser module).

See we-like-parsers/pegen_experiments#220 (comment) and we-like-parsers/pegen_experiments@54d84ad

@pablogsal Do you know what we can do about the test failures? It seems unrelated to our work, but since we have a custom test configuration I don't know what to do about it.

And merges into the 'pegen' branch should also trigger CI.

Only a basic test run is required -- probably just the standard test suite on macOS, Windows and Linux?

FWIW I have no idea how to do this.

Current Parser:

╰─ ./python
Python 3.9.0a5+ (heads/pegen:99a8e2fa08, Apr  9 2020, 16:19:04) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> x = 5 | 4 |
  File "<stdin>", line 1
    x = 5 | 4 |
              ^
SyntaxError: invalid syntax

Pegen:

╰─ ./python -p new
Python 3.9.0a5+ (heads/pegen:99a8e2fa08, Apr  9 2020, 16:19:04) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> x = 5 | 4 |
  File "<stdin>", line 1
    x = 5 | 4 |
               ^
SyntaxError: invalid syntax

Difference by one. Would it be okay to just skip this test if pegen is enabled?

If the new parser is going to be the default (and therefore ast.parse and compile) will use it, do we really need the peg_parser module?

I am asking because I was going to make it compile on Windows, but if we are not going to keep it around, it does not make sense to make the effort.

Wherever the current parser outputs a specialized error message, we ought to do so as well. Not clear how exactly we are going to implement this yet. There's @pablogsal's proposal from #41 (comment).

It should be named PYTHON{SOMETHING}.

• Add a non-function env variable to begin with.
• Actually make the env variable have the desired effect.

• Add a non-functional flag to begin with.
• Implement the needed functionality, so that enabling the flag has the desired effect.

They should all return a mod_ty. The caller can then use it to create the necessary PyObject *.

Hi everyone!

I gave a talk about property-based testing at the Language Summit yesterday, and people seemed interested. Since it's particularly useful when you have two implementations that can be compared, I thought I should drop by and offer to help apply it to help test the new parser 🙂

We've tested against the stdlib and many popular packages - why might this find additional bugs?

Popular and well-written code may have zero examples of many weird syntactic constructs, since it's typically designed for clarity and compatibility. In my demo here, I discovered several strings that can be compiled but not tokenize.tokenized - involving odd use of newlines, backslashes, non-ascii characters, etc.

It's also nice to automatically get minimal examples of any failing inputs.

Say we decide to use this. What's the catch?

I'll assume here that you're familiar with the basic idea of Hypothesis (e.g. saw my talk) - if not, the example above should be helpful and I've collected all the links you could want here: https://github.com/Zac-HD/stdlib-property-tests#further-reading

I've already written a tool to generate Python source code from 3.8's grammar, called hypothesmith - it's a standard strategy, which generates strings which can be passed to the compile builtin (as a convenient predicate for "is this actually valid source code").

hypothesmith is implemented from a reasonably good EBNF grammar, and "inverting" it using Hypothesis' built-in support for such cases (and the st.from_regex() strategy for terminals). The catch is that, for exactly the same reasons as PEP617 exists, I have a bunch of hacks where I filter substrings using the compile builtin - and so there's no way to generate anything not accepted by that function. Pragmatically, I think it's still worth using, since it's pretty quick to set up!

Extensions after vanilla hypothesmith is running against the parser

First, updating hypothesmith to treat the PEG grammar as authoritative is a no-brainer - I'm aiming to finish that in the next week or two. This would remove the "compile is trusted" limitation entirely. It also shouldn't be too hard - strategies are literally parser combinators, and to generate a string we just "run it backwards": start at the root, and choose random productions at each branch or generate random terminals, writing out the string that would drive such transitions.

Second, Hypothesis tests can be used as fuzz targets for coverage-guided fuzzers such as AFL or libfuzzer. Since we can also generate a wide variety of inputs from scratch, this can be a really powerful technique for ratcheting up our coverage of really weird edge cases. Or just hypothesis.target(...) things like the length of the generated code, the number of ast nodes, number of node types, nodes-per-length, etc.

Please be very precise about what you suggest

1. Install Hypothesis and Hypothesmith
2. Use @hypothesis.given(hypothesmith.from_grammar()) to generate inputs to a copy of your existing tests which run against stdlib / pypi / other python modules.
3. Fix any bugs you find, tell me what worked and/or what didn't.

Something I didn't think of.

You probably have more questions, and I hope I haven't been too presumptuous opening this issue. Please ask, and I'm happy to answer and help out (including reviewing and/or writing code) however I can, subject to other commitments and my Australian timezone!

Finally, thanks for all your work on this project - I'm really looking forward to what a precise and complete grammar will do for the core and wider Python community.

This was added in #23.

Current Parser:

╰─ ./python       
Python 3.9.0a5+ (heads/pegen:99a8e2fa08, Apr  9 2020, 16:19:04) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> code = '# -*- coding: badencoding -*-\n"\xc2\xa4"\n'
>>> eval(code)
'¤'

Pegen:

╰─ ./python -p new
Python 3.9.0a5+ (heads/pegen:99a8e2fa08, Apr  9 2020, 16:19:04) 
[GCC 9.2.1 20191008] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> code = '# -*- coding: badencoding -*-\n"\xc2\xa4"\n'
>>> eval(code)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
LookupError: unknown encoding: badencoding

From the test suite after #96 is applied:

======================================================================
FAIL: test_filename_correct (test.test_symtable.SymtableTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/pgalindo3/github/python/pegen/Lib/test/test_symtable.py", line 194, in checkfilename
    symtable.symtable(brokencode, "spam", "exec")
  File "/Users/pgalindo3/github/python/pegen/Lib/symtable.py", line 13, in symtable
    top = _symtable.symtable(code, filename, compile_type)
  File "<string>", line 1
    def f(x): foo)(
                 ^
SyntaxError: unmatched ')'

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/Users/pgalindo3/github/python/pegen/Lib/test/test_symtable.py", line 201, in test_filename_correct
    checkfilename("def f(x): foo)(", 14)  # parse-time
  File "/Users/pgalindo3/github/python/pegen/Lib/test/test_symtable.py", line 196, in checkfilename
    self.assertEqual(e.filename, "spam")
AssertionError: '<string>' != 'spam'
- <string>
+ spam