Upgrade to GAP 4.8.6

[Samuel Lelièvre]

GAP 4.8.6 was released on 2016-11-14.

Release announcement: ​http://mail.gap-system.org/pipermail/forum/2016/005368.html

GAP 4.8.6 page ​http://gap-system.org/Releases/4.8.6.html

Changelog: ​http://www.gap-system.org/Manuals/doc/changes/chap2.html#X7B6C9EFD7DF68823

Tarballs:

• ​http://users.ox.ac.uk/~coml0531/sage/gap-4.8.6.tar.bz2
• ​http://users.ox.ac.uk/~coml0531/sage/database_gap-4.8.6.tar.bz2
• ​http://users.ox.ac.uk/~coml0531/sage/gap_packages-4.8.6.tar.bz2
• ​http://users.ox.ac.uk/~coml0531/sage/libgap-4.8.6.tar.gz

[Dima Pasechnik]

Debian has patches for 4.8.6 update of libgap and gap, see ​https://groups.google.com/d/msg/sage-packaging/O2PAsuAELMA/vKCdnu3RBAAJ

so we just should take them. Due to miscommunication with the Debian people, I only found out by chance, as I saw them asking what a GAP-related Sage doctest would output for GAP 4.8.6 in place of 4.8.3 :-)

[Dima Pasechnik]

a 1st try for update; already includes the patch from #22116, but still needs few doctest fixes, due to changes in random sources, mostly.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ba1e2ae

we don't have these packages installed by default

[Dima Pasechnik]

libgap is built using ​modified upstream with manually adding src/libgap.map to the tarball as mentioned ​here. A proper (upstream) fix should be via automake config, I presume.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b6b44c7	GAPs random object generator has changed
​2d86709	use improved GAPs Iterator and Enuerator in matrix_group.py
​ce16e91	remaining easy doctest fixes

[Jeroen Demeyer]

What do you expect from me? As I mentioned on #22116, I disagree with build/pkgs/gap_packages/patches/guava_leon.patch

[Jeroen Demeyer]

I also wonder why you need the change to build/pkgs/database_gap/spkg-install. I don't know enough about GAP to know when gap_reset_workspace() is needed, but I think that you should give justification for that removal.

[Dima Pasechnik]

Replying to jdemeyer:

What do you expect from me? As I mentioned on #22116, I disagree with build/pkgs/gap_packages/patches/guava_leon.patch

This is now ​upstream and will be in the next release of Guava.

[Jeroen Demeyer]

Replying to dimpase:

Replying to jdemeyer:

What do you expect from me? As I mentioned on #22116, I disagree with build/pkgs/gap_packages/patches/guava_leon.patch

This is now upstream and will be in the next release of Guava.

Then please update the patch file with a pointer to upstream. For reference, also add it on this Trac page.

[Dima Pasechnik]

Replying to jdemeyer:

I also wonder why you need the change to build/pkgs/database_gap/spkg-install. I don't know enough about GAP to know when gap_reset_workspace() is needed, but I think that you should give justification for that removal.

It is safe to omit this call. In fact, gap_reset_workspace() needs some work. It has not really been touched in 5 years, and it hangs on me now and then. I do not want to do it on this ticket - it has been iffy for a while already.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​990b5db	added a pointer to upstream change
​35c8fea	workspace will be updated automatically anyway.

[Dima Pasechnik]

I have opened #22244 to deal with gap_reset_workspace() and GAP packages in more detail.

[Jeroen Demeyer]

If you are planning to deal with it anyway on #22244, why not leave the gap_reset_workspace as it is in this ticket?

[Dima Pasechnik]

Replying to jdemeyer:

If you are planning to deal with it anyway on #22244, why not leave the gap_reset_workspace as it is in this ticket?

Cause it causes spkg-install hang indefinitely on one of my systems.

[Jeroen Demeyer]

Replying to dimpase:

Cause it causes spkg-install hang indefinitely on one of my systems.

Well, then that problem should be fixed instead of hiding it under the carpet.

