RewritingValidator.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / QueryRewriting / RewritingValidator.cs / 1 / RewritingValidator.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System.Data.Mapping.ViewGeneration.Structures; 
using System.Data.Mapping.ViewGeneration.QueryRewriting;
using System.Data.Common.Utils.Boolean;
using System.Collections.Generic;
using System.Text; 
using System.Diagnostics;
using System.Data.Mapping.ViewGeneration.Utils; 
using System.Data.Metadata.Edm; 
using System.Data.Common.Utils;
using System.Linq; 
using System.Globalization;
using System.Data.Entity;

namespace System.Data.Mapping.ViewGeneration.Validation { 

    using BoolDomainConstraint = DomainConstraint; 
 
    /// 
    /// Validates each mapping fragment/cell (Qc = Qs) 
    /// by unfolding update views in Qs and checking query equivalence
    /// 
    internal class RewritingValidator {
 
        private CellNormalizer _normalizer;
        private MemberDomainMap _domainMap; 
        private CellTreeNode _basicView; 
        private IEnumerable _keyAttributes;
        private ErrorLog _errorLog; 

        internal RewritingValidator(CellNormalizer normalizer, CellTreeNode basicView)
        {
            _normalizer = normalizer; 
            _basicView = basicView;
            _domainMap = _normalizer.MemberMaps.UpdateDomainMap; 
            _keyAttributes = MemberPath.GetKeyMembers(_normalizer.Extent, _domainMap, _normalizer.Workspace); 
            _errorLog = new ErrorLog();
        } 

        #region Main logic

        internal void Validate() 
        {
            // turn rewritings into cell trees 
            // plain: according to rewritings for case statements 
            Dictionary plainMemberValueTrees = CreateMemberValueTrees(false);
            // complement: uses complement rewriting for the last WHEN ... THEN 
            // This is how the final case statement will be generated in update views
            Dictionary complementMemberValueTrees = CreateMemberValueTrees(true);

            WhereClauseVisitor plainWhereClauseVisitor = new WhereClauseVisitor(_basicView, plainMemberValueTrees); 
            WhereClauseVisitor complementWhereClauseVisitor = new WhereClauseVisitor(_basicView, complementMemberValueTrees);
 
            // produce CellTree for each SQuery 
            foreach (LeftCellWrapper wrapper in _normalizer.AllWrappersForExtent)
            { 
                Cell cell = wrapper.OnlyInputCell;
                // construct cell tree for CQuery
                CellTreeNode cQueryTree = new LeafCellTreeNode(_normalizer, wrapper);
                // sQueryTree: unfolded update view inside S-side of the cell 
                CellTreeNode sQueryTree;
                // construct cell tree for SQuery (will be used for domain constraint checking) 
                CellTreeNode complementSQueryTreeForCondition = complementWhereClauseVisitor.GetCellTreeNode(cell.SQuery.WhereClause); 
                Debug.Assert(complementSQueryTreeForCondition != null, "Rewriting for S-side query is unsatisfiable");
                if (complementSQueryTreeForCondition == null) 
                {
                    continue; // situation should never happen
                }
                if (complementSQueryTreeForCondition != _basicView) 
                {
                    // intersect with basic expression 
                    sQueryTree = new OpCellTreeNode(_normalizer, CellTreeOpType.IJ, complementSQueryTreeForCondition, _basicView); 
                }
                else 
                {
                    sQueryTree = _basicView;
                }
 
                // Append in-set or in-end condition to both queries to produce more concise errors
                // Otherwise, the errors are of the form "if there exists an entity in extent, then violation". We don't care about empty extents 
                BoolExpression inExtentCondition = BoolExpression.CreateLiteral(wrapper.CreateRoleBoolean(), _normalizer.MemberMaps.QueryDomainMap); 

                BoolExpression unsatisfiedConstraint; 
                if (!CheckEquivalence(cQueryTree.RightFragmentQuery, sQueryTree.RightFragmentQuery, inExtentCondition,
                                      out unsatisfiedConstraint))
                {
                    string extentName = StringUtil.FormatInvariant("{0}", _normalizer.Extent); 

                    // Simplify to produce more readable error messages 
                    cQueryTree.RightFragmentQuery.Condition.ExpensiveSimplify(); 
                    sQueryTree.RightFragmentQuery.Condition.ExpensiveSimplify();
 
                    String message = Strings.ViewGen_CQ_PartitionConstraint_1(extentName);

                    ReportConstraintViolation(message, unsatisfiedConstraint, ViewGenErrorCode.PartitionConstraintViolation,
                                              cQueryTree.GetLeaves().Concat(sQueryTree.GetLeaves())); 
                }
 
                CellTreeNode plainSQueryTreeForCondition = plainWhereClauseVisitor.GetCellTreeNode(cell.SQuery.WhereClause); 
                Debug.Assert(plainSQueryTreeForCondition != null, "Rewriting for S-side query is unsatisfiable");
                if (plainSQueryTreeForCondition != null) 
                {
                    // Query is non-empty. Check domain constraints on:
                    // (a) swapped members
                    DomainConstraintVisitor.CheckConstraints(plainSQueryTreeForCondition, wrapper, _normalizer, _errorLog); 
                    // (b) projected members
                    CheckConstraintsOnProjectedConditionMembers(plainMemberValueTrees, wrapper, sQueryTree, inExtentCondition); 
                } 
                CheckConstraintsOnNonNullableMembers(plainMemberValueTrees, wrapper, sQueryTree, inExtentCondition);
            } 

            if (_errorLog.Count > 0)
            {
                ExceptionHelpers.ThrowMappingException(_errorLog, _normalizer.Config); 
            }
 
        } 

        // Checks equivalence of two C-side queries 
        // inExtentConstraint holds a role variable that effectively denotes that some extent is non-empty
        private bool CheckEquivalence(FragmentQuery cQuery, FragmentQuery sQuery, BoolExpression inExtentCondition,
                                      out BoolExpression unsatisfiedConstraint)
        { 
            FragmentQuery cMinusSx = _normalizer.RightFragmentQP.Difference(cQuery, sQuery);
            FragmentQuery sMinusCx = _normalizer.RightFragmentQP.Difference(sQuery, cQuery); 
 
            // add in-extent condition
            FragmentQuery cMinusS = FragmentQuery.Create(BoolExpression.CreateAnd(cMinusSx.Condition, inExtentCondition)); 
            FragmentQuery sMinusC = FragmentQuery.Create(BoolExpression.CreateAnd(sMinusCx.Condition, inExtentCondition));

            unsatisfiedConstraint = null;
            bool forwardInclusion = true; 
            bool backwardInclusion = true;
 
            if (_normalizer.RightFragmentQP.IsSatisfiable(cMinusS)) 
            {
                unsatisfiedConstraint = cMinusS.Condition; 
                forwardInclusion = false;
            }
            if (_normalizer.RightFragmentQP.IsSatisfiable(sMinusC))
            { 
                unsatisfiedConstraint = sMinusC.Condition;
                backwardInclusion = false; 
            } 
            if (forwardInclusion && backwardInclusion)
            { 
                return true;
            }
            else
            { 
                unsatisfiedConstraint.ExpensiveSimplify();
                return false; 
            } 
        }
 
