Patchwork [1,of,2] test-revlog-raw: fix "genbits" implementation

login
register
mail settings
Submitter Jun Wu
Date April 3, 2017, 1:15 a.m.
Message ID <1caf8fd34ce68f6e6a73.1491182129@x1c>
Download mbox | patch
Permalink /patch/19920/
State Accepted
Headers show

Comments

Jun Wu - April 3, 2017, 1:15 a.m.
# HG changeset patch
# User Jun Wu <quark@fb.com>
# Date 1491181967 25200
#      Sun Apr 02 18:12:47 2017 -0700
# Node ID 1caf8fd34ce68f6e6a739eda7687e795877effa5
# Parent  04ec317b81280c189fcea33a05c8cbbac3c186b1
# Available At https://bitbucket.org/quark-zju/hg-draft
#              hg pull https://bitbucket.org/quark-zju/hg-draft -r 1caf8fd34ce6
test-revlog-raw: fix "genbits" implementation

The "genbits" implementation is actually incorrect. This patch fixes it. A
good "genbits" implementation should pass the below assertion:

    n = 3 # or other number
    l = list(genbits(n))
    assert 2**(n*2) == len(set((l[i]<<n)+l[i+1] for i in range(len(l)-1)))

An assertion is added to make sure "genbits" won't work unexpectedly.
Yuya Nishihara - April 3, 2017, 2:38 p.m.
On Sun, 2 Apr 2017 18:15:29 -0700, Jun Wu wrote:
> # HG changeset patch
> # User Jun Wu <quark@fb.com>
> # Date 1491181967 25200
> #      Sun Apr 02 18:12:47 2017 -0700
> # Node ID 1caf8fd34ce68f6e6a739eda7687e795877effa5
> # Parent  04ec317b81280c189fcea33a05c8cbbac3c186b1
> # Available At https://bitbucket.org/quark-zju/hg-draft
> #              hg pull https://bitbucket.org/quark-zju/hg-draft -r 1caf8fd34ce6
> test-revlog-raw: fix "genbits" implementation

Queued, thanks. I haven't reviewed genbits() carefully, but I trust you.

Patch

diff --git a/tests/test-revlog-raw.py b/tests/test-revlog-raw.py
--- a/tests/test-revlog-raw.py
+++ b/tests/test-revlog-raw.py
@@ -167,4 +167,5 @@  def genbits(n):
     # Gray Code. See https://en.wikipedia.org/wiki/Gray_code
     gray = lambda x: x ^ (x >> 1)
+    reversegray = dict((gray(i), i) for i in range(m))
 
     # Generate (n * 2) bit gray code, yield lower n bits as X, and look for
@@ -178,5 +179,7 @@  def genbits(n):
     yield x
     for i in range(m * m):
+        x = reversegray[x]
         y = gray(a[x] + x * m) & (m - 1)
+        assert a[x] < m
         a[x] += 1
         x = y