[Dima Pasechnik]

Replying to jdemeyer:

Replying to dimpase:

Cause it causes spkg-install hang indefinitely on one of my systems.

Well, then that problem should be fixed instead of hiding it under the carpet.

It is not a problem not to have that call in spkg-install. It merely means that some later GAP startup will be slower, once. (And yes we will look at it in #22244) By the way, there is no such call in spkg-install of gap_packages.

[Jeroen Demeyer]

Regardless, I feel that the removal of gap_reset_workspace is orthogonal to the issue of this ticket and should be handled separately.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​30476df	Merge branch 'u/dimpase/gap4.8.6' of trac.sagemath.org:sage into gapup
​dc8c742	Clean GAP installation directory before re-installing
​573afa5	Make sure that we create $SAGE_LOCAL/gap
​a893fc9	Merge branch 'u/jdemeyer/gap_install_error__text_file_busy_' of trac.sagemath.org:sage into gapup
​224dd07	Revert "workspace will be updated automatically anyway."

[Dima Pasechnik]

I've added the branch from #22272, rebased over the latest beta, and reverted the removal of gap_reset_workspace (commit 35c8fea). I do not see the hang I dealt with by adding the latter commit anymore (perhaps it's the effect of #22272 ?). Anyway, I hope this makes everyone happy :-)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d861b37

obvious doctest fixes

[Dima Pasechnik]

What remains to fix is the following, less obvious:

File "src/sage/combinat/root_system/weyl_group.py", line 175, in sage.combinat.root_system.weyl_group.WeylGroup
Failed example:
    TestSuite(WeylGroup(["A",3,1])).run() # long time
Expected nothing
Got:
    Failure in _test_enumerated_set_contains:
    Traceback (most recent call last):
      File "/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 293, in run
        test_method(tester = tester)
      File "/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/categories/enumerated_sets.py", line 949, in _test_enumerated_set_contains
        for w in self:
      File "/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/groups/libgap_mixin.py", line 342, in __iter__
        iterator = self.gap().Iterator()
      File "sage/libs/gap/element.pyx", line 2168, in sage.libs.gap.element.GapElement_MethodProxy.__call__ (/home/dima/Sage/sage-dev/src/build/cythonized/sage/libs/gap/element.c:17497)
        return GapElement_Function.__call__(self, self.first_argument)
      File "sage/libs/gap/element.pyx", line 2052, in sage.libs.gap.element.GapElement_Function.__call__ (/home/dima/Sage/sage-dev/src/build/cythonized/sage/libs/gap/element.c:16881)
        raise ValueError('libGAP: ' + str(msg))
    ValueError: libGAP: Error, no method found! Error, no 3rd choice method found for `Enumerator' on 1 arguments
    ------------------------------------------------------------
    The following tests failed: _test_enumerated_set_contains
**********************************************************************
File "src/sage/combinat/root_system/weyl_group.py", line 214, in sage.combinat.root_system.weyl_group.WeylGroup.__init__
Failed example:
    TestSuite(W).run() # long time
Expected nothing
Got:
    Failure in _test_enumerated_set_contains:
    Traceback (most recent call last):
      File "/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 293, in run
        test_method(tester = tester)
      File "/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/categories/enumerated_sets.py", line 949, in _test_enumerated_set_contains
        for w in self:
      File "/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/groups/libgap_mixin.py", line 342, in __iter__
        iterator = self.gap().Iterator()
      File "sage/libs/gap/element.pyx", line 2168, in sage.libs.gap.element.GapElement_MethodProxy.__call__ (/home/dima/Sage/sage-dev/src/build/cythonized/sage/libs/gap/element.c:17497)
        return GapElement_Function.__call__(self, self.first_argument)
      File "sage/libs/gap/element.pyx", line 2052, in sage.libs.gap.element.GapElement_Function.__call__ (/home/dima/Sage/sage-dev/src/build/cythonized/sage/libs/gap/element.c:16881)
        raise ValueError('libGAP: ' + str(msg))
    ValueError: libGAP: Error, no method found! Error, no 3rd choice method found for `Enumerator' on 1 arguments
    ------------------------------------------------------------
    The following tests failed: _test_enumerated_set_contains
**********************************************************************
2 items had failures:
   1 of  46 in sage.combinat.root_system.weyl_group.WeylGroup
   1 of   6 in sage.combinat.root_system.weyl_group.WeylGroup.__init__
    [203 tests, 2 failures, 16.77 s]

---

New commits:

​d861b37

obvious doctest fixes

[Nicolas M. Thiéry]

Just 2 cents in case this helps the debugging: this group wraps an infinite gap matrix group.

sage: W = WeylGroup(["A",3,1])
sage: W.generators()
(
[-1  1  0  1]  [ 1  0  0  0]  [ 1  0  0  0]  [ 1  0  0  0]
[ 0  1  0  0]  [ 1 -1  1  0]  [ 0  1  0  0]  [ 0  1  0  0]
[ 0  0  1  0]  [ 0  0  1  0]  [ 0  1 -1  1]  [ 0  0  1  0]
[ 0  0  0  1], [ 0  0  0  1], [ 0  0  0  1], [ 1  0  1 -1]
)
sage: W._gap_()
<matrix group with 4 generators>
sage: W._gap_().GeneratorsOfGroup()
[ [ [ -1, 1, 0, 1 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 0 ], [ 1, -1, 1, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 1, -1, 1 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 1, 0, 1, -1 ] ] ]

The gap matrix group can be constructed with:

gap> G := Group([ [ [ -1, 1, 0, 1 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 0 ], [ 1, -1, 1, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 1, -1, 1 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 1, 0, 1, -1 ] ] ])

I am a bit confused by the call of the "Enumerator" gap function, since the Sage sources seem to contain no reference to it (although I do not have the very latest develop under hand).

[Dima Pasechnik]

Replying to nthiery:

Just 2 cents in case this helps the debugging: this group wraps an infinite gap matrix group.

But what exactly is TestSuite() calling? Is there a way to trace this up? In the log above there is line 949, in _test_enumerated_set_contains so it looks as if some kind of enumeration is attempted.

I am a bit confused by the call of the "Enumerator" gap function, since the Sage sources seem to contain no reference to it (although I do not have the very latest develop under hand).

anyways, GAP's Enumerator does not apply to infinite objects, and it was never possible.

[Dima Pasechnik]

Replying to dimpase:

Replying to nthiery:

Just 2 cents in case this helps the debugging: this group wraps an infinite gap matrix group.

But what exactly is TestSuite() calling? Is there a way to trace this up? In the log above there is line 949, in _test_enumerated_set_contains so it looks as if some kind of enumeration is attempted.

I am trying to run

sage: W = WeylGroup(["A",3,1])
sage: sage: W._test_enumerated_set_contains()

but it just never finishes (other ._test_-things seem to run fine). Is it the real bug here? How does one find out what actually is called here?

[Travis Scrimshaw]

My guess is there is not a way for iterating through infinite matrix groups by using a finite set of specified generators using GAP. This does not work in 7.6.beta1:

sage: G = GL(6, ZZ)
sage: it = iter(G)
sage: [it.next() for _ in range(6)]

although it should because

sage: G.gens()
(
[0 1 0 0 0 0]  [0 1 0 0 0 0]  [-1  0  0  0  0  0]  [1 1 0 0 0 0]
[0 0 1 0 0 0]  [1 0 0 0 0 0]  [ 0  1  0  0  0  0]  [0 1 0 0 0 0]
[0 0 0 1 0 0]  [0 0 1 0 0 0]  [ 0  0  1  0  0  0]  [0 0 1 0 0 0]
[0 0 0 0 1 0]  [0 0 0 1 0 0]  [ 0  0  0  1  0  0]  [0 0 0 1 0 0]
[0 0 0 0 0 1]  [0 0 0 0 1 0]  [ 0  0  0  0  1  0]  [0 0 0 0 1 0]
[1 0 0 0 0 0], [0 0 0 0 0 1], [ 0  0  0  0  0  1], [0 0 0 0 0 1]
)

Does that work here? However, we have the category FinitelyGeneratedSemigroups, which contains a default implementation of such an iterator using RecursivelyEnumeratedSet.

In the case at hand WeylGroups is a subcategory of FinitelyGeneratedSemigroups (which is a subcategory of EnumeratedSets), so I suspect what is missing is for the generic (GAP) group iterator to lift the iteration up to the category if it doesn't know how to iterate directly in GAP.

[John Palmieri]

With 7.6.beta2, this works:

sage: W = WeylGroup(["A",3,1])
sage: for w in W: print w
   (... neverending list ...)

With the branch here:

sage: W = WeylGroup(["A",3,1])
sage: for w in W: print w
gap: cannot extend the workspace any more!!!
   (at which point Sage silently quits)

[John Palmieri]

Replying to dimpase:

Replying to nthiery:

Just 2 cents in case this helps the debugging: this group wraps an infinite gap matrix group.

But what exactly is TestSuite() calling?

In this case, I believe it is calling _test_enumerated_set_contains as defined in categories/enumerated_sets.py. That method has a loop which starts with for w in self:. For the group in question, the iterator can't be constructed.

[Dima Pasechnik]

Replying to jhpalmieri:

With 7.6.beta2, this works:

sage: W = WeylGroup(["A",3,1])
sage: for w in W: print w
   (... neverending list ...)

I believe this invokes W.__iter__, right? And the latter is in sage/groups/libgap_mixin.py (cf. W.__iter__??) So this is merely calling self.gap().Iterator(). And the latter does not actually work in Sage 7.5; one gets

ValueError: libGAP: Error, no method found! Error, no 3rd choice method found for `Enumerator' on 1 arguments

whereas with the branch here it does "work" - it runs out of memory...

That is, I believe that the category framework (or something like this) does try to call that W.__iter__, and upon failing (with the old GAP) actually does something that makes sense, namely sage/groups/matrix_gps/matrix_group.py has the lines

if not self.is_finite():
    # use implementation from category framework
    for g in super(Group, self).__iter__():
          yield g
    return

where the code in sage/categories/coxeter_group.py is called to do the right thing.

Whereas with the new GAP one does not get a ValueError and proceeds with running out of memory (actual running done by GAP).

So, somewhere, something must forbid this execution path, but I don't know where and how. All help is welcome. If the fix is not going to happen in GAP-related code, I'd be inclined to press ahead with this ticket, declaring this issue a known (Sage) bug.

[John Palmieri]

In plain 7.6.beta2, W.__iter__() calls the __iter__ method from sage/groups/matrix_groups/matrix_group.py, but that method has been deleted in the current branch. Isn't that the problem?

[Travis Scrimshaw]

Replying to dimpase:

Replying to jhpalmieri:

With 7.6.beta2, this works:

sage: W = WeylGroup(["A",3,1])
sage: for w in W: print w
   (... neverending list ...)

I believe this invokes W.__iter__, right? And the latter is in sage/groups/libgap_mixin.py (cf. W.__iter__??) So this is merely calling self.gap().Iterator(). And the latter does not actually work in Sage 7.5; one gets

ValueError: libGAP: Error, no method found! Error, no 3rd choice method found for `Enumerator' on 1 arguments

whereas with the branch here it does "work" - it runs out of memory...

I would suspect this is a GAP problem by trying to put the entire (matrix) group into memory as a list under an assumption that it is a finite group. Well, our RecursiveEnumeratedSet iterator runs into the same problem, but it will at least output things along the way...

That is, I believe that the category framework (or something like this) does try to call that W.__iter__, and upon failing (with the old GAP) actually does something that makes sense, namely sage/groups/matrix_gps/matrix_group.py has the lines

if not self.is_finite():
    # use implementation from category framework
    for g in super(Group, self).__iter__():
          yield g
    return

where the code in sage/categories/coxeter_group.py is called to do the right thing.

It's actually the reverse that happens: code in the categories is the last called in the MRO. In particular, the first call is to the lines copied above, and for non-finite groups (or at least those not known to be finite), then call up to the corresponding __iter__ implemented in the category (if there is one).

See comment:29 for why it used to work for Weyl groups.

Whereas with the new GAP one does not get a ValueError and proceeds with running out of memory (actual running done by GAP).

You deleted the code above that would call up to the category framework, where it was not using GAP to do the iteration.

So, somewhere, something must forbid this execution path, but I don't know where and how. All help is welcome. If the fix is not going to happen in GAP-related code, I'd be inclined to press ahead with this ticket, declaring this issue a known (Sage) bug.

You probably need to restore part of the __iter__, specifically the code quoted above.

TL;DR - As John said, the problem is removing __iter__ from sage/groups/matrix_groups/matrix_group.py.

[Dima Pasechnik]

Oh, I see. Thanks. Sorry for taking so long to get it. I removed too mich in this ​commit. I will reinstate the part that deals with infinite groups.

However this is still less than ideal. In the finite case for groups that have a fast category framework iterator (e.g. large finite Coxeter groups) one should not call GAP, either. Should this be dealt with on a follow-up ticket, or is there a quick way to add the corresponding filter?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​971f323

reintroduce __init__ in MatrixGroup_gap to handle infinite groups

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fd68158

putting the doctests right

[Travis Scrimshaw]

Replying to dimpase:

However this is still less than ideal. In the finite case for groups that have a fast category framework iterator (e.g. large finite Coxeter groups) one should not call GAP, either. Should this be dealt with on a follow-up ticket, or is there a quick way to add the corresponding filter?

The category iterator is not just for Coxeter groups, but any group with a finite generating set. Have you run timings (and memory usage) comparing the GAP iterator with the one from the category?

At least for Coxeter groups, we can do a check on the rank if there is some cutoff point.

[Volker Braun]

Testsuite fails:

########> Diff in /Users/buildslave-sage/slave/sage_git/build/local/gap/latest\
1045/tst/testinstall/grpmat.tst, line 32:
1046# Input is:
1047Size( AutomorphismGroup( G ) );
1048# Expected output:
104924
1050# But found:
1051#I  autpgrp package is not available. Check that the name is correct
1052#I  and it is present in one of the GAP root directories (see '??RootPaths')

[Dima Pasechnik]

Replying to vbraun:

Testsuite fails:

########> Diff in /Users/buildslave-sage/slave/sage_git/build/local/gap/latest\
1045/tst/testinstall/grpmat.tst, line 32:
...
1051#I  autpgrp package is not available. Check that the name is correct
1052#I  and it is present in one of the GAP root directories (see '??RootPaths')

As far as I am concerned, this is not a bug, but a decision we made at some point to ship only the very minimal default GAP configuration. As you most probably know, GAP assumes quite a few packages to be installed and autoloaded by default; this is patched away by ​ba1e2ae "we don't have these packages installed by default"

Sage's GAP does not install autpgrp by default, and does not autoload it if it is available. Suppose it is available (i.e. gap_packages is installed); then before running GAP_ROOT/tst/testinstall.g one has to load autpgrp manually. I.e.

gap> LoadPackage("autpgrp");;
gap> Read("testinstall.g");

will make everything pass (on my system at least).

[Volker Braun]

Still I'd prefer to have a passing testsuite so that the buildbots can actuall run the tests. Can we just grep out tst/testinstall/grpmat.tst in spkg-check?

[Volker Braun]

I guess it is annoying because of the newline; How about deleting grpmat.tst from the install then?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8b8bff3

fake the output of GAP test needing autpgrp pkg

[Dima Pasechnik]

Replying to git:

Branch pushed to git repo; I updated commit sha1. New commits:

​8b8bff3

fake the output of GAP test needing autpgrp pkg

this should do the trick - I just fake the output of the test in question.