Made constraint data structures pluggable.

Factored out interface for constraints. Current implementation: NaiveConstraint.
Preparing for a more efficient one.

1 files changed, 95 insertions, 441 deletions

diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala
index 86d686d37..a5c55ccce 100644
--- a/src/dotty/tools/dotc/core/Constraint.scala
+++ b/src/dotty/tools/dotc/core/Constraint.scala
@@ -10,489 +10,143 @@ import printing.Texts._
 import config.Config
 import config.Printers._
 
-object Constraint {
-
-  /** The type of `Constraint#myMap` */
-  type ParamInfo = SimpleMap[PolyType, Array[Type]]
-
-  /** The type of `Constraint#dependents */
-  type DependentMap = SimpleMap[PolyType, Array[Set[PolyParam]]]
-
-  /** The type of functions that include or exclude a `PolyParam` in or from a set*/
-  private type DepDelta = (Set[PolyParam], PolyParam) => Set[PolyParam]
-
-  private val addDep: DepDelta = (_ + _)
-  private val removeDep: DepDelta = (_ - _)
-
-  private val NoTypeBounds = new TypeBounds(WildcardType, WildcardType) {
-    override def computeHash = unsupported("computeHash")
-  }
-
-  /** An accumulator that changes dependencies on `param`.
-   *  @param  param       The parameter to which changed dependencies refer.
-   *  @param  ofVariance  Include `PolyParams` occurring at this variance in the dependencies.
-   *  @param  delta       The dependency change to perform (add or remove).
-   */
-  private class ChangeDependencies(param: PolyParam, ofVariance: Int, delta: DepDelta)(implicit ctx: Context)
-  extends TypeAccumulator[DependentMap] {
-    def apply(deps: DependentMap, tp: Type): DependentMap = tp match {
-      case tp @ PolyParam(pt, n) if
-        this.variance == 0 || this.variance == ofVariance =>
-        val oldDeps = deps(pt)
-        val original = safeSelect(oldDeps, n)
-        val changed = delta(original, param)
-        if (original eq changed) deps
-        else {
-          val newDeps =
-            if (oldDeps == null) new Array[Set[PolyParam]](pt.paramBounds.length)
-            else oldDeps.clone
-          newDeps(n) = changed
-          deps.updated(pt, newDeps)
-        }
-      case _ => foldOver(deps, tp)
-    }
-  }
-
-  /** `deps(n)`, except that `Set()` is returned if `deps` or `deps(n)` are null */
-  private def safeSelect(deps: Array[Set[PolyParam]], n: Int) : Set[PolyParam] =
-    if (deps == null || deps(n) == null) Set()
-    else deps(n)
-}
-
-import Constraint._
-
-/** Constraint over undetermined type parameters
- *  @param myMap 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 dependents a map from PolyTypes to arrays of Sets of PolyParams.
- *               The i'th set in an array corresponding to polytype `pt` contains
- *               those dependent `PolyParam`s `dp` that have `PolyParam(pt, i)` in their bounds in
- *               significant position. A position is significant if solving the
- *               constraint for `(pt, i)` with a type higher than its lower bound
- *               would lead to a constraint for `dp` that was not looser than
- *               the existing constraint. Specifically, it means that all poly params
- *               appearing covariantly in the lower bound and contravariantly in the
- *               upper bound, as well as all poly params appearing nonvariantly are
- *               significant.
- *               The `dependents` map is maintained and queried only of `Config.trackConstrDeps` is set.
+/** Constraint over undetermined type parameters. Constraints are built
+ *  over values of the following types:
+ *  
+ *   - PolyType    A constraint constrains the type parameters of a set of PolyTypes
+ *   - PolyParam   The parameters of the constrained polytypes
+ *   - TypeVar     Every constrained parameter might be associated with a TypeVar 
+ *                 that has the PolyParam as origin.
  */
