class: center, middle .title[How NLL make life easier]
.center[
]
.author[Rnic / H.-S Zheng]
.date[April 17, 2019]
--- # About Me
Rnic / 鄭弘昇 ‣
Telegram: [{ t.me/rnicinr }](https://t.me/rnicinr) ‣
**Emacs**
教派的信徒 --- # Outline * .highlight[**Lifetimes Concept**] * What is Lifetimes ? * Subtyping * .highlight[**NLL**] * Phases of Borrow checker * Future: Polonius --- class: center, middle # Lifetimes Concept .center[
] --- # .center[Borrow] .center[
] .footnote[(by. https://rufflewind.com/img/rust-move-copy-borrow.png)] --
.center[**How long does it borrow ?**] -- .center[.highlight[**NLL:] What is can borrowed here ?**] --- # .center[Borrow] A .pink[borrow] will generate a .pink[reference], and a reference will tagged with a .pink[lifetime] ### Borrow -- → Reference -- --- Lifetime -- ```rust let r; { let x = 5; r = &x; } println!("{}", r); ``` --- # .center[Borrow] A .pink[borrow] will generate a .pink[reference], and a reference will tagged with a .pink[lifetime] ### Borrow → Reference --- Lifetime ```rust let r; { let x = 5; r = &'b x; // -+-- 'b // | *} // -+ println!("{}", r); // ``` --
## .pink[.center[**Lifetime must smaller than Scope**]] --- # .center[Lifetimes] ## .center[.highlight[Set of points on CFG]] --
.center[
] --- # .center[Lifetimes] .pull-left[ ```rust let mut foo: T = ...; let mut bar: T = ...; let p: &'p T; p = &'foo foo; if condition { print(*p); p = &'bar bar; } print(*p); ``` ] .pull-right[ .center[
] ] --- # .center[Lifetimes] .pull-left[ ```rust let mut foo: T = ...; let mut bar: T = ...; let p: &'p T; *p = &'foo foo; if condition { print(*p); p = &'bar bar; } print(*p); ``` ```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { A/1, B/0, C/0 } 'bar: { B/3, B/4, C/0 } ``` ] .pull-right[ .center[
] ] --- # .center[Lifetimes] ## Original Limits ```rust let mut s = "hello".to_string(); let mut c = || s += " world"; // captured by &mut and c become FnMut c(); println!("{}", s); ``` -- ``` | let mut c = || s += " world"; | -- - previous borrow occurs due to use of `s` in closure | | | mutable borrow occurs here | c(); | println!("{}", s); | ^ immutable borrow occurs here | } | - mutable borrow ends here ``` --- # .center[Lifetimes] ## How to solve it ? ```rust let mut s = "hello".to_string(); let mut c = || s += " world"; ---+--- 'a | c(); | | println!("{}", s); -----+--- 'b | ------+ ``` -- ```rust let mut s = "hello".to_string(); * { let mut c = || s += " world"; ---+--- 'a | c(); | * } ----+ println!("{}", s); ----+--- 'b ``` --- # .center[Subtyping] .center[`'a : 'b` : lifetimes of `'a` is outlives `'b`] -- ```rust let p: &'p T; +--------+ | | p = &'foo foo; 'foo +----+ Borrow +----> 'p | | +--------+ ``` --- # .center[Subtyping] .center[`'a : 'b` : lifetimes of `'a` is outlives `'b`] ```rust let p: &'p T; +--------+ | | p = &'foo foo; 'foo +----+ : +----> 'p | | ______________ +--------+ 'foo : 'p ``` --- # .center[Variance] .pull-left[
'a
T
U
&'a T
covariant
covariant
&'a mut T
covariant
invariant
Box<T>
covariant
Vec<T>
covariant
UnsafeCell<T>
invariant
Cell<T>
invariant
fn(T) -> U
contravariant
covariant
*const T
covariant
*mut T
invariant
] .pull-right[ ``` +---+---+---+---+ | X | 0 | + | - | +---------------+ 0: invariant | 0 | 0 | 0 | 0 | +: convariant +---------------+ -: contravariant | + | 0 | + | - | +---------------+ | - | 0 | - | + | +---+---+---+---+ +---+---+---+---+ | ^ | 0 | + | - | +---------------+ | 0 | 0 | 0 | 0 | +---------------+ | + | 0 | + | 0 | +---------------+ | - | 0 | 0 | - | +---+---+---+---+ ``` ] .footnote[(by. https://medium.com/@kennytm/variance-in-rust-964134dd5b3e)] --- ## .center[Example] ```rust let a = 5; let b = &a; ``` --- ## .center[Example] ```rust let a = 5; let b: &'b i32 = &'a a; _______________________ 'a : 'b ``` -- ```rust let x = 5; let p = Cell::new(&x); ``` --- ## .center[Example] ```rust let a = 5; let b: &'b i32 = &'a a; _______________________ 'a : 'b ``` ```rust let x = 5; let p: Cell<&'p i32> = Cell::new(&'x x); ________________________________________ 'x: 'p 'p: 'x ``` --- class: center, middle # NLL .center[
] --- ## .center[Problem] .footnote[[(play: link to play.rust-lang.org/ of this code with eidtion=2015)](https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=6deffeeb7145662d49b87dbe35dee1a1)] ```rust fn process_or_default(map: &mut HashMap
, key: usize) { match map.get_mut(&key) { Some(value) => { process(value); return; } None => { map.insert(key, V::default()); } } } ``` --- ## .center[Problem] .footnote[[(play: link to play.rust-lang.org/ of this code with eidtion=2015)](https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=6deffeeb7145662d49b87dbe35dee1a1)] ```rust fn process_or_default(map: &mut HashMap
, key: usize) { match map.get_mut(&key) { --------------+-- 'a Some(value) => { | process(value); | return; | } | None => { | map.insert(key, V::default()); ----- 'b } | } <--------------------------------------+ } ``` ``` | match map.get_mut(&key) { | --- first mutable borrow occurs here ... | map.insert(key, V::default()); | ^^^ second mutable borrow occurs here | } | } | - first borrow ends here ``` --- ## .center[Solution] .footnote[[(play: link to play.rust-lang.org/ of this code with eidtion=2015)](https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=6deffeeb7145662d49b87dbe35dee1a1)] ```rust fn process_or_default(map: &mut HashMap
, key: usize) { match map.get_mut(&key) { Some(value) => { process(value); return; } None => { * } } * map.insert(key, V::default()); } ``` --
## .center[.pink[But it's annoying]] --- # .center[Phases of Borrowck]
### 1. Build liveness and constraints ### 2. Infer the lifetimes ### 3. Compute loans in scope ### 4. Check action and report errors --- class: center, middle # Demo .footnote[(ref. Prototype of NLL https://github.com/nikomatsakis/borrowck)] --- # .center[Location-aware subtyping]
.center[`'a : 'b` : Lifetimes of `'a` must outlives `'b` ] --- # .center[Location-aware subtyping]
.center[`('a : 'b) @ P` : `'a` must include all points in `'b` .pink[**that are reachable from**] location `P` ] -- .center[.highlight[**Doing DFS on CFG**]] --- ## 1. Build liveness and contraints .pull-left[ ```rust let foo = 2; let bar = 5; let mut p: &i32; p = &foo; if condition { do_something(p); p = &bar; } do_something(p); ``` ] .pull-right[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] --- ## 1. Build .highlight[liveness] and contraints > **liveness**: > a variable 𝑣 is live at point 𝑝 if and only if > there exists a path in CFG from 𝑝 to a use of 𝑣 along which 𝑣 is not redefined. .pull-right[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] --- ## 1. Build .highlight[liveness] and contraints > **liveness**: > a variable 𝑣 is .pink[**live at point 𝑝**] if and only if > there exists a path in CFG .pink[**from 𝑝 to a use of 𝑣**] along which 𝑣 is not redefined. .pull-right[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] -- .pull-left[ ```rust 'p: { 'foo: { 'bar: { ``` ] --- ## 1. Build .highlight[liveness] and contraints > **liveness**: > a variable 𝑣 is .pink[**live at point 𝑝**] if and only if > there exists a path in CFG .pink[**from 𝑝 to a use of 𝑣**] along which 𝑣 is not redefined. .pull-right[ ```rust A 0[ p = &foo ] *1[ if condition ]----\ (true) | | | B v * | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] * | 3[ ... ] * | 4[ goto C ] | | +-------------/ | C v *0[ do_something(p) ] 1[ return ] ``` ] .pull-left[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 'foo: { 'bar: { ``` ] --- ## 1. Build liveness and .highlight[contraints] > **contraints**: > It's lifetime contraints which is converted from subtyping rule. .pull-right[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] .pull-left[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 'foo: { 'bar: { ``` ] --- ## 1. Build liveness and .highlight[contraints] > **contraints**: > It's lifetime contraints which is .pink[**converted from subtyping rule**], e.g. `(&'a T : &'b U)` will convert to `('a : 'b)`. .pull-right[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] .pull-left[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 'foo: { 'bar: { ``` ] --- ## 1. Build liveness and .highlight[contraints] > **contraints**: > It's lifetime contraints which is .pink[**converted from subtyping rule**], e.g. `(&'a T : &'b U)` will convert to `('a : 'b)`. .pull-right[ ```rust p: &'p T; A 0[ p = &'foo foo ] 1[ if condition ]---\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &'bar bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] .pull-left[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 'foo: { 'bar: { ``` ] --- ## 1. Build liveness and .highlight[contraints] > **contraints**: > It's lifetime contraints which is .pink[**converted from subtyping rule**], e.g. `(&'a T : &'b U)` will convert to `('a : 'b)`. .pull-right[ ```rust p: &'p T; A 0[ p = &'foo foo ] 1[ if condition ]---\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &'bar bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] .pull-left[
-
**( .pink['foo : 'p] ) .purple[@ A/0]**
] -- .pull-left[ -
**( .pink['bar : 'p] ) .purple[@ B/2]**
] --- ## 1. Build liveness and .highlight[contraints] > **contraints**: > It's lifetime contraints which is .pink[**converted from subtyping rule**], e.g. `(&'a T : &'b U)` will convert to `('a : 'b)`. ```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { 'bar: { `('foo : 'p) @ A/0` `('bar : 'p) @ B/2` ``` -- .center[ ### Infer the lifetimes ] .center[ ### .highlight[**Solving contraints (use DFS)**] ] --- ## 2. Infer lifetimes (solving contraints) .pull-left[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] .pull-right[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { 'bar: { ('foo : 'p) @ A/0 ('bar : 'p) @ B/2 ``` ] --- ## 2. Infer lifetimes (solving contraints) .pull-left[ ```rust A >> 0[ p = &foo ] *1[ if condition ]----\ (true) | | | B v * | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v *0[ do_something(p) ] 1[ return ] ``` ] .pull-right[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { 'bar: { >>('foo : 'p) @ A/0 ('bar : 'p) @ B/2 ``` ] --- ## 2. Infer lifetimes (solving contraints) .pull-left[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] | 2[ p = &bar ] | 3[ ... ] | 4[ goto C ] | | +-------------/ | C v 0[ do_something(p) ] 1[ return ] ``` ] .pull-right[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { A/1, B/0, C/0 'bar: { ('foo : 'p) @ A/0 ('bar : 'p) @ B/2 ``` ] --- ## 2. Infer lifetimes (solving contraints) .pull-left[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] >> | 2[ p = &bar ] * | 3[ ... ] * | 4[ goto C ] | | +-------------/ | C v *0[ do_something(p) ] 1[ return ] ``` ] .pull-right[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { A/1, B/0, C/0 'bar: { ('foo : 'p) @ A/0 >>('bar : 'p) @ B/2 ``` ] --- ## 2. Infer lifetimes (solving contraints) .pull-left[ ```rust A 0[ p = &foo ] 1[ if condition ]----\ (true) | | | B v | 0[ do_something(p) ] | 1[ ... ] >> | 2[ p = &bar ] * | 3[ ... ] * | 4[ goto C ] | | +-------------/ | C v *0[ do_something(p) ] 1[ return ] ``` ] .pull-right[ ```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { A/1, B/0, C/0 'bar: { B/3, B/4, C/0 ('foo : 'p) @ A/0 ('bar : 'p) @ B/2 ``` ] --- ## 2. Infer lifetimes (solving contraints)
```rust 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { A/1, B/0, C/0 } 'bar: { B/3, B/4, C/0 } ``` .center[
✔
] --- ## 3. Compute loans in scope > **loans**: a set of borrow expressions ```rust A/0 [ p = &'foo foo; ] // loan L0 ``` ```rust loan L0 { point: A/0, path: foo, kind: shared, region 'foo { A/1, B/0, C/0 } } ``` --- ## 3. Compute loans in scope > **loans**: a set of borrow expressions Borrow checker will compute loans at each point via .pink[**fixed-point dataflow computation**] with .pink[**transfer function**]: ```text - Kill Li @ P If P ∉ Li.region - Gen Li @ P If Borrow expression occur @ P - Kill Li @ P If LV is redefined && LV ∈ Li.path ``` --- ## 3. Compute loans in scope ```rust CFG Loans @ each point A 0[ p = &foo ] "gen L0" path: foo, region: { A/1, B/0, C/0 } 1[ if condition ]----\ (true) L0 | | | B v | 0[ do_something(p) ] L0 | 1[ ... ] "kill L0" (rule 1) | 2[ p = &bar ] "gen L1" path: bar, region: { B/3, B/4, C/0 } | 3[ ... ] L1 | 4[ goto C ] L1 | | +-------------/ | v 0[ do_something(p) ] L0, L1 1[ return ] "kill L0, L1" Regions _________________________________ 'p: { A/1, B/0, B/3, B/4, C/0 } 'foo: { A/1, B/0, C/0 } 'bar: { B/3, B/4, C/0 } ``` --- ## 3. Compute loans in scope > Another example: .pull-left[ ```rust let mut x = 22; let y = 44; let mut p = &x; * p = &y; x += 1; use(*p); ``` ] .pull-right[ .center[
] ] --- ## 3. Compute loans in scope > Another example: .pull-left[ ```rust let mut x = 22; let y = 44; let mut p = &x; p = &y; * x += 1; use(*p); ``` ] .pull-right[ .center[
] ] --- ## 3. Compute loans in scope > Another example: .pull-left[ ```rust let mut x = 22; let y = 44; let mut p = &x; p = &y; x += 1; * use(*p); ``` ] .pull-right[ .center[
] ] --- ## 3. Compute loans in scope > Another example: .pull-left[ ```rust let mut x = 22; let y = 44; let mut p = &x; "L0" p = &y; "gen L1" x += 1; "kill L0" use(*p); ``` ] .pull-right[ .center[
] ] --- ## 4. Check action and report Error Check action at each point which dependent on loans we computed before. ```rust fn access_legal(lvalue, is_shallow, is_read) { let relevant_borrows = select_relevant_borrows(lvalue, is_shallow); for borrow in relevant_borrows { // shared borrows like `&x` still permit reads from `x` (but not writes) if is_read && borrow.is_read { continue; } // otherwise, report an error, because we have an access // that conflicts with an in-scope borrow report_error(); } } ``` .pull-left[
read
write
shallow
storageDead()
lvalue
deep
rvalue(copy)
&lvalue
rvalue(move)
&mut lvalue
Drop(lvalue)
] .pull-right[ lvalue =
rvalue
; ```rust x = x + 1 // shallow access to lvalue x ``` ] --- # .center[We Make it !] -- ```rust A/0 | let mut x = 42; A/1 | let y = &x; A/2 | x += 1; ``` -- ``` x: { A/0, A/1, A/2 } y: { A/1 } ``` -- ⇒ y is not live at A/2 -- ⇒ Legal for you to write x --- class: center, middle # Future: Polonius .center[
] --- # .center[Polonius] - He is chief counsellor of the king - A busy-body, [who] is accordingly officious, garrulous, and impertinent - Polonius hides himself behind an arras in Gertrude's room. Hamlet deals roughly with his mother, causing her to cry for help. Polonius echoes the request for help and is heard by Hamlet, who then mistakes the voice for Claudius' and stabs through the arras and kills him. .footnote[(ref. https://en.wikipedia.org/wiki/Polonius)] --- ## .center[Problem] .footnote[(ref. [an aliased-based formulation of the borrow checker](http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-alias-based-formulation-of-the-borrow-checker) )] .center[We want to traversal the Thing and loop forever] ```rust struct Thing; impl Thing { fn maybe_next(&mut self) -> Option<&mut Self> { None } } fn main() { let mut temp = &mut Thing; loop { match temp.maybe_next() { Some(v) => { temp = v; } None => { } } } } ``` --- ## .center[Problem] .footnote[(ref. [an aliased-based formulation of the borrow checker](http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-alias-based-formulation-of-the-borrow-checker) )] .center[We want to traversal the Thing and loop forever] ```rust struct Thing; impl Thing { fn maybe_next(&mut self) -> Option<&mut Self> { None } } fn main() { let mut temp = &mut Thing; loop { match temp.maybe_next() { ^^^^ "mutable borrow starts here in previous iteration of loop" Some(v) => { temp = v; } None => { } } } } ``` -- .pink[**Reason:**] In `None` arm, `temp` was not reassigned. -- .pink[**Why accepted in the future?**] -- 1. `Some` path: Killed the `loan` 2. `None` path: `requires relation` is dropped. --- ## .center[Problem] .footnote[(ref. [an aliased-based formulation of the borrow checker](http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-alias-based-formulation-of-the-borrow-checker) )] .center[We want to traversal the Thing and loop forever] ```rust struct Thing; impl Thing { fn maybe_next(&mut self) -> Option<&mut Self> { None } } fn main() { let mut temp = &mut Thing; loop { match temp.maybe_next() { ^^^^ "mutable borrow starts here in previous iteration of loop" Some(v) => { temp = v; } None => { } } } } ``` ```rust R1 live @ P R1 require L @ P ________________ L live @ p ``` --- class: center ## What is change ? --
.center[.pink[**Region 'a:**] Set of points in CFG] ```rust { A/0, A/1, ... } ``` --- class: center ## What is change ?
.center[.pink[**Region 'a:**] ~~Set of points in CFG]~~ **Set of Loans** ```rust { L0, L1 ... } ``` --
And with some rules, but I'm not mentioned in this talk, e.g. `require_relation`, `borrow_region`...etc --- ## .center[I have not mentioned in this talk]
- **Reborrow contraints :** supporting prefixes rule - **Infinite Loops :** add unwind edge - **Drop variable :** [may_dangle] → not consider live - **Named Lifetimes** : add end_regions --- ## .center[I have not mentioned in this talk]
- **Reborrow contraints :** supporting prefixes rule - **Infinite Loops :** add unwind edge - **Drop variable :** [may_dangle] → not consider live ```rust &'a T // 'a is [may_dangle] Foo<'a> and you impl Drop // 'a cannot dangle ``` - **Named Lifetimes** : add end_regions --- # Command ```rust "Gen MIR information:" rustc --dump-mir=main src/main.rs "or" rustc -Z unpretty=mir src/main.rs "Test NLL Borrowck prototype:" env NLL_DEBUG=true cargo run ../test/foobar.nll ``` --- # .center[reference] (subtype: https://doc.rust-lang.org/nomicon/subtyping.html) (variance: https://medium.com/@kennytm/variance-in-rust-964134dd5b3e) (nll: https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md) (alias-based-formulation: http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-alias-based-formulation-of-the-borrow-checker/) --- class: center, middle # That's All. # QA
.center[
**Rust Taiwan @ https://t.me/rust_tw **]