FR package broken in stable-4.11 branch

[olexandr-konovalov]

I am afraid FR package is broken by some changes in the master branch. First time observed in https://travis-ci.org/gap-infra/gap-docker-pkg-tests-master/jobs/519063953 11 days ago:

============================OUTPUT START==============================
#I  RunPackageTests("fr", "2.4.6", "tst/testall.g", "auto");
 ┌───────┐   GAP 4.dev of today
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-default64-kv6
 Configuration:  gmp 6.1.2, GASMAN, readline
 Loaded workspace: wsp.g
 Packages:   ACE 5.2, AClib 1.3.1, Alnuth 3.1.0, AtlasRep 1.5.1, 
             AutoDoc 2019.02.22, AutPGrp 1.10, Browse 1.8.8, Carat 2.2.3, 
             CRISP 1.4.4, Cryst 4.1.18, CrystCat 1.1.8, CTblLib 1.2.2, 
             FactInt 1.6.2, FGA 1.4.0, FR 2.4.6, GAPDoc 1.6.2, GBNP 1.0.3, 
             IO 4.6.0, IRREDSOL 1.4, LAGUNA 3.9.2, lpres 1.0.1, nq 2.5.4, 
             Polenta 1.3.8, Polycyclic 2.14, PrimGrp 3.3.2, RadiRoot 2.8, 
             ResClasses 4.7.2, SmallGrp 1.3, Sophus 1.24, SpinSym 1.5.1, 
             TomLib 1.2.7, TransGrp 2.0.4, utils 0.61
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
Architecture: x86_64-pc-linux-gnu-default64-kv6
testing: /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/chapter-12.tst
      88 ms (88 ms GC) and 63.4KB allocated for chapter-12.tst
testing: /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/chapter-3.tst
     540 ms (128 ms GC) and 71.7MB allocated for chapter-3.tst
testing: /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/chapter-4.tst
   15336 ms (1700 ms GC) and 1.68GB allocated for chapter-4.tst
testing: /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/chapter-5-a.tst
    4956 ms (696 ms GC) and 618MB allocated for chapter-5-a.tst
testing: /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/chapter-5-b.tst
    1492 ms (216 ms GC) and 177MB allocated for chapter-5-b.tst
testing: /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/cp.tst
########> Diff in /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/cp.tst:67
# Input is:
IsConjugate(GrigorchukGroup,pairs[1][1][1],pairs[1][1][2]);
# Expected output:
#I  Init FRBranchGroupConjugacyData
#I  Finished Init FRBranchGroupConjugacyData
true
# But found:
#I  Init FRBranchGroupConjugacyData
Error, recursion depth trap (5000)
########
########> Diff in /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/cp.tst:73
# Input is:
SetFRBranchGroupConjugacyData(GuptaSidkiGroup,
 rec(initial_conj_dic:=NewDictionary([One(GuptaSidkiGroup),One(GuptaSidkiGroup\
)],true),
    Branchstructure:=BranchStructure(GuptaSidkiGroup),
    RepSystem:=List(~.Branchstructure.group,x->PreImagesRepresentative(~.Branc\
hstructure.quo,x)))
 );
# Expected output:
# But found:
Error, recursion depth trap (5000)
########
########> Diff in /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/cp.tst:78
# Input is:
CallFuncList(function(a,t) 
            local G,D,g,h;
            G:= GuptaSidkiGroup;
            D:= FRBranchGroupConjugacyData(G).initial_conj_dic;
            for g in [a,a^2,t,t^2] do
              for h in [a,a^2,t,t^2] do
               if g<>h then
                AddDictionary(D,[g,h],[]);
               fi;
              od;
            od;
            AddDictionary(D,[a,a],[One(G),a,a^2]);
            AddDictionary(D,[a^2,a^2],[One(G),a,a^2]);
            AddDictionary(D,[t,t],[One(G),,,t,,,t^2]);
            AddDictionary(D,[t^2,t^2],[One(G),,,t,,,t^2]);
          end,GeneratorsOfGroup(GuptaSidkiGroup)
  );
# Expected output:
# But found:
#I  Init FRBranchGroupConjugacyData
Error, recursion depth trap (5000)
########
########> Diff in /home/gap/inst/gap-master/pkg/fr-2.4.6/tst/cp.tst:96
# Input is:
IsConjugate(GuptaSidkiGroup,GuptaSidkiGroup.1^GuptaSidkiGroup.2,GuptaSidkiGrou\
p.1);
# Expected output:
true
# But found:
#I  Init FRBranchGroupConjugacyData
Error, recursion depth trap (5000)
########
    3592 ms (688 ms GC) and 396MB allocated for cp.tst
-----------------------------------
total     26004 ms (3516 ms GC) and 2.92GB allocated
              4 failures in 1 of 6 files
#I  Errors detected while testing
============================OUTPUT END================================

Also reported at gap-packages/fr#33

[fingolfin]

Using etc/bisect.sh, I determined that this regression was introduced by commit 7ea1f43 from PR #3397 by @hulpke

[hulpke]

Using etc/bisect.sh, I determined that this regression was introduced by commit 7ea1f43 from PR #3397 by @hulpke

As #3397 just replaces a ClosureSubgroup by ClosureGroup, this might be triggering it, but cannot really be the source of the error.

[fingolfin]

Just to clarify, with "regression was introduced by", I did not mean to imply that the commit / PR by @hulpke I pointed out are at fault -- indeed, I agree with @hulpke that this is almost certainly not the case. Nevertheless, with that the commit, the regression first showed up, hence my wording. In any case, I will phrase this more carefully in the future to avoid misunderstandings, sorry for that!

Knowing the first commit in gap with which the regression first appeared still is helpful in narrowing down its cause.

[fingolfin]

Looking a bit closer, the infinite recursion involves an orbit stabilizer computation, and a ClosureSubgroupNC call in it, and only happens if the assertion level is high enough.

And this is in turn caused by the statement Assert(2,IsSubset(Parent(G),obj)); added by @hulpke's PR... so perhaps that PR is to blame, after all...

