Whole file
bastikr/boolean.py
The author described this change as “Fix for #45 Do not simplify() by default”. It counts as a record because the check below fails on the code as it stood at 82db01eb3 and passes on 5430d5aa7, with nothing else changed between the two runs.
Projectbastikr/boolean.py
Fix saved2016-05-13
Sharing licenceBSD-2-Clause · LICENSE.txt
Change size+661 −661
What the code was meant to do, written into the code itself as a save note
Fix for #45 Do not simplify() by default
The change
| 174 | 174 | """ | |
| 175 | 175 | return tuple(map(self.Symbol, args)) | |
| 176 | 176 | ||
| 177 | - | def parse(self, expr, simplify=True): | |
| 178 | - | """ | |
| 179 | - | Return a boolean expression parsed from `expr` either a unicode string | |
| 180 | - | or tokens iterable. | |
| 181 | - | ||
| 182 | - | Optionally simplify the expression if `simplify` is True. | |
| 183 | - | ||
| 184 | - | Raise ParseError on errors. | |
| 185 | - | ||
| 186 | - | If `expr` is a string, the standard `tokenizer` is used for tokenization | |
| 187 | - | and the algebra configured Symbol type is used to create Symbol | |
| 188 | - | instances from Symbol tokens. | |
| 189 | - | ||
| 190 | - | If `expr` is an iterable, it should contain 3-tuples of: (token, | |
| 191 | - | token_string, position). In this case, the `token` can be a Symbol | |
| 192 | - | instance or one of the TOKEN_* types. | |
| 193 | - | See the `tokenize()` method for detailed specification. | |
| 194 | - | """ | |
| 195 | - | ||
| 196 | - | precedence = {self.NOT: 5, self.AND: 10, self.OR: 15, TOKEN_LPAR: 20} | |
| 197 | - | ||
| 198 | - | if isinstance(expr, basestring): | |
| 199 | - | tokenized = self.tokenize(expr) | |
| 200 | - | else: | |
| 201 | - | tokenized = iter(expr) | |
| 202 | - | ||
| 203 | - | ast = [None, None] | |
| 204 | - | ||
| 205 | - | for token, tokstr, position in tokenized: | |
| 206 | - | if token == TOKEN_SYMBOL: | |
| 207 | - | ast.append(self.Symbol(tokstr)) | |
| 208 | - | elif isinstance(token, Symbol): | |
| 209 | - | ast.append(token) | |
| 210 | - | ||
| 211 | - | elif token == TOKEN_TRUE: | |
| 212 | - | ast.append(self.TRUE) | |
| 213 | - | elif token == TOKEN_FALSE: | |
| 214 | - | ast.append(self.FALSE) | |
| 215 | - | ||
| 216 | - | elif token == TOKEN_NOT: | |
| 217 | - | ast = [ast, self.NOT] | |
| 218 | - | elif token == TOKEN_AND: | |
| 219 | - | ast = self._start_operation(ast, self.AND, precedence) | |
| 220 | - | elif token == TOKEN_OR: | |
| 221 | - | ast = self._start_operation(ast, self.OR, precedence) | |
| 222 | - | ||
| 223 | - | elif token == TOKEN_LPAR: | |
| 224 | - | ast = [ast, TOKEN_LPAR] | |
| 225 | - | elif token == TOKEN_RPAR: | |
| 226 | - | while True: | |
| 227 | - | if ast[0] is None: | |
| 228 | - | raise ParseError(token, tokstr, position, | |
| 229 | - | PARSE_UNBALANCED_CLOSING_PARENS) | |
| 230 | - | if ast[1] is TOKEN_LPAR: | |
| 231 | - | ast[0].append(ast[2]) | |
| 232 | - | ast = ast[0] | |
| 233 | - | break | |
| 234 | - | subex = ast[1](*ast[2:]) | |
| 235 | - | ast[0].append(subex) | |
| 236 | - | ast = ast[0] | |
| 237 | - | else: | |
| 238 | - | raise ParseError(token, tokstr, position, PARSE_UNKNOWN_TOKEN) | |
| 239 | - | ||
| 240 | - | while True: | |
| 241 | - | if ast[0] is None: | |
| 242 | - | if ast[1] is None: | |
| 243 | - | ||
| 244 | - | if len(ast) != 3: | |
| 245 | - | raise ParseError(error_code=PARSE_INVALID_EXPRESSION) | |
| 246 | - | parsed = ast[2] | |
| 247 | - | else: | |
| 248 | - | parsed = ast[1](*ast[2:]) | |
| 249 | - | break | |
| 250 | - | else: | |
| 251 | - | subex = ast[1](*ast[2:]) | |
| 252 | - | ast[0].append(subex) | |
| 253 | - | ast = ast[0] | |
| 254 | - | ||
| 255 | - | if simplify: | |
| 256 | - | return parsed.simplify() | |
| 257 | - | return parsed | |
| 258 | - | ||
| 259 | - | def _start_operation(self, ast, operation, precedence): | |
| 260 | - | """ | |
| 261 | - | Returns an AST where all operations of lower precedence are finalized. | |
| 262 | - | """ | |
| 263 | - | op_prec = precedence[operation] | |
| 264 | - | while True: | |
| 265 | - | if ast[1] is None: # [None, None, x] | |
| 266 | - | ast[1] = operation | |
| 267 | - | return ast | |
| 268 | - | ||
| 269 | - | prec = precedence[ast[1]] | |
| 270 | - | if prec > op_prec: # op=*, [ast, +, x, y] -> [[ast, +, x], *, y] | |
| 271 | - | ast = [ast, operation, ast.pop(-1)] | |
| 272 | - | return ast | |
| 273 | - | ||
| 274 | - | if prec == op_prec: # op=*, [ast, *, x] -> [ast, *, x] | |
| 275 | - | return ast | |
| 276 | - | ||
| 277 | - | if ast[0] is None: # op=+, [None, *, x, y] -> [None, +, x*y] | |
| 278 | - | subexp = ast[1](*ast[2:]) | |
| 279 | - | return [ast[0], operation, subexp] | |
| 280 | - | ||
| 281 | - | else: # op=+, [[ast, *, x], ~, y] -> [ast, *, x, ~y] | |
| 282 | - | ast[0].append(ast[1](*ast[2:])) | |
| 283 | - | ast = ast[0] | |
| 284 | - | ||
| 285 | - | def tokenize(self, expr): | |
| 286 | - | """ | |
| 287 | - | Return an iterable of 3-tuple describing each token given an expression | |
| 288 | - | unicode string. | |
| 289 | - | ||
| 290 | - | This 3-tuple contains (token, token string, position): | |
| 291 | - | - token: either a Symbol instance or one of TOKEN_* token types.. | |
| 292 | - | - token string: the original token unicode string. | |
| 293 | - | - position: some simple object describing the starting position of the | |
| 294 | - | original token string in the `expr` string. It can be an int for a | |
| 295 | - | character offset, or a tuple of starting (row/line, column). | |
| 296 | - | ||
| 297 | - | The token position is used only for error reporting and can be None or | |
| 298 | - | empty. | |
| 299 | - | ||
| 300 | - | Raise ParseError on errors. The ParseError.args is a tuple of: | |
| 301 | - | (token_string, position, error message) | |
| 302 | - | ||
| 303 | - | You can use this tokenizer as a base to create specialized tokenizers | |
| 304 | - | for your custom algebra by subclassing BooleanAlgebra. See also the | |
| 305 | - | tests for other examples of alternative tokenizers. | |
| 306 | - | ||
| 307 | - | This tokenizer has these characteristics: | |
| 308 | - | - The `expr` string can span multiple lines, | |
| 309 | - | - Whitespace is not significant. | |
| 310 | - | - The returned position is the starting character offset of a token. | |
| 311 | - | ||
| 312 | - | - A TOKEN_SYMBOL is returned for valid identifiers which is a string | |
| 313 | - | without spaces. These are valid identifiers: | |
| 314 | - | - Python identifiers. | |
| 315 | - | - a string even if starting with digits | |
| 316 | - | - digits (except for 0 and 1). | |
| 317 | - | - dotted names : foo.bar consist of one token. | |
| 318 | - | - names with colons: foo:bar consist of one token. | |
| 319 | - | These are not identifiers: | |
| 320 | - | - quoted strings. | |
| 321 | - | - any punctuation which is not an operation | |
| 322 | - | ||
| 323 | - | - Recognized operators are (in any upper/lower case combinations): | |
| 324 | - | - for and: '*', '&', 'and' | |
| 325 | - | - for or: '+', '|', 'or' | |
| 326 | - | - for not: '~', '!', 'not' | |
| 327 | - | ||
| 328 | - | - Recognized special symbols are (in any upper/lower case combinations): | |
| 329 | - | - True symbols: 1 and True | |
| 330 | - | - False symbols: 0, False and None | |
| 331 | - | """ | |
| 332 | - | if not isinstance(expr, basestring): | |
| 333 | - | raise TypeError('expr must be string but it is %s.' % type(expr)) | |
| 334 | - | ||
| 335 | - | # mapping of lowercase token strings to a token type id for the standard | |
| 336 | - | # operators, parens and common true or false symbols, as used in the | |
| 337 | - | # default tokenizer implementation. | |
| 338 | - | TOKENS = { | |
| 339 | - | '*': TOKEN_AND, '&': TOKEN_AND, 'and': TOKEN_AND, | |
| 340 | - | '+': TOKEN_OR, '|': TOKEN_OR, 'or': TOKEN_OR, | |
| 341 | - | '~': TOKEN_NOT, '!': TOKEN_NOT, 'not': TOKEN_NOT, | |
| 342 | - | '(': TOKEN_LPAR, ')': TOKEN_RPAR, | |
| 343 | - | '[': TOKEN_LPAR, ']': TOKEN_RPAR, | |
| 344 | - | 'true': TOKEN_TRUE, '1': TOKEN_TRUE, | |
| 345 | - | 'false': TOKEN_FALSE, '0': TOKEN_FALSE, 'none': TOKEN_FALSE | |
| 346 | - | } | |
| 347 | - | ||
| 348 | - | length = len(expr) | |
| 349 | - | position = 0 | |
| 350 | - | while position < length: | |
| 351 | - | tok = expr[position] | |
| 352 | - | ||
| 353 | - | sym = tok.isalpha() or tok == '_' | |
| 354 | - | if sym: | |
| 355 | - | position += 1 | |
| 356 | - | while position < length: | |
| 357 | - | char = expr[position] | |
| 358 | - | if char.isalnum() or char in ('.', ':', '_'): | |
| 359 | - | position += 1 | |
| 360 | - | tok += char | |
| 361 | - | else: | |
| 362 | - | break | |
| 363 | - | position -= 1 | |
| 364 | - | ||
| 365 | - | try: | |
| 366 | - | yield TOKENS[tok.lower()], tok, position | |
| 367 | - | except KeyError: | |
| 368 | - | if sym: | |
| 369 | - | yield TOKEN_SYMBOL, tok, position | |
| 370 | - | elif tok not in (' ', '\t', '\r', '\n'): | |
| 371 | - | raise ParseError(token_string=tok, position=position, | |
| 372 | - | error_code=PARSE_UNKNOWN_TOKEN) | |
| 373 | - | ||
| 374 | - | position += 1 | |
| 375 | - | ||
| 376 | - | # TODO: explain what this means exactly | |
| 377 | - | def _rdistributive(self, expr, op_example): | |
| 378 | - | """ | |
| 379 | - | Recursively flatten the `expr` expression for the `op_example` | |
| 380 | - | AND or OR operation instance exmaple. | |
| 381 | - | """ | |
| 382 | - | if expr.isliteral: | |
| 383 | - | return expr | |
| 384 | - | ||
| 385 | - | expr_class = expr.__class__ | |
| 386 | - | ||
| 387 | - | args = (self._rdistributive(arg, op_example) for arg in expr.args) | |
| 388 | - | args = tuple(arg.simplify() for arg in args) | |
| 389 | - | if len(args) == 1: | |
| 390 | - | return args[0] | |
| 391 | - | ||
| 392 | - | expr = expr_class(*args) | |
| 393 | - | ||
| 394 | - | dualoperation = op_example.dual | |
| 395 | - | if isinstance(expr, dualoperation): | |
| 396 | - | expr = expr.distributive() | |
| 397 | - | return expr | |
| 398 | - | ||
| 399 | - | def normalize(self, expr, operation): | |
| 400 | - | """ | |
| 401 | - | Return a normalized expression transformed to its normal form in the | |
| 402 | - | given AND or OR operation. | |
| 403 | - | ||
| 404 | - | The new expression arguments will satisfy these conditions: | |
| 405 | - | - operation(*args) == expr (here mathematical equality is meant) | |
| 406 | - | - the operation does not occur in any of its arg. | |
| 407 | - | - NOT is only appearing in literals (aka. Negation normal form). | |
| 408 | - | ||
| 409 | - | The operation must be an AND or OR operation or a subclass. | |
| 410 | - | """ | |
| 411 | - | # ensure that the operation is not NOT | |
| 412 | - | assert operation in (self.AND, self.OR,) | |
| 413 | - | # Move NOT inwards. | |
| 414 | - | expr = expr.literalize() | |
| 415 | - | # Simplify first otherwise _rdistributive() may take forever. | |
| 416 | - | expr = expr.simplify() | |
| 417 | - | operation_example = operation(self.TRUE, self.FALSE) | |
| 418 | - | expr = self._rdistributive(expr, operation_example) | |
| 419 | - | # Canonicalize | |
| 420 | - | expr = expr.simplify() | |
| 421 | - | if isinstance(expr, operation): | |
| 422 | - | return expr | |
| 423 | - | return operation(*expr.args) | |
| 424 | - | ||
| 425 | - | def cnf(self, expr): | |
| 426 | - | """ | |
| 427 | - | Return a conjunctive normal form of the `expr` expression. | |
| 428 | - | """ | |
| 429 | - | return self.normalize(expr, self.AND) | |
| 430 | - | ||
| 431 | - | def dnf(self, expr): | |
| 432 | - | """ | |
| 433 | - | Return a disjunctive normal form of the `expr` expression. | |
| 434 | - | """ | |
| 435 | - | return self.normalize(expr, self.OR) | |
| 436 | - | ||
| 437 | - | ||
| 438 | - | class Expression(object): | |
| 439 | - | """ | |
| 440 | - | Abstract base class for all boolean expressions, including functions and | |
| 441 | - | variable symbols. | |
| 442 | - | """ | |
| 443 | - | # Defines sort and comparison order between expressions arguments | |
| 444 | - | sort_order = None | |
| 445 | - | ||
| 446 | - | # Store arguments aka. subterms of this expressions. | |
| 447 | - | # subterms are either literals or expressions. | |
| 448 | - | args = tuple() | |
| 449 | - | ||
| 450 | - | # True is this is a literal expression such as a Symbol, TRUE or FALSE | |
| 451 | - | isliteral = False | |
| 452 | - | ||
| 453 | - | # True if this expression has been simplified to in canonical form. | |
| 454 | - | iscanonical = False | |
| 455 | - | ||
| 456 | - | # these class attributes are configured when a new BooleanAlgebra is created | |
| 457 | - | TRUE = None | |
| 458 | - | FALSE = None | |
| 459 | - | NOT = None | |
| 460 | - | AND = None | |
| 461 | - | OR = None | |
| 462 | - | Symbol = None | |
| 463 | - | ||
| 464 | - | @property | |
| 465 | - | def objects(self): | |
| 466 | - | """ | |
| 467 | - | Return a set of all associated objects with this expression symbols. | |
| 468 | - | Include recursively subexpressions objects. | |
| 469 | - | """ | |
| 470 | - | return set(s.obj for s in self.symbols) | |
| 471 | - | ||
| 472 | - | def get_literals(self): | |
| 473 | - | """ | |
| 474 | - | Return a list of all the literals contained in this expression. | |
| 475 | - | Include recursively subexpressions symbols. | |
| 476 | - | This includes duplicates. | |
| 477 | - | """ | |
| 478 | - | if self.isliteral: | |
| 479 | - | return [self] | |
| 480 | - | if not self.args: | |
| 481 | - | return [] | |
| 482 | - | return list(itertools.chain.from_iterable(arg.literals for arg in self.args)) | |
| 483 | - | ||
| 484 | - | @property | |
| 485 | - | def literals(self): | |
| 486 | - | """ | |
| 487 | - | Return a set of all literals contained in this expression. | |
| 488 | - | Include recursively subexpressions literals. | |
| 489 | - | """ | |
| 490 | - | return set(self.get_literals()) | |
| 491 | - | ||
| 492 | - | def literalize(self): | |
| 493 | - | """ | |
| 494 | - | Return an expression where NOTs are only occurring as literals. | |
| 495 | - | Applied recursively to subexpressions. | |
| 496 | - | """ | |
| 497 | - | if self.isliteral: | |
| 498 | - | return self | |
| 499 | - | args = tuple(arg.literalize() for arg in self.args) | |
| 500 | - | if all(arg is self.args[i] for i, arg in enumerate(args)): | |
| 501 | - | return self | |
| 502 | - | ||
| 503 | - | return self.__class__(*args) | |
| 504 | - | ||
| 505 | - | def get_symbols(self): | |
| 506 | - | """ | |
| 507 | - | Return a list of all the symbols contained in this expression. | |
| 508 | - | Include recursively subexpressions symbols. | |
| 509 | - | This includes duplicates. | |
| 510 | - | """ | |
| 511 | - | return [s for s in self.literals if isinstance(s, Symbol)] | |
| 512 | - | ||
| 513 | - | @property | |
| 514 | - | def symbols(self,): | |
| 515 | - | """ | |
| 516 | - | Return a list of all the symbols contained in this expression. | |
| 517 | - | Include recursively subexpressions symbols. | |
| 518 | - | This includes duplicates. | |
| 519 | - | """ | |
| 520 | - | return set(self.get_symbols()) | |
| 521 | - | ||
| 522 | - | def subs(self, substitutions, simplify=True): | |
| 523 | - | """ | |
| 524 | - | Return an expression where the expression or all subterms equal to a key | |
| 525 | - | expression are substituted with the corresponding value expression using | |
| 526 | - | a mapping of: {expr->expr to substitute.} | |
| 527 | - | ||
| 528 | - | Return this expression unmodified if nothing could be substituted. | |
| 529 | - | ||
| 530 | - | Note that this can be used to tested for expression containment. | |
| 531 | - | """ | |
| 532 | - | for expr, substitution in substitutions.items(): | |
| 533 | - | if expr == self: | |
| 534 | - | return substitution | |
| 535 | - | ||
| 536 | - | expr = self._subs(substitutions, simplify=simplify) | |
| 537 | - | return self if expr is None else expr | |
| 538 | - | ||
| 539 | - | def _subs(self, substitutions, simplify=True): | |
| 540 | - | """ | |
| 541 | - | Return an expression where all subterms equal to a key expression are | |
| 542 | - | substituted by the corresponding value expression using a mapping of: | |
| 543 | - | {expr->expr to substitute.} | |
| 544 | - | """ | |
| 545 | - | new_args = [] | |
| 546 | - | changed_something = False | |
| 547 | - | for arg in self.args: | |
| 548 | - | matched = False | |
| 549 | - | for expr, substitution in substitutions.items(): | |
| 550 | - | if arg == expr: | |
| 551 | - | new_args.append(substitution) | |
| 552 | - | changed_something = matched = True | |
| 553 | - | break | |
| 554 | - | ||
| 555 | - | if not matched: | |
| 556 | - | # FIXME: this is not right | |
| 557 | - | new_arg = None if not arg.args else arg._subs(substitutions, simplify) | |
| 558 | - | if new_arg is None: | |
| 559 | - | new_args.append(arg) | |
| 560 | - | else: | |
| 561 | - | changed_something = True | |
| 562 | - | new_args.append(new_arg) | |
| 563 | - | ||
| 564 | - | if changed_something: | |
| 565 | - | newexpr = self.__class__(*new_args) | |
| 566 | - | if simplify: | |
| 567 | - | newexpr = newexpr.simplify() | |
| 568 | - | return newexpr | |
| 569 | - | ||
| 570 | - | def simplify(self): | |
| 571 | - | """ | |
| 572 | - | Return a new simplified expression in canonical form built from this | |
| 573 | - | expression. The simplified expression may be exactly the same as this | |
| 928 further changed lines not shown | |||
The check that tells the two apart
fail→pass·boolean/test_boolean.py::BooleanAlgebraTestCase::test_creation
Check file boolean/test_boolean.py, taken without changes from the fix and copied onto the older code, so the exact same check runs against both versions.
Origin and history
The code before it82db01eb3e93a3b9939f23913d9d1667b7717298
Broken version dated2016-05-13
Moduleboolean.boolean
Units changedBooleanAlgebra, Expression, Function
Fingerprint17ce9ab77cec32c1
Checked2026-08-18 by goldset/0.1
Every field above is generated by our program. None of it is written by hand.
Other bugs found in bastikr/boolean.py
- 2024-11-15Fix absorption issue #113 #112 #111
- 2017-01-10Fix bug in normalize and write tests.
- 2016-03-27Fix bug in remove where an undefined variable was used.
- 2012-06-05Fix bug in DualBase.eval