NominalTypeEliminator.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / NominalTypeEliminator.cs / 1 / NominalTypeEliminator.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections; 
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization;
using System.Linq; 
using System.Data.Common;
using md = System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees; 
using System.Data.Query.PlanCompiler;
 

namespace System.Data.Query.PlanCompiler {
    /// 
    /// The goal of this module is to eliminate all references to nominal types 
    /// in the tree. Additionally, all structured types are replaced by "flat"
    /// record types - where every field of the structured type is a scalar type. 
    /// Note that UDTs are not considered to be structured types. 
    ///
    /// At the end of this phase, 
    /// * there are no more nominal types in the tree
    /// * there are no more nested record types in the tree
    /// * No Var in the tree is of an structured type
    /// * Additionally (and these follow from the statements above) 
    ///   * There are no NewInstanceOp constructors in the tree
    ///   * There are no PropertyOp operators where the result is a structured type 
    /// 
    /// This module uses information from the PropertyPushdown phase to "optimize"
    /// structured type elimination. Essentially, if we can avoid producing pieces 
    /// of information that will be discarded later, then lets do that.
    ///
    /// The general mechanism of type elimination is as follows. We walk up the tree
    /// in a bottom up fashion, and try to convert all structured types into flattened 
    /// record types - type constructors are first converted into flat record constructors
    /// and then dismantled etc. The barrier points - Vars - are all converted into 
    /// scalar types, and all intermediate stages will be eliminated in transition. 
    ///
    /// The output from this phase includes a ColumnMap - which is used later by 
    /// the execution model to produce results in the right form from an otherwise
    /// flat query
    ///
    /// Notes: This phase could be combined later with the PropertyPushdown phase 
    ///
    ///  
    internal class NominalTypeEliminator : BasicOpVisitorOfNode { 

        #region Nested Classes 
        /// 
        /// Describes an operation kind - for various property extractions
        /// 
        internal enum OperationKind { 
            /// 
            /// Comparing two instances for equality 
            ///  
            Equality,
 
            /// 
            /// Checking to see if an instance is null
            /// 
            IsNull, 

            ///  
            /// Getting the "identity" of an entity 
            /// 
            GetIdentity, 

            /// 
            /// Getting the keys of an entity
            ///  
            GetKeys,
 
            ///  
            /// All properties of an entity
            ///  
            All
        }
        #endregion
 
        #region private state
 
        private Dictionary m_varPropertyMap; 
        private Dictionary m_nodePropertyMap;
        private VarInfoMap m_varInfoMap; 
        private PlanCompiler m_compilerState;
        private Command m_command { get { return m_compilerState.Command; } }
        private StructuredTypeInfo m_typeInfo;
        private Dictionary m_typeToNewTypeMap; 
        private const string PrefixMatchCharacter = "%"; // This is ANSI-SQL defined, but it should probably be configurable.
 
        #endregion 

        #region constructors 

        private NominalTypeEliminator(PlanCompiler compilerState,
            StructuredTypeInfo typeInfo,
            Dictionary varPropertyMap, 
            Dictionary nodePropertyMap) {
            m_compilerState = compilerState; 
            m_typeInfo = typeInfo; 
            m_varPropertyMap = varPropertyMap;
            m_nodePropertyMap = nodePropertyMap; 
            m_varInfoMap = new VarInfoMap();
            m_typeToNewTypeMap = new Dictionary(TypeUsageEqualityComparer.Instance);
        }
 
        #endregion
 
        #region Process Driver 

        ///  
        /// Eliminates all structural types from the query
        /// 
        /// current compiler state
        /// list of all referenced types 
        /// list of referenced entitysets
        internal static void Process(PlanCompiler compilerState, 
            StructuredTypeInfo structuredTypeInfo) { 
#if DEBUG
            //string phase0 = Dump.ToXml(compilerState.Command); 
            Validator.Validate(compilerState);
#endif

            // Phase 1: Top-down property pushdown 
            Dictionary varPropertyMap;
            Dictionary nodePropertyMap; 
            PropertyPushdownHelper.Process(compilerState.Command, structuredTypeInfo, out varPropertyMap, out nodePropertyMap); 

#if DEBUG 
            //string phase1 = Dump.ToXml(compilerState.Command);
            Validator.Validate(compilerState);
#endif
 
            // Phase 2: actually eliminate nominal types
            NominalTypeEliminator nte = new NominalTypeEliminator(compilerState, structuredTypeInfo, 
                varPropertyMap, nodePropertyMap); 
            nte.Process();
 
#if DEBUG
            //string phase2 = Dump.ToXml(compilerState.Command);
            Validator.Validate(compilerState);
#endif 

#if DEBUG 
            //To avoid garbage collection 
            //int size = phase0.Length;
            //size = phase1.Length; 
            //size = phase2.Length;
#endif
        }
 

        ///  
        /// The real driver. Invokes the visitor to traverse the tree bottom-up, 
        /// and modifies the tree along the way.
        ///  
        private void Process() {
            Node rootNode = m_command.Root;
            PlanCompiler.Assert(rootNode.Op.OpType == OpType.PhysicalProject, "root node is not PhysicalProjectOp?");
            // invoke the visitor on the root node 
            rootNode.Op.Accept(this, rootNode);
        } 
 
        #endregion
 
        #region type utilities

        /// 
        /// The datatype of the typeid property 
        /// 
        private md.TypeUsage DefaultTypeIdType { 
            get { return m_command.StringType; } 
        }
 
        /// 
        /// Get the "new" type corresponding to the input type.
        /// For structured types, we simply look up the typeInfoMap
        /// For collection types, we create a new collection type based on the 
        ///   "new" element type.
        /// For all other types, we simply return the input type 
        ///  
        /// 
        ///  
        private md.TypeUsage GetNewType(md.TypeUsage type) {
            md.TypeUsage newType;

            if (m_typeToNewTypeMap.TryGetValue(type, out newType)) { 
                return newType;
            } 
 
            md.CollectionType collectionType;
            if (TypeHelpers.TryGetEdmType(type, out collectionType)) { 
                // If this is a collection type, then clone a new collection type
                md.TypeUsage newElementType = GetNewType(collectionType.TypeUsage);
                newType = TypeUtils.CreateCollectionType(newElementType);
            } 
            else if (TypeUtils.IsStructuredType(type)) {
                // structured type => we've already calculated the input 
                newType = m_typeInfo.GetTypeInfo(type).FlattenedTypeUsage; 
            }
            else { 
                // "simple" type => return the input type
                newType = type;
            }
 
            // Add this information to the map
            m_typeToNewTypeMap[type] = newType; 
            return newType; 
        }
 
        #endregion

        #region misc utilities
 
        /// 
        /// This function builds a "property accessor" over the input expression.  It 
        /// can produce one of three results: 
        ///
        ///   - It can return "null", if it is convinced that the input has no 
        ///     such expression
        ///   - It can return a subnode of the input, if that subnode represents
        ///     the property
        ///   - Or, it can build a PropertyOp explicitly 
        ///
        /// Assertion: the property is not a structured type 
        ///  
        /// The input expression
        /// The desired property 
        /// 
        private Node BuildAccessor(Node input, md.EdmProperty property) {
            Op inputOp = input.Op;
 
            // Special handling if the input is a NewRecordOp
            NewRecordOp newRecordOp = inputOp as NewRecordOp; 
            if (null != newRecordOp) { 
                int fieldPos;
                // Identify the specific property we're interested in. 
                if (newRecordOp.GetFieldPosition(property, out fieldPos)) {
                    return Copy(input.Children[fieldPos]);
                }
                else { 
                    return null;
                } 
            } 

            // special handling if the input is a null 
            if (inputOp.OpType == OpType.Null) {
                return null;
            }
 
            // The default case: Simply return a new PropertyOp
            PropertyOp newPropertyOp = m_command.CreatePropertyOp(property); 
            return m_command.CreateNode(newPropertyOp, this.Copy(input)); 
        }
 
        /// 
        /// A BuildAccessor variant. If the appropriate property was not found, then
        /// build up a null constant instead
        ///  
        /// 
        ///  
        ///  
        private Node BuildAccessorWithNulls(Node input, md.EdmProperty property) {
            Node newNode = this.BuildAccessor(input, property); 
            if (newNode == null) {
                newNode = CreateNullConstantNode(md.Helper.GetModelTypeUsage(property));
            }
            return newNode; 
        }
 
        ///  
        /// Builds up an accessor to the typeid property. If the type has no typeid
        /// property, then we simply create a constantOp with the corresponding 
        /// typeid value for the type
        /// 
        /// the input expression
        /// the original type of the input expression 
        /// 
        private Node BuildTypeIdAccessor(Node input, TypeInfo typeInfo) { 
            Node result; 

            if (typeInfo.HasTypeIdProperty) { 
                result = BuildAccessorWithNulls(input, typeInfo.TypeIdProperty);
            }
            else {
                result = CreateTypeIdConstant(typeInfo); 
            }
 
            return result; 
        }
 
        /// 
        /// Builds a SoftCast operator over the input - if one is necessary.
        /// 
        /// the input expression to "cast" 
        /// the target type
        /// the "cast"ed expression 
        private Node BuildSoftCast(Node node, md.TypeUsage targetType) { 
            PlanCompiler.Assert(node.Op.IsScalarOp, "Attempting SoftCast around non-ScalarOp?");
            if (Command.EqualTypes(node.Op.Type, targetType)) { 
                return node;
            }
            // Skip any castOps we may have created already
            while (node.Op.OpType == OpType.SoftCast) { 
                node = node.Child0;
            } 
            Node newNode = m_command.CreateNode(m_command.CreateSoftCastOp(targetType), node); 
            return newNode;
        } 

        /// 
        /// Clones a subtree.
        /// This is used by the "BuildAccessor" routines to build a property-accessor 
        /// over some input. If we're reusing the input, the input must be cloned.
        ///  
        /// The subtree to copy 
        /// 
        private Node Copy(Node n) { 
            return OpCopier.Copy(m_command, n);
        }

        ///  
        /// Returns a node for a null constant of the desired type
        ///  
        ///  
        /// 
        private Node CreateNullConstantNode(md.TypeUsage type) { 
            return m_command.CreateNode(m_command.CreateNullOp(type));
        }

        ///  
        /// Create a node to represent nullability.
        ///  
        /// Node for the typeid constant 
        private Node CreateNullSentinelConstant() {
            InternalConstantOp op = m_command.CreateInternalConstantOp(m_command.IntegerType, 1); 
            return m_command.CreateNode(op);
        }

        ///  
        /// Create a node to represent the exact value of the typeid constant
        ///  
        /// The current type 
        /// Node for the typeid constant
        private Node CreateTypeIdConstant(TypeInfo typeInfo) { 
            object value = typeInfo.TypeId;
            md.TypeUsage typeIdType;
            if (typeInfo.RootType.DiscriminatorMap != null) {
                typeIdType = md.Helper.GetModelTypeUsage(typeInfo.RootType.DiscriminatorMap.DiscriminatorProperty); 
            }
            else { 
                typeIdType = DefaultTypeIdType; 
            }
            InternalConstantOp op = m_command.CreateInternalConstantOp(typeIdType, value); 
            return m_command.CreateNode(op);
        }

        ///  
        /// Create a node to represent a typeid constant for a prefix match.
        /// If the typeid value were "123X", then we would generate a constant 
        /// like "123X%" 
        /// 
        /// the current type 
        /// Node for the typeid constant
        private Node CreateTypeIdConstantForPrefixMatch(TypeInfo typeInfo) {
            string value = typeInfo.TypeId + PrefixMatchCharacter;
            InternalConstantOp op = m_command.CreateInternalConstantOp(DefaultTypeIdType, value); 
            return m_command.CreateNode(op);
        } 
 
        /// 
        /// Identify the list of property refs for comparison and isnull semantics 
        /// 
        /// 
        /// 
        ///  
        private IEnumerable GetPropertyRefsForComparisonAndIsNull(TypeInfo typeInfo, OperationKind opKind) {
            PlanCompiler.Assert(opKind == OperationKind.IsNull || opKind == OperationKind.Equality, 
                "Unexpected opKind: " + opKind + "; Can only handle IsNull and Equality"); 

            md.TypeUsage currentType = typeInfo.Type; 

            md.RowType recordType = null;
            if (TypeHelpers.TryGetEdmType(currentType, out recordType)) {
                if (opKind == OperationKind.IsNull && typeInfo.HasNullSentinelProperty) { 
                    yield return NullSentinelPropertyRef.Instance;
                } 
                else 
                foreach (md.EdmProperty m in recordType.Properties) {
                    if (!TypeUtils.IsStructuredType(md.Helper.GetModelTypeUsage(m))) { 
                        yield return new SimplePropertyRef(m);
                    }
                    else {
                        TypeInfo nestedTypeInfo = m_typeInfo.GetTypeInfo(md.Helper.GetModelTypeUsage(m)); 
                        foreach (PropertyRef p in GetPropertyRefs(nestedTypeInfo, opKind)) {
                            PropertyRef nestedPropertyRef = p.CreateNestedPropertyRef(m); 
                            yield return nestedPropertyRef; 
                        }
                    } 
                }
                yield break;
            }
 
            md.EntityType entityType = null;
            if (TypeHelpers.TryGetEdmType(currentType, out entityType)) { 
                if (opKind == OperationKind.Equality || 
                    (opKind == OperationKind.IsNull && !typeInfo.HasTypeIdProperty)) {
                    foreach (PropertyRef p in typeInfo.GetIdentityPropertyRefs()) { 
                        yield return p;
                    }
                }
                else { 
                    yield return TypeIdPropertyRef.Instance;
                } 
                yield break; 
            }
 
            md.ComplexType complexType = null;
            if (TypeHelpers.TryGetEdmType(currentType, out complexType)) {
                PlanCompiler.Assert(opKind == OperationKind.IsNull, "complex types not equality-comparable");
                PlanCompiler.Assert(typeInfo.HasTypeIdProperty, "complex type with no typeid property: can't handle isNull"); 
                yield return TypeIdPropertyRef.Instance;
                yield break; 
            } 

            md.RefType refType = null; 
            if (TypeHelpers.TryGetEdmType(currentType, out refType)) {
                foreach (PropertyRef p in typeInfo.GetAllPropertyRefs()) {
                    yield return p;
                } 
                yield break;
            } 
 
            PlanCompiler.Assert(false, "Unknown type");
        } 

        /// 
        /// Get the list of "desired" propertyrefs for the specified type and operation
        ///  
        /// 
        ///  
        ///  
        private IEnumerable GetPropertyRefs(TypeInfo typeInfo, OperationKind opKind) {
            PlanCompiler.Assert(opKind != OperationKind.All, "unexpected attempt to GetPropertyRefs(...,OperationKind.All)"); 
            if (opKind == OperationKind.GetKeys) {
                return typeInfo.GetKeyPropertyRefs();
            }
            else if (opKind == OperationKind.GetIdentity) { 
                return typeInfo.GetIdentityPropertyRefs();
            } 
            else { 
                return GetPropertyRefsForComparisonAndIsNull(typeInfo, opKind);
            } 
        }

        /// 
        /// Get a list of "desired" properties for each operationKind (specified by the opKind 
        /// parameter). The OpKinds we support are
        /// 
        ///  * GetKeys 
        ///    Applies only to entity and ref types - gets the key properties (more specifically
        ///      the flattened equivalents) 
        ///  * GetIdentity
        ///    Applies only to entity and ref types - gets the entityset id property first, and then the
        ///      the Key properties
        ///  * All 
        ///    Gets all properties of the flattened type
        /// 
        ///  * Equality 
        ///    Scalar types - the entire instance
        ///    Entity - the identity properties 
        ///    Ref - all properties (= identity properties)
        ///    Complex/Collection - Not supported
        ///    Record - recurse over each property
        /// 
        ///  * IsNull
        ///    Scalar types - entire instance 
        ///    Entity - typeid property, if it exists; otherwise, the key properties 
        ///    ComplexType - typeid property
        ///    Ref - all properties 
        ///    Collection - not supported
        ///    Record - recurse over each property
        /// 
        /// Type information for the current op 
        /// Current operation kind
        /// List of desired properties 
        private IEnumerable GetProperties(TypeInfo typeInfo, OperationKind opKind) { 
            if (opKind == OperationKind.All) {
                foreach (md.EdmProperty p in typeInfo.GetAllProperties()) { 
                    yield return p;
                }
            }
            else { 
                foreach (PropertyRef p in GetPropertyRefs(typeInfo, opKind)) {
                    yield return typeInfo.GetNewProperty(p); 
                } 
            }
        } 

        /// 
        /// Get a list of properties and value (expressions) for each desired property of the
        /// input. The list of desired properties is based on the opKind parameter. 
        /// The ignoreMissingProperties indicates if we should create a null constant, in case
        /// the input cannot produce the specified property 
        ///  
        /// typeinfo for the input
        /// Current operation kind 
        /// The input expression tree
        /// Should we ignore missing properties
        /// Output: list of properties
        /// Output: correspondng list of values 
        private void GetPropertyValues(TypeInfo typeInfo, OperationKind opKind, Node input, bool ignoreMissingProperties,
            out List properties, out List values) { 
 
            values = new List();
            properties = new List(); 
            foreach (md.EdmProperty prop in GetProperties(typeInfo, opKind)) {
                KeyValuePair kv = GetPropertyValue(input, prop, ignoreMissingProperties);
                if (kv.Value != null) {
                    properties.Add(kv.Key); 
                    values.Add(kv.Value);
                } 
            } 
        }
 
        /// 
        /// Build up a key-value pair of (property, expression) to represent
        /// the extraction of the appropriate property from the input expression
        ///  
        /// The input (structured type) expression
        /// The property in question 
        /// should we ignore missing properties 
        /// 
        private KeyValuePair GetPropertyValue(Node input, md.EdmProperty property, bool ignoreMissingProperties) { 
            Node n = null;

            if (!ignoreMissingProperties) {
                n = BuildAccessorWithNulls(input, property); 
            }
            else { 
                n = BuildAccessor(input, property); 
            }
            return new KeyValuePair(property, n); 
        }

        /// 
        /// Walk the SortKeys, and expand out 
        /// any Structured type Var references
        ///  
        /// The list of input keys 
        /// An expanded list of keys. If there is nothing to expand it returns the original list.
        private List HandleSortKeys(List keys) { 
            List newSortKeys = new List();
            bool modified = false;
            foreach (InternalTrees.SortKey k in keys) {
                VarInfo varInfo; 
                if (!m_varInfoMap.TryGetVarInfo(k.Var, out varInfo)) {
                    newSortKeys.Add(k); 
                } 
                else {
                    foreach (Var v in varInfo.NewVars) { 
                        InternalTrees.SortKey newKey = Command.CreateSortKey(v, k.AscendingSort, k.Collation);
                        newSortKeys.Add(newKey);
                    }
                    modified = true; 
                }
            } 
 
            List result = modified ? newSortKeys : keys;
            return result; 
        }
        #endregion

        #region Visitor methods 

        #region AncillaryOp Visitors 
 
        /// 
        /// VarDefListOp 
        ///
        /// Walks each VarDefOp child, and "expands" it out if the Var is a
        /// structured type.
        /// 
        /// For each Var that is expanded, a new expression is created to compute
        /// its value (from the original computed expression) 
        /// A new VarDefListOp is created to hold all the "expanded" Varlist 
        /// 
        ///  
        /// 
        /// 
        public override Node Visit(VarDefListOp op, Node n) {
            VisitChildren(n); 

            List newChildren = new List(); 
 
            foreach (Node chi in n.Children) {
                VarDefOp varDefOp = chi.Op as VarDefOp; 

                if (TypeUtils.IsStructuredType(varDefOp.Var.Type)
                 || TypeUtils.IsCollectionType(varDefOp.Var.Type)) {
                    List newChiList; 
                    md.TypeUsage x;
 
                    FlattenComputedVar((ComputedVar)varDefOp.Var, chi, out newChiList, out x); 

                    foreach (Node newChi in newChiList) { 
                        newChildren.Add(newChi);
                    }
                }
                else { 
                    newChildren.Add(chi);
                } 
            } 
            Node newVarDefListNode = m_command.CreateNode(n.Op, newChildren);
            return newVarDefListNode; 
        }

        /// 
        /// Helps flatten out a computedVar expression 
        /// 
        /// The Var 
        /// Subtree rooted at the VarDefOp expression 
        /// list of new nodes produced
        ///  
        /// VarInfo for this var
        private void FlattenComputedVar(ComputedVar v, Node node, out List newNodes, out md.TypeUsage newType) {
            newNodes = new List();
            Node definingExprNode = node.Child0; // defining expression for the VarDefOp 
            newType = null;
 
            if (TypeUtils.IsCollectionType(v.Type)) { 
                newType = GetNewType(v.Type);
                Var newVar; 
                Node newVarDefNode = m_command.CreateVarDefNode(definingExprNode, out newVar);
                newNodes.Add(newVarDefNode);
                m_varInfoMap.CreateCollectionVarInfo(v, newVar);
                return; 
            }
 
            // Get the "new" type for the Var 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(v.Type);
            // Get a list of properties that we think are necessary 
            PropertyRefList desiredProperties = m_varPropertyMap[v];
            List newVars = new List();
            List newProps = new List();
            newNodes = new List(); 
            bool alwaysCreateVar = false;
            foreach (PropertyRef p in typeInfo.PropertyRefList) { 
                // do I care for this property? 
                if (!desiredProperties.Contains(p)) {
                    continue; 
                }

                md.EdmProperty newProperty = typeInfo.GetNewProperty(p);
 
                //
                // #479467 - Make sure that we build Vars for all properties - if 
                // we are asked to produce all properties. This is extremely important 
                // for the top-level Vars
                // 
                Node propAccessor = null;
                if (desiredProperties.AllProperties) {
                    propAccessor = BuildAccessorWithNulls(definingExprNode, newProperty);
                } 
                else {
                    propAccessor = BuildAccessor(definingExprNode, newProperty); 
                    if (propAccessor == null) { 
                        continue;
                    } 
                }

                // Add the new property
                newProps.Add(newProperty); 

                // Create a new VarDefOp. If the new defining expression 
                // is just a VarRefOp, then simply reuse that Var - don't 
                // create a new computed Var
                if (!alwaysCreateVar && (propAccessor.Op.OpType == OpType.VarRef)) { 
                    newVars.Add(((VarRefOp)propAccessor.Op).Var);
                }
                else {
                    Var newVar; 
                    Node newVarDefNode = m_command.CreateVarDefNode(propAccessor, out newVar);
                    newNodes.Add(newVarDefNode); 
                    newVars.Add(newVar); 
                }
                // 
                // Once I see a collection, start creating computed Vars.
                // The result assembly code has certain assumptions about
                // reading data from the store results - specifically, that
                // I won't jump back in the result stream when I see a collection. 
                // We may want to tweak this further, but,...
                // 
                if (TypeUtils.IsCollectionType(propAccessor.Op.Type)) { 
                    alwaysCreateVar = true;
                } 
            }
            m_varInfoMap.CreateStructuredVarInfo(v, typeInfo.FlattenedType, newVars, newProps);
            return;
        } 

