mcs/class/referencesource/System.Data.Entity/System/Data/Common/EntitySql/SemanticResolver.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="SemanticResolver.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  [....]
   7 // @backupOwner [....]
   8 //---------------------------------------------------------------------
   9
  10 namespace System.Data.Common.EntitySql
  11 {
  12     using System;
  13     using System.Collections.Generic;
  14     using System.Data.Common.CommandTrees;
  15     using System.Data.Common.CommandTrees.ExpressionBuilder;
  16     using System.Data.Entity;
  17     using System.Data.Metadata.Edm;
  18     using System.Diagnostics;
  19     using System.Globalization;
  20     using System.Linq;
  21
  22     /// <summary>
  23     /// Represents eSQL expression class.
  24     /// </summary>
  25     internal enum ExpressionResolutionClass
  26     {
  27         /// <summary>
  28         /// A value expression such as a literal, variable or a value-returning expression.
  29         /// </summary>
  30         Value,
  31         /// <summary>
  32         /// An expression returning an entity container.
  33         /// </summary>
  34         EntityContainer,
  35         /// <summary>
  36         /// An expression returning a metadata member such as a type, function group or namespace.
  37         /// </summary>
  38         MetadataMember
  39     }
  40
  41     /// <summary>
  42     /// Abstract class representing the result of an eSQL expression classification.
  43     /// </summary>
  44     internal abstract class ExpressionResolution
  45     {
  46         protected ExpressionResolution(ExpressionResolutionClass @class)
  47         {
  48             ExpressionClass = @class;
  49         }
  50
  51         internal readonly ExpressionResolutionClass ExpressionClass;
  52         internal abstract string ExpressionClassName { get; }
  53     }
  54
  55     /// <summary>
  56     /// Represents an eSQL expression classified as <see cref="ExpressionResolutionClass.Value"/>.
  57     /// </summary>
  58     internal sealed class ValueExpression : ExpressionResolution
  59     {
  60         internal ValueExpression(DbExpression value)
  61             : base(ExpressionResolutionClass.Value)
  62         {
  63             Value = value;
  64         }
  65
  66         internal override string ExpressionClassName { get { return ValueClassName; } }
  67         internal static string ValueClassName { get { return Strings.LocalizedValueExpression; } }
  68
  69         /// <summary>
  70         /// Null if <see cref="ValueExpression"/> represents the untyped null.
  71         /// </summary>
  72         internal readonly DbExpression Value;
  73     }
  74
  75     /// <summary>
  76     /// Represents an eSQL expression classified as <see cref="ExpressionResolutionClass.EntityContainer"/>.
  77     /// </summary>
  78     internal sealed class EntityContainerExpression : ExpressionResolution
  79     {
  80         internal EntityContainerExpression(EntityContainer entityContainer)
  81             : base(ExpressionResolutionClass.EntityContainer)
  82         {
  83             EntityContainer = entityContainer;
  84         }
  85
  86         internal override string ExpressionClassName { get { return EntityContainerClassName; } }
  87         internal static string EntityContainerClassName { get { return Strings.LocalizedEntityContainerExpression; } }
  88
  89         internal readonly EntityContainer EntityContainer;
  90     }
  91
  92     /// <summary>
  93     /// Implements the semantic resolver in the context of a metadata workspace and typespace.
  94     /// </summary>
  95     /// <remarks>not thread safe</remarks>
  96     internal sealed class SemanticResolver
  97     {
  98         #region Fields
  99         private readonly ParserOptions _parserOptions;
 100         private readonly Dictionary<string, DbParameterReferenceExpression> _parameters;
 101         private readonly Dictionary<string, DbVariableReferenceExpression> _variables;
 102         private readonly TypeResolver _typeResolver;
 103         private readonly ScopeManager _scopeManager;
 104         private readonly List<ScopeRegion> _scopeRegions = new List<ScopeRegion>();
 105         private bool _ignoreEntityContainerNameResolution = false;
 106         private GroupAggregateInfo _currentGroupAggregateInfo = null;
 107         private uint _namegenCounter = 0;
 108         #endregion
 109
 110         #region Constructors
 111         /// <summary>
 112         /// Creates new instance of <see cref="SemanticResolver"/>.
 113         /// </summary>
 114         internal static SemanticResolver Create(Perspective perspective,
 115                                                 ParserOptions parserOptions,
 116                                                 IEnumerable<DbParameterReferenceExpression> parameters,
 117                                                 IEnumerable<DbVariableReferenceExpression> variables)
 118         {
 119             EntityUtil.CheckArgumentNull(perspective, "perspective");
 120             EntityUtil.CheckArgumentNull(parserOptions, "parserOptions");
 121
 122             return new SemanticResolver(
 123                 parserOptions,
 124                 ProcessParameters(parameters, parserOptions),
 125                 ProcessVariables(variables, parserOptions),
 126                 new TypeResolver(perspective, parserOptions));
 127         }
 128
 129         /// <summary>
 130         /// Creates a copy of <see cref="SemanticResolver"/> with clean scopes and shared inline function definitions inside of the type resolver.
 131         /// </summary>
 132         internal SemanticResolver CloneForInlineFunctionConversion()
 133         {
 134             return new SemanticResolver(
 135                  _parserOptions,
 136                  _parameters,
 137                  _variables,
 138                  _typeResolver);
 139         }
 140
 141         private SemanticResolver(ParserOptions parserOptions,
 142                                  Dictionary<string, DbParameterReferenceExpression> parameters,
 143                                  Dictionary<string, DbVariableReferenceExpression> variables,
 144                                  TypeResolver typeResolver)
 145         {
 146             _parserOptions = parserOptions;
 147             _parameters = parameters;
 148             _variables = variables;
 149             _typeResolver = typeResolver;
 150
 151             //
 152             // Creates Scope manager
 153             //
 154             _scopeManager = new ScopeManager(this.NameComparer);
 155
 156             //
 157             // Push a root scope region
 158             //
 159             EnterScopeRegion();
 160
 161             //
 162             // Add command free variables to the root scope
 163             //
 164             foreach (DbVariableReferenceExpression variable in _variables.Values)
 165             {
 166                 this.CurrentScope.Add(variable.VariableName, new FreeVariableScopeEntry(variable));
 167             }
 168         }
 169
 170         /// <summary>
 171         /// Validates that the specified parameters have valid, non-duplicated names
 172         /// </summary>
 173         /// <param name="paramDefs">The set of query parameters</param>
 174         /// <returns>A valid dictionary that maps parameter names to <see cref="DbParameterReferenceExpression"/>s using the current NameComparer</returns>
 175         private static Dictionary<string, DbParameterReferenceExpression> ProcessParameters(IEnumerable<DbParameterReferenceExpression> paramDefs, ParserOptions parserOptions)
 176         {
 177             Dictionary<string, DbParameterReferenceExpression> retParams = new Dictionary<string, DbParameterReferenceExpression>(parserOptions.NameComparer);
 178
 179             if (paramDefs != null)
 180             {
 181                 foreach (DbParameterReferenceExpression paramDef in paramDefs)
 182                 {
 183                     if (retParams.ContainsKey(paramDef.ParameterName))
 184                     {
 185                         throw EntityUtil.EntitySqlError(Strings.MultipleDefinitionsOfParameter(paramDef.ParameterName));
 186                     }
 187
 188                     Debug.Assert(paramDef.ResultType.IsReadOnly, "paramDef.ResultType.IsReadOnly must be set");
 189
 190                     retParams.Add(paramDef.ParameterName, paramDef);
 191                 }
 192             }
 193
 194             return retParams;
 195         }
 196
 197         /// <summary>
 198         /// Validates that the specified variables have valid, non-duplicated names
 199         /// </summary>
 200         /// <param name="varDefs">The set of free variables</param>
 201         /// <returns>A valid dictionary that maps variable names to <see cref="DbVariableReferenceExpression"/>s using the current NameComparer</returns>
 202         private static Dictionary<string, DbVariableReferenceExpression> ProcessVariables(IEnumerable<DbVariableReferenceExpression> varDefs, ParserOptions parserOptions)
 203         {
 204             Dictionary<string, DbVariableReferenceExpression> retVars = new Dictionary<string, DbVariableReferenceExpression>(parserOptions.NameComparer);
 205
 206             if (varDefs != null)
 207             {
 208                 foreach (DbVariableReferenceExpression varDef in varDefs)
 209                 {
 210                     if (retVars.ContainsKey(varDef.VariableName))
 211                     {
 212                         throw EntityUtil.EntitySqlError(Strings.MultipleDefinitionsOfVariable(varDef.VariableName));
 213                     }
 214
 215                     Debug.Assert(varDef.ResultType.IsReadOnly, "varDef.ResultType.IsReadOnly must be set");
 216
 217                     retVars.Add(varDef.VariableName, varDef);
 218                 }
 219             }
 220
 221             return retVars;
 222         }
 223         #endregion
 224
 225         #region Properties
 226         /// <summary>
 227         /// Returns ordinary command parameters. Empty dictionary in case of no parameters.
 228         /// </summary>
 229         internal Dictionary<string, DbParameterReferenceExpression> Parameters
 230         {
 231             get { return _parameters; }
 232         }
 233
 234         /// <summary>
 235         /// Returns command free variables. Empty dictionary in case of no variables.
 236         /// </summary>
 237         internal Dictionary<string, DbVariableReferenceExpression> Variables
 238         {
 239             get { return _variables; }
 240         }
 241
 242         /// <summary>
 243         /// TypeSpace/Metadata/Perspective dependent type resolver.
 244         /// </summary>
 245         internal TypeResolver TypeResolver
 246         {
 247             get { return _typeResolver; }
 248         }
 249
 250         /// <summary>
 251         /// Returns current Parser Options.
 252         /// </summary>
 253         internal ParserOptions ParserOptions
 254         {
 255             get { return _parserOptions; }
 256         }
 257
 258         /// <summary>
 259         /// Returns the current string comparer.
 260         /// </summary>
 261         internal StringComparer NameComparer
 262         {
 263             get { return _parserOptions.NameComparer; }
 264         }
 265
 266         /// <summary>
 267         /// Returns the list of scope regions: outer followed by inner.
 268         /// </summary>
 269         internal IEnumerable<ScopeRegion> ScopeRegions
 270         {
 271             get { return _scopeRegions; }
 272         }
 273
 274         /// <summary>
 275         /// Returns the current scope region.
 276         /// </summary>
 277         internal ScopeRegion CurrentScopeRegion
 278         {
 279             get { return _scopeRegions[_scopeRegions.Count - 1]; }
 280         }
 281
 282         /// <summary>
 283         /// Returns the current scope.
 284         /// </summary>
 285         internal Scope CurrentScope
 286         {
 287             get { return _scopeManager.CurrentScope; }
 288         }
 289
 290         /// <summary>
 291         /// Returns index of the current scope.
 292         /// </summary>
 293         internal int CurrentScopeIndex
 294         {
 295             get { return _scopeManager.CurrentScopeIndex; }
 296         }
 297
 298         /// <summary>
 299         /// Returns the current group aggregate info when processing group aggregate argument.
 300         /// </summary>
 301         internal GroupAggregateInfo CurrentGroupAggregateInfo
 302         {
 303             get { return _currentGroupAggregateInfo; }
 304         }
 305         #endregion
 306
 307         #region GetExpressionFromScopeEntry
 308         /// <summary>
 309         /// Returns the appropriate expression from a given scope entry.
 310         /// May return null for scope entries like <see cref="InvalidGroupInputRefScopeEntry"/>.
 311         /// </summary>
 312         private DbExpression GetExpressionFromScopeEntry(ScopeEntry scopeEntry, int scopeIndex, string varName, ErrorContext errCtx)
 313         {
 314             //
 315             // If
 316             //      1) we are in the context of a group aggregate or group key,
 317             //      2) and the scopeEntry can have multiple interpretations depending on the aggregation context,
 318             //      3) and the defining scope region of the scopeEntry is outer or equal to the defining scope region of the group aggregate,
 319             //      4) and the defining scope region of the scopeEntry is not performing conversion of a group key definition,
 320             // Then the expression that corresponds to the scopeEntry is either the GroupVarBasedExpression or the GroupAggBasedExpression.
 321             // Otherwise the default expression that corresponds to the scopeEntry is provided by scopeEntry.GetExpression(...) call.
 322             //
 323             // Explanation for #2 from the list above:
 324             // A scope entry may have multiple aggregation-context interpretations:
 325             //      - An expression in the context of a group key definition, obtained by scopeEntry.GetExpression(...);
 326             //        Example: select k1 from {0} as a group by a%2 as k1
 327             //                                                  ^^^
 328             //      - An expression in the context of a function aggregate, provided by iGroupExpressionExtendedInfo.GroupVarBasedExpression;
 329             //        Example: select max( a ) from {0} as a group by a%2 as k1
 330             //                            ^^^
 331             //      - An expression in the context of a group partition, provided by iGroupExpressionExtendedInfo.GroupAggBasedExpression;
 332             //        Example: select GroupPartition( a ) from {0} as a group by a%2 as k1
 333             //                                       ^^^
 334             // Note that expressions obtained from aggregation-context-dependent scope entries outside of the three contexts mentioned above
 335             // will default to the value returned by the scopeEntry.GetExpression(...) call. This value is the same as in the group key definition context.
 336             // These expressions have correct result types which enables partial expression validation.
 337             // However the contents of the expressions are invalid outside of the group key definitions, hence they can not appear in the final expression tree.
 338             // SemanticAnalyzer.ProcessGroupByClause(...) method guarantees that such expressions are only temporarily used during GROUP BY clause processing and
 339             // dropped afterwards.
 340             // Example: select a, k1 from {0} as a group by a%2 as k1
 341             //                 ^^^^^ - these expressions are processed twice: once during GROUP BY and then SELECT clause processing,
 342             //                         the expressions obtained during GROUP BY clause processing are dropped and only
 343             //                         the ones obtained during SELECT clause processing are accepted.
 344             //
 345             // Explanation for #3 from the list above:
 346             //      - An outer scope entry referenced inside of an aggregate may lift the aggregate to the outer scope region for evaluation,
 347             //        hence such a scope entry must be interpreted in the aggregation context. See explanation for #4 below for more info.
 348             //        Example:
 349             //
 350             //          select
 351             //              (select max(x) from {1} as y)
 352             //          from {0} as x
 353             //
 354             //      - If a scope entry is defined inside of a group aggregate, then the scope entry is not affected by the aggregate,
 355             //        hence such a scope entry is not interpreted in the aggregation context.
 356             //        Example:
 357             //
 358             //          select max(
 359             //                       anyelement( select b from {1} as b )
 360             //                    )
 361             //          from {0} as a group by a %2 as a1
 362             //
 363             //        In this query the aggregate argument contains a nested query expression.
 364             //        The nested query references b. Because b is defined inside of the aggregate it is not interpreted in the aggregation context and
 365             //        the expression for b should not be GroupVar/GroupAgg based, even though the reference to b appears inside of an aggregate.
 366             //
 367             // Explanation for #4 from the list above:
 368             // An aggregate evaluating on a particular scope region defines the interpretation of scope entries defined on that scope region.
 369             // In the case when an inner aggregate references a scope entry belonging to the evaluating region of an outer aggregate, the interpretation
 370             // of the scope entry is controlled by the outer aggregate, otherwise it is controlled by the inner aggregate.
 371             // Example:
 372             //
 373             //      select a1
 374             //      from {0} as a group by
 375             //                                anyelement(select value max(a + b) from {1} as b)
 376             //                          as a1
 377             //
 378             // In this query the aggregate inside of a1 group key definition, the max(a + b), references scope entry a.
 379             // Because a is referenced inside of the group key definition (which serves as an outer aggregate) and the key definition belongs to
 380             // the same scope region as a, a is interpreted in the context of the group key definition, not the function aggregate and
 381             // the expression for a is obtained by scopeEntry.GetExpression(...) call, not iGroupExpressionExtendedInfo.GroupVarBasedExpression.
 382             //
 383
 384             DbExpression expr = scopeEntry.GetExpression(varName, errCtx);
 385             Debug.Assert(expr != null, "scopeEntry.GetExpression(...) returned null");
 386
 387             if (_currentGroupAggregateInfo != null)
 388             {
 389                 //
 390                 // Make sure defining scope regions agree as described above.
 391                 // Outer scope region has smaller index value than the inner.
 392                 //
 393                 ScopeRegion definingScopeRegionOfScopeEntry = GetDefiningScopeRegion(scopeIndex);
 394                 if (definingScopeRegionOfScopeEntry.ScopeRegionIndex <= _currentGroupAggregateInfo.DefiningScopeRegion.ScopeRegionIndex)
 395                 {
 396                     //
 397                     // Let the group aggregate know the scope of the scope entry it references.
 398                     // This affects the scope region that will evaluate the group aggregate.
 399                     //
 400                     _currentGroupAggregateInfo.UpdateScopeIndex(scopeIndex, this);
 401
 402                     IGroupExpressionExtendedInfo iGroupExpressionExtendedInfo = scopeEntry as IGroupExpressionExtendedInfo;
 403                     if (iGroupExpressionExtendedInfo != null)
 404                     {
 405                         //
 406                         // Find the aggregate that controls interpretation of the current scope entry.
 407                         // This would be a containing aggregate with the defining scope region matching definingScopeRegionOfScopeEntry.
 408                         // If there is no such aggregate, then the current containing aggregate controls interpretation.
 409                         //
 410                         GroupAggregateInfo expressionInterpretationContext;
 411                         for (expressionInterpretationContext = _currentGroupAggregateInfo;
 412                              expressionInterpretationContext != null &&
 413                              expressionInterpretationContext.DefiningScopeRegion.ScopeRegionIndex >= definingScopeRegionOfScopeEntry.ScopeRegionIndex;
 414                              expressionInterpretationContext = expressionInterpretationContext.ContainingAggregate)
 415                         {
 416                             if (expressionInterpretationContext.DefiningScopeRegion.ScopeRegionIndex == definingScopeRegionOfScopeEntry.ScopeRegionIndex)
 417                             {
 418                                 break;
 419                             }
 420                         }
 421                         if (expressionInterpretationContext == null ||
 422                             expressionInterpretationContext.DefiningScopeRegion.ScopeRegionIndex < definingScopeRegionOfScopeEntry.ScopeRegionIndex)
 423                         {
 424                             expressionInterpretationContext = _currentGroupAggregateInfo;
 425                         }
 426
 427                         switch (expressionInterpretationContext.AggregateKind)
 428                         {
 429                             case GroupAggregateKind.Function:
 430                                 if (iGroupExpressionExtendedInfo.GroupVarBasedExpression != null)
 431                                 {
 432                                     expr = iGroupExpressionExtendedInfo.GroupVarBasedExpression;
 433                                 }
 434                                 break;
 435
 436                             case GroupAggregateKind.Partition:
 437                                 if (iGroupExpressionExtendedInfo.GroupAggBasedExpression != null)
 438                                 {
 439                                     expr = iGroupExpressionExtendedInfo.GroupAggBasedExpression;
 440                                 }
 441                                 break;
 442
 443                             case GroupAggregateKind.GroupKey:
 444                                 //
 445                                 // User the current expression obtained from scopeEntry.GetExpression(...)
 446                                 //
 447                                 break;
 448
 449                             default:
 450                                 Debug.Fail("Unexpected group aggregate kind.");
 451                                 break;
 452                         }
 453                     }
 454                 }
 455             }
 456
 457             return expr;
 458         }
 459         #endregion
 460
 461         #region Name resolution
 462         #region Resolve simple / metadata member name
 463         internal IDisposable EnterIgnoreEntityContainerNameResolution()
 464         {
 465             Debug.Assert(!_ignoreEntityContainerNameResolution, "EnterIgnoreEntityContainerNameResolution() is not reentrant.");
 466             _ignoreEntityContainerNameResolution = true;
 467             return new Disposer(delegate
 468             {
 469                 Debug.Assert(this._ignoreEntityContainerNameResolution, "_ignoreEntityContainerNameResolution must be true.");
 470                 this._ignoreEntityContainerNameResolution = false;
 471             });
 472         }
 473
 474         internal ExpressionResolution ResolveSimpleName(string name, bool leftHandSideOfMemberAccess, ErrorContext errCtx)
 475         {
 476             Debug.Assert(!String.IsNullOrEmpty(name), "name must not be null or empty");
 477
 478             //
 479             // Try resolving as a scope entry.
 480             //
 481             ScopeEntry scopeEntry;
 482             int scopeIndex;
 483             if (TryScopeLookup(name, out scopeEntry, out scopeIndex))
 484             {
 485                 //
 486                 // Check for invalid join left expression correlation.
 487                 //
 488                 if (scopeEntry.EntryKind == ScopeEntryKind.SourceVar && ((SourceScopeEntry)scopeEntry).IsJoinClauseLeftExpr)
 489                 {
 490                     throw EntityUtil.EntitySqlError(errCtx, Strings.InvalidJoinLeftCorrelation);
 491                 }
 492
 493                 //
 494                 // Set correlation flag.
 495                 //
 496                 SetScopeRegionCorrelationFlag(scopeIndex);
 497
 498                 return new ValueExpression(GetExpressionFromScopeEntry(scopeEntry, scopeIndex, name, errCtx));
 499             }
 500
 501             //
 502             // Try resolving as a member of the default entity container.
 503             //
 504             EntityContainer defaultEntityContainer = this.TypeResolver.Perspective.GetDefaultContainer();
 505             ExpressionResolution defaultEntityContainerResolution;
 506             if (defaultEntityContainer != null && TryResolveEntityContainerMemberAccess(defaultEntityContainer, name, errCtx, out defaultEntityContainerResolution))
 507             {
 508                 return defaultEntityContainerResolution;
 509             }
 510
 511             if (!_ignoreEntityContainerNameResolution)
 512             {
 513                 //
 514                 // Try resolving as an entity container.
 515                 //
 516                 EntityContainer entityContainer;
 517                 if (this.TypeResolver.Perspective.TryGetEntityContainer(name, _parserOptions.NameComparisonCaseInsensitive /*ignoreCase*/, out entityContainer))
 518                 {
 519                     return new EntityContainerExpression(entityContainer);
 520                 }
 521             }
 522
 523             //
 524             // Otherwise, resolve as an unqualified name.
 525             //
 526             return this.TypeResolver.ResolveUnqualifiedName(name, leftHandSideOfMemberAccess /* partOfQualifiedName */, errCtx);
 527         }
 528
 529         internal MetadataMember ResolveSimpleFunctionName(string name, ErrorContext errCtx)
 530         {
 531             //
 532             // "Foo()" represents a simple function name. Resolve it as an unqualified name by calling the type resolver directly.
 533             // Note that calling type resolver directly will avoid resolution of the identifier as a local variable or entity container
 534             // (these resolutions are performed only by ResolveSimpleName(...)).
 535             //
 536             var resolution = this.TypeResolver.ResolveUnqualifiedName(name, false /* partOfQualifiedName */, errCtx);
 537             if (resolution.MetadataMemberClass == MetadataMemberClass.Namespace)
 538             {
 539                 //
 540                 // Try resolving as a function import inside the default entity container.
 541                 //
 542                 EntityContainer defaultEntityContainer = this.TypeResolver.Perspective.GetDefaultContainer();
 543                 ExpressionResolution defaultEntityContainerResolution;
 544                 if (defaultEntityContainer != null &&
 545                     TryResolveEntityContainerMemberAccess(defaultEntityContainer, name, errCtx, out defaultEntityContainerResolution) &&
 546                     defaultEntityContainerResolution.ExpressionClass == ExpressionResolutionClass.MetadataMember)
 547                 {
 548                     resolution = (MetadataMember)defaultEntityContainerResolution;
 549                 }
 550             }
 551             return resolution;
 552         }
 553
 554
 555         /// <summary>
 556         /// Performs scope lookup returning the scope entry and its index.
 557         /// </summary>
 558         private bool TryScopeLookup(string key, out ScopeEntry scopeEntry, out int scopeIndex)
 559         {
 560             scopeEntry = null;
 561             scopeIndex = -1;
 562
 563             for (int i = CurrentScopeIndex; i >= 0; i--)
 564             {
 565                 if (_scopeManager.GetScopeByIndex(i).TryLookup(key, out scopeEntry))
 566                 {
 567                     scopeIndex = i;
 568                     return true;
 569                 }
 570             }
 571
 572             return false;
 573         }
 574
 575         internal MetadataMember ResolveMetadataMemberName(string[] name, ErrorContext errCtx)
 576         {
 577             return this.TypeResolver.ResolveMetadataMemberName(name, errCtx);
 578         }
 579         #endregion
 580
 581         #region Resolve member name in member access
 582         #region Resolve property access
 583         /// <summary>
 584         /// Resolve property <paramref name="name"/> off the <paramref name="valueExpr"/>.
 585         /// </summary>
 586         internal ValueExpression ResolvePropertyAccess(DbExpression valueExpr, string name, ErrorContext errCtx)
 587         {
 588             DbExpression propertyExpr;
 589
 590             if (TryResolveAsPropertyAccess(valueExpr, name, errCtx, out propertyExpr))
 591             {
 592                 return new ValueExpression(propertyExpr);
 593             }
 594
 595             if (TryResolveAsRefPropertyAccess(valueExpr, name, errCtx, out propertyExpr))
 596             {
 597                 return new ValueExpression(propertyExpr);
 598             }
 599
 600             if (TypeSemantics.IsCollectionType(valueExpr.ResultType))
 601             {
 602                 throw EntityUtil.EntitySqlError(errCtx, Strings.NotAMemberOfCollection(name, valueExpr.ResultType.EdmType.FullName));
 603             }
 604             else
 605             {
 606                 throw EntityUtil.EntitySqlError(errCtx, Strings.NotAMemberOfType(name, valueExpr.ResultType.EdmType.FullName));
 607             }
 608         }
 609
 610         /// <summary>
 611         /// Try resolving <paramref name="name"/> as a property of the value returned by the <paramref name="valueExpr"/>.
 612         /// </summary>
 613         private bool TryResolveAsPropertyAccess(DbExpression valueExpr, string name, ErrorContext errCtx, out DbExpression propertyExpr)
 614         {
 615             Debug.Assert(valueExpr != null, "valueExpr != null");
 616
 617             propertyExpr = null;
 618
 619             if (Helper.IsStructuralType(valueExpr.ResultType.EdmType))
 620             {
 621                 EdmMember member;
 622                 if (TypeResolver.Perspective.TryGetMember((StructuralType)valueExpr.ResultType.EdmType, name, _parserOptions.NameComparisonCaseInsensitive /*ignoreCase*/, out member))
 623                 {
 624                     Debug.Assert(member != null, "member != null");
 625                     Debug.Assert(this.NameComparer.Equals(name, member.Name), "this.NameComparer.Equals(name, member.Name)");
 626                     propertyExpr = DbExpressionBuilder.CreatePropertyExpressionFromMember(valueExpr, member);
 627                     return true;
 628                 }
 629             }
 630
 631             return false;
 632         }
 633
 634         /// <summary>
 635         /// If <paramref name="valueExpr"/> returns a reference, then deref and try resolving <paramref name="name"/> as a property of the dereferenced value.
 636         /// </summary>
 637         private bool TryResolveAsRefPropertyAccess(DbExpression valueExpr, string name, ErrorContext errCtx, out DbExpression propertyExpr)
 638         {
 639             Debug.Assert(valueExpr != null, "valueExpr != null");
 640
 641             propertyExpr = null;
 642
 643             if (TypeSemantics.IsReferenceType(valueExpr.ResultType))
 644             {
 645                 DbExpression derefExpr = valueExpr.Deref();
 646                 TypeUsage derefExprType = derefExpr.ResultType;
 647
 648                 if (TryResolveAsPropertyAccess(derefExpr, name, errCtx, out propertyExpr))
 649                 {
 650                     return true;
 651                 }
 652                 else
 653                 {
 654                     throw EntityUtil.EntitySqlError(errCtx, Strings.InvalidDeRefProperty(name, derefExprType.EdmType.FullName, valueExpr.ResultType.EdmType.FullName));
 655                 }
 656             }
 657
 658             return false;
 659         }
 660         #endregion
 661
 662         #region Resolve entity container member access
 663         /// <summary>
 664         /// Resolve entity set or function import <paramref name="name"/> in the <paramref name="entityContainer"/>
 665         /// </summary>
 666         internal ExpressionResolution ResolveEntityContainerMemberAccess(EntityContainer entityContainer, string name, ErrorContext errCtx)
 667         {
 668             ExpressionResolution resolution;
 669             if (TryResolveEntityContainerMemberAccess(entityContainer, name, errCtx, out resolution))
 670             {
 671                 return resolution;
 672             }
 673             else
 674             {
 675                 throw EntityUtil.EntitySqlError(errCtx, Strings.MemberDoesNotBelongToEntityContainer(name, entityContainer.Name));
 676             }
 677         }
 678
 679         private bool TryResolveEntityContainerMemberAccess(EntityContainer entityContainer, string name, ErrorContext errCtx, out ExpressionResolution resolution)
 680         {
 681             EntitySetBase entitySetBase;
 682             EdmFunction functionImport;
 683             if (this.TypeResolver.Perspective.TryGetExtent(entityContainer, name, _parserOptions.NameComparisonCaseInsensitive /*ignoreCase*/, out entitySetBase))
 684             {
 685                 resolution = new ValueExpression(entitySetBase.Scan());
 686                 return true;
 687             }
 688             else if (this.TypeResolver.Perspective.TryGetFunctionImport(entityContainer, name, _parserOptions.NameComparisonCaseInsensitive /*ignoreCase*/, out functionImport))
 689             {
 690                 resolution = new MetadataFunctionGroup(functionImport.FullName, new EdmFunction[] { functionImport });
 691                 return true;
 692             }
 693             else
 694             {
 695                 resolution = null;
 696                 return false;
 697             }
 698         }
 699         #endregion
 700
 701         #region Resolve metadata member access
 702         /// <summary>
 703         /// Resolve namespace, type or function <paramref name="name"/> in the <paramref name="metadataMember"/>
 704         /// </summary>
 705         internal MetadataMember ResolveMetadataMemberAccess(MetadataMember metadataMember, string name, ErrorContext errCtx)
 706         {
 707             return this.TypeResolver.ResolveMetadataMemberAccess(metadataMember, name, errCtx);
 708         }
 709         #endregion
 710         #endregion
 711
 712         #region Resolve internal aggregate name / alternative group key name
 713         /// <summary>
 714         /// Try resolving an internal aggregate name.
 715         /// </summary>
 716         internal bool TryResolveInternalAggregateName(string name, ErrorContext errCtx, out DbExpression dbExpression)
 717         {
 718             ScopeEntry scopeEntry;
 719             int scopeIndex;
 720             if (TryScopeLookup(name, out scopeEntry, out scopeIndex))
 721             {
 722                 //
 723                 // Set the correlation flag.
 724                 //
 725                 SetScopeRegionCorrelationFlag(scopeIndex);
 726
 727                 dbExpression = scopeEntry.GetExpression(name, errCtx);
 728                 return true;
 729             }
 730             else
 731             {
 732                 dbExpression = null;
 733                 return false;
 734             }
 735         }
 736         /// <summary>
 737         /// Try resolving multipart identifier as an alternative name of a group key (see SemanticAnalyzer.ProcessGroupByClause(...) for more info).
 738         /// </summary>
 739         internal bool TryResolveDotExprAsGroupKeyAlternativeName(AST.DotExpr dotExpr, out ValueExpression groupKeyResolution)
 740         {
 741             groupKeyResolution = null;
 742
 743             string[] names;
 744             ScopeEntry scopeEntry;
 745             int scopeIndex;
 746             if (IsInAnyGroupScope() &&
 747                 dotExpr.IsMultipartIdentifier(out names) &&
 748                 TryScopeLookup(TypeResolver.GetFullName(names), out scopeEntry, out scopeIndex))
 749             {
 750                 IGetAlternativeName iGetAlternativeName = scopeEntry as IGetAlternativeName;
 751
 752                 //
 753                 // Accept only if names[] match alternative name part by part.
 754                 //
 755                 if (iGetAlternativeName != null && iGetAlternativeName.AlternativeName != null &&
 756                     names.SequenceEqual(iGetAlternativeName.AlternativeName, this.NameComparer))
 757                 {
 758                     //
 759                     // Set correlation flag
 760                     //
 761                     SetScopeRegionCorrelationFlag(scopeIndex);
 762
 763                     groupKeyResolution = new ValueExpression(GetExpressionFromScopeEntry(scopeEntry, scopeIndex, TypeResolver.GetFullName(names), dotExpr.ErrCtx));
 764                     return true;
 765                 }
 766             }
 767             return false;
 768         }
 769         #endregion
 770         #endregion
 771
 772         #region Name generation utils (GenerateInternalName, CreateNewAlias, InferAliasName)
 773         /// <summary>
 774         /// Generates unique internal name.
 775         /// </summary>
 776         internal string GenerateInternalName(string hint)
 777         {
 778             // string concat is much faster than String.Format
 779             return "_##" + hint + unchecked(_namegenCounter++).ToString(CultureInfo.InvariantCulture);
 780         }
 781
 782         /// <summary>
 783         /// Creates a new alias name based on the <paramref name="expr"/> information.
 784         /// </summary>
 785         private string CreateNewAlias(DbExpression expr)
 786         {
 787             DbScanExpression extent = expr as DbScanExpression;
 788             if (null != extent)
 789             {
 790                 return extent.Target.Name;
 791             }
 792
 793             DbPropertyExpression property = expr as DbPropertyExpression;
 794             if (null != property)
 795             {
 796                 return property.Property.Name;
 797             }
 798
 799             DbVariableReferenceExpression varRef = expr as DbVariableReferenceExpression;
 800             if (null != varRef)
 801             {
 802                 return varRef.VariableName;
 803             }
 804
 805             return GenerateInternalName(String.Empty);
 806         }
 807
 808         /// <summary>
 809         /// Returns alias name from <paramref name="aliasedExpr"/> ast node if it contains an alias,
 810         /// otherwise creates a new alias name based on the <paramref name="aliasedExpr"/>.Expr or <paramref name="convertedExpression"/> information.
 811         /// </summary>
 812         internal string InferAliasName(AST.AliasedExpr aliasedExpr, DbExpression convertedExpression)
 813         {
 814             if (aliasedExpr.Alias != null)
 815             {
 816                 return aliasedExpr.Alias.Name;
 817             }
 818
 819             AST.Identifier id = aliasedExpr.Expr as AST.Identifier;
 820             if (null != id)
 821             {
 822                 return id.Name;
 823             }
 824
 825             AST.DotExpr dotExpr = aliasedExpr.Expr as AST.DotExpr;
 826             string[] names;
 827             if (null != dotExpr && dotExpr.IsMultipartIdentifier(out names))
 828             {
 829                 return names[names.Length - 1];
 830             }
 831
 832             return CreateNewAlias(convertedExpression);
 833         }
 834         #endregion
 835
 836         #region Scope/ScopeRegion utils
 837         /// <summary>
 838         /// Enters a new scope region.
 839         /// </summary>
 840         internal IDisposable EnterScopeRegion()
 841         {
 842             //
 843             // Push new scope (the first scope in the new scope region)
 844             //
 845             _scopeManager.EnterScope();
 846
 847             //
 848             // Create new scope region and push it
 849             //
 850             ScopeRegion scopeRegion = new ScopeRegion(_scopeManager, CurrentScopeIndex, _scopeRegions.Count);
 851             _scopeRegions.Add(scopeRegion);
 852
 853             //
 854             // Return scope region disposer that rolls back the scope.
 855             //
 856             return new Disposer(delegate
 857                 {
 858                     Debug.Assert(this.CurrentScopeRegion == scopeRegion, "Scope region stack is corrupted.");
 859
 860                     //
 861                     // Root scope region is permanent.
 862                     //
 863                     Debug.Assert(this._scopeRegions.Count > 1, "_scopeRegionFlags.Count > 1");
 864
 865                     //
 866                     // Reset aggregate info of AST nodes of aggregates resolved to the CurrentScopeRegion.
 867                     //
 868                     this.CurrentScopeRegion.GroupAggregateInfos.ForEach(groupAggregateInfo => groupAggregateInfo.DetachFromAstNode());
 869
 870                     //
 871                     // Rollback scopes of the region.
 872                     //
 873                     this.CurrentScopeRegion.RollbackAllScopes();
 874
 875                     //
 876                     // Remove the scope region.
 877                     //
 878                     this._scopeRegions.Remove(CurrentScopeRegion);
 879                 });
 880         }
 881
 882         /// <summary>
 883         /// Rollback all scopes above the <paramref name="scopeIndex"/>.
 884         /// </summary>
 885         internal void RollbackToScope(int scopeIndex)
 886         {
 887             _scopeManager.RollbackToScope(scopeIndex);
 888         }
 889
 890         /// <summary>
 891         /// Enter a new scope.
 892         /// </summary>
 893         internal void EnterScope()
 894         {
 895             _scopeManager.EnterScope();
 896         }
 897
 898         /// <summary>
 899         /// Leave the current scope.
 900         /// </summary>
 901         internal void LeaveScope()
 902         {
 903             _scopeManager.LeaveScope();
 904         }
 905
 906         /// <summary>
 907         /// Returns true if any of the ScopeRegions from the closest to the outermost has IsAggregating = true
 908         /// </summary>
 909         internal bool IsInAnyGroupScope()
 910         {
 911             for (int i = 0; i < _scopeRegions.Count; i++)
 912             {
 913                 if (_scopeRegions[i].IsAggregating)
 914                 {
 915                     return true;
 916                 }
 917             }
 918             return false;
 919         }
 920
 921         internal ScopeRegion GetDefiningScopeRegion(int scopeIndex)
 922         {
 923             //
 924             // Starting from the innermost, find the outermost scope region that contains the scope.
 925             //
 926             for (int i = _scopeRegions.Count - 1; i >= 0; --i)
 927             {
 928                 if (_scopeRegions[i].ContainsScope(scopeIndex))
 929                 {
 930                     return _scopeRegions[i];
 931                 }
 932             }
 933             Debug.Fail("Failed to find the defining scope region for the given scope.");
 934             return null;
 935         }
 936
 937         /// <summary>
 938         /// Sets the scope region correlation flag based on the scope index of the referenced scope entry.
 939         /// </summary>
 940         private void SetScopeRegionCorrelationFlag(int scopeIndex)
 941         {
 942             GetDefiningScopeRegion(scopeIndex).WasResolutionCorrelated = true;
 943         }
 944         #endregion
 945
 946         #region Group aggregate utils
 947         /// <summary>
 948         /// Enters processing of a function group aggregate.
 949         /// </summary>
 950         internal IDisposable EnterFunctionAggregate(AST.MethodExpr methodExpr, ErrorContext errCtx, out FunctionAggregateInfo aggregateInfo)
 951         {
 952             aggregateInfo = new FunctionAggregateInfo(methodExpr, errCtx, _currentGroupAggregateInfo, CurrentScopeRegion);
 953             return EnterGroupAggregate(aggregateInfo);
 954         }
 955
 956         /// <summary>
 957         /// Enters processing of a group partition aggregate.
 958         /// </summary>
 959         internal IDisposable EnterGroupPartition(AST.GroupPartitionExpr groupPartitionExpr, ErrorContext errCtx, out GroupPartitionInfo aggregateInfo)
 960         {
 961             aggregateInfo = new GroupPartitionInfo(groupPartitionExpr, errCtx, _currentGroupAggregateInfo, CurrentScopeRegion);
 962             return EnterGroupAggregate(aggregateInfo);
 963         }
 964
 965         /// <summary>
 966         /// Enters processing of a group partition aggregate.
 967         /// </summary>
 968         internal IDisposable EnterGroupKeyDefinition(GroupAggregateKind aggregateKind, ErrorContext errCtx, out GroupKeyAggregateInfo aggregateInfo)
 969         {
 970             aggregateInfo = new GroupKeyAggregateInfo(aggregateKind, errCtx, _currentGroupAggregateInfo, CurrentScopeRegion);
 971             return EnterGroupAggregate(aggregateInfo);
 972         }
 973
 974         private IDisposable EnterGroupAggregate(GroupAggregateInfo aggregateInfo)
 975         {
 976             _currentGroupAggregateInfo = aggregateInfo;
 977             return new Disposer(delegate
 978                 {
 979                     //
 980                     // First, pop the element from the stack to keep the stack valid...
 981                     //
 982                     Debug.Assert(this._currentGroupAggregateInfo == aggregateInfo, "Aggregare info stack is corrupted.");
 983                     this._currentGroupAggregateInfo = aggregateInfo.ContainingAggregate;
 984
 985                     //
 986                     // ...then validate and seal the aggregate info.
 987                     // Note that this operation may throw an EntitySqlException.
 988                     //
 989                     aggregateInfo.ValidateAndComputeEvaluatingScopeRegion(this);
 990                 });
 991         }
 992         #endregion
 993
 994         #region Function overload resolution (untyped null aware)
 995         internal static EdmFunction ResolveFunctionOverloads(IList<EdmFunction> functionsMetadata,
 996                                                              IList<TypeUsage> argTypes,
 997                                                              bool isGroupAggregateFunction,
 998                                                              out bool isAmbiguous)
 999         {
1000             return FunctionOverloadResolver.ResolveFunctionOverloads(
1001                 functionsMetadata,
1002                 argTypes,
1003                 UntypedNullAwareFlattenArgumentType,
1004                 UntypedNullAwareFlattenParameterType,
1005                 UntypedNullAwareIsPromotableTo,
1006                 UntypedNullAwareIsStructurallyEqual,
1007                 isGroupAggregateFunction,
1008                 out isAmbiguous);
1009         }
1010
1011         internal static TFunctionMetadata ResolveFunctionOverloads<TFunctionMetadata, TFunctionParameterMetadata>(
1012             IList<TFunctionMetadata> functionsMetadata,
1013             IList<TypeUsage> argTypes,
1014             Func<TFunctionMetadata, IList<TFunctionParameterMetadata>> getSignatureParams,
1015             Func<TFunctionParameterMetadata, TypeUsage> getParameterTypeUsage,
1016             Func<TFunctionParameterMetadata, ParameterMode> getParameterMode,
1017             bool isGroupAggregateFunction,
1018             out bool isAmbiguous) where TFunctionMetadata : class
1019         {
1020             return FunctionOverloadResolver.ResolveFunctionOverloads(
1021                 functionsMetadata,
1022                 argTypes,
1023                 getSignatureParams,
1024                 getParameterTypeUsage,
1025                 getParameterMode,
1026                 UntypedNullAwareFlattenArgumentType,
1027                 UntypedNullAwareFlattenParameterType,
1028                 UntypedNullAwareIsPromotableTo,
1029                 UntypedNullAwareIsStructurallyEqual,
1030                 isGroupAggregateFunction,
1031                 out isAmbiguous);
1032         }
1033
1034         private static IEnumerable<TypeUsage> UntypedNullAwareFlattenArgumentType(TypeUsage argType)
1035         {
1036             return argType != null ? TypeSemantics.FlattenType(argType) : new TypeUsage[] { null };
1037         }
1038         private static IEnumerable<TypeUsage> UntypedNullAwareFlattenParameterType(TypeUsage paramType, TypeUsage argType)
1039         {
1040             return argType != null ? TypeSemantics.FlattenType(paramType) : new TypeUsage[] { paramType };
1041         }
1042         private static bool UntypedNullAwareIsPromotableTo(TypeUsage fromType, TypeUsage toType)
1043         {
1044             if (fromType == null)
1045             {
1046                 //
1047                 // We can implicitly promote null to any type except collection.
1048                 //
1049                 return !Helper.IsCollectionType(toType.EdmType);
1050             }
1051             else
1052             {
1053                 return TypeSemantics.IsPromotableTo(fromType, toType);
1054             }
1055         }
1056         private static bool UntypedNullAwareIsStructurallyEqual(TypeUsage fromType, TypeUsage toType)
1057         {
1058             if (fromType == null)
1059             {
1060                 return UntypedNullAwareIsPromotableTo(fromType, toType);
1061             }
1062             else
1063             {
1064                 return TypeSemantics.IsStructurallyEqual(fromType, toType);
1065             }
1066         }
1067         #endregion
1068     }
1069
1070     /// <summary>
1071     /// Represents an utility for creating anonymous IDisposable implementations.
1072     /// </summary>
1073     internal class Disposer : IDisposable
1074     {
1075         private readonly Action _action;
1076
1077         internal Disposer(Action action)
1078         {
1079             Debug.Assert(action != null, "action != null");
1080             _action = action;
1081         }
1082
1083         public void Dispose()
1084         {
1085             _action();
1086             GC.SuppressFinalize(this);
1087         }
1088     }
1089
1090     internal enum GroupAggregateKind
1091     {
1092         None,
1093         /// <summary>
1094         /// Inside of an aggregate function (Max, Min, etc).
1095         /// All range variables originating on the defining scope of this aggregate should yield <see cref="IGroupExpressionExtendedInfo.GroupVarBasedExpression"/>.
1096         /// </summary>
1097         Function,
1098         /// <summary>
1099         /// Inside of GROUPPARTITION expression.
1100         /// All range variables originating on the defining scope of this aggregate should yield <see cref="IGroupExpressionExtendedInfo.GroupAggBasedExpression"/>.
1101         /// </summary>
1102         Partition,
1103         /// <summary>
1104         /// Inside of a group key definition
1105         /// All range variables originating on the defining scope of this aggregate should yield <see cref="ScopeEntry.GetExpression"/>.
1106         /// </summary>
1107         GroupKey
1108     }
1109
1110     /// <summary>
1111     /// Represents group aggregate information during aggregate construction/resolution.
1112     /// </summary>
1113     internal abstract class GroupAggregateInfo
1114     {
1115         protected GroupAggregateInfo(
1116             GroupAggregateKind aggregateKind,
1117             AST.GroupAggregateExpr astNode,
1118             ErrorContext errCtx,
1119             GroupAggregateInfo containingAggregate,
1120             ScopeRegion definingScopeRegion)
1121         {
1122             Debug.Assert(aggregateKind != GroupAggregateKind.None, "aggregateKind != GroupAggregateKind.None");
1123             Debug.Assert(errCtx != null, "errCtx != null");
1124             Debug.Assert(definingScopeRegion != null, "definingScopeRegion != null");
1125
1126             AggregateKind = aggregateKind;
1127             AstNode = astNode;
1128             ErrCtx = errCtx;
1129             DefiningScopeRegion = definingScopeRegion;
1130             SetContainingAggregate(containingAggregate);
1131         }
1132
1133         protected void AttachToAstNode(string aggregateName, TypeUsage resultType)
1134         {
1135             Debug.Assert(AstNode != null, "AstNode must be set.");
1136             Debug.Assert(aggregateName != null && resultType != null, "aggregateName and aggregateDefinition must not be null.");
1137             Debug.Assert(AggregateName == null && AggregateStubExpression == null, "Cannot reattach.");
1138
1139             AggregateName = aggregateName;
1140             AggregateStubExpression = resultType.Null();
1141
1142             // Attach group aggregate info to the ast node.
1143             AstNode.AggregateInfo = this;
1144         }
1145
1146         internal void DetachFromAstNode()
1147         {
1148             Debug.Assert(AstNode != null, "AstNode must be set.");
1149             AstNode.AggregateInfo = null;
1150         }
1151
1152         /// <summary>
1153         /// Updates referenced scope index of the aggregate.
1154         /// Function call is not allowed after <see cref="ValidateAndComputeEvaluatingScopeRegion"/> has been called.
1155         /// </summary>
1156         internal void UpdateScopeIndex(int referencedScopeIndex, SemanticResolver sr)
1157         {
1158             Debug.Assert(_evaluatingScopeRegion == null, "Can not update referenced scope index after _evaluatingScopeRegion have been computed.");
1159
1160             ScopeRegion referencedScopeRegion = sr.GetDefiningScopeRegion(referencedScopeIndex);
1161
1162             if (_innermostReferencedScopeRegion == null ||
1163                 _innermostReferencedScopeRegion.ScopeRegionIndex < referencedScopeRegion.ScopeRegionIndex)
1164             {
1165                 _innermostReferencedScopeRegion = referencedScopeRegion;
1166             }
1167         }
1168
1169         /// <summary>
1170         /// Gets/sets the innermost referenced scope region of the current aggregate.
1171         /// This property is used to save/restore the scope region value during a potentially throw-away attempt to
1172         /// convert an <see cref="AST.MethodExpr"/> as a collection function in the <see cref="SemanticAnalyzer.ConvertAggregateFunctionInGroupScope"/> method.
1173         /// Setting the value is not allowed after <see cref="ValidateAndComputeEvaluatingScopeRegion"/> has been called.
1174         /// </summary>
1175         internal ScopeRegion InnermostReferencedScopeRegion
1176         {
1177             get { return _innermostReferencedScopeRegion; }
1178             set
1179             {
1180                 Debug.Assert(_evaluatingScopeRegion == null, "Can't change _innermostReferencedScopeRegion after _evaluatingScopeRegion has been initialized.");
1181                 _innermostReferencedScopeRegion = value;
1182             }
1183         }
1184         private ScopeRegion _innermostReferencedScopeRegion;
1185
1186         /// <summary>
1187         /// Validates the aggregate info and computes <see cref="EvaluatingScopeRegion"/> property.
1188         /// Seals the aggregate info object (no more AddContainedAggregate(...), RemoveContainedAggregate(...) and UpdateScopeIndex(...) calls allowed).
1189         /// </summary>
1190         internal void ValidateAndComputeEvaluatingScopeRegion(SemanticResolver sr)
1191         {
1192             Debug.Assert(_evaluatingScopeRegion == null, "_evaluatingScopeRegion has already been initialized");
1193             //
1194             // If _innermostReferencedScopeRegion is null, it means the aggregate is not correlated (a constant value),
1195             // so resolve it to the DefiningScopeRegion.
1196             //
1197             _evaluatingScopeRegion = _innermostReferencedScopeRegion ?? DefiningScopeRegion;
1198
1199             if (!_evaluatingScopeRegion.IsAggregating)
1200             {
1201                 //
1202                 // In some cases the found scope region does not aggregate (has no grouping). So adding the aggregate to that scope won't work.
1203                 // In this situation we need to backtrack from the found region to the first inner region that performs aggregation.
1204                 // Example:
1205                 // select yy.cx, yy.cy, yy.cz
1206                 // from {1, 2} as x cross apply (select zz.cx, zz.cy, zz.cz
1207                 //                               from {3, 4} as y cross apply (select Count(x) as cx, Count(y) as cy, Count(z) as cz
1208                 //                                                             from {5, 6} as z) as zz
1209                 //                              ) as yy
1210                 // Note that Count aggregates cx and cy refer to scope regions that do aggregate. All three aggregates needs to be added to the only
1211                 // aggregating region - the innermost.
1212                 //
1213                 int scopeRegionIndex = _evaluatingScopeRegion.ScopeRegionIndex;
1214                 _evaluatingScopeRegion = null;
1215                 foreach (ScopeRegion innerSR in sr.ScopeRegions.Skip(scopeRegionIndex))
1216                 {
1217                     if (innerSR.IsAggregating)
1218                     {
1219                         _evaluatingScopeRegion = innerSR;
1220                         break;
1221                     }
1222                 }
1223                 if (_evaluatingScopeRegion == null)
1224                 {
1225                     throw EntityUtil.EntitySqlError(Strings.GroupVarNotFoundInScope);
1226                 }
1227             }
1228
1229             //
1230             // Validate all the contained aggregates for violation of the containment rule:
1231             // None of the nested (contained) aggregates must be evaluating on a scope region that is
1232             //      a. equal or inner to the evaluating scope of the current aggregate and
1233             //      b. equal or outer to the defining scope of the current aggregate.
1234             //
1235             // Example of a disallowed query:
1236             //
1237             //      select
1238             //              (select max(x + max(y))
1239             //               from {1} as y)
1240             //      from {0} as x
1241             //
1242             // Example of an allowed query where the ESR of the nested aggregate is outer to the ESR of the outer aggregate:
1243             //
1244             //      select
1245             //              (select max(y + max(x))
1246             //               from {1} as y)
1247             //      from {0} as x
1248             //
1249             // Example of an allowed query where the ESR of the nested aggregate is inner to the DSR of the outer aggregate:
1250             //
1251             //      select max(x + anyelement(select value max(y) from {1} as y))
1252             //      from {0} as x
1253             //
1254             Debug.Assert(_evaluatingScopeRegion.IsAggregating, "_evaluatingScopeRegion.IsAggregating must be true");
1255             Debug.Assert(_evaluatingScopeRegion.ScopeRegionIndex <= DefiningScopeRegion.ScopeRegionIndex, "_evaluatingScopeRegion must outer to the DefiningScopeRegion");
1256             ValidateContainedAggregates(_evaluatingScopeRegion.ScopeRegionIndex, DefiningScopeRegion.ScopeRegionIndex);
1257         }
1258
1259         /// <summary>
1260         /// Recursively validates that <see cref="GroupAggregateInfo.EvaluatingScopeRegion"/> of all contained aggregates
1261         /// is outside of the range of scope regions defined by <paramref name="outerBoundaryScopeRegionIndex"/> and <paramref name="innerBoundaryScopeRegionIndex"/>.
1262         /// Throws in the case of violation.
1263         /// </summary>
1264         private void ValidateContainedAggregates(int outerBoundaryScopeRegionIndex, int innerBoundaryScopeRegionIndex)
1265         {
1266             if (_containedAggregates != null)
1267             {
1268                 foreach (GroupAggregateInfo containedAggregate in _containedAggregates)
1269                 {
1270                     if (containedAggregate.EvaluatingScopeRegion.ScopeRegionIndex >= outerBoundaryScopeRegionIndex &&
1271                         containedAggregate.EvaluatingScopeRegion.ScopeRegionIndex <= innerBoundaryScopeRegionIndex)
1272                     {
1273                         int line, column;
1274                         string currentAggregateInfo = EntitySqlException.FormatErrorContext(
1275                             ErrCtx.CommandText,
1276                             ErrCtx.InputPosition,
1277                             ErrCtx.ErrorContextInfo,
1278                             ErrCtx.UseContextInfoAsResourceIdentifier,
1279                             out line, out column);
1280
1281                         string nestedAggregateInfo = EntitySqlException.FormatErrorContext(
1282                             containedAggregate.ErrCtx.CommandText,
1283                             containedAggregate.ErrCtx.InputPosition,
1284                             containedAggregate.ErrCtx.ErrorContextInfo,
1285                             containedAggregate.ErrCtx.UseContextInfoAsResourceIdentifier,
1286                             out line, out column);
1287
1288                         throw EntityUtil.EntitySqlError(Strings.NestedAggregateCannotBeUsedInAggregate(nestedAggregateInfo, currentAggregateInfo));
1289                     }
1290
1291                     //
1292                     // We need to check the full subtree in order to catch this case:
1293                     //      select max(x +
1294                     //                     anyelement(select max(y +
1295                     //                                               anyelement(select value max(x)
1296                     //                                               from {2} as z))
1297                     //                                from {1} as y))
1298                     //      from {0} as x
1299                     //
1300                     containedAggregate.ValidateContainedAggregates(outerBoundaryScopeRegionIndex, innerBoundaryScopeRegionIndex);
1301                 }
1302             }
1303         }
1304
1305         internal void SetContainingAggregate(GroupAggregateInfo containingAggregate)
1306         {
1307             if (_containingAggregate != null)
1308             {
1309                 //
1310                 // Aggregates in this query
1311                 //
1312                 //      select value max(anyelement(select value max(b + max(a + anyelement(select value c1
1313                 //                                                                          from {2} as c group by c as c1)))
1314                 //                                  from {1} as b group by b as b1))
1315                 //
1316                 //      from {0} as a group by a as a1
1317                 //
1318                 // are processed in the following steps:
1319                 // 1.  the outermost aggregate (max1) begins processing as a collection function;
1320                 // 2.  the middle aggregate (max2) begins processing as a collection function;
1321                 // 3.  the innermost aggregate (max3) is processed as a collection function;
1322                 // 4.  max3 is reprocessed as an aggregate; it does not see any containing aggregates at this point, so it's not wired up;
1323                 //     max3 is validated and sealed;
1324                 //     evaluating scope region for max3 is the outermost scope region, to which it gets assigned;
1325                 //     max3 aggregate info object is attached to the corresponding AST node;
1326                 // 5.  max2 completes processing as a collection function and begins processing as an aggregate;
1327                 // 6.  max3 is reprocessed as an aggregate in the SemanticAnalyzer.TryConvertAsResolvedGroupAggregate(...) method, and
1328                 //     wired up to max2 as contained/containing;
1329                 // 7.  max2 completes processing as an aggregate;
1330                 //     max2 is validated and sealed;
1331                 //     note that max2 does not see any containing aggregates at this point, so it's wired up only to max3;
1332                 //     evaluating scope region for max2 is the middle scope region to which it gets assigned;
1333                 // 6.  middle scope region completes processing, yields a DbExpression and cleans up all aggregate info objects assigned to it (max2);
1334                 //     max2 is detached from the corresponding AST node;
1335                 //     at this point max3 is still assigned to the outermost scope region and still wired to the dropped max2 as containing/contained;
1336                 // 7.  max1 completes processing as a collection function and begins processing as an aggregate;
1337                 // 8.  max2 is revisited and begins processing as a collection function (note that because the old aggregate info object for max2 was dropped
1338                 //     and detached from the AST node in step 6, SemanticAnalyzer.TryConvertAsResolvedGroupAggregate(...) does not recognize max2 as an aggregate);
1339                 // 9.  max3 is recognized as an aggregate in the SemanticAnalyzer.TryConvertAsResolvedGroupAggregate(...) method;
1340                 //     max3 is rewired from the dropped max2 (step 6) to max1 as contained/containing, now max1 and max3 are wired as containing/contained;
1341                 // 10. max2 completes processing as a collection function and begins processing as an aggregate;
1342                 //     max2 sees max1 as a containing aggregate and wires to it;
1343                 // 11. max3 is reprocessed as resolved aggregate inside of TryConvertAsResolvedGroupAggregate(...) method;
1344                 //     max3 is rewired from max1 to max2 as containing/contained aggregate;
1345                 // 12. at this point max1 is wired to max2 and max2 is wired to max3, the tree is correct;
1346                 //
1347                 // ... both max1 and max3 are assigned to the same scope for evaluation, this is detected and an error is reported;
1348                 //
1349
1350                 //
1351                 // Remove this aggregate from the old containing aggregate before rewiring to the new parent.
1352                 //
1353                 _containingAggregate.RemoveContainedAggregate(this);
1354             }
1355
1356             //
1357             // Accept the new parent and wire to it as a contained aggregate.
1358             //
1359             _containingAggregate = containingAggregate;
1360             if (_containingAggregate != null)
1361             {
1362                 _containingAggregate.AddContainedAggregate(this);
1363             }
1364         }
1365
1366         /// <summary>
1367         /// Function call is not allowed after <see cref="ValidateAndComputeEvaluatingScopeRegion"/> has been called.
1368         /// Adding new contained aggregate may invalidate the current aggregate.
1369         /// </summary>
1370         private void AddContainedAggregate(GroupAggregateInfo containedAggregate)
1371         {
1372             Debug.Assert(_evaluatingScopeRegion == null, "Can not add contained aggregate after _evaluatingScopeRegion have been computed.");
1373
1374             if (_containedAggregates == null)
1375             {
1376                 _containedAggregates = new List<GroupAggregateInfo>();
1377             }
1378             Debug.Assert(_containedAggregates.Contains(containedAggregate) == false, "containedAggregate is already registered");
1379             _containedAggregates.Add(containedAggregate);
1380         }
1381         private List<GroupAggregateInfo> _containedAggregates;
1382
1383         /// <summary>
1384         /// Function call is _allowed_ after <see cref="ValidateAndComputeEvaluatingScopeRegion"/> has been called.
1385         /// Removing contained aggregates cannot invalidate the current aggregate.
1386         ///
1387         /// Consider the following query:
1388         ///
1389         ///   select value max(a + anyelement(select value max(b + max(a + anyelement(select value c1
1390         ///                                                                           from {2} as c group by c as c1)))
1391         ///                                   from {1} as b group by b as b1))
1392         ///   from {0} as a group by a as a1
1393         ///
1394         /// Outer aggregate - max1, middle aggregate - max2, inner aggregate - max3.
1395         /// In this query after max1 have been processed as a collection function, max2 and max3 are wired as containing/contained.
1396         /// There is a point later when max1 is processed as an aggregate, max2 is processed as a collection function and max3 is processed as
1397         /// an aggregate. Note that at this point the "aggregate" version of max2 is dropped and detached from the AST node when the middle scope region
1398         /// completes processing; also note that because evaluating scope region of max3 is the outer scope region, max3 aggregate info is still attached to
1399         /// the AST node and it is still wired to the dropped aggregate info object of max2. At this point max3 does not see new max2 as a containing aggregate,
1400         /// and it rewires to max1, during this rewiring it needs to to remove itself from the old max2 and add itself to max1.
1401         /// The old max2 at this point is sealed, so the removal is performed on the sealed object.
1402         /// </summary>
1403         private void RemoveContainedAggregate(GroupAggregateInfo containedAggregate)
1404         {
1405             Debug.Assert(_containedAggregates != null && _containedAggregates.Contains(containedAggregate), "_containedAggregates.Contains(containedAggregate)");
1406
1407             _containedAggregates.Remove(containedAggregate);
1408         }
1409
1410         internal readonly GroupAggregateKind AggregateKind;
1411
1412         /// <summary>
1413         /// Null when <see cref="GroupAggregateInfo"/> is created for a group key processing.
1414         /// </summary>
1415         internal readonly AST.GroupAggregateExpr AstNode;
1416
1417         internal readonly ErrorContext ErrCtx;
1418
1419         /// <summary>
1420         /// Scope region that contains the aggregate expression.
1421         /// </summary>
1422         internal readonly ScopeRegion DefiningScopeRegion;
1423
1424         /// <summary>
1425         /// Scope region that evaluates the aggregate expression.
1426         /// </summary>
1427         internal ScopeRegion EvaluatingScopeRegion
1428         {
1429             get
1430             {
1431                 //
1432                 // _evaluatingScopeRegion is initialized in the ValidateAndComputeEvaluatingScopeRegion(...) method.
1433                 //
1434                 Debug.Assert(_evaluatingScopeRegion != null, "_evaluatingScopeRegion is not initialized");
1435                 return _evaluatingScopeRegion;
1436             }
1437         }
1438         private ScopeRegion _evaluatingScopeRegion;
1439
1440         /// <summary>
1441         /// Parent aggregate expression that contains the current aggregate expression.
1442         /// May be null.
1443         /// </summary>
1444         internal GroupAggregateInfo ContainingAggregate
1445         {
1446             get { return _containingAggregate; }
1447         }
1448         private GroupAggregateInfo _containingAggregate;
1449
1450         internal string AggregateName;
1451         internal DbNullExpression AggregateStubExpression;
1452     }
1453
1454     internal sealed class FunctionAggregateInfo : GroupAggregateInfo
1455     {
1456         internal FunctionAggregateInfo(AST.MethodExpr methodExpr, ErrorContext errCtx, GroupAggregateInfo containingAggregate, ScopeRegion definingScopeRegion)
1457             : base(GroupAggregateKind.Function, methodExpr, errCtx, containingAggregate, definingScopeRegion)
1458         {
1459             Debug.Assert(methodExpr != null, "methodExpr != null");
1460         }
1461
1462         internal void AttachToAstNode(string aggregateName, DbAggregate aggregateDefinition)
1463         {
1464             Debug.Assert(aggregateDefinition != null, "aggregateDefinition != null");
1465             base.AttachToAstNode(aggregateName, aggregateDefinition.ResultType);
1466             AggregateDefinition = aggregateDefinition;
1467         }
1468
1469         internal DbAggregate AggregateDefinition;
1470     }
1471
1472     internal sealed class GroupPartitionInfo : GroupAggregateInfo
1473     {
1474         internal GroupPartitionInfo(AST.GroupPartitionExpr groupPartitionExpr, ErrorContext errCtx, GroupAggregateInfo containingAggregate, ScopeRegion definingScopeRegion)
1475             : base(GroupAggregateKind.Partition, groupPartitionExpr, errCtx, containingAggregate, definingScopeRegion)
1476         {
1477             Debug.Assert(groupPartitionExpr != null, "groupPartitionExpr != null");
1478         }
1479
1480         internal void AttachToAstNode(string aggregateName, DbExpression aggregateDefinition)
1481         {
1482             Debug.Assert(aggregateDefinition != null, "aggregateDefinition != null");
1483             base.AttachToAstNode(aggregateName, aggregateDefinition.ResultType);
1484             AggregateDefinition = aggregateDefinition;
1485         }
1486
1487         internal DbExpression AggregateDefinition;
1488     }
1489
1490     internal sealed class GroupKeyAggregateInfo : GroupAggregateInfo
1491     {
1492         internal GroupKeyAggregateInfo(GroupAggregateKind aggregateKind, ErrorContext errCtx, GroupAggregateInfo containingAggregate, ScopeRegion definingScopeRegion)
1493             : base(aggregateKind, null /* there is no AST.GroupAggregateExpression corresponding to the group key */, errCtx, containingAggregate, definingScopeRegion)
1494         { }
1495     }
1496
1497     internal abstract class InlineFunctionInfo
1498     {
1499         internal InlineFunctionInfo(AST.FunctionDefinition functionDef, List<DbVariableReferenceExpression> parameters)
1500         {
1501             FunctionDefAst = functionDef;
1502             Parameters = parameters;
1503         }
1504
1505         internal readonly AST.FunctionDefinition FunctionDefAst;
1506         internal readonly List<DbVariableReferenceExpression> Parameters;
1507
1508         internal abstract DbLambda GetLambda(SemanticResolver sr);
1509     }
1510
1511     internal sealed class ScopeRegion
1512     {
1513         private readonly ScopeManager _scopeManager;
1514
1515         internal ScopeRegion(ScopeManager scopeManager, int firstScopeIndex, int scopeRegionIndex)
1516         {
1517             _scopeManager = scopeManager;
1518             _firstScopeIndex = firstScopeIndex;
1519             _scopeRegionIndex = scopeRegionIndex;
1520         }
1521
1522         /// <summary>
1523         /// First scope of the region.
1524         /// </summary>
1525         internal int FirstScopeIndex
1526         {
1527             get { return _firstScopeIndex; }
1528         }
1529         private readonly int _firstScopeIndex;
1530
1531         /// <summary>
1532         /// Index of the scope region.
1533         /// Outer scope regions have smaller index value than inner scope regions.
1534         /// </summary>
1535         internal int ScopeRegionIndex
1536         {
1537             get { return _scopeRegionIndex; }
1538         }
1539         private readonly int _scopeRegionIndex;
1540
1541         /// <summary>
1542         /// True if given scope is in the current scope region.
1543         /// </summary>
1544         internal bool ContainsScope(int scopeIndex)
1545         {
1546             return (scopeIndex >= _firstScopeIndex);
1547         }
1548
1549         /// <summary>
1550         /// Marks current scope region as performing group/folding operation.
1551         /// </summary>
1552         internal void EnterGroupOperation(DbExpressionBinding groupAggregateBinding)
1553         {
1554             Debug.Assert(!IsAggregating, "Scope region group operation is not reentrant.");
1555             _groupAggregateBinding = groupAggregateBinding;
1556         }
1557         /// <summary>
1558         /// Clears the <see cref="IsAggregating"/> flag on the group scope.
1559         /// </summary>
1560         internal void RollbackGroupOperation()
1561         {
1562             Debug.Assert(IsAggregating, "Scope region must inside group operation in order to leave it.");
1563             _groupAggregateBinding = null;
1564         }
1565         /// <summary>
1566         /// True when the scope region performs group/folding operation.
1567         /// </summary>
1568         internal bool IsAggregating
1569         {
1570             get { return _groupAggregateBinding != null; }
1571         }
1572         internal DbExpressionBinding GroupAggregateBinding
1573         {
1574             get
1575             {
1576                 Debug.Assert(IsAggregating, "IsAggregating must be true.");
1577                 return _groupAggregateBinding;
1578             }
1579         }
1580         private DbExpressionBinding _groupAggregateBinding;
1581
1582         /// <summary>
1583         /// Returns list of group aggregates evaluated on the scope region.
1584         /// </summary>
1585         internal List<GroupAggregateInfo> GroupAggregateInfos
1586         {
1587             get { return _groupAggregateInfos; }
1588         }
1589         private List<GroupAggregateInfo> _groupAggregateInfos = new List<GroupAggregateInfo>();
1590
1591         /// <summary>
1592         /// Adds group aggregate name to the scope region.
1593         /// </summary>
1594         internal void RegisterGroupAggregateName(string groupAggregateName)
1595         {
1596             Debug.Assert(!_groupAggregateNames.Contains(groupAggregateName), "!_groupAggregateNames.ContainsKey(groupAggregateName)");
1597             _groupAggregateNames.Add(groupAggregateName);
1598         }
1599         internal bool ContainsGroupAggregate(string groupAggregateName)
1600         {
1601             return _groupAggregateNames.Contains(groupAggregateName);
1602         }
1603         private HashSet<string> _groupAggregateNames = new HashSet<string>();
1604
1605         /// <summary>
1606         /// True if a recent expression resolution was correlated.
1607         /// </summary>
1608         internal bool WasResolutionCorrelated
1609         {
1610             get { return _wasResolutionCorrelated; }
1611             set { _wasResolutionCorrelated = value; }
1612         }
1613         private bool _wasResolutionCorrelated = false;
1614
1615         /// <summary>
1616         /// Applies <paramref name="action"/> to all scope entries in the current scope region.
1617         /// </summary>
1618         internal void ApplyToScopeEntries(Action<ScopeEntry> action)
1619         {
1620             Debug.Assert(FirstScopeIndex <= _scopeManager.CurrentScopeIndex, "FirstScopeIndex <= CurrentScopeIndex");
1621
1622             for (int i = FirstScopeIndex; i <= _scopeManager.CurrentScopeIndex; ++i)
1623             {
1624                 foreach (KeyValuePair<string, ScopeEntry> scopeEntry in _scopeManager.GetScopeByIndex(i))
1625                 {
1626                     action(scopeEntry.Value);
1627                 }
1628             }
1629         }
1630
1631         /// <summary>
1632         /// Applies <paramref name="action"/> to all scope entries in the current scope region.
1633         /// </summary>
1634         internal void ApplyToScopeEntries(Func<ScopeEntry, ScopeEntry> action)
1635         {
1636             Debug.Assert(FirstScopeIndex <= _scopeManager.CurrentScopeIndex, "FirstScopeIndex <= CurrentScopeIndex");
1637
1638             for (int i = FirstScopeIndex; i <= _scopeManager.CurrentScopeIndex; ++i)
1639             {
1640                 Scope scope = _scopeManager.GetScopeByIndex(i);
1641                 List<KeyValuePair<string, ScopeEntry>> updatedEntries = null;
1642                 foreach (KeyValuePair<string, ScopeEntry> scopeEntry in scope)
1643                 {
1644                     ScopeEntry newScopeEntry = action(scopeEntry.Value);
1645                     Debug.Assert(newScopeEntry != null, "newScopeEntry != null");
1646                     if (scopeEntry.Value != newScopeEntry)
1647                     {
1648                         if (updatedEntries == null)
1649                         {
1650                             updatedEntries = new List<KeyValuePair<string, ScopeEntry>>();
1651                         }
1652                         updatedEntries.Add(new KeyValuePair<string, ScopeEntry>(scopeEntry.Key, newScopeEntry));
1653                     }
1654                 }
1655                 if (updatedEntries != null)
1656                 {
1657                     updatedEntries.ForEach((updatedScopeEntry) => scope.Replace(updatedScopeEntry.Key, updatedScopeEntry.Value));
1658                 }
1659             }
1660         }
1661
1662         internal void RollbackAllScopes()
1663         {
1664             _scopeManager.RollbackToScope(FirstScopeIndex - 1);
1665         }
1666     }
1667
1668     /// <summary>
1669     /// Represents a pair of types to avoid uncessary enumerations to split kvp elements
1670     /// </summary>
1671     internal sealed class Pair<L, R>
1672     {
1673         internal Pair(L left, R right)
1674         {
1675             Left = left;
1676             Right = right;
1677         }
1678
1679         internal L Left;
1680         internal R Right;
1681
1682         internal KeyValuePair<L, R> GetKVP()
1683         {
1684             return new KeyValuePair<L, R>(Left, Right);
1685         }
1686     }
1687 }