path: root/src/compiler/scala/tools/nsc/backend/icode/ICodeCheckers.scala

/* NSC -- new Scala compiler
 * Copyright 2005-2013 LAMP/EPFL
 * @author  Martin Odersky
 */

package scala.tools.nsc
package backend
package icode

import scala.collection.mutable
import scala.collection.mutable.ListBuffer

abstract class ICodeCheckers {
  val global: Global
  import global._

  /** <p>
   *    This class performs a set of checks similar to what the bytecode
   *    verifier does. For each basic block, it checks that:
   *  </p>
   *  <ul>
   *    <li>
   *      for primitive operations: the type and number of operands match
   *      the type of the operation
   *    </li>
   *    <li>
   *      for method calls: the method exists in the type of the receiver
   *      and the number and type of arguments match the declared type of
   *      the method.
   *    </li>
   *    <li>
   *      for object creation: the constructor can be called.
   *    </li>
   *    <li>
   *      for load/stores: the field/local/param exists and the type
   *      of the value matches that of the target.
   *    </li>
   *  </ul>
   *  <p>
   *    For a control flow graph it checks that type stacks at entry to
   *    each basic block 'agree':
   *  </p>
   *  <ul>
   *    <li>they have the same length</li>
   *    <li>there exists a lub for all types at the same position in stacks.</li>
   *  </ul>
   *
   *  @author  Iulian Dragos
   *  @version 1.0, 06/09/2005
   *
   *  @todo Better checks for `MONITOR_ENTER/EXIT`
   *        Better checks for local var initializations
   *
   *  @todo Iulian says: I think there's some outdated logic in the checker.
   * The issue with exception handlers being special for least upper
   * bounds pointed out some refactoring in the lattice class. Maybe
   * a worthwhile refactoring would be to make the checker use the
   * DataFlowAnalysis class, and use the lattice trait. In the
   * implementation of LUB, there's a flag telling if one of the
   * successors is 'exceptional'. The inliner is using this mechanism.
   */
  class ICodeChecker {
    import icodes._
    import opcodes._

    var clasz: IClass = _
    var method: IMethod = _
    var code: Code = _

    val in: mutable.Map[BasicBlock, TypeStack]  = perRunCaches.newMap()
    val out: mutable.Map[BasicBlock, TypeStack] = perRunCaches.newMap()
    val emptyStack = new TypeStack() {
      override def toString = "<empty>"
    }

    /** The presence of emptyStack means that path has not yet been checked
     *  (and may not be empty).
     */
    def notChecked(ts: TypeStack) = ts eq emptyStack
    def initMaps(bs: Seq[BasicBlock]): Unit = {
      in.clear()
      out.clear()
      bs foreach { b =>
        in(b) = emptyStack
        out(b) = emptyStack
      }
    }

    /** A wrapper to route log messages to debug output also.
     */
    def logChecker(msg: String) = {
      log(msg)
      checkerDebug(msg)
    }

    def checkICodes(): Unit = {
      if (settings.verbose)
      println("[[consistency check at the beginning of phase " + globalPhase.name + "]]")
      classes.values foreach check
    }

    private def posStr(p: Position) =
      if (p.isDefined) p.line.toString else "<??>"

    private def indent(s: String, prefix: String): String = {
      val lines = s split "\\n"
      lines map (prefix + _) mkString "\n"
    }

    /** Only called when m1 < m2, so already known that (m1 ne m2).
     */
    private def isConflict(m1: IMember, m2: IMember, canOverload: Boolean) = (
      (m1.symbol.name == m2.symbol.name) &&
      (!canOverload || (m1.symbol.tpe =:= m2.symbol.tpe))
    )

    def check(cls: IClass) {
      logChecker("\n<<-- Checking class " + cls + " -->>")
      clasz = cls

      for (f1 <- cls.fields ; f2 <- cls.fields ; if f1 < f2)
        if (isConflict(f1, f2, canOverload = false))
          icodeError("Repetitive field name: " + f1.symbol.fullName)

      for (m1 <- cls.methods ; m2 <- cls.methods ; if m1 < m2)
        if (isConflict(m1, m2, canOverload = true))
          icodeError("Repetitive method: " + m1.symbol.fullName)

      clasz.methods foreach check
    }

