From 8cf9d559eaec93577e16c053b5792f69bb66b06f Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Tue, 7 Feb 2017 12:02:47 +1100 Subject: Fix wildApprox function f-bounded-case-class.scala exhibited a StackOverflow in wildApprox before the fixes. The problem was due to F-bounds. Note: wildApprox is performance critical. I ran timed-bootstrap-repeated a couple of times to verify that the changes did not affect runtimes in significant ways. We should also watch out for a slowdown in the benchmark tests. --- .../src/dotty/tools/dotc/typer/Implicits.scala | 6 +- compiler/src/dotty/tools/dotc/typer/Namer.scala | 2 +- .../src/dotty/tools/dotc/typer/ProtoTypes.scala | 89 +++++++++++++--------- 3 files changed, 57 insertions(+), 40 deletions(-) (limited to 'compiler/src/dotty/tools/dotc') diff --git a/compiler/src/dotty/tools/dotc/typer/Implicits.scala b/compiler/src/dotty/tools/dotc/typer/Implicits.scala index 592e80048..cc798cdf6 100644 --- a/compiler/src/dotty/tools/dotc/typer/Implicits.scala +++ b/compiler/src/dotty/tools/dotc/typer/Implicits.scala @@ -68,9 +68,9 @@ object Implicits { case mt: MethodType => mt.isImplicit || mt.paramTypes.length != 1 || - !(argType relaxed_<:< wildApprox(mt.paramTypes.head)(ctx.fresh.setExploreTyperState)) + !(argType relaxed_<:< wildApprox(mt.paramTypes.head, null, Set.empty)(ctx.fresh.setExploreTyperState)) case rtp => - discardForView(wildApprox(rtp), argType) + discardForView(wildApprox(rtp, null, Set.empty), argType) } case tpw: TermRef => false // can't discard overloaded refs @@ -649,7 +649,7 @@ trait Implicits { self: Typer => } /** The expected type where parameters and uninstantiated typevars are replaced by wildcard types */ - val wildProto = implicitProto(pt, wildApprox(_)) + val wildProto = implicitProto(pt, wildApprox(_, null, Set.empty)) /** Search failures; overridden in ExplainedImplicitSearch */ protected def nonMatchingImplicit(ref: TermRef, trail: List[MessageContainer]): SearchFailure = NoImplicitMatches diff --git a/compiler/src/dotty/tools/dotc/typer/Namer.scala b/compiler/src/dotty/tools/dotc/typer/Namer.scala index 6bd8f6d06..ab8044c76 100644 --- a/compiler/src/dotty/tools/dotc/typer/Namer.scala +++ b/compiler/src/dotty/tools/dotc/typer/Namer.scala @@ -968,7 +968,7 @@ class Namer { typer: Typer => ctx.defContext(sym).denotNamed(original) def paramProto(paramss: List[List[Type]], idx: Int): Type = paramss match { case params :: paramss1 => - if (idx < params.length) wildApprox(params(idx)) + if (idx < params.length) wildApprox(params(idx), null, Set.empty) else paramProto(paramss1, idx - params.length) case nil => WildcardType diff --git a/compiler/src/dotty/tools/dotc/typer/ProtoTypes.scala b/compiler/src/dotty/tools/dotc/typer/ProtoTypes.scala index eb46a131f..d666b563e 100644 --- a/compiler/src/dotty/tools/dotc/typer/ProtoTypes.scala +++ b/compiler/src/dotty/tools/dotc/typer/ProtoTypes.scala @@ -437,65 +437,82 @@ object ProtoTypes { /** Approximate occurrences of parameter types and uninstantiated typevars * by wildcard types. */ - final def wildApprox(tp: Type, theMap: WildApproxMap = null)(implicit ctx: Context): Type = tp match { + final def wildApprox(tp: Type, theMap: WildApproxMap, seen: Set[PolyParam])(implicit ctx: Context): Type = tp match { case tp: NamedType => // default case, inlined for speed if (tp.symbol.isStatic) tp - else tp.derivedSelect(wildApprox(tp.prefix, theMap)) + else tp.derivedSelect(wildApprox(tp.prefix, theMap, seen)) case tp: RefinedType => // default case, inlined for speed - tp.derivedRefinedType(wildApprox(tp.parent, theMap), tp.refinedName, wildApprox(tp.refinedInfo, theMap)) + tp.derivedRefinedType( + wildApprox(tp.parent, theMap, seen), + tp.refinedName, + wildApprox(tp.refinedInfo, theMap, seen)) case tp: TypeAlias => // default case, inlined for speed - tp.derivedTypeAlias(wildApprox(tp.alias, theMap)) + tp.derivedTypeAlias(wildApprox(tp.alias, theMap, seen)) case tp @ PolyParam(poly, pnum) => - def unconstrainedApprox = WildcardType(wildApprox(poly.paramBounds(pnum)).bounds) - if (ctx.mode.is(Mode.TypevarsMissContext)) - unconstrainedApprox - else - ctx.typerState.constraint.entry(tp) match { - case bounds: TypeBounds => wildApprox(WildcardType(bounds)) - case NoType => unconstrainedApprox - case inst => wildApprox(inst) - } + def wildApproxBounds(bounds: TypeBounds) = + if (bounds.lo.isInstanceOf[NamedType] && bounds.hi.isInstanceOf[NamedType]) + WildcardType(wildApprox(bounds, theMap, seen).bounds) + else if (seen.contains(tp)) WildcardType + else WildcardType(wildApprox(bounds, theMap, seen + tp).bounds) + def unconstrainedApprox = wildApproxBounds(poly.paramBounds(pnum)) + def approxPoly = + if (ctx.mode.is(Mode.TypevarsMissContext)) unconstrainedApprox + else + ctx.typerState.constraint.entry(tp) match { + case bounds: TypeBounds => wildApproxBounds(bounds) + case NoType => unconstrainedApprox + case inst => wildApprox(inst, theMap, seen) + } + approxPoly case MethodParam(mt, pnum) => - WildcardType(TypeBounds.upper(wildApprox(mt.paramTypes(pnum)))) + WildcardType(TypeBounds.upper(wildApprox(mt.paramTypes(pnum), theMap, seen))) case tp: TypeVar => - wildApprox(tp.underlying) + wildApprox(tp.underlying, theMap, seen) case tp @ HKApply(tycon, args) => - wildApprox(tycon) match { + wildApprox(tycon, theMap, seen) match { case _: WildcardType => WildcardType // this ensures we get a * type - case tycon1 => tp.derivedAppliedType(tycon1, args.mapConserve(wildApprox(_))) + case tycon1 => tp.derivedAppliedType(tycon1, args.mapConserve(wildApprox(_, theMap, seen))) } case tp: AndType => - val tp1a = wildApprox(tp.tp1) - val tp2a = wildApprox(tp.tp2) - def wildBounds(tp: Type) = - if (tp.isInstanceOf[WildcardType]) tp.bounds else TypeBounds.upper(tp) - if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) - WildcardType(wildBounds(tp1a) & wildBounds(tp2a)) - else - tp.derivedAndType(tp1a, tp2a) + def approxAnd = { + val tp1a = wildApprox(tp.tp1, theMap, seen) + val tp2a = wildApprox(tp.tp2, theMap, seen) + def wildBounds(tp: Type) = + if (tp.isInstanceOf[WildcardType]) tp.bounds else TypeBounds.upper(tp) + if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) + WildcardType(wildBounds(tp1a) & wildBounds(tp2a)) + else + tp.derivedAndType(tp1a, tp2a) + } + approxAnd case tp: OrType => - val tp1a = wildApprox(tp.tp1) - val tp2a = wildApprox(tp.tp2) - if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) - WildcardType(tp1a.bounds | tp2a.bounds) - else - tp.derivedOrType(tp1a, tp2a) + def approxOr = { + val tp1a = wildApprox(tp.tp1, theMap, seen) + val tp2a = wildApprox(tp.tp2, theMap, seen) + if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) + WildcardType(tp1a.bounds | tp2a.bounds) + else + tp.derivedOrType(tp1a, tp2a) + } + approxOr case tp: LazyRef => WildcardType case tp: SelectionProto => - tp.derivedSelectionProto(tp.name, wildApprox(tp.memberProto), NoViewsAllowed) + tp.derivedSelectionProto(tp.name, wildApprox(tp.memberProto, theMap, seen), NoViewsAllowed) case tp: ViewProto => - tp.derivedViewProto(wildApprox(tp.argType), wildApprox(tp.resultType)) + tp.derivedViewProto( + wildApprox(tp.argType, theMap, seen), + wildApprox(tp.resultType, theMap, seen)) case _: ThisType | _: BoundType | NoPrefix => // default case, inlined for speed tp case _ => - (if (theMap != null) theMap else new WildApproxMap).mapOver(tp) + (if (theMap != null) theMap else new WildApproxMap(seen)).mapOver(tp) } @sharable object AssignProto extends UncachedGroundType with MatchAlways - private[ProtoTypes] class WildApproxMap(implicit ctx: Context) extends TypeMap { - def apply(tp: Type) = wildApprox(tp, this) + private[ProtoTypes] class WildApproxMap(val seen: Set[PolyParam])(implicit ctx: Context) extends TypeMap { + def apply(tp: Type) = wildApprox(tp, this, seen) } /** Dummy tree to be used as an argument of a FunProto or ViewProto type */ -- cgit v1.2.3