Python3.10.5 Pattern Matching Excessive Memory Consumption

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.

Wow. I can reproduce this on 3.11 and 3.12(main) too.

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

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

match p:
    case [[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]:
        pass

@tom-p-reichel

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

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

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

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

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

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

Revert 30935 defer bpo45162 to 312 (#94285)

Navigation Menu

Repository navigation

Python3.10.5 Pattern Matching Excessive Memory Consumption #93671

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Python3.10.5 Pattern Matching Excessive Memory Consumption #93671

Description

Activity

Fidget-Spinner commented on Jun 10, 2022

kumaraditya303 commented on Jun 10, 2022

dignissimus commented on Jun 10, 2022

pablogsal commented on Jun 10, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions