Implement GAP's ShallowCopy and StructuralCopy resp. Julia' copy and deepcopy; and, closely related, handle (GAP's) mutability

[fingolfin]

Right now, on the GAP side, all T_JULIA wrappers are marked as immutable. This allows us to provide trivial copying operations for those objects. But of course this unsatisfying, and has immediate undesirable side effects; e.g. we can't implement julia_list[idx] := val; on the GAP level, as the kernel helpfully prints a common error message for assigning to immutable objects.

So, we need something better, but there are pitfalls... In a first iteration, we could switch to the opposite, and mark all T_JULIA objects, and leave it to Julia to figure out the details. (A more clever implementation is difficult, as the concept of "mutability" differs between GAP an Julia: In GAP, it is recursively defined, in Julia, it is not).

Anyway, for copying, here are some relevant links: https://docs.julialang.org/en/v1/base/base/#Base.copy and https://docs.julialang.org/en/v1/base/base/#Base.deepcopy for the Julia side (there is also an undocumented copymutable). Source code: https://github.com/JuliaLang/julia/blob/master/base/deepcopy.jl

On the GAP side, we need to provide (resp. improve) our own implementations for handlers in these function arrays:

• IsMutableObjFuncs (could set to AlwaysYes for now)
• (perhaps MakeImmutableObjFuncs, but probably pointless / not possible)
• IsCopyableObjFuncs
• ShallowCopyObjFuncs
• CopyObjFuncs
• CleanObjFuncs

The Julia copy and deepcopy method for GAP.FFE just can be the identity (and since this is a primitive data type, am guessing that Julia already provides them for us).

I imagine that ShallowCopy of T_JULIA wrappers on the GAP side is pretty easy: we use Julia's copy to shallow copy the wrapped object. If the result is identical, we also don't make a copy of the wrapper (so just return self;). Otherwise, wrap the copied Julia object into a new T_JULIA wrapper.

For deep / structural copies, more work is needed: On the Julia side, deepcopy keeps track of already copied objects via an IdDict (similar to what our copying code for HPC-GAP does), while GAP does so by temporarily modifying the object being copied to store a forwarding pointer. We need to bridge these two concepts.

A first iteration without modifying the GAP kernel could look like this: On the Julia side, we provide a deepcopy_internal method for MPtr (and for FFE, but that one can just return the input). This function stores the stackdict::IdDict passed to it in a global (resp. thread local) variable XYZ for later reference. Then, we call GAP's CopyObj kernel function (as CopyObj(obj, 1) as usual. The global XYZ comes into play in the CopyObjFuncs for T_JULIA objects, which needs to call deepcopy_internal(wrapped, XYZ) on the wrapped object. Of course if XYZ is not yet set, it needs to be set to an empty IdDict first.

One iffy issue with this is when to clear the XYZ variable. I am actually not quite sure how to solve that right now.

An alternative approach, is to modify the GAP copying functions in the kernel to take stackdict::IdDict as an extra argument (and then they could use it instead of the forwarding pointers, too, somewhat similar to what we do in HPC-GAP). But this cannot reasonably be implemented in our package, it really needs modifications to the GAP kernel.

[fingolfin]

We might actually want to enable the HPC-GAP variant for object copying in our Julia version of GAP, too. Possibly with some modifications -- we could modify hpc/traverse.c to use a Julia IdDict instead of a GAP OBJ_MAP.

However, the code in hpc/traverse.c is (or at least was) notoriously buggy and not tested enough, and while I improved it a bit over the years, I never took time to really sit down and toughen it up, nor did anybody else.

[fingolfin]

While a full fix for this is difficult, we might be able to at least handle the case where deepcopy if called on "basic" GAP inputs which do not refer to Julia objects: basically by installing kernel functions for T_JULIA which return an error; and then simply delegating to GAP's StructuralCopy -- if at any point there is a nested T_JULIA, we'll trigger an error and are safe.

That should help with many basic needs, e.g. when one needs a deepcopy of a GAP group (I think @GDeFranceschi may have need for this)

[ThomasBreuer]

@fingolfin I do not understand the example of a deepcopy of a GAP group.

Both ShallowCopy and StructuralCopy return the input when called with a group object in GAP. I think that getting an independent exact copy of such a GAP object is currently not supported (and apparently not needed up to now) in GAP.

What did I misunderstand?

[fingolfin]

I think part of the problem here is that it is not 100% clear what deepcopy really should do for GAP objects: deepcopy only returns an "independent exact copy" for "mutable Julia objects". For immutable ones, it may return the original object itself. E.g.:

julia> t = (1,2,3)
(1, 2, 3)

julia> t2 = deepcopy(t)
(1, 2, 3)

julia> t === t2
true

As an aside, that does not necessarily mean that t and t2 "point" to the same memory; indeed, they might only be stack allocated, or might not even exist for real (optimization might prevent them from ever being actually "materialized" in compiled code); Julia does not allow computing a pointer to such objects:

julia> pointer_from_objref(t)
ERROR: pointer_from_objref cannot be used on immutable objects

Anyway: From a top level, this matches quite well what GAP does: there, StructuralCopy on an immutable objects x also returns x. However, in GAP and Julia, "immutable object" means different things... So, the big open question is, what is the appropriate action when calling deepcopy on GAP objects???

• deepcopy on a GAP internal object that is immutable (more or less all with TNUm between FIRST_CONSTANT_TNUM and LAST_CONSTANT_TNUM, such as large ints / booleans / permutations / ..., should probably return the original object
• for mutable lists or records, a copy shall be made
• for immutable lists / records... it depends on the answer for the next point...
• what about e.g. group objects, which are immutable, but which may contain pointers to a mutable objects???

For GAP, there is indeed no standard way to "clone" a group. (Likewise, there is no good way to serialize and deserialize them in general (an issue we need to address at some point, but I digress), which the deepcopy documentation references...

I see two options:

1. we treat deepcopy as equivalent to StructuralCopy for these objects (i.e., G is mapped to itself)
2. we implement a custom "deepcopy" which tries to create a new group and copy over as much information as we can, recursively (but beware of doing this "completely", else we end up with broken "halfcopies" that still have outdated pointers to objects they shouldn't have)

To decide which we want, we have to determine what we need. For the uses in Oscarjl so, far, I think option 1 might be fine -- perhaps @GDeFranceschi can comment on this, though?

[GDeFranceschi]

The issue came out when I tried to compute deepcopy(x) where x is a variable of type MatrixGroupElem, having a field :X of type GapObj.
An eventual example of a situation where such deepcopy is needed is the following:
Suppose we have a group G and elements x,y of G (this means that x.parent and y.parent equal G). We want to define H = sub(G,[x,y]). The group H has a field H.gens (the generators of H). It is sensible to set H.gens as [x,y], where x and y are the original elements in G with the only difference that the parent group is H instead of G. Since we do not want to modify the original values of x and y, we need a deepcopy of x and y to assign to H.gens. The result is something like

H.gens = [deepcopy(x),deepcopy(y)]
for z in H.gens z.parent = H end

This is not possible since x has a GapObj field, so deepcopy(x) crashes. At the moment, I solved the problem by defining the "new" x and y from zero and assigning to their fields the same values of the original x and y (with the exception of x.parent and y.parent, of course).
Anyway, for me it is not a big issue, it just means 3-4 more lines of code. I do not know whether other people had similar needs.

[ThomasBreuer]

The example shows that a deepcopy method for GapObj objects is necessary.
And I think the situation fits to option 1 proposed by @fingolfin.

[ThomasBreuer]

I do not see problems with the definition that deepcopy for GapObj delegates to GAP's StructuralCopy.
For immutable objects in the sense of GAP, the object itself is returned; this is o.k. also if the GAP object A contains references to a mutable subobject B (for example, an extendible list of known Sylow subgroups stored in a GAP group), because it is not allowed to change the meaning of object A.
And for mutable GAP objects (lists, records, iterators, ...), StructuralCopy creates an independent new object, which is what one wants.

Things become more complicated when the mutable GAP object A stores a Julia object B as a subobject. My proposal would be that StructuralCopy for A has to call deepcopy for B, but perhaps I am missing something. (How can we achieve this behaviour of StructuralCopy?)

[fingolfin]

Implementing deepcopy for GAP objects pointing to Julia objects (which potentially point again to GAP objects, etc.) is tricky, I discuss this in the head post of this issue.

Hence my suggestion that to get started, we just provide a deepcopy (or rather deepcopy_internal) method for GapObj which delegates to StructuralCopy but no StructuralCopy method for T_JULIA objects. This way, one can at least deepcopy the "easy" cases, and gets an error for the rest.

I know in principle how to handle the general case (again, see the top post of this issue), but it's one of these tasks which are too big for one afternoon, so I think I'd really need another coding workshop to address this (similar for a many other issues with GAP.jl sigh).

[ThomasBreuer]

O.k., I can create a pull request for this partial solution (deepcopy for easy GapObj).

Would it --from the viewpoint of GAP-- be attractive to change the StructuralCopy mechanism, in a way that is compatible with Julia's deepcopy mechanism (perhaps exposed to the GAP level?), because this new mechanism can then be used also for the linearization of arbitrary GAP objects?