From 13d6d22aee79670de9dd8fb26eb243b2d21f58c4 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 30 Jan 2013 18:19:13 +0100 Subject: Swiztched to name table, added StdNames and related definitions. Introduced LocalNames. --- src/dotty/tools/dotc/core/Names.scala | 367 ++++++++++++++++++++++------------ 1 file changed, 240 insertions(+), 127 deletions(-) (limited to 'src/dotty/tools/dotc/core/Names.scala') diff --git a/src/dotty/tools/dotc/core/Names.scala b/src/dotty/tools/dotc/core/Names.scala index 30d80a938..abf902a1c 100644 --- a/src/dotty/tools/dotc/core/Names.scala +++ b/src/dotty/tools/dotc/core/Names.scala @@ -3,29 +3,35 @@ package core import scala.io.Codec import util.NameTransformer -import Periods._ import Decorators._ +import collection.IndexedSeqOptimized +import collection.generic.CanBuildFrom +import collection.mutable.{ Builder, StringBuilder } +import collection.immutable.WrappedString +import collection.generic.CanBuildFrom +//import annotation.volatile object Names { /** A name is essentially a string, with three differences * 1. Names belong in one of two universes: they are type names or term names. * The same string can correspond both to a type name and to a term name. - * 2. In each universe, names are hash-consed per basis. Two names - * representing the same string in the same basis are always reference identical. + * 2. NAmes are hash-consed. Two names + * representing the same string in the same universe are always reference identical. * 3. Names are intended to be encoded strings. @see dotc.util.NameTransformer. * The encoding will be applied when converting a string to a name. */ - abstract class Name extends DotClass { + abstract class Name extends DotClass + with Seq[Char] + with IndexedSeqOptimized[Char, Name] { - /** The basis in which this name is stored */ - val basis: NameTable + type ThisName <: Name /** The start index in the character array */ val start: Int /** The length of the names */ - val length: Int + override val length: Int /** Is this name a type name? */ def isTypeName: Boolean @@ -45,31 +51,15 @@ object Names { /** This name downcasted to a term name */ def asTermName: TermName - /** This name in the given basis */ - def in(basis: NameTable) = - if (this.basis eq basis) this - else newName(basis, this.basis.chrs, start, length) + /** This name converted to a local field name */ + def toLocalName: LocalName /** Create a new name of same kind as this one, in the given * basis, with `len` characters taken from `cs` starting at `offset`. */ - protected def newName(basis: NameTable, cs: Array[Char], offset: Int, len: Int): Name + def fromChars(cs: Array[Char], offset: Int, len: Int): ThisName - /** A dummy equals method to catch all comparisons of names - * to other entities (e.g. strings). - * One always should use the ==(Name) method instead. - */ - final override def equals(that: Any): Boolean = unsupported("equals") - - /** The only authorized == method on names */ - def == (that: Name): Boolean = ( - (this eq that) - || - (this.basis ne that.basis) && - (this == (that in this.basis)) - ) - - override def toString = new String(basis.chrs, start, length) + override def toString = new String(chrs, start, length) /** Write to UTF8 representation of this name to given character array. * Start copying to index `to`. Return index of next free byte in array. @@ -77,147 +67,270 @@ object Names { * (i.e. maximally 3*length bytes). */ final def copyUTF8(bs: Array[Byte], offset: Int): Int = { - val bytes = Codec.toUTF8(basis.chrs, start, length) + val bytes = Codec.toUTF8(chrs, start, length) scala.compat.Platform.arraycopy(bytes, 0, bs, offset, bytes.length) offset + bytes.length } /** Convert to string replacing operator symbols by corresponding \$op_name. */ def decode: String = NameTransformer.decode(toString) + + def ++ (other: Name): ThisName = ++ (other.toString) + + def ++ (other: String): ThisName = { + val s = toString + other + fromChars(s.toCharArray, 0, s.length) + } + + // ----- Collections integration ------------------------------------- + + override protected[this] def thisCollection: WrappedString = new WrappedString(repr.toString) + override protected[this] def toCollection(repr: Name): WrappedString = new WrappedString(repr.toString) + + override protected[this] def newBuilder: Builder[Char, Name] = unsupported("newBuilder") + + override def apply(index: Int): Char = chrs(start + index) + + override def slice(from: Int, until: Int): ThisName = + fromChars(chrs, start + from, start + until) + + override def seq = toCollection(this) } - class TermName(val basis: NameTable, val start: Int, val length: Int, val next: TermName) extends Name { + class TermName(val start: Int, val length: Int, private[Names] var next: TermName) extends Name { + type ThisName = TermName def isTypeName = false def isTermName = true - lazy val toTypeName: TypeName = new TypeName(basis, start, length, this) + + @volatile private[this] var _typeName: TypeName = null + + def toTypeName: TypeName = { + if (_typeName == null) + synchronized { + if (_typeName == null) + _typeName = new TypeName(start, length, this) + } + _typeName + } def toTermName = this - def asTypeName = throw new ClassCastException(this+" is not a type name") + def asTypeName = throw new ClassCastException(this + " is not a type name") def asTermName = this - protected def newName(basis: NameTable, cs: Array[Char], offset: Int, len: Int): Name = - basis.newTermName(cs, offset, len) + def toLocalName: LocalName = toTypeName.toLocalName + + override protected[this] def newBuilder: Builder[Char, Name] = termNameBuilder + + def fromChars(cs: Array[Char], offset: Int, len: Int): TermName = termName(cs, offset, len) } - class TypeName(val basis: NameTable, val start: Int, val length: Int, val toTermName: TermName) extends Name { + class TypeName(val start: Int, val length: Int, initialTermName: TermName) extends Name { + type ThisName = TypeName def isTypeName = true def isTermName = false def toTypeName = this def asTypeName = this - def asTermName = throw new ClassCastException(this+" is not a term name") + def asTermName = throw new ClassCastException(this + " is not a term name") + + private[this] var _termName = initialTermName + + def toTermName: TermName = _termName match { + case tn: LocalName => + synchronized { tn.toGlobalName } + case tn => + tn + } + + def toLocalName: LocalName = _termName match { + case tn: LocalName => + tn + case _ => + synchronized { + val lname = new LocalName(start, length, _termName) + _termName = lname + lname + } + } - protected def newName(basis: NameTable, cs: Array[Char], offset: Int, len: Int): Name = - basis.newTypeName(cs, offset, len) + override protected[this] def newBuilder: Builder[Char, Name] = typeNameBuilder + + def fromChars(cs: Array[Char], offset: Int, len: Int): TypeName = typeName(cs, offset, len) } - class NameTable { + /* A local name representing a field that has otherwise the same name as + * a normal term name. Used to avoid name clashes between fields and methods. + * Local names are linked to their corresponding trem anmes and type names. + * + * The encoding is as follows. + * + * If there are only a term name and type name: + * + * TermName + * | ^ + * _typeName | | _termName + * v | + * TypeName + * + * If there is also a local name: + * + * TermName + * | ^ + * | +--------------+ _termNme + * | | + * _typeName | LocalName + * | ^ + * | +--------------+ _termName + * v | + * TypeName + */ + class LocalName(start: Int, length: Int, _next: TermName) extends TermName(start, length, _next) { + def toGlobalName: TermName = next + } - private final val HASH_SIZE = 0x8000 - private final val HASH_MASK = 0x7FFF - private final val NAME_SIZE = 0x20000 - final val nameDebug = false + // Nametable - /** Memory to store all names sequentially. */ - private[Names] var chrs: Array[Char] = new Array[Char](NAME_SIZE) - private var nc = 0 + private final val InitialHashSize = 0x8000 + private final val InitialNameSize = 0x20000 + private final val fillFactor = 0.7 - /** Hashtable for finding term names quickly. */ - private val table = new Array[Names.TermName](HASH_SIZE) + /** Memory to store all names sequentially. */ + private var chrs: Array[Char] = new Array[Char](InitialNameSize) - /** The hashcode of a name. */ - private def hashValue(cs: Array[Char], offset: Int, len: Int): Int = - if (len > 0) - (len * (41 * 41 * 41) + - cs(offset) * (41 * 41) + - cs(offset + len - 1) * 41 + - cs(offset + (len >> 1))) - else 0 + /** The number of characters filled. */ + private var nc = 0 - /** - * Is (the ASCII representation of) name at given index equal to - * cs[offset..offset+len-1]? - */ - private def equals(index: Int, cs: Array[Char], offset: Int, len: Int): Boolean = { - var i = 0 - while ((i < len) && (chrs(index + i) == cs(offset + i))) - i += 1; - i == len + /** Hashtable for finding term names quickly. */ + private var table = new Array[TermName](InitialHashSize) + + /** The number of defined names. */ + private var size = 1 + + /** Make sure the capacity of the character array is at least `n` */ + private def ensureCapacity(n: Int) = + if (n > chrs.length) { + val newchrs = new Array[Char](chrs.length * 2) + chrs.copyToArray(newchrs) + chrs = newchrs } - /** Enter characters into chrs array. */ - private def enterChars(cs: Array[Char], offset: Int, len: Int) { - var i = 0 - while (i < len) { - if (nc + i == chrs.length) { - val newchrs = new Array[Char](chrs.length * 2) - scala.compat.Platform.arraycopy(chrs, 0, newchrs, 0, chrs.length) - chrs = newchrs - } - chrs(nc + i) = cs(offset + i) - i += 1 - } - if (len == 0) nc += 1 - else nc = nc + len + /** Make sure the hash table is large enough for the given load factor */ + private def incTableSize() = { + size += 1 + if (size.toDouble / table.size > fillFactor) { + val oldTable = table + table = new Array[TermName](table.size * 2) + for (i <- 0 until oldTable.size) rehash(oldTable(i)) } + } - /** - * Create a term name from the characters in cs[offset..offset+len-1]. - * Assume they are already encoded. - */ - def newTermName(cs: Array[Char], offset: Int, len: Int): TermName = /* sync if parallel */ { - val h = hashValue(cs, offset, len) & HASH_MASK + /** Rehash chain of names */ + private def rehash(name: TermName): Unit = + if (name != null) { + rehash(name.next) + val h = hashValue(chrs, name.start, name.length) & (table.size - 1) + name.next = table(h) + table(h) = name + } + + /** The hash of a name made of from characters cs[offset..offset+len-1]. */ + private def hashValue(cs: Array[Char], offset: Int, len: Int): Int = + if (len > 0) + (len * (41 * 41 * 41) + + cs(offset) * (41 * 41) + + cs(offset + len - 1) * 41 + + cs(offset + (len >> 1))) + else 0 + + /** Is (the ASCII representation of) name at given index equal to + * cs[offset..offset+len-1]? + */ + private def equals(index: Int, cs: Array[Char], offset: Int, len: Int): Boolean = { + var i = 0 + while ((i < len) && (chrs(index + i) == cs(offset + i))) + i += 1; + i == len + } + + /** Enter characters into chrs array. */ + private def enterChars(cs: Array[Char], offset: Int, len: Int) { + ensureCapacity(nc + len) + var i = 0 + while (i < len) { + chrs(nc + i) = cs(offset + i) + i += 1 + } + nc += len + } + + /** Create a term name from the characters in cs[offset..offset+len-1]. + * Assume they are already encoded. + */ + def termName(cs: Array[Char], offset: Int, len: Int): TermName = { + val h = hashValue(cs, offset, len) & (table.size - 1) + synchronized { val next = table(h) var name = next - while ((name ne null) && (name.length != len || !equals(name.start, cs, offset, len))) + while (name ne null) { + if (name.length == len && equals(name.start, cs, offset, len)) + return name name = name.next - - if (name eq null) /* needs sync if parallel */ { - name = new TermName(this, nc, len, next) - enterChars(cs, offset, len) - table(h) = name - name } - + name = new TermName(nc, len, next) + enterChars(cs, offset, len) + table(h) = name + incTableSize() name } + } - /** - * Create a type name from the characters in cs[offset..offset+len-1]. - * Assume they are already encoded. - */ - def newTypeName(cs: Array[Char], offset: Int, len: Int): TypeName = - newTermName(cs, offset, len).toTypeName + /** Create a type name from the characters in cs[offset..offset+len-1]. + * Assume they are already encoded. + */ + def typeName(cs: Array[Char], offset: Int, len: Int): TypeName = + termName(cs, offset, len).toTypeName - /** - * Create a term name from the UTF8 encoded bytes in bs[offset..offset+len-1]. - * Assume they are already encoded. - */ - def newTermName(bs: Array[Byte], offset: Int, len: Int): TermName = { - val chars = Codec.fromUTF8(bs, offset, len) - newTermName(chars, 0, chars.length) - } + /** Create a term name from the UTF8 encoded bytes in bs[offset..offset+len-1]. + * Assume they are already encoded. + */ + def termName(bs: Array[Byte], offset: Int, len: Int): TermName = { + val chars = Codec.fromUTF8(bs, offset, len) + termName(chars, 0, chars.length) + } - /** - * Create a type name from the UTF8 encoded bytes in bs[offset..offset+len-1]. - * Assume they are already encoded. - */ - def newTypeName(bs: Array[Byte], offset: Int, len: Int): TypeName = - newTermName(bs, offset, len).toTypeName + /** Create a type name from the UTF8 encoded bytes in bs[offset..offset+len-1]. + * Assume they are already encoded. + */ + def typeName(bs: Array[Byte], offset: Int, len: Int): TypeName = + termName(bs, offset, len).toTypeName - /** Create a term name from a string, encode if necessary*/ - def newTermName(s: String): TermName = { - val es = NameTransformer.encode(s) - newTermName(es.toCharArray, 0, es.length) - } + /** Create a term name from a string, wihtout encoding operators */ + def termName(s: String): TermName = termName(s.toCharArray, 0, s.length) - /** Create a type name from a string, encode if necessary */ - def newTypeName(s: String): TypeName = { - val es = NameTransformer.encode(s) - newTypeName(es.toCharArray, 0, es.length) - } - } + /** Create a term name from a string, encode if necessary*/ + def encodedTermName(s: String): TermName = termName(NameTransformer.encode(s)) + + /** Create a type name from a string, wihtout encoding operators */ + def typeName(s: String): TypeName = typeName(s.toCharArray, 0, s.length) + + /** Create a type name from a string, encode if necessary*/ + def encodedTypeName(s: String): TypeName = typeName(NameTransformer.encode(s)) + + /** The term name represented by the empoty string */ + val EmptyTermName = new TermName(-1, 0, null) - object BootNameTable extends NameTable + table(0) = EmptyTermName - val EmptyTypeName = BootNameTable.newTypeName("") - val EmptyTermName = BootNameTable.newTermName("") -} \ No newline at end of file + /** The type name represented by the empoty string */ + val EmptyTypeName = EmptyTermName.toTypeName + + val termNameBuilder: Builder[Char, TermName] = + StringBuilder.newBuilder.mapResult(termName) + + val typeNameBuilder: Builder[Char, TypeName] = + StringBuilder.newBuilder.mapResult(typeName) + + implicit val nameCanBuildFrom: CanBuildFrom[Name, Char, Name] = new CanBuildFrom[Name, Char, Name] { + def apply(from: Name): Builder[Char, Name] = + StringBuilder.newBuilder.mapResult(s => from.fromChars(s.toCharArray, 0, s.length)) + def apply(): Builder[Char, Name] = termNameBuilder + } +} -- cgit v1.2.3