diff options
51 files changed, 1212 insertions, 316 deletions
@@ -1388,6 +1388,7 @@ QUICK BUILD (QUICK) <pathelement location="${build-quick.dir}/classes/compiler"/> <pathelement location="${build-quick.dir}/classes/repl"/> <pathelement location="${build-quick.dir}/classes/scalap"/> + <pathelement location="${build-quick.dir}/classes/continuations-library"/> <pathelement location="${jline.jar}"/> <path refid="asm.classpath"/> <path refid="forkjoin.classpath"/> diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 7ee3ee551f..67c2b99475 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -25,7 +25,7 @@ import transform._ import backend.icode.{ ICodes, GenICode, ICodeCheckers } import backend.{ ScalaPrimitives, Platform, JavaPlatform } import backend.jvm.GenASM -import backend.opt.{ Inliners, InlineExceptionHandlers, ClosureElimination, DeadCodeElimination } +import backend.opt.{ Inliners, InlineExceptionHandlers, ConstantOptimization, ClosureElimination, DeadCodeElimination } import backend.icode.analysis._ import scala.language.postfixOps @@ -594,6 +594,13 @@ class Global(var currentSettings: Settings, var reporter: Reporter) val runsRightAfter = None } with ClosureElimination + // phaseName = "constopt" + object constantOptimization extends { + val global: Global.this.type = Global.this + val runsAfter = List("closelim") + val runsRightAfter = None + } with ConstantOptimization + // phaseName = "dce" object deadCode extends { val global: Global.this.type = Global.this @@ -678,6 +685,7 @@ class Global(var currentSettings: Settings, var reporter: Reporter) inliner -> "optimization: do inlining", inlineExceptionHandlers -> "optimization: inline exception handlers", closureElimination -> "optimization: eliminate uncalled closures", + constantOptimization -> "optimization: optimize null and other constants", deadCode -> "optimization: eliminate dead code", terminal -> "The last phase in the compiler chain" ) diff --git a/src/compiler/scala/tools/nsc/ast/TreeGen.scala b/src/compiler/scala/tools/nsc/ast/TreeGen.scala index b9eb511a9a..692afbac66 100644 --- a/src/compiler/scala/tools/nsc/ast/TreeGen.scala +++ b/src/compiler/scala/tools/nsc/ast/TreeGen.scala @@ -19,18 +19,6 @@ abstract class TreeGen extends scala.reflect.internal.TreeGen with TreeDSL { import global._ import definitions._ - def mkCheckInit(tree: Tree): Tree = { - val tpe = - if (tree.tpe != null || !tree.hasSymbolField) tree.tpe - else tree.symbol.tpe - - if (!global.phase.erasedTypes && settings.warnSelectNullable.value && - tpe <:< NotNullClass.tpe && !tpe.isNotNull) - mkRuntimeCall(nme.checkInitialized, List(tree)) - else - tree - } - /** Builds a fully attributed wildcard import node. */ def mkWildcardImport(pkg: Symbol): Import = { diff --git a/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala b/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala new file mode 100644 index 0000000000..b80acc2324 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala @@ -0,0 +1,622 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2013 LAMP/EPFL + * @author James Iry + */ + +package scala.tools.nsc +package backend.opt + +import scala.tools.nsc.backend.icode.analysis.LubException +import scala.annotation.tailrec + +/** + * ConstantOptimization uses abstract interpretation to approximate for + * each instruction what constants a variable or stack slot might hold + * or cannot hold. From this it will eliminate unreachable conditionals + * where only one branch is reachable, e.g. to eliminate unnecessary + * null checks. + * + * With some more work it could be extended to + * - cache stable values (final fields, modules) in locals + * - replace the copy propagation in ClosureElilmination + * - fold constants + * - eliminate unnecessary stores and loads + * - propagate knowledge gathered from conditionals for further optimization + */ +abstract class ConstantOptimization extends SubComponent { + import global._ + import icodes._ + import icodes.opcodes._ + + val phaseName = "constopt" + + /** Create a new phase */ + override def newPhase(p: Phase) = new ConstantOptimizationPhase(p) + + /** + * The constant optimization phase. + */ + class ConstantOptimizationPhase(prev: Phase) extends ICodePhase(prev) { + + def name = phaseName + + override def apply(c: IClass) { + if (settings.YconstOptimization.value) { + val analyzer = new ConstantOptimizer + analyzer optimizeClass c + } + } + } + + class ConstantOptimizer { + def optimizeClass(cls: IClass) { + log(s"Analyzing ${cls.methods.size} methods in $cls.") + cls.methods foreach { m => + optimizeMethod(m) + } + } + + def optimizeMethod(m: IMethod) { + if (m.hasCode) { + log(s"Analyzing ${m.symbol}") + val replacementInstructions = interpretMethod(m) + for (block <- m.blocks) { + if (replacementInstructions contains block) { + val instructions = replacementInstructions(block) + block.replaceInstruction(block.lastInstruction, instructions) + } + } + } + } + + /** + * A single possible (or impossible) datum that can be held in Contents + */ + private sealed abstract class Datum + /** + * A constant datum + */ + private case class Const(c: Constant) extends Datum { + def isIntAssignable = c.tag >= BooleanTag && c.tag <= IntTag + def toInt = c.tag match { + case BooleanTag => if (c.booleanValue) 1 else 0 + case _ => c.intValue + } + + /** + * True if this constant would compare to other as true under primitive eq + */ + override def equals(other: Any) = other match { + case oc @ Const(o) => (this eq oc) || (if (this.isIntAssignable && oc.isIntAssignable) this.toInt == oc.toInt else c.value == o.value) + case _ => false + } + + /** + * Hash code consistent with equals + */ + override def hashCode = if (this.isIntAssignable) this.toInt else c.hashCode + + } + /** + * A datum that has been Boxed via a BOX instruction + */ + private case class Boxed(c: Datum) extends Datum + + /** + * The knowledge we have about the abstract state of one location in terms + * of what constants it might or cannot hold. Forms a lower + * lattice where lower elements in the lattice indicate less knowledge. + * + * With the following partial ordering (where '>' indicates more precise knowledge) + * + * Possible(xs) > Possible(xs + y) + * Possible(xs) > Impossible(ys) + * Impossible(xs + y) > Impossible(xs) + * + * and the following merges, which indicate merging knowledge from two paths through + * the code, + * + * // left must be 1 or 2, right must be 2 or 3 then we must have a 1, 2 or 3 + * Possible(xs) merge Possible(ys) => Possible(xs union ys) + * + * // Left says can't be 2 or 3, right says can't be 3 or 4 + * // then it's not 3 (it could be 2 from the right or 4 from the left) + * Impossible(xs) merge Impossible(ys) => Impossible(xs intersect ys) + * + * // Left says it can't be 2 or 3, right says it must be 3 or 4, then + * // it can't be 2 (left rules out 4 and right says 3 is possible) + * Impossible(xs) merge Possible(ys) => Impossible(xs -- ys) + * + * Intuitively, Possible(empty) says that a location can't hold anything, + * it's uninitialized. However, Possible(empty) never appears in the code. + * + * Conversely, Impossible(empty) says nothing is impossible, it could be + * anything. Impossible(empty) is given a synonym UNKNOWN and is used + * for, e.g., the result of an arbitrary method call. + */ + private sealed abstract class Contents { + /** + * Join this Contents with another coming from another path. Join enforces + * the lattice structure. It is symmetrical and never moves upward in the + * lattice + */ + final def merge(other: Contents): Contents = if (this eq other) this else (this, other) match { + case (Possible(possible1), Possible(possible2)) => + Possible(possible1 union possible2) + case (Impossible(impossible1), Impossible(impossible2)) => + Impossible(impossible1 intersect impossible2) + case (Impossible(impossible), Possible(possible)) => + Impossible(impossible -- possible) + case (Possible(possible), Impossible(impossible)) => + Impossible(impossible -- possible) + } + // TODO we could have more fine-grained knowledge, e.g. know that 0 < x < 3. But for now equality/inequality is a good start. + def mightEqual(other: Contents): Boolean + def mightNotEqual(other: Contents): Boolean + } + private def SingleImpossible(x: Datum) = new Impossible(Set(x)) + + /** + * The location is known to have one of a set of values. + */ + private case class Possible(possible: Set[Datum]) extends Contents { + assert(possible.nonEmpty, "Contradiction: had an empty possible set indicating an uninitialized location") + def mightEqual(other: Contents): Boolean = (this eq other) || (other match { + // two Possibles might be equal if they have any possible members in common + case Possible(possible2) => (possible intersect possible2).nonEmpty + // a possible can be equal to an impossible if the impossible doesn't rule + // out all the possibilities + case Impossible(possible2) => (possible -- possible2).nonEmpty + }) + def mightNotEqual(other: Contents): Boolean = (this ne other) && (other match { + // two Possibles might not be equal if either has possible members that the other doesn't + case Possible(possible2) => (possible -- possible2).nonEmpty || (possible2 -- possible).nonEmpty + case Impossible(_) => true + }) + } + private def SinglePossible(x: Datum) = new Possible(Set(x)) + + /** + * The location is known to not have any of a set of values value (e.g null). + */ + private case class Impossible(impossible: Set[Datum]) extends Contents { + def mightEqual(other: Contents): Boolean = (this eq other) || (other match { + case Possible(_) => other mightEqual this + case _ => true + }) + def mightNotEqual(other: Contents): Boolean = (this eq other) || (other match { + case Possible(_) => other mightNotEqual this + case _ => true + }) + } + + /** + * Our entire knowledge about the contents of all variables and the stack. It forms + * a lattice primarily driven by the lattice structure of Contents. + * + * In addition to the rules of contents, State has the following properties: + * - The merge of two sets of locals holds the merges of locals found in the intersection + * of the two sets of locals. Locals not found in a + * locals map are thus possibly uninitialized and attempting to load them results + * in an error. + * - The stack heights of two states must match otherwise it's an error to merge them + * + * State is immutable in order to aid in structure sharing of local maps and stacks + */ + private case class State(locals: Map[Local, Contents], stack: List[Contents]) { + def mergeLocals(olocals: Map[Local, Contents]): Map[Local, Contents] = if (locals eq olocals) locals else Map((for { + key <- (locals.keySet intersect olocals.keySet).toSeq + } yield (key, locals(key) merge olocals(key))): _*) + + def merge(other: State): State = if (this eq other) this else { + @tailrec def mergeStacks(l: List[Contents], r: List[Contents], out: List[Contents]): List[Contents] = (l, r) match { + case (Nil, Nil) => out.reverse + case (l, r) if l eq r => out.reverse ++ l + case (lhead :: ltail, rhead :: rtail) => mergeStacks(ltail, rtail, (lhead merge rhead) :: out) + case _ => sys.error("Mismatched stack heights") + } + + val newLocals = mergeLocals(other.locals) + + val newStack = if (stack eq other.stack) stack else mergeStacks(stack, other.stack, Nil) + State(newLocals, newStack) + } + + /** + * Peek at the top of the stack without modifying it. Error if the stack is empty + */ + def peek(n: Int): Contents = stack(n) + /** + * Push contents onto a stack + */ + def push(contents: Contents): State = this copy (stack = contents :: stack) + /** + * Drop n elements from the stack + */ + def drop(number: Int): State = this copy (stack = stack drop number) + /** + * Store the top of the stack into the specified local. An error if the stack + * is empty + */ + def store(variable: Local): State = { + val contents = stack.head + val newVariables = locals + ((variable, contents)) + new State(newVariables, stack.tail) + } + /** + * Load the specified local onto the top of the stack. An error the the local is uninitialized. + */ + def load(variable: Local): State = { + val contents: Contents = locals.getOrElse(variable, sys.error(s"$variable is not initialized")) + push(contents) + } + /** + * A copy of this State with an empty stack + */ + def cleanStack: State = if (stack.isEmpty) this else this copy (stack = Nil) + } + + // some precomputed constants + private val NULL = Const(Constant(null: Any)) + private val UNKNOWN = Impossible(Set.empty) + private val NOT_NULL = SingleImpossible(NULL) + private val CONST_UNIT = SinglePossible(Const(Constant(()))) + private val CONST_FALSE = SinglePossible(Const(Constant(false))) + private val CONST_ZERO_BYTE = SinglePossible(Const(Constant(0: Byte))) + private val CONST_ZERO_SHORT = SinglePossible(Const(Constant(0: Short))) + private val CONST_ZERO_CHAR = SinglePossible(Const(Constant(0: Char))) + private val CONST_ZERO_INT = SinglePossible(Const(Constant(0: Int))) + private val CONST_ZERO_LONG = SinglePossible(Const(Constant(0: Long))) + private val CONST_ZERO_FLOAT = SinglePossible(Const(Constant(0.0f))) + private val CONST_ZERO_DOUBLE = SinglePossible(Const(Constant(0.0d))) + private val CONST_NULL = SinglePossible(NULL) + + /** + * Given a TypeKind, figure out what '0' for it means in order to interpret CZJUMP + */ + private def getZeroOf(k: TypeKind): Contents = k match { + case UNIT => CONST_UNIT + case BOOL => CONST_FALSE + case BYTE => CONST_ZERO_BYTE + case SHORT => CONST_ZERO_SHORT + case CHAR => CONST_ZERO_CHAR + case INT => CONST_ZERO_INT + case LONG => CONST_ZERO_LONG + case FLOAT => CONST_ZERO_FLOAT + case DOUBLE => CONST_ZERO_DOUBLE + case REFERENCE(_) => CONST_NULL + case ARRAY(_) => CONST_NULL + case BOXED(_) => CONST_NULL + case ConcatClass => abort("no zero of ConcatClass") + } + + // normal locals can't be null, so we use null to mean the magic 'this' local + private val THIS_LOCAL: Local = null + + /** + * interpret a single instruction to find its impact on the abstract state + */ + private def interpretInst(in: State, inst: Instruction): State = { + // pop the consumed number of values off the `in` state's stack, producing a new state + def dropConsumed: State = in drop inst.consumed + + inst match { + case THIS(_) => + in load THIS_LOCAL + + case CONSTANT(k) => + // treat NaN as UNKNOWN because NaN must never equal NaN + val const = if (k.isNaN) UNKNOWN + else SinglePossible(Const(k)) + in push const + + case LOAD_ARRAY_ITEM(_) | LOAD_FIELD(_, _) | CALL_PRIMITIVE(_) => + dropConsumed push UNKNOWN + + case LOAD_LOCAL(local) => + // TODO if a local is known to hold a constant then we can replace this instruction with a push of that constant + in load local + + case STORE_LOCAL(local) => + in store local + + case STORE_THIS(_) => + // if a local is already known to have a constant and we're replacing with the same constant then we can + // replace this with a drop + in store THIS_LOCAL + + case CALL_METHOD(_, _) => + // TODO we could special case implementations of equals that are known, e.g. String#equals + // We could turn Possible(string constants).equals(Possible(string constants) into an eq check + // We could turn nonConstantString.equals(constantString) into constantString.equals(nonConstantString) + // and eliminate the null check that likely precedes this call + val initial = dropConsumed + (0 until inst.produced).foldLeft(initial) { case (know, _) => know push UNKNOWN } + + case BOX(_) => + val value = in peek 0 + // we simulate boxing by, um, boxing the possible/impossible contents + // so if we have Possible(1,2) originally then we'll end up with + // a Possible(Boxed(1), Boxed(2)) + // Similarly, if we know the input is not a 0 then we'll know the + // output is not a Boxed(0) + val newValue = value match { + case Possible(values) => Possible(values map Boxed) + case Impossible(values) => Impossible(values map Boxed) + } + dropConsumed push newValue + + case UNBOX(_) => + val value = in peek 0 + val newValue = value match { + // if we have a Possible, then all the possibilities + // should themselves be Boxes. In that + // case we can merge them to figure out what the UNBOX will produce + case Possible(inners) => + assert(inners.nonEmpty, "Empty possible set indicating an uninitialized location") + val sanitized: Set[Contents] = (inners map { + case Boxed(content) => SinglePossible(content) + case _ => UNKNOWN + }) + sanitized reduce (_ merge _) + // if we have an impossible then the thing that's impossible + // should be a box. We'll unbox that to see what we get + case unknown@Impossible(inners) => + if (inners.isEmpty) { + unknown + } else { + val sanitized: Set[Contents] = (inners map { + case Boxed(content) => SingleImpossible(content) + case _ => UNKNOWN + }) + sanitized reduce (_ merge _) + } + } + dropConsumed push newValue + + case LOAD_MODULE(_) | NEW(_) | LOAD_EXCEPTION(_) => + in push NOT_NULL + + case CREATE_ARRAY(_, _) => + dropConsumed push NOT_NULL + + case IS_INSTANCE(_) => + // TODO IS_INSTANCE is going to be followed by a C(Z)JUMP + // and if IS_INSTANCE/C(Z)JUMP the branch for "true" can + // know that whatever was checked was not a null + // see the TODO on CJUMP for more information about propagating null + // information + // TODO if the top of stack is guaranteed null then we can eliminate this IS_INSTANCE check and + // replace with a constant false, but how often is a knowable null checked for instanceof? + // TODO we could track type information and statically know to eliminate IS_INSTANCE + // which might be a nice win under specialization + dropConsumed push UNKNOWN // it's actually a Possible(true, false) but since the following instruction + // will be a conditional jump comparing to true or false there + // nothing to be gained by being more precise + + case CHECK_CAST(_) => + // TODO we could track type information and statically know to eliminate CHECK_CAST + // but that's probably not a huge win + in + + case DUP(_) => + val value = in peek 0 + in push value + + case DROP(_) | MONITOR_ENTER() | MONITOR_EXIT() | STORE_ARRAY_ITEM(_) | STORE_FIELD(_, _) => + dropConsumed + + case SCOPE_ENTER(_) | SCOPE_EXIT(_) => + in + + case JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | RETURN(_) | THROW(_) | SWITCH(_, _) => + dumpClassesAndAbort("Unexpected block ending instruction: " + inst) + } + } + /** + * interpret the last instruction of a block which will be jump, a conditional branch, a throw, or a return. + * It will result in a map from target blocks to the input state computed for that block. It + * also computes a replacement list of instructions + */ + private def interpretLast(in: State, inst: Instruction): (Map[BasicBlock, State], List[Instruction]) = { + def canSwitch(in1: Contents, tagSet: List[Int]) = { + in1 mightEqual Possible(tagSet.toSet map { tag: Int => Const(Constant(tag)) }) + } + + /** + * common code for interpreting CJUMP and CZJUMP + */ + def interpretConditional(kind: TypeKind, val1: Contents, val2: Contents, success: BasicBlock, failure: BasicBlock, cond: TestOp): (Map[BasicBlock, State], List[Instruction]) = { + // TODO use reaching analysis to update the state in the two branches + // e.g. if the comparison was checking null equality on local x + // then the in the success branch we know x is null and + // on the failure branch we know it is not + // in fact, with copy propagation we could propagate that knowledge + // back through a chain of locations + // + // TODO if we do all that we need to be careful in the + // case that success and failure are the same target block + // because we're using a Map and don't want one possible state to clobber the other + // alternative mayb we should just replace the conditional with a jump if both targets are the same + + def mightEqual = val1 mightEqual val2 + def mightNotEqual = val1 mightNotEqual val2 + def guaranteedEqual = mightEqual && !mightNotEqual + + def succPossible = cond match { + case EQ => mightEqual + case NE => mightNotEqual + case LT | GT => !guaranteedEqual // if the two are guaranteed to be equal then they can't be LT/GT + case LE | GE => true + } + + def failPossible = cond match { + case EQ => mightNotEqual + case NE => mightEqual + case LT | GT => true + case LE | GE => !guaranteedEqual // if the two are guaranteed to be equal then they must be LE/GE + } + + val out = in drop inst.consumed + + var result = Map[BasicBlock, State]() + if (succPossible) { + result += ((success, out)) + } + + if (failPossible) { + result += ((failure, out)) + } + + val replacements = if (result.size == 1) List.fill(inst.consumed)(DROP(kind)) :+ JUMP(result.keySet.head) + else inst :: Nil + + (result, replacements) + } + + inst match { + case JUMP(whereto) => + (Map((whereto, in)), inst :: Nil) + + case CJUMP(success, failure, cond, kind) => + val in1 = in peek 0 + val in2 = in peek 1 + interpretConditional(kind, in1, in2, success, failure, cond) + + case CZJUMP(success, failure, cond, kind) => + val in1 = in peek 0 + val in2 = getZeroOf(kind) + interpretConditional(kind, in1, in2, success, failure, cond) + + case SWITCH(tags, labels) => + val in1 = in peek 0 + val newStuff = tags zip labels filter { case (tagSet, _) => canSwitch(in1, tagSet) } + val (reachableTags, reachableNormalLabels) = (tags zip labels filter { case (tagSet, _) => canSwitch(in1, tagSet) }).unzip + val reachableLabels = if (labels.lengthCompare(tags.length) > 0) { + // if we've got an extra label then it's the default + val defaultLabel = labels.last + // see if the default is reachable by seeing if the input might be out of the set + // of all tags + val allTags = Possible(tags.flatten.toSet map { tag: Int => Const(Constant(tag)) }) + if (in1 mightNotEqual allTags) { + reachableNormalLabels :+ defaultLabel + } else { + reachableNormalLabels + } + } else { + reachableNormalLabels + } + // TODO similar to the comment in interpretConditional, we should update our the State going into each + // branch based on which tag is being matched. Also, just like interpretConditional, if target blocks + // are the same we need to merge State rather than clobber + + // alternative, maybe we should simplify the SWITCH to not have same target labels + val newState = in drop inst.consumed + val result = Map(reachableLabels map { label => (label, newState) }: _*) + if (reachableLabels.size == 1) (result, DROP(INT) :: JUMP(reachableLabels.head) :: Nil) + else (result, inst :: Nil) + + // these instructions don't have target blocks + // (exceptions are assumed to be reachable from all instructions) + case RETURN(_) | THROW(_) => + (Map.empty, inst :: Nil) + + case _ => + dumpClassesAndAbort("Unexpected non-block ending instruction: " + inst) + } + } + + /** + * Analyze a single block to find how it transforms an input state into a states for its successor blocks + * Also computes a list of instructions to be used to replace its last instruction + */ + private def interpretBlock(in: State, block: BasicBlock): (Map[BasicBlock, State], Map[BasicBlock, State], List[Instruction]) = { + debuglog(s"interpreting block $block") + // number of instructions excluding the last one + val normalCount = block.size - 1 + + var exceptionState = in.cleanStack + var normalExitState = in + var idx = 0 + while (idx < normalCount) { + val inst = block(idx) + normalExitState = interpretInst(normalExitState, inst) + if (normalExitState.locals ne exceptionState.locals) + exceptionState.copy(locals = exceptionState mergeLocals normalExitState.locals) + idx += 1 + } + + val pairs = block.exceptionSuccessors map { b => (b, exceptionState) } + val exceptionMap = Map(pairs: _*) + + val (normalExitMap, newInstructions) = interpretLast(normalExitState, block.lastInstruction) + + (normalExitMap, exceptionMap, newInstructions) + } + + /** + * Analyze a single method to find replacement instructions + */ + private def interpretMethod(m: IMethod): Map[BasicBlock, List[Instruction]] = { + import scala.collection.mutable.{ Set => MSet, Map => MMap } + + debuglog(s"interpreting method $m") + var iterations = 0 + + // initially we know that 'this' is not null and the params are initialized to some unknown value + val initThis: Iterator[(Local, Contents)] = if (m.isStatic) Iterator.empty else Iterator.single((THIS_LOCAL, NOT_NULL)) + val initOtherLocals: Iterator[(Local, Contents)] = m.params.iterator map { param => (param, UNKNOWN) } + val initialLocals: Map[Local, Contents] = Map((initThis ++ initOtherLocals).toSeq: _*) + val initialState = State(initialLocals, Nil) + + // worklist of basic blocks to process, initially the start block + val worklist = MSet(m.startBlock) + // worklist of exception basic blocks. They're kept in a separate set so they can be + // processed after normal flow basic blocks. That's because exception basic blocks + // are more likely to have multiple predecessors and queueing them for later + // increases the chances that they'll only need to be interpreted once + val exceptionlist = MSet[BasicBlock]() + // our current best guess at what the input state is for each block + // initially we only know about the start block + val inputState = MMap[BasicBlock, State]((m.startBlock, initialState)) + + // update the inputState map based on new information from interpreting a block + // When the input state of a block changes, add it back to the work list to be + // reinterpreted + def updateInputStates(outputStates: Map[BasicBlock, State], worklist: MSet[BasicBlock]) { + for ((block, newState) <- outputStates) { + val oldState = inputState get block + val updatedState = oldState map (x => x merge newState) getOrElse newState + if (oldState != Some(updatedState)) { + worklist add block + inputState(block) = updatedState + } + } + } + + // the instructions to be used as the last instructions on each block + val replacements = MMap[BasicBlock, List[Instruction]]() + + while (worklist.nonEmpty || exceptionlist.nonEmpty) { + if (worklist.isEmpty) { + // once the worklist is empty, start processing exception blocks + val block = exceptionlist.head + exceptionlist remove block + worklist add block + } else { + iterations += 1 + val block = worklist.head + worklist remove block + val (normalExitMap, exceptionMap, newInstructions) = interpretBlock(inputState(block), block) + + updateInputStates(normalExitMap, worklist) + updateInputStates(exceptionMap, exceptionlist) + replacements(block) = newInstructions + } + } + + debuglog(s"method $m with ${m.blocks.size} reached fixpoint in $iterations iterations") + replacements.toMap + } + } +} diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index 9469113238..ee9a3aed2a 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -38,7 +38,7 @@ trait ScalaSettings extends AbsScalaSettings protected def futureSettings = List[BooleanSetting]() /** Enabled under -optimise. */ - protected def optimiseSettings = List[BooleanSetting](inline, inlineHandlers, Xcloselim, Xdce) + protected def optimiseSettings = List[BooleanSetting](inline, inlineHandlers, Xcloselim, Xdce, YconstOptimization) /** Internal use - syntax enhancements. */ private class EnableSettings[T <: BooleanSetting](val s: T) { @@ -128,6 +128,7 @@ trait ScalaSettings extends AbsScalaSettings val check = PhasesSetting ("-Ycheck", "Check the tree at the end of") val Yshow = PhasesSetting ("-Yshow", "(Requires -Xshow-class or -Xshow-object) Show after") val Xcloselim = BooleanSetting ("-Yclosure-elim", "Perform closure elimination.") + val YconstOptimization = BooleanSetting ("-Yconst-opt", "Perform optimization with constant values.") val Ycompacttrees = BooleanSetting ("-Ycompact-trees", "Use compact tree printer when displaying trees.") val noCompletion = BooleanSetting ("-Yno-completion", "Disable tab-completion in the REPL.") val Xdce = BooleanSetting ("-Ydead-code", "Perform dead code elimination.") @@ -166,7 +167,6 @@ trait ScalaSettings extends AbsScalaSettings val Yreifycopypaste = BooleanSetting ("-Yreify-copypaste", "Dump the reified trees in copypasteable representation.") val Yreplsync = BooleanSetting ("-Yrepl-sync", "Do not use asynchronous code for repl startup") val Yreploutdir = StringSetting ("-Yrepl-outdir", "path", "Write repl-generated classfiles to given output directory (use \"\" to generate a temporary dir)" , "") - val Ynotnull = BooleanSetting ("-Ynotnull", "Enable (experimental and incomplete) scala.NotNull.") val YmethodInfer = BooleanSetting ("-Yinfer-argument-types", "Infer types for arguments of overriden methods.") val etaExpandKeepsStar = BooleanSetting ("-Yeta-expand-keeps-star", "Eta-expand varargs methods to T* rather than Seq[T]. This is a temporary option to ease transition."). withDeprecationMessage("This flag is scheduled for removal in 2.12. If you have a case where you need this flag then please report a bug.") diff --git a/src/compiler/scala/tools/nsc/settings/Warnings.scala b/src/compiler/scala/tools/nsc/settings/Warnings.scala index 2649a150ad..791d44153c 100644 --- a/src/compiler/scala/tools/nsc/settings/Warnings.scala +++ b/src/compiler/scala/tools/nsc/settings/Warnings.scala @@ -19,7 +19,6 @@ trait Warnings { // present form, but have the potential to offer useful info. protected def allWarnings = lintWarnings ++ List( warnDeadCode, - warnSelectNullable, warnValueDiscard, warnNumericWiden ) @@ -46,21 +45,20 @@ trait Warnings { allWarnings foreach (_.value = true) } ) + private lazy val warnSelectNullable = BooleanSetting("-Xcheck-null", "This option is obsolete and does nothing.") // Individual warnings. - val warnSelectNullable = BooleanSetting ("-Xcheck-null", "Warn upon selection of nullable reference.") val warnAdaptedArgs = BooleanSetting ("-Ywarn-adapted-args", "Warn if an argument list is modified to match the receiver.") val warnDeadCode = BooleanSetting ("-Ywarn-dead-code", "Warn when dead code is identified.") val warnValueDiscard = BooleanSetting ("-Ywarn-value-discard", "Warn when non-Unit expression results are unused.") val warnNumericWiden = BooleanSetting ("-Ywarn-numeric-widen", "Warn when numerics are widened.") val warnNullaryUnit = BooleanSetting ("-Ywarn-nullary-unit", "Warn when nullary methods return Unit.") val warnInaccessible = BooleanSetting ("-Ywarn-inaccessible", "Warn about inaccessible types in method signatures.") - val warnNullaryOverride = BooleanSetting ("-Ywarn-nullary-override", - "Warn when non-nullary overrides nullary, e.g. `def foo()` over `def foo`.") + val warnNullaryOverride = BooleanSetting ("-Ywarn-nullary-override", "Warn when non-nullary overrides nullary, e.g. `def foo()` over `def foo`.") val warnInferAny = BooleanSetting ("-Ywarn-infer-any", "Warn when a type argument is inferred to be `Any`.") // Backward compatibility. - @deprecated("Use fatalWarnings", "2.11.0") def Xwarnfatal = fatalWarnings // used by sbt - @deprecated("Use warnSelectNullable", "2.11.0") def Xchecknull = warnSelectNullable // used by ide - @deprecated("Use warnDeadCode", "2.11.0") def Ywarndeadcode = warnDeadCode // used by ide + @deprecated("Use fatalWarnings", "2.11.0") def Xwarnfatal = fatalWarnings // used by sbt + @deprecated("This option is being removed", "2.11.0") def Xchecknull = warnSelectNullable // used by ide + @deprecated("Use warnDeadCode", "2.11.0") def Ywarndeadcode = warnDeadCode // used by ide } diff --git a/src/compiler/scala/tools/nsc/transform/Mixin.scala b/src/compiler/scala/tools/nsc/transform/Mixin.scala index 988e80aa77..f7e3310f88 100644 --- a/src/compiler/scala/tools/nsc/transform/Mixin.scala +++ b/src/compiler/scala/tools/nsc/transform/Mixin.scala @@ -1060,7 +1060,7 @@ abstract class Mixin extends InfoTransform with ast.TreeDSL { else if (needsInitFlag(sym)) mkCheckedAccessor(clazz, accessedRef, fieldOffset(sym), sym.pos, sym) else - gen.mkCheckInit(accessedRef) + accessedRef }) } else if (sym.isModule && !(sym hasFlag LIFTED | BRIDGE)) { diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index 2331f82a58..5b11adf127 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -268,7 +268,7 @@ trait Implicits { */ object Function1 { val Sym = FunctionClass(1) - def unapply(tp: Type) = tp match { + def unapply(tp: Type) = tp baseType Sym match { case TypeRef(_, Sym, arg1 :: arg2 :: _) => Some((arg1, arg2)) case _ => None } @@ -431,10 +431,8 @@ trait Implicits { val start = if (Statistics.canEnable) Statistics.startTimer(matchesPtNanos) else null val result = normSubType(tp, pt) || isView && { pt match { - case TypeRef(_, Function1.Sym, arg1 :: arg2 :: Nil) => - matchesPtView(tp, arg1, arg2, undet) - case _ => - false + case Function1(arg1, arg2) => matchesPtView(tp, arg1, arg2, undet) + case _ => false } } if (Statistics.canEnable) Statistics.stopTimer(matchesPtNanos, start) @@ -575,21 +573,21 @@ trait Implicits { ) def fail(reason: String): SearchResult = failure(itree, reason) + def fallback = typed1(itree, EXPRmode, wildPt) try { - val itree1 = - if (isView) { - val arg1 :: arg2 :: _ = pt.typeArgs + val itree1 = if (!isView) fallback else pt match { + case Function1(arg1, arg2) => typed1( atPos(itree.pos)(Apply(itree, List(Ident("<argument>") setType approximate(arg1)))), EXPRmode, approximate(arg2) ) - } - else - typed1(itree, EXPRmode, wildPt) - - if (context.hasErrors) + case _ => fallback + } + if (context.hasErrors) { + log("implicit adapt failed: " + context.errBuffer.head.errMsg) return fail(context.errBuffer.head.errMsg) + } if (Statistics.canEnable) Statistics.incCounter(typedImplicits) diff --git a/src/compiler/scala/tools/nsc/typechecker/MethodSynthesis.scala b/src/compiler/scala/tools/nsc/typechecker/MethodSynthesis.scala index 8c686107b4..5999a64b36 100644 --- a/src/compiler/scala/tools/nsc/typechecker/MethodSynthesis.scala +++ b/src/compiler/scala/tools/nsc/typechecker/MethodSynthesis.scala @@ -426,7 +426,7 @@ trait MethodSynthesis { Nil, Nil, tpt, - if (mods.isDeferred) EmptyTree else gen.mkCheckInit(fieldSelection) + if (mods.isDeferred) EmptyTree else fieldSelection ) setSymbol derivedSym } } diff --git a/src/compiler/scala/tools/nsc/typechecker/Namers.scala b/src/compiler/scala/tools/nsc/typechecker/Namers.scala index 007c7c6a83..d5da4967be 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Namers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Namers.scala @@ -805,23 +805,19 @@ trait Namers extends MethodSynthesis { case _ => false } - - val tpe1 = dropIllegalStarTypes(tpe.deconst) - val tpe2 = tpe1.widen - - // This infers Foo.type instead of "object Foo" - // See Infer#adjustTypeArgs for the polymorphic case. - if (tpe.typeSymbolDirect.isModuleClass) tpe1 - else if (sym.isVariable || sym.isMethod && !sym.hasAccessorFlag) - if (tpe2 <:< pt) tpe2 else tpe1 - else if (isHidden(tpe)) tpe2 - // In an attempt to make pattern matches involving method local vals - // compilable into switches, for a time I had a more generous condition: - // `if (sym.isFinal || sym.isLocal) tpe else tpe1` - // This led to issues with expressions like classOf[List[_]] which apparently - // depend on being deconst-ed here, so this is again the original: - else if (!sym.isFinal) tpe1 - else tpe + val shouldWiden = ( + !tpe.typeSymbolDirect.isModuleClass // Infer Foo.type instead of "object Foo" + && (tpe.widen <:< pt) // Don't widen our way out of conforming to pt + && ( sym.isVariable + || sym.isMethod && !sym.hasAccessorFlag + || isHidden(tpe) + ) + ) + dropIllegalStarTypes( + if (shouldWiden) tpe.widen + else if (sym.isFinal) tpe // "final val" allowed to retain constant type + else tpe.deconst + ) } /** Computes the type of the body in a ValDef or DefDef, and * assigns the type to the tpt's node. Returns the type. diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index 92f53f4956..765916bcdd 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -1124,16 +1124,19 @@ trait Typers extends Adaptations with Tags { else { if (mode.inExprModeButNot(FUNmode)) { pt.dealias match { - case TypeRef(_, sym, _) => + // The <: Any requirement inhibits attempts to adapt continuation types + // to non-continuation types. + case TypeRef(_, sym, _) if tree.tpe <:< AnyClass.tpe => // note: was if (pt.typeSymbol == UnitClass) but this leads to a potentially // infinite expansion if pt is constant type () - if (sym == UnitClass && tree.tpe <:< AnyClass.tpe) { // (12) + if (sym == UnitClass) { // (12) if (settings.warnValueDiscard.value) context.unit.warning(tree.pos, "discarded non-Unit value") return typedPos(tree.pos, mode, pt) { Block(List(tree), Literal(Constant())) } - } else if (isNumericValueClass(sym) && isNumericSubType(tree.tpe, pt)) { + } + else if (isNumericValueClass(sym) && isNumericSubType(tree.tpe, pt)) { if (settings.warnNumericWiden.value) context.unit.warning(tree.pos, "implicit numeric widening") return typedPos(tree.pos, mode, pt) { @@ -4184,11 +4187,11 @@ trait Typers extends Adaptations with Tags { def typedArrayValue(tree: ArrayValue) = { val elemtpt1 = typedType(tree.elemtpt, mode) - val elems1 = tree.elems mapConserve (elem => typed(elem, mode, elemtpt1.tpe)) - treeCopy.ArrayValue(tree, elemtpt1, elems1) - .setType( - (if (isFullyDefined(pt) && !phase.erasedTypes) pt - else arrayType(elemtpt1.tpe)).notNull) + val elems1 = tree.elems mapConserve (elem => typed(elem, mode, elemtpt1.tpe)) + // see run/t6126 for an example where `pt` does not suffice (tagged types) + val tpe1 = if (isFullyDefined(pt) && !phase.erasedTypes) pt else arrayType(elemtpt1.tpe) + + treeCopy.ArrayValue(tree, elemtpt1, elems1) setType tpe1 } def typedAssign(lhs: Tree, rhs: Tree): Tree = { @@ -4491,35 +4494,31 @@ trait Typers extends Adaptations with Tags { reportError } } - silent(_.typed(fun, mode.forFunMode, funpt), - if (mode.inExprMode) false else context.ambiguousErrors, - if (mode.inExprMode) tree else context.tree) match { + val silentResult = silent( + op = _.typed(fun, mode.forFunMode, funpt), + reportAmbiguousErrors = !mode.inExprMode && context.ambiguousErrors, + newtree = if (mode.inExprMode) tree else context.tree + ) + silentResult match { case SilentResultValue(fun1) => val fun2 = if (stableApplication) stabilizeFun(fun1, mode, pt) else fun1 if (Statistics.canEnable) Statistics.incCounter(typedApplyCount) - def isImplicitMethod(tpe: Type) = tpe match { - case mt: MethodType => mt.isImplicit - case _ => false - } - val useTry = ( - !isPastTyper - && fun2.isInstanceOf[Select] - && !isImplicitMethod(fun2.tpe) - && ((fun2.symbol eq null) || !fun2.symbol.isConstructor) - && (mode & (EXPRmode | SNDTRYmode)) == EXPRmode + val noSecondTry = ( + isPastTyper + || (fun2.symbol ne null) && fun2.symbol.isConstructor + || (fun2.tpe match { case mt: MethodType => mt.isImplicit case _ => false }) + ) + val isFirstTry = !noSecondTry && ( + fun2 match { + case Select(_, _) => mode inExprModeButNot SNDTRYmode + case _ => false + } ) - val res = - if (useTry) tryTypedApply(fun2, args) - else doTypedApply(tree, fun2, args, mode, pt) - - if (fun2.symbol == Array_apply && !res.isErrorTyped) { - val checked = gen.mkCheckInit(res) - // this check is needed to avoid infinite recursion in Duplicators - // (calling typed1 more than once for the same tree) - if (checked ne res) typed { atPos(tree.pos)(checked) } - else res - } else - res + if (isFirstTry) + tryTypedApply(fun2, args) + else + doTypedApply(tree, fun2, args, mode, pt) + case SilentTypeError(err) => onError({issue(err); setError(tree)}) } @@ -4735,16 +4734,6 @@ trait Typers extends Adaptations with Tags { (stabilize(treeAndPre._1, treeAndPre._2, mode, pt), None) } - def isPotentialNullDeference() = { - !isPastTyper && - !sym.isConstructor && - !(qual.tpe <:< NotNullClass.tpe) && !qual.tpe.isNotNull && - !(List(Any_isInstanceOf, Any_asInstanceOf) contains result.symbol) // null.is/as is not a dereference - } - // unit is null here sometimes; how are we to know when unit might be null? (See bug #2467.) - if (settings.warnSelectNullable.value && isPotentialNullDeference && unit != null) - unit.warning(tree.pos, "potential null pointer dereference: "+tree) - result match { // could checkAccessible (called by makeAccessible) potentially have skipped checking a type application in qual? case SelectFromTypeTree(qual@TypeTree(), name) if qual.tpe.typeArgs.nonEmpty => // TODO: somehow the new qual is not checked in refchecks diff --git a/src/library/scala/AnyVal.scala b/src/library/scala/AnyVal.scala index 0d6ba2454c..9def6cb054 100644 --- a/src/library/scala/AnyVal.scala +++ b/src/library/scala/AnyVal.scala @@ -52,6 +52,6 @@ package scala * as well as in [[http://docs.scala-lang.org/sips/pending/value-classes.html SIP-15: Value Classes]], * the Scala Improvement Proposal. */ -abstract class AnyVal extends Any with NotNull { +abstract class AnyVal extends Any { def getClass(): Class[_ <: AnyVal] = null } diff --git a/src/library/scala/NotNull.scala b/src/library/scala/NotNull.scala index f87416b49d..3cbe9ed4ac 100644 --- a/src/library/scala/NotNull.scala +++ b/src/library/scala/NotNull.scala @@ -12,4 +12,6 @@ package scala * A marker trait for things that are not allowed to be null * @since 2.5 */ + +@deprecated("This trait will be removed", "2.11.0") trait NotNull extends Any {} diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala index 37b8ecfbc4..48bccde0e8 100644 --- a/src/library/scala/collection/immutable/RedBlackTree.scala +++ b/src/library/scala/collection/immutable/RedBlackTree.scala @@ -325,54 +325,56 @@ object RedBlackTree { // whether the zipper was traversed left-most or right-most. // If the trees were balanced, returns an empty zipper - private[this] def compareDepth[A, B](left: Tree[A, B], right: Tree[A, B]): (List[Tree[A, B]], Boolean, Boolean, Int) = { + private[this] def compareDepth[A, B](left: Tree[A, B], right: Tree[A, B]): (NList[Tree[A, B]], Boolean, Boolean, Int) = { + import NList.cons // Once a side is found to be deeper, unzip it to the bottom - def unzip(zipper: List[Tree[A, B]], leftMost: Boolean): List[Tree[A, B]] = { + def unzip(zipper: NList[Tree[A, B]], leftMost: Boolean): NList[Tree[A, B]] = { val next = if (leftMost) zipper.head.left else zipper.head.right - next match { - case null => zipper - case node => unzip(node :: zipper, leftMost) - } + if (next eq null) zipper + else unzip(cons(next, zipper), leftMost) } // Unzip left tree on the rightmost side and right tree on the leftmost side until one is // found to be deeper, or the bottom is reached def unzipBoth(left: Tree[A, B], right: Tree[A, B], - leftZipper: List[Tree[A, B]], - rightZipper: List[Tree[A, B]], - smallerDepth: Int): (List[Tree[A, B]], Boolean, Boolean, Int) = { + leftZipper: NList[Tree[A, B]], + rightZipper: NList[Tree[A, B]], + smallerDepth: Int): (NList[Tree[A, B]], Boolean, Boolean, Int) = { if (isBlackTree(left) && isBlackTree(right)) { - unzipBoth(left.right, right.left, left :: leftZipper, right :: rightZipper, smallerDepth + 1) + unzipBoth(left.right, right.left, cons(left, leftZipper), cons(right, rightZipper), smallerDepth + 1) } else if (isRedTree(left) && isRedTree(right)) { - unzipBoth(left.right, right.left, left :: leftZipper, right :: rightZipper, smallerDepth) + unzipBoth(left.right, right.left, cons(left, leftZipper), cons(right, rightZipper), smallerDepth) } else if (isRedTree(right)) { - unzipBoth(left, right.left, leftZipper, right :: rightZipper, smallerDepth) + unzipBoth(left, right.left, leftZipper, cons(right, rightZipper), smallerDepth) } else if (isRedTree(left)) { - unzipBoth(left.right, right, left :: leftZipper, rightZipper, smallerDepth) + unzipBoth(left.right, right, cons(left, leftZipper), rightZipper, smallerDepth) } else if ((left eq null) && (right eq null)) { - (Nil, true, false, smallerDepth) + (null, true, false, smallerDepth) } else if ((left eq null) && isBlackTree(right)) { val leftMost = true - (unzip(right :: rightZipper, leftMost), false, leftMost, smallerDepth) + (unzip(cons(right, rightZipper), leftMost), false, leftMost, smallerDepth) } else if (isBlackTree(left) && (right eq null)) { val leftMost = false - (unzip(left :: leftZipper, leftMost), false, leftMost, smallerDepth) + (unzip(cons(left, leftZipper), leftMost), false, leftMost, smallerDepth) } else { sys.error("unmatched trees in unzip: " + left + ", " + right) } } - unzipBoth(left, right, Nil, Nil, 0) + unzipBoth(left, right, null, null, 0) } private[this] def rebalance[A, B](tree: Tree[A, B], newLeft: Tree[A, B], newRight: Tree[A, B]) = { // This is like drop(n-1), but only counting black nodes - def findDepth(zipper: List[Tree[A, B]], depth: Int): List[Tree[A, B]] = zipper match { - case head :: tail if isBlackTree(head) => - if (depth == 1) zipper else findDepth(tail, depth - 1) - case _ :: tail => findDepth(tail, depth) - case Nil => sys.error("Defect: unexpected empty zipper while computing range") - } + @tailrec + def findDepth(zipper: NList[Tree[A, B]], depth: Int): NList[Tree[A, B]] = + if (zipper eq null) { + sys.error("Defect: unexpected empty zipper while computing range") + } else if (isBlackTree(zipper.head)) { + if (depth == 1) zipper else findDepth(zipper.tail, depth - 1) + } else { + findDepth(zipper.tail, depth) + } // Blackening the smaller tree avoids balancing problems on union; // this can't be done later, though, or it would change the result of compareDepth @@ -389,7 +391,7 @@ object RedBlackTree { } else { RedTree(tree.key, tree.value, zipFrom.head, blkNewRight) } - val zippedTree = zipFrom.tail.foldLeft(union: Tree[A, B]) { (tree, node) => + val zippedTree = NList.foldLeft(zipFrom.tail, union: Tree[A, B]) { (tree, node) => if (leftMost) balanceLeft(isBlackTree(node), node.key, node.value, tree, node.right) else @@ -398,6 +400,25 @@ object RedBlackTree { zippedTree } } + + // Null optimized list implementation for tree rebalancing. null presents Nil. + private[this] final class NList[A](val head: A, val tail: NList[A]) + + private[this] final object NList { + + def cons[B](x: B, xs: NList[B]): NList[B] = new NList(x, xs) + + def foldLeft[A, B](xs: NList[A], z: B)(f: (B, A) => B): B = { + var acc = z + var these = xs + while (these ne null) { + acc = f(acc, these.head) + these = these.tail + } + acc + } + + } /* * Forcing direct fields access using the @inline annotation helps speed up diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala index 2a535a799c..397f8099eb 100644 --- a/src/library/scala/collection/mutable/BitSet.scala +++ b/src/library/scala/collection/mutable/BitSet.scala @@ -58,6 +58,11 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int] if (idx < nwords) elems(idx) else 0L private def updateWord(idx: Int, w: Long) { + ensureCapacity(idx) + elems(idx) = w + } + + private def ensureCapacity(idx: Int) { if (idx >= nwords) { var newlen = nwords while (idx >= newlen) newlen = newlen * 2 @@ -65,7 +70,6 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int] Array.copy(elems, 0, elems1, 0, nwords) elems = elems1 } - elems(idx) = w } protected def fromBitMaskNoCopy(words: Array[Long]): BitSet = new BitSet(words) @@ -92,6 +96,51 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int] def += (elem: Int): this.type = { add(elem); this } def -= (elem: Int): this.type = { remove(elem); this } + /** Updates this bitset to the union with another bitset by performing a bitwise "or". + * + * @param other the bitset to form the union with. + * @return the bitset itself. + */ + def |= (other: BitSet): this.type = { + ensureCapacity(other.nwords) + for (i <- 0 until other.nwords) + elems(i) = elems(i) | other.word(i) + this + } + /** Updates this bitset to the intersection with another bitset by performing a bitwise "and". + * + * @param other the bitset to form the intersection with. + * @return the bitset itself. + */ + def &= (other: BitSet): this.type = { + ensureCapacity(other.nwords) + for (i <- 0 until other.nwords) + elems(i) = elems(i) & other.word(i) + this + } + /** Updates this bitset to the symmetric difference with another bitset by performing a bitwise "xor". + * + * @param other the bitset to form the symmetric difference with. + * @return the bitset itself. + */ + def ^= (other: BitSet): this.type = { + ensureCapacity(other.nwords) + for (i <- 0 until other.nwords) + elems(i) = elems(i) ^ other.word(i) + this + } + /** Updates this bitset to the difference with another bitset by performing a bitwise "and-not". + * + * @param other the bitset to form the difference with. + * @return the bitset itself. + */ + def &~= (other: BitSet): this.type = { + ensureCapacity(other.nwords) + for (i <- 0 until other.nwords) + elems(i) = elems(i) & ~other.word(i) + this + } + override def clear() { elems = new Array[Long](elems.length) } diff --git a/src/reflect/scala/reflect/internal/Definitions.scala b/src/reflect/scala/reflect/internal/Definitions.scala index fe5a5c81e2..55954196f6 100644 --- a/src/reflect/scala/reflect/internal/Definitions.scala +++ b/src/reflect/scala/reflect/internal/Definitions.scala @@ -281,7 +281,7 @@ trait Definitions extends api.StandardDefinitions { def Predef_AnyRef = AnyRefModule lazy val AnyValClass: ClassSymbol = (ScalaPackageClass.info member tpnme.AnyVal orElse { - val anyval = enterNewClass(ScalaPackageClass, tpnme.AnyVal, List(AnyClass.tpe, NotNullClass.tpe), ABSTRACT) + val anyval = enterNewClass(ScalaPackageClass, tpnme.AnyVal, AnyClass.tpe :: Nil, ABSTRACT) val av_constr = anyval.newClassConstructor(NoPosition) anyval.info.decls enter av_constr anyval @@ -383,7 +383,6 @@ trait Definitions extends api.StandardDefinitions { lazy val StringAddClass = requiredClass[scala.runtime.StringAdd] lazy val ArrowAssocClass = getRequiredClass("scala.Predef.ArrowAssoc") // SI-5731 lazy val StringAdd_+ = getMemberMethod(StringAddClass, nme.PLUS) - lazy val NotNullClass = getRequiredClass("scala.NotNull") lazy val ScalaNumberClass = requiredClass[scala.math.ScalaNumber] lazy val TraitSetterAnnotationClass = requiredClass[scala.runtime.TraitSetter] lazy val DelayedInitClass = requiredClass[scala.DelayedInit] @@ -1131,7 +1130,7 @@ trait Definitions extends api.StandardDefinitions { /** Is type's symbol a numeric value class? */ def isNumericValueType(tp: Type): Boolean = tp match { case TypeRef(_, sym, _) => isNumericValueClass(sym) - case _ => false + case _ => false } // todo: reconcile with javaSignature!!! diff --git a/src/reflect/scala/reflect/internal/Importers.scala b/src/reflect/scala/reflect/internal/Importers.scala index 53410b29c5..f736202e13 100644 --- a/src/reflect/scala/reflect/internal/Importers.scala +++ b/src/reflect/scala/reflect/internal/Importers.scala @@ -248,8 +248,6 @@ trait Importers extends api.Importers { self: SymbolTable => AntiPolyType(importType(pre), targs map importType) case x: from.TypeVar => TypeVar(importType(x.origin), importTypeConstraint(x.constr), x.typeArgs map importType, x.params map importSymbol) - case from.NotNullType(tpe) => - NotNullType(importType(tpe)) case from.AnnotatedType(annots, tpe, selfsym) => AnnotatedType(annots map importAnnotationInfo, importType(tpe), importSymbol(selfsym)) case from.ErrorType => diff --git a/src/reflect/scala/reflect/internal/Symbols.scala b/src/reflect/scala/reflect/internal/Symbols.scala index 6837f37445..c881de7830 100644 --- a/src/reflect/scala/reflect/internal/Symbols.scala +++ b/src/reflect/scala/reflect/internal/Symbols.scala @@ -1671,6 +1671,19 @@ trait Symbols extends api.Symbols { self: SymbolTable => * and is this class symbol also different from Null or Nothing? */ def isNonBottomSubClass(that: Symbol): Boolean = false + /** Is this class symbol Null or Nothing, + * and (if Null) is `that` inhabited by null? + * If this is Nothing, of course, it is a + * subclass of `that` by definition. + * + * TODO - what is implied by the fact that AnyVal now has + * infinitely many non-bottom subclasses, not only 9? + */ + def isBottomSubClass(that: Symbol) = ( + (this eq NothingClass) + || (this eq NullClass) && that.isClass && (that ne NothingClass) && !(that isNonBottomSubClass AnyValClass) + ) + /** Overridden in NullClass and NothingClass for custom behavior. */ def isSubClass(that: Symbol) = isNonBottomSubClass(that) diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index e1433d1893..a678edbe01 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -131,7 +131,6 @@ trait Types override def isTrivial = underlying.isTrivial override def isHigherKinded: Boolean = underlying.isHigherKinded override def typeConstructor: Type = underlying.typeConstructor - override def isNotNull = underlying.isNotNull override def isError = underlying.isError override def isErroneous = underlying.isErroneous override def isStable: Boolean = underlying.isStable @@ -187,7 +186,6 @@ trait Types override def params: List[Symbol] = List() override def paramTypes: List[Type] = List() override def typeArgs = underlying.typeArgs - override def notNull = maybeRewrap(underlying.notNull) override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]) = underlying.instantiateTypeParams(formals, actuals) override def skolemizeExistential(owner: Symbol, origin: AnyRef) = underlying.skolemizeExistential(owner, origin) override def normalize = maybeRewrap(underlying.normalize) @@ -275,9 +273,6 @@ trait Types */ def isVolatile: Boolean = false - /** Is this type guaranteed not to have `null` as a value? */ - def isNotNull: Boolean = false - /** Is this type a structural refinement type (it ''refines'' members that have not been inherited) */ def isStructuralRefinement: Boolean = false @@ -462,13 +457,6 @@ trait Types * the empty list for all other types */ def boundSyms: immutable.Set[Symbol] = emptySymbolSet - /** Mixin a NotNull trait unless type already has one - * ...if the option is given, since it is causing typing bugs. - */ - def notNull: Type = - if (!settings.Ynotnull.value || isNotNull || phase.erasedTypes) this - else NotNullType(this) - /** Replace formal type parameter symbols with actual type arguments. * * Amounts to substitution except for higher-kinded types. (See overridden method in TypeRef) -- @M @@ -1209,17 +1197,6 @@ trait Types override def baseTypeSeq: BaseTypeSeq = supertype.baseTypeSeq override def baseTypeSeqDepth: Int = supertype.baseTypeSeqDepth override def baseClasses: List[Symbol] = supertype.baseClasses - override def isNotNull = supertype.isNotNull - } - - case class NotNullType(override val underlying: Type) extends SubType with RewrappingTypeProxy { - def supertype = underlying - protected def rewrap(newtp: Type): Type = NotNullType(newtp) - override def isNotNull: Boolean = true - override def notNull = this - override def deconst: Type = underlying //todo: needed? - override def safeToString: String = underlying.toString + " with NotNull" - override def kind = "NotNullType" } /** A base class for types that represent a single value @@ -1324,7 +1301,6 @@ trait Types } override def isTrivial: Boolean = sym.isPackageClass - override def isNotNull = true override def typeSymbol = sym override def underlying: Type = sym.typeOfThis override def isVolatile = false @@ -1363,7 +1339,6 @@ trait Types } override def isGround = sym.isPackageClass || pre.isGround - override def isNotNull = underlying.isNotNull private[reflect] var underlyingCache: Type = NoType private[reflect] var underlyingPeriod = NoPeriod override def underlying: Type = { @@ -1430,8 +1405,6 @@ trait Types if (trivial == UNKNOWN) trivial = fromBoolean(thistpe.isTrivial && supertpe.isTrivial) toBoolean(trivial) } - override def isNotNull = true - override def typeSymbol = thistpe.typeSymbol override def underlying = supertpe override def prefix: Type = supertpe.prefix @@ -1544,7 +1517,6 @@ trait Types } override def narrow: Type = typeSymbol.thisType - override def isNotNull: Boolean = parents exists typeIsNotNull override def isStructuralRefinement: Boolean = typeSymbol.isAnonOrRefinementClass && (decls exists symbolIsPossibleInRefinement) @@ -1988,8 +1960,7 @@ trait Types override def underlying: Type = value.tpe assert(underlying.typeSymbol != UnitClass) override def isTrivial: Boolean = true - override def isNotNull = value.value != null - override def deconst: Type = underlying + override def deconst: Type = underlying.deconst override def safeToString: String = underlying.toString + "(" + value.escapedStringValue + ")" override def kind = "ConstantType" @@ -2042,7 +2013,6 @@ trait Types narrowedCache } - final override def isNotNull = true override protected def finishPrefix(rest: String) = objectPrefix + rest override def directObjectString = super.safeToString override def toLongString = toString @@ -2347,9 +2317,6 @@ trait Types override def typeSymbol = sym override def typeSymbolDirect = sym - override def isNotNull = - sym.isModuleClass || sym == NothingClass || (sym isNonBottomSubClass NotNullClass) || super.isNotNull - override def parents: List[Type] = { val cache = parentsCache if (parentsPeriod == currentPeriod && cache != null) cache @@ -4084,24 +4051,22 @@ trait Types corresponds3(tps1, tps2, tparams map (_.variance))(isSubArg) } - protected[internal] def containsNull(sym: Symbol): Boolean = - sym.isClass && sym != NothingClass && - !(sym isNonBottomSubClass AnyValClass) && - !(sym isNonBottomSubClass NotNullClass) - - def specializesSym(tp: Type, sym: Symbol, depth: Int): Boolean = - tp.typeSymbol == NothingClass || - tp.typeSymbol == NullClass && containsNull(sym.owner) || { - def specializedBy(membr: Symbol): Boolean = - membr == sym || specializesSym(tp.narrow, membr, sym.owner.thisType, sym, depth) - val member = tp.nonPrivateMember(sym.name) + def specializesSym(tp: Type, sym: Symbol, depth: Int): Boolean = { + def directlySpecializedBy(member: Symbol): Boolean = ( + member == sym + || specializesSym(tp.narrow, member, sym.owner.thisType, sym, depth) + ) + // Closure reduction, else this would be simply `member exists directlySpecializedBy` + def specializedBy(member: Symbol): Boolean = ( if (member eq NoSymbol) false - else if (member.isOverloaded) member.alternatives exists specializedBy - else specializedBy(member) - // was - // (tp.nonPrivateMember(sym.name).alternatives exists - // (alt => sym == alt || specializesSym(tp.narrow, alt, sym.owner.thisType, sym, depth))) - } + else if (member.isOverloaded) member.alternatives exists directlySpecializedBy + else directlySpecializedBy(member) + ) + + ( (tp.typeSymbol isBottomSubClass sym.owner) + || specializedBy(tp nonPrivateMember sym.name) + ) + } /** Does member `sym1` of `tp1` have a stronger type * than member `sym2` of `tp2`? @@ -4514,7 +4479,6 @@ trait Types // ----- Hoisted closures and convenience methods, for compile time reductions ------- - private[scala] val typeIsNotNull = (tp: Type) => tp.isNotNull private[scala] val isTypeVar = (tp: Type) => tp.isInstanceOf[TypeVar] private[scala] val typeContainsTypeVar = (tp: Type) => tp exists isTypeVar private[scala] val typeIsNonClassType = (tp: Type) => tp.typeSymbolDirect.isNonClassType diff --git a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala index 506edb861e..e7a1ea9311 100644 --- a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala +++ b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala @@ -35,7 +35,6 @@ abstract class MutableSettings extends AbsSettings { def overrideObjects: BooleanSetting def printtypes: BooleanSetting def debug: BooleanSetting - def Ynotnull: BooleanSetting def explaintypes: BooleanSetting def verbose: BooleanSetting def uniqid: BooleanSetting diff --git a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala index bdccc75d6d..5bdc5f8a73 100644 --- a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala +++ b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala @@ -396,7 +396,7 @@ private[internal] trait GlbLubs { indent = indent stripSuffix " " println(indent + "lub of " + ts + " is " + res)//debug } - if (ts forall typeIsNotNull) res.notNull else res + res } val GlbFailure = new Throwable @@ -536,13 +536,9 @@ private[internal] trait GlbLubs { } } // if (settings.debug.value) { println(indent + "glb of " + ts + " at depth "+depth); indent = indent + " " } //DEBUG - if (Statistics.canEnable) Statistics.incCounter(nestedLubCount) - val res = glb0(ts) - + glb0(ts) // if (settings.debug.value) { indent = indent.substring(0, indent.length() - 2); log(indent + "glb of " + ts + " is " + res) }//DEBUG - - if (ts exists typeIsNotNull) res.notNull else res } /** All types in list must be polytypes with type parameter lists of diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala index 82321f61c2..d36aa0c927 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala @@ -5,6 +5,7 @@ package tpe import scala.collection.{ mutable } import Flags._ import util.Statistics +import scala.annotation.tailrec trait TypeComparers { self: SymbolTable => @@ -73,14 +74,17 @@ trait TypeComparers { // if (subsametypeRecursions == 0) undoLog.clear() } - def isDifferentTypeConstructor(tp1: Type, tp2: Type): Boolean = tp1 match { - case TypeRef(pre1, sym1, _) => - tp2 match { - case TypeRef(pre2, sym2, _) => sym1 != sym2 || isDifferentType(pre1, pre2) - case _ => true - } - case _ => true - } + def isDifferentTypeConstructor(tp1: Type, tp2: Type) = !isSameTypeConstructor(tp1, tp2) + + private def isSameTypeConstructor(tr1: TypeRef, tr2: TypeRef): Boolean = ( + (tr1.sym == tr2.sym) + && !isDifferentType(tr1.pre, tr2.pre) + ) + private def isSameTypeConstructor(tp1: Type, tp2: Type): Boolean = ( + tp1.isInstanceOf[TypeRef] + && tp2.isInstanceOf[TypeRef] + && isSameTypeConstructor(tp1.asInstanceOf[TypeRef], tp2.asInstanceOf[TypeRef]) + ) /** Do `tp1` and `tp2` denote equivalent types? */ def isSameType(tp1: Type, tp2: Type): Boolean = try { @@ -402,6 +406,9 @@ trait TypeComparers { case tr2: TypeRef => tp1 match { case tr1: TypeRef => + // TODO - dedicate a method to TypeRef/TypeRef subtyping. + // These typerefs are pattern matched up and down far more + // than is necessary. val sym1 = tr1.sym val sym2 = tr2.sym val pre1 = tr1.pre @@ -464,33 +471,25 @@ trait TypeComparers { def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = { val sym2 = tp2.sym + def retry(lhs: Type, rhs: Type) = isSubType(lhs, rhs, depth) + def abstractTypeOnRight(lo: Type) = isDifferentTypeConstructor(tp2, lo) && retry(tp1, lo) + def classOnRight = ( + if (isRawType(tp2)) retry(tp1, rawToExistential(tp2)) + else if (sym2.isRefinementClass) retry(tp1, sym2.info) + else fourthTry + ) sym2 match { - case NotNullClass => tp1.isNotNull - case SingletonClass => tp1.isStable || fourthTry - case _: ClassSymbol => - if (isRawType(tp2)) - isSubType(tp1, rawToExistential(tp2), depth) - else if (sym2.name == tpnme.REFINE_CLASS_NAME) - isSubType(tp1, sym2.info, depth) - else - fourthTry - case _: TypeSymbol => - if (sym2 hasFlag DEFERRED) { - val tp2a = tp2.bounds.lo - isDifferentTypeConstructor(tp2, tp2a) && - isSubType(tp1, tp2a, depth) || - fourthTry - } else { - isSubType(tp1.normalize, tp2.normalize, depth) - } - case _ => - fourthTry + case SingletonClass => tp1.isStable || fourthTry + case _: ClassSymbol => classOnRight + case _: TypeSymbol if sym2.isDeferred => abstractTypeOnRight(tp2.bounds.lo) || fourthTry + case _: TypeSymbol => retry(tp1.normalize, tp2.normalize) + case _ => fourthTry } } /** Third try, on the right: * - decompose refined types. - * - handle typerefs, existentials, and notnull types. + * - handle typerefs and existentials. * - handle left+right method types, polytypes, typebounds */ def thirdTry = tp2 match { @@ -501,8 +500,6 @@ trait TypeComparers { (rt2.decls forall (specializesSym(tp1, _, depth))) case et2: ExistentialType => et2.withTypeVars(isSubType(tp1, _, depth), depth) || fourthTry - case nn2: NotNullType => - tp1.isNotNull && isSubType(tp1, nn2.underlying, depth) case mt2: MethodType => tp1 match { case mt1 @ MethodType(params1, res1) => @@ -536,46 +533,39 @@ trait TypeComparers { } /** Fourth try, on the left: - * - handle typerefs, refined types, notnull and singleton types. + * - handle typerefs, refined types, and singleton types. */ - def fourthTry = tp1 match { - case tr1 @ TypeRef(pre1, sym1, _) => - sym1 match { - case NothingClass => true - case NullClass => - tp2 match { - case TypeRef(_, sym2, _) => - containsNull(sym2) - case _ => - isSingleType(tp2) && isSubType(tp1, tp2.widen, depth) - } - case _: ClassSymbol => - if (isRawType(tp1)) - isSubType(rawToExistential(tp1), tp2, depth) - else if (sym1.isModuleClass) tp2 match { - case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1.sourceModule, pre1, sym2, pre2) - case _ => false - } - else if (sym1.isRefinementClass) - isSubType(sym1.info, tp2, depth) - else false - - case _: TypeSymbol => - if (sym1 hasFlag DEFERRED) { - val tp1a = tp1.bounds.hi - isDifferentTypeConstructor(tp1, tp1a) && isSubType(tp1a, tp2, depth) - } else { - isSubType(tp1.normalize, tp2.normalize, depth) - } - case _ => - false - } - case RefinedType(parents1, _) => - parents1 exists (isSubType(_, tp2, depth)) - case _: SingletonType | _: NotNullType => - isSubType(tp1.underlying, tp2, depth) - case _ => - false + def fourthTry = { + def retry(lhs: Type, rhs: Type) = isSubType(lhs, rhs, depth) + def abstractTypeOnLeft(hi: Type) = isDifferentTypeConstructor(tp1, hi) && retry(hi, tp2) + + tp1 match { + case tr1 @ TypeRef(pre1, sym1, _) => + def nullOnLeft = tp2 match { + case TypeRef(_, sym2, _) => sym1 isBottomSubClass sym2 + case _ => isSingleType(tp2) && retry(tp1, tp2.widen) + } + def moduleOnLeft = tp2 match { + case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1.sourceModule, pre1, sym2, pre2) + case _ => false + } + def classOnLeft = ( + if (isRawType(tp1)) retry(rawToExistential(tp1), tp2) + else if (sym1.isModuleClass) moduleOnLeft + else sym1.isRefinementClass && retry(sym1.info, tp2) + ) + sym1 match { + case NothingClass => true + case NullClass => nullOnLeft + case _: ClassSymbol => classOnLeft + case _: TypeSymbol if sym1.isDeferred => abstractTypeOnLeft(tp1.bounds.hi) + case _: TypeSymbol => retry(tp1.normalize, tp2.normalize) + case _ => false + } + case RefinedType(parents, _) => parents exists (retry(_, tp2)) + case _: SingletonType => retry(tp1.underlying, tp2) + case _ => false + } } firstTry @@ -583,9 +573,9 @@ trait TypeComparers { def isWeakSubType(tp1: Type, tp2: Type) = - tp1.deconst.normalize match { + tp1.dealiasWiden match { case TypeRef(_, sym1, _) if isNumericValueClass(sym1) => - tp2.deconst.normalize match { + tp2.deconst.dealias match { case TypeRef(_, sym2, _) if isNumericValueClass(sym2) => isNumericSubClass(sym1, sym2) case tv2 @ TypeVar(_, _) => @@ -594,7 +584,7 @@ trait TypeComparers { isSubType(tp1, tp2) } case tv1 @ TypeVar(_, _) => - tp2.deconst.normalize match { + tp2.deconst.dealias match { case TypeRef(_, sym2, _) if isNumericValueClass(sym2) => tv1.registerBound(tp2, isLowerBound = false, isNumericBound = true) case _ => @@ -604,14 +594,18 @@ trait TypeComparers { isSubType(tp1, tp2) } - /** The isNumericValueType tests appear redundant, but without them - * test/continuations-neg/function3.scala goes into an infinite loop. - * (Even if the calls are to typeSymbolDirect.) - */ - def isNumericSubType(tp1: Type, tp2: Type): Boolean = ( - isNumericValueType(tp1) - && isNumericValueType(tp2) - && isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol) - ) - + def isNumericSubType(tp1: Type, tp2: Type) = ( + isNumericSubClass(primitiveBaseClass(tp1.dealiasWiden), primitiveBaseClass(tp2.dealias)) + ) + + /** If the given type has a primitive class among its base classes, + * the symbol of that class. Otherwise, NoSymbol. + */ + private def primitiveBaseClass(tp: Type): Symbol = { + @tailrec def loop(bases: List[Symbol]): Symbol = bases match { + case Nil => NoSymbol + case x :: xs => if (isPrimitiveValueClass(x)) x else loop(xs) + } + loop(tp.baseClasses) + } } diff --git a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala index 51363c0f82..d225f2f087 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala @@ -174,10 +174,6 @@ private[internal] trait TypeMaps { case tv@TypeVar(_, constr) => if (constr.instValid) this(constr.inst) else tv.applyArgs(mapOverArgs(tv.typeArgs, tv.params)) //@M !args.isEmpty implies !typeParams.isEmpty - case NotNullType(tp) => - val tp1 = this(tp) - if (tp1 eq tp) tp - else NotNullType(tp1) case AnnotatedType(annots, atp, selfsym) => val annots1 = mapOverAnnotations(annots) val atp1 = this(atp) @@ -1135,7 +1131,6 @@ private[internal] trait TypeMaps { case TypeBounds(_, _) => mapOver(tp) case TypeVar(_, _) => mapOver(tp) case AnnotatedType(_,_,_) => mapOver(tp) - case NotNullType(_) => mapOver(tp) case ExistentialType(_, _) => mapOver(tp) case _ => tp } diff --git a/src/reflect/scala/reflect/internal/transform/Erasure.scala b/src/reflect/scala/reflect/internal/transform/Erasure.scala index d83b4d71d9..b8a8e4d0c0 100644 --- a/src/reflect/scala/reflect/internal/transform/Erasure.scala +++ b/src/reflect/scala/reflect/internal/transform/Erasure.scala @@ -125,7 +125,7 @@ trait Erasure { if (unboundedGenericArrayLevel(tp) == 1) ObjectClass.tpe else if (args.head.typeSymbol.isBottomClass) ObjectArray else typeRef(apply(pre), sym, args map applyInArray) - else if (sym == AnyClass || sym == AnyValClass || sym == SingletonClass || sym == NotNullClass) ErasedObject + else if (sym == AnyClass || sym == AnyValClass || sym == SingletonClass) ErasedObject else if (sym == UnitClass) erasedTypeRef(BoxedUnitClass) else if (sym.isRefinementClass) apply(mergeParents(tp.parents)) else if (sym.isDerivedValueClass) eraseDerivedValueClassRef(tref) diff --git a/src/reflect/scala/reflect/runtime/Settings.scala b/src/reflect/scala/reflect/runtime/Settings.scala index 5d58fa96d6..6714bae1e0 100644 --- a/src/reflect/scala/reflect/runtime/Settings.scala +++ b/src/reflect/scala/reflect/runtime/Settings.scala @@ -33,7 +33,6 @@ private[reflect] class Settings extends MutableSettings { val XfullLubs = new BooleanSetting(false) val XnoPatmatAnalysis = new BooleanSetting(false) val Xprintpos = new BooleanSetting(false) - val Ynotnull = new BooleanSetting(false) val Yshowsymkinds = new BooleanSetting(false) val Yposdebug = new BooleanSetting(false) val Yrangepos = new BooleanSetting(false) diff --git a/test/files/jvm/constant-optimization/Foo_1.flags b/test/files/jvm/constant-optimization/Foo_1.flags new file mode 100644 index 0000000000..86f52af447 --- /dev/null +++ b/test/files/jvm/constant-optimization/Foo_1.flags @@ -0,0 +1 @@ +-Ynooptimise -Yconst-opt
\ No newline at end of file diff --git a/test/files/jvm/constant-optimization/Foo_1.scala b/test/files/jvm/constant-optimization/Foo_1.scala new file mode 100644 index 0000000000..cb67ad4e90 --- /dev/null +++ b/test/files/jvm/constant-optimization/Foo_1.scala @@ -0,0 +1,9 @@ +class Foo_1 { + def foo() { + // constant optimization should eliminate all branches + val i = 1 + val x = if (i != 1) null else "good" + val y = if (x == null) "good" else x + "" + println(y) + } +}
\ No newline at end of file diff --git a/test/files/jvm/constant-optimization/Test.scala b/test/files/jvm/constant-optimization/Test.scala new file mode 100644 index 0000000000..283aa6f47a --- /dev/null +++ b/test/files/jvm/constant-optimization/Test.scala @@ -0,0 +1,27 @@ + +import scala.tools.partest.BytecodeTest +import scala.tools.asm +import asm.tree.InsnList +import scala.collection.JavaConverters._ + +object Test extends BytecodeTest { + val comparisons = Set(asm.Opcodes.IF_ACMPEQ, asm.Opcodes.IF_ACMPNE, asm.Opcodes.IF_ICMPEQ, asm.Opcodes.IF_ICMPGE, asm.Opcodes.IF_ICMPGT, asm.Opcodes.IF_ICMPLE, + asm.Opcodes.IF_ICMPLT, asm.Opcodes.IF_ICMPNE, asm.Opcodes.IFEQ, asm.Opcodes.IFGE, asm.Opcodes.IFGT, asm.Opcodes.IFLE, asm.Opcodes.IFLT, + asm.Opcodes.IFNE, asm.Opcodes.IFNONNULL, asm.Opcodes.IFNULL) + + def show: Unit = { + val classNode = loadClassNode("Foo_1") + val methodNode = getMethod(classNode, "foo") + // after optimization there should be no comparisons left + val expected = 0 + + val got = countComparisons(methodNode.instructions) + assert(got == expected, s"expected $expected but got $got comparisons") + } + + def countComparisons(insnList: InsnList): Int = { + def isComparison(node: asm.tree.AbstractInsnNode): Boolean = + (comparisons contains node.getOpcode) + insnList.iterator.asScala count isComparison + } +}
\ No newline at end of file diff --git a/test/files/neg/t0764.scala b/test/files/neg/t0764.scala index 9aebe04b79..f2cc65cf7d 100644 --- a/test/files/neg/t0764.scala +++ b/test/files/neg/t0764.scala @@ -2,13 +2,13 @@ class Top[A] { type AType = A } -trait Node extends NotNull { outer => +trait Node { outer => type T <: Node def prepend = new Node { type T = outer.type } } class Main[NextType <: Node](value: Node { type T = NextType }) extends Top[Node { type T = NextType }] { - + new Main[AType]( (value: AType).prepend ) } diff --git a/test/files/neg/t3977.check b/test/files/neg/t3977.check index 9da118ee91..72335a0926 100644 --- a/test/files/neg/t3977.check +++ b/test/files/neg/t3977.check @@ -1,4 +1,4 @@ t3977.scala:12: error: could not find implicit value for parameter w: False#If[E] - new NotNull + new NoNull ^ one error found diff --git a/test/files/neg/t3977.scala b/test/files/neg/t3977.scala index f55a832c52..11a8cdba4b 100644 --- a/test/files/neg/t3977.scala +++ b/test/files/neg/t3977.scala @@ -7,7 +7,7 @@ trait False extends Bool { } class Field[E, N <: Bool](implicit val w: N#If[E]) { - type NotNull = Field[E, False] + type NoNull = Field[E, False] - new NotNull -}
\ No newline at end of file + new NoNull +} diff --git a/test/files/neg/t6446-additional.check b/test/files/neg/t6446-additional.check index 53dd383941..24201c07c2 100755 --- a/test/files/neg/t6446-additional.check +++ b/test/files/neg/t6446-additional.check @@ -25,7 +25,8 @@ superaccessors 6 add super accessors in traits and nested classes inliner 23 optimization: do inlining inlinehandlers 24 optimization: inline exception handlers closelim 25 optimization: eliminate uncalled closures - dce 26 optimization: eliminate dead code - jvm 27 generate JVM bytecode - ploogin 28 A sample phase that does so many things it's kind of hard... - terminal 29 The last phase in the compiler chain + constopt 26 optimization: optimize null and other constants + dce 27 optimization: eliminate dead code + jvm 28 generate JVM bytecode + ploogin 29 A sample phase that does so many things it's kind of hard... + terminal 30 The last phase in the compiler chain diff --git a/test/files/neg/t6446-missing.check b/test/files/neg/t6446-missing.check index f976bf480e..6e5bdcf07c 100755 --- a/test/files/neg/t6446-missing.check +++ b/test/files/neg/t6446-missing.check @@ -26,6 +26,7 @@ superaccessors 6 add super accessors in traits and nested classes inliner 23 optimization: do inlining inlinehandlers 24 optimization: inline exception handlers closelim 25 optimization: eliminate uncalled closures - dce 26 optimization: eliminate dead code - jvm 27 generate JVM bytecode - terminal 28 The last phase in the compiler chain + constopt 26 optimization: optimize null and other constants + dce 27 optimization: eliminate dead code + jvm 28 generate JVM bytecode + terminal 29 The last phase in the compiler chain diff --git a/test/files/neg/t6446-show-phases.check b/test/files/neg/t6446-show-phases.check index 5bbe43990c..a1bf408506 100644 --- a/test/files/neg/t6446-show-phases.check +++ b/test/files/neg/t6446-show-phases.check @@ -25,6 +25,7 @@ superaccessors 6 add super accessors in traits and nested classes inliner 23 optimization: do inlining inlinehandlers 24 optimization: inline exception handlers closelim 25 optimization: eliminate uncalled closures - dce 26 optimization: eliminate dead code - jvm 27 generate JVM bytecode - terminal 28 The last phase in the compiler chain + constopt 26 optimization: optimize null and other constants + dce 27 optimization: eliminate dead code + jvm 28 generate JVM bytecode + terminal 29 The last phase in the compiler chain diff --git a/test/files/pos/switch-small.flags b/test/files/pos/switch-small.flags new file mode 100644 index 0000000000..85d8eb2ba2 --- /dev/null +++ b/test/files/pos/switch-small.flags @@ -0,0 +1 @@ +-Xfatal-warnings diff --git a/test/files/pos/t3108.scala b/test/files/pos/t3108.scala deleted file mode 100644 index 6a1da73220..0000000000 --- a/test/files/pos/t3108.scala +++ /dev/null @@ -1,5 +0,0 @@ -object A { - val a: NotNull = "" - val b: NotNull = 41 -} - diff --git a/test/files/pos/t3417.scala b/test/files/pos/t3417.scala deleted file mode 100644 index d2de1608aa..0000000000 --- a/test/files/pos/t3417.scala +++ /dev/null @@ -1,11 +0,0 @@ -trait X extends NotNull { - def foo = 1 -} - -trait Y extends Object with NotNull { - def bar = 1 -} - -class Z extends NotNull - -class W extends Object with NotNull diff --git a/test/files/pos/t7228.scala b/test/files/pos/t7228.scala new file mode 100644 index 0000000000..5d936f6529 --- /dev/null +++ b/test/files/pos/t7228.scala @@ -0,0 +1,75 @@ +object AdaptWithWeaklyConformantType { + implicit class D(d: Double) { def double = d*2 } + + val x1: Int = 1 + var x2: Int = 2 + val x3 = 3 + var x4 = 4 + final val x5 = 5 + final var x6 = 6 + + def f1 = x1.double + def f2 = x2.double + def f3 = x3.double + def f4 = x4.double + def f5 = x5.double + def f6 = x6.double +} + +object AdaptAliasWithWeaklyConformantType { + implicit class D(d: Double) { def double = d*2 } + type T = Int + + val x1: T = 1 + var x2: T = 2 + val x3 = (3: T) + var x4 = (4: T) + final val x5 = (5: T) + final var x6 = (6: T) + + def f1 = x1.double + def f2 = x2.double + def f3 = x3.double + def f4 = x4.double + def f5 = x5.double + def f6 = x6.double +} + +object AdaptToAliasWithWeaklyConformantType { + type U = Double + implicit class D(d: U) { def double = d*2 } + + val x1: Int = 1 + var x2: Int = 2 + val x3 = (3: Int) + var x4 = (4: Int) + final val x5 = (5: Int) + final var x6 = (6: Int) + + def f1 = x1.double + def f2 = x2.double + def f3 = x3.double + def f4 = x4.double + def f5 = x5.double + def f6 = x6.double +} + +object AdaptAliasToAliasWithWeaklyConformantType { + type U = Double + type T = Int + implicit class D(d: U) { def double = d*2 } + + val x1: T = 1 + var x2: T = 2 + val x3 = (3: T) + var x4 = (4: T) + final val x5 = (5: T) + final var x6 = (6: T) + + def f1 = x1.double + def f2 = x2.double + def f3 = x3.double + def f4 = x4.double + def f5 = x5.double + def f6 = x6.double +} diff --git a/test/files/run/bitsets.check b/test/files/run/bitsets.check index 3f01d2a400..41c2ccdcb8 100644 --- a/test/files/run/bitsets.check +++ b/test/files/run/bitsets.check @@ -37,6 +37,11 @@ m2_r1 = true m2_r2 = true m2_r3 = true +b1:BitSet(5, 6, 7) +b2:BitSet(5) +b3:BitSet(5, 7) +b4:BitSet(7) +b0:BitSet(5, 6, 7) is0 = BitSet() is1 = BitSet() is2 = BitSet(2) diff --git a/test/files/run/bitsets.scala b/test/files/run/bitsets.scala index bdeb1fd811..0ea43fcb95 100644 --- a/test/files/run/bitsets.scala +++ b/test/files/run/bitsets.scala @@ -81,6 +81,27 @@ object TestMutable2 { println } +object TestMutable3 { + import scala.collection.mutable.BitSet + + val b0 = BitSet(5, 6) + val b1 = BitSet(7) + val b2 = BitSet(1, 5) + val b3 = BitSet(6, 7) + val b4 = BitSet(6, 7) + + b1 |= b0 + println(s"b1:$b1") + b2 &= b0 + println(s"b2:$b2") + b3 ^= b0 + println(s"b3:$b3") + b4 &~= b0 + println(s"b4:$b4") + b0 ^= b0 |= b1 + println(s"b0:$b0") +} + object TestImmutable { import scala.collection.immutable.BitSet @@ -155,6 +176,7 @@ object TestImmutable2 { object Test extends App { TestMutable TestMutable2 + TestMutable3 TestImmutable TestImmutable2 } diff --git a/test/files/run/blame_eye_triple_eee.check b/test/files/run/blame_eye_triple_eee.check new file mode 100644 index 0000000000..5e46d91a8f --- /dev/null +++ b/test/files/run/blame_eye_triple_eee.check @@ -0,0 +1,9 @@ +if (NaN == NaN) is good +if (x == x) is good +if (x == NaN) is good +if (NaN != NaN) is good +if (x != x) is good +if (NaN != x) is good +x matching was good +NaN matching was good +loop with NaN was goood diff --git a/test/files/run/blame_eye_triple_eee.flags b/test/files/run/blame_eye_triple_eee.flags new file mode 100644 index 0000000000..c9b68d70dc --- /dev/null +++ b/test/files/run/blame_eye_triple_eee.flags @@ -0,0 +1 @@ +-optimise diff --git a/test/files/run/blame_eye_triple_eee.scala b/test/files/run/blame_eye_triple_eee.scala new file mode 100644 index 0000000000..1640aead40 --- /dev/null +++ b/test/files/run/blame_eye_triple_eee.scala @@ -0,0 +1,61 @@ +object Test extends App { + import Double.NaN + + // NaN must not equal NaN no matter what optimizations are applied + // All the following will seem redundant, but to an optimizer + // they can appear different + + val x = NaN + + if (NaN == NaN) + println("if (NaN == NaN) is broken") + else + println("if (NaN == NaN) is good") + + if (x == x) + println("if (x == x) is broken") + else + println("if (x == x) is good") + + if (x == NaN) + println("if (x == NaN) is broken") + else + println("if (x == NaN) is good") + + if (NaN != NaN) + println("if (NaN != NaN) is good") + else + println("if (NaN != NaN) broken") + + if (x != x) + println("if (x != x) is good") + else + println("if (x != x) broken") + + if (NaN != x) + println("if (NaN != x) is good") + else + println("if (NaN != x) is broken") + + x match { + case 0.0d => println("x matched 0!") + case NaN => println("x matched NaN!") + case _ => println("x matching was good") + } + + NaN match { + case 0.0d => println("NaN matched 0!") + case NaN => println("NaN matched NaN!") + case _ => println("NaN matching was good") + } + + var z = 0.0d + var i = 0 + while (i < 10) { + if (i % 2 == 0) z = NaN + else z = NaN + i += 1 + } + if (z.isNaN && i == 10) println("loop with NaN was goood") + else println("loop with NaN was broken") +} diff --git a/test/files/run/constant-optimization.check b/test/files/run/constant-optimization.check new file mode 100644 index 0000000000..957ffc5a87 --- /dev/null +++ b/test/files/run/constant-optimization.check @@ -0,0 +1,5 @@ +testBothReachable: good +testOneReachable: good +testAllReachable: good +testOneUnreachable: good +testDefaultUnreachable: good diff --git a/test/files/run/constant-optimization.flags b/test/files/run/constant-optimization.flags new file mode 100644 index 0000000000..c9b68d70dc --- /dev/null +++ b/test/files/run/constant-optimization.flags @@ -0,0 +1 @@ +-optimise diff --git a/test/files/run/constant-optimization.scala b/test/files/run/constant-optimization.scala new file mode 100644 index 0000000000..5d13272f3b --- /dev/null +++ b/test/files/run/constant-optimization.scala @@ -0,0 +1,61 @@ +object Test extends App { + def testBothReachable() { + val i = util.Random.nextInt + val x = if (i % 2 == 0) null else "good" + val y = if (x == null) "good" else x + "" + println(s"testBothReachable: $y") + } + + def testOneReachable() { + val i = 1 + val x = if (i != 1) null else "good" + val y = if (x == null) "good" else x + "" + println(s"testOneReachable: $y") + } + + def testAllReachable() { + val i = util.Random.nextInt + val y = (i % 2) match { + case 0 => "good" + case 1 => "good" + case _ => "good" + } + println(s"testAllReachable: $y") + } + + def testOneUnreachable() { + val i = util.Random.nextInt + val x = if (i % 2 == 0) { + 1 + } else { + 2 + } + val y = x match { + case 0 => "good" + case 1 => "good" + case _ => "good" + } + println(s"testOneUnreachable: $y") + } + + def testDefaultUnreachable() { + val i = util.Random.nextInt + val x = if (i % 2 == 0) { + 1 + } else { + 2 + } + val y = x match { + case 1 => "good" + case 2 => "good" + case _ => "good" + } + println(s"testDefaultUnreachable: $y") + } + + testBothReachable() + testOneReachable() + testAllReachable() + testOneUnreachable() + testDefaultUnreachable() +} diff --git a/test/files/run/programmatic-main.check b/test/files/run/programmatic-main.check index d472c569d2..61b947214c 100644 --- a/test/files/run/programmatic-main.check +++ b/test/files/run/programmatic-main.check @@ -25,7 +25,8 @@ superaccessors 6 add super accessors in traits and nested classes inliner 23 optimization: do inlining inlinehandlers 24 optimization: inline exception handlers closelim 25 optimization: eliminate uncalled closures - dce 26 optimization: eliminate dead code - jvm 27 generate JVM bytecode - terminal 28 The last phase in the compiler chain + constopt 26 optimization: optimize null and other constants + dce 27 optimization: eliminate dead code + jvm 28 generate JVM bytecode + terminal 29 The last phase in the compiler chain diff --git a/test/files/run/t6646.check b/test/files/run/t6646.check index b0b7ad32f3..15715dae91 100644 --- a/test/files/run/t6646.check +++ b/test/files/run/t6646.check @@ -1,4 +1,4 @@ -Found NotNull +Found NoNull Found lower Found 2 A single ident is always a pattern diff --git a/test/files/run/t6646.scala b/test/files/run/t6646.scala index 150b0df11e..a377ac274e 100644 --- a/test/files/run/t6646.scala +++ b/test/files/run/t6646.scala @@ -1,14 +1,14 @@ sealed trait ColumnOption -case object NotNull extends ColumnOption +case object NoNull extends ColumnOption case object PrimaryKey extends ColumnOption case object lower extends ColumnOption object Test { def main(args: Array[String]) { - val l = List(PrimaryKey, NotNull, lower) + val l = List(PrimaryKey, NoNull, lower) // withFilter must be generated in these - for (option @ NotNull <- l) println("Found " + option) + for (option @ NoNull <- l) println("Found " + option) for (option @ `lower` <- l) println("Found " + option) for ((`lower`, i) <- l.zipWithIndex) println("Found " + i) diff --git a/test/pending/pos/no-widen-locals.flags b/test/pending/pos/no-widen-locals.flags new file mode 100644 index 0000000000..85d8eb2ba2 --- /dev/null +++ b/test/pending/pos/no-widen-locals.flags @@ -0,0 +1 @@ +-Xfatal-warnings diff --git a/test/files/pos/no-widen-locals.scala b/test/pending/pos/no-widen-locals.scala index 013e63f0a2..013e63f0a2 100644 --- a/test/files/pos/no-widen-locals.scala +++ b/test/pending/pos/no-widen-locals.scala |