fingolfin commented 6 years ago

[ ping to @alex-konovalov @stevelinton @frankluebeck @ThomasBreuer @ChrisJefferson @markuspf ]

Having merged PR #2773, which updates the ordering of messages as new implications are added (fixing various issues, see issue #2513), we now are seeing a lot of test failures after LoadAllPackages().

Some of them are fixed by PR #2815, but by far not all. The ones I looked at so far all follow the same pattern: two methods A, B in the GAP library where A used to be ranked above B reverse order when all packages are loaded, due to changes in the relative ranking of their involved filters.

In some cases, there already was a static rank adjustment, i.e., by a fixed number, applied in the library; but that change becomes insufficient if one filter increases massively when all packages are loaded, the other are not.

Example 1:

gap> Enumerator( Integers mod 9 );
<enumerator of (Integers mod 9)>
gap> LoadAllPackages();
...
gap> Enumerator( Integers mod 9 );
[ ZmodnZObj( 0, 9 ), ZmodnZObj( 1, 9 ), ZmodnZObj( 2, 9 ), ZmodnZObj( 3, 9 ),
  ZmodnZObj( 4, 9 ), ZmodnZObj( 5, 9 ), ZmodnZObj( 6, 9 ), ZmodnZObj( 7, 9 ),
  ZmodnZObj( 8, 9 ) ]

Explanation for example 1: Before loading all packages, this ViewObj method is used from coll.gi:528:

