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

Jump to bottom

Regexp match goes into infinite loop #59282

Closed
moriyoshi mannequin opened this issue Jun 15, 2012 · 5 comments
Closed

Regexp match goes into infinite loop #59282

moriyoshi mannequin opened this issue Jun 15, 2012 · 5 comments
Labels
topic-regex type-crash A hard crash of the interpreter, possibly with a core dump

Comments

@moriyoshi
Copy link
Mannequin

moriyoshi mannequin commented Jun 15, 2012

BPO 15077
Nosy @ezio-melotti, @moriyoshi, @serhiy-storchaka
Files
  • x.py
    		•

    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 2012-08-05.10:31:46.664>
created_at = <Date 2012-06-15.10:41:09.455>
labels = ['expert-regex', 'invalid', 'type-crash']
title = 'Regexp match goes into infinite loop'
updated_at = <Date 2012-08-05.10:31:46.663>
user = 'https://github.com/moriyoshi'

    bugs.python.org fields:

    activity = <Date 2012-08-05.10:31:46.663>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2012-08-05.10:31:46.664>
closer = 'serhiy.storchaka'
components = ['Regular Expressions']
creation = <Date 2012-06-15.10:41:09.455>
creator = 'moriyoshi'
dependencies = []
files = ['26016']
hgrepos = []
issue_num = 15077
keywords = []
message_count = 5.0
messages = ['162883', '162896', '164280', '164281', '164283']
nosy_count = 4.0
nosy_names = ['ezio.melotti', 'mrabarnett', 'moriyoshi', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = None
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue15077'
versions = ['Python 2.7']
    @moriyoshi
    Copy link
    Mannequin Author

    moriyoshi mannequin commented Jun 15, 2012

    A peculiar pair of a regexp and a target string causes the runtime into an infinite loop. The same expression works with Perl.

    @moriyoshi moriyoshi mannequin added topic-regex type-crash A hard crash of the interpreter, possibly with a core dump labels Jun 15, 2012
    @serhiy-storchaka
    Copy link
    Member

    This is not infinite loop. This is O(2**len(prefix_before_first_quote)) computation. Measure times of matching for "INSER(id...", "INSERT(id...", "INSERT (id...", "INSERT I(id...", etc.

    Better use r'''(?:[^\`';]+|'(?:''|[^'])'|`(?:``|[^\`])`)+;''' regexp.

    @serhiy-storchaka
    Copy link
    Member

    I think it's a bug. The issue can be closed.

    @serhiy-storchaka
    Copy link
    Member

    I think it's *not* a bug. The issue can be closed.

    @mrabarnett
    Copy link
    Mannequin

    mrabarnett mannequin commented Jun 28, 2012

    It's not a bug, it's a pathological regex (i.e. it causes catastrophic backtracking).

    It also works correctly in the "regex" module.

    @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
    Assignees
    No one assigned
    Labels
    topic-regex type-crash A hard crash of the interpreter, possibly with a core dump
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    1 participant
    @serhiy-storchaka