annotate tests/test-pathencode.py @ 26631:e077ce385609

localrepo: restore dirstate to one before rollbacking if not parent-gone

'localrepository.rollback()' explicilty restores dirstate, only if at
least one of current parents of the working directory is removed at
rollbacking (a.k.a "parent-gone").

After DirstateTransactionPlan, 'dirstate.write()' will cause marking
'.hg/dirstate' as a file to be restored at rollbacking.

    https://mercurial.selenic.com/wiki/DirstateTransactionPlan

Then, 'transaction.rollback()' restores '.hg/dirstate' regardless of
parents of the working directory at that time, and this causes
unexpected dirstate changes if not "parent-gone" (e.g.  "hg update" to
another branch after "hg commit" or so, then "hg rollback").

To avoid such situation, this patch restores dirstate to one before
rollbacking if not "parent-gone".

  before:
    b1. restore dirstate explicitly, if "parent-gone"

  after:
    a1. save dirstate before actual rollbacking via dirstateguard
    a2. restore dirstate via 'transaction.rollback()'
    a3. if "parent-gone"
        - discard backup (a1)
        - restore dirstate from 'undo.dirstate'
    a4. otherwise, restore dirstate from backup (a1)

Even though restoring dirstate at (a3) after (a2) seems redundant,
this patch keeps this existing code path, because:

  - it isn't ensured that 'dirstate.write()' was invoked at least once
    while transaction running

    If not, '.hg/dirstate' isn't restored at (a2).

    In addition to it, rude 3rd party extension invoking
    'dirstate.write()' without 'repo' while transaction running (see
    subsequent patches for detail) may break consistency of a file
    backup-ed by transaction.

  - this patch mainly focuses on changes for DirstateTransactionPlan

    Restoring dirstate at (a3) itself should be cheaper enough than
    rollbacking itself. Redundancy will be removed in next step.

Newly added test is almost meaningless at this point. It will be used
to detect regression while implementing delayed dirstate write out.

# This is a randomized test that generates different pathnames every
# time it is invoked, and tests the encoding of those pathnames.
#
# It uses a simple probabilistic model to generate valid pathnames
# that have proven likely to expose bugs and divergent behavior in
# different encoding implementations.

from mercurial import store
import binascii, itertools, math, os, random, sys, time
import collections

if sys.version_info[:2] < (2, 6):
    sys.exit(0)

validchars = set(map(chr, range(0, 256)))
alphanum = range(ord('A'), ord('Z'))

for c in '\0/':
    validchars.remove(c)

winreserved = ('aux con prn nul'.split() +
               ['com%d' % i for i in xrange(1, 10)] +
               ['lpt%d' % i for i in xrange(1, 10)])

def casecombinations(names):
    '''Build all case-diddled combinations of names.'''

    combos = set()

    for r in names:
        for i in xrange(len(r) + 1):
            for c in itertools.combinations(xrange(len(r)), i):
                d = r
                for j in c:
                    d = ''.join((d[:j], d[j].upper(), d[j + 1:]))
                combos.add(d)
    return sorted(combos)

def buildprobtable(fp, cmd='hg manifest tip'):
    '''Construct and print a table of probabilities for path name
    components.  The numbers are percentages.'''

    counts = collections.defaultdict(lambda: 0)
    for line in os.popen(cmd).read().splitlines():
        if line[-2:] in ('.i', '.d'):
            line = line[:-2]
        if line.startswith('data/'):
            line = line[5:]
        for c in line:
            counts[c] += 1
    for c in '\r/\n':
        counts.pop(c, None)
    t = sum(counts.itervalues()) / 100.0
    fp.write('probtable = (')
    for i, (k, v) in enumerate(sorted(counts.iteritems(), key=lambda x: x[1],
                                      reverse=True)):
        if (i % 5) == 0:
            fp.write('\n    ')
        vt = v / t
        if vt < 0.0005:
            break
        fp.write('(%r, %.03f), ' % (k, vt))
    fp.write('\n    )\n')

# A table of character frequencies (as percentages), gleaned by
# looking at filelog names from a real-world, very large repo.

