コミットメタ情報

リビジョンb13366936843ce0dbfb63fc47fac69f43a978a32 (tree)
日時2019-02-09 04:16:53
作者Agustina Arzille <avarzille@rise...>
コミッターAgustina Arzille

ログメッセージ

Use C3 linearization for types

変更サマリ

差分

diff -r 10b4dcf99c57 -r b13366936843 types.cpp
--- a/types.cpp Tue Feb 05 18:41:11 2019 -0300
+++ b/types.cpp Fri Feb 08 16:16:53 2019 -0300
@@ -212,6 +212,109 @@
212212 qp_return (*sd);
213213 }
214214
215+static inline bool
216+lst_addend (sorted_list<>& lst, object x)
217+{
218+ for (sorted_list<>::iterator it (lst); it.valid (); it.adv ())
219+ if ((object)it.key () == x)
220+ return (false);
221+
222+ lst.add_end (x, 0);
223+ return (true);
224+}
225+
226+static inline void
227+array_del_pos (array *ap, int pos)
228+{
229+ move_objs (&ap->data[pos], &ap->data[pos + 1], ap->len - pos - 1);
230+ --ap->len;
231+}
232+
233+static object
234+c3_merge_aux (interpreter *interp, array *heads,
235+ sorted_list<>& out)
236+{
237+ bool found = false;
238+ object h1 = fixint (0);
239+
240+ for (int ix = 0; ix < heads->len; ++ix)
241+ {
242+ array *ap = as_array (heads->data[ix]);
243+ h1 = fixint (0);
244+ if (!ap->len)
245+ continue;
246+
247+ h1 = ap->data[0];
248+
249+ for (int jx = 0; jx < heads->len; ++jx)
250+ {
251+ if (ix == jx)
252+ continue;
253+
254+ array *p2 = as_array (heads->data[jx]);
255+ for (int kx = 1; kx < p2->len; ++kx)
256+ if (p2->data[kx] == h1)
257+ goto skip;
258+ }
259+
260+ found = true;
261+ for (int jx = 0; jx < heads->len; ++jx)
262+ {
263+ array *p2 = as_array (heads->data[jx]);
264+ if (p2->len != 0 && p2->data[0] == h1)
265+ array_del_pos (p2, 0);
266+ }
267+
268+ break;
269+ skip: ;
270+ }
271+
272+ if (h1 == fixint (0))
273+ return (sorted_list_toarray (interp, out));
274+ else if (!found)
275+ interp->raise2 ("type-error", io_sprintf (interp,
276+ "inconsistency in base types when adding %Q", as_typespec(h1)->name));
277+
278+ out.add (h1, 0);
279+ return (c3_merge_aux (interp, heads, out));
280+}
281+
282+static object
283+c3_merge (interpreter *interp, sorted_list<>& parents)
284+{
285+ if (parents.len () == 0)
286+ return (alloc_array (interp, 0));
287+ else if (parents.len () == 1)
288+ return (alloc_array (interp, 1, parents.root.next->key));
289+
290+ QP_TMARK (interp);
291+ object *bp = (object *)QP_TALLOC (interp,
292+ (parents.len () + 1) * sizeof (*bp));
293+ local_varobj<array> heads;
294+ heads.local_init (bp, parents.len () + 1);
295+
296+ heads.len = parents.len () + 1;
297+ memset (bp, 0, heads.len * sizeof (*bp));
298+ interp->push (heads.as_obj ());
299+
300+ heads.data[0] = sorted_list_toarray (interp, parents);
301+ int ix = 0;
302+ sorted_list<> out;
303+
304+ for (sorted_list<>::iterator it (parents); it.valid (); it.adv ())
305+ {
306+ const array *inp = as_array (as_typespec(it.key())->parents);
307+ array *tp = as_array (alloc_array (interp, inp->len + 1));
308+ tp->data[0] = it.key ();
309+ copy_objs (&tp->data[1], inp->data, inp->len);
310+ heads.data[++ix] = tp->as_obj ();
311+ }
312+
313+ object ret = c3_merge_aux (interp, &heads, out);
314+ interp->popn ();
315+ return (ret);
316+}
317+
215318 object type (interpreter *interp, object name,
216319 object parents, object slotdefs)
217320 {
@@ -229,12 +332,9 @@
229332 object px = xcar (c);
230333 if (!typespec_p (px))
231334 interp->raise2 ("arg-error", "parent must be a typespec");
232-
233- p.add (px, 0);
234-
235- const auto tx = as_array (as_typespec(px)->parents);
236- for (int i = 0; i < tx->len; ++i)
237- p.add (tx->data[i], 0);
335+ else if (!lst_addend (p, px))
336+ interp->raise2 ("arg-error", io_sprintf (interp,
337+ "duplicate base type: %Q", as_typespec(px)->name));
238338 }
239339
240340 slotname_list_t slots;
@@ -246,7 +346,7 @@
246346
247347 auto ret = (typespec *)alloch (sizeof (typespec), typecode::TYPE);
248348 ret->name = name;
249- ret->parents = *tmp = sorted_list_toarray (interp, p);
349+ ret->parents = *tmp = c3_merge (interp, p);
250350 ret->num_slots = slots.len ();
251351 ret->slotdefs = make_slotdefs (interp, slotdefs, slots);
252352 ret->acc_slots = slots.len ();
@@ -371,6 +471,7 @@
371471 interp->raise2 ("unbound-error", io_sprintf (interp,
372472 "attribute %Q is unbound", key));
373473
474+ gc_wbarrier (interp, inst, val);
374475 qp_return (*ptr = val);
375476 }
376477
旧リポジトリブラウザで表示