mercurial/revlog.py
author mpm@selenic.com
Sat, 27 Aug 2005 14:43:20 -0700
changeset 1091 d62130f99a73
parent 1089 142b5d5ec9cc
child 1099 0cb9c72b6c03
permissions -rw-r--r--
Move hash function back to revlog from node
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     1
"""
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     2
revlog.py - storage back-end for mercurial
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     3
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     4
This provides efficient delta storage with O(1) retrieve and append
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     5
and O(changes) merge between branches
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     6
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     7
Copyright 2005 Matt Mackall <mpm@selenic.com>
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     8
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
     9
This software may be used and distributed according to the terms
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    10
of the GNU General Public License, incorporated herein by reference.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    11
"""
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    12
208
0a37e9c8ad6c revlog: remove some unnecessary imports
mpm@selenic.com
parents: 192
diff changeset
    13
import zlib, struct, sha, binascii, heapq
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    14
from mercurial import mdiff
1089
142b5d5ec9cc Break apart hg.py
mpm@selenic.com
parents: 1083
diff changeset
    15
from node import *
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
    16
1091
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    17
def hash(text, p1, p2):
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    18
    """generate a hash from the given text and its parent hashes
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    19
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    20
    This hash combines both the current file contents and its history
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    21
    in a manner that makes it easy to distinguish nodes with the same
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    22
    content in the revision graph.
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    23
    """
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    24
    l = [p1, p2]
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    25
    l.sort()
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    26
    s = sha.new(l[0])
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    27
    s.update(l[1])
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    28
    s.update(text)
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    29
    return s.digest()
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    30
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    31
def compress(text):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    32
    """ generate a possibly-compressed representation of text """
112
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    33
    if not text: return text
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    34
    if len(text) < 44:
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    35
        if text[0] == '\0': return text
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    36
        return 'u' + text
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    37
    bin = zlib.compress(text)
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    38
    if len(bin) > len(text):
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    39
        if text[0] == '\0': return text
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    40
        return 'u' + text
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    41
    return bin
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    42
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    43
def decompress(bin):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    44
    """ decompress the given input """
112
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    45
    if not bin: return bin
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    46
    t = bin[0]
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    47
    if t == '\0': return bin
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    48
    if t == 'x': return zlib.decompress(bin)
aea6562add6c Make compression more intelligent:
mpm@selenic.com
parents: 98
diff changeset
    49
    if t == 'u': return bin[1:]
1073
7b35a980b982 [PATCH] raise exceptions with Exception subclasses
Bart Trojanowski <bart@jukie.net>
parents: 1062
diff changeset
    50
    raise RevlogError("unknown compression type %s" % t)
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    51
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    52
indexformat = ">4l20s20s20s"
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
    53
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    54
class lazyparser:
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    55
    """
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    56
    this class avoids the need to parse the entirety of large indices
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    57
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    58
    By default we parse and load 1000 entries at a time.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    59
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    60
    If no position is specified, we load the whole index, and replace
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    61
    the lazy objects in revlog with the underlying objects for
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    62
    efficiency in cases where we look at most of the nodes.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    63
    """
323
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    64
    def __init__(self, data, revlog):
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    65
        self.data = data
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    66
        self.s = struct.calcsize(indexformat)
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    67
        self.l = len(data)/self.s
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    68
        self.index = [None] * self.l
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    69
        self.map = {nullid: -1}
323
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    70
        self.all = 0
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    71
        self.revlog = revlog
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    72
323
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    73
    def load(self, pos=None):
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    74
        if self.all: return
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    75
        if pos is not None:
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    76
            block = pos / 1000
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    77
            i = block * 1000
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    78
            end = min(self.l, i + 1000)
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    79
        else:
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    80
            self.all = 1
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    81
            i = 0
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    82
            end = self.l
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    83
            self.revlog.index = self.index
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
    84
            self.revlog.nodemap = self.map
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
    85
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    86
        while i < end:
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    87
            d = self.data[i * self.s: (i + 1) * self.s]
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    88
            e = struct.unpack(indexformat, d)
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    89
            self.index[i] = e
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    90
            self.map[e[6]] = i
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    91
            i += 1
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
    92
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    93
class lazyindex:
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
    94
    """a lazy version of the index array"""
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    95
    def __init__(self, parser):
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    96
        self.p = parser
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    97
    def __len__(self):
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
    98
        return len(self.p.index)
115
39b438eeb25a Make lazyindex load slightly faster
mpm@selenic.com
parents: 112
diff changeset
    99
    def load(self, pos):
