diff options
author | Adriaan Moors <adriaan.moors@typesafe.com> | 2013-01-30 16:09:49 -0800 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@typesafe.com> | 2013-01-30 16:09:49 -0800 |
commit | 74b3e9aefe05363a14c217b558d8f9890c008379 (patch) | |
tree | fedd97be016296fbe4b008eafc8b5dc00b043a93 /src | |
parent | 62681e191a101213a6af65bb88d77230f1f5d663 (diff) | |
parent | f72354c6cba0d20dda308e531c6e1b129da3ed00 (diff) | |
download | scala-74b3e9aefe05363a14c217b558d8f9890c008379.tar.gz scala-74b3e9aefe05363a14c217b558d8f9890c008379.tar.bz2 scala-74b3e9aefe05363a14c217b558d8f9890c008379.zip |
Merge pull request #2020 from adriaanm/rebase-pr-1994-2.10.x
[retarget #1994 to 2.10.x] SI-6726 Improving pattern matcher analysis performance
Diffstat (limited to 'src')
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala | 29 |
1 files changed, 21 insertions, 8 deletions
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala index 69bbab6e42..1f5b8c74c5 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala @@ -1897,17 +1897,24 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL case object False extends Prop // symbols are propositions - case class Sym(val variable: Var, val const: Const) extends Prop { - private[this] val id = nextSymId + abstract case class Sym(val variable: Var, val const: Const) extends Prop { + private[this] val id = Sym.nextSymId + override def toString = variable +"="+ const +"#"+ id } - private def nextSymId = {_symId += 1; _symId}; private var _symId = 0 - + class UniqueSym(variable: Var, const: Const) extends Sym(variable, const) + object Sym { + private val uniques: util.HashSet[Sym] = new util.HashSet("uniques", 512) + def apply(variable: Var, const: Const): Sym = { + val newSym = new UniqueSym(variable, const) + (uniques findEntryOrUpdate newSym) + } + private def nextSymId = {_symId += 1; _symId}; private var _symId = 0 + } def /\(props: Iterable[Prop]) = if (props.isEmpty) True else props.reduceLeft(And(_, _)) def \/(props: Iterable[Prop]) = if (props.isEmpty) False else props.reduceLeft(Or(_, _)) - trait PropTraverser { def apply(x: Prop): Unit = x match { case And(a, b) => apply(a); apply(b) @@ -2063,6 +2070,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL import scala.collection.mutable.ArrayBuffer type FormulaBuilder = ArrayBuffer[Clause] def formulaBuilder = ArrayBuffer[Clause]() + def formulaBuilderSized(init: Int) = new ArrayBuffer[Clause](init) def addFormula(buff: FormulaBuilder, f: Formula): Unit = buff ++= f def toFormula(buff: FormulaBuilder): Formula = buff @@ -2167,7 +2175,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL class Lit(val sym: Sym, val pos: Boolean) { override def toString = if (!pos) "-"+ sym.toString else sym.toString override def equals(o: Any) = o match { - case o: Lit => (o.sym == sym) && (o.pos == pos) + case o: Lit => (o.sym eq sym) && (o.pos == pos) case _ => false } override def hashCode = sym.hashCode + pos.hashCode @@ -2216,13 +2224,18 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL } private def withLit(res: Model, l: Lit): Model = if (res eq NoModel) NoModel else res + (l.sym -> l.pos) - private def dropUnit(f: Formula, unitLit: Lit) = { + private def dropUnit(f: Formula, unitLit: Lit): Formula = { val negated = -unitLit // drop entire clauses that are trivially true // (i.e., disjunctions that contain the literal we're making true in the returned model), // and simplify clauses by dropping the negation of the literal we're making true // (since False \/ X == X) - f.filterNot(_.contains(unitLit)).map(_ - negated) + val dropped = formulaBuilderSized(f.size) + for { + clause <- f + if !(clause contains unitLit) + } dropped += (clause - negated) + dropped } def findModelFor(f: Formula): Model = { |