-class Constraint(private val myMap: ParamInfo,
-                 private val dependents: DependentMap) extends Showable {
-
+abstract class Constraint extends Showable {
+  
+  type This <: Constraint
+  
   /** Does the constraint's domain contain the type parameters of `pt`? */
-  def contains(pt: PolyType): Boolean = myMap(pt) != null
+  def contains(pt: PolyType): Boolean
 
   /** Does the constraint's domain contain the type parameter `param`? */
-  def contains(param: PolyParam): Boolean = {
-    val entries = myMap(param.binder)
-    entries != null && entries(param.paramNum).isInstanceOf[TypeBounds]
-  }
+  def contains(param: PolyParam): Boolean
 
   /** Does this constraint contain the type variable `tvar` and is it uninstantiated? */
-  def contains(tvar: TypeVar): Boolean = {
-    val origin = tvar.origin
-    val entries = myMap(origin.binder)
-    val pnum = origin.paramNum
-    entries != null && isBounds(entries(pnum)) && (typeVar(entries, pnum) eq tvar)
-  }
-
-  /** 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)
-
-  private def isBounds(tp: Type) = tp.isInstanceOf[TypeBounds]
-
+  def contains(tvar: TypeVar): Boolean
+  
   /** The constraint for given type parameter `param`, or NoType if `param` is not part of
    *  the constraint domain.
    */
-  def at(param: PolyParam): Type = {
-    val entries = myMap(param.binder)
-    if (entries == null) NoType else entries(param.paramNum)
-  }
-
-  /** The constraint bounds for given type parameter `param`.
-   *  @pre `param` is not part of the constraint domain.
-   */
-  def bounds(param: PolyParam): TypeBounds = at(param).asInstanceOf[TypeBounds]
-
+  def at(param: PolyParam): Type
+  
   /** The type variable corresponding to parameter `param`, or
    *  NoType, if `param` is not in constrained or is not paired with a type variable.
    */
-  def typeVarOfParam(param: PolyParam): Type = {
-    val entries = myMap(param.binder)
-    if (entries == null) NoType
-    else {
-      val tvar = typeVar(entries, param.paramNum)
-      if (tvar != null) tvar else NoType
-    }
-  }
-
-  /** Change dependencies in map `deps` to reflect new parameter bounds.
-   *  @param deps       The map to change
-   *  @param pt         the polytype that contains the parameters which might have new bounds
-   *  @param entries    the entries for the parameters which might have new bounds
-   *  @param delta      the change operation, one of `addDep` or `removeDep`.
-   *  @param cmpEntries the comparison entries or `null` if no such entries exist.
-   *                    As an optimization, only bounds that differ between `entries`
-   *                    and `cmpEntries` will record their dependencies.
-   */
-  def changeDependencies(deps: DependentMap, pt: PolyType, entries: Array[Type], delta: DepDelta, cmpEntries: Array[Type])(implicit ctx: Context): DependentMap = {
-    val limit = paramCount(entries)
-    def loop(deps: DependentMap, n: Int): DependentMap = {
-      if (n >= limit) deps
-      else {
-        val newDeps = entries(n) match {
-          case bounds @ TypeBounds(lo, hi) =>
-            val cmpBounds =
-              if (cmpEntries == null) NoTypeBounds
-              else cmpEntries(n) match {
-                case bounds: TypeBounds => bounds
-                case _ => NoTypeBounds
-              }
-            if (cmpBounds eq bounds) deps
-            else {
-              val param = PolyParam(pt, n)
-              val deps1 =
-                if (cmpBounds.lo eq lo) deps
-                else new ChangeDependencies(param, 1, delta).apply(deps, lo)
-              val deps2 =
-                if (cmpBounds.hi eq hi) deps1
-                else new ChangeDependencies(param, -1, delta).apply(deps1, hi)
-              deps2
-            }
-          case _ =>
-            deps
-        }
-        loop(newDeps, n + 1)
-      }
-    }
-    if (Config.trackConstrDeps) loop(deps, 0) else deps
-  }
-
-  /** Change dependencies to reflect all changes between the bounds in `oldMap` and `newMap`.
-   */
-  def diffDependencies(deps: DependentMap, oldMap: ParamInfo, newMap: ParamInfo)(implicit ctx: Context): DependentMap =
-    if (Config.trackConstrDeps) {
-      var d = deps
-      oldMap foreachBinding { (poly, entries) =>
-        val newEntries = newMap(poly)
-        if (newEntries ne entries) d = changeDependencies(d, poly, entries, removeDep, newEntries)
-      }
-      newMap foreachBinding { (poly, entries) =>
-        val oldEntries = oldMap(poly)
-        if (oldEntries ne entries) d = changeDependencies(d, poly, entries, addDep, oldEntries)
-      }
-      d
-    } else deps
-
-  /** The set of parameters that depend directly on `param`
-   *  according to what's stored in `dependents`.
-   */
-  def dependentParams(param: PolyParam): Set[PolyParam] =
-    safeSelect(dependents(param.binder), param.paramNum)
-
-  /** A new constraint which is derived from this constraint by adding or replacing
-   *  the entries corresponding to `pt` with `entries`.
+  def typeVarOfParam(param: PolyParam): Type
+    
+  /** The constraint bounds for given type parameter `param`.
+   *  @pre `param` is not part of the constraint domain.
    */
-  private def updateEntries(pt: PolyType, entries: Array[Type])(implicit ctx: Context) : Constraint = {
-    val res = new Constraint(
-      myMap.updated(pt, entries),
-      changeDependencies(dependents, pt, entries, addDep, myMap(pt)))
-      
-    //assert(res.domainPolys.filter(pt =>
-    //  pt.resultType.resultType.widen.classSymbol.name.toString == "Ensuring").length < 2) //DEBUG
-    if (Config.checkConstraintsNonCyclic) checkNonCyclic(pt, entries)
-    ctx.runInfo.recordConstraintSize(res, res.myMap.size)
-    res
-  }
-
-  /** Check that no constrained parameter in `pt` contains itself as a bound */
-  def checkNonCyclic(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit =
-    for ((entry, i) <- entries.zipWithIndex) {
-      val param = PolyParam(pt, i)
-      entry match {
-        case TypeBounds(lo, hi) =>
-          assert(!param.occursIn(lo, fromBelow = true), s"$param occurs below $lo")
-          assert(!param.occursIn(hi, fromBelow = false), s"$param occurs above $hi")
-        case _ =>
-      }
-    }
-
-  /** Check that no constrained parameter contains itself as a bound */
-  def checkNonCyclic()(implicit ctx: Context): Unit = {
-    for (pt <- domainPolys) checkNonCyclic(pt, myMap(pt))
-  }
-
-  /** Check that no constrained parameter contains itself as a bound,
-   *  either directly or indirectly. This should be not a structer criterion
-   *  than checkNonCyclic because transitivity should be eliminated always,
-   *  but it's good to be paranoid.
+  def bounds(param: PolyParam): TypeBounds
+  
+  /** The non-parameter bounds of this constraint.
+   *  Poly params that are `related` are not contained in the return bounds.
    */
-  def checkNonCyclicTrans()(implicit ctx: Context): Unit = {
-    for (pt <- domainPolys) 
-      checkNonCyclicTrans(pt, myMap(pt))
-  }
+  def nonParamBounds(param: PolyParam)(implicit ctx: Context): TypeBounds
   
-  def checkNonCyclicTrans(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit =
-    for ((entry, i) <- entries.zipWithIndex) {
-      def occursIn(params: Set[PolyParam], bound: Type, fromBelow: Boolean): Boolean = bound.stripTypeVar match {
-        case bound: PolyParam => 
-          params.contains(bound) || {
-            at(bound) match {
-              case TypeBounds(lo, hi) =>
-                occursIn(params + bound, if (fromBelow) lo else hi, fromBelow)
-              case _ =>
-                false
-            }
-          }
-        case bound: AndOrType =>
-          def occ1 = occursIn(params, bound.tp1, fromBelow)
-          def occ2 = occursIn(params, bound.tp2, fromBelow)
-          if (fromBelow == bound.isAnd) occ1 && occ2 else occ1 || occ2
-        case _ => false
-      }
-      val param = PolyParam(pt, i)
-      entry match {
-        case TypeBounds(lo, hi) =>
-          assert(!occursIn(Set(param), lo, fromBelow = true), s"$param occurs below $lo")
-          assert(!occursIn(Set(param), hi, fromBelow = false), s"$param occurs above $hi")
-        case _ =>
-      }
-    }
+  /** If `firstIsLower` is `param1 <:< param2`?
+   *  Otherwise, is `param2 <:< param1`?
+   */
+  def related(param1: PolyParam, param2: PolyParam, firstIsLower: Boolean)(implicit ctx: Context): Boolean
   
+  /** A new constraint which is derived from this constraint by adding
+   *  entries for all type parameters of `poly`.
+   *  @param tvars   A list of type variables associated with the params, 
+   *                 or Nil if the constraint will just be checked for
+   *                 satisfiability but will solved to give instances of
+   *                 type variables.
+   */
+  def add(poly: PolyType, tvars: List[TypeVar])(implicit ctx: Context): This
 
   /** A new constraint which is derived from this constraint by updating
    *  the entry for parameter `param` to `tpe`.
    *  @pre  `this contains param`.
+   *  
+   *  `tp` can be one of the following:
+   *  
+   *   - A TypeBounds value, indicating new constraint bounds
+   *   - Another type, indicating a solution for the parameter
    */
-  def updated(param: PolyParam, tpe: Type)(implicit ctx: Context): Constraint = {
-    val newEntries = myMap(param.binder).clone
-    newEntries(param.paramNum) = tpe
-    updateEntries(param.binder, newEntries)
-  }
-
-  /** A new constraint which is derived from this constraint by mapping
-   *  `op` over all entries of `poly`.
-   *  @pre  `this contains poly`.
-   */
-  def transformed(poly: PolyType, op: Type => Type)(implicit ctx: Context) : Constraint =
-    updateEntries(poly, myMap(poly) map op)
-
-  /** A new constraint with all entries coming from `pt` removed. */
-  def remove(pt: PolyType)(implicit ctx: Context) =
-    new Constraint(
-      myMap remove pt,
-      changeDependencies(dependents, pt, myMap(pt), removeDep, null))
-
-  /** Is entry associated with `pt` removable?
-   *  @param removedParam The index of a parameter which is still present in the
-   *                      entry array, but is going to be removed at the same step,
-   *                      or -1 if no such parameter exists.
-   */
-  def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = {
-    val entries = myMap(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
-  }
-
-  /** Drop parameter `PolyParam(poly, n)` from `bounds`,
-   *  replacing with Nothing in the lower bound and by `Any` in the upper bound.
+  def updated(param: PolyParam, tp: Type)(implicit ctx: Context): This
+  
+  /** A constraint that includes a the relationship `bound <: param` if `fromBelow` is true
+   *  or else `param <: bound` if `fromBelow` is false.
    */
-  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 order(param: PolyParam, bound: PolyParam, fromBelow: Boolean)(implicit ctx: Context): This
 
   /** A new constraint which is derived from this constraint by removing
    *  the type parameter `param` from the domain and replacing all occurrences
    *  of the parameter elsewhere in the constraint by type `tp`.
-   */
-  private def uncheckedReplace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = {
-
-    def subst(poly: PolyType, entries: Array[Type]) = {
-      var result = entries
-      var i = 0
-      while (i < paramCount(entries)) {
-        entries(i) match {
-          case oldBounds: TypeBounds =>
-            val newBounds = oldBounds.substParam(param, tp).asInstanceOf[TypeBounds]
-            if (oldBounds ne newBounds) {
-              if (result eq entries) result = entries.clone
-              result(i) = dropParamIn(newBounds, poly, i)
-            }
-          case _ =>
-        }
-        i += 1
-      }
-      result
-    }
-
-    val pt = param.binder
-    val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp)
-    val substMap = constr1.myMap mapValues subst
-    val result = new Constraint(
-      substMap,
-      diffDependencies(constr1.dependents, constr1.myMap, substMap))
-    if (Config.checkConstraintsNonCyclic) result.checkNonCyclic()
-    result
-  }
-
-  /** A new constraint which is derived from this constraint by removing
-   *  the type parameter `param` from the domain and replacing all occurrences
-   *  of the parameter elsewhere in the constraint by type `tp`.
-   *  `tp` is another polyparam, applies the necessary unifications to avoud a cyclic
+   *  If `tp` is another polyparam, applies the necessary unifications to avoid a cyclic
    *  constraint.
    */
-  def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint =
-    tp.dealias.stripTypeVar match {
-      case tp: PolyParam if this contains tp =>
-        val bs = bounds(tp)
-        if (tp == param)
-          this
-        else if (param.occursIn(bs.lo, fromBelow = true) ||
-                 param.occursIn(bs.hi, fromBelow = false))
-          unify(tp, param).uncheckedReplace(param, tp)
-        else
-          uncheckedReplace(param, tp)
-      case _ =>
-        uncheckedReplace(param, tp)
-    }
+  def replace(param: PolyParam, tp: Type)(implicit ctx: Context): This
+  
+  /** Is entry associated with `pt` removable?
+   *  @param removedParam The index of a parameter which is still present in the
+   *                      entry array, but is going to be removed at the same step,
+   *                      or -1 if no such parameter exists.
+   */
+  def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean
+  
+  /** A new constraint with all entries coming from `pt` removed. */
+  def remove(pt: PolyType)(implicit ctx: Context): This
 
   /** A constraint resulting by adding p2 = p1 to this constraint, and at the same
    *  time transferring all bounds of p2 to p1
    */
-  def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): Constraint = {
-    val p1Bounds =
-      dropParamIn(bounds(p1), p2.binder, p2.paramNum) &
-      dropParamIn(bounds(p2), p1.binder, p1.paramNum)
-    this.updated(p1, p1Bounds).updated(p2, TypeAlias(p1))
-  }
-
-  /** A new constraint which is derived from this constraint by adding
-   *  entries for all type parameters of `poly`.
-   */
-  def add(poly: PolyType, tvars: List[TypeVar] = Nil)(implicit ctx: Context) : Constraint = {
-    val nparams = poly.paramNames.length
-    val entries = new Array[Type](nparams * 2)
-    poly.paramBounds.copyToArray(entries, 0)
-    tvars.copyToArray(entries, nparams)
-    updateEntries(poly, entries)
-  }
+  def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): This
 
   /** The polytypes constrained by this constraint */
-  def domainPolys: List[PolyType] = myMap.keys
+  def domainPolys: List[PolyType]
 
   /** The polytype parameters constrained by this constraint */
-  def domainParams: List[PolyParam] =
-    for {
-      (poly, entries) <- myMap.toList
-      n <- 0 until paramCount(entries)
-      if isBounds(entries(n))
-    } yield PolyParam(poly, n)
+  def domainParams: List[PolyParam]
 
-  /** Check whether predicate holds for all parameters in constraint
-   */
-  def forallParams(p: PolyParam => Boolean): Boolean = {
-    myMap.foreachBinding { (poly, entries) =>
-      for (i <- 0 until paramCount(entries))
-        if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false
-    }
-    true
-  }
+  /** Check whether predicate holds for all parameters in constraint */
+  def forallParams(p: PolyParam => Boolean): Boolean
 
   /** Perform operation `op` on all typevars, or only on uninstantiated
    *  typevars, depending on whether `uninstOnly` is set or not.
    */
-  def foreachTypeVar(op: TypeVar => Unit): Unit =
-    myMap.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] = null
+  def foreachTypeVar(op: TypeVar => Unit): Unit
 
   /** The uninstantiated typevars of this constraint */
-  def uninstVars: collection.Seq[TypeVar] = {
-    if (myUninstVars == null) {
-      myUninstVars = new mutable.ArrayBuffer[TypeVar]
-      myMap.foreachBinding { (poly, entries) =>
-        for (i <- 0 until paramCount(entries)) {
-          typeVar(entries, i) match {
-            case tv: TypeVar if isBounds(entries(i)) => myUninstVars += tv
-            case _ =>
-          }
-        }
-      }
-    }
-    myUninstVars
-  }
+  def uninstVars: collection.Seq[TypeVar]
 
-  def constrainedTypesText(printer: Printer): Text =
-    Text(domainPolys map (_.toText(printer)), ", ")
-
-  def constraintText(indent: Int, printer: Printer): Text = {
-    val assocs =
-      for (param <- domainParams)
-      yield (" " * indent) ~ param.toText(printer) ~ at(param).toText(printer)
-    Text(assocs, "\n")
-  }
-
-  override def toText(printer: Printer): Text = {
-    val header: Text = "Constraint("
-    val uninstVarsText = " uninstVars = " ~
-      Text(uninstVars map (_.toText(printer)), ", ") ~ ";"
-    val constrainedText =
-      " constrained types = " ~ constrainedTypesText(printer) ~ ";"
-    val constraintsText =
-      " constraint = " ~ constraintText(3, printer) ~ ")"
-    Text.lines(List(header, uninstVarsText, constrainedText, constraintsText))
-  }
-}
-
-trait ConstraintRunInfo { self: RunInfo =>
-  private var maxSize = 0
-  private var maxConstraint: Constraint = _
-  def recordConstraintSize(c: Constraint, size: Int) =
-    if (size > maxSize) {
-      maxSize = size
-      maxConstraint = c
-    }
-  def printMaxConstraint()(implicit ctx: Context) =
-    if (maxSize > 0) typr.println(s"max constraint = ${maxConstraint.show}")
+ /** Check that no constrained parameter in `pt` contains itself as a bound */
+  def checkNonCyclic(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit
+  
+  /** Check that no constrained parameter contains itself as a bound */
+  def checkNonCyclic()(implicit ctx: Context): Unit
+  
+ /** Check that no constrained parameter contains itself as a bound,
+   *  either directly or indirectly. This should be not a stricter criterion
+   *  than checkNonCyclic because transitivity should be eliminated always,
+   *  but it's good to be paranoid.
+   */
+  def checkNonCyclicTrans()(implicit ctx: Context): Unit
+  
+  protected def splitParams(tp: Type, seenFromBelow: Boolean, handleParam: PolyParam => Unit)(implicit ctx: Context): Type = tp match {
+    case tp: PolyParam if contains(tp) => 
+      handleParam(tp)
+      NoType
+    case tp: AndOrType if seenFromBelow == tp.isAnd =>
+      val tp1 = splitParams(tp.tp1, seenFromBelow, handleParam)
+      val tp2 = splitParams(tp.tp2, seenFromBelow, handleParam)
+      if (tp1.exists)
+        if (tp2.exists) tp.derivedAndOrType(tp1, tp2)
+        else tp1
+      else if (tp2.exists) tp2
+      else NoType
+    case _ =>
+      tp
+  } 
 }