gap> LoadPackage("fr", false);
true
gap> SetAssertionLevel(2);
gap> n := InfoLevel(InfoFR);;
gap> sc_grps := [];;
gap> for alph in [[1,2],[1..3]] do
>       for fil in [IsFRElement,IsFiniteStateFRElement,IsBoundedFRElement,IsFinitaryFRElement] do
>       Add(sc_grps,FullSCGroup(alph,fil));
>    od;
> od;
gap> grps := [GrigorchukGroup,AleshinGroup,GuptaSidkiGroup];;
gap> pairs := [];;
gap> for grp in grps do
>       pairs_group:=[];
>       n := Size(GeneratorsOfGroup(grp));
>       Add(pairs_group,[grp.(2 mod n +1)^grp.(1 mod n +1),grp.(2 mod n +1)^grp.(3 mod n +1)]);
>       Add(pairs_group,[grp.(1 mod n +1)^grp.(1 mod n +1),grp.(2 mod n +1)^grp.(3 mod n +1)]);
>       Add(pairs,pairs_group);
> od;
gap> pairs_sc := [[AsGroupFRElement(AddingElement(2)),AsGroupFRElement(AddingElement(2))^-1],[AsGroupFRElement(AddingElement(3)),AsGroupFRElement(AddingElement(3))^-1],[AsGroupFRElement(AddingElement(2)),(AsGroupFRElement(AddingElement(2)))^FRElement([[[1],[AddingElement(2)]]],[()],[1])]];;
gap> SetIsBranched(GrigorchukGroup,true);
gap> IsConjugate(GrigorchukGroup,pairs[1][1][1],pairs[1][1][2]);
#I  Init FRBranchGroupConjugacyData
Error, recursion depth trap (5000) in
  DomainForAction( d, acts, act ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:1391 called from
OrbitStabilizerAlgorithm( G, false, false, gens, acts, rec(
    pnt := d,
    act := act,
    onlystab := true ) ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2912 called from
orbish( G, pnt, gens, acts, act ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gd:858 called from
CallFuncList( StabilizerFunc, arg ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2876 called from
Stabilizer( G, v ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2450 called from
StabilizerImage( G, i ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2403 called from
...  at *stdin*:21
you may 'return;'
brk> Where(30);
OrbitStabilizerAlgorithm( G, false, false, gens, acts, rec(
    pnt := d,
    act := act,
    onlystab := true ) ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2912 called from
orbish( G, pnt, gens, acts, act ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gd:858 called from
CallFuncList( StabilizerFunc, arg ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2876 called from
Stabilizer( G, v ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2450 called from
StabilizerImage( G, i ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2403 called from
func( elm ) at /Users/mhorn/Projekte/GAP/gap.github/lib/coll.gi:1565 called from
ForAll( AlphabetOfFRSemigroup( G ), function ( i )
      return IsSubgroup( StabilizerImage( G, i ), G );
  end ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2403 called from
IsRecurrentFRSemigroup( G ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2416 called from
IsLevelTransitive( G ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:1080 called from
IsFinite( G ) at /Users/mhorn/Projekte/GAP/gap.github/lib/grp.gi:3472 called from
IsSubset( Parent( G ), obj ) at /Users/mhorn/Projekte/GAP/gap.github/lib/grp.gi:2407 called from
ClosureSubgroupNC( stb, sch ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:1425 called from
OrbitStabilizerAlgorithm( G, false, false, gens, acts, rec(
    pnt := d,
    act := act,
    onlystab := true ) ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2912 called from
orbish( G, pnt, gens, acts, act ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gd:858 called from
CallFuncList( StabilizerFunc, arg ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2876 called from
Stabilizer( G, v ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2450 called from
StabilizerImage( G, i ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2403 called from
func( elm ) at /Users/mhorn/Projekte/GAP/gap.github/lib/coll.gi:1565 called from
ForAll( AlphabetOfFRSemigroup( G ), function ( i )
      return IsSubgroup( StabilizerImage( G, i ), G );
  end ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2403 called from
IsRecurrentFRSemigroup( G ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2416 called from
IsLevelTransitive( G ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:1080 called from
IsFinite( G ) at /Users/mhorn/Projekte/GAP/gap.github/lib/grp.gi:3472 called from
IsSubset( Parent( G ), obj ) at /Users/mhorn/Projekte/GAP/gap.github/lib/grp.gi:2407 called from
ClosureSubgroupNC( stb, sch ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:1425 called from
OrbitStabilizerAlgorithm( G, false, false, gens, acts, rec(
    pnt := d,
    act := act,
    onlystab := true ) ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2912 called from
orbish( G, pnt, gens, acts, act ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gd:858 called from
CallFuncList( StabilizerFunc, arg ) at /Users/mhorn/Projekte/GAP/gap.github/lib/oprt.gi:2876 called from
Stabilizer( G, v ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2450 called from
StabilizerImage( G, i ) at /Users/mhorn/Projekte/GAP/gap.github/pkg/fr-2.4.6/gap/group.gi:2403 called from
func( elm ) at /Users/mhorn/Projekte/GAP/gap.github/lib/coll.gi:1565 called from
...  at *errin*:1
brk>

[hulpke]

@fingolfin
OK, so what happens is that code (newly) contains an assertion that in this particular case actually is expensive (or impossible) to check. What we could so is either:

1. Ignore it (or require of packages only to test at assertion level 0).

2. remove the assertion (or rank it higher) so the automated test does not trip. This way we lose the benefit of the assertion for general tests.

3. Have the package avoid the particular test (either by changing its code or its test files)

4. Add an option to skip the assertion in particular settings.

5. Edit the test file to deliberately set the assertion level lower than two (as the package cannot deal with the library assertion).

I have used both 4 and 5 in similar circumstances.

[olexandr-konovalov]

I am not in favour of options 1,2,3 and 5, that leaves me with preferring option 4...

[hulpke]

I have added a "noassert" option in #3425, that implements option 4 I sketched above.

That is in FR, the problematic closure call should be done with an added
:noassert
option added.

[fingolfin]

The problem with options 3, 4 and 5 is that we made a change that broke the tests of a package which worked fine before; now we are asking the package author (@laurentbartholdi ) to make a change and release a new version to deal with what we did. That's not quite optimal... Normally, I'd expect that we'd at least submit a PR to the package author making that change for them. At the very, very least, we should talk to them about this.

[olexandr-konovalov]

Yes, sorry that I was not specific enough. By "Add an option to skip the assertion in particular settings" I did not mean that the user has to specify a command line option - I had a hope (maybe wrongly) that one could detect programmatically in which setting we operate and omit an assertion if necessary. Looking again at the code, I am not even sure that this is doable. OTOH, the assertion is new, added 20 days ago, and it's not a part of the fix made in #3397, so maybe removing it completely will not be deteriorating after all...

[laurentbartholdi]

There are 3 levels the consider: - package user - package internals - gap internals I could rather have such changes at the deepest level. Or perhaps we need a 'NC' version of some commands to avoid falling into recursions; or extra filters that are set to trigger finer methods?

[olexandr-konovalov]

So, #3425 has been merged, with "noassert" option added in b6e34f0. Now FR should make use of it - @laurentbartholdi will you be able to do this and publish a new release, please?

[olexandr-konovalov]

Update: this still waits for the new FR release. I have just submitted PR gap-packages/fr#34 attempting to fix the problem in FR.

[fingolfin]

It seems FR works with GAP 4.11.1 and with GAP master (and thus the upcoming 4.12).