    def check(m: IMethod) {
      logChecker("\n<< Checking method " + m.symbol.name + " >>")
      method = m
      if (!m.isAbstractMethod)
        check(m.code)
    }

    def check(c: Code) {
      val worklist = new ListBuffer[BasicBlock]
      def append(elems: List[BasicBlock]) =
        worklist ++= (elems filterNot (worklist contains _))

      code = c
      worklist += c.startBlock
      initMaps(c.blocks)

      while (worklist.nonEmpty) {
        val block  = worklist remove 0
        val output = check(block, in(block))
        if (output != out(block) || notChecked(out(block))) {
          if (block.successors.nonEmpty)
            logChecker("** Output change for %s: %s -> %s".format(block, out(block), output))

          out(block) = output
          append(block.successors)
          block.successors foreach meet
        }
      }
    }

    /**
     * Apply the meet operator of the stack lattice on bl's predecessors.
     * :-). Compute the input to bl by checking that all stacks have the
     * same length, and taking the lub of types at the same positions.
     */
    def meet(bl: BasicBlock) {
      val preds = bl.predecessors

      def hasNothingType(s: TypeStack) = s.nonEmpty && (s.head == NothingReference)

      /* XXX workaround #1: one stack empty, the other has BoxedUnit.
       * One example where this arises is:
       *
       * def f(b: Boolean): Unit = synchronized { if (b) () }
       */
      def allUnits(s: TypeStack)   = s.types forall (_ == BoxedUnitReference)

      def ifAthenB[T](f: T => Boolean): PartialFunction[(T, T), T] = {
        case (x1, x2) if f(x1)  => x2
        case (x1, x2) if f(x2)  => x1
      }

      /* XXX workaround #2: different stacks heading into an exception
       * handler which will clear them anyway.  Examples where it arises:
       *
       * var bippy: Int = synchronized { if (b) 5 else 10 }
       */
      def isHandlerBlock() = bl.exceptionHandlerStart

      def meet2(s1: TypeStack, s2: TypeStack): TypeStack = {
        def workaround(msg: String) = {
          checkerDebug(msg + ": " + method + " at block " + bl)
          checkerDebug("  s1: " + s1)
          checkerDebug("  s2: " + s2)
          new TypeStack()
        }
        def incompatibleString = (
          "Incompatible stacks: " + s1 + " and " + s2 + " in " + method + " at entry to block " + bl.label + ":\n" +
          indent(bl.predContents, "// ") +
          indent(bl.succContents, "// ") +
          indent(bl.blockContents, "// ")
        )

        val f: ((TypeStack, TypeStack)) => TypeStack = {
          ifAthenB(notChecked) orElse ifAthenB(hasNothingType) orElse {
            case (s1: TypeStack, s2: TypeStack) =>
              if (s1.length != s2.length) {
                if (allUnits(s1) && allUnits(s2))
                  workaround("Ignoring mismatched boxed units")
                else if (isHandlerBlock())
                  workaround("Ignoring mismatched stacks entering exception handler")
                else
                  throw new CheckerException(incompatibleString)
              }
              else {
                val newStack: TypeStack = try {
                    new TypeStack((s1.types, s2.types).zipped map lub)
                } catch {
                  case t: Exception =>
                    checkerDebug(t.toString + ": " + s1.types.toString + " vs " + s2.types.toString)
                    new TypeStack(s1.types)
                }
                if (newStack.isEmpty || s1.types == s2.types) ()  // not interesting to report
                else checkerDebug("Checker created new stack:\n  (%s, %s) => %s".format(s1, s2, newStack))

                newStack
              }
          }
        }

        f((s1, s2))
      }

      if (preds.nonEmpty) {
        in(bl) = (preds map out.apply) reduceLeft meet2
        log("Input changed for block: " + bl +" to: " + in(bl))
      }
    }

