.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
alloc/
ast/
gen/
il/
layout/
lower/
manifest/
module/
parser/
resolver/
tests/
metadata.rad
2.6 KiB
printer.rad
33.0 KiB
refs.rad
66.5 KiB
tests.rad
23.6 KiB
scanner/
sexpr/
alloc.rad
1.2 KiB
ast.rad
36.0 KiB
gen.rad
513 B
il.rad
48.5 KiB
layout.rad
6.9 KiB
lower.rad
487.6 KiB
manifest.rad
22.5 KiB
module.rad
17.8 KiB
package.rad
1.5 KiB
parser.rad
114.1 KiB
pretty.rad
103.6 KiB
resolver.rad
508.1 KiB
scanner.rad
19.3 KiB
sexpr.rad
7.1 KiB
strings.rad
3.3 KiB
types.rad
620 B
mem/
sys/
arch.rad
68 B
bits.rad
1.6 KiB
char.rad
1.5 KiB
collections.rad
39 B
fmt.rad
11.6 KiB
fs.rad
11.0 KiB
hash.rad
41 B
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
335 B
mem.rad
12.0 KiB
mem.ras
919 B
process.rad
6.2 KiB
std.manifest
4.9 KiB
std.rad
349 B
sys.rad
1.0 KiB
testing.rad
2.4 KiB
tests.rad
26.6 KiB
vec.rad
3.2 KiB
scripts/
seed/
sublime/
test/
vim/
.gitignore
333 B
.gitsigners
224 B
AGENTS.md
8.3 KiB
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
2.5 KiB
README
3.4 KiB
STYLE
3.2 KiB
std.lib
2.1 KiB
std.lib.test
1.1 KiB
lib/std/lang/resolver/refs.rad
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 ®ions[..]; |
| 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 | } |