39b438eeb25a Make lazyindex load slightly faster
mpm@selenic.com
parents: 112
diff changeset
   100
        self.p.load(pos)
39b438eeb25a Make lazyindex load slightly faster
mpm@selenic.com
parents: 112
diff changeset
   101
        return self.p.index[pos]
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   102
    def __getitem__(self, pos):
115
39b438eeb25a Make lazyindex load slightly faster
mpm@selenic.com
parents: 112
diff changeset
   103
        return self.p.index[pos] or self.load(pos)
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   104
    def append(self, e):
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   105
        self.p.index.append(e)
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   106
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   107
class lazymap:
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   108
    """a lazy version of the node map"""
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   109
    def __init__(self, parser):
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   110
        self.p = parser
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   111
    def load(self, key):
323
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
   112
        if self.p.all: return
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   113
        n = self.p.data.find(key)
86
1b945e8ba67b Friendlier exceptions for unknown node errors
mpm@selenic.com
parents: 84
diff changeset
   114
        if n < 0: raise KeyError("node " + hex(key))
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   115
        pos = n / self.p.s
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   116
        self.p.load(pos)
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   117
    def __contains__(self, key):
323
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
   118
        self.p.load()
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
   119
        return key in self.p.map
97
7a2abee6b0c2 Add iterator to the lazymap code
mpm@selenic.com
parents: 94
diff changeset
   120
    def __iter__(self):
469
e205194ca7ef Various node id lookup tweaks
mpm@selenic.com
parents: 451
diff changeset
   121
        yield nullid
97
7a2abee6b0c2 Add iterator to the lazymap code
mpm@selenic.com
parents: 94
diff changeset
   122
        for i in xrange(self.p.l):
7a2abee6b0c2 Add iterator to the lazymap code
mpm@selenic.com
parents: 94
diff changeset
   123
            try:
7a2abee6b0c2 Add iterator to the lazymap code
mpm@selenic.com
parents: 94
diff changeset
   124
                yield self.p.index[i][6]
7a2abee6b0c2 Add iterator to the lazymap code
mpm@selenic.com
parents: 94
diff changeset
   125
            except:
7a2abee6b0c2 Add iterator to the lazymap code
mpm@selenic.com
parents: 94
diff changeset
   126
                self.p.load(i)
7a2abee6b0c2 Add iterator to the lazymap code
mpm@selenic.com
parents: 94
diff changeset
   127
                yield self.p.index[i][6]
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   128
    def __getitem__(self, key):
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   129
        try:
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   130
            return self.p.map[key]
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   131
        except KeyError:
86
1b945e8ba67b Friendlier exceptions for unknown node errors
mpm@selenic.com
parents: 84
diff changeset
   132
            try:
1b945e8ba67b Friendlier exceptions for unknown node errors
mpm@selenic.com
parents: 84
diff changeset
   133
                self.load(key)
1b945e8ba67b Friendlier exceptions for unknown node errors
mpm@selenic.com
parents: 84
diff changeset
   134
                return self.p.map[key]
1b945e8ba67b Friendlier exceptions for unknown node errors
mpm@selenic.com
parents: 84
diff changeset
   135
            except KeyError:
1b945e8ba67b Friendlier exceptions for unknown node errors
mpm@selenic.com
parents: 84
diff changeset
   136
                raise KeyError("node " + hex(key))
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   137
    def __setitem__(self, key, val):
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   138
        self.p.map[key] = val
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   139
1073
7b35a980b982 [PATCH] raise exceptions with Exception subclasses
Bart Trojanowski <bart@jukie.net>
parents: 1062
diff changeset
   140
class RevlogError(Exception): pass
7b35a980b982 [PATCH] raise exceptions with Exception subclasses
Bart Trojanowski <bart@jukie.net>
parents: 1062
diff changeset
   141
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   142
class revlog:
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   143
    """
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   144
    the underlying revision storage object
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   145
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   146
    A revlog consists of two parts, an index and the revision data.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   147
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   148
    The index is a file with a fixed record size containing
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   149
    information on each revision, includings its nodeid (hash), the
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   150
    nodeids of its parents, the position and offset of its data within
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   151
    the data file, and the revision it's based on. Finally, each entry
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   152
    contains a linkrev entry that can serve as a pointer to external
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   153
    data.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   154
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   155
    The revision data itself is a linear collection of data chunks.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   156
    Each chunk represents a revision and is usually represented as a
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   157
    delta against the previous chunk. To bound lookup time, runs of
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   158
    deltas are limited to about 2 times the length of the original
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   159
    version data. This makes retrieval of a version proportional to
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   160
    its size, or O(1) relative to the number of revisions.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   161
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   162
    Both pieces of the revlog are written to in an append-only
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   163
    fashion, which means we never need to rewrite a file to insert or
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   164
    remove data, and can use some simple techniques to avoid the need
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   165
    for locking while reading.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   166
    """
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   167
    def __init__(self, opener, indexfile, datafile):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   168
        """
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   169
        create a revlog object
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   170
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   171
        opener is a function that abstracts the file opening operation
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   172
        and can be used to implement COW semantics or the like.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   173
        """
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   174
        self.indexfile = indexfile
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   175
        self.datafile = datafile
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   176
        self.opener = opener
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   177
        self.cache = None
116
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   178
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   179
        try:
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   180
            i = self.opener(self.indexfile).read()
73
ee1cbe841e01 Change revlog to use new patch code
mpm@selenic.com
parents: 71
diff changeset
   181
        except IOError:
76
d993ebd69d28 Add lazy{parser,index,map} to speed up processing of index files
mpm@selenic.com
parents: 73
diff changeset
   182
            i = ""
116
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   183
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   184
        if len(i) > 10000:
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   185
            # big index, let's parse it on demand
323
c6f0673ab7e9 lazyparser speed ups
mpm@selenic.com
parents: 306
diff changeset
   186
            parser = lazyparser(i, self)
116
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   187
            self.index = lazyindex(parser)
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   188
            self.nodemap = lazymap(parser)
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   189
        else:
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   190
            s = struct.calcsize(indexformat)
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   191
            l = len(i) / s
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   192
            self.index = [None] * l
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   193
            m = [None] * l
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   194
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   195
            n = 0
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   196
            for f in xrange(0, len(i), s):
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   197
                # offset, size, base, linkrev, p1, p2, nodeid
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   198
                e = struct.unpack(indexformat, i[f:f + s])
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   199
                m[n] = (e[6], n)
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   200
                self.index[n] = e
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   201
                n += 1
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   202
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   203
            self.nodemap = dict(m)
e484cd5ec282 Only use lazy indexing for big indices and avoid the overhead of the
mpm@selenic.com
parents: 115
diff changeset
   204
            self.nodemap[nullid] = -1
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   205
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   206
    def tip(self): return self.node(len(self.index) - 1)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   207
    def count(self): return len(self.index)
26
9cf83bf9ad38 Simplify integrity checking
mpm@selenic.com
parents: 14
diff changeset
   208
    def node(self, rev): return (rev < 0) and nullid or self.index[rev][6]
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   209
    def rev(self, node): return self.nodemap[node]
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   210
    def linkrev(self, node): return self.index[self.nodemap[node]][3]
2
ecf3fd948051 Handle nullid better for ancestor
mpm@selenic.com
parents: 0
diff changeset
   211
    def parents(self, node):
ecf3fd948051 Handle nullid better for ancestor
mpm@selenic.com
parents: 0
diff changeset
   212
        if node == nullid: return (nullid, nullid)
ecf3fd948051 Handle nullid better for ancestor
mpm@selenic.com
parents: 0
diff changeset
   213
        return self.index[self.nodemap[node]][4:6]
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   214
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   215
    def start(self, rev): return self.index[rev][0]
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   216
    def length(self, rev): return self.index[rev][1]
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   217
    def end(self, rev): return self.start(rev) + self.length(rev)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   218
    def base(self, rev): return self.index[rev][2]
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   219
1074
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   220
    def reachable(self, rev, stop=None):
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   221
        reachable = {}
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   222
        visit = [rev]
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   223
        reachable[rev] = 1
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   224
        if stop:
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   225
            stopn = self.rev(stop)
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   226
        else:
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   227
            stopn = 0
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   228
        while visit:
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   229
            n = visit.pop(0)
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   230
            if n == stop:
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   231
                continue
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   232
            if n == nullid:
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   233
                continue
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   234
            for p in self.parents(n):
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   235
                if self.rev(p) < stopn:
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   236
                    continue
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   237
                if p not in reachable:
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   238
                    reachable[p] = 1
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   239
                    visit.append(p)
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   240
        return reachable
55bf5cfde69e Add revlog.reachable to find a graph of ancestors for a given rev
mason@suse.com
parents: 1073
diff changeset
   241
902
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   242
    def heads(self, stop=None):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   243
        """return the list of all nodes that have no children"""
221
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   244
        p = {}
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   245
        h = []
902
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   246
        stoprev = 0
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   247
        if stop and stop in self.nodemap:
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   248
            stoprev = self.rev(stop)
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   249
243
9a9ea2d1d3c4 fix heads for rev 0
mpm@selenic.com
parents: 241
diff changeset
   250
        for r in range(self.count() - 1, -1, -1):
221
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   251
            n = self.node(r)
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   252
            if n not in p:
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   253
                h.append(n)
902
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   254
            if n == stop:
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   255
                break
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   256
            if r < stoprev:
c749ca37aed1 Add optional stop revision to revlog.heads
mason@suse.com
parents: 896
diff changeset
   257
                break
221
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   258
            for pn in self.parents(n):
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   259
                p[pn] = 1
2bfe525ef6ca Beginning of multi-head support
mpm@selenic.com
parents: 208
diff changeset
   260
        return h
370
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   261
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   262
    def children(self, node):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   263
        """find the children of a given node"""
370
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   264
        c = []
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   265
        p = self.rev(node)
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   266
        for r in range(p + 1, self.count()):
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   267
            n = self.node(r)
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   268
            for pn in self.parents(n):
854
473c030d34a6 Fixed revlog.children.
Tristan Wibberley <tristan@wibberley.org>
parents: 655
diff changeset
   269
                if pn == node:
473c030d34a6 Fixed revlog.children.
Tristan Wibberley <tristan@wibberley.org>
parents: 655
diff changeset
   270
                    c.append(n)
370
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   271
                    continue
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   272
                elif pn == nullid:
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   273
                    continue
c90385d82aec revlog: add a children function
mpm@selenic.com
parents: 330
diff changeset
   274
        return c
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   275
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   276
    def lookup(self, id):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   277
        """locate a node based on revision number or subset of hex nodeid"""
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   278
        try:
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   279
            rev = int(id)
469
e205194ca7ef Various node id lookup tweaks
mpm@selenic.com
parents: 451
diff changeset
   280
            if str(rev) != id: raise ValueError
e205194ca7ef Various node id lookup tweaks
mpm@selenic.com
parents: 451
diff changeset
   281
            if rev < 0: rev = self.count() + rev
476
0a338d506268 Really _call_ method revlog.count in revlog.lookup()
Thomas Arendsen Hein <thomas@intevation.de>
parents: 469
diff changeset
   282
            if rev < 0 or rev >= self.count(): raise ValueError
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   283
            return self.node(rev)
469
e205194ca7ef Various node id lookup tweaks
mpm@selenic.com
parents: 451
diff changeset
   284
        except (ValueError, OverflowError):
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   285
            c = []
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   286
            for n in self.nodemap:
469
e205194ca7ef Various node id lookup tweaks
mpm@selenic.com
parents: 451
diff changeset
   287
                if hex(n).startswith(id):
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   288
                    c.append(n)
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   289
            if len(c) > 1: raise KeyError("Ambiguous identifier")
67
a182f2561c8e Add tag support
mpm@selenic.com
parents: 65
diff changeset
   290
            if len(c) < 1: raise KeyError("No match found")
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   291
            return c[0]
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   292
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   293
        return None
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   294
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   295
    def diff(self, a, b):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   296
        """return a delta between two revisions"""
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   297
        return mdiff.textdiff(a, b)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   298
73
ee1cbe841e01 Change revlog to use new patch code
mpm@selenic.com
parents: 71
diff changeset
   299
    def patches(self, t, pl):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   300
        """apply a list of patches to a string"""
73
ee1cbe841e01 Change revlog to use new patch code
mpm@selenic.com
parents: 71
diff changeset
   301
        return mdiff.patches(t, pl)
ee1cbe841e01 Change revlog to use new patch code
mpm@selenic.com
parents: 71
diff changeset
   302
119
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   303
    def delta(self, node):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   304
        """return or calculate a delta between a node and its predecessor"""
119
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   305
        r = self.rev(node)
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   306
        b = self.base(r)
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   307
        if r == b:
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   308
            return self.diff(self.revision(self.node(r - 1)),
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   309
                             self.revision(node))
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   310
        else:
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   311
            f = self.opener(self.datafile)
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   312
            f.seek(self.start(r))
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   313
            data = f.read(self.length(r))
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   314
        return decompress(data)
c7a66f9752a4 Add code to retrieve or construct a revlog delta
mpm@selenic.com
parents: 117
diff changeset
   315
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   316
    def revision(self, node):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   317
        """return an uncompressed revision of a given"""
36
da28286bf6b7 Add smart node lookup by substring or by rev number
mpm@selenic.com
parents: 26
diff changeset
   318
        if node == nullid: return ""
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   319
        if self.cache and self.cache[0] == node: return self.cache[2]
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   320
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   321
        # look up what we need to read
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   322
        text = None
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   323
        rev = self.rev(node)
117
2ac722ad1a9d Make revision code slightly faster
mpm@selenic.com
parents: 116
diff changeset
   324
        start, length, base, link, p1, p2, node = self.index[rev]
2ac722ad1a9d Make revision code slightly faster
mpm@selenic.com
parents: 116
diff changeset
   325
        end = start + length
2ac722ad1a9d Make revision code slightly faster
mpm@selenic.com
parents: 116
diff changeset
   326
        if base != rev: start = self.start(base)
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   327
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   328
        # do we have useful data cached?
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   329
        if self.cache and self.cache[1] >= base and self.cache[1] < rev:
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   330
            base = self.cache[1]
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   331
            start = self.start(base + 1)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   332
            text = self.cache[2]
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   333
            last = 0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   334
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   335
        f = self.opener(self.datafile)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   336
        f.seek(start)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   337
        data = f.read(end - start)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   338
651
08b65d66f3e7 Fix an odd revlog bug
Matt Mackall <mpm@selenic.com>
parents: 644
diff changeset
   339
        if text is None:
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   340
            last = self.length(base)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   341
            text = decompress(data[:last])
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   342
71
47c9a869adee Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents: 67
diff changeset
   343
        bins = []
64
b3e2ddff0159 Diff in subdirectories from Jake Edge
mpm@selenic.com
parents: 46
diff changeset
   344
        for r in xrange(base + 1, rev + 1):
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   345
            s = self.length(r)
71
47c9a869adee Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents: 67
diff changeset
   346
            bins.append(decompress(data[last:last + s]))
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   347
            last = last + s
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   348
71
47c9a869adee Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents: 67
diff changeset
   349
        text = mdiff.patches(text, bins)
47c9a869adee Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents: 67
diff changeset
   350
26
9cf83bf9ad38 Simplify integrity checking
mpm@selenic.com
parents: 14
diff changeset
   351
        if node != hash(text, p1, p2):
98
3dde7c87e36d Add paranoia to diff code
mpm@selenic.com
parents: 97
diff changeset
   352
            raise IOError("integrity check failed on %s:%d"
3dde7c87e36d Add paranoia to diff code
mpm@selenic.com
parents: 97
diff changeset
   353
                          % (self.datafile, rev))
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   354
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   355
        self.cache = (node, rev, text)
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   356
        return text
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   357
644
6ebe118280bd Performance enhancements for manifest.add()
mason@suse.com
parents: 547
diff changeset
   358
    def addrevision(self, text, transaction, link, p1=None, p2=None, d=None):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   359
        """add a revision to the log
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   360
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   361
        text - the revision data to add
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   362
        transaction - the transaction object used for rollback
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   363
        link - the linkrev data to add
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   364
        p1, p2 - the parent nodeids of the revision
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   365
        d - an optional precomputed delta
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   366
        """
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   367
        if text is None: text = ""
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   368
        if p1 is None: p1 = self.tip()
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   369
        if p2 is None: p2 = nullid
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   370
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   371
        node = hash(text, p1, p2)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   372
301
5add718d92db revlog: allow duplicates
mpm@selenic.com
parents: 243
diff changeset
   373
        if node in self.nodemap:
5add718d92db revlog: allow duplicates
mpm@selenic.com
parents: 243
diff changeset
   374
            return node
5add718d92db revlog: allow duplicates
mpm@selenic.com
parents: 243
diff changeset
   375
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   376
        n = self.count()
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   377
        t = n - 1
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   378
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   379
        if n:
64
b3e2ddff0159 Diff in subdirectories from Jake Edge
mpm@selenic.com
parents: 46
diff changeset
   380
            base = self.base(t)
b3e2ddff0159 Diff in subdirectories from Jake Edge
mpm@selenic.com
parents: 46
diff changeset
   381
            start = self.start(base)
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   382
            end = self.end(t)
644
6ebe118280bd Performance enhancements for manifest.add()
mason@suse.com
parents: 547
diff changeset
   383
            if not d:
6ebe118280bd Performance enhancements for manifest.add()
mason@suse.com
parents: 547
diff changeset
   384
                prev = self.revision(self.tip())
6ebe118280bd Performance enhancements for manifest.add()
mason@suse.com
parents: 547
diff changeset
   385
                d = self.diff(prev, text)
98
3dde7c87e36d Add paranoia to diff code
mpm@selenic.com
parents: 97
diff changeset
   386
            data = compress(d)
64
b3e2ddff0159 Diff in subdirectories from Jake Edge
mpm@selenic.com
parents: 46
diff changeset
   387
            dist = end - start + len(data)
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   388
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   389
        # full versions are inserted when the needed deltas
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   390
        # become comparable to the uncompressed text
64
b3e2ddff0159 Diff in subdirectories from Jake Edge
mpm@selenic.com
parents: 46
diff changeset
   391
        if not n or dist > len(text) * 2:
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   392
            data = compress(text)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   393
            base = n
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   394
        else:
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   395
            base = self.base(t)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   396
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   397
        offset = 0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   398
        if t >= 0:
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   399
            offset = self.end(t)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   400
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   401
        e = (offset, len(data), base, link, p1, p2, node)
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   402
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   403
        self.index.append(e)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   404
        self.nodemap[node] = n
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   405
        entry = struct.pack(indexformat, *e)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   406
26
9cf83bf9ad38 Simplify integrity checking
mpm@selenic.com
parents: 14
diff changeset
   407
        transaction.add(self.datafile, e[0])
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   408
        self.opener(self.datafile, "a").write(data)
41
df3f46253878 Fix truncate logic for indices again
mpm@selenic.com
parents: 36
diff changeset
   409
        transaction.add(self.indexfile, n * len(entry))
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   410
        self.opener(self.indexfile, "a").write(entry)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   411
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   412
        self.cache = (node, n, text)
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   413
        return node
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   414
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   415
    def ancestor(self, a, b):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   416
        """calculate the least common ancestor of nodes a and b"""
147
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   417
        # calculate the distance of every node from root
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   418
        dist = {nullid: 0}
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   419
        for i in xrange(self.count()):
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   420
            n = self.node(i)
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   421
            p1, p2 = self.parents(n)
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   422
            dist[n] = max(dist[p1], dist[p2]) + 1
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   423
147
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   424
        # traverse ancestors in order of decreasing distance from root
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   425
        def ancestors(node):
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   426
            # we store negative distances because heap returns smallest member
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   427
            h = [(-dist[node], node)]
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   428
            seen = {}
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   429
            earliest = self.count()
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   430
            while h:
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   431
                d, n = heapq.heappop(h)
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   432
                if n not in seen:
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   433
                    seen[n] = 1
381
024ee0f8722a Ancestor algorithm fix
mpm@selenic.com
parents: 377
diff changeset
   434
                    r = self.rev(n)
024ee0f8722a Ancestor algorithm fix
mpm@selenic.com
parents: 377
diff changeset
   435
                    yield (-d, r, n)
147
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   436
                    for p in self.parents(n):
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   437
                        heapq.heappush(h, (-dist[p], p))
45
f2b2d5daec30 Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents: 41
diff changeset
   438
147
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   439
        x = ancestors(a)
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   440
        y = ancestors(b)
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   441
        lx = x.next()
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   442
        ly = y.next()
45
f2b2d5daec30 Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents: 41
diff changeset
   443
147
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   444
        # increment each ancestor list until it is closer to root than
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   445
        # the other, or they match
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   446
        while 1:
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   447
            if lx == ly:
381
024ee0f8722a Ancestor algorithm fix
mpm@selenic.com
parents: 377
diff changeset
   448
                return lx[2]
147
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   449
            elif lx < ly:
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   450
                ly = y.next()
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   451
            elif lx > ly:
b6d8ed7aeba0 A new ancestor algorithm
mpm@selenic.com
parents: 126
diff changeset
   452
                lx = x.next()
0
9117c6561b0b Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff changeset
   453
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   454
    def group(self, linkmap):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   455
        """calculate a delta group
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   456
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   457
        Given a list of changeset revs, return a set of deltas and
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   458
        metadata corresponding to nodes. the first delta is
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   459
        parent(nodes[0]) -> nodes[0] the receiver is guaranteed to
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   460
        have this parent as it has all history before these
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   461
        changesets. parent is parent[0]
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   462
        """
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   463
        revs = []
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   464
        needed = {}
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   465
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   466
        # find file nodes/revs that match changeset revs
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   467
        for i in xrange(0, self.count()):
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   468
            if self.index[i][3] in linkmap:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   469
                revs.append(i)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   470
                needed[i] = 1
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   471
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   472
        # if we don't have any revisions touched by these changesets, bail
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   473
        if not revs:
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   474
            yield struct.pack(">l", 0)
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   475
            return
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   476
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   477
        # add the parent of the first rev
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   478
        p = self.parents(self.node(revs[0]))[0]
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   479
        revs.insert(0, self.rev(p))
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   480
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   481
        # for each delta that isn't contiguous in the log, we need to
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   482
        # reconstruct the base, reconstruct the result, and then
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   483
        # calculate the delta. We also need to do this where we've
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   484
        # stored a full version and not a delta
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   485
        for i in xrange(0, len(revs) - 1):
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   486
            a, b = revs[i], revs[i + 1]
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   487
            if a + 1 != b or self.base(b) == b:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   488
                for j in xrange(self.base(a), a + 1):
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   489
                    needed[j] = 1
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   490
                for j in xrange(self.base(b), b + 1):
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   491
                    needed[j] = 1
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   492
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   493
        # calculate spans to retrieve from datafile
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   494
        needed = needed.keys()
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   495
        needed.sort()
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   496
        spans = []
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   497
        oo = -1
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   498
        ol = 0
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   499
        for n in needed:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   500
            if n < 0: continue
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   501
            o = self.start(n)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   502
            l = self.length(n)
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   503
            if oo + ol == o: # can we merge with the previous?
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   504
                nl = spans[-1][2]
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   505
                nl.append((n, l))
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   506
                ol += l
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   507
                spans[-1] = (oo, ol, nl)
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   508
            else:
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   509
                oo = o
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   510
                ol = l
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   511
                spans.append((oo, ol, [(n, l)]))
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   512
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   513
        # read spans in, divide up chunks
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   514
        chunks = {}
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   515
        for span in spans:
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   516
            # we reopen the file for each span to make http happy for now
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   517
            f = self.opener(self.datafile)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   518
            f.seek(span[0])
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   519
            data = f.read(span[1])
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   520
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   521
            # divide up the span
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   522
            pos = 0
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   523
            for r, l in span[2]:
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   524
                chunks[r] = decompress(data[pos: pos + l])
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   525
                pos += l
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   526
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   527
        # helper to reconstruct intermediate versions
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   528
        def construct(text, base, rev):
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   529
            bins = [chunks[r] for r in xrange(base + 1, rev + 1)]
71
47c9a869adee Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents: 67
diff changeset
   530
            return mdiff.patches(text, bins)
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   531
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   532
        # build deltas
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   533
        deltas = []
71
47c9a869adee Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents: 67
diff changeset
   534
        for d in xrange(0, len(revs) - 1):
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   535
            a, b = revs[d], revs[d + 1]
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   536
            n = self.node(b)
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   537
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   538
            # do we need to construct a new delta?
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   539
            if a + 1 != b or self.base(b) == b:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   540
                if a >= 0:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   541
                    base = self.base(a)
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   542
                    ta = chunks[self.base(a)]
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   543
                    ta = construct(ta, base, a)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   544
                else:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   545
                    ta = ""
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   546
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   547
                base = self.base(b)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   548
                if a > base:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   549
                    base = a
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   550
                    tb = ta
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   551
                else:
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   552
                    tb = chunks[self.base(b)]
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   553
                tb = construct(tb, base, b)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   554
                d = self.diff(ta, tb)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   555
            else:
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   556
                d = chunks[b]
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   557
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   558
            p = self.parents(n)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   559
            meta = n + p[0] + p[1] + linkmap[self.linkrev(n)]
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   560
            l = struct.pack(">l", len(meta) + len(d) + 4)
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   561
            yield l
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   562
            yield meta
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   563
            yield d
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   564
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   565
        yield struct.pack(">l", 0)
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   566
1062
6d5a62a549fa pep-0008 cleanup
benoit.boissinot@ens-lyon.fr
parents: 902
diff changeset
   567
    def addgroup(self, revs, linkmapper, transaction, unique=0):
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   568
        """
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   569
        add a delta group
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   570
1083
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   571
        given a set of deltas, add them to the revision log. the
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   572
        first delta is against its parent, which should be in our
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   573
        log, the rest are against the previous delta.
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   574
        """
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   575
30974cf73435 Add some docstrings to revlog.py
mpm@selenic.com
parents: 1074
diff changeset
   576
        #track the base of the current delta log
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   577
        r = self.count()
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   578
        t = r - 1
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   579
        node = nullid
515
03f27b1381f9 Whitespace cleanups
mpm@selenic.com
parents: 484
diff changeset
   580
655
b3bba126b04a Fix out of range regression
Matt Mackall <mpm@selenic.com>
parents: 653
diff changeset
   581
        base = prev = -1
