[StGIT PATCH 2/4] Speed up appliedness check during patch creation

["Karl Hasselström" <kha@treskal.com>]

When we create a new patch commit that isn't next to an existing patch
commit (which occurs e.g. every time we push the first patch onto a
stack), we do a full recalculation of the set of uninteresting
commits. However, if we know that the new patch refers to a new
commit, we only have to see if this new commit can reach any existing
patch, which is a much cheaper operation.

Signed-off-by: Karl Hasselström <kha@treskal.com>

---

 stgit/stack.py |   54 ++++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 42 insertions(+), 12 deletions(-)

diff --git a/stgit/stack.py b/stgit/stack.py
index d3756d0..8f1c0ee 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -485,9 +485,13 @@ class UninterestingCache:
 
         self.__uninteresting = uninteresting
         out.done()
-    def create_patch(self, name, top, bottom):
+    def create_patch(self, name, top, bottom, new_commit):
         """The given patch has been created. Update the uninterested
-        state to maintain the invariant."""
+        state to maintain the invariant.
+
+        If new_commit is true, the caller is promising that top is a
+        new commit that isn't reachable from any of the previously
+        existing uninteresting commits."""
         if not self.__cache_file():
             return # not cached
 
@@ -507,6 +511,28 @@ class UninterestingCache:
         if bottom in bottoms or bottom in tops or top in bottoms:
             return
 
+        if new_commit:
+            # The caller has promised us that no existing
+            # uninteresting commit reaches the new patch, which means
+            # that they are all still valid. Now all we have to do is
+            # decide whether to add the new patch's bottom to the set
+            # of uninteresting commits.
+            ref2hash = read_refs(self.__series.get_name())
+            patches = Set([sha1 for ref, sha1 in ref2hash.iteritems() if ref])
+            for commit in git._output_lines('git-rev-list --stdin %s' % bottom,
+                                          ['^%s\n' % u for u in
+                                           self.__uninteresting]):
+                if commit in patches:
+                    # The bottom of the new patch reaches another
+                    # patch, and so isn't uninteresting.
+                    return
+
+            # The bottom of the new patch doesn't reach any other
+            # patch, so it must be uninteresting.
+            self.__uninteresting.add(bottom)
+            self.__write_file()
+            return
+
         # The new patch is not adjacent to an existing patch. We'd
         # need to first get rid of any uninteresting commit that
         # reaches this patch, and then mark the patch's bottom
@@ -619,16 +645,17 @@ class AppliedCache:
                 self.__write_patchorder()
                 return
         raise StackException, 'Unknown patch "%s"' % oldname
-    def new(self, name, top, bottom):
+    def new(self, name, top, bottom, new_commit):
         """Create new patch."""
-        self.__uninteresting.create_patch(name, top, bottom)
+        self.__uninteresting.create_patch(name, top, bottom, new_commit)
     def delete(self, name, top, bottom):
         """Delete a patch."""
         self.__uninteresting.delete_patch(name, top, bottom)
-    def change(self, name, old_top, old_bottom, new_top, new_bottom):
+    def change(self, name, old_top, old_bottom, new_top, new_bottom,
+               new_commit):
         """Change a patch."""
         if (new_top, new_bottom) != (old_top, old_bottom):
-            self.new(name, new_top, new_bottom)
+            self.new(name, new_top, new_bottom, new_commit)
             self.delete(name, old_top, old_bottom)
     def __write_patchorder(self):
         self.__order.set_patchorder(self.get_applied() + self.get_unapplied())
@@ -1128,7 +1155,7 @@ class Series(PatchSet):
         if patch.restore_old_boundaries():
             self.log_patch(patch, 'undo')
         self.__applied_cache.change(name, curr_top, curr_bottom,
-                                    old_top, old_bottom)
+                                    old_top, old_bottom, new_commit = False)
 
     def new_patch(self, name, message = None, can_edit = True,
                   unapplied = False, show_patch = False,
@@ -1163,7 +1190,6 @@ class Series(PatchSet):
 
         bottom = bottom or head
         top = top or head
-        self.__applied_cache.new(name, top, bottom)
 
         patch.set_bottom(bottom)
         patch.set_top(top)
@@ -1197,10 +1223,12 @@ class Series(PatchSet):
                                    committer_name = committer_name,
                                    committer_email = committer_email)
             # set the patch top to the new commit
+            top = commit_id
             patch.set_top(commit_id)
 
         self.log_patch(patch, 'new')
 
+        self.__applied_cache.new(name, top, bottom, new_commit = commit)
         self.__applied_cache.set_patchorder(order)
         return patch
 
@@ -1291,7 +1319,7 @@ class Series(PatchSet):
 
                     self.__applied_cache.change(
                         name, old_top = old_top, old_bottom = bottom,
-                        new_top = top, new_bottom = head)
+                        new_top = top, new_bottom = head, new_commit = True)
                     self.log_patch(patch, 'push(f)')
                 else:
                     top = head
@@ -1349,7 +1377,8 @@ class Series(PatchSet):
             # need an empty commit
             patch.set_bottom(head, backup = True)
             patch.set_top(head, backup = True)
-            self.__applied_cache.change(name, top, bottom, head, head)
+            self.__applied_cache.change(name, top, bottom, head, head,
+                                        new_commit = False)
             modified = True
         elif head == bottom:
             # reset the backup information. No need for logging
@@ -1362,7 +1391,8 @@ class Series(PatchSet):
             # The current patch is empty after merge.
             patch.set_bottom(head, backup = True)
             patch.set_top(head, backup = True)
-            self.__applied_cache.change(name, top, bottom, head, head)
+            self.__applied_cache.change(name, top, bottom, head, head,
+                                        new_commit = False)
 
             # Try the fast applying first. If this fails, fall back to the
             # three-way merge
@@ -1422,7 +1452,7 @@ class Series(PatchSet):
         self.pop_patch(name)
         ret = patch.restore_old_boundaries()
         self.__applied_cache.change(name, curr_top, curr_bottom,
-                                    old_top, old_bottom)
+                                    old_top, old_bottom, new_commit = False)
         if ret:
             self.log_patch(patch, 'undo')