"Fossies" - the Fresh Open Source Software Archive

Member "scala-js-1.3.1/linker/shared/src/main/scala/org/scalajs/linker/analyzer/Analyzer.scala" (14 Nov 2020, 49486 Bytes) of package /linux/www/scala-js-1.3.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Scala source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "Analyzer.scala": 1.3.0_vs_1.3.1.

    1 /*
    2  * Scala.js (https://www.scala-js.org/)
    3  *
    4  * Copyright EPFL.
    5  *
    6  * Licensed under Apache License 2.0
    7  * (https://www.apache.org/licenses/LICENSE-2.0).
    8  *
    9  * See the NOTICE file distributed with this work for
   10  * additional information regarding copyright ownership.
   11  */
   12 
   13 package org.scalajs.linker.analyzer
   14 
   15 import scala.annotation.tailrec
   16 
   17 import scala.collection.mutable
   18 import scala.concurrent._
   19 
   20 import scala.util.{Success, Failure}
   21 
   22 import java.util.concurrent.ConcurrentLinkedQueue
   23 import java.util.concurrent.atomic.{AtomicBoolean, AtomicInteger}
   24 
   25 import org.scalajs.ir
   26 import org.scalajs.ir.ClassKind
   27 import org.scalajs.ir.Names._
   28 import org.scalajs.ir.Trees.{MemberNamespace, JSNativeLoadSpec}
   29 import org.scalajs.ir.Types.ClassRef
   30 
   31 import org.scalajs.linker._
   32 import org.scalajs.linker.interface.{ModuleKind, ModuleInitializer}
   33 import org.scalajs.linker.interface.unstable.ModuleInitializerImpl
   34 import org.scalajs.linker.standard._
   35 import org.scalajs.linker.standard.ModuleSet.ModuleID
   36 
   37 import Analysis._
   38 import Infos.{NamespacedMethodName, ReachabilityInfo}
   39 
   40 private final class Analyzer(config: CommonPhaseConfig,
   41     moduleInitializers: Seq[ModuleInitializer],
   42     symbolRequirements: SymbolRequirement,
   43     allowAddingSyntheticMethods: Boolean,
   44     checkAbstractReachability: Boolean,
   45     inputProvider: Analyzer.InputProvider,
   46     ec: ExecutionContext)
   47     extends Analysis {
   48 
   49   import Analyzer._
   50 
   51   private val isNoModule = config.coreSpec.moduleKind == ModuleKind.NoModule
   52 
   53   private var objectClassInfo: ClassInfo = _
   54   private[this] val _classInfos = mutable.Map.empty[ClassName, ClassLoadingState]
   55 
   56   private[this] val _errors = mutable.Buffer.empty[Error]
   57 
   58   private val workQueue = new WorkQueue(ec)
   59 
   60   private val fromAnalyzer = FromCore("analyzer")
   61 
   62   private[this] var _loadedClassInfos: scala.collection.Map[ClassName, ClassInfo] = _
   63 
   64   def classInfos: scala.collection.Map[ClassName, Analysis.ClassInfo] =
   65     _loadedClassInfos
   66 
   67   var topLevelExportInfos: Map[(ModuleID, String), Analysis.TopLevelExportInfo] = _
   68 
   69   def errors: scala.collection.Seq[Error] = _errors
   70 
   71   def computeReachability(): Future[Unit] = {
   72     require(_classInfos.isEmpty, "Cannot run the same Analyzer multiple times")
   73 
   74     loadObjectClass(() => loadEverything())
   75 
   76     workQueue.join().map(_ => postLoad())(ec)
   77   }
   78 
   79   private def loadObjectClass(onSuccess: () => Unit): Unit = {
   80     implicit val from = fromAnalyzer
   81 
   82     /* Load the java.lang.Object class, and validate it
   83      * If it is missing or invalid, we're in deep trouble, and cannot continue.
   84      */
   85     inputProvider.loadInfo(ObjectClass)(ec) match {
   86       case None =>
   87         _errors += MissingJavaLangObjectClass(fromAnalyzer)
   88 
   89       case Some(future) =>
   90         workQueue.enqueue(future) { data =>
   91           if (data.kind != ClassKind.Class || data.superClass.isDefined ||
   92             data.interfaces.nonEmpty) {
   93             _errors += InvalidJavaLangObjectClass(fromAnalyzer)
   94           } else {
   95             objectClassInfo = new ClassInfo(data,
   96                 unvalidatedSuperClass = None,
   97                 unvalidatedInterfaces = Nil, nonExistent = false)
   98 
   99             objectClassInfo.link()
  100             onSuccess()
  101           }
  102         }
  103     }
  104   }
  105 
  106   private def loadEverything(): Unit = {
  107     assert(objectClassInfo != null)
  108 
  109     implicit val from = fromAnalyzer
  110 
  111     /* java.lang.Object is always instantiated, because it is the
  112      * representative class for JS objects.
  113      */
  114     objectClassInfo.instantiated()
  115 
  116     /* Hijacked classes are always instantiated, because values of primitive
  117      * types are their instances.
  118      *
  119      * Also, they are part of the core infrastructure. As such, j.l.Object
  120      * depends on them.
  121      */
  122     for (hijacked <- HijackedClasses) {
  123       lookupClass(hijacked) { clazz =>
  124         objectClassInfo.staticDependencies += clazz.className
  125         clazz.instantiated()
  126       }
  127     }
  128 
  129     // External symbol requirements.
  130     reachSymbolRequirement(symbolRequirements)
  131 
  132     // Reach static initializers.
  133     for (className <- inputProvider.classesWithEntryPoints())
  134       lookupClass(className)(_.reachStaticInitializer())
  135 
  136     // Reach module initializers.
  137     reachInitializers(moduleInitializers)
  138 
  139     // Reach top level exports
  140     reachTopLevelExports()
  141   }
  142 
  143   private def postLoad(): Unit = {
  144     val infos = _classInfos.collect { case (k, i: ClassInfo) => (k, i) }
  145 
  146     assert(_errors.nonEmpty || infos.size == _classInfos.size,
  147         "unloaded classes in post load phase")
  148 
  149     _loadedClassInfos = infos
  150 
  151     // Reach additional data, based on reflection methods used
  152     reachDataThroughReflection(infos)
  153   }
  154 
  155   private def reachSymbolRequirement(requirement: SymbolRequirement,
  156       optional: Boolean = false): Unit = {
  157 
  158     /* We use j.l.Object as representation of the core infrastructure.
  159      * As such, everything depends on j.l.Object and j.l.Object depends on all
  160      * symbol requirements.
  161      */
  162 
  163     def withClass(className: ClassName)(onSuccess: ClassInfo => Unit)(
  164         implicit from: From): Unit = {
  165       lookupClass(className, ignoreMissing = optional)(onSuccess)
  166     }
  167 
  168     def withMethod(className: ClassName, methodName: MethodName)(
  169         onSuccess: ClassInfo => Unit)(
  170         implicit from: From): Unit = {
  171       withClass(className) { clazz =>
  172         val doReach = !optional || clazz.tryLookupMethod(methodName).isDefined
  173         if (doReach)
  174           onSuccess(clazz)
  175       }
  176     }
  177 
  178     import SymbolRequirement.Nodes._
  179 
  180     requirement match {
  181       case AccessModule(origin, moduleName) =>
  182         implicit val from = FromCore(origin)
  183         withClass(moduleName) { clazz =>
  184           objectClassInfo.staticDependencies += clazz.className
  185           clazz.accessModule()
  186         }
  187 
  188       case InstantiateClass(origin, className, constructor) =>
  189         implicit val from = FromCore(origin)
  190         withMethod(className, constructor) { clazz =>
  191           objectClassInfo.staticDependencies += clazz.className
  192           clazz.instantiated()
  193           clazz.callMethodStatically(MemberNamespace.Constructor, constructor)
  194         }
  195 
  196       case InstanceTests(origin, className) =>
  197         implicit val from = FromCore(origin)
  198         withClass(className){ clazz =>
  199           objectClassInfo.staticDependencies += clazz.className
  200           clazz.useInstanceTests()
  201         }
  202 
  203       case ClassData(origin, className) =>
  204         implicit val from = FromCore(origin)
  205         withClass(className) { clazz =>
  206           objectClassInfo.staticDependencies += clazz.className
  207           clazz.accessData()
  208         }
  209 
  210       case CallMethod(origin, className, methodName, statically) =>
  211         implicit val from = FromCore(origin)
  212         withMethod(className, methodName) { clazz =>
  213           if (statically) {
  214             objectClassInfo.staticDependencies += clazz.className
  215             clazz.callMethodStatically(MemberNamespace.Public, methodName)
  216           } else {
  217             clazz.callMethod(methodName)
  218           }
  219         }
  220 
  221       case CallStaticMethod(origin, className, methodName) =>
  222         implicit val from = FromCore(origin)
  223         withMethod(className, methodName) { clazz =>
  224           objectClassInfo.staticDependencies += clazz.className
  225           clazz.callMethodStatically(MemberNamespace.PublicStatic, methodName)
  226         }
  227 
  228       case Optional(requirement) =>
  229         reachSymbolRequirement(requirement, optional = true)
  230 
  231       case Multiple(requirements) =>
  232         for (requirement <- requirements)
  233           reachSymbolRequirement(requirement, optional)
  234 
  235       case NoRequirement => // skip
  236     }
  237   }
  238 
  239   private def reachInitializers(
  240       moduleInitializers: Seq[ModuleInitializer]): Unit = {
  241     implicit val from = FromCore("module initializers")
  242 
  243     for (moduleInitializer <- moduleInitializers) {
  244       import ModuleInitializerImpl._
  245 
  246       fromInitializer(moduleInitializer.initializer) match {
  247         case VoidMainMethod(className, mainMethodName) =>
  248           lookupClass(className) { classInfo =>
  249             classInfo.callMethodStatically(MemberNamespace.PublicStatic, mainMethodName)
  250           }
  251 
  252         case MainMethodWithArgs(className, mainMethodName, _) =>
  253           lookupClass(className) { classInfo =>
  254             classInfo.callMethodStatically(MemberNamespace.PublicStatic, mainMethodName)
  255           }
  256 
  257           // For new Array[String]
  258           lookupClass(BoxedStringClass)(_.accessData())
  259       }
  260     }
  261   }
  262 
  263   private def reachTopLevelExports(): Unit = {
  264     workQueue.enqueue(inputProvider.loadTopLevelExportInfos()(ec)) { data =>
  265       // Assemble individual infos.
  266       val infos = data.map(new TopLevelExportInfo(_))
  267 
  268       infos.foreach(_.reach())
  269 
  270       if (isNoModule) {
  271         // Check there is only a single module.
  272         val publicModuleIDs = (
  273             infos.map(_.moduleID) ++
  274             moduleInitializers.map(i => ModuleID(i.moduleID))
  275         ).distinct
  276 
  277         if (publicModuleIDs.size > 1)
  278           _errors += MultiplePublicModulesWithoutModuleSupport(publicModuleIDs)
  279       }
  280 
  281       // Check conflicts, record infos
  282       topLevelExportInfos = for {
  283         (id @ (moduleID, exportName), infos) <- infos.groupBy(i => (i.moduleID, i.exportName))
  284       } yield {
  285         if (infos.size > 1)
  286           _errors += ConflictingTopLevelExport(moduleID, exportName, infos)
  287 
  288         id -> infos.head
  289       }
  290     }
  291   }
  292 
  293   /** Reach additional class data based on reflection methods being used. */
  294   private def reachDataThroughReflection(
  295       classInfos: scala.collection.Map[ClassName, ClassInfo]): Unit = {
  296 
  297     val classClassInfo = classInfos.get(ClassClass)
  298 
  299     /* If Class.getSuperclass() is reachable, we can reach the data of all
  300      * superclasses of classes whose data we can already reach.
  301      */
  302     for {
  303       getSuperclassMethodInfo <-
  304         classClassInfo.flatMap(_.publicMethodInfos.get(getSuperclassMethodName))
  305       if getSuperclassMethodInfo.isReachable
  306     } {
  307       // calledFrom should always be nonEmpty if isReachable, but let's be robust
  308       implicit val from =
  309         getSuperclassMethodInfo.calledFrom.headOption.getOrElse(fromAnalyzer)
  310       for (classInfo <- classInfos.values.filter(_.isDataAccessed).toList) {
  311         @tailrec
  312         def loop(classInfo: ClassInfo): Unit = {
  313           classInfo.accessData()
  314           classInfo.superClass match {
  315             case Some(superClass) =>
  316               classInfo.staticDependencies += superClass.className
  317               loop(superClass)
  318 
  319             case None =>
  320           }
  321         }
  322         loop(classInfo)
  323       }
  324     }
  325   }
  326 
  327   private def lookupClass(className: ClassName,
  328       ignoreMissing: Boolean = false)(
  329       onSuccess: ClassInfo => Unit)(implicit from: From): Unit = {
  330     lookupClassForLinking(className, Set.empty) {
  331       case info: ClassInfo =>
  332         if (!info.nonExistent || !ignoreMissing) {
  333           info.link()
  334           onSuccess(info)
  335         }
  336 
  337       case CycleInfo(cycle, _) =>
  338         _errors += CycleInInheritanceChain(cycle, fromAnalyzer)
  339     }
  340   }
  341 
  342   private def lookupClassForLinking(className: ClassName,
  343       knownDescendants: Set[LoadingClass] = Set.empty)(
  344       onSuccess: LoadingResult => Unit): Unit = {
  345 
  346     _classInfos.get(className) match {
  347       case None =>
  348         val loading = new LoadingClass(className)
  349         loading.requestLink(knownDescendants)(onSuccess)
  350 
  351       case Some(loading: LoadingClass) =>
  352         loading.requestLink(knownDescendants)(onSuccess)
  353 
  354       case Some(info: ClassInfo) =>
  355         onSuccess(info)
  356     }
  357   }
  358 
  359 
  360   private sealed trait LoadingResult
  361   private sealed trait ClassLoadingState
  362 
  363   // sealed instead of final because of spurious unchecked warnings
  364   private sealed case class CycleInfo(cycle: List[ClassName],
  365       root: LoadingClass)
  366       extends LoadingResult
  367 
  368   private final class LoadingClass(className: ClassName)
  369       extends ClassLoadingState {
  370 
  371     private val promise = Promise[LoadingResult]()
  372     private var knownDescendants = Set[LoadingClass](this)
  373 
  374     _classInfos(className) = this
  375 
  376     inputProvider.loadInfo(className)(ec) match {
  377       case Some(future) =>
  378         workQueue.enqueue(future)(link(_, nonExistent = false))
  379 
  380       case None =>
  381         val data = createMissingClassInfo(className)
  382         link(data, nonExistent = true)
  383     }
  384 
  385     def requestLink(knownDescendants: Set[LoadingClass])(onSuccess: LoadingResult => Unit): Unit = {
  386       if (knownDescendants.contains(this)) {
  387         onSuccess(CycleInfo(Nil, this))
  388       } else {
  389         this.knownDescendants ++= knownDescendants
  390         workQueue.enqueue(promise.future)(onSuccess)
  391       }
  392     }
  393 
  394     private def link(data: Infos.ClassInfo, nonExistent: Boolean): Unit = {
  395       lookupAncestors(data.superClass.toList ++ data.interfaces) { classes =>
  396         val (superClass, interfaces) =
  397           if (data.superClass.isEmpty) (None, classes)
  398           else (Some(classes.head), classes.tail)
  399 
  400         val info = new ClassInfo(data, superClass, interfaces, nonExistent)
  401 
  402         implicit val from = FromClass(info)
  403         classes.foreach(_.link())
  404 
  405         promise.success(info)
  406       } { cycleInfo =>
  407         val newInfo = cycleInfo match {
  408           case CycleInfo(_, null) => cycleInfo
  409 
  410           case CycleInfo(c, root) if root == this =>
  411             CycleInfo(className :: c, null)
  412 
  413           case CycleInfo(c, root) =>
  414             CycleInfo(className :: c, root)
  415         }
  416 
  417         promise.success(newInfo)
  418       }
  419     }
  420 
  421     private def lookupAncestors(classNames: List[ClassName])(
  422         loaded: List[ClassInfo] => Unit)(cycle: CycleInfo => Unit): Unit = {
  423       classNames match {
  424         case first :: rest =>
  425           lookupClassForLinking(first, knownDescendants) {
  426             case c: CycleInfo => cycle(c)
  427 
  428             case ifirst: ClassInfo =>
  429               lookupAncestors(rest)(irest => loaded(ifirst :: irest))(cycle)
  430           }
  431         case Nil =>
  432           loaded(Nil)
  433       }
  434     }
  435   }
  436 
  437   private class ClassInfo(
  438       val data: Infos.ClassInfo,
  439       unvalidatedSuperClass: Option[ClassInfo],
  440       unvalidatedInterfaces: List[ClassInfo],
  441       val nonExistent: Boolean)
  442       extends Analysis.ClassInfo with ClassLoadingState with LoadingResult {
  443 
  444     var linkedFrom: List[From] = Nil
  445 
  446     val className = data.className
  447     val kind = data.kind
  448     val isAnyModuleClass =
  449       data.kind.hasModuleAccessor || data.kind == ClassKind.NativeJSModuleClass
  450     val isInterface = data.kind == ClassKind.Interface
  451     val isScalaClass = data.kind.isClass || data.kind == ClassKind.HijackedClass
  452     val isJSClass = data.kind.isJSClass
  453     val isJSType = data.kind.isJSType
  454     val isAnyClass = isScalaClass || isJSClass
  455     val isNativeJSClass =
  456       kind == ClassKind.NativeJSClass || kind == ClassKind.NativeJSModuleClass
  457 
  458     // Note: j.l.Object is special and is validated upfront
  459 
  460     val superClass: Option[ClassInfo] =
  461       if (className == ObjectClass) unvalidatedSuperClass
  462       else validateSuperClass(unvalidatedSuperClass)
  463 
  464     val interfaces: List[ClassInfo] =
  465       if (className == ObjectClass) unvalidatedInterfaces
  466       else validateInterfaces(unvalidatedInterfaces)
  467 
  468     /** Ancestors of this class or interface.
  469      *
  470      *  This always includes this class and `java.lang.Object`.
  471      */
  472     val ancestors: List[ClassInfo] = {
  473       if (className == ObjectClass) {
  474         this :: Nil
  475       } else {
  476         val parents = superClass.getOrElse(objectClassInfo) :: interfaces
  477         this +: parents.flatMap(_.ancestors).distinct
  478       }
  479     }
  480 
  481     _classInfos(className) = this
  482 
  483     def link()(implicit from: From): Unit = {
  484       if (nonExistent)
  485         _errors += MissingClass(this, from)
  486 
  487       linkedFrom ::= from
  488     }
  489 
  490     private[this] def validateSuperClass(superClass: Option[ClassInfo]): Option[ClassInfo] = {
  491       def from = FromClass(this)
  492 
  493       kind match {
  494         case ClassKind.Class | ClassKind.ModuleClass | ClassKind.HijackedClass =>
  495           superClass.fold[Option[ClassInfo]] {
  496             _errors += MissingSuperClass(this, from)
  497             Some(objectClassInfo)
  498           } { superCl =>
  499             if (superCl.kind != ClassKind.Class) {
  500               _errors += InvalidSuperClass(superCl, this, from)
  501               Some(objectClassInfo)
  502             } else {
  503               superClass
  504             }
  505           }
  506 
  507         case ClassKind.Interface =>
  508           superClass.foreach { superCl =>
  509             _errors += InvalidSuperClass(superCl, this, from)
  510           }
  511 
  512           None
  513 
  514         case ClassKind.JSClass | ClassKind.JSModuleClass =>
  515           /* There is no correct fallback in case of error, here. The logical
  516            * thing to do would be to pick `js.Object`, but we cannot be sure
  517            * that `js.Object` and its inheritance chain are valid themselves.
  518            * So we just say superClass = None in invalid cases, and make sure
  519            * this does not blow up the rest of the analysis.
  520            */
  521           superClass.fold[Option[ClassInfo]] {
  522             _errors += MissingSuperClass(this, from)
  523             None
  524           } { superCl =>
  525             superCl.kind match {
  526               case ClassKind.JSClass | ClassKind.NativeJSClass =>
  527                 superClass // ok
  528               case _ =>
  529                 _errors += InvalidSuperClass(superCl, this, from)
  530                 None
  531             }
  532           }
  533 
  534         case ClassKind.NativeJSClass | ClassKind.NativeJSModuleClass =>
  535           superClass.fold[Option[ClassInfo]] {
  536             _errors += MissingSuperClass(this, from)
  537             Some(objectClassInfo)
  538           } { superCl =>
  539             superCl.kind match {
  540               case ClassKind.JSClass | ClassKind.NativeJSClass =>
  541                 superClass // ok
  542               case _ if superCl eq objectClassInfo =>
  543                 superClass // ok
  544               case _ =>
  545                 _errors += InvalidSuperClass(superCl, this, from)
  546                 Some(objectClassInfo)
  547             }
  548           }
  549 
  550         case ClassKind.AbstractJSType =>
  551           superClass.flatMap { superCl =>
  552             superCl.kind match {
  553               case ClassKind.JSClass | ClassKind.NativeJSClass =>
  554                 superClass // ok
  555               case _ if superCl eq objectClassInfo =>
  556                 superClass // ok
  557               case _ =>
  558                 _errors += InvalidSuperClass(superCl, this, from)
  559                 None
  560             }
  561           }
  562       }
  563     }
  564 
  565     private[this] def validateInterfaces(interfaces: List[ClassInfo]): List[ClassInfo] = {
  566       def from = FromClass(this)
  567 
  568       val validSuperIntfKind = kind match {
  569         case ClassKind.Class | ClassKind.ModuleClass |
  570             ClassKind.HijackedClass | ClassKind.Interface =>
  571           ClassKind.Interface
  572         case ClassKind.JSClass | ClassKind.JSModuleClass |
  573             ClassKind.NativeJSClass | ClassKind.NativeJSModuleClass |
  574             ClassKind.AbstractJSType =>
  575           ClassKind.AbstractJSType
  576       }
  577 
  578       interfaces.filter { superIntf =>
  579         if (superIntf.nonExistent) {
  580           // Remove it but do not report an additional error message
  581           false
  582         } else if (superIntf.kind != validSuperIntfKind) {
  583           _errors += InvalidImplementedInterface(superIntf, this, from)
  584           false
  585         } else {
  586           true
  587         }
  588       }
  589     }
  590 
  591     var isInstantiated: Boolean = false
  592     var isAnySubclassInstantiated: Boolean = false
  593     var isModuleAccessed: Boolean = false
  594     var areInstanceTestsUsed: Boolean = false
  595     var isDataAccessed: Boolean = false
  596     var isAnyStaticFieldUsed: Boolean = false
  597     var isAnyPrivateJSFieldUsed: Boolean = false
  598 
  599     val jsNativeMembersUsed: mutable.Set[MethodName] = mutable.Set.empty
  600 
  601     val jsNativeLoadSpec: Option[JSNativeLoadSpec] = data.jsNativeLoadSpec
  602 
  603     /* j.l.Object represents the core infrastructure. As such, everything
  604      * depends on it unconditionally.
  605      */
  606     val staticDependencies: mutable.Set[ClassName] =
  607       if (className == ObjectClass) mutable.Set.empty
  608       else mutable.Set(ObjectClass)
  609 
  610     val externalDependencies: mutable.Set[String] = mutable.Set.empty
  611 
  612     var instantiatedFrom: List[From] = Nil
  613 
  614     /** List of all instantiated (Scala) subclasses of this Scala class/trait.
  615      *  For JS types, this always remains empty.
  616      */
  617     var instantiatedSubclasses: List[ClassInfo] = Nil
  618     var methodsCalledLog: List[(MethodName, From)] = Nil
  619 
  620     private val nsMethodInfos = {
  621       val nsMethodInfos = Array.fill(MemberNamespace.Count) {
  622         mutable.Map.empty[MethodName, MethodInfo]
  623       }
  624       for (methodData <- data.methods) {
  625         // TODO It would be good to report duplicates as errors at this point
  626         val relevantMap = nsMethodInfos(methodData.namespace.ordinal)
  627         relevantMap(methodData.methodName) = new MethodInfo(this, methodData)
  628       }
  629       nsMethodInfos
  630     }
  631 
  632     def methodInfos(
  633         namespace: MemberNamespace): mutable.Map[MethodName, MethodInfo] = {
  634       nsMethodInfos(namespace.ordinal)
  635     }
  636 
  637     val publicMethodInfos: mutable.Map[MethodName, MethodInfo] =
  638       methodInfos(MemberNamespace.Public)
  639 
  640     def lookupAbstractMethod(methodName: MethodName): MethodInfo = {
  641       val candidatesIterator = for {
  642         ancestor <- ancestors.iterator
  643         m <- ancestor.publicMethodInfos.get(methodName)
  644         if !m.isDefaultBridge
  645       } yield {
  646         m
  647       }
  648 
  649       if (candidatesIterator.isEmpty)
  650         createNonExistentMethod(methodName)
  651       else
  652         candidatesIterator.next()
  653     }
  654 
  655     def lookupMethod(methodName: MethodName): MethodInfo = {
  656       tryLookupMethod(methodName).getOrElse {
  657         createNonExistentMethod(methodName)
  658       }
  659     }
  660 
  661     private def createNonExistentMethod(methodName: MethodName): MethodInfo = {
  662       val syntheticData = makeSyntheticMethodInfo(methodName)
  663       val m = new MethodInfo(this, syntheticData)
  664       m.nonExistent = true
  665       publicMethodInfos += methodName -> m
  666       m
  667     }
  668 
  669     def tryLookupMethod(methodName: MethodName): Option[MethodInfo] = {
  670       assert(isScalaClass || isInterface,
  671           s"Cannot call lookupMethod($methodName) on non Scala class $this")
  672 
  673       @tailrec
  674       def tryLookupInherited(ancestorInfo: ClassInfo): Option[MethodInfo] = {
  675         ancestorInfo.publicMethodInfos.get(methodName) match {
  676           case Some(m) if !m.isAbstract =>
  677             Some(m)
  678           case _ =>
  679             ancestorInfo.superClass match {
  680               case Some(superClass) => tryLookupInherited(superClass)
  681               case None             => None
  682             }
  683         }
  684       }
  685       val existing =
  686         if (isScalaClass) tryLookupInherited(this)
  687         else publicMethodInfos.get(methodName).filter(!_.isAbstract)
  688 
  689       if (!allowAddingSyntheticMethods) {
  690         existing
  691       } else if (existing.exists(m => !m.isDefaultBridge || m.owner == this)) {
  692         /* If we found a non-bridge, it must be the right target.
  693          * If we found a bridge directly in this class/interface, it must also
  694          * be the right target.
  695          */
  696         existing
  697       } else {
  698         // Try and find the target of a possible default bridge
  699         findDefaultTarget(methodName).fold {
  700           assert(existing.isEmpty)
  701           existing
  702         } { defaultTarget =>
  703           if (existing.exists(_.defaultBridgeTarget == defaultTarget.owner.className)) {
  704             /* If we found an existing bridge targeting the right method, we
  705              * can reuse it.
  706              * We also get here with None when there is no target whatsoever.
  707              */
  708             existing
  709           } else {
  710             // Otherwise, create a new default bridge
  711             Some(createDefaultBridge(defaultTarget))
  712           }
  713         }
  714       }
  715     }
  716 
  717     /** Resolves an inherited default method.
  718      *
  719      *  This lookup is specified by the JVM resolution rules for default
  720      *  methods. See the `invokespecial` opcode in the JVM Specification
  721      *  version 8, Section 6.5:
  722      *  https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.invokespecial
  723      */
  724     private def findDefaultTarget(methodName: MethodName): Option[MethodInfo] = {
  725       val candidates = for {
  726         intf <- ancestors if intf.isInterface
  727         m <- intf.publicMethodInfos.get(methodName)
  728         if !m.isAbstract && !m.isDefaultBridge
  729       } yield m
  730 
  731       val notShadowed = candidates filterNot { m =>
  732         candidates exists { n =>
  733           (n ne m) && n.owner.ancestors.contains(m.owner)
  734         }
  735       }
  736 
  737       if (notShadowed.size > 1) {
  738         /* Deviation from the spec: if there are several targets, the spec
  739          * chooses one arbitrarily. However, unless the classpath is
  740          * manipulated and/or corrupted, this should not happen. The Java
  741          * *language* and compiler do not let this happen on their own.
  742          * Besides, the current implementation of the JVM throws an
  743          * IncompatibleClassChangeError when trying to resolve such ambiguous
  744          * references.
  745          * So we emit an error too, so that we can more easily discover bugs.
  746          * We use fromAnalyzer because we don't have any From here (we
  747          * shouldn't, since lookup methods are not supposed to produce errors).
  748          */
  749         _errors += ConflictingDefaultMethods(notShadowed, fromAnalyzer)
  750       }
  751 
  752       notShadowed.headOption
  753     }
  754 
  755     private def createDefaultBridge(target: MethodInfo): MethodInfo = {
  756       val methodName = target.methodName
  757       val targetOwner = target.owner
  758 
  759       val syntheticInfo = makeSyntheticMethodInfo(
  760           methodName = methodName,
  761           methodsCalledStatically = List(
  762               targetOwner.className -> NamespacedMethodName(MemberNamespace.Public, methodName)))
  763       val m = new MethodInfo(this, syntheticInfo)
  764       m.syntheticKind = MethodSyntheticKind.DefaultBridge(
  765           targetOwner.className)
  766       publicMethodInfos += methodName -> m
  767       m
  768     }
  769 
  770     def tryLookupReflProxyMethod(proxyName: MethodName)(
  771         onSuccess: MethodInfo => Unit)(implicit from: From): Unit = {
  772       if (!allowAddingSyntheticMethods) {
  773         tryLookupMethod(proxyName).foreach(onSuccess)
  774       } else {
  775         publicMethodInfos.get(proxyName).fold {
  776           workQueue.enqueue(findReflectiveTarget(proxyName)) { maybeTarget =>
  777             maybeTarget.foreach { reflectiveTarget =>
  778               val proxy = createReflProxy(proxyName, reflectiveTarget.methodName)
  779               onSuccess(proxy)
  780             }
  781           }
  782         } (onSuccess)
  783       }
  784     }
  785 
  786     private def findReflectiveTarget(proxyName: MethodName)(
  787         implicit from: From): Future[Option[MethodInfo]] = {
  788       /* The lookup for a target method in this code implements the
  789        * algorithm defining `java.lang.Class.getMethod`. This mimics how
  790        * reflective calls are implemented on the JVM, at link time.
  791        *
  792        * We add a bit of guess-work for default methods, as the documentation
  793        * is very vague about them. Basically, we just take the first match in
  794        * `ancestors`, as it's easy, and we're in a gray area anyway. At least,
  795        * this will work when there is no overload.
  796        *
  797        * Caveat: protected methods are not ignored. This can only make an
  798        * otherwise invalid reflective call suddenly able to call a protected
  799        * method. It never breaks valid reflective calls. This could be fixed
  800        * if the IR retained the information that a method is protected.
  801        */
  802 
  803       val superClasses =
  804         Iterator.iterate(this)(_.superClass.orNull).takeWhile(_ ne null)
  805       val superClassesThenAncestors = superClasses ++ ancestors.iterator
  806 
  807       val candidates = superClassesThenAncestors.map(_.findProxyMatch(proxyName))
  808 
  809       locally {
  810         implicit val iec = ec
  811         Future.sequence(candidates).map(_.collectFirst { case Some(m) => m })
  812       }
  813     }
  814 
  815     private def findProxyMatch(proxyName: MethodName)(
  816         implicit from: From): Future[Option[MethodInfo]] = {
  817       val candidates = publicMethodInfos.valuesIterator.filter { m =>
  818         // TODO In theory we should filter out protected methods
  819         !m.isReflectiveProxy && !m.isDefaultBridge && !m.isAbstract &&
  820         reflProxyMatches(m.methodName, proxyName)
  821       }.toSeq
  822 
  823       /* From the JavaDoc of java.lang.Class.getMethod:
  824        *
  825        *   If more than one [candidate] method is found in C, and one of these
  826        *   methods has a return type that is more specific than any of the
  827        *   others, that method is reflected; otherwise one of the methods is
  828        *   chosen arbitrarily.
  829        */
  830 
  831       val resultTypes = candidates.map(c => c.methodName.resultTypeRef)
  832 
  833       // We must not use Future.traverse since otherwise we might run things on
  834       // the non-main thread.
  835       val specificityChecks = resultTypes.map { x =>
  836         for (y <- resultTypes if x != y)
  837           yield isMoreSpecific(y, x)
  838       }
  839 
  840       // Starting here, we just do data juggling, so it can run on any thread.
  841       locally {
  842         implicit val iec = ec
  843 
  844         val hasMoreSpecific = Future.traverse(specificityChecks)(
  845             checks => Future.sequence(checks).map(_.contains(true)))
  846 
  847         hasMoreSpecific.map { hms =>
  848           val targets = candidates.zip(hms).filterNot(_._2).map(_._1)
  849 
  850           /* This last step (chosen arbitrarily) causes some soundness issues of
  851            * the implementation of reflective calls. This is bug-compatible with
  852            * Scala/JVM.
  853            */
  854           targets.headOption
  855         }
  856       }
  857     }
  858 
  859     private def reflProxyMatches(methodName: MethodName,
  860         proxyName: MethodName): Boolean = {
  861       methodName.simpleName == proxyName.simpleName &&
  862       methodName.paramTypeRefs == proxyName.paramTypeRefs
  863     }
  864 
  865     private def isMoreSpecific(left: ir.Types.TypeRef, right: ir.Types.TypeRef)(
  866         implicit from: From): Future[Boolean] = {
  867       import ir.Types._
  868 
  869       def classIsMoreSpecific(leftCls: ClassName, rightCls: ClassName): Future[Boolean] = {
  870         if (leftCls == rightCls) {
  871           Future.successful(false)
  872         } else {
  873           val promise = Promise[Boolean]()
  874 
  875           lookupClass(leftCls) { leftInfo =>
  876             lookupClass(rightCls) { rightInfo =>
  877               promise.success(leftInfo.ancestors.contains(rightInfo))
  878             }
  879           }
  880 
  881           promise.future
  882         }
  883       }
  884 
  885       (left, right) match {
  886         case (ClassRef(leftCls), ClassRef(rightCls)) =>
  887           classIsMoreSpecific(leftCls, rightCls)
  888         case (ArrayTypeRef(ClassRef(leftBaseCls), leftDepth),
  889             ArrayTypeRef(ClassRef(rightBaseCls), rightDepth)) =>
  890           if (leftDepth != rightDepth) Future.successful(false)
  891           else classIsMoreSpecific(leftBaseCls, rightBaseCls)
  892         case (ArrayTypeRef(_, _), ClassRef(ObjectClass)) =>
  893           Future.successful(true)
  894         case _ =>
  895           Future.successful(false)
  896       }
  897     }
  898 
  899     private def createReflProxy(proxyName: MethodName,
  900         targetName: MethodName): MethodInfo = {
  901       assert(this.isScalaClass,
  902           s"Cannot create reflective proxy in non-Scala class $this")
  903 
  904       val syntheticInfo = makeSyntheticMethodInfo(
  905           methodName = proxyName,
  906           methodsCalled = List(this.className -> targetName))
  907       val m = new MethodInfo(this, syntheticInfo)
  908       m.syntheticKind = MethodSyntheticKind.ReflectiveProxy(targetName)
  909       publicMethodInfos += proxyName -> m
  910       m
  911     }
  912 
  913     def lookupStaticLikeMethod(namespace: MemberNamespace,
  914         methodName: MethodName): MethodInfo = {
  915       tryLookupStaticLikeMethod(namespace, methodName).getOrElse {
  916         val syntheticData = makeSyntheticMethodInfo(methodName, namespace)
  917         val m = new MethodInfo(this, syntheticData)
  918         m.nonExistent = true
  919         methodInfos(namespace)(methodName) = m
  920         m
  921       }
  922     }
  923 
  924     def tryLookupStaticLikeMethod(namespace: MemberNamespace,
  925         methodName: MethodName): Option[MethodInfo] = {
  926       methodInfos(namespace).get(methodName)
  927     }
  928 
  929     override def toString(): String = className.nameString
  930 
  931     def reachStaticInitializer(): Unit = {
  932       implicit val from = FromExports
  933 
  934       tryLookupStaticLikeMethod(MemberNamespace.StaticConstructor,
  935           StaticInitializerName).foreach {
  936         _.reachStatic()(fromAnalyzer)
  937       }
  938     }
  939 
  940     def accessModule()(implicit from: From): Unit = {
  941       if (!isAnyModuleClass) {
  942         _errors += NotAModule(this, from)
  943       } else if (!isModuleAccessed) {
  944         isModuleAccessed = true
  945 
  946         instantiated()
  947         if (isScalaClass)
  948           callMethodStatically(MemberNamespace.Constructor, NoArgConstructorName)
  949       }
  950     }
  951 
  952     def instantiated()(implicit from: From): Unit = {
  953       instantiatedFrom ::= from
  954 
  955       /* TODO? When the second line is false, shouldn't this be a linking error
  956        * instead?
  957        */
  958       if (!isInstantiated &&
  959           (isScalaClass || isJSClass || isNativeJSClass)) {
  960         isInstantiated = true
  961 
  962         /* Reach referenced classes of non-static fields
  963          *
  964          * Note that the classes referenced by static fields are reached
  965          * implicitly by the call-sites that read or write the field: the
  966          * SelectStatic expression has the same type as the field.
  967          *
  968          * We do not need to add this to staticDependencies: The definition
  969          * site will not reference the classes in the final JS code.
  970          */
  971         // TODO: Why is this not in subclassInstantiated()?
  972         for (className <- data.referencedFieldClasses)
  973           lookupClass(className)(_ => ())
  974 
  975         if (isScalaClass) {
  976           accessData()
  977 
  978           val allMethodsCalledLogs = for (ancestor <- ancestors) yield {
  979             ancestor.subclassInstantiated()
  980             ancestor.instantiatedSubclasses ::= this
  981             ancestor.methodsCalledLog
  982           }
  983 
  984           for {
  985             log <- allMethodsCalledLogs
  986             logEntry <- log
  987           } {
  988             val methodName = logEntry._1
  989             implicit val from = logEntry._2
  990             callMethodResolved(methodName)
  991           }
  992         } else {
  993           assert(isJSClass || isNativeJSClass)
  994 
  995           subclassInstantiated()
  996 
  997           if (isJSClass) {
  998             superClass.foreach(_.instantiated())
  999             tryLookupStaticLikeMethod(MemberNamespace.StaticConstructor,
 1000                 ClassInitializerName).foreach {
 1001               staticInit => staticInit.reachStatic()
 1002             }
 1003           } else {
 1004             data.jsNativeLoadSpec match {
 1005               case None =>
 1006                 _errors += MissingJSNativeLoadSpec(this, from)
 1007               case Some(jsNativeLoadSpec) =>
 1008                 validateLoadSpec(jsNativeLoadSpec, jsNativeMember = None)
 1009             }
 1010           }
 1011 
 1012           for (reachabilityInfo <- data.exportedMembers)
 1013             followReachabilityInfo(reachabilityInfo, staticDependencies,
 1014                 externalDependencies)(FromExports)
 1015         }
 1016       }
 1017     }
 1018 
 1019     private def subclassInstantiated()(implicit from: From): Unit = {
 1020       instantiatedFrom ::= from
 1021       if (!isAnySubclassInstantiated && (isScalaClass || isJSType)) {
 1022         isAnySubclassInstantiated = true
 1023 
 1024         if (!isNativeJSClass) {
 1025           for (clazz <- superClass) {
 1026             clazz.jsNativeLoadSpec match {
 1027               case None =>
 1028                 staticDependencies += clazz.className
 1029               case Some(loadSpec) =>
 1030                 addLoadSpec(externalDependencies, loadSpec)
 1031             }
 1032           }
 1033         }
 1034 
 1035         // Reach exported members
 1036         if (!isJSClass) {
 1037           for (reachabilityInfo <- data.exportedMembers)
 1038             followReachabilityInfo(reachabilityInfo, staticDependencies,
 1039                 externalDependencies)(FromExports)
 1040         }
 1041       }
 1042     }
 1043 
 1044     def useInstanceTests()(implicit from: From): Unit = {
 1045       if (!areInstanceTestsUsed)
 1046         areInstanceTestsUsed = true
 1047     }
 1048 
 1049     def accessData()(implicit from: From): Unit = {
 1050       if (!isDataAccessed)
 1051         isDataAccessed = true
 1052     }
 1053 
 1054     def callMethod(methodName: MethodName)(implicit from: From): Unit = {
 1055       /* First add the call to the log, then fetch the instantiated subclasses,
 1056        * then perform the resolved call. This order is important because,
 1057        * during the resolved calls, new instantiated subclasses could be
 1058        * detected, and those need to see the updated log, since the loop in
 1059        * this method won't see them.
 1060        */
 1061       methodsCalledLog ::= ((methodName, from))
 1062       val subclasses = instantiatedSubclasses
 1063       for (subclass <- subclasses)
 1064         subclass.callMethodResolved(methodName)
 1065 
 1066       if (checkAbstractReachability) {
 1067         /* Also lookup the method as abstract from this class, to make sure it
 1068          * is *declared* on this type. We do this after the concrete lookup to
 1069          * avoid work, since a concretely reachable method is already marked as
 1070          * abstractly reachable.
 1071          */
 1072         if (!methodName.isReflectiveProxy)
 1073           lookupAbstractMethod(methodName).reachAbstract()
 1074       }
 1075     }
 1076 
 1077     private def callMethodResolved(methodName: MethodName)(
 1078         implicit from: From): Unit = {
 1079       if (methodName.isReflectiveProxy) {
 1080         tryLookupReflProxyMethod(methodName)(_.reach(this))
 1081       } else {
 1082         lookupMethod(methodName).reach(this)
 1083       }
 1084     }
 1085 
 1086     def callMethodStatically(namespacedMethodName: NamespacedMethodName)(
 1087         implicit from: From): Unit = {
 1088       callMethodStatically(namespacedMethodName.namespace,
 1089           namespacedMethodName.methodName)
 1090     }
 1091 
 1092     def callMethodStatically(namespace: MemberNamespace,
 1093         methodName: MethodName)(
 1094         implicit from: From): Unit = {
 1095       assert(!methodName.isReflectiveProxy,
 1096           s"Trying to call statically refl proxy $this.$methodName")
 1097       if (namespace != MemberNamespace.Public)
 1098         lookupStaticLikeMethod(namespace, methodName).reachStatic()
 1099       else
 1100         lookupMethod(methodName).reachStatic()
 1101     }
 1102 
 1103     def useJSNativeMember(name: MethodName)(
 1104         implicit from: From): Option[JSNativeLoadSpec] = {
 1105       val maybeJSNativeLoadSpec = data.jsNativeMembers.get(name)
 1106       if (jsNativeMembersUsed.add(name)) {
 1107         maybeJSNativeLoadSpec match {
 1108           case None =>
 1109             _errors += MissingJSNativeMember(this, name, from)
 1110           case Some(jsNativeLoadSpec) =>
 1111             validateLoadSpec(jsNativeLoadSpec, Some(name))
 1112         }
 1113       }
 1114       maybeJSNativeLoadSpec
 1115     }
 1116 
 1117     private def validateLoadSpec(jsNativeLoadSpec: JSNativeLoadSpec,
 1118         jsNativeMember: Option[MethodName])(implicit from: From): Unit = {
 1119       if (isNoModule) {
 1120         jsNativeLoadSpec match {
 1121           case JSNativeLoadSpec.Import(module, _) =>
 1122             _errors += ImportWithoutModuleSupport(module, this, jsNativeMember, from)
 1123           case _ =>
 1124         }
 1125       }
 1126     }
 1127   }
 1128 
 1129   private class MethodInfo(val owner: ClassInfo,
 1130       data: Infos.MethodInfo) extends Analysis.MethodInfo {
 1131 
 1132     val methodName = data.methodName
 1133     val namespace = data.namespace
 1134     val isAbstract = data.isAbstract
 1135 
 1136     var isAbstractReachable: Boolean = false
 1137     var isReachable: Boolean = false
 1138 
 1139     var calledFrom: List[From] = Nil
 1140     var instantiatedSubclasses: List[ClassInfo] = Nil
 1141 
 1142     var nonExistent: Boolean = false
 1143 
 1144     var syntheticKind: MethodSyntheticKind = MethodSyntheticKind.None
 1145 
 1146     def isReflectiveProxy: Boolean =
 1147       methodName.isReflectiveProxy
 1148 
 1149     def isDefaultBridge: Boolean =
 1150       syntheticKind.isInstanceOf[MethodSyntheticKind.DefaultBridge]
 1151 
 1152     /** Throws MatchError if `!isDefaultBridge`. */
 1153     def defaultBridgeTarget: ClassName = (syntheticKind: @unchecked) match {
 1154       case MethodSyntheticKind.DefaultBridge(target) => target
 1155     }
 1156 
 1157     override def toString(): String =
 1158       s"$owner.${methodName.simpleName.nameString}"
 1159 
 1160     def reachStatic()(implicit from: From): Unit = {
 1161       assert(!isAbstract,
 1162           s"Trying to reach statically the abstract method $this")
 1163 
 1164       checkExistent()
 1165 
 1166       calledFrom ::= from
 1167       if (!isReachable) {
 1168         isAbstractReachable = true
 1169         isReachable = true
 1170         doReach()
 1171       }
 1172     }
 1173 
 1174     def reachAbstract()(implicit from: From): Unit = {
 1175       assert(namespace == MemberNamespace.Public)
 1176 
 1177       if (!isAbstractReachable) {
 1178         checkExistent()
 1179         calledFrom ::= from
 1180         isAbstractReachable = true
 1181       }
 1182     }
 1183 
 1184     def reach(inClass: ClassInfo)(implicit from: From): Unit = {
 1185       assert(!namespace.isStatic,
 1186           s"Trying to dynamically reach the static method $this")
 1187       assert(!isAbstract,
 1188           s"Trying to dynamically reach the abstract method $this")
 1189       assert(owner.isAnyClass,
 1190           s"Trying to dynamically reach the non-class method $this")
 1191       assert(!namespace.isConstructor,
 1192           s"Trying to dynamically reach the constructor $this")
 1193 
 1194       checkExistent()
 1195 
 1196       calledFrom ::= from
 1197       instantiatedSubclasses ::= inClass
 1198 
 1199       if (!isReachable) {
 1200         isAbstractReachable = true
 1201         isReachable = true
 1202         doReach()
 1203       }
 1204     }
 1205 
 1206     private def checkExistent()(implicit from: From) = {
 1207       if (nonExistent)
 1208         _errors += MissingMethod(this, from)
 1209     }
 1210 
 1211     private[this] def doReach(): Unit = {
 1212       followReachabilityInfo(data.reachabilityInfo, owner.staticDependencies,
 1213           owner.externalDependencies)(FromMethod(this))
 1214     }
 1215   }
 1216 
 1217   private class TopLevelExportInfo(data: Infos.TopLevelExportInfo) extends Analysis.TopLevelExportInfo {
 1218     val owningClass: ClassName = data.owningClass
 1219     val moduleID: ModuleID = data.moduleID
 1220     val exportName: String = data.exportName
 1221 
 1222     if (isNoModule && !ir.Trees.JSGlobalRef.isValidJSGlobalRefName(exportName)) {
 1223       _errors += InvalidTopLevelExportInScript(this)
 1224     }
 1225 
 1226     val staticDependencies: mutable.Set[ClassName] = mutable.Set.empty
 1227     val externalDependencies: mutable.Set[String] = mutable.Set.empty
 1228 
 1229     def reach(): Unit = {
 1230       followReachabilityInfo(data.reachability, staticDependencies,
 1231           externalDependencies)(FromExports)
 1232     }
 1233   }
 1234 
 1235   private def followReachabilityInfo(data: ReachabilityInfo,
 1236       staticDependencies: mutable.Set[ClassName],
 1237       externalDependencies: mutable.Set[String])(
 1238       implicit from: From): Unit = {
 1239 
 1240     def addInstanceDependency(info: ClassInfo) = {
 1241       info.jsNativeLoadSpec.foreach(addLoadSpec(externalDependencies, _))
 1242       if (info.kind.isAnyNonNativeClass)
 1243         staticDependencies += info.className
 1244     }
 1245 
 1246     for (moduleName <- data.accessedModules) {
 1247       lookupClass(moduleName) { module =>
 1248         module.accessModule()
 1249         addInstanceDependency(module)
 1250       }
 1251     }
 1252 
 1253     for (className <- data.instantiatedClasses) {
 1254       lookupClass(className) { clazz =>
 1255         clazz.instantiated()
 1256         addInstanceDependency(clazz)
 1257       }
 1258     }
 1259 
 1260     for (className <- data.usedInstanceTests) {
 1261       staticDependencies += className
 1262       lookupClass(className)(_.useInstanceTests())
 1263     }
 1264 
 1265     for (className <- data.accessedClassData) {
 1266       staticDependencies += className
 1267       lookupClass(className)(_.accessData())
 1268     }
 1269 
 1270     for (className <- data.referencedClasses) {
 1271       /* No need to add to staticDependencies: The classes will not be
 1272        * referenced in the final JS code.
 1273        */
 1274       lookupClass(className)(_ => ())
 1275     }
 1276 
 1277     /* `for` loops on maps are written with `while` loops to help the JIT
 1278      * compiler to inline and stack allocate tuples created by the iterators
 1279      */
 1280 
 1281     val privateJSFieldsUsedIterator = data.privateJSFieldsUsed.iterator
 1282     while (privateJSFieldsUsedIterator.hasNext) {
 1283       val (className, fields) = privateJSFieldsUsedIterator.next()
 1284       if (fields.nonEmpty) {
 1285         staticDependencies += className
 1286         lookupClass(className)(_.isAnyPrivateJSFieldUsed = true)
 1287       }
 1288     }
 1289 
 1290     val staticFieldsReadIterator = data.staticFieldsRead.iterator
 1291     while (staticFieldsReadIterator.hasNext) {
 1292       val (className, fields) = staticFieldsReadIterator.next()
 1293       if (fields.nonEmpty) {
 1294         staticDependencies += className
 1295         lookupClass(className)(_.isAnyStaticFieldUsed = true)
 1296       }
 1297     }
 1298 
 1299     val staticFieldsWrittenIterator = data.staticFieldsWritten.iterator
 1300     while (staticFieldsWrittenIterator.hasNext) {
 1301       val (className, fields) = staticFieldsWrittenIterator.next()
 1302       if (fields.nonEmpty) {
 1303         staticDependencies += className
 1304         lookupClass(className)(_.isAnyStaticFieldUsed = true)
 1305       }
 1306     }
 1307 
 1308     val methodsCalledIterator = data.methodsCalled.iterator
 1309     while (methodsCalledIterator.hasNext) {
 1310       val (className, methods) = methodsCalledIterator.next()
 1311       // Do not add to staticDependencies: We call these on the object.
 1312       lookupClass(className) { classInfo =>
 1313         for (methodName <- methods)
 1314           classInfo.callMethod(methodName)
 1315       }
 1316     }
 1317 
 1318     val methodsCalledStaticallyIterator = data.methodsCalledStatically.iterator
 1319     while (methodsCalledStaticallyIterator.hasNext) {
 1320       val (className, methods) = methodsCalledStaticallyIterator.next()
 1321       staticDependencies += className
 1322       lookupClass(className) { classInfo =>
 1323         for (methodName <- methods)
 1324           classInfo.callMethodStatically(methodName)
 1325       }
 1326     }
 1327 
 1328     val jsNativeMembersUsedIterator = data.jsNativeMembersUsed.iterator
 1329     while (jsNativeMembersUsedIterator.hasNext) {
 1330       val (className, members) = jsNativeMembersUsedIterator.next()
 1331       lookupClass(className) { classInfo =>
 1332         for (member <- members)
 1333           classInfo.useJSNativeMember(member)
 1334             .foreach(addLoadSpec(externalDependencies, _))
 1335       }
 1336     }
 1337   }
 1338 
 1339   @tailrec
 1340   private def addLoadSpec(externalDependencies: mutable.Set[String],
 1341       jsNativeLoadSpec: JSNativeLoadSpec): Unit = {
 1342     jsNativeLoadSpec match {
 1343       case _: JSNativeLoadSpec.Global =>
 1344 
 1345       case JSNativeLoadSpec.Import(module, _) =>
 1346         externalDependencies += module
 1347 
 1348       case JSNativeLoadSpec.ImportWithGlobalFallback(importSpec, _) =>
 1349         if (!isNoModule)
 1350           addLoadSpec(externalDependencies, importSpec)
 1351     }
 1352   }
 1353 
 1354   private def createMissingClassInfo(className: ClassName): Infos.ClassInfo = {
 1355     new Infos.ClassInfoBuilder(className, ClassKind.Class,
 1356         superClass = Some(ObjectClass), interfaces = Nil, jsNativeLoadSpec = None)
 1357       .addMethod(makeSyntheticMethodInfo(NoArgConstructorName))
 1358       .result()
 1359   }
 1360 
 1361   private def makeSyntheticMethodInfo(
 1362       methodName: MethodName,
 1363       namespace: MemberNamespace = MemberNamespace.Public,
 1364       methodsCalled: List[(ClassName, MethodName)] = Nil,
 1365       methodsCalledStatically: List[(ClassName, NamespacedMethodName)] = Nil,
 1366       instantiatedClasses: List[ClassName] = Nil
 1367   ): Infos.MethodInfo = {
 1368     val reachabilityInfoBuilder = new Infos.ReachabilityInfoBuilder()
 1369     for ((className, methodName) <- methodsCalled)
 1370       reachabilityInfoBuilder.addMethodCalled(className, methodName)
 1371     for ((className, methodName) <- methodsCalledStatically)
 1372       reachabilityInfoBuilder.addMethodCalledStatically(className, methodName)
 1373     Infos.MethodInfo(methodName, namespace, isAbstract = false,
 1374         reachabilityInfoBuilder.result())
 1375   }
 1376 
 1377 }
 1378 
 1379 object Analyzer {
 1380   private val getSuperclassMethodName =
 1381     MethodName("getSuperclass", Nil, ClassRef(ClassClass))
 1382 
 1383   def computeReachability(config: CommonPhaseConfig,
 1384       moduleInitializers: Seq[ModuleInitializer],
 1385       symbolRequirements: SymbolRequirement,
 1386       allowAddingSyntheticMethods: Boolean,
 1387       checkAbstractReachability: Boolean,
 1388       inputProvider: InputProvider)(implicit ec: ExecutionContext): Future[Analysis] = {
 1389     val analyzer = new Analyzer(config, moduleInitializers, symbolRequirements,
 1390         allowAddingSyntheticMethods, checkAbstractReachability, inputProvider, ec)
 1391     analyzer.computeReachability().map(_ => analyzer)
 1392   }
 1393 
 1394   trait InputProvider {
 1395     def classesWithEntryPoints(): Iterable[ClassName]
 1396 
 1397     def loadTopLevelExportInfos()(
 1398         implicit ec: ExecutionContext): Future[List[Infos.TopLevelExportInfo]]
 1399 
 1400     def loadInfo(className: ClassName)(
 1401         implicit ec: ExecutionContext): Option[Future[Infos.ClassInfo]]
 1402   }
 1403 
 1404   private class WorkQueue(ec: ExecutionContext) {
 1405     private val queue = new ConcurrentLinkedQueue[() => Unit]()
 1406     private val working = new AtomicBoolean(false)
 1407     private val pending = new AtomicInteger(0)
 1408     private val promise = Promise[Unit]()
 1409 
 1410     def enqueue[T](fut: Future[T])(onSuccess: T => Unit): Unit = {
 1411       val got = pending.incrementAndGet()
 1412       assert(got > 0)
 1413 
 1414       fut.onComplete {
 1415         case Success(r) =>
 1416           queue.add(() => onSuccess(r))
 1417           tryDoWork()
 1418 
 1419         case Failure(t) =>
 1420           promise.tryFailure(t)
 1421       } (ec)
 1422     }
 1423 
 1424     def join(): Future[Unit] = {
 1425       tryDoWork()
 1426       promise.future
 1427     }
 1428 
 1429     @tailrec
 1430     private def tryDoWork(): Unit = {
 1431       if (!working.getAndSet(true)) {
 1432         while (!queue.isEmpty) {
 1433           try {
 1434             val work = queue.poll()
 1435             work()
 1436           } catch {
 1437             case t: Throwable => promise.tryFailure(t)
 1438           }
 1439 
 1440           pending.decrementAndGet()
 1441         }
 1442 
 1443         if (pending.compareAndSet(0, -1)) {
 1444           assert(queue.isEmpty)
 1445           promise.trySuccess(())
 1446         }
 1447 
 1448         working.set(false)
 1449 
 1450         /* Another thread might have inserted work in the meantime but not yet
 1451          * seen that we released the lock. Try and work steal again if this
 1452          * happens.
 1453          */
 1454         if (!queue.isEmpty) tryDoWork()
 1455       }
 1456     }
 1457   }
 1458 }