Design of persistent tag cache

[Greg Ward]

Having implemented persistent tag caching according to the design that
Matt suggested back in May, I think I've hit a problem: stripping.
Here's Matt's original idea for the tag cache: a text file like

  <headnode> <headrev> <tagnode>
  [...repeat: 1 line per head...]

  <node> <tag>
  [...repeat: 1 line per tag...]

Good things about this design:
  * it's easy to detect if the entire cache is still valid: if the set
of heads in the cache == the current repo heads, the cache is all good
and we don't have to read any .hgtags files
  * when heads have been added, it minimizes the amount of work to
refresh the cache: IOW, you only need to visit the heads with a new
version of .hgtags

This design seems to work well when heads are replaced (ordinary
linear commit), added, or merged (2 heads replaced by 1 new one, but
the new one contains all the tag info of its parents).  But I cannot
see how to make it work when heads are stripped, which can destroy tag
info.  The problem is that the cached tag info is the merge of .hgtags
across all heads, so there's no way to know which tags no longer
exist.

AFAICT, the only fix is to cache more information: specifically, I
need to cache the info harvested from .hgtags in each head separately.
 E.g.:

  <headhash> <headrev> <tagnode> <ntags>
  <node> <tag>
  [...repeat <ntags> times...]
  <headhash> <headrev> <tagnode> <ntags>
  [...and so on...]

Alternately, I could keep the "big list of heads up front", followed
by a list of tags from each head.  It really depends on which is
easier to code.

Before I dive into implementing this, am I missing something?  Is
there a less space-intensive way to cache tags?

Also, what's the general feeling on a binary format?  I'm trying to
favour text for all the obvious reasons, but I have an immediate need
for caching ~5000 tags from 100+ heads.  So I want to ensure that the
design will scale well beyond that.  That might call for a dedicated
binary format.

 Thanks!

Greg