]> git.lizzy.rs Git - rust.git/blob - src/librustc/middle/resolve.rs
e67734179476a1c711d7f631401fee9560d3ee78
[rust.git] / src / librustc / middle / resolve.rs
1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 use core::prelude::*;
12
13 use driver::session;
14 use driver::session::Session;
15 use metadata::csearch::{each_path, get_method_names_if_trait};
16 use metadata::csearch::{get_static_methods_if_impl, get_struct_fields};
17 use metadata::csearch::{get_type_name_if_impl};
18 use metadata::cstore::find_extern_mod_stmt_cnum;
19 use metadata::decoder::{def_like, dl_def, dl_field, dl_impl};
20 use middle::lang_items::LanguageItems;
21 use middle::lint::{deny, allow, forbid, level, unused_imports, warn};
22 use middle::pat_util::{pat_bindings};
23
24 use core::cmp;
25 use core::str;
26 use core::vec;
27 use syntax::ast::{RegionTyParamBound, TraitTyParamBound, _mod, add, arm};
28 use syntax::ast::{binding_mode, bitand, bitor, bitxor, blk};
29 use syntax::ast::{bind_infer, bind_by_ref, bind_by_copy};
30 use syntax::ast::{crate, crate_num, decl_item, def, def_arg, def_binding};
31 use syntax::ast::{def_const, def_foreign_mod, def_fn, def_id, def_label};
32 use syntax::ast::{def_local, def_mod, def_prim_ty, def_region, def_self};
33 use syntax::ast::{def_self_ty, def_static_method, def_struct, def_ty};
34 use syntax::ast::{def_ty_param, def_typaram_binder};
35 use syntax::ast::{def_upvar, def_use, def_variant, expr, expr_assign_op};
36 use syntax::ast::{expr_binary, expr_break, expr_cast, expr_field, expr_fn};
37 use syntax::ast::{expr_fn_block, expr_index, expr_method_call, expr_path};
38 use syntax::ast::{def_prim_ty, def_region, def_self, def_ty, def_ty_param};
39 use syntax::ast::{def_upvar, def_use, def_variant, div, eq};
40 use syntax::ast::{enum_variant_kind, expr, expr_again, expr_assign_op};
41 use syntax::ast::{expr_fn_block, expr_index, expr_loop};
42 use syntax::ast::{expr_path, expr_struct, expr_unary, fn_decl};
43 use syntax::ast::{foreign_item, foreign_item_const, foreign_item_fn, ge};
44 use syntax::ast::{gt, ident, impure_fn, inherited, item, item_struct};
45 use syntax::ast::{item_const, item_enum, item_fn, item_foreign_mod};
46 use syntax::ast::{item_impl, item_mac, item_mod, item_trait, item_ty, le};
47 use syntax::ast::{local, local_crate, lt, method, mode, module_ns, mul};
48 use syntax::ast::{named_field, ne, neg, node_id, pat, pat_enum, pat_ident};
49 use syntax::ast::{path, pat_box, pat_lit, pat_range, pat_rec, pat_struct};
50 use syntax::ast::{pat_tup, pat_uniq, pat_wild, prim_ty, private, provided};
51 use syntax::ast::{public, required, rem, self_ty_, shl, shr, stmt_decl};
52 use syntax::ast::{struct_dtor, struct_field, struct_variant_kind, sty_by_ref};
53 use syntax::ast::{sty_static, subtract, trait_ref, tuple_variant_kind, Ty};
54 use syntax::ast::{ty_bool, ty_char, ty_f, ty_f32, ty_f64, ty_float, ty_i};
55 use syntax::ast::{ty_i16, ty_i32, ty_i64, ty_i8, ty_int, ty_param, ty_path};
56 use syntax::ast::{ty_str, ty_u, ty_u16, ty_u32, ty_u64, ty_u8, ty_uint};
57 use syntax::ast::{type_value_ns, ty_param_bound, unnamed_field};
58 use syntax::ast::{variant, view_item, view_item_extern_mod};
59 use syntax::ast::{view_item_use, view_path_glob, view_path_list};
60 use syntax::ast::{view_path_simple, visibility, anonymous, named, not};
61 use syntax::ast::{unsafe_fn};
62 use syntax::ast_util::{def_id_of_def, local_def};
63 use syntax::ast_util::{path_to_ident, walk_pat, trait_method_to_ty_method};
64 use syntax::ast_util::{Privacy, Public, Private};
65 use syntax::ast_util::{variant_visibility_to_privacy, visibility_to_privacy};
66 use syntax::attr::{attr_metas, contains_name, attrs_contains_name};
67 use syntax::parse::token::ident_interner;
68 use syntax::parse::token::special_idents;
69 use syntax::print::pprust::{pat_to_str, path_to_str};
70 use syntax::codemap::{span, dummy_sp};
71 use syntax::visit::{default_visitor, fk_method, mk_vt, Visitor, visit_block};
72 use syntax::visit::{visit_crate, visit_expr, visit_expr_opt, visit_fn};
73 use syntax::visit::{visit_foreign_item, visit_item, visit_method_helper};
74 use syntax::visit::{visit_mod, visit_ty, vt};
75
76 use managed::ptr_eq;
77 use dvec::DVec;
78 use option::{Some, get, is_some, is_none};
79 use str::{connect, split_str};
80 use vec::pop;
81
82 use std::list::{Cons, List, Nil};
83 use std::oldmap::HashMap;
84 use str_eq = str::eq;
85
86 // Definition mapping
87 pub type DefMap = HashMap<node_id,def>;
88
89 pub struct binding_info {
90     span: span,
91     binding_mode: binding_mode,
92 }
93
94 // Map from the name in a pattern to its binding mode.
95 pub type BindingMap = HashMap<ident,binding_info>;
96
97 // Implementation resolution
98 //
99 // FIXME #4946: This kind of duplicates information kept in
100 // ty::method. Maybe it should go away.
101
102 pub type MethodInfo = {
103     did: def_id,
104     n_tps: uint,
105     ident: ident,
106     self_type: self_ty_
107 };
108
109 pub type Impl = { did: def_id, ident: ident, methods: ~[@MethodInfo] };
110
111 // Trait method resolution
112 pub type TraitMap = @HashMap<node_id,@DVec<def_id>>;
113
114 // This is the replacement export map. It maps a module to all of the exports
115 // within.
116 pub type ExportMap2 = HashMap<node_id, ~[Export2]>;
117
118 pub struct Export2 {
119     name: ~str,         // The name of the target.
120     def_id: def_id,     // The definition of the target.
121     reexport: bool,     // Whether this is a reexport.
122 }
123
124 #[deriving_eq]
125 pub enum PatternBindingMode {
126     RefutableMode,
127     LocalIrrefutableMode,
128     ArgumentIrrefutableMode(mode)
129 }
130
131 pub enum Namespace {
132     TypeNS,
133     ValueNS
134 }
135
136 /// A NamespaceResult represents the result of resolving an import in
137 /// a particular namespace. The result is either definitely-resolved,
138 /// definitely- unresolved, or unknown.
139 pub enum NamespaceResult {
140     /// Means that resolve hasn't gathered enough information yet to determine
141     /// whether the name is bound in this namespace. (That is, it hasn't
142     /// resolved all `use` directives yet.)
143     UnknownResult,
144     /// Means that resolve has determined that the name is definitely
145     /// not bound in the namespace.
146     UnboundResult,
147     /// Means that resolve has determined that the name is bound in the Module
148     /// argument, and specified by the NameBindings argument.
149     BoundResult(@Module, @mut NameBindings)
150 }
151
152 pub impl NamespaceResult {
153     pure fn is_unknown() -> bool {
154         match self {
155             UnknownResult => true,
156             _ => false
157         }
158     }
159 }
160
161 pub enum NameDefinition {
162     NoNameDefinition,           //< The name was unbound.
163     ChildNameDefinition(def),   //< The name identifies an immediate child.
164     ImportNameDefinition(def)   //< The name identifies an import.
165
166 }
167
168 #[deriving_eq]
169 pub enum Mutability {
170     Mutable,
171     Immutable
172 }
173
174 pub enum SelfBinding {
175     NoSelfBinding,
176     HasSelfBinding(node_id, bool /* is implicit */)
177 }
178
179 pub type ResolveVisitor = vt<()>;
180
181 #[deriving_eq]
182 pub enum ImportDirectiveNS {
183     TypeNSOnly,
184     AnyNS
185 }
186
187 /// Contains data for specific types of import directives.
188 pub enum ImportDirectiveSubclass {
189     SingleImport(ident /* target */, ident /* source */, ImportDirectiveNS),
190     GlobImport
191 }
192
193 /// The context that we thread through while building the reduced graph.
194 pub enum ReducedGraphParent {
195     ModuleReducedGraphParent(@Module)
196 }
197
198 pub enum ResolveResult<T> {
199     Failed,         // Failed to resolve the name.
200     Indeterminate,  // Couldn't determine due to unresolved globs.
201     Success(T)      // Successfully resolved the import.
202 }
203
204 pub impl<T> ResolveResult<T> {
205     fn failed() -> bool {
206         match self { Failed => true, _ => false }
207     }
208     fn indeterminate() -> bool {
209         match self { Indeterminate => true, _ => false }
210     }
211 }
212
213 pub enum TypeParameters/& {
214     NoTypeParameters,               //< No type parameters.
215     HasTypeParameters(&~[ty_param], //< Type parameters.
216                       node_id,      //< ID of the enclosing item
217
218                       // The index to start numbering the type parameters at.
219                       // This is zero if this is the outermost set of type
220                       // parameters, or equal to the number of outer type
221                       // parameters. For example, if we have:
222                       //
223                       //   impl I<T> {
224                       //     fn method<U>() { ... }
225                       //   }
226                       //
227                       // The index at the method site will be 1, because the
228                       // outer T had index 0.
229
230                       uint,
231
232                       // The kind of the rib used for type parameters.
233                       RibKind)
234 }
235
236 // The rib kind controls the translation of argument or local definitions
237 // (`def_arg` or `def_local`) to upvars (`def_upvar`).
238
239 pub enum RibKind {
240     // No translation needs to be applied.
241     NormalRibKind,
242
243     // We passed through a function scope at the given node ID. Translate
244     // upvars as appropriate.
245     FunctionRibKind(node_id /* func id */, node_id /* body id */),
246
247     // We passed through an impl or trait and are now in one of its
248     // methods. Allow references to ty params that that impl or trait
249     // binds. Disallow any other upvars (including other ty params that are
250     // upvars).
251               // parent;   method itself
252     MethodRibKind(node_id, MethodSort),
253
254     // We passed through a function *item* scope. Disallow upvars.
255     OpaqueFunctionRibKind,
256
257     // We're in a constant item. Can't refer to dynamic stuff.
258     ConstantItemRibKind
259 }
260
261 // Methods can be required or provided. Required methods only occur in traits.
262 pub enum MethodSort {
263     Required,
264     Provided(node_id)
265 }
266
267 // The X-ray flag indicates that a context has the X-ray privilege, which
268 // allows it to reference private names. Currently, this is used for the test
269 // runner.
270 //
271 // FIXME #4947: The X-ray flag is kind of questionable in the first
272 // place. It might be better to introduce an expr_xray_path instead.
273
274 #[deriving_eq]
275 pub enum XrayFlag {
276     NoXray,     //< Private items cannot be accessed.
277     Xray        //< Private items can be accessed.
278 }
279
280 pub enum UseLexicalScopeFlag {
281     DontUseLexicalScope,
282     UseLexicalScope
283 }
284
285 pub enum SearchThroughModulesFlag {
286     DontSearchThroughModules,
287     SearchThroughModules
288 }
289
290 pub enum ModulePrefixResult {
291     NoPrefixFound,
292     PrefixFound(@Module, uint)
293 }
294
295 #[deriving_eq]
296 pub enum AllowCapturingSelfFlag {
297     AllowCapturingSelf,         //< The "self" definition can be captured.
298     DontAllowCapturingSelf,     //< The "self" definition cannot be captured.
299 }
300
301 pub enum BareIdentifierPatternResolution {
302     FoundStructOrEnumVariant(def),
303     FoundConst(def),
304     BareIdentifierPatternUnresolved
305 }
306
307 // Specifies how duplicates should be handled when adding a child item if
308 // another item exists with the same name in some namespace.
309 #[deriving_eq]
310 pub enum DuplicateCheckingMode {
311     ForbidDuplicateModules,
312     ForbidDuplicateTypes,
313     ForbidDuplicateValues,
314     ForbidDuplicateTypesAndValues,
315     OverwriteDuplicates
316 }
317
318 // Returns the namespace associated with the given duplicate checking mode,
319 // or fails for OverwriteDuplicates. This is used for error messages.
320 pub fn namespace_for_duplicate_checking_mode(mode: DuplicateCheckingMode)
321                                           -> Namespace {
322     match mode {
323         ForbidDuplicateModules | ForbidDuplicateTypes |
324         ForbidDuplicateTypesAndValues => TypeNS,
325         ForbidDuplicateValues => ValueNS,
326         OverwriteDuplicates => fail!(~"OverwriteDuplicates has no namespace")
327     }
328 }
329
330 /// One local scope.
331 pub struct Rib {
332     bindings: HashMap<ident,def_like>,
333     kind: RibKind,
334 }
335
336 pub fn Rib(kind: RibKind) -> Rib {
337     Rib {
338         bindings: HashMap(),
339         kind: kind
340     }
341 }
342
343
344 /// One import directive.
345 pub struct ImportDirective {
346     privacy: Privacy,
347     module_path: @DVec<ident>,
348     subclass: @ImportDirectiveSubclass,
349     span: span,
350 }
351
352 pub fn ImportDirective(privacy: Privacy,
353                        module_path: @DVec<ident>,
354                        subclass: @ImportDirectiveSubclass,
355                        span: span)
356                     -> ImportDirective {
357     ImportDirective {
358         privacy: privacy,
359         module_path: module_path,
360         subclass: subclass,
361         span: span
362     }
363 }
364
365 /// The item that an import resolves to.
366 pub struct Target {
367     target_module: @Module,
368     bindings: @mut NameBindings,
369 }
370
371 pub fn Target(target_module: @Module, bindings: @mut NameBindings) -> Target {
372     Target {
373         target_module: target_module,
374         bindings: bindings
375     }
376 }
377
378 /// An ImportResolution represents a particular `use` directive.
379 pub struct ImportResolution {
380     /// The privacy of this `use` directive (whether it's `use` or
381     /// `pub use`.
382     privacy: Privacy,
383     span: span,
384
385     // The number of outstanding references to this name. When this reaches
386     // zero, outside modules can count on the targets being correct. Before
387     // then, all bets are off; future imports could override this name.
388
389     outstanding_references: uint,
390
391     /// The value that this `use` directive names, if there is one.
392     value_target: Option<Target>,
393     /// The type that this `use` directive names, if there is one.
394     type_target: Option<Target>,
395
396     /// There exists one state per import statement
397     state: @mut ImportState,
398 }
399
400 pub fn ImportResolution(privacy: Privacy,
401                         +span: span,
402                         state: @mut ImportState) -> ImportResolution {
403     ImportResolution {
404         privacy: privacy,
405         span: span,
406         outstanding_references: 0,
407         value_target: None,
408         type_target: None,
409         state: state,
410     }
411 }
412
413 pub impl ImportResolution {
414     fn target_for_namespace(namespace: Namespace) -> Option<Target> {
415         match namespace {
416             TypeNS      => return copy self.type_target,
417             ValueNS     => return copy self.value_target
418         }
419     }
420 }
421
422 pub struct ImportState {
423     used: bool,
424     warned: bool
425 }
426
427 pub fn ImportState() -> ImportState {
428     ImportState{ used: false, warned: false }
429 }
430
431 /// The link from a module up to its nearest parent node.
432 pub enum ParentLink {
433     NoParentLink,
434     ModuleParentLink(@Module, ident),
435     BlockParentLink(@Module, node_id)
436 }
437
438 /// The type of module this is.
439 pub enum ModuleKind {
440     NormalModuleKind,
441     ExternModuleKind,
442     TraitModuleKind,
443     AnonymousModuleKind,
444 }
445
446 /// One node in the tree of modules.
447 pub struct Module {
448     parent_link: ParentLink,
449     mut def_id: Option<def_id>,
450     kind: ModuleKind,
451
452     children: HashMap<ident,@mut NameBindings>,
453     imports: DVec<@ImportDirective>,
454
455     // The anonymous children of this node. Anonymous children are pseudo-
456     // modules that are implicitly created around items contained within
457     // blocks.
458     //
459     // For example, if we have this:
460     //
461     //  fn f() {
462     //      fn g() {
463     //          ...
464     //      }
465     //  }
466     //
467     // There will be an anonymous module created around `g` with the ID of the
468     // entry block for `f`.
469
470     anonymous_children: HashMap<node_id,@Module>,
471
472     // The status of resolving each import in this module.
473     import_resolutions: HashMap<ident,@mut ImportResolution>,
474
475     // The number of unresolved globs that this module exports.
476     mut glob_count: uint,
477
478     // The index of the import we're resolving.
479     mut resolved_import_count: uint,
480 }
481
482 pub fn Module(parent_link: ParentLink,
483               def_id: Option<def_id>,
484               kind: ModuleKind)
485            -> Module {
486     Module {
487         parent_link: parent_link,
488         def_id: def_id,
489         kind: kind,
490         children: HashMap(),
491         imports: DVec(),
492         anonymous_children: HashMap(),
493         import_resolutions: HashMap(),
494         glob_count: 0,
495         resolved_import_count: 0
496     }
497 }
498
499 pub impl Module {
500     fn all_imports_resolved() -> bool {
501         return self.imports.len() == self.resolved_import_count;
502     }
503 }
504
505 pub fn unused_import_lint_level(session: Session) -> level {
506     for session.opts.lint_opts.each |lint_option_pair| {
507         let (lint_type, lint_level) = *lint_option_pair;
508         if lint_type == unused_imports {
509             return lint_level;
510         }
511     }
512     return allow;
513 }
514
515 // Records a possibly-private type definition.
516 pub struct TypeNsDef {
517     privacy: Privacy,
518     module_def: Option<@Module>,
519     type_def: Option<def>
520 }
521
522 // Records a possibly-private value definition.
523 pub struct ValueNsDef {
524     privacy: Privacy,
525     def: def,
526 }
527
528 // Records the definitions (at most one for each namespace) that a name is
529 // bound to.
530 pub struct NameBindings {
531     type_def: Option<TypeNsDef>,    //< Meaning in type namespace.
532     value_def: Option<ValueNsDef>,  //< Meaning in value namespace.
533
534     // For error reporting
535     // FIXME (#3783): Merge me into TypeNsDef and ValueNsDef.
536     type_span: Option<span>,
537     value_span: Option<span>,
538 }
539
540 pub impl NameBindings {
541     /// Creates a new module in this set of name bindings.
542     fn define_module(@mut self,
543                      privacy: Privacy,
544                      parent_link: ParentLink,
545                      def_id: Option<def_id>,
546                      kind: ModuleKind,
547                      sp: span) {
548         // Merges the module with the existing type def or creates a new one.
549         let module_ = @Module(parent_link, def_id, kind);
550         match self.type_def {
551             None => {
552                 self.type_def = Some(TypeNsDef {
553                     privacy: privacy,
554                     module_def: Some(module_),
555                     type_def: None
556                 });
557             }
558             Some(copy type_def) => {
559                 self.type_def = Some(TypeNsDef {
560                     privacy: privacy,
561                     module_def: Some(module_),
562                     .. type_def
563                 });
564             }
565         }
566         self.type_span = Some(sp);
567     }
568
569     /// Records a type definition.
570     fn define_type(@mut self, privacy: Privacy, def: def, sp: span) {
571         // Merges the type with the existing type def or creates a new one.
572         match self.type_def {
573             None => {
574                 self.type_def = Some(TypeNsDef {
575                     privacy: privacy,
576                     module_def: None,
577                     type_def: Some(def)
578                 });
579             }
580             Some(copy type_def) => {
581                 self.type_def = Some(TypeNsDef {
582                     privacy: privacy,
583                     type_def: Some(def),
584                     .. type_def
585                 });
586             }
587         }
588         self.type_span = Some(sp);
589     }
590
591     /// Records a value definition.
592     fn define_value(@mut self, privacy: Privacy, def: def, sp: span) {
593         self.value_def = Some(ValueNsDef { privacy: privacy, def: def });
594         self.value_span = Some(sp);
595     }
596
597     /// Returns the module node if applicable.
598     fn get_module_if_available() -> Option<@Module> {
599         match self.type_def {
600             Some(ref type_def) => (*type_def).module_def,
601             None => None
602         }
603     }
604
605     /**
606      * Returns the module node. Fails if this node does not have a module
607      * definition.
608      */
609     fn get_module(@mut self) -> @Module {
610         match self.get_module_if_available() {
611             None => {
612                 fail!(~"get_module called on a node with no module \
613                        definition!")
614             }
615             Some(module_def) => module_def
616         }
617     }
618
619     fn defined_in_namespace(namespace: Namespace) -> bool {
620         match namespace {
621             TypeNS   => return self.type_def.is_some(),
622             ValueNS  => return self.value_def.is_some()
623         }
624     }
625
626     fn def_for_namespace(namespace: Namespace) -> Option<def> {
627         match namespace {
628             TypeNS => {
629                 match self.type_def {
630                     None => None,
631                     Some(ref type_def) => {
632                         // FIXME (#3784): This is reallllly questionable.
633                         // Perhaps the right thing to do is to merge def_mod
634                         // and def_ty.
635                         match (*type_def).type_def {
636                             Some(type_def) => Some(type_def),
637                             None => {
638                                 match (*type_def).module_def {
639                                     Some(module_def) => {
640                                         module_def.def_id.map(|def_id|
641                                             def_mod(*def_id))
642                                     }
643                                     None => None
644                                 }
645                             }
646                         }
647                     }
648                 }
649             }
650             ValueNS => {
651                 match self.value_def {
652                     None => None,
653                     Some(value_def) => Some(value_def.def)
654                 }
655             }
656         }
657     }
658
659     fn privacy_for_namespace(namespace: Namespace) -> Option<Privacy> {
660         match namespace {
661             TypeNS => {
662                 match self.type_def {
663                     None => None,
664                     Some(ref type_def) => Some((*type_def).privacy)
665                 }
666             }
667             ValueNS => {
668                 match self.value_def {
669                     None => None,
670                     Some(value_def) => Some(value_def.privacy)
671                 }
672             }
673         }
674     }
675
676     fn span_for_namespace(namespace: Namespace) -> Option<span> {
677         if self.defined_in_namespace(namespace) {
678             match namespace {
679                 TypeNS  => self.type_span,
680                 ValueNS => self.value_span,
681             }
682         } else {
683             None
684         }
685     }
686 }
687
688 pub fn NameBindings() -> NameBindings {
689     NameBindings {
690         type_def: None,
691         value_def: None,
692         type_span: None,
693         value_span: None
694     }
695 }
696
697 /// Interns the names of the primitive types.
698 pub struct PrimitiveTypeTable {
699     primitive_types: HashMap<ident,prim_ty>,
700 }
701
702 pub impl PrimitiveTypeTable {
703     fn intern(intr: @ident_interner, string: @~str,
704               primitive_type: prim_ty) {
705         let ident = intr.intern(string);
706         self.primitive_types.insert(ident, primitive_type);
707     }
708 }
709
710 pub fn PrimitiveTypeTable(intr: @ident_interner) -> PrimitiveTypeTable {
711     let table = PrimitiveTypeTable {
712         primitive_types: HashMap()
713     };
714
715     table.intern(intr, @~"bool",    ty_bool);
716     table.intern(intr, @~"char",    ty_int(ty_char));
717     table.intern(intr, @~"float",   ty_float(ty_f));
718     table.intern(intr, @~"f32",     ty_float(ty_f32));
719     table.intern(intr, @~"f64",     ty_float(ty_f64));
720     table.intern(intr, @~"int",     ty_int(ty_i));
721     table.intern(intr, @~"i8",      ty_int(ty_i8));
722     table.intern(intr, @~"i16",     ty_int(ty_i16));
723     table.intern(intr, @~"i32",     ty_int(ty_i32));
724     table.intern(intr, @~"i64",     ty_int(ty_i64));
725     table.intern(intr, @~"str",     ty_str);
726     table.intern(intr, @~"uint",    ty_uint(ty_u));
727     table.intern(intr, @~"u8",      ty_uint(ty_u8));
728     table.intern(intr, @~"u16",     ty_uint(ty_u16));
729     table.intern(intr, @~"u32",     ty_uint(ty_u32));
730     table.intern(intr, @~"u64",     ty_uint(ty_u64));
731
732     return table;
733 }
734
735
736 pub fn namespace_to_str(ns: Namespace) -> ~str {
737     match ns {
738         TypeNS  => ~"type",
739         ValueNS => ~"value",
740     }
741 }
742
743 pub fn Resolver(session: Session,
744                 lang_items: LanguageItems,
745                 crate: @crate)
746              -> Resolver {
747     let graph_root = @mut NameBindings();
748
749     graph_root.define_module(Public,
750                              NoParentLink,
751                              Some(def_id { crate: 0, node: 0 }),
752                              NormalModuleKind,
753                              crate.span);
754
755     let current_module = graph_root.get_module();
756
757     let self = Resolver {
758         session: session,
759         lang_items: copy lang_items,
760         crate: crate,
761
762         // The outermost module has def ID 0; this is not reflected in the
763         // AST.
764
765         graph_root: graph_root,
766
767         unused_import_lint_level: unused_import_lint_level(session),
768
769         trait_info: HashMap(),
770         structs: HashMap(),
771
772         unresolved_imports: 0,
773
774         current_module: current_module,
775         value_ribs: @DVec(),
776         type_ribs: @DVec(),
777         label_ribs: @DVec(),
778
779         xray_context: NoXray,
780         current_trait_refs: None,
781
782         self_ident: special_idents::self_,
783         type_self_ident: special_idents::type_self,
784
785         primitive_type_table: @PrimitiveTypeTable(session.
786                                                   parse_sess.interner),
787
788         namespaces: ~[ TypeNS, ValueNS ],
789
790         attr_main_fn: None,
791         main_fns: ~[],
792
793         def_map: HashMap(),
794         export_map2: HashMap(),
795         trait_map: @HashMap(),
796
797         intr: session.intr()
798     };
799
800     self
801 }
802
803 /// The main resolver class.
804 pub struct Resolver {
805     session: Session,
806     lang_items: LanguageItems,
807     crate: @crate,
808
809     intr: @ident_interner,
810
811     graph_root: @mut NameBindings,
812
813     unused_import_lint_level: level,
814
815     trait_info: HashMap<def_id,@HashMap<ident,()>>,
816     structs: HashMap<def_id,()>,
817
818     // The number of imports that are currently unresolved.
819     mut unresolved_imports: uint,
820
821     // The module that represents the current item scope.
822     mut current_module: @Module,
823
824     // The current set of local scopes, for values.
825     // FIXME #4948: Reuse ribs to avoid allocation.
826     value_ribs: @DVec<@Rib>,
827
828     // The current set of local scopes, for types.
829     type_ribs: @DVec<@Rib>,
830
831     // The current set of local scopes, for labels.
832     label_ribs: @DVec<@Rib>,
833
834     // Whether the current context is an X-ray context. An X-ray context is
835     // allowed to access private names of any module.
836     mut xray_context: XrayFlag,
837
838     // The trait that the current context can refer to.
839     mut current_trait_refs: Option<@DVec<def_id>>,
840
841     // The ident for the keyword "self".
842     self_ident: ident,
843     // The ident for the non-keyword "Self".
844     type_self_ident: ident,
845
846     // The idents for the primitive types.
847     primitive_type_table: @PrimitiveTypeTable,
848
849     // The four namespaces.
850     namespaces: ~[Namespace],
851
852     // The function that has attribute named 'main'
853     mut attr_main_fn: Option<(node_id, span)>,
854     // The functions named 'main'
855     mut main_fns: ~[Option<(node_id, span)>],
856
857     def_map: DefMap,
858     export_map2: ExportMap2,
859     trait_map: TraitMap,
860 }
861
862 pub impl Resolver {
863     /// The main name resolution procedure.
864     fn resolve(@self, this: @Resolver) {
865         self.build_reduced_graph(this);
866         self.session.abort_if_errors();
867
868         self.resolve_imports();
869         self.session.abort_if_errors();
870
871         self.record_exports();
872         self.session.abort_if_errors();
873
874         self.resolve_crate();
875         self.session.abort_if_errors();
876
877         self.check_duplicate_main();
878         self.check_for_unused_imports_if_necessary();
879     }
880
881     //
882     // Reduced graph building
883     //
884     // Here we build the "reduced graph": the graph of the module tree without
885     // any imports resolved.
886     //
887
888     /// Constructs the reduced graph for the entire crate.
889     fn build_reduced_graph(this: @Resolver) {
890         let initial_parent =
891             ModuleReducedGraphParent(self.graph_root.get_module());
892         visit_crate(*self.crate, initial_parent, mk_vt(@Visitor {
893             visit_item: |item, context, visitor|
894                 (*this).build_reduced_graph_for_item(item, context, visitor),
895
896             visit_foreign_item: |foreign_item, context, visitor|
897                 (*this).build_reduced_graph_for_foreign_item(foreign_item,
898                                                              context,
899                                                              visitor),
900
901             visit_view_item: |view_item, context, visitor|
902                 (*this).build_reduced_graph_for_view_item(view_item,
903                                                           context,
904                                                           visitor),
905
906             visit_block: |block, context, visitor|
907                 (*this).build_reduced_graph_for_block(block,
908                                                       context,
909                                                       visitor),
910
911             .. *default_visitor()
912         }));
913     }
914
915     /// Returns the current module tracked by the reduced graph parent.
916     fn get_module_from_parent(reduced_graph_parent: ReducedGraphParent)
917                            -> @Module {
918         match reduced_graph_parent {
919             ModuleReducedGraphParent(module_) => {
920                 return module_;
921             }
922         }
923     }
924
925     /**
926      * Adds a new child item to the module definition of the parent node and
927      * returns its corresponding name bindings as well as the current parent.
928      * Or, if we're inside a block, creates (or reuses) an anonymous module
929      * corresponding to the innermost block ID and returns the name bindings
930      * as well as the newly-created parent.
931      *
932      * If this node does not have a module definition and we are not inside
933      * a block, fails.
934      */
935     fn add_child(name: ident,
936                  reduced_graph_parent: ReducedGraphParent,
937                  duplicate_checking_mode: DuplicateCheckingMode,
938                  // For printing errors
939                  sp: span)
940               -> (@mut NameBindings, ReducedGraphParent) {
941
942         // If this is the immediate descendant of a module, then we add the
943         // child name directly. Otherwise, we create or reuse an anonymous
944         // module and add the child to that.
945
946         let mut module_;
947         match reduced_graph_parent {
948             ModuleReducedGraphParent(parent_module) => {
949                 module_ = parent_module;
950             }
951         }
952
953         // Add or reuse the child.
954         let new_parent = ModuleReducedGraphParent(module_);
955         match module_.children.find(&name) {
956             None => {
957                 let child = @mut NameBindings();
958                 module_.children.insert(name, child);
959                 return (child, new_parent);
960             }
961             Some(child) => {
962                 // Enforce the duplicate checking mode. If we're requesting
963                 // duplicate module checking, check that there isn't a module
964                 // in the module with the same name. If we're requesting
965                 // duplicate type checking, check that there isn't a type in
966                 // the module with the same name. If we're requesting
967                 // duplicate value checking, check that there isn't a value in
968                 // the module with the same name. If we're requesting
969                 // duplicate type checking and duplicate value checking, check
970                 // that there isn't a duplicate type and a duplicate value
971                 // with the same name. If no duplicate checking was requested
972                 // at all, do nothing.
973
974                 let mut is_duplicate = false;
975                 match duplicate_checking_mode {
976                     ForbidDuplicateModules => {
977                         is_duplicate =
978                             child.get_module_if_available().is_some();
979                     }
980                     ForbidDuplicateTypes => {
981                         match child.def_for_namespace(TypeNS) {
982                             Some(def_mod(_)) | None => {}
983                             Some(_) => is_duplicate = true
984                         }
985                     }
986                     ForbidDuplicateValues => {
987                         is_duplicate = child.defined_in_namespace(ValueNS);
988                     }
989                     ForbidDuplicateTypesAndValues => {
990                         match child.def_for_namespace(TypeNS) {
991                             Some(def_mod(_)) | None => {}
992                             Some(_) => is_duplicate = true
993                         };
994                         if child.defined_in_namespace(ValueNS) {
995                             is_duplicate = true;
996                         }
997                     }
998                     OverwriteDuplicates => {}
999                 }
1000                 if duplicate_checking_mode != OverwriteDuplicates &&
1001                         is_duplicate {
1002                     // Return an error here by looking up the namespace that
1003                     // had the duplicate.
1004                     let ns = namespace_for_duplicate_checking_mode(
1005                         duplicate_checking_mode);
1006                     self.session.span_err(sp,
1007                         fmt!("duplicate definition of %s %s",
1008                              namespace_to_str(ns),
1009                              self.session.str_of(name)));
1010                     do child.span_for_namespace(ns).iter() |sp| {
1011                         self.session.span_note(*sp,
1012                              fmt!("first definition of %s %s here:",
1013                                   namespace_to_str(ns),
1014                                   self.session.str_of(name)));
1015                     }
1016                 }
1017                 return (child, new_parent);
1018             }
1019         }
1020     }
1021
1022     fn block_needs_anonymous_module(block: blk) -> bool {
1023         // If the block has view items, we need an anonymous module.
1024         if block.node.view_items.len() > 0 {
1025             return true;
1026         }
1027
1028         // Check each statement.
1029         for block.node.stmts.each |statement| {
1030             match statement.node {
1031                 stmt_decl(declaration, _) => {
1032                     match declaration.node {
1033                         decl_item(_) => {
1034                             return true;
1035                         }
1036                         _ => {
1037                             // Keep searching.
1038                         }
1039                     }
1040                 }
1041                 _ => {
1042                     // Keep searching.
1043                 }
1044             }
1045         }
1046
1047         // If we found neither view items nor items, we don't need to create
1048         // an anonymous module.
1049
1050         return false;
1051     }
1052
1053     fn get_parent_link(parent: ReducedGraphParent,
1054                        name: ident) -> ParentLink {
1055         match parent {
1056             ModuleReducedGraphParent(module_) => {
1057                 return ModuleParentLink(module_, name);
1058             }
1059         }
1060     }
1061
1062     /// Constructs the reduced graph for one item.
1063     fn build_reduced_graph_for_item(item: @item,
1064                                     parent: ReducedGraphParent,
1065                                     &&visitor: vt<ReducedGraphParent>) {
1066         let ident = item.ident;
1067         let sp = item.span;
1068         let privacy = visibility_to_privacy(item.vis);
1069
1070         match /*bad*/copy item.node {
1071             item_mod(module_) => {
1072                 let (name_bindings, new_parent) =
1073                     self.add_child(ident, parent, ForbidDuplicateModules, sp);
1074
1075                 let parent_link = self.get_parent_link(new_parent, ident);
1076                 let def_id = def_id { crate: 0, node: item.id };
1077                 name_bindings.define_module(privacy,
1078                                             parent_link,
1079                                             Some(def_id),
1080                                             NormalModuleKind,
1081                                             sp);
1082
1083                 let new_parent =
1084                     ModuleReducedGraphParent(name_bindings.get_module());
1085
1086                 visit_mod(module_, sp, item.id, new_parent, visitor);
1087             }
1088
1089             item_foreign_mod(fm) => {
1090                 let new_parent = match fm.sort {
1091                     named => {
1092                         let (name_bindings, new_parent) =
1093                             self.add_child(ident, parent,
1094                                            ForbidDuplicateModules, sp);
1095
1096                         let parent_link = self.get_parent_link(new_parent,
1097                                                                ident);
1098                         let def_id = def_id { crate: 0, node: item.id };
1099                         name_bindings.define_module(privacy,
1100                                                     parent_link,
1101                                                     Some(def_id),
1102                                                     ExternModuleKind,
1103                                                     sp);
1104
1105                         ModuleReducedGraphParent(name_bindings.get_module())
1106                     }
1107
1108                     // For anon foreign mods, the contents just go in the
1109                     // current scope
1110                     anonymous => parent
1111                 };
1112
1113                 visit_item(item, new_parent, visitor);
1114             }
1115
1116             // These items live in the value namespace.
1117             item_const(*) => {
1118                 let (name_bindings, _) =
1119                     self.add_child(ident, parent, ForbidDuplicateValues, sp);
1120
1121                 name_bindings.define_value
1122                     (privacy, def_const(local_def(item.id)), sp);
1123             }
1124             item_fn(_, purity, _, _) => {
1125               let (name_bindings, new_parent) =
1126                 self.add_child(ident, parent, ForbidDuplicateValues, sp);
1127
1128                 let def = def_fn(local_def(item.id), purity);
1129                 name_bindings.define_value(privacy, def, sp);
1130                 visit_item(item, new_parent, visitor);
1131             }
1132
1133             // These items live in the type namespace.
1134             item_ty(*) => {
1135                 let (name_bindings, _) =
1136                     self.add_child(ident, parent, ForbidDuplicateTypes, sp);
1137
1138                 name_bindings.define_type
1139                     (privacy, def_ty(local_def(item.id)), sp);
1140             }
1141
1142             item_enum(ref enum_definition, _) => {
1143                 let (name_bindings, new_parent) =
1144                     self.add_child(ident, parent, ForbidDuplicateTypes, sp);
1145
1146                 name_bindings.define_type
1147                     (privacy, def_ty(local_def(item.id)), sp);
1148
1149                 for (*enum_definition).variants.each |variant| {
1150                     self.build_reduced_graph_for_variant(*variant,
1151                         local_def(item.id),
1152                         // inherited => privacy of the enum item
1153                         variant_visibility_to_privacy(variant.node.vis,
1154                                                       privacy == Public),
1155                         new_parent,
1156                         visitor);
1157                 }
1158             }
1159
1160             // These items live in both the type and value namespaces.
1161             item_struct(struct_def, _) => {
1162                 let (name_bindings, new_parent) =
1163                     self.add_child(ident, parent, ForbidDuplicateTypes, sp);
1164
1165                 name_bindings.define_type(
1166                     privacy, def_ty(local_def(item.id)), sp);
1167
1168                 // If this struct is tuple-like or enum-like, define a name
1169                 // in the value namespace.
1170                 match struct_def.ctor_id {
1171                     None => {}
1172                     Some(ctor_id) => {
1173                         name_bindings.define_value(
1174                             privacy,
1175                             def_struct(local_def(ctor_id)),
1176                             sp);
1177                     }
1178                 }
1179
1180                 // Record the def ID of this struct.
1181                 self.structs.insert(local_def(item.id), ());
1182
1183                 visit_item(item, new_parent, visitor);
1184             }
1185
1186             item_impl(_, trait_ref_opt, ty, methods) => {
1187                 // If this implements an anonymous trait and it has static
1188                 // methods, then add all the static methods within to a new
1189                 // module, if the type was defined within this module.
1190                 //
1191                 // FIXME (#3785): This is quite unsatisfactory. Perhaps we
1192                 // should modify anonymous traits to only be implementable in
1193                 // the same module that declared the type.
1194
1195                 // Bail out early if there are no static methods.
1196                 let mut has_static_methods = false;
1197                 for methods.each |method| {
1198                     match method.self_ty.node {
1199                         sty_static => has_static_methods = true,
1200                         _ => {}
1201                     }
1202                 }
1203
1204                 // If there are static methods, then create the module
1205                 // and add them.
1206                 match (trait_ref_opt, ty) {
1207                     (None, @Ty { node: ty_path(path, _), _ }) if
1208                             has_static_methods && path.idents.len() == 1 => {
1209                         // Create the module.
1210                         let name = path_to_ident(path);
1211                         let (name_bindings, new_parent) =
1212                             self.add_child(name,
1213                                            parent,
1214                                            ForbidDuplicateModules,
1215                                            sp);
1216
1217                         let parent_link = self.get_parent_link(new_parent,
1218                                                                ident);
1219                         let def_id = local_def(item.id);
1220                         name_bindings.define_module(Public,
1221                                                     parent_link,
1222                                                     Some(def_id),
1223                                                     TraitModuleKind,
1224                                                     sp);
1225
1226                         let new_parent = ModuleReducedGraphParent(
1227                             name_bindings.get_module());
1228
1229                         // For each static method...
1230                         for methods.each |method| {
1231                             match method.self_ty.node {
1232                                 sty_static => {
1233                                     // Add the static method to the
1234                                     // module.
1235                                     let ident = method.ident;
1236                                     let (method_name_bindings, _) =
1237                                         self.add_child(
1238                                             ident,
1239                                             new_parent,
1240                                             ForbidDuplicateValues,
1241                                             method.span);
1242                                     let def = def_fn(local_def(method.id),
1243                                                      method.purity);
1244                                     method_name_bindings.define_value(
1245                                         Public, def, method.span);
1246                                 }
1247                                 _ => {}
1248                             }
1249                         }
1250                     }
1251                     _ => {}
1252                 }
1253
1254                 visit_item(item, parent, visitor);
1255             }
1256
1257             item_trait(_, _, ref methods) => {
1258                 let (name_bindings, new_parent) =
1259                     self.add_child(ident, parent, ForbidDuplicateTypes, sp);
1260
1261                 // If the trait has static methods, then add all the static
1262                 // methods within to a new module.
1263                 //
1264                 // We only need to create the module if the trait has static
1265                 // methods, so check that first.
1266                 let mut has_static_methods = false;
1267                 for (*methods).each |method| {
1268                     let ty_m = trait_method_to_ty_method(*method);
1269                     match ty_m.self_ty.node {
1270                         sty_static => {
1271                             has_static_methods = true;
1272                             break;
1273                         }
1274                         _ => {}
1275                     }
1276                 }
1277
1278                 // Create the module if necessary.
1279                 let module_parent_opt;
1280                 if has_static_methods {
1281                     let parent_link = self.get_parent_link(parent, ident);
1282                     name_bindings.define_module(privacy,
1283                                                 parent_link,
1284                                                 Some(local_def(item.id)),
1285                                                 TraitModuleKind,
1286                                                 sp);
1287                     module_parent_opt = Some(ModuleReducedGraphParent(
1288                         name_bindings.get_module()));
1289                 } else {
1290                     module_parent_opt = None;
1291                 }
1292
1293                 // Add the names of all the methods to the trait info.
1294                 let method_names = @HashMap();
1295                 for (*methods).each |method| {
1296                     let ty_m = trait_method_to_ty_method(*method);
1297
1298                     let ident = ty_m.ident;
1299                     // Add it to the trait info if not static,
1300                     // add it as a name in the trait module otherwise.
1301                     match ty_m.self_ty.node {
1302                         sty_static => {
1303                             let def = def_static_method(
1304                                 local_def(ty_m.id),
1305                                 Some(local_def(item.id)),
1306                                 ty_m.purity);
1307
1308                             let (method_name_bindings, _) =
1309                                 self.add_child(ident,
1310                                                module_parent_opt.get(),
1311                                                ForbidDuplicateValues,
1312                                                ty_m.span);
1313                             method_name_bindings.define_value(Public,
1314                                                               def,
1315                                                               ty_m.span);
1316                         }
1317                         _ => {
1318                             method_names.insert(ident, ());
1319                         }
1320                     }
1321                 }
1322
1323                 let def_id = local_def(item.id);
1324                 self.trait_info.insert(def_id, method_names);
1325
1326                 name_bindings.define_type(privacy, def_ty(def_id), sp);
1327                 visit_item(item, new_parent, visitor);
1328             }
1329
1330             item_mac(*) => {
1331                 fail!(~"item macros unimplemented")
1332             }
1333         }
1334     }
1335
1336     // Constructs the reduced graph for one variant. Variants exist in the
1337     // type and/or value namespaces.
1338     fn build_reduced_graph_for_variant(variant: variant,
1339                                        item_id: def_id,
1340                                        +parent_privacy: Privacy,
1341                                        parent: ReducedGraphParent,
1342                                        &&visitor: vt<ReducedGraphParent>) {
1343
1344         let ident = variant.node.name;
1345         let (child, _) = self.add_child(ident, parent, ForbidDuplicateValues,
1346                                         variant.span);
1347
1348         let privacy;
1349         match variant.node.vis {
1350             public => privacy = Public,
1351             private => privacy = Private,
1352             inherited => privacy = parent_privacy
1353         }
1354
1355         match variant.node.kind {
1356             tuple_variant_kind(_) => {
1357                 child.define_value(privacy,
1358                                    def_variant(item_id,
1359                                                local_def(variant.node.id)),
1360                                    variant.span);
1361             }
1362             struct_variant_kind(_) => {
1363                 child.define_type(privacy,
1364                                   def_variant(item_id,
1365                                               local_def(variant.node.id)),
1366                                   variant.span);
1367                 self.structs.insert(local_def(variant.node.id), ());
1368             }
1369             enum_variant_kind(ref enum_definition) => {
1370                 child.define_type(privacy,
1371                                   def_ty(local_def(variant.node.id)),
1372                                   variant.span);
1373                 for (*enum_definition).variants.each |variant| {
1374                     self.build_reduced_graph_for_variant(*variant, item_id,
1375                                                          parent_privacy,
1376                                                          parent, visitor);
1377                 }
1378             }
1379         }
1380     }
1381
1382     /**
1383      * Constructs the reduced graph for one 'view item'. View items consist
1384      * of imports and use directives.
1385      */
1386     fn build_reduced_graph_for_view_item(view_item: @view_item,
1387                                          parent: ReducedGraphParent,
1388                                          &&_visitor: vt<ReducedGraphParent>) {
1389         let privacy = visibility_to_privacy(view_item.vis);
1390         match /*bad*/copy view_item.node {
1391             view_item_use(view_paths) => {
1392                 for view_paths.each |view_path| {
1393                     // Extract and intern the module part of the path. For
1394                     // globs and lists, the path is found directly in the AST;
1395                     // for simple paths we have to munge the path a little.
1396
1397                     let module_path = @DVec();
1398                     match view_path.node {
1399                         view_path_simple(_, full_path, _, _) => {
1400                             let path_len = full_path.idents.len();
1401                             assert path_len != 0;
1402
1403                             for full_path.idents.eachi |i, ident| {
1404                                 if i != path_len - 1 {
1405                                     (*module_path).push(*ident);
1406                                 }
1407                             }
1408                         }
1409
1410                         view_path_glob(module_ident_path, _) |
1411                         view_path_list(module_ident_path, _, _) => {
1412                             for module_ident_path.idents.each |ident| {
1413                                 (*module_path).push(*ident);
1414                             }
1415                         }
1416                     }
1417
1418                     // Build up the import directives.
1419                     let module_ = self.get_module_from_parent(parent);
1420                     let state = @mut ImportState();
1421                     match view_path.node {
1422                         view_path_simple(binding, full_path, ns, _) => {
1423                             let ns = match ns {
1424                                 module_ns => TypeNSOnly,
1425                                 type_value_ns => AnyNS
1426                             };
1427
1428                             let source_ident = full_path.idents.last();
1429                             let subclass = @SingleImport(binding,
1430                                                          source_ident,
1431                                                          ns);
1432                             self.build_import_directive(privacy,
1433                                                         module_,
1434                                                         module_path,
1435                                                         subclass,
1436                                                         view_path.span,
1437                                                         state);
1438                         }
1439                         view_path_list(_, ref source_idents, _) => {
1440                             for (*source_idents).each |source_ident| {
1441                                 let name = source_ident.node.name;
1442                                 let subclass = @SingleImport(name,
1443                                                              name,
1444                                                              AnyNS);
1445                                 self.build_import_directive(privacy,
1446                                                             module_,
1447                                                             module_path,
1448                                                             subclass,
1449                                                             view_path.span,
1450                                                             state);
1451                             }
1452                         }
1453                         view_path_glob(_, _) => {
1454                             self.build_import_directive(privacy,
1455                                                         module_,
1456                                                         module_path,
1457                                                         @GlobImport,
1458                                                         view_path.span,
1459                                                         state);
1460                         }
1461                     }
1462                 }
1463             }
1464
1465             view_item_extern_mod(name, _, node_id) => {
1466                 match find_extern_mod_stmt_cnum(self.session.cstore, node_id) {
1467                     Some(crate_id) => {
1468                         let (child_name_bindings, new_parent) =
1469                             self.add_child(name, parent, ForbidDuplicateTypes,
1470                                            view_item.span);
1471
1472                         let def_id = def_id { crate: crate_id, node: 0 };
1473                         let parent_link = ModuleParentLink
1474                             (self.get_module_from_parent(new_parent), name);
1475
1476                         child_name_bindings.define_module(privacy,
1477                                                           parent_link,
1478                                                           Some(def_id),
1479                                                           NormalModuleKind,
1480                                                           view_item.span);
1481                         self.build_reduced_graph_for_external_crate
1482                             (child_name_bindings.get_module());
1483                     }
1484                     None => {
1485                         /* Ignore. */
1486                     }
1487                 }
1488             }
1489         }
1490     }
1491
1492     /// Constructs the reduced graph for one foreign item.
1493     fn build_reduced_graph_for_foreign_item(foreign_item: @foreign_item,
1494                                             parent: ReducedGraphParent,
1495                                             &&visitor:
1496                                                 vt<ReducedGraphParent>) {
1497
1498         let name = foreign_item.ident;
1499         let (name_bindings, new_parent) =
1500             self.add_child(name, parent, ForbidDuplicateValues,
1501                            foreign_item.span);
1502
1503         match /*bad*/copy foreign_item.node {
1504             foreign_item_fn(_, _, type_parameters) => {
1505                 let def = def_fn(local_def(foreign_item.id), unsafe_fn);
1506                 name_bindings.define_value(Public, def, foreign_item.span);
1507
1508                 do self.with_type_parameter_rib
1509                         (HasTypeParameters(&type_parameters, foreign_item.id,
1510                                            0, NormalRibKind)) {
1511                     visit_foreign_item(foreign_item, new_parent, visitor);
1512                 }
1513             }
1514             foreign_item_const(*) => {
1515                 let def = def_const(local_def(foreign_item.id));
1516                 name_bindings.define_value(Public, def, foreign_item.span);
1517
1518                 visit_foreign_item(foreign_item, new_parent, visitor);
1519             }
1520         }
1521     }
1522
1523     fn build_reduced_graph_for_block(block: blk,
1524                                      parent: ReducedGraphParent,
1525                                      &&visitor: vt<ReducedGraphParent>) {
1526
1527         let mut new_parent;
1528         if self.block_needs_anonymous_module(block) {
1529             let block_id = block.node.id;
1530
1531             debug!("(building reduced graph for block) creating a new \
1532                     anonymous module for block %d",
1533                    block_id);
1534
1535             let parent_module = self.get_module_from_parent(parent);
1536             let new_module = @Module(BlockParentLink(parent_module, block_id),
1537                                      None,
1538                                      AnonymousModuleKind);
1539             parent_module.anonymous_children.insert(block_id, new_module);
1540             new_parent = ModuleReducedGraphParent(new_module);
1541         } else {
1542             new_parent = parent;
1543         }
1544
1545         visit_block(block, new_parent, visitor);
1546     }
1547
1548     fn handle_external_def(def: def,
1549                            modules: HashMap<def_id, @Module>,
1550                            child_name_bindings: @mut NameBindings,
1551                            final_ident: ~str,
1552                            ident: ident,
1553                            new_parent: ReducedGraphParent) {
1554         match def {
1555           def_mod(def_id) | def_foreign_mod(def_id) => {
1556             match copy child_name_bindings.type_def {
1557               Some(TypeNsDef { module_def: Some(copy module_def), _ }) => {
1558                 debug!("(building reduced graph for external crate) \
1559                         already created module");
1560                 module_def.def_id = Some(def_id);
1561                 modules.insert(def_id, module_def);
1562               }
1563               Some(_) | None => {
1564                 debug!("(building reduced graph for \
1565                         external crate) building module \
1566                         %s", final_ident);
1567                 let parent_link = self.get_parent_link(new_parent, ident);
1568
1569                 match modules.find(&def_id) {
1570                   None => {
1571                     child_name_bindings.define_module(Public,
1572                                                       parent_link,
1573                                                       Some(def_id),
1574                                                       NormalModuleKind,
1575                                                       dummy_sp());
1576                     modules.insert(def_id,
1577                                    child_name_bindings.get_module());
1578                   }
1579                   Some(existing_module) => {
1580                     // Create an import resolution to
1581                     // avoid creating cycles in the
1582                     // module graph.
1583
1584                     let resolution =
1585                         @mut ImportResolution(Public,
1586                                               dummy_sp(),
1587                                               @mut ImportState());
1588                     resolution.outstanding_references = 0;
1589
1590                     match existing_module.parent_link {
1591                       NoParentLink |
1592                       BlockParentLink(*) => {
1593                         fail!(~"can't happen");
1594                       }
1595                       ModuleParentLink(parent_module, ident) => {
1596                         let name_bindings = parent_module.children.get(
1597                             &ident);
1598                         resolution.type_target =
1599                             Some(Target(parent_module, name_bindings));
1600                       }
1601                     }
1602
1603                     debug!("(building reduced graph for external crate) \
1604                             ... creating import resolution");
1605
1606                     new_parent.import_resolutions.insert(ident, resolution);
1607                   }
1608                 }
1609               }
1610             }
1611           }
1612           def_fn(*) | def_static_method(*) | def_const(*) |
1613           def_variant(*) => {
1614             debug!("(building reduced graph for external \
1615                     crate) building value %s", final_ident);
1616             child_name_bindings.define_value(Public, def, dummy_sp());
1617           }
1618           def_ty(def_id) => {
1619             debug!("(building reduced graph for external \
1620                     crate) building type %s", final_ident);
1621
1622             // If this is a trait, add all the method names
1623             // to the trait info.
1624
1625             match get_method_names_if_trait(self.session.cstore, def_id) {
1626               None => {
1627                 // Nothing to do.
1628               }
1629               Some(method_names) => {
1630                 let interned_method_names = @HashMap();
1631                 for method_names.each |method_data| {
1632                     let (method_name, self_ty) = *method_data;
1633                     debug!("(building reduced graph for \
1634                             external crate) ... adding \
1635                             trait method '%s'",
1636                            self.session.str_of(method_name));
1637
1638                     // Add it to the trait info if not static.
1639                     if self_ty != sty_static {
1640                         interned_method_names.insert(method_name, ());
1641                     }
1642                 }
1643                 self.trait_info.insert(def_id, interned_method_names);
1644               }
1645             }
1646
1647             child_name_bindings.define_type(Public, def, dummy_sp());
1648           }
1649           def_struct(def_id) => {
1650             debug!("(building reduced graph for external \
1651                     crate) building type %s",
1652                    final_ident);
1653             child_name_bindings.define_type(Public, def, dummy_sp());
1654             self.structs.insert(def_id, ());
1655           }
1656           def_self(*) | def_arg(*) | def_local(*) |
1657           def_prim_ty(*) | def_ty_param(*) | def_binding(*) |
1658           def_use(*) | def_upvar(*) | def_region(*) |
1659           def_typaram_binder(*) | def_label(*) | def_self_ty(*) => {
1660             fail!(fmt!("didn't expect `%?`", def));
1661           }
1662         }
1663     }
1664
1665     /**
1666      * Builds the reduced graph rooted at the 'use' directive for an external
1667      * crate.
1668      */
1669     fn build_reduced_graph_for_external_crate(root: @Module) {
1670         let modules = HashMap();
1671
1672         // Create all the items reachable by paths.
1673         for each_path(self.session.cstore, root.def_id.get().crate)
1674                 |path_string, def_like| {
1675
1676             debug!("(building reduced graph for external crate) found path \
1677                         entry: %s (%?)",
1678                     path_string, def_like);
1679
1680             let mut pieces = split_str(path_string, ~"::");
1681             let final_ident_str = pieces.pop();
1682             let final_ident = self.session.ident_of(final_ident_str);
1683
1684             // Find the module we need, creating modules along the way if we
1685             // need to.
1686
1687             let mut current_module = root;
1688             for pieces.each |ident_str| {
1689                 let ident = self.session.ident_of(/*bad*/copy *ident_str);
1690                 // Create or reuse a graph node for the child.
1691                 let (child_name_bindings, new_parent) =
1692                     self.add_child(ident,
1693                                    ModuleReducedGraphParent(current_module),
1694                                    OverwriteDuplicates,
1695                                    dummy_sp());
1696
1697                 // Define or reuse the module node.
1698                 match child_name_bindings.type_def {
1699                     None => {
1700                         debug!("(building reduced graph for external crate) \
1701                                 autovivifying missing type def %s",
1702                                 *ident_str);
1703                         let parent_link = self.get_parent_link(new_parent,
1704                                                                ident);
1705                         child_name_bindings.define_module(Public,
1706                                                           parent_link,
1707                                                           None,
1708                                                           NormalModuleKind,
1709                                                           dummy_sp());
1710                     }
1711                     Some(copy type_ns_def)
1712                             if type_ns_def.module_def.is_none() => {
1713                         debug!("(building reduced graph for external crate) \
1714                                 autovivifying missing module def %s",
1715                                 *ident_str);
1716                         let parent_link = self.get_parent_link(new_parent,
1717                                                                ident);
1718                         child_name_bindings.define_module(Public,
1719                                                           parent_link,
1720                                                           None,
1721                                                           NormalModuleKind,
1722                                                           dummy_sp());
1723                     }
1724                     _ => {} // Fall through.
1725                 }
1726
1727                 current_module = child_name_bindings.get_module();
1728             }
1729
1730             match def_like {
1731                 dl_def(def) => {
1732                     // Add the new child item.
1733                     let (child_name_bindings, new_parent) =
1734                         self.add_child(final_ident,
1735                                        ModuleReducedGraphParent(
1736                                             current_module),
1737                                        OverwriteDuplicates,
1738                                        dummy_sp());
1739
1740                     self.handle_external_def(def,
1741                                              modules,
1742                                              child_name_bindings,
1743                                              self.session.str_of(final_ident),
1744                                              final_ident,
1745                                              new_parent);
1746                 }
1747                 dl_impl(def) => {
1748                     // We only process static methods of impls here.
1749                     match get_type_name_if_impl(self.session.cstore, def) {
1750                         None => {}
1751                         Some(final_ident) => {
1752                             let static_methods_opt =
1753                                 get_static_methods_if_impl(
1754                                     self.session.cstore, def);
1755                             match static_methods_opt {
1756                                 Some(ref static_methods) if
1757                                     static_methods.len() >= 1 => {
1758                                     debug!("(building reduced graph for \
1759                                             external crate) processing \
1760                                             static methods for type name %s",
1761                                             self.session.str_of(final_ident));
1762
1763                                     let (child_name_bindings, new_parent) =
1764                                         self.add_child(final_ident,
1765                                             ModuleReducedGraphParent(
1766                                                             current_module),
1767                                             OverwriteDuplicates,
1768                                             dummy_sp());
1769
1770                                     // Process the static methods. First,
1771                                     // create the module.
1772                                     let type_module;
1773                                     match copy child_name_bindings.type_def {
1774                                         Some(TypeNsDef {
1775                                             module_def: Some(copy module_def),
1776                                             _
1777                                         }) => {
1778                                             // We already have a module. This
1779                                             // is OK.
1780                                             type_module = module_def;
1781                                         }
1782                                         Some(_) | None => {
1783                                             let parent_link =
1784                                                 self.get_parent_link(
1785                                                     new_parent, final_ident);
1786                                             child_name_bindings.define_module(
1787                                                 Public,
1788                                                 parent_link,
1789                                                 Some(def),
1790                                                 NormalModuleKind,
1791                                                 dummy_sp());
1792                                             type_module =
1793                                                 child_name_bindings.
1794                                                     get_module();
1795                                         }
1796                                     }
1797
1798                                     // Add each static method to the module.
1799                                     let new_parent = ModuleReducedGraphParent(
1800                                         type_module);
1801                                     for static_methods.each
1802                                             |static_method_info| {
1803                                         let ident = static_method_info.ident;
1804                                         debug!("(building reduced graph for \
1805                                                  external crate) creating \
1806                                                  static method '%s'",
1807                                                self.session.str_of(ident));
1808
1809                                         let (method_name_bindings, _) =
1810                                             self.add_child(
1811                                                 ident,
1812                                                 new_parent,
1813                                                 OverwriteDuplicates,
1814                                                 dummy_sp());
1815                                         let def = def_fn(
1816                                             static_method_info.def_id,
1817                                             static_method_info.purity);
1818                                         method_name_bindings.define_value(
1819                                             Public, def, dummy_sp());
1820                                     }
1821                                 }
1822
1823                                 // Otherwise, do nothing.
1824                                 Some(_) | None => {}
1825                             }
1826                         }
1827                     }
1828                 }
1829                 dl_field => {
1830                     debug!("(building reduced graph for external crate) \
1831                             ignoring field");
1832                 }
1833             }
1834         }
1835     }
1836
1837     /// Creates and adds an import directive to the given module.
1838     fn build_import_directive(privacy: Privacy,
1839                               module_: @Module,
1840                               module_path: @DVec<ident>,
1841                               subclass: @ImportDirectiveSubclass,
1842                               span: span,
1843                               state: @mut ImportState) {
1844         let directive = @ImportDirective(privacy, module_path,
1845                                          subclass, span);
1846         module_.imports.push(directive);
1847
1848         // Bump the reference count on the name. Or, if this is a glob, set
1849         // the appropriate flag.
1850
1851         match *subclass {
1852             SingleImport(target, _, _) => {
1853                 debug!("(building import directive) building import \
1854                         directive: privacy %? %s::%s",
1855                        privacy,
1856                        self.idents_to_str(module_path.get()),
1857                        self.session.str_of(target));
1858
1859                 match module_.import_resolutions.find(&target) {
1860                     Some(resolution) => {
1861                         debug!("(building import directive) bumping \
1862                                 reference");
1863                         resolution.outstanding_references += 1;
1864                     }
1865                     None => {
1866                         debug!("(building import directive) creating new");
1867                         let resolution = @mut ImportResolution(privacy,
1868                                                                span,
1869                                                                state);
1870                         let name = self.idents_to_str(module_path.get());
1871                         // Don't warn about unused intrinsics because they're
1872                         // automatically appended to all files
1873                         if name == ~"intrinsic::rusti" {
1874                             resolution.state.warned = true;
1875                         }
1876                         resolution.outstanding_references = 1;
1877                         module_.import_resolutions.insert(target, resolution);
1878                     }
1879                 }
1880             }
1881             GlobImport => {
1882                 // Set the glob flag. This tells us that we don't know the
1883                 // module's exports ahead of time.
1884
1885                 module_.glob_count += 1;
1886             }
1887         }
1888
1889         self.unresolved_imports += 1;
1890     }
1891
1892     // Import resolution
1893     //
1894     // This is a fixed-point algorithm. We resolve imports until our efforts
1895     // are stymied by an unresolved import; then we bail out of the current
1896     // module and continue. We terminate successfully once no more imports
1897     // remain or unsuccessfully when no forward progress in resolving imports
1898     // is made.
1899
1900     /**
1901      * Resolves all imports for the crate. This method performs the fixed-
1902      * point iteration.
1903      */
1904     fn resolve_imports() {
1905         let mut i = 0;
1906         let mut prev_unresolved_imports = 0;
1907         loop {
1908             debug!("(resolving imports) iteration %u, %u imports left",
1909                    i, self.unresolved_imports);
1910
1911             let module_root = self.graph_root.get_module();
1912             self.resolve_imports_for_module_subtree(module_root);
1913
1914             if self.unresolved_imports == 0 {
1915                 debug!("(resolving imports) success");
1916                 break;
1917             }
1918
1919             if self.unresolved_imports == prev_unresolved_imports {
1920                 self.session.err(~"failed to resolve imports");
1921                 self.report_unresolved_imports(module_root);
1922                 break;
1923             }
1924
1925             i += 1;
1926             prev_unresolved_imports = self.unresolved_imports;
1927         }
1928     }
1929
1930     /**
1931      * Attempts to resolve imports for the given module and all of its
1932      * submodules.
1933      */
1934     fn resolve_imports_for_module_subtree(module_: @Module) {
1935         debug!("(resolving imports for module subtree) resolving %s",
1936                self.module_to_str(module_));
1937         self.resolve_imports_for_module(module_);
1938
1939         for module_.children.each_value |&child_node| {
1940             match child_node.get_module_if_available() {
1941                 None => {
1942                     // Nothing to do.
1943                 }
1944                 Some(child_module) => {
1945                     self.resolve_imports_for_module_subtree(child_module);
1946                 }
1947             }
1948         }
1949
1950         for module_.anonymous_children.each_value |&child_module| {
1951             self.resolve_imports_for_module_subtree(child_module);
1952         }
1953     }
1954
1955     /// Attempts to resolve imports for the given module only.
1956     fn resolve_imports_for_module(module_: @Module) {
1957         if (*module_).all_imports_resolved() {
1958             debug!("(resolving imports for module) all imports resolved for \
1959                    %s",
1960                    self.module_to_str(module_));
1961             return;
1962         }
1963
1964         let import_count = module_.imports.len();
1965         while module_.resolved_import_count < import_count {
1966             let import_index = module_.resolved_import_count;
1967             let import_directive = module_.imports.get_elt(import_index);
1968             match self.resolve_import_for_module(module_, import_directive) {
1969                 Failed => {
1970                     // We presumably emitted an error. Continue.
1971                     let idents = import_directive.module_path.get();
1972                     let msg = fmt!("failed to resolve import: %s",
1973                                    self.import_path_to_str(idents,
1974                                    *import_directive.subclass));
1975                     self.session.span_err(import_directive.span, msg);
1976                 }
1977                 Indeterminate => {
1978                     // Bail out. We'll come around next time.
1979                     break;
1980                 }
1981                 Success(()) => {
1982                     // Good. Continue.
1983                 }
1984             }
1985
1986             module_.resolved_import_count += 1;
1987         }
1988     }
1989
1990     fn idents_to_str(idents: ~[ident]) -> ~str {
1991         let ident_strs = idents.map(|&ident| self.session.str_of(ident));
1992         return str::connect(ident_strs, "::");
1993     }
1994
1995     fn import_directive_subclass_to_str(subclass: ImportDirectiveSubclass)
1996                                                                      -> ~str {
1997         match subclass {
1998             SingleImport(_target, source, _ns) => self.session.str_of(source),
1999             GlobImport => ~"*"
2000         }
2001     }
2002
2003     fn import_path_to_str(idents: ~[ident], subclass: ImportDirectiveSubclass)
2004                                                                      -> ~str {
2005         if idents.is_empty() {
2006             self.import_directive_subclass_to_str(subclass)
2007         } else {
2008             fmt!("%s::%s",
2009                  self.idents_to_str(idents),
2010                  self.import_directive_subclass_to_str(subclass))
2011         }
2012     }
2013
2014     /**
2015      * Attempts to resolve the given import. The return value indicates
2016      * failure if we're certain the name does not exist, indeterminate if we
2017      * don't know whether the name exists at the moment due to other
2018      * currently-unresolved imports, or success if we know the name exists.
2019      * If successful, the resolved bindings are written into the module.
2020      */
2021     fn resolve_import_for_module(module_: @Module,
2022                                  import_directive: @ImportDirective)
2023                               -> ResolveResult<()> {
2024
2025         let mut resolution_result;
2026         let module_path = import_directive.module_path;
2027
2028         debug!("(resolving import for module) resolving import `%s::...` in \
2029                 `%s`",
2030                self.idents_to_str((*module_path).get()),
2031                self.module_to_str(module_));
2032
2033         // One-level renaming imports of the form `import foo = bar;` are
2034         // handled specially.
2035
2036         if (*module_path).len() == 0 {
2037             resolution_result =
2038                 self.resolve_one_level_renaming_import(module_,
2039                                                        import_directive);
2040         } else {
2041             // First, resolve the module path for the directive, if necessary.
2042             match self.resolve_module_path_for_import(module_,
2043                                                       module_path,
2044                                                       DontUseLexicalScope,
2045                                                       import_directive.span) {
2046
2047                 Failed => {
2048                     resolution_result = Failed;
2049                 }
2050                 Indeterminate => {
2051                     resolution_result = Indeterminate;
2052                 }
2053                 Success(containing_module) => {
2054                     // We found the module that the target is contained
2055                     // within. Attempt to resolve the import within it.
2056
2057                     match *import_directive.subclass {
2058                         SingleImport(target, source, AnyNS) => {
2059                             resolution_result =
2060                                 self.resolve_single_import(module_,
2061                                                            containing_module,
2062                                                            target,
2063                                                            source);
2064                         }
2065                         SingleImport(target, source, TypeNSOnly) => {
2066                             resolution_result =
2067                                 self.resolve_single_module_import
2068                                     (module_, containing_module, target,
2069                                      source);
2070                         }
2071                         GlobImport => {
2072                             let span = import_directive.span;
2073                             let p = import_directive.privacy;
2074                             resolution_result =
2075                                 self.resolve_glob_import(p,
2076                                                          module_,
2077                                                          containing_module,
2078                                                          span);
2079                         }
2080                     }
2081                 }
2082             }
2083         }
2084
2085         // Decrement the count of unresolved imports.
2086         match resolution_result {
2087             Success(()) => {
2088                 assert self.unresolved_imports >= 1;
2089                 self.unresolved_imports -= 1;
2090             }
2091             _ => {
2092                 // Nothing to do here; just return the error.
2093             }
2094         }
2095
2096         // Decrement the count of unresolved globs if necessary. But only if
2097         // the resolution result is indeterminate -- otherwise we'll stop
2098         // processing imports here. (See the loop in
2099         // resolve_imports_for_module.)
2100
2101         if !resolution_result.indeterminate() {
2102             match *import_directive.subclass {
2103                 GlobImport => {
2104                     assert module_.glob_count >= 1;
2105                     module_.glob_count -= 1;
2106                 }
2107                 SingleImport(*) => {
2108                     // Ignore.
2109                 }
2110             }
2111         }
2112
2113         return resolution_result;
2114     }
2115
2116     fn resolve_single_import(module_: @Module,
2117                              containing_module: @Module,
2118                              target: ident,
2119                              source: ident)
2120                           -> ResolveResult<()> {
2121
2122         debug!("(resolving single import) resolving `%s` = `%s::%s` from \
2123                 `%s`",
2124                self.session.str_of(target),
2125                self.module_to_str(containing_module),
2126                self.session.str_of(source),
2127                self.module_to_str(module_));
2128
2129         // We need to resolve both namespaces for this to succeed.
2130         //
2131         // FIXME #4949: See if there's some way of handling namespaces in
2132         // a more generic way. We have two of them; it seems worth
2133         // doing...
2134
2135         let mut value_result = UnknownResult;
2136         let mut type_result = UnknownResult;
2137
2138         // Search for direct children of the containing module.
2139         match containing_module.children.find(&source) {
2140             None => {
2141                 // Continue.
2142             }
2143             Some(child_name_bindings) => {
2144                 if (*child_name_bindings).defined_in_namespace(ValueNS) {
2145                     value_result = BoundResult(containing_module,
2146                                                child_name_bindings);
2147                 }
2148                 if (*child_name_bindings).defined_in_namespace(TypeNS) {
2149                     type_result = BoundResult(containing_module,
2150                                               child_name_bindings);
2151                 }
2152             }
2153         }
2154
2155         // Unless we managed to find a result in both namespaces (unlikely),
2156         // search imports as well.
2157         match (value_result, type_result) {
2158             (BoundResult(*), BoundResult(*)) => {
2159                 // Continue.
2160             }
2161             _ => {
2162                 // If there is an unresolved glob at this point in the
2163                 // containing module, bail out. We don't know enough to be
2164                 // able to resolve this import.
2165
2166                 if containing_module.glob_count > 0 {
2167                     debug!("(resolving single import) unresolved glob; \
2168                             bailing out");
2169                     return Indeterminate;
2170                 }
2171
2172                 // Now search the exported imports within the containing
2173                 // module.
2174
2175                 match containing_module.import_resolutions.find(&source) {
2176                     None => {
2177                         // The containing module definitely doesn't have an
2178                         // exported import with the name in question. We can
2179                         // therefore accurately report that the names are
2180                         // unbound.
2181
2182                         if value_result.is_unknown() {
2183                             value_result = UnboundResult;
2184                         }
2185                         if type_result.is_unknown() {
2186                             type_result = UnboundResult;
2187                         }
2188                     }
2189                     Some(import_resolution)
2190                             if import_resolution.outstanding_references
2191                                 == 0 => {
2192
2193                         fn get_binding(import_resolution:
2194                                           @mut ImportResolution,
2195                                        namespace: Namespace)
2196                                     -> NamespaceResult {
2197
2198                             // Import resolutions must be declared with "pub"
2199                             // in order to be exported.
2200                             if import_resolution.privacy == Private {
2201                                 return UnboundResult;
2202                             }
2203
2204                             match (*import_resolution).
2205                                     target_for_namespace(namespace) {
2206                                 None => {
2207                                     return UnboundResult;
2208                                 }
2209                                 Some(target) => {
2210                                     import_resolution.state.used = true;
2211                                     return BoundResult(target.target_module,
2212                                                     target.bindings);
2213                                 }
2214                             }
2215                         }
2216
2217                         // The name is an import which has been fully
2218                         // resolved. We can, therefore, just follow it.
2219                         if value_result.is_unknown() {
2220                             value_result = get_binding(import_resolution,
2221                                                        ValueNS);
2222                         }
2223                         if type_result.is_unknown() {
2224                             type_result = get_binding(import_resolution,
2225                                                       TypeNS);
2226                         }
2227                     }
2228                     Some(_) => {
2229                         // The import is unresolved. Bail out.
2230                         debug!("(resolving single import) unresolved import; \
2231                                 bailing out");
2232                         return Indeterminate;
2233                     }
2234                 }
2235             }
2236         }
2237
2238         // We've successfully resolved the import. Write the results in.
2239         assert module_.import_resolutions.contains_key(&target);
2240         let import_resolution = module_.import_resolutions.get(&target);
2241
2242         match value_result {
2243             BoundResult(target_module, name_bindings) => {
2244                 import_resolution.value_target =
2245                     Some(Target(target_module, name_bindings));
2246             }
2247             UnboundResult => { /* Continue. */ }
2248             UnknownResult => {
2249                 fail!(~"value result should be known at this point");
2250             }
2251         }
2252         match type_result {
2253             BoundResult(target_module, name_bindings) => {
2254                 import_resolution.type_target =
2255                     Some(Target(target_module, name_bindings));
2256             }
2257             UnboundResult => { /* Continue. */ }
2258             UnknownResult => {
2259                 fail!(~"type result should be known at this point");
2260             }
2261         }
2262
2263         let i = import_resolution;
2264         match (i.value_target, i.type_target) {
2265             // If this name wasn't found in either namespace, it's definitely
2266             // unresolved.
2267             (None, None) => { return Failed; }
2268             // If it's private, it's also unresolved.
2269             (Some(t), None) | (None, Some(t)) => {
2270                 match t.bindings.type_def {
2271                     Some(ref type_def) => {
2272                         if type_def.privacy == Private {
2273                             return Failed;
2274                         }
2275                     }
2276                     _ => ()
2277                 }
2278                 match t.bindings.value_def {
2279                     Some(ref value_def) => {
2280                         if value_def.privacy == Private {
2281                             return Failed;
2282                         }
2283                     }
2284                     _ => ()
2285                 }
2286             }
2287             // It's also an error if there's both a type and a value with this
2288             // name, but both are private
2289             (Some(val), Some(ty)) => {
2290                 match (val.bindings.value_def, ty.bindings.value_def) {
2291                     (Some(ref value_def), Some(ref type_def)) =>
2292                         if value_def.privacy == Private
2293                             && type_def.privacy == Private {
2294                             return Failed;
2295                         },
2296                     _ => ()
2297                 }
2298             }
2299         }
2300
2301         assert import_resolution.outstanding_references >= 1;
2302         import_resolution.outstanding_references -= 1;
2303
2304         debug!("(resolving single import) successfully resolved import");
2305         return Success(());
2306     }
2307
2308     fn resolve_single_module_import(module_: @Module,
2309                                     containing_module: @Module,
2310                                     target: ident,
2311                                     source: ident)
2312                                  -> ResolveResult<()> {
2313
2314         debug!("(resolving single module import) resolving `%s` = `%s::%s` \
2315                 from `%s`",
2316                self.session.str_of(target),
2317                self.module_to_str(containing_module),
2318                self.session.str_of(source),
2319                self.module_to_str(module_));
2320
2321         // We need to resolve the module namespace for this to succeed.
2322         let mut module_result = UnknownResult;
2323
2324         // Search for direct children of the containing module.
2325         match containing_module.children.find(&source) {
2326             None => {
2327                 // Continue.
2328             }
2329             Some(child_name_bindings) => {
2330                 if (*child_name_bindings).defined_in_namespace(TypeNS) {
2331                     module_result = BoundResult(containing_module,
2332                                                 child_name_bindings);
2333                 }
2334             }
2335         }
2336
2337         // Unless we managed to find a result, search imports as well.
2338         match module_result {
2339             BoundResult(*) => {
2340                 // Continue.
2341             }
2342             _ => {
2343                 // If there is an unresolved glob at this point in the
2344                 // containing module, bail out. We don't know enough to be
2345                 // able to resolve this import.
2346
2347                 if containing_module.glob_count > 0 {
2348                     debug!("(resolving single module import) unresolved \
2349                             glob; bailing out");
2350                     return Indeterminate;
2351                 }
2352
2353                 // Now search the exported imports within the containing
2354                 // module.
2355                 match containing_module.import_resolutions.find(&source) {
2356                     None => {
2357                         // The containing module definitely doesn't have an
2358                         // exported import with the name in question. We can
2359                         // therefore accurately report that the names are
2360                         // unbound.
2361
2362                         if module_result.is_unknown() {
2363                             module_result = UnboundResult;
2364                         }
2365                     }
2366                     Some(import_resolution)
2367                             if import_resolution.outstanding_references
2368                                 == 0 => {
2369                         // The name is an import which has been fully
2370                         // resolved. We can, therefore, just follow it.
2371
2372                         if module_result.is_unknown() {
2373                             match (*import_resolution).target_for_namespace(
2374                                     TypeNS) {
2375                                 None => {
2376                                     module_result = UnboundResult;
2377                                 }
2378                                 Some(target) => {
2379                                     import_resolution.state.used = true;
2380                                     module_result = BoundResult
2381                                         (target.target_module,
2382                                          target.bindings);
2383                                 }
2384                             }
2385                         }
2386                     }
2387                     Some(_) => {
2388                         // The import is unresolved. Bail out.
2389                         debug!("(resolving single module import) unresolved \
2390                                 import; bailing out");
2391                         return Indeterminate;
2392                     }
2393                 }
2394             }
2395         }
2396
2397         // We've successfully resolved the import. Write the results in.
2398         assert module_.import_resolutions.contains_key(&target);
2399         let import_resolution = module_.import_resolutions.get(&target);
2400
2401         match module_result {
2402             BoundResult(target_module, name_bindings) => {
2403                 debug!("(resolving single import) found module binding");
2404                 import_resolution.type_target =
2405                     Some(Target(target_module, name_bindings));
2406             }
2407             UnboundResult => {
2408                 debug!("(resolving single import) didn't find module \
2409                         binding");
2410             }
2411             UnknownResult => {
2412                 fail!(~"module result should be known at this point");
2413             }
2414         }
2415
2416         let i = import_resolution;
2417         if i.type_target.is_none() {
2418           // If this name wasn't found in the type namespace, it's
2419           // definitely unresolved.
2420           return Failed;
2421         }
2422
2423         assert import_resolution.outstanding_references >= 1;
2424         import_resolution.outstanding_references -= 1;
2425
2426         debug!("(resolving single module import) successfully resolved \
2427                import");
2428         return Success(());
2429     }
2430
2431
2432     /**
2433      * Resolves a glob import. Note that this function cannot fail; it either
2434      * succeeds or bails out (as importing * from an empty module or a module
2435      * that exports nothing is valid).
2436      */
2437     fn resolve_glob_import(privacy: Privacy,
2438                            module_: @Module,
2439                            containing_module: @Module,
2440                            span: span)
2441                         -> ResolveResult<()> {
2442         // This function works in a highly imperative manner; it eagerly adds
2443         // everything it can to the list of import resolutions of the module
2444         // node.
2445         debug!("(resolving glob import) resolving %? glob import", privacy);
2446         let state = @mut ImportState();
2447
2448         // We must bail out if the node has unresolved imports of any kind
2449         // (including globs).
2450         if !(*containing_module).all_imports_resolved() {
2451             debug!("(resolving glob import) target module has unresolved \
2452                     imports; bailing out");
2453             return Indeterminate;
2454         }
2455
2456         assert containing_module.glob_count == 0;
2457
2458         // Add all resolved imports from the containing module.
2459         for containing_module.import_resolutions.each
2460                 |&ident, &target_import_resolution| {
2461
2462             debug!("(resolving glob import) writing module resolution \
2463                     %? into `%s`",
2464                    is_none(&target_import_resolution.type_target),
2465                    self.module_to_str(module_));
2466
2467             // Here we merge two import resolutions.
2468             match module_.import_resolutions.find(&ident) {
2469                 None => {
2470                     // Simple: just copy the old import resolution.
2471                     let new_import_resolution =
2472                         @mut ImportResolution(privacy,
2473                                               target_import_resolution.span,
2474                                               state);
2475                     new_import_resolution.value_target =
2476                         copy target_import_resolution.value_target;
2477                     new_import_resolution.type_target =
2478                         copy target_import_resolution.type_target;
2479
2480                     module_.import_resolutions.insert
2481                         (ident, new_import_resolution);
2482                 }
2483                 Some(dest_import_resolution) => {
2484                     // Merge the two import resolutions at a finer-grained
2485                     // level.
2486
2487                     match copy target_import_resolution.value_target {
2488                         None => {
2489                             // Continue.
2490                         }
2491                         Some(value_target) => {
2492                             dest_import_resolution.value_target =
2493                                 Some(copy value_target);
2494                         }
2495                     }
2496                     match copy target_import_resolution.type_target {
2497                         None => {
2498                             // Continue.
2499                         }
2500                         Some(type_target) => {
2501                             dest_import_resolution.type_target =
2502                                 Some(copy type_target);
2503                         }
2504                     }
2505                 }
2506             }
2507         }
2508
2509         // Add all children from the containing module.
2510         for containing_module.children.each |&ident, &name_bindings| {
2511             let mut dest_import_resolution;
2512             match module_.import_resolutions.find(&ident) {
2513                 None => {
2514                     // Create a new import resolution from this child.
2515                     dest_import_resolution = @mut ImportResolution(privacy,
2516                                                                    span,
2517                                                                    state);
2518                     module_.import_resolutions.insert
2519                         (ident, dest_import_resolution);
2520                 }
2521                 Some(existing_import_resolution) => {
2522                     dest_import_resolution = existing_import_resolution;
2523                 }
2524             }
2525
2526
2527             debug!("(resolving glob import) writing resolution `%s` in `%s` \
2528                     to `%s`, privacy=%?",
2529                    self.session.str_of(ident),
2530                    self.module_to_str(containing_module),
2531                    self.module_to_str(module_),
2532                    dest_import_resolution.privacy);
2533
2534             // Merge the child item into the import resolution.
2535             if (*name_bindings).defined_in_namespace(ValueNS) {
2536                 debug!("(resolving glob import) ... for value target");
2537                 dest_import_resolution.value_target =
2538                     Some(Target(containing_module, name_bindings));
2539             }
2540             if (*name_bindings).defined_in_namespace(TypeNS) {
2541                 debug!("(resolving glob import) ... for type target");
2542                 dest_import_resolution.type_target =
2543                     Some(Target(containing_module, name_bindings));
2544             }
2545         }
2546
2547         debug!("(resolving glob import) successfully resolved import");
2548         return Success(());
2549     }
2550
2551     fn resolve_module_path_from_root(module_: @Module,
2552                                      module_path: @DVec<ident>,
2553                                      index: uint,
2554                                      span: span)
2555                                   -> ResolveResult<@Module> {
2556         let mut search_module = module_;
2557         let mut index = index;
2558         let module_path_len = (*module_path).len();
2559
2560         // Resolve the module part of the path. This does not involve looking
2561         // upward though scope chains; we simply resolve names directly in
2562         // modules as we go.
2563
2564         while index < module_path_len {
2565             let name = (*module_path).get_elt(index);
2566             match self.resolve_name_in_module(search_module,
2567                                               name,
2568                                               TypeNS,
2569                                               false) {
2570                 Failed => {
2571                     self.session.span_err(span, ~"unresolved name");
2572                     return Failed;
2573                 }
2574                 Indeterminate => {
2575                     debug!("(resolving module path for import) module \
2576                             resolution is indeterminate: %s",
2577                             self.session.str_of(name));
2578                     return Indeterminate;
2579                 }
2580                 Success(target) => {
2581                     // Check to see whether there are type bindings, and, if
2582                     // so, whether there is a module within.
2583                     match target.bindings.type_def {
2584                         Some(copy type_def) => {
2585                             match type_def.module_def {
2586                                 None => {
2587                                     // Not a module.
2588                                     self.session.span_err(span,
2589                                                           fmt!("not a \
2590                                                                 module: %s",
2591                                                                self.session.
2592                                                                    str_of(
2593                                                                     name)));
2594                                     return Failed;
2595                                 }
2596                                 Some(copy module_def) => {
2597                                     search_module = module_def;
2598                                 }
2599                             }
2600                         }
2601                         None => {
2602                             // There are no type bindings at all.
2603                             self.session.span_err(span,
2604                                                   fmt!("not a module: %s",
2605                                                        self.session.str_of(
2606                                                             name)));
2607                             return Failed;
2608                         }
2609                     }
2610                 }
2611             }
2612
2613             index += 1;
2614         }
2615
2616         return Success(search_module);
2617     }
2618
2619     /**
2620      * Attempts to resolve the module part of an import directive or path
2621      * rooted at the given module.
2622      */
2623     fn resolve_module_path_for_import(module_: @Module,
2624                                       module_path: @DVec<ident>,
2625                                       use_lexical_scope: UseLexicalScopeFlag,
2626                                       span: span)
2627                                    -> ResolveResult<@Module> {
2628
2629         let module_path_len = (*module_path).len();
2630         assert module_path_len > 0;
2631
2632         debug!("(resolving module path for import) processing `%s` rooted at \
2633                `%s`",
2634                self.idents_to_str((*module_path).get()),
2635                self.module_to_str(module_));
2636
2637         // Resolve the module prefix, if any.
2638         let module_prefix_result = self.resolve_module_prefix(module_,
2639                                                               module_path);
2640
2641         let mut search_module;
2642         let mut start_index;
2643         match module_prefix_result {
2644             Failed => {
2645                 self.session.span_err(span, ~"unresolved name");
2646                 return Failed;
2647             }
2648             Indeterminate => {
2649                 debug!("(resolving module path for import) indeterminate; \
2650                         bailing");
2651                 return Indeterminate;
2652             }
2653             Success(NoPrefixFound) => {
2654                 // There was no prefix, so we're considering the first element
2655                 // of the path. How we handle this depends on whether we were
2656                 // instructed to use lexical scope or not.
2657                 match use_lexical_scope {
2658                     DontUseLexicalScope => {
2659                         // This is a crate-relative path. We will start the
2660                         // resolution process at index zero.
2661                         search_module = self.graph_root.get_module();
2662                         start_index = 0;
2663                     }
2664                     UseLexicalScope => {
2665                         // This is not a crate-relative path. We resolve the
2666                         // first component of the path in the current lexical
2667                         // scope and then proceed to resolve below that.
2668                         let result = self.resolve_module_in_lexical_scope(
2669                             module_,
2670                             module_path.get_elt(0));
2671                         match result {
2672                             Failed => {
2673                                 self.session.span_err(span,
2674                                                       ~"unresolved name");
2675                                 return Failed;
2676                             }
2677                             Indeterminate => {
2678                                 debug!("(resolving module path for import) \
2679                                         indeterminate; bailing");
2680                                 return Indeterminate;
2681                             }
2682                             Success(containing_module) => {
2683                                 search_module = containing_module;
2684                                 start_index = 1;
2685                             }
2686                         }
2687                     }
2688                 }
2689             }
2690             Success(PrefixFound(containing_module, index)) => {
2691                 search_module = containing_module;
2692                 start_index = index;
2693             }
2694         }
2695
2696         return self.resolve_module_path_from_root(search_module,
2697                                                   module_path,
2698                                                   start_index,
2699                                                   span);
2700     }
2701
2702     fn resolve_item_in_lexical_scope(module_: @Module,
2703                                      name: ident,
2704                                      namespace: Namespace,
2705                                      search_through_modules:
2706                                         SearchThroughModulesFlag)
2707                                   -> ResolveResult<Target> {
2708
2709         debug!("(resolving item in lexical scope) resolving `%s` in \
2710                 namespace %? in `%s`",
2711                self.session.str_of(name),
2712                namespace,
2713                self.module_to_str(module_));
2714
2715         // The current module node is handled specially. First, check for
2716         // its immediate children.
2717
2718         match module_.children.find(&name) {
2719             Some(name_bindings)
2720                     if (*name_bindings).defined_in_namespace(namespace) => {
2721                 return Success(Target(module_, name_bindings));
2722             }
2723             Some(_) | None => { /* Not found; continue. */ }
2724         }
2725
2726         // Now check for its import directives. We don't have to have resolved
2727         // all its imports in the usual way; this is because chains of
2728         // adjacent import statements are processed as though they mutated the
2729         // current scope.
2730
2731         match module_.import_resolutions.find(&name) {
2732             None => {
2733                 // Not found; continue.
2734             }
2735             Some(import_resolution) => {
2736                 match (*import_resolution).target_for_namespace(namespace) {
2737                     None => {
2738                         // Not found; continue.
2739                         debug!("(resolving item in lexical scope) found \
2740                                 import resolution, but not in namespace %?",
2741                                namespace);
2742                     }
2743                     Some(target) => {
2744                         import_resolution.state.used = true;
2745                         return Success(copy target);
2746                     }
2747                 }
2748             }
2749         }
2750
2751         // Finally, proceed up the scope chain looking for parent modules.
2752         let mut search_module = module_;
2753         loop {
2754             // Go to the next parent.
2755             match search_module.parent_link {
2756                 NoParentLink => {
2757                     // No more parents. This module was unresolved.
2758                     debug!("(resolving item in lexical scope) unresolved \
2759                             module");
2760                     return Failed;
2761                 }
2762                 ModuleParentLink(parent_module_node, _) => {
2763                     match search_through_modules {
2764                         DontSearchThroughModules => {
2765                             match search_module.kind {
2766                                 NormalModuleKind => {
2767                                     // We stop the search here.
2768                                     debug!("(resolving item in lexical \
2769                                             scope) unresolved module: not \
2770                                             searching through module \
2771                                             parents");
2772                                     return Failed;
2773                                 }
2774                                 ExternModuleKind |
2775                                 TraitModuleKind |
2776                                 AnonymousModuleKind => {
2777                                     search_module = parent_module_node;
2778                                 }
2779                             }
2780                         }
2781                         SearchThroughModules => {
2782                             search_module = parent_module_node;
2783                         }
2784                     }
2785                 }
2786                 BlockParentLink(parent_module_node, _) => {
2787                     search_module = parent_module_node;
2788                 }
2789             }
2790
2791             // Resolve the name in the parent module.
2792             match self.resolve_name_in_module(search_module,
2793                                               name,
2794                                               namespace,
2795                                               false) {
2796                 Failed => {
2797                     // Continue up the search chain.
2798                 }
2799                 Indeterminate => {
2800                     // We couldn't see through the higher scope because of an
2801                     // unresolved import higher up. Bail.
2802
2803                     debug!("(resolving item in lexical scope) indeterminate \
2804                             higher scope; bailing");
2805                     return Indeterminate;
2806                 }
2807                 Success(target) => {
2808                     // We found the module.
2809                     return Success(copy target);
2810                 }
2811             }
2812         }
2813     }
2814
2815     /** Resolves a module name in the current lexical scope. */
2816     fn resolve_module_in_lexical_scope(module_: @Module, name: ident)
2817                                     -> ResolveResult<@Module> {
2818         // If this module is an anonymous module, resolve the item in the
2819         // lexical scope. Otherwise, resolve the item from the crate root.
2820         let resolve_result = self.resolve_item_in_lexical_scope(
2821             module_, name, TypeNS, DontSearchThroughModules);
2822         match resolve_result {
2823             Success(target) => {
2824                 match target.bindings.type_def {
2825                     Some(ref type_def) => {
2826                         match (*type_def).module_def {
2827                             None => {
2828                                 error!("!!! (resolving module in lexical \
2829                                         scope) module wasn't actually a \
2830                                         module!");
2831                                 return Failed;
2832                             }
2833                             Some(module_def) => {
2834                                 return Success(module_def);
2835                             }
2836                         }
2837                     }
2838                     None => {
2839                         error!("!!! (resolving module in lexical scope) module
2840                                 wasn't actually a module!");
2841                         return Failed;
2842                     }
2843                 }
2844             }
2845             Indeterminate => {
2846                 debug!("(resolving module in lexical scope) indeterminate; \
2847                         bailing");
2848                 return Indeterminate;
2849             }
2850             Failed => {
2851                 debug!("(resolving module in lexical scope) failed to \
2852                         resolve");
2853                 return Failed;
2854             }
2855         }
2856     }
2857
2858     /**
2859      * Returns the nearest normal module parent of the given module.
2860      */
2861     fn get_nearest_normal_module_parent(module_: @Module) -> Option<@Module> {
2862         let mut module_ = module_;
2863         loop {
2864             match module_.parent_link {
2865                 NoParentLink => return None,
2866                 ModuleParentLink(new_module, _) |
2867                 BlockParentLink(new_module, _) => {
2868                     match new_module.kind {
2869                         NormalModuleKind => return Some(new_module),
2870                         ExternModuleKind |
2871                         TraitModuleKind |
2872                         AnonymousModuleKind => module_ = new_module,
2873                     }
2874                 }
2875             }
2876         }
2877     }
2878
2879     /**
2880      * Returns the nearest normal module parent of the given module, or the
2881      * module itself if it is a normal module.
2882      */
2883     fn get_nearest_normal_module_parent_or_self(module_: @Module) -> @Module {
2884         match module_.kind {
2885             NormalModuleKind => return module_,
2886             ExternModuleKind | TraitModuleKind | AnonymousModuleKind => {
2887                 match self.get_nearest_normal_module_parent(module_) {
2888                     None => module_,
2889                     Some(new_module) => new_module
2890                 }
2891             }
2892         }
2893     }
2894
2895     /**
2896      * Resolves a "module prefix". A module prefix is one of (a) `self::`;
2897      * (b) some chain of `super::`.
2898      */
2899     fn resolve_module_prefix(module_: @Module,
2900                              module_path: @DVec<ident>)
2901                           -> ResolveResult<ModulePrefixResult> {
2902         let interner = self.session.parse_sess.interner;
2903
2904         // Start at the current module if we see `self` or `super`, or at the
2905         // top of the crate otherwise.
2906         let mut containing_module;
2907         let mut i;
2908         if *interner.get(module_path.get_elt(0)) == ~"self" {
2909             containing_module =
2910                 self.get_nearest_normal_module_parent_or_self(module_);
2911             i = 1;
2912         } else if *interner.get(module_path.get_elt(0)) == ~"super" {
2913             containing_module =
2914                 self.get_nearest_normal_module_parent_or_self(module_);
2915             i = 0;  // We'll handle `super` below.
2916         } else {
2917             return Success(NoPrefixFound);
2918         }
2919
2920         // Now loop through all the `super`s we find.
2921         while i < module_path.len() &&
2922                 *interner.get(module_path.get_elt(i)) == ~"super" {
2923             debug!("(resolving module prefix) resolving `super` at %s",
2924                    self.module_to_str(containing_module));
2925             match self.get_nearest_normal_module_parent(containing_module) {
2926                 None => return Failed,
2927                 Some(new_module) => {
2928                     containing_module = new_module;
2929                     i += 1;
2930                 }
2931             }
2932         }
2933
2934         debug!("(resolving module prefix) finished resolving prefix at %s",
2935                self.module_to_str(containing_module));
2936
2937         return Success(PrefixFound(containing_module, i));
2938     }
2939
2940     /**
2941      * Attempts to resolve the supplied name in the given module for the
2942      * given namespace. If successful, returns the target corresponding to
2943      * the name.
2944      */
2945     fn resolve_name_in_module(module_: @Module,
2946                               name: ident,
2947                               namespace: Namespace,
2948                               allow_globs: bool)
2949                            -> ResolveResult<Target> {
2950         debug!("(resolving name in module) resolving `%s` in `%s`",
2951                self.session.str_of(name),
2952                self.module_to_str(module_));
2953
2954         // First, check the direct children of the module.
2955         match module_.children.find(&name) {
2956             Some(name_bindings)
2957                     if (*name_bindings).defined_in_namespace(namespace) => {
2958
2959                 debug!("(resolving name in module) found node as child");
2960                 return Success(Target(module_, name_bindings));
2961             }
2962             Some(_) | None => {
2963                 // Continue.
2964             }
2965         }
2966
2967         // Next, check the module's imports. If the module has a glob and
2968         // globs were not allowed, then we bail out; we don't know its imports
2969         // yet.
2970         if !allow_globs && module_.glob_count > 0 {
2971             debug!("(resolving name in module) module has glob; bailing out");
2972             return Indeterminate;
2973         }
2974
2975         // Otherwise, we check the list of resolved imports.
2976         match module_.import_resolutions.find(&name) {
2977             Some(import_resolution) => {
2978                 if import_resolution.outstanding_references != 0 {
2979                     debug!("(resolving name in module) import unresolved; \
2980                             bailing out");
2981                     return Indeterminate;
2982                 }
2983
2984                 match (*import_resolution).target_for_namespace(namespace) {
2985                     None => {
2986                         debug!("(resolving name in module) name found, but \
2987                                 not in namespace %?",
2988                                namespace);
2989                     }
2990                     Some(target) => {
2991                         debug!("(resolving name in module) resolved to \
2992                                 import");
2993                         import_resolution.state.used = true;
2994                         return Success(copy target);
2995                     }
2996                 }
2997             }
2998             None => {
2999                 // Continue.
3000             }
3001         }
3002
3003         // We're out of luck.
3004         debug!("(resolving name in module) failed to resolve %s",
3005                self.session.str_of(name));
3006         return Failed;
3007     }
3008
3009     /**
3010      * Resolves a one-level renaming import of the kind `import foo = bar;`
3011      * This needs special handling, as, unlike all of the other imports, it
3012      * needs to look in the scope chain for modules and non-modules alike.
3013      */
3014     fn resolve_one_level_renaming_import(module_: @Module,
3015                                          import_directive: @ImportDirective)
3016                                       -> ResolveResult<()> {
3017
3018         let mut target_name;
3019         let mut source_name;
3020         let allowable_namespaces;
3021         match *import_directive.subclass {
3022             SingleImport(target, source, namespaces) => {
3023                 target_name = target;
3024                 source_name = source;
3025                 allowable_namespaces = namespaces;
3026             }
3027             GlobImport => {
3028                 fail!(~"found `import *`, which is invalid");
3029             }
3030         }
3031
3032         debug!("(resolving one-level naming result) resolving import `%s` = \
3033                 `%s` in `%s`",
3034                 self.session.str_of(target_name),
3035                 self.session.str_of(source_name),
3036                 self.module_to_str(module_));
3037
3038         // Find the matching items in the lexical scope chain for every
3039         // namespace. If any of them come back indeterminate, this entire
3040         // import is indeterminate.
3041
3042         let mut module_result;
3043         debug!("(resolving one-level naming result) searching for module");
3044         match self.resolve_item_in_lexical_scope(module_,
3045                                                  source_name,
3046                                                  TypeNS,
3047                                                  SearchThroughModules) {
3048             Failed => {
3049                 debug!("(resolving one-level renaming import) didn't find \
3050                         module result");
3051                 module_result = None;
3052             }
3053             Indeterminate => {
3054                 debug!("(resolving one-level renaming import) module result \
3055                         is indeterminate; bailing");
3056                 return Indeterminate;
3057             }
3058             Success(name_bindings) => {
3059                 debug!("(resolving one-level renaming import) module result \
3060                         found");
3061                 module_result = Some(copy name_bindings);
3062             }
3063         }
3064
3065         let mut value_result;
3066         let mut type_result;
3067         if allowable_namespaces == TypeNSOnly {
3068             value_result = None;
3069             type_result = None;
3070         } else {
3071             debug!("(resolving one-level naming result) searching for value");
3072             match self.resolve_item_in_lexical_scope(module_,
3073                                                      source_name,
3074                                                      ValueNS,
3075                                                      SearchThroughModules) {
3076
3077                 Failed => {
3078                     debug!("(resolving one-level renaming import) didn't \
3079                             find value result");
3080                     value_result = None;
3081                 }
3082                 Indeterminate => {
3083                     debug!("(resolving one-level renaming import) value \
3084                             result is indeterminate; bailing");
3085                     return Indeterminate;
3086                 }
3087                 Success(name_bindings) => {
3088                     debug!("(resolving one-level renaming import) value \
3089                             result found");
3090                     value_result = Some(copy name_bindings);
3091                 }
3092             }
3093
3094             debug!("(resolving one-level naming result) searching for type");
3095             match self.resolve_item_in_lexical_scope(module_,
3096                                                      source_name,
3097                                                      TypeNS,
3098                                                      SearchThroughModules) {
3099
3100                 Failed => {
3101                     debug!("(resolving one-level renaming import) didn't \
3102                             find type result");
3103                     type_result = None;
3104                 }
3105                 Indeterminate => {
3106                     debug!("(resolving one-level renaming import) type \
3107                             result is indeterminate; bailing");
3108                     return Indeterminate;
3109                 }
3110                 Success(name_bindings) => {
3111                     debug!("(resolving one-level renaming import) type \
3112                             result found");
3113                     type_result = Some(copy name_bindings);
3114                 }
3115             }
3116         }
3117
3118         //
3119         // NB: This one results in effects that may be somewhat surprising. It
3120         // means that this:
3121         //
3122         // mod A {
3123         //     impl foo for ... { ... }
3124         //     mod B {
3125         //         impl foo for ... { ... }
3126         //         import bar = foo;
3127         //         ...
3128         //     }
3129         // }
3130         //
3131         // results in only A::B::foo being aliased to A::B::bar, not A::foo
3132         // *and* A::B::foo being aliased to A::B::bar.
3133         //
3134
3135         // If nothing at all was found, that's an error.
3136         if is_none(&module_result) &&
3137                 is_none(&value_result) &&
3138                 is_none(&type_result) {
3139
3140             self.session.span_err(import_directive.span,
3141                                   ~"unresolved import");
3142             return Failed;
3143         }
3144
3145         // Otherwise, proceed and write in the bindings.
3146         match module_.import_resolutions.find(&target_name) {
3147             None => {
3148                 fail!(~"(resolving one-level renaming import) reduced graph \
3149                       construction or glob importing should have created the \
3150                       import resolution name by now");
3151             }
3152             Some(import_resolution) => {
3153                 debug!("(resolving one-level renaming import) writing module \
3154                         result %? for `%s` into `%s`",
3155                        is_none(&module_result),
3156                        self.session.str_of(target_name),
3157                        self.module_to_str(module_));
3158
3159                 import_resolution.value_target = value_result;
3160                 import_resolution.type_target = type_result;
3161
3162                 assert import_resolution.outstanding_references >= 1;
3163                 import_resolution.outstanding_references -= 1;
3164             }
3165         }
3166
3167         debug!("(resolving one-level renaming import) successfully resolved");
3168         return Success(());
3169     }
3170
3171     fn report_unresolved_imports(module_: @Module) {
3172         let index = module_.resolved_import_count;
3173         let import_count = module_.imports.len();
3174         if index != import_count {
3175             self.session.span_err(module_.imports.get_elt(index).span,
3176                                   ~"unresolved import");
3177         }
3178
3179         // Descend into children and anonymous children.
3180         for module_.children.each_value |&child_node| {
3181             match child_node.get_module_if_available() {
3182                 None => {
3183                     // Continue.
3184                 }
3185                 Some(child_module) => {
3186                     self.report_unresolved_imports(child_module);
3187                 }
3188             }
3189         }
3190
3191         for module_.anonymous_children.each_value |&module_| {
3192             self.report_unresolved_imports(module_);
3193         }
3194     }
3195
3196     // Export recording
3197     //
3198     // This pass simply determines what all "export" keywords refer to and
3199     // writes the results into the export map.
3200     //
3201     // FIXME #4953 This pass will be removed once exports change to per-item.
3202     // Then this operation can simply be performed as part of item (or import)
3203     // processing.
3204
3205     fn record_exports() {
3206         let root_module = self.graph_root.get_module();
3207         self.record_exports_for_module_subtree(root_module);
3208     }
3209
3210     fn record_exports_for_module_subtree(module_: @Module) {
3211         // If this isn't a local crate, then bail out. We don't need to record
3212         // exports for nonlocal crates.
3213
3214         match module_.def_id {
3215             Some(def_id) if def_id.crate == local_crate => {
3216                 // OK. Continue.
3217                 debug!("(recording exports for module subtree) recording \
3218                         exports for local module");
3219             }
3220             None => {
3221                 // Record exports for the root module.
3222                 debug!("(recording exports for module subtree) recording \
3223                         exports for root module");
3224             }
3225             Some(_) => {
3226                 // Bail out.
3227                 debug!("(recording exports for module subtree) not recording \
3228                         exports for `%s`",
3229                        self.module_to_str(module_));
3230                 return;
3231             }
3232         }
3233
3234         self.record_exports_for_module(module_);
3235
3236         for module_.children.each_value |&child_name_bindings| {
3237             match child_name_bindings.get_module_if_available() {
3238                 None => {
3239                     // Nothing to do.
3240                 }
3241                 Some(child_module) => {
3242                     self.record_exports_for_module_subtree(child_module);
3243                 }
3244             }
3245         }
3246
3247         for module_.anonymous_children.each_value |&child_module| {
3248             self.record_exports_for_module_subtree(child_module);
3249         }
3250     }
3251
3252     fn record_exports_for_module(module_: @Module) {
3253         let mut exports2 = ~[];
3254
3255         self.add_exports_for_module(&mut exports2, module_);
3256         match copy module_.def_id {
3257             Some(def_id) => {
3258                 self.export_map2.insert(def_id.node, exports2);
3259                 debug!("(computing exports) writing exports for %d (some)",
3260                        def_id.node);
3261             }
3262             None => {}
3263         }
3264     }
3265
3266
3267     fn add_exports_of_namebindings(exports2: &mut ~[Export2],
3268                                    ident: ident,
3269                                    namebindings: @mut NameBindings,
3270                                    ns: Namespace,
3271                                    reexport: bool) {
3272         match (namebindings.def_for_namespace(ns),
3273                namebindings.privacy_for_namespace(ns)) {
3274             (Some(d), Some(Public)) => {
3275                 debug!("(computing exports) YES: %s '%s' => %?",
3276                        if reexport { ~"reexport" } else { ~"export"},
3277                        self.session.str_of(ident),
3278                        def_id_of_def(d));
3279                 exports2.push(Export2 {
3280                     reexport: reexport,
3281                     name: self.session.str_of(ident),
3282                     def_id: def_id_of_def(d)
3283                 });
3284             }
3285             (Some(_), Some(privacy)) => {
3286                 debug!("(computing reexports) NO: privacy %?", privacy);
3287             }
3288             (d_opt, p_opt) => {
3289                 debug!("(computing reexports) NO: %?, %?", d_opt, p_opt);
3290             }
3291         }
3292     }
3293
3294     fn add_exports_for_module(exports2: &mut ~[Export2], module_: @Module) {
3295         for module_.children.each |ident, namebindings| {
3296             debug!("(computing exports) maybe export '%s'",
3297                    self.session.str_of(*ident));
3298             self.add_exports_of_namebindings(&mut *exports2,
3299                                              *ident,
3300                                              *namebindings,
3301                                              TypeNS,
3302                                              false);
3303             self.add_exports_of_namebindings(&mut *exports2,
3304                                              *ident,
3305                                              *namebindings,
3306                                              ValueNS,
3307                                              false);
3308         }
3309
3310         for module_.import_resolutions.each |ident, importresolution| {
3311             if importresolution.privacy != Public {
3312                 debug!("(computing exports) not reexporting private `%s`",
3313                        self.session.str_of(*ident));
3314                 loop;
3315             }
3316             for [ TypeNS, ValueNS ].each |ns| {
3317                 match importresolution.target_for_namespace(*ns) {
3318                     Some(target) => {
3319                         debug!("(computing exports) maybe reexport '%s'",
3320                                self.session.str_of(*ident));
3321                         self.add_exports_of_namebindings(&mut *exports2,
3322                                                          *ident,
3323                                                          target.bindings,
3324                                                          *ns,
3325                                                          true)
3326                     }
3327                     _ => ()
3328                 }
3329             }
3330         }
3331     }
3332
3333     // AST resolution
3334     //
3335     // We maintain a list of value ribs and type ribs.
3336     //
3337     // Simultaneously, we keep track of the current position in the module
3338     // graph in the `current_module` pointer. When we go to resolve a name in
3339     // the value or type namespaces, we first look through all the ribs and
3340     // then query the module graph. When we resolve a name in the module
3341     // namespace, we can skip all the ribs (since nested modules are not
3342     // allowed within blocks in Rust) and jump straight to the current module
3343     // graph node.
3344     //
3345     // Named implementations are handled separately. When we find a method
3346     // call, we consult the module node to find all of the implementations in
3347     // scope. This information is lazily cached in the module node. We then
3348     // generate a fake "implementation scope" containing all the
3349     // implementations thus found, for compatibility with old resolve pass.
3350
3351     fn with_scope(name: Option<ident>, f: fn()) {
3352         let orig_module = self.current_module;
3353
3354         // Move down in the graph.
3355         match name {
3356             None => {
3357                 // Nothing to do.
3358             }
3359             Some(name) => {
3360                 match orig_module.children.find(&name) {
3361                     None => {
3362                         debug!("!!! (with scope) didn't find `%s` in `%s`",
3363                                self.session.str_of(name),
3364                                self.module_to_str(orig_module));
3365                     }
3366                     Some(name_bindings) => {
3367                         match (*name_bindings).get_module_if_available() {
3368                             None => {
3369                                 debug!("!!! (with scope) didn't find module \
3370                                         for `%s` in `%s`",
3371                                        self.session.str_of(name),
3372                                        self.module_to_str(orig_module));
3373                             }
3374                             Some(module_) => {
3375                                 self.current_module = module_;
3376                             }
3377                         }
3378                     }
3379                 }
3380             }
3381         }
3382
3383         f();
3384
3385         self.current_module = orig_module;
3386     }
3387
3388     // Wraps the given definition in the appropriate number of `def_upvar`
3389     // wrappers.
3390
3391     fn upvarify(ribs: @DVec<@Rib>, rib_index: uint, def_like: def_like,
3392                 span: span, allow_capturing_self: AllowCapturingSelfFlag)
3393              -> Option<def_like> {
3394
3395         let mut def;
3396         let mut is_ty_param;
3397
3398         match def_like {
3399             dl_def(d @ def_local(*)) | dl_def(d @ def_upvar(*)) |
3400             dl_def(d @ def_arg(*)) | dl_def(d @ def_binding(*)) => {
3401                 def = d;
3402                 is_ty_param = false;
3403             }
3404             dl_def(d @ def_ty_param(*)) => {
3405                 def = d;
3406                 is_ty_param = true;
3407             }
3408             dl_def(d @ def_self(*))
3409                     if allow_capturing_self == DontAllowCapturingSelf => {
3410                 def = d;
3411                 is_ty_param = false;
3412             }
3413             _ => {
3414                 return Some(def_like);
3415             }
3416         }
3417
3418         let mut rib_index = rib_index + 1;
3419         while rib_index < (*ribs).len() {
3420             let rib = (*ribs).get_elt(rib_index);
3421             match rib.kind {
3422                 NormalRibKind => {
3423                     // Nothing to do. Continue.
3424                 }
3425                 FunctionRibKind(function_id, body_id) => {
3426                     if !is_ty_param {
3427                         def = def_upvar(def_id_of_def(def).node,
3428                                         @def,
3429                                         function_id,
3430                                         body_id);
3431                     }
3432                 }
3433                 MethodRibKind(item_id, _) => {
3434                   // If the def is a ty param, and came from the parent
3435                   // item, it's ok
3436                   match def {
3437                     def_ty_param(did, _) if self.def_map.find(&did.node)
3438                       == Some(def_typaram_binder(item_id)) => {
3439                       // ok
3440                     }
3441                     _ => {
3442                     if !is_ty_param {
3443                         // This was an attempt to access an upvar inside a
3444                         // named function item. This is not allowed, so we
3445                         // report an error.
3446
3447                         self.session.span_err(
3448                             span,
3449                             ~"attempted dynamic environment-capture");
3450                     } else {
3451                         // This was an attempt to use a type parameter outside
3452                         // its scope.
3453
3454                         self.session.span_err(span,
3455                                               ~"attempt to use a type \
3456                                                argument out of scope");
3457                     }
3458
3459                     return None;
3460                     }
3461                   }
3462                 }
3463                 OpaqueFunctionRibKind => {
3464                     if !is_ty_param {
3465                         // This was an attempt to access an upvar inside a
3466                         // named function item. This is not allowed, so we
3467                         // report an error.
3468
3469                         self.session.span_err(
3470                             span,
3471                             ~"attempted dynamic environment-capture");
3472                     } else {
3473                         // This was an attempt to use a type parameter outside
3474                         // its scope.
3475
3476                         self.session.span_err(span,
3477                                               ~"attempt to use a type \
3478                                                argument out of scope");
3479                     }
3480
3481                     return None;
3482                 }
3483                 ConstantItemRibKind => {
3484                     // Still doesn't deal with upvars
3485                     self.session.span_err(span,
3486                                           ~"attempt to use a non-constant \
3487                                             value in a constant");
3488
3489                 }
3490             }
3491
3492             rib_index += 1;
3493         }
3494
3495         return Some(dl_def(def));
3496     }
3497
3498     fn search_ribs(ribs: @DVec<@Rib>, name: ident, span: span,
3499                    allow_capturing_self: AllowCapturingSelfFlag)
3500                 -> Option<def_like> {
3501
3502         // FIXME #4950: This should not use a while loop.
3503         // FIXME #4950: Try caching?
3504
3505         let mut i = (*ribs).len();
3506         while i != 0 {
3507             i -= 1;
3508             let rib = (*ribs).get_elt(i);
3509             match rib.bindings.find(&name) {
3510                 Some(def_like) => {
3511                     return self.upvarify(ribs, i, def_like, span,
3512                                       allow_capturing_self);
3513                 }
3514                 None => {
3515                     // Continue.
3516                 }
3517             }
3518         }
3519
3520         return None;
3521     }
3522
3523     fn resolve_crate(@self) {
3524         debug!("(resolving crate) starting");
3525
3526         visit_crate(*self.crate, (), mk_vt(@Visitor {
3527             visit_item: |item, _context, visitor|
3528                 self.resolve_item(item, visitor),
3529             visit_arm: |arm, _context, visitor|
3530                 self.resolve_arm(arm, visitor),
3531             visit_block: |block, _context, visitor|
3532                 self.resolve_block(block, visitor),
3533             visit_expr: |expr, _context, visitor|
3534                 self.resolve_expr(expr, visitor),
3535             visit_local: |local, _context, visitor|
3536                 self.resolve_local(local, visitor),
3537             visit_ty: |ty, _context, visitor|
3538                 self.resolve_type(ty, visitor),
3539             .. *default_visitor()
3540         }));
3541     }
3542
3543     fn resolve_item(item: @item, visitor: ResolveVisitor) {
3544         debug!("(resolving item) resolving %s",
3545                self.session.str_of(item.ident));
3546
3547         // Items with the !resolve_unexported attribute are X-ray contexts.
3548         // This is used to allow the test runner to run unexported tests.
3549         let orig_xray_flag = self.xray_context;
3550         if contains_name(attr_metas(/*bad*/copy item.attrs),
3551                          ~"!resolve_unexported") {
3552             self.xray_context = Xray;
3553         }
3554
3555         match /*bad*/copy item.node {
3556
3557             // enum item: resolve all the variants' discrs,
3558             // then resolve the ty params
3559             item_enum(ref enum_def, ref type_parameters) => {
3560
3561                 for (*enum_def).variants.each() |variant| {
3562                     do variant.node.disr_expr.iter() |dis_expr| {
3563                         // resolve the discriminator expr
3564                         // as a constant
3565                         self.with_constant_rib(|| {
3566                             self.resolve_expr(*dis_expr, visitor);
3567                         });
3568                     }
3569                 }
3570
3571                 // n.b. the discr expr gets visted twice.
3572                 // but maybe it's okay since the first time will signal an
3573                 // error if there is one? -- tjc
3574                 do self.with_type_parameter_rib(
3575                     HasTypeParameters(
3576                         type_parameters, item.id, 0, NormalRibKind)) {
3577                     visit_item(item, (), visitor);
3578                 }
3579             }
3580
3581             item_ty(_, type_parameters) => {
3582                 do self.with_type_parameter_rib
3583                         (HasTypeParameters(&type_parameters, item.id, 0,
3584                                            NormalRibKind))
3585                         || {
3586
3587                     visit_item(item, (), visitor);
3588                 }
3589             }
3590
3591             item_impl(type_parameters,
3592                       implemented_traits,
3593                       self_type,
3594                       methods) => {
3595                 self.resolve_implementation(item.id,
3596                                             item.span,
3597                                             type_parameters,
3598                                             implemented_traits,
3599                                             self_type,
3600                                             methods,
3601                                             visitor);
3602             }
3603
3604             item_trait(ref type_parameters, ref traits, ref methods) => {
3605                 // Create a new rib for the self type.
3606                 let self_type_rib = @Rib(NormalRibKind);
3607                 (*self.type_ribs).push(self_type_rib);
3608                 self_type_rib.bindings.insert(self.type_self_ident,
3609                                               dl_def(def_self_ty(item.id)));
3610
3611                 // Create a new rib for the trait-wide type parameters.
3612                 do self.with_type_parameter_rib
3613                         (HasTypeParameters(type_parameters, item.id, 0,
3614                                            NormalRibKind)) {
3615
3616                     self.resolve_type_parameters(/*bad*/copy *type_parameters,
3617                                                  visitor);
3618
3619                     // Resolve derived traits.
3620                     for traits.each |trt| {
3621                         match self.resolve_path(trt.path, TypeNS, true,
3622                                                 visitor) {
3623                             None =>
3624                                 self.session.span_err(trt.path.span,
3625                                                       ~"attempt to derive a \
3626                                                        nonexistent trait"),
3627                             Some(def) => {
3628                                 // Write a mapping from the trait ID to the
3629                                 // definition of the trait into the definition
3630                                 // map.
3631
3632                                 debug!("(resolving trait) found trait def: \
3633                                        %?", def);
3634
3635                                 self.record_def(trt.ref_id, def);
3636                             }
3637                         }
3638                     }
3639
3640                     for (*methods).each |method| {
3641                         // Create a new rib for the method-specific type
3642                         // parameters.
3643                         //
3644                         // FIXME #4951: Do we need a node ID here?
3645
3646                         match *method {
3647                           required(ref ty_m) => {
3648                             do self.with_type_parameter_rib
3649                                 (HasTypeParameters(&(*ty_m).tps,
3650                                                    item.id,
3651                                                    type_parameters.len(),
3652                                         MethodRibKind(item.id, Required))) {
3653
3654                                 // Resolve the method-specific type
3655                                 // parameters.
3656                                 self.resolve_type_parameters(
3657                                     /*bad*/copy (*ty_m).tps,
3658                                     visitor);
3659
3660                                 for (*ty_m).decl.inputs.each |argument| {
3661                                     self.resolve_type(argument.ty, visitor);
3662                                 }
3663
3664                                 self.resolve_type(ty_m.decl.output, visitor);
3665                             }
3666                           }
3667                           provided(m) => {
3668                               self.resolve_method(MethodRibKind(item.id,
3669                                                      Provided(m.id)),
3670                                                   m,
3671                                                   type_parameters.len(),
3672                                                   visitor)
3673                           }
3674                         }
3675                     }
3676                 }
3677
3678                 (*self.type_ribs).pop();
3679             }
3680
3681             item_struct(struct_def, ty_params) => {
3682                 self.resolve_struct(item.id,
3683                                    @copy ty_params,
3684                                    /*bad*/copy struct_def.fields,
3685                                    struct_def.dtor,
3686                                    visitor);
3687             }
3688
3689             item_mod(module_) => {
3690                 do self.with_scope(Some(item.ident)) {
3691                     self.resolve_module(module_, item.span, item.ident,
3692                                         item.id, visitor);
3693                 }
3694             }
3695
3696             item_foreign_mod(foreign_module) => {
3697                 do self.with_scope(Some(item.ident)) {
3698                     for foreign_module.items.each |foreign_item| {
3699                         match /*bad*/copy foreign_item.node {
3700                             foreign_item_fn(_, _, type_parameters) => {
3701                                 do self.with_type_parameter_rib
3702                                     (HasTypeParameters(&type_parameters,
3703                                                        foreign_item.id,
3704                                                        0,
3705                                                        OpaqueFunctionRibKind))
3706                                         || {
3707
3708                                     visit_foreign_item(*foreign_item, (),
3709                                                        visitor);
3710                                 }
3711                             }
3712                             foreign_item_const(_) => {
3713                                 visit_foreign_item(*foreign_item, (),
3714                                                    visitor);
3715                             }
3716                         }
3717                     }
3718                 }
3719             }
3720
3721             item_fn(ref fn_decl, _, ref ty_params, ref block) => {
3722                 // If this is the main function, we must record it in the
3723                 // session.
3724                 // FIXME #4404 android JNI hacks
3725                 if !*self.session.building_library ||
3726                     self.session.targ_cfg.os == session::os_android {
3727
3728                     if self.attr_main_fn.is_none() &&
3729                            item.ident == special_idents::main {
3730
3731                         self.main_fns.push(Some((item.id, item.span)));
3732                     }
3733
3734                     if attrs_contains_name(item.attrs, ~"main") {
3735                         if self.attr_main_fn.is_none() {
3736                             self.attr_main_fn = Some((item.id, item.span));
3737                         } else {
3738                             self.session.span_err(
3739                                     item.span,
3740                                     ~"multiple 'main' functions");
3741                         }
3742                     }
3743                 }
3744
3745                 self.resolve_function(OpaqueFunctionRibKind,
3746                                       Some(@/*bad*/copy *fn_decl),
3747                                       HasTypeParameters
3748                                         (ty_params,
3749                                          item.id,
3750                                          0,
3751                                          OpaqueFunctionRibKind),
3752                                       (*block),
3753                                       NoSelfBinding,
3754                                       visitor);
3755             }
3756
3757             item_const(*) => {
3758                 self.with_constant_rib(|| {
3759                     visit_item(item, (), visitor);
3760                 });
3761             }
3762
3763           item_mac(*) => {
3764             fail!(~"item macros unimplemented")
3765           }
3766         }
3767
3768         self.xray_context = orig_xray_flag;
3769     }
3770
3771     fn with_type_parameter_rib(type_parameters: TypeParameters, f: fn()) {
3772         match type_parameters {
3773             HasTypeParameters(type_parameters, node_id, initial_index,
3774                               rib_kind) => {
3775
3776                 let function_type_rib = @Rib(rib_kind);
3777                 (*self.type_ribs).push(function_type_rib);
3778
3779                 for (*type_parameters).eachi |index, type_parameter| {
3780                     let name = type_parameter.ident;
3781                     debug!("with_type_parameter_rib: %d %d", node_id,
3782                            type_parameter.id);
3783                     let def_like = dl_def(def_ty_param
3784                         (local_def(type_parameter.id),
3785                          index + initial_index));
3786                     // Associate this type parameter with
3787                     // the item that bound it
3788                     self.record_def(type_parameter.id,
3789                                     def_typaram_binder(node_id));
3790                     (*function_type_rib).bindings.insert(name, def_like);
3791                 }
3792             }
3793
3794             NoTypeParameters => {
3795                 // Nothing to do.
3796             }
3797         }
3798
3799         f();
3800
3801         match type_parameters {
3802             HasTypeParameters(*) => {
3803                 (*self.type_ribs).pop();
3804             }
3805
3806             NoTypeParameters => {
3807                 // Nothing to do.
3808             }
3809         }
3810     }
3811
3812     fn with_label_rib(f: fn()) {
3813         (*self.label_ribs).push(@Rib(NormalRibKind));
3814         f();
3815         (*self.label_ribs).pop();
3816     }
3817     fn with_constant_rib(f: fn()) {
3818         (*self.value_ribs).push(@Rib(ConstantItemRibKind));
3819         f();
3820         (*self.value_ribs).pop();
3821     }
3822
3823
3824     fn resolve_function(rib_kind: RibKind,
3825                         optional_declaration: Option<@fn_decl>,
3826                         type_parameters: TypeParameters,
3827                         block: blk,
3828                         self_binding: SelfBinding,
3829                         visitor: ResolveVisitor) {
3830         // Create a value rib for the function.
3831         let function_value_rib = @Rib(rib_kind);
3832         (*self.value_ribs).push(function_value_rib);
3833
3834         // Create a label rib for the function.
3835         let function_label_rib = @Rib(rib_kind);
3836         (*self.label_ribs).push(function_label_rib);
3837
3838         // If this function has type parameters, add them now.
3839         do self.with_type_parameter_rib(type_parameters) {
3840             // Resolve the type parameters.
3841             match type_parameters {
3842                 NoTypeParameters => {
3843                     // Continue.
3844                 }
3845                 HasTypeParameters(type_parameters, _, _, _) => {
3846                     self.resolve_type_parameters(/*bad*/copy *type_parameters,
3847                                                  visitor);
3848                 }
3849             }
3850
3851             // Add self to the rib, if necessary.
3852             match self_binding {
3853                 NoSelfBinding => {
3854                     // Nothing to do.
3855                 }
3856                 HasSelfBinding(self_node_id, is_implicit) => {
3857                     let def_like = dl_def(def_self(self_node_id,
3858                                                    is_implicit));
3859                     (*function_value_rib).bindings.insert(self.self_ident,
3860                                                           def_like);
3861                 }
3862             }
3863
3864             // Add each argument to the rib.
3865             match optional_declaration {
3866                 None => {
3867                     // Nothing to do.
3868                 }
3869                 Some(declaration) => {
3870                     for declaration.inputs.each |argument| {
3871                         let binding_mode =
3872                             ArgumentIrrefutableMode(argument.mode);
3873                         let mutability =
3874                             if argument.is_mutbl {Mutable} else {Immutable};
3875                         self.resolve_pattern(argument.pat,
3876                                              binding_mode,
3877                                              mutability,
3878                                              None,
3879                                              visitor);
3880
3881                         self.resolve_type(argument.ty, visitor);
3882
3883                         debug!("(resolving function) recorded argument");
3884                     }
3885
3886                     self.resolve_type(declaration.output, visitor);
3887                 }
3888             }
3889
3890             // Resolve the function body.
3891             self.resolve_block(block, visitor);
3892
3893             debug!("(resolving function) leaving function");
3894         }
3895
3896         (*self.label_ribs).pop();
3897         (*self.value_ribs).pop();
3898     }
3899
3900     fn resolve_type_parameters(type_parameters: ~[ty_param],
3901                                visitor: ResolveVisitor) {
3902         for type_parameters.each |type_parameter| {
3903             for type_parameter.bounds.each |&bound| {
3904                 match bound {
3905                     TraitTyParamBound(ty) => self.resolve_type(ty, visitor),
3906                     RegionTyParamBound => {}
3907                 }
3908             }
3909         }
3910     }
3911
3912     fn resolve_struct(id: node_id,
3913                      type_parameters: @~[ty_param],
3914                      fields: ~[@struct_field],
3915                      optional_destructor: Option<struct_dtor>,
3916                      visitor: ResolveVisitor) {
3917         // If applicable, create a rib for the type parameters.
3918         let borrowed_type_parameters: &~[ty_param] = &*type_parameters;
3919         do self.with_type_parameter_rib(HasTypeParameters
3920                                         (borrowed_type_parameters, id, 0,
3921                                          OpaqueFunctionRibKind)) {
3922
3923             // Resolve the type parameters.
3924             self.resolve_type_parameters(/*bad*/copy *type_parameters,
3925                                          visitor);
3926
3927             // Resolve fields.
3928             for fields.each |field| {
3929                 self.resolve_type(field.node.ty, visitor);
3930             }
3931
3932             // Resolve the destructor, if applicable.
3933             match optional_destructor {
3934                 None => {
3935                     // Nothing to do.
3936                 }
3937                 Some(ref destructor) => {
3938                     self.resolve_function(NormalRibKind,
3939                                           None,
3940                                           NoTypeParameters,
3941                                           (*destructor).node.body,
3942                                           HasSelfBinding
3943                                             ((*destructor).node.self_id,
3944                                              true),
3945                                           visitor);
3946                 }
3947             }
3948         }
3949     }
3950
3951     // Does this really need to take a RibKind or is it always going
3952     // to be NormalRibKind?
3953     fn resolve_method(rib_kind: RibKind,
3954                       method: @method,
3955                       outer_type_parameter_count: uint,
3956                       visitor: ResolveVisitor) {
3957         let borrowed_method_type_parameters = &method.tps;
3958         let type_parameters =
3959             HasTypeParameters(borrowed_method_type_parameters,
3960                               method.id,
3961                               outer_type_parameter_count,
3962                               rib_kind);
3963         // we only have self ty if it is a non static method
3964         let self_binding = match method.self_ty.node {
3965           sty_static => { NoSelfBinding }
3966           sty_by_ref => { HasSelfBinding(method.self_id, true) }
3967           _ => { HasSelfBinding(method.self_id, false) }
3968         };
3969
3970         self.resolve_function(rib_kind,
3971                               Some(@/*bad*/copy method.decl),
3972                               type_parameters,
3973                               method.body,
3974                               self_binding,
3975                               visitor);
3976     }
3977
3978     fn resolve_implementation(id: node_id,
3979                               span: span,
3980                               type_parameters: ~[ty_param],
3981                               opt_trait_reference: Option<@trait_ref>,
3982                               self_type: @Ty,
3983                               methods: ~[@method],
3984                               visitor: ResolveVisitor) {
3985         // If applicable, create a rib for the type parameters.
3986         let outer_type_parameter_count = type_parameters.len();
3987         let borrowed_type_parameters: &~[ty_param] = &type_parameters;
3988         do self.with_type_parameter_rib(HasTypeParameters
3989                                         (borrowed_type_parameters, id, 0,
3990                                          NormalRibKind)) {
3991             // Resolve the type parameters.
3992             self.resolve_type_parameters(/*bad*/copy type_parameters,
3993                                          visitor);
3994
3995             // Resolve the trait reference, if necessary.
3996             let original_trait_refs = self.current_trait_refs;
3997             match opt_trait_reference {
3998                 Some(trait_reference) => {
3999                     let new_trait_refs = @DVec();
4000                     match self.resolve_path(
4001                         trait_reference.path, TypeNS, true, visitor) {
4002                         None => {
4003                             self.session.span_err(span,
4004                                                   ~"attempt to implement an \
4005                                                     unknown trait");
4006                         }
4007                         Some(def) => {
4008                             self.record_def(trait_reference.ref_id, def);
4009
4010                             // Record the current trait reference.
4011                             (*new_trait_refs).push(def_id_of_def(def));
4012                         }
4013                     }
4014                     // Record the current set of trait references.
4015                     self.current_trait_refs = Some(new_trait_refs);
4016                 }
4017                 None => ()
4018             }
4019
4020             // Resolve the self type.
4021             self.resolve_type(self_type, visitor);
4022
4023             for methods.each |method| {
4024                 // We also need a new scope for the method-specific
4025                 // type parameters.
4026                 self.resolve_method(MethodRibKind(
4027                     id,
4028                     Provided(method.id)),
4029                     *method,
4030                     outer_type_parameter_count,
4031                     visitor);
4032 /*
4033                     let borrowed_type_parameters = &method.tps;
4034                     self.resolve_function(MethodRibKind(
4035                                           id,
4036                                           Provided(method.id)),
4037                                           Some(@method.decl),
4038                                           HasTypeParameters
4039                                             (borrowed_type_parameters,
4040                                              method.id,
4041                                              outer_type_parameter_count,
4042                                              NormalRibKind),
4043                                           method.body,
4044                                           HasSelfBinding(method.self_id),
4045                                           visitor);
4046 */
4047             }
4048
4049             // Restore the original trait references.
4050             self.current_trait_refs = original_trait_refs;
4051         }
4052     }
4053
4054     fn resolve_module(module_: _mod, span: span, _name: ident, id: node_id,
4055                       visitor: ResolveVisitor) {
4056
4057         // Write the implementations in scope into the module metadata.
4058         debug!("(resolving module) resolving module ID %d", id);
4059         visit_mod(module_, span, id, (), visitor);
4060     }
4061
4062     fn resolve_local(local: @local, visitor: ResolveVisitor) {
4063         let mutability = if local.node.is_mutbl {Mutable} else {Immutable};
4064
4065         // Resolve the type.
4066         self.resolve_type(local.node.ty, visitor);
4067
4068         // Resolve the initializer, if necessary.
4069         match local.node.init {
4070             None => {
4071                 // Nothing to do.
4072             }
4073             Some(initializer) => {
4074                 self.resolve_expr(initializer, visitor);
4075             }
4076         }
4077
4078         // Resolve the pattern.
4079         self.resolve_pattern(local.node.pat, LocalIrrefutableMode, mutability,
4080                              None, visitor);
4081     }
4082
4083     fn binding_mode_map(pat: @pat) -> BindingMap {
4084         let result = HashMap();
4085         do pat_bindings(self.def_map, pat) |binding_mode, _id, sp, path| {
4086             let ident = path_to_ident(path);
4087             result.insert(ident,
4088                           binding_info {span: sp,
4089                                         binding_mode: binding_mode});
4090         }
4091         return result;
4092     }
4093
4094     fn check_consistent_bindings(arm: arm) {
4095         if arm.pats.len() == 0 { return; }
4096         let map_0 = self.binding_mode_map(arm.pats[0]);
4097         for arm.pats.eachi() |i, p| {
4098             let map_i = self.binding_mode_map(*p);
4099
4100             for map_0.each |&key, &binding_0| {
4101                 match map_i.find(&key) {
4102                   None => {
4103                     self.session.span_err(
4104                         p.span,
4105                         fmt!("variable `%s` from pattern #1 is \
4106                                   not bound in pattern #%u",
4107                              self.session.str_of(key), i + 1));
4108                   }
4109                   Some(binding_i) => {
4110                     if binding_0.binding_mode != binding_i.binding_mode {
4111                         self.session.span_err(
4112                             binding_i.span,
4113                             fmt!("variable `%s` is bound with different \
4114                                       mode in pattern #%u than in pattern #1",
4115                                  self.session.str_of(key), i + 1));
4116                     }
4117                   }
4118                 }
4119             }
4120
4121             for map_i.each |&key, &binding| {
4122                 if !map_0.contains_key(&key) {
4123                     self.session.span_err(
4124                         binding.span,
4125                         fmt!("variable `%s` from pattern #%u is \
4126                                   not bound in pattern #1",
4127                              self.session.str_of(key), i + 1));
4128                 }
4129             }
4130         }
4131     }
4132
4133     fn resolve_arm(arm: arm, visitor: ResolveVisitor) {
4134         (*self.value_ribs).push(@Rib(NormalRibKind));
4135
4136         let bindings_list = HashMap();
4137         for arm.pats.each |pattern| {
4138             self.resolve_pattern(*pattern, RefutableMode, Immutable,
4139                                  Some(bindings_list), visitor);
4140         }
4141
4142         // This has to happen *after* we determine which
4143         // pat_idents are variants
4144         self.check_consistent_bindings(arm);
4145
4146         visit_expr_opt(arm.guard, (), visitor);
4147         self.resolve_block(arm.body, visitor);
4148
4149         (*self.value_ribs).pop();
4150     }
4151
4152     fn resolve_block(block: blk, visitor: ResolveVisitor) {
4153         debug!("(resolving block) entering block");
4154         (*self.value_ribs).push(@Rib(NormalRibKind));
4155
4156         // Move down in the graph, if there's an anonymous module rooted here.
4157         let orig_module = self.current_module;
4158         match self.current_module.anonymous_children.find(&block.node.id) {
4159             None => { /* Nothing to do. */ }
4160             Some(anonymous_module) => {
4161                 debug!("(resolving block) found anonymous module, moving \
4162                         down");
4163                 self.current_module = anonymous_module;
4164             }
4165         }
4166
4167         // Descend into the block.
4168         visit_block(block, (), visitor);
4169
4170         // Move back up.
4171         self.current_module = orig_module;
4172
4173         (*self.value_ribs).pop();
4174         debug!("(resolving block) leaving block");
4175     }
4176
4177     fn resolve_type(ty: @Ty, visitor: ResolveVisitor) {
4178         match ty.node {
4179             // Like path expressions, the interpretation of path types depends
4180             // on whether the path has multiple elements in it or not.
4181
4182             ty_path(path, path_id) => {
4183                 // This is a path in the type namespace. Walk through scopes
4184                 // scopes looking for it.
4185                 let mut result_def = None;
4186
4187                 // First, check to see whether the name is a primitive type.
4188                 if path.idents.len() == 1 {
4189                     let name = path.idents.last();
4190
4191                     match self.primitive_type_table
4192                             .primitive_types
4193                             .find(&name) {
4194
4195                         Some(primitive_type) => {
4196                             result_def =
4197                                 Some(def_prim_ty(primitive_type));
4198                         }
4199                         None => {
4200                             // Continue.
4201                         }
4202                     }
4203                 }
4204
4205                 match result_def {
4206                     None => {
4207                         match self.resolve_path(path, TypeNS, true, visitor) {
4208                             Some(def) => {
4209                                 debug!("(resolving type) resolved `%s` to \
4210                                         type %?",
4211                                        self.session.str_of(
4212                                             path.idents.last()),
4213                                        def);
4214                                 result_def = Some(def);
4215                             }
4216                             None => {
4217                                 result_def = None;
4218                             }
4219                         }
4220                     }
4221                     Some(_) => {
4222                         // Continue.
4223                     }
4224                 }
4225
4226                 match copy result_def {
4227                     Some(def) => {
4228                         // Write the result into the def map.
4229                         debug!("(resolving type) writing resolution for `%s` \
4230                                 (id %d)",
4231                                self.idents_to_str(path.idents),
4232                                path_id);
4233                         self.record_def(path_id, def);
4234                     }
4235                     None => {
4236                         self.session.span_err
4237                             (ty.span, fmt!("use of undeclared type name `%s`",
4238                                            self.idents_to_str(path.idents)));
4239                     }
4240                 }
4241             }
4242
4243             _ => {
4244                 // Just resolve embedded types.
4245                 visit_ty(ty, (), visitor);
4246             }
4247         }
4248     }
4249
4250     fn resolve_pattern(pattern: @pat,
4251                        mode: PatternBindingMode,
4252                        mutability: Mutability,
4253                        // Maps idents to the node ID for the (outermost)
4254                        // pattern that binds them
4255                        bindings_list: Option<HashMap<ident,node_id>>,
4256                        visitor: ResolveVisitor) {
4257
4258         let pat_id = pattern.id;
4259         do walk_pat(pattern) |pattern| {
4260             match pattern.node {
4261                 pat_ident(binding_mode, path, _)
4262                         if !path.global && path.idents.len() == 1 => {
4263
4264                     // The meaning of pat_ident with no type parameters
4265                     // depends on whether an enum variant or unit-like struct
4266                     // with that name is in scope. The probing lookup has to
4267                     // be careful not to emit spurious errors. Only matching
4268                     // patterns (match) can match nullary variants or
4269                     // unit-like structs. For binding patterns (let), matching
4270                     // such a value is simply disallowed (since it's rarely
4271                     // what you want).
4272
4273                     let ident = path.idents[0];
4274
4275                     match self.resolve_bare_identifier_pattern(ident) {
4276                         FoundStructOrEnumVariant(def)
4277                                 if mode == RefutableMode => {
4278                             debug!("(resolving pattern) resolving `%s` to \
4279                                     struct or enum variant",
4280                                     self.session.str_of(ident));
4281
4282                             self.enforce_default_binding_mode(
4283                                 pattern,
4284                                 binding_mode,
4285                                 "an enum variant");
4286                             self.record_def(pattern.id, def);
4287                         }
4288                         FoundStructOrEnumVariant(_) => {
4289                             self.session.span_err(pattern.span,
4290                                                   fmt!("declaration of `%s` \
4291                                                         shadows an enum \
4292                                                         variant or unit-like \
4293                                                         struct in scope",
4294                                                         self.session
4295                                                         .str_of(ident)));
4296                         }
4297                         FoundConst(def) if mode == RefutableMode => {
4298                             debug!("(resolving pattern) resolving `%s` to \
4299                                     constant",
4300                                     self.session.str_of(ident));
4301
4302                             self.enforce_default_binding_mode(
4303                                 pattern,
4304                                 binding_mode,
4305                                 "a constant");
4306                             self.record_def(pattern.id, def);
4307                         }
4308                         FoundConst(_) => {
4309                             self.session.span_err(pattern.span,
4310                                                   ~"only refutable patterns \
4311                                                     allowed here");
4312                         }
4313                         BareIdentifierPatternUnresolved => {
4314                             debug!("(resolving pattern) binding `%s`",
4315                                    self.session.str_of(ident));
4316
4317                             let is_mutable = mutability == Mutable;
4318
4319                             let def = match mode {
4320                                 RefutableMode => {
4321                                     // For pattern arms, we must use
4322                                     // `def_binding` definitions.
4323
4324                                     def_binding(pattern.id, binding_mode)
4325                                 }
4326                                 LocalIrrefutableMode => {
4327                                     // But for locals, we use `def_local`.
4328                                     def_local(pattern.id, is_mutable)
4329                                 }
4330                                 ArgumentIrrefutableMode(argument_mode) => {
4331                                     // And for function arguments, `def_arg`.
4332                                     def_arg(pattern.id, argument_mode,
4333                                             is_mutable)
4334                                 }
4335                             };
4336
4337                             // Record the definition so that later passes
4338                             // will be able to distinguish variants from
4339                             // locals in patterns.
4340
4341                             self.record_def(pattern.id, def);
4342
4343                             // Add the binding to the local ribs, if it
4344                             // doesn't already exist in the bindings list. (We
4345                             // must not add it if it's in the bindings list
4346                             // because that breaks the assumptions later
4347                             // passes make about or-patterns.)
4348
4349                             match bindings_list {
4350                                 Some(bindings_list)
4351                                 if !bindings_list.contains_key(&ident)
4352                                     => {
4353                                     let last_rib = (*self.value_ribs).last();
4354                                     last_rib.bindings.insert(ident,
4355                                                              dl_def(def));
4356                                     bindings_list.insert(ident, pat_id);
4357                                 }
4358                                 Some(b) => {
4359                                   if b.find(&ident) == Some(pat_id) {
4360                                       // Then this is a duplicate variable
4361                                       // in the same disjunct, which is an
4362                                       // error
4363                                      self.session.span_err(pattern.span,
4364                                        fmt!("Identifier %s is bound more \
4365                                              than once in the same pattern",
4366                                             path_to_str(path, self.session
4367                                                         .intr())));
4368                                   }
4369                                   // Not bound in the same pattern: do nothing
4370                                 }
4371                                 None => {
4372                                     let last_rib = (*self.value_ribs).last();
4373                                     last_rib.bindings.insert(ident,
4374                                                              dl_def(def));
4375                                 }
4376                             }
4377                         }
4378                     }
4379
4380                     // Check the types in the path pattern.
4381                     for path.types.each |ty| {
4382                         self.resolve_type(*ty, visitor);
4383                     }
4384                 }
4385
4386                 pat_ident(_, path, _) | pat_enum(path, _) => {
4387                     // These two must be enum variants or structs.
4388                     match self.resolve_path(path, ValueNS, false, visitor) {
4389                         Some(def @ def_variant(*)) |
4390                                 Some(def @ def_struct(*)) => {
4391                             self.record_def(pattern.id, def);
4392                         }
4393                         Some(_) => {
4394                             self.session.span_err(
4395                                 path.span,
4396                                 fmt!("not an enum variant: %s",
4397                                      self.session.str_of(
4398                                          path.idents.last())));
4399                         }
4400                         None => {
4401                             self.session.span_err(path.span,
4402                                                   ~"unresolved enum variant");
4403                         }
4404                     }
4405
4406                     // Check the types in the path pattern.
4407                     for path.types.each |ty| {
4408                         self.resolve_type(*ty, visitor);
4409                     }
4410                 }
4411
4412                 pat_lit(expr) => {
4413                     self.resolve_expr(expr, visitor);
4414                 }
4415
4416                 pat_range(first_expr, last_expr) => {
4417                     self.resolve_expr(first_expr, visitor);
4418                     self.resolve_expr(last_expr, visitor);
4419                 }
4420
4421                 pat_struct(path, _, _) => {
4422                     match self.resolve_path(path, TypeNS, false, visitor) {
4423                         Some(def_ty(class_id))
4424                                 if self.structs.contains_key(&class_id)
4425                                      => {
4426                             let class_def = def_struct(class_id);
4427                             self.record_def(pattern.id, class_def);
4428                         }
4429                         Some(definition @ def_struct(class_id))
4430                                 if self.structs.contains_key(&class_id)
4431                                      => {
4432                             self.record_def(pattern.id, definition);
4433                         }
4434                         Some(definition @ def_variant(_, variant_id))
4435                                 if self.structs.contains_key(&variant_id)
4436                                      => {
4437                             self.record_def(pattern.id, definition);
4438                         }
4439                         result => {
4440                             debug!("(resolving pattern) didn't find struct \
4441                                     def: %?", result);
4442                             self.session.span_err(
4443                                 path.span,
4444                                 fmt!("`%s` does not name a structure",
4445                                      self.idents_to_str(path.idents)));
4446                         }
4447                     }
4448                 }
4449
4450                 _ => {
4451                     // Nothing to do.
4452                 }
4453             }
4454         }
4455     }
4456
4457     fn resolve_bare_identifier_pattern(name: ident)
4458                                     -> BareIdentifierPatternResolution {
4459         match self.resolve_item_in_lexical_scope(self.current_module,
4460                                                  name,
4461                                                  ValueNS,
4462                                                  SearchThroughModules) {
4463             Success(target) => {
4464                 match target.bindings.value_def {
4465                     None => {
4466                         fail!(~"resolved name in the value namespace to a \
4467                               set of name bindings with no def?!");
4468                     }
4469                     Some(def) => {
4470                         match def.def {
4471                             def @ def_variant(*) | def @ def_struct(*) => {
4472                                 return FoundStructOrEnumVariant(def);
4473                             }
4474                             def @ def_const(*) => {
4475                                 return FoundConst(def);
4476                             }
4477                             _ => {
4478                                 return BareIdentifierPatternUnresolved;
4479                             }
4480                         }
4481                     }
4482                 }
4483             }
4484
4485             Indeterminate => {
4486                 fail!(~"unexpected indeterminate result");
4487             }
4488
4489             Failed => {
4490                 return BareIdentifierPatternUnresolved;
4491             }
4492         }
4493     }
4494
4495     /**
4496      * If `check_ribs` is true, checks the local definitions first; i.e.
4497      * doesn't skip straight to the containing module.
4498      */
4499     fn resolve_path(path: @path,
4500                     namespace: Namespace,
4501                     check_ribs: bool,
4502                     visitor: ResolveVisitor)
4503                  -> Option<def> {
4504         // First, resolve the types.
4505         for path.types.each |ty| {
4506             self.resolve_type(*ty, visitor);
4507         }
4508
4509         if path.global {
4510             return self.resolve_crate_relative_path(path,
4511                                                  self.xray_context,
4512                                                  namespace);
4513         }
4514
4515         if path.idents.len() > 1 {
4516             return self.resolve_module_relative_path(path,
4517                                                      self.xray_context,
4518                                                      namespace);
4519         }
4520
4521         return self.resolve_identifier(path.idents.last(),
4522                                        namespace,
4523                                        check_ribs,
4524                                        path.span);
4525     }
4526
4527     fn resolve_identifier(identifier: ident,
4528                           namespace: Namespace,
4529                           check_ribs: bool,
4530                           span: span)
4531                        -> Option<def> {
4532
4533         if check_ribs {
4534             match self.resolve_identifier_in_local_ribs(identifier,
4535                                                       namespace,
4536                                                       span) {
4537                 Some(def) => {
4538                     return Some(def);
4539                 }
4540                 None => {
4541                     // Continue.
4542                 }
4543             }
4544         }
4545
4546         return self.resolve_item_by_identifier_in_lexical_scope(identifier,
4547                                                                 namespace);
4548     }
4549
4550     // FIXME #4952: Merge me with resolve_name_in_module?
4551     fn resolve_definition_of_name_in_module(containing_module: @Module,
4552                                             name: ident,
4553                                             namespace: Namespace,
4554                                             xray: XrayFlag)
4555                                          -> NameDefinition {
4556
4557         // First, search children.
4558         match containing_module.children.find(&name) {
4559             Some(child_name_bindings) => {
4560                 match (child_name_bindings.def_for_namespace(namespace),
4561                        child_name_bindings.privacy_for_namespace(namespace)) {
4562                     (Some(def), Some(Public)) => {
4563                         // Found it. Stop the search here.
4564                         return ChildNameDefinition(def);
4565                     }
4566                     (Some(def), _) if xray == Xray => {
4567                         // Found it. Stop the search here.
4568                         return ChildNameDefinition(def);
4569                     }
4570                     (Some(_), _) | (None, _) => {
4571                         // Continue.
4572                     }
4573                 }
4574             }
4575             None => {
4576                 // Continue.
4577             }
4578         }
4579
4580         // Next, search import resolutions.
4581         match containing_module.import_resolutions.find(&name) {
4582             Some(import_resolution) if import_resolution.privacy == Public ||
4583                                        xray == Xray => {
4584                 match (*import_resolution).target_for_namespace(namespace) {
4585                     Some(target) => {
4586                         match (target.bindings.def_for_namespace(namespace),
4587                                target.bindings.privacy_for_namespace(
4588                                     namespace)) {
4589                             (Some(def), Some(Public)) => {
4590                                 // Found it.
4591                                 import_resolution.state.used = true;
4592                                 return ImportNameDefinition(def);
4593                             }
4594                             (Some(_), _) | (None, _) => {
4595                                 // This can happen with external impls, due to
4596                                 // the imperfect way we read the metadata.
4597
4598                                 return NoNameDefinition;
4599                             }
4600                         }
4601                     }
4602                     None => {
4603                         return NoNameDefinition;
4604                     }
4605                 }
4606             }
4607             Some(_) | None => {
4608                 return NoNameDefinition;
4609             }
4610         }
4611     }
4612
4613     fn intern_module_part_of_path(path: @path) -> @DVec<ident> {
4614         let module_path_idents = @DVec();
4615         for path.idents.eachi |index, ident| {
4616             if index == path.idents.len() - 1 {
4617                 break;
4618             }
4619
4620             (*module_path_idents).push(*ident);
4621         }
4622
4623         return module_path_idents;
4624     }
4625
4626     fn resolve_module_relative_path(path: @path,
4627                                     +xray: XrayFlag,
4628                                     namespace: Namespace)
4629                                  -> Option<def> {
4630
4631         let module_path_idents = self.intern_module_part_of_path(path);
4632
4633         let mut containing_module;
4634         match self.resolve_module_path_for_import(self.current_module,
4635                                                   module_path_idents,
4636                                                   UseLexicalScope,
4637                                                   path.span) {
4638             Failed => {
4639                 self.session.span_err(path.span,
4640                                       fmt!("use of undeclared module `%s`",
4641                                            self.idents_to_str(
4642                                                (*module_path_idents).get())));
4643                 return None;
4644             }
4645
4646             Indeterminate => {
4647                 fail!(~"indeterminate unexpected");
4648             }
4649
4650             Success(resulting_module) => {
4651                 containing_module = resulting_module;
4652             }
4653         }
4654
4655         let name = path.idents.last();
4656         match self.resolve_definition_of_name_in_module(containing_module,
4657                                                         name,
4658                                                         namespace,
4659                                                         xray) {
4660             NoNameDefinition => {
4661                 // We failed to resolve the name. Report an error.
4662                 return None;
4663             }
4664             ChildNameDefinition(def) | ImportNameDefinition(def) => {
4665                 return Some(def);
4666             }
4667         }
4668     }
4669
4670     fn resolve_crate_relative_path(path: @path,
4671                                    +xray: XrayFlag,
4672                                    namespace: Namespace)
4673                                 -> Option<def> {
4674
4675         let module_path_idents = self.intern_module_part_of_path(path);
4676
4677         let root_module = self.graph_root.get_module();
4678
4679         let mut containing_module;
4680         match self.resolve_module_path_from_root(root_module,
4681                                                  module_path_idents,
4682                                                  0,
4683                                                  path.span) {
4684
4685             Failed => {
4686                 self.session.span_err(path.span,
4687                                       fmt!("use of undeclared module `::%s`",
4688                                             self.idents_to_str
4689                                               ((*module_path_idents).get())));
4690                 return None;
4691             }
4692
4693             Indeterminate => {
4694                 fail!(~"indeterminate unexpected");
4695             }
4696
4697             Success(resulting_module) => {
4698                 containing_module = resulting_module;
4699             }
4700         }
4701
4702         let name = path.idents.last();
4703         match self.resolve_definition_of_name_in_module(containing_module,
4704                                                         name,
4705                                                         namespace,
4706                                                         xray) {
4707             NoNameDefinition => {
4708                 // We failed to resolve the name. Report an error.
4709                 return None;
4710             }
4711             ChildNameDefinition(def) | ImportNameDefinition(def) => {
4712                 return Some(def);
4713             }
4714         }
4715     }
4716
4717     fn resolve_identifier_in_local_ribs(ident: ident,
4718                                         namespace: Namespace,
4719                                         span: span)
4720                                      -> Option<def> {
4721         // Check the local set of ribs.
4722         let mut search_result;
4723         match namespace {
4724             ValueNS => {
4725                 search_result = self.search_ribs(self.value_ribs, ident, span,
4726                                                  DontAllowCapturingSelf);
4727             }
4728             TypeNS => {
4729                 search_result = self.search_ribs(self.type_ribs, ident, span,
4730                                                  AllowCapturingSelf);
4731             }
4732         }
4733
4734         match copy search_result {
4735             Some(dl_def(def)) => {
4736                 debug!("(resolving path in local ribs) resolved `%s` to \
4737                         local: %?",
4738                        self.session.str_of(ident),
4739                        def);
4740                 return Some(def);
4741             }
4742             Some(dl_field) | Some(dl_impl(_)) | None => {
4743                 return None;
4744             }
4745         }
4746     }
4747
4748     fn resolve_item_by_identifier_in_lexical_scope(ident: ident,
4749                                                    namespace: Namespace)
4750                                                 -> Option<def> {
4751         // Check the items.
4752         match self.resolve_item_in_lexical_scope(self.current_module,
4753                                                  ident,
4754                                                  namespace,
4755                                                  DontSearchThroughModules) {
4756             Success(target) => {
4757                 match (*target.bindings).def_for_namespace(namespace) {
4758                     None => {
4759                         // This can happen if we were looking for a type and
4760                         // found a module instead. Modules don't have defs.
4761                         return None;
4762                     }
4763                     Some(def) => {
4764                         debug!("(resolving item path in lexical scope) \
4765                                 resolved `%s` to item",
4766                                self.session.str_of(ident));
4767                         return Some(def);
4768                     }
4769                 }
4770             }
4771             Indeterminate => {
4772                 fail!(~"unexpected indeterminate result");
4773             }
4774             Failed => {
4775                 return None;
4776             }
4777         }
4778     }
4779
4780     fn name_exists_in_scope_struct(name: &str) -> bool {
4781         let mut i = self.type_ribs.len();
4782         while i != 0 {
4783           i -= 1;
4784           let rib = self.type_ribs.get_elt(i);
4785           match rib.kind {
4786             MethodRibKind(node_id, _) =>
4787               for vec::each(self.crate.node.module.items) |item| {
4788                 if item.id == node_id {
4789                   match item.node {
4790                     item_struct(class_def, _) => {
4791                       for vec::each(class_def.fields) |field| {
4792                         match field.node.kind {
4793                           unnamed_field => {},
4794                           named_field(ident, _, _) => {
4795                               if str::eq_slice(self.session.str_of(ident),
4796                                                name) {
4797                                 return true
4798                               }
4799                             }
4800                         }
4801                       }
4802                     }
4803                     _ => {}
4804                   }
4805                 }
4806             },
4807           _ => {}
4808         }
4809       }
4810       return false;
4811     }
4812
4813     fn resolve_expr(expr: @expr, visitor: ResolveVisitor) {
4814         // First, record candidate traits for this expression if it could
4815         // result in the invocation of a method call.
4816
4817         self.record_candidate_traits_for_expr_if_necessary(expr);
4818
4819         // Next, resolve the node.
4820         match expr.node {
4821             // The interpretation of paths depends on whether the path has
4822             // multiple elements in it or not.
4823
4824             expr_path(path) => {
4825                 // This is a local path in the value namespace. Walk through
4826                 // scopes looking for it.
4827
4828                 match self.resolve_path(path, ValueNS, true, visitor) {
4829                     Some(def) => {
4830                         // Write the result into the def map.
4831                         debug!("(resolving expr) resolved `%s`",
4832                                self.idents_to_str(path.idents));
4833                         self.record_def(expr.id, def);
4834                     }
4835                     None => {
4836                         let wrong_name = self.idents_to_str(
4837                             /*bad*/copy path.idents);
4838                         if self.name_exists_in_scope_struct(wrong_name) {
4839                             self.session.span_err(expr.span,
4840                                         fmt!("unresolved name: `%s`. \
4841                                             Did you mean: `self.%s`?",
4842                                         wrong_name,
4843                                         wrong_name));
4844                         }
4845                         else {
4846                             self.session.span_err(expr.span,
4847                                                 fmt!("unresolved name: %s",
4848                                                 wrong_name));
4849                         }
4850                     }
4851                 }
4852
4853                 visit_expr(expr, (), visitor);
4854             }
4855
4856             expr_fn(_, ref fn_decl, ref block, _) |
4857             expr_fn_block(ref fn_decl, ref block) => {
4858                 self.resolve_function(FunctionRibKind(expr.id, block.node.id),
4859                                       Some(@/*bad*/copy *fn_decl),
4860                                       NoTypeParameters,
4861                                       (*block),
4862                                       NoSelfBinding,
4863                                       visitor);
4864             }
4865
4866             expr_struct(path, _, _) => {
4867                 // Resolve the path to the structure it goes to.
4868                 match self.resolve_path(path, TypeNS, false, visitor) {
4869                     Some(def_ty(class_id)) | Some(def_struct(class_id))
4870                             if self.structs.contains_key(&class_id) => {
4871                         let class_def = def_struct(class_id);
4872                         self.record_def(expr.id, class_def);
4873                     }
4874                     Some(definition @ def_variant(_, class_id))
4875                             if self.structs.contains_key(&class_id) => {
4876                         self.record_def(expr.id, definition);
4877                     }
4878                     _ => {
4879                         self.session.span_err(
4880                             path.span,
4881                             fmt!("`%s` does not name a structure",
4882                                  self.idents_to_str(path.idents)));
4883                     }
4884                 }
4885
4886                 visit_expr(expr, (), visitor);
4887             }
4888
4889             expr_loop(_, Some(label)) => {
4890                 do self.with_label_rib {
4891                     let def_like = dl_def(def_label(expr.id));
4892                     self.label_ribs.last().bindings.insert(label, def_like);
4893
4894                     visit_expr(expr, (), visitor);
4895                 }
4896             }
4897
4898             expr_break(Some(label)) | expr_again(Some(label)) => {
4899                 match self.search_ribs(self.label_ribs, label, expr.span,
4900                                        DontAllowCapturingSelf) {
4901                     None =>
4902                         self.session.span_err(expr.span,
4903                                               fmt!("use of undeclared label \
4904                                                    `%s`", self.session.str_of(
4905                                                   label))),
4906                     Some(dl_def(def @ def_label(_))) =>
4907                         self.record_def(expr.id, def),
4908                     Some(_) =>
4909                         self.session.span_bug(expr.span,
4910                                               ~"label wasn't mapped to a \
4911                                                 label def!")
4912                 }
4913             }
4914
4915             _ => {
4916                 visit_expr(expr, (), visitor);
4917             }
4918         }
4919     }
4920
4921     fn record_candidate_traits_for_expr_if_necessary(expr: @expr) {
4922         match expr.node {
4923             expr_field(_, ident, _) => {
4924                 let traits = self.search_for_traits_containing_method(ident);
4925                 self.trait_map.insert(expr.id, traits);
4926             }
4927             expr_method_call(_, ident, _, _, _) => {
4928                 let traits = self.search_for_traits_containing_method(ident);
4929                 self.trait_map.insert(expr.id, traits);
4930             }
4931             expr_binary(add, _, _) | expr_assign_op(add, _, _) => {
4932                 self.add_fixed_trait_for_expr(expr.id,
4933                                               self.lang_items.add_trait());
4934             }
4935             expr_binary(subtract, _, _) | expr_assign_op(subtract, _, _) => {
4936                 self.add_fixed_trait_for_expr(expr.id,
4937                                               self.lang_items.sub_trait());
4938             }
4939             expr_binary(mul, _, _) | expr_assign_op(mul, _, _) => {
4940                 self.add_fixed_trait_for_expr(expr.id,
4941                                               self.lang_items.mul_trait());
4942             }
4943             expr_binary(div, _, _) | expr_assign_op(div, _, _) => {
4944                 self.add_fixed_trait_for_expr(expr.id,
4945                                               self.lang_items.div_trait());
4946             }
4947             expr_binary(rem, _, _) | expr_assign_op(rem, _, _) => {
4948                 self.add_fixed_trait_for_expr(expr.id,
4949                                               self.lang_items.modulo_trait());
4950             }
4951             expr_binary(bitxor, _, _) | expr_assign_op(bitxor, _, _) => {
4952                 self.add_fixed_trait_for_expr(expr.id,
4953                                               self.lang_items.bitxor_trait());
4954             }
4955             expr_binary(bitand, _, _) | expr_assign_op(bitand, _, _) => {
4956                 self.add_fixed_trait_for_expr(expr.id,
4957                                               self.lang_items.bitand_trait());
4958             }
4959             expr_binary(bitor, _, _) | expr_assign_op(bitor, _, _) => {
4960                 self.add_fixed_trait_for_expr(expr.id,
4961                                               self.lang_items.bitor_trait());
4962             }
4963             expr_binary(shl, _, _) | expr_assign_op(shl, _, _) => {
4964                 self.add_fixed_trait_for_expr(expr.id,
4965                                               self.lang_items.shl_trait());
4966             }
4967             expr_binary(shr, _, _) | expr_assign_op(shr, _, _) => {
4968                 self.add_fixed_trait_for_expr(expr.id,
4969                                               self.lang_items.shr_trait());
4970             }
4971             expr_binary(lt, _, _) | expr_binary(le, _, _) |
4972             expr_binary(ge, _, _) | expr_binary(gt, _, _) => {
4973                 self.add_fixed_trait_for_expr(expr.id,
4974                                               self.lang_items.ord_trait());
4975             }
4976             expr_binary(eq, _, _) | expr_binary(ne, _, _) => {
4977                 self.add_fixed_trait_for_expr(expr.id,
4978                                               self.lang_items.eq_trait());
4979             }
4980             expr_unary(neg, _) => {
4981                 self.add_fixed_trait_for_expr(expr.id,
4982                                               self.lang_items.neg_trait());
4983             }
4984             expr_unary(not, _) => {
4985                 self.add_fixed_trait_for_expr(expr.id,
4986                                               self.lang_items.not_trait());
4987             }
4988             expr_index(*) => {
4989                 self.add_fixed_trait_for_expr(expr.id,
4990                                               self.lang_items.index_trait());
4991             }
4992             _ => {
4993                 // Nothing to do.
4994             }
4995         }
4996     }
4997
4998     fn search_for_traits_containing_method(name: ident) -> @DVec<def_id> {
4999         debug!("(searching for traits containing method) looking for '%s'",
5000                self.session.str_of(name));
5001
5002         let found_traits = @DVec();
5003         let mut search_module = self.current_module;
5004         loop {
5005             // Look for the current trait.
5006             match copy self.current_trait_refs {
5007                 Some(trait_def_ids) => {
5008                     for trait_def_ids.each |trait_def_id| {
5009                         self.add_trait_info_if_containing_method(
5010                             found_traits, *trait_def_id, name);
5011                     }
5012                 }
5013                 None => {
5014                     // Nothing to do.
5015                 }
5016             }
5017
5018             // Look for trait children.
5019             for search_module.children.each_value |&child_name_bindings| {
5020                 match child_name_bindings.def_for_namespace(TypeNS) {
5021                     Some(def) => {
5022                         match def {
5023                             def_ty(trait_def_id) => {
5024                                 self.add_trait_info_if_containing_method(
5025                                     found_traits, trait_def_id, name);
5026                             }
5027                             _ => {
5028                                 // Continue.
5029                             }
5030                         }
5031                     }
5032                     None => {
5033                         // Continue.
5034                     }
5035                 }
5036             }
5037
5038             // Look for imports.
5039             for search_module.import_resolutions.each_value
5040                     |&import_resolution| {
5041
5042                 match import_resolution.target_for_namespace(TypeNS) {
5043                     None => {
5044                         // Continue.
5045                     }
5046                     Some(target) => {
5047                         match target.bindings.def_for_namespace(TypeNS) {
5048                             Some(def) => {
5049                                 match def {
5050                                     def_ty(trait_def_id) => {
5051                                         let added = self.
5052                                         add_trait_info_if_containing_method(
5053                                         found_traits, trait_def_id, name);
5054                                         if added {
5055                                             import_resolution.state.used =
5056                                                 true;
5057                                         }
5058                                     }
5059                                     _ => {
5060                                         // Continue.
5061                                     }
5062                                 }
5063                             }
5064                             None => {
5065                                 // Continue.
5066                             }
5067                         }
5068                     }
5069                 }
5070             }
5071
5072             // Move to the next parent.
5073             match search_module.parent_link {
5074                 NoParentLink => {
5075                     // Done.
5076                     break;
5077                 }
5078                 ModuleParentLink(parent_module, _) |
5079                 BlockParentLink(parent_module, _) => {
5080                     search_module = parent_module;
5081                 }
5082             }
5083         }
5084
5085         return found_traits;
5086     }
5087
5088     fn add_trait_info_if_containing_method(found_traits: @DVec<def_id>,
5089                                            trait_def_id: def_id,
5090                                            name: ident) -> bool {
5091
5092         debug!("(adding trait info if containing method) trying trait %d:%d \
5093                 for method '%s'",
5094                trait_def_id.crate,
5095                trait_def_id.node,
5096                self.session.str_of(name));
5097
5098         match self.trait_info.find(&trait_def_id) {
5099             Some(trait_info) if trait_info.contains_key(&name) => {
5100                 debug!("(adding trait info if containing method) found trait \
5101                         %d:%d for method '%s'",
5102                        trait_def_id.crate,
5103                        trait_def_id.node,
5104                        self.session.str_of(name));
5105                 (*found_traits).push(trait_def_id);
5106                 true
5107             }
5108             Some(_) | None => {
5109                 false
5110             }
5111         }
5112     }
5113
5114     fn add_fixed_trait_for_expr(expr_id: node_id, +trait_id: def_id) {
5115         let traits = @DVec();
5116         traits.push(trait_id);
5117         self.trait_map.insert(expr_id, traits);
5118     }
5119
5120     fn record_def(node_id: node_id, def: def) {
5121         debug!("(recording def) recording %? for %?", def, node_id);
5122         self.def_map.insert(node_id, def);
5123     }
5124
5125     fn enforce_default_binding_mode(pat: @pat,
5126                                     pat_binding_mode: binding_mode,
5127                                     descr: &str) {
5128         match pat_binding_mode {
5129             bind_infer => {}
5130             bind_by_copy => {
5131                 self.session.span_err(
5132                     pat.span,
5133                     fmt!("cannot use `copy` binding mode with %s",
5134                          descr));
5135             }
5136             bind_by_ref(*) => {
5137                 self.session.span_err(
5138                     pat.span,
5139                     fmt!("cannot use `ref` binding mode with %s",
5140                          descr));
5141             }
5142         }
5143     }
5144
5145     //
5146     // main function checking
5147     //
5148     // be sure that there is only one main function
5149     //
5150     fn check_duplicate_main() {
5151         if self.attr_main_fn.is_none() {
5152             if self.main_fns.len() >= 1u {
5153                 let mut i = 1u;
5154                 while i < self.main_fns.len() {
5155                     let (_, dup_main_span) =
5156                             option::unwrap(self.main_fns[i]);
5157                     self.session.span_err(
5158                         dup_main_span,
5159                         ~"multiple 'main' functions");
5160                     i += 1;
5161                 }
5162                 *self.session.main_fn = self.main_fns[0];
5163             }
5164         } else {
5165             *self.session.main_fn = self.attr_main_fn;
5166         }
5167     }
5168
5169     //
5170     // Unused import checking
5171     //
5172     // Although this is a lint pass, it lives in here because it depends on
5173     // resolve data structures.
5174     //
5175
5176     fn check_for_unused_imports_if_necessary() {
5177         if self.unused_import_lint_level == allow {
5178             return;
5179         }
5180
5181         let root_module = self.graph_root.get_module();
5182         self.check_for_unused_imports_in_module_subtree(root_module);
5183     }
5184
5185     fn check_for_unused_imports_in_module_subtree(module_: @Module) {
5186         // If this isn't a local crate, then bail out. We don't need to check
5187         // for unused imports in external crates.
5188
5189         match module_.def_id {
5190             Some(def_id) if def_id.crate == local_crate => {
5191                 // OK. Continue.
5192             }
5193             None => {
5194                 // Check for unused imports in the root module.
5195             }
5196             Some(_) => {
5197                 // Bail out.
5198                 debug!("(checking for unused imports in module subtree) not \
5199                         checking for unused imports for `%s`",
5200                        self.module_to_str(module_));
5201                 return;
5202             }
5203         }
5204
5205         self.check_for_unused_imports_in_module(module_);
5206
5207         for module_.children.each_value |&child_name_bindings| {
5208             match (*child_name_bindings).get_module_if_available() {
5209                 None => {
5210                     // Nothing to do.
5211                 }
5212                 Some(child_module) => {
5213                     self.check_for_unused_imports_in_module_subtree
5214                         (child_module);
5215                 }
5216             }
5217         }
5218
5219         for module_.anonymous_children.each_value |&child_module| {
5220             self.check_for_unused_imports_in_module_subtree(child_module);
5221         }
5222     }
5223
5224     fn check_for_unused_imports_in_module(module_: @Module) {
5225         for module_.import_resolutions.each_value |&import_resolution| {
5226             // Ignore dummy spans for things like automatically injected
5227             // imports for the prelude, and also don't warn about the same
5228             // import statement being unused more than once.
5229             if !import_resolution.state.used &&
5230                     !import_resolution.state.warned &&
5231                     import_resolution.span != dummy_sp() {
5232                 import_resolution.state.warned = true;
5233                 match self.unused_import_lint_level {
5234                     warn => {
5235                         self.session.span_warn(copy import_resolution.span,
5236                                                ~"unused import");
5237                     }
5238                     deny | forbid => {
5239                       self.session.span_err(copy import_resolution.span,
5240                                             ~"unused import");
5241                     }
5242                     allow => {
5243                       self.session.span_bug(copy import_resolution.span,
5244                                             ~"shouldn't be here if lint \
5245                                               is allowed");
5246                     }
5247                 }
5248             }
5249         }
5250     }
5251
5252
5253     //
5254     // Diagnostics
5255     //
5256     // Diagnostics are not particularly efficient, because they're rarely
5257     // hit.
5258     //
5259
5260     /// A somewhat inefficient routine to obtain the name of a module.
5261     fn module_to_str(module_: @Module) -> ~str {
5262         let idents = DVec();
5263         let mut current_module = module_;
5264         loop {
5265             match current_module.parent_link {
5266                 NoParentLink => {
5267                     break;
5268                 }
5269                 ModuleParentLink(module_, name) => {
5270                     idents.push(name);
5271                     current_module = module_;
5272                 }
5273                 BlockParentLink(module_, _) => {
5274                     idents.push(special_idents::opaque);
5275                     current_module = module_;
5276                 }
5277             }
5278         }
5279
5280         if idents.len() == 0 {
5281             return ~"???";
5282         }
5283         return self.idents_to_str(vec::reversed(idents.get()));
5284     }
5285
5286     fn dump_module(module_: @Module) {
5287         debug!("Dump of module `%s`:", self.module_to_str(module_));
5288
5289         debug!("Children:");
5290         for module_.children.each_key |&name| {
5291             debug!("* %s", self.session.str_of(name));
5292         }
5293
5294         debug!("Import resolutions:");
5295         for module_.import_resolutions.each |&name, &import_resolution| {
5296             let mut value_repr;
5297             match (*import_resolution).target_for_namespace(ValueNS) {
5298                 None => { value_repr = ~""; }
5299                 Some(_) => {
5300                     value_repr = ~" value:?";
5301                     // FIXME #4954
5302                 }
5303             }
5304
5305             let mut type_repr;
5306             match (*import_resolution).target_for_namespace(TypeNS) {
5307                 None => { type_repr = ~""; }
5308                 Some(_) => {
5309                     type_repr = ~" type:?";
5310                     // FIXME #4954
5311                 }
5312             }
5313
5314             debug!("* %s:%s%s", self.session.str_of(name),
5315                    value_repr, type_repr);
5316         }
5317     }
5318 }
5319
5320 /// Entry point to crate resolution.
5321 pub fn resolve_crate(session: Session,
5322                      lang_items: LanguageItems,
5323                      crate: @crate)
5324                   -> {
5325                     def_map: DefMap,
5326                     exp_map2: ExportMap2,
5327                     trait_map: TraitMap
5328                   } {
5329     let resolver = @Resolver(session, lang_items, crate);
5330     resolver.resolve(resolver);
5331     return {
5332         def_map: resolver.def_map,
5333         exp_map2: resolver.export_map2,
5334         trait_map: resolver.trait_map
5335     };
5336 }
5337