patch, 4 partsSpeed up the discovery of uninteresting commits

diff --git a/stgit/stack.py b/stgit/stack.py
index 1b6808e..d3756d0 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -472,11 +472,17 @@ class UninterestingCache:
                 for p in parents:
                     if not p in interesting:
                         uninteresting.add(p)
-                continue
+
+                # If this is the last patch commit, there is no way we
+                # can encounter any more uninteresting commits.
+                patches.remove(commit)
+                if not patches:
+                    break
 
             # Commits with interesting parents are interesting.
-            if interesting.intersection(parents):
+            elif interesting.intersection(parents):
                 interesting.add(commit)
+
         self.__uninteresting = uninteresting
         out.done()
     def create_patch(self, name, top, bottom):

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')
 

diff --git a/stgit/stack.py b/stgit/stack.py
index 8f1c0ee..dbb27eb 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -459,7 +459,8 @@ class UninterestingCache:
         # Iterate over all commits. We are guaranteed to see each
         # commit before any of its children.
         for line in git._output_lines(
-            'git-rev-list --topo-order --reverse --parents --all'):
+            'git-rev-list --topo-order --reverse --parents --stdin',
+            ['%s\n' % p for p in patches]):
             commits = line.split()
             commit, parents = commits[0], Set(commits[1:])
 

diff --git a/stgit/stack.py b/stgit/stack.py
index dbb27eb..b00a024 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -449,15 +449,27 @@ class UninterestingCache:
         self.__compute_uninteresting()
         self.__write_file()
     def __compute_uninteresting(self):
-        """Compute a reasonable set of uninteresting commits from
-        scratch. This is expensive."""
-        out.start('Finding uninteresting commits')
+        """Compute the set of uninteresting commits from scratch. This
+        is expensive in the general case; therefore, we print a
+        message to the user."""
         ref2hash = read_refs(self.__series.get_name())
         patches = Set([sha1 for ref, sha1 in ref2hash.iteritems() if ref])
-        interesting, uninteresting = Set(), Set()
+
+        # Optimize some important special cases.
+        if len(patches) == 0:
+            self.__uninteresting = Set()
+            return
+        elif len(patches) == 1:
+            patch = iter(patches).next()
+            commit, parent = git._output_one_line(
+                'git-rev-list --parents %s' % patch).split()
+            self.__uninteresting = Set([parent])
+            return
 
         # Iterate over all commits. We are guaranteed to see each
         # commit before any of its children.
+        out.start('Finding uninteresting commits')
+        interesting, uninteresting = Set(), Set()
         for line in git._output_lines(
             'git-rev-list --topo-order --reverse --parents --stdin',
             ['%s\n' % p for p in patches]):
@@ -483,7 +495,6 @@ class UninterestingCache:
             # Commits with interesting parents are interesting.
             elif interesting.intersection(parents):
                 interesting.add(commit)
-
         self.__uninteresting = uninteresting
         out.done()
     def create_patch(self, name, top, bottom, new_commit):
@@ -496,6 +507,13 @@ class UninterestingCache:
         if not self.__cache_file():
             return # not cached
 
+        # If there are no existing uninteresting commits, this is the
+        # first patch, so its bottom has to be uninteresting.
+        if not self.__uninteresting:
+            self.__uninteresting.add(bottom)
+            self.__write_file()
+            return
+
         # New patch inserted just below an existing bottommost patch:
         # need to move the uninteresting commit down one step.
         if top in self.__uninteresting: