1from __future__ import print_function
2from __future__ import absolute_import
3# Written by Bram Cohen and Ross Cohen
4# Maintained by Chris Hutchinson
5# see LICENSE.txt for license information
6
7from builtins import next
8from builtins import str
9from builtins import range
10from builtins import object
11from future.utils import raise_
12from .bencode import bdecode, bencode
13import binascii
14from .db import db
15from .DFS import DFS
16from .merge import MergeError, replay
17from os import path
18from sha import sha
19import struct
20from time import localtime, strftime
21from xml.sax import saxutils
22import zlib
23
24roothandle = '\xdfp\xce\xbaNt5\xf9\xa1\xabd\xf2\xc4\x87\xc5\xd1\x0bI\x8d\xb4'
25rootnode = '\xb3L\xac\x1f\x98B\x15\\\x8c\t0&\xd7m\xecK\xdd\n\x81\xc4'
26
27class HistoryError(Exception):
28    pass
29
30def damerge(*dargs):
31    dc = {}
32    for dm in dargs:
33        dc.update({}.fromkeys(dm))
34    return list(dc.keys())
35
36# keeping this one for possible performance reasons, need to measure
37def dmerge(da, db):
38    dc = {}.fromkeys(da)
39    dc.update({}.fromkeys(db))
40    return list(dc.keys())
41
42def rename_conflict_check(linfo, rinfo):
43    def _is_applied(line_points, points):
44        assert list == type(line_points)
45        for p in line_points:
46            if p in points:
47                return True
48        return False
49
50    # if we're merging, maybe nothing is different. this shields the root
51    # directory from causing problems
52    if linfo == rinfo:
53        return ('local', linfo['rename point'])
54
55    lapplied = _is_applied(linfo['rename point'], rinfo['points'])
56    rapplied = _is_applied(rinfo['rename point'], linfo['points'])
57
58    try:
59        if     linfo['name'] == rinfo['name'] and \
60               linfo['parent'] == rinfo['parent']:
61            return ('local', dmerge(linfo['rename point'], rinfo['rename point']))
62    except KeyError:
63        assert linfo['rename point'] == rinfo['rename point'] == [rootnode]
64        raise HistoryError('cannot rename root directory')
65
66    if rapplied and not lapplied:
67        return ('local', linfo['rename point'])
68    if not rapplied and lapplied:
69        return ('remote', rinfo['rename point'])
70
71    return ('conflict', None)
72
73def _name_use_count(co, state, point, func, txn):
74    cursor = co.allnamesdb.cursor(txn=txn)
75    lookup = state['parent'] + state['name']
76    try:
77        key, value = cursor.set(lookup)
78    except (db.DBNotFoundError, TypeError):
79        return []
80    named = []
81    while key == lookup:
82        vinfo = func(co, value, point, txn)
83        if vinfo is not None:
84            if 'delete' not in vinfo and vinfo['parent'] == state['parent'] and vinfo['name'] == state['name']:
85                named.append(value)
86        # next_dup() is broken
87        foo = next(cursor)
88        if foo is None:
89            break
90        key, value = foo
91    cursor.close()
92    return named
93
94def name_use_count(co, state, point, txn):
95    return _name_use_count(co, state, point, handle_name_at_point, txn)
96
97def _children_count(co, handle, point, func, txn):
98    cursor = co.allnamesdb.cursor(txn=txn)
99    try:
100        foo = cursor.set_range(handle)
101    except (db.DBNotFoundError, TypeError):
102        foo = None
103    children = {}
104    while foo is not None:
105        key, value = foo
106        parent = key[:20]
107        if parent != handle:
108            break
109        vinfo = func(co, value, point, txn)
110        if vinfo is not None:
111            if 'delete' not in vinfo and vinfo['parent'] == handle:
112                children[value] = None
113        foo = next(cursor)
114    cursor.close()
115    return list(children.keys())
116
117def children_count(co, handle, point, txn):
118    return _children_count(co, handle, point, handle_name_at_point, txn)
119
120def parent_loop_check(co, handle, point, txn):
121    hseen = {}
122    while handle != roothandle:
123        if handle in hseen:
124            return handle
125        hseen[handle] = 1
126        phandle = handle_name_at_point(co, handle, point, txn)['parent']
127        if phandle is None:
128            return handle
129        handle = phandle
130    return None
131
132def is_ancestor(co, ancestor, point, txn):
133    if point is None:
134        return 0
135    return _is_ancestor(co, ancestor, [point], txn)
136
137def _is_ancestor(co, ancestor, points, txn):
138    #ainfo = bdecode(co.branchmapdb.get(ancestor, txn=txn))
139    ainfo = db_get(co, co.branchmapdb, ancestor, txn)
140    points = points[:]
141    state = {}
142
143    while len(points):
144        pnext = points.pop()
145        if pnext == ancestor:
146            return 1
147        # if it's in state, then we've already walked it
148        if pnext in state:
149            continue
150        state[pnext] = 1
151        #pinfo = bdecode(co.branchmapdb.get(pnext, txn=txn))
152        pinfo = db_get(co, co.branchmapdb, pnext, txn)
153        if pinfo['generation'] <= ainfo['generation']:
154            continue
155        ps = pinfo['precursors'][:]
156        ps.reverse()
157        points.extend(ps)
158
159    return 0
160
161def read_diff(co, handle, point, txn):
162    hinfo = bdecode(co.contents.dagdb.get(handle + point, txn=txn))
163    hfile = open(path.join(co.cpath, binascii.hexlify(handle)), 'rb')
164    #hfile = open(path.join(co.cpath, 'diffs'), 'rb')
165    diff = _read_diff(hinfo, hfile)
166    hfile.close()
167    return diff
168
169def _read_diff(index, hfile):
170    if 'handle' not in index:
171        return None
172    try:
173        hfile.seek(index['handle']['offset'])
174    except IOError:
175        print(index)
176        raise
177    return hfile.read(index['handle']['length'])
178
179def write_diff(co, handle, diff, txn):
180    cdagdb = co.contents.dagdb
181    try:
182        fend = struct.unpack('<I', cdagdb.get(handle, txn=txn))[0]
183        hfile = open(path.join(co.cpath, binascii.hexlify(handle)), 'r+b')
184        #fend = struct.unpack('<I', cdagdb.get('diffend', txn=txn))[0]
185        #hfile = open(path.join(co.cpath, 'diffs'), 'r+b')
186    except TypeError:
187        fend = 0
188        hfile = open(path.join(co.cpath, binascii.hexlify(handle)), 'wb')
189        #hfile = open(path.join(co.cpath, 'diffs'), 'wb')
190
191    hfile.seek(fend)
192    hfile.write(diff)
193    hfile.close()
194    index = {'offset': fend, 'length': len(diff)}
195    fend += index['length']
196    cdagdb.put(handle, struct.pack('<I', fend), txn=txn)
197    #cdagdb.put('diffend', struct.pack('<I', fend), txn=txn)
198    return index
199
200# This should be merged with write_diff()
201def write_index(co, point, handle, index, txn):
202    cdagdb = co.contents.dagdb
203    try:
204        old_index = bdecode(cdagdb.get(handle + point, txn=txn))
205        old_index['handle'] = index
206    except (db.DBNotFoundError, TypeError):
207        old_index = {'handle': index}
208    cdagdb.put(handle + point, bencode(old_index), txn=txn)
209
210class WriteDiff(object):
211    def __init__(self, co, handle, txn):
212        self.co = co
213        self.handle = handle
214        self.txn = txn
215        self.indices = []
216
217        cdagdb = co.contents.dagdb
218        fname = path.join(self.co.cpath, binascii.hexlify(handle))
219        #fname = path.join(self.co.cpath, 'diffs')
220        try:
221            self.fend = struct.unpack('<I', cdagdb.get(handle, txn=txn))[0]
222            #self.fend = struct.unpack('<I', cdagdb.get('diffend', txn=txn))[0]
223            self.hfile = open(fname, 'r+b')
224        except (db.DBNotFoundError, TypeError):
225            self.fend = 0
226            self.hfile = open(fname, 'wb')
227        self.hfile.seek(self.fend)
228        return
229
230    def write(self, diff, point):
231        self.hfile.write(diff)
232        self.indices.append(({'offset': self.fend, 'length': len(diff)}, point))
233        self.fend += len(diff)
234        return
235
236    def close(self):
237        self.hfile.close()
238
239        # update where to write next time
240        cdagdb = self.co.contents.dagdb
241        cdagdb.put(self.handle, struct.pack('<I', self.fend), txn=self.txn)
242        #cdagdb.put('diffend', struct.pack('<I', self.fend), txn=self.txn)
243
244        # write out the indices
245        for index, point in self.indices:
246            try:
247                old_index = bdecode(cdagdb.get(self.handle + point, txn=self.txn))
248                old_index['handle'] = index
249            except (db.DBNotFoundError, TypeError):
250                old_index = {'handle': index}
251            cdagdb.put(self.handle + point, bencode(old_index), txn=self.txn)
252        return
253
254def write_changeset(co, point, cset, txn):
255    co.lcrepo.put(point, cset, txn=txn)
256
257def sync_history(co, point, txn, cache=dict()):
258    named, modified, manifest = [], [], {}
259
260    sync_dfs = DFS(_history_deps, [co, txn, cache])
261    sync_dfs.search(point)
262    points = sync_dfs.result()
263
264    for npoint in points:
265        named, modified, unnamed, unmodified = \
266               _sync_history(co, npoint, txn, cache=cache)
267        unchecked = dict.fromkeys(unnamed)
268        for handle in named:
269            if handle in unchecked:
270                continue
271            _verify_manifest(co, handle, npoint, txn)
272        co.changesdb.put(binascii.hexlify(npoint), '', txn=txn)
273
274    return named, modified
275
276def _history_deps(node, args):
277    co, txn, cache = args[0], args[1], args[2]
278
279    # decode the changeset and populate the cache
280    cset = bdecode(co.lcrepo.get(node, txn=txn))
281    cache[node] = cset
282
283    # reversing the nodes gives better overall performance
284    nodes = []
285
286    for i in range(len(cset['precursors'])-1, -1, -1):
287        pre_node = cset['precursors'][i]
288
289        # don't sync it if we handled it in a previous import
290        if co.changesdb.has_key(binascii.hexlify(pre_node), txn):
291            continue
292        nodes.append(pre_node)
293
294    return nodes
295
296def _sync_history(co, point, txn, cache=dict()):
297    pinfo = cache[point]
298
299    # see if we can extend an existing branch
300    pre, prebminfo = None, None
301    generations, pre_important = [], []
302    bminfo = {'precursors': pinfo['precursors']}
303    for pre in bminfo['precursors']:
304        prebminfo = db_get(co, co.branchmapdb, pre, txn)
305        generations.append(prebminfo['generation'])
306
307        if 'branch' in bminfo:
308            continue
309
310        binfo = db_get(co, co.branchdb, prebminfo['branch'], txn)
311        if prebminfo['branchnum'] == binfo['last']:
312            bminfo['branch'] = prebminfo['branch']
313            bminfo['branchnum'] = prebminfo['branchnum'] + 1
314            binfo['last'] += 1
315            db_put(co, co.branchdb, bminfo['branch'], binfo, txn)
316
317            pre_important.append(pre)
318
319    # generation == 'distance to root node', the exception is for the root
320    try:
321        bminfo['generation'] = max(generations) + 1
322    except ValueError:
323        bminfo['generation'] = 0
324
325    # if we couldn't extend a branch, start a new one
326    if 'branch' not in bminfo:
327        bminfo['branch'] = bdecode(co.linforepo.get('branchmax', txn=txn)) + 1
328        co.linforepo.put('branchmax', bencode(bminfo['branch']), txn=txn)
329        bminfo['branchnum'] = 0
330
331        try:
332            # using the last precursor for this did the best empirically,
333            # beating out both first precursor and largest branch number.
334            binfo = {'last': 0,
335                     'parent': prebminfo['branch'],
336                     'parentnum': prebminfo['branchnum']}
337            pre_important.append(pre)
338
339        except TypeError:
340            # special stuff for the rootnode
341            assert bminfo['branch'] == 1
342            binfo = {'last': 0}
343
344        db_put(co, co.branchdb, bminfo['branch'], binfo, txn)
345
346    db_put(co, co.branchmapdb, point, bminfo, txn)
347
348    # put new files into staticdb
349    for (handle, value) in list(pinfo['handles'].items()):
350        if 'add' in value:
351            validate_handle(handle, pinfo['precursors'], value)
352            db_put(co, co.staticdb, handle, {'type': value['add']['type']}, txn)
353
354    # figure out which files were modified here and hand off to helpers
355    named, modified, added, deleted = \
356           handles_in_branch(co, pre_important, [point], txn, cache=cache)
357
358    named = damerge(named, added, deleted)
359    modified = damerge(modified, added, deleted)
360
361    # function with side effects, modifies named and modified
362    pinfo['point'] = point
363    unnamed    = _update_mini_dag(co, co.names,
364                                  _update_helper_name, named,
365                                  pinfo, txn)
366    unmodified = _update_mini_dag(co, co.contents,
367                                  _update_helper_content, modified,
368                                  pinfo, txn)
369
370    return (named, modified, unnamed, unmodified)
371
372def _verify_manifest(co, handle, point, txn):
373    state = _handle_name_at_point(co, handle, point, txn)
374    co.name_cache = {}
375
376    if state['name'] == '' and handle != roothandle:
377        raise HistoryError('illegal name')
378    if state['name'] == '.' or state['name'] == '..':
379        raise HistoryError('illegal name')
380    if state['name'] == '.cdv':
381        raise HistoryError('illegal name')
382
383    if 'delete' in state:
384        if len(children_count(co, handle, point, txn)):
385            raise HistoryError('non-empty directory can\'t be deleted')
386        return state
387
388    staticinfo = db_get(co, co.staticdb, handle, txn)
389    if staticinfo['type'] == 'dir':
390        try:
391            if parent_loop_check(co, state['parent'], point, txn):
392                raise HistoryError('parent loop')
393        except KeyError:
394            pass
395
396    try:
397        #parentinfo = bdecode(co.staticdb.get(state['parent'], txn=txn))
398        parentinfo = db_get(co, co.staticdb, state['parent'], txn)
399        if parentinfo['type'] != 'dir':
400            raise HistoryError('parent not a directory')
401
402        parentstate = handle_name_at_point(co, state['parent'], point, txn)
403        if parentstate is None:
404            raise HistoryError('parent not in repository')
405        if 'delete' in parentstate:
406            raise HistoryError('file committed with deleted parent')
407        if len(name_use_count(co, state, point, txn)) != 1:
408            raise HistoryError('name already in use')
409    except KeyError:
410        if handle != roothandle:
411            raise
412
413    return
414
415def validate_handle(handle, precursors, hinfo):
416    encinfo = bencode({'precursors': precursors, 'handle': hinfo})
417    if sha(encinfo).digest() != handle:
418        raise HistoryError('bad identifier')
419
420def pretty_print_big_dag(co, heads):
421    print('digraph {')
422
423    points = heads[:]
424    cache = {}
425    while len(points):
426        point = points.pop()
427        if point in cache:
428            continue
429        cache[point] = 1
430
431        info = bdecode(co.lcrepo.get(point))
432        sid = short_id(co, point)
433
434        color = "orange"
435        style = "dashed"
436        if clean_merge_point(info) or point == rootnode:
437            color = "lightblue"
438            style = "solid"
439
440        label = sid
441        if point == rootnode:
442            label = "root"
443
444        print('c_%s [label="%s",style=filled,color=%s]' % (sid, label, color))
445
446        for pre in info['precursors']:
447            print('c_%s -> c_%s [style=%s]' % (short_id(co, pre), sid, style))
448            style = "dashed"
449
450        points.extend([point for point in info['precursors']])
451
452    print('}')
453
454def pretty_print_dag(co, handle, heads):
455    print('digraph {')
456
457    points = []
458    for point in heads:
459        head = handle_last_modified(co, co.contents, handle, point, None)
460        if head is not None:
461            points.append(head)
462
463    cdagdb = co.contents.dagdb
464    cache = {}
465    while len(points):
466        point = points.pop()
467        if point in cache:
468            continue
469        cache[point] = 1
470
471        sid = short_id(co, point)
472        print('c_%s [label="%s"]' % (sid, sid))
473
474        info = bdecode(cdagdb.get(handle + point))
475        for pre, foo in info['precursors']:
476            print('c_%s -> c_%s' % (sid, short_id(co, pre)))
477
478        points.extend([point for point, index in info['precursors']])
479
480    print('}')
481
482def _update_mini_dag(co, changedbs, helper, handles, cset, txn):
483    indexdb = changedbs.indexdb
484    dagdb   = changedbs.dagdb
485
486    pres = cset['precursors']
487    point = cset['point']
488    #bminfo = bdecode(co.branchmapdb.get(point, txn=txn))
489    bminfo = db_get(co, co.branchmapdb, point, txn)
490    bnum = struct.pack('>II', bminfo['branch'], bminfo['branchnum'])
491
492    untouched = []
493
494    for handle in handles:
495        precursors = simplify_precursors(co, handle, changedbs, pres, txn)[0]
496
497        mdinfo = {'handle': {}}
498
499        # there's some broken history, need to work around it for now
500        # deleted files are deleted, regardless of later edits
501        deleted = None
502        #if len(precursors) > 1:
503        if True:
504            # only deletes can be implicitly merged
505            all_deleted = True
506            for pre in precursors:
507                phinfo = bdecode(dagdb.get(handle + pre[0], txn=txn))
508                if 'delete' in phinfo['handle']:
509                    deleted = phinfo
510                else:
511                    all_deleted = False
512
513            if all_deleted:
514                if len(precursors) > 1:
515                    # affects finding when the handle was modified
516                    untouched.append(handle)
517                    continue
518
519        if deleted is not None:
520            mdinfo['handle'] = deleted['handle']
521
522        elif handle in cset['handles']:
523            mdinfo['handle'] = helper(co, handle, point, precursors,
524                                      cset['handles'][handle], txn)
525
526        if mdinfo['handle'] == {}:
527            if deleted is None:
528                if len(precursors) > 1:
529                    raise HistoryError('can not automatically merge changes')
530
531            del mdinfo['handle']
532
533        mdinfo['precursors'] = precursors
534        if precursors == []:
535            assert 'add' in cset['handles'][handle]
536
537        dagdb.put(handle + point, bencode(mdinfo), txn=txn)
538        indexdb.put(handle + bnum, point, txn=txn)
539
540    return untouched
541
542def simplify_precursors(co, handle, changedbs, pres, txn):
543    # map big DAG precursors to little DAG
544    dagdb = changedbs.dagdb
545    precursors, indices = [], []
546    for i in range(len(pres)):
547        last = handle_last_modified(co, changedbs, handle, pres[i], txn)
548        if last is None:
549            continue
550
551        precursors.append(last)
552        indices.append(i)
553
554    # second pass to eliminate precursors which are ancestors of others
555    retval = []
556    for i in range(len(precursors)):
557        pre = precursors.pop(0)
558        index = indices.pop(0)
559        if _is_ancestor(co, pre, precursors, txn):
560            continue
561        precursors.append(pre)
562        retval.append((pre, index))
563
564    return retval, len(pres)
565
566def _update_helper_content(co, handle, point, precursors, hinfo, txn):
567    oinfo = {}
568    if 'hash' in hinfo:
569        if co.contents.dagdb.has_key(handle + point, txn):
570            dinfo = bdecode(co.contents.dagdb.get(handle + point, txn=txn))
571            oinfo['offset'] = dinfo['handle']['offset']
572            oinfo['length'] = dinfo['handle']['length']
573        else:
574            # XXX: ugly in general
575            oinfo['offset'] = -1
576    if 'add' in hinfo:
577        oinfo['add'] = 1
578    elif 'delete' in hinfo:
579        oinfo['delete'] = 1
580    return oinfo
581
582def _update_helper_name(co, handle, point, precursors, hinfo, txn):
583    oinfo = {}
584    if 'name' in hinfo:
585        # XXX: work around some broken history, remove this later
586        # check to see if the file was already deleted.
587        for pre in precursors:
588            phinfo = bdecode(co.names.dagdb.get(handle + pre[0], txn=txn))
589            if 'delete' in phinfo['handle']:
590                oinfo = phinfo['handle']
591                return oinfo
592
593        oinfo['name'] = hinfo['name']
594        try:
595            oinfo['parent'] = hinfo['parent']
596            co.allnamesdb.put(hinfo['parent'] + hinfo['name'],
597                              handle, flags=db.DB_NODUPDATA, txn=txn)
598        except KeyError:
599            assert handle == roothandle
600            assert 'add' in hinfo
601        except db.DBKeyExistError:
602            pass
603
604    if 'add' in hinfo:
605        assert len(precursors) == 0
606        oinfo['add'] = 1
607    elif 'delete' in hinfo:
608        # part of making lookups faster
609        phinfo = bdecode(co.names.dagdb.get(handle + precursors[0][0], txn=txn))
610        oinfo = phinfo['handle']
611        oinfo['delete'] = 1
612    else:
613        # something to make name lookups faster
614        for pre in precursors:
615            phinfo = bdecode(co.names.dagdb.get(handle + pre[0], txn=txn))
616            if 'delete' in phinfo:
617                oinfo = phinfo['handle']
618                break
619    if oinfo != {}:
620        assert 'name' in oinfo or 'delete' in oinfo
621    return oinfo
622
623def changes_in_branch(co, lpoints, bpoints, txn, cache=None):
624    points = bpoints[:]
625    seen, changes = {}, []
626    while len(points):
627        pnext = points.pop()
628        if pnext in seen:
629            continue
630        seen[pnext] = 1
631        if _is_ancestor(co, pnext, lpoints, txn):
632            continue
633        if cache:
634            if pnext in cache:
635                pinfo = cache[pnext]
636            else:
637                pinfo = bdecode(co.lcrepo.get(pnext, txn=txn))
638                cache[pnext] = pinfo
639        else:
640            pinfo = bdecode(co.lcrepo.get(pnext, txn=txn))
641
642        points.extend(pinfo['precursors'])
643
644        changes.append(pnext)
645
646    return changes
647
648def handles_in_branch(co, lpoints, bpoints, txn, cache=None):
649    points = bpoints[:]
650    seen = {}
651    named, modified, added, deleted = {}, {}, {}, {}
652    while len(points):
653        pnext = points.pop()
654        if pnext in seen:
655            continue
656        seen[pnext] = 1
657        if _is_ancestor(co, pnext, lpoints, txn):
658            continue
659        if cache:
660            if pnext in cache:
661                pinfo = cache[pnext]
662            else:
663                pinfo = bdecode(co.lcrepo.get(pnext, txn=txn))
664                cache[pnext] = pinfo
665        else:
666            pinfo = bdecode(co.lcrepo.get(pnext, txn=txn))
667        for handle, hinfo in list(pinfo['handles'].items()):
668            if 'add' in hinfo:
669                added[handle] = 1
670            if 'name' in hinfo:
671                named[handle] = 1
672            if 'hash' in hinfo:
673                modified[handle] = 1
674            if 'delete' in hinfo:
675                deleted[handle] = 1
676
677        points.extend(pinfo['precursors'])
678
679    return (list(named.keys()), list(modified.keys()), list(added.keys()), list(deleted.keys()))
680
681def handle_last_modified(co, changedbs, handle, change, txn):
682    retval = _handle_last_modified(co, changedbs, handle, change, txn)
683    if retval is None:
684        return retval
685
686    # optimization step. we may have gotten an artifact of the indexing
687    # structure. because of how the mini-dags are constructed, this can be
688    # corrected by following a single precursor.
689    pinfo = bdecode(changedbs.dagdb.get(handle + retval, txn=txn))
690    if 'handle' not in pinfo and len(pinfo['precursors']) == 1:
691        retval = _handle_last_modified(co, changedbs, handle,
692                                       pinfo['precursors'][0][0], txn)
693
694    return retval
695
696def _handle_last_modified(co, changedbs, handle, change, txn):
697    indexdb = changedbs.indexdb
698    dagdb   = changedbs.dagdb
699
700    if dagdb.has_key(handle + change, txn):
701        return change
702
703    #hinfo = bdecode(co.branchmapdb.get(change, txn=txn))
704    hinfo = db_get(co, co.branchmapdb, change, txn)
705    bbranch, bnum = int(hinfo['branch']), hinfo['branchnum']
706    retval = None
707    cursor = indexdb.cursor(txn=txn)
708    while True:
709        branchpoint = struct.pack('>20sII', handle, bbranch, bnum)
710        try:
711            foo = cursor.set_range(branchpoint)
712        except db.DBNotFoundError:
713            foo = None
714        if foo is None:
715            foo = cursor.last()
716            if foo is None:
717                break
718            key, value = foo
719        else:
720            key, value = foo
721            if key != branchpoint:
722                try:
723                    foo = cursor.prev_nodup()
724                except db.DBNotFound:
725                    foo = None
726                if foo is None:
727                    break
728                key, value = foo
729        rhandle, rbranch, rnum = struct.unpack('>20sII', key)
730        if rhandle == handle and rbranch == bbranch:
731            retval = value
732            break
733        #pinfo = bdecode(co.branchdb.get(bbranch, txn=txn))
734        pinfo = db_get(co, co.branchdb, bbranch, txn)
735        try:
736            bbranch, bnum = int(pinfo['parent']), pinfo['parentnum']
737        except KeyError:
738            #_print_indexdb(co, indexdb, handle, txn)
739            break
740    cursor.close()
741
742    return retval
743
744def _print_indexdb(co, indexdb, handle, txn):
745    print('indexdb')
746    cursor = indexdb.cursor(txn=txn)
747    foo = cursor.set_range(handle)
748    while foo != None:
749        key, value = foo
750        nhandle, branch, num = struct.unpack('>20sII', key)
751        if handle != nhandle:
752            break
753        print("%d, %d" % (branch, num))
754        foo = next(cursor)
755    cursor.close()
756
757def handle_name_at_point(co, handle, point, txn, lookup=True):
758    change = point
759    if lookup:
760        change = handle_last_modified(co, co.names, handle, point, txn)
761        if change is None:
762            return None
763    blinfo = co.names.dagdb.get(handle + change, txn=txn)
764    linfo  = bdecode(blinfo)
765    return linfo['handle']
766
767def __handle_name_at_point(co, handle, point, txn, docache=True):
768    #key = handle + point
769    #if co.name_cache.has_key(key):
770    #    return co.name_cache[key]
771
772    change = handle_last_modified(co, co.names, handle, point, txn)
773    if change is None:
774        return None
775
776    return _handle_name_at_point(co, handle, change, txn, docache=docache)
777
778def _handle_name_from_precursors(precursors, resolution, point):
779    if 'delete' in resolution:
780        resolution.update(precursors[0])
781        return
782
783    resolution['rename point'] = []
784    for pre in precursors:
785        if 'delete' in pre:
786            resolution.update(pre)
787            return
788        if     pre['name'] == resolution['name'] and \
789               pre['parent'] == resolution['parent']:
790            assert list == type(pre['rename point'])
791            resolution['rename point'].extend(pre['rename point'])
792
793    if resolution['rename point'] == []:
794        resolution['rename point'] = [point]
795        return
796
797    # figure out the whether we should assign a new rename point. this handles
798    # 2 cases:
799    # 1) ambiguous merge picking the line points of an ancestor
800    # 2) ancestors are A and B where B should win, but user reassigned to A
801    for pre in precursors:
802        outcome, rename_point = rename_conflict_check(resolution, pre)
803        if outcome != 'local':
804            resolution['rename point'] = [point]
805            break
806
807    return
808
809def _deleted_in_precursors(precursors):
810    deleted = True
811    for pre in precursors:
812        if 'delete' not in pre:
813            deleted = False
814            break
815    return deleted
816
817def _handle_name_at_point(co, handle, point, txn, docache=False):
818    cset = bdecode(co.names.dagdb.get(handle + point, txn=txn))
819
820    precursors, points = [], [point]
821    for pre, index in cset['precursors']:
822        pre_name = _handle_name_at_point(co, handle, pre, txn, docache=docache)
823        if pre_name is None:
824            continue
825        points = dmerge(points, pre_name['points'])
826        precursors.append(pre_name)
827
828    state = {}
829    if 'handle' not in cset:
830        if len(cset['precursors']) != 1:
831            # we don't require deletes to be explicitly merged
832            if not _deleted_in_precursors(precursors):
833                raise HistoryError('implicit name merges not permitted')
834        state = precursors[0]
835    elif 'delete' in cset['handle']:
836        state['delete'] = 1
837    else:
838        state['name'] = cset['handle']['name']
839        try:
840            state['parent'] = cset['handle']['parent']
841        except KeyError:
842            assert handle == roothandle
843            assert 'add' in cset['handle']
844
845    state['points'] = points
846    _handle_name_from_precursors(precursors, state, point)
847
848    if not docache:
849        return state
850
851    co.name_cache[handle + point] = state
852
853    return state
854
855def fullpath_at_point(co, handle, point, txn=None):
856    name = None
857    while handle != roothandle:
858        pinfo = handle_name_at_point(co, handle, point, txn)
859        if pinfo is None:
860            return None
861        if name is None:
862            name = pinfo['name']
863        else:
864            name = path.join(pinfo['name'], name)
865        handle = pinfo['parent']
866    return name
867
868def _mini_dag_refcount(co, handle, point, txn, cache=None, info_cache=None):
869    assert info_cache is not None
870    if cache is None:
871        cache = {}
872    points = [point]
873    while len(points):
874        point = points.pop()
875        if point in cache:
876            cache[point]['refcount'] += 1
877            continue
878        cache[point] = {'refcount': 1}
879
880        pinfo = bdecode(co.contents.dagdb.get(handle + point, txn=txn))
881        info_cache[point] = pinfo
882
883        for p, i in pinfo['precursors']:
884            points.append(p)
885    return cache
886
887def _merge_check_deps(node, args):
888    co, handle, txn, hcache = args[0], args[1], args[2], args[3]
889    hinfo = bdecode(co.contents.dagdb.get(handle + node, txn=txn))
890    hcache[node] = hinfo
891
892    return [p[0] for p in hinfo['precursors']]
893
894def handle_merge_check(co, handle, point, txn):
895    change = handle_last_modified(co, co.contents, handle, point, txn)
896    if change is None:
897        return None
898
899    hcache = {}
900    cDFS = DFS(_merge_check_deps, [co, handle, txn, hcache])
901    cDFS.search(change)
902    ordering = cDFS.result()
903
904    for point in ordering:
905        hinfo = hcache[point]
906
907        if 'handle' not in hinfo and len(hinfo['precursors']) > 1:
908            raise HistoryError('can not automatically merge changes')
909
910    return
911
912def _content_deps(node, args):
913    hcache = args[0]
914    return [p[0] for p in hcache[node]['precursors']]
915
916def handle_contents_at_point(co, handle, point, txn, dcache=None, replayfunc=replay):
917    if dcache is None:
918        dcache = {}
919    #staticinfo = bdecode(co.staticdb.get(handle, txn=txn))
920    staticinfo = db_get(co, co.staticdb, handle, txn)
921    if staticinfo['type'] != 'file':
922        raise_(ValueError, 'Expected type \"file\", got type \"%s\"' % \
923              (staticinfo['type'],))
924
925    change = handle_last_modified(co, co.contents, handle, point, txn)
926    if change is None:
927        return None
928
929    hcache = {}
930    cache = _mini_dag_refcount(co, handle, change, txn, info_cache=hcache)
931    hfile = open(path.join(co.cpath, binascii.hexlify(handle)), 'rb')
932    #hfile = open(path.join(co.cpath, 'diffs'), 'rb')
933
934    cDFS = DFS(_content_deps, [hcache])
935    cDFS.search(change)
936    ordering = cDFS.result()
937
938    for point in ordering:
939        hinfo = hcache[point]
940
941        if 'delete' in hinfo['handle']:
942            # Pick contents of an ancestor, doesn't really matter
943            cache[point]['info'] = cache[hinfo['precursors'][0][0]].copy()
944            cache[point]['info']['delete'] = hinfo['handle']['delete']
945
946        # put together the precursor list and decrement refcounts
947        precursors = []
948        for pre, foo in hinfo['precursors']:
949            precursors.append(cache[pre]['info'])
950
951            cache[pre]['refcount'] -= 1
952            if cache[pre]['refcount'] == 0:
953                del cache[pre]
954
955        if 'delete' in hinfo['handle']:
956            # This has to be done after decrementing refcounts, whereas the
957            # content setting has to be done before.
958            continue
959
960        # read the diff
961        if point in dcache:
962            diff = dcache[point]
963        else:
964            diff = _read_diff(hinfo, hfile)
965
966        if diff is None:
967            if len(hinfo['precursors']) > 1:
968                raise HistoryError('can not automatically merge changes')
969            raise HistoryError('change with no diff')
970
971        diff = bdecode(zlib.decompress(diff))
972
973        # finally, get the contents
974        cache[point]['info'] = _handle_contents_at_point(point, hinfo,
975                                                         precursors, diff,
976                                                         replayfunc=replayfunc)
977
978    hfile.close()
979
980    cache[change]['info']['type'] = staticinfo['type']
981    return cache[change]['info']
982
983def _handle_contents_at_point(point, hinfo, precursors, diff, replayfunc=replay):
984    state = {}
985
986    matches = []
987    for pre, index in hinfo['precursors']:
988        matches.append(diff['matches'][index])
989
990    if 'add' in diff:
991        if precursors != []:
992            raise HistoryError('handle already exists')
993    elif precursors == []:
994        raise HistoryError('can not modify non-existent file')
995
996    if 'delete' in diff:
997        state['delete'] = diff['delete']
998
999    if 'delete' not in state:
1000        fpre = []
1001        for pre in precursors:
1002            fpre.append((pre['lines'], pre['line points'], pre['points']))
1003
1004        try:
1005            lines, line_points, points = replayfunc(fpre, matches,
1006                                                    diff['newlines'], point)
1007        except MergeError as msg:
1008            raise_(HistoryError, 'merge error: ' + str(msg))
1009        except KeyError:
1010            raise HistoryError('malformed change')
1011
1012        points.append(point)
1013        state['lines'] = lines
1014        state['line points'] = line_points
1015
1016    state['points'] = points
1017    return state
1018
1019def print_file_with_points(pre):
1020    def _print_points(line_points):
1021        ps = []
1022        for line_point in line_points:
1023            ps.append(binascii.hexlify(line_point))
1024        return ', '.join(ps)
1025
1026    lines, line_points, points = pre
1027    out = [_print_points(line_points[0])]
1028    for i in range(len(lines)):
1029        out.append(lines[i])
1030        out.append(_print_points(line_points[i+1]))
1031    return '\n'.join(out)
1032
1033from .merge import _find_conflict
1034
1035def print_conflict(co, fpre):
1036    p1, p2 = fpre[0], fpre[1]
1037    olines, oline_points = _find_conflict(fpre[0][0], fpre[0][1], fpre[0][2],
1038                                          fpre[1][0], fpre[1][1], fpre[1][2])[:2]
1039
1040    ls = []
1041    offset = [0, 0]
1042    for i in range(len(olines)):
1043        l = olines[i]
1044
1045        if type(l) is str:
1046            offset[0] += 1
1047            offset[1] += 1
1048            continue
1049
1050        print('@@ -%d,%d +%d,%d @@' % (offset[0], len(l[0]), offset[0], len(l[1])))
1051
1052        offset[0] += len(l[0])
1053        offset[1] += len(l[1])
1054
1055        lp = oline_points[i]
1056        ls.append('<<<<<<< local')
1057
1058        ps = ', '.join([short_id(co, p) for p in lp[0][0]])
1059        ls.append(ps)
1060        for j in range(len(l[0])):
1061            ls.append(l[0][j])
1062            ps = ', '.join([short_id(co, p) for p in lp[0][j+1]])
1063            ls.append(ps)
1064
1065        ls.append('=======')
1066
1067        ps = ', '.join([short_id(co, p) for p in lp[1][0]])
1068        ls.append(ps)
1069        for j in range(len(l[1])):
1070            ls.append(l[1][j])
1071            ps = ', '.join([short_id(co, p) for p in lp[1][j+1]])
1072            ls.append(ps)
1073
1074        ls.append('>>>>>>> remote')
1075
1076    return '\n'.join(ls)
1077
1078def rebuild_from_points(co, points, txn):
1079    co.changesdb.truncate(txn)
1080    co.branchdb.truncate(txn)
1081    co.branchmapdb.truncate(txn)
1082    co.names.indexdb.truncate(txn)
1083    co.names.dagdb.truncate(txn)
1084    co.contents.indexdb.truncate(txn)
1085    # we don't truncate the cdagdb because it contains the offsets and lengths
1086    # for the diffs in the files, which we can't recreate. the sync below will
1087    # read those parameters out and rewrite the cdagdb, anyway.
1088    co.linforepo.put('branchmax', bencode(0), txn=txn)
1089
1090    cdagdb = co.contents.dagdb
1091    for key, value in cdagdb.items(txn):
1092        if len(key) != 40:
1093            continue
1094        if 'handle' not in bdecode(value):
1095            cdagdb.delete(key, txn=txn)
1096
1097    for point in points:
1098        sync_history(co, point, txn)
1099
1100def clean_merge_point(info):
1101    if info['handles'] != {}:
1102        return 0
1103    if len(info['precursors']) != 2:
1104        return 0
1105    if 'comment' in info:
1106        return 0
1107    return 1
1108
1109def short_id(co, point):
1110    apoint = binascii.hexlify(point)
1111    length = 3
1112    key = apoint[:length]
1113    cursor = co.changesdb.cursor()
1114    while key.startswith(apoint[:length]) and length < len(apoint):
1115        length += 1
1116        try:
1117            key, value = cursor.set_range(apoint[:length])
1118        except (db.DBNotFoundError, TypeError):
1119            break
1120        if key != apoint:
1121            continue
1122        foo = next(cursor)
1123        if foo is None:
1124            break
1125        key, value = foo
1126    cursor.close()
1127    return apoint[:length]
1128
1129class ChangeNotKnown(Exception): pass
1130
1131class ChangeNotUnique(Exception): pass
1132
1133class ChangeBadRepository(Exception): pass
1134
1135def long_id(co, point):
1136    if point.startswith('cdv://'):
1137        key = repo_head(co, tuple_to_server(server_to_tuple(point)))
1138        if key is None:
1139            raise_(ChangeBadRepository, point)
1140        return key
1141
1142    cursor = co.changesdb.cursor()
1143    try:
1144        key, value = cursor.set_range(point)
1145    except (db.DBNotFoundError, TypeError):
1146        cursor.close()
1147        raise_(ChangeNotKnown, point)
1148    if not key.startswith(point):
1149        cursor.close()
1150        raise_(ChangeNotKnown, point)
1151    try:
1152        key2, value = next(cursor)
1153    except (db.DBNotFoundError, TypeError):
1154        cursor.close()
1155        return binascii.unhexlify(key)
1156    if key2.startswith(point):
1157        keys = [key]
1158        while key2.startswith(point):
1159            keys.append(key2)
1160            try:
1161                key2, value = next(cursor)
1162            except (db.DBNotFoundError, TypeError):
1163                break
1164        cursor.close()
1165        raise ChangeNotUnique(point, keys)
1166    cursor.close()
1167    return binascii.unhexlify(key)
1168
1169def repo_head(co, repo):
1170    if repo is None:
1171        return None
1172    repo = tuple_to_server(server_to_tuple(repo))
1173    return co.linforepo.get(repo)
1174
1175def server_to_tuple(server_string):
1176    if server_string.startswith('cdv://'):
1177        server_string = server_string[6:]
1178    temp = server_string.split('/', 1)
1179
1180    if len(temp) != 2 or temp[1] == '':
1181        repo = None
1182    else:
1183        repo = temp[1]
1184        if repo[-1] == '/':
1185            repo = repo[:-1]
1186
1187    temp  = temp[0].split(':', 1)
1188    if len(temp) == 1:
1189        port = 6601
1190    else:
1191        try:
1192            port = int(temp[1])
1193        except ValueError:
1194            return None
1195    server_string = temp[0]
1196    return (temp[0], port, repo)
1197
1198def tuple_to_server(tuple):
1199    return 'cdv://%s:%d/%s' % tuple
1200
1201def print_change(co, change, changeset):
1202    escape = saxutils.escape
1203
1204    output = []
1205    output.append("<change>")
1206
1207    output.append("<changenumber>" + binascii.hexlify(change) + "</changenumber>")
1208    output.append("<short-changenumber>" + short_id(co, change) + "</short-changenumber>")
1209    output.append("<user>" + escape(changeset['user']) + "</user>")
1210    try:
1211        output.append("<comment>" + escape(changeset['comment']) + "</comment>")
1212    except KeyError:
1213        pass
1214    output.append("<date>" + str(changeset['time']) + "</date>")
1215    output.append("<pretty-date>" + strftime('%a %b %d %H:%M:%S %Y %Z', localtime(changeset['time'])) + "</pretty-date>")
1216
1217    adds, deletes, renames, mods = {}, {}, {}, {}
1218    for handle, value in list(changeset['handles'].items()):
1219        if 'add' in value:
1220            adds[handle] = value['add']
1221        else:
1222            if 'delete' in value:
1223                deletes[handle] = 1
1224            if 'name' in value:
1225                renames[handle] = 1
1226            if 'hash' in value:
1227                mods[handle] = 1
1228
1229    output.append("<added-files>")
1230    for handle, info in list(adds.items()):
1231        output.append("<file>")
1232        output.append("<name>" + escape(fullpath_at_point(co, handle, change)) + "</name>")
1233        output.append("<type>" + info['type'] + "</type>")
1234        output.append("</file>")
1235    output.append("</added-files>")
1236
1237    output.append("<deleted-files>")
1238    for handle in list(deletes.keys()):
1239        output.append("<file>")
1240        output.append("<name>" + escape(fullpath_at_point(co, handle, change)) + "</name>")
1241        output.append("</file>")
1242    output.append("</deleted-files>")
1243
1244    output.append("<renamed-files>")
1245    for handle in list(renames.keys()):
1246        output.append("<file>")
1247        output.append("<name>" + escape(fullpath_at_point(co, handle, change)) + "</name>")
1248        output.append("</file>")
1249    output.append("</renamed-files>")
1250
1251    output.append("<modified-files>")
1252    for handle in list(mods.keys()):
1253        output.append("<file>")
1254        output.append("<name>" + escape(fullpath_at_point(co, handle, change)) + "</name>")
1255        output.append("</file>")
1256    output.append("</modified-files>")
1257
1258    output.append("</change>")
1259    return output
1260
1261def dump_changeinfo(co, change, repo=None):
1262    output = []
1263
1264    changeset = bdecode(co.lcrepo.get(change))
1265    if not clean_merge_point(changeset):
1266        raise ValueError
1267
1268    output.append("<root>")
1269    if repo:
1270        output.append("<repository>" + saxutils.escape(repo) + "</repository>")
1271    output.append("<changenumber>" + binascii.hexlify(change) + "</changenumber>")
1272    output.append("<short-changenumber>" + short_id(co, change) + "</short-changenumber>")
1273    output.append("<committer>" + saxutils.escape(changeset['user']) + "</committer>")
1274    output.append("<date>" + str(changeset['time']) + "</date>")
1275
1276    for change in changes_in_branch(co, [changeset['precursors'][0]],
1277                                    changeset['precursors'][1:], None):
1278        changeset = bdecode(co.lcrepo.get(change))
1279        if not clean_merge_point(changeset):
1280            output.extend(print_change(co, change, changeset))
1281
1282    output.append("</root>\n")
1283    return '\n'.join(output)
1284
1285def db_get(co, cdb, key, txn):
1286    try:
1287        cache = co.db_cache[db]
1288    except KeyError:
1289        cache = co.db_cache[db] = {}
1290    if key in cache:
1291        return cache[key]
1292    cache[key] = bdecode(cdb.get(key, txn=txn))
1293    #try:
1294    #    return cache[key]
1295    #except KeyError:
1296    #    cache[key] = bdecode(cdb.get(key, txn=txn))
1297    return cache[key]
1298
1299def db_put(co, cdb, key, value, txn):
1300    cdb.put(key, bencode(value), txn=txn)
1301    try:
1302        cache = co.db_cache[db]
1303    except KeyError:
1304        cache = co.db_cache[db] = {}
1305    cache[key] = value
1306
1307try:
1308    import psyco
1309    psyco.bind(_is_ancestor, 1)
1310    psyco.bind(handle_last_modified, 1)
1311except ImportError:
1312    pass
1313