1(*
2    Title:      Weak references
3    Author:     David Matthews
4    Copyright   David Matthews 2008, 2015-16, 2019, 2020
5
6    This library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License version 2.1 as published by the Free Software Foundation.
9    
10    This library is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    Lesser General Public License for more details.
14    
15    You should have received a copy of the GNU Lesser General Public
16    License along with this library; if not, write to the Free Software
17    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18*)
19
20(* A weak reference or array contains option values.  The SOME variant of
21   the option must contain a reference.  This restriction is imposed because
22   they require pointer equality.  A weak reference or array behaves just like
23   a normal ref or array with one difference.  The garbage collector may set
24   a weak ref or the field of weak array to NONE if it currently contains
25   SOME r but r is not reachable other than through weak references.  The
26   one proviso is that if r is contained in the executable it is always
27   reachable.
28*)
29
30(**
31  The `Weak` structure contains functions for constructing 
32  *weak* references and arrays. A weak reference is a way of detecting 
33  when a resource is no longer in use and can be recovered. It is, in effect, 
34  a way of extending the concept of garbage-collection to user code.
35**)
36signature WEAK =
37sig
38    (** Constructs a weak reference.  **)
39    val weak: 'a ref option -> 'a ref option ref
40    (** Constructs an array containing weak references. **)
41    val weakArray: int * 'a ref option -> 'a ref option array
42    (** A lock and a condition variable that is broadcast when the garbage collector has recovered a *token*. **)
43    val weakLock: Thread.Mutex.mutex
44    and weakSignal: Thread.ConditionVar.conditionVar
45    (** Uses the reference without changing it, ensuring that it is reachable at that point. **)
46    val touch : 'a ref -> unit
47end;
48
49structure Weak: WEAK =
50struct
51    fun weak (v: 'a ref option): 'a ref option ref = RunCall.allocateWordMemory(0w1, 0wx60, v)
52    
53    fun weakArray(n: int, v: 'a ref option): 'a ref option array =
54    let
55        val () = if n < 0 orelse n >= Array.maxLen then raise Size else ()
56        val arr = RunCall.allocateWordMemory(Word.fromInt n, 0wx60, v)
57    in
58        arr
59    end
60
61    val weakLock = Thread.Mutex.mutex()
62    and weakSignal = Thread.ConditionVar.conditionVar()
63
64    (* touch is considered by the compiler as an access to the ref but doesn't
65       actually do anything with it.  The idea is that it ensures that when a ref
66       is used as a token that this will access the ref and avoid the weak
67       reference becoming set to NONE.  It's primarily there for long-term
68       security in the event that the compiler is sufficiently clever to
69       work out that something is no longer referenced. *)
70    val touch: 'a ref -> unit = RunCall.touch
71end;
72(**
73   The idea behind weak references is to allow user library code to recover resources 
74  when they are no longer in use. This is only relevant for resources, such as 
75  file descriptors, that exist outside the Poly/ML memory and need to be recovered.
76  
77  The garbage-collector recovers space in the heap by identifying cells that 
78  are reachable from *roots*, generally the stacks of threads, and treating 
79  everything else as garbage. This can be extended to external resources by associating 
80  a *token* with the resource. While the token is reachable the resource 
81  is considered to be in use. Once the token ceases to be reachable the resource 
82  can be recovered.
83  
84  A weak reference is used to detect when the token is no longer accessible. 
85  To make use of this the library code must allocate a normal reference value, 
86  the token, whenever it constructs or links to the external resource and include 
87  the token within the data it returns to the client code. The contents of the 
88  reference are not relevant; it can be a `unit ref`, 
89  what matters is the identity of the reference. When the library creates a token 
90  it makes an entry in its own data structure within a weak reference or array. 
91  That entry is set to `SOME token`. Note that the 
92  type of a weak reference is `'a ref option ref` 
93  i.e. it can only contain an option type holding a reference value.
94  
95  Provided the client code continues to use the resource and has a reachable 
96  pointer to the token there will be no change to the state. If, though, it discards 
97  the data associated with the resource and hence the pointer to the token the 
98  resource is considered to be released and the library may recover the resource. 
99  If the garbage collector detects that there are no other pointers to the token 
100  except the weak reference it will change the weak reference from `SOME token` to
101  `NONE`, so there are no longer  any pointers at all.
102  
103  To actually release the external resource the library must check the weak references 
104  or arrays within its own data structures and look for entries that have been 
105  set to `NONE`. Depending how the library code 
106  works it may be appropriate to do this synchronously whenever a request is made 
107  to allocate a new resource. An alternative would be to create a new thread to 
108  manage the process asynchronously. To aid this the thread should lock the `weakLock` 
109  mutex and suspend itself by calling `Thread.ConditionVar.wait` 
110  or `Thread.ConditionVar.waitUntil`,  passing `weakLock` and `weakSignal` 
111  as arguments. The `weakSignal` condition variable 
112  is broadcast after a garbage-collection if the garbage collector has modified 
113  a weak reference. Because there may be several libraries using weak references 
114  the receipt of the signal does not guarantee that a resource associated with 
115  any particular library has been released.
116  
117  The garbage-collector is only run when necessary and detection of released 
118  resources may happen very infrequently, depending on factors such as the size 
119  of the heap. To force a collection the library can call `PolyML.fullGC`
120**)
121