        private void ReportConstraintViolation(string message, BoolExpression extraConstraint, ViewGenErrorCode errorCode, IEnumerable relevantWrappers)
        {
            if (ErrorPatternMatcher.FindMappingErrors(_normalizer, _domainMap, _errorLog))
            { 
                return;
            } 
 
            extraConstraint.ExpensiveSimplify();
            // gather all relevant cell wrappers and sort them in the original input order 
            HashSet relevantCellWrappers = new HashSet(relevantWrappers);
            List relevantWrapperList = new List(relevantCellWrappers);
            relevantWrapperList.Sort(LeftCellWrapper.OriginalCellIdComparer);
 
            StringBuilder builder = new StringBuilder();
            builder.AppendLine(message); 
            EntityConfigurationToUserString(extraConstraint, builder); 
            _errorLog.AddEntry(new ErrorLog.Record(true, errorCode, builder.ToString(), relevantCellWrappers, ""));
        } 

        // according to case statements, where WHEN ... THEN was replaced by ELSE
        private Dictionary CreateMemberValueTrees(bool complementElse)
        { 
            Dictionary memberValueTrees = new Dictionary();
 
            foreach (MemberPath column in _domainMap.ConditionMembers(_normalizer.Extent)) 
            {
                List domain = new List(_domainMap.GetDomain(column)); 

                // all domain members but the last
                OpCellTreeNode memberCover = new OpCellTreeNode(_normalizer, CellTreeOpType.Union);
                for (int i = 0; i < domain.Count; i++) 
                {
                    CellConstant domainValue = domain[i]; 
                    MemberValueBinding memberValue = new MemberValueBinding(column, domainValue); 
                    FragmentQuery memberConditionQuery = QueryRewriter.CreateMemberConditionQuery(column, domainValue, _keyAttributes, _domainMap, _normalizer.Workspace);
                    Tile rewriting; 
                    if (_normalizer.TryGetCachedRewriting(memberConditionQuery, out rewriting))
                    {
                        // turn rewriting into a cell tree
                        CellTreeNode cellTreeNode = QueryRewriter.TileToCellTree(rewriting, _normalizer); 
                        memberValueTrees[memberValue] = cellTreeNode;
                        // collect a union of all domain constants but the last 
                        if (i < domain.Count - 1) 
                        {
                            memberCover.Add(cellTreeNode); 
                        }
                    }
                    else
                    { 
                        Debug.Fail(String.Format(CultureInfo.InvariantCulture, "No cached rewriting for {0}={1}", column, domainValue));
                    } 
                } 

                if (complementElse && domain.Count > 1) 
                {
                    CellConstant lastDomainValue = domain[domain.Count - 1];
                    MemberValueBinding lastMemberValue = new MemberValueBinding(column, lastDomainValue);
                    memberValueTrees[lastMemberValue] = new OpCellTreeNode(_normalizer, CellTreeOpType.LASJ, _basicView, memberCover); 
                }
            } 
 
            return memberValueTrees;
        } 

        #endregion

        #region Checking constraints on projected condition members 

        private void CheckConstraintsOnProjectedConditionMembers(Dictionary memberValueTrees, LeftCellWrapper wrapper, CellTreeNode sQueryTree, BoolExpression inExtentCondition) 
        { 
            // for S-side condition members that are projected,
            // add condition  on both sides of the mapping constraint, and check key equivalence 
            // applies to columns that are (1) projected and (2) conditional
            foreach (MemberPath column in _domainMap.ConditionMembers(_normalizer.Extent))
            {
                // Get the slot on the C side and see if it is projected 
                int index = _normalizer.MemberMaps.ProjectedSlotMap.IndexOf(column);
                JoinTreeSlot slot = wrapper.RightCellQuery.ProjectedSlotAt(index) as JoinTreeSlot; 
                if (slot != null) 
                {
                    foreach (CellConstant domainValue in _domainMap.GetDomain(column)) 
                    {
                        CellTreeNode sQueryTreeForDomainValue;
                        if (memberValueTrees.TryGetValue(new MemberValueBinding(column, domainValue), out sQueryTreeForDomainValue))
                        { 
                            BoolExpression cWhereClause = PropagateCellConstantsToWhereClause(wrapper, wrapper.RightCellQuery.WhereClause,
                                domainValue, column, _normalizer.MemberMaps); 
                            FragmentQuery cCombinedQuery = FragmentQuery.Create(cWhereClause); 
                            CellTreeNode sCombinedTree = (sQueryTree == _basicView) ?
                               sQueryTreeForDomainValue : 
                               new OpCellTreeNode(_normalizer, CellTreeOpType.IJ, sQueryTreeForDomainValue, sQueryTree);

                            BoolExpression unsatisfiedConstraint;
                            if (!CheckEquivalence(cCombinedQuery, sCombinedTree.RightFragmentQuery, inExtentCondition, 
                                                  out unsatisfiedConstraint))
                            { 
                                string memberLossMessage = Strings.ViewGen_CQ_DomainConstraint_1(slot.ToUserString()); 
                                ReportConstraintViolation(memberLossMessage, unsatisfiedConstraint, ViewGenErrorCode.DomainConstraintViolation,
                                                          sCombinedTree.GetLeaves().Concat(new LeftCellWrapper[] { wrapper })); 
                            }
                        }
                    }
                } 
            }
        } 
 

        private static JoinTreeSlot GetCSideMappedSlotForSMember(LeftCellWrapper wrapper, MemberPath member, MemberMaps memberMaps) 
        {
            // Get the slot on the C side and see if it is projected
            int index = memberMaps.ProjectedSlotMap.IndexOf(member);
            Debug.Assert(index != -1, "Multiconstant member does not exist"); 
            CellQuery query = wrapper.RightCellQuery;
            ProjectedSlot slot = query.ProjectedSlotAt(index); 
            if (slot == null || slot is ConstantSlot) 
            {
                return null; 
            }

            // This must be a join tree slot
            JoinTreeSlot joinSlot = (JoinTreeSlot)slot; 
            return joinSlot;
        } 
 
        // effects: Given a sequence of constants that need to be propagated
        // to the C-side and the current boolean expression, generates a new 
        // expression of the form "expression AND C-side Member in constants"
        // expression" and returns it. Each constant is propagated only if member
        // is projected -- if member is not projected, returns "expression"
        internal static BoolExpression PropagateCellConstantsToWhereClause(LeftCellWrapper wrapper, BoolExpression expression, 
                                                                          CellConstant constant, MemberPath member,
                                                                          MemberMaps memberMaps) 
        { 
            JoinTreeSlot joinSlot = GetCSideMappedSlotForSMember(wrapper, member, memberMaps);
            if (joinSlot == null) 
            {
                return expression;
            }
 
            // Look at the constants and determine if they correspond to
            // typeConstants or scalarConstants 
            // This slot is being projected. We need to add a where clause element 
            Debug.Assert(constant is ScalarConstant || constant.IsNull() || constant is NegatedCellConstant, "Invalid type of constant");
 
            // We want the possible values for joinSlot.MemberPath which is a
            // C-side element -- so we use the queryDomainMap
            IEnumerable possibleValues = memberMaps.QueryDomainMap.GetDomain(joinSlot.MemberPath);
            // Note: the values in constaints can be null or not null as 
            // well (i.e., just not scalarConstants)
            Set allowedValues = new Set(CellConstant.EqualityComparer); 
            if (constant is NegatedCellConstant) 
            {
                // select all values from the c-side domain that are not in the negated set 
                allowedValues.Unite(possibleValues);
                allowedValues.Difference(((NegatedCellConstant)constant).Elements);
            }
            else 
            {
                allowedValues.Add(constant); 
            } 
            OneOfConst oneOfConst = new OneOfScalarConst(joinSlot.JoinTreeNode, allowedValues, possibleValues);
 
            BoolExpression result = BoolExpression.CreateAnd(expression, BoolExpression.CreateLiteral(oneOfConst, memberMaps.QueryDomainMap));
            return result;
        }
        #endregion 

 
        ///  
        /// Given a LeftCellWrapper for the S-side fragment and a non-nullable colum m, return a CQuery with nullability condition
        /// appended to Cquery of c-side member that column m is mapped to 
        /// 
        private static FragmentQuery AddNullConditionOnCSideFragment(LeftCellWrapper wrapper, MemberPath member, MemberMaps memberMaps)
        {
            JoinTreeSlot joinSlot = GetCSideMappedSlotForSMember(wrapper, member, memberMaps); 
            if (joinSlot == null || !joinSlot.MemberPath.IsNullable) //don't bother checking further fore non nullable C-side member
            { 
                return null; 
            }
            BoolExpression expression = wrapper.RightCellQuery.WhereClause; 

            IEnumerable possibleValues = memberMaps.QueryDomainMap.GetDomain(joinSlot.MemberPath);
            Set allowedValues = new Set(CellConstant.EqualityComparer);
            allowedValues.Add(CellConstant.Null); 

            //Create a condition as conjunction of originalCondition and slot IS NULL 
            OneOfConst oneOfConst = new OneOfScalarConst(joinSlot.JoinTreeNode, allowedValues, possibleValues); 
            BoolExpression resultingExpr = BoolExpression.CreateAnd(expression, BoolExpression.CreateLiteral(oneOfConst, memberMaps.QueryDomainMap));
 
            return  FragmentQuery.Create(resultingExpr);
        }

