PreProcessor.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / PreProcessor.cs / 3 / PreProcessor.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections.Generic; 
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Linq;
using System.Data.Common;
using md = System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees;
using System.Data.Metadata.Edm; 
using System.Data.Common.Utils; 
//
// The PreProcessor module is responsible for performing any required preprocessing 
// on the tree (and gathering information) before subsequent phases mess with the tree.
// The main aspects of preprocessing we perform here are
//   (a) gathering information about all structured types and entitysets referenced in the
//       query 
//   (b) Normalization of queries. Currently, we only handle scalar subqueries, and these
//       are converted into outer-apply subqueries 
//   (c) Translation of multiset constructors into subqueries of the form 
//       "select a from dual union all select b from dual ..."
// 
namespace System.Data.Query.PlanCompiler
{
    internal class DiscriminatorMapInfo {
        internal EntityTypeBase RootEntityType; 
        internal bool IncludesSubTypes;
        internal ExplicitDiscriminatorMap DiscriminatorMap; 
 
        internal DiscriminatorMapInfo(EntityTypeBase rootEntityType, bool includesSubTypes, ExplicitDiscriminatorMap discriminatorMap)
        { 
            RootEntityType = rootEntityType;
            IncludesSubTypes = includesSubTypes;
            DiscriminatorMap = discriminatorMap;
        } 

        ///  
        /// Merge the discriminatorMap info we just found with what we've already found. 
        ///
        /// In practice, if either the current or the new map is from an OfTypeOnly view, we 
        /// have to avoid the optimizations.
        ///
        /// If we have a new map that is a superset of the current map, then we can just swap
        /// the new map for the current one. 
        ///
        /// If the current map is tha super set of the new one ther's nothing to do. 
        /// 
        /// (Of course, if neither has changed, then we really don't need to look)
        ///  
        internal void Merge(EntityTypeBase neededRootEntityType, bool includesSubtypes, ExplicitDiscriminatorMap discriminatorMap)
        {
            // If what we've found doesn't exactly match what we are looking for we have more work to do
            if (RootEntityType != neededRootEntityType || IncludesSubTypes != includesSubtypes) 
            {
                if (!IncludesSubTypes || !includesSubtypes) 
                { 
                    // If either the original or the new map is from an of-type-only view we can't
                    // merge, we just have to not optimize this case. 
                    DiscriminatorMap = null;

                }
                if (TypeSemantics.IsSubTypeOf(RootEntityType, neededRootEntityType)) 
                {
                    // we're asking for a super type of existing type, and what we had is a proper 
                    // subset of it -we can replace the existing item. 
                    RootEntityType = neededRootEntityType;
                    DiscriminatorMap = discriminatorMap; 
                }
                if (!TypeSemantics.IsSubTypeOf(neededRootEntityType, RootEntityType))
                {
                    // If either the original or the new map is from an of-type-only view we can't 
                    // merge, we just have to not optimize this case.
                    DiscriminatorMap = null; 
                } 
            }
        } 
    }

    /// 
    /// The PreProcessor performs preprocessing of the ITree to facilitate processing 
    /// by later modules.
    ///  
    internal class PreProcessor : BasicOpVisitorOfNode 
    {
        #region private state 
        private PlanCompiler m_compilerState;
        private Command m_command { get { return m_compilerState.Command; } }

        // nested subquery tracking 
        private Stack m_ancestors;
        private Dictionary> m_nodeSubqueries; 
        // current nested view depth (0 for top-level query) 
        private int m_viewNestingLevel;
 
        // track list of referenced types, entitysets and entitycontainers
        private HashSet m_referencedEntityContainers;
        private List m_referencedEntitySets;
        private List m_referencedTypes; 
        private List m_freeFloatingEntityConstructorTypes;
        private HashSet m_typesNeedingNullSentinel; 
 
        // helper for rel properties
        private RelPropertyHelper m_relPropertyHelper; 

        // track discriminator metadata
        private bool m_suppressDiscriminatorMaps;
        private readonly Dictionary m_discriminatorMaps; 
        #endregion
 
        #region constructors 
        private PreProcessor(PlanCompiler planCompilerState)
        { 
            m_compilerState = planCompilerState;
            m_ancestors = new Stack();
            m_nodeSubqueries = new Dictionary>();
            m_viewNestingLevel = 0; 
            m_referencedEntitySets = new List();
            m_referencedTypes = new List(); 
            m_freeFloatingEntityConstructorTypes = new List(); 
            m_referencedEntityContainers = new HashSet();
            m_relPropertyHelper = new RelPropertyHelper(m_command.MetadataWorkspace, m_command.ReferencedRelProperties); 
            m_discriminatorMaps = new Dictionary();
            m_typesNeedingNullSentinel = new HashSet();
        }
        #endregion 

        #region public methods 
        ///  
        /// The driver routine. "Normalizes" the command;
        ///  
        /// plan compiler state
        /// type information about all types/sets referenced in the query
        internal static void Process(PlanCompiler planCompilerState,
            out StructuredTypeInfo typeInfo) 
        {
            PreProcessor preProcessor = new PreProcessor(planCompilerState); 
            preProcessor.Process(); 

            StructuredTypeInfo.Process(planCompilerState.Command, 
                preProcessor.m_referencedTypes,
                preProcessor.m_referencedEntitySets,
                preProcessor.m_freeFloatingEntityConstructorTypes,
                preProcessor.m_suppressDiscriminatorMaps ? null : preProcessor.m_discriminatorMaps, 
                preProcessor.m_relPropertyHelper,
                preProcessor.m_typesNeedingNullSentinel, 
                out typeInfo); 
        }
 
        #endregion

        #region private methods
 
        #region driver
        internal void Process() 
        { 
            m_command.Root = VisitNode(m_command.Root);
            // 
            // Add any Vars that are of structured type - if the Vars aren't
            // referenced via a VarRefOp, we end up losing them...
            //
            foreach (Var v in m_command.Vars) 
            {
                AddTypeReference(v.Type); 
            } 

            // 
            // If we have any "structured" types, then we need to run through NTE
            //
            if (m_referencedTypes.Count > 0)
            { 
                m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NTE);
 
                // 
                // Find any structured types that are projected at the top level, and
                // ensure that we can handle their nullability. 
                //
                PhysicalProjectOp ppOp = (PhysicalProjectOp)m_command.Root.Op; // this better be the case or we have other problems.
                ppOp.ColumnMap.Accept(StructuredTypeNullabilityAnalyzer.Instance, m_typesNeedingNullSentinel);
            } 
        }
        #endregion 
 
        #region private state maintenance
 
        #region type and set information

        /// 
        /// Mark this EntitySet as referenced in the query 
        /// 
        ///  
        private void AddEntitySetReference(EntitySet entitySet) 
        {
            m_referencedEntitySets.Add(entitySet); 
            if (!m_referencedEntityContainers.Contains(entitySet.EntityContainer))
            {
                m_referencedEntityContainers.Add(entitySet.EntityContainer);
            } 
        }
 
        ///  
        /// Mark this type as being referenced in the query, if it is a structured
        /// type or a collection of structured type 
        /// 
        /// type to reference
        private void AddTypeReference(TypeUsage type)
        { 
            if (TypeUtils.IsStructuredType(type) || TypeUtils.IsCollectionType(type))
            { 
                m_referencedTypes.Add(type); 
            }
        } 

        /// 
        /// Get the list of relationshipsets that can hold instances of the given relationshiptype
        /// 
        /// We identify the list of relationshipsets in the current list of entitycontainers that are
        /// of the given type. Since we don't yet support relationshiptype subtyping, this is a little 
        /// easier than the entity version 
        /// 
        /// the relationship type to look for 
        /// the list of relevant relationshipsets
        private List GetRelationshipSets(RelationshipType relType)
        {
            List relSets = new List(); 
            foreach (EntityContainer entityContainer in m_referencedEntityContainers)
            { 
                foreach (EntitySetBase set in entityContainer.BaseEntitySets) 
                {
                    RelationshipSet relSet = set as RelationshipSet; 
                    if (relSet != null &&
                        relSet.ElementType.Equals(relType))
                    {
                        relSets.Add(relSet); 
                    }
                } 
            } 
            return relSets;
        } 

        /// 
        /// Find all entitysets (that are reachable in the current query) that can hold instances that
        /// are *at least* of type "entityType". 
        /// An entityset ES of type T1 can hold instances that are at least of type T2, if one of the following
        /// is true 
        ///   - T1 is a subtype of T2 
        ///   - T2 is a subtype of T1
        ///   - T1 is equal to T2 
        /// 
        /// the desired entity type
        /// list of all entitysets of the desired shape
        private List GetEntitySets(TypeUsage entityType) 
        {
            List sets = new List(); 
            foreach (EntityContainer container in m_referencedEntityContainers) 
            {
                foreach (EntitySetBase baseSet in container.BaseEntitySets) 
                {
                    EntitySet set = baseSet as EntitySet;
                    if (set != null &&
                        (set.ElementType.Equals(entityType.EdmType) || 
                         TypeSemantics.IsSubTypeOf(entityType.EdmType, set.ElementType) ||
                         TypeSemantics.IsSubTypeOf(set.ElementType, entityType.EdmType))) 
                    { 
                        sets.Add(set);
                    } 
                }
            }

            return sets; 
        }
 
        #endregion 

        #region Subquery Handling 
        /// 
        /// Adds a subquery to the list of subqueries for the relOpNode
        /// 
        /// the RelOp node 
        /// the subquery
        private void AddSubqueryToRelOpNode(Node relOpNode, Node subquery) 
        { 
            List nestedSubqueries;
 
            // Create an entry in the map if there isn't one already
            if (!m_nodeSubqueries.TryGetValue(relOpNode, out nestedSubqueries))
            {
                nestedSubqueries = new List(); 
                m_nodeSubqueries[relOpNode] = nestedSubqueries;
            } 
            // add this subquery to the list of currently tracked subqueries 
            nestedSubqueries.Add(subquery);
        } 

        /// 
        /// Add a subquery to the "parent" relop node
        ///  
        /// the output var to be used - at the current location - in lieu of the subquery
        /// the subquery to move 
        /// a var ref node for the var returned from the subquery 
        private Node AddSubqueryToParentRelOp(Var outputVar, Node subquery)
        { 
            Node ancestor = FindRelOpAncestor();
            PlanCompiler.Assert(ancestor != null, "no ancestors found?");
            AddSubqueryToRelOpNode(ancestor, subquery);
 
            subquery = m_command.CreateNode(m_command.CreateVarRefOp(outputVar));
            return subquery; 
        } 

        ///  
        /// Find the first RelOp node that is in my ancestral path.
        /// If I see a PhysicalOp, then I don't have a RelOp parent
        /// 
        /// the first RelOp node 
        private Node FindRelOpAncestor()
        { 
            foreach (Node n in m_ancestors) 
            {
                if (n.Op.IsRelOp) 
                {
                    return n;
                }
                else if (n.Op.IsPhysicalOp) 
                {
                    return null; 
                } 
            }
            return null; 
        }
        #endregion

        #endregion 

        #region View Expansion 
        ///  
        /// Gets the "defining" query for an S-Space entityset.
        /// We simply convert this into 
        ///     select Type(c1, c2, ...) from Set
        ///
        /// A *key* assumption here is that the set is not polymorphic - otherwise, our smplistic
        /// constructor model above does not suffice 
        /// 
        /// current scan table node 
        /// the ScanTableOp 
        /// the defining query for this set
        private Node GetDefiningQueryForSSpaceSet(Node node, ScanTableOp scanTableOp) 
        {
            //
            // We have an S-Space entityset. Build up a simple "select * from T"
            // node tree on top of the base entityset 
            //
            EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent; 
            EntityType entityType = entitySet.ElementType as EntityType; 
            // For relationshipsets, do nothing
            if (entityType != null) 
            {
                Table baseTable = m_command.CreateTableInstance(scanTableOp.Table.TableMetadata);
                ScanTableOp baseTableOp = m_command.CreateScanTableOp(baseTable);
                Node baseTableNode = m_command.CreateNode(baseTableOp); 
                Var col = baseTable.Columns[0];
                List constructorArgs = new List(); 
                foreach (EdmProperty p in entityType.Properties) 
                {
                    Node arg = m_command.CreateNode(m_command.CreatePropertyOp(p), 
                        m_command.CreateNode(m_command.CreateVarRefOp(col)));
                    constructorArgs.Add(arg);
                }
                Node constructor = m_command.CreateNode( 
                    m_command.CreateNewInstanceOp(TypeUsage.Create(entityType)),
                    constructorArgs); 
                Var projectVar; 
                node = m_command.BuildProject(baseTableNode, constructor, out projectVar);
            } 

            return node;
        }
 
        /// 
        /// Convert a CQT command into an IQT subtree. 
        /// We expect the CQT command to be a query command tree. This is a 3-step 
        /// process
        ///   * We first run through the standard CQT-IQT convertor. 
        ///   * We then strip off the root of the IQT (the PhysicalProjectOp)
        ///   * Finally, we copy the IQT into our current IQT
        ///
        /// When we have metadata caching of IQTs (for views), instead of CQTs, 
        /// we can get rid of steps 1 and 2.
        ///  
        /// the view 
        /// an IQT subtree in the current command
        private Node ConvertToInternalTree(System.Data.Mapping.ViewGeneration.GeneratedView generatedView) 
        {
            Node ret;
            Node sourceIqt = generatedView.GetInternalTree(m_command.MetadataWorkspace);
            ret = OpCopier.Copy(m_command, sourceIqt); 
            return ret;
        } 
 
        /// 
        /// Gets the "expanded" query mapping view for the specified C-Space entity set 
        /// 
        /// The current node
        /// The scanTableOp that references the entity set
        ///  
        ///     An optional type filter to apply to the generated view.
        ///     Set to null on return if the generated view renders the type filter superfluous. 
        ///  
        /// A node that is the root of the new expanded view
        private Node ExpandView(Node node, ScanTableOp scanTableOp, ref IsOfOp typeFilter) 
        {
            EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent;
            PlanCompiler.Assert(entitySet != null, "The target of a ScanTableOp must reference an EntitySet to be used with ExpandView");
            PlanCompiler.Assert(entitySet.EntityContainer.DataSpace == DataSpace.CSpace, "Store entity sets cannot have Query Mapping Views and should not be used with ExpandView"); 

            if(typeFilter != null && 
               !typeFilter.IsOfOnly && 
                TypeSemantics.IsSubTypeOf(entitySet.ElementType, typeFilter.IsOfType.EdmType))
            { 
                //
                // If a type filter is being applied to the ScanTableOp, but that filter is asking
                // for all elements that are the same type or a supertype of the element type of the
                // target entity set, then the type filter is a no-op and can safely be discarded - 
                // IF AND ONLY IF the type filter is 'OfType' - which includes subtypes - and NOT
                // 'IsOfOnly' - which requires an exact type match, and so does not include subtypes. 
                // 
                typeFilter = null;
            } 

            //
            // Call the GetGeneratedView method to retrieve the query mapping view for the extent referenced
            // by the ScanTableOp. The actual method used to do this differs depending on whether the default 
            // Query Mapping View is sufficient or a targeted view that only filters by element type is required.
            // 
            System.Data.Mapping.ViewGeneration.GeneratedView definingQuery = null; 
            EntityTypeBase requiredType = scanTableOp.Table.TableMetadata.Extent.ElementType;
            bool includeSubtypes = true; 
            if(typeFilter != null)
            {
                //
                // A type filter is being applied to the ScanTableOp; it may be possible to produce 
                // an optimized expansion of the view based on type-specific views generated for the
                // C-Space entity set. 
                // The type for which the view should be tuned is the 'OfType' specified on the type filter. 
                // If the type filter is an 'IsOfOnly' filter then the view should NOT include subtypes of the required type.
                // 
                requiredType = (EntityTypeBase)typeFilter.IsOfType.EdmType;
                includeSubtypes = !typeFilter.IsOfOnly;
                if(m_command.MetadataWorkspace.TryGetGeneratedViewOfType(entitySet, requiredType, includeSubtypes, out definingQuery))
                { 
                    //
                    // At this point a type-specific view was found that satisifies the type filter's 
                    // constraints in terms of required type and whether subtypes should be included; 
                    // the type filter itself is now unnecessary and should be set to null indicating
                    // that it can be safely removed (see ProcessScanTableOp and Visit(FilterOp) for this). 
                    //
                    typeFilter = null;
                }
            } 

            // 
            // If a generated view has not been obtained at this point then either: 
            // - A type filter was specified but no type-specific view exists that satisfies its constraints.
            //   OR 
            // - No type filter was specified.
            // In either case the default query mapping view for the referenced entity set should now be retrieved.
            //
            if(null == definingQuery) 
            {
                definingQuery = m_command.MetadataWorkspace.GetGeneratedView(entitySet); 
            } 

            // 
            // If even the default query mapping view was not found then we cannot continue.
            // This implies that the set was not mapped, which should not be allowed, therefore
            // a retail assert is used here instead of a regular exception.
            // 
            PlanCompiler.Assert(definingQuery != null, Entity.Strings.ADP_NoQueryMappingView(entitySet.EntityContainer.Name, entitySet.Name));
 
            // 
            // At this point we're guaranteed to have found a defining query for the view.
            // We're now going to convert this into an IQT, and then copy it into our own IQT. 
            //
            Node ret = ConvertToInternalTree(definingQuery);

            // 
            // Make sure we're tracking what we've asked any discriminator maps to contain.
            // 
            DetermineDiscriminatorMapUsage(ret, entitySet, requiredType, includeSubtypes); 

            // 
            // Build up a ScanViewOp to "cap" the defining query below
            //
            ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table);
            ret = m_command.CreateNode(scanViewOp, ret); 

