1 //---------------------------------------------------------------------
2 // <copyright file="ITreeGenerator.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
7 // @backupOwner Microsoft
8 //---------------------------------------------------------------------
10 //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
12 // It is fine to use Debug.Assert in cases where you assert an obvious thing that is supposed
13 // to prevent from simple mistakes during development (e.g. method argument validation
14 // in cases where it was you who created the variables or the variables had already been validated or
15 // in "else" clauses where due to code changes (e.g. adding a new value to an enum type) the default
16 // "else" block is chosen why the new condition should be treated separately). This kind of asserts are
17 // (can be) helpful when developing new code to avoid simple mistakes but have no or little value in
18 // the shipped product.
19 // PlanCompiler.Assert *MUST* be used to verify conditions in the trees. These would be assumptions
20 // about how the tree was built etc. - in these cases we probably want to throw an exception (this is
21 // what PlanCompiler.Assert does when the condition is not met) if either the assumption is not correct
22 // or the tree was built/rewritten not the way we thought it was.
23 // Use your judgment - if you rather remove an assert than ship it use Debug.Assert otherwise use
24 // PlanCompiler.Assert.
26 namespace System.Data.Query.PlanCompiler
29 using System.Collections.Generic;
31 using System.Data.Common;
32 using System.Data.Common.CommandTrees;
33 using System.Data.Common.CommandTrees.ExpressionBuilder;
34 using System.Data.Common.Utils;
35 using System.Data.Entity;
36 using System.Data.Entity.Util;
37 using System.Data.Metadata.Edm;
38 using System.Data.Query.InternalTrees;
41 internal class ITreeGenerator : DbExpressionVisitor<Node>
45 /// Abstract base class for both DbExpressionBinding and LambdaFunction scopes
47 private abstract class CqtVariableScope
49 internal abstract bool Contains(string varName);
50 internal abstract Node this[string varName] { get; }
52 /// Returns true if it is a lambda variable representing a predicate expression.
54 internal abstract bool IsPredicate(string varName);
58 /// Represents a variable scope introduced by a CQT DbExpressionBinding, and therefore contains a single variable.
60 private class ExpressionBindingScope : CqtVariableScope
62 private Command _tree;
63 private string _varName;
66 internal ExpressionBindingScope(Command iqtTree, string name, Var iqtVar)
73 internal override bool Contains(string name) { return (_varName == name); }
74 internal override Node this[string name]
78 PlanCompiler.Assert(name == _varName,"huh?");
79 return _tree.CreateNode(_tree.CreateVarRefOp(_var));
82 internal override bool IsPredicate(string varName)
87 internal Var ScopeVar { get { return _var; } }
91 /// Represents a variable scope introduced by a LambdaFunction.
93 private sealed class LambdaScope : CqtVariableScope
95 private readonly ITreeGenerator _treeGen;
96 private readonly Command _command;
98 /// varName : [node, IsPredicate]
100 private readonly Dictionary<string, Tuple<Node, bool>> _arguments;
101 private readonly Dictionary<Node, bool> _referencedArgs;
103 internal LambdaScope(ITreeGenerator treeGen, Command command, Dictionary<string, Tuple<Node, bool>> args)
108 _referencedArgs = new Dictionary<Node, bool>(_arguments.Count);
111 internal override bool Contains(string name) { return (_arguments.ContainsKey(name)); }
112 internal override Node this[string name]
116 PlanCompiler.Assert(_arguments.ContainsKey(name), "LambdaScope indexer called for invalid Var");
118 Node argNode = _arguments[name].Item1;
119 if (_referencedArgs.ContainsKey(argNode))
121 // The specified argument has already been substituted into the
122 // IQT and so this substitution requires a copy of the argument.
123 VarMap mappedVars = null;
125 // This is a 'deep copy' operation that clones the entire subtree rooted at the node.
126 Node argCopy = OpCopier.Copy(_command, argNode, out mappedVars);
128 // If any Nodes in the copy of the argument produce Vars then the
129 // Node --> Var map must be updated to include them.
130 if (mappedVars.Count > 0)
132 List<Node> sources = new List<Node>(1);
133 sources.Add(argNode);
135 List<Node> copies = new List<Node>(1);
138 MapCopiedNodeVars(sources, copies, mappedVars);
145 // This is the first reference of the lambda argument, so the Node itself
146 // can be returned rather than a copy, but the dictionary that tracks
147 // whether or not an argument has been referenced needs to be updated.
148 _referencedArgs[argNode] = true;
155 internal override bool IsPredicate(string name)
157 PlanCompiler.Assert(_arguments.ContainsKey(name), "LambdaScope indexer called for invalid Var");
158 return _arguments[name].Item2;
161 private void MapCopiedNodeVars(IList<Node> sources, IList<Node> copies, Dictionary<Var, Var> varMappings)
163 PlanCompiler.Assert(sources.Count == copies.Count, "Source/Copy Node count mismatch");
166 // For each Source/Copy Node in the two lists:
167 // - Recursively update the Node --> Var map for any child nodes
168 // - If the Source Node is mapped to a Var, then retrieve the new Var
169 // produced by the Op copier that corresponds to that Source Var, and
170 // add an entry to the Node --> Var map that maps the Copy Node to the
173 for (int idx = 0; idx < sources.Count; idx++)
175 Node sourceNode = sources[idx];
176 Node copyNode = copies[idx];
178 if (sourceNode.Children.Count > 0)
180 MapCopiedNodeVars(sourceNode.Children, copyNode.Children, varMappings);
183 Var sourceVar = null;
184 if (_treeGen.VarMap.TryGetValue(sourceNode, out sourceVar))
186 PlanCompiler.Assert(varMappings.ContainsKey(sourceVar), "No mapping found for Var in Var to Var map from OpCopier");
187 this._treeGen.VarMap[copyNode] = varMappings[sourceVar];
194 private static Dictionary<DbExpressionKind, OpType> s_opMap = InitializeExpressionKindToOpTypeMap();
196 private readonly Command _iqtCommand;
197 private readonly Stack<CqtVariableScope> _varScopes = new Stack<CqtVariableScope>();
198 private readonly Dictionary<Node, Var> _varMap = new Dictionary<Node, Var>();
199 private readonly Stack<EdmFunction> _functionExpansions = new Stack<EdmFunction>();
201 /// Maintained for lambda and model-defined function applications (DbLambdaExpression and DbFunctionExpression).
203 private readonly Dictionary<DbExpression, bool> _functionsIsPredicateFlag = new Dictionary<DbExpression, bool>();
205 // Used to track which IsOf type filter expressions have already been processed
206 private readonly HashSet<DbFilterExpression> _processedIsOfFilters = new HashSet<DbFilterExpression>();
207 private readonly HashSet<DbTreatExpression> _fakeTreats = new HashSet<DbTreatExpression>();
209 // leverage discriminator metadata in the top-level project when translating query mapping views...
210 private readonly System.Data.Mapping.ViewGeneration.DiscriminatorMap _discriminatorMap;
211 private readonly DbProjectExpression _discriminatedViewTopProject;
215 /// Initialize the DbExpressionKind --> OpType mappings for DbComparisonExpression and DbArithmeticExpression
217 private static Dictionary<DbExpressionKind, OpType> InitializeExpressionKindToOpTypeMap()
219 Dictionary<DbExpressionKind, OpType> opMap = new Dictionary<DbExpressionKind, OpType>(12);
222 // Arithmetic operators
224 opMap[DbExpressionKind.Plus] = OpType.Plus;
225 opMap[DbExpressionKind.Minus] = OpType.Minus;
226 opMap[DbExpressionKind.Multiply] = OpType.Multiply;
227 opMap[DbExpressionKind.Divide] = OpType.Divide;
228 opMap[DbExpressionKind.Modulo] = OpType.Modulo;
229 opMap[DbExpressionKind.UnaryMinus] = OpType.UnaryMinus;
232 // Comparison operators
234 opMap[DbExpressionKind.Equals] = OpType.EQ;
235 opMap[DbExpressionKind.NotEquals] = OpType.NE;
236 opMap[DbExpressionKind.LessThan] = OpType.LT;
237 opMap[DbExpressionKind.GreaterThan] = OpType.GT;
238 opMap[DbExpressionKind.LessThanOrEquals] = OpType.LE;
239 opMap[DbExpressionKind.GreaterThanOrEquals] = OpType.GE;
244 internal Dictionary<Node, Var> VarMap { get { return _varMap; } }
246 public static Command Generate(DbQueryCommandTree ctree)
248 return Generate(ctree, null);
252 /// Generate an IQT given a query command tree and discriminator metadata (available for certain query mapping views)
254 internal static Command Generate(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap)
256 ITreeGenerator treeGenerator = new ITreeGenerator(ctree, discriminatorMap);
257 return treeGenerator._iqtCommand;
260 private ITreeGenerator(DbQueryCommandTree ctree, System.Data.Mapping.ViewGeneration.DiscriminatorMap discriminatorMap)
263 // Create a new IQT Command instance that uses the same metadata workspace as the incoming command tree
265 _iqtCommand = new Command(ctree.MetadataWorkspace);
268 // When translating a query mapping view matching the TPH discrimination pattern, remember the top level discriminator map
269 // (leveraged to produced a DiscriminatedNewInstanceOp for the top-level projection in the view)
271 if (null != discriminatorMap)
273 _discriminatorMap = discriminatorMap;
274 // see System.Data.Mapping.ViewGeneration.DiscriminatorMap
275 PlanCompiler.Assert(ctree.Query.ExpressionKind == DbExpressionKind.Project,
276 "top level QMV expression must be project to match discriminator pattern");
277 _discriminatedViewTopProject = (DbProjectExpression)ctree.Query;
281 // For each Parameter declared by the command tree, add a ParameterVar to the set of parameter vars maintained by the conversion visitor.
282 // Each ParameterVar has the same name and type as the corresponding parameter on the command tree.
284 foreach (KeyValuePair<string, TypeUsage> paramInfo in ctree.Parameters)
286 if (!ValidateParameterType(paramInfo.Value))
288 throw EntityUtil.NotSupported(System.Data.Entity.Strings.ParameterTypeNotSupported(paramInfo.Key, paramInfo.Value.ToString()));
290 _iqtCommand.CreateParameterVar(paramInfo.Key, paramInfo.Value);
293 // Convert into an ITree
294 _iqtCommand.Root = VisitExpr(ctree.Query);
297 // If the root of the tree is not a relop, build up a fake project over a
298 // a singlerowtableOp.
299 // "s" => Project(SingleRowTableOp, "s")
301 if (!_iqtCommand.Root.Op.IsRelOp)
303 Node scalarExpr = ConvertToScalarOpTree(_iqtCommand.Root, ctree.Query);
304 Node singletonTableNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowTableOp());
306 Node varDefListNode = _iqtCommand.CreateVarDefListNode(scalarExpr, out newVar);
307 ProjectOp projectOp = _iqtCommand.CreateProjectOp(newVar);
310 Node newRoot = _iqtCommand.CreateNode(projectOp, singletonTableNode, varDefListNode);
312 if (TypeSemantics.IsCollectionType(_iqtCommand.Root.Op.Type))
314 UnnestOp unnestOp = _iqtCommand.CreateUnnestOp(newVar);
315 newRoot = _iqtCommand.CreateNode(unnestOp, varDefListNode.Child0);
316 newVar = unnestOp.Table.Columns[0];
319 _iqtCommand.Root = newRoot;
320 _varMap[_iqtCommand.Root] = newVar;
325 // Ensure that the topmost portion of the query is capped by a
326 // PhysicalProject expression
328 _iqtCommand.Root = CapWithPhysicalProject(_iqtCommand.Root);
331 private static bool ValidateParameterType(TypeUsage paramType)
333 return (paramType != null && paramType.EdmType != null &&
334 (TypeSemantics.IsPrimitiveType(paramType) || paramType.EdmType is EnumType));
337 #region DbExpressionVisitor Helpers
339 private static RowType ExtractElementRowType(TypeUsage typeUsage)
341 return TypeHelpers.GetEdmType<RowType>(TypeHelpers.GetEdmType<CollectionType>(typeUsage).TypeUsage);
345 private static bool IsCollectionOfRecord(TypeUsage typeUsage)
347 CollectionType collectionType;
348 return (TypeHelpers.TryGetEdmType<CollectionType>(typeUsage, out collectionType) &&
349 collectionType != null &&
350 TypeSemantics.IsRowType(collectionType.TypeUsage));
355 /// Is the current expression a predicate?
357 /// <param name="expr">expr to check</param>
358 /// <returns>true, if the expression is a predicate</returns>
359 private bool IsPredicate(DbExpression expr)
361 if (TypeSemantics.IsPrimitiveType(expr.ResultType, PrimitiveTypeKind.Boolean))
363 switch (expr.ExpressionKind)
365 case DbExpressionKind.Equals:
366 case DbExpressionKind.NotEquals:
367 case DbExpressionKind.LessThan:
368 case DbExpressionKind.LessThanOrEquals:
369 case DbExpressionKind.GreaterThan:
370 case DbExpressionKind.GreaterThanOrEquals:
371 case DbExpressionKind.And:
372 case DbExpressionKind.Or:
373 case DbExpressionKind.Not:
374 case DbExpressionKind.Like:
375 case DbExpressionKind.IsEmpty:
376 case DbExpressionKind.IsNull:
377 case DbExpressionKind.IsOf:
378 case DbExpressionKind.IsOfOnly:
379 case DbExpressionKind.Any:
380 case DbExpressionKind.All:
382 case DbExpressionKind.VariableReference:
383 var varRef = (DbVariableReferenceExpression)expr;
384 return ResolveScope(varRef).IsPredicate(varRef.VariableName);
385 case DbExpressionKind.Lambda:
388 bool isPredicateFunction;
389 if (_functionsIsPredicateFlag.TryGetValue(expr, out isPredicateFunction))
391 return isPredicateFunction;
395 // It is important that IsPredicate is called after the expression has been visited, otherwise
396 // _functionsIsPredicateFlag map will not contain an entry for the lambda
397 PlanCompiler.Assert(false, "IsPredicate must be called on a visited lambda expression");
401 case DbExpressionKind.Function:
404 EdmFunction edmFunction = ((DbFunctionExpression)expr).Function;
405 if (edmFunction.HasUserDefinedBody)
407 bool isPredicateFunction;
408 if (_functionsIsPredicateFlag.TryGetValue(expr, out isPredicateFunction))
410 return isPredicateFunction;
414 // It is important that IsPredicate is called after the expression has been visited, otherwise
415 // _functionsIsPredicateFlag map will not contain an entry for the function with a definition
416 PlanCompiler.Assert(false, "IsPredicate must be called on a visited function expression");
436 /// Callback to process an expression
438 /// <param name="e">The expression to convert</param>
439 /// <returns></returns>
440 private delegate Node VisitExprDelegate(DbExpression e);
442 private Node VisitExpr(DbExpression e)
450 return e.Accept<Node>(this);
455 /// Convert this expression into a "scalar value" ITree expression. There are two main
457 /// <param name="expr"></param>
458 /// <returns></returns>
459 private Node VisitExprAsScalar(DbExpression expr)
466 Node node = VisitExpr(expr); // the real work
467 node = ConvertToScalarOpTree(node, expr);
472 /// Convert an Itree node into a scalar op tree
474 /// <param name="node">the subtree</param>
475 /// <param name="expr">the original CQT expression</param>
476 /// <returns>the converted subtree</returns>
477 private Node ConvertToScalarOpTree(Node node, DbExpression expr)
480 // If the current expression is a collection, and we've simply produced a RelOp
481 // then we need to add a CollectOp above a PhysicalProjectOp above the RelOp
485 node = ConvertRelOpToScalarOpTree(node, expr.ResultType);
488 // If the current expression is a boolean, and it is really a predicate, then
489 // scalarize the predicate (ie) convert it into a "case when <predicate> then 'true' else 'false' end" expression
490 // SQLBUDT #431406: handle 3-valued logic for all predicates except IsNull
491 // Convert boolean predicate p into
492 // case when p then true when not(p) then false else null end
494 else if (IsPredicate(expr))
496 node = ConvertPredicateToScalarOpTree(node, expr);
503 /// Convert a rel op Itree node into a scalar op tree
505 /// <param name="node"></param>
506 /// <param name="resultType"></param>
507 /// <returns></returns>
508 private Node ConvertRelOpToScalarOpTree(Node node, TypeUsage resultType)
510 PlanCompiler.Assert(TypeSemantics.IsCollectionType(resultType), "RelOp with non-Collection result type");
511 CollectOp collectOp = _iqtCommand.CreateCollectOp(resultType);
513 // I'm not thrilled about having to build a PhysicalProjectOp here - this
514 // is definitely something I will need to revisit soon
516 Node projectNode = CapWithPhysicalProject(node);
517 node = _iqtCommand.CreateNode(collectOp, projectNode);
523 /// Scalarize the predicate (x = y) by converting it into a "case when x = y then 'true' else 'false' end" expression.
525 private Node ConvertPredicateToScalarOpTree(Node node, DbExpression expr)
527 CaseOp caseOp = _iqtCommand.CreateCaseOp(_iqtCommand.BooleanType);
529 //For 2-valued logic there are 3 arguments, for 3-valued there are 5
530 List<Node> arguments = new List<Node>((expr.ExpressionKind == DbExpressionKind.IsNull) ? 3 : 5);
532 //Add the original as the first when
535 //Add the first then, the true node
536 arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)));
538 //If the expression has 3-valued logic, add a second when
539 if (expr.ExpressionKind != DbExpressionKind.IsNull)
541 Node predCopy = VisitExpr(expr);
542 arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), predCopy));
545 //Add the false node: for 3 valued logic this is the second then, for 2 valued the else
546 arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, false)));
548 //The null node, it is the else-clause for 3-valued logic
549 if (expr.ExpressionKind != DbExpressionKind.IsNull)
551 arguments.Add(_iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.BooleanType)));
554 node = _iqtCommand.CreateNode(caseOp, arguments);
559 /// Convert an expression into an iqt predicate
561 /// <param name="expr">the expression to process</param>
562 /// <returns></returns>
563 private Node VisitExprAsPredicate(DbExpression expr)
570 Node node = VisitExpr(expr);
573 // If the current expression is not a predicate, then we need to make it one, by
574 // comparing it with the constant 'true'
576 if (!IsPredicate(expr))
578 ComparisonOp comparisonOp = _iqtCommand.CreateComparisonOp(OpType.EQ);
579 Node trueNode = _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true));
580 node = _iqtCommand.CreateNode(comparisonOp, node, trueNode);
584 PlanCompiler.Assert(!node.Op.IsRelOp, "unexpected relOp as predicate?");
591 /// Process a list of expressions, and apply the delegate to each of the expressions
593 /// <param name="exprs">list of cqt expressions to process</param>
594 /// <param name="exprDelegate">the callback to apply</param>
595 /// <returns>a list of IQT expressions</returns>
596 private static IList<Node> VisitExpr(IList<DbExpression> exprs, VisitExprDelegate exprDelegate)
598 List<Node> nodeList = new List<Node>();
599 for(int idx = 0; idx < exprs.Count; idx++)
601 nodeList.Add(exprDelegate(exprs[idx]));
607 /// Process a set of cqt expressions - and convert them into scalar iqt expressions
609 /// <param name="exprs">list of cqt expressions</param>
610 /// <returns>list of iqt expressions</returns>
611 private IList<Node> VisitExprAsScalar(IList<DbExpression> exprs)
613 return VisitExpr(exprs, VisitExprAsScalar);
616 private Node VisitUnary(DbUnaryExpression e, Op op, VisitExprDelegate exprDelegate)
618 return _iqtCommand.CreateNode(op, exprDelegate(e.Argument));
621 private Node VisitBinary(DbBinaryExpression e, Op op, VisitExprDelegate exprDelegate)
623 return _iqtCommand.CreateNode(op, exprDelegate(e.Left), exprDelegate(e.Right));
627 /// 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.
629 /// <param name="inputNode">The input Node/Op pair</param>
630 /// <returns>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)</returns>
631 private Node EnsureRelOp(Node inputNode)
636 Op inputOp = inputNode.Op;
639 // If the Op is already a RelOp then simply return its Node
647 // Assert that the input is a ScalarOp (CQT expressions should only ever produce RelOps or ScalarOps)
649 ScalarOp scalar = inputOp as ScalarOp;
650 PlanCompiler.Assert(scalar != null, "An expression in a CQT produced a non-ScalarOp and non-RelOp output Op");
653 // Assert that the ScalarOp has a collection result type. EnsureRelOp is called to ensure that arguments to
654 // RelOps are either also RelOps or are ScalarOps that produce a collection, which can be wrapped in an
655 // unnest to produce a RelOp.
657 PlanCompiler.Assert(TypeSemantics.IsCollectionType(scalar.Type), "An expression used as a RelOp argument was neither a RelOp or a collection");
660 // If the ScalarOp represents the nesting of an existing RelOp, simply return that RelOp instead.
661 // CollectOp(PhysicalProjectOp(x)) => x
663 CollectOp collect = inputOp as CollectOp;
666 PlanCompiler.Assert(inputNode.HasChild0, "CollectOp without argument");
667 if (inputNode.Child0.Op as PhysicalProjectOp != null)
669 PlanCompiler.Assert(inputNode.Child0.HasChild0, "PhysicalProjectOp without argument");
670 PlanCompiler.Assert(inputNode.Child0.Child0.Op.IsRelOp, "PhysicalProjectOp applied to non-RelOp input");
673 // The structure of the Input is Collect(PhysicalProject(x)), so return x
675 return inputNode.Child0.Child0;
680 // Create a new VarDefOp that defines the computed var that represents the ScalarOp collection.
681 // This var is the input to the UnnestOp.
684 Var inputCollectionVar;
685 Node varDefNode = _iqtCommand.CreateVarDefNode(inputNode, out inputCollectionVar);
688 // Create an UnnestOp that references the computed var created above. The VarDefOp that defines the var
689 // using the original input Node/Op pair becomes a child of the UnnestOp.
691 UnnestOp unnest = _iqtCommand.CreateUnnestOp(inputCollectionVar);
692 PlanCompiler.Assert(unnest.Table.Columns.Count == 1, "Unnest of collection ScalarOp produced unexpected number of columns (1 expected)");
695 // Create the unnest node, N3
696 // The UnnestOp produces a new Var, the single ColumnVar produced by the table that results from the Unnest.
698 Node unnestNode = _iqtCommand.CreateNode(unnest, varDefNode);
699 _varMap[unnestNode] = unnest.Table.Columns[0];
702 // Create a Project node above the Unnest, so we can simplify the work to eliminate
703 // the Unnest later. That means we need to create a VarRef to the column var in the
704 // table, a VarDef to define it, and a VarDefList to hold it, then a Project node, N4,
708 Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(unnest.Table.Columns[0]));
709 Node varDefListNode = _iqtCommand.CreateVarDefListNode(varRefNode, out projectVar);
711 ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar);
712 Node projectNode = _iqtCommand.CreateNode(projectOp, unnestNode, varDefListNode);
714 _varMap[projectNode] = projectVar;
720 /// Cap a RelOp with a ProjectOp. The output var of the Project is the
721 /// output var from the input
723 /// <param name="input">the input relop tree</param>
724 /// <returns>the relop tree with a projectNode at the root</returns>
725 private Node CapWithProject(Node input)
727 PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?");
728 if (input.Op.OpType == OpType.Project)
733 // Get the Var from the input; and build up a Project above it
734 Var inputVar = _varMap[input];
735 ProjectOp projectOp = _iqtCommand.CreateProjectOp(inputVar);
736 Node projectNode = _iqtCommand.CreateNode(projectOp, input,
737 _iqtCommand.CreateNode(_iqtCommand.CreateVarDefListOp()));
738 _varMap[projectNode] = inputVar;
744 /// Cap a relop tree with a PhysicalProjectOp. The Vars of the PhysicalProjectOp
745 /// are the vars from the RelOp tree
747 /// <param name="input">the input relop tree</param>
748 /// <returns>relop tree capped by a PhysicalProjectOp</returns>
749 private Node CapWithPhysicalProject(Node input)
751 PlanCompiler.Assert(input.Op.IsRelOp, "unexpected non-RelOp?");
753 // Get the Var from the input; and build up a Project above it
754 Var inputVar = _varMap[input];
755 PhysicalProjectOp projectOp = _iqtCommand.CreatePhysicalProjectOp(inputVar);
756 Node projectNode = _iqtCommand.CreateNode(projectOp, input);
762 /// 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.
764 /// <param name="binding">The DbExpressionBinding that defines the scope</param>
765 /// <returns>The Node produced by converting the binding's DbExpression</returns>
766 private Node EnterExpressionBinding(DbExpressionBinding binding)
768 return VisitBoundExpressionPushBindingScope(binding.Expression, binding.VariableName);
772 /// 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.
773 /// 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.
775 /// <param name="binding">The DbGroupExpressionBinding that defines the scope</param>
776 /// <returns>The Node produced by converting the binding's DbExpression</returns>
777 private Node EnterGroupExpressionBinding(DbGroupExpressionBinding binding)
779 return VisitBoundExpressionPushBindingScope(binding.Expression, binding.VariableName);
783 /// Common implementation method called by both EnterExpressionBinding and EnterGroupExpressionBinding
785 /// <param name="boundExpression">The DbExpression that defines the binding</param>
786 /// <param name="bindingName">The name of the binding variable</param>
787 /// <returns></returns>
788 private Node VisitBoundExpressionPushBindingScope(DbExpression boundExpression, string bindingName)
791 Node inputNode = VisitBoundExpression(boundExpression, out boundVar);
792 PushBindingScope(boundVar, bindingName);
797 /// Common implementation method called by both VisitBoundExpressionPushBindingScope and VisitJoin
799 /// <param name="boundExpression">The DbExpression that defines the binding</param>
800 /// <param name="boundVar">Var representing the RelOp produced for the <paramref name="boundExpression"/></param>
801 /// <returns></returns>
802 private Node VisitBoundExpression(DbExpression boundExpression, out Var boundVar)
805 // Visit the expression binding's DbExpression to convert it to a Node/Op pair
807 Node inputNode = VisitExpr(boundExpression);
808 PlanCompiler.Assert(inputNode != null, "DbExpressionBinding.Expression produced null conversion");
811 // Call EnsureRelOp on the converted Node and set inputNode equal to the result
813 inputNode = EnsureRelOp(inputNode);
816 // Retrieve the Var produced by the RelOp from the Node --> Var map
818 boundVar = _varMap[inputNode];
819 PlanCompiler.Assert(boundVar != null, "No Var found for Input Op");
825 /// Common implementation method called by both VisitBoundExpressionPushBindingScope and VisitJoin
827 /// <param name="boundVar">The Var produced by the RelOp from DbExpression that defines the binding</param>
828 /// <param name="bindingName">The name of the binding variable</param>
829 /// <returns></returns>
830 private void PushBindingScope(Var boundVar, string bindingName)
833 // Create a new ExpressionBindingScope using the VarName from the DbExpressionBinding and
834 // the Var associated with the Input RelOp, and push the new scope onto the variable scope stack.
836 _varScopes.Push(new ExpressionBindingScope(_iqtCommand, bindingName, boundVar));
840 /// 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.
842 /// <returns>The removed ExpressionBindingScope</returns>
843 private ExpressionBindingScope ExitExpressionBinding()
846 // Pop the scope from the variable scope stack, assert that it is a DbExpressionBinding scope, and return it.
848 ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope;
849 PlanCompiler.Assert(retScope != null, "ExitExpressionBinding called without ExpressionBindingScope on top of scope stack");
854 /// 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.
855 /// Should only be called after visiting the Aggregates of a DbGroupByExpression in Visit(DbGroupByExpression).
856 /// The sequence (in Visit(GroupExpression e) is:
857 /// 1. EnterGroupExpressionBinding
859 /// 3. ExitExpressionBinding
860 /// 4. (Push new scope with GroupVarName instead of VarName)
861 /// 5. Visit e.Aggregates
862 /// 6. ExitGroupExpressionBinding
864 private void ExitGroupExpressionBinding()
866 ExpressionBindingScope retScope = _varScopes.Pop() as ExpressionBindingScope;
867 PlanCompiler.Assert(retScope != null, "ExitGroupExpressionBinding called without ExpressionBindingScope on top of scope stack");
871 /// Creates a new variable scope that is based on a CQT DbLambda and pushes it onto the variable scope stack.
873 /// <param name="function">The DbLambda that defines the scope</param>
874 /// <param name="argumentValues">A list of Nodes and IsPredicate bits produced by converting the CQT Expressions that provide the arguments to the Lambda function</param>
875 /// <param name="expandingEdmFunction">an edm function for which the current lambda represents the generated body, otherwise null</param>
876 private void EnterLambdaFunction(DbLambda lambda, List<Tuple<Node, bool>> argumentValues, EdmFunction expandingEdmFunction)
878 IList<DbVariableReferenceExpression> lambdaParams = lambda.Variables;
880 var args = new Dictionary<string, Tuple<Node, bool>>();
882 foreach (var argumentValue in argumentValues)
884 args.Add(lambdaParams[idx].VariableName, argumentValue);
889 // If lambda represents an edm function body then check for a possible recursion in the function definition.
891 if (expandingEdmFunction != null)
894 // Check if we are already inside the function body.
896 if (_functionExpansions.Contains(expandingEdmFunction))
898 throw EntityUtil.CommandCompilation(Strings.Cqt_UDF_FunctionDefinitionWithCircularReference(expandingEdmFunction.FullName), null);
901 // Push the function before processing its body
903 _functionExpansions.Push(expandingEdmFunction);
906 _varScopes.Push(new LambdaScope(this, _iqtCommand, args));
910 /// 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.
912 /// <param name="expandingEdmFunction">an edm function for which the current lambda represents the generated body, otherwise null</param>
913 private LambdaScope ExitLambdaFunction(EdmFunction expandingEdmFunction)
916 // Pop the scope from the variable scope stack, assert that it is a Lambda scope, and return it.
918 LambdaScope retScope = _varScopes.Pop() as LambdaScope;
919 PlanCompiler.Assert(retScope != null, "ExitLambdaFunction called without LambdaScope on top of scope stack");
922 // If lambda represents an edm function body then pop the function from the expansion stack and make sure it is the expected one.
924 if (expandingEdmFunction != null)
926 EdmFunction edmFunction = _functionExpansions.Pop();
927 PlanCompiler.Assert(edmFunction == expandingEdmFunction, "Function expansion stack corruption: unexpected function at the top of the stack");
934 /// Constructs a NewRecordOp on top of a multi-Var-producing Op, resulting in a RelOp that produces a single Var.
936 /// <param name="inputNode">The Node that references the multi-Var-producing Op. This Node will become the first child node of the new ProjectOp's Node</param>
937 /// <param name="recType">Type metadata that describes the output record type</param>
938 /// <param name="colVars">A list of Vars that provide the output columns of the projection</param>
939 /// <returns>A new ProjectOp that projects a new record of the specified type from the specified Vars over the original input Op/Node</returns>
940 private Node ProjectNewRecord(Node inputNode, RowType recType, IEnumerable<Var> colVars)
943 // Create a list of VarRefOp Nodes that provide the column values for the new record
945 List<Node> recordColumns = new List<Node>();
946 foreach (Var colVar in colVars)
948 recordColumns.Add(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(colVar)));
952 // Create the NewRecordOp Node using the record column nodes as its child nodes
954 Node newRecordNode = _iqtCommand.CreateNode(_iqtCommand.CreateNewRecordOp(recType), recordColumns);
957 // Create a new ComputedVar and a VarDefOp that uses the NewRecordOp Node to define it
960 Node varDefNode = _iqtCommand.CreateVarDefListNode(newRecordNode, out newRecordVar);
963 // Create a ProjectOp with the single Computed Var defined by the new record construction
965 ProjectOp projection = _iqtCommand.CreateProjectOp(newRecordVar);
966 Node projectionNode = _iqtCommand.CreateNode(projection, inputNode, varDefNode);
967 _varMap[projectionNode] = newRecordVar;
969 return projectionNode;
973 #region DbExpressionVisitor<Node> Members
975 public override Node Visit(DbExpression e)
977 throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_General_UnsupportedExpression(e.GetType().FullName));
980 public override Node Visit(DbConstantExpression e)
982 // Don't use CreateInternalConstantOp - respect user-intent
984 // Note that it is only safe to call GetValue and access the
985 // constant value directly because any immutable values (byte[])
986 // will be cloned as the result expression is built in CTreeGenerator,
987 // during the call to DbExpressionBuilder.Constant in VisitConstantOp.
988 ConstantBaseOp op = _iqtCommand.CreateConstantOp(e.ResultType, e.GetValue());
989 return _iqtCommand.CreateNode(op);
992 public override Node Visit(DbNullExpression e)
994 NullOp op = _iqtCommand.CreateNullOp(e.ResultType);
995 return _iqtCommand.CreateNode(op);
998 public override Node Visit(DbVariableReferenceExpression e)
1000 Node varNode = ResolveScope(e)[e.VariableName];
1004 private CqtVariableScope ResolveScope(DbVariableReferenceExpression e)
1007 // Search the stack of variables scopes, top-down,
1008 // until the first one is found that defines a variable with the specified name.
1010 foreach (CqtVariableScope scope in _varScopes)
1012 if (scope.Contains(e.VariableName))
1019 // If the variable name was not resolved then either:
1020 // 1. The original CQT was invalid (should not be allowed into the ITreeGenerator).
1021 // 2. The variable scope stack itself is invalid.
1023 PlanCompiler.Assert(false, "CQT VarRef could not be resolved in the variable scope stack");
1027 public override Node Visit(DbParameterReferenceExpression e)
1029 Op op = _iqtCommand.CreateVarRefOp(_iqtCommand.GetParameter(e.ParameterName));
1030 return _iqtCommand.CreateNode(op);
1033 public override Node Visit(DbFunctionExpression e)
1035 Node retNode = null;
1037 if (e.Function.IsModelDefinedFunction)
1039 // This is a user-defined CSpace function with a body definition.
1040 // Try expanding it:
1041 // - replace the function call with the call to the body lambda,
1042 // - visit the lambda call expression.
1044 // Get/generate the body lambda. Wrap body generation exceptions.
1048 lambda = _iqtCommand.MetadataWorkspace.GetGeneratedFunctionDefinition(e.Function);
1050 catch (Exception exception)
1052 if (EntityUtil.IsCatchableExceptionType(exception))
1054 throw EntityUtil.CommandCompilation(Strings.Cqt_UDF_FunctionDefinitionGenerationFailed(e.Function.FullName), exception);
1059 // Visit the lambda call expression.
1060 // Argument types should be validated by now, hence the visitor should not throw under normal conditions.
1061 retNode = VisitLambdaExpression(lambda, e.Arguments, e, e.Function);
1063 else // a provider-manifest-defined or store function call - no expansion needed
1065 List<Node> argNodes = new List<Node>(e.Arguments.Count);
1066 for (int idx = 0; idx < e.Arguments.Count; idx++)
1068 // Ensure that any argument with a result type that does not exactly match the type of
1069 // the corresponding function parameter is enclosed in a SoftCastOp.
1070 argNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Arguments[idx]), e.Function.Parameters[idx].TypeUsage));
1073 retNode = _iqtCommand.CreateNode(_iqtCommand.CreateFunctionOp(e.Function), argNodes);
1079 public override Node Visit(DbLambdaExpression e)
1081 return VisitLambdaExpression(e.Lambda, e.Arguments, e, null);
1084 private Node VisitLambdaExpression(DbLambda lambda, IList<DbExpression> arguments, DbExpression applicationExpr, EdmFunction expandingEdmFunction)
1086 Node retNode = null;
1088 var argNodes = new List<Tuple<Node, bool>>(arguments.Count);
1089 foreach (DbExpression argExpr in arguments)
1091 // #484709: Lambda function parameters should not have enclosing SoftCastOps.
1092 argNodes.Add(Tuple.Create(VisitExpr(argExpr), IsPredicate(argExpr)));
1095 EnterLambdaFunction(lambda, argNodes, expandingEdmFunction);
1096 retNode = VisitExpr(lambda.Body);
1098 // Check the body to see if the current lambda yields a predicate.
1099 _functionsIsPredicateFlag[applicationExpr] = IsPredicate(lambda.Body);
1101 ExitLambdaFunction(expandingEdmFunction);
1106 #if METHOD_EXPRESSION
1107 public override Node Visit(MethodExpression e)
1109 throw EntityUtil.NotSupported();
1112 #region SoftCast Helpers
1114 /// This method builds a "soft"Cast operator over the input node (if necessary) to (soft)
1115 /// cast it to the desired type (targetType)
1117 /// If the input is a scalarOp, then we simply add on the SoftCastOp
1118 /// directly (if it is needed, of course). If the input is a RelOp, we create a
1119 /// new ProjectOp above the input, add a SoftCast above the Var of the
1120 /// input, and then return the new ProjectOp
1122 /// The "need to cast" is determined by the Command.EqualTypes function. All type
1123 /// equivalence in the plan compiler is determined by this function
1125 /// <param name="node">the expression to soft-cast</param>
1126 /// <param name="targetType">the desired type to cast to</param>
1127 /// <returns></returns>
1128 private Node BuildSoftCast(Node node, TypeUsage targetType)
1131 // If the input is a RelOp (say X), and the Var of the input is "x",
1132 // we convert this into
1133 // Project(X, softCast(x, t))
1134 // where t is the element type of the desired target type
1136 if (node.Op.IsRelOp)
1138 CollectionType targetCollectionType = TypeHelpers.GetEdmType<CollectionType>(targetType);
1139 targetType = targetCollectionType.TypeUsage;
1141 Var nodeVar = _varMap[node];
1142 // Do we need a cast at all?
1143 if (Command.EqualTypes(targetType, nodeVar.Type))
1148 // Build up the projectOp
1150 Node varRefNode = _iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(nodeVar));
1151 Node castNode = _iqtCommand.CreateNode(_iqtCommand.CreateSoftCastOp(targetType), varRefNode);
1152 Node varDefListNode = _iqtCommand.CreateVarDefListNode(castNode, out projectVar);
1154 ProjectOp projectOp = _iqtCommand.CreateProjectOp(projectVar);
1155 Node projectNode = _iqtCommand.CreateNode(projectOp, node, varDefListNode);
1157 _varMap[projectNode] = projectVar;
1162 PlanCompiler.Assert(node.Op.IsScalarOp, "I want a scalar op");
1163 if (Command.EqualTypes(node.Op.Type, targetType))
1169 SoftCastOp castOp = _iqtCommand.CreateSoftCastOp(targetType);
1170 return _iqtCommand.CreateNode(castOp, node);
1176 /// A variant of the function above. Works with an EdmType instead
1177 /// of a TypeUsage, but leverages all the work above
1179 /// <param name="node">the node to "cast"</param>
1180 /// <param name="targetType">the desired type</param>
1181 /// <returns>the transformed expression</returns>
1182 private Node BuildSoftCast(Node node, EdmType targetType)
1184 return BuildSoftCast(node, TypeUsage.Create(targetType));
1187 private Node BuildEntityRef(Node arg, TypeUsage entityType)
1189 TypeUsage refType = TypeHelpers.CreateReferenceTypeUsage((EntityType)entityType.EdmType);
1190 return _iqtCommand.CreateNode(_iqtCommand.CreateGetEntityRefOp(refType), arg);
1196 /// We simplify the property instance where the user is accessing a key member of
1197 /// a reference navigation. The instance becomes simply the reference key in such
1200 /// For instance, product.Category.CategoryID becomes Ref(product.Category).CategoryID,
1201 /// which gives us a chance of optimizing the query (using foreign keys rather than joins)
1203 /// <param name="propertyExpression">The original property expression that specifies the member and instance</param>
1204 /// <param name="rewritten">'Simplified' instance. If the member is a key and the instance is a navigation
1205 /// the rewritten expression's instance is a reference navigation rather than the full entity.</param>
1206 /// <returns><c>true</c> if the property expression was rewritten, in which case <paramref name="rewritten"/> will be non-null,
1207 /// otherwise <c>false</c>, in which case <paramref name="rewritten"/> will be null.</returns>
1208 private bool TryRewriteKeyPropertyAccess(DbPropertyExpression propertyExpression, out DbExpression rewritten)
1210 // if we're accessing a key member of a navigation, collapse the structured instance
1211 // to the key reference.
1212 if (propertyExpression.Instance.ExpressionKind == DbExpressionKind.Property &&
1213 Helper.IsEntityType(propertyExpression.Instance.ResultType.EdmType))
1215 EntityType instanceType = (EntityType)propertyExpression.Instance.ResultType.EdmType;
1216 DbPropertyExpression instanceExpression = (DbPropertyExpression)propertyExpression.Instance;
1217 if (Helper.IsNavigationProperty(instanceExpression.Property) &&
1218 instanceType.KeyMembers.Contains(propertyExpression.Property))
1220 // modify the property expression so that it merely retrieves the reference
1221 // not the entire entity
1222 NavigationProperty navigationProperty = (NavigationProperty)instanceExpression.Property;
1224 DbExpression navigationSource = instanceExpression.Instance.GetEntityRef();
1225 DbExpression navigationExpression = navigationSource.Navigate(navigationProperty.FromEndMember, navigationProperty.ToEndMember);
1226 rewritten = navigationExpression.GetRefKey();
1227 rewritten = rewritten.Property(propertyExpression.Property.Name);
1237 public override Node Visit(DbPropertyExpression e)
1239 // Only Properties, Relationship End and NavigationProperty members are supported.
1240 if (BuiltInTypeKind.EdmProperty != e.Property.BuiltInTypeKind &&
1241 BuiltInTypeKind.AssociationEndMember != e.Property.BuiltInTypeKind &&
1242 BuiltInTypeKind.NavigationProperty != e.Property.BuiltInTypeKind)
1244 throw EntityUtil.NotSupported();
1247 PlanCompiler.Assert(e.Instance != null, "Static properties are not supported");
1249 Node retNode = null;
1250 DbExpression rewritten;
1251 if (TryRewriteKeyPropertyAccess(e, out rewritten))
1253 retNode = this.VisitExpr(rewritten);
1257 Node instance = VisitExpr(e.Instance);
1260 // Retrieving a property from a new instance constructor can be
1261 // simplified to just the node that provides the corresponding property.
1262 // For example, Property(Row(A = x, B = y), 'A') => x
1263 // All structured types (including association types) are considered.
1265 if (e.Instance.ExpressionKind == DbExpressionKind.NewInstance &&
1266 Helper.IsStructuralType(e.Instance.ResultType.EdmType))
1268 // Retrieve the 'structural' members of the instance's type.
1269 // For Association types this should be only Association End members,
1270 // while for Complex, Entity or Row types is should be only Properties.
1271 System.Collections.IList propertyOrEndMembers = Helper.GetAllStructuralMembers(e.Instance.ResultType.EdmType);
1273 // Find the position of the member with the same name as the retrieved
1274 // member in the list of structural members.
1276 for (int idx = 0; idx < propertyOrEndMembers.Count; idx++)
1278 if (string.Equals(e.Property.Name, ((EdmMember)propertyOrEndMembers[idx]).Name, StringComparison.Ordinal))
1285 PlanCompiler.Assert(memberIdx > -1, "The specified property was not found");
1287 // If the member was found, return the corresponding argument value
1288 // to the new instance op.
1289 retNode = instance.Children[memberIdx];
1291 // Make sure the argument value has been "cast" to the return type
1292 // of the property, if necessary.
1293 retNode = BuildSoftCast(retNode, e.ResultType);
1297 Op op = _iqtCommand.CreatePropertyOp(e.Property);
1299 // Make sure that the input has been "cast" to the right type
1300 instance = BuildSoftCast(instance, e.Property.DeclaringType);
1301 retNode = _iqtCommand.CreateNode(op, instance);
1308 public override Node Visit(DbComparisonExpression e)
1310 Op op = _iqtCommand.CreateComparisonOp(s_opMap[e.ExpressionKind]);
1312 Node leftArg = VisitExprAsScalar(e.Left);
1313 Node rightArg = VisitExprAsScalar(e.Right);
1315 TypeUsage commonType = TypeHelpers.GetCommonTypeUsage(e.Left.ResultType, e.Right.ResultType);
1317 // Make sure that the inputs have been cast to the right types
1318 if (!Command.EqualTypes(e.Left.ResultType, e.Right.ResultType))
1320 leftArg = BuildSoftCast(leftArg, commonType);
1321 rightArg = BuildSoftCast(rightArg, commonType);
1324 if (TypeSemantics.IsEntityType(commonType) &&
1325 (e.ExpressionKind == DbExpressionKind.Equals || e.ExpressionKind == DbExpressionKind.NotEquals))
1327 // Entity (in)equality is implemented as ref (in)equality
1328 leftArg = BuildEntityRef(leftArg, commonType);
1329 rightArg = BuildEntityRef(rightArg, commonType);
1332 return _iqtCommand.CreateNode(op, leftArg, rightArg);
1335 public override Node Visit(DbLikeExpression e)
1337 return _iqtCommand.CreateNode(
1338 _iqtCommand.CreateLikeOp(),
1339 VisitExpr(e.Argument),
1340 VisitExpr(e.Pattern),
1345 private Node CreateLimitNode(Node inputNode, Node limitNode, bool withTies)
1348 // Limit(Skip(x)) - which becomes ConstrainedSortOp - and Limit(Sort(x)) are special cases
1350 Node retNode = null;
1351 if (OpType.ConstrainedSort == inputNode.Op.OpType &&
1352 OpType.Null == inputNode.Child2.Op.OpType)
1355 // The input was a DbSkipExpression which is now represented
1356 // as a ConstrainedSortOp with a NullOp Limit. The Limit from
1357 // this DbLimitExpression can be merged into the input ConstrainedSortOp
1358 // rather than creating a new ConstrainedSortOp.
1360 inputNode.Child2 = limitNode;
1362 // If this DbLimitExpression specifies WithTies, the input ConstrainedSortOp must be
1363 // updated to reflect this (DbSkipExpression always produces a ConstrainedSortOp with
1364 // WithTies equal to false).
1367 ((ConstrainedSortOp)inputNode.Op).WithTies = true;
1370 retNode = inputNode;
1372 else if (OpType.Sort == inputNode.Op.OpType)
1375 // This DbLimitExpression is applying a limit to a DbSortExpression.
1376 // The two expressions can be merged into a single ConstrainedSortOp
1377 // rather than creating a new ConstrainedSortOp over the input SortOp.
1379 // The new ConstrainedSortOp has the same SortKeys as the input SortOp.
1380 // The returned Node will have the following children:
1381 // - The input to the Sort
1382 // - A NullOp to indicate no Skip operation is specified
1383 // - The limit Node from the DbLimitExpression
1386 _iqtCommand.CreateNode(
1387 _iqtCommand.CreateConstrainedSortOp(((SortOp)inputNode.Op).Keys, withTies),
1389 _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)),
1396 // The input to the Limit is neither ConstrainedSortOp or SortOp.
1397 // A new ConstrainedSortOp must be created with an empty list of keys
1398 // and the following children:
1399 // - The input to the DbLimitExpression
1400 // - a NullOp to indicate that no Skip operation is specified
1401 // - The limit Node from the DbLimitExpression
1404 _iqtCommand.CreateNode(
1405 _iqtCommand.CreateConstrainedSortOp(new List<SortKey>(), withTies),
1407 _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType)),
1415 public override Node Visit(DbLimitExpression expression)
1418 // Visit the Argument and retrieve its Var
1420 Node inputNode = EnsureRelOp(VisitExpr(expression.Argument));
1421 Var inputVar = _varMap[inputNode];
1424 // Visit the Limit ensuring that it is a scalar
1426 Node limitNode = VisitExprAsScalar(expression.Limit);
1429 if (OpType.Project == inputNode.Op.OpType
1430 && (!AppSettings.SimplifyLimitOperations
1431 || (OpType.Sort == inputNode.Child0.Op.OpType
1432 || OpType.ConstrainedSort == inputNode.Child0.Op.OpType)))
1435 // If the input to the DbLimitExpression is a projection, then apply the Limit operation to the
1436 // input to the ProjectOp instead. This allows Limit(Project(Skip(x))) and Limit(Project(Sort(x)))
1437 // to be treated in the same way as Limit(Skip(x)) and Limit(Sort(x)).
1438 // Note that even if the input to the projection is not a ConstrainedSortOp or SortOp, the
1439 // Limit operation is still pushed under the Project when the SimplifyLimitOperations AppSetting
1440 // is set to false. SimplifyLimitOperations is false by default.
1442 inputNode.Child0 = CreateLimitNode(inputNode.Child0, limitNode, expression.WithTies);
1443 retNode = inputNode;
1448 // Otherwise, apply the Limit operation directly to the input.
1450 retNode = CreateLimitNode(inputNode, limitNode, expression.WithTies);
1454 // The output Var of the resulting Node is the same as the output Var of its input Node.
1455 // If the input node is being returned (either because the Limit was pushed under a Project
1456 // or because the input was a ConstrainedSortOp that was simply updated with the Limit value)
1457 // then the Node -> Var map does not need to be updated.
1459 if(!object.ReferenceEquals(retNode, inputNode))
1461 _varMap[retNode] = inputVar;
1467 public override Node Visit(DbIsNullExpression e)
1469 // SQLBUDT #484294: We need to recognize and simplify IsNull - IsNull and IsNull - Not - IsNull
1470 // This is the latest point where such patterns can be easily recognized.
1471 // After this the input predicate would get translated into a case statement.
1472 bool isAlwaysFalse = false; //true if IsNull - IsNull and IsNull - Not - IsNull is recognized
1474 if (e.Argument.ExpressionKind == DbExpressionKind.IsNull)
1476 isAlwaysFalse = true;
1478 else if (e.Argument.ExpressionKind == DbExpressionKind.Not)
1480 DbNotExpression notExpression = (DbNotExpression)e.Argument;
1481 if (notExpression.Argument.ExpressionKind == DbExpressionKind.IsNull)
1483 isAlwaysFalse = true;
1487 Op op = _iqtCommand.CreateConditionalOp(OpType.IsNull);
1489 //If we have recognized that the result is always false, return IsNull(true), to still have predicate as output.
1490 //This gets further simplified by transformation rules.
1493 return _iqtCommand.CreateNode(op, _iqtCommand.CreateNode(_iqtCommand.CreateInternalConstantOp(_iqtCommand.BooleanType, true)));
1496 Node argNode = VisitExprAsScalar(e.Argument);
1497 if (TypeSemantics.IsEntityType(e.Argument.ResultType))
1499 argNode = BuildEntityRef(argNode, e.Argument.ResultType);
1502 return _iqtCommand.CreateNode(op, argNode);
1505 public override Node Visit(DbArithmeticExpression e)
1507 Op op = _iqtCommand.CreateArithmeticOp(s_opMap[e.ExpressionKind], e.ResultType);
1508 // Make sure that the inputs have been "cast" to the result type
1509 // Assumption: The input type must be the same as the result type. Is this always true?
1510 List<Node> children = new List<Node>();
1511 foreach (DbExpression arg in e.Arguments)
1513 Node child = VisitExprAsScalar(arg);
1514 children.Add(BuildSoftCast(child, e.ResultType));
1516 return _iqtCommand.CreateNode(op, children);
1519 public override Node Visit(DbAndExpression e)
1521 Op op = _iqtCommand.CreateConditionalOp(OpType.And);
1522 return VisitBinary(e, op, VisitExprAsPredicate);
1525 public override Node Visit(DbOrExpression e)
1527 Op op = _iqtCommand.CreateConditionalOp(OpType.Or);
1528 return VisitBinary(e, op, VisitExprAsPredicate);
1531 public override Node Visit(DbNotExpression e)
1533 Op op = _iqtCommand.CreateConditionalOp(OpType.Not);
1534 return VisitUnary(e, op, VisitExprAsPredicate);
1537 public override Node Visit(DbDistinctExpression e)
1539 Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument));
1540 Var inputVar = _varMap[inputSetNode];
1541 Op distinctOp = _iqtCommand.CreateDistinctOp(inputVar);
1542 Node distinctNode = _iqtCommand.CreateNode(distinctOp, inputSetNode);
1543 _varMap[distinctNode] = inputVar;
1544 return distinctNode;
1547 public override Node Visit(DbElementExpression e)
1549 Op elementOp = _iqtCommand.CreateElementOp(e.ResultType);
1550 Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument));
1552 // Add a soft cast if needed
1553 inputSetNode = BuildSoftCast(inputSetNode, TypeHelpers.CreateCollectionTypeUsage(e.ResultType));
1555 Var inputVar = _varMap[inputSetNode];
1558 // Add a singleRowOp enforcer, as we are not guaranteed that the input
1559 // collection produces at most one row
1561 inputSetNode = _iqtCommand.CreateNode(_iqtCommand.CreateSingleRowOp(), inputSetNode);
1562 _varMap[inputSetNode] = inputVar;
1564 // add a fake projectNode
1565 inputSetNode = CapWithProject(inputSetNode);
1566 return _iqtCommand.CreateNode(elementOp, inputSetNode);
1569 public override Node Visit(DbIsEmptyExpression e)
1572 // IsEmpty(input set) --> Not(Exists(input set))
1574 Op existsOp = _iqtCommand.CreateExistsOp();
1575 Node inputSetNode = EnsureRelOp(VisitExpr(e.Argument));
1577 return _iqtCommand.CreateNode(
1578 _iqtCommand.CreateConditionalOp(OpType.Not),
1579 _iqtCommand.CreateNode(existsOp, inputSetNode)
1584 /// Encapsulates the logic required to convert a SetOp (Except, Intersect, UnionAll) expression
1585 /// into an IQT Node/Op pair.
1587 /// <param name="expression">The DbExceptExpression, DbIntersectExpression or DbUnionAllExpression to convert, as an instance of DbBinaryExpression</param>
1588 /// <returns>A new IQT Node that references the ExceptOp, IntersectOp or UnionAllOp created based on the expression</returns>
1589 private Node VisitSetOpExpression(DbBinaryExpression expression)
1591 PlanCompiler.Assert(DbExpressionKind.Except == expression.ExpressionKind ||
1592 DbExpressionKind.Intersect == expression.ExpressionKind ||
1593 DbExpressionKind.UnionAll == expression.ExpressionKind,
1594 "Non-SetOp DbExpression used as argument to VisitSetOpExpression");
1596 PlanCompiler.Assert(TypeSemantics.IsCollectionType(expression.ResultType), "SetOp DbExpression does not have collection result type?");
1598 // Visit the left and right collection arguments
1599 Node leftNode = EnsureRelOp(VisitExpr(expression.Left));
1600 Node rightNode = EnsureRelOp(VisitExpr(expression.Right));
1603 // Now the hard part. "Normalize" the left and right sides to
1604 // match the result type.
1606 leftNode = BuildSoftCast(leftNode, expression.ResultType);
1607 rightNode = BuildSoftCast(rightNode, expression.ResultType);
1609 // The SetOp produces a single Var of the same type as the element type of the expression's collection result type
1610 Var outputVar = _iqtCommand.CreateSetOpVar(TypeHelpers.GetEdmType<CollectionType>(expression.ResultType).TypeUsage);
1612 // Create VarMaps for the left and right arguments that map the output Var to the Var produced by the corresponding argument
1613 VarMap leftMap = new VarMap();
1614 leftMap.Add(outputVar, _varMap[leftNode]);
1616 VarMap rightMap = new VarMap();
1617 rightMap.Add(outputVar, _varMap[rightNode]);
1619 // Create a SetOp that corresponds to the operation specified by the expression's DbExpressionKind
1621 switch(expression.ExpressionKind)
1623 case DbExpressionKind.Except:
1624 setOp = _iqtCommand.CreateExceptOp(leftMap, rightMap);
1627 case DbExpressionKind.Intersect:
1628 setOp = _iqtCommand.CreateIntersectOp(leftMap, rightMap);
1631 case DbExpressionKind.UnionAll:
1632 setOp = _iqtCommand.CreateUnionAllOp(leftMap, rightMap);
1636 // Create a new Node that references the SetOp
1637 Node setOpNode = _iqtCommand.CreateNode(setOp, leftNode, rightNode);
1639 // Update the Node => Var map with an entry that maps the new Node to the output Var
1640 _varMap[setOpNode] = outputVar;
1642 // Return the newly created SetOp Node
1646 public override Node Visit(DbUnionAllExpression e)
1648 return VisitSetOpExpression(e);
1651 public override Node Visit(DbIntersectExpression e)
1653 return VisitSetOpExpression(e);
1656 public override Node Visit(DbExceptExpression e)
1658 return VisitSetOpExpression(e);
1661 public override Node Visit(DbTreatExpression e)
1664 if (_fakeTreats.Contains(e))
1666 op = _iqtCommand.CreateFakeTreatOp(e.ResultType);
1670 op = _iqtCommand.CreateTreatOp(e.ResultType);
1672 return VisitUnary(e, op, VisitExprAsScalar);
1675 public override Node Visit(DbIsOfExpression e)
1678 if (DbExpressionKind.IsOfOnly == e.ExpressionKind)
1680 op = _iqtCommand.CreateIsOfOnlyOp(e.OfType);
1684 op = _iqtCommand.CreateIsOfOp(e.OfType);
1686 return VisitUnary(e, op, VisitExprAsScalar);
1689 public override Node Visit(DbCastExpression e)
1691 Op op = _iqtCommand.CreateCastOp(e.ResultType);
1692 return VisitUnary(e, op, VisitExprAsScalar);
1695 public override Node Visit(DbCaseExpression e)
1697 List<Node> childNodes = new List<Node>();
1698 for (int idx = 0; idx < e.When.Count; idx++)
1700 childNodes.Add(VisitExprAsPredicate(e.When[idx]));
1701 // Make sure that each then-clause is the same type as the result
1702 childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Then[idx]), e.ResultType));
1705 // Make sure that the else-clause is the same type as the result
1706 childNodes.Add(BuildSoftCast(VisitExprAsScalar(e.Else), e.ResultType));
1707 return _iqtCommand.CreateNode(_iqtCommand.CreateCaseOp(e.ResultType), childNodes);
1711 /// Represents one or more type filters that should be AND'd together to produce an aggregate IsOf filter expression
1713 private class IsOfFilter
1716 /// The type that elements of the filtered input set must be to satisfy this IsOf filter
1718 private readonly TypeUsage requiredType;
1721 /// Indicates whether elements of the filtered input set may be of a subtype (IsOf) of the required type
1722 /// and still satisfy the IsOfFilter, or must be exactly of the required type (IsOfOnly) to do so.
1724 private readonly bool isExact;
1727 /// The next IsOfFilter in the AND chain.
1729 private IsOfFilter next;
1731 internal IsOfFilter(DbIsOfExpression template)
1733 this.requiredType = template.OfType;
1734 this.isExact = (template.ExpressionKind == DbExpressionKind.IsOfOnly);
1737 internal IsOfFilter(DbOfTypeExpression template)
1739 this.requiredType = template.OfType;
1740 this.isExact = (template.ExpressionKind == DbExpressionKind.OfTypeOnly);
1743 private IsOfFilter(TypeUsage required, bool exact)
1745 this.requiredType = required;
1746 this.isExact = exact;
1749 private IsOfFilter Merge(TypeUsage otherRequiredType, bool otherIsExact)
1751 // Can the two type filters be merged? In general, a more specific
1752 // type filter can replace a less specific type filter.
1754 bool typesEqual = this.requiredType.EdmEquals(otherRequiredType);
1756 // The simplest case - the filters are equivalent
1757 if (typesEqual && this.isExact == otherIsExact)
1762 // Next simplest - two IsOfOnly filters can never be merged if the types are different
1763 // (and if the types were equal the above condition would have been satisfied).
1765 else if (this.isExact && otherIsExact)
1767 result = new IsOfFilter(otherRequiredType, otherIsExact);
1771 // Two IsOf filters can potentially be adjusted - the more specific type filter should be kept, if present
1772 else if (!this.isExact && !otherIsExact)
1774 // At this point the types cannot be equal. If one filter specifies a type that is a subtype of the other,
1775 // then the subtype filter is the one that should remain
1776 if (otherRequiredType.IsSubtypeOf(this.requiredType))
1778 result = new IsOfFilter(otherRequiredType, false);
1779 result.next = this.next;
1781 else if (this.requiredType.IsSubtypeOf(otherRequiredType))
1787 // The types are not related and the filters cannot be merged
1788 // Note that this case may not be possible since IsOf and OfType
1789 // both require an argument with a compatible type to the IsOf type.
1790 result = new IsOfFilter(otherRequiredType, otherIsExact);
1795 // One filter is an IsOf filter while the other is an IsOfOnly filter
1798 // For IsOf(T) AND IsOfOnly(T), the IsOf filter can be dropped
1801 result = new IsOfFilter(otherRequiredType, true);
1802 result.next = this.next;
1806 // Decide which is the 'IsOfOnly' type and which is the 'IsOf' type
1807 TypeUsage isOfOnlyType = (this.isExact ? this.requiredType : otherRequiredType);
1808 TypeUsage isOfType = (this.isExact ? otherRequiredType : this.requiredType);
1810 // IsOf(Super) && IsOfOnly(Sub) => IsOfOnly(Sub)
1811 // In all other cases, both filters remain - even though the IsOfOnly(Super) and IsOf(Sub) is obviously a contradiction.
1813 if (isOfOnlyType.IsSubtypeOf(isOfType))
1815 if (object.ReferenceEquals(isOfOnlyType, this.requiredType) && this.isExact)
1821 result = new IsOfFilter(isOfOnlyType, true);
1822 result.next = this.next;
1827 result = new IsOfFilter(otherRequiredType, otherIsExact);
1836 internal IsOfFilter Merge(DbIsOfExpression other)
1838 return Merge(other.OfType, (other.ExpressionKind == DbExpressionKind.IsOfOnly));
1841 internal IsOfFilter Merge(DbOfTypeExpression other)
1843 return Merge(other.OfType, (other.ExpressionKind == DbExpressionKind.OfTypeOnly));
1846 internal IEnumerable<KeyValuePair<TypeUsage, bool>> ToEnumerable()
1848 IsOfFilter currentFilter = this;
1849 while (currentFilter != null)
1851 yield return new KeyValuePair<TypeUsage, bool>(currentFilter.requiredType, currentFilter.isExact);
1852 currentFilter = currentFilter.next;
1857 private DbFilterExpression CreateIsOfFilterExpression(DbExpression input, IsOfFilter typeFilter)
1859 // Create a filter expression based on the IsOf/IsOfOnly operations specified by typeFilter
1860 DbExpressionBinding resultBinding = input.Bind();
1861 List<DbExpression> predicates = new List<DbExpression>(
1862 typeFilter.ToEnumerable().Select(tf => tf.Value ? resultBinding.Variable.IsOfOnly(tf.Key) : resultBinding.Variable.IsOf(tf.Key)).ToList()
1864 DbExpression predicate = Helpers.BuildBalancedTreeInPlace(predicates, (left, right) => left.And(right));
1865 DbFilterExpression result = resultBinding.Filter(predicate);
1867 // Track the fact that this IsOfFilter was created by the ITreeGenerator itself and should
1868 // simply be converted to an ITree Node when it is encountered again by the visitor pass.
1869 _processedIsOfFilters.Add(result);
1873 private bool IsIsOfFilter(DbFilterExpression filter)
1875 if(filter.Predicate.ExpressionKind != DbExpressionKind.IsOf &&
1876 filter.Predicate.ExpressionKind != DbExpressionKind.IsOfOnly)
1881 DbExpression isOfArgument = ((DbIsOfExpression)filter.Predicate).Argument;
1882 return (isOfArgument.ExpressionKind == DbExpressionKind.VariableReference &&
1883 ((DbVariableReferenceExpression)isOfArgument).VariableName == filter.Input.VariableName);
1886 private DbExpression ApplyIsOfFilter(DbExpression current, IsOfFilter typeFilter)
1888 // An IsOf filter can be safely pushed down through the following expressions:
1891 // Filter - may be merged if the Filter is also an OfType filter
1892 // OfType - converted to Project(Filter(input, IsOf(T)), TreatAs(T)) and the Filter may be merged
1893 // Project - only for identity project
1903 DbExpression result;
1904 switch(current.ExpressionKind)
1906 case DbExpressionKind.Distinct:
1908 result = ApplyIsOfFilter(((DbDistinctExpression)current).Argument, typeFilter).Distinct();
1912 case DbExpressionKind.Filter:
1914 DbFilterExpression filter = (DbFilterExpression)current;
1915 if (IsIsOfFilter(filter))
1917 // If this is an IsOf filter, examine the interaction with the current filter we are trying to apply
1918 DbIsOfExpression isOfExp = (DbIsOfExpression)filter.Predicate;
1919 typeFilter = typeFilter.Merge(isOfExp);
1920 result = ApplyIsOfFilter(filter.Input.Expression, typeFilter);
1924 // Otherwise, push the current IsOf filter under this filter
1925 DbExpression rewritten = ApplyIsOfFilter(filter.Input.Expression, typeFilter);
1926 result = rewritten.BindAs(filter.Input.VariableName).Filter(filter.Predicate);
1931 case DbExpressionKind.OfType:
1932 case DbExpressionKind.OfTypeOnly:
1934 // Examine the interaction of this nested OfType filter with the OfType filter we are trying to apply
1935 // and construct an aggregated type filter (where possible)
1936 DbOfTypeExpression ofTypeExp = (DbOfTypeExpression)current;
1937 typeFilter = typeFilter.Merge(ofTypeExp);
1938 DbExpression rewrittenIsOf = ApplyIsOfFilter(ofTypeExp.Argument, typeFilter);
1939 DbExpressionBinding treatBinding = rewrittenIsOf.Bind();
1940 DbTreatExpression treatProjection = treatBinding.Variable.TreatAs(ofTypeExp.OfType);
1941 _fakeTreats.Add(treatProjection);
1942 result = treatBinding.Project(treatProjection);
1946 case DbExpressionKind.Project:
1948 DbProjectExpression project = (DbProjectExpression)current;
1949 if(project.Projection.ExpressionKind == DbExpressionKind.VariableReference &&
1950 ((DbVariableReferenceExpression)project.Projection).VariableName == project.Input.VariableName)
1952 // If this is an identity-project, remove it by visiting the input expression
1953 result = ApplyIsOfFilter(project.Input.Expression, typeFilter);
1957 // Otherwise, the projection is opaque to the IsOf rewrite
1958 result = CreateIsOfFilterExpression(current, typeFilter);
1963 case DbExpressionKind.Sort:
1965 // The IsOf filter is applied to the Sort input, then the sort keys are reapplied to create a new Sort expression.
1966 DbSortExpression sort = (DbSortExpression)current;
1967 DbExpression sortInput = ApplyIsOfFilter(sort.Input.Expression, typeFilter);
1968 result = sortInput.BindAs(sort.Input.VariableName).Sort(sort.SortOrder);
1974 // This is not a recognized case, so simply apply the type filter to the expression.
1975 result = CreateIsOfFilterExpression(current, typeFilter);
1983 /// Build the equivalent of an OfTypeExpression over the input (ie) produce the set of values from the
1984 /// input that are of the desired type (exactly of the desired type, if the "includeSubtypes" parameter is false).
1986 /// Further more, "update" the result element type to be the desired type.
1988 /// We accomplish this by first building a FilterOp with an IsOf (or an IsOfOnly) predicate for the desired
1989 /// type. We then build out a ProjectOp over the FilterOp, where we introduce a "Fake" TreatOp over the input
1990 /// element to cast it to the right type. The "Fake" TreatOp is only there for "compile-time" typing reasons,
1991 /// and will be ignored in the rest of the plan compiler
1993 // <param name="inputNode">the input collection</param>
1994 // <param name="inputVar">the single Var produced by the input collection</param>
1995 // <param name="desiredType">the desired element type </param>
1996 // <param name="includeSubtypes">do we include subtypes of the desired element type</param>
1997 // <param name="resultNode">the result subtree</param>
1998 // <param name="resultVar">the single Var produced by the result subtree</param>
1999 public override Node Visit(DbOfTypeExpression e)
2002 // The argument to OfType must be a collection
2004 PlanCompiler.Assert(TypeSemantics.IsCollectionType(e.Argument.ResultType), "Non-Collection Type Argument in DbOfTypeExpression");
2006 DbExpression rewrittenIsOfFilter = ApplyIsOfFilter(e.Argument, new IsOfFilter(e));
2009 // Visit the collection argument and ensure that it is a RelOp suitable for subsequent use in the Filter/Project used to convert OfType.
2011 Node inputNode = EnsureRelOp(VisitExpr(rewrittenIsOfFilter));
2014 // Retrieve the Var produced by the RelOp input.
2016 Var inputVar = _varMap[inputNode];
2019 // Build the Treat part of the OfType expression tree - note that this is a 'fake'
2020 // Treat because the underlying IsOf filter makes it unnecessary (as far as the
2021 // plan compiler is concerned).
2024 Node resultNode = _iqtCommand.BuildFakeTreatProject(inputNode, inputVar, e.OfType, out resultVar);
2027 // Add the node-var mapping, and return
2029 _varMap[resultNode] = resultVar;
2033 public override Node Visit(DbNewInstanceExpression e)
2035 Op newInstOp = null;
2036 List<Node> relPropertyExprs = null;
2037 if (TypeSemantics.IsCollectionType(e.ResultType))
2039 newInstOp = _iqtCommand.CreateNewMultisetOp(e.ResultType);
2041 else if (TypeSemantics.IsRowType(e.ResultType))
2043 newInstOp = _iqtCommand.CreateNewRecordOp(e.ResultType);
2045 else if (TypeSemantics.IsEntityType(e.ResultType))
2047 List<RelProperty> relPropertyList = new List<RelProperty>();
2048 relPropertyExprs = new List<Node>();
2049 if (e.HasRelatedEntityReferences)
2051 foreach (DbRelatedEntityRef targetRef in e.RelatedEntityReferences)
2053 RelProperty relProperty = new RelProperty((RelationshipType)targetRef.TargetEnd.DeclaringType, targetRef.SourceEnd, targetRef.TargetEnd);
2054 relPropertyList.Add(relProperty);
2055 Node relPropertyNode = VisitExprAsScalar(targetRef.TargetEntityReference);
2056 relPropertyExprs.Add(relPropertyNode);
2059 newInstOp = _iqtCommand.CreateNewEntityOp(e.ResultType, relPropertyList);
2063 newInstOp = _iqtCommand.CreateNewInstanceOp(e.ResultType);
2067 // Build up the list of arguments. Make sure that they match
2068 // the expected types (and add "soft" casts, if needed)
2070 List<Node> newArgs = new List<Node>();
2071 if (TypeSemantics.IsStructuralType(e.ResultType))
2073 StructuralType resultType = TypeHelpers.GetEdmType<StructuralType>(e.ResultType);
2075 foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(resultType))
2077 Node newArg = BuildSoftCast(VisitExprAsScalar(e.Arguments[i]), Helper.GetModelTypeUsage(m));
2078 newArgs.Add(newArg);
2084 CollectionType resultType = TypeHelpers.GetEdmType<CollectionType>(e.ResultType);
2085 TypeUsage elementTypeUsage = resultType.TypeUsage;
2086 foreach (DbExpression arg in e.Arguments)
2088 Node newArg = BuildSoftCast(VisitExprAsScalar(arg), elementTypeUsage);
2089 newArgs.Add(newArg);
2093 if (relPropertyExprs != null)
2095 newArgs.AddRange(relPropertyExprs);
2097 Node node = _iqtCommand.CreateNode(newInstOp, newArgs);
2102 public override Node Visit(DbRefExpression e)
2104 // SQLBUDT #502617: Creating a collection of refs throws an Assert
2105 // A SoftCastOp may be required if the argument to the RefExpression is only promotable
2106 // to the row type produced from the key properties of the referenced Entity type. Since
2107 // this row type is not actually represented anywhere in the tree it must be built here in
2108 // order to determine whether or not the SoftCastOp should be applied.
2110 Op op = _iqtCommand.CreateRefOp(e.EntitySet, e.ResultType);
2111 Node newArg = BuildSoftCast(VisitExprAsScalar(e.Argument), TypeHelpers.CreateKeyRowType(e.EntitySet.ElementType));
2112 return _iqtCommand.CreateNode(op, newArg);
2115 public override Node Visit(DbRelationshipNavigationExpression e)
2117 RelProperty relProperty = new RelProperty(e.Relationship, e.NavigateFrom, e.NavigateTo);
2118 Op op = _iqtCommand.CreateNavigateOp(e.ResultType, relProperty);
2119 Node arg = VisitExprAsScalar(e.NavigationSource);
2120 return _iqtCommand.CreateNode(op, arg);
2123 public override Node Visit(DbDerefExpression e)
2125 Op op = _iqtCommand.CreateDerefOp(e.ResultType);
2126 return VisitUnary(e, op, VisitExprAsScalar);
2129 public override Node Visit(DbRefKeyExpression e)
2131 Op op = _iqtCommand.CreateGetRefKeyOp(e.ResultType);
2132 return VisitUnary(e, op, VisitExprAsScalar);
2135 public override Node Visit(DbEntityRefExpression e)
2137 Op op = _iqtCommand.CreateGetEntityRefOp(e.ResultType);
2138 return VisitUnary(e, op, VisitExprAsScalar);
2141 public override Node Visit(DbScanExpression e)
2143 // Create a new table definition
2144 TableMD tableMetadata = Command.CreateTableDefinition(e.Target);
2146 // Create a scan table operator
2147 ScanTableOp op = _iqtCommand.CreateScanTableOp(tableMetadata);
2149 // Map the ScanTableOp to the ColumnVar of the Table's single column of the Extent's element type
2150 Node node = _iqtCommand.CreateNode(op);
2151 Var singleColumn = op.Table.Columns[0];
2152 _varMap[node] = singleColumn;
2157 public override Node Visit(DbFilterExpression e)
2159 if (!IsIsOfFilter(e) || _processedIsOfFilters.Contains(e))
2162 // Visit the Predicate with the Input binding's variable in scope
2164 Node inputSetNode = EnterExpressionBinding(e.Input);
2165 Node predicateNode = VisitExprAsPredicate(e.Predicate);
2166 ExitExpressionBinding();
2168 Op filtOp = _iqtCommand.CreateFilterOp();
2170 // Update the Node --> Var mapping. Filter maps to the same Var as its input.
2171 Node filtNode = _iqtCommand.CreateNode(filtOp, inputSetNode, predicateNode);
2172 _varMap[filtNode] = _varMap[inputSetNode];
2178 DbIsOfExpression isOfPredicate = (DbIsOfExpression)e.Predicate;
2179 DbExpression processed = ApplyIsOfFilter(e.Input.Expression, new IsOfFilter(isOfPredicate));
2180 return this.VisitExpr(processed);
2184 public override Node Visit(DbProjectExpression e)
2186 // check if this is the discriminated projection for a query mapping view
2187 if (e == this._discriminatedViewTopProject)
2189 return GenerateDiscriminatedProject(e);
2193 return GenerateStandardProject(e);
2197 private Node GenerateDiscriminatedProject(DbProjectExpression e)
2199 PlanCompiler.Assert(null != _discriminatedViewTopProject, "if a project matches the pattern, there must be a corresponding discriminator map");
2201 // convert the input to the top level projection
2202 Node source = EnterExpressionBinding(e.Input);
2204 List<RelProperty> relPropertyList = new List<RelProperty>();
2205 List<Node> relPropertyExprs = new List<Node>();
2206 foreach (KeyValuePair<RelProperty, DbExpression> kv in _discriminatorMap.RelPropertyMap)
2208 relPropertyList.Add(kv.Key);
2209 relPropertyExprs.Add(VisitExprAsScalar(kv.Value));
2212 // construct a DiscriminatedNewInstanceOp
2213 DiscriminatedNewEntityOp newInstOp = _iqtCommand.CreateDiscriminatedNewEntityOp(e.Projection.ResultType,
2214 new ExplicitDiscriminatorMap(_discriminatorMap), _discriminatorMap.EntitySet, relPropertyList);
2216 // args include all projected properties and discriminator and the relProperties
2217 List<Node> newArgs = new List<Node>(_discriminatorMap.PropertyMap.Count + 1);
2218 newArgs.Add(CreateNewInstanceArgument(_discriminatorMap.Discriminator.Property, _discriminatorMap.Discriminator));
2219 foreach (var propertyMap in _discriminatorMap.PropertyMap)
2221 DbExpression value = propertyMap.Value;
2222 EdmProperty property = propertyMap.Key;
2223 Node newArg = CreateNewInstanceArgument(property, value);
2224 newArgs.Add(newArg);
2226 newArgs.AddRange(relPropertyExprs);
2228 Node newInstNode = _iqtCommand.CreateNode(newInstOp, newArgs);
2229 ExitExpressionBinding();
2232 Node varDefListNode = _iqtCommand.CreateVarDefListNode(newInstNode, out sourceVar);
2234 ProjectOp projOp = _iqtCommand.CreateProjectOp(sourceVar);
2235 Node projNode = _iqtCommand.CreateNode(projOp, source, varDefListNode);
2236 _varMap[projNode] = sourceVar;
2241 private Node CreateNewInstanceArgument(EdmMember property, DbExpression value)
2243 Node newArg = BuildSoftCast(VisitExprAsScalar(value), Helper.GetModelTypeUsage(property));
2247 private Node GenerateStandardProject(DbProjectExpression e)
2249 Node projectedSetNode = EnterExpressionBinding(e.Input);
2250 Node projectionNode = VisitExprAsScalar(e.Projection);
2251 ExitExpressionBinding();
2254 Node varDefListNode = _iqtCommand.CreateVarDefListNode(projectionNode, out projectionVar);
2256 ProjectOp projOp = _iqtCommand.CreateProjectOp(projectionVar);
2257 Node projNode = _iqtCommand.CreateNode(projOp, projectedSetNode, varDefListNode);
2258 _varMap[projNode] = projectionVar;
2263 public override Node Visit(DbCrossJoinExpression e)
2265 return VisitJoin(e, e.Inputs, null);
2268 public override Node Visit(DbJoinExpression e)
2270 List<DbExpressionBinding> inputs = new List<DbExpressionBinding>();
2272 inputs.Add(e.Right);
2274 return VisitJoin(e, inputs, e.JoinCondition);
2277 private Node VisitJoin(DbExpression e, IList<DbExpressionBinding> inputs, DbExpression joinCond)
2280 // Assert that the JoinType is covered. If JoinTypes are added to CQT then the
2281 // switch statement that constructs the JoinOp must be updated, along with this assert.
2283 PlanCompiler.Assert(DbExpressionKind.CrossJoin == e.ExpressionKind ||
2284 DbExpressionKind.InnerJoin == e.ExpressionKind ||
2285 DbExpressionKind.LeftOuterJoin == e.ExpressionKind ||
2286 DbExpressionKind.FullOuterJoin == e.ExpressionKind,
2287 "Unrecognized JoinType specified in DbJoinExpression");
2291 // Assert that the DbJoinExpression is producing a collection result with a record element type.
2292 // !!! IsCollectionOfRecord() is defined only in DEBUG !!!
2293 PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbJoinExpression");
2297 // Visit Join inputs, track their nodes and vars.
2299 List<Node> inputNodes = new List<Node>();
2300 List<Var> inputVars = new List<Var>();
2301 for(int idx = 0; idx < inputs.Count; idx++)
2304 Node inputNode = VisitBoundExpression(inputs[idx].Expression, out boundVar);
2305 inputNodes.Add(inputNode);
2306 inputVars.Add(boundVar);
2310 // Bring the variables for the Join inputs into scope.
2312 for (int scopeCount = 0; scopeCount < inputNodes.Count; scopeCount++)
2314 PushBindingScope(inputVars[scopeCount], inputs[scopeCount].VariableName);
2318 // Visit join condition, if present.
2320 Node joinCondNode = VisitExprAsPredicate(joinCond);
2323 // Remove the input variables from scope after visiting the Join condition.
2325 for (int scopeCount = 0; scopeCount < inputNodes.Count; scopeCount++)
2327 ExitExpressionBinding();
2331 // Create an appropriate JoinOp based on the JoinType specified in the DbJoinExpression.
2333 JoinBaseOp joinOp = null;
2334 switch (e.ExpressionKind)
2336 case DbExpressionKind.CrossJoin:
2338 joinOp = _iqtCommand.CreateCrossJoinOp();
2342 case DbExpressionKind.InnerJoin:
2344 joinOp = _iqtCommand.CreateInnerJoinOp();
2348 case DbExpressionKind.LeftOuterJoin:
2350 joinOp = _iqtCommand.CreateLeftOuterJoinOp();
2354 case DbExpressionKind.FullOuterJoin:
2356 joinOp = _iqtCommand.CreateFullOuterJoinOp();
2362 // 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.
2364 PlanCompiler.Assert(joinOp != null, "Unrecognized JoinOp specified in DbJoinExpression, no JoinOp was produced");
2367 // If the Join condition was present then add its converted form to the list of child nodes for the new Join node.
2369 if (e.ExpressionKind != DbExpressionKind.CrossJoin)
2371 PlanCompiler.Assert(joinCondNode != null, "Non CrossJoinOps must specify a join condition");
2372 inputNodes.Add(joinCondNode);
2376 // Create and return a new projection that unifies the multiple vars produced by the Join columns into a single record constructor.
2378 return ProjectNewRecord(
2379 _iqtCommand.CreateNode(joinOp, inputNodes),
2380 ExtractElementRowType(e.ResultType),
2385 public override Node Visit(DbApplyExpression e)
2389 // Assert that the DbJoinExpression is producing a collection result with a record element type.
2390 // !!! IsCollectionOfRecord() is defined only in DEBUG !!!
2391 PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "Invalid Type returned by DbApplyExpression");
2395 // Bring the Input set's variable into scope
2397 Node inputNode = EnterExpressionBinding(e.Input);
2400 // Visit the Apply expression with the Input's variable in scope.
2401 // This is done via EnterExpressionBinding, which is allowable only because
2402 // it will only bring the Apply variable into scope *after* visiting the Apply expression
2403 // (which means that the Apply expression cannot validly reference its own binding variable)
2405 Node applyNode = EnterExpressionBinding(e.Apply);
2408 // Remove the Apply and Input variables from scope
2410 ExitExpressionBinding(); // for the Apply
2411 ExitExpressionBinding(); // for the Input
2414 // The ApplyType should only be either CrossApply or OuterApply.
2416 PlanCompiler.Assert(DbExpressionKind.CrossApply == e.ExpressionKind || DbExpressionKind.OuterApply == e.ExpressionKind, "Unrecognized DbExpressionKind specified in DbApplyExpression");
2419 // Create a new Node with the correct ApplyOp as its Op and the input and apply nodes as its child nodes.
2421 ApplyBaseOp applyOp = null;
2422 if (DbExpressionKind.CrossApply == e.ExpressionKind)
2424 applyOp = _iqtCommand.CreateCrossApplyOp();
2428 applyOp = _iqtCommand.CreateOuterApplyOp();
2431 Node retNode = _iqtCommand.CreateNode(applyOp, inputNode, applyNode);
2434 // Create and return a new projection that unifies the vars produced by the input and apply columns into a single record constructor.
2436 return ProjectNewRecord(
2438 ExtractElementRowType(e.ResultType),
2439 new Var[] { _varMap[inputNode], _varMap[applyNode] }
2443 public override Node Visit(DbGroupByExpression e)
2446 // !!! IsCollectionOfRecord() is defined only in DEBUG !!!
2447 PlanCompiler.Assert(IsCollectionOfRecord(e.ResultType), "DbGroupByExpression has invalid result Type (not record collection)");
2451 // Process the input and the keys
2453 VarVec keyVarSet = _iqtCommand.CreateVarVec();
2454 VarVec outputVarSet = _iqtCommand.CreateVarVec();
2456 List<Node> keyVarDefNodes;
2457 ExpressionBindingScope scope;
2458 ExtractKeys(e, keyVarSet, outputVarSet, out inputNode, out keyVarDefNodes, out scope);
2460 // Get the index of the group aggregate if any
2461 int groupAggregateIndex = -1;
2462 for (int i = 0; i < e.Aggregates.Count; i++)
2464 if (e.Aggregates[i].GetType() == typeof(DbGroupAggregate))
2466 groupAggregateIndex = i;
2472 //If there is a group aggregate, create a copy of the input
2474 Node copyOfInput = null;
2475 List<Node> copyOfKeyVarDefNodes = null;
2476 VarVec copyOutputVarSet = _iqtCommand.CreateVarVec();
2477 VarVec copyKeyVarSet = _iqtCommand.CreateVarVec();
2478 if (groupAggregateIndex >= 0)
2480 ExpressionBindingScope copyOfScope; //not needed
2481 ExtractKeys(e, copyKeyVarSet, copyOutputVarSet, out copyOfInput, out copyOfKeyVarDefNodes, out copyOfScope);
2485 // Bring the Input variable from the DbGroupByExpression into scope
2487 scope = new ExpressionBindingScope(_iqtCommand, e.Input.GroupVariableName, scope.ScopeVar);
2488 _varScopes.Push(scope);
2491 // Process the Aggregates: For each DbAggregate, produce the corresponding IQT conversion depending on whether the DbAggregate is a DbFunctionAggregate or DbGroupAggregate.
2492 // 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.
2493 // 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).
2495 List<Node> aggVarDefNodes = new List<Node>();
2496 Node groupAggDefNode = null;
2497 for(int idx = 0; idx < e.Aggregates.Count; idx++)
2499 DbAggregate agg = e.Aggregates[idx];
2503 // Produce the converted form of the Arguments to the aggregate
2505 IList<Node> argNodes = VisitExprAsScalar(agg.Arguments);
2508 // Handle if it is DbFunctionAggregate
2510 if (idx != groupAggregateIndex)
2512 DbFunctionAggregate funcAgg = agg as DbFunctionAggregate;
2513 PlanCompiler.Assert(funcAgg != null, "Unrecognized DbAggregate used in DbGroupByExpression");
2515 aggVarDefNodes.Add(ProcessFunctionAggregate(funcAgg, argNodes, out aggVar));
2518 // Handle if it is DbGroupAggregate
2522 groupAggDefNode = ProcessGroupAggregate(keyVarDefNodes, copyOfInput, copyOfKeyVarDefNodes, copyKeyVarSet, e.Input.Expression.ResultType, out aggVar);
2525 outputVarSet.Set(aggVar);
2529 // The Aggregates have now been processed, so remove the group variable from scope.
2531 ExitGroupExpressionBinding();
2534 // Construct the GroupBy. This consists of a GroupByOp (or GroupByIntoOp) with 3 (or 4) children:
2535 // 1. The Node produced from the Input set
2536 // 2. A VarDefListOp Node that uses the Key VarDefs to define the Key Vars (created above)
2537 // 3. A VarDefListOp Node that uses the Aggregate VarDefs to define the Aggregate Vars (created above)
2538 // 4. For a GroupByIntoOp a verDefLIstOp Node with a single var def node that defines the group aggregate
2540 List<Node> groupByChildren = new List<Node>();
2541 groupByChildren.Add(inputNode); // The Node produced from the Input set
2542 groupByChildren.Add( // The Key VarDefs
2543 _iqtCommand.CreateNode(
2544 _iqtCommand.CreateVarDefListOp(),
2547 groupByChildren.Add( // The Aggregate VarDefs
2548 _iqtCommand.CreateNode(
2549 _iqtCommand.CreateVarDefListOp(),
2554 if (groupAggregateIndex >= 0)
2556 groupByChildren.Add( // The GroupAggregate VarDef
2557 _iqtCommand.CreateNode(
2558 _iqtCommand.CreateVarDefListOp(),
2561 op = _iqtCommand.CreateGroupByIntoOp(keyVarSet, this._iqtCommand.CreateVarVec(_varMap[inputNode]), outputVarSet);
2565 op = _iqtCommand.CreateGroupByOp(keyVarSet, outputVarSet);
2568 Node groupByNode = _iqtCommand.CreateNode(
2569 op, groupByChildren);
2572 // Create and return a projection that unifies the multiple output vars of the GroupBy into a single record constructor.
2574 return ProjectNewRecord(
2576 ExtractElementRowType(e.ResultType),
2577 outputVarSet //todo: it is not correct to pass a varvec where an ordered list is expected
2581 private void ExtractKeys(DbGroupByExpression e, VarVec keyVarSet, VarVec outputVarSet, out Node inputNode, out List<Node> keyVarDefNodes, out ExpressionBindingScope scope)
2583 inputNode = EnterGroupExpressionBinding(e.Input);
2586 // Process the Keys: For each Key, produce the corresponding IQT conversion.
2587 // The converted Node is then used as the child node of a VarDefOp Node that is
2588 // added to a list of Key VarDefs. The Var defined by the converted Key expression
2589 // is added to both the overall list of Vars produced by the GroupBy and the list of Key vars produced by the GroupBy.
2591 keyVarDefNodes = new List<Node>();
2592 for (int idx = 0; idx < e.Keys.Count; idx++)
2594 DbExpression keyExpr = e.Keys[idx];
2596 Node keyNode = VisitExprAsScalar(keyExpr);
2597 ScalarOp keyOp = keyNode.Op as ScalarOp;
2600 // In a valid CQT, each group key expressions will result in a ScalarOp since they
2601 // must be of an equality comparable type.
2603 PlanCompiler.Assert(keyOp != null, "GroupBy Key is not a ScalarOp");
2606 // 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.
2610 // Create a VarDefOp that uses the converted form of the Key to define the ComputedVar and add it to the list of Key VarDefs.
2612 keyVarDefNodes.Add(_iqtCommand.CreateVarDefNode(keyNode, out keyVar));
2613 outputVarSet.Set(keyVar);
2614 keyVarSet.Set(keyVar);
2618 // Before the Aggregates are processed, the Input variable must be taken out of scope and the 'group' variable introduced into scope in its place
2619 // This is done as follows:
2620 // 1. Pop the current ExpressionBindingScope from the stack
2621 // 2. Create a new ExpressionBindingScope using the same Var but the name of the 'group' variable from the DbGroupByExpression's DbGroupExpressionBinding
2622 // 3. Push this new scope onto the variable scope stack.
2624 scope = ExitExpressionBinding();
2627 private Node ProcessFunctionAggregate(DbFunctionAggregate funcAgg, IList<Node> argNodes, out Var aggVar)
2629 Node aggNode = _iqtCommand.CreateNode(
2630 _iqtCommand.CreateAggregateOp(funcAgg.Function, funcAgg.Distinct),
2635 // Create a VarDefOp that uses the converted form of the DbAggregate to define the ComputedVar
2637 return _iqtCommand.CreateVarDefNode(aggNode, out aggVar);
2641 /// Translation for GroupAggregate
2643 /// Create the translation as :
2649 /// GroupNodeDefinition
2651 /// Here, GroupNodeDefinition is:
2652 /// 1. If there are no keys: copyOfInput;
2653 /// 2. If there are keys:
2655 /// Filter (keyDef1 = copyOfKeyDef1 or keyDef1 is null and copyOfKeyDef1 is null) and ... and (keyDefn = copyOfKeyDefn or keyDefn is null and copyOfKeyDefn is null)
2657 /// Project (copyOfInput, copyOfKeyDef1, copyOfKeyDef1, ... copyOfKeyDefn)
2662 /// <param name="keyVarDefNodes"></param>
2663 /// <param name="copyOfInput"></param>
2664 /// <param name="copyOfkeyVarDefNodes"></param>
2665 /// <param name="copyKeyVarSet"></param>
2666 /// <param name="inputResultType"></param>
2667 /// <param name="groupAggVar"></param>
2668 /// <returns></returns>
2669 private Node ProcessGroupAggregate(List<Node> keyVarDefNodes, Node copyOfInput, List<Node> copyOfkeyVarDefNodes, VarVec copyKeyVarSet, TypeUsage inputResultType, out Var groupAggVar)
2671 Var inputVar = this._varMap[copyOfInput];
2672 Node groupDefNode = copyOfInput;
2674 if (keyVarDefNodes.Count > 0)
2676 VarVec projectOutpus = _iqtCommand.CreateVarVec();
2677 projectOutpus.Set(inputVar);
2678 projectOutpus.Or(copyKeyVarSet);
2680 Node projectNodeWithKeys = _iqtCommand.CreateNode(
2681 _iqtCommand.CreateProjectOp(projectOutpus),
2682 groupDefNode, //the input
2683 _iqtCommand.CreateNode( //the key var defs
2684 _iqtCommand.CreateVarDefListOp(),
2685 copyOfkeyVarDefNodes
2688 List<Node> flattentedKeys = new List<Node>();
2689 List<Node> copyFlattenedKeys = new List<Node>();
2691 for (int i = 0; i < keyVarDefNodes.Count; i++)
2693 Node keyVarDef = keyVarDefNodes[i];
2694 Node copyOfKeyVarDef = copyOfkeyVarDefNodes[i];
2696 Var keyVar = ((VarDefOp)keyVarDef.Op).Var;
2697 Var copyOfKeyVar = ((VarDefOp)copyOfKeyVarDef.Op).Var;
2700 // The keys of type row need to be flattened, because grouping by a row means grouping by its individual
2701 // members and thus we have to check the individual members whether they are null.
2702 // IsNull(x) where x is a row type does not mean whether the individual properties of x are null,
2703 // but rather whether the entire row is null.
2705 FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(keyVar)), flattentedKeys);
2706 FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreateVarRefOp(copyOfKeyVar)), copyFlattenedKeys);
2709 PlanCompiler.Assert(flattentedKeys.Count == copyFlattenedKeys.Count, "The flattened keys lists should have the same nubmer of elements");
2711 Node filterPredicateNode = null;
2713 for(int j = 0; j< flattentedKeys.Count; j++)
2715 Node keyNode = flattentedKeys[j];
2716 Node copyKeyNode = copyFlattenedKeys[j];
2719 // Create the predicate for a single key
2720 // keyVar = copyOfKeyVar or keyVar is null and copyOfKeyVar is null
2722 Node predicate = _iqtCommand.CreateNode(
2723 _iqtCommand.CreateConditionalOp(OpType.Or),
2724 _iqtCommand.CreateNode(
2725 _iqtCommand.CreateComparisonOp(OpType.EQ), keyNode, copyKeyNode),
2726 _iqtCommand.CreateNode(
2727 _iqtCommand.CreateConditionalOp(OpType.And),
2728 _iqtCommand.CreateNode(
2729 _iqtCommand.CreateConditionalOp(OpType.IsNull),
2730 OpCopier.Copy(_iqtCommand, keyNode)),
2731 _iqtCommand.CreateNode(
2732 _iqtCommand.CreateConditionalOp(OpType.IsNull),
2733 OpCopier.Copy(_iqtCommand, copyKeyNode))));
2735 if (filterPredicateNode == null)
2737 filterPredicateNode = predicate;
2741 filterPredicateNode = _iqtCommand.CreateNode(
2742 _iqtCommand.CreateConditionalOp(OpType.And),
2743 filterPredicateNode, predicate);
2747 Node filterNode = _iqtCommand.CreateNode(
2748 _iqtCommand.CreateFilterOp(), projectNodeWithKeys, filterPredicateNode);
2750 groupDefNode = filterNode;
2753 //Cap with Collect over PhysicalProject
2754 _varMap[groupDefNode] = inputVar;
2755 groupDefNode = ConvertRelOpToScalarOpTree(groupDefNode, inputResultType);
2757 Node result = _iqtCommand.CreateVarDefNode(groupDefNode, out groupAggVar);
2762 /// If the return type of the input node is a RowType it flattens its individual non-row properties.
2763 /// The produced nodes are added to the given flattenedProperties list
2765 /// <param name="input"></param>
2766 /// <param name="flattenedProperties"></param>
2767 private void FlattenProperties(Node input, IList<Node> flattenedProperties)
2769 if (input.Op.Type.EdmType.BuiltInTypeKind == BuiltInTypeKind.RowType)
2771 IList<EdmProperty> properties = TypeHelpers.GetProperties(input.Op.Type);
2772 PlanCompiler.Assert(properties.Count != 0, "No nested properties for RowType");
2774 for (int i = 0; i < properties.Count; i++)
2776 Node newInput = (i == 0) ? input : OpCopier.Copy(_iqtCommand, input);
2777 FlattenProperties(_iqtCommand.CreateNode(_iqtCommand.CreatePropertyOp(properties[i]), newInput), flattenedProperties);
2782 flattenedProperties.Add(input);
2787 /// Common processing for the identical input and sort order arguments to the unrelated
2788 /// DbSkipExpression and DbSortExpression types.
2790 /// <param name="input">The input DbExpressionBinding from the DbSkipExpression or DbSortExpression</param>
2791 /// <param name="sortOrder">The list of SortClauses from the DbSkipExpression or DbSortExpression</param>
2792 /// <param name="sortKeys">A list to contain the converted SortKeys produced from the SortClauses</param>
2793 /// <param name="inputVar">The Var produced by the input to the DbSkipExpression or DbSortExpression</param>
2795 /// The converted form of the input to the DbSkipExpression or DbSortExpression, capped by a
2796 /// ProjectOp that defines and Vars referenced by the SortKeys.
2798 private Node VisitSortArguments(DbExpressionBinding input, IList<DbSortClause> sortOrder, List<SortKey> sortKeys, out Var inputVar)
2801 // Skip/DbSortExpression conversion first produces a ProjectOp over the original input.
2802 // This is done to ensure that the new (Constrained)SortOp itself does not
2803 // contain any local variable definitions (in the form of a VarDefList child node)
2804 // which makes it simpler to pull SortOps over ProjectOps later in the PlanCompiler
2805 // (specifically the PreProcessor).
2806 // The new ProjectOp projects the output Var of the input along with any Vars referenced
2807 // by the SortKeys, and its VarDefList child defines those Vars.
2810 // Bring the variable defined by the DbSortExpression's input set into scope
2811 // and retrieve it from the Node => Var map for later use.
2813 Node inputNode = EnterExpressionBinding(input);
2814 inputVar = _varMap[inputNode];
2817 // Convert the SortClauses, building a new VarDefOp Node for each one.
2819 VarVec projectedVars = _iqtCommand.CreateVarVec();
2820 projectedVars.Set(inputVar);
2822 List<Node> sortVarDefs = new List<Node>();
2823 PlanCompiler.Assert(sortKeys.Count == 0, "Non-empty SortKey list before adding converted SortClauses");
2824 for (int idx = 0; idx < sortOrder.Count; idx++)
2826 DbSortClause clause = sortOrder[idx];
2829 // Convert the DbSortClause DbExpression to a Node/Op pair
2831 Node exprNode = VisitExprAsScalar(clause.Expression);
2834 // In a valid CQT, DbSortClause expressions must have a result of an OrderComparable Type,
2835 // and such expressions will always convert to ScalarOps.
2837 ScalarOp specOp = exprNode.Op as ScalarOp;
2838 PlanCompiler.Assert(specOp != null, "DbSortClause Expression converted to non-ScalarOp");
2841 // Create a new ComputedVar with the same Type as the result Type of the DbSortClause DbExpression
2846 // Create a new VarDefOp Node that defines the ComputedVar and add it both to the
2847 // list of VarDefs and the VarVec of produced Vars that will be used to create a
2848 // SortKey-defining ProjectOp over the Sort input.
2850 sortVarDefs.Add(_iqtCommand.CreateVarDefNode(exprNode, out specVar));
2851 projectedVars.Set(specVar);
2854 // Create a new IQT SortKey that references the ComputedVar and has the same
2855 // Ascending and Collation as the original DbSortClause, then add it to the list of SortKeys.
2857 SortKey sortKey = null;
2858 if (string.IsNullOrEmpty(clause.Collation))
2860 sortKey = Command.CreateSortKey(specVar, clause.Ascending);
2864 sortKey = Command.CreateSortKey(specVar, clause.Ascending, clause.Collation);
2866 sortKeys.Add(sortKey);
2870 // Now that the SortClauses have been converted, remove the Input set's variable from scope.
2872 ExitExpressionBinding();
2875 // Cap the Input with a ProjectOp that pushes the sort key VarDefs down to that projection.
2878 _iqtCommand.CreateNode(
2879 _iqtCommand.CreateProjectOp(projectedVars),
2881 _iqtCommand.CreateNode(
2882 _iqtCommand.CreateVarDefListOp(),
2890 public override Node Visit(DbSkipExpression expression)
2893 // Invoke common processing of Skip/DbSortExpression arguments.
2896 List<SortKey> sortKeys = new List<SortKey>();
2897 Node inputNode = VisitSortArguments(expression.Input, expression.SortOrder, sortKeys, out inputVar);
2900 // Visit the Skip Count
2902 Node countNode = VisitExprAsScalar(expression.Count);
2905 // Create a new Node that has a new ConstrainedSortOp based on the SortKeys as its Op
2906 // and the following children:
2907 // - The Input node from VisitSortArguments
2908 // - The converted form of the skip count
2909 // - A NullOp of type Int64 to indicate that no limit operation is applied
2912 _iqtCommand.CreateNode(
2913 _iqtCommand.CreateConstrainedSortOp(sortKeys),
2916 _iqtCommand.CreateNode(_iqtCommand.CreateNullOp(_iqtCommand.IntegerType))
2919 // Update the Node --> Var mapping for the new ConstrainedSort Node.
2920 // ConstrainedSortOp maps to the same Op that its RelOp input maps to.
2921 _varMap[skipNode] = inputVar;
2926 public override Node Visit(DbSortExpression e)
2929 // Invoke common processing of Skip/DbSortExpression arguments.
2932 List<SortKey> sortKeys = new List<SortKey>();
2933 Node inputNode = VisitSortArguments(e.Input, e.SortOrder, sortKeys, out inputVar);
2936 // Create a new SortOp that uses the constructed SortKeys.
2938 SortOp newSortOp = _iqtCommand.CreateSortOp(sortKeys);
2941 // Create a new SortOp Node that has the new SortOp as its Op the Key-defining ProjectOp Node as its only child.
2943 Node newSortNode = _iqtCommand.CreateNode(newSortOp, inputNode);
2945 // Update the Node --> Var mapping for the new Sort Node.
2946 // SortOp maps to the same Op that its RelOp input maps to.
2947 _varMap[newSortNode] = inputVar;
2952 public override Node Visit(DbQuantifierExpression e)
2954 Node retNode = null;
2957 // Any converts to Exists(Filter(Input, Predicate))
2958 // All converts to Not(Exists(Filter(Input, Or(Not(Predicate), IsNull(Predicate)))))
2960 PlanCompiler.Assert(DbExpressionKind.Any == e.ExpressionKind || DbExpressionKind.All == e.ExpressionKind, "Invalid DbExpressionKind in DbQuantifierExpression");
2963 // Bring the input's variable into scope
2965 Node inputNode = EnterExpressionBinding(e.Input);
2968 // Convert the predicate
2970 Node predicateNode = VisitExprAsPredicate(e.Predicate);
2973 // If the quantifier is All then the predicate must become 'Not(Predicate) Or IsNull(Predicate)',
2974 // since the converted form of the predicate should exclude a member of the input set if and only if
2975 // the predicate evaluates to False - filtering only with the negated predicate would also exclude members
2976 // for which that negated predicate evaluates to null, possibly resulting in an erroneous empty result set
2977 // and causing the quantifier to produce a false positive result.
2979 if (DbExpressionKind.All == e.ExpressionKind)
2981 // Create the 'Not(Predicate)' branch of the Or.
2982 predicateNode = _iqtCommand.CreateNode(
2983 _iqtCommand.CreateConditionalOp(OpType.Not),
2987 // Visit the original predicate for use in the 'IsNull(Predicate)' branch of the Or.
2988 // Note that this is treated as a scalar value rather than a Boolean predicate.
2989 Node predicateCopy = VisitExprAsScalar(e.Predicate);
2991 // Create the 'IsNull(Predicate)' branch of the Or.
2992 predicateCopy = _iqtCommand.CreateNode(
2993 _iqtCommand.CreateConditionalOp(OpType.IsNull),
2997 // Finally, combine the branches with a Boolean 'Or' Op to create the updated predicate node.
2998 predicateNode = _iqtCommand.CreateNode(
2999 _iqtCommand.CreateConditionalOp(OpType.Or),
3006 // Remove the input's variable from scope
3008 ExitExpressionBinding();
3011 // Create a FilterOp around the original input set and map the FilterOp to the Var produced by the original input set.
3013 Var inputVar = _varMap[inputNode];
3014 inputNode = _iqtCommand.CreateNode(_iqtCommand.CreateFilterOp(), inputNode, predicateNode);
3015 _varMap[inputNode] = inputVar;
3018 // Create an ExistsOp around the filtered set to perform the quantifier operation.
3020 retNode = _iqtCommand.CreateNode(_iqtCommand.CreateExistsOp(), inputNode);
3023 // For All, the exists operation as currently built must now be negated.
3025 if (DbExpressionKind.All == e.ExpressionKind)
3027 retNode = _iqtCommand.CreateNode(_iqtCommand.CreateConditionalOp(OpType.Not), retNode);