diff options
7 files changed, 1034 insertions, 44 deletions
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala index 4ea569c8e6..cef22d7d6b 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala @@ -10,6 +10,7 @@ package tools.nsc.transform.patmat import scala.language.postfixOps import scala.collection.mutable import scala.reflect.internal.util.{NoPosition, Position, Statistics, HashSet} +import scala.tools.nsc.Global trait Logic extends Debugging { import PatternMatchingStats._ @@ -90,6 +91,8 @@ trait Logic extends Debugging { // compute the domain and return it (call registerNull first!) def domainSyms: Option[Set[Sym]] + def groupedDomains: List[Set[Sym]] + // the symbol for this variable being equal to its statically known type // (only available if registerEquality has been called for that type before) def symForStaticTp: Option[Sym] @@ -118,6 +121,9 @@ trait Logic extends Debugging { final case class Not(a: Prop) extends Prop + // mutually exclusive (i.e., not more than one symbol is set) + final case class AtMostOne(ops: List[Sym]) extends Prop + case object True extends Prop case object False extends Prop @@ -192,7 +198,8 @@ trait Logic extends Debugging { case Not(negated) => negationNormalFormNot(negated) case True | False - | (_: Sym) => p + | (_: Sym) + | (_: AtMostOne) => p } def simplifyProp(p: Prop): Prop = p match { @@ -252,6 +259,7 @@ trait Logic extends Debugging { case Not(a) => apply(a) case Eq(a, b) => applyVar(a); applyConst(b) case s: Sym => applySymbol(s) + case AtMostOne(ops) => ops.foreach(applySymbol) case _ => } def applyVar(x: Var): Unit = {} @@ -374,7 +382,23 @@ trait Logic extends Debugging { // when sym is true, what must hold... implied foreach (impliedSym => addAxiom(Or(Not(sym), impliedSym))) // ... and what must not? - excluded foreach (excludedSym => addAxiom(Or(Not(sym), Not(excludedSym)))) + excluded foreach { + excludedSym => + val related = Set(sym, excludedSym) + val exclusive = v.groupedDomains.exists { + domain => related subsetOf domain.toSet + } + + // TODO: populate `v.exclusiveDomains` with `Set`s from the start, and optimize to: + // val exclusive = v.exclusiveDomains.exists { inDomain => inDomain(sym) && inDomain(excludedSym) } + if (!exclusive) + addAxiom(Or(Not(sym), Not(excludedSym))) + } + } + + // all symbols in a domain are mutually exclusive + v.groupedDomains.foreach { + syms => if (syms.size > 1) addAxiom(AtMostOne(syms.toList)) } } @@ -449,7 +473,9 @@ trait ScalaLogic extends Interface with Logic with TreeAndTypeAnalysis { // once we go to run-time checks (on Const's), convert them to checkable types // TODO: there seems to be bug for singleton domains (variable does not show up in model) lazy val domain: Option[Set[Const]] = { - val subConsts = enumerateSubtypes(staticTp).map{ tps => + val subConsts = + enumerateSubtypes(staticTp, grouped = false) + .headOption.map { tps => tps.toSet[Type].map{ tp => val domainC = TypeConst(tp) registerEquality(domainC) @@ -467,6 +493,15 @@ trait ScalaLogic extends Interface with Logic with TreeAndTypeAnalysis { observed(); allConsts } + lazy val groupedDomains: List[Set[Sym]] = { + val subtypes = enumerateSubtypes(staticTp, grouped = true) + subtypes.map { + subTypes => + val syms = subTypes.flatMap(tpe => symForEqualsTo.get(TypeConst(tpe))).toSet + if (mayBeNull) syms + symForEqualsTo(NullConst) else syms + }.filter(_.nonEmpty) + } + // populate equalitySyms // don't care about the result, but want only one fresh symbol per distinct constant c def registerEquality(c: Const): Unit = {ensureCanModify(); symForEqualsTo getOrElseUpdate(c, Sym(this, c))} diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala index cecb5c37be..a11906ace1 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala @@ -95,58 +95,84 @@ trait TreeAndTypeAnalysis extends Debugging { val typer: Typer // TODO: domain of other feasibly enumerable built-in types (char?) - def enumerateSubtypes(tp: Type): Option[List[Type]] = + def enumerateSubtypes(tp: Type, grouped: Boolean): List[List[Type]] = tp.typeSymbol match { // TODO case _ if tp.isTupleType => // recurse into component types? - case UnitClass => - Some(List(UnitTpe)) - case BooleanClass => - Some(ConstantTrue :: ConstantFalse :: Nil) + case UnitClass if !grouped => + List(List(UnitTpe)) + case BooleanClass if !grouped => + List(ConstantTrue :: ConstantFalse :: Nil) // TODO case _ if tp.isTupleType => // recurse into component types - case modSym: ModuleClassSymbol => - Some(List(tp)) + case modSym: ModuleClassSymbol if !grouped => + List(List(tp)) case sym: RefinementClassSymbol => - val parentSubtypes: List[Option[List[Type]]] = tp.parents.map(parent => enumerateSubtypes(parent)) - if (parentSubtypes exists (_.isDefined)) + val parentSubtypes = tp.parents.flatMap(parent => enumerateSubtypes(parent, grouped)) + if (parentSubtypes exists (_.nonEmpty)) { // If any of the parents is enumerable, then the refinement type is enumerable. - Some( - // We must only include subtypes of the parents that conform to `tp`. - // See neg/virtpatmat_exhaust_compound.scala for an example. - parentSubtypes flatMap (_.getOrElse(Nil)) filter (_ <:< tp) - ) - else None + // We must only include subtypes of the parents that conform to `tp`. + // See neg/virtpatmat_exhaust_compound.scala for an example. + parentSubtypes map (_.filter(_ <:< tp)) + } + else Nil // make sure it's not a primitive, else (5: Byte) match { case 5 => ... } sees no Byte case sym if sym.isSealed => - val subclasses = debug.patmatResult(s"enum $sym sealed, subclasses")( - // symbols which are both sealed and abstract need not be covered themselves, because - // all of their children must be and they cannot otherwise be created. - sym.sealedDescendants.toList - sortBy (_.sealedSortName) - filterNot (x => x.isSealed && x.isAbstractClass && !isPrimitiveValueClass(x)) - ) val tpApprox = typer.infer.approximateAbstracts(tp) val pre = tpApprox.prefix - Some(debug.patmatResult(s"enum sealed tp=$tp, tpApprox=$tpApprox as") { - // valid subtypes are turned into checkable types, as we are entering the realm of the dynamic - subclasses flatMap { sym => + def filterChildren(children: List[Symbol]): List[Type] = { + children flatMap { sym => // have to filter out children which cannot match: see ticket #3683 for an example // compare to the fully known type `tp` (modulo abstract types), // so that we can rule out stuff like: sealed trait X[T]; class XInt extends X[Int] --> XInt not valid when enumerating X[String] // however, must approximate abstract types in - val memberType = nestedMemberType(sym, pre, tpApprox.typeSymbol.owner) - val subTp = appliedType(memberType, sym.typeParams.map(_ => WildcardType)) + val memberType = nestedMemberType(sym, pre, tpApprox.typeSymbol.owner) + val subTp = appliedType(memberType, sym.typeParams.map(_ => WildcardType)) val subTpApprox = typer.infer.approximateAbstracts(subTp) // TODO: needed? // debug.patmat("subtp"+(subTpApprox <:< tpApprox, subTpApprox, tpApprox)) if (subTpApprox <:< tpApprox) Some(checkableType(subTp)) else None } - }) + } + + if(grouped) { + def enumerateChildren(sym: Symbol) = { + sym.children.toList + .sortBy(_.sealedSortName) + .filterNot(x => x.isSealed && x.isAbstractClass && !isPrimitiveValueClass(x)) + } + + // enumerate only direct subclasses, + // subclasses of subclasses are enumerated in the next iteration + // and added to a new group + def groupChildren(wl: List[Symbol], + acc: List[List[Type]]): List[List[Type]] = wl match { + case hd :: tl => + val children = enumerateChildren(hd) + groupChildren(tl ++ children, acc :+ filterChildren(children)) + case Nil => acc + } + + groupChildren(sym :: Nil, Nil) + } else { + val subclasses = debug.patmatResult(s"enum $sym sealed, subclasses")( + // symbols which are both sealed and abstract need not be covered themselves, because + // all of their children must be and they cannot otherwise be created. + sym.sealedDescendants.toList + sortBy (_.sealedSortName) + filterNot (x => x.isSealed && x.isAbstractClass && !isPrimitiveValueClass(x)) + ) + + List(debug.patmatResult(s"enum sealed tp=$tp, tpApprox=$tpApprox as") { + // valid subtypes are turned into checkable types, as we are entering the realm of the dynamic + filterChildren(subclasses) + }) + } + case sym => debug.patmat("enum unsealed "+ ((tp, sym, sym.isSealed, isPrimitiveValueClass(sym)))) - None + Nil } // approximate a type to the static type that is fully checkable at run time, @@ -176,7 +202,7 @@ trait TreeAndTypeAnalysis extends Debugging { def uncheckableType(tp: Type): Boolean = { val checkable = ( (isTupleType(tp) && tupleComponents(tp).exists(tp => !uncheckableType(tp))) - || enumerateSubtypes(tp).nonEmpty) + || enumerateSubtypes(tp, grouped = false).nonEmpty) // if (!checkable) debug.patmat("deemed uncheckable: "+ tp) !checkable } diff --git a/src/compiler/scala/tools/nsc/transform/patmat/Solving.scala b/src/compiler/scala/tools/nsc/transform/patmat/Solving.scala index c43f1b6209..9710c5c66b 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/Solving.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/Solving.scala @@ -65,11 +65,22 @@ trait Solving extends Logic { def size = symbols.size } + def cnfString(f: Array[Clause]): String + final case class Solvable(cnf: Cnf, symbolMapping: SymbolMapping) { def ++(other: Solvable) = { require(this.symbolMapping eq other.symbolMapping) Solvable(cnf ++ other.cnf, symbolMapping) } + + override def toString: String = { + "Solvable\nLiterals:\n" + + (for { + (lit, sym) <- symbolMapping.symForVar.toSeq.sortBy(_._1) + } yield { + s"$lit -> $sym" + }).mkString("\n") + "Cnf:\n" + cnfString(cnf) + } } trait CnfBuilder { @@ -140,20 +151,23 @@ trait Solving extends Logic { def apply(p: Prop): Solvable = { - def convert(p: Prop): Lit = { + def convert(p: Prop): Option[Lit] = { p match { case And(fv) => - and(fv.map(convert)) + Some(and(fv.flatMap(convert))) case Or(fv) => - or(fv.map(convert)) + Some(or(fv.flatMap(convert))) case Not(a) => - not(convert(a)) + convert(a).map(not) case sym: Sym => - convertSym(sym) + Some(convertSym(sym)) case True => - constTrue + Some(constTrue) case False => - constFalse + Some(constFalse) + case AtMostOne(ops) => + atMostOne(ops) + None case _: Eq => throw new MatchError(p) } @@ -199,8 +213,57 @@ trait Solving extends Logic { // no need for auxiliary variable def not(a: Lit): Lit = -a + /** + * This encoding adds 3n-4 variables auxiliary variables + * to encode that at most 1 symbol can be set. + * See also "Towards an Optimal CNF Encoding of Boolean Cardinality Constraints" + * http://www.carstensinz.de/papers/CP-2005.pdf + */ + def atMostOne(ops: List[Sym]) { + (ops: @unchecked) match { + case hd :: Nil => convertSym(hd) + case x1 :: tail => + // sequential counter: 3n-4 clauses + // pairwise encoding: n*(n-1)/2 clauses + // thus pays off only if n > 5 + if (ops.lengthCompare(5) > 0) { + + @inline + def /\(a: Lit, b: Lit) = addClauseProcessed(clause(a, b)) + + val (mid, xn :: Nil) = tail.splitAt(tail.size - 1) + + // 1 <= x1,...,xn <==> + // + // (!x1 \/ s1) /\ (!xn \/ !sn-1) /\ + // + // /\ + // / \ (!xi \/ si) /\ (!si-1 \/ si) /\ (!xi \/ !si-1) + // 1 < i < n + val s1 = newLiteral() + /\(-convertSym(x1), s1) + val snMinus = mid.foldLeft(s1) { + case (siMinus, sym) => + val xi = convertSym(sym) + val si = newLiteral() + /\(-xi, si) + /\(-siMinus, si) + /\(-xi, -siMinus) + si + } + /\(-convertSym(xn), -snMinus) + } else { + ops.map(convertSym).combinations(2).foreach { + case a :: b :: Nil => + addClauseProcessed(clause(-a, -b)) + case _ => + } + } + } + } + // add intermediate variable since we want the formula to be SAT! - addClauseProcessed(clause(convert(p))) + addClauseProcessed(convert(p).toSet) Solvable(buildCnf, symbolMapping) } diff --git a/test/files/neg/patmatexhaust-huge.check b/test/files/neg/patmatexhaust-huge.check new file mode 100644 index 0000000000..66dbd42ef3 --- /dev/null +++ b/test/files/neg/patmatexhaust-huge.check @@ -0,0 +1,7 @@ +patmatexhaust-huge.scala:404: warning: match may not be exhaustive. +It would fail on the following inputs: C392, C397 + def f(c: C): Int = c match { + ^ +error: No warnings can be incurred under -Xfatal-warnings. +one warning found +one error found diff --git a/test/files/neg/patmatexhaust-huge.flags b/test/files/neg/patmatexhaust-huge.flags new file mode 100644 index 0000000000..591a950f83 --- /dev/null +++ b/test/files/neg/patmatexhaust-huge.flags @@ -0,0 +1 @@ +-Xfatal-warnings -unchecked -Ypatmat-exhaust-depth off
\ No newline at end of file diff --git a/test/files/neg/patmatexhaust-huge.scala b/test/files/neg/patmatexhaust-huge.scala new file mode 100644 index 0000000000..8f87655b7a --- /dev/null +++ b/test/files/neg/patmatexhaust-huge.scala @@ -0,0 +1,806 @@ +sealed trait C +case object C1 extends C +case object C2 extends C +case object C3 extends C +case object C4 extends C +case object C5 extends C +case object C6 extends C +case object C7 extends C +case object C8 extends C +case object C9 extends C +case object C10 extends C +case object C11 extends C +case object C12 extends C +case object C13 extends C +case object C14 extends C +case object C15 extends C +case object C16 extends C +case object C17 extends C +case object C18 extends C +case object C19 extends C +case object C20 extends C +case object C21 extends C +case object C22 extends C +case object C23 extends C +case object C24 extends C +case object C25 extends C +case object C26 extends C +case object C27 extends C +case object C28 extends C +case object C29 extends C +case object C30 extends C +case object C31 extends C +case object C32 extends C +case object C33 extends C +case object C34 extends C +case object C35 extends C +case object C36 extends C +case object C37 extends C +case object C38 extends C +case object C39 extends C +case object C40 extends C +case object C41 extends C +case object C42 extends C +case object C43 extends C +case object C44 extends C +case object C45 extends C +case object C46 extends C +case object C47 extends C +case object C48 extends C +case object C49 extends C +case object C50 extends C +case object C51 extends C +case object C52 extends C +case object C53 extends C +case object C54 extends C +case object C55 extends C +case object C56 extends C +case object C57 extends C +case object C58 extends C +case object C59 extends C +case object C60 extends C +case object C61 extends C +case object C62 extends C +case object C63 extends C +case object C64 extends C +case object C65 extends C +case object C66 extends C +case object C67 extends C +case object C68 extends C +case object C69 extends C +case object C70 extends C +case object C71 extends C +case object C72 extends C +case object C73 extends C +case object C74 extends C +case object C75 extends C +case object C76 extends C +case object C77 extends C +case object C78 extends C +case object C79 extends C +case object C80 extends C +case object C81 extends C +case object C82 extends C +case object C83 extends C +case object C84 extends C +case object C85 extends C +case object C86 extends C +case object C87 extends C +case object C88 extends C +case object C89 extends C +case object C90 extends C +case object C91 extends C +case object C92 extends C +case object C93 extends C +case object C94 extends C +case object C95 extends C +case object C96 extends C +case object C97 extends C +case object C98 extends C +case object C99 extends C +case object C100 extends C +case object C101 extends C +case object C102 extends C +case object C103 extends C +case object C104 extends C +case object C105 extends C +case object C106 extends C +case object C107 extends C +case object C108 extends C +case object C109 extends C +case object C110 extends C +case object C111 extends C +case object C112 extends C +case object C113 extends C +case object C114 extends C +case object C115 extends C +case object C116 extends C +case object C117 extends C +case object C118 extends C +case object C119 extends C +case object C120 extends C +case object C121 extends C +case object C122 extends C +case object C123 extends C +case object C124 extends C +case object C125 extends C +case object C126 extends C +case object C127 extends C +case object C128 extends C +case object C129 extends C +case object C130 extends C +case object C131 extends C +case object C132 extends C +case object C133 extends C +case object C134 extends C +case object C135 extends C +case object C136 extends C +case object C137 extends C +case object C138 extends C +case object C139 extends C +case object C140 extends C +case object C141 extends C +case object C142 extends C +case object C143 extends C +case object C144 extends C +case object C145 extends C +case object C146 extends C +case object C147 extends C +case object C148 extends C +case object C149 extends C +case object C150 extends C +case object C151 extends C +case object C152 extends C +case object C153 extends C +case object C154 extends C +case object C155 extends C +case object C156 extends C +case object C157 extends C +case object C158 extends C +case object C159 extends C +case object C160 extends C +case object C161 extends C +case object C162 extends C +case object C163 extends C +case object C164 extends C +case object C165 extends C +case object C166 extends C +case object C167 extends C +case object C168 extends C +case object C169 extends C +case object C170 extends C +case object C171 extends C +case object C172 extends C +case object C173 extends C +case object C174 extends C +case object C175 extends C +case object C176 extends C +case object C177 extends C +case object C178 extends C +case object C179 extends C +case object C180 extends C +case object C181 extends C +case object C182 extends C +case object C183 extends C +case object C184 extends C +case object C185 extends C +case object C186 extends C +case object C187 extends C +case object C188 extends C +case object C189 extends C +case object C190 extends C +case object C191 extends C +case object C192 extends C +case object C193 extends C +case object C194 extends C +case object C195 extends C +case object C196 extends C +case object C197 extends C +case object C198 extends C +case object C199 extends C +case object C200 extends C +case object C201 extends C +case object C202 extends C +case object C203 extends C +case object C204 extends C +case object C205 extends C +case object C206 extends C +case object C207 extends C +case object C208 extends C +case object C209 extends C +case object C210 extends C +case object C211 extends C +case object C212 extends C +case object C213 extends C +case object C214 extends C +case object C215 extends C +case object C216 extends C +case object C217 extends C +case object C218 extends C +case object C219 extends C +case object C220 extends C +case object C221 extends C +case object C222 extends C +case object C223 extends C +case object C224 extends C +case object C225 extends C +case object C226 extends C +case object C227 extends C +case object C228 extends C +case object C229 extends C +case object C230 extends C +case object C231 extends C +case object C232 extends C +case object C233 extends C +case object C234 extends C +case object C235 extends C +case object C236 extends C +case object C237 extends C +case object C238 extends C +case object C239 extends C +case object C240 extends C +case object C241 extends C +case object C242 extends C +case object C243 extends C +case object C244 extends C +case object C245 extends C +case object C246 extends C +case object C247 extends C +case object C248 extends C +case object C249 extends C +case object C250 extends C +case object C251 extends C +case object C252 extends C +case object C253 extends C +case object C254 extends C +case object C255 extends C +case object C256 extends C +case object C257 extends C +case object C258 extends C +case object C259 extends C +case object C260 extends C +case object C261 extends C +case object C262 extends C +case object C263 extends C +case object C264 extends C +case object C265 extends C +case object C266 extends C +case object C267 extends C +case object C268 extends C +case object C269 extends C +case object C270 extends C +case object C271 extends C +case object C272 extends C +case object C273 extends C +case object C274 extends C +case object C275 extends C +case object C276 extends C +case object C277 extends C +case object C278 extends C +case object C279 extends C +case object C280 extends C +case object C281 extends C +case object C282 extends C +case object C283 extends C +case object C284 extends C +case object C285 extends C +case object C286 extends C +case object C287 extends C +case object C288 extends C +case object C289 extends C +case object C290 extends C +case object C291 extends C +case object C292 extends C +case object C293 extends C +case object C294 extends C +case object C295 extends C +case object C296 extends C +case object C297 extends C +case object C298 extends C +case object C299 extends C +case object C300 extends C +case object C301 extends C +case object C302 extends C +case object C303 extends C +case object C304 extends C +case object C305 extends C +case object C306 extends C +case object C307 extends C +case object C308 extends C +case object C309 extends C +case object C310 extends C +case object C311 extends C +case object C312 extends C +case object C313 extends C +case object C314 extends C +case object C315 extends C +case object C316 extends C +case object C317 extends C +case object C318 extends C +case object C319 extends C +case object C320 extends C +case object C321 extends C +case object C322 extends C +case object C323 extends C +case object C324 extends C +case object C325 extends C +case object C326 extends C +case object C327 extends C +case object C328 extends C +case object C329 extends C +case object C330 extends C +case object C331 extends C +case object C332 extends C +case object C333 extends C +case object C334 extends C +case object C335 extends C +case object C336 extends C +case object C337 extends C +case object C338 extends C +case object C339 extends C +case object C340 extends C +case object C341 extends C +case object C342 extends C +case object C343 extends C +case object C344 extends C +case object C345 extends C +case object C346 extends C +case object C347 extends C +case object C348 extends C +case object C349 extends C +case object C350 extends C +case object C351 extends C +case object C352 extends C +case object C353 extends C +case object C354 extends C +case object C355 extends C +case object C356 extends C +case object C357 extends C +case object C358 extends C +case object C359 extends C +case object C360 extends C +case object C361 extends C +case object C362 extends C +case object C363 extends C +case object C364 extends C +case object C365 extends C +case object C366 extends C +case object C367 extends C +case object C368 extends C +case object C369 extends C +case object C370 extends C +case object C371 extends C +case object C372 extends C +case object C373 extends C +case object C374 extends C +case object C375 extends C +case object C376 extends C +case object C377 extends C +case object C378 extends C +case object C379 extends C +case object C380 extends C +case object C381 extends C +case object C382 extends C +case object C383 extends C +case object C384 extends C +case object C385 extends C +case object C386 extends C +case object C387 extends C +case object C388 extends C +case object C389 extends C +case object C390 extends C +case object C391 extends C +case object C392 extends C +case object C393 extends C +case object C394 extends C +case object C395 extends C +case object C396 extends C +case object C397 extends C +case object C398 extends C +case object C399 extends C +case object C400 extends C + +object M { + def f(c: C): Int = c match { + case C1 => 1 + case C2 => 2 + case C3 => 3 + case C4 => 4 + case C5 => 5 + case C6 => 6 + case C7 => 7 + case C8 => 8 + case C9 => 9 + case C10 => 10 + case C11 => 11 + case C12 => 12 + case C13 => 13 + case C14 => 14 + case C15 => 15 + case C16 => 16 + case C17 => 17 + case C18 => 18 + case C19 => 19 + case C20 => 20 + case C21 => 21 + case C22 => 22 + case C23 => 23 + case C24 => 24 + case C25 => 25 + case C26 => 26 + case C27 => 27 + case C28 => 28 + case C29 => 29 + case C30 => 30 + case C31 => 31 + case C32 => 32 + case C33 => 33 + case C34 => 34 + case C35 => 35 + case C36 => 36 + case C37 => 37 + case C38 => 38 + case C39 => 39 + case C40 => 40 + case C41 => 41 + case C42 => 42 + case C43 => 43 + case C44 => 44 + case C45 => 45 + case C46 => 46 + case C47 => 47 + case C48 => 48 + case C49 => 49 + case C50 => 50 + case C51 => 51 + case C52 => 52 + case C53 => 53 + case C54 => 54 + case C55 => 55 + case C56 => 56 + case C57 => 57 + case C58 => 58 + case C59 => 59 + case C60 => 60 + case C61 => 61 + case C62 => 62 + case C63 => 63 + case C64 => 64 + case C65 => 65 + case C66 => 66 + case C67 => 67 + case C68 => 68 + case C69 => 69 + case C70 => 70 + case C71 => 71 + case C72 => 72 + case C73 => 73 + case C74 => 74 + case C75 => 75 + case C76 => 76 + case C77 => 77 + case C78 => 78 + case C79 => 79 + case C80 => 80 + case C81 => 81 + case C82 => 82 + case C83 => 83 + case C84 => 84 + case C85 => 85 + case C86 => 86 + case C87 => 87 + case C88 => 88 + case C89 => 89 + case C90 => 90 + case C91 => 91 + case C92 => 92 + case C93 => 93 + case C94 => 94 + case C95 => 95 + case C96 => 96 + case C97 => 97 + case C98 => 98 + case C99 => 99 + case C100 => 100 + case C101 => 101 + case C102 => 102 + case C103 => 103 + case C104 => 104 + case C105 => 105 + case C106 => 106 + case C107 => 107 + case C108 => 108 + case C109 => 109 + case C110 => 110 + case C111 => 111 + case C112 => 112 + case C113 => 113 + case C114 => 114 + case C115 => 115 + case C116 => 116 + case C117 => 117 + case C118 => 118 + case C119 => 119 + case C120 => 120 + case C121 => 121 + case C122 => 122 + case C123 => 123 + case C124 => 124 + case C125 => 125 + case C126 => 126 + case C127 => 127 + case C128 => 128 + case C129 => 129 + case C130 => 130 + case C131 => 131 + case C132 => 132 + case C133 => 133 + case C134 => 134 + case C135 => 135 + case C136 => 136 + case C137 => 137 + case C138 => 138 + case C139 => 139 + case C140 => 140 + case C141 => 141 + case C142 => 142 + case C143 => 143 + case C144 => 144 + case C145 => 145 + case C146 => 146 + case C147 => 147 + case C148 => 148 + case C149 => 149 + case C150 => 150 + case C151 => 151 + case C152 => 152 + case C153 => 153 + case C154 => 154 + case C155 => 155 + case C156 => 156 + case C157 => 157 + case C158 => 158 + case C159 => 159 + case C160 => 160 + case C161 => 161 + case C162 => 162 + case C163 => 163 + case C164 => 164 + case C165 => 165 + case C166 => 166 + case C167 => 167 + case C168 => 168 + case C169 => 169 + case C170 => 170 + case C171 => 171 + case C172 => 172 + case C173 => 173 + case C174 => 174 + case C175 => 175 + case C176 => 176 + case C177 => 177 + case C178 => 178 + case C179 => 179 + case C180 => 180 + case C181 => 181 + case C182 => 182 + case C183 => 183 + case C184 => 184 + case C185 => 185 + case C186 => 186 + case C187 => 187 + case C188 => 188 + case C189 => 189 + case C190 => 190 + case C191 => 191 + case C192 => 192 + case C193 => 193 + case C194 => 194 + case C195 => 195 + case C196 => 196 + case C197 => 197 + case C198 => 198 + case C199 => 199 + case C200 => 200 + case C201 => 201 + case C202 => 202 + case C203 => 203 + case C204 => 204 + case C205 => 205 + case C206 => 206 + case C207 => 207 + case C208 => 208 + case C209 => 209 + case C210 => 210 + case C211 => 211 + case C212 => 212 + case C213 => 213 + case C214 => 214 + case C215 => 215 + case C216 => 216 + case C217 => 217 + case C218 => 218 + case C219 => 219 + case C220 => 220 + case C221 => 221 + case C222 => 222 + case C223 => 223 + case C224 => 224 + case C225 => 225 + case C226 => 226 + case C227 => 227 + case C228 => 228 + case C229 => 229 + case C230 => 230 + case C231 => 231 + case C232 => 232 + case C233 => 233 + case C234 => 234 + case C235 => 235 + case C236 => 236 + case C237 => 237 + case C238 => 238 + case C239 => 239 + case C240 => 240 + case C241 => 241 + case C242 => 242 + case C243 => 243 + case C244 => 244 + case C245 => 245 + case C246 => 246 + case C247 => 247 + case C248 => 248 + case C249 => 249 + case C250 => 250 + case C251 => 251 + case C252 => 252 + case C253 => 253 + case C254 => 254 + case C255 => 255 + case C256 => 256 + case C257 => 257 + case C258 => 258 + case C259 => 259 + case C260 => 260 + case C261 => 261 + case C262 => 262 + case C263 => 263 + case C264 => 264 + case C265 => 265 + case C266 => 266 + case C267 => 267 + case C268 => 268 + case C269 => 269 + case C270 => 270 + case C271 => 271 + case C272 => 272 + case C273 => 273 + case C274 => 274 + case C275 => 275 + case C276 => 276 + case C277 => 277 + case C278 => 278 + case C279 => 279 + case C280 => 280 + case C281 => 281 + case C282 => 282 + case C283 => 283 + case C284 => 284 + case C285 => 285 + case C286 => 286 + case C287 => 287 + case C288 => 288 + case C289 => 289 + case C290 => 290 + case C291 => 291 + case C292 => 292 + case C293 => 293 + case C294 => 294 + case C295 => 295 + case C296 => 296 + case C297 => 297 + case C298 => 298 + case C299 => 299 + case C300 => 300 + case C301 => 301 + case C302 => 302 + case C303 => 303 + case C304 => 304 + case C305 => 305 + case C306 => 306 + case C307 => 307 + case C308 => 308 + case C309 => 309 + case C310 => 310 + case C311 => 311 + case C312 => 312 + case C313 => 313 + case C314 => 314 + case C315 => 315 + case C316 => 316 + case C317 => 317 + case C318 => 318 + case C319 => 319 + case C320 => 320 + case C321 => 321 + case C322 => 322 + case C323 => 323 + case C324 => 324 + case C325 => 325 + case C326 => 326 + case C327 => 327 + case C328 => 328 + case C329 => 329 + case C330 => 330 + case C331 => 331 + case C332 => 332 + case C333 => 333 + case C334 => 334 + case C335 => 335 + case C336 => 336 + case C337 => 337 + case C338 => 338 + case C339 => 339 + case C340 => 340 + case C341 => 341 + case C342 => 342 + case C343 => 343 + case C344 => 344 + case C345 => 345 + case C346 => 346 + case C347 => 347 + case C348 => 348 + case C349 => 349 + case C350 => 350 + case C351 => 351 + case C352 => 352 + case C353 => 353 + case C354 => 354 + case C355 => 355 + case C356 => 356 + case C357 => 357 + case C358 => 358 + case C359 => 359 + case C360 => 360 + case C361 => 361 + case C362 => 362 + case C363 => 363 + case C364 => 364 + case C365 => 365 + case C366 => 366 + case C367 => 367 + case C368 => 368 + case C369 => 369 + case C370 => 370 + case C371 => 371 + case C372 => 372 + case C373 => 373 + case C374 => 374 + case C375 => 375 + case C376 => 376 + case C377 => 377 + case C378 => 378 + case C379 => 379 + case C380 => 380 + case C381 => 381 + case C382 => 382 + case C383 => 383 + case C384 => 384 + case C385 => 385 + case C386 => 386 + case C387 => 387 + case C388 => 388 + case C389 => 389 + case C390 => 390 + case C391 => 391 +// case C392 => 392 + case C393 => 393 + case C394 => 394 + case C395 => 395 + case C396 => 396 +// case C397 => 397 + case C398 => 398 + case C399 => 399 + case C400 => 400 + } +} diff --git a/test/junit/scala/tools/nsc/transform/patmat/SolvingTest.scala b/test/junit/scala/tools/nsc/transform/patmat/SolvingTest.scala index 1fe7b19056..7bcb90a2ee 100644 --- a/test/junit/scala/tools/nsc/transform/patmat/SolvingTest.scala +++ b/test/junit/scala/tools/nsc/transform/patmat/SolvingTest.scala @@ -52,6 +52,8 @@ object TestSolver extends Logic with Solving { def domainSyms = None + def groupedDomains: List[Set[TestSolver.Sym]] = Nil + def implications = Nil def mayBeNull = false @@ -207,11 +209,44 @@ class SolvingTest { import scala.tools.nsc.transform.patmat.TestSolver.TestSolver._ - implicit val Ord: Ordering[TestSolver.TestSolver.Model] = Ordering.by { - _.toSeq.sortBy(_.toString()).toIterable + object SymName { + def unapply(s: Sym): Option[String] = { + val Var(Tree(name)) = s.variable + Some(name) + } + } + + implicit val ModelOrd: Ordering[TestSolver.TestSolver.Model] = Ordering.by { + _.toSeq.sortWith { + case ((sym1, v1), (sym2, v2)) => + val SymName(name1) = sym1 + val SymName(name2) = sym2 + if (name1 < name2) + true + else if (name1 > name2) + false + else + v1 < v2 + }.toIterable + } + + implicit val SolutionOrd: Ordering[TestSolver.TestSolver.Solution] = + Ordering.by(_.model) + + def formatSolution(solution: Solution): String = { + formatModel(solution.model) } - private def sym(name: String) = Sym(Var(Tree(name)), NullConst) + def formatModel(model: Model): String = { + (for { + (SymName(name), value) <- model + } yield { + val v = if (value) "T" else "F" + s"$name -> $v" + }).mkString(", ") + } + + def sym(name: String) = Sym(Var(Tree(name)), NullConst) @Test def testSymCreation() { @@ -553,6 +588,23 @@ class SolvingTest { assertEquals(tseitinNoUnassigned, expansionNoUnassigned) } } + + def pairWiseEncoding(ops: List[Sym]) = { + And(ops.combinations(2).collect { + case a :: b :: Nil => Or(Not(a), Not(b)) + }.toSet[TestSolver.TestSolver.Prop]) + } + + @Test + def testAtMostOne() { + val dummySym = sym("dummy") + val syms = "pqrstu".map(c => sym(c.toString)).toList + // expand unassigned variables + // (otherwise solutions can not be compared) + val expected = TestSolver.TestSolver.findAllModelsFor(propToSolvable(And(dummySym, pairWiseEncoding(syms)))).flatMap(expandUnassigned) + val actual = TestSolver.TestSolver.findAllModelsFor(propToSolvable(And(dummySym, AtMostOne(syms)))).flatMap(expandUnassigned) + assertEquals(expected.toSet, actual.toSet) + } } |