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.

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.

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.

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?

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?

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 issue 2532.

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 issue 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>
> _______________________________________
>

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?

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.

Nick, what do you think about that?

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

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.

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

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?

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.

Applied as r66775. I used the example file from issue2532 as test data.

Thanks for the patch, Nick!