content: // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
  // for details. All rights reserved. Use of this source code is governed by a
  // BSD-style license that can be found in the LICENSE file.
  
  part of dart2js;
  
  /**
   * [CompilerTask] for loading libraries and setting up the import/export scopes.
   *
   * The library loader uses four different kinds of URIs in different parts of
   * the loading process.
   *
   * ## User URI ##
   *
   * A 'user URI' is a URI provided by the user in code and as the main entry URI
   * at the command line. These generally come in 3 versions:
   *
   *   * A relative URI such as 'foo.dart', '../bar.dart', and 'baz/boz.dart'.
   *
   *   * A dart URI such as 'dart:core' and 'dart:_js_helper'.
   *
   *   * A package URI such as 'package:foo.dart' and 'package:bar/baz.dart'.
   *
   * A user URI can also be absolute, like 'file:///foo.dart' or
   * 'http://example.com/bar.dart', but such URIs cannot necessarily be used for
   * locating source files, since the scheme must be supported by the input
   * provider. The standard input provider for dart2js only supports the 'file'
   * scheme.
   *
   * ## Resolved URI ##
   *
   * A 'resolved URI' is a (user) URI that has been resolved to an absolute URI
   * based on the readable URI (see below) from which it was loaded. A URI with an
   * explicit scheme (such as 'dart:', 'package:' or 'file:') is already resolved.
   * A relative URI like for instance '../foo/bar.dart' is translated into an
   * resolved URI in one of three ways:
   *
   *  * If provided as the main entry URI at the command line, the URI is resolved
   *    relative to the current working directory, say
   *    'file:///current/working/dir/', and the resolved URI is therefore
   *    'file:///current/working/foo/bar.dart'.
   *
   *  * If the relative URI is provided in an import, export or part tag, and the
   *    readable URI of the enclosing compilation unit is a file URI,
   *    'file://some/path/baz.dart', then the resolved URI is
   *    'file://some/foo/bar.dart'.
   *
   *  * If the relative URI is provided in an import, export or part tag, and the
   *    readable URI of the enclosing compilation unit is a package URI,
   *    'package:some/path/baz.dart', then the resolved URI is
   *    'package:some/foo/bar.dart'.
   *
   * The resolved URI thus preserves the scheme through resolution: A readable
   * file URI results in an resolved file URI and a readable package URI results
   * in an resolved package URI. Note that since a dart URI is not a readable URI,
   * import, export or part tags within platform libraries are not interpreted as
   * dart URIs but instead relative to the library source file location.
   *
   * The resolved URI of a library is also used as the canonical URI
   * ([LibraryElement.canonicalUri]) by which we identify which libraries are
   * identical. This means that libraries loaded through the 'package' scheme will
   * resolve to the same library when loaded from within using relative URIs (see
   * for instance the test 'standalone/package/package1_test.dart'). But loading a
   * platform library using a relative URI will _not_ result in the same library
   * as when loaded through the dart URI.
   *
   * ## Readable URI ##
   *
   * A 'readable URI' is an absolute URI whose scheme is either 'package' or
   * something supported by the input provider, normally 'file'. Dart URIs such as
   * 'dart:core' and 'dart:_js_helper' are not readable themselves but are instead
   * resolved into a readable URI using the library root URI provided from the
   * command line and the list of platform libraries found in
   * 'sdk/lib/_internal/libraries.dart'. This is done through the
   * [Compiler.translateResolvedUri] method which checks whether a library by that
   * name exists and in case of internal libraries whether access is granted.
   *
   * ## Resource URI ##
   *
   * A 'resource URI' is an absolute URI with a scheme supported by the input
   * provider. For the standard implementation this means a URI with the 'file'
   * scheme. Readable URIs are converted into resource URIs as part of the
   * [Compiler.readScript] method. In the standard implementation the package URIs
   * are converted to file URIs using the package root URI provided on the
   * command line as base. If the package root URI is
   * 'file:///current/working/dir/' then the package URI 'package:foo/bar.dart'
   * will be resolved to the resource URI
   * 'file:///current/working/dir/foo/bar.dart'.
   *
   * The distinction between readable URI and resource URI is necessary to ensure
   * that these imports
   *
   *     import 'package:foo.dart' as a;
   *     import 'packages/foo.dart' as b;
   *
   * do _not_ resolve to the same library when the package root URI happens to
   * point to the 'packages' folder.
   *
   */
  abstract class LibraryLoader extends CompilerTask {
    LibraryLoader(Compiler compiler) : super(compiler);
  
    /**
     * Loads the library specified by the [resolvedUri] and returns its
     * [LibraryElement].
     *
     * If the library is not already loaded, the method creates the
     * [LibraryElement] for the library and computes the import/export scope,
     * loading and computing the import/export scopes of all required libraries in
     * the process. The method handles cyclic dependency between libraries.
     *
     * This is the main entry point for [LibraryLoader].
     */
    // TODO(johnniwinther): Remove [canonicalUri] together with
    // [Compiler.scanBuiltinLibrary].
    Future<LibraryElement> loadLibrary(Uri resolvedUri, Node node,
                                       Uri canonicalUri);
  
    // TODO(johnniwinther): Remove this when patches don't need special parsing.
    Future registerLibraryFromTag(LibraryDependencyHandler handler,
                                  LibraryElement library,
                                  LibraryDependency tag);
  
    /**
     * Adds the elements in the export scope of [importedLibrary] to the import
     * scope of [importingLibrary].
     */
    // TODO(johnniwinther): Move handling of 'js_helper' to the library loader
    // to remove this method from the [LibraryLoader] interface.
    void importLibrary(LibraryElement importingLibrary,
                       LibraryElement importedLibrary,
                       Import tag);
  }
  
  /**
   * [CombinatorFilter] is a succinct representation of a list of combinators from
   * a library dependency tag.
   */
  class CombinatorFilter {
    const CombinatorFilter();
  
    /**
     * Returns [:true:] if [element] is excluded by this filter.
     */
    bool exclude(Element element) => false;
  
    /**
     * Creates a filter based on the combinators of [tag].
     */
    factory CombinatorFilter.fromTag(LibraryDependency tag) {
      if (tag == null || tag.combinators == null) {
        return const CombinatorFilter();
      }
  
      // If the list of combinators contain at least one [:show:] we can create
      // a positive list of elements to include, otherwise we create a negative
      // list of elements to exclude.
      bool show = false;
      Set<String> nameSet;
      for (Combinator combinator in tag.combinators) {
        if (combinator.isShow) {
          show = true;
          var set = new Set<String>();
          for (Identifier identifier in combinator.identifiers) {
            set.add(identifier.source);
          }
          if (nameSet == null) {
            nameSet = set;
          } else {
            nameSet = nameSet.intersection(set);
          }
        }
      }
      if (nameSet == null) {
        nameSet = new Set<String>();
      }
      for (Combinator combinator in tag.combinators) {
        if (combinator.isHide) {
          for (Identifier identifier in combinator.identifiers) {
            if (show) {
              // We have a positive list => Remove hidden elements.
              nameSet.remove(identifier.source);
            } else {
              // We have no positive list => Accumulate hidden elements.
              nameSet.add(identifier.source);
            }
          }
        }
      }
      return show ? new ShowFilter(nameSet) : new HideFilter(nameSet);
    }
  }
  
  /**
   * A list of combinators represented as a list of element names to include.
   */
  class ShowFilter extends CombinatorFilter {
    final Set<String> includedNames;
  
    ShowFilter(this.includedNames);
  
    bool exclude(Element element) => !includedNames.contains(element.name);
  }
  
  /**
   * A list of combinators represented as a list of element names to exclude.
   */
  class HideFilter extends CombinatorFilter {
    final Set<String> excludedNames;
  
    HideFilter(this.excludedNames);
  
    bool exclude(Element element) => excludedNames.contains(element.name);
  }
  
  /**
   * Implementation class for [LibraryLoader]. The distinction between
   * [LibraryLoader] and [LibraryLoaderTask] is made to hide internal members from
   * the [LibraryLoader] interface.
   */
  class LibraryLoaderTask extends LibraryLoader {
    LibraryLoaderTask(Compiler compiler) : super(compiler);
    String get name => 'LibraryLoader';
    List onLibraryLoadedCallbacks = [];
  
    final Map<String, LibraryElement> libraryNames =
        new Map<String, LibraryElement>();
  
    LibraryDependencyHandler currentHandler;
  
    Future<LibraryElement> loadLibrary(Uri resolvedUri, Node node,
        Uri canonicalUri) {
      return measure(() {
        assert(currentHandler == null);
        // TODO(johnniwinther): Ensure that currentHandler correctly encloses the
        // loading of a library cluster.
        currentHandler = new LibraryDependencyHandler(compiler);
        return createLibrary(currentHandler, null, resolvedUri, node,
            canonicalUri).then((LibraryElement library) {
          return compiler.withCurrentElement(library, () {
            return measure(() {
              currentHandler.computeExports();
              currentHandler = null;
              var workList = onLibraryLoadedCallbacks;
              onLibraryLoadedCallbacks = [];
              return Future.forEach(workList, (f) => f()).then((_) => library);
            });
          });
        });
      });
    }
  
    /**
     * Processes the library tags in [library].
     *
     * The imported/exported libraries are loaded and processed recursively but
     * the import/export scopes are not set up.
     */
    Future processLibraryTags(LibraryDependencyHandler handler,
                              LibraryElement library) {
      int tagState = TagState.NO_TAG_SEEN;
  
      /**
       * If [value] is less than [tagState] complain and return
       * [tagState]. Otherwise return the new value for [tagState]
       * (transition function for state machine).
       */
      int checkTag(int value, LibraryTag tag) {
        if (tagState > value) {
          compiler.reportFatalError(
              tag,
              MessageKind.GENERIC, {'text': 'Error: Out of order.'});
          return tagState;
        }
        return TagState.NEXT[value];
      }
  
      bool importsDartCore = false;
      var libraryDependencies = new LinkBuilder<LibraryDependency>();
      Uri base = library.entryCompilationUnit.script.uri;
  
      // TODO(rnystrom): Remove .toList() here if #11523 is fixed.
      return Future.forEach(library.tags.reverse().toList(), (LibraryTag tag) {
        return compiler.withCurrentElement(library, () {
          if (tag.isImport) {
            Import import = tag;
            tagState = checkTag(TagState.IMPORT_OR_EXPORT, import);
            if (import.uri.dartString.slowToString() == 'dart:core') {
              importsDartCore = true;
            }
            libraryDependencies.addLast(import);
          } else if (tag.isExport) {
            tagState = checkTag(TagState.IMPORT_OR_EXPORT, tag);
            libraryDependencies.addLast(tag);
          } else if (tag.isLibraryName) {
            tagState = checkTag(TagState.LIBRARY, tag);
            if (library.libraryTag != null) {
              compiler.cancel("duplicated library declaration", node: tag);
            } else {
              library.libraryTag = tag;
            }
            checkDuplicatedLibraryName(library);
          } else if (tag.isPart) {
            Part part = tag;
            StringNode uri = part.uri;
            Uri resolvedUri = base.resolve(uri.dartString.slowToString());
            tagState = checkTag(TagState.SOURCE, part);
            return scanPart(part, resolvedUri, library);
          } else {
            compiler.internalError("Unhandled library tag.", node: tag);
          }
        });
      }).then((_) {
        return compiler.withCurrentElement(library, () {
          // Apply patch, if any.
          if (library.isPlatformLibrary) {
            return patchDartLibrary(handler, library, library.canonicalUri.path);
          }
        });
      }).then((_) {
        return compiler.withCurrentElement(library, () {
          // Import dart:core if not already imported.
          if (!importsDartCore && !isDartCore(library.canonicalUri)) {
            return loadCoreLibrary(handler).then((LibraryElement coreLibrary) {
              handler.registerDependency(library, null, coreLibrary);
            });
          }
        });
      }).then((_) {
        // TODO(rnystrom): Remove .toList() here if #11523 is fixed.
        return Future.forEach(libraryDependencies.toLink().toList(), (tag) {
          return compiler.withCurrentElement(library, () {
            return registerLibraryFromTag(handler, library, tag);
          });
        });
      });
    }
  
    void checkDuplicatedLibraryName(LibraryElement library) {
      LibraryName tag = library.libraryTag;
      if (tag != null) {
        String name = library.getLibraryOrScriptName();
        LibraryElement existing =
            libraryNames.putIfAbsent(name, () => library);
        if (!identical(existing, library)) {
          Uri uri = library.entryCompilationUnit.script.uri;
          compiler.reportMessage(
              compiler.spanFromSpannable(tag.name, uri),
              MessageKind.DUPLICATED_LIBRARY_NAME.error({'libraryName': name}),
              api.Diagnostic.WARNING);
          Uri existingUri = existing.entryCompilationUnit.script.uri;
          compiler.reportMessage(
              compiler.spanFromSpannable(existing.libraryTag.name, existingUri),
              MessageKind.DUPLICATED_LIBRARY_NAME.error({'libraryName': name}),
              api.Diagnostic.WARNING);
        }
      }
    }
  
    bool isDartCore(Uri uri) => uri.scheme == "dart" && uri.path == "core";
  
    /**
     * Lazily loads and returns the [LibraryElement] for the dart:core library.
     */
    Future<LibraryElement> loadCoreLibrary(LibraryDependencyHandler handler) {
      if (compiler.coreLibrary != null) {
        return new Future.value(compiler.coreLibrary);
      }
  
      Uri coreUri = new Uri(scheme: 'dart', path: 'core');
      return createLibrary(handler, null, coreUri, null, coreUri)
          .then((LibraryElement library) {
        compiler.coreLibrary = library;
        return library;
      });
    }
  
    Future patchDartLibrary(LibraryDependencyHandler handler,
                          LibraryElement library, String dartLibraryPath) {
      if (library.isPatched) return new Future.value();
      Uri patchUri = compiler.resolvePatchUri(dartLibraryPath);
      if (patchUri == null) return new Future.value();
  
      return compiler.patchParser.patchLibrary(handler, patchUri, library);
    }
  
    /**
     * Handle a part tag in the scope of [library]. The [resolvedUri] given is
     * used as is, any URI resolution should be done beforehand.
     */
    Future scanPart(Part part, Uri resolvedUri, LibraryElement library) {
      if (!resolvedUri.isAbsolute) throw new ArgumentError(resolvedUri);
      Uri readableUri = compiler.translateResolvedUri(library, resolvedUri, part);
      if (readableUri == null) return new Future.value();
      return compiler.readScript(readableUri, library, part).
          then((Script sourceScript) {
            if (sourceScript == null) return;
            CompilationUnitElement unit =
                new CompilationUnitElementX(sourceScript, library);
            compiler.withCurrentElement(unit, () {
              compiler.scanner.scan(unit);
              if (unit.partTag == null) {
                compiler.reportError(unit, MessageKind.MISSING_PART_OF_TAG);
              }
            });
          });
    }
  
    /**
     * Handle an import/export tag by loading the referenced library and
     * registering its dependency in [handler] for the computation of the import/
     * export scope.
     */
    Future registerLibraryFromTag(LibraryDependencyHandler handler,
                                  LibraryElement library,
                                  LibraryDependency tag) {
      Uri base = library.entryCompilationUnit.script.uri;
      Uri resolvedUri = base.resolve(tag.uri.dartString.slowToString());
      return createLibrary(handler, library, resolvedUri, tag.uri, resolvedUri)
          .then((LibraryElement loadedLibrary) {
            if (loadedLibrary == null) return;
            compiler.withCurrentElement(library, () {
              handler.registerDependency(library, tag, loadedLibrary);
            });
          });
    }
  
    /**
     * Create (or reuse) a library element for the library specified by the
     * [resolvedUri].
     *
     * If a new library is created, the [handler] is notified.
     */
    // TODO(johnniwinther): Remove [canonicalUri] and make [resolvedUri] the
    // canonical uri when [Compiler.scanBuiltinLibrary] is removed.
    Future<LibraryElement> createLibrary(LibraryDependencyHandler handler,
                                 LibraryElement importingLibrary,
                                 Uri resolvedUri, Node node, Uri canonicalUri) {
      // TODO(johnniwinther): Create erroneous library elements for missing
      // libraries.
      Uri readableUri =
          compiler.translateResolvedUri(importingLibrary, resolvedUri, node);
      if (readableUri == null) return new Future.value();
      LibraryElement library;
      if (canonicalUri != null) {
        library = compiler.libraries[canonicalUri.toString()];
      }
      if (library != null) {
        return new Future.value(library);
      }
      return compiler.readScript(readableUri, importingLibrary, node)
          .then((Script script) {
            if (script == null) return null;
            LibraryElement element = new LibraryElementX(script, canonicalUri);
            compiler.withCurrentElement(element, () {
              handler.registerNewLibrary(element);
              native.maybeEnableNative(compiler, element);
              if (canonicalUri != null) {
                compiler.libraries[canonicalUri.toString()] = element;
              }
              compiler.scanner.scanLibrary(element);
            });
            return processLibraryTags(handler, element).then((_) {
              compiler.withCurrentElement(element, () {
                handler.registerLibraryExports(element);
                onLibraryLoadedCallbacks.add(
                    () => compiler.onLibraryLoaded(element, resolvedUri));
              });
              return element;
            });
          });
    }
  
    // TODO(johnniwinther): Remove this method when 'js_helper' is handled by
    // [LibraryLoaderTask].
    void importLibrary(LibraryElement importingLibrary,
                       LibraryElement importedLibrary,
                       Import tag) {
      new ImportLink(tag, importedLibrary).importLibrary(compiler,
                                                         importingLibrary);
    }
  }
  
  
  /**
   * The fields of this class models a state machine for checking script
   * tags come in the correct order.
   */
  class TagState {
    static const int NO_TAG_SEEN = 0;
    static const int LIBRARY = 1;
    static const int IMPORT_OR_EXPORT = 2;
    static const int SOURCE = 3;
    static const int RESOURCE = 4;
  
    /** Next state. */
    static const List<int> NEXT =
        const <int>[NO_TAG_SEEN,
                    IMPORT_OR_EXPORT, // Only one library tag is allowed.
                    IMPORT_OR_EXPORT,
                    SOURCE,
                    RESOURCE];
  }
  
  /**
   * An [import] tag and the [importedLibrary] imported through [import].
   */
  class ImportLink {
    final Import import;
    final LibraryElement importedLibrary;
  
    ImportLink(this.import, this.importedLibrary);
  
    /**
     * Imports the library into the [importingLibrary].
     */
    void importLibrary(Compiler compiler, LibraryElement importingLibrary) {
      assert(invariant(importingLibrary,
                       importedLibrary.exportsHandled,
                       message: 'Exports not handled on $importedLibrary'));
      var combinatorFilter = new CombinatorFilter.fromTag(import);
      if (import != null && import.prefix != null) {
        String prefix = import.prefix.source;
        Element existingElement = importingLibrary.find(prefix);
        PrefixElement prefixElement;
        if (existingElement == null || !existingElement.isPrefix()) {
          prefixElement = new PrefixElementX(prefix,
              importingLibrary.entryCompilationUnit, import.getBeginToken());
        } else {
          prefixElement = existingElement;
        }
        importingLibrary.addToScope(prefixElement, compiler);
        importedLibrary.forEachExport((Element element) {
          if (combinatorFilter.exclude(element)) return;
          prefixElement.addImport(element, import, compiler);
        });
      } else {
        importedLibrary.forEachExport((Element element) {
          compiler.withCurrentElement(importingLibrary, () {
            if (combinatorFilter.exclude(element)) return;
            importingLibrary.addImport(element, import, compiler);
          });
        });
      }
    }
  }
  
  /**
   * The combinator filter computed from an export tag and the library dependency
   * node for the library that declared the export tag. This represents an edge in
   * the library dependency graph.
   */
  class ExportLink {
    final Export export;
    final CombinatorFilter combinatorFilter;
    final LibraryDependencyNode exportNode;
  
    ExportLink(Export export, LibraryDependencyNode this.exportNode)
        : this.export = export,
          this.combinatorFilter = new CombinatorFilter.fromTag(export);
  
    /**
     * Exports [element] to the dependent library unless [element] is filtered by
     * the export combinators. Returns [:true:] if the set pending exports of the
     * dependent library was modified.
     */
    bool exportElement(Element element) {
      if (combinatorFilter.exclude(element)) return false;
      return exportNode.addElementToPendingExports(element, export);
    }
  }
  
  /**
   * A node in the library dependency graph.
   *
   * This class is used to collect the library dependencies expressed through
   * import and export tags, and as the work-list entry in computations of library
   * exports performed in [LibraryDependencyHandler.computeExports].
   */
  class LibraryDependencyNode {
    final LibraryElement library;
  
    // TODO(ahe): Remove [hashCodeCounter] and [hashCode] when
    // VM implementation of Object.hashCode is not slow.
    final int hashCode = ++hashCodeCounter;
    static int hashCodeCounter = 0;
  
  
    /**
     * A linked list of the import tags that import [library] mapped to the
     * corresponding libraries. This is used to propagate exports into imports
     * after the export scopes have been computed.
     */
    Link<ImportLink> imports = const Link<ImportLink>();
  
    /**
     * A linked list of the export tags the dependent upon this node library.
     * This is used to propagate exports during the computation of export scopes.
     */
    Link<ExportLink> dependencies = const Link<ExportLink>();
  
    /**
     * The export scope for [library] which is gradually computed by the work-list
     * computation in [LibraryDependencyHandler.computeExports].
     */
    Map<String, Element> exportScope =
        new Map<String, Element>();
  
    /// Map from exported elements to the export directives that exported them.
    Map<Element, Link<Export>> exporters = new Map<Element, Link<Export>>();
  
    /**
     * The set of exported elements that need to be propageted to dependent
     * libraries as part of the work-list computation performed in
     * [LibraryDependencyHandler.computeExports]. Each export element is mapped
     * to a list of exports directives that export it.
     */
    Map<Element, Link<Export>> pendingExportMap =
        new Map<Element, Link<Export>>();
  
    LibraryDependencyNode(LibraryElement this.library);
  
    /**
     * Registers that the library of this node imports [importLibrary] through the
     * [import] tag.
     */
    void registerImportDependency(Import import,
                                  LibraryElement importedLibrary) {
      imports = imports.prepend(new ImportLink(import, importedLibrary));
    }
  
    /**
     * Registers that the library of this node is exported by
     * [exportingLibraryNode] through the [export] tag.
     */
    void registerExportDependency(Export export,
                                  LibraryDependencyNode exportingLibraryNode) {
      dependencies =
          dependencies.prepend(new ExportLink(export, exportingLibraryNode));
    }
  
    /**
     * Registers all non-private locally declared members of the library of this
     * node to be exported. This forms the basis for the work-list computation of
     * the export scopes performed in [LibraryDependencyHandler.computeExports].
     */
    void registerInitialExports() {
      for (Element element in library.getNonPrivateElementsInScope()) {
        pendingExportMap[element] = const Link<Export>();
      }
    }
  
    void registerHandledExports(LibraryElement exportedLibraryElement,
                                Export export,
                                CombinatorFilter filter) {
      assert(invariant(library, exportedLibraryElement.exportsHandled));
      for (Element exportedElement in exportedLibraryElement.exports) {
        if (!filter.exclude(exportedElement)) {
          Link<Export> exports =
              pendingExportMap.putIfAbsent(exportedElement,
                                           () => const Link<Export>());
          pendingExportMap[exportedElement] = exports.prepend(export);
        }
      }
    }
  
    /**
     * Registers the compute export scope with the node library.
     */
    void registerExports() {
      library.setExports(exportScope.values.toList());
    }
  
    /**
     * Registers the imports of the node library.
     */
    void registerImports(Compiler compiler) {
      for (ImportLink link in imports) {
        link.importLibrary(compiler, library);
      }
    }
  
    /**
     * Copies and clears pending export set for this node.
     */
    Map<Element, Link<Export>> pullPendingExports() {
      Map<Element, Link<Export>> pendingExports =
          new Map<Element, Link<Export>>.from(pendingExportMap);
      pendingExportMap.clear();
      return pendingExports;
    }
  
    /**
     * Adds [element] to the export scope for this node. If the [element] name
     * is a duplicate, an error element is inserted into the export scope.
     */
    Element addElementToExportScope(Compiler compiler, Element element,
                                    Link<Export> exports) {
      String name = element.name;
  
      void reportDuplicateExport(Element duplicate,
                                 Link<Export> duplicateExports,
                                 {bool reportError: true}) {
        assert(invariant(library, !duplicateExports.isEmpty,
            message: "No export for $duplicate from ${duplicate.getLibrary()} "
                     "in $library."));
        compiler.withCurrentElement(library, () {
          for (Export export in duplicateExports) {
            if (reportError) {
              compiler.reportError(export,
                  MessageKind.DUPLICATE_EXPORT, {'name': name});
              reportError = false;
            } else {
              compiler.reportInfo(export,
                  MessageKind.DUPLICATE_EXPORT_CONT, {'name': name});
            }
          }
        });
      }
  
      void reportDuplicateExportDecl(Element duplicate,
                                     Link<Export> duplicateExports) {
        assert(invariant(library, !duplicateExports.isEmpty,
            message: "No export for $duplicate from ${duplicate.getLibrary()} "
                     "in $library."));
        compiler.reportInfo(duplicate, MessageKind.DUPLICATE_EXPORT_DECL,
            {'name': name, 'uriString': duplicateExports.head.uri});
      }
  
      Element existingElement = exportScope[name];
      if (existingElement != null && existingElement != element) {
        if (existingElement.isErroneous()) {
          reportDuplicateExport(element, exports);
          reportDuplicateExportDecl(element, exports);
          element = existingElement;
        } else if (existingElement.getLibrary() == library) {
          // Do nothing. [existingElement] hides [element].
        } else if (element.getLibrary() == library) {
          // [element] hides [existingElement].
          exportScope[name] = element;
          exporters[element] = exports;
        } else {
          // Declared elements hide exported elements.
          Link<Export> existingExports = exporters[existingElement];
          reportDuplicateExport(existingElement, existingExports);
          reportDuplicateExport(element, exports, reportError: false);
          reportDuplicateExportDecl(existingElement, existingExports);
          reportDuplicateExportDecl(element, exports);
          element = exportScope[name] = new ErroneousElementX(
              MessageKind.DUPLICATE_EXPORT, {'name': name}, name, library);
        }
      } else {
        exportScope[name] = element;
        exporters[element] = exports;
      }
      return element;
    }
  
    /**
     * Propagates the exported [element] to all library nodes that depend upon
     * this node. If the propagation updated any pending exports, [:true:] is
     * returned.
     */
    bool propagateElement(Element element) {
      bool change = false;
      for (ExportLink link in dependencies) {
        if (link.exportElement(element)) {
          change = true;
        }
      }
      return change;
    }
  
    /**
     * Adds [element] to the pending exports of this node and returns [:true:] if
     * the pending export set was modified. The combinators of [export] are used
     * to filter the element.
     */
    bool addElementToPendingExports(Element element, Export export) {
      bool changed = false;
      if (!identical(exportScope[element.name], element)) {
        Link<Export> exports = pendingExportMap.putIfAbsent(element, () {
          changed = true;
          return const Link<Export>();
        });
        pendingExportMap[element] = exports.prepend(export);
      }
      return changed;
    }
  }
  
  /**
   * Helper class used for computing the possibly cyclic import/export scopes of
   * a set of libraries.
   *
   * This class is used by [ScannerTask.scanLibrary] to collect all newly loaded
   * libraries and to compute their import/export scopes through a fixed-point
   * algorithm.
   */
  class LibraryDependencyHandler {
    final Compiler compiler;
  
    /**
     * Newly loaded libraries and their corresponding node in the library
     * dependency graph. Libraries that have already been fully loaded are not
     * part of the dependency graph of this handler since their export scopes have
     * already been computed.
     */
    Map<LibraryElement,LibraryDependencyNode> nodeMap =
        new Map<LibraryElement,LibraryDependencyNode>();
  
    LibraryDependencyHandler(Compiler this.compiler);
  
    /**
     * Performs a fixed-point computation on the export scopes of all registered
     * libraries and creates the import/export of the libraries based on the
     * fixed-point.
     */
    void computeExports() {
      bool changed = true;
      while (changed) {
        changed = false;
        Map<LibraryDependencyNode, Map<Element, Link<Export>>> tasks =
            new Map<LibraryDependencyNode, Map<Element, Link<Export>>>();
  
        // Locally defined elements take precedence over exported
        // elements.  So we must propagate local elements first.  We
        // ensure this by pulling the pending exports before
        // propagating.  This enforces that we handle exports
        // breadth-first, with locally defined elements being level 0.
        nodeMap.forEach((_, LibraryDependencyNode node) {
          Map<Element, Link<Export>> pendingExports = node.pullPendingExports();
          tasks[node] = pendingExports;
        });
        tasks.forEach((LibraryDependencyNode node,
                       Map<Element, Link<Export>> pendingExports) {
          pendingExports.forEach((Element element, Link<Export> exports) {
            element = node.addElementToExportScope(compiler, element, exports);
            if (node.propagateElement(element)) {
              changed = true;
            }
          });
        });
      }
  
      // Setup export scopes. These have to be set before computing the import
      // scopes to avoid accessing uncomputed export scopes during handling of
      // imports.
      nodeMap.forEach((LibraryElement library, LibraryDependencyNode node) {
        node.registerExports();
      });
  
      // Setup import scopes.
      nodeMap.forEach((LibraryElement library, LibraryDependencyNode node) {
        node.registerImports(compiler);
      });
    }
  
    /**
     * Registers that [library] depends on [loadedLibrary] through [tag].
     */
    void registerDependency(LibraryElement library,
                            LibraryDependency tag,
                            LibraryElement loadedLibrary) {
      if (tag != null) {
        library.recordResolvedTag(tag, loadedLibrary);
      }
      if (tag is Export) {
        // [loadedLibrary] is exported by [library].
        LibraryDependencyNode exportingNode = nodeMap[library];
        if (loadedLibrary.exportsHandled) {
          // Export scope already computed on [loadedLibrary].
          var combinatorFilter = new CombinatorFilter.fromTag(tag);
          exportingNode.registerHandledExports(
              loadedLibrary, tag, combinatorFilter);
          return;
        }
        LibraryDependencyNode exportedNode = nodeMap[loadedLibrary];
        assert(invariant(loadedLibrary, exportedNode != null,
            message: "$loadedLibrary has not been registered"));
        assert(invariant(library, exportingNode != null,
            message: "$library has not been registered"));
        exportedNode.registerExportDependency(tag, exportingNode);
      } else if (tag == null || tag is Import) {
        // [loadedLibrary] is imported by [library].
        LibraryDependencyNode importingNode = nodeMap[library];
        assert(invariant(library, importingNode != null,
            message: "$library has not been registered"));
        importingNode.registerImportDependency(tag, loadedLibrary);
      }
    }
  
    /**
     * Registers [library] for the processing of its import/export scope.
     */
    void registerNewLibrary(LibraryElement library) {
      nodeMap[library] = new LibraryDependencyNode(library);
    }
  
    /**
     * Registers all top-level entities of [library] as starting point for the
     * fixed-point computation of the import/export scopes.
     */
    void registerLibraryExports(LibraryElement library) {
      nodeMap[library].registerInitialExports();
    }
  }
  