checkers.scala

来自「JAVA 语言的函数式编程扩展」· SCALA 代码 · 共 601 行 · 第 1/2 页

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

// $Id: Checkers.scala 13819 2008-01-28 18:43:24Z odersky $

package scala.tools.nsc.backend.icode

import scala.collection.mutable.{Buffer, ListBuffer, Map, HashMap}
import scala.tools.nsc.symtab._

abstract class Checkers {
  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 numer 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 <code>MONITOR_ENTER/EXIT</code>
   *        Better checks for local var initializations
   */
  class ICodeChecker {
    import icodes._
    import opcodes._

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

    val in: Map[BasicBlock, TypeStack] = new HashMap()
    val out: Map[BasicBlock, TypeStack] = new HashMap()

    val emptyStack = new TypeStack()

    val STRING        = REFERENCE(definitions.StringClass)
    val SCALA_ALL     = REFERENCE(definitions.AllClass)
    val SCALA_ALL_REF = REFERENCE(definitions.AllRefClass)
//    val CASE_CLASS    = REFERENCE(definitions.getClass("scala.CaseClass"))

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

    def check(cls: IClass) {
      log("Checking class " + cls)
      clasz = cls

      for (f1 <- cls.fields; f2 <- cls.fields if f1 ne f2)
        if (f1.symbol.name == f2.symbol.name)
          Checkers.this.global.error("Repetitive field name: " +
                                     f1.symbol.fullNameString);

      for (m1 <- cls.methods; m2 <- cls.methods if m1 ne m2)
        if (m1.symbol.name == m2.symbol.name &&
            m1.symbol.tpe =:= m2.symbol.tpe)
          Checkers.this.global.error("Repetitive method: " +
                                     m1.symbol.fullNameString);
      clasz.methods.foreach(check)
    }

    /** Apply the give funtion to each pair of the cartesian product of
     * l1 x l2.
     */
    def pairwise[a](l1: List[a], l2: List[a])(f: (a, a) => Unit) =
      l1 foreach { x =>
        l2 foreach { y => f(x, y) }
      }

    def check(m: IMethod) {
      log("Checking method " + m)
      method = m
      if (!m.isDeferred)
        check(m.code)
    }

    def check(c: Code) {
      var worklist: Buffer[BasicBlock] = new ListBuffer()

      def append(elems: List[BasicBlock]) = elems foreach appendBlock;
      def appendBlock(bl: BasicBlock) =
        if ( !worklist.exists(bl.==) )
          worklist + bl;

      in.clear;  out.clear;
      code = c;
      worklist + c.startBlock;
      for (bl <- c.blocks) {
        in  += (bl -> emptyStack)
        out += (bl -> emptyStack)
      }

      while (worklist.length > 0) {
        val block = worklist(0); worklist.trimStart(1);
        val output = check(block, in(block));
        if (output != out(block) ||
            (out(block) eq emptyStack)) {
          log("Output changed for block: " + block.fullString);
          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 meet2(s1: TypeStack, s2: TypeStack): TypeStack = {
        if (s1 eq emptyStack) s2
        else if (s2 eq emptyStack) s1 
        else {
          if (s1.length != s2.length)
            throw new CheckerError("Incompatible stacks: " + s1 + " and " + s2 + " in " + method + " at entry to block: " + bl);
          new TypeStack(List.map2(s1.types, s2.types) (lub))
        }
      }

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

    private var typeStack: TypeStack = null
    private var instruction: Instruction = null
    private var basicBlock: BasicBlock = null

    /**
     * Check the basic block to be type correct and return the
     * produced type stack.
     */
    def check(b: BasicBlock, initial: TypeStack): TypeStack = {
      log("** Checking block:\n" + b.fullString + " with initial stack:\n" + initial)
      var stack = new TypeStack(initial)

      this.typeStack = stack
      this.basicBlock = b

      def typeError(k1: TypeKind, k2: TypeKind) {
        error(" expected: " + k1 + " but " + k2 + " found")
      }

      b traverse (instr => {

        def checkStack(len: Int) {
          if (stack.length < len)
            ICodeChecker.this.error("Expected at least " + len + " elements on the stack", stack);
          else
            ()
        }

        def checkLocal(local: Local) {
          method.lookupLocal(local.sym.name) match {
            case None => error(" " + local + " is not defined in method " + method);
            case _ => ()
          }
        }

        def checkField(obj: TypeKind, field: Symbol) {
          obj match {
            case REFERENCE(sym) =>
              if (sym.info.member(field.name) == NoSymbol) 
                error(" " + field + " is not defined in class " + clasz);
            case _ =>
              error(" 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 (isOneOf(tpe, allowed: _*))
            ()
          else
            error(tpe.toString() + " is not one of: " + allowed.toList.mkString("{", ", ", "}"));
        }

        /** Checks that the 2 topmost elements on stack are of the
         *  kind TypeKind.
         */
        def checkBinop(kind: TypeKind) {
          val (a, b) = stack.pop2
          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)
          params.reverse.foreach( (tpe) => checkType(stack.pop, toTypeKind(tpe)))
        }

        /** Checks that the object passed as receiver has a method
         *  <code>method</code> and that it is callable from the current method.
         *
         *  @param receiver ...
         *  @param 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.fullNameString);
              if (method hasFlag Flags.PRIVATE)
                checkBool(method.owner == clasz.symbol,
                          "Cannot call private method of " + method.owner.fullNameString 
                          + " from " + clasz.symbol.fullNameString);
              else if (method hasFlag Flags.PROTECTED)
                checkBool(clasz.symbol isSubClass method.owner,
                          "Cannot call protected method of " + method.owner.fullNameString
                          + " from " + clasz.symbol.fullNameString);

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

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

        def checkBool(cond: Boolean, msg: String) =
          if (cond) () else error(msg)

        this.instruction = instr

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

          case CONSTANT(const) =>
            stack push toTypeKind(const.tpe)

          case LOAD_ARRAY_ITEM(kind) =>
            checkStack(2)
            (stack.pop2: @unchecked) match {
              case (INT, ARRAY(elem)) => 
                if (!(elem <:< kind))
                  typeError(kind, elem);
                stack.push(elem);
              case (a, b) =>
                error(" expected and INT and a array reference, but " +
                    a + ", " + b + " found");
            }

         case LOAD_LOCAL(local) =>
           checkLocal(local)
           stack.push(local.kind)

         case LOAD_FIELD(field, isStatic) =>
           if (isStatic) {
             // the symbol's owner should contain it's field, but
             // this is already checked by the type checker, no need
             // to redo that here
           } else {
             checkStack(1)
             val obj = stack.pop
             checkField(obj, field)
           }