--- a/mercurial/context.py	Mon Aug 27 09:37:49 2012 -0700
+++ b/mercurial/context.py	Tue Aug 28 20:52:04 2012 +0200
@@ -11,6 +11,7 @@
 import copies
 import match as matchmod
 import os, errno, stat
+import obsolete as obsmod
 
 propertycache = util.propertycache
 
@@ -232,38 +233,15 @@
 
     def obsolete(self):
         """True if the changeset is obsolete"""
-        return (self.node() in self._repo.obsstore.precursors
-                and self.phase() > phases.public)
+        return self.rev() in obsmod.getobscache(self._repo, 'obsolete')
 
     def extinct(self):
         """True if the changeset is extinct"""
-        # We should just compute a cache and check against it.
-        # See revset implementation for details.
-        #
-        # But this naive implementation does not require cache
-        if self.phase() <= phases.public:
-            return False
-        if not self.obsolete():
-            return False
-        for desc in self.descendants():
-            if not desc.obsolete():
-                return False
-        return True
+        return self.rev() in obsmod.getobscache(self._repo, 'extinct')
 
     def unstable(self):
         """True if the changeset is not obsolete but it's ancestor are"""
-        # We should just compute /(obsolete()::) - obsolete()/
-        # and keep it in a cache.
-        #
-        # But this naive implementation does not require cache
-        if self.phase() <= phases.public:
-            return False
-        if self.obsolete():
-            return False
-        for anc in self.ancestors():
-            if anc.obsolete():
-                return True
-        return False
+        return self.rev() in obsmod.getobscache(self._repo, 'unstable')
 
     def _fileinfo(self, path):
         if '_manifest' in self.__dict__:

--- a/mercurial/localrepo.py	Mon Aug 27 09:37:49 2012 -0700
+++ b/mercurial/localrepo.py	Tue Aug 28 20:52:04 2012 +0200
@@ -1042,6 +1042,7 @@
 
         self._branchcache = None # in UTF-8
         self._branchcachetip = None