        #endregion 
 
        #region PhysicalOp Visitors
 
        /// 
        /// PhysicalProjectOp
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(PhysicalProjectOp op, Node n) { 
            // visit my children
            VisitChildren(n); 

            // flatten out the varset
            VarList newVarList = FlattenVarList(op.Outputs);
            // reflect changes into my column map 
            SimpleCollectionColumnMap newColumnMap = ExpandColumnMap(op.ColumnMap);
            PhysicalProjectOp newOp = m_command.CreatePhysicalProjectOp(newVarList, newColumnMap); 
            n.Op = newOp; 

            return n; 
        }

        private SimpleCollectionColumnMap ExpandColumnMap(SimpleCollectionColumnMap columnMap) {
            VarRefColumnMap varRefColumnMap = columnMap.Element as VarRefColumnMap; 
            PlanCompiler.Assert(varRefColumnMap != null, "Encountered a SimpleCollectionColumnMap element that is not VarRefColumnMap when expanding a column map in NominalTypeEliminator.");
 
            // see if this var has changed in some fashion 
            VarInfo varInfo;
            if (!m_varInfoMap.TryGetVarInfo(varRefColumnMap.Var, out varInfo)) { 
                return columnMap; // no changes
            }

            // 
            // Ensure that we get the right number of Vars - we need one Var for
            // each scalar property 
            // 
            if (TypeUtils.IsStructuredType(varRefColumnMap.Var.Type)) {
                TypeInfo typeInfo = m_typeInfo.GetTypeInfo(varRefColumnMap.Var.Type); 
                PlanCompiler.Assert(typeInfo.RootType.FlattenedType.Properties.Count == varInfo.NewVars.Count,
                    "Var count mismatch; Expected " + typeInfo.RootType.FlattenedType.Properties.Count + "; got " + varInfo.NewVars.Count + " instead.");
            }
 
            // "Process" this columnMap
            ColumnMapProcessor processor = new ColumnMapProcessor(varRefColumnMap, varInfo, m_typeInfo); 
            ColumnMap newColumnMap = processor.ExpandColumnMap(); 

            //Wrap it with a collection 
            SimpleCollectionColumnMap resultColumnMap = new SimpleCollectionColumnMap(TypeUtils.CreateCollectionType(newColumnMap.Type), newColumnMap.Name, newColumnMap, columnMap.Keys, columnMap.ForeignKeys, columnMap.SortKeys);

            return resultColumnMap;
        } 

        #endregion 
 
        #region RelOp Visitors
 
        /// 
        /// Walk the input var sequence, flatten each var, and return the new sequence of
        /// Vars
        ///  
        /// input Var sequence
        /// flattened output var sequence 
        private IEnumerable FlattenVars(IEnumerable vars) { 
            foreach (Var v in vars) {
                VarInfo varInfo; 

                if (!m_varInfoMap.TryGetVarInfo(v, out varInfo)) {
                    yield return v;
                } 
                else {
                    foreach (Var newVar in varInfo.NewVars) { 
                        yield return newVar; 
                    }
                } 
            }
        }

        ///  
        /// Probe the current VarSet for "structured" Vars - replace these with the
        /// corresponding sets of flattened Vars 
        ///  
        /// current set of vars
        /// an "expanded" varset 
        private VarVec FlattenVarSet(VarVec varSet) {
            VarVec newVarSet = m_command.CreateVarVec(FlattenVars(varSet));
            return newVarSet;
        } 

        ///  
        /// Build up a new varlist, where each structured var has been replaced by its 
        /// corresponding flattened vars
        ///  
        /// the varlist to flatten
        /// the new flattened varlist
        private VarList FlattenVarList(VarList varList) {
            VarList newVarList = Command.CreateVarList(FlattenVars(varList)); 
            return newVarList;
        } 
 
        /// 
        /// Eliminates the internal constants and nulls from the list of keys in the given GroupBy node. 
        /// These may end up in the list of keys in the var flattening process.
        /// If elimination needs to happen, it does the following transformation:
        ///
        ///     GroupBy => Project (GroupBy') 
        ///
        /// GroupBy' is the same as GroupBy only with internal constants and nulls removed 
        ///  from the list of keys and the outputs. 
        /// The project has a VarDefList that includes these internal constants and nulls.
        ///  
        /// The subtree rooted at a group by node
        /// Transformed subtree
        private Node EliminateInternalConstantAndNullGroupByKeys(Node n) {
            PlanCompiler.Assert(n != null, "Null input"); 

            GroupByOp groupByOp = n.Op as GroupByOp; 
            PlanCompiler.Assert(groupByOp != null, "The op type of the input node to EliminateInternalConstantAndNullGroupByKeys is not a GroupByOp"); 

            PlanCompiler.Assert(n.Child1 != null, "A GroupBy node with no Child1"); 

            //If no keys are defined there is nothing to do
            if (n.Child1.Children.Count == 0) {
                return n; 
            }
 
            List nodesToMove = new List(); 

            //Find all keys that are internal constants or nulls 
            foreach (Node varDefNode in n.Child1.Children) {
                PlanCompiler.Assert(varDefNode.Op.OpType == OpType.VarDef, "A child of a VarDefList is not a VarDef");
                Node definingExprNode = varDefNode.Child0;
 
                if (definingExprNode.Op.OpType == OpType.InternalConstant || definingExprNode.Op.OpType == OpType.Null) {
                    nodesToMove.Add(varDefNode); 
                } 
            }
 
            //If there are no nodes to be moved, return the original
            if (nodesToMove.Count == 0) {
                return n;
            } 

            //Create a new project op 
            Node projectNode = 
                m_command.CreateNode(
                    m_command.CreateProjectOp(groupByOp.Outputs.Clone()), 
                    n,
                    m_command.CreateNode(
                        m_command.CreateVarDefListOp(),
                        nodesToMove 
                    )
                ); 
 
            //Remove all moved nodes from the group by
            foreach (Node nodeToMove in nodesToMove) { 
                n.Child1.Children.Remove(nodeToMove);

                VarDefOp nodeToMoveOp = nodeToMove.Op as VarDefOp;
                PlanCompiler.Assert(nodeToMoveOp != null, "A child of a VarDefList is not a VarDef"); 

                groupByOp.Keys.Clear(nodeToMoveOp.Var); 
                groupByOp.Outputs.Clear(nodeToMoveOp.Var); 
            }
 
            // return the modified subtree
            return projectNode;
        }
 
        /// 
        /// Simply flatten out every var in the keys, and return a new DistinctOp 
        ///  
        /// DistinctOp
        /// Current subtree 
        /// 
        public override Node Visit(DistinctOp op, Node n) {
            VisitChildren(n);
 
            // Simply flatten out all the Vars
            VarVec newKeys = FlattenVarSet(op.Keys); 
            n.Op = m_command.CreateDistinctOp(newKeys); 
            return n;
        } 

        /// 
        /// GroupByOp
        /// 
        /// Again, VisitChildren - for the Keys and Properties VarDefList nodes - does
        /// the real work. 
        /// 
        /// The "Keys" and the "OutputVars" varsets are updated to flatten out
        /// references to any structured Vars. 
        ///
        /// NOTE: If the Keys of the GroupByOp contain references to entitytypes -
        /// those need special handling - the flattening that we describe may not be enough
        ///  
        /// 
        ///  
        /// new subtree 
        public override Node Visit(GroupByOp op, Node n) {
            VisitChildren(n); 

            // update the output Vars and the key vars with the right sets
            VarVec newKeys = FlattenVarSet(op.Keys);
            VarVec newOutputs = FlattenVarSet(op.Outputs); 

            if (newKeys != op.Keys || newOutputs != op.Outputs) { 
                n.Op = m_command.CreateGroupByOp(newKeys, newOutputs); 
            }
 
            Node newResult = EliminateInternalConstantAndNullGroupByKeys(n);
            return newResult;
        }
 
        /// 
        /// ProjectOp 
        /// 
        /// The computedVars (the VarDefList) are processed via the VisitChildren() call
        /// We then try to update the "Vars" property to flatten out any structured 
        /// type Vars - if a new VarSet is produced, then the ProjectOp is cloned
        /// 
        /// 
        ///  
        /// new subtree
        public override Node Visit(ProjectOp op, Node n) { 
            VisitChildren(n); 

            // update the output Vars with the right set of information 
            VarVec newVars = FlattenVarSet(op.Outputs);

            if (op.Outputs != newVars) {
                // If the set of vars is empty, that means we didn;t need any of the Vars 
                if (newVars.IsEmpty) {
                    return n.Child0; 
                } 
                n.Op = m_command.CreateProjectOp(newVars);
            } 
            return n;
        }

        ///  
        /// ScanTableOp
        /// 
        /// Visit a scanTable Op. Flatten out the table's record into one column 
        /// for each field. Additionally, set up the VarInfo map appropriately
        ///  
        /// 
        /// 
        /// new subtree
        public override Node Visit(ScanTableOp op, Node n) { 

            Var columnVar = op.Table.Columns[0]; 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(columnVar.Type); 
            md.RowType newRowType = typeInfo.FlattenedType;
 
            List properties = new List();
            List keyProperties = new List();
            HashSet declaredProps = new HashSet();
            foreach (md.EdmProperty p in TypeHelpers.GetAllStructuralMembers(columnVar.Type.EdmType)) { 
                declaredProps.Add(p.Name);
            } 
            foreach (md.EdmProperty p in newRowType.Properties) { 
                if (declaredProps.Contains(p.Name)) {
                    properties.Add(p); 
                }
            }
            foreach (PropertyRef pref in typeInfo.GetKeyPropertyRefs()) {
                md.EdmProperty p = typeInfo.GetNewProperty(pref); 
                keyProperties.Add(p);
            } 
 
            //
            // Create a flattened table definition, and a table with that definiton; 
            //
            TableMD newTableMD = m_command.CreateFlatTableDefinition(properties, keyProperties, op.Table.TableMetadata.Extent);
            Table newTable = m_command.CreateTableInstance(newTableMD);
 
            VarInfo varInfo = m_varInfoMap.CreateStructuredVarInfo(columnVar, newRowType, newTable.Columns, properties);
 
            n.Op = m_command.CreateScanTableOp(newTable); 
            return n;
        } 

        /// 
        /// Get the *single" var produced by the subtree rooted at this node.
        /// Returns null, if the node produces more than one var, or less than one 
        /// 
        /// the node 
        /// the single var produced by the node 
        internal static Var GetSingletonVar(Node n) {
            switch (n.Op.OpType) { 
                case OpType.Project: {
                        ProjectOp projectOp = (ProjectOp)n.Op;
                        return (projectOp.Outputs.Count == 1) ? projectOp.Outputs.First : null;
                    } 
                case OpType.ScanTable: {
                        ScanTableOp tableOp = (ScanTableOp)n.Op; 
                        return (tableOp.Table.Columns.Count == 1) ? tableOp.Table.Columns[0] : null; 
                    }
 
                case OpType.Filter:
                case OpType.SingleRow:
                case OpType.Sort:
                case OpType.ConstrainedSort: 
                    return GetSingletonVar(n.Child0);
 
                case OpType.UnionAll: 
                case OpType.Intersect:
                case OpType.Except: { 
                        SetOp setOp = (SetOp)n.Op;
                        return (setOp.Outputs.Count == 1) ? setOp.Outputs.First : null;
                    }
 
                case OpType.Unnest: {
                        UnnestOp unnestOp = (UnnestOp)n.Op; 
                        return unnestOp.Table.Columns.Count == 1 ? unnestOp.Table.Columns[0] : null; 
                    }
 
                case OpType.Distinct: {
                        DistinctOp distinctOp = (DistinctOp)n.Op;
                        return (distinctOp.Keys.Count == 1) ? distinctOp.Keys.First : null;
                    } 

                default: 
                    return null; 
            }
        } 

        /// 
        /// ScanViewOp
        /// 
        /// Flatten out the view definition, and return that after
        /// the appropriate remapping 
        ///  
        /// the ScanViewOp
        /// current subtree 
        /// the flattened view definition
        public override Node Visit(ScanViewOp op, Node n) {
            //
            // Get the "single" var produced by the input 
            //
            Var inputVar = GetSingletonVar(n.Child0); 
            PlanCompiler.Assert(inputVar != null, "cannot identify Var for the input node to the ScanViewOp"); 
            // and the table should have exactly one column
            PlanCompiler.Assert(op.Table.Columns.Count == 1, "table for scanViewOp has more than on column?"); 
            Var columnVar = op.Table.Columns[0];

            Node definingNode = VisitNode(n.Child0);
 
            VarInfo varInfo;
            if (!m_varInfoMap.TryGetVarInfo(inputVar, out varInfo)) { 
                PlanCompiler.Assert(false, "didn't find inputVar for scanViewOp?"); 
            }
            // we must be dealing with a structured column here 
            StructuredVarInfo svarInfo = (StructuredVarInfo)varInfo;

            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(columnVar.Type);
 
            // if this view does not represent an entityset, then we're pretty much
            // done. We simply add a mapping from the columnVar to the list of flattened 
            // vars produced by the underlying projectOp 
            m_varInfoMap.CreateStructuredVarInfo(columnVar, svarInfo.NewType, svarInfo.NewVars, svarInfo.Fields);
            return definingNode; 
        }

        /// 
        /// Convert a SortOp. Specifically, walk the SortKeys, and expand out 
        /// any Structured type Var references
        ///  
        /// the sortOp 
        /// the current node
        /// new subtree 
        public override Node Visit(SortOp op, Node n) {
            VisitChildren(n);

            List newSortKeys = HandleSortKeys(op.Keys); 

            if (newSortKeys != op.Keys) { 
                n.Op = m_command.CreateSortOp(newSortKeys); 
            }
            return n; 
        }

        /// 
        /// UnnestOp 
        ///
        /// Converts an UnnestOp to the right shape. 
        /// Flattens out the Table instance, and updates 
        /// 
        ///  
        /// 
        /// new subtree
        public override Node Visit(UnnestOp op, Node n) {
            // Visit the children first 
            VisitChildren(n);
 
            md.TypeUsage newType; 

            if (n.HasChild0) { 
                Node chi = n.Child0;
                VarDefOp varDefOp = chi.Op as VarDefOp;

                if (null != varDefOp) { 
                    if (TypeUtils.IsStructuredType(varDefOp.Var.Type)
                     || TypeUtils.IsCollectionType(varDefOp.Var.Type)) { 
                        List newChildren = new List(); 

                        FlattenComputedVar((ComputedVar)varDefOp.Var, chi, out newChildren, out newType); 
                        PlanCompiler.Assert(newChildren.Count == 1, "Flattening unnest var produced more than one Var");
                        n.Child0 = newChildren[0];
                    }
                } 
            }
 
            // Create a new unnestVar 
            VarInfo unnestVarInfo;
            Var newUnnestVar; 
            if (!m_varInfoMap.TryGetVarInfo(op.Var, out unnestVarInfo)) {
                throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.WrongVarType);
            }
            else if (!unnestVarInfo.IsCollectionType) { 
                throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.WrongVarType);
            } 
            else { 
                newUnnestVar = ((CollectionVarInfo)unnestVarInfo).NewVar;
            } 

            //
            // Flatten out the table
            // Create a flattened table definition, and a table with that definiton; 
            //
            Table newTable = op.Table; 
            Var columnVar = op.Table.Columns[0]; 
            if (TypeUtils.IsStructuredType(columnVar.Type)) {
                TypeInfo typeInfo = m_typeInfo.GetTypeInfo(columnVar.Type); 
                md.RowType newRowType = typeInfo.FlattenedType;
                TableMD newTableMD = m_command.CreateFlatTableDefinition(newRowType);

                newTable = m_command.CreateTableInstance(newTableMD); 
                VarInfo outputVarInfo = m_varInfoMap.CreateStructuredVarInfo(columnVar, newRowType, newTable.Columns, newRowType.Properties.ToList());
            } 
 
