diff options
Diffstat (limited to 'src/librustc')
| -rw-r--r-- | src/librustc/driver.rs | 5 | ||||
| -rw-r--r-- | src/librustc/driver/mod.rs | 8 | ||||
| -rw-r--r-- | src/librustc/metadata.rs | 31 | ||||
| -rw-r--r-- | src/librustc/metadata/mod.rs | 33 | ||||
| -rw-r--r-- | src/librustc/middle/borrowck.rs | 618 | ||||
| -rw-r--r-- | src/librustc/middle/borrowck/mod.rs | 620 | ||||
| -rw-r--r-- | src/librustc/middle/typeck.rs | 376 | ||||
| -rw-r--r-- | src/librustc/middle/typeck/mod.rs | 377 | ||||
| -rw-r--r-- | src/librustc/rustc.rc | 10 |
9 files changed, 1042 insertions, 1036 deletions
diff --git a/src/librustc/driver.rs b/src/librustc/driver.rs deleted file mode 100644 index cbe6345a9f1..00000000000 --- a/src/librustc/driver.rs +++ /dev/null @@ -1,5 +0,0 @@ -use syntax::diagnostic; -export diagnostic; - -export driver; -export session; diff --git a/src/librustc/driver/mod.rs b/src/librustc/driver/mod.rs index 7d9a55571d4..a9d5afeb522 100644 --- a/src/librustc/driver/mod.rs +++ b/src/librustc/driver/mod.rs @@ -1,4 +1,12 @@ #[legacy_exports]; + +use syntax::diagnostic; + +export diagnostic; + +export driver; +export session; + #[legacy_exports] mod driver; #[legacy_exports] diff --git a/src/librustc/metadata.rs b/src/librustc/metadata.rs deleted file mode 100644 index 2d2d6a3f79e..00000000000 --- a/src/librustc/metadata.rs +++ /dev/null @@ -1,31 +0,0 @@ -// Define the rustc API's that the metadata module has access to -// Over time we will reduce these dependencies and, once metadata has -// no dependencies on rustc it can move into its own crate. - -mod middle { - #[legacy_exports]; - pub use middle_::ty; - pub use middle_::resolve; -} - -mod front { - #[legacy_exports]; -} - -mod back { - #[legacy_exports]; -} - -mod driver { - #[legacy_exports]; -} - -mod util { - #[legacy_exports]; - pub use util_::ppaux; -} - -mod lib { - #[legacy_exports]; - pub use lib_::llvm; -} diff --git a/src/librustc/metadata/mod.rs b/src/librustc/metadata/mod.rs index a82ad39d412..dfe983cc32b 100644 --- a/src/librustc/metadata/mod.rs +++ b/src/librustc/metadata/mod.rs @@ -30,3 +30,36 @@ mod csearch; mod loader; #[legacy_exports] mod filesearch; + + +// Define the rustc API's that the metadata module has access to +// Over time we will reduce these dependencies and, once metadata has +// no dependencies on rustc it can move into its own crate. + +mod middle { + #[legacy_exports]; + pub use middle_::ty; + pub use middle_::resolve; +} + +mod front { + #[legacy_exports]; +} + +mod back { + #[legacy_exports]; +} + +mod driver { + #[legacy_exports]; +} + +mod util { + #[legacy_exports]; + pub use util_::ppaux; +} + +mod lib { + #[legacy_exports]; + pub use lib_::llvm; +} diff --git a/src/librustc/middle/borrowck.rs b/src/librustc/middle/borrowck.rs deleted file mode 100644 index df573b121f8..00000000000 --- a/src/librustc/middle/borrowck.rs +++ /dev/null @@ -1,618 +0,0 @@ -/*! -# Borrow check - -This pass is in job of enforcing *memory safety* and *purity*. As -memory safety is by far the more complex topic, I'll focus on that in -this description, but purity will be covered later on. In the context -of Rust, memory safety means three basic things: - -- no writes to immutable memory; -- all pointers point to non-freed memory; -- all pointers point to memory of the same type as the pointer. - -The last point might seem confusing: after all, for the most part, -this condition is guaranteed by the type check. However, there are -two cases where the type check effectively delegates to borrow check. - -The first case has to do with enums. If there is a pointer to the -interior of an enum, and the enum is in a mutable location (such as a -local variable or field declared to be mutable), it is possible that -the user will overwrite the enum with a new value of a different -variant, and thus effectively change the type of the memory that the -pointer is pointing at. - -The second case has to do with mutability. Basically, the type -checker has only a limited understanding of mutability. It will allow -(for example) the user to get an immutable pointer with the address of -a mutable local variable. It will also allow a `@mut T` or `~mut T` -pointer to be borrowed as a `&r.T` pointer. These seeming oversights -are in fact intentional; they allow the user to temporarily treat a -mutable value as immutable. It is up to the borrow check to guarantee -that the value in question is not in fact mutated during the lifetime -`r` of the reference. - -# Definition of unstable memory - -The primary danger to safety arises due to *unstable memory*. -Unstable memory is memory whose validity or type may change as a -result of an assignment, move, or a variable going out of scope. -There are two cases in Rust where memory is unstable: the contents of -unique boxes and enums. - -Unique boxes are unstable because when the variable containing the -unique box is re-assigned, moves, or goes out of scope, the unique box -is freed or---in the case of a move---potentially given to another -task. In either case, if there is an extant and usable pointer into -the box, then safety guarantees would be compromised. - -Enum values are unstable because they are reassigned the types of -their contents may change if they are assigned with a different -variant than they had previously. - -# Safety criteria that must be enforced - -Whenever a piece of memory is borrowed for lifetime L, there are two -things which the borrow checker must guarantee. First, it must -guarantee that the memory address will remain allocated (and owned by -the current task) for the entirety of the lifetime L. Second, it must -guarantee that the type of the data will not change for the entirety -of the lifetime L. In exchange, the region-based type system will -guarantee that the pointer is not used outside the lifetime L. These -guarantees are to some extent independent but are also inter-related. - -In some cases, the type of a pointer cannot be invalidated but the -lifetime can. For example, imagine a pointer to the interior of -a shared box like: - - let mut x = @mut {f: 5, g: 6}; - let y = &mut x.f; - -Here, a pointer was created to the interior of a shared box which -contains a record. Even if `*x` were to be mutated like so: - - *x = {f: 6, g: 7}; - -This would cause `*y` to change from 5 to 6, but the pointer pointer -`y` remains valid. It still points at an integer even if that integer -has been overwritten. - -However, if we were to reassign `x` itself, like so: - - x = @{f: 6, g: 7}; - -This could potentially invalidate `y`, because if `x` were the final -reference to the shared box, then that memory would be released and -now `y` points at freed memory. (We will see that to prevent this -scenario we will *root* shared boxes that reside in mutable memory -whose contents are borrowed; rooting means that we create a temporary -to ensure that the box is not collected). - -In other cases, like an enum on the stack, the memory cannot be freed -but its type can change: - - let mut x = Some(5); - match x { - Some(ref y) => { ... } - None => { ... } - } - -Here as before, the pointer `y` would be invalidated if we were to -reassign `x` to `none`. (We will see that this case is prevented -because borrowck tracks data which resides on the stack and prevents -variables from reassigned if there may be pointers to their interior) - -Finally, in some cases, both dangers can arise. For example, something -like the following: - - let mut x = ~some(5); - match x { - ~some(ref y) => { ... } - ~none => { ... } - } - -In this case, if `x` to be reassigned or `*x` were to be mutated, then -the pointer `y` would be invalided. (This case is also prevented by -borrowck tracking data which is owned by the current stack frame) - -# Summary of the safety check - -In order to enforce mutability, the borrow check has a few tricks up -its sleeve: - -- When data is owned by the current stack frame, we can identify every - possible assignment to a local variable and simply prevent - potentially dangerous assignments directly. - -- If data is owned by a shared box, we can root the box to increase - its lifetime. - -- If data is found within a borrowed pointer, we can assume that the - data will remain live for the entirety of the borrowed pointer. - -- We can rely on the fact that pure actions (such as calling pure - functions) do not mutate data which is not owned by the current - stack frame. - -# Possible future directions - -There are numerous ways that the `borrowck` could be strengthened, but -these are the two most likely: - -- flow-sensitivity: we do not currently consider flow at all but only - block-scoping. This means that innocent code like the following is - rejected: - - let mut x: int; - ... - x = 5; - let y: &int = &x; // immutable ptr created - ... - - The reason is that the scope of the pointer `y` is the entire - enclosing block, and the assignment `x = 5` occurs within that - block. The analysis is not smart enough to see that `x = 5` always - happens before the immutable pointer is created. This is relatively - easy to fix and will surely be fixed at some point. - -- finer-grained purity checks: currently, our fallback for - guaranteeing random references into mutable, aliasable memory is to - require *total purity*. This is rather strong. We could use local - type-based alias analysis to distinguish writes that could not - possibly invalid the references which must be guaranteed. This - would only work within the function boundaries; function calls would - still require total purity. This seems less likely to be - implemented in the short term as it would make the code - significantly more complex; there is currently no code to analyze - the types and determine the possible impacts of a write. - -# How the code works - -The borrow check code is divided into several major modules, each of -which is documented in its own file. - -The `gather_loans` and `check_loans` are the two major passes of the -analysis. The `gather_loans` pass runs over the IR once to determine -what memory must remain valid and for how long. Its name is a bit of -a misnomer; it does in fact gather up the set of loans which are -granted, but it also determines when @T pointers must be rooted and -for which scopes purity must be required. - -The `check_loans` pass walks the IR and examines the loans and purity -requirements computed in `gather_loans`. It checks to ensure that (a) -the conditions of all loans are honored; (b) no contradictory loans -were granted (for example, loaning out the same memory as mutable and -immutable simultaneously); and (c) any purity requirements are -honored. - -The remaining modules are helper modules used by `gather_loans` and -`check_loans`: - -- `categorization` has the job of analyzing an expression to determine - what kind of memory is used in evaluating it (for example, where - dereferences occur and what kind of pointer is dereferenced; whether - the memory is mutable; etc) -- `loan` determines when data uniquely tied to the stack frame can be - loaned out. -- `preserve` determines what actions (if any) must be taken to preserve - aliasable data. This is the code which decides when to root - an @T pointer or to require purity. - -# Maps that are created - -Borrowck results in two maps. - -- `root_map`: identifies those expressions or patterns whose result - needs to be rooted. Conceptually the root_map maps from an - expression or pattern node to a `node_id` identifying the scope for - which the expression must be rooted (this `node_id` should identify - a block or call). The actual key to the map is not an expression id, - however, but a `root_map_key`, which combines an expression id with a - deref count and is used to cope with auto-deref. - -- `mutbl_map`: identifies those local variables which are modified or - moved. This is used by trans to guarantee that such variables are - given a memory location and not used as immediates. - */ - -use syntax::ast; -use syntax::ast::{mutability, m_mutbl, m_imm, m_const}; -use syntax::visit; -use syntax::ast_util; -use syntax::ast_map; -use syntax::codemap::span; -use util::ppaux::{ty_to_str, region_to_str, explain_region, - expr_repr, note_and_explain_region}; -use std::map::{HashMap, Set}; -use std::list; -use std::list::{List, Cons, Nil}; -use result::{Result, Ok, Err}; -use syntax::print::pprust; -use util::common::indenter; -use ty::to_str; -use dvec::DVec; -use mem_categorization::*; - -export check_crate, root_map, mutbl_map; - -fn check_crate(tcx: ty::ctxt, - method_map: typeck::method_map, - last_use_map: liveness::last_use_map, - crate: @ast::crate) -> (root_map, mutbl_map) { - - let bccx = borrowck_ctxt_(@{tcx: tcx, - method_map: method_map, - last_use_map: last_use_map, - root_map: root_map(), - mutbl_map: HashMap(), - mut loaned_paths_same: 0, - mut loaned_paths_imm: 0, - mut stable_paths: 0, - mut req_pure_paths: 0, - mut guaranteed_paths: 0}); - - let req_maps = gather_loans::gather_loans(bccx, crate); - check_loans::check_loans(bccx, req_maps, crate); - - if tcx.sess.borrowck_stats() { - io::println(~"--- borrowck stats ---"); - io::println(fmt!("paths requiring guarantees: %u", - bccx.guaranteed_paths)); - io::println(fmt!("paths requiring loans : %s", - make_stat(bccx, bccx.loaned_paths_same))); - io::println(fmt!("paths requiring imm loans : %s", - make_stat(bccx, bccx.loaned_paths_imm))); - io::println(fmt!("stable paths : %s", - make_stat(bccx, bccx.stable_paths))); - io::println(fmt!("paths requiring purity : %s", - make_stat(bccx, bccx.req_pure_paths))); - } - - return (bccx.root_map, bccx.mutbl_map); - - fn make_stat(bccx: borrowck_ctxt, stat: uint) -> ~str { - let stat_f = stat as float; - let total = bccx.guaranteed_paths as float; - fmt!("%u (%.0f%%)", stat , stat_f * 100f / total) - } -} - -// ---------------------------------------------------------------------- -// Type definitions - -type borrowck_ctxt_ = {tcx: ty::ctxt, - method_map: typeck::method_map, - last_use_map: liveness::last_use_map, - root_map: root_map, - mutbl_map: mutbl_map, - - // Statistics: - mut loaned_paths_same: uint, - mut loaned_paths_imm: uint, - mut stable_paths: uint, - mut req_pure_paths: uint, - mut guaranteed_paths: uint}; - -enum borrowck_ctxt { - borrowck_ctxt_(@borrowck_ctxt_) -} - -// a map mapping id's of expressions of gc'd type (@T, @[], etc) where -// the box needs to be kept live to the id of the scope for which they -// must stay live. -type root_map = HashMap<root_map_key, ast::node_id>; - -// the keys to the root map combine the `id` of the expression with -// the number of types that it is autodereferenced. So, for example, -// if you have an expression `x.f` and x has type ~@T, we could add an -// entry {id:x, derefs:0} to refer to `x` itself, `{id:x, derefs:1}` -// to refer to the deref of the unique pointer, and so on. -type root_map_key = {id: ast::node_id, derefs: uint}; - -// set of ids of local vars / formal arguments that are modified / moved. -// this is used in trans for optimization purposes. -type mutbl_map = std::map::HashMap<ast::node_id, ()>; - -// Errors that can occur"] -enum bckerr_code { - err_mut_uniq, - err_mut_variant, - err_root_not_permitted, - err_mutbl(ast::mutability), - err_out_of_root_scope(ty::Region, ty::Region), // superscope, subscope - err_out_of_scope(ty::Region, ty::Region) // superscope, subscope -} - -impl bckerr_code : cmp::Eq { - pure fn eq(&self, other: &bckerr_code) -> bool { - match (*self) { - err_mut_uniq => { - match (*other) { - err_mut_uniq => true, - _ => false - } - } - err_mut_variant => { - match (*other) { - err_mut_variant => true, - _ => false - } - } - err_root_not_permitted => { - match (*other) { - err_root_not_permitted => true, - _ => false - } - } - err_mutbl(e0a) => { - match (*other) { - err_mutbl(e0b) => e0a == e0b, - _ => false - } - } - err_out_of_root_scope(e0a, e1a) => { - match (*other) { - err_out_of_root_scope(e0b, e1b) => - e0a == e0b && e1a == e1b, - _ => false - } - } - err_out_of_scope(e0a, e1a) => { - match (*other) { - err_out_of_scope(e0b, e1b) => e0a == e0b && e1a == e1b, - _ => false - } - } - } - } - pure fn ne(&self, other: &bckerr_code) -> bool { !(*self).eq(other) } -} - -// Combination of an error code and the categorization of the expression -// that caused it -type bckerr = {cmt: cmt, code: bckerr_code}; - -impl bckerr : cmp::Eq { - pure fn eq(&self, other: &bckerr) -> bool { - (*self).cmt == (*other).cmt && (*self).code == (*other).code - } - pure fn ne(&self, other: &bckerr) -> bool { !(*self).eq(other) } -} - -// shorthand for something that fails with `bckerr` or succeeds with `T` -type bckres<T> = Result<T, bckerr>; - -/// a complete record of a loan that was granted -struct Loan {lp: @loan_path, cmt: cmt, mutbl: ast::mutability} - -/// maps computed by `gather_loans` that are then used by `check_loans` -/// -/// - `req_loan_map`: map from each block/expr to the required loans needed -/// for the duration of that block/expr -/// - `pure_map`: map from block/expr that must be pure to the error message -/// that should be reported if they are not pure -type req_maps = { - req_loan_map: HashMap<ast::node_id, @DVec<Loan>>, - pure_map: HashMap<ast::node_id, bckerr> -}; - -fn save_and_restore<T:Copy,U>(save_and_restore_t: &mut T, f: fn() -> U) -> U { - let old_save_and_restore_t = *save_and_restore_t; - let u = f(); - *save_and_restore_t = old_save_and_restore_t; - move u -} - -/// Creates and returns a new root_map - -impl root_map_key : cmp::Eq { - pure fn eq(&self, other: &root_map_key) -> bool { - (*self).id == (*other).id && (*self).derefs == (*other).derefs - } - pure fn ne(&self, other: &root_map_key) -> bool { - ! ((*self) == (*other)) - } -} - -#[cfg(stage0)] -impl root_map_key : to_bytes::IterBytes { - pure fn iter_bytes(+lsb0: bool, f: to_bytes::Cb) { - to_bytes::iter_bytes_2(&self.id, &self.derefs, lsb0, f); - } -} -#[cfg(stage1)] -#[cfg(stage2)] -impl root_map_key : to_bytes::IterBytes { - pure fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) { - to_bytes::iter_bytes_2(&self.id, &self.derefs, lsb0, f); - } -} - -fn root_map() -> root_map { - return HashMap(); - - pure fn root_map_key_eq(k1: &root_map_key, k2: &root_map_key) -> bool { - k1.id == k2.id && k1.derefs == k2.derefs - } - - pure fn root_map_key_hash(k: &root_map_key) -> uint { - (k.id << 4) as uint | k.derefs - } -} - -// ___________________________________________________________________________ -// Misc - -impl borrowck_ctxt { - fn is_subregion_of(r_sub: ty::Region, r_sup: ty::Region) -> bool { - region::is_subregion_of(self.tcx.region_map, r_sub, r_sup) - } - - fn cat_expr(expr: @ast::expr) -> cmt { - cat_expr(self.tcx, self.method_map, expr) - } - - fn cat_expr_unadjusted(expr: @ast::expr) -> cmt { - cat_expr_unadjusted(self.tcx, self.method_map, expr) - } - - fn cat_expr_autoderefd(expr: @ast::expr, - adj: @ty::AutoAdjustment) - -> cmt { - cat_expr_autoderefd(self.tcx, self.method_map, expr, adj) - } - - fn cat_def(id: ast::node_id, - span: span, - ty: ty::t, - def: ast::def) -> cmt { - cat_def(self.tcx, self.method_map, id, span, ty, def) - } - - fn cat_variant<N: ast_node>(arg: N, - enum_did: ast::def_id, - cmt: cmt) -> cmt { - cat_variant(self.tcx, self.method_map, arg, enum_did, cmt) - } - - fn cat_discr(cmt: cmt, alt_id: ast::node_id) -> cmt { - return @{cat:cat_discr(cmt, alt_id),.. *cmt}; - } - - fn cat_pattern(cmt: cmt, pat: @ast::pat, op: fn(cmt, @ast::pat)) { - let mc = &mem_categorization_ctxt {tcx: self.tcx, - method_map: self.method_map}; - mc.cat_pattern(cmt, pat, op); - } - - fn report_if_err(bres: bckres<()>) { - match bres { - Ok(()) => (), - Err(e) => self.report(e) - } - } - - fn report(err: bckerr) { - self.span_err( - err.cmt.span, - fmt!("illegal borrow: %s", - self.bckerr_to_str(err))); - self.note_and_explain_bckerr(err); - } - - fn span_err(s: span, m: ~str) { - self.tcx.sess.span_err(s, m); - } - - fn span_note(s: span, m: ~str) { - self.tcx.sess.span_note(s, m); - } - - fn add_to_mutbl_map(cmt: cmt) { - match cmt.cat { - cat_local(id) | cat_arg(id) => { - self.mutbl_map.insert(id, ()); - } - cat_stack_upvar(cmt) => { - self.add_to_mutbl_map(cmt); - } - _ => () - } - } - - fn bckerr_to_str(err: bckerr) -> ~str { - match err.code { - err_mutbl(req) => { - fmt!("creating %s alias to %s", - self.mut_to_str(req), - self.cmt_to_str(err.cmt)) - } - err_mut_uniq => { - ~"unique value in aliasable, mutable location" - } - err_mut_variant => { - ~"enum variant in aliasable, mutable location" - } - err_root_not_permitted => { - // note: I don't expect users to ever see this error - // message, reasons are discussed in attempt_root() in - // preserve.rs. - ~"rooting is not permitted" - } - err_out_of_root_scope(*) => { - ~"cannot root managed value long enough" - } - err_out_of_scope(*) => { - ~"borrowed value does not live long enough" - } - } - } - - fn note_and_explain_bckerr(err: bckerr) { - let code = err.code; - match code { - err_mutbl(*) | err_mut_uniq | err_mut_variant | - err_root_not_permitted => {} - - err_out_of_root_scope(super_scope, sub_scope) => { - note_and_explain_region( - self.tcx, - ~"managed value would have to be rooted for ", - sub_scope, - ~"..."); - note_and_explain_region( - self.tcx, - ~"...but can only be rooted for ", - super_scope, - ~""); - } - - err_out_of_scope(super_scope, sub_scope) => { - note_and_explain_region( - self.tcx, - ~"borrowed pointer must be valid for ", - sub_scope, - ~"..."); - note_and_explain_region( - self.tcx, - ~"...but borrowed value is only valid for ", - super_scope, - ~""); - } - } - } - - - fn cmt_to_str(cmt: cmt) -> ~str { - let mc = &mem_categorization_ctxt {tcx: self.tcx, - method_map: self.method_map}; - mc.cmt_to_str(cmt) - } - - fn cmt_to_repr(cmt: cmt) -> ~str { - let mc = &mem_categorization_ctxt {tcx: self.tcx, - method_map: self.method_map}; - mc.cmt_to_repr(cmt) - } - - fn mut_to_str(mutbl: ast::mutability) -> ~str { - let mc = &mem_categorization_ctxt {tcx: self.tcx, - method_map: self.method_map}; - mc.mut_to_str(mutbl) - } - - fn loan_to_repr(loan: &Loan) -> ~str { - fmt!("Loan(lp=%?, cmt=%s, mutbl=%?)", - loan.lp, self.cmt_to_repr(loan.cmt), loan.mutbl) - } -} - -// The inherent mutability of a component is its default mutability -// assuming it is embedded in an immutable context. In general, the -// mutability can be "overridden" if the component is embedded in a -// mutable structure. -fn inherent_mutability(ck: comp_kind) -> mutability { - match ck { - comp_tuple | comp_anon_field | comp_variant(_) => m_imm, - comp_field(_, m) | comp_index(_, m) => m - } -} diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs index c4411008404..6ef80321ec2 100644 --- a/src/librustc/middle/borrowck/mod.rs +++ b/src/librustc/middle/borrowck/mod.rs @@ -1,4 +1,239 @@ +/*! +# Borrow check + +This pass is in job of enforcing *memory safety* and *purity*. As +memory safety is by far the more complex topic, I'll focus on that in +this description, but purity will be covered later on. In the context +of Rust, memory safety means three basic things: + +- no writes to immutable memory; +- all pointers point to non-freed memory; +- all pointers point to memory of the same type as the pointer. + +The last point might seem confusing: after all, for the most part, +this condition is guaranteed by the type check. However, there are +two cases where the type check effectively delegates to borrow check. + +The first case has to do with enums. If there is a pointer to the +interior of an enum, and the enum is in a mutable location (such as a +local variable or field declared to be mutable), it is possible that +the user will overwrite the enum with a new value of a different +variant, and thus effectively change the type of the memory that the +pointer is pointing at. + +The second case has to do with mutability. Basically, the type +checker has only a limited understanding of mutability. It will allow +(for example) the user to get an immutable pointer with the address of +a mutable local variable. It will also allow a `@mut T` or `~mut T` +pointer to be borrowed as a `&r.T` pointer. These seeming oversights +are in fact intentional; they allow the user to temporarily treat a +mutable value as immutable. It is up to the borrow check to guarantee +that the value in question is not in fact mutated during the lifetime +`r` of the reference. + +# Definition of unstable memory + +The primary danger to safety arises due to *unstable memory*. +Unstable memory is memory whose validity or type may change as a +result of an assignment, move, or a variable going out of scope. +There are two cases in Rust where memory is unstable: the contents of +unique boxes and enums. + +Unique boxes are unstable because when the variable containing the +unique box is re-assigned, moves, or goes out of scope, the unique box +is freed or---in the case of a move---potentially given to another +task. In either case, if there is an extant and usable pointer into +the box, then safety guarantees would be compromised. + +Enum values are unstable because they are reassigned the types of +their contents may change if they are assigned with a different +variant than they had previously. + +# Safety criteria that must be enforced + +Whenever a piece of memory is borrowed for lifetime L, there are two +things which the borrow checker must guarantee. First, it must +guarantee that the memory address will remain allocated (and owned by +the current task) for the entirety of the lifetime L. Second, it must +guarantee that the type of the data will not change for the entirety +of the lifetime L. In exchange, the region-based type system will +guarantee that the pointer is not used outside the lifetime L. These +guarantees are to some extent independent but are also inter-related. + +In some cases, the type of a pointer cannot be invalidated but the +lifetime can. For example, imagine a pointer to the interior of +a shared box like: + + let mut x = @mut {f: 5, g: 6}; + let y = &mut x.f; + +Here, a pointer was created to the interior of a shared box which +contains a record. Even if `*x` were to be mutated like so: + + *x = {f: 6, g: 7}; + +This would cause `*y` to change from 5 to 6, but the pointer pointer +`y` remains valid. It still points at an integer even if that integer +has been overwritten. + +However, if we were to reassign `x` itself, like so: + + x = @{f: 6, g: 7}; + +This could potentially invalidate `y`, because if `x` were the final +reference to the shared box, then that memory would be released and +now `y` points at freed memory. (We will see that to prevent this +scenario we will *root* shared boxes that reside in mutable memory +whose contents are borrowed; rooting means that we create a temporary +to ensure that the box is not collected). + +In other cases, like an enum on the stack, the memory cannot be freed +but its type can change: + + let mut x = Some(5); + match x { + Some(ref y) => { ... } + None => { ... } + } + +Here as before, the pointer `y` would be invalidated if we were to +reassign `x` to `none`. (We will see that this case is prevented +because borrowck tracks data which resides on the stack and prevents +variables from reassigned if there may be pointers to their interior) + +Finally, in some cases, both dangers can arise. For example, something +like the following: + + let mut x = ~some(5); + match x { + ~some(ref y) => { ... } + ~none => { ... } + } + +In this case, if `x` to be reassigned or `*x` were to be mutated, then +the pointer `y` would be invalided. (This case is also prevented by +borrowck tracking data which is owned by the current stack frame) + +# Summary of the safety check + +In order to enforce mutability, the borrow check has a few tricks up +its sleeve: + +- When data is owned by the current stack frame, we can identify every + possible assignment to a local variable and simply prevent + potentially dangerous assignments directly. + +- If data is owned by a shared box, we can root the box to increase + its lifetime. + +- If data is found within a borrowed pointer, we can assume that the + data will remain live for the entirety of the borrowed pointer. + +- We can rely on the fact that pure actions (such as calling pure + functions) do not mutate data which is not owned by the current + stack frame. + +# Possible future directions + +There are numerous ways that the `borrowck` could be strengthened, but +these are the two most likely: + +- flow-sensitivity: we do not currently consider flow at all but only + block-scoping. This means that innocent code like the following is + rejected: + + let mut x: int; + ... + x = 5; + let y: &int = &x; // immutable ptr created + ... + + The reason is that the scope of the pointer `y` is the entire + enclosing block, and the assignment `x = 5` occurs within that + block. The analysis is not smart enough to see that `x = 5` always + happens before the immutable pointer is created. This is relatively + easy to fix and will surely be fixed at some point. + +- finer-grained purity checks: currently, our fallback for + guaranteeing random references into mutable, aliasable memory is to + require *total purity*. This is rather strong. We could use local + type-based alias analysis to distinguish writes that could not + possibly invalid the references which must be guaranteed. This + would only work within the function boundaries; function calls would + still require total purity. This seems less likely to be + implemented in the short term as it would make the code + significantly more complex; there is currently no code to analyze + the types and determine the possible impacts of a write. + +# How the code works + +The borrow check code is divided into several major modules, each of +which is documented in its own file. + +The `gather_loans` and `check_loans` are the two major passes of the +analysis. The `gather_loans` pass runs over the IR once to determine +what memory must remain valid and for how long. Its name is a bit of +a misnomer; it does in fact gather up the set of loans which are +granted, but it also determines when @T pointers must be rooted and +for which scopes purity must be required. + +The `check_loans` pass walks the IR and examines the loans and purity +requirements computed in `gather_loans`. It checks to ensure that (a) +the conditions of all loans are honored; (b) no contradictory loans +were granted (for example, loaning out the same memory as mutable and +immutable simultaneously); and (c) any purity requirements are +honored. + +The remaining modules are helper modules used by `gather_loans` and +`check_loans`: + +- `categorization` has the job of analyzing an expression to determine + what kind of memory is used in evaluating it (for example, where + dereferences occur and what kind of pointer is dereferenced; whether + the memory is mutable; etc) +- `loan` determines when data uniquely tied to the stack frame can be + loaned out. +- `preserve` determines what actions (if any) must be taken to preserve + aliasable data. This is the code which decides when to root + an @T pointer or to require purity. + +# Maps that are created + +Borrowck results in two maps. + +- `root_map`: identifies those expressions or patterns whose result + needs to be rooted. Conceptually the root_map maps from an + expression or pattern node to a `node_id` identifying the scope for + which the expression must be rooted (this `node_id` should identify + a block or call). The actual key to the map is not an expression id, + however, but a `root_map_key`, which combines an expression id with a + deref count and is used to cope with auto-deref. + +- `mutbl_map`: identifies those local variables which are modified or + moved. This is used by trans to guarantee that such variables are + given a memory location and not used as immediates. + */ + #[legacy_exports]; + +use syntax::ast; +use syntax::ast::{mutability, m_mutbl, m_imm, m_const}; +use syntax::visit; +use syntax::ast_util; +use syntax::ast_map; +use syntax::codemap::span; +use util::ppaux::{ty_to_str, region_to_str, explain_region, + expr_repr, note_and_explain_region}; +use std::map::{HashMap, Set}; +use std::list; +use std::list::{List, Cons, Nil}; +use result::{Result, Ok, Err}; +use syntax::print::pprust; +use util::common::indenter; +use ty::to_str; +use dvec::DVec; +use mem_categorization::*; + #[legacy_exports] mod check_loans; #[legacy_exports] @@ -7,3 +242,388 @@ mod gather_loans; mod loan; #[legacy_exports] mod preserve; + +export check_crate, root_map, mutbl_map; + +fn check_crate(tcx: ty::ctxt, + method_map: typeck::method_map, + last_use_map: liveness::last_use_map, + crate: @ast::crate) -> (root_map, mutbl_map) { + + let bccx = borrowck_ctxt_(@{tcx: tcx, + method_map: method_map, + last_use_map: last_use_map, + root_map: root_map(), + mutbl_map: HashMap(), + mut loaned_paths_same: 0, + mut loaned_paths_imm: 0, + mut stable_paths: 0, + mut req_pure_paths: 0, + mut guaranteed_paths: 0}); + + let req_maps = gather_loans::gather_loans(bccx, crate); + check_loans::check_loans(bccx, req_maps, crate); + + if tcx.sess.borrowck_stats() { + io::println(~"--- borrowck stats ---"); + io::println(fmt!("paths requiring guarantees: %u", + bccx.guaranteed_paths)); + io::println(fmt!("paths requiring loans : %s", + make_stat(bccx, bccx.loaned_paths_same))); + io::println(fmt!("paths requiring imm loans : %s", + make_stat(bccx, bccx.loaned_paths_imm))); + io::println(fmt!("stable paths : %s", + make_stat(bccx, bccx.stable_paths))); + io::println(fmt!("paths requiring purity : %s", + make_stat(bccx, bccx.req_pure_paths))); + } + + return (bccx.root_map, bccx.mutbl_map); + + fn make_stat(bccx: borrowck_ctxt, stat: uint) -> ~str { + let stat_f = stat as float; + let total = bccx.guaranteed_paths as float; + fmt!("%u (%.0f%%)", stat , stat_f * 100f / total) + } +} + +// ---------------------------------------------------------------------- +// Type definitions + +type borrowck_ctxt_ = {tcx: ty::ctxt, + method_map: typeck::method_map, + last_use_map: liveness::last_use_map, + root_map: root_map, + mutbl_map: mutbl_map, + + // Statistics: + mut loaned_paths_same: uint, + mut loaned_paths_imm: uint, + mut stable_paths: uint, + mut req_pure_paths: uint, + mut guaranteed_paths: uint}; + +enum borrowck_ctxt { + borrowck_ctxt_(@borrowck_ctxt_) +} + +// a map mapping id's of expressions of gc'd type (@T, @[], etc) where +// the box needs to be kept live to the id of the scope for which they +// must stay live. +type root_map = HashMap<root_map_key, ast::node_id>; + +// the keys to the root map combine the `id` of the expression with +// the number of types that it is autodereferenced. So, for example, +// if you have an expression `x.f` and x has type ~@T, we could add an +// entry {id:x, derefs:0} to refer to `x` itself, `{id:x, derefs:1}` +// to refer to the deref of the unique pointer, and so on. +type root_map_key = {id: ast::node_id, derefs: uint}; + +// set of ids of local vars / formal arguments that are modified / moved. +// this is used in trans for optimization purposes. +type mutbl_map = std::map::HashMap<ast::node_id, ()>; + +// Errors that can occur"] +enum bckerr_code { + err_mut_uniq, + err_mut_variant, + err_root_not_permitted, + err_mutbl(ast::mutability), + err_out_of_root_scope(ty::Region, ty::Region), // superscope, subscope + err_out_of_scope(ty::Region, ty::Region) // superscope, subscope +} + +impl bckerr_code : cmp::Eq { + pure fn eq(&self, other: &bckerr_code) -> bool { + match (*self) { + err_mut_uniq => { + match (*other) { + err_mut_uniq => true, + _ => false + } + } + err_mut_variant => { + match (*other) { + err_mut_variant => true, + _ => false + } + } + err_root_not_permitted => { + match (*other) { + err_root_not_permitted => true, + _ => false + } + } + err_mutbl(e0a) => { + match (*other) { + err_mutbl(e0b) => e0a == e0b, + _ => false + } + } + err_out_of_root_scope(e0a, e1a) => { + match (*other) { + err_out_of_root_scope(e0b, e1b) => + e0a == e0b && e1a == e1b, + _ => false + } + } + err_out_of_scope(e0a, e1a) => { + match (*other) { + err_out_of_scope(e0b, e1b) => e0a == e0b && e1a == e1b, + _ => false + } + } + } + } + pure fn ne(&self, other: &bckerr_code) -> bool { !(*self).eq(other) } +} + +// Combination of an error code and the categorization of the expression +// that caused it +type bckerr = {cmt: cmt, code: bckerr_code}; + +impl bckerr : cmp::Eq { + pure fn eq(&self, other: &bckerr) -> bool { + (*self).cmt == (*other).cmt && (*self).code == (*other).code + } + pure fn ne(&self, other: &bckerr) -> bool { !(*self).eq(other) } +} + +// shorthand for something that fails with `bckerr` or succeeds with `T` +type bckres<T> = Result<T, bckerr>; + +/// a complete record of a loan that was granted +struct Loan {lp: @loan_path, cmt: cmt, mutbl: ast::mutability} + +/// maps computed by `gather_loans` that are then used by `check_loans` +/// +/// - `req_loan_map`: map from each block/expr to the required loans needed +/// for the duration of that block/expr +/// - `pure_map`: map from block/expr that must be pure to the error message +/// that should be reported if they are not pure +type req_maps = { + req_loan_map: HashMap<ast::node_id, @DVec<Loan>>, + pure_map: HashMap<ast::node_id, bckerr> +}; + +fn save_and_restore<T:Copy,U>(save_and_restore_t: &mut T, f: fn() -> U) -> U { + let old_save_and_restore_t = *save_and_restore_t; + let u = f(); + *save_and_restore_t = old_save_and_restore_t; + move u +} + +/// Creates and returns a new root_map + +impl root_map_key : cmp::Eq { + pure fn eq(&self, other: &root_map_key) -> bool { + (*self).id == (*other).id && (*self).derefs == (*other).derefs + } + pure fn ne(&self, other: &root_map_key) -> bool { + ! ((*self) == (*other)) + } +} + +#[cfg(stage0)] +impl root_map_key : to_bytes::IterBytes { + pure fn iter_bytes(+lsb0: bool, f: to_bytes::Cb) { + to_bytes::iter_bytes_2(&self.id, &self.derefs, lsb0, f); + } +} +#[cfg(stage1)] +#[cfg(stage2)] +impl root_map_key : to_bytes::IterBytes { + pure fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) { + to_bytes::iter_bytes_2(&self.id, &self.derefs, lsb0, f); + } +} + +fn root_map() -> root_map { + return HashMap(); + + pure fn root_map_key_eq(k1: &root_map_key, k2: &root_map_key) -> bool { + k1.id == k2.id && k1.derefs == k2.derefs + } + + pure fn root_map_key_hash(k: &root_map_key) -> uint { + (k.id << 4) as uint | k.derefs + } +} + +// ___________________________________________________________________________ +// Misc + +impl borrowck_ctxt { + fn is_subregion_of(r_sub: ty::Region, r_sup: ty::Region) -> bool { + region::is_subregion_of(self.tcx.region_map, r_sub, r_sup) + } + + fn cat_expr(expr: @ast::expr) -> cmt { + cat_expr(self.tcx, self.method_map, expr) + } + + fn cat_expr_unadjusted(expr: @ast::expr) -> cmt { + cat_expr_unadjusted(self.tcx, self.method_map, expr) + } + + fn cat_expr_autoderefd(expr: @ast::expr, + adj: @ty::AutoAdjustment) + -> cmt { + cat_expr_autoderefd(self.tcx, self.method_map, expr, adj) + } + + fn cat_def(id: ast::node_id, + span: span, + ty: ty::t, + def: ast::def) -> cmt { + cat_def(self.tcx, self.method_map, id, span, ty, def) + } + + fn cat_variant<N: ast_node>(arg: N, + enum_did: ast::def_id, + cmt: cmt) -> cmt { + cat_variant(self.tcx, self.method_map, arg, enum_did, cmt) + } + + fn cat_discr(cmt: cmt, alt_id: ast::node_id) -> cmt { + return @{cat:cat_discr(cmt, alt_id),.. *cmt}; + } + + fn cat_pattern(cmt: cmt, pat: @ast::pat, op: fn(cmt, @ast::pat)) { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.cat_pattern(cmt, pat, op); + } + + fn report_if_err(bres: bckres<()>) { + match bres { + Ok(()) => (), + Err(e) => self.report(e) + } + } + + fn report(err: bckerr) { + self.span_err( + err.cmt.span, + fmt!("illegal borrow: %s", + self.bckerr_to_str(err))); + self.note_and_explain_bckerr(err); + } + + fn span_err(s: span, m: ~str) { + self.tcx.sess.span_err(s, m); + } + + fn span_note(s: span, m: ~str) { + self.tcx.sess.span_note(s, m); + } + + fn add_to_mutbl_map(cmt: cmt) { + match cmt.cat { + cat_local(id) | cat_arg(id) => { + self.mutbl_map.insert(id, ()); + } + cat_stack_upvar(cmt) => { + self.add_to_mutbl_map(cmt); + } + _ => () + } + } + + fn bckerr_to_str(err: bckerr) -> ~str { + match err.code { + err_mutbl(req) => { + fmt!("creating %s alias to %s", + self.mut_to_str(req), + self.cmt_to_str(err.cmt)) + } + err_mut_uniq => { + ~"unique value in aliasable, mutable location" + } + err_mut_variant => { + ~"enum variant in aliasable, mutable location" + } + err_root_not_permitted => { + // note: I don't expect users to ever see this error + // message, reasons are discussed in attempt_root() in + // preserve.rs. + ~"rooting is not permitted" + } + err_out_of_root_scope(*) => { + ~"cannot root managed value long enough" + } + err_out_of_scope(*) => { + ~"borrowed value does not live long enough" + } + } + } + + fn note_and_explain_bckerr(err: bckerr) { + let code = err.code; + match code { + err_mutbl(*) | err_mut_uniq | err_mut_variant | + err_root_not_permitted => {} + + err_out_of_root_scope(super_scope, sub_scope) => { + note_and_explain_region( + self.tcx, + ~"managed value would have to be rooted for ", + sub_scope, + ~"..."); + note_and_explain_region( + self.tcx, + ~"...but can only be rooted for ", + super_scope, + ~""); + } + + err_out_of_scope(super_scope, sub_scope) => { + note_and_explain_region( + self.tcx, + ~"borrowed pointer must be valid for ", + sub_scope, + ~"..."); + note_and_explain_region( + self.tcx, + ~"...but borrowed value is only valid for ", + super_scope, + ~""); + } + } + } + + + fn cmt_to_str(cmt: cmt) -> ~str { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.cmt_to_str(cmt) + } + + fn cmt_to_repr(cmt: cmt) -> ~str { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.cmt_to_repr(cmt) + } + + fn mut_to_str(mutbl: ast::mutability) -> ~str { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.mut_to_str(mutbl) + } + + fn loan_to_repr(loan: &Loan) -> ~str { + fmt!("Loan(lp=%?, cmt=%s, mutbl=%?)", + loan.lp, self.cmt_to_repr(loan.cmt), loan.mutbl) + } +} + +// The inherent mutability of a component is its default mutability +// assuming it is embedded in an immutable context. In general, the +// mutability can be "overridden" if the component is embedded in a +// mutable structure. +fn inherent_mutability(ck: comp_kind) -> mutability { + match ck { + comp_tuple | comp_anon_field | comp_variant(_) => m_imm, + comp_field(_, m) | comp_index(_, m) => m + } +} diff --git a/src/librustc/middle/typeck.rs b/src/librustc/middle/typeck.rs deleted file mode 100644 index 421c68fa9a2..00000000000 --- a/src/librustc/middle/typeck.rs +++ /dev/null @@ -1,376 +0,0 @@ -/* - -typeck.rs, an introduction - -The type checker is responsible for: - -1. Determining the type of each expression -2. Resolving methods and traits -3. Guaranteeing that most type rules are met ("most?", you say, "why most?" - Well, dear reader, read on) - -The main entry point is `check_crate()`. Type checking operates in two major -phases: collect and check. The collect phase passes over all items and -determines their type, without examining their "innards". The check phase -then checks function bodies and so forth. - -Within the check phase, we check each function body one at a time (bodies of -function expressions are checked as part of the containing function). -Inference is used to supply types wherever they are unknown. The actual -checking of a function itself has several phases (check, regionck, writeback), -as discussed in the documentation for the `check` module. - -The type checker is defined into various submodules which are documented -independently: - -- astconv: converts the AST representation of types - into the `ty` representation - -- collect: computes the types of each top-level item and enters them into - the `cx.tcache` table for later use - -- check: walks over function bodies and type checks them, inferring types for - local variables, type parameters, etc as necessary. - -- infer: finds the types to use for each type variable such that - all subtyping and assignment constraints are met. In essence, the check - module specifies the constraints, and the infer module solves them. - -*/ - -use result::Result; -use syntax::{ast, ast_util, ast_map}; -use ast::spanned; -use ast::{required, provided}; -use syntax::ast_map::node_id_to_str; -use syntax::ast_util::{local_def, respan, split_trait_methods}; -use syntax::visit; -use metadata::csearch; -use util::common::{block_query, loop_query}; -use syntax::codemap::span; -use pat_util::{pat_id_map, PatIdMap}; -use middle::ty; -use middle::ty::{arg, field, node_type_table, mk_nil, ty_param_bounds_and_ty}; -use middle::ty::{ty_param_substs_and_ty, vstore_uniq}; -use std::smallintmap; -use std::map; -use std::map::HashMap; -use syntax::print::pprust::*; -use util::ppaux::{ty_to_str, tys_to_str, region_to_str, - bound_region_to_str, vstore_to_str, expr_repr}; -use util::common::{indent, indenter}; -use std::list; -use list::{List, Nil, Cons}; -use dvec::DVec; - -export check; -export check_crate; -export infer; -export method_map; -export method_origin; -export method_map_entry; -export vtable_map; -export vtable_res; -export vtable_origin; -export method_static, method_param, method_trait, method_self; -export vtable_static, vtable_param, vtable_trait; -export provided_methods_map; - -#[auto_serialize] -#[auto_deserialize] -enum method_origin { - // fully statically resolved method - method_static(ast::def_id), - - // method invoked on a type parameter with a bounded trait - method_param(method_param), - - // method invoked on a trait instance - method_trait(ast::def_id, uint, ty::vstore), - - // method invoked on "self" inside a default method - method_self(ast::def_id, uint), -} - -// details for a method invoked with a receiver whose type is a type parameter -// with a bounded trait. -#[auto_serialize] -#[auto_deserialize] -type method_param = { - // the trait containing the method to be invoked - trait_id: ast::def_id, - - // index of the method to be invoked amongst the trait's methods - method_num: uint, - - // index of the type parameter (from those that are in scope) that is - // the type of the receiver - param_num: uint, - - // index of the bound for this type parameter which specifies the trait - bound_num: uint -}; - -type method_map_entry = { - // the type and mode of the self parameter, which is not reflected - // in the fn type (FIXME #3446) - self_arg: ty::arg, - - // method details being invoked - origin: method_origin -}; - -// maps from an expression id that corresponds to a method call to the details -// of the method to be invoked -type method_map = HashMap<ast::node_id, method_map_entry>; - -// Resolutions for bounds of all parameters, left to right, for a given path. -type vtable_res = @~[vtable_origin]; - -enum vtable_origin { - /* - Statically known vtable. def_id gives the class or impl item - from whence comes the vtable, and tys are the type substs. - vtable_res is the vtable itself - */ - vtable_static(ast::def_id, ~[ty::t], vtable_res), - /* - Dynamic vtable, comes from a parameter that has a bound on it: - fn foo<T: quux, baz, bar>(a: T) -- a's vtable would have a - vtable_param origin - - The first uint is the param number (identifying T in the example), - and the second is the bound number (identifying baz) - */ - vtable_param(uint, uint), - /* - Dynamic vtable, comes from something known to have a trait - type. def_id refers to the trait item, tys are the substs - */ - vtable_trait(ast::def_id, ~[ty::t]), -} - -impl vtable_origin { - fn to_str(tcx: ty::ctxt) -> ~str { - match self { - vtable_static(def_id, ref tys, ref vtable_res) => { - fmt!("vtable_static(%?:%s, %?, %?)", - def_id, ty::item_path_str(tcx, def_id), - tys, - vtable_res.map(|o| o.to_str(tcx))) - } - - vtable_param(x, y) => { - fmt!("vtable_param(%?, %?)", x, y) - } - - vtable_trait(def_id, ref tys) => { - fmt!("vtable_trait(%?:%s, %?)", - def_id, ty::item_path_str(tcx, def_id), - tys.map(|t| ty_to_str(tcx, *t))) - } - } - } -} - -type vtable_map = HashMap<ast::node_id, vtable_res>; - -type crate_ctxt_ = {// A mapping from method call sites to traits that have - // that method. - trait_map: resolve::TraitMap, - method_map: method_map, - vtable_map: vtable_map, - coherence_info: @coherence::CoherenceInfo, - tcx: ty::ctxt}; - -enum crate_ctxt { - crate_ctxt_(crate_ctxt_) -} - -// Functions that write types into the node type table -fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::node_id, ty: ty::t) { - debug!("write_ty_to_tcx(%d, %s)", node_id, ty_to_str(tcx, ty)); - smallintmap::insert(*tcx.node_types, node_id as uint, ty); -} -fn write_substs_to_tcx(tcx: ty::ctxt, - node_id: ast::node_id, - +substs: ~[ty::t]) { - if substs.len() > 0u { - debug!("write_substs_to_tcx(%d, %?)", node_id, - substs.map(|t| ty_to_str(tcx, *t))); - tcx.node_type_substs.insert(node_id, substs); - } -} - -fn lookup_def_tcx(tcx: ty::ctxt, sp: span, id: ast::node_id) -> ast::def { - match tcx.def_map.find(id) { - Some(x) => x, - _ => { - tcx.sess.span_fatal(sp, ~"internal error looking up a definition") - } - } -} - -fn lookup_def_ccx(ccx: @crate_ctxt, sp: span, id: ast::node_id) -> ast::def { - lookup_def_tcx(ccx.tcx, sp, id) -} - -fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty { - {bounds: @~[], region_param: None, ty: t} -} - -fn require_same_types( - tcx: ty::ctxt, - maybe_infcx: Option<infer::infer_ctxt>, - t1_is_expected: bool, - span: span, - t1: ty::t, - t2: ty::t, - msg: fn() -> ~str) -> bool { - - let l_tcx, l_infcx; - match maybe_infcx { - None => { - l_tcx = tcx; - l_infcx = infer::new_infer_ctxt(tcx); - } - Some(i) => { - l_tcx = i.tcx; - l_infcx = i; - } - } - - match infer::mk_eqty(l_infcx, t1_is_expected, span, t1, t2) { - result::Ok(()) => true, - result::Err(ref terr) => { - l_tcx.sess.span_err(span, msg() + ~": " + - ty::type_err_to_str(l_tcx, terr)); - ty::note_and_explain_type_err(l_tcx, terr); - false - } - } -} - -// a list of mapping from in-scope-region-names ("isr") to the -// corresponding ty::Region -type isr_alist = @List<(ty::bound_region, ty::Region)>; - -trait get_and_find_region { - fn get(br: ty::bound_region) -> ty::Region; - fn find(br: ty::bound_region) -> Option<ty::Region>; -} - -impl isr_alist: get_and_find_region { - fn get(br: ty::bound_region) -> ty::Region { - self.find(br).get() - } - - fn find(br: ty::bound_region) -> Option<ty::Region> { - for list::each(self) |isr| { - let (isr_br, isr_r) = *isr; - if isr_br == br { return Some(isr_r); } - } - return None; - } -} - -fn arg_is_argv_ty(tcx: ty::ctxt, a: ty::arg) -> bool { - match ty::resolved_mode(tcx, a.mode) { - ast::by_val => { /*ok*/ } - _ => { - return false; - } - } - - match ty::get(a.ty).sty { - ty::ty_evec(mt, vstore_uniq) => { - if mt.mutbl != ast::m_imm { return false; } - match ty::get(mt.ty).sty { - ty::ty_estr(vstore_uniq) => return true, - _ => return false - } - } - _ => return false - } -} - -fn check_main_fn_ty(ccx: @crate_ctxt, - main_id: ast::node_id, - main_span: span) { - - let tcx = ccx.tcx; - let main_t = ty::node_id_to_type(tcx, main_id); - match ty::get(main_t).sty { - ty::ty_fn(fn_ty) => { - match tcx.items.find(main_id) { - Some(ast_map::node_item(it,_)) => { - match it.node { - ast::item_fn(_,_,ps,_) if vec::is_not_empty(ps) => { - tcx.sess.span_err( - main_span, - ~"main function is not allowed \ - to have type parameters"); - return; - } - _ => () - } - } - _ => () - } - let mut ok = ty::type_is_nil(fn_ty.sig.output); - let num_args = vec::len(fn_ty.sig.inputs); - ok &= num_args == 0u; - if !ok { - tcx.sess.span_err( - main_span, - fmt!("Wrong type in main function: found `%s`, \ - expected `fn() -> ()`", - ty_to_str(tcx, main_t))); - } - } - _ => { - tcx.sess.span_bug(main_span, - ~"main has a non-function type: found `" + - ty_to_str(tcx, main_t) + ~"`"); - } - } -} - -fn check_for_main_fn(ccx: @crate_ctxt) { - let tcx = ccx.tcx; - if !tcx.sess.building_library { - match copy tcx.sess.main_fn { - Some((id, sp)) => check_main_fn_ty(ccx, id, sp), - None => tcx.sess.err(~"main function not found") - } - } -} - -fn check_crate(tcx: ty::ctxt, - trait_map: resolve::TraitMap, - crate: @ast::crate) - -> (method_map, vtable_map) { - - let ccx = @crate_ctxt_({trait_map: trait_map, - method_map: std::map::HashMap(), - vtable_map: std::map::HashMap(), - coherence_info: @coherence::CoherenceInfo(), - tcx: tcx}); - collect::collect_item_types(ccx, crate); - coherence::check_coherence(ccx, crate); - deriving::check_deriving(ccx, crate); - - check::check_item_types(ccx, crate); - check_for_main_fn(ccx); - tcx.sess.abort_if_errors(); - (ccx.method_map, ccx.vtable_map) -} -// -// Local Variables: -// mode: rust -// fill-column: 78; -// indent-tabs-mode: nil -// c-basic-offset: 4 -// buffer-file-coding-system: utf-8-unix -// End: -// diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs index 11077081d91..6241cac2f5d 100644 --- a/src/librustc/middle/typeck/mod.rs +++ b/src/librustc/middle/typeck/mod.rs @@ -1,5 +1,83 @@ +/* + +typeck.rs, an introduction + +The type checker is responsible for: + +1. Determining the type of each expression +2. Resolving methods and traits +3. Guaranteeing that most type rules are met ("most?", you say, "why most?" + Well, dear reader, read on) + +The main entry point is `check_crate()`. Type checking operates in two major +phases: collect and check. The collect phase passes over all items and +determines their type, without examining their "innards". The check phase +then checks function bodies and so forth. + +Within the check phase, we check each function body one at a time (bodies of +function expressions are checked as part of the containing function). +Inference is used to supply types wherever they are unknown. The actual +checking of a function itself has several phases (check, regionck, writeback), +as discussed in the documentation for the `check` module. + +The type checker is defined into various submodules which are documented +independently: + +- astconv: converts the AST representation of types + into the `ty` representation + +- collect: computes the types of each top-level item and enters them into + the `cx.tcache` table for later use + +- check: walks over function bodies and type checks them, inferring types for + local variables, type parameters, etc as necessary. + +- infer: finds the types to use for each type variable such that + all subtyping and assignment constraints are met. In essence, the check + module specifies the constraints, and the infer module solves them. + +*/ + #[legacy_exports]; +use result::Result; +use syntax::{ast, ast_util, ast_map}; +use ast::spanned; +use ast::{required, provided}; +use syntax::ast_map::node_id_to_str; +use syntax::ast_util::{local_def, respan, split_trait_methods}; +use syntax::visit; +use metadata::csearch; +use util::common::{block_query, loop_query}; +use syntax::codemap::span; +use pat_util::{pat_id_map, PatIdMap}; +use middle::ty; +use middle::ty::{arg, field, node_type_table, mk_nil, ty_param_bounds_and_ty}; +use middle::ty::{ty_param_substs_and_ty, vstore_uniq}; +use std::smallintmap; +use std::map; +use std::map::HashMap; +use syntax::print::pprust::*; +use util::ppaux::{ty_to_str, tys_to_str, region_to_str, + bound_region_to_str, vstore_to_str, expr_repr}; +use util::common::{indent, indenter}; +use std::list; +use list::{List, Nil, Cons}; +use dvec::DVec; + +export check; +export check_crate; +export infer; +export method_map; +export method_origin; +export method_map_entry; +export vtable_map; +export vtable_res; +export vtable_origin; +export method_static, method_param, method_trait, method_self; +export vtable_static, vtable_param, vtable_trait; +export provided_methods_map; + #[legacy_exports] #[merge = "check/mod.rs"] pub mod check; @@ -14,3 +92,302 @@ mod collect; #[legacy_exports] mod coherence; mod deriving; + +#[auto_serialize] +#[auto_deserialize] +enum method_origin { + // fully statically resolved method + method_static(ast::def_id), + + // method invoked on a type parameter with a bounded trait + method_param(method_param), + + // method invoked on a trait instance + method_trait(ast::def_id, uint, ty::vstore), + + // method invoked on "self" inside a default method + method_self(ast::def_id, uint), +} + +// details for a method invoked with a receiver whose type is a type parameter +// with a bounded trait. +#[auto_serialize] +#[auto_deserialize] +type method_param = { + // the trait containing the method to be invoked + trait_id: ast::def_id, + + // index of the method to be invoked amongst the trait's methods + method_num: uint, + + // index of the type parameter (from those that are in scope) that is + // the type of the receiver + param_num: uint, + + // index of the bound for this type parameter which specifies the trait + bound_num: uint +}; + +type method_map_entry = { + // the type and mode of the self parameter, which is not reflected + // in the fn type (FIXME #3446) + self_arg: ty::arg, + + // method details being invoked + origin: method_origin +}; + +// maps from an expression id that corresponds to a method call to the details +// of the method to be invoked +type method_map = HashMap<ast::node_id, method_map_entry>; + +// Resolutions for bounds of all parameters, left to right, for a given path. +type vtable_res = @~[vtable_origin]; + +enum vtable_origin { + /* + Statically known vtable. def_id gives the class or impl item + from whence comes the vtable, and tys are the type substs. + vtable_res is the vtable itself + */ + vtable_static(ast::def_id, ~[ty::t], vtable_res), + /* + Dynamic vtable, comes from a parameter that has a bound on it: + fn foo<T: quux, baz, bar>(a: T) -- a's vtable would have a + vtable_param origin + + The first uint is the param number (identifying T in the example), + and the second is the bound number (identifying baz) + */ + vtable_param(uint, uint), + /* + Dynamic vtable, comes from something known to have a trait + type. def_id refers to the trait item, tys are the substs + */ + vtable_trait(ast::def_id, ~[ty::t]), +} + +impl vtable_origin { + fn to_str(tcx: ty::ctxt) -> ~str { + match self { + vtable_static(def_id, ref tys, ref vtable_res) => { + fmt!("vtable_static(%?:%s, %?, %?)", + def_id, ty::item_path_str(tcx, def_id), + tys, + vtable_res.map(|o| o.to_str(tcx))) + } + + vtable_param(x, y) => { + fmt!("vtable_param(%?, %?)", x, y) + } + + vtable_trait(def_id, ref tys) => { + fmt!("vtable_trait(%?:%s, %?)", + def_id, ty::item_path_str(tcx, def_id), + tys.map(|t| ty_to_str(tcx, *t))) + } + } + } +} + +type vtable_map = HashMap<ast::node_id, vtable_res>; + +type crate_ctxt_ = {// A mapping from method call sites to traits that have + // that method. + trait_map: resolve::TraitMap, + method_map: method_map, + vtable_map: vtable_map, + coherence_info: @coherence::CoherenceInfo, + tcx: ty::ctxt}; + +enum crate_ctxt { + crate_ctxt_(crate_ctxt_) +} + +// Functions that write types into the node type table +fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::node_id, ty: ty::t) { + debug!("write_ty_to_tcx(%d, %s)", node_id, ty_to_str(tcx, ty)); + smallintmap::insert(*tcx.node_types, node_id as uint, ty); +} +fn write_substs_to_tcx(tcx: ty::ctxt, + node_id: ast::node_id, + +substs: ~[ty::t]) { + if substs.len() > 0u { + debug!("write_substs_to_tcx(%d, %?)", node_id, + substs.map(|t| ty_to_str(tcx, *t))); + tcx.node_type_substs.insert(node_id, substs); + } +} + +fn lookup_def_tcx(tcx: ty::ctxt, sp: span, id: ast::node_id) -> ast::def { + match tcx.def_map.find(id) { + Some(x) => x, + _ => { + tcx.sess.span_fatal(sp, ~"internal error looking up a definition") + } + } +} + +fn lookup_def_ccx(ccx: @crate_ctxt, sp: span, id: ast::node_id) -> ast::def { + lookup_def_tcx(ccx.tcx, sp, id) +} + +fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty { + {bounds: @~[], region_param: None, ty: t} +} + +fn require_same_types( + tcx: ty::ctxt, + maybe_infcx: Option<infer::infer_ctxt>, + t1_is_expected: bool, + span: span, + t1: ty::t, + t2: ty::t, + msg: fn() -> ~str) -> bool { + + let l_tcx, l_infcx; + match maybe_infcx { + None => { + l_tcx = tcx; + l_infcx = infer::new_infer_ctxt(tcx); + } + Some(i) => { + l_tcx = i.tcx; + l_infcx = i; + } + } + + match infer::mk_eqty(l_infcx, t1_is_expected, span, t1, t2) { + result::Ok(()) => true, + result::Err(ref terr) => { + l_tcx.sess.span_err(span, msg() + ~": " + + ty::type_err_to_str(l_tcx, terr)); + ty::note_and_explain_type_err(l_tcx, terr); + false + } + } +} + +// a list of mapping from in-scope-region-names ("isr") to the +// corresponding ty::Region +type isr_alist = @List<(ty::bound_region, ty::Region)>; + +trait get_and_find_region { + fn get(br: ty::bound_region) -> ty::Region; + fn find(br: ty::bound_region) -> Option<ty::Region>; +} + +impl isr_alist: get_and_find_region { + fn get(br: ty::bound_region) -> ty::Region { + self.find(br).get() + } + + fn find(br: ty::bound_region) -> Option<ty::Region> { + for list::each(self) |isr| { + let (isr_br, isr_r) = *isr; + if isr_br == br { return Some(isr_r); } + } + return None; + } +} + +fn arg_is_argv_ty(tcx: ty::ctxt, a: ty::arg) -> bool { + match ty::resolved_mode(tcx, a.mode) { + ast::by_val => { /*ok*/ } + _ => { + return false; + } + } + + match ty::get(a.ty).sty { + ty::ty_evec(mt, vstore_uniq) => { + if mt.mutbl != ast::m_imm { return false; } + match ty::get(mt.ty).sty { + ty::ty_estr(vstore_uniq) => return true, + _ => return false + } + } + _ => return false + } +} + +fn check_main_fn_ty(ccx: @crate_ctxt, + main_id: ast::node_id, + main_span: span) { + + let tcx = ccx.tcx; + let main_t = ty::node_id_to_type(tcx, main_id); + match ty::get(main_t).sty { + ty::ty_fn(fn_ty) => { + match tcx.items.find(main_id) { + Some(ast_map::node_item(it,_)) => { + match it.node { + ast::item_fn(_,_,ps,_) if vec::is_not_empty(ps) => { + tcx.sess.span_err( + main_span, + ~"main function is not allowed \ + to have type parameters"); + return; + } + _ => () + } + } + _ => () + } + let mut ok = ty::type_is_nil(fn_ty.sig.output); + let num_args = vec::len(fn_ty.sig.inputs); + ok &= num_args == 0u; + if !ok { + tcx.sess.span_err( + main_span, + fmt!("Wrong type in main function: found `%s`, \ + expected `fn() -> ()`", + ty_to_str(tcx, main_t))); + } + } + _ => { + tcx.sess.span_bug(main_span, + ~"main has a non-function type: found `" + + ty_to_str(tcx, main_t) + ~"`"); + } + } +} + +fn check_for_main_fn(ccx: @crate_ctxt) { + let tcx = ccx.tcx; + if !tcx.sess.building_library { + match copy tcx.sess.main_fn { + Some((id, sp)) => check_main_fn_ty(ccx, id, sp), + None => tcx.sess.err(~"main function not found") + } + } +} + +fn check_crate(tcx: ty::ctxt, + trait_map: resolve::TraitMap, + crate: @ast::crate) + -> (method_map, vtable_map) { + + let ccx = @crate_ctxt_({trait_map: trait_map, + method_map: std::map::HashMap(), + vtable_map: std::map::HashMap(), + coherence_info: @coherence::CoherenceInfo(), + tcx: tcx}); + collect::collect_item_types(ccx, crate); + coherence::check_coherence(ccx, crate); + deriving::check_deriving(ccx, crate); + + check::check_item_types(ccx, crate); + check_for_main_fn(ccx); + tcx.sess.abort_if_errors(); + (ccx.method_map, ccx.vtable_map) +} +// +// Local Variables: +// mode: rust +// fill-column: 78; +// indent-tabs-mode: nil +// c-basic-offset: 4 +// buffer-file-coding-system: utf-8-unix +// End: +// diff --git a/src/librustc/rustc.rc b/src/librustc/rustc.rc index 80592fea500..14af4bc443e 100644 --- a/src/librustc/rustc.rc +++ b/src/librustc/rustc.rc @@ -122,8 +122,7 @@ mod middle { #[legacy_exports] #[path = "middle/resolve.rs"] mod resolve; - #[path = "middle/typeck.rs"] - #[merge = "middle/typeck/mod.rs"] + #[path = "middle/typeck/mod.rs"] pub mod typeck; #[legacy_exports] #[path = "middle/check_loop.rs"] @@ -137,8 +136,7 @@ mod middle { #[legacy_exports] #[path = "middle/lint.rs"] mod lint; - #[path = "middle/borrowck.rs"] - #[merge = "middle/borrowck/mod.rs"] + #[path = "middle/borrowck/mod.rs"] mod borrowck; #[legacy_exports] #[path = "middle/mem_categorization.rs"] @@ -216,10 +214,10 @@ mod back { mod target_strs; } -#[merge = "metadata/mod.rs"] +#[path = "metadata/mod.rs"] mod metadata; -#[merge = "driver/mod.rs"] +#[path = "driver/mod.rs"] mod driver; mod util { |