Repository navigation
Trailing whitespace makes tokenize.generate_tokens pathological #60356
Description
| BPO | 16152 |
|---|---|
| Nosy | @jcea, @vstinner, @nedbat, @ezio-melotti |
| PRs | |
| Files |
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 = 'https://github.com/ezio-melotti'
closed_at = <Date 2012-11-03.15:53:58.477>
created_at = <Date 2012-10-06.21:09:21.224>
labels = ['type-bug', 'library']
title = 'Trailing whitespace makes tokenize.generate_tokens pathological'
updated_at = <Date 2018-04-23.01:26:42.255>
user = 'https://github.com/nedbat'bugs.python.org fields:
activity = <Date 2018-04-23.01:26:42.255>
actor = 'nedbat'
assignee = 'ezio.melotti'
closed = True
closed_date = <Date 2012-11-03.15:53:58.477>
closer = 'ezio.melotti'
components = ['Library (Lib)']
creation = <Date 2012-10-06.21:09:21.224>
creator = 'nedbat'
dependencies = []
files = ['27466', '27467']
hgrepos = []
issue_num = 16152
keywords = ['patch']
message_count = 8.0
messages = ['172244', '172246', '172276', '172546', '172548', '174640', '174641', '315641']
nosy_count = 5.0
nosy_names = ['jcea', 'vstinner', 'nedbat', 'ezio.melotti', 'python-dev']
pr_nums = ['6572']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue16152'
versions = ['Python 2.7', 'Python 3.2', 'Python 3.3', 'Python 3.4']
Activity
nedbat commentedon Oct 6, 2012
When tokenizing with tokenize.generate_tokens, if the code ends with whitespace (no newline), the tokenizer produces an ERRORTOKEN for each space. Additionally, the regex that fails to find tokens in those spaces is linear in the number of spaces, so the overall performance is O(n**2).
I found this while tokenizing code samples uploaded to a public web site. One sample for some reason ended with 40,000 spaces, which was taking two hours to tokenize.
Demonstration:
{{{
import token
import tokenize
try:
from cStringIO import StringIO
except:
from io import StringIO
code = "@"+" "*10000
code_reader = StringIO(code).readline
nedbat commentedon Oct 6, 2012
Here's a patch for 3.3.
I would like to also fix 2.7...
nedbat commentedon Oct 7, 2012
Updated with new (better) patch, for v2.7 and v3.3. They are the same except for the test.
jcea commentedon Oct 10, 2012
Ned, could you possibly send a Contributor Form Agreement? http://www.python.org/psf/contrib/
nedbat commentedon Oct 10, 2012
Jesús, done!
python-dev commentedon Nov 3, 2012
New changeset eb7ea51e658e by Ezio Melotti in branch '2.7':
bpo-16152: fix tokenize to ignore whitespace at the end of the code when no newline is found. Patch by Ned Batchelder.
http://hg.python.org/cpython/rev/eb7ea51e658e
New changeset 3ffff1798ed5 by Ezio Melotti in branch '3.2':
bpo-16152: fix tokenize to ignore whitespace at the end of the code when no newline is found. Patch by Ned Batchelder.
http://hg.python.org/cpython/rev/3ffff1798ed5
New changeset 1fdeddabddda by Ezio Melotti in branch '3.3':
bpo-16152: merge with 3.2.
http://hg.python.org/cpython/rev/1fdeddabddda
New changeset ed091424f230 by Ezio Melotti in branch 'default':
bpo-16152: merge with 3.3.
http://hg.python.org/cpython/rev/ed091424f230
ezio-melotti commentedon Nov 3, 2012
Fixed, thanks for the report and the patch!
nedbat commentedon Apr 23, 2018
PR 6273 is mentioned, but I think 6573 is the correct number.