Listing meataxe matrices with zero rows is broken

[tscrim]

sage: Matrix(GF(9), 0, 3)._list()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-673c5638db92> in <module>()
----> 1 Matrix(GF(Integer(9)), Integer(0), Integer(3))._list()

/usr/local/src/sage-git/local/lib/python2.7/site-packages/sage/matrix/matrix_gfpn_dense.pyx in sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense._list (build/cythonized/sage/matrix/matrix_gfpn_dense.c:9038)()
    908             FfStepPtr(&(p))
    909             sig_check()
--> 910         x.extend([self._converter.int_to_field(FfToInt(FfExtract(p,j))) for j in range(self.Data.Noc)])
    911         self.cache('list', x)
    912         return x

/usr/local/src/sage-git/local/lib/python2.7/site-packages/sage/matrix/matrix_gfpn_dense.pyx in sage.matrix.matrix_gfpn_dense.FieldConverter_class.int_to_field (build/cythonized/sage/matrix/matrix_gfpn_dense.c:3717)()
    135 
    136         """
--> 137         return self.field(x)
    138     cpdef int field_to_int(self, x):
    139         """

/usr/local/src/sage-git/local/lib/python2.7/site-packages/sage/rings/finite_rings/element_givaro.pyx in sage.rings.finite_rings.element_givaro.Cache_givaro.fetch_int (build/cythonized/sage/rings/finite_rings/element_givaro.cpp:8618)()
    591 
    592         if n<0 or n>k.cardinality():
--> 593             raise TypeError("n must be between 0 and self.order()")
    594 
    595         for i from 0 <= i < k.exponent():

TypeError: n must be between 0 and self.order()

CC: @simon-king-jena

Component: interfaces: optional

Author: Jeroen Demeyer

Branch/Commit: 828b188

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/26389

[kwankyu]

comment:2

