From 5eef15df126e8dfedc9e72ee3d9456ead0c9d06d Mon Sep 17 00:00:00 2001 From: Graydon Hoare Date: Wed, 29 Aug 2012 13:26:26 -0700 Subject: Rename resolve3 -> resolve. --- src/rustc/driver/driver.rs | 2 +- src/rustc/metadata.rs | 4 +- src/rustc/metadata/encoder.rs | 6 +- src/rustc/middle/check_const.rs | 10 +- src/rustc/middle/const_eval.rs | 4 +- src/rustc/middle/freevars.rs | 4 +- src/rustc/middle/pat_util.rs | 8 +- src/rustc/middle/region.rs | 8 +- src/rustc/middle/resolve.rs | 4611 +++++++++++++++++++++++++++++++ src/rustc/middle/resolve3.rs | 4611 ------------------------------- src/rustc/middle/trans/alt.rs | 2 +- src/rustc/middle/trans/base.rs | 4 +- src/rustc/middle/trans/common.rs | 4 +- src/rustc/middle/trans/reachable.rs | 4 +- src/rustc/middle/ty.rs | 4 +- src/rustc/middle/typeck.rs | 6 +- src/rustc/middle/typeck/check/method.rs | 4 +- src/rustc/middle/typeck/coherence.rs | 2 +- src/rustc/rustc.rc | 2 +- 19 files changed, 4650 insertions(+), 4650 deletions(-) create mode 100644 src/rustc/middle/resolve.rs delete mode 100644 src/rustc/middle/resolve3.rs (limited to 'src/rustc') diff --git a/src/rustc/driver/driver.rs b/src/rustc/driver/driver.rs index 9d92a452b67..6aa3451271d 100644 --- a/src/rustc/driver/driver.rs +++ b/src/rustc/driver/driver.rs @@ -187,7 +187,7 @@ fn compile_upto(sess: session, cfg: ast::crate_cfg, exp_map2: exp_map2, trait_map: trait_map } = time(time_passes, ~"resolution", || - middle::resolve3::resolve_crate(sess, lang_items, crate)); + middle::resolve::resolve_crate(sess, lang_items, crate)); let freevars = time(time_passes, ~"freevar finding", || freevars::annotate_freevars(def_map, crate)); diff --git a/src/rustc/metadata.rs b/src/rustc/metadata.rs index 0744430b844..af28556fd33 100644 --- a/src/rustc/metadata.rs +++ b/src/rustc/metadata.rs @@ -5,8 +5,8 @@ mod middle { import ty = middle_::ty; export ty; - import resolve3 = middle_::resolve3; - export resolve3; + import resolve = middle_::resolve; + export resolve; } mod front { diff --git a/src/rustc/metadata/encoder.rs b/src/rustc/metadata/encoder.rs index 1b360b7f782..712d8ef691a 100644 --- a/src/rustc/metadata/encoder.rs +++ b/src/rustc/metadata/encoder.rs @@ -13,7 +13,7 @@ import syntax::ast_util::*; import common::*; import middle::ty; import middle::ty::node_id_to_type; -import middle::resolve3; +import middle::resolve; import syntax::ast_map; import syntax::attr; import std::serialization::serializer; @@ -46,7 +46,7 @@ type encode_parms = { tcx: ty::ctxt, reachable: hashmap, reexports: ~[(~str, def_id)], - reexports2: middle::resolve3::ExportMap2, + reexports2: middle::resolve::ExportMap2, item_symbols: hashmap, discrim_symbols: hashmap, link_meta: link_meta, @@ -73,7 +73,7 @@ enum encode_ctxt = { stats: stats, reachable: hashmap, reexports: ~[(~str, def_id)], - reexports2: middle::resolve3::ExportMap2, + reexports2: middle::resolve::ExportMap2, item_symbols: hashmap, discrim_symbols: hashmap, link_meta: link_meta, diff --git a/src/rustc/middle/check_const.rs b/src/rustc/middle/check_const.rs index 8c50c9461b7..cc426b5cb74 100644 --- a/src/rustc/middle/check_const.rs +++ b/src/rustc/middle/check_const.rs @@ -5,7 +5,7 @@ import std::map::hashmap; import dvec::DVec; fn check_crate(sess: session, crate: @crate, ast_map: ast_map::map, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, method_map: typeck::method_map, tcx: ty::ctxt) { visit::visit_crate(*crate, false, visit::mk_vt(@{ visit_item: |a,b,c| check_item(sess, ast_map, def_map, a, b, c), @@ -18,7 +18,7 @@ fn check_crate(sess: session, crate: @crate, ast_map: ast_map::map, } fn check_item(sess: session, ast_map: ast_map::map, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, it: @item, &&_is_const: bool, v: visit::vt) { match it.node { item_const(_, ex) => { @@ -55,7 +55,7 @@ fn check_pat(p: @pat, &&_is_const: bool, v: visit::vt) { } } -fn check_expr(sess: session, def_map: resolve3::DefMap, +fn check_expr(sess: session, def_map: resolve::DefMap, method_map: typeck::method_map, tcx: ty::ctxt, e: @expr, &&is_const: bool, v: visit::vt) { if is_const { @@ -143,13 +143,13 @@ fn check_expr(sess: session, def_map: resolve3::DefMap, // Make sure a const item doesn't recursively refer to itself // FIXME: Should use the dependency graph when it's available (#1356) fn check_item_recursion(sess: session, ast_map: ast_map::map, - def_map: resolve3::DefMap, it: @item) { + def_map: resolve::DefMap, it: @item) { type env = { root_it: @item, sess: session, ast_map: ast_map::map, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, idstack: @DVec, }; diff --git a/src/rustc/middle/const_eval.rs b/src/rustc/middle/const_eval.rs index 328430d9464..9cc74c56b90 100644 --- a/src/rustc/middle/const_eval.rs +++ b/src/rustc/middle/const_eval.rs @@ -55,7 +55,7 @@ fn join_all(cs: &[constness]) -> constness { } fn classify(e: @expr, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, tcx: ty::ctxt) -> constness { let did = ast_util::local_def(e.id); match tcx.ccache.find(did) { @@ -168,7 +168,7 @@ fn classify(e: @expr, } fn process_crate(crate: @ast::crate, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, tcx: ty::ctxt) { let v = visit::mk_simple_visitor(@{ visit_expr_post: |e| { classify(e, def_map, tcx); } diff --git a/src/rustc/middle/freevars.rs b/src/rustc/middle/freevars.rs index 72388a8964e..143c494684a 100644 --- a/src/rustc/middle/freevars.rs +++ b/src/rustc/middle/freevars.rs @@ -30,7 +30,7 @@ type freevar_map = hashmap; // Since we want to be able to collect upvars in some arbitrary piece // of the AST, we take a walker function that we invoke with a visitor // in order to start the search. -fn collect_freevars(def_map: resolve3::DefMap, blk: ast::blk) +fn collect_freevars(def_map: resolve::DefMap, blk: ast::blk) -> freevar_info { let seen = int_hash(); let refs = @mut ~[]; @@ -85,7 +85,7 @@ fn collect_freevars(def_map: resolve3::DefMap, blk: ast::blk) // efficient as it fully recomputes the free variables at every // node of interest rather than building up the free variables in // one pass. This could be improved upon if it turns out to matter. -fn annotate_freevars(def_map: resolve3::DefMap, crate: @ast::crate) -> +fn annotate_freevars(def_map: resolve::DefMap, crate: @ast::crate) -> freevar_map { let freevars = int_hash(); diff --git a/src/rustc/middle/pat_util.rs b/src/rustc/middle/pat_util.rs index f80d4e2a239..9b473c32256 100644 --- a/src/rustc/middle/pat_util.rs +++ b/src/rustc/middle/pat_util.rs @@ -13,7 +13,7 @@ type pat_id_map = std::map::hashmap; // This is used because same-named variables in alternative patterns need to // use the node_id of their namesake in the first pattern. -fn pat_id_map(dm: resolve3::DefMap, pat: @pat) -> pat_id_map { +fn pat_id_map(dm: resolve::DefMap, pat: @pat) -> pat_id_map { let map = std::map::uint_hash(); do pat_bindings(dm, pat) |_bm, p_id, _s, n| { map.insert(path_to_ident(n), p_id); @@ -21,7 +21,7 @@ fn pat_id_map(dm: resolve3::DefMap, pat: @pat) -> pat_id_map { return map; } -fn pat_is_variant(dm: resolve3::DefMap, pat: @pat) -> bool { +fn pat_is_variant(dm: resolve::DefMap, pat: @pat) -> bool { match pat.node { pat_enum(_, _) => true, pat_ident(_, _, None) => match dm.find(pat.id) { @@ -32,7 +32,7 @@ fn pat_is_variant(dm: resolve3::DefMap, pat: @pat) -> bool { } } -fn pat_bindings(dm: resolve3::DefMap, pat: @pat, +fn pat_bindings(dm: resolve::DefMap, pat: @pat, it: fn(binding_mode, node_id, span, @path)) { do walk_pat(pat) |p| { match p.node { @@ -44,7 +44,7 @@ fn pat_bindings(dm: resolve3::DefMap, pat: @pat, } } -fn pat_binding_ids(dm: resolve3::DefMap, pat: @pat) -> ~[node_id] { +fn pat_binding_ids(dm: resolve::DefMap, pat: @pat) -> ~[node_id] { let mut found = ~[]; pat_bindings(dm, pat, |_bm, b_id, _sp, _pt| vec::push(found, b_id) ); return found; diff --git a/src/rustc/middle/region.rs b/src/rustc/middle/region.rs index f1d97f7ba6c..10bdce082ab 100644 --- a/src/rustc/middle/region.rs +++ b/src/rustc/middle/region.rs @@ -43,7 +43,7 @@ type region_map = hashmap; struct ctxt { sess: session; - def_map: resolve3::DefMap; + def_map: resolve::DefMap; // Generated maps: region_map: region_map; @@ -325,7 +325,7 @@ fn resolve_fn(fk: visit::fn_kind, decl: ast::fn_decl, body: ast::blk, visit::visit_fn(fk, decl, body, sp, id, fn_cx, visitor); } -fn resolve_crate(sess: session, def_map: resolve3::DefMap, +fn resolve_crate(sess: session, def_map: resolve::DefMap, crate: @ast::crate) -> region_map { let cx: ctxt = ctxt {sess: sess, def_map: def_map, @@ -373,7 +373,7 @@ type dep_map = hashmap>; type determine_rp_ctxt_ = { sess: session, ast_map: ast_map::map, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, region_paramd_items: region_paramd_items, dep_map: dep_map, worklist: DVec, @@ -746,7 +746,7 @@ fn determine_rp_in_struct_field(cm: @ast::struct_field, fn determine_rp_in_crate(sess: session, ast_map: ast_map::map, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, crate: @ast::crate) -> region_paramd_items { let cx = determine_rp_ctxt_(@{sess: sess, ast_map: ast_map, diff --git a/src/rustc/middle/resolve.rs b/src/rustc/middle/resolve.rs new file mode 100644 index 00000000000..33260e1fe6f --- /dev/null +++ b/src/rustc/middle/resolve.rs @@ -0,0 +1,4611 @@ +import driver::session::session; +import metadata::csearch::{each_path, get_method_names_if_trait}; +import metadata::cstore::find_use_stmt_cnum; +import metadata::decoder::{def_like, dl_def, dl_field, dl_impl}; +import middle::lang_items::LanguageItems; +import middle::lint::{deny, allow, forbid, level, unused_imports, warn}; +import middle::pat_util::{pat_bindings}; +import syntax::ast::{_mod, add, arm}; +import syntax::ast::{bind_by_ref, bind_by_implicit_ref, bind_by_value}; +import syntax::ast::{bitand, bitor, bitxor}; +import syntax::ast::{blk, bound_const, bound_copy, bound_owned, bound_send}; +import syntax::ast::{bound_trait, binding_mode, + capture_clause, class_ctor, class_dtor}; +import syntax::ast::{crate, crate_num, decl_item}; +import syntax::ast::{def, def_arg, def_binding, def_class, def_const, def_fn}; +import syntax::ast::{def_foreign_mod, def_id, def_label, def_local, def_mod}; +import syntax::ast::{def_prim_ty, def_region, def_self, def_ty, def_ty_param}; +import syntax::ast::{def_typaram_binder, def_static_method}; +import syntax::ast::{def_upvar, def_use, def_variant, expr, expr_assign_op}; +import syntax::ast::{expr_binary, expr_cast, expr_field, expr_fn}; +import syntax::ast::{expr_fn_block, expr_index, expr_path}; +import syntax::ast::{def_prim_ty, def_region, def_self, def_ty, def_ty_param}; +import syntax::ast::{def_upvar, def_use, def_variant, div, eq}; +import syntax::ast::{enum_variant_kind, expr, expr_again, expr_assign_op}; +import syntax::ast::{expr_binary, expr_break, expr_cast, expr_field, expr_fn}; +import syntax::ast::{expr_fn_block, expr_index, expr_loop}; +import syntax::ast::{expr_path, expr_struct, expr_unary, fn_decl}; +import syntax::ast::{foreign_item, foreign_item_const, foreign_item_fn, ge}; +import syntax::ast::{gt, ident, impure_fn, inherited, item, item_class}; +import syntax::ast::{item_const, item_enum, item_fn, item_foreign_mod}; +import syntax::ast::{item_impl, item_mac, item_mod, item_trait, item_ty, le}; +import syntax::ast::{local, local_crate, lt, method, mul, ne, neg, node_id}; +import syntax::ast::{pat, pat_enum, pat_ident, path, prim_ty, pat_box}; +import syntax::ast::{pat_lit, pat_range, pat_rec, pat_struct, pat_tup}; +import syntax::ast::{pat_uniq, pat_wild, private, provided, public, required}; +import syntax::ast::{rem, self_ty_, shl, shr, stmt_decl, struct_field}; +import syntax::ast::{struct_variant_kind, sty_static, subtract, trait_ref}; +import syntax::ast::{tuple_variant_kind, ty, ty_bool, ty_char, ty_f, ty_f32}; +import syntax::ast::{ty_f64, ty_float, ty_i, ty_i16, ty_i32, ty_i64, ty_i8}; +import syntax::ast::{ty_int, ty_param, ty_path, ty_str, ty_u, ty_u16, ty_u32}; +import syntax::ast::{ty_u64, ty_u8, ty_uint, variant, view_item}; +import syntax::ast::{view_item_export, view_item_import, view_item_use}; +import syntax::ast::{view_path_glob, view_path_list, view_path_simple}; +import syntax::ast::{visibility, anonymous, named}; +import syntax::ast_util::{def_id_of_def, dummy_sp, local_def, new_def_hash}; +import syntax::ast_util::{path_to_ident, walk_pat, trait_method_to_ty_method}; +import syntax::attr::{attr_metas, contains_name}; +import syntax::print::pprust::{pat_to_str, path_to_str}; +import syntax::codemap::span; +import syntax::visit::{default_visitor, fk_method, mk_vt, visit_block}; +import syntax::visit::{visit_crate, visit_expr, visit_expr_opt, visit_fn}; +import syntax::visit::{visit_foreign_item, visit_item, visit_method_helper}; +import syntax::visit::{visit_mod, visit_ty, vt}; + +import box::ptr_eq; +import dvec::DVec; +import option::{get, is_some}; +import str::{connect, split_str}; +import vec::pop; +import syntax::parse::token::ident_interner; + +import std::list::{cons, list, nil}; +import std::map::{hashmap, int_hash, uint_hash}; +import str_eq = str::eq; + +// Definition mapping +type DefMap = hashmap; + +struct binding_info { + span: span; + binding_mode: binding_mode; +} + +// Map from the name in a pattern to its binding mode. +type BindingMap = hashmap; + +// Implementation resolution +// +// XXX: This kind of duplicates information kept in ty::method. Maybe it +// should go away. + +type MethodInfo = { + did: def_id, + n_tps: uint, + ident: ident, + self_type: self_ty_ +}; + +type Impl = { did: def_id, ident: ident, methods: ~[@MethodInfo] }; + +// Trait method resolution +type TraitMap = @hashmap>; + +// Export mapping +type Export = { reexp: bool, id: def_id }; +type ExportMap = hashmap; + +// This is the replacement export map. It maps a module to all of the exports +// within. +type ExportMap2 = hashmap; + +struct Export2 { + name: ~str; // The name of the target. + def_id: def_id; // The definition of the target. + reexport: bool; // Whether this is a reexport. +} + +enum PatternBindingMode { + RefutableMode, + IrrefutableMode +} + +enum Namespace { + ModuleNS, + TypeNS, + ValueNS +} + +enum NamespaceResult { + UnknownResult, + UnboundResult, + BoundResult(@Module, @NameBindings) +} + +enum NameDefinition { + NoNameDefinition, //< The name was unbound. + ChildNameDefinition(def), //< The name identifies an immediate child. + ImportNameDefinition(def) //< The name identifies an import. + +} + +enum Mutability { + Mutable, + Immutable +} + +enum SelfBinding { + NoSelfBinding, + HasSelfBinding(node_id) +} + +enum CaptureClause { + NoCaptureClause, + HasCaptureClause(capture_clause) +} + +type ResolveVisitor = vt<()>; + +enum ModuleDef { + NoModuleDef, // Does not define a module. + ModuleDef(@Module), // Defines a module. +} + +/// Contains data for specific types of import directives. +enum ImportDirectiveSubclass { + SingleImport(Atom /* target */, Atom /* source */), + GlobImport +} + +/// The context that we thread through while building the reduced graph. +enum ReducedGraphParent { + ModuleReducedGraphParent(@Module) +} + +enum ResolveResult { + Failed, // Failed to resolve the name. + Indeterminate, // Couldn't determine due to unresolved globs. + Success(T) // Successfully resolved the import. +} + +enum TypeParameters/& { + NoTypeParameters, //< No type parameters. + HasTypeParameters(&~[ty_param], //< Type parameters. + node_id, //< ID of the enclosing item + + // The index to start numbering the type parameters at. + // This is zero if this is the outermost set of type + // parameters, or equal to the number of outer type + // parameters. For example, if we have: + // + // impl I { + // fn method() { ... } + // } + // + // The index at the method site will be 1, because the + // outer T had index 0. + + uint, + + // The kind of the rib used for type parameters. + RibKind) +} + +// The rib kind controls the translation of argument or local definitions +// (`def_arg` or `def_local`) to upvars (`def_upvar`). + +enum RibKind { + // No translation needs to be applied. + NormalRibKind, + + // We passed through a function scope at the given node ID. Translate + // upvars as appropriate. + FunctionRibKind(node_id /* func id */, node_id /* body id */), + + // We passed through a class, impl, or trait and are now in one of its + // methods. Allow references to ty params that that class, impl or trait + // binds. Disallow any other upvars (including other ty params that are + // upvars). + // parent; method itself + MethodRibKind(node_id, MethodSort), + + // We passed through a function *item* scope. Disallow upvars. + OpaqueFunctionRibKind +} + +// Methods can be required or provided. Required methods only occur in traits. +enum MethodSort { + Required, + Provided(node_id) +} + +// The X-ray flag indicates that a context has the X-ray privilege, which +// allows it to reference private names. Currently, this is used for the test +// runner. +// +// XXX: The X-ray flag is kind of questionable in the first place. It might +// be better to introduce an expr_xray_path instead. + +enum XrayFlag { + NoXray, //< Private items cannot be accessed. + Xray //< Private items can be accessed. +} + +enum AllowCapturingSelfFlag { + AllowCapturingSelf, //< The "self" definition can be captured. + DontAllowCapturingSelf, //< The "self" definition cannot be captured. +} + +enum EnumVariantOrConstResolution { + FoundEnumVariant(def), + FoundConst, + EnumVariantOrConstNotFound +} + +// FIXME (issue #2550): Should be a class but then it becomes not implicitly +// copyable due to a kind bug. + +type Atom = uint; + +fn Atom(n: uint) -> Atom { + return n; +} + +/// Creates a hash table of atoms. +fn atom_hashmap() -> hashmap { + hashmap::(uint::hash, uint::eq) +} + +/// One local scope. +struct Rib { + let bindings: hashmap; + let kind: RibKind; + + new(kind: RibKind) { + self.bindings = atom_hashmap(); + self.kind = kind; + } +} + +/// One import directive. +struct ImportDirective { + let module_path: @DVec; + let subclass: @ImportDirectiveSubclass; + let span: span; + + new(module_path: @DVec, + subclass: @ImportDirectiveSubclass, + span: span) { + + self.module_path = module_path; + self.subclass = subclass; + self.span = span; + } +} + +/// The item that an import resolves to. +struct Target { + let target_module: @Module; + let bindings: @NameBindings; + + new(target_module: @Module, bindings: @NameBindings) { + self.target_module = target_module; + self.bindings = bindings; + } +} + +struct ImportResolution { + let span: span; + + // The number of outstanding references to this name. When this reaches + // zero, outside modules can count on the targets being correct. Before + // then, all bets are off; future imports could override this name. + + let mut outstanding_references: uint; + + let mut module_target: Option; + let mut value_target: Option; + let mut type_target: Option; + + let mut used: bool; + + new(span: span) { + self.span = span; + + self.outstanding_references = 0u; + + self.module_target = None; + self.value_target = None; + self.type_target = None; + + self.used = false; + } + + fn target_for_namespace(namespace: Namespace) -> Option { + match namespace { + ModuleNS => return copy self.module_target, + TypeNS => return copy self.type_target, + ValueNS => return copy self.value_target + } + } +} + +/// The link from a module up to its nearest parent node. +enum ParentLink { + NoParentLink, + ModuleParentLink(@Module, Atom), + BlockParentLink(@Module, node_id) +} + +/// One node in the tree of modules. +struct Module { + let parent_link: ParentLink; + let mut def_id: Option; + + let children: hashmap; + let imports: DVec<@ImportDirective>; + + // The anonymous children of this node. Anonymous children are pseudo- + // modules that are implicitly created around items contained within + // blocks. + // + // For example, if we have this: + // + // fn f() { + // fn g() { + // ... + // } + // } + // + // There will be an anonymous module created around `g` with the ID of the + // entry block for `f`. + + let anonymous_children: hashmap; + + // XXX: This is about to be reworked so that exports are on individual + // items, not names. + // + // The atom is the name of the exported item, while the node ID is the + // ID of the export path. + + let exported_names: hashmap; + + // The status of resolving each import in this module. + let import_resolutions: hashmap; + + // The number of unresolved globs that this module exports. + let mut glob_count: uint; + + // The index of the import we're resolving. + let mut resolved_import_count: uint; + + new(parent_link: ParentLink, def_id: Option) { + self.parent_link = parent_link; + self.def_id = def_id; + + self.children = atom_hashmap(); + self.imports = DVec(); + + self.anonymous_children = int_hash(); + + self.exported_names = atom_hashmap(); + + self.import_resolutions = atom_hashmap(); + self.glob_count = 0u; + self.resolved_import_count = 0u; + } + + fn all_imports_resolved() -> bool { + return self.imports.len() == self.resolved_import_count; + } +} + +// XXX: This is a workaround due to is_none in the standard library mistakenly +// requiring a T:copy. + +pure fn is_none(x: Option) -> bool { + match x { + None => return true, + Some(_) => return false + } +} + +fn unused_import_lint_level(session: session) -> level { + for session.opts.lint_opts.each |lint_option_pair| { + let (lint_type, lint_level) = lint_option_pair; + if lint_type == unused_imports { + return lint_level; + } + } + return allow; +} + +enum Privacy { + Private, + Public +} + +// Records a possibly-private definition. +struct Definition { + privacy: Privacy; + def: def; +} + +// Records the definitions (at most one for each namespace) that a name is +// bound to. +struct NameBindings { + let mut module_def: ModuleDef; //< Meaning in module namespace. + let mut type_def: Option; //< Meaning in type namespace. + let mut value_def: Option; //< Meaning in value namespace. + + // For error reporting + // XXX: Merge me into Definition. + let mut module_span: Option; + let mut type_span: Option; + let mut value_span: Option; + + new() { + self.module_def = NoModuleDef; + self.type_def = None; + self.value_def = None; + self.module_span = None; + self.type_span = None; + self.value_span = None; + } + + /// Creates a new module in this set of name bindings. + fn define_module(parent_link: ParentLink, def_id: Option, + sp: span) { + if self.module_def == NoModuleDef { + let module_ = @Module(parent_link, def_id); + self.module_def = ModuleDef(module_); + self.module_span = Some(sp); + } + } + + /// Records a type definition. + fn define_type(privacy: Privacy, def: def, sp: span) { + self.type_def = Some(Definition { privacy: privacy, def: def }); + self.type_span = Some(sp); + } + + /// Records a value definition. + fn define_value(privacy: Privacy, def: def, sp: span) { + self.value_def = Some(Definition { privacy: privacy, def: def }); + self.value_span = Some(sp); + } + + /// Returns the module node if applicable. + fn get_module_if_available() -> Option<@Module> { + match self.module_def { + NoModuleDef => return None, + ModuleDef(module_) => return Some(module_) + } + } + + /** + * Returns the module node. Fails if this node does not have a module + * definition. + */ + fn get_module() -> @Module { + match self.module_def { + NoModuleDef => { + fail + ~"get_module called on a node with no module definition!"; + } + ModuleDef(module_) => { + return module_; + } + } + } + + fn defined_in_namespace(namespace: Namespace) -> bool { + match namespace { + ModuleNS => return self.module_def != NoModuleDef, + TypeNS => return self.type_def != None, + ValueNS => return self.value_def != None + } + } + + fn def_for_namespace(namespace: Namespace) -> Option { + match namespace { + TypeNS => return self.type_def, + ValueNS => return self.value_def, + ModuleNS => match self.module_def { + NoModuleDef => return None, + ModuleDef(module_) => + match module_.def_id { + None => return None, + Some(def_id) => { + return Some(Definition { + privacy: Public, + def: def_mod(def_id) + }); + } + } + } + } + } + + fn span_for_namespace(namespace: Namespace) -> Option { + match self.def_for_namespace(namespace) { + Some(_) => { + match namespace { + TypeNS => self.type_span, + ValueNS => self.value_span, + ModuleNS => self.module_span + } + } + None => None + } + } +} + +/// Interns the names of the primitive types. +struct PrimitiveTypeTable { + let primitive_types: hashmap; + + new(intr: ident_interner) { + self.primitive_types = atom_hashmap(); + + self.intern(intr, @~"bool", ty_bool); + self.intern(intr, @~"char", ty_int(ty_char)); + self.intern(intr, @~"float", ty_float(ty_f)); + self.intern(intr, @~"f32", ty_float(ty_f32)); + self.intern(intr, @~"f64", ty_float(ty_f64)); + self.intern(intr, @~"int", ty_int(ty_i)); + self.intern(intr, @~"i8", ty_int(ty_i8)); + self.intern(intr, @~"i16", ty_int(ty_i16)); + self.intern(intr, @~"i32", ty_int(ty_i32)); + self.intern(intr, @~"i64", ty_int(ty_i64)); + self.intern(intr, @~"str", ty_str); + self.intern(intr, @~"uint", ty_uint(ty_u)); + self.intern(intr, @~"u8", ty_uint(ty_u8)); + self.intern(intr, @~"u16", ty_uint(ty_u16)); + self.intern(intr, @~"u32", ty_uint(ty_u32)); + self.intern(intr, @~"u64", ty_uint(ty_u64)); + } + + fn intern(intr: ident_interner, string: @~str, + primitive_type: prim_ty) { + let atom = intr.intern(string); + self.primitive_types.insert(atom, primitive_type); + } +} + +fn namespace_to_str(ns: Namespace) -> ~str { + match ns { + TypeNS => ~"type", + ValueNS => ~"value", + ModuleNS => ~"module" + } +} + +/// The main resolver class. +struct Resolver { + let session: session; + let lang_items: LanguageItems; + let crate: @crate; + + let intr: ident_interner; + + let graph_root: @NameBindings; + + let unused_import_lint_level: level; + + let trait_info: hashmap>; + let structs: hashmap; + + // The number of imports that are currently unresolved. + let mut unresolved_imports: uint; + + // The module that represents the current item scope. + let mut current_module: @Module; + + // The current set of local scopes, for values. + // XXX: Reuse ribs to avoid allocation. + let value_ribs: @DVec<@Rib>; + + // The current set of local scopes, for types. + let type_ribs: @DVec<@Rib>; + + // The current set of local scopes, for labels. + let label_ribs: @DVec<@Rib>; + + // Whether the current context is an X-ray context. An X-ray context is + // allowed to access private names of any module. + let mut xray_context: XrayFlag; + + // The trait that the current context can refer to. + let mut current_trait_refs: Option<@DVec>; + + // The atom for the keyword "self". + let self_atom: Atom; + + // The atoms for the primitive types. + let primitive_type_table: @PrimitiveTypeTable; + + // The four namespaces. + let namespaces: ~[Namespace]; + + let def_map: DefMap; + let export_map: ExportMap; + let export_map2: ExportMap2; + let trait_map: TraitMap; + + new(session: session, lang_items: LanguageItems, crate: @crate) { + self.session = session; + self.lang_items = copy lang_items; + self.crate = crate; + + // The outermost module has def ID 0; this is not reflected in the + // AST. + + self.graph_root = @NameBindings(); + (*self.graph_root).define_module(NoParentLink, + Some({ crate: 0, node: 0 }), + crate.span); + + self.unused_import_lint_level = unused_import_lint_level(session); + + self.trait_info = new_def_hash(); + self.structs = new_def_hash(); + + self.unresolved_imports = 0u; + + self.current_module = (*self.graph_root).get_module(); + self.value_ribs = @DVec(); + self.type_ribs = @DVec(); + self.label_ribs = @DVec(); + + self.xray_context = NoXray; + self.current_trait_refs = None; + + self.self_atom = syntax::parse::token::special_idents::self_; + self.primitive_type_table = @PrimitiveTypeTable(self.session. + parse_sess.interner); + + self.namespaces = ~[ ModuleNS, TypeNS, ValueNS ]; + + self.def_map = int_hash(); + self.export_map = int_hash(); + self.export_map2 = int_hash(); + self.trait_map = @int_hash(); + + self.intr = session.intr(); + } + + /// The main name resolution procedure. + fn resolve(@self, this: @Resolver) { + self.build_reduced_graph(this); + self.session.abort_if_errors(); + + self.resolve_imports(); + self.session.abort_if_errors(); + + self.record_exports(); + self.session.abort_if_errors(); + + self.resolve_crate(); + self.session.abort_if_errors(); + + self.check_for_unused_imports_if_necessary(); + } + + // + // Reduced graph building + // + // Here we build the "reduced graph": the graph of the module tree without + // any imports resolved. + // + + /// Constructs the reduced graph for the entire crate. + fn build_reduced_graph(this: @Resolver) { + let initial_parent = + ModuleReducedGraphParent((*self.graph_root).get_module()); + visit_crate(*self.crate, initial_parent, mk_vt(@{ + visit_item: |item, context, visitor| + (*this).build_reduced_graph_for_item(item, context, visitor), + + visit_foreign_item: |foreign_item, context, visitor| + (*this).build_reduced_graph_for_foreign_item(foreign_item, + context, + visitor), + + visit_view_item: |view_item, context, visitor| + (*this).build_reduced_graph_for_view_item(view_item, + context, + visitor), + + visit_block: |block, context, visitor| + (*this).build_reduced_graph_for_block(block, + context, + visitor) + + with *default_visitor() + })); + } + + fn visibility_to_privacy(visibility: visibility) -> Privacy { + match visibility { + inherited | public => Public, + private => Private + } + } + + /// Returns the current module tracked by the reduced graph parent. + fn get_module_from_parent(reduced_graph_parent: ReducedGraphParent) + -> @Module { + match reduced_graph_parent { + ModuleReducedGraphParent(module_) => { + return module_; + } + } + } + + /** + * Adds a new child item to the module definition of the parent node and + * returns its corresponding name bindings as well as the current parent. + * Or, if we're inside a block, creates (or reuses) an anonymous module + * corresponding to the innermost block ID and returns the name bindings + * as well as the newly-created parent. + * + * If this node does not have a module definition and we are not inside + * a block, fails. + */ + fn add_child(name: Atom, + reduced_graph_parent: ReducedGraphParent, + // Pass in the namespaces for the child item so that we can + // check for duplicate items in the same namespace + ns: ~[Namespace], + // For printing errors + sp: span) + -> (@NameBindings, ReducedGraphParent) { + + // If this is the immediate descendant of a module, then we add the + // child name directly. Otherwise, we create or reuse an anonymous + // module and add the child to that. + + let mut module_; + match reduced_graph_parent { + ModuleReducedGraphParent(parent_module) => { + module_ = parent_module; + } + } + + // Add or reuse the child. + let new_parent = ModuleReducedGraphParent(module_); + match module_.children.find(name) { + None => { + let child = @NameBindings(); + module_.children.insert(name, child); + return (child, new_parent); + } + Some(child) => { + // We don't want to complain if the multiple definitions + // are in different namespaces. + match ns.find(|n| child.defined_in_namespace(n)) { + Some(ns) => { + self.session.span_err(sp, + #fmt("Duplicate definition of %s %s", + namespace_to_str(ns), + self.session.str_of(name))); + do child.span_for_namespace(ns).iter() |sp| { + self.session.span_note(sp, + #fmt("First definition of %s %s here:", + namespace_to_str(ns), + self.session.str_of(name))); + } + } + _ => {} + } + return (child, new_parent); + } + } + } + + fn block_needs_anonymous_module(block: blk) -> bool { + // If the block has view items, we need an anonymous module. + if block.node.view_items.len() > 0u { + return true; + } + + // Check each statement. + for block.node.stmts.each |statement| { + match statement.node { + stmt_decl(declaration, _) => { + match declaration.node { + decl_item(_) => { + return true; + } + _ => { + // Keep searching. + } + } + } + _ => { + // Keep searching. + } + } + } + + // If we found neither view items nor items, we don't need to create + // an anonymous module. + + return false; + } + + fn get_parent_link(parent: ReducedGraphParent, name: Atom) -> ParentLink { + match parent { + ModuleReducedGraphParent(module_) => { + return ModuleParentLink(module_, name); + } + } + } + + /// Constructs the reduced graph for one item. + fn build_reduced_graph_for_item(item: @item, + parent: ReducedGraphParent, + &&visitor: vt) { + + let atom = item.ident; + let sp = item.span; + + match item.node { + item_mod(module_) => { + let (name_bindings, new_parent) = self.add_child(atom, parent, + ~[ModuleNS], sp); + + let parent_link = self.get_parent_link(new_parent, atom); + let def_id = { crate: 0, node: item.id }; + (*name_bindings).define_module(parent_link, Some(def_id), + sp); + + let new_parent = + ModuleReducedGraphParent((*name_bindings).get_module()); + + visit_mod(module_, sp, item.id, new_parent, visitor); + } + item_foreign_mod(fm) => { + let new_parent = match fm.sort { + named => { + let (name_bindings, new_parent) = self.add_child(atom, + parent, ~[ModuleNS], sp); + + let parent_link = self.get_parent_link(new_parent, atom); + let def_id = { crate: 0, node: item.id }; + (*name_bindings).define_module(parent_link, Some(def_id), + sp); + + ModuleReducedGraphParent((*name_bindings).get_module()) + } + // For anon foreign mods, the contents just go in the + // current scope + anonymous => parent + }; + + visit_item(item, new_parent, visitor); + } + + // These items live in the value namespace. + item_const(*) => { + let (name_bindings, _) = self.add_child(atom, parent, + ~[ValueNS], sp); + + (*name_bindings).define_value + (self.visibility_to_privacy(item.vis), + def_const(local_def(item.id)), + sp); + } + item_fn(_, purity, _, _) => { + let (name_bindings, new_parent) = self.add_child(atom, parent, + ~[ValueNS], sp); + + let def = def_fn(local_def(item.id), purity); + (*name_bindings).define_value + (self.visibility_to_privacy(item.vis), def, sp); + visit_item(item, new_parent, visitor); + } + + // These items live in the type namespace. + item_ty(*) => { + let (name_bindings, _) = self.add_child(atom, parent, + ~[TypeNS], sp); + + (*name_bindings).define_type + (self.visibility_to_privacy(item.vis), + def_ty(local_def(item.id)), + sp); + } + + item_enum(enum_definition, _) => { + + let (name_bindings, new_parent) = self.add_child(atom, parent, + ~[TypeNS], sp); + + (*name_bindings).define_type + (self.visibility_to_privacy(item.vis), + def_ty(local_def(item.id)), + sp); + + for enum_definition.variants.each |variant| { + self.build_reduced_graph_for_variant(variant, + local_def(item.id), + new_parent, + visitor); + } + } + + // These items live in both the type and value namespaces. + item_class(struct_definition, _) => { + let new_parent = + match struct_definition.ctor { + None => { + let (name_bindings, new_parent) = + self.add_child(atom, parent, ~[TypeNS], sp); + + (*name_bindings).define_type + (self.visibility_to_privacy(item.vis), + def_ty(local_def(item.id)), + sp); + new_parent + } + Some(ctor) => { + let (name_bindings, new_parent) = + self.add_child(atom, parent, ~[ValueNS, TypeNS], + sp); + + let privacy = self.visibility_to_privacy(item.vis); + + (*name_bindings).define_type + (privacy, def_ty(local_def(item.id)), sp); + + let purity = impure_fn; + let ctor_def = def_fn(local_def(ctor.node.id), + purity); + (*name_bindings).define_value(privacy, ctor_def, sp); + new_parent + } + }; + + // Record the def ID of this struct. + self.structs.insert(local_def(item.id), + is_some(struct_definition.ctor)); + + visit_item(item, new_parent, visitor); + } + + item_impl(*) => { + visit_item(item, parent, visitor); + } + + item_trait(_, _, methods) => { + let (name_bindings, new_parent) = self.add_child(atom, parent, + ~[TypeNS], sp); + + // Add the names of all the methods to the trait info. + let method_names = @atom_hashmap(); + for methods.each |method| { + let ty_m = trait_method_to_ty_method(method); + + let atom = ty_m.ident; + // Add it to the trait info if not static, + // add it as a name in the enclosing module otherwise. + match ty_m.self_ty.node { + sty_static => { + // which parent to use?? + let (method_name_bindings, _) = + self.add_child(atom, new_parent, ~[ValueNS], + ty_m.span); + let def = def_static_method(local_def(ty_m.id), + ty_m.purity); + (*method_name_bindings).define_value + (Public, def, ty_m.span); + } + _ => { + (*method_names).insert(atom, ()); + } + } + } + + let def_id = local_def(item.id); + self.trait_info.insert(def_id, method_names); + + (*name_bindings).define_type + (self.visibility_to_privacy(item.vis), + def_ty(def_id), + sp); + visit_item(item, new_parent, visitor); + } + + item_mac(*) => { + fail ~"item macros unimplemented" + } + } + } + + // Constructs the reduced graph for one variant. Variants exist in the + // type and/or value namespaces. + fn build_reduced_graph_for_variant(variant: variant, + item_id: def_id, + parent: ReducedGraphParent, + &&visitor: vt) { + + let atom = variant.node.name; + let (child, _) = self.add_child(atom, parent, ~[ValueNS], + variant.span); + + match variant.node.kind { + tuple_variant_kind(_) => { + (*child).define_value(Public, + def_variant(item_id, + local_def(variant.node.id)), + variant.span); + } + struct_variant_kind(_) => { + (*child).define_type(Public, + def_variant(item_id, + local_def(variant.node.id)), + variant.span); + self.structs.insert(local_def(variant.node.id), false); + } + enum_variant_kind(enum_definition) => { + (*child).define_type(Public, + def_ty(local_def(variant.node.id)), + variant.span); + for enum_definition.variants.each |variant| { + self.build_reduced_graph_for_variant(variant, item_id, + parent, visitor); + } + } + } + } + + /** + * Constructs the reduced graph for one 'view item'. View items consist + * of imports and use directives. + */ + fn build_reduced_graph_for_view_item(view_item: @view_item, + parent: ReducedGraphParent, + &&_visitor: vt) { + match view_item.node { + view_item_import(view_paths) => { + for view_paths.each |view_path| { + // Extract and intern the module part of the path. For + // globs and lists, the path is found directly in the AST; + // for simple paths we have to munge the path a little. + + let module_path = @DVec(); + match view_path.node { + view_path_simple(_, full_path, _) => { + let path_len = full_path.idents.len(); + assert path_len != 0u; + + for full_path.idents.eachi |i, ident| { + if i != path_len - 1u { + (*module_path).push(ident); + } + } + } + + view_path_glob(module_ident_path, _) | + view_path_list(module_ident_path, _, _) => { + for module_ident_path.idents.each |ident| { + (*module_path).push(ident); + } + } + } + + // Build up the import directives. + let module_ = self.get_module_from_parent(parent); + match view_path.node { + view_path_simple(binding, full_path, _) => { + let source_ident = full_path.idents.last(); + let subclass = @SingleImport(binding, + source_ident); + self.build_import_directive(module_, + module_path, + subclass, + view_path.span); + } + view_path_list(_, source_idents, _) => { + for source_idents.each |source_ident| { + let name = source_ident.node.name; + let subclass = @SingleImport(name, name); + self.build_import_directive(module_, + module_path, + subclass, + view_path.span); + } + } + view_path_glob(_, _) => { + self.build_import_directive(module_, + module_path, + @GlobImport, + view_path.span); + } + } + } + } + + view_item_export(view_paths) => { + let module_ = self.get_module_from_parent(parent); + for view_paths.each |view_path| { + match view_path.node { + view_path_simple(ident, full_path, ident_id) => { + let last_ident = full_path.idents.last(); + if last_ident != ident { + self.session.span_err(view_item.span, + ~"cannot export under \ + a new name"); + } + if full_path.idents.len() != 1u { + self.session.span_err( + view_item.span, + ~"cannot export an item \ + that is not in this \ + module"); + } + + module_.exported_names.insert(ident, ident_id); + } + + view_path_glob(*) => { + self.session.span_err(view_item.span, + ~"export globs are \ + unsupported"); + } + + view_path_list(path, path_list_idents, _) => { + if path.idents.len() == 1u && + path_list_idents.len() == 0u { + + self.session.span_warn(view_item.span, + ~"this syntax for \ + exporting no \ + variants is \ + unsupported; export \ + variants \ + individually"); + } else { + if path.idents.len() != 0u { + self.session.span_err(view_item.span, + ~"cannot export an \ + item that is not \ + in this module"); + } + + for path_list_idents.each |path_list_ident| { + let atom = path_list_ident.node.name; + let id = path_list_ident.node.id; + module_.exported_names.insert(atom, id); + } + } + } + } + } + } + + view_item_use(name, _, node_id) => { + match find_use_stmt_cnum(self.session.cstore, node_id) { + Some(crate_id) => { + let (child_name_bindings, new_parent) = + // should this be in ModuleNS? --tjc + self.add_child(name, parent, ~[ModuleNS], + view_item.span); + + let def_id = { crate: crate_id, node: 0 }; + let parent_link = ModuleParentLink + (self.get_module_from_parent(new_parent), name); + + (*child_name_bindings).define_module(parent_link, + Some(def_id), + view_item.span); + self.build_reduced_graph_for_external_crate + ((*child_name_bindings).get_module()); + } + None => { + /* Ignore. */ + } + } + } + } + } + + /// Constructs the reduced graph for one foreign item. + fn build_reduced_graph_for_foreign_item(foreign_item: @foreign_item, + parent: ReducedGraphParent, + &&visitor: + vt) { + + let name = foreign_item.ident; + let (name_bindings, new_parent) = + self.add_child(name, parent, ~[ValueNS], foreign_item.span); + + match foreign_item.node { + foreign_item_fn(_, purity, type_parameters) => { + let def = def_fn(local_def(foreign_item.id), purity); + (*name_bindings).define_value(Public, def, foreign_item.span); + + do self.with_type_parameter_rib + (HasTypeParameters(&type_parameters, foreign_item.id, + 0u, NormalRibKind)) { + visit_foreign_item(foreign_item, new_parent, visitor); + } + } + foreign_item_const(*) => { + let def = def_const(local_def(foreign_item.id)); + (*name_bindings).define_value(Public, def, foreign_item.span); + + visit_foreign_item(foreign_item, new_parent, visitor); + } + } + } + + fn build_reduced_graph_for_block(block: blk, + parent: ReducedGraphParent, + &&visitor: vt) { + + let mut new_parent; + if self.block_needs_anonymous_module(block) { + let block_id = block.node.id; + + debug!("(building reduced graph for block) creating a new \ + anonymous module for block %d", + block_id); + + let parent_module = self.get_module_from_parent(parent); + let new_module = @Module(BlockParentLink(parent_module, block_id), + None); + parent_module.anonymous_children.insert(block_id, new_module); + new_parent = ModuleReducedGraphParent(new_module); + } else { + new_parent = parent; + } + + visit_block(block, new_parent, visitor); + } + + fn handle_external_def(def: def, modules: hashmap, + child_name_bindings: @NameBindings, + final_ident: ~str, + atom: Atom, new_parent: ReducedGraphParent) { + match def { + def_mod(def_id) | def_foreign_mod(def_id) => { + match copy child_name_bindings.module_def { + NoModuleDef => { + debug!("(building reduced graph for \ + external crate) building module \ + %s", final_ident); + let parent_link = self.get_parent_link(new_parent, atom); + + match modules.find(def_id) { + None => { + child_name_bindings.define_module(parent_link, + Some(def_id), + dummy_sp()); + modules.insert(def_id, + child_name_bindings.get_module()); + } + Some(existing_module) => { + // Create an import resolution to + // avoid creating cycles in the + // module graph. + + let resolution = @ImportResolution(dummy_sp()); + resolution.outstanding_references = 0; + + match existing_module.parent_link { + NoParentLink | + BlockParentLink(*) => { + fail ~"can't happen"; + } + ModuleParentLink(parent_module, atom) => { + + let name_bindings = parent_module.children.get(atom); + + resolution.module_target = + Some(Target(parent_module, name_bindings)); + } + } + + debug!("(building reduced graph for external crate) \ + ... creating import resolution"); + + new_parent.import_resolutions.insert(atom, resolution); + } + } + } + ModuleDef(module_) => { + debug!("(building reduced graph for \ + external crate) already created \ + module"); + module_.def_id = Some(def_id); + modules.insert(def_id, module_); + } + } + } + def_fn(*) | def_static_method(*) | def_const(*) | + def_variant(*) => { + debug!("(building reduced graph for external \ + crate) building value %s", final_ident); + (*child_name_bindings).define_value(Public, def, dummy_sp()); + } + def_ty(def_id) => { + debug!("(building reduced graph for external \ + crate) building type %s", final_ident); + + // If this is a trait, add all the method names + // to the trait info. + + match get_method_names_if_trait(self.session.cstore, + def_id) { + None => { + // Nothing to do. + } + Some(method_names) => { + let interned_method_names = @atom_hashmap(); + for method_names.each |method_data| { + let (method_name, self_ty) = method_data; + debug!("(building reduced graph for \ + external crate) ... adding \ + trait method '%s'", + self.session.str_of(method_name)); + + // Add it to the trait info if not static. + if self_ty != sty_static { + interned_method_names.insert(method_name, ()); + } + } + self.trait_info.insert(def_id, interned_method_names); + } + } + + child_name_bindings.define_type(Public, def, dummy_sp()); + } + def_class(def_id, has_constructor) => { + debug!("(building reduced graph for external \ + crate) building type %s (value? %d)", + final_ident, + if has_constructor { 1 } else { 0 }); + child_name_bindings.define_type(Public, def, dummy_sp()); + + if has_constructor { + child_name_bindings.define_value(Public, def, dummy_sp()); + } + + self.structs.insert(def_id, has_constructor); + } + def_self(*) | def_arg(*) | def_local(*) | + def_prim_ty(*) | def_ty_param(*) | def_binding(*) | + def_use(*) | def_upvar(*) | def_region(*) | + def_typaram_binder(*) | def_label(*) => { + fail fmt!("didn't expect `%?`", def); + } + } + } + + /** + * Builds the reduced graph rooted at the 'use' directive for an external + * crate. + */ + fn build_reduced_graph_for_external_crate(root: @Module) { + let modules = new_def_hash(); + + // Create all the items reachable by paths. + for each_path(self.session.cstore, get(root.def_id).crate) + |path_entry| { + + debug!("(building reduced graph for external crate) found path \ + entry: %s (%?)", + path_entry.path_string, + path_entry.def_like); + + let mut pieces = split_str(path_entry.path_string, ~"::"); + let final_ident_str = pop(pieces); + let final_ident = self.session.ident_of(final_ident_str); + + // Find the module we need, creating modules along the way if we + // need to. + + let mut current_module = root; + for pieces.each |ident_str| { + let ident = self.session.ident_of(ident_str); + // Create or reuse a graph node for the child. + let (child_name_bindings, new_parent) = + self.add_child(ident, + ModuleReducedGraphParent(current_module), + // May want a better span + ~[], dummy_sp()); + + // Define or reuse the module node. + match child_name_bindings.module_def { + NoModuleDef => { + debug!("(building reduced graph for external crate) \ + autovivifying %s", ident_str); + let parent_link = self.get_parent_link(new_parent, + ident); + (*child_name_bindings).define_module(parent_link, + None, dummy_sp()); + } + ModuleDef(_) => { /* Fall through. */ } + } + + current_module = (*child_name_bindings).get_module(); + } + + // Add the new child item. + let (child_name_bindings, new_parent) = + self.add_child(final_ident, + ModuleReducedGraphParent(current_module), + ~[], dummy_sp()); + + match path_entry.def_like { + dl_def(def) => { + self.handle_external_def(def, modules, + child_name_bindings, + self.session.str_of(final_ident), + final_ident, new_parent); + } + dl_impl(_) => { + // Because of the infelicitous way the metadata is + // written, we can't process this impl now. We'll get it + // later. + + debug!("(building reduced graph for external crate) \ + ignoring impl %s", final_ident_str); + } + dl_field => { + debug!("(building reduced graph for external crate) \ + ignoring field %s", final_ident_str); + } + } + } + } + + /// Creates and adds an import directive to the given module. + fn build_import_directive(module_: @Module, + module_path: @DVec, + subclass: @ImportDirectiveSubclass, + span: span) { + + let directive = @ImportDirective(module_path, subclass, span); + module_.imports.push(directive); + + // Bump the reference count on the name. Or, if this is a glob, set + // the appropriate flag. + + match *subclass { + SingleImport(target, _) => { + match module_.import_resolutions.find(target) { + Some(resolution) => { + resolution.outstanding_references += 1u; + } + None => { + let resolution = @ImportResolution(span); + resolution.outstanding_references = 1u; + module_.import_resolutions.insert(target, resolution); + } + } + } + GlobImport => { + // Set the glob flag. This tells us that we don't know the + // module's exports ahead of time. + + module_.glob_count += 1u; + } + } + + self.unresolved_imports += 1u; + } + + // Import resolution + // + // This is a fixed-point algorithm. We resolve imports until our efforts + // are stymied by an unresolved import; then we bail out of the current + // module and continue. We terminate successfully once no more imports + // remain or unsuccessfully when no forward progress in resolving imports + // is made. + + /** + * Resolves all imports for the crate. This method performs the fixed- + * point iteration. + */ + fn resolve_imports() { + let mut i = 0u; + let mut prev_unresolved_imports = 0u; + loop { + debug!("(resolving imports) iteration %u, %u imports left", + i, self.unresolved_imports); + + let module_root = (*self.graph_root).get_module(); + self.resolve_imports_for_module_subtree(module_root); + + if self.unresolved_imports == 0u { + debug!("(resolving imports) success"); + break; + } + + if self.unresolved_imports == prev_unresolved_imports { + self.session.err(~"failed to resolve imports"); + self.report_unresolved_imports(module_root); + break; + } + + i += 1u; + prev_unresolved_imports = self.unresolved_imports; + } + } + + /** + * Attempts to resolve imports for the given module and all of its + * submodules. + */ + fn resolve_imports_for_module_subtree(module_: @Module) { + debug!("(resolving imports for module subtree) resolving %s", + self.module_to_str(module_)); + self.resolve_imports_for_module(module_); + + for module_.children.each |_name, child_node| { + match (*child_node).get_module_if_available() { + None => { + // Nothing to do. + } + Some(child_module) => { + self.resolve_imports_for_module_subtree(child_module); + } + } + } + + for module_.anonymous_children.each |_block_id, child_module| { + self.resolve_imports_for_module_subtree(child_module); + } + } + + /// Attempts to resolve imports for the given module only. + fn resolve_imports_for_module(module_: @Module) { + if (*module_).all_imports_resolved() { + debug!("(resolving imports for module) all imports resolved for \ + %s", + self.module_to_str(module_)); + return; + } + + let import_count = module_.imports.len(); + while module_.resolved_import_count < import_count { + let import_index = module_.resolved_import_count; + let import_directive = module_.imports.get_elt(import_index); + match self.resolve_import_for_module(module_, import_directive) { + Failed => { + // We presumably emitted an error. Continue. + self.session.span_err(import_directive.span, + ~"failed to resolve import"); + } + Indeterminate => { + // Bail out. We'll come around next time. + break; + } + Success(()) => { + // Good. Continue. + } + } + + module_.resolved_import_count += 1u; + } + } + + fn atoms_to_str(atoms: ~[Atom]) -> ~str { + // XXX: str::connect should do this. + let mut result = ~""; + let mut first = true; + for atoms.each() |atom| { + if first { + first = false; + } else { + result += ~"::"; + } + result += self.session.str_of(atom); + } + // XXX: Shouldn't copy here. We need string builder functionality. + return result; + } + /** + * Attempts to resolve the given import. The return value indicates + * failure if we're certain the name does not exist, indeterminate if we + * don't know whether the name exists at the moment due to other + * currently-unresolved imports, or success if we know the name exists. + * If successful, the resolved bindings are written into the module. + */ + fn resolve_import_for_module(module_: @Module, + import_directive: @ImportDirective) + -> ResolveResult<()> { + + let mut resolution_result; + let module_path = import_directive.module_path; + + debug!("(resolving import for module) resolving import `%s::...` in \ + `%s`", + self.atoms_to_str((*module_path).get()), + self.module_to_str(module_)); + + // One-level renaming imports of the form `import foo = bar;` are + // handled specially. + + if (*module_path).len() == 0u { + resolution_result = + self.resolve_one_level_renaming_import(module_, + import_directive); + } else { + // First, resolve the module path for the directive, if necessary. + match self.resolve_module_path_for_import(module_, + module_path, + NoXray, + import_directive.span) { + + Failed => { + resolution_result = Failed; + } + Indeterminate => { + resolution_result = Indeterminate; + } + Success(containing_module) => { + // We found the module that the target is contained + // within. Attempt to resolve the import within it. + + match *import_directive.subclass { + SingleImport(target, source) => { + resolution_result = + self.resolve_single_import(module_, + containing_module, + target, + source); + } + GlobImport => { + let span = import_directive.span; + resolution_result = + self.resolve_glob_import(module_, + containing_module, + span); + } + } + } + } + } + + // Decrement the count of unresolved imports. + match resolution_result { + Success(()) => { + assert self.unresolved_imports >= 1u; + self.unresolved_imports -= 1u; + } + _ => { + // Nothing to do here; just return the error. + } + } + + // Decrement the count of unresolved globs if necessary. But only if + // the resolution result is indeterminate -- otherwise we'll stop + // processing imports here. (See the loop in + // resolve_imports_for_module.) + + if resolution_result != Indeterminate { + match *import_directive.subclass { + GlobImport => { + assert module_.glob_count >= 1u; + module_.glob_count -= 1u; + } + SingleImport(*) => { + // Ignore. + } + } + } + + return resolution_result; + } + + fn resolve_single_import(module_: @Module, containing_module: @Module, + target: Atom, source: Atom) + -> ResolveResult<()> { + + debug!("(resolving single import) resolving `%s` = `%s::%s` from \ + `%s`", + self.session.str_of(target), + self.module_to_str(containing_module), + self.session.str_of(source), + self.module_to_str(module_)); + + if !self.name_is_exported(containing_module, source) { + debug!("(resolving single import) name `%s` is unexported", + self.session.str_of(source)); + return Failed; + } + + // We need to resolve all four namespaces for this to succeed. + // + // XXX: See if there's some way of handling namespaces in a more + // generic way. We have four of them; it seems worth doing... + + let mut module_result = UnknownResult; + let mut value_result = UnknownResult; + let mut type_result = UnknownResult; + + // Search for direct children of the containing module. + match containing_module.children.find(source) { + None => { + // Continue. + } + Some(child_name_bindings) => { + if (*child_name_bindings).defined_in_namespace(ModuleNS) { + module_result = BoundResult(containing_module, + child_name_bindings); + } + if (*child_name_bindings).defined_in_namespace(ValueNS) { + value_result = BoundResult(containing_module, + child_name_bindings); + } + if (*child_name_bindings).defined_in_namespace(TypeNS) { + type_result = BoundResult(containing_module, + child_name_bindings); + } + } + } + + // Unless we managed to find a result in all four namespaces + // (exceedingly unlikely), search imports as well. + + match (module_result, value_result, type_result) { + (BoundResult(*), BoundResult(*), BoundResult(*)) => { + // Continue. + } + _ => { + // If there is an unresolved glob at this point in the + // containing module, bail out. We don't know enough to be + // able to resolve this import. + + if containing_module.glob_count > 0u { + debug!("(resolving single import) unresolved glob; \ + bailing out"); + return Indeterminate; + } + + // Now search the exported imports within the containing + // module. + + match containing_module.import_resolutions.find(source) { + None => { + // The containing module definitely doesn't have an + // exported import with the name in question. We can + // therefore accurately report that the names are + // unbound. + + if module_result == UnknownResult { + module_result = UnboundResult; + } + if value_result == UnknownResult { + value_result = UnboundResult; + } + if type_result == UnknownResult { + type_result = UnboundResult; + } + } + Some(import_resolution) + if import_resolution.outstanding_references + == 0u => { + + fn get_binding(import_resolution: @ImportResolution, + namespace: Namespace) + -> NamespaceResult { + + match (*import_resolution). + target_for_namespace(namespace) { + None => { + return UnboundResult; + } + Some(target) => { + import_resolution.used = true; + return BoundResult(target.target_module, + target.bindings); + } + } + } + + // The name is an import which has been fully + // resolved. We can, therefore, just follow it. + + if module_result == UnknownResult { + module_result = get_binding(import_resolution, + ModuleNS); + } + if value_result == UnknownResult { + value_result = get_binding(import_resolution, + ValueNS); + } + if type_result == UnknownResult { + type_result = get_binding(import_resolution, + TypeNS); + } + } + Some(_) => { + // The import is unresolved. Bail out. + debug!("(resolving single import) unresolved import; \ + bailing out"); + return Indeterminate; + } + } + } + } + + // We've successfully resolved the import. Write the results in. + assert module_.import_resolutions.contains_key(target); + let import_resolution = module_.import_resolutions.get(target); + + match module_result { + BoundResult(target_module, name_bindings) => { + debug!("(resolving single import) found module binding"); + import_resolution.module_target = + Some(Target(target_module, name_bindings)); + } + UnboundResult => { + debug!("(resolving single import) didn't find module \ + binding"); + } + UnknownResult => { + fail ~"module result should be known at this point"; + } + } + match value_result { + BoundResult(target_module, name_bindings) => { + import_resolution.value_target = + Some(Target(target_module, name_bindings)); + } + UnboundResult => { /* Continue. */ } + UnknownResult => { + fail ~"value result should be known at this point"; + } + } + match type_result { + BoundResult(target_module, name_bindings) => { + import_resolution.type_target = + Some(Target(target_module, name_bindings)); + } + UnboundResult => { /* Continue. */ } + UnknownResult => { + fail ~"type result should be known at this point"; + } + } + + let i = import_resolution; + match (i.module_target, i.value_target, i.type_target) { + /* + If this name wasn't found in any of the four namespaces, it's + definitely unresolved + */ + (None, None, None) => { return Failed; } + _ => {} + } + + assert import_resolution.outstanding_references >= 1u; + import_resolution.outstanding_references -= 1u; + + debug!("(resolving single import) successfully resolved import"); + return Success(()); + } + + /** + * Resolves a glob import. Note that this function cannot fail; it either + * succeeds or bails out (as importing * from an empty module or a module + * that exports nothing is valid). + */ + fn resolve_glob_import(module_: @Module, + containing_module: @Module, + span: span) + -> ResolveResult<()> { + + // This function works in a highly imperative manner; it eagerly adds + // everything it can to the list of import resolutions of the module + // node. + + // We must bail out if the node has unresolved imports of any kind + // (including globs). + + if !(*containing_module).all_imports_resolved() { + debug!("(resolving glob import) target module has unresolved \ + imports; bailing out"); + return Indeterminate; + } + + assert containing_module.glob_count == 0u; + + // Add all resolved imports from the containing module. + for containing_module.import_resolutions.each + |atom, target_import_resolution| { + + if !self.name_is_exported(containing_module, atom) { + debug!("(resolving glob import) name `%s` is unexported", + self.session.str_of(atom)); + again; + } + + debug!("(resolving glob import) writing module resolution \ + %? into `%s`", + is_none(target_import_resolution.module_target), + self.module_to_str(module_)); + + // Here we merge two import resolutions. + match module_.import_resolutions.find(atom) { + None => { + // Simple: just copy the old import resolution. + let new_import_resolution = + @ImportResolution(target_import_resolution.span); + new_import_resolution.module_target = + copy target_import_resolution.module_target; + new_import_resolution.value_target = + copy target_import_resolution.value_target; + new_import_resolution.type_target = + copy target_import_resolution.type_target; + + module_.import_resolutions.insert + (atom, new_import_resolution); + } + Some(dest_import_resolution) => { + // Merge the two import resolutions at a finer-grained + // level. + + match copy target_import_resolution.module_target { + None => { + // Continue. + } + Some(module_target) => { + dest_import_resolution.module_target = + Some(copy module_target); + } + } + match copy target_import_resolution.value_target { + None => { + // Continue. + } + Some(value_target) => { + dest_import_resolution.value_target = + Some(copy value_target); + } + } + match copy target_import_resolution.type_target { + None => { + // Continue. + } + Some(type_target) => { + dest_import_resolution.type_target = + Some(copy type_target); + } + } + } + } + } + + // Add all children from the containing module. + for containing_module.children.each |atom, name_bindings| { + if !self.name_is_exported(containing_module, atom) { + debug!("(resolving glob import) name `%s` is unexported", + self.session.str_of(atom)); + again; + } + + let mut dest_import_resolution; + match module_.import_resolutions.find(atom) { + None => { + // Create a new import resolution from this child. + dest_import_resolution = @ImportResolution(span); + module_.import_resolutions.insert + (atom, dest_import_resolution); + } + Some(existing_import_resolution) => { + dest_import_resolution = existing_import_resolution; + } + } + + + debug!("(resolving glob import) writing resolution `%s` in `%s` \ + to `%s`", + self.session.str_of(atom), + self.module_to_str(containing_module), + self.module_to_str(module_)); + + // Merge the child item into the import resolution. + if (*name_bindings).defined_in_namespace(ModuleNS) { + debug!("(resolving glob import) ... for module target"); + dest_import_resolution.module_target = + Some(Target(containing_module, name_bindings)); + } + if (*name_bindings).defined_in_namespace(ValueNS) { + debug!("(resolving glob import) ... for value target"); + dest_import_resolution.value_target = + Some(Target(containing_module, name_bindings)); + } + if (*name_bindings).defined_in_namespace(TypeNS) { + debug!("(resolving glob import) ... for type target"); + dest_import_resolution.type_target = + Some(Target(containing_module, name_bindings)); + } + } + + debug!("(resolving glob import) successfully resolved import"); + return Success(()); + } + + fn resolve_module_path_from_root(module_: @Module, + module_path: @DVec, + index: uint, + xray: XrayFlag, + span: span) + -> ResolveResult<@Module> { + + let mut search_module = module_; + let mut index = index; + let module_path_len = (*module_path).len(); + + // Resolve the module part of the path. This does not involve looking + // upward though scope chains; we simply resolve names directly in + // modules as we go. + + while index < module_path_len { + let name = (*module_path).get_elt(index); + match self.resolve_name_in_module(search_module, name, ModuleNS, + xray) { + + Failed => { + self.session.span_err(span, ~"unresolved name"); + return Failed; + } + Indeterminate => { + debug!("(resolving module path for import) module \ + resolution is indeterminate: %s", + self.session.str_of(name)); + return Indeterminate; + } + Success(target) => { + match target.bindings.module_def { + NoModuleDef => { + // Not a module. + self.session.span_err(span, + fmt!("not a module: %s", + self.session. + str_of(name))); + return Failed; + } + ModuleDef(copy module_) => { + search_module = module_; + } + } + } + } + + index += 1u; + } + + return Success(search_module); + } + + /** + * Attempts to resolve the module part of an import directive rooted at + * the given module. + */ + fn resolve_module_path_for_import(module_: @Module, + module_path: @DVec, + xray: XrayFlag, + span: span) + -> ResolveResult<@Module> { + + let module_path_len = (*module_path).len(); + assert module_path_len > 0u; + + debug!("(resolving module path for import) processing `%s` rooted at \ + `%s`", + self.atoms_to_str((*module_path).get()), + self.module_to_str(module_)); + + // The first element of the module path must be in the current scope + // chain. + + let first_element = (*module_path).get_elt(0u); + let mut search_module; + match self.resolve_module_in_lexical_scope(module_, first_element) { + Failed => { + self.session.span_err(span, ~"unresolved name"); + return Failed; + } + Indeterminate => { + debug!("(resolving module path for import) indeterminate; \ + bailing"); + return Indeterminate; + } + Success(resulting_module) => { + search_module = resulting_module; + } + } + + return self.resolve_module_path_from_root(search_module, + module_path, + 1u, + xray, + span); + } + + fn resolve_item_in_lexical_scope(module_: @Module, + name: Atom, + namespace: Namespace) + -> ResolveResult { + + debug!("(resolving item in lexical scope) resolving `%s` in \ + namespace %? in `%s`", + self.session.str_of(name), + namespace, + self.module_to_str(module_)); + + // The current module node is handled specially. First, check for + // its immediate children. + + match module_.children.find(name) { + Some(name_bindings) + if (*name_bindings).defined_in_namespace(namespace) => { + + return Success(Target(module_, name_bindings)); + } + Some(_) | None => { /* Not found; continue. */ } + } + + // Now check for its import directives. We don't have to have resolved + // all its imports in the usual way; this is because chains of + // adjacent import statements are processed as though they mutated the + // current scope. + + match module_.import_resolutions.find(name) { + None => { + // Not found; continue. + } + Some(import_resolution) => { + match (*import_resolution).target_for_namespace(namespace) { + None => { + // Not found; continue. + debug!("(resolving item in lexical scope) found \ + import resolution, but not in namespace %?", + namespace); + } + Some(target) => { + import_resolution.used = true; + return Success(copy target); + } + } + } + } + + // Finally, proceed up the scope chain looking for parent modules. + let mut search_module = module_; + loop { + // Go to the next parent. + match search_module.parent_link { + NoParentLink => { + // No more parents. This module was unresolved. + debug!("(resolving item in lexical scope) unresolved \ + module"); + return Failed; + } + ModuleParentLink(parent_module_node, _) | + BlockParentLink(parent_module_node, _) => { + search_module = parent_module_node; + } + } + + // Resolve the name in the parent module. + match self.resolve_name_in_module(search_module, name, namespace, + Xray) { + Failed => { + // Continue up the search chain. + } + Indeterminate => { + // We couldn't see through the higher scope because of an + // unresolved import higher up. Bail. + + debug!("(resolving item in lexical scope) indeterminate \ + higher scope; bailing"); + return Indeterminate; + } + Success(target) => { + // We found the module. + return Success(copy target); + } + } + } + } + + fn resolve_module_in_lexical_scope(module_: @Module, name: Atom) + -> ResolveResult<@Module> { + + match self.resolve_item_in_lexical_scope(module_, name, ModuleNS) { + Success(target) => { + match target.bindings.module_def { + NoModuleDef => { + error!("!!! (resolving module in lexical scope) module + wasn't actually a module!"); + return Failed; + } + ModuleDef(module_) => { + return Success(module_); + } + } + } + Indeterminate => { + debug!("(resolving module in lexical scope) indeterminate; \ + bailing"); + return Indeterminate; + } + Failed => { + debug!("(resolving module in lexical scope) failed to \ + resolve"); + return Failed; + } + } + } + + fn name_is_exported(module_: @Module, name: Atom) -> bool { + return module_.exported_names.size() == 0u || + module_.exported_names.contains_key(name); + } + + /** + * Attempts to resolve the supplied name in the given module for the + * given namespace. If successful, returns the target corresponding to + * the name. + */ + fn resolve_name_in_module(module_: @Module, + name: Atom, + namespace: Namespace, + xray: XrayFlag) + -> ResolveResult { + + debug!("(resolving name in module) resolving `%s` in `%s`", + self.session.str_of(name), + self.module_to_str(module_)); + + if xray == NoXray && !self.name_is_exported(module_, name) { + debug!("(resolving name in module) name `%s` is unexported", + self.session.str_of(name)); + return Failed; + } + + // First, check the direct children of the module. + match module_.children.find(name) { + Some(name_bindings) + if (*name_bindings).defined_in_namespace(namespace) => { + + debug!("(resolving name in module) found node as child"); + return Success(Target(module_, name_bindings)); + } + Some(_) | None => { + // Continue. + } + } + + // Next, check the module's imports. If the module has a glob, then + // we bail out; we don't know its imports yet. + + if module_.glob_count > 0u { + debug!("(resolving name in module) module has glob; bailing out"); + return Indeterminate; + } + + // Otherwise, we check the list of resolved imports. + match module_.import_resolutions.find(name) { + Some(import_resolution) => { + if import_resolution.outstanding_references != 0u { + debug!("(resolving name in module) import unresolved; \ + bailing out"); + return Indeterminate; + } + + match (*import_resolution).target_for_namespace(namespace) { + None => { + debug!("(resolving name in module) name found, but \ + not in namespace %?", + namespace); + } + Some(target) => { + debug!("(resolving name in module) resolved to \ + import"); + import_resolution.used = true; + return Success(copy target); + } + } + } + None => { + // Continue. + } + } + + // We're out of luck. + debug!("(resolving name in module) failed to resolve %s", + self.session.str_of(name)); + return Failed; + } + + /** + * Resolves a one-level renaming import of the kind `import foo = bar;` + * This needs special handling, as, unlike all of the other imports, it + * needs to look in the scope chain for modules and non-modules alike. + */ + fn resolve_one_level_renaming_import(module_: @Module, + import_directive: @ImportDirective) + -> ResolveResult<()> { + + let mut target_name; + let mut source_name; + match *import_directive.subclass { + SingleImport(target, source) => { + target_name = target; + source_name = source; + } + GlobImport => { + fail ~"found `import *`, which is invalid"; + } + } + + debug!("(resolving one-level naming result) resolving import `%s` = \ + `%s` in `%s`", + self.session.str_of(target_name), + self.session.str_of(source_name), + self.module_to_str(module_)); + + // Find the matching items in the lexical scope chain for every + // namespace. If any of them come back indeterminate, this entire + // import is indeterminate. + + let mut module_result; + debug!("(resolving one-level naming result) searching for module"); + match self.resolve_item_in_lexical_scope(module_, + source_name, + ModuleNS) { + + Failed => { + debug!("(resolving one-level renaming import) didn't find \ + module result"); + module_result = None; + } + Indeterminate => { + debug!("(resolving one-level renaming import) module result \ + is indeterminate; bailing"); + return Indeterminate; + } + Success(name_bindings) => { + debug!("(resolving one-level renaming import) module result \ + found"); + module_result = Some(copy name_bindings); + } + } + + let mut value_result; + debug!("(resolving one-level naming result) searching for value"); + match self.resolve_item_in_lexical_scope(module_, + source_name, + ValueNS) { + + Failed => { + debug!("(resolving one-level renaming import) didn't find \ + value result"); + value_result = None; + } + Indeterminate => { + debug!("(resolving one-level renaming import) value result \ + is indeterminate; bailing"); + return Indeterminate; + } + Success(name_bindings) => { + debug!("(resolving one-level renaming import) value result \ + found"); + value_result = Some(copy name_bindings); + } + } + + let mut type_result; + debug!("(resolving one-level naming result) searching for type"); + match self.resolve_item_in_lexical_scope(module_, + source_name, + TypeNS) { + + Failed => { + debug!("(resolving one-level renaming import) didn't find \ + type result"); + type_result = None; + } + Indeterminate => { + debug!("(resolving one-level renaming import) type result is \ + indeterminate; bailing"); + return Indeterminate; + } + Success(name_bindings) => { + debug!("(resolving one-level renaming import) type result \ + found"); + type_result = Some(copy name_bindings); + } + } + + // + // NB: This one results in effects that may be somewhat surprising. It + // means that this: + // + // mod A { + // impl foo for ... { ... } + // mod B { + // impl foo for ... { ... } + // import bar = foo; + // ... + // } + // } + // + // results in only A::B::foo being aliased to A::B::bar, not A::foo + // *and* A::B::foo being aliased to A::B::bar. + // + + // If nothing at all was found, that's an error. + if is_none(module_result) && + is_none(value_result) && + is_none(type_result) { + + self.session.span_err(import_directive.span, + ~"unresolved import"); + return Failed; + } + + // Otherwise, proceed and write in the bindings. + match module_.import_resolutions.find(target_name) { + None => { + fail ~"(resolving one-level renaming import) reduced graph \ + construction or glob importing should have created the \ + import resolution name by now"; + } + Some(import_resolution) => { + debug!("(resolving one-level renaming import) writing module \ + result %? for `%s` into `%s`", + is_none(module_result), + self.session.str_of(target_name), + self.module_to_str(module_)); + + import_resolution.module_target = module_result; + import_resolution.value_target = value_result; + import_resolution.type_target = type_result; + + assert import_resolution.outstanding_references >= 1u; + import_resolution.outstanding_references -= 1u; + } + } + + debug!("(resolving one-level renaming import) successfully resolved"); + return Success(()); + } + + fn report_unresolved_imports(module_: @Module) { + let index = module_.resolved_import_count; + let import_count = module_.imports.len(); + if index != import_count { + self.session.span_err(module_.imports.get_elt(index).span, + ~"unresolved import"); + } + + // Descend into children and anonymous children. + for module_.children.each |_name, child_node| { + match (*child_node).get_module_if_available() { + None => { + // Continue. + } + Some(child_module) => { + self.report_unresolved_imports(child_module); + } + } + } + + for module_.anonymous_children.each |_name, module_| { + self.report_unresolved_imports(module_); + } + } + + // Export recording + // + // This pass simply determines what all "export" keywords refer to and + // writes the results into the export map. + // + // XXX: This pass will be removed once exports change to per-item. Then + // this operation can simply be performed as part of item (or import) + // processing. + + fn record_exports() { + let root_module = (*self.graph_root).get_module(); + self.record_exports_for_module_subtree(root_module); + } + + fn record_exports_for_module_subtree(module_: @Module) { + // If this isn't a local crate, then bail out. We don't need to record + // exports for local crates. + + match module_.def_id { + Some(def_id) if def_id.crate == local_crate => { + // OK. Continue. + } + None => { + // Record exports for the root module. + } + Some(_) => { + // Bail out. + debug!("(recording exports for module subtree) not recording \ + exports for `%s`", + self.module_to_str(module_)); + return; + } + } + + self.record_exports_for_module(module_); + + for module_.children.each |_atom, child_name_bindings| { + match (*child_name_bindings).get_module_if_available() { + None => { + // Nothing to do. + } + Some(child_module) => { + self.record_exports_for_module_subtree(child_module); + } + } + } + + for module_.anonymous_children.each |_node_id, child_module| { + self.record_exports_for_module_subtree(child_module); + } + } + + fn record_exports_for_module(module_: @Module) { + let mut exports2 = ~[]; + for module_.exported_names.each |name, node_id| { + let mut exports = ~[]; + for self.namespaces.each |namespace| { + match self.resolve_definition_of_name_in_module(module_, + name, + namespace, + Xray) { + NoNameDefinition => { + // Nothing to do. + } + ChildNameDefinition(target_def) => { + debug!("(computing exports) found child export '%s' \ + for %?", + self.session.str_of(name), + module_.def_id); + vec::push(exports, { + reexp: false, + id: def_id_of_def(target_def) + }); + vec::push(exports2, Export2 { + reexport: false, + name: self.session.str_of(name), + def_id: def_id_of_def(target_def) + }); + } + ImportNameDefinition(target_def) => { + debug!("(computing exports) found reexport '%s' for \ + %?", + self.session.str_of(name), + module_.def_id); + vec::push(exports, { + reexp: true, + id: def_id_of_def(target_def) + }); + vec::push(exports2, Export2 { + reexport: true, + name: self.session.str_of(name), + def_id: def_id_of_def(target_def) + }); + } + } + } + + self.export_map.insert(node_id, exports); + } + + match copy module_.def_id { + Some(def_id) => { + self.export_map2.insert(def_id.node, move exports2); + debug!("(computing exports) writing exports for %d (some)", + def_id.node); + } + None => {} + } + } + + // AST resolution + // + // We maintain a list of value ribs and type ribs. + // + // Simultaneously, we keep track of the current position in the module + // graph in the `current_module` pointer. When we go to resolve a name in + // the value or type namespaces, we first look through all the ribs and + // then query the module graph. When we resolve a name in the module + // namespace, we can skip all the ribs (since nested modules are not + // allowed within blocks in Rust) and jump straight to the current module + // graph node. + // + // Named implementations are handled separately. When we find a method + // call, we consult the module node to find all of the implementations in + // scope. This information is lazily cached in the module node. We then + // generate a fake "implementation scope" containing all the + // implementations thus found, for compatibility with old resolve pass. + + fn with_scope(name: Option, f: fn()) { + let orig_module = self.current_module; + + // Move down in the graph. + match name { + None => { + // Nothing to do. + } + Some(name) => { + match orig_module.children.find(name) { + None => { + debug!("!!! (with scope) didn't find `%s` in `%s`", + self.session.str_of(name), + self.module_to_str(orig_module)); + } + Some(name_bindings) => { + match (*name_bindings).get_module_if_available() { + None => { + debug!("!!! (with scope) didn't find module \ + for `%s` in `%s`", + self.session.str_of(name), + self.module_to_str(orig_module)); + } + Some(module_) => { + self.current_module = module_; + } + } + } + } + } + } + + f(); + + self.current_module = orig_module; + } + + // Wraps the given definition in the appropriate number of `def_upvar` + // wrappers. + + fn upvarify(ribs: @DVec<@Rib>, rib_index: uint, def_like: def_like, + span: span, allow_capturing_self: AllowCapturingSelfFlag) + -> Option { + + let mut def; + let mut is_ty_param; + + match def_like { + dl_def(d @ def_local(*)) | dl_def(d @ def_upvar(*)) | + dl_def(d @ def_arg(*)) | dl_def(d @ def_binding(*)) => { + def = d; + is_ty_param = false; + } + dl_def(d @ def_ty_param(*)) => { + def = d; + is_ty_param = true; + } + dl_def(d @ def_self(*)) + if allow_capturing_self == DontAllowCapturingSelf => { + def = d; + is_ty_param = false; + } + _ => { + return Some(def_like); + } + } + + let mut rib_index = rib_index + 1u; + while rib_index < (*ribs).len() { + let rib = (*ribs).get_elt(rib_index); + match rib.kind { + NormalRibKind => { + // Nothing to do. Continue. + } + FunctionRibKind(function_id, body_id) => { + if !is_ty_param { + def = def_upvar(def_id_of_def(def).node, + @def, + function_id, + body_id); + } + } + MethodRibKind(item_id, _) => { + // If the def is a ty param, and came from the parent + // item, it's ok + match def { + def_ty_param(did, _) if self.def_map.find(copy(did.node)) + == Some(def_typaram_binder(item_id)) => { + // ok + } + _ => { + if !is_ty_param { + // This was an attempt to access an upvar inside a + // named function item. This is not allowed, so we + // report an error. + + self.session.span_err( + span, + ~"attempted dynamic environment-capture"); + } else { + // This was an attempt to use a type parameter outside + // its scope. + + self.session.span_err(span, + ~"attempt to use a type \ + argument out of scope"); + } + + return None; + } + } + } + OpaqueFunctionRibKind => { + if !is_ty_param { + // This was an attempt to access an upvar inside a + // named function item. This is not allowed, so we + // report an error. + + self.session.span_err( + span, + ~"attempted dynamic environment-capture"); + } else { + // This was an attempt to use a type parameter outside + // its scope. + + self.session.span_err(span, + ~"attempt to use a type \ + argument out of scope"); + } + + return None; + } + } + + rib_index += 1u; + } + + return Some(dl_def(def)); + } + + fn search_ribs(ribs: @DVec<@Rib>, name: Atom, span: span, + allow_capturing_self: AllowCapturingSelfFlag) + -> Option { + + // XXX: This should not use a while loop. + // XXX: Try caching? + + let mut i = (*ribs).len(); + while i != 0u { + i -= 1u; + let rib = (*ribs).get_elt(i); + match rib.bindings.find(name) { + Some(def_like) => { + return self.upvarify(ribs, i, def_like, span, + allow_capturing_self); + } + None => { + // Continue. + } + } + } + + return None; + } + + fn resolve_crate(@self) { + debug!("(resolving crate) starting"); + + visit_crate(*self.crate, (), mk_vt(@{ + visit_item: |item, _context, visitor| + self.resolve_item(item, visitor), + visit_arm: |arm, _context, visitor| + self.resolve_arm(arm, visitor), + visit_block: |block, _context, visitor| + self.resolve_block(block, visitor), + visit_expr: |expr, _context, visitor| + self.resolve_expr(expr, visitor), + visit_local: |local, _context, visitor| + self.resolve_local(local, visitor), + visit_ty: |ty, _context, visitor| + self.resolve_type(ty, visitor) + with *default_visitor() + })); + } + + fn resolve_item(item: @item, visitor: ResolveVisitor) { + debug!("(resolving item) resolving %s", + self.session.str_of(item.ident)); + + // Items with the !resolve_unexported attribute are X-ray contexts. + // This is used to allow the test runner to run unexported tests. + let orig_xray_flag = self.xray_context; + if contains_name(attr_metas(item.attrs), ~"!resolve_unexported") { + self.xray_context = Xray; + } + + match item.node { + item_enum(_, type_parameters) | + item_ty(_, type_parameters) => { + do self.with_type_parameter_rib + (HasTypeParameters(&type_parameters, item.id, 0u, + NormalRibKind)) + || { + + visit_item(item, (), visitor); + } + } + + item_impl(type_parameters, implemented_traits, self_type, + methods) => { + + self.resolve_implementation(item.id, item.span, + type_parameters, + implemented_traits, + self_type, methods, visitor); + } + + item_trait(type_parameters, traits, methods) => { + // Create a new rib for the self type. + let self_type_rib = @Rib(NormalRibKind); + (*self.type_ribs).push(self_type_rib); + self_type_rib.bindings.insert(self.self_atom, + dl_def(def_self(item.id))); + + // Create a new rib for the trait-wide type parameters. + do self.with_type_parameter_rib + (HasTypeParameters(&type_parameters, item.id, 0u, + NormalRibKind)) { + + self.resolve_type_parameters(type_parameters, visitor); + + // Resolve derived traits. + for traits.each |trt| { + match self.resolve_path(trt.path, TypeNS, true, + visitor) { + None => + self.session.span_err(trt.path.span, + ~"attempt to derive a \ + nonexistent trait"), + Some(def) => { + // Write a mapping from the trait ID to the + // definition of the trait into the definition + // map. + + debug!("(resolving trait) found trait def: \ + %?", def); + + self.record_def(trt.ref_id, def); + } + } + } + + for methods.each |method| { + // Create a new rib for the method-specific type + // parameters. + // + // XXX: Do we need a node ID here? + + match method { + required(ty_m) => { + do self.with_type_parameter_rib + (HasTypeParameters(&ty_m.tps, + item.id, + type_parameters.len(), + MethodRibKind(item.id, Required))) { + + // Resolve the method-specific type + // parameters. + self.resolve_type_parameters(ty_m.tps, + visitor); + + for ty_m.decl.inputs.each |argument| { + self.resolve_type(argument.ty, visitor); + } + + self.resolve_type(ty_m.decl.output, visitor); + } + } + provided(m) => { + self.resolve_method(MethodRibKind(item.id, + Provided(m.id)), + m, + type_parameters.len(), + visitor) + } + } + } + } + + (*self.type_ribs).pop(); + } + + item_class(struct_def, ty_params) => { + self.resolve_class(item.id, + @copy ty_params, + struct_def.traits, + struct_def.fields, + struct_def.methods, + struct_def.ctor, + struct_def.dtor, + visitor); + } + + item_mod(module_) => { + do self.with_scope(Some(item.ident)) { + self.resolve_module(module_, item.span, item.ident, + item.id, visitor); + } + } + + item_foreign_mod(foreign_module) => { + do self.with_scope(Some(item.ident)) { + for foreign_module.items.each |foreign_item| { + match foreign_item.node { + foreign_item_fn(_, _, type_parameters) => { + do self.with_type_parameter_rib + (HasTypeParameters(&type_parameters, + foreign_item.id, + 0u, + OpaqueFunctionRibKind)) + || { + + visit_foreign_item(foreign_item, (), + visitor); + } + } + foreign_item_const(_) => { + visit_foreign_item(foreign_item, (), + visitor); + } + } + } + } + } + + item_fn(fn_decl, _, ty_params, block) => { + // If this is the main function, we must record it in the + // session. + // + // For speed, we put the string comparison last in this chain + // of conditionals. + + if !self.session.building_library && + is_none(self.session.main_fn) && + item.ident == syntax::parse::token::special_idents::main { + + self.session.main_fn = Some((item.id, item.span)); + } + + self.resolve_function(OpaqueFunctionRibKind, + Some(@fn_decl), + HasTypeParameters + (&ty_params, + item.id, + 0u, + OpaqueFunctionRibKind), + block, + NoSelfBinding, + NoCaptureClause, + visitor); + } + + item_const(*) => { + visit_item(item, (), visitor); + } + + item_mac(*) => { + fail ~"item macros unimplemented" + } + } + + self.xray_context = orig_xray_flag; + } + + fn with_type_parameter_rib(type_parameters: TypeParameters, f: fn()) { + match type_parameters { + HasTypeParameters(type_parameters, node_id, initial_index, + rib_kind) => { + + let function_type_rib = @Rib(rib_kind); + (*self.type_ribs).push(function_type_rib); + + for (*type_parameters).eachi |index, type_parameter| { + let name = type_parameter.ident; + debug!("with_type_parameter_rib: %d %d", node_id, + type_parameter.id); + let def_like = dl_def(def_ty_param + (local_def(type_parameter.id), + index + initial_index)); + // Associate this type parameter with + // the item that bound it + self.record_def(type_parameter.id, + def_typaram_binder(node_id)); + (*function_type_rib).bindings.insert(name, def_like); + } + } + + NoTypeParameters => { + // Nothing to do. + } + } + + f(); + + match type_parameters { + HasTypeParameters(*) => { + (*self.type_ribs).pop(); + } + + NoTypeParameters => { + // Nothing to do. + } + } + } + + fn with_label_rib(f: fn()) { + (*self.label_ribs).push(@Rib(NormalRibKind)); + f(); + (*self.label_ribs).pop(); + } + + fn resolve_function(rib_kind: RibKind, + optional_declaration: Option<@fn_decl>, + type_parameters: TypeParameters, + block: blk, + self_binding: SelfBinding, + capture_clause: CaptureClause, + visitor: ResolveVisitor) { + + // Check each element of the capture clause. + match capture_clause { + NoCaptureClause => { + // Nothing to do. + } + HasCaptureClause(capture_clause) => { + // Resolve each captured item. + for (*capture_clause).each |capture_item| { + match self.resolve_identifier(capture_item.name, + ValueNS, + true, + capture_item.span) { + None => { + self.session.span_err(capture_item.span, + ~"unresolved name in \ + capture clause"); + } + Some(def) => { + self.record_def(capture_item.id, def); + } + } + } + } + } + + // Create a value rib for the function. + let function_value_rib = @Rib(rib_kind); + (*self.value_ribs).push(function_value_rib); + + // Create a label rib for the function. + let function_label_rib = @Rib(rib_kind); + (*self.label_ribs).push(function_label_rib); + + // If this function has type parameters, add them now. + do self.with_type_parameter_rib(type_parameters) { + // Resolve the type parameters. + match type_parameters { + NoTypeParameters => { + // Continue. + } + HasTypeParameters(type_parameters, _, _, _) => { + self.resolve_type_parameters(*type_parameters, visitor); + } + } + + // Add self to the rib, if necessary. + match self_binding { + NoSelfBinding => { + // Nothing to do. + } + HasSelfBinding(self_node_id) => { + let def_like = dl_def(def_self(self_node_id)); + (*function_value_rib).bindings.insert(self.self_atom, + def_like); + } + } + + // Add each argument to the rib. + match optional_declaration { + None => { + // Nothing to do. + } + Some(declaration) => { + for declaration.inputs.each |argument| { + let name = argument.ident; + let def_like = dl_def(def_arg(argument.id, + argument.mode)); + (*function_value_rib).bindings.insert(name, def_like); + + self.resolve_type(argument.ty, visitor); + + debug!("(resolving function) recorded argument `%s`", + self.session.str_of(name)); + } + + self.resolve_type(declaration.output, visitor); + } + } + + // Resolve the function body. + self.resolve_block(block, visitor); + + debug!("(resolving function) leaving function"); + } + + (*self.label_ribs).pop(); + (*self.value_ribs).pop(); + } + + fn resolve_type_parameters(type_parameters: ~[ty_param], + visitor: ResolveVisitor) { + + for type_parameters.each |type_parameter| { + for (*type_parameter.bounds).each |bound| { + match bound { + bound_copy | bound_send | bound_const | bound_owned => { + // Nothing to do. + } + bound_trait(trait_type) => { + self.resolve_type(trait_type, visitor); + } + } + } + } + } + + fn resolve_class(id: node_id, + type_parameters: @~[ty_param], + traits: ~[@trait_ref], + fields: ~[@struct_field], + methods: ~[@method], + optional_constructor: Option, + optional_destructor: Option, + visitor: ResolveVisitor) { + + // If applicable, create a rib for the type parameters. + let outer_type_parameter_count = (*type_parameters).len(); + let borrowed_type_parameters: &~[ty_param] = &*type_parameters; + do self.with_type_parameter_rib(HasTypeParameters + (borrowed_type_parameters, id, 0u, + NormalRibKind)) { + + // Resolve the type parameters. + self.resolve_type_parameters(*type_parameters, visitor); + + // Resolve implemented traits. + for traits.each |trt| { + match self.resolve_path(trt.path, TypeNS, true, visitor) { + None => { + self.session.span_err(trt.path.span, + ~"attempt to implement a \ + nonexistent trait"); + } + Some(def) => { + // Write a mapping from the trait ID to the + // definition of the trait into the definition + // map. + + debug!("(resolving class) found trait def: %?", def); + + self.record_def(trt.ref_id, def); + + // XXX: This is wrong but is needed for tests to + // pass. + + self.record_def(id, def); + } + } + } + + // Resolve methods. + for methods.each |method| { + self.resolve_method(MethodRibKind(id, Provided(method.id)), + method, + outer_type_parameter_count, + visitor); + } + + // Resolve fields. + for fields.each |field| { + self.resolve_type(field.node.ty, visitor); + } + + // Resolve the constructor, if applicable. + match optional_constructor { + None => { + // Nothing to do. + } + Some(constructor) => { + self.resolve_function(NormalRibKind, + Some(@constructor.node.dec), + NoTypeParameters, + constructor.node.body, + HasSelfBinding(constructor.node. + self_id), + NoCaptureClause, + visitor); + } + } + + // Resolve the destructor, if applicable. + match optional_destructor { + None => { + // Nothing to do. + } + Some(destructor) => { + self.resolve_function(NormalRibKind, + None, + NoTypeParameters, + destructor.node.body, + HasSelfBinding + (destructor.node.self_id), + NoCaptureClause, + visitor); + } + } + } + } + + // Does this really need to take a RibKind or is it always going + // to be NormalRibKind? + fn resolve_method(rib_kind: RibKind, + method: @method, + outer_type_parameter_count: uint, + visitor: ResolveVisitor) { + let borrowed_method_type_parameters = &method.tps; + let type_parameters = + HasTypeParameters(borrowed_method_type_parameters, + method.id, + outer_type_parameter_count, + rib_kind); + // we only have self ty if it is a non static method + let self_binding = match method.self_ty.node { + sty_static => { NoSelfBinding } + _ => { HasSelfBinding(method.self_id) } + }; + + self.resolve_function(rib_kind, + Some(@method.decl), + type_parameters, + method.body, + self_binding, + NoCaptureClause, + visitor); + } + + fn resolve_implementation(id: node_id, + span: span, + type_parameters: ~[ty_param], + trait_references: ~[@trait_ref], + self_type: @ty, + methods: ~[@method], + visitor: ResolveVisitor) { + + // If applicable, create a rib for the type parameters. + let outer_type_parameter_count = type_parameters.len(); + let borrowed_type_parameters: &~[ty_param] = &type_parameters; + do self.with_type_parameter_rib(HasTypeParameters + (borrowed_type_parameters, id, 0u, + NormalRibKind)) { + + // Resolve the type parameters. + self.resolve_type_parameters(type_parameters, visitor); + + // Resolve the trait reference, if necessary. + let original_trait_refs = self.current_trait_refs; + if trait_references.len() >= 1 { + let mut new_trait_refs = @DVec(); + for trait_references.each |trait_reference| { + match self.resolve_path( + trait_reference.path, TypeNS, true, visitor) { + None => { + self.session.span_err(span, + ~"attempt to implement an \ + unknown trait"); + } + Some(def) => { + self.record_def(trait_reference.ref_id, def); + + // Record the current trait reference. + (*new_trait_refs).push(def_id_of_def(def)); + } + } + } + + // Record the current set of trait references. + self.current_trait_refs = Some(new_trait_refs); + } + + // Resolve the self type. + self.resolve_type(self_type, visitor); + + for methods.each |method| { + // We also need a new scope for the method-specific + // type parameters. + self.resolve_method(MethodRibKind(id, Provided(method.id)), + method, + outer_type_parameter_count, + visitor); +/* + let borrowed_type_parameters = &method.tps; + self.resolve_function(MethodRibKind(id, Provided(method.id)), + Some(@method.decl), + HasTypeParameters + (borrowed_type_parameters, + method.id, + outer_type_parameter_count, + NormalRibKind), + method.body, + HasSelfBinding(method.self_id), + NoCaptureClause, + visitor); +*/ + } + + // Restore the original trait references. + self.current_trait_refs = original_trait_refs; + } + } + + fn resolve_module(module_: _mod, span: span, _name: ident, id: node_id, + visitor: ResolveVisitor) { + + // Write the implementations in scope into the module metadata. + debug!("(resolving module) resolving module ID %d", id); + visit_mod(module_, span, id, (), visitor); + } + + fn resolve_local(local: @local, visitor: ResolveVisitor) { + let mut mutability; + if local.node.is_mutbl { + mutability = Mutable; + } else { + mutability = Immutable; + } + + // Resolve the type. + self.resolve_type(local.node.ty, visitor); + + // Resolve the initializer, if necessary. + match local.node.init { + None => { + // Nothing to do. + } + Some(initializer) => { + self.resolve_expr(initializer.expr, visitor); + } + } + + // Resolve the pattern. + self.resolve_pattern(local.node.pat, IrrefutableMode, mutability, + None, visitor); + } + + fn binding_mode_map(pat: @pat) -> BindingMap { + let result = uint_hash(); + do pat_bindings(self.def_map, pat) |binding_mode, _id, sp, path| { + let ident = path_to_ident(path); + result.insert(ident, + binding_info {span: sp, + binding_mode: binding_mode}); + } + return result; + } + + fn check_consistent_bindings(arm: arm) { + if arm.pats.len() == 0 { return; } + let map_0 = self.binding_mode_map(arm.pats[0]); + for arm.pats.eachi() |i, p: @pat| { + let map_i = self.binding_mode_map(p); + + for map_0.each |key, binding_0| { + match map_i.find(key) { + None => { + self.session.span_err( + p.span, + fmt!("variable `%s` from pattern #1 is \ + not bound in pattern #%u", + self.session.str_of(key), i + 1)); + } + Some(binding_i) => { + if binding_0.binding_mode != binding_i.binding_mode { + self.session.span_err( + binding_i.span, + fmt!("variable `%s` is bound with different \ + mode in pattern #%u than in pattern #1", + self.session.str_of(key), i + 1)); + } + } + } + } + + for map_i.each |key, binding| { + if !map_0.contains_key(key) { + self.session.span_err( + binding.span, + fmt!("variable `%s` from pattern #%u is \ + not bound in pattern #1", + self.session.str_of(key), i + 1)); + } + } + } + } + + fn resolve_arm(arm: arm, visitor: ResolveVisitor) { + (*self.value_ribs).push(@Rib(NormalRibKind)); + + let bindings_list = atom_hashmap(); + for arm.pats.each |pattern| { + self.resolve_pattern(pattern, RefutableMode, Immutable, + Some(bindings_list), visitor); + } + + // This has to happen *after* we determine which + // pat_idents are variants + self.check_consistent_bindings(arm); + + visit_expr_opt(arm.guard, (), visitor); + self.resolve_block(arm.body, visitor); + + (*self.value_ribs).pop(); + } + + fn resolve_block(block: blk, visitor: ResolveVisitor) { + debug!("(resolving block) entering block"); + (*self.value_ribs).push(@Rib(NormalRibKind)); + + // Move down in the graph, if there's an anonymous module rooted here. + let orig_module = self.current_module; + match self.current_module.anonymous_children.find(block.node.id) { + None => { /* Nothing to do. */ } + Some(anonymous_module) => { + debug!("(resolving block) found anonymous module, moving \ + down"); + self.current_module = anonymous_module; + } + } + + // Descend into the block. + visit_block(block, (), visitor); + + // Move back up. + self.current_module = orig_module; + + (*self.value_ribs).pop(); + debug!("(resolving block) leaving block"); + } + + fn resolve_type(ty: @ty, visitor: ResolveVisitor) { + match ty.node { + // Like path expressions, the interpretation of path types depends + // on whether the path has multiple elements in it or not. + + ty_path(path, path_id) => { + // This is a path in the type namespace. Walk through scopes + // scopes looking for it. + + let mut result_def; + match self.resolve_path(path, TypeNS, true, visitor) { + Some(def) => { + debug!("(resolving type) resolved `%s` to type", + self.session.str_of(path.idents.last())); + result_def = Some(def); + } + None => { + result_def = None; + } + } + + match result_def { + Some(_) => { + // Continue. + } + None => { + // Check to see whether the name is a primitive type. + if path.idents.len() == 1u { + let name = path.idents.last(); + + match self.primitive_type_table + .primitive_types + .find(name) { + + Some(primitive_type) => { + result_def = + Some(def_prim_ty(primitive_type)); + } + None => { + // Continue. + } + } + } + } + } + + match copy result_def { + Some(def) => { + // Write the result into the def map. + debug!("(resolving type) writing resolution for `%s` \ + (id %d)", + connect(path.idents.map( + |x| self.session.str_of(x)), ~"::"), + path_id); + self.record_def(path_id, def); + } + None => { + self.session.span_err + (ty.span, fmt!("use of undeclared type name `%s`", + connect(path.idents.map( + |x| self.session.str_of(x)), + ~"::"))); + } + } + } + + _ => { + // Just resolve embedded types. + visit_ty(ty, (), visitor); + } + } + } + + fn resolve_pattern(pattern: @pat, + mode: PatternBindingMode, + mutability: Mutability, + // Maps idents to the node ID for the (outermost) + // pattern that binds them + bindings_list: Option>, + visitor: ResolveVisitor) { + + let pat_id = pattern.id; + do walk_pat(pattern) |pattern| { + match pattern.node { + pat_ident(binding_mode, path, _) + if !path.global && path.idents.len() == 1u => { + + // The meaning of pat_ident with no type parameters + // depends on whether an enum variant with that name is in + // scope. The probing lookup has to be careful not to emit + // spurious errors. Only matching patterns (match) can + // match nullary variants. For binding patterns (let), + // matching such a variant is simply disallowed (since + // it's rarely what you want). + + let atom = path.idents[0]; + + match self.resolve_enum_variant_or_const(atom) { + FoundEnumVariant(def) if mode == RefutableMode => { + debug!("(resolving pattern) resolving `%s` to \ + enum variant", + self.session.str_of(atom)); + + self.record_def(pattern.id, def); + } + FoundEnumVariant(_) => { + self.session.span_err(pattern.span, + fmt!("declaration of `%s` \ + shadows an enum \ + that's in scope", + self.session + .str_of(atom))); + } + FoundConst => { + self.session.span_err(pattern.span, + ~"pattern variable \ + conflicts with a constant \ + in scope"); + } + EnumVariantOrConstNotFound => { + debug!("(resolving pattern) binding `%s`", + self.session.str_of(atom)); + + let is_mutable = mutability == Mutable; + + let def = match mode { + RefutableMode => { + // For pattern arms, we must use + // `def_binding` definitions. + + def_binding(pattern.id, binding_mode) + } + IrrefutableMode => { + // But for locals, we use `def_local`. + def_local(pattern.id, is_mutable) + } + }; + + // Record the definition so that later passes + // will be able to distinguish variants from + // locals in patterns. + + self.record_def(pattern.id, def); + + // Add the binding to the local ribs, if it + // doesn't already exist in the bindings list. (We + // must not add it if it's in the bindings list + // because that breaks the assumptions later + // passes make about or-patterns.) + + match bindings_list { + Some(bindings_list) + if !bindings_list.contains_key(atom) => { + let last_rib = (*self.value_ribs).last(); + last_rib.bindings.insert(atom, + dl_def(def)); + bindings_list.insert(atom, pat_id); + } + Some(b) => { + if b.find(atom) == Some(pat_id) { + // Then this is a duplicate variable + // in the same disjunct, which is an + // error + self.session.span_err(pattern.span, + fmt!("Identifier %s is bound more \ + than once in the same pattern", + path_to_str(path, self.session + .intr()))); + } + // Not bound in the same pattern: do nothing + } + None => { + let last_rib = (*self.value_ribs).last(); + last_rib.bindings.insert(atom, + dl_def(def)); + } + } + } + } + + // Check the types in the path pattern. + for path.types.each |ty| { + self.resolve_type(ty, visitor); + } + } + + pat_ident(_, path, _) | pat_enum(path, _) => { + // These two must be enum variants. + match self.resolve_path(path, ValueNS, false, visitor) { + Some(def @ def_variant(*)) => { + self.record_def(pattern.id, def); + } + Some(_) => { + self.session.span_err( + path.span, + fmt!("not an enum variant: %s", + self.session.str_of( + path.idents.last()))); + } + None => { + self.session.span_err(path.span, + ~"unresolved enum variant"); + } + } + + // Check the types in the path pattern. + for path.types.each |ty| { + self.resolve_type(ty, visitor); + } + } + + pat_lit(expr) => { + self.resolve_expr(expr, visitor); + } + + pat_range(first_expr, last_expr) => { + self.resolve_expr(first_expr, visitor); + self.resolve_expr(last_expr, visitor); + } + + pat_struct(path, _, _) => { + match self.resolve_path(path, TypeNS, false, visitor) { + Some(def_ty(class_id)) + if self.structs.contains_key(class_id) => { + let has_constructor = self.structs.get(class_id); + let class_def = def_class(class_id, + has_constructor); + self.record_def(pattern.id, class_def); + } + Some(definition @ def_variant(_, variant_id)) + if self.structs.contains_key(variant_id) => { + self.record_def(pattern.id, definition); + } + _ => { + self.session.span_err( + path.span, + fmt!("`%s` does not name a structure", + connect(path.idents.map( + |x| self.session.str_of(x)), + ~"::"))); + } + } + } + + _ => { + // Nothing to do. + } + } + } + } + + fn resolve_enum_variant_or_const(name: Atom) + -> EnumVariantOrConstResolution { + + match self.resolve_item_in_lexical_scope(self.current_module, + name, + ValueNS) { + + Success(target) => { + match target.bindings.value_def { + None => { + fail ~"resolved name in the value namespace to a set \ + of name bindings with no def?!"; + } + Some(def) => { + match def.def { + def @ def_variant(*) => { + return FoundEnumVariant(def); + } + def_const(*) => { + return FoundConst; + } + _ => { + return EnumVariantOrConstNotFound; + } + } + } + } + } + + Indeterminate => { + fail ~"unexpected indeterminate result"; + } + + Failed => { + return EnumVariantOrConstNotFound; + } + } + } + + /** + * If `check_ribs` is true, checks the local definitions first; i.e. + * doesn't skip straight to the containing module. + */ + fn resolve_path(path: @path, namespace: Namespace, check_ribs: bool, + visitor: ResolveVisitor) + -> Option { + + // First, resolve the types. + for path.types.each |ty| { + self.resolve_type(ty, visitor); + } + + if path.global { + return self.resolve_crate_relative_path(path, + self.xray_context, + namespace); + } + + if path.idents.len() > 1u { + return self.resolve_module_relative_path(path, + self.xray_context, + namespace); + } + + return self.resolve_identifier(path.idents.last(), + namespace, + check_ribs, + path.span); + } + + fn resolve_identifier(identifier: ident, + namespace: Namespace, + check_ribs: bool, + span: span) + -> Option { + + if check_ribs { + match self.resolve_identifier_in_local_ribs(identifier, + namespace, + span) { + Some(def) => { + return Some(def); + } + None => { + // Continue. + } + } + } + + return self.resolve_item_by_identifier_in_lexical_scope(identifier, + namespace); + } + + // XXX: Merge me with resolve_name_in_module? + fn resolve_definition_of_name_in_module(containing_module: @Module, + name: Atom, + namespace: Namespace, + xray: XrayFlag) + -> NameDefinition { + + if xray == NoXray && !self.name_is_exported(containing_module, name) { + debug!("(resolving definition of name in module) name `%s` is \ + unexported", + self.session.str_of(name)); + return NoNameDefinition; + } + + // First, search children. + match containing_module.children.find(name) { + Some(child_name_bindings) => { + match (*child_name_bindings).def_for_namespace(namespace) { + Some(def) if def.privacy == Public => { + // Found it. Stop the search here. + return ChildNameDefinition(def.def); + } + Some(_) | None => { + // Continue. + } + } + } + None => { + // Continue. + } + } + + // Next, search import resolutions. + match containing_module.import_resolutions.find(name) { + Some(import_resolution) => { + match (*import_resolution).target_for_namespace(namespace) { + Some(target) => { + match (*target.bindings) + .def_for_namespace(namespace) { + Some(def) if def.privacy == Public => { + // Found it. + import_resolution.used = true; + return ImportNameDefinition(def.def); + } + Some(_) | None => { + // This can happen with external impls, due to + // the imperfect way we read the metadata. + + return NoNameDefinition; + } + } + } + None => { + return NoNameDefinition; + } + } + } + None => { + return NoNameDefinition; + } + } + } + + fn intern_module_part_of_path(path: @path) -> @DVec { + let module_path_atoms = @DVec(); + for path.idents.eachi |index, ident| { + if index == path.idents.len() - 1u { + break; + } + + (*module_path_atoms).push(ident); + } + + return module_path_atoms; + } + + fn resolve_module_relative_path(path: @path, + +xray: XrayFlag, + namespace: Namespace) + -> Option { + + let module_path_atoms = self.intern_module_part_of_path(path); + + let mut containing_module; + match self.resolve_module_path_for_import(self.current_module, + module_path_atoms, + xray, + path.span) { + + Failed => { + self.session.span_err(path.span, + fmt!("use of undeclared module `%s`", + self.atoms_to_str( + (*module_path_atoms).get()))); + return None; + } + + Indeterminate => { + fail ~"indeterminate unexpected"; + } + + Success(resulting_module) => { + containing_module = resulting_module; + } + } + + let name = path.idents.last(); + match self.resolve_definition_of_name_in_module(containing_module, + name, + namespace, + xray) { + NoNameDefinition => { + // We failed to resolve the name. Report an error. + self.session.span_err( + path.span, + fmt!("unresolved name: %s::%s", + self.atoms_to_str((*module_path_atoms).get()), + self.session.str_of(name))); + return None; + } + ChildNameDefinition(def) | ImportNameDefinition(def) => { + return Some(def); + } + } + } + + fn resolve_crate_relative_path(path: @path, + +xray: XrayFlag, + namespace: Namespace) + -> Option { + + let module_path_atoms = self.intern_module_part_of_path(path); + + let root_module = (*self.graph_root).get_module(); + + let mut containing_module; + match self.resolve_module_path_from_root(root_module, + module_path_atoms, + 0u, + xray, + path.span) { + + Failed => { + self.session.span_err(path.span, + fmt!("use of undeclared module `::%s`", + self.atoms_to_str + ((*module_path_atoms).get()))); + return None; + } + + Indeterminate => { + fail ~"indeterminate unexpected"; + } + + Success(resulting_module) => { + containing_module = resulting_module; + } + } + + let name = path.idents.last(); + match self.resolve_definition_of_name_in_module(containing_module, + name, + namespace, + xray) { + NoNameDefinition => { + // We failed to resolve the name. Report an error. + self.session.span_err( + path.span, + fmt!("unresolved name: %s::%s", self.atoms_to_str( + (*module_path_atoms).get()), + self.session.str_of(name))); + return None; + } + ChildNameDefinition(def) | ImportNameDefinition(def) => { + return Some(def); + } + } + } + + fn resolve_identifier_in_local_ribs(ident: ident, + namespace: Namespace, + span: span) + -> Option { + // Check the local set of ribs. + let mut search_result; + match namespace { + ValueNS => { + search_result = self.search_ribs(self.value_ribs, ident, span, + DontAllowCapturingSelf); + } + TypeNS => { + search_result = self.search_ribs(self.type_ribs, ident, span, + AllowCapturingSelf); + } + ModuleNS => { + fail ~"module namespaces do not have local ribs"; + } + } + + match copy search_result { + Some(dl_def(def)) => { + debug!("(resolving path in local ribs) resolved `%s` to \ + local: %?", + self.session.str_of(ident), + def); + return Some(def); + } + Some(dl_field) | Some(dl_impl(_)) | None => { + return None; + } + } + } + + fn resolve_item_by_identifier_in_lexical_scope(ident: ident, + namespace: Namespace) + -> Option { + + // Check the items. + match self.resolve_item_in_lexical_scope(self.current_module, + ident, + namespace) { + + Success(target) => { + match (*target.bindings).def_for_namespace(namespace) { + None => { + fail ~"resolved name in a namespace to a set of name \ + bindings with no def for that namespace?!"; + } + Some(def) => { + debug!("(resolving item path in lexical scope) \ + resolved `%s` to item", + self.session.str_of(ident)); + return Some(def.def); + } + } + } + Indeterminate => { + fail ~"unexpected indeterminate result"; + } + Failed => { + return None; + } + } + } + + fn name_exists_in_scope_class(name: &str) -> bool { + let mut i = self.type_ribs.len(); + while i != 0 { + i -= 1; + let rib = self.type_ribs.get_elt(i); + match rib.kind { + MethodRibKind(node_id, _) => + for vec::each(self.crate.node.module.items) |item| { + if item.id == node_id { + match item.node { + item_class(class_def, _) => { + for vec::each(class_def.fields) |field| { + match field.node.kind { + syntax::ast::unnamed_field + => {}, + syntax::ast::named_field(ident, _, _) + => { + if str::eq_slice(self.session.str_of(ident), + name) { + return true + } + } + } + } + for vec::each(class_def.methods) |method| { + if str::eq_slice(self.session.str_of(method.ident), + name) { + return true + } + } + } + _ => {} + } + } + }, + _ => {} + } + } + return false; + } + + fn resolve_expr(expr: @expr, visitor: ResolveVisitor) { + // First, record candidate traits for this expression if it could + // result in the invocation of a method call. + + self.record_candidate_traits_for_expr_if_necessary(expr); + + // Next, resolve the node. + match expr.node { + // The interpretation of paths depends on whether the path has + // multiple elements in it or not. + + expr_path(path) => { + // This is a local path in the value namespace. Walk through + // scopes looking for it. + + match self.resolve_path(path, ValueNS, true, visitor) { + Some(def) => { + // Write the result into the def map. + debug!("(resolving expr) resolved `%s`", + connect(path.idents.map( + |x| self.session.str_of(x)), ~"::")); + self.record_def(expr.id, def); + } + None => { + let wrong_name = + connect(path.idents.map( + |x| self.session.str_of(x)), ~"::") ; + if self.name_exists_in_scope_class(wrong_name) { + self.session.span_err(expr.span, + fmt!("unresolved name: `%s`. \ + Did you mean: `self.%s`?", + wrong_name, + wrong_name)); + } + else { + self.session.span_err(expr.span, + fmt!("unresolved name: %s", + wrong_name)); + } + } + } + + visit_expr(expr, (), visitor); + } + + expr_fn(_, fn_decl, block, capture_clause) | + expr_fn_block(fn_decl, block, capture_clause) => { + self.resolve_function(FunctionRibKind(expr.id, block.node.id), + Some(@fn_decl), + NoTypeParameters, + block, + NoSelfBinding, + HasCaptureClause(capture_clause), + visitor); + } + + expr_struct(path, _, _) => { + // Resolve the path to the structure it goes to. + // + // XXX: We might want to support explicit type parameters in + // the path, in which case this gets a little more + // complicated: + // + // 1. Should we go through the ast_path_to_ty() path, which + // handles typedefs and the like? + // + // 2. If so, should programmers be able to write this? + // + // class Foo { ... } + // type Bar = Foo; + // let bar = Bar { ... } // no type parameters + + match self.resolve_path(path, TypeNS, false, visitor) { + Some(def_ty(class_id)) | Some(def_class(class_id, _)) + if self.structs.contains_key(class_id) => { + let has_constructor = self.structs.get(class_id); + let class_def = def_class(class_id, has_constructor); + self.record_def(expr.id, class_def); + } + Some(definition @ def_variant(_, class_id)) + if self.structs.contains_key(class_id) => { + self.record_def(expr.id, definition); + } + _ => { + self.session.span_err( + path.span, + fmt!("`%s` does not name a structure", + connect(path.idents.map( + |x| self.session.str_of(x)), + ~"::"))); + } + } + + visit_expr(expr, (), visitor); + } + + expr_loop(_, Some(label)) => { + do self.with_label_rib { + let def_like = dl_def(def_label(expr.id)); + self.label_ribs.last().bindings.insert(label, def_like); + + visit_expr(expr, (), visitor); + } + } + + expr_break(Some(label)) | expr_again(Some(label)) => { + match self.search_ribs(self.label_ribs, label, expr.span, + DontAllowCapturingSelf) { + None => + self.session.span_err(expr.span, + fmt!("use of undeclared label \ + `%s`", self.session.str_of( + label))), + Some(dl_def(def @ def_label(_))) => + self.record_def(expr.id, def), + Some(_) => + self.session.span_bug(expr.span, + ~"label wasn't mapped to a \ + label def!") + } + } + + _ => { + visit_expr(expr, (), visitor); + } + } + } + + fn record_candidate_traits_for_expr_if_necessary(expr: @expr) { + match expr.node { + expr_field(_, ident, _) => { + let traits = self.search_for_traits_containing_method(ident); + self.trait_map.insert(expr.id, traits); + } + expr_binary(add, _, _) | expr_assign_op(add, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.add_trait); + } + expr_binary(subtract, _, _) | expr_assign_op(subtract, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.sub_trait); + } + expr_binary(mul, _, _) | expr_assign_op(mul, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.mul_trait); + } + expr_binary(div, _, _) | expr_assign_op(div, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.div_trait); + } + expr_binary(rem, _, _) | expr_assign_op(rem, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.modulo_trait); + } + expr_binary(bitxor, _, _) | expr_assign_op(bitxor, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.bitxor_trait); + } + expr_binary(bitand, _, _) | expr_assign_op(bitand, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.bitand_trait); + } + expr_binary(bitor, _, _) | expr_assign_op(bitor, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.bitor_trait); + } + expr_binary(shl, _, _) | expr_assign_op(shl, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.shl_trait); + } + expr_binary(shr, _, _) | expr_assign_op(shr, _, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.shr_trait); + } + expr_unary(neg, _) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.neg_trait); + } + expr_index(*) => { + self.add_fixed_trait_for_expr(expr.id, + self.lang_items.index_trait); + } + _ => { + // Nothing to do. + } + } + } + + fn search_for_traits_containing_method(name: Atom) -> @DVec { + let found_traits = @DVec(); + let mut search_module = self.current_module; + loop { + // Look for the current trait. + match copy self.current_trait_refs { + Some(trait_def_ids) => { + for trait_def_ids.each |trait_def_id| { + self.add_trait_info_if_containing_method + (found_traits, trait_def_id, name); + } + } + None => { + // Nothing to do. + } + } + + // Look for trait children. + for search_module.children.each |_name, child_name_bindings| { + match child_name_bindings.def_for_namespace(TypeNS) { + Some(def) => { + match def.def { + def_ty(trait_def_id) => { + self.add_trait_info_if_containing_method + (found_traits, trait_def_id, name); + } + _ => { + // Continue. + } + } + } + None => { + // Continue. + } + } + } + + // Look for imports. + for search_module.import_resolutions.each + |_atom, import_resolution| { + + match import_resolution.target_for_namespace(TypeNS) { + None => { + // Continue. + } + Some(target) => { + match target.bindings.def_for_namespace(TypeNS) { + Some(def) => { + match def.def { + def_ty(trait_def_id) => { + self. + add_trait_info_if_containing_method + (found_traits, trait_def_id, name); + } + _ => { + // Continue. + } + } + } + None => { + // Continue. + } + } + } + } + } + + // Move to the next parent. + match search_module.parent_link { + NoParentLink => { + // Done. + break; + } + ModuleParentLink(parent_module, _) | + BlockParentLink(parent_module, _) => { + search_module = parent_module; + } + } + } + + return found_traits; + } + + fn add_trait_info_if_containing_method(found_traits: @DVec, + trait_def_id: def_id, + name: Atom) { + + match self.trait_info.find(trait_def_id) { + Some(trait_info) if trait_info.contains_key(name) => { + debug!("(adding trait info if containing method) found trait \ + %d:%d for method '%s'", + trait_def_id.crate, + trait_def_id.node, + self.session.str_of(name)); + (*found_traits).push(trait_def_id); + } + Some(_) | None => { + // Continue. + } + } + } + + fn add_fixed_trait_for_expr(expr_id: node_id, +trait_id: Option) { + let traits = @DVec(); + traits.push(trait_id.get()); + self.trait_map.insert(expr_id, traits); + } + + fn record_def(node_id: node_id, def: def) { + debug!("(recording def) recording %? for %?", def, node_id); + self.def_map.insert(node_id, def); + } + + // + // Unused import checking + // + // Although this is a lint pass, it lives in here because it depends on + // resolve data structures. + // + + fn check_for_unused_imports_if_necessary() { + if self.unused_import_lint_level == allow { + return; + } + + let root_module = (*self.graph_root).get_module(); + self.check_for_unused_imports_in_module_subtree(root_module); + } + + fn check_for_unused_imports_in_module_subtree(module_: @Module) { + // If this isn't a local crate, then bail out. We don't need to check + // for unused imports in external crates. + + match module_.def_id { + Some(def_id) if def_id.crate == local_crate => { + // OK. Continue. + } + None => { + // Check for unused imports in the root module. + } + Some(_) => { + // Bail out. + debug!("(checking for unused imports in module subtree) not \ + checking for unused imports for `%s`", + self.module_to_str(module_)); + return; + } + } + + self.check_for_unused_imports_in_module(module_); + + for module_.children.each |_atom, child_name_bindings| { + match (*child_name_bindings).get_module_if_available() { + None => { + // Nothing to do. + } + Some(child_module) => { + self.check_for_unused_imports_in_module_subtree + (child_module); + } + } + } + + for module_.anonymous_children.each |_node_id, child_module| { + self.check_for_unused_imports_in_module_subtree(child_module); + } + } + + fn check_for_unused_imports_in_module(module_: @Module) { + for module_.import_resolutions.each |_name, import_resolution| { + if !import_resolution.used { + match self.unused_import_lint_level { + warn => { + self.session.span_warn(import_resolution.span, + ~"unused import"); + } + deny | forbid => { + self.session.span_err(import_resolution.span, + ~"unused import"); + } + allow => { + self.session.span_bug(import_resolution.span, + ~"shouldn't be here if lint \ + is allowed"); + } + } + } + } + } + + + // + // Diagnostics + // + // Diagnostics are not particularly efficient, because they're rarely + // hit. + // + + /// A somewhat inefficient routine to print out the name of a module. + fn module_to_str(module_: @Module) -> ~str { + let atoms = DVec(); + let mut current_module = module_; + loop { + match current_module.parent_link { + NoParentLink => { + break; + } + ModuleParentLink(module_, name) => { + atoms.push(name); + current_module = module_; + } + BlockParentLink(module_, _) => { + atoms.push(syntax::parse::token::special_idents::opaque); + current_module = module_; + } + } + } + + if atoms.len() == 0u { + return ~"???"; + } + + let mut string = ~""; + let mut i = atoms.len() - 1u; + loop { + if i < atoms.len() - 1u { + string += ~"::"; + } + string += self.session.str_of(atoms.get_elt(i)); + + if i == 0u { + break; + } + i -= 1u; + } + + return string; + } + + fn dump_module(module_: @Module) { + debug!("Dump of module `%s`:", self.module_to_str(module_)); + + debug!("Children:"); + for module_.children.each |name, _child| { + debug!("* %s", self.session.str_of(name)); + } + + debug!("Import resolutions:"); + for module_.import_resolutions.each |name, import_resolution| { + let mut module_repr; + match (*import_resolution).target_for_namespace(ModuleNS) { + None => { module_repr = ~""; } + Some(_) => { + module_repr = ~" module:?"; + // XXX + } + } + + let mut value_repr; + match (*import_resolution).target_for_namespace(ValueNS) { + None => { value_repr = ~""; } + Some(_) => { + value_repr = ~" value:?"; + // XXX + } + } + + let mut type_repr; + match (*import_resolution).target_for_namespace(TypeNS) { + None => { type_repr = ~""; } + Some(_) => { + type_repr = ~" type:?"; + // XXX + } + } + + debug!("* %s:%s%s%s", + self.session.str_of(name), + module_repr, value_repr, type_repr); + } + } +} + +/// Entry point to crate resolution. +fn resolve_crate(session: session, lang_items: LanguageItems, crate: @crate) + -> { def_map: DefMap, + exp_map: ExportMap, + exp_map2: ExportMap2, + trait_map: TraitMap } { + + let resolver = @Resolver(session, lang_items, crate); + resolver.resolve(resolver); + return { + def_map: resolver.def_map, + exp_map: resolver.export_map, + exp_map2: resolver.export_map2, + trait_map: resolver.trait_map + }; +} + diff --git a/src/rustc/middle/resolve3.rs b/src/rustc/middle/resolve3.rs deleted file mode 100644 index 33260e1fe6f..00000000000 --- a/src/rustc/middle/resolve3.rs +++ /dev/null @@ -1,4611 +0,0 @@ -import driver::session::session; -import metadata::csearch::{each_path, get_method_names_if_trait}; -import metadata::cstore::find_use_stmt_cnum; -import metadata::decoder::{def_like, dl_def, dl_field, dl_impl}; -import middle::lang_items::LanguageItems; -import middle::lint::{deny, allow, forbid, level, unused_imports, warn}; -import middle::pat_util::{pat_bindings}; -import syntax::ast::{_mod, add, arm}; -import syntax::ast::{bind_by_ref, bind_by_implicit_ref, bind_by_value}; -import syntax::ast::{bitand, bitor, bitxor}; -import syntax::ast::{blk, bound_const, bound_copy, bound_owned, bound_send}; -import syntax::ast::{bound_trait, binding_mode, - capture_clause, class_ctor, class_dtor}; -import syntax::ast::{crate, crate_num, decl_item}; -import syntax::ast::{def, def_arg, def_binding, def_class, def_const, def_fn}; -import syntax::ast::{def_foreign_mod, def_id, def_label, def_local, def_mod}; -import syntax::ast::{def_prim_ty, def_region, def_self, def_ty, def_ty_param}; -import syntax::ast::{def_typaram_binder, def_static_method}; -import syntax::ast::{def_upvar, def_use, def_variant, expr, expr_assign_op}; -import syntax::ast::{expr_binary, expr_cast, expr_field, expr_fn}; -import syntax::ast::{expr_fn_block, expr_index, expr_path}; -import syntax::ast::{def_prim_ty, def_region, def_self, def_ty, def_ty_param}; -import syntax::ast::{def_upvar, def_use, def_variant, div, eq}; -import syntax::ast::{enum_variant_kind, expr, expr_again, expr_assign_op}; -import syntax::ast::{expr_binary, expr_break, expr_cast, expr_field, expr_fn}; -import syntax::ast::{expr_fn_block, expr_index, expr_loop}; -import syntax::ast::{expr_path, expr_struct, expr_unary, fn_decl}; -import syntax::ast::{foreign_item, foreign_item_const, foreign_item_fn, ge}; -import syntax::ast::{gt, ident, impure_fn, inherited, item, item_class}; -import syntax::ast::{item_const, item_enum, item_fn, item_foreign_mod}; -import syntax::ast::{item_impl, item_mac, item_mod, item_trait, item_ty, le}; -import syntax::ast::{local, local_crate, lt, method, mul, ne, neg, node_id}; -import syntax::ast::{pat, pat_enum, pat_ident, path, prim_ty, pat_box}; -import syntax::ast::{pat_lit, pat_range, pat_rec, pat_struct, pat_tup}; -import syntax::ast::{pat_uniq, pat_wild, private, provided, public, required}; -import syntax::ast::{rem, self_ty_, shl, shr, stmt_decl, struct_field}; -import syntax::ast::{struct_variant_kind, sty_static, subtract, trait_ref}; -import syntax::ast::{tuple_variant_kind, ty, ty_bool, ty_char, ty_f, ty_f32}; -import syntax::ast::{ty_f64, ty_float, ty_i, ty_i16, ty_i32, ty_i64, ty_i8}; -import syntax::ast::{ty_int, ty_param, ty_path, ty_str, ty_u, ty_u16, ty_u32}; -import syntax::ast::{ty_u64, ty_u8, ty_uint, variant, view_item}; -import syntax::ast::{view_item_export, view_item_import, view_item_use}; -import syntax::ast::{view_path_glob, view_path_list, view_path_simple}; -import syntax::ast::{visibility, anonymous, named}; -import syntax::ast_util::{def_id_of_def, dummy_sp, local_def, new_def_hash}; -import syntax::ast_util::{path_to_ident, walk_pat, trait_method_to_ty_method}; -import syntax::attr::{attr_metas, contains_name}; -import syntax::print::pprust::{pat_to_str, path_to_str}; -import syntax::codemap::span; -import syntax::visit::{default_visitor, fk_method, mk_vt, visit_block}; -import syntax::visit::{visit_crate, visit_expr, visit_expr_opt, visit_fn}; -import syntax::visit::{visit_foreign_item, visit_item, visit_method_helper}; -import syntax::visit::{visit_mod, visit_ty, vt}; - -import box::ptr_eq; -import dvec::DVec; -import option::{get, is_some}; -import str::{connect, split_str}; -import vec::pop; -import syntax::parse::token::ident_interner; - -import std::list::{cons, list, nil}; -import std::map::{hashmap, int_hash, uint_hash}; -import str_eq = str::eq; - -// Definition mapping -type DefMap = hashmap; - -struct binding_info { - span: span; - binding_mode: binding_mode; -} - -// Map from the name in a pattern to its binding mode. -type BindingMap = hashmap; - -// Implementation resolution -// -// XXX: This kind of duplicates information kept in ty::method. Maybe it -// should go away. - -type MethodInfo = { - did: def_id, - n_tps: uint, - ident: ident, - self_type: self_ty_ -}; - -type Impl = { did: def_id, ident: ident, methods: ~[@MethodInfo] }; - -// Trait method resolution -type TraitMap = @hashmap>; - -// Export mapping -type Export = { reexp: bool, id: def_id }; -type ExportMap = hashmap; - -// This is the replacement export map. It maps a module to all of the exports -// within. -type ExportMap2 = hashmap; - -struct Export2 { - name: ~str; // The name of the target. - def_id: def_id; // The definition of the target. - reexport: bool; // Whether this is a reexport. -} - -enum PatternBindingMode { - RefutableMode, - IrrefutableMode -} - -enum Namespace { - ModuleNS, - TypeNS, - ValueNS -} - -enum NamespaceResult { - UnknownResult, - UnboundResult, - BoundResult(@Module, @NameBindings) -} - -enum NameDefinition { - NoNameDefinition, //< The name was unbound. - ChildNameDefinition(def), //< The name identifies an immediate child. - ImportNameDefinition(def) //< The name identifies an import. - -} - -enum Mutability { - Mutable, - Immutable -} - -enum SelfBinding { - NoSelfBinding, - HasSelfBinding(node_id) -} - -enum CaptureClause { - NoCaptureClause, - HasCaptureClause(capture_clause) -} - -type ResolveVisitor = vt<()>; - -enum ModuleDef { - NoModuleDef, // Does not define a module. - ModuleDef(@Module), // Defines a module. -} - -/// Contains data for specific types of import directives. -enum ImportDirectiveSubclass { - SingleImport(Atom /* target */, Atom /* source */), - GlobImport -} - -/// The context that we thread through while building the reduced graph. -enum ReducedGraphParent { - ModuleReducedGraphParent(@Module) -} - -enum ResolveResult { - Failed, // Failed to resolve the name. - Indeterminate, // Couldn't determine due to unresolved globs. - Success(T) // Successfully resolved the import. -} - -enum TypeParameters/& { - NoTypeParameters, //< No type parameters. - HasTypeParameters(&~[ty_param], //< Type parameters. - node_id, //< ID of the enclosing item - - // The index to start numbering the type parameters at. - // This is zero if this is the outermost set of type - // parameters, or equal to the number of outer type - // parameters. For example, if we have: - // - // impl I { - // fn method() { ... } - // } - // - // The index at the method site will be 1, because the - // outer T had index 0. - - uint, - - // The kind of the rib used for type parameters. - RibKind) -} - -// The rib kind controls the translation of argument or local definitions -// (`def_arg` or `def_local`) to upvars (`def_upvar`). - -enum RibKind { - // No translation needs to be applied. - NormalRibKind, - - // We passed through a function scope at the given node ID. Translate - // upvars as appropriate. - FunctionRibKind(node_id /* func id */, node_id /* body id */), - - // We passed through a class, impl, or trait and are now in one of its - // methods. Allow references to ty params that that class, impl or trait - // binds. Disallow any other upvars (including other ty params that are - // upvars). - // parent; method itself - MethodRibKind(node_id, MethodSort), - - // We passed through a function *item* scope. Disallow upvars. - OpaqueFunctionRibKind -} - -// Methods can be required or provided. Required methods only occur in traits. -enum MethodSort { - Required, - Provided(node_id) -} - -// The X-ray flag indicates that a context has the X-ray privilege, which -// allows it to reference private names. Currently, this is used for the test -// runner. -// -// XXX: The X-ray flag is kind of questionable in the first place. It might -// be better to introduce an expr_xray_path instead. - -enum XrayFlag { - NoXray, //< Private items cannot be accessed. - Xray //< Private items can be accessed. -} - -enum AllowCapturingSelfFlag { - AllowCapturingSelf, //< The "self" definition can be captured. - DontAllowCapturingSelf, //< The "self" definition cannot be captured. -} - -enum EnumVariantOrConstResolution { - FoundEnumVariant(def), - FoundConst, - EnumVariantOrConstNotFound -} - -// FIXME (issue #2550): Should be a class but then it becomes not implicitly -// copyable due to a kind bug. - -type Atom = uint; - -fn Atom(n: uint) -> Atom { - return n; -} - -/// Creates a hash table of atoms. -fn atom_hashmap() -> hashmap { - hashmap::(uint::hash, uint::eq) -} - -/// One local scope. -struct Rib { - let bindings: hashmap; - let kind: RibKind; - - new(kind: RibKind) { - self.bindings = atom_hashmap(); - self.kind = kind; - } -} - -/// One import directive. -struct ImportDirective { - let module_path: @DVec; - let subclass: @ImportDirectiveSubclass; - let span: span; - - new(module_path: @DVec, - subclass: @ImportDirectiveSubclass, - span: span) { - - self.module_path = module_path; - self.subclass = subclass; - self.span = span; - } -} - -/// The item that an import resolves to. -struct Target { - let target_module: @Module; - let bindings: @NameBindings; - - new(target_module: @Module, bindings: @NameBindings) { - self.target_module = target_module; - self.bindings = bindings; - } -} - -struct ImportResolution { - let span: span; - - // The number of outstanding references to this name. When this reaches - // zero, outside modules can count on the targets being correct. Before - // then, all bets are off; future imports could override this name. - - let mut outstanding_references: uint; - - let mut module_target: Option; - let mut value_target: Option; - let mut type_target: Option; - - let mut used: bool; - - new(span: span) { - self.span = span; - - self.outstanding_references = 0u; - - self.module_target = None; - self.value_target = None; - self.type_target = None; - - self.used = false; - } - - fn target_for_namespace(namespace: Namespace) -> Option { - match namespace { - ModuleNS => return copy self.module_target, - TypeNS => return copy self.type_target, - ValueNS => return copy self.value_target - } - } -} - -/// The link from a module up to its nearest parent node. -enum ParentLink { - NoParentLink, - ModuleParentLink(@Module, Atom), - BlockParentLink(@Module, node_id) -} - -/// One node in the tree of modules. -struct Module { - let parent_link: ParentLink; - let mut def_id: Option; - - let children: hashmap; - let imports: DVec<@ImportDirective>; - - // The anonymous children of this node. Anonymous children are pseudo- - // modules that are implicitly created around items contained within - // blocks. - // - // For example, if we have this: - // - // fn f() { - // fn g() { - // ... - // } - // } - // - // There will be an anonymous module created around `g` with the ID of the - // entry block for `f`. - - let anonymous_children: hashmap; - - // XXX: This is about to be reworked so that exports are on individual - // items, not names. - // - // The atom is the name of the exported item, while the node ID is the - // ID of the export path. - - let exported_names: hashmap; - - // The status of resolving each import in this module. - let import_resolutions: hashmap; - - // The number of unresolved globs that this module exports. - let mut glob_count: uint; - - // The index of the import we're resolving. - let mut resolved_import_count: uint; - - new(parent_link: ParentLink, def_id: Option) { - self.parent_link = parent_link; - self.def_id = def_id; - - self.children = atom_hashmap(); - self.imports = DVec(); - - self.anonymous_children = int_hash(); - - self.exported_names = atom_hashmap(); - - self.import_resolutions = atom_hashmap(); - self.glob_count = 0u; - self.resolved_import_count = 0u; - } - - fn all_imports_resolved() -> bool { - return self.imports.len() == self.resolved_import_count; - } -} - -// XXX: This is a workaround due to is_none in the standard library mistakenly -// requiring a T:copy. - -pure fn is_none(x: Option) -> bool { - match x { - None => return true, - Some(_) => return false - } -} - -fn unused_import_lint_level(session: session) -> level { - for session.opts.lint_opts.each |lint_option_pair| { - let (lint_type, lint_level) = lint_option_pair; - if lint_type == unused_imports { - return lint_level; - } - } - return allow; -} - -enum Privacy { - Private, - Public -} - -// Records a possibly-private definition. -struct Definition { - privacy: Privacy; - def: def; -} - -// Records the definitions (at most one for each namespace) that a name is -// bound to. -struct NameBindings { - let mut module_def: ModuleDef; //< Meaning in module namespace. - let mut type_def: Option; //< Meaning in type namespace. - let mut value_def: Option; //< Meaning in value namespace. - - // For error reporting - // XXX: Merge me into Definition. - let mut module_span: Option; - let mut type_span: Option; - let mut value_span: Option; - - new() { - self.module_def = NoModuleDef; - self.type_def = None; - self.value_def = None; - self.module_span = None; - self.type_span = None; - self.value_span = None; - } - - /// Creates a new module in this set of name bindings. - fn define_module(parent_link: ParentLink, def_id: Option, - sp: span) { - if self.module_def == NoModuleDef { - let module_ = @Module(parent_link, def_id); - self.module_def = ModuleDef(module_); - self.module_span = Some(sp); - } - } - - /// Records a type definition. - fn define_type(privacy: Privacy, def: def, sp: span) { - self.type_def = Some(Definition { privacy: privacy, def: def }); - self.type_span = Some(sp); - } - - /// Records a value definition. - fn define_value(privacy: Privacy, def: def, sp: span) { - self.value_def = Some(Definition { privacy: privacy, def: def }); - self.value_span = Some(sp); - } - - /// Returns the module node if applicable. - fn get_module_if_available() -> Option<@Module> { - match self.module_def { - NoModuleDef => return None, - ModuleDef(module_) => return Some(module_) - } - } - - /** - * Returns the module node. Fails if this node does not have a module - * definition. - */ - fn get_module() -> @Module { - match self.module_def { - NoModuleDef => { - fail - ~"get_module called on a node with no module definition!"; - } - ModuleDef(module_) => { - return module_; - } - } - } - - fn defined_in_namespace(namespace: Namespace) -> bool { - match namespace { - ModuleNS => return self.module_def != NoModuleDef, - TypeNS => return self.type_def != None, - ValueNS => return self.value_def != None - } - } - - fn def_for_namespace(namespace: Namespace) -> Option { - match namespace { - TypeNS => return self.type_def, - ValueNS => return self.value_def, - ModuleNS => match self.module_def { - NoModuleDef => return None, - ModuleDef(module_) => - match module_.def_id { - None => return None, - Some(def_id) => { - return Some(Definition { - privacy: Public, - def: def_mod(def_id) - }); - } - } - } - } - } - - fn span_for_namespace(namespace: Namespace) -> Option { - match self.def_for_namespace(namespace) { - Some(_) => { - match namespace { - TypeNS => self.type_span, - ValueNS => self.value_span, - ModuleNS => self.module_span - } - } - None => None - } - } -} - -/// Interns the names of the primitive types. -struct PrimitiveTypeTable { - let primitive_types: hashmap; - - new(intr: ident_interner) { - self.primitive_types = atom_hashmap(); - - self.intern(intr, @~"bool", ty_bool); - self.intern(intr, @~"char", ty_int(ty_char)); - self.intern(intr, @~"float", ty_float(ty_f)); - self.intern(intr, @~"f32", ty_float(ty_f32)); - self.intern(intr, @~"f64", ty_float(ty_f64)); - self.intern(intr, @~"int", ty_int(ty_i)); - self.intern(intr, @~"i8", ty_int(ty_i8)); - self.intern(intr, @~"i16", ty_int(ty_i16)); - self.intern(intr, @~"i32", ty_int(ty_i32)); - self.intern(intr, @~"i64", ty_int(ty_i64)); - self.intern(intr, @~"str", ty_str); - self.intern(intr, @~"uint", ty_uint(ty_u)); - self.intern(intr, @~"u8", ty_uint(ty_u8)); - self.intern(intr, @~"u16", ty_uint(ty_u16)); - self.intern(intr, @~"u32", ty_uint(ty_u32)); - self.intern(intr, @~"u64", ty_uint(ty_u64)); - } - - fn intern(intr: ident_interner, string: @~str, - primitive_type: prim_ty) { - let atom = intr.intern(string); - self.primitive_types.insert(atom, primitive_type); - } -} - -fn namespace_to_str(ns: Namespace) -> ~str { - match ns { - TypeNS => ~"type", - ValueNS => ~"value", - ModuleNS => ~"module" - } -} - -/// The main resolver class. -struct Resolver { - let session: session; - let lang_items: LanguageItems; - let crate: @crate; - - let intr: ident_interner; - - let graph_root: @NameBindings; - - let unused_import_lint_level: level; - - let trait_info: hashmap>; - let structs: hashmap; - - // The number of imports that are currently unresolved. - let mut unresolved_imports: uint; - - // The module that represents the current item scope. - let mut current_module: @Module; - - // The current set of local scopes, for values. - // XXX: Reuse ribs to avoid allocation. - let value_ribs: @DVec<@Rib>; - - // The current set of local scopes, for types. - let type_ribs: @DVec<@Rib>; - - // The current set of local scopes, for labels. - let label_ribs: @DVec<@Rib>; - - // Whether the current context is an X-ray context. An X-ray context is - // allowed to access private names of any module. - let mut xray_context: XrayFlag; - - // The trait that the current context can refer to. - let mut current_trait_refs: Option<@DVec>; - - // The atom for the keyword "self". - let self_atom: Atom; - - // The atoms for the primitive types. - let primitive_type_table: @PrimitiveTypeTable; - - // The four namespaces. - let namespaces: ~[Namespace]; - - let def_map: DefMap; - let export_map: ExportMap; - let export_map2: ExportMap2; - let trait_map: TraitMap; - - new(session: session, lang_items: LanguageItems, crate: @crate) { - self.session = session; - self.lang_items = copy lang_items; - self.crate = crate; - - // The outermost module has def ID 0; this is not reflected in the - // AST. - - self.graph_root = @NameBindings(); - (*self.graph_root).define_module(NoParentLink, - Some({ crate: 0, node: 0 }), - crate.span); - - self.unused_import_lint_level = unused_import_lint_level(session); - - self.trait_info = new_def_hash(); - self.structs = new_def_hash(); - - self.unresolved_imports = 0u; - - self.current_module = (*self.graph_root).get_module(); - self.value_ribs = @DVec(); - self.type_ribs = @DVec(); - self.label_ribs = @DVec(); - - self.xray_context = NoXray; - self.current_trait_refs = None; - - self.self_atom = syntax::parse::token::special_idents::self_; - self.primitive_type_table = @PrimitiveTypeTable(self.session. - parse_sess.interner); - - self.namespaces = ~[ ModuleNS, TypeNS, ValueNS ]; - - self.def_map = int_hash(); - self.export_map = int_hash(); - self.export_map2 = int_hash(); - self.trait_map = @int_hash(); - - self.intr = session.intr(); - } - - /// The main name resolution procedure. - fn resolve(@self, this: @Resolver) { - self.build_reduced_graph(this); - self.session.abort_if_errors(); - - self.resolve_imports(); - self.session.abort_if_errors(); - - self.record_exports(); - self.session.abort_if_errors(); - - self.resolve_crate(); - self.session.abort_if_errors(); - - self.check_for_unused_imports_if_necessary(); - } - - // - // Reduced graph building - // - // Here we build the "reduced graph": the graph of the module tree without - // any imports resolved. - // - - /// Constructs the reduced graph for the entire crate. - fn build_reduced_graph(this: @Resolver) { - let initial_parent = - ModuleReducedGraphParent((*self.graph_root).get_module()); - visit_crate(*self.crate, initial_parent, mk_vt(@{ - visit_item: |item, context, visitor| - (*this).build_reduced_graph_for_item(item, context, visitor), - - visit_foreign_item: |foreign_item, context, visitor| - (*this).build_reduced_graph_for_foreign_item(foreign_item, - context, - visitor), - - visit_view_item: |view_item, context, visitor| - (*this).build_reduced_graph_for_view_item(view_item, - context, - visitor), - - visit_block: |block, context, visitor| - (*this).build_reduced_graph_for_block(block, - context, - visitor) - - with *default_visitor() - })); - } - - fn visibility_to_privacy(visibility: visibility) -> Privacy { - match visibility { - inherited | public => Public, - private => Private - } - } - - /// Returns the current module tracked by the reduced graph parent. - fn get_module_from_parent(reduced_graph_parent: ReducedGraphParent) - -> @Module { - match reduced_graph_parent { - ModuleReducedGraphParent(module_) => { - return module_; - } - } - } - - /** - * Adds a new child item to the module definition of the parent node and - * returns its corresponding name bindings as well as the current parent. - * Or, if we're inside a block, creates (or reuses) an anonymous module - * corresponding to the innermost block ID and returns the name bindings - * as well as the newly-created parent. - * - * If this node does not have a module definition and we are not inside - * a block, fails. - */ - fn add_child(name: Atom, - reduced_graph_parent: ReducedGraphParent, - // Pass in the namespaces for the child item so that we can - // check for duplicate items in the same namespace - ns: ~[Namespace], - // For printing errors - sp: span) - -> (@NameBindings, ReducedGraphParent) { - - // If this is the immediate descendant of a module, then we add the - // child name directly. Otherwise, we create or reuse an anonymous - // module and add the child to that. - - let mut module_; - match reduced_graph_parent { - ModuleReducedGraphParent(parent_module) => { - module_ = parent_module; - } - } - - // Add or reuse the child. - let new_parent = ModuleReducedGraphParent(module_); - match module_.children.find(name) { - None => { - let child = @NameBindings(); - module_.children.insert(name, child); - return (child, new_parent); - } - Some(child) => { - // We don't want to complain if the multiple definitions - // are in different namespaces. - match ns.find(|n| child.defined_in_namespace(n)) { - Some(ns) => { - self.session.span_err(sp, - #fmt("Duplicate definition of %s %s", - namespace_to_str(ns), - self.session.str_of(name))); - do child.span_for_namespace(ns).iter() |sp| { - self.session.span_note(sp, - #fmt("First definition of %s %s here:", - namespace_to_str(ns), - self.session.str_of(name))); - } - } - _ => {} - } - return (child, new_parent); - } - } - } - - fn block_needs_anonymous_module(block: blk) -> bool { - // If the block has view items, we need an anonymous module. - if block.node.view_items.len() > 0u { - return true; - } - - // Check each statement. - for block.node.stmts.each |statement| { - match statement.node { - stmt_decl(declaration, _) => { - match declaration.node { - decl_item(_) => { - return true; - } - _ => { - // Keep searching. - } - } - } - _ => { - // Keep searching. - } - } - } - - // If we found neither view items nor items, we don't need to create - // an anonymous module. - - return false; - } - - fn get_parent_link(parent: ReducedGraphParent, name: Atom) -> ParentLink { - match parent { - ModuleReducedGraphParent(module_) => { - return ModuleParentLink(module_, name); - } - } - } - - /// Constructs the reduced graph for one item. - fn build_reduced_graph_for_item(item: @item, - parent: ReducedGraphParent, - &&visitor: vt) { - - let atom = item.ident; - let sp = item.span; - - match item.node { - item_mod(module_) => { - let (name_bindings, new_parent) = self.add_child(atom, parent, - ~[ModuleNS], sp); - - let parent_link = self.get_parent_link(new_parent, atom); - let def_id = { crate: 0, node: item.id }; - (*name_bindings).define_module(parent_link, Some(def_id), - sp); - - let new_parent = - ModuleReducedGraphParent((*name_bindings).get_module()); - - visit_mod(module_, sp, item.id, new_parent, visitor); - } - item_foreign_mod(fm) => { - let new_parent = match fm.sort { - named => { - let (name_bindings, new_parent) = self.add_child(atom, - parent, ~[ModuleNS], sp); - - let parent_link = self.get_parent_link(new_parent, atom); - let def_id = { crate: 0, node: item.id }; - (*name_bindings).define_module(parent_link, Some(def_id), - sp); - - ModuleReducedGraphParent((*name_bindings).get_module()) - } - // For anon foreign mods, the contents just go in the - // current scope - anonymous => parent - }; - - visit_item(item, new_parent, visitor); - } - - // These items live in the value namespace. - item_const(*) => { - let (name_bindings, _) = self.add_child(atom, parent, - ~[ValueNS], sp); - - (*name_bindings).define_value - (self.visibility_to_privacy(item.vis), - def_const(local_def(item.id)), - sp); - } - item_fn(_, purity, _, _) => { - let (name_bindings, new_parent) = self.add_child(atom, parent, - ~[ValueNS], sp); - - let def = def_fn(local_def(item.id), purity); - (*name_bindings).define_value - (self.visibility_to_privacy(item.vis), def, sp); - visit_item(item, new_parent, visitor); - } - - // These items live in the type namespace. - item_ty(*) => { - let (name_bindings, _) = self.add_child(atom, parent, - ~[TypeNS], sp); - - (*name_bindings).define_type - (self.visibility_to_privacy(item.vis), - def_ty(local_def(item.id)), - sp); - } - - item_enum(enum_definition, _) => { - - let (name_bindings, new_parent) = self.add_child(atom, parent, - ~[TypeNS], sp); - - (*name_bindings).define_type - (self.visibility_to_privacy(item.vis), - def_ty(local_def(item.id)), - sp); - - for enum_definition.variants.each |variant| { - self.build_reduced_graph_for_variant(variant, - local_def(item.id), - new_parent, - visitor); - } - } - - // These items live in both the type and value namespaces. - item_class(struct_definition, _) => { - let new_parent = - match struct_definition.ctor { - None => { - let (name_bindings, new_parent) = - self.add_child(atom, parent, ~[TypeNS], sp); - - (*name_bindings).define_type - (self.visibility_to_privacy(item.vis), - def_ty(local_def(item.id)), - sp); - new_parent - } - Some(ctor) => { - let (name_bindings, new_parent) = - self.add_child(atom, parent, ~[ValueNS, TypeNS], - sp); - - let privacy = self.visibility_to_privacy(item.vis); - - (*name_bindings).define_type - (privacy, def_ty(local_def(item.id)), sp); - - let purity = impure_fn; - let ctor_def = def_fn(local_def(ctor.node.id), - purity); - (*name_bindings).define_value(privacy, ctor_def, sp); - new_parent - } - }; - - // Record the def ID of this struct. - self.structs.insert(local_def(item.id), - is_some(struct_definition.ctor)); - - visit_item(item, new_parent, visitor); - } - - item_impl(*) => { - visit_item(item, parent, visitor); - } - - item_trait(_, _, methods) => { - let (name_bindings, new_parent) = self.add_child(atom, parent, - ~[TypeNS], sp); - - // Add the names of all the methods to the trait info. - let method_names = @atom_hashmap(); - for methods.each |method| { - let ty_m = trait_method_to_ty_method(method); - - let atom = ty_m.ident; - // Add it to the trait info if not static, - // add it as a name in the enclosing module otherwise. - match ty_m.self_ty.node { - sty_static => { - // which parent to use?? - let (method_name_bindings, _) = - self.add_child(atom, new_parent, ~[ValueNS], - ty_m.span); - let def = def_static_method(local_def(ty_m.id), - ty_m.purity); - (*method_name_bindings).define_value - (Public, def, ty_m.span); - } - _ => { - (*method_names).insert(atom, ()); - } - } - } - - let def_id = local_def(item.id); - self.trait_info.insert(def_id, method_names); - - (*name_bindings).define_type - (self.visibility_to_privacy(item.vis), - def_ty(def_id), - sp); - visit_item(item, new_parent, visitor); - } - - item_mac(*) => { - fail ~"item macros unimplemented" - } - } - } - - // Constructs the reduced graph for one variant. Variants exist in the - // type and/or value namespaces. - fn build_reduced_graph_for_variant(variant: variant, - item_id: def_id, - parent: ReducedGraphParent, - &&visitor: vt) { - - let atom = variant.node.name; - let (child, _) = self.add_child(atom, parent, ~[ValueNS], - variant.span); - - match variant.node.kind { - tuple_variant_kind(_) => { - (*child).define_value(Public, - def_variant(item_id, - local_def(variant.node.id)), - variant.span); - } - struct_variant_kind(_) => { - (*child).define_type(Public, - def_variant(item_id, - local_def(variant.node.id)), - variant.span); - self.structs.insert(local_def(variant.node.id), false); - } - enum_variant_kind(enum_definition) => { - (*child).define_type(Public, - def_ty(local_def(variant.node.id)), - variant.span); - for enum_definition.variants.each |variant| { - self.build_reduced_graph_for_variant(variant, item_id, - parent, visitor); - } - } - } - } - - /** - * Constructs the reduced graph for one 'view item'. View items consist - * of imports and use directives. - */ - fn build_reduced_graph_for_view_item(view_item: @view_item, - parent: ReducedGraphParent, - &&_visitor: vt) { - match view_item.node { - view_item_import(view_paths) => { - for view_paths.each |view_path| { - // Extract and intern the module part of the path. For - // globs and lists, the path is found directly in the AST; - // for simple paths we have to munge the path a little. - - let module_path = @DVec(); - match view_path.node { - view_path_simple(_, full_path, _) => { - let path_len = full_path.idents.len(); - assert path_len != 0u; - - for full_path.idents.eachi |i, ident| { - if i != path_len - 1u { - (*module_path).push(ident); - } - } - } - - view_path_glob(module_ident_path, _) | - view_path_list(module_ident_path, _, _) => { - for module_ident_path.idents.each |ident| { - (*module_path).push(ident); - } - } - } - - // Build up the import directives. - let module_ = self.get_module_from_parent(parent); - match view_path.node { - view_path_simple(binding, full_path, _) => { - let source_ident = full_path.idents.last(); - let subclass = @SingleImport(binding, - source_ident); - self.build_import_directive(module_, - module_path, - subclass, - view_path.span); - } - view_path_list(_, source_idents, _) => { - for source_idents.each |source_ident| { - let name = source_ident.node.name; - let subclass = @SingleImport(name, name); - self.build_import_directive(module_, - module_path, - subclass, - view_path.span); - } - } - view_path_glob(_, _) => { - self.build_import_directive(module_, - module_path, - @GlobImport, - view_path.span); - } - } - } - } - - view_item_export(view_paths) => { - let module_ = self.get_module_from_parent(parent); - for view_paths.each |view_path| { - match view_path.node { - view_path_simple(ident, full_path, ident_id) => { - let last_ident = full_path.idents.last(); - if last_ident != ident { - self.session.span_err(view_item.span, - ~"cannot export under \ - a new name"); - } - if full_path.idents.len() != 1u { - self.session.span_err( - view_item.span, - ~"cannot export an item \ - that is not in this \ - module"); - } - - module_.exported_names.insert(ident, ident_id); - } - - view_path_glob(*) => { - self.session.span_err(view_item.span, - ~"export globs are \ - unsupported"); - } - - view_path_list(path, path_list_idents, _) => { - if path.idents.len() == 1u && - path_list_idents.len() == 0u { - - self.session.span_warn(view_item.span, - ~"this syntax for \ - exporting no \ - variants is \ - unsupported; export \ - variants \ - individually"); - } else { - if path.idents.len() != 0u { - self.session.span_err(view_item.span, - ~"cannot export an \ - item that is not \ - in this module"); - } - - for path_list_idents.each |path_list_ident| { - let atom = path_list_ident.node.name; - let id = path_list_ident.node.id; - module_.exported_names.insert(atom, id); - } - } - } - } - } - } - - view_item_use(name, _, node_id) => { - match find_use_stmt_cnum(self.session.cstore, node_id) { - Some(crate_id) => { - let (child_name_bindings, new_parent) = - // should this be in ModuleNS? --tjc - self.add_child(name, parent, ~[ModuleNS], - view_item.span); - - let def_id = { crate: crate_id, node: 0 }; - let parent_link = ModuleParentLink - (self.get_module_from_parent(new_parent), name); - - (*child_name_bindings).define_module(parent_link, - Some(def_id), - view_item.span); - self.build_reduced_graph_for_external_crate - ((*child_name_bindings).get_module()); - } - None => { - /* Ignore. */ - } - } - } - } - } - - /// Constructs the reduced graph for one foreign item. - fn build_reduced_graph_for_foreign_item(foreign_item: @foreign_item, - parent: ReducedGraphParent, - &&visitor: - vt) { - - let name = foreign_item.ident; - let (name_bindings, new_parent) = - self.add_child(name, parent, ~[ValueNS], foreign_item.span); - - match foreign_item.node { - foreign_item_fn(_, purity, type_parameters) => { - let def = def_fn(local_def(foreign_item.id), purity); - (*name_bindings).define_value(Public, def, foreign_item.span); - - do self.with_type_parameter_rib - (HasTypeParameters(&type_parameters, foreign_item.id, - 0u, NormalRibKind)) { - visit_foreign_item(foreign_item, new_parent, visitor); - } - } - foreign_item_const(*) => { - let def = def_const(local_def(foreign_item.id)); - (*name_bindings).define_value(Public, def, foreign_item.span); - - visit_foreign_item(foreign_item, new_parent, visitor); - } - } - } - - fn build_reduced_graph_for_block(block: blk, - parent: ReducedGraphParent, - &&visitor: vt) { - - let mut new_parent; - if self.block_needs_anonymous_module(block) { - let block_id = block.node.id; - - debug!("(building reduced graph for block) creating a new \ - anonymous module for block %d", - block_id); - - let parent_module = self.get_module_from_parent(parent); - let new_module = @Module(BlockParentLink(parent_module, block_id), - None); - parent_module.anonymous_children.insert(block_id, new_module); - new_parent = ModuleReducedGraphParent(new_module); - } else { - new_parent = parent; - } - - visit_block(block, new_parent, visitor); - } - - fn handle_external_def(def: def, modules: hashmap, - child_name_bindings: @NameBindings, - final_ident: ~str, - atom: Atom, new_parent: ReducedGraphParent) { - match def { - def_mod(def_id) | def_foreign_mod(def_id) => { - match copy child_name_bindings.module_def { - NoModuleDef => { - debug!("(building reduced graph for \ - external crate) building module \ - %s", final_ident); - let parent_link = self.get_parent_link(new_parent, atom); - - match modules.find(def_id) { - None => { - child_name_bindings.define_module(parent_link, - Some(def_id), - dummy_sp()); - modules.insert(def_id, - child_name_bindings.get_module()); - } - Some(existing_module) => { - // Create an import resolution to - // avoid creating cycles in the - // module graph. - - let resolution = @ImportResolution(dummy_sp()); - resolution.outstanding_references = 0; - - match existing_module.parent_link { - NoParentLink | - BlockParentLink(*) => { - fail ~"can't happen"; - } - ModuleParentLink(parent_module, atom) => { - - let name_bindings = parent_module.children.get(atom); - - resolution.module_target = - Some(Target(parent_module, name_bindings)); - } - } - - debug!("(building reduced graph for external crate) \ - ... creating import resolution"); - - new_parent.import_resolutions.insert(atom, resolution); - } - } - } - ModuleDef(module_) => { - debug!("(building reduced graph for \ - external crate) already created \ - module"); - module_.def_id = Some(def_id); - modules.insert(def_id, module_); - } - } - } - def_fn(*) | def_static_method(*) | def_const(*) | - def_variant(*) => { - debug!("(building reduced graph for external \ - crate) building value %s", final_ident); - (*child_name_bindings).define_value(Public, def, dummy_sp()); - } - def_ty(def_id) => { - debug!("(building reduced graph for external \ - crate) building type %s", final_ident); - - // If this is a trait, add all the method names - // to the trait info. - - match get_method_names_if_trait(self.session.cstore, - def_id) { - None => { - // Nothing to do. - } - Some(method_names) => { - let interned_method_names = @atom_hashmap(); - for method_names.each |method_data| { - let (method_name, self_ty) = method_data; - debug!("(building reduced graph for \ - external crate) ... adding \ - trait method '%s'", - self.session.str_of(method_name)); - - // Add it to the trait info if not static. - if self_ty != sty_static { - interned_method_names.insert(method_name, ()); - } - } - self.trait_info.insert(def_id, interned_method_names); - } - } - - child_name_bindings.define_type(Public, def, dummy_sp()); - } - def_class(def_id, has_constructor) => { - debug!("(building reduced graph for external \ - crate) building type %s (value? %d)", - final_ident, - if has_constructor { 1 } else { 0 }); - child_name_bindings.define_type(Public, def, dummy_sp()); - - if has_constructor { - child_name_bindings.define_value(Public, def, dummy_sp()); - } - - self.structs.insert(def_id, has_constructor); - } - def_self(*) | def_arg(*) | def_local(*) | - def_prim_ty(*) | def_ty_param(*) | def_binding(*) | - def_use(*) | def_upvar(*) | def_region(*) | - def_typaram_binder(*) | def_label(*) => { - fail fmt!("didn't expect `%?`", def); - } - } - } - - /** - * Builds the reduced graph rooted at the 'use' directive for an external - * crate. - */ - fn build_reduced_graph_for_external_crate(root: @Module) { - let modules = new_def_hash(); - - // Create all the items reachable by paths. - for each_path(self.session.cstore, get(root.def_id).crate) - |path_entry| { - - debug!("(building reduced graph for external crate) found path \ - entry: %s (%?)", - path_entry.path_string, - path_entry.def_like); - - let mut pieces = split_str(path_entry.path_string, ~"::"); - let final_ident_str = pop(pieces); - let final_ident = self.session.ident_of(final_ident_str); - - // Find the module we need, creating modules along the way if we - // need to. - - let mut current_module = root; - for pieces.each |ident_str| { - let ident = self.session.ident_of(ident_str); - // Create or reuse a graph node for the child. - let (child_name_bindings, new_parent) = - self.add_child(ident, - ModuleReducedGraphParent(current_module), - // May want a better span - ~[], dummy_sp()); - - // Define or reuse the module node. - match child_name_bindings.module_def { - NoModuleDef => { - debug!("(building reduced graph for external crate) \ - autovivifying %s", ident_str); - let parent_link = self.get_parent_link(new_parent, - ident); - (*child_name_bindings).define_module(parent_link, - None, dummy_sp()); - } - ModuleDef(_) => { /* Fall through. */ } - } - - current_module = (*child_name_bindings).get_module(); - } - - // Add the new child item. - let (child_name_bindings, new_parent) = - self.add_child(final_ident, - ModuleReducedGraphParent(current_module), - ~[], dummy_sp()); - - match path_entry.def_like { - dl_def(def) => { - self.handle_external_def(def, modules, - child_name_bindings, - self.session.str_of(final_ident), - final_ident, new_parent); - } - dl_impl(_) => { - // Because of the infelicitous way the metadata is - // written, we can't process this impl now. We'll get it - // later. - - debug!("(building reduced graph for external crate) \ - ignoring impl %s", final_ident_str); - } - dl_field => { - debug!("(building reduced graph for external crate) \ - ignoring field %s", final_ident_str); - } - } - } - } - - /// Creates and adds an import directive to the given module. - fn build_import_directive(module_: @Module, - module_path: @DVec, - subclass: @ImportDirectiveSubclass, - span: span) { - - let directive = @ImportDirective(module_path, subclass, span); - module_.imports.push(directive); - - // Bump the reference count on the name. Or, if this is a glob, set - // the appropriate flag. - - match *subclass { - SingleImport(target, _) => { - match module_.import_resolutions.find(target) { - Some(resolution) => { - resolution.outstanding_references += 1u; - } - None => { - let resolution = @ImportResolution(span); - resolution.outstanding_references = 1u; - module_.import_resolutions.insert(target, resolution); - } - } - } - GlobImport => { - // Set the glob flag. This tells us that we don't know the - // module's exports ahead of time. - - module_.glob_count += 1u; - } - } - - self.unresolved_imports += 1u; - } - - // Import resolution - // - // This is a fixed-point algorithm. We resolve imports until our efforts - // are stymied by an unresolved import; then we bail out of the current - // module and continue. We terminate successfully once no more imports - // remain or unsuccessfully when no forward progress in resolving imports - // is made. - - /** - * Resolves all imports for the crate. This method performs the fixed- - * point iteration. - */ - fn resolve_imports() { - let mut i = 0u; - let mut prev_unresolved_imports = 0u; - loop { - debug!("(resolving imports) iteration %u, %u imports left", - i, self.unresolved_imports); - - let module_root = (*self.graph_root).get_module(); - self.resolve_imports_for_module_subtree(module_root); - - if self.unresolved_imports == 0u { - debug!("(resolving imports) success"); - break; - } - - if self.unresolved_imports == prev_unresolved_imports { - self.session.err(~"failed to resolve imports"); - self.report_unresolved_imports(module_root); - break; - } - - i += 1u; - prev_unresolved_imports = self.unresolved_imports; - } - } - - /** - * Attempts to resolve imports for the given module and all of its - * submodules. - */ - fn resolve_imports_for_module_subtree(module_: @Module) { - debug!("(resolving imports for module subtree) resolving %s", - self.module_to_str(module_)); - self.resolve_imports_for_module(module_); - - for module_.children.each |_name, child_node| { - match (*child_node).get_module_if_available() { - None => { - // Nothing to do. - } - Some(child_module) => { - self.resolve_imports_for_module_subtree(child_module); - } - } - } - - for module_.anonymous_children.each |_block_id, child_module| { - self.resolve_imports_for_module_subtree(child_module); - } - } - - /// Attempts to resolve imports for the given module only. - fn resolve_imports_for_module(module_: @Module) { - if (*module_).all_imports_resolved() { - debug!("(resolving imports for module) all imports resolved for \ - %s", - self.module_to_str(module_)); - return; - } - - let import_count = module_.imports.len(); - while module_.resolved_import_count < import_count { - let import_index = module_.resolved_import_count; - let import_directive = module_.imports.get_elt(import_index); - match self.resolve_import_for_module(module_, import_directive) { - Failed => { - // We presumably emitted an error. Continue. - self.session.span_err(import_directive.span, - ~"failed to resolve import"); - } - Indeterminate => { - // Bail out. We'll come around next time. - break; - } - Success(()) => { - // Good. Continue. - } - } - - module_.resolved_import_count += 1u; - } - } - - fn atoms_to_str(atoms: ~[Atom]) -> ~str { - // XXX: str::connect should do this. - let mut result = ~""; - let mut first = true; - for atoms.each() |atom| { - if first { - first = false; - } else { - result += ~"::"; - } - result += self.session.str_of(atom); - } - // XXX: Shouldn't copy here. We need string builder functionality. - return result; - } - /** - * Attempts to resolve the given import. The return value indicates - * failure if we're certain the name does not exist, indeterminate if we - * don't know whether the name exists at the moment due to other - * currently-unresolved imports, or success if we know the name exists. - * If successful, the resolved bindings are written into the module. - */ - fn resolve_import_for_module(module_: @Module, - import_directive: @ImportDirective) - -> ResolveResult<()> { - - let mut resolution_result; - let module_path = import_directive.module_path; - - debug!("(resolving import for module) resolving import `%s::...` in \ - `%s`", - self.atoms_to_str((*module_path).get()), - self.module_to_str(module_)); - - // One-level renaming imports of the form `import foo = bar;` are - // handled specially. - - if (*module_path).len() == 0u { - resolution_result = - self.resolve_one_level_renaming_import(module_, - import_directive); - } else { - // First, resolve the module path for the directive, if necessary. - match self.resolve_module_path_for_import(module_, - module_path, - NoXray, - import_directive.span) { - - Failed => { - resolution_result = Failed; - } - Indeterminate => { - resolution_result = Indeterminate; - } - Success(containing_module) => { - // We found the module that the target is contained - // within. Attempt to resolve the import within it. - - match *import_directive.subclass { - SingleImport(target, source) => { - resolution_result = - self.resolve_single_import(module_, - containing_module, - target, - source); - } - GlobImport => { - let span = import_directive.span; - resolution_result = - self.resolve_glob_import(module_, - containing_module, - span); - } - } - } - } - } - - // Decrement the count of unresolved imports. - match resolution_result { - Success(()) => { - assert self.unresolved_imports >= 1u; - self.unresolved_imports -= 1u; - } - _ => { - // Nothing to do here; just return the error. - } - } - - // Decrement the count of unresolved globs if necessary. But only if - // the resolution result is indeterminate -- otherwise we'll stop - // processing imports here. (See the loop in - // resolve_imports_for_module.) - - if resolution_result != Indeterminate { - match *import_directive.subclass { - GlobImport => { - assert module_.glob_count >= 1u; - module_.glob_count -= 1u; - } - SingleImport(*) => { - // Ignore. - } - } - } - - return resolution_result; - } - - fn resolve_single_import(module_: @Module, containing_module: @Module, - target: Atom, source: Atom) - -> ResolveResult<()> { - - debug!("(resolving single import) resolving `%s` = `%s::%s` from \ - `%s`", - self.session.str_of(target), - self.module_to_str(containing_module), - self.session.str_of(source), - self.module_to_str(module_)); - - if !self.name_is_exported(containing_module, source) { - debug!("(resolving single import) name `%s` is unexported", - self.session.str_of(source)); - return Failed; - } - - // We need to resolve all four namespaces for this to succeed. - // - // XXX: See if there's some way of handling namespaces in a more - // generic way. We have four of them; it seems worth doing... - - let mut module_result = UnknownResult; - let mut value_result = UnknownResult; - let mut type_result = UnknownResult; - - // Search for direct children of the containing module. - match containing_module.children.find(source) { - None => { - // Continue. - } - Some(child_name_bindings) => { - if (*child_name_bindings).defined_in_namespace(ModuleNS) { - module_result = BoundResult(containing_module, - child_name_bindings); - } - if (*child_name_bindings).defined_in_namespace(ValueNS) { - value_result = BoundResult(containing_module, - child_name_bindings); - } - if (*child_name_bindings).defined_in_namespace(TypeNS) { - type_result = BoundResult(containing_module, - child_name_bindings); - } - } - } - - // Unless we managed to find a result in all four namespaces - // (exceedingly unlikely), search imports as well. - - match (module_result, value_result, type_result) { - (BoundResult(*), BoundResult(*), BoundResult(*)) => { - // Continue. - } - _ => { - // If there is an unresolved glob at this point in the - // containing module, bail out. We don't know enough to be - // able to resolve this import. - - if containing_module.glob_count > 0u { - debug!("(resolving single import) unresolved glob; \ - bailing out"); - return Indeterminate; - } - - // Now search the exported imports within the containing - // module. - - match containing_module.import_resolutions.find(source) { - None => { - // The containing module definitely doesn't have an - // exported import with the name in question. We can - // therefore accurately report that the names are - // unbound. - - if module_result == UnknownResult { - module_result = UnboundResult; - } - if value_result == UnknownResult { - value_result = UnboundResult; - } - if type_result == UnknownResult { - type_result = UnboundResult; - } - } - Some(import_resolution) - if import_resolution.outstanding_references - == 0u => { - - fn get_binding(import_resolution: @ImportResolution, - namespace: Namespace) - -> NamespaceResult { - - match (*import_resolution). - target_for_namespace(namespace) { - None => { - return UnboundResult; - } - Some(target) => { - import_resolution.used = true; - return BoundResult(target.target_module, - target.bindings); - } - } - } - - // The name is an import which has been fully - // resolved. We can, therefore, just follow it. - - if module_result == UnknownResult { - module_result = get_binding(import_resolution, - ModuleNS); - } - if value_result == UnknownResult { - value_result = get_binding(import_resolution, - ValueNS); - } - if type_result == UnknownResult { - type_result = get_binding(import_resolution, - TypeNS); - } - } - Some(_) => { - // The import is unresolved. Bail out. - debug!("(resolving single import) unresolved import; \ - bailing out"); - return Indeterminate; - } - } - } - } - - // We've successfully resolved the import. Write the results in. - assert module_.import_resolutions.contains_key(target); - let import_resolution = module_.import_resolutions.get(target); - - match module_result { - BoundResult(target_module, name_bindings) => { - debug!("(resolving single import) found module binding"); - import_resolution.module_target = - Some(Target(target_module, name_bindings)); - } - UnboundResult => { - debug!("(resolving single import) didn't find module \ - binding"); - } - UnknownResult => { - fail ~"module result should be known at this point"; - } - } - match value_result { - BoundResult(target_module, name_bindings) => { - import_resolution.value_target = - Some(Target(target_module, name_bindings)); - } - UnboundResult => { /* Continue. */ } - UnknownResult => { - fail ~"value result should be known at this point"; - } - } - match type_result { - BoundResult(target_module, name_bindings) => { - import_resolution.type_target = - Some(Target(target_module, name_bindings)); - } - UnboundResult => { /* Continue. */ } - UnknownResult => { - fail ~"type result should be known at this point"; - } - } - - let i = import_resolution; - match (i.module_target, i.value_target, i.type_target) { - /* - If this name wasn't found in any of the four namespaces, it's - definitely unresolved - */ - (None, None, None) => { return Failed; } - _ => {} - } - - assert import_resolution.outstanding_references >= 1u; - import_resolution.outstanding_references -= 1u; - - debug!("(resolving single import) successfully resolved import"); - return Success(()); - } - - /** - * Resolves a glob import. Note that this function cannot fail; it either - * succeeds or bails out (as importing * from an empty module or a module - * that exports nothing is valid). - */ - fn resolve_glob_import(module_: @Module, - containing_module: @Module, - span: span) - -> ResolveResult<()> { - - // This function works in a highly imperative manner; it eagerly adds - // everything it can to the list of import resolutions of the module - // node. - - // We must bail out if the node has unresolved imports of any kind - // (including globs). - - if !(*containing_module).all_imports_resolved() { - debug!("(resolving glob import) target module has unresolved \ - imports; bailing out"); - return Indeterminate; - } - - assert containing_module.glob_count == 0u; - - // Add all resolved imports from the containing module. - for containing_module.import_resolutions.each - |atom, target_import_resolution| { - - if !self.name_is_exported(containing_module, atom) { - debug!("(resolving glob import) name `%s` is unexported", - self.session.str_of(atom)); - again; - } - - debug!("(resolving glob import) writing module resolution \ - %? into `%s`", - is_none(target_import_resolution.module_target), - self.module_to_str(module_)); - - // Here we merge two import resolutions. - match module_.import_resolutions.find(atom) { - None => { - // Simple: just copy the old import resolution. - let new_import_resolution = - @ImportResolution(target_import_resolution.span); - new_import_resolution.module_target = - copy target_import_resolution.module_target; - new_import_resolution.value_target = - copy target_import_resolution.value_target; - new_import_resolution.type_target = - copy target_import_resolution.type_target; - - module_.import_resolutions.insert - (atom, new_import_resolution); - } - Some(dest_import_resolution) => { - // Merge the two import resolutions at a finer-grained - // level. - - match copy target_import_resolution.module_target { - None => { - // Continue. - } - Some(module_target) => { - dest_import_resolution.module_target = - Some(copy module_target); - } - } - match copy target_import_resolution.value_target { - None => { - // Continue. - } - Some(value_target) => { - dest_import_resolution.value_target = - Some(copy value_target); - } - } - match copy target_import_resolution.type_target { - None => { - // Continue. - } - Some(type_target) => { - dest_import_resolution.type_target = - Some(copy type_target); - } - } - } - } - } - - // Add all children from the containing module. - for containing_module.children.each |atom, name_bindings| { - if !self.name_is_exported(containing_module, atom) { - debug!("(resolving glob import) name `%s` is unexported", - self.session.str_of(atom)); - again; - } - - let mut dest_import_resolution; - match module_.import_resolutions.find(atom) { - None => { - // Create a new import resolution from this child. - dest_import_resolution = @ImportResolution(span); - module_.import_resolutions.insert - (atom, dest_import_resolution); - } - Some(existing_import_resolution) => { - dest_import_resolution = existing_import_resolution; - } - } - - - debug!("(resolving glob import) writing resolution `%s` in `%s` \ - to `%s`", - self.session.str_of(atom), - self.module_to_str(containing_module), - self.module_to_str(module_)); - - // Merge the child item into the import resolution. - if (*name_bindings).defined_in_namespace(ModuleNS) { - debug!("(resolving glob import) ... for module target"); - dest_import_resolution.module_target = - Some(Target(containing_module, name_bindings)); - } - if (*name_bindings).defined_in_namespace(ValueNS) { - debug!("(resolving glob import) ... for value target"); - dest_import_resolution.value_target = - Some(Target(containing_module, name_bindings)); - } - if (*name_bindings).defined_in_namespace(TypeNS) { - debug!("(resolving glob import) ... for type target"); - dest_import_resolution.type_target = - Some(Target(containing_module, name_bindings)); - } - } - - debug!("(resolving glob import) successfully resolved import"); - return Success(()); - } - - fn resolve_module_path_from_root(module_: @Module, - module_path: @DVec, - index: uint, - xray: XrayFlag, - span: span) - -> ResolveResult<@Module> { - - let mut search_module = module_; - let mut index = index; - let module_path_len = (*module_path).len(); - - // Resolve the module part of the path. This does not involve looking - // upward though scope chains; we simply resolve names directly in - // modules as we go. - - while index < module_path_len { - let name = (*module_path).get_elt(index); - match self.resolve_name_in_module(search_module, name, ModuleNS, - xray) { - - Failed => { - self.session.span_err(span, ~"unresolved name"); - return Failed; - } - Indeterminate => { - debug!("(resolving module path for import) module \ - resolution is indeterminate: %s", - self.session.str_of(name)); - return Indeterminate; - } - Success(target) => { - match target.bindings.module_def { - NoModuleDef => { - // Not a module. - self.session.span_err(span, - fmt!("not a module: %s", - self.session. - str_of(name))); - return Failed; - } - ModuleDef(copy module_) => { - search_module = module_; - } - } - } - } - - index += 1u; - } - - return Success(search_module); - } - - /** - * Attempts to resolve the module part of an import directive rooted at - * the given module. - */ - fn resolve_module_path_for_import(module_: @Module, - module_path: @DVec, - xray: XrayFlag, - span: span) - -> ResolveResult<@Module> { - - let module_path_len = (*module_path).len(); - assert module_path_len > 0u; - - debug!("(resolving module path for import) processing `%s` rooted at \ - `%s`", - self.atoms_to_str((*module_path).get()), - self.module_to_str(module_)); - - // The first element of the module path must be in the current scope - // chain. - - let first_element = (*module_path).get_elt(0u); - let mut search_module; - match self.resolve_module_in_lexical_scope(module_, first_element) { - Failed => { - self.session.span_err(span, ~"unresolved name"); - return Failed; - } - Indeterminate => { - debug!("(resolving module path for import) indeterminate; \ - bailing"); - return Indeterminate; - } - Success(resulting_module) => { - search_module = resulting_module; - } - } - - return self.resolve_module_path_from_root(search_module, - module_path, - 1u, - xray, - span); - } - - fn resolve_item_in_lexical_scope(module_: @Module, - name: Atom, - namespace: Namespace) - -> ResolveResult { - - debug!("(resolving item in lexical scope) resolving `%s` in \ - namespace %? in `%s`", - self.session.str_of(name), - namespace, - self.module_to_str(module_)); - - // The current module node is handled specially. First, check for - // its immediate children. - - match module_.children.find(name) { - Some(name_bindings) - if (*name_bindings).defined_in_namespace(namespace) => { - - return Success(Target(module_, name_bindings)); - } - Some(_) | None => { /* Not found; continue. */ } - } - - // Now check for its import directives. We don't have to have resolved - // all its imports in the usual way; this is because chains of - // adjacent import statements are processed as though they mutated the - // current scope. - - match module_.import_resolutions.find(name) { - None => { - // Not found; continue. - } - Some(import_resolution) => { - match (*import_resolution).target_for_namespace(namespace) { - None => { - // Not found; continue. - debug!("(resolving item in lexical scope) found \ - import resolution, but not in namespace %?", - namespace); - } - Some(target) => { - import_resolution.used = true; - return Success(copy target); - } - } - } - } - - // Finally, proceed up the scope chain looking for parent modules. - let mut search_module = module_; - loop { - // Go to the next parent. - match search_module.parent_link { - NoParentLink => { - // No more parents. This module was unresolved. - debug!("(resolving item in lexical scope) unresolved \ - module"); - return Failed; - } - ModuleParentLink(parent_module_node, _) | - BlockParentLink(parent_module_node, _) => { - search_module = parent_module_node; - } - } - - // Resolve the name in the parent module. - match self.resolve_name_in_module(search_module, name, namespace, - Xray) { - Failed => { - // Continue up the search chain. - } - Indeterminate => { - // We couldn't see through the higher scope because of an - // unresolved import higher up. Bail. - - debug!("(resolving item in lexical scope) indeterminate \ - higher scope; bailing"); - return Indeterminate; - } - Success(target) => { - // We found the module. - return Success(copy target); - } - } - } - } - - fn resolve_module_in_lexical_scope(module_: @Module, name: Atom) - -> ResolveResult<@Module> { - - match self.resolve_item_in_lexical_scope(module_, name, ModuleNS) { - Success(target) => { - match target.bindings.module_def { - NoModuleDef => { - error!("!!! (resolving module in lexical scope) module - wasn't actually a module!"); - return Failed; - } - ModuleDef(module_) => { - return Success(module_); - } - } - } - Indeterminate => { - debug!("(resolving module in lexical scope) indeterminate; \ - bailing"); - return Indeterminate; - } - Failed => { - debug!("(resolving module in lexical scope) failed to \ - resolve"); - return Failed; - } - } - } - - fn name_is_exported(module_: @Module, name: Atom) -> bool { - return module_.exported_names.size() == 0u || - module_.exported_names.contains_key(name); - } - - /** - * Attempts to resolve the supplied name in the given module for the - * given namespace. If successful, returns the target corresponding to - * the name. - */ - fn resolve_name_in_module(module_: @Module, - name: Atom, - namespace: Namespace, - xray: XrayFlag) - -> ResolveResult { - - debug!("(resolving name in module) resolving `%s` in `%s`", - self.session.str_of(name), - self.module_to_str(module_)); - - if xray == NoXray && !self.name_is_exported(module_, name) { - debug!("(resolving name in module) name `%s` is unexported", - self.session.str_of(name)); - return Failed; - } - - // First, check the direct children of the module. - match module_.children.find(name) { - Some(name_bindings) - if (*name_bindings).defined_in_namespace(namespace) => { - - debug!("(resolving name in module) found node as child"); - return Success(Target(module_, name_bindings)); - } - Some(_) | None => { - // Continue. - } - } - - // Next, check the module's imports. If the module has a glob, then - // we bail out; we don't know its imports yet. - - if module_.glob_count > 0u { - debug!("(resolving name in module) module has glob; bailing out"); - return Indeterminate; - } - - // Otherwise, we check the list of resolved imports. - match module_.import_resolutions.find(name) { - Some(import_resolution) => { - if import_resolution.outstanding_references != 0u { - debug!("(resolving name in module) import unresolved; \ - bailing out"); - return Indeterminate; - } - - match (*import_resolution).target_for_namespace(namespace) { - None => { - debug!("(resolving name in module) name found, but \ - not in namespace %?", - namespace); - } - Some(target) => { - debug!("(resolving name in module) resolved to \ - import"); - import_resolution.used = true; - return Success(copy target); - } - } - } - None => { - // Continue. - } - } - - // We're out of luck. - debug!("(resolving name in module) failed to resolve %s", - self.session.str_of(name)); - return Failed; - } - - /** - * Resolves a one-level renaming import of the kind `import foo = bar;` - * This needs special handling, as, unlike all of the other imports, it - * needs to look in the scope chain for modules and non-modules alike. - */ - fn resolve_one_level_renaming_import(module_: @Module, - import_directive: @ImportDirective) - -> ResolveResult<()> { - - let mut target_name; - let mut source_name; - match *import_directive.subclass { - SingleImport(target, source) => { - target_name = target; - source_name = source; - } - GlobImport => { - fail ~"found `import *`, which is invalid"; - } - } - - debug!("(resolving one-level naming result) resolving import `%s` = \ - `%s` in `%s`", - self.session.str_of(target_name), - self.session.str_of(source_name), - self.module_to_str(module_)); - - // Find the matching items in the lexical scope chain for every - // namespace. If any of them come back indeterminate, this entire - // import is indeterminate. - - let mut module_result; - debug!("(resolving one-level naming result) searching for module"); - match self.resolve_item_in_lexical_scope(module_, - source_name, - ModuleNS) { - - Failed => { - debug!("(resolving one-level renaming import) didn't find \ - module result"); - module_result = None; - } - Indeterminate => { - debug!("(resolving one-level renaming import) module result \ - is indeterminate; bailing"); - return Indeterminate; - } - Success(name_bindings) => { - debug!("(resolving one-level renaming import) module result \ - found"); - module_result = Some(copy name_bindings); - } - } - - let mut value_result; - debug!("(resolving one-level naming result) searching for value"); - match self.resolve_item_in_lexical_scope(module_, - source_name, - ValueNS) { - - Failed => { - debug!("(resolving one-level renaming import) didn't find \ - value result"); - value_result = None; - } - Indeterminate => { - debug!("(resolving one-level renaming import) value result \ - is indeterminate; bailing"); - return Indeterminate; - } - Success(name_bindings) => { - debug!("(resolving one-level renaming import) value result \ - found"); - value_result = Some(copy name_bindings); - } - } - - let mut type_result; - debug!("(resolving one-level naming result) searching for type"); - match self.resolve_item_in_lexical_scope(module_, - source_name, - TypeNS) { - - Failed => { - debug!("(resolving one-level renaming import) didn't find \ - type result"); - type_result = None; - } - Indeterminate => { - debug!("(resolving one-level renaming import) type result is \ - indeterminate; bailing"); - return Indeterminate; - } - Success(name_bindings) => { - debug!("(resolving one-level renaming import) type result \ - found"); - type_result = Some(copy name_bindings); - } - } - - // - // NB: This one results in effects that may be somewhat surprising. It - // means that this: - // - // mod A { - // impl foo for ... { ... } - // mod B { - // impl foo for ... { ... } - // import bar = foo; - // ... - // } - // } - // - // results in only A::B::foo being aliased to A::B::bar, not A::foo - // *and* A::B::foo being aliased to A::B::bar. - // - - // If nothing at all was found, that's an error. - if is_none(module_result) && - is_none(value_result) && - is_none(type_result) { - - self.session.span_err(import_directive.span, - ~"unresolved import"); - return Failed; - } - - // Otherwise, proceed and write in the bindings. - match module_.import_resolutions.find(target_name) { - None => { - fail ~"(resolving one-level renaming import) reduced graph \ - construction or glob importing should have created the \ - import resolution name by now"; - } - Some(import_resolution) => { - debug!("(resolving one-level renaming import) writing module \ - result %? for `%s` into `%s`", - is_none(module_result), - self.session.str_of(target_name), - self.module_to_str(module_)); - - import_resolution.module_target = module_result; - import_resolution.value_target = value_result; - import_resolution.type_target = type_result; - - assert import_resolution.outstanding_references >= 1u; - import_resolution.outstanding_references -= 1u; - } - } - - debug!("(resolving one-level renaming import) successfully resolved"); - return Success(()); - } - - fn report_unresolved_imports(module_: @Module) { - let index = module_.resolved_import_count; - let import_count = module_.imports.len(); - if index != import_count { - self.session.span_err(module_.imports.get_elt(index).span, - ~"unresolved import"); - } - - // Descend into children and anonymous children. - for module_.children.each |_name, child_node| { - match (*child_node).get_module_if_available() { - None => { - // Continue. - } - Some(child_module) => { - self.report_unresolved_imports(child_module); - } - } - } - - for module_.anonymous_children.each |_name, module_| { - self.report_unresolved_imports(module_); - } - } - - // Export recording - // - // This pass simply determines what all "export" keywords refer to and - // writes the results into the export map. - // - // XXX: This pass will be removed once exports change to per-item. Then - // this operation can simply be performed as part of item (or import) - // processing. - - fn record_exports() { - let root_module = (*self.graph_root).get_module(); - self.record_exports_for_module_subtree(root_module); - } - - fn record_exports_for_module_subtree(module_: @Module) { - // If this isn't a local crate, then bail out. We don't need to record - // exports for local crates. - - match module_.def_id { - Some(def_id) if def_id.crate == local_crate => { - // OK. Continue. - } - None => { - // Record exports for the root module. - } - Some(_) => { - // Bail out. - debug!("(recording exports for module subtree) not recording \ - exports for `%s`", - self.module_to_str(module_)); - return; - } - } - - self.record_exports_for_module(module_); - - for module_.children.each |_atom, child_name_bindings| { - match (*child_name_bindings).get_module_if_available() { - None => { - // Nothing to do. - } - Some(child_module) => { - self.record_exports_for_module_subtree(child_module); - } - } - } - - for module_.anonymous_children.each |_node_id, child_module| { - self.record_exports_for_module_subtree(child_module); - } - } - - fn record_exports_for_module(module_: @Module) { - let mut exports2 = ~[]; - for module_.exported_names.each |name, node_id| { - let mut exports = ~[]; - for self.namespaces.each |namespace| { - match self.resolve_definition_of_name_in_module(module_, - name, - namespace, - Xray) { - NoNameDefinition => { - // Nothing to do. - } - ChildNameDefinition(target_def) => { - debug!("(computing exports) found child export '%s' \ - for %?", - self.session.str_of(name), - module_.def_id); - vec::push(exports, { - reexp: false, - id: def_id_of_def(target_def) - }); - vec::push(exports2, Export2 { - reexport: false, - name: self.session.str_of(name), - def_id: def_id_of_def(target_def) - }); - } - ImportNameDefinition(target_def) => { - debug!("(computing exports) found reexport '%s' for \ - %?", - self.session.str_of(name), - module_.def_id); - vec::push(exports, { - reexp: true, - id: def_id_of_def(target_def) - }); - vec::push(exports2, Export2 { - reexport: true, - name: self.session.str_of(name), - def_id: def_id_of_def(target_def) - }); - } - } - } - - self.export_map.insert(node_id, exports); - } - - match copy module_.def_id { - Some(def_id) => { - self.export_map2.insert(def_id.node, move exports2); - debug!("(computing exports) writing exports for %d (some)", - def_id.node); - } - None => {} - } - } - - // AST resolution - // - // We maintain a list of value ribs and type ribs. - // - // Simultaneously, we keep track of the current position in the module - // graph in the `current_module` pointer. When we go to resolve a name in - // the value or type namespaces, we first look through all the ribs and - // then query the module graph. When we resolve a name in the module - // namespace, we can skip all the ribs (since nested modules are not - // allowed within blocks in Rust) and jump straight to the current module - // graph node. - // - // Named implementations are handled separately. When we find a method - // call, we consult the module node to find all of the implementations in - // scope. This information is lazily cached in the module node. We then - // generate a fake "implementation scope" containing all the - // implementations thus found, for compatibility with old resolve pass. - - fn with_scope(name: Option, f: fn()) { - let orig_module = self.current_module; - - // Move down in the graph. - match name { - None => { - // Nothing to do. - } - Some(name) => { - match orig_module.children.find(name) { - None => { - debug!("!!! (with scope) didn't find `%s` in `%s`", - self.session.str_of(name), - self.module_to_str(orig_module)); - } - Some(name_bindings) => { - match (*name_bindings).get_module_if_available() { - None => { - debug!("!!! (with scope) didn't find module \ - for `%s` in `%s`", - self.session.str_of(name), - self.module_to_str(orig_module)); - } - Some(module_) => { - self.current_module = module_; - } - } - } - } - } - } - - f(); - - self.current_module = orig_module; - } - - // Wraps the given definition in the appropriate number of `def_upvar` - // wrappers. - - fn upvarify(ribs: @DVec<@Rib>, rib_index: uint, def_like: def_like, - span: span, allow_capturing_self: AllowCapturingSelfFlag) - -> Option { - - let mut def; - let mut is_ty_param; - - match def_like { - dl_def(d @ def_local(*)) | dl_def(d @ def_upvar(*)) | - dl_def(d @ def_arg(*)) | dl_def(d @ def_binding(*)) => { - def = d; - is_ty_param = false; - } - dl_def(d @ def_ty_param(*)) => { - def = d; - is_ty_param = true; - } - dl_def(d @ def_self(*)) - if allow_capturing_self == DontAllowCapturingSelf => { - def = d; - is_ty_param = false; - } - _ => { - return Some(def_like); - } - } - - let mut rib_index = rib_index + 1u; - while rib_index < (*ribs).len() { - let rib = (*ribs).get_elt(rib_index); - match rib.kind { - NormalRibKind => { - // Nothing to do. Continue. - } - FunctionRibKind(function_id, body_id) => { - if !is_ty_param { - def = def_upvar(def_id_of_def(def).node, - @def, - function_id, - body_id); - } - } - MethodRibKind(item_id, _) => { - // If the def is a ty param, and came from the parent - // item, it's ok - match def { - def_ty_param(did, _) if self.def_map.find(copy(did.node)) - == Some(def_typaram_binder(item_id)) => { - // ok - } - _ => { - if !is_ty_param { - // This was an attempt to access an upvar inside a - // named function item. This is not allowed, so we - // report an error. - - self.session.span_err( - span, - ~"attempted dynamic environment-capture"); - } else { - // This was an attempt to use a type parameter outside - // its scope. - - self.session.span_err(span, - ~"attempt to use a type \ - argument out of scope"); - } - - return None; - } - } - } - OpaqueFunctionRibKind => { - if !is_ty_param { - // This was an attempt to access an upvar inside a - // named function item. This is not allowed, so we - // report an error. - - self.session.span_err( - span, - ~"attempted dynamic environment-capture"); - } else { - // This was an attempt to use a type parameter outside - // its scope. - - self.session.span_err(span, - ~"attempt to use a type \ - argument out of scope"); - } - - return None; - } - } - - rib_index += 1u; - } - - return Some(dl_def(def)); - } - - fn search_ribs(ribs: @DVec<@Rib>, name: Atom, span: span, - allow_capturing_self: AllowCapturingSelfFlag) - -> Option { - - // XXX: This should not use a while loop. - // XXX: Try caching? - - let mut i = (*ribs).len(); - while i != 0u { - i -= 1u; - let rib = (*ribs).get_elt(i); - match rib.bindings.find(name) { - Some(def_like) => { - return self.upvarify(ribs, i, def_like, span, - allow_capturing_self); - } - None => { - // Continue. - } - } - } - - return None; - } - - fn resolve_crate(@self) { - debug!("(resolving crate) starting"); - - visit_crate(*self.crate, (), mk_vt(@{ - visit_item: |item, _context, visitor| - self.resolve_item(item, visitor), - visit_arm: |arm, _context, visitor| - self.resolve_arm(arm, visitor), - visit_block: |block, _context, visitor| - self.resolve_block(block, visitor), - visit_expr: |expr, _context, visitor| - self.resolve_expr(expr, visitor), - visit_local: |local, _context, visitor| - self.resolve_local(local, visitor), - visit_ty: |ty, _context, visitor| - self.resolve_type(ty, visitor) - with *default_visitor() - })); - } - - fn resolve_item(item: @item, visitor: ResolveVisitor) { - debug!("(resolving item) resolving %s", - self.session.str_of(item.ident)); - - // Items with the !resolve_unexported attribute are X-ray contexts. - // This is used to allow the test runner to run unexported tests. - let orig_xray_flag = self.xray_context; - if contains_name(attr_metas(item.attrs), ~"!resolve_unexported") { - self.xray_context = Xray; - } - - match item.node { - item_enum(_, type_parameters) | - item_ty(_, type_parameters) => { - do self.with_type_parameter_rib - (HasTypeParameters(&type_parameters, item.id, 0u, - NormalRibKind)) - || { - - visit_item(item, (), visitor); - } - } - - item_impl(type_parameters, implemented_traits, self_type, - methods) => { - - self.resolve_implementation(item.id, item.span, - type_parameters, - implemented_traits, - self_type, methods, visitor); - } - - item_trait(type_parameters, traits, methods) => { - // Create a new rib for the self type. - let self_type_rib = @Rib(NormalRibKind); - (*self.type_ribs).push(self_type_rib); - self_type_rib.bindings.insert(self.self_atom, - dl_def(def_self(item.id))); - - // Create a new rib for the trait-wide type parameters. - do self.with_type_parameter_rib - (HasTypeParameters(&type_parameters, item.id, 0u, - NormalRibKind)) { - - self.resolve_type_parameters(type_parameters, visitor); - - // Resolve derived traits. - for traits.each |trt| { - match self.resolve_path(trt.path, TypeNS, true, - visitor) { - None => - self.session.span_err(trt.path.span, - ~"attempt to derive a \ - nonexistent trait"), - Some(def) => { - // Write a mapping from the trait ID to the - // definition of the trait into the definition - // map. - - debug!("(resolving trait) found trait def: \ - %?", def); - - self.record_def(trt.ref_id, def); - } - } - } - - for methods.each |method| { - // Create a new rib for the method-specific type - // parameters. - // - // XXX: Do we need a node ID here? - - match method { - required(ty_m) => { - do self.with_type_parameter_rib - (HasTypeParameters(&ty_m.tps, - item.id, - type_parameters.len(), - MethodRibKind(item.id, Required))) { - - // Resolve the method-specific type - // parameters. - self.resolve_type_parameters(ty_m.tps, - visitor); - - for ty_m.decl.inputs.each |argument| { - self.resolve_type(argument.ty, visitor); - } - - self.resolve_type(ty_m.decl.output, visitor); - } - } - provided(m) => { - self.resolve_method(MethodRibKind(item.id, - Provided(m.id)), - m, - type_parameters.len(), - visitor) - } - } - } - } - - (*self.type_ribs).pop(); - } - - item_class(struct_def, ty_params) => { - self.resolve_class(item.id, - @copy ty_params, - struct_def.traits, - struct_def.fields, - struct_def.methods, - struct_def.ctor, - struct_def.dtor, - visitor); - } - - item_mod(module_) => { - do self.with_scope(Some(item.ident)) { - self.resolve_module(module_, item.span, item.ident, - item.id, visitor); - } - } - - item_foreign_mod(foreign_module) => { - do self.with_scope(Some(item.ident)) { - for foreign_module.items.each |foreign_item| { - match foreign_item.node { - foreign_item_fn(_, _, type_parameters) => { - do self.with_type_parameter_rib - (HasTypeParameters(&type_parameters, - foreign_item.id, - 0u, - OpaqueFunctionRibKind)) - || { - - visit_foreign_item(foreign_item, (), - visitor); - } - } - foreign_item_const(_) => { - visit_foreign_item(foreign_item, (), - visitor); - } - } - } - } - } - - item_fn(fn_decl, _, ty_params, block) => { - // If this is the main function, we must record it in the - // session. - // - // For speed, we put the string comparison last in this chain - // of conditionals. - - if !self.session.building_library && - is_none(self.session.main_fn) && - item.ident == syntax::parse::token::special_idents::main { - - self.session.main_fn = Some((item.id, item.span)); - } - - self.resolve_function(OpaqueFunctionRibKind, - Some(@fn_decl), - HasTypeParameters - (&ty_params, - item.id, - 0u, - OpaqueFunctionRibKind), - block, - NoSelfBinding, - NoCaptureClause, - visitor); - } - - item_const(*) => { - visit_item(item, (), visitor); - } - - item_mac(*) => { - fail ~"item macros unimplemented" - } - } - - self.xray_context = orig_xray_flag; - } - - fn with_type_parameter_rib(type_parameters: TypeParameters, f: fn()) { - match type_parameters { - HasTypeParameters(type_parameters, node_id, initial_index, - rib_kind) => { - - let function_type_rib = @Rib(rib_kind); - (*self.type_ribs).push(function_type_rib); - - for (*type_parameters).eachi |index, type_parameter| { - let name = type_parameter.ident; - debug!("with_type_parameter_rib: %d %d", node_id, - type_parameter.id); - let def_like = dl_def(def_ty_param - (local_def(type_parameter.id), - index + initial_index)); - // Associate this type parameter with - // the item that bound it - self.record_def(type_parameter.id, - def_typaram_binder(node_id)); - (*function_type_rib).bindings.insert(name, def_like); - } - } - - NoTypeParameters => { - // Nothing to do. - } - } - - f(); - - match type_parameters { - HasTypeParameters(*) => { - (*self.type_ribs).pop(); - } - - NoTypeParameters => { - // Nothing to do. - } - } - } - - fn with_label_rib(f: fn()) { - (*self.label_ribs).push(@Rib(NormalRibKind)); - f(); - (*self.label_ribs).pop(); - } - - fn resolve_function(rib_kind: RibKind, - optional_declaration: Option<@fn_decl>, - type_parameters: TypeParameters, - block: blk, - self_binding: SelfBinding, - capture_clause: CaptureClause, - visitor: ResolveVisitor) { - - // Check each element of the capture clause. - match capture_clause { - NoCaptureClause => { - // Nothing to do. - } - HasCaptureClause(capture_clause) => { - // Resolve each captured item. - for (*capture_clause).each |capture_item| { - match self.resolve_identifier(capture_item.name, - ValueNS, - true, - capture_item.span) { - None => { - self.session.span_err(capture_item.span, - ~"unresolved name in \ - capture clause"); - } - Some(def) => { - self.record_def(capture_item.id, def); - } - } - } - } - } - - // Create a value rib for the function. - let function_value_rib = @Rib(rib_kind); - (*self.value_ribs).push(function_value_rib); - - // Create a label rib for the function. - let function_label_rib = @Rib(rib_kind); - (*self.label_ribs).push(function_label_rib); - - // If this function has type parameters, add them now. - do self.with_type_parameter_rib(type_parameters) { - // Resolve the type parameters. - match type_parameters { - NoTypeParameters => { - // Continue. - } - HasTypeParameters(type_parameters, _, _, _) => { - self.resolve_type_parameters(*type_parameters, visitor); - } - } - - // Add self to the rib, if necessary. - match self_binding { - NoSelfBinding => { - // Nothing to do. - } - HasSelfBinding(self_node_id) => { - let def_like = dl_def(def_self(self_node_id)); - (*function_value_rib).bindings.insert(self.self_atom, - def_like); - } - } - - // Add each argument to the rib. - match optional_declaration { - None => { - // Nothing to do. - } - Some(declaration) => { - for declaration.inputs.each |argument| { - let name = argument.ident; - let def_like = dl_def(def_arg(argument.id, - argument.mode)); - (*function_value_rib).bindings.insert(name, def_like); - - self.resolve_type(argument.ty, visitor); - - debug!("(resolving function) recorded argument `%s`", - self.session.str_of(name)); - } - - self.resolve_type(declaration.output, visitor); - } - } - - // Resolve the function body. - self.resolve_block(block, visitor); - - debug!("(resolving function) leaving function"); - } - - (*self.label_ribs).pop(); - (*self.value_ribs).pop(); - } - - fn resolve_type_parameters(type_parameters: ~[ty_param], - visitor: ResolveVisitor) { - - for type_parameters.each |type_parameter| { - for (*type_parameter.bounds).each |bound| { - match bound { - bound_copy | bound_send | bound_const | bound_owned => { - // Nothing to do. - } - bound_trait(trait_type) => { - self.resolve_type(trait_type, visitor); - } - } - } - } - } - - fn resolve_class(id: node_id, - type_parameters: @~[ty_param], - traits: ~[@trait_ref], - fields: ~[@struct_field], - methods: ~[@method], - optional_constructor: Option, - optional_destructor: Option, - visitor: ResolveVisitor) { - - // If applicable, create a rib for the type parameters. - let outer_type_parameter_count = (*type_parameters).len(); - let borrowed_type_parameters: &~[ty_param] = &*type_parameters; - do self.with_type_parameter_rib(HasTypeParameters - (borrowed_type_parameters, id, 0u, - NormalRibKind)) { - - // Resolve the type parameters. - self.resolve_type_parameters(*type_parameters, visitor); - - // Resolve implemented traits. - for traits.each |trt| { - match self.resolve_path(trt.path, TypeNS, true, visitor) { - None => { - self.session.span_err(trt.path.span, - ~"attempt to implement a \ - nonexistent trait"); - } - Some(def) => { - // Write a mapping from the trait ID to the - // definition of the trait into the definition - // map. - - debug!("(resolving class) found trait def: %?", def); - - self.record_def(trt.ref_id, def); - - // XXX: This is wrong but is needed for tests to - // pass. - - self.record_def(id, def); - } - } - } - - // Resolve methods. - for methods.each |method| { - self.resolve_method(MethodRibKind(id, Provided(method.id)), - method, - outer_type_parameter_count, - visitor); - } - - // Resolve fields. - for fields.each |field| { - self.resolve_type(field.node.ty, visitor); - } - - // Resolve the constructor, if applicable. - match optional_constructor { - None => { - // Nothing to do. - } - Some(constructor) => { - self.resolve_function(NormalRibKind, - Some(@constructor.node.dec), - NoTypeParameters, - constructor.node.body, - HasSelfBinding(constructor.node. - self_id), - NoCaptureClause, - visitor); - } - } - - // Resolve the destructor, if applicable. - match optional_destructor { - None => { - // Nothing to do. - } - Some(destructor) => { - self.resolve_function(NormalRibKind, - None, - NoTypeParameters, - destructor.node.body, - HasSelfBinding - (destructor.node.self_id), - NoCaptureClause, - visitor); - } - } - } - } - - // Does this really need to take a RibKind or is it always going - // to be NormalRibKind? - fn resolve_method(rib_kind: RibKind, - method: @method, - outer_type_parameter_count: uint, - visitor: ResolveVisitor) { - let borrowed_method_type_parameters = &method.tps; - let type_parameters = - HasTypeParameters(borrowed_method_type_parameters, - method.id, - outer_type_parameter_count, - rib_kind); - // we only have self ty if it is a non static method - let self_binding = match method.self_ty.node { - sty_static => { NoSelfBinding } - _ => { HasSelfBinding(method.self_id) } - }; - - self.resolve_function(rib_kind, - Some(@method.decl), - type_parameters, - method.body, - self_binding, - NoCaptureClause, - visitor); - } - - fn resolve_implementation(id: node_id, - span: span, - type_parameters: ~[ty_param], - trait_references: ~[@trait_ref], - self_type: @ty, - methods: ~[@method], - visitor: ResolveVisitor) { - - // If applicable, create a rib for the type parameters. - let outer_type_parameter_count = type_parameters.len(); - let borrowed_type_parameters: &~[ty_param] = &type_parameters; - do self.with_type_parameter_rib(HasTypeParameters - (borrowed_type_parameters, id, 0u, - NormalRibKind)) { - - // Resolve the type parameters. - self.resolve_type_parameters(type_parameters, visitor); - - // Resolve the trait reference, if necessary. - let original_trait_refs = self.current_trait_refs; - if trait_references.len() >= 1 { - let mut new_trait_refs = @DVec(); - for trait_references.each |trait_reference| { - match self.resolve_path( - trait_reference.path, TypeNS, true, visitor) { - None => { - self.session.span_err(span, - ~"attempt to implement an \ - unknown trait"); - } - Some(def) => { - self.record_def(trait_reference.ref_id, def); - - // Record the current trait reference. - (*new_trait_refs).push(def_id_of_def(def)); - } - } - } - - // Record the current set of trait references. - self.current_trait_refs = Some(new_trait_refs); - } - - // Resolve the self type. - self.resolve_type(self_type, visitor); - - for methods.each |method| { - // We also need a new scope for the method-specific - // type parameters. - self.resolve_method(MethodRibKind(id, Provided(method.id)), - method, - outer_type_parameter_count, - visitor); -/* - let borrowed_type_parameters = &method.tps; - self.resolve_function(MethodRibKind(id, Provided(method.id)), - Some(@method.decl), - HasTypeParameters - (borrowed_type_parameters, - method.id, - outer_type_parameter_count, - NormalRibKind), - method.body, - HasSelfBinding(method.self_id), - NoCaptureClause, - visitor); -*/ - } - - // Restore the original trait references. - self.current_trait_refs = original_trait_refs; - } - } - - fn resolve_module(module_: _mod, span: span, _name: ident, id: node_id, - visitor: ResolveVisitor) { - - // Write the implementations in scope into the module metadata. - debug!("(resolving module) resolving module ID %d", id); - visit_mod(module_, span, id, (), visitor); - } - - fn resolve_local(local: @local, visitor: ResolveVisitor) { - let mut mutability; - if local.node.is_mutbl { - mutability = Mutable; - } else { - mutability = Immutable; - } - - // Resolve the type. - self.resolve_type(local.node.ty, visitor); - - // Resolve the initializer, if necessary. - match local.node.init { - None => { - // Nothing to do. - } - Some(initializer) => { - self.resolve_expr(initializer.expr, visitor); - } - } - - // Resolve the pattern. - self.resolve_pattern(local.node.pat, IrrefutableMode, mutability, - None, visitor); - } - - fn binding_mode_map(pat: @pat) -> BindingMap { - let result = uint_hash(); - do pat_bindings(self.def_map, pat) |binding_mode, _id, sp, path| { - let ident = path_to_ident(path); - result.insert(ident, - binding_info {span: sp, - binding_mode: binding_mode}); - } - return result; - } - - fn check_consistent_bindings(arm: arm) { - if arm.pats.len() == 0 { return; } - let map_0 = self.binding_mode_map(arm.pats[0]); - for arm.pats.eachi() |i, p: @pat| { - let map_i = self.binding_mode_map(p); - - for map_0.each |key, binding_0| { - match map_i.find(key) { - None => { - self.session.span_err( - p.span, - fmt!("variable `%s` from pattern #1 is \ - not bound in pattern #%u", - self.session.str_of(key), i + 1)); - } - Some(binding_i) => { - if binding_0.binding_mode != binding_i.binding_mode { - self.session.span_err( - binding_i.span, - fmt!("variable `%s` is bound with different \ - mode in pattern #%u than in pattern #1", - self.session.str_of(key), i + 1)); - } - } - } - } - - for map_i.each |key, binding| { - if !map_0.contains_key(key) { - self.session.span_err( - binding.span, - fmt!("variable `%s` from pattern #%u is \ - not bound in pattern #1", - self.session.str_of(key), i + 1)); - } - } - } - } - - fn resolve_arm(arm: arm, visitor: ResolveVisitor) { - (*self.value_ribs).push(@Rib(NormalRibKind)); - - let bindings_list = atom_hashmap(); - for arm.pats.each |pattern| { - self.resolve_pattern(pattern, RefutableMode, Immutable, - Some(bindings_list), visitor); - } - - // This has to happen *after* we determine which - // pat_idents are variants - self.check_consistent_bindings(arm); - - visit_expr_opt(arm.guard, (), visitor); - self.resolve_block(arm.body, visitor); - - (*self.value_ribs).pop(); - } - - fn resolve_block(block: blk, visitor: ResolveVisitor) { - debug!("(resolving block) entering block"); - (*self.value_ribs).push(@Rib(NormalRibKind)); - - // Move down in the graph, if there's an anonymous module rooted here. - let orig_module = self.current_module; - match self.current_module.anonymous_children.find(block.node.id) { - None => { /* Nothing to do. */ } - Some(anonymous_module) => { - debug!("(resolving block) found anonymous module, moving \ - down"); - self.current_module = anonymous_module; - } - } - - // Descend into the block. - visit_block(block, (), visitor); - - // Move back up. - self.current_module = orig_module; - - (*self.value_ribs).pop(); - debug!("(resolving block) leaving block"); - } - - fn resolve_type(ty: @ty, visitor: ResolveVisitor) { - match ty.node { - // Like path expressions, the interpretation of path types depends - // on whether the path has multiple elements in it or not. - - ty_path(path, path_id) => { - // This is a path in the type namespace. Walk through scopes - // scopes looking for it. - - let mut result_def; - match self.resolve_path(path, TypeNS, true, visitor) { - Some(def) => { - debug!("(resolving type) resolved `%s` to type", - self.session.str_of(path.idents.last())); - result_def = Some(def); - } - None => { - result_def = None; - } - } - - match result_def { - Some(_) => { - // Continue. - } - None => { - // Check to see whether the name is a primitive type. - if path.idents.len() == 1u { - let name = path.idents.last(); - - match self.primitive_type_table - .primitive_types - .find(name) { - - Some(primitive_type) => { - result_def = - Some(def_prim_ty(primitive_type)); - } - None => { - // Continue. - } - } - } - } - } - - match copy result_def { - Some(def) => { - // Write the result into the def map. - debug!("(resolving type) writing resolution for `%s` \ - (id %d)", - connect(path.idents.map( - |x| self.session.str_of(x)), ~"::"), - path_id); - self.record_def(path_id, def); - } - None => { - self.session.span_err - (ty.span, fmt!("use of undeclared type name `%s`", - connect(path.idents.map( - |x| self.session.str_of(x)), - ~"::"))); - } - } - } - - _ => { - // Just resolve embedded types. - visit_ty(ty, (), visitor); - } - } - } - - fn resolve_pattern(pattern: @pat, - mode: PatternBindingMode, - mutability: Mutability, - // Maps idents to the node ID for the (outermost) - // pattern that binds them - bindings_list: Option>, - visitor: ResolveVisitor) { - - let pat_id = pattern.id; - do walk_pat(pattern) |pattern| { - match pattern.node { - pat_ident(binding_mode, path, _) - if !path.global && path.idents.len() == 1u => { - - // The meaning of pat_ident with no type parameters - // depends on whether an enum variant with that name is in - // scope. The probing lookup has to be careful not to emit - // spurious errors. Only matching patterns (match) can - // match nullary variants. For binding patterns (let), - // matching such a variant is simply disallowed (since - // it's rarely what you want). - - let atom = path.idents[0]; - - match self.resolve_enum_variant_or_const(atom) { - FoundEnumVariant(def) if mode == RefutableMode => { - debug!("(resolving pattern) resolving `%s` to \ - enum variant", - self.session.str_of(atom)); - - self.record_def(pattern.id, def); - } - FoundEnumVariant(_) => { - self.session.span_err(pattern.span, - fmt!("declaration of `%s` \ - shadows an enum \ - that's in scope", - self.session - .str_of(atom))); - } - FoundConst => { - self.session.span_err(pattern.span, - ~"pattern variable \ - conflicts with a constant \ - in scope"); - } - EnumVariantOrConstNotFound => { - debug!("(resolving pattern) binding `%s`", - self.session.str_of(atom)); - - let is_mutable = mutability == Mutable; - - let def = match mode { - RefutableMode => { - // For pattern arms, we must use - // `def_binding` definitions. - - def_binding(pattern.id, binding_mode) - } - IrrefutableMode => { - // But for locals, we use `def_local`. - def_local(pattern.id, is_mutable) - } - }; - - // Record the definition so that later passes - // will be able to distinguish variants from - // locals in patterns. - - self.record_def(pattern.id, def); - - // Add the binding to the local ribs, if it - // doesn't already exist in the bindings list. (We - // must not add it if it's in the bindings list - // because that breaks the assumptions later - // passes make about or-patterns.) - - match bindings_list { - Some(bindings_list) - if !bindings_list.contains_key(atom) => { - let last_rib = (*self.value_ribs).last(); - last_rib.bindings.insert(atom, - dl_def(def)); - bindings_list.insert(atom, pat_id); - } - Some(b) => { - if b.find(atom) == Some(pat_id) { - // Then this is a duplicate variable - // in the same disjunct, which is an - // error - self.session.span_err(pattern.span, - fmt!("Identifier %s is bound more \ - than once in the same pattern", - path_to_str(path, self.session - .intr()))); - } - // Not bound in the same pattern: do nothing - } - None => { - let last_rib = (*self.value_ribs).last(); - last_rib.bindings.insert(atom, - dl_def(def)); - } - } - } - } - - // Check the types in the path pattern. - for path.types.each |ty| { - self.resolve_type(ty, visitor); - } - } - - pat_ident(_, path, _) | pat_enum(path, _) => { - // These two must be enum variants. - match self.resolve_path(path, ValueNS, false, visitor) { - Some(def @ def_variant(*)) => { - self.record_def(pattern.id, def); - } - Some(_) => { - self.session.span_err( - path.span, - fmt!("not an enum variant: %s", - self.session.str_of( - path.idents.last()))); - } - None => { - self.session.span_err(path.span, - ~"unresolved enum variant"); - } - } - - // Check the types in the path pattern. - for path.types.each |ty| { - self.resolve_type(ty, visitor); - } - } - - pat_lit(expr) => { - self.resolve_expr(expr, visitor); - } - - pat_range(first_expr, last_expr) => { - self.resolve_expr(first_expr, visitor); - self.resolve_expr(last_expr, visitor); - } - - pat_struct(path, _, _) => { - match self.resolve_path(path, TypeNS, false, visitor) { - Some(def_ty(class_id)) - if self.structs.contains_key(class_id) => { - let has_constructor = self.structs.get(class_id); - let class_def = def_class(class_id, - has_constructor); - self.record_def(pattern.id, class_def); - } - Some(definition @ def_variant(_, variant_id)) - if self.structs.contains_key(variant_id) => { - self.record_def(pattern.id, definition); - } - _ => { - self.session.span_err( - path.span, - fmt!("`%s` does not name a structure", - connect(path.idents.map( - |x| self.session.str_of(x)), - ~"::"))); - } - } - } - - _ => { - // Nothing to do. - } - } - } - } - - fn resolve_enum_variant_or_const(name: Atom) - -> EnumVariantOrConstResolution { - - match self.resolve_item_in_lexical_scope(self.current_module, - name, - ValueNS) { - - Success(target) => { - match target.bindings.value_def { - None => { - fail ~"resolved name in the value namespace to a set \ - of name bindings with no def?!"; - } - Some(def) => { - match def.def { - def @ def_variant(*) => { - return FoundEnumVariant(def); - } - def_const(*) => { - return FoundConst; - } - _ => { - return EnumVariantOrConstNotFound; - } - } - } - } - } - - Indeterminate => { - fail ~"unexpected indeterminate result"; - } - - Failed => { - return EnumVariantOrConstNotFound; - } - } - } - - /** - * If `check_ribs` is true, checks the local definitions first; i.e. - * doesn't skip straight to the containing module. - */ - fn resolve_path(path: @path, namespace: Namespace, check_ribs: bool, - visitor: ResolveVisitor) - -> Option { - - // First, resolve the types. - for path.types.each |ty| { - self.resolve_type(ty, visitor); - } - - if path.global { - return self.resolve_crate_relative_path(path, - self.xray_context, - namespace); - } - - if path.idents.len() > 1u { - return self.resolve_module_relative_path(path, - self.xray_context, - namespace); - } - - return self.resolve_identifier(path.idents.last(), - namespace, - check_ribs, - path.span); - } - - fn resolve_identifier(identifier: ident, - namespace: Namespace, - check_ribs: bool, - span: span) - -> Option { - - if check_ribs { - match self.resolve_identifier_in_local_ribs(identifier, - namespace, - span) { - Some(def) => { - return Some(def); - } - None => { - // Continue. - } - } - } - - return self.resolve_item_by_identifier_in_lexical_scope(identifier, - namespace); - } - - // XXX: Merge me with resolve_name_in_module? - fn resolve_definition_of_name_in_module(containing_module: @Module, - name: Atom, - namespace: Namespace, - xray: XrayFlag) - -> NameDefinition { - - if xray == NoXray && !self.name_is_exported(containing_module, name) { - debug!("(resolving definition of name in module) name `%s` is \ - unexported", - self.session.str_of(name)); - return NoNameDefinition; - } - - // First, search children. - match containing_module.children.find(name) { - Some(child_name_bindings) => { - match (*child_name_bindings).def_for_namespace(namespace) { - Some(def) if def.privacy == Public => { - // Found it. Stop the search here. - return ChildNameDefinition(def.def); - } - Some(_) | None => { - // Continue. - } - } - } - None => { - // Continue. - } - } - - // Next, search import resolutions. - match containing_module.import_resolutions.find(name) { - Some(import_resolution) => { - match (*import_resolution).target_for_namespace(namespace) { - Some(target) => { - match (*target.bindings) - .def_for_namespace(namespace) { - Some(def) if def.privacy == Public => { - // Found it. - import_resolution.used = true; - return ImportNameDefinition(def.def); - } - Some(_) | None => { - // This can happen with external impls, due to - // the imperfect way we read the metadata. - - return NoNameDefinition; - } - } - } - None => { - return NoNameDefinition; - } - } - } - None => { - return NoNameDefinition; - } - } - } - - fn intern_module_part_of_path(path: @path) -> @DVec { - let module_path_atoms = @DVec(); - for path.idents.eachi |index, ident| { - if index == path.idents.len() - 1u { - break; - } - - (*module_path_atoms).push(ident); - } - - return module_path_atoms; - } - - fn resolve_module_relative_path(path: @path, - +xray: XrayFlag, - namespace: Namespace) - -> Option { - - let module_path_atoms = self.intern_module_part_of_path(path); - - let mut containing_module; - match self.resolve_module_path_for_import(self.current_module, - module_path_atoms, - xray, - path.span) { - - Failed => { - self.session.span_err(path.span, - fmt!("use of undeclared module `%s`", - self.atoms_to_str( - (*module_path_atoms).get()))); - return None; - } - - Indeterminate => { - fail ~"indeterminate unexpected"; - } - - Success(resulting_module) => { - containing_module = resulting_module; - } - } - - let name = path.idents.last(); - match self.resolve_definition_of_name_in_module(containing_module, - name, - namespace, - xray) { - NoNameDefinition => { - // We failed to resolve the name. Report an error. - self.session.span_err( - path.span, - fmt!("unresolved name: %s::%s", - self.atoms_to_str((*module_path_atoms).get()), - self.session.str_of(name))); - return None; - } - ChildNameDefinition(def) | ImportNameDefinition(def) => { - return Some(def); - } - } - } - - fn resolve_crate_relative_path(path: @path, - +xray: XrayFlag, - namespace: Namespace) - -> Option { - - let module_path_atoms = self.intern_module_part_of_path(path); - - let root_module = (*self.graph_root).get_module(); - - let mut containing_module; - match self.resolve_module_path_from_root(root_module, - module_path_atoms, - 0u, - xray, - path.span) { - - Failed => { - self.session.span_err(path.span, - fmt!("use of undeclared module `::%s`", - self.atoms_to_str - ((*module_path_atoms).get()))); - return None; - } - - Indeterminate => { - fail ~"indeterminate unexpected"; - } - - Success(resulting_module) => { - containing_module = resulting_module; - } - } - - let name = path.idents.last(); - match self.resolve_definition_of_name_in_module(containing_module, - name, - namespace, - xray) { - NoNameDefinition => { - // We failed to resolve the name. Report an error. - self.session.span_err( - path.span, - fmt!("unresolved name: %s::%s", self.atoms_to_str( - (*module_path_atoms).get()), - self.session.str_of(name))); - return None; - } - ChildNameDefinition(def) | ImportNameDefinition(def) => { - return Some(def); - } - } - } - - fn resolve_identifier_in_local_ribs(ident: ident, - namespace: Namespace, - span: span) - -> Option { - // Check the local set of ribs. - let mut search_result; - match namespace { - ValueNS => { - search_result = self.search_ribs(self.value_ribs, ident, span, - DontAllowCapturingSelf); - } - TypeNS => { - search_result = self.search_ribs(self.type_ribs, ident, span, - AllowCapturingSelf); - } - ModuleNS => { - fail ~"module namespaces do not have local ribs"; - } - } - - match copy search_result { - Some(dl_def(def)) => { - debug!("(resolving path in local ribs) resolved `%s` to \ - local: %?", - self.session.str_of(ident), - def); - return Some(def); - } - Some(dl_field) | Some(dl_impl(_)) | None => { - return None; - } - } - } - - fn resolve_item_by_identifier_in_lexical_scope(ident: ident, - namespace: Namespace) - -> Option { - - // Check the items. - match self.resolve_item_in_lexical_scope(self.current_module, - ident, - namespace) { - - Success(target) => { - match (*target.bindings).def_for_namespace(namespace) { - None => { - fail ~"resolved name in a namespace to a set of name \ - bindings with no def for that namespace?!"; - } - Some(def) => { - debug!("(resolving item path in lexical scope) \ - resolved `%s` to item", - self.session.str_of(ident)); - return Some(def.def); - } - } - } - Indeterminate => { - fail ~"unexpected indeterminate result"; - } - Failed => { - return None; - } - } - } - - fn name_exists_in_scope_class(name: &str) -> bool { - let mut i = self.type_ribs.len(); - while i != 0 { - i -= 1; - let rib = self.type_ribs.get_elt(i); - match rib.kind { - MethodRibKind(node_id, _) => - for vec::each(self.crate.node.module.items) |item| { - if item.id == node_id { - match item.node { - item_class(class_def, _) => { - for vec::each(class_def.fields) |field| { - match field.node.kind { - syntax::ast::unnamed_field - => {}, - syntax::ast::named_field(ident, _, _) - => { - if str::eq_slice(self.session.str_of(ident), - name) { - return true - } - } - } - } - for vec::each(class_def.methods) |method| { - if str::eq_slice(self.session.str_of(method.ident), - name) { - return true - } - } - } - _ => {} - } - } - }, - _ => {} - } - } - return false; - } - - fn resolve_expr(expr: @expr, visitor: ResolveVisitor) { - // First, record candidate traits for this expression if it could - // result in the invocation of a method call. - - self.record_candidate_traits_for_expr_if_necessary(expr); - - // Next, resolve the node. - match expr.node { - // The interpretation of paths depends on whether the path has - // multiple elements in it or not. - - expr_path(path) => { - // This is a local path in the value namespace. Walk through - // scopes looking for it. - - match self.resolve_path(path, ValueNS, true, visitor) { - Some(def) => { - // Write the result into the def map. - debug!("(resolving expr) resolved `%s`", - connect(path.idents.map( - |x| self.session.str_of(x)), ~"::")); - self.record_def(expr.id, def); - } - None => { - let wrong_name = - connect(path.idents.map( - |x| self.session.str_of(x)), ~"::") ; - if self.name_exists_in_scope_class(wrong_name) { - self.session.span_err(expr.span, - fmt!("unresolved name: `%s`. \ - Did you mean: `self.%s`?", - wrong_name, - wrong_name)); - } - else { - self.session.span_err(expr.span, - fmt!("unresolved name: %s", - wrong_name)); - } - } - } - - visit_expr(expr, (), visitor); - } - - expr_fn(_, fn_decl, block, capture_clause) | - expr_fn_block(fn_decl, block, capture_clause) => { - self.resolve_function(FunctionRibKind(expr.id, block.node.id), - Some(@fn_decl), - NoTypeParameters, - block, - NoSelfBinding, - HasCaptureClause(capture_clause), - visitor); - } - - expr_struct(path, _, _) => { - // Resolve the path to the structure it goes to. - // - // XXX: We might want to support explicit type parameters in - // the path, in which case this gets a little more - // complicated: - // - // 1. Should we go through the ast_path_to_ty() path, which - // handles typedefs and the like? - // - // 2. If so, should programmers be able to write this? - // - // class Foo { ... } - // type Bar = Foo; - // let bar = Bar { ... } // no type parameters - - match self.resolve_path(path, TypeNS, false, visitor) { - Some(def_ty(class_id)) | Some(def_class(class_id, _)) - if self.structs.contains_key(class_id) => { - let has_constructor = self.structs.get(class_id); - let class_def = def_class(class_id, has_constructor); - self.record_def(expr.id, class_def); - } - Some(definition @ def_variant(_, class_id)) - if self.structs.contains_key(class_id) => { - self.record_def(expr.id, definition); - } - _ => { - self.session.span_err( - path.span, - fmt!("`%s` does not name a structure", - connect(path.idents.map( - |x| self.session.str_of(x)), - ~"::"))); - } - } - - visit_expr(expr, (), visitor); - } - - expr_loop(_, Some(label)) => { - do self.with_label_rib { - let def_like = dl_def(def_label(expr.id)); - self.label_ribs.last().bindings.insert(label, def_like); - - visit_expr(expr, (), visitor); - } - } - - expr_break(Some(label)) | expr_again(Some(label)) => { - match self.search_ribs(self.label_ribs, label, expr.span, - DontAllowCapturingSelf) { - None => - self.session.span_err(expr.span, - fmt!("use of undeclared label \ - `%s`", self.session.str_of( - label))), - Some(dl_def(def @ def_label(_))) => - self.record_def(expr.id, def), - Some(_) => - self.session.span_bug(expr.span, - ~"label wasn't mapped to a \ - label def!") - } - } - - _ => { - visit_expr(expr, (), visitor); - } - } - } - - fn record_candidate_traits_for_expr_if_necessary(expr: @expr) { - match expr.node { - expr_field(_, ident, _) => { - let traits = self.search_for_traits_containing_method(ident); - self.trait_map.insert(expr.id, traits); - } - expr_binary(add, _, _) | expr_assign_op(add, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.add_trait); - } - expr_binary(subtract, _, _) | expr_assign_op(subtract, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.sub_trait); - } - expr_binary(mul, _, _) | expr_assign_op(mul, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.mul_trait); - } - expr_binary(div, _, _) | expr_assign_op(div, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.div_trait); - } - expr_binary(rem, _, _) | expr_assign_op(rem, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.modulo_trait); - } - expr_binary(bitxor, _, _) | expr_assign_op(bitxor, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.bitxor_trait); - } - expr_binary(bitand, _, _) | expr_assign_op(bitand, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.bitand_trait); - } - expr_binary(bitor, _, _) | expr_assign_op(bitor, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.bitor_trait); - } - expr_binary(shl, _, _) | expr_assign_op(shl, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.shl_trait); - } - expr_binary(shr, _, _) | expr_assign_op(shr, _, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.shr_trait); - } - expr_unary(neg, _) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.neg_trait); - } - expr_index(*) => { - self.add_fixed_trait_for_expr(expr.id, - self.lang_items.index_trait); - } - _ => { - // Nothing to do. - } - } - } - - fn search_for_traits_containing_method(name: Atom) -> @DVec { - let found_traits = @DVec(); - let mut search_module = self.current_module; - loop { - // Look for the current trait. - match copy self.current_trait_refs { - Some(trait_def_ids) => { - for trait_def_ids.each |trait_def_id| { - self.add_trait_info_if_containing_method - (found_traits, trait_def_id, name); - } - } - None => { - // Nothing to do. - } - } - - // Look for trait children. - for search_module.children.each |_name, child_name_bindings| { - match child_name_bindings.def_for_namespace(TypeNS) { - Some(def) => { - match def.def { - def_ty(trait_def_id) => { - self.add_trait_info_if_containing_method - (found_traits, trait_def_id, name); - } - _ => { - // Continue. - } - } - } - None => { - // Continue. - } - } - } - - // Look for imports. - for search_module.import_resolutions.each - |_atom, import_resolution| { - - match import_resolution.target_for_namespace(TypeNS) { - None => { - // Continue. - } - Some(target) => { - match target.bindings.def_for_namespace(TypeNS) { - Some(def) => { - match def.def { - def_ty(trait_def_id) => { - self. - add_trait_info_if_containing_method - (found_traits, trait_def_id, name); - } - _ => { - // Continue. - } - } - } - None => { - // Continue. - } - } - } - } - } - - // Move to the next parent. - match search_module.parent_link { - NoParentLink => { - // Done. - break; - } - ModuleParentLink(parent_module, _) | - BlockParentLink(parent_module, _) => { - search_module = parent_module; - } - } - } - - return found_traits; - } - - fn add_trait_info_if_containing_method(found_traits: @DVec, - trait_def_id: def_id, - name: Atom) { - - match self.trait_info.find(trait_def_id) { - Some(trait_info) if trait_info.contains_key(name) => { - debug!("(adding trait info if containing method) found trait \ - %d:%d for method '%s'", - trait_def_id.crate, - trait_def_id.node, - self.session.str_of(name)); - (*found_traits).push(trait_def_id); - } - Some(_) | None => { - // Continue. - } - } - } - - fn add_fixed_trait_for_expr(expr_id: node_id, +trait_id: Option) { - let traits = @DVec(); - traits.push(trait_id.get()); - self.trait_map.insert(expr_id, traits); - } - - fn record_def(node_id: node_id, def: def) { - debug!("(recording def) recording %? for %?", def, node_id); - self.def_map.insert(node_id, def); - } - - // - // Unused import checking - // - // Although this is a lint pass, it lives in here because it depends on - // resolve data structures. - // - - fn check_for_unused_imports_if_necessary() { - if self.unused_import_lint_level == allow { - return; - } - - let root_module = (*self.graph_root).get_module(); - self.check_for_unused_imports_in_module_subtree(root_module); - } - - fn check_for_unused_imports_in_module_subtree(module_: @Module) { - // If this isn't a local crate, then bail out. We don't need to check - // for unused imports in external crates. - - match module_.def_id { - Some(def_id) if def_id.crate == local_crate => { - // OK. Continue. - } - None => { - // Check for unused imports in the root module. - } - Some(_) => { - // Bail out. - debug!("(checking for unused imports in module subtree) not \ - checking for unused imports for `%s`", - self.module_to_str(module_)); - return; - } - } - - self.check_for_unused_imports_in_module(module_); - - for module_.children.each |_atom, child_name_bindings| { - match (*child_name_bindings).get_module_if_available() { - None => { - // Nothing to do. - } - Some(child_module) => { - self.check_for_unused_imports_in_module_subtree - (child_module); - } - } - } - - for module_.anonymous_children.each |_node_id, child_module| { - self.check_for_unused_imports_in_module_subtree(child_module); - } - } - - fn check_for_unused_imports_in_module(module_: @Module) { - for module_.import_resolutions.each |_name, import_resolution| { - if !import_resolution.used { - match self.unused_import_lint_level { - warn => { - self.session.span_warn(import_resolution.span, - ~"unused import"); - } - deny | forbid => { - self.session.span_err(import_resolution.span, - ~"unused import"); - } - allow => { - self.session.span_bug(import_resolution.span, - ~"shouldn't be here if lint \ - is allowed"); - } - } - } - } - } - - - // - // Diagnostics - // - // Diagnostics are not particularly efficient, because they're rarely - // hit. - // - - /// A somewhat inefficient routine to print out the name of a module. - fn module_to_str(module_: @Module) -> ~str { - let atoms = DVec(); - let mut current_module = module_; - loop { - match current_module.parent_link { - NoParentLink => { - break; - } - ModuleParentLink(module_, name) => { - atoms.push(name); - current_module = module_; - } - BlockParentLink(module_, _) => { - atoms.push(syntax::parse::token::special_idents::opaque); - current_module = module_; - } - } - } - - if atoms.len() == 0u { - return ~"???"; - } - - let mut string = ~""; - let mut i = atoms.len() - 1u; - loop { - if i < atoms.len() - 1u { - string += ~"::"; - } - string += self.session.str_of(atoms.get_elt(i)); - - if i == 0u { - break; - } - i -= 1u; - } - - return string; - } - - fn dump_module(module_: @Module) { - debug!("Dump of module `%s`:", self.module_to_str(module_)); - - debug!("Children:"); - for module_.children.each |name, _child| { - debug!("* %s", self.session.str_of(name)); - } - - debug!("Import resolutions:"); - for module_.import_resolutions.each |name, import_resolution| { - let mut module_repr; - match (*import_resolution).target_for_namespace(ModuleNS) { - None => { module_repr = ~""; } - Some(_) => { - module_repr = ~" module:?"; - // XXX - } - } - - let mut value_repr; - match (*import_resolution).target_for_namespace(ValueNS) { - None => { value_repr = ~""; } - Some(_) => { - value_repr = ~" value:?"; - // XXX - } - } - - let mut type_repr; - match (*import_resolution).target_for_namespace(TypeNS) { - None => { type_repr = ~""; } - Some(_) => { - type_repr = ~" type:?"; - // XXX - } - } - - debug!("* %s:%s%s%s", - self.session.str_of(name), - module_repr, value_repr, type_repr); - } - } -} - -/// Entry point to crate resolution. -fn resolve_crate(session: session, lang_items: LanguageItems, crate: @crate) - -> { def_map: DefMap, - exp_map: ExportMap, - exp_map2: ExportMap2, - trait_map: TraitMap } { - - let resolver = @Resolver(session, lang_items, crate); - resolver.resolve(resolver); - return { - def_map: resolver.def_map, - exp_map: resolver.export_map, - exp_map2: resolver.export_map2, - trait_map: resolver.trait_map - }; -} - diff --git a/src/rustc/middle/trans/alt.rs b/src/rustc/middle/trans/alt.rs index 4a610799fff..134e25da11e 100644 --- a/src/rustc/middle/trans/alt.rs +++ b/src/rustc/middle/trans/alt.rs @@ -10,7 +10,7 @@ import syntax::ast_util::{dummy_sp, path_to_ident}; import syntax::ast::def_id; import syntax::codemap::span; import syntax::print::pprust::pat_to_str; -import middle::resolve3::DefMap; +import middle::resolve::DefMap; import back::abi; import std::map::hashmap; import dvec::DVec; diff --git a/src/rustc/middle/trans/base.rs b/src/rustc/middle/trans/base.rs index 5afab464748..a25b5e28410 100644 --- a/src/rustc/middle/trans/base.rs +++ b/src/rustc/middle/trans/base.rs @@ -5868,8 +5868,8 @@ fn trans_crate(sess: session::session, crate: @ast::crate, tcx: ty::ctxt, output: &Path, - emap: resolve3::ExportMap, - emap2: resolve3::ExportMap2, + emap: resolve::ExportMap, + emap2: resolve::ExportMap2, maps: astencode::maps) -> (ModuleRef, link_meta) { diff --git a/src/rustc/middle/trans/common.rs b/src/rustc/middle/trans/common.rs index 1a205929e5c..2f66da09a78 100644 --- a/src/rustc/middle/trans/common.rs +++ b/src/rustc/middle/trans/common.rs @@ -107,8 +107,8 @@ type crate_ctxt = { externs: hashmap<~str, ValueRef>, intrinsics: hashmap<~str, ValueRef>, item_vals: hashmap, - exp_map: resolve3::ExportMap, - exp_map2: resolve3::ExportMap2, + exp_map: resolve::ExportMap, + exp_map2: resolve::ExportMap2, reachable: reachable::map, item_symbols: hashmap, mut main_fn: Option, diff --git a/src/rustc/middle/trans/reachable.rs b/src/rustc/middle/trans/reachable.rs index 319a2f5db7d..b252351cd98 100644 --- a/src/rustc/middle/trans/reachable.rs +++ b/src/rustc/middle/trans/reachable.rs @@ -17,12 +17,12 @@ export map, find_reachable; type map = std::map::hashmap; -type ctx = {exp_map: resolve3::ExportMap, +type ctx = {exp_map: resolve::ExportMap, tcx: ty::ctxt, method_map: typeck::method_map, rmap: map}; -fn find_reachable(crate_mod: _mod, exp_map: resolve3::ExportMap, +fn find_reachable(crate_mod: _mod, exp_map: resolve::ExportMap, tcx: ty::ctxt, method_map: typeck::method_map) -> map { let rmap = std::map::int_hash(); let cx = {exp_map: exp_map, tcx: tcx, method_map: method_map, rmap: rmap}; diff --git a/src/rustc/middle/ty.rs b/src/rustc/middle/ty.rs index 7666672406a..18d54dbf5d8 100644 --- a/src/rustc/middle/ty.rs +++ b/src/rustc/middle/ty.rs @@ -253,7 +253,7 @@ type ctxt = vecs_implicitly_copyable: bool, cstore: metadata::cstore::cstore, sess: session::session, - def_map: resolve3::DefMap, + def_map: resolve::DefMap, region_map: middle::region::region_map, region_paramd_items: middle::region::region_paramd_items, @@ -603,7 +603,7 @@ fn new_ty_hash() -> map::hashmap { } fn mk_ctxt(s: session::session, - dm: resolve3::DefMap, + dm: resolve::DefMap, amap: ast_map::map, freevars: freevars::freevar_map, region_map: middle::region::region_map, diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs index 51c152f3948..1fa619a1ca3 100644 --- a/src/rustc/middle/typeck.rs +++ b/src/rustc/middle/typeck.rs @@ -157,13 +157,13 @@ type vtable_map = hashmap; // Maps from a trait's def_id to a MethodInfo about // that method in that trait. type provided_methods_map = hashmap; + ~[@resolve::MethodInfo]>; type ty_param_substs_and_ty = {substs: ty::substs, ty: ty::t}; type crate_ctxt_ = {// A mapping from method call sites to traits that have // that method. - trait_map: resolve3::TraitMap, + trait_map: resolve::TraitMap, method_map: method_map, vtable_map: vtable_map, coherence_info: @coherence::CoherenceInfo, @@ -301,7 +301,7 @@ fn check_for_main_fn(ccx: @crate_ctxt) { } fn check_crate(tcx: ty::ctxt, - trait_map: resolve3::TraitMap, + trait_map: resolve::TraitMap, crate: @ast::crate) -> (method_map, vtable_map) { diff --git a/src/rustc/middle/typeck/check/method.rs b/src/rustc/middle/typeck/check/method.rs index fb4d2565c44..bb90bcaea01 100644 --- a/src/rustc/middle/typeck/check/method.rs +++ b/src/rustc/middle/typeck/check/method.rs @@ -1,7 +1,7 @@ /* Code to handle method lookups (which can be quite complex) */ import coherence::get_base_type_def_id; -import middle::resolve3::{Impl, MethodInfo}; +import middle::resolve::{Impl, MethodInfo}; import middle::ty::{mk_box, mk_rptr, mk_uniq}; import syntax::ast::{def_id, sty_static, sty_box, sty_by_ref, sty_region, sty_uniq}; @@ -462,7 +462,7 @@ struct lookup { } // Returns true if any were added and false otherwise. - fn add_candidates_from_impl(im: @resolve3::Impl, mode: method_lookup_mode) + fn add_candidates_from_impl(im: @resolve::Impl, mode: method_lookup_mode) -> bool { let mut added_any = false; diff --git a/src/rustc/middle/typeck/coherence.rs b/src/rustc/middle/typeck/coherence.rs index 0c89b0abe11..8076da7c971 100644 --- a/src/rustc/middle/typeck/coherence.rs +++ b/src/rustc/middle/typeck/coherence.rs @@ -7,7 +7,7 @@ import metadata::csearch::{each_path, get_impl_traits, get_impls_for_mod}; import metadata::cstore::{cstore, iter_crate_data}; import metadata::decoder::{dl_def, dl_field, dl_impl}; -import middle::resolve3::{Impl, MethodInfo}; +import middle::resolve::{Impl, MethodInfo}; import middle::ty::{get, lookup_item_type, subst, t, ty_box}; import middle::ty::{ty_uniq, ty_ptr, ty_rptr, ty_enum}; import middle::ty::{ty_class, ty_nil, ty_bot, ty_bool, ty_int, ty_uint}; diff --git a/src/rustc/rustc.rc b/src/rustc/rustc.rc index fd6e86c5b8c..ce77613da06 100644 --- a/src/rustc/rustc.rc +++ b/src/rustc/rustc.rc @@ -53,7 +53,7 @@ mod middle { mod reachable; } mod ty; - mod resolve3; + mod resolve; mod typeck { mod check { mod alt; -- cgit 1.4.1-3-g733a5