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