Find instructions that would cause an IllegalAccessError when inlined

Some instructions would cause an IllegalAccessError if they are
inlined into a different class.

Based on Miguel's implementation in 6efc0528c6.

7 files changed, 375 insertions, 9 deletions

diff --git a/src/asm/scala/tools/asm/tree/MethodInsnNode.java b/src/asm/scala/tools/asm/tree/MethodInsnNode.java
index 1ec46d473d..30c7854646 100644
--- a/src/asm/scala/tools/asm/tree/MethodInsnNode.java
+++ b/src/asm/scala/tools/asm/tree/MethodInsnNode.java
@@ -45,6 +45,7 @@ public class MethodInsnNode extends AbstractInsnNode {
     /**
      * The internal name of the method's owner class (see
      * {@link scala.tools.asm.Type#getInternalName() getInternalName}).
+     * For methods of arrays, e.g., clone(), the array type descriptor.
      */
     public String owner;
 
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
index ec26ef9b48..ff30631c10 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
@@ -6,10 +6,11 @@
 package scala.tools.nsc
 package backend.jvm
 
+import scala.annotation.switch
 import scala.tools.asm
 import asm.Opcodes
 import scala.tools.asm.tree.{InnerClassNode, ClassNode}
-import opt.ByteCodeRepository
+import opt.{ByteCodeRepository, Inliner}
 import scala.collection.convert.decorateAsScala._
 
 /**
@@ -34,6 +35,8 @@ abstract class BTypes {
    */
   val byteCodeRepository: ByteCodeRepository
 
+  val inliner: Inliner[this.type]
+
   // Allows to define per-run caches here and in the CallGraph component, which don't have a global
   def recordPerRunCache[T <: collection.generic.Clearable](cache: T): T
 
@@ -51,6 +54,31 @@ abstract class BTypes {
   val classBTypeFromInternalName: collection.concurrent.Map[InternalName, ClassBType] = recordPerRunCache(collection.concurrent.TrieMap.empty[InternalName, ClassBType])
 
   /**
+   * Obtain the BType for a type descriptor or internal name. For class descriptors, the ClassBType
+   * is constructed by parsing the corresponding classfile.
+   * 
+   * Some JVM operations use either a full descriptor or only an internal name. Example:
+   *   ANEWARRAY java/lang/String    // a new array of strings (internal name for the String class)
+   *   ANEWARRAY [Ljava/lang/String; // a new array of array of string (full descriptor for the String class)
+   *
+   * This method supports both descriptors and internal names.
+   */
+  def bTypeForDescriptorOrInternalNameFromClassfile(desc: String): BType = (desc(0): @switch) match {
+    case 'V'                     => UNIT
+    case 'Z'                     => BOOL
+    case 'C'                     => CHAR
+    case 'B'                     => BYTE
+    case 'S'                     => SHORT
+    case 'I'                     => INT
+    case 'F'                     => FLOAT
+    case 'J'                     => LONG
+    case 'D'                     => DOUBLE
+    case '['                     => ArrayBType(bTypeForDescriptorOrInternalNameFromClassfile(desc.substring(1)))
+    case 'L' if desc.last == ';' => classBTypeFromParsedClassfile(desc.substring(1, desc.length - 1))
+    case _                       => classBTypeFromParsedClassfile(desc)
+  }
+
+  /**
    * Parse the classfile for `internalName` and construct the [[ClassBType]].
    */
   def classBTypeFromParsedClassfile(internalName: InternalName): ClassBType = {
@@ -725,6 +753,19 @@ abstract class BTypes {
       case Some(sc) => sc :: sc.superClassesTransitive
     }
 
+    /**
+     * The prefix of the internal name until the last '/', or the empty string.
+     */
+    def packageInternalName: String = {
+      val name = internalName
+      name.lastIndexOf('/') match {
+        case -1 => ""
+        case i  => name.substring(0, i)
+      }
+    }
+
+    def isPublic = (info.flags & asm.Opcodes.ACC_PUBLIC) != 0
+
     def isNestedClass = info.nestedInfo.isDefined
 
     def enclosingNestedClassesChain: List[ClassBType] =
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
index 2af665d31c..117b377622 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
@@ -7,9 +7,9 @@ package scala.tools.nsc
 package backend.jvm
 
 import scala.tools.asm
-import opt.ByteCodeRepository
 import scala.tools.asm.tree.ClassNode
 import scala.tools.nsc.backend.jvm.opt.ByteCodeRepository.Source
+import scala.tools.nsc.backend.jvm.opt.{Inliner, ByteCodeRepository}
 import BTypes.InternalName
 
 /**
@@ -38,6 +38,8 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes {
 
   val byteCodeRepository = new ByteCodeRepository(global.classPath, recordPerRunCache(collection.concurrent.TrieMap.empty[InternalName, (ClassNode, Source)]))
 
+  val inliner: Inliner[this.type] = new Inliner(this)
+
   final def initializeCoreBTypes(): Unit = {
     coreBTypes.setBTypes(new CoreBTypes[this.type](this))
   }
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala
index 7b424d2107..9e56f25888 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala
@@ -59,12 +59,16 @@ class ByteCodeRepository(val classPath: ClassFileLookup[AbstractFile], val class
    *
    * @return The [[MethodNode]] of the requested method and the [[InternalName]] of its declaring class.
    */
-  def methodNode(classInternalName: InternalName, name: String, descriptor: String): Option[(MethodNode, InternalName)] = {
-    val c = classNode(classInternalName)
-    c.methods.asScala.find(m => m.name == name && m.desc == descriptor).map((_, classInternalName)) orElse {
-      val parents = Option(c.superName) ++ c.interfaces.asScala
-      // `view` to stop at the first result
-      parents.view.flatMap(methodNode(_, name, descriptor)).headOption
+  def methodNode(ownerInternalNameOrArrayDescriptor: String, name: String, descriptor: String): Option[(MethodNode, InternalName)] = {
+    // In a MethodInsnNode, the `owner` field may be an array descriptor, for exmple when invoking `clone`.
+    if (ownerInternalNameOrArrayDescriptor.charAt(0) == '[') None
+    else {
+      val c = classNode(ownerInternalNameOrArrayDescriptor)
+      c.methods.asScala.find(m => m.name == name && m.desc == descriptor).map((_, ownerInternalNameOrArrayDescriptor)) orElse {
+        val parents = Option(c.superName) ++ c.interfaces.asScala
+        // `view` to stop at the first result
+        parents.view.flatMap(methodNode(_, name, descriptor)).headOption
+      }
     }
   }
 
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
new file mode 100644
index 0000000000..6e5e03f730
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -0,0 +1,118 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2014 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+package scala.tools.nsc
+package backend.jvm
+package opt
+
+import scala.tools.asm
+import asm.Opcodes
+import asm.tree._
+import scala.collection.convert.decorateAsScala._
+import OptimizerReporting._
+
+class Inliner[BT <: BTypes](val btypes: BT) {
+  import btypes._
+  import btypes.byteCodeRepository
+
+  def findIllegalAccess(instructions: InsnList, destinationClass: ClassBType): Option[AbstractInsnNode] = {
+
+    /**
+     * Check if a type is accessible to some class, as defined in JVMS 5.4.4.
+     *  (A1) C is public
+     *  (A2) C and D are members of the same run-time package
+     */
+    def classIsAccessible(accessed: BType, from: ClassBType = destinationClass): Boolean = (accessed: @unchecked) match {
+      // TODO: A2 requires "same run-time package", which seems to be package + classloader (JMVS 5.3.). is the below ok?
+      case c: ClassBType     => c.isPublic || c.packageInternalName == from.packageInternalName
+      case a: ArrayBType     => classIsAccessible(a.elementType, from)
+      case _: PrimitiveBType => true
+    }
+
+    /**
+     * Check if a member reference is accessible from the [[destinationClass]], as defined in the
+     * JVMS 5.4.4. Note that the class name in a field / method reference is not necessarily the
+     * class in which the member is declared:
+     *
+     *   class A { def f = 0 }; class B extends A { f }
+     *
+     * The INVOKEVIRTUAL instruction uses a method reference "B.f ()I". Therefore this method has
+     * two parameters:
+     *
+     * @param memberDeclClass The class in which the member is declared (A)
+     * @param memberRefClass  The class used in the member reference (B)
+     *
+     * JVMS 5.4.4 summary: A field or method R is accessible to a class D (destinationClass) iff
+     *  (B1) R is public
+     *  (B2) R is protected, declared in C (memberDeclClass) and D is a subclass of C.
+     *       If R is not static, R must contain a symbolic reference to a class T (memberRefClass),
+     *       such that T is either a subclass of D, a superclass of D, or D itself.
+     *  (B3) R is either protected or has default access and declared by a class in the same
+     *       run-time package as D.
+     *  (B4) R is private and is declared in D.
+     */
+    def memberIsAccessible(memberFlags: Int, memberDeclClass: ClassBType, memberRefClass: ClassBType): Boolean = {
+      // TODO: B3 requires "same run-time package", which seems to be package + classloader (JMVS 5.3.). is the below ok?
+      def samePackageAsDestination = memberDeclClass.packageInternalName == destinationClass.packageInternalName
+
+      val key = (Opcodes.ACC_PUBLIC | Opcodes.ACC_PROTECTED | Opcodes.ACC_PRIVATE) & memberFlags
+      key match {
+        case Opcodes.ACC_PUBLIC     =>       // B1
+          true
+
+        case Opcodes.ACC_PROTECTED  =>       // B2
+          val condB2 = destinationClass.isSubtypeOf(memberDeclClass) && {
+            val isStatic = (Opcodes.ACC_STATIC & memberFlags) != 0
+            isStatic || memberRefClass.isSubtypeOf(destinationClass) || destinationClass.isSubtypeOf(memberRefClass)
+          }
+          condB2 || samePackageAsDestination // B3 (protected)
+
+        case 0 =>                            // B3 (default access)
+          samePackageAsDestination
+
+        case Opcodes.ACC_PRIVATE    =>       // B4
+          memberDeclClass == destinationClass
+      }
+    }
+
+    def isLegal(instruction: AbstractInsnNode): Boolean = instruction match {
+      case ti: TypeInsnNode  =>
+        // NEW, ANEWARRAY, CHECKCAST or INSTANCEOF. For these instructions, the reference
+        // "must be a symbolic reference to a class, array, or interface type" (JVMS 6), so
+        // it can be an internal name, or a full array descriptor.
+        classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ti.desc))
+
+      case ma: MultiANewArrayInsnNode =>
+        // "a symbolic reference to a class, array, or interface type"
+        classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ma.desc))
+
+      case fi: FieldInsnNode =>
+        val fieldRefClass = classBTypeFromParsedClassfile(fi.owner)
+        val (fieldNode, fieldDeclClass) = byteCodeRepository.fieldNode(fieldRefClass.internalName, fi.name, fi.desc).get
+        memberIsAccessible(fieldNode.access, classBTypeFromParsedClassfile(fieldDeclClass), fieldRefClass)
+
+      case mi: MethodInsnNode =>
+        if (mi.owner.charAt(0) == '[') true // array methods are accessible
+        else {
+          val methodRefClass = classBTypeFromParsedClassfile(mi.owner)
+          val (methodNode, methodDeclClass) = byteCodeRepository.methodNode(methodRefClass.internalName, mi.name, mi.desc).get
+          memberIsAccessible(methodNode.access, classBTypeFromParsedClassfile(methodDeclClass), methodRefClass)
+        }
+
+      case ivd: InvokeDynamicInsnNode =>
+        // TODO @lry check necessary conditions to inline an indy, instead of giving up
+        false
+
+      case ci: LdcInsnNode => ci.cst match {
+        case t: asm.Type => classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(t.getInternalName))
+        case _           => true
+      }
+
+      case _ => true
+    }
+
+    instructions.iterator.asScala.find(!isLegal(_))
+  }
+}
diff --git a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
index c1c5a71b83..e94f33db3d 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
@@ -2,12 +2,14 @@ package scala.tools.nsc.backend.jvm
 
 import org.junit.Assert._
 