            // Create a new UnnestOp
            n.Op = m_command.CreateUnnestOp(newUnnestVar, newTable); 
            return n;
        }

        #region SetOps 

        ///  
        /// SetOp 
        ///
        /// Converts all SetOps - union/intersect/except. 
        /// Calls VisitChildren() to do the bulk of the work. After that, the VarMaps
        /// need to be updated to reflect the removal of any structured Vars
        /// 
        ///  
        /// 
        /// new subtree 
        protected override Node VisitSetOp(SetOp op, Node n) { 
            VisitChildren(n);
 
            // Now walk through the first VarMap, and identify the Vars that are needed
            for (int i = 0; i < op.VarMap.Length; i++) {
                List newComputedVars;
                op.VarMap[i] = FlattenVarMap(op.VarMap[i], out newComputedVars); 
                if (newComputedVars != null) {
                    n.Children[i] = FixupSetOpChild(n.Children[i], op.VarMap[i], newComputedVars); 
                } 
            }
 
            // now get the set of Vars that we will actually need
            op.Outputs.Clear();
            foreach (Var v in op.VarMap[0].Keys) {
                op.Outputs.Set(v); 
            }
            return n; 
        } 

        ///  
        /// Fixes up a SetOp child.
        /// As part of Var flattening, it may so happen that the outer var in the VarMap
        /// may require a property that has no corresponding analog in the inner Var
        /// This logically implies that the corresponding inner property is null. H 
        /// What we do here is to throw an additional projectOp over the setOp child to
        /// add computed Vars (whose defining expressions are null constants) for each 
        /// of those missing properties 
        /// 
        /// one child of the setop 
        /// the varmap for this child
        /// list of new Vars produced
        /// new node for the setOpchild (if any)
        private Node FixupSetOpChild(Node setOpChild, VarMap varMap, List newComputedVars) { 
            PlanCompiler.Assert(null != setOpChild, "null setOpChild?");
            PlanCompiler.Assert(null != varMap, "null varMap?"); 
            PlanCompiler.Assert(null != newComputedVars, "null newComputedVars?"); 

            // Walk through the list of Vars that have no inner analog, and create 
            // a computed Var for each of them
            VarVec newVarSet = m_command.CreateVarVec();
            foreach (KeyValuePair kv in varMap) {
                newVarSet.Set(kv.Value); 
            }
 
            List varDefOpNodes = new List(); 
            foreach (Var v in newComputedVars) {
                VarDefOp varDefOp = m_command.CreateVarDefOp(v); 
                Node varDefOpNode = m_command.CreateNode(varDefOp, CreateNullConstantNode(v.Type));
                varDefOpNodes.Add(varDefOpNode);
            }
            Node varDefListNode = m_command.CreateNode(m_command.CreateVarDefListOp(), varDefOpNodes); 
            ProjectOp projectOp = m_command.CreateProjectOp(newVarSet);
            Node projectNode = m_command.CreateNode(projectOp, setOpChild, varDefListNode); 
            return projectNode; 
        }
 
        /// 
        /// Flattens out a VarMap.
        ///
        /// Any structured type Vars are expanded out; and collection type Vars 
        /// are replaced by new Vars that reflect the new collection types.
        /// 
        /// There is one special case when dealing with Structured type Vars - 
        /// the output and input vars may no longer be 1-1; specifically, there
        /// may be no input Var corresponding to an output var. In such cases, we 
        /// build up a new ComputedVar (with an expected value of null), and use that
        /// in place of the inner var. A subsequent stage will inspect the list of
        /// new ComputedVars, and perform the appropriate fixups
        ///  
        /// The VarMap to fixup
        /// list of any new computedVars that are created 
        /// a new VarMap 
        private VarMap FlattenVarMap(VarMap varMap, out List newComputedVars) {
            newComputedVars = null; 

            VarMap newVarMap = new VarMap();
            foreach (KeyValuePair kv in varMap) {
                VarInfo innerVarInfo; 
                VarInfo outerVarInfo;
                // Does the inner var have a Varinfo - if not, simply add it 
                // to the VarMap, and continue. 
                // Otherwise, the Outer var must have a VarInfo too
                if (!m_varInfoMap.TryGetVarInfo(kv.Value, out innerVarInfo)) { 
                    newVarMap.Add(kv.Key, kv.Value);
                }
                else {
                    // get my own var info 
                    if (!m_varInfoMap.TryGetVarInfo(kv.Key, out outerVarInfo)) {
                        outerVarInfo = FlattenSetOpVar((SetOpVar)kv.Key); 
                    } 

                    // If this Var represents a collection type, then simply 
                    // replace the singleton Var
                    if (outerVarInfo.IsCollectionType) {
                        newVarMap.Add(((CollectionVarInfo)outerVarInfo).NewVar, ((CollectionVarInfo)innerVarInfo).NewVar);
                    } 
                    else { // structured type
                        StructuredVarInfo outerSvarInfo = (StructuredVarInfo)outerVarInfo; 
                        StructuredVarInfo innerSvarInfo = (StructuredVarInfo)innerVarInfo; 

                        // walk through each property, and find the innerVar corresponding 
                        // to that property
                        foreach (md.EdmProperty prop in outerSvarInfo.Fields) {
                            Var outerVar;
                            Var innerVar; 
                            bool ret = outerSvarInfo.TryGetVar(prop, out outerVar);
                            PlanCompiler.Assert(ret, "Could not find VarInfo for prop " + prop.Name); 
 
                            if (!innerSvarInfo.TryGetVar(prop, out innerVar)) {
                                // we didn't find a corresponding innerVar. 
                                innerVar = m_command.CreateComputedVar(outerVar.Type);
                                if (newComputedVars == null) {
                                    newComputedVars = new List();
                                } 
                                newComputedVars.Add((ComputedVar)innerVar);
                            } 
                            newVarMap.Add(outerVar, innerVar); 
                        }
                    } 
                }
            }
            return newVarMap;
        } 

        ///  
        /// Flattens a SetOpVar (used in SetOps). Simply produces a list of 
        /// properties corresponding to each desired property
        ///  
        /// 
        /// 
        private VarInfo FlattenSetOpVar(SetOpVar v) {
            if (TypeUtils.IsCollectionType(v.Type)) { 
                md.TypeUsage newType = GetNewType(v.Type);
                Var newVar = m_command.CreateSetOpVar(newType); 
                return m_varInfoMap.CreateCollectionVarInfo(v, newVar); 
            }
 
            // Get the "new" type for the Var
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(v.Type);
            // Get a list of properties that we think are necessary
            PropertyRefList desiredProperties = m_varPropertyMap[v]; 
            List newVars = new List();
            List newProps = new List(); 
            foreach (PropertyRef p in typeInfo.PropertyRefList) { 
                if (!desiredProperties.Contains(p)) {
                    continue; 
                }
                md.EdmProperty newProperty = typeInfo.GetNewProperty(p);
                newProps.Add(newProperty);
                SetOpVar newVar = m_command.CreateSetOpVar(md.Helper.GetModelTypeUsage(newProperty)); 
                newVars.Add(newVar);
            } 
            VarInfo varInfo = m_varInfoMap.CreateStructuredVarInfo(v, typeInfo.FlattenedType, newVars, newProps); 
            return varInfo;
        } 

        #endregion

        #region DML RelOps 

        // 
        // DML RelOps are technically very simple - we should simply visit the 
        // children. However, I will defer this to when we actually support DML
        // so for now, the default implementation in the basicVisitor is to throw 
        // unimplemented and that's good enough.
        //

        #endregion 

        #endregion 
 
        #region ScalarOp Visitors
 
        /// 
        /// SoftCastOp
        ///
        /// Visit the children first. 
        ///
        /// If this is an entity type, complextype or ref type, simply return the 
        ///   visited child. (Rationale: These must be in the same type hierarchy; or 
        ///   the earlier stages of query would have barfed. And, we end up
        ///   using the same "flat" type for every type in the hierarchy) 
        ///
        /// If this is a scalar type, then simply return the current node
        ///
        /// If this is a collection type, then create a new softcastOp over the input 
        ///  (the collection type may have changed)
        /// 
        /// Otherwise, we're dealing with a record type. Since our earlier 
        /// definitions of equivalence required that equivalent record types must
        /// have the same number of fields, with "promotable" types, and in the same 
        /// order; *and* since we asked for all properties (see PropertyPushdownHelper),
        /// the input must be a NewRecordOp, whose fields line up 1-1 with our fields.
        /// Build up a new NewRecordOp based on the arguments to the input NewRecordOp,
        /// and build up SoftCastOps for any field whose type does not match 
        /// 
        ///  
        ///  
        /// 
        public override Node Visit(SoftCastOp op, Node n) { 
            md.TypeUsage inputTypeUsage = n.Child0.Op.Type;
            md.TypeUsage oldType = op.Type;

            // Always think of your children first 
            VisitChildren(n);
 
            md.TypeUsage newType = GetNewType(oldType); 

            if (md.TypeSemantics.IsRowType(oldType)) { 
                PlanCompiler.Assert(n.Child0.Op.OpType == OpType.NewRecord, "Expected a record constructor here. Found " + n.Child0.Op.OpType + " instead");

                TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(inputTypeUsage);
                TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(op.Type); 

                NewRecordOp newOp = m_command.CreateNewRecordOp(newType); 
 
                List newArgs = new List();
 
                // We have to adjust for when we're supposed to add/remove null sentinels;
                // it is entirely possible that we may need to add multiple null sentinel
                // columns (See SQLBUDT #549068 for an example).
                IEnumerator outputs = newOp.Properties.GetEnumerator(); 
                int outputPropertyCount = newOp.Properties.Count;
                outputs.MoveNext(); 
 
                IEnumerator inputs = n.Child0.Children.GetEnumerator();
                int inputPropertyCount = n.Child0.Children.Count; 
                inputs.MoveNext();

                // We know that all Null Sentinels are added on the left side, so we'll
                // just keep adding them until we have the same number of properties on 
                // both the input and the output...
                while (inputPropertyCount < outputPropertyCount) { 
                    PlanCompiler.Assert(outputTypeInfo.HasNullSentinelProperty && !inputTypeInfo.HasNullSentinelProperty, "NullSentinelProperty mismatch on input?"); 

                    // make up a null sentinel; the output requires it. 
                    newArgs.Add(CreateNullSentinelConstant());
                    outputs.MoveNext();
                    outputPropertyCount--;
                } 

                // Likewise, we'll just drop any null sentinel columns from the input until 
                // we have the same number of columns... 
                while (inputPropertyCount > outputPropertyCount) {
                    PlanCompiler.Assert(!outputTypeInfo.HasNullSentinelProperty && inputTypeInfo.HasNullSentinelProperty, "NullSentinelProperty mismatch on output?"); 

                    // remove the null sentinel; the output doesn't require it.
                    inputs.MoveNext();
                    inputPropertyCount--; 
                }
 
                do { 
                    md.EdmProperty p = outputs.Current;
                    Node arg = BuildSoftCast(inputs.Current, md.Helper.GetModelTypeUsage(p)); 
                    newArgs.Add(arg);
                    outputs.MoveNext();
                }
                while (inputs.MoveNext()); 

                Node newNode = m_command.CreateNode(newOp, newArgs); 
                return newNode; 
            }
            else if (md.TypeSemantics.IsCollectionType(oldType)) { 
                //
                // Our collection type may have changed - 'coz the
                // element type of the collection may have changed.
                // Simply build up a new castOp (if necessary) 
                //
                return BuildSoftCast(n.Child0, newType); 
            } 
            else if (md.TypeSemantics.IsPrimitiveType(oldType)) {
                // How primitive! Well, the Prime Directive prohibits me 
                // from doing much with these.
                return n;
            }
            else { 
                PlanCompiler.Assert(md.TypeSemantics.IsNominalType(oldType) ||
                    md.TypeSemantics.IsReferenceType(oldType), 
                    "Gasp! Not a nominal type or even a reference type"); 
                // I'm dealing with a nominal type (entity, complex type) or
                // a reference type here. Every type in the same hierarchy 
                // must have been rationalized into the same type, and so, we
                // won't need to do anything special
                PlanCompiler.Assert(Command.EqualTypes(newType, n.Child0.Op.Type),
                    "Types are not equal"); 
                return n.Child0;
            } 
        } 

        ///  
        /// CaseOp
        ///
        /// Special handling
        /// 
        /// If the case statement is of one of the following two shapes:
        ///     (1) case when X then NULL else Y, or 
        ///     (2) case when X then Y else NULL, 
        /// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same,
        /// it gets rewritten into:  Y', where Y's null sentinel N' is: 
        ///     (1) case when X then NULL else N, or
        /// where N is Y's null sentinel.
        /// 
        /// the CaseOp 
        /// corresponding node
        /// new subtree 
        public override Node Visit(CaseOp op, Node n) { 
            // Before visiting the children, check whether the case statment can be optimized
            bool thenClauseIsNull; 
            bool canSimplifyPrecheck = PlanCompilerUtil.IsRowTypeCaseOpWithNullability(op, n, out thenClauseIsNull);

            VisitChildren(n);
 
            if (canSimplifyPrecheck)  {
                Node rewrittenNode; 
                if (TryRewriteCaseOp(n, thenClauseIsNull, out rewrittenNode)) { 
                    return rewrittenNode;
                } 
            }

            //
            // If the CaseOp returns a simple type, then we don't need to do 
            // anything special.
            // 
            // Bug 480780: We must perform further processing, if the result 
            // type is not a scalar
            // 

            // If the CaseOp returns a collection, then we need to create a
            // new CaseOp of the new and improved collection type.
            if (TypeUtils.IsCollectionType(op.Type)) { 
                md.TypeUsage newType = GetNewType(op.Type);
 
                n.Op = m_command.CreateCaseOp(newType); 
                return n;
            } 
            else if (TypeUtils.IsStructuredType(op.Type)) {
                // We've got a structured type, so the CaseOp is flattened out into
                // a NewRecordOp via the FlattenCaseOp method.
                PropertyRefList desiredProperties = m_nodePropertyMap[n]; 
                Node newNode = FlattenCaseOp(op, n, m_typeInfo.GetTypeInfo(op.Type), desiredProperties);
                return newNode; 
            } 
            else {
                return n; 
            }
        }

        ///  
        /// Given a case statement of one of the following two shapes:
        ///     (1) case when X then NULL else Y, or 
        ///     (2) case when X then Y else NULL, 
        /// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same,
        /// it rewrittes into:  Y', where Y's null sentinel N' is: 
        ///     (1) case when X then NULL else N, or
        /// where N is Y's null sentinel.
        ///
        /// The rewrite only happens if: 
        ///     (1) Y has null sentinel, and
        ///     (2) Y is a NewRecordOp. 
        ///  
        /// 
        ///  
        /// 
        /// Whether a rewrite was done
        private bool TryRewriteCaseOp(Node n, bool thenClauseIsNull, out Node rewrittenNode) {
            rewrittenNode = n; 

            //If the type of the case op does not have a null sentinel, we can't do the rewrite. 
            if (!m_typeInfo.GetTypeInfo(n.Op.Type).HasNullSentinelProperty) { 
                return false;
            } 

            Node resultNode = thenClauseIsNull ? n.Child2 : n.Child1;
            if (resultNode.Op.OpType != OpType.NewRecord) {
                return false; 
            }
 
            //Rewrite the null sentinel, which is the first child of the resultNode 
            Node currentNullSentinel = resultNode.Child0;
            md.TypeUsage integerType = this.m_command.IntegerType; 
            PlanCompiler.Assert(currentNullSentinel.Op.Type.EdmEquals(integerType), "Column that is expected to be a null sentinel is not of Integer type.");

            CaseOp newCaseOp = m_command.CreateCaseOp(integerType);
            List children = new List(3); 

            //The the 'when' from the case statement 
            children.Add(n.Child0); 

            Node nullSentinelNullNode = m_command.CreateNode(m_command.CreateNullOp(integerType)); 
            Node nullSentinelThenNode = thenClauseIsNull ? nullSentinelNullNode : currentNullSentinel;
            Node nullSentinelElseNode = thenClauseIsNull ? currentNullSentinel : nullSentinelNullNode;
            children.Add(nullSentinelThenNode);
            children.Add(nullSentinelElseNode); 

            //Use the case op as a new null sentinel 
            resultNode.Child0 = m_command.CreateNode(newCaseOp, children); 

            rewrittenNode = resultNode; 
            return true;
        }

        ///  
        /// Flattens a CaseOp - Specifically, if the CaseOp returns a structuredtype,
        /// then the CaseOp is broken up so that we build up a "flat" record constructor 
        /// for that structured type, with each argument to the record constructor being 
        /// a (scalar) CaseOp.  For example:
        /// 
        ///     Case when b1 then e1 else e2 end
        ///
        /// gets translated into:
        /// 
        ///     RecordOp(case when b1 then e1.a else e2.a end,
        ///              case when b1 then e1.b else e2.b end, 
        ///              ...) 
        ///
        /// The property extraction is optimized by producing only those properties 
        /// that have actually been requested.
        /// 
        /// the CaseOp
        /// Node corresponding to the CaseOp 
        /// Information about the type
        /// Set of properties desired 
        ///  
        private Node FlattenCaseOp(CaseOp op, Node n, TypeInfo typeInfo, PropertyRefList desiredProperties) {
            // Build up a type constructor - with only as many fields filled in 
            // as are desired.
            List fieldTypes = new List();
            List fieldValues = new List();
 
            foreach (PropertyRef pref in typeInfo.PropertyRefList) {
                // Is this property desired later? 
                if (!desiredProperties.Contains(pref)) { 
                    continue;
                } 
                md.EdmProperty property = typeInfo.GetNewProperty(pref);

                // Build up an accessor for this property across each when/then clause
                List caseChildren = new List(); 
                for (int i = 0; i < n.Children.Count - 1; ) {
                    Node whenNode = Copy(n.Children[i]); 
                    caseChildren.Add(whenNode); 
                    i++;
 
                    Node propNode = BuildAccessorWithNulls(n.Children[i], property);
                    caseChildren.Add(propNode);
                    i++;
                } 
                Node elseNode = BuildAccessorWithNulls(n.Children[n.Children.Count - 1], property);
                caseChildren.Add(elseNode); 
 
                Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(md.Helper.GetModelTypeUsage(property)), caseChildren);
 
                fieldTypes.Add(property);
                fieldValues.Add(caseNode);
            }
 
            NewRecordOp newRec = m_command.CreateNewRecordOp(typeInfo.FlattenedTypeUsage, fieldTypes);
            return m_command.CreateNode(newRec, fieldValues); 
        } 

        ///  
        /// CollectOp
        ///
        /// Nothing much to do - simply update the result type
        ///  
        /// the NestOp
        /// corresponding node 
        /// new subtree 
        public override Node Visit(CollectOp op, Node n) {
            VisitChildren(n); 
            // simply update the desired type
            n.Op = m_command.CreateCollectOp(GetNewType(op.Type));
            return n;
        } 

        ///  
        /// ComparisonOp 
        ///
        /// If the inputs to the comparisonOp are Refs/records/entitytypes, then 
        /// we need to flatten these out. Of course, the only reasonable comparisons
        /// should be EQ and NE
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(ComparisonOp op, Node n) { 
            md.TypeUsage child0Type = ((ScalarOp)n.Child0.Op).Type;
            md.TypeUsage child1Type = ((ScalarOp)n.Child1.Op).Type; 

            if (!TypeUtils.IsStructuredType(child0Type)) {
                return VisitScalarOpDefault(op, n);
            } 

            VisitChildren(n); // visit the children first 
 
            // We're now dealing with a structured type
            PlanCompiler.Assert(!(md.TypeSemantics.IsComplexType(child0Type) || md.TypeSemantics.IsComplexType(child1Type)), "complex type?"); // cannot be a complex type 
            PlanCompiler.Assert(op.OpType == OpType.EQ || op.OpType == OpType.NE, "non-equality comparison of structured types?");

            //
            // Strictly speaking, we should be able to use the typeinfo of either of the arguments. 
            // However, as things stand today, we do have scenarios where the types on the
            // two sides (records mainly) are equivalent, but not identical. This non-identicality 
            // may involve the field types being different, the field names being different etc. - but 
            // we may be assured that the order of the field types is fixed.
            // 
            TypeInfo child0TypeInfo = m_typeInfo.GetTypeInfo(child0Type);
            TypeInfo child1TypeInfo = m_typeInfo.GetTypeInfo(child1Type);
            List properties1;
            List properties2; 
            List values1;
            List values2; 
 
            // get a list of the relevant properties and values from each of the children
 
            GetPropertyValues(child0TypeInfo, OperationKind.Equality, n.Child0, false, out properties1, out values1);
            GetPropertyValues(child1TypeInfo, OperationKind.Equality, n.Child1, false, out properties2, out values2);

            PlanCompiler.Assert((properties1.Count == properties2.Count) && (values1.Count == values2.Count), "different shaped structured types?"); 

            // Build up an and-chain of comparison ops on the property values 
            Node andNode = null; 
            for (int i = 0; i < values1.Count; i++) {
                ComparisonOp newCompOp = m_command.CreateComparisonOp(op.OpType); 
                Node newCompNode = m_command.CreateNode(newCompOp, values1[i], values2[i]);
                if (null == andNode)
                    andNode = newCompNode;
                else 
                    andNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And), andNode, newCompNode);
            } 
            return andNode; 
        }
 
        /// 
        /// ConditionalOp
        ///
        /// IsNull requires special handling. 
        /// 
        ///  
        ///  
        /// 
        public override Node Visit(ConditionalOp op, Node n) { 
            if (op.OpType != OpType.IsNull) {
                return VisitScalarOpDefault(op, n);
            }
 
            //
            // Special handling for IS NULL ops on structured types 
            // 
            // For structured types, we simply convert this into an AND chain of
            // IS NULL predicates, one for each property. There are a couple of 
            // optimizations that we perform.
            //
            // For entity types, we simply perfom the IS NULL operations on the
            // key attributes alone. 
            //
            // Complex types must have a typeid property - the isnull is pushed to the 
            // typeid property 
            //
            // We do NOT support IsNull for Collections 
            //

            md.TypeUsage childOpType = ((ScalarOp)n.Child0.Op).Type;
 
            // Special cases are for structured types only
            if (!TypeUtils.IsStructuredType(childOpType)) { 
                return VisitScalarOpDefault(op, n); 
            }
 
            // visit the children first
            VisitChildren(n);

            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(childOpType); 

            // Otherwise, build up an and-chain of is null checks for each appropriate 
            // property - which should consist only of key properties for Entity types. 
            List properties = null;
            List values = null; 
            GetPropertyValues(typeInfo, OperationKind.IsNull, n.Child0, false, out properties, out values);

            PlanCompiler.Assert(properties.Count == values.Count && properties.Count > 0, "No properties returned from GetPropertyValues(IsNull)?");
 
            Node andNode = null;
            foreach (Node propertyValue in values) { 
                Node isNullNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.IsNull), propertyValue); 
                if (andNode == null)
                    andNode = isNullNode; 
                else
                    andNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And), andNode, isNullNode);
            }
            return andNode; 
        }
 
        ///  
        /// Convert a ConstrainedSortOp. Specifically, walk the SortKeys, and expand out
        /// any Structured type Var references 
        /// 
        /// the constrainedSortOp
        /// the current node
        /// new subtree 
        public override Node Visit(ConstrainedSortOp op, Node n) {
            VisitChildren(n); 
 
            List newSortKeys = HandleSortKeys(op.Keys);
 
            if (newSortKeys != op.Keys) {
                n.Op = m_command.CreateConstrainedSortOp(newSortKeys, op.WithTies);
            }
            return n; 
        }
 
        ///  
        /// GetEntityKeyOp
        ///  
        /// 
        /// 
        /// 
        public override Node Visit(GetEntityRefOp op, Node n) { 
            return FlattenGetKeyOp(op, n);
        } 
 
        /// 
        /// GetRefKeyOp 
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(GetRefKeyOp op, Node n) {
            return FlattenGetKeyOp(op, n); 
        } 

        ///  
        /// GetEntityKeyOp/GetRefKeyOp common handling
        ///
        /// In either case, get the "key" properties from the input entity/ref, and
        /// build up a record constructor from these values 
        /// 
        /// the GetRefKey/GetEntityKey op 
        /// current subtree 
        /// new expression subtree
        private Node FlattenGetKeyOp(ScalarOp op, Node n) { 
            PlanCompiler.Assert(op.OpType == OpType.GetEntityRef || op.OpType == OpType.GetRefKey, "Expecting GetEntityRef or GetRefKey ops");

            TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(((ScalarOp)n.Child0.Op).Type);
            TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(op.Type); 

            // Visit the child - will flatten out the input ref/entity 
            VisitChildren(n); 

            // Get "key" properties (and the corresponding values) from the input 
            List inputFieldTypes;
            List inputFieldValues;

            // Get the key properties for GetRefKey; get the Identity properties 
            // for GetEntityRef
            if (op.OpType == OpType.GetRefKey) { 
                GetPropertyValues(inputTypeInfo, OperationKind.GetKeys, n.Child0, false /* ignore missing props */, out inputFieldTypes, out inputFieldValues); 
            }
            else { 
                PlanCompiler.Assert(op.OpType == OpType.GetEntityRef,
                    "Expected OpType.GetEntityRef: Found " + op.OpType);
                GetPropertyValues(inputTypeInfo, OperationKind.GetIdentity, n.Child0, false, out inputFieldTypes, out inputFieldValues);
            } 

            if (outputTypeInfo.HasNullSentinelProperty && !inputTypeInfo.HasNullSentinelProperty) { 
                // Add a null sentinel column, the input doesn't have one but the output requires it. 
                inputFieldValues.Insert(0,CreateNullSentinelConstant());
            } 

            // create an appropriate record constructor
            List outputFieldTypes = new List(outputTypeInfo.FlattenedType.Properties);
            PlanCompiler.Assert(inputFieldValues.Count == outputFieldTypes.Count, "fieldTypes.Count mismatch?"); 

            NewRecordOp rec = m_command.CreateNewRecordOp(outputTypeInfo.FlattenedTypeUsage, outputFieldTypes); 
            Node newNode = m_command.CreateNode(rec, inputFieldValues); 
            return newNode;
        } 

        /// 
        /// NewMultisetOp
        /// 
        /// For now, all it does is to visit its children
        /// and update the collection type 
        ///  
        /// the NewMultisetOp
        /// corresponding node 
        /// new subtree
        public override Node Visit(NewMultisetOp op, Node n) {
            // Visit my children first
            VisitChildren(n); 
            // then simply, update my type.
            n.Op = m_command.CreateNewMultisetOp(GetNewType(op.Type)); 
            return n; 
        }
 
        /// 
        /// Common handler for PropertyOp and RelPropertyOp
        /// 
        ///  
        /// 
        ///  
        ///  
        private Node VisitPropertyOp(Op op, Node n, PropertyRef propertyRef) {
            PlanCompiler.Assert(op.OpType == OpType.Property || op.OpType == OpType.RelProperty, 
                "Unexpected optype: " + op.OpType);

            md.TypeUsage inputType = n.Child0.Op.Type;
            md.TypeUsage outputType = op.Type; 

            // First visit all my children 
            VisitChildren(n); 

            // If the instance is not a structured type (ie) it is a udt, then there 
            // is little for us to do. Simply return
            if (TypeUtils.IsUdt(inputType)) {
                return n;
            } 

            Node newNode = null; 
            TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(inputType); 

            if (TypeUtils.IsStructuredType(outputType)) { 
                TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(outputType);
                List fieldTypes = new List();
                List fieldValues = new List();
                PropertyRefList expectedProperties = m_nodePropertyMap[n]; 

                foreach (PropertyRef npr in outputTypeInfo.PropertyRefList) { 
                    // Is this a property that's desired by my consumers? 
                    if (expectedProperties.Contains(npr)) {
                        PropertyRef newPropRef = npr.CreateNestedPropertyRef(propertyRef); 
                        md.EdmProperty outputNestedProp = outputTypeInfo.GetNewProperty(npr);
                        md.EdmProperty newNestedProp = inputTypeInfo.GetNewProperty(newPropRef);

                        Node field = BuildAccessor(n.Child0, newNestedProp); 
                        if (null != field) {
                            fieldTypes.Add(outputNestedProp); 
                            fieldValues.Add(field); 
                        }
                    } 
                }
                Op newRecordOp = m_command.CreateNewRecordOp(outputTypeInfo.FlattenedTypeUsage, fieldTypes);
                newNode = m_command.CreateNode(newRecordOp, fieldValues);
            } 
            else {
                md.EdmProperty newProp = inputTypeInfo.GetNewProperty(propertyRef); 
                // Build an accessor over the new property 
                newNode = this.BuildAccessorWithNulls(n.Child0, newProp);
            } 
            return newNode;
        }

        ///  
        /// PropertyOp
        /// 
        /// If this is a scalar/collection property, then simply get the appropriate 
        /// field out.
        /// 
        /// Otherwise, build up a record constructor corresponding to the result
        /// type - optimize this by only getting those properties that are needed
        ///
        /// If the instance is not a structured type (ie) it is a UDT, then simply return 
        ///
        ///  
        /// the PropertyOp 
        /// the corresponding node
        /// new subtree 
        public override Node Visit(PropertyOp op, Node n) {
            return VisitPropertyOp(op, n, new SimplePropertyRef(op.PropertyInfo));
        }
 
        /// 
        /// RelPropertyOp. Pick out the appropriate property from the child 
        ///  
        /// 
        ///  
        /// 
        public override Node Visit(RelPropertyOp op, Node n) {
            return VisitPropertyOp(op, n, new RelPropertyRef(op.PropertyInfo));
        } 

        ///  
        /// RefOp 
        ///
        /// Simply convert this into the corresponding record type - with one 
        /// field for each key, and one for the entitysetid
        /// 
        /// 
        ///  
        /// 
        public override Node Visit(RefOp op, Node n) { 
            TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(((ScalarOp)n.Child0.Op).Type); 
            TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(op.Type);
 
            // visit children now
            VisitChildren(n);

            // Get the list of fields and properties from the input (key) op 
            List inputFields;
            List inputFieldValues; 
            GetPropertyValues(inputTypeInfo, OperationKind.All, n.Child0, false, out inputFields, out inputFieldValues); 

            // Get my property list 
            List outputFields = new List(outputTypeInfo.FlattenedType.Properties);

            // We have to adjust for when we're supposed to remove null sentinels;
            // columns (See SQLBUDT #553534 for an example).  Note that we shouldn't 
            // have to add null sentinels here, since reference types won't be expecting
            // them (the fact that the key is null is good enough...) 
            if (inputTypeInfo.HasNullSentinelProperty && !outputTypeInfo.HasNullSentinelProperty) { 
                while (inputFields.Count > outputFields.Count) {
                    inputFields.RemoveAt(0); 
                    inputFieldValues.RemoveAt(0);
                }
            }
 
            if (outputTypeInfo.HasEntitySetIdProperty) {
                PlanCompiler.Assert(outputFields.Count == inputFields.Count + 1, "Mismatched field count: Expected " + (inputFields.Count + 1) + "; Got " + outputFields.Count); 
                PlanCompiler.Assert(outputFields[0] == outputTypeInfo.EntitySetIdProperty, "OutputField0 must be the entitySetId property"); 

                // Now prepend a value for the entitysetid property and a value for this property 
                int entitySetId = m_typeInfo.GetEntitySetId(op.EntitySet);
                inputFieldValues.Insert(0, m_command.CreateNode(m_command.CreateInternalConstantOp(md.Helper.GetModelTypeUsage(outputTypeInfo.EntitySetIdProperty), entitySetId)));
            }
            else { 
                PlanCompiler.Assert(outputFields.Count == inputFields.Count, "Mismatched field count: Expected " + inputFields.Count + "; Got " + outputFields.Count);
            } 
 
            // now build up a NewRecordConstructor with the appropriate info
            NewRecordOp recOp = m_command.CreateNewRecordOp(outputTypeInfo.FlattenedTypeUsage, outputFields); 
            Node newNode = m_command.CreateNode(recOp, inputFieldValues);

            return newNode;
        } 

        ///  
        /// VarRefOp 
        ///
        /// Replace a VarRef with a copy of the corresponding "Record" constructor 
        /// 
        /// the VarRefOp
        /// the node
        /// new subtree 
        public override Node Visit(VarRefOp op, Node n) {
            // Lookup my VarInfo 
            VarInfo varInfo; 
            if (!m_varInfoMap.TryGetVarInfo(op.Var, out varInfo)) {
                PlanCompiler.Assert(!TypeUtils.IsStructuredType(op.Type), 
                    "No varInfo for a structured type var: Id = " + op.Var.Id + " Type = " + op.Type);
                return n;
            }
            if (varInfo.IsCollectionType) { 
                n.Op = m_command.CreateVarRefOp(((CollectionVarInfo)varInfo).NewVar);
                return n; 
            } 
            else {
                // A very specialized record constructor mechanism for structured type Vars. 
                // We look up the VarInfo corresponding to the Var - which has a set of fields
                // and the corresponding properties that we need to produce

                StructuredVarInfo structuredVarInfo = (StructuredVarInfo)varInfo; 

                NewRecordOp newOp = m_command.CreateNewRecordOp(structuredVarInfo.NewTypeUsage, structuredVarInfo.Fields); 
                List newNodeChildren = new List(); 
                foreach (Var v in varInfo.NewVars) {
                    VarRefOp newVarRefOp = m_command.CreateVarRefOp(v); 
                    newNodeChildren.Add(m_command.CreateNode(newVarRefOp));
                }
                Node newNode = m_command.CreateNode(newOp, newNodeChildren);
                return newNode; 
            }
        } 
 
        #region record construction ops
 
        /// 
        /// Handler for NewEntity
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(NewEntityOp op, Node n) { 
            return FlattenConstructor(op, n);
        } 

        /// 
        /// NewInstanceOp
        ///  
        /// the NewInstanceOp
        /// corresponding node 
        /// new subtree 
        public override Node Visit(NewInstanceOp op, Node n) {
            return FlattenConstructor(op, n); 
        }

        /// 
        /// DiscriminatedNewInstanceOp 
        /// 
        /// the DiscriminatedNewInstanceOp 
        /// corresponding node 
        /// new subtree
        public override Node Visit(DiscriminatedNewEntityOp op, Node n) { 
            return FlattenConstructor(op, n);
        }

        ///  
        /// Given an explicit discriminator value, map to normalized values. Essentially, this allows
        /// a discriminated new instance to coexist with free-floating entities, MEST, etc. which use 
        /// general purpose ordpath type ids (e.g. '0X0X') 
        ///
        /// An example of the normalization is given: 
        ///
        /// CASE
        ///     WHEN discriminator = 'Base' THEN '0X'
        ///     WHEN discriminator = 'Derived1' THEN '0X0X' 
        ///     WHEN discriminator = 'Derived2' THEN '0X1X'
        ///     ELSE '0X2X' -- default case for 'Derived3' 
        ///  
        private Node NormalizeTypeDiscriminatorValues(DiscriminatedNewEntityOp op, Node discriminator) {
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type); 

            CaseOp normalizer = m_command.CreateCaseOp(typeInfo.RootType.TypeIdProperty.TypeUsage);
            List children = new List(op.DiscriminatorMap.TypeMap.Count * 2 - 1);
            for (int i = 0; i < op.DiscriminatorMap.TypeMap.Count; i++) { 
                object discriminatorValue = op.DiscriminatorMap.TypeMap[i].Key;
                md.EntityType type = op.DiscriminatorMap.TypeMap[i].Value; 
                TypeInfo currentTypeInfo = m_typeInfo.GetTypeInfo(md.TypeUsage.Create(type)); 

                Node normalizedDiscriminatorConstant = CreateTypeIdConstant(currentTypeInfo); 
                // for the last type, return the 'then' value
                if (i == op.DiscriminatorMap.TypeMap.Count - 1) {
                    // ELSE normalizedDiscriminatorValue
                    children.Add(normalizedDiscriminatorConstant); 
                }
                else { 
                    // WHEN discriminator = discriminatorValue THEN normalizedDiscriminatorValue 
                    ConstantBaseOp discriminatorValueOp = m_command.CreateConstantOp(md.Helper.GetModelTypeUsage(op.DiscriminatorMap.DiscriminatorProperty.TypeUsage),
                                                                                     discriminatorValue); 
                    Node discriminatorConstant = m_command.CreateNode(discriminatorValueOp);
                    ComparisonOp discriminatorPredicateOp = m_command.CreateComparisonOp(OpType.EQ);
                    Node discriminatorPredicate = m_command.CreateNode(discriminatorPredicateOp, discriminator, discriminatorConstant);
                    children.Add(discriminatorPredicate); 
                    children.Add(normalizedDiscriminatorConstant);
                } 
            } 

            // swap discriminator with case op normalizing the discriminator 
            discriminator = m_command.CreateNode(normalizer, children);
            return discriminator;
        }
 
        /// 
        /// NewRecordOp 
        ///  
        /// the newRecordOp
        /// corresponding node 
        /// new subtree
        public override Node Visit(NewRecordOp op, Node n) {
            return FlattenConstructor(op, n);
        } 

        ///  
        /// Build out an expression corresponding to the entitysetid 
        /// 
        /// the property corresponding to the entitysetid 
        /// the *NewEntity op
        /// 
        private Node GetEntitySetIdExpr(md.EdmProperty entitySetIdProperty, NewEntityBaseOp op) {
            Node entitySetIdNode; 
            md.EntitySet entitySet = op.EntitySet as md.EntitySet;
            if (entitySet != null) { 
                int entitySetId = m_typeInfo.GetEntitySetId(entitySet); 
                InternalConstantOp entitySetIdOp = m_command.CreateInternalConstantOp(md.Helper.GetModelTypeUsage(entitySetIdProperty), entitySetId);
                entitySetIdNode = m_command.CreateNode(entitySetIdOp); 
            }
            else {
                //
                // Not in a view context; simply assume a null entityset 
                //
                entitySetIdNode = CreateNullConstantNode(md.Helper.GetModelTypeUsage(entitySetIdProperty)); 
            } 

            return entitySetIdNode; 
        }

        /// 
        /// Flattens out a constructor into a "flat" record constructor. 
        /// The "flat" record type is looked up for the current constructor's type,
        /// and each property is filled out from the current constructor's fields 
        ///  
        /// The NewRecordOp/NewInstanceOp
        /// The current subtree 
        /// the new subtree
        private Node FlattenConstructor(ScalarOp op, Node n) {
            PlanCompiler.Assert(op.OpType == OpType.NewInstance || op.OpType == OpType.NewRecord || op.OpType == OpType.DiscriminatedNewEntity || op.OpType == OpType.NewEntity,
                "unexpected op: " + op.OpType + "?"); 

            // First visit all my children 
            VisitChildren(n); 

            // Find the new type corresponding to the type 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type);
            md.RowType flatType = typeInfo.FlattenedType;
            NewEntityBaseOp newEntityOp = op as NewEntityBaseOp;
 
            // Identify the fields
            IEnumerable opFields = null; 
            DiscriminatedNewEntityOp discriminatedNewInstanceOp = null; 
            if (op.OpType == OpType.NewRecord) {
                // Get only those fields that I have values for 
                opFields = ((NewRecordOp)op).Properties;
            }
            else if (op.OpType == OpType.DiscriminatedNewEntity) {
                // Get all properties projected by the discriminated new instance op 
                discriminatedNewInstanceOp = (DiscriminatedNewEntityOp)op;
                opFields = discriminatedNewInstanceOp.DiscriminatorMap.Properties; 
            } 
            else {
                // Children align with structural members of type for a standard NewInstanceOp 
                opFields = TypeHelpers.GetAllStructuralMembers(op.Type);
            }

            // Next, walk through each of my field, and flatten out any field 
            // that is structured.
            List newFields = new List(); 
            List newFieldValues = new List(); 

            // 
            // NOTE: we expect the type id property and the entityset id properties
            //       to be at the start of the properties collection.
            //
            // Add a typeid property if we need one 
            //
            if (typeInfo.HasTypeIdProperty) { 
                newFields.Add(typeInfo.TypeIdProperty); 
                if (null == discriminatedNewInstanceOp) {
                    newFieldValues.Add(CreateTypeIdConstant(typeInfo)); 
                }
                else {
                    // first child in DiscriminatedNewInstanceOp is discriminator/typeid
                    Node discriminator = n.Children[0]; 

                    if (null == typeInfo.RootType.DiscriminatorMap) { 
                        // if there are multiple sets (or free-floating constructors) for this type 
                        // hierarchy, normalize the discriminator value to expose the standard
                        // '0X' style values 
                        discriminator = NormalizeTypeDiscriminatorValues(discriminatedNewInstanceOp, discriminator);
                    }

                    newFieldValues.Add(discriminator); 
                }
            } 
 
            //
            // Add an entitysetid property if we need one 
            //
            if (typeInfo.HasEntitySetIdProperty) {
                newFields.Add(typeInfo.EntitySetIdProperty);
 
                PlanCompiler.Assert(newEntityOp != null, "unexpected optype:" + op.OpType);
                Node entitySetIdNode = GetEntitySetIdExpr(typeInfo.EntitySetIdProperty, newEntityOp); 
 
                // Get the entity-set-id of the "current" entityset
                newFieldValues.Add(entitySetIdNode); 
            }

            // Add a nullability property if we need one
            if (typeInfo.HasNullSentinelProperty) { 
                newFields.Add(typeInfo.NullSentinelProperty);
                newFieldValues.Add(CreateNullSentinelConstant()); 
            } 

            // 
            // first child of discriminatedNewInstanceOp is the typeId; otherwise, the first child is the first property
            //
            int childrenIndex = null == discriminatedNewInstanceOp ? 0 : 1;
 
            foreach (md.EdmMember opField in opFields) {
                Node fieldValue = n.Children[childrenIndex]; 
                if (TypeUtils.IsStructuredType(md.Helper.GetModelTypeUsage(opField))) { 
                    // Flatten out nested type
                    md.RowType nestedFlatType = m_typeInfo.GetTypeInfo(md.Helper.GetModelTypeUsage(opField)).FlattenedType; 

                    // Find offset of opField in top-level flat type
                    int nestedPropertyOffset = typeInfo.RootType.GetNestedStructureOffset(new SimplePropertyRef(opField));
 
                    foreach (md.EdmProperty nestedProperty in nestedFlatType.Properties) {
                        // Try to build up an accessor for this property from the input 
                        Node nestedPropertyValue = BuildAccessor(fieldValue, nestedProperty); 

                        if (null != nestedPropertyValue) { 
                            newFields.Add(flatType.Properties[nestedPropertyOffset]);
                            newFieldValues.Add(nestedPropertyValue);
                        }
 
                        nestedPropertyOffset++;
                    } 
                } 
                else {
                    PropertyRef propRef = new SimplePropertyRef(opField); 
                    md.EdmProperty outputTypeProp = typeInfo.GetNewProperty(propRef);

                    newFields.Add(outputTypeProp);
 
                    newFieldValues.Add(fieldValue);
                } 
 
                childrenIndex++;
            } 

            //
            // We've now handled all the regular properties. Now, walk through all the rel properties -
            // obviously, this only applies for the *NewEntityOps 
            //
            if (newEntityOp != null) { 
                foreach (RelProperty relProp in newEntityOp.RelationshipProperties) { 
                    Node fieldValue = n.Children[childrenIndex];
                    md.RowType nestedFlatType = m_typeInfo.GetTypeInfo(relProp.ToEnd.TypeUsage).FlattenedType; 

                    // Find offset of opField in top-level flat type
                    int nestedPropertyOffset = typeInfo.RootType.GetNestedStructureOffset(new RelPropertyRef(relProp));
 
                    foreach (md.EdmProperty nestedProperty in nestedFlatType.Properties) {
                        // Try to build up an accessor for this property from the input 
                        Node nestedPropertyValue = BuildAccessor(fieldValue, nestedProperty); 

                        if (null != nestedPropertyValue) { 
                            newFields.Add(flatType.Properties[nestedPropertyOffset]);
                            newFieldValues.Add(nestedPropertyValue);
                        }
 
                        nestedPropertyOffset++;
                    } 
                    childrenIndex++; 
                }
            } 

            //
            // So, now we have the list of all fields that should make up the
            // flat type.  Create a new node with them. 
            //
            NewRecordOp newOp = m_command.CreateNewRecordOp(typeInfo.FlattenedTypeUsage, newFields); 
            Node newNode = m_command.CreateNode(newOp, newFieldValues); 

            return newNode; 
        }

        /// 
        /// NullOp 
        ///
        /// If the node represents a null of an entity type it 'flattens' it into a new record, 
        /// with at most one non-null value: for the typeIdProperty, if one is needed. 
        /// If the node represents an null of a non-entity type, no special work is done.
        ///  
        /// The NullOp
        /// The current subtree
        /// the new subtree
        public override Node Visit(NullOp op, Node n) { 
            if (!TypeUtils.IsStructuredType(op.Type)) {
                return n; 
            } 

            // Find the new type corresponding to the type 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type);

            List newFields = new List();
            List newFieldValues = new List(); 

            // Add a typeid property if we need one 
            if (typeInfo.HasTypeIdProperty) { 
                newFields.Add(typeInfo.TypeIdProperty);
                var typeIdType = md.Helper.GetModelTypeUsage(typeInfo.TypeIdProperty); 
                newFieldValues.Add(CreateNullConstantNode(typeIdType));
            }

            NewRecordOp newRecordOp = new NewRecordOp(typeInfo.FlattenedTypeUsage, newFields); 
            return m_command.CreateNode(newRecordOp, newFieldValues);
        } 
 
        #endregion
 
        #region type comparison ops

        /// 
        /// IsOf 
        ///
        /// Convert an IsOf operator into a typeid comparison: 
        /// 
        ///     IsOfOnly(e, T) => e.TypeId == TypeIdValue(T)
        ///     IsOf(e, T)     => e.TypeId like TypeIdValue(T)% escape null 
        ///
        /// 
        /// The IsOfOp to handle
        /// current isof subtree 
        /// new subtree
        public override Node Visit(IsOfOp op, Node n) { 
            // First visit all my children 
            VisitChildren(n);
 
            if (!TypeUtils.IsStructuredType(op.IsOfType)) {
                return n;
            }
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.IsOfType); 
            Node newNode = CreateTypeComparisonOp(n.Child0, typeInfo, op.IsOfOnly);
            return newNode; 
        } 

        ///  
        /// TreatOp
        ///
        ///     TreatOp(e, T) => case when e.TypeId like TypeIdValue(T) then T else null end
        ///  
        /// the TreatOp
        /// the node 
        /// new subtree 
        public override Node Visit(TreatOp op, Node n) {
            // First visit all my children 
            VisitChildren(n);

            //
            // filter out useless treat operations 
            // Treat(subtype-instance as superType)
            // 
            ScalarOp arg = (ScalarOp)n.Child0.Op; 
            if (op.IsFakeTreat ||
                md.TypeSemantics.IsEquivalent(arg.Type, op.Type) || 
                md.TypeSemantics.IsSubTypeOf(arg.Type, op.Type)) {
                return n.Child0;
            }
 
            // When we support UDTs
            if (!TypeUtils.IsStructuredType(op.Type)) { 
                return n; 
            }
 
            //
            // First, convert this into a CaseOp:
            //   case when e.TypeId like TypeIdValue then e else null end
            // 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type);
            Node likeNode = CreateTypeComparisonOp(n.Child0, typeInfo, false); 
            CaseOp caseOp = m_command.CreateCaseOp(typeInfo.FlattenedTypeUsage); 
            Node caseNode = m_command.CreateNode(caseOp, likeNode, n.Child0, CreateNullConstantNode(caseOp.Type));
 
            //
            // Now "flatten" out this Op into a constructor. But only get the
            // desired properties
            // 
            PropertyRefList desiredProperties = m_nodePropertyMap[n];
            Node flattenedCaseNode = FlattenCaseOp(caseOp, caseNode, typeInfo, desiredProperties); 
            return flattenedCaseNode; 
        }
 
        /// 
        /// Create a typeid-comparison operator - more specifically, create an
        /// operator that compares a typeid value with the typeid property of an
        /// input structured type. 
        /// The comparison may be "exact" - in which case we're looking for the exact
        /// type; otherwise, we're looking for any possible subtypes. 
        /// The "exact" variant is used by the IsOfOp (only); the other variant is 
        /// used by IsOfOp and TreatOp
        ///  
        /// The input structured type expression
        /// Augmented type information for the type
        /// Exact comparison?
        /// New comparison expression 
        private Node CreateTypeComparisonOp(Node input, TypeInfo typeInfo, bool isExact) {
            Node typeIdProperty = BuildTypeIdAccessor(input, typeInfo); 
            Node newNode = null; 

            if (isExact) { 
                newNode = CreateTypeEqualsOp(typeInfo, typeIdProperty);
            }
            else {
                if (typeInfo.RootType.DiscriminatorMap != null) { 
                    // where there are explicit discriminator values, LIKE '0X%' pattern does not work...
                    newNode = CreateDisjunctiveTypeComparisonOp(typeInfo, typeIdProperty); 
                } 
                else {
                    Node typeIdConstantNode = CreateTypeIdConstantForPrefixMatch(typeInfo); 
                    LikeOp likeOp = m_command.CreateLikeOp();
                    newNode = m_command.CreateNode(likeOp, typeIdProperty, typeIdConstantNode, CreateNullConstantNode(DefaultTypeIdType));
                }
            } 
            return newNode;
        } 
 
        /// 
        /// Create a filter matching all types in the given hierarchy (typeIdProperty IN typeInfo.Hierarchy) e.g.: 
        ///
        ///     typeIdProperty = 'Base' OR typeIdProperty = 'Derived1' ...
        ///
        /// This is called only for types using DiscriminatorMap (explicit discriminator values) 
        /// 
        ///  
        ///  
        /// type hierarchy check
        private Node CreateDisjunctiveTypeComparisonOp(TypeInfo typeInfo, Node typeIdProperty) { 
            PlanCompiler.Assert(typeInfo.RootType.DiscriminatorMap != null, "should be used only for DiscriminatorMap type checks");
            // collect all non-abstract types in the given hierarchy
            IEnumerable types = typeInfo.GetTypeHierarchy().Where(t => !t.Type.EdmType.Abstract);
 
            // generate a disjunction
            Node current = null; 
            foreach (TypeInfo type in types) { 
                Node typeComparisonNode = CreateTypeEqualsOp(type, typeIdProperty);
                if (null == current) { 
                    current = typeComparisonNode;
                }
                else {
                    current = m_command.CreateNode(m_command.CreateConditionalOp(OpType.Or), current, typeComparisonNode); 
                }
            } 
            if (null == current) { 
                // only abstract types in this hierarchy... no values possible
                current = m_command.CreateNode(m_command.CreateFalseOp()); 
            }
            return current;
        }
 
        /// 
        /// Generates a node of the form typeIdProperty = typeInfo.TypeId 
        ///  
        /// 
        ///  
        /// type equality check
        private Node CreateTypeEqualsOp(TypeInfo typeInfo, Node typeIdProperty) {
            Node typeIdConstantNode = CreateTypeIdConstant(typeInfo);
            ComparisonOp eqCompOp = m_command.CreateComparisonOp(OpType.EQ); 
            Node result = m_command.CreateNode(eqCompOp, typeIdProperty, typeIdConstantNode);
            return result; 
        } 

        #endregion 

        #endregion

        #endregion 

    } 
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections; 
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization;
using System.Linq; 
using System.Data.Common;
using md = System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees; 
using System.Data.Query.PlanCompiler;
 

