mcs/class/referencesource/System.Data.Entity/System/Data/Common/Utils/Boolean/Simplifier.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="Simplifier.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner [....]
   7 // @backupOwner [....]
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Text;
  13 using System.Diagnostics;
  14
  15 namespace System.Data.Common.Utils.Boolean
  16 {
  17     // Simplifier visitor for Boolean expressions. Performs the following
  18     // simplifications bottom-up:
  19     // - Eliminate True and False (A Or False iff. A, A And True iff. A)
  20     // - Resolve tautology (A Or !A iff. True, True Or A iff. True) and
  21     // contradiction (A And !A iff. False, False And A iff. False)
  22     // - Flatten nested negations (!!A iff. A)
  23     // - Evaluate bound literals (!True iff. False, etc.)
  24     // - Flatten unary/empty And/Or expressions
  25     internal class Simplifier<T_Identifier> : BasicVisitor<T_Identifier>
  26     {
  27         internal static readonly Simplifier<T_Identifier> Instance = new Simplifier<T_Identifier>();
  28
  29         protected Simplifier()
  30         {
  31         }
  32
  33         internal override BoolExpr<T_Identifier> VisitNot(NotExpr<T_Identifier> expression)
  34         {
  35             BoolExpr<T_Identifier> child = expression.Child.Accept(this);
  36             switch (child.ExprType)
  37             {
  38                 case ExprType.Not:
  39                     return ((NotExpr<T_Identifier>)child).Child;
  40                 case ExprType.True: return FalseExpr<T_Identifier>.Value;
  41                 case ExprType.False: return TrueExpr<T_Identifier>.Value;
  42                 default: return base.VisitNot(expression);
  43             }
  44         }
  45
  46         internal override BoolExpr<T_Identifier> VisitAnd(AndExpr<T_Identifier> expression)
  47         {
  48             return SimplifyTree(expression);
  49         }
  50
  51         internal override BoolExpr<T_Identifier> VisitOr(OrExpr<T_Identifier> expression)
  52         {
  53             return SimplifyTree(expression);
  54         }
  55
  56         private BoolExpr<T_Identifier> SimplifyTree(TreeExpr<T_Identifier> tree)
  57         {
  58             bool isAnd = ExprType.And == tree.ExprType;
  59             Debug.Assert(isAnd || ExprType.Or == tree.ExprType);
  60
  61             // Get list of simplified children, flattening nested And/Or expressions
  62             List<BoolExpr<T_Identifier>> simplifiedChildren = new List<BoolExpr<T_Identifier>>(tree.Children.Count);
  63             foreach (BoolExpr<T_Identifier> child in tree.Children)
  64             {
  65                 BoolExpr<T_Identifier> simplifiedChild = child.Accept(this);
  66                 // And(And(A, B), C) iff. And(A, B, C)
  67                 // Or(Or(A, B), C) iff. Or(A, B, C)
  68                 if (simplifiedChild.ExprType == tree.ExprType)
  69                 {
  70                     simplifiedChildren.AddRange(((TreeExpr<T_Identifier>)simplifiedChild).Children);
  71                 }
  72                 else
  73                 {
  74                     simplifiedChildren.Add(simplifiedChild);
  75                 }
  76             }
  77
  78             // Track negated children separately to identify tautologies and contradictions
  79             Dictionary<BoolExpr<T_Identifier>, bool> negatedChildren = new Dictionary<BoolExpr<T_Identifier>, bool>(tree.Children.Count);
  80             List<BoolExpr<T_Identifier>> otherChildren = new List<BoolExpr<T_Identifier>>(tree.Children.Count);
  81             foreach (BoolExpr<T_Identifier> simplifiedChild in simplifiedChildren)
  82             {
  83                 switch (simplifiedChild.ExprType)
  84                 {
  85                     case ExprType.Not:
  86                         negatedChildren[((NotExpr<T_Identifier>)simplifiedChild).Child] = true;
  87                         break;
  88                     case ExprType.False:
  89                         // False And A --> False
  90                         if (isAnd) { return FalseExpr<T_Identifier>.Value; }
  91                         // False || A --> A (omit False from child collections)
  92                         break;
  93                     case ExprType.True:
  94                         // True Or A --> True
  95                         if (!isAnd) { return TrueExpr<T_Identifier>.Value; }
  96                         // True And A --> A (omit True from child collections)
  97                         break;
  98                     default:
  99                         otherChildren.Add(simplifiedChild);
 100                         break;
 101                 }
 102             }
 103             List<BoolExpr<T_Identifier>> children = new List<BoolExpr<T_Identifier>>();
 104             foreach (BoolExpr<T_Identifier> child in otherChildren)
 105             {
 106                 if (negatedChildren.ContainsKey(child))
 107                 {
 108                     // A && !A --> False, A || !A --> True
 109                     if (isAnd) { return FalseExpr<T_Identifier>.Value; }
 110                     else { return TrueExpr<T_Identifier>.Value; }
 111                 }
 112                 children.Add(child);
 113             }
 114             foreach (BoolExpr<T_Identifier> child in negatedChildren.Keys)
 115             {
 116                 children.Add(child.MakeNegated());
 117             }
 118             if (0 == children.Count)
 119             {
 120                 // And() iff. True
 121                 if (isAnd) { return TrueExpr<T_Identifier>.Value; }
 122                 // Or() iff. False
 123                 else { return FalseExpr<T_Identifier>.Value; }
 124             }
 125             else if (1 == children.Count)
 126             {
 127                 // Or(A) iff. A, And(A) iff. A
 128                 return children[0];
 129             }
 130             else
 131             {
 132                 // Construct simplified And/Or expression
 133                 TreeExpr<T_Identifier> result;
 134                 if (isAnd) { result = new AndExpr<T_Identifier>(children); }
 135                 else { result = new OrExpr<T_Identifier>(children); }
 136                 return result;
 137             }
 138         }
 139     }
 140 }