Opened 15 months ago

Closed 14 months ago

Last modified 14 months ago

#26389 closed defect (fixed)

Listing meataxe matrices with zero rows is broken

Reported by: tscrim Owned by:
Priority: major Milestone: sage-8.5
Component: interfaces: optional Keywords:
Cc: SimonKing Merged in:
Authors: Jeroen Demeyer Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 828b188 (Commits) Commit: 828b18891f09f40960bc6a7f3aa1510cfb679391
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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()

Change History (28)

comment:1 Changed 15 months ago by jdemeyer

  • Priority changed from critical to blocker
  • Summary changed from Hisenbug with Matrix_gfpn_dense or meataxe to Heisenbug with Matrix_gfpn_dense or meataxe

comment:2 follow-up: Changed 15 months ago by klee

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?

comment:3 in reply to: ↑ 2 Changed 15 months ago by tscrim

Replying to klee:

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.

comment:4 follow-up: Changed 15 months ago by klee

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

comment:5 in reply to: ↑ description ; follow-up: Changed 14 months ago by SimonKing

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?

comment:6 in reply to: ↑ 5 ; follow-up: Changed 14 months ago by tscrim

Replying to SimonKing:

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.

comment:7 in reply to: ↑ 4 Changed 14 months ago by tscrim

Replying to klee:

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).

comment:8 in reply to: ↑ 6 Changed 14 months ago by SimonKing

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.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:9 Changed 14 months ago by SimonKing

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.

comment:10 Changed 14 months ago by SimonKing

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.

comment:11 Changed 14 months ago by klee

  • Description modified (diff)

comment:12 Changed 14 months ago by klee

  • Description modified (diff)

comment:13 Changed 14 months ago by klee

  • Description modified (diff)

comment:14 Changed 14 months ago by klee

  • Description modified (diff)
  • Summary changed from Heisenbug with Matrix_gfpn_dense or meataxe to A bug likely with Matrix_gfpn_dense or meataxe

comment:15 Changed 14 months ago by klee

  • Description modified (diff)

comment:16 Changed 14 months ago by SimonKing

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.

comment:17 Changed 14 months ago by vbraun

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...

comment:18 Changed 14 months ago by klee

  • Priority changed from blocker to major

comment:19 Changed 14 months ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Description modified (diff)

comment:20 Changed 14 months ago by SimonKing

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.

comment:21 Changed 14 months ago by jdemeyer

  • Branch set to u/jdemeyer/a_bug_likely_with_matrix_gfpn_dense_or_meataxe

comment:22 Changed 14 months ago by jdemeyer

  • Commit set to 828b18891f09f40960bc6a7f3aa1510cfb679391
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from A bug likely with Matrix_gfpn_dense or meataxe to Listing meataxe matrices with zero rows is broken

New commits:

828b188Fix listing meataxe matrices with zero rows

comment:23 follow-up: Changed 14 months ago by 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.

comment:24 in reply to: ↑ 23 Changed 14 months ago by SimonKing

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.

comment:25 Changed 14 months ago by jdemeyer

Patchbot passed on sage4 which has meataxe installed.

comment:26 Changed 14 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM. Thank you Jeroen.

comment:27 Changed 14 months ago by vbraun

  • Branch changed from u/jdemeyer/a_bug_likely_with_matrix_gfpn_dense_or_meataxe to 828b18891f09f40960bc6a7f3aa1510cfb679391
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:28 Changed 14 months ago by embray

  • Milestone changed from sage-8.4 to sage-8.5

This should be re-targeted for 8.5.

Note: See TracTickets for help on using tickets.