namespace System.Data.Query.PlanCompiler {
    /// 
    /// The goal of this module is to eliminate all references to nominal types 
    /// in the tree. Additionally, all structured types are replaced by "flat"
    /// record types - where every field of the structured type is a scalar type. 
    /// Note that UDTs are not considered to be structured types. 
    ///
    /// At the end of this phase, 
    /// * there are no more nominal types in the tree
    /// * there are no more nested record types in the tree
    /// * No Var in the tree is of an structured type
    /// * Additionally (and these follow from the statements above) 
    ///   * There are no NewInstanceOp constructors in the tree
    ///   * There are no PropertyOp operators where the result is a structured type 
    /// 
    /// This module uses information from the PropertyPushdown phase to "optimize"
    /// structured type elimination. Essentially, if we can avoid producing pieces 
    /// of information that will be discarded later, then lets do that.
    ///
    /// The general mechanism of type elimination is as follows. We walk up the tree
    /// in a bottom up fashion, and try to convert all structured types into flattened 
    /// record types - type constructors are first converted into flat record constructors
    /// and then dismantled etc. The barrier points - Vars - are all converted into 
    /// scalar types, and all intermediate stages will be eliminated in transition. 
    ///
    /// The output from this phase includes a ColumnMap - which is used later by 
    /// the execution model to produce results in the right form from an otherwise
    /// flat query
    ///
    /// Notes: This phase could be combined later with the PropertyPushdown phase 
    ///
    ///  
    internal class NominalTypeEliminator : BasicOpVisitorOfNode { 