        ///  
        /// Checks whether non nullable S-side members are mapped to nullable C-query.
        /// It is possible that C-side attribute is nullable but the fragment's C-query is not 
        ///  
        private void CheckConstraintsOnNonNullableMembers(Dictionary memberValueTrees, LeftCellWrapper wrapper, CellTreeNode sQueryTree, BoolExpression inExtentCondition)
        { 
            //For each non-condition member that has non-nullability constraint
            foreach (MemberPath column in _domainMap.NonConditionMembers(_normalizer.Extent))
            {
                bool isColumnSimpleType = (column.EdmType as System.Data.Metadata.Edm.SimpleType)!=null; 

                if (!column.IsNullable && isColumnSimpleType) 
                { 
                    FragmentQuery cFragment = AddNullConditionOnCSideFragment(wrapper, column, _normalizer.MemberMaps);
 
                    if (cFragment!=null && _normalizer.RightFragmentQP.IsSatisfiable(cFragment))
                    {
                        _errorLog.AddEntry(new ErrorLog.Record(true, ViewGenErrorCode.NullableMappingForNonNullableColumn, Strings.Viewgen_NullableMappingForNonNullableColumn(wrapper.LeftExtent.ToString(), column.ToFullString()), wrapper.Cells, ""));
                    } 
                }
            } 
 
        }
 


        #region Methods for turning a boolean condition into user string
 
        internal static void EntityConfigurationToUserString(BoolExpression condition, StringBuilder builder)
        { 
            condition.AsUserString(builder, "PK"); 
        }
 
        // effects: Given a DNF clause, converts it into a user-readable
        // string into builder (wrapper is the wrapper from which clause came)
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode", Justification = "Keep for pretty printing user-friendly errors")]
        private static void ClauseToStringBuilder(DnfClause clause, LeftCellWrapper wrapper, 
                                                  MemberMaps memberMaps, StringBuilder builder, MetadataWorkspace workspace)
        { 
            // Get the literals 
            List positiveScalars = new List();
            List negativeScalars = new List(); 
            List positiveTypes = new List();
            List negativeTypes = new List();
            // The expression "expr" is a DNF clause -- so it must
            // be AND, NOT or a literal 

            // Get all the positive and negative literals along with the 
            // list of columns on the S-side for these literals 
            // For type constants, we assume that we should assume that
            // the values are what they should be 

            foreach (Literal literal in clause.Literals)
            {
                BoolLiteral boolLiteral = BoolExpression.GetBoolLiteral(literal.Term); 
                if (boolLiteral is RoleBoolean)
                { 
                    continue; // ignore those 
                }
                OneOfConst oneOfConst = (OneOfConst)boolLiteral; // It should not be anything else! 
                OneOfTypeConst oneOfTypeConst = oneOfConst as OneOfTypeConst;
                OneOfScalarConst oneOfScalarConst = oneOfConst as OneOfScalarConst;

                if (oneOfScalarConst != null) 
                {
                    if (literal.IsTermPositive) 
                    { 
                        positiveScalars.Add(oneOfScalarConst);
                    } 
                    else
                    {
                        negativeScalars.Add(oneOfScalarConst);
                    } 
                }
                else 
                { 
                    Debug.Assert(oneOfTypeConst != null, "One of const must be scalar or type");
                    if (literal.IsTermPositive) 
                    {
                        positiveTypes.Add(oneOfTypeConst);
                    }
                    else 
                    {
                        negativeTypes.Add(oneOfTypeConst); 
                    } 
                }
            } 

            Debug.Assert(positiveScalars.Count > 0 || negativeScalars.Count > 0 ||
                         positiveTypes.Count > 0 || negativeTypes.Count > 0, "The whole expression is empty?");
            // If positive is empty: ~A.~B must be false, i.e., ~(A+B) must be false, i.e., A+B must be true 
            // If negative is empty: A.B.C must be false, i.e., one of them must be false
 
            // If both have values: 
            // A.B.~C.~D must be false, i.e.. one of A.B.~C.~D must be false
            // i.e., A is false OR B is false or C is true or D is true 

            // For types, we print them out as they are
            if (positiveTypes.Count > 0 || negativeTypes.Count > 0)
            { 
                builder.Append(Strings.ViewGen_DomainConstraint_EntityTypes);
            } 
 
            OneOfConstToString(positiveTypes, builder, Strings.ViewGen_AND, false, workspace);
            OneOfConstToString(negativeTypes, builder, Strings.ViewGen_AND, true, workspace); 

            if (positiveTypes.Count > 0 || negativeTypes.Count > 0)
            {
                builder.AppendLine(String.Empty); 
            }
 
            // We just print: X must NOT be in (T, K) for the positive 
            // literals and "X must be in (T, K)" for the negative
            // See example above 

            OneOfConstToString(positiveScalars, builder, Strings.ViewGen_OR, true, workspace);
            OneOfConstToString(negativeScalars, builder, Strings.ViewGen_OR, false, workspace);
            builder.AppendLine(String.Empty); 
        }
 
        // effects: Adds each OneOfConst in oneOfConsts to builder as a user-presentable string 
        // connectResource is the resource string that is used to connect the oneOfConsts
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode",Justification="Keep for pretty printing user-friendly errors")] 
        private static void OneOfConstToString(IEnumerable oneOfConsts, StringBuilder builder,
                                                  string connect, bool toInvert, MetadataWorkspace workspace) where T : OneOfConst
        {
            bool isFirst = true; 
            foreach (T oneOfConst in oneOfConsts)
            { 
                if (isFirst == false) 
                {
                    builder.Append(" "); 
                    builder.Append(connect);
                }
                oneOfConst.ToUserString(toInvert, builder, workspace);
                isFirst = false; 
            }
        } 
        #endregion 

        #region WhereClauseVisitor: turns WHERE clause into CellTreeNode 
        private class WhereClauseVisitor : Visitor, CellTreeNode>
        {
            CellNormalizer _normalizer;
            CellTreeNode _topLevelTree; 
            Dictionary _memberValueTrees;
 
