/// <summary>
 /// Create a new VarInfo for a structured type Var
 /// </summary>
 /// <param name="v">The structured type Var</param>
 /// <param name="newType">"Mapped" type for v</param>
 /// <param name="newVars">List of vars corresponding to v</param>
 /// <param name="newProperties">Flattened Properties </param>
 /// <param name="newVarsIncludeNullSentinelVar">Do the new vars include a var that represents a null sentinel either for this type or for any nested type</param>
 /// <returns>the VarInfo</returns>
 internal VarInfo CreateStructuredVarInfo(
     Var v, RowType newType, List<Var> newVars, List<EdmProperty> newProperties, bool newVarsIncludeNullSentinelVar)
 {
     VarInfo varInfo = new StructuredVarInfo(newType, newVars, newProperties, newVarsIncludeNullSentinelVar);
     m_map.Add(v, varInfo);
     return varInfo;
 }

        private readonly List<Var> m_newVars; // always a singleton list

        /// <summary>
        /// Initializes a new instance of <see cref="PrimitiveTypeVarInfo"/> class.
        /// </summary>
        /// <param name="newVar">
        /// New <see cref="Var"/> that replaces current <see cref="Var"/>.
        /// </param>
        internal PrimitiveTypeVarInfo(Var newVar)
        {
            Debug.Assert(newVar != null, "newVar != null");
            m_newVars = new List<Var>
                {
                    newVar
                };
        }

        /// <summary>
        /// Add a subquery to the "parent" relop node
        /// </summary>
        /// <param name="outputVar">the output var to be used - at the current location - in lieu of the subquery</param>
        /// <param name="subquery">the subquery to move</param>
        /// <returns>a var ref node for the var returned from the subquery</returns>
        protected 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;
        }

 /// <summary>
 /// Determines whether the given node is a VarRef over the given var
 /// </summary>
 /// <param name="node"></param>
 /// <param name="var"></param>
 /// <returns></returns>
 internal static bool IsVarRefOverGivenVar(Node node, Var var)
 {
     if (node.Op.OpType
         != OpType.VarRef)
     {
         return false;
     }
     return ((VarRefOp)node.Op).Var == var;
 }

 internal CollectionInfo(
     Var collectionVar, ColumnMap columnMap, VarList flattenedElementVars, VarVec keys, List<SortKey> sortKeys,
     object discriminatorValue)
 {
     m_collectionVar = collectionVar;
     m_columnMap = columnMap;
     m_flattenedElementVars = flattenedElementVars;
     m_keys = keys;
     m_sortKeys = sortKeys;
     m_discriminatorValue = discriminatorValue;
 }

        internal VarInfo CreatePrimitiveTypeVarInfo(Var v, Var newVar)
        {
            Debug.Assert(v != null, "v != null");
            Debug.Assert(newVar != null, "newVar != null");

            PlanCompiler.Assert(TypeSemantics.IsScalarType(v.Type), "The current variable should be of primitive or enum type.");
            PlanCompiler.Assert(TypeSemantics.IsScalarType(newVar.Type), "The new variable should be of primitive or enum type.");

            VarInfo varInfo = new PrimitiveTypeVarInfo(newVar);
            m_map.Add(v, varInfo);
            return varInfo;
        }

        /// <summary>
        /// Add an entry that the given property of the given var is a computation represented 
        /// by the computationTemplate over the var represented by the given groupAggregateVarInfo        
        /// </summary>
        /// <param name="var"></param>
        /// <param name="groupAggregateVarInfo"></param>
        /// <param name="computationTemplate"></param>
        /// <param name="isUnnested"></param>
        /// <param name="property"></param>
        internal void Add(
            Var var, GroupAggregateVarInfo groupAggregateVarInfo, Node computationTemplate, bool isUnnested, EdmMember property)
        {
            if (property == null)
            {
                Add(var, groupAggregateVarInfo, computationTemplate, isUnnested);
                return;
            }
            if (_groupAggregateVarRelatedVarPropertyToInfo == null)
            {
                _groupAggregateVarRelatedVarPropertyToInfo = new Dictionary<Var, Dictionary<EdmMember, GroupAggregateVarRefInfo>>();
            }
            Dictionary<EdmMember, GroupAggregateVarRefInfo> varPropertyDictionary;
            if (!_groupAggregateVarRelatedVarPropertyToInfo.TryGetValue(var, out varPropertyDictionary))
            {
                varPropertyDictionary = new Dictionary<EdmMember, GroupAggregateVarRefInfo>();
                _groupAggregateVarRelatedVarPropertyToInfo.Add(var, varPropertyDictionary);
            }
            varPropertyDictionary.Add(property, new GroupAggregateVarRefInfo(groupAggregateVarInfo, computationTemplate, isUnnested));

            // Note: The following line is not necessary with the current usage pattern, this method is 
            // never called with a new groupAggregateVarInfo thus it is a no-op.
            _groupAggregateVarInfos.Add(groupAggregateVarInfo);
        }

        /// <summary>
        /// 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.  
        /// </summary>
        /// <param name="relSet">the relationshipset</param>
        /// <param name="end">the toEnd of the relationship</param>
        /// <param name="rsVar">the var representing the relationship instance ("r") in the output subquery</param>
        /// <param name="esVar">the var representing the entity instance ("e") in the output subquery</param>
        /// <returns>the join subquery described above</returns>
        private Node BuildJoinForNavProperty(
            RelationshipSet relSet, RelationshipEndMember end,
            out Var rsVar, out Var esVar)
        {
            var entitySet = FindTargetEntitySet(relSet, end);

            //
            // Build out the ScanTable ops for the relationshipset and the entityset. Add the 
            //
            var asTableNode = BuildOfTypeTable(relSet, null, out rsVar);
            var esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar);

            // 
            // Build up a join between the entityset and the associationset; join on the to-end
            //
            var 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)))
                );

            var joinNode = m_command.CreateNode(
                m_command.CreateInnerJoinOp(),
                asTableNode, esTableNode, joinPredicate);

            return joinNode;
        }

        private Node RewriteFromOneNavigationProperty(
            RelProperty relProperty, List<RelationshipSet> relationshipSets, Node sourceRefNode, out Var outputVar)
        {
            PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationship set here");
            PlanCompiler.Assert(
                relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many,
                "Expected source end multiplicity to be one. Found 'Many' instead " + relProperty);

            var entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage);
            var scanTableNodes = new List<Node>(relationshipSets.Count);
            var scanTableVars = new List<Var>(relationshipSets.Count);
            foreach (var r in relationshipSets)
            {
                var entitySet = FindTargetEntitySet(r, relProperty.ToEnd);
                Var tableVar;
                var tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);

                scanTableNodes.Add(tableNode);
                scanTableVars.Add(tableVar);
            }

            // 
            // Build the union-all node
            //
            Node unionAllNode;

            m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out outputVar);

            //
            // Now build up the appropriate filter. Select out the relproperty from the other end
            //
            var inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd);
            PlanCompiler.Assert(
                m_command.IsRelPropertyReferenced(inverseRelProperty),
                "Unreferenced rel property? " + inverseRelProperty);
            var inverseRelPropertyNode = m_command.CreateNode(
                m_command.CreateRelPropertyOp(inverseRelProperty),
                m_command.CreateNode(m_command.CreateVarRefOp(outputVar)));
            var predicateNode = m_command.BuildComparison(
                OpType.EQ,
                sourceRefNode, inverseRelPropertyNode);
            var ret = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicateNode);

            return ret;
        }

 /// <summary>
 /// Another overload - with an additional discriminatorValue.
 /// Should this be a subtype instead?
 /// </summary>
 /// <param name="collectionVar">the collectionVar</param>
 /// <param name="columnMap">column map for the collection element</param>
 /// <param name="flattenedElementVars">elementVars with any nested collections pulled up</param>
 /// <param name="keys">keys specific to this collection</param>
 /// <param name="sortKeys">sort keys specific to this collecion</param>
 /// <param name="discriminatorValue">discriminator value for this collection (under the current nestOp)</param>
 /// <returns>a new CollectionInfo instance</returns>
 internal static CollectionInfo CreateCollectionInfo(Var collectionVar, ColumnMap columnMap, VarList flattenedElementVars, VarVec keys, List<InternalTrees.SortKey> sortKeys, object discriminatorValue)
 {
     return new CollectionInfo(collectionVar, columnMap, flattenedElementVars, keys, sortKeys, discriminatorValue);
 }

        /// <summary>
        /// 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. 
        /// </summary>
        /// <param name="derefOpNode">the derefOp subtree</param>
        /// <param name="derefOp">the derefOp</param>
        /// <param name="outputVar">output var produced</param>
        /// <returns>the subquery described above</returns>
        private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar)
        {
            var entityType = derefOp.Type;
            var 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));
            }

            var scanTableNodes = new List<Node>();
            var scanTableVars = new List<Var>();
            foreach (var entitySet in targetEntitySets)
            {
                Var tableVar;
                var 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
            //
            var entityRefNode = m_command.CreateNode(
                m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type),
                m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
            var keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode);
            var filterNode = m_command.CreateNode(
                m_command.CreateFilterOp(),
                unionAllNode,
                keyComparisonPred);

            outputVar = unionAllVar;
            return filterNode;
        }

        /// <summary>
        /// Convert a SingleStreamNestOp into a massive UnionAllOp
        /// </summary>
        /// <param name="nestOp"></param>
        /// <param name="nestNode"></param>
        /// <param name="drivingNodeVars"></param>
        /// <param name="discriminatorVarList"></param>
        /// <param name="discriminatorVar"></param>
        /// <param name="varMapList"></param>
        /// <returns></returns>
        private Node BuildUnionAllSubqueryForNestOp(
            NestBaseOp nestOp, Node nestNode, VarList drivingNodeVars, VarList discriminatorVarList, out Var discriminatorVar,
            out List<Dictionary<Var, Var>> varMapList)
        {
            var drivingNode = nestNode.Child0;

            // For each of the NESTED collections...
            Node unionAllNode = null;
            VarList unionAllOutputs = null;
            for (var i = 1; i < nestNode.Children.Count; i++)
            {
                // Ensure we only use the driving collection tree once, so other
                // transformations do not unintentionally change more than one path.
                // To prevent nodes in the tree from being used in multiple paths,
                // we copy the driving input on successive nodes.
                VarList newDrivingNodeVars;
                Node newDrivingNode;
                VarList newFlattenedElementVars;
                Op op;

                if (i > 1)
                {
                    newDrivingNode = OpCopier.Copy(Command, drivingNode, drivingNodeVars, out newDrivingNodeVars);
                    // 
                    // Bug 450245: If we copied the driver node, then references to driver node vars
                    // from the collection subquery must be patched up
                    //
                    var varRemapper = new VarRemapper(Command);
                    for (var j = 0; j < drivingNodeVars.Count; j++)
                    {
                        varRemapper.AddMapping(drivingNodeVars[j], newDrivingNodeVars[j]);
                    }
                    // Remap all references in the current subquery
                    varRemapper.RemapSubtree(nestNode.Children[i]);

                    // Bug 479183: Remap the flattened element vars
                    newFlattenedElementVars = varRemapper.RemapVarList(nestOp.CollectionInfo[i - 1].FlattenedElementVars);

                    // Create a cross apply for all but the first collection
                    op = Command.CreateCrossApplyOp();
                }
                else
                {
                    newDrivingNode = drivingNode;
                    newDrivingNodeVars = drivingNodeVars;
                    newFlattenedElementVars = nestOp.CollectionInfo[i - 1].FlattenedElementVars;

                    // Create an outer apply for the first collection, 
                    // that way we ensure at least one row for each row in the driver node.
                    op = Command.CreateOuterApplyOp();
                }

                // Create an outer apply with the driver node and the nested collection.
                var applyNode = Command.CreateNode(op, newDrivingNode, nestNode.Children[i]);

                // Now create a ProjectOp that augments the output from the OuterApplyOp
                // with nulls for each column from other collections

                // Build the VarDefList (the list of vars) for the Project, starting
                // with the collection discriminator var
                var varDefListChildren = new List<Node>();
                var projectOutputs = Command.CreateVarList();

                // Add the collection discriminator var to the output.
                projectOutputs.Add(discriminatorVarList[i]);

                // Add all columns from the driving node
                projectOutputs.AddRange(newDrivingNodeVars);

                // Add all the vars from all the nested collections;
                for (var j = 1; j < nestNode.Children.Count; j++)
                {
                    var otherCollectionInfo = nestOp.CollectionInfo[j - 1];
                    // For the current nested collection, we just pick the var that's
                    // coming from there and don't need have a new var defined, but for
                    // the rest we construct null values.
                    if (i == j)
                    {
                        projectOutputs.AddRange(newFlattenedElementVars);
                    }
                    else
                    {
                        foreach (var v in otherCollectionInfo.FlattenedElementVars)
                        {
                            var nullOp = Command.CreateNullOp(v.Type);
                            var nullOpNode = Command.CreateNode(nullOp);
                            Var nullOpVar;
                            var nullOpVarDefNode = Command.CreateVarDefNode(nullOpNode, out nullOpVar);
                            varDefListChildren.Add(nullOpVarDefNode);
                            projectOutputs.Add(nullOpVar);
//.........这里部分代码省略.........

        /// <summary>
        /// Input =>  Filter(input, Ref(var) is not null)
        /// </summary>
        /// <param name="input"></param>
        /// <param name="var"></param>
        /// <returns></returns>
        private Node CapWithIsNotNullFilter(Node input, Var var)
        {
            var varRefNode = Command.CreateNode(Command.CreateVarRefOp(var));
            var predicateNode = Command.CreateNode(
                Command.CreateConditionalOp(OpType.Not),
                Command.CreateNode(
                    Command.CreateConditionalOp(OpType.IsNull),
                    varRefNode));

            var filterNode = Command.CreateNode(Command.CreateFilterOp(), input, predicateNode);
            return filterNode;
        }

 /// <summary>
 /// Build up a CollectOp over a relop tree
 /// </summary>
 /// <param name="relOpNode">the relop tree</param>
 /// <param name="relOpVar">the single output var from the relop tree</param>
 /// <returns></returns>
 internal Node BuildCollect(Node relOpNode, Var relOpVar)
 {
     Node physicalProjectNode = this.CreateNode(this.CreatePhysicalProjectOp(relOpVar), relOpNode);
     TypeUsage collectOpType = TypeHelpers.CreateCollectionTypeUsage(relOpVar.Type);
     Node collectNode = this.CreateNode(this.CreateCollectOp(collectOpType), physicalProjectNode);
     return collectNode;
 }

 /// <summary>
 /// 'Extend' a given input node to also project out an internal integer constant with the given value
 /// </summary>
 /// <param name="input"></param>
 /// <param name="value"></param>
 /// <param name="internalConstantVar"></param>
 /// <returns></returns>
 private Node AugmentNodeWithInternalIntegerConstant(Node input, int value, out Var internalConstantVar)
 {
     return AugmentNodeWithConstant(
         input, () => Command.CreateInternalConstantOp(Command.IntegerType, value), out internalConstantVar);
 }

        /// <summary>
        /// Build the equivalent of an OfTypeExpression over the input (ie) produce the set of values from the
        /// input that are of the desired type (exactly of the desired type, if the "includeSubtypes" parameter is false).
        /// 
        /// Further more, "update" the result element type to be the desired type.
        /// 
        /// We accomplish this by first building a FilterOp with an IsOf (or an IsOfOnly) predicate for the desired 
        /// type. We then build out a ProjectOp over the FilterOp, where we introduce a "Fake" TreatOp over the input
        /// element to cast it to the right type. The "Fake" TreatOp is only there for "compile-time" typing reasons,
        /// and will be ignored in the rest of the plan compiler
        /// </summary>
        /// <param name="inputNode">the input collection</param>
        /// <param name="inputVar">the single Var produced by the input collection</param>
        /// <param name="desiredType">the desired element type </param>
        /// <param name="includeSubtypes">do we include subtypes of the desired element type</param>
        /// <param name="resultNode">the result subtree</param>
        /// <param name="resultVar">the single Var produced by the result subtree</param>
        internal void BuildOfTypeTree(Node inputNode, Var inputVar, TypeUsage desiredType, bool includeSubtypes,
            out Node resultNode, out Var resultVar)
        {
            Op isOfOp = includeSubtypes ? this.CreateIsOfOp(desiredType) : this.CreateIsOfOnlyOp(desiredType);
            Node predicate = this.CreateNode(isOfOp, this.CreateNode(this.CreateVarRefOp(inputVar)));
            Node filterNode = this.CreateNode(this.CreateFilterOp(), inputNode, predicate);

            resultNode = BuildFakeTreatProject(filterNode, inputVar, desiredType, out resultVar);
        }

 /// Builds out a ProjectOp over the input that introduces a "Fake" TreatOp over the input Var to cast it to the desired type
 /// The "Fake" TreatOp is only there for "compile-time" typing reasons, and will be ignored in the rest of the plan compiler.
 /// </summary>
 /// <param name="inputNode">the input collection</param>
 /// <param name="inputVar">the single Var produced by the input collection</param>
 /// <param name="desiredType">the desired element type </param>
 /// <param name="resultVar">the single Var produced by the result subtree</param>
 /// <returns>the result subtree</returns>
 internal Node BuildFakeTreatProject(Node inputNode, Var inputVar, TypeUsage desiredType, out Var resultVar)
 {
     Node treatNode = this.CreateNode(this.CreateFakeTreatOp(desiredType), 
         this.CreateNode(this.CreateVarRefOp(inputVar)));
     Node resultNode = this.BuildProject(inputNode, treatNode, out resultVar);
     return resultNode;
 }

 /// <summary>
 /// A "simpler" builder method for ProjectOp. The assumption is that the only output is the
 /// (var corresponding to) the computedExpression. None of the Vars of the "input" are projected out
 /// 
 /// The single output Var is returned in the "outputVar" parameter
 /// </summary>
 /// <param name="input">the input relop</param>
 /// <param name="computedExpression">the computed expression</param>
 /// <param name="projectVar">(output) the computed var corresponding to the computed expression</param>
 /// <returns>the new project subtree node</returns>
 internal Node BuildProject(Node input, Node computedExpression, out Var projectVar)
 {
     Node projectNode = BuildProject(input, new Var[] { }, new Node[] { computedExpression });
     projectVar = ((ProjectOp)projectNode.Op).Outputs.First;
     return projectNode;
 }

 /// <summary>
 /// A simplified version of the method above - each branch can produce only one var
 /// </summary>
 /// <param name="inputNodes"></param>
 /// <param name="inputVars"></param>
 /// <param name="resultNode"></param>
 /// <param name="resultVar"></param>
 internal void BuildUnionAllLadder(IList<Node> inputNodes, IList<Var> inputVars,
     out Node resultNode, out Var resultVar)
 {
     Debug.Assert(inputNodes.Count == inputVars.Count, "Count mismatch:" + inputNodes.Count + "," + inputVars.Count);
     IList<Var> varList;
     BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out varList);
     if (varList != null && varList.Count > 0)
     {
         resultVar = varList[0];
     }
     else
     {
         resultVar = null;
     }
 }

 /// <summary>
 /// Create a singleStreamNestOp
 /// </summary>
 /// <param name="keys">keys for the nest operation</param>
 /// <param name="prefixSortKeys">list of prefix sort keys</param>
 /// <param name="postfixSortKeys">list of postfix sort keys</param>
 /// <param name="outputVars">List of outputVars</param>
 /// <param name="collectionInfoList">CollectionInfo for each collection </param>
 /// <param name="discriminatorVar">Var describing the discriminator</param>
 /// <returns></returns>
 internal SingleStreamNestOp CreateSingleStreamNestOp(VarVec keys,
     List<SortKey> prefixSortKeys, List<SortKey> postfixSortKeys,
     VarVec outputVars,
     List<CollectionInfo> collectionInfoList, Var discriminatorVar)
 {
     return new SingleStreamNestOp(keys, prefixSortKeys, postfixSortKeys, outputVars, collectionInfoList, discriminatorVar);
 }