[StGIT PATCH 0/5] Compute patch appliedness using the commit DAG

@@ -466,7 +466,7 @@ class Series(PatchSet):
         crt = self.get_current()
         if not crt:
             return None
-        return Patch(crt, self.__patch_dir, self.__refs_dir)
+        return self.get_patch(crt)
 
     def get_current(self):
         """Return the name of the topmost patch, or None if there is

@@ -684,7 +684,7 @@ class Series(PatchSet):
                 raise StackException, \
                       'Cannot delete: the series still contains patches'
             for p in patches:
-                Patch(p, self.__patch_dir, self.__refs_dir).delete()
+                self.get_patch(p).delete()
 
             # remove the trash directory if any
             if os.path.exists(self.__trash_dir):

@@ -741,7 +741,7 @@ class Series(PatchSet):
         if not name:
             raise StackException, 'No patches applied'
 
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+        patch = self.get_patch(name)
 
         descr = patch.get_description()
         if not (message or descr):

@@ -807,7 +807,7 @@ class Series(PatchSet):
         name = self.get_current()
         assert(name)
 
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+        patch = self.get_patch(name)
         old_bottom = patch.get_old_bottom()
         old_top = patch.get_old_top()
 

@@ -848,7 +848,7 @@ class Series(PatchSet):
         if name == None:
             name = make_patch_name(descr, self.patch_exists)
 
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+        patch = self.get_patch(name)
         patch.create()
 
         if not bottom:

@@ -936,7 +936,7 @@ class Series(PatchSet):
         for name in names:
             assert(name in unapplied)
 
-            patch = Patch(name, self.__patch_dir, self.__refs_dir)
+            patch = self.get_patch(name)
 
             head = top
             bottom = patch.get_bottom()

@@ -1002,8 +1002,7 @@ class Series(PatchSet):
         patches detected to have been applied. The state of the tree
         is restored to the original one
         """
-        patches = [Patch(name, self.__patch_dir, self.__refs_dir)
-                   for name in names]
+        patches = [self.get_patch(name) for name in names]
         patches.reverse()
 
         merged = []

@@ -1022,7 +1021,7 @@ class Series(PatchSet):
         unapplied = self.get_unapplied()
         assert(name in unapplied)
 
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+        patch = self.get_patch(name)
 
         head = git.get_head()
         bottom = patch.get_bottom()

@@ -1096,7 +1095,7 @@ class Series(PatchSet):
         name = self.get_current()
         assert(name)
 
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+        patch = self.get_patch(name)
         old_bottom = patch.get_old_bottom()
         old_top = patch.get_old_top()
 

@@ -1122,7 +1121,7 @@ class Series(PatchSet):
         applied.reverse()
         assert(name in applied)
 
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+        patch = self.get_patch(name)
 
         if git.get_head_file() == self.get_name():
             if keep and not git.apply_diff(git.get_head(), patch.get_bottom()):

@@ -1148,7 +1147,7 @@ class Series(PatchSet):
         """Returns True if the patch is empty
         """
         self.__patch_name_valid(name)
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+        patch = self.get_patch(name)
         bottom = patch.get_bottom()
         top = patch.get_top()
 

@@ -1173,11 +1172,11 @@ class Series(PatchSet):
             raise StackException, 'Patch "%s" already exists' % newname
 
         if oldname in unapplied:
-            Patch(oldname, self.__patch_dir, self.__refs_dir).rename(newname)
+            self.get_patch(oldname).rename(newname)
             unapplied[unapplied.index(oldname)] = newname
             write_strings(self.__unapplied_file, unapplied)
         elif oldname in applied:
-            Patch(oldname, self.__patch_dir, self.__refs_dir).rename(newname)
+            self.get_patch(oldname).rename(newname)
 
             applied[applied.index(oldname)] = newname
             write_strings(self.__applied_file, applied)

@@ -52,14 +52,8 @@ def func(parser, options, args):
     if crt_series.get_protected():
         raise CmdException, 'This branch is protected.  Commit is not permitted'
 
-    crt_head = git.get_head()
-
     out.start('Committing %d patches' % len(applied))
-
-    crt_series.pop_patch(applied[0])
-    git.switch(crt_head)
-
     for patch in applied:
-        crt_series.delete_patch(patch)
+        crt_series.delete_patch_data(patch)
 
     out.done()

@@ -48,7 +48,7 @@ def func(parser, options, args):
     check_head_top_equal()
 
     unapplied = crt_series.get_unapplied()
-    applied = crt_series.get_applied()
+    applied = list(crt_series.get_applied()) # a copy, since we'll modify it
     all = unapplied + applied
 
     if options.series:

@@ -293,7 +293,7 @@ def __create_patch(filename, message, author_name, author_email,
         git.apply_patch(diff = diff, base = git_id(options.base))
     else:
         git.apply_patch(diff = diff)
-    crt_series.refresh_patch(edit = options.edit,
+    crt_series.refresh_patch(patch, edit = options.edit,
                              show_patch = options.showpatch)
     out.done()
 

@@ -147,7 +147,7 @@ def func(parser, options, args):
 
         if autoresolved == 'yes':
             resolved_all()
-        crt_series.refresh_patch(files = files,
+        crt_series.refresh_patch(patch, files = files,
                                  message = options.message,
                                  edit = options.edit,
                                  show_patch = options.showpatch,

@@ -156,7 +156,7 @@ def func(parser, options, args):
         if git.local_changes(verbose = False):
             # index (cache) already updated by the git merge. The
             # backup information was already reset above
-            crt_series.refresh_patch(cache_update = False, backup = False,
+            crt_series.refresh_patch(p, cache_update = False, backup = False,
                                      log = 'sync')
             out.done('updated')
         else:

@@ -189,8 +189,11 @@ def _output_one_line(cmd, file_desc = None):
                                                 p.childerr.read().strip())
     return output
 
-def _output_lines(cmd):
+def _output_lines(cmd, input = []):
     p=popen2.Popen3(cmd, True)
+    for line in input:
+        p.tochild.write(line)
+    p.tochild.close()
     lines = p.fromchild.readlines()
     if p.wait():
         raise GitException, '%s failed (%s)' % (' '.join(cmd),

@@ -18,13 +18,13 @@ along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 """
 
-import sys, os, re
+import sys, os, popen2, re
 
 from stgit.utils import *
 from stgit import git, basedir, templates
 from stgit.config import config
 from shutil import copyfile
-
+from sets import Set
 
 # stack exception class
 class StackException(Exception):

@@ -274,7 +274,7 @@ class Patch(StgitObject):
         self.__update_log_ref(value)
 
 # The current StGIT metadata format version.
-FORMAT_VERSION = 2
+FORMAT_VERSION = 3
 
 class PatchSet(StgitObject):
     def __init__(self, name = None):

@@ -346,6 +346,153 @@ class PatchSet(StgitObject):
         return bool(config.get(self.format_version_key()))
 
 
+class PatchorderCache:
+    """An object that keeps track of the patch order for a series, as
+    saved in its patchorder file."""
+    def __init__(self, series):
+        self.__series = series
+        self.__invalidate()
+    def __invalidate(self):
+        self.__patchnames = None
+        self.__position = None
+    def __cache(self):
+        if self.__patchnames != None:
+            return # already cached
+
+        self.__patchnames = []
+        self.__position = {}
+        pof = os.path.join(self.__series._dir(), 'patchorder')
+        if os.path.isfile(pof):
+            for line in file(pof):
+                name = line.strip()
+                assert not name in self.__position
+                self.__position[name] = len(self.__patchnames)
+                self.__patchnames.append(name)
+    def set_patchorder(self, new_order):
+        self.__invalidate()
+        f = file(os.path.join(self.__series._dir(), 'patchorder'), 'w')
+        for name in new_order:
+            f.write('%s\n' % name)
+        f.close()
+    def cmp(self, name1, name2):
+        """Compare two patch names to see which patch comes first. If
+        both patches are listed in the patchorder file, sort them by
+        the order they appear there; if one is listed and the other
+        not, the listed patch goes first; and if neither is listed,
+        sort them by their names."""
+        self.__cache()
+        largepos = len(self.__patchnames)
+        pos1 = self.__position.get(name1, largepos)
+        pos2 = self.__position.get(name2, largepos)
+        return cmp((pos1, name1), (pos2, name2))
+
+def read_refs(branch):
+    """Return a mapping from patches and branch head to hashes for a
+    given branch. The patches are listed by name; the branch head is
+    None."""
+    refs = {}
+    patchpat = re.compile(r'^refs/patches/%s/([^\.]+)$' % branch)
+    for line in git._output_lines('git-show-ref'):
+        sha1, ref = line.split()
+        m = re.match(patchpat, ref)
+        if m:
+            refs[m.group(1)] = sha1
+        elif ref == 'refs/heads/%s' % branch:
+            refs[None] = sha1
+    return refs
+
+def unapplied_patches(ref2hash):
+    """Given a map of patch names (and the branch head, keyed by None)
+    to hashes, return the set of unapplied patches."""
+    hash2refs = {}
+    for r, h in ref2hash.iteritems():
+        hash2refs.setdefault(h, Set()).add(r)
+
+    unapplied = Set()
+    for line in git._output_lines(
+        'git-rev-list --stdin',
+        ('%s%s\n' % (['', '^'][ref == None], sha1)
+         for ref, sha1 in ref2hash.iteritems())):
+        for ref in hash2refs.get(line.strip(), []):
+            unapplied.add(ref)
+    return unapplied
+
+def sort_applied_patches(ref2hash):
+    """Given a map of patch names (and the branch head, keyed by None)
+    to hashes, return a list with the applied patches in stack order.
+    All patches in the map must be applied."""
+    hash2refs = {}
+    for r, h in ref2hash.iteritems():
+        if r != None:
+            hash2refs.setdefault(h, Set()).add(r)
+
+    missing = Set(ref for ref in ref2hash.iterkeys() if ref != None)
+    if not missing:
+        return []
+    applied = []
+    grl = popen2.Popen3('git-rev-list %s' % ref2hash[None], True)
+    for line in grl.fromchild:
+        for ref in hash2refs.get(line.strip(), []):
+            applied.append(ref)
+            missing.remove(ref)
+        if not missing:
+            applied.reverse()
+            return applied
+
+    raise StackException, 'Could not find patches: %s' % ', '.join(missing)
+
+class AppliedCache:
+    """An object that keeps track of the appliedness and order of the
+    patches in a patch series."""
+    def __init__(self, series):
+        self.__series = series
+        self.__order = PatchorderCache(series)
+        self.__invalidate()
+    def get_applied(self):
+        self.__cache()
+        return self.__applied
+    def get_unapplied(self):
+        self.__cache()
+        return self.__unapplied
+    def rename(self, oldname, newname):
+        """Rename a patch."""
+        self.__cache()
+        for lst in (self.__applied, self.__unapplied):
+            try:
+                lst[lst.index(oldname)] = newname
+            except ValueError:
+                pass # lst.index() couldn't find the index
+            else:
+                self.__write_patchorder()
+                return
+        raise StackException, 'Unknown patch "%s"' % oldname
+    def __write_patchorder(self):
+        self.__order.set_patchorder(self.get_applied() + self.get_unapplied())
+    def set_patchorder(self, new_order):
+        self.__order.set_patchorder(new_order)
+        self.refresh()
+    def refresh(self):
+        """Re-read patch appliedness info, and write patch order to
+        disk."""
+        self.__invalidate()
+        self.__write_patchorder()
+    def __invalidate(self):
+        self.__applied = None
+        self.__unapplied = None
+    def __cached(self):
+        return (self.__applied != None)
+    def __cache(self):
+        if self.__cached():
+            return
+        patches = read_refs(self.__series.get_name())
+        unapplied = unapplied_patches(patches)
+        for patch in unapplied:
+            del patches[patch]
+        self.__applied = sort_applied_patches(patches)
+        self.__unapplied = list(unapplied)
+        self.__unapplied.sort(self.__order.cmp)
+
+
 class Series(PatchSet):
     """Class including the operations on series
     """

@@ -361,8 +508,6 @@ class Series(PatchSet):
         self.__refs_dir = os.path.join(self._basedir(), 'refs', 'patches',
                                        self.get_name())
 
-        self.__applied_file = os.path.join(self._dir(), 'applied')
-        self.__unapplied_file = os.path.join(self._dir(), 'unapplied')
         self.__hidden_file = os.path.join(self._dir(), 'hidden')
 
         # where this series keeps its patches

@@ -371,6 +516,8 @@ class Series(PatchSet):
         # trash directory
         self.__trash_dir = os.path.join(self._dir(), 'trash')
 
+        self.__applied_cache = AppliedCache(self)
+
     def format_version_key(self):
         return 'branch.%s.stgit.stackformatversion' % self.get_name()
 

@@ -444,6 +591,21 @@ class Series(PatchSet):
             rm(os.path.join(self._basedir(), 'refs', 'bases', self.get_name()))
             set_format_version(2)
 
+        # Update 2 -> 3.
+        if get_format_version() == 2:
+            patchorder = file(os.path.join(branch_dir, 'patchorder'), 'w')
+            for pf in ['applied', 'unapplied']:
+                pfn = os.path.join(branch_dir, pf)
+                if not os.path.isfile(pfn):
+                    continue
+                for line in file(pfn):
+                    line = line.strip()
+                    if line:
+                        patchorder.write(line + '\n')
+                rm(pfn)
+            patchorder.close()
+            set_format_version(3)
+
         # Make sure we're at the latest version.
         if not get_format_version() in [None, FORMAT_VERSION]:
             raise StackException('Branch %s is at format version %d, expected %d'

@@ -471,11 +633,7 @@ class Series(PatchSet):
     def get_current(self):
         """Return the name of the topmost patch, or None if there is
         no such patch."""
-        try:
-            applied = self.get_applied()
-        except StackException:
-            # No "applied" file: branch is not initialized.
-            return None
+        applied = self.get_applied()
         try:
             return applied[-1]
         except IndexError:

@@ -483,14 +641,10 @@ class Series(PatchSet):
             return None
 
     def get_applied(self):
-        if not os.path.isfile(self.__applied_file):
-            raise StackException, 'Branch "%s" not initialised' % self.get_name()
-        return read_strings(self.__applied_file)
+        return self.__applied_cache.get_applied()
 
     def get_unapplied(self):
-        if not os.path.isfile(self.__unapplied_file):
-            raise StackException, 'Branch "%s" not initialised' % self.get_name()
-        return read_strings(self.__unapplied_file)
+        return self.__applied_cache.get_unapplied()
 
     def get_hidden(self):
         if not os.path.isfile(self.__hidden_file):

@@ -498,13 +652,12 @@ class Series(PatchSet):
         return read_strings(self.__hidden_file)
 
     def get_base(self):
-        # Return the parent of the bottommost patch, if there is one.
-        if os.path.isfile(self.__applied_file):
-            bottommost = file(self.__applied_file).readline().strip()
-            if bottommost:
-                return self.get_patch(bottommost).get_bottom()
-        # No bottommost patch, so just return HEAD
-        return git.get_head()
+        applied = self.get_applied()
+        if applied:
+            return self.get_patch(applied[0]).get_bottom()
+        else:
+            # No bottommost patch, so just return HEAD
+            return git.get_head()
 
     def get_parent_remote(self):
         value = config.get('branch.%s.remote' % self.get_name())

@@ -591,8 +744,6 @@ class Series(PatchSet):
 
         self.set_parent(parent_remote, parent_branch)
 
-        self.create_empty_field('applied')
-        self.create_empty_field('unapplied')
         os.makedirs(self.__refs_dir)
         self._set_field('orig-base', git.get_head())
 

@@ -694,10 +845,6 @@ class Series(PatchSet):
 
             # FIXME: find a way to get rid of those manual removals
             # (move functionality to StgitObject ?)
-            if os.path.exists(self.__applied_file):
-                os.remove(self.__applied_file)
-            if os.path.exists(self.__unapplied_file):
-                os.remove(self.__unapplied_file)
             if os.path.exists(self.__hidden_file):
                 os.remove(self.__hidden_file)
             if os.path.exists(self._dir()+'/orig-base'):

@@ -727,7 +874,7 @@ class Series(PatchSet):
         config.unset('branch.%s.stgit.parentbranch' % self.get_name())
         config.unset(self.format_version_key())
 
-    def refresh_patch(self, files = None, message = None, edit = False,
+    def refresh_patch(self, name, files = None, message = None, edit = False,
                       show_patch = False,
                       cache_update = True,
                       author_name = None, author_email = None,

@@ -737,10 +884,6 @@ class Series(PatchSet):
                       notes = None):
         """Generates a new commit for the given patch
         """
-        name = self.get_current()
-        if not name:
-            raise StackException, 'No patches applied'
-
         patch = self.get_patch(name)
 
         descr = patch.get_description()

@@ -830,9 +973,10 @@ class Series(PatchSet):
         """Creates a new patch
         """
 
+        appl, unappl = self.get_applied(), self.get_unapplied()
         if name != None:
             self.__patch_name_valid(name)
-            if self.patch_exists(name):
+            if name in appl or name in unappl:
                 raise StackException, 'Patch "%s" already exists' % name
 
         if not message and can_edit:

@@ -866,17 +1010,12 @@ class Series(PatchSet):
         patch.set_commemail(committer_email)
 
         if before_existing:
-            insert_string(self.__applied_file, patch.get_name())
+            order = [patch.get_name()] + appl + unappl
             # no need to commit anything as the object is already
             # present (mainly used by 'uncommit')
             commit = False
-        elif unapplied:
-            patches = [patch.get_name()] + self.get_unapplied()
-            write_strings(self.__unapplied_file, patches)
-            set_head = False
         else:
-            append_string(self.__applied_file, patch.get_name())
-            set_head = True
+            order = appl + [patch.get_name()] + unappl
 
         if commit:
             # create a commit for the patch (may be empty if top == bottom);

@@ -886,7 +1025,7 @@ class Series(PatchSet):
             commit_id = git.commit(message = descr, parents = [bottom],
                                    cache_update = False,
                                    tree_id = top_commit.get_tree(),
-                                   allowempty = True, set_head = set_head,
+                                   allowempty = True, set_head = not unapplied,
                                    author_name = author_name,
                                    author_email = author_email,
                                    author_date = author_date,

@@ -897,15 +1036,27 @@ class Series(PatchSet):
 
         self.log_patch(patch, 'new')
 
+        self.__applied_cache.set_patchorder(order)
+        return patch
+
+    def delete_patch_data(self, name):
+        """Deletes the stgit data for a patch."""
+        patch = Patch(name, self.__patch_dir, self.__refs_dir)
+
+        # save the commit id to a trash file
+        write_string(os.path.join(self.__trash_dir, name), patch.get_top())
+
+        patch.delete()
+        if self.patch_hidden(name):
+            self.unhide_patch(name)
+
         return patch
 
     def delete_patch(self, name):
         """Deletes a patch
         """
         self.__patch_name_valid(name)
-        patch = Patch(name, self.__patch_dir, self.__refs_dir)
-
-        if self.__patch_is_current(patch):
+        if self.get_current() == name:
             self.pop_patch(name)
         elif self.patch_applied(name):
             raise StackException, 'Cannot remove an applied patch, "%s", ' \

@@ -913,14 +1064,8 @@ class Series(PatchSet):
         elif not name in self.get_unapplied():
             raise StackException, 'Unknown patch "%s"' % name
 
-        # save the commit id to a trash file
-        write_string(os.path.join(self.__trash_dir, name), patch.get_top())
-
-        patch.delete()
-
-        unapplied = self.get_unapplied()
-        unapplied.remove(name)
-        write_strings(self.__unapplied_file, unapplied)
+        self.delete_patch_data(name)
+        self.__applied_cache.refresh()
 
     def forward_patches(self, names):
         """Try to fast-forward an array of patches.

@@ -984,16 +1129,12 @@ class Series(PatchSet):
                     break
 
             forwarded+=1
-            unapplied.remove(name)
 
         if forwarded == 0:
             return 0
 
         git.switch(top)
-
-        append_strings(self.__applied_file, names[0:forwarded])
-        write_strings(self.__unapplied_file, unapplied)
-
+        self.__applied_cache.refresh()
         return forwarded
 
     def merged_patches(self, names):

@@ -1066,11 +1207,6 @@ class Series(PatchSet):
                               'Use "refresh" after fixing the conflicts or'
                               ' revert the operation with "push --undo".')
 
-        append_string(self.__applied_file, name)
-
-        unapplied.remove(name)
-        write_strings(self.__unapplied_file, unapplied)
-
         # head == bottom case doesn't need to refresh the patch
         if empty or head != bottom:
             if not ex:

@@ -1080,15 +1216,17 @@ class Series(PatchSet):
                     log = 'push(m)'
                 else:
                     log = 'push'
-                self.refresh_patch(cache_update = False, log = log)
+                self.refresh_patch(name, cache_update = False, log = log)
             else:
                 # we store the correctly merged files only for
                 # tracking the conflict history. Note that the
                 # git.merge() operations should always leave the index
                 # in a valid state (i.e. only stage 0 files)
-                self.refresh_patch(cache_update = False, log = 'push(c)')
+                self.refresh_patch(name, cache_update = False, log = 'push(c)')
                 raise StackException, str(ex)
 
+        self.__applied_cache.refresh()
+
         return modified
 
     def undo_push(self):

@@ -1117,10 +1255,7 @@ class Series(PatchSet):
     def pop_patch(self, name, keep = False):
         """Pops the top patch from the stack
         """
-        applied = self.get_applied()
-        applied.reverse()
-        assert(name in applied)
-
+        assert(name in self.get_applied())
         patch = self.get_patch(name)
 
         if git.get_head_file() == self.get_name():

@@ -1131,17 +1266,7 @@ class Series(PatchSet):
         else:
             git.set_branch(self.get_name(), patch.get_bottom())
 
-        # save the new applied list
-        idx = applied.index(name) + 1
-
-        popped = applied[:idx]
-        popped.reverse()
-        unapplied = popped + self.get_unapplied()
-        write_strings(self.__unapplied_file, unapplied)
-
-        del applied[:idx]
-        applied.reverse()
-        write_strings(self.__applied_file, applied)
+        self.__applied_cache.refresh()
 
     def empty_patch(self, name):
         """Returns True if the patch is empty

@@ -1171,17 +1296,8 @@ class Series(PatchSet):
         if newname in applied or newname in unapplied:
             raise StackException, 'Patch "%s" already exists' % newname
 
-        if oldname in unapplied:
-            self.get_patch(oldname).rename(newname)
-            unapplied[unapplied.index(oldname)] = newname
-            write_strings(self.__unapplied_file, unapplied)
-        elif oldname in applied:
-            self.get_patch(oldname).rename(newname)
-
-            applied[applied.index(oldname)] = newname
-            write_strings(self.__applied_file, applied)
-        else:
-            raise StackException, 'Unknown patch "%s"' % oldname
+        self.get_patch(oldname).rename(newname)
+        self.__applied_cache.rename(oldname, newname)
 
     def log_patch(self, patch, message, notes = None):
         """Generate a log commit for a patch

@@ -34,6 +34,12 @@ for ver in 0.12 0.8; do
         ! git show-ref --verify --quiet refs/bases/master
     '
 
+    test_expect_success \
+        "v$ver: Make sure the applied and unapplied files are gone" '
+        [ ! -e .git/patches/master/applied ] &&
+        [ ! -e .git/patches/master/unapplied ]
+'
+
     cd ..
 done
 

@@ -0,0 +1,60 @@
+#!/bin/sh
+# Copyright (c) 2007 Karl Hasselström
+test_description='Test git/StGIT interoperability'
+. ./test-lib.sh
+
+test_expect_success \
+    'Create some git-only history' '
+    echo foo > foo.txt &&
+    git add foo.txt &&
+    git commit -a -m foo &&
+    git tag foo-tag &&
+    for i in 0 1 2 3 4; do
+        echo foo$i >> foo.txt &&
+        git commit -a -m foo$i;
+    done
+'
+
+test_expect_success \
+    'Initialize the StGIT repository' '
+    stg init
+'
+
+test_expect_success \
+    'Create five patches' '
+    for i in 0 1 2 3 4; do
+        stg new p$i -m p$i;
+    done &&
+    [ "$(echo $(stg applied))" = "p0 p1 p2 p3 p4" ] &&
+    [ "$(echo $(stg unapplied))" = "" ]
+'
+
+test_expect_success \
+    'Pop two patches with git-reset' '
+    git reset --hard HEAD~2 &&
+    [ "$(echo $(stg applied))" = "p0 p1 p2" ] &&
+    [ "$(echo $(stg unapplied))" = "p3 p4" ]
+'
+
+test_expect_success \
+    'Create a new patch' '
+    stg new q0 -m q0 &&
+    [ "$(echo $(stg applied))" = "p0 p1 p2 q0" ] &&
+    [ "$(echo $(stg unapplied))" = "p3 p4" ]
+'
+
+test_expect_success \
+    'Go to an unapplied patch with with git-reset' '
+    git reset --hard $(stg id p3) &&
+    [ "$(echo $(stg applied))" = "p0 p1 p2 p3" ] &&
+    [ "$(echo $(stg unapplied))" = "q0 p4" ]
+'
+
+test_expect_success \
+    'Go back to below the stack base with git-reset' '
+    git reset --hard foo-tag &&
+    [ "$(echo $(stg applied))" = "" ] &&
+    [ "$(echo $(stg unapplied))" = "p0 p1 p2 q0 p3 p4" ]
+'
+
+test_done

@@ -70,15 +70,13 @@ _current_branch ()
 # List of all applied patches.
 _applied_patches ()
 {
-    local g=$(_gitdir)
-    [ "$g" ] && cat "$g/patches/$(_current_branch)/applied"
+    stg applied 2> /dev/null
 }
 
 # List of all unapplied patches.
 _unapplied_patches ()
 {
-    local g=$(_gitdir)
-    [ "$g" ] && cat "$g/patches/$(_current_branch)/unapplied"
+    stg unapplied 2> /dev/null
 }
 
 # List of all applied patches.

@@ -91,18 +89,13 @@ _hidden_patches ()
 # List of all patches.
 _all_patches ()
 {
-    local b=$(_current_branch)
-    local g=$(_gitdir)
-    [ "$g" ] && cat "$g/patches/$b/applied" "$g/patches/$b/unapplied"
+    stg series --noprefix 2> /dev/null
 }
 
 # List of all patches except the current patch.
 _all_other_patches ()
 {
-    local b=$(_current_branch)
-    local g=$(_gitdir)
-    [ "$g" ] && cat "$g/patches/$b/applied" "$g/patches/$b/unapplied" \
-        | grep -v "^$(cat $g/patches/$b/current 2> /dev/null)$"
+    stg series 2> /dev/null | grep -v '^>' | cut -f 2 -d ' '
 }
 
 _all_branches ()

@@ -155,7 +155,7 @@ class Patch(StgitObject):
         os.mkdir(self._dir())
         self.create_empty_field('bottom')
         self.create_empty_field('top')
-
+ 
     def delete(self):
         for f in os.listdir(self._dir()):
             os.remove(os.path.join(self._dir(), f))

@@ -351,7 +351,11 @@ class PatchorderCache:
     saved in its patchorder file."""
     def __init__(self, series):
         self.__series = series
+        self.__file = os.path.join(self.__series._dir(), 'patchorder')
         self.__invalidate()
+    def delete_file(self):
+        if os.path.isfile(self.__file):
+            os.remove(self.__file)
     def __invalidate(self):
         self.__patchnames = None
         self.__position = None

@@ -361,9 +365,8 @@ class PatchorderCache:
 
         self.__patchnames = []
         self.__position = {}
-        pof = os.path.join(self.__series._dir(), 'patchorder')
-        if os.path.isfile(pof):
-            for line in file(pof):
+        if os.path.isfile(self.__file):
+            for line in file(self.__file):
                 name = line.strip()
                 assert not name in self.__position
                 self.__position[name] = len(self.__patchnames)

@@ -386,60 +389,200 @@ class PatchorderCache:
         pos2 = self.__position.get(name2, largepos)
         return cmp((pos1, name1), (pos2, name2))
 
+class UninterestingCache:
+    """Keeps track of a set of commits that do not reach any patches.
+    These are used to speed up the detection of unapplied patches.
+
+    Specifically, this is at all times the set of commits c that
+    fulfill the following two criteria:
+
+      * c does not reach any patch
+
+      * c is the parent of a patch
+
+    """
+    def __init__(self, series):
+        self.__series = series
+        self.__uninteresting = None
+        self.__filename = os.path.join(self.__series._dir(), 'uninteresting')
+    def __invalidate(self):
+        self.__uninteresting = None
+        self.delete_file()
+    def delete_file(self):
+        if os.path.isfile(self.__filename):
+            os.remove(self.__filename)
+    def __other_patches(self, patchname):
+        """All patches except the named one."""
+        ref2hash = read_refs(self.__series.get_name())
+        return [self.__series.get_patch(ref)
+                for ref in ref2hash.iterkeys()
+                if ref and ref != patchname]
+    def __write_file(self):
+        """Write the uninteresting commits to file."""
+        try:
+            f = file(self.__filename, 'w')
+            for u in self.__uninteresting:
+                f.write('%s\n' % u)
+            f.close()
+        except IOError:
+            pass # this isn't fatal -- the directory is probably missing
+    def __read_file(self):
+        """Read the uninteresting commits from file. Return true on
+        success, false on failure."""
+        if not os.path.isfile(self.__filename):
+            return False
+        self.__uninteresting = Set()
+        for line in file(self.__filename):
+            self.__uninteresting.add(line.strip())
+        return True
+    def __cache_file(self):
+        """Try to cache the uninteresting commits using only the cache
+        file. Return true on success, false on failure."""
+        if self.__uninteresting != None:
+            return True # already cached
+        return self.__read_file()
+    def __cache(self):
+        """Cache the uninteresting commits, recomputing them if
+        necessary."""
+        if self.__cache_file():
+            return
+        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')
+        ref2hash = read_refs(self.__series.get_name())
+        patches = Set([sha1 for ref, sha1 in ref2hash.iteritems() if ref])
+        interesting, uninteresting = Set(), Set()
+
+        # 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'):
+            commits = line.split()
+            commit, parents = commits[0], Set(commits[1:])
+
+            # Patches are interesting.
+            if commit in patches:
+                interesting.add(commit)
+
+                # The parents of a patch are uninteresting unless they
+                # are interesting.
+                for p in parents:
+                    if not p in interesting:
+                        uninteresting.add(p)
+                continue
+
+            # Commits with interesting parents are interesting.
+            if interesting.intersection(parents):
+                interesting.add(commit)
+        self.__uninteresting = uninteresting
+        out.done()
+    def create_patch(self, name, top, bottom):
+        """The given patch has been created. Update the uninterested
+        state to maintain the invariant."""
+        if not self.__cache_file():
+            return # not cached
+
+        # New patch inserted just below an existing bottommost patch:
+        # need to move the uninteresting commit down one step.
+        if top in self.__uninteresting:
+            self.__uninteresting.remove(top)
+            self.__uninteresting.add(bottom)
+            self.__write_file()
+            return
+
+        # New patch inserted next to an existing non-bottommost patch:
+        # don't need to do anything.
+        existing_patches = self.__other_patches(name)
+        tops = Set([p.get_top() for p in existing_patches])
+        bottoms = Set([p.get_bottom() for p in existing_patches])
+        if bottom in bottoms or bottom in tops or top in bottoms:
+            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
+        # uninteresting if it doesn't reach any other patch. This is a
+        # lot of work, so we chicken out and blow the whole cache
+        # instead.
+        self.__invalidate()
+    def delete_patch(self, name, top, bottom):
+        """The given patch has been deleted. Update the uninterested
+        state to maintain the invariant."""
+        if not self.__cache_file():
+            return # not cached
+
+        # If this patch reaches another patch, there's nothing to do.
+        if not bottom in self.__uninteresting:
+            return
+
+        # If another patch has the same bottom, it's still
+        # uninteresting and there's nothing more to do.
+        other_patches = self.__other_patches(name)
+        for p in other_patches:
+            if p.get_bottom() == bottom:
+                return
+
+        # If there are other patches on top of this one, their bottoms
+        # (this patch's top) become uninteresting in place of this
+        # patch's bottom.
+        for p in other_patches:
+            if p.get_bottom() == top:
+                self.__uninteresting.remove(bottom)
+                self.__uninteresting.add(top)
+                self.__write_file()
+                return
+
+        # The bottom of this patch is no longer uninteresting. But
+        # there might be other patches that reach it, whose bottoms
+        # would need to be marked uninteresting. That would require an
+        # expensive reachability analysis.
+        self.__invalidate()
+    def get(self):
+        self.__cache()
+        return self.__uninteresting
+
 def read_refs(branch):
     """Return a mapping from patches and branch head to hashes for a
     given branch. The patches are listed by name; the branch head is
     None."""
     refs = {}
     patchpat = re.compile(r'^refs/patches/%s/([^\.]+)$' % branch)
+    head = 'refs/heads/%s' % branch
     for line in git._output_lines('git-show-ref'):
         sha1, ref = line.split()
         m = re.match(patchpat, ref)
         if m:
             refs[m.group(1)] = sha1
-        elif ref == 'refs/heads/%s' % branch:
+        elif ref == head:
             refs[None] = sha1
+    if not None in refs:
+        raise StackException, 'Could not find %s' % head
     return refs
 
-def unapplied_patches(ref2hash):
+def get_patches(ref2hash, uninteresting):
     """Given a map of patch names (and the branch head, keyed by None)
-    to hashes, return the set of unapplied patches."""
-    hash2refs = {}
-    for r, h in ref2hash.iteritems():
-        hash2refs.setdefault(h, Set()).add(r)
-
+    to hashes, return the list of applied patches and the set of
+    unapplied patches. The second parameter is a set of commit objects
+    that do not reach any patch."""
+    applied = []
     unapplied = Set()
-    for line in git._output_lines(
-        'git-rev-list --stdin',
-        ('%s%s\n' % (['', '^'][ref == None], sha1)
-         for ref, sha1 in ref2hash.iteritems())):
-        for ref in hash2refs.get(line.strip(), []):
-            unapplied.add(ref)
-    return unapplied
-
-def sort_applied_patches(ref2hash):
-    """Given a map of patch names (and the branch head, keyed by None)
-    to hashes, return a list with the applied patches in stack order.
-    All patches in the map must be applied."""
-    hash2refs = {}
+    hash2patches = {}
     for r, h in ref2hash.iteritems():
-        if r != None:
-            hash2refs.setdefault(h, Set()).add(r)
+        if r:
+            hash2patches.setdefault(h, Set()).add(r)
+            unapplied.add(r)
 
-    missing = Set(ref for ref in ref2hash.iterkeys() if ref != None)
-    if not missing:
-        return []
-    applied = []
-    grl = popen2.Popen3('git-rev-list %s' % ref2hash[None], True)
-    for line in grl.fromchild:
-        for ref in hash2refs.get(line.strip(), []):
+    for line in git._output_lines(
+        'git-rev-list --topo-order --stdin', ['%s\n' % ref2hash[None]]
+        + ['^%s\n' % u for u in uninteresting]):
+        for ref in hash2patches.get(line.strip(), []):
             applied.append(ref)
-            missing.remove(ref)
-        if not missing:
-            applied.reverse()
-            return applied
-
-    raise StackException, 'Could not find patches: %s' % ', '.join(missing)
+            unapplied.remove(ref)
+    applied.reverse()
+    return applied, unapplied
 
 class AppliedCache:
     """An object that keeps track of the appliedness and order of the

@@ -447,7 +590,11 @@ class AppliedCache:
     def __init__(self, series):
         self.__series = series
         self.__order = PatchorderCache(series)
+        self.__uninteresting = UninterestingCache(series)
         self.__invalidate()
+    def delete_files(self):
+        for sub in [self.__uninteresting, self.__order]:
+            sub.delete_file()
     def get_applied(self):
         self.__cache()
         return self.__applied

@@ -466,6 +613,17 @@ class AppliedCache:
                 self.__write_patchorder()
                 return
         raise StackException, 'Unknown patch "%s"' % oldname
+    def new(self, name, top, bottom):
+        """Create new patch."""
+        self.__uninteresting.create_patch(name, top, bottom)
+    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):
+        """Change a patch."""
+        if (new_top, new_bottom) != (old_top, old_bottom):
+            self.new(name, new_top, new_bottom)
+            self.delete(name, old_top, old_bottom)
     def __write_patchorder(self):
         self.__order.set_patchorder(self.get_applied() + self.get_unapplied())
     def set_patchorder(self, new_order):

@@ -484,11 +642,8 @@ class AppliedCache:
     def __cache(self):
         if self.__cached():
             return
-        patches = read_refs(self.__series.get_name())
-        unapplied = unapplied_patches(patches)
-        for patch in unapplied:
-            del patches[patch]
-        self.__applied = sort_applied_patches(patches)
+        self.__applied, unapplied = get_patches(
+            read_refs(self.__series.get_name()), self.__uninteresting.get())
         self.__unapplied = list(unapplied)
         self.__unapplied.sort(self.__order.cmp)
 

@@ -849,6 +1004,7 @@ class Series(PatchSet):
                 os.remove(self.__hidden_file)
             if os.path.exists(self._dir()+'/orig-base'):
                 os.remove(self._dir()+'/orig-base')
+            self.__applied_cache.delete_files()
 
             if not os.listdir(self.__patch_dir):
                 os.rmdir(self.__patch_dir)