File: System\Data\Mapping\ViewGeneration\Structures\BoolExpression.cs
Project: ndp\fx\src\DataEntity\System.Data.Entity.csproj (System.Data.Entity)
//---------------------------------------------------------------------
// <copyright file="BoolExpression.cs" company="Microsoft">
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------
 
using System.Collections.Generic;
using System.Data.Common.CommandTrees;
using System.Data.Common.Utils;
using System.Data.Common.Utils.Boolean;
using System.Data.Entity;
using System.Diagnostics;
using System.Linq;
using System.Text;
 
namespace System.Data.Mapping.ViewGeneration.Structures
{
    using BoolDomainConstraint = DomainConstraint<BoolLiteral, Constant>;
    using DomainAndExpr = AndExpr<DomainConstraint<BoolLiteral, Constant>>;
    using DomainBoolExpr = BoolExpr<DomainConstraint<BoolLiteral, Constant>>;
    using DomainFalseExpr = FalseExpr<DomainConstraint<BoolLiteral, Constant>>;
    using DomainNotExpr = NotExpr<DomainConstraint<BoolLiteral, Constant>>;
    using DomainOrExpr = OrExpr<DomainConstraint<BoolLiteral, Constant>>;
    using DomainTermExpr = TermExpr<DomainConstraint<BoolLiteral, Constant>>;
    using DomainTrueExpr = TrueExpr<DomainConstraint<BoolLiteral, Constant>>;
 
 
    // This class represents an arbitrary boolean expression
    internal partial class BoolExpression : InternalBase
    {
 
        #region Constructors
        // effects: Create a boolean expression from a literal value
        internal static BoolExpression CreateLiteral(BoolLiteral literal, MemberDomainMap memberDomainMap)
        {
            DomainBoolExpr expr = literal.GetDomainBoolExpression(memberDomainMap);
            return new BoolExpression(expr, memberDomainMap);
        }
 
        // effects: Creates a new boolean expression using the memberDomainMap of this expression
        internal BoolExpression Create(BoolLiteral literal)
        {
            DomainBoolExpr expr = literal.GetDomainBoolExpression(m_memberDomainMap);
            return new BoolExpression(expr, m_memberDomainMap);
        }
 
        // effects: Create a boolean expression of the form "NOT expression"
        internal static BoolExpression CreateNot(BoolExpression expression)
        {
            return new BoolExpression(ExprType.Not, new BoolExpression[] { expression });
        }
 
        // effects: Create a boolean expression of the form "children[0] AND
        // children[1] AND ..."
        internal static BoolExpression CreateAnd(params BoolExpression[] children)
        {
            return new BoolExpression(ExprType.And, children);
        }
 
        // effects: Create a boolean expression of the form "children[0] OR
        // children[1] OR ..."
        internal static BoolExpression CreateOr(params BoolExpression[] children)
        {
            return new BoolExpression(ExprType.Or, children);
        }
 
        internal static BoolExpression CreateAndNot(BoolExpression e1, BoolExpression e2)
        {
            return CreateAnd(e1, CreateNot(e2));
        }
 
        // effects: Creates a new boolean expression using the memberDomainMap of this expression
        internal BoolExpression Create(DomainBoolExpr expression)
        {
            return new BoolExpression(expression, m_memberDomainMap);
        }
 
        // effects: Creates a boolean expression corresponding to TRUE (if
        // isTrue is true) or FALSE (if isTrue is false)
        private BoolExpression(bool isTrue)
        {
            if (isTrue)
            {
                m_tree = DomainTrueExpr.Value;
            }
            else
            {
                m_tree = DomainFalseExpr.Value;
            }
        }
 
        // effects: Given the operation type (AND/OR/NOT) and the relevant number of
        // children, returns the corresponding bool expression
        private BoolExpression(ExprType opType, IEnumerable<BoolExpression> children)
        {
            List<BoolExpression> childList = new List<BoolExpression>(children);
            Debug.Assert(childList.Count > 0);
            // If any child is other than true or false, it will have m_memberDomainMap set
            foreach (BoolExpression child in children)
            {
                if (child.m_memberDomainMap != null)
                {
                    m_memberDomainMap = child.m_memberDomainMap;
                    break;
                }
            }
 
            switch (opType)
            {
                case ExprType.And:
                    m_tree = new DomainAndExpr(ToBoolExprList(childList));
                    break;
                case ExprType.Or:
                    m_tree = new DomainOrExpr(ToBoolExprList(childList));
                    break;
                case ExprType.Not:
                    Debug.Assert(childList.Count == 1);
                    m_tree = new DomainNotExpr(childList[0].m_tree);
                    break;
                default:
                    Debug.Fail("Unknown expression type");
                    break;
            }
        }
 
        // effects: Creates a boolean expression based on expr
        internal BoolExpression(DomainBoolExpr expr, MemberDomainMap memberDomainMap)
        {
            m_tree = expr;
            m_memberDomainMap = memberDomainMap;
        }
        #endregion
 
        #region Fields
        private DomainBoolExpr m_tree; // The actual tree that has the expression
        // Domain map for various member paths - can be null
        private readonly MemberDomainMap m_memberDomainMap;
        private Converter<BoolDomainConstraint> m_converter;
 
        internal static readonly IEqualityComparer<BoolExpression> EqualityComparer = new BoolComparer();
        internal static readonly BoolExpression True = new BoolExpression(true);
        internal static readonly BoolExpression False = new BoolExpression(false);
        #endregion
 
        #region Properties
        // requires: this is of the form "True", "Literal" or "Literal AND ... AND Literal".
        // effects: Yields the individual atoms in this (for True does not
        // yield anything)
        internal IEnumerable<BoolExpression> Atoms
        {
            get
            {
                // Create the terms visitor and visit it to get atoms (it
                // ensures that there are no ANDs or NOTs in the expression)
                IEnumerable<DomainTermExpr> atoms = TermVisitor.GetTerms(m_tree, false);
                foreach (DomainTermExpr atom in atoms)
                {
                    yield return new BoolExpression(atom, m_memberDomainMap);
                }
            }
        }
 
        // effects: Yields all the leaves in this
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        internal IEnumerable<BoolLiteral> Leaves
        {
            get
            {
                // Create the term visitor and visit it to get terms
                IEnumerable<DomainTermExpr> terms = TermVisitor.GetTerms(m_tree, true);
                foreach (DomainTermExpr term in terms)
                {
                    yield return term.Identifier.Variable.Identifier;
                }
            }
        }
 
 
        // effects: if this expression is a boolean expression of type BoolLiteral
        // Returns the literal, else returns null
        internal BoolLiteral AsLiteral
        {
            get
            {
                DomainTermExpr literal = m_tree as DomainTermExpr;
                if (literal == null) { return null; }
                BoolLiteral result = GetBoolLiteral(literal);
                return result;
            }
        }
 
        // effects: Given a term expression, extracts the BoolLiteral from it
        internal static BoolLiteral GetBoolLiteral(DomainTermExpr term)
        {
            DomainConstraint<BoolLiteral, Constant> domainConstraint = term.Identifier;
            DomainVariable<BoolLiteral, Constant> variable = domainConstraint.Variable;
            return variable.Identifier;
        }
 
        // effects: Returns true iff this corresponds to the boolean literal "true" 
        internal bool IsTrue
        {
            get
            {
                return m_tree.ExprType == ExprType.True;
            }
        }
 
        // effects: Returns true iff this corresponds to the boolean literal "false" 
        internal bool IsFalse
        {
            get
            {
                return m_tree.ExprType == ExprType.False;
            }
        }
 
        // effects: Returns true if the expression always evaluates to true
        internal bool IsAlwaysTrue()
        {
            InitializeConverter();
            return m_converter.Vertex.IsOne();
        }
 
        // effects: Returns true if there is a possible assignment to
        // variables in this such that the expression evaluates to true
        internal bool IsSatisfiable()
        {
            return !IsUnsatisfiable();
        }
 
