Test failures due to method re-ordering

[fingolfin]

[ 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:

1. Switch some methods from static rank adjustments to dynamic (in the GAP library and in packages)
2. Add a rank adjustment to some methods that don't have any right now
3. 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???
4. Perhaps there are other things we should do?

[fingolfin]

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

[fingolfin]

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]

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]

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.

[fingolfin]

The semidirect product method issue listed under #2818 (comment) 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]

"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]

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]

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

[ThomasBreuer]

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]

@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]

@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]

#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]

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]

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 There should be no implications to IsEnumerableSemigroupRep semigroups/Semigroups#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.