1 # revlog.py - storage back-end for mercurial

     2 #

     3 # Copyright 2005-2007 Matt Mackall <mpm@selenic.com>

     4 #

     5 # This software may be used and distributed according to the terms of the

     6 # GNU General Public License version 2 or any later version.

     7 

     8 """Storage back-end for Mercurial.

     9 

    10 This provides efficient delta storage with O(1) retrieve and append

    11 and O(changes) merge between branches.

    12 """

    13 

    14 # import stuff from node for others to import from revlog

    15 from node import bin, hex, nullid, nullrev, short #@UnusedImport

    16 from i18n import _

    17 import changegroup, ancestor, mdiff, parsers, error, util

    18 import struct, zlib, errno

    19 

    20 _pack = struct.pack

    21 _unpack = struct.unpack

    22 _compress = zlib.compress

    23 _decompress = zlib.decompress

    24 _sha = util.sha1

    25 

    26 # revlog header flags

    27 REVLOGV0 = 0

    28 REVLOGNG = 1

    29 REVLOGNGINLINEDATA = (1 << 16)

    30 REVLOGSHALLOW = (1 << 17)

    31 REVLOG_DEFAULT_FLAGS = REVLOGNGINLINEDATA

    32 REVLOG_DEFAULT_FORMAT = REVLOGNG

    33 REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS

    34 REVLOGNG_FLAGS = REVLOGNGINLINEDATA | REVLOGSHALLOW

    35 

    36 # revlog index flags

    37 REVIDX_PARENTDELTA  = 1

    38 REVIDX_PUNCHED_FLAG = 2

    39 REVIDX_KNOWN_FLAGS = REVIDX_PUNCHED_FLAG | REVIDX_PARENTDELTA

    40 

    41 # amount of data read unconditionally, should be >= 4

    42 # when not inline: threshold for using lazy index

    43 _prereadsize = 1048576

    44 # max size of revlog with inline data

    45 _maxinline = 131072

    46 

    47 RevlogError = error.RevlogError

    48 LookupError = error.LookupError

    49 

    50 def getoffset(q):

    51     return int(q >> 16)

    52 

    53 def gettype(q):

    54     return int(q & 0xFFFF)

    55 

    56 def offset_type(offset, type):

    57     return long(long(offset) << 16 | type)

    58 

    59 nullhash = _sha(nullid)

    60 

    61 def hash(text, p1, p2):

    62     """generate a hash from the given text and its parent hashes

    63 

    64     This hash combines both the current file contents and its history

    65     in a manner that makes it easy to distinguish nodes with the same

    66     content in the revision graph.

    67     """

    68     # As of now, if one of the parent node is null, p2 is null

    69     if p2 == nullid:

    70         # deep copy of a hash is faster than creating one

    71         s = nullhash.copy()

    72         s.update(p1)

    73     else:

    74         # none of the parent nodes are nullid

    75         l = [p1, p2]

    76         l.sort()

    77         s = _sha(l[0])

    78         s.update(l[1])

    79     s.update(text)

    80     return s.digest()

    81 

    82 def compress(text):

    83     """ generate a possibly-compressed representation of text """

    84     if not text:

    85         return ("", text)

    86     l = len(text)

    87     bin = None

    88     if l < 44:

    89         pass

    90     elif l > 1000000:

    91         # zlib makes an internal copy, thus doubling memory usage for

    92         # large files, so lets do this in pieces

    93         z = zlib.compressobj()

    94         p = []

    95         pos = 0

    96         while pos < l:

    97             pos2 = pos + 2**20

    98             p.append(z.compress(text[pos:pos2]))

    99             pos = pos2

   100         p.append(z.flush())

   101         if sum(map(len, p)) < l:

   102             bin = "".join(p)

   103     else:

   104         bin = _compress(text)

   105     if bin is None or len(bin) > l:

   106         if text[0] == '\0':

   107             return ("", text)

   108         return ('u', text)

   109     return ("", bin)

   110 

   111 def decompress(bin):

   112     """ decompress the given input """

   113     if not bin:

   114         return bin

   115     t = bin[0]

   116     if t == '\0':

   117         return bin

   118     if t == 'x':

   119         return _decompress(bin)

   120     if t == 'u':

   121         return bin[1:]

   122     raise RevlogError(_("unknown compression type %r") % t)

   123 

   124 class lazyparser(object):

   125     """

   126     this class avoids the need to parse the entirety of large indices

   127     """

   128 

   129     # lazyparser is not safe to use on windows if win32 extensions not

   130     # available. it keeps file handle open, which make it not possible

   131     # to break hardlinks on local cloned repos.

   132 

   133     def __init__(self, dataf):

   134         try:

   135             size = util.fstat(dataf).st_size

   136         except AttributeError:

   137             size = 0

   138         self.dataf = dataf

   139         self.s = struct.calcsize(indexformatng)

   140         self.datasize = size

   141         self.l = size // self.s

   142         self.index = [None] * self.l

   143         self.map = {nullid: nullrev}

   144         self.allmap = 0

   145         self.all = 0

   146         self.mapfind_count = 0

   147 

   148     def loadmap(self):

   149         """

   150         during a commit, we need to make sure the rev being added is

   151         not a duplicate.  This requires loading the entire index,

   152         which is fairly slow.  loadmap can load up just the node map,

   153         which takes much less time.

   154         """

   155         if self.allmap:

   156             return

   157         end = self.datasize

   158         self.allmap = 1

   159         cur = 0

   160         count = 0

   161         blocksize = self.s * 256

   162         self.dataf.seek(0)

   163         while cur < end:

   164             data = self.dataf.read(blocksize)

   165             off = 0

   166             for x in xrange(256):

   167                 n = data[off + ngshaoffset:off + ngshaoffset + 20]

   168                 self.map[n] = count

   169                 count += 1

   170                 if count >= self.l:

   171                     break

   172                 off += self.s

   173             cur += blocksize

   174 

   175     def loadblock(self, blockstart, blocksize, data=None):

   176         if self.all:

   177             return

   178         if data is None:

   179             self.dataf.seek(blockstart)

   180             if blockstart + blocksize > self.datasize:

   181                 # the revlog may have grown since we've started running,

   182                 # but we don't have space in self.index for more entries.

   183                 # limit blocksize so that we don't get too much data.

   184                 blocksize = max(self.datasize - blockstart, 0)

   185             data = self.dataf.read(blocksize)

   186         lend = len(data) // self.s

   187         i = blockstart // self.s

   188         off = 0

   189         # lazyindex supports __delitem__

   190         if lend > len(self.index) - i:

   191             lend = len(self.index) - i

   192         for x in xrange(lend):

   193             if self.index[i + x] is None:

   194                 b = data[off : off + self.s]

   195                 self.index[i + x] = b

   196                 n = b[ngshaoffset:ngshaoffset + 20]

   197                 self.map[n] = i + x

   198             off += self.s

   199 

   200     def findnode(self, node):

   201         """search backwards through the index file for a specific node"""

   202         if self.allmap:

   203             return None

   204 

   205         # hg log will cause many many searches for the manifest

   206         # nodes.  After we get called a few times, just load the whole

   207         # thing.

   208         if self.mapfind_count > 8:

   209             self.loadmap()

   210             if node in self.map:

   211                 return node

   212             return None

   213         self.mapfind_count += 1

   214         last = self.l - 1

   215         while self.index[last] != None:

   216             if last == 0:

   217                 self.all = 1

   218                 self.allmap = 1

   219                 return None

   220             last -= 1

   221         end = (last + 1) * self.s

   222         blocksize = self.s * 256

   223         while end >= 0:

   224             start = max(end - blocksize, 0)

   225             self.dataf.seek(start)

   226             data = self.dataf.read(end - start)

   227             findend = end - start

   228             while True:

   229                 # we're searching backwards, so we have to make sure

   230                 # we don't find a changeset where this node is a parent

   231                 off = data.find(node, 0, findend)

   232                 findend = off

   233                 if off >= 0:

   234                     i = off / self.s

   235                     off = i * self.s

   236                     n = data[off + ngshaoffset:off + ngshaoffset + 20]

   237                     if n == node:

   238                         self.map[n] = i + start / self.s

   239                         return node

   240                 else:

   241                     break

   242             end -= blocksize

   243         return None

   244 

   245     def loadindex(self, i=None, end=None):

   246         if self.all:

   247             return

   248         all = False

   249         if i is None:

   250             blockstart = 0

   251             blocksize = (65536 / self.s) * self.s

   252             end = self.datasize

   253             all = True

   254         else:

   255             if end:

   256                 blockstart = i * self.s

   257                 end = end * self.s

   258                 blocksize = end - blockstart

   259             else:

   260                 blockstart = (i & ~1023) * self.s

   261                 blocksize = self.s * 1024

   262                 end = blockstart + blocksize

   263         while blockstart < end:

   264             self.loadblock(blockstart, blocksize)

   265             blockstart += blocksize

   266         if all:

   267             self.all = True

   268 

   269 class lazyindex(object):

   270     """a lazy version of the index array"""

   271     def __init__(self, parser):

   272         self.p = parser

   273     def __len__(self):

   274         return len(self.p.index)

   275     def load(self, pos):

   276         if pos < 0:

   277             pos += len(self.p.index)

   278         self.p.loadindex(pos)

   279         return self.p.index[pos]

   280     def __getitem__(self, pos):

   281         return _unpack(indexformatng, self.p.index[pos] or self.load(pos))

   282     def __setitem__(self, pos, item):

   283         self.p.index[pos] = _pack(indexformatng, *item)

   284     def __delitem__(self, pos):

   285         del self.p.index[pos]

   286     def insert(self, pos, e):

   287         self.p.index.insert(pos, _pack(indexformatng, *e))

   288     def append(self, e):

   289         self.p.index.append(_pack(indexformatng, *e))

   290 

   291 class lazymap(object):

   292     """a lazy version of the node map"""

   293     def __init__(self, parser):

   294         self.p = parser

   295     def load(self, key):

   296         n = self.p.findnode(key)

   297         if n is None:

   298             raise KeyError(key)

   299     def __contains__(self, key):

   300         if key in self.p.map:

   301             return True

   302         self.p.loadmap()

   303         return key in self.p.map

   304     def __iter__(self):

   305         yield nullid

   306         for i, ret in enumerate(self.p.index):

   307             if not ret:

   308                 self.p.loadindex(i)

   309                 ret = self.p.index[i]

   310             if isinstance(ret, str):

   311                 ret = _unpack(indexformatng, ret)

   312             yield ret[7]

   313     def __getitem__(self, key):

   314         try:

   315             return self.p.map[key]

   316         except KeyError:

   317             try:

   318                 self.load(key)

   319                 return self.p.map[key]

   320             except KeyError:

   321                 raise KeyError("node " + hex(key))

   322     def __setitem__(self, key, val):

   323         self.p.map[key] = val

   324     def __delitem__(self, key):

   325         del self.p.map[key]

   326 

   327 indexformatv0 = ">4l20s20s20s"

   328 v0shaoffset = 56

   329 

   330 class revlogoldio(object):

   331     def __init__(self):

   332         self.size = struct.calcsize(indexformatv0)

   333 

   334     def parseindex(self, fp, data, inline):

   335         s = self.size

   336         index = []

   337         nodemap =  {nullid: nullrev}

   338         n = off = 0

   339         if len(data) == _prereadsize:

   340             data += fp.read() # read the rest

   341         l = len(data)

   342         while off + s <= l:

   343             cur = data[off:off + s]

   344             off += s

   345             e = _unpack(indexformatv0, cur)

   346             # transform to revlogv1 format

   347             e2 = (offset_type(e[0], 0), e[1], -1, e[2], e[3],

   348                   nodemap.get(e[4], nullrev), nodemap.get(e[5], nullrev), e[6])

   349             index.append(e2)

   350             nodemap[e[6]] = n

   351             n += 1

   352 

   353         return index, nodemap, None

   354 

   355     def packentry(self, entry, node, version, rev):

   356         if gettype(entry[0]):

   357             raise RevlogError(_("index entry flags need RevlogNG"))

   358         e2 = (getoffset(entry[0]), entry[1], entry[3], entry[4],

   359               node(entry[5]), node(entry[6]), entry[7])

   360         return _pack(indexformatv0, *e2)

   361 

   362 # index ng:

   363 #  6 bytes: offset

   364 #  2 bytes: flags

   365 #  4 bytes: compressed length

   366 #  4 bytes: uncompressed length

   367 #  4 bytes: base rev

   368 #  4 bytes: link rev

   369 #  4 bytes: parent 1 rev

   370 #  4 bytes: parent 2 rev

   371 # 32 bytes: nodeid

   372 indexformatng = ">Qiiiiii20s12x"

   373 ngshaoffset = 32

   374 versionformat = ">I"

   375 

   376 class revlogio(object):

   377     def __init__(self):

   378         self.size = struct.calcsize(indexformatng)

   379 

   380     def parseindex(self, fp, data, inline):

   381         if len(data) == _prereadsize:

   382             if util.openhardlinks() and not inline:

   383                 # big index, let's parse it on demand

   384                 parser = lazyparser(fp)

   385                 index = lazyindex(parser)

   386                 nodemap = lazymap(parser)

   387                 e = list(index[0])

   388                 type = gettype(e[0])

   389                 e[0] = offset_type(0, type)

   390                 index[0] = e

   391                 return index, nodemap, None

   392             else:

   393                 data += fp.read()

   394 

   395         # call the C implementation to parse the index data

   396         index, nodemap, cache = parsers.parse_index(data, inline)

   397         return index, nodemap, cache

   398 

   399     def packentry(self, entry, node, version, rev):

   400         p = _pack(indexformatng, *entry)

   401         if rev == 0:

   402             p = _pack(versionformat, version) + p[4:]

   403         return p

   404 

   405 class revlog(object):

   406     """

   407     the underlying revision storage object

   408 

   409     A revlog consists of two parts, an index and the revision data.

   410 

   411     The index is a file with a fixed record size containing

   412     information on each revision, including its nodeid (hash), the

   413     nodeids of its parents, the position and offset of its data within

   414     the data file, and the revision it's based on. Finally, each entry

   415     contains a linkrev entry that can serve as a pointer to external

   416     data.

   417 

   418     The revision data itself is a linear collection of data chunks.

   419     Each chunk represents a revision and is usually represented as a

   420     delta against the previous chunk. To bound lookup time, runs of

   421     deltas are limited to about 2 times the length of the original

   422     version data. This makes retrieval of a version proportional to

   423     its size, or O(1) relative to the number of revisions.

   424 

   425     Both pieces of the revlog are written to in an append-only

   426     fashion, which means we never need to rewrite a file to insert or

   427     remove data, and can use some simple techniques to avoid the need

   428     for locking while reading.

   429     """

   430     def __init__(self, opener, indexfile, shallowroot=None):

   431         """

   432         create a revlog object

   433 

   434         opener is a function that abstracts the file opening operation

   435         and can be used to implement COW semantics or the like.

   436         """

   437         self.indexfile = indexfile

   438         self.datafile = indexfile[:-2] + ".d"

   439         self.opener = opener

   440         self._cache = None

   441         self._chunkcache = (0, '')

   442         self.nodemap = {nullid: nullrev}

   443         self.index = []

   444         self._shallowroot = shallowroot

   445         self._parentdelta = 0

   446 

   447         v = REVLOG_DEFAULT_VERSION

   448         if hasattr(opener, 'options') and 'defversion' in opener.options:

   449             v = opener.options['defversion']

   450             if v & REVLOGNG:

   451                 v |= REVLOGNGINLINEDATA

   452             if v & REVLOGNG and 'parentdelta' in opener.options:

   453                 self._parentdelta = 1

   454 

   455         if shallowroot:

   456             v |= REVLOGSHALLOW

   457 

   458         i = ''

   459         try:

   460             f = self.opener(self.indexfile)

   461             if "nonlazy" in getattr(self.opener, 'options', {}):

   462                 i = f.read()

   463             else:

   464                 i = f.read(_prereadsize)

   465             if len(i) > 0:

   466                 v = struct.unpack(versionformat, i[:4])[0]

   467         except IOError, inst:

   468             if inst.errno != errno.ENOENT:

   469                 raise

   470 

   471         self.version = v

   472         self._inline = v & REVLOGNGINLINEDATA

   473         self._shallow = v & REVLOGSHALLOW

   474         flags = v & ~0xFFFF

   475         fmt = v & 0xFFFF

   476         if fmt == REVLOGV0 and flags:

   477             raise RevlogError(_("index %s unknown flags %#04x for format v0")

   478                               % (self.indexfile, flags >> 16))

   479         elif fmt == REVLOGNG and flags & ~REVLOGNG_FLAGS:

   480             raise RevlogError(_("index %s unknown flags %#04x for revlogng")

   481                               % (self.indexfile, flags >> 16))

   482         elif fmt > REVLOGNG:

   483             raise RevlogError(_("index %s unknown format %d")

   484                               % (self.indexfile, fmt))

   485 

   486         self._io = revlogio()

   487         if self.version == REVLOGV0:

   488             self._io = revlogoldio()

   489         if i:

   490             try:

   491                 d = self._io.parseindex(f, i, self._inline)

   492             except (ValueError, IndexError):

   493                 raise RevlogError(_("index %s is corrupted") % (self.indexfile))

   494             self.index, self.nodemap, self._chunkcache = d

   495             if not self._chunkcache:

   496                 self._chunkclear()

   497 

   498         # add the magic null revision at -1 (if it hasn't been done already)

   499         if (self.index == [] or isinstance(self.index, lazyindex) or

   500             self.index[-1][7] != nullid) :

   501             self.index.append((0, 0, 0, -1, -1, -1, -1, nullid))

   502 

   503     def _loadindex(self, start, end):

   504         """load a block of indexes all at once from the lazy parser"""

   505         if isinstance(self.index, lazyindex):

   506             self.index.p.loadindex(start, end)

   507 

   508     def _loadindexmap(self):

   509         """loads both the map and the index from the lazy parser"""

   510         if isinstance(self.index, lazyindex):

   511             p = self.index.p

   512             p.loadindex()

   513             self.nodemap = p.map

   514 

   515     def _loadmap(self):

   516         """loads the map from the lazy parser"""

   517         if isinstance(self.nodemap, lazymap):

   518             self.nodemap.p.loadmap()

   519             self.nodemap = self.nodemap.p.map

   520 

   521     def tip(self):

   522         return self.node(len(self.index) - 2)

   523     def __len__(self):

   524         return len(self.index) - 1

   525     def __iter__(self):

   526         for i in xrange(len(self)):

   527             yield i

   528     def rev(self, node):

   529         try:

   530             return self.nodemap[node]

   531         except KeyError:

   532             raise LookupError(node, self.indexfile, _('no node'))

   533     def node(self, rev):

   534         return self.index[rev][7]

   535     def linkrev(self, rev):

   536         return self.index[rev][4]

   537     def parents(self, node):

   538         i = self.index

   539         d = i[self.rev(node)]

   540         return i[d[5]][7], i[d[6]][7] # map revisions to nodes inline

   541     def parentrevs(self, rev):

   542         return self.index[rev][5:7]

   543     def start(self, rev):

   544         return int(self.index[rev][0] >> 16)

   545     def end(self, rev):

   546         return self.start(rev) + self.length(rev)

   547     def length(self, rev):

   548         return self.index[rev][1]

   549     def base(self, rev):

   550         return self.index[rev][3]

   551     def flags(self, rev):

   552         return self.index[rev][0] & 0xFFFF

   553     def rawsize(self, rev):

   554         """return the length of the uncompressed text for a given revision"""

   555         l = self.index[rev][2]

   556         if l >= 0:

   557             return l

   558 

   559         t = self.revision(self.node(rev))

   560         return len(t)

   561     size = rawsize

   562 

   563     def reachable(self, node, stop=None):

   564         """return the set of all nodes ancestral to a given node, including

   565          the node itself, stopping when stop is matched"""

   566         reachable = set((node,))

   567         visit = [node]

   568         if stop:

   569             stopn = self.rev(stop)

   570         else:

   571             stopn = 0

   572         while visit:

   573             n = visit.pop(0)

   574             if n == stop:

   575                 continue

   576             if n == nullid:

   577                 continue

   578             for p in self.parents(n):

   579                 if self.rev(p) < stopn:

   580                     continue

   581                 if p not in reachable:

   582                     reachable.add(p)

   583                     visit.append(p)

   584         return reachable

   585 

   586     def ancestors(self, *revs):

   587         """Generate the ancestors of 'revs' in reverse topological order.

   588 

   589         Yield a sequence of revision numbers starting with the parents

   590         of each revision in revs, i.e., each revision is *not* considered

   591         an ancestor of itself.  Results are in breadth-first order:

   592         parents of each rev in revs, then parents of those, etc.  Result

   593         does not include the null revision."""

   594         visit = list(revs)

   595         seen = set([nullrev])

   596         while visit:

   597             for parent in self.parentrevs(visit.pop(0)):

   598                 if parent not in seen:

   599                     visit.append(parent)

   600                     seen.add(parent)

   601                     yield parent

   602 

   603     def descendants(self, *revs):

   604         """Generate the descendants of 'revs' in revision order.

   605 

   606         Yield a sequence of revision numbers starting with a child of

   607         some rev in revs, i.e., each revision is *not* considered a

   608         descendant of itself.  Results are ordered by revision number (a

   609         topological sort)."""

   610         first = min(revs)

   611         if first == nullrev:

   612             for i in self:

   613                 yield i

   614             return

   615 

   616         seen = set(revs)

   617         for i in xrange(first + 1, len(self)):

   618             for x in self.parentrevs(i):

   619                 if x != nullrev and x in seen:

   620                     seen.add(i)

   621                     yield i

   622                     break

   623 

   624     def findmissing(self, common=None, heads=None):

   625         """Return the ancestors of heads that are not ancestors of common.

   626 

   627         More specifically, return a list of nodes N such that every N

   628         satisfies the following constraints:

   629 

   630           1. N is an ancestor of some node in 'heads'

   631           2. N is not an ancestor of any node in 'common'

   632 

   633         The list is sorted by revision number, meaning it is

   634         topologically sorted.

   635 

   636         'heads' and 'common' are both lists of node IDs.  If heads is

   637         not supplied, uses all of the revlog's heads.  If common is not

   638         supplied, uses nullid."""

   639         if common is None:

   640             common = [nullid]

   641         if heads is None:

   642             heads = self.heads()

   643 

   644         common = [self.rev(n) for n in common]

   645         heads = [self.rev(n) for n in heads]

   646 

   647         # we want the ancestors, but inclusive

   648         has = set(self.ancestors(*common))

   649         has.add(nullrev)

   650         has.update(common)

   651 

   652         # take all ancestors from heads that aren't in has

   653         missing = set()

   654         visit = [r for r in heads if r not in has]

   655         while visit:

   656             r = visit.pop(0)

   657             if r in missing:

   658                 continue

   659             else:

   660                 missing.add(r)

   661                 for p in self.parentrevs(r):

   662                     if p not in has:

   663                         visit.append(p)

   664         missing = list(missing)

   665         missing.sort()

   666         return [self.node(r) for r in missing]

   667 

   668     def nodesbetween(self, roots=None, heads=None):

   669         """Return a topological path from 'roots' to 'heads'.

   670 

   671         Return a tuple (nodes, outroots, outheads) where 'nodes' is a

   672         topologically sorted list of all nodes N that satisfy both of

   673         these constraints:

   674 

   675           1. N is a descendant of some node in 'roots'

   676           2. N is an ancestor of some node in 'heads'

   677 

   678         Every node is considered to be both a descendant and an ancestor

   679         of itself, so every reachable node in 'roots' and 'heads' will be

   680         included in 'nodes'.

   681 

   682         'outroots' is the list of reachable nodes in 'roots', i.e., the

   683         subset of 'roots' that is returned in 'nodes'.  Likewise,

   684         'outheads' is the subset of 'heads' that is also in 'nodes'.

   685 

   686         'roots' and 'heads' are both lists of node IDs.  If 'roots' is

   687         unspecified, uses nullid as the only root.  If 'heads' is

   688         unspecified, uses list of all of the revlog's heads."""

   689         nonodes = ([], [], [])

   690         if roots is not None:

   691             roots = list(roots)

   692             if not roots:

   693                 return nonodes

   694             lowestrev = min([self.rev(n) for n in roots])

   695         else:

   696             roots = [nullid] # Everybody's a descendent of nullid

   697             lowestrev = nullrev

   698         if (lowestrev == nullrev) and (heads is None):

   699             # We want _all_ the nodes!

   700             return ([self.node(r) for r in self], [nullid], list(self.heads()))

   701         if heads is None:

   702             # All nodes are ancestors, so the latest ancestor is the last

   703             # node.

   704             highestrev = len(self) - 1

   705             # Set ancestors to None to signal that every node is an ancestor.

   706             ancestors = None

   707             # Set heads to an empty dictionary for later discovery of heads

   708             heads = {}

   709         else:

   710             heads = list(heads)

   711             if not heads:

   712                 return nonodes

   713             ancestors = set()

   714             # Turn heads into a dictionary so we can remove 'fake' heads.

   715             # Also, later we will be using it to filter out the heads we can't

   716             # find from roots.

   717             heads = dict.fromkeys(heads, 0)

   718             # Start at the top and keep marking parents until we're done.

   719             nodestotag = set(heads)

   720             # Remember where the top was so we can use it as a limit later.

   721             highestrev = max([self.rev(n) for n in nodestotag])

   722             while nodestotag:

   723                 # grab a node to tag

   724                 n = nodestotag.pop()

   725                 # Never tag nullid

   726                 if n == nullid:

   727                     continue

   728                 # A node's revision number represents its place in a

   729                 # topologically sorted list of nodes.

   730                 r = self.rev(n)

   731                 if r >= lowestrev:

   732                     if n not in ancestors:

   733                         # If we are possibly a descendent of one of the roots

   734                         # and we haven't already been marked as an ancestor

   735                         ancestors.add(n) # Mark as ancestor

   736                         # Add non-nullid parents to list of nodes to tag.

   737                         nodestotag.update([p for p in self.parents(n) if

   738                                            p != nullid])

   739                     elif n in heads: # We've seen it before, is it a fake head?

   740                         # So it is, real heads should not be the ancestors of

   741                         # any other heads.

   742                         heads.pop(n)

   743             if not ancestors:

   744                 return nonodes

   745             # Now that we have our set of ancestors, we want to remove any

   746             # roots that are not ancestors.

   747 

   748             # If one of the roots was nullid, everything is included anyway.

   749             if lowestrev > nullrev:

   750                 # But, since we weren't, let's recompute the lowest rev to not

   751                 # include roots that aren't ancestors.

   752 

   753                 # Filter out roots that aren't ancestors of heads

   754                 roots = [n for n in roots if n in ancestors]

   755                 # Recompute the lowest revision

   756                 if roots:

   757                     lowestrev = min([self.rev(n) for n in roots])

   758                 else:

   759                     # No more roots?  Return empty list

   760                     return nonodes

   761             else:

   762                 # We are descending from nullid, and don't need to care about

   763                 # any other roots.

   764                 lowestrev = nullrev

   765                 roots = [nullid]

   766         # Transform our roots list into a set.

   767         descendents = set(roots)

   768         # Also, keep the original roots so we can filter out roots that aren't

   769         # 'real' roots (i.e. are descended from other roots).

   770         roots = descendents.copy()

   771         # Our topologically sorted list of output nodes.

   772         orderedout = []

   773         # Don't start at nullid since we don't want nullid in our output list,

   774         # and if nullid shows up in descedents, empty parents will look like

   775         # they're descendents.

   776         for r in xrange(max(lowestrev, 0), highestrev + 1):

   777             n = self.node(r)

   778             isdescendent = False

   779             if lowestrev == nullrev:  # Everybody is a descendent of nullid

   780                 isdescendent = True

   781             elif n in descendents:

   782                 # n is already a descendent

   783                 isdescendent = True

   784                 # This check only needs to be done here because all the roots

   785                 # will start being marked is descendents before the loop.

   786                 if n in roots:

   787                     # If n was a root, check if it's a 'real' root.

   788                     p = tuple(self.parents(n))

   789                     # If any of its parents are descendents, it's not a root.

   790                     if (p[0] in descendents) or (p[1] in descendents):

   791                         roots.remove(n)

   792             else:

   793                 p = tuple(self.parents(n))

   794                 # A node is a descendent if either of its parents are

   795                 # descendents.  (We seeded the dependents list with the roots

   796                 # up there, remember?)

   797                 if (p[0] in descendents) or (p[1] in descendents):

   798                     descendents.add(n)

   799                     isdescendent = True

   800             if isdescendent and ((ancestors is None) or (n in ancestors)):

   801                 # Only include nodes that are both descendents and ancestors.

   802                 orderedout.append(n)

   803                 if (ancestors is not None) and (n in heads):

   804                     # We're trying to figure out which heads are reachable

   805                     # from roots.

   806                     # Mark this head as having been reached

   807                     heads[n] = 1

   808                 elif ancestors is None:

   809                     # Otherwise, we're trying to discover the heads.

   810                     # Assume this is a head because if it isn't, the next step

   811                     # will eventually remove it.

   812                     heads[n] = 1

   813                     # But, obviously its parents aren't.

   814                     for p in self.parents(n):

   815                         heads.pop(p, None)

   816         heads = [n for n in heads.iterkeys() if heads[n] != 0]

   817         roots = list(roots)

   818         assert orderedout

   819         assert roots

   820         assert heads

   821         return (orderedout, roots, heads)

   822 

   823     def heads(self, start=None, stop=None):

   824         """return the list of all nodes that have no children

   825 

   826         if start is specified, only heads that are descendants of

   827         start will be returned

   828         if stop is specified, it will consider all the revs from stop

   829         as if they had no children

   830         """

   831         if start is None and stop is None:

   832             count = len(self)

   833             if not count:

   834                 return [nullid]

   835             ishead = [1] * (count + 1)

   836             index = self.index

   837             for r in xrange(count):

   838                 e = index[r]

   839                 ishead[e[5]] = ishead[e[6]] = 0

   840             return [self.node(r) for r in xrange(count) if ishead[r]]

   841 

   842         if start is None:

   843             start = nullid

   844         if stop is None:

   845             stop = []

   846         stoprevs = set([self.rev(n) for n in stop])

   847         startrev = self.rev(start)

   848         reachable = set((startrev,))

   849         heads = set((startrev,))

   850 

   851         parentrevs = self.parentrevs

   852         for r in xrange(startrev + 1, len(self)):

   853             for p in parentrevs(r):

   854                 if p in reachable:

   855                     if r not in stoprevs:

   856                         reachable.add(r)

   857                     heads.add(r)

   858                 if p in heads and p not in stoprevs:

   859                     heads.remove(p)

   860 

   861         return [self.node(r) for r in heads]

   862 

   863     def children(self, node):

   864         """find the children of a given node"""

   865         c = []

   866         p = self.rev(node)

   867         for r in range(p + 1, len(self)):

   868             prevs = [pr for pr in self.parentrevs(r) if pr != nullrev]

   869             if prevs:

   870                 for pr in prevs:

   871                     if pr == p:

   872                         c.append(self.node(r))

   873             elif p == nullrev:

   874                 c.append(self.node(r))

   875         return c

   876 

   877     def descendant(self, start, end):

   878         if start == nullrev:

   879             return True

   880         for i in self.descendants(start):

   881             if i == end:

   882                 return True

   883             elif i > end:

   884                 break

   885         return False

   886 

   887     def ancestor(self, a, b):

   888         """calculate the least common ancestor of nodes a and b"""

   889 

   890         # fast path, check if it is a descendant

   891         a, b = self.rev(a), self.rev(b)

   892         start, end = sorted((a, b))

   893         if self.descendant(start, end):

   894             return self.node(start)

   895 

   896         def parents(rev):

   897             return [p for p in self.parentrevs(rev) if p != nullrev]

   898 

   899         c = ancestor.ancestor(a, b, parents)

   900         if c is None:

   901             return nullid

   902 

   903         return self.node(c)

   904 

   905     def _match(self, id):

   906         if isinstance(id, (long, int)):

   907             # rev

   908             return self.node(id)

   909         if len(id) == 20:

   910             # possibly a binary node

   911             # odds of a binary node being all hex in ASCII are 1 in 10**25

   912             try:

   913                 node = id

   914                 self.rev(node) # quick search the index

   915                 return node

   916             except LookupError:

   917                 pass # may be partial hex id

   918         try:

   919             # str(rev)

   920             rev = int(id)

   921             if str(rev) != id:

   922                 raise ValueError

   923             if rev < 0:

   924                 rev = len(self) + rev

   925             if rev < 0 or rev >= len(self):

   926                 raise ValueError

   927             return self.node(rev)

   928         except (ValueError, OverflowError):

   929             pass

   930         if len(id) == 40:

   931             try:

   932                 # a full hex nodeid?

   933                 node = bin(id)

   934                 self.rev(node)

   935                 return node

   936             except (TypeError, LookupError):

   937                 pass

   938 

   939     def _partialmatch(self, id):

   940         if len(id) < 40:

   941             try:

   942                 # hex(node)[:...]

   943                 l = len(id) // 2  # grab an even number of digits

   944                 bin_id = bin(id[:l * 2])

   945                 nl = [n for n in self.nodemap if n[:l] == bin_id]

   946                 nl = [n for n in nl if hex(n).startswith(id)]

   947                 if len(nl) > 0:

   948                     if len(nl) == 1:

   949                         return nl[0]

   950                     raise LookupError(id, self.indexfile,

   951                                       _('ambiguous identifier'))

   952                 return None

   953             except TypeError:

   954                 pass

   955 

   956     def lookup(self, id):

   957         """locate a node based on:

   958             - revision number or str(revision number)

   959             - nodeid or subset of hex nodeid

   960         """

   961         n = self._match(id)

   962         if n is not None:

   963             return n

   964         n = self._partialmatch(id)

   965         if n:

   966             return n

   967 

   968         raise LookupError(id, self.indexfile, _('no match found'))

   969 

   970     def cmp(self, node, text):

   971         """compare text with a given file revision

   972 

   973         returns True if text is different than what is stored.

   974         """

   975         p1, p2 = self.parents(node)

   976         return hash(text, p1, p2) != node

   977 

   978     def _addchunk(self, offset, data):

   979         o, d = self._chunkcache

   980         # try to add to existing cache

   981         if o + len(d) == offset and len(d) + len(data) < _prereadsize:

   982             self._chunkcache = o, d + data

   983         else:

   984             self._chunkcache = offset, data

   985 

   986     def _loadchunk(self, offset, length):

   987         if self._inline:

   988             df = self.opener(self.indexfile)

   989         else:

   990             df = self.opener(self.datafile)

   991 

   992         readahead = max(65536, length)

   993         df.seek(offset)

   994         d = df.read(readahead)

   995         self._addchunk(offset, d)

   996         if readahead > length:

   997             return d[:length]

   998         return d

   999 

  1000     def _getchunk(self, offset, length):

  1001         o, d = self._chunkcache

  1002         l = len(d)

  1003 

  1004         # is it in the cache?

  1005         cachestart = offset - o

  1006         cacheend = cachestart + length

  1007         if cachestart >= 0 and cacheend <= l:

  1008             if cachestart == 0 and cacheend == l:

  1009                 return d # avoid a copy

  1010             return d[cachestart:cacheend]

  1011 

  1012         return self._loadchunk(offset, length)

  1013 

  1014     def _chunkraw(self, startrev, endrev):

  1015         start = self.start(startrev)

  1016         length = self.end(endrev) - start

  1017         if self._inline:

  1018             start += (startrev + 1) * self._io.size

  1019         return self._getchunk(start, length)

  1020 

  1021     def _chunk(self, rev):

  1022         return decompress(self._chunkraw(rev, rev))

  1023 

  1024     def _chunkclear(self):

  1025         self._chunkcache = (0, '')

  1026 

  1027     def deltaparent(self, rev):

  1028         """return previous revision or parentrev according to flags"""

  1029         if self.flags(rev) & REVIDX_PARENTDELTA:

  1030             return self.parentrevs(rev)[0]

  1031         else:

  1032             return rev - 1

  1033 

  1034     def revdiff(self, rev1, rev2):

  1035         """return or calculate a delta between two revisions"""

  1036         if self.base(rev2) != rev2 and self.deltaparent(rev2) == rev1:

  1037             return self._chunk(rev2)

  1038 

  1039         return mdiff.textdiff(self.revision(self.node(rev1)),

  1040                               self.revision(self.node(rev2)))

  1041 

  1042     def revision(self, node):

  1043         """return an uncompressed revision of a given node"""

  1044         cachedrev = None

  1045         if node == nullid:

  1046             return ""

  1047         if self._cache:

  1048             if self._cache[0] == node:

  1049                 return self._cache[2]

  1050             cachedrev = self._cache[1]

  1051 

  1052         # look up what we need to read

  1053         text = None

  1054         rev = self.rev(node)

  1055         base = self.base(rev)

  1056 

  1057         # check rev flags

  1058         if self.flags(rev) & ~REVIDX_KNOWN_FLAGS:

  1059             raise RevlogError(_('incompatible revision flag %x') %

  1060                               (self.flags(rev) & ~REVIDX_KNOWN_FLAGS))

  1061 

  1062         # build delta chain

  1063         self._loadindex(base, rev + 1)

  1064         chain = []

  1065         index = self.index # for performance

  1066         iterrev = rev

  1067         e = index[iterrev]

  1068         while iterrev != base and iterrev != cachedrev:

  1069             chain.append(iterrev)

  1070             if e[0] & REVIDX_PARENTDELTA:

  1071                 iterrev = e[5]

  1072             else:

  1073                 iterrev -= 1

  1074             e = index[iterrev]

  1075         chain.reverse()

  1076         base = iterrev

  1077 

  1078         if iterrev == cachedrev:

  1079             # cache hit

  1080             text = self._cache[2]

  1081 

  1082         # drop cache to save memory

  1083         self._cache = None

  1084 

  1085         self._chunkraw(base, rev)

  1086         if text is None:

  1087             text = self._chunk(base)

  1088 

  1089         bins = [self._chunk(r) for r in chain]

  1090         text = mdiff.patches(text, bins)

  1091         p1, p2 = self.parents(node)

  1092         if (node != hash(text, p1, p2) and

  1093             not (self.flags(rev) & REVIDX_PUNCHED_FLAG)):

  1094             raise RevlogError(_("integrity check failed on %s:%d")

  1095                               % (self.indexfile, rev))

  1096 

  1097         self._cache = (node, rev, text)

  1098         return text

  1099 

  1100     def checkinlinesize(self, tr, fp=None):

  1101         if not self._inline or (self.start(-2) + self.length(-2)) < _maxinline:

  1102             return

  1103 

  1104         trinfo = tr.find(self.indexfile)

  1105         if trinfo is None:

  1106             raise RevlogError(_("%s not found in the transaction")

  1107                               % self.indexfile)

  1108 

  1109         trindex = trinfo[2]

  1110         dataoff = self.start(trindex)

  1111 

  1112         tr.add(self.datafile, dataoff)

  1113 

  1114         if fp:

  1115             fp.flush()

  1116             fp.close()

  1117 

  1118         df = self.opener(self.datafile, 'w')

  1119         try:

  1120             for r in self:

  1121                 df.write(self._chunkraw(r, r))

  1122         finally:

  1123             df.close()

  1124 

  1125         fp = self.opener(self.indexfile, 'w', atomictemp=True)

  1126         self.version &= ~(REVLOGNGINLINEDATA)

  1127         self._inline = False

  1128         for i in self:

  1129             e = self._io.packentry(self.index[i], self.node, self.version, i)

  1130             fp.write(e)

  1131 

  1132         # if we don't call rename, the temp file will never replace the

  1133         # real index

  1134         fp.rename()

  1135 

  1136         tr.replace(self.indexfile, trindex * self._io.size)