Do you know offhand (i.e., don't spend much time on this) of a simple way I can extract out the relevant matrix >computation? This is not a minimal example, and it would be useful to get it down smaller.

Right. But I didn't see the failure from the doctest yet, even after I installed meataxe to my installation (on mac). Do you have a specific procedure likely to encounter the failure?

[tscrim]

comment:3

Replying to @kwankyu:

Do you know offhand (i.e., don't spend much time on this) of a simple way I can extract out the relevant matrix >computation? This is not a minimal example, and it would be useful to get it down smaller.

Right. But I didn't see the failure from the doctest yet, even after I installed meataxe to my installation (on mac). Do you have a specific procedure likely to encounter the failure?

You may also have to run sage -b. However, it doesn't always happen, which is the annoying part. Usually I just run sage -tp on the file a bunch of times and it happens with some reasonable frequency.

[kwankyu]

comment:4

Still no failure from

 for i in {1..100}; do sage -tp src/sage/rings/function_field/ideal.py; done

on mac, after sage -i meataxe; make

[simon-king-jena]

Replying to @tscrim:

There is likely an issue with Matrix_gfpn_dense or meataxe, which is likely caused by where things are in memory. This was first noticed by the following test in rings/function_field/ideal.py:

Question: Are you using a special branch? Or do you mean the test in sage/rings/function_field/function_field_ideal.py, not sage/rings/function_field/ideal.py (which doesn't exist)?

When running the tests in .../function_field_ideal.py a hundred times, I get no problems whatsoever. And yes, I do have meataxe installed (using it intensively in computations with the p_group_cohomology package).

This raises the question what kind of machine you are using. Anything special concerning endianness, size of long, I think I recall there can also be issues regarding whether char is signed or not?

[tscrim]

comment:6

Replying to @simon-king-jena:

Replying to @tscrim:

There is likely an issue with Matrix_gfpn_dense or meataxe, which is likely caused by where things are in memory. This was first noticed by the following test in rings/function_field/ideal.py:

Question: Are you using a special branch? Or do you mean the test in sage/rings/function_field/function_field_ideal.py, not sage/rings/function_field/ideal.py (which doesn't exist)?

When running the tests in .../function_field_ideal.py a hundred times, I get no problems whatsoever. And yes, I do have meataxe installed (using it intensively in computations with the p_group_cohomology package).

No, I am running vanilla 8.4.beta7. It seems like you are running 8.4.beta6 or below (specifically, this was added in #25435).

This raises the question what kind of machine you are using. Anything special concerning endianness, size of long, I think I recall there can also be issues regarding whether char is signed or not?

I have seen this arise on multiple patchbots from multiple tickets (sardonis on 25477, sage4 on 12053, sage4 on 26400). I don't think I have anything special. I kinda recall there being a signed char issue, but I thought you had fixed that.

[tscrim]

comment:7

Replying to @kwankyu:

Still no failure from

 for i in {1..100}; do sage -tp src/sage/rings/function_field/ideal.py; done

on mac, after sage -i meataxe; make

Maybe it is not something that shows up on macs (I am running Ubuntu 16.04 LTS).

[simon-king-jena]

comment:8

Replying to @tscrim:

No, I am running vanilla 8.4.beta7. It seems like you are running 8.4.beta6 or below (specifically, this was added in #25435).

That would explain it: I got

sage: version()
'SageMath version 8.4.beta5, Release Date: 2018-09-15'

OK, I'll try to see what I can do.

EDIT: I'll use the current develop branch merged with the branch that introduces singular-4.1.1.p3.

[simon-king-jena]

comment:9

After upgrading, I indeed get frequent errors with that test, namely twice the same test in the same file:

File "src/sage/rings/function_field/ideal.py", line 2581, in sage.rings.function_field.ideal.FunctionFieldIdealInfinite_global.is_prime
Failed example:
    I.factor()
Exception raised:
    Traceback (most recent call last):
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 659, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1070, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.rings.function_field.ideal.FunctionFieldIdealInfinite_global.is_prime[4]>", line 1, in <module>
        I.factor()
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/function_field/ideal.py", line 2673, in factor
        return Factorization(self._factor(), cr=True)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/function_field/ideal.py", line 2695, in _factor
        for iprime, exp in O._to_iF(self).factor():
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/function_field/ideal.py", line 1574, in factor
        return Factorization(self._factor(), cr=True)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/function_field/ideal.py", line 1600, in _factor
        qs = [q[0] for q in O.decomposition(prime)]
      File "sage/misc/cachefunc.pyx", line 1953, in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10824)
        w = self._instance_call(*args, **kwds)
      File "sage/misc/cachefunc.pyx", line 1829, in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:10280)
        return self.f(self._instance, *args, **kwds)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/function_field/order.py", line 1840, in decomposition
        Jb =[Kb[0]] + [div(Kb[j],Kb[j-1]) for j in range(1,len(Kb))]
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/function_field/order.py", line 1807, in div
        sJbsIb,proj_sJbsIb,lift_sJbsIb = sJb.quotient_abstract(sIb)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/modules/free_module.py", line 4548, in quotient_abstract
        if check and (not is_FreeModule(sub) or not sub.is_subspace(self)):
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/modules/free_module.py", line 3792, in is_subspace
        return self.is_submodule(other)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/modules/free_module.py", line 1460, in is_submodule
        return all(x in S for x in M.list())
      File "sage/matrix/matrix0.pyx", line 156, in sage.matrix.matrix0.Matrix.list (build/cythonized/sage/matrix/matrix0.c:4165)
        return list(self._list())
      File "sage/matrix/matrix_gfpn_dense.pyx", line 910, in sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense._list (build/cythonized/sage/matrix/matrix_gfpn_dense.c:9038)
        x.extend([self._converter.int_to_field(FfToInt(FfExtract(p,j))) for j in range(self.Data.Noc)])
      File "sage/matrix/matrix_gfpn_dense.pyx", line 137, in sage.matrix.matrix_gfpn_dense.FieldConverter_class.int_to_field (build/cythonized/sage/matrix/matrix_gfpn_dense.c:3717)
        return self.field(x)
      File "sage/rings/finite_rings/element_givaro.pyx", line 593, in sage.rings.finite_rings.element_givaro.Cache_givaro.fetch_int (build/cythonized/sage/rings/finite_rings/element_givaro.cpp:8618)
        raise TypeError("n must be between 0 and self.order()")
    TypeError: n must be between 0 and self.order()

The error seems to indicate that the matrix contains items that do not belong to the underlying field. And that sounds pretty much like a memory corruption.

I cannot dive into it at the moment (need to prepare a written exam to be held tomorrow), but at least I can confirm the problem.

[simon-king-jena]

comment:10

The good thing is that it seems not to be caused by some obscure side-effect of other tests: I did

sage: K.<x> = FunctionField(GF(3^2)); _.<t> = PolynomialRing(K)
sage: F.<y> = K.extension(t^3 + t^2 - x^4)
sage: Oinf = F.maximal_order_infinite()
sage: I = Oinf.ideal(1/x)
sage: I.factor()

in three new Sage sessions. The first two times the test worked. The third time it failed.

[simon-king-jena]

comment:16

Please do not always change the ticket description. It makes me get a long mail (stating the old description but not the new one). Moreover it hides what you have actually changed (unless one clicks on the "diff" button).

So please, when you dig further, write a comment.

[vbraun]

comment:17

Since its optional I don't really see this as a blocker; Though if a simple bugfix materializes really soon I'd consider merging it...

[jdemeyer]

Author: Jeroen Demeyer

[simon-king-jena]

comment:20

Nice! So, the problem is just a corner case that was forgotten to be dealt with in my wrapper for SharedMeatAxe. That's a big relief. I thought it would be caused by a problem in SharedMeatAxe's memory management.

[jdemeyer]

Branch: u/jdemeyer/a_bug_likely_with_matrix_gfpn_dense_or_meataxe

[jdemeyer]

New commits:

828b188

Fix listing meataxe matrices with zero rows

[jdemeyer]

Commit: 828b188

[jdemeyer]

comment:23

The mystery is why this bug suddenly shows up now. As far as I can tell (by looking at git history), this has been broken all the time since #12103.

[simon-king-jena]

comment:24

Replying to @jdemeyer:

The mystery is why this bug suddenly shows up now. As far as I can tell (by looking at git history), this has been broken all the time since #12103.

Well, it is not a big surprise if the old code accessed uninitialised memory.

[jdemeyer]

comment:25

Patchbot passed on sage4 which has meataxe installed.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:26

LGTM. Thank you Jeroen.

[vbraun]

Changed branch from u/jdemeyer/a_bug_likely_with_matrix_gfpn_dense_or_meataxe to 828b188

[embray]

comment:28

This should be re-targeted for 8.5.