            internal WhereClauseVisitor(CellTreeNode topLevelTree, Dictionary memberValueTrees) 
            {
                _topLevelTree = topLevelTree; 
                _memberValueTrees = memberValueTrees;
                _normalizer = topLevelTree.CellNormalizer;
            }
 
            // returns _topLevelTree when expression evaluates to True, null if it evaluates to False
            internal CellTreeNode GetCellTreeNode(BoolExpression whereClause) 
            { 
                return whereClause.Tree.Accept(this);
            } 

            internal override CellTreeNode VisitAnd(AndExpr> expression)
            {
                IEnumerable childrenTrees = AcceptChildren(expression.Children); 
                OpCellTreeNode node = new OpCellTreeNode(_normalizer, CellTreeOpType.IJ);
                foreach (CellTreeNode childNode in childrenTrees) 
                { 
                    if (childNode == null)
                    { 
                        return null; // unsatisfiable
                    }
                    if (childNode != _topLevelTree)
                    { 
                        node.Add(childNode);
                    } 
                } 
                return node.Children.Count == 0 ? _topLevelTree : node;
            } 

            internal override CellTreeNode VisitTrue(TrueExpr> expression)
            {
                return _topLevelTree; 
            }
 
            internal override CellTreeNode VisitTerm(TermExpr> expression) 
            {
                OneOfConst oneOf = (OneOfConst)expression.Identifier.Variable.Identifier; 
                Set range = expression.Identifier.Range;

                // create a disjunction
                OpCellTreeNode disjunctionNode = new OpCellTreeNode(_normalizer, CellTreeOpType.Union); 
                CellTreeNode singleNode = null;
                foreach (CellConstant value in range) 
                { 
                    if (TryGetCellTreeNode(oneOf.Slot.MemberPath, value, out singleNode))
                    { 
                        disjunctionNode.Add(singleNode);
                    }
                    // else, there is no rewriting for this member value, i.e., it is empty
                } 
                switch (disjunctionNode.Children.Count)
                { 
                    case 0: 
                        return null; // empty rewriting
                    case 1: return singleNode; 
                    default: return disjunctionNode;
                }
            }
 
            internal override CellTreeNode VisitFalse(FalseExpr> expression)
            { 
                throw new NotImplementedException(); 
            }
            internal override CellTreeNode VisitNot(NotExpr> expression) 
            {
                throw new NotImplementedException();
            }
            internal override CellTreeNode VisitOr(OrExpr> expression) 
            {
                throw new NotImplementedException(); 
            } 

            private bool TryGetCellTreeNode(MemberPath memberPath, CellConstant value, out CellTreeNode singleNode) 
            {
                if (_memberValueTrees.TryGetValue(new MemberValueBinding(memberPath, value), out singleNode))
                {
                    return true; 
                }
                // Debug.Assert(!_normalizer.MemberMaps.LeftDomainMap.IsConditionMember(memberPath), "No domain for condition member"); 
                return false; 
            }
 
            private IEnumerable AcceptChildren(IEnumerable>> children)
            {
                foreach (BoolExpr> child in children) { yield return child.Accept(this); }
            } 

        } 
        #endregion 

        #region DomainConstraintVisitor: checks domain constraints 
        internal class DomainConstraintVisitor : CellTreeNode.SimpleCellTreeVisitor
        {
            LeftCellWrapper m_wrapper;
            CellNormalizer m_normalizer; 
            ErrorLog m_errorLog;
 
            private DomainConstraintVisitor(LeftCellWrapper wrapper, CellNormalizer normalizer, ErrorLog errorLog) 
            {
                m_wrapper = wrapper; 
                m_normalizer = normalizer;
                m_errorLog = errorLog;
            }
 
            internal static void CheckConstraints(CellTreeNode node, LeftCellWrapper wrapper,
                                                      CellNormalizer normalizer, ErrorLog errorLog) 
            { 
                DomainConstraintVisitor visitor = new DomainConstraintVisitor(wrapper, normalizer, errorLog);
                node.Accept(visitor, true); 
            }

            internal override bool VisitLeaf(LeafCellTreeNode node, bool dummy)
            { 
                // make sure all projected attributes in wrapper correspond exactly to those in node
                CellQuery thisQuery = m_wrapper.RightCellQuery; 
                CellQuery thatQuery = node.LeftCellWrapper.RightCellQuery; 
                List collidingColumns = new List();
                if (thisQuery != thatQuery) 
                {
                    for (int i = 0; i < thisQuery.NumProjectedSlots; i++)
                    {
                        JoinTreeSlot thisSlot = thisQuery.ProjectedSlotAt(i) as JoinTreeSlot; 
                        if (thisSlot != null)
                        { 
                            JoinTreeSlot thatSlot = thatQuery.ProjectedSlotAt(i) as JoinTreeSlot; 
                            if (thatSlot != null)
                            { 
                                MemberPath tableMember = m_normalizer.MemberMaps.ProjectedSlotMap[i];
                                if (!tableMember.IsPartOfKey)
                                {
                                    bool compatible; 
                                    if (thisSlot.MemberPath.Extent is EntitySet &&
                                        thatSlot.MemberPath.Extent is EntitySet) 
                                    { 
                                        // if both are entity sets, compare member paths
                                        compatible = MemberPath.EqualityComparer.Equals(thisSlot.MemberPath, thatSlot.MemberPath); 
                                    }
                                    else // else, compare members so keys of association ends are dereferenced properly
                                    {
                                        compatible = (thisSlot.MemberPath.LastMember == thatSlot.MemberPath.LastMember); 
                                    }
                                    if (!compatible) 
                                    { 
                                        collidingColumns.Add(tableMember);
                                    } 
                                }
                            }
                        }
                    } 
                }
                if (collidingColumns.Count > 0) 
                { 
                    string columnsString = MemberPath.PropertiesToUserString(collidingColumns, false);
                    string message = Strings.ViewGen_NonKeyProjectedWithOverlappingPartitions_0(columnsString); 
                    ErrorLog.Record record = new ErrorLog.Record(true, ViewGenErrorCode.NonKeyProjectedWithOverlappingPartitions, message,
                                                                 new LeftCellWrapper[] { m_wrapper, node.LeftCellWrapper }, String.Empty);
                    m_errorLog.AddEntry(record);
                } 
                return true;
            } 
 
            internal override bool VisitOpNode(OpCellTreeNode node, bool dummy)
            { 
                if (node.OpType == CellTreeOpType.LASJ)
                {
                    // add conditions only on the positive node
                    node.Children[0].Accept(this, dummy); 
                }
                else 
                { 
                    foreach (CellTreeNode child in node.Children)
                    { 
                        child.Accept(this, dummy);
                    }
                }
                return true; 
            }
        } 
        #endregion 

        #region MemberValueBinding struct: (MemberPath, CellConstant) pair 
        private struct MemberValueBinding : IEquatable
        {
            internal readonly MemberPath Member;
            internal readonly CellConstant Value; 

            public MemberValueBinding(MemberPath member, CellConstant value) 
            { 
                Member = member;
                Value = value; 
            }

            public override string ToString()
            { 
                return String.Format(CultureInfo.InvariantCulture, "{0}={1}", Member, Value);
            } 
 
            #region IEquatable Members
 
            public bool Equals(MemberValueBinding other)
            {
                return MemberPath.EqualityComparer.Equals(Member, other.Member) &&
                       CellConstant.EqualityComparer.Equals(Value, other.Value); 
            }
 