    private var instruction: Instruction = null
    private var basicBlock: BasicBlock = null
    private var stringConcatDepth = 0
    private def stringConcatIndent() = "  " * stringConcatDepth
    private def currentInstrString: String = {
      val (indent, str) = this.instruction match {
        case CALL_PRIMITIVE(StartConcat)      =>
          val x = stringConcatIndent()
          stringConcatDepth += 1
          (x, "concat(")
        case CALL_PRIMITIVE(EndConcat)        =>
          if (stringConcatDepth > 0) {
            stringConcatDepth -= 1
            (stringConcatIndent(), ") // end concat")
          }
          else ("", "")
        case _ =>
          (stringConcatIndent(), this.instruction match {
            case CALL_PRIMITIVE(StringConcat(el)) => "..."
            case null                             => "null"
            case cm @ CALL_METHOD(_, _)           => if (clasz.symbol == cm.hostClass) cm.toShortString else cm.toString
            case x                                => x.toString
          })
      }
      indent + str
    }
    /** A couple closure creators to reduce noise in the output: when multiple
     *  items are pushed or popped, this lets us print something short and sensible
     *  for those beyond the first.
     */
    def mkInstrPrinter(f: Int => String): () => String = {
      var counter = -1
      val indent = stringConcatIndent()
      () => {
        counter += 1
        if (counter == 0) currentInstrString
        else indent + f(counter)
      }
    }
    def defaultInstrPrinter: () => String = mkInstrPrinter(_ => "\"\"\"")

    /**
     * Check the basic block to be type correct and return the
     * produced type stack.
     */
    def check(b: BasicBlock, initial: TypeStack): TypeStack = {
      this.basicBlock = b

      logChecker({
        val prefix = "** Checking " + b.fullString

        if (initial.isEmpty) prefix
        else prefix + " with initial stack " + initial.types.mkString("[", ", ", "]")
      })

      val stack = new TypeStack(initial)
      def checkStack(len: Int) {
        if (stack.length < len)
          ICodeChecker.this.icodeError("Expected at least " + len + " elements on the stack", stack)
      }

      def sizeString(push: Boolean) = {
        val arrow = if (push) "-> " else "<- "
        val sp    = "   " * stack.length

        sp + stack.length + arrow
      }
      def printStackString(isPush: Boolean, value: TypeKind, instrString: String) = {
        val pushString = if (isPush) "+" else "-"
        val posString  = posStr(this.instruction.pos)

        checkerDebug("%-70s %-4s %s %s".format(sizeString(isPush) + value, posString, pushString, instrString))
      }
      def _popStack: TypeKind = {
        if (stack.isEmpty) {
          icodeError("Popped empty stack in " + b.fullString + ", throwing a Unit")
          return UNIT
        }
        stack.pop
      }
      def popStackN(num: Int, instrFn: () => String = defaultInstrPrinter) = {
        List.range(0, num) map { _ =>
          val res = _popStack
          printStackString(isPush = false, res, instrFn())
          res
        }
      }
      def pushStackN(xs: Seq[TypeKind], instrFn: () => String) = {
        xs foreach { x =>
          stack push x
          printStackString(isPush = true, x, instrFn())
        }
      }

      def popStack     = { checkStack(1) ; (popStackN(1): @unchecked) match { case List(x) => x } }
      def popStack2    = { checkStack(2) ; (popStackN(2): @unchecked) match { case List(x, y) => (x, y) } }
      def popStack3    = { checkStack(3) ; (popStackN(3): @unchecked) match { case List(x, y, z) => (x, y, z) } }

      /* Called by faux instruction LOAD_EXCEPTION to wipe out the stack. */
      def clearStack() = {
        if (stack.nonEmpty)
          logChecker("Wiping out the " + stack.length + " element stack for exception handler: " + stack)

        1 to stack.length foreach (_ => popStack)
      }

      def pushStack(xs: TypeKind*): Unit = {
        pushStackN(xs filterNot (_ == UNIT), defaultInstrPrinter)
      }

      def typeError(k1: TypeKind, k2: TypeKind) {
        icodeError("\n  expected: " + k1 + "\n     found: " + k2)
      }
      def isSubtype(k1: TypeKind, k2: TypeKind) = (k1 isAssignabledTo k2) || {
        import platform.isMaybeBoxed

        (k1, k2) match {
          case (REFERENCE(_), REFERENCE(_)) if k1.isInterfaceType || k2.isInterfaceType =>
            logChecker("Considering %s <:< %s because at least one is an interface".format(k1, k2))
            true
          case (REFERENCE(cls1), REFERENCE(cls2)) if isMaybeBoxed(cls1) || isMaybeBoxed(cls2) =>
            logChecker("Considering %s <:< %s because at least one might be a boxed primitive".format(cls1, cls2))
            true
          case _ =>
            false
        }
      }

      def subtypeTest(k1: TypeKind, k2: TypeKind): Unit =
        if (isSubtype(k1, k2)) ()
        else typeError(k2, k1)

      for (instr <- b) {
        this.instruction = instr

        def checkLocal(local: Local) {
          if ((method lookupLocal local.sym.name).isEmpty)
            icodeError(s" $local is not defined in method $method")
        }
        def checkField(obj: TypeKind, field: Symbol): Unit = obj match {
          case REFERENCE(sym) =>
            if (sym.info.member(field.name) == NoSymbol)
              icodeError(" " + field + " is not defined in class " + clasz)
          case _ =>
            icodeError(" expected reference type, but " + obj + " found")
        }

        /* Checks that tpe is a subtype of one of the allowed types */
        def checkType(tpe: TypeKind, allowed: TypeKind*) = (
          if (allowed exists (k => isSubtype(tpe, k))) ()
          else icodeError(tpe + " is not one of: " + allowed.mkString("{ ", ", ", " }"))
        )
        def checkNumeric(tpe: TypeKind) =
          checkType(tpe, BYTE, CHAR, SHORT, INT, LONG, FLOAT, DOUBLE)

        /* Checks that the 2 topmost elements on stack are of the kind TypeKind. */
        def checkBinop(kind: TypeKind) {
          val (a, b) = popStack2
          checkType(a, kind)
          checkType(b, kind)
        }

        /* Check that arguments on the stack match method params. */
        def checkMethodArgs(method: Symbol) {
          val params = method.info.paramTypes
          checkStack(params.length)
          (
            popStackN(params.length, mkInstrPrinter(num => "<arg" + num + ">")),
            params.reverse map toTypeKind).zipped foreach ((x, y) => checkType(x, y)
          )
        }

        /* Checks that the object passed as receiver has a method
         * `method` and that it is callable from the current method.
         */
        def checkMethod(receiver: TypeKind, method: Symbol) =
          receiver match {
            case REFERENCE(sym) =>
              checkBool(sym.info.member(method.name) != NoSymbol,
                        "Method " + method + " does not exist in " + sym.fullName)
              if (method.isPrivate)
                checkBool(method.owner == clasz.symbol,
                          "Cannot call private method of " + method.owner.fullName
                          + " from " + clasz.symbol.fullName)
              else if (method.isProtected) {
                val isProtectedOK = (
                  (clasz.symbol isSubClass method.owner) ||
                  (clasz.symbol.typeOfThis.typeSymbol isSubClass method.owner)  // see pos/bug780.scala
                )

                checkBool(isProtectedOK,
                          "Cannot call protected method of " + method.owner.fullName
                          + " from " + clasz.symbol.fullName)
              }

            case ARRAY(_) =>
              checkBool(receiver.toType.member(method.name) != NoSymbol,
                        "Method " + method + " does not exist in " + receiver)

            case t =>
              icodeError("Not a reference type: " + t)
          }

        def checkBool(cond: Boolean, msg: String) =
          if (!cond) icodeError(msg)

        if (settings.debug) {
          log("PC: " + instr)
          log("stack: " + stack)
          log("================")
        }
        instr match {
          case THIS(clasz) =>
            pushStack(toTypeKind(clasz.tpe))

          case CONSTANT(const) =>
            pushStack(toTypeKind(const.tpe))

          case LOAD_ARRAY_ITEM(kind) =>
            popStack2 match {
              case (INT, ARRAY(elem)) =>
                subtypeTest(elem, kind)
                pushStack(elem)
              case (a, b) =>
                icodeError(" expected an INT and an array reference, but " +
                    a + ", " + b + " found")
            }

         case LOAD_LOCAL(local) =>
           checkLocal(local)
           pushStack(local.kind)

         case LOAD_FIELD(field, isStatic) =>
           // the symbol's owner should contain its field, but
           // this is already checked by the type checker, no need
           // to redo that here
           if (isStatic) ()
           else checkField(popStack, field)

           pushStack(toTypeKind(field.tpe))

         case LOAD_MODULE(module) =>
           checkBool((module.isModule || module.isModuleClass),
                     "Expected module: " + module + " flags: " + module.flagString)
           pushStack(toTypeKind(module.tpe))

          case STORE_THIS(kind) =>
           val actualType = popStack
           if (actualType.isReferenceType) subtypeTest(actualType, kind)
           else icodeError("Expected this reference but found: " + actualType)

         case STORE_ARRAY_ITEM(kind) =>
           popStack3 match {
             case (k, INT, ARRAY(elem)) =>
               subtypeTest(k, kind)
               subtypeTest(k, elem)
             case (a, b, c) =>
                icodeError(" expected and array reference, and int and " + kind +
                      " but " + a + ", " + b + ", " + c + " found")
           }

         case STORE_LOCAL(local) =>
           checkLocal(local)
           val actualType = popStack
           if (local.kind != NullReference)
            subtypeTest(actualType, local.kind)

         case STORE_FIELD(field, true) =>     // static
           val fieldType = toTypeKind(field.tpe)
           val actualType = popStack
           subtypeTest(actualType, fieldType)

         case STORE_FIELD(field, false) =>    // not static
           val (value, obj) = popStack2
           checkField(obj, field)
           val fieldType = toTypeKind(field.tpe)
           if (fieldType == NullReference) ()
           else subtypeTest(value, fieldType)

         case CALL_PRIMITIVE(primitive) =>
           checkStack(instr.consumed)
           primitive match {
             case Negation(kind) =>
               checkType(kind, BOOL, BYTE, CHAR, SHORT, INT, LONG, FLOAT, DOUBLE)
               checkType(popStack, kind)
               pushStack(kind)

             case Test(op, kind, zero) =>
               if (zero) checkType(popStack, kind)
               else checkBinop(kind)

               pushStack(BOOL)

             case Comparison(op, kind) =>
               checkNumeric(kind)
               checkBinop(kind)
               pushStack(INT)

             case Arithmetic(op, kind) =>
               checkNumeric(kind)
               if (op == NOT)
                 checkType(popStack, kind)
               else
                 checkBinop(kind)
               pushStack(kind)

             case Logical(op, kind) =>
               checkType(kind, BOOL, BYTE, CHAR, SHORT, INT, LONG)
               checkBinop(kind)
               pushStack(kind)

             case Shift(op, kind) =>
               checkType(kind, BYTE, CHAR, SHORT, INT, LONG)
               val (a, b) = popStack2
               checkType(a, INT)
               checkType(b, kind)
               pushStack(kind)

             case Conversion(src, dst) =>
               checkNumeric(src)
               checkNumeric(dst)
               checkType(popStack, src)
               pushStack(dst)

             case ArrayLength(kind) =>
               popStack match {
                 case ARRAY(elem) => checkType(elem, kind)
                 case arr         => icodeError(" array reference expected, but " + arr + " found")
               }
               pushStack(INT)

             case StartConcat =>
               pushStack(ConcatClass)

             case EndConcat =>
               checkType(popStack, ConcatClass)
               pushStack(StringReference)

             case StringConcat(el) =>
               checkType(popStack, el)
               checkType(popStack, ConcatClass)
               pushStack(ConcatClass)
           }

         case CALL_METHOD(method, style) =>
           // PP to ID: I moved the if (!method.isConstructor) check to cover all
           // the styles to address checker failure.  Can you confirm if the change
           // was correct? If I remember right it's a matter of whether some brand
           // of supercall should leave a value on the stack, and I know there is some
           // trickery performed elsewhere regarding this.
           val paramCount = method.info.paramTypes.length match {
             case x if style.hasInstance  => x + 1
             case x                       => x
           }
           if (style == Static(onInstance = true))
             checkBool(method.isPrivate || method.isConstructor, "Static call to non-private method.")

          checkStack(paramCount)
          checkMethodArgs(method)
          if (style.hasInstance)
            checkMethod(popStack, method)
          if (!method.isConstructor)
            pushStack(toTypeKind(method.info.resultType))

          case NEW(kind) =>
            pushStack(kind)

          case CREATE_ARRAY(elem, dims) =>
            checkStack(dims)
            stack.pop(dims) foreach (checkType(_, INT))
            pushStack(ARRAY(elem))

          case IS_INSTANCE(tpe) =>
            val ref = popStack
            checkBool(!ref.isValueType, "IS_INSTANCE on primitive type: " + ref)
            checkBool(!tpe.isValueType, "IS_INSTANCE on primitive type: " + tpe)
            pushStack(BOOL)

          case CHECK_CAST(tpe) =>
            val ref = popStack
            checkBool(!ref.isValueType, "CHECK_CAST to primitive type: " + ref)
            checkBool(!tpe.isValueType, "CHECK_CAST to primitive type: " + tpe)
            pushStack(tpe)

          case SWITCH(tags, labels) =>
            checkType(popStack, INT)
            checkBool(tags.length == labels.length - 1,
                      "The number of tags and labels does not coincide.")
            checkBool(labels forall (b => code.blocks contains b),
                      "Switch target cannot be found in code.")

          case JUMP(whereto) =>
            checkBool(code.blocks contains whereto,
                      "Jump to non-existant block " + whereto)

          case CJUMP(success, failure, cond, kind) =>
            checkBool(code.blocks contains success,
                      "Jump to non-existant block " + success)
            checkBool(code.blocks contains failure,
                      "Jump to non-existant block " + failure)
            checkBinop(kind)

          case CZJUMP(success, failure, cond, kind) =>
            checkBool(code.blocks contains success,
                      "Jump to non-existant block " + success)
            checkBool(code.blocks contains failure,
                      "Jump to non-existant block " + failure)
            checkType(popStack, kind)

          case RETURN(UNIT) => ()
          case RETURN(kind) =>
            val top = popStack
            if (kind.isValueType) checkType(top, kind)
            else checkBool(!top.isValueType, "" + kind + " is a reference type, but " + top + " is not")

          case THROW(clasz) =>
            checkType(popStack, toTypeKind(clasz.tpe))
            pushStack(NothingReference)

          case DROP(kind) =>
            checkType(popStack, kind)

          case DUP(kind) =>
            val top = popStack
            checkType(top, kind)
            pushStack(top)
            pushStack(top)

          case MONITOR_ENTER() =>
            checkBool(popStack.isReferenceType, "MONITOR_ENTER on non-reference type")

          case MONITOR_EXIT() =>
            checkBool(popStack.isReferenceType, "MONITOR_EXIT on non-reference type")

          case BOX(kind) =>
            checkType(popStack, kind)
            pushStack(REFERENCE(definitions.boxedClass(kind.toType.typeSymbol)))

          case UNBOX(kind) =>
            popStack
            pushStack(kind)

          case LOAD_EXCEPTION(clasz) =>
            clearStack()
            pushStack(REFERENCE(clasz))

          case SCOPE_ENTER(_) | SCOPE_EXIT(_) =>
            ()

          case _ =>
            abort("Unknown instruction: " + instr)
        }
      }
      stack
    }

    //////////////// Error reporting /////////////////////////

    def icodeError(msg: String) {
      ICodeCheckers.this.global.warning(
        "!! ICode checker fatality in " + method +
        "\n  at: " + basicBlock.fullString +
        "\n  error message: " + msg
      )
    }

    def icodeError(msg: String, stack: TypeStack) {
      icodeError(msg + "\n type stack: " + stack)
    }
  }
}