653
94cdd02792b5 Fix corruption resulting from skipping parts of a revision group
Matt Mackall <mpm@selenic.com>
parents: 651
diff changeset
   582
        start = end = measure = 0
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   583
        if r:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   584
            start = self.start(self.base(t))
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   585
            end = self.end(t)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   586
            measure = self.length(self.base(t))
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   587
            base = self.base(t)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   588
            prev = self.tip()
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   589
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   590
        transaction.add(self.datafile, end)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   591
        transaction.add(self.indexfile, r * struct.calcsize(indexformat))
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   592
        dfh = self.opener(self.datafile, "a")
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   593
        ifh = self.opener(self.indexfile, "a")
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   594
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   595
        # loop through our set of deltas
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   596
        chain = None
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   597
        for chunk in revs:
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   598
            node, p1, p2, cs = struct.unpack("20s20s20s20s", chunk[:80])
94
7daef883134f Refactor merge code
mpm@selenic.com
parents: 86
diff changeset
   599
            link = linkmapper(cs)
77
bed15e766511 Fix bug in lazymap code
mpm@selenic.com
parents: 76
diff changeset
   600
            if node in self.nodemap:
224
ccbcc4d76f81 fix bad assumption about uniqueness of file versions
mpm@selenic.com
parents: 221
diff changeset
   601
                # this can happen if two branches make the same change
ccbcc4d76f81 fix bad assumption about uniqueness of file versions
mpm@selenic.com
parents: 221
diff changeset
   602
                if unique:
1073
7b35a980b982 [PATCH] raise exceptions with Exception subclasses
Bart Trojanowski <bart@jukie.net>
parents: 1062
diff changeset
   603
                    raise RevlogError("already have %s" % hex(node[:4]))
653
94cdd02792b5 Fix corruption resulting from skipping parts of a revision group
Matt Mackall <mpm@selenic.com>
parents: 651
diff changeset
   604
                chain = node
224
ccbcc4d76f81 fix bad assumption about uniqueness of file versions
mpm@selenic.com
parents: 221
diff changeset
   605
                continue
192
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   606
            delta = chunk[80:]
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   607
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   608
            if not chain:
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   609
                # retrieve the parent revision of the delta chain
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   610
                chain = p1
5d8553352d2e Changes to network protocol
mpm@selenic.com
parents: 155
diff changeset
   611
                if not chain in self.nodemap:
1073
7b35a980b982 [PATCH] raise exceptions with Exception subclasses
Bart Trojanowski <bart@jukie.net>
parents: 1062
diff changeset
   612
                    raise RevlogError("unknown base %s" % short(chain[:4]))
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   613
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   614
            # full versions are inserted when the needed deltas become
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   615
            # comparable to the uncompressed text or when the previous
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   616
            # version is not the one we have a delta against. We use
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   617
            # the size of the previous full rev as a proxy for the
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   618
            # current size.
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   619
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   620
            if chain == prev:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   621
                cdelta = compress(delta)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   622
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   623
            if chain != prev or (end - start + len(cdelta)) > measure * 2:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   624
                # flush our writes here so we can read it in revision
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   625
                dfh.flush()
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   626
                ifh.flush()
65
d40cc5aacc31 Fix up a bunch of bugs in the new merge code
mpm@selenic.com
parents: 64
diff changeset
   627
                text = self.revision(chain)
73
ee1cbe841e01 Change revlog to use new patch code
mpm@selenic.com
parents: 71
diff changeset
   628
                text = self.patches(text, [delta])
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   629
                chk = self.addrevision(text, transaction, link, p1, p2)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   630
                if chk != node:
1073
7b35a980b982 [PATCH] raise exceptions with Exception subclasses
Bart Trojanowski <bart@jukie.net>
parents: 1062
diff changeset
   631
                    raise RevlogError("consistency error adding group")
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   632
                measure = len(text)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   633
            else:
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   634
                e = (end, len(cdelta), self.base(t), link, p1, p2, node)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   635
                self.index.append(e)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   636
                self.nodemap[node] = r
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   637
                dfh.write(cdelta)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   638
                ifh.write(struct.pack(indexformat, *e))
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   639
65
d40cc5aacc31 Fix up a bunch of bugs in the new merge code
mpm@selenic.com
parents: 64
diff changeset
   640
            t, r, chain, prev = r, r + 1, node, node
46
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   641
            start = self.start(self.base(t))
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   642
            end = self.end(t)
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   643
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   644
        dfh.close()
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   645
        ifh.close()
93e868fa0db8 Add changegroup support
mpm@selenic.com
parents: 45
diff changeset
   646
        return node