diff options
author | Martin Odersky <odersky@gmail.com> | 2014-04-30 14:54:18 +0200 |
---|---|---|
committer | Dmitry Petrashko <dmitry.petrashko@gmail.com> | 2014-05-08 21:51:47 +0200 |
commit | cb1f9cb03f9610d0c6f4d8aa08b9144e90dcf2b5 (patch) | |
tree | 65d8cd832e4955b5e08aadec143a724bc9409eae /src | |
parent | 4d47745e8fbadc26aaa093b3513d1c9b42798bed (diff) | |
download | dotty-cb1f9cb03f9610d0c6f4d8aa08b9144e90dcf2b5.tar.gz dotty-cb1f9cb03f9610d0c6f4d8aa08b9144e90dcf2b5.tar.bz2 dotty-cb1f9cb03f9610d0c6f4d8aa08b9144e90dcf2b5.zip |
Optimization: Avoid substituting when checking satisfiability
Instead of replacing all constrained poly params by their lower bounds before checking satsfiability,
we now do this on the fly in the subtype tests.
Diffstat (limited to 'src')
-rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 95 |
1 files changed, 59 insertions, 36 deletions
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 319b9957e..f5f7ac367 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -32,6 +32,11 @@ class TypeComparer(initctx: Context) extends DotClass { */ protected var ignoreConstraint = false + /** Compare a solution of the constraint instead of the constrained parameters. + * The solution maps every parameter to its lower bound. + */ + protected var solvedConstraint = false + private var needsGc = false /** Is a subtype check in course? In that case we may not @@ -82,7 +87,7 @@ class TypeComparer(initctx: Context) extends DotClass { /** Map that approximates each param in constraint by its lower bound */ val approxParams = new TypeMap { def apply(tp: Type): Type = tp.stripTypeVar match { - case tp: PolyParam if constraint contains tp => + case tp: PolyParam if !solvedConstraint && (constraint contains tp) => this(constraint.bounds(tp).lo) case tp => mapOver(tp) @@ -99,16 +104,30 @@ class TypeComparer(initctx: Context) extends DotClass { /** Check whether the lower bounds of all parameters in this * constraint are a solution to the constraint. */ - def isSatisfiable: Boolean = - constraint.forallParams { poly => - val TypeBounds(lo, hi) = constraint.bounds(poly) - isSubType(approxParams(lo), approxParams(hi)) || - { ctx.log(i"sub fail $lo <:< $hi") - ctx.log(i"approximated = ${approxParams(lo)} <:< ${approxParams(hi)}") - ctx.log(TypeComparer.explained(implicit ctx => isSubType(approxParams(lo), approxParams(hi)))) - false - } - } + def isSatisfiable(useSolved: Boolean): Boolean = { + val saved = solvedConstraint + solvedConstraint = true + try + constraint.forallParams { poly => + val TypeBounds(lo, hi) = constraint.bounds(poly) + isSubType(approxParams(lo), approxParams(hi)) || + { + ctx.log(i"sub fail $lo <:< $hi") + solvedConstraint = saved + ctx.log(i"approximated = ${approxParams(lo)} <:< ${approxParams(hi)}") + ctx.log(TypeComparer.explained(implicit ctx => isSubType(approxParams(lo), approxParams(hi)))) + false + } + } + finally solvedConstraint = saved + } + + def isSatisfiable: Boolean = { + val withSolved = isSatisfiable(true) + val withoutSolved = isSatisfiable(false) + assert(withSolved == withoutSolved, i"sat diff for $constraint, with solved: $withSolved, without: $withoutSolved") + withSolved + } /** Update constraint for `param` to `bounds`, check that * new constraint is still satisfiable. @@ -193,7 +212,7 @@ class TypeComparer(initctx: Context) extends DotClass { } def isConstrained(param: PolyParam): Boolean = - !frozenConstraint && (constraint contains param) + !frozenConstraint && !solvedConstraint && (constraint contains param) /** Solve constraint set for given type parameter `param`. * If `fromBelow` is true the parameter is approximated by its lower bound, @@ -343,13 +362,15 @@ class TypeComparer(initctx: Context) extends DotClass { case tp2: ProtoType => isMatchedByProto(tp2, tp1) case tp2: PolyParam => - def comparePolyParam = { - tp2 == tp1 || - isSubTypeWhenFrozen(tp1, bounds(tp2).lo) || { - if (isConstrained(tp2)) addConstraint(tp2, tp1.widen, fromBelow = true) - else (ctx.mode is Mode.TypevarsMissContext) || secondTry(tp1, tp2) - } - } + def comparePolyParam = + tp2 == tp1 || { + if (solvedConstraint && (constraint contains tp2)) isSubType(tp1, bounds(tp2).lo) + else + isSubTypeWhenFrozen(tp1, bounds(tp2).lo) || { + if (isConstrained(tp2)) addConstraint(tp2, tp1.widen, fromBelow = true) + else (ctx.mode is Mode.TypevarsMissContext) || secondTry(tp1, tp2) + } + } comparePolyParam case tp2: BoundType => tp2 == tp1 || secondTry(tp1, tp2) @@ -383,23 +404,25 @@ class TypeComparer(initctx: Context) extends DotClass { case OrType(tp11, tp12) => isSubType(tp11, tp2) && isSubType(tp12, tp2) case tp1: PolyParam => - def comparePolyParam = { - tp1 == tp2 || - isSubTypeWhenFrozen(bounds(tp1).hi, tp2) || { - if (isConstrained(tp1)) - addConstraint(tp1, tp2, fromBelow = false) && { - if ((!frozenConstraint) && - (tp2 isRef defn.NothingClass) && - state.isGlobalCommittable) { - def msg = s"!!! instantiated to Nothing: $tp1, constraint = ${constraint.show}" - if (Config.flagInstantiationToNothing) assert(false, msg) - else ctx.log(msg) - } - true + def comparePolyParam = + tp1 == tp2 || { + if (solvedConstraint && (constraint contains tp1)) isSubType(bounds(tp1).lo, tp2) + else + isSubTypeWhenFrozen(bounds(tp1).hi, tp2) || { + if (isConstrained(tp1)) + addConstraint(tp1, tp2, fromBelow = false) && { + if ((!frozenConstraint) && + (tp2 isRef defn.NothingClass) && + state.isGlobalCommittable) { + def msg = s"!!! instantiated to Nothing: $tp1, constraint = ${constraint.show}" + if (Config.flagInstantiationToNothing) assert(false, msg) + else ctx.log(msg) + } + true + } + else (ctx.mode is Mode.TypevarsMissContext) || thirdTry(tp1, tp2) } - else (ctx.mode is Mode.TypevarsMissContext) || thirdTry(tp1, tp2) } - } comparePolyParam case tp1: BoundType => tp1 == tp2 || thirdTry(tp1, tp2) @@ -628,7 +651,7 @@ class TypeComparer(initctx: Context) extends DotClass { /** Defer constraining type variables when compared against prototypes */ def isMatchedByProto(proto: ProtoType, tp: Type) = tp.stripTypeVar match { - case tp: PolyParam if constraint contains tp => true + case tp: PolyParam if !solvedConstraint && (constraint contains tp) => true case _ => proto.isMatchedBy(tp) } @@ -657,7 +680,7 @@ class TypeComparer(initctx: Context) extends DotClass { * type variable with (the corresponding type in) `tp2` instead. */ def isCappable(tp: Type): Boolean = tp match { - case tp: PolyParam => constraint contains tp + case tp: PolyParam => !solvedConstraint && (constraint contains tp) case tp: TypeProxy => isCappable(tp.underlying) case tp: AndOrType => isCappable(tp.tp1) || isCappable(tp.tp2) case _ => false |