[GAP Forum] Segmentation Fault

[Frank Lübeck]

On Tue, Apr 13, 2010 at 08:11:34PM -0700, Justin Walker wrote:
> Dear Forum,
>
> I was fiddling with lists and tried the following, which resulted in a  
> segmentation fault:
>
> gap> l:=ListWithIdenticalEntries(6,[1,2,3]);;
> gap> l[1][1]:=l[3];;
> gap> l;
> [ [ ~[1], 2, 3 ], [ ~[2], 2, 3 ], [ ~[3], 2, 3 ], [ ~[4], 2, 3 ], [ ~[5], 
> 2, 3 ],
>   [ ~[6], 2, 3 ] ]
> gap> MakeImmutable(l);
>
> Boom!
>
> I gather that the result of the second assignment is to tie the list  
> into knots.  The following call then goes recursive and eventually blows 
> the stack (true?).
>
> I thought it worth reporting, in case it's fixable.

Dear Justin, dear Forum,

Thanks for this example, I'm a bit surprised that nobody reported this
before. A slightly shorter example is:

gap> l := [~]; # equivalent to:  l := [];; l[1] := l;
[ ~ ]
gap> MakeImmutable(l);
Segmentation fault

I tend to consider this as "feature" rather than a bug. But it should at
least be documented. 

GAP can only make a list immutable when all its entries are immutable.
MakeImmutable just recurses into the list and tries to make all entries
immutable first (if they are not already immutable). In the examples above 
this runs into an infinite recursion. 

This could be fixed. For example you see above that Print or View can deal
with the self-recursive structure. You can also make an immutable copy
of the object:

gap> l := [~];;
gap> l := Immutable(l);
[ ~ ]
gap> IsMutable(l);
false

But I think that MakeImmutable is intended to be very fast on newly 
created objects (which may be huge and have many subobjects). If we would
fix the reported problem, MakeImmutable would become much slower and we
would loose its speed advantage compared to Immutable. Therefore:
For self-recursive objects use don't use 'MakeImmutable', create a copy
with 'Immutable' instead.

Best regards,
  Frank

BTW: Self-recursive objects are not uncommon in GAP, e.g., a group
may contain a list of its conjugacy classes and each class points back to
the group it belongs to.  Or think of a tree structure where the nodes 
point back to the root.

-- 
///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,  ///
\\\                    52062 Aachen, Germany                          \\\
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De                        ///
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/           \\\