(1) add devirtualization phase.

15 files changed, 571 insertions, 65 deletions

diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
index 8e82d056ed..1125cd6f4c 100644
--- a/src/compiler/scala/tools/nsc/Global.scala
+++ b/src/compiler/scala/tools/nsc/Global.scala
@@ -282,6 +282,10 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
     val global: Global.this.type = Global.this
   }
 
+  object devirtualize extends DeVirtualize {
+    val global: Global.this.type = Global.this
+  }
+
   object refchecks extends RefChecks {
     val global: Global.this.type = Global.this
   }
@@ -391,7 +395,8 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
     analyzer.namerFactory: SubComponent, // note: types are there because otherwise
     analyzer.typerFactory: SubComponent, // consistency check after refchecks would fail.
     superAccessors,  // add super accessors
-    pickler,         // serializes symbol tables
+    pickler,         // serialize symbol tables
+    devirtualize,    // expand virtual classes
     refchecks       // perform reference and override checking, translate nested objects
   ) ::: (
     if (forJVM) List(liftcode) else List()  // generate reified trees
@@ -501,6 +506,7 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
 
     val namerPhase = phaseNamed("namer")
     val typerPhase = phaseNamed("typer")
+    val picklerPhase = phaseNamed("pickler")
     val refchecksPhase = phaseNamed("refchecks")
 
     val explicitOuterPhase = phaseNamed("explicitouter")
diff --git a/src/compiler/scala/tools/nsc/SubComponent.scala b/src/compiler/scala/tools/nsc/SubComponent.scala
index e683e7072d..5f879a550c 100644
--- a/src/compiler/scala/tools/nsc/SubComponent.scala
+++ b/src/compiler/scala/tools/nsc/SubComponent.scala
@@ -24,6 +24,18 @@ abstract class SubComponent {
   /** The phase factory */
   def newPhase(prev: Phase): Phase
 
+  private var ownPhaseCache: Phase = _
+  private var ownPhaseRunId = global.NoRunId
+
+  /** The phase corresponding to this subcomponent in the current compiler run */
+  def ownPhase: Phase = {
+    if (ownPhaseRunId != global.currentRunId) {
+      ownPhaseCache = global.currentRun.phaseNamed(phaseName)
+      ownPhaseRunId = global.currentRunId
+    }
+    ownPhaseCache
+  }
+
   /** The phase defined by this subcomponent. Can be called only after phase is installed by newPhase. */
 //  lazy val ownPhase: Phase = global.currentRun.phaseNamed(phaseName)
 
diff --git a/src/compiler/scala/tools/nsc/ast/TreeBrowsers.scala b/src/compiler/scala/tools/nsc/ast/TreeBrowsers.scala
index 42e6b641f2..69b691c7ae 100644
--- a/src/compiler/scala/tools/nsc/ast/TreeBrowsers.scala
+++ b/src/compiler/scala/tools/nsc/ast/TreeBrowsers.scala
@@ -572,8 +572,7 @@ abstract class TreeBrowsers {
 
       if (s ne null) {
         var str = flagsToString(s.flags)
-        if (s.hasFlag(STATIC) || s.hasFlag(STATICMEMBER))
-          str = str + " isStatic ";
+        if (s.isStaticMember) str = str + " isStatic ";
         str
       }
       else ""
diff --git a/src/compiler/scala/tools/nsc/ast/Trees.scala b/src/compiler/scala/tools/nsc/ast/Trees.scala
index d9f6220433..970aa33a9a 100644
--- a/src/compiler/scala/tools/nsc/ast/Trees.scala
+++ b/src/compiler/scala/tools/nsc/ast/Trees.scala
@@ -335,12 +335,13 @@ trait Trees {
   /** Construct class definition with given class symbol, value parameters,
    *  supercall arguments and template body.
    *
-   *  @param sym       the class symbol
-   *  @param vparamss  the value parameters -- if they have symbols they
-   *                   should be owned by `sym'
-   *  @param argss     the supercall arguments
-   *  @param body      the template statements without primary constructor
-   *                   and value parameter fields.
+   *  @param sym        the class symbol
+   *  @param constrMods the modifiers for the class constructor, i.e. as in `class C private (...)'
+   *  @param vparamss   the value parameters -- if they have symbols they
+   *                    should be owned by `sym'
+   *  @param argss      the supercall arguments
+   *  @param body       the template statements without primary constructor
+   *                    and value parameter fields.
    *  @return          ...
    */
   def ClassDef(sym: Symbol, constrMods: Modifiers, vparamss: List[List[ValDef]], argss: List[List[Tree]], body: List[Tree]): ClassDef =
diff --git a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
index 8c2c0685ab..c24a43f5d9 100644
--- a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
+++ b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
@@ -2250,13 +2250,15 @@ trait Parsers extends NewScanners with MarkupParsers {
     def isInterface(mods: Modifiers, body: List[Tree]) =
       (mods.hasFlag(Flags.TRAIT) && (body forall treeInfo.isInterfaceMember))
 
-    /** ClassTemplateOpt ::= extends ClassTemplate | [[extends] TemplateBody]
-     *  TraitTemplateOpt ::= extends TraitTemplate | [[extends] TemplateBody]
+    /** ClassTemplateOpt ::= Extends ClassTemplate | [[Extends] TemplateBody]
+     *  TraitTemplateOpt ::= Extends TraitTemplate | [[Extends] TemplateBody]
+     *  Extends          ::= extends | `<:'
      */
-    def templateOpt(mods: Modifiers, name: Name, constrMods: Modifiers, vparamss: List[List[ValDef]]): Template = {
+    def templateOpt(mods0: Modifiers, name: Name, constrMods: Modifiers, vparamss: List[List[ValDef]]): Template = {
+      val mods = if (inToken == SUBTYPE) mods0 | ABSTRACT else mods0
       val pos = inCurrentPos;
       val (parents0, argss, self, body) =
-        if (inToken == EXTENDS) {
+        if (inToken == EXTENDS || inToken == SUBTYPE) {
           inNextToken
           template(mods hasFlag Flags.TRAIT)
         } else {
diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
index 41961d5a0c..0294ffeaf7 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
@@ -161,7 +161,7 @@ abstract class GenICode extends SubComponent  {
 
       tree match {
         case Assign(lhs @ Select(_, _), rhs) =>
-          if (isStaticSymbol(lhs.symbol)) {
+          if (lhs.symbol.isStaticMember) {
             val ctx1 = genLoad(rhs, ctx, toTypeKind(lhs.symbol.info))
             ctx1.bb.emit(STORE_FIELD(lhs.symbol, true), tree.pos)
             ctx1
@@ -809,9 +809,9 @@ abstract class GenICode extends SubComponent  {
             ctx1
           } else {  // normal method call
             if (settings.debug.value)
-              log("Gen CALL_METHOD with sym: " + sym + " isStaticSymbol: " + isStaticSymbol(sym));
+              log("Gen CALL_METHOD with sym: " + sym + " isStaticSymbol: " + sym.isStaticMember);
             var invokeStyle =
-              if (isStaticSymbol(sym))
+              if (sym.isStaticMember)
                 Static(false)
               else if (sym.hasFlag(Flags.PRIVATE) || sym.isClassConstructor)
                 Static(true)
@@ -883,7 +883,7 @@ abstract class GenICode extends SubComponent  {
             assert(!tree.symbol.isPackageClass, "Cannot use package as value: " + tree)
             ctx.bb.emit(LOAD_MODULE(sym), tree.pos);
             ctx
-          } else if (isStaticSymbol(sym)) {
+          } else if (sym.isStaticMember) {
             ctx.bb.emit(LOAD_FIELD(sym, true), tree.pos)
             ctx
           } else {
@@ -1057,10 +1057,6 @@ abstract class GenICode extends SubComponent  {
           abort("Unknown qualifier " + tree)
       }
 
-    /** Is this symbol static in the Java sense? */
-    def isStaticSymbol(s: Symbol): Boolean =
-      s.hasFlag(Flags.STATIC) || s.hasFlag(Flags.STATICMEMBER) || s.owner.isImplClass
-
     /**
      * Generate code that loads args into label parameters.
      */
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
index 15f5d434f0..5dcebe7ecf 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
@@ -220,8 +220,7 @@ trait Members { self: ICodes =>
       native
     );
 
-    def isStatic: Boolean =
-      symbol.hasFlag(Flags.STATIC) || symbol.hasFlag(Flags.STATICMEMBER) || symbol.owner.isImplClass;
+    def isStatic: Boolean = symbol.isStaticMember
 
     override def toString() = symbol.fullNameString
 
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
index bfa35a1550..0813bd88ce 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
@@ -454,7 +454,7 @@ abstract class GenJVM extends SubComponent {
     }
 
     def isTopLevelModule(sym: Symbol): Boolean =
-      atPhase (currentRun.refchecksPhase) {
+      atPhase (currentRun.picklerPhase.next) {
         sym.isModuleClass && !sym.isImplClass && !sym.isNestedClass
       }
 
@@ -628,7 +628,7 @@ abstract class GenJVM extends SubComponent {
                                            clasz.cunit.source.toString)
       for (val m <- clasz.symbol.tpe.nonPrivateMembers;
            m.owner != definitions.ObjectClass && !m.hasFlag(Flags.PROTECTED) &&
-           m.isMethod && !m.hasFlag(Flags.CASE) && !m.isConstructor && !isStaticSymbol(m) &&
+           m.isMethod && !m.hasFlag(Flags.CASE) && !m.isConstructor && !m.isStaticMember &&
            !definitions.ObjectClass.info.nonPrivateMembers.exists(_.name == m.name))
       {
         val paramJavaTypes = m.tpe.paramTypes map (t => toTypeKind(t));
@@ -1379,7 +1379,7 @@ abstract class GenJVM extends SubComponent {
      */
     def computeLocalVarsIndex(m: IMethod) {
       var idx = 1
-      if (isStaticSymbol(m.symbol))
+      if (m.symbol.isStaticMember)
         idx = 0;
 
       for (l <- m.locals) {
@@ -1467,7 +1467,7 @@ abstract class GenJVM extends SubComponent {
       jf = jf | (if ((sym hasFlag Flags.FINAL)
                        && !sym.enclClass.hasFlag(Flags.INTERFACE)
                        && !sym.isClassConstructor) ACC_FINAL else 0)
-      jf = jf | (if (isStaticSymbol(sym)) ACC_STATIC else 0)
+      jf = jf | (if (sym.isStaticMember) ACC_STATIC else 0)
       if (settings.target.value == "jvm-1.5")
         jf = jf | (if (sym hasFlag Flags.BRIDGE) ACC_BRIDGE else 0)
       if (sym.isClass && !sym.hasFlag(Flags.INTERFACE))
@@ -1475,9 +1475,6 @@ abstract class GenJVM extends SubComponent {
       jf
     }
 
-    def isStaticSymbol(s: Symbol): Boolean =
-      s.hasFlag(Flags.STATIC) || s.hasFlag(Flags.STATICMEMBER) || s.owner.isImplClass;
-
     /** Calls to methods in 'sym' need invokeinterface? */
     def needsInterfaceCall(sym: Symbol): Boolean =
       sym.hasFlag(Flags.INTERFACE) ||
diff --git a/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala b/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala
index 23cc7b94e1..512531d8f1 100644
--- a/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala
+++ b/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala
@@ -1800,7 +1800,7 @@ abstract class GenMSIL extends SubComponent {
     def computeLocalVarsIndex(m: IMethod) {
       val params = m.params
       var idx = 1
-      if (isStaticSymbol(m.symbol))
+      if (m.symbol.isStaticMember)
         idx = 0
 
       for (l <- params) {
@@ -1884,7 +1884,7 @@ abstract class GenMSIL extends SubComponent {
          else MethodAttributes.Public)
 
       if (!sym.isClassConstructor) {
-        if (isStaticSymbol(sym))
+        if (sym.isStaticMember)
           mf = mf | FieldAttributes.Static
         else {
           mf = mf | MethodAttributes.Virtual
@@ -1907,7 +1907,7 @@ abstract class GenMSIL extends SubComponent {
       if (sym hasFlag Flags.FINAL)
         mf = mf | FieldAttributes.InitOnly
 
-      if (isStaticSymbol(sym))
+      if (sym.isStaticMember)
         mf = mf | FieldAttributes.Static
 
       // TRANSIENT: "not nerialized", VOLATILE: doesn't exist on .net
@@ -1922,11 +1922,6 @@ abstract class GenMSIL extends SubComponent {
       mf.toShort
     }
 
-
-    def isStaticSymbol(s: Symbol): Boolean =
-      s.hasFlag(Flags.STATIC) || s.hasFlag(Flags.STATICMEMBER) || s.owner.isImplClass
-
-
     ////////////////////// builders, types ///////////////////////
 
     var entryPoint: Symbol = _
@@ -2202,7 +2197,7 @@ abstract class GenMSIL extends SubComponent {
 
       for (m <- sym.tpe.nonPrivateMembers
            if m.owner != definitions.ObjectClass && !m.hasFlag(Flags.PROTECTED) &&
-           m.isMethod && !m.isClassConstructor && !isStaticSymbol(m) && !m.hasFlag(Flags.CASE))
+           m.isMethod && !m.isClassConstructor && !m.isStaticMember && !m.hasFlag(Flags.CASE))
         {
           if (settings.debug.value)
             log("   Mirroring method: " + m)
diff --git a/src/compiler/scala/tools/nsc/symtab/Flags.scala b/src/compiler/scala/tools/nsc/symtab/Flags.scala
index 2c526f77a9..fae47dd0f3 100644
--- a/src/compiler/scala/tools/nsc/symtab/Flags.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Flags.scala
@@ -101,9 +101,6 @@ object Flags extends Enumeration {
   final val notOVERRIDE   = (OVERRIDE: Long) << AntiShift
   final val notMETHOD     = (METHOD: Long) << AntiShift
 
-  final val STATICMODULE  = lateMODULE
-  final val STATICMEMBER  = notOVERRIDE
-
 
   // masks
   /** This flags can be set when class or module symbol is first created. */
diff --git a/src/compiler/scala/tools/nsc/symtab/Names.scala b/src/compiler/scala/tools/nsc/symtab/Names.scala
index 83ba15d128..aafdca2a8a 100644
--- a/src/compiler/scala/tools/nsc/symtab/Names.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Names.scala
@@ -22,9 +22,9 @@ class Names {
   private final val HASH_SIZE  = 0x8000
   private final val HASH_MASK  = 0x7FFF
   private final val NAME_SIZE  = 0x20000
-  private final val MAX_LEN    = 240 // for longer names use a partial MD5 hash
-  private final val PREFIX_LEN = 100 // the length of the prefix to keep unhashed
-  private final val SUFFIX_LEN = 64  // the length of the suffix to keep unhashed
+
+  private final val MaxFileNameLength = 255
+  private final val MaxClassNameLength = MaxFileNameLength - 6 // leave space for ".class"
 
   final val nameDebug = false
 
@@ -86,13 +86,15 @@ class Names {
 
   private lazy val md5 = MessageDigest.getInstance("MD5")
 
-  private def toMD5(cs: Array[Char], offset: Int, len: Int): String = {
+  private def toMD5(s: String, prefixSuffixLen: Int) = {
+	println("COMPACTIFY "+s)
+    val cs: Array[Char] = s.toCharArray
     val bytes = new Array[Byte](cs.length * 4)
     val len = UTF8Codec.encode(cs, 0, bytes, 0, cs.length)
     md5.update(bytes, 0, len)
     val hash = md5.digest()
     val sb = new StringBuilder
-    sb.append(cs, 0, PREFIX_LEN)
+    sb.append(cs, 0, prefixSuffixLen)
     sb.append("$$$$")
     for (i <- 0 until hash.length) {
       val b = hash(i)
@@ -100,10 +102,14 @@ class Names {
       sb.append((b & 0xF).toHexString)
     }
     sb.append("$$$$")
-    sb.append(cs, len - SUFFIX_LEN, SUFFIX_LEN)
+    sb.append(cs, len - prefixSuffixLen, prefixSuffixLen)
     sb.toString
   }
 
+  def compactify(s: String): String =
+    if (s.length <= MaxClassNameLength) s
+    else toMD5(s, MaxClassNameLength / 4)
+
   /** Create a term name from the characters in <code>cs[offset..offset+len-1]</code>.
    *
    *  @param cs     ...
@@ -111,18 +117,17 @@ class Names {
    *  @param len    ...
    *  @return       the created term name
    */
-  def newTermName(cs: Array[Char], offset: Int, len: Int): Name =
-    if (len <= MAX_LEN) {
-      val h = hashValue(cs, offset, len) & HASH_MASK
-      var n = termHashtable(h)
-      while ((n ne null) && (n.length != len || !equals(n.start, cs, offset, len)))
-        n = n.next;
-      if (n eq null) {
-        n = new TermName(nc, len, h)
-        enterChars(cs, offset, len)
-      }
-      n
-    } else newTermName(toMD5(cs, offset, len))
+  def newTermName(cs: Array[Char], offset: Int, len: Int): Name = {
+    val h = hashValue(cs, offset, len) & HASH_MASK
+    var n = termHashtable(h)
+    while ((n ne null) && (n.length != len || !equals(n.start, cs, offset, len)))
+    n = n.next;
+    if (n eq null) {
+      n = new TermName(nc, len, h)
+      enterChars(cs, offset, len)
+    }
+    n
+  }
 
   /** create a term name from string
    */
diff --git a/src/compiler/scala/tools/nsc/symtab/Symbols.scala b/src/compiler/scala/tools/nsc/symtab/Symbols.scala
index 1adcc8d15c..977b174ae5 100644
--- a/src/compiler/scala/tools/nsc/symtab/Symbols.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Symbols.scala
@@ -311,6 +311,10 @@ trait Symbols {
     final def isStatic: Boolean =
       hasFlag(STATIC) || isRoot || owner.isStaticOwner
 
+    /** Is this symbol a static member of its class? (i.e. needs to be implemented as a Java static?) */
+    final def isStaticMember: Boolean =
+      hasFlag(STATIC) || owner.isImplClass
+
     /** Does this symbol denote a class that defines static symbols? */
     final def isStaticOwner: Boolean =
       isPackageClass || isModuleClass && isStatic
@@ -984,6 +988,15 @@ trait Symbols {
               if s != NoSymbol } yield s
       else List()
 
+    /** The virtual classes overridden by this virtual class (including `clazz' itself)
+     *  Classes appear in linearization order (with superclasses before subclasses)
+     */
+    final def overriddenVirtuals: List[Symbol] =
+      this.owner.info.baseClasses
+        .map(_.info.decl(name))
+        .filter(_.isVirtualClass)
+        .reverse
+
     /** The symbol accessed by a super in the definition of this symbol when
      *  seen from class `base'. This symbol is always concrete.
      *  pre: `this.owner' is in the base class sequence of `base'.
@@ -1331,7 +1344,7 @@ trait Symbols {
           rawowner != NoSymbol && !rawowner.isPackageClass) {
         if (flatname == nme.EMPTY) {
           assert(rawowner.isClass)
-          flatname = newTermName(rawowner.name.toString() + "$" + rawname)
+          flatname = newTermName(compactify(rawowner.name.toString() + "$" + rawname))
         }
         flatname
       } else rawname
@@ -1481,7 +1494,7 @@ trait Symbols {
       if (phase.flatClasses && rawowner != NoSymbol && !rawowner.isPackageClass) {
         if (flatname == nme.EMPTY) {
           assert(rawowner.isClass)
-          flatname = newTypeName(rawowner.name.toString() + "$" + rawname)
+          flatname = newTypeName(compactify(rawowner.name.toString() + "$" + rawname))
         }
         flatname
       } else rawname
diff --git a/src/compiler/scala/tools/nsc/transform/Mixin.scala b/src/compiler/scala/tools/nsc/transform/Mixin.scala
index 48ef18ff04..a0b66a6644 100644
--- a/src/compiler/scala/tools/nsc/transform/Mixin.scala
+++ b/src/compiler/scala/tools/nsc/transform/Mixin.scala
@@ -88,12 +88,12 @@ abstract class Mixin extends InfoTransform {
 
   /** Returns the symbol that is accessed by a super-accessor in a mixin composition.
    *
-   *  @param base       The class in mwhich everything is mixed together
+   *  @param base       The class in which everything is mixed together
    *  @param member     The symbol statically referred to by the superaccessor in the trait
    *  @param mixinClass The mixin class that produced the superaccessor
    */
   private def rebindSuper(base: Symbol, member: Symbol, mixinClass: Symbol): Symbol =
-    atPhase(currentRun.refchecksPhase) {
+    atPhase(currentRun.picklerPhase.next) {
       var bcs = base.info.baseClasses.dropWhile(mixinClass !=).tail
       var sym: Symbol = NoSymbol
       if (settings.debug.value)
diff --git a/src/compiler/scala/tools/nsc/typechecker/DeVirtualize.scala b/src/compiler/scala/tools/nsc/typechecker/DeVirtualize.scala
new file mode 100644
index 0000000000..ee98200daa
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/typechecker/DeVirtualize.scala
@@ -0,0 +1,475 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2007 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+// $Id: RefChecks.scala 13735 2008-01-18 17:18:58Z odersky $
+
+package scala.tools.nsc.typechecker
+
+import symtab.Flags._
+import transform.{InfoTransform, TypingTransformers}
+import scala.tools.nsc.util.{Position, NoPosition}
+import scala.collection.mutable.ListBuffer
+
+abstract class DeVirtualize extends InfoTransform with TypingTransformers {
+
+  import global._
+  import definitions._
+  import typer.{typed, typedOperator, atOwner}
+  import posAssigner.atPos
+
+  /** the following two members override abstract members in Transform */
+  val phaseName: String = "devirtualize"
+
+  /** The phase might set the following new flags: */
+  override def phaseNewFlags: Long = notOVERRIDE | notFINAL
+  //
+  // todo: this does not work yet: for some unknown reason the backend
+  // generates unverifiable code when notOVERRIDE is set for any phase whatsoever
+  // (I tried to set it later at phase Mixin, with same effect.
+  // One gets error messages like the following:
+  //
+  // /home/odersky/scala/sabbus.xml:37: The following error occurred while executing this line:
+  // /home/odersky/scala/sabbus.xml:456: Could not create type quick-bin due to java.lang.VerifyError: (class: scala/Option, method: productPrefix signature: ()Ljava/lang/String;) Illegal local variable number
+  //
+  // we need to fix this before notOVERRIDE can be turned on here.
+
+
+  def newTransformer(unit: CompilationUnit): DeVirtualizeTransformer =
+    new DeVirtualizeTransformer(unit)
+
+  /** The class does not change base-classes of existing classes */
+  override def changesBaseClasses = false
+
+  def transformInfo(sym: Symbol, tp: Type): Type = devirtualizeMap(tp)
+
+  /* todo:
+     handle constructor arguments
+     check: overriding classes must have same type params
+     virtual classes cannot have self types
+   */
+
+  /** Do the following transformations everywhere in a type:
+   *
+   *  1. If a class defines virtual classes VC, add abstract types VA,
+   *     worker traits VT and factories VF instead (@see devirtualize).
+   *  2. For all virtual member classes VC which
+   *     are not abstract and which are or inherit from a virtual class defined in current class
+   *     add a factory (@see addFactory)
+   *  3. Convert VC.this where VC is a virtual class to WT.this where WT is the worker trait for VC
+   *     (@see workerTrait)
+   *  4. Convert TypeRef's to VC where VC is a virtual class to TypeRef's to AT, where AT
+   *     is the abstract type corresponding to VC.
+   *
+   *  Note: If a class inherits vc's from two different paths, a vc in the
+   *  inheriting class has to be created beforehand. This is done in phase ??? (NOT YET DONE!)
+   *
+   *  Note: subclasses of virtual classes are treated as if they are virtual.
+   *  isVirtualClass returns true for them also.
+   */
+  object devirtualizeMap extends TypeMap {
+    def apply(tp: Type): Type = mapOver(tp) match {
+      case tp1 @ ClassInfoType(parents, decls, clazz) if containsVirtuals(clazz) =>
+        transformOwnerInfo(clazz) // we might need to do this in two phases: enter/resolve
+        val ds = decls.toList
+        val decls1 = newScope(ds)
+        for (m <- ds)
+          if (m.isVirtualClass) devirtualize(m, decls1)
+        for (m <- classesInNeedOfFactories(clazz))
+          addFactory(m, clazz, decls1)
+        ClassInfoType(parents, decls1, clazz)
+      case tp1 @ ThisType(clazz) if clazz.isVirtualClass =>
+        ThisType(workerTrait(clazz))
+      case tp1 @ TypeRef(pre, clazz, args) if clazz.isVirtualClass =>
+        TypeRef(pre, abstractType(clazz), args)
+      case tp1 =>
+        tp1
+    }
+  }
+
+  /** Transform owner of given clazz symbol */
+  protected def transformOwnerInfo(clazz: Symbol) { atPhase(ownPhase.next) { clazz.owner.info } }
+
+  /** Names of derived classes and factories */
+  protected def workerTraitName(clazzName: Name) = newTypeName(clazzName+"$trait")
+  protected def concreteClassName(clazzName: Name) = newTypeName(clazzName+"$fix")
+  protected def factoryName(clazzName: Name) = newTermName("new$"+clazzName)
+
+  /** Does `clazz' contaion virtual classes? */
+  protected def containsVirtuals(clazz: Symbol) = clazz.info.decls.toList exists (_.isVirtualClass)
+
+  /** The inner classes that need factory methods in `clazz'
+   *  This is intended to catch situations like the following
+   *
+   *  abstract class C {
+   *    class V <: {...}
+   *    class W extends V
+   *  }
+   *  class D extends C {
+   *    class V <: {...}
+   *    // factories needed for V and W!
+   *  }
+   */
+  protected def classesInNeedOfFactories(clazz: Symbol) = atPhase(ownPhase) {
+    def isDefinedVirtual(c: Symbol) = c.isVirtualClass && c.owner == clazz
+    val buf = new ListBuffer[Symbol]
+    for (m <- clazz.info.members)
+      if (m.isVirtualClass && !(m hasFlag ABSTRACT) && (m.info.baseClasses exists isDefinedVirtual))
+        buf += m
+    buf.toList
+  }
+
+  /** The abstract type corresponding to a virtual class. */
+  protected def abstractType(clazz: Symbol): Symbol = atPhase(ownPhase.next) {
+    val tsym = clazz.owner.info.member(clazz.name)
+    assert(tsym.isAbstractType, clazz)
+    tsym
+  }
+
+  /** The worker trait corresponding to a virtual class. */
+  protected def workerTrait(clazz: Symbol) = atPhase(ownPhase.next) {
+    val tsym = clazz.owner.info.member(workerTraitName(clazz.name))
+    assert(tsym.isTrait, clazz)
+    tsym
+  }
+
+  /** The factory corresponding to a virtual class. */
+  protected def factory(clazz: Symbol) = atPhase(ownPhase.next) {
+    assert(!(clazz hasFlag ABSTRACT), clazz)
+    val fsym = clazz.owner.info.member(factoryName(clazz.name))
+    assert(fsym.isMethod, clazz)
+    fsym
+  }
+
+  /** The flags that a worker trait can inherit from its virtual class */
+  protected val traitFlagMask = AccessFlags
+
+  /** The flags that an abstract type can inherit from its virtual class */
+  protected val absTypeFlagMask = AccessFlags | DEFERRED
+
+  /** The flags that a factory method can inherit from its virtual class */
+  protected val factoryFlagMask = AccessFlags
+
+  /** Create a polytype with given type parameters and given type, or return just the type
+   *  if type params is empty. */
+  protected def mkPolyType(tparams: List[Symbol], tp: Type) =
+    if (tparams.isEmpty) tp else PolyType(tparams, tp)
+
+  /** Set info of `dst' to `tp', potentially wrapped by copies of any type
+   *  parameters of symbol `from' */
+  def setPolyInfo(dst: Symbol, from: Symbol, tp: Type) = {
+    val tparams = cloneSymbols(from.typeParams, dst)
+    dst setInfo mkPolyType(tparams, tp substSym (from.typeParams, tparams))
+  }
+
+  /** Replace a virtual class
+   *
+   *  attrs mods class VC[Ts] <: Ps { decls }
+   *
+   * by the following symbols
+   *
+   *  attrs mods1 type VC[Ts] <: dvm(Ps) with VC$trait[Ts]
+   *  attrs mods2 trait VC$trait[Ts] extends AnyRef with ScalaObject {
+   *    this: VC[Ts] with VC$trait[Ts] => decls1
+   *  }
+   *
+   * where
+   *
+   *  dvm    is the devirtalization mapping which converts refs to
+   *         virtual classes to refs to their abstract types (@see devirtualize)
+   *  mods1  are the modifiers inherited to abstract types
+   *  mods2  are the modifiers inherited to worker traits
+   *  decls1 is decls but members that have an override modifier
+   *         lose it and any final modifier as well.
+   */
+  protected def devirtualize(clazz: Symbol, scope: Scope) {
+    scope.unlink(clazz)
+
+    val cabstype = clazz.owner.newAbstractType(clazz.pos, clazz.name)
+      .setFlag(clazz.flags & absTypeFlagMask)
+      .setAttributes(clazz.attributes)
+    scope.enter(cabstype)
+
+    cabstype setInfo new LazyType {
+      override val typeParams = cloneSymbols(clazz.typeParams, cabstype)
+      override def complete(sym: Symbol) {
+        def parentTypeRef(tp: Type) =
+          devirtualizeMap(tp.substSym(clazz.typeParams, typeParams))
+        val parents = (clazz.info.parents map parentTypeRef) :::
+          List(appliedType(workerTrait(clazz).typeConstructor, typeParams map (_.tpe)))
+        sym.setInfo(
+          mkPolyType(typeParams, mkTypeBounds(AllClass.tpe, intersectionType(parents))))
+      }
+    }
+
+    val wtrait = clazz.owner.newClass(clazz.pos, workerTraitName(clazz.name))
+      .setFlag(clazz.flags & traitFlagMask | TRAIT)
+      .setAttributes(clazz.attributes)
+    scope.enter(wtrait)
+
+    // remove OVERRIDE from all workertrait members
+    val decls1 = clazz.info.decls.toList
+    for (val m <- decls1)
+      if (m hasFlag OVERRIDE) m setFlag (notOVERRIDE | notFINAL)
+
+    setPolyInfo(
+      wtrait, clazz,
+      ClassInfoType(List(ObjectClass.tpe, ScalaObjectClass.tpe), newScope(decls1), wtrait))
+    wtrait.typeOfThis = intersectionType(List(
+      appliedType(cabstype.typeConstructor, wtrait.typeParams map (_.tpe)),
+      wtrait.tpe))
+  }
+
+  /* Add a factory symbol for a virtual class
+   *
+   *  attrs mods class VC[Ts] <: Ps { decls }
+   *  with base classes BC[Us]'s
+   *
+   * which corresponds to the following definition :
+   *
+   *  attrs mods3 def new$VC[Ts](): VC[Ts] = {
+   *    class VC$fix extends v2w(BC's[Ts]) with VC$trait[Ts] { ... }
+   *    new VC$fix
+   *  }
+   *
+   * where
+   *
+   *  mods3  are the modifiers inherited to factories
+   *  v2w is maps every virtual class to its workertrait and leaves other types alone.
+   *
+   *  @param  clazz    The virtual class for which factory is added
+   *  @param  owner    The owner for which factory is added as a member
+   *  @param  scope    The scope into which factory is entered
+   */
+  def addFactory(clazz: Symbol, owner: Symbol, scope: Scope) {
+    val pos = if (clazz.owner == owner) clazz.pos else owner.pos
+    val factory = owner.newMethod(pos, factoryName(clazz.name))
+      .setFlag(clazz.flags & factoryFlagMask)
+      .setAttributes(clazz.attributes)
+    scope.enter(factory)
+    val cabstype = abstractType(clazz)
+    setPolyInfo(factory, cabstype, MethodType(List(/*todo: handle constructor parameters*/),
+                                              cabstype.tpe))
+  }
+
+  /** The concrete class symbol VC$fix in the factory symbol (@see addFactory)
+   *  @param clazz    the virtual class
+   *  @param factory  the factory which returns an instance of this class
+   */
+  protected def concreteClassSym(clazz: Symbol, factory: Symbol) = {
+    val cclazz = factory.newClass(clazz.pos, concreteClassName(clazz.name))
+      .setFlag(FINAL)
+      .setAttributes(clazz.attributes)
+
+    cclazz setInfo new LazyType {
+      override def complete(sym: Symbol) {
+        def v2w(bc: Symbol): Type = {
+          val btp = clazz.info baseType bc
+          if (bc.isVirtualClass)
+            (btp: @unchecked) match {
+              case TypeRef(pre, _, args) =>
+                TypeRef(pre, workerTrait(bc), args)
+            }
+          else btp
+        }.substSym(clazz.typeParams, factory.typeParams)
+        val parents = clazz.info.baseClasses.reverse map v2w
+        sym setInfo ClassInfoType(parents, newScope, cclazz)
+      }
+    }
+
+    cclazz
+  }
+
+  /** Perform the following tree transformations:
+   *
+   *  1. Add trees for abstract types (@see devirtualize),
+   *     worker traits (@see devirtualize)
+   *     and factories (@see addFactory)
+   *
+   *  2. Replace a new VC().init(...) where VC is a virtual class with new$VC(...)
+   *
+   *  3. Replace references to VC.this and VC.super where VC is a virtual class
+   *     with VC$trait.this and VC$trait.super
+   *
+   *  4. Transform type references to virtual classes to type references of corresponding
+   *     abstract types.
+   */
+  class DeVirtualizeTransformer(unit: CompilationUnit) extends TypingTransformer(unit) {
+    // all code is executed at phase ownPhase.next
+
+    /** Add trees for abstract types, worker traits, and factories (@see addFactory)
+     *  to template body `stats'
+     */
+    override def transformStats(stats: List[Tree], exprOwner: Symbol): List[Tree] = {
+      val stats1 = stats flatMap transformStat map transform
+      val newDefs = new ListBuffer[Tree]
+      if (currentOwner.isClass && containsVirtuals(currentOwner)) {
+        for (m <- classesInNeedOfFactories(currentOwner))
+          newDefs += factoryDef(m)
+      }
+      if (newDefs.isEmpty) stats1
+      else stats1 ::: newDefs.toList
+    }
+
+    /** The factory definition for virtual class `clazz' (@see addFactory)
+     *  For a virtual class
+     *
+     *  attrs mods class VC[Ts] <: Ps { decls }
+     *  with overridden classes _VC[Us]'s
+     *
+     * we need the following factory:
+     *
+     *  attrs mods3 def new$VC[Ts](): VC[Ts] = {
+     *    class VC$fix extends _VC$trait's[Ts] with VC$trait[Ts] {
+     *      override-bridges
+     *    }
+     *    new VC$fix
+     *  }
+     *
+     * where
+     *
+     *  mods3  are the modifiers inherited to factories
+     *  override-bridges are definitions that link every symbol in a worker trait
+     *                   that was overriding something to the overridden symbol
+     *                   //todo: not sure what happens with abstract override?
+     */
+    def factoryDef(clazz: Symbol): Tree = {
+      val factorySym = factory(clazz)
+      val cclazzSym = concreteClassSym(clazz, factorySym)
+      val overrideBridges =
+        for (m <- workerTrait(clazz).info.decls.toList if m hasFlag notOVERRIDE)
+        yield overrideBridge(m, cclazzSym)
+      val cclazzDef = ClassDef(cclazzSym, Modifiers(0), List(List()), List(List()), overrideBridges)
+      val factoryExpr = atPos(factorySym.pos) {
+        Block(List(cclazzDef), New(TypeTree(cclazzSym.tpe), List(List())))
+      }
+      DefDef(factorySym, vparamss => factoryExpr)
+    }
+
+    /** Create an override bridge for method `meth' in concrete class `cclazz'.
+     *  An override bridge has the form
+     *
+     *   override f(xs1)...(xsN) = super.f(xs)...(xsN)
+     */
+    def overrideBridge(meth: Symbol, cclazz: Symbol) = atPos(meth.pos) {
+      val bridge = meth.cloneSymbol(cclazz)
+        .resetFlag(notOVERRIDE | notFINAL)
+      val superRef: Tree = Select(Super(cclazz, nme.EMPTY.toTypeName), meth)
+      DefDef(bridge, vparamss => (superRef /: vparamss)((fn, vparams) =>
+        Apply(fn, vparams map (param => Ident(param) setPos param.pos))))
+    }
+
+    /** Replace definitions of virtual classes by definitions of corresponding
+     *  abstract type and worker traits.
+     */
+    protected def transformStat(tree: Tree): List[Tree] = tree match {
+      case ClassDef(mods, name, tparams, templ @ Template(parents, self, body)) if (tree.symbol.isVirtualClass) =>
+        val clazz = tree.symbol
+        val absTypeSym = abstractType(clazz)
+        val workerTraitSym = workerTrait(clazz)
+        val abstypeDef = TypeDef(abstractType(clazz))
+        val workerTraitDef = ClassDef(
+          workerTraitSym,
+          Modifiers(0),
+          List(List()),
+          List(List()),
+          body)
+        new ChangeOwnerTraverser(clazz, workerTraitSym)(
+          new ChangeOwnerTraverser(templ.symbol, workerTraitDef.impl.symbol)(workerTraitDef.impl))
+        List(abstypeDef, workerTraitDef) map localTyper.typed
+      case _ =>
+        List(tree)
+    }
+
+    override def transform(tree: Tree): Tree = {
+      tree match {
+        // Replace references to VC.this and VC.super where VC is a virtual class
+        // with VC$trait.this and VC$trait.super
+        case This(_) | Super(_, _) if tree.symbol.isVirtualClass =>
+          tree setSymbol workerTrait(tree.symbol)
+
+        // Replace a new VC().init() where VC is a virtual class with new$VC
+        case Select(New(tpt), name) if (tree.symbol.isConstructor && tree.symbol.owner.isVirtualClass) =>
+          val clazz = tpt.tpe.typeSymbol
+          val fn = gen.mkAttributedRef(factory(clazz))
+          val targs = tpt.tpe.typeArgs
+          atPos(tree.pos) {
+            localTyper.typed {
+              Apply(
+                if (targs.isEmpty) fn else TypeApply(fn, targs map TypeTree),
+                List())
+            }
+          }
+
+        case _ =>
+          super.transform(tree)
+      }
+    } setType devirtualizeMap(tree.tpe)
+
+    override def transformUnit(unit: CompilationUnit) = atPhase(ownPhase.next) {
+      super.transformUnit(unit)
+    }
+  }
+}
+
+
+
+/*
+    class A {
+      class C[X, Y](x: X) <: { var y = x ; def f(z: Y): X }
+      class D[Y](z) extends C[Int, Y](f(z)) { override def f(z:Int) = 3 }
+    }
+    class B extends A {
+      class C[X, Y](x: X) <: { def g = 2 }
+    }
+
+maps to:
+
+  class A {
+    type C[X, Y] <: CT[X, Y]
+
+    trait CT[X, Y] { self: C => protected[this] val x: Int; val y = x; def f(z:Int) = z + 1 }
+
+    type D <: C with DT
+
+    trait DT extends { self: D => def f(z:Int) = z + 2 }
+
+    trait preDT extends { self: D => val z: Int; val x = f(z) }
+
+    def newC(x: Int): C
+    def newD(x: Int): D
+
+    //type C = CT
+    //type D = C with DT
+
+    class CC(_x:Int) extends { val x = _x } with CT
+
+    def newC[X, Y](x:Int): C =
+      new CC(x).asInstanceOf[C]
+
+    class DC(_z:Int) extends { val z = _z } with preDT with CT with DT {
+      override def f(z:Int) = super.f(z)
+    }
+
+    def newD(z:Int):D = new DC(z).asInstanceOf[D]
+  }
+
+  class B extends A {
+    type C <: CT with CT2
+
+    trait CT2 { self : C => def g = 2 }
+
+    //type C = CT with CT2
+    //type D = C with DT
+
+    class CC2(_x:Int) extends { val x = _x } with CT with CT2
+
+    def newC(x:Int): C = new CC2(x).asInstanceOf[C]
+
+    class DC2(_z:Int) extends { val z = _z } with preDT with CT with CT2
+      with DT { override def f(z:Int) = super.f(z) }
+
+    def newD(z:Int): D = new DC2(z).asInstanceOf[D]
+  }
+
+*/
diff --git a/src/compiler/scala/tools/nsc/typechecker/Namers.scala b/src/compiler/scala/tools/nsc/typechecker/Namers.scala
index 7b9a1e646c..fe9bc2aeab 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Namers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Namers.scala
@@ -524,11 +524,20 @@ trait Namers { self: Analyzer =>
           self.symbol = context.scope enter self.symbol
         }
       }
-      val parents = typer.parentTypes(templ) map checkParent
+      var parents = typer.parentTypes(templ) map checkParent
       enterSelf(templ.self)
       val decls = newClassScope(clazz)
       val templateNamer = newNamer(context.make(templ, clazz, decls))
         .enterSyms(templ.body)
+      // make subclasses of virtual classes virtual as well
+      if (parents exists (_.typeSymbol.isVirtualClass))
+        clazz setFlag DEFERRED
+      // add overridden virtuals to parents
+      if (clazz.isVirtualClass)
+        parents = parents ::: (clazz.overriddenVirtuals map (
+          TypeRef(clazz.thisType, _, clazz.typeParams map (_.tpe))))
+      // add apply and unapply methods to companion objects of case classes,
+      // unless they exist already
       caseClassOfModuleClass get clazz match {
         case Some(cdef) =>
           addApplyUnapply(cdef, templateNamer)