        #region Nested Classes 
        /// 
        /// Describes an operation kind - for various property extractions
        /// 
        internal enum OperationKind { 
            /// 
            /// Comparing two instances for equality 
            ///  
            Equality,
 
            /// 
            /// Checking to see if an instance is null
            /// 
            IsNull, 

            ///  
            /// Getting the "identity" of an entity 
            /// 
            GetIdentity, 

            /// 
            /// Getting the keys of an entity
            ///  
            GetKeys,
 
            ///  
            /// All properties of an entity
            ///  
            All
        }
        #endregion
 
        #region private state
 
        private Dictionary m_varPropertyMap; 
        private Dictionary m_nodePropertyMap;
        private VarInfoMap m_varInfoMap; 
        private PlanCompiler m_compilerState;
        private Command m_command { get { return m_compilerState.Command; } }
        private StructuredTypeInfo m_typeInfo;
        private Dictionary m_typeToNewTypeMap; 
        private const string PrefixMatchCharacter = "%"; // This is ANSI-SQL defined, but it should probably be configurable.
 
        #endregion 

        #region constructors 

        private NominalTypeEliminator(PlanCompiler compilerState,
            StructuredTypeInfo typeInfo,
            Dictionary varPropertyMap, 
            Dictionary nodePropertyMap) {
            m_compilerState = compilerState; 
            m_typeInfo = typeInfo; 
            m_varPropertyMap = varPropertyMap;
            m_nodePropertyMap = nodePropertyMap; 
            m_varInfoMap = new VarInfoMap();
            m_typeToNewTypeMap = new Dictionary(TypeUsageEqualityComparer.Instance);
        }
 
        #endregion
 
        #region Process Driver 

        ///  
        /// Eliminates all structural types from the query
        /// 
        /// current compiler state
        /// list of all referenced types 
        /// list of referenced entitysets
        internal static void Process(PlanCompiler compilerState, 
            StructuredTypeInfo structuredTypeInfo) { 
#if DEBUG
            //string phase0 = Dump.ToXml(compilerState.Command); 
            Validator.Validate(compilerState);
#endif

            // Phase 1: Top-down property pushdown 
            Dictionary varPropertyMap;
            Dictionary nodePropertyMap; 
            PropertyPushdownHelper.Process(compilerState.Command, structuredTypeInfo, out varPropertyMap, out nodePropertyMap); 

#if DEBUG 
            //string phase1 = Dump.ToXml(compilerState.Command);
            Validator.Validate(compilerState);
#endif
 
            // Phase 2: actually eliminate nominal types
            NominalTypeEliminator nte = new NominalTypeEliminator(compilerState, structuredTypeInfo, 
                varPropertyMap, nodePropertyMap); 
            nte.Process();
 
#if DEBUG
            //string phase2 = Dump.ToXml(compilerState.Command);
            Validator.Validate(compilerState);
#endif 

#if DEBUG 
            //To avoid garbage collection 
            //int size = phase0.Length;
            //size = phase1.Length; 
            //size = phase2.Length;
#endif
        }
 

        ///  
        /// The real driver. Invokes the visitor to traverse the tree bottom-up, 
        /// and modifies the tree along the way.
        ///  
        private void Process() {
            Node rootNode = m_command.Root;
            PlanCompiler.Assert(rootNode.Op.OpType == OpType.PhysicalProject, "root node is not PhysicalProjectOp?");
            // invoke the visitor on the root node 
            rootNode.Op.Accept(this, rootNode);
        } 
 
        #endregion
 
        #region type utilities

        /// 
        /// The datatype of the typeid property 
        /// 
        private md.TypeUsage DefaultTypeIdType { 
            get { return m_command.StringType; } 
        }
 
        /// 
        /// Get the "new" type corresponding to the input type.
        /// For structured types, we simply look up the typeInfoMap
        /// For collection types, we create a new collection type based on the 
        ///   "new" element type.
        /// For all other types, we simply return the input type 
        ///  
        /// 
        ///  
        private md.TypeUsage GetNewType(md.TypeUsage type) {
            md.TypeUsage newType;

            if (m_typeToNewTypeMap.TryGetValue(type, out newType)) { 
                return newType;
            } 
 
            md.CollectionType collectionType;
            if (TypeHelpers.TryGetEdmType(type, out collectionType)) { 
                // If this is a collection type, then clone a new collection type
                md.TypeUsage newElementType = GetNewType(collectionType.TypeUsage);
                newType = TypeUtils.CreateCollectionType(newElementType);
            } 
            else if (TypeUtils.IsStructuredType(type)) {
                // structured type => we've already calculated the input 
                newType = m_typeInfo.GetTypeInfo(type).FlattenedTypeUsage; 
            }
            else { 
                // "simple" type => return the input type
                newType = type;
            }
 
            // Add this information to the map
            m_typeToNewTypeMap[type] = newType; 
            return newType; 
        }
 
        #endregion

        #region misc utilities
 
        /// 
        /// This function builds a "property accessor" over the input expression.  It 
        /// can produce one of three results: 
        ///
        ///   - It can return "null", if it is convinced that the input has no 
        ///     such expression
        ///   - It can return a subnode of the input, if that subnode represents
        ///     the property
        ///   - Or, it can build a PropertyOp explicitly 
        ///
        /// Assertion: the property is not a structured type 
        ///  
        /// The input expression
        /// The desired property 
        /// 
        private Node BuildAccessor(Node input, md.EdmProperty property) {
            Op inputOp = input.Op;
 
            // Special handling if the input is a NewRecordOp
            NewRecordOp newRecordOp = inputOp as NewRecordOp; 
            if (null != newRecordOp) { 
                int fieldPos;
                // Identify the specific property we're interested in. 
                if (newRecordOp.GetFieldPosition(property, out fieldPos)) {
                    return Copy(input.Children[fieldPos]);
                }
                else { 
                    return null;
                } 
            } 

            // special handling if the input is a null 
            if (inputOp.OpType == OpType.Null) {
                return null;
            }
 
            // The default case: Simply return a new PropertyOp
            PropertyOp newPropertyOp = m_command.CreatePropertyOp(property); 
            return m_command.CreateNode(newPropertyOp, this.Copy(input)); 
        }
 
        /// 
        /// A BuildAccessor variant. If the appropriate property was not found, then
        /// build up a null constant instead
        ///  
        /// 
        ///  
        ///  
        private Node BuildAccessorWithNulls(Node input, md.EdmProperty property) {
            Node newNode = this.BuildAccessor(input, property); 
            if (newNode == null) {
                newNode = CreateNullConstantNode(md.Helper.GetModelTypeUsage(property));
            }
            return newNode; 
        }
 
        ///  
        /// Builds up an accessor to the typeid property. If the type has no typeid
        /// property, then we simply create a constantOp with the corresponding 
        /// typeid value for the type
        /// 
        /// the input expression
        /// the original type of the input expression 
        /// 
        private Node BuildTypeIdAccessor(Node input, TypeInfo typeInfo) { 
            Node result; 

            if (typeInfo.HasTypeIdProperty) { 
                result = BuildAccessorWithNulls(input, typeInfo.TypeIdProperty);
            }
            else {
                result = CreateTypeIdConstant(typeInfo); 
            }
 
            return result; 
        }
 
        /// 
        /// Builds a SoftCast operator over the input - if one is necessary.
        /// 
        /// the input expression to "cast" 
        /// the target type
        /// the "cast"ed expression 
        private Node BuildSoftCast(Node node, md.TypeUsage targetType) { 
            PlanCompiler.Assert(node.Op.IsScalarOp, "Attempting SoftCast around non-ScalarOp?");
            if (Command.EqualTypes(node.Op.Type, targetType)) { 
                return node;
            }
            // Skip any castOps we may have created already
            while (node.Op.OpType == OpType.SoftCast) { 
                node = node.Child0;
            } 
            Node newNode = m_command.CreateNode(m_command.CreateSoftCastOp(targetType), node); 
            return newNode;
        } 

        /// 
        /// Clones a subtree.
        /// This is used by the "BuildAccessor" routines to build a property-accessor 
        /// over some input. If we're reusing the input, the input must be cloned.
        ///  
        /// The subtree to copy 
        /// 
        private Node Copy(Node n) { 
            return OpCopier.Copy(m_command, n);
        }

        ///  
        /// Returns a node for a null constant of the desired type
        ///  
        ///  
        /// 
        private Node CreateNullConstantNode(md.TypeUsage type) { 
            return m_command.CreateNode(m_command.CreateNullOp(type));
        }

        ///  
        /// Create a node to represent nullability.
        ///  
        /// Node for the typeid constant 
        private Node CreateNullSentinelConstant() {
            InternalConstantOp op = m_command.CreateInternalConstantOp(m_command.IntegerType, 1); 
            return m_command.CreateNode(op);
        }

        ///  
        /// Create a node to represent the exact value of the typeid constant
        ///  
        /// The current type 
        /// Node for the typeid constant
        private Node CreateTypeIdConstant(TypeInfo typeInfo) { 
            object value = typeInfo.TypeId;
            md.TypeUsage typeIdType;
            if (typeInfo.RootType.DiscriminatorMap != null) {
                typeIdType = md.Helper.GetModelTypeUsage(typeInfo.RootType.DiscriminatorMap.DiscriminatorProperty); 
            }
            else { 
                typeIdType = DefaultTypeIdType; 
            }
            InternalConstantOp op = m_command.CreateInternalConstantOp(typeIdType, value); 
            return m_command.CreateNode(op);
        }

        ///  
        /// Create a node to represent a typeid constant for a prefix match.
        /// If the typeid value were "123X", then we would generate a constant 
        /// like "123X%" 
        /// 
        /// the current type 
        /// Node for the typeid constant
        private Node CreateTypeIdConstantForPrefixMatch(TypeInfo typeInfo) {
            string value = typeInfo.TypeId + PrefixMatchCharacter;
            InternalConstantOp op = m_command.CreateInternalConstantOp(DefaultTypeIdType, value); 
            return m_command.CreateNode(op);
        } 
 
        /// 
        /// Identify the list of property refs for comparison and isnull semantics 
        /// 
        /// 
        /// 
        ///  
        private IEnumerable GetPropertyRefsForComparisonAndIsNull(TypeInfo typeInfo, OperationKind opKind) {
            PlanCompiler.Assert(opKind == OperationKind.IsNull || opKind == OperationKind.Equality, 
                "Unexpected opKind: " + opKind + "; Can only handle IsNull and Equality"); 

            md.TypeUsage currentType = typeInfo.Type; 

            md.RowType recordType = null;
            if (TypeHelpers.TryGetEdmType(currentType, out recordType)) {
                if (opKind == OperationKind.IsNull && typeInfo.HasNullSentinelProperty) { 
                    yield return NullSentinelPropertyRef.Instance;
                } 
                else 
                foreach (md.EdmProperty m in recordType.Properties) {
                    if (!TypeUtils.IsStructuredType(md.Helper.GetModelTypeUsage(m))) { 
                        yield return new SimplePropertyRef(m);
                    }
                    else {
                        TypeInfo nestedTypeInfo = m_typeInfo.GetTypeInfo(md.Helper.GetModelTypeUsage(m)); 
                        foreach (PropertyRef p in GetPropertyRefs(nestedTypeInfo, opKind)) {
                            PropertyRef nestedPropertyRef = p.CreateNestedPropertyRef(m); 
                            yield return nestedPropertyRef; 
                        }
                    } 
                }
                yield break;
            }
 
            md.EntityType entityType = null;
            if (TypeHelpers.TryGetEdmType(currentType, out entityType)) { 
                if (opKind == OperationKind.Equality || 
                    (opKind == OperationKind.IsNull && !typeInfo.HasTypeIdProperty)) {
                    foreach (PropertyRef p in typeInfo.GetIdentityPropertyRefs()) { 
                        yield return p;
                    }
                }
                else { 
                    yield return TypeIdPropertyRef.Instance;
                } 
                yield break; 
            }
 
            md.ComplexType complexType = null;
            if (TypeHelpers.TryGetEdmType(currentType, out complexType)) {
                PlanCompiler.Assert(opKind == OperationKind.IsNull, "complex types not equality-comparable");
                PlanCompiler.Assert(typeInfo.HasTypeIdProperty, "complex type with no typeid property: can't handle isNull"); 
                yield return TypeIdPropertyRef.Instance;
                yield break; 
            } 

            md.RefType refType = null; 
            if (TypeHelpers.TryGetEdmType(currentType, out refType)) {
                foreach (PropertyRef p in typeInfo.GetAllPropertyRefs()) {
                    yield return p;
                } 
                yield break;
            } 
 
            PlanCompiler.Assert(false, "Unknown type");
        } 

        /// 
        /// Get the list of "desired" propertyrefs for the specified type and operation
        ///  
        /// 
        ///  
        ///  
        private IEnumerable GetPropertyRefs(TypeInfo typeInfo, OperationKind opKind) {
            PlanCompiler.Assert(opKind != OperationKind.All, "unexpected attempt to GetPropertyRefs(...,OperationKind.All)"); 
            if (opKind == OperationKind.GetKeys) {
                return typeInfo.GetKeyPropertyRefs();
            }
            else if (opKind == OperationKind.GetIdentity) { 
                return typeInfo.GetIdentityPropertyRefs();
            } 
            else { 
                return GetPropertyRefsForComparisonAndIsNull(typeInfo, opKind);
            } 
        }

        /// 
        /// Get a list of "desired" properties for each operationKind (specified by the opKind 
        /// parameter). The OpKinds we support are
        /// 
        ///  * GetKeys 
        ///    Applies only to entity and ref types - gets the key properties (more specifically
        ///      the flattened equivalents) 
        ///  * GetIdentity
        ///    Applies only to entity and ref types - gets the entityset id property first, and then the
        ///      the Key properties
        ///  * All 
        ///    Gets all properties of the flattened type
        /// 
        ///  * Equality 
        ///    Scalar types - the entire instance
        ///    Entity - the identity properties 
        ///    Ref - all properties (= identity properties)
        ///    Complex/Collection - Not supported
        ///    Record - recurse over each property
        /// 
        ///  * IsNull
        ///    Scalar types - entire instance 
        ///    Entity - typeid property, if it exists; otherwise, the key properties 
        ///    ComplexType - typeid property
        ///    Ref - all properties 
        ///    Collection - not supported
        ///    Record - recurse over each property
        /// 
        /// Type information for the current op 
        /// Current operation kind
        /// List of desired properties 
        private IEnumerable GetProperties(TypeInfo typeInfo, OperationKind opKind) { 
            if (opKind == OperationKind.All) {
                foreach (md.EdmProperty p in typeInfo.GetAllProperties()) { 
                    yield return p;
                }
            }
            else { 
                foreach (PropertyRef p in GetPropertyRefs(typeInfo, opKind)) {
                    yield return typeInfo.GetNewProperty(p); 
                } 
            }
        } 

        /// 
        /// Get a list of properties and value (expressions) for each desired property of the
        /// input. The list of desired properties is based on the opKind parameter. 
        /// The ignoreMissingProperties indicates if we should create a null constant, in case
        /// the input cannot produce the specified property 
        ///  
        /// typeinfo for the input
        /// Current operation kind 
        /// The input expression tree
        /// Should we ignore missing properties
        /// Output: list of properties
        /// Output: correspondng list of values 
        private void GetPropertyValues(TypeInfo typeInfo, OperationKind opKind, Node input, bool ignoreMissingProperties,
            out List properties, out List values) { 
 
            values = new List();
            properties = new List(); 
            foreach (md.EdmProperty prop in GetProperties(typeInfo, opKind)) {
                KeyValuePair kv = GetPropertyValue(input, prop, ignoreMissingProperties);
                if (kv.Value != null) {
                    properties.Add(kv.Key); 
                    values.Add(kv.Value);
                } 
            } 
        }
 
        /// 
        /// Build up a key-value pair of (property, expression) to represent
        /// the extraction of the appropriate property from the input expression
        ///  
        /// The input (structured type) expression
        /// The property in question 
        /// should we ignore missing properties 
        /// 
        private KeyValuePair GetPropertyValue(Node input, md.EdmProperty property, bool ignoreMissingProperties) { 
            Node n = null;

            if (!ignoreMissingProperties) {
                n = BuildAccessorWithNulls(input, property); 
            }
            else { 
                n = BuildAccessor(input, property); 
            }
            return new KeyValuePair(property, n); 
        }

        /// 
        /// Walk the SortKeys, and expand out 
        /// any Structured type Var references
        ///  
        /// The list of input keys 
        /// An expanded list of keys. If there is nothing to expand it returns the original list.
        private List HandleSortKeys(List keys) { 
            List newSortKeys = new List();
            bool modified = false;
            foreach (InternalTrees.SortKey k in keys) {
                VarInfo varInfo; 
                if (!m_varInfoMap.TryGetVarInfo(k.Var, out varInfo)) {
                    newSortKeys.Add(k); 
                } 
                else {
                    foreach (Var v in varInfo.NewVars) { 
                        InternalTrees.SortKey newKey = Command.CreateSortKey(v, k.AscendingSort, k.Collation);
                        newSortKeys.Add(newKey);
                    }
                    modified = true; 
                }
            } 
 
            List result = modified ? newSortKeys : keys;
            return result; 
        }
        #endregion

        #region Visitor methods 

        #region AncillaryOp Visitors 
 
        /// 
        /// VarDefListOp 
        ///
        /// Walks each VarDefOp child, and "expands" it out if the Var is a
        /// structured type.
        /// 
        /// For each Var that is expanded, a new expression is created to compute
        /// its value (from the original computed expression) 
        /// A new VarDefListOp is created to hold all the "expanded" Varlist 
        /// 
        ///  
        /// 
        /// 
        public override Node Visit(VarDefListOp op, Node n) {
            VisitChildren(n); 

            List newChildren = new List(); 
 
            foreach (Node chi in n.Children) {
                VarDefOp varDefOp = chi.Op as VarDefOp; 

                if (TypeUtils.IsStructuredType(varDefOp.Var.Type)
                 || TypeUtils.IsCollectionType(varDefOp.Var.Type)) {
                    List newChiList; 
                    md.TypeUsage x;
 
                    FlattenComputedVar((ComputedVar)varDefOp.Var, chi, out newChiList, out x); 

                    foreach (Node newChi in newChiList) { 
                        newChildren.Add(newChi);
                    }
                }
                else { 
                    newChildren.Add(chi);
                } 
            } 
            Node newVarDefListNode = m_command.CreateNode(n.Op, newChildren);
            return newVarDefListNode; 
        }

        /// 
        /// Helps flatten out a computedVar expression 
        /// 
        /// The Var 
        /// Subtree rooted at the VarDefOp expression 
        /// list of new nodes produced
        ///  
        /// VarInfo for this var
        private void FlattenComputedVar(ComputedVar v, Node node, out List newNodes, out md.TypeUsage newType) {
            newNodes = new List();
            Node definingExprNode = node.Child0; // defining expression for the VarDefOp 
            newType = null;
 
            if (TypeUtils.IsCollectionType(v.Type)) { 
                newType = GetNewType(v.Type);
                Var newVar; 
                Node newVarDefNode = m_command.CreateVarDefNode(definingExprNode, out newVar);
                newNodes.Add(newVarDefNode);
                m_varInfoMap.CreateCollectionVarInfo(v, newVar);
                return; 
            }
 
            // Get the "new" type for the Var 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(v.Type);
            // Get a list of properties that we think are necessary 
            PropertyRefList desiredProperties = m_varPropertyMap[v];
            List newVars = new List();
            List newProps = new List();
            newNodes = new List(); 
            bool alwaysCreateVar = false;
            foreach (PropertyRef p in typeInfo.PropertyRefList) { 
                // do I care for this property? 
                if (!desiredProperties.Contains(p)) {
                    continue; 
                }

                md.EdmProperty newProperty = typeInfo.GetNewProperty(p);
 
                //
                // #479467 - Make sure that we build Vars for all properties - if 
                // we are asked to produce all properties. This is extremely important 
                // for the top-level Vars
                // 
                Node propAccessor = null;
                if (desiredProperties.AllProperties) {
                    propAccessor = BuildAccessorWithNulls(definingExprNode, newProperty);
                } 
                else {
                    propAccessor = BuildAccessor(definingExprNode, newProperty); 
                    if (propAccessor == null) { 
                        continue;
                    } 
                }

                // Add the new property
                newProps.Add(newProperty); 

                // Create a new VarDefOp. If the new defining expression 
                // is just a VarRefOp, then simply reuse that Var - don't 
                // create a new computed Var
                if (!alwaysCreateVar && (propAccessor.Op.OpType == OpType.VarRef)) { 
                    newVars.Add(((VarRefOp)propAccessor.Op).Var);
                }
                else {
                    Var newVar; 
                    Node newVarDefNode = m_command.CreateVarDefNode(propAccessor, out newVar);
                    newNodes.Add(newVarDefNode); 
                    newVars.Add(newVar); 
                }
                // 
                // Once I see a collection, start creating computed Vars.
                // The result assembly code has certain assumptions about
                // reading data from the store results - specifically, that
                // I won't jump back in the result stream when I see a collection. 
                // We may want to tweak this further, but,...
                // 
                if (TypeUtils.IsCollectionType(propAccessor.Op.Type)) { 
                    alwaysCreateVar = true;
                } 
            }
            m_varInfoMap.CreateStructuredVarInfo(v, typeInfo.FlattenedType, newVars, newProps);
            return;
        } 

        #endregion 
 
        #region PhysicalOp Visitors
 
        /// 
        /// PhysicalProjectOp
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(PhysicalProjectOp op, Node n) { 
            // visit my children
            VisitChildren(n); 

            // flatten out the varset
            VarList newVarList = FlattenVarList(op.Outputs);
            // reflect changes into my column map 
            SimpleCollectionColumnMap newColumnMap = ExpandColumnMap(op.ColumnMap);
            PhysicalProjectOp newOp = m_command.CreatePhysicalProjectOp(newVarList, newColumnMap); 
            n.Op = newOp; 

            return n; 
        }

        private SimpleCollectionColumnMap ExpandColumnMap(SimpleCollectionColumnMap columnMap) {
            VarRefColumnMap varRefColumnMap = columnMap.Element as VarRefColumnMap; 
            PlanCompiler.Assert(varRefColumnMap != null, "Encountered a SimpleCollectionColumnMap element that is not VarRefColumnMap when expanding a column map in NominalTypeEliminator.");
 
            // see if this var has changed in some fashion 
            VarInfo varInfo;
            if (!m_varInfoMap.TryGetVarInfo(varRefColumnMap.Var, out varInfo)) { 
                return columnMap; // no changes
            }

            // 
            // Ensure that we get the right number of Vars - we need one Var for
            // each scalar property 
            // 
            if (TypeUtils.IsStructuredType(varRefColumnMap.Var.Type)) {
                TypeInfo typeInfo = m_typeInfo.GetTypeInfo(varRefColumnMap.Var.Type); 
                PlanCompiler.Assert(typeInfo.RootType.FlattenedType.Properties.Count == varInfo.NewVars.Count,
                    "Var count mismatch; Expected " + typeInfo.RootType.FlattenedType.Properties.Count + "; got " + varInfo.NewVars.Count + " instead.");
            }
 
            // "Process" this columnMap
            ColumnMapProcessor processor = new ColumnMapProcessor(varRefColumnMap, varInfo, m_typeInfo); 
            ColumnMap newColumnMap = processor.ExpandColumnMap(); 

            //Wrap it with a collection 
            SimpleCollectionColumnMap resultColumnMap = new SimpleCollectionColumnMap(TypeUtils.CreateCollectionType(newColumnMap.Type), newColumnMap.Name, newColumnMap, columnMap.Keys, columnMap.ForeignKeys, columnMap.SortKeys);

            return resultColumnMap;
        } 

        #endregion 
 
        #region RelOp Visitors
 
        /// 
        /// Walk the input var sequence, flatten each var, and return the new sequence of
        /// Vars
        ///  
        /// input Var sequence
        /// flattened output var sequence 
        private IEnumerable FlattenVars(IEnumerable vars) { 
            foreach (Var v in vars) {
                VarInfo varInfo; 

                if (!m_varInfoMap.TryGetVarInfo(v, out varInfo)) {
                    yield return v;
                } 
                else {
                    foreach (Var newVar in varInfo.NewVars) { 
                        yield return newVar; 
                    }
                } 
            }
        }

        ///  
        /// Probe the current VarSet for "structured" Vars - replace these with the
        /// corresponding sets of flattened Vars 
        ///  
        /// current set of vars
        /// an "expanded" varset 
        private VarVec FlattenVarSet(VarVec varSet) {
            VarVec newVarSet = m_command.CreateVarVec(FlattenVars(varSet));
            return newVarSet;
        } 

        ///  
        /// Build up a new varlist, where each structured var has been replaced by its 
        /// corresponding flattened vars
        ///  
        /// the varlist to flatten
        /// the new flattened varlist
        private VarList FlattenVarList(VarList varList) {
            VarList newVarList = Command.CreateVarList(FlattenVars(varList)); 
            return newVarList;
        } 
 
        /// 
        /// Eliminates the internal constants and nulls from the list of keys in the given GroupBy node. 
        /// These may end up in the list of keys in the var flattening process.
        /// If elimination needs to happen, it does the following transformation:
        ///
        ///     GroupBy => Project (GroupBy') 
        ///
        /// GroupBy' is the same as GroupBy only with internal constants and nulls removed 
        ///  from the list of keys and the outputs. 
        /// The project has a VarDefList that includes these internal constants and nulls.
        ///  
        /// The subtree rooted at a group by node
        /// Transformed subtree
        private Node EliminateInternalConstantAndNullGroupByKeys(Node n) {
            PlanCompiler.Assert(n != null, "Null input"); 

            GroupByOp groupByOp = n.Op as GroupByOp; 
            PlanCompiler.Assert(groupByOp != null, "The op type of the input node to EliminateInternalConstantAndNullGroupByKeys is not a GroupByOp"); 

            PlanCompiler.Assert(n.Child1 != null, "A GroupBy node with no Child1"); 

            //If no keys are defined there is nothing to do
            if (n.Child1.Children.Count == 0) {
                return n; 
            }
 
            List nodesToMove = new List(); 

            //Find all keys that are internal constants or nulls 
            foreach (Node varDefNode in n.Child1.Children) {
                PlanCompiler.Assert(varDefNode.Op.OpType == OpType.VarDef, "A child of a VarDefList is not a VarDef");
                Node definingExprNode = varDefNode.Child0;
 
                if (definingExprNode.Op.OpType == OpType.InternalConstant || definingExprNode.Op.OpType == OpType.Null) {
                    nodesToMove.Add(varDefNode); 
                } 
            }
 
            //If there are no nodes to be moved, return the original
            if (nodesToMove.Count == 0) {
                return n;
            } 

            //Create a new project op 
            Node projectNode = 
                m_command.CreateNode(
                    m_command.CreateProjectOp(groupByOp.Outputs.Clone()), 
                    n,
                    m_command.CreateNode(
                        m_command.CreateVarDefListOp(),
                        nodesToMove 
                    )
                ); 
 
            //Remove all moved nodes from the group by
            foreach (Node nodeToMove in nodesToMove) { 
                n.Child1.Children.Remove(nodeToMove);

                VarDefOp nodeToMoveOp = nodeToMove.Op as VarDefOp;
                PlanCompiler.Assert(nodeToMoveOp != null, "A child of a VarDefList is not a VarDef"); 

                groupByOp.Keys.Clear(nodeToMoveOp.Var); 
                groupByOp.Outputs.Clear(nodeToMoveOp.Var); 
            }
 
            // return the modified subtree
            return projectNode;
        }
 
        /// 
        /// Simply flatten out every var in the keys, and return a new DistinctOp 
        ///  
        /// DistinctOp
        /// Current subtree 
        /// 
        public override Node Visit(DistinctOp op, Node n) {
            VisitChildren(n);
 
            // Simply flatten out all the Vars
            VarVec newKeys = FlattenVarSet(op.Keys); 
            n.Op = m_command.CreateDistinctOp(newKeys); 
            return n;
        } 

        /// 
        /// GroupByOp
        /// 
        /// Again, VisitChildren - for the Keys and Properties VarDefList nodes - does
        /// the real work. 
        /// 
        /// The "Keys" and the "OutputVars" varsets are updated to flatten out
        /// references to any structured Vars. 
        ///
        /// NOTE: If the Keys of the GroupByOp contain references to entitytypes -
        /// those need special handling - the flattening that we describe may not be enough
        ///  
        /// 
        ///  
        /// new subtree 
        public override Node Visit(GroupByOp op, Node n) {
            VisitChildren(n); 

            // update the output Vars and the key vars with the right sets
            VarVec newKeys = FlattenVarSet(op.Keys);
            VarVec newOutputs = FlattenVarSet(op.Outputs); 

            if (newKeys != op.Keys || newOutputs != op.Outputs) { 
                n.Op = m_command.CreateGroupByOp(newKeys, newOutputs); 
            }
 
            Node newResult = EliminateInternalConstantAndNullGroupByKeys(n);
            return newResult;
        }
 
        /// 
        /// ProjectOp 
        /// 
        /// The computedVars (the VarDefList) are processed via the VisitChildren() call
        /// We then try to update the "Vars" property to flatten out any structured 
        /// type Vars - if a new VarSet is produced, then the ProjectOp is cloned
        /// 
        /// 
        ///  
        /// new subtree
        public override Node Visit(ProjectOp op, Node n) { 
            VisitChildren(n); 

            // update the output Vars with the right set of information 
            VarVec newVars = FlattenVarSet(op.Outputs);

            if (op.Outputs != newVars) {
                // If the set of vars is empty, that means we didn;t need any of the Vars 
                if (newVars.IsEmpty) {
                    return n.Child0; 
                } 
                n.Op = m_command.CreateProjectOp(newVars);
            } 
            return n;
        }

        ///  
        /// ScanTableOp
        /// 
        /// Visit a scanTable Op. Flatten out the table's record into one column 
        /// for each field. Additionally, set up the VarInfo map appropriately
        ///  
        /// 
        /// 
        /// new subtree
        public override Node Visit(ScanTableOp op, Node n) { 

            Var columnVar = op.Table.Columns[0]; 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(columnVar.Type); 
            md.RowType newRowType = typeInfo.FlattenedType;
 
            List properties = new List();
            List keyProperties = new List();
            HashSet declaredProps = new HashSet();
            foreach (md.EdmProperty p in TypeHelpers.GetAllStructuralMembers(columnVar.Type.EdmType)) { 
                declaredProps.Add(p.Name);
            } 
            foreach (md.EdmProperty p in newRowType.Properties) { 
                if (declaredProps.Contains(p.Name)) {
                    properties.Add(p); 
                }
            }
            foreach (PropertyRef pref in typeInfo.GetKeyPropertyRefs()) {
                md.EdmProperty p = typeInfo.GetNewProperty(pref); 
                keyProperties.Add(p);
            } 
 
            //
            // Create a flattened table definition, and a table with that definiton; 
            //
            TableMD newTableMD = m_command.CreateFlatTableDefinition(properties, keyProperties, op.Table.TableMetadata.Extent);
            Table newTable = m_command.CreateTableInstance(newTableMD);
 
            VarInfo varInfo = m_varInfoMap.CreateStructuredVarInfo(columnVar, newRowType, newTable.Columns, properties);
 
            n.Op = m_command.CreateScanTableOp(newTable); 
            return n;
        } 

        /// 
        /// Get the *single" var produced by the subtree rooted at this node.
        /// Returns null, if the node produces more than one var, or less than one 
        /// 
        /// the node 
        /// the single var produced by the node 
        internal static Var GetSingletonVar(Node n) {
            switch (n.Op.OpType) { 
                case OpType.Project: {
                        ProjectOp projectOp = (ProjectOp)n.Op;
                        return (projectOp.Outputs.Count == 1) ? projectOp.Outputs.First : null;
                    } 
                case OpType.ScanTable: {
                        ScanTableOp tableOp = (ScanTableOp)n.Op; 
                        return (tableOp.Table.Columns.Count == 1) ? tableOp.Table.Columns[0] : null; 
                    }
 
                case OpType.Filter:
                case OpType.SingleRow:
                case OpType.Sort:
                case OpType.ConstrainedSort: 
                    return GetSingletonVar(n.Child0);
 
                case OpType.UnionAll: 
                case OpType.Intersect:
                case OpType.Except: { 
                        SetOp setOp = (SetOp)n.Op;
                        return (setOp.Outputs.Count == 1) ? setOp.Outputs.First : null;
                    }
 
                case OpType.Unnest: {
                        UnnestOp unnestOp = (UnnestOp)n.Op; 
                        return unnestOp.Table.Columns.Count == 1 ? unnestOp.Table.Columns[0] : null; 
                    }
 
                case OpType.Distinct: {
                        DistinctOp distinctOp = (DistinctOp)n.Op;
                        return (distinctOp.Keys.Count == 1) ? distinctOp.Keys.First : null;
                    } 

                default: 
                    return null; 
            }
        } 

        /// 
        /// ScanViewOp
        /// 
        /// Flatten out the view definition, and return that after
        /// the appropriate remapping 
        ///  
        /// the ScanViewOp
        /// current subtree 
        /// the flattened view definition
        public override Node Visit(ScanViewOp op, Node n) {
            //
            // Get the "single" var produced by the input 
            //
            Var inputVar = GetSingletonVar(n.Child0); 
            PlanCompiler.Assert(inputVar != null, "cannot identify Var for the input node to the ScanViewOp"); 
            // and the table should have exactly one column
            PlanCompiler.Assert(op.Table.Columns.Count == 1, "table for scanViewOp has more than on column?"); 
            Var columnVar = op.Table.Columns[0];

            Node definingNode = VisitNode(n.Child0);
 
            VarInfo varInfo;
            if (!m_varInfoMap.TryGetVarInfo(inputVar, out varInfo)) { 
                PlanCompiler.Assert(false, "didn't find inputVar for scanViewOp?"); 
            }
            // we must be dealing with a structured column here 
            StructuredVarInfo svarInfo = (StructuredVarInfo)varInfo;

            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(columnVar.Type);
 
            // if this view does not represent an entityset, then we're pretty much
            // done. We simply add a mapping from the columnVar to the list of flattened 
            // vars produced by the underlying projectOp 
            m_varInfoMap.CreateStructuredVarInfo(columnVar, svarInfo.NewType, svarInfo.NewVars, svarInfo.Fields);
            return definingNode; 
        }

        /// 
        /// Convert a SortOp. Specifically, walk the SortKeys, and expand out 
        /// any Structured type Var references
        ///  
        /// the sortOp 
        /// the current node
        /// new subtree 
        public override Node Visit(SortOp op, Node n) {
            VisitChildren(n);

            List newSortKeys = HandleSortKeys(op.Keys); 

            if (newSortKeys != op.Keys) { 
                n.Op = m_command.CreateSortOp(newSortKeys); 
            }
            return n; 
        }

        /// 
        /// UnnestOp 
        ///
        /// Converts an UnnestOp to the right shape. 
        /// Flattens out the Table instance, and updates 
        /// 
        ///  
        /// 
        /// new subtree
        public override Node Visit(UnnestOp op, Node n) {
            // Visit the children first 
            VisitChildren(n);
 
            md.TypeUsage newType; 

            if (n.HasChild0) { 
                Node chi = n.Child0;
                VarDefOp varDefOp = chi.Op as VarDefOp;

                if (null != varDefOp) { 
                    if (TypeUtils.IsStructuredType(varDefOp.Var.Type)
                     || TypeUtils.IsCollectionType(varDefOp.Var.Type)) { 
                        List newChildren = new List(); 

                        FlattenComputedVar((ComputedVar)varDefOp.Var, chi, out newChildren, out newType); 
                        PlanCompiler.Assert(newChildren.Count == 1, "Flattening unnest var produced more than one Var");
                        n.Child0 = newChildren[0];
                    }
                } 
            }
 
            // Create a new unnestVar 
            VarInfo unnestVarInfo;
            Var newUnnestVar; 
            if (!m_varInfoMap.TryGetVarInfo(op.Var, out unnestVarInfo)) {
                throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.WrongVarType);
            }
            else if (!unnestVarInfo.IsCollectionType) { 
                throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.WrongVarType);
            } 
            else { 
                newUnnestVar = ((CollectionVarInfo)unnestVarInfo).NewVar;
            } 

            //
            // Flatten out the table
            // Create a flattened table definition, and a table with that definiton; 
            //
            Table newTable = op.Table; 
            Var columnVar = op.Table.Columns[0]; 
            if (TypeUtils.IsStructuredType(columnVar.Type)) {
                TypeInfo typeInfo = m_typeInfo.GetTypeInfo(columnVar.Type); 
                md.RowType newRowType = typeInfo.FlattenedType;
                TableMD newTableMD = m_command.CreateFlatTableDefinition(newRowType);

                newTable = m_command.CreateTableInstance(newTableMD); 
                VarInfo outputVarInfo = m_varInfoMap.CreateStructuredVarInfo(columnVar, newRowType, newTable.Columns, newRowType.Properties.ToList());
            } 
 