            return ret; 
        } 

 
        /// 
        /// If the discrminator map we're already tracking for this type (in this entityset)
        /// isn't already rooted at our required type, then we have to suppress the use of
        /// the descriminator maps when we constrct the structuredtypes; see SQLBUDT #615744 
        /// 
        private void DetermineDiscriminatorMapUsage(Node viewNode, EntitySetBase entitySet, EntityTypeBase rootEntityType, bool includeSubtypes) { 
            ExplicitDiscriminatorMap discriminatorMap = null; 

            // we expect the view to be capped with a project; we're just being careful here. 
            if (viewNode.Op.OpType == OpType.Project)
            {
                DiscriminatedNewEntityOp discriminatedNewEntityOp = viewNode.Child1.Child0.Child0.Op as DiscriminatedNewEntityOp;
 
                if (null != discriminatedNewEntityOp)
                { 
                    discriminatorMap = discriminatedNewEntityOp.DiscriminatorMap; 
                }
            } 

            DiscriminatorMapInfo discriminatorMapInfo;
            if (!m_discriminatorMaps.TryGetValue(entitySet, out discriminatorMapInfo))
            { 
                if (null == rootEntityType)
                { 
                    rootEntityType = entitySet.ElementType; 
                    includeSubtypes = true;
                } 
                discriminatorMapInfo = new DiscriminatorMapInfo(rootEntityType, includeSubtypes, discriminatorMap);
                m_discriminatorMaps.Add(entitySet, discriminatorMapInfo);
            }
            else 
            {
                discriminatorMapInfo.Merge(rootEntityType, includeSubtypes, discriminatorMap); 
            } 
        }
 
        #endregion

        #region NavigateOp rewrites
        ///  
        /// Rewrites a NavigateOp tree in the following fashion
        ///   SELECT VALUE r.ToEnd 
        ///   FROM (SELECT VALUE r1 FROM RS1 as r1 
        ///         UNION ALL
        ///         SELECT VALUE r2 FROM RS2 as r2 
        ///         ...
        ///         SELECT VALUE rN FROM RSN as rN) as r
        ///   WHERE r.FromEnd = sourceRef
        /// 
        ///  RS1, RS2 etc. are the set of all relationshipsets that can hold instances of the specified
        ///  relationship type. "sourceRef" is the single (ref-type) argument to the NavigateOp that 
        ///  represents the from-end of the navigation traversal 
        /// If the toEnd is multi-valued, then we stick a Collect(PhysicalProject( over the subquery above
        /// 
        /// A couple of special cases.
        ///    If no relationship sets can be found, we return a NULL (if the
        /// toEnd is single-valued), or an empty multiset (if the toEnd is multi-valued)
        /// 
        ///    If the toEnd is single-valued, *AND* the input Op is a GetEntityRefOp, then
        /// we convert the NavigateOp into a RelPropertyOp over the entity. 
        ///  
        /// the navigateOp tree
        /// the navigateOp 
        /// the output var produced by the subquery (ONLY if the to-End is single-valued)
        /// the resulting node
        private Node RewriteNavigateOp(Node navigateOpNode, NavigateOp navigateOp, out Var outputVar)
        { 
            outputVar = null;
 
            // 
            // Currently, navigation of composition relationships is not supported.
            // 
            if (!Helper.IsAssociationType(navigateOp.Relationship))
            {
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_RelNav_NoCompositions);
            } 

            // 
            // If the input to the navigateOp is a GetEntityRefOp, and the navigation 
            // is to the 1-end of the relationship, convert this into a RelPropertyOp instead - operating on the
            // input child to the GetEntityRefOp 
            //
            if (navigateOpNode.Child0.Op.OpType == OpType.GetEntityRef &&
                (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne ||
                navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One)) 
            {
                PlanCompiler.Assert(m_command.IsRelPropertyReferenced(navigateOp.RelProperty), 
                    "Unreferenced rel property? " + navigateOp.RelProperty); 
                Op relPropertyOp = m_command.CreateRelPropertyOp(navigateOp.RelProperty);
                Node relPropertyNode = m_command.CreateNode(relPropertyOp, 
                    navigateOpNode.Child0.Child0);
                return relPropertyNode;
            }
 
            List relationshipSets = GetRelationshipSets(navigateOp.Relationship);
 
            // 
            // Special case: when no relationshipsets can be found. Return NULL or an empty multiset,
            //   depending on the multiplicity of the toEnd 
            //
            if (relationshipSets.Count == 0)
            {
                // 
                // If we're navigating to the 1-end of the relationship, then simply return a null constant
                // 
                if (navigateOp.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many) 
                {
                    return m_command.CreateNode(m_command.CreateNullOp(navigateOp.Type)); 
                }
                else // return an empty set
                {
                    return m_command.CreateNode(m_command.CreateNewMultisetOp(navigateOp.Type)); 
                }
            } 
 
            //
            // Build up a UNION-ALL ladder over all the relationshipsets 
            //
            List scanTableNodes = new List();
            List scanTableVars = new List();
            foreach (RelationshipSet relSet in relationshipSets) 
            {
                TableMD tableMD = Command.CreateTableDefinition(relSet); 
                ScanTableOp tableOp = m_command.CreateScanTableOp(tableMD); 
                Node branchNode = m_command.CreateNode(tableOp);
                Var branchVar = tableOp.Table.Columns[0]; 
                scanTableVars.Add(branchVar);
                scanTableNodes.Add(branchNode);
            }
 
            Node unionAllNode = null;
            Var unionAllVar; 
            m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); 

            // 
            // Now build up the predicate
            //
            Node targetEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.ToEnd),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node sourceEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.FromEnd),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node predicateNode = m_command.BuildComparison(OpType.EQ, navigateOpNode.Child0, sourceEnd); 
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
                unionAllNode, predicateNode); 
            Var projectVar;
            Node projectNode = m_command.BuildProject(filterNode, targetEnd, out projectVar);

            // 
            // Finally, some magic about single-valued vs collection-valued ends
            // 
            Node ret; 
            if (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
            { 
                ret = m_command.BuildCollect(projectNode, projectVar);
            }
            else
            { 
                ret = projectNode;
                outputVar = projectVar; 
            } 

            return ret; 
        }
        #endregion

        #region DerefOp Rewrites 
        /// 
        /// Build up a node tree that represents the set of instances from the given table that are at least 
        /// of the specified type ("ofType"). If "ofType" is NULL, then all rows are returned 
        ///
        /// Return the outputVar from the nodetree 
        /// 
        /// the entityset or relationshipset to scan over
        /// the element types we're interested in
        /// the output var produced by this node tree 
        /// the node tree
        private Node BuildOfTypeTable(EntitySetBase entitySet, TypeUsage ofType, out Var resultVar) 
        { 
            TableMD tableMetadata = Command.CreateTableDefinition(entitySet);
            ScanTableOp tableOp = m_command.CreateScanTableOp(tableMetadata); 
            Node tableNode = m_command.CreateNode(tableOp);
            Var tableVar = tableOp.Table.Columns[0];

            Node resultNode; 
            //
            // Build a logical "oftype" expression - simply a filter predicate 
            // 
            if ((ofType != null) && !entitySet.ElementType.EdmEquals(ofType.EdmType))
            { 
                m_command.BuildOfTypeTree(tableNode, tableVar, ofType, true, out resultNode, out resultVar);
            }
            else
            { 
                resultNode = tableNode;
                resultVar = tableVar; 
            } 

            return resultNode; 
        }

        /// 
        /// Produces a relop tree that "logically" produces the target of the derefop. In essence, this gets rewritten 
        /// into
        ///      SELECT VALUE e 
        ///      FROM (SELECT VALUE e0 FROM OFTYPE(ES0, T) as e0 
        ///            UNION ALL
        ///            SELECT VALUE e1 FROM OFTYPE(ES1, T) as e1 
        ///            ...
        ///            SELECT VALUE eN from OFTYPE(ESN, T) as eN)) as e
        ///      WHERE REF(e) = myRef
        /// 
        /// "T" is the target type of the Deref, and myRef is the (single) argument to the DerefOp
        /// 
        /// ES0, ES1 etc. are all the EntitySets that could hold instances that are at least of type "T". We identify this list of sets 
        /// by looking at all entitycontainers referenced in the query, and looking at all entitysets in those
        /// containers that are of the right type 
        /// An EntitySet ES (of entity type X) can hold instances of T, if one of the following is true
        ///   - T is a subtype of X
        ///   - X is equal to T
        /// Our situation is a little trickier, since we also need to look for cases where X is a subtype of T. 
        /// 
        /// the derefOp subtree 
        /// the derefOp 
        /// output var produced
        /// the subquery described above 
        private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar)
        {
            TypeUsage entityType = derefOp.Type;
            List targetEntitySets = GetEntitySets(entityType); 
            if (targetEntitySets.Count == 0)
            { 
                // We didn't find any entityset that could match this. Simply return a null-value 
                outputVar = null;
                return m_command.CreateNode(m_command.CreateNullOp(entityType)); 
            }

            List scanTableNodes = new List();
            List scanTableVars = new List(); 
            foreach (EntitySet entitySet in targetEntitySets)
            { 
                Var tableVar; 
                Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
 
                scanTableNodes.Add(tableNode);
                scanTableVars.Add(tableVar);
            }
            Node unionAllNode; 
            Var unionAllVar;
            m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); 
 
            //
            // Finally build up the key comparison predicate 
            //
            Node entityRefNode = m_command.CreateNode(
                m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode);
            Node filterNode = m_command.CreateNode( 
                m_command.CreateFilterOp(), 
                unionAllNode,
                keyComparisonPred); 

            outputVar = unionAllVar;
            return filterNode;
        } 
        #endregion
 
        #region NavigationProperty Rewrites 

        ///  
        /// Find the entityset that corresponds to the specified end of the relationship.
        ///
        /// We must find one - else we assert.
        ///  
        /// the relationshipset
        /// the destination end of the relationship traversal 
        /// the entityset corresponding to the target end 
        private static EntitySetBase FindTargetEntitySet(RelationshipSet relationshipSet, RelationshipEndMember targetEnd)
        { 
            EntitySetBase entitySet = null;

            AssociationSet associationSet = (AssociationSet)relationshipSet;
            // find the corresponding entityset 
            entitySet = null;
            foreach (AssociationSetEnd e in associationSet.AssociationSetEnds) 
            { 
                if (e.CorrespondingAssociationEndMember.EdmEquals(targetEnd))
                { 
                    entitySet = e.EntitySet;
                    break;
                }
            } 
            PlanCompiler.Assert(entitySet != null, "Could not find entityset for relationshipset " + relationshipSet + ";association end " + targetEnd);
            return entitySet; 
        } 

 
        /// 
        /// Builds up a join between the relationshipset and the entityset corresponding to its toEnd. In essence,
        /// we produce
        ///    SELECT r, e 
        ///    FROM RS as r, OFTYPE(ES, T) as e
        ///    WHERE r.ToEnd = Ref(e) 
        /// 
        /// "T" is the entity type of the toEnd of the relationship.
        ///  
        /// the relationshipset
        /// the toEnd of the relationship
        /// the var representing the relationship instance ("r") in the output subquery
        /// the var representing the entity instance ("e") in the output subquery 
        /// the join subquery described above
        private Node BuildJoinForNavProperty(RelationshipSet relSet, RelationshipEndMember end, 
            out Var rsVar, out Var esVar) 
        {
            EntitySetBase entitySet = FindTargetEntitySet(relSet, end); 

            //
            // Build out the ScanTable ops for the relationshipset and the entityset. Add the
            // 
            Node asTableNode = BuildOfTypeTable(relSet, null, out rsVar);
            Node esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar); 
 
            //
            // Build up a join between the entityset and the associationset; join on the to-end 
            //
            Node joinPredicate = m_command.BuildComparison(OpType.EQ,
                m_command.CreateNode(m_command.CreateGetEntityRefOp(end.TypeUsage), m_command.CreateNode(m_command.CreateVarRefOp(esVar))),
                m_command.CreateNode(m_command.CreatePropertyOp(end), m_command.CreateNode(m_command.CreateVarRefOp(rsVar))) 
                );
 
            Node joinNode = m_command.CreateNode(m_command.CreateInnerJoinOp(), 
                asTableNode, esTableNode, joinPredicate);
 
            return joinNode;
        }

        ///  
        /// Rewrite a NavPropertyOp when the target end of the nav property has multiplicity
        /// of one (or zero..one). 
        /// We simply pick up the corresponding rel property from the input entity, and 
        /// apply a deref operation
        ///     NavProperty(e, n) => deref(relproperty(e, r)) 
        /// where e is the entity expression, n is the nav-property, and r is the corresponding
        /// rel-property
        /// 
        /// the rel-property describing the navigation 
        /// entity instance that we're starting the traversal from
        /// type of the target entity 
        /// a rewritten subtree 
        private Node RewriteToOneNavigationProperty(RelProperty relProperty,
            Node sourceEntityNode, TypeUsage resultType) 
        {
            RelPropertyOp relPropertyOp = m_command.CreateRelPropertyOp(relProperty);
            Node relPropertyNode = m_command.CreateNode(relPropertyOp, sourceEntityNode);
            DerefOp derefOp = m_command.CreateDerefOp(resultType); 
            Node derefNode = m_command.CreateNode(derefOp, relPropertyNode);
 
            return derefNode; 
        }
 
        /// 
        /// Rewrite a NavigationProperty when the relationship is a 1:N relationship.
        /// In essence, we find all the relevant target entitysets, and then compare the
        /// rel-property on the target end with the source ref 
        ///
        /// Converts 
        ///   NavigationProperty(e, r) 
        /// into
        ///   SELECT VALUE t 
        ///   FROM (SELECT VALUE e1 FROM ES1 as e1
        ///         UNION ALL
        ///         SELECT VALUE e2 FROM ES2 as e2
        ///         UNION ALL 
        ///         ...
        ///         ) as t 
        ///   WHERE RelProperty(t, r') = GetEntityRef(e) 
        ///
        /// r' is the inverse-relproperty for r 
        ///
        /// We also build out a CollectOp over the subquery above, and return that
        /// 
        /// the rel-property describing the relationship traversal 
        /// the list of relevant relationshipsets
        /// node tree corresponding to the source entity ref 
        /// type of the result 
        /// the rewritten subtree
        private Node RewriteOneToManyNavigationProperty(RelProperty relProperty, 
            List relationshipSets,
            Node sourceRefNode, TypeUsage resultType)
        {
            PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here"); 
            PlanCompiler.Assert(relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many,
                "Expected source end multiplicity to be one. Found 'Many' instead " + relProperty); 
            Node ret = null; 

            // 
            // We convert the
            //
            TypeUsage entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage);
            List scanTableNodes = new List(relationshipSets.Count); 
            List scanTableVars = new List(relationshipSets.Count);
            foreach (RelationshipSet r in relationshipSets) 
            { 
                EntitySetBase entitySet = FindTargetEntitySet(r, relProperty.ToEnd);
                Var tableVar; 
                Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);

                scanTableNodes.Add(tableNode);
                scanTableVars.Add(tableVar); 
            }
 
            // 
            // Build the union-all node
            // 
            Node unionAllNode;
            Var unionAllVar;
            m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
 
            //
            // Now build up the appropriate filter. Select out the relproperty from the other end 
            // 
            RelProperty inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd);
            PlanCompiler.Assert(m_command.IsRelPropertyReferenced(inverseRelProperty), 
                "Unreferenced rel property? " + inverseRelProperty);
            Node inverseRelPropertyNode = m_command.CreateNode(
                m_command.CreateRelPropertyOp(inverseRelProperty),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node predicateNode = m_command.BuildComparison(OpType.EQ,
                sourceRefNode, inverseRelPropertyNode); 
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), 
                unionAllNode, predicateNode);
 
            //
            // The magic of collections...
            //
            ret = m_command.BuildCollect(filterNode, unionAllVar); 

            return ret; 
        } 

        ///  
        /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r))
        /// where "r" is a many-to-many relationship
        ///
        /// We essentially produce the following subquery 
        ///   SELECT VALUE x.e
        ///   FROM (SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1) 
        ///         UNION ALL 
        ///         SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
        ///         ... 
        ///         ) as x
        ///   WHERE x.r.FromEnd = sourceRef
        ///
        /// RS1, RS2 etc. are the relevant relationshipsets 
        /// ES1, ES2 etc. are the corresponding entitysets for the toEnd of the relationship
        /// sourceRef is the ref argument 
        /// T is the type of the target-end of the relationship 
        ///
        /// We then build a CollectOp over the subquery above 
        /// 
        /// the rel property to traverse
        /// list of relevant relationshipsets
        /// source ref 
        /// type of the result
        ///  
        private Node RewriteManyToManyNavigationProperty(RelProperty relProperty, 
            List relationshipSets,
            Node sourceRefNode, TypeUsage resultType) 
        {
            PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
            PlanCompiler.Assert(relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many &&
                relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many, 
                "Expected target end multiplicity to be 'many'. Found " + relProperty + "; multiplicity = " + relProperty.ToEnd.RelationshipMultiplicity);
 
            Node ret = null; 

            List joinNodes = new List(relationshipSets.Count); 
            List outputVars = new List(relationshipSets.Count * 2);
            foreach (RelationshipSet r in relationshipSets)
            {
                Var rsVar; 
                Var esVar;
                Node joinNode = BuildJoinForNavProperty(r, relProperty.ToEnd, out rsVar, out esVar); 
                joinNodes.Add(joinNode); 
                outputVars.Add(rsVar);
                outputVars.Add(esVar); 
            }

            //
            // Build the union-all node 
            //
            Node unionAllNode; 
            IList unionAllVars; 
            m_command.BuildUnionAllLadder(joinNodes, outputVars, out unionAllNode, out unionAllVars);
 
            //
            // Now build out the filterOp over the left-side var
            //
            Node rsSourceRefNode = m_command.CreateNode(m_command.CreatePropertyOp(relProperty.FromEnd), 
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVars[0])));
            Node predicate = m_command.BuildComparison(OpType.EQ, 
                sourceRefNode, rsSourceRefNode); 
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
                unionAllNode, predicate); 

            //
            // Finally, build out a project node that only projects out the entity side
            // 
            Node projectNode = m_command.BuildProject(filterNode, new Var[] { unionAllVars[1] }, new Node[] { });
 
            // 
            // Build a collectOp over the project node
            // 
            ret = m_command.BuildCollect(projectNode, unionAllVars[1]);

            return ret;
        } 

        ///  
        /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r)) 
        ///
        /// We handle three cases here, depending on the kind of relationship we're 
        /// dealing with.
        ///   - *:1 relationships
        ///   - N:1 relationships
        ///   - N:M relationships 
        ///
        ///  
        /// the navigation property 
        /// the input ref to start the traversal
        /// the result type of the expression 
        /// the rewritten tree
        private Node RewriteNavigationProperty(NavigationProperty navProperty,
            Node sourceEntityNode, TypeUsage resultType)
        { 
            Node ret = null;
            RelProperty relProperty = new RelProperty(navProperty.RelationshipType, navProperty.FromEndMember, navProperty.ToEndMember); 
            PlanCompiler.Assert(m_command.IsRelPropertyReferenced(relProperty) || (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many), 
                "Unreferenced rel property? " + relProperty);
            // 
            // Case 1: The (target end of the) nav property has a multiplicity of 1 (or 0..1)
            //   (doesn't matter what the sourceEnd multiplicity is)
            //
            if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One || 
                relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne)
            { 
                ret = RewriteToOneNavigationProperty(relProperty, sourceEntityNode, resultType); 
                return ret;
            } 

            //
            // Otherwise, the target end is multi-valued. We need to deal with
            // 2 cases here. A N:1 relationship or a N:M relationship 
            //
 
            // 
            // Find the list of all relationships that could satisfy this relationship
            // If we find no matching relationship set, simply return an empty collection 
            //
            List relationshipSets = GetRelationshipSets(relProperty.Relationship);
            if (relationshipSets.Count == 0)
            { 
                // return an empty set
                return m_command.CreateNode(m_command.CreateNewMultisetOp(resultType)); 
            } 

            // 
            // Build out a ref over the source entity now
            //
            Node sourceRefNode = m_command.CreateNode(
                m_command.CreateGetEntityRefOp(relProperty.FromEnd.TypeUsage), 
                sourceEntityNode);
 
            // 
            // Are we dealing with a many-to-many relationship ?
            // 
            if (relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
            {
                ret = RewriteManyToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType);
            } 
            else
            { 
                ret = RewriteOneToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType); 
            }
 
            return ret;
        }

        #endregion 

        #region visitor helpers 
 
        /// 
        /// Extends the base class implementation of VisitChildren. 
        /// Wraps the call to visitchildren() by first adding the current node
        /// to the stack of "ancestors", and then popping back the node at the end
        /// 
        /// Current node 
        protected override void VisitChildren(Node n)
        { 
            // Push the current node onto the stack 
            m_ancestors.Push(n);
 
            for (int i = 0; i < n.Children.Count; i++)
            {
                n.Children[i] = VisitNode(n.Children[i]);
            } 

            m_ancestors.Pop(); 
        } 

        #endregion 

        #region visitor methods

        #region ScalarOps 

        ///  
        /// Default handler for scalar Ops. Simply traverses the children, 
        /// and also identifies any structured types along the way
        ///  
        /// the ScalarOp
        /// current subtree
        /// the possibly modified node
        protected override Node VisitScalarOpDefault(ScalarOp op, Node n) 
        {
            VisitChildren(n); // visit my children 
 
            // keep track of referenced types
            AddTypeReference(op.Type); 

            return n;
        }
 
        /// 
        /// Rewrite a DerefOp subtree. We have two cases to consider here. 
        /// We call RewriteDerefOp to return a subtree (and an optional outputVar). 
        /// If the outputVar is null, then we simply return the subtree produced by those calls.
        /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar 
        /// in its place.
        ///
        /// As an example,
        ///    select deref(e) from T 
        /// gets rewritten into
        ///    select v from T OuterApply X 
        /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X 
        ///
        ///  
        /// the derefOp
        /// the deref subtree
        /// the rewritten tree
        public override Node Visit(DerefOp op, Node n) 
        {
            Var outputVar; 
 
            VisitScalarOpDefault(op, n);
 
            Node ret = RewriteDerefOp(n, op, out outputVar);
            ret = VisitNode(ret);

            if (outputVar != null) 
            {
                ret = AddSubqueryToParentRelOp(outputVar, ret); 
            } 

            return ret; 
        }

        /// 
        /// Processing for an ElementOp. Replaces this by the corresponding Var from 
        /// the subquery, and adds the subquery to the list of currently tracked subqueries
        ///  
        /// the elementOp 
        /// current subtree
        /// the Var from the subquery 
        public override Node Visit(ElementOp op, Node n)
        {
            VisitScalarOpDefault(op, n); // default processing
 
            // get to the subquery...
            Node subQueryRelOp = n.Child0; 
            ProjectOp projectOp = (ProjectOp)subQueryRelOp.Op; 
            PlanCompiler.Assert(projectOp.Outputs.Count == 1, "input to ElementOp has more than one output var?");
            Var projectVar = projectOp.Outputs.First; 

            Node ret = AddSubqueryToParentRelOp(projectVar, subQueryRelOp);
            return ret;
        } 

        ///  
        /// Translate Exists(X) into Exists(select 0 from X) 
        /// 
        ///  
        /// 
        /// 
        public override Node Visit(ExistsOp op, Node n)
        { 
            VisitChildren(n);
 
            // Build up a dummy project node over the input 
            n.Child0 = BuildDummyProjectForExists(n.Child0);
 
            return n;
        }

        ///  
        /// Build Project(select 0 from child).
        ///  
        ///  
        /// 
        private Node BuildDummyProjectForExists(Node child) 
        {
            Var newVar;
            Node projectNode = m_command.BuildProject(
                child, 
                m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.BooleanType, true)),
                out newVar); 
            return projectNode; 
        }
 
        /// 
        /// Build up an unnest above a scalar op node
        ///    X => unnest(X)
        ///  
        /// the scalarop collection node
        /// the unnest node 
        private Node BuildUnnest(Node collectionNode) 
        {
            PlanCompiler.Assert(collectionNode.Op.IsScalarOp, "non-scalar usage of Unnest?"); 
            PlanCompiler.Assert(md.TypeSemantics.IsCollectionType(collectionNode.Op.Type), "non-collection usage for Unnest?");

            Var newVar;
            Node varDefNode = m_command.CreateVarDefNode(collectionNode, out newVar); 
            UnnestOp unnestOp = m_command.CreateUnnestOp(newVar);
            Node unnestNode = m_command.CreateNode(unnestOp, varDefNode); 
 
            return unnestNode;
        } 

        /// 
        /// Is this function a TVF?
        ///  
        /// current function op
        /// true, if the function returns a collection 
        private static bool IsCollectionFunction(FunctionOp op) 
        {
            return md.TypeSemantics.IsCollectionType(op.Type); 
        }

        /// 
        /// Converts a reference to a TVF, by the following 
        ///    Collect(PhysicalProject(Unnest(Func)))
        ///  
        /// current function op 
        /// current function subtree
        /// the new expression that corresponds to the TVF 
        private Node VisitCollectionFunction(FunctionOp op, Node n)
        {
            PlanCompiler.Assert(IsCollectionFunction(op), "non-TVF function?");
 
            Node unnestNode = BuildUnnest(n);
            UnnestOp unnestOp = unnestNode.Op as UnnestOp; 
            PhysicalProjectOp projectOp = m_command.CreatePhysicalProjectOp(unnestOp.Table.Columns[0]); 
            Node projectNode = m_command.CreateNode(projectOp, unnestNode);
            CollectOp collectOp = m_command.CreateCollectOp(n.Op.Type); 
            Node collectNode = m_command.CreateNode(collectOp, projectNode);

            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
            return collectNode; 
        }
 
        ///  
        /// Is this function a collection aggregate function. It is, if
        ///   - it has exactly one child 
        ///   - that child is a collection type
        ///   - and the function has been marked with the aggregate attribute
        /// 
        /// the function op 
        /// the current subtree
        /// true, if this was a collection aggregate function 
        private static bool IsCollectionAggregateFunction(FunctionOp op, Node n) 
        {
            return ((n.Children.Count == 1) && 
                    md.TypeSemantics.IsCollectionType(n.Child0.Op.Type) &&
                    md.TypeSemantics.IsAggregateFunction(op.Function));
        }
 
        /// 
        /// Converts a collection aggregate function count(X), where X is a collection into 
        /// two parts. Part A is a groupby subquery that looks like 
        ///    GroupBy(Unnest(X), empty, count(y))
        /// where "empty" describes the fact that the groupby has no keys, and y is an 
        /// element var of the Unnest
        ///
        /// Part 2 is a VarRef that refers to the aggregate var for count(y) described above.
        /// 
        /// Logically, we would replace the entire functionOp by element(GroupBy...). However,
        /// since we also want to translate element() into single-row-subqueries, we do this 
        /// here as well. 
        ///
        /// The function itself is replaced by the VarRef, and the GroupBy is added to the list 
        /// of scalar subqueries for the current relOp node on the stack
        ///
        /// 
        /// the functionOp for the collection agg 
        /// current subtree
        /// the VarRef node that should replace the function 
        private Node VisitCollectionAggregateFunction(FunctionOp op, Node n) 
        {
            md.TypeUsage softCastType = null; 
            Node argNode = n.Child0;
            if (OpType.SoftCast == argNode.Op.OpType)
            {
                softCastType = TypeHelpers.GetEdmType(argNode.Op.Type).TypeUsage; 
                argNode = argNode.Child0;
 
                while (OpType.SoftCast == argNode.Op.OpType) 
                {
                    argNode = argNode.Child0; 
                }
            }

            Node unnestNode = BuildUnnest(argNode); 
            UnnestOp unnestOp = unnestNode.Op as UnnestOp;
            Var unnestOutputVar = unnestOp.Table.Columns[0]; 
 
            AggregateOp aggregateOp = m_command.CreateAggregateOp(op.Function, false);
            VarRefOp unnestVarRefOp = m_command.CreateVarRefOp(unnestOutputVar); 
            Node unnestVarRefNode = m_command.CreateNode(unnestVarRefOp);
            if (softCastType != null)
            {
                unnestVarRefNode = m_command.CreateNode(m_command.CreateSoftCastOp(softCastType), unnestVarRefNode); 
            }
            Node aggExprNode = m_command.CreateNode(aggregateOp, unnestVarRefNode); 
 
            VarVec keyVars = m_command.CreateVarVec(); // empty keys
            Node keyVarDefListNode = m_command.CreateNode(m_command.CreateVarDefListOp()); 

            VarVec gbyOutputVars = m_command.CreateVarVec();
            Var aggVar;
            Node aggVarDefListNode = m_command.CreateVarDefListNode(aggExprNode, out aggVar); 
            gbyOutputVars.Set(aggVar);
            GroupByOp gbyOp = m_command.CreateGroupByOp(keyVars, gbyOutputVars); 
            Node gbySubqueryNode = m_command.CreateNode(gbyOp, unnestNode, keyVarDefListNode, aggVarDefListNode); 

            // "Move" this subquery to my parent relop 
            Node ret = AddSubqueryToParentRelOp(aggVar, gbySubqueryNode);

            return ret;
        } 

        ///  
        /// Pre-processing for a function. Does the default thing. In addition, if the 
        /// function is a TVF (ie) returns a collection, convert this expression into
        ///    Nest(select value p from unnest(f) as p) 
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(FunctionOp op, Node n)
        { 
            VisitScalarOpDefault(op, n); 
            Node newNode = null;
 
            // Is this a TVF?
            if (IsCollectionFunction(op))
            {
                newNode = VisitCollectionFunction(op, n); 
            }
            // Is this a collection-aggregate function? 
            else if (IsCollectionAggregateFunction(op, n)) 
            {
                newNode = VisitCollectionAggregateFunction(op, n); 
            }
            else
            {
                // sigh! 
                newNode = n;
            } 
 
            PlanCompiler.Assert(newNode != null, "failure to construct a functionOp?");
            return newNode; 
        }

        /// 
        /// Default processing. 
        /// In addition, if the case statement is of the shape
        ///     case when X then NULL else Y, or 
        ///     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,
        /// marks that type as needing a null sentinel. 
        /// This allows in NominalTypeElimination the case op to be pushed inside Y's null sentinel.
        /// 
        /// 
        ///  
        /// 
        public override Node Visit(CaseOp op, Node n) 
        { 
            VisitScalarOpDefault(op, n);
            //special handling to enable optimization 
            bool thenClauseIsNull;
            if (PlanCompilerUtil.IsRowTypeCaseOpWithNullability(op, n, out thenClauseIsNull))
            {
                //Add a null sentinel for the row type 
                m_typesNeedingNullSentinel.Add(op.Type.EdmType.Identity);
            } 
            return n; 
        }
 
        /// 
        /// If it is a IsNull op over a row type, mark the row type as needing a null sentinel.
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(ConditionalOp op, Node n) 
        {
            VisitScalarOpDefault(op, n); 
            if (op.OpType == OpType.IsNull && md.TypeSemantics.IsRowType(n.Child0.Op.Type))
            {
                StructuredTypeNullabilityAnalyzer.MarkAsNeedingNullSentinel(m_typesNeedingNullSentinel, n.Child0.Op.Type);
            } 
            return n;
        } 
 
        #region PropertyOp Handling
 
        /// 
        /// Validates that the nav property agrees with the underlying relationship
        /// 
        /// the Nav PropertyOp 
        /// the subtree
        private void ValidateNavPropertyOp(PropertyOp op, Node n) 
        { 
            NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
 
            //
            // If the result of the expanded form of the navigation property is not compatible with
            // the declared type of the property, then the navigation property is invalid in the
            // context of this command tree's metadata workspace. 
            //
            md.TypeUsage resultType = navProperty.ToEndMember.TypeUsage; 
            if (TypeSemantics.IsReferenceType(resultType)) 
            {
                resultType = TypeHelpers.GetElementTypeUsage(resultType); 
            }
            if (navProperty.ToEndMember.RelationshipMultiplicity == RelationshipMultiplicity.Many)
            {
                resultType = TypeUsage.Create(resultType.EdmType.GetCollectionType()); 
            }
            if (!TypeSemantics.IsEquivalentOrPromotableTo(resultType, op.Type)) 
            { 
                throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_IncompatibleNavigationPropertyResult(
                        navProperty.DeclaringType.FullName, 
                        navProperty.Name
                    )
                );
            } 
        }
 
        ///  
        /// Rewrite a PropertyOp subtree for a nav property
        /// 
        /// We call RewriteNavigationPropertyOp to return a subtree (and an
        /// optional outputVar). If the outputVar is null, then we simply return the subtree produced by those calls.
        /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
        /// in its place. 
        ///
        /// As an example, 
        ///    select e.NP from T 
        /// gets rewritten into
        ///    select v from T OuterApply X 
        /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
        /// 
        /// the PropertyOp
        /// the current node 
        /// the rewritten subtree
        private Node VisitNavPropertyOp(PropertyOp op, Node n) 
        { 
            ValidateNavPropertyOp(op, n);
 
            //
            // This is a bit weird. Ideally, I would always visit the child first (ie) a bottom-up traversal,
            // but there's some weird gotchas in the elinq tests ("SelectManyNullResult531057")
            // 
            bool visitChildFirst = (n.Child0.Op.OpType != OpType.Property);
            if (visitChildFirst) 
            { 
                VisitScalarOpDefault(op, n);
            } 

            NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
            Node ret = RewriteNavigationProperty(navProperty, n.Child0, op.Type);
            ret = VisitNode(ret); 

            return ret; 
        } 

        ///  
        /// Rewrite a PropertyOp subtree.
        ///
        /// If the PropertyOp represents a simple property (ie) not a navigation property, we simply call
        /// VisitScalarOpDefault() and return. Otherwise, we call VisitNavPropertyOp and return the result from 
        /// that function
        /// 
        ///  
        /// the PropertyOp
        /// the PropertyOp subtree 
        /// the rewritten tree
        public override Node Visit(PropertyOp op, Node n)
        {
            Node ret; 
            if (Helper.IsNavigationProperty(op.PropertyInfo))
            { 
                ret = VisitNavPropertyOp(op, n); 
            }
            else 
            {
                ret = VisitScalarOpDefault(op, n);
            }
            return ret; 
        }
 
        #endregion 

        ///  
        /// Handler for a RefOp.
        /// Keeps track of the entityset
        /// 
        /// the RefOp 
        /// current RefOp subtree
        /// current subtree 
        public override Node Visit(RefOp op, Node n) 
        {
            VisitScalarOpDefault(op, n); // use default processing 
            AddEntitySetReference(op.EntitySet); // add to list of references
            return n;
        }
 
        /// 
        /// Handler for a TreatOp. 
        /// Rewrites the operator if the argument is guaranteed to be of type 
        /// op.
        ///  
        /// Current TreatOp
        /// Current subtree
        /// Current subtree
        public override Node Visit(TreatOp op, Node n) 
        {
            n = base.Visit(op, n); 
 
            // See if TreatOp can be rewritten (if it's not polymorphic)
            if (CanRewriteTypeTest(op.Type.EdmType, n.Child0.Op.Type.EdmType)) 
            {
                // Return argument directly (if the argument is null, 'treat as' also returns null;
                // if the argument is not null, it's guaranteed to be of the correct type)
                return n.Child0; 
            }
 
            return n; 
        }
 
        /// 
        /// Handler for an IsOfOp.
        /// Keeps track of the IsOfType (if it is a structured type) and rewrites the
        /// operator if the argument is guaranteed to be of type op.IsOfType 
        /// 
        /// Current IsOfOp 
        /// Current subtree 
        /// Current subtree
        public override Node Visit(IsOfOp op, Node n) 
        {
            n = VisitScalarOpDefault(op, n); // default handling first
            // keep track of any structured types
            AddTypeReference(op.IsOfType); 

            // See if the IsOfOp can be rewritten (if it's not polymorphic) 
            if (CanRewriteTypeTest(op.IsOfType.EdmType, n.Child0.Op.Type.EdmType)) 
            {
                n = RewriteIsOfAsIsNull(op, n); 
            }

            // For IsOfOnly(abstract type), suppress DiscriminatorMaps since no explicit type id is available for
            // abstract types. 
            if (op.IsOfOnly && op.IsOfType.EdmType.Abstract)
            { 
                m_suppressDiscriminatorMaps = true; 
            }
 
            return n;
        }

        // Determines whether a type test expression can be rewritten. Returns true of the 
        // argument type is guaranteed to implement "testType" (if the argument is non-null).
        private bool CanRewriteTypeTest(EdmType testType, EdmType argumentType) 
        { 
            // The rewrite only proceeds if the types are the same. If they are not,
            // it suggests either that the input result is polymorphic (in which case if OfType 
            // should be preserved) or the types are incompatible (which is caught
            // elsewhere)
            if (!testType.EdmEquals(argumentType))
            { 
                return false;
            } 
 
            // If the IsOfType is non-polymorphic (no base or derived types) the rewrite
            // is possible. 
            if (null != testType.BaseType)
            {
                return false;
            } 

            // Count sub types 
            int subTypeCount = 0; 
            foreach (EdmType subType in MetadataHelper.GetTypeAndSubtypesOf(testType, m_command.MetadataWorkspace, true /*includeAbstractTypes*/))
            { 
                subTypeCount++;
                if (2 == subTypeCount) { break; }
            }
 
            return 1 == subTypeCount; // no children types
        } 
 
        // Translates
        //      'R is of T' 
        // to
        //      '(case when not (R is null) then True else null end) = True'
        //
        // Input requirements: 
        //
        //      - IsOfOp and argument to same must be in the same hierarchy. 
        //      - IsOfOp and argument must have the same type 
        //      - IsOfOp.IsOfType may not have super- or sub- types (validate
        //        using CanRewriteTypeTest) 
        //
        // Design requirements:
        //
        //      - Must return true if the record exists 
        //      - Must return null if it does not
        //      - Must be in predicate form to avoid confusing SQL gen 
        // 
        // The translation assumes R is of T when R is non null.
        private Node RewriteIsOfAsIsNull(IsOfOp op, Node n) 
        {
            // construct 'R is null' predicate
            ConditionalOp isNullOp = m_command.CreateConditionalOp(OpType.IsNull);
            Node isNullNode = m_command.CreateNode(isNullOp, n.Child0); 

            // construct 'not (R is null)' predicate 
            ConditionalOp notOp = m_command.CreateConditionalOp(OpType.Not); 
            Node notNode = m_command.CreateNode(notOp, isNullNode);
 
            // construct 'True' result
            ConstantBaseOp trueOp = m_command.CreateConstantOp(op.Type, true);
            Node trueNode = m_command.CreateNode(trueOp);
 
            // construct 'null' default result
            NullOp nullOp = m_command.CreateNullOp(op.Type); 
            Node nullNode = m_command.CreateNode(nullOp); 

            // create case statement 
            CaseOp caseOp = m_command.CreateCaseOp(op.Type);
            Node caseNode = m_command.CreateNode(caseOp, notNode, trueNode, nullNode);

            // create 'case = true' operator 
            ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
            Node equalsNode = m_command.CreateNode(equalsOp, caseNode, trueNode); 
 
            return equalsNode;
        } 

        /// 
        /// Rewrite a NavigateOp subtree.
        /// We call RewriteNavigateOp to return a subtree (and an optional outputVar). 
        /// If the outputVar is null, then we simply return the subtree produced by those calls.
        /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar 
        /// in its place. 
        ///
        /// As an example, 
        ///    select navigate(e) from T
        /// gets rewritten into
        ///    select v from T OuterApply X
        /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X 
        ///
        ///  
        /// the navigateOp 
        /// the navigateOp subtree
        /// the rewritten tree 
        public override Node Visit(NavigateOp op, Node n)
        {
            VisitScalarOpDefault(op, n);
            Var outputVar; 
            Node ret = RewriteNavigateOp(n, op, out outputVar);
            ret = VisitNode(ret); 
 
            // Move subquery to parent relop if necessary
            if (outputVar != null) 
            {
                ret = AddSubqueryToParentRelOp(outputVar, ret);
            }
            return ret; 
        }
 
        ///  
        /// Find the "current" enclosing entityset
        ///  
        /// the enclosing entityset (if any)
        private EntitySetBase FindEnclosingEntitySetView()
        {
            if (m_viewNestingLevel == 0) 
            {
                return null; 
            } 

            // 
            // Walk up the stack of ancestors until we find the appropriate ScanViewOp
            //
            foreach (Node n in m_ancestors)
            { 
                if (n.Op.OpType == OpType.ScanView)
                { 
                    ScanViewOp op = (ScanViewOp)n.Op; 
                    return op.Table.TableMetadata.Extent;
                } 
            }

            PlanCompiler.Assert(false, "found no enclosing view - but view-nesting level is greater than zero");
            return null; 
        }
 
        ///  
        /// Find the relationshipset that matches the current entityset + from/to roles
        ///  
        /// 
        /// 
        /// 
        private RelationshipSet FindRelationshipSet(EntitySetBase entitySet, RelProperty relProperty) 
        {
            foreach (EntitySetBase es in entitySet.EntityContainer.BaseEntitySets) 
            { 
                AssociationSet rs = es as AssociationSet;
                if (rs != null && 
                    rs.ElementType.EdmEquals(relProperty.Relationship) &&
                    rs.AssociationSetEnds[relProperty.FromEnd.Identity].EntitySet.EdmEquals(entitySet))
                {
                    return rs; 
                }
            } 
            return null; 
        }
 
        /// 
        /// Find the position of a property in a type.
        /// Positions start at zero, and a supertype's properties precede the current
        /// type's properties 
        /// 
        /// the type in question 
        /// the member to lookup 
        /// the position of the member in the type (0-based)
        private int FindPosition(EdmType type, EdmMember member) 
        {
            int pos = 0;
            foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(type))
            { 
                if (m.EdmEquals(member))
                { 
                    return pos; 
                }
                pos++; 
            }
            PlanCompiler.Assert(false, "Could not find property " + member + " in type " + type.Name);
            return -1;
        } 

        ///  
        /// Build out an expression (NewRecord) that corresponds to the key properties 
        /// of the passed-in entity constructor
        /// 
        /// This function simply looks up the key properties of the entity type, and then
        /// identifies the arguments to the constructor corresponding to those
        /// properties, and then slaps on a record wrapper over those expressions.
        /// 
        /// No copies/clones are performed. That's the responsibility of the caller
        /// 
        ///  
        /// the entity constructor op
        /// the corresponding subtree 
        /// the key expression
        private Node BuildKeyExpressionForNewEntityOp(Op op, Node n)
        {
            PlanCompiler.Assert(op.OpType == OpType.NewEntity || op.OpType == OpType.DiscriminatedNewEntity, 
                "BuildKeyExpression: Unexpected OpType:" + op.OpType);
            int offset = (op.OpType == OpType.DiscriminatedNewEntity) ? 1 : 0; 
            EntityTypeBase entityType = (EntityTypeBase)op.Type.EdmType; 
            List keyFields = new List();
            List> keyFieldTypes = new List>(); 
            foreach (EdmMember k in entityType.KeyMembers)
            {
                int pos = FindPosition(entityType, k) + offset;
                PlanCompiler.Assert(n.Children.Count > pos, "invalid position " + pos + "; total count = " + n.Children.Count); 
                keyFields.Add(n.Children[pos]);
                keyFieldTypes.Add(new KeyValuePair(k.Name, k.TypeUsage)); 
            } 
            TypeUsage keyExprType = TypeHelpers.CreateRowTypeUsage(keyFieldTypes, true);
            NewRecordOp keyOp = m_command.CreateNewRecordOp(keyExprType); 
            Node keyNode = m_command.CreateNode(keyOp, keyFields);
            return keyNode;
        }
 
        /// 
        /// Build out an expression corresponding to the rel-property. 
        /// 
        /// We create a subquery that looks like
        ///    (select r 
        ///     from RS r
        ///     where GetRefKey(r.FromEnd) = myKey)
        ///
        /// RS is the single relationship set that corresponds to the given entityset/rel-property pair 
        /// FromEnd - is the source end of the relationship
        /// myKey - is the key expression of the entity being constructed 
        /// 
        /// NOTE: We always clone "myKey" before use.
        /// 
        /// We then convert it into a scalar subquery, and extract out the ToEnd property from
        /// the output var of the subquery. (Should we do this inside the subquery itself?)
        ///
        /// If no single relationship-set is found, we return a NULL instead. 
        /// 
        /// entity set that logically holds instances of the entity we're building 
        /// the rel-property we're trying to build up 
        /// the "key" of the entity instance
        /// the rel-property expression 
        private Node BuildRelPropertyExpression(EntitySetBase entitySet, RelProperty relProperty,
            Node keyExpr)
        {
            // 
            // Make a copy of the current key expression
            // 
            keyExpr = OpCopier.Copy(m_command, keyExpr); 

            // 
            // Find the relationship set corresponding to this entityset (and relProperty)
            // Return a null ref, if we can't find one
            //
            RelationshipSet relSet = FindRelationshipSet(entitySet, relProperty); 
            if (relSet == null)
            { 
                return m_command.CreateNode(m_command.CreateNullOp(relProperty.ToEnd.TypeUsage)); 
            }
 
            ScanTableOp scanTableOp = m_command.CreateScanTableOp(Command.CreateTableDefinition(relSet));
            PlanCompiler.Assert(scanTableOp.Table.Columns.Count == 1,
                "Unexpected column count for table:" + scanTableOp.Table.TableMetadata.Extent + "=" + scanTableOp.Table.Columns.Count);
            Var scanTableVar = scanTableOp.Table.Columns[0]; 
            Node scanNode = m_command.CreateNode(scanTableOp);
 
            Node sourceEndNode = m_command.CreateNode( 
                m_command.CreatePropertyOp(relProperty.FromEnd),
                m_command.CreateNode(m_command.CreateVarRefOp(scanTableVar))); 
            Node predicateNode = m_command.BuildComparison(OpType.EQ,
                keyExpr,
                m_command.CreateNode(m_command.CreateGetRefKeyOp(keyExpr.Op.Type), sourceEndNode));
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), 
                scanNode, predicateNode);
 
            // 
            // Process the node, and then add this as a subquery to the parent relop
            // 
            Node ret = VisitNode(filterNode);
            ret = AddSubqueryToParentRelOp(scanTableVar, ret);

            // 
            // Now extract out the target end property
            // 
            ret = m_command.CreateNode( 
                m_command.CreatePropertyOp(relProperty.ToEnd),
                ret); 

            return ret;
        }
 
        /// 
        /// Given an entity constructor (NewEntityOp, DiscriminatedNewEntityOp), build up 
        /// the list of rel-property expressions. 
        ///
        /// Walks through the list of relevant rel-properties, and builds up expressions 
        /// (using BuildRelPropertyExpression) for each rel-property that does not have
        /// an expression already built (preBuiltExpressions)
        /// 
        /// entity set that holds instances of the entity we're building 
        /// the list of relevant rel-properties for this entity type
        /// the prebuilt rel-property expressions 
        /// the key of the entity instance 
        /// a list of rel-property expressions (lines up 1-1 with 'relPropertyList')
        private IEnumerable BuildAllRelPropertyExpressions(EntitySetBase entitySet, 
            List relPropertyList,
            Dictionary prebuiltExpressions,
            Node keyExpr)
        { 
            foreach (RelProperty r in relPropertyList)
            { 
                Node relPropNode; 
                if (!prebuiltExpressions.TryGetValue(r, out relPropNode))
                { 
                    relPropNode = BuildRelPropertyExpression(entitySet, r, keyExpr);
                }
                yield return relPropNode;
            } 
        }
 
        ///  
        /// Handler for NewEntityOp.
        /// If this is an EntityConstructor, and the current view nesting level is 0 
        /// (ie) this is an EntityConstructor at the top-level query, then add
        /// the type to the list of "free-floating" entity constructor types
        /// 
        /// the NewEntityOp 
        /// the node tree corresponding to the op
        /// rewritten tree 
        public override Node Visit(NewEntityOp op, Node n) 
        {
            // 
            // The default processing first
            //
            VisitScalarOpDefault(op, n);
 
            md.EntityType entityType = op.Type.EdmType as md.EntityType;
            md.EntitySetBase entitySet = FindEnclosingEntitySetView(); 
 
            if (entitySet == null)
            { 
                if (entityType != null)
                {
                    m_freeFloatingEntityConstructorTypes.Add(entityType);
                } 

                // SQLBUDT #546546: Qmv/Umv tests Assert and throws in plan compiler in association tests. 
                // If this Entity constructor is not within a view then there should not be any RelProps 
                // specified on the NewEntityOp - the eSQL WITH RELATIONSHIPS clause that would cause such
                // RelProps to be added is only enabled when parsing in the user or generated view mode. 
                PlanCompiler.Assert(op.RelationshipProperties == null ||
                                    op.RelationshipProperties.Count == 0,
                                    "Related Entities cannot be specified for Entity constructors that are not part of the Query Mapping View for an Entity Set.");
 
                return n;
            } 
 
            //
            // Find the relationship properties for this entitytype (and entity set) 
            //
            List relProperties = new List(m_relPropertyHelper.GetRelProperties(entityType));

            // 
            // Ok, now, I have to build out some relationship properties that
            // haven't been specified 
            // 
            Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
 
            //
            // Find the list of rel properties that have already been specified
            //
            Dictionary prebuiltRelPropertyExprs = new Dictionary(); 
            int j = 0;
            for (int i = entityType.Properties.Count; i < n.Children.Count; i++, j++) 
            { 
                prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
            } 

            //
            // Fill in the missing pieces
            // 

            // 
            // Next, rebuild the list of children - includes expressions for each rel property 
            //
            List newChildren = new List(); 
            for (int i = 0; i < entityType.Properties.Count; i++)
            {
                newChildren.Add(n.Children[i]);
            } 

            foreach (Node relPropNode in BuildAllRelPropertyExpressions(entitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) 
            { 
                newChildren.Add(relPropNode);
            } 

            //
            // finally, build out the newOp
            // 
            Op newEntityOp = m_command.CreateNewEntityOp(op.Type, relProperties, entitySet);
            Node newNode = m_command.CreateNode(newEntityOp, newChildren); 
            return newNode; 
        }
 
        /// 
        /// Tracks discriminator metadata so that is can be used when constructing
        /// StructuredTypeInfo.
        ///  
        public override Node Visit(DiscriminatedNewEntityOp op, Node n)
        { 
            PlanCompiler.Assert(0 < m_viewNestingLevel, "DiscriminatedNewInstanceOp may appear only within view definition"); 

            HashSet relPropertyHashSet = new HashSet(); 
            List relProperties = new List();
            //
            // add references to each type produced by this node
            // Also, get the set of rel-properties for each of the types 
            //
            foreach (var discriminatorTypePair in op.DiscriminatorMap.TypeMap) 
            { 
                EntityTypeBase entityType = discriminatorTypePair.Value;
                AddTypeReference(TypeUsage.Create(entityType)); 
                foreach (RelProperty relProperty in m_relPropertyHelper.GetRelProperties(entityType))
                {
                    relPropertyHashSet.Add(relProperty);
                } 
            }
            relProperties = new List(relPropertyHashSet); 
            VisitScalarOpDefault(op, n); 

            // 
            // Now build out the set of missing rel-properties (if any)
            //

            // first, build the key expression 
            Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
 
            List newChildren = new List(); 
            int firstRelPropertyNodeOffset = n.Children.Count - op.RelationshipProperties.Count;
            for (int i = 0; i < firstRelPropertyNodeOffset; i++) 
            {
                newChildren.Add(n.Children[i]);
            }
            // 
            // Find the list of rel properties that have already been specified
            // 
            Dictionary prebuiltRelPropertyExprs = new Dictionary(); 
            for (int i = firstRelPropertyNodeOffset, j =0; i < n.Children.Count; i++, j++ )
            { 
               prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
            }

            // 
            // Fill in the missing pieces
            // 
            foreach (Node relPropNode in BuildAllRelPropertyExpressions(op.EntitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) 
            {
                newChildren.Add(relPropNode); 
            }

            Op newEntityOp = m_command.CreateDiscriminatedNewEntityOp(op.Type, op.DiscriminatorMap, op.EntitySet, relProperties);
            Node newNode = m_command.CreateNode(newEntityOp, newChildren); 

            return newNode; 
        } 

        ///  
        /// Handles a newMultiset constructor. Converts this into
        ///   select a from dual union all select b from dual union all ...
        /// Handles a NewMultiset constructor, i.e. {x, y, z}
        ///   1. Empty multiset constructors are simply converted into: 
        ///
        ///        select x from singlerowtable as x where false 
        /// 
        ///   2. Mulltset constructors with only one element or with multiple elements all of
        ///   which are constants or nulls are converted into: 
        ///
        ///     select x from dual union all select y from dual union all select z
        ///
        ///   3. All others are converted into: 
        ///
        ///      select case when d = 0 then x when d = 1 then y else z end 
        ///      from (  select 0 as d from single_row_table 
        ///              union all
        ///              select 1 as d from single_row_table 
        ///              union all
        ///              select 2 as d  from single_row_table )
        ///
        ///       NOTE: The  translation for 2 is valid for 3 too. We choose different translation 
        ///       in order to avoid correlation inside the union all,
        ///       which would prevent us from removing apply operators 
        /// 
        /// Do this before processing the children, and then
        /// call Visit on the result to handle the elements 
        /// 
        /// the new instance op
        /// the current subtree
        /// the modified subtree 
        public override Node Visit(NewMultisetOp op, Node n)
        { 
            Node resultNode = null; 
            Var resultVar = null;
 
            md.CollectionType collectionType = TypeHelpers.GetEdmType(op.Type);

            //
            // Empty multiset constructors are simply converted into 
            //    Project(Filter(SingleRowTableOp(), false)
            // 
            if (!n.HasChild0) 
            {
                Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); 
                Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
                    singleRowTableNode,
                    m_command.CreateNode(m_command.CreateFalseOp()));
                Node fakeChild = m_command.CreateNode(m_command.CreateNullOp(collectionType.TypeUsage)); 
                Var newVar;
                Node projectNode = m_command.BuildProject(filterNode, fakeChild, out newVar); 
 
                resultNode = projectNode;
                resultVar = newVar; 
            }

            //
            // Multiset constructors with only one elment or with multiple elments all of 
            //   which are constants or nulls are converted into:
            // 
            // UnionAll(Project(SingleRowTable, e1), Project(SingleRowTable, e2), ...) 
            //
            // The degenerate case when the collection has only one element does not require an 
            // outer unionAll node
            //
            else if (n.Children.Count == 1 || AreAllConstantsOrNulls(n.Children))
            { 
                List inputNodes = new List();
                List inputVars = new List(); 
                foreach (Node chi in n.Children) 
                {
                    Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); 
                    Var newVar;
                    Node projectNode = m_command.BuildProject(singleRowTableNode, chi, out newVar);
                    inputNodes.Add(projectNode);
                    inputVars.Add(newVar); 
                }
                // Build the union-all ladder 
                m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar); 

            } 
            //
            //   All other cases:
            //
            //  select case when d = 0 then x when d = 1 then y else z end 
            //  from (  select 0 as d from single_row_table
            //          union all 
            //          select 1 as d from single_row_table 
            //          union all
            //          select 2 as d  from single_row_table ) 
            //
            else
            {
                List inputNodes = new List(); 
                List inputVars = new List();
                //Create the union all lather first 
                for (int i = 0; i < n.Children.Count; i++) 
                {
                    Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); 
                    // the discriminator for this branch
                    Node discriminatorNode = m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.IntegerType, i));
                    Var newVar;
                    Node projectNode = m_command.BuildProject(singleRowTableNode, discriminatorNode, out newVar); 

                    inputNodes.Add(projectNode); 
                    inputVars.Add(newVar); 
                }
                // Build the union-all ladder now 
                m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);

                //Now create the case statement for the projection
                List caseArgNodes = new List(n.Children.Count * 2 + 1); 
                for (int i = 0; i < n.Children.Count; i++)
                { 
                    //For all but the last we need a when 
                    if (i != (n.Children.Count - 1))
                    { 
                        ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
                        Node whenNode = m_command.CreateNode(equalsOp,
                            m_command.CreateNode(m_command.CreateVarRefOp(resultVar)),
                            m_command.CreateNode( 
                                m_command.CreateConstantOp(m_command.IntegerType, i)));
                        caseArgNodes.Add(whenNode); 
                    } 

                    //Add the then/else node 
                    caseArgNodes.Add(n.Children[i]);
                }

                //Create the project 
                Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(collectionType.TypeUsage), caseArgNodes);
                resultNode = m_command.BuildProject(resultNode, caseNode, out resultVar); 
            } 

            // So, I've finally built up a complex query corresponding to the constructor. 
            // Now, cap this with a physicalprojectOp, and then with a CollectOp
            PhysicalProjectOp physicalProjectOp = m_command.CreatePhysicalProjectOp(resultVar);
            Node physicalProjectNode = m_command.CreateNode(physicalProjectOp, resultNode);
 
            CollectOp collectOp = m_command.CreateCollectOp(op.Type);
            Node collectNode = m_command.CreateNode(collectOp, physicalProjectNode); 
 
            return VisitNode(collectNode);
        } 

        /// 
        /// Returns true if each node in the list is either a constant or a null
        ///  
        /// 
        ///  
        private bool AreAllConstantsOrNulls(List nodes) 
        {
            foreach (Node node in nodes) 
            {
                if (node.Op.OpType != OpType.Constant && node.Op.OpType != OpType.Null)
                {
                    return false; 
                }
            } 
            return true; 
        }
 
        /// 
        /// Default processing for a CollectOp. But make sure that we
        /// go through the NestPullUp phase
        ///  
        /// 
        ///  
        ///  
        public override Node Visit(CollectOp op, Node n)
        { 
            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
            return VisitScalarOpDefault(op, n);
        }
 
        #endregion
 
        #region RelOps 

        ///  
        /// Augments a node with a number of OuterApply's - one for each subquery
        /// If S1, S2, ... are the list of subqueries for the node, and D is the
        /// original (driver) input, we convert D into
        ///    OuterApply(OuterApply(D, S1), S2), ... 
        /// 
        /// the input (driver) node 
        /// List of subqueries 
        /// should the input node be first in the apply chain, or the last?
        /// The resulting node tree 
        private Node AugmentWithSubqueries(Node input, List subqueries, bool inputFirst)
        {
            Node newNode;
            int subqueriesStartPos; 

            if (inputFirst) 
            { 
                newNode = input;
                subqueriesStartPos = 0; 
            }
            else
            {
                newNode = subqueries[0]; 
                subqueriesStartPos = 1;
            } 
            for (int i =subqueriesStartPos; i < subqueries.Count; i++) 
            {
                    OuterApplyOp op = m_command.CreateOuterApplyOp(); 
                    newNode = m_command.CreateNode(op, newNode, subqueries[i]);
            }
            if (!inputFirst)
            { 
                newNode = m_command.CreateNode(m_command.CreateOuterApplyOp(), newNode, input);
            } 
 
            // We may need to perform join elimination
            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); 
            return newNode;
        }

        ///  
        /// Default processing for RelOps.
        /// - First, we mark the current node as its own ancestor (so that any 
        ///   subqueries that we detect internally will be added to this node's list) 
        /// - then, visit each child
        /// - finally, accumulate all nested subqueries. 
        /// - if the current RelOp has only one input, then add the nested subqueries via
        ///   Outer apply nodes to this input.
        ///
        /// The interesting RelOps are 
        ///   Project, Filter, GroupBy, Sort,
        /// Should we break this out into separate functions instead? 
        ///  
        /// Current RelOp
        /// Node to process 
        /// Current subtree
        protected override Node VisitRelOpDefault(RelOp op, Node n)
        {
            VisitChildren(n); // visit all my children first 

            // Then identify all the subqueries that have shown up as part of my node 
            // Create Apply Nodes for each of these. 
            List nestedSubqueries;
            if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries) && nestedSubqueries.Count > 0) 
            {
                // Validate - this must only apply to the following nodes
                PlanCompiler.Assert(
                    n.Op.OpType == OpType.Project || n.Op.OpType == OpType.Filter || 
                    n.Op.OpType == OpType.GroupBy,
                    "VisitRelOpDefault: Unexpected op?" + n.Op.OpType); 
 
                Node newInputNode = AugmentWithSubqueries(n.Child0, nestedSubqueries, true);
                // Now make this the new input child 
                n.Child0 = newInputNode;
            }

            return n; 
        }
 
        private void HandleTableOpMetadata(ScanTableBaseOp op) 
        {
            // add to the list of referenced entitysets 
            md.EntitySet entitySet = op.Table.TableMetadata.Extent as md.EntitySet;
            if (entitySet != null)
            {
                AddEntitySetReference(entitySet); 
            }
 
            md.TypeUsage elementType = TypeUsage.Create(op.Table.TableMetadata.Extent.ElementType); 
            // add to the list of structured types
            AddTypeReference(elementType); 
        }

        /// 
        /// Visits a "table" expression - performs view expansion on the table (if appropriate), 
        /// and then some additional book-keeping.
        /// 
        /// The "ofType" and "includeSubtypes" parameters are optional hints for view expansion, allowing 
        /// for more customized (and hopefully, more optimal) views. The wasOfTypeSatisfied out parameter
        /// tells whether the ofType filter was already handled by the view expansion, or if the caller still 
        /// needs to deal with it.
        ///
        /// If the "table" is a C-space entityset, then we produce a ScanViewOp
        /// tree with the defining query as the only child of the ScanViewOp 
        ///
        /// If the table is an S-space entityset, then we still produce a ScanViewOp, but this 
        /// time, we produce a simple "select * from BaseTable" as the defining 
        /// query
        ///  
        /// the scanTable node tree
        /// the scanTableOp
        /// 
        ///     An optional IsOfOp representing a type filter to apply to the scan table; will be set to null 
        ///     if the scan target is expanded to a view that renders the type filter superfluous.
        ///  
        ///  
        private Node ProcessScanTable(Node scanTableNode, ScanTableOp scanTableOp, ref IsOfOp typeFilter)
        { 
            HandleTableOpMetadata(scanTableOp);

            PlanCompiler.Assert(scanTableOp.Table.TableMetadata.Extent != null, "ScanTableOp must reference a table with an extent");
 
            Node ret = null;
 
            // 
            // Get simple things out of the way. If we're dealing with an S-space entityset, and
            // it isn't at the top-level of the query, simply return the node 
            //
            if (scanTableOp.Table.TableMetadata.Extent.EntityContainer.DataSpace == DataSpace.SSpace)
            {
                if (m_viewNestingLevel > 0) 
                {
                    return scanTableNode; 
                } 

                // If the S-level entityset is at the  "top-level" of the query, 
                // i.e. it is not referenced inside a view, we perform a "select *"
                // translation over the set. This also caps the entityset with a
                // ScanViewOp so it is logically withing a view definition when the
                // PreProcessor is run again over the resulting Node. 
                Node definingQuery = GetDefiningQueryForSSpaceSet(scanTableNode, scanTableOp);
                ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table); 
                ret = m_command.CreateNode(scanViewOp, definingQuery); 
            }
            else 
            {
                // "Expand" the C-Space view
                ret = ExpandView(scanTableNode, scanTableOp, ref typeFilter);
            } 

            m_viewNestingLevel++; 
            // Rerun the processor over the resulting subtree 
            ret = VisitNode(ret);
            m_viewNestingLevel--; 

            return ret;
        }
 
        /// 
        /// Processes a ScanTableOp - simply delegates to ProcessScanTableOp 
        ///  
        /// the view op
        /// current node tree 
        /// the transformed view-op
        public override Node Visit(ScanTableOp op, Node n)
        {
            IsOfOp nullFilter = null; 
            return ProcessScanTable(n, op, ref nullFilter);
        } 
 
        /// 
        /// Visitor for a ScanViewOp 
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(ScanViewOp op, Node n)
        { 
            HandleTableOpMetadata(op); 
            // Ideally, I should call this as the first statement, but that was causing too
            // many test diffs - because of the order in which the entitytypes/sets 
            // were being added. There is no semantic difference in calling this here
            VisitRelOpDefault(op, n);
            return n;
        } 

        ///  
        /// Processing for all JoinOps 
        /// 
        /// JoinOp 
        /// Current subtree
        /// 
        protected override Node VisitJoinOp(JoinBaseOp op, Node n)
        { 
            VisitChildren(n); // visit all my children first
 
            // 
            // Need a join elimination phase?
            // 
            if (op.OpType == OpType.InnerJoin || op.OpType == OpType.LeftOuterJoin)
            {
                m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination);
            } 

            // then check to see if we have any nested subqueries. This can only 
            // occur in the join condition. 
            // What we'll do in this case is to convert the join condition - "p" into
            //    p -> Exists(Filter(SingleRowTableOp, p)) 
            // We will then move the subqueries into an outerApply on the SingleRowTable
            List nestedSubqueries;
            if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries))
            { 
                PlanCompiler.Assert(n.Op.OpType == OpType.InnerJoin ||
                    n.Op.OpType == OpType.LeftOuterJoin || 
                    n.Op.OpType == OpType.FullOuterJoin, "unexpected op?"); 
                PlanCompiler.Assert(n.HasChild2, "missing second child to JoinOp?");
                Node joinCondition = n.Child2; 

                Node inputNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
                inputNode = AugmentWithSubqueries(inputNode, nestedSubqueries, true);
                Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), inputNode, joinCondition); 

                // update the join condition 
                // #479372: Build up a dummy project node over the input, as we always wrap the child of exists 
                Node projectNode = BuildDummyProjectForExists(filterNode);
                Node existsNode = m_command.CreateNode(m_command.CreateExistsOp(), projectNode); 

                n.Child2 = existsNode;
            }
 
            return n;
        } 
 
        /// 
        /// Perform default relop processing; Also "require" the join-elimination phase 
        /// 
        /// 
        /// 
        ///  
        protected override Node VisitApplyOp(ApplyBaseOp op, Node n)
        { 
            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); 
            return VisitRelOpDefault(op, n);
        } 

        /// 
        /// Visitor for UnnestOp. If the child has any subqueries, we need to convert this
        /// into an 
        ///    OuterApply(S, Unnest)
        /// unlike the other cases where the OuterApply will appear as the input of the node 
        ///  
        /// the unnestOp
        /// current subtree 
        /// modified subtree
        public override Node Visit(UnnestOp op, Node n)
        {
            VisitChildren(n); // visit all my children first 

            List nestedSubqueries; 
            if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries)) 
            {
                Node newNode = AugmentWithSubqueries(n, nestedSubqueries, false); 
                return newNode;
            }
            else
            { 
                return n;
            } 
 
        }
        ///  
        /// Can I eliminate this sort? I can, if the current path is *not* one of the
        /// following
        ///   TopN(Sort)
        ///   PhysicalProject(Sort) 
        ///
        /// We don't yet handle the TopN variant 
        ///  
        /// 
        private bool IsSortUnnecessary() 
        {
            Node ancestor = m_ancestors.Peek();
            PlanCompiler.Assert(ancestor != null, "unexpected SortOp as root node?");
 
            if (ancestor.Op.OpType == OpType.PhysicalProject)
            { 
                return false; 
            }
 
            return true;
        }

        ///  
        /// Visit a SortOp. Eliminate it if the path to this node is not one of
        /// PhysicalProject(Sort) or 
        /// TopN(Sort) 
        ///
        /// Otherwise, simply visit the child RelOp 
        ///
        /// 
        /// Current sortOp
        /// current subtree 
        /// possibly transformed subtree
        public override Node Visit(SortOp op, Node n) 
        { 
            // can I eliminate this sort
            if (this.IsSortUnnecessary()) 
            {
                return VisitNode(n.Child0);
            }
 
            // perform default processing
            return VisitRelOpDefault(op, n); 
        } 

        ///  
        /// Checks to see if this filterOp represents an IS OF (or IS OF ONLY) filter over a ScanTableOp
        /// 
        /// the filterOp node
        /// (OUT) the Type to restrict to 
        /// (OUT) was an ONLY clause specified
        ///  
        private bool IsOfTypeOverScanTable(Node n, out IsOfOp typeFilter) 
        {
            typeFilter = null; 

            //
            // Is the predicate an IsOf predicate
            // 
            IsOfOp isOfOp = n.Child1.Op as IsOfOp;
            if (isOfOp == null) 
            { 
                return false;
            } 
            //
            // Is the Input RelOp a ScanTableOp
            //
            ScanTableOp scanTableOp = n.Child0.Op as ScanTableOp; 
            if (scanTableOp == null || scanTableOp.Table.Columns.Count != 1)
            { 
                return false; 
            }
            // 
            // Is the argument to the IsOfOp the single column of the table?
            //
            VarRefOp varRefOp = n.Child1.Child0.Op as VarRefOp;
            if (varRefOp == null || varRefOp.Var != scanTableOp.Table.Columns[0]) 
            {
                return false; 
            } 

            // 
            // All conditions match. Return the info from the IsOf predicate
            //
            typeFilter = isOfOp;
            return true; 
        }
 
        ///  
        /// Handler for a FilterOp. Usually delegates to VisitRelOpDefault.
        /// 
        /// There's one special case - where we have an ISOF predicate over a ScanTable. In that case, we attempt
        /// to get a more "optimal" view; and return that optimal view
        ///
        ///  
        /// the filterOp
        /// the node tree 
        ///  
        public override Node Visit(FilterOp op, Node n)
        { 
            IsOfOp typeFilter;
            if (IsOfTypeOverScanTable(n, out typeFilter))
            {
                Node ret = ProcessScanTable(n.Child0, (ScanTableOp)n.Child0.Op, ref typeFilter); 
                if (typeFilter != null)
                { 
                    n.Child1 = VisitNode(n.Child1); 
                    n.Child0 = ret;
                    ret = n; 
                }
                return ret;
            }
            else 
            {
                return VisitRelOpDefault(op, n); 
            } 
        }
 
        /// 
        /// Visit a ProjectOp; if the input is a SortOp, we pullup the sort over
        /// the ProjectOp to ensure that we don't have nested sorts;
        ///  
        /// 
        ///  
        ///  
        public override Node Visit(ProjectOp op, Node n)
        { 
            PlanCompiler.Assert(n.HasChild0, "projectOp without input?");

            if (OpType.Sort == n.Child0.Op.OpType || OpType.ConstrainedSort == n.Child0.Op.OpType)
            { 
                SortBaseOp sort = (SortBaseOp)n.Child0.Op;
 
                IList sortChildren = new List(); 
                sortChildren.Add(n);
 
                //A ConstrainedSort has two other children besides the input and it needs to keep them.
                for (int i = 1; i < n.Child0.Children.Count; i++)
                {
                    sortChildren.Add(n.Child0.Children[i]); 
                }
 
                // Replace the ProjectOp input (currently the Sort node) with the input to the Sort. 
                n.Child0 = n.Child0.Child0;
 
                // Vars produced by the Sort input and used as SortKeys should be considered outputs
                // of the ProjectOp that now operates over what was the Sort input.
                foreach (SortKey key in sort.Keys)
                { 
                    op.Outputs.Set(key.Var);
                } 
 
                // Finally, pull the Sort over the Project by creating a new Sort node with the original
                // Sort as its Op and the Project node as its only child. This is sufficient because 
                // the ITreeGenerator ensures that the SortOp does not have any local VarDefs.
                return VisitNode(m_command.CreateNode(sort, sortChildren));
            }
 
            // perform default processing
            Node newNode = VisitRelOpDefault(op, n); 
            return newNode; 
        }
 
        #endregion

        #endregion
 
        #endregion
    } 
 
    /// 
    /// Finds the record (Row) types that we're projecting out of the query, and 
    /// ensures that we mark them as needing a nullable sentinel, so when we
    /// flatten them later we'll have one added.
    /// 
    internal class StructuredTypeNullabilityAnalyzer : ColumnMapVisitor> 
    {
        static internal StructuredTypeNullabilityAnalyzer Instance = new StructuredTypeNullabilityAnalyzer(); 
 
        /// 
        /// VarRefColumnMap 
        /// 
        /// 
        /// 
        ///  
        internal override void Visit(VarRefColumnMap columnMap, HashSet typesNeedingNullSentinel)
        { 
            AddTypeNeedingNullSentinel(typesNeedingNullSentinel, columnMap.Type); 
            base.Visit(columnMap, typesNeedingNullSentinel);
        } 

        /// 
        /// Recursively add any Row types to the list of types needing a sentinel.
        ///  
        /// 
        ///  
        private static void AddTypeNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage) 
        {
            if (md.TypeSemantics.IsCollectionType(typeUsage)) 
            {
                AddTypeNeedingNullSentinel(typesNeedingNullSentinel, TypeHelpers.GetElementTypeUsage(typeUsage));
            }
            else 
            {
                if (md.TypeSemantics.IsRowType(typeUsage) || md.TypeSemantics.IsComplexType(typeUsage)) 
                { 
                    MarkAsNeedingNullSentinel(typesNeedingNullSentinel, typeUsage);
                } 
                foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(typeUsage))
                {
                    AddTypeNeedingNullSentinel(typesNeedingNullSentinel, m.TypeUsage);
                } 
            }
        } 
 
        /// 
        /// Marks the given typeUsage as needing a null sentinel. 
        /// Call this method instead of calling Add over the HashSet directly, to ensure consistency.
        /// 
        /// 
        ///  
        internal static void MarkAsNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage)
        { 
            typesNeedingNullSentinel.Add(typeUsage.EdmType.Identity); 
        }
    } 

}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections.Generic; 
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Linq;
using System.Data.Common;
using md = System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees;
using System.Data.Metadata.Edm; 
using System.Data.Common.Utils; 
//
// The PreProcessor module is responsible for performing any required preprocessing 
// on the tree (and gathering information) before subsequent phases mess with the tree.
// The main aspects of preprocessing we perform here are
//   (a) gathering information about all structured types and entitysets referenced in the
//       query 
//   (b) Normalization of queries. Currently, we only handle scalar subqueries, and these
//       are converted into outer-apply subqueries 
//   (c) Translation of multiset constructors into subqueries of the form 
//       "select a from dual union all select b from dual ..."
// 
namespace System.Data.Query.PlanCompiler
{
    internal class DiscriminatorMapInfo {
        internal EntityTypeBase RootEntityType; 
        internal bool IncludesSubTypes;
        internal ExplicitDiscriminatorMap DiscriminatorMap; 
 
        internal DiscriminatorMapInfo(EntityTypeBase rootEntityType, bool includesSubTypes, ExplicitDiscriminatorMap discriminatorMap)
        { 
            RootEntityType = rootEntityType;
            IncludesSubTypes = includesSubTypes;
            DiscriminatorMap = discriminatorMap;
        } 

        ///  
        /// Merge the discriminatorMap info we just found with what we've already found. 
        ///
        /// In practice, if either the current or the new map is from an OfTypeOnly view, we 
        /// have to avoid the optimizations.
        ///
        /// If we have a new map that is a superset of the current map, then we can just swap
        /// the new map for the current one. 
        ///
        /// If the current map is tha super set of the new one ther's nothing to do. 
        /// 
        /// (Of course, if neither has changed, then we really don't need to look)
        ///  
        internal void Merge(EntityTypeBase neededRootEntityType, bool includesSubtypes, ExplicitDiscriminatorMap discriminatorMap)
        {
            // If what we've found doesn't exactly match what we are looking for we have more work to do
            if (RootEntityType != neededRootEntityType || IncludesSubTypes != includesSubtypes) 
            {
                if (!IncludesSubTypes || !includesSubtypes) 
                { 
                    // If either the original or the new map is from an of-type-only view we can't
                    // merge, we just have to not optimize this case. 
                    DiscriminatorMap = null;

                }
                if (TypeSemantics.IsSubTypeOf(RootEntityType, neededRootEntityType)) 
                {
                    // we're asking for a super type of existing type, and what we had is a proper 
                    // subset of it -we can replace the existing item. 
                    RootEntityType = neededRootEntityType;
                    DiscriminatorMap = discriminatorMap; 
                }
                if (!TypeSemantics.IsSubTypeOf(neededRootEntityType, RootEntityType))
                {
                    // If either the original or the new map is from an of-type-only view we can't 
                    // merge, we just have to not optimize this case.
                    DiscriminatorMap = null; 
                } 
            }
        } 
    }

    /// 
    /// The PreProcessor performs preprocessing of the ITree to facilitate processing 
    /// by later modules.
    ///  
    internal class PreProcessor : BasicOpVisitorOfNode 
    {
        #region private state 
        private PlanCompiler m_compilerState;
        private Command m_command { get { return m_compilerState.Command; } }

        // nested subquery tracking 
        private Stack m_ancestors;
        private Dictionary> m_nodeSubqueries; 
        // current nested view depth (0 for top-level query) 
        private int m_viewNestingLevel;
 
        // track list of referenced types, entitysets and entitycontainers
        private HashSet m_referencedEntityContainers;
        private List m_referencedEntitySets;
        private List m_referencedTypes; 
        private List m_freeFloatingEntityConstructorTypes;
        private HashSet m_typesNeedingNullSentinel; 
 
        // helper for rel properties
        private RelPropertyHelper m_relPropertyHelper; 

        // track discriminator metadata
        private bool m_suppressDiscriminatorMaps;
        private readonly Dictionary m_discriminatorMaps; 
        #endregion
 
        #region constructors 
        private PreProcessor(PlanCompiler planCompilerState)
        { 
            m_compilerState = planCompilerState;
            m_ancestors = new Stack();
            m_nodeSubqueries = new Dictionary>();
            m_viewNestingLevel = 0; 
            m_referencedEntitySets = new List();
            m_referencedTypes = new List(); 
            m_freeFloatingEntityConstructorTypes = new List(); 
            m_referencedEntityContainers = new HashSet();
            m_relPropertyHelper = new RelPropertyHelper(m_command.MetadataWorkspace, m_command.ReferencedRelProperties); 
            m_discriminatorMaps = new Dictionary();
            m_typesNeedingNullSentinel = new HashSet();
        }
        #endregion 

        #region public methods 
        ///  
        /// The driver routine. "Normalizes" the command;
        ///  
        /// plan compiler state
        /// type information about all types/sets referenced in the query
        internal static void Process(PlanCompiler planCompilerState,
            out StructuredTypeInfo typeInfo) 
        {
            PreProcessor preProcessor = new PreProcessor(planCompilerState); 
            preProcessor.Process(); 

            StructuredTypeInfo.Process(planCompilerState.Command, 
                preProcessor.m_referencedTypes,
                preProcessor.m_referencedEntitySets,
                preProcessor.m_freeFloatingEntityConstructorTypes,
                preProcessor.m_suppressDiscriminatorMaps ? null : preProcessor.m_discriminatorMaps, 
                preProcessor.m_relPropertyHelper,
                preProcessor.m_typesNeedingNullSentinel, 
                out typeInfo); 
        }
 
        #endregion

        #region private methods
 
        #region driver
        internal void Process() 
        { 
            m_command.Root = VisitNode(m_command.Root);
            // 
            // Add any Vars that are of structured type - if the Vars aren't
            // referenced via a VarRefOp, we end up losing them...
            //
            foreach (Var v in m_command.Vars) 
            {
                AddTypeReference(v.Type); 
            } 

            // 
            // If we have any "structured" types, then we need to run through NTE
            //
            if (m_referencedTypes.Count > 0)
            { 
                m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NTE);
 
                // 
                // Find any structured types that are projected at the top level, and
                // ensure that we can handle their nullability. 
                //
                PhysicalProjectOp ppOp = (PhysicalProjectOp)m_command.Root.Op; // this better be the case or we have other problems.
                ppOp.ColumnMap.Accept(StructuredTypeNullabilityAnalyzer.Instance, m_typesNeedingNullSentinel);
            } 
        }
        #endregion 
 
        #region private state maintenance
 
        #region type and set information

        /// 
        /// Mark this EntitySet as referenced in the query 
        /// 
        ///  
        private void AddEntitySetReference(EntitySet entitySet) 
        {
            m_referencedEntitySets.Add(entitySet); 
            if (!m_referencedEntityContainers.Contains(entitySet.EntityContainer))
            {
                m_referencedEntityContainers.Add(entitySet.EntityContainer);
            } 
        }
 
        ///  
        /// Mark this type as being referenced in the query, if it is a structured
        /// type or a collection of structured type 
        /// 
        /// type to reference
        private void AddTypeReference(TypeUsage type)
        { 
            if (TypeUtils.IsStructuredType(type) || TypeUtils.IsCollectionType(type))
            { 
                m_referencedTypes.Add(type); 
            }
        } 

        /// 
        /// Get the list of relationshipsets that can hold instances of the given relationshiptype
        /// 
        /// We identify the list of relationshipsets in the current list of entitycontainers that are
        /// of the given type. Since we don't yet support relationshiptype subtyping, this is a little 
        /// easier than the entity version 
        /// 
        /// the relationship type to look for 
        /// the list of relevant relationshipsets
        private List GetRelationshipSets(RelationshipType relType)
        {
            List relSets = new List(); 
            foreach (EntityContainer entityContainer in m_referencedEntityContainers)
            { 
                foreach (EntitySetBase set in entityContainer.BaseEntitySets) 
                {
                    RelationshipSet relSet = set as RelationshipSet; 
                    if (relSet != null &&
                        relSet.ElementType.Equals(relType))
                    {
                        relSets.Add(relSet); 
                    }
                } 
            } 
            return relSets;
        } 

        /// 
        /// Find all entitysets (that are reachable in the current query) that can hold instances that
        /// are *at least* of type "entityType". 
        /// An entityset ES of type T1 can hold instances that are at least of type T2, if one of the following
        /// is true 
        ///   - T1 is a subtype of T2 
        ///   - T2 is a subtype of T1
        ///   - T1 is equal to T2 
        /// 
        /// the desired entity type
        /// list of all entitysets of the desired shape
        private List GetEntitySets(TypeUsage entityType) 
        {
            List sets = new List(); 
            foreach (EntityContainer container in m_referencedEntityContainers) 
            {
                foreach (EntitySetBase baseSet in container.BaseEntitySets) 
                {
                    EntitySet set = baseSet as EntitySet;
                    if (set != null &&
                        (set.ElementType.Equals(entityType.EdmType) || 
                         TypeSemantics.IsSubTypeOf(entityType.EdmType, set.ElementType) ||
                         TypeSemantics.IsSubTypeOf(set.ElementType, entityType.EdmType))) 
                    { 
                        sets.Add(set);
                    } 
                }
            }

            return sets; 
        }
 
        #endregion 

        #region Subquery Handling 
        /// 
        /// Adds a subquery to the list of subqueries for the relOpNode
        /// 
        /// the RelOp node 
        /// the subquery
        private void AddSubqueryToRelOpNode(Node relOpNode, Node subquery) 
        { 
            List nestedSubqueries;
 
            // Create an entry in the map if there isn't one already
            if (!m_nodeSubqueries.TryGetValue(relOpNode, out nestedSubqueries))
            {
                nestedSubqueries = new List(); 
                m_nodeSubqueries[relOpNode] = nestedSubqueries;
            } 
            // add this subquery to the list of currently tracked subqueries 
            nestedSubqueries.Add(subquery);
        } 

        /// 
        /// Add a subquery to the "parent" relop node
        ///  
        /// the output var to be used - at the current location - in lieu of the subquery
        /// the subquery to move 
        /// a var ref node for the var returned from the subquery 
        private Node AddSubqueryToParentRelOp(Var outputVar, Node subquery)
        { 
            Node ancestor = FindRelOpAncestor();
            PlanCompiler.Assert(ancestor != null, "no ancestors found?");
            AddSubqueryToRelOpNode(ancestor, subquery);
 
            subquery = m_command.CreateNode(m_command.CreateVarRefOp(outputVar));
            return subquery; 
        } 

        ///  
        /// Find the first RelOp node that is in my ancestral path.
        /// If I see a PhysicalOp, then I don't have a RelOp parent
        /// 
        /// the first RelOp node 
        private Node FindRelOpAncestor()
        { 
            foreach (Node n in m_ancestors) 
            {
                if (n.Op.IsRelOp) 
                {
                    return n;
                }
                else if (n.Op.IsPhysicalOp) 
                {
                    return null; 
                } 
            }
            return null; 
        }
        #endregion

        #endregion 

        #region View Expansion 
        ///  
        /// Gets the "defining" query for an S-Space entityset.
        /// We simply convert this into 
        ///     select Type(c1, c2, ...) from Set
        ///
        /// A *key* assumption here is that the set is not polymorphic - otherwise, our smplistic
        /// constructor model above does not suffice 
        /// 
        /// current scan table node 
        /// the ScanTableOp 
        /// the defining query for this set
        private Node GetDefiningQueryForSSpaceSet(Node node, ScanTableOp scanTableOp) 
        {
            //
            // We have an S-Space entityset. Build up a simple "select * from T"
            // node tree on top of the base entityset 
            //
            EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent; 
            EntityType entityType = entitySet.ElementType as EntityType; 
            // For relationshipsets, do nothing
            if (entityType != null) 
            {
                Table baseTable = m_command.CreateTableInstance(scanTableOp.Table.TableMetadata);
                ScanTableOp baseTableOp = m_command.CreateScanTableOp(baseTable);
                Node baseTableNode = m_command.CreateNode(baseTableOp); 
                Var col = baseTable.Columns[0];
                List constructorArgs = new List(); 
                foreach (EdmProperty p in entityType.Properties) 
                {
                    Node arg = m_command.CreateNode(m_command.CreatePropertyOp(p), 
                        m_command.CreateNode(m_command.CreateVarRefOp(col)));
                    constructorArgs.Add(arg);
                }
                Node constructor = m_command.CreateNode( 
                    m_command.CreateNewInstanceOp(TypeUsage.Create(entityType)),
                    constructorArgs); 
                Var projectVar; 
                node = m_command.BuildProject(baseTableNode, constructor, out projectVar);
            } 

            return node;
        }
 
        /// 
        /// Convert a CQT command into an IQT subtree. 
        /// We expect the CQT command to be a query command tree. This is a 3-step 
        /// process
        ///   * We first run through the standard CQT-IQT convertor. 
        ///   * We then strip off the root of the IQT (the PhysicalProjectOp)
        ///   * Finally, we copy the IQT into our current IQT
        ///
        /// When we have metadata caching of IQTs (for views), instead of CQTs, 
        /// we can get rid of steps 1 and 2.
        ///  
        /// the view 
        /// an IQT subtree in the current command
        private Node ConvertToInternalTree(System.Data.Mapping.ViewGeneration.GeneratedView generatedView) 
        {
            Node ret;
            Node sourceIqt = generatedView.GetInternalTree(m_command.MetadataWorkspace);
            ret = OpCopier.Copy(m_command, sourceIqt); 
            return ret;
        } 
 
        /// 
        /// Gets the "expanded" query mapping view for the specified C-Space entity set 
        /// 
        /// The current node
        /// The scanTableOp that references the entity set
        ///  
        ///     An optional type filter to apply to the generated view.
        ///     Set to null on return if the generated view renders the type filter superfluous. 
        ///  
        /// A node that is the root of the new expanded view
        private Node ExpandView(Node node, ScanTableOp scanTableOp, ref IsOfOp typeFilter) 
        {
            EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent;
            PlanCompiler.Assert(entitySet != null, "The target of a ScanTableOp must reference an EntitySet to be used with ExpandView");
            PlanCompiler.Assert(entitySet.EntityContainer.DataSpace == DataSpace.CSpace, "Store entity sets cannot have Query Mapping Views and should not be used with ExpandView"); 

            if(typeFilter != null && 
               !typeFilter.IsOfOnly && 
                TypeSemantics.IsSubTypeOf(entitySet.ElementType, typeFilter.IsOfType.EdmType))
            { 
                //
                // If a type filter is being applied to the ScanTableOp, but that filter is asking
                // for all elements that are the same type or a supertype of the element type of the
                // target entity set, then the type filter is a no-op and can safely be discarded - 
                // IF AND ONLY IF the type filter is 'OfType' - which includes subtypes - and NOT
                // 'IsOfOnly' - which requires an exact type match, and so does not include subtypes. 
                // 
                typeFilter = null;
            } 

            //
            // Call the GetGeneratedView method to retrieve the query mapping view for the extent referenced
            // by the ScanTableOp. The actual method used to do this differs depending on whether the default 
            // Query Mapping View is sufficient or a targeted view that only filters by element type is required.
            // 
            System.Data.Mapping.ViewGeneration.GeneratedView definingQuery = null; 
            EntityTypeBase requiredType = scanTableOp.Table.TableMetadata.Extent.ElementType;
            bool includeSubtypes = true; 
            if(typeFilter != null)
            {
                //
                // A type filter is being applied to the ScanTableOp; it may be possible to produce 
                // an optimized expansion of the view based on type-specific views generated for the
                // C-Space entity set. 
                // The type for which the view should be tuned is the 'OfType' specified on the type filter. 
                // If the type filter is an 'IsOfOnly' filter then the view should NOT include subtypes of the required type.
                // 
                requiredType = (EntityTypeBase)typeFilter.IsOfType.EdmType;
                includeSubtypes = !typeFilter.IsOfOnly;
                if(m_command.MetadataWorkspace.TryGetGeneratedViewOfType(entitySet, requiredType, includeSubtypes, out definingQuery))
                { 
                    //
                    // At this point a type-specific view was found that satisifies the type filter's 
                    // constraints in terms of required type and whether subtypes should be included; 
                    // the type filter itself is now unnecessary and should be set to null indicating
                    // that it can be safely removed (see ProcessScanTableOp and Visit(FilterOp) for this). 
                    //
                    typeFilter = null;
                }
            } 

            // 
            // If a generated view has not been obtained at this point then either: 
            // - A type filter was specified but no type-specific view exists that satisfies its constraints.
            //   OR 
            // - No type filter was specified.
            // In either case the default query mapping view for the referenced entity set should now be retrieved.
            //
            if(null == definingQuery) 
            {
                definingQuery = m_command.MetadataWorkspace.GetGeneratedView(entitySet); 
            } 

            // 
            // If even the default query mapping view was not found then we cannot continue.
            // This implies that the set was not mapped, which should not be allowed, therefore
            // a retail assert is used here instead of a regular exception.
            // 
            PlanCompiler.Assert(definingQuery != null, Entity.Strings.ADP_NoQueryMappingView(entitySet.EntityContainer.Name, entitySet.Name));
 
            // 
            // At this point we're guaranteed to have found a defining query for the view.
            // We're now going to convert this into an IQT, and then copy it into our own IQT. 
            //
            Node ret = ConvertToInternalTree(definingQuery);

            // 
            // Make sure we're tracking what we've asked any discriminator maps to contain.
            // 
            DetermineDiscriminatorMapUsage(ret, entitySet, requiredType, includeSubtypes); 

            // 
            // Build up a ScanViewOp to "cap" the defining query below
            //
            ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table);
            ret = m_command.CreateNode(scanViewOp, ret); 

