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