Description

tom-p-reichel

opened on Jun 10, 2022

Issue body actions

Crash report

While writing some code to match a particularly complicated AST, I accidentally wrote a function whose definition causes the Python 3.10.5 interpreter to rapidly consume memory. On my system, it consumed approximately 24 GBs of memory before being killed.

The function is as follows:

def defines(self):
        match self.ast:
                case [S('CoqAst'), [[S('v'), [_, _, [S('expr'), [S('VernacDefinition'), [S('NoDischarge'), S('Definition')], [[[S('v'), [S('Name'), [S('Id'), S(name)]]], _], []], [S('DefineBody'), [], [], [_, _], []]]]]], _]]
                | [S('CoqAst'), [[S('v'), [[S('control'), []], [S('attrs'), []], [S('expr'), [S('VernacStartTheoremProof'), S('Theorem'), [[[[[S('v'), [S('Id'), name]], _], []], _]]]]]], _]]:
                        return name

To replicate, paste the above function into a python file and run it.

Error messages

OOM killing produced no output, save for Killed.

Your environment

• CPython versions tested on: 3.10.5
• Operating system and architecture: Tested on both Windows 10 and ArchLinux.

Activity

1. tom-p-reichel

   added

   type-crashA hard crash of the interpreter, possibly with a core dumpA hard crash of the interpreter, possibly with a core dump

   on Jun 10, 2022
2. AlexWaygood

   assigned

   brandtbucher

   on Jun 10, 2022
3. Fidget-Spinner commented on Jun 10, 2022

   

   Fidget-Spinner

   on Jun 10, 2022

   Member

   More actions

   Wow. I can reproduce this on 3.11 and 3.12(main) too.
4. Fidget-Spinner

   added

   3.11only security fixesonly security fixes

   3.10 (EOL)end of lifeend of life

   3.12only security fixesonly security fixes

   on Jun 10, 2022
5. kumaraditya303 commented on Jun 10, 2022

   

   kumaraditya303

   on Jun 10, 2022

   Contributor

   More actions

   This seems like a parser issue.

   Linux perf output:

   Samples: 36K of event 'cpu-clock:pppH', Event count (approx.): 9100000000
   Overhead  Command  Shared Object       Symbol
      7.30%  python   python              [.] _PyPegen_expect_token
      6.68%  python   [kernel.kallsyms]   [k] clear_page_erms
      6.28%  python   [kernel.kallsyms]   [k] __do_page_fault
      4.64%  python   python              [.] closed_pattern_rule
      4.09%  python   python              [.] _PyArena_Malloc
      3.36%  python   python              [.] signed_real_number_rule
      3.09%  python   libc-2.31.so        [.] _int_malloc
      3.05%  python   python              [.] or_pattern_rule
      2.84%  python   python              [.] unicodekeys_lookup_unicode
6. dignissimus commented on Jun 10, 2022

   

   dignissimus

   on Jun 10, 2022

   Contributor

   More actions

   It might be the related to the depth of the statement, the following also produces a crash

   match p:
       case [[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]:
           pass
7. kumaraditya303

   assigned

   pablogsal

   on Jun 10, 2022
8. pablogsal commented on Jun 10, 2022

   

   pablogsal

   on Jun 10, 2022

   Member

   More actions

   Thanks, @tom-p-reichel and @dignissimus for the report and thanks a lot @kumaraditya303 for the initial investigation. Great work!

   Reacted by Kumar Aditya and Talia Ringer
9. ambv

   closed this as completedin #93680on Jun 10, 2022
10. ambv

    added a commit that references this issue on Jun 10, 2022

    gh-93671: Avoid exponential backtracking in deeply nested sequence pa…

    53a8b17
11. miss-islington

    added 2 commits that reference this issue on Jun 10, 2022

    pythongh-93671: Avoid exponential backtracking in deeply nested seque…

    af70c4f

    gh-93671: Avoid exponential backtracking in deeply nested sequence pa…

    f9d0240
12. pablogsal

    added 2 commits that reference this issue on Jun 10, 2022

    [3.10] pythongh-93671: Avoid exponential backtracking in deeply neste…

    fd56269

    [3.10] gh-93671: Avoid exponential backtracking in deeply nested sequ…

    8f36c73
13. serhiy-storchaka

    added a commit that references this issue on Jun 26, 2022

    Revert 30935 defer bpo45162 to 312 (#94285)

    1ffde3e

Issue actions