            return ret; 
        } 

 
        /// 
        /// If the discrminator map we're already tracking for this type (in this entityset)
        /// isn't already rooted at our required type, then we have to suppress the use of
        /// the descriminator maps when we constrct the structuredtypes; see SQLBUDT #615744 
        /// 
        private void DetermineDiscriminatorMapUsage(Node viewNode, EntitySetBase entitySet, EntityTypeBase rootEntityType, bool includeSubtypes) { 
            ExplicitDiscriminatorMap discriminatorMap = null; 

            // we expect the view to be capped with a project; we're just being careful here. 
            if (viewNode.Op.OpType == OpType.Project)
            {
                DiscriminatedNewEntityOp discriminatedNewEntityOp = viewNode.Child1.Child0.Child0.Op as DiscriminatedNewEntityOp;
 
                if (null != discriminatedNewEntityOp)
                { 
                    discriminatorMap = discriminatedNewEntityOp.DiscriminatorMap; 
                }
            } 

            DiscriminatorMapInfo discriminatorMapInfo;
            if (!m_discriminatorMaps.TryGetValue(entitySet, out discriminatorMapInfo))
            { 
                if (null == rootEntityType)
                { 
                    rootEntityType = entitySet.ElementType; 
                    includeSubtypes = true;
                } 
                discriminatorMapInfo = new DiscriminatorMapInfo(rootEntityType, includeSubtypes, discriminatorMap);
                m_discriminatorMaps.Add(entitySet, discriminatorMapInfo);
            }
            else 
            {
                discriminatorMapInfo.Merge(rootEntityType, includeSubtypes, discriminatorMap); 
            } 
        }
 
        #endregion

        #region NavigateOp rewrites
        ///  
        /// Rewrites a NavigateOp tree in the following fashion
        ///   SELECT VALUE r.ToEnd 
        ///   FROM (SELECT VALUE r1 FROM RS1 as r1 
        ///         UNION ALL
        ///         SELECT VALUE r2 FROM RS2 as r2 
        ///         ...
        ///         SELECT VALUE rN FROM RSN as rN) as r
        ///   WHERE r.FromEnd = sourceRef
        /// 
        ///  RS1, RS2 etc. are the set of all relationshipsets that can hold instances of the specified
        ///  relationship type. "sourceRef" is the single (ref-type) argument to the NavigateOp that 
        ///  represents the from-end of the navigation traversal 
        /// If the toEnd is multi-valued, then we stick a Collect(PhysicalProject( over the subquery above
        /// 
        /// A couple of special cases.
        ///    If no relationship sets can be found, we return a NULL (if the
        /// toEnd is single-valued), or an empty multiset (if the toEnd is multi-valued)
        /// 
        ///    If the toEnd is single-valued, *AND* the input Op is a GetEntityRefOp, then
        /// we convert the NavigateOp into a RelPropertyOp over the entity. 
        ///  
        /// the navigateOp tree
        /// the navigateOp 
        /// the output var produced by the subquery (ONLY if the to-End is single-valued)
        /// the resulting node
        private Node RewriteNavigateOp(Node navigateOpNode, NavigateOp navigateOp, out Var outputVar)
        { 
            outputVar = null;
 
            // 
            // Currently, navigation of composition relationships is not supported.
            // 
            if (!Helper.IsAssociationType(navigateOp.Relationship))
            {
                throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_RelNav_NoCompositions);
            } 

            // 
            // If the input to the navigateOp is a GetEntityRefOp, and the navigation 
            // is to the 1-end of the relationship, convert this into a RelPropertyOp instead - operating on the
            // input child to the GetEntityRefOp 
            //
            if (navigateOpNode.Child0.Op.OpType == OpType.GetEntityRef &&
                (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne ||
                navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One)) 
            {
                PlanCompiler.Assert(m_command.IsRelPropertyReferenced(navigateOp.RelProperty), 
                    "Unreferenced rel property? " + navigateOp.RelProperty); 
                Op relPropertyOp = m_command.CreateRelPropertyOp(navigateOp.RelProperty);
                Node relPropertyNode = m_command.CreateNode(relPropertyOp, 
                    navigateOpNode.Child0.Child0);
                return relPropertyNode;
            }
 
            List relationshipSets = GetRelationshipSets(navigateOp.Relationship);
 
            // 
            // Special case: when no relationshipsets can be found. Return NULL or an empty multiset,
            //   depending on the multiplicity of the toEnd 
            //
            if (relationshipSets.Count == 0)
            {
                // 
                // If we're navigating to the 1-end of the relationship, then simply return a null constant
                // 
                if (navigateOp.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many) 
                {
                    return m_command.CreateNode(m_command.CreateNullOp(navigateOp.Type)); 
                }
                else // return an empty set
                {
                    return m_command.CreateNode(m_command.CreateNewMultisetOp(navigateOp.Type)); 
                }
            } 
 
            //
            // Build up a UNION-ALL ladder over all the relationshipsets 
            //
            List scanTableNodes = new List();
            List scanTableVars = new List();
            foreach (RelationshipSet relSet in relationshipSets) 
            {
                TableMD tableMD = Command.CreateTableDefinition(relSet); 
                ScanTableOp tableOp = m_command.CreateScanTableOp(tableMD); 
                Node branchNode = m_command.CreateNode(tableOp);
                Var branchVar = tableOp.Table.Columns[0]; 
                scanTableVars.Add(branchVar);
                scanTableNodes.Add(branchNode);
            }
 
            Node unionAllNode = null;
            Var unionAllVar; 
            m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); 

            // 
            // Now build up the predicate
            //
            Node targetEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.ToEnd),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node sourceEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.FromEnd),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node predicateNode = m_command.BuildComparison(OpType.EQ, navigateOpNode.Child0, sourceEnd); 
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
                unionAllNode, predicateNode); 
            Var projectVar;
            Node projectNode = m_command.BuildProject(filterNode, targetEnd, out projectVar);

            // 
            // Finally, some magic about single-valued vs collection-valued ends
            // 
            Node ret; 
            if (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
            { 
                ret = m_command.BuildCollect(projectNode, projectVar);
            }
            else
            { 
                ret = projectNode;
                outputVar = projectVar; 
            } 

            return ret; 
        }
        #endregion

        #region DerefOp Rewrites 
        /// 
        /// Build up a node tree that represents the set of instances from the given table that are at least 
        /// of the specified type ("ofType"). If "ofType" is NULL, then all rows are returned 
        ///
        /// Return the outputVar from the nodetree 
        /// 
        /// the entityset or relationshipset to scan over
        /// the element types we're interested in
        /// the output var produced by this node tree 
        /// the node tree
        private Node BuildOfTypeTable(EntitySetBase entitySet, TypeUsage ofType, out Var resultVar) 
        { 
            TableMD tableMetadata = Command.CreateTableDefinition(entitySet);
            ScanTableOp tableOp = m_command.CreateScanTableOp(tableMetadata); 
            Node tableNode = m_command.CreateNode(tableOp);
            Var tableVar = tableOp.Table.Columns[0];

            Node resultNode; 
            //
            // Build a logical "oftype" expression - simply a filter predicate 
            // 
            if ((ofType != null) && !entitySet.ElementType.EdmEquals(ofType.EdmType))
            { 
                m_command.BuildOfTypeTree(tableNode, tableVar, ofType, true, out resultNode, out resultVar);
            }
            else
            { 
                resultNode = tableNode;
                resultVar = tableVar; 
            } 

            return resultNode; 
        }

        /// 
        /// Produces a relop tree that "logically" produces the target of the derefop. In essence, this gets rewritten 
        /// into
        ///      SELECT VALUE e 
        ///      FROM (SELECT VALUE e0 FROM OFTYPE(ES0, T) as e0 
        ///            UNION ALL
        ///            SELECT VALUE e1 FROM OFTYPE(ES1, T) as e1 
        ///            ...
        ///            SELECT VALUE eN from OFTYPE(ESN, T) as eN)) as e
        ///      WHERE REF(e) = myRef
        /// 
        /// "T" is the target type of the Deref, and myRef is the (single) argument to the DerefOp
        /// 
        /// ES0, ES1 etc. are all the EntitySets that could hold instances that are at least of type "T". We identify this list of sets 
        /// by looking at all entitycontainers referenced in the query, and looking at all entitysets in those
        /// containers that are of the right type 
        /// An EntitySet ES (of entity type X) can hold instances of T, if one of the following is true
        ///   - T is a subtype of X
        ///   - X is equal to T
        /// Our situation is a little trickier, since we also need to look for cases where X is a subtype of T. 
        /// 
        /// the derefOp subtree 
        /// the derefOp 
        /// output var produced
        /// the subquery described above 
        private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar)
        {
            TypeUsage entityType = derefOp.Type;
            List targetEntitySets = GetEntitySets(entityType); 
            if (targetEntitySets.Count == 0)
            { 
                // We didn't find any entityset that could match this. Simply return a null-value 
                outputVar = null;
                return m_command.CreateNode(m_command.CreateNullOp(entityType)); 
            }

            List scanTableNodes = new List();
            List scanTableVars = new List(); 
            foreach (EntitySet entitySet in targetEntitySets)
            { 
                Var tableVar; 
                Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
 
                scanTableNodes.Add(tableNode);
                scanTableVars.Add(tableVar);
            }
            Node unionAllNode; 
            Var unionAllVar;
            m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); 
 
            //
            // Finally build up the key comparison predicate 
            //
            Node entityRefNode = m_command.CreateNode(
                m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode);
            Node filterNode = m_command.CreateNode( 
                m_command.CreateFilterOp(), 
                unionAllNode,
                keyComparisonPred); 

            outputVar = unionAllVar;
            return filterNode;
        } 
        #endregion
 
        #region NavigationProperty Rewrites 

        ///  
        /// Find the entityset that corresponds to the specified end of the relationship.
        ///
        /// We must find one - else we assert.
        ///  
        /// the relationshipset
        /// the destination end of the relationship traversal 
        /// the entityset corresponding to the target end 
        private static EntitySetBase FindTargetEntitySet(RelationshipSet relationshipSet, RelationshipEndMember targetEnd)
        { 
            EntitySetBase entitySet = null;

            AssociationSet associationSet = (AssociationSet)relationshipSet;
            // find the corresponding entityset 
            entitySet = null;
            foreach (AssociationSetEnd e in associationSet.AssociationSetEnds) 
            { 
                if (e.CorrespondingAssociationEndMember.EdmEquals(targetEnd))
                { 
                    entitySet = e.EntitySet;
                    break;
                }
            } 
            PlanCompiler.Assert(entitySet != null, "Could not find entityset for relationshipset " + relationshipSet + ";association end " + targetEnd);
            return entitySet; 
        } 

 
        /// 
        /// Builds up a join between the relationshipset and the entityset corresponding to its toEnd. In essence,
        /// we produce
        ///    SELECT r, e 
        ///    FROM RS as r, OFTYPE(ES, T) as e
        ///    WHERE r.ToEnd = Ref(e) 
        /// 
        /// "T" is the entity type of the toEnd of the relationship.
        ///  
        /// the relationshipset
        /// the toEnd of the relationship
        /// the var representing the relationship instance ("r") in the output subquery
        /// the var representing the entity instance ("e") in the output subquery 
        /// the join subquery described above
        private Node BuildJoinForNavProperty(RelationshipSet relSet, RelationshipEndMember end, 
            out Var rsVar, out Var esVar) 
        {
            EntitySetBase entitySet = FindTargetEntitySet(relSet, end); 

            //
            // Build out the ScanTable ops for the relationshipset and the entityset. Add the
            // 
            Node asTableNode = BuildOfTypeTable(relSet, null, out rsVar);
            Node esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar); 
 
            //
            // Build up a join between the entityset and the associationset; join on the to-end 
            //
            Node joinPredicate = m_command.BuildComparison(OpType.EQ,
                m_command.CreateNode(m_command.CreateGetEntityRefOp(end.TypeUsage), m_command.CreateNode(m_command.CreateVarRefOp(esVar))),
                m_command.CreateNode(m_command.CreatePropertyOp(end), m_command.CreateNode(m_command.CreateVarRefOp(rsVar))) 
                );
 
            Node joinNode = m_command.CreateNode(m_command.CreateInnerJoinOp(), 
                asTableNode, esTableNode, joinPredicate);
 
            return joinNode;
        }

        ///  
        /// Rewrite a NavPropertyOp when the target end of the nav property has multiplicity
        /// of one (or zero..one). 
        /// We simply pick up the corresponding rel property from the input entity, and 
        /// apply a deref operation
        ///     NavProperty(e, n) => deref(relproperty(e, r)) 
        /// where e is the entity expression, n is the nav-property, and r is the corresponding
        /// rel-property
        /// 
        /// the rel-property describing the navigation 
        /// entity instance that we're starting the traversal from
        /// type of the target entity 
        /// a rewritten subtree 
        private Node RewriteToOneNavigationProperty(RelProperty relProperty,
            Node sourceEntityNode, TypeUsage resultType) 
        {
            RelPropertyOp relPropertyOp = m_command.CreateRelPropertyOp(relProperty);
            Node relPropertyNode = m_command.CreateNode(relPropertyOp, sourceEntityNode);
            DerefOp derefOp = m_command.CreateDerefOp(resultType); 
            Node derefNode = m_command.CreateNode(derefOp, relPropertyNode);
 
            return derefNode; 
        }
 
        /// 
        /// Rewrite a NavigationProperty when the relationship is a 1:N relationship.
        /// In essence, we find all the relevant target entitysets, and then compare the
        /// rel-property on the target end with the source ref 
        ///
        /// Converts 
        ///   NavigationProperty(e, r) 
        /// into
        ///   SELECT VALUE t 
        ///   FROM (SELECT VALUE e1 FROM ES1 as e1
        ///         UNION ALL
        ///         SELECT VALUE e2 FROM ES2 as e2
        ///         UNION ALL 
        ///         ...
        ///         ) as t 
        ///   WHERE RelProperty(t, r') = GetEntityRef(e) 
        ///
        /// r' is the inverse-relproperty for r 
        ///
        /// We also build out a CollectOp over the subquery above, and return that
        /// 
        /// the rel-property describing the relationship traversal 
        /// the list of relevant relationshipsets
        /// node tree corresponding to the source entity ref 
        /// type of the result 
        /// the rewritten subtree
        private Node RewriteOneToManyNavigationProperty(RelProperty relProperty, 
            List relationshipSets,
            Node sourceRefNode, TypeUsage resultType)
        {
            PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here"); 
            PlanCompiler.Assert(relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many,
                "Expected source end multiplicity to be one. Found 'Many' instead " + relProperty); 
            Node ret = null; 

            // 
            // We convert the
            //
            TypeUsage entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage);
            List scanTableNodes = new List(relationshipSets.Count); 
            List scanTableVars = new List(relationshipSets.Count);
            foreach (RelationshipSet r in relationshipSets) 
            { 
                EntitySetBase entitySet = FindTargetEntitySet(r, relProperty.ToEnd);
                Var tableVar; 
                Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);

                scanTableNodes.Add(tableNode);
                scanTableVars.Add(tableVar); 
            }
 
            // 
            // Build the union-all node
            // 
            Node unionAllNode;
            Var unionAllVar;
            m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
 
            //
            // Now build up the appropriate filter. Select out the relproperty from the other end 
            // 
            RelProperty inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd);
            PlanCompiler.Assert(m_command.IsRelPropertyReferenced(inverseRelProperty), 
                "Unreferenced rel property? " + inverseRelProperty);
            Node inverseRelPropertyNode = m_command.CreateNode(
                m_command.CreateRelPropertyOp(inverseRelProperty),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); 
            Node predicateNode = m_command.BuildComparison(OpType.EQ,
                sourceRefNode, inverseRelPropertyNode); 
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), 
                unionAllNode, predicateNode);
 
            //
            // The magic of collections...
            //
            ret = m_command.BuildCollect(filterNode, unionAllVar); 

            return ret; 
        } 

        ///  
        /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r))
        /// where "r" is a many-to-many relationship
        ///
        /// We essentially produce the following subquery 
        ///   SELECT VALUE x.e
        ///   FROM (SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1) 
        ///         UNION ALL 
        ///         SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
        ///         ... 
        ///         ) as x
        ///   WHERE x.r.FromEnd = sourceRef
        ///
        /// RS1, RS2 etc. are the relevant relationshipsets 
        /// ES1, ES2 etc. are the corresponding entitysets for the toEnd of the relationship
        /// sourceRef is the ref argument 
        /// T is the type of the target-end of the relationship 
        ///
        /// We then build a CollectOp over the subquery above 
        /// 
        /// the rel property to traverse
        /// list of relevant relationshipsets
        /// source ref 
        /// type of the result
        ///  
        private Node RewriteManyToManyNavigationProperty(RelProperty relProperty, 
            List relationshipSets,
            Node sourceRefNode, TypeUsage resultType) 
        {
            PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
            PlanCompiler.Assert(relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many &&
                relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many, 
                "Expected target end multiplicity to be 'many'. Found " + relProperty + "; multiplicity = " + relProperty.ToEnd.RelationshipMultiplicity);
 
            Node ret = null; 

            List joinNodes = new List(relationshipSets.Count); 
            List outputVars = new List(relationshipSets.Count * 2);
            foreach (RelationshipSet r in relationshipSets)
            {
                Var rsVar; 
                Var esVar;
                Node joinNode = BuildJoinForNavProperty(r, relProperty.ToEnd, out rsVar, out esVar); 
                joinNodes.Add(joinNode); 
                outputVars.Add(rsVar);
                outputVars.Add(esVar); 
            }

            //
            // Build the union-all node 
            //
            Node unionAllNode; 
            IList unionAllVars; 
            m_command.BuildUnionAllLadder(joinNodes, outputVars, out unionAllNode, out unionAllVars);
 
            //
            // Now build out the filterOp over the left-side var
            //
            Node rsSourceRefNode = m_command.CreateNode(m_command.CreatePropertyOp(relProperty.FromEnd), 
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVars[0])));
            Node predicate = m_command.BuildComparison(OpType.EQ, 
                sourceRefNode, rsSourceRefNode); 
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
                unionAllNode, predicate); 

            //
            // Finally, build out a project node that only projects out the entity side
            // 
            Node projectNode = m_command.BuildProject(filterNode, new Var[] { unionAllVars[1] }, new Node[] { });
 
            // 
            // Build a collectOp over the project node
            // 
            ret = m_command.BuildCollect(projectNode, unionAllVars[1]);

            return ret;
        } 

        ///  
        /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r)) 
        ///
        /// We handle three cases here, depending on the kind of relationship we're 
        /// dealing with.
        ///   - *:1 relationships
        ///   - N:1 relationships
        ///   - N:M relationships 
        ///
        ///  
        /// the navigation property 
        /// the input ref to start the traversal
        /// the result type of the expression 
        /// the rewritten tree
        private Node RewriteNavigationProperty(NavigationProperty navProperty,
            Node sourceEntityNode, TypeUsage resultType)
        { 
            Node ret = null;
            RelProperty relProperty = new RelProperty(navProperty.RelationshipType, navProperty.FromEndMember, navProperty.ToEndMember); 
            PlanCompiler.Assert(m_command.IsRelPropertyReferenced(relProperty) || (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many), 
                "Unreferenced rel property? " + relProperty);
            // 
            // Case 1: The (target end of the) nav property has a multiplicity of 1 (or 0..1)
            //   (doesn't matter what the sourceEnd multiplicity is)
            //
            if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One || 
                relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne)
            { 
                ret = RewriteToOneNavigationProperty(relProperty, sourceEntityNode, resultType); 
                return ret;
            } 

            //
            // Otherwise, the target end is multi-valued. We need to deal with
            // 2 cases here. A N:1 relationship or a N:M relationship 
            //
 
            // 
            // Find the list of all relationships that could satisfy this relationship
            // If we find no matching relationship set, simply return an empty collection 
            //
            List relationshipSets = GetRelationshipSets(relProperty.Relationship);
            if (relationshipSets.Count == 0)
            { 
                // return an empty set
                return m_command.CreateNode(m_command.CreateNewMultisetOp(resultType)); 
            } 

            // 
            // Build out a ref over the source entity now
            //
            Node sourceRefNode = m_command.CreateNode(
                m_command.CreateGetEntityRefOp(relProperty.FromEnd.TypeUsage), 
                sourceEntityNode);
 
            // 
            // Are we dealing with a many-to-many relationship ?
            // 
            if (relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
            {
                ret = RewriteManyToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType);
            } 
            else
            { 
                ret = RewriteOneToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType); 
            }
 
            return ret;
        }

        #endregion 

        #region visitor helpers 
 
        /// 
        /// Extends the base class implementation of VisitChildren. 
        /// Wraps the call to visitchildren() by first adding the current node
        /// to the stack of "ancestors", and then popping back the node at the end
        /// 
        /// Current node 
        protected override void VisitChildren(Node n)
        { 
            // Push the current node onto the stack 
            m_ancestors.Push(n);
 
            for (int i = 0; i < n.Children.Count; i++)
            {
                n.Children[i] = VisitNode(n.Children[i]);
            } 

            m_ancestors.Pop(); 
        } 

        #endregion 

        #region visitor methods

        #region ScalarOps 

        ///  
        /// Default handler for scalar Ops. Simply traverses the children, 
        /// and also identifies any structured types along the way
        ///  
        /// the ScalarOp
        /// current subtree
        /// the possibly modified node
        protected override Node VisitScalarOpDefault(ScalarOp op, Node n) 
        {
            VisitChildren(n); // visit my children 
 
            // keep track of referenced types
            AddTypeReference(op.Type); 

            return n;
        }
 
        /// 
        /// Rewrite a DerefOp subtree. We have two cases to consider here. 
        /// We call RewriteDerefOp to return a subtree (and an optional outputVar). 
        /// If the outputVar is null, then we simply return the subtree produced by those calls.
        /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar 
        /// in its place.
        ///
        /// As an example,
        ///    select deref(e) from T 
        /// gets rewritten into
        ///    select v from T OuterApply X 
        /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X 
        ///
        ///  
        /// the derefOp
        /// the deref subtree
        /// the rewritten tree
        public override Node Visit(DerefOp op, Node n) 
        {
            Var outputVar; 
 
            VisitScalarOpDefault(op, n);
 
            Node ret = RewriteDerefOp(n, op, out outputVar);
            ret = VisitNode(ret);

            if (outputVar != null) 
            {
                ret = AddSubqueryToParentRelOp(outputVar, ret); 
            } 

            return ret; 
        }

        /// 
        /// Processing for an ElementOp. Replaces this by the corresponding Var from 
        /// the subquery, and adds the subquery to the list of currently tracked subqueries
        ///  
        /// the elementOp 
        /// current subtree
        /// the Var from the subquery 
        public override Node Visit(ElementOp op, Node n)
        {
            VisitScalarOpDefault(op, n); // default processing
 
            // get to the subquery...
            Node subQueryRelOp = n.Child0; 
            ProjectOp projectOp = (ProjectOp)subQueryRelOp.Op; 
            PlanCompiler.Assert(projectOp.Outputs.Count == 1, "input to ElementOp has more than one output var?");
            Var projectVar = projectOp.Outputs.First; 

            Node ret = AddSubqueryToParentRelOp(projectVar, subQueryRelOp);
            return ret;
        } 

        ///  
        /// Translate Exists(X) into Exists(select 0 from X) 
        /// 
        ///  
        /// 
        /// 
        public override Node Visit(ExistsOp op, Node n)
        { 
            VisitChildren(n);
 
            // Build up a dummy project node over the input 
            n.Child0 = BuildDummyProjectForExists(n.Child0);
 
            return n;
        }

        ///  
        /// Build Project(select 0 from child).
        ///  
        ///  
        /// 
        private Node BuildDummyProjectForExists(Node child) 
        {
            Var newVar;
            Node projectNode = m_command.BuildProject(
                child, 
                m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.BooleanType, true)),
                out newVar); 
            return projectNode; 
        }
 
        /// 
        /// Build up an unnest above a scalar op node
        ///    X => unnest(X)
        ///  
        /// the scalarop collection node
        /// the unnest node 
        private Node BuildUnnest(Node collectionNode) 
        {
            PlanCompiler.Assert(collectionNode.Op.IsScalarOp, "non-scalar usage of Unnest?"); 
            PlanCompiler.Assert(md.TypeSemantics.IsCollectionType(collectionNode.Op.Type), "non-collection usage for Unnest?");

            Var newVar;
            Node varDefNode = m_command.CreateVarDefNode(collectionNode, out newVar); 
            UnnestOp unnestOp = m_command.CreateUnnestOp(newVar);
            Node unnestNode = m_command.CreateNode(unnestOp, varDefNode); 
 
            return unnestNode;
        } 

        /// 
        /// Is this function a TVF?
        ///  
        /// current function op
        /// true, if the function returns a collection 
        private static bool IsCollectionFunction(FunctionOp op) 
        {
            return md.TypeSemantics.IsCollectionType(op.Type); 
        }

        /// 
        /// Converts a reference to a TVF, by the following 
        ///    Collect(PhysicalProject(Unnest(Func)))
        ///  
        /// current function op 
        /// current function subtree
        /// the new expression that corresponds to the TVF 
        private Node VisitCollectionFunction(FunctionOp op, Node n)
        {
            PlanCompiler.Assert(IsCollectionFunction(op), "non-TVF function?");
 
            Node unnestNode = BuildUnnest(n);
            UnnestOp unnestOp = unnestNode.Op as UnnestOp; 
            PhysicalProjectOp projectOp = m_command.CreatePhysicalProjectOp(unnestOp.Table.Columns[0]); 
            Node projectNode = m_command.CreateNode(projectOp, unnestNode);
            CollectOp collectOp = m_command.CreateCollectOp(n.Op.Type); 
            Node collectNode = m_command.CreateNode(collectOp, projectNode);

            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
            return collectNode; 
        }
 
        ///  
        /// Is this function a collection aggregate function. It is, if
        ///   - it has exactly one child 
        ///   - that child is a collection type
        ///   - and the function has been marked with the aggregate attribute
        /// 
        /// the function op 
        /// the current subtree
        /// true, if this was a collection aggregate function 
        private static bool IsCollectionAggregateFunction(FunctionOp op, Node n) 
        {
            return ((n.Children.Count == 1) && 
                    md.TypeSemantics.IsCollectionType(n.Child0.Op.Type) &&
                    md.TypeSemantics.IsAggregateFunction(op.Function));
        }
 
        /// 
        /// Converts a collection aggregate function count(X), where X is a collection into 
        /// two parts. Part A is a groupby subquery that looks like 
        ///    GroupBy(Unnest(X), empty, count(y))
        /// where "empty" describes the fact that the groupby has no keys, and y is an 
        /// element var of the Unnest
        ///
        /// Part 2 is a VarRef that refers to the aggregate var for count(y) described above.
        /// 
        /// Logically, we would replace the entire functionOp by element(GroupBy...). However,
        /// since we also want to translate element() into single-row-subqueries, we do this 
        /// here as well. 
        ///
        /// The function itself is replaced by the VarRef, and the GroupBy is added to the list 
        /// of scalar subqueries for the current relOp node on the stack
        ///
        /// 
        /// the functionOp for the collection agg 
        /// current subtree
        /// the VarRef node that should replace the function 
        private Node VisitCollectionAggregateFunction(FunctionOp op, Node n) 
        {
            md.TypeUsage softCastType = null; 
            Node argNode = n.Child0;
            if (OpType.SoftCast == argNode.Op.OpType)
            {
                softCastType = TypeHelpers.GetEdmType(argNode.Op.Type).TypeUsage; 
                argNode = argNode.Child0;
 
                while (OpType.SoftCast == argNode.Op.OpType) 
                {
                    argNode = argNode.Child0; 
                }
            }

            Node unnestNode = BuildUnnest(argNode); 
            UnnestOp unnestOp = unnestNode.Op as UnnestOp;
            Var unnestOutputVar = unnestOp.Table.Columns[0]; 
 
            AggregateOp aggregateOp = m_command.CreateAggregateOp(op.Function, false);
            VarRefOp unnestVarRefOp = m_command.CreateVarRefOp(unnestOutputVar); 
            Node unnestVarRefNode = m_command.CreateNode(unnestVarRefOp);
            if (softCastType != null)
            {
                unnestVarRefNode = m_command.CreateNode(m_command.CreateSoftCastOp(softCastType), unnestVarRefNode); 
            }
            Node aggExprNode = m_command.CreateNode(aggregateOp, unnestVarRefNode); 
 
            VarVec keyVars = m_command.CreateVarVec(); // empty keys
            Node keyVarDefListNode = m_command.CreateNode(m_command.CreateVarDefListOp()); 

            VarVec gbyOutputVars = m_command.CreateVarVec();
            Var aggVar;
            Node aggVarDefListNode = m_command.CreateVarDefListNode(aggExprNode, out aggVar); 
            gbyOutputVars.Set(aggVar);
            GroupByOp gbyOp = m_command.CreateGroupByOp(keyVars, gbyOutputVars); 
            Node gbySubqueryNode = m_command.CreateNode(gbyOp, unnestNode, keyVarDefListNode, aggVarDefListNode); 

            // "Move" this subquery to my parent relop 
            Node ret = AddSubqueryToParentRelOp(aggVar, gbySubqueryNode);

            return ret;
        } 

        ///  
        /// Pre-processing for a function. Does the default thing. In addition, if the 
        /// function is a TVF (ie) returns a collection, convert this expression into
        ///    Nest(select value p from unnest(f) as p) 
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(FunctionOp op, Node n)
        { 
            VisitScalarOpDefault(op, n); 
            Node newNode = null;
 
            // Is this a TVF?
            if (IsCollectionFunction(op))
            {
                newNode = VisitCollectionFunction(op, n); 
            }
            // Is this a collection-aggregate function? 
            else if (IsCollectionAggregateFunction(op, n)) 
            {
                newNode = VisitCollectionAggregateFunction(op, n); 
            }
            else
            {
                // sigh! 
                newNode = n;
            } 
 
            PlanCompiler.Assert(newNode != null, "failure to construct a functionOp?");
            return newNode; 
        }

        /// 
        /// Default processing. 
        /// In addition, if the case statement is of the shape
        ///     case when X then NULL else Y, or 
        ///     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,
        /// marks that type as needing a null sentinel. 
        /// This allows in NominalTypeElimination the case op to be pushed inside Y's null sentinel.
        /// 
        /// 
        ///  
        /// 
        public override Node Visit(CaseOp op, Node n) 
        { 
            VisitScalarOpDefault(op, n);
            //special handling to enable optimization 
            bool thenClauseIsNull;
            if (PlanCompilerUtil.IsRowTypeCaseOpWithNullability(op, n, out thenClauseIsNull))
            {
                //Add a null sentinel for the row type 
                m_typesNeedingNullSentinel.Add(op.Type.EdmType.Identity);
            } 
            return n; 
        }
 
        /// 
        /// If it is a IsNull op over a row type, mark the row type as needing a null sentinel.
        /// 
        ///  
        /// 
        ///  
        public override Node Visit(ConditionalOp op, Node n) 
        {
            VisitScalarOpDefault(op, n); 
            if (op.OpType == OpType.IsNull && md.TypeSemantics.IsRowType(n.Child0.Op.Type))
            {
                StructuredTypeNullabilityAnalyzer.MarkAsNeedingNullSentinel(m_typesNeedingNullSentinel, n.Child0.Op.Type);
            } 
            return n;
        } 
 
        #region PropertyOp Handling
 
        /// 
        /// Validates that the nav property agrees with the underlying relationship
        /// 
        /// the Nav PropertyOp 
        /// the subtree
        private void ValidateNavPropertyOp(PropertyOp op, Node n) 
        { 
            NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
 
            //
            // If the result of the expanded form of the navigation property is not compatible with
            // the declared type of the property, then the navigation property is invalid in the
            // context of this command tree's metadata workspace. 
            //
            md.TypeUsage resultType = navProperty.ToEndMember.TypeUsage; 
            if (TypeSemantics.IsReferenceType(resultType)) 
            {
                resultType = TypeHelpers.GetElementTypeUsage(resultType); 
            }
            if (navProperty.ToEndMember.RelationshipMultiplicity == RelationshipMultiplicity.Many)
            {
                resultType = TypeUsage.Create(resultType.EdmType.GetCollectionType()); 
            }
            if (!TypeSemantics.IsEquivalentOrPromotableTo(resultType, op.Type)) 
            { 
                throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_IncompatibleNavigationPropertyResult(
                        navProperty.DeclaringType.FullName, 
                        navProperty.Name
                    )
                );
            } 
        }
 
        ///  
        /// Rewrite a PropertyOp subtree for a nav property
        /// 
        /// We call RewriteNavigationPropertyOp to return a subtree (and an
        /// optional outputVar). If the outputVar is null, then we simply return the subtree produced by those calls.
        /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
        /// in its place. 
        ///
        /// As an example, 
        ///    select e.NP from T 
        /// gets rewritten into
        ///    select v from T OuterApply X 
        /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
        /// 
        /// the PropertyOp
        /// the current node 
        /// the rewritten subtree
        private Node VisitNavPropertyOp(PropertyOp op, Node n) 
        { 
            ValidateNavPropertyOp(op, n);
 
            //
            // This is a bit weird. Ideally, I would always visit the child first (ie) a bottom-up traversal,
            // but there's some weird gotchas in the elinq tests ("SelectManyNullResult531057")
            // 
            bool visitChildFirst = (n.Child0.Op.OpType != OpType.Property);
            if (visitChildFirst) 
            { 
                VisitScalarOpDefault(op, n);
            } 

            NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
            Node ret = RewriteNavigationProperty(navProperty, n.Child0, op.Type);
            ret = VisitNode(ret); 

            return ret; 
        } 

        ///  
        /// Rewrite a PropertyOp subtree.
        ///
        /// If the PropertyOp represents a simple property (ie) not a navigation property, we simply call
        /// VisitScalarOpDefault() and return. Otherwise, we call VisitNavPropertyOp and return the result from 
        /// that function
        /// 
        ///  
        /// the PropertyOp
        /// the PropertyOp subtree 
        /// the rewritten tree
        public override Node Visit(PropertyOp op, Node n)
        {
            Node ret; 
            if (Helper.IsNavigationProperty(op.PropertyInfo))
            { 
                ret = VisitNavPropertyOp(op, n); 
            }
            else 
            {
                ret = VisitScalarOpDefault(op, n);
            }
            return ret; 
        }
 
        #endregion 

        ///  
        /// Handler for a RefOp.
        /// Keeps track of the entityset
        /// 
        /// the RefOp 
        /// current RefOp subtree
        /// current subtree 
        public override Node Visit(RefOp op, Node n) 
        {
            VisitScalarOpDefault(op, n); // use default processing 
            AddEntitySetReference(op.EntitySet); // add to list of references
            return n;
        }
 
        /// 
        /// Handler for a TreatOp. 
        /// Rewrites the operator if the argument is guaranteed to be of type 
        /// op.
        ///  
        /// Current TreatOp
        /// Current subtree
        /// Current subtree
        public override Node Visit(TreatOp op, Node n) 
        {
            n = base.Visit(op, n); 
 
            // See if TreatOp can be rewritten (if it's not polymorphic)
            if (CanRewriteTypeTest(op.Type.EdmType, n.Child0.Op.Type.EdmType)) 
            {
                // Return argument directly (if the argument is null, 'treat as' also returns null;
                // if the argument is not null, it's guaranteed to be of the correct type)
                return n.Child0; 
            }
 
            return n; 
        }
 
        /// 
        /// Handler for an IsOfOp.
        /// Keeps track of the IsOfType (if it is a structured type) and rewrites the
        /// operator if the argument is guaranteed to be of type op.IsOfType 
        /// 
        /// Current IsOfOp 
        /// Current subtree 
        /// Current subtree
        public override Node Visit(IsOfOp op, Node n) 
        {
            n = VisitScalarOpDefault(op, n); // default handling first
            // keep track of any structured types
            AddTypeReference(op.IsOfType); 

            // See if the IsOfOp can be rewritten (if it's not polymorphic) 
            if (CanRewriteTypeTest(op.IsOfType.EdmType, n.Child0.Op.Type.EdmType)) 
            {
                n = RewriteIsOfAsIsNull(op, n); 
            }

            // For IsOfOnly(abstract type), suppress DiscriminatorMaps since no explicit type id is available for
            // abstract types. 
            if (op.IsOfOnly && op.IsOfType.EdmType.Abstract)
            { 
                m_suppressDiscriminatorMaps = true; 
            }
 
            return n;
        }

        // Determines whether a type test expression can be rewritten. Returns true of the 
        // argument type is guaranteed to implement "testType" (if the argument is non-null).
        private bool CanRewriteTypeTest(EdmType testType, EdmType argumentType) 
        { 
            // The rewrite only proceeds if the types are the same. If they are not,
            // it suggests either that the input result is polymorphic (in which case if OfType 
            // should be preserved) or the types are incompatible (which is caught
            // elsewhere)
            if (!testType.EdmEquals(argumentType))
            { 
                return false;
            } 
 
            // If the IsOfType is non-polymorphic (no base or derived types) the rewrite
            // is possible. 
            if (null != testType.BaseType)
            {
                return false;
            } 

            // Count sub types 
            int subTypeCount = 0; 
            foreach (EdmType subType in MetadataHelper.GetTypeAndSubtypesOf(testType, m_command.MetadataWorkspace, true /*includeAbstractTypes*/))
            { 
                subTypeCount++;
                if (2 == subTypeCount) { break; }
            }
 
            return 1 == subTypeCount; // no children types
        } 
 
        // Translates
        //      'R is of T' 
        // to
        //      '(case when not (R is null) then True else null end) = True'
        //
        // Input requirements: 
        //
        //      - IsOfOp and argument to same must be in the same hierarchy. 
        //      - IsOfOp and argument must have the same type 
        //      - IsOfOp.IsOfType may not have super- or sub- types (validate
        //        using CanRewriteTypeTest) 
        //
        // Design requirements:
        //
        //      - Must return true if the record exists 
        //      - Must return null if it does not
        //      - Must be in predicate form to avoid confusing SQL gen 
        // 
        // The translation assumes R is of T when R is non null.
        private Node RewriteIsOfAsIsNull(IsOfOp op, Node n) 
        {
            // construct 'R is null' predicate
            ConditionalOp isNullOp = m_command.CreateConditionalOp(OpType.IsNull);
            Node isNullNode = m_command.CreateNode(isNullOp, n.Child0); 

            // construct 'not (R is null)' predicate 
            ConditionalOp notOp = m_command.CreateConditionalOp(OpType.Not); 
            Node notNode = m_command.CreateNode(notOp, isNullNode);
 
            // construct 'True' result
            ConstantBaseOp trueOp = m_command.CreateConstantOp(op.Type, true);
            Node trueNode = m_command.CreateNode(trueOp);
 
            // construct 'null' default result
            NullOp nullOp = m_command.CreateNullOp(op.Type); 
            Node nullNode = m_command.CreateNode(nullOp); 

            // create case statement 
            CaseOp caseOp = m_command.CreateCaseOp(op.Type);
            Node caseNode = m_command.CreateNode(caseOp, notNode, trueNode, nullNode);

            // create 'case = true' operator 
            ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
            Node equalsNode = m_command.CreateNode(equalsOp, caseNode, trueNode); 
 
            return equalsNode;
        } 

        /// 
        /// Rewrite a NavigateOp subtree.
        /// We call RewriteNavigateOp to return a subtree (and an optional outputVar). 
        /// If the outputVar is null, then we simply return the subtree produced by those calls.
        /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar 
        /// in its place. 
        ///
        /// As an example, 
        ///    select navigate(e) from T
        /// gets rewritten into
        ///    select v from T OuterApply X
        /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X 
        ///
        ///  
        /// the navigateOp 
        /// the navigateOp subtree
        /// the rewritten tree 
        public override Node Visit(NavigateOp op, Node n)
        {
            VisitScalarOpDefault(op, n);
            Var outputVar; 
            Node ret = RewriteNavigateOp(n, op, out outputVar);
            ret = VisitNode(ret); 
 
            // Move subquery to parent relop if necessary
            if (outputVar != null) 
            {
                ret = AddSubqueryToParentRelOp(outputVar, ret);
            }
            return ret; 
        }
 
        ///  
        /// Find the "current" enclosing entityset
        ///  
        /// the enclosing entityset (if any)
        private EntitySetBase FindEnclosingEntitySetView()
        {
            if (m_viewNestingLevel == 0) 
            {
                return null; 
            } 

            // 
            // Walk up the stack of ancestors until we find the appropriate ScanViewOp
            //
            foreach (Node n in m_ancestors)
            { 
                if (n.Op.OpType == OpType.ScanView)
                { 
                    ScanViewOp op = (ScanViewOp)n.Op; 
                    return op.Table.TableMetadata.Extent;
                } 
            }

            PlanCompiler.Assert(false, "found no enclosing view - but view-nesting level is greater than zero");
            return null; 
        }
 
        ///  
        /// Find the relationshipset that matches the current entityset + from/to roles
        ///  
        /// 
        /// 
        /// 
        private RelationshipSet FindRelationshipSet(EntitySetBase entitySet, RelProperty relProperty) 
        {
            foreach (EntitySetBase es in entitySet.EntityContainer.BaseEntitySets) 
            { 
                AssociationSet rs = es as AssociationSet;
                if (rs != null && 
                    rs.ElementType.EdmEquals(relProperty.Relationship) &&
                    rs.AssociationSetEnds[relProperty.FromEnd.Identity].EntitySet.EdmEquals(entitySet))
                {
                    return rs; 
                }
            } 
            return null; 
        }
 
        /// 
        /// Find the position of a property in a type.
        /// Positions start at zero, and a supertype's properties precede the current
        /// type's properties 
        /// 
        /// the type in question 
        /// the member to lookup 
        /// the position of the member in the type (0-based)
        private int FindPosition(EdmType type, EdmMember member) 
        {
            int pos = 0;
            foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(type))
            { 
                if (m.EdmEquals(member))
                { 
                    return pos; 
                }
                pos++; 
            }
            PlanCompiler.Assert(false, "Could not find property " + member + " in type " + type.Name);
            return -1;
        } 

        ///  
        /// Build out an expression (NewRecord) that corresponds to the key properties 
        /// of the passed-in entity constructor
        /// 
        /// This function simply looks up the key properties of the entity type, and then
        /// identifies the arguments to the constructor corresponding to those
        /// properties, and then slaps on a record wrapper over those expressions.
        /// 
        /// No copies/clones are performed. That's the responsibility of the caller
        /// 
        ///  
        /// the entity constructor op
        /// the corresponding subtree 
        /// the key expression
        private Node BuildKeyExpressionForNewEntityOp(Op op, Node n)
        {
            PlanCompiler.Assert(op.OpType == OpType.NewEntity || op.OpType == OpType.DiscriminatedNewEntity, 
                "BuildKeyExpression: Unexpected OpType:" + op.OpType);
            int offset = (op.OpType == OpType.DiscriminatedNewEntity) ? 1 : 0; 
            EntityTypeBase entityType = (EntityTypeBase)op.Type.EdmType; 
            List keyFields = new List();
            List> keyFieldTypes = new List>(); 
            foreach (EdmMember k in entityType.KeyMembers)
            {
                int pos = FindPosition(entityType, k) + offset;
                PlanCompiler.Assert(n.Children.Count > pos, "invalid position " + pos + "; total count = " + n.Children.Count); 
                keyFields.Add(n.Children[pos]);
                keyFieldTypes.Add(new KeyValuePair(k.Name, k.TypeUsage)); 
            } 
            TypeUsage keyExprType = TypeHelpers.CreateRowTypeUsage(keyFieldTypes, true);
            NewRecordOp keyOp = m_command.CreateNewRecordOp(keyExprType); 
            Node keyNode = m_command.CreateNode(keyOp, keyFields);
            return keyNode;
        }
 
        /// 
        /// Build out an expression corresponding to the rel-property. 
        /// 
        /// We create a subquery that looks like
        ///    (select r 
        ///     from RS r
        ///     where GetRefKey(r.FromEnd) = myKey)
        ///
        /// RS is the single relationship set that corresponds to the given entityset/rel-property pair 
        /// FromEnd - is the source end of the relationship
        /// myKey - is the key expression of the entity being constructed 
        /// 
        /// NOTE: We always clone "myKey" before use.
        /// 
        /// We then convert it into a scalar subquery, and extract out the ToEnd property from
        /// the output var of the subquery. (Should we do this inside the subquery itself?)
        ///
        /// If no single relationship-set is found, we return a NULL instead. 
        /// 
        /// entity set that logically holds instances of the entity we're building 
        /// the rel-property we're trying to build up 
        /// the "key" of the entity instance
        /// the rel-property expression 
        private Node BuildRelPropertyExpression(EntitySetBase entitySet, RelProperty relProperty,
            Node keyExpr)
        {
            // 
            // Make a copy of the current key expression
            // 
            keyExpr = OpCopier.Copy(m_command, keyExpr); 

            // 
            // Find the relationship set corresponding to this entityset (and relProperty)
            // Return a null ref, if we can't find one
            //
            RelationshipSet relSet = FindRelationshipSet(entitySet, relProperty); 
            if (relSet == null)
            { 
                return m_command.CreateNode(m_command.CreateNullOp(relProperty.ToEnd.TypeUsage)); 
            }
 
            ScanTableOp scanTableOp = m_command.CreateScanTableOp(Command.CreateTableDefinition(relSet));
            PlanCompiler.Assert(scanTableOp.Table.Columns.Count == 1,
                "Unexpected column count for table:" + scanTableOp.Table.TableMetadata.Extent + "=" + scanTableOp.Table.Columns.Count);
            Var scanTableVar = scanTableOp.Table.Columns[0]; 
            Node scanNode = m_command.CreateNode(scanTableOp);
 
            Node sourceEndNode = m_command.CreateNode( 
                m_command.CreatePropertyOp(relProperty.FromEnd),
                m_command.CreateNode(m_command.CreateVarRefOp(scanTableVar))); 
            Node predicateNode = m_command.BuildComparison(OpType.EQ,
                keyExpr,
                m_command.CreateNode(m_command.CreateGetRefKeyOp(keyExpr.Op.Type), sourceEndNode));
            Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), 
                scanNode, predicateNode);
 
            // 
            // Process the node, and then add this as a subquery to the parent relop
            // 
            Node ret = VisitNode(filterNode);
            ret = AddSubqueryToParentRelOp(scanTableVar, ret);

            // 
            // Now extract out the target end property
            // 
            ret = m_command.CreateNode( 
                m_command.CreatePropertyOp(relProperty.ToEnd),
                ret); 

            return ret;
        }
 
        /// 
        /// Given an entity constructor (NewEntityOp, DiscriminatedNewEntityOp), build up 
        /// the list of rel-property expressions. 
        ///
        /// Walks through the list of relevant rel-properties, and builds up expressions 
        /// (using BuildRelPropertyExpression) for each rel-property that does not have
        /// an expression already built (preBuiltExpressions)
        /// 
        /// entity set that holds instances of the entity we're building 
        /// the list of relevant rel-properties for this entity type
        /// the prebuilt rel-property expressions 
        /// the key of the entity instance 
        /// a list of rel-property expressions (lines up 1-1 with 'relPropertyList')
        private IEnumerable BuildAllRelPropertyExpressions(EntitySetBase entitySet, 
            List relPropertyList,
            Dictionary prebuiltExpressions,
            Node keyExpr)
        { 
            foreach (RelProperty r in relPropertyList)
            { 
                Node relPropNode; 
                if (!prebuiltExpressions.TryGetValue(r, out relPropNode))
                { 
                    relPropNode = BuildRelPropertyExpression(entitySet, r, keyExpr);
                }
                yield return relPropNode;
            } 
        }
 
        ///  
        /// Handler for NewEntityOp.
        /// If this is an EntityConstructor, and the current view nesting level is 0 
        /// (ie) this is an EntityConstructor at the top-level query, then add
        /// the type to the list of "free-floating" entity constructor types
        /// 
        /// the NewEntityOp 
        /// the node tree corresponding to the op
        /// rewritten tree 
        public override Node Visit(NewEntityOp op, Node n) 
        {
            // 
            // The default processing first
            //
            VisitScalarOpDefault(op, n);
 
            md.EntityType entityType = op.Type.EdmType as md.EntityType;
            md.EntitySetBase entitySet = FindEnclosingEntitySetView(); 
 
            if (entitySet == null)
            { 
                if (entityType != null)
                {
                    m_freeFloatingEntityConstructorTypes.Add(entityType);
                } 

                // SQLBUDT #546546: Qmv/Umv tests Assert and throws in plan compiler in association tests. 
                // If this Entity constructor is not within a view then there should not be any RelProps 
                // specified on the NewEntityOp - the eSQL WITH RELATIONSHIPS clause that would cause such
                // RelProps to be added is only enabled when parsing in the user or generated view mode. 
                PlanCompiler.Assert(op.RelationshipProperties == null ||
                                    op.RelationshipProperties.Count == 0,
                                    "Related Entities cannot be specified for Entity constructors that are not part of the Query Mapping View for an Entity Set.");
 
                return n;
            } 
 
            //
            // Find the relationship properties for this entitytype (and entity set) 
            //
            List relProperties = new List(m_relPropertyHelper.GetRelProperties(entityType));

            // 
            // Ok, now, I have to build out some relationship properties that
            // haven't been specified 
            // 
            Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
 
            //
            // Find the list of rel properties that have already been specified
            //
            Dictionary prebuiltRelPropertyExprs = new Dictionary(); 
            int j = 0;
            for (int i = entityType.Properties.Count; i < n.Children.Count; i++, j++) 
            { 
                prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
            } 

            //
            // Fill in the missing pieces
            // 

            // 
            // Next, rebuild the list of children - includes expressions for each rel property 
            //
            List newChildren = new List(); 
            for (int i = 0; i < entityType.Properties.Count; i++)
            {
                newChildren.Add(n.Children[i]);
            } 

            foreach (Node relPropNode in BuildAllRelPropertyExpressions(entitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) 
            { 
                newChildren.Add(relPropNode);
            } 

            //
            // finally, build out the newOp
            // 
            Op newEntityOp = m_command.CreateNewEntityOp(op.Type, relProperties, entitySet);
            Node newNode = m_command.CreateNode(newEntityOp, newChildren); 
            return newNode; 
        }
 
        /// 
        /// Tracks discriminator metadata so that is can be used when constructing
        /// StructuredTypeInfo.
        ///  
        public override Node Visit(DiscriminatedNewEntityOp op, Node n)
        { 
            PlanCompiler.Assert(0 < m_viewNestingLevel, "DiscriminatedNewInstanceOp may appear only within view definition"); 

            HashSet relPropertyHashSet = new HashSet(); 
            List relProperties = new List();
            //
            // add references to each type produced by this node
            // Also, get the set of rel-properties for each of the types 
            //
            foreach (var discriminatorTypePair in op.DiscriminatorMap.TypeMap) 
            { 
                EntityTypeBase entityType = discriminatorTypePair.Value;
                AddTypeReference(TypeUsage.Create(entityType)); 
                foreach (RelProperty relProperty in m_relPropertyHelper.GetRelProperties(entityType))
                {
                    relPropertyHashSet.Add(relProperty);
                } 
            }
            relProperties = new List(relPropertyHashSet); 
            VisitScalarOpDefault(op, n); 

            // 
            // Now build out the set of missing rel-properties (if any)
            //

            // first, build the key expression 
            Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
 
            List newChildren = new List(); 
            int firstRelPropertyNodeOffset = n.Children.Count - op.RelationshipProperties.Count;
            for (int i = 0; i < firstRelPropertyNodeOffset; i++) 
            {
                newChildren.Add(n.Children[i]);
            }
            // 
            // Find the list of rel properties that have already been specified
            // 
            Dictionary prebuiltRelPropertyExprs = new Dictionary(); 
            for (int i = firstRelPropertyNodeOffset, j =0; i < n.Children.Count; i++, j++ )
            { 
               prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
            }

            // 
            // Fill in the missing pieces
            // 
            foreach (Node relPropNode in BuildAllRelPropertyExpressions(op.EntitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) 
            {
                newChildren.Add(relPropNode); 
            }

            Op newEntityOp = m_command.CreateDiscriminatedNewEntityOp(op.Type, op.DiscriminatorMap, op.EntitySet, relProperties);
            Node newNode = m_command.CreateNode(newEntityOp, newChildren); 

            return newNode; 
        } 

        ///  
        /// Handles a newMultiset constructor. Converts this into
        ///   select a from dual union all select b from dual union all ...
        /// Handles a NewMultiset constructor, i.e. {x, y, z}
        ///   1. Empty multiset constructors are simply converted into: 
        ///
        ///        select x from singlerowtable as x where false 
        /// 
        ///   2. Mulltset constructors with only one element or with multiple elements all of
        ///   which are constants or nulls are converted into: 
        ///
        ///     select x from dual union all select y from dual union all select z
        ///
        ///   3. All others are converted into: 
        ///
        ///      select case when d = 0 then x when d = 1 then y else z end 
        ///      from (  select 0 as d from single_row_table 
        ///              union all
        ///              select 1 as d from single_row_table 
        ///              union all
        ///              select 2 as d  from single_row_table )
        ///
        ///       NOTE: The  translation for 2 is valid for 3 too. We choose different translation 
        ///       in order to avoid correlation inside the union all,
        ///       which would prevent us from removing apply operators 
        /// 
        /// Do this before processing the children, and then
        /// call Visit on the result to handle the elements 
        /// 
        /// the new instance op
        /// the current subtree
        /// the modified subtree 
        public override Node Visit(NewMultisetOp op, Node n)
        { 
            Node resultNode = null; 
            Var resultVar = null;
 
            md.CollectionType collectionType = TypeHelpers.GetEdmType(op.Type);

            //
            // Empty multiset constructors are simply converted into 
            //    Project(Filter(SingleRowTableOp(), false)
            // 
            if (!n.HasChild0) 
            {
                Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); 
                Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
                    singleRowTableNode,
                    m_command.CreateNode(m_command.CreateFalseOp()));
                Node fakeChild = m_command.CreateNode(m_command.CreateNullOp(collectionType.TypeUsage)); 
                Var newVar;
                Node projectNode = m_command.BuildProject(filterNode, fakeChild, out newVar); 
 
                resultNode = projectNode;
                resultVar = newVar; 
            }

            //
            // Multiset constructors with only one elment or with multiple elments all of 
            //   which are constants or nulls are converted into:
            // 
            // UnionAll(Project(SingleRowTable, e1), Project(SingleRowTable, e2), ...) 
            //
            // The degenerate case when the collection has only one element does not require an 
            // outer unionAll node
            //
            else if (n.Children.Count == 1 || AreAllConstantsOrNulls(n.Children))
            { 
                List inputNodes = new List();
                List inputVars = new List(); 
                foreach (Node chi in n.Children) 
                {
                    Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); 
                    Var newVar;
                    Node projectNode = m_command.BuildProject(singleRowTableNode, chi, out newVar);
                    inputNodes.Add(projectNode);
                    inputVars.Add(newVar); 
                }
                // Build the union-all ladder 
                m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar); 

            } 
            //
            //   All other cases:
            //
            //  select case when d = 0 then x when d = 1 then y else z end 
            //  from (  select 0 as d from single_row_table
            //          union all 
            //          select 1 as d from single_row_table 
            //          union all
            //          select 2 as d  from single_row_table ) 
            //
            else
            {
                List inputNodes = new List(); 
                List inputVars = new List();
                //Create the union all lather first 
                for (int i = 0; i < n.Children.Count; i++) 
                {
                    Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); 
                    // the discriminator for this branch
                    Node discriminatorNode = m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.IntegerType, i));
                    Var newVar;
                    Node projectNode = m_command.BuildProject(singleRowTableNode, discriminatorNode, out newVar); 

                    inputNodes.Add(projectNode); 
                    inputVars.Add(newVar); 
                }
                // Build the union-all ladder now 
                m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);

                //Now create the case statement for the projection
                List caseArgNodes = new List(n.Children.Count * 2 + 1); 
                for (int i = 0; i < n.Children.Count; i++)
                { 
                    //For all but the last we need a when 
                    if (i != (n.Children.Count - 1))
                    { 
                        ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
                        Node whenNode = m_command.CreateNode(equalsOp,
                            m_command.CreateNode(m_command.CreateVarRefOp(resultVar)),
                            m_command.CreateNode( 
                                m_command.CreateConstantOp(m_command.IntegerType, i)));
                        caseArgNodes.Add(whenNode); 
                    } 

                    //Add the then/else node 
                    caseArgNodes.Add(n.Children[i]);
                }

                //Create the project 
                Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(collectionType.TypeUsage), caseArgNodes);
                resultNode = m_command.BuildProject(resultNode, caseNode, out resultVar); 
            } 

            // So, I've finally built up a complex query corresponding to the constructor. 
            // Now, cap this with a physicalprojectOp, and then with a CollectOp
            PhysicalProjectOp physicalProjectOp = m_command.CreatePhysicalProjectOp(resultVar);
            Node physicalProjectNode = m_command.CreateNode(physicalProjectOp, resultNode);
 
            CollectOp collectOp = m_command.CreateCollectOp(op.Type);
            Node collectNode = m_command.CreateNode(collectOp, physicalProjectNode); 
 
            return VisitNode(collectNode);
        } 

        /// 
        /// Returns true if each node in the list is either a constant or a null
        ///  
        /// 
        ///  
        private bool AreAllConstantsOrNulls(List nodes) 
        {
            foreach (Node node in nodes) 
            {
                if (node.Op.OpType != OpType.Constant && node.Op.OpType != OpType.Null)
                {
                    return false; 
                }
            } 
            return true; 
        }
 
        /// 
        /// Default processing for a CollectOp. But make sure that we
        /// go through the NestPullUp phase
        ///  
        /// 
        ///  
        ///  
        public override Node Visit(CollectOp op, Node n)
        { 
            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
            return VisitScalarOpDefault(op, n);
        }
 
        #endregion
 
        #region RelOps 

        ///  
        /// Augments a node with a number of OuterApply's - one for each subquery
        /// If S1, S2, ... are the list of subqueries for the node, and D is the
        /// original (driver) input, we convert D into
        ///    OuterApply(OuterApply(D, S1), S2), ... 
        /// 
        /// the input (driver) node 
        /// List of subqueries 
        /// should the input node be first in the apply chain, or the last?
        /// The resulting node tree 
        private Node AugmentWithSubqueries(Node input, List subqueries, bool inputFirst)
        {
            Node newNode;
            int subqueriesStartPos; 

            if (inputFirst) 
            { 
                newNode = input;
                subqueriesStartPos = 0; 
            }
            else
            {
                newNode = subqueries[0]; 
                subqueriesStartPos = 1;
            } 
            for (int i =subqueriesStartPos; i < subqueries.Count; i++) 
            {
                    OuterApplyOp op = m_command.CreateOuterApplyOp(); 
                    newNode = m_command.CreateNode(op, newNode, subqueries[i]);
            }
            if (!inputFirst)
            { 
                newNode = m_command.CreateNode(m_command.CreateOuterApplyOp(), newNode, input);
            } 
 
            // We may need to perform join elimination
            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); 
            return newNode;
        }

        ///  
        /// Default processing for RelOps.
        /// - First, we mark the current node as its own ancestor (so that any 
        ///   subqueries that we detect internally will be added to this node's list) 
        /// - then, visit each child
        /// - finally, accumulate all nested subqueries. 
        /// - if the current RelOp has only one input, then add the nested subqueries via
        ///   Outer apply nodes to this input.
        ///
        /// The interesting RelOps are 
        ///   Project, Filter, GroupBy, Sort,
        /// Should we break this out into separate functions instead? 
        ///  
        /// Current RelOp
        /// Node to process 
        /// Current subtree
        protected override Node VisitRelOpDefault(RelOp op, Node n)
        {
            VisitChildren(n); // visit all my children first 

            // Then identify all the subqueries that have shown up as part of my node 
            // Create Apply Nodes for each of these. 
            List nestedSubqueries;
            if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries) && nestedSubqueries.Count > 0) 
            {
                // Validate - this must only apply to the following nodes
                PlanCompiler.Assert(
                    n.Op.OpType == OpType.Project || n.Op.OpType == OpType.Filter || 
                    n.Op.OpType == OpType.GroupBy,
                    "VisitRelOpDefault: Unexpected op?" + n.Op.OpType); 
 
                Node newInputNode = AugmentWithSubqueries(n.Child0, nestedSubqueries, true);
                // Now make this the new input child 
                n.Child0 = newInputNode;
            }

            return n; 
        }
 
        private void HandleTableOpMetadata(ScanTableBaseOp op) 
        {
            // add to the list of referenced entitysets 
            md.EntitySet entitySet = op.Table.TableMetadata.Extent as md.EntitySet;
            if (entitySet != null)
            {
                AddEntitySetReference(entitySet); 
            }
 
            md.TypeUsage elementType = TypeUsage.Create(op.Table.TableMetadata.Extent.ElementType); 
            // add to the list of structured types
            AddTypeReference(elementType); 
        }

        /// 
        /// Visits a "table" expression - performs view expansion on the table (if appropriate), 
        /// and then some additional book-keeping.
        /// 
        /// The "ofType" and "includeSubtypes" parameters are optional hints for view expansion, allowing 
        /// for more customized (and hopefully, more optimal) views. The wasOfTypeSatisfied out parameter
        /// tells whether the ofType filter was already handled by the view expansion, or if the caller still 
        /// needs to deal with it.
        ///
        /// If the "table" is a C-space entityset, then we produce a ScanViewOp
        /// tree with the defining query as the only child of the ScanViewOp 
        ///
        /// If the table is an S-space entityset, then we still produce a ScanViewOp, but this 
        /// time, we produce a simple "select * from BaseTable" as the defining 
        /// query
        ///  
        /// the scanTable node tree
        /// the scanTableOp
        /// 
        ///     An optional IsOfOp representing a type filter to apply to the scan table; will be set to null 
        ///     if the scan target is expanded to a view that renders the type filter superfluous.
        ///  
        ///  
        private Node ProcessScanTable(Node scanTableNode, ScanTableOp scanTableOp, ref IsOfOp typeFilter)
        { 
            HandleTableOpMetadata(scanTableOp);

            PlanCompiler.Assert(scanTableOp.Table.TableMetadata.Extent != null, "ScanTableOp must reference a table with an extent");
 
            Node ret = null;
 
            // 
            // Get simple things out of the way. If we're dealing with an S-space entityset, and
            // it isn't at the top-level of the query, simply return the node 
            //
            if (scanTableOp.Table.TableMetadata.Extent.EntityContainer.DataSpace == DataSpace.SSpace)
            {
                if (m_viewNestingLevel > 0) 
                {
                    return scanTableNode; 
                } 

                // If the S-level entityset is at the  "top-level" of the query, 
                // i.e. it is not referenced inside a view, we perform a "select *"
                // translation over the set. This also caps the entityset with a
                // ScanViewOp so it is logically withing a view definition when the
                // PreProcessor is run again over the resulting Node. 
                Node definingQuery = GetDefiningQueryForSSpaceSet(scanTableNode, scanTableOp);
                ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table); 
                ret = m_command.CreateNode(scanViewOp, definingQuery); 
            }
            else 
            {
                // "Expand" the C-Space view
                ret = ExpandView(scanTableNode, scanTableOp, ref typeFilter);
            } 

            m_viewNestingLevel++; 
            // Rerun the processor over the resulting subtree 
            ret = VisitNode(ret);
            m_viewNestingLevel--; 

            return ret;
        }
 
        /// 
        /// Processes a ScanTableOp - simply delegates to ProcessScanTableOp 
        ///  
        /// the view op
        /// current node tree 
        /// the transformed view-op
        public override Node Visit(ScanTableOp op, Node n)
        {
            IsOfOp nullFilter = null; 
            return ProcessScanTable(n, op, ref nullFilter);
        } 
 
        /// 
        /// Visitor for a ScanViewOp 
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(ScanViewOp op, Node n)
        { 
            HandleTableOpMetadata(op); 
            // Ideally, I should call this as the first statement, but that was causing too
            // many test diffs - because of the order in which the entitytypes/sets 
            // were being added. There is no semantic difference in calling this here
            VisitRelOpDefault(op, n);
            return n;
        } 

        ///  
        /// Processing for all JoinOps 
        /// 
        /// JoinOp 
        /// Current subtree
        /// 
        protected override Node VisitJoinOp(JoinBaseOp op, Node n)
        { 
            VisitChildren(n); // visit all my children first
 
            // 
            // Need a join elimination phase?
            // 
            if (op.OpType == OpType.InnerJoin || op.OpType == OpType.LeftOuterJoin)
            {
                m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination);
            } 

            // then check to see if we have any nested subqueries. This can only 
            // occur in the join condition. 
            // What we'll do in this case is to convert the join condition - "p" into
            //    p -> Exists(Filter(SingleRowTableOp, p)) 
            // We will then move the subqueries into an outerApply on the SingleRowTable
            List nestedSubqueries;
            if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries))
            { 
                PlanCompiler.Assert(n.Op.OpType == OpType.InnerJoin ||
                    n.Op.OpType == OpType.LeftOuterJoin || 
                    n.Op.OpType == OpType.FullOuterJoin, "unexpected op?"); 
                PlanCompiler.Assert(n.HasChild2, "missing second child to JoinOp?");
                Node joinCondition = n.Child2; 

                Node inputNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
                inputNode = AugmentWithSubqueries(inputNode, nestedSubqueries, true);
                Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), inputNode, joinCondition); 

                // update the join condition 
                // #479372: Build up a dummy project node over the input, as we always wrap the child of exists 
                Node projectNode = BuildDummyProjectForExists(filterNode);
                Node existsNode = m_command.CreateNode(m_command.CreateExistsOp(), projectNode); 

                n.Child2 = existsNode;
            }
 
            return n;
        } 
 
        /// 
        /// Perform default relop processing; Also "require" the join-elimination phase 
        /// 
        /// 
        /// 
        ///  
        protected override Node VisitApplyOp(ApplyBaseOp op, Node n)
        { 
            m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); 
            return VisitRelOpDefault(op, n);
        } 

        /// 
        /// Visitor for UnnestOp. If the child has any subqueries, we need to convert this
        /// into an 
        ///    OuterApply(S, Unnest)
        /// unlike the other cases where the OuterApply will appear as the input of the node 
        ///  
        /// the unnestOp
        /// current subtree 
        /// modified subtree
        public override Node Visit(UnnestOp op, Node n)
        {
            VisitChildren(n); // visit all my children first 

            List nestedSubqueries; 
            if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries)) 
            {
                Node newNode = AugmentWithSubqueries(n, nestedSubqueries, false); 
                return newNode;
            }
            else
            { 
                return n;
            } 
 
        }
        ///  
        /// Can I eliminate this sort? I can, if the current path is *not* one of the
        /// following
        ///   TopN(Sort)
        ///   PhysicalProject(Sort) 
        ///
        /// We don't yet handle the TopN variant 
        ///  
        /// 
        private bool IsSortUnnecessary() 
        {
            Node ancestor = m_ancestors.Peek();
            PlanCompiler.Assert(ancestor != null, "unexpected SortOp as root node?");
 
            if (ancestor.Op.OpType == OpType.PhysicalProject)
            { 
                return false; 
            }
 
            return true;
        }

        ///  
        /// Visit a SortOp. Eliminate it if the path to this node is not one of
        /// PhysicalProject(Sort) or 
        /// TopN(Sort) 
        ///
        /// Otherwise, simply visit the child RelOp 
        ///
        /// 
        /// Current sortOp
        /// current subtree 
        /// possibly transformed subtree
        public override Node Visit(SortOp op, Node n) 
        { 
            // can I eliminate this sort
            if (this.IsSortUnnecessary()) 
            {
                return VisitNode(n.Child0);
            }
 
            // perform default processing
            return VisitRelOpDefault(op, n); 
        } 

        ///  
        /// Checks to see if this filterOp represents an IS OF (or IS OF ONLY) filter over a ScanTableOp
        /// 
        /// the filterOp node
        /// (OUT) the Type to restrict to 
        /// (OUT) was an ONLY clause specified
        ///  
        private bool IsOfTypeOverScanTable(Node n, out IsOfOp typeFilter) 
        {
            typeFilter = null; 

            //
            // Is the predicate an IsOf predicate
            // 
            IsOfOp isOfOp = n.Child1.Op as IsOfOp;
            if (isOfOp == null) 
            { 
                return false;
            } 
            //
            // Is the Input RelOp a ScanTableOp
            //
            ScanTableOp scanTableOp = n.Child0.Op as ScanTableOp; 
            if (scanTableOp == null || scanTableOp.Table.Columns.Count != 1)
            { 
                return false; 
            }
            // 
            // Is the argument to the IsOfOp the single column of the table?
            //
            VarRefOp varRefOp = n.Child1.Child0.Op as VarRefOp;
            if (varRefOp == null || varRefOp.Var != scanTableOp.Table.Columns[0]) 
            {
                return false; 
            } 

            // 
            // All conditions match. Return the info from the IsOf predicate
            //
            typeFilter = isOfOp;
            return true; 
        }
 
        ///  
        /// Handler for a FilterOp. Usually delegates to VisitRelOpDefault.
        /// 
        /// There's one special case - where we have an ISOF predicate over a ScanTable. In that case, we attempt
        /// to get a more "optimal" view; and return that optimal view
        ///
        ///  
        /// the filterOp
        /// the node tree 
        ///  
        public override Node Visit(FilterOp op, Node n)
        { 
            IsOfOp typeFilter;
            if (IsOfTypeOverScanTable(n, out typeFilter))
            {
                Node ret = ProcessScanTable(n.Child0, (ScanTableOp)n.Child0.Op, ref typeFilter); 
                if (typeFilter != null)
                { 
                    n.Child1 = VisitNode(n.Child1); 
                    n.Child0 = ret;
                    ret = n; 
                }
                return ret;
            }
            else 
            {
                return VisitRelOpDefault(op, n); 
            } 
        }
 
        /// 
        /// Visit a ProjectOp; if the input is a SortOp, we pullup the sort over
        /// the ProjectOp to ensure that we don't have nested sorts;
        ///  
        /// 
        ///  
        ///  
        public override Node Visit(ProjectOp op, Node n)
        { 
            PlanCompiler.Assert(n.HasChild0, "projectOp without input?");

            if (OpType.Sort == n.Child0.Op.OpType || OpType.ConstrainedSort == n.Child0.Op.OpType)
            { 
                SortBaseOp sort = (SortBaseOp)n.Child0.Op;
 
                IList sortChildren = new List(); 
                sortChildren.Add(n);
 
                //A ConstrainedSort has two other children besides the input and it needs to keep them.
                for (int i = 1; i < n.Child0.Children.Count; i++)
                {
                    sortChildren.Add(n.Child0.Children[i]); 
                }
 
                // Replace the ProjectOp input (currently the Sort node) with the input to the Sort. 
                n.Child0 = n.Child0.Child0;
 
                // Vars produced by the Sort input and used as SortKeys should be considered outputs
                // of the ProjectOp that now operates over what was the Sort input.
                foreach (SortKey key in sort.Keys)
                { 
                    op.Outputs.Set(key.Var);
                } 
 
                // Finally, pull the Sort over the Project by creating a new Sort node with the original
                // Sort as its Op and the Project node as its only child. This is sufficient because 
                // the ITreeGenerator ensures that the SortOp does not have any local VarDefs.
                return VisitNode(m_command.CreateNode(sort, sortChildren));
            }
 
            // perform default processing
            Node newNode = VisitRelOpDefault(op, n); 
            return newNode; 
        }
 
        #endregion

        #endregion
 
        #endregion
    } 
 
    /// 
    /// Finds the record (Row) types that we're projecting out of the query, and 
    /// ensures that we mark them as needing a nullable sentinel, so when we
    /// flatten them later we'll have one added.
    /// 
    internal class StructuredTypeNullabilityAnalyzer : ColumnMapVisitor> 
    {
        static internal StructuredTypeNullabilityAnalyzer Instance = new StructuredTypeNullabilityAnalyzer(); 
 
        /// 
        /// VarRefColumnMap 
        /// 
        /// 
        /// 
        ///  
        internal override void Visit(VarRefColumnMap columnMap, HashSet typesNeedingNullSentinel)
        { 
            AddTypeNeedingNullSentinel(typesNeedingNullSentinel, columnMap.Type); 
            base.Visit(columnMap, typesNeedingNullSentinel);
        } 

        /// 
        /// Recursively add any Row types to the list of types needing a sentinel.
        ///  
        /// 
        ///  
        private static void AddTypeNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage) 
        {
            if (md.TypeSemantics.IsCollectionType(typeUsage)) 
            {
                AddTypeNeedingNullSentinel(typesNeedingNullSentinel, TypeHelpers.GetElementTypeUsage(typeUsage));
            }
            else 
            {
                if (md.TypeSemantics.IsRowType(typeUsage) || md.TypeSemantics.IsComplexType(typeUsage)) 
                { 
                    MarkAsNeedingNullSentinel(typesNeedingNullSentinel, typeUsage);
                } 
                foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(typeUsage))
                {
                    AddTypeNeedingNullSentinel(typesNeedingNullSentinel, m.TypeUsage);
                } 
            }
        } 
 
        /// 
        /// Marks the given typeUsage as needing a null sentinel. 
        /// Call this method instead of calling Add over the HashSet directly, to ensure consistency.
        /// 
        /// 
        ///  
        internal static void MarkAsNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage)
        { 
            typesNeedingNullSentinel.Add(typeUsage.EdmType.Identity); 
        }
    } 

}

// 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