Skip to content
← Back

src/ir/program/dispatch_plan.ghul

1
namespace IR.Program is
2
use Collections.LIST
3
use Collections.MAP
4
use Collections.SET
5
6
use Semantic.Symbols.Scope
7
use Semantic.Types.Type
8
use Semantic.Symbols.Symbol
9
use Semantic.Symbols.Classy
10
use Semantic.Symbols.Function
11
use Semantic.Symbols.GENERIC
12
13
/// A slot in the vtables of a class and everything derived from it.
14
///
15
/// - owner: the class whose vtable first has the slot
16
/// - index: the slot's position in that vtable and every vtable derived from it
17
/// - signature: the target's handle for the function type every entry in the slot has
18
class DISPATCH_SLOT(owner: CLASS_INSTANCE, index: int, signature: int)
19
20
/// A trait method, at one instantiation of its trait, called through the
21
/// trait table.
22
///
23
/// - method: the trait method, which overrides no other trait method
24
/// - signature: the target's handle for the function type every entry in its row has
25
class TRAIT_SELECTOR(method: FUNCTION_INSTANCE, signature: int) is
26
/// Where the selector's row starts in the table, once packed.
27
offset: int public
28
si
29
30
/// What a dispatch plan needs to know about the program's classes from
31
/// the target that compiles them.
32
trait DispatchTarget open is
33
/// The root class, or null for a program with no classes.
34
root: CLASS_INSTANCE?
35
36
/// The numbers given to the classes.
37
numbering: CLASS_ID_NUMBERING[CLASS_INSTANCE]
38
39
/// The class a value of `type` is an instance of, or null where the
40
/// program has none.
41
class_of(type: Type?) -> CLASS_INSTANCE?
42
43
/// The class `type` extends, or null where that is the root.
44
superclass_of(type: CLASS_INSTANCE) -> CLASS_INSTANCE?
45
46
/// The methods `definition` has, including any the target gave it.
47
methods_of(definition: Classy) -> Collections.List[Function]
48
49
/// Whether `type` is the root class.
50
is_object(type: CLASS_INSTANCE) -> bool
51
52
/// Whether `type` is a class with a representation of its own.
53
is_object_type(type: CLASS_INSTANCE) -> bool
54
55
/// Whether `type` is a scalar's box.
56
is_box(type: CLASS_INSTANCE) -> bool
57
58
/// Whether `type` is an array type.
59
is_array(type: CLASS_INSTANCE) -> bool
60
61
/// Whether `type` is the string type.
62
is_string(type: CLASS_INSTANCE) -> bool
63
64
/// Whether `type` is the built-in `bigint`.
65
is_bigint(type: CLASS_INSTANCE) -> bool
66
67
/// Whether anything creates an instance of `type`.
68
is_instantiated(type: CLASS_INSTANCE) -> bool
69
70
/// The target's handle for the function type of a vtable slot
71
/// opened by `method` on `owner`, or null where the target cannot
72
/// call it through a vtable.
73
slot_signature(owner: CLASS_INSTANCE, method: FUNCTION_INSTANCE) -> int?
74
75
/// The target's handle for the function type of the trait table row
76
/// of `method`, or null where the target cannot call it through the
77
/// table.
78
selector_signature(method: FUNCTION_INSTANCE) -> int?
79
si
80
81
/// How a program's virtual and trait calls dispatch: the vtable slots of
82
/// each class, and the trait selectors with their packed table.
83
///
84
/// A class method that something overrides takes a slot in its class's
85
/// vtable; an override fills the same slot. A trait method takes a row
86
/// in one table, indexed by the receiver's class number plus the row's
87
/// offset, one row for each instantiation of its trait.
88
class DISPATCH_PLAN is
89
_target: DispatchTarget
90
91
_slots: MAP[CLASS_INSTANCE, LIST[DISPATCH_SLOT]]
92
_slot_of: MAP[FUNCTION_INSTANCE, DISPATCH_SLOT]
93
_slot_entries: MAP[CLASS_INSTANCE, LIST[FUNCTION_INSTANCE?]]
94
95
_traits: MAP[CLASS_INSTANCE, CLASS_INSTANCE]
96
_trait_classes: MAP[CLASS_INSTANCE, LIST[CLASS_INSTANCE]]
97
_class_traits: MAP[CLASS_INSTANCE, LIST[CLASS_INSTANCE]]
98
_selectors: MAP[FUNCTION_INSTANCE, TRAIT_SELECTOR]
99
_rows: MAP[FUNCTION_INSTANCE, MAP[int, FUNCTION_INSTANCE]]
100
_generic_calls: MAP[FUNCTION_INSTANCE, (root: Function, owner: CLASS_INSTANCE, arguments: Collections.List[Type])]
101
102
_table_size: int
103
104
/// A plan for the classes `target` compiles.
105
init(target: DispatchTarget) is
106
_target = target
107
108
_slots = MAP[CLASS_INSTANCE, LIST[DISPATCH_SLOT]]()
109
_slot_of = MAP[FUNCTION_INSTANCE, DISPATCH_SLOT]()
110
_slot_entries = MAP[CLASS_INSTANCE, LIST[FUNCTION_INSTANCE?]]()
111
112
_traits = MAP[CLASS_INSTANCE, CLASS_INSTANCE]()
113
_trait_classes = MAP[CLASS_INSTANCE, LIST[CLASS_INSTANCE]]()
114
_class_traits = MAP[CLASS_INSTANCE, LIST[CLASS_INSTANCE]]()
115
_selectors = MAP[FUNCTION_INSTANCE, TRAIT_SELECTOR]()
116
_rows = MAP[FUNCTION_INSTANCE, MAP[int, FUNCTION_INSTANCE]]()
117
_generic_calls = MAP[FUNCTION_INSTANCE, (root: Function, owner: CLASS_INSTANCE, arguments: Collections.List[Type])]()
118
si
119
120
/// The trait table's size, once `plan_traits` has packed it.
121
table_size: int => _table_size
122
123
/// Every selector's row: the implementation for each class number.
124
rows: Collections.Iterable[Collections.KEY_VALUE_PAIR[FUNCTION_INSTANCE, MAP[int, FUNCTION_INSTANCE]]] => _rows
125
126
/// The selector whose row `method` heads.
127
selector(method: FUNCTION_INSTANCE) -> TRAIT_SELECTOR => _selectors[method]
128
129
/// Whether `type` has a vtable with at least one slot.
130
has_slots(type: CLASS_INSTANCE) -> bool =>
131
_slots.contains_key(type) /\ _slots[type].count > 0
132
133
/// The slots of `type`'s vtable, in order.
134
slots(type: CLASS_INSTANCE) -> Collections.List[DISPATCH_SLOT] => _slots[type]
135
136
/// The implementation filling each of `type`'s slots, in order.
137
slot_entries(type: CLASS_INSTANCE) -> Collections.List[FUNCTION_INSTANCE?] => _slot_entries[type]
138
139
/// Plans the slots of the classes in `ordered`, which lists parents
140
/// before children, and finds the traits each implements.
141
plan_slots(ordered: Collections.List[CLASS_INSTANCE]) is
142
for type in ordered do
143
// A box and the string type implement whatever traits an `impl`
144
// block gives their built-in type, so they take places in the
145
// trait table as a class does.
146
if _target.is_object_type(type) \/ _target.is_array(type) \/ _target.is_box(type) \/ _target.is_string(type) then
147
_plan_slots(type)
148
_collect_traits(type)
149
else
150
_plan_slots(type)
151
fi
152
od
153
si
154
155
/// Plans the selectors of every trait instance the program uses, and
156
/// packs their rows into the table.
157
plan_traits() is
158
_close_over_variance()
159
160
// A trait instance the program uses that nothing implements has
161
// a selector too, with an empty row: a call through it compiles,
162
// and can only ever be made on an absent receiver.
163
for used in LIST[CLASS_INSTANCE](_traits.values) do
164
if !_trait_classes.contains_key(used) then
165
_trait_classes[used] = LIST[CLASS_INSTANCE]()
166
fi
167
od
168
169
for (trait_type, classes) in _trait_classes do
170
_plan_selectors(trait_type, classes)
171
od
172
173
for (selector, call) in _generic_calls do
174
_plan_generic_selector(selector, call.root, call.owner, call.arguments)
175
od
176
177
_pack()
178
si
179
180
// Every row takes its place in the table before any body is
181
// compiled, since a call bakes its row's offset into the code.
182
// Every implementation a row could hold is placed, whether or not
183
// anything reaches it: a call through a selector reaches them all.
184
_pack() is
185
let packing = ROW_DISPLACEMENT[FUNCTION_INSTANCE]()
186
187
for (selector, row) in _rows do
188
packing.add(selector, row.keys)
189
od
190
191
packing.pack()
192
193
_table_size = packing.size
194
195
for (selector_method, _) in _rows do
196
_selectors[selector_method].offset = packing.offset(selector_method)
197
od
198
si
199
200
/// The class `type`'s vtable extends: its superclass, or the root,
201
/// or null for the root itself.
202
parent(type: CLASS_INSTANCE) -> CLASS_INSTANCE? is
203
if _target.is_object(type) then
204
return null
205
fi
206
207
if let parent = _target.superclass_of(type) /\ _target.is_object_type(parent) then
208
return parent
209
fi
210
211
return _target.root
212
si
213
214
/// Whether calls to `method` dispatch through a vtable or the table.
215
is_dispatched(method: Function) -> bool static =>
216
method.is_instance /\ method.is_virtual /\ !method.is_constructor /\ method.generic_arguments.count == 0
217
218
/// Whether `method` is a trait method generic in its own right,
219
/// whose calls dispatch through a row of the table for each
220
/// instantiation the program calls it at.
221
is_dispatched_generic(method: Function) -> bool static =>
222
method.is_instance /\ !method.is_constructor /\ method.generic_arguments.count > 0 /\ (cast Classy?(method.owner)?.is_trait ?? false)
223
224
/// The type arguments `call`, the instance a call names, gives its
225
/// function's own type parameters, or null where it has none.
226
///
227
/// - call: the function and type arguments a call names
228
own_type_arguments(call: FUNCTION_INSTANCE) -> LIST[Type]? static is
229
if call.definition.generic_arguments.count == 0 then
230
return null
231
fi
232
233
let result = LIST[Type]()
234
235
for parameter in call.definition.generic_arguments do
236
let argument: Type mut
237
238
if !call.type_map.try_get_value(parameter.symbol, argument ref) then
239
return null
240
fi
241
242
result.add(argument)
243
od
244
245
return result
246
si
247
248
/// Records a call to the generic trait method `method` on an
249
/// instance of `trait_type`, made at `arguments`, its own type
250
/// arguments, so that `plan_traits` gives the instantiation a row.
251
/// Answers the selector's method, or null where `trait_type` is not
252
/// an instance of the trait that declares it.
253
///
254
/// - method: the trait method called
255
/// - trait_type: the trait instance the call goes through
256
/// - arguments: the method's own type arguments at the call
257
note_generic_call(method: Function, trait_type: CLASS_INSTANCE, arguments: Collections.List[Type]) -> FUNCTION_INSTANCE? is
258
let root = _root_trait_method(method)
259
let owner = _trait_ancestor(trait_type, root.owner)
260
261
if !owner? \/ root.generic_arguments.count != arguments.count then
262
return null
263
fi
264
265
let key = FUNCTION_INSTANCE(root, _with_arguments(owner.type_map, root, arguments))
266
267
if !_generic_calls.contains_key(key) then
268
_generic_calls[key] = (root, owner, arguments)
269
fi
270
271
return key
272
si
273
274
/// The method a call to the generic trait method `method` runs on an
275
/// instance of `type` at `arguments`, its own type arguments: the
276
/// class's override or its implementation by name and signature, or
277
/// a trait's default, at those arguments. Null where `type` has none.
278
///
279
/// - type: the class of the receiver
280
/// - method: the trait method called
281
/// - arguments: the method's own type arguments at the call
282
generic_implementation(type: CLASS_INSTANCE, method: Function, arguments: Collections.List[Type]) -> FUNCTION_INSTANCE? is
283
let root = _root_trait_method(method)
284
let traits = _traits_of(type)
285
286
if !(traits |> Ghul.Pipes.any(t => t.definition == root.owner)) then
287
return null
288
fi
289
290
let current: CLASS_INSTANCE? mut = type
291
292
while current? do
293
for candidate in _target.methods_of(current.definition) do
294
if _takes_generic_call(candidate, arguments) /\ (_overrides(candidate, root) \/ TRAIT_SIGNATURE_MATCH.implements(candidate, root)) then
295
return FUNCTION_INSTANCE(candidate, _with_arguments(current.type_map, candidate, arguments))
296
fi
297
od
298
299
current = parent(current)
300
od
301
302
for trait_type in traits do
303
for candidate in _target.methods_of(trait_type.definition) do
304
if _takes_generic_call(candidate, arguments) /\ !candidate.is_abstract /\ (candidate == root \/ _overrides(candidate, root)) then
305
return FUNCTION_INSTANCE(candidate, _with_arguments(trait_type.type_map, candidate, arguments))
306
fi
307
od
308
od
309
310
return null
311
si
312
313
_takes_generic_call(method: Function, arguments: Collections.List[Type]) -> bool =>
314
method.is_instance /\ !method.is_constructor /\ method.generic_arguments.count == arguments.count
315
316
// `map` with each of `method`'s own type parameters taking the
317
// argument at its position.
318
_with_arguments(map: Collections.Map[Symbol, Type], method: Function, arguments: Collections.List[Type]) -> MAP[Symbol, Type] is
319
let result = MAP[Symbol, Type]()
320
321
for (parameter, argument) in map do
322
result[parameter] = argument
323
od
324
325
for i in 0..method.generic_arguments.count do
326
result[method.generic_arguments[i].symbol] = arguments[i]
327
od
328
329
return result
330
si
331
332
// Every trait instance `type` implements, through its own
333
// declarations, the traits those derive from, and its superclasses,
334
// found without recording anything.
335
_traits_of(type: CLASS_INSTANCE) -> LIST[CLASS_INSTANCE] is
336
let result = LIST[CLASS_INSTANCE]()
337
338
_traits_of(type.definition, type.type_map, result)
339
340
return result
341
si
342
343
_traits_of(from: Classy, map: Collections.Map[Symbol, Type], result: LIST[CLASS_INSTANCE]) is
344
for ancestor in from.ancestors do
345
let specialized = TYPE_MAPS.specialize(ancestor, map)!
346
347
if ancestor.is_trait then
348
if let trait_type = trait_of(specialized) /\ !result.contains(trait_type) then
349
result.add(trait_type)
350
351
_traits_of(trait_type.definition, trait_type.type_map, result)
352
fi
353
elif let superclass = _target.class_of(specialized) /\ _target.is_object_type(superclass) then
354
_traits_of(superclass.definition, superclass.type_map, result)
355
fi
356
od
357
si
358
359
// The instance of `definition`, one of `type`'s ancestors, that
360
// `type` derives from.
361
_ancestor(type: CLASS_INSTANCE, definition: Scope?) -> CLASS_INSTANCE? is
362
let current: CLASS_INSTANCE? mut = type
363
364
while current? do
365
if current.definition == definition then
366
return current
367
fi
368
369
current = parent(current)
370
od
371
372
return null
373
si
374
375
// A class's vtable starts as a copy of its parent's. A method
376
// overriding a class method fills that method's slot; one that
377
// something overrides and that overrides nothing opens a new slot.
378
_plan_slots(type: CLASS_INSTANCE) is
379
let slots = LIST[DISPATCH_SLOT]()
380
let entries = LIST[FUNCTION_INSTANCE?]()
381
382
if let parent = parent(type) then
383
slots.add_range(_slots[parent])
384
entries.add_range(_slot_entries[parent])
385
fi
386
387
// The root and the classes the program declares bring methods
388
// of their own, and the string type overrides the root's; a box
389
// answers the root's.
390
let is_string = _target.is_string(type)
391
let has_own_methods = _target.is_object(type) \/ _target.is_object_type(type) \/ is_string
392
393
for method in if has_own_methods then _target.methods_of(type.definition) else LIST[Function]() fi do
394
if !is_dispatched(method) then
395
continue
396
fi
397
398
let key = FUNCTION_INSTANCE(method, type.type_map)
399
400
if let slot = _overridden_slot(type, method) then
401
_slot_of[key] = slot
402
entries[slot.index] = key
403
elif !is_string /\ !method.has_no_overriders then
404
if let signature = _target.slot_signature(type, key) then
405
let slot = DISPATCH_SLOT(type, slots.count, signature)
406
407
slots.add(slot)
408
entries.add(key)
409
410
_slot_of[key] = slot
411
fi
412
fi
413
od
414
415
// A box answers with its scalar's own methods where they override
416
// the root's, as the scalar would on .NET, and so does bigint.
417
// Their methods are not the box's own to dispatch, so they only
418
// fill the slots they override.
419
if _target.is_box(type) \/ _target.is_bigint(type) then
420
for method in _target.methods_of(type.definition) do
421
if !method.is_instance \/ method.is_constructor then
422
continue
423
fi
424
425
if let slot = _overridden_slot(type, method) then
426
let key = FUNCTION_INSTANCE(method, type.type_map)
427
428
_slot_of[key] = slot
429
entries[slot.index] = key
430
fi
431
od
432
fi
433
434
_slots[type] = slots
435
_slot_entries[type] = entries
436
si
437
438
_overridden_slot(type: CLASS_INSTANCE, method: Function) -> DISPATCH_SLOT? is
439
if let overridees = method.overridees then
440
for overridee in overridees do
441
if let function: Function = overridee then
442
if let owner = _ancestor(type, function.owner) then
443
let slot: DISPATCH_SLOT mut
444
445
if _slot_of.try_get_value(FUNCTION_INSTANCE(function, owner.type_map), slot ref) then
446
return slot
447
fi
448
fi
449
fi
450
od
451
fi
452
453
return null
454
si
455
456
/// The one instance of the trait a value of `type` is, at its
457
/// arguments.
458
trait_of(type: Type) -> CLASS_INSTANCE? is
459
let definition: Classy mut
460
let map: Collections.Map[Symbol, Type] mut
461
462
if let generic: GENERIC = type.symbol /\ isa Classy(generic.unspecialized_symbol) then
463
definition = cast Classy?(generic.unspecialized_symbol)!
464
map = generic.type_map
465
elif let classy: Classy = type.symbol then
466
definition = classy
467
map = MAP[Symbol, Type]()
468
else
469
return null
470
fi
471
472
if !definition.is_trait then
473
return null
474
fi
475
476
let key = CLASS_INSTANCE(definition, type.arguments, map)
477
478
let existing: CLASS_INSTANCE mut
479
480
if _traits.try_get_value(key, existing ref) then
481
return existing
482
fi
483
484
_traits[key] = key
485
486
return key
487
si
488
489
/// The one instance of the trait `definition` at the arguments
490
/// `type_map` gives its parameters.
491
trait_of(definition: Classy, type_map: Collections.Map[Symbol, Type]) -> CLASS_INSTANCE? is
492
if !definition.is_trait then
493
return null
494
fi
495
496
let map = MAP[Symbol, Type]()
497
498
for (parameter, argument) in type_map do
499
if parameter.owner == definition then
500
map[parameter] = argument
501
fi
502
od
503
504
let key = CLASS_INSTANCE(definition, LIST[Type](map.values), map)
505
506
let existing: CLASS_INSTANCE mut
507
508
if _traits.try_get_value(key, existing ref) then
509
return existing
510
fi
511
512
_traits[key] = key
513
514
return key
515
si
516
517
// Each trait instance the program uses takes, as its implementors,
518
// the classes implementing any instance of the same trait that
519
// converts to it under the trait's declared variance, so a value
520
// reached through a variant instantiation dispatches and tests as
521
// it does on .NET. A row entry for the variant instance calls the
522
// same compiled member as the instance the class implements.
523
_close_over_variance() is
524
let implemented = LIST[CLASS_INSTANCE](_trait_classes.keys)
525
526
for used in LIST[CLASS_INSTANCE](_traits.values) do
527
for trait_type in implemented do
528
if trait_type != used /\ trait_type.definition == used.definition /\ _converts_by_variance(trait_type, used) then
529
if !_trait_classes.contains_key(used) then
530
_trait_classes[used] = LIST[CLASS_INSTANCE]()
531
fi
532
533
let classes = _trait_classes[used]
534
535
for type in _trait_classes[trait_type] do
536
if !classes.contains(type) then
537
classes.add(type)
538
_class_traits[type].add(used)
539
fi
540
od
541
fi
542
od
543
od
544
si
545
546
// Whether the trait instance `from` converts to `to`, an instance of
547
// the same trait: each type argument is the same, or, where the
548
// parameter is declared `out` or `in` and both arguments are
549
// reference types, a subtype or a supertype of `to`'s.
550
_converts_by_variance(from: CLASS_INSTANCE, to: CLASS_INSTANCE) -> bool is
551
if from.arguments.count != to.arguments.count then
552
return false
553
fi
554
555
for i in 0..from.arguments.count do
556
let source = from.arguments[i]
557
let target = to.arguments[i]
558
559
if source.is_assignable_from(target) /\ target.is_assignable_from(source) then
560
continue
561
fi
562
563
if source.is_value_type \/ target.is_value_type then
564
return false
565
fi
566
567
let variance = from.definition.get_argument_variance(i)
568
569
if variance == Semantic.Types.TypeVariance.COVARIANT then
570
if !target.is_assignable_from(source) then
571
return false
572
fi
573
elif variance == Semantic.Types.TypeVariance.CONTRAVARIANT then
574
if !source.is_assignable_from(target) then
575
return false
576
fi
577
else
578
return false
579
fi
580
od
581
582
return true
583
si
584
585
// Every trait instance a class implements, through its own
586
// declarations, the traits those derive from, and its superclasses.
587
_collect_traits(type: CLASS_INSTANCE) is
588
let seen = SET[CLASS_INSTANCE]()
589
590
_class_traits[type] = LIST[CLASS_INSTANCE]()
591
592
_collect_traits(type, type.definition, type.type_map, seen)
593
si
594
595
_collect_traits(type: CLASS_INSTANCE, from: Classy, map: Collections.Map[Symbol, Type], seen: SET[CLASS_INSTANCE]) is
596
for ancestor in from.ancestors do
597
let specialized = TYPE_MAPS.specialize(ancestor, map)!
598
599
if ancestor.is_trait then
600
if let trait_type = trait_of(specialized) /\ seen.add(trait_type) then
601
if !_trait_classes.contains_key(trait_type) then
602
_trait_classes[trait_type] = LIST[CLASS_INSTANCE]()
603
fi
604
605
_trait_classes[trait_type].add(type)
606
_class_traits[type].add(trait_type)
607
608
_collect_traits(type, trait_type.definition, trait_type.type_map, seen)
609
fi
610
elif let superclass = _target.class_of(specialized) /\ _target.is_object_type(superclass) then
611
_collect_traits(type, superclass.definition, superclass.type_map, seen)
612
fi
613
od
614
si
615
616
// A trait method that overrides no other trait method is a
617
// selector, one for each instantiation of its trait; one that does
618
// dispatches through the one it overrides.
619
_plan_selectors(trait_type: CLASS_INSTANCE, classes: LIST[CLASS_INSTANCE]) is
620
for method in _target.methods_of(trait_type.definition) do
621
if !is_dispatched(method) \/ _root_trait_method(method) != method then
622
continue
623
fi
624
625
let selector = FUNCTION_INSTANCE(method, trait_type.type_map)
626
627
if _selectors.contains_key(selector) then
628
continue
629
fi
630
631
if let signature = _target.selector_signature(selector) then
632
_selectors[selector] = TRAIT_SELECTOR(selector, signature)
633
634
let row = MAP[int, FUNCTION_INSTANCE]()
635
636
for type in classes do
637
if let implementation = _implementation(type, method) then
638
row[_target.numbering.id(type)] = implementation
639
fi
640
od
641
642
_rows[selector] = row
643
fi
644
od
645
si
646
647
// A generic trait method has a selector for each instantiation a
648
// call was recorded at, whose row holds each implementor's method
649
// at the same arguments.
650
_plan_generic_selector(selector: FUNCTION_INSTANCE, root: Function, owner: CLASS_INSTANCE, arguments: Collections.List[Type]) is
651
if _selectors.contains_key(selector) then
652
return
653
fi
654
655
let signature = _target.selector_signature(selector)
656
657
if !signature? then
658
return
659
fi
660
661
_selectors[selector] = TRAIT_SELECTOR(selector, signature)
662
663
let row = MAP[int, FUNCTION_INSTANCE]()
664
let classes: LIST[CLASS_INSTANCE] mut
665
666
if _trait_classes.try_get_value(owner, classes ref) then
667
for type in classes do
668
if let implementation = generic_implementation(type, root, arguments) then
669
row[_target.numbering.id(type)] = implementation
670
fi
671
od
672
fi
673
674
_rows[selector] = row
675
si
676
677
_root_trait_method(method: Function) -> Function is
678
if let overridees = method.overridees then
679
for overridee in overridees do
680
if let function: Function = overridee /\ (cast Classy?(function.owner)?.is_trait ?? false) then
681
return _root_trait_method(function)
682
fi
683
od
684
fi
685
686
return method
687
si
688
689
// The method a call to `selector` on an instance of `type` runs:
690
// the nearest one up the class chain that overrides it, or that
691
// implements it by name and signature where it is a trait method,
692
// else a trait's default.
693
_implementation(type: CLASS_INSTANCE, selector: Function) -> FUNCTION_INSTANCE? is
694
let current: CLASS_INSTANCE? mut = type
695
696
while current? do
697
for method in _target.methods_of(current.definition) do
698
if is_dispatched(method) /\ (_overrides(method, selector) \/ TRAIT_SIGNATURE_MATCH.implements(method, selector)) then
699
return FUNCTION_INSTANCE(method, current.type_map)
700
fi
701
od
702
703
current = parent(current)
704
od
705
706
for trait_type in _class_traits[type] do
707
for method in _target.methods_of(trait_type.definition) do
708
if is_dispatched(method) /\ !method.is_abstract /\ (method == selector \/ _overrides(method, selector)) then
709
return FUNCTION_INSTANCE(method, trait_type.type_map)
710
fi
711
od
712
od
713
714
return null
715
si
716
717
_overrides(method: Function, target: Function) -> bool is
718
if let overridees = method.overridees then
719
for overridee in overridees do
720
if let function: Function = overridee then
721
if function == target \/ _overrides(function, target) then
722
return true
723
fi
724
fi
725
od
726
fi
727
728
return false
729
si
730
731
/// The vtable slot a call to `method` reads, or null where nothing
732
/// overrides it.
733
slot_of(method: FUNCTION_INSTANCE) -> DISPATCH_SLOT? is
734
let result: DISPATCH_SLOT mut
735
736
if _slot_of.try_get_value(method, result ref) then
737
return result
738
fi
739
740
return null
741
si
742
743
/// The selector a call to the trait method `method` dispatches on,
744
/// where `method` is called on an instance of `trait_type`, or null
745
/// where it has none.
746
selector_of(method: Function, trait_type: CLASS_INSTANCE) -> TRAIT_SELECTOR? is
747
let root = _root_trait_method(method)
748
let owner = _trait_ancestor(trait_type, root.owner)
749
750
if !owner? then
751
return null
752
fi
753
754
let result: TRAIT_SELECTOR mut
755
756
if _selectors.try_get_value(FUNCTION_INSTANCE(root, owner.type_map), result ref) then
757
return result
758
fi
759
760
return null
761
si
762
763
/// The selector a call to the generic trait method `method` at
764
/// `arguments` dispatches on, where it is called on an instance of
765
/// `trait_type`, or null where no call at those arguments was
766
/// recorded.
767
///
768
/// - method: the trait method called
769
/// - trait_type: the trait instance the call goes through
770
/// - arguments: the method's own type arguments at the call
771
generic_selector_of(method: Function, trait_type: CLASS_INSTANCE, arguments: Collections.List[Type]) -> TRAIT_SELECTOR? is
772
let root = _root_trait_method(method)
773
let owner = _trait_ancestor(trait_type, root.owner)
774
775
if !owner? \/ root.generic_arguments.count != arguments.count then
776
return null
777
fi
778
779
let result: TRAIT_SELECTOR mut
780
781
if _selectors.try_get_value(FUNCTION_INSTANCE(root, _with_arguments(owner.type_map, root, arguments)), result ref) then
782
return result
783
fi
784
785
return null
786
si
787
788
// The instance of the trait `definition` that `trait_type` is or
789
// derives from.
790
_trait_ancestor(trait_type: CLASS_INSTANCE, definition: Scope?) -> CLASS_INSTANCE? is
791
if trait_type.definition == definition then
792
return trait_type
793
fi
794
795
for ancestor in trait_type.definition.ancestors do
796
if ancestor.is_trait then
797
if let parent = trait_of(trait_type.specialize(ancestor)!) then
798
if let found = _trait_ancestor(parent, definition) then
799
return found
800
fi
801
fi
802
fi
803
od
804
805
return null
806
si
807
808
/// The one method any call to `selector` can run, or null where the
809
/// row has more than one, or none.
810
only_implementation(selector: TRAIT_SELECTOR) -> FUNCTION_INSTANCE? =>
811
only_implementation(selector, _ => true)
812
813
/// The one method a call to `selector` can run on a value of a class
814
/// `can_exist` accepts, or null where those classes run more than
815
/// one, or none.
816
///
817
/// - selector: the trait method's row
818
/// - can_exist: whether a value of a class, by its number, can exist
819
only_implementation(selector: TRAIT_SELECTOR, can_exist: (int) -> bool) -> FUNCTION_INSTANCE? =>
820
_only(implementations(selector, can_exist))
821
822
/// Every method a call to `selector` can run on a value of a class
823
/// `can_exist` accepts.
824
///
825
/// - selector: the trait method's row
826
/// - can_exist: whether a value of a class, by its number, can exist
827
implementations(selector: TRAIT_SELECTOR, can_exist: (int) -> bool) -> SET[FUNCTION_INSTANCE] is
828
let implementations = SET[FUNCTION_INSTANCE]()
829
830
for (class_id, implementation) in _rows[selector.method] do
831
if can_exist(class_id) then
832
implementations.add(implementation)
833
fi
834
od
835
836
return implementations
837
si
838
839
/// The method a call through `slot` runs on a value of exactly
840
/// `type`, or null where `type`'s vtable has no such entry.
841
///
842
/// - slot: the vtable slot the call reads
843
/// - type: the receiver's exact class
844
slot_implementation(slot: DISPATCH_SLOT, type: CLASS_INSTANCE) -> FUNCTION_INSTANCE? is
845
let slots: LIST[DISPATCH_SLOT] mut
846
847
if !_slots.try_get_value(type, slots ref) \/ slot.index >= slots.count \/ slots[slot.index] != slot then
848
return null
849
fi
850
851
return _slot_entries[type][slot.index]
852
si
853
854
/// The method a call to `selector` runs on a value of the class
855
/// numbered `class_id`, or null where its row has none.
856
///
857
/// - selector: the trait method's row
858
/// - class_id: the receiver's exact class, by its number
859
implementation(selector: TRAIT_SELECTOR, class_id: int) -> FUNCTION_INSTANCE? is
860
let row: MAP[int, FUNCTION_INSTANCE] mut
861
let implementation: FUNCTION_INSTANCE mut
862
863
if _rows.try_get_value(selector.method, row ref) /\ row.try_get_value(class_id, implementation ref) then
864
return implementation
865
fi
866
867
return null
868
si
869
870
/// The one method a call through `slot` can run on a value of a
871
/// class `can_exist` accepts, or null where those classes run more
872
/// than one, or none.
873
///
874
/// - slot: the vtable slot the call reads
875
/// - can_exist: whether a value of a class can exist
876
only_slot_implementation(slot: DISPATCH_SLOT, can_exist: (CLASS_INSTANCE) -> bool) -> FUNCTION_INSTANCE? =>
877
if let implementations = slot_implementations(slot, can_exist) then _only(implementations) else null fi
878
879
/// Every method a call through `slot` can run on a value of a class
880
/// `can_exist` accepts, or null where the slot is the root's, which
881
/// values with no class of their own, such as closures, answer too.
882
///
883
/// - slot: the vtable slot the call reads
884
/// - can_exist: whether a value of a class can exist
885
slot_implementations(slot: DISPATCH_SLOT, can_exist: (CLASS_INSTANCE) -> bool) -> SET[FUNCTION_INSTANCE]? is
886
if _target.is_object(slot.owner) then
887
return null
888
fi
889
890
let implementations = SET[FUNCTION_INSTANCE]()
891
892
for (type, slots) in _slots do
893
// A class whose entry is empty, as an abstract class's is,
894
// has no instance a call could reach.
895
if slot.index < slots.count /\ slots[slot.index] == slot /\ can_exist(type) then
896
if let implementation = _slot_entries[type][slot.index] then
897
implementations.add(implementation)
898
fi
899
fi
900
od
901
902
return implementations
903
si
904
905
_only(implementations: SET[FUNCTION_INSTANCE]) -> FUNCTION_INSTANCE? is
906
if implementations.count == 1 then
907
for implementation in implementations do
908
return implementation
909
od
910
fi
911
912
return null
913
si
914
915
/// The classes implementing `trait_type`, or null where the program
916
/// has none.
917
implementors(trait_type: CLASS_INSTANCE) -> Collections.List[CLASS_INSTANCE]? is
918
let result: LIST[CLASS_INSTANCE] mut
919
920
if _trait_classes.try_get_value(trait_type, result ref) then
921
return result
922
fi
923
924
return null
925
si
926
927
/// Marks every implementation that can fill `slot` as reached:
928
/// `reach` is given each.
929
use_slot(slot: DISPATCH_SLOT, reach: (FUNCTION_INSTANCE) -> void) is
930
for (type, slots) in _slots do
931
if !_target.is_instantiated(type) then
932
continue
933
fi
934
935
if slot.index < slots.count /\ slots[slot.index] == slot then
936
if let implementation = _slot_entries[type][slot.index] then
937
reach(implementation)
938
fi
939
fi
940
od
941
si
942
943
/// Marks every implementation in `selector`'s row as reached:
944
/// `reach` is given each.
945
use_selector(selector: TRAIT_SELECTOR, reach: (FUNCTION_INSTANCE) -> void) is
946
for (_, implementation) in _rows[selector.method] do
947
reach(implementation)
948
od
949
si
950
si
951
si