classification
Title: 2to3 Iterative Wildcard Matching
Type: Stage:
Components: 2to3 (2.x to 3.x conversion tool) Versions:
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: collinwinter Nosy List: benjamin.peterson, collinwinter, nedds
Priority: normal Keywords: patch

Created on 2008-07-15 04:12 by nedds, last changed 2008-10-03 17:09 by collinwinter. This issue is now closed.

Files
File name Uploaded Description Edit
iterative.diff nedds, 2008-07-15 04:12 Diff for iterative changes
iterative_recursive.diff nedds, 2008-08-04 16:06 Diff for pytree with iterative and recursive matching
Messages (16)
msg69672 - (view) Author: Nick Edds (nedds) Date: 2008-07-15 04:12
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.
msg69958 - (view) Author: Nick Edds (nedds) Date: 2008-07-18 17:00
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.
msg70242 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2008-07-25 05:26
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.
msg70278 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2008-07-25 21:10
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?
msg70282 - (view) Author: Nick Edds (nedds) Date: 2008-07-25 21:22
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?
msg70330 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2008-07-27 23:07
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.
msg70332 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2008-07-28 00:13
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>
> _______________________________________
>
msg70333 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2008-07-28 00:15
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?
msg70336 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2008-07-28 01:50
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.
msg70619 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2008-08-02 03:41
Nick, what do you think about that?
msg70620 - (view) Author: Nick Edds (nedds) Date: 2008-08-02 03:42
Sounds good to me. I should have a chance to implement this and submit
it within the next couple of days.
msg70705 - (view) Author: Nick Edds (nedds) Date: 2008-08-04 16:06
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.
msg73154 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2008-09-12 23:51
Nick, it would be nice if your patch had a test.
msg73914 - (view) Author: Nick Edds (nedds) Date: 2008-09-27 02:24
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?
msg73916 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2008-09-27 02:35
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.
msg74263 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2008-10-03 17:09
Applied as r66775. I used the example file from issue2532 as test data.

Thanks for the patch, Nick!
History
Date User Action Args
2008-10-03 17:09:47collinwintersetstatus: open -> closed
resolution: fixed
messages: + msg74263
2008-09-27 02:35:59benjamin.petersonsetmessages: + msg73916
2008-09-27 02:24:14neddssetmessages: + msg73914
2008-09-12 23:51:19benjamin.petersonsetmessages: + msg73154
2008-08-04 16:06:01neddssetfiles: + iterative_recursive.diff
messages: + msg70705
2008-08-02 03:42:47neddssetmessages: + msg70620
2008-08-02 03:41:03collinwintersetmessages: + msg70619
2008-07-28 01:50:51benjamin.petersonsetmessages: + msg70336
2008-07-28 00:15:56collinwintersetmessages: + msg70333
2008-07-28 00:13:03benjamin.petersonsetmessages: + msg70332
2008-07-27 23:07:17collinwintersetmessages: + msg70330
2008-07-25 21:22:12neddssetmessages: + msg70282
2008-07-25 21:10:29benjamin.petersonsetnosy: + benjamin.peterson
messages: + msg70278
2008-07-25 05:26:04collinwintersetmessages: + msg70242
2008-07-18 17:00:19neddssetmessages: + msg69958
2008-07-15 04:12:28neddscreate