bup repositories are in Git format. This library allows us to
interact with the Git data structures.
"""
-import os, errno, zlib, time, subprocess, struct, stat, re, tempfile
+import os, zlib, time, subprocess, struct, stat, re, tempfile
import heapq
from bup.helpers import *
+from bup import _helpers
+
+MIDX_VERSION = 2
verbose = 0
ignore_midx = 0
_typemap = { 'blob':3, 'tree':2, 'commit':1, 'tag':4 }
_typermap = { 3:'blob', 2:'tree', 1:'commit', 4:'tag' }
+_total_searches = 0
+_total_steps = 0
+
class GitError(Exception):
pass
return os.path.join(repodir, sub)
+def auto_midx(objdir):
+ main_exe = os.environ.get('BUP_MAIN_EXE') or sys.argv[0]
+ args = [main_exe, 'midx', '--auto', '--dir', objdir]
+ rv = subprocess.call(args, stdout=open('/dev/null', 'w'))
+ if rv:
+ add_error('%r: returned %d' % (args, rv))
+
+
def mangle_name(name, mode, gitmode):
"""Mangle a file name to present an abstract name for segmented files.
Mangled file names will have the ".bup" extension added to them. If a
class PackIdx:
- """Object representation of a Git pack index file."""
- def __init__(self, filename):
+ def __init__(self):
+ assert(0)
+
+ def find_offset(self, hash):
+ """Get the offset of an object inside the index file."""
+ idx = self._idx_from_hash(hash)
+ if idx != None:
+ return self._ofs_from_idx(idx)
+ return None
+
+ def exists(self, hash):
+ """Return nonempty if the object exists in this index."""
+ return hash and (self._idx_from_hash(hash) != None) and True or None
+
+ def __len__(self):
+ return int(self.fanout[255])
+
+ def _idx_from_hash(self, hash):
+ global _total_searches, _total_steps
+ _total_searches += 1
+ assert(len(hash) == 20)
+ b1 = ord(hash[0])
+ start = self.fanout[b1-1] # range -1..254
+ end = self.fanout[b1] # range 0..255
+ want = str(hash)
+ _total_steps += 1 # lookup table is a step
+ while start < end:
+ _total_steps += 1
+ mid = start + (end-start)/2
+ v = self._idx_to_hash(mid)
+ if v < want:
+ start = mid+1
+ elif v > want:
+ end = mid
+ else: # got it!
+ return mid
+ return None
+
+
+class PackIdxV1(PackIdx):
+ """Object representation of a Git pack index (version 1) file."""
+ def __init__(self, filename, f):
self.name = filename
- self.map = mmap_read(open(filename))
+ self.idxnames = [self.name]
+ self.map = mmap_read(f)
+ self.fanout = list(struct.unpack('!256I',
+ str(buffer(self.map, 0, 256*4))))
+ self.fanout.append(0) # entry "-1"
+ nsha = self.fanout[255]
+ self.shatable = buffer(self.map, 256*4, nsha*24)
+
+ def _ofs_from_idx(self, idx):
+ return struct.unpack('!I', str(self.shatable[idx*24 : idx*24+4]))[0]
+
+ def _idx_to_hash(self, idx):
+ return str(self.shatable[idx*24+4 : idx*24+24])
+
+ def __iter__(self):
+ for i in xrange(self.fanout[255]):
+ yield buffer(self.map, 256*4 + 24*i + 4, 20)
+
+
+class PackIdxV2(PackIdx):
+ """Object representation of a Git pack index (version 2) file."""
+ def __init__(self, filename, f):
+ self.name = filename
+ self.idxnames = [self.name]
+ self.map = mmap_read(f)
assert(str(self.map[0:8]) == '\377tOc\0\0\0\2')
self.fanout = list(struct.unpack('!256I',
str(buffer(self.map, 8, 256*4))))
self.fanout.append(0) # entry "-1"
nsha = self.fanout[255]
+ self.shatable = buffer(self.map, 8 + 256*4, nsha*20)
self.ofstable = buffer(self.map,
8 + 256*4 + nsha*20 + nsha*4,
nsha*4)
str(buffer(self.ofs64table, idx64*8, 8)))[0]
return ofs
- def _idx_from_hash(self, hash):
- assert(len(hash) == 20)
- b1 = ord(hash[0])
- start = self.fanout[b1-1] # range -1..254
- end = self.fanout[b1] # range 0..255
- buf = buffer(self.map, 8 + 256*4, end*20)
- want = str(hash)
- while start < end:
- mid = start + (end-start)/2
- v = str(buf[mid*20:(mid+1)*20])
- if v < want:
- start = mid+1
- elif v > want:
- end = mid
- else: # got it!
- return mid
- return None
-
- def find_offset(self, hash):
- """Get the offset of an object inside the index file."""
- idx = self._idx_from_hash(hash)
- if idx != None:
- return self._ofs_from_idx(idx)
- return None
-
- def exists(self, hash):
- """Return nonempty if the object exists in this index."""
- return hash and (self._idx_from_hash(hash) != None) and True or None
+ def _idx_to_hash(self, idx):
+ return str(self.shatable[idx*20:(idx+1)*20])
def __iter__(self):
for i in xrange(self.fanout[255]):
yield buffer(self.map, 8 + 256*4 + 20*i, 20)
- def __len__(self):
- return int(self.fanout[255])
-
-def extract_bits(buf, nbits):
- """Take the first 'nbits' bits from 'buf' and return them as an integer."""
- mask = (1<<nbits) - 1
- v = struct.unpack('!I', buf[0:4])[0]
- v = (v >> (32-nbits)) & mask
- return v
+extract_bits = _helpers.extract_bits
class PackMidx:
"""
def __init__(self, filename):
self.name = filename
+ self.force_keep = False
assert(filename.endswith('.midx'))
self.map = mmap_read(open(filename))
- if str(self.map[0:8]) == 'MIDX\0\0\0\1':
- log('Warning: ignoring old-style midx %r\n' % filename)
- self.bits = 0
- self.entries = 1
- self.fanout = buffer('\0\0\0\0')
- self.shalist = buffer('\0'*20)
- self.idxnames = []
- else:
- assert(str(self.map[0:8]) == 'MIDX\0\0\0\2')
- self.bits = struct.unpack('!I', self.map[8:12])[0]
- self.entries = 2**self.bits
- self.fanout = buffer(self.map, 12, self.entries*4)
- shaofs = 12 + self.entries*4
- nsha = self._fanget(self.entries-1)
- self.shalist = buffer(self.map, shaofs, nsha*20)
- self.idxnames = str(self.map[shaofs + 20*nsha:]).split('\0')
+ if str(self.map[0:4]) != 'MIDX':
+ log('Warning: skipping: invalid MIDX header in %r\n' % filename)
+ self.force_keep = True
+ return self._init_failed()
+ ver = struct.unpack('!I', self.map[4:8])[0]
+ if ver < MIDX_VERSION:
+ log('Warning: ignoring old-style (v%d) midx %r\n'
+ % (ver, filename))
+ self.force_keep = False # old stuff is boring
+ return self._init_failed()
+ if ver > MIDX_VERSION:
+ log('Warning: ignoring too-new (v%d) midx %r\n'
+ % (ver, filename))
+ self.force_keep = True # new stuff is exciting
+ return self._init_failed()
+
+ self.bits = _helpers.firstword(self.map[8:12])
+ self.entries = 2**self.bits
+ self.fanout = buffer(self.map, 12, self.entries*4)
+ shaofs = 12 + self.entries*4
+ nsha = self._fanget(self.entries-1)
+ self.shalist = buffer(self.map, shaofs, nsha*20)
+ self.idxnames = str(self.map[shaofs + 20*nsha:]).split('\0')
+
+ def _init_failed(self):
+ self.bits = 0
+ self.entries = 1
+ self.fanout = buffer('\0\0\0\0')
+ self.shalist = buffer('\0'*20)
+ self.idxnames = []
def _fanget(self, i):
start = i*4
s = self.fanout[start:start+4]
- return struct.unpack('!I', s)[0]
+ return _helpers.firstword(s)
+
+ def _get(self, i):
+ return str(self.shalist[i*20:(i+1)*20])
def exists(self, hash):
"""Return nonempty if the object exists in the index files."""
+ global _total_searches, _total_steps
+ _total_searches += 1
want = str(hash)
el = extract_bits(want, self.bits)
if el:
start = self._fanget(el-1)
+ startv = el << (32-self.bits)
else:
start = 0
+ startv = 0
end = self._fanget(el)
+ endv = (el+1) << (32-self.bits)
+ _total_steps += 1 # lookup table is a step
+ hashv = _helpers.firstword(hash)
+ #print '(%08x) %08x %08x %08x' % (extract_bits(want, 32), startv, hashv, endv)
while start < end:
- mid = start + (end-start)/2
- v = str(self.shalist[mid*20:(mid+1)*20])
+ _total_steps += 1
+ #print '! %08x %08x %08x %d - %d' % (startv, hashv, endv, start, end)
+ mid = start + (hashv-startv)*(end-start-1)/(endv-startv)
+ #print ' %08x %08x %08x %d %d %d' % (startv, hashv, endv, start, mid, end)
+ v = self._get(mid)
+ #print ' %08x' % self._num(v)
if v < want:
start = mid+1
+ startv = _helpers.firstword(v)
elif v > want:
end = mid
+ endv = _helpers.firstword(v)
else: # got it!
return True
return None
def __iter__(self):
return iter(idxmerge(self.packs))
+ def __len__(self):
+ return sum(len(pack) for pack in self.packs)
+
def exists(self, hash):
"""Return nonempty if the object exists in the index files."""
+ global _total_searches
+ _total_searches += 1
if hash in self.also:
return True
for i in range(len(self.packs)):
p = self.packs[i]
+ _total_searches -= 1 # will be incremented by sub-pack
if p.exists(hash):
# reorder so most recently used packs are searched first
self.packs = [p] + self.packs[:i] + self.packs[i+1:]
d[os.path.join(self.dir, name)] = ix
any += 1
break
- if not any:
- log('midx: removing redundant: %s\n'
- % os.path.basename(ix.name))
+ if not any and not ix.force_keep:
+ debug1('midx: removing redundant: %s\n'
+ % os.path.basename(ix.name))
unlink(ix.name)
for f in os.listdir(self.dir):
full = os.path.join(self.dir, f)
if f.endswith('.idx') and not d.get(full):
- ix = PackIdx(full)
+ ix = open_idx(full)
d[full] = ix
self.packs = list(set(d.values()))
- log('PackIdxList: using %d index%s.\n'
+ debug1('PackIdxList: using %d index%s.\n'
% (len(self.packs), len(self.packs)!=1 and 'es' or ''))
def add(self, hash):
return name
-def idxmerge(idxlist):
+def open_idx(filename):
+ if filename.endswith('.idx'):
+ f = open(filename, 'rb')
+ header = f.read(8)
+ if header[0:4] == '\377tOc':
+ version = struct.unpack('!I', header[4:8])[0]
+ if version == 2:
+ return PackIdxV2(filename, f)
+ else:
+ raise GitError('%s: expected idx file version 2, got %d'
+ % (filename, version))
+ else:
+ return PackIdxV1(filename, f)
+ elif filename.endswith('.midx'):
+ return PackMidx(filename)
+ else:
+ raise GitError('idx filenames must end with .idx or .midx')
+
+
+def idxmerge(idxlist, final_progress=True):
"""Generate a list of all the objects reachable in a PackIdxList."""
total = sum(len(i) for i in idxlist)
iters = (iter(i) for i in idxlist)
heapq.heapreplace(heap, (e, it))
else:
heapq.heappop(heap)
- log('Reading indexes: %.2f%% (%d/%d), done.\n' % (100, total, total))
+ if final_progress:
+ log('Reading indexes: %.2f%% (%d/%d), done.\n' % (100, total, total))
class PackWriter:
self.close()
def _make_objcache(self):
- if not self.objcache:
+ if self.objcache == None:
if self.objcache_maker:
self.objcache = self.objcache_maker()
else:
l.append(msg)
return self.maybe_write('commit', '\n'.join(l))
- def new_commit(self, parent, tree, msg):
+ def new_commit(self, parent, tree, date, msg):
"""Create a commit object in the pack."""
- now = time.time()
userline = '%s <%s@%s>' % (userfullname(), username(), hostname())
commit = self._new_commit(tree, parent,
- userline, now, userline, now,
+ userline, date, userline, date,
msg)
return commit
os.unlink(self.filename + '.map')
os.rename(self.filename + '.pack', nameprefix + '.pack')
os.rename(self.filename + '.idx', nameprefix + '.idx')
+
+ auto_midx(repo('objects/pack'))
return nameprefix
def close(self):
sys.exit(15)
-def _treeparse(buf):
+def treeparse(buf):
+ """Generate a list of (mode, name, hash) tuples of objects from 'buf'."""
ofs = 0
while ofs < len(buf):
z = buf[ofs:].find('\0')
self.p = subprocess.Popen(['git', 'cat-file', '--batch'],
stdin=subprocess.PIPE,
stdout=subprocess.PIPE,
+ close_fds = True,
preexec_fn = _gitenv)
def _fast_get(self, id):
assert(not self.inprogress)
assert(id.find('\n') < 0)
assert(id.find('\r') < 0)
- assert(id[0] != '-')
+ assert(not id.startswith('-'))
self.inprogress = id
self.p.stdin.write('%s\n' % id)
hdr = self.p.stdout.readline()
if hdr.endswith(' missing\n'):
+ self.inprogress = None
raise KeyError('blob %r is missing' % id)
spl = hdr.split(' ')
if len(spl) != 3 or len(spl[0]) != 40:
yield blob
elif type == 'tree':
treefile = ''.join(it)
- for (mode, name, sha) in _treeparse(treefile):
+ for (mode, name, sha) in treeparse(treefile):
for blob in self.join(sha.encode('hex')):
yield blob
elif type == 'commit':
yield d
except StopIteration:
log('booger!\n')
-
-
-def cat(id):
- c = CatPipe()
- for d in c.join(id):
- yield d