            // Create a new UnnestOp
            n.Op = m_command.CreateUnnestOp(newUnnestVar, newTable); 
            return n;
        }

        #region SetOps 

        ///  
        /// SetOp 
        ///
        /// Converts all SetOps - union/intersect/except. 
        /// Calls VisitChildren() to do the bulk of the work. After that, the VarMaps
        /// need to be updated to reflect the removal of any structured Vars
        /// 
        ///  
        /// 
        /// new subtree 
        protected override Node VisitSetOp(SetOp op, Node n) { 
            VisitChildren(n);
 
            // Now walk through the first VarMap, and identify the Vars that are needed
            for (int i = 0; i < op.VarMap.Length; i++) {
                List newComputedVars;
                op.VarMap[i] = FlattenVarMap(op.VarMap[i], out newComputedVars); 
                if (newComputedVars != null) {
                    n.Children[i] = FixupSetOpChild(n.Children[i], op.VarMap[i], newComputedVars); 
                } 
            }
 
            // now get the set of Vars that we will actually need
            op.Outputs.Clear();
            foreach (Var v in op.VarMap[0].Keys) {
                op.Outputs.Set(v); 
            }
            return n; 
        } 

        ///  
        /// Fixes up a SetOp child.
        /// As part of Var flattening, it may so happen that the outer var in the VarMap
        /// may require a property that has no corresponding analog in the inner Var
        /// This logically implies that the corresponding inner property is null. H 
        /// What we do here is to throw an additional projectOp over the setOp child to
        /// add computed Vars (whose defining expressions are null constants) for each 
        /// of those missing properties 
        /// 
        /// one child of the setop 
        /// the varmap for this child
        /// list of new Vars produced
        /// new node for the setOpchild (if any)
        private Node FixupSetOpChild(Node setOpChild, VarMap varMap, List newComputedVars) { 
            PlanCompiler.Assert(null != setOpChild, "null setOpChild?");
            PlanCompiler.Assert(null != varMap, "null varMap?"); 
            PlanCompiler.Assert(null != newComputedVars, "null newComputedVars?"); 

            // Walk through the list of Vars that have no inner analog, and create 
            // a computed Var for each of them
            VarVec newVarSet = m_command.CreateVarVec();
            foreach (KeyValuePair kv in varMap) {
                newVarSet.Set(kv.Value); 
            }
 
            List varDefOpNodes = new List(); 
            foreach (Var v in newComputedVars) {
                VarDefOp varDefOp = m_command.CreateVarDefOp(v); 
                Node varDefOpNode = m_command.CreateNode(varDefOp, CreateNullConstantNode(v.Type));
                varDefOpNodes.Add(varDefOpNode);
            }
            Node varDefListNode = m_command.CreateNode(m_command.CreateVarDefListOp(), varDefOpNodes); 
            ProjectOp projectOp = m_command.CreateProjectOp(newVarSet);
            Node projectNode = m_command.CreateNode(projectOp, setOpChild, varDefListNode); 
            return projectNode; 
        }
 
        /// 
        /// Flattens out a VarMap.
        ///
        /// Any structured type Vars are expanded out; and collection type Vars 
        /// are replaced by new Vars that reflect the new collection types.
        /// 
        /// There is one special case when dealing with Structured type Vars - 
        /// the output and input vars may no longer be 1-1; specifically, there
        /// may be no input Var corresponding to an output var. In such cases, we 
        /// build up a new ComputedVar (with an expected value of null), and use that
        /// in place of the inner var. A subsequent stage will inspect the list of
        /// new ComputedVars, and perform the appropriate fixups
        ///  
        /// The VarMap to fixup
        /// list of any new computedVars that are created 
        /// a new VarMap 
        private VarMap FlattenVarMap(VarMap varMap, out List newComputedVars) {
            newComputedVars = null; 

            VarMap newVarMap = new VarMap();
            foreach (KeyValuePair kv in varMap) {
                VarInfo innerVarInfo; 
                VarInfo outerVarInfo;
                // Does the inner var have a Varinfo - if not, simply add it 
                // to the VarMap, and continue. 
                // Otherwise, the Outer var must have a VarInfo too
                if (!m_varInfoMap.TryGetVarInfo(kv.Value, out innerVarInfo)) { 
                    newVarMap.Add(kv.Key, kv.Value);
                }
                else {
                    // get my own var info 
                    if (!m_varInfoMap.TryGetVarInfo(kv.Key, out outerVarInfo)) {
                        outerVarInfo = FlattenSetOpVar((SetOpVar)kv.Key); 
                    } 

                    // If this Var represents a collection type, then simply 
                    // replace the singleton Var
                    if (outerVarInfo.IsCollectionType) {
                        newVarMap.Add(((CollectionVarInfo)outerVarInfo).NewVar, ((CollectionVarInfo)innerVarInfo).NewVar);
                    } 
                    else { // structured type
                        StructuredVarInfo outerSvarInfo = (StructuredVarInfo)outerVarInfo; 
                        StructuredVarInfo innerSvarInfo = (StructuredVarInfo)innerVarInfo; 

                        // walk through each property, and find the innerVar corresponding 
                        // to that property
                        foreach (md.EdmProperty prop in outerSvarInfo.Fields) {
                            Var outerVar;
                            Var innerVar; 
                            bool ret = outerSvarInfo.TryGetVar(prop, out outerVar);
                            PlanCompiler.Assert(ret, "Could not find VarInfo for prop " + prop.Name); 
 
                            if (!innerSvarInfo.TryGetVar(prop, out innerVar)) {
                                // we didn't find a corresponding innerVar. 
                                innerVar = m_command.CreateComputedVar(outerVar.Type);
                                if (newComputedVars == null) {
                                    newComputedVars = new List();
                                } 
                                newComputedVars.Add((ComputedVar)innerVar);
                            } 
                            newVarMap.Add(outerVar, innerVar); 
                        }
                    } 
                }
            }
            return newVarMap;
        } 

        ///  
        /// Flattens a SetOpVar (used in SetOps). Simply produces a list of 
        /// properties corresponding to each desired property
        ///  
        /// 
        /// 
        private VarInfo FlattenSetOpVar(SetOpVar v) {
            if (TypeUtils.IsCollectionType(v.Type)) { 
                md.TypeUsage newType = GetNewType(v.Type);
                Var newVar = m_command.CreateSetOpVar(newType); 
                return m_varInfoMap.CreateCollectionVarInfo(v, newVar); 
            }
 
            // Get the "new" type for the Var
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(v.Type);
            // Get a list of properties that we think are necessary
            PropertyRefList desiredProperties = m_varPropertyMap[v]; 
            List newVars = new List();
            List newProps = new List(); 
            foreach (PropertyRef p in typeInfo.PropertyRefList) { 
                if (!desiredProperties.Contains(p)) {
                    continue; 
                }
                md.EdmProperty newProperty = typeInfo.GetNewProperty(p);
                newProps.Add(newProperty);
                SetOpVar newVar = m_command.CreateSetOpVar(md.Helper.GetModelTypeUsage(newProperty)); 
                newVars.Add(newVar);
            } 
            VarInfo varInfo = m_varInfoMap.CreateStructuredVarInfo(v, typeInfo.FlattenedType, newVars, newProps); 
            return varInfo;
        } 

        #endregion

        #region DML RelOps 

        // 
        // DML RelOps are technically very simple - we should simply visit the 
        // children. However, I will defer this to when we actually support DML
        // so for now, the default implementation in the basicVisitor is to throw 
        // unimplemented and that's good enough.
        //

        #endregion 

        #endregion 
 
        #region ScalarOp Visitors
 
        /// 
        /// SoftCastOp
        ///
        /// Visit the children first. 
        ///
        /// If this is an entity type, complextype or ref type, simply return the 
        ///   visited child. (Rationale: These must be in the same type hierarchy; or 
        ///   the earlier stages of query would have barfed. And, we end up
        ///   using the same "flat" type for every type in the hierarchy) 
        ///
        /// If this is a scalar type, then simply return the current node
        ///
        /// If this is a collection type, then create a new softcastOp over the input 
        ///  (the collection type may have changed)
        /// 
        /// Otherwise, we're dealing with a record type. Since our earlier 
        /// definitions of equivalence required that equivalent record types must
        /// have the same number of fields, with "promotable" types, and in the same 
        /// order; *and* since we asked for all properties (see PropertyPushdownHelper),
        /// the input must be a NewRecordOp, whose fields line up 1-1 with our fields.
        /// Build up a new NewRecordOp based on the arguments to the input NewRecordOp,
        /// and build up SoftCastOps for any field whose type does not match 
        /// 
        ///  
        ///  
        /// 
        public override Node Visit(SoftCastOp op, Node n) { 
            md.TypeUsage inputTypeUsage = n.Child0.Op.Type;
            md.TypeUsage oldType = op.Type;

            // Always think of your children first 
            VisitChildren(n);
 
            md.TypeUsage newType = GetNewType(oldType); 

            if (md.TypeSemantics.IsRowType(oldType)) { 
                PlanCompiler.Assert(n.Child0.Op.OpType == OpType.NewRecord, "Expected a record constructor here. Found " + n.Child0.Op.OpType + " instead");

                TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(inputTypeUsage);
                TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(op.Type); 

                NewRecordOp newOp = m_command.CreateNewRecordOp(newType); 
 
                List newArgs = new List();
 
                // We have to adjust for when we're supposed to add/remove null sentinels;
                // it is entirely possible that we may need to add multiple null sentinel
                // columns (See SQLBUDT #549068 for an example).
                IEnumerator outputs = newOp.Properties.GetEnumerator(); 
                int outputPropertyCount = newOp.Properties.Count;
                outputs.MoveNext(); 
 
                IEnumerator inputs = n.Child0.Children.GetEnumerator();
                int inputPropertyCount = n.Child0.Children.Count; 
                inputs.MoveNext();

                // We know that all Null Sentinels are added on the left side, so we'll
                // just keep adding them until we have the same number of properties on 
                // both the input and the output...
                while (inputPropertyCount < outputPropertyCount) { 
                    PlanCompiler.Assert(outputTypeInfo.HasNullSentinelProperty && !inputTypeInfo.HasNullSentinelProperty, "NullSentinelProperty mismatch on input?"); 

                    // make up a null sentinel; the output requires it. 
                    newArgs.Add(CreateNullSentinelConstant());
                    outputs.MoveNext();
                    outputPropertyCount--;
                } 

                // Likewise, we'll just drop any null sentinel columns from the input until 
                // we have the same number of columns... 
                while (inputPropertyCount > outputPropertyCount) {
                    PlanCompiler.Assert(!outputTypeInfo.HasNullSentinelProperty && inputTypeInfo.HasNullSentinelProperty, "NullSentinelProperty mismatch on output?"); 

                    // remove the null sentinel; the output doesn't require it.
                    inputs.MoveNext();
                    inputPropertyCount--; 
                }
 
                do { 
                    md.EdmProperty p = outputs.Current;
                    Node arg = BuildSoftCast(inputs.Current, md.Helper.GetModelTypeUsage(p)); 
                    newArgs.Add(arg);
                    outputs.MoveNext();
                }
                while (inputs.MoveNext()); 

                Node newNode = m_command.CreateNode(newOp, newArgs); 
                return newNode; 
            }
            else if (md.TypeSemantics.IsCollectionType(oldType)) { 
                //
                // Our collection type may have changed - 'coz the
                // element type of the collection may have changed.
                // Simply build up a new castOp (if necessary) 
                //
                return BuildSoftCast(n.Child0, newType); 
            } 
            else if (md.TypeSemantics.IsPrimitiveType(oldType)) {
                // How primitive! Well, the Prime Directive prohibits me 
                // from doing much with these.
                return n;
            }
            else { 
                PlanCompiler.Assert(md.TypeSemantics.IsNominalType(oldType) ||
                    md.TypeSemantics.IsReferenceType(oldType), 
                    "Gasp! Not a nominal type or even a reference type"); 
                // I'm dealing with a nominal type (entity, complex type) or
                // a reference type here. Every type in the same hierarchy 
                // must have been rationalized into the same type, and so, we
                // won't need to do anything special
                PlanCompiler.Assert(Command.EqualTypes(newType, n.Child0.Op.Type),
                    "Types are not equal"); 
                return n.Child0;
            } 
        } 

        ///  
        /// CaseOp
        ///
        /// Special handling
        /// 
        /// If the case statement is of one of the following two shapes:
        ///     (1) case when X then NULL else Y, or 
        ///     (2) case when X then Y else NULL, 
        /// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same,
        /// it gets rewritten into:  Y', where Y's null sentinel N' is: 
        ///     (1) case when X then NULL else N, or
        /// where N is Y's null sentinel.
        /// 
        /// the CaseOp 
        /// corresponding node
        /// new subtree 
        public override Node Visit(CaseOp op, Node n) { 
            // Before visiting the children, check whether the case statment can be optimized
            bool thenClauseIsNull; 
            bool canSimplifyPrecheck = PlanCompilerUtil.IsRowTypeCaseOpWithNullability(op, n, out thenClauseIsNull);

            VisitChildren(n);
 
            if (canSimplifyPrecheck)  {
                Node rewrittenNode; 
                if (TryRewriteCaseOp(n, thenClauseIsNull, out rewrittenNode)) { 
                    return rewrittenNode;
                } 
            }

            //
            // If the CaseOp returns a simple type, then we don't need to do 
            // anything special.
            // 
            // Bug 480780: We must perform further processing, if the result 
            // type is not a scalar
            // 

            // If the CaseOp returns a collection, then we need to create a
            // new CaseOp of the new and improved collection type.
            if (TypeUtils.IsCollectionType(op.Type)) { 
                md.TypeUsage newType = GetNewType(op.Type);
 
                n.Op = m_command.CreateCaseOp(newType); 
                return n;
            } 
            else if (TypeUtils.IsStructuredType(op.Type)) {
                // We've got a structured type, so the CaseOp is flattened out into
                // a NewRecordOp via the FlattenCaseOp method.
                PropertyRefList desiredProperties = m_nodePropertyMap[n]; 
                Node newNode = FlattenCaseOp(op, n, m_typeInfo.GetTypeInfo(op.Type), desiredProperties);
                return newNode; 
            } 
            else {
                return n; 
            }
        }

        ///  
        /// Given a case statement of one of the following two shapes:
        ///     (1) case when X then NULL else Y, or 
        ///     (2) case when X then Y else NULL, 
        /// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same,
        /// it rewrittes into:  Y', where Y's null sentinel N' is: 
        ///     (1) case when X then NULL else N, or
        /// where N is Y's null sentinel.
        ///
        /// The rewrite only happens if: 
        ///     (1) Y has null sentinel, and
        ///     (2) Y is a NewRecordOp. 
        ///  
        /// 
        ///  
        /// 
        /// Whether a rewrite was done
        private bool TryRewriteCaseOp(Node n, bool thenClauseIsNull, out Node rewrittenNode) {
            rewrittenNode = n; 

            //If the type of the case op does not have a null sentinel, we can't do the rewrite. 
            if (!m_typeInfo.GetTypeInfo(n.Op.Type).HasNullSentinelProperty) { 
                return false;
            } 

            Node resultNode = thenClauseIsNull ? n.Child2 : n.Child1;
            if (resultNode.Op.OpType != OpType.NewRecord) {
                return false; 
            }
 
            //Rewrite the null sentinel, which is the first child of the resultNode 
            Node currentNullSentinel = resultNode.Child0;
            md.TypeUsage integerType = this.m_command.IntegerType; 
            PlanCompiler.Assert(currentNullSentinel.Op.Type.EdmEquals(integerType), "Column that is expected to be a null sentinel is not of Integer type.");

            CaseOp newCaseOp = m_command.CreateCaseOp(integerType);
            List children = new List(3); 

            //The the 'when' from the case statement 
            children.Add(n.Child0); 

            Node nullSentinelNullNode = m_command.CreateNode(m_command.CreateNullOp(integerType)); 
            Node nullSentinelThenNode = thenClauseIsNull ? nullSentinelNullNode : currentNullSentinel;
            Node nullSentinelElseNode = thenClauseIsNull ? currentNullSentinel : nullSentinelNullNode;
            children.Add(nullSentinelThenNode);
            children.Add(nullSentinelElseNode); 

            //Use the case op as a new null sentinel 
            resultNode.Child0 = m_command.CreateNode(newCaseOp, children); 

            rewrittenNode = resultNode; 
            return true;
        }

        ///  
        /// Flattens a CaseOp - Specifically, if the CaseOp returns a structuredtype,
        /// then the CaseOp is broken up so that we build up a "flat" record constructor 
        /// for that structured type, with each argument to the record constructor being 
        /// a (scalar) CaseOp.  For example:
        /// 
        ///     Case when b1 then e1 else e2 end
        ///
        /// gets translated into:
        /// 
        ///     RecordOp(case when b1 then e1.a else e2.a end,
        ///              case when b1 then e1.b else e2.b end, 
        ///              ...) 
        ///
        /// The property extraction is optimized by producing only those properties 
        /// that have actually been requested.
        /// 
        /// the CaseOp
        /// Node corresponding to the CaseOp 
        /// Information about the type
        /// Set of properties desired 
        ///  
        private Node FlattenCaseOp(CaseOp op, Node n, TypeInfo typeInfo, PropertyRefList desiredProperties) {
            // Build up a type constructor - with only as many fields filled in 
            // as are desired.
            List fieldTypes = new List();
            List fieldValues = new List();
 
            foreach (PropertyRef pref in typeInfo.PropertyRefList) {
                // Is this property desired later? 
                if (!desiredProperties.Contains(pref)) { 
                    continue;
                } 
                md.EdmProperty property = typeInfo.GetNewProperty(pref);

                // Build up an accessor for this property across each when/then clause
                List caseChildren = new List(); 
                for (int i = 0; i < n.Children.Count - 1; ) {
                    Node whenNode = Copy(n.Children[i]); 
                    caseChildren.Add(whenNode); 
                    i++;
 
                    Node propNode = BuildAccessorWithNulls(n.Children[i], property);
                    caseChildren.Add(propNode);
                    i++;
                } 
                Node elseNode = BuildAccessorWithNulls(n.Children[n.Children.Count - 1], property);
                caseChildren.Add(elseNode); 
 
                Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(md.Helper.GetModelTypeUsage(property)), caseChildren);
 
                fieldTypes.Add(property);
                fieldValues.Add(caseNode);
            }
 
            NewRecordOp newRec = m_command.CreateNewRecordOp(typeInfo.FlattenedTypeUsage, fieldTypes);
            return m_command.CreateNode(newRec, fieldValues); 
        } 

        ///  
        /// CollectOp
        ///
        /// Nothing much to do - simply update the result type
        ///  
        /// the NestOp
        /// corresponding node 
        /// new subtree 
        public override Node Visit(CollectOp op, Node n) {
            VisitChildren(n); 
            // simply update the desired type
            n.Op = m_command.CreateCollectOp(GetNewType(op.Type));
            return n;
        } 

        ///  
        /// ComparisonOp 
        ///
        /// If the inputs to the comparisonOp are Refs/records/entitytypes, then 
        /// we need to flatten these out. Of course, the only reasonable comparisons
        /// should be EQ and NE
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(ComparisonOp op, Node n) { 
            md.TypeUsage child0Type = ((ScalarOp)n.Child0.Op).Type;
            md.TypeUsage child1Type = ((ScalarOp)n.Child1.Op).Type; 

            if (!TypeUtils.IsStructuredType(child0Type)) {
                return VisitScalarOpDefault(op, n);
            } 

            VisitChildren(n); // visit the children first 
 
            // We're now dealing with a structured type
            PlanCompiler.Assert(!(md.TypeSemantics.IsComplexType(child0Type) || md.TypeSemantics.IsComplexType(child1Type)), "complex type?"); // cannot be a complex type 
            PlanCompiler.Assert(op.OpType == OpType.EQ || op.OpType == OpType.NE, "non-equality comparison of structured types?");

            //
            // Strictly speaking, we should be able to use the typeinfo of either of the arguments. 
            // However, as things stand today, we do have scenarios where the types on the
            // two sides (records mainly) are equivalent, but not identical. This non-identicality 
            // may involve the field types being different, the field names being different etc. - but 
            // we may be assured that the order of the field types is fixed.
            // 
            TypeInfo child0TypeInfo = m_typeInfo.GetTypeInfo(child0Type);
            TypeInfo child1TypeInfo = m_typeInfo.GetTypeInfo(child1Type);
            List properties1;
            List properties2; 
            List values1;
            List values2; 
 
            // get a list of the relevant properties and values from each of the children
 
            GetPropertyValues(child0TypeInfo, OperationKind.Equality, n.Child0, false, out properties1, out values1);
            GetPropertyValues(child1TypeInfo, OperationKind.Equality, n.Child1, false, out properties2, out values2);

            PlanCompiler.Assert((properties1.Count == properties2.Count) && (values1.Count == values2.Count), "different shaped structured types?"); 

            // Build up an and-chain of comparison ops on the property values 
            Node andNode = null; 
            for (int i = 0; i < values1.Count; i++) {
                ComparisonOp newCompOp = m_command.CreateComparisonOp(op.OpType); 
                Node newCompNode = m_command.CreateNode(newCompOp, values1[i], values2[i]);
                if (null == andNode)
                    andNode = newCompNode;
                else 
                    andNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And), andNode, newCompNode);
            } 
            return andNode; 
        }
 
        /// 
        /// ConditionalOp
        ///
        /// IsNull requires special handling. 
        /// 
        ///  
        ///  
        /// 
        public override Node Visit(ConditionalOp op, Node n) { 
            if (op.OpType != OpType.IsNull) {
                return VisitScalarOpDefault(op, n);
            }
 
            //
            // Special handling for IS NULL ops on structured types 
            // 
            // For structured types, we simply convert this into an AND chain of
            // IS NULL predicates, one for each property. There are a couple of 
            // optimizations that we perform.
            //
            // For entity types, we simply perfom the IS NULL operations on the
            // key attributes alone. 
            //
            // Complex types must have a typeid property - the isnull is pushed to the 
            // typeid property 
            //
            // We do NOT support IsNull for Collections 
            //

            md.TypeUsage childOpType = ((ScalarOp)n.Child0.Op).Type;
 
            // Special cases are for structured types only
            if (!TypeUtils.IsStructuredType(childOpType)) { 
                return VisitScalarOpDefault(op, n); 
            }
 
            // visit the children first
            VisitChildren(n);

            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(childOpType); 

            // Otherwise, build up an and-chain of is null checks for each appropriate 
            // property - which should consist only of key properties for Entity types. 
            List properties = null;
            List values = null; 
            GetPropertyValues(typeInfo, OperationKind.IsNull, n.Child0, false, out properties, out values);

            PlanCompiler.Assert(properties.Count == values.Count && properties.Count > 0, "No properties returned from GetPropertyValues(IsNull)?");
 
            Node andNode = null;
            foreach (Node propertyValue in values) { 
                Node isNullNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.IsNull), propertyValue); 
                if (andNode == null)
                    andNode = isNullNode; 
                else
                    andNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And), andNode, isNullNode);
            }
            return andNode; 
        }
 
        ///  
        /// Convert a ConstrainedSortOp. Specifically, walk the SortKeys, and expand out
        /// any Structured type Var references 
        /// 
        /// the constrainedSortOp
        /// the current node
        /// new subtree 
        public override Node Visit(ConstrainedSortOp op, Node n) {
            VisitChildren(n); 
 
            List newSortKeys = HandleSortKeys(op.Keys);
 
            if (newSortKeys != op.Keys) {
                n.Op = m_command.CreateConstrainedSortOp(newSortKeys, op.WithTies);
            }
            return n; 
        }
 
        ///  
        /// GetEntityKeyOp
        ///  
        /// 
        /// 
        /// 
        public override Node Visit(GetEntityRefOp op, Node n) { 
            return FlattenGetKeyOp(op, n);
        } 
 
        /// 
        /// GetRefKeyOp 
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(GetRefKeyOp op, Node n) {
            return FlattenGetKeyOp(op, n); 
        } 

        ///  
        /// GetEntityKeyOp/GetRefKeyOp common handling
        ///
        /// In either case, get the "key" properties from the input entity/ref, and
        /// build up a record constructor from these values 
        /// 
        /// the GetRefKey/GetEntityKey op 
        /// current subtree 
        /// new expression subtree
        private Node FlattenGetKeyOp(ScalarOp op, Node n) { 
            PlanCompiler.Assert(op.OpType == OpType.GetEntityRef || op.OpType == OpType.GetRefKey, "Expecting GetEntityRef or GetRefKey ops");

            TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(((ScalarOp)n.Child0.Op).Type);
            TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(op.Type); 

            // Visit the child - will flatten out the input ref/entity 
            VisitChildren(n); 

            // Get "key" properties (and the corresponding values) from the input 
            List inputFieldTypes;
            List inputFieldValues;

            // Get the key properties for GetRefKey; get the Identity properties 
            // for GetEntityRef
            if (op.OpType == OpType.GetRefKey) { 
                GetPropertyValues(inputTypeInfo, OperationKind.GetKeys, n.Child0, false /* ignore missing props */, out inputFieldTypes, out inputFieldValues); 
            }
            else { 
                PlanCompiler.Assert(op.OpType == OpType.GetEntityRef,
                    "Expected OpType.GetEntityRef: Found " + op.OpType);
                GetPropertyValues(inputTypeInfo, OperationKind.GetIdentity, n.Child0, false, out inputFieldTypes, out inputFieldValues);
            } 

            if (outputTypeInfo.HasNullSentinelProperty && !inputTypeInfo.HasNullSentinelProperty) { 
                // Add a null sentinel column, the input doesn't have one but the output requires it. 
                inputFieldValues.Insert(0,CreateNullSentinelConstant());
            } 

            // create an appropriate record constructor
            List outputFieldTypes = new List(outputTypeInfo.FlattenedType.Properties);
            PlanCompiler.Assert(inputFieldValues.Count == outputFieldTypes.Count, "fieldTypes.Count mismatch?"); 

            NewRecordOp rec = m_command.CreateNewRecordOp(outputTypeInfo.FlattenedTypeUsage, outputFieldTypes); 
            Node newNode = m_command.CreateNode(rec, inputFieldValues); 
            return newNode;
        } 

        /// 
        /// NewMultisetOp
        /// 
        /// For now, all it does is to visit its children
        /// and update the collection type 
        ///  
        /// the NewMultisetOp
        /// corresponding node 
        /// new subtree
        public override Node Visit(NewMultisetOp op, Node n) {
            // Visit my children first
            VisitChildren(n); 
            // then simply, update my type.
            n.Op = m_command.CreateNewMultisetOp(GetNewType(op.Type)); 
            return n; 
        }
 
        /// 
        /// Common handler for PropertyOp and RelPropertyOp
        /// 
        ///  
        /// 
        ///  
        ///  
        private Node VisitPropertyOp(Op op, Node n, PropertyRef propertyRef) {
            PlanCompiler.Assert(op.OpType == OpType.Property || op.OpType == OpType.RelProperty, 
                "Unexpected optype: " + op.OpType);

            md.TypeUsage inputType = n.Child0.Op.Type;
            md.TypeUsage outputType = op.Type; 

            // First visit all my children 
            VisitChildren(n); 

            // If the instance is not a structured type (ie) it is a udt, then there 
            // is little for us to do. Simply return
            if (TypeUtils.IsUdt(inputType)) {
                return n;
            } 

            Node newNode = null; 
            TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(inputType); 

            if (TypeUtils.IsStructuredType(outputType)) { 
                TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(outputType);
                List fieldTypes = new List();
                List fieldValues = new List();
                PropertyRefList expectedProperties = m_nodePropertyMap[n]; 

                foreach (PropertyRef npr in outputTypeInfo.PropertyRefList) { 
                    // Is this a property that's desired by my consumers? 
                    if (expectedProperties.Contains(npr)) {
                        PropertyRef newPropRef = npr.CreateNestedPropertyRef(propertyRef); 
                        md.EdmProperty outputNestedProp = outputTypeInfo.GetNewProperty(npr);
                        md.EdmProperty newNestedProp = inputTypeInfo.GetNewProperty(newPropRef);

                        Node field = BuildAccessor(n.Child0, newNestedProp); 
                        if (null != field) {
                            fieldTypes.Add(outputNestedProp); 
                            fieldValues.Add(field); 
                        }
                    } 
                }
                Op newRecordOp = m_command.CreateNewRecordOp(outputTypeInfo.FlattenedTypeUsage, fieldTypes);
                newNode = m_command.CreateNode(newRecordOp, fieldValues);
            } 
            else {
                md.EdmProperty newProp = inputTypeInfo.GetNewProperty(propertyRef); 
                // Build an accessor over the new property 
                newNode = this.BuildAccessorWithNulls(n.Child0, newProp);
            } 
            return newNode;
        }

        ///  
        /// PropertyOp
        /// 
        /// If this is a scalar/collection property, then simply get the appropriate 
        /// field out.
        /// 
        /// Otherwise, build up a record constructor corresponding to the result
        /// type - optimize this by only getting those properties that are needed
        ///
        /// If the instance is not a structured type (ie) it is a UDT, then simply return 
        ///
        ///  
        /// the PropertyOp 
        /// the corresponding node
        /// new subtree 
        public override Node Visit(PropertyOp op, Node n) {
            return VisitPropertyOp(op, n, new SimplePropertyRef(op.PropertyInfo));
        }
 
        /// 
        /// RelPropertyOp. Pick out the appropriate property from the child 
        ///  
        /// 
        ///  
        /// 
        public override Node Visit(RelPropertyOp op, Node n) {
            return VisitPropertyOp(op, n, new RelPropertyRef(op.PropertyInfo));
        } 

        ///  
        /// RefOp 
        ///
        /// Simply convert this into the corresponding record type - with one 
        /// field for each key, and one for the entitysetid
        /// 
        /// 
        ///  
        /// 
        public override Node Visit(RefOp op, Node n) { 
            TypeInfo inputTypeInfo = m_typeInfo.GetTypeInfo(((ScalarOp)n.Child0.Op).Type); 
            TypeInfo outputTypeInfo = m_typeInfo.GetTypeInfo(op.Type);
 
            // visit children now
            VisitChildren(n);

            // Get the list of fields and properties from the input (key) op 
            List inputFields;
            List inputFieldValues; 
            GetPropertyValues(inputTypeInfo, OperationKind.All, n.Child0, false, out inputFields, out inputFieldValues); 

            // Get my property list 
            List outputFields = new List(outputTypeInfo.FlattenedType.Properties);

            // We have to adjust for when we're supposed to remove null sentinels;
            // columns (See SQLBUDT #553534 for an example).  Note that we shouldn't 
            // have to add null sentinels here, since reference types won't be expecting
            // them (the fact that the key is null is good enough...) 
            if (inputTypeInfo.HasNullSentinelProperty && !outputTypeInfo.HasNullSentinelProperty) { 
                while (inputFields.Count > outputFields.Count) {
                    inputFields.RemoveAt(0); 
                    inputFieldValues.RemoveAt(0);
                }
            }
 
            if (outputTypeInfo.HasEntitySetIdProperty) {
                PlanCompiler.Assert(outputFields.Count == inputFields.Count + 1, "Mismatched field count: Expected " + (inputFields.Count + 1) + "; Got " + outputFields.Count); 
                PlanCompiler.Assert(outputFields[0] == outputTypeInfo.EntitySetIdProperty, "OutputField0 must be the entitySetId property"); 

                // Now prepend a value for the entitysetid property and a value for this property 
                int entitySetId = m_typeInfo.GetEntitySetId(op.EntitySet);
                inputFieldValues.Insert(0, m_command.CreateNode(m_command.CreateInternalConstantOp(md.Helper.GetModelTypeUsage(outputTypeInfo.EntitySetIdProperty), entitySetId)));
            }
            else { 
                PlanCompiler.Assert(outputFields.Count == inputFields.Count, "Mismatched field count: Expected " + inputFields.Count + "; Got " + outputFields.Count);
            } 
 
            // now build up a NewRecordConstructor with the appropriate info
            NewRecordOp recOp = m_command.CreateNewRecordOp(outputTypeInfo.FlattenedTypeUsage, outputFields); 
            Node newNode = m_command.CreateNode(recOp, inputFieldValues);

            return newNode;
        } 

        ///  
        /// VarRefOp 
        ///
        /// Replace a VarRef with a copy of the corresponding "Record" constructor 
        /// 
        /// the VarRefOp
        /// the node
        /// new subtree 
        public override Node Visit(VarRefOp op, Node n) {
            // Lookup my VarInfo 
            VarInfo varInfo; 
            if (!m_varInfoMap.TryGetVarInfo(op.Var, out varInfo)) {
                PlanCompiler.Assert(!TypeUtils.IsStructuredType(op.Type), 
                    "No varInfo for a structured type var: Id = " + op.Var.Id + " Type = " + op.Type);
                return n;
            }
            if (varInfo.IsCollectionType) { 
                n.Op = m_command.CreateVarRefOp(((CollectionVarInfo)varInfo).NewVar);
                return n; 
            } 
            else {
                // A very specialized record constructor mechanism for structured type Vars. 
                // We look up the VarInfo corresponding to the Var - which has a set of fields
                // and the corresponding properties that we need to produce

                StructuredVarInfo structuredVarInfo = (StructuredVarInfo)varInfo; 

                NewRecordOp newOp = m_command.CreateNewRecordOp(structuredVarInfo.NewTypeUsage, structuredVarInfo.Fields); 
                List newNodeChildren = new List(); 
                foreach (Var v in varInfo.NewVars) {
                    VarRefOp newVarRefOp = m_command.CreateVarRefOp(v); 
                    newNodeChildren.Add(m_command.CreateNode(newVarRefOp));
                }
                Node newNode = m_command.CreateNode(newOp, newNodeChildren);
                return newNode; 
            }
        } 
 
        #region record construction ops
 
        /// 
        /// Handler for NewEntity
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(NewEntityOp op, Node n) { 
            return FlattenConstructor(op, n);
        } 

        /// 
        /// NewInstanceOp
        ///  
        /// the NewInstanceOp
        /// corresponding node 
        /// new subtree 
        public override Node Visit(NewInstanceOp op, Node n) {
            return FlattenConstructor(op, n); 
        }

        /// 
        /// DiscriminatedNewInstanceOp 
        /// 
        /// the DiscriminatedNewInstanceOp 
        /// corresponding node 
        /// new subtree
        public override Node Visit(DiscriminatedNewEntityOp op, Node n) { 
            return FlattenConstructor(op, n);
        }

        ///  
        /// Given an explicit discriminator value, map to normalized values. Essentially, this allows
        /// a discriminated new instance to coexist with free-floating entities, MEST, etc. which use 
        /// general purpose ordpath type ids (e.g. '0X0X') 
        ///
        /// An example of the normalization is given: 
        ///
        /// CASE
        ///     WHEN discriminator = 'Base' THEN '0X'
        ///     WHEN discriminator = 'Derived1' THEN '0X0X' 
        ///     WHEN discriminator = 'Derived2' THEN '0X1X'
        ///     ELSE '0X2X' -- default case for 'Derived3' 
        ///  
        private Node NormalizeTypeDiscriminatorValues(DiscriminatedNewEntityOp op, Node discriminator) {
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type); 

            CaseOp normalizer = m_command.CreateCaseOp(typeInfo.RootType.TypeIdProperty.TypeUsage);
            List children = new List(op.DiscriminatorMap.TypeMap.Count * 2 - 1);
            for (int i = 0; i < op.DiscriminatorMap.TypeMap.Count; i++) { 
                object discriminatorValue = op.DiscriminatorMap.TypeMap[i].Key;
                md.EntityType type = op.DiscriminatorMap.TypeMap[i].Value; 
                TypeInfo currentTypeInfo = m_typeInfo.GetTypeInfo(md.TypeUsage.Create(type)); 

                Node normalizedDiscriminatorConstant = CreateTypeIdConstant(currentTypeInfo); 
                // for the last type, return the 'then' value
                if (i == op.DiscriminatorMap.TypeMap.Count - 1) {
                    // ELSE normalizedDiscriminatorValue
                    children.Add(normalizedDiscriminatorConstant); 
                }
                else { 
                    // WHEN discriminator = discriminatorValue THEN normalizedDiscriminatorValue 
                    ConstantBaseOp discriminatorValueOp = m_command.CreateConstantOp(md.Helper.GetModelTypeUsage(op.DiscriminatorMap.DiscriminatorProperty.TypeUsage),
                                                                                     discriminatorValue); 
                    Node discriminatorConstant = m_command.CreateNode(discriminatorValueOp);
                    ComparisonOp discriminatorPredicateOp = m_command.CreateComparisonOp(OpType.EQ);
                    Node discriminatorPredicate = m_command.CreateNode(discriminatorPredicateOp, discriminator, discriminatorConstant);
                    children.Add(discriminatorPredicate); 
                    children.Add(normalizedDiscriminatorConstant);
                } 
            } 

            // swap discriminator with case op normalizing the discriminator 
            discriminator = m_command.CreateNode(normalizer, children);
            return discriminator;
        }
 
        /// 
        /// NewRecordOp 
        ///  
        /// the newRecordOp
        /// corresponding node 
        /// new subtree
        public override Node Visit(NewRecordOp op, Node n) {
            return FlattenConstructor(op, n);
        } 

        ///  
        /// Build out an expression corresponding to the entitysetid 
        /// 
        /// the property corresponding to the entitysetid 
        /// the *NewEntity op
        /// 
        private Node GetEntitySetIdExpr(md.EdmProperty entitySetIdProperty, NewEntityBaseOp op) {
            Node entitySetIdNode; 
            md.EntitySet entitySet = op.EntitySet as md.EntitySet;
            if (entitySet != null) { 
                int entitySetId = m_typeInfo.GetEntitySetId(entitySet); 
                InternalConstantOp entitySetIdOp = m_command.CreateInternalConstantOp(md.Helper.GetModelTypeUsage(entitySetIdProperty), entitySetId);
                entitySetIdNode = m_command.CreateNode(entitySetIdOp); 
            }
            else {
                //
                // Not in a view context; simply assume a null entityset 
                //
                entitySetIdNode = CreateNullConstantNode(md.Helper.GetModelTypeUsage(entitySetIdProperty)); 
            } 

            return entitySetIdNode; 
        }

        /// 
        /// Flattens out a constructor into a "flat" record constructor. 
        /// The "flat" record type is looked up for the current constructor's type,
        /// and each property is filled out from the current constructor's fields 
        ///  
        /// The NewRecordOp/NewInstanceOp
        /// The current subtree 
        /// the new subtree
        private Node FlattenConstructor(ScalarOp op, Node n) {
            PlanCompiler.Assert(op.OpType == OpType.NewInstance || op.OpType == OpType.NewRecord || op.OpType == OpType.DiscriminatedNewEntity || op.OpType == OpType.NewEntity,
                "unexpected op: " + op.OpType + "?"); 

            // First visit all my children 
            VisitChildren(n); 

            // Find the new type corresponding to the type 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type);
            md.RowType flatType = typeInfo.FlattenedType;
            NewEntityBaseOp newEntityOp = op as NewEntityBaseOp;
 
            // Identify the fields
            IEnumerable opFields = null; 
            DiscriminatedNewEntityOp discriminatedNewInstanceOp = null; 
            if (op.OpType == OpType.NewRecord) {
                // Get only those fields that I have values for 
                opFields = ((NewRecordOp)op).Properties;
            }
            else if (op.OpType == OpType.DiscriminatedNewEntity) {
                // Get all properties projected by the discriminated new instance op 
                discriminatedNewInstanceOp = (DiscriminatedNewEntityOp)op;
                opFields = discriminatedNewInstanceOp.DiscriminatorMap.Properties; 
            } 
            else {
                // Children align with structural members of type for a standard NewInstanceOp 
                opFields = TypeHelpers.GetAllStructuralMembers(op.Type);
            }

            // Next, walk through each of my field, and flatten out any field 
            // that is structured.
            List newFields = new List(); 
            List newFieldValues = new List(); 

            // 
            // NOTE: we expect the type id property and the entityset id properties
            //       to be at the start of the properties collection.
            //
            // Add a typeid property if we need one 
            //
            if (typeInfo.HasTypeIdProperty) { 
                newFields.Add(typeInfo.TypeIdProperty); 
                if (null == discriminatedNewInstanceOp) {
                    newFieldValues.Add(CreateTypeIdConstant(typeInfo)); 
                }
                else {
                    // first child in DiscriminatedNewInstanceOp is discriminator/typeid
                    Node discriminator = n.Children[0]; 

                    if (null == typeInfo.RootType.DiscriminatorMap) { 
                        // if there are multiple sets (or free-floating constructors) for this type 
                        // hierarchy, normalize the discriminator value to expose the standard
                        // '0X' style values 
                        discriminator = NormalizeTypeDiscriminatorValues(discriminatedNewInstanceOp, discriminator);
                    }

                    newFieldValues.Add(discriminator); 
                }
            } 
 
            //
            // Add an entitysetid property if we need one 
            //
            if (typeInfo.HasEntitySetIdProperty) {
                newFields.Add(typeInfo.EntitySetIdProperty);
 
                PlanCompiler.Assert(newEntityOp != null, "unexpected optype:" + op.OpType);
                Node entitySetIdNode = GetEntitySetIdExpr(typeInfo.EntitySetIdProperty, newEntityOp); 
 
                // Get the entity-set-id of the "current" entityset
                newFieldValues.Add(entitySetIdNode); 
            }

            // Add a nullability property if we need one
            if (typeInfo.HasNullSentinelProperty) { 
                newFields.Add(typeInfo.NullSentinelProperty);
                newFieldValues.Add(CreateNullSentinelConstant()); 
            } 

            // 
            // first child of discriminatedNewInstanceOp is the typeId; otherwise, the first child is the first property
            //
            int childrenIndex = null == discriminatedNewInstanceOp ? 0 : 1;
 
            foreach (md.EdmMember opField in opFields) {
                Node fieldValue = n.Children[childrenIndex]; 
                if (TypeUtils.IsStructuredType(md.Helper.GetModelTypeUsage(opField))) { 
                    // Flatten out nested type
                    md.RowType nestedFlatType = m_typeInfo.GetTypeInfo(md.Helper.GetModelTypeUsage(opField)).FlattenedType; 

                    // Find offset of opField in top-level flat type
                    int nestedPropertyOffset = typeInfo.RootType.GetNestedStructureOffset(new SimplePropertyRef(opField));
 
                    foreach (md.EdmProperty nestedProperty in nestedFlatType.Properties) {
                        // Try to build up an accessor for this property from the input 
                        Node nestedPropertyValue = BuildAccessor(fieldValue, nestedProperty); 

                        if (null != nestedPropertyValue) { 
                            newFields.Add(flatType.Properties[nestedPropertyOffset]);
                            newFieldValues.Add(nestedPropertyValue);
                        }
 
                        nestedPropertyOffset++;
                    } 
                } 
                else {
                    PropertyRef propRef = new SimplePropertyRef(opField); 
                    md.EdmProperty outputTypeProp = typeInfo.GetNewProperty(propRef);

                    newFields.Add(outputTypeProp);
 
                    newFieldValues.Add(fieldValue);
                } 
 
                childrenIndex++;
            } 

            //
            // We've now handled all the regular properties. Now, walk through all the rel properties -
            // obviously, this only applies for the *NewEntityOps 
            //
            if (newEntityOp != null) { 
                foreach (RelProperty relProp in newEntityOp.RelationshipProperties) { 
                    Node fieldValue = n.Children[childrenIndex];
                    md.RowType nestedFlatType = m_typeInfo.GetTypeInfo(relProp.ToEnd.TypeUsage).FlattenedType; 

                    // Find offset of opField in top-level flat type
                    int nestedPropertyOffset = typeInfo.RootType.GetNestedStructureOffset(new RelPropertyRef(relProp));
 
                    foreach (md.EdmProperty nestedProperty in nestedFlatType.Properties) {
                        // Try to build up an accessor for this property from the input 
                        Node nestedPropertyValue = BuildAccessor(fieldValue, nestedProperty); 

                        if (null != nestedPropertyValue) { 
                            newFields.Add(flatType.Properties[nestedPropertyOffset]);
                            newFieldValues.Add(nestedPropertyValue);
                        }
 
                        nestedPropertyOffset++;
                    } 
                    childrenIndex++; 
                }
            } 

            //
            // So, now we have the list of all fields that should make up the
            // flat type.  Create a new node with them. 
            //
            NewRecordOp newOp = m_command.CreateNewRecordOp(typeInfo.FlattenedTypeUsage, newFields); 
            Node newNode = m_command.CreateNode(newOp, newFieldValues); 

            return newNode; 
        }

        /// 
        /// NullOp 
        ///
        /// If the node represents a null of an entity type it 'flattens' it into a new record, 
        /// with at most one non-null value: for the typeIdProperty, if one is needed. 
        /// If the node represents an null of a non-entity type, no special work is done.
        ///  
        /// The NullOp
        /// The current subtree
        /// the new subtree
        public override Node Visit(NullOp op, Node n) { 
            if (!TypeUtils.IsStructuredType(op.Type)) {
                return n; 
            } 

            // Find the new type corresponding to the type 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type);

            List newFields = new List();
            List newFieldValues = new List(); 

            // Add a typeid property if we need one 
            if (typeInfo.HasTypeIdProperty) { 
                newFields.Add(typeInfo.TypeIdProperty);
                var typeIdType = md.Helper.GetModelTypeUsage(typeInfo.TypeIdProperty); 
                newFieldValues.Add(CreateNullConstantNode(typeIdType));
            }

            NewRecordOp newRecordOp = new NewRecordOp(typeInfo.FlattenedTypeUsage, newFields); 
            return m_command.CreateNode(newRecordOp, newFieldValues);
        } 
 
        #endregion
 
        #region type comparison ops

        /// 
        /// IsOf 
        ///
        /// Convert an IsOf operator into a typeid comparison: 
        /// 
        ///     IsOfOnly(e, T) => e.TypeId == TypeIdValue(T)
        ///     IsOf(e, T)     => e.TypeId like TypeIdValue(T)% escape null 
        ///
        /// 
        /// The IsOfOp to handle
        /// current isof subtree 
        /// new subtree
        public override Node Visit(IsOfOp op, Node n) { 
            // First visit all my children 
            VisitChildren(n);
 
            if (!TypeUtils.IsStructuredType(op.IsOfType)) {
                return n;
            }
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.IsOfType); 
            Node newNode = CreateTypeComparisonOp(n.Child0, typeInfo, op.IsOfOnly);
            return newNode; 
        } 

        ///  
        /// TreatOp
        ///
        ///     TreatOp(e, T) => case when e.TypeId like TypeIdValue(T) then T else null end
        ///  
        /// the TreatOp
        /// the node 
        /// new subtree 
        public override Node Visit(TreatOp op, Node n) {
            // First visit all my children 
            VisitChildren(n);

            //
            // filter out useless treat operations 
            // Treat(subtype-instance as superType)
            // 
            ScalarOp arg = (ScalarOp)n.Child0.Op; 
            if (op.IsFakeTreat ||
                md.TypeSemantics.IsEquivalent(arg.Type, op.Type) || 
                md.TypeSemantics.IsSubTypeOf(arg.Type, op.Type)) {
                return n.Child0;
            }
 
            // When we support UDTs
            if (!TypeUtils.IsStructuredType(op.Type)) { 
                return n; 
            }
 
            //
            // First, convert this into a CaseOp:
            //   case when e.TypeId like TypeIdValue then e else null end
            // 
            TypeInfo typeInfo = m_typeInfo.GetTypeInfo(op.Type);
            Node likeNode = CreateTypeComparisonOp(n.Child0, typeInfo, false); 
            CaseOp caseOp = m_command.CreateCaseOp(typeInfo.FlattenedTypeUsage); 
            Node caseNode = m_command.CreateNode(caseOp, likeNode, n.Child0, CreateNullConstantNode(caseOp.Type));
 
            //
            // Now "flatten" out this Op into a constructor. But only get the
            // desired properties
            // 
            PropertyRefList desiredProperties = m_nodePropertyMap[n];
            Node flattenedCaseNode = FlattenCaseOp(caseOp, caseNode, typeInfo, desiredProperties); 
            return flattenedCaseNode; 
        }
 
        /// 
        /// Create a typeid-comparison operator - more specifically, create an
        /// operator that compares a typeid value with the typeid property of an
        /// input structured type. 
        /// The comparison may be "exact" - in which case we're looking for the exact
        /// type; otherwise, we're looking for any possible subtypes. 
        /// The "exact" variant is used by the IsOfOp (only); the other variant is 
        /// used by IsOfOp and TreatOp
        ///  
        /// The input structured type expression
        /// Augmented type information for the type
        /// Exact comparison?
        /// New comparison expression 
        private Node CreateTypeComparisonOp(Node input, TypeInfo typeInfo, bool isExact) {
            Node typeIdProperty = BuildTypeIdAccessor(input, typeInfo); 
            Node newNode = null; 

            if (isExact) { 
                newNode = CreateTypeEqualsOp(typeInfo, typeIdProperty);
            }
            else {
                if (typeInfo.RootType.DiscriminatorMap != null) { 
                    // where there are explicit discriminator values, LIKE '0X%' pattern does not work...
                    newNode = CreateDisjunctiveTypeComparisonOp(typeInfo, typeIdProperty); 
                } 
                else {
                    Node typeIdConstantNode = CreateTypeIdConstantForPrefixMatch(typeInfo); 
                    LikeOp likeOp = m_command.CreateLikeOp();
                    newNode = m_command.CreateNode(likeOp, typeIdProperty, typeIdConstantNode, CreateNullConstantNode(DefaultTypeIdType));
                }
            } 
            return newNode;
        } 
 
        /// 
        /// Create a filter matching all types in the given hierarchy (typeIdProperty IN typeInfo.Hierarchy) e.g.: 
        ///
        ///     typeIdProperty = 'Base' OR typeIdProperty = 'Derived1' ...
        ///
        /// This is called only for types using DiscriminatorMap (explicit discriminator values) 
        /// 
        ///  
        ///  
        /// type hierarchy check
        private Node CreateDisjunctiveTypeComparisonOp(TypeInfo typeInfo, Node typeIdProperty) { 
            PlanCompiler.Assert(typeInfo.RootType.DiscriminatorMap != null, "should be used only for DiscriminatorMap type checks");
            // collect all non-abstract types in the given hierarchy
            IEnumerable types = typeInfo.GetTypeHierarchy().Where(t => !t.Type.EdmType.Abstract);
 
            // generate a disjunction
            Node current = null; 
            foreach (TypeInfo type in types) { 
                Node typeComparisonNode = CreateTypeEqualsOp(type, typeIdProperty);
                if (null == current) { 
                    current = typeComparisonNode;
                }
                else {
                    current = m_command.CreateNode(m_command.CreateConditionalOp(OpType.Or), current, typeComparisonNode); 
                }
            } 
            if (null == current) { 
                // only abstract types in this hierarchy... no values possible
                current = m_command.CreateNode(m_command.CreateFalseOp()); 
            }
            return current;
        }
 
        /// 
        /// Generates a node of the form typeIdProperty = typeInfo.TypeId 
        ///  
        /// 
        ///  
        /// type equality check
        private Node CreateTypeEqualsOp(TypeInfo typeInfo, Node typeIdProperty) {
            Node typeIdConstantNode = CreateTypeIdConstant(typeInfo);
            ComparisonOp eqCompOp = m_command.CreateComparisonOp(OpType.EQ); 
            Node result = m_command.CreateNode(eqCompOp, typeIdProperty, typeIdConstantNode);
            return result; 
        } 

        #endregion 

        #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