Patmat: efficient reasoning about mutual exclusion

Faster analysis of wide (but relatively flat) class hierarchies
by using a more efficient encoding of mutual exclusion.

The old CNF encoding for mutually exclusive symbols of a domain
added a quadratic number of clauses to the formula to satisfy.

E.g. if a domain has the symbols `a`, `b` and `c` then
the clauses
```
!a \/ !b  /\
!a \/ !c  /\
!b \/ !c
```
were added.

The first line prevents that `a` and `b` are both true at the same time, etc.

There's a simple, more efficient encoding that can be used instead: consider a
comparator circuit in hardware, that checks that out of `n` signals, at most 1
is true. Such a circuit can be built in the form of a sequential counter and
thus requires only 3n-4 additional clauses [1]. A comprehensible comparison of
different encodings can be found in [2].

[1]: http://www.carstensinz.de/papers/CP-2005.pdf
[2]: http://www.wv.inf.tu-dresden.de/Publications/2013/report-13-04.pdf

1 files changed, 806 insertions, 0 deletions

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
+  }
+}