Common code to create AndPredicate or OrPredicate instances.
| 667 | |
| 668 | // Common code to create AndPredicate or OrPredicate instances. |
| 669 | Predicate* PredicateFactory::MakeAndOrImpl( |
| 670 | absl::Span<Predicate* const> operands, bool is_and) { |
| 671 | Predicate::Kind pred_kind = |
| 672 | is_and ? Predicate::Kind::kAnd : Predicate::Kind::kOr; |
| 673 | |
| 674 | IncrementStackDepth stack_frame(this); |
| 675 | if (stack_frame.HasOverflowed()) { |
| 676 | return MakeInternedAndOr( |
| 677 | std::vector<Predicate*>(operands.begin(), operands.end()), pred_kind); |
| 678 | } |
| 679 | |
| 680 | Predicate::Kind other_pred_kind = |
| 681 | is_and ? Predicate::Kind::kOr : Predicate::Kind::kAnd; |
| 682 | absl::flat_hash_set<Predicate*> simplified_ops_set; |
| 683 | std::vector<Predicate*> simplified_ops; |
| 684 | for (Predicate* op : operands) { |
| 685 | // Simplify A&A => A and A|A => A. |
| 686 | if (!simplified_ops_set.insert(op).second) { |
| 687 | continue; |
| 688 | } |
| 689 | |
| 690 | if (op->kind() == pred_kind) { |
| 691 | // "Inline" the operands of an inner And/Or into the parent And/Or. |
| 692 | for (Predicate* subop : op->GetOperands()) { |
| 693 | if (simplified_ops_set.insert(subop).second) { |
| 694 | simplified_ops.push_back(subop); |
| 695 | } |
| 696 | } |
| 697 | } else { |
| 698 | simplified_ops.push_back(op); |
| 699 | } |
| 700 | } |
| 701 | |
| 702 | if (simplified_ops.size() == 1) { |
| 703 | return simplified_ops[0]; |
| 704 | } |
| 705 | |
| 706 | // Simplify "A&~A=>False" and "A|~A=>True". |
| 707 | absl::flat_hash_set<Predicate*> negated_ops; |
| 708 | for (Predicate* op : simplified_ops) { |
| 709 | if (negated_ops.count(op)) { |
| 710 | // Simple case: |
| 711 | // |
| 712 | // A & ~A & ... == False |
| 713 | // A | ~A | ... == True |
| 714 | return is_and ? MakeFalse() : MakeTrue(); |
| 715 | } |
| 716 | |
| 717 | Predicate* negated_op = MakeNotPredicate(op); |
| 718 | if (negated_op->kind() == pred_kind) { |
| 719 | // Slightly more complicated case: |
| 720 | // |
| 721 | // (~A | ~B | ~C) & A & B & C & ... == |
| 722 | // ~(A & B & C) & (A & B & C) & ... == False |
| 723 | // |
| 724 | // (~A & ~B & ~C) | A | B | C | ... == |
| 725 | // ~(A | B | C) | (A | B | C) | ... == True |
| 726 | if (absl::c_all_of(negated_op->GetOperands(), [&](Predicate* p) { |
nothing calls this directly
no test coverage detected