Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / ITreeGenerator.cs / 1305376 / ITreeGenerator.cs
//---------------------------------------------------------------------- //// Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System; using System.Collections.Generic; //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class... using System.Data; using System.Data.Common; using System.Data.Metadata.Edm; using System.Data.Common.CommandTrees; using System.Data.Common.CommandTrees.ExpressionBuilder; using System.Data.Common.CommandTrees.Internal; using System.Data.Common.EntitySql; using System.Data.Query.InternalTrees; using System.Linq; using System.Text; using System.Data.Common.Utils; namespace System.Data.Query.PlanCompiler { internal class ITreeGenerator : DbExpressionVisitor{ #region Nested Types /// /// Abstract base class for both DbExpressionBinding and LambdaFunction scopes /// private abstract class CqtVariableScope { internal abstract bool Contains(string varName); internal abstract Node this[string varName] { get; } } ////// Represents a variable scope introduced by a CQT DbExpressionBinding, and therefore contains a single variable. /// private class ExpressionBindingScope : CqtVariableScope { private Command _tree; private string _varName; private Var _var; internal ExpressionBindingScope(Command iqtTree, string name, Var iqtVar) { _tree = iqtTree; _varName = name; _var = iqtVar; } internal override bool Contains(string name) { return (_varName == name); } internal override Node this[string name] { get { PlanCompiler.Assert(name == _varName,"huh?"); return _tree.CreateNode(_tree.CreateVarRefOp(_var)); } } internal Var ScopeVar { get { return _var; } } } ////// Represents a variable scope introduced by a LambdaFunction. /// private sealed class LambdaScope : CqtVariableScope { private readonly ITreeGenerator _treeGen; private readonly Command _command; private readonly Dictionary_arguments; private readonly Dictionary _referencedArgs; internal LambdaScope(ITreeGenerator treeGen, Command command, Dictionary args) { _treeGen = treeGen; _command = command; _arguments = args; _referencedArgs = new Dictionary (_arguments.Count); } internal override bool Contains(string name) { return (_arguments.ContainsKey(name)); } internal override Node this[string name] { get { PlanCompiler.Assert(_arguments.ContainsKey(name), "LambdaScope indexer called for invalid Var"); Node argNode = _arguments[name]; if (_referencedArgs.ContainsKey(argNode)) { // The specified argument has already been substituted into the // IQT and so this substitution requires a copy of the argument. VarMap mappedVars = null; // This is a 'deep copy' operation that clones the entire subtree rooted at the node. Node argCopy = OpCopier.Copy(_command, argNode, out mappedVars); // If any Nodes in the copy of the argument produce Vars then the // Node --> Var map must be updated to include them. if (mappedVars.Count > 0) { List sources = new List (1); sources.Add(argNode); List copies = new List (1); copies.Add(argCopy); MapCopiedNodeVars(sources, copies, mappedVars); } argNode = argCopy; } else { // This is the first reference of the lambda argument, so the Node itself // can be returned rather than a copy, but the dictionary that tracks // whether or not an argument has been referenced needs to be updated. _referencedArgs[argNode] = true; } return argNode; } } private void MapCopiedNodeVars(IList sources, IList copies, Dictionary varMappings) { PlanCompiler.Assert(sources.Count == copies.Count, "Source/Copy Node count mismatch"); // // For each Source/Copy Node in the two lists: // - Recursively update the Node --> Var map for any child nodes // - If the Source Node is mapped to a Var, then retrieve the new Var // produced by the Op copier that corresponds to that Source Var, and // add an entry to the Node --> Var map that maps the Copy Node to the // new Var. // for (int idx = 0; idx < sources.Count; idx++) { Node sourceNode = sources[idx]; Node copyNode = copies[idx]; if (sourceNode.Children.Count > 0) { MapCopiedNodeVars(sourceNode.Children, copyNode.Children, varMappings); } Var sourceVar = null; if (_treeGen.VarMap.TryGetValue(sourceNode, out sourceVar)) { PlanCompiler.Assert(varMappings.ContainsKey(sourceVar), "No mapping found for Var in Var to Var map from OpCopier"); this._treeGen.VarMap[copyNode] = varMappings[sourceVar]; } } } } #endregion private static Dictionary s_opMap = InitializeExpressionKindToOpTypeMap(); private readonly Command _iqtCommand; private readonly Stack _varScopes = new Stack (); private readonly Dictionary _varMap = new Dictionary (); private readonly Stack _functionExpansions = new Stack (); /// /// Maintained only for model functions with user-defined body. /// private readonly Dictionary_functionsIsPredicateFlag = new Dictionary (); // Used to track which IsOf type filter expressions have already been processed private readonly HashSet _processedIsOfFilters = new HashSet (); private readonly HashSet _fakeTreats = new HashSet (); // leverage discriminator metadata in the top-level project when translating query mapping views... private readonly System.Data.Mapping.ViewGeneration.DiscriminatorMap _discriminatorMap; private readonly DbProjectExpression _discriminatedViewTopProject; /// /// Initialize the DbExpressionKind --> OpType mappings for DbComparisonExpression and DbArithmeticExpression /// private static DictionaryInitializeExpressionKindToOpTypeMap() { Dictionary opMap = new Dictionary (12); // // Arithmetic operators // opMap[DbExpressionKind.Plus] = OpType.Plus; opMap[DbExpressionKind.Minus] = OpType.Minus; opMap[DbExpressionKind.Multiply] = OpType.Multiply; opMap[DbExpressionKind.Divide] = OpType.Divide; opMap[DbExpressionKind.Modulo] = OpType.Modulo; opMap[DbExpressionKind.UnaryMinus] = OpType.UnaryMinus; // // Comparison operators // opMap[DbExpressionKind.Equals] = OpType.EQ; opMap[DbExpressionKind.NotEquals] = OpType.NE; opMap[DbExpressionKind.LessThan] = OpType.LT; opMap[DbExpressionKind.GreaterThan] = OpType.GT; opMap[DbExpressionKind.LessThanOrEquals] = OpType.LE; opMap[DbExpressionKind.GreaterThanOrEquals] = OpType.GE; return opMap; } internal Dictionary VarMap { get { return _varMap; } } public static Command Generate(DbQueryCommandTree ctree) { return Generate(ctree, null); } /// /// Generate an IQT given a query command tree and discriminator metadata (available for certain query mapping views) /// internal static Command Generate(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap) { ITreeGenerator treeGenerator = new ITreeGenerator(ctree, discriminatorMap); return treeGenerator._iqtCommand; } private ITreeGenerator(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap) { // // Create a new IQT Command instance that uses the same metadata workspace as the incoming command tree // _iqtCommand = new Command(ctree.MetadataWorkspace); // // When translating a query mapping view matching the TPH discrimination pattern, remember the top level discriminator map // (leveraged to produced a DiscriminatedNewInstanceOp for the top-level projection in the view) // if (null != discriminatorMap) { _discriminatorMap = discriminatorMap; // see System.Data.Mapping.ViewGeneration.DiscriminatorMap PlanCompiler.Assert(ctree.Query.ExpressionKind == DbExpressionKind.Project, "top level QMV expression must be project to match discriminator pattern"); _discriminatedViewTopProject = (DbProjectExpression)ctree.Query; } // // For each Parameter declared by the command tree, add a ParameterVar to the set of parameter vars maintained by the conversion visitor. // Each ParameterVar has the same name and type as the corresponding parameter on the command tree. // foreach (KeyValuePairparamInfo in ctree.Parameters) { if (!ValidateParameterType(paramInfo.Value)) { throw EntityUtil.NotSupported(System.Data.Entity.Strings.ParameterTypeNotSupported(paramInfo.Key, paramInfo.Value.ToString())); } _iqtCommand.CreateParameterVar(paramInfo.Key, paramInfo.Value); } // Convert into an ITree _iqtCommand.Root = VisitExpr(ctree.Query); // // If the root of the tree is not a relop, build up a fake project over a // a singlerowtableOp. // "s" => Project(SingleRowTableOp, "s") // if (!_iqtCommand.Root.Op.IsRelOp) { Node scalarExpr = ConvertToScalarOpTree(_iqtCommand.Root, ctree.Query); Node singletonTableNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowTableOp()); Var newVar; Node varDefListNode = _iqtCommand.CreateVarDefListNode(scalarExpr, out newVar); ProjectOp projectOp = _iqtCommand.CreateProjectOp(newVar); Node newRoot = _iqtCommand.CreateNode(projectOp, singletonTableNode, varDefListNode); if (TypeSemantics.IsCollectionType(_iqtCommand.Root.Op.Type)) { UnnestOp unnestOp = _iqtCommand.CreateUnnestOp(newVar); newRoot = _iqtCommand.CreateNode(unnestOp, varDefListNode.Child0); newVar = unnestOp.Table.Columns[0]; } _iqtCommand.Root = newRoot; _varMap[_iqtCommand.Root] = newVar; } // // Ensure that the topmost portion of the query is capped by a // PhysicalProject expression // _iqtCommand.Root = CapWithPhysicalProject(_iqtCommand.Root); } private static bool ValidateParameterType(TypeUsage paramType) { return (paramType != null && paramType.EdmType != null && (TypeSemantics.IsPrimitiveType(paramType) || paramType.EdmType is EnumType)); } #region DbExpressionVisitor Helpers private static RowType ExtractElementRowType(TypeUsage typeUsage) { return TypeHelpers.GetEdmType (TypeHelpers.GetEdmType (typeUsage).TypeUsage); } #if DEBUG private static bool IsCollectionOfRecord(TypeUsage typeUsage) { CollectionType collectionType; return (TypeHelpers.TryGetEdmType (typeUsage, out collectionType) && collectionType != null && TypeSemantics.IsRowType(collectionType.TypeUsage)); } #endif /// /// Is the current expression a predicate? /// /// expr to check ///true, if the expression is a predicate private bool IsPredicate(DbExpression expr) { if (TypeSemantics.IsPrimitiveType(expr.ResultType, PrimitiveTypeKind.Boolean)) { switch (expr.ExpressionKind) { case DbExpressionKind.Equals: case DbExpressionKind.NotEquals: case DbExpressionKind.LessThan: case DbExpressionKind.LessThanOrEquals: case DbExpressionKind.GreaterThan: case DbExpressionKind.GreaterThanOrEquals: case DbExpressionKind.And: case DbExpressionKind.Or: case DbExpressionKind.Not: case DbExpressionKind.Like: case DbExpressionKind.IsEmpty: case DbExpressionKind.IsNull: case DbExpressionKind.IsOf: case DbExpressionKind.IsOfOnly: case DbExpressionKind.Any: case DbExpressionKind.All: return true; case DbExpressionKind.Lambda: // return IsPredicate(((DbLambdaExpression)expr).Lambda.Body); case DbExpressionKind.Function: { // EdmFunction edmFunction = ((DbFunctionExpression)expr).Function; if (edmFunction.HasUserDefinedBody) { bool isPredicateFunction; if (_functionsIsPredicateFlag.TryGetValue(edmFunction, out isPredicateFunction)) { return isPredicateFunction; } else { // It is important that IsPredicate is called after the expression has been visited, otherwise // _functionsIsPredicateFlag map will not contain an entry for the function with a definition PlanCompiler.Assert(false, "IsPredicate must be called on a visited function expression"); return false; } } else { return false; } } default: return false; } } else { return false; } } ////// Callback to process an expression /// /// The expression to convert ///private delegate Node VisitExprDelegate(DbExpression e); private Node VisitExpr(DbExpression e) { if (e == null) { return null; } else { return e.Accept (this); } } /// /// Convert this expression into a "scalar value" ITree expression. There are two main /// /// ///private Node VisitExprAsScalar(DbExpression expr) { if (expr == null) { return null; } Node node = VisitExpr(expr); // the real work node = ConvertToScalarOpTree(node, expr); return node; } /// /// Convert an Itree node into a scalar op tree /// /// the subtree /// the original CQT expression ///the converted subtree private Node ConvertToScalarOpTree(Node node, DbExpression expr) { // // If the current expression is a collection, and we've simply produced a RelOp // then we need to add a CollectOp above a PhysicalProjectOp above the RelOp // if (node.Op.IsRelOp) { node = ConvertRelOpToScalarOpTree(node, expr.ResultType); } // // If the current expression is a boolean, and it is really a predicate, then // scalarize the predicate (ie) convert it into a "case whenthen 'true' else 'false' end" expression // SQLBUDT #431406: handle 3-valued logic for all predicates except IsNull // Convert boolean predicate p into // case when p then true when not(p) then false else null end // else if (IsPredicate(expr)) { CaseOp caseOp = _iqtCommand.CreateCaseOp(_iqtCommand.BooleanType); //For 2-valued logic there are 3 arguments, for 3-valued there are 5 List arguments = new List ((expr.ExpressionKind == DbExpressionKind.IsNull) ? 3 : 5); //Add the original as the first when arguments.Add(node); //Add the first then, the true node arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true))); //If the expression has 3-valued logic, add a second when if (expr.ExpressionKind != DbExpressionKind.IsNull) { Node predCopy = VisitExpr(expr); arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), predCopy)); } //Add the false node: for 3 valued logic this is the second then, for 2 valued the else arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, false))); //The null node, it is the else-clause for 3-valued logic if (expr.ExpressionKind != DbExpressionKind.IsNull) { arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.BooleanType))); } node = _iqtCommand.CreateNode(caseOp, arguments); } return node; } /// /// Convert a rel op Itree node into a scalar op tree /// /// /// ///private Node ConvertRelOpToScalarOpTree(Node node, TypeUsage resultType) { PlanCompiler.Assert(TypeSemantics.IsCollectionType(resultType), "RelOp with non-Collection result type"); CollectOp collectOp = _iqtCommand.CreateCollectOp(resultType); // // I'm not thrilled about having to build a PhysicalProjectOp here - this // is definitely something I will need to revisit soon // Node projectNode = CapWithPhysicalProject(node); node = _iqtCommand.CreateNode(collectOp, projectNode); return node; } /// /// Convert an expression into an iqt predicate /// /// the expression to process ///private Node VisitExprAsPredicate(DbExpression expr) { if (expr == null) { return null; } Node node = VisitExpr(expr); // // If the current expression is not a predicate, then we need to make it one, by // comparing it with the constant 'true' // if (!IsPredicate(expr)) { ComparisonOp comparisonOp = _iqtCommand.CreateComparisonOp(OpType.EQ); Node trueNode = _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)); node = _iqtCommand.CreateNode(comparisonOp, node, trueNode); } else { PlanCompiler.Assert(!node.Op.IsRelOp, "unexpected relOp as predicate?"); } return node; } /// /// Process a list of expressions, and apply the delegate to each of the expressions /// /// list of cqt expressions to process /// the callback to apply ///a list of IQT expressions private static IListVisitExpr(IList exprs, VisitExprDelegate exprDelegate) { List nodeList = new List (); for(int idx = 0; idx < exprs.Count; idx++) { nodeList.Add(exprDelegate(exprs[idx])); } return nodeList; } /// /// Process a set of cqt expressions - and convert them into scalar iqt expressions /// /// list of cqt expressions ///list of iqt expressions private IListVisitExprAsScalar(IList exprs) { return VisitExpr(exprs, VisitExprAsScalar); } private Node VisitUnary(DbUnaryExpression e, Op op, VisitExprDelegate exprDelegate) { return _iqtCommand.CreateNode(op, exprDelegate(e.Argument)); } private Node VisitBinary(DbBinaryExpression e, Op op, VisitExprDelegate exprDelegate) { return _iqtCommand.CreateNode(op, exprDelegate(e.Left), exprDelegate(e.Right)); } /// /// Ensures that an input op is a RelOp. If the specified Node's Op is not a RelOp then it is wrapped in an Unnest to create a synthetic RelOp. This is only possible if the input Op produces a collection. /// /// The input Node/Op pair ///A Node with an Op that is guaranteed to be a RelOp (this may be the original Node or a new Node created to perform the Unnest) private Node EnsureRelOp(Node inputNode) { // // Input node = N1 // Op inputOp = inputNode.Op; // // If the Op is already a RelOp then simply return its Node // if (inputOp.IsRelOp) { return inputNode; } // // Assert that the input is a ScalarOp (CQT expressions should only ever produce RelOps or ScalarOps) // ScalarOp scalar = inputOp as ScalarOp; PlanCompiler.Assert(scalar != null, "An expression in a CQT produced a non-ScalarOp and non-RelOp output Op"); // // Assert that the ScalarOp has a collection result type. EnsureRelOp is called to ensure that arguments to // RelOps are either also RelOps or are ScalarOps that produce a collection, which can be wrapped in an // unnest to produce a RelOp. // PlanCompiler.Assert(TypeSemantics.IsCollectionType(scalar.Type), "An expression used as a RelOp argument was neither a RelOp or a collection"); // // If the ScalarOp represents the nesting of an existing RelOp, simply return that RelOp instead. // CollectOp(PhysicalProjectOp(x)) => x // CollectOp collect = inputOp as CollectOp; if (collect != null) { PlanCompiler.Assert(inputNode.HasChild0, "CollectOp without argument"); if (inputNode.Child0.Op as PhysicalProjectOp != null) { PlanCompiler.Assert(inputNode.Child0.HasChild0, "PhysicalProjectOp without argument"); PlanCompiler.Assert(inputNode.Child0.Child0.Op.IsRelOp, "PhysicalProjectOp applied to non-RelOp input"); // // The structure of the Input is Collect(PhysicalProject(x)), so return x // return inputNode.Child0.Child0; } } // // Create a new VarDefOp that defines the computed var that represents the ScalarOp collection. // This var is the input to the UnnestOp. // varDefNode = N2 // Var inputCollectionVar; Node varDefNode = _iqtCommand.CreateVarDefNode(inputNode, out inputCollectionVar); // // Create an UnnestOp that references the computed var created above. The VarDefOp that defines the var // using the original input Node/Op pair becomes a child of the UnnestOp. // UnnestOp unnest = _iqtCommand.CreateUnnestOp(inputCollectionVar); PlanCompiler.Assert(unnest.Table.Columns.Count == 1, "Unnest of collection ScalarOp produced unexpected number of columns (1 expected)"); // // Create the unnest node, N3 // The UnnestOp produces a new Var, the single ColumnVar produced by the table that results from the Unnest. // Node unnestNode = _iqtCommand.CreateNode(unnest, varDefNode); _varMap[unnestNode] = unnest.Table.Columns[0]; // // Create a Project node above the Unnest, so we can simplify the work to eliminate // the Unnest later. That means we need to create a VarRef to the column var in the // table, a VarDef to define it, and a VarDefList to hold it, then a Project node, N4, // which we return. // Var projectVar; Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(unnest.Table.Columns[0])); Node varDefListNode = _iqtCommand.CreateVarDefListNode(varRefNode, out projectVar); ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar); Node projectNode = _iqtCommand.CreateNode(projectOp, unnestNode, varDefListNode); _varMap[projectNode] = projectVar; return projectNode; } ////// Cap a RelOp with a ProjectOp. The output var of the Project is the /// output var from the input /// /// the input relop tree ///the relop tree with a projectNode at the root private Node CapWithProject(Node input) { PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); if (input.Op.OpType == OpType.Project) { return input; } // Get the Var from the input; and build up a Project above it Var inputVar = _varMap[input]; ProjectOp projectOp = _iqtCommand.CreateProjectOp(inputVar); Node projectNode = _iqtCommand.CreateNode(projectOp, input, _iqtCommand.CreateNode(_iqtCommand.CreateVarDefListOp())); _varMap[projectNode] = inputVar; return projectNode; } ////// Cap a relop tree with a PhysicalProjectOp. The Vars of the PhysicalProjectOp /// are the vars from the RelOp tree /// /// the input relop tree ///relop tree capped by a PhysicalProjectOp private Node CapWithPhysicalProject(Node input) { PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); // Get the Var from the input; and build up a Project above it Var inputVar = _varMap[input]; PhysicalProjectOp projectOp = _iqtCommand.CreatePhysicalProjectOp(inputVar); Node projectNode = _iqtCommand.CreateNode(projectOp, input); return projectNode; } ////// Creates a new variable scope that is based on a CQT DbExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression. /// /// The DbExpressionBinding that defines the scope ///The Node produced by converting the binding's DbExpression private Node EnterExpressionBinding(DbExpressionBinding binding) { return PushBindingScope(binding.Expression, binding.VariableName); } ////// Creates a new variable scope that is based on a CQT DbGroupExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression. /// This method does not bring the GroupVarName into scope. Note that ExitExpressionBinding and NOT ExitGroupExpressionBinding should be used to remove this scope from the stack. /// /// The DbGroupExpressionBinding that defines the scope ///The Node produced by converting the binding's DbExpression private Node EnterGroupExpressionBinding(DbGroupExpressionBinding binding) { return PushBindingScope(binding.Expression, binding.VariableName); } ////// Common implementation method called by both EnterExpressionBinding and EnterGroupExpressionBinding /// /// The DbExpression that defines the binding /// The name of the binding variable ///private Node PushBindingScope(DbExpression boundExpression, string bindingName) { // // Visit the DbExpressionBinding's DbExpression to convert it to a Node/Op pair // Node inputNode = VisitExpr(boundExpression); PlanCompiler.Assert(inputNode != null, "DbExpressionBinding.Expression produced null conversion"); // // Call EnsureRelOp on the converted Node and set inputNode equal to the result // inputNode = EnsureRelOp(inputNode); // // Retrieve the Var produced by the RelOp from the Node --> Var map // Var boundVar = _varMap[inputNode]; PlanCompiler.Assert(boundVar != null, "No Var found for Input Op"); // // Create a new ExpressionBindingScope using the VarName from the DbExpressionBinding and // the Var associated with the Input RelOp, and push the new scope onto the variable scope stack. // _varScopes.Push(new ExpressionBindingScope(_iqtCommand, bindingName, boundVar)); // // Return the IQT conversion of the DbExpressionBinding's DbExpression. // return inputNode; } /// /// Removes a variable scope created based on a DbExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope. /// ///The removed ExpressionBindingScope private ExpressionBindingScope ExitExpressionBinding() { // // Pop the scope from the variable scope stack, assert that it is a DbExpressionBinding scope, and return it. // ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope; PlanCompiler.Assert(retScope != null, "ExitExpressionBinding called without ExpressionBindingScope on top of scope stack"); return retScope; } ////// Removes a variable scope created based on a DbGroupExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope. /// Should only be called after visiting the Aggregates of a DbGroupByExpression in Visit(DbGroupByExpression). /// The sequence (in Visit(GroupExpression e) is: /// 1. EnterGroupExpressionBinding /// 2. Visit e.Keys /// 3. ExitExpressionBinding /// 4. (Push new scope with GroupVarName instead of VarName) /// 5. Visit e.Aggregates /// 6. ExitGroupExpressionBinding /// private void ExitGroupExpressionBinding() { ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope; PlanCompiler.Assert(retScope != null, "ExitGroupExpressionBinding called without ExpressionBindingScope on top of scope stack"); } ////// Creates a new variable scope that is based on a CQT DbLambda and pushes it onto the variable scope stack. /// /// The DbLambda that defines the scope /// A list of Nodes produced by converting the CQT Expressions that provide the arguments to the Lambda function /// an edm function for which the current lambda represents the generated body, otherwise null private void EnterLambdaFunction(DbLambda lambda, ListargumentValues, EdmFunction expandingEdmFunction) { IList lambdaParams = lambda.Variables; Dictionary args = new Dictionary (); int idx = 0; foreach (Node argumentValue in argumentValues) { args.Add(lambdaParams[idx].VariableName, argumentValue); idx++; } // // If lambda represents an edm function body then check for a possible recursion in the function definition. // if (expandingEdmFunction != null) { // // Check if we are already inside the function body. // if (_functionExpansions.Contains(expandingEdmFunction)) { throw EntityUtil.CommandCompilation(Entity.Strings.Cqt_UDF_FunctionDefinitionWithCircularReference(expandingEdmFunction.FullName), null); } // // Push the function before processing its body // _functionExpansions.Push(expandingEdmFunction); } _varScopes.Push(new LambdaScope(this, _iqtCommand, args)); } /// /// Removes a variable scope created based on a Lambda function from the top of the variable scope stack, verifying that it is in fact a LambdaScope. /// /// an edm function for which the current lambda represents the generated body, otherwise null private LambdaScope ExitLambdaFunction(EdmFunction expandingEdmFunction) { // // Pop the scope from the variable scope stack, assert that it is a Lambda scope, and return it. // LambdaScope retScope = _varScopes.Pop() as LambdaScope; PlanCompiler.Assert(retScope != null, "ExitLambdaFunction called without LambdaScope on top of scope stack"); // // If lambda represents an edm function body then pop the function from the expansion stack and make sure it is the expected one. // if (expandingEdmFunction != null) { EdmFunction edmFunction = _functionExpansions.Pop(); PlanCompiler.Assert(edmFunction == expandingEdmFunction, "Function expansion stack corruption: unexpected function at the top of the stack"); } return retScope; } ////// Constructs a NewRecordOp on top of a multi-Var-producing Op, resulting in a RelOp that produces a single Var. /// /// The Node that references the multi-Var-producing Op. This Node will become the first child node of the new ProjectOp's Node /// Type metadata that describes the output record type /// A list of Vars that provide the output columns of the projection ///A new ProjectOp that projects a new record of the specified type from the specified Vars over the original input Op/Node private Node ProjectNewRecord(Node inputNode, RowType recType, IEnumerable colVars) { // // Create a list of VarRefOp Nodes that provide the column values for the new record // ListrecordColumns = new List (); foreach (Var colVar in colVars) { recordColumns.Add(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(colVar))); } // // Create the NewRecordOp Node using the record column nodes as its child nodes // Node newRecordNode = _iqtCommand.CreateNode(_iqtCommand.CreateNewRecordOp(recType), recordColumns); // // Create a new ComputedVar and a VarDefOp that uses the NewRecordOp Node to define it // Var newRecordVar; Node varDefNode = _iqtCommand.CreateVarDefListNode(newRecordNode, out newRecordVar); // // Create a ProjectOp with the single Computed Var defined by the new record construction // ProjectOp projection = _iqtCommand.CreateProjectOp(newRecordVar); Node projectionNode = _iqtCommand.CreateNode(projection, inputNode, varDefNode); _varMap[projectionNode] = newRecordVar; return projectionNode; } #endregion #region DbExpressionVisitor Members public override Node Visit(DbExpression e) { throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_General_UnsupportedExpression(e.GetType().FullName)); } public override Node Visit(DbConstantExpression e) { // Don't use CreateInternalConstantOp - respect user-intent // // Note that it is only safe to call GetValue and access the // constant value directly because any immutable values (byte[]) // will be cloned as the result expression is built in CTreeGenerator, // during the call to DbExpressionBuilder.Constant in VisitConstantOp. ConstantBaseOp op = _iqtCommand.CreateConstantOp(e.ResultType, e.GetValue()); return _iqtCommand.CreateNode(op); } public override Node Visit(DbNullExpression e) { NullOp op = _iqtCommand.CreateNullOp(e.ResultType); return _iqtCommand.CreateNode(op); } public override Node Visit(DbVariableReferenceExpression e) { // // Search the stack of variables scopes, top-down, // until the first one is found that defines a variable with the specified name. // Node varNode = null; foreach (CqtVariableScope scope in _varScopes) { if (scope.Contains(e.VariableName)) { varNode = scope[e.VariableName]; break; } } // // If the variable name was not resolved then either: // 1. The original CQT was invalid (should not be allowed into the ITreeGenerator). // 2. The variable scope stack itself is invalid. // PlanCompiler.Assert(varNode != null, "CQT VarRef could not be resolved in the variable scope stack"); return varNode; } public override Node Visit(DbParameterReferenceExpression e) { Op op = _iqtCommand.CreateVarRefOp(_iqtCommand.GetParameter(e.ParameterName)); return _iqtCommand.CreateNode(op); } public override Node Visit(DbFunctionExpression e) { Node retNode = null; if (e.Function.HasUserDefinedBody) { // This is a CSpace function with a body definition. // Expand it: // - replace the function call with the call to the body lambda, // - visit the lambda call expression. // Get/generate the body lambda. Wrap body generation exceptions. DbLambda lambda; try { lambda = _iqtCommand.MetadataWorkspace.GetGeneratedFunctionDefinition(e.Function); } catch (Exception exception) { if (EntityUtil.IsCatchableExceptionType(exception)) { throw EntityUtil.CommandCompilation(Entity.Strings.Cqt_UDF_FunctionDefinitionGenerationFailed(e.Function.FullName), exception); } throw; } // Visit the lambda call expression. // Argument types should be validated by now, hence the visitor should not throw under normal conditions. retNode = VisitLambdaExpression(lambda, e.Arguments, e.Function); // Check the body to see if the current function is a predicate function // Note that check needs to be done after visiting the the lambdaCall. // Doing it after will ensure that the function defintion has no recursion and IsPredicate will not throw the assertion. _functionsIsPredicateFlag[e.Function] = IsPredicate(lambda.Body); } else // a regular function call - no expansion needed { List argNodes = new List (e.Arguments.Count); for (int idx = 0; idx < e.Arguments.Count; idx++) { // Ensure that any argument with a result type that does not exactly match the type of // the corresponding function parameter is enclosed in a SoftCastOp. argNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Arguments[idx]), e.Function.Parameters[idx].TypeUsage)); } retNode = _iqtCommand.CreateNode(_iqtCommand.CreateFunctionOp(e.Function), argNodes); } return retNode; } public override Node Visit(DbLambdaExpression e) { return VisitLambdaExpression(e.Lambda, e.Arguments, null); } private Node VisitLambdaExpression(DbLambda lambda, IList arguments, EdmFunction expandingEdmFunction) { Node retNode = null; List argNodes = new List (arguments.Count); foreach (DbExpression argExpr in arguments) { // #484709: Lambda function parameters should not have enclosing SoftCastOps. argNodes.Add(VisitExpr(argExpr)); } EnterLambdaFunction(lambda, argNodes, expandingEdmFunction); retNode = VisitExpr(lambda.Body); ExitLambdaFunction(expandingEdmFunction); return retNode; } #if METHOD_EXPRESSION public override Node Visit(MethodExpression e) { throw EntityUtil.NotSupported(); } #endif #region SoftCast Helpers /// /// This method builds a "soft"Cast operator over the input node (if necessary) to (soft) /// cast it to the desired type (targetType) /// /// If the input is a scalarOp, then we simply add on the SoftCastOp /// directly (if it is needed, of course). If the input is a RelOp, we create a /// new ProjectOp above the input, add a SoftCast above the Var of the /// input, and then return the new ProjectOp /// /// The "need to cast" is determined by the Command.EqualTypes function. All type /// equivalence in the plan compiler is determined by this function /// /// the expression to soft-cast /// the desired type to cast to ///private Node BuildSoftCast(Node node, TypeUsage targetType) { // // If the input is a RelOp (say X), and the Var of the input is "x", // we convert this into // Project(X, softCast(x, t)) // where t is the element type of the desired target type // if (node.Op.IsRelOp) { CollectionType targetCollectionType = TypeHelpers.GetEdmType (targetType); targetType = targetCollectionType.TypeUsage; Var nodeVar = _varMap[node]; // Do we need a cast at all? if (Command.EqualTypes(targetType, nodeVar.Type)) { return node; } // Build up the projectOp Var projectVar; Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(nodeVar)); Node castNode = _iqtCommand.CreateNode(_iqtCommand.CreateSoftCastOp(targetType), varRefNode); Node varDefListNode = _iqtCommand.CreateVarDefListNode(castNode, out projectVar); ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar); Node projectNode = _iqtCommand.CreateNode(projectOp, node, varDefListNode); _varMap[projectNode] = projectVar; return projectNode; } else { PlanCompiler.Assert(node.Op.IsScalarOp, "I want a scalar op"); if (Command.EqualTypes(node.Op.Type, targetType)) { return node; } else { SoftCastOp castOp = _iqtCommand.CreateSoftCastOp(targetType); return _iqtCommand.CreateNode(castOp, node); } } } /// /// A variant of the function above. Works with an EdmType instead /// of a TypeUsage, but leverages all the work above /// /// the node to "cast" /// the desired type ///the transformed expression private Node BuildSoftCast(Node node, EdmType targetType) { return BuildSoftCast(node, TypeUsage.Create(targetType)); } private Node BuildEntityRef(Node arg, TypeUsage entityType) { TypeUsage refType = TypeHelpers.CreateReferenceTypeUsage((EntityType)entityType.EdmType); return _iqtCommand.CreateNode(_iqtCommand.CreateGetEntityRefOp(refType), arg); } #endregion ////// We simplify the property instance where the user is accessing a key member of /// a reference navigation. The instance becomes simply the reference key in such /// cases. /// /// For instance, product.Category.CategoryID becomes Ref(product.Category).CategoryID, /// which gives us a chance of optimizing the query (using foreign keys rather than joins) /// /// The original property expression that specifies the member and instance /// 'Simplified' instance. If the member is a key and the instance is a navigation /// the rewritten expression's instance is a reference navigation rather than the full entity. ///private bool TryRewriteKeyPropertyAccess(DbPropertyExpression propertyExpression, out DbExpression rewritten) { // if we're accessing a key member of a navigation, collapse the structured instance // to the key reference. if (propertyExpression.Instance.ExpressionKind == DbExpressionKind.Property && Helper.IsEntityType(propertyExpression.Instance.ResultType.EdmType)) { EntityType instanceType = (EntityType)propertyExpression.Instance.ResultType.EdmType; DbPropertyExpression instanceExpression = (DbPropertyExpression)propertyExpression.Instance; if (Helper.IsNavigationProperty(instanceExpression.Property) && instanceType.KeyMembers.Contains(propertyExpression.Property)) { // modify the property expression so that it merely retrieves the reference // not the entire entity NavigationProperty navigationProperty = (NavigationProperty)instanceExpression.Property; DbExpression navigationSource = instanceExpression.Instance.GetEntityRef(); DbExpression navigationExpression = navigationSource.Navigate(navigationProperty.FromEndMember, navigationProperty.ToEndMember); rewritten = navigationExpression.GetRefKey(); rewritten = rewritten.Property(propertyExpression.Property.Name); return true; } } rewritten = null; return false; } public override Node Visit(DbPropertyExpression e) { // Only Properties, Relationship End and NavigationProperty members are supported. if (BuiltInTypeKind.EdmProperty != e.Property.BuiltInTypeKind && BuiltInTypeKind.AssociationEndMember != e.Property.BuiltInTypeKind && BuiltInTypeKind.NavigationProperty != e.Property.BuiltInTypeKind) { throw EntityUtil.NotSupported(); } PlanCompiler.Assert(e.Instance != null, "Static properties are not supported"); Node retNode = null; DbExpression rewritten; if (TryRewriteKeyPropertyAccess(e, out rewritten)) { retNode = this.VisitExpr(rewritten); } else { Node instance = VisitExpr(e.Instance); // // Retrieving a property from a new instance constructor can be // simplified to just the node that provides the corresponding property. // For example, Property(Row(A = x, B = y), 'A') => x // All structured types (including association types) are considered. // if (e.Instance.ExpressionKind == DbExpressionKind.NewInstance && Helper.IsStructuralType(e.Instance.ResultType.EdmType)) { // Retrieve the 'structural' members of the instance's type. // For Association types this should be only Association End members, // while for Complex, Entity or Row types is should be only Properties. System.Collections.IList propertyOrEndMembers = Helper.GetAllStructuralMembers(e.Instance.ResultType.EdmType); // Find the position of the member with the same name as the retrieved // member in the list of structural members. int memberIdx = -1; for (int idx = 0; idx < propertyOrEndMembers.Count; idx++) { if (string.Equals(e.Property.Name, ((EdmMember)propertyOrEndMembers[idx]).Name, StringComparison.Ordinal)) { memberIdx = idx; break; } } PlanCompiler.Assert(memberIdx > -1, "The specified property was not found"); // If the member was found, return the corresponding argument value // to the new instance op. retNode = instance.Children[memberIdx]; // Make sure the argument value has been "cast" to the return type // of the property, if necessary. retNode = BuildSoftCast(retNode, e.ResultType); } else { Op op = _iqtCommand.CreatePropertyOp(e.Property); // Make sure that the input has been "cast" to the right type instance = BuildSoftCast(instance, e.Property.DeclaringType); retNode = _iqtCommand.CreateNode(op, instance); } } return retNode; } public override Node Visit(DbComparisonExpression e) { Op op = _iqtCommand.CreateComparisonOp(s_opMap[e.ExpressionKind]); Node leftArg = VisitExprAsScalar(e.Left); Node rightArg = VisitExprAsScalar(e.Right); TypeUsage commonType = TypeHelpers.GetCommonTypeUsage(e.Left.ResultType, e.Right.ResultType); // Make sure that the inputs have been cast to the right types if (!Command.EqualTypes(e.Left.ResultType, e.Right.ResultType)) { leftArg = BuildSoftCast(leftArg, commonType); rightArg = BuildSoftCast(rightArg, commonType); } if (TypeSemantics.IsEntityType(commonType) && (e.ExpressionKind == DbExpressionKind.Equals || e.ExpressionKind == DbExpressionKind.NotEquals)) { // Entity (in)equality is implemented as ref (in)equality leftArg = BuildEntityRef(leftArg, commonType); rightArg = BuildEntityRef(rightArg, commonType); } return _iqtCommand.CreateNode(op, leftArg, rightArg); } public override Node Visit(DbLikeExpression e) { return _iqtCommand.CreateNode( _iqtCommand.CreateLikeOp(), VisitExpr(e.Argument), VisitExpr(e.Pattern), VisitExpr(e.Escape) ); } private Node CreateLimitNode(Node inputNode, Node limitNode, bool withTies) { // // Limit(Skip(x)) - which becomes ConstrainedSortOp - and Limit(Sort(x)) are special cases // Node retNode = null; if (OpType.ConstrainedSort == inputNode.Op.OpType && OpType.Null == inputNode.Child2.Op.OpType) { // // The input was a DbSkipExpression which is now represented // as a ConstrainedSortOp with a NullOp Limit. The Limit from // this DbLimitExpression can be merged into the input ConstrainedSortOp // rather than creating a new ConstrainedSortOp. // inputNode.Child2 = limitNode; // If this DbLimitExpression specifies WithTies, the input ConstrainedSortOp must be // updated to reflect this (DbSkipExpression always produces a ConstrainedSortOp with // WithTies equal to false). if (withTies) { ((ConstrainedSortOp)inputNode.Op).WithTies = true; } retNode = inputNode; } else if (OpType.Sort == inputNode.Op.OpType) { // // This DbLimitExpression is applying a limit to a DbSortExpression. // The two expressions can be merged into a single ConstrainedSortOp // rather than creating a new ConstrainedSortOp over the input SortOp. // // The new ConstrainedSortOp has the same SortKeys as the input SortOp. // The returned Node will have the following children: // - The input to the Sort // - A NullOp to indicate no Skip operation is specified // - The limit Node from the DbLimitExpression // retNode = _iqtCommand.CreateNode( _iqtCommand.CreateConstrainedSortOp(((SortOp)inputNode.Op).Keys, withTies), inputNode.Child0, _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)), limitNode ); } else { // // The input to the Limit is neither ConstrainedSortOp or SortOp. // A new ConstrainedSortOp must be created with an empty list of keys // and the following children: // - The input to the DbLimitExpression // - a NullOp to indicate that no Skip operation is specified // - The limit Node from the DbLimitExpression // retNode = _iqtCommand.CreateNode( _iqtCommand.CreateConstrainedSortOp(new List true if the property expression was rewritten, in which casewill be non-null, /// otherwise false , in which casewill be null. (), withTies), inputNode, _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)), limitNode ); } return retNode; } public override Node Visit(DbLimitExpression expression) { // // Visit the Argument and retrieve its Var // Node inputNode = EnsureRelOp(VisitExpr(expression.Argument)); Var inputVar = _varMap[inputNode]; // // Visit the Limit ensuring that it is a scalar // Node limitNode = VisitExprAsScalar(expression.Limit); Node retNode; if(OpType.Project == inputNode.Op.OpType) { // // If the input to the DbLimitExpression is a projection, then apply the Limit operation to the // input to the ProjectOp instead. This allows Limit(Project(Skip(x))) and Limit(Project(Sort(x))) // to be treated in the same way as Limit(Skip(x)) and Limit(Sort(x)). // Note that even if the input to the projection is not a ConstrainedSortOp or SortOp, the // Limit operation is still pushed under the Project. // inputNode.Child0 = CreateLimitNode(inputNode.Child0, limitNode, expression.WithTies); retNode = inputNode; } else { // // Otherwise, apply the Limit operation directly to the input. // retNode = CreateLimitNode(inputNode, limitNode, expression.WithTies); } // // The output Var of the resulting Node is the same as the output Var of its input Node. // If the input node is being returned (either because the Limit was pushed under a Project // or because the input was a ConstrainedSortOp that was simply updated with the Limit value) // then the Node -> Var map does not need to be updated. // if(!object.ReferenceEquals(retNode, inputNode)) { _varMap[retNode] = inputVar; } return retNode; } public override Node Visit(DbIsNullExpression e) { // SQLBUDT #484294: We need to recognize and simplify IsNull - IsNull and IsNull - Not - IsNull // This is the latest point where such patterns can be easily recognized. // After this the input predicate would get translated into a case statement. bool isAlwaysFalse = false; //true if IsNull - IsNull and IsNull - Not - IsNull is recognized if (e.Argument.ExpressionKind == DbExpressionKind.IsNull) { isAlwaysFalse = true; } else if (e.Argument.ExpressionKind == DbExpressionKind.Not) { DbNotExpression notExpression = (DbNotExpression)e.Argument; if (notExpression.Argument.ExpressionKind == DbExpressionKind.IsNull) { isAlwaysFalse = true; } } Op op = _iqtCommand.CreateConditionalOp(OpType.IsNull); //If we have recognized that the result is always false, return IsNull(true), to still have predicate as output. //This gets further simplified by transformation rules. if (isAlwaysFalse) { return _iqtCommand.CreateNode(op, _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true))); } Node argNode = VisitExprAsScalar(e.Argument); if (TypeSemantics.IsEntityType(e.Argument.ResultType)) { argNode = BuildEntityRef(argNode, e.Argument.ResultType); } return _iqtCommand.CreateNode(op, argNode); } public override Node Visit(DbArithmeticExpression e) { Op op = _iqtCommand.CreateArithmeticOp(s_opMap[e.ExpressionKind], e.ResultType); // Make sure that the inputs have been "cast" to the result type // Assumption: The input type must be the same as the result type. Is this always true? List children = new List (); foreach (DbExpression arg in e.Arguments) { Node child = VisitExprAsScalar(arg); children.Add(BuildSoftCast(child, e.ResultType)); } return _iqtCommand.CreateNode(op, children); } public override Node Visit(DbAndExpression e) { Op op = _iqtCommand.CreateConditionalOp(OpType.And); return VisitBinary(e, op, VisitExprAsPredicate); } public override Node Visit(DbOrExpression e) { Op op = _iqtCommand.CreateConditionalOp(OpType.Or); return VisitBinary(e, op, VisitExprAsPredicate); } public override Node Visit(DbNotExpression e) { Op op = _iqtCommand.CreateConditionalOp(OpType.Not); return VisitUnary(e, op, VisitExprAsPredicate); } public override Node Visit(DbDistinctExpression e) { Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); Var inputVar = _varMap[inputSetNode]; Op distinctOp = _iqtCommand.CreateDistinctOp(inputVar); Node distinctNode = _iqtCommand.CreateNode(distinctOp, inputSetNode); _varMap[distinctNode] = inputVar; return distinctNode; } public override Node Visit(DbElementExpression e) { Op elementOp = _iqtCommand.CreateElementOp(e.ResultType); Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); // Add a soft cast if needed inputSetNode = BuildSoftCast(inputSetNode, TypeHelpers.CreateCollectionTypeUsage(e.ResultType)); Var inputVar = _varMap[inputSetNode]; // // Add a singleRowOp enforcer, as we are not guaranteed that the input // collection produces at most one row // inputSetNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowOp(), inputSetNode); _varMap[inputSetNode] = inputVar; // add a fake projectNode inputSetNode = CapWithProject(inputSetNode); return _iqtCommand.CreateNode(elementOp, inputSetNode); } public override Node Visit(DbIsEmptyExpression e) { // // IsEmpty(input set) --> Not(Exists(input set)) // Op existsOp = _iqtCommand.CreateExistsOp(); Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); return _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Not), _iqtCommand.CreateNode(existsOp, inputSetNode) ); } /// /// Encapsulates the logic required to convert a SetOp (Except, Intersect, UnionAll) expression /// into an IQT Node/Op pair. /// /// The DbExceptExpression, DbIntersectExpression or DbUnionAllExpression to convert, as an instance of DbBinaryExpression ///A new IQT Node that references the ExceptOp, IntersectOp or UnionAllOp created based on the expression private Node VisitSetOpExpression(DbBinaryExpression expression) { PlanCompiler.Assert(DbExpressionKind.Except == expression.ExpressionKind || DbExpressionKind.Intersect == expression.ExpressionKind || DbExpressionKind.UnionAll == expression.ExpressionKind, "Non-SetOp DbExpression used as argument to VisitSetOpExpression"); PlanCompiler.Assert(TypeSemantics.IsCollectionType(expression.ResultType), "SetOp DbExpression does not have collection result type?"); // Visit the left and right collection arguments Node leftNode = EnsureRelOp(VisitExpr(expression.Left)); Node rightNode = EnsureRelOp(VisitExpr(expression.Right)); // // Now the hard part. "Normalize" the left and right sides to // match the result type. // leftNode = BuildSoftCast(leftNode, expression.ResultType); rightNode = BuildSoftCast(rightNode, expression.ResultType); // The SetOp produces a single Var of the same type as the element type of the expression's collection result type Var outputVar = _iqtCommand.CreateSetOpVar(TypeHelpers.GetEdmType(expression.ResultType).TypeUsage); // Create VarMaps for the left and right arguments that map the output Var to the Var produced by the corresponding argument VarMap leftMap = new VarMap(); leftMap.Add(outputVar, _varMap[leftNode]); VarMap rightMap = new VarMap(); rightMap.Add(outputVar, _varMap[rightNode]); // Create a SetOp that corresponds to the operation specified by the expression's DbExpressionKind Op setOp = null; switch(expression.ExpressionKind) { case DbExpressionKind.Except: setOp = _iqtCommand.CreateExceptOp(leftMap, rightMap); break; case DbExpressionKind.Intersect: setOp = _iqtCommand.CreateIntersectOp(leftMap, rightMap); break; case DbExpressionKind.UnionAll: setOp = _iqtCommand.CreateUnionAllOp(leftMap, rightMap); break; } // Create a new Node that references the SetOp Node setOpNode = _iqtCommand.CreateNode(setOp, leftNode, rightNode); // Update the Node => Var map with an entry that maps the new Node to the output Var _varMap[setOpNode] = outputVar; // Return the newly created SetOp Node return setOpNode; } public override Node Visit(DbUnionAllExpression e) { return VisitSetOpExpression(e); } public override Node Visit(DbIntersectExpression e) { return VisitSetOpExpression(e); } public override Node Visit(DbExceptExpression e) { return VisitSetOpExpression(e); } public override Node Visit(DbTreatExpression e) { Op op; if (_fakeTreats.Contains(e)) { op = _iqtCommand.CreateFakeTreatOp(e.ResultType); } else { op = _iqtCommand.CreateTreatOp(e.ResultType); } return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbIsOfExpression e) { Op op = null; if (DbExpressionKind.IsOfOnly == e.ExpressionKind) { op = _iqtCommand.CreateIsOfOnlyOp(e.OfType); } else { op = _iqtCommand.CreateIsOfOp(e.OfType); } return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbCastExpression e) { Op op = _iqtCommand.CreateCastOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbCaseExpression e) { List childNodes = new List (); for (int idx = 0; idx < e.When.Count; idx++) { childNodes.Add(VisitExprAsPredicate(e.When[idx])); // Make sure that each then-clause is the same type as the result childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Then[idx]), e.ResultType)); } // Make sure that the else-clause is the same type as the result childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Else), e.ResultType)); return _iqtCommand.CreateNode(_iqtCommand.CreateCaseOp(e.ResultType), childNodes); } /// /// Represents one or more type filters that should be AND'd together to produce an aggregate IsOf filter expression /// private class IsOfFilter { ////// The type that elements of the filtered input set must be to satisfy this IsOf filter /// private readonly TypeUsage requiredType; ////// Indicates whether elements of the filtered input set may be of a subtype (IsOf) of the required type /// and still satisfy the IsOfFilter, or must be exactly of the required type (IsOfOnly) to do so. /// private readonly bool isExact; ////// The next IsOfFilter in the AND chain. /// private IsOfFilter next; internal IsOfFilter(DbIsOfExpression template) { this.requiredType = template.OfType; this.isExact = (template.ExpressionKind == DbExpressionKind.IsOfOnly); } internal IsOfFilter(DbOfTypeExpression template) { this.requiredType = template.OfType; this.isExact = (template.ExpressionKind == DbExpressionKind.OfTypeOnly); } private IsOfFilter(TypeUsage required, bool exact) { this.requiredType = required; this.isExact = exact; } private IsOfFilter Merge(TypeUsage otherRequiredType, bool otherIsExact) { // Can the two type filters be merged? In general, a more specific // type filter can replace a less specific type filter. IsOfFilter result; bool typesEqual = this.requiredType.EdmEquals(otherRequiredType); // The simplest case - the filters are equivalent if (typesEqual && this.isExact == otherIsExact) { result = this; } // Next simplest - two IsOfOnly filters can never be merged if the types are different // (and if the types were equal the above condition would have been satisfied). // SC_ else if (this.isExact && otherIsExact) { result = new IsOfFilter(otherRequiredType, otherIsExact); result.next = this; } // Two IsOf filters can potentially be adjusted - the more specific type filter should be kept, if present else if (!this.isExact && !otherIsExact) { // At this point the types cannot be equal. If one filter specifies a type that is a subtype of the other, // then the subtype filter is the one that should remain if (otherRequiredType.IsSubtypeOf(this.requiredType)) { result = new IsOfFilter(otherRequiredType, false); result.next = this.next; } else if (this.requiredType.IsSubtypeOf(otherRequiredType)) { result = this; } else { // The types are not related and the filters cannot be merged // Note that this case may not be possible since IsOf and OfType // both require an argument with a compatible type to the IsOf type. result = new IsOfFilter(otherRequiredType, otherIsExact); result.next = this; } } // One filter is an IsOf filter while the other is an IsOfOnly filter else { // For IsOf(T) AND IsOfOnly(T), the IsOf filter can be dropped if (typesEqual) { result = new IsOfFilter(otherRequiredType, true); result.next = this.next; } else { // Decide which is the 'IsOfOnly' type and which is the 'IsOf' type TypeUsage isOfOnlyType = (this.isExact ? this.requiredType : otherRequiredType); TypeUsage isOfType = (this.isExact ? otherRequiredType : this.requiredType); // IsOf(Super) && IsOfOnly(Sub) => IsOfOnly(Sub) // In all other cases, both filters remain - even though the IsOfOnly(Super) and IsOf(Sub) is obviously a contradiction. // SC_ if (isOfOnlyType.IsSubtypeOf(isOfType)) { if (object.ReferenceEquals(isOfOnlyType, this.requiredType) && this.isExact) { result = this; } else { result = new IsOfFilter(isOfOnlyType, true); result.next = this.next; } } else { result = new IsOfFilter(otherRequiredType, otherIsExact); result.next = this; } } } return result; } internal IsOfFilter Merge(DbIsOfExpression other) { return Merge(other.OfType, (other.ExpressionKind == DbExpressionKind.IsOfOnly)); } internal IsOfFilter Merge(DbOfTypeExpression other) { return Merge(other.OfType, (other.ExpressionKind == DbExpressionKind.OfTypeOnly)); } internal IEnumerable> ToEnumerable() { IsOfFilter currentFilter = this; while (currentFilter != null) { yield return new KeyValuePair (currentFilter.requiredType, currentFilter.isExact); currentFilter = currentFilter.next; } } } private DbFilterExpression CreateIsOfFilterExpression(DbExpression input, IsOfFilter typeFilter) { // Create a filter expression based on the IsOf/IsOfOnly operations specified by typeFilter DbExpressionBinding resultBinding = input.Bind(); List predicates = new List ( typeFilter.ToEnumerable().Select(tf => tf.Value ? resultBinding.Variable.IsOfOnly(tf.Key) : resultBinding.Variable.IsOf(tf.Key)).ToList() ); DbExpression predicate = Helpers.BuildBalancedTreeInPlace(predicates, (left, right) => left.And(right)); DbFilterExpression result = resultBinding.Filter(predicate); // Track the fact that this IsOfFilter was created by the ITreeGenerator itself and should // simply be converted to an ITree Node when it is encountered again by the visitor pass. _processedIsOfFilters.Add(result); return result; } private bool IsIsOfFilter(DbFilterExpression filter) { if(filter.Predicate.ExpressionKind != DbExpressionKind.IsOf && filter.Predicate.ExpressionKind != DbExpressionKind.IsOfOnly) { return false; } DbExpression isOfArgument = ((DbIsOfExpression)filter.Predicate).Argument; return (isOfArgument.ExpressionKind == DbExpressionKind.VariableReference && ((DbVariableReferenceExpression)isOfArgument).VariableName == filter.Input.VariableName); } private DbExpression ApplyIsOfFilter(DbExpression current, IsOfFilter typeFilter) { // An IsOf filter can be safely pushed down through the following expressions: // // Distinct // Filter - may be merged if the Filter is also an OfType filter // OfType - converted to Project(Filter(input, IsOf(T)), TreatAs(T)) and the Filter may be merged // Project - only for identity project // SC_ DbExpression result; switch(current.ExpressionKind) { case DbExpressionKind.Distinct: { result = ApplyIsOfFilter(((DbDistinctExpression)current).Argument, typeFilter).Distinct(); } break; case DbExpressionKind.Filter: { DbFilterExpression filter = (DbFilterExpression)current; if (IsIsOfFilter(filter)) { // If this is an IsOf filter, examine the interaction with the current filter we are trying to apply DbIsOfExpression isOfExp = (DbIsOfExpression)filter.Predicate; typeFilter = typeFilter.Merge(isOfExp); result = ApplyIsOfFilter(filter.Input.Expression, typeFilter); } else { // Otherwise, push the current IsOf filter under this filter DbExpression rewritten = ApplyIsOfFilter(filter.Input.Expression, typeFilter); result = rewritten.BindAs(filter.Input.VariableName).Filter(filter.Predicate); } } break; case DbExpressionKind.OfType: case DbExpressionKind.OfTypeOnly: { // Examine the interaction of this nested OfType filter with the OfType filter we are trying to apply // and construct an aggregated type filter (where possible) DbOfTypeExpression ofTypeExp = (DbOfTypeExpression)current; typeFilter = typeFilter.Merge(ofTypeExp); DbExpression rewrittenIsOf = ApplyIsOfFilter(ofTypeExp.Argument, typeFilter); DbExpressionBinding treatBinding = rewrittenIsOf.Bind(); DbTreatExpression treatProjection = treatBinding.Variable.TreatAs(ofTypeExp.OfType); _fakeTreats.Add(treatProjection); result = treatBinding.Project(treatProjection); } break; case DbExpressionKind.Project: { DbProjectExpression project = (DbProjectExpression)current; if(project.Projection.ExpressionKind == DbExpressionKind.VariableReference && ((DbVariableReferenceExpression)project.Projection).VariableName == project.Input.VariableName) { // If this is an identity-project, remove it by visiting the input expression result = ApplyIsOfFilter(project.Input.Expression, typeFilter); } else { // Otherwise, the projection is opaque to the IsOf rewrite result = CreateIsOfFilterExpression(current, typeFilter); } } break; case DbExpressionKind.Sort: { // The IsOf filter is applied to the Sort input, then the sort keys are reapplied to create a new Sort expression. DbSortExpression sort = (DbSortExpression)current; DbExpression sortInput = ApplyIsOfFilter(sort.Input.Expression, typeFilter); result = sortInput.BindAs(sort.Input.VariableName).Sort(sort.SortOrder); } break; default: { // This is not a recognized case, so simply apply the type filter to the expression. result = CreateIsOfFilterExpression(current, typeFilter); } break; } return result; } /// /// Build the equivalent of an OfTypeExpression over the input (ie) produce the set of values from the /// input that are of the desired type (exactly of the desired type, if the "includeSubtypes" parameter is false). /// /// Further more, "update" the result element type to be the desired type. /// /// We accomplish this by first building a FilterOp with an IsOf (or an IsOfOnly) predicate for the desired /// type. We then build out a ProjectOp over the FilterOp, where we introduce a "Fake" TreatOp over the input /// element to cast it to the right type. The "Fake" TreatOp is only there for "compile-time" typing reasons, /// and will be ignored in the rest of the plan compiler /// // the input collection // the single Var produced by the input collection // the desired element type // do we include subtypes of the desired element type // the result subtree // the single Var produced by the result subtree public override Node Visit(DbOfTypeExpression e) { // // The argument to OfType must be a collection // PlanCompiler.Assert(TypeSemantics.IsCollectionType(e.Argument.ResultType), "Non-Collection Type Argument in DbOfTypeExpression"); DbExpression rewrittenIsOfFilter = ApplyIsOfFilter(e.Argument, new IsOfFilter(e)); // // Visit the collection argument and ensure that it is a RelOp suitable for subsequent use in the Filter/Project used to convert OfType. // Node inputNode = EnsureRelOp(VisitExpr(rewrittenIsOfFilter)); // // Retrieve the Var produced by the RelOp input. // Var inputVar = _varMap[inputNode]; // // Build the Treat part of the OfType expression tree - note that this is a 'fake' // Treat because the underlying IsOf filter makes it unnecessary (as far as the // plan compiler is concerned). // Var resultVar; Node resultNode = _iqtCommand.BuildFakeTreatProject(inputNode, inputVar, e.OfType, out resultVar); // // Add the node-var mapping, and return // _varMap[resultNode] = resultVar; return resultNode; } public override Node Visit(DbNewInstanceExpression e) { Op newInstOp = null; ListrelPropertyExprs = null; if (TypeSemantics.IsCollectionType(e.ResultType)) { newInstOp = _iqtCommand.CreateNewMultisetOp(e.ResultType); } else if (TypeSemantics.IsRowType(e.ResultType)) { newInstOp = _iqtCommand.CreateNewRecordOp(e.ResultType); } else if (TypeSemantics.IsEntityType(e.ResultType)) { List relPropertyList = new List (); relPropertyExprs = new List (); if (e.HasRelatedEntityReferences) { foreach (DbRelatedEntityRef targetRef in e.RelatedEntityReferences) { RelProperty relProperty = new RelProperty((RelationshipType)targetRef.TargetEnd.DeclaringType, targetRef.SourceEnd, targetRef.TargetEnd); relPropertyList.Add(relProperty); Node relPropertyNode = VisitExprAsScalar(targetRef.TargetEntityReference); relPropertyExprs.Add(relPropertyNode); } } newInstOp = _iqtCommand.CreateNewEntityOp(e.ResultType, relPropertyList); } else { newInstOp = _iqtCommand.CreateNewInstanceOp(e.ResultType); } // // Build up the list of arguments. Make sure that they match // the expected types (and add "soft" casts, if needed) // List newArgs = new List (); if (TypeSemantics.IsStructuralType(e.ResultType)) { StructuralType resultType = TypeHelpers.GetEdmType (e.ResultType); int i = 0; foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(resultType)) { Node newArg = BuildSoftCast(VisitExprAsScalar(e.Arguments[i]), Helper.GetModelTypeUsage(m)); newArgs.Add(newArg); i++; } } else { CollectionType resultType = TypeHelpers.GetEdmType (e.ResultType); TypeUsage elementTypeUsage = resultType.TypeUsage; foreach (DbExpression arg in e.Arguments) { Node newArg = BuildSoftCast(VisitExprAsScalar(arg), elementTypeUsage); newArgs.Add(newArg); } } if (relPropertyExprs != null) { newArgs.AddRange(relPropertyExprs); } Node node = _iqtCommand.CreateNode(newInstOp, newArgs); return node; } public override Node Visit(DbRefExpression e) { // SQLBUDT #502617: Creating a collection of refs throws an Assert // A SoftCastOp may be required if the argument to the RefExpression is only promotable // to the row type produced from the key properties of the referenced Entity type. Since // this row type is not actually represented anywhere in the tree it must be built here in // order to determine whether or not the SoftCastOp should be applied. // Op op = _iqtCommand.CreateRefOp(e.EntitySet, e.ResultType); Node newArg = BuildSoftCast(VisitExprAsScalar(e.Argument), TypeHelpers.CreateKeyRowType(e.EntitySet.ElementType)); return _iqtCommand.CreateNode(op, newArg); } public override Node Visit(DbRelationshipNavigationExpression e) { RelProperty relProperty = new RelProperty(e.Relationship, e.NavigateFrom, e.NavigateTo); Op op = _iqtCommand.CreateNavigateOp(e.ResultType, relProperty); Node arg = VisitExprAsScalar(e.NavigationSource); return _iqtCommand.CreateNode(op, arg); } public override Node Visit(DbDerefExpression e) { Op op = _iqtCommand.CreateDerefOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbRefKeyExpression e) { Op op = _iqtCommand.CreateGetRefKeyOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbEntityRefExpression e) { Op op = _iqtCommand.CreateGetEntityRefOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbScanExpression e) { // Create a new table definition TableMD tableMetadata = Command.CreateTableDefinition(e.Target); // Create a scan table operator ScanTableOp op = _iqtCommand.CreateScanTableOp(tableMetadata); // Map the ScanTableOp to the ColumnVar of the Table's single column of the Extent's element type Node node = _iqtCommand.CreateNode(op); Var singleColumn = op.Table.Columns[0]; _varMap[node] = singleColumn; return node; } public override Node Visit(DbFilterExpression e) { if (!IsIsOfFilter(e) || _processedIsOfFilters.Contains(e)) { // // Visit the Predicate with the Input binding's variable in scope // Node inputSetNode = EnterExpressionBinding(e.Input); Node predicateNode = VisitExprAsPredicate(e.Predicate); ExitExpressionBinding(); Op filtOp = _iqtCommand.CreateFilterOp(); // Update the Node --> Var mapping. Filter maps to the same Var as its input. Node filtNode = _iqtCommand.CreateNode(filtOp, inputSetNode, predicateNode); _varMap[filtNode] = _varMap[inputSetNode]; return filtNode; } else { DbIsOfExpression isOfPredicate = (DbIsOfExpression)e.Predicate; DbExpression processed = ApplyIsOfFilter(e.Input.Expression, new IsOfFilter(isOfPredicate)); return this.VisitExpr(processed); } } public override Node Visit(DbProjectExpression e) { // check if this is the discriminated projection for a query mapping view if (e == this._discriminatedViewTopProject) { return GenerateDiscriminatedProject(e); } else { return GenerateStandardProject(e); } } private Node GenerateDiscriminatedProject(DbProjectExpression e) { PlanCompiler.Assert(null != _discriminatedViewTopProject, "if a project matches the pattern, there must be a corresponding discriminator map"); // convert the input to the top level projection Node source = EnterExpressionBinding(e.Input); List relPropertyList = new List (); List relPropertyExprs = new List (); foreach (KeyValuePair kv in _discriminatorMap.RelPropertyMap) { relPropertyList.Add(kv.Key); relPropertyExprs.Add(VisitExprAsScalar(kv.Value)); } // construct a DiscriminatedNewInstanceOp DiscriminatedNewEntityOp newInstOp = _iqtCommand.CreateDiscriminatedNewEntityOp(e.Projection.ResultType, new ExplicitDiscriminatorMap(_discriminatorMap), _discriminatorMap.EntitySet, relPropertyList); // args include all projected properties and discriminator and the relProperties List newArgs = new List (_discriminatorMap.PropertyMap.Count + 1); newArgs.Add(CreateNewInstanceArgument(_discriminatorMap.Discriminator.Property, _discriminatorMap.Discriminator)); foreach (var propertyMap in _discriminatorMap.PropertyMap) { DbExpression value = propertyMap.Value; EdmProperty property = propertyMap.Key; Node newArg = CreateNewInstanceArgument(property, value); newArgs.Add(newArg); } newArgs.AddRange(relPropertyExprs); Node newInstNode = _iqtCommand.CreateNode(newInstOp, newArgs); ExitExpressionBinding(); Var sourceVar; Node varDefListNode = _iqtCommand.CreateVarDefListNode(newInstNode, out sourceVar); ProjectOp projOp = _iqtCommand.CreateProjectOp(sourceVar); Node projNode = _iqtCommand.CreateNode(projOp, source, varDefListNode); _varMap[projNode] = sourceVar; return projNode; } private Node CreateNewInstanceArgument(EdmMember property, DbExpression value) { Node newArg = BuildSoftCast(VisitExprAsScalar(value), Helper.GetModelTypeUsage(property)); return newArg; } private Node GenerateStandardProject(DbProjectExpression e) { Node projectedSetNode = EnterExpressionBinding(e.Input); Node projectionNode = VisitExprAsScalar(e.Projection); ExitExpressionBinding(); Var projectionVar; Node varDefListNode = _iqtCommand.CreateVarDefListNode(projectionNode, out projectionVar); ProjectOp projOp = _iqtCommand.CreateProjectOp(projectionVar); Node projNode = _iqtCommand.CreateNode(projOp, projectedSetNode, varDefListNode); _varMap[projNode] = projectionVar; return projNode; } public override Node Visit(DbCrossJoinExpression e) { return VisitJoin(e, e.Inputs, null); } public override Node Visit(DbJoinExpression e) { List inputs = new List (); inputs.Add(e.Left); inputs.Add(e.Right); return VisitJoin(e, inputs, e.JoinCondition); } private Node VisitJoin(DbExpression e, IList inputs, DbExpression joinCond) { // // Assert that the JoinType is covered. If JoinTypes are added to CQT then the // switch statement that constructs the JoinOp must be updated, along with this assert. // PlanCompiler.Assert(DbExpressionKind.CrossJoin == e.ExpressionKind || DbExpressionKind.InnerJoin == e.ExpressionKind || DbExpressionKind.LeftOuterJoin == e.ExpressionKind || DbExpressionKind.FullOuterJoin == e.ExpressionKind, "Unrecognized JoinType specified in DbJoinExpression"); #if DEBUG // // Assert that the DbJoinExpression is producing a collection result with a record element type. // !!! IsCollectionOfRecord() is defined only in DEBUG !!! PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbJoinExpression"); #endif // // Bring the variables for the Join inputs into scope, track their nodes and vars, and visit the Join condition, if present. // List inputNodes = new List (); List inputVars = new List(); for(int idx = 0; idx < inputs.Count; idx++) { Node inputNode = EnterExpressionBinding(inputs[idx]); inputNodes.Add(inputNode); inputVars.Add(_varMap[inputNode]); } Node joinCondNode = VisitExprAsPredicate(joinCond); // // Remove the input variables from scope after visiting the Join condition. // for (int scopeCount = 0; scopeCount < inputNodes.Count; scopeCount++) { ExitExpressionBinding(); } // // Create an appropriate JoinOp based on the JoinType specified in the DbJoinExpression. // JoinBaseOp joinOp = null; switch (e.ExpressionKind) { case DbExpressionKind.CrossJoin: { joinOp = _iqtCommand.CreateCrossJoinOp(); } break; case DbExpressionKind.InnerJoin: { joinOp = _iqtCommand.CreateInnerJoinOp(); } break; case DbExpressionKind.LeftOuterJoin: { joinOp = _iqtCommand.CreateLeftOuterJoinOp(); } break; case DbExpressionKind.FullOuterJoin: { joinOp = _iqtCommand.CreateFullOuterJoinOp(); } break; } // // Assert that a JoinOp was produced. This check is again in case a new JoinType is introduced to CQT and this method is not updated. // PlanCompiler.Assert(joinOp != null, "Unrecognized JoinOp specified in DbJoinExpression, no JoinOp was produced"); // // If the Join condition was present then add its converted form to the list of child nodes for the new Join node. // if (e.ExpressionKind != DbExpressionKind.CrossJoin) { PlanCompiler.Assert(joinCondNode != null, "Non CrossJoinOps must specify a join condition"); inputNodes.Add(joinCondNode); } // // Create and return a new projection that unifies the multiple vars produced by the Join columns into a single record constructor. // return ProjectNewRecord( _iqtCommand.CreateNode(joinOp, inputNodes), ExtractElementRowType(e.ResultType), inputVars ); } public override Node Visit(DbApplyExpression e) { #if DEBUG // // Assert that the DbJoinExpression is producing a collection result with a record element type. // !!! IsCollectionOfRecord() is defined only in DEBUG !!! PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbApplyExpression"); #endif // // Bring the Input set's variable into scope // Node inputNode = EnterExpressionBinding(e.Input); // // Visit the Apply expression with the Input's variable in scope. // This is done via EnterExpressionBinding, which is allowable only because // it will only bring the Apply variable into scope *after* visiting the Apply expression // (which means that the Apply expression cannot validly reference its own binding variable) // Node applyNode = EnterExpressionBinding(e.Apply); // // Remove the Apply and Input variables from scope // ExitExpressionBinding(); // for the Apply ExitExpressionBinding(); // for the Input // // The ApplyType should only be either CrossApply or OuterApply. // PlanCompiler.Assert(DbExpressionKind.CrossApply == e.ExpressionKind || DbExpressionKind.OuterApply == e.ExpressionKind, "Unrecognized DbExpressionKind specified in DbApplyExpression"); // // Create a new Node with the correct ApplyOp as its Op and the input and apply nodes as its child nodes. // ApplyBaseOp applyOp = null; if (DbExpressionKind.CrossApply == e.ExpressionKind) { applyOp = _iqtCommand.CreateCrossApplyOp(); } else { applyOp = _iqtCommand.CreateOuterApplyOp(); } Node retNode = _iqtCommand.CreateNode(applyOp, inputNode, applyNode); // // Create and return a new projection that unifies the vars produced by the input and apply columns into a single record constructor. // return ProjectNewRecord( retNode, ExtractElementRowType(e.ResultType), new Var[] { _varMap[inputNode], _varMap[applyNode] } ); } public override Node Visit(DbGroupByExpression e) { #if DEBUG // !!! IsCollectionOfRecord() is defined only in DEBUG !!! PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "DbGroupByExpression has invalid result Type (not record collection)"); #endif // // Process the input and the keys // VarVec keyVarSet = _iqtCommand.CreateVarVec(); VarVec outputVarSet = _iqtCommand.CreateVarVec(); Node inputNode; List keyVarDefNodes; ExpressionBindingScope scope; ExtractKeys(e, keyVarSet, outputVarSet, out inputNode, out keyVarDefNodes, out scope); // Get the index of the group aggregate if any int groupAggregateIndex = -1; for (int i = 0; i < e.Aggregates.Count; i++) { if (e.Aggregates[i].GetType() == typeof(DbGroupAggregate)) { groupAggregateIndex = i; break; } } // //If there is a group aggregate, create a copy of the input // Node copyOfInput = null; List copyOfKeyVarDefNodes = null; VarVec copyOutputVarSet = _iqtCommand.CreateVarVec(); VarVec copyKeyVarSet = _iqtCommand.CreateVarVec(); if (groupAggregateIndex >= 0) { ExpressionBindingScope copyOfScope; //not needed ExtractKeys(e, copyKeyVarSet, copyOutputVarSet, out copyOfInput, out copyOfKeyVarDefNodes, out copyOfScope); } // // Bring the Input variable from the DbGroupByExpression into scope // scope = new ExpressionBindingScope(_iqtCommand, e.Input.GroupVariableName, scope.ScopeVar); _varScopes.Push(scope); // // Process the Aggregates: For each DbAggregate, produce the corresponding IQT conversion depending on whether the DbAggregate is a DbFunctionAggregate or DbGroupAggregate. // The converted Node is then used as the child node of a VarDefOp Node that is added to a list of Aggregate VarDefs or Group Aggregate VarDefs correspondingly. // The Var defined by the converted DbAggregate is added only to the overall list of Vars produced by the GroupBy (not the list of Keys). // List aggVarDefNodes = new List (); Node groupAggDefNode = null; for(int idx = 0; idx < e.Aggregates.Count; idx++) { DbAggregate agg = e.Aggregates[idx]; Var aggVar; // // Produce the converted form of the Arguments to the aggregate // IList argNodes = VisitExprAsScalar(agg.Arguments); // // Handle if it is DbFunctionAggregate // if (idx != groupAggregateIndex) { DbFunctionAggregate funcAgg = agg as DbFunctionAggregate; PlanCompiler.Assert(funcAgg != null, "Unrecognized DbAggregate used in DbGroupByExpression"); aggVarDefNodes.Add(ProcessFunctionAggregate(funcAgg, argNodes, out aggVar)); } // // Handle if it is DbGroupAggregate // else { groupAggDefNode = ProcessGroupAggregate(keyVarDefNodes, copyOfInput, copyOfKeyVarDefNodes, copyKeyVarSet, e.Input.Expression.ResultType, out aggVar); } outputVarSet.Set(aggVar); } // // The Aggregates have now been processed, so remove the group variable from scope. // ExitGroupExpressionBinding(); // // Construct the GroupBy. This consists of a GroupByOp (or GroupByIntoOp) with 3 (or 4) children: // 1. The Node produced from the Input set // 2. A VarDefListOp Node that uses the Key VarDefs to define the Key Vars (created above) // 3. A VarDefListOp Node that uses the Aggregate VarDefs to define the Aggregate Vars (created above) // 4. For a GroupByIntoOp a verDefLIstOp Node with a single var def node that defines the group aggregate // List groupByChildren = new List (); groupByChildren.Add(inputNode); // The Node produced from the Input set groupByChildren.Add( // The Key VarDefs _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), keyVarDefNodes )); groupByChildren.Add( // The Aggregate VarDefs _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), aggVarDefNodes )); GroupByBaseOp op; if (groupAggregateIndex >= 0) { groupByChildren.Add( // The GroupAggregate VarDef _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), groupAggDefNode )); op = _iqtCommand.CreateGroupByIntoOp(keyVarSet, this._iqtCommand.CreateVarVec(_varMap[inputNode]), outputVarSet); } else { op = _iqtCommand.CreateGroupByOp(keyVarSet, outputVarSet); } Node groupByNode = _iqtCommand.CreateNode( op, groupByChildren); // // Create and return a projection that unifies the multiple output vars of the GroupBy into a single record constructor. // return ProjectNewRecord( groupByNode, ExtractElementRowType(e.ResultType), outputVarSet //todo: it is not correct to pass a varvec where an ordered list is expected ); } private void ExtractKeys(DbGroupByExpression e, VarVec keyVarSet, VarVec outputVarSet, out Node inputNode, out List keyVarDefNodes, out ExpressionBindingScope scope) { inputNode = EnterGroupExpressionBinding(e.Input); // // Process the Keys: For each Key, produce the corresponding IQT conversion. // The converted Node is then used as the child node of a VarDefOp Node that is // added to a list of Key VarDefs. The Var defined by the converted Key expression // is added to both the overall list of Vars produced by the GroupBy and the list of Key vars produced by the GroupBy. // keyVarDefNodes = new List (); for (int idx = 0; idx < e.Keys.Count; idx++) { DbExpression keyExpr = e.Keys[idx]; Node keyNode = VisitExprAsScalar(keyExpr); ScalarOp keyOp = keyNode.Op as ScalarOp; // // In a valid CQT, each group key expressions will result in a ScalarOp since they // must be of an equality comparable type. // PlanCompiler.Assert(keyOp != null, "GroupBy Key is not a ScalarOp"); // // Create a ComputedVar with the same type as the Key and add it to both the set of output Vars produced by the GroupBy and the set of Key vars. // Var keyVar; // // Create a VarDefOp that uses the converted form of the Key to define the ComputedVar and add it to the list of Key VarDefs. // keyVarDefNodes.Add(_iqtCommand.CreateVarDefNode(keyNode, out keyVar)); outputVarSet.Set(keyVar); keyVarSet.Set(keyVar); } // // Before the Aggregates are processed, the Input variable must be taken out of scope and the 'group' variable introduced into scope in its place // This is done as follows: // 1. Pop the current ExpressionBindingScope from the stack // 2. Create a new ExpressionBindingScope using the same Var but the name of the 'group' variable from the DbGroupByExpression's DbGroupExpressionBinding // 3. Push this new scope onto the variable scope stack. // scope = ExitExpressionBinding(); } private Node ProcessFunctionAggregate(DbFunctionAggregate funcAgg, IList argNodes, out Var aggVar) { Node aggNode = _iqtCommand.CreateNode( _iqtCommand.CreateAggregateOp(funcAgg.Function, funcAgg.Distinct), argNodes ); // // Create a VarDefOp that uses the converted form of the DbAggregate to define the ComputedVar // return _iqtCommand.CreateVarDefNode(aggNode, out aggVar); } /// /// Translation for GroupAggregate /// /// Create the translation as : /// /// Collect /// | /// PhysicalProject /// | /// GroupNodeDefinition /// /// Here, GroupNodeDefinition is: /// 1. If there are no keys: copyOfInput; /// 2. If there are keys: /// /// Filter (keyDef1 = copyOfKeyDef1 or keyDef1 is null and copyOfKeyDef1 is null) and ... and (keyDefn = copyOfKeyDefn or keyDefn is null and copyOfKeyDefn is null) /// | /// Project (copyOfInput, copyOfKeyDef1, copyOfKeyDef1, ... copyOfKeyDefn) /// | /// copyOfInput /// /// /// /// /// /// /// /// ///private Node ProcessGroupAggregate(List keyVarDefNodes, Node copyOfInput, List copyOfkeyVarDefNodes, VarVec copyKeyVarSet, TypeUsage inputResultType, out Var groupAggVar) { Var inputVar = this._varMap[copyOfInput]; Node groupDefNode = copyOfInput; if (keyVarDefNodes.Count > 0) { VarVec projectOutpus = _iqtCommand.CreateVarVec(); projectOutpus.Set(inputVar); projectOutpus.Or(copyKeyVarSet); Node projectNodeWithKeys = _iqtCommand.CreateNode( _iqtCommand.CreateProjectOp(projectOutpus), groupDefNode, //the input _iqtCommand.CreateNode( //the key var defs _iqtCommand.CreateVarDefListOp(), copyOfkeyVarDefNodes )); List flattentedKeys = new List (); List copyFlattenedKeys = new List (); for (int i = 0; i < keyVarDefNodes.Count; i++) { Node keyVarDef = keyVarDefNodes[i]; Node copyOfKeyVarDef = copyOfkeyVarDefNodes[i]; Var keyVar = ((VarDefOp)keyVarDef.Op).Var; Var copyOfKeyVar = ((VarDefOp)copyOfKeyVarDef.Op).Var; // // The keys of type row need to be flattened, because grouping by a row means grouping by its individual // members and thus we have to check the individual members whether they are null. // IsNull(x) where x is a row type does not mean whether the individual properties of x are null, // but rather whether the entire row is null. // FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(keyVar)), flattentedKeys); FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(copyOfKeyVar)), copyFlattenedKeys); } PlanCompiler.Assert(flattentedKeys.Count == copyFlattenedKeys.Count, "The flattened keys lists should have the same nubmer of elements"); Node filterPredicateNode = null; for(int j = 0; j< flattentedKeys.Count; j++) { Node keyNode = flattentedKeys[j]; Node copyKeyNode = copyFlattenedKeys[j]; // // Create the predicate for a single key // keyVar = copyOfKeyVar or keyVar is null and copyOfKeyVar is null // Node predicate = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Or), _iqtCommand.CreateNode( _iqtCommand.CreateComparisonOp(OpType.EQ), keyNode, copyKeyNode), _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.And), _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.IsNull), OpCopier.Copy(_iqtCommand, keyNode)), _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.IsNull), OpCopier.Copy(_iqtCommand, copyKeyNode)))); if (filterPredicateNode == null) { filterPredicateNode = predicate; } else { filterPredicateNode = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.And), filterPredicateNode, predicate); } } Node filterNode = _iqtCommand.CreateNode( _iqtCommand.CreateFilterOp(), projectNodeWithKeys, filterPredicateNode); groupDefNode = filterNode; } //Cap with Collect over PhysicalProject _varMap[groupDefNode] = inputVar; groupDefNode = ConvertRelOpToScalarOpTree(groupDefNode, inputResultType); Node result = _iqtCommand.CreateVarDefNode(groupDefNode, out groupAggVar); return result; } /// /// If the return type of the input node is a RowType it flattens its individual non-row properties. /// The produced nodes are added to the given flattenedProperties list /// /// /// private void FlattenProperties(Node input, IListflattenedProperties) { if (input.Op.Type.EdmType.BuiltInTypeKind == BuiltInTypeKind.RowType) { IList properties = TypeHelpers.GetProperties(input.Op.Type); PlanCompiler.Assert(properties.Count != 0, "No nested properties for RowType"); for (int i = 0; i < properties.Count; i++) { Node newInput = (i == 0) ? input : OpCopier.Copy(_iqtCommand, input); FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreatePropertyOp(properties[i]), newInput), flattenedProperties); } } else { flattenedProperties.Add(input); } } /// /// Common processing for the identical input and sort order arguments to the unrelated /// DbSkipExpression and DbSortExpression types. /// /// The input DbExpressionBinding from the DbSkipExpression or DbSortExpression /// The list of SortClauses from the DbSkipExpression or DbSortExpression /// A list to contain the converted SortKeys produced from the SortClauses /// The Var produced by the input to the DbSkipExpression or DbSortExpression ////// The converted form of the input to the DbSkipExpression or DbSortExpression, capped by a /// ProjectOp that defines and Vars referenced by the SortKeys. /// private Node VisitSortArguments(DbExpressionBinding input, IListsortOrder, List sortKeys, out Var inputVar) { // // Skip/DbSortExpression conversion first produces a ProjectOp over the original input. // This is done to ensure that the new (Constrained)SortOp itself does not // contain any local variable definitions (in the form of a VarDefList child node) // which makes it simpler to pull SortOps over ProjectOps later in the PlanCompiler // (specifically the PreProcessor). // The new ProjectOp projects the output Var of the input along with any Vars referenced // by the SortKeys, and its VarDefList child defines those Vars. // // Bring the variable defined by the DbSortExpression's input set into scope // and retrieve it from the Node => Var map for later use. // Node inputNode = EnterExpressionBinding(input); inputVar = _varMap[inputNode]; // // Convert the SortClauses, building a new VarDefOp Node for each one. // VarVec projectedVars = _iqtCommand.CreateVarVec(); projectedVars.Set(inputVar); List sortVarDefs = new List (); PlanCompiler.Assert(sortKeys.Count == 0, "Non-empty SortKey list before adding converted SortClauses"); for (int idx = 0; idx < sortOrder.Count; idx++) { DbSortClause clause = sortOrder[idx]; // // Convert the DbSortClause DbExpression to a Node/Op pair // Node exprNode = VisitExprAsScalar(clause.Expression); // // In a valid CQT, DbSortClause expressions must have a result of an OrderComparable Type, // and such expressions will always convert to ScalarOps. // ScalarOp specOp = exprNode.Op as ScalarOp; PlanCompiler.Assert(specOp != null, "DbSortClause Expression converted to non-ScalarOp"); // // Create a new ComputedVar with the same Type as the result Type of the DbSortClause DbExpression // Var specVar; // // Create a new VarDefOp Node that defines the ComputedVar and add it both to the // list of VarDefs and the VarVec of produced Vars that will be used to create a // SortKey-defining ProjectOp over the Sort input. // sortVarDefs.Add(_iqtCommand.CreateVarDefNode(exprNode, out specVar)); projectedVars.Set(specVar); // // Create a new IQT SortKey that references the ComputedVar and has the same // Ascending and Collation as the original DbSortClause, then add it to the list of SortKeys. // SortKey sortKey = null; if (string.IsNullOrEmpty(clause.Collation)) { sortKey = Command.CreateSortKey(specVar, clause.Ascending); } else { sortKey = Command.CreateSortKey(specVar, clause.Ascending, clause.Collation); } sortKeys.Add(sortKey); } // // Now that the SortClauses have been converted, remove the Input set's variable from scope. // ExitExpressionBinding(); // // Cap the Input with a ProjectOp that pushes the sort key VarDefs down to that projection. // inputNode = _iqtCommand.CreateNode( _iqtCommand.CreateProjectOp(projectedVars), inputNode, _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), sortVarDefs ) ); return inputNode; } public override Node Visit(DbSkipExpression expression) { // // Invoke common processing of Skip/DbSortExpression arguments. // Var inputVar; List sortKeys = new List (); Node inputNode = VisitSortArguments(expression.Input, expression.SortOrder, sortKeys, out inputVar); // // Visit the Skip Count // Node countNode = VisitExprAsScalar(expression.Count); // // Create a new Node that has a new ConstrainedSortOp based on the SortKeys as its Op // and the following children: // - The Input node from VisitSortArguments // - The converted form of the skip count // - A NullOp of type Int64 to indicate that no limit operation is applied // Node skipNode = _iqtCommand.CreateNode( _iqtCommand.CreateConstrainedSortOp(sortKeys), inputNode, countNode, _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)) ); // Update the Node --> Var mapping for the new ConstrainedSort Node. // ConstrainedSortOp maps to the same Op that its RelOp input maps to. _varMap[skipNode] = inputVar; return skipNode; } public override Node Visit(DbSortExpression e) { // // Invoke common processing of Skip/DbSortExpression arguments. // Var inputVar; List sortKeys = new List (); Node inputNode = VisitSortArguments(e.Input, e.SortOrder, sortKeys, out inputVar); // // Create a new SortOp that uses the constructed SortKeys. // SortOp newSortOp = _iqtCommand.CreateSortOp(sortKeys); // // Create a new SortOp Node that has the new SortOp as its Op the Key-defining ProjectOp Node as its only child. // Node newSortNode = _iqtCommand.CreateNode(newSortOp, inputNode); // Update the Node --> Var mapping for the new Sort Node. // SortOp maps to the same Op that its RelOp input maps to. _varMap[newSortNode] = inputVar; return newSortNode; } public override Node Visit(DbQuantifierExpression e) { Node retNode = null; // // Any converts to Exists(Filter(Input, Predicate)) // All converts to Not(Exists(Filter(Input, Or(Not(Predicate), IsNull(Predicate))))) // PlanCompiler.Assert(DbExpressionKind.Any == e.ExpressionKind || DbExpressionKind.All == e.ExpressionKind, "Invalid DbExpressionKind in DbQuantifierExpression"); // // Bring the input's variable into scope // Node inputNode = EnterExpressionBinding(e.Input); // // Convert the predicate // Node predicateNode = VisitExprAsPredicate(e.Predicate); // // If the quantifier is All then the predicate must become 'Not(Predicate) Or IsNull(Predicate)', // since the converted form of the predicate should exclude a member of the input set if and only if // the predicate evaluates to False - filtering only with the negated predicate would also exclude members // for which that negated predicate evaluates to null, possibly resulting in an erroneous empty result set // and causing the quantifier to produce a false positive result. // if (DbExpressionKind.All == e.ExpressionKind) { // Create the 'Not(Predicate)' branch of the Or. predicateNode = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Not), predicateNode ); // Visit the original predicate for use in the 'IsNull(Predicate)' branch of the Or. // Note that this is treated as a scalar value rather than a Boolean predicate. Node predicateCopy = VisitExprAsScalar(e.Predicate); // Create the 'IsNull(Predicate)' branch of the Or. predicateCopy = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.IsNull), predicateCopy ); // Finally, combine the branches with a Boolean 'Or' Op to create the updated predicate node. predicateNode = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Or), predicateNode, predicateCopy ); } // // Remove the input's variable from scope // ExitExpressionBinding(); // // Create a FilterOp around the original input set and map the FilterOp to the Var produced by the original input set. // Var inputVar = _varMap[inputNode]; inputNode = _iqtCommand.CreateNode(_iqtCommand.CreateFilterOp(), inputNode, predicateNode); _varMap[inputNode] = inputVar; // // Create an ExistsOp around the filtered set to perform the quantifier operation. // retNode = _iqtCommand.CreateNode(_iqtCommand.CreateExistsOp(), inputNode); // // For All, the exists operation as currently built must now be negated. // if (DbExpressionKind.All == e.ExpressionKind) { retNode = _iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), retNode); } return retNode; } #endregion } } // 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.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class... using System.Data; using System.Data.Common; using System.Data.Metadata.Edm; using System.Data.Common.CommandTrees; using System.Data.Common.CommandTrees.ExpressionBuilder; using System.Data.Common.CommandTrees.Internal; using System.Data.Common.EntitySql; using System.Data.Query.InternalTrees; using System.Linq; using System.Text; using System.Data.Common.Utils; namespace System.Data.Query.PlanCompiler { internal class ITreeGenerator : DbExpressionVisitor{ #region Nested Types /// /// Abstract base class for both DbExpressionBinding and LambdaFunction scopes /// private abstract class CqtVariableScope { internal abstract bool Contains(string varName); internal abstract Node this[string varName] { get; } } ////// Represents a variable scope introduced by a CQT DbExpressionBinding, and therefore contains a single variable. /// private class ExpressionBindingScope : CqtVariableScope { private Command _tree; private string _varName; private Var _var; internal ExpressionBindingScope(Command iqtTree, string name, Var iqtVar) { _tree = iqtTree; _varName = name; _var = iqtVar; } internal override bool Contains(string name) { return (_varName == name); } internal override Node this[string name] { get { PlanCompiler.Assert(name == _varName,"huh?"); return _tree.CreateNode(_tree.CreateVarRefOp(_var)); } } internal Var ScopeVar { get { return _var; } } } ////// Represents a variable scope introduced by a LambdaFunction. /// private sealed class LambdaScope : CqtVariableScope { private readonly ITreeGenerator _treeGen; private readonly Command _command; private readonly Dictionary_arguments; private readonly Dictionary _referencedArgs; internal LambdaScope(ITreeGenerator treeGen, Command command, Dictionary args) { _treeGen = treeGen; _command = command; _arguments = args; _referencedArgs = new Dictionary (_arguments.Count); } internal override bool Contains(string name) { return (_arguments.ContainsKey(name)); } internal override Node this[string name] { get { PlanCompiler.Assert(_arguments.ContainsKey(name), "LambdaScope indexer called for invalid Var"); Node argNode = _arguments[name]; if (_referencedArgs.ContainsKey(argNode)) { // The specified argument has already been substituted into the // IQT and so this substitution requires a copy of the argument. VarMap mappedVars = null; // This is a 'deep copy' operation that clones the entire subtree rooted at the node. Node argCopy = OpCopier.Copy(_command, argNode, out mappedVars); // If any Nodes in the copy of the argument produce Vars then the // Node --> Var map must be updated to include them. if (mappedVars.Count > 0) { List sources = new List (1); sources.Add(argNode); List copies = new List (1); copies.Add(argCopy); MapCopiedNodeVars(sources, copies, mappedVars); } argNode = argCopy; } else { // This is the first reference of the lambda argument, so the Node itself // can be returned rather than a copy, but the dictionary that tracks // whether or not an argument has been referenced needs to be updated. _referencedArgs[argNode] = true; } return argNode; } } private void MapCopiedNodeVars(IList sources, IList copies, Dictionary varMappings) { PlanCompiler.Assert(sources.Count == copies.Count, "Source/Copy Node count mismatch"); // // For each Source/Copy Node in the two lists: // - Recursively update the Node --> Var map for any child nodes // - If the Source Node is mapped to a Var, then retrieve the new Var // produced by the Op copier that corresponds to that Source Var, and // add an entry to the Node --> Var map that maps the Copy Node to the // new Var. // for (int idx = 0; idx < sources.Count; idx++) { Node sourceNode = sources[idx]; Node copyNode = copies[idx]; if (sourceNode.Children.Count > 0) { MapCopiedNodeVars(sourceNode.Children, copyNode.Children, varMappings); } Var sourceVar = null; if (_treeGen.VarMap.TryGetValue(sourceNode, out sourceVar)) { PlanCompiler.Assert(varMappings.ContainsKey(sourceVar), "No mapping found for Var in Var to Var map from OpCopier"); this._treeGen.VarMap[copyNode] = varMappings[sourceVar]; } } } } #endregion private static Dictionary s_opMap = InitializeExpressionKindToOpTypeMap(); private readonly Command _iqtCommand; private readonly Stack _varScopes = new Stack (); private readonly Dictionary _varMap = new Dictionary (); private readonly Stack _functionExpansions = new Stack (); /// /// Maintained only for model functions with user-defined body. /// private readonly Dictionary_functionsIsPredicateFlag = new Dictionary (); // Used to track which IsOf type filter expressions have already been processed private readonly HashSet _processedIsOfFilters = new HashSet (); private readonly HashSet _fakeTreats = new HashSet (); // leverage discriminator metadata in the top-level project when translating query mapping views... private readonly System.Data.Mapping.ViewGeneration.DiscriminatorMap _discriminatorMap; private readonly DbProjectExpression _discriminatedViewTopProject; /// /// Initialize the DbExpressionKind --> OpType mappings for DbComparisonExpression and DbArithmeticExpression /// private static DictionaryInitializeExpressionKindToOpTypeMap() { Dictionary opMap = new Dictionary (12); // // Arithmetic operators // opMap[DbExpressionKind.Plus] = OpType.Plus; opMap[DbExpressionKind.Minus] = OpType.Minus; opMap[DbExpressionKind.Multiply] = OpType.Multiply; opMap[DbExpressionKind.Divide] = OpType.Divide; opMap[DbExpressionKind.Modulo] = OpType.Modulo; opMap[DbExpressionKind.UnaryMinus] = OpType.UnaryMinus; // // Comparison operators // opMap[DbExpressionKind.Equals] = OpType.EQ; opMap[DbExpressionKind.NotEquals] = OpType.NE; opMap[DbExpressionKind.LessThan] = OpType.LT; opMap[DbExpressionKind.GreaterThan] = OpType.GT; opMap[DbExpressionKind.LessThanOrEquals] = OpType.LE; opMap[DbExpressionKind.GreaterThanOrEquals] = OpType.GE; return opMap; } internal Dictionary VarMap { get { return _varMap; } } public static Command Generate(DbQueryCommandTree ctree) { return Generate(ctree, null); } /// /// Generate an IQT given a query command tree and discriminator metadata (available for certain query mapping views) /// internal static Command Generate(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap) { ITreeGenerator treeGenerator = new ITreeGenerator(ctree, discriminatorMap); return treeGenerator._iqtCommand; } private ITreeGenerator(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap) { // // Create a new IQT Command instance that uses the same metadata workspace as the incoming command tree // _iqtCommand = new Command(ctree.MetadataWorkspace); // // When translating a query mapping view matching the TPH discrimination pattern, remember the top level discriminator map // (leveraged to produced a DiscriminatedNewInstanceOp for the top-level projection in the view) // if (null != discriminatorMap) { _discriminatorMap = discriminatorMap; // see System.Data.Mapping.ViewGeneration.DiscriminatorMap PlanCompiler.Assert(ctree.Query.ExpressionKind == DbExpressionKind.Project, "top level QMV expression must be project to match discriminator pattern"); _discriminatedViewTopProject = (DbProjectExpression)ctree.Query; } // // For each Parameter declared by the command tree, add a ParameterVar to the set of parameter vars maintained by the conversion visitor. // Each ParameterVar has the same name and type as the corresponding parameter on the command tree. // foreach (KeyValuePairparamInfo in ctree.Parameters) { if (!ValidateParameterType(paramInfo.Value)) { throw EntityUtil.NotSupported(System.Data.Entity.Strings.ParameterTypeNotSupported(paramInfo.Key, paramInfo.Value.ToString())); } _iqtCommand.CreateParameterVar(paramInfo.Key, paramInfo.Value); } // Convert into an ITree _iqtCommand.Root = VisitExpr(ctree.Query); // // If the root of the tree is not a relop, build up a fake project over a // a singlerowtableOp. // "s" => Project(SingleRowTableOp, "s") // if (!_iqtCommand.Root.Op.IsRelOp) { Node scalarExpr = ConvertToScalarOpTree(_iqtCommand.Root, ctree.Query); Node singletonTableNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowTableOp()); Var newVar; Node varDefListNode = _iqtCommand.CreateVarDefListNode(scalarExpr, out newVar); ProjectOp projectOp = _iqtCommand.CreateProjectOp(newVar); Node newRoot = _iqtCommand.CreateNode(projectOp, singletonTableNode, varDefListNode); if (TypeSemantics.IsCollectionType(_iqtCommand.Root.Op.Type)) { UnnestOp unnestOp = _iqtCommand.CreateUnnestOp(newVar); newRoot = _iqtCommand.CreateNode(unnestOp, varDefListNode.Child0); newVar = unnestOp.Table.Columns[0]; } _iqtCommand.Root = newRoot; _varMap[_iqtCommand.Root] = newVar; } // // Ensure that the topmost portion of the query is capped by a // PhysicalProject expression // _iqtCommand.Root = CapWithPhysicalProject(_iqtCommand.Root); } private static bool ValidateParameterType(TypeUsage paramType) { return (paramType != null && paramType.EdmType != null && (TypeSemantics.IsPrimitiveType(paramType) || paramType.EdmType is EnumType)); } #region DbExpressionVisitor Helpers private static RowType ExtractElementRowType(TypeUsage typeUsage) { return TypeHelpers.GetEdmType (TypeHelpers.GetEdmType (typeUsage).TypeUsage); } #if DEBUG private static bool IsCollectionOfRecord(TypeUsage typeUsage) { CollectionType collectionType; return (TypeHelpers.TryGetEdmType (typeUsage, out collectionType) && collectionType != null && TypeSemantics.IsRowType(collectionType.TypeUsage)); } #endif /// /// Is the current expression a predicate? /// /// expr to check ///true, if the expression is a predicate private bool IsPredicate(DbExpression expr) { if (TypeSemantics.IsPrimitiveType(expr.ResultType, PrimitiveTypeKind.Boolean)) { switch (expr.ExpressionKind) { case DbExpressionKind.Equals: case DbExpressionKind.NotEquals: case DbExpressionKind.LessThan: case DbExpressionKind.LessThanOrEquals: case DbExpressionKind.GreaterThan: case DbExpressionKind.GreaterThanOrEquals: case DbExpressionKind.And: case DbExpressionKind.Or: case DbExpressionKind.Not: case DbExpressionKind.Like: case DbExpressionKind.IsEmpty: case DbExpressionKind.IsNull: case DbExpressionKind.IsOf: case DbExpressionKind.IsOfOnly: case DbExpressionKind.Any: case DbExpressionKind.All: return true; case DbExpressionKind.Lambda: // return IsPredicate(((DbLambdaExpression)expr).Lambda.Body); case DbExpressionKind.Function: { // EdmFunction edmFunction = ((DbFunctionExpression)expr).Function; if (edmFunction.HasUserDefinedBody) { bool isPredicateFunction; if (_functionsIsPredicateFlag.TryGetValue(edmFunction, out isPredicateFunction)) { return isPredicateFunction; } else { // It is important that IsPredicate is called after the expression has been visited, otherwise // _functionsIsPredicateFlag map will not contain an entry for the function with a definition PlanCompiler.Assert(false, "IsPredicate must be called on a visited function expression"); return false; } } else { return false; } } default: return false; } } else { return false; } } ////// Callback to process an expression /// /// The expression to convert ///private delegate Node VisitExprDelegate(DbExpression e); private Node VisitExpr(DbExpression e) { if (e == null) { return null; } else { return e.Accept (this); } } /// /// Convert this expression into a "scalar value" ITree expression. There are two main /// /// ///private Node VisitExprAsScalar(DbExpression expr) { if (expr == null) { return null; } Node node = VisitExpr(expr); // the real work node = ConvertToScalarOpTree(node, expr); return node; } /// /// Convert an Itree node into a scalar op tree /// /// the subtree /// the original CQT expression ///the converted subtree private Node ConvertToScalarOpTree(Node node, DbExpression expr) { // // If the current expression is a collection, and we've simply produced a RelOp // then we need to add a CollectOp above a PhysicalProjectOp above the RelOp // if (node.Op.IsRelOp) { node = ConvertRelOpToScalarOpTree(node, expr.ResultType); } // // If the current expression is a boolean, and it is really a predicate, then // scalarize the predicate (ie) convert it into a "case whenthen 'true' else 'false' end" expression // SQLBUDT #431406: handle 3-valued logic for all predicates except IsNull // Convert boolean predicate p into // case when p then true when not(p) then false else null end // else if (IsPredicate(expr)) { CaseOp caseOp = _iqtCommand.CreateCaseOp(_iqtCommand.BooleanType); //For 2-valued logic there are 3 arguments, for 3-valued there are 5 List arguments = new List ((expr.ExpressionKind == DbExpressionKind.IsNull) ? 3 : 5); //Add the original as the first when arguments.Add(node); //Add the first then, the true node arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true))); //If the expression has 3-valued logic, add a second when if (expr.ExpressionKind != DbExpressionKind.IsNull) { Node predCopy = VisitExpr(expr); arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), predCopy)); } //Add the false node: for 3 valued logic this is the second then, for 2 valued the else arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, false))); //The null node, it is the else-clause for 3-valued logic if (expr.ExpressionKind != DbExpressionKind.IsNull) { arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.BooleanType))); } node = _iqtCommand.CreateNode(caseOp, arguments); } return node; } /// /// Convert a rel op Itree node into a scalar op tree /// /// /// ///private Node ConvertRelOpToScalarOpTree(Node node, TypeUsage resultType) { PlanCompiler.Assert(TypeSemantics.IsCollectionType(resultType), "RelOp with non-Collection result type"); CollectOp collectOp = _iqtCommand.CreateCollectOp(resultType); // // I'm not thrilled about having to build a PhysicalProjectOp here - this // is definitely something I will need to revisit soon // Node projectNode = CapWithPhysicalProject(node); node = _iqtCommand.CreateNode(collectOp, projectNode); return node; } /// /// Convert an expression into an iqt predicate /// /// the expression to process ///private Node VisitExprAsPredicate(DbExpression expr) { if (expr == null) { return null; } Node node = VisitExpr(expr); // // If the current expression is not a predicate, then we need to make it one, by // comparing it with the constant 'true' // if (!IsPredicate(expr)) { ComparisonOp comparisonOp = _iqtCommand.CreateComparisonOp(OpType.EQ); Node trueNode = _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)); node = _iqtCommand.CreateNode(comparisonOp, node, trueNode); } else { PlanCompiler.Assert(!node.Op.IsRelOp, "unexpected relOp as predicate?"); } return node; } /// /// Process a list of expressions, and apply the delegate to each of the expressions /// /// list of cqt expressions to process /// the callback to apply ///a list of IQT expressions private static IListVisitExpr(IList exprs, VisitExprDelegate exprDelegate) { List nodeList = new List (); for(int idx = 0; idx < exprs.Count; idx++) { nodeList.Add(exprDelegate(exprs[idx])); } return nodeList; } /// /// Process a set of cqt expressions - and convert them into scalar iqt expressions /// /// list of cqt expressions ///list of iqt expressions private IListVisitExprAsScalar(IList exprs) { return VisitExpr(exprs, VisitExprAsScalar); } private Node VisitUnary(DbUnaryExpression e, Op op, VisitExprDelegate exprDelegate) { return _iqtCommand.CreateNode(op, exprDelegate(e.Argument)); } private Node VisitBinary(DbBinaryExpression e, Op op, VisitExprDelegate exprDelegate) { return _iqtCommand.CreateNode(op, exprDelegate(e.Left), exprDelegate(e.Right)); } /// /// Ensures that an input op is a RelOp. If the specified Node's Op is not a RelOp then it is wrapped in an Unnest to create a synthetic RelOp. This is only possible if the input Op produces a collection. /// /// The input Node/Op pair ///A Node with an Op that is guaranteed to be a RelOp (this may be the original Node or a new Node created to perform the Unnest) private Node EnsureRelOp(Node inputNode) { // // Input node = N1 // Op inputOp = inputNode.Op; // // If the Op is already a RelOp then simply return its Node // if (inputOp.IsRelOp) { return inputNode; } // // Assert that the input is a ScalarOp (CQT expressions should only ever produce RelOps or ScalarOps) // ScalarOp scalar = inputOp as ScalarOp; PlanCompiler.Assert(scalar != null, "An expression in a CQT produced a non-ScalarOp and non-RelOp output Op"); // // Assert that the ScalarOp has a collection result type. EnsureRelOp is called to ensure that arguments to // RelOps are either also RelOps or are ScalarOps that produce a collection, which can be wrapped in an // unnest to produce a RelOp. // PlanCompiler.Assert(TypeSemantics.IsCollectionType(scalar.Type), "An expression used as a RelOp argument was neither a RelOp or a collection"); // // If the ScalarOp represents the nesting of an existing RelOp, simply return that RelOp instead. // CollectOp(PhysicalProjectOp(x)) => x // CollectOp collect = inputOp as CollectOp; if (collect != null) { PlanCompiler.Assert(inputNode.HasChild0, "CollectOp without argument"); if (inputNode.Child0.Op as PhysicalProjectOp != null) { PlanCompiler.Assert(inputNode.Child0.HasChild0, "PhysicalProjectOp without argument"); PlanCompiler.Assert(inputNode.Child0.Child0.Op.IsRelOp, "PhysicalProjectOp applied to non-RelOp input"); // // The structure of the Input is Collect(PhysicalProject(x)), so return x // return inputNode.Child0.Child0; } } // // Create a new VarDefOp that defines the computed var that represents the ScalarOp collection. // This var is the input to the UnnestOp. // varDefNode = N2 // Var inputCollectionVar; Node varDefNode = _iqtCommand.CreateVarDefNode(inputNode, out inputCollectionVar); // // Create an UnnestOp that references the computed var created above. The VarDefOp that defines the var // using the original input Node/Op pair becomes a child of the UnnestOp. // UnnestOp unnest = _iqtCommand.CreateUnnestOp(inputCollectionVar); PlanCompiler.Assert(unnest.Table.Columns.Count == 1, "Unnest of collection ScalarOp produced unexpected number of columns (1 expected)"); // // Create the unnest node, N3 // The UnnestOp produces a new Var, the single ColumnVar produced by the table that results from the Unnest. // Node unnestNode = _iqtCommand.CreateNode(unnest, varDefNode); _varMap[unnestNode] = unnest.Table.Columns[0]; // // Create a Project node above the Unnest, so we can simplify the work to eliminate // the Unnest later. That means we need to create a VarRef to the column var in the // table, a VarDef to define it, and a VarDefList to hold it, then a Project node, N4, // which we return. // Var projectVar; Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(unnest.Table.Columns[0])); Node varDefListNode = _iqtCommand.CreateVarDefListNode(varRefNode, out projectVar); ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar); Node projectNode = _iqtCommand.CreateNode(projectOp, unnestNode, varDefListNode); _varMap[projectNode] = projectVar; return projectNode; } ////// Cap a RelOp with a ProjectOp. The output var of the Project is the /// output var from the input /// /// the input relop tree ///the relop tree with a projectNode at the root private Node CapWithProject(Node input) { PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); if (input.Op.OpType == OpType.Project) { return input; } // Get the Var from the input; and build up a Project above it Var inputVar = _varMap[input]; ProjectOp projectOp = _iqtCommand.CreateProjectOp(inputVar); Node projectNode = _iqtCommand.CreateNode(projectOp, input, _iqtCommand.CreateNode(_iqtCommand.CreateVarDefListOp())); _varMap[projectNode] = inputVar; return projectNode; } ////// Cap a relop tree with a PhysicalProjectOp. The Vars of the PhysicalProjectOp /// are the vars from the RelOp tree /// /// the input relop tree ///relop tree capped by a PhysicalProjectOp private Node CapWithPhysicalProject(Node input) { PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?"); // Get the Var from the input; and build up a Project above it Var inputVar = _varMap[input]; PhysicalProjectOp projectOp = _iqtCommand.CreatePhysicalProjectOp(inputVar); Node projectNode = _iqtCommand.CreateNode(projectOp, input); return projectNode; } ////// Creates a new variable scope that is based on a CQT DbExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression. /// /// The DbExpressionBinding that defines the scope ///The Node produced by converting the binding's DbExpression private Node EnterExpressionBinding(DbExpressionBinding binding) { return PushBindingScope(binding.Expression, binding.VariableName); } ////// Creates a new variable scope that is based on a CQT DbGroupExpressionBinding and pushes it onto the variable scope stack. The scope defines a single variable based on the DbExpressionBinding's VarName and DbExpression. /// This method does not bring the GroupVarName into scope. Note that ExitExpressionBinding and NOT ExitGroupExpressionBinding should be used to remove this scope from the stack. /// /// The DbGroupExpressionBinding that defines the scope ///The Node produced by converting the binding's DbExpression private Node EnterGroupExpressionBinding(DbGroupExpressionBinding binding) { return PushBindingScope(binding.Expression, binding.VariableName); } ////// Common implementation method called by both EnterExpressionBinding and EnterGroupExpressionBinding /// /// The DbExpression that defines the binding /// The name of the binding variable ///private Node PushBindingScope(DbExpression boundExpression, string bindingName) { // // Visit the DbExpressionBinding's DbExpression to convert it to a Node/Op pair // Node inputNode = VisitExpr(boundExpression); PlanCompiler.Assert(inputNode != null, "DbExpressionBinding.Expression produced null conversion"); // // Call EnsureRelOp on the converted Node and set inputNode equal to the result // inputNode = EnsureRelOp(inputNode); // // Retrieve the Var produced by the RelOp from the Node --> Var map // Var boundVar = _varMap[inputNode]; PlanCompiler.Assert(boundVar != null, "No Var found for Input Op"); // // Create a new ExpressionBindingScope using the VarName from the DbExpressionBinding and // the Var associated with the Input RelOp, and push the new scope onto the variable scope stack. // _varScopes.Push(new ExpressionBindingScope(_iqtCommand, bindingName, boundVar)); // // Return the IQT conversion of the DbExpressionBinding's DbExpression. // return inputNode; } /// /// Removes a variable scope created based on a DbExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope. /// ///The removed ExpressionBindingScope private ExpressionBindingScope ExitExpressionBinding() { // // Pop the scope from the variable scope stack, assert that it is a DbExpressionBinding scope, and return it. // ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope; PlanCompiler.Assert(retScope != null, "ExitExpressionBinding called without ExpressionBindingScope on top of scope stack"); return retScope; } ////// Removes a variable scope created based on a DbGroupExpressionBinding from the top of the variable scope stack, verifying that it is in fact an ExpressionBindingScope. /// Should only be called after visiting the Aggregates of a DbGroupByExpression in Visit(DbGroupByExpression). /// The sequence (in Visit(GroupExpression e) is: /// 1. EnterGroupExpressionBinding /// 2. Visit e.Keys /// 3. ExitExpressionBinding /// 4. (Push new scope with GroupVarName instead of VarName) /// 5. Visit e.Aggregates /// 6. ExitGroupExpressionBinding /// private void ExitGroupExpressionBinding() { ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope; PlanCompiler.Assert(retScope != null, "ExitGroupExpressionBinding called without ExpressionBindingScope on top of scope stack"); } ////// Creates a new variable scope that is based on a CQT DbLambda and pushes it onto the variable scope stack. /// /// The DbLambda that defines the scope /// A list of Nodes produced by converting the CQT Expressions that provide the arguments to the Lambda function /// an edm function for which the current lambda represents the generated body, otherwise null private void EnterLambdaFunction(DbLambda lambda, ListargumentValues, EdmFunction expandingEdmFunction) { IList lambdaParams = lambda.Variables; Dictionary args = new Dictionary (); int idx = 0; foreach (Node argumentValue in argumentValues) { args.Add(lambdaParams[idx].VariableName, argumentValue); idx++; } // // If lambda represents an edm function body then check for a possible recursion in the function definition. // if (expandingEdmFunction != null) { // // Check if we are already inside the function body. // if (_functionExpansions.Contains(expandingEdmFunction)) { throw EntityUtil.CommandCompilation(Entity.Strings.Cqt_UDF_FunctionDefinitionWithCircularReference(expandingEdmFunction.FullName), null); } // // Push the function before processing its body // _functionExpansions.Push(expandingEdmFunction); } _varScopes.Push(new LambdaScope(this, _iqtCommand, args)); } /// /// Removes a variable scope created based on a Lambda function from the top of the variable scope stack, verifying that it is in fact a LambdaScope. /// /// an edm function for which the current lambda represents the generated body, otherwise null private LambdaScope ExitLambdaFunction(EdmFunction expandingEdmFunction) { // // Pop the scope from the variable scope stack, assert that it is a Lambda scope, and return it. // LambdaScope retScope = _varScopes.Pop() as LambdaScope; PlanCompiler.Assert(retScope != null, "ExitLambdaFunction called without LambdaScope on top of scope stack"); // // If lambda represents an edm function body then pop the function from the expansion stack and make sure it is the expected one. // if (expandingEdmFunction != null) { EdmFunction edmFunction = _functionExpansions.Pop(); PlanCompiler.Assert(edmFunction == expandingEdmFunction, "Function expansion stack corruption: unexpected function at the top of the stack"); } return retScope; } ////// Constructs a NewRecordOp on top of a multi-Var-producing Op, resulting in a RelOp that produces a single Var. /// /// The Node that references the multi-Var-producing Op. This Node will become the first child node of the new ProjectOp's Node /// Type metadata that describes the output record type /// A list of Vars that provide the output columns of the projection ///A new ProjectOp that projects a new record of the specified type from the specified Vars over the original input Op/Node private Node ProjectNewRecord(Node inputNode, RowType recType, IEnumerable colVars) { // // Create a list of VarRefOp Nodes that provide the column values for the new record // ListrecordColumns = new List (); foreach (Var colVar in colVars) { recordColumns.Add(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(colVar))); } // // Create the NewRecordOp Node using the record column nodes as its child nodes // Node newRecordNode = _iqtCommand.CreateNode(_iqtCommand.CreateNewRecordOp(recType), recordColumns); // // Create a new ComputedVar and a VarDefOp that uses the NewRecordOp Node to define it // Var newRecordVar; Node varDefNode = _iqtCommand.CreateVarDefListNode(newRecordNode, out newRecordVar); // // Create a ProjectOp with the single Computed Var defined by the new record construction // ProjectOp projection = _iqtCommand.CreateProjectOp(newRecordVar); Node projectionNode = _iqtCommand.CreateNode(projection, inputNode, varDefNode); _varMap[projectionNode] = newRecordVar; return projectionNode; } #endregion #region DbExpressionVisitor Members public override Node Visit(DbExpression e) { throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_General_UnsupportedExpression(e.GetType().FullName)); } public override Node Visit(DbConstantExpression e) { // Don't use CreateInternalConstantOp - respect user-intent // // Note that it is only safe to call GetValue and access the // constant value directly because any immutable values (byte[]) // will be cloned as the result expression is built in CTreeGenerator, // during the call to DbExpressionBuilder.Constant in VisitConstantOp. ConstantBaseOp op = _iqtCommand.CreateConstantOp(e.ResultType, e.GetValue()); return _iqtCommand.CreateNode(op); } public override Node Visit(DbNullExpression e) { NullOp op = _iqtCommand.CreateNullOp(e.ResultType); return _iqtCommand.CreateNode(op); } public override Node Visit(DbVariableReferenceExpression e) { // // Search the stack of variables scopes, top-down, // until the first one is found that defines a variable with the specified name. // Node varNode = null; foreach (CqtVariableScope scope in _varScopes) { if (scope.Contains(e.VariableName)) { varNode = scope[e.VariableName]; break; } } // // If the variable name was not resolved then either: // 1. The original CQT was invalid (should not be allowed into the ITreeGenerator). // 2. The variable scope stack itself is invalid. // PlanCompiler.Assert(varNode != null, "CQT VarRef could not be resolved in the variable scope stack"); return varNode; } public override Node Visit(DbParameterReferenceExpression e) { Op op = _iqtCommand.CreateVarRefOp(_iqtCommand.GetParameter(e.ParameterName)); return _iqtCommand.CreateNode(op); } public override Node Visit(DbFunctionExpression e) { Node retNode = null; if (e.Function.HasUserDefinedBody) { // This is a CSpace function with a body definition. // Expand it: // - replace the function call with the call to the body lambda, // - visit the lambda call expression. // Get/generate the body lambda. Wrap body generation exceptions. DbLambda lambda; try { lambda = _iqtCommand.MetadataWorkspace.GetGeneratedFunctionDefinition(e.Function); } catch (Exception exception) { if (EntityUtil.IsCatchableExceptionType(exception)) { throw EntityUtil.CommandCompilation(Entity.Strings.Cqt_UDF_FunctionDefinitionGenerationFailed(e.Function.FullName), exception); } throw; } // Visit the lambda call expression. // Argument types should be validated by now, hence the visitor should not throw under normal conditions. retNode = VisitLambdaExpression(lambda, e.Arguments, e.Function); // Check the body to see if the current function is a predicate function // Note that check needs to be done after visiting the the lambdaCall. // Doing it after will ensure that the function defintion has no recursion and IsPredicate will not throw the assertion. _functionsIsPredicateFlag[e.Function] = IsPredicate(lambda.Body); } else // a regular function call - no expansion needed { List argNodes = new List (e.Arguments.Count); for (int idx = 0; idx < e.Arguments.Count; idx++) { // Ensure that any argument with a result type that does not exactly match the type of // the corresponding function parameter is enclosed in a SoftCastOp. argNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Arguments[idx]), e.Function.Parameters[idx].TypeUsage)); } retNode = _iqtCommand.CreateNode(_iqtCommand.CreateFunctionOp(e.Function), argNodes); } return retNode; } public override Node Visit(DbLambdaExpression e) { return VisitLambdaExpression(e.Lambda, e.Arguments, null); } private Node VisitLambdaExpression(DbLambda lambda, IList arguments, EdmFunction expandingEdmFunction) { Node retNode = null; List argNodes = new List (arguments.Count); foreach (DbExpression argExpr in arguments) { // #484709: Lambda function parameters should not have enclosing SoftCastOps. argNodes.Add(VisitExpr(argExpr)); } EnterLambdaFunction(lambda, argNodes, expandingEdmFunction); retNode = VisitExpr(lambda.Body); ExitLambdaFunction(expandingEdmFunction); return retNode; } #if METHOD_EXPRESSION public override Node Visit(MethodExpression e) { throw EntityUtil.NotSupported(); } #endif #region SoftCast Helpers /// /// This method builds a "soft"Cast operator over the input node (if necessary) to (soft) /// cast it to the desired type (targetType) /// /// If the input is a scalarOp, then we simply add on the SoftCastOp /// directly (if it is needed, of course). If the input is a RelOp, we create a /// new ProjectOp above the input, add a SoftCast above the Var of the /// input, and then return the new ProjectOp /// /// The "need to cast" is determined by the Command.EqualTypes function. All type /// equivalence in the plan compiler is determined by this function /// /// the expression to soft-cast /// the desired type to cast to ///private Node BuildSoftCast(Node node, TypeUsage targetType) { // // If the input is a RelOp (say X), and the Var of the input is "x", // we convert this into // Project(X, softCast(x, t)) // where t is the element type of the desired target type // if (node.Op.IsRelOp) { CollectionType targetCollectionType = TypeHelpers.GetEdmType (targetType); targetType = targetCollectionType.TypeUsage; Var nodeVar = _varMap[node]; // Do we need a cast at all? if (Command.EqualTypes(targetType, nodeVar.Type)) { return node; } // Build up the projectOp Var projectVar; Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(nodeVar)); Node castNode = _iqtCommand.CreateNode(_iqtCommand.CreateSoftCastOp(targetType), varRefNode); Node varDefListNode = _iqtCommand.CreateVarDefListNode(castNode, out projectVar); ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar); Node projectNode = _iqtCommand.CreateNode(projectOp, node, varDefListNode); _varMap[projectNode] = projectVar; return projectNode; } else { PlanCompiler.Assert(node.Op.IsScalarOp, "I want a scalar op"); if (Command.EqualTypes(node.Op.Type, targetType)) { return node; } else { SoftCastOp castOp = _iqtCommand.CreateSoftCastOp(targetType); return _iqtCommand.CreateNode(castOp, node); } } } /// /// A variant of the function above. Works with an EdmType instead /// of a TypeUsage, but leverages all the work above /// /// the node to "cast" /// the desired type ///the transformed expression private Node BuildSoftCast(Node node, EdmType targetType) { return BuildSoftCast(node, TypeUsage.Create(targetType)); } private Node BuildEntityRef(Node arg, TypeUsage entityType) { TypeUsage refType = TypeHelpers.CreateReferenceTypeUsage((EntityType)entityType.EdmType); return _iqtCommand.CreateNode(_iqtCommand.CreateGetEntityRefOp(refType), arg); } #endregion ////// We simplify the property instance where the user is accessing a key member of /// a reference navigation. The instance becomes simply the reference key in such /// cases. /// /// For instance, product.Category.CategoryID becomes Ref(product.Category).CategoryID, /// which gives us a chance of optimizing the query (using foreign keys rather than joins) /// /// The original property expression that specifies the member and instance /// 'Simplified' instance. If the member is a key and the instance is a navigation /// the rewritten expression's instance is a reference navigation rather than the full entity. ///private bool TryRewriteKeyPropertyAccess(DbPropertyExpression propertyExpression, out DbExpression rewritten) { // if we're accessing a key member of a navigation, collapse the structured instance // to the key reference. if (propertyExpression.Instance.ExpressionKind == DbExpressionKind.Property && Helper.IsEntityType(propertyExpression.Instance.ResultType.EdmType)) { EntityType instanceType = (EntityType)propertyExpression.Instance.ResultType.EdmType; DbPropertyExpression instanceExpression = (DbPropertyExpression)propertyExpression.Instance; if (Helper.IsNavigationProperty(instanceExpression.Property) && instanceType.KeyMembers.Contains(propertyExpression.Property)) { // modify the property expression so that it merely retrieves the reference // not the entire entity NavigationProperty navigationProperty = (NavigationProperty)instanceExpression.Property; DbExpression navigationSource = instanceExpression.Instance.GetEntityRef(); DbExpression navigationExpression = navigationSource.Navigate(navigationProperty.FromEndMember, navigationProperty.ToEndMember); rewritten = navigationExpression.GetRefKey(); rewritten = rewritten.Property(propertyExpression.Property.Name); return true; } } rewritten = null; return false; } public override Node Visit(DbPropertyExpression e) { // Only Properties, Relationship End and NavigationProperty members are supported. if (BuiltInTypeKind.EdmProperty != e.Property.BuiltInTypeKind && BuiltInTypeKind.AssociationEndMember != e.Property.BuiltInTypeKind && BuiltInTypeKind.NavigationProperty != e.Property.BuiltInTypeKind) { throw EntityUtil.NotSupported(); } PlanCompiler.Assert(e.Instance != null, "Static properties are not supported"); Node retNode = null; DbExpression rewritten; if (TryRewriteKeyPropertyAccess(e, out rewritten)) { retNode = this.VisitExpr(rewritten); } else { Node instance = VisitExpr(e.Instance); // // Retrieving a property from a new instance constructor can be // simplified to just the node that provides the corresponding property. // For example, Property(Row(A = x, B = y), 'A') => x // All structured types (including association types) are considered. // if (e.Instance.ExpressionKind == DbExpressionKind.NewInstance && Helper.IsStructuralType(e.Instance.ResultType.EdmType)) { // Retrieve the 'structural' members of the instance's type. // For Association types this should be only Association End members, // while for Complex, Entity or Row types is should be only Properties. System.Collections.IList propertyOrEndMembers = Helper.GetAllStructuralMembers(e.Instance.ResultType.EdmType); // Find the position of the member with the same name as the retrieved // member in the list of structural members. int memberIdx = -1; for (int idx = 0; idx < propertyOrEndMembers.Count; idx++) { if (string.Equals(e.Property.Name, ((EdmMember)propertyOrEndMembers[idx]).Name, StringComparison.Ordinal)) { memberIdx = idx; break; } } PlanCompiler.Assert(memberIdx > -1, "The specified property was not found"); // If the member was found, return the corresponding argument value // to the new instance op. retNode = instance.Children[memberIdx]; // Make sure the argument value has been "cast" to the return type // of the property, if necessary. retNode = BuildSoftCast(retNode, e.ResultType); } else { Op op = _iqtCommand.CreatePropertyOp(e.Property); // Make sure that the input has been "cast" to the right type instance = BuildSoftCast(instance, e.Property.DeclaringType); retNode = _iqtCommand.CreateNode(op, instance); } } return retNode; } public override Node Visit(DbComparisonExpression e) { Op op = _iqtCommand.CreateComparisonOp(s_opMap[e.ExpressionKind]); Node leftArg = VisitExprAsScalar(e.Left); Node rightArg = VisitExprAsScalar(e.Right); TypeUsage commonType = TypeHelpers.GetCommonTypeUsage(e.Left.ResultType, e.Right.ResultType); // Make sure that the inputs have been cast to the right types if (!Command.EqualTypes(e.Left.ResultType, e.Right.ResultType)) { leftArg = BuildSoftCast(leftArg, commonType); rightArg = BuildSoftCast(rightArg, commonType); } if (TypeSemantics.IsEntityType(commonType) && (e.ExpressionKind == DbExpressionKind.Equals || e.ExpressionKind == DbExpressionKind.NotEquals)) { // Entity (in)equality is implemented as ref (in)equality leftArg = BuildEntityRef(leftArg, commonType); rightArg = BuildEntityRef(rightArg, commonType); } return _iqtCommand.CreateNode(op, leftArg, rightArg); } public override Node Visit(DbLikeExpression e) { return _iqtCommand.CreateNode( _iqtCommand.CreateLikeOp(), VisitExpr(e.Argument), VisitExpr(e.Pattern), VisitExpr(e.Escape) ); } private Node CreateLimitNode(Node inputNode, Node limitNode, bool withTies) { // // Limit(Skip(x)) - which becomes ConstrainedSortOp - and Limit(Sort(x)) are special cases // Node retNode = null; if (OpType.ConstrainedSort == inputNode.Op.OpType && OpType.Null == inputNode.Child2.Op.OpType) { // // The input was a DbSkipExpression which is now represented // as a ConstrainedSortOp with a NullOp Limit. The Limit from // this DbLimitExpression can be merged into the input ConstrainedSortOp // rather than creating a new ConstrainedSortOp. // inputNode.Child2 = limitNode; // If this DbLimitExpression specifies WithTies, the input ConstrainedSortOp must be // updated to reflect this (DbSkipExpression always produces a ConstrainedSortOp with // WithTies equal to false). if (withTies) { ((ConstrainedSortOp)inputNode.Op).WithTies = true; } retNode = inputNode; } else if (OpType.Sort == inputNode.Op.OpType) { // // This DbLimitExpression is applying a limit to a DbSortExpression. // The two expressions can be merged into a single ConstrainedSortOp // rather than creating a new ConstrainedSortOp over the input SortOp. // // The new ConstrainedSortOp has the same SortKeys as the input SortOp. // The returned Node will have the following children: // - The input to the Sort // - A NullOp to indicate no Skip operation is specified // - The limit Node from the DbLimitExpression // retNode = _iqtCommand.CreateNode( _iqtCommand.CreateConstrainedSortOp(((SortOp)inputNode.Op).Keys, withTies), inputNode.Child0, _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)), limitNode ); } else { // // The input to the Limit is neither ConstrainedSortOp or SortOp. // A new ConstrainedSortOp must be created with an empty list of keys // and the following children: // - The input to the DbLimitExpression // - a NullOp to indicate that no Skip operation is specified // - The limit Node from the DbLimitExpression // retNode = _iqtCommand.CreateNode( _iqtCommand.CreateConstrainedSortOp(new List true if the property expression was rewritten, in which casewill be non-null, /// otherwise false , in which casewill be null. (), withTies), inputNode, _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)), limitNode ); } return retNode; } public override Node Visit(DbLimitExpression expression) { // // Visit the Argument and retrieve its Var // Node inputNode = EnsureRelOp(VisitExpr(expression.Argument)); Var inputVar = _varMap[inputNode]; // // Visit the Limit ensuring that it is a scalar // Node limitNode = VisitExprAsScalar(expression.Limit); Node retNode; if(OpType.Project == inputNode.Op.OpType) { // // If the input to the DbLimitExpression is a projection, then apply the Limit operation to the // input to the ProjectOp instead. This allows Limit(Project(Skip(x))) and Limit(Project(Sort(x))) // to be treated in the same way as Limit(Skip(x)) and Limit(Sort(x)). // Note that even if the input to the projection is not a ConstrainedSortOp or SortOp, the // Limit operation is still pushed under the Project. // inputNode.Child0 = CreateLimitNode(inputNode.Child0, limitNode, expression.WithTies); retNode = inputNode; } else { // // Otherwise, apply the Limit operation directly to the input. // retNode = CreateLimitNode(inputNode, limitNode, expression.WithTies); } // // The output Var of the resulting Node is the same as the output Var of its input Node. // If the input node is being returned (either because the Limit was pushed under a Project // or because the input was a ConstrainedSortOp that was simply updated with the Limit value) // then the Node -> Var map does not need to be updated. // if(!object.ReferenceEquals(retNode, inputNode)) { _varMap[retNode] = inputVar; } return retNode; } public override Node Visit(DbIsNullExpression e) { // SQLBUDT #484294: We need to recognize and simplify IsNull - IsNull and IsNull - Not - IsNull // This is the latest point where such patterns can be easily recognized. // After this the input predicate would get translated into a case statement. bool isAlwaysFalse = false; //true if IsNull - IsNull and IsNull - Not - IsNull is recognized if (e.Argument.ExpressionKind == DbExpressionKind.IsNull) { isAlwaysFalse = true; } else if (e.Argument.ExpressionKind == DbExpressionKind.Not) { DbNotExpression notExpression = (DbNotExpression)e.Argument; if (notExpression.Argument.ExpressionKind == DbExpressionKind.IsNull) { isAlwaysFalse = true; } } Op op = _iqtCommand.CreateConditionalOp(OpType.IsNull); //If we have recognized that the result is always false, return IsNull(true), to still have predicate as output. //This gets further simplified by transformation rules. if (isAlwaysFalse) { return _iqtCommand.CreateNode(op, _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true))); } Node argNode = VisitExprAsScalar(e.Argument); if (TypeSemantics.IsEntityType(e.Argument.ResultType)) { argNode = BuildEntityRef(argNode, e.Argument.ResultType); } return _iqtCommand.CreateNode(op, argNode); } public override Node Visit(DbArithmeticExpression e) { Op op = _iqtCommand.CreateArithmeticOp(s_opMap[e.ExpressionKind], e.ResultType); // Make sure that the inputs have been "cast" to the result type // Assumption: The input type must be the same as the result type. Is this always true? List children = new List (); foreach (DbExpression arg in e.Arguments) { Node child = VisitExprAsScalar(arg); children.Add(BuildSoftCast(child, e.ResultType)); } return _iqtCommand.CreateNode(op, children); } public override Node Visit(DbAndExpression e) { Op op = _iqtCommand.CreateConditionalOp(OpType.And); return VisitBinary(e, op, VisitExprAsPredicate); } public override Node Visit(DbOrExpression e) { Op op = _iqtCommand.CreateConditionalOp(OpType.Or); return VisitBinary(e, op, VisitExprAsPredicate); } public override Node Visit(DbNotExpression e) { Op op = _iqtCommand.CreateConditionalOp(OpType.Not); return VisitUnary(e, op, VisitExprAsPredicate); } public override Node Visit(DbDistinctExpression e) { Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); Var inputVar = _varMap[inputSetNode]; Op distinctOp = _iqtCommand.CreateDistinctOp(inputVar); Node distinctNode = _iqtCommand.CreateNode(distinctOp, inputSetNode); _varMap[distinctNode] = inputVar; return distinctNode; } public override Node Visit(DbElementExpression e) { Op elementOp = _iqtCommand.CreateElementOp(e.ResultType); Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); // Add a soft cast if needed inputSetNode = BuildSoftCast(inputSetNode, TypeHelpers.CreateCollectionTypeUsage(e.ResultType)); Var inputVar = _varMap[inputSetNode]; // // Add a singleRowOp enforcer, as we are not guaranteed that the input // collection produces at most one row // inputSetNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowOp(), inputSetNode); _varMap[inputSetNode] = inputVar; // add a fake projectNode inputSetNode = CapWithProject(inputSetNode); return _iqtCommand.CreateNode(elementOp, inputSetNode); } public override Node Visit(DbIsEmptyExpression e) { // // IsEmpty(input set) --> Not(Exists(input set)) // Op existsOp = _iqtCommand.CreateExistsOp(); Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument)); return _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Not), _iqtCommand.CreateNode(existsOp, inputSetNode) ); } /// /// Encapsulates the logic required to convert a SetOp (Except, Intersect, UnionAll) expression /// into an IQT Node/Op pair. /// /// The DbExceptExpression, DbIntersectExpression or DbUnionAllExpression to convert, as an instance of DbBinaryExpression ///A new IQT Node that references the ExceptOp, IntersectOp or UnionAllOp created based on the expression private Node VisitSetOpExpression(DbBinaryExpression expression) { PlanCompiler.Assert(DbExpressionKind.Except == expression.ExpressionKind || DbExpressionKind.Intersect == expression.ExpressionKind || DbExpressionKind.UnionAll == expression.ExpressionKind, "Non-SetOp DbExpression used as argument to VisitSetOpExpression"); PlanCompiler.Assert(TypeSemantics.IsCollectionType(expression.ResultType), "SetOp DbExpression does not have collection result type?"); // Visit the left and right collection arguments Node leftNode = EnsureRelOp(VisitExpr(expression.Left)); Node rightNode = EnsureRelOp(VisitExpr(expression.Right)); // // Now the hard part. "Normalize" the left and right sides to // match the result type. // leftNode = BuildSoftCast(leftNode, expression.ResultType); rightNode = BuildSoftCast(rightNode, expression.ResultType); // The SetOp produces a single Var of the same type as the element type of the expression's collection result type Var outputVar = _iqtCommand.CreateSetOpVar(TypeHelpers.GetEdmType(expression.ResultType).TypeUsage); // Create VarMaps for the left and right arguments that map the output Var to the Var produced by the corresponding argument VarMap leftMap = new VarMap(); leftMap.Add(outputVar, _varMap[leftNode]); VarMap rightMap = new VarMap(); rightMap.Add(outputVar, _varMap[rightNode]); // Create a SetOp that corresponds to the operation specified by the expression's DbExpressionKind Op setOp = null; switch(expression.ExpressionKind) { case DbExpressionKind.Except: setOp = _iqtCommand.CreateExceptOp(leftMap, rightMap); break; case DbExpressionKind.Intersect: setOp = _iqtCommand.CreateIntersectOp(leftMap, rightMap); break; case DbExpressionKind.UnionAll: setOp = _iqtCommand.CreateUnionAllOp(leftMap, rightMap); break; } // Create a new Node that references the SetOp Node setOpNode = _iqtCommand.CreateNode(setOp, leftNode, rightNode); // Update the Node => Var map with an entry that maps the new Node to the output Var _varMap[setOpNode] = outputVar; // Return the newly created SetOp Node return setOpNode; } public override Node Visit(DbUnionAllExpression e) { return VisitSetOpExpression(e); } public override Node Visit(DbIntersectExpression e) { return VisitSetOpExpression(e); } public override Node Visit(DbExceptExpression e) { return VisitSetOpExpression(e); } public override Node Visit(DbTreatExpression e) { Op op; if (_fakeTreats.Contains(e)) { op = _iqtCommand.CreateFakeTreatOp(e.ResultType); } else { op = _iqtCommand.CreateTreatOp(e.ResultType); } return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbIsOfExpression e) { Op op = null; if (DbExpressionKind.IsOfOnly == e.ExpressionKind) { op = _iqtCommand.CreateIsOfOnlyOp(e.OfType); } else { op = _iqtCommand.CreateIsOfOp(e.OfType); } return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbCastExpression e) { Op op = _iqtCommand.CreateCastOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbCaseExpression e) { List childNodes = new List (); for (int idx = 0; idx < e.When.Count; idx++) { childNodes.Add(VisitExprAsPredicate(e.When[idx])); // Make sure that each then-clause is the same type as the result childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Then[idx]), e.ResultType)); } // Make sure that the else-clause is the same type as the result childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Else), e.ResultType)); return _iqtCommand.CreateNode(_iqtCommand.CreateCaseOp(e.ResultType), childNodes); } /// /// Represents one or more type filters that should be AND'd together to produce an aggregate IsOf filter expression /// private class IsOfFilter { ////// The type that elements of the filtered input set must be to satisfy this IsOf filter /// private readonly TypeUsage requiredType; ////// Indicates whether elements of the filtered input set may be of a subtype (IsOf) of the required type /// and still satisfy the IsOfFilter, or must be exactly of the required type (IsOfOnly) to do so. /// private readonly bool isExact; ////// The next IsOfFilter in the AND chain. /// private IsOfFilter next; internal IsOfFilter(DbIsOfExpression template) { this.requiredType = template.OfType; this.isExact = (template.ExpressionKind == DbExpressionKind.IsOfOnly); } internal IsOfFilter(DbOfTypeExpression template) { this.requiredType = template.OfType; this.isExact = (template.ExpressionKind == DbExpressionKind.OfTypeOnly); } private IsOfFilter(TypeUsage required, bool exact) { this.requiredType = required; this.isExact = exact; } private IsOfFilter Merge(TypeUsage otherRequiredType, bool otherIsExact) { // Can the two type filters be merged? In general, a more specific // type filter can replace a less specific type filter. IsOfFilter result; bool typesEqual = this.requiredType.EdmEquals(otherRequiredType); // The simplest case - the filters are equivalent if (typesEqual && this.isExact == otherIsExact) { result = this; } // Next simplest - two IsOfOnly filters can never be merged if the types are different // (and if the types were equal the above condition would have been satisfied). // SC_ else if (this.isExact && otherIsExact) { result = new IsOfFilter(otherRequiredType, otherIsExact); result.next = this; } // Two IsOf filters can potentially be adjusted - the more specific type filter should be kept, if present else if (!this.isExact && !otherIsExact) { // At this point the types cannot be equal. If one filter specifies a type that is a subtype of the other, // then the subtype filter is the one that should remain if (otherRequiredType.IsSubtypeOf(this.requiredType)) { result = new IsOfFilter(otherRequiredType, false); result.next = this.next; } else if (this.requiredType.IsSubtypeOf(otherRequiredType)) { result = this; } else { // The types are not related and the filters cannot be merged // Note that this case may not be possible since IsOf and OfType // both require an argument with a compatible type to the IsOf type. result = new IsOfFilter(otherRequiredType, otherIsExact); result.next = this; } } // One filter is an IsOf filter while the other is an IsOfOnly filter else { // For IsOf(T) AND IsOfOnly(T), the IsOf filter can be dropped if (typesEqual) { result = new IsOfFilter(otherRequiredType, true); result.next = this.next; } else { // Decide which is the 'IsOfOnly' type and which is the 'IsOf' type TypeUsage isOfOnlyType = (this.isExact ? this.requiredType : otherRequiredType); TypeUsage isOfType = (this.isExact ? otherRequiredType : this.requiredType); // IsOf(Super) && IsOfOnly(Sub) => IsOfOnly(Sub) // In all other cases, both filters remain - even though the IsOfOnly(Super) and IsOf(Sub) is obviously a contradiction. // SC_ if (isOfOnlyType.IsSubtypeOf(isOfType)) { if (object.ReferenceEquals(isOfOnlyType, this.requiredType) && this.isExact) { result = this; } else { result = new IsOfFilter(isOfOnlyType, true); result.next = this.next; } } else { result = new IsOfFilter(otherRequiredType, otherIsExact); result.next = this; } } } return result; } internal IsOfFilter Merge(DbIsOfExpression other) { return Merge(other.OfType, (other.ExpressionKind == DbExpressionKind.IsOfOnly)); } internal IsOfFilter Merge(DbOfTypeExpression other) { return Merge(other.OfType, (other.ExpressionKind == DbExpressionKind.OfTypeOnly)); } internal IEnumerable> ToEnumerable() { IsOfFilter currentFilter = this; while (currentFilter != null) { yield return new KeyValuePair (currentFilter.requiredType, currentFilter.isExact); currentFilter = currentFilter.next; } } } private DbFilterExpression CreateIsOfFilterExpression(DbExpression input, IsOfFilter typeFilter) { // Create a filter expression based on the IsOf/IsOfOnly operations specified by typeFilter DbExpressionBinding resultBinding = input.Bind(); List predicates = new List ( typeFilter.ToEnumerable().Select(tf => tf.Value ? resultBinding.Variable.IsOfOnly(tf.Key) : resultBinding.Variable.IsOf(tf.Key)).ToList() ); DbExpression predicate = Helpers.BuildBalancedTreeInPlace(predicates, (left, right) => left.And(right)); DbFilterExpression result = resultBinding.Filter(predicate); // Track the fact that this IsOfFilter was created by the ITreeGenerator itself and should // simply be converted to an ITree Node when it is encountered again by the visitor pass. _processedIsOfFilters.Add(result); return result; } private bool IsIsOfFilter(DbFilterExpression filter) { if(filter.Predicate.ExpressionKind != DbExpressionKind.IsOf && filter.Predicate.ExpressionKind != DbExpressionKind.IsOfOnly) { return false; } DbExpression isOfArgument = ((DbIsOfExpression)filter.Predicate).Argument; return (isOfArgument.ExpressionKind == DbExpressionKind.VariableReference && ((DbVariableReferenceExpression)isOfArgument).VariableName == filter.Input.VariableName); } private DbExpression ApplyIsOfFilter(DbExpression current, IsOfFilter typeFilter) { // An IsOf filter can be safely pushed down through the following expressions: // // Distinct // Filter - may be merged if the Filter is also an OfType filter // OfType - converted to Project(Filter(input, IsOf(T)), TreatAs(T)) and the Filter may be merged // Project - only for identity project // SC_ DbExpression result; switch(current.ExpressionKind) { case DbExpressionKind.Distinct: { result = ApplyIsOfFilter(((DbDistinctExpression)current).Argument, typeFilter).Distinct(); } break; case DbExpressionKind.Filter: { DbFilterExpression filter = (DbFilterExpression)current; if (IsIsOfFilter(filter)) { // If this is an IsOf filter, examine the interaction with the current filter we are trying to apply DbIsOfExpression isOfExp = (DbIsOfExpression)filter.Predicate; typeFilter = typeFilter.Merge(isOfExp); result = ApplyIsOfFilter(filter.Input.Expression, typeFilter); } else { // Otherwise, push the current IsOf filter under this filter DbExpression rewritten = ApplyIsOfFilter(filter.Input.Expression, typeFilter); result = rewritten.BindAs(filter.Input.VariableName).Filter(filter.Predicate); } } break; case DbExpressionKind.OfType: case DbExpressionKind.OfTypeOnly: { // Examine the interaction of this nested OfType filter with the OfType filter we are trying to apply // and construct an aggregated type filter (where possible) DbOfTypeExpression ofTypeExp = (DbOfTypeExpression)current; typeFilter = typeFilter.Merge(ofTypeExp); DbExpression rewrittenIsOf = ApplyIsOfFilter(ofTypeExp.Argument, typeFilter); DbExpressionBinding treatBinding = rewrittenIsOf.Bind(); DbTreatExpression treatProjection = treatBinding.Variable.TreatAs(ofTypeExp.OfType); _fakeTreats.Add(treatProjection); result = treatBinding.Project(treatProjection); } break; case DbExpressionKind.Project: { DbProjectExpression project = (DbProjectExpression)current; if(project.Projection.ExpressionKind == DbExpressionKind.VariableReference && ((DbVariableReferenceExpression)project.Projection).VariableName == project.Input.VariableName) { // If this is an identity-project, remove it by visiting the input expression result = ApplyIsOfFilter(project.Input.Expression, typeFilter); } else { // Otherwise, the projection is opaque to the IsOf rewrite result = CreateIsOfFilterExpression(current, typeFilter); } } break; case DbExpressionKind.Sort: { // The IsOf filter is applied to the Sort input, then the sort keys are reapplied to create a new Sort expression. DbSortExpression sort = (DbSortExpression)current; DbExpression sortInput = ApplyIsOfFilter(sort.Input.Expression, typeFilter); result = sortInput.BindAs(sort.Input.VariableName).Sort(sort.SortOrder); } break; default: { // This is not a recognized case, so simply apply the type filter to the expression. result = CreateIsOfFilterExpression(current, typeFilter); } break; } return result; } /// /// Build the equivalent of an OfTypeExpression over the input (ie) produce the set of values from the /// input that are of the desired type (exactly of the desired type, if the "includeSubtypes" parameter is false). /// /// Further more, "update" the result element type to be the desired type. /// /// We accomplish this by first building a FilterOp with an IsOf (or an IsOfOnly) predicate for the desired /// type. We then build out a ProjectOp over the FilterOp, where we introduce a "Fake" TreatOp over the input /// element to cast it to the right type. The "Fake" TreatOp is only there for "compile-time" typing reasons, /// and will be ignored in the rest of the plan compiler /// // the input collection // the single Var produced by the input collection // the desired element type // do we include subtypes of the desired element type // the result subtree // the single Var produced by the result subtree public override Node Visit(DbOfTypeExpression e) { // // The argument to OfType must be a collection // PlanCompiler.Assert(TypeSemantics.IsCollectionType(e.Argument.ResultType), "Non-Collection Type Argument in DbOfTypeExpression"); DbExpression rewrittenIsOfFilter = ApplyIsOfFilter(e.Argument, new IsOfFilter(e)); // // Visit the collection argument and ensure that it is a RelOp suitable for subsequent use in the Filter/Project used to convert OfType. // Node inputNode = EnsureRelOp(VisitExpr(rewrittenIsOfFilter)); // // Retrieve the Var produced by the RelOp input. // Var inputVar = _varMap[inputNode]; // // Build the Treat part of the OfType expression tree - note that this is a 'fake' // Treat because the underlying IsOf filter makes it unnecessary (as far as the // plan compiler is concerned). // Var resultVar; Node resultNode = _iqtCommand.BuildFakeTreatProject(inputNode, inputVar, e.OfType, out resultVar); // // Add the node-var mapping, and return // _varMap[resultNode] = resultVar; return resultNode; } public override Node Visit(DbNewInstanceExpression e) { Op newInstOp = null; ListrelPropertyExprs = null; if (TypeSemantics.IsCollectionType(e.ResultType)) { newInstOp = _iqtCommand.CreateNewMultisetOp(e.ResultType); } else if (TypeSemantics.IsRowType(e.ResultType)) { newInstOp = _iqtCommand.CreateNewRecordOp(e.ResultType); } else if (TypeSemantics.IsEntityType(e.ResultType)) { List relPropertyList = new List (); relPropertyExprs = new List (); if (e.HasRelatedEntityReferences) { foreach (DbRelatedEntityRef targetRef in e.RelatedEntityReferences) { RelProperty relProperty = new RelProperty((RelationshipType)targetRef.TargetEnd.DeclaringType, targetRef.SourceEnd, targetRef.TargetEnd); relPropertyList.Add(relProperty); Node relPropertyNode = VisitExprAsScalar(targetRef.TargetEntityReference); relPropertyExprs.Add(relPropertyNode); } } newInstOp = _iqtCommand.CreateNewEntityOp(e.ResultType, relPropertyList); } else { newInstOp = _iqtCommand.CreateNewInstanceOp(e.ResultType); } // // Build up the list of arguments. Make sure that they match // the expected types (and add "soft" casts, if needed) // List newArgs = new List (); if (TypeSemantics.IsStructuralType(e.ResultType)) { StructuralType resultType = TypeHelpers.GetEdmType (e.ResultType); int i = 0; foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(resultType)) { Node newArg = BuildSoftCast(VisitExprAsScalar(e.Arguments[i]), Helper.GetModelTypeUsage(m)); newArgs.Add(newArg); i++; } } else { CollectionType resultType = TypeHelpers.GetEdmType (e.ResultType); TypeUsage elementTypeUsage = resultType.TypeUsage; foreach (DbExpression arg in e.Arguments) { Node newArg = BuildSoftCast(VisitExprAsScalar(arg), elementTypeUsage); newArgs.Add(newArg); } } if (relPropertyExprs != null) { newArgs.AddRange(relPropertyExprs); } Node node = _iqtCommand.CreateNode(newInstOp, newArgs); return node; } public override Node Visit(DbRefExpression e) { // SQLBUDT #502617: Creating a collection of refs throws an Assert // A SoftCastOp may be required if the argument to the RefExpression is only promotable // to the row type produced from the key properties of the referenced Entity type. Since // this row type is not actually represented anywhere in the tree it must be built here in // order to determine whether or not the SoftCastOp should be applied. // Op op = _iqtCommand.CreateRefOp(e.EntitySet, e.ResultType); Node newArg = BuildSoftCast(VisitExprAsScalar(e.Argument), TypeHelpers.CreateKeyRowType(e.EntitySet.ElementType)); return _iqtCommand.CreateNode(op, newArg); } public override Node Visit(DbRelationshipNavigationExpression e) { RelProperty relProperty = new RelProperty(e.Relationship, e.NavigateFrom, e.NavigateTo); Op op = _iqtCommand.CreateNavigateOp(e.ResultType, relProperty); Node arg = VisitExprAsScalar(e.NavigationSource); return _iqtCommand.CreateNode(op, arg); } public override Node Visit(DbDerefExpression e) { Op op = _iqtCommand.CreateDerefOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbRefKeyExpression e) { Op op = _iqtCommand.CreateGetRefKeyOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbEntityRefExpression e) { Op op = _iqtCommand.CreateGetEntityRefOp(e.ResultType); return VisitUnary(e, op, VisitExprAsScalar); } public override Node Visit(DbScanExpression e) { // Create a new table definition TableMD tableMetadata = Command.CreateTableDefinition(e.Target); // Create a scan table operator ScanTableOp op = _iqtCommand.CreateScanTableOp(tableMetadata); // Map the ScanTableOp to the ColumnVar of the Table's single column of the Extent's element type Node node = _iqtCommand.CreateNode(op); Var singleColumn = op.Table.Columns[0]; _varMap[node] = singleColumn; return node; } public override Node Visit(DbFilterExpression e) { if (!IsIsOfFilter(e) || _processedIsOfFilters.Contains(e)) { // // Visit the Predicate with the Input binding's variable in scope // Node inputSetNode = EnterExpressionBinding(e.Input); Node predicateNode = VisitExprAsPredicate(e.Predicate); ExitExpressionBinding(); Op filtOp = _iqtCommand.CreateFilterOp(); // Update the Node --> Var mapping. Filter maps to the same Var as its input. Node filtNode = _iqtCommand.CreateNode(filtOp, inputSetNode, predicateNode); _varMap[filtNode] = _varMap[inputSetNode]; return filtNode; } else { DbIsOfExpression isOfPredicate = (DbIsOfExpression)e.Predicate; DbExpression processed = ApplyIsOfFilter(e.Input.Expression, new IsOfFilter(isOfPredicate)); return this.VisitExpr(processed); } } public override Node Visit(DbProjectExpression e) { // check if this is the discriminated projection for a query mapping view if (e == this._discriminatedViewTopProject) { return GenerateDiscriminatedProject(e); } else { return GenerateStandardProject(e); } } private Node GenerateDiscriminatedProject(DbProjectExpression e) { PlanCompiler.Assert(null != _discriminatedViewTopProject, "if a project matches the pattern, there must be a corresponding discriminator map"); // convert the input to the top level projection Node source = EnterExpressionBinding(e.Input); List relPropertyList = new List (); List relPropertyExprs = new List (); foreach (KeyValuePair kv in _discriminatorMap.RelPropertyMap) { relPropertyList.Add(kv.Key); relPropertyExprs.Add(VisitExprAsScalar(kv.Value)); } // construct a DiscriminatedNewInstanceOp DiscriminatedNewEntityOp newInstOp = _iqtCommand.CreateDiscriminatedNewEntityOp(e.Projection.ResultType, new ExplicitDiscriminatorMap(_discriminatorMap), _discriminatorMap.EntitySet, relPropertyList); // args include all projected properties and discriminator and the relProperties List newArgs = new List (_discriminatorMap.PropertyMap.Count + 1); newArgs.Add(CreateNewInstanceArgument(_discriminatorMap.Discriminator.Property, _discriminatorMap.Discriminator)); foreach (var propertyMap in _discriminatorMap.PropertyMap) { DbExpression value = propertyMap.Value; EdmProperty property = propertyMap.Key; Node newArg = CreateNewInstanceArgument(property, value); newArgs.Add(newArg); } newArgs.AddRange(relPropertyExprs); Node newInstNode = _iqtCommand.CreateNode(newInstOp, newArgs); ExitExpressionBinding(); Var sourceVar; Node varDefListNode = _iqtCommand.CreateVarDefListNode(newInstNode, out sourceVar); ProjectOp projOp = _iqtCommand.CreateProjectOp(sourceVar); Node projNode = _iqtCommand.CreateNode(projOp, source, varDefListNode); _varMap[projNode] = sourceVar; return projNode; } private Node CreateNewInstanceArgument(EdmMember property, DbExpression value) { Node newArg = BuildSoftCast(VisitExprAsScalar(value), Helper.GetModelTypeUsage(property)); return newArg; } private Node GenerateStandardProject(DbProjectExpression e) { Node projectedSetNode = EnterExpressionBinding(e.Input); Node projectionNode = VisitExprAsScalar(e.Projection); ExitExpressionBinding(); Var projectionVar; Node varDefListNode = _iqtCommand.CreateVarDefListNode(projectionNode, out projectionVar); ProjectOp projOp = _iqtCommand.CreateProjectOp(projectionVar); Node projNode = _iqtCommand.CreateNode(projOp, projectedSetNode, varDefListNode); _varMap[projNode] = projectionVar; return projNode; } public override Node Visit(DbCrossJoinExpression e) { return VisitJoin(e, e.Inputs, null); } public override Node Visit(DbJoinExpression e) { List inputs = new List (); inputs.Add(e.Left); inputs.Add(e.Right); return VisitJoin(e, inputs, e.JoinCondition); } private Node VisitJoin(DbExpression e, IList inputs, DbExpression joinCond) { // // Assert that the JoinType is covered. If JoinTypes are added to CQT then the // switch statement that constructs the JoinOp must be updated, along with this assert. // PlanCompiler.Assert(DbExpressionKind.CrossJoin == e.ExpressionKind || DbExpressionKind.InnerJoin == e.ExpressionKind || DbExpressionKind.LeftOuterJoin == e.ExpressionKind || DbExpressionKind.FullOuterJoin == e.ExpressionKind, "Unrecognized JoinType specified in DbJoinExpression"); #if DEBUG // // Assert that the DbJoinExpression is producing a collection result with a record element type. // !!! IsCollectionOfRecord() is defined only in DEBUG !!! PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbJoinExpression"); #endif // // Bring the variables for the Join inputs into scope, track their nodes and vars, and visit the Join condition, if present. // List inputNodes = new List (); List inputVars = new List(); for(int idx = 0; idx < inputs.Count; idx++) { Node inputNode = EnterExpressionBinding(inputs[idx]); inputNodes.Add(inputNode); inputVars.Add(_varMap[inputNode]); } Node joinCondNode = VisitExprAsPredicate(joinCond); // // Remove the input variables from scope after visiting the Join condition. // for (int scopeCount = 0; scopeCount < inputNodes.Count; scopeCount++) { ExitExpressionBinding(); } // // Create an appropriate JoinOp based on the JoinType specified in the DbJoinExpression. // JoinBaseOp joinOp = null; switch (e.ExpressionKind) { case DbExpressionKind.CrossJoin: { joinOp = _iqtCommand.CreateCrossJoinOp(); } break; case DbExpressionKind.InnerJoin: { joinOp = _iqtCommand.CreateInnerJoinOp(); } break; case DbExpressionKind.LeftOuterJoin: { joinOp = _iqtCommand.CreateLeftOuterJoinOp(); } break; case DbExpressionKind.FullOuterJoin: { joinOp = _iqtCommand.CreateFullOuterJoinOp(); } break; } // // Assert that a JoinOp was produced. This check is again in case a new JoinType is introduced to CQT and this method is not updated. // PlanCompiler.Assert(joinOp != null, "Unrecognized JoinOp specified in DbJoinExpression, no JoinOp was produced"); // // If the Join condition was present then add its converted form to the list of child nodes for the new Join node. // if (e.ExpressionKind != DbExpressionKind.CrossJoin) { PlanCompiler.Assert(joinCondNode != null, "Non CrossJoinOps must specify a join condition"); inputNodes.Add(joinCondNode); } // // Create and return a new projection that unifies the multiple vars produced by the Join columns into a single record constructor. // return ProjectNewRecord( _iqtCommand.CreateNode(joinOp, inputNodes), ExtractElementRowType(e.ResultType), inputVars ); } public override Node Visit(DbApplyExpression e) { #if DEBUG // // Assert that the DbJoinExpression is producing a collection result with a record element type. // !!! IsCollectionOfRecord() is defined only in DEBUG !!! PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbApplyExpression"); #endif // // Bring the Input set's variable into scope // Node inputNode = EnterExpressionBinding(e.Input); // // Visit the Apply expression with the Input's variable in scope. // This is done via EnterExpressionBinding, which is allowable only because // it will only bring the Apply variable into scope *after* visiting the Apply expression // (which means that the Apply expression cannot validly reference its own binding variable) // Node applyNode = EnterExpressionBinding(e.Apply); // // Remove the Apply and Input variables from scope // ExitExpressionBinding(); // for the Apply ExitExpressionBinding(); // for the Input // // The ApplyType should only be either CrossApply or OuterApply. // PlanCompiler.Assert(DbExpressionKind.CrossApply == e.ExpressionKind || DbExpressionKind.OuterApply == e.ExpressionKind, "Unrecognized DbExpressionKind specified in DbApplyExpression"); // // Create a new Node with the correct ApplyOp as its Op and the input and apply nodes as its child nodes. // ApplyBaseOp applyOp = null; if (DbExpressionKind.CrossApply == e.ExpressionKind) { applyOp = _iqtCommand.CreateCrossApplyOp(); } else { applyOp = _iqtCommand.CreateOuterApplyOp(); } Node retNode = _iqtCommand.CreateNode(applyOp, inputNode, applyNode); // // Create and return a new projection that unifies the vars produced by the input and apply columns into a single record constructor. // return ProjectNewRecord( retNode, ExtractElementRowType(e.ResultType), new Var[] { _varMap[inputNode], _varMap[applyNode] } ); } public override Node Visit(DbGroupByExpression e) { #if DEBUG // !!! IsCollectionOfRecord() is defined only in DEBUG !!! PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "DbGroupByExpression has invalid result Type (not record collection)"); #endif // // Process the input and the keys // VarVec keyVarSet = _iqtCommand.CreateVarVec(); VarVec outputVarSet = _iqtCommand.CreateVarVec(); Node inputNode; List keyVarDefNodes; ExpressionBindingScope scope; ExtractKeys(e, keyVarSet, outputVarSet, out inputNode, out keyVarDefNodes, out scope); // Get the index of the group aggregate if any int groupAggregateIndex = -1; for (int i = 0; i < e.Aggregates.Count; i++) { if (e.Aggregates[i].GetType() == typeof(DbGroupAggregate)) { groupAggregateIndex = i; break; } } // //If there is a group aggregate, create a copy of the input // Node copyOfInput = null; List copyOfKeyVarDefNodes = null; VarVec copyOutputVarSet = _iqtCommand.CreateVarVec(); VarVec copyKeyVarSet = _iqtCommand.CreateVarVec(); if (groupAggregateIndex >= 0) { ExpressionBindingScope copyOfScope; //not needed ExtractKeys(e, copyKeyVarSet, copyOutputVarSet, out copyOfInput, out copyOfKeyVarDefNodes, out copyOfScope); } // // Bring the Input variable from the DbGroupByExpression into scope // scope = new ExpressionBindingScope(_iqtCommand, e.Input.GroupVariableName, scope.ScopeVar); _varScopes.Push(scope); // // Process the Aggregates: For each DbAggregate, produce the corresponding IQT conversion depending on whether the DbAggregate is a DbFunctionAggregate or DbGroupAggregate. // The converted Node is then used as the child node of a VarDefOp Node that is added to a list of Aggregate VarDefs or Group Aggregate VarDefs correspondingly. // The Var defined by the converted DbAggregate is added only to the overall list of Vars produced by the GroupBy (not the list of Keys). // List aggVarDefNodes = new List (); Node groupAggDefNode = null; for(int idx = 0; idx < e.Aggregates.Count; idx++) { DbAggregate agg = e.Aggregates[idx]; Var aggVar; // // Produce the converted form of the Arguments to the aggregate // IList argNodes = VisitExprAsScalar(agg.Arguments); // // Handle if it is DbFunctionAggregate // if (idx != groupAggregateIndex) { DbFunctionAggregate funcAgg = agg as DbFunctionAggregate; PlanCompiler.Assert(funcAgg != null, "Unrecognized DbAggregate used in DbGroupByExpression"); aggVarDefNodes.Add(ProcessFunctionAggregate(funcAgg, argNodes, out aggVar)); } // // Handle if it is DbGroupAggregate // else { groupAggDefNode = ProcessGroupAggregate(keyVarDefNodes, copyOfInput, copyOfKeyVarDefNodes, copyKeyVarSet, e.Input.Expression.ResultType, out aggVar); } outputVarSet.Set(aggVar); } // // The Aggregates have now been processed, so remove the group variable from scope. // ExitGroupExpressionBinding(); // // Construct the GroupBy. This consists of a GroupByOp (or GroupByIntoOp) with 3 (or 4) children: // 1. The Node produced from the Input set // 2. A VarDefListOp Node that uses the Key VarDefs to define the Key Vars (created above) // 3. A VarDefListOp Node that uses the Aggregate VarDefs to define the Aggregate Vars (created above) // 4. For a GroupByIntoOp a verDefLIstOp Node with a single var def node that defines the group aggregate // List groupByChildren = new List (); groupByChildren.Add(inputNode); // The Node produced from the Input set groupByChildren.Add( // The Key VarDefs _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), keyVarDefNodes )); groupByChildren.Add( // The Aggregate VarDefs _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), aggVarDefNodes )); GroupByBaseOp op; if (groupAggregateIndex >= 0) { groupByChildren.Add( // The GroupAggregate VarDef _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), groupAggDefNode )); op = _iqtCommand.CreateGroupByIntoOp(keyVarSet, this._iqtCommand.CreateVarVec(_varMap[inputNode]), outputVarSet); } else { op = _iqtCommand.CreateGroupByOp(keyVarSet, outputVarSet); } Node groupByNode = _iqtCommand.CreateNode( op, groupByChildren); // // Create and return a projection that unifies the multiple output vars of the GroupBy into a single record constructor. // return ProjectNewRecord( groupByNode, ExtractElementRowType(e.ResultType), outputVarSet //todo: it is not correct to pass a varvec where an ordered list is expected ); } private void ExtractKeys(DbGroupByExpression e, VarVec keyVarSet, VarVec outputVarSet, out Node inputNode, out List keyVarDefNodes, out ExpressionBindingScope scope) { inputNode = EnterGroupExpressionBinding(e.Input); // // Process the Keys: For each Key, produce the corresponding IQT conversion. // The converted Node is then used as the child node of a VarDefOp Node that is // added to a list of Key VarDefs. The Var defined by the converted Key expression // is added to both the overall list of Vars produced by the GroupBy and the list of Key vars produced by the GroupBy. // keyVarDefNodes = new List (); for (int idx = 0; idx < e.Keys.Count; idx++) { DbExpression keyExpr = e.Keys[idx]; Node keyNode = VisitExprAsScalar(keyExpr); ScalarOp keyOp = keyNode.Op as ScalarOp; // // In a valid CQT, each group key expressions will result in a ScalarOp since they // must be of an equality comparable type. // PlanCompiler.Assert(keyOp != null, "GroupBy Key is not a ScalarOp"); // // Create a ComputedVar with the same type as the Key and add it to both the set of output Vars produced by the GroupBy and the set of Key vars. // Var keyVar; // // Create a VarDefOp that uses the converted form of the Key to define the ComputedVar and add it to the list of Key VarDefs. // keyVarDefNodes.Add(_iqtCommand.CreateVarDefNode(keyNode, out keyVar)); outputVarSet.Set(keyVar); keyVarSet.Set(keyVar); } // // Before the Aggregates are processed, the Input variable must be taken out of scope and the 'group' variable introduced into scope in its place // This is done as follows: // 1. Pop the current ExpressionBindingScope from the stack // 2. Create a new ExpressionBindingScope using the same Var but the name of the 'group' variable from the DbGroupByExpression's DbGroupExpressionBinding // 3. Push this new scope onto the variable scope stack. // scope = ExitExpressionBinding(); } private Node ProcessFunctionAggregate(DbFunctionAggregate funcAgg, IList argNodes, out Var aggVar) { Node aggNode = _iqtCommand.CreateNode( _iqtCommand.CreateAggregateOp(funcAgg.Function, funcAgg.Distinct), argNodes ); // // Create a VarDefOp that uses the converted form of the DbAggregate to define the ComputedVar // return _iqtCommand.CreateVarDefNode(aggNode, out aggVar); } /// /// Translation for GroupAggregate /// /// Create the translation as : /// /// Collect /// | /// PhysicalProject /// | /// GroupNodeDefinition /// /// Here, GroupNodeDefinition is: /// 1. If there are no keys: copyOfInput; /// 2. If there are keys: /// /// Filter (keyDef1 = copyOfKeyDef1 or keyDef1 is null and copyOfKeyDef1 is null) and ... and (keyDefn = copyOfKeyDefn or keyDefn is null and copyOfKeyDefn is null) /// | /// Project (copyOfInput, copyOfKeyDef1, copyOfKeyDef1, ... copyOfKeyDefn) /// | /// copyOfInput /// /// /// /// /// /// /// /// ///private Node ProcessGroupAggregate(List keyVarDefNodes, Node copyOfInput, List copyOfkeyVarDefNodes, VarVec copyKeyVarSet, TypeUsage inputResultType, out Var groupAggVar) { Var inputVar = this._varMap[copyOfInput]; Node groupDefNode = copyOfInput; if (keyVarDefNodes.Count > 0) { VarVec projectOutpus = _iqtCommand.CreateVarVec(); projectOutpus.Set(inputVar); projectOutpus.Or(copyKeyVarSet); Node projectNodeWithKeys = _iqtCommand.CreateNode( _iqtCommand.CreateProjectOp(projectOutpus), groupDefNode, //the input _iqtCommand.CreateNode( //the key var defs _iqtCommand.CreateVarDefListOp(), copyOfkeyVarDefNodes )); List flattentedKeys = new List (); List copyFlattenedKeys = new List (); for (int i = 0; i < keyVarDefNodes.Count; i++) { Node keyVarDef = keyVarDefNodes[i]; Node copyOfKeyVarDef = copyOfkeyVarDefNodes[i]; Var keyVar = ((VarDefOp)keyVarDef.Op).Var; Var copyOfKeyVar = ((VarDefOp)copyOfKeyVarDef.Op).Var; // // The keys of type row need to be flattened, because grouping by a row means grouping by its individual // members and thus we have to check the individual members whether they are null. // IsNull(x) where x is a row type does not mean whether the individual properties of x are null, // but rather whether the entire row is null. // FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(keyVar)), flattentedKeys); FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(copyOfKeyVar)), copyFlattenedKeys); } PlanCompiler.Assert(flattentedKeys.Count == copyFlattenedKeys.Count, "The flattened keys lists should have the same nubmer of elements"); Node filterPredicateNode = null; for(int j = 0; j< flattentedKeys.Count; j++) { Node keyNode = flattentedKeys[j]; Node copyKeyNode = copyFlattenedKeys[j]; // // Create the predicate for a single key // keyVar = copyOfKeyVar or keyVar is null and copyOfKeyVar is null // Node predicate = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Or), _iqtCommand.CreateNode( _iqtCommand.CreateComparisonOp(OpType.EQ), keyNode, copyKeyNode), _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.And), _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.IsNull), OpCopier.Copy(_iqtCommand, keyNode)), _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.IsNull), OpCopier.Copy(_iqtCommand, copyKeyNode)))); if (filterPredicateNode == null) { filterPredicateNode = predicate; } else { filterPredicateNode = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.And), filterPredicateNode, predicate); } } Node filterNode = _iqtCommand.CreateNode( _iqtCommand.CreateFilterOp(), projectNodeWithKeys, filterPredicateNode); groupDefNode = filterNode; } //Cap with Collect over PhysicalProject _varMap[groupDefNode] = inputVar; groupDefNode = ConvertRelOpToScalarOpTree(groupDefNode, inputResultType); Node result = _iqtCommand.CreateVarDefNode(groupDefNode, out groupAggVar); return result; } /// /// If the return type of the input node is a RowType it flattens its individual non-row properties. /// The produced nodes are added to the given flattenedProperties list /// /// /// private void FlattenProperties(Node input, IListflattenedProperties) { if (input.Op.Type.EdmType.BuiltInTypeKind == BuiltInTypeKind.RowType) { IList properties = TypeHelpers.GetProperties(input.Op.Type); PlanCompiler.Assert(properties.Count != 0, "No nested properties for RowType"); for (int i = 0; i < properties.Count; i++) { Node newInput = (i == 0) ? input : OpCopier.Copy(_iqtCommand, input); FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreatePropertyOp(properties[i]), newInput), flattenedProperties); } } else { flattenedProperties.Add(input); } } /// /// Common processing for the identical input and sort order arguments to the unrelated /// DbSkipExpression and DbSortExpression types. /// /// The input DbExpressionBinding from the DbSkipExpression or DbSortExpression /// The list of SortClauses from the DbSkipExpression or DbSortExpression /// A list to contain the converted SortKeys produced from the SortClauses /// The Var produced by the input to the DbSkipExpression or DbSortExpression ////// The converted form of the input to the DbSkipExpression or DbSortExpression, capped by a /// ProjectOp that defines and Vars referenced by the SortKeys. /// private Node VisitSortArguments(DbExpressionBinding input, IListsortOrder, List sortKeys, out Var inputVar) { // // Skip/DbSortExpression conversion first produces a ProjectOp over the original input. // This is done to ensure that the new (Constrained)SortOp itself does not // contain any local variable definitions (in the form of a VarDefList child node) // which makes it simpler to pull SortOps over ProjectOps later in the PlanCompiler // (specifically the PreProcessor). // The new ProjectOp projects the output Var of the input along with any Vars referenced // by the SortKeys, and its VarDefList child defines those Vars. // // Bring the variable defined by the DbSortExpression's input set into scope // and retrieve it from the Node => Var map for later use. // Node inputNode = EnterExpressionBinding(input); inputVar = _varMap[inputNode]; // // Convert the SortClauses, building a new VarDefOp Node for each one. // VarVec projectedVars = _iqtCommand.CreateVarVec(); projectedVars.Set(inputVar); List sortVarDefs = new List (); PlanCompiler.Assert(sortKeys.Count == 0, "Non-empty SortKey list before adding converted SortClauses"); for (int idx = 0; idx < sortOrder.Count; idx++) { DbSortClause clause = sortOrder[idx]; // // Convert the DbSortClause DbExpression to a Node/Op pair // Node exprNode = VisitExprAsScalar(clause.Expression); // // In a valid CQT, DbSortClause expressions must have a result of an OrderComparable Type, // and such expressions will always convert to ScalarOps. // ScalarOp specOp = exprNode.Op as ScalarOp; PlanCompiler.Assert(specOp != null, "DbSortClause Expression converted to non-ScalarOp"); // // Create a new ComputedVar with the same Type as the result Type of the DbSortClause DbExpression // Var specVar; // // Create a new VarDefOp Node that defines the ComputedVar and add it both to the // list of VarDefs and the VarVec of produced Vars that will be used to create a // SortKey-defining ProjectOp over the Sort input. // sortVarDefs.Add(_iqtCommand.CreateVarDefNode(exprNode, out specVar)); projectedVars.Set(specVar); // // Create a new IQT SortKey that references the ComputedVar and has the same // Ascending and Collation as the original DbSortClause, then add it to the list of SortKeys. // SortKey sortKey = null; if (string.IsNullOrEmpty(clause.Collation)) { sortKey = Command.CreateSortKey(specVar, clause.Ascending); } else { sortKey = Command.CreateSortKey(specVar, clause.Ascending, clause.Collation); } sortKeys.Add(sortKey); } // // Now that the SortClauses have been converted, remove the Input set's variable from scope. // ExitExpressionBinding(); // // Cap the Input with a ProjectOp that pushes the sort key VarDefs down to that projection. // inputNode = _iqtCommand.CreateNode( _iqtCommand.CreateProjectOp(projectedVars), inputNode, _iqtCommand.CreateNode( _iqtCommand.CreateVarDefListOp(), sortVarDefs ) ); return inputNode; } public override Node Visit(DbSkipExpression expression) { // // Invoke common processing of Skip/DbSortExpression arguments. // Var inputVar; List sortKeys = new List (); Node inputNode = VisitSortArguments(expression.Input, expression.SortOrder, sortKeys, out inputVar); // // Visit the Skip Count // Node countNode = VisitExprAsScalar(expression.Count); // // Create a new Node that has a new ConstrainedSortOp based on the SortKeys as its Op // and the following children: // - The Input node from VisitSortArguments // - The converted form of the skip count // - A NullOp of type Int64 to indicate that no limit operation is applied // Node skipNode = _iqtCommand.CreateNode( _iqtCommand.CreateConstrainedSortOp(sortKeys), inputNode, countNode, _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)) ); // Update the Node --> Var mapping for the new ConstrainedSort Node. // ConstrainedSortOp maps to the same Op that its RelOp input maps to. _varMap[skipNode] = inputVar; return skipNode; } public override Node Visit(DbSortExpression e) { // // Invoke common processing of Skip/DbSortExpression arguments. // Var inputVar; List sortKeys = new List (); Node inputNode = VisitSortArguments(e.Input, e.SortOrder, sortKeys, out inputVar); // // Create a new SortOp that uses the constructed SortKeys. // SortOp newSortOp = _iqtCommand.CreateSortOp(sortKeys); // // Create a new SortOp Node that has the new SortOp as its Op the Key-defining ProjectOp Node as its only child. // Node newSortNode = _iqtCommand.CreateNode(newSortOp, inputNode); // Update the Node --> Var mapping for the new Sort Node. // SortOp maps to the same Op that its RelOp input maps to. _varMap[newSortNode] = inputVar; return newSortNode; } public override Node Visit(DbQuantifierExpression e) { Node retNode = null; // // Any converts to Exists(Filter(Input, Predicate)) // All converts to Not(Exists(Filter(Input, Or(Not(Predicate), IsNull(Predicate))))) // PlanCompiler.Assert(DbExpressionKind.Any == e.ExpressionKind || DbExpressionKind.All == e.ExpressionKind, "Invalid DbExpressionKind in DbQuantifierExpression"); // // Bring the input's variable into scope // Node inputNode = EnterExpressionBinding(e.Input); // // Convert the predicate // Node predicateNode = VisitExprAsPredicate(e.Predicate); // // If the quantifier is All then the predicate must become 'Not(Predicate) Or IsNull(Predicate)', // since the converted form of the predicate should exclude a member of the input set if and only if // the predicate evaluates to False - filtering only with the negated predicate would also exclude members // for which that negated predicate evaluates to null, possibly resulting in an erroneous empty result set // and causing the quantifier to produce a false positive result. // if (DbExpressionKind.All == e.ExpressionKind) { // Create the 'Not(Predicate)' branch of the Or. predicateNode = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Not), predicateNode ); // Visit the original predicate for use in the 'IsNull(Predicate)' branch of the Or. // Note that this is treated as a scalar value rather than a Boolean predicate. Node predicateCopy = VisitExprAsScalar(e.Predicate); // Create the 'IsNull(Predicate)' branch of the Or. predicateCopy = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.IsNull), predicateCopy ); // Finally, combine the branches with a Boolean 'Or' Op to create the updated predicate node. predicateNode = _iqtCommand.CreateNode( _iqtCommand.CreateConditionalOp(OpType.Or), predicateNode, predicateCopy ); } // // Remove the input's variable from scope // ExitExpressionBinding(); // // Create a FilterOp around the original input set and map the FilterOp to the Var produced by the original input set. // Var inputVar = _varMap[inputNode]; inputNode = _iqtCommand.CreateNode(_iqtCommand.CreateFilterOp(), inputNode, predicateNode); _varMap[inputNode] = inputVar; // // Create an ExistsOp around the filtered set to perform the quantifier operation. // retNode = _iqtCommand.CreateNode(_iqtCommand.CreateExistsOp(), inputNode); // // For All, the exists operation as currently built must now be negated. // if (DbExpressionKind.All == e.ExpressionKind) { retNode = _iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), retNode); } return retNode; } #endregion } } // 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
- SymbolEqualComparer.cs
- SerializationObjectManager.cs
- StringSorter.cs
- AsyncStreamReader.cs
- CommonGetThemePartSize.cs
- LockedAssemblyCache.cs
- PropertyInformation.cs
- LinqMaximalSubtreeNominator.cs
- XhtmlBasicValidationSummaryAdapter.cs
- DecoderNLS.cs
- SHA384.cs
- OleServicesContext.cs
- ConfigurationStrings.cs
- CompositionDesigner.cs
- IResourceProvider.cs
- DocobjHost.cs
- PageThemeCodeDomTreeGenerator.cs
- _DigestClient.cs
- SqlDataSourceTableQuery.cs
- PointIndependentAnimationStorage.cs
- TextureBrush.cs
- RegexInterpreter.cs
- FtpWebRequest.cs
- MessageBodyDescription.cs
- UInt16Storage.cs
- SerializableAttribute.cs
- Substitution.cs
- TextWriterTraceListener.cs
- IsolatedStoragePermission.cs
- CodeComment.cs
- RowToFieldTransformer.cs
- XmlTextAttribute.cs
- Int32Storage.cs
- DialogResultConverter.cs
- IConvertible.cs
- DbProviderFactories.cs
- WizardStepBase.cs
- OLEDB_Util.cs
- TypeInfo.cs
- SqlBooleanMismatchVisitor.cs
- QueryableFilterUserControl.cs
- altserialization.cs
- EntityDesignerBuildProvider.cs
- PropertyDescriptors.cs
- ISAPIApplicationHost.cs
- SimplePropertyEntry.cs
- NotifyParentPropertyAttribute.cs
- ScrollItemPatternIdentifiers.cs
- ExpressionNormalizer.cs
- TabRenderer.cs
- WebPartConnectionsCancelEventArgs.cs
- NestPullup.cs
- XmlSchemaExternal.cs
- BaseValidatorDesigner.cs
- ResourceCategoryAttribute.cs
- SqlConnectionStringBuilder.cs
- LambdaCompiler.Logical.cs
- OverrideMode.cs
- HtmlInputSubmit.cs
- XmlSchema.cs
- SendMailErrorEventArgs.cs
- StretchValidation.cs
- Rijndael.cs
- ExpressionTextBox.xaml.cs
- SoapExtensionStream.cs
- HttpCachePolicyElement.cs
- RelationshipConverter.cs
- IPHostEntry.cs
- StoreAnnotationsMap.cs
- SoapAttributeAttribute.cs
- SqlXml.cs
- MissingSatelliteAssemblyException.cs
- GeometryHitTestResult.cs
- GrammarBuilderPhrase.cs
- ServiceManagerHandle.cs
- PropertyItemInternal.cs
- ScaleTransform.cs
- ProjectionCamera.cs
- ServiceManagerHandle.cs
- XmlConvert.cs
- RegexInterpreter.cs
- DescriptionAttribute.cs
- StrongNamePublicKeyBlob.cs
- ClientSettingsSection.cs
- ArraySubsetEnumerator.cs
- GridViewCellAutomationPeer.cs
- Events.cs
- BaseUriHelper.cs
- RelatedEnd.cs
- EntryIndex.cs
- Site.cs
- DataPagerFieldItem.cs
- SqlClientFactory.cs
- XPathNavigatorReader.cs
- Freezable.cs
- RepeatInfo.cs
- IDispatchConstantAttribute.cs
- TextBoxBase.cs
- WindowsListViewItemStartMenu.cs
- NegotiationTokenAuthenticator.cs