+import scala.collection.mutable.ListBuffer
 import scala.reflect.internal.util.BatchSourceFile
 import scala.reflect.io.VirtualDirectory
 import scala.tools.asm.Opcodes
 import scala.tools.asm.tree.{AbstractInsnNode, LabelNode, ClassNode, MethodNode}
 import scala.tools.cmd.CommandLineParser
 import scala.tools.nsc.backend.jvm.opt.LocalOpt
+import scala.tools.nsc.io.AbstractFile
 import scala.tools.nsc.settings.{MutableSettings, ScalaSettings}
 import scala.tools.nsc.{Settings, Global}
 import scala.tools.partest.ASMConverters
@@ -54,7 +56,15 @@ object CodeGenTools {
     val run = new compiler.Run()
     run.compileSources(List(new BatchSourceFile("unitTestSource.scala", code)))
     val outDir = compiler.settings.outputDirs.getSingleOutput.get
-    (for (f <- outDir.iterator if !f.isDirectory) yield (f.name, f.toByteArray)).toList
+    def files(dir: AbstractFile): List[(String, Array[Byte])] = {
+      val res = ListBuffer.empty[(String, Array[Byte])]
+      for (f <- dir.iterator) {
+        if (!f.isDirectory) res += ((f.name, f.toByteArray))
+        else if (f.name != "." && f.name != "..") res ++= files(f)
+      }
+      res.toList
+    }
+    files(outDir)
   }
 
   def compileClasses(compiler: Global)(code: String): List[ClassNode] = {
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerIllegalAccessTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerIllegalAccessTest.scala
new file mode 100644
index 0000000000..406b8da570
--- /dev/null
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerIllegalAccessTest.scala
@@ -0,0 +1,190 @@
+package scala.tools.nsc
+package backend.jvm
+package opt
+
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.Test
+import scala.tools.asm.Opcodes._
+import org.junit.Assert._
+
+import scala.tools.asm.tree._
+import scala.tools.testing.AssertUtil._
+
+import CodeGenTools._
+import scala.tools.partest.ASMConverters
+import ASMConverters._
+import AsmUtils._
+
+import scala.collection.convert.decorateAsScala._
+
+@RunWith(classOf[JUnit4])
+class InlinerIllegalAccessTest {
+  val compiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:none")
+  import compiler.genBCode.bTypes._
+
+  def addToRepo(cls: List[ClassNode]): Unit = for (c <- cls) byteCodeRepository.classes(c.name) = (c, ByteCodeRepository.Classfile)
+  def assertEmpty(ins: Option[AbstractInsnNode]) = for (i <- ins) throw new AssertionError(textify(i))
+
+  @Test
+  def typeAccessible(): Unit = {
+    val code =
+      """package a {
+        |  private class C {            // the Scala compiler makes all classes public
+        |    def f1 = new C                   // NEW a/C
+        |    def f2 = new Array[C](0)         // ANEWARRAY a/C
+        |    def f3 = new Array[Array[C]](0)  // ANEWARRAY [La/C;
+        |  }
+        |  class D
+        |}
+        |package b {
+        |  class E
+        |}
+      """.stripMargin
+
+    val allClasses = compileClasses(compiler)(code)
+    val List(cClass, dClass, eClass) = allClasses
+    assert(cClass.name == "a/C" && dClass.name == "a/D" && eClass.name == "b/E", s"${cClass.name}, ${dClass.name}, ${eClass.name}")
+    addToRepo(allClasses) // they are not on the compiler's classpath, so we add them manually to the code repo
+
+    val methods = cClass.methods.asScala.filter(_.name(0) == 'f').toList
+
+    def check(classNode: ClassNode, test: Option[AbstractInsnNode] => Unit) = {
+      for (m <- methods)
+        test(inliner.findIllegalAccess(m.instructions, classBTypeFromParsedClassfile(classNode.name)))
+    }
+
+    check(cClass, assertEmpty)
+    check(dClass, assertEmpty)
+    check(eClass, assertEmpty) // C is public, so accessible in E
+
+    byteCodeRepository.classes.clear()
+    classBTypeFromInternalName.clear()
+
+    cClass.access &= ~ACC_PUBLIC // ftw
+    addToRepo(allClasses)
+
+    // private classes can be accessed from the same package
+    check(cClass, assertEmpty)
+    check(dClass, assertEmpty) // accessing a private class in the same package is OK
+    check(eClass, {
+      case Some(ti: TypeInsnNode) if Set("a/C", "[La/C;")(ti.desc) => ()
+      // MatchError otherwise
+    })
+  }
+
+  @Test
+  def memberAccessible(): Unit = {
+    val code =
+      """package a {
+        |  class C {
+        |    /*public*/  def a = 0
+        |    /*default*/ def b = 0
+        |    protected   def c = 0
+        |    private     def d = 0
+        |
+        |    /*public static*/    def e = 0
+        |    /*default static*/   def f = 0
+        |    protected /*static*/ def g = 0
+        |    private /*static*/   def h = 0
+        |
+        |    def raC = a
+        |    def rbC = b
+        |    def rcC = c
+        |    def rdC = d
+        |    def reC = e
+        |    def rfC = f
+        |    def rgC = g
+        |    def rhC = h
+        |  }
+        |
+        |  class D extends C {
+        |    def rbD = b // 1: default access b, accessed in D, declared in C. can be inlined into any class in the same package as C.
+        |    def rcD = c // 2: protected c, accessed in D. can be inlined into C, D or E, but not into F (F and D are unrelated).
+        |
+        |    def rfD = f // 1
+        |    def rgD = g // 2
+        |  }
+        |  class E extends D
+        |
+        |  class F extends C
+        |
+        |  class G
+        |}
+        |
+        |package b {
+        |  class H extends a.C
+        |  class I
+        |}
+      """.stripMargin
+
+    val allClasses = compileClasses(compiler)(code)
+    val List(cCl, dCl, eCl, fCl, gCl, hCl, iCl) = allClasses
+    addToRepo(allClasses)
+
+    // set flags that Scala scala doesn't (default access, static) - a hacky way to test all access modes.
+    val names = ('a' to 'h').map(_.toString).toSet
+    val List(a, b, c, d, e, f, g, h) = cCl.methods.asScala.toList.filter(m => names(m.name))
+
+    def checkAccess(a: MethodNode, expected: Int): Unit = {
+      assert((a.access & (ACC_STATIC | ACC_PUBLIC | ACC_PROTECTED | ACC_PRIVATE)) == expected, s"${a.name}, ${a.access}")
+    }
+
+                                                        checkAccess(a, ACC_PUBLIC)
+    b.access &= ~ACC_PUBLIC;                            checkAccess(b, 0) // make it default access
+    c.access &= ~ACC_PUBLIC; c.access |= ACC_PROTECTED; checkAccess(c, ACC_PROTECTED) // make it protected - scalac actually never emits PROTECTED in bytecode, see javaFlags in BTypesFromSymbols
+                                                        checkAccess(d, ACC_PRIVATE)
+
+                             e.access |= ACC_STATIC;                   checkAccess(e, ACC_STATIC | ACC_PUBLIC)
+    f.access &= ~ACC_PUBLIC; f.access |= ACC_STATIC;                   checkAccess(f, ACC_STATIC)
+    g.access &= ~ACC_PUBLIC; g.access |= (ACC_STATIC | ACC_PROTECTED); checkAccess(g, ACC_STATIC | ACC_PROTECTED)
+                             h.access |= ACC_STATIC;                   checkAccess(h, ACC_STATIC | ACC_PRIVATE)
+
+    val List(raC, rbC, rcC, rdC, reC, rfC, rgC, rhC) = cCl.methods.asScala.toList.filter(_.name(0) == 'r').sortBy(_.name)
+
+    val List(rbD, rcD, rfD, rgD) = dCl.methods.asScala.toList.filter(_.name(0) == 'r').sortBy(_.name)
+
+    def check(method: MethodNode, dest: ClassNode, test: Option[AbstractInsnNode] => Unit): Unit = {
+      test(inliner.findIllegalAccess(method.instructions, classBTypeFromParsedClassfile(dest.name)))
+    }
+
+    val cOrDOwner = (_: Option[AbstractInsnNode] @unchecked) match {
+      case Some(mi: MethodInsnNode) if Set("a/C", "a/D")(mi.owner) => ()
+      // MatchError otherwise
+    }
+
+    // PUBLIC
+
+    // public methods allowed everywhere
+    for (m <- Set(raC, reC); c <- allClasses) check(m, c, assertEmpty)
+
+    // DEFAULT ACCESS
+
+    // default access OK in same package
+    for (m <- Set(rbC, rfC, rbD, rfD); c <- allClasses) {
+      if (c.name startsWith "a/") check(m, c, assertEmpty)
+      else check(m, c, cOrDOwner)
+    }
+
+    // PROTECTED
+
+    // protected accessed in same class, or protected static accessed in subclass(rgD).
+    // can be inlined to subclasses, and classes in the same package (gCl)
+    for (m <- Set(rcC, rgC, rgD); c <- Set(cCl, dCl, eCl, fCl, gCl, hCl)) check(m, c, assertEmpty)
+
+    // protected in non-subclass and different package
+    for (m <- Set(rcC, rgC)) check(m, iCl, cOrDOwner)
+
+    // non-static protected accessed in subclass (rcD). can be inlined to related class, or classes in the same package
+    for (c <- Set(cCl, dCl, eCl, fCl, gCl)) check(rcD, c, assertEmpty)
+
+    // rcD cannot be inlined into non-related classes, if the declaration and destination are not in the same package
+    for (c <- Set(hCl, iCl)) check(rcD, c, cOrDOwner)
+
+    // PRIVATE
+
+    // privated method accesses can only be inlined in the same class
+    for (m <- Set(rdC, rhC)) check(m, cCl, assertEmpty)
+    for (m <- Set(rdC, rhC); c <- allClasses.tail) check(m, c, cOrDOwner)
+  }
+}