1#include "include/pw.h"
2#include "src/types/compound_internal.h"
3
4
5[[nodiscard]] PwValuePtr _pw_value_is_on_chain(PwValuePtr value, _PwCompoundChain* tail)
6{
7 do {
8 if (value->struct_data == tail->value->struct_data) {
9 return tail->value;
10 }
11 tail = tail->prev;
12 } while (tail);
13 return nullptr;
14}
15
16/****************************************************************
17 * Basic interface
18 */
19
20static bool compound_create(PwMethod_Basic_create* mthis, PwValuePtr result, PwCtorArgs* ctor_args)
21{
22 if (!pw_super(mthis, result, ctor_args)) {
23 return false;
24 }
25
26 _PwCompoundData* cdata = pw_this_data(result);
27
28 _pw_atomic_store(&cdata->set_refcount, 1);
29 cdata->set_refcount_ptr = &cdata->set_refcount;
30 return true;
31}
32
33static bool compound_destroy(PwMethod_Basic_destroy* mthis, PwValuePtr self, _PwCompoundChain* tail)
34{
35 PwValuePtr value_seen = _pw_on_chain(self, tail);
36 if (value_seen) {
37 return true;
38 }
39 return pw_super(mthis, self, tail);
40}
41
42static bool compound_clone(PwMethod_Basic_clone* mthis, PwValuePtr self)
43{
44 /*
45 * Clone compound: increase set_refcount along with refcount.
46 * We decrement set_refcount in _pw_compound_join which immediatelly follows clone (or deepcopy).
47 */
48
49 // XXX copy-pasted from Struct to avoid super call
50
51 _PwStructData* struct_data = (_PwStructData*) self->struct_data;
52 _pw_atomic_add(&struct_data->refcount, 1);
53
54 // increment set_refcount
55
56 _PwCompoundData* cdata = pw_this_data(self);
57 _pw_atomic_add(cdata->set_refcount_ptr, 1);
58 return true;
59}
60
61static bool compound_decref(PwMethod_Basic_decref* mthis, PwValuePtr self)
62{
63 // XXX copy-pasted from Struct to avoid super call
64
65 _PwStructData* struct_data = (_PwStructData*) self->struct_data;
66 _pw_atomic_sub(&struct_data->refcount, 1);
67
68 // decrement set_refcount
69
70 _PwCompoundData* cdata = pw_this_data(self);
71
72 unsigned prev_refcount = atomic_fetch_sub_explicit(cdata->set_refcount_ptr, 1, memory_order_relaxed);
73 if (prev_refcount == 0) {
74 // allow set_refcount underflow, which means destruction is in progress
75 // just keep it zero
76 atomic_fetch_add_explicit(cdata->set_refcount_ptr, 1, memory_order_relaxed);
77 prev_refcount = 1;
78 }
79 return prev_refcount != 1;
80}
81
82static bool compound_dump(PwMethod_Basic_dump* mthis, PwValuePtr self, FILE* fp, int indent, _PwCompoundChain* tail)
83{
84 PwValuePtr value_seen = _pw_on_chain(self, tail);
85 if (value_seen) {
86 _pw_print_indent(fp, indent + 4);
87 fprintf(fp, "already dumped: %p, data=%p\n", (void*) value_seen, (void*) value_seen->struct_data);
88 return true;
89 }
90
91 if (!pw_super(mthis, self, fp, indent, tail)) {
92 return false;
93 }
94
95 _PwCompoundData* cdata = pw_this_data(self);
96
97 _pw_print_indent(fp, indent + 4);
98 fprintf(fp, "Set refcount: %u (%s) at %p (cdata=%p)\n",
99 _pw_atomic_load(cdata->set_refcount_ptr),
100 (cdata->set_refcount_ptr == &cdata->set_refcount)? "this" : "foreign",
101 (void*) cdata->set_refcount_ptr,
102 (void*) cdata);
103 return true;
104}
105
106PwInterface_Basic _pw_compound_basic_interface = {
107 .create = { .func = compound_create },
108 .destroy = { .func = compound_destroy },
109 .clone = { .func = compound_clone },
110 .decref = { .func = compound_decref },
111 .dump = { .func = compound_dump }
112};
113
114/****************************************************************
115 * Join/split sets of compound values
116 */
117
118typedef struct {
119 PwValuePtr parent;
120 unsigned total_refcount; // total refcount of all children
121 unsigned internal_refcount; // number of references between children
122 _PwCompoundData* set_refcount_host;
123 bool have_refs_to_parent;
124} CircularityCheckerData;
125
126static void check_circularity(PwValuePtr value, _PwCompoundChain* tail, void* udata)
127/*
128 * Set `have_refs_to_parent` field in (CircularityCheckerData*) udata if value circularily refers to parent.
129 *
130 * If there's no circular references to parent, all other fields are valid.
131 */
132{
133 CircularityCheckerData* ccdata = (CircularityCheckerData*) udata;
134
135 if (value->struct_data == ccdata->parent->struct_data) {
136 ccdata->have_refs_to_parent = true;
137 return;
138 }
139 _PwCompoundData* cdata = _pw_get_struct_ptr(value, PwTypeId_Compound); // XXX optimize, CompoundData always follows StructData
140 if (cdata->set_refcount_ptr == &cdata->set_refcount) {
141 ccdata->set_refcount_host = cdata;
142 }
143
144 ccdata->total_refcount += _pw_atomic_load(&((_PwStructData*) value->struct_data)->refcount);
145 ccdata->internal_refcount++;
146
147 bool local_circularity = false;
148 for (_PwCompoundChain* prev = tail; prev; prev = prev->prev) {
149 auto struct_data = prev->value->struct_data;
150 if (struct_data == ccdata->parent->struct_data) {
151 ccdata->have_refs_to_parent = true;
152 return;
153 }
154 if (struct_data == value->struct_data) {
155 local_circularity = true;
156 ccdata->internal_refcount++;
157 }
158 }
159 if (local_circularity) {
160 return;
161 }
162
163 PwMethod_Basic_iter_children* meth_iter_children;
164 if (!pw_method(value->type_id, Basic, iter_children, &meth_iter_children)) {
165 return;
166 }
167 PwFunc_Basic_iter_children fn_iter_children = meth_iter_children->func;
168 if (_pw_likely(!fn_iter_children)) {
169 return;
170 }
171 // compound chain is to avoid infinite loops only; circular links between children are okay
172 _PwCompoundChain cc_link = {
173 .prev = tail,
174 .value = value
175 };
176 fn_iter_children(meth_iter_children, value, &cc_link, check_circularity, udata);
177}
178
179static void replace_set_refcount_ptr(PwValuePtr value, _PwCompoundChain* tail, void* set_refcount_ptr)
180{
181 _PwCompoundData* cdata = _pw_get_struct_ptr(value, PwTypeId_Compound); // XXX optimize, CompoundData always follows StructData
182 cdata->set_refcount_ptr = (atomic_uint*) set_refcount_ptr;
183
184 PwMethod_Basic_iter_children* meth_iter_children;
185 if (!pw_method(value->type_id, Basic, iter_children, &meth_iter_children)) {
186 return;
187 }
188 PwFunc_Basic_iter_children fn_iter_children = meth_iter_children->func;
189 if (_pw_likely(!fn_iter_children)) {
190 return;
191 }
192 _PwCompoundChain cc_link = {
193 .prev = tail,
194 .value = value
195 };
196 fn_iter_children(meth_iter_children, value, &cc_link, replace_set_refcount_ptr, set_refcount_ptr);
197}
198
199void _pw_compound_split(PwValuePtr parent, PwValuePtr child)
200{
201 // XXX optimize, CompoundData always follows StructData
202 _PwCompoundData* parent_cdata = _pw_get_struct_ptr(parent, PwTypeId_Compound);
203 _PwCompoundData* child_cdata = _pw_get_struct_ptr(child, PwTypeId_Compound);
204
205 if (!(parent_cdata && child_cdata)) {
206 return;
207 }
208
209 CircularityCheckerData ccdata = {
210 .parent = parent
211 };
212 check_circularity(child, nullptr, &ccdata);
213
214 if (ccdata.have_refs_to_parent) {
215 /*
216 * Cannot split if child circularly references to parent.
217 * If `child` is removed from `parent` and still refers to it
218 * (e.g. array that has an item referring to self),
219 * the parent will be gone only when the last reference to the entire set is gone.
220 */
221 return;
222 }
223 unsigned num_child_external_refs = ccdata.total_refcount - ccdata.internal_refcount;
224 if (num_child_external_refs == 0) {
225 // all references to child are held by parent, splitting does not make sense
226 return;
227 }
228 if (ccdata.set_refcount_host) {
229 /*
230 * set_refcount is hosted in child's subset ao we cannot change set_refcount_ptr
231 * because it would require replacing it for all parent values.
232 * We can't do this without back reference to parent, so do not.
233 */
234 return;
235 }
236
237 // decrement parent set refcount
238
239 if (_pw_atomic_sub(parent_cdata->set_refcount_ptr, num_child_external_refs) == 0) {
240 pw_panic("Parent %p must have references\n", parent);
241 }
242
243 // init child's set_refcount
244
245 _pw_atomic_store(&child_cdata->set_refcount, num_child_external_refs);
246
247 // replace set_refcount ptr for grandchildren
248
249 replace_set_refcount_ptr(child, nullptr, &child_cdata->set_refcount);
250}
251
252void _pw_compound_join(PwValuePtr parent, PwValuePtr child)
253{
254 // XXX optimize, CompoundData always follows StructData
255 _PwCompoundData* parent_cdata = _pw_get_struct_ptr(parent, PwTypeId_Compound);
256 _PwCompoundData* child_cdata = _pw_get_struct_ptr(child, PwTypeId_Compound);
257
258 if (!(parent_cdata && child_cdata)) {
259 return;
260 }
261 if (parent_cdata == child_cdata) {
262 // reference to self
263 } else if (parent_cdata->set_refcount_ptr == child_cdata->set_refcount_ptr) {
264 // already joined
265 } else {
266 // add child set refcount to parent
267
268 unsigned child_set_refcount = _pw_atomic_load(child_cdata->set_refcount_ptr);
269 _pw_atomic_add(parent_cdata->set_refcount_ptr, child_set_refcount);
270
271 // replace set_refcount ptr for child and grandchildren
272
273 replace_set_refcount_ptr(child, nullptr, parent_cdata->set_refcount_ptr);
274 }
275 // decrement set_refcount
276 _pw_atomic_sub(parent_cdata->set_refcount_ptr, 1);
277}