test_lll_lll fails on 32-bit platforms

[infinity0]

See https://buildd.debian.org/status/package.php?p=fpylll&suite=experimental failing on armhf armel i386 mips mipsel powerpc x32

I think 32-bit is the common factor here.

=================================== FAILURES ===================================
_________________________________ test_lll_lll _________________________________

    def test_lll_lll():
        for m, n in dimensions:
            A = make_integer_matrix(m, n)
            for int_type in int_types:
                AA = IntegerMatrix.from_matrix(A, int_type=int_type)
                b00 = []
                for float_type in float_types:
                    B = copy(AA)
                    M = GSO.Mat(B, float_type=float_type)
                    lll = LLL.Reduction(M)
                    lll()
                    if (m, n) == (0, 0):
                        continue
                    b00.append(B[0, 0])
                for i in range(1, len(b00)):
>                   assert b00[0] == b00[i]
E                   assert 0 == -1

tests/test_lll.py:40: AssertionError
===================== 1 failed, 23 passed in 88.09 seconds =====================

[infinity0]

The failure persists even after I apply b1004c289e344da0d20298add7cd56a4b5abc45f

[infinity0]

Strangely, the failure is only triggered if I run all of the preceding tests in the same run:

python2.7 -m pytest -s tests/test_bkz.py tests/test_bkz_python.py tests/test_cvp.py tests/test_gso.py tests/test_lll.py

Removing any one of these will give a different error in test_lll_lll:

_____________________________________________________________________________________________________________ test_lll_lll ______________________________________________________________________________________________________________

    def test_lll_lll():
        for m, n in dimensions:
            print m, n
            A = make_integer_matrix(m, n)
            for int_type in int_types:
>               AA = IntegerMatrix.from_matrix(A, int_type=int_type)

tests/test_lll.py:30: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
src/fpylll/fplll/integer_matrix.pyx:408: in fpylll.fplll.integer_matrix.IntegerMatrix.from_matrix
    ???
src/fpylll/fplll/integer_matrix.pyx:656: in fpylll.fplll.integer_matrix.IntegerMatrix.set_matrix
    ???
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

>   ???
E   OverflowError: Python int too large to convert to C long

src/fpylll/fplll/integer_matrix.pyx:911: OverflowError
================================================================================================== 1 failed, 8 passed in 46.31 seconds ==================================================================================================

[infinity0]

The OverflowError happens when n, m = 50, 50, which is expected on 32 bit platforms since you call A.randomize("uniform", bits=m) earlier in the test. A's elements are 50 bits (mpz_t) but you try to set these into AA with elements having max 32 bits.

The AssertionError happens when n, m = 2, 2, and I'm still not sure why it is only triggered when running those other tests before running test_lll_lll.

[infinity0]

The AssertionError goes away when I remove (10, 10), (50, 50), (60, 60) from the dimensions array (to try to deal with the OverflowError), even when I run the other tests as well.

[infinity0]

(However I'm not sure if that's the best fix, since it doesn't explain why the AssertionError was happening in the first place, and in fact confuses me more since it occured with m, n = 2, 2 which remains in the dimensions array).

[infinity0]

TL;DR summary:

GOOD Running test_lll.py by itself:

test_lll_lll
m n = 2 2
long [('d', 0), ('ld', 0), ('dpe', 0), ('mpfr', 0)]
mpz  [('d', 0), ('ld', 0), ('dpe', 0), ('mpfr', 0)]

(expected OverflowError for m n > 32)

BAD Running test_{bkz,bkz_python,cvp,gso,lll}.py in sequence:

test_lll_lll
m n = 2 2
long [('d', 0), ('ld', 0), ('dpe', -1), ('mpfr', -1)]  # fails
mpz  [('d', 0), ('ld', 0), ('dpe', -1), ('mpfr', -1)]  # fails, with for int_type in reversed(int_types):

GOOD Running test_{bkz,bkz_python,cvp,gso,lll}.py in sequence, with dimensions without 50,50 and 60,60:

test_lll_lll
m n = 2 2
long [('d', 0), ('ld', 0), ('dpe', 0), ('mpfr', 0)]
mpz  [('d', 0), ('ld', 0), ('dpe', 0), ('mpfr', 0)]

GOOD Running test_{bkz,bkz_python,cvp,gso,lll}.py in sequence, with test_lll_init disabled/removed:

test_lll_lll
m n = 2 2
long [('d', 0), ('ld', 0), ('dpe', 0), ('mpfr', 0)]
mpz  [('d', 0), ('ld', 0), ('dpe', 0), ('mpfr', 0)]

(expected OverflowError for m n > 32)

[malb]

I can reproduce this in a 32-bit VM. Not sure when I'll get around to fixing it, though, unfortunately.

[infinity0]

Do you think it's fine to just "fix" the test by removing those higher dimensions? I would have done it already, but the failure mode is so weird I thought it might indicate some deeper problem (that might also affect 64 bit platforms).

[infinity0]

I applied this work around, like this: https://anonscm.debian.org/cgit/python-modules/packages/fpylll.git/tree/debian/patches/workaround-test-lll-lll-32-bit.patch?id=9307be893b783c97d91e65bec415e55c24f355e4

Sage seems to be unaffected, I have no extra test failures on x86 relating to fpylll, beyond the failures already observed on x86-64.

[malb]

Hi, I've merged your patch. You patch is actually more than a workaround, it is the fix that's needed. Thank you! Would you like us to cut a new release for easier packaging?

[infinity0]

Hey, thanks for merging. A new release is not necessary for Debian since I've already applied the patch, but might make things slightly easier for other distributions.

I thought it was only a "work around" because those larger dimensions cause AssertionError instead of OverflowError in the case where specific other unrelated tests are run beforehand. That suggests that there is some global state somewhere, that causes errors from different tests to affect each other, which might affect "real code" as well.

[malb]

AFAIK the global state is simply the global RNG state, leading to different lattices being presented to the test depending on how the thing is run. We should definitely fix that.