Merged revisions 83852-83853,83857,84042,84216,84274-84276,84375,85388,85478,85506-85508 via svnmerge from

svn+ssh://pythondev@svn.python.org/sandbox/trunk/2to3/lib2to3

........
  r83852 | benjamin.peterson | 2010-08-08 15:45:44 -0500 (Sun, 08 Aug 2010) | 1 line

  wrap with parens
........
  r83853 | benjamin.peterson | 2010-08-08 15:46:31 -0500 (Sun, 08 Aug 2010) | 1 line

  use parens
........
  r83857 | benjamin.peterson | 2010-08-08 15:59:49 -0500 (Sun, 08 Aug 2010) | 1 line

  things which use touch_import should be pre order
........
  r84042 | george.boutsioukis | 2010-08-14 16:10:19 -0500 (Sat, 14 Aug 2010) | 2 lines

  This revision incorporates into the 2to3 tool the new, faster, tree matching algorithm developed during a GSOC project. The algorithm resides in the two added modules, btm_matcher and btm_utils. New code has been added to drive the new matching process in refactor.py and a few minor changes were made in other modules. A BM_compatible flag(False by default) has been added in fixer_base and it is set to True in most of the current fixers.
........
  r84216 | benjamin.peterson | 2010-08-19 16:44:05 -0500 (Thu, 19 Aug 2010) | 1 line

  allow star_expr in testlist_gexp
........
  r84274 | benjamin.peterson | 2010-08-22 18:40:46 -0500 (Sun, 22 Aug 2010) | 1 line

  wrap long line
........
  r84275 | benjamin.peterson | 2010-08-22 18:42:22 -0500 (Sun, 22 Aug 2010) | 1 line

  cleanup
........
  r84276 | benjamin.peterson | 2010-08-22 18:51:01 -0500 (Sun, 22 Aug 2010) | 1 line

  when there's a None value and a traceback, don't call type with it #9661
........
  r84375 | george.boutsioukis | 2010-08-31 08:38:53 -0500 (Tue, 31 Aug 2010) | 3 lines

  Idiomatic code changes & stylistic issues fixed in the BottomMatcher module. Thanks to Benjamin Peterson for taking the time to review the code.
........
  r85388 | benjamin.peterson | 2010-10-12 17:27:44 -0500 (Tue, 12 Oct 2010) | 1 line

  fix urllib fixer with multiple as imports on a line #10069
........
  r85478 | benjamin.peterson | 2010-10-14 08:09:56 -0500 (Thu, 14 Oct 2010) | 1 line

  stop abusing docstrings
........
  r85506 | benjamin.peterson | 2010-10-14 17:45:19 -0500 (Thu, 14 Oct 2010) | 1 line

  kill sibling import
........
  r85507 | benjamin.peterson | 2010-10-14 17:54:15 -0500 (Thu, 14 Oct 2010) | 1 line

  remove trailing whitespace
........
  r85508 | benjamin.peterson | 2010-10-14 17:55:28 -0500 (Thu, 14 Oct 2010) | 1 line

  typo
........

1 files changed, 83 insertions, 4 deletions

diff --git a/Lib/lib2to3/refactor.py b/Lib/lib2to3/refactor.py
index 4d83d20..54e00ee 100644
--- a/Lib/lib2to3/refactor.py
+++ b/Lib/lib2to3/refactor.py
@@ -24,7 +24,10 @@ from itertools import chain
 
 # Local imports
 from .pgen2 import driver, tokenize, token
+from .fixer_util import find_root
 from . import pytree, pygram
+from . import btm_utils as bu
+from . import btm_matcher as bm
 
 
 def get_all_fix_names(fixer_pkg, remove_prefix=True):
@@ -201,11 +204,28 @@ class RefactoringTool(object):
                                     logger=self.logger)
         self.pre_order, self.post_order = self.get_fixers()
 
-        self.pre_order_heads = _get_headnode_dict(self.pre_order)
-        self.post_order_heads = _get_headnode_dict(self.post_order)
 
         self.files = []  # List of files that were or should be modified
 
