/* NSC -- new Scala compiler
* Copyright 2005-2013 LAMP/EPFL
* @author Paul Phillips
*/
package scala
package reflect
package internal
import scala.collection.mutable
import util.HashSet
import scala.annotation.tailrec
/** An abstraction for considering symbol pairs.
* One of the greatest sources of compiler bugs is that symbols can
* trivially lose their prefixes and turn into some completely different
* type with the smallest of errors. It is the exception not the rule
* that type comparisons are done correctly.
*
* This offers a small step toward coherence with two abstractions
* which come up over and over again:
*
* RelativeTo: operations relative to a prefix
* SymbolPair: two symbols being related somehow, plus the class
* in which the relation is being performed
*
* This is only a start, but it is a start.
*/
abstract class SymbolPairs {
val global: SymbolTable
import global._
/** Are types tp1 and tp2 equivalent seen from the perspective
* of `baseClass`? For instance List[Int] and Seq[Int] are =:=
* when viewed from IterableClass.
*/
def sameInBaseClass(baseClass: Symbol)(tp1: Type, tp2: Type) =
(tp1 baseType baseClass) =:= (tp2 baseType baseClass)
final case class SymbolPair(base: Symbol, low: Symbol, high: Symbol) {
private[this] val self = base.thisType
def pos = if (low.owner == base) low.pos else if (high.owner == base) high.pos else base.pos
def rootType: Type = self
def lowType: Type = self memberType low
def lowErased: Type = erasure.specialErasure(base)(low.tpe)
def lowClassBound: Type = classBoundAsSeen(low.tpe.typeSymbol)
def highType: Type = self memberType high
def highInfo: Type = self memberInfo high
def highErased: Type = erasure.specialErasure(base)(high.tpe)
def highClassBound: Type = classBoundAsSeen(high.tpe.typeSymbol)
def isErroneous = low.tpe.isErroneous || high.tpe.isErroneous
def sameKind = sameLength(low.typeParams, high.typeParams)
private def classBoundAsSeen(tsym: Symbol) =
tsym.classBound.asSeenFrom(rootType, tsym.owner)
private def memberDefString(sym: Symbol, where: Boolean) = {
val def_s = (
if (sym.isConstructor) s"$sym: ${self memberType sym}"
else sym defStringSeenAs (self memberType sym)
)
def_s + whereString(sym)
}
/** A string like ' at line 55' if the symbol is defined in the class
* under consideration, or ' in trait Foo' if defined elsewhere.
*/
private def whereString(sym: Symbol) =
if (sym.owner == base) " at line " + sym.pos.line else sym.locationString
def lowString = memberDefString(low, where = true)
def highString = memberDefString(high, where = true)
override def toString = sm"""
|Cursor(in $base) {
| high $highString
| erased $highErased
| infos ${high.infosString}
| low $lowString
| erased $lowErased
| infos ${low.infosString}
|}""".trim
}
/** The cursor class
* @param base the base class containing the participating symbols
*/
abstract class Cursor(val base: Symbol) {
cursor =>
final val self = base.thisType // The type relative to which symbols are seen.
private val decls = newScope // all the symbols which can take part in a pair.
private val size = bases.length
/** A symbol for which exclude returns true will not appear as
* either end of a pair.
*/
protected def exclude(sym: Symbol): Boolean
/** Does `sym1` match `sym2` such that (sym1, sym2) should be
* considered as a (lo, high) pair? Types always match. Term symbols
* match if their member types relative to `self` match.
*/
protected def matches(lo: Symbol, high: Symbol): Boolean
/** The parents and base classes of `base`. Can be refined in subclasses.
*/
protected def parents: List[Type] = base.info.parents
protected def bases: List[Symbol] = base.info.baseClasses
/** An implementation of BitSets as arrays (maybe consider collection.BitSet
* for that?) The main purpose of this is to implement
* intersectionContainsElement efficiently.
*/
private type BitSet = Array[Int]
/** A mapping from all base class indices to a bitset
* which indicates whether parents are subclasses.
*
* i \in subParents(j) iff
* exists p \in parents, b \in baseClasses:
* i = index(p)
* j = index(b)
* p isSubClass b
* p.baseType(b) == self.baseType(b)
*/
private val subParents = new Array[BitSet](size)
/** A map from baseclasses of <base> to ints, with smaller ints meaning lower in
* linearization order. Symbols that are not baseclasses map to -1.
*/
private val index = new mutable.HashMap[Symbol, Int] { override def default(key: Symbol) = -1 }
/** The scope entries that have already been visited as highSymbol
* (but may have been excluded via hasCommonParentAsSubclass.)
* These will not appear as lowSymbol.
*/
private val visited = HashSet[ScopeEntry]("visited", 64)
/** Initialization has to run now so decls is populated before
* the declaration of curEntry.
*/
init()
// The current low and high symbols; the high may be null.
private[this] var lowSymbol: Symbol = _
private[this] var highSymbol: Symbol = _
// The current entry candidates for low and high symbol.
private[this] var curEntry = decls.elems
private[this] var nextEntry = curEntry
// These fields are initially populated with a call to next().
next()
// populate the above data structures
private def init() {
// Fill `decls` with lower symbols shadowing higher ones
def fillDecls(bcs: List[Symbol], deferred: Boolean) {
if (!bcs.isEmpty) {
fillDecls(bcs.tail, deferred)
var e = bcs.head.info.decls.elems
while (e ne null) {
if (e.sym.initialize.isDeferred == deferred && !exclude(e.sym))
decls enter e.sym
e = e.next
}
}
}
var i = 0
for (bc <- bases) {
index(bc) = i
subParents(i) = new BitSet(size)
i += 1
}
for (p <- parents) {
val pIndex = index(p.typeSymbol)
if (pIndex >= 0)
for (bc <- p.baseClasses ; if sameInBaseClass(bc)(p, self)) {
val bcIndex = index(bc)
if (bcIndex >= 0)
include(subParents(bcIndex), pIndex)
}
}
// first, deferred (this will need to change if we change lookup rules!)
fillDecls(bases, deferred = true)
// then, concrete.
fillDecls(bases, deferred = false)
}
private def include(bs: BitSet, n: Int) {
val nshifted = n >> 5
val nmask = 1 << (n & 31)
bs(nshifted) |= nmask
}
/** Implements `bs1 * bs2 * {0..n} != 0`.
* Used in hasCommonParentAsSubclass */
private def intersectionContainsElementLeq(bs1: BitSet, bs2: BitSet, n: Int): Boolean = {
val nshifted = n >> 5
val nmask = 1 << (n & 31)
var i = 0
while (i < nshifted) {
if ((bs1(i) & bs2(i)) != 0) return true
i += 1
}
(bs1(nshifted) & bs2(nshifted) & (nmask | nmask - 1)) != 0
}
/** Do `sym1` and `sym2` have a common subclass in `parents`?
* In that case we do not follow their pairs.
*/
private def hasCommonParentAsSubclass(sym1: Symbol, sym2: Symbol) = {
val index1 = index(sym1.owner)
(index1 >= 0) && {
val index2 = index(sym2.owner)
(index2 >= 0) && {
intersectionContainsElementLeq(
subParents(index1), subParents(index2), index1 min index2)
}
}
}
@tailrec private def advanceNextEntry() {
if (nextEntry ne null) {
nextEntry = decls lookupNextEntry nextEntry
if (nextEntry ne null) {
val high = nextEntry.sym
val isMatch = matches(lowSymbol, high) && { visited addEntry nextEntry ; true } // side-effect visited on all matches
// skip nextEntry if a class in `parents` is a subclass of the
// owners of both low and high.
if (isMatch && !hasCommonParentAsSubclass(lowSymbol, high))
highSymbol = high
else
advanceNextEntry()
}
}
}
@tailrec private def advanceCurEntry() {
if (curEntry ne null) {
curEntry = curEntry.next
if (curEntry ne null) {
if (visited(curEntry) || exclude(curEntry.sym))
advanceCurEntry()
else
nextEntry = curEntry
}
}
}
/** The `low` and `high` symbol. In the context of overriding pairs,
* low == overriding and high == overridden.
*/
def low = lowSymbol
def high = highSymbol
def hasNext = curEntry ne null
def currentPair = new SymbolPair(base, low, high)
def iterator = new Iterator[SymbolPair] {
def hasNext = cursor.hasNext
def next() = try cursor.currentPair finally cursor.next()
}
// Note that next is called once during object initialization to
// populate the fields tracking the current symbol pair.
def next() {
if (curEntry ne null) {
lowSymbol = curEntry.sym
advanceNextEntry() // sets highSymbol
if (nextEntry eq null) {
advanceCurEntry()
next()
}
}
}
}
}
