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
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
|
/* NSC -- new Scala compiler
*
* Copyright 2011-2013 LAMP/EPFL
* @author Adriaan Moors
*/
package scala.tools.nsc.transform.patmat
import scala.tools.nsc.symtab.Flags.{SYNTHETIC, ARTIFACT}
import scala.language.postfixOps
import scala.collection.mutable
import scala.reflect.internal.util.Statistics
import scala.reflect.internal.util.Position
/** Translate our IR (TreeMakers) into actual Scala Trees using the factory methods in MatchCodeGen.
*
* The IR is mostly concerned with sequencing, substitution, and rendering all necessary conditions,
* mostly agnostic to whether we're in optimized/pure (virtualized) mode.
*/
trait MatchTreeMaking extends MatchCodeGen with Debugging {
import global._
import definitions._
final case class Suppression(exhaustive: Boolean, unreachable: Boolean)
object Suppression {
val NoSuppression = Suppression(false, false)
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// the making of the trees
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
trait TreeMakers extends TypedSubstitution with CodegenCore {
def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree])
def analyzeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type, suppression: Suppression): Unit
def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type, matchFailGenOverride: Option[Tree => Tree], unchecked: Boolean): Option[Tree] =
None
// for catch (no need to customize match failure)
def emitTypeSwitch(bindersAndCases: List[(Symbol, List[TreeMaker])], pt: Type): Option[List[CaseDef]] =
None
abstract class TreeMaker {
def pos: Position
/** captures the scope and the value of the bindings in patterns
* important *when* the substitution happens (can't accumulate and do at once after the full matcher has been constructed)
*/
def substitution: Substitution =
if (currSub eq null) localSubstitution
else currSub
protected def localSubstitution: Substitution
private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
if (currSub ne null) {
debug.patmat("BUG: incorporateOuterSubstitution called more than once for "+ ((this, currSub, outerSubst)))
Thread.dumpStack()
}
else currSub = outerSubst >> substitution
}
private[this] var currSub: Substitution = null
/** The substitution that specifies the trees that compute the values of the subpattern binders.
*
* Should not be used to perform actual substitution!
* Only used to reason symbolically about the values the subpattern binders are bound to.
* See TreeMakerToCond#updateSubstitution.
*
* Overridden in PreserveSubPatBinders to pretend it replaces the subpattern binders by subpattern refs
* (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.)
*
* TODO: clean this up, would be nicer to have some higher-level way to compute
* the binders bound by this tree maker and the symbolic values that correspond to them
*/
def subPatternsAsSubstitution: Substitution = substitution
// build Tree that chains `next` after the current extractor
def chainBefore(next: Tree)(casegen: Casegen): Tree
}
sealed trait NoNewBinders extends TreeMaker {
protected val localSubstitution: Substitution = EmptySubstitution
}
case class TrivialTreeMaker(tree: Tree) extends TreeMaker with NoNewBinders {
def pos = tree.pos
def chainBefore(next: Tree)(casegen: Casegen): Tree = tree
}
case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker with NoNewBinders {
def pos = body.pos
def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(next eq EmptyTree)
atPos(body.pos)(casegen.one(substitution(body))) // since SubstOnly treemakers are dropped, need to do it here
override def toString = "B"+((body, matchPt))
}
case class SubstOnlyTreeMaker(prevBinder: Symbol, nextBinder: Symbol) extends TreeMaker {
val pos = NoPosition
val localSubstitution = Substitution(prevBinder, CODE.REF(nextBinder))
def chainBefore(next: Tree)(casegen: Casegen): Tree = substitution(next)
override def toString = "S"+ localSubstitution
}
sealed abstract class FunTreeMaker extends TreeMaker {
val nextBinder: Symbol
def pos = nextBinder.pos
}
sealed abstract class CondTreeMaker extends FunTreeMaker {
val prevBinder: Symbol
val nextBinderTp: Type
val cond: Tree
val res: Tree
lazy val nextBinder = freshSym(pos, nextBinderTp)
lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
def chainBefore(next: Tree)(casegen: Casegen): Tree =
atPos(pos)(casegen.flatMapCond(cond, res, nextBinder, substitution(next)))
}
// unless we're optimizing, emit local variable bindings for all subpatterns of extractor/case class patterns
protected val debugInfoEmitVars = !settings.optimise.value
sealed trait PreserveSubPatBinders extends TreeMaker {
val subPatBinders: List[Symbol]
val subPatRefs: List[Tree]
val ignoredSubPatBinders: Set[Symbol]
// unless `debugInfoEmitVars`, this set should contain the bare minimum for correctness
// mutable case class fields need to be stored regardless (SI-5158, SI-6070) -- see override in ProductExtractorTreeMaker
// sub patterns bound to wildcard (_) are never stored as they can't be referenced
// dirty debuggers will have to get dirty to see the wildcards
lazy val storedBinders: Set[Symbol] =
(if (debugInfoEmitVars) subPatBinders.toSet else Set.empty) ++ extraStoredBinders -- ignoredSubPatBinders
// e.g., mutable fields of a case class in ProductExtractorTreeMaker
def extraStoredBinders: Set[Symbol]
def emitVars = storedBinders.nonEmpty
private lazy val (stored, substed) = (subPatBinders, subPatRefs).zipped.partition{ case (sym, _) => storedBinders(sym) }
protected lazy val localSubstitution: Substitution = if (!emitVars) Substitution(subPatBinders, subPatRefs)
else {
val (subPatBindersSubstituted, subPatRefsSubstituted) = substed.unzip
Substitution(subPatBindersSubstituted.toList, subPatRefsSubstituted.toList)
}
/** The substitution that specifies the trees that compute the values of the subpattern binders.
*
* We pretend to replace the subpattern binders by subpattern refs
* (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.)
*/
override def subPatternsAsSubstitution =
Substitution(subPatBinders, subPatRefs) >> super.subPatternsAsSubstitution
def bindSubPats(in: Tree): Tree =
if (!emitVars) in
else {
// binders in `subPatBindersStored` that are referenced by tree `in`
val usedBinders = new mutable.HashSet[Symbol]()
// all potentially stored subpat binders
val potentiallyStoredBinders = stored.unzip._1.toSet
// compute intersection of all symbols in the tree `in` and all potentially stored subpat binders
in.foreach(t => if (potentiallyStoredBinders(t.symbol)) usedBinders += t.symbol)
if (usedBinders.isEmpty) in
else {
// only store binders actually used
val (subPatBindersStored, subPatRefsStored) = stored.filter{case (b, _) => usedBinders(b)}.unzip
Block(map2(subPatBindersStored.toList, subPatRefsStored.toList)(ValDef(_, _)), in)
}
}
}
/**
* Make a TreeMaker that will result in an extractor call specified by `extractor`
* the next TreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing
* a function with binder `nextBinder` over our extractor's result
* the function's body is determined by the next TreeMaker
* (furthermore, the interpretation of `flatMap` depends on the codegen instance we're using).
*
* The values for the subpatterns, as computed by the extractor call in `extractor`,
* are stored in local variables that re-use the symbols in `subPatBinders`.
* This makes extractor patterns more debuggable (SI-5739).
*/
case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol)(
val subPatBinders: List[Symbol],
val subPatRefs: List[Tree],
extractorReturnsBoolean: Boolean,
val checkedLength: Option[Int],
val prevBinder: Symbol,
val ignoredSubPatBinders: Set[Symbol]
) extends FunTreeMaker with PreserveSubPatBinders {
def extraStoredBinders: Set[Symbol] = Set()
debug.patmat(s"""
|ExtractorTreeMaker($extractor, $extraCond, $nextBinder) {
| $subPatBinders
| $subPatRefs
| $extractorReturnsBoolean
| $checkedLength
| $prevBinder
| $ignoredSubPatBinders
|}""".stripMargin)
def chainBefore(next: Tree)(casegen: Casegen): Tree = {
val condAndNext = extraCond match {
case Some(cond) =>
casegen.ifThenElseZero(substitution(cond), bindSubPats(substitution(next)))
case _ =>
bindSubPats(substitution(next))
}
atPos(extractor.pos)(
if (extractorReturnsBoolean) casegen.flatMapCond(extractor, CODE.UNIT, nextBinder, condAndNext)
else casegen.flatMap(extractor, nextBinder, condAndNext)
)
}
override def toString = "X"+((extractor, nextBinder.name))
}
/**
* An optimized version of ExtractorTreeMaker for Products.
* For now, this is hard-coded to case classes, and we simply extract the case class fields.
*
* The values for the subpatterns, as specified by the case class fields at the time of extraction,
* are stored in local variables that re-use the symbols in `subPatBinders`.
* This makes extractor patterns more debuggable (SI-5739) as well as
* avoiding mutation after the pattern has been matched (SI-5158, SI-6070)
*
* TODO: make this user-definable as follows
* When a companion object defines a method `def unapply_1(x: T): U_1`, but no `def unapply` or `def unapplySeq`,
* the extractor is considered to match any non-null value of type T
* the pattern is expected to have as many sub-patterns as there are `def unapply_I(x: T): U_I` methods,
* and the type of the I'th sub-pattern is `U_I`.
* The same exception for Seq patterns applies: if the last extractor is of type `Seq[U_N]`,
* the pattern must have at least N arguments (exactly N if the last argument is annotated with `: _*`).
* The arguments starting at N (and beyond) are taken from the sequence returned by apply_N,
* and it is checked that that sequence has enough elements to provide values for all expected sub-patterns.
*
* For a case class C, the implementation is assumed to be `def unapply_I(x: C) = x._I`,
* and the extractor call is inlined under that assumption.
*/
case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree])(
val subPatBinders: List[Symbol],
val subPatRefs: List[Tree],
val mutableBinders: List[Symbol],
binderKnownNonNull: Boolean,
val ignoredSubPatBinders: Set[Symbol]
) extends FunTreeMaker with PreserveSubPatBinders {
import CODE._
val nextBinder = prevBinder // just passing through
// mutable binders must be stored to avoid unsoundness or seeing mutation of fields after matching (SI-5158, SI-6070)
def extraStoredBinders: Set[Symbol] = mutableBinders.toSet
def chainBefore(next: Tree)(casegen: Casegen): Tree = {
val nullCheck = REF(prevBinder) OBJ_NE NULL
val cond =
if (binderKnownNonNull) extraCond
else (extraCond map (nullCheck AND _)
orElse Some(nullCheck))
cond match {
case Some(cond) =>
casegen.ifThenElseZero(cond, bindSubPats(substitution(next)))
case _ =>
bindSubPats(substitution(next))
}
}
override def toString = "P"+((prevBinder.name, extraCond getOrElse "", localSubstitution))
}
object IrrefutableExtractorTreeMaker {
// will an extractor with unapply method of methodtype `tp` always succeed?
// note: this assumes the other side-conditions implied by the extractor are met
// (argument of the right type, length check succeeds for unapplySeq,...)
def irrefutableExtractorType(tp: Type): Boolean = tp.resultType.dealias match {
case TypeRef(_, SomeClass, _) => true
// probably not useful since this type won't be inferred nor can it be written down (yet)
case ConstantTrue => true
case _ => false
}
def unapply(xtm: ExtractorTreeMaker): Option[(Tree, Symbol)] = xtm match {
case ExtractorTreeMaker(extractor, None, nextBinder) if irrefutableExtractorType(extractor.tpe) =>
Some((extractor, nextBinder))
case _ =>
None
}
}
object TypeTestTreeMaker {
// factored out so that we can consistently generate other representations of the tree that implements the test
// (e.g. propositions for exhaustivity and friends, boolean for isPureTypeTest)
trait TypeTestCondStrategy {
type Result
def outerTest(testedBinder: Symbol, expectedTp: Type): Result
// TODO: can probably always widen
def typeTest(testedBinder: Symbol, expectedTp: Type): Result
def nonNullTest(testedBinder: Symbol): Result
def equalsTest(pat: Tree, testedBinder: Symbol): Result
def eqTest(pat: Tree, testedBinder: Symbol): Result
def and(a: Result, b: Result): Result
def tru: Result
}
object treeCondStrategy extends TypeTestCondStrategy { import CODE._
type Result = Tree
def and(a: Result, b: Result): Result = a AND b
def tru = mkTRUE
def typeTest(testedBinder: Symbol, expectedTp: Type) = codegen._isInstanceOf(testedBinder, expectedTp)
def nonNullTest(testedBinder: Symbol) = REF(testedBinder) OBJ_NE NULL
def equalsTest(pat: Tree, testedBinder: Symbol) = codegen._equals(pat, testedBinder)
def eqTest(pat: Tree, testedBinder: Symbol) = REF(testedBinder) OBJ_EQ pat
def outerTest(testedBinder: Symbol, expectedTp: Type): Tree = {
val expectedOuter = expectedTp.prefix match {
case ThisType(clazz) => This(clazz)
case NoType => mkTRUE // fallback for SI-6183
case pre => REF(pre.prefix, pre.termSymbol)
}
// ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix`
// if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor?
val outer = expectedTp.typeSymbol.newMethod(vpmName.outer, newFlags = SYNTHETIC | ARTIFACT) setInfo expectedTp.prefix
(Select(codegen._asInstanceOf(testedBinder, expectedTp), outer)) OBJ_EQ expectedOuter
}
}
object pureTypeTestChecker extends TypeTestCondStrategy {
type Result = Boolean
def typeTest(testedBinder: Symbol, expectedTp: Type): Result = true
def outerTest(testedBinder: Symbol, expectedTp: Type): Result = false
def nonNullTest(testedBinder: Symbol): Result = false
def equalsTest(pat: Tree, testedBinder: Symbol): Result = false
def eqTest(pat: Tree, testedBinder: Symbol): Result = false
def and(a: Result, b: Result): Result = false // we don't and type tests, so the conjunction must include at least one false
def tru = true
}
def nonNullImpliedByTestChecker(binder: Symbol) = new TypeTestCondStrategy {
type Result = Boolean
def typeTest(testedBinder: Symbol, expectedTp: Type): Result = testedBinder eq binder
def outerTest(testedBinder: Symbol, expectedTp: Type): Result = false
def nonNullTest(testedBinder: Symbol): Result = testedBinder eq binder
def equalsTest(pat: Tree, testedBinder: Symbol): Result = false // could in principle analyse pat and see if it's statically known to be non-null
def eqTest(pat: Tree, testedBinder: Symbol): Result = false // could in principle analyse pat and see if it's statically known to be non-null
def and(a: Result, b: Result): Result = a || b
def tru = false
}
}
/** implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations)
*
* Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms:
- A reference to a class C, p.C, or T#C.
This type pattern matches any non-null instance of the given class.
Note that the prefix of the class, if it is given, is relevant for determining class instances.
For instance, the pattern p.C matches only instances of classes C which were created with the path p as prefix.
The bottom types scala.Nothing and scala.Null cannot be used as type patterns, because they would match nothing in any case.
- A singleton type p.type.
This type pattern matches only the value denoted by the path p
(that is, a pattern match involved a comparison of the matched value with p using method eq in class AnyRef). // TODO: the actual pattern matcher uses ==, so that's what I'm using for now
// https://issues.scala-lang.org/browse/SI-4577 "pattern matcher, still disappointing us at equality time"
- A compound type pattern T1 with ... with Tn where each Ti is a type pat- tern.
This type pattern matches all values that are matched by each of the type patterns Ti.
- A parameterized type pattern T[a1,...,an], where the ai are type variable patterns or wildcards _.
This type pattern matches all values which match T for some arbitrary instantiation of the type variables and wildcards.
The bounds or alias type of these type variable are determined as described in (§8.3).
- A parameterized type pattern scala.Array[T1], where T1 is a type pattern. // TODO
This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1.
**/
case class TypeTestTreeMaker(prevBinder: Symbol, testedBinder: Symbol, expectedTp: Type, nextBinderTp: Type)(override val pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker {
import TypeTestTreeMaker._
debug.patmat("TTTM"+((prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp)))
lazy val outerTestNeeded = (
(expectedTp.prefix ne NoPrefix)
&& !expectedTp.prefix.typeSymbol.isPackageClass
&& needsOuterTest(expectedTp, testedBinder.info, matchOwner)
)
// the logic to generate the run-time test that follows from the fact that
// a `prevBinder` is expected to have type `expectedTp`
// the actual tree-generation logic is factored out, since the analyses generate Cond(ition)s rather than Trees
// TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null`
// don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false")
def renderCondition(cs: TypeTestCondStrategy): cs.Result = {
import cs._
// propagate expected type
def expTp(t: Tree): t.type = t setType expectedTp
def testedWide = testedBinder.info.widen
def expectedWide = expectedTp.widen
def isAnyRef = testedWide <:< AnyRefTpe
def isAsExpected = testedWide <:< expectedTp
def isExpectedPrimitiveType = isAsExpected && isPrimitiveValueType(expectedTp)
def isExpectedReferenceType = isAsExpected && (expectedTp <:< AnyRefTpe)
def mkNullTest = nonNullTest(testedBinder)
def mkOuterTest = outerTest(testedBinder, expectedTp)
def mkTypeTest = typeTest(testedBinder, expectedWide)
def mkEqualsTest(lhs: Tree): cs.Result = equalsTest(lhs, testedBinder)
def mkEqTest(lhs: Tree): cs.Result = eqTest(lhs, testedBinder)
def addOuterTest(res: cs.Result): cs.Result = if (outerTestNeeded) and(res, mkOuterTest) else res
// If we conform to expected primitive type:
// it cannot be null and cannot have an outer pointer. No further checking.
// If we conform to expected reference type:
// have to test outer and non-null
// If we do not conform to expected type:
// have to test type and outer (non-null is implied by successful type test)
def mkDefault = (
if (isExpectedPrimitiveType) tru
else addOuterTest(
if (isExpectedReferenceType) mkNullTest
else mkTypeTest
)
)
// true when called to type-test the argument to an extractor
// don't do any fancy equality checking, just test the type
// TODO: verify that we don't need to special-case Array
// I think it's okay:
// - the isInstanceOf test includes a test for the element type
// - Scala's arrays are invariant (so we don't drop type tests unsoundly)
if (extractorArgTypeTest) mkDefault
else expectedTp match {
case SingleType(_, sym) => mkEqTest(gen.mkAttributedQualifier(expectedTp)) // SI-4577, SI-4897
case ThisType(sym) if sym.isModule => and(mkEqualsTest(CODE.REF(sym)), mkTypeTest) // must use == to support e.g. List() == Nil
case ConstantType(Constant(null)) if isAnyRef => mkEqTest(expTp(CODE.NULL))
case ConstantType(const) => mkEqualsTest(expTp(Literal(const)))
case ThisType(sym) => mkEqTest(expTp(This(sym)))
case _ => mkDefault
}
}
val cond = renderCondition(treeCondStrategy)
val res = codegen._asInstanceOf(testedBinder, nextBinderTp)
// is this purely a type test, e.g. no outer check, no equality tests (used in switch emission)
def isPureTypeTest = renderCondition(pureTypeTestChecker)
def impliesBinderNonNull(binder: Symbol) = renderCondition(nonNullImpliedByTestChecker(binder))
override def toString = "TT"+((expectedTp, testedBinder.name, nextBinderTp))
}
// need to substitute to deal with existential types -- TODO: deal with existentials better, don't substitute (see RichClass during quick.comp)
case class EqualityTestTreeMaker(prevBinder: Symbol, patTree: Tree, override val pos: Position) extends CondTreeMaker {
val nextBinderTp = prevBinder.info.widen
// NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null)
// equals need not be well-behaved, so don't intersect with pattern's (stabilized) type (unlike MaybeBoundTyped's accumType, where it's required)
val cond = codegen._equals(patTree, prevBinder)
val res = CODE.REF(prevBinder)
override def toString = "ET"+((prevBinder.name, patTree))
}
case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker with NoNewBinders {
// don't substitute prevBinder to nextBinder, a set of alternatives does not need to introduce a new binder, simply reuse the previous one
override private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
super.incorporateOuterSubstitution(outerSubst)
altss = altss map (alts => propagateSubstitution(alts, substitution))
}
def chainBefore(next: Tree)(codegenAlt: Casegen): Tree = {
atPos(pos){
// one alternative may still generate multiple trees (e.g., an extractor call + equality test)
// (for now,) alternatives may not bind variables (except wildcards), so we don't care about the final substitution built internally by makeTreeMakers
val combinedAlts = altss map (altTreeMakers =>
((casegen: Casegen) => combineExtractors(altTreeMakers :+ TrivialTreeMaker(casegen.one(mkTRUE)))(casegen))
)
val findAltMatcher = codegenAlt.matcher(EmptyTree, NoSymbol, BooleanTpe)(combinedAlts, Some(x => mkFALSE))
codegenAlt.ifThenElseZero(findAltMatcher, substitution(next))
}
}
}
case class GuardTreeMaker(guardTree: Tree) extends TreeMaker with NoNewBinders {
val pos = guardTree.pos
def chainBefore(next: Tree)(casegen: Casegen): Tree = casegen.flatMapGuard(substitution(guardTree), next)
override def toString = "G("+ guardTree +")"
}
// combineExtractors changes the current substitution's of the tree makers in `treeMakers`
// requires propagateSubstitution(treeMakers) has been called
def combineExtractors(treeMakers: List[TreeMaker])(casegen: Casegen): Tree =
treeMakers.foldRight(EmptyTree: Tree)((a, b) => a.chainBefore(b)(casegen))
def removeSubstOnly(makers: List[TreeMaker]) = makers filterNot (_.isInstanceOf[SubstOnlyTreeMaker])
// a foldLeft to accumulate the localSubstitution left-to-right
// it drops SubstOnly tree makers, since their only goal in life is to propagate substitutions to the next tree maker, which is fullfilled by propagateSubstitution
def propagateSubstitution(treeMakers: List[TreeMaker], initial: Substitution): List[TreeMaker] = {
var accumSubst: Substitution = initial
treeMakers foreach { maker =>
maker incorporateOuterSubstitution accumSubst
accumSubst = maker.substitution
}
removeSubstOnly(treeMakers)
}
// calls propagateSubstitution on the treemakers
def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = {
// drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them
val casesNoSubstOnly = casesRaw map (propagateSubstitution(_, EmptySubstitution))
combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, matchFailGenOverride)
}
// pt is the fully defined type of the cases (either pt or the lub of the types of the cases)
def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree =
fixerUpper(owner, scrut.pos) {
def matchFailGen = matchFailGenOverride orElse Some(Throw(MatchErrorClass.tpe, _: Tree))
debug.patmat("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}")))
val (suppression, requireSwitch): (Suppression, Boolean) =
if (settings.XnoPatmatAnalysis) (Suppression.NoSuppression, false)
else scrut match {
case Typed(tree, tpt) =>
val suppressExhaustive = tpt.tpe hasAnnotation UncheckedClass
val supressUnreachable = tree match {
case Ident(name) if name startsWith nme.CHECK_IF_REFUTABLE_STRING => true // SI-7183 don't warn for withFilter's that turn out to be irrefutable.
case _ => false
}
val suppression = Suppression(suppressExhaustive, supressUnreachable)
// matches with two or fewer cases need not apply for switchiness (if-then-else will do)
val requireSwitch = treeInfo.isSwitchAnnotation(tpt.tpe) && casesNoSubstOnly.lengthCompare(2) > 0
(suppression, requireSwitch)
case _ =>
(Suppression.NoSuppression, false)
}
emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt, matchFailGenOverride, suppression.exhaustive).getOrElse{
if (requireSwitch) typer.context.unit.warning(scrut.pos, "could not emit switch for @switch annotated match")
if (casesNoSubstOnly nonEmpty) {
// before optimizing, check casesNoSubstOnly for presence of a default case,
// since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one
// exhaustivity and reachability must be checked before optimization as well
// TODO: improve notion of trivial/irrefutable -- a trivial type test before the body still makes for a default case
// ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op)
// irrefutability checking should use the approximation framework also used for CSE, unreachability and exhaustivity checking
val synthCatchAll =
if (casesNoSubstOnly.nonEmpty && {
val nonTrivLast = casesNoSubstOnly.last
nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
}) None
else matchFailGen
analyzeCases(scrutSym, casesNoSubstOnly, pt, suppression)
val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt)
val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, synthCatchAll)
if (toHoist isEmpty) matchRes else Block(toHoist, matchRes)
} else {
codegen.matcher(scrut, scrutSym, pt)(Nil, matchFailGen)
}
}
}
// TODO: do this during tree construction, but that will require tracking the current owner in treemakers
// TODO: assign more fine-grained positions
// fixes symbol nesting, assigns positions
protected def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser {
currentOwner = origOwner
override def traverse(t: Tree) {
if (t != EmptyTree && t.pos == NoPosition) {
t.setPos(pos)
}
t match {
case Function(_, _) if t.symbol == NoSymbol =>
t.symbol = currentOwner.newAnonymousFunctionValue(t.pos)
debug.patmat("new symbol for "+ ((t, t.symbol.ownerChain)))
case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) =>
debug.patmat("fundef: "+ ((t, t.symbol.ownerChain, currentOwner.ownerChain)))
t.symbol.owner = currentOwner
case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2)
debug.patmat("def: "+ ((d, d.symbol.ownerChain, currentOwner.ownerChain)))
d.symbol.moduleClass andAlso (_.owner = currentOwner)
d.symbol.owner = currentOwner
// case _ if (t.symbol != NoSymbol) && (t.symbol ne null) =>
debug.patmat("untouched "+ ((t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain)))
case _ =>
}
super.traverse(t)
}
// override def apply
// debug.patmat("before fixerupper: "+ xTree)
// currentRun.trackerFactory.snapshot()
// debug.patmat("after fixerupper")
// currentRun.trackerFactory.snapshot()
}
}
}
|