lib/std/lang/resolver/refs.rad 66.5 KiB raw
1
//! References and regions of values.
2
//!
3
//! A value holds references directly, or as a value of a record or union that
4
//! declares regions. The region positions of a type number its regions: the
5
//! region of a reference's address, then the positions of its target, or the
6
//! region parameters of a record or union. A region value has one region per
7
//! position of its type. The resolver tracks the region value of each local, and
8
//! checks it where a value is stored, returned or constructed.
9
10
use std::lang::ast;
11
use std::lang::types;
12
use std::mem::heap;
13
use super::NominalType;
14
use super::Resolver;
15
use super::SymbolData;
16
use super::Type;
17
18
/// Region of the references that a value holds.
19
export union Region: Copy {
20
    /// The value holds no reference, so it fits any region.
21
    Free,
22
    /// The references have no known bound and cannot prove a region contract.
23
    Local,
24
    /// The references belong to a named region, by its symbol.
25
    Named(super::SymbolId),
26
    /// An unnamed reference position in a parameter binding.
27
    Parameter {
28
        /// Binding that supplies the reference.
29
        binding: super::SymbolId,
30
        /// Reference position in the parameter type.
31
        position: u32,
32
    },
33
    /// Storage with an implicit region bounded by a lexical scope.
34
    Scoped(super::ScopeId),
35
    /// A region and the source accesses that its value retains.
36
    Borrowed(*Dependency),
37
    /// One region per position of the value's type.
38
    Many(*[Region]),
39
}
40
41
/// Storage access retained by a region value.
42
export record Source: Copy {
43
    /// Expression that supplies the storage.
44
    node: *ast::Node,
45
    /// Reference binding that provides access to this source.
46
    binding: ?super::SymbolId,
47
    /// Whether other reads of the source are excluded.
48
    exclusive: bool,
49
}
50
51
/// Provenance and source accesses of one content position.
52
export record Dependency: Copy {
53
    /// Region bound of the content position.
54
    region: Region,
55
    /// Source accesses retained by the value.
56
    sources: *[Source],
57
}
58
59
/// Whether an empty expected position accepts references.
60
export union Check: Copy {
61
    /// The value must fit a storage or return contract.
62
    Assignment,
63
    /// Either alternative can omit references at a position.
64
    Alternatives,
65
}
66
67
/// Return the provenance bound of a region value.
68
export fn bound(region: Region) -> Region {
69
    if let case Region::Borrowed(dependency) = region {
70
        return dependency.region;
71
    }
72
    return region;
73
}
74
75
/// Return the source accesses retained by a content position.
76
export fn sources(region: Region) -> *[Source] {
77
    if let case Region::Borrowed(dependency) = region {
78
        return dependency.sources;
79
    }
80
    return &[];
81
}
82
83
/// Attach source accesses to a provenance bound.
84
fn dependency(self: &Resolver, region: Region, sources: *[Source]) -> Region {
85
    if sources.len == 0 {
86
        return region;
87
    }
88
    let mut values: *mut [Dependency] = &mut [];
89
    try! values.append(Dependency { region, sources }, self.arena);
90
    return Region::Borrowed(&values[0]);
91
}
92
93
/// Retain a source access with the references that it supplies.
94
export fn borrow(
95
    self: &Resolver, node: *ast::Node, region: Region, exclusive: bool
96
) -> Region {
97
    let mut regionBound = bound(region);
98
    if regionBound == Region::Free {
99
        return region;
100
    }
101
    if regionBound == Region::Local {
102
        if let sym = super::symbolFor(self, node) {
103
            if let case SymbolData::Value { scope, .. } = self.symbols[*sym].data {
104
                set regionBound = Region::Scoped(scope);
105
            }
106
        }
107
    }
108
    if not exclusive {
109
        if let case Region::Named(sym) = regionBound {
110
            if let case SymbolData::Region { mutable: false, .. } = self.symbols[*sym].data {
111
                return region;
112
            }
113
        }
114
    }
115
    // Shared dependencies keep their storage borrowed without a loan on its holder.
116
    if not exclusive and sources(region).len > 0 {
117
        let mut shared = true;
118
        for source in sources(region) {
119
            set shared = shared and not source.exclusive;
120
        }
121
        if shared {
122
            return dependency(self, regionBound, sources(region));
123
        }
124
    }
125
    let mut retained: *mut [Source] = &mut [];
126
    try! retained.extend(sources(region), self.arena);
127
    let source = Source { node, binding: nil, exclusive };
128
    try! retained.append(source, self.arena);
129
    return dependency(self, regionBound, &retained[..]);
130
}
131
132
/// Capture a reference value at a binding or aggregate boundary: an address
133
/// without a retained source retains the reference itself.
134
export fn capture(self: &Resolver, node: *ast::Node) -> Region {
135
    let region = valueRegion(self, node);
136
    let ty = super::typeFor(self, node) else return region;
137
    let address = part(region, 0);
138
    if super::isRefType(ty) and sources(address).len == 0 {
139
        let view = borrow(self, node, address, super::isExclusiveArgument(self, ty));
140
        return withAddress(self, view, region, positions(self, ty));
141
    }
142
    return region;
143
}
144
145
/// Give new source accesses the binding through which they can be used.
146
fn anchor(self: &Resolver, region: Region, binding: super::SymbolId) -> Region {
147
    if let case Region::Many(parts) = region {
148
        let mut values: *mut [Region] = &mut [];
149
        for part in parts {
150
            try! values.append(anchor(self, part, binding), self.arena);
151
        }
152
        return bundle(self, &values[..]);
153
    }
154
    let mut retained: *mut [Source] = &mut [];
155
    for source in sources(region) {
156
        let mut source = source;
157
        if source.binding == nil {
158
            set source.binding = binding;
159
        }
160
        try! retained.append(source, self.arena);
161
    }
162
    return dependency(self, bound(region), &retained[..]);
163
}
164
165
/// One input source of a region of a function result.
166
export record Borrow: Copy {
167
    /// Region position in the result type.
168
    result: u32,
169
    /// Source parameter index, counting a method receiver first.
170
    param: u32,
171
    /// Region position in the parameter type.
172
    source: u32,
173
}
174
175
/// One input source that a function may store into a region of the object of a
176
/// parameter.
177
export record Store: Copy {
178
    /// Parameter whose object receives the source, counting a method receiver first.
179
    target: u32,
180
    /// Region position in the target parameter's type.
181
    region: u32,
182
    /// Source parameter index, counting a method receiver first.
183
    param: u32,
184
    /// Region position in the source parameter's type.
185
    source: u32,
186
}
187
188
/// A function type whose store contracts are found once the types of its
189
/// parameters are resolved.
190
export record PendingStores: Copy {
191
    /// Index of the contracts in the store table.
192
    index: u32,
193
    /// The method receiver type, if any.
194
    receiverType: ?*ast::Node,
195
    /// The parameter nodes.
196
    params: *[*ast::Node],
197
    /// The parameter types, counting a method receiver first.
198
    types: *[*Type],
199
}
200
201
/// Store contracts of function types.
202
export record StoreTable {
203
    /// Contracts, indexed by the `stores` index of a function type.
204
    contracts: *mut [*[Store]],
205
    /// Function types whose contracts wait for the end of the declaration phase.
206
    pending: *mut [PendingStores],
207
}
208
209
/// Return the sources that a function may store into the objects of its parameters.
210
export fn storesOf(self: &Resolver, info: *super::FnType) -> *[Store] {
211
    let index = info.stores else return &[];
212
    return self.stores.contracts[index];
213
}
214
215
/// Whether two function types have the same store contracts.
216
export fn sameStores(self: &Resolver, a: ?u32, b: ?u32) -> bool {
217
    let mut left: *[Store] = &[];
218
    let mut right: *[Store] = &[];
219
    if let index = a {
220
        set left = self.stores.contracts[index];
221
    }
222
    if let index = b {
223
        set right = self.stores.contracts[index];
224
    }
225
    if left.len <> right.len {
226
        return false;
227
    }
228
    for item, i in left {
229
        if item <> right[i] {
230
            return false;
231
        }
232
    }
233
    return true;
234
}
235
236
/// Return the type node of parameter `index`, counting a method receiver first.
237
/// A function type lists its parameter types without names.
238
export fn paramTypeNode(
239
    receiverType: ?*ast::Node, params: *[*ast::Node], index: u32
240
) -> *ast::Node {
241
    let mut at = index;
242
    if let receiver = receiverType {
243
        if index == 0 {
244
            return receiver;
245
        }
246
        set at = index - 1;
247
    }
248
    if let case ast::NodeValue::FnParam(param) = params[at].value {
249
        return param.type;
250
    }
251
    return params[at];
252
}
253
254
/// Whether a signature can have store contracts: a position of a parameter's
255
/// contents names a region that another position of the parameters names.
256
export fn mayStore(
257
    self: &Resolver, receiverType: ?*ast::Node, params: *[*ast::Node], types: *[*Type]
258
) -> bool {
259
    return sharedSources(self, receiverType, params, types, false).len > 0;
260
}
261
262
/// Find the sources that a function may store into the objects of its parameters:
263
/// each writable position of a parameter receives the positions of parameters that
264
/// name the same region.
265
export fn storeContracts(
266
    self: &Resolver, receiverType: ?*ast::Node, params: *[*ast::Node], types: *[*Type]
267
) -> *[Store] {
268
    return sharedSources(self, receiverType, params, types, true);
269
}
270
271
/// Pair each position of a parameter's contents with the positions of parameters
272
/// that name the same region. The address of a reference is not its contents.
273
/// With `writable`, only positions that a callee can write receive sources.
274
fn sharedSources(
275
    self: &Resolver,
276
    receiverType: ?*ast::Node,
277
    params: *[*ast::Node],
278
    types: *[*Type],
279
    writable: bool
280
) -> *[Store] {
281
    let mut collected: *mut [*[?*ast::Node]] = &mut [];
282
    for i in 0 .. types.len {
283
        let names = positionNames(self, paramTypeNode(receiverType, params, i));
284
        try! collected.append(names, self.arena);
285
    }
286
    let names: *[*[?*ast::Node]] = &collected[..];
287
    let mut out: *mut [Store] = &mut [];
288
    for target in 0 .. types.len {
289
        let mut mask: *[bool] = &[];
290
        if writable {
291
            set mask = writablePositions(self, *types[target]);
292
        }
293
        let start: u32 = 1 if super::isRefType(*types[target]) else 0;
294
        for region in start .. names[target].len {
295
            let name = names[target][region] else continue;
296
            let case ast::NodeValue::Ident(text) = name.value else continue;
297
            if writable and (region >= mask.len or not mask[region]) {
298
                continue;
299
            }
300
            for inputs, param in names {
301
                for input, source in inputs {
302
                    if (param <> target or source <> region) and isRegionName(input, text) {
303
                        try! out.append(Store { target, region, param, source }, self.arena);
304
                    }
305
                }
306
            }
307
        }
308
    }
309
    return &out[..];
310
}
311
312
/// Maximum number of nested record and union types that [`writes`] follows.
313
constant WRITES_DEPTH: u32 = 16;
314
315
/// Record and union types that a [`writes`] search is inside.
316
record Visit {
317
    /// The types, outermost first.
318
    ids: [super::NominalId; WRITES_DEPTH],
319
    /// Number of types.
320
    len: u32,
321
}
322
323
/// Whether a value of `ty` reaches a mutable reference, through which a callee can
324
/// store references into its caller's objects.
325
export fn writes(self: &Resolver, ty: Type) -> bool {
326
    let mut visit = Visit { ids: undefined, len: 0 };
327
    return reachesMutable(self, ty, &mut visit);
328
}
329
330
/// Whether a value of `ty` reaches a mutable reference. A type that the search is
331
/// inside adds nothing, and a search that nests too deep assumes that it does.
332
fn reachesMutable(self: &Resolver, ty: Type, visit: &mut Visit) -> bool {
333
    match ty {
334
        case Type::Pointer { class: types::PointerClass::Ref, mutable, target } =>
335
            return mutable or reachesMutable(self, *target, visit),
336
        case Type::Slice { class: types::PointerClass::Ref, mutable, item } =>
337
            return mutable or reachesMutable(self, *item, visit),
338
        case Type::Optional(inner) => return reachesMutable(self, *inner, visit),
339
        case Type::Array(array)    => return reachesMutable(self, *array.item, visit),
340
        case Type::Nominal(id) => {
341
            for i in 0 .. visit.len {
342
                if visit.ids[i] == id {
343
                    return false;
344
                }
345
            }
346
            if visit.len == WRITES_DEPTH {
347
                return true;
348
            }
349
            set visit.ids[visit.len] = id;
350
            set visit.len += 1;
351
            let mut found = false;
352
            match self.nominals[*id] {
353
                case NominalType::Record(info) => {
354
                    for field in info.fields {
355
                        set found = found or reachesMutable(self, field.fieldType, visit);
356
                    }
357
                }
358
                case NominalType::Union(info) => {
359
                    for variant in info.variants {
360
                        set found = found or reachesMutable(self, variant.valueType, visit);
361
                    }
362
                }
363
                case NominalType::Placeholder(_), NominalType::Parameter { .. } =>
364
                    set found = true,
365
            }
366
            set visit.len -= 1;
367
            return found;
368
        }
369
        else => return false,
370
    }
371
}
372
373
/// Return, for each region position of `ty`, whether a callee can store references
374
/// at it in its caller's objects: the position is reached through a mutable
375
/// reference, or a record or union that reaches one holds it.
376
export fn writablePositions(self: &Resolver, ty: Type) -> *[bool] {
377
    let mut out: *mut [bool] = &mut [];
378
    collectWritable(self, ty, false, &mut out);
379
    return &out[..];
380
}
381
382
/// Append whether each region position of `ty` is writable, when it is reached
383
/// through a mutable reference if `through` holds.
384
fn collectWritable(self: &Resolver, ty: Type, through: bool, out: &mut *mut [bool]) {
385
    if positions(self, ty) == 0 {
386
        return;
387
    }
388
    match ty {
389
        case Type::Pointer { class, mutable, target } => {
390
            if class == types::PointerClass::Ref {
391
                try! out.append(through, self.arena);
392
            }
393
            collectWritable(self, *target, through or mutable, out);
394
        }
395
        case Type::Slice { class, mutable, item } => {
396
            if class == types::PointerClass::Ref {
397
                try! out.append(through, self.arena);
398
            }
399
            collectWritable(self, *item, through or mutable, out);
400
        }
401
        case Type::Optional(inner) => collectWritable(self, *inner, through, out),
402
        case Type::Array(array)    => collectWritable(self, *array.item, through, out),
403
        case Type::Nominal(id) => {
404
            let writable = through or writes(self, ty);
405
            for _ in nominalRegions(self, id) {
406
                try! out.append(writable, self.arena);
407
            }
408
        }
409
        else => try! out.append(through, self.arena),
410
    }
411
}
412
413
/// Return whether a type contains a reference, directly or as a value of a type
414
/// with a region.
415
export fn containsRef(self: &Resolver, ty: Type) -> bool {
416
    if super::isRefType(ty) {
417
        return true;
418
    }
419
    if let case Type::Pointer { target, .. } = ty {
420
        return containsRef(self, *target);
421
    }
422
    if let case Type::Slice { item, .. } = ty {
423
        return containsRef(self, *item);
424
    }
425
    match ty {
426
        case Type::Array(array)    => return containsRef(self, *array.item),
427
        case Type::Optional(inner) => return containsRef(self, *inner),
428
        // Nominal declarations validate their own fields and variants.
429
        // Treating them as leaves also terminates recursive pointer types.
430
        case Type::Nominal(id) => return isBorrowedNominal(self, id),
431
        else                   => return false,
432
    }
433
}
434
435
/// Whether a nominal type declares a region. An unresolved declaration is read
436
/// from its syntax.
437
fn isBorrowedNominal(self: &Resolver, id: super::NominalId) -> bool {
438
    match self.nominals[*id] {
439
        case NominalType::Record(r)        => return r.borrowed,
440
        case NominalType::Union(u)         => return u.borrowed,
441
        case NominalType::Placeholder(_)   => return nominalRegions(self, id).len > 0,
442
        case NominalType::Parameter { .. } => return false,
443
    }
444
}
445
446
/// Whether `ty` is a reference to a value, or to elements, of a type with a region.
447
export fn refersToBorrowed(self: &Resolver, ty: Type) -> bool {
448
    match ty {
449
        case Type::Pointer { class: types::PointerClass::Ref, target, .. } =>
450
            return containsRef(self, *target),
451
        case Type::Slice { class: types::PointerClass::Ref, item, .. } =>
452
            return containsRef(self, *item),
453
        else => return false,
454
    }
455
}
456
457
/// Whether `ty` holds a reference behind an unsafe pointer, which is plain data
458
/// without regions.
459
export fn hidesRef(self: &Resolver, ty: Type) -> bool {
460
    match ty {
461
        case Type::Pointer { class: types::PointerClass::Unsafe, target, .. } =>
462
            return containsRef(self, *target),
463
        case Type::Slice { class: types::PointerClass::Unsafe, item, .. } =>
464
            return containsRef(self, *item),
465
        case Type::Pointer { target, .. } => return hidesRef(self, *target),
466
        case Type::Slice { item, .. }     => return hidesRef(self, *item),
467
        case Type::Array(array)           => return hidesRef(self, *array.item),
468
        case Type::Optional(inner)        => return hidesRef(self, *inner),
469
        else                              => return false,
470
    }
471
}
472
473
/// Whether `ty` contains a value of a type with a region.
474
export fn isBorrowedType(self: &Resolver, ty: Type) -> bool {
475
    return containsRef(self, ty) and not (super::isRefType(ty) and not refersToBorrowed(self, ty));
476
}
477
478
/// Whether every region position of a type node has a name.
479
export fn namesRegions(self: &Resolver, type: *ast::Node) -> bool {
480
    for name in positionNames(self, type) {
481
        if name == nil {
482
            return false;
483
        }
484
    }
485
    return true;
486
}
487
488
/// Whether a region name node is `name`.
489
export fn isRegionName(region: ?*ast::Node, name: *[u8]) -> bool {
490
    let r = region else return false;
491
    let case ast::NodeValue::Ident(n) = r.value else return false;
492
    return n == name;
493
}
494
495
/// Return the regions that a signature declares: the first name node of each
496
/// distinct region that the receiver type or a parameter type names, in
497
/// signature order. A region named only by the result or the body has no
498
/// input, so the signature does not declare it.
499
export fn signatureRegions(
500
    self: &Resolver,
501
    receiverType: ?*ast::Node,
502
    params: *[*ast::Node]
503
) -> *[*ast::Node] {
504
    let mut regions: *mut [*ast::Node] = &mut [];
505
    if let type = receiverType {
506
        collectSignatureRegions(self, type, &mut regions);
507
    }
508
    for i in 0 .. params.len {
509
        collectSignatureRegions(self, paramTypeNode(nil, params, i), &mut regions);
510
    }
511
    return &regions[..];
512
}
513
514
/// Append the region names of a type node that are not in `out` yet.
515
fn collectSignatureRegions(self: &Resolver, type: *ast::Node, out: &mut *mut [*ast::Node]) {
516
    for position in positionNames(self, type) {
517
        let region = position else continue;
518
        let case ast::NodeValue::Ident(name) = region.value else continue;
519
        let mut seen = false;
520
        for other in &out[..] {
521
            if isRegionName(other, name) {
522
                set seen = true;
523
                break;
524
            }
525
        }
526
        if not seen {
527
            try! out.append(region, self.arena);
528
        }
529
    }
530
}
531
532
/// Return the region name of each region position of a type node, or nil for
533
/// a reference that names no region.
534
export fn positionNames(self: &Resolver, type: *ast::Node) -> *[?*ast::Node] {
535
    let mut names: *mut [?*ast::Node] = &mut [];
536
    collectNames(self, type, &mut names);
537
    return &names[..];
538
}
539
540
/// Append the region names of the positions of a type node.
541
fn collectNames(self: &Resolver, type: *ast::Node, out: &mut *mut [?*ast::Node]) {
542
    if let ty = super::typeFor(self, type); positions(self, ty) == 0 {
543
        return;
544
    }
545
    let case ast::NodeValue::TypeSig(sig) = type.value else return;
546
    match sig {
547
        case ast::TypeSig::Nominal { args, .. } => {
548
            for arg in args {
549
                if let case ast::NodeValue::Ident(_) = arg.value {
550
                    try! out.append(arg, self.arena);
551
                }
552
            }
553
        }
554
        case ast::TypeSig::Optional { valueType } => collectNames(self, valueType, out),
555
        case ast::TypeSig::Array { itemType, .. } => collectNames(self, itemType, out),
556
        case ast::TypeSig::Pointer { class, valueType, region, .. } => {
557
            if class == types::PointerClass::Ref {
558
                try! out.append(region, self.arena);
559
            }
560
            collectNames(self, valueType, out);
561
        }
562
        case ast::TypeSig::Slice { class, itemType, region, .. } => {
563
            if class == types::PointerClass::Ref {
564
                try! out.append(region, self.arena);
565
            }
566
            collectNames(self, itemType, out);
567
        }
568
        case ast::TypeSig::TraitObject { .. } => try! out.append(nil, self.arena),
569
        else                                  => {}
570
    }
571
}
572
573
/// Return the declared region parameters of a nominal type.
574
export fn nominalRegions(self: &Resolver, id: super::NominalId) -> *[*ast::Node] {
575
    match self.nominals[*id] {
576
        case NominalType::Record(r)        => return r.regions,
577
        case NominalType::Union(u)         => return u.regions,
578
        case NominalType::Parameter { .. } => return &[],
579
        case NominalType::Placeholder(node) => {
580
            match node.value {
581
                case ast::NodeValue::RecordDecl(r) => return r.binders,
582
                case ast::NodeValue::UnionDecl(u)  => return u.binders,
583
                else                               => return &[],
584
            }
585
        }
586
    }
587
}
588
589
/// Map the content arguments of a declaration member to enclosing parameters.
590
export fn declarationMap(
591
    self: &Resolver, type: *ast::Node, parameters: *[*ast::Node]
592
) -> *[u32] {
593
    let mut mapping: *mut [u32] = &mut [];
594
    if let case ast::NodeValue::TypeSig(ast::TypeSig::Record { .. }) = type.value {
595
        for _, i in parameters {
596
            try! mapping.append(i, self.arena);
597
        }
598
        return &mapping[..];
599
    }
600
    for region in positionNames(self, type) {
601
        let mut index: u32 = 0;
602
        if let name = region {
603
            let case ast::NodeValue::Ident(text) = name.value
604
                else panic "declarationMap: not a name";
605
            for param, i in parameters {
606
                if isRegionName(param, text) {
607
                    set index = i;
608
                    break;
609
                }
610
            }
611
        }
612
        try! mapping.append(index, self.arena);
613
    }
614
    return &mapping[..];
615
}
616
617
/// Whether two function source contracts are identical.
618
export fn sameBorrows(a: *[Borrow], b: *[Borrow]) -> bool {
619
    if a.len <> b.len {
620
        return false;
621
    }
622
    for item, i in a {
623
        if item <> b[i] {
624
            return false;
625
        }
626
    }
627
    return true;
628
}
629
630
/// Whether a type node is a mutable reference that names region `name`.
631
export fn namesMutRegion(type: *ast::Node, name: *[u8]) -> bool {
632
    let case ast::NodeValue::TypeSig(sig) = type.value else return false;
633
    match sig {
634
        case ast::TypeSig::Pointer { mutable, region, .. } =>
635
            return mutable and isRegionName(region, name),
636
        case ast::TypeSig::Slice { mutable, region, .. } =>
637
            return mutable and isRegionName(region, name),
638
        else => return false,
639
    }
640
}
641
642
/// Whether the receiver or a parameter is a mutable reference that names
643
/// region `name`.
644
export fn signatureNamesMutRegion(
645
    receiverType: ?*ast::Node,
646
    params: *[*ast::Node],
647
    name: *[u8]
648
) -> bool {
649
    if let type = receiverType; namesMutRegion(type, name) {
650
        return true;
651
    }
652
    for i in 0 .. params.len {
653
        if namesMutRegion(paramTypeNode(nil, params, i), name) {
654
            return true;
655
        }
656
    }
657
    return false;
658
}
659
660
/// Regions of the subject of a pattern, which its bindings take.
661
export record BindingRegions: Copy {
662
    /// Region value of the matched value.
663
    value: Region,
664
    /// Region of the storage of the matched value, for bindings by reference.
665
    storage: Region,
666
    /// The subject expression, which bindings by reference retain.
667
    node: ?*ast::Node,
668
}
669
670
/// Index of the region state of symbol `sym`, if it holds references.
671
fn regionIndex(self: &Resolver, sym: super::SymbolId) -> ?u32 {
672
    let case SymbolData::Value { regions, .. } = self.symbols[*sym].data else return nil;
673
    return regions;
674
}
675
676
/// Return the region value of symbol `sym`.
677
export fn symbolRegion(self: &Resolver, sym: super::SymbolId) -> Region {
678
    let index = regionIndex(self, sym) else return Region::Free;
679
    return self.symbolRegions[index];
680
}
681
682
/// Assign a distinct bound to each unnamed position of a parameter.
683
export fn parameterRegion(
684
    self: &Resolver, binding: ?super::SymbolId, declared: Region, ty: Type
685
) -> Region {
686
    let binding = binding else return declared;
687
    let mut values: *mut [Region] = &mut [];
688
    for position in 0 .. positions(self, ty) {
689
        let mut value = part(declared, position);
690
        if value == Region::Local {
691
            set value = Region::Parameter { binding, position };
692
        }
693
        try! values.append(value, self.arena);
694
    }
695
    return bundle(self, &values[..]);
696
}
697
698
/// Store an ordered collection of content regions, with scalar storage for one.
699
export fn bundle(self: &Resolver, parts: &[Region]) -> Region {
700
    if parts.len == 0 {
701
        return Region::Free;
702
    }
703
    if parts.len == 1 {
704
        return parts[0];
705
    }
706
    let mut values: *mut [Region] = &mut [];
707
    try! values.extend(parts, self.arena);
708
    return Region::Many(&values[..]);
709
}
710
711
/// Return the region at a position of a region value. Free values fit all regions.
712
export fn part(region: Region, index: u32) -> Region {
713
    if let case Region::Many(parts) = region {
714
        return parts[index] if index < parts.len else Region::Local;
715
    }
716
    if index == 0 or region == Region::Free or region == Region::Local {
717
        return region;
718
    }
719
    return Region::Local;
720
}
721
722
/// Whether the dependencies fit a contract or the other alternative.
723
export fn fits(self: &Resolver, expected: Region, actual: Region, check: Check) -> bool {
724
    let expected = bound(expected);
725
    let actual = bound(actual);
726
    if actual == Region::Free or (check == Check::Alternatives and expected == Region::Free) {
727
        return true;
728
    }
729
    if expected == Region::Local or actual == Region::Local {
730
        return false;
731
    }
732
    if let case Region::Many(want) = expected {
733
        let case Region::Many(have) = actual else return false;
734
        if want.len <> have.len {
735
            return false;
736
        }
737
        for value, i in have {
738
            if not fits(self, want[i], value, check) {
739
                return false;
740
            }
741
        }
742
        return true;
743
    }
744
    if let case Region::Scoped(target) = expected {
745
        let mut at: ?super::ScopeId = target;
746
        while let scope = at {
747
            if actual == Region::Scoped(scope) {
748
                return true;
749
            }
750
            if let case Region::Named(sym) = actual {
751
                if let case SymbolData::Region { scope: source, .. } =
752
                    self.symbols[*sym].data;
753
                    source == scope
754
                {
755
                    return true;
756
                }
757
            }
758
            if let case Region::Parameter { binding, .. } = actual {
759
                if let case SymbolData::Value { scope: source, .. } =
760
                    self.symbols[*binding].data;
761
                    source == scope
762
                {
763
                    return true;
764
                }
765
            }
766
            set at = self.scopes[*scope].parent;
767
        }
768
        return false;
769
    }
770
    if check == Check::Alternatives {
771
        if let case Region::Scoped(_) = actual {
772
            return fits(self, actual, expected, Check::Assignment);
773
        }
774
    }
775
    return expected == actual;
776
}
777
778
/// Join the dependencies of alternatives or elements of one type.
779
export fn joinRegion(self: &Resolver, a: Region, b: Region) -> Region {
780
    if a == Region::Free {
781
        return b;
782
    }
783
    if b == Region::Free {
784
        return a;
785
    }
786
    if let case Region::Many(left) = a {
787
        let case Region::Many(right) = b else return Region::Local;
788
        if left.len <> right.len {
789
            return Region::Local;
790
        }
791
        let mut joined: *mut [Region] = &mut [];
792
        for value, i in left {
793
            try! joined.append(joinRegion(self, value, right[i]), self.arena);
794
        }
795
        return bundle(self, &joined[..]);
796
    }
797
    let left = bound(a);
798
    let right = bound(b);
799
    let region = right
800
        if fits(self, right, left, Check::Assignment)
801
        else left if fits(self, left, right, Check::Assignment) else Region::Local;
802
    let mut retained: *mut [Source] = &mut [];
803
    try! retained.extend(sources(a), self.arena);
804
    for source in sources(b) {
805
        let mut seen = false;
806
        for i in 0 .. retained.len {
807
            let previous = retained[i];
808
            if previous.node == source.node and previous.exclusive == source.exclusive {
809
                set seen = true;
810
                break;
811
            }
812
        }
813
        if not seen {
814
            try! retained.append(source, self.arena);
815
        }
816
    }
817
    return dependency(self, region, &retained[..]);
818
}
819
820
/// Project the region arguments of a member from its containing value.
821
export fn project(self: &Resolver, value: Region, mapping: *[u32]) -> Region {
822
    let mut parts: *mut [Region] = &mut [];
823
    for index in mapping {
824
        try! parts.append(part(value, index), self.arena);
825
    }
826
    return bundle(self, &parts[..]);
827
}
828
829
/// Replace the address region of a reference value of `count` positions.
830
export fn withAddress(self: &Resolver, address: Region, region: Region, count: u32) -> Region {
831
    let mut parts: *mut [Region] = &mut [];
832
    try! parts.append(address, self.arena);
833
    for i in 1 .. count {
834
        try! parts.append(part(region, i), self.arena);
835
    }
836
    return bundle(self, &parts[..]);
837
}
838
839
/// Return the region value of a reference of `count` positions to a target of
840
/// `region`, whose address is `address`.
841
export fn reference(self: &Resolver, address: Region, region: Region, count: u32) -> Region {
842
    let mut parts: *mut [Region] = &mut [];
843
    try! parts.append(address, self.arena);
844
    for i in 1 .. count {
845
        try! parts.append(part(region, i - 1), self.arena);
846
    }
847
    return bundle(self, &parts[..]);
848
}
849
850
/// Replace each free position of a region value of `count` positions with `with`.
851
export fn fillFree(self: &Resolver, region: Region, count: u32, with: Region) -> Region {
852
    let mut parts: *mut [Region] = &mut [];
853
    for i in 0 .. count {
854
        let value = part(region, i);
855
        try! parts.append(with if value == Region::Free else value, self.arena);
856
    }
857
    return bundle(self, &parts[..]);
858
}
859
860
/// Return the region value of the target of a value of type `ty`: a reference
861
/// drops its address, and other values are their own target.
862
export fn target(self: &Resolver, region: Region, ty: Type) -> Region {
863
    if not super::isRefType(ty) {
864
        return region;
865
    }
866
    let mut parts: *mut [Region] = &mut [];
867
    for i in 1 .. positions(self, ty) {
868
        try! parts.append(part(region, i), self.arena);
869
    }
870
    return bundle(self, &parts[..]);
871
}
872
873
/// Add a member's content regions to the parameter positions of its container.
874
fn inject(self: &Resolver, values: &mut [Region], mapping: *[u32], value: Region) {
875
    for index, i in mapping {
876
        set values[index] = joinRegion(self, values[index], part(value, i));
877
    }
878
}
879
880
/// Return the region value of `node`: one region per position of its type. A
881
/// value without references fits any region.
882
export fn valueRegion(self: &Resolver, node: *ast::Node) -> Region {
883
    let ty = super::typeFor(self, node) else return Region::Local;
884
    if not containsRef(self, ty) {
885
        return Region::Free;
886
    }
887
    match node.value {
888
        case ast::NodeValue::Ident(_), ast::NodeValue::ScopeAccess(_) => {
889
            // Constants and variants hold no references.
890
            let sym = super::symbolFor(self, node) else return Region::Local;
891
            return symbolRegion(self, sym);
892
        }
893
        case ast::NodeValue::AddressOf(addr) => {
894
            if isEmptyArray(addr.target) {
895
                return Region::Free;
896
            }
897
            let address = borrow(self, node, placeRegion(self, addr.target), addr.mutable);
898
            return reference(self, address, valueRegion(self, addr.target), positions(self, ty));
899
        }
900
        // A field or element of a value holds the references of the value.
901
        case ast::NodeValue::FieldAccess(access) => {
902
            let parentTy = super::typeFor(self, access.parent) else return Region::Local;
903
            let mut region = target(self, valueRegion(self, access.parent), parentTy);
904
            if let index = super::recordFieldIndexFor(self, access.child) {
905
                if let field = super::getRecordField(self, super::autoDeref(parentTy), index) {
906
                    set region = project(self, region, field.regions);
907
                }
908
            }
909
            if mutableReference(ty) {
910
                if let view = mutableView(self, access.parent) {
911
                    return withAddress(self, view, region, positions(self, ty));
912
                }
913
            }
914
            return region;
915
        }
916
        case ast::NodeValue::Bracket { base: container, .. } => {
917
            let containerTy = super::typeFor(self, container) else return Region::Local;
918
            return target(self, valueRegion(self, container), containerTy);
919
        }
920
        case ast::NodeValue::Deref(inner) => {
921
            let innerTy = super::typeFor(self, inner) else return Region::Local;
922
            return target(self, valueRegion(self, inner), innerTy);
923
        }
924
        case ast::NodeValue::As(cast) => return valueRegion(self, cast.value),
925
        case ast::NodeValue::Try(t)   => return valueRegion(self, t.expr),
926
        case ast::NodeValue::CondExpr(cond) =>
927
            return joinRegion(self, valueRegion(self, cond.thenExpr), valueRegion(
928
                self, cond.elseExpr
929
            )),
930
        case ast::NodeValue::Call(_) => {
931
            if let info = super::borrowedFunction(self, node); info.borrows.len > 0 {
932
                return callRegions(self, node, info);
933
            }
934
            return constructorRegions(self, node);
935
        }
936
        case ast::NodeValue::RecordLit(_)        => return constructorRegions(self, node),
937
        case ast::NodeValue::ArrayLit(items)     => return joinRegions(self, items),
938
        case ast::NodeValue::ArrayRepeatLit(r)   => return valueRegion(self, r.item),
939
        case ast::NodeValue::RecordLitField(arg) => return valueRegion(self, arg.value),
940
        case ast::NodeValue::Nil                 => return Region::Free,
941
        else                                     => return Region::Local,
942
    }
943
}
944
945
/// Return the region value of argument `param` of a call, in the positions of the
946
/// parameter type. A receiver passed by value is borrowed at its place.
947
export fn argumentRegion(
948
    self: &Resolver, node: *ast::Node, info: *super::FnType, param: u32
949
) -> Region {
950
    let arg = super::borrowedInput(self, node, param);
951
    let paramTy = *info.paramTypes[param];
952
    let input = valueRegion(self, arg);
953
    if let actual = super::typeFor(self, arg);
954
        super::isRefType(paramTy) and not super::isRefType(actual)
955
    {
956
        return reference(self, placeRegion(self, arg), input, positions(self, paramTy));
957
    }
958
    return input;
959
}
960
961
/// Return the region value that a store into place `node` must fit: the regions
962
/// declared for the place, not those of a view that bounds reads of it.
963
export fn storedRegion(self: &Resolver, node: *ast::Node) -> Region {
964
    let case ast::NodeValue::FieldAccess(access) = node.value else return valueRegion(self, node);
965
    let parentTy = super::typeFor(self, access.parent) else return Region::Local;
966
    let region = target(self, valueRegion(self, access.parent), parentTy);
967
    let index = super::recordFieldIndexFor(self, access.child) else return region;
968
    let field = super::getRecordField(self, super::autoDeref(parentTy), index) else return region;
969
    return project(self, region, field.regions);
970
}
971
972
/// Substitute all declared input sources into the result's region positions.
973
fn callRegions(self: &Resolver, node: *ast::Node, info: *super::FnType) -> Region {
974
    let resultTy = super::typeFor(self, node) else return Region::Local;
975
    let mut values: *mut [Region] = &mut [];
976
    try! values.resize(positions(self, *info.returnType), Region::Free, self.arena);
977
    for source in info.borrows {
978
        let arg = super::borrowedInput(self, node, source.param);
979
        let argTy = *info.paramTypes[source.param];
980
        let mut region = part(argumentRegion(self, node, info, source.param), source.source);
981
        if super::isRefType(argTy) {
982
            set region = borrow(
983
                self,
984
                arg,
985
                region,
986
                super::isExclusiveArgument(self, resultTy)
987
                    and super::isExclusiveArgument(self, argTy)
988
            );
989
        }
990
        set values[source.result] = joinRegion(self, values[source.result], region);
991
    }
992
    return bundle(self, &values[..]);
993
}
994
995
/// Fields and arguments that map a constructor's content regions.
996
record ConstructorParts: Copy {
997
    /// Fields of a record or a labeled union payload.
998
    fields: *[super::RecordField],
999
    /// Region positions of an unlabeled union payload.
1000
    mapping: *[u32],
1001
    /// Values supplied to the constructor.
1002
    args: *[*ast::Node],
1003
}
1004
1005
/// Return the fields and values that supply the regions of a constructor.
1006
fn constructorParts(self: &Resolver, node: *ast::Node) -> ?ConstructorParts {
1007
    let case Type::Nominal(id) = super::typeFor(self, node) else return nil;
1008
    let mut fields: *[super::RecordField] = &[];
1009
    let mut mapping: *[u32] = &[];
1010
    let mut args: *[*ast::Node] = &[];
1011
    match node.value {
1012
        case ast::NodeValue::Call(call)     => set args = call.args,
1013
        case ast::NodeValue::RecordLit(lit) => set args = lit.fields,
1014
        else                                => panic "constructorRegions: expected constructor",
1015
    }
1016
    match self.nominals[*id] {
1017
        case NominalType::Record(info) => set fields = info.fields,
1018
        case NominalType::Union(info) => {
1019
            let case super::NodeExtra::UnionVariant { ordinal, .. } =
1020
                super::nodeData(self, node).extra else return nil;
1021
            let variant = info.variants[ordinal];
1022
            let decl = self.symbols[*variant.symbol].node;
1023
            let case ast::NodeValue::UnionDeclVariant(value) = decl.value
1024
                else panic "constructorRegions: expected variant";
1025
            set mapping = variant.regions;
1026
            if let type = value.type {
1027
                if let case ast::NodeValue::TypeSig(ast::TypeSig::Record { .. }) = type.value {
1028
                    let rec = super::getRecord(self, variant.valueType)
1029
                        else panic "constructorRegions: expected payload record";
1030
                    set fields = rec.fields;
1031
                }
1032
            }
1033
        }
1034
        else => panic "constructorRegions: unresolved nominal",
1035
    }
1036
    return ConstructorParts { fields, mapping, args };
1037
}
1038
1039
/// Collect per-position dependencies of record and union constructors.
1040
fn constructorRegions(self: &Resolver, node: *ast::Node) -> Region {
1041
    let case Type::Nominal(id) = super::typeFor(self, node) else return Region::Local;
1042
    let parts = constructorParts(self, node) else return Region::Free;
1043
    let mut values: *mut [Region] = &mut [];
1044
    try! values.resize(nominalRegions(self, id).len, Region::Free, self.arena);
1045
    for arg, i in parts.args {
1046
        let mut value = arg;
1047
        let mut index = i;
1048
        if let case ast::NodeValue::RecordLitField(field) = arg.value {
1049
            set value = field.value;
1050
            let resolved = super::recordFieldIndexFor(self, arg)
1051
                else panic "constructorRegions: unresolved field";
1052
            set index = resolved;
1053
        }
1054
        let positions = parts.fields[index].regions if parts.fields.len > 0 else parts.mapping;
1055
        inject(self, &mut values[..], positions, capture(self, value));
1056
    }
1057
    return bundle(self, &values[..]);
1058
}
1059
1060
/// Join the regions of the values of `nodes`.
1061
fn joinRegions(self: &Resolver, nodes: *[*ast::Node]) -> Region {
1062
    let mut region = Region::Free;
1063
    for n in nodes {
1064
        set region = joinRegion(self, region, capture(self, n));
1065
    }
1066
    return region;
1067
}
1068
1069
/// Whether `node` is an empty array literal, whose view addresses no storage.
1070
fn isEmptyArray(node: *ast::Node) -> bool {
1071
    let case ast::NodeValue::ArrayLit(items) = node.value else return false;
1072
    return items.len == 0;
1073
}
1074
1075
/// Return the region of the storage of place `node`. Storage of the frame, and
1076
/// storage behind a pointer that names no region, are local. A literal string
1077
/// is static data, which fits any region.
1078
fn placeRegion(self: &Resolver, node: *ast::Node) -> Region {
1079
    match node.value {
1080
        case ast::NodeValue::String(_)           => return Region::Free,
1081
        case ast::NodeValue::FieldAccess(access) => return containerRegion(self, access.parent),
1082
        case ast::NodeValue::Bracket { base: container, .. } =>
1083
            return containerRegion(self, container),
1084
        case ast::NodeValue::Deref(target) => return outerRegion(self, target),
1085
        case ast::NodeValue::As(cast)      => return placeRegion(self, cast.value),
1086
        case ast::NodeValue::Ident(_), ast::NodeValue::ScopeAccess(_) => {
1087
            if let sym = super::symbolFor(self, node) {
1088
                if let case SymbolData::Value { scope, .. } = self.symbols[*sym].data {
1089
                    return Region::Scoped(scope);
1090
                }
1091
            }
1092
            return Region::Local;
1093
        }
1094
        else => return Region::Local,
1095
    }
1096
}
1097
1098
/// Return the region of the storage of the fields or elements of `node`: the
1099
/// storage that a pointer or slice points to, or the storage of a value.
1100
fn containerRegion(self: &Resolver, node: *ast::Node) -> Region {
1101
    let ty = super::typeFor(self, node) else return Region::Local;
1102
    match ty {
1103
        case Type::Pointer { .. }, Type::Slice { .. } =>
1104
            return outerRegion(self, node),
1105
        else => return placeRegion(self, node),
1106
    }
1107
}
1108
1109
/// Return the region of the storage that a pointer or slice points to: the
1110
/// address region of a reference. The storage of an owning pointer belongs to the
1111
/// place that holds the pointer.
1112
export fn outerRegion(self: &Resolver, node: *ast::Node) -> Region {
1113
    let ty = super::typeFor(self, node) else return Region::Local;
1114
    if super::isRefType(ty) {
1115
        return part(valueRegion(self, node), 0);
1116
    }
1117
    match ty {
1118
        case
1119
            Type::Pointer { class: types::PointerClass::Owned, .. },
1120
            Type::Slice { class: types::PointerClass::Owned, .. },
1121
            Type::Nominal(_),
1122
            Type::Array(_) =>
1123
            return placeRegion(self, node),
1124
        else => return Region::Local,
1125
    }
1126
}
1127
1128
/// Return the view region that bounds access to a mutable content field.
1129
fn mutableView(self: &Resolver, node: *ast::Node) -> ?Region {
1130
    let ty = super::typeFor(self, node) else return nil;
1131
    if refersToBorrowed(self, ty) {
1132
        return outerRegion(self, node);
1133
    }
1134
    match node.value {
1135
        case ast::NodeValue::FieldAccess(access) => return mutableView(self, access.parent),
1136
        case ast::NodeValue::Bracket { base: container, .. } => return mutableView(self, container),
1137
        else => return nil,
1138
    }
1139
}
1140
1141
/// Whether a type is a direct mutable reference.
1142
fn mutableReference(ty: Type) -> bool {
1143
    match ty {
1144
        case Type::Pointer { class: types::PointerClass::Ref, mutable, .. } =>
1145
            return mutable,
1146
        case Type::Slice { class: types::PointerClass::Ref, mutable, .. } => return mutable,
1147
        else                                                              => return false,
1148
    }
1149
}
1150
1151
/// Set the region of the references that the value of symbol `sym` holds.
1152
export fn setSymbolRegion(self: &mut Resolver, sym: ?super::SymbolId, region: Region) {
1153
    let sym = sym else return;
1154
    let index = regionIndex(self, sym) else return;
1155
    set self.symbolRegions[index] = anchor(self, region, sym);
1156
}
1157
1158
/// Enter the subject of a pattern, whose regions its bindings take, and return
1159
/// the regions of the enclosing subject. A reference subject is matched through.
1160
export fn enterSubject(self: &mut Resolver, subject: *ast::Node) -> BindingRegions {
1161
    let outer = self.subject;
1162
    let mut value = valueRegion(self, subject);
1163
    if let ty = super::typeFor(self, subject) {
1164
        set value = target(self, value, ty);
1165
    }
1166
    set self.subject = BindingRegions { value, storage: outerRegion(self, subject), node: subject };
1167
    return outer;
1168
}
1169
1170
/// Number of region positions of a type: the region of a reference's address,
1171
/// then the positions of its target, or the region parameters of a record or
1172
/// union. Arrays and optionals have the positions of their contents. A heap
1173
/// handle, an unsafe pointer and data hold no references.
1174
export fn positions(self: &Resolver, ty: Type) -> u32 {
1175
    if super::heapRefKind(self, ty) <> nil {
1176
        return 0;
1177
    }
1178
    match ty {
1179
        case Type::Pointer { class, target, .. } => return viewPositions(self, class, *target),
1180
        case Type::Slice { class, item, .. }     => return viewPositions(self, class, *item),
1181
        case Type::TraitObject { class, .. } =>
1182
            return 1 if class == types::PointerClass::Ref and super::isTraitSlot(ty) else 0,
1183
        case Type::Optional(inner) => return positions(self, *inner),
1184
        case Type::Array(array)    => return positions(self, *array.item),
1185
        case Type::Nominal(id)     => return nominalRegions(self, id).len,
1186
        else                       => return 0,
1187
    }
1188
}
1189
1190
/// Number of region positions of a pointer or slice of class `class`.
1191
fn viewPositions(self: &Resolver, class: types::PointerClass, target: Type) -> u32 {
1192
    if class == types::PointerClass::Unsafe or target == Type::Opaque {
1193
        return 0;
1194
    }
1195
    let address: u32 = 1 if class == types::PointerClass::Ref else 0;
1196
    return address + positions(self, target);
1197
}
1198
1199
/// Map member region positions through the parameters of its enclosing type.
1200
export fn compose(mapping: *[u32], member: *[u32], arena: &heap::Heap) -> *[u32] {
1201
    if mapping.len == 0 {
1202
        return member;
1203
    }
1204
    let mut out: *mut [u32] = &mut [];
1205
    for index in member {
1206
        assert index < mapping.len;
1207
        try! out.append(mapping[index], arena);
1208
    }
1209
    return &out[..];
1210
}
1211
1212
/// One region position of a local value that a store can change.
1213
export record StoreTarget: Copy {
1214
    /// Local value whose dependencies change.
1215
    symbol: super::SymbolId,
1216
    /// Region position in the local value's type.
1217
    position: u32,
1218
}
1219
1220
/// One expression position that a store can reach.
1221
record StorePlace: Copy {
1222
    /// Expression that names the object.
1223
    node: *ast::Node,
1224
    /// Region position in the expression's type.
1225
    position: u32,
1226
}
1227
1228
/// Find local region positions reached by a store through an expression.
1229
/// Reference content also reaches the storage retained by its address.
1230
export fn storeTargets(
1231
    self: &Resolver, node: *ast::Node, position: u32, mode: StoreMode
1232
) -> *[StoreTarget] {
1233
    let mut pending: *mut [StorePlace] = &mut [];
1234
    let mut result: *mut [StoreTarget] = &mut [];
1235
    try! pending.append(StorePlace { node, position }, self.arena);
1236
    let mut cursor: u32 = 0;
1237
    while cursor < pending.len {
1238
        let place = pending[cursor];
1239
        let mut seen = false;
1240
        for i in 0 .. cursor {
1241
            if pending[i] == place {
1242
                set seen = true;
1243
                break;
1244
            }
1245
        }
1246
        set cursor += 1;
1247
        if seen {
1248
            continue;
1249
        }
1250
        let ty = super::typeFor(self, place.node) else continue;
1251
        if place.position >= positions(self, ty) {
1252
            continue;
1253
        }
1254
        if mode == StoreMode::Contents or (super::isRefType(ty) and place.position > 0) {
1255
            aliasTargets(self, place, &mut pending);
1256
        }
1257
        match place.node.value {
1258
            case ast::NodeValue::Ident(_), ast::NodeValue::ScopeAccess(_) => {
1259
                let symbol = super::symbolFor(self, place.node) else continue;
1260
                if regionIndex(self, symbol) == nil {
1261
                    continue;
1262
                }
1263
                let target = StoreTarget { symbol, position: place.position };
1264
                let mut known = false;
1265
                for i in 0 .. result.len {
1266
                    if result[i] == target {
1267
                        set known = true;
1268
                        break;
1269
                    }
1270
                }
1271
                if not known {
1272
                    try! result.append(target, self.arena);
1273
                }
1274
            }
1275
            case ast::NodeValue::AddressOf(address) => {
1276
                if place.position > 0 {
1277
                    try! pending.append(
1278
                        StorePlace {
1279
                            node: address.target, position: place.position - 1
1280
                        },
1281
                        self.arena
1282
                    );
1283
                }
1284
            }
1285
            case ast::NodeValue::FieldAccess(access) => {
1286
                let parent = super::typeFor(self, access.parent) else continue;
1287
                let index = super::recordFieldIndexFor(self, access.child) else continue;
1288
                let field = super::getRecordField(self, super::autoDeref(parent), index)
1289
                    else continue;
1290
                if place.position < field.regions.len {
1291
                    let offset: u32 = 1 if super::isRefType(parent) else 0;
1292
                    try! pending.append(
1293
                        StorePlace {
1294
                            node: access.parent, position: offset + field.regions[place.position]
1295
                        },
1296
                        self.arena
1297
                    );
1298
                }
1299
            }
1300
            case ast::NodeValue::Bracket { base: container, .. } => {
1301
                let parent = super::typeFor(self, container) else continue;
1302
                let offset: u32 = 1 if super::isRefType(parent) else 0;
1303
                try! pending.append(
1304
                    StorePlace {
1305
                        node: container, position: place.position + offset
1306
                    },
1307
                    self.arena
1308
                );
1309
            }
1310
            case ast::NodeValue::Deref(parent) => {
1311
                let parentTy = super::typeFor(self, parent) else continue;
1312
                let offset: u32 = 1 if super::isRefType(parentTy) else 0;
1313
                try! pending.append(
1314
                    StorePlace {
1315
                        node: parent, position: place.position + offset
1316
                    },
1317
                    self.arena
1318
                );
1319
            }
1320
            case ast::NodeValue::Try(value) => {
1321
                try! pending.append(
1322
                    StorePlace {
1323
                        node: value.expr, position: place.position
1324
                    },
1325
                    self.arena
1326
                );
1327
            }
1328
            case ast::NodeValue::As(value) => {
1329
                try! pending.append(
1330
                    StorePlace {
1331
                        node: value.value, position: place.position
1332
                    },
1333
                    self.arena
1334
                );
1335
            }
1336
            case ast::NodeValue::CondExpr(value) => {
1337
                try! pending.append(
1338
                    StorePlace {
1339
                        node: value.thenExpr, position: place.position
1340
                    },
1341
                    self.arena
1342
                );
1343
                try! pending.append(
1344
                    StorePlace {
1345
                        node: value.elseExpr, position: place.position
1346
                    },
1347
                    self.arena
1348
                );
1349
            }
1350
            case ast::NodeValue::Call(_) => {
1351
                let info = super::borrowedFunction(self, place.node) else {
1352
                    constructorTargets(self, place, &mut pending);
1353
                    continue;
1354
                };
1355
                for borrow in info.borrows {
1356
                    if borrow.result <> place.position {
1357
                        continue;
1358
                    }
1359
                    let argument = super::borrowedInput(self, place.node, borrow.param);
1360
                    let actual = super::typeFor(self, argument) else continue;
1361
                    let expected = *info.paramTypes[borrow.param];
1362
                    let mut position = borrow.source;
1363
                    if super::isRefType(expected) and not super::isRefType(actual) {
1364
                        if position == 0 {
1365
                            continue;
1366
                        }
1367
                        set position -= 1;
1368
                    }
1369
                    try! pending.append(StorePlace { node: argument, position }, self.arena);
1370
                }
1371
            }
1372
            case ast::NodeValue::RecordLit(_) => constructorTargets(self, place, &mut pending),
1373
            case ast::NodeValue::ArrayLit(items) => {
1374
                for item in items {
1375
                    try! pending.append(
1376
                        StorePlace { node: item, position: place.position }, self.arena
1377
                    );
1378
                }
1379
            }
1380
            case ast::NodeValue::ArrayRepeatLit(repeat) => {
1381
                try! pending.append(
1382
                    StorePlace { node: repeat.item, position: place.position }, self.arena
1383
                );
1384
            }
1385
            else => {}
1386
        }
1387
    }
1388
    return &result[..];
1389
}
1390
1391
/// Add dependencies to one local position and keep its declared region bound.
1392
export fn retainPosition(self: &mut Resolver, target: StoreTarget, value: Region) {
1393
    if sources(value).len == 0 {
1394
        return;
1395
    }
1396
    let index = regionIndex(self, target.symbol) else return;
1397
    let case SymbolData::Value { type: ty, .. } = self.symbols[*target.symbol].data else return;
1398
    let previous = self.symbolRegions[index];
1399
    let mut parts: *mut [Region] = &mut [];
1400
    for i in 0 .. positions(self, ty) {
1401
        let original = part(previous, i);
1402
        let mut updated = original;
1403
        if i == target.position {
1404
            let joined = joinRegion(self, original, value);
1405
            set updated = dependency(self, bound(original), sources(joined));
1406
        }
1407
        try! parts.append(updated, self.arena);
1408
    }
1409
    setSymbolRegion(self, target.symbol, bundle(self, &parts[..]));
1410
}
1411
1412
/// A value whose source loans continue during evaluation or in stored content.
1413
export union Retention {
1414
    /// A value retained until its enclosing expression ends.
1415
    Temporary(*ast::Node),
1416
    /// One position written into a value and the storage reached through it.
1417
    Stored {
1418
        /// Expression that receives the source.
1419
        node: *ast::Node,
1420
        /// Region position in the expression's type.
1421
        position: u32,
1422
        /// Source references written at this position.
1423
        value: Region,
1424
        /// Whether the store can follow references inside the value.
1425
        mode: StoreMode,
1426
    },
1427
}
1428
1429
/// Whether a pattern binds a complete subject or compares a case.
1430
export union PatternMode: Copy {
1431
    /// Bind the subject, or its present optional value.
1432
    Bind,
1433
    /// Bind only the variables inside a case pattern.
1434
    Compare,
1435
}
1436
1437
/// Refresh a pattern from the current sources of its subject.
1438
export fn refreshPattern(
1439
    self: &mut Resolver, pattern: *ast::Node, subject: *ast::Node, mode: PatternMode
1440
) {
1441
    let ty = super::typeFor(self, subject) else return;
1442
    let matched = super::unwrapMatchSubject(ty);
1443
    let mut payload = matched.effectiveTy;
1444
    if mode == PatternMode::Bind {
1445
        if let case Type::Optional(inner) = payload {
1446
            set payload = *inner;
1447
        }
1448
    }
1449
    let value = valueRegion(self, subject);
1450
    let regions = BindingRegions {
1451
        value: target(self, value, ty) if matched.by <> super::MatchBy::Value else value,
1452
        storage: outerRegion(self, subject),
1453
        node: subject,
1454
    };
1455
    refreshPatternRegions(self, pattern, payload, regions, matched.by, mode);
1456
}
1457
1458
/// Add the current sources of a value to the declared positions of its binding.
1459
export fn refreshBindingRegions(self: &mut Resolver, binding: super::SymbolId, value: Region) {
1460
    let case super::SymbolData::Value { type: ty, .. } = self.symbols[*binding].data else return;
1461
    for position in 0 .. positions(self, ty) {
1462
        retainPosition(self, StoreTarget { symbol: binding, position }, part(
1463
            value, position
1464
        ));
1465
    }
1466
}
1467
1468
/// Update the dependencies of resolved pattern bindings from the current subject.
1469
/// `regions` describes the value, its storage, and the expression that retains it.
1470
fn refreshPatternRegions(
1471
    self: &mut Resolver,
1472
    pattern: *ast::Node,
1473
    ty: Type,
1474
    regions: BindingRegions,
1475
    by: super::MatchBy,
1476
    mode: PatternMode
1477
) {
1478
    if let case Type::Optional(inner) = ty {
1479
        if super::isDestructuringPattern(pattern) {
1480
            refreshPatternRegions(self, pattern, *inner, regions, by, mode);
1481
            return;
1482
        }
1483
    }
1484
    if let case Type::Pointer { target: pointee, .. } = ty; super::isDestructuringPattern(pattern) {
1485
        let mut inner = regions;
1486
        set inner.storage = part(regions.value, 0)
1487
            if super::isRefType(ty)
1488
            else regions.storage;
1489
        set inner.value = target(self, regions.value, ty);
1490
        refreshPatternRegions(self, pattern, *pointee, inner, by, mode);
1491
        return;
1492
    }
1493
    match pattern.value {
1494
        case ast::NodeValue::Ident(_) => {
1495
            if mode <> PatternMode::Bind {
1496
                return;
1497
            }
1498
            let symbol = super::symbolFor(self, pattern) else return;
1499
            let bindTy = super::typeFor(self, pattern) else return;
1500
            let mut value = regions.value;
1501
            if by <> super::MatchBy::Value {
1502
                let mut address = regions.storage;
1503
                if let subject = regions.node {
1504
                    set address = borrow(self, subject, address, false);
1505
                }
1506
                set value = reference(self, address, value, positions(
1507
                    self, bindTy
1508
                ));
1509
            }
1510
            refreshBindingRegions(self, symbol, value);
1511
        }
1512
        case ast::NodeValue::Call(_), ast::NodeValue::RecordLit(_) => {
1513
            let case Type::Nominal(id) = ty else return;
1514
            match self.nominals[*id] {
1515
                case NominalType::Record(info) =>
1516
                    refreshRecordPatternRegions(self, pattern, &info, regions, by),
1517
                case NominalType::Union(info) => {
1518
                    let key = super::patternVariantKeyNode(pattern) else return;
1519
                    let case super::NodeExtra::UnionVariant { ordinal, .. } =
1520
                        super::nodeData(self, key).extra else return;
1521
                    let variant = info.variants[ordinal];
1522
                    let payload = super::getRecord(self, variant.valueType) else return;
1523
                    let mut inner = regions;
1524
                    set inner.value = project(self, regions.value, variant.regions);
1525
                    refreshRecordPatternRegions(self, pattern, &payload, inner, by);
1526
                }
1527
                else => {}
1528
            }
1529
        }
1530
        case ast::NodeValue::ArrayLit(items) => {
1531
            let case Type::Array(info) = ty else return;
1532
            for item in items {
1533
                refreshPatternRegions(self, item, *info.item, regions, by, PatternMode::Bind);
1534
            }
1535
        }
1536
        else => {}
1537
    }
1538
}
1539
1540
/// Project the current dependencies of a record into its resolved field patterns.
1541
fn refreshRecordPatternRegions(
1542
    self: &mut Resolver,
1543
    pattern: *ast::Node,
1544
    info: &super::RecordType,
1545
    regions: BindingRegions,
1546
    by: super::MatchBy
1547
) {
1548
    match pattern.value {
1549
        case ast::NodeValue::Call(call) => {
1550
            for argument, index in call.args {
1551
                let field = info.fields[index];
1552
                let mut inner = regions;
1553
                set inner.value = project(self, regions.value, field.regions);
1554
                refreshPatternRegions(
1555
                    self, argument, field.fieldType, inner, by, PatternMode::Bind
1556
                );
1557
            }
1558
        }
1559
        case ast::NodeValue::RecordLit(lit) => {
1560
            for node in lit.fields {
1561
                let case ast::NodeValue::RecordLitField(field) = node.value else continue;
1562
                let index = super::recordFieldIndexFor(self, node) else continue;
1563
                let member = info.fields[index];
1564
                let mut inner = regions;
1565
                set inner.value = project(self, regions.value, member.regions);
1566
                refreshPatternRegions(
1567
                    self, field.value, member.fieldType, inner, by, PatternMode::Bind
1568
                );
1569
            }
1570
        }
1571
        else => {}
1572
    }
1573
}
1574
1575
/// Follow a constructor's field map to the arguments that supply one position.
1576
fn constructorTargets(self: &Resolver, place: StorePlace, out: &mut *mut [StorePlace]) {
1577
    let parts = constructorParts(self, place.node) else return;
1578
    for arg, i in parts.args {
1579
        let mut value = arg;
1580
        let mut index = i;
1581
        if let case ast::NodeValue::RecordLitField(field) = arg.value {
1582
            set value = field.value;
1583
            let resolved = super::recordFieldIndexFor(self, arg)
1584
                else panic "constructorTargets: unresolved field";
1585
            set index = resolved;
1586
        }
1587
        let mapping = parts.fields[index].regions if parts.fields.len > 0 else parts.mapping;
1588
        for region, position in mapping {
1589
            if region == place.position {
1590
                try! out.append(StorePlace { node: value, position }, self.arena);
1591
            }
1592
        }
1593
    }
1594
}
1595
1596
/// A value type whose region positions map into the stored expression.
1597
record AliasView: Copy {
1598
    /// Type that can contain a reference to other storage.
1599
    type: Type,
1600
    /// Positions in the stored expression, in the order of this type.
1601
    mapping: *[u32],
1602
}
1603
1604
/// Follow references inside a value to the local storage of its content.
1605
/// Type maps preserve the distinct region positions of records and unions.
1606
fn aliasTargets(
1607
    self: &Resolver, place: StorePlace, out: &mut *mut [StorePlace]
1608
) {
1609
    let ty = super::typeFor(self, place.node) else return;
1610
    let value = storedRegion(self, place.node);
1611
    let mut identity: *mut [u32] = &mut [];
1612
    for i in 0 .. positions(self, ty) {
1613
        try! identity.append(i, self.arena);
1614
    }
1615
    let mut views: *mut [AliasView] = &mut [];
1616
    try! views.append(AliasView { type: ty, mapping: &identity[..] }, self.arena);
1617
    let mut cursor: u32 = 0;
1618
    while cursor < views.len {
1619
        let view = views[cursor];
1620
        let mut seen = false;
1621
        for i in 0 .. cursor {
1622
            let previous = views[i];
1623
            if previous.type <> view.type or previous.mapping.len <> view.mapping.len {
1624
                continue;
1625
            }
1626
            let mut same = true;
1627
            for region, k in view.mapping {
1628
                if previous.mapping[k] <> region {
1629
                    set same = false;
1630
                    break;
1631
                }
1632
            }
1633
            if same {
1634
                set seen = true;
1635
                break;
1636
            }
1637
        }
1638
        set cursor += 1;
1639
        if seen {
1640
            continue;
1641
        }
1642
        if super::isRefType(view.type) {
1643
            for region, position in view.mapping {
1644
                if position == 0 or region <> place.position {
1645
                    continue;
1646
                }
1647
                for source in sources(part(value, view.mapping[0])) {
1648
                    let sourceTy = super::typeFor(self, source.node) else continue;
1649
                    let position = aliasPosition(self, view.type, sourceTy, position) else continue;
1650
                    try! out.append(StorePlace { node: source.node, position }, self.arena);
1651
                }
1652
            }
1653
            continue;
1654
        }
1655
        match view.type {
1656
            case Type::Pointer { target, .. } =>
1657
                try! views.append(AliasView { type: *target, mapping: view.mapping }, self.arena),
1658
            case Type::Slice { item, .. } =>
1659
                try! views.append(AliasView { type: *item, mapping: view.mapping }, self.arena),
1660
            case Type::Optional(inner) =>
1661
                try! views.append(AliasView { type: *inner, mapping: view.mapping }, self.arena),
1662
            case Type::Array(info) =>
1663
                try! views.append(
1664
                    AliasView { type: *info.item, mapping: view.mapping }, self.arena
1665
                ),
1666
            case Type::Nominal(id) => {
1667
                match self.nominals[*id] {
1668
                    case NominalType::Record(info) => {
1669
                        for field in info.fields {
1670
                            if field.regions.len > 0 {
1671
                                try! views.append(
1672
                                    AliasView {
1673
                                        type: field.fieldType,
1674
                                        mapping: compose(view.mapping, field.regions, self.arena),
1675
                                    },
1676
                                    self.arena
1677
                                );
1678
                            }
1679
                        }
1680
                    }
1681
                    case NominalType::Union(info) => {
1682
                        for variant in info.variants {
1683
                            if variant.regions.len > 0 {
1684
                                try! views.append(
1685
                                    AliasView {
1686
                                        type: variant.valueType,
1687
                                        mapping: compose(view.mapping, variant.regions, self.arena),
1688
                                    },
1689
                                    self.arena
1690
                                );
1691
                            }
1692
                        }
1693
                    }
1694
                    else => {}
1695
                }
1696
            }
1697
            else => {}
1698
        }
1699
    }
1700
}
1701
1702
/// Map a reference content position to a source with the same pointee type.
1703
/// An owning source or a borrowed place has no reference address position.
1704
fn aliasPosition(self: &Resolver, reference: Type, source: Type, position: u32) -> ?u32 {
1705
    let mut same = false;
1706
    match reference {
1707
        case Type::Pointer { target, .. } => {
1708
            if let case Type::Pointer { target: pointee, .. } = source {
1709
                set same = super::typesEqual(self, *target, *pointee);
1710
            } else {
1711
                set same = super::typesEqual(self, *target, source);
1712
            }
1713
        }
1714
        case Type::Slice { item, .. } => {
1715
            match source {
1716
                case Type::Slice { item: element, .. } =>
1717
                    set same = super::typesEqual(self, *item, *element),
1718
                case Type::Array(info) => set same = super::typesEqual(self, *item, *info.item),
1719
                else                   => {}
1720
            }
1721
        }
1722
        else => {}
1723
    }
1724
    if not same {
1725
        return nil;
1726
    }
1727
    return position if super::isRefType(source) else position - 1;
1728
}
1729
1730
/// Which storage a store can change at a value position.
1731
export union StoreMode: Copy {
1732
    /// The value of an explicit place.
1733
    Value,
1734
    /// The value and objects reached through its references.
1735
    Contents,
1736
}