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
|
/* NSC -- new Scala compiler
*
* Copyright 2011-2013 LAMP/EPFL
* @author Adriaan Moors
*/
package scala.tools.nsc.transform.patmat
import scala.tools.nsc.Global
import scala.tools.nsc.ast
import scala.language.postfixOps
import scala.tools.nsc.transform.TypingTransformers
import scala.tools.nsc.transform.Transform
import scala.reflect.internal.util.Statistics
import scala.reflect.internal.Types
import scala.reflect.internal.util.Position
/** Translate pattern matching.
*
* Either into optimized if/then/else's, or virtualized as method calls (these methods form a zero-plus monad),
* similar in spirit to how for-comprehensions are compiled.
*
* For each case, express all patterns as extractor calls, guards as 0-ary extractors, and sequence them using `flatMap`
* (lifting the body of the case into the monad using `one`).
*
* Cases are combined into a pattern match using the `orElse` combinator (the implicit failure case is expressed using the monad's `zero`).
*
* TODO:
* - DCE (on irrefutable patterns)
* - update spec and double check it's implemented correctly (see TODO's)
*
* (longer-term) TODO:
* - user-defined unapplyProd
* - recover GADT typing by locally inserting implicit witnesses to type equalities derived from the current case, and considering these witnesses during subtyping (?)
* - recover exhaustivity/unreachability of user-defined extractors by partitioning the types they match on using an HList or similar type-level structure
*/
trait PatternMatching extends Transform
with TypingTransformers
with Debugging
with Interface
with MatchTranslation
with MatchTreeMaking
with MatchCodeGen
with MatchCps
with ScalaLogic
with Solving
with MatchAnalysis
with MatchOptimization
with MatchWarnings
with ScalacPatternExpanders {
import global._
val phaseName: String = "patmat"
def newTransformer(unit: CompilationUnit): Transformer = new MatchTransformer(unit)
class MatchTransformer(unit: CompilationUnit) extends TypingTransformer(unit) {
override def transform(tree: Tree): Tree = tree match {
case Match(sel, cases) =>
val origTp = tree.tpe
// setType origTp intended for CPS -- TODO: is it necessary?
val translated = translator.translateMatch(treeCopy.Match(tree, transform(sel), transformTrees(cases).asInstanceOf[List[CaseDef]]))
try {
localTyper.typed(translated) setType origTp
} catch {
case x: (Types#TypeError) =>
// TODO: this should never happen; error should've been reported during type checking
unit.error(tree.pos, "error during expansion of this match (this is a scalac bug).\nThe underlying error was: "+ x.msg)
translated
}
case Try(block, catches, finalizer) =>
treeCopy.Try(tree, transform(block), translator.translateTry(transformTrees(catches).asInstanceOf[List[CaseDef]], tree.tpe, tree.pos), transform(finalizer))
case _ => super.transform(tree)
}
// TODO: only instantiate new match translator when localTyper has changed
// override def atOwner[A](tree: Tree, owner: Symbol)(trans: => A): A
// as this is the only time TypingTransformer changes it
def translator: MatchTranslator with CodegenCore = {
new OptimizingMatchTranslator(localTyper)
}
}
class PureMatchTranslator(val typer: analyzer.Typer, val matchStrategy: Tree) extends MatchTranslator with PureCodegen {
def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type) = (cases, Nil)
def analyzeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type, suppression: Suppression): Unit = {}
}
class OptimizingMatchTranslator(val typer: analyzer.Typer) extends MatchTranslator
with MatchOptimizer
with MatchAnalyzer
with Solver
}
trait Debugging {
val global: Global
// TODO: the inliner fails to inline the closures to debug.patmat unless the method is nested in an object
object debug {
val printPatmat = global.settings.Ypatmatdebug.value
@inline final def patmat(s: => String) = if (printPatmat) Console.err.println(s)
@inline final def patmatResult[T](s: => String)(result: T): T = {
if (printPatmat) Console.err.println(s + ": " + result)
result
}
}
}
trait Interface extends ast.TreeDSL {
import global._
import analyzer.Typer
// 2.10/2.11 compatibility
protected final def dealiasWiden(tp: Type) = tp.dealiasWiden
protected final def mkTRUE = CODE.TRUE
protected final def mkFALSE = CODE.FALSE
protected final def hasStableSymbol(p: Tree) = p.hasSymbolField && p.symbol.isStable
object vpmName {
val one = newTermName("one")
val flatMap = newTermName("flatMap")
val get = newTermName("get")
val guard = newTermName("guard")
val isEmpty = newTermName("isEmpty")
val orElse = newTermName("orElse")
val outer = newTermName("<outer>")
val runOrElse = newTermName("runOrElse")
val zero = newTermName("zero")
val _match = newTermName("__match") // don't call the val __match, since that will trigger virtual pattern matching...
def counted(str: String, i: Int) = newTermName(str + i)
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// talking to userland
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/** Interface with user-defined match monad?
* if there's a <code>__match</code> in scope, we use this as the match strategy, assuming it conforms to MatchStrategy as defined below:
{{{
type Matcher[P[_], M[+_], A] = {
def flatMap[B](f: P[A] => M[B]): M[B]
def orElse[B >: A](alternative: => M[B]): M[B]
}
abstract class MatchStrategy[P[_], M[+_]] {
// runs the matcher on the given input
def runOrElse[T, U](in: P[T])(matcher: P[T] => M[U]): P[U]
def zero: M[Nothing]
def one[T](x: P[T]): M[T]
def guard[T](cond: P[Boolean], then: => P[T]): M[T]
}
}}}
* P and M are derived from one's signature (`def one[T](x: P[T]): M[T]`)
* if no <code>__match</code> is found, we assume the following implementation (and generate optimized code accordingly)
{{{
object __match extends MatchStrategy[({type Id[x] = x})#Id, Option] {
def zero = None
def one[T](x: T) = Some(x)
// NOTE: guard's return type must be of the shape M[T], where M is the monad in which the pattern match should be interpreted
def guard[T](cond: Boolean, then: => T): Option[T] = if(cond) Some(then) else None
def runOrElse[T, U](x: T)(f: T => Option[U]): U = f(x) getOrElse (throw new MatchError(x))
}
}}}
*/
trait MatchMonadInterface {
val typer: Typer
val matchOwner = typer.context.owner
def pureType(tp: Type): Type = tp
def reportUnreachable(pos: Position) = typer.context.unit.warning(pos, "unreachable code")
def reportMissingCases(pos: Position, counterExamples: List[String]) = {
val ceString =
if (counterExamples.tail.isEmpty) "input: " + counterExamples.head
else "inputs: " + counterExamples.mkString(", ")
typer.context.unit.warning(pos, "match may not be exhaustive.\nIt would fail on the following "+ ceString)
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// substitution
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
trait TypedSubstitution extends MatchMonadInterface {
object Substitution {
def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
// requires sameLength(from, to)
def apply(from: List[Symbol], to: List[Tree]) =
if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
}
class Substitution(val from: List[Symbol], val to: List[Tree]) {
import global.{Transformer, Ident, NoType}
// We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
// and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
def apply(tree: Tree): Tree = {
// according to -Ystatistics 10% of translateMatch's time is spent in this method...
// since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
else (new Transformer {
private def typedIfOrigTyped(to: Tree, origTp: Type): Tree =
if (origTp == null || origTp == NoType) to
// important: only type when actually substing and when original tree was typed
// (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors)
else typer.typed(to)
override def transform(tree: Tree): Tree = {
def subst(from: List[Symbol], to: List[Tree]): Tree =
if (from.isEmpty) tree
else if (tree.symbol == from.head) typedIfOrigTyped(to.head.shallowDuplicate.setPos(tree.pos), tree.tpe)
else subst(from.tail, to.tail)
tree match {
case Ident(_) => subst(from, to)
case _ => super.transform(tree)
}
}
}).transform(tree)
}
// the substitution that chains `other` before `this` substitution
// forall t: Tree. this(other(t)) == (this >> other)(t)
def >>(other: Substitution): Substitution = {
val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) => !other.from.contains(f) }
new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly
}
override def toString = (from.map(_.name) zip to) mkString("Substitution(", ", ", ")")
}
object EmptySubstitution extends Substitution(Nil, Nil) {
override def apply(tree: Tree): Tree = tree
override def >>(other: Substitution): Substitution = other
}
}
}
object PatternMatchingStats {
val patmatNanos = Statistics.newTimer ("time spent in patmat", "patmat")
val patmatAnaDPLL = Statistics.newSubTimer (" of which DPLL", patmatNanos)
val patmatCNF = Statistics.newSubTimer (" of which in CNF conversion", patmatNanos)
val patmatCNFSizes = Statistics.newQuantMap[Int, Statistics.Counter](" CNF size counts", "patmat")(Statistics.newCounter(""))
val patmatAnaVarEq = Statistics.newSubTimer (" of which variable equality", patmatNanos)
val patmatAnaExhaust = Statistics.newSubTimer (" of which in exhaustivity", patmatNanos)
val patmatAnaReach = Statistics.newSubTimer (" of which in unreachability", patmatNanos)
}
|