+        obsolete.clearobscaches(self)
 
     def invalidatedirstate(self):
         '''Invalidates the dirstate, causing the next call to dirstate
@@ -2404,6 +2405,7 @@
             self.ui.status(_("added %d changesets"
                              " with %d changes to %d files%s\n")
                              % (changesets, revisions, files, htext))
+            obsolete.clearobscaches(self)
 
             if changesets > 0:
                 p = lambda: cl.writepending() and self.root or ""

--- a/mercurial/obsolete.py	Mon Aug 27 09:37:49 2012 -0700
+++ b/mercurial/obsolete.py	Tue Aug 28 20:52:04 2012 +0200
@@ -161,6 +161,8 @@
     """
 
     def __init__(self, sopener):
+        # caches for various obsolescence related cache
+        self.caches = {}
         self._all = []
         # new markers to serialize
         self.precursors = {}
@@ -220,6 +222,8 @@
                 # call 'filecacheentry.refresh()'  here
                 f.close()
             self._load(new)
+            # new marker *may* have changed several set. invalidate the cache.
+            self.caches.clear()
         return len(new)
 
     def mergemarkers(self, transation, data):
@@ -327,3 +331,67 @@
                 if suc not in seen:
                     seen.add(suc)
                     remaining.add(suc)
+
+# mapping of 'set-name' -> <function to computer this set>
+cachefuncs = {}
+def cachefor(name):
+    """Decorator to register a function as computing the cache for a set"""
+    def decorator(func):
+        assert name not in cachefuncs
+        cachefuncs[name] = func
+        return func
+    return decorator
+
+def getobscache(repo, name):
+    """Return the set of revision that belong to the <name> set
+
+    Such access may compute the set and cache it for future use"""
+    if not repo.obsstore:
+        return ()
+    if name not in repo.obsstore.caches:
+        repo.obsstore.caches[name] = cachefuncs[name](repo)
+    return repo.obsstore.caches[name]
+
+# To be simple we need to invalidate obsolescence cache when:
+#
+# - new changeset is added:
+# - public phase is changed
+# - obsolescence marker are added
+# - strip is used a repo
+def clearobscaches(repo):
+    """Remove all obsolescence related cache from a repo
+
+    This remove all cache in obsstore is the obsstore already exist on the
+    repo.
+
+    (We could be smarter here given the exact event that trigger the cache
+    clearing)"""
+    # only clear cache is there is obsstore data in this repo
+    if 'obsstore' in repo._filecache:
+        repo.obsstore.caches.clear()
+
+@cachefor('obsolete')
+def _computeobsoleteset(repo):
+    """the set of obsolete revisions"""
+    obs = set()
+    nm = repo.changelog.nodemap
+    for prec in repo.obsstore.precursors:
+        rev = nm.get(prec)
+        if rev is not None:
+            obs.add(rev)
+    return set(repo.revs('%ld - public()', obs))
+
+@cachefor('unstable')
+def _computeunstableset(repo):
+    """the set of non obsolete revisions with obsolete parents"""
+    return set(repo.revs('(obsolete()::) - obsolete()'))
+
+@cachefor('suspended')
+def _computesuspendedset(repo):
+    """the set of obsolete parents with non obsolete descendants"""
+    return set(repo.revs('obsolete() and obsolete()::unstable()'))
+
+@cachefor('extinct')
+def _computeextinctset(repo):
+    """the set of obsolete parents without non obsolete descendants"""
+    return set(repo.revs('obsolete() - obsolete()::unstable()'))

--- a/mercurial/phases.py	Mon Aug 27 09:37:49 2012 -0700
+++ b/mercurial/phases.py	Tue Aug 28 20:52:04 2012 +0200
@@ -104,6 +104,7 @@
 from node import nullid, nullrev, bin, hex, short
 from i18n import _
 import util
+import obsolete
 
 allphases = public, draft, secret = range(3)
 trackedphases = allphases[1:]
@@ -244,6 +245,7 @@
             # declare deleted root in the target phase
             if targetphase != 0:
                 self.retractboundary(repo, targetphase, delroots)
+        obsolete.clearobscaches(repo)
 
     def retractboundary(self, repo, targetphase, nodes):
         # Be careful to preserve shallow-copied values: do not update
@@ -260,6 +262,7 @@
             ctxs = repo.set('roots(%ln::)', currentroots)
             currentroots.intersection_update(ctx.node() for ctx in ctxs)
             self._updateroots(targetphase, currentroots)
+        obsolete.clearobscaches(repo)
 
 def advanceboundary(repo, targetphase, nodes):
     """Add nodes to a phase changing other nodes phases if necessary.

--- a/mercurial/revset.py	Mon Aug 27 09:37:49 2012 -0700
+++ b/mercurial/revset.py	Tue Aug 28 20:52:04 2012 +0200
@@ -12,6 +12,7 @@
 import match as matchmod
 from i18n import _
 import encoding
+import obsolete as obsmod
 
 def _revancestors(repo, revs, followfirst):
     """Like revlog.ancestors(), but supports followfirst."""
@@ -621,8 +622,8 @@
     """
     # i18n: "extinct" is a keyword
     getargs(x, 0, 0, _("extinct takes no arguments"))
-    extinctset = set(repo.revs('(obsolete()::) - (::(not obsolete()))'))
-    return [r for r in subset if r in extinctset]
+    extincts = obsmod.getobscache(repo, 'extinct')
+    return [r for r in subset if r in extincts]
 
 def extra(repo, subset, x):
     """``extra(label, [value])``
@@ -959,7 +960,8 @@
     Mutable changeset with a newer version."""
     # i18n: "obsolete" is a keyword
     getargs(x, 0, 0, _("obsolete takes no arguments"))
-    return [r for r in subset if repo[r].obsolete()]
+    obsoletes = obsmod.getobscache(repo, 'obsolete')
+    return [r for r in subset if r in obsoletes]
 
 def origin(repo, subset, x):
     """``origin([set])``
@@ -1437,8 +1439,8 @@
     """
     # i18n: "unstable" is a keyword
     getargs(x, 0, 0, _("unstable takes no arguments"))
-    unstableset = set(repo.revs('(obsolete()::) - obsolete()'))
-    return [r for r in subset if r in unstableset]
+    unstables = obsmod.getobscache(repo, 'unstable')
+    return [r for r in subset if r in unstables]
 
 
 def user(repo, subset, x):