%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  weakptr.tex              GAP documentation               Steve Linton
%%
%H  @(#)$Id: weakptr.tex,v 4.11.2.1 2006/03/07 14:46:25 sal Exp $
%%
%Y  Copyright 1997,  The GAP Project
%%
%%  This file describes the use of weak pointers
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Weak Pointers}

This chapter describes the use of the kernel feature of *weak pointers*. This
feature is  intended    for use only   in  {\GAP}  internals,  and  is   *not
recommended* for use in {\GAP} packages,  user code,  or at the higher levels
of the library.

The GASMAN garbage collector is the part of the kernel that manages memory in
the users workspace.  It will  normally only reclaim  the storage used by  an
object when the object cannot be reached as a subobject  of any GAP variable,
or from any reference in the kernel.  We say that any link to object <a> from
object  <b>  ``keeps object <a>  alive'',  as long  as <b>  is  alive.  It is
occasionally convenient, however to have a link to an  object which *does not
keep   it alive*, and this  is  a weak pointer.   The  most common  use is in
caches, and similar structures, where it is only necessary to remember how to
solve problem x as long as some other link to x exists.

The  following section "Weak Pointer  Objects" describes the semantics of the
objects that contain weak pointers. Following sections describe the functions
available to manipulate them.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Weak Pointer Objects}

A  *weak pointer object* is  similar to a  mutable plain list, except that it
does  not  keep its subobjects alive   during a garbage collection.  From the
{\GAP} viewpoint this  means that its  entries may become unbound, apparently
spontaneously,  at  any   time.  Considerable care   is  therefore needed  in
programming with such an object.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{WeakPointerObj}\nolabel

\>WeakPointerObj( <list> )

`WeakPointerObj' returns  a  weak pointer object  which contains  the same
subobjects as <list>, that is it returns a *shallow* weak copy of <list>.

\beginexample
gap> w := WeakPointerObj( [ 1, , [2,3], fail, rec( a := 1) ] );
WeakPointerObj( [ 1, , [ 2, 3 ], fail, rec( a := 1 ) ] )
gap> GASMAN("collect");
gap> w;
WeakPointerObj( [ 1, , , fail ] )
\endexample

Note that `w' has failed to keep its  list and record subobjects alive during
the garbage    collection.  Certain subobjects, such  as   small integers and
elements of small finite fields, are not stored in  the workspace, and so are
not subject  to garbage collection, while certain  other objects, such as the
Boolean values, are always reachable from  global variables or the kernel and
so are never garbage collected.

Subobjects reachable without  going  through  a weak  pointer object  do  not
evaporate, as in:

\beginexample
gap> l := [1,2,3];;
gap> w[1] := l;;
gap> w;
WeakPointerObj( [ [ 1, 2, 3 ], , , fail ] )
gap> GASMAN("collect");
gap> w;                
WeakPointerObj( [ [ 1, 2, 3 ], , , fail ] )
\endexample

Note also  that the global  variables  `last', `last2' and `last3'  will keep
things alive -- this can be confusing when debugging.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Low Level Access Functions for Weak Pointer Objects}
\index{ElmWPObj}

\>SetElmWPObj(<wp>,<pos>,<val>)
\>UnbindElmWPObj(<wp>,<pos>)
\>ElmWPObj(<wp>, <pos>)
\>IsBOundElmWPObj(<wp>,<pos>)
\>LengthWPObj(<wp>)

The          functions           `SetElmWPObj(<wp>,<pos>,<val>)'          and
`UnbindElmWPObj(<wp>,<pos>)' set and unbind entries in a weak pointer object.

The function `ElmWPObj(<wp>, <pos>)' returns the element at position <pos> of
the weak pointer object <wp>, if there is one, and `fail' otherwise. A return
value of `fail' can thus arise either because (a)  the value `fail' is stored
at position <pos>, or (b) no value is stored  at position <pos>. Since `fail'
cannot   vanish in  a  garbage collection,   these   two cases can  safely be
distinguished by  a *subsequent* call to `IsBoundElmWPObj(<wp>,<pos>)', which
returns `true' if there is currently a value bound at  position <pos> of <wp>
and `false' otherwise.

Note that it  is  *not*  safe to write:   `if IsBoundElmWpObj(w,i)  then  x:=
ElmWPObj(w,i); fi;'  and treat `x' as  reliably containing a value taken from
`w', as a badly  timed garbage collection could  leave `x' containing `fail'. 
Instead use `x := ElmWPObj(w,i); if x \<> fail or IsBoundElmWPObj(w,i) then . 
. .'.

\beginexample
gap> w := WeakPointerObj( [ 1, , [2,3], fail, rec() ] );   
WeakPointerObj( [ 1, , [ 2, 3 ], fail, rec(  ) ] )
gap> SetElmWPObj(w,5,[]);
gap> w;
WeakPointerObj( [ 1, , [ 2, 3 ], fail, [  ] ] )
gap> UnbindElmWPObj(w,1);
gap> w;
WeakPointerObj( [ , , [ 2, 3 ], fail, [  ] ] )
gap> ElmWPObj(w,3);      
[ 2, 3 ]
gap> ElmWPObj(w,1);
fail
gap> 2;;3;;4;;GASMAN("collect"); # clear last etc.
gap> ElmWPObj(w,3);          
fail
gap> w;
WeakPointerObj( [ , , , fail ] )
gap> ElmWPObj(w,4);
fail
gap> IsBoundElmWPObj(w,3);
false
gap> IsBoundElmWPObj(w,4);
true
\endexample
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Accessing Weak Pointer Objects as Lists}

Weak pointer objects are members of `ListsFamily' and the categories `IsList'
and `IsMutable'.  Methods based  on  the low-level functions in  the previous
section, are  installed for the list  access operations,  enabling them to be
used as lists.    However, it is  *not recommended*  that  these be used   in
programming. They   are  supplied mainly as   a convenience  for  interactive
working, and   may not be   safe, since functions  and methods  for lists may
assume that after `IsBound(w[i])' returns true, access to `w[i]' is safe.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Copying Weak Pointer Objects}

A `ShallowCopy'  method is installed, which  makes a  new weak pointer object
containing the same objects as the original.

It is possible to apply `StructuralCopy'  to a weak pointer object, obtaining
a new weak  pointer object containing copies of  the objects in the original. 
This *may  not  be safe*  if a  badly timed garbage  collection occurs during
copying.

Applying `Immutable'  to a weak   pointer object produces an  immutable plain
list containing immutable copies of the objects contained in the weak pointer
object. An immutable weak pointer object is a contradiction in terms.
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The GASMAN Interface for Weak Pointer Objects}

The  key support for  weak  pointers is in   `gasman.c' and `gasman.h'.  This
document assumes  familiarity  with the rest of  the operation of  GASMAN.  A
kernel type (tnum) of   bags which are  intended  to act as weak  pointers to
their  subobjects must meet  three conditions.  Firstly, the marking function
installed for that tnum must  use  `MarkBagWeakly' for those subbags,  rather
than `MARK_BAG'.  Secondly,  before any access to  such a subbag, it must be
checked with `IS_WEAK_DEAD_BAG'. If that   returns true, then the subbag  has
evaporated in a recent garbage collection and must not be accessed. Typically
the reference to it should be removed. Thirdly, a *sweeping function* must be
installed for that tnum which copies the bag, removing all references to dead
weakly held subbags.

The  files `weakptr.c' and  `weakptr.h'  use this  interface  to support weak
pointer objects. Other objects with weak behaviour  could be implemented in a
similar way.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E