+        self.BM = bm.BottomMatcher()
+        self.bmi_pre_order = [] # Bottom Matcher incompatible fixers
+        self.bmi_post_order = []
+
+        for fixer in chain(self.post_order, self.pre_order):
+            if fixer.BM_compatible:
+                self.BM.add_fixer(fixer)
+                # remove fixers that will be handled by the bottom-up
+                # matcher
+            elif fixer in self.pre_order:
+                self.bmi_pre_order.append(fixer)
+            elif fixer in self.post_order:
+                self.bmi_post_order.append(fixer)
+
+        self.bmi_pre_order_heads = _get_headnode_dict(self.bmi_pre_order)
+        self.bmi_post_order_heads = _get_headnode_dict(self.bmi_post_order)
+
+
+
     def get_fixers(self):
         """Inspects the options to load the requested patterns and handlers.
 
@@ -268,6 +288,7 @@ class RefactoringTool(object):
 
     def refactor(self, items, write=False, doctests_only=False):
         """Refactor a list of files and directories."""
+
         for dir_or_file in items:
             if os.path.isdir(dir_or_file):
                 self.refactor_dir(dir_or_file, write, doctests_only)
@@ -378,6 +399,10 @@ class RefactoringTool(object):
     def refactor_tree(self, tree, name):
         """Refactors a parse tree (modifying the tree in place).
 
+        For compatible patterns the bottom matcher module is
+        used. Otherwise the tree is traversed node-to-node for
+        matches.
+
         Args:
             tree: a pytree.Node instance representing the root of the tree
                   to be refactored.
@@ -386,11 +411,65 @@ class RefactoringTool(object):
         Returns:
             True if the tree was modified, False otherwise.
         """
+
         for fixer in chain(self.pre_order, self.post_order):
             fixer.start_tree(tree, name)
 
-        self.traverse_by(self.pre_order_heads, tree.pre_order())
-        self.traverse_by(self.post_order_heads, tree.post_order())
+        #use traditional matching for the incompatible fixers
+        self.traverse_by(self.bmi_pre_order_heads, tree.pre_order())
+        self.traverse_by(self.bmi_post_order_heads, tree.post_order())
+
+        # obtain a set of candidate nodes
+        match_set = self.BM.run(tree.leaves())
+
+        while any(match_set.values()):
+            for fixer in self.BM.fixers:
+                if fixer in match_set and match_set[fixer]:
+                    #sort by depth; apply fixers from bottom(of the AST) to top
+                    match_set[fixer].sort(key=pytree.Base.depth, reverse=True)
+
+                    if fixer.keep_line_order:
+                        #some fixers(eg fix_imports) must be applied
+                        #with the original file's line order
+                        match_set[fixer].sort(key=pytree.Base.get_lineno)
+
+                    for node in list(match_set[fixer]):
+                        if node in match_set[fixer]:
+                            match_set[fixer].remove(node)
+
+                        try:
+                            find_root(node)
+                        except AssertionError:
+                            # this node has been cut off from a
+                            # previous transformation ; skip
+                            continue
+
+                        if node.fixers_applied and fixer in node.fixers_applied:
+                            # do not apply the same fixer again
+                            continue
+
+                        results = fixer.match(node)
+
+                        if results:
+                            new = fixer.transform(node, results)
+                            if new is not None:
+                                node.replace(new)
+                                #new.fixers_applied.append(fixer)
+                                for node in new.post_order():
+                                    # do not apply the fixer again to
+                                    # this or any subnode
+                                    if not node.fixers_applied:
+                                        node.fixers_applied = []
+                                    node.fixers_applied.append(fixer)
+
+                                # update the original match set for
+                                # the added code
+                                new_matches = self.BM.run(new.leaves())
+                                for fxr in new_matches:
+                                    if not fxr in match_set:
+                                        match_set[fxr]=[]
+
+                                    match_set[fxr].extend(new_matches[fxr])
 
         for fixer in chain(self.pre_order, self.post_order):
             fixer.finish_tree(tree, name)