        // effects: Returns true if there is no possible assignment to
        // variables in this such that the expression evaluates to true,
        // i.e., the expression will always evaluate to false
        internal bool IsUnsatisfiable()
        {
            InitializeConverter();
            return m_converter.Vertex.IsZero();
        }
 
        // effects: Returns the internal tree in this
        internal DomainBoolExpr Tree
        {
            get { return m_tree; }
        }
 
        internal IEnumerable<DomainConstraint<BoolLiteral, Constant>> VariableConstraints
        {
            get { return LeafVisitor<DomainConstraint<BoolLiteral, Constant>>.GetLeaves(m_tree); }
        }
 
        internal IEnumerable<DomainVariable<BoolLiteral, Constant>> Variables
        {
            get { return VariableConstraints.Select(domainConstraint => domainConstraint.Variable); }
        }
 
        internal IEnumerable<MemberRestriction> MemberRestrictions
        {
            get
            {
                foreach (DomainVariable<BoolLiteral, Constant> var in Variables)
                {
                    MemberRestriction variableCondition = var.Identifier as MemberRestriction;
                    if (variableCondition != null)
                    {
                        yield return variableCondition;
                    }
                }
            }
        }
 
        #endregion
 
        #region Methods
 
        // effects: Given a sequence of boolean expressions, yields the
        // corresponding trees in it in the same order
        private IEnumerable<DomainBoolExpr> ToBoolExprList(IEnumerable<BoolExpression> nodes)
        {
            foreach (BoolExpression node in nodes)
            {
                yield return node.m_tree;
            }
        }
 
 
        /// <summary>
        /// Whether the boolean expression contains only OneOFTypeConst variables.
        /// </summary>
        internal bool RepresentsAllTypeConditions
        {
            get
            {
                return this.MemberRestrictions.All(var => (var is TypeRestriction));
            }
        }
 
 
        internal BoolExpression RemapLiterals(Dictionary<BoolLiteral, BoolLiteral> remap)
        {
            var rewriter = new BooleanExpressionTermRewriter<BoolDomainConstraint, BoolDomainConstraint>(
                //                term => remap[BoolExpression.GetBoolLiteral(term)].GetDomainBoolExpression(m_memberDomainMap));
                delegate(DomainTermExpr term)
                {
                    BoolLiteral newLiteral;
                    return remap.TryGetValue(BoolExpression.GetBoolLiteral(term), out newLiteral) ?
                        newLiteral.GetDomainBoolExpression(m_memberDomainMap) : term;
                });
            return new BoolExpression(m_tree.Accept(rewriter), m_memberDomainMap);
        }
 
        // effects: Given a boolean expression, modifies requiredSlots
        // to indicate which slots are required to generate the expression
        // projectedSlotMap indicates a mapping from member paths to slot
        // numbers (that need to be checked off in requiredSlots)
        internal virtual void GetRequiredSlots(MemberProjectionIndex projectedSlotMap, bool[] requiredSlots)
        {
            RequiredSlotsVisitor.GetRequiredSlots(m_tree, projectedSlotMap, requiredSlots);
        }
 
        /// <summary>
        /// Given the <paramref name="blockAlias"/> for the block in which the expression resides, converts the expression into eSQL.
        /// </summary>
        internal StringBuilder AsEsql(StringBuilder builder, string blockAlias)
        {
            return AsEsqlVisitor.AsEsql(m_tree, builder, blockAlias);
        }
 
        /// <summary>
        /// Given the <paramref name="row"/> for the input, converts the expression into CQT.
        /// </summary>
        internal DbExpression AsCqt(DbExpression row)
        {
            return AsCqtVisitor.AsCqt(m_tree, row);
        }
        
