Cache child sibling lookups

Removes catastrophically quadratic behavior on nodes with very many siblings.

diff --git a/README.md b/README.md
index 440f42b19b20c97e0e5b6ee3460b8ef65196c787..67cd613cb62b356239971d617179dbb4fdd1bed1 100644 (file)
--- a/README.md
+++ b/README.md
@@ -814,6 +814,8 @@ More details can be found in [CONTRIBUTING](CONTRIBUTING.md).
 
 * fixed unnecessary slowdown when long list literals where found in a file
 
 
 * fixed unnecessary slowdown when long list literals where found in a file
 

+* fixed unnecessary slowdown on AST nodes with very many siblings
+

 
 ### 18.6b2
 
 
 ### 18.6b2
 

diff --git a/blib2to3/pytree.py b/blib2to3/pytree.py
index 693366f7b2e4fb3bba6ad237aefa8bfca7904dc3..b24866e29269ebde7893c1fd893b0254ea58b658 100644 (file)
--- a/blib2to3/pytree.py
+++ b/blib2to3/pytree.py
@@ -115,8 +115,9 @@ class Base(object):
             else:
                 l_children.append(ch)
         assert found, (self.children, self, new)
             else:
                 l_children.append(ch)
         assert found, (self.children, self, new)

-        self.parent.changed()

         self.parent.children = l_children
         self.parent.children = l_children

+        self.parent.changed()
+        self.parent.invalidate_sibling_maps()

         for x in new:
             x.parent = self.parent
         self.parent = None
         for x in new:
             x.parent = self.parent
         self.parent = None


@@ -143,8 +144,9 @@ class Base(object):
         if self.parent:
             for i, node in enumerate(self.parent.children):
                 if node is self:
         if self.parent:
             for i, node in enumerate(self.parent.children):
                 if node is self:

-                    self.parent.changed()

                     del self.parent.children[i]
                     del self.parent.children[i]

+                    self.parent.changed()
+                    self.parent.invalidate_sibling_maps()

                     self.parent = None
                     return i
 
                     self.parent = None
                     return i
 


@@ -157,13 +159,9 @@ class Base(object):
         if self.parent is None:
             return None
 
         if self.parent is None:
             return None
 

-        # Can't use index(); we need to test by identity
-        for i, child in enumerate(self.parent.children):
-            if child is self:
-                try:
-                    return self.parent.children[i+1]
-                except IndexError:
-                    return None
+        if self.parent.next_sibling_map is None:
+            self.parent.update_sibling_maps()
+        return self.parent.next_sibling_map[id(self)]

 
     @property
     def prev_sibling(self):
 
     @property
     def prev_sibling(self):


@@ -174,12 +172,9 @@ class Base(object):
         if self.parent is None:
             return None
 
         if self.parent is None:
             return None
 

-        # Can't use index(); we need to test by identity
-        for i, child in enumerate(self.parent.children):
-            if child is self:
-                if i == 0:
-                    return None
-                return self.parent.children[i-1]
+        if self.parent.prev_sibling_map is None:
+            self.parent.update_sibling_maps()
+        return self.parent.prev_sibling_map[id(self)]

 
     def leaves(self):
         for child in self.children:
 
     def leaves(self):
         for child in self.children:


@@ -226,6 +221,7 @@ class Node(Base):
         for ch in self.children:
             assert ch.parent is None, repr(ch)
             ch.parent = self
         for ch in self.children:
             assert ch.parent is None, repr(ch)
             ch.parent = self

+        self.invalidate_sibling_maps()

         if prefix is not None:
             self.prefix = prefix
         if fixers_applied:
         if prefix is not None:
             self.prefix = prefix
         if fixers_applied:


@@ -294,6 +290,7 @@ class Node(Base):
         self.children[i].parent = None
         self.children[i] = child
         self.changed()
         self.children[i].parent = None
         self.children[i] = child
         self.changed()

+        self.invalidate_sibling_maps()

 
     def insert_child(self, i, child):
         """
 
     def insert_child(self, i, child):
         """


@@ -303,6 +300,7 @@ class Node(Base):
         child.parent = self
         self.children.insert(i, child)
         self.changed()
         child.parent = self
         self.children.insert(i, child)
         self.changed()

+        self.invalidate_sibling_maps()

 
     def append_child(self, child):
         """
 
     def append_child(self, child):
         """


@@ -312,7 +310,21 @@ class Node(Base):
         child.parent = self
         self.children.append(child)
         self.changed()
         child.parent = self
         self.children.append(child)
         self.changed()

-
+        self.invalidate_sibling_maps()
+
+    def invalidate_sibling_maps(self):
+        self.prev_sibling_map = None
+        self.next_sibling_map = None
+
+    def update_sibling_maps(self):
+        self.prev_sibling_map = _prev = {}
+        self.next_sibling_map = _next = {}
+        previous = None
+        for current in self.children:
+            _prev[id(current)] = previous
+            _next[id(previous)] = current
+            previous = current
+        _next[id(current)] = None

 
 class Leaf(Base):
 
 
 class Leaf(Base):