"Fossies" - the Fresh Open Source Software Archive

Member "scala-js-1.0.0-RC1/linker/shared/src/main/scala/org/scalajs/linker/analyzer/Analyzer.scala" (21 Nov 2019, 42538 Bytes) of package /linux/www/scala-js-1.0.0-RC1.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.

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