aboutsummaryrefslogtreecommitdiff
path: root/src/dotty/tools/dotc/core/SubTypers.scala
blob: 29c7b73887050383801248e31f57a13ffca894db (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
package dotty.tools.dotc.core

import Types._, Contexts._, Symbols._
import collection.mutable

object SubTypers {

  type Constraints = Map[PolyParam, TypeBounds]

  object SubTyper {
    private final val LogPendingSubTypesThreshold = 50
  }

  class SubTyper(_ctx: Context) extends DotClass {
    import SubTyper._

    implicit val ctx = _ctx

    var constraints = ctx.constraints

    private var pendingSubTypes: mutable.Set[(Type, Type)] = null
    private var recCount = 0

    def addConstraint(param: PolyParam, bounds: TypeBounds): Boolean = {
      val newbounds = constraints(param) & bounds
      constraints = constraints.updated(param, newbounds)
      newbounds.lo <:< newbounds.hi
    }

    def isSubType(tp1: Type, tp2: Type): Boolean =
      if (tp1 == NoType || tp2 == NoType) false
      else if (tp1 eq tp2) true
      else {
        val cs = constraints
        try {
          recCount += 1
          val result =
            if (recCount < LogPendingSubTypesThreshold) firstTry(tp1, tp2)
            else monitoredIsSubType(tp1, tp2)
          recCount -= 1
          if (!result) constraints = cs
          result
        } catch {
          case ex: Throwable =>
            recCount -= 1
            constraints = cs
            throw ex
        }
      }

    def monitoredIsSubType(tp1: Type, tp2: Type) = {
      if (pendingSubTypes == null)
        pendingSubTypes = new mutable.HashSet[(Type, Type)]
      val p = (tp1, tp2)
      !pendingSubTypes(p) && {
        try {
          pendingSubTypes += p
          firstTry(tp1, tp2)
        } finally {
          pendingSubTypes -= p
        }
      }
    }

    def firstTry(tp1: Type, tp2: Type): Boolean = tp2 match {
      case tp2: TypeRef =>
        tp1 match {
          case tp1: TypeRef =>
            val sym1 = tp1.symbol
            val sym2 = tp2.symbol
            val pre1 = tp1.prefix
            val pre2 = tp2.prefix
            (sym1 == sym2 && (
              ctx.erasedTypes ||
              sym1.owner.hasFlag(Flags.Package) ||
              isSubType(pre1, pre2))
              ||
              tp1.name == tp2.name &&
              isSubType(pre1, pre2) &&
              (sym2.isAbstractType || isSubType(pre2, pre1)) // ???
              ||
              (sym2.isClass) && {
                val base = tp1.baseType(sym2)
                (base ne tp1) && isSubType(base, tp2)
              }
              ||
              thirdTryRef(tp1, tp2))
          case _ =>
            secondTry(tp1, tp2)
        }
      case WildcardType | ErrorType =>
        true
      case tp2: PolyParam if (constraints contains tp2) =>
        addConstraint(tp2, TypeBounds(tp1, defn.AnyType))
      case _ =>
        secondTry(tp1, tp2)
    }


    def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match {
      case tp1: PolyParam if (constraints contains tp1) =>
        addConstraint(tp1, TypeBounds(defn.NothingType, tp2))
      case WildcardType | ErrorType =>
        true
      case _ =>
        thirdTry(tp1, tp2)
    }

    def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = (
      (tp2 == defn.SingletonType && tp1.isStable)
      ||
      (!tp2.symbol.isClass && isSubType(tp1, tp2.info.bounds.lo))
      ||
      fourthTry(tp1, tp2)
    )

    def thirdTry(tp1: Type, tp2: Type): Boolean = tp2 match {
      case tp2: TypeRef =>
        thirdTryRef(tp1, tp2)
      case AppliedType(tycon, targs) =>
        val clazz2 = tycon.typeSymbol
        val base = tp1.baseType(clazz2)
        base.exists && isSubArgs(base.typeArgs, tp2.typeArgs, clazz2.typeParams) ||
        fourthTry(tp1, tp2)
      case tp2: RefinedType =>
        isSubType(tp1, tp2.parent) &&
        ((tp2.names, tp2.infos).zipped forall ((name, info) =>
          isSubType(tp1.member(name).info, info)))
      case AndType(tp21, tp22) =>
        isSubType(tp1, tp21) && isSubType(tp1, tp22)
      case OrType(tp21, tp22) =>
        isSubType(tp1, tp21) || isSubType(tp1, tp22)
      case tp2 @ MethodType(_, formals1) =>
        tp1 match {
          case tp1 @ MethodType(_, formals2) =>
            tp1.signature == tp2.signature &&
            matchingParams(formals1, formals2, tp1.isJava, tp2.isJava) &&
            tp1.isImplicit == tp2.isImplicit &&
            isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
          case _ =>
            false
        }
      case tp2: PolyType =>
        tp1 match {
          case tp1: PolyType =>
            tp1.signature == tp2.signature &&
            (tp1.paramBounds corresponds tp2.paramBounds)(
              (b1, b2) => b1 =:= b2.subst(tp2, tp1)) &&
            isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
          case _ =>
            false
        }
      case tp2 @ ExprType(restpe1) =>
        tp1 match {
          case tp1 @ ExprType(restpe2) =>
            isSubType(restpe1, restpe2)
          case _ =>
            false
        }
      case TypeBounds(lo2, hi2) =>
        tp1 match {
          case TypeBounds(lo1, hi1) =>
            isSubType(lo2, lo1) && isSubType(hi1, hi2)
          case tp1: ClassInfo =>
            val tt = tp1.typeTemplate
            lo2 <:< tt && tt <:< hi2
          case _ =>
            false
        }
      case _ =>
        fourthTry(tp1, tp2)
    }

    def fourthTry(tp1: Type, tp2: Type): Boolean =  tp1 match {
      case tp1: TypeRef =>
        ((tp1 eq defn.NothingType)
         ||
         (tp1 eq defn.NullType) && tp2.typeSymbol.containsNull
         ||
         (!tp1.symbol.isClass && isSubType(tp1.info.bounds.hi, tp2)))
      case RefinedType(parent, _) =>
        isSubType(parent, tp2)
      case AndType(tp11, tp12) =>
        isSubType(tp11, tp2) || isSubType(tp12, tp2)
      case OrType(tp11, tp12) =>
        isSubType(tp11, tp2) && isSubType(tp12, tp2)
      case tp1: SingletonType =>
        isSubType(tp1.underlying, tp2)
      case _ =>
        false
    }

    def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[TypeSymbol]): Boolean = tparams match {
      case tparam :: tparams1 =>
        val variance = tparam.variance
        val t1 = tps1.head
        val t2 = tps2.head
        (variance > 0 || isSubType(t2, t1)) &&
        (variance < 0 || isSubType(t1, t2)) &&
        isSubArgs(tps1.tail, tps2.tail, tparams1)
      case _ =>
        assert(tps1.isEmpty && tps2.isEmpty)
        true
    }

    /** A function implementing `tp1` matches `tp2`. */
    final def matchesType(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = tp1 match {
      case tp1: MethodType =>
        tp2 match {
          case tp2: MethodType =>
            tp1.isImplicit == tp2.isImplicit &&
              matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isJava, tp2.isJava) &&
              matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), alwaysMatchSimple)
          case tp2: ExprType =>
            tp1.paramNames.isEmpty &&
              matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple)
          case _ =>
            false
        }
      case tp1: ExprType =>
        tp2 match {
          case tp2: MethodType =>
            tp2.paramNames.isEmpty &&
              matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple)
          case tp2: ExprType =>
            matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple)
          case _ =>
            matchesType(tp1.resultType, tp2, alwaysMatchSimple)
        }
      case tp1: PolyType =>
        tp2 match {
          case tp2: PolyType =>
            sameLength(tp1.paramNames, tp2.paramNames) &&
              matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), alwaysMatchSimple)
          case _ =>
            false
        }
      case _ =>
        tp2 match {
          case _: MethodType | _: PolyType =>
            false
          case _ =>
            alwaysMatchSimple || isSameType(tp1, tp2)
        }
      }

    /** Are `syms1` and `syms2` parameter lists with pairwise equivalent types? */
    private def matchingParams(formals1: List[Type], formals2: List[Type], isJava1: Boolean, isJava2: Boolean): Boolean = formals1 match {
      case Nil =>
        formals2.isEmpty
      case formal1 :: rest1 =>
        formals2 match {
          case Nil =>
            false
          case formal2 :: rest2 =>
            (formal1 =:= formal2 ||
              isJava1 && formal2 == defn.ObjectType && formal1 == defn.AnyType ||
              isJava2 && formal1 == defn.ObjectType && formal2 == defn.AnyType) &&
              matchingParams(rest1, rest2, isJava1, isJava2)
        }
    }

    def isSameType(tp1: Type, tp2: Type): Boolean =
      if (tp1 == NoType || tp2 == NoType) false
      else if (tp1 eq tp2) true
      else isSubType(tp1, tp2) && isSubType(tp2, tp1)
  }
}