package dotty.tools
package dotc
package core
import Types._, Contexts._, Symbols._, Decorators._
import util.SimpleMap
import collection.mutable
import printing.{Printer, Showable}
import printing.Texts._
import config.Config
import config.Printers._
import collection.immutable.BitSet
import reflect.ClassTag
object OrderingConstraint {
/** The type of `Constraint#boundsMap` */
type ParamBounds = SimpleMap[PolyType, Array[Type]]
/** The type of `Constraint#lowerMap`, `Constraint#upperMap` */
type ParamOrdering = SimpleMap[PolyType, Array[List[PolyParam]]]
/** A new constraint with given maps */
private def newConstraint(boundsMap: ParamBounds, lowerMap: ParamOrdering, upperMap: ParamOrdering)(implicit ctx: Context) : OrderingConstraint = {
val result = new OrderingConstraint(boundsMap, lowerMap, upperMap)
if (Config.checkConstraintsNonCyclic) result.checkNonCyclic()
ctx.runInfo.recordConstraintSize(result, result.boundsMap.size)
result
}
/** A lens for updating a single entry array in one of the three constraint maps */
abstract class ConstraintLens[T <: AnyRef: ClassTag] {
def entries(c: OrderingConstraint, poly: PolyType): Array[T]
def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[T])(implicit ctx: Context): OrderingConstraint
def initial: T
def apply(c: OrderingConstraint, poly: PolyType, idx: Int) = {
val es = entries(c, poly)
if (es == null) initial else es(idx)
}
/** The `current` constraint but with the entry for `param` updated to `entry`.
* `current` is used linearly. If it is different from `prev` it is
* known to be dead after the call. Hence it is OK to update destructively
* parts of `current` which are not shared by `prev`.
*/
def update(prev: OrderingConstraint, current: OrderingConstraint,
poly: PolyType, idx: Int, entry: T)(implicit ctx: Context): OrderingConstraint = {
var es = entries(current, poly)
if (es != null && (es(idx) eq entry)) current
else {
val result =
if (es == null) {
es = Array.fill(poly.paramNames.length)(initial)
updateEntries(current, poly, es)
}
else if (es ne entries(prev, poly))
current // can re-use existing entries array.
else {
es = es.clone
updateEntries(current, poly, es)
}
es(idx) = entry
result
}
}
def update(prev: OrderingConstraint, current: OrderingConstraint,
param: PolyParam, entry: T)(implicit ctx: Context): OrderingConstraint =
update(prev, current, param.binder, param.paramNum, entry)
def map(prev: OrderingConstraint, current: OrderingConstraint,
poly: PolyType, idx: Int, f: T => T)(implicit ctx: Context): OrderingConstraint =
update(prev, current, poly, idx, f(apply(current, poly, idx)))
def map(prev: OrderingConstraint, current: OrderingConstraint,
param: PolyParam, f: T => T)(implicit ctx: Context): OrderingConstraint =
map(prev, current, param.binder, param.paramNum, f)
}
val boundsLens = new ConstraintLens[Type] {
def entries(c: OrderingConstraint, poly: PolyType): Array[Type] =
c.boundsMap(poly)
def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[Type])(implicit ctx: Context): OrderingConstraint =
newConstraint(c.boundsMap.updated(poly, entries), c.lowerMap, c.upperMap)
def initial = NoType
}
val lowerLens = new ConstraintLens[List[PolyParam]] {
def entries(c: OrderingConstraint, poly: PolyType): Array[List[PolyParam]] =
c.lowerMap(poly)
def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[PolyParam]])(implicit ctx: Context): OrderingConstraint =
newConstraint(c.boundsMap, c.lowerMap.updated(poly, entries), c.upperMap)
def initial = Nil
}
val upperLens = new ConstraintLens[List[PolyParam]] {
def entries(c: OrderingConstraint, poly: PolyType): Array[List[PolyParam]] =
c.upperMap(poly)
def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[PolyParam]])(implicit ctx: Context): OrderingConstraint =
newConstraint(c.boundsMap, c.lowerMap, c.upperMap.updated(poly, entries))
def initial = Nil
}
}
import OrderingConstraint._
/** Constraint over undetermined type parameters that keeps separate maps to
* reflect parameter orderings.
* @param boundsMap a map from PolyType to arrays.
* Each array contains twice the number of entries as there a type parameters
* in the PolyType. The first half of the array contains the type bounds that constrain the
* polytype's type parameters. The second half might contain type variables that
* track the corresponding parameters, or is left empty (filled with nulls).
* An instantiated type parameter is represented by having its instance type in
* the corresponding array entry.
*
* @param lowerMap a map from PolyTypes to arrays. Each array entry corresponds
* to a parameter P of the polytype; it contains all constrained parameters
* Q that are known to be smaller than P, i.e. P <: Q.
* @param upperMap a map from PolyTypes to arrays. Each array entry corresponds
* to a parameter P of the polytype; it contains all constrained parameters
* Q that are known to be greater than P, i.e. Q <: P.
*/
class OrderingConstraint(private val boundsMap: ParamBounds,
private val lowerMap : ParamOrdering,
private val upperMap : ParamOrdering) extends Constraint {
type This = OrderingConstraint
// ----------- Basic indices --------------------------------------------------
/** The number of type parameters in the given entry array */
private def paramCount(entries: Array[Type]) = entries.length >> 1
/** The type variable corresponding to parameter numbered `n`, null if none was created */
private def typeVar(entries: Array[Type], n: Int): Type =
entries(paramCount(entries) + n)
/** The `boundsMap` entry corresponding to `param` */
def entry(param: PolyParam): Type = {
val entries = boundsMap(param.binder)
if (entries == null) NoType
else entries(param.paramNum)
}
// ----------- Contains tests --------------------------------------------------
def contains(pt: PolyType): Boolean = boundsMap(pt) != null
def contains(param: PolyParam): Boolean = {
val entries = boundsMap(param.binder)
entries != null && entries(param.paramNum).isInstanceOf[TypeBounds]
}
def contains(tvar: TypeVar): Boolean = {
val origin = tvar.origin
val entries = boundsMap(origin.binder)
val pnum = origin.paramNum
entries != null && isBounds(entries(pnum)) && (typeVar(entries, pnum) eq tvar)
}
private def isBounds(tp: Type) = tp.isInstanceOf[TypeBounds]
// ---------- Dependency handling ----------------------------------------------
def lower(param: PolyParam): List[PolyParam] = lowerLens(this, param.binder, param.paramNum)
def upper(param: PolyParam): List[PolyParam] = upperLens(this, param.binder, param.paramNum)
def minLower(param: PolyParam): List[PolyParam] = {
val all = lower(param)
all.filterNot(p => all.exists(isLess(p, _)))
}
def minUpper(param: PolyParam): List[PolyParam] = {
val all = upper(param)
all.filterNot(p => all.exists(isLess(_, p)))
}
def exclusiveLower(param: PolyParam, butNot: PolyParam): List[PolyParam] =
lower(param).filterNot(isLess(_, butNot))
def exclusiveUpper(param: PolyParam, butNot: PolyParam): List[PolyParam] =
upper(param).filterNot(isLess(butNot, _))
// ---------- Info related to PolyParams -------------------------------------------
def isLess(param1: PolyParam, param2: PolyParam): Boolean =
upper(param1).contains(param2)
def nonParamBounds(param: PolyParam): TypeBounds =
entry(param).asInstanceOf[TypeBounds]
def fullLowerBound(param: PolyParam)(implicit ctx: Context): Type =
(nonParamBounds(param).lo /: minLower(param))(_ | _)
def fullUpperBound(param: PolyParam)(implicit ctx: Context): Type =
(nonParamBounds(param).hi /: minUpper(param))(_ & _)
def fullBounds(param: PolyParam)(implicit ctx: Context): TypeBounds =
nonParamBounds(param).derivedTypeBounds(fullLowerBound(param), fullUpperBound(param))
def typeVarOfParam(param: PolyParam): Type = {
val entries = boundsMap(param.binder)
if (entries == null) NoType
else {
val tvar = typeVar(entries, param.paramNum)
if (tvar != null) tvar else NoType
}
}
// ---------- Adding PolyTypes --------------------------------------------------
/** The bound type `tp` without dependent parameters
* NoType if type consists only of dependent parameters.
* @param seenFromBelow If true, `bound` is an upper bound, else a lower bound.
*/
private def stripParams(tp: Type, paramBuf: mutable.ListBuffer[PolyParam],
isUpper: Boolean)(implicit ctx: Context): Type = tp match {
case param: PolyParam if contains(param) =>
if (!paramBuf.contains(param)) paramBuf += param
NoType
case tp: AndOrType if isUpper == tp.isAnd =>
val tp1 = stripParams(tp.tp1, paramBuf, isUpper)
val tp2 = stripParams(tp.tp2, paramBuf, isUpper)
if (tp1.exists)
if (tp2.exists) tp.derivedAndOrType(tp1, tp2)
else tp1
else tp2
case _ =>
tp
}
/** The bound type `tp` without dependent parameters.
* A top or bottom type if type consists only of dependent parameters.
* @param seenFromBelow If true, `bound` is an upper bound, else a lower bound.
*/
private def normalizedType(tp: Type, paramBuf: mutable.ListBuffer[PolyParam],
isUpper: Boolean)(implicit ctx: Context): Type =
stripParams(tp, paramBuf, isUpper)
.orElse(if (isUpper) defn.AnyType else defn.NothingType)
def add(poly: PolyType, tvars: List[TypeVar])(implicit ctx: Context): This = {
assert(!contains(poly))
val nparams = poly.paramNames.length
val entries1 = new Array[Type](nparams * 2)
poly.paramBounds.copyToArray(entries1, 0)
tvars.copyToArray(entries1, nparams)
newConstraint(boundsMap.updated(poly, entries1), lowerMap, upperMap).init(poly)
}
private def init(poly: PolyType)(implicit ctx: Context): This = {
var current = this
val loBuf, hiBuf = new mutable.ListBuffer[PolyParam]
var i = 0
while (i < poly.paramNames.length) {
val param = PolyParam(poly, i)
val bounds = nonParamBounds(param)
val lo = normalizedType(bounds.lo, loBuf, isUpper = false)
val hi = normalizedType(bounds.hi, hiBuf, isUpper = true)
current = boundsLens.update(this, current, poly, i, bounds.derivedTypeBounds(lo, hi))
current = (current /: loBuf)(order(_, _, param))
current = (current /: hiBuf)(order(_, param, _))
loBuf.clear()
hiBuf.clear()
i += 1
}
if (Config.checkConstraintsNonCyclic) checkNonCyclic()
current
}
// ---------- Updates ------------------------------------------------------------
/** An updated partial order matrix that incorporates `less` and also reflects that `param` relates
* to `p2` wrt <:< if `inOrder` is true, `>:>` otherwise.
*/
private def order(current: This, param1: PolyParam, param2: PolyParam)(implicit ctx: Context): This =
if (param1 == param2 || current.isLess(param1, param2)) this
else {
assert(contains(param1))
assert(contains(param2))
val newUpper = param2 :: exclusiveUpper(param2, param1)
val newLower = param1 :: exclusiveLower(param1, param2)
val current1 = (current /: newLower)(upperLens.map(this, _, _, newUpper ::: _))
val current2 = (current1 /: newUpper)(lowerLens.map(this, _, _, newLower ::: _))
current2
}
def addLess(param1: PolyParam, param2: PolyParam)(implicit ctx: Context): This =
order(this, param1, param2)
def updateEntry(param: PolyParam, tp: Type)(implicit ctx: Context): This =
boundsLens.update(this, this, param, tp)
def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): This = {
val p1Bounds = (nonParamBounds(p1) & nonParamBounds(p2)).substParam(p2, p1)
updateEntry(p1, p1Bounds).replace(p2, p1)
}
def narrowBound(param: PolyParam, bound: Type, isUpper: Boolean)(implicit ctx: Context): This = {
val oldBounds @ TypeBounds(lo, hi) = nonParamBounds(param)
val newBounds =
if (isUpper) oldBounds.derivedTypeBounds(lo, hi & bound)
else oldBounds.derivedTypeBounds(lo | bound, hi)
updateEntry(param, newBounds)
}
// ---------- Removals ------------------------------------------------------------
/** Drop parameter `PolyParam(poly, n)` from `bounds`,
* replacing with Nothing in the lower bound and by `Any` in the upper bound.
*/
private def dropParamIn(bounds: TypeBounds, poly: PolyType, n: Int)(implicit ctx: Context): TypeBounds = {
def drop(tp: Type): Type = tp match {
case tp: AndOrType =>
val tp1 = drop(tp.tp1)
val tp2 = drop(tp.tp2)
if (!tp1.exists) tp2
else if (!tp2.exists) tp1
else tp
case PolyParam(`poly`, `n`) => NoType
case _ => tp
}
def approx(tp: Type, limit: Type): Type = {
val tp1 = drop(tp)
if (tp1.exists || !tp.exists) tp1 else limit
}
bounds.derivedTypeBounds(
approx(bounds.lo, defn.NothingType), approx(bounds.hi, defn.AnyType))
}
def replace(param: PolyParam, tp: Type)(implicit ctx: Context): OrderingConstraint = {
val replacement = tp.dealias.stripTypeVar
if (param == replacement) this
else {
assert(replacement.isValueType)
val poly = param.binder
val idx = param.paramNum
def removeParam(ps: List[PolyParam]) =
ps.filterNot(p => p.binder.eq(poly) && p.paramNum == idx)
def replaceParam(tp: Type, atPoly: PolyType, atIdx: Int) = tp match {
case bounds: TypeBounds =>
val bounds1 = tp.substParam(param, replacement).asInstanceOf[TypeBounds]
if (bounds1 eq bounds) bounds
else dropParamIn(bounds1, atPoly, atIdx)
case _ => tp
}
var current = this
if (isRemovable(poly, idx)) current = remove(poly)
else {
current = updateEntry(param, replacement)
lowerLens.update(this, current, poly, idx, Nil)
upperLens.update(this, current, poly, idx, Nil)
}
current.foreachParam {(p, i) =>
current = boundsLens.map(this, current, p, i, replaceParam(_, p, i))
current = lowerLens.map(this, current, p, i, removeParam)
current = upperLens.map(this, current, p, i, removeParam)
}
current
}
}
def remove(pt: PolyType)(implicit ctx: Context): This =
newConstraint(boundsMap.remove(pt), lowerMap.remove(pt), upperMap.remove(pt))
def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = {
val entries = boundsMap(pt)
var noneLeft = true
var i = paramCount(entries)
while (noneLeft && i > 0) {
i -= 1
if (i != removedParam && isBounds(entries(i))) noneLeft = false
else typeVar(entries, i) match {
case tv: TypeVar =>
if (!tv.inst.exists) noneLeft = false // need to keep line around to compute instType
case _ =>
}
}
noneLeft
}
// ---------- Exploration --------------------------------------------------------
def domainPolys: List[PolyType] = boundsMap.keys
def domainParams: List[PolyParam] =
for {
(poly, entries) <- boundsMap.toList
n <- 0 until paramCount(entries)
if isBounds(entries(n))
} yield PolyParam(poly, n)
def forallParams(p: PolyParam => Boolean): Boolean = {
boundsMap.foreachBinding { (poly, entries) =>
for (i <- 0 until paramCount(entries))
if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false
}
true
}
def foreachParam(p: (PolyType, Int) => Unit): Unit =
boundsMap.foreachBinding { (poly, entries) =>
0.until(poly.paramNames.length).foreach(p(poly, _))
}
def foreachTypeVar(op: TypeVar => Unit): Unit =
boundsMap.foreachBinding { (poly, entries) =>
for (i <- 0 until paramCount(entries)) {
typeVar(entries, i) match {
case tv: TypeVar if !tv.inst.exists => op(tv)
case _ =>
}
}
}
private var myUninstVars: mutable.ArrayBuffer[TypeVar] = _
/** The uninstantiated typevars of this constraint */
def uninstVars: collection.Seq[TypeVar] = {
if (myUninstVars == null) {
myUninstVars = new mutable.ArrayBuffer[TypeVar]
boundsMap.foreachBinding { (poly, entries) =>
for (i <- 0 until paramCount(entries)) {
typeVar(entries, i) match {
case tv: TypeVar if !tv.inst.exists && isBounds(entries(i)) => myUninstVars += tv
case _ =>
}
}
}
}
myUninstVars
}
// ---------- Cyclic checking -------------------------------------------
def checkNonCyclic()(implicit ctx: Context): Unit =
domainParams.foreach(checkNonCyclic)
private def checkNonCyclic(param: PolyParam)(implicit ctx: Context): Unit =
assert(!isLess(param, param), i"cyclic constraint involving $param in $this")
// ---------- toText -----------------------------------------------------
override def toText(printer: Printer): Text = {
def entryText(tp: Type) = tp match {
case tp: TypeBounds =>
tp.toText(printer)
case _ =>
" := " ~ tp.toText(printer)
}
val indent = 3
val header: Text = "Constraint("
val uninstVarsText = " uninstVars = " ~
Text(uninstVars map (_.toText(printer)), ", ") ~ ";"
val constrainedText =
" constrained types = " ~ Text(domainPolys map (_.toText(printer)), ", ")
val boundsText =
" bounds = " ~ {
val assocs =
for (param <- domainParams)
yield (" " * indent) ~ param.toText(printer) ~ entryText(entry(param))
Text(assocs, "\n")
}
val orderingText =
" ordering = " ~ {
val deps =
for {
param <- domainParams
ups = minUpper(param)
if ups.nonEmpty
}
yield
(" " * indent) ~ param.toText(printer) ~ " <: " ~
Text(ups.map(_.toText(printer)), ", ")
Text(deps, "\n")
}
Text.lines(List(header, uninstVarsText, constrainedText, boundsText, orderingText, ")"))
}
}
