(index<- )        ./librustc/middle/resolve.rs

    git branch:    * master           5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
    modified:    Fri May  9 13:02:28 2014

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

librustc/middle/resolve.rs:243:1-243:1 -enum- definition:
enum RibKind {
    // No translation needs to be applied.
    NormalRibKind,
references:- 5
237:                       // The kind of the rib used for type parameters.
238:                       RibKind)
239: }
--
3913:     fn resolve_method(&mut self,
3914:                       rib_kind: RibKind,
3915:                       method: &Method,


librustc/middle/resolve.rs:747:1-747:1 -fn- definition:
fn NameBindings() -> NameBindings {
    NameBindings {
        type_def: RefCell::new(None),
references:- 2
1011:             None => {
1012:                 let child = Rc::new(NameBindings());
1013:                 module_.children.borrow_mut().insert(name.name, child.clone());


librustc/middle/resolve.rs:534:13-534:13 -struct- definition:
// bound to.
struct NameBindings {
    type_def: RefCell<Option<TypeNsDef>>,   //< Meaning in type namespace.
references:- 14
748: fn NameBindings() -> NameBindings {
749:     NameBindings {
750:         type_def: RefCell::new(None),
--
2191:     fn create_name_bindings_from_module(module: Rc<Module>) -> NameBindings {
2192:         NameBindings {
2193:             type_def: RefCell::new(Some(TypeNsDef {
--
3277:                                    name: Name,
3278:                                    namebindings: &NameBindings,
3279:                                    ns: Namespace) {


librustc/middle/resolve.rs:68:14-68:14 -NK_AS_STR_TODO- definition:
// FIXME: dox
pub type LastPrivateMap = NodeMap<LastPrivate>;
pub enum LastPrivate {
references:- 4
5375:     pub external_exports: ExternalExports,
5376:     pub last_private_map: LastPrivateMap,
5377: }
librustc/middle/privacy.rs:
341:     external_exports: resolve::ExternalExports,
342:     last_private_map: resolve::LastPrivateMap,
343: }
--
1405:                    external_exports: resolve::ExternalExports,
1406:                    last_private_map: resolve::LastPrivateMap,
1407:                    krate: &ast::Crate) -> (ExportedItems, PublicItems) {


librustc/middle/resolve.rs:185:59-185:59 -enum- definition:
/// Contains data for specific types of import directives.
enum ImportDirectiveSubclass {
    SingleImport(Ident /* target */, Ident /* source */),
references:- 5
331:     module_path: Vec<Ident>,
332:     subclass: ImportDirectiveSubclass,
333:     span: Span,
--
1901:                               module_path: Vec<Ident> ,
1902:                               subclass: ImportDirectiveSubclass,
1903:                               span: Span,
--
2071:     fn import_directive_subclass_to_str(&mut self,
2072:                                         subclass: ImportDirectiveSubclass)
2073:                                         -> ~str {
--
2083:                           idents: &[Ident],
2084:                           subclass: ImportDirectiveSubclass)
2085:                           -> ~str {


librustc/middle/resolve.rs:5102:8-5102:8 -fn- definition:
        fn add_trait_info(found_traits: &mut Vec<DefId>,
                          trait_def_id: DefId,
                          name: Name) {
references:- 3
5144:                     if method_map.contains_key(&(name, trait_def_id)) {
5145:                         add_trait_info(&mut found_traits, trait_def_id, name);
5146:                     }
--
5160:                 if self.method_map.borrow().contains_key(&(name, did)) {
5161:                     add_trait_info(&mut found_traits, did, name);
5162:                     self.used_imports.insert((import.type_id, TypeNS));


librustc/middle/resolve.rs:105:16-105:16 -enum- definition:
enum PatternBindingMode {
    RefutableMode,
    LocalIrrefutableMode,
references:- 4
106: enum PatternBindingMode {
--
4234:                        pattern: &Pat,
4235:                        mode: PatternBindingMode,
4236:                        // Maps idents to the node ID for the (outermost)


librustc/middle/resolve.rs:129:19-129:19 -enum- definition:
enum NamespaceResult {
    /// Means that resolve hasn't gathered enough information yet to determine
    /// whether the name is bound in this namespace. (That is, it hasn't
references:- 4
128: /// definitely- unresolved, or unknown.
130: enum NamespaceResult {
--
2291:                                        namespace: Namespace)
2292:                                     -> NamespaceResult {


librustc/middle/resolve.rs:52:27-52:27 -NK_AS_STR_TODO- definition:
// Trait method resolution
pub type TraitMap = NodeMap<Vec<DefId> >;
// This is the replacement export map. It maps a module to all of the exports
references:- 4
5373:     pub exp_map2: ExportMap2,
5374:     pub trait_map: TraitMap,
5375:     pub external_exports: ExternalExports,
librustc/middle/typeck/mod.rs:
243:     // A mapping from method call sites to traits that have that method.
244:     trait_map: resolve::TraitMap,
245:     tcx: &'a ty::ctxt
--
423: pub fn check_crate(tcx: &ty::ctxt,
424:                    trait_map: resolve::TraitMap,
425:                    krate: &ast::Crate) {


librustc/middle/resolve.rs:192:19-192:19 -enum- definition:
enum ReducedGraphParent {
    ModuleReducedGraphParent(Rc<Module>)
}
references:- 18
1138:                                     item: &Item,
1139:                                     parent: ReducedGraphParent)
1140:                                     -> ReducedGraphParent
--
1514:                                             foreign_item: &ForeignItem,
1515:                                             parent: ReducedGraphParent,
1516:                                             f: |&mut Resolver|) {
--
1545:                                          block: &Block,
1546:                                          parent: ReducedGraphParent)
1547:                                             -> ReducedGraphParent
1548:     {
--
1576:                            ident: Ident,
1577:                            new_parent: ReducedGraphParent) {
1578:         debug!("(building reduced graph for \


librustc/middle/resolve.rs:118:16-118:16 -enum- definition:
enum NamespaceError {
    NoError,
    ModuleError,
references:- 4
119: enum NamespaceError {
--
792: fn namespace_error_to_str(ns: NamespaceError) -> &'static str {
793:     match ns {


librustc/middle/resolve.rs:65:46-65:46 -NK_AS_STR_TODO- definition:
// not contain any entries from local crates.
pub type ExternalExports = DefIdSet;
// FIXME: dox
references:- 4
5374:     pub trait_map: TraitMap,
5375:     pub external_exports: ExternalExports,
5376:     pub last_private_map: LastPrivateMap,
librustc/middle/privacy.rs:
340:     parents: NodeMap<ast::NodeId>,
341:     external_exports: resolve::ExternalExports,
342:     last_private_map: resolve::LastPrivateMap,
--
1404:                    exp_map2: &resolve::ExportMap2,
1405:                    external_exports: resolve::ExternalExports,
1406:                    last_private_map: resolve::LastPrivateMap,


librustc/middle/resolve.rs:206:1-206:1 -enum- definition:
enum ResolveResult<T> {
    Failed,         // Failed to resolve the name.
    Indeterminate,  // Couldn't determine due to unresolved globs.
references:- 10
2715:                            name_search_type: NameSearchType)
2716:                                -> ResolveResult<(Rc<Module>, LastPrivate)> {
2717:         let module_path_len = module_path.len();
--
2815:                                      SearchThroughModulesFlag)
2816:                                     -> ResolveResult<(Target, bool)> {
2817:         debug!("(resolving item in lexical scope) resolving `{}` in \
--
2947:                                        name: Ident)
2948:                                 -> ResolveResult<Rc<Module>> {
2949:         // If this module is an anonymous module, resolve the item in the
--
3035:                              module_path: &[Ident])
3036:                                  -> ResolveResult<ModulePrefixResult> {
3037:         // Start at the current module if we see `self` or `super`, or at the
--
3088:                               allow_private_imports: bool)
3089:                               -> ResolveResult<(Target, bool)> {
3090:         debug!("(resolving name in module) resolving `{}` in `{}`",


librustc/middle/resolve.rs:5370:1-5370:1 -struct- definition:
pub struct CrateMap {
    pub def_map: DefMap,
    pub exp_map2: ExportMap2,
references:- 3
5382:                      krate: &Crate)
5383:                   -> CrateMap {
5384:     let mut resolver = Resolver(session, lang_items, krate.span);
librustc/driver/driver.rs:
298:     let middle::resolve::CrateMap {
299:         def_map: def_map,
librustc/middle/resolve.rs:
5387:                    external_exports, .. } = resolver;
5388:     CrateMap {
5389:         def_map: def_map,


librustc/middle/resolve.rs:70:1-70:1 -enum- definition:
pub enum LastPrivate {
    LastMod(PrivateDep),
    // `use` directives (imports) can refer to two separate definitions in the
references:- 19
2596:                                      name_search_type: NameSearchType,
2597:                                      lp: LastPrivate)
2598:                                 -> ResolveResult<(Rc<Module>, LastPrivate)> {
--
4537:                     namespace: Namespace,
4538:                     check_ribs: bool) -> Option<(Def, LastPrivate)> {
4539:         // First, resolve the types.
--
4743:                                    namespace: Namespace)
4744:                                        -> Option<(Def, LastPrivate)> {
4745:         let module_path_idents = path.segments.init().iter()
--
5177:     fn record_def(&mut self, node_id: NodeId, (def, lp): (Def, LastPrivate)) {
5178:         debug!("(recording def) recording {:?} for {:?}, last private {:?}",


librustc/middle/resolve.rs:43:1-43:1 -struct- definition:
struct binding_info {
    span: Span,
    binding_mode: BindingMode,
references:- 2
4032:             result.insert(name,
4033:                           binding_info {span: sp,
4034:                                         binding_mode: binding_mode});


librustc/middle/resolve.rs:434:16-434:16 -enum- definition:
enum ModuleKind {
    NormalModuleKind,
    ExternModuleKind,
references:- 7
490:            def_id: Option<DefId>,
491:            kind: ModuleKind,
492:            external: bool,
--
583:                        def_id: Option<DefId>,
584:                        kind: ModuleKind,
585:                        external: bool,


librustc/middle/resolve.rs:287:16-287:16 -enum- definition:
enum NameSearchType {
    /// We're doing a name search in order to resolve a `use` directive.
    ImportSearch,
references:- 6
288: enum NameSearchType {
--
2714:                            span: Span,
2715:                            name_search_type: NameSearchType)
2716:                                -> ResolveResult<(Rc<Module>, LastPrivate)> {
--
3086:                               namespace: Namespace,
3087:                               name_search_type: NameSearchType,
3088:                               allow_private_imports: bool)


librustc/middle/resolve.rs:41:22-41:22 -NK_AS_STR_TODO- definition:
// Definition mapping
pub type DefMap = RefCell<NodeMap<Def>>;
struct binding_info {
references:- 24
896:     def_map: DefMap,
897:     export_map2: ExportMap2,
--
5371: pub struct CrateMap {
5372:     pub def_map: DefMap,
5373:     pub exp_map2: ExportMap2,
librustc/middle/check_const.rs:
187:                                 ast_map: &'a ast_map::Map,
188:                                 def_map: &'a resolve::DefMap,
189:                                 it: &'a Item) {
librustc/middle/freevars.rs:
108: struct AnnotateFreevarsVisitor<'a> {
109:     def_map: &'a resolve::DefMap,
110:     freevars: freevar_map,
--
126: // one pass. This could be improved upon if it turns out to matter.
127: pub fn annotate_freevars(def_map: &resolve::DefMap, krate: &ast::Crate) ->
128:    freevar_map {
librustc/middle/pat_util.rs:
90: /// an ident, e.g. `foo`, or `Foo(foo)` or `foo @ Bar(..)`.
91: pub fn pat_contains_bindings(dm: &resolve::DefMap, pat: &Pat) -> bool {
92:     let mut contains_bindings = false;
librustc/middle/trans/_match.rs:
822:               bcx: &'b Block<'b>,
823:               dm: &DefMap,
824:               m: &'a [Match<'a, 'b>],
librustc/middle/ty.rs:
1072: pub fn mk_ctxt(s: Session,
1073:                dm: resolve::DefMap,
1074:                named_region_map: resolve_lifetime::NamedRegionMap,
librustc/middle/trans/_match.rs:
850:                 bcx: &'b Block<'b>,
851:                 dm: &DefMap,
852:                 m: &'a [Match<'a, 'b>],


librustc/middle/resolve.rs:856:29-856:29 -struct- definition:
/// The main resolver class.
struct Resolver<'a> {
    session: &'a Session,
references:- 14
815:     let this = Resolver {
816:         session: session,
--
3701:                                type_parameters: TypeParameters,
3702:                                f: |&mut Resolver|) {
3703:         match type_parameters {
--
3746:     fn with_constant_rib(&mut self, f: |&mut Resolver|) {
3747:         self.value_ribs.borrow_mut().push(Rib::new(ConstantItemRibKind));
--
5385:     resolver.resolve(krate);
5386:     let Resolver { def_map, export_map2, trait_map, last_private,
5387:                    external_exports, .. } = resolver;


librustc/middle/resolve.rs:526:19-526:19 -struct- definition:
struct ValueNsDef {
    is_public: bool, // see note in ImportResolution about how to use this
    def: Def,
references:- 6
525: // Records a possibly-private value definition.
527: struct ValueNsDef {
--
536:     type_def: RefCell<Option<TypeNsDef>>,   //< Meaning in type namespace.
537:     value_def: RefCell<Option<ValueNsDef>>, //< Meaning in value namespace.
538: }
--
646:     fn define_value(&self, def: Def, sp: Span, is_public: bool) {
647:         *self.value_def.borrow_mut() = Some(ValueNsDef {
648:             def: def,


librustc/middle/resolve.rs:909:1-909:1 -struct- definition:
struct BuildReducedGraphVisitor<'a, 'b> {
    resolver: &'a mut Resolver<'b>,
}
references:- 3
981:         let mut visitor = BuildReducedGraphVisitor { resolver: self, };
982:         visit::walk_crate(&mut visitor, krate, initial_parent);


librustc/middle/resolve.rs:517:19-517:19 -struct- definition:
struct TypeNsDef {
    is_public: bool, // see note in ImportResolution about how to use this
    module_def: Option<Rc<Module>>,
references:- 14
592:                                          external, is_public);
593:                 *self.type_def.borrow_mut() = Some(TypeNsDef {
594:                     is_public: is_public,
--
626:             None => {
627:                 *self.type_def.borrow_mut() = Some(TypeNsDef {
628:                     module_def: None,
--
2192:         NameBindings {
2193:             type_def: RefCell::new(Some(TypeNsDef {
2194:                 is_public: false,


librustc/middle/resolve.rs:329:26-329:26 -struct- definition:
/// One import directive.
struct ImportDirective {
    module_path: Vec<Ident>,
references:- 6
344:            -> ImportDirective {
345:         ImportDirective {
346:             module_path: module_path,
--
2101:                                  module_: Rc<Module>,
2102:                                  import_directive: &ImportDirective)
2103:                                  -> ResolveResult<()> {
--
2207:                              source: Ident,
2208:                              directive: &ImportDirective,
2209:                              lp: LastPrivate)


librustc/middle/resolve.rs:755:46-755:46 -struct- definition:
/// Interns the names of the primitive types.
struct PrimitiveTypeTable {
    primitive_types: HashMap<Name, PrimTy>,
references:- 4
766: fn PrimitiveTypeTable() -> PrimitiveTypeTable {
767:     let mut table = PrimitiveTypeTable {
768:         primitive_types: HashMap::new()
--
890:     // The idents for the primitive types.
891:     primitive_type_table: PrimitiveTypeTable,


librustc/middle/resolve.rs:218:1-218:1 -enum- definition:
enum TypeParameters<'a> {
    NoTypeParameters,                   //< No type parameters.
    HasTypeParameters(&'a Generics,  //< Type parameters.
references:- 2
3756:                         optional_declaration: Option<P<FnDecl>>,
3757:                         type_parameters: TypeParameters,
3758:                         block: P<Block>) {


librustc/middle/resolve.rs:371:65-371:65 -struct- definition:
/// An ImportResolution represents a particular `use` directive.
struct ImportResolution {
    /// Whether this resolution came from a `use` or a `pub use`. Note that this
references:- 5
398:     fn new(id: NodeId, is_public: bool) -> ImportResolution {
399:         ImportResolution {
400:             type_id: id,
--
473:     // The status of resolving each import in this module.
474:     import_resolutions: RefCell<HashMap<Name, ImportResolution>>,
--
2289:                         fn get_binding(this: &mut Resolver,
2290:                                        import_resolution: &ImportResolution,
2291:                                        namespace: Namespace)


librustc/middle/resolve.rs:305:16-305:16 -enum- definition:
enum DuplicateCheckingMode {
    ForbidDuplicateModules,
    ForbidDuplicateTypes,
references:- 4
304: // another item exists with the same name in some namespace.
306: enum DuplicateCheckingMode {
--
997:                  reduced_graph_parent: ReducedGraphParent,
998:                  duplicate_checking_mode: DuplicateCheckingMode,
999:                  // For printing errors


librustc/middle/resolve.rs:791:1-791:1 -fn- definition:
fn namespace_error_to_str(ns: NamespaceError) -> &'static str {
    match ns {
        NoError     => "",
references:- 2
1085:                                  format!("first definition of {} `{}` here",
1086:                                       namespace_error_to_str(duplicate_type),
1087:                                       token::get_ident(name)));


librustc/middle/resolve.rs:941:1-941:1 -struct- definition:
struct UnusedImportCheckVisitor<'a, 'b> { resolver: &'a mut Resolver<'b> }
impl<'a, 'b> Visitor<()> for UnusedImportCheckVisitor<'a, 'b> {
    fn visit_view_item(&mut self, vi: &ViewItem, _: ()) {
references:- 2
5217:     fn check_for_unused_imports(&mut self, krate: &ast::Crate) {
5218:         let mut visitor = UnusedImportCheckVisitor{ resolver: self };
5219:         visit::walk_crate(&mut visitor, krate, ());


librustc/middle/resolve.rs:443:37-443:37 -struct- definition:
/// One node in the tree of modules.
struct Module {
    parent_link: ParentLink,
references:- 53


librustc/middle/resolve.rs:112:31-112:31 -enum- definition:
enum Namespace {
    TypeNS,
    ValueNS
references:- 24
417:     fn id(&self, namespace: Namespace) -> NodeId {
418:         match namespace {
--
3085:                               name: Ident,
3086:                               namespace: Namespace,
3087:                               name_search_type: NameSearchType,
--
4791:                                             ident: Ident,
4792:                                             namespace: Namespace,
4793:                                             span: Span)
--
4823:                                                    ident: Ident,
4824:                                                    namespace: Namespace)
4825:                                                 -> Option<(Def, LastPrivate)> {


librustc/middle/resolve.rs:83:1-83:1 -enum- definition:
pub enum PrivateDep {
    AllPublic,
    DependsOn(DefId),
references:- 3
79:                pub value_used: ImportUse,
80:                pub type_priv: Option<PrivateDep>,
81:                pub type_used: ImportUse},


librustc/middle/resolve.rs:314:21-314:21 -struct- definition:
/// One local scope.
struct Rib {
    bindings: RefCell<HashMap<Name, DefLike>>,
references:- 8
321:     fn new(kind: RibKind) -> Rib {
322:         Rib {
323:             bindings: RefCell::new(HashMap::new()),
--
879:     // The current set of local scopes, for labels.
880:     label_ribs: RefCell<Vec<Rib>>,
--
3495:     fn search_ribs(&self,
3496:                    ribs: &[Rib],
3497:                    name: Name,


librustc/middle/resolve.rs:356:19-356:19 -struct- definition:
struct Target {
    target_module: Rc<Module>,
    bindings: Rc<NameBindings>,
references:- 13
355: /// The item that an import resolves to.
357: struct Target {
--
362: impl Target {
363:     fn new(target_module: Rc<Module>, bindings: Rc<NameBindings>) -> Target {
--
3088:                               allow_private_imports: bool)
3089:                               -> ResolveResult<(Target, bool)> {
3090:         debug!("(resolving name in module) resolving `{}` in `{}`",


librustc/middle/resolve.rs:56:11-56:11 -NK_AS_STR_TODO- definition:
// within.
pub type ExportMap2 = RefCell<NodeMap<Vec<Export2> >>;
pub struct Export2 {
references:- 10
896:     def_map: DefMap,
897:     export_map2: ExportMap2,
898:     trait_map: TraitMap,
--
5372:     pub def_map: DefMap,
5373:     pub exp_map2: ExportMap2,
5374:     pub trait_map: TraitMap,
librustc/middle/privacy.rs:
136:     tcx: &'a ty::ctxt,
137:     exp_map2: &'a resolve::ExportMap2,
--
1403: pub fn check_crate(tcx: &ty::ctxt,
1404:                    exp_map2: &resolve::ExportMap2,
1405:                    external_exports: resolve::ExternalExports,
librustc/metadata/encoder.rs:
82:     pub tcx: &'a ty::ctxt,
83:     pub reexports2: &'a middle::resolve::ExportMap2,
84:     pub item_symbols: &'a RefCell<NodeMap<~str>>,
librustc/middle/trans/context.rs:
60:     pub item_vals: RefCell<NodeMap<ValueRef>>,
61:     pub exp_map2: resolve::ExportMap2,
62:     pub reachable: NodeSet,
--
130:                tcx: ty::ctxt,
131:                emap2: resolve::ExportMap2,
132:                symbol_hasher: Sha256,
librustc/driver/driver.rs:
275: pub struct CrateAnalysis {
276:     pub exp_map2: middle::resolve::ExportMap2,
277:     pub exported_items: middle::privacy::ExportedItems,


librustc/middle/resolve.rs:58:1-58:1 -struct- definition:
pub struct Export2 {
    pub name: ~str,        // The name of the target.
    pub def_id: DefId,     // The definition of the target.
references:- 8
3284:                        name, def_id_of_def(d));
3285:                 exports2.push(Export2 {
3286:                     name: name.get().to_str(),
--
3296:     fn add_exports_for_module(&mut self,
3297:                               exports2: &mut Vec<Export2> ,
3298:                               module_: &Module) {
librustc/metadata/encoder.rs:
365: fn encode_reexported_static_method(ebml_w: &mut Encoder,
366:                                    exp: &middle::resolve::Export2,
367:                                    method_def_id: DefId,
--
382:                                          ebml_w: &mut Encoder,
383:                                          exp: &middle::resolve::Export2)
384:                                          -> bool {
--
423:                                     mod_path: PathElems,
424:                                     exp: &middle::resolve::Export2) {
425:     match ecx.tcx.map.find(exp.def_id.node) {
librustc/middle/resolve.rs:
3275:     fn add_exports_of_namebindings(&mut self,
3276:                                    exports2: &mut Vec<Export2> ,
3277:                                    name: Name,


librustc/middle/resolve.rs:426:19-426:19 -enum- definition:
enum ParentLink {
    NoParentLink,
    ModuleParentLink(Weak<Module>, Ident),
references:- 7
549:     fn define_module(&self,
550:                      parent_link: ParentLink,
551:                      def_id: Option<DefId>,
--
1127:     fn get_parent_link(&mut self, parent: ReducedGraphParent, name: Ident)
1128:                            -> ParentLink {
1129:         match parent {


librustc/middle/resolve.rs:5312:8-5312:8 -fn- definition:
        fn collect_mod(idents: &mut Vec<ast::Ident>, module: &Module) {
            match module.parent_link {
                NoParentLink => {}
references:- 3
5320:                     idents.push(special_idents::opaque);
5321:                     collect_mod(idents, &*module.upgrade().unwrap());
5322:                 }
--
5324:         }
5325:         collect_mod(&mut idents, module);


librustc/middle/resolve.rs:2289:24-2289:24 -fn- definition:
                        fn get_binding(this: &mut Resolver,
                                       import_resolution: &ImportResolution,
                                       namespace: Namespace)
references:- 2
2322:                         if type_result.is_unknown() {
2323:                             type_result = get_binding(self, import_resolution,
2324:                                                       TypeNS);


librustc/middle/resolve.rs:90:16-90:16 -enum- definition:
pub enum ImportUse {
    Unused,       // The import is not used.
    Used,         // The import is used.
references:- 5
89: // How an import is used.
91: pub enum ImportUse {