            #endregion 
        }
        #endregion 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System.Data.Mapping.ViewGeneration.Structures; 
using System.Data.Mapping.ViewGeneration.QueryRewriting;
using System.Data.Common.Utils.Boolean;
using System.Collections.Generic;
using System.Text; 
using System.Diagnostics;
using System.Data.Mapping.ViewGeneration.Utils; 
using System.Data.Metadata.Edm; 
using System.Data.Common.Utils;
using System.Linq; 
using System.Globalization;
using System.Data.Entity;

namespace System.Data.Mapping.ViewGeneration.Validation { 

    using BoolDomainConstraint = DomainConstraint; 
 
    /// 
    /// Validates each mapping fragment/cell (Qc = Qs) 
    /// by unfolding update views in Qs and checking query equivalence
    /// 
    internal class RewritingValidator {
 
        private CellNormalizer _normalizer;
        private MemberDomainMap _domainMap; 
        private CellTreeNode _basicView; 
        private IEnumerable _keyAttributes;
        private ErrorLog _errorLog; 

        internal RewritingValidator(CellNormalizer normalizer, CellTreeNode basicView)
        {
            _normalizer = normalizer; 
            _basicView = basicView;
            _domainMap = _normalizer.MemberMaps.UpdateDomainMap; 
            _keyAttributes = MemberPath.GetKeyMembers(_normalizer.Extent, _domainMap, _normalizer.Workspace); 
            _errorLog = new ErrorLog();
        } 

        #region Main logic

        internal void Validate() 
        {
            // turn rewritings into cell trees 
            // plain: according to rewritings for case statements 
            Dictionary plainMemberValueTrees = CreateMemberValueTrees(false);
            // complement: uses complement rewriting for the last WHEN ... THEN 
            // This is how the final case statement will be generated in update views
            Dictionary complementMemberValueTrees = CreateMemberValueTrees(true);

            WhereClauseVisitor plainWhereClauseVisitor = new WhereClauseVisitor(_basicView, plainMemberValueTrees); 
            WhereClauseVisitor complementWhereClauseVisitor = new WhereClauseVisitor(_basicView, complementMemberValueTrees);
 
            // produce CellTree for each SQuery 
            foreach (LeftCellWrapper wrapper in _normalizer.AllWrappersForExtent)
            { 
                Cell cell = wrapper.OnlyInputCell;
                // construct cell tree for CQuery
                CellTreeNode cQueryTree = new LeafCellTreeNode(_normalizer, wrapper);
                // sQueryTree: unfolded update view inside S-side of the cell 
                CellTreeNode sQueryTree;
                // construct cell tree for SQuery (will be used for domain constraint checking) 
                CellTreeNode complementSQueryTreeForCondition = complementWhereClauseVisitor.GetCellTreeNode(cell.SQuery.WhereClause); 
                Debug.Assert(complementSQueryTreeForCondition != null, "Rewriting for S-side query is unsatisfiable");
                if (complementSQueryTreeForCondition == null) 
                {
                    continue; // situation should never happen
                }
                if (complementSQueryTreeForCondition != _basicView) 
                {
                    // intersect with basic expression 
                    sQueryTree = new OpCellTreeNode(_normalizer, CellTreeOpType.IJ, complementSQueryTreeForCondition, _basicView); 
                }
                else 
                {
                    sQueryTree = _basicView;
                }
 
                // Append in-set or in-end condition to both queries to produce more concise errors
                // Otherwise, the errors are of the form "if there exists an entity in extent, then violation". We don't care about empty extents 
                BoolExpression inExtentCondition = BoolExpression.CreateLiteral(wrapper.CreateRoleBoolean(), _normalizer.MemberMaps.QueryDomainMap); 

                BoolExpression unsatisfiedConstraint; 
                if (!CheckEquivalence(cQueryTree.RightFragmentQuery, sQueryTree.RightFragmentQuery, inExtentCondition,
                                      out unsatisfiedConstraint))
                {
                    string extentName = StringUtil.FormatInvariant("{0}", _normalizer.Extent); 

                    // Simplify to produce more readable error messages 
                    cQueryTree.RightFragmentQuery.Condition.ExpensiveSimplify(); 
                    sQueryTree.RightFragmentQuery.Condition.ExpensiveSimplify();
 
                    String message = Strings.ViewGen_CQ_PartitionConstraint_1(extentName);

                    ReportConstraintViolation(message, unsatisfiedConstraint, ViewGenErrorCode.PartitionConstraintViolation,
                                              cQueryTree.GetLeaves().Concat(sQueryTree.GetLeaves())); 
                }
 
                CellTreeNode plainSQueryTreeForCondition = plainWhereClauseVisitor.GetCellTreeNode(cell.SQuery.WhereClause); 
                Debug.Assert(plainSQueryTreeForCondition != null, "Rewriting for S-side query is unsatisfiable");
                if (plainSQueryTreeForCondition != null) 
                {
                    // Query is non-empty. Check domain constraints on:
                    // (a) swapped members
                    DomainConstraintVisitor.CheckConstraints(plainSQueryTreeForCondition, wrapper, _normalizer, _errorLog); 
                    // (b) projected members
                    CheckConstraintsOnProjectedConditionMembers(plainMemberValueTrees, wrapper, sQueryTree, inExtentCondition); 
                } 
                CheckConstraintsOnNonNullableMembers(plainMemberValueTrees, wrapper, sQueryTree, inExtentCondition);
            } 

            if (_errorLog.Count > 0)
            {
                ExceptionHelpers.ThrowMappingException(_errorLog, _normalizer.Config); 
            }
 
        } 

        // Checks equivalence of two C-side queries 
        // inExtentConstraint holds a role variable that effectively denotes that some extent is non-empty
        private bool CheckEquivalence(FragmentQuery cQuery, FragmentQuery sQuery, BoolExpression inExtentCondition,
                                      out BoolExpression unsatisfiedConstraint)
        { 
            FragmentQuery cMinusSx = _normalizer.RightFragmentQP.Difference(cQuery, sQuery);
            FragmentQuery sMinusCx = _normalizer.RightFragmentQP.Difference(sQuery, cQuery); 
 
            // add in-extent condition
            FragmentQuery cMinusS = FragmentQuery.Create(BoolExpression.CreateAnd(cMinusSx.Condition, inExtentCondition)); 
            FragmentQuery sMinusC = FragmentQuery.Create(BoolExpression.CreateAnd(sMinusCx.Condition, inExtentCondition));

            unsatisfiedConstraint = null;
            bool forwardInclusion = true; 
            bool backwardInclusion = true;
 
            if (_normalizer.RightFragmentQP.IsSatisfiable(cMinusS)) 
            {
                unsatisfiedConstraint = cMinusS.Condition; 
                forwardInclusion = false;
            }
            if (_normalizer.RightFragmentQP.IsSatisfiable(sMinusC))
            { 
                unsatisfiedConstraint = sMinusC.Condition;
                backwardInclusion = false; 
            } 
            if (forwardInclusion && backwardInclusion)
            { 
                return true;
            }
            else
            { 
                unsatisfiedConstraint.ExpensiveSimplify();
                return false; 
            } 
        }
 
