diff options
Diffstat (limited to 'compiler/src/dotty/tools/dotc/util')
22 files changed, 2191 insertions, 0 deletions
diff --git a/compiler/src/dotty/tools/dotc/util/Attachment.scala b/compiler/src/dotty/tools/dotc/util/Attachment.scala new file mode 100644 index 000000000..20facfd97 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/Attachment.scala @@ -0,0 +1,96 @@ +package dotty.tools.dotc.util + +/** A class inheriting from Attachment.Container supports + * adding, removing and lookup of attachments. Attachments are typed key/value pairs. + */ +object Attachment { + import Property.Key + + /** An implementation trait for attachments. + * Clients should inherit from Container instead. + */ + trait LinkSource { + private[Attachment] var next: Link[_] + + /** Optionally get attachment corresponding to `key` */ + final def getAttachment[V](key: Key[V]): Option[V] = { + val nx = next + if (nx == null) None + else if (nx.key eq key) Some(nx.value.asInstanceOf[V]) + else nx.getAttachment[V](key) + } + + /** The attachment corresponding to `key`. + * @throws NoSuchElementException if no attachment with key exists + */ + final def attachment[V](key: Key[V]): V = { + val nx = next + if (nx == null) throw new NoSuchElementException + else if (nx.key eq key) nx.value.asInstanceOf[V] + else nx.attachment(key) + } + + /** The attachment corresponding to `key`, or `default` + * if no attachment with `key` exists. + */ + final def attachmentOrElse[V](key: Key[V], default: V): V = { + val nx = next + if (nx == null) default + else if (nx.key eq key) nx.value.asInstanceOf[V] + else nx.attachmentOrElse(key, default) + } + + /** Add attachment with given `key` and `value`. + * @return Optionally, the old attachment with given `key` if one existed before. + * The new attachment is added at the position of the old one, or at the end + * if no attachment with same `key` existed. + */ + final def putAttachment[V](key: Key[V], value: V): Option[V] = { + val nx = next + if (nx == null) { + next = new Link(key, value, null) + None + } + else if (nx.key eq key) { + next = new Link(key, value, nx.next) + Some(nx.value.asInstanceOf[V]) + } + else nx.putAttachment(key, value) + } + + /** Remove attachment with given `key`, if it exists. + * @return Optionally, the removed attachment with given `key` if one existed before. + */ + final def removeAttachment[V](key: Key[V]): Option[V] = { + val nx = next + if (nx == null) + None + else if (nx.key eq key) { + next = nx.next + Some(nx.value.asInstanceOf[V]) + } + else nx.removeAttachment(key) + } + + /** The list of all keys and values attached to this container. */ + final def allAttachments: List[(Key[_], Any)] = { + val nx = next + if (nx == null) Nil else (nx.key, nx.value) :: nx.allAttachments + } + } + + /** A private, concrete implementation class linking attachments. + */ + private[Attachment] class Link[+V](val key: Key[V], val value: V, var next: Link[_]) + extends LinkSource + + /** A trait for objects that can contain attachments */ + trait Container extends LinkSource { + private[Attachment] var next: Link[_] = null + + final def pushAttachment[V](key: Key[V], value: V): Unit = { + assert(!getAttachment(key).isDefined, s"duplicate attachment for key $key") + next = new Link(key, value, next) + } + } +} diff --git a/compiler/src/dotty/tools/dotc/util/Chars.scala b/compiler/src/dotty/tools/dotc/util/Chars.scala new file mode 100644 index 000000000..bae3b4732 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/Chars.scala @@ -0,0 +1,96 @@ +/* NSC -- new Scala compiler + * Copyright 2006-2012 LAMP/EPFL + * @author Martin Odersky + */ +package dotty.tools.dotc +package util + +import scala.annotation.switch +import java.lang.{ Character => JCharacter } +import java.lang.{Character => JCharacter} +import java.lang.Character.LETTER_NUMBER +import java.lang.Character.LOWERCASE_LETTER +import java.lang.Character.OTHER_LETTER +import java.lang.Character.TITLECASE_LETTER +import java.lang.Character.UPPERCASE_LETTER + +/** Contains constants and classifier methods for characters */ +object Chars { + + final val LF = '\u000A' + final val FF = '\u000C' + final val CR = '\u000D' + final val SU = '\u001A' + + /** Convert a character digit to an Int according to given base, + * -1 if no success + */ + def digit2int(ch: Char, base: Int): Int = { + val num = ( + if (ch <= '9') ch - '0' + else if ('a' <= ch && ch <= 'z') ch - 'a' + 10 + else if ('A' <= ch && ch <= 'Z') ch - 'A' + 10 + else -1 + ) + if (0 <= num && num < base) num else -1 + } + /** Buffer for creating '\ u XXXX' strings. */ + private[this] val char2uescapeArray = Array[Char]('\\', 'u', 0, 0, 0, 0) + + /** Convert a character to a backslash-u escape */ + def char2uescape(c: Char): String = { + @inline def hexChar(ch: Int): Char = + (( if (ch < 10) '0' else 'A' - 10 ) + ch).toChar + + char2uescapeArray(2) = hexChar((c >> 12) ) + char2uescapeArray(3) = hexChar((c >> 8) % 16) + char2uescapeArray(4) = hexChar((c >> 4) % 16) + char2uescapeArray(5) = hexChar((c ) % 16) + + new String(char2uescapeArray) + } + + /** Is character a line break? */ + def isLineBreakChar(c: Char) = (c: @switch) match { + case LF|FF|CR|SU => true + case _ => false + } + + /** Is character a whitespace character (but not a new line)? */ + def isWhitespace(c: Char) = + c == ' ' || c == '\t' || c == CR + + /** Can character form part of a doc comment variable $xxx? */ + def isVarPart(c: Char) = + '0' <= c && c <= '9' || 'A' <= c && c <= 'Z' || 'a' <= c && c <= 'z' + + /** Can character start an alphanumeric Scala identifier? */ + def isIdentifierStart(c: Char): Boolean = + (c == '_') || (c == '$') || Character.isUnicodeIdentifierStart(c) + + /** Can character form part of an alphanumeric Scala identifier? */ + def isIdentifierPart(c: Char) = + (c == '$') || Character.isUnicodeIdentifierPart(c) + + /** Is character a math or other symbol in Unicode? */ + def isSpecial(c: Char) = { + val chtp = Character.getType(c) + chtp == Character.MATH_SYMBOL.toInt || chtp == Character.OTHER_SYMBOL.toInt + } + + private final val otherLetters = Set[Char]('\u0024', '\u005F') // '$' and '_' + private final val letterGroups = { + import JCharacter._ + Set[Byte](LOWERCASE_LETTER, UPPERCASE_LETTER, OTHER_LETTER, TITLECASE_LETTER, LETTER_NUMBER) + } + def isScalaLetter(ch: Char) = letterGroups(JCharacter.getType(ch).toByte) || otherLetters(ch) + + /** Can character form part of a Scala operator name? */ + def isOperatorPart(c : Char) : Boolean = (c: @switch) match { + case '~' | '!' | '@' | '#' | '%' | + '^' | '*' | '+' | '-' | '<' | + '>' | '?' | ':' | '=' | '&' | + '|' | '/' | '\\' => true + case c => isSpecial(c) + } +} diff --git a/compiler/src/dotty/tools/dotc/util/CommentParsing.scala b/compiler/src/dotty/tools/dotc/util/CommentParsing.scala new file mode 100644 index 000000000..cc790d683 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/CommentParsing.scala @@ -0,0 +1,239 @@ +/* + * Port of DocStrings.scala from nsc + * @author Martin Odersky + * @author Felix Mulder + */ +package dotty.tools.dotc.util + +/** The comment parsing in `dotc` is used by both the comment cooking and the + * dottydoc tool. + * + * The comment cooking is used to expand comments with `@inheritdoc` and + * `@define` annotations. The rest of the comment is untouched and later + * handled by dottydoc. + */ +object CommentParsing { + import scala.reflect.internal.Chars._ + + /** Returns index of string `str` following `start` skipping longest + * sequence of whitespace characters characters (but no newlines) + */ + def skipWhitespace(str: String, start: Int): Int = + if (start < str.length && isWhitespace(str charAt start)) skipWhitespace(str, start + 1) + else start + + /** Returns index of string `str` following `start` skipping + * sequence of identifier characters. + */ + def skipIdent(str: String, start: Int): Int = + if (start < str.length && isIdentifierPart(str charAt start)) skipIdent(str, start + 1) + else start + + /** Returns index of string `str` following `start` skipping + * sequence of identifier characters. + */ + def skipTag(str: String, start: Int): Int = + if (start < str.length && (str charAt start) == '@') skipIdent(str, start + 1) + else start + + + /** Returns index of string `str` after `start` skipping longest + * sequence of space and tab characters, possibly also containing + * a single `*` character or the `/``**` sequence. + * @pre start == str.length || str(start) == `\n` + */ + def skipLineLead(str: String, start: Int): Int = + if (start == str.length) start + else { + val idx = skipWhitespace(str, start + 1) + if (idx < str.length && (str charAt idx) == '*') skipWhitespace(str, idx + 1) + else if (idx + 2 < str.length && (str charAt idx) == '/' && (str charAt (idx + 1)) == '*' && (str charAt (idx + 2)) == '*') + skipWhitespace(str, idx + 3) + else idx + } + + /** Skips to next occurrence of `\n` or to the position after the `/``**` sequence following index `start`. + */ + def skipToEol(str: String, start: Int): Int = + if (start + 2 < str.length && (str charAt start) == '/' && (str charAt (start + 1)) == '*' && (str charAt (start + 2)) == '*') start + 3 + else if (start < str.length && (str charAt start) != '\n') skipToEol(str, start + 1) + else start + + /** Returns first index following `start` and starting a line (i.e. after skipLineLead) or starting the comment + * which satisfies predicate `p`. + */ + def findNext(str: String, start: Int)(p: Int => Boolean): Int = { + val idx = skipLineLead(str, skipToEol(str, start)) + if (idx < str.length && !p(idx)) findNext(str, idx)(p) + else idx + } + + /** Return first index following `start` and starting a line (i.e. after skipLineLead) + * which satisfies predicate `p`. + */ + def findAll(str: String, start: Int)(p: Int => Boolean): List[Int] = { + val idx = findNext(str, start)(p) + if (idx == str.length) List() + else idx :: findAll(str, idx)(p) + } + + /** Produces a string index, which is a list of `sections`, i.e + * pairs of start/end positions of all tagged sections in the string. + * Every section starts with an at sign and extends to the next at sign, + * or to the end of the comment string, but excluding the final two + * characters which terminate the comment. + * + * Also take usecases into account - they need to expand until the next + * usecase or the end of the string, as they might include other sections + * of their own + */ + def tagIndex(str: String, p: Int => Boolean = (idx => true)): List[(Int, Int)] = { + var indices = findAll(str, 0) (idx => str(idx) == '@' && p(idx)) + indices = mergeUsecaseSections(str, indices) + indices = mergeInheritdocSections(str, indices) + + indices match { + case List() => List() + case idxs => idxs zip (idxs.tail ::: List(str.length - 2)) + } + } + + /** + * Merge sections following an usecase into the usecase comment, so they + * can override the parent symbol's sections + */ + def mergeUsecaseSections(str: String, idxs: List[Int]): List[Int] = { + idxs.indexWhere(str.startsWith("@usecase", _)) match { + case firstUCIndex if firstUCIndex != -1 => + val commentSections = idxs.take(firstUCIndex) + val usecaseSections = idxs.drop(firstUCIndex).filter(str.startsWith("@usecase", _)) + commentSections ::: usecaseSections + case _ => + idxs + } + } + + /** + * Merge the inheritdoc sections, as they never make sense on their own + */ + def mergeInheritdocSections(str: String, idxs: List[Int]): List[Int] = + idxs.filterNot(str.startsWith("@inheritdoc", _)) + + /** Does interval `iv` start with given `tag`? + */ + def startsWithTag(str: String, section: (Int, Int), tag: String): Boolean = + startsWithTag(str, section._1, tag) + + def startsWithTag(str: String, start: Int, tag: String): Boolean = + str.startsWith(tag, start) && !isIdentifierPart(str charAt (start + tag.length)) + + /** The first start tag of a list of tag intervals, + * or the end of the whole comment string - 2 if list is empty + */ + def startTag(str: String, sections: List[(Int, Int)]) = sections match { + case Nil => str.length - 2 + case (start, _) :: _ => start + } + + /** A map from parameter names to start/end indices describing all parameter + * sections in `str` tagged with `tag`, where `sections` is the index of `str`. + */ + def paramDocs(str: String, tag: String, sections: List[(Int, Int)]): Map[String, (Int, Int)] = + Map() ++ { + for (section <- sections if startsWithTag(str, section, tag)) yield { + val start = skipWhitespace(str, section._1 + tag.length) + str.substring(start, skipIdent(str, start)) -> section + } + } + + /** Optionally start and end index of return section in `str`, or `None` + * if `str` does not have a @group. */ + def groupDoc(str: String, sections: List[(Int, Int)]): Option[(Int, Int)] = + sections find (startsWithTag(str, _, "@group")) + + + /** Optionally start and end index of return section in `str`, or `None` + * if `str` does not have a @return. + */ + def returnDoc(str: String, sections: List[(Int, Int)]): Option[(Int, Int)] = + sections find (startsWithTag(str, _, "@return")) + + /** Extracts variable name from a string, stripping any pair of surrounding braces */ + def variableName(str: String): String = + if (str.length >= 2 && (str charAt 0) == '{' && (str charAt (str.length - 1)) == '}') + str.substring(1, str.length - 1) + else + str + + /** Returns index following variable, or start index if no variable was recognized + */ + def skipVariable(str: String, start: Int): Int = { + var idx = start + if (idx < str.length && (str charAt idx) == '{') { + do idx += 1 + while (idx < str.length && (str charAt idx) != '}') + if (idx < str.length) idx + 1 else start + } else { + while (idx < str.length && isVarPart(str charAt idx)) + idx += 1 + idx + } + } + + /** A map from the section tag to section parameters */ + def sectionTagMap(str: String, sections: List[(Int, Int)]): Map[String, (Int, Int)] = + Map() ++ { + for (section <- sections) yield + extractSectionTag(str, section) -> section + } + + /** Extract the section tag, treating the section tag as an identifier */ + def extractSectionTag(str: String, section: (Int, Int)): String = + str.substring(section._1, skipTag(str, section._1)) + + /** Extract the section parameter */ + def extractSectionParam(str: String, section: (Int, Int)): String = { + val (beg, _) = section + assert(str.startsWith("@param", beg) || + str.startsWith("@tparam", beg) || + str.startsWith("@throws", beg)) + + val start = skipWhitespace(str, skipTag(str, beg)) + val finish = skipIdent(str, start) + + str.substring(start, finish) + } + + /** Extract the section text, except for the tag and comment newlines */ + def extractSectionText(str: String, section: (Int, Int)): (Int, Int) = { + val (beg, end) = section + if (str.startsWith("@param", beg) || + str.startsWith("@tparam", beg) || + str.startsWith("@throws", beg)) + (skipWhitespace(str, skipIdent(str, skipWhitespace(str, skipTag(str, beg)))), end) + else + (skipWhitespace(str, skipTag(str, beg)), end) + } + + /** Cleanup section text */ + def cleanupSectionText(str: String) = { + var result = str.trim.replaceAll("\n\\s+\\*\\s+", " \n") + while (result.endsWith("\n")) + result = result.substring(0, str.length - 1) + result + } + + + def removeSections(raw: String, xs: String*): String = { + val sections = tagIndex(raw) + + val toBeRemoved = for { + section <- xs + lines = sections filter { startsWithTag(raw, _, section) } + } yield lines + + val end = startTag(raw, toBeRemoved.flatten.sortBy(_._1).toList) + + if (end == raw.length - 2) raw else raw.substring(0, end) + "*/" + } +} diff --git a/compiler/src/dotty/tools/dotc/util/DiffUtil.scala b/compiler/src/dotty/tools/dotc/util/DiffUtil.scala new file mode 100644 index 000000000..b55aee719 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/DiffUtil.scala @@ -0,0 +1,174 @@ +package dotty.tools.dotc.util + +import scala.annotation.tailrec +import scala.collection.mutable + +object DiffUtil { + + private final val ANSI_DEFAULT = "\u001B[0m" + private final val ANSI_RED = "\u001B[31m" + private final val ANSI_GREEN = "\u001B[32m" + + private final val DELETION_COLOR = ANSI_RED + private final val ADDITION_COLOR = ANSI_GREEN + + @tailrec private def splitTokens(str: String, acc: List[String] = Nil): List[String] = { + if (str == "") { + acc.reverse + } else { + val head = str.charAt(0) + val (token, rest) = if (Character.isAlphabetic(head) || Character.isDigit(head)) { + str.span(c => Character.isAlphabetic(c) || Character.isDigit(c)) + } else if (Character.isMirrored(head) || Character.isWhitespace(head)) { + str.splitAt(1) + } else { + str.span { c => + !Character.isAlphabetic(c) && !Character.isDigit(c) && + !Character.isMirrored(c) && !Character.isWhitespace(c) + } + } + splitTokens(rest, token :: acc) + } + } + + + /** @return a tuple of the (found, expected, changedPercentage) diffs as strings */ + def mkColoredTypeDiff(found: String, expected: String): (String, String, Double) = { + var totalChange = 0 + val foundTokens = splitTokens(found, Nil).toArray + val expectedTokens = splitTokens(expected, Nil).toArray + + val diffExp = hirschberg(foundTokens, expectedTokens) + val diffAct = hirschberg(expectedTokens, foundTokens) + + val exp = diffExp.collect { + case Unmodified(str) => str + case Inserted(str) => + totalChange += str.length + ADDITION_COLOR + str + ANSI_DEFAULT + }.mkString + + val fnd = diffAct.collect { + case Unmodified(str) => str + case Inserted(str) => + totalChange += str.length + DELETION_COLOR + str + ANSI_DEFAULT + }.mkString + + (fnd, exp, totalChange.toDouble / (expected.length + found.length)) + } + + def mkColoredCodeDiff(code: String, lastCode: String, printDiffDel: Boolean): String = { + + val tokens = splitTokens(code, Nil).toArray + val lastTokens = splitTokens(lastCode, Nil).toArray + + val diff = hirschberg(lastTokens, tokens) + + diff.collect { + case Unmodified(str) => str + case Inserted(str) => ADDITION_COLOR + str + ANSI_DEFAULT + case Modified(old, str) if printDiffDel => DELETION_COLOR + old + ADDITION_COLOR + str + ANSI_DEFAULT + case Modified(_, str) => ADDITION_COLOR + str + ANSI_DEFAULT + case Deleted(str) if printDiffDel => DELETION_COLOR + str + ANSI_DEFAULT + }.mkString + } + + private sealed trait Patch + private final case class Unmodified(str: String) extends Patch + private final case class Modified(original: String, str: String) extends Patch + private final case class Deleted(str: String) extends Patch + private final case class Inserted(str: String) extends Patch + + private def hirschberg(a: Array[String], b: Array[String]): Array[Patch] = { + def build(x: Array[String], y: Array[String], builder: mutable.ArrayBuilder[Patch]): Unit = { + if (x.isEmpty) { + builder += Inserted(y.mkString) + } else if (y.isEmpty) { + builder += Deleted(x.mkString) + } else if (x.length == 1 || y.length == 1) { + needlemanWunsch(x, y, builder) + } else { + val xlen = x.length + val xmid = xlen / 2 + val ylen = y.length + + val (x1, x2) = x.splitAt(xmid) + val leftScore = nwScore(x1, y) + val rightScore = nwScore(x2.reverse, y.reverse) + val scoreSum = (leftScore zip rightScore.reverse).map { + case (left, right) => left + right + } + val max = scoreSum.max + val ymid = scoreSum.indexOf(max) + + val (y1, y2) = y.splitAt(ymid) + build(x1, y1, builder) + build(x2, y2, builder) + } + } + val builder = Array.newBuilder[Patch] + build(a, b, builder) + builder.result() + } + + private def nwScore(x: Array[String], y: Array[String]): Array[Int] = { + def ins(s: String) = -2 + def del(s: String) = -2 + def sub(s1: String, s2: String) = if (s1 == s2) 2 else -1 + + val score = Array.fill(x.length + 1, y.length + 1)(0) + for (j <- 1 to y.length) + score(0)(j) = score(0)(j - 1) + ins(y(j - 1)) + for (i <- 1 to x.length) { + score(i)(0) = score(i - 1)(0) + del(x(i - 1)) + for (j <- 1 to y.length) { + val scoreSub = score(i - 1)(j - 1) + sub(x(i - 1), y(j - 1)) + val scoreDel = score(i - 1)(j) + del(x(i - 1)) + val scoreIns = score(i)(j - 1) + ins(y(j - 1)) + score(i)(j) = scoreSub max scoreDel max scoreIns + } + } + Array.tabulate(y.length + 1)(j => score(x.length)(j)) + } + + private def needlemanWunsch(x: Array[String], y: Array[String], builder: mutable.ArrayBuilder[Patch]): Unit = { + def similarity(a: String, b: String) = if (a == b) 2 else -1 + val d = 1 + val score = Array.tabulate(x.length + 1, y.length + 1) { (i, j) => + if (i == 0) d * j + else if (j == 0) d * i + else 0 + } + for (i <- 1 to x.length) { + for (j <- 1 to y.length) { + val mtch = score(i - 1)(j - 1) + similarity(x(i - 1), y(j - 1)) + val delete = score(i - 1)(j) + d + val insert = score(i)(j - 1) + d + score(i)(j) = mtch max insert max delete + } + } + + var alignment = List.empty[Patch] + var i = x.length + var j = y.length + while (i > 0 || j > 0) { + if (i > 0 && j > 0 && score(i)(j) == score(i - 1)(j - 1) + similarity(x(i - 1), y(j - 1))) { + val newHead = + if (x(i - 1) == y(j - 1)) Unmodified(x(i - 1)) + else Modified(x(i - 1), y(j - 1)) + alignment = newHead :: alignment + i = i - 1 + j = j - 1 + } else if (i > 0 && score(i)(j) == score(i - 1)(j) + d) { + alignment = Deleted(x(i - 1)) :: alignment + i = i - 1 + } else { + alignment = Inserted(y(j - 1)) :: alignment + j = j - 1 + } + } + builder ++= alignment + } + +} diff --git a/compiler/src/dotty/tools/dotc/util/DotClass.scala b/compiler/src/dotty/tools/dotc/util/DotClass.scala new file mode 100644 index 000000000..cdb697a45 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/DotClass.scala @@ -0,0 +1,12 @@ +package dotty.tools.dotc.util + +/** Adds standard functionality to a class. + * For now: Just the `unsupported` method. + */ +class DotClass { + + /** Throws an `UnsupportedOperationException` with the given method name. */ + def unsupported(methodName: String): Nothing = + throw new UnsupportedOperationException(s"$getClass.$methodName") + +} diff --git a/compiler/src/dotty/tools/dotc/util/FreshNameCreator.scala b/compiler/src/dotty/tools/dotc/util/FreshNameCreator.scala new file mode 100644 index 000000000..521947895 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/FreshNameCreator.scala @@ -0,0 +1,33 @@ +package dotty.tools +package dotc +package util + +import scala.collection.mutable + +trait FreshNameCreator { + def newName(prefix: String = ""): String + + @deprecated("use newName(prefix)", "2.9.0") + def newName(pos: scala.reflect.internal.util.Position, prefix: String): String = newName(prefix) + @deprecated("use newName()", "2.9.0") + def newName(pos: scala.reflect.internal.util.Position): String = newName() +} + +object FreshNameCreator { + class Default extends FreshNameCreator { + protected var counter = 0 + protected val counters = mutable.AnyRefMap[String, Int]() withDefaultValue 0 + + /** + * Create a fresh name with the given prefix. It is guaranteed + * that the returned name has never been returned by a previous + * call to this function (provided the prefix does not end in a digit). + */ + def newName(prefix: String): String = { + val safePrefix = prefix.replaceAll("""[<>]""", """\$""") + counters(safePrefix) += 1 + val counter = counters(safePrefix) + if (prefix.isEmpty) "$" + counter + "$" else safePrefix + counter + } + } +} diff --git a/compiler/src/dotty/tools/dotc/util/HashSet.scala b/compiler/src/dotty/tools/dotc/util/HashSet.scala new file mode 100644 index 000000000..ff470ef5d --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/HashSet.scala @@ -0,0 +1,146 @@ +package dotty.tools.dotc.util + +/** A hash set that allows some privileged protected access to its internals + */ +class HashSet[T >: Null <: AnyRef](initialCapacity: Int, loadFactor: Float = 0.25f) extends Set[T] { + private var used: Int = _ + private var limit: Int = _ + private var table: Array[AnyRef] = _ + + clear() + + /** The number of elements in the set */ + def size: Int = used + + private def allocate(size: Int) = { + table = new Array[AnyRef](size) + limit = (size * loadFactor).toInt + } + + /** Remove all elements from this set and set back to initial configuration */ + def clear(): Unit = { + used = 0 + allocate(initialCapacity) + } + + /** Turn hashode `x` into a table index */ + private def index(x: Int): Int = math.abs(x % table.length) + + /** Hashcode, can be overridden */ + def hash(x: T): Int = x.hashCode + + /** Find entry such that `x equals entry`. If it exists, return it. + * If not, enter `x` in set and return `x`. + */ + def findEntryOrUpdate(x: T): T = { + var h = index(hash(x)) + var entry = table(h) + while (entry ne null) { + if (x equals entry) return entry.asInstanceOf[T] + h = index(h + 1) + entry = table(h) + } + addEntryAt(h, x) + } + + /** Add entry at `x` at index `idx` */ + private def addEntryAt(idx: Int, x: T) = { + table(idx) = x + used += 1 + if (used > limit) growTable() + x + } + + /** The entry in the set such that `x equals entry`, or else `null`. */ + def findEntry(x: T): T = { + var h = index(hash(x)) + var entry = table(h) + while ((entry ne null) && !(x equals entry)) { + h = index(h + 1) + entry = table(h) + } + entry.asInstanceOf[T] + } + + private var rover: Int = -1 + + /** Add entry `x` to set */ + def addEntry(x: T): Unit = { + var h = index(hash(x)) + var entry = table(h) + while (entry ne null) { + if (x equals entry) return + h = index(h + 1) + entry = table(h) + } + table(h) = x + used += 1 + if (used > (table.length >> 2)) growTable() + } + + /** Add all entries in `xs` to set */ + def addEntries(xs: TraversableOnce[T]): Unit = { + xs foreach addEntry + } + + /** The iterator of all elements in the set */ + def iterator = new Iterator[T] { + private var i = 0 + def hasNext: Boolean = { + while (i < table.length && (table(i) eq null)) i += 1 + i < table.length + } + def next(): T = + if (hasNext) { i += 1; table(i - 1).asInstanceOf[T] } + else null + } + + /** Privileged access: Find first entry with given hashcode */ + protected def findEntryByHash(hashCode: Int): T = { + rover = index(hashCode) + nextEntryByHash(hashCode) + } + + /** Privileged access: Find next entry with given hashcode. Needs to immediately + * follow a `findEntryByhash` or `nextEntryByHash` operation. + */ + protected def nextEntryByHash(hashCode: Int): T = { + var entry = table(rover) + while (entry ne null) { + rover = index(rover + 1) + if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T] + entry = table(rover) + } + null + } + + /** Privileged access: Add entry `x` at the last position where an unsuccsessful + * `findEntryByHash` or `nextEntryByhash` operation returned. Needs to immediately + * follow a `findEntryByhash` or `nextEntryByHash` operation that was unsucessful, + * i.e. that returned `null`. + */ + protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x) + + private def addOldEntry(x: T): Unit = { + var h = index(hash(x)) + var entry = table(h) + while (entry ne null) { + h = index(h + 1) + entry = table(h) + } + table(h) = x + } + + private def growTable(): Unit = { + val oldtable = table + allocate(table.length * 2) + var i = 0 + while (i < oldtable.length) { + val entry = oldtable(i) + if (entry ne null) addOldEntry(entry.asInstanceOf[T]) + i += 1 + } + } + + override def toString() = "HashSet(%d / %d)".format(used, table.length) +} diff --git a/compiler/src/dotty/tools/dotc/util/LRUCache.scala b/compiler/src/dotty/tools/dotc/util/LRUCache.scala new file mode 100644 index 000000000..5f53e81c4 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/LRUCache.scala @@ -0,0 +1,100 @@ +package dotty.tools.dotc.util + +import reflect.ClassTag +import annotation.tailrec + +/** A least-recently-used cache for Key -> Value computations + * It currently keeps the last 8 associations, but this can be + * changed to anywhere between 2 and 16 by changing `LRUCache.Retained`. + * + * Implementation: We keep a ring of eight places, linked + * with the `next` data structure. The ring models a priority queue. + * `last` points to the last element of the queue, and + * `next(last)` to the first one. Lookups compare keys + * sequentially from first to last. Elements with successful lookup + * get promoted to be first in the queue. Elements are evicted + * at the `last` position. + */ +class LRUCache[Key >: Null <: AnyRef : ClassTag, Value >: Null: ClassTag] { + import LRUCache._ + val keys = new Array[Key](Retained) + val values = new Array[Value](Retained) + var next = new SixteenNibbles(initialRing.bits) + var last = Retained - 1 // value is arbitrary + var lastButOne: Int = last - 1 + + def first = next(last) + + /** Lookup key, returning value or `null` for not found. + * As a side effect, sets `lastButOne` to the element before `last` + * if key was not found. + */ + def lookup(key: Key): Value = { + @tailrec + def lookupNext(prev: Int, current: Int, nx: SixteenNibbles): Value = { + val follow = nx(current) + if (keys(current) eq key) { + // arrange so that found element is at position `first`. + if (current == last) last = prev + else if (prev != last) { + next = next.updated(prev, follow) + next = next.updated(current, first) + next = next.updated(last, current) + } + values(current) + } else if (current == last) { + lastButOne = prev + null + } else + lookupNext(current, follow, nx) + } + lookupNext(last, first, next) + } + + /** Enter key/value in cache at position `last`. + * As a side effect, sets `last` to `lastButOne`. + * If `lastButOne` was set by a preceding unsuccessful `lookup` + * for the same key, this means that the new element is now the + * first in the queue. If there was no preceding lookup, the element + * is inserted at a random position in the queue. + */ + def enter(key: Key, value: Value): Unit = { + keys(last) = key + values(last) = value + last = lastButOne + } + + /** Invalidate key. The invalidated element becomes + * the last in the queue. + */ + def invalidate(key: Key): Unit = + if (lookup(key) != null) { + keys(first) = null + last = first + } + + def indices: Iterator[Int] = Iterator.iterate(first)(next.apply) + + def keysIterator: Iterator[Key] = + indices take Retained map keys filter (_ != null) + + override def toString = { + val assocs = keysIterator + .toList // double reverse so that lookups do not perturb order + .reverse + .map(key => s"$key -> ${lookup(key)}") + .reverse + s"LRUCache(${assocs.mkString(", ")})" + } +} + +object LRUCache { + + /** The number of retained elements in the cache; must be at most 16. */ + val Retained = 16 + + /** The initial ring: 0 -> 1 -> ... -> 7 -> 0 */ + val initialRing = + (new SixteenNibbles(0L) /: (0 until Retained))((nibbles, idx) => + nibbles.updated(idx, (idx + 1) % Retained)) +} diff --git a/compiler/src/dotty/tools/dotc/util/NameTransformer.scala b/compiler/src/dotty/tools/dotc/util/NameTransformer.scala new file mode 100644 index 000000000..330d513fe --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/NameTransformer.scala @@ -0,0 +1,163 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package dotty.tools.dotc +package util + +import core.Names._ +import core.Decorators._ + +/** Provides functions to encode and decode Scala symbolic names. + * Also provides some constants. + */ +object NameTransformer { + // XXX Short term: providing a way to alter these without having to recompile + // the compiler before recompiling the compiler. + val MODULE_SUFFIX_STRING = sys.props.getOrElse("SCALA_MODULE_SUFFIX_STRING", "$") + val NAME_JOIN_STRING = sys.props.getOrElse("SCALA_NAME_JOIN_STRING", "$") + val MODULE_INSTANCE_NAME = "MODULE$" + + private val nops = 128 + private val ncodes = 26 * 26 + + private class OpCodes(val op: Char, val code: String, val next: OpCodes) + + private val op2code = new Array[String](nops) + private val code2op = new Array[OpCodes](ncodes) + private def enterOp(op: Char, code: String) = { + op2code(op) = code + val c = (code.charAt(1) - 'a') * 26 + code.charAt(2) - 'a' + code2op(c) = new OpCodes(op, code, code2op(c)) + } + + /* Note: decoding assumes opcodes are only ever lowercase. */ + enterOp('~', "$tilde") + enterOp('=', "$eq") + enterOp('<', "$less") + enterOp('>', "$greater") + enterOp('!', "$bang") + enterOp('#', "$hash") + enterOp('%', "$percent") + enterOp('^', "$up") + enterOp('&', "$amp") + enterOp('|', "$bar") + enterOp('*', "$times") + enterOp('/', "$div") + enterOp('+', "$plus") + enterOp('-', "$minus") + enterOp(':', "$colon") + enterOp('\\', "$bslash") + enterOp('?', "$qmark") + enterOp('@', "$at") + + /** Replace operator symbols by corresponding `\$opname`. + * + * @param name the string to encode + * @return the string with all recognized opchars replaced with their encoding + */ + def encode[N <: Name](name: N): N = { + var buf: StringBuilder = null + val len = name.length + var i = 0 + while (i < len) { + val c = name(i) + if (c < nops && (op2code(c) ne null)) { + if (buf eq null) { + buf = new StringBuilder() + buf.append(name.slice(0, i)) + } + buf.append(op2code(c)) + /* Handle glyphs that are not valid Java/JVM identifiers */ + } + else if (!Character.isJavaIdentifierPart(c)) { + if (buf eq null) { + buf = new StringBuilder() + buf.append(name.slice(0, i)) + } + buf.append("$u%04X".format(c.toInt)) + } + else if (buf ne null) { + buf.append(c) + } + i += 1 + } + if (buf eq null) name + else if (name.isTermName) buf.toString.toTermName.asInstanceOf[N] + else buf.toString.toTypeName.asInstanceOf[N] + } + + /** Replace `\$opname` by corresponding operator symbol. + * + * @param name0 the string to decode + * @return the string with all recognized operator symbol encodings replaced with their name + */ + def decode(name0: String): String = { + //System.out.println("decode: " + name);//DEBUG + val name = if (name0.endsWith("<init>")) name0.substring(0, name0.length() - ("<init>").length()) + "this" + else name0 + var buf: StringBuilder = null + val len = name.length() + var i = 0 + while (i < len) { + var ops: OpCodes = null + var unicode = false + val c = name charAt i + if (c == '$' && i + 2 < len) { + val ch1 = name.charAt(i + 1) + if ('a' <= ch1 && ch1 <= 'z') { + val ch2 = name.charAt(i + 2) + if ('a' <= ch2 && ch2 <= 'z') { + ops = code2op((ch1 - 'a') * 26 + ch2 - 'a') + while ((ops ne null) && !name.startsWith(ops.code, i)) ops = ops.next + if (ops ne null) { + if (buf eq null) { + buf = new StringBuilder() + buf.append(name.substring(0, i)) + } + buf.append(ops.op) + i += ops.code.length() + } + /* Handle the decoding of Unicode glyphs that are + * not valid Java/JVM identifiers */ + } else if ((len - i) >= 6 && // Check that there are enough characters left + ch1 == 'u' && + ((Character.isDigit(ch2)) || + ('A' <= ch2 && ch2 <= 'F'))) { + /* Skip past "$u", next four should be hexadecimal */ + val hex = name.substring(i + 2, i + 6) + try { + val str = Integer.parseInt(hex, 16).toChar + if (buf eq null) { + buf = new StringBuilder() + buf.append(name.substring(0, i)) + } + buf.append(str) + /* 2 for "$u", 4 for hexadecimal number */ + i += 6 + unicode = true + } catch { + case _:NumberFormatException => + /* `hex` did not decode to a hexadecimal number, so + * do nothing. */ + } + } + } + } + /* If we didn't see an opcode or encoded Unicode glyph, and the + buffer is non-empty, write the current character and advance + one */ + if ((ops eq null) && !unicode) { + if (buf ne null) + buf.append(c) + i += 1 + } + } + //System.out.println("= " + (if (buf == null) name else buf.toString()));//DEBUG + if (buf eq null) name else buf.toString() + } +} diff --git a/compiler/src/dotty/tools/dotc/util/Positions.scala b/compiler/src/dotty/tools/dotc/util/Positions.scala new file mode 100644 index 000000000..c3890cc9a --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/Positions.scala @@ -0,0 +1,173 @@ +package dotty.tools.dotc +package util +import language.implicitConversions + +/** Position format in little endian: + * Start: unsigned 26 Bits (works for source files up to 64M) + * End: unsigned 26 Bits + * Point: unsigned 12 Bits relative to start + * NoPosition encoded as -1L (this is a normally invalid position + * because point would lie beyond end. + */ +object Positions { + + private val StartEndBits = 26 + val StartEndMask: Long = (1L << StartEndBits) - 1 + private val SyntheticPointDelta = (1 << (64 - StartEndBits * 2)) - 1 + + /** The maximal representable offset in a position */ + val MaxOffset = StartEndMask + + /** Convert offset `x` to an integer by sign extending the original + * field of `StartEndBits` width. + */ + def offsetToInt(x: Int) = + x << (32 - StartEndBits) >> (32 - StartEndBits) + + /** A position indicates a range between a start offset and an end offset. + * Positions can be synthetic or source-derived. A source-derived position + * has in addition a point lies somewhere between start and end. The point + * is roughly where the ^ would go if an error was diagnosed at that position. + * All quantities are encoded opaquely in a Long. + */ + class Position(val coords: Long) extends AnyVal { + + /** Is this position different from NoPosition? */ + def exists = this != NoPosition + + /** The start of this position. */ + def start: Int = { + assert(exists) + (coords & StartEndMask).toInt + } + + /** The end of this position */ + def end: Int = { + assert(exists) + ((coords >>> StartEndBits) & StartEndMask).toInt + } + + /** The point of this position, returns start for synthetic positions */ + def point: Int = { + assert(exists) + val poff = pointDelta + if (poff == SyntheticPointDelta) start else start + poff + } + + /** The difference between point and start in this position */ + def pointDelta = + (coords >>> (StartEndBits * 2)).toInt + + def orElse(that: Position) = + if (this.exists) this else that + + /** The union of two positions. This is the least range that encloses + * both positions. It is always a synthetic position. + */ + def union(that: Position) = + if (!this.exists) that + else if (!that.exists) this + else Position(this.start min that.start, this.end max that.end, this.point) + + /** Does the range of this position contain the one of that position? */ + def contains(that: Position): Boolean = + !that.exists || exists && (start <= that.start && end >= that.end) + + /** Is this position synthetic? */ + def isSynthetic = pointDelta == SyntheticPointDelta + + /** Is this position source-derived? */ + def isSourceDerived = !isSynthetic + + /** A position where all components are shifted by a given `offset` + * relative to this position. + */ + def shift(offset: Int) = + if (exists) fromOffsets(start + offset, end + offset, pointDelta) + else this + + /** The zero-extent position with start and end at the point of this position */ + def focus = if (exists) Position(point) else NoPosition + + /** The zero-extent position with start and end at the start of this position */ + def startPos = if (exists) Position(start) else NoPosition + + /** The zero-extent position with start and end at the end of this position */ + def endPos = if (exists) Position(end) else NoPosition + + /** A copy of this position with a different start */ + def withStart(start: Int) = + fromOffsets(start, this.end, if (isSynthetic) SyntheticPointDelta else this.point - start) + + /** A copy of this position with a different end */ + def withEnd(end: Int) = fromOffsets(this.start, end, pointDelta) + + /** A copy of this position with a different point */ + def withPoint(point: Int) = fromOffsets(this.start, this.end, point - this.start) + + /** A synthetic copy of this position */ + def toSynthetic = if (isSynthetic) this else Position(start, end) + + override def toString = { + val (left, right) = if (isSynthetic) ("<", ">") else ("[", "]") + if (exists) + s"$left$start..${if (point == start) "" else s"$point.."}$end$right" + else + s"${left}no position${right}" + } + } + + private def fromOffsets(start: Int, end: Int, pointDelta: Int) = { + //assert(start <= end || start == 1 && end == 0, s"$start..$end") + new Position( + (start & StartEndMask).toLong | + ((end & StartEndMask).toLong << StartEndBits) | + (pointDelta.toLong << (StartEndBits * 2))) + } + + /** A synthetic position with given start and end */ + def Position(start: Int, end: Int): Position = { + val pos = fromOffsets(start, end, SyntheticPointDelta) + assert(pos.isSynthetic) + pos + } + + /** A source-derived position with given start, end, and point delta */ + def Position(start: Int, end: Int, point: Int): Position = { + val pointDelta = (point - start) max 0 + val pos = fromOffsets(start, end, if (pointDelta >= SyntheticPointDelta) 0 else pointDelta) + assert(pos.isSourceDerived) + pos + } + + /** A synthetic zero-extent position that starts and ends at given `start`. */ + def Position(start: Int): Position = Position(start, start) + + /** A sentinel for a non-existing position */ + val NoPosition = Position(1, 0) + + /** The coordinate of a symbol. This is either an index or + * a zero-range position. + */ + class Coord(val encoding: Int) extends AnyVal { + def isIndex = encoding > 0 + def isPosition = encoding <= 0 + def toIndex: Int = { + assert(isIndex) + encoding - 1 + } + def toPosition = { + assert(isPosition) + if (this == NoCoord) NoPosition else Position(-1 - encoding) + } + } + + /** An index coordinate */ + implicit def indexCoord(n: Int): Coord = new Coord(n + 1) + implicit def positionCoord(pos: Position): Coord = + if (pos.exists) new Coord(-(pos.point + 1)) + else NoCoord + + /** A sentinel for a missing coordinate */ + val NoCoord = new Coord(0) +} diff --git a/compiler/src/dotty/tools/dotc/util/Property.scala b/compiler/src/dotty/tools/dotc/util/Property.scala new file mode 100644 index 000000000..608fc88e6 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/Property.scala @@ -0,0 +1,10 @@ +package dotty.tools.dotc.util + +/** Defines a key type with which to tag properties, such as attachments + * or context properties + */ +object Property { + + /** The class of keys for properties of type V */ + class Key[+V] +}
\ No newline at end of file diff --git a/compiler/src/dotty/tools/dotc/util/Set.scala b/compiler/src/dotty/tools/dotc/util/Set.scala new file mode 100644 index 000000000..3e906c6a8 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/Set.scala @@ -0,0 +1,27 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2012 LAMP/EPFL + * @author Martin Odersky + */ +package dotty.tools.dotc.util + +/** A common class for lightweight sets. + */ +abstract class Set[T >: Null] { + + def findEntry(x: T): T + + def addEntry(x: T): Unit + + def iterator: Iterator[T] + + def foreach[U](f: T => U): Unit = iterator foreach f + + def apply(x: T): Boolean = contains(x) + + def contains(x: T): Boolean = + findEntry(x) != null + + def toList = iterator.toList + + def clear: Unit +} diff --git a/compiler/src/dotty/tools/dotc/util/ShowPickled.scala b/compiler/src/dotty/tools/dotc/util/ShowPickled.scala new file mode 100644 index 000000000..477449074 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/ShowPickled.scala @@ -0,0 +1,287 @@ +package dotty.tools.dotc +package util + +import java.io.{File, FileInputStream, PrintStream} +import java.lang.Long.toHexString +import java.lang.Float.intBitsToFloat +import java.lang.Double.longBitsToDouble +import scala.reflect.internal.Flags +import scala.reflect.internal.pickling.PickleFormat +import core.unpickleScala2.PickleBuffer +import core.Names._ + +object ShowPickled { + import PickleFormat._ + + case class PickleBufferEntry(num: Int, startIndex: Int, tag: Int, bytes: Array[Byte]) { + def isName = tag == TERMname || tag == TYPEname + def hasName = tag match { + case TYPEsym | ALIASsym | CLASSsym | MODULEsym | VALsym | EXTref | EXTMODCLASSref => true + case _ => false + } + def readName = + if (isName) new String(bytes, "UTF-8") + else sys.error("%s is no name" format tagName) + def nameIndex = + if (hasName) readNat(bytes, 0) + else sys.error("%s has no name" format tagName) + + def tagName = tag2string(tag) + override def toString = "%d,%d: %s".format(num, startIndex, tagName) + } + + case class PickleBufferEntryList(entries: IndexedSeq[PickleBufferEntry]) { + def nameAt(idx: Int) = { + val entry = entries(idx) + if (entry.isName) entry.readName + else if (entry.hasName) entries(entry.nameIndex).readName + else "?" + } + } + + def makeEntryList(buf: PickleBuffer, index: Array[Int]) = { + val entries = buf.toIndexedSeq.zipWithIndex map { + case ((tag, data), num) => PickleBufferEntry(num, index(num), tag, data) + } + + PickleBufferEntryList(entries) + } + + def tag2string(tag: Int): String = tag match { + case TERMname => "TERMname" + case TYPEname => "TYPEname" + case NONEsym => "NONEsym" + case TYPEsym => "TYPEsym" + case ALIASsym => "ALIASsym" + case CLASSsym => "CLASSsym" + case MODULEsym => "MODULEsym" + case VALsym => "VALsym" + case EXTref => "EXTref" + case EXTMODCLASSref => "EXTMODCLASSref" + case NOtpe => "NOtpe" + case NOPREFIXtpe => "NOPREFIXtpe" + case THIStpe => "THIStpe" + case SINGLEtpe => "SINGLEtpe" + case CONSTANTtpe => "CONSTANTtpe" + case TYPEREFtpe => "TYPEREFtpe" + case TYPEBOUNDStpe => "TYPEBOUNDStpe" + case REFINEDtpe => "REFINEDtpe" + case CLASSINFOtpe => "CLASSINFOtpe" + case METHODtpe => "METHODtpe" + case POLYtpe => "POLYtpe" + case IMPLICITMETHODtpe => "METHODtpe" // IMPLICITMETHODtpe no longer used. + case SUPERtpe => "SUPERtpe" + case LITERALunit => "LITERALunit" + case LITERALboolean => "LITERALboolean" + case LITERALbyte => "LITERALbyte" + case LITERALshort => "LITERALshort" + case LITERALchar => "LITERALchar" + case LITERALint => "LITERALint" + case LITERALlong => "LITERALlong" + case LITERALfloat => "LITERALfloat" + case LITERALdouble => "LITERALdouble" + case LITERALstring => "LITERALstring" + case LITERALnull => "LITERALnull" + case LITERALclass => "LITERALclass" + case LITERALenum => "LITERALenum" + case SYMANNOT => "SYMANNOT" + case CHILDREN => "CHILDREN" + case ANNOTATEDtpe => "ANNOTATEDtpe" + case ANNOTINFO => "ANNOTINFO" + case ANNOTARGARRAY => "ANNOTARGARRAY" + // case DEBRUIJNINDEXtpe => "DEBRUIJNINDEXtpe" + case EXISTENTIALtpe => "EXISTENTIALtpe" + case TREE => "TREE" + case MODIFIERS => "MODIFIERS" + + case _ => "***BAD TAG***(" + tag + ")" + } + + /** Extremely regrettably, essentially copied from PickleBuffer. + */ + def readNat(data: Array[Byte], index: Int): Int = { + var idx = index + var result = 0L + var b = 0L + do { + b = data(idx) + idx += 1 + result = (result << 7) + (b & 0x7f) + } while((b & 0x80) != 0L) + + result.toInt + } + + def printFile(buf: PickleBuffer, out: PrintStream = System.out): Unit = { + out.println("Version " + buf.readNat() + "." + buf.readNat()) + val index = buf.createIndex + val entryList = makeEntryList(buf, index) + buf.readIndex = 0 + + def p(s: String) = out print s + + def printNameRef(): Unit = { + val idx = buf.readNat() + val name = entryList nameAt idx + val toPrint = " %s(%s)".format(idx, name) + + out print toPrint + } + + def printNat() = p(" " + buf.readNat()) + def printReadNat(x: Int) = p(" " + x) + + def printSymbolRef() = printNat() + def printTypeRef() = printNat() + def printConstantRef() = printNat() + def printAnnotInfoRef() = printNat() + def printConstAnnotArgRef() = printNat() + def printAnnotArgRef() = printNat() + + def printSymInfo(end: Int, isType: Boolean): Unit = { + printNameRef() + printSymbolRef() + val pflags = buf.readLongNat() + def printFlags(privateWithin: Option[Int]) = { + val accessBoundary = ( + for (idx <- privateWithin) yield { + val s = entryList nameAt idx + idx + "(" + s + ")" + } + ) + val flagString = PickleBuffer.unpickleScalaFlags(pflags, isType).toString + out.print(" %s[%s]".format(toHexString(pflags), flagString)) + } + + /** Might be info or privateWithin */ + val x = buf.readNat() + if (buf.readIndex == end) { + printFlags(None) + printReadNat(x) + } + else { + printFlags(Some(x)) + printTypeRef() + } + } + + /** Note: the entries which require some semantic analysis to be correctly + * interpreted are for the most part going to tell you the wrong thing. + * It's not so easy to duplicate the logic applied in the UnPickler. + */ + def printEntry(i: Int): Unit = { + buf.readIndex = index(i) + p(i + "," + buf.readIndex + ": ") + val tag = buf.readByte() + out.print(tag2string(tag)) + val len = buf.readNat() + val end = len + buf.readIndex + p(" " + len + ":") + tag match { + case TERMname => + out.print(" ") + out.print(termName(buf.bytes, buf.readIndex, len).toString) + buf.readIndex = end + case TYPEname => + out.print(" ") + out.print(typeName(buf.bytes, buf.readIndex, len)) + buf.readIndex = end + case TYPEsym | ALIASsym | CLASSsym | MODULEsym | VALsym => + printSymInfo(end, tag == TYPEsym || tag == ALIASsym || tag == CLASSsym) + if (tag == CLASSsym && (buf.readIndex < end)) printTypeRef() + case EXTref | EXTMODCLASSref => + printNameRef() + if (buf.readIndex < end) { printSymbolRef() } + case THIStpe => + printSymbolRef() + case SINGLEtpe => + printTypeRef(); printSymbolRef() + case CONSTANTtpe => + printTypeRef(); printConstantRef() + case TYPEREFtpe => + printTypeRef(); printSymbolRef(); buf.until(end, printTypeRef) + case TYPEBOUNDStpe => + printTypeRef(); printTypeRef() + case REFINEDtpe => + printSymbolRef(); buf.until(end, printTypeRef) + case CLASSINFOtpe => + printSymbolRef(); buf.until(end, printTypeRef) + case METHODtpe | IMPLICITMETHODtpe => + printTypeRef(); buf.until(end, printTypeRef) + case POLYtpe => + printTypeRef(); buf.until(end, printSymbolRef) + case LITERALboolean => + out.print(if (buf.readLong(len) == 0L) " false" else " true") + case LITERALbyte => + out.print(" " + buf.readLong(len).toByte) + case LITERALshort => + out.print(" " + buf.readLong(len).toShort) + case LITERALchar => + out.print(" " + buf.readLong(len).toChar) + case LITERALint => + out.print(" " + buf.readLong(len).toInt) + case LITERALlong => + out.print(" " + buf.readLong(len)) + case LITERALfloat => + out.print(" " + intBitsToFloat(buf.readLong(len).toInt)) + case LITERALdouble => + out.print(" " + longBitsToDouble(buf.readLong(len))) + case LITERALstring => + printNameRef() + case LITERALenum => + printSymbolRef() + case LITERALnull => + out.print(" <null>") + case LITERALclass => + printTypeRef() + case CHILDREN => + printSymbolRef(); buf.until(end, printSymbolRef) + case SYMANNOT => + printSymbolRef(); printTypeRef(); buf.until(end, printAnnotArgRef) + case ANNOTATEDtpe => + printTypeRef(); buf.until(end, printAnnotInfoRef) + case ANNOTINFO => + printTypeRef(); buf.until(end, printAnnotArgRef) + case ANNOTARGARRAY => + buf.until(end, printConstAnnotArgRef) + case EXISTENTIALtpe => + printTypeRef(); buf.until(end, printSymbolRef) + + case _ => + } + out.println() + if (buf.readIndex != end) { + out.println("BAD ENTRY END: computed = %d, actual = %d, bytes = %s".format( + end, buf.readIndex, buf.bytes.slice(index(i), (end max buf.readIndex)).mkString(", ") + )) + } + } + + for (i <- 0 until index.length) printEntry(i) + } + +/* + * + def fromFile(path: String) = fromBytes(io.File(path).toByteArray) + def fromName(name: String) = fromBytes(scalaSigBytesForPath(name) getOrElse Array()) + def fromBytes(data: => Array[Byte]): Option[PickleBuffer] = + try Some(new PickleBuffer(data, 0, data.length)) + catch { case _: Exception => None } + + def show(what: String, pickle: PickleBuffer) = { + Console.println(what) + val saved = pickle.readIndex + pickle.readIndex = 0 + printFile(pickle, Console.out) + pickle.readIndex = saved + } + + def main(args: Array[String]) { + args foreach { arg => + (fromFile(arg) orElse fromName(arg)) match { + case Some(pb) => show(arg + ":", pb) + case _ => Console.println("Cannot read " + arg) + } + } + }*/ +} diff --git a/compiler/src/dotty/tools/dotc/util/SimpleMap.scala b/compiler/src/dotty/tools/dotc/util/SimpleMap.scala new file mode 100644 index 000000000..b8668d7e4 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/SimpleMap.scala @@ -0,0 +1,223 @@ +package dotty.tools.dotc.util + +import collection.mutable.ListBuffer + +abstract class SimpleMap[K <: AnyRef, +V >: Null <: AnyRef] extends (K => V) { + def size: Int + def apply(k: K): V + def remove(k: K): SimpleMap[K, V] + def updated[V1 >: V <: AnyRef](k: K, v: V1): SimpleMap[K, V1] + def contains(k: K): Boolean = apply(k) != null + def mapValuesNow[V1 >: V <: AnyRef](f: (K, V1) => V1): SimpleMap[K, V1] + def foreachBinding(f: (K, V) => Unit): Unit + def map2[T](f: (K, V) => T): List[T] = { + val buf = new ListBuffer[T] + foreachBinding((k, v) => buf += f(k, v)) + buf.toList + } + def keys: List[K] = map2((k, v) => k) + def toList: List[(K, V)] = map2((k, v) => (k, v)) + override def toString = { + def assocToString(key: K, value: V) = s"$key -> $value" + map2(assocToString) mkString ("(", ", ", ")") + } +} + +object SimpleMap { + + private val CompactifyThreshold = 4 + + private object myEmpty extends SimpleMap[AnyRef, Null] { + def size = 0 + def apply(k: AnyRef) = null + def remove(k: AnyRef) = this + def updated[V1 >: Null <: AnyRef](k: AnyRef, v: V1) = new Map1(k, v) + def mapValuesNow[V1 >: Null <: AnyRef](f: (AnyRef, V1) => V1) = this + def foreachBinding(f: (AnyRef, Null) => Unit) = () + } + + def Empty[K <: AnyRef] = myEmpty.asInstanceOf[SimpleMap[K, Null]] + + class Map1[K <: AnyRef, +V >: Null <: AnyRef] (k1: K, v1: V) extends SimpleMap[K, V] { + def size = 1 + def apply(k: K) = + if (k == k1) v1 + else null + def remove(k: K) = + if (k == k1) Empty.asInstanceOf[SimpleMap[K, V]] + else this + def updated[V1 >: V <: AnyRef](k: K, v: V1) = + if (k == k1) new Map1(k, v) + else new Map2(k1, v1, k, v) + def mapValuesNow[V1 >: V <: AnyRef](f: (K, V1) => V1) = { + val w1 = f(k1, v1) + if (v1 eq w1) this else new Map1(k1, w1) + } + def foreachBinding(f: (K, V) => Unit) = f(k1, v1) + } + + class Map2[K <: AnyRef, +V >: Null <: AnyRef] (k1: K, v1: V, k2: K, v2: V) extends SimpleMap[K, V] { + def size = 2 + def apply(k: K) = + if (k == k1) v1 + else if (k == k2) v2 + else null + def remove(k: K) = + if (k == k1) new Map1(k2, v2) + else if (k == k2) new Map1(k1, v1) + else this + def updated[V1 >: V <: AnyRef](k: K, v: V1) = + if (k == k1) new Map2(k, v, k2, v2) + else if (k == k2) new Map2(k1, v1, k, v) + else new Map3(k1, v1, k2, v2, k, v) + def mapValuesNow[V1 >: V <: AnyRef](f: (K, V1) => V1) = { + val w1 = f(k1, v1); val w2 = f(k2, v2) + if ((v1 eq w1) && (v2 eq w2)) this + else new Map2(k1, w1, k2, w2) + } + def foreachBinding(f: (K, V) => Unit) = { f(k1, v1); f(k2, v2) } + } + + class Map3[K <: AnyRef, +V >: Null <: AnyRef] (k1: K, v1: V, k2: K, v2: V, k3: K, v3: V) extends SimpleMap[K, V] { + def size = 3 + def apply(k: K) = + if (k == k1) v1 + else if (k == k2) v2 + else if (k == k3) v3 + else null + def remove(k: K) = + if (k == k1) new Map2(k2, v2, k3, v3) + else if (k == k2) new Map2(k1, v1, k3, v3) + else if (k == k3) new Map2(k1, v1, k2, v2) + else this + def updated[V1 >: V <: AnyRef](k: K, v: V1) = + if (k == k1) new Map3(k, v, k2, v2, k3, v3) + else if (k == k2) new Map3(k1, v1, k, v, k3, v3) + else if (k == k3) new Map3(k1, v1, k2, v2, k, v) + else new Map4(k1, v1, k2, v2, k3, v3, k, v) + def mapValuesNow[V1 >: V <: AnyRef](f: (K, V1) => V1) = { + val w1 = f(k1, v1); val w2 = f(k2, v2); val w3 = f(k3, v3) + if ((v1 eq w1) && (v2 eq w2) && (v3 eq w3)) this + else new Map3(k1, w1, k2, w2, k3, w3) + } + def foreachBinding(f: (K, V) => Unit) = { f(k1, v1); f(k2, v2); f(k3, v3) } + } + + class Map4[K <: AnyRef, +V >: Null <: AnyRef] (k1: K, v1: V, k2: K, v2: V, k3: K, v3: V, k4: K, v4: V) extends SimpleMap[K, V] { + def size = 4 + def apply(k: K) = + if (k == k1) v1 + else if (k == k2) v2 + else if (k == k3) v3 + else if (k == k4) v4 + else null + def remove(k: K) = + if (k == k1) new Map3(k2, v2, k3, v3, k4, v4) + else if (k == k2) new Map3(k1, v1, k3, v3, k4, v4) + else if (k == k3) new Map3(k1, v1, k2, v2, k4, v4) + else if (k == k4) new Map3(k1, v1, k2, v2, k3, v3) + else this + def updated[V1 >: V <: AnyRef](k: K, v: V1) = + if (k == k1) new Map4(k, v, k2, v2, k3, v3, k4, v4) + else if (k == k2) new Map4(k1, v1, k, v, k3, v3, k4, v4) + else if (k == k3) new Map4(k1, v1, k2, v2, k, v, k4, v4) + else if (k == k4) new Map4(k1, v1, k2, v2, k3, v3, k, v) + else new MapMore(Array[AnyRef](k1, v1, k2, v2, k3, v3, k4, v4, k, v)) + def mapValuesNow[V1 >: V <: AnyRef](f: (K, V1) => V1) = { + val w1 = f(k1, v1); val w2 = f(k2, v2); val w3 = f(k3, v3); val w4 = f(k4, v4) + if ((v1 eq w1) && (v2 eq w2) && (v3 eq w3) && (v4 eq w4)) this + else new Map4(k1, w1, k2, w2, k3, w3, k4, w4) + } + def foreachBinding(f: (K, V) => Unit) = { f(k1, v1); f(k2, v2); f(k3, v3); f(k4, v4) } + } + + class MapMore[K <: AnyRef, +V >: Null <: AnyRef](bindings: Array[AnyRef]) extends SimpleMap[K, V] { + private def key(i: Int): K = bindings(i).asInstanceOf[K] + private def value(i: Int): V = bindings(i + 1).asInstanceOf[V] + + def size = bindings.length / 2 + + def apply(k: K): V = { + var i = 0 + while (i < bindings.length) { + if (bindings(i) eq k) return value(i) + i += 2 + } + null + } + + def remove(k: K): SimpleMap[K, V] = { + var i = 0 + while (i < bindings.length) { + if (bindings(i) eq k) return { + if (size == CompactifyThreshold) { + var m: SimpleMap[K, V] = Empty[K] + for (j <- 0 until bindings.length by 2) + if (j != i) m = m.updated(key(j), value(j)) + m + } else { + val bindings1 = new Array[AnyRef](bindings.length - 2) + Array.copy(bindings, 0, bindings1, 0, i) + Array.copy(bindings, i + 2, bindings1, i, bindings1.length - i) + new MapMore(bindings1) + } + } + i += 2 + } + this + } + + def updated[V1 >: V <: AnyRef](k: K, v: V1): SimpleMap[K, V] = { + var i = 0 + while (i < bindings.length) { + if (bindings(i) eq k) + return { + if (v eq bindings(i + 1)) this + else { + val bindings1 = bindings.clone + bindings1(i + 1) = v + new MapMore(bindings1) + } + } + i += 2 + } + val bindings2 = new Array[AnyRef](bindings.length + 2) + Array.copy(bindings, 0, bindings2, 0, bindings.length) + bindings2(bindings.length) = k + bindings2(bindings.length + 1) = v + new MapMore(bindings2) + } + + override def contains(k: K): Boolean = { + var i = 0 + while (i < bindings.length) { + if (bindings(i) eq k) return true + i += 2 + } + false + } + + def mapValuesNow[V1 >: V <: AnyRef](f: (K, V1) => V1) = { + var bindings1: Array[AnyRef] = bindings + var i = 0 + while (i < bindings.length) { + val v = value(i) + val v1 = f(key(i), v) + if ((v1 ne v) && (bindings1 eq bindings)) + bindings1 = bindings.clone + bindings1(i) = bindings(i) + bindings1(i + 1) = v1 + i += 2 + } + if (bindings1 eq bindings) this else new MapMore(bindings1) + } + + def foreachBinding(f: (K, V) => Unit) = { + var i = 0 + while (i < bindings.length) { + f(key(i), value(i)) + i += 2 + } + } + } +} diff --git a/compiler/src/dotty/tools/dotc/util/SixteenNibbles.scala b/compiler/src/dotty/tools/dotc/util/SixteenNibbles.scala new file mode 100644 index 000000000..93817604e --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/SixteenNibbles.scala @@ -0,0 +1,28 @@ +package dotty.tools.dotc.util + +/** An efficient implementation of sequences of 16 indexed elements with + * values 0..15 in a single Long. + * + */ +class SixteenNibbles(val bits: Long) extends AnyVal { + import SixteenNibbles._ + + def apply(idx: Int): Int = + (bits >>> (idx * Width)).toInt & Mask + + def updated(idx: Int, value: Int): SixteenNibbles = + new SixteenNibbles( + (bits & ~(LongMask << (idx * Width))) | + ((value & Mask).toLong << (idx * Width))) + + def elements: IndexedSeq[Int] = (0 until 16) map apply + + override def toString = + s"SixteenNibbles(${elements.mkString(", ")})" +} + +object SixteenNibbles { + final val Width = 4 + final val Mask = (1 << Width) - 1 + final val LongMask = Mask.toLong +} diff --git a/compiler/src/dotty/tools/dotc/util/SourceFile.scala b/compiler/src/dotty/tools/dotc/util/SourceFile.scala new file mode 100644 index 000000000..1d4c9c2ab --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/SourceFile.scala @@ -0,0 +1,145 @@ +package dotty.tools +package dotc +package util + +import scala.collection.mutable.ArrayBuffer +import dotty.tools.io._ +import annotation.tailrec +import java.util.regex.Pattern +import java.io.IOException +import Chars._ +import ScriptSourceFile._ +import Positions._ +import scala.io.Codec + +import java.util.Optional + +object ScriptSourceFile { + @sharable private val headerPattern = Pattern.compile("""^(::)?!#.*(\r|\n|\r\n)""", Pattern.MULTILINE) + private val headerStarts = List("#!", "::#!") + + def apply(file: AbstractFile, content: Array[Char]) = { + /** Length of the script header from the given content, if there is one. + * The header begins with "#!" or "::#!" and ends with a line starting + * with "!#" or "::!#". + */ + val headerLength = + if (headerStarts exists (content startsWith _)) { + val matcher = headerPattern matcher content.mkString + if (matcher.find) matcher.end + else throw new IOException("script file does not close its header with !# or ::!#") + } else 0 + new SourceFile(file, content drop headerLength) { + override val underlying = new SourceFile(file, content) + } + } +} + +case class SourceFile(file: AbstractFile, content: Array[Char]) extends interfaces.SourceFile { + + def this(_file: AbstractFile, codec: Codec) = this(_file, new String(_file.toByteArray, codec.charSet).toCharArray) + def this(sourceName: String, cs: Seq[Char]) = this(new VirtualFile(sourceName), cs.toArray) + def this(file: AbstractFile, cs: Seq[Char]) = this(file, cs.toArray) + + /** Tab increment; can be overridden */ + def tabInc = 8 + + override def name = file.name + override def path = file.path + override def jfile = Optional.ofNullable(file.file) + + override def equals(that : Any) = that match { + case that : SourceFile => file.path == that.file.path && start == that.start + case _ => false + } + override def hashCode = file.path.## + start.## + + def apply(idx: Int) = content.apply(idx) + + val length = content.length + + /** true for all source files except `NoSource` */ + def exists: Boolean = true + + /** The underlying source file */ + def underlying: SourceFile = this + + /** The start of this file in the underlying source file */ + def start = 0 + + def atPos(pos: Position): SourcePosition = + if (pos.exists) SourcePosition(underlying, pos) + else NoSourcePosition + + def isSelfContained = underlying eq this + + /** Map a position to a position in the underlying source file. + * For regular source files, simply return the argument. + */ + def positionInUltimateSource(position: SourcePosition): SourcePosition = + SourcePosition(underlying, position.pos shift start) + + private def isLineBreak(idx: Int) = + if (idx >= length) false else { + val ch = content(idx) + // don't identify the CR in CR LF as a line break, since LF will do. + if (ch == CR) (idx + 1 == length) || (content(idx + 1) != LF) + else isLineBreakChar(ch) + } + + private def calculateLineIndices(cs: Array[Char]) = { + val buf = new ArrayBuffer[Int] + buf += 0 + for (i <- 0 until cs.length) if (isLineBreak(i)) buf += i + 1 + buf += cs.length // sentinel, so that findLine below works smoother + buf.toArray + } + private lazy val lineIndices: Array[Int] = calculateLineIndices(content) + + /** Map line to offset of first character in line */ + def lineToOffset(index: Int): Int = lineIndices(index) + + /** A cache to speed up offsetToLine searches to similar lines */ + private var lastLine = 0 + + /** Convert offset to line in this source file + * Lines are numbered from 0 + */ + def offsetToLine(offset: Int): Int = { + lastLine = Util.bestFit(lineIndices, lineIndices.length, offset, lastLine) + lastLine + } + + /** The index of the first character of the line containing position `offset` */ + def startOfLine(offset: Int): Int = { + require(offset >= 0) + lineToOffset(offsetToLine(offset)) + } + + /** The start index of the line following the one containing position `offset` */ + def nextLine(offset: Int): Int = + lineToOffset(offsetToLine(offset) + 1 min lineIndices.length - 1) + + /** The content of the line containing position `offset` */ + def lineContent(offset: Int): String = + content.slice(startOfLine(offset), nextLine(offset)).mkString + + /** The column corresponding to `offset`, starting at 0 */ + def column(offset: Int): Int = { + var idx = startOfLine(offset) + var col = 0 + while (idx != offset) { + col += (if (content(idx) == '\t') (tabInc - col) % tabInc else 1) + idx += 1 + } + col + } + + override def toString = file.toString +} + +@sharable object NoSource extends SourceFile("<no source>", Nil) { + override def exists = false + override def atPos(pos: Position): SourcePosition = NoSourcePosition +} + diff --git a/compiler/src/dotty/tools/dotc/util/SourcePosition.scala b/compiler/src/dotty/tools/dotc/util/SourcePosition.scala new file mode 100644 index 000000000..aad4995d8 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/SourcePosition.scala @@ -0,0 +1,57 @@ +package dotty.tools +package dotc +package util + +import Positions.{Position, NoPosition} + +/** A source position is comprised of a position in a source file */ +case class SourcePosition(source: SourceFile, pos: Position, outer: SourcePosition = NoSourcePosition) +extends interfaces.SourcePosition { + def exists = pos.exists + + def lineContent: String = source.lineContent(point) + + def point: Int = pos.point + /** The line of the position, starting at 0 */ + def line: Int = source.offsetToLine(point) + + /** The lines of the position */ + def lines: List[Int] = + List.range(source.offsetToLine(start), source.offsetToLine(end + 1)) match { + case Nil => line :: Nil + case xs => xs + } + + def lineOffsets: List[Int] = + lines.map(source.lineToOffset(_)) + + def lineContent(lineNumber: Int): String = + source.lineContent(source.lineToOffset(lineNumber)) + + def beforeAndAfterPoint: (List[Int], List[Int]) = + lineOffsets.partition(_ <= point) + + /** The column of the position, starting at 0 */ + def column: Int = source.column(point) + + def start: Int = pos.start + def startLine: Int = source.offsetToLine(start) + def startColumn: Int = source.column(start) + + def end: Int = pos.end + def endLine: Int = source.offsetToLine(end) + def endColumn: Int = source.column(end) + + def withOuter(outer: SourcePosition) = new SourcePosition(source, pos, outer) + + override def toString = + if (source.exists) s"${source.file}:${line + 1}" + else s"(no source file, offset = ${pos.point})" +} + +/** A sentinel for a non-existing source position */ +@sharable object NoSourcePosition extends SourcePosition(NoSource, NoPosition) { + override def toString = "?" + override def withOuter(outer: SourcePosition) = outer +} + diff --git a/compiler/src/dotty/tools/dotc/util/Stats.scala b/compiler/src/dotty/tools/dotc/util/Stats.scala new file mode 100644 index 000000000..b7e0996f5 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/Stats.scala @@ -0,0 +1,78 @@ +package dotty.tools +package dotc +package util + +import core.Contexts._ +import collection.mutable + +@sharable object Stats { + + final val enabled = false + + /** The period in ms in which stack snapshots are displayed */ + final val HeartBeatPeriod = 250 + + var monitored = false + + @volatile private var stack: List[String] = Nil + + val hits = new mutable.HashMap[String, Int] { + override def default(key: String): Int = 0 + } + + @inline + def record(fn: String, n: Int = 1) = + if (enabled) doRecord(fn, n) + + private def doRecord(fn: String, n: Int) = + if (monitored) { + val name = if (fn.startsWith("member-")) "member" else fn + hits(name) += n + } + + @inline + def track[T](fn: String)(op: => T) = + if (enabled) doTrack(fn)(op) else op + + def doTrack[T](fn: String)(op: => T) = + if (monitored) { + stack = fn :: stack + record(fn) + try op + finally stack = stack.tail + } else op + + class HeartBeat extends Thread() { + @volatile private[Stats] var continue = true + + private def printStack(stack: List[String]): Unit = stack match { + case str :: rest => + printStack(rest) + print(s"-> $str ") + case Nil => + println() + print("|") + } + + override final def run(): Unit = { + Thread.sleep(HeartBeatPeriod) + printStack(stack) + if (continue) run() + } + } + + def monitorHeartBeat[T](op: => T)(implicit ctx: Context) = { + if (ctx.settings.Yheartbeat.value) { + var hb = new HeartBeat() + hb.start() + monitored = true + try op + finally { + hb.continue = false + println() + println(hits.toList.sortBy(_._2).map{ case (x, y) => s"$x -> $y" } mkString "\n") + println(s"sizes: ${ctx.base.uniquesSizes}") + } + } else op + } +} diff --git a/compiler/src/dotty/tools/dotc/util/Util.scala b/compiler/src/dotty/tools/dotc/util/Util.scala new file mode 100644 index 000000000..0d37f687b --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/Util.scala @@ -0,0 +1,32 @@ +package dotty.tools.dotc.util +import reflect.ClassTag + +object Util { + + /** The index `i` in `candidates.indices` such that `candidates(i) <= x` and + * `candidates(i)` is closest to `x`, determined by binary search, or -1 + * if `x < candidates(0)`. + * @param hint If between 0 and `candidates.length` use this + * as the first search point, otherwise use + * `candidates.length/2`. + * @pre candidates is sorted + */ + def bestFit(candidates: Array[Int], length: Int, x: Int, hint: Int = -1): Int = { + def recur(lo: Int, hi: Int, mid: Int): Int = + if (x < candidates(mid)) + recur(lo, mid - 1, (lo + mid - 1) / 2) + else if (mid + 1 < length && x >= candidates(mid + 1)) + recur(mid + 1, hi, (mid + 1 + hi) / 2) + else mid + val initMid = if (0 <= hint && hint < length) hint else length / 2 + if (length == 0 || x < candidates(0)) -1 + else recur(0, length, initMid) + } + + /** An array twice the size of given array, with existing elements copied over */ + def dble[T: ClassTag](arr: Array[T]) = { + val arr1 = new Array[T](arr.length * 2) + Array.copy(arr, 0, arr1, 0, arr.length) + arr1 + } +} diff --git a/compiler/src/dotty/tools/dotc/util/common.scala b/compiler/src/dotty/tools/dotc/util/common.scala new file mode 100644 index 000000000..d9798aec5 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/common.scala @@ -0,0 +1,14 @@ +package dotty.tools.dotc +package util + +import core.Names.Name +import core.Types.WildcardType + +/** Common values hoisted out for performance */ +object common { + + val alwaysTrue = Function.const(true) _ + val alwaysZero = Function.const(0) _ + val alwaysWildcardType = Function.const(WildcardType) _ + +} diff --git a/compiler/src/dotty/tools/dotc/util/kwords.sc b/compiler/src/dotty/tools/dotc/util/kwords.sc new file mode 100644 index 000000000..94c17eaf4 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/kwords.sc @@ -0,0 +1,18 @@ +package dotty.tools.dotc.util + +import dotty.tools.dotc.parsing._ +import Scanners._ +import Tokens._ + +object kwords { + println("Welcome to the Scala worksheet") //> Welcome to the Scala worksheet + keywords.toList.map(tokenString) //> res0: List[String] = List(if, for, else, this, null, new, with, super, case, + //| case class, case object, val, abstract, final, private, protected, override + //| , implicit, var, def, type, extends, true, false, object, class, import, pac + //| kage, yield, do, trait, sealed, throw, try, catch, finally, while, return, m + //| atch, lazy, then, forSome, _, :, =, <-, =>, ';', ';', <:, >:, #, @, <%) + keywords.toList.filter(kw => tokenString(kw) == null) + //> res1: List[Int] = List() + canStartStatTokens contains CASE //> res2: Boolean = false + +}
\ No newline at end of file diff --git a/compiler/src/dotty/tools/dotc/util/lrutest.sc b/compiler/src/dotty/tools/dotc/util/lrutest.sc new file mode 100644 index 000000000..6e6328b24 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/lrutest.sc @@ -0,0 +1,40 @@ +package dotty.tools.dotc.util + +object lrutest { + println("Welcome to the Scala worksheet") //> Welcome to the Scala worksheet + val bits = new SixteenNibbles(0L) //> bits : dotty.tools.dotc.util.SixteenNibbles = SixteenNibbles(0, 0, 0, 0, 0, + //| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) + bits.updated(1, 3) //> res0: dotty.tools.dotc.util.SixteenNibbles = SixteenNibbles(0, 3, 0, 0, 0, 0 + //| , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) + LRUCache.initialRing //> res1: dotty.tools.dotc.util.SixteenNibbles = SixteenNibbles(1, 2, 3, 4, 5, 6 + //| , 7, 0, 0, 0, 0, 0, 0, 0, 0, 0) + val cache = new LRUCache[String, String] //> cache : dotty.tools.dotc.util.LRUCache[String,String] = LRUCache() + cache lookup "hi" //> res2: String = null + cache enter ("hi", "x") + cache.indices.take(10).toList //> res3: List[Int] = List(7, 0, 1, 2, 3, 4, 5, 6, 7, 0) + cache.last //> res4: Int = 6 + cache lookup "hi" //> res5: String = x + cache.indices.take(10).toList //> res6: List[Int] = List(7, 0, 1, 2, 3, 4, 5, 6, 7, 0) + + for (i <- 1 to 10) { + if (cache.lookup(i.toString) == null) + cache.enter(i.toString, i.toString) + } + + cache.indices.take(10).toList //> res7: List[Int] = List(5, 6, 7, 0, 1, 2, 3, 4, 5, 6) + cache //> res8: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(10 -> 10, 9 - + //| > 9, 8 -> 8, 7 -> 7, 6 -> 6, 5 -> 5, 4 -> 4, 3 -> 3) + cache //> res9: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(10 -> 10, 9 - + //| > 9, 8 -> 8, 7 -> 7, 6 -> 6, 5 -> 5, 4 -> 4, 3 -> 3) + cache.lookup("7") //> res10: String = 7 + cache.indices.take(10).toList //> res11: List[Int] = List(0, 5, 6, 7, 1, 2, 3, 4, 0, 5) + cache.keysIterator.toList //> res12: List[String] = List(7, 10, 9, 8, 6, 5, 4, 3) + cache.lookup("10") //> res13: String = 10 + cache.lookup("5") //> res14: String = 5 + cache //> res15: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(5 -> 5, 10 - + //| > 10, 7 -> 7, 9 -> 9, 8 -> 8, 6 -> 6, 4 -> 4, 3 -> 3) + cache.lookup("11") //> res16: String = null + cache.enter("11", "!!") + cache //> res17: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(11 -> !!, 5 + //| -> 5, 10 -> 10, 7 -> 7, 9 -> 9, 8 -> 8, 6 -> 6, 4 -> 4) +}
\ No newline at end of file |