InstallMethod( ViewObj,
    "for an enumerator that perhaps has its own `ViewObj' function",
    [ IsEnumeratorByFunctions ], 20,

Note the manual rank increase by 20. After loading all packages, this method is used instead:

InstallMethod( ViewObj,
    "for finite lists",
    [ IsList and IsFinite ],
function( list )

Yet in a fresh GAP session, started with gap -A, we observe this:

gap> RankFilter(IsEnumeratorByFunctions);
7
gap> RankFilter(IsList and IsFinite);
4
gap> LoadAllPackages();
...
gap> RankFilter(IsEnumeratorByFunctions);
7
gap> RankFilter(IsList and IsFinite);
139

Oops. So the meager static rank adjustment by 20 is not enough. We'd have to use at least 133 instead. But of course that won't work, unless one adds more packages.

A quick fix for this is the following: since we always want to prefer the IsEnumeratorByFunctions if it is applicable, we could use this dynamic rank adjustment instead: {} -> RankFilter(IsList and IsFinite).

This works, but it leaves me a bit uneasy: for example, the PrintObj method for IsEnumeratorByFunctions has no rank adjustment, static or dynamic, and it doesn't need one. But it might need one if somebody ever adds a PrintObj for, say, IsList and IsFinite. I.e., a non-local change could break that code; there is no way to code defensively to prevent this using a simple low static or dynamic rank adjustment.

So perhaps a better fix is to use SUM_FLAGS here as rank adjustment (strictly speaking, that's still a static rank adjustment, but for practical purposes works fine). After all, we wan these ViewObj and PrintObj methods applied to all IsEnumeratorByFunctions objects (which, after all, have built-in hooks for setting custom ViewObj and PrintObj functions). And even if somebody wanted to install a custom method for their IsEnumeratorByFunctions and IsFOOBAR objects, they can do it, as long as they also set SUM_FLAGS as rank adjustment.

A totally different angle to view this problem is to wonder why did the rank of IsFinite and IsList increase so much? Most of it comes from IsFinite, indeed, RankFilter(IsFinite) = 136 after all packages are loaded.

That's because tons of packages add implications to IsFinite, and at least in some cases, I'd argue they are wrong or at least problematic. But there are certainly many legitimate ones... And then of course there are countless hidden implications which nevertheless affect the ranking (see issue #2336). So in the end, we can't completely fight this...

But in this particular case, the big jump in rank is due to a single implications, set by the automgrp package. It does this:

DeclareProperty("IsAmenable", IsTreeAutomorphismGroup);
InstallTrueMethod(IsAmenable, IsAbelian);
InstallTrueMethod(IsAmenable, IsFinite);

So now IsFinite implies IsAmenable and that in turn has an hidden implication to IsTreeAutomorphismGroup, hence to IsGroup. If I change the above lines to

DeclareProperty("IsAmenable", IsTreeAutomorphismGroup);
InstallTrueMethod(IsAmenable, IsAbelian and IsGroup);
InstallTrueMethod(IsAmenable, IsFinite and IsGroup);

.. then I get RankFilter(IsList and IsFinite) = 6, which is still less than RankFilter(IsEnumeratorByFunctions) = 7, so example 1 is fixed.

But of course this is a fragile fix (and not completely under our control, although I'll contact the AutomGrp authors).

I'll add more examples if I find time, but for now I can already say that we'll have to change something, in the GAP library and in packages:

Switch some methods from static rank adjustments to dynamic (in the GAP library and in packages)
Add a rank adjustment to some methods that don't have any right now
Possibly use SUM_FLAGS for some methods; very loosely said: we'll want that if the filter involves a representation (e.g. in example 1, IsEnumeratorByFunctions is an and-filter that has IsEnumeratorByFunctionsRep amongst it constituents). Perhaps we'd even want to rank representations higher than 1 by default???
Perhaps there are other things we should do?

fingolfin commented 6 years ago

As to "wrong" true methods: e.g. the LOOPS package does this (reported as https://github.com/gap-packages/loops/issues/5)

InstallTrueMethod( IsMiddleALoop, IsCommutative );
InstallTrueMethod( IsFlexible, IsMiddleALoop );
InstallTrueMethod( IsALoop, IsAssociative );

fingolfin commented 6 years ago

Another reason why the rank of IsAbelian increases so much is this from semigroups (reported as https://github.com/gap-packages/Semigroups/issues/519):

InstallTrueMethod(IsCommutativeSemigroup, IsCommutative);

fingolfin commented 6 years ago

With these fixed, only a handful test failures remain in testinstall.

Example 2:

gap> A := AbelianGroup([3,3,3]);; H := AutomorphismGroup(A);;
gap> B := SylowSubgroup(H, 13);; G := SemidirectProduct(B, A);;

This runs into an infinite recursion, in this method from gprd.gi:1080 (the static rank adjustment looks suspicious):

InstallMethod( SemidirectProduct,"different representations",true, 
    [ IsGroup and IsFinite, IsGroupHomomorphism, IsGroup and IsFinite], 
    # don't be higher than specific perm/pc methods
    -20,

Example 3:

gap> IsomorphismPermGroup(Group(()));
IdentityMapping( Group(()) )
gap> LoadAllPackages();
...
gap> IsomorphismPermGroup(Group(()));
[  ] -> [  ]

Reason: Before loading all packages, we trigger this method from ghomperm.gi:1928:

InstallMethod( IsomorphismPermGroup,
    "perm groups",
    true,
    [ IsPermGroup ], 0,
    IdentityMapping );

Afterwards, these two methods both are ranked higher:

InstallMethod( IsomorphismPermGroup,
    [ IsGroup and IsFinite and IsAbelian and CanEasilyComputeWithIndependentGensAbelianGroup ],
    0,
    G -> IsomorphismAbelianGroupViaIndependentGenerators( IsPermGroup, G )
    );

and

InstallMethod( IsomorphismPermGroup, "for finite nilpotent groups", true,
                [ IsNilpotentGroup and IsFinite and KnowsHowToDecompose ], 0,

Indeed, the relative ranks of the filters shifted considerably (note that this already is with fixes applied for the various issues I described above):

gap> RankFilter(IsPermGroup); RankFilter(IsGroup and IsFinite and IsAbelian and CanEasilyComputeWithIndependentGensAbelianGroup); RankFilter(IsNilpotentGroup and IsFinite and KnowsHowToDecompose);
59
58
57
gap> List([IsPermGroup,IsGroup,IsFinite,IsAbelian,CanEasilyComputeWithIndependentGensAbelianGroup,IsNilpotentGroup,KnowsHowToDecompose], RankFilter);
[ 59, 35, 3, 13, 1, 41, 37 ]
gap> LoadAllPackages();
...
gap> RankFilter(IsPermGroup); RankFilter(IsGroup and IsFinite and IsAbelian and CanEasilyComputeWithIndependentGensAbelianGroup); RankFilter(IsNilpotentGroup and IsFinite and KnowsHowToDecompose);
79
94
85
gap> List([IsPermGroup,IsGroup,IsFinite,IsAbelian,CanEasilyComputeWithIndependentGensAbelianGroup,IsNilpotentGroup,KnowsHowToDecompose], RankFilter);
[ 79, 43, 5, 13, 1, 61, 45 ]

I'd argue that in this case, the "correct" solution is to add SUM_FLAGS to the first of the three listed methods.

wilfwilson commented 6 years ago

I agree that we should add SUM_FLAGS to the first method. Selfishly, I have made a PR doing exactly that (https://github.com/gap-system/gap/pull/2819), because with this change, and with a PR to Semigroups that I am about to open, the Semigroups package tests run without errors against both GAP master and stable-4.10.

frankluebeck commented 6 years ago

Here are a few comments on these interesting examples.

In my opinion we should try to avoid any method installations with an extra rank. Using the optional val argument of InstallMethod will sooner or later lead to a mess.
The example of the ViewObj method for Enumerator( Integers mod 9 ):
- There is nothing really bad with the example shown above, there are two applicable methods which can both be higher ranked, depending on the (current) rank of some filters.
- One option is to just accept this, both methods print something valid.
- On the other hand I agree to prefer the method for enumerators, even if an enumerator happens to be a finite list. But this is really a personal preference, and there is no way that GAP can do this choice for us. The "correct" solution for me in such a case is to install the method for enumerators twice to tell GAP that this method should be preferred:
```
InstallMethod( ViewObj, ["IsEnumeratorByFunctions"], 
function(e) Print("Enumerator"); end );
## prefer this method also for finite enumerators
InstallMethod( ViewObj, ["IsEnumeratorByFunctions and IsFinite"], 
function(e) Print("Enumerator"); end );
```
  Side remark: I have code which does the above in one step, maybe something like that could also be implemented in the GAP library, it then looks like:
```
InstallMethod( ViewObj, 
["IsEnumeratorByFunctions or IsEnumeratorByFunctions and IsFinite"],
function(e) Print("Enumerator"); end );
```
The example
```
DeclareProperty("IsAmenable", IsTreeAutomorphismGroup);
InstallTrueMethod(IsAmenable, IsAbelian);
InstallTrueMethod(IsAmenable, IsFinite);
```
I would say that these calls of InstallTrueMethod are a bug. The property IsAmenable is declared here only for groups in IsTreeAutomorphismGroup. And the True-methods following this declaration should really only involve groups in IsTreeAutomorphismGroup and no other objects which happen to be in the filter IsAbelian or IsFinite. That is, the lines above should be corrected to
```
DeclareProperty("IsAmenable", IsTreeAutomorphismGroup);
InstallTrueMethod(IsAmenable, IsTreeAutomorphismGroup and IsAbelian);
InstallTrueMethod(IsAmenable, IsTreeAutomorphismGroup and  IsFinite);
```
I guess (or hope) that this is really what the author of those lines had in mind.

fingolfin commented 6 years ago

Re IsAmeanable: yes, I also consider this as a bug, which is why I reported it as such to the AutomGrp authors.

olexandr-konovalov commented 6 years ago

Latest observed number of diffs from today's build of the release candidate for GAP 4.11:

testinstall: 171
teststandard: 175
testbugfix: 12 not covering package tests that fail.

fingolfin commented 6 years ago

I made two pull requests to work on improving this, and reported an issue in JupyterKernel which made things here worse (by now they made a new release with a fix, thanks for the quick reaction). I also have a few more fixes lined up as part of PR #2835. But right now it seems I am the only one working on resolving these, and I am not even sure it's a winnable battle on the long run.

So perhaps we should simply disable the method reordering code @stevelinton wrote again, at least until the time other people have time to look into this issue and fix it.

ThomasBreuer commented 6 years ago

@fingolfin thanks for your investigations.

Concerning the question whether or not the method reordering code should be disabled, I think it is better to keep it in the master branch, but not to consider it for a release.

Concerning the question for fixes, I do not think that we have understood enough for being able to tell what fixing means.

I regard this topic as one for which a global discussion via e-mail would be more appropriate than a collection of pull requests with their own sets of discussions. I am interested in this topic, and will put together my thoughts on it.

wilfwilson commented 6 years ago

My general feeling is that keeping the method reordering in the master branch is the right thing to do.

olexandr-konovalov commented 6 years ago

I do have hope that it may stay and we may understand the remaining problems and fix them. This night's tests in Jenkins demonstrate substantial reduction in the number of diffs in testinstall and teststandard:

testinstall: 171 -> 21
teststandard: 175 -> 25
testbugfix: 12 -> 12

olexandr-konovalov commented 6 years ago

2869 reduces the number of diffs a bit further, but does not seem to resolve the issue completely yet. More details tomorrow.

fingolfin commented 6 years ago

Alll remaining issues seems to be related to semigroups related, so perhaps @wilfwilson and @james-d-mitchell can help. Specifically, after LoadAllPackages(), I am seeing:

...
testing: GAPROOT/tst/testinstall/reesmat.tst
########> Diff in GAPROOT/tst/testinstall/reesmat.tst:226
# Input is:
IsRegularSemigroup(R);
# Expected output:
true
# But found:
Error, recursion depth trap (5000)
########
########> Diff in GAPROOT/tst/testinstall/reesmat.tst:898
# Input is:
iso := IsomorphismReesMatrixSemigroup(U);;
# Expected output:
# But found:
Error, recursion depth trap (5000)
########
     408 ms (239 ms GC) and 46.2MB allocated for reesmat.tst
...
testing: GAPROOT/tst/testinstall/semipperm.tst
########> Diff in GAPROOT/tst/testinstall/semipperm.tst:35
# Input is:
One(I);
# Expected output:
<identity partial perm on [ 1, 2, 3 ]>
# But found:
Error, Record Element: <rec> must be a record (not a boolean or fail)
########
     462 ms (343 ms GC) and 39.1MB allocated for semipperm.tst
testing: GAPROOT/tst/testinstall/semirel.tst
########> Diff in GAPROOT/tst/testinstall/semirel.tst:64
# Input is:
grp := EquivalenceRelationPartition(GreensRRelation(s1));;
# Expected output:
# But found:
Error, recursion depth trap (5000)
########
########> Diff in GAPROOT/tst/testinstall/semirel.tst:66
# Input is:
Set(List(grp,i->Size(i))) = Set(List(grp1,i->Size(i)));
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `Size' on 1 arguments
########
########> Diff in GAPROOT/tst/testinstall/semirel.tst:68
# Input is:
glp := EquivalenceRelationPartition(GreensLRelation(s1));;
# Expected output:
# But found:
Error, recursion depth trap (5000)
########
########> Diff in GAPROOT/tst/testinstall/semirel.tst:70
# Input is:
Set(List(glp,i->Size(i))) = Set(List(glp1,i->Size(i)));
# Expected output:
true
# But found:
Error, Variable: 'glp' must have a value
########
########> Diff in GAPROOT/tst/testinstall/semirel.tst:72
# Input is:
gjp := EquivalenceRelationPartition(GreensJRelation(s1));;
# Expected output:
# But found:
Error, recursion depth trap (5000)
########
########> Diff in GAPROOT/tst/testinstall/semirel.tst:74
# Input is:
Set(List(gjp,i->Size(i))) = Set(List(gjp1,i->Size(i)));
# Expected output:
true
# But found:
Error, Variable: 'gjp' must have a value
########
     456 ms (338 ms GC) and 28.1MB allocated for semirel.tst
testing: GAPROOT/tst/testinstall/semitran.tst
########> Diff in GAPROOT/tst/testinstall/semitran.tst:242
# Input is:
IsomorphismTransformationSemigroup(I);;
# Expected output:
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `Enumerate' on 1 arguments
The 1st argument is 'fail' which might point to an earlier problem

########
########> Diff in GAPROOT/tst/testinstall/semitran.tst:243
# Input is:
BruteForceIsoCheck(last);
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `IsInjective' on 1 arguments
########
########> Diff in GAPROOT/tst/testinstall/semitran.tst:245
# Input is:
BruteForceInverseCheck(last2);
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `InverseGeneralMapping' on 1 arguments
########
########> Diff in GAPROOT/tst/testinstall/semitran.tst:311
# Input is:
IsomorphismTransformationMonoid(T);;
# Expected output:
# But found:
Error, Record Element: <rec> must be a record (not a boolean or fail)
########
########> Diff in GAPROOT/tst/testinstall/semitran.tst:312
# Input is:
BruteForceIsoCheck(last);
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `IsInjective' on 1 arguments
########
########> Diff in GAPROOT/tst/testinstall/semitran.tst:314
# Input is:
BruteForceInverseCheck(last2);
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `InverseGeneralMapping' on 1 arguments
########
########> Diff in GAPROOT/tst/testinstall/semitran.tst:360
# Input is:
BruteForceAntiIsoCheck(last);
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `Enumerate' on 1 arguments
The 1st argument is 'fail' which might point to an earlier problem

########
########> Diff in GAPROOT/tst/testinstall/semitran.tst:362
# Input is:
BruteForceInverseCheck(last2);
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `InverseGeneralMapping' on 1 arguments
########
     480 ms (334 ms GC) and 59.2MB allocated for semitran.tst

fingolfin commented 6 years ago

The source of the first error is this method in semirel.gi:

#################
#################
##
#M AsSSortedList(<gclass>)
##
## returns the elements of the Greens class <gclass>
##

InstallMethod(AsSSortedList, "for a Green's class", true, [IsGreensClass], 0,
    x-> AsSSortedList(CanonicalGreensClass(x)));

If x equals CanonicalGreensClass(x) then clearly this leads to an infinite loop. This usually works because the GAP library method for GreensRClasses does this for the "canonical" classes:

SetAsSSortedList(classes[i], AsSSortedList(semi){sc[i]});

This still works if semigroups is loaded, but breaks once all packages are loaded -- presumably because some methods change their relative ranks.

olexandr-konovalov commented 6 years ago

Thanks. Just in case, in Jenkins with new Semigroup release picked up on Oct 2nd, there are still diffs. From St Andrews, one can access logs here.

olexandr-konovalov commented 6 years ago

Diffs in last night tests in Jenkins increased again:

testinstall: 171 -> 21 -> 30
teststandard: 175 -> 25 -> 34
testbugfix: 12 -> 12 -> 12

due to some packages update happening in the meantime (Semigroups, AutomGrp, and more). On Travis, with the "approved" packages archive packages-master.tar.gz, we have 17 diffs in testinstall.

wilfwilson commented 6 years ago

I made a PR to the Semigroups package which will mean that testinstall runs without diffs with all packages loaded. But not yet testbugfix.

https://github.com/gap-packages/Semigroups/pull/551

fingolfin commented 6 years ago

Actually, many of these failures are due to IsFinite having an insane high rank. But that should be fixed by automgrp 1.3.1. Strangely enough, this is not included in the current package distribution tarball (downloaded 10 minutes ago), though @alex-konovalov ?

olexandr-konovalov commented 6 years ago

Nothing strange. automgrp package has been just picked up this week, but the archive of "approved" package releases, i.e. packages-master,tag.gz was last time updated during the weekend. It's not updated automatically daily, since otherwise life will be harder with several moving targets.

P.S. I still see 30 diffs in testinstall.g in the nightly tests which includes that new version of automgrp.

fingolfin commented 6 years ago

OK. It would still be helpful to get automgrp 1.3.1 and then repeat the test, because I suspect there will be different errors, and that difference is quite significant.

olexandr-konovalov commented 6 years ago

Looked at Jenkins: new automgrp package has problems. First, when GAP started with -A or loaded with default packages, its test fails:

============================OUTPUT START==============================

#I  RunPackageTests("automgrp", "1.3", "tst/testall.tst", "auto");
 ���������������������������   GAP 4.dev of today
 ���  GAP  ���   https://www.gap-system.org
 ���������������������������   Architecture: x86_64-pc-linux-gnu-default64-kv5
 Configuration:  gmp 6.0.0, GASMAN, readline
 Loaded workspace: wsp.g
 Packages:   ACE 5.2, AClib 1.3, Alnuth 3.1.0, AtlasRep 1.5.1, 
             AutoDoc 2018.09.20, AutomGrp 1.3, AutPGrp 1.10, Browse 1.8.8, 
             Carat 2.2.2, CRISP 1.4.4, Cryst 4.1.17, CrystCat 1.1.8, 
             CTblLib 1.2.2, FactInt 1.6.2, FGA 1.4.0, FR 2.4.5, GAPDoc 1.6.1, 
             GBNP 1.0.3, IO 4.5.4, IRREDSOL 1.4, LAGUNA 3.9.0, lpres 1.0.0, 
             nq 2.5.3, Polenta 1.3.8, Polycyclic 2.14, PrimGrp 3.3.1, 
             RadiRoot 2.8, ResClasses 4.7.1, SmallGrp 1.3, Sophus 1.24, 
             SpinSym 1.5, TomLib 1.2.6, TransGrp 2.0.4, utils 0.58
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-master-test/GAPCOPT\
S/64build/GAPTARGET/packages/label/kovacs/GAP-master-snapshot/pkg/automgrp/tst\
/testall.tst:18
# Input is:
Read(Filename(DirectoriesLibrary("pkg/automgrp/tst"), "testall.g"));
# Expected output:
Testing automgrp package

Parsing automaton string  done
Groups  done
Semigroups  done
Multiplication in groups  done
Multiplication in self-similar groups  done
Multiplication in semigroups  done
Multiplication in self-similar semigroups  done
Rewriting systems  done
Rewriting systems self-sim  done
Decompose  done
Order  done
Contracting groups  done
Iterator  done
Miscellaneous  done
SelfSim  done
Examples from manual  done
RWS 1  done
Automaton  done

All 6480 tests passed
# But found:
Testing automgrp package

Parsing automaton string  done
Groups  done
Semigroups  done
Multiplication in groups  done
Multiplication in self-similar groups  done
Multiplication in semigroups  done
Multiplication in self-similar semigroups  done
Rewriting systems  done
Rewriting systems self-sim  done
Decompose  done
Order  done
Contracting groups  done
Iterator  done
Miscellaneous  done
SelfSim Error, recursion depth trap (5000)
########
automgrp
msecs: 5217
#I  Errors detected while testing package automgrp 1.3
#I  using the test file `tst/testall.tst'
#I  RunPackageTests("automgrp", "1.3", "tst/testall.tst", "auto"): runtime 
5957
============================OUTPUT END================================

Second, with all packages loaded the test of automgrp crashes at all. When I call

make testpackage PKGNAME=automgrp

it shows

Testing automgrp 1.3, test=/circa/scratch/gap-jenkins/workspace/GAP-master-test/GAPCOPTS/64build/GAPTARGET/packages/label/kovacs/GAP-master-snapshot/pkg/automgrp/tst/testall.tst, all packages=true
Error, Integer operations: <divisor> must be nonzero in
  result[i] := left[i] mod right[i]
 ; at /circa/scratch/gap-jenkins/workspace/GAP-master-test/GAPCOPTS/64build/GA\
PTARGET/packages/label/kovacs/GAP-master-snapshot/lib/list.gi:3516 called from

fingolfin commented 6 years ago

Also, how do you measure those diffs? I only see like 5 or so with automgrp 1.3.1 and testinstall.

olexandr-konovalov commented 6 years ago

@fingolfin please see log file attached to compare: log.txt

olexandr-konovalov commented 6 years ago

State as of today:

testinstall: 15 failures in 4 of 220 files
teststandard: 19 failures in 6 of 255 files
testbugfix: 13 failures in 8 of 392 files (see e.g. https://travis-ci.org/gap-system/gap-docker-master-testsuite/jobs/439661724)

olexandr-konovalov commented 6 years ago

I've noticed that Travis tests set to terminate when GAP runs out of memory, so you can't see 15 diffs there. I am pasting them from the Jenkins log below:

1)

########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-pkg-update-master-q\
uicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/install/label/kovacs/GAP-pkg-up\
date-master-snapshot/tst/testinstall/algmat.tst:156
# Input is:
cen:= Centralizer( a, GeneratorsOfAlgebra( a )[1] );
# Expected output:
<algebra of dimension 12 over GF(3)>
# But found:
Error, reached the pre-set memory limit
(change it with the -o command line option)
########

2)

########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-pkg-update-master-q\
uicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/install/label/kovacs/GAP-pkg-up\
date-master-snapshot/tst/testinstall/mgmring.tst:19
# Input is:
centre:= Centre( rm );
# Expected output:
<algebra-with-one of dimension 3 over GF(3)>
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `SubNearRingBySubgroupNC' on 2 arguments
########

3)

########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-pkg-update-master-q\
uicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/install/label/kovacs/GAP-pkg-up\
date-master-snapshot/tst/testinstall/opers/IsSolvableGroup.tst:33
# Input is:
B := SylowSubgroup(H, 13);; G := SemidirectProduct(B, A);;
# Expected output:
# But found:
Error, recursion depth trap (5000)
########

4)

########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-pkg-update-master-q\
uicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/install/label/kovacs/GAP-pkg-up\
date-master-snapshot/tst/testinstall/vspchom.tst:457
# Input is:
Random( endo ) in endo;
# Expected output:
true
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `Gamma' on 1 arguments
########

This is less than 15 - I believe the rest is caused by the domino effect.

olexandr-konovalov commented 6 years ago

Did fresh pull from master and installed packages-master.tar.gz. All four above reproducible by loading all packages and reading testinstall.g, with the default assertion level.

olexandr-konovalov commented 6 years ago

4th diff is caused by interaction with SONATA:

gap> endo:=End( GF(3), GF(27) );
End( GF(3), GF(3^3) )
gap> Random( endo ) ;
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `Gamma' on 1 arguments at /Users/alexk/GITREPS/gap/lib/methsel2.g:250 called from
Gamma( nr ) at /Users/alexk/GITREPS/gap/pkg/sonata-2.9.1/lib/grptfms.gi:511 called from
<function "unknown">( <arguments> )
 called from read-eval loop at *stdin*:9
type 'quit;' to quit to outer loop
brk>

However, in a clean session loading SONATA does not break the example. The problem occurs in both cases - whenever LOOPS is loaded before SONATA or after.

Sonata indeed has

InstallMethod(
    Random,
    "Random for nearrings with known additive group",
    true,
    [IsNearRing and IsTransformationNearRing],
    0,
  function ( nr )
    return GroupGeneralMappingByGroupElement( Gamma(nr), Random( GroupReduct(nr) ) );
  end );

and endo matches the filter, but unless LOOPS (with OnlyNeeded option to avoid loading more packages) is loaded, that method from SONATA is never called...

olexandr-konovalov commented 5 years ago

Progress - the new release of FR has been published today (thanks @laurentbartholdi). I've tried make testinstall with currently picked up packages+this release of FR+current clone of LOOPS. This eliminates almost all diffs, and I hope that a new release of LOOPS containing the fix from https://github.com/gap-packages/loops/issues/5 will appear soon with @nagygp or me publishing it. After that, we will have to deal with the infinite recursion in

########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-pkg-update-master-q\
uicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/install/label/kovacs/GAP-pkg-up\
date-master-snapshot/tst/testinstall/opers/IsSolvableGroup.tst:33
# Input is:
B := SylowSubgroup(H, 13);; G := SemidirectProduct(B, A);;
# Expected output:
# But found:
Error, recursion depth trap (5000)
########

and also with

########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-pkg-update-master-q\
uicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/install/label/kovacs/GAP-pkg-up\
date-master-snapshot/tst/testinstall/grp/basic.tst:283
# Input is:
F:=FunctionField(GF(3),["t"]);
# Expected output:
FunctionField(...,[ t ])
# But found:
<field in characteristic 3>
########

(the latter may be new and not coming from this issue).

olexandr-konovalov commented 5 years ago

New Loops release has been published and is now included in packages-master.tar.gz archive. With it we have 4 diffs in testinstall with all packages loaded (https://travis-ci.org/gap-system/gap-docker-master-testsuite/jobs/451398298) and 6 in testbugfix (https://travis-ci.org/gap-system/gap-docker-master-testsuite/jobs/451398301), all coming from the recursion depth trap.

fingolfin commented 5 years ago

The semidirect product method issue listed under https://github.com/gap-system/gap/issues/2818#issuecomment-421863573 still needs to be resolved. I just looked at that; it is caused by the rank of IsFinite and IsGroup increasing from 47 to 71 with all packages loaded. While looking at the causes for that, by using ShowImpliedFilters(IsGroup and IsFinite);, I noticed that in particular there still is at least one incorrect implication being add: IsComponentObjectRep is now implied by IsGroup and IsFinite, which is of course nonsense.

The rank of IsGroupHomomorphism also increased, and this seems to be due to yet another bogus implication IsGroupHomomorphism => IsNearAdditiveElement being added.

To track down which packages are at fault, I used this GAP script:

pkgs := RecNames( GAPInfo.PackagesInfo );;
check:=function()
  Assert(0, RankFilter(IsGroupHomomorphism) < RankFilter(IsGroupHomomorphism and IsNearAdditiveElement));
  Assert(0, RankFilter(IsGroup and IsFinite) < RankFilter(IsGroup and IsFinite and IsComponentObjectRep));
end;
check();
for pkg in pkgs do
  #if pkg in ["xmod", "guava"] then continue; fi;
  Print("Loading ", pkg, "\n");
  LoadPackage(pkg);
  check();
od;

Turns out the first issue is caused by xmod or one of the packages it loads; digging deeper, I eventually narrowed it down to the Semigroups package: this code is bad:

InstallTrueMethod(IsEnumerableSemigroupRep, IsGroup and IsFinite);

Pining @james-d-mitchell @wilfwilson

The second issue is caused by sonata, via these bad implications:

InstallTrueMethod( IsNearRingElement, IsMapping );
InstallTrueMethod( IsNearAdditiveElementWithInverse, IsGeneralMapping );

fingolfin commented 5 years ago

"Fixing" those two issues in a hackish way (i.e. just removing the InstallTrueMethod calls, which of course is not correct), also fixes the infinite recursion bug in SemidirectProduct; but of course that method still should be fixed "properly", by replacing the hard coded -20 with something more appropriate dynamic.

fingolfin commented 5 years ago

Sorry, I had a copy&paste mistake in my post above regarding the faulty line in semigroups; I fixed it there now, but to avoid confusion for people who read the email notifications, this is the actual "bad" line:

InstallTrueMethod(IsEnumerableSemigroupRep, IsGroup and IsFinite);

There are more similar issues, though, e.g. these are also bad:

InstallTrueMethod(IsEnumerableSemigroupRep, IsFpSemigroup and IsFinite);
InstallTrueMethod(IsEnumerableSemigroupRep, IsFpMonoid and IsFinite);

and probably all involving InstallTrueMethod(IsEnumerableSemigroupRep

wilfwilson commented 5 years ago

Thanks for the information @fingolfin, and for creating the Semigroups package issue.

ThomasBreuer commented 5 years ago

Concerning the latest examples of bad implications: I think that filters created with DeclareRepresentation should never get implied from other filters via InstallTrueMethod, thus we could signal an error when someone attempts to install such an implication. (Of course one can create a hierarchy of filters that denote representations of objects, the second argument of DeclareRepresentation is intended for that.)

fingolfin commented 5 years ago

@ThomasBreuer I agree! In fact, to locate the offending InstallTrueMethod calls, I added a check to InstallTrueMethod to report any calls with tofilt implying IsComponentObjectRep. It turns out that the GAP library also does it, for IsHandledByNiceBasis, which is why my code ended up a bit messy and hackish to silence all reports about that. Definitely would be useful to add such a check in general though. And perhaps also an IsImpliedBy(filt1, filt2)tester.

ThomasBreuer commented 5 years ago

@fingolfin I will prepare a pull request for the new feature that no implications to representation filters are allowed.

UPDATE: Thomas submitted PR #3006

olexandr-konovalov commented 5 years ago

https://github.com/gap-system/gap/pull/2977 helped a lot to the core system tests when they are run with all packages loaded. However, there are still some packages that had runnable tests before method reordering but failing tests now. They can be seen at https://travis-ci.org/gap-system/gap-docker-pkg-tests-master (I deliberately did not transfer them to the staging tests, to make that visible).

olexandr-konovalov commented 5 years ago

Furthermore, all but one tests https://travis-ci.org/gap-system/gap-docker-master-testsuite/ now pass, and the failing one (e.g. https://travis-ci.org/gap-system/gap-docker-master-testsuite/jobs/453280130) trips over reesmat.tst (not observable in Jenkins?!). Note also an unrelated issue - children.tst triggers a lot of locale warnings; any hints how to avoid that?

perl: warning: Falling back to the standard locale ("C").
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LANG = "en_GB.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
       0 ms (0 ms GC) and 2.54MB allocated for processes/children.tst
testing: /home/gap/inst/gap-master/tst/teststandard/reesmat.tst
Panic in src/sysmem.c:438: will not extend workspace above -K limit!

olexandr-konovalov commented 5 years ago

Status update: I have moved all packages with failing tests in the GAP master branch to the staging build - see commit message under https://github.com/gap-system/gap-docker-pkg-tests-master/commit/08d5b9778bba5534b6bd67c2fb9b0db2dc31b581 for the list of 10 packages and links to individual commit messages with further details. Half of these seem to be caused by other problems and not by method reordering. However, automgrp, grpconst, polycyclic, RCWA and possibly profiling are impacted.

fingolfin commented 5 years ago

Another affected package: https://github.com/gap-packages/numericalsgps/issues/25

UPDATE: Resolves in version Version 1.2.1 of that package

fingolfin commented 5 years ago

I went through this issue and hid a lot of comments which seemed to be resolved or otherwise outdated, so that the stuff that still needs work stands out. As far as I could determine, we are in good shape, only a few things are left:

the automgrp package still has an infinite recursion in its test suite (regardless of which packages are loaded) -- however, that may not even be related to the issue here. Unfortunately, this package is not hosted on GitHub (but rather on SourceForge), so no PR to fix it can be submitted, and there is no issue tracker; that only leaves emailing back and forth with the authors. Anyway, I have now emailed one of the authors (with CC to @alex-konovalov) and sent them a fix.
we are still waiting for https://github.com/gap-packages/Semigroups/issues/556 to be resolved.
the RCWA tests seem to hang (see e.g. https://travis-ci.org/gap-infra/gap-docker-pkg-tests-master-devel/jobs/580038005) in some cases, which may be related to this. I am looking into this.

gap-system / gap

Test failures due to method re-ordering #2818

2869 reduces the number of diffs a bit further, but does not seem to resolve the issue completely yet. More details tomorrow.