        private void ReportConstraintViolation(string message, BoolExpression extraConstraint, ViewGenErrorCode errorCode, IEnumerable relevantWrappers)
        {
            if (ErrorPatternMatcher.FindMappingErrors(_normalizer, _domainMap, _errorLog))
            { 
                return;
            } 
 
            extraConstraint.ExpensiveSimplify();
            // gather all relevant cell wrappers and sort them in the original input order 
            HashSet relevantCellWrappers = new HashSet(relevantWrappers);
            List relevantWrapperList = new List(relevantCellWrappers);
            relevantWrapperList.Sort(LeftCellWrapper.OriginalCellIdComparer);
 
            StringBuilder builder = new StringBuilder();
            builder.AppendLine(message); 
            EntityConfigurationToUserString(extraConstraint, builder); 
            _errorLog.AddEntry(new ErrorLog.Record(true, errorCode, builder.ToString(), relevantCellWrappers, ""));
        } 

        // according to case statements, where WHEN ... THEN was replaced by ELSE
        private Dictionary CreateMemberValueTrees(bool complementElse)
        { 
            Dictionary memberValueTrees = new Dictionary();
 
            foreach (MemberPath column in _domainMap.ConditionMembers(_normalizer.Extent)) 
            {
                List domain = new List(_domainMap.GetDomain(column)); 

                // all domain members but the last
                OpCellTreeNode memberCover = new OpCellTreeNode(_normalizer, CellTreeOpType.Union);
                for (int i = 0; i < domain.Count; i++) 
                {
                    CellConstant domainValue = domain[i]; 
                    MemberValueBinding memberValue = new MemberValueBinding(column, domainValue); 
                    FragmentQuery memberConditionQuery = QueryRewriter.CreateMemberConditionQuery(column, domainValue, _keyAttributes, _domainMap, _normalizer.Workspace);
                    Tile rewriting; 
                    if (_normalizer.TryGetCachedRewriting(memberConditionQuery, out rewriting))
                    {
                        // turn rewriting into a cell tree
                        CellTreeNode cellTreeNode = QueryRewriter.TileToCellTree(rewriting, _normalizer); 
                        memberValueTrees[memberValue] = cellTreeNode;
                        // collect a union of all domain constants but the last 
                        if (i < domain.Count - 1) 
                        {
                            memberCover.Add(cellTreeNode); 
                        }
                    }
                    else
                    { 
                        Debug.Fail(String.Format(CultureInfo.InvariantCulture, "No cached rewriting for {0}={1}", column, domainValue));
                    } 
                } 

                if (complementElse && domain.Count > 1) 
                {
                    CellConstant lastDomainValue = domain[domain.Count - 1];
                    MemberValueBinding lastMemberValue = new MemberValueBinding(column, lastDomainValue);
                    memberValueTrees[lastMemberValue] = new OpCellTreeNode(_normalizer, CellTreeOpType.LASJ, _basicView, memberCover); 
                }
            } 
 
            return memberValueTrees;
        } 

        #endregion

        #region Checking constraints on projected condition members 

        private void CheckConstraintsOnProjectedConditionMembers(Dictionary memberValueTrees, LeftCellWrapper wrapper, CellTreeNode sQueryTree, BoolExpression inExtentCondition) 
        { 
            // for S-side condition members that are projected,
            // add condition  on both sides of the mapping constraint, and check key equivalence 
            // applies to columns that are (1) projected and (2) conditional
            foreach (MemberPath column in _domainMap.ConditionMembers(_normalizer.Extent))
            {
                // Get the slot on the C side and see if it is projected 
                int index = _normalizer.MemberMaps.ProjectedSlotMap.IndexOf(column);
                JoinTreeSlot slot = wrapper.RightCellQuery.ProjectedSlotAt(index) as JoinTreeSlot; 
                if (slot != null) 
                {
                    foreach (CellConstant domainValue in _domainMap.GetDomain(column)) 
                    {
                        CellTreeNode sQueryTreeForDomainValue;
                        if (memberValueTrees.TryGetValue(new MemberValueBinding(column, domainValue), out sQueryTreeForDomainValue))
                        { 
                            BoolExpression cWhereClause = PropagateCellConstantsToWhereClause(wrapper, wrapper.RightCellQuery.WhereClause,
                                domainValue, column, _normalizer.MemberMaps); 
                            FragmentQuery cCombinedQuery = FragmentQuery.Create(cWhereClause); 
                            CellTreeNode sCombinedTree = (sQueryTree == _basicView) ?
                               sQueryTreeForDomainValue : 
                               new OpCellTreeNode(_normalizer, CellTreeOpType.IJ, sQueryTreeForDomainValue, sQueryTree);

                            BoolExpression unsatisfiedConstraint;
                            if (!CheckEquivalence(cCombinedQuery, sCombinedTree.RightFragmentQuery, inExtentCondition, 
                                                  out unsatisfiedConstraint))
                            { 
                                string memberLossMessage = Strings.ViewGen_CQ_DomainConstraint_1(slot.ToUserString()); 
                                ReportConstraintViolation(memberLossMessage, unsatisfiedConstraint, ViewGenErrorCode.DomainConstraintViolation,
                                                          sCombinedTree.GetLeaves().Concat(new LeftCellWrapper[] { wrapper })); 
                            }
                        }
                    }
                } 
            }
        } 
 

        private static JoinTreeSlot GetCSideMappedSlotForSMember(LeftCellWrapper wrapper, MemberPath member, MemberMaps memberMaps) 
        {
            // Get the slot on the C side and see if it is projected
            int index = memberMaps.ProjectedSlotMap.IndexOf(member);
            Debug.Assert(index != -1, "Multiconstant member does not exist"); 
            CellQuery query = wrapper.RightCellQuery;
            ProjectedSlot slot = query.ProjectedSlotAt(index); 
            if (slot == null || slot is ConstantSlot) 
            {
                return null; 
            }

            // This must be a join tree slot
            JoinTreeSlot joinSlot = (JoinTreeSlot)slot; 
            return joinSlot;
        } 
 
        // effects: Given a sequence of constants that need to be propagated
        // to the C-side and the current boolean expression, generates a new 
        // expression of the form "expression AND C-side Member in constants"
        // expression" and returns it. Each constant is propagated only if member
        // is projected -- if member is not projected, returns "expression"
        internal static BoolExpression PropagateCellConstantsToWhereClause(LeftCellWrapper wrapper, BoolExpression expression, 
                                                                          CellConstant constant, MemberPath member,
                                                                          MemberMaps memberMaps) 
        { 
            JoinTreeSlot joinSlot = GetCSideMappedSlotForSMember(wrapper, member, memberMaps);
            if (joinSlot == null) 
            {
                return expression;
            }
 
            // Look at the constants and determine if they correspond to
            // typeConstants or scalarConstants 
            // This slot is being projected. We need to add a where clause element 
            Debug.Assert(constant is ScalarConstant || constant.IsNull() || constant is NegatedCellConstant, "Invalid type of constant");
 
            // We want the possible values for joinSlot.MemberPath which is a
            // C-side element -- so we use the queryDomainMap
            IEnumerable possibleValues = memberMaps.QueryDomainMap.GetDomain(joinSlot.MemberPath);
            // Note: the values in constaints can be null or not null as 
            // well (i.e., just not scalarConstants)
            Set allowedValues = new Set(CellConstant.EqualityComparer); 
            if (constant is NegatedCellConstant) 
            {
                // select all values from the c-side domain that are not in the negated set 
                allowedValues.Unite(possibleValues);
                allowedValues.Difference(((NegatedCellConstant)constant).Elements);
            }
            else 
            {
                allowedValues.Add(constant); 
            } 
            OneOfConst oneOfConst = new OneOfScalarConst(joinSlot.JoinTreeNode, allowedValues, possibleValues);
 
            BoolExpression result = BoolExpression.CreateAnd(expression, BoolExpression.CreateLiteral(oneOfConst, memberMaps.QueryDomainMap));
            return result;
        }
        #endregion 

 
        ///  
        /// Given a LeftCellWrapper for the S-side fragment and a non-nullable colum m, return a CQuery with nullability condition
        /// appended to Cquery of c-side member that column m is mapped to 
        /// 
        private static FragmentQuery AddNullConditionOnCSideFragment(LeftCellWrapper wrapper, MemberPath member, MemberMaps memberMaps)
        {
            JoinTreeSlot joinSlot = GetCSideMappedSlotForSMember(wrapper, member, memberMaps); 
            if (joinSlot == null || !joinSlot.MemberPath.IsNullable) //don't bother checking further fore non nullable C-side member
            { 
                return null; 
            }
            BoolExpression expression = wrapper.RightCellQuery.WhereClause; 

            IEnumerable possibleValues = memberMaps.QueryDomainMap.GetDomain(joinSlot.MemberPath);
            Set allowedValues = new Set(CellConstant.EqualityComparer);
            allowedValues.Add(CellConstant.Null); 

            //Create a condition as conjunction of originalCondition and slot IS NULL 
            OneOfConst oneOfConst = new OneOfScalarConst(joinSlot.JoinTreeNode, allowedValues, possibleValues); 
            BoolExpression resultingExpr = BoolExpression.CreateAnd(expression, BoolExpression.CreateLiteral(oneOfConst, memberMaps.QueryDomainMap));
 
            return  FragmentQuery.Create(resultingExpr);
        }

