Type Members

1.  trait Debugging extends AnyRef
2.  trait Interface extends TreeDSL
3.  case class Lit(v: Int) extends Product with Serializable
4.  trait Logic extends Debugging
5.  trait MatchAnalysis extends MatchApproximation
6.  trait MatchApproximation extends TreeAndTypeAnalysis with ScalaLogic with MatchTreeMaking
7.  trait MatchCodeGen extends Interface

   Factory methods used by TreeMakers to make the actual trees.

   Factory methods used by TreeMakers to make the actual trees.

   We have two modes in which to emit trees: optimized (the default) and pure (aka "virtualized": match is parametric in its monad).

8.  trait MatchCps extends AnyRef

   Segregating this super hacky CPS code.

9.  trait MatchOptimization extends MatchTreeMaking with MatchAnalysis

   Optimize and analyze matches based on their TreeMaker-representation.

   Optimize and analyze matches based on their TreeMaker-representation.

   The patmat translation doesn't rely on this, so it could be disabled in principle.

   • well, not quite: the backend crashes if we emit duplicates in switches (e.g. scala/bug#7290)
10.  trait MatchTranslation extends AnyRef

    Translate typed Trees that represent pattern matches into the patternmatching IR, defined by TreeMakers.

11.  trait MatchTreeMaking extends MatchCodeGen with Debugging

    Translate our IR (TreeMakers) into actual Scala Trees using the factory methods in MatchCodeGen.

    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.

12.  trait MatchWarnings extends AnyRef
13.  trait PatternExpansion extends AnyRef

    An 'extractor' can be a case class or an unapply or unapplySeq method.

    An 'extractor' can be a case class or an unapply or unapplySeq method.

    In a case class, the class is the unextracted type and the fixed and repeated types are derived from its constructor parameters.

    In an unapply, this is reversed: the parameter to the unapply is the unextracted type, and the other types are derived based on the return type of the unapply method.

    An extractor returns: F1, F2, ..., Fi, opt[Seq[E] or E*] A case matches: P1, P2, ..., Pj, opt[Seq[E]] Put together: P1/F1, P2/F2, ... Pi/Fi, Pi+1/E, Pi+2/E, ... Pj/E, opt[Seq[E]]

    Here Pm/Fi is the last pattern to match the fixed arity section.

    productArity: the value of i, i.e. the number of non-sequence types in the extractor nonStarArity: the value of j, i.e. the number of non-star patterns in the case definition elementArity: j - i, i.e. the number of non-star patterns which must match sequence elements starArity: 1 or 0 based on whether there is a star (sequence-absorbing) pattern totalArity: nonStarArity + starArity, i.e. the number of patterns in the case definition

    Note that productArity is a function only of the extractor, and nonStar/star/totalArity are all functions of the patterns. The key value for aligning and typing the patterns is elementArity, as it is derived from both sets of information.

    If elementArity is...

    • zero: A perfect match between extractor and the fixed patterns. If there is a star pattern it will match any sequence.
    • positive: There are more patterns than products. There will have to be a sequence which can populate at least elementArity patterns.
    • negative: There are more products than patterns: compile time error.
14.  trait PatternMatching extends SubComponent with 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 PatternExpansion

    Translate pattern matching.

    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
15.  trait PatternMatchingStats extends AnyRef
16.  trait ScalaLogic extends Interface with Logic with TreeAndTypeAnalysis
17.  trait Solving extends Logic

    Solve pattern matcher exhaustivity problem via DPLL.

18.  trait TreeAndTypeAnalysis extends Debugging