From 340dc52a567de022c56acb1533c5772d21405f2a Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sun, 8 Feb 2015 10:06:43 +0100 Subject: First prototype of pickler. --- src/dotty/tools/dotc/core/Flags.scala | 8 +- .../tools/dotc/core/pickling/NameBuffer.scala | 74 ++++ .../tools/dotc/core/pickling/PickleFormat.scala | 317 ++++++++++++++++++ .../tools/dotc/core/pickling/TastyBuffer.scala | 162 +++++++++ src/dotty/tools/dotc/core/pickling/TastyName.scala | 22 ++ .../tools/dotc/core/pickling/TastyPickler.scala | 50 +++ .../tools/dotc/core/pickling/TreeBuffer.scala | 133 ++++++++ .../tools/dotc/core/pickling/TreePickler.scala | 371 +++++++++++++++++++++ src/dotty/tools/dotc/typer/Namer.scala | 4 +- 9 files changed, 1135 insertions(+), 6 deletions(-) create mode 100644 src/dotty/tools/dotc/core/pickling/NameBuffer.scala create mode 100644 src/dotty/tools/dotc/core/pickling/PickleFormat.scala create mode 100644 src/dotty/tools/dotc/core/pickling/TastyBuffer.scala create mode 100644 src/dotty/tools/dotc/core/pickling/TastyName.scala create mode 100644 src/dotty/tools/dotc/core/pickling/TastyPickler.scala create mode 100644 src/dotty/tools/dotc/core/pickling/TreeBuffer.scala create mode 100644 src/dotty/tools/dotc/core/pickling/TreePickler.scala (limited to 'src/dotty') diff --git a/src/dotty/tools/dotc/core/Flags.scala b/src/dotty/tools/dotc/core/Flags.scala index 53beae838..3a174d95f 100644 --- a/src/dotty/tools/dotc/core/Flags.scala +++ b/src/dotty/tools/dotc/core/Flags.scala @@ -333,7 +333,7 @@ object Flags { final val JavaStaticType = JavaStatic.toTypeFlags /** Trait is not an interface, but does not have fields or intialization code */ - final val NoInits = typeFlag(32, "") + final val NoInits = typeFlag(32, "") // TODO reconstitute from context /** Variable is accessed from nested function. */ final val Captured = termFlag(32, "") @@ -345,7 +345,7 @@ object Flags { final val Bridge = termFlag(34, "") /** Symbol is a Java varargs bridge */ // (needed?) - final val VBridge = termFlag(35, "") + final val VBridge = termFlag(35, "") // TODO remove /** Symbol is a method which should be marked ACC_SYNCHRONIZED */ final val Synchronized = termFlag(36, "") @@ -364,7 +364,7 @@ object Flags { /** Symbol always defines a fresh named type */ final val Fresh = commonFlag(45, "") - /** Symbol is defined in a super call */ + /** Symbol is defined in a super call */ // TODO reconstitute from context final val InSuperCall = commonFlag(46, "") /** Symbol with private access is accessed outside its private scope */ @@ -551,7 +551,7 @@ object Flags { /** A Java interface, potentially with default methods */ final val JavaTrait = allOf(JavaDefined, Trait, NoInits) - /** A Java interface */ + /** A Java interface */ // TODO reconstitute from context final val JavaInterface = allOf(JavaDefined, Trait) /** A Java companion object */ diff --git a/src/dotty/tools/dotc/core/pickling/NameBuffer.scala b/src/dotty/tools/dotc/core/pickling/NameBuffer.scala new file mode 100644 index 000000000..c9994ecb5 --- /dev/null +++ b/src/dotty/tools/dotc/core/pickling/NameBuffer.scala @@ -0,0 +1,74 @@ +package dotty.tools +package dotc +package core +package pickling + +import collection.mutable +import Names.{Name, chrs} +import Decorators._ +import TastyBuffer._ +import scala.io.Codec +import TastyName._ +import PickleFormat._ + +class NameBuffer extends TastyBuffer(100000) { + + private val nameRefs = new mutable.LinkedHashMap[TastyName, Ref] + + def nameIndex(name: TastyName): Ref = nameRefs.get(name) match { + case Some(ref) => + ref + case None => + val ref = new Ref(nameRefs.size) + nameRefs(name) = ref + ref + } + def nameIndex(name: Name): Ref = nameIndex(Simple(name.toTermName)) + def nameIndex(str: String): Ref = nameIndex(str.toTermName) + + private def withLength(op: => Unit): Unit = { + val lengthAddr = currentAddr + writeByte(0) + op + val length = currentAddr.index - lengthAddr.index - 1 + assert(length < 128) + putNat(lengthAddr, length, 1) + } + + def writeRef(ref: Ref) = writeNat(ref.index) + + def pickleName(name: TastyName): Unit = name match { + case Simple(name) => + val bytes = Codec.toUTF8(chrs, name.start, name.length) + writeByte(UTF8) + writeNat(bytes.length) + writeBytes(bytes, bytes.length) + case Qualified(qualified, selector) => + writeByte(QUALIFIED) + withLength { writeRef(qualified); writeRef(selector) } + case Signed(original, params, result) => + writeByte(SIGNED) + withLength { writeRef(original); writeRef(result); params.foreach(writeRef) } + case Expanded(original) => + writeByte(EXPANDED) + withLength { writeRef(original) } + case ModuleClass(module) => + writeByte(MODULECLASS) + withLength { writeRef(module) } + case SuperAccessor(accessed) => + writeByte(SUPERACCESSOR) + withLength { writeRef(accessed) } + case DefaultGetter(method, paramNumer) => + writeByte(DEFAULTGETTER) + withLength { writeRef(method); writeNat(paramNumer) } + } + + override def assemble(): Unit = { + var i = 0 + for ((name, ref) <- nameRefs) { + assert(ref.index == i) + i += 1 + pickleName(name) + } + } +} diff --git a/src/dotty/tools/dotc/core/pickling/PickleFormat.scala b/src/dotty/tools/dotc/core/pickling/PickleFormat.scala new file mode 100644 index 000000000..16356718c --- /dev/null +++ b/src/dotty/tools/dotc/core/pickling/PickleFormat.scala @@ -0,0 +1,317 @@ +package dotty.tools.dotc +package core +package pickling + +/************************************************************ +Notation: + +We use BNF notation. Terminal symbols start with at least two +consecutive upper case letters. Each terminal is represented as a +single byte tag. Non-terminals are mixed case. Prefixes of the form +lower case letter*_ are for explanation of semantic content only, they +can be dropped without changing the grammar. + +Micro-syntax: + + LongNat = Digit* StopDigit // big endian, value fits in a Long without overflow + Nat = LongNat // value fits in an Int without overflow + Digit = 0 | ... | 127 + StopDigit = 128 | ... | 255 // value = digit - 128 + FullInt = Byte Byte Byte Byte + FullLong = Byte Byte Byte Byte Byte Byte Byte Byte + Byte - 0 | ... | 255 + +Macro-format: + + File = Header majorVersion_Nat minorVersion_Nat nameTable_Length Name* Section* + Header = "5CA1AB1F" + + Section = NameRef Length Bytes + Length = Nat // length of rest of entry in bytes + + Name = UTF8 Length UTF8-CodePoint* + QUALIFIED Length qualified_NameRef selector_NameRef + SIGNED Length original_NameRef resultSig_NameRef paramSig_NameRef* + EXPANDED Length original_NameRef + MODULECLASS Length module_NameRef + SUPERACCESSOR Length accessed_NameRef + DEFAULTGETTER Length method_NameRef paramNumber_Nat + ... + + NameRef = Nat // ordinal number of name in name table, starting from 1. + +Note: Unqualified names in the name table are strings. The context decides whether a name is +a type-name or a term-name. The same string can represent both. + +Standard-Section: "ASTs" Tree* + + Tree = PACKAGE Length Path Tree* + Stat + + Stat = Term + VALDEF Length NameRef Type rhs_Tree Modifier* + DEFDEF Length NameRef TypeParam* Params* return_Type rhs_Tree + Modifier* + TYPEDEF Length NameRef (Type | Template) Modifier* + IMPORT Length qual_Term Selector* + + TypeParam = TYPEPARAM Length NameRef Type Modifier* + Params = PARAMS Length Param* + Param = PARAM Length NameRef Type Modifier + Selector = IMPORTED Length name_NameRef + RENAMED Length from_NameRef to_NameRef + + Term = Path + SELECT qual_Term possiblySigned_NameRef + SUPER Length this_Term mixinTrait_Type? + APPLY Length fn_Term arg_Term* + TYPEAPPLY Length fn_Term arg_Term* + NEW Length cls_Type + PAIR Length left_Term right_Term + TYPED Length expr_Term ascription_Type + NAMEDARG Length paramName_NameRef arg_Term + ASSIGN Length lhs_Term rhs_Term + BLOCK Length expr_Term Stat* + IF Length cond_Term then_Term else_Term + CLOSURE Length meth_Term target_Type env_Term* + MATCH Length sel_Term CaseDef* + RETURN Length meth_ASTRef expr_Term? + TRY Length expr_Term CaseDef* finalizer_Term? + THROW Length expr_Term + SEQLITERAL Length elem_Term* + JSEQLITERAL Length elem_Term* + BIND Length boundName_NameRef pat_Type pat_Term + ALTERNATIVE Length alt_Term* + UNAPPLY Length fun_Term ImplicitArg* pat_Term* + ANNOTATED Length annot_Term underlying_Term + EMPTYTREE + + CaseDef = CASEDEF Length pat_Tree guard_Tree rhs_Tree + ImplicitArg = IMPLICITARG Length arg_Tree + Template = TEMPLATE Length parent_Tree* SelfDef? Stat* +// if there is a primary constructor, it is the first statement in Stat*.. + SelfDef = Param + ASTRef = Nat // byte position in AST payload + + Path = Constant + TERMREFdirect sym_ASTRef + TERMREFsymbol qual_Type sym_ASTRef + TERMREF qual_Type possiblySigned_NameRef + THIS Length clsRef_Type + SHARED path_ASTRef + + Constant = UNITconst + FALSEconst + TRUEconst + BYTEconst Nat + BYTEneg NegNat + SHORTconst Nat + SHORTneg NegNat + CHARconst Nat + INTconst Nat + INTneg NegNat + LONGconst LongNat + LONGneg NegLongNat + FLOATconst FullInt + DOUBLEconst FullLong + STRINGconst NameRef + NULLconst + CLASSconst Length Type + ENUMconst Length Path + NegNat = Nat // negValue = -natValue - 1 + NegLongNat = LongNat // negValue = -natValue - 1 + + Type = Path + TYPEREFdirect sym_ASTRef + TYPEREFsymbol qual_Type sym_ASTRef + TYPEREF qual_Type possiblySigned_NameRef + SUPERtype Length this_Type underlying_Type + SKOLEMtype Length underlying_Type + REFINEDtype Length refinement_NameRef info_Type + APPLIEDtype Length tycon_Type arg_Type* + TYPEBOUNDS Length low_Type high_Type + TYPEALIAS Length alias_Type + ANNOTATED Length annot_Tree underlying_Type + ANDtype Length left_Type right_Type + ORtype Length left_Type right_Type + BYNAMEtype Length underlying_Type + NOTYPE + NOPREFIX + SHARED type_ASTRef + + Modifier = PRIVATE + INTERNAL // package private + PROTECTED + PRIVATEqualified qualifier_ASTRef // will be dropped + PROTECTEDqualified qualifier_ASTRef // will be dropped + ABSTRACT + FINAL + SEALED + CASE + IMPLICIT + LAZY + OVERRIDE + INLINE + ABSOVERRIDE // abstract override + STATIC // mapped to static Java member + MODULE // an object or its class + LOCAL // private[this] or protected[this] + SYNTHETIC // generated by Scala compiler + ARTIFACT // to be tagged Java Synthetic + MUTABLE // a var + LABEL // method generated as a label + FIELDaccessor // getter or setter + PARAMaccessor // getter or setter for class param + CASEaccessor // getter for case class param + COVARIANT // type param marked “+” + CONTRAVARIANT // type param marked “-” + SCALA2X // Imported from Scala2.x + DEFAULTparameterized // Method with default params + DEFAULTinit // variable with “_” initializer + annotation_Term + +Note: Tree tags are grouped into 4 categories that determine what follows, and thus allow to compute the size of the tagged tree in a generic way. + + Category 1 (tags 0-95): tag + Category 2 (tags 96-127): tag Nat + Category 3 (tags 128-159): tag AST Nat + Category 4 (tags 160-255): tag Length + +Standard Section: "Positions" startPos_Index endPos_Index + + Index = Length Assoc* + Assoc = Delta ASTRef // largest tree starting/ending at offset + Delta = Nat // # chars from last offset or start of file + +**************************************************************************************/ + +object PickleFormat { + + final val header = "5CA1AB1F" + final val MajorVersion = 0 + final val MinorVersion = 1 + + // Name tags + + final val UTF8 = 1 + final val QUALIFIED = 2 + final val SIGNED = 3 + final val EXPANDED = 4 + final val MODULECLASS = 5 + final val SUPERACCESSOR = 6 + final val DEFAULTGETTER = 7 + +// AST tags + + final val EMPTYTREE = 0 + final val NOTYPE = 1 + final val NOPREFIX = 2 + final val UNITconst = 3 + final val FALSEconst = 4 + final val TRUEconst = 5 + final val NULLconst = 6 + final val PRIVATE = 7 + final val INTERNAL = 8 + final val PROTECTED = 9 + final val ABSTRACT = 10 + final val FINAL = 11 + final val SEALED = 12 + final val CASE = 13 + final val IMPLICIT = 14 + final val LAZY = 15 + final val OVERRIDE = 16 + final val INLINE = 17 + final val ABSOVERRIDE = 18 + final val STATIC = 19 + final val MODULE = 20 + final val LOCAL = 21 + final val SYNTHETIC = 22 + final val ARTIFACT = 23 + final val MUTABLE = 24 + final val LABEL = 25 + final val FIELDaccessor = 26 + final val PARAMaccessor = 27 + final val CASEaccessor = 28 + final val COVARIANT = 29 + final val CONTRAVARIANT = 30 + final val SCALA2X = 31 + final val DEFAULTparameterized = 32 + final val DEFAULTinit = 33 + + final val SHARED = 96 + final val TERMREFdirect = 97 + final val TYPEREFdirect = 98 + final val BYTEconst = 99 + final val BYTEneg = 100 + final val SHORTconst = 101 + final val SHORTneg = 102 + final val CHARconst = 103 + final val INTconst = 104 + final val INTneg = 105 + final val LONGconst = 106 + final val LONGneg = 107 + final val FLOATconst = 108 + final val DOUBLEconst = 109 + final val STRINGconst = 110 + final val PRIVATEqualified = 111 + final val PROTECTEDqualified = 112 + + final val SELECT = 128 + final val TERMREFsymbol = 129 + final val TERMREF = 130 + final val TYPEREFsymbol = 131 + final val TYPEREF = 132 + + final val PACKAGE = 160 + final val VALDEF = 161 + final val DEFDEF = 162 + final val TYPEDEF = 163 + final val IMPORT = 164 + final val TYPEPARAM = 165 + final val PARAMS = 166 + final val PARAM = 167 + final val IMPORTED = 168 + final val RENAMED = 169 + final val APPLY = 170 + final val TYPEAPPLY = 171 + final val NEW = 172 + final val PAIR = 173 + final val TYPED = 174 + final val NAMEDARG = 175 + final val ASSIGN = 176 + final val BLOCK = 177 + final val IF = 178 + final val CLOSURE = 179 + final val MATCH = 180 + final val RETURN = 181 + final val TRY = 182 + final val THROW = 183 + final val SEQLITERAL = 184 + final val JSEQLITERAL = 185 + final val BIND = 186 + final val ALTERNATIVE = 187 + final val UNAPPLY = 188 + final val ANNOTATED = 189 + final val CASEDEF = 190 + final val IMPLICITarg = 191 + final val TEMPLATE = 192 + final val THIS = 193 + final val SUPER = 194 + final val CLASSconst = 195 + final val ENUMconst = 196 + final val SUPERtype = 197 + final val SKOLEMtype = 198 + final val REFINEDtype = 199 + final val APPLIEDtype = 200 + final val TYPEBOUNDS = 201 + final val TYPEALIAS = 202 + final val ANDtype = 203 + final val ORtype = 204 + final val BYNAMEtype = 205 + final val IMPLICITARG = 206 + + final val firstSimpleTreeTag = EMPTYTREE + final val firstNatTreeTag = SHARED + final val firstTreeNatTreeTag = SELECT + final val firstLengthTreeTag = PACKAGE +} diff --git a/src/dotty/tools/dotc/core/pickling/TastyBuffer.scala b/src/dotty/tools/dotc/core/pickling/TastyBuffer.scala new file mode 100644 index 000000000..f6a7a17b4 --- /dev/null +++ b/src/dotty/tools/dotc/core/pickling/TastyBuffer.scala @@ -0,0 +1,162 @@ +package dotty.tools +package dotc +package core +package pickling + +import util.Util.dble + +object TastyBuffer { + + /** The number of digits of the natural number `nat`, written in base 128 format. */ + def natSize(nat: Int): Int = + if (nat < 128) 1 else natSize(nat >>> 7) + 1 + + /** An address pointing to an index in a Tasty buffer's byte array */ + class Addr(val index: Int) extends AnyVal { + def -(delta: Int): Addr = new Addr(this.index - delta) + def +(delta: Int): Addr = new Addr(this.index + delta) + + def relativeTo(base: Addr): Addr = this - base.index - AddrWidth + } + + /** The maximal number of address bytes. + * Since addresses are written as base-128 natural numbers, + * the value of 4 gives a maximal array size of 512M. + */ + final val AddrWidth = 4 +} +import TastyBuffer._ + +/** A byte array buffer that can be filled with bytes or natural numbers in TASTY format, + * and that supports reading and patching addresses represented as natural numbers. + */ +class TastyBuffer(initialSize: Int) { + + /** The current byte array, will be expanded as needed */ + var bytes = new Array[Byte](initialSize) + + /** The number of bytes written */ + var length = 0 + + // -- Output routines -------------------------------------------- + + /** Write a byte of data. */ + def writeByte(b: Int): Unit = { + if (length == bytes.length) bytes = dble(bytes) + bytes(length) = b.toByte + length += 1 + } + + /** Write the first `n` bytes of `data`. */ + def writeBytes(data: Array[Byte], n: Int): Unit = { + while (bytes.length < length + data.length) bytes = dble(bytes) + Array.copy(data, 0, bytes, length, n) + length += n + } + + /** Write a natural number in big endian format, base 128. + * All but the last digits have bit 0x80 set. + */ + def writeNat(x: Int): Unit = + writeLongNat(x.toLong & 0x00000000FFFFFFFFL) + + /** + * Like writeNat, but for longs. This is not the same as + * writeRaw, which writes in base 256. Note that the + * binary representation of LongNat is identical to Nat + * if the long value is in the range Int.MIN_VALUE to + * Int.MAX_VALUE. + */ + def writeLongNat(x: Long): Unit = { + def writeNatPrefix(x: Long): Unit = { + val y = x >>> 7 + if (y != 0L) writeNatPrefix(y) + writeByte(((x & 0x7f) | 0x80).toInt) + } + val y = x >>> 7 + if (y != 0L) writeNatPrefix(y) + writeByte((x & 0x7f).toInt) + } + + /** Write the `nbytes` least significant bytes of `x` in big endian format */ + def writeRaw(x: Long, nbytes: Int): Unit = { + def recur(x: Long, n: Int): Unit = + if (n > 0) { + recur(x >>> 8, n - 1) + writeByte((x & 0xff).toInt) + } + recur(x, nbytes) + } + + // -- Address handling -------------------------------------------- + + /** Write natural number `x` right-adjusted in a field of `width` bytes + * starting with address `at`. + */ + def putNat(at: Addr, x: Int, width: Int): Unit = { + var y = x + var w = width + var digit = y & 0x7f | 0x80 + while (w > 0) { + w -= 1 + bytes(at.index + w) = digit.toByte + y >>>= 7 + digit = y & 0x7f + } + assert(y == 0, s"number $x too large to fit in $width bytes") + } + + /** The byte at given address */ + def getByte(at: Addr): Int = bytes(at.index) + + /** The natural number at address `at` */ + def getNat(at: Addr): Int = getLongNat(at).toInt + + /** The long natural number at address `at` */ + def getLongNat(at: Addr): Long = { + var b = 0L + var x = 0L + var idx = at.index + do { + b = bytes(idx) + x = (x << 7) + (b & 0x7f) + idx += 1 + } while ((b & 0x80) != 0L) + x + } + + /** The address (represented as a natural number) at address `at` */ + def getAddr(at: Addr) = new Addr(getNat(at)) + + /** The smallest address equal to or following `at` which points to a non-zero byte */ + final def skipZeroes(at: Addr): Addr = + if (getByte(at) != 0) at else skipZeroes(at + 1) + + /** The address after the natural number found at address `at`. */ + final def skipNat(at: Addr): Addr = { + val next = at + 1 + if ((getByte(at) & 0x80) != 0) next else skipNat(next) + } + + /** The address referring to the end of data written so far */ + def currentAddr: Addr = new Addr(length) + + /** Reserve `AddrWidth` bytes to write an address into */ + def reserveAddr(): Addr = { + val result = currentAddr + length += AddrWidth + result + } + + /** Fill reserved space at address `at` with address `target` */ + def fillAddr(at: Addr, target: Addr) = + putNat(at, target.index, AddrWidth) + + // -- Finalization -------------------------------------------- + + /** Hook to be overridden in subclasses. + * Perform all actions necessary to assemble the final byte array. + * After `assemble` no more output actions to this buffer are permitted. + */ + def assemble(): Unit = () +} diff --git a/src/dotty/tools/dotc/core/pickling/TastyName.scala b/src/dotty/tools/dotc/core/pickling/TastyName.scala new file mode 100644 index 000000000..911d4c0cd --- /dev/null +++ b/src/dotty/tools/dotc/core/pickling/TastyName.scala @@ -0,0 +1,22 @@ +package dotty.tools +package dotc +package core +package pickling + +import core.Names.TermName + +abstract class TastyName + +object TastyName { + + class Ref(val index: Int) extends AnyVal + + case class Simple(name: TermName) extends TastyName + case class Qualified(qualified: Ref, selector: Ref) extends TastyName + case class Signed(original: Ref, params: List[Ref], result: Ref) extends TastyName + case class Expanded(original: Ref) extends TastyName + case class ModuleClass(module: Ref) extends TastyName + case class SuperAccessor(accessed: Ref) extends TastyName + case class DefaultGetter(method: Ref, num: Int) extends TastyName + +} diff --git a/src/dotty/tools/dotc/core/pickling/TastyPickler.scala b/src/dotty/tools/dotc/core/pickling/TastyPickler.scala new file mode 100644 index 000000000..2ae6848e0 --- /dev/null +++ b/src/dotty/tools/dotc/core/pickling/TastyPickler.scala @@ -0,0 +1,50 @@ +package dotty.tools +package dotc +package core +package pickling + +import PickleFormat._ +import collection.mutable +import TastyBuffer._ + +class TastyPickler { + + private val sections = new mutable.ArrayBuffer[(TastyName.Ref, TastyBuffer)] + + private val headerBuffer = { + val buf = new TastyBuffer(16) + for (ch <- header) buf.writeByte(ch.toByte) + buf.writeNat(MajorVersion) + buf.writeNat(MinorVersion) + buf + } + + val nameBuffer = new NameBuffer + + def newSection(name: String, buf: TastyBuffer) = + sections += ((nameBuffer.nameIndex(name), buf)) + + def assembleParts: Array[Byte] = { + def lengthWithLength(buf: TastyBuffer) = { + buf.assemble() + buf.length + natSize(buf.length) + } + val totalSize = + headerBuffer.length + + lengthWithLength(nameBuffer) + { + for ((nameRef, buf) <- sections) yield + natSize(nameRef.index) + lengthWithLength(buf) + }.sum + val all = new TastyBuffer(totalSize) + all.writeBytes(headerBuffer.bytes, headerBuffer.length) + all.writeNat(nameBuffer.length) + all.writeBytes(nameBuffer.bytes, nameBuffer.length) + for ((nameRef, buf) <- sections) { + all.writeNat(nameRef.index) + all.writeNat(buf.length) + all.writeBytes(buf.bytes, buf.length) + } + assert(all.length == totalSize && all.bytes.length == totalSize) + all.bytes + } +} diff --git a/src/dotty/tools/dotc/core/pickling/TreeBuffer.scala b/src/dotty/tools/dotc/core/pickling/TreeBuffer.scala new file mode 100644 index 000000000..5a445124d --- /dev/null +++ b/src/dotty/tools/dotc/core/pickling/TreeBuffer.scala @@ -0,0 +1,133 @@ +package dotty.tools +package dotc +package core +package pickling + +import util.Util.{bestFit, dble} +import TastyBuffer.{Addr, AddrWidth} + +class TreeBuffer extends TastyBuffer(1000000) { + + private final val ItemsOverOffsets = 2 + + private val initialOffsetSize = bytes.length / (AddrWidth * ItemsOverOffsets) + private var offsets = new Array[Int](initialOffsetSize) + private var isRelative = new Array[Boolean](initialOffsetSize) + private var delta: Array[Int] = _ + private var numOffsets = 0 + + private def offset(i: Int): Addr = new Addr(offsets(i)) + + private def keepOffset(relative: Boolean): Unit = { + if (numOffsets == offsets.length) { + offsets = dble(offsets) + isRelative = dble(isRelative) + } + offsets(numOffsets) = length + isRelative(numOffsets) = relative + numOffsets += 1 + } + + def reserveRef(relative: Boolean): Addr = { + val addr = currentAddr + keepOffset(relative) + reserveAddr() + addr + } + + def writeRef(target: Addr) = { + keepOffset(relative = false) + writeNat(target.index) + } + + def fillRef(at: Addr, target: Addr, relative: Boolean) = { + val addr = if (relative) target.relativeTo(at) else target + fillAddr(at, addr) + } + + def adjusted(x: Addr): Addr = { + val idx = bestFit(offsets, x.index - 1) + if (idx < 0) x else x - delta(idx) + } + + private def computeDeltas() = { + delta = new Array[Int](numOffsets) + var lastDelta = 0 + var i = 0 + while (i < numOffsets) { + val off = offset(i) + val skippedOff = skipZeroes(off) + val skippedCount = skippedOff.index - off.index + assert(skippedCount < AddrWidth, s"unset field at position $off") + lastDelta += skippedCount + delta(i) = lastDelta + i += 1 + } + } + + private def adjustedOffset(at: Addr, isRelative: Boolean): Addr = { + val original = getAddr(at) + if (isRelative) { + val start = skipNat(at).index + adjusted(original + start) - start + } else adjusted(original) + } + + private def adjustOffsets(): Unit = { + for (i <- 0 until numOffsets) { + val off = offset(i) + val original = getAddr(off) + val corrected = adjustedOffset(off, isRelative(i)) + fillAddr(off, corrected) + } + } + + private def adjustDeltas(): Int = { + val delta1 = new Array[Int](delta.length) + var lastDelta = 0 + var i = 0 + while (i < numOffsets) { + val corrected = adjustedOffset(offset(i), isRelative(i)) + lastDelta += AddrWidth - TastyBuffer.natSize(corrected.index) + delta1(i) = lastDelta + i += 1 + } + val saved = + if (numOffsets == 0) 0 + else delta1(numOffsets - 1) - delta(numOffsets - 1) + delta = delta1 + saved + } + + private def compress(): Int = { + var lastDelta = 0 + var start = 0 + var i = 0 + var wasted = 0 + while (i < numOffsets) { + val next = offsets(i) + Array.copy(bytes, start, bytes, start - lastDelta, next - start) + start = next + delta(i) - lastDelta + val pastZeroes = skipZeroes(new Addr(next)).index + assert(pastZeroes >= start, s"something's wrong: eliminated non-zero") + wasted += (pastZeroes - start) + lastDelta = delta(i) + i += 1 + } + length -= lastDelta + wasted + } + + override def assemble(): Unit = { + val origLength = length + computeDeltas() + adjustOffsets() + if (false) { + var saved = 0 + do saved = adjustDeltas() + while (saved > 0 && length / saved < 100) + } + val wasted = compress() + println(s"original length: $origLength, compressed to: $length, wasted: $wasted") + } +} diff --git a/src/dotty/tools/dotc/core/pickling/TreePickler.scala b/src/dotty/tools/dotc/core/pickling/TreePickler.scala new file mode 100644 index 000000000..8c92e2ed8 --- /dev/null +++ b/src/dotty/tools/dotc/core/pickling/TreePickler.scala @@ -0,0 +1,371 @@ +package dotty.tools +package dotc +package core +package pickling + +import util.Util.{bestFit, dble} +import ast.Trees._ +import PickleFormat._ +import core._ +import Contexts._, Symbols._, Types._, Names._, Constants._, Decorators._ +import collection.mutable +import TastyBuffer._ + +class TreePickler(pickler: TastyPickler, picklePositions: Boolean) { + val buf = new TreeBuffer + pickler.newSection("ASTs", buf) + import buf._ + import pickler.nameBuffer.nameIndex + import ast.tpd._ + + private val symRefs = new mutable.HashMap[Symbol, Addr] + private val forwardSymRefs = new mutable.HashMap[Symbol, List[Addr]] + private val pickledTypes = new java.util.IdentityHashMap[Type, Any] // Value type is really Addr, but that's not compatible with null + + private def withLength(op: => Unit) = { + val lengthAddr = reserveRef(relative = true) + op + fillRef(lengthAddr, currentAddr, relative = true) + } + + def registerDef(sym: Symbol) = { + symRefs(sym) = currentAddr + forwardSymRefs.get(sym) match { + case Some(refs) => + refs.foreach(fillRef(_, currentAddr, relative = false)) + forwardSymRefs -= sym + case None => + } + } + + private def pickleName(name: Name) = writeNat(nameIndex(name).index) + private def pickleName(name: TastyName) = writeNat(nameIndex(name).index) + private def pickleNameAndSig(name: Name, sig: Signature) = { + val Signature(params, result) = sig + pickleName(TastyName.Signed(nameIndex(name), params.map(nameIndex), nameIndex(result))) + } + + private def pickleSym(sym: Symbol) = symRefs.get(sym) match { + case Some(label) => + writeRef(label) + case None => + val ref = reserveRef(relative = false) + forwardSymRefs(sym) = ref :: forwardSymRefs.getOrElse(sym, Nil) + } + + def pickle(tree: Tree)(implicit ctx: Context) = { + + def pickleConstant(c: Constant): Unit = { + def pickleNum(nonNegTag: Int, negTag: Int) = { + val x = c.longValue + if (x < 0) { + writeByte(negTag) + writeLongNat(-(x + 1)) + } + else { + writeByte(nonNegTag) + writeLongNat(x) + } + } + c.tag match { + case UnitTag => + writeByte(UNITconst) + case BooleanTag => + writeByte(if (c.booleanValue) TRUEconst else FALSEconst) + case ByteTag => + pickleNum(BYTEconst, BYTEneg) + case ShortTag => + pickleNum(SHORTconst, SHORTneg) + case CharTag => + writeByte(CHARconst) + writeNat(c.charValue) + case IntTag => + pickleNum(INTconst, INTneg) + case LongTag => + pickleNum(LONGconst, LONGneg) + case FloatTag => + writeByte(FLOATconst) + writeRaw(java.lang.Float.floatToRawIntBits(c.floatValue), 4) + case DoubleTag => + writeByte(DOUBLEconst) + writeRaw(java.lang.Double.doubleToRawLongBits(c.doubleValue), 8) + case StringTag => + writeByte(STRINGconst) + writeNat(nameIndex(c.stringValue).index) + case NullTag => + writeByte(NULLconst) + case ClazzTag => + writeByte(CLASSconst) + withLength { pickleType(c.typeValue) } + case EnumTag => + writeByte(ENUMconst) + withLength { pickleType(c.symbolValue.termRef) } + } + } + + def pickleType(tpe: Type): Unit = { + val prev = pickledTypes.get(tpe) + if (prev == null) { + val addr = currentAddr + pickleNewType(tpe) + pickledTypes.put(tpe, addr) + } + else { + writeByte(SHARED) + writeRef(prev.asInstanceOf[Addr]) + } + } + + def pickleNewType(tpe: Type)= tpe match { + case ConstantType(value) => pickleConstant(value) + case tpe: WithFixedSym => + if (tpe.prefix == NoPrefix) { + writeByte(if (tpe.isType) TYPEREFdirect else TERMREFdirect) + pickleSym(tpe.symbol) + } + else { + writeByte(if (tpe.isType) TYPEREFsymbol else TERMREFsymbol) + pickleType(tpe.prefix); pickleSym(tpe.symbol) + } + case tpe: TermRefWithSignature => + writeByte(TERMREF) + pickleType(tpe.prefix); pickleNameAndSig(tpe.name, tpe.signature) + case tpe: NamedType => + writeByte(if (tpe.isType) TYPEREF else TERMREF) + pickleType(tpe.prefix); pickleName(tpe.name) + case tpe: ThisType => + writeByte(THIS) + pickleType(tpe.tref) + case tpe: SuperType => + writeByte(SUPERtype) + withLength { pickleType(tpe.thistpe); pickleType(tpe.supertpe)} + case tpe: SkolemType => + writeByte(SKOLEMtype) + withLength { pickleType(tpe.underlying) } + case tpe: RefinedType => + val args = tpe.argInfos(interpolate = false) + if (args.isEmpty) { + writeByte(REFINEDtype) + withLength { pickleName(tpe.refinedName); pickleType(tpe.refinedInfo) } + } + else { + writeByte(APPLIEDtype) + withLength { pickleType(tpe.withoutArgs(args)); args.foreach(pickleType) } + } + case tpe: TypeAlias => + writeByte(TYPEALIAS) + withLength { pickleType(tpe.alias) } + case tpe: TypeBounds => + writeByte(TYPEBOUNDS) + withLength { pickleType(tpe.lo); pickleType(tpe.hi) } + case tpe: AnnotatedType => + writeByte(ANNOTATED) + withLength { pickleTree(tpe.annot.tree); pickleType(tpe.tpe) } + case tpe: AndOrType => + writeByte(if (tpe.isAnd) ANDtype else ORtype) + withLength { pickleType(tpe.tp1); pickleType(tpe.tp2) } + case tpe: ExprType => + writeByte(BYNAMEtype) + withLength { pickleType(tpe.underlying) } + case NoType => + writeByte(NOTYPE) +// case NoPrefix => // not sure we need this! +// writeByte(NOPREFIX) + } + + def pickleTpt(tpt: Tree): Unit = pickleType(tpt.tpe) // TODO correlate with original when generating positions + + def pickleTreeIfNonEmpty(tree: Tree): Unit = + if (!tree.isEmpty) pickleTree(tree) + + def pickleTree(tree: Tree): Unit = tree match { + case Ident(_) | This(_) => + pickleType(tree.tpe) + case Select(qual, name) => + writeByte(SELECT) + val sig = tree.tpe.signature + if (sig == Signature.NotAMethod) pickleName(name) + else pickleNameAndSig(name, sig) + case Apply(fun, args) => + writeByte(APPLY) + withLength { + pickleTree(fun) + args.foreach(pickleTree) + } + case TypeApply(fun, args) => + writeByte(TYPEAPPLY) + withLength { + pickleTree(fun) + args.foreach(pickleTree) + } + case Literal(const) => + pickleConstant(const) + case Super(qual, mix) => + writeByte(SUPER) + withLength { + pickleTree(qual); + if (!mix.isEmpty) { + val SuperType(_, mixinType) = tree.tpe + pickleType(mixinType) + } + } + case New(tpt) => + writeByte(NEW) + withLength { pickleTpt(tpt) } + case Pair(left, right) => + writeByte(PAIR) + withLength { pickleTree(left); pickleTree(right) } + case Typed(expr, tpt) => + writeByte(TYPED) + withLength { pickleTree(expr); pickleTpt(tpt) } + case NamedArg(name, arg) => + writeByte(NAMEDARG) + withLength { pickleName(name); pickleTree(arg) } + case Assign(lhs, rhs) => + writeByte(ASSIGN) + withLength { pickleTree(lhs); pickleTree(rhs) } + case Block(stats, expr) => + writeByte(BLOCK) + withLength { pickleTree(expr); stats.foreach(pickleTree) } + case If(cond, thenp, elsep) => + writeByte(IF) + withLength{ pickleTree(cond); pickleTree(thenp); pickleTree(elsep) } + case Closure(env, meth, tpt) => + writeByte(CLOSURE) + withLength{ pickleTree(meth); pickleTpt(tpt); env.foreach(pickleTree) } + case Match(selector, cases) => + writeByte(MATCH) + withLength { pickleTree(selector); cases.foreach(pickleTree) } + case CaseDef(pat, guard, rhs) => + writeByte(CASEDEF) + withLength { pickleTree(pat); pickleTree(guard); pickleTree(rhs) } + case Return(expr, from) => + writeByte(RETURN) + withLength { pickleSym(from.symbol); pickleTreeIfNonEmpty(expr) } + case Try(block, cases, finalizer) => + writeByte(TRY) + withLength { pickleTree(block); cases.foreach(pickleTree); pickleTreeIfNonEmpty(finalizer) } + case Throw(expr) => + writeByte(THROW) + withLength { pickleTree(expr) } + case SeqLiteral(elems) => + writeByte(if (tree.isInstanceOf[JavaSeqLiteral]) JSEQLITERAL else SEQLITERAL) + withLength { elems.foreach(pickleTree) } + case TypeTree(original) => + pickleTpt(tree) + case Bind(name, body) => + registerDef(tree.symbol) + writeByte(BIND) + withLength { pickleName(name); pickleType(tree.symbol.info); pickleTree(body) } + case Alternative(alts) => + writeByte(ALTERNATIVE) + withLength { alts.foreach(pickleTree) } + case UnApply(fun, implicits, patterns) => + writeByte(UNAPPLY) + withLength { + pickleTree(fun) + for (implicitArg <- implicits) { + writeByte(IMPLICITARG) + withLength { pickleTree(implicitArg) } + } + patterns.foreach(pickleTree) + } + case tree: ValDef => + pickleDef(VALDEF, tree.symbol, tree.rhs) + case tree: DefDef => + def pickleParams = { + for (tparam <- tree.tparams) pickleDef(TYPEPARAM, tparam.symbol, EmptyTree) + for (vparams <- tree.vparamss) { + writeByte(PARAMS) + withLength { + for (vparam <- vparams) pickleDef(PARAM, vparam.symbol, EmptyTree) + } + } + } + pickleDef(DEFDEF, tree.symbol, tree.rhs, pickleParams) + case tree: TypeDef => + pickleDef(TYPEDEF, tree.symbol, tree.rhs) + case tree: Template => + writeByte(TEMPLATE) + withLength { + tree.parents.foreach(pickleTree) + if (!tree.self.isEmpty) + pickleDef(PARAM, tree.self.symbol, EmptyTree) + pickleTreeIfNonEmpty(tree.constr) + tree.body.foreach(pickleTree) + } + case Import(expr, selectors) => + writeByte(IMPORT) + withLength { + pickleTree(expr) + selectors foreach { + case Pair(Ident(from), Ident(to)) => + writeByte(RENAMED) + withLength { pickleName(from); pickleName(to) } + case Ident(name) => + writeByte(IMPORTED) + withLength { pickleName(name) } + } + } + case PackageDef(pid, stats) => + writeByte(PACKAGE) + withLength { pickleType(pid.tpe); stats.foreach(pickleTree) } + case Annotated(annot, arg) => + writeByte(ANNOTATED) + withLength { pickleTree(annot); pickleTree(arg) } + } + + def pickleDef(tag: Int, sym: Symbol, rhs: Tree, pickleParams: => Unit = ()) = { + registerDef(sym) + writeByte(tag) + withLength { + pickleName(sym.name) + pickleParams + if (tag != TYPEDEF) pickleType(sym.info.finalResultType) + if (tag != PARAM && tag != TYPEPARAM) pickleTree(rhs) + pickleModifiers(sym) + } + } + + def pickleModifiers(sym: Symbol): Unit = { + import Flags._ + val flags = sym.flags + val privateWithin = sym.privateWithin + if (privateWithin.exists) { + writeByte(if (flags is Protected) PROTECTEDqualified else PRIVATEqualified) + pickleSym(privateWithin) + } + if (flags is Private) writeByte(PRIVATE) + if (flags is Protected) if (!privateWithin.exists) writeByte(PROTECTED) + if (flags is Final) writeByte(FINAL) + if (flags is Case) writeByte(CASE) + if (flags is Override) writeByte(OVERRIDE) + if (flags is Inline) writeByte(INLINE) + if (flags is JavaStatic) writeByte(STATIC) + if (flags is Module) writeByte(MODULE) + if (flags is Local) writeByte(LOCAL) + if (flags is Synthetic) writeByte(SYNTHETIC) + if (flags is Artifact) writeByte(ARTIFACT) + if (flags is Scala2x) writeByte(SCALA2X) + if (sym.isTerm) { + if (flags is Implicit) writeByte(IMPLICIT) + if (flags is Lazy) writeByte(LAZY) + if (flags is AbsOverride) writeByte(ABSOVERRIDE) + if (flags is Mutable) writeByte(MUTABLE) + if (flags is Accessor) writeByte(FIELDaccessor) + if (flags is ParamAccessor) writeByte(PARAMaccessor) + if (flags is CaseAccessor) writeByte(CASEaccessor) + if (flags is DefaultParameterized) writeByte(DEFAULTparameterized) + if (flags is DefaultInit) writeByte(DEFAULTinit) + } else { + if (flags is Sealed) writeByte(SEALED) + if (flags is Abstract) writeByte(ABSTRACT) + if (flags is Covariant) writeByte(COVARIANT) + if (flags is Contravariant) writeByte(CONTRAVARIANT) + } + sym.annotations.foreach(ann => pickleTree(ann.tree)) + } + + pickleTree(tree) + } +} diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala index c522a5998..95f0b4165 100644 --- a/src/dotty/tools/dotc/typer/Namer.scala +++ b/src/dotty/tools/dotc/typer/Namer.scala @@ -497,9 +497,9 @@ class Namer { typer: Typer => denot.info = ClassInfo(cls.owner.thisType, cls, parentRefs, decls, selfInfo) if (cls is Trait) { if (body forall isNoInitMember) { - cls.setFlag(NoInits) + cls.setFlag(NoInits) // TODO set when unpickling if (body forall isPureInterfaceMember) - cls.setFlag(PureInterface) + cls.setFlag(PureInterface) // TODO set when unpickling } } } -- cgit v1.2.3