        ///  
        /// Checks whether non nullable S-side members are mapped to nullable C-query.
        /// It is possible that C-side attribute is nullable but the fragment's C-query is not 
        ///  
        private void CheckConstraintsOnNonNullableMembers(Dictionary memberValueTrees, LeftCellWrapper wrapper, CellTreeNode sQueryTree, BoolExpression inExtentCondition)
        { 
            //For each non-condition member that has non-nullability constraint
            foreach (MemberPath column in _domainMap.NonConditionMembers(_normalizer.Extent))
            {
                bool isColumnSimpleType = (column.EdmType as System.Data.Metadata.Edm.SimpleType)!=null; 

                if (!column.IsNullable && isColumnSimpleType) 
                { 
                    FragmentQuery cFragment = AddNullConditionOnCSideFragment(wrapper, column, _normalizer.MemberMaps);
 
                    if (cFragment!=null && _normalizer.RightFragmentQP.IsSatisfiable(cFragment))
                    {
                        _errorLog.AddEntry(new ErrorLog.Record(true, ViewGenErrorCode.NullableMappingForNonNullableColumn, Strings.Viewgen_NullableMappingForNonNullableColumn(wrapper.LeftExtent.ToString(), column.ToFullString()), wrapper.Cells, ""));
                    } 
                }
            } 
 
        }
 


        #region Methods for turning a boolean condition into user string
 
        internal static void EntityConfigurationToUserString(BoolExpression condition, StringBuilder builder)
        { 
            condition.AsUserString(builder, "PK"); 
        }
 
        // effects: Given a DNF clause, converts it into a user-readable
        // string into builder (wrapper is the wrapper from which clause came)
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode", Justification = "Keep for pretty printing user-friendly errors")]
        private static void ClauseToStringBuilder(DnfClause clause, LeftCellWrapper wrapper, 
                                                  MemberMaps memberMaps, StringBuilder builder, MetadataWorkspace workspace)
        { 
            // Get the literals 
            List positiveScalars = new List();
            List negativeScalars = new List(); 
            List positiveTypes = new List();
            List negativeTypes = new List();
            // The expression "expr" is a DNF clause -- so it must
            // be AND, NOT or a literal 

            // Get all the positive and negative literals along with the 
            // list of columns on the S-side for these literals 
            // For type constants, we assume that we should assume that
            // the values are what they should be 

            foreach (Literal literal in clause.Literals)
            {
                BoolLiteral boolLiteral = BoolExpression.GetBoolLiteral(literal.Term); 
                if (boolLiteral is RoleBoolean)
                { 
                    continue; // ignore those 
                }
                OneOfConst oneOfConst = (OneOfConst)boolLiteral; // It should not be anything else! 
                OneOfTypeConst oneOfTypeConst = oneOfConst as OneOfTypeConst;
                OneOfScalarConst oneOfScalarConst = oneOfConst as OneOfScalarConst;

                if (oneOfScalarConst != null) 
                {
                    if (literal.IsTermPositive) 
                    { 
                        positiveScalars.Add(oneOfScalarConst);
                    } 
                    else
                    {
                        negativeScalars.Add(oneOfScalarConst);
                    } 
                }
                else 
                { 
                    Debug.Assert(oneOfTypeConst != null, "One of const must be scalar or type");
                    if (literal.IsTermPositive) 
                    {
                        positiveTypes.Add(oneOfTypeConst);
                    }
                    else 
                    {
                        negativeTypes.Add(oneOfTypeConst); 
                    } 
                }
            } 

            Debug.Assert(positiveScalars.Count > 0 || negativeScalars.Count > 0 ||
                         positiveTypes.Count > 0 || negativeTypes.Count > 0, "The whole expression is empty?");
            // If positive is empty: ~A.~B must be false, i.e., ~(A+B) must be false, i.e., A+B must be true 
            // If negative is empty: A.B.C must be false, i.e., one of them must be false
 
            // If both have values: 
            // A.B.~C.~D must be false, i.e.. one of A.B.~C.~D must be false
            // i.e., A is false OR B is false or C is true or D is true 

            // For types, we print them out as they are
            if (positiveTypes.Count > 0 || negativeTypes.Count > 0)
            { 
                builder.Append(Strings.ViewGen_DomainConstraint_EntityTypes);
            } 
 
            OneOfConstToString(positiveTypes, builder, Strings.ViewGen_AND, false, workspace);
            OneOfConstToString(negativeTypes, builder, Strings.ViewGen_AND, true, workspace); 

            if (positiveTypes.Count > 0 || negativeTypes.Count > 0)
            {
                builder.AppendLine(String.Empty); 
            }
 
            // We just print: X must NOT be in (T, K) for the positive 
            // literals and "X must be in (T, K)" for the negative
            // See example above 

            OneOfConstToString(positiveScalars, builder, Strings.ViewGen_OR, true, workspace);
            OneOfConstToString(negativeScalars, builder, Strings.ViewGen_OR, false, workspace);
            builder.AppendLine(String.Empty); 
        }
 
        // effects: Adds each OneOfConst in oneOfConsts to builder as a user-presentable string 
        // connectResource is the resource string that is used to connect the oneOfConsts
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode",Justification="Keep for pretty printing user-friendly errors")] 
        private static void OneOfConstToString(IEnumerable oneOfConsts, StringBuilder builder,
                                                  string connect, bool toInvert, MetadataWorkspace workspace) where T : OneOfConst
        {
            bool isFirst = true; 
            foreach (T oneOfConst in oneOfConsts)
            { 
                if (isFirst == false) 
                {
                    builder.Append(" "); 
                    builder.Append(connect);
                }
                oneOfConst.ToUserString(toInvert, builder, workspace);
                isFirst = false; 
            }
        } 
        #endregion 

        #region WhereClauseVisitor: turns WHERE clause into CellTreeNode 
        private class WhereClauseVisitor : Visitor, CellTreeNode>
        {
            CellNormalizer _normalizer;
            CellTreeNode _topLevelTree; 
            Dictionary _memberValueTrees;
 