        internal StringBuilder AsUserString(StringBuilder builder, string blockAlias, bool writeRoundtrippingMessage)
        {
            if (writeRoundtrippingMessage)
            {
                builder.AppendLine(Strings.Viewgen_ConfigurationErrorMsg(blockAlias));
                builder.Append("  ");
            }
            return AsUserStringVisitor.AsUserString(m_tree, builder, blockAlias);
        }
 
        internal override void ToCompactString(StringBuilder builder)
        {
            CompactStringVisitor.ToBuilder(m_tree, builder);
        }
 
        // effects: Given a mapping from old jointree nodes to new ones,
        // creates a boolean expression from "this" in which the references
        // to old join tree nodes are replaced by references to new nodes
        // from remap (boolean expressions other than constants can contain
        // references to jointree nodes, e.g., "var in values" -- var is a
        // reference to a JoinTreeNode
        internal BoolExpression RemapBool(Dictionary<MemberPath, MemberPath> remap)
        {
            DomainBoolExpr expr = RemapBoolVisitor.RemapExtentTreeNodes(m_tree, m_memberDomainMap, remap);
            return new BoolExpression(expr, m_memberDomainMap);
        }
 
        // effects: Given a list of bools, returns a list of boolean expressions where each
        // boolean in bools has been ANDed with conjunct
        // CHANGE_Microsoft_IMPROVE: replace with lambda pattern
        internal static List<BoolExpression> AddConjunctionToBools(List<BoolExpression> bools,
                                                                   BoolExpression conjunct)
        {
            List<BoolExpression> result = new List<BoolExpression>();
            // Go through the list -- AND each non-null boolean with conjunct
            foreach (BoolExpression b in bools)
            {
                if (null == b)
                { // unused boolean -- leave as it is
                    result.Add(null);
                }
                else
                {
                    result.Add(CreateAnd(b, conjunct));
                }
            }
            return result;
        }
 
        private void InitializeConverter()
        {
            if (null != m_converter)
            {
                // already done
                return;
            }
 
            m_converter = new Converter<BoolDomainConstraint>(m_tree,
                IdentifierService<BoolDomainConstraint>.Instance.CreateConversionContext());
        }
 
        internal BoolExpression MakeCopy()
        {
            BoolExpression copy = Create(m_tree.Accept(CopyVisitorInstance));
            return copy;
        }
        static readonly CopyVisitor CopyVisitorInstance = new CopyVisitor();
        private class CopyVisitor : BasicVisitor<BoolDomainConstraint> { }
 
        internal void ExpensiveSimplify()
        {
            if (!IsFinal())
            {
                m_tree = m_tree.Simplify();
                return;
            }
 
            InitializeConverter();
            m_tree = m_tree.ExpensiveSimplify(out m_converter);
            // this call is needed because the possible values on restriction and TrueFalseLiterals
            // may change and need to be synchronized
            FixDomainMap(m_memberDomainMap);
        }
 
        internal void FixDomainMap(MemberDomainMap domainMap)
        {
            Debug.Assert(domainMap != null, "Member domain map is not set");
            m_tree = FixRangeVisitor.FixRange(m_tree, domainMap);
        }
 
        private bool IsFinal()
        {
            // First call simplify to get rid of tautologies and true, false
            // etc. and then collapse the OneOfs
            return (m_memberDomainMap != null && IsFinalVisitor.IsFinal(m_tree));
        }
 
        #endregion
 
        #region Comparer class
        // This class compares boolean expressions
        private class BoolComparer : IEqualityComparer<BoolExpression>
        {
 
            #region IEqualityComparer<BoolExpression> Members
            public bool Equals(BoolExpression left, BoolExpression right)
            {
                // Quick check with references
                if (object.ReferenceEquals(left, right))
                {
                    // Gets the Null and Undefined case as well
                    return true;
                }
                // One of them is non-null at least
                if (left == null || right == null)
                {
                    return false;
                }
                // Both are non-null at this point
                return left.m_tree.Equals(right.m_tree);
            }
 
            public int GetHashCode(BoolExpression expression)
            {
                return expression.m_tree.GetHashCode();
            }
            #endregion
        }
        #endregion
    }
}