1 files changed, 587 insertions, 0 deletions
diff --git a/examples/scala-js/tools/shared/src/main/scala/scala/scalajs/tools/optimizer/Analyzer.scala b/examples/scala-js/tools/shared/src/main/scala/scala/scalajs/tools/optimizer/Analyzer.scala
new file mode 100644
index 0000000..9cdd764
--- /dev/null
+++ b/examples/scala-js/tools/shared/src/main/scala/scala/scalajs/tools/optimizer/Analyzer.scala
@@ -0,0 +1,587 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___      __ ____  Scala.js tools             **
+**    / __/ __// _ | / /  / _ | __ / // __/  (c) 2013-2014, LAMP/EPFL   **
+**  __\ \/ /__/ __ |/ /__/ __ |/_// /_\ \    http://scala-js.org/       **
+** /____/\___/_/ |_/____/_/ | |__/ /____/                               **
+**                          |/____/                                     **
+\*                                                                      */
+
+
+package scala.scalajs.tools.optimizer
+
+import scala.annotation.tailrec
+
+import scala.collection.mutable
+
+import scala.scalajs.ir
+import ir.{ClassKind, Definitions, Infos}
+
+import scala.scalajs.tools.sem._
+import scala.scalajs.tools.javascript.LongImpl
+import scala.scalajs.tools.logging._
+
+import ScalaJSOptimizer._
+
+class Analyzer(logger0: Logger, semantics: Semantics,
+    allData: Seq[Infos.ClassInfo], globalWarnEnabled: Boolean,
+    isBeforeOptimizer: Boolean) {
+  /* Set this to true to debug the DCE analyzer.
+   * We don't rely on config to disable 'debug' messages because we want
+   * to use 'debug' for displaying more stack trace info that the user can
+   * see with the 'last' command.
+   */
+  val DebugAnalyzer = false
+
+  object logger extends Logger {
+    var indentation: String = ""
+
+    def indent(): Unit = indentation += "  "
+    def undent(): Unit = indentation = indentation.substring(2)
+
+    def log(level: Level, message: => String) =
+      logger0.log(level, indentation+message)
+    def success(message: => String) =
+      logger0.success(indentation+message)
+    def trace(t: => Throwable) =
+      logger0.trace(t)
+
+    def indented[A](body: => A): A = {
+      indent()
+      try body
+      finally undent()
+    }
+
+    def debugIndent[A](message: => String)(body: => A): A = {
+      if (DebugAnalyzer) {
+        debug(message)
+        indented(body)
+      } else {
+        body
+      }
+    }
+
+    def temporarilyNotIndented[A](body: => A): A = {
+      val savedIndent = indentation
+      indentation = ""
+      try body
+      finally indentation = savedIndent
+    }
+  }
+
+  sealed trait From
+  case class FromMethod(methodInfo: MethodInfo) extends From
+  case object FromCore extends From
+  case object FromExports extends From
+  case object FromManual extends From
+
+  var allAvailable: Boolean = true
+
+  val classInfos: mutable.Map[String, ClassInfo] = {
+    val cs = for (classData <- allData)
+      yield (classData.encodedName, new ClassInfo(classData))
+    mutable.Map.empty[String, ClassInfo] ++ cs
+  }
+
+  def lookupClass(encodedName: String): ClassInfo = {
+    classInfos.get(encodedName) match {
+      case Some(info) => info
+      case None =>
+        val c = new ClassInfo(createMissingClassInfo(encodedName))
+        classInfos += encodedName -> c
+        c.nonExistent = true
+        c.linkClasses()
+        c
+    }
+  }
+
+  def lookupModule(encodedName: String): ClassInfo = {
+    lookupClass(encodedName+"$")
+  }
+
+  linkClasses()
+
+  def linkClasses(): Unit = {
+    if (!classInfos.contains(ir.Definitions.ObjectClass))
+      sys.error("Fatal error: could not find java.lang.Object on the classpath")
+    for (classInfo <- classInfos.values.toList)
+      classInfo.linkClasses()
+  }
+
+  def computeReachability(manuallyReachable: Seq[ManualReachability],
+      noWarnMissing: Seq[NoWarnMissing]): Unit = {
+    // Stuff reachable from core symbols always should warn
+    reachCoreSymbols()
+
+    // Disable warnings as requested
+    noWarnMissing.foreach(disableWarning _)
+
+    // Reach all user stuff
+    manuallyReachable.foreach(reachManually _)
+    for (classInfo <- classInfos.values)
+      classInfo.reachExports()
+  }
+
+  /** Reach symbols used directly by scalajsenv.js. */
+  def reachCoreSymbols(): Unit = {
+    import semantics._
+    import CheckedBehavior._
+
+    implicit val from = FromCore
+
+    def instantiateClassWith(className: String, constructor: String): ClassInfo = {
+      val info = lookupClass(className)
+      info.instantiated()
+      info.callMethod(constructor)
+      info
+    }
+
+    val ObjectClass = instantiateClassWith("O", "init___")
+    ObjectClass.callMethod("toString__T")
+    ObjectClass.callMethod("equals__O__Z")
+
+    instantiateClassWith("jl_NullPointerException", "init___")
+
+    if (asInstanceOfs != Unchecked)
+      instantiateClassWith("jl_ClassCastException", "init___T")
+
+    if (asInstanceOfs == Fatal)
+      instantiateClassWith("sjsr_UndefinedBehaviorError", "init___jl_Throwable")
+
+    instantiateClassWith("jl_Class", "init___jl_ScalaJSClassData")
+
+    val RTStringModuleClass = lookupClass("sjsr_RuntimeString$")
+    RTStringModuleClass.accessModule()
+    RTStringModuleClass.callMethod("hashCode__T__I")
+
+    val RTLongClass = lookupClass(LongImpl.RuntimeLongClass)
+    RTLongClass.instantiated()
+    for (method <- LongImpl.AllConstructors ++ LongImpl.AllMethods)
+      RTLongClass.callMethod(method)
+
+    if (isBeforeOptimizer) {
+      for (method <- LongImpl.AllIntrinsicMethods)
+        RTLongClass.callMethod(method)
+    }
+
+    val RTLongModuleClass = lookupClass(LongImpl.RuntimeLongModuleClass)
+    RTLongModuleClass.accessModule()
+    for (method <- LongImpl.AllModuleMethods)
+      RTLongModuleClass.callMethod(method)
+
+    if (isBeforeOptimizer) {
+      for (hijacked <- Definitions.HijackedClasses)
+        lookupClass(hijacked).instantiated()
+    } else {
+      for (hijacked <- Definitions.HijackedClasses)
+        lookupClass(hijacked).accessData()
+    }
+
+    if (semantics.strictFloats) {
+      val RuntimePackage = lookupClass("sjsr_package$")
+      RuntimePackage.accessModule()
+      RuntimePackage.callMethod("froundPolyfill__D__D")
+    }
+
+    val BitsModuleClass = lookupClass("sjsr_Bits$")
+    BitsModuleClass.accessModule()
+    BitsModuleClass.callMethod("numberHashCode__D__I")
+  }
+
+  def reachManually(info: ManualReachability) = {
+    implicit val from = FromManual
+
+    // Don't lookupClass here, since we don't want to create any
+    // symbols. If a symbol doesn't exist, we fail.
+    info match {
+      case ReachObject(name) => classInfos(name + "$").accessModule()
+      case Instantiate(name) => classInfos(name).instantiated()
+      case ReachMethod(className, methodName, static) =>
+        classInfos(className).callMethod(methodName, static)
+    }
+  }
+
+  def disableWarning(noWarn: NoWarnMissing) = noWarn match {
+    case NoWarnClass(className) =>
+      lookupClass(className).warnEnabled = false
+    case NoWarnMethod(className, methodName) =>
+      lookupClass(className).lookupMethod(methodName).warnEnabled = false
+  }
+
+  class ClassInfo(data: Infos.ClassInfo) {
+    val encodedName = data.encodedName
+    val ancestorCount = data.ancestorCount
+    val isStaticModule = data.kind == ClassKind.ModuleClass
+    val isInterface = data.kind == ClassKind.Interface
+    val isImplClass = data.kind == ClassKind.TraitImpl
+    val isRawJSType = data.kind == ClassKind.RawJSType
+    val isHijackedClass = data.kind == ClassKind.HijackedClass
+    val isClass = !isInterface && !isImplClass && !isRawJSType
+    val isExported = data.isExported
+
+    val hasData = !isImplClass
+    val hasMoreThanData = isClass && !isHijackedClass
+
+    var superClass: ClassInfo = _
+    val ancestors = mutable.ListBuffer.empty[ClassInfo]
+    val descendants = mutable.ListBuffer.empty[ClassInfo]
+
+    var nonExistent: Boolean = false
+    var warnEnabled: Boolean = true
+
+    def linkClasses(): Unit = {
+      if (data.superClass != "")
+        superClass = lookupClass(data.superClass)
+      ancestors ++= data.ancestors.map(lookupClass)
+      for (ancestor <- ancestors)
+        ancestor.descendants += this
+    }
+
+    lazy val descendentClasses = descendants.filter(_.isClass)
+
+    def optimizerHints: Infos.OptimizerHints = data.optimizerHints
+
+    var isInstantiated: Boolean = false
+    var isAnySubclassInstantiated: Boolean = false
+    var isModuleAccessed: Boolean = false
+    var isDataAccessed: Boolean = false
+
+    var instantiatedFrom: Option[From] = None
+
+    val delayedCalls = mutable.Map.empty[String, From]
+
+    def isNeededAtAll =
+      isDataAccessed ||
+      isAnySubclassInstantiated ||
+      (isImplClass && methodInfos.values.exists(_.isReachable))
+
+    lazy val methodInfos: mutable.Map[String, MethodInfo] = {
+      val ms = for (methodData <- data.methods)
+        yield (methodData.encodedName, new MethodInfo(this, methodData))
+      mutable.Map.empty[String, MethodInfo] ++ ms
+    }
+
+    def lookupMethod(methodName: String): MethodInfo = {
+      tryLookupMethod(methodName).getOrElse {
+        val syntheticData = createMissingMethodInfo(methodName)
+        val m = new MethodInfo(this, syntheticData)
+        m.nonExistent = true
+        methodInfos += methodName -> m
+        m
+      }
+    }
+
+    def tryLookupMethod(methodName: String): Option[MethodInfo] = {
+      assert(isClass || isImplClass,
+          s"Cannot call lookupMethod($methodName) on non-class $this")
+      @tailrec
+      def loop(ancestorInfo: ClassInfo): Option[MethodInfo] = {
+        if (ancestorInfo ne null) {
+          ancestorInfo.methodInfos.get(methodName) match {
+            case Some(m) if !m.isAbstract => Some(m)
+            case _ => loop(ancestorInfo.superClass)
+          }
+        } else {
+          None
+        }
+      }
+      loop(this)
+    }
+
+    override def toString(): String = encodedName
+
+    /** Start reachability algorithm with the exports for that class. */
+    def reachExports(): Unit = {
+      implicit val from = FromExports
+
+      // Myself
+      if (isExported) {
+        assert(!isImplClass, "An implementation class must not be exported")
+        if (isStaticModule) accessModule()
+        else instantiated()
+      }
+
+      // My methods
+      for (methodInfo <- methodInfos.values) {
+        if (methodInfo.isExported)
+          callMethod(methodInfo.encodedName)
+      }
+    }
+
+    def accessModule()(implicit from: From): Unit = {
+      assert(isStaticModule, s"Cannot call accessModule() on non-module $this")
+      if (!isModuleAccessed) {
+        logger.debugIndent(s"$this.isModuleAccessed = true") {
+          isModuleAccessed = true
+          instantiated()
+          callMethod("init___")
+        }
+      }
+    }
+
+    def instantiated()(implicit from: From): Unit = {
+      if (!isInstantiated && isClass) {
+        logger.debugIndent(s"$this.isInstantiated = true") {
+          isInstantiated = true
+          instantiatedFrom = Some(from)
+          ancestors.foreach(_.subclassInstantiated())
+        }
+
+        for ((methodName, from) <- delayedCalls)
+          delayedCallMethod(methodName)(from)
+      }
+    }
+
+    private def subclassInstantiated()(implicit from: From): Unit = {
+      if (!isAnySubclassInstantiated && isClass) {
+        logger.debugIndent(s"$this.isAnySubclassInstantiated = true") {
+          isAnySubclassInstantiated = true
+          if (instantiatedFrom.isEmpty)
+            instantiatedFrom = Some(from)
+          accessData()
+          methodInfos.get("__init__").foreach(_.reachStatic())
+        }
+      }
+    }
+
+    def accessData()(implicit from: From): Unit = {
+      if (!isDataAccessed && hasData) {
+        checkExistent()
+        if (DebugAnalyzer)
+          logger.debug(s"$this.isDataAccessed = true")
+        isDataAccessed = true
+      }
+    }
+
+    def checkExistent()(implicit from: From): Unit = {
+      if (nonExistent) {
+        if (warnEnabled && globalWarnEnabled) {
+          logger.warn(s"Referring to non-existent class $encodedName")
+          warnCallStack()
+        }
+        nonExistent = false
+        allAvailable = false
+      }
+    }
+
+    def callMethod(methodName: String, static: Boolean = false)(
+        implicit from: From): Unit = {
+      logger.debugIndent(s"calling${if (static) " static" else ""} $this.$methodName") {
+        if (isImplClass) {
+          // methods in impl classes are always implicitly called statically
+          lookupMethod(methodName).reachStatic()
+        } else if (isConstructorName(methodName)) {
+          // constructors are always implicitly called statically
+          lookupMethod(methodName).reachStatic()
+        } else if (static) {
+          assert(!isReflProxyName(methodName),
+              s"Trying to call statically refl proxy $this.$methodName")
+          lookupMethod(methodName).reachStatic()
+        } else {
+          for (descendentClass <- descendentClasses) {
+            if (descendentClass.isInstantiated)
+              descendentClass.delayedCallMethod(methodName)
+            else
+              descendentClass.delayedCalls += ((methodName, from))
+          }
+        }
+      }
+    }
+
+    private def delayedCallMethod(methodName: String)(implicit from: From): Unit = {
+      if (isReflProxyName(methodName)) {
+        tryLookupMethod(methodName).foreach(_.reach(this))
+      } else {
+        lookupMethod(methodName).reach(this)
+      }
+    }
+  }
+
+  class MethodInfo(val owner: ClassInfo, data: Infos.MethodInfo) {
+
+    val encodedName = data.encodedName
+    val isAbstract = data.isAbstract
+    val isExported = data.isExported
+    val isReflProxy = isReflProxyName(encodedName)
+
+    def optimizerHints: Infos.OptimizerHints = data.optimizerHints
+
+    var isReachable: Boolean = false
+
+    var calledFrom: Option[From] = None
+    var instantiatedSubclass: Option[ClassInfo] = None
+
+    var nonExistent: Boolean = false
+    var warnEnabled: Boolean = true
+
+    override def toString(): String = s"$owner.$encodedName"
+
+    def reachStatic()(implicit from: From): Unit = {
+      assert(!isAbstract,
+          s"Trying to reach statically the abstract method $this")
+
+      checkExistent()
+
+      if (!isReachable) {
+        logger.debugIndent(s"$this.isReachable = true") {
+          isReachable = true
+          calledFrom = Some(from)
+          doReach()
+        }
+      }
+    }
+
+    def reach(inClass: ClassInfo)(implicit from: From): Unit = {
+      assert(owner.isClass,
+          s"Trying to reach dynamically the non-class method $this")
+      assert(!isConstructorName(encodedName),
+          s"Trying to reach dynamically the constructor $this")
+
+      checkExistent()
+
+      if (!isReachable) {
+        logger.debugIndent(s"$this.isReachable = true") {
+          isReachable = true
+          calledFrom = Some(from)
+          instantiatedSubclass = Some(inClass)
+          doReach()
+        }
+      }
+    }
+
+    private def checkExistent()(implicit from: From) = {
+      if (nonExistent) {
+        if (warnEnabled && owner.warnEnabled && globalWarnEnabled) {
+          logger.temporarilyNotIndented {
+            logger.warn(s"Referring to non-existent method $this")
+            warnCallStack()
+          }
+        }
+        allAvailable = false
+      }
+    }
+
+    private[this] def doReach(): Unit = {
+      logger.debugIndent(s"$this.doReach()") {
+        implicit val from = FromMethod(this)
+
+        if (owner.isImplClass)
+          owner.checkExistent()
+
+        for (moduleName <- data.accessedModules) {
+          lookupModule(moduleName).accessModule()
+        }
+
+        for (className <- data.instantiatedClasses) {
+          lookupClass(className).instantiated()
+        }
+
+        for (className <- data.accessedClassData) {
+          lookupClass(className).accessData()
+        }
+
+        for ((className, methods) <- data.calledMethods) {
+          val classInfo = lookupClass(className)
+          for (methodName <- methods)
+            classInfo.callMethod(methodName)
+        }
+
+        for ((className, methods) <- data.calledMethodsStatic) {
+          val classInfo = lookupClass(className)
+          for (methodName <- methods)
+            classInfo.callMethod(methodName, static = true)
+        }
+      }
+    }
+  }
+
+  def isReflProxyName(encodedName: String): Boolean = {
+    encodedName.endsWith("__") &&
+    (encodedName != "init___") && (encodedName != "__init__")
+  }
+
+  def isConstructorName(encodedName: String): Boolean =
+    encodedName.startsWith("init___") || (encodedName == "__init__")
+
+  private def createMissingClassInfo(encodedName: String): Infos.ClassInfo = {
+    val kind =
+      if (encodedName.endsWith("$")) ClassKind.ModuleClass
+      else if (encodedName.endsWith("$class")) ClassKind.TraitImpl
+      else ClassKind.Class
+    Infos.ClassInfo(
+        name = s"<$encodedName>",
+        encodedName = encodedName,
+        isExported = false,
+        ancestorCount = if (kind.isClass) 1 else 0,
+        kind = kind,
+        superClass = if (kind.isClass) "O" else "",
+        ancestors = List(encodedName, "O"),
+        methods = List(
+            createMissingMethodInfo("__init__"),
+            createMissingMethodInfo("init___"))
+    )
+  }
+
+  private def createMissingMethodInfo(encodedName: String,
+      isAbstract: Boolean = false): Infos.MethodInfo = {
+    Infos.MethodInfo(encodedName = encodedName, isAbstract = isAbstract)
+  }
+
+  def warnCallStack()(implicit from: From): Unit = {
+    val seenInfos = mutable.Set.empty[AnyRef]
+
+    def rec(level: Level, optFrom: Option[From],
+        verb: String = "called"): Unit = {
+      val involvedClasses = new mutable.ListBuffer[ClassInfo]
+
+      def onlyOnce(info: AnyRef): Boolean = {
+        if (seenInfos.add(info)) {
+          true
+        } else {
+          logger.log(level, "  (already seen, not repeating call stack)")
+          false
+        }
+      }
+
+      @tailrec
+      def loopTrace(optFrom: Option[From], verb: String = "called"): Unit = {
+        optFrom match {
+          case None =>
+            logger.log(level, s"$verb from ... er ... nowhere!? (this is a bug in dce)")
+          case Some(from) =>
+            from match {
+              case FromMethod(methodInfo) =>
+                logger.log(level, s"$verb from $methodInfo")
+                if (onlyOnce(methodInfo)) {
+                  methodInfo.instantiatedSubclass.foreach(involvedClasses += _)
+                  loopTrace(methodInfo.calledFrom)
+                }
+              case FromCore =>
+                logger.log(level, s"$verb from scalajs-corejslib.js")
+              case FromExports =>
+                logger.log(level, "exported to JavaScript with @JSExport")
+              case FromManual =>
+                logger.log(level, "manually made reachable")
+            }
+        }
+      }
+
+      logger.indented {
+        loopTrace(optFrom, verb = verb)
+      }
+
+      if (involvedClasses.nonEmpty) {
+        logger.log(level, "involving instantiated classes:")
+        logger.indented {
+          for (classInfo <- involvedClasses.result().distinct) {
+            logger.log(level, s"$classInfo")
+            if (onlyOnce(classInfo))
+              rec(Level.Debug, classInfo.instantiatedFrom, verb = "instantiated")
+            // recurse with Debug log level not to overwhelm the user
+          }
+        }
+      }
+    }
+
+    rec(Level.Warn, Some(from))
+  }
+}