src/librustc_resolve/resolve_imports.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use self::ImportDirectiveSubclass::*;
  12
  13 use DefModifiers;
  14 use Module;
  15 use ModuleKind;
  16 use Namespace::{self, TypeNS, ValueNS};
  17 use NameBindings;
  18 use NamespaceResult::{BoundResult, UnboundResult, UnknownResult};
  19 use NamespaceResult;
  20 use NameSearchType;
  21 use ResolveResult;
  22 use Resolver;
  23 use UseLexicalScopeFlag;
  24 use {names_to_string, module_to_string};
  25
  26 use build_reduced_graph;
  27
  28 use rustc::middle::def::*;
  29 use rustc::middle::privacy::*;
  30
  31 use syntax::ast::{DefId, NodeId, Name};
  32 use syntax::attr::AttrMetaMethods;
  33 use syntax::parse::token;
  34 use syntax::codemap::Span;
  35
  36 use std::mem::replace;
  37 use std::rc::Rc;
  38
  39
  40 /// Contains data for specific types of import directives.
  41 #[derive(Copy, Clone,Debug)]
  42 pub enum ImportDirectiveSubclass {
  43     SingleImport(Name /* target */, Name /* source */),
  44     GlobImport
  45 }
  46
  47 /// Whether an import can be shadowed by another import.
  48 #[derive(Debug,PartialEq,Clone,Copy)]
  49 pub enum Shadowable {
  50     Always,
  51     Never
  52 }
  53
  54 /// One import directive.
  55 #[derive(Debug)]
  56 pub struct ImportDirective {
  57     pub module_path: Vec<Name>,
  58     pub subclass: ImportDirectiveSubclass,
  59     pub span: Span,
  60     pub id: NodeId,
  61     pub is_public: bool, // see note in ImportResolution about how to use this
  62     pub shadowable: Shadowable,
  63 }
  64
  65 impl ImportDirective {
  66     pub fn new(module_path: Vec<Name> ,
  67            subclass: ImportDirectiveSubclass,
  68            span: Span,
  69            id: NodeId,
  70            is_public: bool,
  71            shadowable: Shadowable)
  72            -> ImportDirective {
  73         ImportDirective {
  74             module_path: module_path,
  75             subclass: subclass,
  76             span: span,
  77             id: id,
  78             is_public: is_public,
  79             shadowable: shadowable,
  80         }
  81     }
  82 }
  83
  84 /// The item that an import resolves to.
  85 #[derive(Clone,Debug)]
  86 pub struct Target {
  87     pub target_module: Rc<Module>,
  88     pub bindings: Rc<NameBindings>,
  89     pub shadowable: Shadowable,
  90 }
  91
  92 impl Target {
  93     pub fn new(target_module: Rc<Module>,
  94            bindings: Rc<NameBindings>,
  95            shadowable: Shadowable)
  96            -> Target {
  97         Target {
  98             target_module: target_module,
  99             bindings: bindings,
 100             shadowable: shadowable,
 101         }
 102     }
 103 }
 104
 105 /// An ImportResolution represents a particular `use` directive.
 106 #[derive(Debug)]
 107 pub struct ImportResolution {
 108     /// Whether this resolution came from a `use` or a `pub use`. Note that this
 109     /// should *not* be used whenever resolution is being performed. Privacy
 110     /// testing occurs during a later phase of compilation.
 111     pub is_public: bool,
 112
 113     // The number of outstanding references to this name. When this reaches
 114     // zero, outside modules can count on the targets being correct. Before
 115     // then, all bets are off; future imports could override this name.
 116     // Note that this is usually either 0 or 1 - shadowing is forbidden the only
 117     // way outstanding_references is > 1 in a legal program is if the name is
 118     // used in both namespaces.
 119     pub outstanding_references: usize,
 120
 121     /// The value that this `use` directive names, if there is one.
 122     pub value_target: Option<Target>,
 123     /// The source node of the `use` directive leading to the value target
 124     /// being non-none
 125     pub value_id: NodeId,
 126
 127     /// The type that this `use` directive names, if there is one.
 128     pub type_target: Option<Target>,
 129     /// The source node of the `use` directive leading to the type target
 130     /// being non-none
 131     pub type_id: NodeId,
 132 }
 133
 134 impl ImportResolution {
 135     pub fn new(id: NodeId, is_public: bool) -> ImportResolution {
 136         ImportResolution {
 137             type_id: id,
 138             value_id: id,
 139             outstanding_references: 0,
 140             value_target: None,
 141             type_target: None,
 142             is_public: is_public,
 143         }
 144     }
 145
 146     pub fn target_for_namespace(&self, namespace: Namespace)
 147                                 -> Option<Target> {
 148         match namespace {
 149             TypeNS  => self.type_target.clone(),
 150             ValueNS => self.value_target.clone(),
 151         }
 152     }
 153
 154     pub fn id(&self, namespace: Namespace) -> NodeId {
 155         match namespace {
 156             TypeNS  => self.type_id,
 157             ValueNS => self.value_id,
 158         }
 159     }
 160
 161     pub fn shadowable(&self, namespace: Namespace) -> Shadowable {
 162         let target = self.target_for_namespace(namespace);
 163         if target.is_none() {
 164             return Shadowable::Always;
 165         }
 166
 167         target.unwrap().shadowable
 168     }
 169
 170     pub fn set_target_and_id(&mut self,
 171                          namespace: Namespace,
 172                          target: Option<Target>,
 173                          id: NodeId) {
 174         match namespace {
 175             TypeNS  => {
 176                 self.type_target = target;
 177                 self.type_id = id;
 178             }
 179             ValueNS => {
 180                 self.value_target = target;
 181                 self.value_id = id;
 182             }
 183         }
 184     }
 185 }
 186
 187
 188 struct ImportResolver<'a, 'b:'a, 'tcx:'b> {
 189     resolver: &'a mut Resolver<'b, 'tcx>
 190 }
 191
 192 impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
 193     // Import resolution
 194     //
 195     // This is a fixed-point algorithm. We resolve imports until our efforts
 196     // are stymied by an unresolved import; then we bail out of the current
 197     // module and continue. We terminate successfully once no more imports
 198     // remain or unsuccessfully when no forward progress in resolving imports
 199     // is made.
 200
 201     /// Resolves all imports for the crate. This method performs the fixed-
 202     /// point iteration.
 203     fn resolve_imports(&mut self) {
 204         let mut i = 0;
 205         let mut prev_unresolved_imports = 0;
 206         loop {
 207             debug!("(resolving imports) iteration {}, {} imports left",
 208                    i, self.resolver.unresolved_imports);
 209
 210             let module_root = self.resolver.graph_root.get_module();
 211             self.resolve_imports_for_module_subtree(module_root.clone());
 212
 213             if self.resolver.unresolved_imports == 0 {
 214                 debug!("(resolving imports) success");
 215                 break;
 216             }
 217
 218             if self.resolver.unresolved_imports == prev_unresolved_imports {
 219                 self.resolver.report_unresolved_imports(module_root);
 220                 break;
 221             }
 222
 223             i += 1;
 224             prev_unresolved_imports = self.resolver.unresolved_imports;
 225         }
 226     }
 227
 228     /// Attempts to resolve imports for the given module and all of its
 229     /// submodules.
 230     fn resolve_imports_for_module_subtree(&mut self, module_: Rc<Module>) {
 231         debug!("(resolving imports for module subtree) resolving {}",
 232                module_to_string(&*module_));
 233         let orig_module = replace(&mut self.resolver.current_module, module_.clone());
 234         self.resolve_imports_for_module(module_.clone());
 235         self.resolver.current_module = orig_module;
 236
 237         build_reduced_graph::populate_module_if_necessary(self.resolver, &module_);
 238         for (_, child_node) in module_.children.borrow().iter() {
 239             match child_node.get_module_if_available() {
 240                 None => {
 241                     // Nothing to do.
 242                 }
 243                 Some(child_module) => {
 244                     self.resolve_imports_for_module_subtree(child_module);
 245                 }
 246             }
 247         }
 248
 249         for (_, child_module) in module_.anonymous_children.borrow().iter() {
 250             self.resolve_imports_for_module_subtree(child_module.clone());
 251         }
 252     }
 253
 254     /// Attempts to resolve imports for the given module only.
 255     fn resolve_imports_for_module(&mut self, module: Rc<Module>) {
 256         if module.all_imports_resolved() {
 257             debug!("(resolving imports for module) all imports resolved for \
 258                    {}",
 259                    module_to_string(&*module));
 260             return;
 261         }
 262
 263         let imports = module.imports.borrow();
 264         let import_count = imports.len();
 265         while module.resolved_import_count.get() < import_count {
 266             let import_index = module.resolved_import_count.get();
 267             let import_directive = &(*imports)[import_index];
 268             match self.resolve_import_for_module(module.clone(),
 269                                                  import_directive) {
 270                 ResolveResult::Failed(err) => {
 271                     let (span, help) = match err {
 272                         Some((span, msg)) => (span, format!(". {}", msg)),
 273                         None => (import_directive.span, String::new())
 274                     };
 275                     let msg = format!("unresolved import `{}`{}",
 276                                       import_path_to_string(
 277                                           &import_directive.module_path,
 278                                           import_directive.subclass),
 279                                       help);
 280                     self.resolver.resolve_error(span, &msg[..]);
 281                 }
 282                 ResolveResult::Indeterminate => break, // Bail out. We'll come around next time.
 283                 ResolveResult::Success(()) => () // Good. Continue.
 284             }
 285
 286             module.resolved_import_count
 287                   .set(module.resolved_import_count.get() + 1);
 288         }
 289     }
 290
 291     /// Attempts to resolve the given import. The return value indicates
 292     /// failure if we're certain the name does not exist, indeterminate if we
 293     /// don't know whether the name exists at the moment due to other
 294     /// currently-unresolved imports, or success if we know the name exists.
 295     /// If successful, the resolved bindings are written into the module.
 296     fn resolve_import_for_module(&mut self,
 297                                  module_: Rc<Module>,
 298                                  import_directive: &ImportDirective)
 299                                  -> ResolveResult<()> {
 300         let mut resolution_result = ResolveResult::Failed(None);
 301         let module_path = &import_directive.module_path;
 302
 303         debug!("(resolving import for module) resolving import `{}::...` in `{}`",
 304                names_to_string(&module_path[..]),
 305                module_to_string(&*module_));
 306
 307         // First, resolve the module path for the directive, if necessary.
 308         let container = if module_path.is_empty() {
 309             // Use the crate root.
 310             Some((self.resolver.graph_root.get_module(), LastMod(AllPublic)))
 311         } else {
 312             match self.resolver.resolve_module_path(module_.clone(),
 313                                                     &module_path[..],
 314                                                     UseLexicalScopeFlag::DontUseLexicalScope,
 315                                                     import_directive.span,
 316                                                     NameSearchType::ImportSearch) {
 317                 ResolveResult::Failed(err) => {
 318                     resolution_result = ResolveResult::Failed(err);
 319                     None
 320                 },
 321                 ResolveResult::Indeterminate => {
 322                     resolution_result = ResolveResult::Indeterminate;
 323                     None
 324                 }
 325                 ResolveResult::Success(container) => Some(container),
 326             }
 327         };
 328
 329         match container {
 330             None => {}
 331             Some((containing_module, lp)) => {
 332                 // We found the module that the target is contained
 333                 // within. Attempt to resolve the import within it.
 334
 335                 match import_directive.subclass {
 336                     SingleImport(target, source) => {
 337                         resolution_result =
 338                             self.resolve_single_import(&module_,
 339                                                        containing_module,
 340                                                        target,
 341                                                        source,
 342                                                        import_directive,
 343                                                        lp);
 344                     }
 345                     GlobImport => {
 346                         resolution_result =
 347                             self.resolve_glob_import(&module_,
 348                                                      containing_module,
 349                                                      import_directive,
 350                                                      lp);
 351                     }
 352                 }
 353             }
 354         }
 355
 356         // Decrement the count of unresolved imports.
 357         match resolution_result {
 358             ResolveResult::Success(()) => {
 359                 assert!(self.resolver.unresolved_imports >= 1);
 360                 self.resolver.unresolved_imports -= 1;
 361             }
 362             _ => {
 363                 // Nothing to do here; just return the error.
 364             }
 365         }
 366
 367         // Decrement the count of unresolved globs if necessary. But only if
 368         // the resolution result is indeterminate -- otherwise we'll stop
 369         // processing imports here. (See the loop in
 370         // resolve_imports_for_module).
 371
 372         if !resolution_result.indeterminate() {
 373             match import_directive.subclass {
 374                 GlobImport => {
 375                     assert!(module_.glob_count.get() >= 1);
 376                     module_.glob_count.set(module_.glob_count.get() - 1);
 377                 }
 378                 SingleImport(..) => {
 379                     // Ignore.
 380                 }
 381             }
 382         }
 383
 384         return resolution_result;
 385     }
 386
 387     fn resolve_single_import(&mut self,
 388                              module_: &Module,
 389                              target_module: Rc<Module>,
 390                              target: Name,
 391                              source: Name,
 392                              directive: &ImportDirective,
 393                              lp: LastPrivate)
 394                              -> ResolveResult<()> {
 395         debug!("(resolving single import) resolving `{}` = `{}::{}` from \
 396                 `{}` id {}, last private {:?}",
 397                target,
 398                module_to_string(&*target_module),
 399                source,
 400                module_to_string(module_),
 401                directive.id,
 402                lp);
 403
 404         let lp = match lp {
 405             LastMod(lp) => lp,
 406             LastImport {..} => {
 407                 self.resolver.session
 408                     .span_bug(directive.span,
 409                               "not expecting Import here, must be LastMod")
 410             }
 411         };
 412
 413         // We need to resolve both namespaces for this to succeed.
 414         //
 415
 416         let mut value_result = UnknownResult;
 417         let mut type_result = UnknownResult;
 418
 419         // Search for direct children of the containing module.
 420         build_reduced_graph::populate_module_if_necessary(self.resolver, &target_module);
 421
 422         match target_module.children.borrow().get(&source) {
 423             None => {
 424                 // Continue.
 425             }
 426             Some(ref child_name_bindings) => {
 427                 // pub_err makes sure we don't give the same error twice.
 428                 let mut pub_err = false;
 429                 if child_name_bindings.defined_in_namespace(ValueNS) {
 430                     debug!("(resolving single import) found value binding");
 431                     value_result = BoundResult(target_module.clone(),
 432                                                (*child_name_bindings).clone());
 433                     if directive.is_public && !child_name_bindings.is_public(ValueNS) {
 434                         let msg = format!("`{}` is private", source);
 435                         span_err!(self.resolver.session, directive.span, E0364, "{}", &msg);
 436                         pub_err = true;
 437                     }
 438                 }
 439                 if child_name_bindings.defined_in_namespace(TypeNS) {
 440                     debug!("(resolving single import) found type binding");
 441                     type_result = BoundResult(target_module.clone(),
 442                                               (*child_name_bindings).clone());
 443                     if !pub_err && directive.is_public && !child_name_bindings.is_public(TypeNS) {
 444                         let msg = format!("`{}` is private", source);
 445                         span_err!(self.resolver.session, directive.span, E0365, "{}", &msg);
 446                     }
 447                 }
 448             }
 449         }
 450
 451         // Unless we managed to find a result in both namespaces (unlikely),
 452         // search imports as well.
 453         let mut value_used_reexport = false;
 454         let mut type_used_reexport = false;
 455         match (value_result.clone(), type_result.clone()) {
 456             (BoundResult(..), BoundResult(..)) => {} // Continue.
 457             _ => {
 458                 // If there is an unresolved glob at this point in the
 459                 // containing module, bail out. We don't know enough to be
 460                 // able to resolve this import.
 461
 462                 if target_module.glob_count.get() > 0 {
 463                     debug!("(resolving single import) unresolved glob; \
 464                             bailing out");
 465                     return ResolveResult::Indeterminate;
 466                 }
 467
 468                 // Now search the exported imports within the containing module.
 469                 match target_module.import_resolutions.borrow().get(&source) {
 470                     None => {
 471                         debug!("(resolving single import) no import");
 472                         // The containing module definitely doesn't have an
 473                         // exported import with the name in question. We can
 474                         // therefore accurately report that the names are
 475                         // unbound.
 476
 477                         if value_result.is_unknown() {
 478                             value_result = UnboundResult;
 479                         }
 480                         if type_result.is_unknown() {
 481                             type_result = UnboundResult;
 482                         }
 483                     }
 484                     Some(import_resolution)
 485                             if import_resolution.outstanding_references == 0 => {
 486
 487                         fn get_binding(this: &mut Resolver,
 488                                        import_resolution: &ImportResolution,
 489                                        namespace: Namespace,
 490                                        source: &Name)
 491                                     -> NamespaceResult {
 492
 493                             // Import resolutions must be declared with "pub"
 494                             // in order to be exported.
 495                             if !import_resolution.is_public {
 496                                 return UnboundResult;
 497                             }
 498
 499                             match import_resolution.target_for_namespace(namespace) {
 500                                 None => {
 501                                     return UnboundResult;
 502                                 }
 503                                 Some(Target {
 504                                     target_module,
 505                                     bindings,
 506                                     shadowable: _
 507                                 }) => {
 508                                     debug!("(resolving single import) found \
 509                                             import in ns {:?}", namespace);
 510                                     let id = import_resolution.id(namespace);
 511                                     // track used imports and extern crates as well
 512                                     this.used_imports.insert((id, namespace));
 513                                     this.record_import_use(id, *source);
 514                                     match target_module.def_id.get() {
 515                                         Some(DefId{krate: kid, ..}) => {
 516                                             this.used_crates.insert(kid);
 517                                         },
 518                                         _ => {}
 519                                     }
 520                                     return BoundResult(target_module, bindings);
 521                                 }
 522                             }
 523                         }
 524
 525                         // The name is an import which has been fully
 526                         // resolved. We can, therefore, just follow it.
 527                         if value_result.is_unknown() {
 528                             value_result = get_binding(self.resolver,
 529                                                        import_resolution,
 530                                                        ValueNS,
 531                                                        &source);
 532                             value_used_reexport = import_resolution.is_public;
 533                         }
 534                         if type_result.is_unknown() {
 535                             type_result = get_binding(self.resolver,
 536                                                       import_resolution,
 537                                                       TypeNS,
 538                                                       &source);
 539                             type_used_reexport = import_resolution.is_public;
 540                         }
 541
 542                     }
 543                     Some(_) => {
 544                         // If target_module is the same module whose import we are resolving
 545                         // and there it has an unresolved import with the same name as `source`,
 546                         // then the user is actually trying to import an item that is declared
 547                         // in the same scope
 548                         //
 549                         // e.g
 550                         // use self::submodule;
 551                         // pub mod submodule;
 552                         //
 553                         // In this case we continue as if we resolved the import and let the
 554                         // check_for_conflicts_between_imports_and_items call below handle
 555                         // the conflict
 556                         match (module_.def_id.get(),  target_module.def_id.get()) {
 557                             (Some(id1), Some(id2)) if id1 == id2  => {
 558                                 if value_result.is_unknown() {
 559                                     value_result = UnboundResult;
 560                                 }
 561                                 if type_result.is_unknown() {
 562                                     type_result = UnboundResult;
 563                                 }
 564                             }
 565                             _ =>  {
 566                                 // The import is unresolved. Bail out.
 567                                 debug!("(resolving single import) unresolved import; \
 568                                         bailing out");
 569                                 return ResolveResult::Indeterminate;
 570                             }
 571                         }
 572                     }
 573                 }
 574             }
 575         }
 576
 577         let mut value_used_public = false;
 578         let mut type_used_public = false;
 579
 580         // If we didn't find a result in the type namespace, search the
 581         // external modules.
 582         match type_result {
 583             BoundResult(..) => {}
 584             _ => {
 585                 match target_module.external_module_children.borrow_mut().get(&source).cloned() {
 586                     None => {} // Continue.
 587                     Some(module) => {
 588                         debug!("(resolving single import) found external module");
 589                         // track the module as used.
 590                         match module.def_id.get() {
 591                             Some(DefId{krate: kid, ..}) => {
 592                                 self.resolver.used_crates.insert(kid);
 593                             }
 594                             _ => {}
 595                         }
 596                         let name_bindings =
 597                             Rc::new(Resolver::create_name_bindings_from_module(module));
 598                         type_result = BoundResult(target_module.clone(), name_bindings);
 599                         type_used_public = true;
 600                     }
 601                 }
 602             }
 603         }
 604
 605         // We've successfully resolved the import. Write the results in.
 606         let mut import_resolutions = module_.import_resolutions.borrow_mut();
 607         let import_resolution = import_resolutions.get_mut(&target).unwrap();
 608
 609         {
 610             let mut check_and_write_import = |namespace, result: &_, used_public: &mut bool| {
 611                 let namespace_name = match namespace {
 612                     TypeNS => "type",
 613                     ValueNS => "value",
 614                 };
 615
 616                 match *result {
 617                     BoundResult(ref target_module, ref name_bindings) => {
 618                         debug!("(resolving single import) found {:?} target: {:?}",
 619                                namespace_name,
 620                                name_bindings.def_for_namespace(namespace));
 621                         self.check_for_conflicting_import(
 622                             &import_resolution,
 623                             directive.span,
 624                             target,
 625                             namespace);
 626
 627                         self.check_that_import_is_importable(
 628                             &**name_bindings,
 629                             directive.span,
 630                             target,
 631                             namespace);
 632
 633                         let target = Some(Target::new(target_module.clone(),
 634                                                       name_bindings.clone(),
 635                                                       directive.shadowable));
 636                         import_resolution.set_target_and_id(namespace, target, directive.id);
 637                         import_resolution.is_public = directive.is_public;
 638                         *used_public = name_bindings.defined_in_public_namespace(namespace);
 639                     }
 640                     UnboundResult => { /* Continue. */ }
 641                     UnknownResult => {
 642                         panic!("{:?} result should be known at this point", namespace_name);
 643                     }
 644                 }
 645             };
 646             check_and_write_import(ValueNS, &value_result, &mut value_used_public);
 647             check_and_write_import(TypeNS, &type_result, &mut type_used_public);
 648         }
 649
 650         self.check_for_conflicts_between_imports_and_items(
 651             module_,
 652             import_resolution,
 653             directive.span,
 654             target);
 655
 656         if value_result.is_unbound() && type_result.is_unbound() {
 657             let msg = format!("There is no `{}` in `{}`",
 658                               source,
 659                               module_to_string(&target_module));
 660             return ResolveResult::Failed(Some((directive.span, msg)));
 661         }
 662         let value_used_public = value_used_reexport || value_used_public;
 663         let type_used_public = type_used_reexport || type_used_public;
 664
 665         assert!(import_resolution.outstanding_references >= 1);
 666         import_resolution.outstanding_references -= 1;
 667
 668         // Record what this import resolves to for later uses in documentation,
 669         // this may resolve to either a value or a type, but for documentation
 670         // purposes it's good enough to just favor one over the other.
 671         let value_def_and_priv = import_resolution.value_target.as_ref().map(|target| {
 672             let def = target.bindings.def_for_namespace(ValueNS).unwrap();
 673             (def, if value_used_public { lp } else { DependsOn(def.def_id()) })
 674         });
 675         let type_def_and_priv = import_resolution.type_target.as_ref().map(|target| {
 676             let def = target.bindings.def_for_namespace(TypeNS).unwrap();
 677             (def, if type_used_public { lp } else { DependsOn(def.def_id()) })
 678         });
 679
 680         let import_lp = LastImport {
 681             value_priv: value_def_and_priv.map(|(_, p)| p),
 682             value_used: Used,
 683             type_priv: type_def_and_priv.map(|(_, p)| p),
 684             type_used: Used
 685         };
 686
 687         if let Some((def, _)) = value_def_and_priv {
 688             self.resolver.def_map.borrow_mut().insert(directive.id, PathResolution {
 689                 base_def: def,
 690                 last_private: import_lp,
 691                 depth: 0
 692             });
 693         }
 694         if let Some((def, _)) = type_def_and_priv {
 695             self.resolver.def_map.borrow_mut().insert(directive.id, PathResolution {
 696                 base_def: def,
 697                 last_private: import_lp,
 698                 depth: 0
 699             });
 700         }
 701
 702         debug!("(resolving single import) successfully resolved import");
 703         return ResolveResult::Success(());
 704     }
 705
 706     // Resolves a glob import. Note that this function cannot fail; it either
 707     // succeeds or bails out (as importing * from an empty module or a module
 708     // that exports nothing is valid). target_module is the module we are
 709     // actually importing, i.e., `foo` in `use foo::*`.
 710     fn resolve_glob_import(&mut self,
 711                            module_: &Module,
 712                            target_module: Rc<Module>,
 713                            import_directive: &ImportDirective,
 714                            lp: LastPrivate)
 715                            -> ResolveResult<()> {
 716         let id = import_directive.id;
 717         let is_public = import_directive.is_public;
 718
 719         // This function works in a highly imperative manner; it eagerly adds
 720         // everything it can to the list of import resolutions of the module
 721         // node.
 722         debug!("(resolving glob import) resolving glob import {}", id);
 723
 724         // We must bail out if the node has unresolved imports of any kind
 725         // (including globs).
 726         if !(*target_module).all_imports_resolved() {
 727             debug!("(resolving glob import) target module has unresolved \
 728                     imports; bailing out");
 729             return ResolveResult::Indeterminate;
 730         }
 731
 732         assert_eq!(target_module.glob_count.get(), 0);
 733
 734         // Add all resolved imports from the containing module.
 735         let import_resolutions = target_module.import_resolutions.borrow();
 736         for (ident, target_import_resolution) in import_resolutions.iter() {
 737             debug!("(resolving glob import) writing module resolution \
 738                     {} into `{}`",
 739                    *ident,
 740                    module_to_string(module_));
 741
 742             if !target_import_resolution.is_public {
 743                 debug!("(resolving glob import) nevermind, just kidding");
 744                 continue
 745             }
 746
 747             // Here we merge two import resolutions.
 748             let mut import_resolutions = module_.import_resolutions.borrow_mut();
 749             match import_resolutions.get_mut(ident) {
 750                 Some(dest_import_resolution) => {
 751                     // Merge the two import resolutions at a finer-grained
 752                     // level.
 753
 754                     match target_import_resolution.value_target {
 755                         None => {
 756                             // Continue.
 757                         }
 758                         Some(ref value_target) => {
 759                             self.check_for_conflicting_import(&dest_import_resolution,
 760                                                               import_directive.span,
 761                                                               *ident,
 762                                                               ValueNS);
 763                             dest_import_resolution.value_target = Some(value_target.clone());
 764                         }
 765                     }
 766                     match target_import_resolution.type_target {
 767                         None => {
 768                             // Continue.
 769                         }
 770                         Some(ref type_target) => {
 771                             self.check_for_conflicting_import(&dest_import_resolution,
 772                                                               import_directive.span,
 773                                                               *ident,
 774                                                               TypeNS);
 775                             dest_import_resolution.type_target = Some(type_target.clone());
 776                         }
 777                     }
 778                     dest_import_resolution.is_public = is_public;
 779                     continue;
 780                 }
 781                 None => {}
 782             }
 783
 784             // Simple: just copy the old import resolution.
 785             let mut new_import_resolution = ImportResolution::new(id, is_public);
 786             new_import_resolution.value_target =
 787                 target_import_resolution.value_target.clone();
 788             new_import_resolution.type_target =
 789                 target_import_resolution.type_target.clone();
 790
 791             import_resolutions.insert(*ident, new_import_resolution);
 792         }
 793
 794         // Add all children from the containing module.
 795         build_reduced_graph::populate_module_if_necessary(self.resolver, &target_module);
 796
 797         for (&name, name_bindings) in target_module.children.borrow().iter() {
 798             self.merge_import_resolution(module_,
 799                                          target_module.clone(),
 800                                          import_directive,
 801                                          name,
 802                                          name_bindings.clone());
 803
 804         }
 805
 806         // Add external module children from the containing module.
 807         for (&name, module) in target_module.external_module_children.borrow().iter() {
 808             let name_bindings =
 809                 Rc::new(Resolver::create_name_bindings_from_module(module.clone()));
 810             self.merge_import_resolution(module_,
 811                                          target_module.clone(),
 812                                          import_directive,
 813                                          name,
 814                                          name_bindings);
 815         }
 816
 817         // Record the destination of this import
 818         if let Some(did) = target_module.def_id.get() {
 819             self.resolver.def_map.borrow_mut().insert(id, PathResolution {
 820                 base_def: DefMod(did),
 821                 last_private: lp,
 822                 depth: 0
 823             });
 824         }
 825
 826         debug!("(resolving glob import) successfully resolved import");
 827         return ResolveResult::Success(());
 828     }
 829
 830     fn merge_import_resolution(&mut self,
 831                                module_: &Module,
 832                                containing_module: Rc<Module>,
 833                                import_directive: &ImportDirective,
 834                                name: Name,
 835                                name_bindings: Rc<NameBindings>) {
 836         let id = import_directive.id;
 837         let is_public = import_directive.is_public;
 838
 839         let mut import_resolutions = module_.import_resolutions.borrow_mut();
 840         let dest_import_resolution = import_resolutions.entry(name)
 841             .or_insert_with(|| ImportResolution::new(id, is_public));
 842
 843         debug!("(resolving glob import) writing resolution `{}` in `{}` \
 844                to `{}`",
 845                name,
 846                module_to_string(&*containing_module),
 847                module_to_string(module_));
 848
 849         // Merge the child item into the import resolution.
 850         {
 851             let mut merge_child_item = |namespace| {
 852                 let modifier = DefModifiers::IMPORTABLE | DefModifiers::PUBLIC;
 853
 854                 if name_bindings.defined_in_namespace_with(namespace, modifier) {
 855                     let namespace_name = match namespace {
 856                         TypeNS => "type",
 857                         ValueNS => "value",
 858                     };
 859                     debug!("(resolving glob import) ... for {} target", namespace_name);
 860                     if dest_import_resolution.shadowable(namespace) == Shadowable::Never {
 861                         let msg = format!("a {} named `{}` has already been imported \
 862                                            in this module",
 863                                           namespace_name,
 864                                           name);
 865                         span_err!(self.resolver.session, import_directive.span, E0251, "{}", msg);
 866                     } else {
 867                         let target = Target::new(containing_module.clone(),
 868                                                  name_bindings.clone(),
 869                                                  import_directive.shadowable);
 870                         dest_import_resolution.set_target_and_id(namespace,
 871                                                                  Some(target),
 872                                                                  id);
 873                     }
 874                 }
 875             };
 876             merge_child_item(ValueNS);
 877             merge_child_item(TypeNS);
 878         }
 879
 880         dest_import_resolution.is_public = is_public;
 881
 882         self.check_for_conflicts_between_imports_and_items(
 883             module_,
 884             dest_import_resolution,
 885             import_directive.span,
 886             name);
 887     }
 888
 889     /// Checks that imported names and items don't have the same name.
 890     fn check_for_conflicting_import(&mut self,
 891                                     import_resolution: &ImportResolution,
 892                                     import_span: Span,
 893                                     name: Name,
 894                                     namespace: Namespace) {
 895         let target = import_resolution.target_for_namespace(namespace);
 896         debug!("check_for_conflicting_import: {}; target exists: {}",
 897                name,
 898                target.is_some());
 899
 900         match target {
 901             Some(ref target) if target.shadowable != Shadowable::Always => {
 902                 let ns_word = match namespace {
 903                     TypeNS => {
 904                         if let Some(ref ty_def) = *target.bindings.type_def.borrow() {
 905                             match ty_def.module_def {
 906                                 Some(ref module)
 907                                     if module.kind.get() == ModuleKind::NormalModuleKind =>
 908                                         "module",
 909                                 Some(ref module)
 910                                     if module.kind.get() == ModuleKind::TraitModuleKind =>
 911                                         "trait",
 912                                 _ => "type",
 913                             }
 914                         } else { "type" }
 915                     },
 916                     ValueNS => "value",
 917                 };
 918                 span_err!(self.resolver.session, import_span, E0252,
 919                           "a {} named `{}` has already been imported \
 920                            in this module", ns_word,
 921                                   name);
 922                 let use_id = import_resolution.id(namespace);
 923                 let item = self.resolver.ast_map.expect_item(use_id);
 924                 // item is syntax::ast::Item;
 925                 span_note!(self.resolver.session, item.span,
 926                             "previous import of `{}` here",
 927                             name);
 928             }
 929             Some(_) | None => {}
 930         }
 931     }
 932
 933     /// Checks that an import is actually importable
 934     fn check_that_import_is_importable(&mut self,
 935                                        name_bindings: &NameBindings,
 936                                        import_span: Span,
 937                                        name: Name,
 938                                        namespace: Namespace) {
 939         if !name_bindings.defined_in_namespace_with(namespace, DefModifiers::IMPORTABLE) {
 940             let msg = format!("`{}` is not directly importable",
 941                               name);
 942             span_err!(self.resolver.session, import_span, E0253, "{}", &msg[..]);
 943         }
 944     }
 945
 946     /// Checks that imported names and items don't have the same name.
 947     fn check_for_conflicts_between_imports_and_items(&mut self,
 948                                                      module: &Module,
 949                                                      import_resolution:
 950                                                      &ImportResolution,
 951                                                      import_span: Span,
 952                                                      name: Name) {
 953         // First, check for conflicts between imports and `extern crate`s.
 954         if module.external_module_children
 955                  .borrow()
 956                  .contains_key(&name) {
 957             match import_resolution.type_target {
 958                 Some(ref target) if target.shadowable != Shadowable::Always => {
 959                     let msg = format!("import `{0}` conflicts with imported \
 960                                        crate in this module \
 961                                        (maybe you meant `use {0}::*`?)",
 962                                       name);
 963                     span_err!(self.resolver.session, import_span, E0254, "{}", &msg[..]);
 964                 }
 965                 Some(_) | None => {}
 966             }
 967         }
 968
 969         // Check for item conflicts.
 970         let children = module.children.borrow();
 971         let name_bindings = match children.get(&name) {
 972             None => {
 973                 // There can't be any conflicts.
 974                 return
 975             }
 976             Some(ref name_bindings) => (*name_bindings).clone(),
 977         };
 978
 979         match import_resolution.value_target {
 980             Some(ref target) if target.shadowable != Shadowable::Always => {
 981                 if let Some(ref value) = *name_bindings.value_def.borrow() {
 982                     span_err!(self.resolver.session, import_span, E0255,
 983                               "import `{}` conflicts with value in this module",
 984                               name);
 985                     if let Some(span) = value.value_span {
 986                         self.resolver.session.span_note(span, "conflicting value here");
 987                     }
 988                 }
 989             }
 990             Some(_) | None => {}
 991         }
 992
 993         match import_resolution.type_target {
 994             Some(ref target) if target.shadowable != Shadowable::Always => {
 995                 if let Some(ref ty) = *name_bindings.type_def.borrow() {
 996                     let (what, note) = match ty.module_def {
 997                         Some(ref module)
 998                             if module.kind.get() == ModuleKind::NormalModuleKind =>
 999                                 ("existing submodule", "note conflicting module here"),
1000                         Some(ref module)
1001                             if module.kind.get() == ModuleKind::TraitModuleKind =>
1002                                 ("trait in this module", "note conflicting trait here"),
1003                         _    => ("type in this module", "note conflicting type here"),
1004                     };
1005                     span_err!(self.resolver.session, import_span, E0256,
1006                               "import `{}` conflicts with {}",
1007                               name, what);
1008                     if let Some(span) = ty.type_span {
1009                         self.resolver.session.span_note(span, note);
1010                     }
1011                 }
1012             }
1013             Some(_) | None => {}
1014         }
1015     }
1016 }
1017
1018 fn import_path_to_string(names: &[Name],
1019                          subclass: ImportDirectiveSubclass)
1020                          -> String {
1021     if names.is_empty() {
1022         import_directive_subclass_to_string(subclass)
1023     } else {
1024         (format!("{}::{}",
1025                  names_to_string(names),
1026                  import_directive_subclass_to_string(subclass))).to_string()
1027     }
1028 }
1029
1030 fn import_directive_subclass_to_string(subclass: ImportDirectiveSubclass) -> String {
1031     match subclass {
1032         SingleImport(_, source) => {
1033             token::get_name(source).to_string()
1034         }
1035         GlobImport => "*".to_string()
1036     }
1037 }
1038
1039 pub fn resolve_imports(resolver: &mut Resolver) {
1040     let mut import_resolver = ImportResolver {
1041         resolver: resolver,
1042     };
1043     import_resolver.resolve_imports();
1044 }