2to3 Iterative Wildcard Matching

[nedds]

BPO	3358
Nosy	@benjaminp
Files	iterative.diff: Diff for iterative changes iterative_recursive.diff: Diff for pytree with iterative and recursive matching

^{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 2008-10-03.17:09:47.824>
created_at = <Date 2008-07-15.04:12:28.466>
labels = ['expert-2to3']
title = '2to3 Iterative Wildcard Matching'
updated_at = <Date 2008-10-03.17:09:47.822>
user = 'https://bugs.python.org/nedds'

bugs.python.org fields:

activity = <Date 2008-10-03.17:09:47.822>
actor = 'collinwinter'
assignee = 'collinwinter'
closed = True
closed_date = <Date 2008-10-03.17:09:47.824>
closer = 'collinwinter'
components = ['2to3 (2.x to 3.x conversion tool)']
creation = <Date 2008-07-15.04:12:28.466>
creator = 'nedds'
dependencies = []
files = ['10896', '11058']
hgrepos = []
issue_num = 3358
keywords = ['patch']
message_count = 16.0
messages = ['69672', '69958', '70242', '70278', '70282', '70330', '70332', '70333', '70336', '70619', '70620', '70705', '73154', '73914', '73916', '74263']
nosy_count = 3.0
nosy_names = ['collinwinter', 'benjamin.peterson', 'nedds']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue3358'
versions = []

[nedds]

Here is an iterative replacement to _recursive_matches for Wildcard
Patterns. It's not really much faster now, although I think there is
some room to improve it. It's doesn't seem like the most elegant
solution, but it works. It passes all of the tests, although I had to
rewrite one because it was generating the same matches but in a
different order.

[nedds]

Just as an added note: with the new changes made to fix_imports, this is
now noticeably slower than the recursive approach, even after I made a
few optimizations like removing the unnecessary len() in the while loop.

[collinwinter]

Yeah, benchmarking this change against the unmodified HEAD, the
iterative version runs the test suite much slower. Let's file this under
the "didn't work out" category. It was a good idea that you obviated
with the fix_imports improvements.

[benjaminp]

Maybe this is a bad idea, but would it be possible/reasonable to provide
recursive and iterative implementations and use the iterative one on
large files?

[nedds]

I don't think it would be hard to implement, I just need a good, fast
metric to determine if a file should be processed iteratively or
recursively. What do you think would be the best way to do this?

[collinwinter]

One option would be to use the faster recursive version, falling back to
the iterative version if you hit a "RuntimeError: maximum recursion
depth exceeded" error. This would keep the speed for most files, but
would allow 2to3 to parse files like the one in bpo-2532.

[benjaminp]

On Sun, Jul 27, 2008 at 6:07 PM, Collin Winter <report@bugs.python.org> wrote:

Collin Winter <collinw@gmail.com> added the comment:

One option would be to use the faster recursive version, falling back to
the iterative version if you hit a "RuntimeError: maximum recursion
depth exceeded" error. This would keep the speed for most files, but
would allow 2to3 to parse files like the one in bpo-2532.

Sounds fine to me. I think we should provide a command line switch, too

---

Python tracker <report@bugs.python.org>
<http://bugs.python.org/issue3358\>

---

[collinwinter]

Why include a command-line flag? Would you know when to use it? In what
cases would you want to second-guess the app like that?

[benjaminp]

Never mind. I had thought it would take a while for the RuntimeError to
be generated, but it only took about 7 seconds; I have no need for a
command line switch.

[collinwinter]

Nick, what do you think about that?

[nedds]

Sounds good to me. I should have a chance to implement this and submit
it within the next couple of days.

[nedds]

Here is a patch that tries to use the faster recursive matching, but if
there is a RuntimeError, it will use the iterative matching. It passes
all the tests and works on the ssl.py file that were known to break the
recursive matching.

[benjaminp]

Nick, it would be nice if your patch had a test.

[nedds]

What do you think would be the best way to implement a test for this? To
test it, I ran it on a known file that caused the old recursive method
to fail, but I don't know if it makes sense to include that with the
tests. I could always write a test to verify that the iterative element
works, but as for testing the transition from recursive to iterative
when the recursion limit is exceeded, do you think that is something I
should do, and is there a better way than simply including the file that
I know causes the recursion limit to be exceeded?

[benjaminp]

On Fri, Sep 26, 2008 at 9:24 PM, Nick Edds <report@bugs.python.org> wrote:

Nick Edds <nedds@uchicago.edu> added the comment:

What do you think would be the best way to implement a test for this? To
test it, I ran it on a known file that caused the old recursive method
to fail, but I don't know if it makes sense to include that with the
tests. I could always write a test to verify that the iterative element
works, but as for testing the transition from recursive to iterative
when the recursion limit is exceeded, do you think that is something I
should do, and is there a better way than simply including the file that
I know causes the recursion limit to be exceeded?

I recommend generating a deeply nested structure and/or using
sys.setrecursionlimit to make the recursion limit artificially low,
and testing that refactoring works as planned.

[collinwinter]

Applied as r66775. I used the example file from bpo-2532 as test data.

Thanks for the patch, Nick!