probtable = (
    ('t', 9.828), ('e', 9.042), ('s', 8.011), ('a', 6.801), ('i', 6.618),
    ('g', 5.053), ('r', 5.030), ('o', 4.887), ('p', 4.363), ('n', 4.258),
    ('l', 3.830), ('h', 3.693), ('_', 3.659), ('.', 3.377), ('m', 3.194),
    ('u', 2.364), ('d', 2.296), ('c', 2.163), ('b', 1.739), ('f', 1.625),
    ('6', 0.666), ('j', 0.610), ('y', 0.554), ('x', 0.487), ('w', 0.477),
    ('k', 0.476), ('v', 0.473), ('3', 0.336), ('1', 0.335), ('2', 0.326),
    ('4', 0.310), ('5', 0.305), ('9', 0.302), ('8', 0.300), ('7', 0.299),
    ('q', 0.298), ('0', 0.250), ('z', 0.223), ('-', 0.118), ('C', 0.095),
    ('T', 0.087), ('F', 0.085), ('B', 0.077), ('S', 0.076), ('P', 0.076),
    ('L', 0.059), ('A', 0.058), ('N', 0.051), ('D', 0.049), ('M', 0.046),
    ('E', 0.039), ('I', 0.035), ('R', 0.035), ('G', 0.028), ('U', 0.026),
    ('W', 0.025), ('O', 0.017), ('V', 0.015), ('H', 0.013), ('Q', 0.011),
    ('J', 0.007), ('K', 0.005), ('+', 0.004), ('X', 0.003), ('Y', 0.001),
    )

for c, _ in probtable:
    validchars.remove(c)
validchars = list(validchars)

def pickfrom(rng, table):
    c = 0
    r = rng.random() * sum(i[1] for i in table)
    for i, p in table:
        c += p
        if c >= r:
            return i

reservedcombos = casecombinations(winreserved)

# The first component of a name following a slash.

firsttable = (
    (lambda rng: pickfrom(rng, probtable), 90),
    (lambda rng: rng.choice(validchars), 5),
    (lambda rng: rng.choice(reservedcombos), 5),
    )

# Components of a name following the first.

resttable = firsttable[:-1]

# Special suffixes.

internalsuffixcombos = casecombinations('.hg .i .d'.split())

# The last component of a path, before a slash or at the end of a name.

lasttable = resttable + (
    (lambda rng: '', 95),
    (lambda rng: rng.choice(internalsuffixcombos), 5),
    )

def makepart(rng, k):
    '''Construct a part of a pathname, without slashes.'''

    p = pickfrom(rng, firsttable)(rng)
    l = len(p)
    ps = [p]
    maxl = rng.randint(1, k)
    while l < maxl:
        p = pickfrom(rng, resttable)(rng)
        l += len(p)
        ps.append(p)
    ps.append(pickfrom(rng, lasttable)(rng))
    return ''.join(ps)

def makepath(rng, j, k):
    '''Construct a complete pathname.'''

    return ('data/' + '/'.join(makepart(rng, k) for _ in xrange(j)) +
            rng.choice(['.d', '.i']))

def genpath(rng, count):
    '''Generate random pathnames with gradually increasing lengths.'''

    mink, maxk = 1, 4096
    def steps():
        for i in xrange(count):
            yield mink + int(round(math.sqrt((maxk - mink) * float(i) / count)))
    for k in steps():
        x = rng.randint(1, k)
        y = rng.randint(1, k)
        yield makepath(rng, x, y)

def runtests(rng, seed, count):
    nerrs = 0
    for p in genpath(rng, count):
        h = store._pathencode(p)    # uses C implementation, if available
        r = store._hybridencode(p, True) # reference implementation in Python
        if h != r:
            if nerrs == 0:
                print >> sys.stderr, 'seed:', hex(seed)[:-1]
            print >> sys.stderr, "\np: '%s'" % p.encode("string_escape")
            print >> sys.stderr, "h: '%s'" % h.encode("string_escape")
            print >> sys.stderr, "r: '%s'" % r.encode("string_escape")
            nerrs += 1
    return nerrs

def main():
    import getopt

    # Empirically observed to take about a second to run
    count = 100
    seed = None
    opts, args = getopt.getopt(sys.argv[1:], 'c:s:',
                               ['build', 'count=', 'seed='])
    for o, a in opts:
        if o in ('-c', '--count'):
            count = int(a)
        elif o in ('-s', '--seed'):
            seed = long(a, base=0) # accepts base 10 or 16 strings
        elif o == '--build':
            buildprobtable(sys.stdout,
                           'find .hg/store/data -type f && '
                           'cat .hg/store/fncache 2>/dev/null')
            sys.exit(0)

    if seed is None:
        try:
            seed = long(binascii.hexlify(os.urandom(16)), 16)
        except AttributeError:
            seed = long(time.time() * 1000)

    rng = random.Random(seed)
    if runtests(rng, seed, count):
        sys.exit(1)

if __name__ == '__main__':
    main()