            internal WhereClauseVisitor(CellTreeNode topLevelTree, Dictionary memberValueTrees) 
            {
                _topLevelTree = topLevelTree; 
                _memberValueTrees = memberValueTrees;
                _normalizer = topLevelTree.CellNormalizer;
            }
 
            // returns _topLevelTree when expression evaluates to True, null if it evaluates to False
            internal CellTreeNode GetCellTreeNode(BoolExpression whereClause) 
            { 
                return whereClause.Tree.Accept(this);
            } 

            internal override CellTreeNode VisitAnd(AndExpr> expression)
            {
                IEnumerable childrenTrees = AcceptChildren(expression.Children); 
                OpCellTreeNode node = new OpCellTreeNode(_normalizer, CellTreeOpType.IJ);
                foreach (CellTreeNode childNode in childrenTrees) 
                { 
                    if (childNode == null)
                    { 
                        return null; // unsatisfiable
                    }
                    if (childNode != _topLevelTree)
                    { 
                        node.Add(childNode);
                    } 
                } 
                return node.Children.Count == 0 ? _topLevelTree : node;
            } 

            internal override CellTreeNode VisitTrue(TrueExpr> expression)
            {
                return _topLevelTree; 
            }
 
            internal override CellTreeNode VisitTerm(TermExpr> expression) 
            {
                OneOfConst oneOf = (OneOfConst)expression.Identifier.Variable.Identifier; 
                Set range = expression.Identifier.Range;

                // create a disjunction
                OpCellTreeNode disjunctionNode = new OpCellTreeNode(_normalizer, CellTreeOpType.Union); 
                CellTreeNode singleNode = null;
                foreach (CellConstant value in range) 
                { 
                    if (TryGetCellTreeNode(oneOf.Slot.MemberPath, value, out singleNode))
                    { 
                        disjunctionNode.Add(singleNode);
                    }
                    // else, there is no rewriting for this member value, i.e., it is empty
                } 
                switch (disjunctionNode.Children.Count)
                { 
                    case 0: 
                        return null; // empty rewriting
                    case 1: return singleNode; 
                    default: return disjunctionNode;
                }
            }
 
            internal override CellTreeNode VisitFalse(FalseExpr> expression)
            { 
                throw new NotImplementedException(); 
            }
            internal override CellTreeNode VisitNot(NotExpr> expression) 
            {
                throw new NotImplementedException();
            }
            internal override CellTreeNode VisitOr(OrExpr> expression) 
            {
                throw new NotImplementedException(); 
            } 

            private bool TryGetCellTreeNode(MemberPath memberPath, CellConstant value, out CellTreeNode singleNode) 
            {
                if (_memberValueTrees.TryGetValue(new MemberValueBinding(memberPath, value), out singleNode))
                {
                    return true; 
                }
                // Debug.Assert(!_normalizer.MemberMaps.LeftDomainMap.IsConditionMember(memberPath), "No domain for condition member"); 
                return false; 
            }
 
            private IEnumerable AcceptChildren(IEnumerable>> children)
            {
                foreach (BoolExpr> child in children) { yield return child.Accept(this); }
            } 

        } 
        #endregion 

        #region DomainConstraintVisitor: checks domain constraints 
        internal class DomainConstraintVisitor : CellTreeNode.SimpleCellTreeVisitor
        {
            LeftCellWrapper m_wrapper;
            CellNormalizer m_normalizer; 
            ErrorLog m_errorLog;
 
            private DomainConstraintVisitor(LeftCellWrapper wrapper, CellNormalizer normalizer, ErrorLog errorLog) 
            {
                m_wrapper = wrapper; 
                m_normalizer = normalizer;
                m_errorLog = errorLog;
            }
 
            internal static void CheckConstraints(CellTreeNode node, LeftCellWrapper wrapper,
                                                      CellNormalizer normalizer, ErrorLog errorLog) 
            { 
                DomainConstraintVisitor visitor = new DomainConstraintVisitor(wrapper, normalizer, errorLog);
                node.Accept(visitor, true); 
            }

            internal override bool VisitLeaf(LeafCellTreeNode node, bool dummy)
            { 
                // make sure all projected attributes in wrapper correspond exactly to those in node
                CellQuery thisQuery = m_wrapper.RightCellQuery; 
                CellQuery thatQuery = node.LeftCellWrapper.RightCellQuery; 
                List collidingColumns = new List();
                if (thisQuery != thatQuery) 
                {
                    for (int i = 0; i < thisQuery.NumProjectedSlots; i++)
                    {
                        JoinTreeSlot thisSlot = thisQuery.ProjectedSlotAt(i) as JoinTreeSlot; 
                        if (thisSlot != null)
                        { 
                            JoinTreeSlot thatSlot = thatQuery.ProjectedSlotAt(i) as JoinTreeSlot; 
                            if (thatSlot != null)
                            { 
                                MemberPath tableMember = m_normalizer.MemberMaps.ProjectedSlotMap[i];
                                if (!tableMember.IsPartOfKey)
                                {
                                    bool compatible; 
                                    if (thisSlot.MemberPath.Extent is EntitySet &&
                                        thatSlot.MemberPath.Extent is EntitySet) 
                                    { 
                                        // if both are entity sets, compare member paths
                                        compatible = MemberPath.EqualityComparer.Equals(thisSlot.MemberPath, thatSlot.MemberPath); 
                                    }
                                    else // else, compare members so keys of association ends are dereferenced properly
                                    {
                                        compatible = (thisSlot.MemberPath.LastMember == thatSlot.MemberPath.LastMember); 
                                    }
                                    if (!compatible) 
                                    { 
                                        collidingColumns.Add(tableMember);
                                    } 
                                }
                            }
                        }
                    } 
                }
                if (collidingColumns.Count > 0) 
                { 
                    string columnsString = MemberPath.PropertiesToUserString(collidingColumns, false);
                    string message = Strings.ViewGen_NonKeyProjectedWithOverlappingPartitions_0(columnsString); 
                    ErrorLog.Record record = new ErrorLog.Record(true, ViewGenErrorCode.NonKeyProjectedWithOverlappingPartitions, message,
                                                                 new LeftCellWrapper[] { m_wrapper, node.LeftCellWrapper }, String.Empty);
                    m_errorLog.AddEntry(record);
                } 
                return true;
            } 
 
            internal override bool VisitOpNode(OpCellTreeNode node, bool dummy)
            { 
                if (node.OpType == CellTreeOpType.LASJ)
                {
                    // add conditions only on the positive node
                    node.Children[0].Accept(this, dummy); 
                }
                else 
                { 
                    foreach (CellTreeNode child in node.Children)
                    { 
                        child.Accept(this, dummy);
                    }
                }
                return true; 
            }
        } 
        #endregion 

        #region MemberValueBinding struct: (MemberPath, CellConstant) pair 
        private struct MemberValueBinding : IEquatable
        {
            internal readonly MemberPath Member;
            internal readonly CellConstant Value; 

            public MemberValueBinding(MemberPath member, CellConstant value) 
            { 
                Member = member;
                Value = value; 
            }

            public override string ToString()
            { 
                return String.Format(CultureInfo.InvariantCulture, "{0}={1}", Member, Value);
            } 
 
            #region IEquatable Members
 
            public bool Equals(MemberValueBinding other)
            {
                return MemberPath.EqualityComparer.Equals(Member, other.Member) &&
                       CellConstant.EqualityComparer.Equals(Value, other.Value); 
            }
 
            #endregion 
        }
        #endregion 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK