Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / PreProcessor.cs / 1305376 / PreProcessor.cs
//---------------------------------------------------------------------- //// Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System; using System.Collections.Generic; using System.Data.Common; using System.Data.Common.Utils; using System.Data.Metadata.Edm; using System.Data.Query.InternalTrees; //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class... // // The PreProcessor module is responsible for performing any required preprocessing // on the tree and gathering information before subsequent phases may be performed. // The main responsibilites of the preprocessor are: // // (a) gathering information about all structured types and entitysets referenced in the // query // (b) expanding views, navigate operators, and rewritting other type related operators // (c) gathering information about which subsequent phases may be requried // (d) pulling sort over project, and removing unnecessary sorts // (e) eliminates certain operations by translating them into equivalent subtrees // (ElementOp, NewMultisetOp) // namespace System.Data.Query.PlanCompiler { internal class DiscriminatorMapInfo { internal EntityTypeBase RootEntityType; internal bool IncludesSubTypes; internal ExplicitDiscriminatorMap DiscriminatorMap; internal DiscriminatorMapInfo(EntityTypeBase rootEntityType, bool includesSubTypes, ExplicitDiscriminatorMap discriminatorMap) { RootEntityType = rootEntityType; IncludesSubTypes = includesSubTypes; DiscriminatorMap = discriminatorMap; } ////// Merge the discriminatorMap info we just found with what we've already found. /// /// In practice, if either the current or the new map is from an OfTypeOnly view, we /// have to avoid the optimizations. /// /// If we have a new map that is a superset of the current map, then we can just swap /// the new map for the current one. /// /// If the current map is tha super set of the new one ther's nothing to do. /// /// (Of course, if neither has changed, then we really don't need to look) /// internal void Merge(EntityTypeBase neededRootEntityType, bool includesSubtypes, ExplicitDiscriminatorMap discriminatorMap) { // If what we've found doesn't exactly match what we are looking for we have more work to do if (RootEntityType != neededRootEntityType || IncludesSubTypes != includesSubtypes) { if (!IncludesSubTypes || !includesSubtypes) { // If either the original or the new map is from an of-type-only view we can't // merge, we just have to not optimize this case. DiscriminatorMap = null; } if (TypeSemantics.IsSubTypeOf(RootEntityType, neededRootEntityType)) { // we're asking for a super type of existing type, and what we had is a proper // subset of it -we can replace the existing item. RootEntityType = neededRootEntityType; DiscriminatorMap = discriminatorMap; } if (!TypeSemantics.IsSubTypeOf(neededRootEntityType, RootEntityType)) { // If either the original or the new map is from an of-type-only view we can't // merge, we just have to not optimize this case. DiscriminatorMap = null; } } } } ////// The PreProcessor module is responsible for performing any required preprocessing /// on the tree and gathering information before subsequent phases may be performed. /// internal class PreProcessor : SubqueryTrackingVisitor { #region private state // current nested view depth (0 for top-level query) private int m_viewNestingLevel = 0; // track referenced types, entitysets, entitycontainers, free floating entity constructor types // and types needing a null sentinel private HashSetm_referencedEntityContainers = new HashSet (); private HashSet m_referencedEntitySets = new HashSet (); private HashSet m_referencedTypes = new HashSet (); private HashSet m_freeFloatingEntityConstructorTypes = new HashSet (); private HashSet m_typesNeedingNullSentinel = new HashSet (); // helper for rel properties private RelPropertyHelper m_relPropertyHelper; // track discriminator metadata private bool m_suppressDiscriminatorMaps; private readonly Dictionary m_discriminatorMaps = new Dictionary (); #endregion #region constructors private PreProcessor(PlanCompiler planCompilerState) : base(planCompilerState) { m_relPropertyHelper = new RelPropertyHelper(m_command.MetadataWorkspace, m_command.ReferencedRelProperties); } #endregion #region public methods /// /// The driver routine. /// /// plan compiler state /// type information about all types/sets referenced in the query internal static void Process(PlanCompiler planCompilerState, out StructuredTypeInfo typeInfo) { PreProcessor preProcessor = new PreProcessor(planCompilerState); preProcessor.Process(); StructuredTypeInfo.Process(planCompilerState.Command, preProcessor.m_referencedTypes, preProcessor.m_referencedEntitySets, preProcessor.m_freeFloatingEntityConstructorTypes, preProcessor.m_suppressDiscriminatorMaps ? null : preProcessor.m_discriminatorMaps, preProcessor.m_relPropertyHelper, preProcessor.m_typesNeedingNullSentinel, out typeInfo); } #endregion #region private methods #region driver internal void Process() { m_command.Root = VisitNode(m_command.Root); // // Add any Vars that are of structured type - if the Vars aren't // referenced via a VarRefOp, we end up losing them... // foreach (Var v in m_command.Vars) { AddTypeReference(v.Type); } // // If we have any "structured" types, then we need to run through NTE // if (m_referencedTypes.Count > 0) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NTE); // // Find any structured types that are projected at the top level, and // ensure that we can handle their nullability. // PhysicalProjectOp ppOp = (PhysicalProjectOp)m_command.Root.Op; // this better be the case or we have other problems. ppOp.ColumnMap.Accept(StructuredTypeNullabilityAnalyzer.Instance, m_typesNeedingNullSentinel); } } #endregion #region private state maintenance - type and set information ////// Mark this EntitySet as referenced in the query /// /// private void AddEntitySetReference(EntitySet entitySet) { m_referencedEntitySets.Add(entitySet); if (!m_referencedEntityContainers.Contains(entitySet.EntityContainer)) { m_referencedEntityContainers.Add(entitySet.EntityContainer); } } ////// Mark this type as being referenced in the query, if it is a structured /// type or a collection of structured type /// /// type to reference private void AddTypeReference(TypeUsage type) { if (TypeUtils.IsStructuredType(type) || TypeUtils.IsCollectionType(type)) { m_referencedTypes.Add(type); } } ////// Get the list of relationshipsets that can hold instances of the given relationshiptype /// /// We identify the list of relationshipsets in the current list of entitycontainers that are /// of the given type. Since we don't yet support relationshiptype subtyping, this is a little /// easier than the entity version /// /// the relationship type to look for ///the list of relevant relationshipsets private ListGetRelationshipSets(RelationshipType relType) { List relSets = new List (); foreach (EntityContainer entityContainer in m_referencedEntityContainers) { foreach (EntitySetBase set in entityContainer.BaseEntitySets) { RelationshipSet relSet = set as RelationshipSet; if (relSet != null && relSet.ElementType.Equals(relType)) { relSets.Add(relSet); } } } return relSets; } /// /// Find all entitysets (that are reachable in the current query) that can hold instances that /// are *at least* of type "entityType". /// An entityset ES of type T1 can hold instances that are at least of type T2, if one of the following /// is true /// - T1 is a subtype of T2 /// - T2 is a subtype of T1 /// - T1 is equal to T2 /// /// the desired entity type ///list of all entitysets of the desired shape private ListGetEntitySets(TypeUsage entityType) { List sets = new List (); foreach (EntityContainer container in m_referencedEntityContainers) { foreach (EntitySetBase baseSet in container.BaseEntitySets) { EntitySet set = baseSet as EntitySet; if (set != null && (set.ElementType.Equals(entityType.EdmType) || TypeSemantics.IsSubTypeOf(entityType.EdmType, set.ElementType) || TypeSemantics.IsSubTypeOf(set.ElementType, entityType.EdmType))) { sets.Add(set); } } } return sets; } #endregion #region View Expansion /// /// Convert a CQT command into an IQT subtree. /// We expect the CQT command to be a query command tree. This is a 3-step /// process /// * We first run through the standard CQT-IQT convertor. /// * We then strip off the root of the IQT (the PhysicalProjectOp) /// * Finally, we copy the IQT into our current IQT /// /// When we have metadata caching of IQTs (for views), instead of CQTs, /// we can get rid of steps 1 and 2. /// /// the view ///an IQT subtree in the current command private Node ConvertToInternalTree(System.Data.Mapping.ViewGeneration.GeneratedView generatedView) { Node ret; Node sourceIqt = generatedView.GetInternalTree(m_command.MetadataWorkspace); ret = OpCopier.Copy(m_command, sourceIqt); return ret; } ////// Gets the "expanded" query mapping view for the specified C-Space entity set /// /// The current node /// The scanTableOp that references the entity set /// /// An optional type filter to apply to the generated view. /// Set tonull on return if the generated view renders the type filter superfluous. /// ///A node that is the root of the new expanded view private Node ExpandView(Node node, ScanTableOp scanTableOp, ref IsOfOp typeFilter) { EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent; PlanCompiler.Assert(entitySet != null, "The target of a ScanTableOp must reference an EntitySet to be used with ExpandView"); PlanCompiler.Assert(entitySet.EntityContainer.DataSpace == DataSpace.CSpace, "Store entity sets cannot have Query Mapping Views and should not be used with ExpandView"); if (typeFilter != null && !typeFilter.IsOfOnly && TypeSemantics.IsSubTypeOf(entitySet.ElementType, typeFilter.IsOfType.EdmType)) { // // If a type filter is being applied to the ScanTableOp, but that filter is asking // for all elements that are the same type or a supertype of the element type of the // target entity set, then the type filter is a no-op and can safely be discarded - // IF AND ONLY IF the type filter is 'OfType' - which includes subtypes - and NOT // 'IsOfOnly' - which requires an exact type match, and so does not include subtypes. // typeFilter = null; } // // Call the GetGeneratedView method to retrieve the query mapping view for the extent referenced // by the ScanTableOp. The actual method used to do this differs depending on whether the default // Query Mapping View is sufficient or a targeted view that only filters by element type is required. // System.Data.Mapping.ViewGeneration.GeneratedView definingQuery = null; EntityTypeBase requiredType = scanTableOp.Table.TableMetadata.Extent.ElementType; bool includeSubtypes = true; if (typeFilter != null) { // // A type filter is being applied to the ScanTableOp; it may be possible to produce // an optimized expansion of the view based on type-specific views generated for the // C-Space entity set. // The type for which the view should be tuned is the 'OfType' specified on the type filter. // If the type filter is an 'IsOfOnly' filter then the view should NOT include subtypes of the required type. // requiredType = (EntityTypeBase)typeFilter.IsOfType.EdmType; includeSubtypes = !typeFilter.IsOfOnly; if (m_command.MetadataWorkspace.TryGetGeneratedViewOfType(entitySet, requiredType, includeSubtypes, out definingQuery)) { // // At this point a type-specific view was found that satisifies the type filter's // constraints in terms of required type and whether subtypes should be included; // the type filter itself is now unnecessary and should be set to null indicating // that it can be safely removed (see ProcessScanTableOp and Visit(FilterOp) for this). // typeFilter = null; } } // // If a generated view has not been obtained at this point then either: // - A type filter was specified but no type-specific view exists that satisfies its constraints. // OR // - No type filter was specified. // In either case the default query mapping view for the referenced entity set should now be retrieved. // if (null == definingQuery) { definingQuery = m_command.MetadataWorkspace.GetGeneratedView(entitySet); } // // If even the default query mapping view was not found then we cannot continue. // This implies that the set was not mapped, which should not be allowed, therefore // a retail assert is used here instead of a regular exception. // PlanCompiler.Assert(definingQuery != null, Entity.Strings.ADP_NoQueryMappingView(entitySet.EntityContainer.Name, entitySet.Name)); // // At this point we're guaranteed to have found a defining query for the view. // We're now going to convert this into an IQT, and then copy it into our own IQT. // Node ret = ConvertToInternalTree(definingQuery); // // Make sure we're tracking what we've asked any discriminator maps to contain. // DetermineDiscriminatorMapUsage(ret, entitySet, requiredType, includeSubtypes); // // Build up a ScanViewOp to "cap" the defining query below // ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table); ret = m_command.CreateNode(scanViewOp, ret); return ret; } ////// If the discrminator map we're already tracking for this type (in this entityset) /// isn't already rooted at our required type, then we have to suppress the use of /// the descriminator maps when we constrct the structuredtypes; see SQLBUDT #615744 /// private void DetermineDiscriminatorMapUsage(Node viewNode, EntitySetBase entitySet, EntityTypeBase rootEntityType, bool includeSubtypes) { ExplicitDiscriminatorMap discriminatorMap = null; // we expect the view to be capped with a project; we're just being careful here. if (viewNode.Op.OpType == OpType.Project) { DiscriminatedNewEntityOp discriminatedNewEntityOp = viewNode.Child1.Child0.Child0.Op as DiscriminatedNewEntityOp; if (null != discriminatedNewEntityOp) { discriminatorMap = discriminatedNewEntityOp.DiscriminatorMap; } } DiscriminatorMapInfo discriminatorMapInfo; if (!m_discriminatorMaps.TryGetValue(entitySet, out discriminatorMapInfo)) { if (null == rootEntityType) { rootEntityType = entitySet.ElementType; includeSubtypes = true; } discriminatorMapInfo = new DiscriminatorMapInfo(rootEntityType, includeSubtypes, discriminatorMap); m_discriminatorMaps.Add(entitySet, discriminatorMapInfo); } else { discriminatorMapInfo.Merge(rootEntityType, includeSubtypes, discriminatorMap); } } #endregion #region NavigateOp rewrites ////// Rewrites a NavigateOp tree in the following fashion /// SELECT VALUE r.ToEnd /// FROM (SELECT VALUE r1 FROM RS1 as r1 /// UNION ALL /// SELECT VALUE r2 FROM RS2 as r2 /// ... /// SELECT VALUE rN FROM RSN as rN) as r /// WHERE r.FromEnd = sourceRef /// /// RS1, RS2 etc. are the set of all relationshipsets that can hold instances of the specified /// relationship type. "sourceRef" is the single (ref-type) argument to the NavigateOp that /// represents the from-end of the navigation traversal /// If the toEnd is multi-valued, then we stick a Collect(PhysicalProject( over the subquery above /// /// A couple of special cases. /// If no relationship sets can be found, we return a NULL (if the /// toEnd is single-valued), or an empty multiset (if the toEnd is multi-valued) /// /// If the toEnd is single-valued, *AND* the input Op is a GetEntityRefOp, then /// we convert the NavigateOp into a RelPropertyOp over the entity. /// /// the navigateOp tree /// the navigateOp /// the output var produced by the subquery (ONLY if the to-End is single-valued) ///the resulting node private Node RewriteNavigateOp(Node navigateOpNode, NavigateOp navigateOp, out Var outputVar) { outputVar = null; // // Currently, navigation of composition relationships is not supported. // if (!Helper.IsAssociationType(navigateOp.Relationship)) { throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_RelNav_NoCompositions); } // // If the input to the navigateOp is a GetEntityRefOp, and the navigation // is to the 1-end of the relationship, convert this into a RelPropertyOp instead - operating on the // input child to the GetEntityRefOp // if (navigateOpNode.Child0.Op.OpType == OpType.GetEntityRef && (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne || navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One)) { PlanCompiler.Assert(m_command.IsRelPropertyReferenced(navigateOp.RelProperty), "Unreferenced rel property? " + navigateOp.RelProperty); Op relPropertyOp = m_command.CreateRelPropertyOp(navigateOp.RelProperty); Node relPropertyNode = m_command.CreateNode(relPropertyOp, navigateOpNode.Child0.Child0); return relPropertyNode; } ListrelationshipSets = GetRelationshipSets(navigateOp.Relationship); // // Special case: when no relationshipsets can be found. Return NULL or an empty multiset, // depending on the multiplicity of the toEnd // if (relationshipSets.Count == 0) { // // If we're navigating to the 1-end of the relationship, then simply return a null constant // if (navigateOp.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many) { return m_command.CreateNode(m_command.CreateNullOp(navigateOp.Type)); } else // return an empty set { return m_command.CreateNode(m_command.CreateNewMultisetOp(navigateOp.Type)); } } // // Build up a UNION-ALL ladder over all the relationshipsets // List scanTableNodes = new List (); List scanTableVars = new List(); foreach (RelationshipSet relSet in relationshipSets) { TableMD tableMD = Command.CreateTableDefinition(relSet); ScanTableOp tableOp = m_command.CreateScanTableOp(tableMD); Node branchNode = m_command.CreateNode(tableOp); Var branchVar = tableOp.Table.Columns[0]; scanTableVars.Add(branchVar); scanTableNodes.Add(branchNode); } Node unionAllNode = null; Var unionAllVar; m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); // // Now build up the predicate // Node targetEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.ToEnd), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node sourceEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.FromEnd), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node predicateNode = m_command.BuildComparison(OpType.EQ, navigateOpNode.Child0, sourceEnd); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicateNode); Var projectVar; Node projectNode = m_command.BuildProject(filterNode, targetEnd, out projectVar); // // Finally, some magic about single-valued vs collection-valued ends // Node ret; if (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many) { ret = m_command.BuildCollect(projectNode, projectVar); } else { ret = projectNode; outputVar = projectVar; } return ret; } #endregion #region DerefOp Rewrites /// /// Build up a node tree that represents the set of instances from the given table that are at least /// of the specified type ("ofType"). If "ofType" is NULL, then all rows are returned /// /// Return the outputVar from the nodetree /// /// the entityset or relationshipset to scan over /// the element types we're interested in /// the output var produced by this node tree ///the node tree private Node BuildOfTypeTable(EntitySetBase entitySet, TypeUsage ofType, out Var resultVar) { TableMD tableMetadata = Command.CreateTableDefinition(entitySet); ScanTableOp tableOp = m_command.CreateScanTableOp(tableMetadata); Node tableNode = m_command.CreateNode(tableOp); Var tableVar = tableOp.Table.Columns[0]; Node resultNode; // // Build a logical "oftype" expression - simply a filter predicate // if ((ofType != null) && !entitySet.ElementType.EdmEquals(ofType.EdmType)) { m_command.BuildOfTypeTree(tableNode, tableVar, ofType, true, out resultNode, out resultVar); } else { resultNode = tableNode; resultVar = tableVar; } return resultNode; } ////// Produces a relop tree that "logically" produces the target of the derefop. In essence, this gets rewritten /// into /// SELECT VALUE e /// FROM (SELECT VALUE e0 FROM OFTYPE(ES0, T) as e0 /// UNION ALL /// SELECT VALUE e1 FROM OFTYPE(ES1, T) as e1 /// ... /// SELECT VALUE eN from OFTYPE(ESN, T) as eN)) as e /// WHERE REF(e) = myRef /// /// "T" is the target type of the Deref, and myRef is the (single) argument to the DerefOp /// /// ES0, ES1 etc. are all the EntitySets that could hold instances that are at least of type "T". We identify this list of sets /// by looking at all entitycontainers referenced in the query, and looking at all entitysets in those /// containers that are of the right type /// An EntitySet ES (of entity type X) can hold instances of T, if one of the following is true /// - T is a subtype of X /// - X is equal to T /// Our situation is a little trickier, since we also need to look for cases where X is a subtype of T. /// /// the derefOp subtree /// the derefOp /// output var produced ///the subquery described above private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar) { TypeUsage entityType = derefOp.Type; ListtargetEntitySets = GetEntitySets(entityType); if (targetEntitySets.Count == 0) { // We didn't find any entityset that could match this. Simply return a null-value outputVar = null; return m_command.CreateNode(m_command.CreateNullOp(entityType)); } List scanTableNodes = new List (); List scanTableVars = new List(); foreach (EntitySet entitySet in targetEntitySets) { Var tableVar; Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar); scanTableNodes.Add(tableNode); scanTableVars.Add(tableVar); } Node unionAllNode; Var unionAllVar; m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); // // Finally build up the key comparison predicate // Node entityRefNode = m_command.CreateNode( m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode); Node filterNode = m_command.CreateNode( m_command.CreateFilterOp(), unionAllNode, keyComparisonPred); outputVar = unionAllVar; return filterNode; } #endregion #region NavigationProperty Rewrites /// /// Find the entityset that corresponds to the specified end of the relationship. /// /// We must find one - else we assert. /// /// the relationshipset /// the destination end of the relationship traversal ///the entityset corresponding to the target end private static EntitySetBase FindTargetEntitySet(RelationshipSet relationshipSet, RelationshipEndMember targetEnd) { EntitySetBase entitySet = null; AssociationSet associationSet = (AssociationSet)relationshipSet; // find the corresponding entityset entitySet = null; foreach (AssociationSetEnd e in associationSet.AssociationSetEnds) { if (e.CorrespondingAssociationEndMember.EdmEquals(targetEnd)) { entitySet = e.EntitySet; break; } } PlanCompiler.Assert(entitySet != null, "Could not find entityset for relationshipset " + relationshipSet + ";association end " + targetEnd); return entitySet; } ////// Builds up a join between the relationshipset and the entityset corresponding to its toEnd. In essence, /// we produce /// SELECT r, e /// FROM RS as r, OFTYPE(ES, T) as e /// WHERE r.ToEnd = Ref(e) /// /// "T" is the entity type of the toEnd of the relationship. /// /// the relationshipset /// the toEnd of the relationship /// the var representing the relationship instance ("r") in the output subquery /// the var representing the entity instance ("e") in the output subquery ///the join subquery described above private Node BuildJoinForNavProperty(RelationshipSet relSet, RelationshipEndMember end, out Var rsVar, out Var esVar) { EntitySetBase entitySet = FindTargetEntitySet(relSet, end); // // Build out the ScanTable ops for the relationshipset and the entityset. Add the // Node asTableNode = BuildOfTypeTable(relSet, null, out rsVar); Node esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar); // // Build up a join between the entityset and the associationset; join on the to-end // Node joinPredicate = m_command.BuildComparison(OpType.EQ, m_command.CreateNode(m_command.CreateGetEntityRefOp(end.TypeUsage), m_command.CreateNode(m_command.CreateVarRefOp(esVar))), m_command.CreateNode(m_command.CreatePropertyOp(end), m_command.CreateNode(m_command.CreateVarRefOp(rsVar))) ); Node joinNode = m_command.CreateNode(m_command.CreateInnerJoinOp(), asTableNode, esTableNode, joinPredicate); return joinNode; } ////// Rewrite a NavPropertyOp when the target end of the nav property has multiplicity /// of one (or zero..one). /// We simply pick up the corresponding rel property from the input entity, and /// apply a deref operation /// NavProperty(e, n) => deref(relproperty(e, r)) /// where e is the entity expression, n is the nav-property, and r is the corresponding /// rel-property /// /// the rel-property describing the navigation /// entity instance that we're starting the traversal from /// type of the target entity ///a rewritten subtree private Node RewriteToOneNavigationProperty(RelProperty relProperty, Node sourceEntityNode, TypeUsage resultType) { RelPropertyOp relPropertyOp = m_command.CreateRelPropertyOp(relProperty); Node relPropertyNode = m_command.CreateNode(relPropertyOp, sourceEntityNode); DerefOp derefOp = m_command.CreateDerefOp(resultType); Node derefNode = m_command.CreateNode(derefOp, relPropertyNode); return derefNode; } ////// Rewrite a NavigationProperty when the relationship is a 1:N relationship. /// In essence, we find all the relevant target entitysets, and then compare the /// rel-property on the target end with the source ref /// /// Converts /// NavigationProperty(e, r) /// into /// SELECT VALUE t /// FROM (SELECT VALUE e1 FROM ES1 as e1 /// UNION ALL /// SELECT VALUE e2 FROM ES2 as e2 /// UNION ALL /// ... /// ) as t /// WHERE RelProperty(t, r') = GetEntityRef(e) /// /// r' is the inverse-relproperty for r /// /// We also build out a CollectOp over the subquery above, and return that /// /// the rel-property describing the relationship traversal /// the list of relevant relationshipsets /// node tree corresponding to the source entity ref /// type of the result ///the rewritten subtree private Node RewriteOneToManyNavigationProperty(RelProperty relProperty, ListrelationshipSets, Node sourceRefNode, TypeUsage resultType) { PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here"); PlanCompiler.Assert(relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many, "Expected source end multiplicity to be one. Found 'Many' instead " + relProperty); Node ret = null; // // We convert the // TypeUsage entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage); List scanTableNodes = new List (relationshipSets.Count); List scanTableVars = new List(relationshipSets.Count); foreach (RelationshipSet r in relationshipSets) { EntitySetBase entitySet = FindTargetEntitySet(r, relProperty.ToEnd); Var tableVar; Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar); scanTableNodes.Add(tableNode); scanTableVars.Add(tableVar); } // // Build the union-all node // Node unionAllNode; Var unionAllVar; m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); // // Now build up the appropriate filter. Select out the relproperty from the other end // RelProperty inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd); PlanCompiler.Assert(m_command.IsRelPropertyReferenced(inverseRelProperty), "Unreferenced rel property? " + inverseRelProperty); Node inverseRelPropertyNode = m_command.CreateNode( m_command.CreateRelPropertyOp(inverseRelProperty), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node predicateNode = m_command.BuildComparison(OpType.EQ, sourceRefNode, inverseRelPropertyNode); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicateNode); // // The magic of collections... // ret = m_command.BuildCollect(filterNode, unionAllVar); return ret; } /// /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r)) /// where "r" is a many-to-many relationship /// /// We essentially produce the following subquery /// SELECT VALUE x.e /// FROM (SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1) /// UNION ALL /// SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1) /// ... /// ) as x /// WHERE x.r.FromEnd = sourceRef /// /// RS1, RS2 etc. are the relevant relationshipsets /// ES1, ES2 etc. are the corresponding entitysets for the toEnd of the relationship /// sourceRef is the ref argument /// T is the type of the target-end of the relationship /// /// We then build a CollectOp over the subquery above /// /// the rel property to traverse /// list of relevant relationshipsets /// source ref /// type of the result ///private Node RewriteManyToManyNavigationProperty(RelProperty relProperty, List relationshipSets, Node sourceRefNode, TypeUsage resultType) { PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here"); PlanCompiler.Assert(relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many && relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many, "Expected target end multiplicity to be 'many'. Found " + relProperty + "; multiplicity = " + relProperty.ToEnd.RelationshipMultiplicity); Node ret = null; List joinNodes = new List (relationshipSets.Count); List outputVars = new List(relationshipSets.Count * 2); foreach (RelationshipSet r in relationshipSets) { Var rsVar; Var esVar; Node joinNode = BuildJoinForNavProperty(r, relProperty.ToEnd, out rsVar, out esVar); joinNodes.Add(joinNode); outputVars.Add(rsVar); outputVars.Add(esVar); } // // Build the union-all node // Node unionAllNode; IList unionAllVars; m_command.BuildUnionAllLadder(joinNodes, outputVars, out unionAllNode, out unionAllVars); // // Now build out the filterOp over the left-side var // Node rsSourceRefNode = m_command.CreateNode(m_command.CreatePropertyOp(relProperty.FromEnd), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVars[0]))); Node predicate = m_command.BuildComparison(OpType.EQ, sourceRefNode, rsSourceRefNode); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicate); // // Finally, build out a project node that only projects out the entity side // Node projectNode = m_command.BuildProject(filterNode, new Var[] { unionAllVars[1] }, new Node[] { }); // // Build a collectOp over the project node // ret = m_command.BuildCollect(projectNode, unionAllVars[1]); return ret; } /// /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r)) /// /// We handle three cases here, depending on the kind of relationship we're /// dealing with. /// - *:1 relationships /// - N:1 relationships /// - N:M relationships /// /// /// the navigation property /// the input ref to start the traversal /// the result type of the expression ///the rewritten tree private Node RewriteNavigationProperty(NavigationProperty navProperty, Node sourceEntityNode, TypeUsage resultType) { Node ret = null; RelProperty relProperty = new RelProperty(navProperty.RelationshipType, navProperty.FromEndMember, navProperty.ToEndMember); PlanCompiler.Assert(m_command.IsRelPropertyReferenced(relProperty) || (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many), "Unreferenced rel property? " + relProperty); // // Case 1: The (target end of the) nav property has a multiplicity of 1 (or 0..1) // (doesn't matter what the sourceEnd multiplicity is) // if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One || relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne) { ret = RewriteToOneNavigationProperty(relProperty, sourceEntityNode, resultType); return ret; } // // Otherwise, the target end is multi-valued. We need to deal with // 2 cases here. A N:1 relationship or a N:M relationship // // // Find the list of all relationships that could satisfy this relationship // If we find no matching relationship set, simply return an empty collection // ListrelationshipSets = GetRelationshipSets(relProperty.Relationship); if (relationshipSets.Count == 0) { // return an empty set return m_command.CreateNode(m_command.CreateNewMultisetOp(resultType)); } // // Build out a ref over the source entity now // Node sourceRefNode = m_command.CreateNode( m_command.CreateGetEntityRefOp(relProperty.FromEnd.TypeUsage), sourceEntityNode); // // Are we dealing with a many-to-many relationship ? // if (relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many) { ret = RewriteManyToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType); } else { ret = RewriteOneToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType); } return ret; } #endregion #region visitor methods #region ScalarOps /// /// Default handler for scalar Ops. Simply traverses the children, /// and also identifies any structured types along the way /// /// the ScalarOp /// current subtree ///the possibly modified node protected override Node VisitScalarOpDefault(ScalarOp op, Node n) { VisitChildren(n); // visit my children // keep track of referenced types AddTypeReference(op.Type); return n; } ////// Rewrite a DerefOp subtree. We have two cases to consider here. /// We call RewriteDerefOp to return a subtree (and an optional outputVar). /// If the outputVar is null, then we simply return the subtree produced by those calls. /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar /// in its place. /// /// As an example, /// select deref(e) from T /// gets rewritten into /// select v from T OuterApply X /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X /// /// /// the derefOp /// the deref subtree ///the rewritten tree public override Node Visit(DerefOp op, Node n) { Var outputVar; VisitScalarOpDefault(op, n); Node ret = RewriteDerefOp(n, op, out outputVar); ret = VisitNode(ret); if (outputVar != null) { ret = AddSubqueryToParentRelOp(outputVar, ret); } return ret; } ////// Processing for an ElementOp. Replaces this by the corresponding Var from /// the subquery, and adds the subquery to the list of currently tracked subqueries /// /// the elementOp /// current subtree ///the Var from the subquery public override Node Visit(ElementOp op, Node n) { VisitScalarOpDefault(op, n); // default processing // get to the subquery... Node subQueryRelOp = n.Child0; ProjectOp projectOp = (ProjectOp)subQueryRelOp.Op; PlanCompiler.Assert(projectOp.Outputs.Count == 1, "input to ElementOp has more than one output var?"); Var projectVar = projectOp.Outputs.First; Node ret = AddSubqueryToParentRelOp(projectVar, subQueryRelOp); return ret; } ////// Mark Normalization as needed /// /// /// ///public override Node Visit(ExistsOp op, Node n) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization); return base.Visit(op, n); } /// /// If this is TVF or a collection aggregate function NestPullUp and Normalization are needed /// /// /// ///public override Node Visit(FunctionOp op, Node n) { // If this is TVF or a collection aggregate function NestPullUp and Normalization are needed if (TypeSemantics.IsCollectionType(op.Type) || PlanCompilerUtil.IsCollectionAggregateFunction(op, n)) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup); m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization); } return base.Visit(op, n); } /// /// Default processing. /// In addition, if the case statement is of the shape /// case when X then NULL else Y, or /// case when X then Y else NULL, /// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same, /// marks that type as needing a null sentinel. /// This allows in NominalTypeElimination the case op to be pushed inside Y's null sentinel. /// /// /// ///public override Node Visit(CaseOp op, Node n) { VisitScalarOpDefault(op, n); //special handling to enable optimization bool thenClauseIsNull; if (PlanCompilerUtil.IsRowTypeCaseOpWithNullability(op, n, out thenClauseIsNull)) { //Add a null sentinel for the row type m_typesNeedingNullSentinel.Add(op.Type.EdmType.Identity); } return n; } /// /// Special processing for ConditionalOp is handled by /// /// ////// public override Node Visit(ConditionalOp op, Node n) { VisitScalarOpDefault(op, n); ProcessConditionalOp(op, n); return n; } /// /// If it is a IsNull op over a row type or a complex type mark the type as needing a null sentinel. /// /// /// private void ProcessConditionalOp(ConditionalOp op, Node n) { if (op.OpType == OpType.IsNull && TypeSemantics.IsRowType(n.Child0.Op.Type) || TypeSemantics.IsComplexType(n.Child0.Op.Type)) { StructuredTypeNullabilityAnalyzer.MarkAsNeedingNullSentinel(m_typesNeedingNullSentinel, n.Child0.Op.Type); } } #region PropertyOp Handling ////// Validates that the nav property agrees with the underlying relationship /// /// the Nav PropertyOp /// the subtree private void ValidateNavPropertyOp(PropertyOp op, Node n) { NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo; // // If the result of the expanded form of the navigation property is not compatible with // the declared type of the property, then the navigation property is invalid in the // context of this command tree's metadata workspace. // TypeUsage resultType = navProperty.ToEndMember.TypeUsage; if (TypeSemantics.IsReferenceType(resultType)) { resultType = TypeHelpers.GetElementTypeUsage(resultType); } if (navProperty.ToEndMember.RelationshipMultiplicity == RelationshipMultiplicity.Many) { resultType = TypeUsage.Create(resultType.EdmType.GetCollectionType()); } if (!TypeSemantics.IsStructurallyEqualOrPromotableTo(resultType, op.Type)) { throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_IncompatibleNavigationPropertyResult( navProperty.DeclaringType.FullName, navProperty.Name ) ); } } ////// Rewrite a PropertyOp subtree for a nav property /// /// We call RewriteNavigationPropertyOp to return a subtree (and an /// optional outputVar). If the outputVar is null, then we simply return the subtree produced by those calls. /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar /// in its place. /// /// As an example, /// select e.NP from T /// gets rewritten into /// select v from T OuterApply X /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X /// /// the PropertyOp /// the current node ///the rewritten subtree private Node VisitNavPropertyOp(PropertyOp op, Node n) { ValidateNavPropertyOp(op, n); // // This is a bit weird. Ideally, I would always visit the child first (ie) a bottom-up traversal, // but there's some weird gotchas in the elinq tests ("SelectManyNullResult531057") // bool visitChildFirst = (n.Child0.Op.OpType != OpType.Property); if (visitChildFirst) { VisitScalarOpDefault(op, n); } NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo; Node ret = RewriteNavigationProperty(navProperty, n.Child0, op.Type); ret = VisitNode(ret); return ret; } ////// Rewrite a PropertyOp subtree. /// /// If the PropertyOp represents a simple property (ie) not a navigation property, we simply call /// VisitScalarOpDefault() and return. Otherwise, we call VisitNavPropertyOp and return the result from /// that function /// /// /// the PropertyOp /// the PropertyOp subtree ///the rewritten tree public override Node Visit(PropertyOp op, Node n) { Node ret; if (Helper.IsNavigationProperty(op.PropertyInfo)) { ret = VisitNavPropertyOp(op, n); } else { ret = VisitScalarOpDefault(op, n); } return ret; } #endregion ////// Handler for a RefOp. /// Keeps track of the entityset /// /// the RefOp /// current RefOp subtree ///current subtree public override Node Visit(RefOp op, Node n) { VisitScalarOpDefault(op, n); // use default processing AddEntitySetReference(op.EntitySet); // add to list of references return n; } ////// Handler for a TreatOp. /// Rewrites the operator if the argument is guaranteed to be of type /// op. /// /// Current TreatOp /// Current subtree ///Current subtree public override Node Visit(TreatOp op, Node n) { n = base.Visit(op, n); // See if TreatOp can be rewritten (if it's not polymorphic) if (CanRewriteTypeTest(op.Type.EdmType, n.Child0.Op.Type.EdmType)) { // Return argument directly (if the argument is null, 'treat as' also returns null; // if the argument is not null, it's guaranteed to be of the correct type) return n.Child0; } return n; } ////// Handler for an IsOfOp. /// Keeps track of the IsOfType (if it is a structured type) and rewrites the /// operator if the argument is guaranteed to be of type op.IsOfType /// /// Current IsOfOp /// Current subtree ///Current subtree public override Node Visit(IsOfOp op, Node n) { n = VisitScalarOpDefault(op, n); // default handling first // keep track of any structured types AddTypeReference(op.IsOfType); // See if the IsOfOp can be rewritten (if it's not polymorphic) if (CanRewriteTypeTest(op.IsOfType.EdmType, n.Child0.Op.Type.EdmType)) { n = RewriteIsOfAsIsNull(op, n); } // For IsOfOnly(abstract type), suppress DiscriminatorMaps since no explicit type id is available for // abstract types. if (op.IsOfOnly && op.IsOfType.EdmType.Abstract) { m_suppressDiscriminatorMaps = true; } return n; } // Determines whether a type test expression can be rewritten. Returns true of the // argument type is guaranteed to implement "testType" (if the argument is non-null). private bool CanRewriteTypeTest(EdmType testType, EdmType argumentType) { // The rewrite only proceeds if the types are the same. If they are not, // it suggests either that the input result is polymorphic (in which case if OfType // should be preserved) or the types are incompatible (which is caught // elsewhere) if (!testType.EdmEquals(argumentType)) { return false; } // If the IsOfType is non-polymorphic (no base or derived types) the rewrite // is possible. if (null != testType.BaseType) { return false; } // Count sub types int subTypeCount = 0; foreach (EdmType subType in MetadataHelper.GetTypeAndSubtypesOf(testType, m_command.MetadataWorkspace, true /*includeAbstractTypes*/)) { subTypeCount++; if (2 == subTypeCount) { break; } } return 1 == subTypeCount; // no children types } // Translates // 'R is of T' // to // '(case when not (R is null) then True else null end) = True' // // Input requirements: // // - IsOfOp and argument to same must be in the same hierarchy. // - IsOfOp and argument must have the same type // - IsOfOp.IsOfType may not have super- or sub- types (validate // using CanRewriteTypeTest) // // Design requirements: // // - Must return true if the record exists // - Must return null if it does not // - Must be in predicate form to avoid confusing SQL gen // // The translation assumes R is of T when R is non null. private Node RewriteIsOfAsIsNull(IsOfOp op, Node n) { // construct 'R is null' predicate ConditionalOp isNullOp = m_command.CreateConditionalOp(OpType.IsNull); Node isNullNode = m_command.CreateNode(isNullOp, n.Child0); // Process the IsNull node to make sure a null sentinel gets added if needed ProcessConditionalOp(isNullOp, isNullNode); // construct 'not (R is null)' predicate ConditionalOp notOp = m_command.CreateConditionalOp(OpType.Not); Node notNode = m_command.CreateNode(notOp, isNullNode); // construct 'True' result ConstantBaseOp trueOp = m_command.CreateConstantOp(op.Type, true); Node trueNode = m_command.CreateNode(trueOp); // construct 'null' default result NullOp nullOp = m_command.CreateNullOp(op.Type); Node nullNode = m_command.CreateNode(nullOp); // create case statement CaseOp caseOp = m_command.CreateCaseOp(op.Type); Node caseNode = m_command.CreateNode(caseOp, notNode, trueNode, nullNode); // create 'case = true' operator ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ); Node equalsNode = m_command.CreateNode(equalsOp, caseNode, trueNode); return equalsNode; } ////// Rewrite a NavigateOp subtree. /// We call RewriteNavigateOp to return a subtree (and an optional outputVar). /// If the outputVar is null, then we simply return the subtree produced by those calls. /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar /// in its place. /// /// As an example, /// select navigate(e) from T /// gets rewritten into /// select v from T OuterApply X /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X /// /// /// the navigateOp /// the navigateOp subtree ///the rewritten tree public override Node Visit(NavigateOp op, Node n) { VisitScalarOpDefault(op, n); Var outputVar; Node ret = RewriteNavigateOp(n, op, out outputVar); ret = VisitNode(ret); // Move subquery to parent relop if necessary if (outputVar != null) { ret = AddSubqueryToParentRelOp(outputVar, ret); } return ret; } ////// Find the "current" enclosing entityset /// ///the enclosing entityset (if any) private EntitySetBase FindEnclosingEntitySetView() { if (m_viewNestingLevel == 0) { return null; } // // Walk up the stack of ancestors until we find the appropriate ScanViewOp // foreach (Node n in m_ancestors) { if (n.Op.OpType == OpType.ScanView) { ScanViewOp op = (ScanViewOp)n.Op; return op.Table.TableMetadata.Extent; } } PlanCompiler.Assert(false, "found no enclosing view - but view-nesting level is greater than zero"); return null; } ////// Find the relationshipset that matches the current entityset + from/to roles /// /// /// ///private RelationshipSet FindRelationshipSet(EntitySetBase entitySet, RelProperty relProperty) { foreach (EntitySetBase es in entitySet.EntityContainer.BaseEntitySets) { AssociationSet rs = es as AssociationSet; if (rs != null && rs.ElementType.EdmEquals(relProperty.Relationship) && rs.AssociationSetEnds[relProperty.FromEnd.Identity].EntitySet.EdmEquals(entitySet)) { return rs; } } return null; } /// /// Find the position of a property in a type. /// Positions start at zero, and a supertype's properties precede the current /// type's properties /// /// the type in question /// the member to lookup ///the position of the member in the type (0-based) private int FindPosition(EdmType type, EdmMember member) { int pos = 0; foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(type)) { if (m.EdmEquals(member)) { return pos; } pos++; } PlanCompiler.Assert(false, "Could not find property " + member + " in type " + type.Name); return -1; } ////// Build out an expression (NewRecord) that corresponds to the key properties /// of the passed-in entity constructor /// /// This function simply looks up the key properties of the entity type, and then /// identifies the arguments to the constructor corresponding to those /// properties, and then slaps on a record wrapper over those expressions. /// /// No copies/clones are performed. That's the responsibility of the caller /// /// /// the entity constructor op /// the corresponding subtree ///the key expression private Node BuildKeyExpressionForNewEntityOp(Op op, Node n) { PlanCompiler.Assert(op.OpType == OpType.NewEntity || op.OpType == OpType.DiscriminatedNewEntity, "BuildKeyExpression: Unexpected OpType:" + op.OpType); int offset = (op.OpType == OpType.DiscriminatedNewEntity) ? 1 : 0; EntityTypeBase entityType = (EntityTypeBase)op.Type.EdmType; ListkeyFields = new List (); List > keyFieldTypes = new List >(); foreach (EdmMember k in entityType.KeyMembers) { int pos = FindPosition(entityType, k) + offset; PlanCompiler.Assert(n.Children.Count > pos, "invalid position " + pos + "; total count = " + n.Children.Count); keyFields.Add(n.Children[pos]); keyFieldTypes.Add(new KeyValuePair (k.Name, k.TypeUsage)); } TypeUsage keyExprType = TypeHelpers.CreateRowTypeUsage(keyFieldTypes, true); NewRecordOp keyOp = m_command.CreateNewRecordOp(keyExprType); Node keyNode = m_command.CreateNode(keyOp, keyFields); return keyNode; } /// /// Build out an expression corresponding to the rel-property. /// /// We create a subquery that looks like /// (select r /// from RS r /// where GetRefKey(r.FromEnd) = myKey) /// /// RS is the single relationship set that corresponds to the given entityset/rel-property pair /// FromEnd - is the source end of the relationship /// myKey - is the key expression of the entity being constructed /// /// NOTE: We always clone "myKey" before use. /// /// We then convert it into a scalar subquery, and extract out the ToEnd property from /// the output var of the subquery. (Should we do this inside the subquery itself?) /// /// If no single relationship-set is found, we return a NULL instead. /// /// entity set that logically holds instances of the entity we're building /// the rel-property we're trying to build up /// the "key" of the entity instance ///the rel-property expression private Node BuildRelPropertyExpression(EntitySetBase entitySet, RelProperty relProperty, Node keyExpr) { // // Make a copy of the current key expression // keyExpr = OpCopier.Copy(m_command, keyExpr); // // Find the relationship set corresponding to this entityset (and relProperty) // Return a null ref, if we can't find one // RelationshipSet relSet = FindRelationshipSet(entitySet, relProperty); if (relSet == null) { return m_command.CreateNode(m_command.CreateNullOp(relProperty.ToEnd.TypeUsage)); } ScanTableOp scanTableOp = m_command.CreateScanTableOp(Command.CreateTableDefinition(relSet)); PlanCompiler.Assert(scanTableOp.Table.Columns.Count == 1, "Unexpected column count for table:" + scanTableOp.Table.TableMetadata.Extent + "=" + scanTableOp.Table.Columns.Count); Var scanTableVar = scanTableOp.Table.Columns[0]; Node scanNode = m_command.CreateNode(scanTableOp); Node sourceEndNode = m_command.CreateNode( m_command.CreatePropertyOp(relProperty.FromEnd), m_command.CreateNode(m_command.CreateVarRefOp(scanTableVar))); Node predicateNode = m_command.BuildComparison(OpType.EQ, keyExpr, m_command.CreateNode(m_command.CreateGetRefKeyOp(keyExpr.Op.Type), sourceEndNode)); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), scanNode, predicateNode); // // Process the node, and then add this as a subquery to the parent relop // Node ret = VisitNode(filterNode); ret = AddSubqueryToParentRelOp(scanTableVar, ret); // // Now extract out the target end property // ret = m_command.CreateNode( m_command.CreatePropertyOp(relProperty.ToEnd), ret); return ret; } ////// Given an entity constructor (NewEntityOp, DiscriminatedNewEntityOp), build up /// the list of rel-property expressions. /// /// Walks through the list of relevant rel-properties, and builds up expressions /// (using BuildRelPropertyExpression) for each rel-property that does not have /// an expression already built (preBuiltExpressions) /// /// entity set that holds instances of the entity we're building /// the list of relevant rel-properties for this entity type /// the prebuilt rel-property expressions /// the key of the entity instance ///a list of rel-property expressions (lines up 1-1 with 'relPropertyList') private IEnumerableBuildAllRelPropertyExpressions(EntitySetBase entitySet, List relPropertyList, Dictionary prebuiltExpressions, Node keyExpr) { foreach (RelProperty r in relPropertyList) { Node relPropNode; if (!prebuiltExpressions.TryGetValue(r, out relPropNode)) { relPropNode = BuildRelPropertyExpression(entitySet, r, keyExpr); } yield return relPropNode; } } /// /// Handler for NewEntityOp. /// If this is an EntityConstructor, and the current view nesting level is 0 /// (ie) this is an EntityConstructor at the top-level query, then add /// the type to the list of "free-floating" entity constructor types /// /// the NewEntityOp /// the node tree corresponding to the op ///rewritten tree public override Node Visit(NewEntityOp op, Node n) { // Note: We don't do the default processing first to avoid adding references to types and entity sets // that may only be used in pre-build rel property expressions that may not be needed. EntityType entityType = op.Type.EdmType as EntityType; EntitySetBase entitySet = FindEnclosingEntitySetView(); if (entitySet == null) { if (entityType != null) { m_freeFloatingEntityConstructorTypes.Add(entityType); } // SQLBUDT #546546: Qmv/Umv tests Assert and throws in plan compiler in association tests. // If this Entity constructor is not within a view then there should not be any RelProps // specified on the NewEntityOp - the eSQL WITH RELATIONSHIPS clause that would cause such // RelProps to be added is only enabled when parsing in the user or generated view mode. PlanCompiler.Assert(op.RelationshipProperties == null || op.RelationshipProperties.Count == 0, "Related Entities cannot be specified for Entity constructors that are not part of the Query Mapping View for an Entity Set."); VisitScalarOpDefault(op, n); return n; } // // Find the relationship properties for this entitytype (and entity set) // ListrelProperties = new List (m_relPropertyHelper.GetRelProperties(entityType)); // Remove pre-build rel property expressions that would not be needed to avoid // unnecessary adding references to types and entity sets during default processing int j = op.RelationshipProperties.Count - 1; List copiedRelPropList = new List (op.RelationshipProperties); for (int i = n.Children.Count - 1; i >= entityType.Properties.Count; i--, j--) { if (!relProperties.Contains(op.RelationshipProperties[j])) { n.Children.RemoveAt(i); copiedRelPropList.RemoveAt(j); } } //Default processing VisitScalarOpDefault(op, n); // // Ok, now, I have to build out some relationship properties that // haven't been specified // Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n); // // Find the list of rel properties that have already been specified // Dictionary prebuiltRelPropertyExprs = new Dictionary (); j = 0; for (int i = entityType.Properties.Count; i < n.Children.Count; i++, j++) { prebuiltRelPropertyExprs[copiedRelPropList[j]] = n.Children[i]; } // // Fill in the missing pieces // // // Next, rebuild the list of children - includes expressions for each rel property // List newChildren = new List (); for (int i = 0; i < entityType.Properties.Count; i++) { newChildren.Add(n.Children[i]); } foreach (Node relPropNode in BuildAllRelPropertyExpressions(entitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) { newChildren.Add(relPropNode); } // // finally, build out the newOp // Op newEntityOp = m_command.CreateNewEntityOp(op.Type, relProperties, entitySet); Node newNode = m_command.CreateNode(newEntityOp, newChildren); return newNode; } /// /// Tracks discriminator metadata so that is can be used when constructing /// StructuredTypeInfo. /// public override Node Visit(DiscriminatedNewEntityOp op, Node n) { HashSetrelPropertyHashSet = new HashSet (); List relProperties = new List (); // // add references to each type produced by this node // Also, get the set of rel-properties for each of the types // foreach (var discriminatorTypePair in op.DiscriminatorMap.TypeMap) { EntityTypeBase entityType = discriminatorTypePair.Value; AddTypeReference(TypeUsage.Create(entityType)); foreach (RelProperty relProperty in m_relPropertyHelper.GetRelProperties(entityType)) { relPropertyHashSet.Add(relProperty); } } relProperties = new List (relPropertyHashSet); VisitScalarOpDefault(op, n); // // Now build out the set of missing rel-properties (if any) // // first, build the key expression Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n); List newChildren = new List (); int firstRelPropertyNodeOffset = n.Children.Count - op.RelationshipProperties.Count; for (int i = 0; i < firstRelPropertyNodeOffset; i++) { newChildren.Add(n.Children[i]); } // // Find the list of rel properties that have already been specified // Dictionary prebuiltRelPropertyExprs = new Dictionary (); for (int i = firstRelPropertyNodeOffset, j = 0; i < n.Children.Count; i++, j++) { prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i]; } // // Fill in the missing pieces // foreach (Node relPropNode in BuildAllRelPropertyExpressions(op.EntitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) { newChildren.Add(relPropNode); } Op newEntityOp = m_command.CreateDiscriminatedNewEntityOp(op.Type, op.DiscriminatorMap, op.EntitySet, relProperties); Node newNode = m_command.CreateNode(newEntityOp, newChildren); return newNode; } /// /// Handles a newMultiset constructor. Converts this into /// select a from dual union all select b from dual union all ... /// Handles a NewMultiset constructor, i.e. {x, y, z} /// 1. Empty multiset constructors are simply converted into: /// /// select x from singlerowtable as x where false /// /// 2. Mulltset constructors with only one element or with multiple elements all of /// which are constants or nulls are converted into: /// /// select x from dual union all select y from dual union all select z /// /// 3. All others are converted into: /// /// select case when d = 0 then x when d = 1 then y else z end /// from ( select 0 as d from single_row_table /// union all /// select 1 as d from single_row_table /// union all /// select 2 as d from single_row_table ) /// /// NOTE: The translation for 2 is valid for 3 too. We choose different translation /// in order to avoid correlation inside the union all, /// which would prevent us from removing apply operators /// /// Do this before processing the children, and then /// call Visit on the result to handle the elements /// /// the new instance op /// the current subtree ///the modified subtree public override Node Visit(NewMultisetOp op, Node n) { Node resultNode = null; Var resultVar = null; CollectionType collectionType = TypeHelpers.GetEdmType(op.Type); // // Empty multiset constructors are simply converted into // Project(Filter(SingleRowTableOp(), false) // if (!n.HasChild0) { Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), singleRowTableNode, m_command.CreateNode(m_command.CreateFalseOp())); Node fakeChild = m_command.CreateNode(m_command.CreateNullOp(collectionType.TypeUsage)); Var newVar; Node projectNode = m_command.BuildProject(filterNode, fakeChild, out newVar); resultNode = projectNode; resultVar = newVar; } // // Multiset constructors with only one elment or with multiple elments all of // which are constants or nulls are converted into: // // UnionAll(Project(SingleRowTable, e1), Project(SingleRowTable, e2), ...) // // The degenerate case when the collection has only one element does not require an // outer unionAll node // else if (n.Children.Count == 1 || AreAllConstantsOrNulls(n.Children)) { List inputNodes = new List (); List inputVars = new List(); foreach (Node chi in n.Children) { Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); Var newVar; Node projectNode = m_command.BuildProject(singleRowTableNode, chi, out newVar); inputNodes.Add(projectNode); inputVars.Add(newVar); } // Build the union-all ladder m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar); } // // All other cases: // // select case when d = 0 then x when d = 1 then y else z end // from ( select 0 as d from single_row_table // union all // select 1 as d from single_row_table // union all // select 2 as d from single_row_table ) // else { List inputNodes = new List (); List inputVars = new List(); //Create the union all lather first for (int i = 0; i < n.Children.Count; i++) { Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); // the discriminator for this branch Node discriminatorNode = m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.IntegerType, i)); Var newVar; Node projectNode = m_command.BuildProject(singleRowTableNode, discriminatorNode, out newVar); inputNodes.Add(projectNode); inputVars.Add(newVar); } // Build the union-all ladder now m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar); //Now create the case statement for the projection List caseArgNodes = new List (n.Children.Count * 2 + 1); for (int i = 0; i < n.Children.Count; i++) { //For all but the last we need a when if (i != (n.Children.Count - 1)) { ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ); Node whenNode = m_command.CreateNode(equalsOp, m_command.CreateNode(m_command.CreateVarRefOp(resultVar)), m_command.CreateNode( m_command.CreateConstantOp(m_command.IntegerType, i))); caseArgNodes.Add(whenNode); } //Add the then/else node caseArgNodes.Add(n.Children[i]); } //Create the project Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(collectionType.TypeUsage), caseArgNodes); resultNode = m_command.BuildProject(resultNode, caseNode, out resultVar); } // So, I've finally built up a complex query corresponding to the constructor. // Now, cap this with a physicalprojectOp, and then with a CollectOp PhysicalProjectOp physicalProjectOp = m_command.CreatePhysicalProjectOp(resultVar); Node physicalProjectNode = m_command.CreateNode(physicalProjectOp, resultNode); CollectOp collectOp = m_command.CreateCollectOp(op.Type); Node collectNode = m_command.CreateNode(collectOp, physicalProjectNode); return VisitNode(collectNode); } /// /// Returns true if each node in the list is either a constant or a null /// /// ///private bool AreAllConstantsOrNulls(List nodes) { foreach (Node node in nodes) { if (node.Op.OpType != OpType.Constant && node.Op.OpType != OpType.Null) { return false; } } return true; } /// /// Default processing for a CollectOp. But make sure that we /// go through the NestPullUp phase /// /// /// ///public override Node Visit(CollectOp op, Node n) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup); return VisitScalarOpDefault(op, n); } #endregion #region RelOps private void HandleTableOpMetadata(ScanTableBaseOp op) { // add to the list of referenced entitysets EntitySet entitySet = op.Table.TableMetadata.Extent as EntitySet; if (entitySet != null) { AddEntitySetReference(entitySet); } TypeUsage elementType = TypeUsage.Create(op.Table.TableMetadata.Extent.ElementType); // add to the list of structured types AddTypeReference(elementType); } /// /// Visits a "table" expression - performs view expansion on the table (if appropriate), /// and then some additional book-keeping. /// /// The "ofType" and "includeSubtypes" parameters are optional hints for view expansion, allowing /// for more customized (and hopefully, more optimal) views. The wasOfTypeSatisfied out parameter /// tells whether the ofType filter was already handled by the view expansion, or if the caller still /// needs to deal with it. /// /// If the "table" is a C-space entityset, then we produce a ScanViewOp /// tree with the defining query as the only child of the ScanViewOp /// /// If the table is an S-space entityset, then we still produce a ScanViewOp, but this /// time, we produce a simple "select * from BaseTable" as the defining /// query /// /// the scanTable node tree /// the scanTableOp /// /// An optional IsOfOp representing a type filter to apply to the scan table; will be set tonull /// if the scan target is expanded to a view that renders the type filter superfluous. /// ///private Node ProcessScanTable(Node scanTableNode, ScanTableOp scanTableOp, ref IsOfOp typeFilter) { HandleTableOpMetadata(scanTableOp); PlanCompiler.Assert(scanTableOp.Table.TableMetadata.Extent != null, "ScanTableOp must reference a table with an extent"); Node ret = null; // // Get simple things out of the way. If we're dealing with an S-space entityset, // simply return the node // if (scanTableOp.Table.TableMetadata.Extent.EntityContainer.DataSpace == DataSpace.SSpace) { return scanTableNode; } else { // "Expand" the C-Space view ret = ExpandView(scanTableNode, scanTableOp, ref typeFilter); } m_viewNestingLevel++; // Rerun the processor over the resulting subtree ret = VisitNode(ret); m_viewNestingLevel--; return ret; } /// /// Processes a ScanTableOp - simply delegates to ProcessScanTableOp /// /// the view op /// current node tree ///the transformed view-op public override Node Visit(ScanTableOp op, Node n) { IsOfOp nullFilter = null; return ProcessScanTable(n, op, ref nullFilter); } ////// Visitor for a ScanViewOp /// /// /// ///public override Node Visit(ScanViewOp op, Node n) { HandleTableOpMetadata(op); // Ideally, I should call this as the first statement, but that was causing too // many test diffs - because of the order in which the entitytypes/sets // were being added. There is no semantic difference in calling this here VisitRelOpDefault(op, n); return n; } /// /// Processing for all JoinOps /// /// JoinOp /// Current subtree ///protected override Node VisitJoinOp(JoinBaseOp op, Node n) { // Only LeftOuterJoin and InnerJoin are handled by JoinElimination if (op.OpType == OpType.InnerJoin || op.OpType == OpType.LeftOuterJoin) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); } // If a subquery was added with an exists node, we have to go througth Normalization if (base.ProcessJoinOp(op, n)) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization); } return n; } /// /// Perform default relop processing; Also "require" the join-elimination phase /// /// /// ///protected override Node VisitApplyOp(ApplyBaseOp op, Node n) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); return VisitRelOpDefault(op, n); } /// /// Can I eliminate this sort? I can, if the current path is *not* one of the /// following /// TopN(Sort) /// PhysicalProject(Sort) /// /// We don't yet handle the TopN variant /// ///private bool IsSortUnnecessary() { Node ancestor = m_ancestors.Peek(); PlanCompiler.Assert(ancestor != null, "unexpected SortOp as root node?"); if (ancestor.Op.OpType == OpType.PhysicalProject) { return false; } return true; } /// /// Visit a SortOp. Eliminate it if the path to this node is not one of /// PhysicalProject(Sort) or /// TopN(Sort) /// /// Otherwise, simply visit the child RelOp /// /// /// Current sortOp /// current subtree ///possibly transformed subtree public override Node Visit(SortOp op, Node n) { // can I eliminate this sort if (this.IsSortUnnecessary()) { return VisitNode(n.Child0); } // perform default processing return VisitRelOpDefault(op, n); } ////// Checks to see if this filterOp represents an IS OF (or IS OF ONLY) filter over a ScanTableOp /// /// the filterOp node /// (OUT) the Type to restrict to /// (OUT) was an ONLY clause specified ///private bool IsOfTypeOverScanTable(Node n, out IsOfOp typeFilter) { typeFilter = null; // // Is the predicate an IsOf predicate // IsOfOp isOfOp = n.Child1.Op as IsOfOp; if (isOfOp == null) { return false; } // // Is the Input RelOp a ScanTableOp // ScanTableOp scanTableOp = n.Child0.Op as ScanTableOp; if (scanTableOp == null || scanTableOp.Table.Columns.Count != 1) { return false; } // // Is the argument to the IsOfOp the single column of the table? // VarRefOp varRefOp = n.Child1.Child0.Op as VarRefOp; if (varRefOp == null || varRefOp.Var != scanTableOp.Table.Columns[0]) { return false; } // // All conditions match. Return the info from the IsOf predicate // typeFilter = isOfOp; return true; } /// /// Handler for a FilterOp. Usually delegates to VisitRelOpDefault. /// /// There's one special case - where we have an ISOF predicate over a ScanTable. In that case, we attempt /// to get a more "optimal" view; and return that optimal view /// /// /// the filterOp /// the node tree ///public override Node Visit(FilterOp op, Node n) { IsOfOp typeFilter; if (IsOfTypeOverScanTable(n, out typeFilter)) { Node ret = ProcessScanTable(n.Child0, (ScanTableOp)n.Child0.Op, ref typeFilter); if (typeFilter != null) { n.Child1 = VisitNode(n.Child1); n.Child0 = ret; ret = n; } return ret; } else { return VisitRelOpDefault(op, n); } } /// /// Visit a ProjectOp; if the input is a SortOp, we pullup the sort over /// the ProjectOp to ensure that we don't have nested sorts; /// Note: This transformation cannot be moved in the normalizer, /// because it needs to happen before any subquery augmentation happens. /// /// /// ///public override Node Visit(ProjectOp op, Node n) { PlanCompiler.Assert(n.HasChild0, "projectOp without input?"); if (OpType.Sort == n.Child0.Op.OpType || OpType.ConstrainedSort == n.Child0.Op.OpType) { SortBaseOp sort = (SortBaseOp)n.Child0.Op; IList sortChildren = new List (); sortChildren.Add(n); //A ConstrainedSort has two other children besides the input and it needs to keep them. for (int i = 1; i < n.Child0.Children.Count; i++) { sortChildren.Add(n.Child0.Children[i]); } // Replace the ProjectOp input (currently the Sort node) with the input to the Sort. n.Child0 = n.Child0.Child0; // Vars produced by the Sort input and used as SortKeys should be considered outputs // of the ProjectOp that now operates over what was the Sort input. foreach (SortKey key in sort.Keys) { op.Outputs.Set(key.Var); } // Finally, pull the Sort over the Project by creating a new Sort node with the original // Sort as its Op and the Project node as its only child. This is sufficient because // the ITreeGenerator ensures that the SortOp does not have any local VarDefs. return VisitNode(m_command.CreateNode(sort, sortChildren)); } // perform default processing Node newNode = VisitRelOpDefault(op, n); return newNode; } /// /// Mark AggregatePushdown as needed /// /// the groupByInto op /// the node tree ///public override Node Visit(GroupByIntoOp op, Node n) { this.m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.AggregatePushdown); return base.Visit(op, n); } #endregion #endregion #endregion } /// /// Finds the record (Row) types that we're projecting out of the query, and /// ensures that we mark them as needing a nullable sentinel, so when we /// flatten them later we'll have one added. /// internal class StructuredTypeNullabilityAnalyzer : ColumnMapVisitor> { static internal StructuredTypeNullabilityAnalyzer Instance = new StructuredTypeNullabilityAnalyzer(); /// /// VarRefColumnMap /// /// /// ///internal override void Visit(VarRefColumnMap columnMap, HashSet typesNeedingNullSentinel) { AddTypeNeedingNullSentinel(typesNeedingNullSentinel, columnMap.Type); base.Visit(columnMap, typesNeedingNullSentinel); } /// /// Recursively add any Row types to the list of types needing a sentinel. /// /// /// private static void AddTypeNeedingNullSentinel(HashSettypesNeedingNullSentinel, TypeUsage typeUsage) { if (TypeSemantics.IsCollectionType(typeUsage)) { AddTypeNeedingNullSentinel(typesNeedingNullSentinel, TypeHelpers.GetElementTypeUsage(typeUsage)); } else { if (TypeSemantics.IsRowType(typeUsage) || TypeSemantics.IsComplexType(typeUsage)) { MarkAsNeedingNullSentinel(typesNeedingNullSentinel, typeUsage); } foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(typeUsage)) { AddTypeNeedingNullSentinel(typesNeedingNullSentinel, m.TypeUsage); } } } /// /// Marks the given typeUsage as needing a null sentinel. /// Call this method instead of calling Add over the HashSet directly, to ensure consistency. /// /// /// internal static void MarkAsNeedingNullSentinel(HashSettypesNeedingNullSentinel, TypeUsage typeUsage) { typesNeedingNullSentinel.Add(typeUsage.EdmType.Identity); } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. //---------------------------------------------------------------------- // // Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System; using System.Collections.Generic; using System.Data.Common; using System.Data.Common.Utils; using System.Data.Metadata.Edm; using System.Data.Query.InternalTrees; //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class... // // The PreProcessor module is responsible for performing any required preprocessing // on the tree and gathering information before subsequent phases may be performed. // The main responsibilites of the preprocessor are: // // (a) gathering information about all structured types and entitysets referenced in the // query // (b) expanding views, navigate operators, and rewritting other type related operators // (c) gathering information about which subsequent phases may be requried // (d) pulling sort over project, and removing unnecessary sorts // (e) eliminates certain operations by translating them into equivalent subtrees // (ElementOp, NewMultisetOp) // namespace System.Data.Query.PlanCompiler { internal class DiscriminatorMapInfo { internal EntityTypeBase RootEntityType; internal bool IncludesSubTypes; internal ExplicitDiscriminatorMap DiscriminatorMap; internal DiscriminatorMapInfo(EntityTypeBase rootEntityType, bool includesSubTypes, ExplicitDiscriminatorMap discriminatorMap) { RootEntityType = rootEntityType; IncludesSubTypes = includesSubTypes; DiscriminatorMap = discriminatorMap; } ////// Merge the discriminatorMap info we just found with what we've already found. /// /// In practice, if either the current or the new map is from an OfTypeOnly view, we /// have to avoid the optimizations. /// /// If we have a new map that is a superset of the current map, then we can just swap /// the new map for the current one. /// /// If the current map is tha super set of the new one ther's nothing to do. /// /// (Of course, if neither has changed, then we really don't need to look) /// internal void Merge(EntityTypeBase neededRootEntityType, bool includesSubtypes, ExplicitDiscriminatorMap discriminatorMap) { // If what we've found doesn't exactly match what we are looking for we have more work to do if (RootEntityType != neededRootEntityType || IncludesSubTypes != includesSubtypes) { if (!IncludesSubTypes || !includesSubtypes) { // If either the original or the new map is from an of-type-only view we can't // merge, we just have to not optimize this case. DiscriminatorMap = null; } if (TypeSemantics.IsSubTypeOf(RootEntityType, neededRootEntityType)) { // we're asking for a super type of existing type, and what we had is a proper // subset of it -we can replace the existing item. RootEntityType = neededRootEntityType; DiscriminatorMap = discriminatorMap; } if (!TypeSemantics.IsSubTypeOf(neededRootEntityType, RootEntityType)) { // If either the original or the new map is from an of-type-only view we can't // merge, we just have to not optimize this case. DiscriminatorMap = null; } } } } ////// The PreProcessor module is responsible for performing any required preprocessing /// on the tree and gathering information before subsequent phases may be performed. /// internal class PreProcessor : SubqueryTrackingVisitor { #region private state // current nested view depth (0 for top-level query) private int m_viewNestingLevel = 0; // track referenced types, entitysets, entitycontainers, free floating entity constructor types // and types needing a null sentinel private HashSetm_referencedEntityContainers = new HashSet (); private HashSet m_referencedEntitySets = new HashSet (); private HashSet m_referencedTypes = new HashSet (); private HashSet m_freeFloatingEntityConstructorTypes = new HashSet (); private HashSet m_typesNeedingNullSentinel = new HashSet (); // helper for rel properties private RelPropertyHelper m_relPropertyHelper; // track discriminator metadata private bool m_suppressDiscriminatorMaps; private readonly Dictionary m_discriminatorMaps = new Dictionary (); #endregion #region constructors private PreProcessor(PlanCompiler planCompilerState) : base(planCompilerState) { m_relPropertyHelper = new RelPropertyHelper(m_command.MetadataWorkspace, m_command.ReferencedRelProperties); } #endregion #region public methods /// /// The driver routine. /// /// plan compiler state /// type information about all types/sets referenced in the query internal static void Process(PlanCompiler planCompilerState, out StructuredTypeInfo typeInfo) { PreProcessor preProcessor = new PreProcessor(planCompilerState); preProcessor.Process(); StructuredTypeInfo.Process(planCompilerState.Command, preProcessor.m_referencedTypes, preProcessor.m_referencedEntitySets, preProcessor.m_freeFloatingEntityConstructorTypes, preProcessor.m_suppressDiscriminatorMaps ? null : preProcessor.m_discriminatorMaps, preProcessor.m_relPropertyHelper, preProcessor.m_typesNeedingNullSentinel, out typeInfo); } #endregion #region private methods #region driver internal void Process() { m_command.Root = VisitNode(m_command.Root); // // Add any Vars that are of structured type - if the Vars aren't // referenced via a VarRefOp, we end up losing them... // foreach (Var v in m_command.Vars) { AddTypeReference(v.Type); } // // If we have any "structured" types, then we need to run through NTE // if (m_referencedTypes.Count > 0) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NTE); // // Find any structured types that are projected at the top level, and // ensure that we can handle their nullability. // PhysicalProjectOp ppOp = (PhysicalProjectOp)m_command.Root.Op; // this better be the case or we have other problems. ppOp.ColumnMap.Accept(StructuredTypeNullabilityAnalyzer.Instance, m_typesNeedingNullSentinel); } } #endregion #region private state maintenance - type and set information ////// Mark this EntitySet as referenced in the query /// /// private void AddEntitySetReference(EntitySet entitySet) { m_referencedEntitySets.Add(entitySet); if (!m_referencedEntityContainers.Contains(entitySet.EntityContainer)) { m_referencedEntityContainers.Add(entitySet.EntityContainer); } } ////// Mark this type as being referenced in the query, if it is a structured /// type or a collection of structured type /// /// type to reference private void AddTypeReference(TypeUsage type) { if (TypeUtils.IsStructuredType(type) || TypeUtils.IsCollectionType(type)) { m_referencedTypes.Add(type); } } ////// Get the list of relationshipsets that can hold instances of the given relationshiptype /// /// We identify the list of relationshipsets in the current list of entitycontainers that are /// of the given type. Since we don't yet support relationshiptype subtyping, this is a little /// easier than the entity version /// /// the relationship type to look for ///the list of relevant relationshipsets private ListGetRelationshipSets(RelationshipType relType) { List relSets = new List (); foreach (EntityContainer entityContainer in m_referencedEntityContainers) { foreach (EntitySetBase set in entityContainer.BaseEntitySets) { RelationshipSet relSet = set as RelationshipSet; if (relSet != null && relSet.ElementType.Equals(relType)) { relSets.Add(relSet); } } } return relSets; } /// /// Find all entitysets (that are reachable in the current query) that can hold instances that /// are *at least* of type "entityType". /// An entityset ES of type T1 can hold instances that are at least of type T2, if one of the following /// is true /// - T1 is a subtype of T2 /// - T2 is a subtype of T1 /// - T1 is equal to T2 /// /// the desired entity type ///list of all entitysets of the desired shape private ListGetEntitySets(TypeUsage entityType) { List sets = new List (); foreach (EntityContainer container in m_referencedEntityContainers) { foreach (EntitySetBase baseSet in container.BaseEntitySets) { EntitySet set = baseSet as EntitySet; if (set != null && (set.ElementType.Equals(entityType.EdmType) || TypeSemantics.IsSubTypeOf(entityType.EdmType, set.ElementType) || TypeSemantics.IsSubTypeOf(set.ElementType, entityType.EdmType))) { sets.Add(set); } } } return sets; } #endregion #region View Expansion /// /// Convert a CQT command into an IQT subtree. /// We expect the CQT command to be a query command tree. This is a 3-step /// process /// * We first run through the standard CQT-IQT convertor. /// * We then strip off the root of the IQT (the PhysicalProjectOp) /// * Finally, we copy the IQT into our current IQT /// /// When we have metadata caching of IQTs (for views), instead of CQTs, /// we can get rid of steps 1 and 2. /// /// the view ///an IQT subtree in the current command private Node ConvertToInternalTree(System.Data.Mapping.ViewGeneration.GeneratedView generatedView) { Node ret; Node sourceIqt = generatedView.GetInternalTree(m_command.MetadataWorkspace); ret = OpCopier.Copy(m_command, sourceIqt); return ret; } ////// Gets the "expanded" query mapping view for the specified C-Space entity set /// /// The current node /// The scanTableOp that references the entity set /// /// An optional type filter to apply to the generated view. /// Set tonull on return if the generated view renders the type filter superfluous. /// ///A node that is the root of the new expanded view private Node ExpandView(Node node, ScanTableOp scanTableOp, ref IsOfOp typeFilter) { EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent; PlanCompiler.Assert(entitySet != null, "The target of a ScanTableOp must reference an EntitySet to be used with ExpandView"); PlanCompiler.Assert(entitySet.EntityContainer.DataSpace == DataSpace.CSpace, "Store entity sets cannot have Query Mapping Views and should not be used with ExpandView"); if (typeFilter != null && !typeFilter.IsOfOnly && TypeSemantics.IsSubTypeOf(entitySet.ElementType, typeFilter.IsOfType.EdmType)) { // // If a type filter is being applied to the ScanTableOp, but that filter is asking // for all elements that are the same type or a supertype of the element type of the // target entity set, then the type filter is a no-op and can safely be discarded - // IF AND ONLY IF the type filter is 'OfType' - which includes subtypes - and NOT // 'IsOfOnly' - which requires an exact type match, and so does not include subtypes. // typeFilter = null; } // // Call the GetGeneratedView method to retrieve the query mapping view for the extent referenced // by the ScanTableOp. The actual method used to do this differs depending on whether the default // Query Mapping View is sufficient or a targeted view that only filters by element type is required. // System.Data.Mapping.ViewGeneration.GeneratedView definingQuery = null; EntityTypeBase requiredType = scanTableOp.Table.TableMetadata.Extent.ElementType; bool includeSubtypes = true; if (typeFilter != null) { // // A type filter is being applied to the ScanTableOp; it may be possible to produce // an optimized expansion of the view based on type-specific views generated for the // C-Space entity set. // The type for which the view should be tuned is the 'OfType' specified on the type filter. // If the type filter is an 'IsOfOnly' filter then the view should NOT include subtypes of the required type. // requiredType = (EntityTypeBase)typeFilter.IsOfType.EdmType; includeSubtypes = !typeFilter.IsOfOnly; if (m_command.MetadataWorkspace.TryGetGeneratedViewOfType(entitySet, requiredType, includeSubtypes, out definingQuery)) { // // At this point a type-specific view was found that satisifies the type filter's // constraints in terms of required type and whether subtypes should be included; // the type filter itself is now unnecessary and should be set to null indicating // that it can be safely removed (see ProcessScanTableOp and Visit(FilterOp) for this). // typeFilter = null; } } // // If a generated view has not been obtained at this point then either: // - A type filter was specified but no type-specific view exists that satisfies its constraints. // OR // - No type filter was specified. // In either case the default query mapping view for the referenced entity set should now be retrieved. // if (null == definingQuery) { definingQuery = m_command.MetadataWorkspace.GetGeneratedView(entitySet); } // // If even the default query mapping view was not found then we cannot continue. // This implies that the set was not mapped, which should not be allowed, therefore // a retail assert is used here instead of a regular exception. // PlanCompiler.Assert(definingQuery != null, Entity.Strings.ADP_NoQueryMappingView(entitySet.EntityContainer.Name, entitySet.Name)); // // At this point we're guaranteed to have found a defining query for the view. // We're now going to convert this into an IQT, and then copy it into our own IQT. // Node ret = ConvertToInternalTree(definingQuery); // // Make sure we're tracking what we've asked any discriminator maps to contain. // DetermineDiscriminatorMapUsage(ret, entitySet, requiredType, includeSubtypes); // // Build up a ScanViewOp to "cap" the defining query below // ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table); ret = m_command.CreateNode(scanViewOp, ret); return ret; } ////// If the discrminator map we're already tracking for this type (in this entityset) /// isn't already rooted at our required type, then we have to suppress the use of /// the descriminator maps when we constrct the structuredtypes; see SQLBUDT #615744 /// private void DetermineDiscriminatorMapUsage(Node viewNode, EntitySetBase entitySet, EntityTypeBase rootEntityType, bool includeSubtypes) { ExplicitDiscriminatorMap discriminatorMap = null; // we expect the view to be capped with a project; we're just being careful here. if (viewNode.Op.OpType == OpType.Project) { DiscriminatedNewEntityOp discriminatedNewEntityOp = viewNode.Child1.Child0.Child0.Op as DiscriminatedNewEntityOp; if (null != discriminatedNewEntityOp) { discriminatorMap = discriminatedNewEntityOp.DiscriminatorMap; } } DiscriminatorMapInfo discriminatorMapInfo; if (!m_discriminatorMaps.TryGetValue(entitySet, out discriminatorMapInfo)) { if (null == rootEntityType) { rootEntityType = entitySet.ElementType; includeSubtypes = true; } discriminatorMapInfo = new DiscriminatorMapInfo(rootEntityType, includeSubtypes, discriminatorMap); m_discriminatorMaps.Add(entitySet, discriminatorMapInfo); } else { discriminatorMapInfo.Merge(rootEntityType, includeSubtypes, discriminatorMap); } } #endregion #region NavigateOp rewrites ////// Rewrites a NavigateOp tree in the following fashion /// SELECT VALUE r.ToEnd /// FROM (SELECT VALUE r1 FROM RS1 as r1 /// UNION ALL /// SELECT VALUE r2 FROM RS2 as r2 /// ... /// SELECT VALUE rN FROM RSN as rN) as r /// WHERE r.FromEnd = sourceRef /// /// RS1, RS2 etc. are the set of all relationshipsets that can hold instances of the specified /// relationship type. "sourceRef" is the single (ref-type) argument to the NavigateOp that /// represents the from-end of the navigation traversal /// If the toEnd is multi-valued, then we stick a Collect(PhysicalProject( over the subquery above /// /// A couple of special cases. /// If no relationship sets can be found, we return a NULL (if the /// toEnd is single-valued), or an empty multiset (if the toEnd is multi-valued) /// /// If the toEnd is single-valued, *AND* the input Op is a GetEntityRefOp, then /// we convert the NavigateOp into a RelPropertyOp over the entity. /// /// the navigateOp tree /// the navigateOp /// the output var produced by the subquery (ONLY if the to-End is single-valued) ///the resulting node private Node RewriteNavigateOp(Node navigateOpNode, NavigateOp navigateOp, out Var outputVar) { outputVar = null; // // Currently, navigation of composition relationships is not supported. // if (!Helper.IsAssociationType(navigateOp.Relationship)) { throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_RelNav_NoCompositions); } // // If the input to the navigateOp is a GetEntityRefOp, and the navigation // is to the 1-end of the relationship, convert this into a RelPropertyOp instead - operating on the // input child to the GetEntityRefOp // if (navigateOpNode.Child0.Op.OpType == OpType.GetEntityRef && (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne || navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One)) { PlanCompiler.Assert(m_command.IsRelPropertyReferenced(navigateOp.RelProperty), "Unreferenced rel property? " + navigateOp.RelProperty); Op relPropertyOp = m_command.CreateRelPropertyOp(navigateOp.RelProperty); Node relPropertyNode = m_command.CreateNode(relPropertyOp, navigateOpNode.Child0.Child0); return relPropertyNode; } ListrelationshipSets = GetRelationshipSets(navigateOp.Relationship); // // Special case: when no relationshipsets can be found. Return NULL or an empty multiset, // depending on the multiplicity of the toEnd // if (relationshipSets.Count == 0) { // // If we're navigating to the 1-end of the relationship, then simply return a null constant // if (navigateOp.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many) { return m_command.CreateNode(m_command.CreateNullOp(navigateOp.Type)); } else // return an empty set { return m_command.CreateNode(m_command.CreateNewMultisetOp(navigateOp.Type)); } } // // Build up a UNION-ALL ladder over all the relationshipsets // List scanTableNodes = new List (); List scanTableVars = new List(); foreach (RelationshipSet relSet in relationshipSets) { TableMD tableMD = Command.CreateTableDefinition(relSet); ScanTableOp tableOp = m_command.CreateScanTableOp(tableMD); Node branchNode = m_command.CreateNode(tableOp); Var branchVar = tableOp.Table.Columns[0]; scanTableVars.Add(branchVar); scanTableNodes.Add(branchNode); } Node unionAllNode = null; Var unionAllVar; m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); // // Now build up the predicate // Node targetEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.ToEnd), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node sourceEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.FromEnd), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node predicateNode = m_command.BuildComparison(OpType.EQ, navigateOpNode.Child0, sourceEnd); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicateNode); Var projectVar; Node projectNode = m_command.BuildProject(filterNode, targetEnd, out projectVar); // // Finally, some magic about single-valued vs collection-valued ends // Node ret; if (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many) { ret = m_command.BuildCollect(projectNode, projectVar); } else { ret = projectNode; outputVar = projectVar; } return ret; } #endregion #region DerefOp Rewrites /// /// Build up a node tree that represents the set of instances from the given table that are at least /// of the specified type ("ofType"). If "ofType" is NULL, then all rows are returned /// /// Return the outputVar from the nodetree /// /// the entityset or relationshipset to scan over /// the element types we're interested in /// the output var produced by this node tree ///the node tree private Node BuildOfTypeTable(EntitySetBase entitySet, TypeUsage ofType, out Var resultVar) { TableMD tableMetadata = Command.CreateTableDefinition(entitySet); ScanTableOp tableOp = m_command.CreateScanTableOp(tableMetadata); Node tableNode = m_command.CreateNode(tableOp); Var tableVar = tableOp.Table.Columns[0]; Node resultNode; // // Build a logical "oftype" expression - simply a filter predicate // if ((ofType != null) && !entitySet.ElementType.EdmEquals(ofType.EdmType)) { m_command.BuildOfTypeTree(tableNode, tableVar, ofType, true, out resultNode, out resultVar); } else { resultNode = tableNode; resultVar = tableVar; } return resultNode; } ////// Produces a relop tree that "logically" produces the target of the derefop. In essence, this gets rewritten /// into /// SELECT VALUE e /// FROM (SELECT VALUE e0 FROM OFTYPE(ES0, T) as e0 /// UNION ALL /// SELECT VALUE e1 FROM OFTYPE(ES1, T) as e1 /// ... /// SELECT VALUE eN from OFTYPE(ESN, T) as eN)) as e /// WHERE REF(e) = myRef /// /// "T" is the target type of the Deref, and myRef is the (single) argument to the DerefOp /// /// ES0, ES1 etc. are all the EntitySets that could hold instances that are at least of type "T". We identify this list of sets /// by looking at all entitycontainers referenced in the query, and looking at all entitysets in those /// containers that are of the right type /// An EntitySet ES (of entity type X) can hold instances of T, if one of the following is true /// - T is a subtype of X /// - X is equal to T /// Our situation is a little trickier, since we also need to look for cases where X is a subtype of T. /// /// the derefOp subtree /// the derefOp /// output var produced ///the subquery described above private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar) { TypeUsage entityType = derefOp.Type; ListtargetEntitySets = GetEntitySets(entityType); if (targetEntitySets.Count == 0) { // We didn't find any entityset that could match this. Simply return a null-value outputVar = null; return m_command.CreateNode(m_command.CreateNullOp(entityType)); } List scanTableNodes = new List (); List scanTableVars = new List(); foreach (EntitySet entitySet in targetEntitySets) { Var tableVar; Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar); scanTableNodes.Add(tableNode); scanTableVars.Add(tableVar); } Node unionAllNode; Var unionAllVar; m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); // // Finally build up the key comparison predicate // Node entityRefNode = m_command.CreateNode( m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode); Node filterNode = m_command.CreateNode( m_command.CreateFilterOp(), unionAllNode, keyComparisonPred); outputVar = unionAllVar; return filterNode; } #endregion #region NavigationProperty Rewrites /// /// Find the entityset that corresponds to the specified end of the relationship. /// /// We must find one - else we assert. /// /// the relationshipset /// the destination end of the relationship traversal ///the entityset corresponding to the target end private static EntitySetBase FindTargetEntitySet(RelationshipSet relationshipSet, RelationshipEndMember targetEnd) { EntitySetBase entitySet = null; AssociationSet associationSet = (AssociationSet)relationshipSet; // find the corresponding entityset entitySet = null; foreach (AssociationSetEnd e in associationSet.AssociationSetEnds) { if (e.CorrespondingAssociationEndMember.EdmEquals(targetEnd)) { entitySet = e.EntitySet; break; } } PlanCompiler.Assert(entitySet != null, "Could not find entityset for relationshipset " + relationshipSet + ";association end " + targetEnd); return entitySet; } ////// Builds up a join between the relationshipset and the entityset corresponding to its toEnd. In essence, /// we produce /// SELECT r, e /// FROM RS as r, OFTYPE(ES, T) as e /// WHERE r.ToEnd = Ref(e) /// /// "T" is the entity type of the toEnd of the relationship. /// /// the relationshipset /// the toEnd of the relationship /// the var representing the relationship instance ("r") in the output subquery /// the var representing the entity instance ("e") in the output subquery ///the join subquery described above private Node BuildJoinForNavProperty(RelationshipSet relSet, RelationshipEndMember end, out Var rsVar, out Var esVar) { EntitySetBase entitySet = FindTargetEntitySet(relSet, end); // // Build out the ScanTable ops for the relationshipset and the entityset. Add the // Node asTableNode = BuildOfTypeTable(relSet, null, out rsVar); Node esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar); // // Build up a join between the entityset and the associationset; join on the to-end // Node joinPredicate = m_command.BuildComparison(OpType.EQ, m_command.CreateNode(m_command.CreateGetEntityRefOp(end.TypeUsage), m_command.CreateNode(m_command.CreateVarRefOp(esVar))), m_command.CreateNode(m_command.CreatePropertyOp(end), m_command.CreateNode(m_command.CreateVarRefOp(rsVar))) ); Node joinNode = m_command.CreateNode(m_command.CreateInnerJoinOp(), asTableNode, esTableNode, joinPredicate); return joinNode; } ////// Rewrite a NavPropertyOp when the target end of the nav property has multiplicity /// of one (or zero..one). /// We simply pick up the corresponding rel property from the input entity, and /// apply a deref operation /// NavProperty(e, n) => deref(relproperty(e, r)) /// where e is the entity expression, n is the nav-property, and r is the corresponding /// rel-property /// /// the rel-property describing the navigation /// entity instance that we're starting the traversal from /// type of the target entity ///a rewritten subtree private Node RewriteToOneNavigationProperty(RelProperty relProperty, Node sourceEntityNode, TypeUsage resultType) { RelPropertyOp relPropertyOp = m_command.CreateRelPropertyOp(relProperty); Node relPropertyNode = m_command.CreateNode(relPropertyOp, sourceEntityNode); DerefOp derefOp = m_command.CreateDerefOp(resultType); Node derefNode = m_command.CreateNode(derefOp, relPropertyNode); return derefNode; } ////// Rewrite a NavigationProperty when the relationship is a 1:N relationship. /// In essence, we find all the relevant target entitysets, and then compare the /// rel-property on the target end with the source ref /// /// Converts /// NavigationProperty(e, r) /// into /// SELECT VALUE t /// FROM (SELECT VALUE e1 FROM ES1 as e1 /// UNION ALL /// SELECT VALUE e2 FROM ES2 as e2 /// UNION ALL /// ... /// ) as t /// WHERE RelProperty(t, r') = GetEntityRef(e) /// /// r' is the inverse-relproperty for r /// /// We also build out a CollectOp over the subquery above, and return that /// /// the rel-property describing the relationship traversal /// the list of relevant relationshipsets /// node tree corresponding to the source entity ref /// type of the result ///the rewritten subtree private Node RewriteOneToManyNavigationProperty(RelProperty relProperty, ListrelationshipSets, Node sourceRefNode, TypeUsage resultType) { PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here"); PlanCompiler.Assert(relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many, "Expected source end multiplicity to be one. Found 'Many' instead " + relProperty); Node ret = null; // // We convert the // TypeUsage entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage); List scanTableNodes = new List (relationshipSets.Count); List scanTableVars = new List(relationshipSets.Count); foreach (RelationshipSet r in relationshipSets) { EntitySetBase entitySet = FindTargetEntitySet(r, relProperty.ToEnd); Var tableVar; Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar); scanTableNodes.Add(tableNode); scanTableVars.Add(tableVar); } // // Build the union-all node // Node unionAllNode; Var unionAllVar; m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar); // // Now build up the appropriate filter. Select out the relproperty from the other end // RelProperty inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd); PlanCompiler.Assert(m_command.IsRelPropertyReferenced(inverseRelProperty), "Unreferenced rel property? " + inverseRelProperty); Node inverseRelPropertyNode = m_command.CreateNode( m_command.CreateRelPropertyOp(inverseRelProperty), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar))); Node predicateNode = m_command.BuildComparison(OpType.EQ, sourceRefNode, inverseRelPropertyNode); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicateNode); // // The magic of collections... // ret = m_command.BuildCollect(filterNode, unionAllVar); return ret; } /// /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r)) /// where "r" is a many-to-many relationship /// /// We essentially produce the following subquery /// SELECT VALUE x.e /// FROM (SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1) /// UNION ALL /// SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1) /// ... /// ) as x /// WHERE x.r.FromEnd = sourceRef /// /// RS1, RS2 etc. are the relevant relationshipsets /// ES1, ES2 etc. are the corresponding entitysets for the toEnd of the relationship /// sourceRef is the ref argument /// T is the type of the target-end of the relationship /// /// We then build a CollectOp over the subquery above /// /// the rel property to traverse /// list of relevant relationshipsets /// source ref /// type of the result ///private Node RewriteManyToManyNavigationProperty(RelProperty relProperty, List relationshipSets, Node sourceRefNode, TypeUsage resultType) { PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here"); PlanCompiler.Assert(relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many && relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many, "Expected target end multiplicity to be 'many'. Found " + relProperty + "; multiplicity = " + relProperty.ToEnd.RelationshipMultiplicity); Node ret = null; List joinNodes = new List (relationshipSets.Count); List outputVars = new List(relationshipSets.Count * 2); foreach (RelationshipSet r in relationshipSets) { Var rsVar; Var esVar; Node joinNode = BuildJoinForNavProperty(r, relProperty.ToEnd, out rsVar, out esVar); joinNodes.Add(joinNode); outputVars.Add(rsVar); outputVars.Add(esVar); } // // Build the union-all node // Node unionAllNode; IList unionAllVars; m_command.BuildUnionAllLadder(joinNodes, outputVars, out unionAllNode, out unionAllVars); // // Now build out the filterOp over the left-side var // Node rsSourceRefNode = m_command.CreateNode(m_command.CreatePropertyOp(relProperty.FromEnd), m_command.CreateNode(m_command.CreateVarRefOp(unionAllVars[0]))); Node predicate = m_command.BuildComparison(OpType.EQ, sourceRefNode, rsSourceRefNode); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), unionAllNode, predicate); // // Finally, build out a project node that only projects out the entity side // Node projectNode = m_command.BuildProject(filterNode, new Var[] { unionAllVars[1] }, new Node[] { }); // // Build a collectOp over the project node // ret = m_command.BuildCollect(projectNode, unionAllVars[1]); return ret; } /// /// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r)) /// /// We handle three cases here, depending on the kind of relationship we're /// dealing with. /// - *:1 relationships /// - N:1 relationships /// - N:M relationships /// /// /// the navigation property /// the input ref to start the traversal /// the result type of the expression ///the rewritten tree private Node RewriteNavigationProperty(NavigationProperty navProperty, Node sourceEntityNode, TypeUsage resultType) { Node ret = null; RelProperty relProperty = new RelProperty(navProperty.RelationshipType, navProperty.FromEndMember, navProperty.ToEndMember); PlanCompiler.Assert(m_command.IsRelPropertyReferenced(relProperty) || (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many), "Unreferenced rel property? " + relProperty); // // Case 1: The (target end of the) nav property has a multiplicity of 1 (or 0..1) // (doesn't matter what the sourceEnd multiplicity is) // if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One || relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne) { ret = RewriteToOneNavigationProperty(relProperty, sourceEntityNode, resultType); return ret; } // // Otherwise, the target end is multi-valued. We need to deal with // 2 cases here. A N:1 relationship or a N:M relationship // // // Find the list of all relationships that could satisfy this relationship // If we find no matching relationship set, simply return an empty collection // ListrelationshipSets = GetRelationshipSets(relProperty.Relationship); if (relationshipSets.Count == 0) { // return an empty set return m_command.CreateNode(m_command.CreateNewMultisetOp(resultType)); } // // Build out a ref over the source entity now // Node sourceRefNode = m_command.CreateNode( m_command.CreateGetEntityRefOp(relProperty.FromEnd.TypeUsage), sourceEntityNode); // // Are we dealing with a many-to-many relationship ? // if (relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many) { ret = RewriteManyToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType); } else { ret = RewriteOneToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType); } return ret; } #endregion #region visitor methods #region ScalarOps /// /// Default handler for scalar Ops. Simply traverses the children, /// and also identifies any structured types along the way /// /// the ScalarOp /// current subtree ///the possibly modified node protected override Node VisitScalarOpDefault(ScalarOp op, Node n) { VisitChildren(n); // visit my children // keep track of referenced types AddTypeReference(op.Type); return n; } ////// Rewrite a DerefOp subtree. We have two cases to consider here. /// We call RewriteDerefOp to return a subtree (and an optional outputVar). /// If the outputVar is null, then we simply return the subtree produced by those calls. /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar /// in its place. /// /// As an example, /// select deref(e) from T /// gets rewritten into /// select v from T OuterApply X /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X /// /// /// the derefOp /// the deref subtree ///the rewritten tree public override Node Visit(DerefOp op, Node n) { Var outputVar; VisitScalarOpDefault(op, n); Node ret = RewriteDerefOp(n, op, out outputVar); ret = VisitNode(ret); if (outputVar != null) { ret = AddSubqueryToParentRelOp(outputVar, ret); } return ret; } ////// Processing for an ElementOp. Replaces this by the corresponding Var from /// the subquery, and adds the subquery to the list of currently tracked subqueries /// /// the elementOp /// current subtree ///the Var from the subquery public override Node Visit(ElementOp op, Node n) { VisitScalarOpDefault(op, n); // default processing // get to the subquery... Node subQueryRelOp = n.Child0; ProjectOp projectOp = (ProjectOp)subQueryRelOp.Op; PlanCompiler.Assert(projectOp.Outputs.Count == 1, "input to ElementOp has more than one output var?"); Var projectVar = projectOp.Outputs.First; Node ret = AddSubqueryToParentRelOp(projectVar, subQueryRelOp); return ret; } ////// Mark Normalization as needed /// /// /// ///public override Node Visit(ExistsOp op, Node n) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization); return base.Visit(op, n); } /// /// If this is TVF or a collection aggregate function NestPullUp and Normalization are needed /// /// /// ///public override Node Visit(FunctionOp op, Node n) { // If this is TVF or a collection aggregate function NestPullUp and Normalization are needed if (TypeSemantics.IsCollectionType(op.Type) || PlanCompilerUtil.IsCollectionAggregateFunction(op, n)) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup); m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization); } return base.Visit(op, n); } /// /// Default processing. /// In addition, if the case statement is of the shape /// case when X then NULL else Y, or /// case when X then Y else NULL, /// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same, /// marks that type as needing a null sentinel. /// This allows in NominalTypeElimination the case op to be pushed inside Y's null sentinel. /// /// /// ///public override Node Visit(CaseOp op, Node n) { VisitScalarOpDefault(op, n); //special handling to enable optimization bool thenClauseIsNull; if (PlanCompilerUtil.IsRowTypeCaseOpWithNullability(op, n, out thenClauseIsNull)) { //Add a null sentinel for the row type m_typesNeedingNullSentinel.Add(op.Type.EdmType.Identity); } return n; } /// /// Special processing for ConditionalOp is handled by /// /// ////// public override Node Visit(ConditionalOp op, Node n) { VisitScalarOpDefault(op, n); ProcessConditionalOp(op, n); return n; } /// /// If it is a IsNull op over a row type or a complex type mark the type as needing a null sentinel. /// /// /// private void ProcessConditionalOp(ConditionalOp op, Node n) { if (op.OpType == OpType.IsNull && TypeSemantics.IsRowType(n.Child0.Op.Type) || TypeSemantics.IsComplexType(n.Child0.Op.Type)) { StructuredTypeNullabilityAnalyzer.MarkAsNeedingNullSentinel(m_typesNeedingNullSentinel, n.Child0.Op.Type); } } #region PropertyOp Handling ////// Validates that the nav property agrees with the underlying relationship /// /// the Nav PropertyOp /// the subtree private void ValidateNavPropertyOp(PropertyOp op, Node n) { NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo; // // If the result of the expanded form of the navigation property is not compatible with // the declared type of the property, then the navigation property is invalid in the // context of this command tree's metadata workspace. // TypeUsage resultType = navProperty.ToEndMember.TypeUsage; if (TypeSemantics.IsReferenceType(resultType)) { resultType = TypeHelpers.GetElementTypeUsage(resultType); } if (navProperty.ToEndMember.RelationshipMultiplicity == RelationshipMultiplicity.Many) { resultType = TypeUsage.Create(resultType.EdmType.GetCollectionType()); } if (!TypeSemantics.IsStructurallyEqualOrPromotableTo(resultType, op.Type)) { throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_IncompatibleNavigationPropertyResult( navProperty.DeclaringType.FullName, navProperty.Name ) ); } } ////// Rewrite a PropertyOp subtree for a nav property /// /// We call RewriteNavigationPropertyOp to return a subtree (and an /// optional outputVar). If the outputVar is null, then we simply return the subtree produced by those calls. /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar /// in its place. /// /// As an example, /// select e.NP from T /// gets rewritten into /// select v from T OuterApply X /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X /// /// the PropertyOp /// the current node ///the rewritten subtree private Node VisitNavPropertyOp(PropertyOp op, Node n) { ValidateNavPropertyOp(op, n); // // This is a bit weird. Ideally, I would always visit the child first (ie) a bottom-up traversal, // but there's some weird gotchas in the elinq tests ("SelectManyNullResult531057") // bool visitChildFirst = (n.Child0.Op.OpType != OpType.Property); if (visitChildFirst) { VisitScalarOpDefault(op, n); } NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo; Node ret = RewriteNavigationProperty(navProperty, n.Child0, op.Type); ret = VisitNode(ret); return ret; } ////// Rewrite a PropertyOp subtree. /// /// If the PropertyOp represents a simple property (ie) not a navigation property, we simply call /// VisitScalarOpDefault() and return. Otherwise, we call VisitNavPropertyOp and return the result from /// that function /// /// /// the PropertyOp /// the PropertyOp subtree ///the rewritten tree public override Node Visit(PropertyOp op, Node n) { Node ret; if (Helper.IsNavigationProperty(op.PropertyInfo)) { ret = VisitNavPropertyOp(op, n); } else { ret = VisitScalarOpDefault(op, n); } return ret; } #endregion ////// Handler for a RefOp. /// Keeps track of the entityset /// /// the RefOp /// current RefOp subtree ///current subtree public override Node Visit(RefOp op, Node n) { VisitScalarOpDefault(op, n); // use default processing AddEntitySetReference(op.EntitySet); // add to list of references return n; } ////// Handler for a TreatOp. /// Rewrites the operator if the argument is guaranteed to be of type /// op. /// /// Current TreatOp /// Current subtree ///Current subtree public override Node Visit(TreatOp op, Node n) { n = base.Visit(op, n); // See if TreatOp can be rewritten (if it's not polymorphic) if (CanRewriteTypeTest(op.Type.EdmType, n.Child0.Op.Type.EdmType)) { // Return argument directly (if the argument is null, 'treat as' also returns null; // if the argument is not null, it's guaranteed to be of the correct type) return n.Child0; } return n; } ////// Handler for an IsOfOp. /// Keeps track of the IsOfType (if it is a structured type) and rewrites the /// operator if the argument is guaranteed to be of type op.IsOfType /// /// Current IsOfOp /// Current subtree ///Current subtree public override Node Visit(IsOfOp op, Node n) { n = VisitScalarOpDefault(op, n); // default handling first // keep track of any structured types AddTypeReference(op.IsOfType); // See if the IsOfOp can be rewritten (if it's not polymorphic) if (CanRewriteTypeTest(op.IsOfType.EdmType, n.Child0.Op.Type.EdmType)) { n = RewriteIsOfAsIsNull(op, n); } // For IsOfOnly(abstract type), suppress DiscriminatorMaps since no explicit type id is available for // abstract types. if (op.IsOfOnly && op.IsOfType.EdmType.Abstract) { m_suppressDiscriminatorMaps = true; } return n; } // Determines whether a type test expression can be rewritten. Returns true of the // argument type is guaranteed to implement "testType" (if the argument is non-null). private bool CanRewriteTypeTest(EdmType testType, EdmType argumentType) { // The rewrite only proceeds if the types are the same. If they are not, // it suggests either that the input result is polymorphic (in which case if OfType // should be preserved) or the types are incompatible (which is caught // elsewhere) if (!testType.EdmEquals(argumentType)) { return false; } // If the IsOfType is non-polymorphic (no base or derived types) the rewrite // is possible. if (null != testType.BaseType) { return false; } // Count sub types int subTypeCount = 0; foreach (EdmType subType in MetadataHelper.GetTypeAndSubtypesOf(testType, m_command.MetadataWorkspace, true /*includeAbstractTypes*/)) { subTypeCount++; if (2 == subTypeCount) { break; } } return 1 == subTypeCount; // no children types } // Translates // 'R is of T' // to // '(case when not (R is null) then True else null end) = True' // // Input requirements: // // - IsOfOp and argument to same must be in the same hierarchy. // - IsOfOp and argument must have the same type // - IsOfOp.IsOfType may not have super- or sub- types (validate // using CanRewriteTypeTest) // // Design requirements: // // - Must return true if the record exists // - Must return null if it does not // - Must be in predicate form to avoid confusing SQL gen // // The translation assumes R is of T when R is non null. private Node RewriteIsOfAsIsNull(IsOfOp op, Node n) { // construct 'R is null' predicate ConditionalOp isNullOp = m_command.CreateConditionalOp(OpType.IsNull); Node isNullNode = m_command.CreateNode(isNullOp, n.Child0); // Process the IsNull node to make sure a null sentinel gets added if needed ProcessConditionalOp(isNullOp, isNullNode); // construct 'not (R is null)' predicate ConditionalOp notOp = m_command.CreateConditionalOp(OpType.Not); Node notNode = m_command.CreateNode(notOp, isNullNode); // construct 'True' result ConstantBaseOp trueOp = m_command.CreateConstantOp(op.Type, true); Node trueNode = m_command.CreateNode(trueOp); // construct 'null' default result NullOp nullOp = m_command.CreateNullOp(op.Type); Node nullNode = m_command.CreateNode(nullOp); // create case statement CaseOp caseOp = m_command.CreateCaseOp(op.Type); Node caseNode = m_command.CreateNode(caseOp, notNode, trueNode, nullNode); // create 'case = true' operator ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ); Node equalsNode = m_command.CreateNode(equalsOp, caseNode, trueNode); return equalsNode; } ////// Rewrite a NavigateOp subtree. /// We call RewriteNavigateOp to return a subtree (and an optional outputVar). /// If the outputVar is null, then we simply return the subtree produced by those calls. /// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar /// in its place. /// /// As an example, /// select navigate(e) from T /// gets rewritten into /// select v from T OuterApply X /// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X /// /// /// the navigateOp /// the navigateOp subtree ///the rewritten tree public override Node Visit(NavigateOp op, Node n) { VisitScalarOpDefault(op, n); Var outputVar; Node ret = RewriteNavigateOp(n, op, out outputVar); ret = VisitNode(ret); // Move subquery to parent relop if necessary if (outputVar != null) { ret = AddSubqueryToParentRelOp(outputVar, ret); } return ret; } ////// Find the "current" enclosing entityset /// ///the enclosing entityset (if any) private EntitySetBase FindEnclosingEntitySetView() { if (m_viewNestingLevel == 0) { return null; } // // Walk up the stack of ancestors until we find the appropriate ScanViewOp // foreach (Node n in m_ancestors) { if (n.Op.OpType == OpType.ScanView) { ScanViewOp op = (ScanViewOp)n.Op; return op.Table.TableMetadata.Extent; } } PlanCompiler.Assert(false, "found no enclosing view - but view-nesting level is greater than zero"); return null; } ////// Find the relationshipset that matches the current entityset + from/to roles /// /// /// ///private RelationshipSet FindRelationshipSet(EntitySetBase entitySet, RelProperty relProperty) { foreach (EntitySetBase es in entitySet.EntityContainer.BaseEntitySets) { AssociationSet rs = es as AssociationSet; if (rs != null && rs.ElementType.EdmEquals(relProperty.Relationship) && rs.AssociationSetEnds[relProperty.FromEnd.Identity].EntitySet.EdmEquals(entitySet)) { return rs; } } return null; } /// /// Find the position of a property in a type. /// Positions start at zero, and a supertype's properties precede the current /// type's properties /// /// the type in question /// the member to lookup ///the position of the member in the type (0-based) private int FindPosition(EdmType type, EdmMember member) { int pos = 0; foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(type)) { if (m.EdmEquals(member)) { return pos; } pos++; } PlanCompiler.Assert(false, "Could not find property " + member + " in type " + type.Name); return -1; } ////// Build out an expression (NewRecord) that corresponds to the key properties /// of the passed-in entity constructor /// /// This function simply looks up the key properties of the entity type, and then /// identifies the arguments to the constructor corresponding to those /// properties, and then slaps on a record wrapper over those expressions. /// /// No copies/clones are performed. That's the responsibility of the caller /// /// /// the entity constructor op /// the corresponding subtree ///the key expression private Node BuildKeyExpressionForNewEntityOp(Op op, Node n) { PlanCompiler.Assert(op.OpType == OpType.NewEntity || op.OpType == OpType.DiscriminatedNewEntity, "BuildKeyExpression: Unexpected OpType:" + op.OpType); int offset = (op.OpType == OpType.DiscriminatedNewEntity) ? 1 : 0; EntityTypeBase entityType = (EntityTypeBase)op.Type.EdmType; ListkeyFields = new List (); List > keyFieldTypes = new List >(); foreach (EdmMember k in entityType.KeyMembers) { int pos = FindPosition(entityType, k) + offset; PlanCompiler.Assert(n.Children.Count > pos, "invalid position " + pos + "; total count = " + n.Children.Count); keyFields.Add(n.Children[pos]); keyFieldTypes.Add(new KeyValuePair (k.Name, k.TypeUsage)); } TypeUsage keyExprType = TypeHelpers.CreateRowTypeUsage(keyFieldTypes, true); NewRecordOp keyOp = m_command.CreateNewRecordOp(keyExprType); Node keyNode = m_command.CreateNode(keyOp, keyFields); return keyNode; } /// /// Build out an expression corresponding to the rel-property. /// /// We create a subquery that looks like /// (select r /// from RS r /// where GetRefKey(r.FromEnd) = myKey) /// /// RS is the single relationship set that corresponds to the given entityset/rel-property pair /// FromEnd - is the source end of the relationship /// myKey - is the key expression of the entity being constructed /// /// NOTE: We always clone "myKey" before use. /// /// We then convert it into a scalar subquery, and extract out the ToEnd property from /// the output var of the subquery. (Should we do this inside the subquery itself?) /// /// If no single relationship-set is found, we return a NULL instead. /// /// entity set that logically holds instances of the entity we're building /// the rel-property we're trying to build up /// the "key" of the entity instance ///the rel-property expression private Node BuildRelPropertyExpression(EntitySetBase entitySet, RelProperty relProperty, Node keyExpr) { // // Make a copy of the current key expression // keyExpr = OpCopier.Copy(m_command, keyExpr); // // Find the relationship set corresponding to this entityset (and relProperty) // Return a null ref, if we can't find one // RelationshipSet relSet = FindRelationshipSet(entitySet, relProperty); if (relSet == null) { return m_command.CreateNode(m_command.CreateNullOp(relProperty.ToEnd.TypeUsage)); } ScanTableOp scanTableOp = m_command.CreateScanTableOp(Command.CreateTableDefinition(relSet)); PlanCompiler.Assert(scanTableOp.Table.Columns.Count == 1, "Unexpected column count for table:" + scanTableOp.Table.TableMetadata.Extent + "=" + scanTableOp.Table.Columns.Count); Var scanTableVar = scanTableOp.Table.Columns[0]; Node scanNode = m_command.CreateNode(scanTableOp); Node sourceEndNode = m_command.CreateNode( m_command.CreatePropertyOp(relProperty.FromEnd), m_command.CreateNode(m_command.CreateVarRefOp(scanTableVar))); Node predicateNode = m_command.BuildComparison(OpType.EQ, keyExpr, m_command.CreateNode(m_command.CreateGetRefKeyOp(keyExpr.Op.Type), sourceEndNode)); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), scanNode, predicateNode); // // Process the node, and then add this as a subquery to the parent relop // Node ret = VisitNode(filterNode); ret = AddSubqueryToParentRelOp(scanTableVar, ret); // // Now extract out the target end property // ret = m_command.CreateNode( m_command.CreatePropertyOp(relProperty.ToEnd), ret); return ret; } ////// Given an entity constructor (NewEntityOp, DiscriminatedNewEntityOp), build up /// the list of rel-property expressions. /// /// Walks through the list of relevant rel-properties, and builds up expressions /// (using BuildRelPropertyExpression) for each rel-property that does not have /// an expression already built (preBuiltExpressions) /// /// entity set that holds instances of the entity we're building /// the list of relevant rel-properties for this entity type /// the prebuilt rel-property expressions /// the key of the entity instance ///a list of rel-property expressions (lines up 1-1 with 'relPropertyList') private IEnumerableBuildAllRelPropertyExpressions(EntitySetBase entitySet, List relPropertyList, Dictionary prebuiltExpressions, Node keyExpr) { foreach (RelProperty r in relPropertyList) { Node relPropNode; if (!prebuiltExpressions.TryGetValue(r, out relPropNode)) { relPropNode = BuildRelPropertyExpression(entitySet, r, keyExpr); } yield return relPropNode; } } /// /// Handler for NewEntityOp. /// If this is an EntityConstructor, and the current view nesting level is 0 /// (ie) this is an EntityConstructor at the top-level query, then add /// the type to the list of "free-floating" entity constructor types /// /// the NewEntityOp /// the node tree corresponding to the op ///rewritten tree public override Node Visit(NewEntityOp op, Node n) { // Note: We don't do the default processing first to avoid adding references to types and entity sets // that may only be used in pre-build rel property expressions that may not be needed. EntityType entityType = op.Type.EdmType as EntityType; EntitySetBase entitySet = FindEnclosingEntitySetView(); if (entitySet == null) { if (entityType != null) { m_freeFloatingEntityConstructorTypes.Add(entityType); } // SQLBUDT #546546: Qmv/Umv tests Assert and throws in plan compiler in association tests. // If this Entity constructor is not within a view then there should not be any RelProps // specified on the NewEntityOp - the eSQL WITH RELATIONSHIPS clause that would cause such // RelProps to be added is only enabled when parsing in the user or generated view mode. PlanCompiler.Assert(op.RelationshipProperties == null || op.RelationshipProperties.Count == 0, "Related Entities cannot be specified for Entity constructors that are not part of the Query Mapping View for an Entity Set."); VisitScalarOpDefault(op, n); return n; } // // Find the relationship properties for this entitytype (and entity set) // ListrelProperties = new List (m_relPropertyHelper.GetRelProperties(entityType)); // Remove pre-build rel property expressions that would not be needed to avoid // unnecessary adding references to types and entity sets during default processing int j = op.RelationshipProperties.Count - 1; List copiedRelPropList = new List (op.RelationshipProperties); for (int i = n.Children.Count - 1; i >= entityType.Properties.Count; i--, j--) { if (!relProperties.Contains(op.RelationshipProperties[j])) { n.Children.RemoveAt(i); copiedRelPropList.RemoveAt(j); } } //Default processing VisitScalarOpDefault(op, n); // // Ok, now, I have to build out some relationship properties that // haven't been specified // Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n); // // Find the list of rel properties that have already been specified // Dictionary prebuiltRelPropertyExprs = new Dictionary (); j = 0; for (int i = entityType.Properties.Count; i < n.Children.Count; i++, j++) { prebuiltRelPropertyExprs[copiedRelPropList[j]] = n.Children[i]; } // // Fill in the missing pieces // // // Next, rebuild the list of children - includes expressions for each rel property // List newChildren = new List (); for (int i = 0; i < entityType.Properties.Count; i++) { newChildren.Add(n.Children[i]); } foreach (Node relPropNode in BuildAllRelPropertyExpressions(entitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) { newChildren.Add(relPropNode); } // // finally, build out the newOp // Op newEntityOp = m_command.CreateNewEntityOp(op.Type, relProperties, entitySet); Node newNode = m_command.CreateNode(newEntityOp, newChildren); return newNode; } /// /// Tracks discriminator metadata so that is can be used when constructing /// StructuredTypeInfo. /// public override Node Visit(DiscriminatedNewEntityOp op, Node n) { HashSetrelPropertyHashSet = new HashSet (); List relProperties = new List (); // // add references to each type produced by this node // Also, get the set of rel-properties for each of the types // foreach (var discriminatorTypePair in op.DiscriminatorMap.TypeMap) { EntityTypeBase entityType = discriminatorTypePair.Value; AddTypeReference(TypeUsage.Create(entityType)); foreach (RelProperty relProperty in m_relPropertyHelper.GetRelProperties(entityType)) { relPropertyHashSet.Add(relProperty); } } relProperties = new List (relPropertyHashSet); VisitScalarOpDefault(op, n); // // Now build out the set of missing rel-properties (if any) // // first, build the key expression Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n); List newChildren = new List (); int firstRelPropertyNodeOffset = n.Children.Count - op.RelationshipProperties.Count; for (int i = 0; i < firstRelPropertyNodeOffset; i++) { newChildren.Add(n.Children[i]); } // // Find the list of rel properties that have already been specified // Dictionary prebuiltRelPropertyExprs = new Dictionary (); for (int i = firstRelPropertyNodeOffset, j = 0; i < n.Children.Count; i++, j++) { prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i]; } // // Fill in the missing pieces // foreach (Node relPropNode in BuildAllRelPropertyExpressions(op.EntitySet, relProperties, prebuiltRelPropertyExprs, keyExpr)) { newChildren.Add(relPropNode); } Op newEntityOp = m_command.CreateDiscriminatedNewEntityOp(op.Type, op.DiscriminatorMap, op.EntitySet, relProperties); Node newNode = m_command.CreateNode(newEntityOp, newChildren); return newNode; } /// /// Handles a newMultiset constructor. Converts this into /// select a from dual union all select b from dual union all ... /// Handles a NewMultiset constructor, i.e. {x, y, z} /// 1. Empty multiset constructors are simply converted into: /// /// select x from singlerowtable as x where false /// /// 2. Mulltset constructors with only one element or with multiple elements all of /// which are constants or nulls are converted into: /// /// select x from dual union all select y from dual union all select z /// /// 3. All others are converted into: /// /// select case when d = 0 then x when d = 1 then y else z end /// from ( select 0 as d from single_row_table /// union all /// select 1 as d from single_row_table /// union all /// select 2 as d from single_row_table ) /// /// NOTE: The translation for 2 is valid for 3 too. We choose different translation /// in order to avoid correlation inside the union all, /// which would prevent us from removing apply operators /// /// Do this before processing the children, and then /// call Visit on the result to handle the elements /// /// the new instance op /// the current subtree ///the modified subtree public override Node Visit(NewMultisetOp op, Node n) { Node resultNode = null; Var resultVar = null; CollectionType collectionType = TypeHelpers.GetEdmType(op.Type); // // Empty multiset constructors are simply converted into // Project(Filter(SingleRowTableOp(), false) // if (!n.HasChild0) { Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), singleRowTableNode, m_command.CreateNode(m_command.CreateFalseOp())); Node fakeChild = m_command.CreateNode(m_command.CreateNullOp(collectionType.TypeUsage)); Var newVar; Node projectNode = m_command.BuildProject(filterNode, fakeChild, out newVar); resultNode = projectNode; resultVar = newVar; } // // Multiset constructors with only one elment or with multiple elments all of // which are constants or nulls are converted into: // // UnionAll(Project(SingleRowTable, e1), Project(SingleRowTable, e2), ...) // // The degenerate case when the collection has only one element does not require an // outer unionAll node // else if (n.Children.Count == 1 || AreAllConstantsOrNulls(n.Children)) { List inputNodes = new List (); List inputVars = new List(); foreach (Node chi in n.Children) { Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); Var newVar; Node projectNode = m_command.BuildProject(singleRowTableNode, chi, out newVar); inputNodes.Add(projectNode); inputVars.Add(newVar); } // Build the union-all ladder m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar); } // // All other cases: // // select case when d = 0 then x when d = 1 then y else z end // from ( select 0 as d from single_row_table // union all // select 1 as d from single_row_table // union all // select 2 as d from single_row_table ) // else { List inputNodes = new List (); List inputVars = new List(); //Create the union all lather first for (int i = 0; i < n.Children.Count; i++) { Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp()); // the discriminator for this branch Node discriminatorNode = m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.IntegerType, i)); Var newVar; Node projectNode = m_command.BuildProject(singleRowTableNode, discriminatorNode, out newVar); inputNodes.Add(projectNode); inputVars.Add(newVar); } // Build the union-all ladder now m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar); //Now create the case statement for the projection List caseArgNodes = new List (n.Children.Count * 2 + 1); for (int i = 0; i < n.Children.Count; i++) { //For all but the last we need a when if (i != (n.Children.Count - 1)) { ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ); Node whenNode = m_command.CreateNode(equalsOp, m_command.CreateNode(m_command.CreateVarRefOp(resultVar)), m_command.CreateNode( m_command.CreateConstantOp(m_command.IntegerType, i))); caseArgNodes.Add(whenNode); } //Add the then/else node caseArgNodes.Add(n.Children[i]); } //Create the project Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(collectionType.TypeUsage), caseArgNodes); resultNode = m_command.BuildProject(resultNode, caseNode, out resultVar); } // So, I've finally built up a complex query corresponding to the constructor. // Now, cap this with a physicalprojectOp, and then with a CollectOp PhysicalProjectOp physicalProjectOp = m_command.CreatePhysicalProjectOp(resultVar); Node physicalProjectNode = m_command.CreateNode(physicalProjectOp, resultNode); CollectOp collectOp = m_command.CreateCollectOp(op.Type); Node collectNode = m_command.CreateNode(collectOp, physicalProjectNode); return VisitNode(collectNode); } /// /// Returns true if each node in the list is either a constant or a null /// /// ///private bool AreAllConstantsOrNulls(List nodes) { foreach (Node node in nodes) { if (node.Op.OpType != OpType.Constant && node.Op.OpType != OpType.Null) { return false; } } return true; } /// /// Default processing for a CollectOp. But make sure that we /// go through the NestPullUp phase /// /// /// ///public override Node Visit(CollectOp op, Node n) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup); return VisitScalarOpDefault(op, n); } #endregion #region RelOps private void HandleTableOpMetadata(ScanTableBaseOp op) { // add to the list of referenced entitysets EntitySet entitySet = op.Table.TableMetadata.Extent as EntitySet; if (entitySet != null) { AddEntitySetReference(entitySet); } TypeUsage elementType = TypeUsage.Create(op.Table.TableMetadata.Extent.ElementType); // add to the list of structured types AddTypeReference(elementType); } /// /// Visits a "table" expression - performs view expansion on the table (if appropriate), /// and then some additional book-keeping. /// /// The "ofType" and "includeSubtypes" parameters are optional hints for view expansion, allowing /// for more customized (and hopefully, more optimal) views. The wasOfTypeSatisfied out parameter /// tells whether the ofType filter was already handled by the view expansion, or if the caller still /// needs to deal with it. /// /// If the "table" is a C-space entityset, then we produce a ScanViewOp /// tree with the defining query as the only child of the ScanViewOp /// /// If the table is an S-space entityset, then we still produce a ScanViewOp, but this /// time, we produce a simple "select * from BaseTable" as the defining /// query /// /// the scanTable node tree /// the scanTableOp /// /// An optional IsOfOp representing a type filter to apply to the scan table; will be set tonull /// if the scan target is expanded to a view that renders the type filter superfluous. /// ///private Node ProcessScanTable(Node scanTableNode, ScanTableOp scanTableOp, ref IsOfOp typeFilter) { HandleTableOpMetadata(scanTableOp); PlanCompiler.Assert(scanTableOp.Table.TableMetadata.Extent != null, "ScanTableOp must reference a table with an extent"); Node ret = null; // // Get simple things out of the way. If we're dealing with an S-space entityset, // simply return the node // if (scanTableOp.Table.TableMetadata.Extent.EntityContainer.DataSpace == DataSpace.SSpace) { return scanTableNode; } else { // "Expand" the C-Space view ret = ExpandView(scanTableNode, scanTableOp, ref typeFilter); } m_viewNestingLevel++; // Rerun the processor over the resulting subtree ret = VisitNode(ret); m_viewNestingLevel--; return ret; } /// /// Processes a ScanTableOp - simply delegates to ProcessScanTableOp /// /// the view op /// current node tree ///the transformed view-op public override Node Visit(ScanTableOp op, Node n) { IsOfOp nullFilter = null; return ProcessScanTable(n, op, ref nullFilter); } ////// Visitor for a ScanViewOp /// /// /// ///public override Node Visit(ScanViewOp op, Node n) { HandleTableOpMetadata(op); // Ideally, I should call this as the first statement, but that was causing too // many test diffs - because of the order in which the entitytypes/sets // were being added. There is no semantic difference in calling this here VisitRelOpDefault(op, n); return n; } /// /// Processing for all JoinOps /// /// JoinOp /// Current subtree ///protected override Node VisitJoinOp(JoinBaseOp op, Node n) { // Only LeftOuterJoin and InnerJoin are handled by JoinElimination if (op.OpType == OpType.InnerJoin || op.OpType == OpType.LeftOuterJoin) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); } // If a subquery was added with an exists node, we have to go througth Normalization if (base.ProcessJoinOp(op, n)) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.Normalization); } return n; } /// /// Perform default relop processing; Also "require" the join-elimination phase /// /// /// ///protected override Node VisitApplyOp(ApplyBaseOp op, Node n) { m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination); return VisitRelOpDefault(op, n); } /// /// Can I eliminate this sort? I can, if the current path is *not* one of the /// following /// TopN(Sort) /// PhysicalProject(Sort) /// /// We don't yet handle the TopN variant /// ///private bool IsSortUnnecessary() { Node ancestor = m_ancestors.Peek(); PlanCompiler.Assert(ancestor != null, "unexpected SortOp as root node?"); if (ancestor.Op.OpType == OpType.PhysicalProject) { return false; } return true; } /// /// Visit a SortOp. Eliminate it if the path to this node is not one of /// PhysicalProject(Sort) or /// TopN(Sort) /// /// Otherwise, simply visit the child RelOp /// /// /// Current sortOp /// current subtree ///possibly transformed subtree public override Node Visit(SortOp op, Node n) { // can I eliminate this sort if (this.IsSortUnnecessary()) { return VisitNode(n.Child0); } // perform default processing return VisitRelOpDefault(op, n); } ////// Checks to see if this filterOp represents an IS OF (or IS OF ONLY) filter over a ScanTableOp /// /// the filterOp node /// (OUT) the Type to restrict to /// (OUT) was an ONLY clause specified ///private bool IsOfTypeOverScanTable(Node n, out IsOfOp typeFilter) { typeFilter = null; // // Is the predicate an IsOf predicate // IsOfOp isOfOp = n.Child1.Op as IsOfOp; if (isOfOp == null) { return false; } // // Is the Input RelOp a ScanTableOp // ScanTableOp scanTableOp = n.Child0.Op as ScanTableOp; if (scanTableOp == null || scanTableOp.Table.Columns.Count != 1) { return false; } // // Is the argument to the IsOfOp the single column of the table? // VarRefOp varRefOp = n.Child1.Child0.Op as VarRefOp; if (varRefOp == null || varRefOp.Var != scanTableOp.Table.Columns[0]) { return false; } // // All conditions match. Return the info from the IsOf predicate // typeFilter = isOfOp; return true; } /// /// Handler for a FilterOp. Usually delegates to VisitRelOpDefault. /// /// There's one special case - where we have an ISOF predicate over a ScanTable. In that case, we attempt /// to get a more "optimal" view; and return that optimal view /// /// /// the filterOp /// the node tree ///public override Node Visit(FilterOp op, Node n) { IsOfOp typeFilter; if (IsOfTypeOverScanTable(n, out typeFilter)) { Node ret = ProcessScanTable(n.Child0, (ScanTableOp)n.Child0.Op, ref typeFilter); if (typeFilter != null) { n.Child1 = VisitNode(n.Child1); n.Child0 = ret; ret = n; } return ret; } else { return VisitRelOpDefault(op, n); } } /// /// Visit a ProjectOp; if the input is a SortOp, we pullup the sort over /// the ProjectOp to ensure that we don't have nested sorts; /// Note: This transformation cannot be moved in the normalizer, /// because it needs to happen before any subquery augmentation happens. /// /// /// ///public override Node Visit(ProjectOp op, Node n) { PlanCompiler.Assert(n.HasChild0, "projectOp without input?"); if (OpType.Sort == n.Child0.Op.OpType || OpType.ConstrainedSort == n.Child0.Op.OpType) { SortBaseOp sort = (SortBaseOp)n.Child0.Op; IList sortChildren = new List (); sortChildren.Add(n); //A ConstrainedSort has two other children besides the input and it needs to keep them. for (int i = 1; i < n.Child0.Children.Count; i++) { sortChildren.Add(n.Child0.Children[i]); } // Replace the ProjectOp input (currently the Sort node) with the input to the Sort. n.Child0 = n.Child0.Child0; // Vars produced by the Sort input and used as SortKeys should be considered outputs // of the ProjectOp that now operates over what was the Sort input. foreach (SortKey key in sort.Keys) { op.Outputs.Set(key.Var); } // Finally, pull the Sort over the Project by creating a new Sort node with the original // Sort as its Op and the Project node as its only child. This is sufficient because // the ITreeGenerator ensures that the SortOp does not have any local VarDefs. return VisitNode(m_command.CreateNode(sort, sortChildren)); } // perform default processing Node newNode = VisitRelOpDefault(op, n); return newNode; } /// /// Mark AggregatePushdown as needed /// /// the groupByInto op /// the node tree ///public override Node Visit(GroupByIntoOp op, Node n) { this.m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.AggregatePushdown); return base.Visit(op, n); } #endregion #endregion #endregion } /// /// Finds the record (Row) types that we're projecting out of the query, and /// ensures that we mark them as needing a nullable sentinel, so when we /// flatten them later we'll have one added. /// internal class StructuredTypeNullabilityAnalyzer : ColumnMapVisitor> { static internal StructuredTypeNullabilityAnalyzer Instance = new StructuredTypeNullabilityAnalyzer(); /// /// VarRefColumnMap /// /// /// ///internal override void Visit(VarRefColumnMap columnMap, HashSet typesNeedingNullSentinel) { AddTypeNeedingNullSentinel(typesNeedingNullSentinel, columnMap.Type); base.Visit(columnMap, typesNeedingNullSentinel); } /// /// Recursively add any Row types to the list of types needing a sentinel. /// /// /// private static void AddTypeNeedingNullSentinel(HashSettypesNeedingNullSentinel, TypeUsage typeUsage) { if (TypeSemantics.IsCollectionType(typeUsage)) { AddTypeNeedingNullSentinel(typesNeedingNullSentinel, TypeHelpers.GetElementTypeUsage(typeUsage)); } else { if (TypeSemantics.IsRowType(typeUsage) || TypeSemantics.IsComplexType(typeUsage)) { MarkAsNeedingNullSentinel(typesNeedingNullSentinel, typeUsage); } foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(typeUsage)) { AddTypeNeedingNullSentinel(typesNeedingNullSentinel, m.TypeUsage); } } } /// /// Marks the given typeUsage as needing a null sentinel. /// Call this method instead of calling Add over the HashSet directly, to ensure consistency. /// /// /// internal static void MarkAsNeedingNullSentinel(HashSettypesNeedingNullSentinel, TypeUsage typeUsage) { typesNeedingNullSentinel.Add(typeUsage.EdmType.Identity); } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ActivityCodeGenerator.cs
- InfoCardRSACryptoProvider.cs
- XPathDescendantIterator.cs
- TypeResolver.cs
- RegexMatchCollection.cs
- DataPager.cs
- documentsequencetextpointer.cs
- NavigationEventArgs.cs
- BlurBitmapEffect.cs
- TableStyle.cs
- PixelFormat.cs
- SqlCommand.cs
- SwitchLevelAttribute.cs
- Screen.cs
- ZoneLinkButton.cs
- IisTraceWebEventProvider.cs
- DispatcherExceptionFilterEventArgs.cs
- TraceSection.cs
- WhitespaceRuleLookup.cs
- DataGridItem.cs
- SimplePropertyEntry.cs
- FlowDocumentReader.cs
- EncoderParameters.cs
- TokenBasedSet.cs
- FillErrorEventArgs.cs
- ImmutablePropertyDescriptorGridEntry.cs
- FixUpCollection.cs
- EventLogStatus.cs
- PropertyValueChangedEvent.cs
- PermissionRequestEvidence.cs
- RelatedCurrencyManager.cs
- TextEmbeddedObject.cs
- COM2ExtendedUITypeEditor.cs
- Point3DCollection.cs
- ListenerConstants.cs
- GcHandle.cs
- EventLog.cs
- IPipelineRuntime.cs
- SourceSwitch.cs
- FlowLayout.cs
- SmiGettersStream.cs
- KeyNotFoundException.cs
- DataSourceControlBuilder.cs
- HtmlObjectListAdapter.cs
- DynamicValidatorEventArgs.cs
- RoutedEventArgs.cs
- XmlQueryCardinality.cs
- UnsafeNativeMethods.cs
- EncoderNLS.cs
- keycontainerpermission.cs
- XamlVector3DCollectionSerializer.cs
- PrintDialog.cs
- wgx_commands.cs
- CustomAttributeBuilder.cs
- StylusPlugin.cs
- ElementNotEnabledException.cs
- TypefaceMetricsCache.cs
- SoapMessage.cs
- BeginGetFileNameFromUserRequest.cs
- DockProviderWrapper.cs
- JsonReaderDelegator.cs
- AttributeUsageAttribute.cs
- RijndaelManaged.cs
- XmlIncludeAttribute.cs
- Directory.cs
- ExpressionBinding.cs
- AttributeQuery.cs
- PropertyChange.cs
- AlternateViewCollection.cs
- WebRequest.cs
- DataGridViewCell.cs
- BehaviorService.cs
- DragDeltaEventArgs.cs
- GridItemProviderWrapper.cs
- _AutoWebProxyScriptEngine.cs
- IIS7UserPrincipal.cs
- LogManagementAsyncResult.cs
- _SecureChannel.cs
- __Filters.cs
- DataGridViewSortCompareEventArgs.cs
- GCHandleCookieTable.cs
- VisualStyleRenderer.cs
- Delay.cs
- SafeLibraryHandle.cs
- SettingsBindableAttribute.cs
- RawContentTypeMapper.cs
- ColorConverter.cs
- Matrix3DConverter.cs
- EmptyStringExpandableObjectConverter.cs
- GridViewRowCollection.cs
- Dictionary.cs
- PartialCachingAttribute.cs
- GroupQuery.cs
- ParameterToken.cs
- SecurityHelper.cs
- PassportPrincipal.cs
- SpotLight.cs
- Stacktrace.cs
- AutoSizeToolBoxItem.cs
- WebPartEditorCancelVerb.cs