Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Build-out an AST optimizer, moving some functionality out of the peephole optimizer #55758

Closed
eltoder mannequin opened this issue Mar 15, 2011 · 81 comments
Closed

Build-out an AST optimizer, moving some functionality out of the peephole optimizer #55758

eltoder mannequin opened this issue Mar 15, 2011 · 81 comments
Labels
3.7 interpreter-core

Comments

@eltoder
Copy link
Mannequin

@eltoder eltoder mannequin commented Mar 15, 2011

BPO 11549
Nosy @birkenfeld, @rhettinger, @terryjreedy, @mdickinson, @ncoghlan, @pitrou, @vstinner, @benjaminp, @Trundle, @methane, @davidmalcolm, @meadori, @durban, @jeremyhylton, @eltoder, @ericsnowcurrently, @berkerpeksag, @serhiy-storchaka, @phmc, @pstch, @mbdevpl
Dependencies
  • bpo-11682: PEP 380 reference implementation for 3.3
  • Files
  • 0_ast.patch
  • 0_fold.patch
  • 0_compile.patch
  • 0_generated.patch
  • 0_tests.patch
  • issue11549.patch: Regenerated for review
  • change-ast.patch
  • ast-docstring.patch
  • Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = None
    closed_at = <Date 2020-01-26.06:07:31.706>
    created_at = <Date 2011-03-15.04:46:42.255>
    labels = ['interpreter-core', '3.7']
    title = 'Build-out an AST optimizer, moving some functionality out of the peephole optimizer'
    updated_at = <Date 2020-01-26.06:07:31.705>
    user = 'https://github.com/eltoder'

    bugs.python.org fields:

    activity = <Date 2020-01-26.06:07:31.705>
    actor = 'rhettinger'
    assignee = 'none'
    closed = True
    closed_date = <Date 2020-01-26.06:07:31.706>
    closer = 'rhettinger'
    components = ['Interpreter Core']
    creation = <Date 2011-03-15.04:46:42.255>
    creator = 'eltoder'
    dependencies = ['11682']
    files = ['21198', '21199', '21200', '21201', '21202', '42810', '46467', '46542']
    hgrepos = []
    issue_num = 11549
    keywords = ['patch']
    message_count = 81.0
    messages = ['130955', '131070', '131071', '131072', '131074', '131083', '131084', '131085', '131166', '131172', '131210', '131214', '131392', '131396', '131952', '131953', '132310', '132312', '132313', '132314', '132346', '132348', '132349', '132350', '132361', '132362', '132382', '132453', '132455', '132473', '132476', '137785', '137788', '137819', '137906', '138413', '139395', '160608', '160662', '168146', '169894', '169895', '169896', '169897', '169898', '169899', '169900', '169902', '169903', '185286', '193656', '193657', '265296', '265553', '265554', '265607', '265613', '265621', '286503', '286528', '286530', '286531', '286532', '286534', '286535', '286539', '286542', '286588', '286589', '286591', '286592', '286668', '286697', '286725', '286726', '286730', '287120', '287121', '287187', '287217', '360721']
    nosy_count = 26.0
    nosy_names = ['georg.brandl', 'rhettinger', 'terry.reedy', 'mark.dickinson', 'ncoghlan', 'pitrou', 'vstinner', 'techtonik', 'nadeem.vawda', 'benjamin.peterson', 'Trundle', 'methane', 'dmalcolm', 'meador.inge', 'daniel.urban', 'Jeremy.Hylton', 'santoso.wijaya', 'eltoder', 'eric.snow', 'jcon', 'berker.peksag', 'serhiy.storchaka', 'pconnell', 'isoschiz', 'pstch', 'mbdevpl']
    pr_nums = []
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = None
    url = 'https://bugs.python.org/issue11549'
    versions = ['Python 3.7']

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 15, 2011

    As pointed out by Raymond, constant folding should be done on AST rather than on generated bytecode. Here's a patch to do that. It's rather long, so overview first.

    The patch replaces existing peephole pass with a folding pass on AST and a few changes in compiler. Feature-wise it should be on par with old peepholer, applying optimizations more consistently and thoroughly, but maybe missing some others. It passes all peepholer tests (though they seem not very extensive) and 'make test', but more testing is, of course, needed.

    I've split it in 5 pieces for easier reviewing, but these are not 5 separate patches, they should all be applied together. I can upload it somewhere for review or split it in other ways, let me know. Also, patches are versus 1e00b161f5f5, I will redo against head.

    TOC:

    1. Changes to AST
    2. Folding pass
    3. Changes to compiler
    4. Generated files (since they're checked in)
    5. Tests

    In detail:

    1. I needed to make some changes to AST to enable constant folding. These are
      a) Merge Num, Str, Bytes and Ellipsis constructors into a single Lit (literal) that can hold anything. For one thing, this removes a good deal of copy-paste in the code, since these are always treated the same. (There were a couple of places where Bytes ctor was missing for no apparent reason, I think it was forgotten.) Otherwise, I would have to introduce at least 4 more node types: None, Bool, TupleConst, SetConst. This seemed excessive.
      b) Docstring is now an attribute of Module, FunctionDef and ClassDef, rather than a first statement. Docstring is a special syntactic construction, it's not an executable code, so it makes sense to separate it. Otherwise, optimizer would have to take extra care not to introduce, change or remove docstring. For example:
    def foo():
      "doc" + "string"

    Without optimizations foo doesn't have a docstring. After folding, however, the first statement in foo is a string literal. This means that docstring depends on the level of optimizations. Making it an attribute avoids the problem.
    c) 'None', 'True' and 'False' are parsed as literals instead of names, even without optimizations. Since they are not redefineable, I think it makes most sense to treat them as literals. This isn't strictly needed for folding, and I haven't removed all the artefacts, in case this turns out controversial.

    1. Constant folding (and a couple of other tweaks) is performed by a visitor. The visitor is auto-generated from ASDL and a C template. C template (Python/ast_opt.ct) provides code for optimizations and rules on how to call it. Parser/asdl_ct.py takes this and ASDL and generates a visitor, that visits only nodes which have associated rules (but visits them via all paths).
      The code for optimizations itself is pretty straight-forward.
      The generator can probably be used for symtable.c too, removing ~200 tedious lines of code.

    2. Changes to compiler are in 3 categories
      a) Updates for AST changes.
      b) Changes to generate better code and not need any optimizations. This includes tuple unpacking optimization and if/while conditions.
      c) Simple peephole pass on compiler internal structures. This is a better form for doing this, than a bytecode. The pass only deals with jumps to jumps/returns and trivial dead code.
      I've also made 'raise' recognized as a terminator, so that 'return None' is not inserted after it.

    4, 5. No big surprises here.

    @eltoder eltoder mannequin added the interpreter-core label Mar 15, 2011
    @smontanaro
    Copy link
    Contributor

    @smontanaro smontanaro commented Mar 15, 2011

    I'm confused. Why aren't there review links?

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 15, 2011

    Because I don't know how to make them. Any pointers?

    @pitrou
    Copy link
    Member

    @pitrou pitrou commented Mar 15, 2011

    Because I don't know how to make them. Any pointers?

    Martin is hacking on the tool these days... So it's no surprise it
    doesn't work perfectly yet ;)
    If you have a Google account you can upload these patches to
    http://codereview.appspot.com/, though.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 16, 2011

    @ncoghlan
    Copy link
    Contributor

    @ncoghlan ncoghlan commented Mar 16, 2011

    The review links didn't come up automatically because 336137a359ae isn't a hg.python.org/cpython revision ID.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 16, 2011

    I see. Should I attach diffs vs. some revision from hg.python.org?

    @ncoghlan
    Copy link
    Contributor

    @ncoghlan ncoghlan commented Mar 16, 2011

    No need, since you manually created a review on appspot. The local Reitveld links are just a convenience that can avoid the need to manually create a review instance.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 16, 2011

    Any comments on the code so far or suggestions on how we should move forward?

    @ncoghlan
    Copy link
    Contributor

    @ncoghlan ncoghlan commented Mar 16, 2011

    I've been focusing on softer targets during the sprints - I'll dig into this once I'm back home and using my desktop machine again.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 17, 2011

    I've updated patches on Rietveld with some small changes. This includes better code generation for boolops used outside of conditions and cleaned up optimize_jumps(). This is probably the last change before I get some feedback.
    Also, I forgot to mention yesterday, patches on Rietveld are vs. ab45c4d0b6ef

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 17, 2011

    Just for fun I've run pystones. W/o my changes it averages to about 70k, with my changes to about 72.5k.

    @terryjreedy
    Copy link
    Member

    @terryjreedy terryjreedy commented Mar 19, 2011

    A couple of somewhat related issues:
    bpo-10399 AST Optimization: inlining of function calls
    bpo-1346238 A constant folding optimization pass for the AST
    Obviously, ast optimizers should work together and not duplicate.
    Nice to see increased attention.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 19, 2011

    AFAICT my patch has everything that bpo-1346238 has, except BoolOps, which can be easily added (there's a TODO). I don't want to add any new code, though, until the current patch will get reviewed -- adding code will only make reviewing harder.

    bpo-10399 looks interesting, I will take a look.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 24, 2011

    Is anyone looking or planing to look at the patch?

    @terryjreedy
    Copy link
    Member

    @terryjreedy terryjreedy commented Mar 24, 2011

    I suspect someone will sometime. There is bit of a backlog of older issues.

    @ncoghlan
    Copy link
    Contributor

    @ncoghlan ncoghlan commented Mar 27, 2011

    Finally got around to reviewing this (just a visual scan at this stage) - thanks for the effort. These are mostly "big picture" type comments, so I'm keeping them here rather than burying them amongst all the details in the code review tool.

    The effect that collapsing Num/Str/Bytes into a single Lit node type has on ast.literal_eval bothered me initially, but looking more closely, I think those changes will actually improve the function (string concatenation will now work, and errors like "'hello' - 'world'" should give a more informative TypeError). (Bikeshed: We use Attribute rather than Attr for that node type, perhaps the full "Literal" name would be better, too)

    Lib/test/disutil.py should really be made a feature of the dis module itself, by creating an inner disassembly function that returns a string, then making the existing "dis" and "disassembly" functions print that string (i.e. similar to what I already did in making dis.show_code() a thin wrapper around the new dis.code_info() function in 3.2). In the absence of a better name, "dis_to_str" would do.

    Since the disassembly is interpreter specific, the new disassembly tests really shouldn't go directly in test_compile.py. A separate "test_ast_optimiser" file would be easier for alternate implementations to skip over. A less fragile testing strategy may also be to use the ast.PyCF_ONLY_AST flag and check the generated AST rather than the generated bytecode.

    I'd like to see a written explanation for the first few changes in test_peepholer.py. Are those cases no longer optimised? Are they optimised differently? Why did these test cases have to change? (The later changes in that file look OK, since they seem to just be updating tests to handle the more comprehensive optimisation)

    When you get around to rebasing the patch on 3.3 trunk, don't forget to drop any unneeded "from __future__" imports.

    The generated code for the Lit node type looks wrong: it sets v to Py_None, then immediately checks to see if v is NULL again.

    Don't use "string" as a C type - use "char *" (and "char **" instead of "string *").

    There should be a new compiler flag to skip the AST optimisation step.

    A bunch of the compiler internal changes seem to make the basic flow of the generated assembly not match the incoming source code. It doesn't seem like a good idea to conflate these with the AST optimisation patch. If that means leaving the peepholer in to handle them for now, that's OK - it's fine to just descope the peepholer without removing it entirely.

    @ncoghlan
    Copy link
    Contributor

    @ncoghlan ncoghlan commented Mar 27, 2011

    I think the biggest thing to take out of my review is that I strongly encourage deferring the changes for 5(b) and 5(c).

    I like the basic idea of using a template-based approach to try to get rid of a lot of the boilerplate code currently needed for AST visitors.

    Providing a hook for optimisation in Python (as Dave Malcolm's approach does) is valuable as well, but I don't think the two ideas need to be mutually exclusive.

    As a more general policy question... where do we stand in regards to backwards compatibility of the AST? The ast module docs don't have any caveats to say that it may change between versions, but it obviously *can* change due to new language constructs (if nothing else).

    @pitrou
    Copy link
    Member

    @pitrou pitrou commented Mar 27, 2011

    As a more general policy question... where do we stand in regards to
    backwards compatibility of the AST? The ast module docs don't have any
    caveats to say that it may change between versions, but it obviously
    *can* change due to new language constructs (if nothing else).

    Yes, but can existing constructs produce a different structure from one
    Python version to another?
    It seems to me that the ast module is the recommended way to inspect the
    structure of Python code (much more so that bytecode or concrete syntax
    trees). Perhaps the optimizations can leave the initial ast intact?
    Perhaps with an additional API to get the optimized ast as well?

    @birkenfeld
    Copy link
    Member

    @birkenfeld birkenfeld commented Mar 27, 2011

    I would provide this via another compile flag a la PyCF_ONLY_AST. If you give only this flag, you get the original AST. If you give (e.g.)
    PyCF_OPTIMIZED_AST, you get the resulting AST after the optimization stage (or the same, if optimization has been disabled).

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 27, 2011

    Thanks.

    string concatenation will now work, and errors like "'hello' - 'world'"
    should give a more informative TypeError
    Yes, 'x'*5 works too.

    Bikeshed: We use Attribute rather than Attr for that node type,
    perhaps the full "Literal" name would be better
    Lit seemed more in line with Num, Str, BinOp etc. No reason it can't be changed, of course.

    Lib/test/disutil.py should really be made a feature of the dis module
    itself
    Agreed, but I didn't want to widen the scope of the patch. If this is something that can be reviewed quickly, I can make a change to dis. I'd add a keyword-only arg to dis and disassembly -- an output stream defaulting to stdout. dis_to_str then passes StringIO and returns the string. Sounds OK?

    Since the disassembly is interpreter specific, the new disassembly
    tests really shouldn't go directly in test_compile.py. A separate
    "test_ast_optimiser" file would be easier for alternate
    implementations to skip over.
    New tests in test_compiler are not for the AST pass, but for changes to compile.c. I can split them out, how about test_compiler_opts?

    I'd like to see a written explanation for the first few changes in
    test_peepholer.py
    Sure.

    1. not x == 2 can be theoretically optimized to x != 2, while this test is for another optimization. not x is more robust.
    2. Expression statement which is just a literal doesn't produce any code at all. This is now true for None/True/False as well. To preserve constants in the output I've put them in tuples.

    When you get around to rebasing the patch on 3.3 trunk, don't forget
    to drop any unneeded "from __future__" imports.
    If you're referring to asdl_ct.py, that's actually an interesting question. asdl_ct.py is run by system installed python2, for obvious reasons. What is the policy here -- what is the minimum version of system python that should be sufficient to build python3? I tested my code on 2.6 and 3.1, and with __future__ it should work on 2.5 as well. Is this OK or should I drop 'with' so it runs on 2.4?

    The generated code for the Lit node type looks wrong: it sets v to
    Py_None, then immediately checks to see if v is NULL again.
    Right, comment in asdl_c.py says:
    # XXX: special hack for Lit. Lit value can be None and it
    # should be stored as Py_None, not as NULL.
    If there's a general agreement on Lit I can certainly clean this up.

    Don't use "string" as a C type - use "char *" (and "char **" instead
    of "string *").
    string is a typedef for PyObject that ASDL uses. I don't think I have a choice to not use it. Can you point to a specific place where char* could be used?

    There should be a new compiler flag to skip the AST optimisation step.
    There's already an 'optimizations level' flag. Maybe we should make it more meaningful rather than multiplying the number of flags?

    A bunch of the compiler internal changes seem to make the basic flow
    of the generated assembly not match the incoming source code.
    Can you give an example of what you mean?
    The changes are basically 1) standard way of handling conditions in simple compilers 2) peephole.

    It doesn't seem like a good idea to conflate these with the AST
    optimisation patch. If that means leaving the peepholer in to handle
    them for now, that's OK - it's fine to just descope the peepholer
    without removing it entirely.
    The reason why I think it makes sense to have this in a single change is testing. This allows to reuse all existing peephole tests. If I leave old peephole enabled there's no way to tell if my pass did something from disassembly. I can port tests to AST, but that seemed like more work than match old peepholer optimizations.
    Is there any opposition to doing simple optimizations on compiler structures? They seem a good fit for the job. In fact, if not for stack representation, I'd say that they are better IR for optimizer than AST.

    Also, can I get your opinion on making None/True/False into literals early on and getting rid of forbidden_name?

    Antoine, Georg -- I think Nick's question is not about AST changing after optimizations (this can indeed be a separate flag), but the structure of AST changing. E.g. collapsing of Num/Str/Bytes into Lit.

    Btw, if this is acceptable I'd make a couple more changes to make scope structure obvious from AST. This will allow auto-generating much of the symtable pass.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 27, 2011

    and with __future__ it should work on 2.5 as well.
    Actually, seems that at least str.format is not in 2.5 as well. Still the question is should I make it run on 2.5 or 2.4 or is 2.6 OK (then __future__ can be removed).

    @durban
    Copy link
    Mannequin

    @durban durban mannequin commented Mar 27, 2011

    not x == 2 can be theoretically optimized to x != 2, ...

    I don't think it can:

    >>> class X:
    ...     def __eq__(self, other):
    ...             return True
    ...     def __ne__(self, other):
    ...             return True
    ... 
    >>> x = X()
    >>> 
    >>> not x == 2
    False
    >>> x != 2
    True
    >>>

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 27, 2011

    I don't think it can:
    That already doesn't work in dict and set (eq not consistent with hash), I don't think it's a big problem if that stops working in some other cases. Anyway, I said "theoretically" -- maybe after some conservative type inference.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 27, 2011

    Also, to avoid any confusion -- currently my patch only runs AST optimizations before code generation, so compile() with ast.PyCF_ONLY_AST returns non-optimized AST.

    @terryjreedy
    Copy link
    Member

    @terryjreedy terryjreedy commented Mar 27, 2011

    While I would not be happy to use class X above, the 3.2 manual explicitly says "There are no implied relationships among the comparison operators. The truth of x==y does not imply that x!=y is false. " .

    @ncoghlan
    Copy link
    Contributor

    @ncoghlan ncoghlan commented Mar 28, 2011

    OK, I missed the fact that the new optimisation pass isn't run under PyCF_ONLY_AST.

    However, as Eugene picked up, my concern is actually with the collapsing of Str/Num/Bytes/Ellipsis into the new Lit node, and the changes to the way None/True/False are handled. They're all changes that *make sense*, but would also likely cause a variety of AST manipulations to break. We definitely don't care when bytecode hacks break, but providing the ast module means that AST manipulation is officially supported.

    However, the reason I bring up new constructs, is the fact that new constructs may break AST manipulation passes, even if the old structures are left intact - the AST visitor may miss (or misinterpret) things because it doesn't understand the meaning of the new nodes.

    We may need to take this one back to python-dev (and get input from the other implementations as well). It's a fairly fundamental question when it comes to the structure of any changes.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Mar 29, 2011

    If we have to preserve backward compatibility of Python AST API, we can do this relatively easily (at the expense of some code complexity):

    • Add 'version' argument to compile() and ast.parse() with default value of 1 (old AST). Value 2 will correspond to the new AST.
    • Do not remove Num/Str/Bytes/Ellipsis Python classes. Make PyAST_obj2mod and PyAST_mod2obj do appropriate conversions when version is 1.
    • Possibly emit a PendingDeprecationWarning when version 1 is used with the goal of removing it in 3.5

    Alternative implementation is to leave Num/Str/etc classes in C as well, and write visitors (similar to folding one) to convert AST between old and new forms.

    Does this sounds reasonable? Should this be posted to python-dev? Should I write a PEP (I'd need some help with this)?

    Are there any other big issues preventing this to be merged?

    @rhettinger
    Copy link
    Contributor

    @rhettinger rhettinger commented Mar 29, 2011

    Eugene, I think you're doing great work here and would like to see you succeed. In the near term, I don't have time to participate, but don't let that stop you.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented May 14, 2016

    Fairly sure it's 5 years old.

    @serhiy-storchaka
    Copy link
    Member

    @serhiy-storchaka serhiy-storchaka commented May 15, 2016

    Yes, the patch is outdated, conflicts with current code (and would conflict even more after pushing the wordcode patch) and contains bugs. But it moved in right direction, I think your _PyCode_ConstantKey() could help to fix bugs. I'm going to revive this issue.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented May 15, 2016

    Serhiy: Nice! Yes, _PyCode_ConstantKey solved the problem.

    But bpo-16619 went in the opposite direction of this patch, and introduced a new type of literal node instead of unifying the existing ones. Kind of a shame, since *this* patch, I believe, both fixes that bug and removes the unreachable code in the example :)

    I also see that Victor has been doing some of the same work, e.g. bpo-26146.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented May 15, 2016

    I also see that Victor has been doing some of the same work, e.g. bpo-26146.

    ast.Constant idea directly comes from your work. The implementatiln may ve
    different.

    It's a first step for AST optimizers.

    @methane
    Copy link
    Member

    @methane methane commented Jan 31, 2017

    @Haypo, how do you think about ast.Lit and ast.Constant?
    Is this patch updated to use ast.Constant?
    Or ast.Constant should be used only for some transform like constant folding?

    @methane methane added the 3.7 label Jan 31, 2017
    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Jan 31, 2017

    @Haypo, how do you think about ast.Lit and ast.Constant?

    I already made two changes in Python 3.6 :-)

    I added ast.Constant to Python 3.6. While it's not used by .py=>AST compiler, it is understood by the AST->bytecode compiler (ex: handle correctly special cases like docstrings).
    https://docs.python.org/dev/whatsnew/3.6.html#ast
    => issue bpo-26146

    Moreover, I also modified the format of the co_lnotab structure to support negative line number delta. So a code transformer can move instructions and preserve the Python traceback feature.
    https://docs.python.org/dev/whatsnew/3.6.html#changes-in-the-python-api
    => see the PEP-511

    @pstch
    Copy link
    Mannequin

    @pstch pstch mannequin commented Jan 31, 2017

    I would like to point out that the changes in ast.literal_eval may have some security risk for code that do not expect this function to return an object with user-controlled length (for example, with 2**32*'X'). AFAIK, this is not possible with the current version of literal_eval.

    At least this library would have a serious risk of remote DoS :

    Because it only serializes literals and recreates the objects using ast.literal_eval(), the serialized data is safe to transport to other machines (over the network for instance) and de-serialize it there.

    Sorry for the noise if this is a useless/incorrect consideration.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Jan 31, 2017

    Hugo Geoffroy added the comment:

    I would like to point out that the changes in ast.literal_eval may have some security risk for code that do not expect this function to return an object with user-controlled length (for example, with 2**32*'X'). AFAIK, this is not possible with the current version of literal_eval.

    Since the Python compiler doesn't produce ast.Constant, there is no
    change in practice in ast.literal_eval(). If you found a bug, please
    open a new issue.

    At least this library would have a serious risk of remote DoS :

    I tried hard to implement a sandbox in Python and I failed:
    https://lwn.net/Articles/574215/

    I don't think that literal_eval() is safe *by design*.

    @serhiy-storchaka
    Copy link
    Member

    @serhiy-storchaka serhiy-storchaka commented Jan 31, 2017

    Good point Hugo. Yes, this should be taken into account when move constant folding to AST level. Thank you for the reminder.

    @serhiy-storchaka
    Copy link
    Member

    @serhiy-storchaka serhiy-storchaka commented Jan 31, 2017

    Since the Python compiler doesn't produce ast.Constant, there is no
    change in practice in ast.literal_eval(). If you found a bug, please
    open a new issue.

    Currently there is no a bug in ast.literal_eval() because the '**' operator is not accepted.

    >>> ast.literal_eval("2**2**32")
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "/home/serhiy/py/cpython/Lib/ast.py", line 85, in literal_eval
        return _convert(node_or_string)
      File "/home/serhiy/py/cpython/Lib/ast.py", line 84, in _convert
        raise ValueError('malformed node or string: ' + repr(node))
    ValueError: malformed node or string: <_ast.BinOp object at 0xb6f2fa4c>

    But if move the optimization to AST level this can add a vulnerability to DOS attack. The optimizer should do additional checks first than execute operators that can return too large value or take too much CPU time. Currently this vulnerability have place in the peephole optimizer.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Jan 31, 2017

    Currently there is no a bug in ast.literal_eval() because the '**' operator is not accepted.

    The doc says "This can be used for safely evaluating strings containing Python values from untrusted sources without the need to parse the values oneself. It is not capable of evaluating arbitrarily complex expressions, for example involving operators or indexing."
    https://docs.python.org/dev/library/ast.html#ast.literal_eval

    I don't think that it's a bug, but a deliberate design choice. a**b is an obvious trick to DoS a server (high CPU and memory usage).

    @ncoghlan
    Copy link
    Contributor

    @ncoghlan ncoghlan commented Jan 31, 2017

    Hugo, Serhiy, and Victor: I think you're all agreeing with each other, but to make sure I'm understanding the point correctly:

    1. ast.literal_eval() is currently safe from malicious code like "100000 ** 100000" or "1073741824 * 'a'" because it only traverses addition and subtraction nodes, so any such operations will just throw ValueError (As a point of interest: unary plus and minus are required to support positive and negative numeric literals, while binary addition and subtraction are required to support complex number literals. So the status quo isn't precisely the result of a conscious security decision, it's just a minimalist implementation of exactly what's necessary to support all of the builtin types, which also provides some highly desirable security properties when evaluating untrusted code)

    2. an eager constant folding optimisation in the AST tier would happen *before* literal_eval filtered out the multiplication and exponentiation nodes, and hence would make literal_eval vulnerable to remote DOS attacks in cases where it is expected to be safe

    However, that's not exactly how this patch works: if you pass "PyCF_ONLY_AST" as ast.parse does, it *doesn't* run the constant-folding step. Instead, the constant folding is run as an AST-to-AST transform during the AST-to-bytecode compilation step, *not* the initial source-to-AST step. (see http://bugs.python.org/issue11549#msg132361 )

    This has a few nice properties:

    • ast.literal_eval() remains safe
    • source -> AST -> source transformation pipelines continue to preserve the original code structure
    • externally generated AST structures still benefit from the AST optimisation pass
    • we don't need a new flag to turn this optimisation pass off when generating the AST for a given piece of source code

    @methane
    Copy link
    Member

    @methane methane commented Jan 31, 2017

    1. Changes to AST

    I'm working on updating this part. There are some failing tests remains.
    But I doubt this stage is worth enough for now.

    a) Merge Num, Str, Bytes and Ellipsis constructors into a single Lit (literal) that can hold anything. For one thing, this removes a good deal of copy-paste in the code, since these are always treated the same. (There were a couple of places where Bytes ctor was missing for no apparent reason, I think it was forgotten.) Otherwise, I would have to introduce at least 4 more node types: None, Bool, TupleConst, SetConst. This seemed excessive.

    We have already Constant and NameConstant. So it seems there are no need for
    None, Bool, TupleConst, SetConst nodes.

    I think converting Num, Str, Bytes, Ellipsis into Constant in folding stage
    is easier than fixing all tests.

    b) Docstring is now an attribute of Module, FunctionDef and ClassDef, rather than a first statement. Docstring is a special syntactic construction, it's not an executable code, so it makes sense to separate it. Otherwise, optimizer would have to take extra care not to introduce, change or remove docstring.

    Take docstring before constant folding isn't enough?
    (I'm sorry if I'm wrong. I haven't tried it yet.)

    c) 'None', 'True' and 'False' are parsed as literals instead of names, even without optimizations. Since they are not redefineable, I think it makes most sense to treat them as literals. This isn't strictly needed for folding, and I haven't removed all the artefacts, in case this turns out controversial.

    They are all NameConstant already.

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Feb 1, 2017

    We have already Constant and NameConstant. So it seems there are no need for
    None, Bool, TupleConst, SetConst nodes.
    Yes, Constant is Victor's version of Lit.

    I think converting Num, Str, Bytes, Ellipsis into Constant in folding stage
    is easier than fixing all tests.
    Fixing tests was fairly easy the last time. I think the question is what changes to the public API of AST are acceptable.

    Take docstring before constant folding isn't enough?
    (I'm sorry if I'm wrong. I haven't tried it yet.)
    It may be doable, but seems very messy. Instead of a clean pipeline text -> AST -> Optimized AST -> bytecode, you have to collect all docstrings, and pass them around in a side structure.

    With the current code there can be a simple fix. If original string literals are Str, but constant-folded string constants are Constant, only treat Strs as docstrings. Then the optimizer needs a change to always preserve Str as a first statement in a function/module, and that's it.
    I still think that having a dedicated docstring attribute in AST is cleaner, though.

    They are all NameConstant already.
    Keep in mind this patch is 6 years old :)

    @methane
    Copy link
    Member

    @methane methane commented Feb 1, 2017

    > We have already Constant and NameConstant. So it seems there are no need for
    > None, Bool, TupleConst, SetConst nodes.
    Yes, Constant is Victor's version of Lit.

    Then, may I remove ast.Lit, and use Constant and NameConstant?

    > I think converting Num, Str, Bytes, Ellipsis into Constant in folding stage
    > is easier than fixing all tests.
    Fixing tests was fairly easy the last time. I think the question is what changes to the public API of AST are acceptable.

    I think backward compatibility is not guaranteed.
    But there are some usage of ast. (https://github.com/search?l=Python&p=2&q=ast.Num&type=Code&utf8=%E2%9C%93 )

    So I think we should make change small as possible.

    > Take docstring before constant folding isn't enough?
    > (I'm sorry if I'm wrong. I haven't tried it yet.)
    It may be doable, but seems very messy. Instead of a clean pipeline text -> AST -> Optimized AST -> bytecode, you have to collect all docstrings, and pass them around in a side structure.

    With the current code there can be a simple fix. If original string literals are Str, but constant-folded string constants are Constant, only treat Strs as docstrings. Then the optimizer needs a change to always preserve Str as a first statement in a function/module, and that's it.
    I still think that having a dedicated docstring attribute in AST is cleaner, though.

    OK.

    > They are all NameConstant already.
    Keep in mind this patch is 6 years old :)

    I know. I want to move this patch forward, but I'm not frontend (parser, AST, and compiler) expert.
    I can't make design decision without expert's advice. Thanks for your reply.

    Then, may I update the patch in following direction?

    • Remove ast.Lit.
    • Keep docstring change.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Feb 1, 2017

    If you would like to implement constant folding at the AST level, I suggest
    you to look at my fatoptimizer project:
    https://github.com/haypo/fatoptimizer/blob/master/fatoptimizer/const_fold.py

    The tricky part is to avoid operations when we know that it will raise an
    exception or create an object too big according to our constraints.

    I would prefer to implement an AST optimizer in Python, but converting C
    structures to Python objects and then back to C structures has a cost. I'm
    not sure that my optimizer implemented in Python is fast enough.

    By the way, an idea would be to skip all optimizations in some cases like
    for script.py when running python3 script.py.

    @methane
    Copy link
    Member

    @methane methane commented Feb 1, 2017

    Before trying advanced optimizations, I want move suspended obvious optimizations forwards.

    For example, removing unused constants is suspended because constant folding
    should be moved from peephole to AST. This is why I found this issue.

    After that, I'm thinking about shrinking stacksize. frame_dealloc (scans whole stack) is one of hot functions.

    @brettcannon
    Copy link
    Member

    @brettcannon brettcannon commented Feb 1, 2017

    Dropping ast.Lit is fine. As for the docstring part, I'm torn. Yes it's nice as that will show up semantically in the Python code, but it's also easy to check for by just looking if the first statement is a Str (or Constant if that's what we make all strings). So I'll say I'm +0 on the docstring part.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Feb 1, 2017

    At the AST level, you have a wide range of possible optimizations. See the optimizations that I implemented in fatoptimizer (FAT Python) to have an idea:
    http://fatoptimizer.readthedocs.io/en/latest/optimizations.html

    FAT Python adds guards checked at runtime, something not possible (not wanted) here.

    But if you start with constant folding, why not implementing constant propagation as well? What about loop unrolling?

    Where is the limit? If you implement the AST optimizer in C, the limit will probably be your C skills and your motivation :-) In Python, the limit is more the Python semantics which is... hum... not well defined. For example, does it break the Python semantics to replace [i for i in (1, 2, 3)] with [1, 2, 3]?

    What if you use a debugger? Do yo expect a list comprehension or a literal list?

    FYI I suspended my work on FAT Python because almost no other core developer was interested. I didn't get any support, whereas I need support to push core FAT Python features like function specialization and runtime checks (PEP-510, see also PEP-511). Moreover, I failed to show any significant speedup on non-trivial functions. I abandoned before investigating function inlining, even if FAT Python already has a basic support for function inlining.

    This issue is open since 2011. The question is always the same: is it worth it?

    An alternative is to experiment an AST optimizer outside CPython and come back later with more data to drive the design of such optimizer. With FAT Python, I chose to add hooks in the Python compiler, but different people told me that it's possible to do that without such hook but importlib (importlib hooks).

    What do you think Naoki?

    @eltoder
    Copy link
    Mannequin Author

    @eltoder eltoder mannequin commented Feb 2, 2017

    Yes, doing optimizations on AST in CPython is unlikely to give any sizable speed improvements in real world programs. Python as a language is not suited for static optimization, and even if you manage to inline a function, there's still CPython's interpreted overhead and boxed types that dwarf the effect of the optimization.

    The goal of this patch was never to significantly improve the speed. It was to replace the existing bytecode peephole pass with cleaner and simpler code, which also happens to produce slightly better results.

    @methane
    Copy link
    Member

    @methane methane commented Feb 2, 2017

    My motivation is improve speed, reduce memory usage, and quicker
    startup time for real world applications. If some optimization in
    FAT optimizer has significant speedup, I want to try it.

    But this time, my motivation is I felt "everyone think constant folding
    should go to AST from peephole, there is a patch about it, but unfortunately
    it was suspended (because of lack of reviewers, maybe)."

    As reading bpo-28813, I think there are consensus about constant folding
    should go AST.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Feb 2, 2017

    INADA Naoki added the comment:

    My motivation is improve speed,

    Ah, if the motivation is performance, I would like to see benchmark
    results :-) I understand that an AST optimizer would help to produce
    more efficient bytecode, right?

    reduce memory usage,

    I noticed an issue with the peephole optimizer: the constant folding
    step keeps original constants. Moving constant folding to the AST
    stage fixes this issue by design.

    and quicker startup time for real world applications.

    You mean faster import time on precompiled .pyc files, right? It's
    related to the hypothetical faster bytecode.

    If some optimization in FAT optimizer has significant speedup, I want to try it.

    See http://fatoptimizer.readthedocs.io/en/latest/microbenchmarks.html#microbench

    FYI it took me something like 2 months to build FAT Python
    "infrastructure": fix CPython bugs, design guards, design the AST
    optimizer, write unit tests, etc. I didn't spend much time on
    efficient optimizations. But for my first rule was to not break the
    CPython test suite! Not break the Python semantics, otherwise it would
    be impossible to put enable the optimizer by default in CPython, which
    is my long term goal.

    @methane
    Copy link
    Member

    @methane methane commented Feb 6, 2017

    I've tried to update ast_opt.c[t] without changing AST.
    But I can't find clear way to solve "foo" + "bar" docstring problem.

    This patch adds only docstring to AST.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Feb 6, 2017

    Naoki: Can you please open a new issue for your ast-docstring.patch change? I like it, but this issue became too big, and I'm not sure that everyone in the nosy list is interested by this specific change.

    @methane
    Copy link
    Member

    @methane methane commented Feb 7, 2017

    I submit new issues:

    • bpo-29463 for AST change (change docstring from first statement to attribute).
    • bpo-29469 for constant folding

    Note that this issue contains more peephole -> AST optimization changes.
    But I want to start these two patch to ease review and discussion.

    @vstinner
    Copy link
    Member

    @vstinner vstinner commented Feb 7, 2017

    I created the issue bpo-29471: "AST: add an attribute to FunctionDef to distinguish functions from generators and coroutines".

    @rhettinger
    Copy link
    Contributor

    @rhettinger rhettinger commented Jan 26, 2020

    I think this particular issue can be closed in now. After it was written, the AST optimizer has been built-out and some peephole logic has moved.

    Other adjustments and improvements can be continue to be done in the other open issues.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.7 interpreter-core
    Projects
    None yet
    Development

    No branches or pull requests

    10 participants