1 //---------------------------------------------------------------------
2 // <copyright file="PreProcessor.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
7 // @backupOwner Microsoft
8 //---------------------------------------------------------------------
10 //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
12 // It is fine to use Debug.Assert in cases where you assert an obvious thing that is supposed
13 // to prevent from simple mistakes during development (e.g. method argument validation
14 // in cases where it was you who created the variables or the variables had already been validated or
15 // in "else" clauses where due to code changes (e.g. adding a new value to an enum type) the default
16 // "else" block is chosen why the new condition should be treated separately). This kind of asserts are
17 // (can be) helpful when developing new code to avoid simple mistakes but have no or little value in
18 // the shipped product.
19 // PlanCompiler.Assert *MUST* be used to verify conditions in the trees. These would be assumptions
20 // about how the tree was built etc. - in these cases we probably want to throw an exception (this is
21 // what PlanCompiler.Assert does when the condition is not met) if either the assumption is not correct
22 // or the tree was built/rewritten not the way we thought it was.
23 // Use your judgment - if you rather remove an assert than ship it use Debug.Assert otherwise use
24 // PlanCompiler.Assert.
27 // The PreProcessor module is responsible for performing any required preprocessing
28 // on the tree and gathering information before subsequent phases may be performed.
29 // The main responsibilites of the preprocessor are:
31 // (a) gathering information about all structured types and entitysets referenced in the
33 // (b) expanding views, navigate operators, and rewritting other type related operators
34 // (c) gathering information about which subsequent phases may be requried
35 // (d) pulling sort over project, and removing unnecessary sorts
36 // (e) eliminates certain operations by translating them into equivalent subtrees
37 // (ElementOp, NewMultisetOp)
40 namespace System.Data.Query.PlanCompiler
42 using System.Collections.Generic;
43 using System.Data.Common;
44 using System.Data.Common.Utils;
45 using System.Data.Entity;
46 using System.Data.Mapping;
47 using System.Data.Metadata.Edm;
48 using System.Data.Query.InternalTrees;
50 internal class DiscriminatorMapInfo
52 internal EntityTypeBase RootEntityType;
53 internal bool IncludesSubTypes;
54 internal ExplicitDiscriminatorMap DiscriminatorMap;
56 internal DiscriminatorMapInfo(EntityTypeBase rootEntityType, bool includesSubTypes, ExplicitDiscriminatorMap discriminatorMap)
58 RootEntityType = rootEntityType;
59 IncludesSubTypes = includesSubTypes;
60 DiscriminatorMap = discriminatorMap;
64 /// Merge the discriminatorMap info we just found with what we've already found.
66 /// In practice, if either the current or the new map is from an OfTypeOnly view, we
67 /// have to avoid the optimizations.
69 /// If we have a new map that is a superset of the current map, then we can just swap
70 /// the new map for the current one.
72 /// If the current map is tha super set of the new one ther's nothing to do.
74 /// (Of course, if neither has changed, then we really don't need to look)
76 internal void Merge(EntityTypeBase neededRootEntityType, bool includesSubtypes, ExplicitDiscriminatorMap discriminatorMap)
78 // If what we've found doesn't exactly match what we are looking for we have more work to do
79 if (RootEntityType != neededRootEntityType || IncludesSubTypes != includesSubtypes)
81 if (!IncludesSubTypes || !includesSubtypes)
83 // If either the original or the new map is from an of-type-only view we can't
84 // merge, we just have to not optimize this case.
85 DiscriminatorMap = null;
88 if (TypeSemantics.IsSubTypeOf(RootEntityType, neededRootEntityType))
90 // we're asking for a super type of existing type, and what we had is a proper
91 // subset of it -we can replace the existing item.
92 RootEntityType = neededRootEntityType;
93 DiscriminatorMap = discriminatorMap;
95 if (!TypeSemantics.IsSubTypeOf(neededRootEntityType, RootEntityType))
97 // If either the original or the new map is from an of-type-only view we can't
98 // merge, we just have to not optimize this case.
99 DiscriminatorMap = null;
106 /// The PreProcessor module is responsible for performing any required preprocessing
107 /// on the tree and gathering information before subsequent phases may be performed.
109 internal class PreProcessor : SubqueryTrackingVisitor
111 #region private state
113 /// Tracks affinity of entity constructors to entity sets (aka scoped entity type constructors).
114 /// Scan view ops and entityset-bound tvfs push corresponding entity sets so that their child nodes representing entity constructors could
115 /// determine the entity set to which the constructed entity belongs.
117 private readonly Stack<EntitySet> m_entityTypeScopes = new Stack<EntitySet>();
119 // Track referenced types, entitysets, entitycontainers, free floating entity constructor types
120 // and types needing a null sentinel.
121 private readonly HashSet<EntityContainer> m_referencedEntityContainers = new HashSet<EntityContainer>();
122 private readonly HashSet<EntitySet> m_referencedEntitySets = new HashSet<EntitySet>();
123 private readonly HashSet<TypeUsage> m_referencedTypes = new HashSet<TypeUsage>();
124 private readonly HashSet<EntityType> m_freeFloatingEntityConstructorTypes = new HashSet<EntityType>();
125 private readonly HashSet<string> m_typesNeedingNullSentinel = new HashSet<string>();
126 private readonly Dictionary<EdmFunction, EdmProperty[]> m_tvfResultKeys = new Dictionary<EdmFunction, EdmProperty[]>();
129 /// Helper for rel properties
131 private RelPropertyHelper m_relPropertyHelper;
133 // Track discriminator metadata.
134 private bool m_suppressDiscriminatorMaps;
135 private readonly Dictionary<EntitySetBase, DiscriminatorMapInfo> m_discriminatorMaps = new Dictionary<EntitySetBase, DiscriminatorMapInfo>();
139 private PreProcessor(PlanCompiler planCompilerState)
140 : base(planCompilerState)
142 m_relPropertyHelper = new RelPropertyHelper(m_command.MetadataWorkspace, m_command.ReferencedRelProperties);
146 #region public methods
148 /// The driver routine.
150 /// <param name="planCompilerState">plan compiler state</param>
151 /// <param name="typeInfo">type information about all types/sets referenced in the query</param>
152 /// <param name="tvfResultKeys">inferred key columns of tvfs return types</param>
153 internal static void Process(
154 PlanCompiler planCompilerState,
155 out StructuredTypeInfo typeInfo,
156 out Dictionary<EdmFunction, EdmProperty[]> tvfResultKeys)
158 PreProcessor preProcessor = new PreProcessor(planCompilerState);
159 preProcessor.Process(out tvfResultKeys);
161 StructuredTypeInfo.Process(planCompilerState.Command,
162 preProcessor.m_referencedTypes,
163 preProcessor.m_referencedEntitySets,
164 preProcessor.m_freeFloatingEntityConstructorTypes,
165 preProcessor.m_suppressDiscriminatorMaps ? null : preProcessor.m_discriminatorMaps,
166 preProcessor.m_relPropertyHelper,
167 preProcessor.m_typesNeedingNullSentinel,
173 #region private methods
176 internal void Process(out Dictionary<EdmFunction, EdmProperty[]> tvfResultKeys)
178 m_command.Root = VisitNode(m_command.Root);
180 // Add any Vars that are of structured type - if the Vars aren't
181 // referenced via a VarRefOp, we end up losing them...
183 foreach (Var v in m_command.Vars)
185 AddTypeReference(v.Type);
189 // If we have any "structured" types, then we need to run through NTE
191 if (m_referencedTypes.Count > 0)
193 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NTE);
196 // Find any structured types that are projected at the top level, and
197 // ensure that we can handle their nullability.
199 PhysicalProjectOp ppOp = (PhysicalProjectOp)m_command.Root.Op; // this better be the case or we have other problems.
200 ppOp.ColumnMap.Accept(StructuredTypeNullabilityAnalyzer.Instance, m_typesNeedingNullSentinel);
203 tvfResultKeys = m_tvfResultKeys;
207 #region private state maintenance - type and set information
210 /// Mark this EntitySet as referenced in the query
212 /// <param name="entitySet"></param>
213 private void AddEntitySetReference(EntitySet entitySet)
215 m_referencedEntitySets.Add(entitySet);
216 if (!m_referencedEntityContainers.Contains(entitySet.EntityContainer))
218 m_referencedEntityContainers.Add(entitySet.EntityContainer);
223 /// Mark this type as being referenced in the query, if it is a structured, collection or enum type.
225 /// <param name="type">type to reference</param>
226 private void AddTypeReference(TypeUsage type)
228 if (TypeUtils.IsStructuredType(type) || TypeUtils.IsCollectionType(type) || TypeUtils.IsEnumerationType(type))
230 m_referencedTypes.Add(type);
235 /// Get the list of relationshipsets that can hold instances of the given relationshiptype
237 /// We identify the list of relationshipsets in the current list of entitycontainers that are
238 /// of the given type. Since we don't yet support relationshiptype subtyping, this is a little
239 /// easier than the entity version
241 /// <param name="relType">the relationship type to look for</param>
242 /// <returns>the list of relevant relationshipsets</returns>
243 private List<RelationshipSet> GetRelationshipSets(RelationshipType relType)
245 List<RelationshipSet> relSets = new List<RelationshipSet>();
246 foreach (EntityContainer entityContainer in m_referencedEntityContainers)
248 foreach (EntitySetBase set in entityContainer.BaseEntitySets)
250 RelationshipSet relSet = set as RelationshipSet;
251 if (relSet != null &&
252 relSet.ElementType.Equals(relType))
262 /// Find all entitysets (that are reachable in the current query) that can hold instances that
263 /// are *at least* of type "entityType".
264 /// An entityset ES of type T1 can hold instances that are at least of type T2, if one of the following
266 /// - T1 is a subtype of T2
267 /// - T2 is a subtype of T1
268 /// - T1 is equal to T2
270 /// <param name="entityType">the desired entity type</param>
271 /// <returns>list of all entitysets of the desired shape</returns>
272 private List<EntitySet> GetEntitySets(TypeUsage entityType)
274 List<EntitySet> sets = new List<EntitySet>();
275 foreach (EntityContainer container in m_referencedEntityContainers)
277 foreach (EntitySetBase baseSet in container.BaseEntitySets)
279 EntitySet set = baseSet as EntitySet;
281 (set.ElementType.Equals(entityType.EdmType) ||
282 TypeSemantics.IsSubTypeOf(entityType.EdmType, set.ElementType) ||
283 TypeSemantics.IsSubTypeOf(set.ElementType, entityType.EdmType)))
295 #region View Expansion
297 /// Gets the "expanded" query mapping view for the specified C-Space entity set
299 /// <param name="node">The current node</param>
300 /// <param name="scanTableOp">The scanTableOp that references the entity set</param>
301 /// <param name="typeFilter">
302 /// An optional type filter to apply to the generated view.
303 /// Set to <c>null</c> on return if the generated view renders the type filter superfluous.
305 /// <returns>A node that is the root of the new expanded view</returns>
306 private Node ExpandView(Node node, ScanTableOp scanTableOp, ref IsOfOp typeFilter)
308 EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent;
309 PlanCompiler.Assert(entitySet != null, "The target of a ScanTableOp must reference an EntitySet to be used with ExpandView");
310 PlanCompiler.Assert(entitySet.EntityContainer.DataSpace == DataSpace.CSpace, "Store entity sets cannot have Query Mapping Views and should not be used with ExpandView");
312 if (typeFilter != null &&
313 !typeFilter.IsOfOnly &&
314 TypeSemantics.IsSubTypeOf(entitySet.ElementType, typeFilter.IsOfType.EdmType))
317 // If a type filter is being applied to the ScanTableOp, but that filter is asking
318 // for all elements that are the same type or a supertype of the element type of the
319 // target entity set, then the type filter is a no-op and can safely be discarded -
320 // IF AND ONLY IF the type filter is 'OfType' - which includes subtypes - and NOT
321 // 'IsOfOnly' - which requires an exact type match, and so does not include subtypes.
327 // Call the GetGeneratedView method to retrieve the query mapping view for the extent referenced
328 // by the ScanTableOp. The actual method used to do this differs depending on whether the default
329 // Query Mapping View is sufficient or a targeted view that only filters by element type is required.
331 System.Data.Mapping.ViewGeneration.GeneratedView definingQuery = null;
332 EntityTypeBase requiredType = scanTableOp.Table.TableMetadata.Extent.ElementType;
333 bool includeSubtypes = true;
334 if (typeFilter != null)
337 // A type filter is being applied to the ScanTableOp; it may be possible to produce
338 // an optimized expansion of the view based on type-specific views generated for the
339 // C-Space entity set.
340 // The type for which the view should be tuned is the 'OfType' specified on the type filter.
341 // If the type filter is an 'IsOfOnly' filter then the view should NOT include subtypes of the required type.
343 requiredType = (EntityTypeBase)typeFilter.IsOfType.EdmType;
344 includeSubtypes = !typeFilter.IsOfOnly;
345 if (m_command.MetadataWorkspace.TryGetGeneratedViewOfType(entitySet, requiredType, includeSubtypes, out definingQuery))
348 // At this point a type-specific view was found that satisifies the type filter's
349 // constraints in terms of required type and whether subtypes should be included;
350 // the type filter itself is now unnecessary and should be set to null indicating
351 // that it can be safely removed (see ProcessScanTableOp and Visit(FilterOp) for this).
358 // If a generated view has not been obtained at this point then either:
359 // - A type filter was specified but no type-specific view exists that satisfies its constraints.
361 // - No type filter was specified.
362 // In either case the default query mapping view for the referenced entity set should now be retrieved.
364 if (null == definingQuery)
366 definingQuery = m_command.MetadataWorkspace.GetGeneratedView(entitySet);
370 // If even the default query mapping view was not found then we cannot continue.
371 // This implies that the set was not mapped, which should not be allowed, therefore
372 // a retail assert is used here instead of a regular exception.
374 PlanCompiler.Assert(definingQuery != null, Strings.ADP_NoQueryMappingView(entitySet.EntityContainer.Name, entitySet.Name));
377 // At this point we're guaranteed to have found a defining query for the view.
378 // We're now going to convert this into an IQT, and then copy it into our own IQT.
380 Node ret = definingQuery.GetInternalTree(m_command);
383 // Make sure we're tracking what we've asked any discriminator maps to contain.
385 DetermineDiscriminatorMapUsage(ret, entitySet, requiredType, includeSubtypes);
388 // Build up a ScanViewOp to "cap" the defining query below
390 ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table);
391 ret = m_command.CreateNode(scanViewOp, ret);
398 /// If the discrminator map we're already tracking for this type (in this entityset)
399 /// isn't already rooted at our required type, then we have to suppress the use of
400 /// the descriminator maps when we constrct the structuredtypes; see SQLBUDT #615744
402 private void DetermineDiscriminatorMapUsage(Node viewNode, EntitySetBase entitySet, EntityTypeBase rootEntityType, bool includeSubtypes)
404 ExplicitDiscriminatorMap discriminatorMap = null;
406 // we expect the view to be capped with a project; we're just being careful here.
407 if (viewNode.Op.OpType == OpType.Project)
409 DiscriminatedNewEntityOp discriminatedNewEntityOp = viewNode.Child1.Child0.Child0.Op as DiscriminatedNewEntityOp;
411 if (null != discriminatedNewEntityOp)
413 discriminatorMap = discriminatedNewEntityOp.DiscriminatorMap;
417 DiscriminatorMapInfo discriminatorMapInfo;
418 if (!m_discriminatorMaps.TryGetValue(entitySet, out discriminatorMapInfo))
420 if (null == rootEntityType)
422 rootEntityType = entitySet.ElementType;
423 includeSubtypes = true;
425 discriminatorMapInfo = new DiscriminatorMapInfo(rootEntityType, includeSubtypes, discriminatorMap);
426 m_discriminatorMaps.Add(entitySet, discriminatorMapInfo);
430 discriminatorMapInfo.Merge(rootEntityType, includeSubtypes, discriminatorMap);
436 #region NavigateOp rewrites
438 /// Rewrites a NavigateOp tree in the following fashion
439 /// SELECT VALUE r.ToEnd
440 /// FROM (SELECT VALUE r1 FROM RS1 as r1
442 /// SELECT VALUE r2 FROM RS2 as r2
444 /// SELECT VALUE rN FROM RSN as rN) as r
445 /// WHERE r.FromEnd = sourceRef
447 /// RS1, RS2 etc. are the set of all relationshipsets that can hold instances of the specified
448 /// relationship type. "sourceRef" is the single (ref-type) argument to the NavigateOp that
449 /// represents the from-end of the navigation traversal
450 /// If the toEnd is multi-valued, then we stick a Collect(PhysicalProject( over the subquery above
452 /// A couple of special cases.
453 /// If no relationship sets can be found, we return a NULL (if the
454 /// toEnd is single-valued), or an empty multiset (if the toEnd is multi-valued)
456 /// If the toEnd is single-valued, *AND* the input Op is a GetEntityRefOp, then
457 /// we convert the NavigateOp into a RelPropertyOp over the entity.
459 /// <param name="navigateOpNode">the navigateOp tree</param>
460 /// <param name="navigateOp">the navigateOp</param>
461 /// <param name="outputVar">the output var produced by the subquery (ONLY if the to-End is single-valued)</param>
462 /// <returns>the resulting node</returns>
463 private Node RewriteNavigateOp(Node navigateOpNode, NavigateOp navigateOp, out Var outputVar)
468 // Currently, navigation of composition relationships is not supported.
470 if (!Helper.IsAssociationType(navigateOp.Relationship))
472 throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_RelNav_NoCompositions);
476 // If the input to the navigateOp is a GetEntityRefOp, and the navigation
477 // is to the 1-end of the relationship, convert this into a RelPropertyOp instead - operating on the
478 // input child to the GetEntityRefOp
480 if (navigateOpNode.Child0.Op.OpType == OpType.GetEntityRef &&
481 (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne ||
482 navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One))
484 PlanCompiler.Assert(m_command.IsRelPropertyReferenced(navigateOp.RelProperty),
485 "Unreferenced rel property? " + navigateOp.RelProperty);
486 Op relPropertyOp = m_command.CreateRelPropertyOp(navigateOp.RelProperty);
487 Node relPropertyNode = m_command.CreateNode(relPropertyOp,
488 navigateOpNode.Child0.Child0);
489 return relPropertyNode;
492 List<RelationshipSet> relationshipSets = GetRelationshipSets(navigateOp.Relationship);
495 // Special case: when no relationshipsets can be found. Return NULL or an empty multiset,
496 // depending on the multiplicity of the toEnd
498 if (relationshipSets.Count == 0)
501 // If we're navigating to the 1-end of the relationship, then simply return a null constant
503 if (navigateOp.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many)
505 return m_command.CreateNode(m_command.CreateNullOp(navigateOp.Type));
507 else // return an empty set
509 return m_command.CreateNode(m_command.CreateNewMultisetOp(navigateOp.Type));
514 // Build up a UNION-ALL ladder over all the relationshipsets
516 List<Node> scanTableNodes = new List<Node>();
517 List<Var> scanTableVars = new List<Var>();
518 foreach (RelationshipSet relSet in relationshipSets)
520 TableMD tableMD = Command.CreateTableDefinition(relSet);
521 ScanTableOp tableOp = m_command.CreateScanTableOp(tableMD);
522 Node branchNode = m_command.CreateNode(tableOp);
523 Var branchVar = tableOp.Table.Columns[0];
524 scanTableVars.Add(branchVar);
525 scanTableNodes.Add(branchNode);
528 Node unionAllNode = null;
530 m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
533 // Now build up the predicate
535 Node targetEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.ToEnd),
536 m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
537 Node sourceEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.FromEnd),
538 m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
539 Node predicateNode = m_command.BuildComparison(OpType.EQ, navigateOpNode.Child0, sourceEnd);
540 Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
541 unionAllNode, predicateNode);
543 Node projectNode = m_command.BuildProject(filterNode, targetEnd, out projectVar);
546 // Finally, some magic about single-valued vs collection-valued ends
549 if (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
551 ret = m_command.BuildCollect(projectNode, projectVar);
556 outputVar = projectVar;
563 #region DerefOp Rewrites
565 /// Build up a node tree that represents the set of instances from the given table that are at least
566 /// of the specified type ("ofType"). If "ofType" is NULL, then all rows are returned
568 /// Return the outputVar from the nodetree
570 /// <param name="entitySet">the entityset or relationshipset to scan over</param>
571 /// <param name="ofType">the element types we're interested in</param>
572 /// <param name="resultVar">the output var produced by this node tree</param>
573 /// <returns>the node tree</returns>
574 private Node BuildOfTypeTable(EntitySetBase entitySet, TypeUsage ofType, out Var resultVar)
576 TableMD tableMetadata = Command.CreateTableDefinition(entitySet);
577 ScanTableOp tableOp = m_command.CreateScanTableOp(tableMetadata);
578 Node tableNode = m_command.CreateNode(tableOp);
579 Var tableVar = tableOp.Table.Columns[0];
583 // Build a logical "oftype" expression - simply a filter predicate
585 if ((ofType != null) && !entitySet.ElementType.EdmEquals(ofType.EdmType))
587 m_command.BuildOfTypeTree(tableNode, tableVar, ofType, true, out resultNode, out resultVar);
591 resultNode = tableNode;
592 resultVar = tableVar;
599 /// Produces a relop tree that "logically" produces the target of the derefop. In essence, this gets rewritten
602 /// FROM (SELECT VALUE e0 FROM OFTYPE(ES0, T) as e0
604 /// SELECT VALUE e1 FROM OFTYPE(ES1, T) as e1
606 /// SELECT VALUE eN from OFTYPE(ESN, T) as eN)) as e
607 /// WHERE REF(e) = myRef
609 /// "T" is the target type of the Deref, and myRef is the (single) argument to the DerefOp
611 /// ES0, ES1 etc. are all the EntitySets that could hold instances that are at least of type "T". We identify this list of sets
612 /// by looking at all entitycontainers referenced in the query, and looking at all entitysets in those
613 /// containers that are of the right type
614 /// An EntitySet ES (of entity type X) can hold instances of T, if one of the following is true
615 /// - T is a subtype of X
616 /// - X is equal to T
617 /// Our situation is a little trickier, since we also need to look for cases where X is a subtype of T.
619 /// <param name="derefOpNode">the derefOp subtree</param>
620 /// <param name="derefOp">the derefOp</param>
621 /// <param name="outputVar">output var produced</param>
622 /// <returns>the subquery described above</returns>
623 private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar)
625 TypeUsage entityType = derefOp.Type;
626 List<EntitySet> targetEntitySets = GetEntitySets(entityType);
627 if (targetEntitySets.Count == 0)
629 // We didn't find any entityset that could match this. Simply return a null-value
631 return m_command.CreateNode(m_command.CreateNullOp(entityType));
634 List<Node> scanTableNodes = new List<Node>();
635 List<Var> scanTableVars = new List<Var>();
636 foreach (EntitySet entitySet in targetEntitySets)
639 Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
641 scanTableNodes.Add(tableNode);
642 scanTableVars.Add(tableVar);
646 m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
649 // Finally build up the key comparison predicate
651 Node entityRefNode = m_command.CreateNode(
652 m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type),
653 m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
654 Node keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode);
655 Node filterNode = m_command.CreateNode(
656 m_command.CreateFilterOp(),
660 outputVar = unionAllVar;
665 #region NavigationProperty Rewrites
668 /// Find the entityset that corresponds to the specified end of the relationship.
670 /// We must find one - else we assert.
672 /// <param name="relationshipSet">the relationshipset</param>
673 /// <param name="targetEnd">the destination end of the relationship traversal</param>
674 /// <returns>the entityset corresponding to the target end</returns>
675 private static EntitySetBase FindTargetEntitySet(RelationshipSet relationshipSet, RelationshipEndMember targetEnd)
677 EntitySetBase entitySet = null;
679 AssociationSet associationSet = (AssociationSet)relationshipSet;
680 // find the corresponding entityset
682 foreach (AssociationSetEnd e in associationSet.AssociationSetEnds)
684 if (e.CorrespondingAssociationEndMember.EdmEquals(targetEnd))
686 entitySet = e.EntitySet;
690 PlanCompiler.Assert(entitySet != null, "Could not find entityset for relationshipset " + relationshipSet + ";association end " + targetEnd);
696 /// Builds up a join between the relationshipset and the entityset corresponding to its toEnd. In essence,
699 /// FROM RS as r, OFTYPE(ES, T) as e
700 /// WHERE r.ToEnd = Ref(e)
702 /// "T" is the entity type of the toEnd of the relationship.
704 /// <param name="relSet">the relationshipset</param>
705 /// <param name="end">the toEnd of the relationship</param>
706 /// <param name="rsVar">the var representing the relationship instance ("r") in the output subquery</param>
707 /// <param name="esVar">the var representing the entity instance ("e") in the output subquery</param>
708 /// <returns>the join subquery described above</returns>
709 private Node BuildJoinForNavProperty(RelationshipSet relSet, RelationshipEndMember end,
710 out Var rsVar, out Var esVar)
712 EntitySetBase entitySet = FindTargetEntitySet(relSet, end);
715 // Build out the ScanTable ops for the relationshipset and the entityset. Add the
717 Node asTableNode = BuildOfTypeTable(relSet, null, out rsVar);
718 Node esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar);
721 // Build up a join between the entityset and the associationset; join on the to-end
723 Node joinPredicate = m_command.BuildComparison(OpType.EQ,
724 m_command.CreateNode(m_command.CreateGetEntityRefOp(end.TypeUsage), m_command.CreateNode(m_command.CreateVarRefOp(esVar))),
725 m_command.CreateNode(m_command.CreatePropertyOp(end), m_command.CreateNode(m_command.CreateVarRefOp(rsVar)))
728 Node joinNode = m_command.CreateNode(m_command.CreateInnerJoinOp(),
729 asTableNode, esTableNode, joinPredicate);
735 /// Rewrite a navigation property when the target end has multiplicity
736 /// of one (or zero..one) and the source end has multiplicity of many.
738 /// Note that this translation is also valid for a navigation property when the target
739 /// end has multiplicity of one (or zero..one) and the source end has multiplicity of one
740 /// (or zero..one), but a different translation is used because it yields a simpler query in some cases.
742 /// We simply pick up the corresponding rel property from the input entity, and
743 /// apply a deref operation
744 /// NavProperty(e, n) => deref(relproperty(e, r))
745 /// where e is the entity expression, n is the nav-property, and r is the corresponding
748 /// <param name="relProperty">the rel-property describing the navigation</param>
749 /// <param name="sourceEntityNode">entity instance that we're starting the traversal from</param>
750 /// <param name="resultType">type of the target entity</param>
751 /// <returns>a rewritten subtree</returns>
752 private Node RewriteManyToOneNavigationProperty(RelProperty relProperty,
753 Node sourceEntityNode, TypeUsage resultType)
755 RelPropertyOp relPropertyOp = m_command.CreateRelPropertyOp(relProperty);
756 Node relPropertyNode = m_command.CreateNode(relPropertyOp, sourceEntityNode);
757 DerefOp derefOp = m_command.CreateDerefOp(resultType);
758 Node derefNode = m_command.CreateNode(derefOp, relPropertyNode);
764 /// Rewrite a navigation property when the source end has multiplicity
765 /// of one (or zero..one) and the target end has multiplicity of many.
767 /// <see cref="RewriteFromOneNavigationProperty"/>
768 /// We also build out a CollectOp over the subquery above, and return that
770 /// <param name="relProperty">the rel-property describing the relationship traversal</param>
771 /// <param name="relationshipSets">the list of relevant relationshipsets</param>
772 /// <param name="sourceRefNode">node tree corresponding to the source entity ref</param>
773 /// <returns>the rewritten subtree</returns>
774 private Node RewriteOneToManyNavigationProperty(RelProperty relProperty,
775 List<RelationshipSet> relationshipSets,
779 Node ret = RewriteFromOneNavigationProperty(relProperty, relationshipSets, sourceRefNode, out outputVar);
781 // The return value is a collection, but used as a property, thus it needs to be capped with a collect
782 ret = m_command.BuildCollect(ret, outputVar);
788 /// Rewrite a navigation property when the target end has multiplicity
789 /// of one (or zero..one) and the source end has multiplicity of one (or zero..one).
791 /// <see cref="RewriteFromOneNavigationProperty"/>
792 /// We add the translation as a subquery to the parent rel op and return a reference to
793 /// the corresponding var
795 /// <param name="relProperty">the rel-property describing the relationship traversal</param>
796 /// <param name="relationshipSets">the list of relevant relationshipsets</param>
797 /// <param name="sourceRefNode">node tree corresponding to the source entity ref</param>
798 /// <returns>the rewritten subtree</returns>
799 private Node RewriteOneToOneNavigationProperty(RelProperty relProperty,
800 List<RelationshipSet> relationshipSets,
804 Node ret = RewriteFromOneNavigationProperty(relProperty, relationshipSets, sourceRefNode, out outputVar);
806 ret = VisitNode(ret);
807 ret = AddSubqueryToParentRelOp(outputVar, ret);
813 /// Translation for Navigation Properties with a 0 or 0..1 source end
814 /// In essence, we find all the relevant target entitysets, and then compare the
815 /// rel-property on the target end with the source ref
818 /// NavigationProperty(e, r)
821 /// FROM (SELECT VALUE e1 FROM ES1 as e1
823 /// SELECT VALUE e2 FROM ES2 as e2
827 /// WHERE RelProperty(t, r') = GetEntityRef(e)
829 /// r' is the inverse-relproperty for r
831 /// <param name="relProperty">the rel-property describing the relationship traversal</param>
832 /// <param name="relationshipSets">the list of relevant relationshipsets</param>
833 /// <param name="sourceRefNode">node tree corresponding to the source entity ref</param>
834 /// <param name="outputVar">the var representing the output</param>
835 /// <returns>the rewritten subtree</returns>
836 private Node RewriteFromOneNavigationProperty(RelProperty relProperty, List<RelationshipSet> relationshipSets, Node sourceRefNode, out Var outputVar)
838 PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
839 PlanCompiler.Assert(relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many,
840 "Expected source end multiplicity to be one. Found 'Many' instead " + relProperty);
842 TypeUsage entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage);
843 List<Node> scanTableNodes = new List<Node>(relationshipSets.Count);
844 List<Var> scanTableVars = new List<Var>(relationshipSets.Count);
845 foreach (RelationshipSet r in relationshipSets)
847 EntitySetBase entitySet = FindTargetEntitySet(r, relProperty.ToEnd);
849 Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
851 scanTableNodes.Add(tableNode);
852 scanTableVars.Add(tableVar);
856 // Build the union-all node
860 m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out outputVar);
863 // Now build up the appropriate filter. Select out the relproperty from the other end
865 RelProperty inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd);
866 PlanCompiler.Assert(m_command.IsRelPropertyReferenced(inverseRelProperty),
867 "Unreferenced rel property? " + inverseRelProperty);
868 Node inverseRelPropertyNode = m_command.CreateNode(
869 m_command.CreateRelPropertyOp(inverseRelProperty),
870 m_command.CreateNode(m_command.CreateVarRefOp(outputVar)));
871 Node predicateNode = m_command.BuildComparison(OpType.EQ,
872 sourceRefNode, inverseRelPropertyNode);
873 Node ret = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicateNode);
879 /// Rewrite a navigation property when the target end has multiplicity
880 /// many and the source end has multiplicity of many.
882 /// Consider this a rewrite of DEREF(NAVIGATE(r)) where "r" is a many-to-many relationship
884 /// We essentially produce the following subquery
886 /// FROM (SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
888 /// SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
891 /// WHERE x.r.FromEnd = sourceRef
893 /// RS1, RS2 etc. are the relevant relationshipsets
894 /// ES1, ES2 etc. are the corresponding entitysets for the toEnd of the relationship
895 /// sourceRef is the ref argument
896 /// T is the type of the target-end of the relationship
898 /// We then build a CollectOp over the subquery above
900 /// <param name="relProperty">the rel property to traverse</param>
901 /// <param name="relationshipSets">list of relevant relationshipsets</param>
902 /// <param name="sourceRefNode">source ref</param>
903 /// <returns></returns>
904 private Node RewriteManyToManyNavigationProperty(RelProperty relProperty,
905 List<RelationshipSet> relationshipSets,
908 PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
909 PlanCompiler.Assert(relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many &&
910 relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many,
911 "Expected target end multiplicity to be 'many'. Found " + relProperty + "; multiplicity = " + relProperty.ToEnd.RelationshipMultiplicity);
915 List<Node> joinNodes = new List<Node>(relationshipSets.Count);
916 List<Var> outputVars = new List<Var>(relationshipSets.Count * 2);
917 foreach (RelationshipSet r in relationshipSets)
921 Node joinNode = BuildJoinForNavProperty(r, relProperty.ToEnd, out rsVar, out esVar);
922 joinNodes.Add(joinNode);
923 outputVars.Add(rsVar);
924 outputVars.Add(esVar);
928 // Build the union-all node
931 IList<Var> unionAllVars;
932 m_command.BuildUnionAllLadder(joinNodes, outputVars, out unionAllNode, out unionAllVars);
935 // Now build out the filterOp over the left-side var
937 Node rsSourceRefNode = m_command.CreateNode(m_command.CreatePropertyOp(relProperty.FromEnd),
938 m_command.CreateNode(m_command.CreateVarRefOp(unionAllVars[0])));
939 Node predicate = m_command.BuildComparison(OpType.EQ,
940 sourceRefNode, rsSourceRefNode);
941 Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
942 unionAllNode, predicate);
945 // Finally, build out a project node that only projects out the entity side
947 Node projectNode = m_command.BuildProject(filterNode, new Var[] { unionAllVars[1] }, new Node[] { });
950 // Build a collectOp over the project node
952 ret = m_command.BuildCollect(projectNode, unionAllVars[1]);
958 /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r))
960 /// We handle four cases here, depending on the kind of relationship we're
962 /// - 1:1 relationships
963 /// - 1:M relationships
964 /// - N:1 relationships
965 /// - N:M relationships
968 /// <param name="navProperty">the navigation property</param>
969 /// <param name="sourceEntityNode">the input ref to start the traversal</param>
970 /// <param name="resultType">the result type of the expression</param>
971 /// <returns>the rewritten tree</returns>
972 private Node RewriteNavigationProperty(NavigationProperty navProperty,
973 Node sourceEntityNode, TypeUsage resultType)
975 RelProperty relProperty = new RelProperty(navProperty.RelationshipType, navProperty.FromEndMember, navProperty.ToEndMember);
976 PlanCompiler.Assert(m_command.IsRelPropertyReferenced(relProperty) || (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many),
977 "Unreferenced rel property? " + relProperty);
980 if ((relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many) &&
981 (relProperty.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many))
983 return RewriteManyToOneNavigationProperty(relProperty, sourceEntityNode, resultType);
987 // Find the list of all relationships that could satisfy this relationship
988 // If we find no matching relationship set, simply return a null node / empty collection
990 List<RelationshipSet> relationshipSets = GetRelationshipSets(relProperty.Relationship);
991 if (relationshipSets.Count == 0)
993 // return an empty set / null node
994 if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
996 return m_command.CreateNode(m_command.CreateNewMultisetOp(resultType));
998 return m_command.CreateNode(m_command.CreateNullOp(resultType));
1001 // Build out a ref over the source entity
1002 Node sourceRefNode = m_command.CreateNode(
1003 m_command.CreateGetEntityRefOp(relProperty.FromEnd.TypeUsage),
1006 // Hanlde the 1:M and N:M cases
1007 if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
1010 if (relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
1012 return RewriteManyToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode);
1015 return RewriteOneToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode);
1019 return RewriteOneToOneNavigationProperty(relProperty, relationshipSets,sourceRefNode);
1024 #region visitor methods
1029 /// Default handler for scalar Ops. Simply traverses the children,
1030 /// and also identifies any structured types along the way
1032 /// <param name="op">the ScalarOp</param>
1033 /// <param name="n">current subtree</param>
1034 /// <returns>the possibly modified node</returns>
1035 protected override Node VisitScalarOpDefault(ScalarOp op, Node n)
1037 VisitChildren(n); // visit my children
1039 // keep track of referenced types
1040 AddTypeReference(op.Type);
1046 /// Rewrite a DerefOp subtree. We have two cases to consider here.
1047 /// We call RewriteDerefOp to return a subtree (and an optional outputVar).
1048 /// If the outputVar is null, then we simply return the subtree produced by those calls.
1049 /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
1053 /// select deref(e) from T
1054 /// gets rewritten into
1055 /// select v from T OuterApply X
1056 /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
1059 /// <param name="op">the derefOp</param>
1060 /// <param name="n">the deref subtree</param>
1061 /// <returns>the rewritten tree</returns>
1062 public override Node Visit(DerefOp op, Node n)
1066 VisitScalarOpDefault(op, n);
1068 Node ret = RewriteDerefOp(n, op, out outputVar);
1069 ret = VisitNode(ret);
1071 if (outputVar != null)
1073 ret = AddSubqueryToParentRelOp(outputVar, ret);
1080 /// Processing for an ElementOp. Replaces this by the corresponding Var from
1081 /// the subquery, and adds the subquery to the list of currently tracked subqueries
1083 /// <param name="op">the elementOp</param>
1084 /// <param name="n">current subtree</param>
1085 /// <returns>the Var from the subquery</returns>
1086 public override Node Visit(ElementOp op, Node n)
1088 VisitScalarOpDefault(op, n); // default processing
1090 // get to the subquery...
1091 Node subQueryRelOp = n.Child0;
1092 ProjectOp projectOp = (ProjectOp)subQueryRelOp.Op;
1093 PlanCompiler.Assert(projectOp.Outputs.Count == 1, "input to ElementOp has more than one output var?");
1094 Var projectVar = projectOp.Outputs.First;
1096 Node ret = AddSubqueryToParentRelOp(projectVar, subQueryRelOp);
1101 /// Mark Normalization as needed
1103 /// <param name="op"></param>
1104 /// <param name="n"></param>
1105 /// <returns></returns>
1106 public override Node Visit(ExistsOp op, Node n)
1108 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization);
1109 return base.Visit(op, n);
1113 /// Visit a function call expression. If function is mapped, expand and visit the mapping expression.
1114 /// If this is TVF or a collection aggregate function, NestPullUp and Normalization are needed.
1116 /// <param name="op"></param>
1117 /// <param name="n"></param>
1118 /// <returns></returns>
1119 public override Node Visit(FunctionOp op, Node n)
1121 if (op.Function.IsFunctionImport)
1123 PlanCompiler.Assert(op.Function.IsComposableAttribute, "Cannot process a non-composable function inside query tree composition.");
1125 FunctionImportMapping functionImportMapping = null;
1126 if (!m_command.MetadataWorkspace.TryGetFunctionImportMapping(op.Function, out functionImportMapping))
1128 throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_UnmappedFunctionImport(op.Function.FullName));
1130 PlanCompiler.Assert(functionImportMapping is FunctionImportMappingComposable, "Composable function import must have corresponding mapping.");
1131 var functionImportMappingComposable = (FunctionImportMappingComposable)functionImportMapping;
1133 // Visit children (function call arguments) before processing the function view.
1134 // Visiting argument trees before the view tree is required because we want to process them first
1135 // outside of the context of the view. For example if an argument tree contains a free-floating entity-type constructor
1136 // and the function mapping scopes the function results to a particular entity set, we don't want
1137 // the free-floating constructor to be auto-scoped to this set. So we process the argument first, it will
1138 // scope the constructor to the null scope and which guarantees that this constructor will not be rescoped after the argument
1139 // tree is embedded into the function view inside the functionMapping.GetInternalTree(...) call.
1142 // Get the mapping view of the function.
1143 Node ret = functionImportMappingComposable.GetInternalTree(m_command, n.Children);
1145 // Push the entity type scope, if any, before processing the view.
1146 if (op.Function.EntitySet != null)
1148 m_entityTypeScopes.Push(op.Function.EntitySet);
1149 AddEntitySetReference(op.Function.EntitySet);
1150 PlanCompiler.Assert(functionImportMappingComposable.TvfKeys != null && functionImportMappingComposable.TvfKeys.Length > 0, "Function imports returning entities must have inferred keys.");
1151 if (!m_tvfResultKeys.ContainsKey(functionImportMappingComposable.TargetFunction))
1153 m_tvfResultKeys.Add(functionImportMappingComposable.TargetFunction, functionImportMappingComposable.TvfKeys);
1157 // Rerun the processor over the resulting subtree.
1158 ret = VisitNode(ret);
1160 // Remove the entity type scope, if any.
1161 if (op.Function.EntitySet != null)
1163 var scope = m_entityTypeScopes.Pop();
1164 PlanCompiler.Assert(scope == op.Function.EntitySet, "m_entityTypeScopes stack is broken");
1171 PlanCompiler.Assert(op.Function.EntitySet == null, "Entity type scope is not supported on functions that aren't mapped.");
1173 // If this is TVF or a collection aggregate, function NestPullUp and Normalization are needed.
1174 if (TypeSemantics.IsCollectionType(op.Type) || PlanCompilerUtil.IsCollectionAggregateFunction(op, n))
1176 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
1177 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization);
1179 return base.Visit(op, n);
1184 /// Default processing.
1185 /// In addition, if the case statement is of the shape
1186 /// case when X then NULL else Y, or
1187 /// case when X then Y else NULL,
1188 /// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same,
1189 /// marks that type as needing a null sentinel.
1190 /// This allows in NominalTypeElimination the case op to be pushed inside Y's null sentinel.
1192 /// <param name="op"></param>
1193 /// <param name="n"></param>
1194 /// <returns></returns>
1195 public override Node Visit(CaseOp op, Node n)
1197 VisitScalarOpDefault(op, n);
1198 //special handling to enable optimization
1199 bool thenClauseIsNull;
1200 if (PlanCompilerUtil.IsRowTypeCaseOpWithNullability(op, n, out thenClauseIsNull))
1202 //Add a null sentinel for the row type
1203 m_typesNeedingNullSentinel.Add(op.Type.EdmType.Identity);
1209 /// Special processing for ConditionalOp is handled by <see cref="ProcessConditionalOp"/>
1211 /// <param name="op"></param>
1212 /// <param name="n"></param>
1213 /// <returns></returns>
1214 public override Node Visit(ConditionalOp op, Node n)
1216 VisitScalarOpDefault(op, n);
1217 ProcessConditionalOp(op, n);
1222 /// If it is a IsNull op over a row type or a complex type mark the type as needing a null sentinel.
1224 /// <param name="op"></param>
1225 /// <param name="n"></param>
1226 private void ProcessConditionalOp(ConditionalOp op, Node n)
1228 if (op.OpType == OpType.IsNull && TypeSemantics.IsRowType(n.Child0.Op.Type) || TypeSemantics.IsComplexType(n.Child0.Op.Type))
1230 StructuredTypeNullabilityAnalyzer.MarkAsNeedingNullSentinel(m_typesNeedingNullSentinel, n.Child0.Op.Type);
1234 #region PropertyOp Handling
1237 /// Validates that the nav property agrees with the underlying relationship
1239 /// <param name="op">the Nav PropertyOp</param>
1240 /// <param name="n">the subtree</param>
1241 private void ValidateNavPropertyOp(PropertyOp op, Node n)
1243 NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
1246 // If the result of the expanded form of the navigation property is not compatible with
1247 // the declared type of the property, then the navigation property is invalid in the
1248 // context of this command tree's metadata workspace.
1250 TypeUsage resultType = navProperty.ToEndMember.TypeUsage;
1251 if (TypeSemantics.IsReferenceType(resultType))
1253 resultType = TypeHelpers.GetElementTypeUsage(resultType);
1255 if (navProperty.ToEndMember.RelationshipMultiplicity == RelationshipMultiplicity.Many)
1257 resultType = TypeUsage.Create(resultType.EdmType.GetCollectionType());
1259 if (!TypeSemantics.IsStructurallyEqualOrPromotableTo(resultType, op.Type))
1261 throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_IncompatibleNavigationPropertyResult(
1262 navProperty.DeclaringType.FullName,
1270 /// Rewrite a PropertyOp subtree for a nav property
1271 /// <see cref="RewriteNavigationProperty"/> does the heavy lifting
1273 /// <param name="op">the PropertyOp</param>
1274 /// <param name="n">the current node</param>
1275 /// <returns>the rewritten subtree</returns>
1276 private Node VisitNavPropertyOp(PropertyOp op, Node n)
1278 ValidateNavPropertyOp(op, n);
1281 // In this special case we visit the parent before the child to avoid TSQL regressions.
1282 // In particular, a subquery coming out of the child would need to be attached to the closest rel-op parent
1283 // and if the parent is already visited that rel op parent would be part of the subtree resulting from the parent.
1284 // If the parent is not visited it would be a rel op parent higher in the tree (also valid), and leaves less room
1285 // for join elimination.
1286 // The original out-of-order visitation was put in place to work around a bug that has been fixed.
1288 bool visitChildLater = IsNavigationPropertyOverVarRef(n.Child0);
1289 if (!visitChildLater)
1291 VisitScalarOpDefault(op, n);
1294 NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
1295 Node ret = RewriteNavigationProperty(navProperty, n.Child0, op.Type);
1296 ret = VisitNode(ret);
1302 /// Is the given node of shape NavigationProperty(SoftCast(VarRef)), or NavigationProperty(VarRef)
1304 /// <param name="n"></param>
1305 /// <returns></returns>
1306 private static bool IsNavigationPropertyOverVarRef(Node n)
1308 if (n.Op.OpType != OpType.Property || (!Helper.IsNavigationProperty(((PropertyOp)n.Op).PropertyInfo)))
1313 Node currentNode = n.Child0;
1314 if (currentNode.Op.OpType == OpType.SoftCast)
1316 currentNode = currentNode.Child0;
1318 return currentNode.Op.OpType == OpType.VarRef;
1322 /// Rewrite a PropertyOp subtree.
1324 /// If the PropertyOp represents a simple property (ie) not a navigation property, we simply call
1325 /// VisitScalarOpDefault() and return. Otherwise, we call VisitNavPropertyOp and return the result from
1329 /// <param name="op">the PropertyOp</param>
1330 /// <param name="n">the PropertyOp subtree</param>
1331 /// <returns>the rewritten tree</returns>
1332 public override Node Visit(PropertyOp op, Node n)
1335 if (Helper.IsNavigationProperty(op.PropertyInfo))
1337 ret = VisitNavPropertyOp(op, n);
1341 ret = VisitScalarOpDefault(op, n);
1349 /// Handler for a RefOp.
1350 /// Keeps track of the entityset
1352 /// <param name="op">the RefOp</param>
1353 /// <param name="n">current RefOp subtree</param>
1354 /// <returns>current subtree</returns>
1355 public override Node Visit(RefOp op, Node n)
1357 VisitScalarOpDefault(op, n); // use default processing
1358 AddEntitySetReference(op.EntitySet); // add to list of references
1363 /// Handler for a TreatOp.
1364 /// Rewrites the operator if the argument is guaranteed to be of type
1367 /// <param name="op">Current TreatOp</param>
1368 /// <param name="n">Current subtree</param>
1369 /// <returns>Current subtree</returns>
1370 public override Node Visit(TreatOp op, Node n)
1372 n = base.Visit(op, n);
1374 // See if TreatOp can be rewritten (if it's not polymorphic)
1375 if (CanRewriteTypeTest(op.Type.EdmType, n.Child0.Op.Type.EdmType))
1377 // Return argument directly (if the argument is null, 'treat as' also returns null;
1378 // if the argument is not null, it's guaranteed to be of the correct type)
1386 /// Handler for an IsOfOp.
1387 /// Keeps track of the IsOfType (if it is a structured type) and rewrites the
1388 /// operator if the argument is guaranteed to be of type op.IsOfType
1390 /// <param name="op">Current IsOfOp</param>
1391 /// <param name="n">Current subtree</param>
1392 /// <returns>Current subtree</returns>
1393 public override Node Visit(IsOfOp op, Node n)
1395 VisitScalarOpDefault(op, n); // default handling first
1396 // keep track of any structured types
1397 AddTypeReference(op.IsOfType);
1399 // See if the IsOfOp can be rewritten (if it's not polymorphic)
1400 if (CanRewriteTypeTest(op.IsOfType.EdmType, n.Child0.Op.Type.EdmType))
1402 n = RewriteIsOfAsIsNull(op, n);
1405 // For IsOfOnly(abstract type), suppress DiscriminatorMaps since no explicit type id is available for
1407 if (op.IsOfOnly && op.IsOfType.EdmType.Abstract)
1409 m_suppressDiscriminatorMaps = true;
1415 // Determines whether a type test expression can be rewritten. Returns true of the
1416 // argument type is guaranteed to implement "testType" (if the argument is non-null).
1417 private bool CanRewriteTypeTest(EdmType testType, EdmType argumentType)
1419 // The rewrite only proceeds if the types are the same. If they are not,
1420 // it suggests either that the input result is polymorphic (in which case if OfType
1421 // should be preserved) or the types are incompatible (which is caught
1423 if (!testType.EdmEquals(argumentType))
1428 // If the IsOfType is non-polymorphic (no base or derived types) the rewrite
1430 if (null != testType.BaseType)
1436 int subTypeCount = 0;
1437 foreach (EdmType subType in MetadataHelper.GetTypeAndSubtypesOf(testType, m_command.MetadataWorkspace, true /*includeAbstractTypes*/))
1440 if (2 == subTypeCount) { break; }
1443 return 1 == subTypeCount; // no children types
1449 // '(case when not (R is null) then True else null end) = True'
1451 // Input requirements:
1453 // - IsOfOp and argument to same must be in the same hierarchy.
1454 // - IsOfOp and argument must have the same type
1455 // - IsOfOp.IsOfType may not have super- or sub- types (validate
1456 // using CanRewriteTypeTest)
1458 // Design requirements:
1460 // - Must return true if the record exists
1461 // - Must return null if it does not
1462 // - Must be in predicate form to avoid confusing SQL gen
1464 // The translation assumes R is of T when R is non null.
1465 private Node RewriteIsOfAsIsNull(IsOfOp op, Node n)
1467 // construct 'R is null' predicate
1468 ConditionalOp isNullOp = m_command.CreateConditionalOp(OpType.IsNull);
1469 Node isNullNode = m_command.CreateNode(isNullOp, n.Child0);
1471 // Process the IsNull node to make sure a null sentinel gets added if needed
1472 ProcessConditionalOp(isNullOp, isNullNode);
1474 // construct 'not (R is null)' predicate
1475 ConditionalOp notOp = m_command.CreateConditionalOp(OpType.Not);
1476 Node notNode = m_command.CreateNode(notOp, isNullNode);
1478 // construct 'True' result
1479 ConstantBaseOp trueOp = m_command.CreateConstantOp(op.Type, true);
1480 Node trueNode = m_command.CreateNode(trueOp);
1482 // construct 'null' default result
1483 NullOp nullOp = m_command.CreateNullOp(op.Type);
1484 Node nullNode = m_command.CreateNode(nullOp);
1486 // create case statement
1487 CaseOp caseOp = m_command.CreateCaseOp(op.Type);
1488 Node caseNode = m_command.CreateNode(caseOp, notNode, trueNode, nullNode);
1490 // create 'case = true' operator
1491 ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
1492 Node equalsNode = m_command.CreateNode(equalsOp, caseNode, trueNode);
1498 /// Rewrite a NavigateOp subtree.
1499 /// We call RewriteNavigateOp to return a subtree (and an optional outputVar).
1500 /// If the outputVar is null, then we simply return the subtree produced by those calls.
1501 /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
1505 /// select navigate(e) from T
1506 /// gets rewritten into
1507 /// select v from T OuterApply X
1508 /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
1511 /// <param name="op">the navigateOp</param>
1512 /// <param name="n">the navigateOp subtree</param>
1513 /// <returns>the rewritten tree</returns>
1514 public override Node Visit(NavigateOp op, Node n)
1516 VisitScalarOpDefault(op, n);
1518 Node ret = RewriteNavigateOp(n, op, out outputVar);
1519 ret = VisitNode(ret);
1521 // Move subquery to parent relop if necessary
1522 if (outputVar != null)
1524 ret = AddSubqueryToParentRelOp(outputVar, ret);
1530 /// Returns the current entity set scope, if any, for an entity type constructor.
1531 /// The scope defines the result of the construtor as a scoped entity type.
1533 private EntitySet GetCurrentEntityTypeScope()
1535 if (m_entityTypeScopes.Count == 0)
1539 return m_entityTypeScopes.Peek();
1543 /// Find the relationshipset that matches the current entityset + from/to roles
1545 /// <param name="entitySet"></param>
1546 /// <param name="relProperty"></param>
1547 /// <returns></returns>
1548 private RelationshipSet FindRelationshipSet(EntitySetBase entitySet, RelProperty relProperty)
1550 foreach (EntitySetBase es in entitySet.EntityContainer.BaseEntitySets)
1552 AssociationSet rs = es as AssociationSet;
1554 rs.ElementType.EdmEquals(relProperty.Relationship) &&
1555 rs.AssociationSetEnds[relProperty.FromEnd.Identity].EntitySet.EdmEquals(entitySet))
1564 /// Find the position of a property in a type.
1565 /// Positions start at zero, and a supertype's properties precede the current
1566 /// type's properties
1568 /// <param name="type">the type in question</param>
1569 /// <param name="member">the member to lookup</param>
1570 /// <returns>the position of the member in the type (0-based)</returns>
1571 private int FindPosition(EdmType type, EdmMember member)
1574 foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(type))
1576 if (m.EdmEquals(member))
1582 PlanCompiler.Assert(false, "Could not find property " + member + " in type " + type.Name);
1587 /// Build out an expression (NewRecord) that corresponds to the key properties
1588 /// of the passed-in entity constructor
1590 /// This function simply looks up the key properties of the entity type, and then
1591 /// identifies the arguments to the constructor corresponding to those
1592 /// properties, and then slaps on a record wrapper over those expressions.
1594 /// No copies/clones are performed. That's the responsibility of the caller
1597 /// <param name="op">the entity constructor op</param>
1598 /// <param name="n">the corresponding subtree</param>
1599 /// <returns>the key expression</returns>
1600 private Node BuildKeyExpressionForNewEntityOp(Op op, Node n)
1602 PlanCompiler.Assert(op.OpType == OpType.NewEntity || op.OpType == OpType.DiscriminatedNewEntity,
1603 "BuildKeyExpression: Unexpected OpType:" + op.OpType);
1604 int offset = (op.OpType == OpType.DiscriminatedNewEntity) ? 1 : 0;
1605 EntityTypeBase entityType = (EntityTypeBase)op.Type.EdmType;
1606 List<Node> keyFields = new List<Node>();
1607 List<KeyValuePair<string, TypeUsage>> keyFieldTypes = new List<KeyValuePair<string, TypeUsage>>();
1608 foreach (EdmMember k in entityType.KeyMembers)
1610 int pos = FindPosition(entityType, k) + offset;
1611 PlanCompiler.Assert(n.Children.Count > pos, "invalid position " + pos + "; total count = " + n.Children.Count);
1612 keyFields.Add(n.Children[pos]);
1613 keyFieldTypes.Add(new KeyValuePair<string, TypeUsage>(k.Name, k.TypeUsage));
1615 TypeUsage keyExprType = TypeHelpers.CreateRowTypeUsage(keyFieldTypes, true);
1616 NewRecordOp keyOp = m_command.CreateNewRecordOp(keyExprType);
1617 Node keyNode = m_command.CreateNode(keyOp, keyFields);
1622 /// Build out an expression corresponding to the rel-property.
1624 /// We create a subquery that looks like
1627 /// where GetRefKey(r.FromEnd) = myKey)
1629 /// RS is the single relationship set that corresponds to the given entityset/rel-property pair
1630 /// FromEnd - is the source end of the relationship
1631 /// myKey - is the key expression of the entity being constructed
1633 /// NOTE: We always clone "myKey" before use.
1635 /// We then convert it into a scalar subquery, and extract out the ToEnd property from
1636 /// the output var of the subquery. (Should we do this inside the subquery itself?)
1638 /// If no single relationship-set is found, we return a NULL instead.
1640 /// <param name="entitySet">entity set that logically holds instances of the entity we're building</param>
1641 /// <param name="relProperty">the rel-property we're trying to build up</param>
1642 /// <param name="keyExpr">the "key" of the entity instance</param>
1643 /// <returns>the rel-property expression</returns>
1644 private Node BuildRelPropertyExpression(EntitySetBase entitySet, RelProperty relProperty,
1648 // Make a copy of the current key expression
1650 keyExpr = OpCopier.Copy(m_command, keyExpr);
1653 // Find the relationship set corresponding to this entityset (and relProperty)
1654 // Return a null ref, if we can't find one
1656 RelationshipSet relSet = FindRelationshipSet(entitySet, relProperty);
1659 return m_command.CreateNode(m_command.CreateNullOp(relProperty.ToEnd.TypeUsage));
1662 ScanTableOp scanTableOp = m_command.CreateScanTableOp(Command.CreateTableDefinition(relSet));
1663 PlanCompiler.Assert(scanTableOp.Table.Columns.Count == 1,
1664 "Unexpected column count for table:" + scanTableOp.Table.TableMetadata.Extent + "=" + scanTableOp.Table.Columns.Count);
1665 Var scanTableVar = scanTableOp.Table.Columns[0];
1666 Node scanNode = m_command.CreateNode(scanTableOp);
1668 Node sourceEndNode = m_command.CreateNode(
1669 m_command.CreatePropertyOp(relProperty.FromEnd),
1670 m_command.CreateNode(m_command.CreateVarRefOp(scanTableVar)));
1671 Node predicateNode = m_command.BuildComparison(OpType.EQ,
1673 m_command.CreateNode(m_command.CreateGetRefKeyOp(keyExpr.Op.Type), sourceEndNode));
1674 Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
1675 scanNode, predicateNode);
1678 // Process the node, and then add this as a subquery to the parent relop
1680 Node ret = VisitNode(filterNode);
1681 ret = AddSubqueryToParentRelOp(scanTableVar, ret);
1684 // Now extract out the target end property
1686 ret = m_command.CreateNode(
1687 m_command.CreatePropertyOp(relProperty.ToEnd),
1694 /// Given an entity constructor (NewEntityOp, DiscriminatedNewEntityOp), build up
1695 /// the list of rel-property expressions.
1697 /// Walks through the list of relevant rel-properties, and builds up expressions
1698 /// (using BuildRelPropertyExpression) for each rel-property that does not have
1699 /// an expression already built (preBuiltExpressions)
1701 /// <param name="entitySet">entity set that holds instances of the entity we're building</param>
1702 /// <param name="relPropertyList">the list of relevant rel-properties for this entity type</param>
1703 /// <param name="prebuiltExpressions">the prebuilt rel-property expressions</param>
1704 /// <param name="keyExpr">the key of the entity instance</param>
1705 /// <returns>a list of rel-property expressions (lines up 1-1 with 'relPropertyList')</returns>
1706 private IEnumerable<Node> BuildAllRelPropertyExpressions(EntitySetBase entitySet,
1707 List<RelProperty> relPropertyList,
1708 Dictionary<RelProperty, Node> prebuiltExpressions,
1711 foreach (RelProperty r in relPropertyList)
1714 if (!prebuiltExpressions.TryGetValue(r, out relPropNode))
1716 relPropNode = BuildRelPropertyExpression(entitySet, r, keyExpr);
1718 yield return relPropNode;
1723 /// Handler for NewEntityOp.
1724 /// Assignes scope to the entity constructor if it hasn't been assigned before.
1726 /// <param name="op">the NewEntityOp</param>
1727 /// <param name="n">the node tree corresponding to the op</param>
1728 /// <returns>rewritten tree</returns>
1729 public override Node Visit(NewEntityOp op, Node n)
1731 // If this is not an entity type constructor, or it's been already scoped,
1732 // then just do the default processing.
1733 if (op.Scoped || op.Type.EdmType.BuiltInTypeKind != BuiltInTypeKind.EntityType)
1735 return base.Visit(op, n);
1738 EntityType entityType = (EntityType)op.Type.EdmType;
1739 EntitySet scope = GetCurrentEntityTypeScope();
1741 List<RelProperty> relProperties;
1742 List<Node> newChildren;
1746 m_freeFloatingEntityConstructorTypes.Add(entityType);
1748 // SQLBUDT #546546: Qmv/Umv tests Assert and throws in plan compiler in association tests.
1749 // If this Entity constructor is not within a view then there should not be any RelProps
1750 // specified on the NewEntityOp - the eSQL WITH RELATIONSHIP clauses that would cause such
1751 // RelProps to be added is only enabled when parsing in the user or generated view mode.
1752 PlanCompiler.Assert(op.RelationshipProperties == null ||
1753 op.RelationshipProperties.Count == 0,
1754 "Related Entities cannot be specified for Entity constructors that are not part of the Query Mapping View for an Entity Set.");
1756 // Default processing.
1757 VisitScalarOpDefault(op, n);
1759 relProperties = op.RelationshipProperties;
1760 newChildren = n.Children;
1765 // Note: We don't do the default processing first to avoid adding references to types and entity sets
1766 // that may only be used in pre-built rel property expressions that may not be needed.
1770 // Find the relationship properties for this entitytype (and entity set)
1772 relProperties = new List<RelProperty>(m_relPropertyHelper.GetRelProperties(entityType));
1774 // Remove pre-built rel property expressions that would not be needed to avoid
1775 // unnecessary adding references to types and entity sets during default processing
1776 int j = op.RelationshipProperties.Count - 1;
1777 List<RelProperty> copiedRelPropList = new List<RelProperty>(op.RelationshipProperties);
1778 for (int i = n.Children.Count - 1; i >= entityType.Properties.Count; i--, j--)
1780 if (!relProperties.Contains(op.RelationshipProperties[j]))
1782 n.Children.RemoveAt(i);
1783 copiedRelPropList.RemoveAt(j);
1787 // Default processing.
1788 VisitScalarOpDefault(op, n);
1791 // Ok, now, I have to build out some relationship properties that
1792 // haven't been specified
1794 Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
1797 // Find the list of rel properties that have already been specified
1799 Dictionary<RelProperty, Node> prebuiltRelPropertyExprs = new Dictionary<RelProperty, Node>();
1801 for (int i = entityType.Properties.Count; i < n.Children.Count; i++, j++)
1803 prebuiltRelPropertyExprs[copiedRelPropList[j]] = n.Children[i];
1807 // Next, rebuild the list of children - includes expressions for each rel property
1809 newChildren = new List<Node>();
1810 for (int i = 0; i < entityType.Properties.Count; i++)
1812 newChildren.Add(n.Children[i]);
1815 foreach (Node relPropNode in BuildAllRelPropertyExpressions(scope, relProperties, prebuiltRelPropertyExprs, keyExpr))
1817 newChildren.Add(relPropNode);
1822 // Finally, build out the newOp.
1824 Op newEntityOp = m_command.CreateScopedNewEntityOp(op.Type, relProperties, scope);
1825 Node newNode = m_command.CreateNode(newEntityOp, newChildren);
1830 /// Tracks discriminator metadata so that is can be used when constructing
1831 /// StructuredTypeInfo.
1833 public override Node Visit(DiscriminatedNewEntityOp op, Node n)
1835 HashSet<RelProperty> relPropertyHashSet = new HashSet<RelProperty>();
1836 List<RelProperty> relProperties = new List<RelProperty>();
1838 // add references to each type produced by this node
1839 // Also, get the set of rel-properties for each of the types
1841 foreach (var discriminatorTypePair in op.DiscriminatorMap.TypeMap)
1843 EntityTypeBase entityType = discriminatorTypePair.Value;
1844 AddTypeReference(TypeUsage.Create(entityType));
1845 foreach (RelProperty relProperty in m_relPropertyHelper.GetRelProperties(entityType))
1847 relPropertyHashSet.Add(relProperty);
1850 relProperties = new List<RelProperty>(relPropertyHashSet);
1851 VisitScalarOpDefault(op, n);
1854 // Now build out the set of missing rel-properties (if any)
1857 // first, build the key expression
1858 Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
1860 List<Node> newChildren = new List<Node>();
1861 int firstRelPropertyNodeOffset = n.Children.Count - op.RelationshipProperties.Count;
1862 for (int i = 0; i < firstRelPropertyNodeOffset; i++)
1864 newChildren.Add(n.Children[i]);
1867 // Find the list of rel properties that have already been specified
1869 Dictionary<RelProperty, Node> prebuiltRelPropertyExprs = new Dictionary<RelProperty, Node>();
1870 for (int i = firstRelPropertyNodeOffset, j = 0; i < n.Children.Count; i++, j++)
1872 prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
1876 // Fill in the missing pieces
1878 foreach (Node relPropNode in BuildAllRelPropertyExpressions(op.EntitySet, relProperties, prebuiltRelPropertyExprs, keyExpr))
1880 newChildren.Add(relPropNode);
1883 Op newEntityOp = m_command.CreateDiscriminatedNewEntityOp(op.Type, op.DiscriminatorMap, op.EntitySet, relProperties);
1884 Node newNode = m_command.CreateNode(newEntityOp, newChildren);
1890 /// Handles a newMultiset constructor. Converts this into
1891 /// select a from dual union all select b from dual union all ...
1892 /// Handles a NewMultiset constructor, i.e. {x, y, z}
1893 /// 1. Empty multiset constructors are simply converted into:
1895 /// select x from singlerowtable as x where false
1897 /// 2. Mulltset constructors with only one element or with multiple elements all of
1898 /// which are constants or nulls are converted into:
1900 /// select x from dual union all select y from dual union all select z
1902 /// 3. All others are converted into:
1904 /// select case when d = 0 then x when d = 1 then y else z end
1905 /// from ( select 0 as d from single_row_table
1907 /// select 1 as d from single_row_table
1909 /// select 2 as d from single_row_table )
1911 /// NOTE: The translation for 2 is valid for 3 too. We choose different translation
1912 /// in order to avoid correlation inside the union all,
1913 /// which would prevent us from removing apply operators
1915 /// Do this before processing the children, and then
1916 /// call Visit on the result to handle the elements
1918 /// <param name="op">the new instance op</param>
1919 /// <param name="n">the current subtree</param>
1920 /// <returns>the modified subtree</returns>
1921 public override Node Visit(NewMultisetOp op, Node n)
1923 Node resultNode = null;
1924 Var resultVar = null;
1926 CollectionType collectionType = TypeHelpers.GetEdmType<CollectionType>(op.Type);
1929 // Empty multiset constructors are simply converted into
1930 // Project(Filter(SingleRowTableOp(), false)
1934 Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
1935 Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
1937 m_command.CreateNode(m_command.CreateFalseOp()));
1938 Node fakeChild = m_command.CreateNode(m_command.CreateNullOp(collectionType.TypeUsage));
1940 Node projectNode = m_command.BuildProject(filterNode, fakeChild, out newVar);
1942 resultNode = projectNode;
1947 // Multiset constructors with only one elment or with multiple elments all of
1948 // which are constants or nulls are converted into:
1950 // UnionAll(Project(SingleRowTable, e1), Project(SingleRowTable, e2), ...)
1952 // The degenerate case when the collection has only one element does not require an
1953 // outer unionAll node
1955 else if (n.Children.Count == 1 || AreAllConstantsOrNulls(n.Children))
1957 List<Node> inputNodes = new List<Node>();
1958 List<Var> inputVars = new List<Var>();
1959 foreach (Node chi in n.Children)
1961 Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
1963 Node projectNode = m_command.BuildProject(singleRowTableNode, chi, out newVar);
1964 inputNodes.Add(projectNode);
1965 inputVars.Add(newVar);
1967 // Build the union-all ladder
1968 m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);
1974 // select case when d = 0 then x when d = 1 then y else z end
1975 // from ( select 0 as d from single_row_table
1977 // select 1 as d from single_row_table
1979 // select 2 as d from single_row_table )
1983 List<Node> inputNodes = new List<Node>();
1984 List<Var> inputVars = new List<Var>();
1985 //Create the union all lather first
1986 for (int i = 0; i < n.Children.Count; i++)
1988 Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
1989 // the discriminator for this branch
1990 Node discriminatorNode = m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.IntegerType, i));
1992 Node projectNode = m_command.BuildProject(singleRowTableNode, discriminatorNode, out newVar);
1994 inputNodes.Add(projectNode);
1995 inputVars.Add(newVar);
1997 // Build the union-all ladder now
1998 m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);
2000 //Now create the case statement for the projection
2001 List<Node> caseArgNodes = new List<Node>(n.Children.Count * 2 + 1);
2002 for (int i = 0; i < n.Children.Count; i++)
2004 //For all but the last we need a when
2005 if (i != (n.Children.Count - 1))
2007 ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
2008 Node whenNode = m_command.CreateNode(equalsOp,
2009 m_command.CreateNode(m_command.CreateVarRefOp(resultVar)),
2010 m_command.CreateNode(
2011 m_command.CreateConstantOp(m_command.IntegerType, i)));
2012 caseArgNodes.Add(whenNode);
2015 //Add the then/else node
2016 caseArgNodes.Add(n.Children[i]);
2019 //Create the project
2020 Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(collectionType.TypeUsage), caseArgNodes);
2021 resultNode = m_command.BuildProject(resultNode, caseNode, out resultVar);
2024 // So, I've finally built up a complex query corresponding to the constructor.
2025 // Now, cap this with a physicalprojectOp, and then with a CollectOp
2026 PhysicalProjectOp physicalProjectOp = m_command.CreatePhysicalProjectOp(resultVar);
2027 Node physicalProjectNode = m_command.CreateNode(physicalProjectOp, resultNode);
2029 CollectOp collectOp = m_command.CreateCollectOp(op.Type);
2030 Node collectNode = m_command.CreateNode(collectOp, physicalProjectNode);
2032 return VisitNode(collectNode);
2036 /// Returns true if each node in the list is either a constant or a null
2038 /// <param name="nodes"></param>
2039 /// <returns></returns>
2040 private bool AreAllConstantsOrNulls(List<Node> nodes)
2042 foreach (Node node in nodes)
2044 if (node.Op.OpType != OpType.Constant && node.Op.OpType != OpType.Null)
2053 /// Default processing for a CollectOp. But make sure that we
2054 /// go through the NestPullUp phase
2056 /// <param name="op"></param>
2057 /// <param name="n"></param>
2058 /// <returns></returns>
2059 public override Node Visit(CollectOp op, Node n)
2061 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
2062 return VisitScalarOpDefault(op, n);
2069 private void HandleTableOpMetadata(ScanTableBaseOp op)
2071 // add to the list of referenced entitysets
2072 EntitySet entitySet = op.Table.TableMetadata.Extent as EntitySet;
2073 if (entitySet != null)
2075 // If entitySet is an association set, the appropriate entity set references will be registered inside Visit(RefOp, Node).
2076 AddEntitySetReference(entitySet);
2079 TypeUsage elementType = TypeUsage.Create(op.Table.TableMetadata.Extent.ElementType);
2080 // add to the list of structured types
2081 AddTypeReference(elementType);
2085 /// Visits a "table" expression - performs view expansion on the table (if appropriate),
2086 /// and then some additional book-keeping.
2088 /// The "ofType" and "includeSubtypes" parameters are optional hints for view expansion, allowing
2089 /// for more customized (and hopefully, more optimal) views. The wasOfTypeSatisfied out parameter
2090 /// tells whether the ofType filter was already handled by the view expansion, or if the caller still
2091 /// needs to deal with it.
2093 /// If the "table" is a C-space entityset, then we produce a ScanViewOp
2094 /// tree with the defining query as the only child of the ScanViewOp
2096 /// If the table is an S-space entityset, then we still produce a ScanViewOp, but this
2097 /// time, we produce a simple "select * from BaseTable" as the defining
2100 /// <param name="scanTableNode">the scanTable node tree</param>
2101 /// <param name="scanTableOp">the scanTableOp</param>
2102 /// <param name="typeFilter">
2103 /// An optional IsOfOp representing a type filter to apply to the scan table; will be set to <c>null</c>
2104 /// if the scan target is expanded to a view that renders the type filter superfluous.
2106 /// <returns></returns>
2107 private Node ProcessScanTable(Node scanTableNode, ScanTableOp scanTableOp, ref IsOfOp typeFilter)
2109 HandleTableOpMetadata(scanTableOp);
2111 PlanCompiler.Assert(scanTableOp.Table.TableMetadata.Extent != null, "ScanTableOp must reference a table with an extent");
2116 // Get simple things out of the way. If we're dealing with an S-space entityset,
2117 // simply return the node
2119 if (scanTableOp.Table.TableMetadata.Extent.EntityContainer.DataSpace == DataSpace.SSpace)
2121 return scanTableNode;
2125 // "Expand" the C-Space view
2126 ret = ExpandView(scanTableNode, scanTableOp, ref typeFilter);
2129 // Rerun the processor over the resulting subtree
2130 ret = VisitNode(ret);
2136 /// Processes a ScanTableOp - simply delegates to ProcessScanTableOp
2138 /// <param name="op">the view op</param>
2139 /// <param name="n">current node tree</param>
2140 /// <returns>the transformed view-op</returns>
2141 public override Node Visit(ScanTableOp op, Node n)
2143 IsOfOp nullFilter = null;
2144 return ProcessScanTable(n, op, ref nullFilter);
2148 /// Visitor for a ScanViewOp
2150 /// <param name="op"></param>
2151 /// <param name="n"></param>
2152 /// <returns></returns>
2153 public override Node Visit(ScanViewOp op, Node n)
2155 bool entityTypeScopePushed = false;
2156 if (op.Table.TableMetadata.Extent.BuiltInTypeKind == BuiltInTypeKind.EntitySet)
2158 m_entityTypeScopes.Push((EntitySet)op.Table.TableMetadata.Extent);
2159 entityTypeScopePushed = true;
2162 HandleTableOpMetadata(op);
2163 // Ideally, I should call this as the first statement, but that was causing too
2164 // many test diffs - because of the order in which the entitytypes/sets
2165 // were being added. There is no semantic difference in calling this here
2166 VisitRelOpDefault(op, n);
2168 if (entityTypeScopePushed)
2170 var scope = m_entityTypeScopes.Pop();
2171 PlanCompiler.Assert(scope == op.Table.TableMetadata.Extent, "m_entityTypeScopes stack is broken");
2178 /// Processing for all JoinOps
2180 /// <param name="op">JoinOp</param>
2181 /// <param name="n">Current subtree</param>
2182 /// <returns></returns>
2183 protected override Node VisitJoinOp(JoinBaseOp op, Node n)
2185 // Only LeftOuterJoin and InnerJoin are handled by JoinElimination
2186 if (op.OpType == OpType.InnerJoin || op.OpType == OpType.LeftOuterJoin)
2188 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination);
2191 // If a subquery was added with an exists node, we have to go througth Normalization
2192 if (base.ProcessJoinOp(op, n))
2194 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization);
2200 /// Perform default relop processing; Also "require" the join-elimination phase
2202 /// <param name="op"></param>
2203 /// <param name="n"></param>
2204 /// <returns></returns>
2205 protected override Node VisitApplyOp(ApplyBaseOp op, Node n)
2207 m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination);
2208 return VisitRelOpDefault(op, n);
2212 /// Can I eliminate this sort? I can, if the current path is *not* one of the
2215 /// PhysicalProject(Sort)
2217 /// We don't yet handle the TopN variant
2219 /// <returns></returns>
2220 private bool IsSortUnnecessary()
2222 Node ancestor = m_ancestors.Peek();
2223 PlanCompiler.Assert(ancestor != null, "unexpected SortOp as root node?");
2225 if (ancestor.Op.OpType == OpType.PhysicalProject)
2234 /// Visit a SortOp. Eliminate it if the path to this node is not one of
2235 /// PhysicalProject(Sort) or
2238 /// Otherwise, simply visit the child RelOp
2241 /// <param name="op">Current sortOp</param>
2242 /// <param name="n">current subtree</param>
2243 /// <returns>possibly transformed subtree</returns>
2244 public override Node Visit(SortOp op, Node n)
2246 // can I eliminate this sort
2247 if (this.IsSortUnnecessary())
2249 return VisitNode(n.Child0);
2252 // perform default processing
2253 return VisitRelOpDefault(op, n);
2257 /// Checks to see if this filterOp represents an IS OF (or IS OF ONLY) filter over a ScanTableOp
2259 /// <param name="n">the filterOp node</param>
2260 /// <param name="ofType">(OUT) the Type to restrict to</param>
2261 /// <param name="isOfOnly">(OUT) was an ONLY clause specified</param>
2262 /// <returns></returns>
2263 private bool IsOfTypeOverScanTable(Node n, out IsOfOp typeFilter)
2268 // Is the predicate an IsOf predicate
2270 IsOfOp isOfOp = n.Child1.Op as IsOfOp;
2276 // Is the Input RelOp a ScanTableOp
2278 ScanTableOp scanTableOp = n.Child0.Op as ScanTableOp;
2279 if (scanTableOp == null || scanTableOp.Table.Columns.Count != 1)
2284 // Is the argument to the IsOfOp the single column of the table?
2286 VarRefOp varRefOp = n.Child1.Child0.Op as VarRefOp;
2287 if (varRefOp == null || varRefOp.Var != scanTableOp.Table.Columns[0])
2293 // All conditions match. Return the info from the IsOf predicate
2295 typeFilter = isOfOp;
2300 /// Handler for a FilterOp. Usually delegates to VisitRelOpDefault.
2302 /// There's one special case - where we have an ISOF predicate over a ScanTable. In that case, we attempt
2303 /// to get a more "optimal" view; and return that optimal view
2306 /// <param name="op">the filterOp</param>
2307 /// <param name="n">the node tree</param>
2308 /// <returns></returns>
2309 public override Node Visit(FilterOp op, Node n)
2312 if (IsOfTypeOverScanTable(n, out typeFilter))
2314 Node ret = ProcessScanTable(n.Child0, (ScanTableOp)n.Child0.Op, ref typeFilter);
2315 if (typeFilter != null)
2317 n.Child1 = VisitNode(n.Child1);
2325 return VisitRelOpDefault(op, n);
2330 /// Visit a ProjectOp; if the input is a SortOp, we pullup the sort over
2331 /// the ProjectOp to ensure that we don't have nested sorts;
2332 /// Note: This transformation cannot be moved in the normalizer,
2333 /// because it needs to happen before any subquery augmentation happens.
2335 /// <param name="op"></param>
2336 /// <param name="n"></param>
2337 /// <returns></returns>
2338 public override Node Visit(ProjectOp op, Node n)
2340 PlanCompiler.Assert(n.HasChild0, "projectOp without input?");
2342 if (OpType.Sort == n.Child0.Op.OpType || OpType.ConstrainedSort == n.Child0.Op.OpType)
2344 SortBaseOp sort = (SortBaseOp)n.Child0.Op;
2346 // Don't pullup the sort if it doesn't have any keys.
2347 // An example of such sort is "ctx.Products.Take(1)".
2348 if (sort.Keys.Count > 0)
2350 IList<Node> sortChildren = new List<Node>();
2351 sortChildren.Add(n);
2353 //A ConstrainedSort has two other children besides the input and it needs to keep them.
2354 for (int i = 1; i < n.Child0.Children.Count; i++)
2356 sortChildren.Add(n.Child0.Children[i]);
2359 // Replace the ProjectOp input (currently the Sort node) with the input to the Sort.
2360 n.Child0 = n.Child0.Child0;
2362 // Vars produced by the Sort input and used as SortKeys should be considered outputs
2363 // of the ProjectOp that now operates over what was the Sort input.
2364 foreach (SortKey key in sort.Keys)
2366 op.Outputs.Set(key.Var);
2369 // Finally, pull the Sort over the Project by creating a new Sort node with the original
2370 // Sort as its Op and the Project node as its only child. This is sufficient because
2371 // the ITreeGenerator ensures that the SortOp does not have any local VarDefs.
2372 return VisitNode(m_command.CreateNode(sort, sortChildren));
2376 // perform default processing
2377 Node newNode = VisitRelOpDefault(op, n);
2382 /// Mark AggregatePushdown as needed
2384 /// <param name="op">the groupByInto op</param>
2385 /// <param name="n">the node tree</param>
2386 /// <returns></returns>
2387 public override Node Visit(GroupByIntoOp op, Node n)
2389 this.m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.AggregatePushdown);
2390 return base.Visit(op, n);
2401 /// Finds the record (Row) types that we're projecting out of the query, and
2402 /// ensures that we mark them as needing a nullable sentinel, so when we
2403 /// flatten them later we'll have one added.
2405 internal class StructuredTypeNullabilityAnalyzer : ColumnMapVisitor<HashSet<string>>
2407 static internal StructuredTypeNullabilityAnalyzer Instance = new StructuredTypeNullabilityAnalyzer();
2412 /// <param name="columnMap"></param>
2413 /// <param name="typesNeedingNullSentinel"></param>
2414 /// <returns></returns>
2415 internal override void Visit(VarRefColumnMap columnMap, HashSet<string> typesNeedingNullSentinel)
2417 AddTypeNeedingNullSentinel(typesNeedingNullSentinel, columnMap.Type);
2418 base.Visit(columnMap, typesNeedingNullSentinel);
2422 /// Recursively add any Row types to the list of types needing a sentinel.
2424 /// <param name="typesNeedingNullableSentinel"></param>
2425 /// <param name="typeUsage"></param>
2426 private static void AddTypeNeedingNullSentinel(HashSet<string> typesNeedingNullSentinel, TypeUsage typeUsage)
2428 if (TypeSemantics.IsCollectionType(typeUsage))
2430 AddTypeNeedingNullSentinel(typesNeedingNullSentinel, TypeHelpers.GetElementTypeUsage(typeUsage));
2434 if (TypeSemantics.IsRowType(typeUsage) || TypeSemantics.IsComplexType(typeUsage))
2436 MarkAsNeedingNullSentinel(typesNeedingNullSentinel, typeUsage);
2438 foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(typeUsage))
2440 AddTypeNeedingNullSentinel(typesNeedingNullSentinel, m.TypeUsage);
2446 /// Marks the given typeUsage as needing a null sentinel.
2447 /// Call this method instead of calling Add over the HashSet directly, to ensure consistency.
2449 /// <param name="typesNeedingNullSentinel"></param>
2450 /// <param name="typeUsage"></param>
2451 internal static void MarkAsNeedingNullSentinel(HashSet<string> typesNeedingNullSentinel, TypeUsage typeUsage)
2453 typesNeedingNullSentinel.Add(typeUsage.EdmType.Identity);