mcs/class/referencesource/System.Data.Linq/SqlClient/Query/QueryConverter.cs

   1 using System;
   2 using System.Globalization;
   3 using System.Collections;
   4 using System.Collections.Generic;
   5 using System.Data;
   6 using System.Reflection;
   7 using System.Text;
   8 using System.Linq;
   9 using System.Linq.Expressions;
  10 using System.Data.Linq;
  11 using System.Data.Linq.Mapping;
  12 using System.Data.Linq.Provider;
  13 using System.Collections.ObjectModel;
  14 using System.Diagnostics.CodeAnalysis;
  15
  16 namespace System.Data.Linq.SqlClient {
  17
  18     /// <summary>
  19     /// These are application types used to represent types used during intermediate
  20     /// stages of the query building process.
  21     /// </summary>
  22     enum ConverterSpecialTypes {
  23         Row,
  24         Table
  25     }
  26
  27     [Flags]
  28     internal enum ConverterStrategy {
  29         Default = 0x0,
  30         SkipWithRowNumber = 0x1,
  31         CanUseScopeIdentity = 0x2,
  32         CanUseOuterApply = 0x4,
  33         CanUseRowStatus = 0x8,
  34         CanUseJoinOn = 0x10,  // Whether or not to use ON clause of JOIN.
  35         CanOutputFromInsert = 0x20
  36     }
  37
  38     [SuppressMessage("Microsoft.Maintainability", "CA1506:AvoidExcessiveClassCoupling", Justification="Unknown reason.")]
  39     internal class QueryConverter {
  40         IDataServices services;
  41         Translator translator;
  42         SqlFactory sql;
  43         TypeSystemProvider typeProvider;
  44         bool outerNode;
  45         Dictionary<ParameterExpression, SqlExpression> map;
  46         Dictionary<ParameterExpression, Expression> exprMap;
  47         Dictionary<ParameterExpression, SqlNode> dupMap;
  48         Dictionary<SqlNode, GroupInfo> gmap;
  49         Expression dominatingExpression;
  50         bool allowDeferred;
  51         ConverterStrategy converterStrategy = ConverterStrategy.Default;
  52
  53         class GroupInfo {
  54             internal SqlSelect SelectWithGroup;
  55             internal SqlExpression ElementOnGroupSource;
  56         }
  57
  58         internal ConverterStrategy ConverterStrategy {
  59             get { return converterStrategy; }
  60             set { converterStrategy = value; }
  61         }
  62
  63         private bool UseConverterStrategy(ConverterStrategy strategy) {
  64             return (this.converterStrategy & strategy) == strategy;
  65         }
  66
  67         internal QueryConverter(IDataServices services, TypeSystemProvider typeProvider, Translator translator, SqlFactory sql) {
  68             if (services == null) {
  69                 throw Error.ArgumentNull("services");
  70             }
  71             if (sql == null) {
  72                 throw Error.ArgumentNull("sql");
  73             }
  74             if (translator == null) {
  75                 throw Error.ArgumentNull("translator");
  76             }
  77             if (typeProvider == null) {
  78                 throw Error.ArgumentNull("typeProvider");
  79             }
  80             this.services = services;
  81             this.translator = translator;
  82             this.sql = sql;
  83             this.typeProvider = typeProvider;
  84             this.map = new Dictionary<ParameterExpression, SqlExpression>();
  85             this.exprMap = new Dictionary<ParameterExpression, Expression>();
  86             this.dupMap = new Dictionary<ParameterExpression, SqlNode>();
  87             this.gmap = new Dictionary<SqlNode, GroupInfo>();
  88             this.allowDeferred = true;
  89         }
  90
  91         /// <summary>
  92         /// Convert inner expression from C# expression to basic SQL Query.
  93         /// </summary>
  94         /// <param name="node">The expression to convert.</param>
  95         /// <returns>The converted SQL query.</returns>
  96         internal SqlNode ConvertOuter(Expression node) {
  97             this.dominatingExpression = node;
  98             this.outerNode = true;
  99             SqlNode retNode;
 100             if (typeof(ITable).IsAssignableFrom(node.Type)) {
 101                 retNode = this.VisitSequence(node);
 102             }
 103             else {
 104                 retNode = this.VisitInner(node);
 105             }
 106
 107             if (retNode.NodeType == SqlNodeType.MethodCall) {
 108                 // if a tree consists of a single method call expression only, that method
 109                 // must be either a mapped stored procedure or a mapped function
 110                 throw Error.InvalidMethodExecution(((SqlMethodCall)retNode).Method.Name);
 111             }
 112
 113             // if after conversion the node is an expression, we must
 114             // wrap it in a select
 115             SqlExpression sqlExpression = retNode as SqlExpression;
 116             if (sqlExpression != null) {
 117                 retNode = new SqlSelect(sqlExpression, null, this.dominatingExpression);
 118             }
 119             retNode = new SqlIncludeScope(retNode, this.dominatingExpression);
 120             return retNode;
 121         }
 122
 123         internal SqlNode Visit(Expression node) {
 124             bool tempOuterNode = this.outerNode;
 125             this.outerNode = false;
 126             SqlNode result = this.VisitInner(node);
 127             this.outerNode = tempOuterNode;
 128             return result;
 129         }
 130
 131         /// <summary>
 132         /// Convert inner expression from C# expression to basic SQL Query.
 133         /// </summary>
 134         /// <param name="node">The expression to convert.</param>
 135         /// <param name="dominantExpression">Current dominating expression, used for producing meaningful exception text.</param>
 136         /// <returns>The converted SQL query.</returns>
 137         internal SqlNode ConvertInner(Expression node, Expression dominantExpression) {
 138             this.dominatingExpression = dominantExpression;
 139             bool tempOuterNode = this.outerNode;
 140             this.outerNode = false;
 141             SqlNode result = this.VisitInner(node);
 142             this.outerNode = tempOuterNode;
 143             return result;
 144         }
 145
 146         [SuppressMessage("Microsoft.Performance", "CA1800:DoNotCastUnnecessarily", Justification = "Microsoft: Cast is dependent on node type and casts do not happen unecessarily in a single code path.")]
 147         [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity", Justification = "These issues are related to our use of if-then and case statements for node types, which adds to the complexity count however when reviewed they are easy to navigate and understand.")]
 148         private SqlNode VisitInner(Expression node) {
 149             if (node == null) return null;
 150             Expression save = this.dominatingExpression;
 151             this.dominatingExpression = ChooseBestDominatingExpression(this.dominatingExpression, node);
 152
 153             try {
 154                 switch (node.NodeType) {
 155                     case ExpressionType.New:
 156                         return this.VisitNew((NewExpression)node);
 157                     case ExpressionType.MemberInit:
 158                         return this.VisitMemberInit((MemberInitExpression)node);
 159                     case ExpressionType.Negate:
 160                     case ExpressionType.NegateChecked:
 161                     case ExpressionType.Not:
 162                         return this.VisitUnary((UnaryExpression)node);
 163                     case ExpressionType.UnaryPlus:
 164                         if (node.Type == typeof(TimeSpan))
 165                             return this.VisitUnary((UnaryExpression)node);
 166                         throw Error.UnrecognizedExpressionNode(node.NodeType);
 167                     case ExpressionType.Add:
 168                     case ExpressionType.AddChecked:
 169                     case ExpressionType.Subtract:
 170                     case ExpressionType.SubtractChecked:
 171                     case ExpressionType.Multiply:
 172                     case ExpressionType.MultiplyChecked:
 173                     case ExpressionType.Divide:
 174                     case ExpressionType.Modulo:
 175                     case ExpressionType.And:
 176                     case ExpressionType.AndAlso:
 177                     case ExpressionType.Or:
 178                     case ExpressionType.OrElse:
 179                     case ExpressionType.Power:
 180                     case ExpressionType.LessThan:
 181                     case ExpressionType.LessThanOrEqual:
 182                     case ExpressionType.GreaterThan:
 183                     case ExpressionType.GreaterThanOrEqual:
 184                     case ExpressionType.Equal:
 185                     case ExpressionType.NotEqual:
 186                     case ExpressionType.Coalesce:
 187                     case ExpressionType.ExclusiveOr:
 188                         return this.VisitBinary((BinaryExpression)node);
 189                     case ExpressionType.ArrayIndex:
 190                         return this.VisitArrayIndex((BinaryExpression)node);
 191                     case ExpressionType.TypeIs:
 192                         return this.VisitTypeBinary((TypeBinaryExpression)node);
 193                     case ExpressionType.Convert:
 194                     case ExpressionType.ConvertChecked:
 195                         return this.VisitCast((UnaryExpression)node);
 196                     case ExpressionType.TypeAs:
 197                         return this.VisitAs((UnaryExpression)node);
 198                     case ExpressionType.Conditional:
 199                         return this.VisitConditional((ConditionalExpression)node);
 200                     case ExpressionType.Constant:
 201                         return this.VisitConstant((ConstantExpression)node);
 202                     case ExpressionType.Parameter:
 203                         return this.VisitParameter((ParameterExpression)node);
 204                     case ExpressionType.MemberAccess:
 205                         return this.VisitMemberAccess((MemberExpression)node);
 206                     case ExpressionType.Call:
 207                         return this.VisitMethodCall((MethodCallExpression)node);
 208                     case ExpressionType.ArrayLength:
 209                         return this.VisitArrayLength((UnaryExpression)node);
 210                     case ExpressionType.NewArrayInit:
 211                         return this.VisitNewArrayInit((NewArrayExpression)node);
 212                     case ExpressionType.ListInit:
 213                         return this.VisitListInit((ListInitExpression)node);
 214                     case ExpressionType.Quote:
 215                         return this.Visit(((UnaryExpression)node).Operand);
 216                     case ExpressionType.Invoke:
 217                         return this.VisitInvocation((InvocationExpression)node);
 218                     case ExpressionType.Lambda:
 219                         return this.VisitLambda((LambdaExpression)node);
 220                     case ExpressionType.RightShift:
 221                     case ExpressionType.LeftShift:
 222                         throw Error.UnsupportedNodeType(node.NodeType);
 223                     case (ExpressionType)InternalExpressionType.Known:
 224                         return ((KnownExpression)node).Node;
 225                     case (ExpressionType)InternalExpressionType.LinkedTable:
 226                         return this.VisitLinkedTable((LinkedTableExpression)node);
 227                     default:
 228                         throw Error.UnrecognizedExpressionNode(node.NodeType);
 229                 }
 230             }
 231             finally {
 232                 this.dominatingExpression = save;
 233             }
 234         }
 235
 236         /// <summary>
 237         /// Heuristic which chooses the best Expression root to use for displaying user messages
 238         /// and exception text.
 239         /// </summary>
 240         private static Expression ChooseBestDominatingExpression(Expression last, Expression next) {
 241             if (last == null) {
 242                 return next;
 243             }
 244             else if (next == null) {
 245                 return last;
 246             }
 247             else {
 248                 if (next is MethodCallExpression) {
 249                     return next;
 250                 }
 251                 if (last is MethodCallExpression) {
 252                     return last;
 253                 }
 254             }
 255             return next;
 256         }
 257
 258         private SqlSelect LockSelect(SqlSelect sel) {
 259             if (sel.Selection.NodeType != SqlNodeType.AliasRef ||
 260                 sel.Where != null ||
 261                 sel.OrderBy.Count > 0 ||
 262                 sel.GroupBy.Count > 0 ||
 263                 sel.Having != null ||
 264                 sel.Top != null ||
 265                 sel.OrderingType != SqlOrderingType.Default ||
 266                 sel.IsDistinct) {
 267                 SqlAlias alias = new SqlAlias(sel);
 268                 SqlAliasRef aref = new SqlAliasRef(alias);
 269                 return new SqlSelect(aref, alias, this.dominatingExpression);
 270             }
 271             return sel;
 272         }
 273
 274         private SqlSelect VisitSequence(Expression exp) {
 275             return this.CoerceToSequence(this.Visit(exp));
 276         }
 277
 278         private SqlSelect CoerceToSequence(SqlNode node) {
 279             SqlSelect select = node as SqlSelect;
 280             if (select == null) {
 281                 if (node.NodeType == SqlNodeType.Value) {
 282                     SqlValue sv = (SqlValue)node;
 283                     // Check for ITables.
 284                     ITable t = sv.Value as ITable;
 285                     if (t != null) {
 286                         return this.CoerceToSequence(this.TranslateConstantTable(t, null));
 287                     }
 288                     // Check for IQueryable.
 289                     IQueryable query = sv.Value as IQueryable;
 290                     if (query != null) {
 291                         Expression fex = Funcletizer.Funcletize(query.Expression);
 292                         // IQueryables that return self-referencing Constant expressions cause infinite recursion
 293                         if (fex.NodeType != ExpressionType.Constant ||
 294                             ((ConstantExpression)fex).Value != query) {
 295                             return this.VisitSequence(fex);
 296                         }
 297                         throw Error.IQueryableCannotReturnSelfReferencingConstantExpression();
 298                     }
 299                     throw Error.CapturedValuesCannotBeSequences();
 300                 }
 301                 else if (node.NodeType == SqlNodeType.Multiset || node.NodeType == SqlNodeType.Element) {
 302                     return ((SqlSubSelect)node).Select;
 303                 }
 304                 else if (node.NodeType == SqlNodeType.ClientArray) {
 305                     throw Error.ConstructedArraysNotSupported();
 306                 }
 307                 else if (node.NodeType == SqlNodeType.ClientParameter) {
 308                     throw Error.ParametersCannotBeSequences();
 309                 }
 310                 // this needs to be a sequence expression!
 311                 SqlExpression sqlExpr = (SqlExpression)node;
 312                 SqlAlias sa = new SqlAlias(sqlExpr);
 313                 SqlAliasRef aref = new SqlAliasRef(sa);
 314                 return new SqlSelect(aref, sa, this.dominatingExpression);
 315             }
 316             return select;
 317         }
 318
 319         //
 320         // Recursive call to VisitInvocation.
 321         [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining)]
 322         private SqlNode VisitInvocation(InvocationExpression invoke) {
 323             LambdaExpression lambda =
 324                 (invoke.Expression.NodeType == ExpressionType.Quote)
 325                     ? (LambdaExpression)((UnaryExpression)invoke.Expression).Operand
 326                     : (invoke.Expression as LambdaExpression);
 327             if (lambda != null) {
 328                 // just map arg values into lambda's parameters and evaluate lambda's body
 329                 for (int i = 0, n = invoke.Arguments.Count; i < n; i++) {
 330                     this.exprMap[lambda.Parameters[i]] = invoke.Arguments[i];
 331                 }
 332                 return this.VisitInner(lambda.Body);
 333             }
 334             else {
 335                 // check for compiled query invocation
 336                 SqlExpression expr = this.VisitExpression(invoke.Expression);
 337                 if (expr.NodeType == SqlNodeType.Value) {
 338                     SqlValue value = (SqlValue)expr;
 339                     Delegate d = value.Value as Delegate;
 340                     if (d != null) {
 341                         CompiledQuery cq = d.Target as CompiledQuery;
 342                         if (cq != null) {
 343                             return this.VisitInvocation(Expression.Invoke(cq.Expression, invoke.Arguments));
 344                         } else if (invoke.Arguments.Count == 0) {
 345                             object invokeResult;
 346                             try {
 347                                 invokeResult = d.DynamicInvoke(null);
 348                             } catch (System.Reflection.TargetInvocationException e) {
 349                                 throw e.InnerException;
 350                             }
 351                             return this.sql.ValueFromObject(invokeResult, invoke.Type, true, this.dominatingExpression);
 352                         }
 353                     }
 354                 }
 355                 SqlExpression [] args = new SqlExpression[invoke.Arguments.Count];
 356                 for(int i = 0; i<args.Length; ++i) {
 357                     args[i] = (SqlExpression)this.Visit(invoke.Arguments[i]);
 358                 }
 359                 var sca = new SqlClientArray(typeof(object[]), this.typeProvider.From(typeof(object[])), args, this.dominatingExpression);
 360                 return sql.MethodCall(invoke.Type, typeof(Delegate).GetMethod("DynamicInvoke"), expr, new SqlExpression[] {sca}, this.dominatingExpression);
 361             }
 362         }
 363
 364         // inline lambda expressions w/o invocation are parameterized queries
 365         private SqlNode VisitLambda(LambdaExpression lambda) {
 366
 367             // turn lambda parameters into client parameters
 368             for (int i = 0, n = lambda.Parameters.Count; i < n; i++) {
 369                 ParameterExpression p = lambda.Parameters[i];
 370
 371                 if (p.Type == typeof(Type)) {
 372                     throw Error.BadParameterType(p.Type);
 373                 }
 374
 375                 // construct accessor for parameter
 376                 ParameterExpression pa = Expression.Parameter(typeof(object[]), "args");
 377                 LambdaExpression accessor =
 378                     Expression.Lambda(
 379                         typeof(Func<,>).MakeGenericType(typeof(object[]), p.Type),
 380                         Expression.Convert(
 381 #pragma warning disable 618 // Disable the 'obsolete' warning
 382                             Expression.ArrayIndex(pa, Expression.Constant(i)),
 383                             p.Type
 384                             ),
 385 #pragma warning restore 618
 386                         pa
 387                         );
 388
 389                 SqlClientParameter cp = new SqlClientParameter(p.Type, this.typeProvider.From(p.Type), accessor, this.dominatingExpression);
 390
 391                 // map references to lambda's parameter to client parameter node
 392                 this.dupMap[p] = cp;
 393             }
 394
 395             // call this so we don't erase 'outerNode' setting
 396             return this.VisitInner(lambda.Body);
 397         }
 398
 399         private SqlExpression VisitExpression(Expression exp) {
 400             SqlNode result = this.Visit(exp);
 401             if (result == null) return null;
 402             SqlExpression x = result as SqlExpression;
 403             if (x != null) return x;
 404             SqlSelect select = result as SqlSelect;
 405             if (select != null) {
 406                 SqlSubSelect ms = sql.SubSelect(SqlNodeType.Multiset, select, exp.Type);
 407                 return ms;
 408             }
 409             throw Error.UnrecognizedExpressionNode(result);
 410         }
 411
 412         private SqlSelect VisitSelect(Expression sequence, LambdaExpression selector) {
 413             SqlSelect source = this.VisitSequence(sequence);
 414             SqlAlias alias = new SqlAlias(source);
 415             SqlAliasRef aref = new SqlAliasRef(alias);
 416
 417             this.map[selector.Parameters[0]] = aref;
 418             SqlNode project = this.Visit(selector.Body);
 419
 420             SqlSelect pselect = project as SqlSelect;
 421             if (pselect != null) {
 422                 return new SqlSelect(sql.SubSelect(SqlNodeType.Multiset, pselect, selector.Body.Type), alias, this.dominatingExpression);
 423             }
 424             else if ((project.NodeType == SqlNodeType.Element || project.NodeType == SqlNodeType.ScalarSubSelect) &&
 425                      (this.converterStrategy & ConverterStrategy.CanUseOuterApply) != 0) {
 426                 SqlSubSelect sub = (SqlSubSelect)project;
 427                 SqlSelect inner = sub.Select;
 428                 SqlAlias innerAlias = new SqlAlias(inner);
 429                 SqlAliasRef innerRef = new SqlAliasRef(innerAlias);
 430                 if (project.NodeType == SqlNodeType.Element) {
 431                     inner.Selection = new SqlOptionalValue(
 432                         new SqlColumn(
 433                             "test",
 434                             sql.Unary(
 435                                 SqlNodeType.OuterJoinedValue,
 436                                 sql.Value(typeof(int?), this.typeProvider.From(typeof(int)), 1, false, this.dominatingExpression)
 437                                 )
 438                             ),
 439                             sql.Unary(SqlNodeType.OuterJoinedValue, inner.Selection)
 440                         );
 441                 }
 442                 else {
 443                     inner.Selection = sql.Unary(SqlNodeType.OuterJoinedValue, inner.Selection);
 444                 }
 445                 SqlJoin join = new SqlJoin(SqlJoinType.OuterApply, alias, innerAlias, null, this.dominatingExpression);
 446                 return new SqlSelect(innerRef, join, this.dominatingExpression);
 447             }
 448             else {
 449                 SqlExpression expr = project as SqlExpression;
 450                 if (expr != null) {
 451                     return new SqlSelect(expr, alias, this.dominatingExpression);
 452                 }
 453                 else {
 454                     throw Error.BadProjectionInSelect();
 455                 }
 456             }
 457         }
 458
 459         private SqlSelect VisitSelectMany(Expression sequence, LambdaExpression colSelector, LambdaExpression resultSelector) {
 460             SqlSelect seqSelect = this.VisitSequence(sequence);
 461             SqlAlias seqAlias = new SqlAlias(seqSelect);
 462             SqlAliasRef seqRef = new SqlAliasRef(seqAlias);
 463
 464             this.map[colSelector.Parameters[0]] = seqRef;
 465
 466             SqlNode colSelectorNode = this.VisitSequence(colSelector.Body);
 467             SqlAlias selAlias = new SqlAlias(colSelectorNode);
 468             SqlAliasRef selRef = new SqlAliasRef(selAlias);
 469             SqlJoin join = new SqlJoin(SqlJoinType.CrossApply, seqAlias, selAlias, null, this.dominatingExpression);
 470
 471             SqlExpression projection = selRef;
 472
 473             if (resultSelector != null) {
 474                 this.map[resultSelector.Parameters[0]] = seqRef;
 475                 this.map[resultSelector.Parameters[1]] = selRef;
 476                 projection = this.VisitExpression(resultSelector.Body);
 477             }
 478
 479             return new SqlSelect(projection, join, this.dominatingExpression);
 480         }
 481
 482         private SqlSelect VisitJoin(Expression outerSequence, Expression innerSequence, LambdaExpression outerKeySelector, LambdaExpression innerKeySelector, LambdaExpression resultSelector) {
 483             SqlSelect outerSelect = this.VisitSequence(outerSequence);
 484             SqlSelect innerSelect = this.VisitSequence(innerSequence);
 485
 486             SqlAlias outerAlias = new SqlAlias(outerSelect);
 487             SqlAliasRef outerRef = new SqlAliasRef(outerAlias);
 488             SqlAlias innerAlias = new SqlAlias(innerSelect);
 489             SqlAliasRef innerRef = new SqlAliasRef(innerAlias);
 490
 491             this.map[outerKeySelector.Parameters[0]] = outerRef;
 492             SqlExpression outerKey = this.VisitExpression(outerKeySelector.Body);
 493
 494             this.map[innerKeySelector.Parameters[0]] = innerRef;
 495             SqlExpression innerKey = this.VisitExpression(innerKeySelector.Body);
 496
 497             this.map[resultSelector.Parameters[0]] = outerRef;
 498             this.map[resultSelector.Parameters[1]] = innerRef;
 499             SqlExpression result = this.VisitExpression(resultSelector.Body);
 500
 501             SqlExpression condition = sql.Binary(SqlNodeType.EQ, outerKey, innerKey);
 502             SqlSelect select = null;
 503             if ((this.converterStrategy & ConverterStrategy.CanUseJoinOn) != 0) {
 504                 SqlJoin join = new SqlJoin(SqlJoinType.Inner, outerAlias, innerAlias, condition, this.dominatingExpression);
 505                 select = new SqlSelect(result, join, this.dominatingExpression);
 506             } else {
 507                 SqlJoin join = new SqlJoin(SqlJoinType.Cross, outerAlias, innerAlias, null, this.dominatingExpression);
 508                 select = new SqlSelect(result, join, this.dominatingExpression);
 509                 select.Where = condition;
 510             }
 511             return select;
 512         }
 513
 514         private SqlSelect VisitGroupJoin(Expression outerSequence, Expression innerSequence, LambdaExpression outerKeySelector, LambdaExpression innerKeySelector, LambdaExpression resultSelector) {
 515             SqlSelect outerSelect = this.VisitSequence(outerSequence);
 516             SqlSelect innerSelect = this.VisitSequence(innerSequence);
 517
 518             SqlAlias outerAlias = new SqlAlias(outerSelect);
 519             SqlAliasRef outerRef = new SqlAliasRef(outerAlias);
 520             SqlAlias innerAlias = new SqlAlias(innerSelect);
 521             SqlAliasRef innerRef = new SqlAliasRef(innerAlias);
 522
 523             this.map[outerKeySelector.Parameters[0]] = outerRef;
 524             SqlExpression outerKey = this.VisitExpression(outerKeySelector.Body);
 525
 526             this.map[innerKeySelector.Parameters[0]] = innerRef;
 527             SqlExpression innerKey = this.VisitExpression(innerKeySelector.Body);
 528
 529             // make multiset
 530             SqlExpression pred = sql.Binary(SqlNodeType.EQ, outerKey, innerKey);
 531             SqlSelect select = new SqlSelect(innerRef, innerAlias, this.dominatingExpression);
 532             select.Where = pred;
 533             SqlSubSelect subquery = sql.SubSelect(SqlNodeType.Multiset, select);
 534
 535             // make outer ref & multiset for result-selector params
 536             this.map[resultSelector.Parameters[0]] = outerRef;
 537             this.dupMap[resultSelector.Parameters[1]] = subquery;
 538             SqlExpression result = this.VisitExpression(resultSelector.Body);
 539
 540             return new SqlSelect(result, outerAlias, this.dominatingExpression);
 541         }
 542
 543         private SqlSelect VisitDefaultIfEmpty(Expression sequence) {
 544             SqlSelect select = this.VisitSequence(sequence);
 545             SqlAlias alias = new SqlAlias(select);
 546             SqlAliasRef aliasRef = new SqlAliasRef(alias);
 547
 548             SqlExpression opt = new SqlOptionalValue(
 549                 new SqlColumn(
 550                     "test",
 551                     sql.Unary(SqlNodeType.OuterJoinedValue,
 552                         sql.Value(typeof(int?), this.typeProvider.From(typeof(int)), 1, false, this.dominatingExpression)
 553                         )
 554                     ),
 555                     sql.Unary(SqlNodeType.OuterJoinedValue, aliasRef)
 556                 );
 557             SqlSelect optSelect = new SqlSelect(opt, alias, this.dominatingExpression);
 558
 559             alias = new SqlAlias(optSelect);
 560             aliasRef = new SqlAliasRef(alias);
 561
 562             SqlExpression litNull = sql.TypedLiteralNull(typeof(string), this.dominatingExpression);
 563             SqlSelect selNull = new SqlSelect(litNull, null, this.dominatingExpression);
 564             SqlAlias aliasNull = new SqlAlias(selNull);
 565
 566             SqlJoin join = new SqlJoin(SqlJoinType.OuterApply, aliasNull, alias, null, this.dominatingExpression);
 567
 568             return new SqlSelect(aliasRef, join, this.dominatingExpression);
 569         }
 570
 571         /// <summary>
 572         /// Rewrite seq.OfType<T> as seq.Select(s=>s as T).Where(p=>p!=null).
 573         /// </summary>
 574         private SqlSelect VisitOfType(Expression sequence, Type ofType) {
 575             SqlSelect select = this.LockSelect(this.VisitSequence(sequence));
 576             SqlAliasRef aref = (SqlAliasRef)select.Selection;
 577
 578             select.Selection = new SqlUnary(SqlNodeType.Treat, ofType, typeProvider.From(ofType), aref, this.dominatingExpression);
 579
 580             select = this.LockSelect(select);
 581             aref = (SqlAliasRef)select.Selection;
 582
 583             // Append the 'is' operator into the WHERE clause.
 584             select.Where = sql.AndAccumulate(select.Where,
 585                     sql.Unary(SqlNodeType.IsNotNull, aref, this.dominatingExpression)
 586                 );
 587
 588             return select;
 589         }
 590
 591         /// <summary>
 592         /// Rewrite seq.Cast<T> as seq.Select(s=>(T)s).
 593         /// </summary>
 594         private SqlNode VisitSequenceCast(Expression sequence, Type type) {
 595             Type sourceType = TypeSystem.GetElementType(sequence.Type);
 596             ParameterExpression p = Expression.Parameter(sourceType, "pc");
 597             return this.Visit(Expression.Call(
 598                 typeof(Enumerable), "Select",
 599                 new Type[] {
 600                     sourceType, // TSource element type.
 601                     type, // TResult element type.
 602                 },
 603                 sequence,
 604                 Expression.Lambda(
 605                     Expression.Convert(p, type),
 606                     new ParameterExpression[] { p }
 607                 ))
 608            );
 609         }
 610
 611         /// <summary>
 612         /// This is the 'is' operator.
 613         /// </summary>
 614         private SqlNode VisitTypeBinary(TypeBinaryExpression b) {
 615             SqlExpression expr = this.VisitExpression(b.Expression);
 616             SqlExpression result = null;
 617             switch (b.NodeType) {
 618                 case ExpressionType.TypeIs:
 619                     Type ofType = b.TypeOperand;
 620                     result = sql.Unary(SqlNodeType.IsNotNull, new SqlUnary(SqlNodeType.Treat, ofType, typeProvider.From(ofType), expr, this.dominatingExpression), this.dominatingExpression);
 621                     break;
 622                 default:
 623                     throw Error.TypeBinaryOperatorNotRecognized();
 624             }
 625             return result;
 626         }
 627         private SqlSelect VisitWhere(Expression sequence, LambdaExpression predicate) {
 628             SqlSelect select = this.LockSelect(this.VisitSequence(sequence));
 629
 630             this.map[predicate.Parameters[0]] = (SqlAliasRef)select.Selection;
 631
 632             select.Where = this.VisitExpression(predicate.Body);
 633             return select;
 634         }
 635
 636         private SqlNode VisitAs(UnaryExpression a) {
 637             SqlNode node = this.Visit(a.Operand);
 638             SqlExpression expr = node as SqlExpression;
 639             if (expr != null) {
 640                 return new SqlUnary(SqlNodeType.Treat, a.Type, typeProvider.From(a.Type), expr, a);
 641             }
 642             SqlSelect select = node as SqlSelect;
 643             if (select != null) {
 644                 SqlSubSelect ms = sql.SubSelect(SqlNodeType.Multiset, select);
 645                 return new SqlUnary(SqlNodeType.Treat, a.Type, typeProvider.From(a.Type), ms, a);
 646             }
 647             throw Error.DidNotExpectAs(a);
 648         }
 649
 650         private SqlNode VisitArrayLength(UnaryExpression c) {
 651             SqlExpression exp = this.VisitExpression(c.Operand);
 652
 653             if (exp.SqlType.IsString || exp.SqlType.IsChar) {
 654                 return sql.CLRLENGTH(exp);
 655             }
 656             else {
 657                 return sql.DATALENGTH(exp);
 658             }
 659         }
 660
 661         private SqlNode VisitArrayIndex(BinaryExpression b) {
 662             SqlExpression array = this.VisitExpression(b.Left);
 663             SqlExpression index = this.VisitExpression(b.Right);
 664
 665             if (array.NodeType == SqlNodeType.ClientParameter
 666                 && index.NodeType == SqlNodeType.Value) {
 667                 SqlClientParameter cpArray = (SqlClientParameter)array;
 668                 SqlValue vIndex = (SqlValue)index;
 669                 return new SqlClientParameter(
 670                        b.Type, sql.TypeProvider.From(b.Type),
 671                        Expression.Lambda(
 672 #pragma warning disable 618 // Disable the 'obsolete' warning
 673                            Expression.ArrayIndex(cpArray.Accessor.Body, Expression.Constant(vIndex.Value, vIndex.ClrType)),
 674 #pragma warning restore 618
 675                            cpArray.Accessor.Parameters.ToArray()
 676                        ),
 677
 678                        this.dominatingExpression
 679                        );
 680             }
 681
 682             throw Error.UnrecognizedExpressionNode(b.NodeType);
 683         }
 684
 685         private SqlNode VisitCast(UnaryExpression c) {
 686             if (c.Method != null) {
 687                 SqlExpression exp = this.VisitExpression(c.Operand);
 688                 return sql.MethodCall(c.Type, c.Method, null, new SqlExpression[] { exp }, dominatingExpression);
 689             }
 690             return this.VisitChangeType(c.Operand, c.Type);
 691         }
 692
 693         private SqlNode VisitChangeType(Expression expression, Type type) {
 694             SqlExpression expr = this.VisitExpression(expression);
 695             return this.ChangeType(expr, type);
 696         }
 697
 698         private SqlNode ConvertDateToDateTime2(SqlExpression expr) {
 699             SqlExpression datetime2 = new SqlVariable(expr.ClrType, expr.SqlType, "DATETIME2", expr.SourceExpression);
 700             return sql.FunctionCall(typeof(DateTime), "CONVERT", new SqlExpression[2] { datetime2, expr }, expr.SourceExpression);
 701         }
 702
 703         private SqlNode ChangeType(SqlExpression expr, Type type) {
 704             if (type == typeof(object)) {
 705                 return expr; // Boxing conversion?
 706             }
 707             else if (expr.NodeType == SqlNodeType.Value && ((SqlValue)expr).Value == null) {
 708                 return sql.TypedLiteralNull(type, expr.SourceExpression);
 709             }
 710             else if (expr.NodeType == SqlNodeType.ClientParameter) {
 711                 SqlClientParameter cp = (SqlClientParameter)expr;
 712                 return new SqlClientParameter(
 713                         type, sql.TypeProvider.From(type),
 714                         Expression.Lambda(Expression.Convert(cp.Accessor.Body, type), cp.Accessor.Parameters.ToArray()),
 715                         cp.SourceExpression
 716                         );
 717             }
 718
 719             ConversionMethod cm = ChooseConversionMethod(expr.ClrType, type);
 720             switch (cm) {
 721                 case ConversionMethod.Convert:
 722                     return sql.UnaryConvert(type, typeProvider.From(type), expr, expr.SourceExpression);
 723                 case ConversionMethod.Lift:
 724                     if (SqlFactory.IsSqlDateType(expr)) {
 725                         expr = (SqlExpression) ConvertDateToDateTime2(expr);
 726                     }
 727                     return new SqlLift(type, expr, this.dominatingExpression);
 728                 case ConversionMethod.Ignore:
 729                     if (SqlFactory.IsSqlDateType(expr)) {
 730                         return ConvertDateToDateTime2(expr);
 731                     }
 732                     return expr;
 733                 case ConversionMethod.Treat:
 734                     return new SqlUnary(SqlNodeType.Treat, type, typeProvider.From(type), expr, expr.SourceExpression);
 735                 default:
 736                     throw Error.UnhandledExpressionType(cm);
 737             }
 738         }
 739
 740         enum ConversionMethod {
 741             Treat,
 742             Ignore,
 743             Convert,
 744             Lift
 745         }
 746
 747         private ConversionMethod ChooseConversionMethod(Type fromType, Type toType) {
 748             Type nnFromType = TypeSystem.GetNonNullableType(fromType);
 749             Type nnToType = TypeSystem.GetNonNullableType(toType);
 750
 751             if (fromType != toType && nnFromType == nnToType) {
 752                 return ConversionMethod.Lift;
 753             }
 754             else if (TypeSystem.IsSequenceType(nnFromType) || TypeSystem.IsSequenceType(nnToType)) {
 755                 return ConversionMethod.Ignore;
 756             }
 757
 758             ProviderType sfromType = typeProvider.From(nnFromType);
 759             ProviderType stoType = typeProvider.From(nnToType);
 760
 761             bool isRuntimeOnly1 = sfromType.IsRuntimeOnlyType;
 762             bool isRuntimeOnly2 = stoType.IsRuntimeOnlyType;
 763
 764             if (isRuntimeOnly1 || isRuntimeOnly2) {
 765                 return ConversionMethod.Treat;
 766             }
 767
 768             if (nnFromType == nnToType                                  // same non-nullable .NET types
 769                 || (sfromType.IsString && sfromType.Equals(stoType))    // same SQL string types
 770                 || (nnFromType.IsEnum || nnToType.IsEnum)               // any .NET enum type
 771                 ) {
 772                 return ConversionMethod.Ignore;
 773             }
 774             else {
 775                 return ConversionMethod.Convert;
 776             }
 777         }
 778
 779         /// <summary>
 780         /// Convert ITable into SqlNodes. If the hierarchy involves inheritance then
 781         /// a type case is built. Abstractly, a type case is a CASE where each WHEN is a possible
 782         /// a typebinding that may be instantianted.
 783         /// </summary>
 784         private SqlNode TranslateConstantTable(ITable table, SqlLink link) {
 785             if (table.Context != this.services.Context) {
 786                 throw Error.WrongDataContext();
 787             }
 788             MetaTable metaTable = this.services.Model.GetTable(table.ElementType);
 789             return this.translator.BuildDefaultQuery(metaTable.RowType, this.allowDeferred, link, this.dominatingExpression);
 790         }
 791
 792         private SqlNode VisitLinkedTable(LinkedTableExpression linkedTable) {
 793             return TranslateConstantTable(linkedTable.Table, linkedTable.Link);
 794         }
 795
 796         private SqlNode VisitConstant(ConstantExpression cons) {
 797             // A value constant or null.
 798             Type type = cons.Type;
 799             if (cons.Value == null) {
 800                 return sql.TypedLiteralNull(type, this.dominatingExpression);
 801             }
 802             if (type == typeof(object)) {
 803                 type = cons.Value.GetType();
 804             }
 805             return sql.ValueFromObject(cons.Value, type, true, this.dominatingExpression);
 806         }
 807
 808         private SqlExpression VisitConditional(ConditionalExpression cond) {
 809             List<SqlWhen> whens = new List<SqlWhen>(1);
 810             whens.Add(new SqlWhen(this.VisitExpression(cond.Test), this.VisitExpression(cond.IfTrue)));
 811             SqlExpression @else = this.VisitExpression(cond.IfFalse);
 812             // combine search cases found in the else clause into a single seach case
 813             while (@else.NodeType == SqlNodeType.SearchedCase) {
 814                 SqlSearchedCase sc = (SqlSearchedCase)@else;
 815                 whens.AddRange(sc.Whens);
 816                 @else = sc.Else;
 817             }
 818             return sql.SearchedCase(whens.ToArray(), @else, this.dominatingExpression);
 819         }
 820
 821         private SqlExpression VisitNew(NewExpression qn) {
 822             if (TypeSystem.IsNullableType(qn.Type) && qn.Arguments.Count == 1 &&
 823                 TypeSystem.GetNonNullableType(qn.Type) == qn.Arguments[0].Type) {
 824                 return this.VisitCast(Expression.Convert(qn.Arguments[0], qn.Type)) as SqlExpression;
 825             }
 826             else if (qn.Type == typeof(decimal) && qn.Arguments.Count == 1) {
 827                 return this.VisitCast(Expression.Convert(qn.Arguments[0], typeof(decimal))) as SqlExpression;
 828             }
 829
 830             MetaType mt = this.services.Model.GetMetaType(qn.Type);
 831             if (mt.IsEntity) {
 832                 throw Error.CannotMaterializeEntityType(qn.Type);
 833             }
 834
 835
 836             SqlExpression[] args = null;
 837
 838             if (qn.Arguments.Count > 0) {
 839                 args = new SqlExpression[qn.Arguments.Count];
 840                 for (int i = 0, n = qn.Arguments.Count; i < n; i++) {
 841                     args[i] = this.VisitExpression(qn.Arguments[i]);
 842                 }
 843             }
 844
 845             SqlNew tb = sql.New(mt, qn.Constructor, args, PropertyOrFieldOf(qn.Members), null, this.dominatingExpression);
 846             return tb;
 847         }
 848
 849         private SqlExpression VisitMemberInit(MemberInitExpression init) {
 850             MetaType mt = this.services.Model.GetMetaType(init.Type);
 851             if (mt.IsEntity) {
 852                 throw Error.CannotMaterializeEntityType(init.Type);
 853             }
 854             SqlExpression[] args = null;
 855
 856             NewExpression qn = init.NewExpression;
 857
 858             if (qn.Type == typeof(decimal) && qn.Arguments.Count == 1) {
 859                 return this.VisitCast(Expression.Convert(qn.Arguments[0], typeof(decimal))) as SqlExpression;
 860             }
 861
 862             if (qn.Arguments.Count > 0) {
 863                 args = new SqlExpression[qn.Arguments.Count];
 864                 for (int i = 0, n = args.Length; i < n; i++) {
 865                     args[i] = this.VisitExpression(qn.Arguments[i]);
 866                 }
 867             }
 868
 869             int cBindings = init.Bindings.Count;
 870             SqlMemberAssign[] members = new SqlMemberAssign[cBindings];
 871             int[] ordinal = new int[members.Length];
 872             for (int i = 0; i < cBindings; i++) {
 873                 MemberAssignment mb = init.Bindings[i] as MemberAssignment;
 874                 if (mb != null) {
 875                     SqlExpression expr = this.VisitExpression(mb.Expression);
 876                     SqlMemberAssign sma = new SqlMemberAssign(mb.Member, expr);
 877                     members[i] = sma;
 878                     ordinal[i] = mt.GetDataMember(mb.Member).Ordinal;
 879                 }
 880                 else {
 881                     throw Error.UnhandledBindingType(init.Bindings[i].BindingType);
 882                 }
 883             }
 884             // put members in type's declaration order
 885             Array.Sort(ordinal, members, 0, members.Length);
 886
 887             SqlNew tb = sql.New(mt, qn.Constructor, args, PropertyOrFieldOf(qn.Members), members, this.dominatingExpression);
 888             return tb;
 889         }
 890
 891         private static IEnumerable<MemberInfo> PropertyOrFieldOf(IEnumerable<MemberInfo> members) {
 892             if (members == null) {
 893                 return null;
 894             }
 895             List<MemberInfo> result = new List<MemberInfo>();
 896             foreach (MemberInfo mi in members) {
 897                 switch (mi.MemberType) {
 898                     case MemberTypes.Method: {
 899                             foreach (PropertyInfo pi in mi.DeclaringType.GetProperties(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic)) {
 900                                 MethodInfo method = mi as MethodInfo;
 901                                 if (pi.CanRead && pi.GetGetMethod() == method) {
 902                                     result.Add(pi);
 903                                     break;
 904                                 }
 905                             }
 906                             break;
 907                         }
 908                     case MemberTypes.Field:
 909                     case MemberTypes.Property: {
 910                             result.Add(mi);
 911                             break;
 912                         }
 913                     default: {
 914                             throw Error.CouldNotConvertToPropertyOrField(mi);
 915                     }
 916                 }
 917             }
 918             return result;
 919         }
 920
 921         private SqlSelect VisitDistinct(Expression sequence) {
 922             SqlSelect select = this.LockSelect(this.VisitSequence(sequence));
 923             select.IsDistinct = true;
 924             select.OrderingType = SqlOrderingType.Blocked;
 925             return select;
 926         }
 927
 928         private SqlSelect VisitTake(Expression sequence, Expression count) {
 929             // verify that count >= 0
 930             SqlExpression takeExp = this.VisitExpression(count);
 931             if (takeExp.NodeType == SqlNodeType.Value) {
 932                 SqlValue constTakeCount = (SqlValue)takeExp;
 933                 if (typeof(int).IsAssignableFrom(constTakeCount.Value.GetType()) && ((int)constTakeCount.Value) < 0) {
 934                     throw Error.ArgumentOutOfRange("takeCount");
 935                 }
 936             }
 937
 938             MethodCallExpression mce = sequence as MethodCallExpression;
 939             if (mce != null && IsSequenceOperatorCall(mce) && mce.Method.Name == "Skip" && mce.Arguments.Count == 2) {
 940                 SqlExpression skipExp = this.VisitExpression(mce.Arguments[1]);
 941
 942                 // verify that count >= 0
 943                 if (skipExp.NodeType == SqlNodeType.Value) {
 944                     SqlValue constSkipCount = (SqlValue)skipExp;
 945                     if (typeof(int).IsAssignableFrom(constSkipCount.Value.GetType()) && ((int)constSkipCount.Value) < 0) {
 946                         throw Error.ArgumentOutOfRange("skipCount");
 947                     }
 948                 }
 949
 950                 SqlSelect select = this.VisitSequence(mce.Arguments[0]);
 951                 return this.GenerateSkipTake(select, skipExp, takeExp);
 952             }
 953             else {
 954                 SqlSelect select = this.VisitSequence(sequence);
 955                 return this.GenerateSkipTake(select, null, takeExp);
 956             }
 957         }
 958
 959         /// <summary>
 960         /// In order for elements of a sequence to be skipped, they must have identity
 961         /// that can be compared.  This excludes elements that are sequences and elements
 962         /// that contain sequences.
 963         /// </summary>
 964         private bool CanSkipOnSelection(SqlExpression selection) {
 965             // we can skip over groupings (since we can compare them by key)
 966             if (IsGrouping(selection.ClrType)) {
 967                 return true;
 968             }
 969             // we can skip over entities (since we can compare them by primary key)
 970             MetaTable table = this.services.Model.GetTable(selection.ClrType);
 971             if (table != null) {
 972                 return true;
 973             }
 974             // sequences that are not primitives are not skippable
 975             if (TypeSystem.IsSequenceType(selection.ClrType) && !selection.SqlType.CanBeColumn) {
 976                 return false;
 977             }
 978             switch (selection.NodeType) {
 979                 case SqlNodeType.AliasRef: {
 980                         SqlNode node = ((SqlAliasRef)selection).Alias.Node;
 981                         SqlSelect select = node as SqlSelect;
 982                         if (select != null) {
 983                             return CanSkipOnSelection(select.Selection);
 984                         }
 985                         SqlUnion union = node as SqlUnion;
 986                         if (union != null) {
 987                             bool left = default(bool);
 988                             bool right = default(bool);
 989
 990                             SqlSelect selectLeft = union.Left as SqlSelect;
 991                             if (selectLeft != null) {
 992                                 left = CanSkipOnSelection(selectLeft.Selection);
 993                             }
 994
 995                             SqlSelect selectRight = union.Right as SqlSelect;
 996                             if (selectRight != null) {
 997                                 right = CanSkipOnSelection(selectRight.Selection);
 998                             }
 999
1000                             return left && right;
1001                         }
1002                         SqlExpression expr = (SqlExpression)node;
1003                         return CanSkipOnSelection(expr);
1004                     }
1005                 case SqlNodeType.New:
1006                     SqlNew sn = (SqlNew)selection;
1007                     // check each member of the projection for sequences
1008                     foreach (SqlMemberAssign ma in sn.Members) {
1009                         if (!CanSkipOnSelection(ma.Expression))
1010                             return false;
1011                     }
1012                     if (sn.ArgMembers != null) {
1013                         for (int i = 0, n = sn.ArgMembers.Count; i < n; ++i) {
1014                             if (!CanSkipOnSelection(sn.Args[i])) {
1015                                 return false;
1016                             }
1017                         }
1018                     }
1019                     break;
1020             }
1021             return true;
1022         }
1023
1024         /// <summary>
1025         /// SQL2000:
1026         ///          SELECT *
1027         ///          FROM sequence
1028         ///          WHERE NOT EXISTS (
1029         ///             SELECT TOP count *
1030         ///             FROM sequence)
1031         ///
1032         /// SQL2005: SELECT *
1033         ///          FROM (SELECT sequence.*,
1034         ///                ROW_NUMBER() OVER (ORDER BY order) AS ROW_NUMBER
1035         ///                FROM sequence)
1036         ///          WHERE ROW_NUMBER > count
1037         /// </summary>
1038         /// <param name="sequence">Sequence containing elements to skip</param>
1039         /// <param name="count">Number of elements to skip</param>
1040         /// <returns>SELECT node</returns>
1041         private SqlSelect VisitSkip(Expression sequence, Expression skipCount) {
1042             SqlExpression skipExp = this.VisitExpression(skipCount);
1043
1044             // verify that count >= 0
1045             if (skipExp.NodeType == SqlNodeType.Value) {
1046                 SqlValue constSkipCount = (SqlValue)skipExp;
1047                 if (typeof(int).IsAssignableFrom(constSkipCount.Value.GetType()) && ((int)constSkipCount.Value) < 0) {
1048                     throw Error.ArgumentOutOfRange("skipCount");
1049                 }
1050             }
1051
1052             SqlSelect select = this.VisitSequence(sequence);
1053             return this.GenerateSkipTake(select, skipExp, null);
1054         }
1055
1056         private SqlSelect GenerateSkipTake(SqlSelect sequence, SqlExpression skipExp, SqlExpression takeExp) {
1057             SqlSelect select = this.LockSelect(sequence);
1058
1059             // no skip?
1060             if (skipExp == null) {
1061                 if (takeExp != null) {
1062                     select.Top = takeExp;
1063                 }
1064                 return select;
1065             }
1066
1067             SqlAlias alias = new SqlAlias(select);
1068             SqlAliasRef aref = new SqlAliasRef(alias);
1069
1070             if (this.UseConverterStrategy(ConverterStrategy.SkipWithRowNumber)) {
1071                 // use ROW_NUMBER() (preferred)
1072                 SqlColumn rowNumber = new SqlColumn("ROW_NUMBER", sql.RowNumber(new List<SqlOrderExpression>(), this.dominatingExpression));
1073                 SqlColumnRef rowNumberRef = new SqlColumnRef(rowNumber);
1074
1075                 select.Row.Columns.Add(rowNumber);
1076
1077                 SqlSelect final = new SqlSelect(aref, alias, this.dominatingExpression);
1078
1079                 if (takeExp != null) {
1080                     // use BETWEEN for skip+take combo (much faster)
1081                     final.Where = sql.Between(
1082                         rowNumberRef,
1083                         sql.Add(skipExp, 1),
1084                         sql.Binary(SqlNodeType.Add, (SqlExpression)SqlDuplicator.Copy(skipExp), takeExp),
1085                         this.dominatingExpression
1086                         );
1087                 }
1088                 else {
1089                     final.Where = sql.Binary(SqlNodeType.GT, rowNumberRef, skipExp);
1090                 }
1091
1092                 return final;
1093             }
1094             else {
1095                 // Ensure that the sequence contains elements that can be skipped
1096                 if (!CanSkipOnSelection(select.Selection)) {
1097                     throw Error.SkipNotSupportedForSequenceTypes();
1098                 }
1099
1100                 // use NOT EXISTS
1101
1102                 // Supported cases:
1103                 //  - Entities
1104                 //  - Projections that contain all PK columns
1105                 //
1106                 // .. where there sequence can be traced back to a:
1107                 //  - Single-table query
1108                 //  - Distinct
1109                 //  - Except
1110                 //  - Intersect
1111                 //  - Union, where union.All == false
1112
1113                 // Not supported: joins
1114
1115                 // Sequence should also be ordered, but we can't test for it at this
1116                 // point in processing, and we won't know that we need to test it, later.
1117
1118                 SingleTableQueryVisitor stqv = new SingleTableQueryVisitor();
1119                 stqv.Visit(select);
1120                 if (!stqv.IsValid) {
1121                     throw Error.SkipRequiresSingleTableQueryWithPKs();
1122                 }
1123
1124                 SqlSelect dupsel = (SqlSelect)SqlDuplicator.Copy(select);
1125                 dupsel.Top = skipExp;
1126
1127                 SqlAlias dupAlias = new SqlAlias(dupsel);
1128                 SqlAliasRef dupRef = new SqlAliasRef(dupAlias);
1129
1130                 SqlSelect eqsel = new SqlSelect(dupRef, dupAlias, this.dominatingExpression);
1131                 eqsel.Where = sql.Binary(SqlNodeType.EQ2V, aref, dupRef);
1132                 SqlSubSelect ss = sql.SubSelect(SqlNodeType.Exists, eqsel);
1133
1134                 SqlSelect final = new SqlSelect(aref, alias, this.dominatingExpression);
1135                 final.Where = sql.Unary(SqlNodeType.Not, ss, this.dominatingExpression);
1136                 final.Top = takeExp;
1137
1138                 return final;
1139             }
1140         }
1141
1142         private SqlNode VisitParameter(ParameterExpression p) {
1143             SqlExpression sqlExpr;
1144             if (this.map.TryGetValue(p, out sqlExpr))
1145                 return sqlExpr;
1146             Expression expr;
1147             if (this.exprMap.TryGetValue(p, out expr))
1148                 return this.Visit(expr);
1149             SqlNode nodeToDup;
1150             if (this.dupMap.TryGetValue(p, out nodeToDup)) {
1151                 SqlDuplicator duplicator = new SqlDuplicator(true);
1152                 return duplicator.Duplicate(nodeToDup);
1153             }
1154             throw Error.ParameterNotInScope(p.Name);
1155         }
1156
1157         /// <summary>
1158         /// Translate a call to a table valued function expression into a sql select.
1159         /// </summary>
1160         private SqlNode TranslateTableValuedFunction(MethodCallExpression mce, MetaFunction function) {
1161             // translate method call into sql function call
1162             List<SqlExpression> sqlParams = GetFunctionParameters(mce, function);
1163             SqlTableValuedFunctionCall functionCall = sql.TableValuedFunctionCall(function.ResultRowTypes[0].InheritanceRoot, mce.Method.ReturnType, function.MappedName, sqlParams, mce);
1164
1165             SqlAlias alias = new SqlAlias(functionCall);
1166             SqlAliasRef aref = new SqlAliasRef(alias);
1167
1168             // Build default projection
1169             SqlExpression projection = this.translator.BuildProjection(aref, function.ResultRowTypes[0].InheritanceRoot, this.allowDeferred, null, mce);
1170
1171             SqlSelect select = new SqlSelect(projection, alias, mce);
1172             return select;
1173         }
1174
1175         /// <summary>
1176         /// Translate a call to a stored procedure
1177         /// </summary>
1178         private SqlNode TranslateStoredProcedureCall(MethodCallExpression mce, MetaFunction function) {
1179             if (!this.outerNode) {
1180                 throw Error.SprocsCannotBeComposed();
1181             }
1182
1183             // translate method call into sql function call
1184             List<SqlExpression> sqlParams = GetFunctionParameters(mce, function);
1185
1186             SqlStoredProcedureCall spc = new SqlStoredProcedureCall(function, null, sqlParams, mce);
1187
1188             Type returnType = mce.Method.ReturnType;
1189             if (returnType.IsGenericType &&
1190                 (returnType.GetGenericTypeDefinition() == typeof(IEnumerable<>) ||
1191                 returnType.GetGenericTypeDefinition() == typeof(ISingleResult<>))) {
1192
1193                 // Since this is a single rowset returning sproc, we use the one
1194                 // and only root metatype.
1195                 MetaType rowType = function.ResultRowTypes[0].InheritanceRoot;
1196
1197                 SqlUserRow rowExp = new SqlUserRow(rowType, this.typeProvider.GetApplicationType((int)ConverterSpecialTypes.Row), spc, mce);
1198                 spc.Projection = this.translator.BuildProjection(rowExp, rowType, this.allowDeferred, null, mce);
1199             }
1200             else if (!(
1201                 typeof(IMultipleResults).IsAssignableFrom(returnType)
1202                 || returnType == typeof(int)
1203                 || returnType == typeof(int?)
1204                 )) {
1205                 throw Error.InvalidReturnFromSproc(returnType);
1206             }
1207
1208             return spc;
1209         }
1210
1211         /// <summary>
1212         /// Create a list of sql parameters for the specified method call expression,
1213         /// taking into account any explicit typing applied to the parameters via the
1214         /// Parameter attribute.
1215         /// </summary>
1216         private List<SqlExpression> GetFunctionParameters(MethodCallExpression mce, MetaFunction function) {
1217             List<SqlExpression> sqlParams = new List<SqlExpression>(mce.Arguments.Count);
1218
1219             // create sql parameters for each method parameter
1220             for (int i = 0, n = mce.Arguments.Count; i < n; i++) {
1221                 SqlExpression newParamExpression = this.VisitExpression(mce.Arguments[i]);
1222
1223                 // If the parameter explicitly specifies a type in metadata,
1224                 // use it as the provider type.
1225                 MetaParameter currMetaParam = function.Parameters[i];
1226                 if (!string.IsNullOrEmpty(currMetaParam.DbType)) {
1227                     SqlSimpleTypeExpression typeExpression = newParamExpression as SqlSimpleTypeExpression;
1228                     if (typeExpression != null) {
1229                         // determine provider type, and update the parameter expression
1230                         ProviderType providerType = typeProvider.Parse(currMetaParam.DbType);
1231                         typeExpression.SetSqlType(providerType);
1232                     }
1233                 }
1234                 sqlParams.Add(newParamExpression);
1235             }
1236
1237             return sqlParams;
1238         }
1239
1240         private SqlUserQuery VisitUserQuery(string query, Expression[] arguments, Type resultType) {
1241             SqlExpression[] args = new SqlExpression[arguments.Length];
1242             for (int i = 0, n = args.Length; i < n; i++) {
1243                 args[i] = this.VisitExpression(arguments[i]);
1244             }
1245             SqlUserQuery suq = new SqlUserQuery(query, null, args, this.dominatingExpression);
1246             if (resultType != typeof(void)) {
1247                 Type elementType = TypeSystem.GetElementType(resultType);
1248                 MetaType mType = this.services.Model.GetMetaType(elementType);
1249
1250                 // if the element type is a simple type (int, bool, etc.) we create
1251                 // a single column binding
1252                 if (TypeSystem.IsSimpleType(elementType)) {
1253                     SqlUserColumn col = new SqlUserColumn(elementType, typeProvider.From(elementType), suq, "", false, this.dominatingExpression);
1254                     suq.Columns.Add(col);
1255                     suq.Projection = col;
1256                 }
1257                 else {
1258                     // ... otherwise we generate a default projection
1259                     SqlUserRow rowExp = new SqlUserRow(mType.InheritanceRoot, this.typeProvider.GetApplicationType((int)ConverterSpecialTypes.Row), suq, this.dominatingExpression);
1260                     suq.Projection = this.translator.BuildProjection(rowExp, mType, this.allowDeferred, null, this.dominatingExpression);
1261                 }
1262             }
1263             return suq;
1264         }
1265
1266         private SqlNode VisitUnary(UnaryExpression u) {
1267             SqlExpression exp = this.VisitExpression(u.Operand);
1268
1269             if (u.Method != null) {
1270                 return sql.MethodCall(u.Type, u.Method, null, new SqlExpression[] { exp }, dominatingExpression);
1271             }
1272
1273             SqlExpression result = null;
1274             switch (u.NodeType) {
1275                 case ExpressionType.Negate:
1276                 case ExpressionType.NegateChecked:
1277                     result = sql.Unary(SqlNodeType.Negate, exp, this.dominatingExpression);
1278                     break;
1279                 case ExpressionType.Not:
1280                     if (u.Operand.Type == typeof(bool) || u.Operand.Type == typeof(bool?)) {
1281                         result = sql.Unary(SqlNodeType.Not, exp, this.dominatingExpression);
1282                     }
1283                     else {
1284                         result = sql.Unary(SqlNodeType.BitNot, exp, this.dominatingExpression);
1285                     }
1286                     break;
1287                 case ExpressionType.TypeAs:
1288                     result = sql.Unary(SqlNodeType.Treat, exp, this.dominatingExpression);
1289                     break;
1290             }
1291             return result;
1292         }
1293
1294
1295         [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity", Justification = "These issues are related to our use of if-then and case statements for node types, which adds to the complexity count however when reviewed they are easy to navigate and understand.")]
1296         private SqlNode VisitBinary(BinaryExpression b) {
1297             SqlExpression left = this.VisitExpression(b.Left);
1298             SqlExpression right = this.VisitExpression(b.Right);
1299
1300             if (b.Method != null) {
1301                 return sql.MethodCall(b.Type, b.Method, null, new SqlExpression[] { left, right }, dominatingExpression);
1302             }
1303
1304             SqlExpression result = null;
1305
1306             switch (b.NodeType) {
1307                 case ExpressionType.Add:
1308                 case ExpressionType.AddChecked:
1309                     result = sql.Binary(SqlNodeType.Add, left, right, b.Type);
1310                     break;
1311                 case ExpressionType.Subtract:
1312                 case ExpressionType.SubtractChecked:
1313                     result = sql.Binary(SqlNodeType.Sub, left, right, b.Type);
1314                     break;
1315                 case ExpressionType.Multiply:
1316                 case ExpressionType.MultiplyChecked:
1317                     result = sql.Binary(SqlNodeType.Mul, left, right, b.Type);
1318                     break;
1319                 case ExpressionType.Divide:
1320                     result = sql.Binary(SqlNodeType.Div, left, right, b.Type);
1321                     break;
1322                 case ExpressionType.Modulo:
1323                     result = sql.Binary(SqlNodeType.Mod, left, right, b.Type);
1324                     break;
1325                 case ExpressionType.And:
1326                     if (b.Left.Type == typeof(bool) || b.Left.Type == typeof(bool?)) {
1327                         result = sql.Binary(SqlNodeType.And, left, right, b.Type);
1328                     }
1329                     else {
1330                         result = sql.Binary(SqlNodeType.BitAnd, left, right, b.Type);
1331                     }
1332                     break;
1333                 case ExpressionType.AndAlso:
1334                     result = sql.Binary(SqlNodeType.And, left, right, b.Type);
1335                     break;
1336                 case ExpressionType.Or:
1337                     if (b.Left.Type == typeof(bool) || b.Left.Type == typeof(bool?)) {
1338                         result = sql.Binary(SqlNodeType.Or, left, right, b.Type);
1339                     }
1340                     else {
1341                         result = sql.Binary(SqlNodeType.BitOr, left, right, b.Type);
1342                     }
1343                     break;
1344                 case ExpressionType.OrElse:
1345                     result = sql.Binary(SqlNodeType.Or, left, right, b.Type);
1346                     break;
1347                 case ExpressionType.LessThan:
1348                     result = sql.Binary(SqlNodeType.LT, left, right, b.Type);
1349                     break;
1350                 case ExpressionType.LessThanOrEqual:
1351                     result = sql.Binary(SqlNodeType.LE, left, right, b.Type);
1352                     break;
1353                 case ExpressionType.GreaterThan:
1354                     result = sql.Binary(SqlNodeType.GT, left, right, b.Type);
1355                     break;
1356                 case ExpressionType.GreaterThanOrEqual:
1357                     result = sql.Binary(SqlNodeType.GE, left, right, b.Type);
1358                     break;
1359                 case ExpressionType.Equal:
1360                     result = sql.Binary(SqlNodeType.EQ, left, right, b.Type);
1361                     break;
1362                 case ExpressionType.NotEqual:
1363                     result = sql.Binary(SqlNodeType.NE, left, right, b.Type);
1364                     break;
1365                 case ExpressionType.ExclusiveOr:
1366                     result = sql.Binary(SqlNodeType.BitXor, left, right, b.Type);
1367                     break;
1368                 case ExpressionType.Coalesce:
1369                     result = this.MakeCoalesce(left, right, b.Type);
1370                     break;
1371                 default:
1372                     throw Error.BinaryOperatorNotRecognized(b.NodeType);
1373             }
1374             return result;
1375         }
1376
1377         private SqlExpression MakeCoalesce(SqlExpression left, SqlExpression right, Type resultType) {
1378             CompensateForLowerPrecedenceOfDateType(ref left, ref right);    // DevDiv 176874
1379             if (TypeSystem.IsSimpleType(resultType)) {
1380                 return sql.Binary(SqlNodeType.Coalesce, left, right, resultType);
1381             }
1382             else {
1383                 List<SqlWhen> whens = new List<SqlWhen>(1);
1384                 whens.Add(new SqlWhen(sql.Unary(SqlNodeType.IsNull, left, left.SourceExpression), right));
1385                 SqlDuplicator dup = new SqlDuplicator(true);
1386                 return sql.SearchedCase(whens.ToArray(), (SqlExpression)dup.Duplicate(left), this.dominatingExpression);
1387             }
1388         }
1389
1390         // The result *type* of a COALESCE function call is that of the operand with the highest precedence.
1391         // However, the SQL DATE type has a lower precedence than DATETIME or SMALLDATETIME, despite having
1392         // a hihger range. The following logic compensates for that discrepancy.
1393         //
1394         private void CompensateForLowerPrecedenceOfDateType(ref SqlExpression left, ref SqlExpression right) {
1395             if (SqlFactory.IsSqlDateType(left) && SqlFactory.IsSqlDateTimeType(right)) {
1396                 right = (SqlExpression)ConvertDateToDateTime2(right);
1397             }
1398             else if (SqlFactory.IsSqlDateType(right) && SqlFactory.IsSqlDateTimeType(left)) {
1399                 left = (SqlExpression)ConvertDateToDateTime2(left);
1400             }
1401         }
1402
1403         private SqlNode VisitConcat(Expression source1, Expression source2) {
1404             SqlSelect left = this.VisitSequence(source1);
1405             SqlSelect right = this.VisitSequence(source2);
1406             SqlUnion union = new SqlUnion(left, right, true);
1407             SqlAlias alias = new SqlAlias(union);
1408             SqlAliasRef aref = new SqlAliasRef(alias);
1409             SqlSelect result = new SqlSelect(aref, alias, this.dominatingExpression);
1410             result.OrderingType = SqlOrderingType.Blocked;
1411             return result;
1412         }
1413
1414         private SqlNode VisitUnion(Expression source1, Expression source2) {
1415             SqlSelect left = this.VisitSequence(source1);
1416             SqlSelect right = this.VisitSequence(source2);
1417             SqlUnion union = new SqlUnion(left, right, false);
1418             SqlAlias alias = new SqlAlias(union);
1419             SqlAliasRef aref = new SqlAliasRef(alias);
1420             SqlSelect result = new SqlSelect(aref, alias, this.dominatingExpression);
1421             result.OrderingType = SqlOrderingType.Blocked;
1422             return result;
1423         }
1424
1425         private SqlNode VisitIntersect(Expression source1, Expression source2) {
1426             Type type = TypeSystem.GetElementType(source1.Type);
1427             if (IsGrouping(type)) {
1428                 throw Error.IntersectNotSupportedForHierarchicalTypes();
1429             }
1430
1431             SqlSelect select1 = this.LockSelect(this.VisitSequence(source1));
1432             SqlSelect select2 = this.VisitSequence(source2);
1433
1434             SqlAlias alias1 = new SqlAlias(select1);
1435             SqlAliasRef aref1 = new SqlAliasRef(alias1);
1436
1437             SqlAlias alias2 = new SqlAlias(select2);
1438             SqlAliasRef aref2 = new SqlAliasRef(alias2);
1439
1440             SqlExpression any = this.GenerateQuantifier(alias2, sql.Binary(SqlNodeType.EQ2V, aref1, aref2), true);
1441
1442             SqlSelect result = new SqlSelect(aref1, alias1, select1.SourceExpression);
1443             result.Where = any;
1444             result.IsDistinct = true;
1445             result.OrderingType = SqlOrderingType.Blocked;
1446             return result;
1447         }
1448
1449         private SqlNode VisitExcept(Expression source1, Expression source2) {
1450             Type type = TypeSystem.GetElementType(source1.Type);
1451             if (IsGrouping(type)) {
1452                 throw Error.ExceptNotSupportedForHierarchicalTypes();
1453             }
1454
1455             SqlSelect select1 = this.LockSelect(this.VisitSequence(source1));
1456             SqlSelect select2 = this.VisitSequence(source2);
1457
1458             SqlAlias alias1 = new SqlAlias(select1);
1459             SqlAliasRef aref1 = new SqlAliasRef(alias1);
1460
1461             SqlAlias alias2 = new SqlAlias(select2);
1462             SqlAliasRef aref2 = new SqlAliasRef(alias2);
1463
1464             SqlExpression any = this.GenerateQuantifier(alias2, sql.Binary(SqlNodeType.EQ2V, aref1, aref2), true);
1465
1466             SqlSelect result = new SqlSelect(aref1, alias1, select1.SourceExpression);
1467             result.Where = sql.Unary(SqlNodeType.Not, any);
1468             result.IsDistinct = true;
1469             result.OrderingType = SqlOrderingType.Blocked;
1470             return result;
1471         }
1472
1473         /// <summary>
1474         /// Returns true if the type is an IGrouping.
1475         /// </summary>
1476         [SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic", Justification="Unknown reason.")]
1477         private bool IsGrouping(Type t) {
1478             if (t.IsGenericType &&
1479                 t.GetGenericTypeDefinition() == typeof(IGrouping<,>))
1480                 return true;
1481             return false;
1482         }
1483
1484         private SqlSelect VisitOrderBy(Expression sequence, LambdaExpression expression, SqlOrderType orderType) {
1485             if (IsGrouping(expression.Body.Type)) {
1486                 throw Error.GroupingNotSupportedAsOrderCriterion();
1487             }
1488             if (!this.typeProvider.From(expression.Body.Type).IsOrderable) {
1489                 throw Error.TypeCannotBeOrdered(expression.Body.Type);
1490             }
1491
1492             SqlSelect select = this.LockSelect(this.VisitSequence(sequence));
1493
1494             if (select.Selection.NodeType != SqlNodeType.AliasRef || select.OrderBy.Count > 0) {
1495                 SqlAlias alias = new SqlAlias(select);
1496                 SqlAliasRef aref = new SqlAliasRef(alias);
1497                 select = new SqlSelect(aref, alias, this.dominatingExpression);
1498             }
1499
1500             this.map[expression.Parameters[0]] = (SqlAliasRef)select.Selection;
1501             SqlExpression expr = this.VisitExpression(expression.Body);
1502
1503             select.OrderBy.Add(new SqlOrderExpression(orderType, expr));
1504             return select;
1505         }
1506
1507         private SqlSelect VisitThenBy(Expression sequence, LambdaExpression expression, SqlOrderType orderType) {
1508             if (IsGrouping(expression.Body.Type)) {
1509                 throw Error.GroupingNotSupportedAsOrderCriterion();
1510             }
1511             if (!this.typeProvider.From(expression.Body.Type).IsOrderable) {
1512                 throw Error.TypeCannotBeOrdered(expression.Body.Type);
1513             }
1514
1515             SqlSelect select = this.VisitSequence(sequence);
1516             System.Diagnostics.Debug.Assert(select.Selection.NodeType == SqlNodeType.AliasRef);
1517
1518             this.map[expression.Parameters[0]] = (SqlAliasRef)select.Selection;
1519             SqlExpression expr = this.VisitExpression(expression.Body);
1520
1521             select.OrderBy.Add(new SqlOrderExpression(orderType, expr));
1522             return select;
1523         }
1524
1525         private SqlNode VisitGroupBy(Expression sequence, LambdaExpression keyLambda, LambdaExpression elemLambda, LambdaExpression resultSelector) {
1526             // Convert seq.Group(elem, key) into
1527             //
1528             // SELECT s.key, MULTISET(select s2.elem from seq AS s2 where s.key == s2.key)
1529             // FROM seq AS s
1530             //
1531             // where key and elem can be either simple scalars or object constructions
1532             //
1533             SqlSelect seq = this.VisitSequence(sequence);
1534             seq = this.LockSelect(seq);
1535             SqlAlias seqAlias = new SqlAlias(seq);
1536             SqlAliasRef seqAliasRef = new SqlAliasRef(seqAlias);
1537
1538             // evaluate the key expression relative to original sequence
1539             this.map[keyLambda.Parameters[0]] = seqAliasRef;
1540             SqlExpression keyExpr = this.VisitExpression(keyLambda.Body);
1541
1542             // make a duplicate of the original sequence to use as a foundation of our group multiset
1543             SqlDuplicator sd = new SqlDuplicator();
1544             SqlSelect selDup = (SqlSelect)sd.Duplicate(seq);
1545
1546             // rebind key in relative to the duplicate sequence
1547             SqlAlias selDupAlias = new SqlAlias(selDup);
1548             SqlAliasRef selDupRef = new SqlAliasRef(selDupAlias);
1549             this.map[keyLambda.Parameters[0]] = selDupRef;
1550             SqlExpression keyDup = this.VisitExpression(keyLambda.Body);
1551
1552             SqlExpression elemExpr = null;
1553             SqlExpression elemOnGroupSource = null;
1554             if (elemLambda != null) {
1555                 // evaluate element expression relative to the duplicate sequence
1556                 this.map[elemLambda.Parameters[0]] = selDupRef;
1557                 elemExpr = this.VisitExpression(elemLambda.Body);
1558
1559                 // evaluate element expression relative to original sequence
1560                 this.map[elemLambda.Parameters[0]] = seqAliasRef;
1561                 elemOnGroupSource = this.VisitExpression(elemLambda.Body);
1562             }
1563             else {
1564                 // no elem expression supplied, so just use an alias ref to the duplicate sequence.
1565                 // this will resolve to whatever was being produced by the sequence
1566                 elemExpr = selDupRef;
1567                 elemOnGroupSource = seqAliasRef;
1568             }
1569
1570             // Make a sub expression out of the key.  This will allow a single definition of the
1571             // expression to be shared at multiple points in the tree (via SqlSharedExpressionRef's)
1572             SqlSharedExpression keySubExpr = new SqlSharedExpression(keyExpr);
1573             keyExpr = new SqlSharedExpressionRef(keySubExpr);
1574
1575             // construct the select clause that picks out the elements (this may be redundant...)
1576             SqlSelect selElem = new SqlSelect(elemExpr, selDupAlias, this.dominatingExpression);
1577             selElem.Where = sql.Binary(SqlNodeType.EQ2V, keyExpr, keyDup);
1578
1579             // Finally, make the MULTISET node. this will be used as part of the final select
1580             SqlSubSelect ss = sql.SubSelect(SqlNodeType.Multiset, selElem);
1581
1582             // add a layer to the original sequence before applying the actual group-by clause
1583             SqlSelect gsel = new SqlSelect(new SqlSharedExpressionRef(keySubExpr), seqAlias, this.dominatingExpression);
1584             gsel.GroupBy.Add(keySubExpr);
1585             SqlAlias gselAlias = new SqlAlias(gsel);
1586
1587             SqlSelect result = null;
1588             if (resultSelector != null) {
1589                 // Create final select to include construction of group multiset
1590                 // select new Grouping { Key = key, Group = Multiset(select elem from seq where match) } from ...
1591                 Type elementType = typeof(IGrouping<,>).MakeGenericType(keyExpr.ClrType, elemExpr.ClrType);
1592
1593                 SqlExpression keyGroup = new SqlGrouping(elementType, this.typeProvider.From(elementType), keyExpr, ss, this.dominatingExpression);
1594                 SqlSelect keyGroupSel = new SqlSelect(keyGroup, gselAlias, this.dominatingExpression);
1595                 SqlAlias kgAlias = new SqlAlias(keyGroupSel);
1596                 SqlAliasRef kgAliasRef = new SqlAliasRef(kgAlias);
1597
1598                 this.map[resultSelector.Parameters[0]] = sql.Member(kgAliasRef, elementType.GetProperty("Key"));
1599                 this.map[resultSelector.Parameters[1]] = kgAliasRef;
1600
1601                 // remember the select that has the actual group (for optimizing aggregates later)
1602                 this.gmap[kgAliasRef] = new GroupInfo { SelectWithGroup = gsel, ElementOnGroupSource = elemOnGroupSource };
1603
1604                 SqlExpression resultExpr = this.VisitExpression(resultSelector.Body);
1605                 result = new SqlSelect(resultExpr, kgAlias, this.dominatingExpression);
1606
1607                 // remember the select that has the actual group (for optimizing aggregates later)
1608                 this.gmap[resultExpr] = new GroupInfo { SelectWithGroup = gsel, ElementOnGroupSource = elemOnGroupSource };
1609             }
1610             else {
1611                 // Create final select to include construction of group multiset
1612                 // select new Grouping { Key = key, Group = Multiset(select elem from seq where match) } from ...
1613                 Type elementType = typeof(IGrouping<,>).MakeGenericType(keyExpr.ClrType, elemExpr.ClrType);
1614
1615                 SqlExpression resultExpr = new SqlGrouping(elementType, this.typeProvider.From(elementType), keyExpr, ss, this.dominatingExpression);
1616                 result = new SqlSelect(resultExpr, gselAlias, this.dominatingExpression);
1617
1618                 // remember the select that has the actual group (for optimizing aggregates later)
1619                 this.gmap[resultExpr] = new GroupInfo { SelectWithGroup = gsel, ElementOnGroupSource = elemOnGroupSource };
1620             }
1621
1622             return result;
1623         }
1624
1625         [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity", Justification="These issues are related to our use of if-then and case statements for node types, which adds to the complexity count however when reviewed they are easy to navigate and understand.")]
1626         private SqlNode VisitAggregate(Expression sequence, LambdaExpression lambda, SqlNodeType aggType, Type returnType) {
1627             // Convert seq.Agg(exp) into
1628             //
1629             // 1) SELECT Agg(exp) FROM seq
1630             // 2) SELECT Agg1 FROM (SELECT Agg(exp) as Agg1 FROM group-seq GROUP BY ...)
1631             // 3) SCALAR(SELECT Agg(exp) FROM seq)
1632             //
1633             bool isCount = aggType == SqlNodeType.Count || aggType == SqlNodeType.LongCount;
1634
1635             SqlNode source = this.Visit(sequence);
1636             SqlSelect select = this.CoerceToSequence(source);
1637             SqlAlias alias = new SqlAlias(select);
1638             SqlAliasRef aref = new SqlAliasRef(alias);
1639
1640             // If the sequence is of the form x.Select(expr).Agg() and the lambda for the aggregate is null,
1641             // or is a no-op parameter expression (like u=>u), clone the group by selection lambda
1642             // expression, and use for the aggregate.
1643             // Final form should be x.Agg(expr)
1644             MethodCallExpression mce = sequence as MethodCallExpression;
1645             if (!outerNode && !isCount && (lambda == null || (lambda.Parameters.Count == 1 && lambda.Parameters[0] == lambda.Body)) &&
1646                 (mce != null) && IsSequenceOperatorCall(mce, "Select") && select.From is SqlAlias) {
1647                 LambdaExpression selectionLambda = GetLambda(mce.Arguments[1]);
1648
1649                 lambda = Expression.Lambda(selectionLambda.Type, selectionLambda.Body, selectionLambda.Parameters);
1650
1651                 alias = (SqlAlias)select.From;
1652                 aref = new SqlAliasRef(alias);
1653             }
1654
1655             if (lambda != null && !TypeSystem.IsSimpleType(lambda.Body.Type)) {
1656                 throw Error.CannotAggregateType(lambda.Body.Type);
1657             }
1658
1659             //Empty parameter aggregates are not allowed on anonymous types
1660             //i.e. db.Customers.Select(c=>new{c.Age}).Max() instead it should be
1661             //     db.Customers.Select(c=>new{c.Age}).Max(c=>c.Age)
1662             if (select.Selection.SqlType.IsRuntimeOnlyType && !IsGrouping(sequence.Type) && !isCount && lambda == null) {
1663                 throw Error.NonCountAggregateFunctionsAreNotValidOnProjections(aggType);
1664             }
1665             if (lambda != null)
1666                 this.map[lambda.Parameters[0]] = aref;
1667
1668             if (this.outerNode) {
1669                 // If this aggregate is basically the last/outer-most operator of the query
1670                 //
1671                 // produce SELECT Agg(exp) FROM seq
1672                 //
1673                 SqlExpression exp = (lambda != null) ? this.VisitExpression(lambda.Body) : null;
1674                 SqlExpression where = null;
1675                 if (isCount && exp != null) {
1676                     where = exp;
1677                     exp = null;
1678                 }
1679                 else if (exp == null && !isCount) {
1680                     exp = aref;
1681                 }
1682                 if (exp != null) {
1683                     // in case this contains another aggregate
1684                     exp = new SqlSimpleExpression(exp);
1685                 }
1686                 SqlSelect sel = new SqlSelect(
1687                     this.GetAggregate(aggType, returnType, exp),
1688                     alias,
1689                     this.dominatingExpression
1690                     );
1691                 sel.Where = where;
1692                 sel.OrderingType = SqlOrderingType.Never;
1693                 return sel;
1694             }
1695             else if (!isCount || lambda == null) {
1696                 // Look to optimize aggregate by pushing its evaluation down to the select node that has the
1697                 // actual group-by operator.
1698                 //
1699                 // Produce:  SELECT Agg1 FROM (SELECT Agg(exp) as Agg1 FROM seq GROUP BY ...)
1700                 //
1701                 GroupInfo info = this.FindGroupInfo(source);
1702                 if (info != null) {
1703                     SqlExpression exp = null;
1704                     if (lambda != null) {
1705                         // evaluate expression relative to the group-by select node
1706                         this.map[lambda.Parameters[0]] = (SqlExpression)SqlDuplicator.Copy(info.ElementOnGroupSource);
1707                         exp = this.VisitExpression(lambda.Body);
1708                     } else if (!isCount) {
1709                         // support aggregates w/o an explicit selector specified
1710                         exp = info.ElementOnGroupSource;
1711                     }
1712                     if (exp != null) {
1713                         // in case this contains another aggregate
1714                         exp = new SqlSimpleExpression(exp);
1715                     }
1716                     SqlExpression agg = this.GetAggregate(aggType, returnType, exp);
1717                     SqlColumn c = new SqlColumn(agg.ClrType, agg.SqlType, null, null, agg, this.dominatingExpression);
1718                     info.SelectWithGroup.Row.Columns.Add(c);
1719                     return new SqlColumnRef(c);
1720                 }
1721             }
1722             // Otherwise, if we cannot optimize then fall back to generating a nested aggregate in a correlated sub query
1723             //
1724             // SCALAR(SELECT Agg(exp) FROM seq)
1725             {
1726                 SqlExpression exp = (lambda != null) ? this.VisitExpression(lambda.Body) : null;
1727                 if (exp != null) {
1728                     // in case this contains another aggregate
1729                     exp = new SqlSimpleExpression(exp);
1730                 }
1731                 SqlSelect sel = new SqlSelect(
1732                     this.GetAggregate(aggType, returnType, isCount ? null : (lambda == null) ? aref : exp),
1733                     alias,
1734                     this.dominatingExpression
1735                     );
1736                 sel.Where = isCount ? exp : null;
1737                 return sql.SubSelect(SqlNodeType.ScalarSubSelect, sel);
1738             }
1739         }
1740
1741         private GroupInfo FindGroupInfo(SqlNode source) {
1742             GroupInfo info = null;
1743             this.gmap.TryGetValue(source, out info);
1744             if (info != null) {
1745                 return info;
1746             }
1747             SqlAlias alias = source as SqlAlias;
1748             if (alias != null) {
1749                 SqlSelect select = alias.Node as SqlSelect;
1750                 if (select != null) {
1751                     return this.FindGroupInfo(select.Selection);
1752                 }
1753                 // it might be an expression (not yet fully resolved)
1754                 source = alias.Node;
1755             }
1756             SqlExpression expr = source as SqlExpression;
1757             if (expr != null) {
1758                 switch (expr.NodeType) {
1759                     case SqlNodeType.AliasRef:
1760                         return this.FindGroupInfo(((SqlAliasRef)expr).Alias);
1761                     case SqlNodeType.Member:
1762                         return this.FindGroupInfo(((SqlMember)expr).Expression);
1763                     default:
1764                         this.gmap.TryGetValue(expr, out info);
1765                         return info;
1766                 }
1767             }
1768             return null;
1769         }
1770
1771         private SqlExpression GetAggregate(SqlNodeType aggType, Type clrType, SqlExpression exp) {
1772             ProviderType sqlType = this.typeProvider.From(clrType);
1773             return new SqlUnary(aggType, clrType, sqlType, exp, this.dominatingExpression);
1774         }
1775
1776         private SqlNode VisitContains(Expression sequence, Expression value) {
1777             Type elemType = TypeSystem.GetElementType(sequence.Type);
1778             SqlNode seqNode = this.Visit(sequence);
1779             if (seqNode.NodeType == SqlNodeType.ClientArray) {
1780                 SqlClientArray array = (SqlClientArray)seqNode;
1781                 return this.GenerateInExpression(this.VisitExpression(value), array.Expressions);
1782             }
1783             else if (seqNode.NodeType == SqlNodeType.Value) {
1784                 IEnumerable values = ((SqlValue)seqNode).Value as IEnumerable;
1785                 IQueryable query = values as IQueryable;
1786                 if (query == null) {
1787                     SqlExpression expr = this.VisitExpression(value);
1788                     List<SqlExpression> list = values.OfType<object>().Select(v => sql.ValueFromObject(v, elemType, true, this.dominatingExpression)).ToList();
1789                     return this.GenerateInExpression(expr, list);
1790                 }
1791                 seqNode = this.Visit(query.Expression);
1792             }
1793             ParameterExpression p = Expression.Parameter(value.Type, "p");
1794             LambdaExpression lambda = Expression.Lambda(Expression.Equal(p, value), p);
1795             return this.VisitQuantifier(this.CoerceToSequence(seqNode), lambda, true);
1796         }
1797
1798         private SqlExpression GenerateInExpression(SqlExpression expr, List<SqlExpression> list) {
1799             if (list.Count == 0) {
1800                 return sql.ValueFromObject(false, this.dominatingExpression);
1801             }
1802             else if (list[0].SqlType.CanBeColumn) {
1803                 return sql.In(expr, list, this.dominatingExpression);
1804             }
1805             else {
1806                 SqlExpression pred = sql.Binary(SqlNodeType.EQ, expr, list[0]);
1807                 for (int i = 1, n = list.Count; i < n; i++) {
1808                     pred = sql.Binary(SqlNodeType.Or, pred, sql.Binary(SqlNodeType.EQ, (SqlExpression)SqlDuplicator.Copy(expr), list[i]));
1809                 }
1810                 return pred;
1811             }
1812         }
1813
1814         private SqlNode VisitQuantifier(Expression sequence, LambdaExpression lambda, bool isAny) {
1815             return this.VisitQuantifier(this.VisitSequence(sequence), lambda, isAny);
1816         }
1817
1818         private SqlNode VisitQuantifier(SqlSelect select, LambdaExpression lambda, bool isAny) {
1819             SqlAlias alias = new SqlAlias(select);
1820             SqlAliasRef aref = new SqlAliasRef(alias);
1821             if (lambda != null) {
1822                 this.map[lambda.Parameters[0]] = aref;
1823             }
1824             SqlExpression cond = lambda != null ? this.VisitExpression(lambda.Body) : null;
1825             return this.GenerateQuantifier(alias, cond, isAny);
1826         }
1827
1828         private SqlExpression GenerateQuantifier(SqlAlias alias, SqlExpression cond, bool isAny) {
1829             SqlAliasRef aref = new SqlAliasRef(alias);
1830             if (isAny) {
1831                 SqlSelect sel = new SqlSelect(aref, alias, this.dominatingExpression);
1832                 sel.Where = cond;
1833                 sel.OrderingType = SqlOrderingType.Never;
1834                 SqlSubSelect exists = sql.SubSelect(SqlNodeType.Exists, sel);
1835                 return exists;
1836             }
1837             else {
1838                 SqlSelect sel = new SqlSelect(aref, alias, this.dominatingExpression);
1839                 SqlSubSelect ss = sql.SubSelect(SqlNodeType.Exists, sel);
1840                 sel.Where = sql.Unary(SqlNodeType.Not2V, cond, this.dominatingExpression);
1841                 return sql.Unary(SqlNodeType.Not, ss, this.dominatingExpression);
1842             }
1843         }
1844
1845         private void CheckContext(SqlExpression expr) {
1846             // try to catch use of incorrect context if we can
1847             SqlValue value = expr as SqlValue;
1848             if (value != null) {
1849                 DataContext dc = value.Value as DataContext;
1850                 if (dc != null) {
1851                     if (dc != this.services.Context) {
1852                         throw Error.WrongDataContext();
1853                     }
1854                 }
1855             }
1856         }
1857
1858         private SqlNode VisitMemberAccess(MemberExpression ma) {
1859             Type memberType = TypeSystem.GetMemberType(ma.Member);
1860             if (memberType.IsGenericType && memberType.GetGenericTypeDefinition() == typeof(Table<>)) {
1861                 Type rowType = memberType.GetGenericArguments()[0];
1862                 CheckContext(this.VisitExpression(ma.Expression));
1863                 ITable table = this.services.Context.GetTable(rowType);
1864                 if (table != null)
1865                     return this.Visit(Expression.Constant(table));
1866             }
1867             if (ma.Member.Name == "Count" && TypeSystem.IsSequenceType(ma.Expression.Type)) {
1868                 return this.VisitAggregate(ma.Expression, null, SqlNodeType.Count, typeof(int));
1869             }
1870
1871             return sql.Member(VisitExpression(ma.Expression), ma.Member);
1872         }
1873
1874         [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity", Justification = "These issues are related to our use of if-then and case statements for node types, which adds to the complexity count however when reviewed they are easy to navigate and understand.")]
1875         private SqlNode VisitMethodCall(MethodCallExpression mc) {
1876             Type declType = mc.Method.DeclaringType;
1877             if (mc.Method.IsStatic) {
1878                 if (this.IsSequenceOperatorCall(mc)) {
1879                     return this.VisitSequenceOperatorCall(mc);
1880                 }
1881                 else if (IsDataManipulationCall(mc)) {
1882                     return this.VisitDataManipulationCall(mc);
1883                 }
1884                 // why is this handled here and not in SqlMethodCallConverter?
1885                 else if (declType == typeof(DBConvert) || declType == typeof(Convert)) {
1886                     if (mc.Method.Name == "ChangeType") {
1887                         SqlNode sn = null;
1888                         if (mc.Arguments.Count == 2) {
1889                             object value = GetValue(mc.Arguments[1], "ChangeType");
1890                             if (value != null && typeof(Type).IsAssignableFrom(value.GetType())) {
1891                                 sn = this.VisitChangeType(mc.Arguments[0], (Type)value);
1892                             }
1893                         }
1894                         if(sn == null) {
1895                             throw Error.MethodFormHasNoSupportConversionToSql(mc.Method.Name, mc.Method);
1896                         }
1897                         return sn;
1898                     }
1899                 }
1900             }
1901             else if (typeof(DataContext).IsAssignableFrom(mc.Method.DeclaringType)) {
1902                 switch (mc.Method.Name) {
1903                     case "GetTable": {
1904                             // calls to GetTable<T> can be translated directly as table references
1905                             if (mc.Method.IsGenericMethod) {
1906                                 Type[] typeArgs = mc.Method.GetGenericArguments();
1907                                 if (typeArgs.Length == 1 && mc.Method.GetParameters().Length == 0) {
1908                                     CheckContext(this.VisitExpression(mc.Object));
1909                                     ITable table = this.services.Context.GetTable(typeArgs[0]);
1910                                     if (table != null) {
1911                                         return this.Visit(Expression.Constant(table));
1912                                     }
1913                                 }
1914                             }
1915                             break;
1916                         }
1917                     case "ExecuteCommand":
1918                     case "ExecuteQuery":
1919                         return this.VisitUserQuery((string)GetValue(mc.Arguments[0], mc.Method.Name), GetArray(mc.Arguments[1]), mc.Type);
1920                 }
1921
1922                 if (this.IsMappedFunctionCall(mc)) {
1923                     return this.VisitMappedFunctionCall(mc);
1924                 }
1925             }
1926             else if (
1927                 mc.Method.DeclaringType != typeof(string)
1928                 && mc.Method.Name == "Contains"
1929                 && !mc.Method.IsStatic
1930                 && typeof(IList).IsAssignableFrom(mc.Method.DeclaringType)
1931                 && mc.Type == typeof(bool)
1932                 && mc.Arguments.Count == 1
1933                 && TypeSystem.GetElementType(mc.Method.DeclaringType).IsAssignableFrom(mc.Arguments[0].Type)
1934                 ) {
1935                 return this.VisitContains(mc.Object, mc.Arguments[0]);
1936             }
1937
1938             // default: create sql method call node instead
1939             SqlExpression obj = VisitExpression(mc.Object);
1940             SqlExpression[] args = new SqlExpression[mc.Arguments.Count];
1941             for (int i = 0, n = args.Length; i < n; i++) {
1942                 args[i] = VisitExpression(mc.Arguments[i]);
1943             }
1944             return sql.MethodCall(mc.Method, obj, args, dominatingExpression);
1945         }
1946
1947         private object GetValue(Expression expression, string operation) {
1948             SqlExpression exp = this.VisitExpression(expression);
1949             if (exp.NodeType == SqlNodeType.Value) {
1950                 return ((SqlValue)exp).Value;
1951             }
1952             throw Error.NonConstantExpressionsNotSupportedFor(operation);
1953         }
1954
1955         private static Expression[] GetArray(Expression array) {
1956             NewArrayExpression n = array as NewArrayExpression;
1957             if (n != null) {
1958                 return n.Expressions.ToArray();
1959             }
1960             ConstantExpression c = array as ConstantExpression;
1961             if (c != null) {
1962                 object[] obs = c.Value as object[];
1963                 if (obs != null) {
1964                     Type elemType = TypeSystem.GetElementType(c.Type);
1965                     return obs.Select(o => Expression.Constant(o, elemType)).ToArray();
1966                 }
1967             }
1968             return new Expression[] { };
1969         }
1970
1971         [SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic", Justification="Unknown reason.")]
1972         private Expression RemoveQuotes(Expression expression) {
1973             while (expression.NodeType == ExpressionType.Quote) {
1974                 expression = ((UnaryExpression)expression).Operand;
1975             }
1976             return expression;
1977         }
1978
1979         private bool IsLambda(Expression expression) {
1980             return this.RemoveQuotes(expression).NodeType == ExpressionType.Lambda;
1981         }
1982
1983         private LambdaExpression GetLambda(Expression expression) {
1984             return this.RemoveQuotes(expression) as LambdaExpression;
1985         }
1986
1987         private bool IsMappedFunctionCall(MethodCallExpression mc) {
1988             MetaFunction function = services.Model.GetFunction(mc.Method);
1989             return function != null;
1990         }
1991
1992         private SqlNode VisitMappedFunctionCall(MethodCallExpression mc) {
1993             // See if the method maps to a user defined function
1994             MetaFunction function = services.Model.GetFunction(mc.Method);
1995             System.Diagnostics.Debug.Assert(function != null);
1996             CheckContext(this.VisitExpression(mc.Object));
1997             if (!function.IsComposable) {
1998                 return this.TranslateStoredProcedureCall(mc, function);
1999             }
2000             else if (function.ResultRowTypes.Count > 0) {
2001                 return this.TranslateTableValuedFunction(mc, function);
2002             }
2003             else {
2004                 ProviderType sqlType = function.ReturnParameter != null && !string.IsNullOrEmpty(function.ReturnParameter.DbType)
2005                     ? this.typeProvider.Parse(function.ReturnParameter.DbType)
2006                     : this.typeProvider.From(mc.Method.ReturnType);
2007                 List<SqlExpression> sqlParams = this.GetFunctionParameters(mc, function);
2008                 return sql.FunctionCall(mc.Method.ReturnType, sqlType, function.MappedName, sqlParams, mc);
2009             }
2010         }
2011
2012         [SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic", Justification="Unknown reason.")]
2013         private bool IsSequenceOperatorCall(MethodCallExpression mc) {
2014             Type declType = mc.Method.DeclaringType;
2015             if (declType == typeof(System.Linq.Enumerable) ||
2016                 declType == typeof(System.Linq.Queryable)) {
2017                 return true;
2018             }
2019             return false;
2020         }
2021
2022         private bool IsSequenceOperatorCall(MethodCallExpression mc, string methodName) {
2023             if (IsSequenceOperatorCall(mc) && mc.Method.Name == methodName) {
2024                 return true;
2025             }
2026             return false;
2027         }
2028
2029         [SuppressMessage("Microsoft.Maintainability", "CA1505:AvoidUnmaintainableCode", Justification = "These issues are related to our use of if-then and case statements for node types, which adds to the complexity count however when reviewed they are easy to navigate and understand.")]
2030         [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity", Justification = "These issues are related to our use of if-then and case statements for node types, which adds to the complexity count however when reviewed they are easy to navigate and understand.")]
2031         private SqlNode VisitSequenceOperatorCall(MethodCallExpression mc) {
2032             Type declType = mc.Method.DeclaringType;
2033             bool isSupportedSequenceOperator = false;
2034             if (IsSequenceOperatorCall(mc)) {
2035                 switch (mc.Method.Name) {
2036                     case "Select":
2037                         isSupportedSequenceOperator = true;
2038                         if (mc.Arguments.Count == 2 &&
2039                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2040                             return this.VisitSelect(mc.Arguments[0], this.GetLambda(mc.Arguments[1]));
2041                         }
2042                         break;
2043                     case "SelectMany":
2044                         isSupportedSequenceOperator = true;
2045                         if (mc.Arguments.Count == 2 &&
2046                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2047                             return this.VisitSelectMany(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), null);
2048                         }
2049                         else if (mc.Arguments.Count == 3 &&
2050                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1 &&
2051                             this.IsLambda(mc.Arguments[2]) && this.GetLambda(mc.Arguments[2]).Parameters.Count == 2) {
2052                             return this.VisitSelectMany(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), this.GetLambda(mc.Arguments[2]));
2053                         }
2054                         break;
2055                     case "Join":
2056                         isSupportedSequenceOperator = true;
2057                         if (mc.Arguments.Count == 5 &&
2058                             this.IsLambda(mc.Arguments[2]) && this.GetLambda(mc.Arguments[2]).Parameters.Count == 1 &&
2059                             this.IsLambda(mc.Arguments[3]) && this.GetLambda(mc.Arguments[3]).Parameters.Count == 1 &&
2060                             this.IsLambda(mc.Arguments[4]) && this.GetLambda(mc.Arguments[4]).Parameters.Count == 2) {
2061                             return this.VisitJoin(mc.Arguments[0], mc.Arguments[1], this.GetLambda(mc.Arguments[2]), this.GetLambda(mc.Arguments[3]), this.GetLambda(mc.Arguments[4]));
2062                         }
2063                         break;
2064                     case "GroupJoin":
2065                         isSupportedSequenceOperator = true;
2066                         if (mc.Arguments.Count == 5 &&
2067                             this.IsLambda(mc.Arguments[2]) && this.GetLambda(mc.Arguments[2]).Parameters.Count == 1 &&
2068                             this.IsLambda(mc.Arguments[3]) && this.GetLambda(mc.Arguments[3]).Parameters.Count == 1 &&
2069                             this.IsLambda(mc.Arguments[4]) && this.GetLambda(mc.Arguments[4]).Parameters.Count == 2) {
2070                             return this.VisitGroupJoin(mc.Arguments[0], mc.Arguments[1], this.GetLambda(mc.Arguments[2]), this.GetLambda(mc.Arguments[3]), this.GetLambda(mc.Arguments[4]));
2071                         }
2072                         break;
2073                     case "DefaultIfEmpty":
2074                         isSupportedSequenceOperator = true;
2075                         if (mc.Arguments.Count == 1) {
2076                             return this.VisitDefaultIfEmpty(mc.Arguments[0]);
2077                         }
2078                         break;
2079                     case "OfType":
2080                         isSupportedSequenceOperator = true;
2081                         if (mc.Arguments.Count == 1) {
2082                             Type ofType = mc.Method.GetGenericArguments()[0];
2083                             return this.VisitOfType(mc.Arguments[0], ofType);
2084                         }
2085                         break;
2086                     case "Cast":
2087                         isSupportedSequenceOperator = true;
2088                         if (mc.Arguments.Count == 1) {
2089                             Type type = mc.Method.GetGenericArguments()[0];
2090                             return this.VisitSequenceCast(mc.Arguments[0], type);
2091                         }
2092                         break;
2093                     case "Where":
2094                         isSupportedSequenceOperator = true;
2095                         if (mc.Arguments.Count == 2 &&
2096                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2097                             return this.VisitWhere(mc.Arguments[0], this.GetLambda(mc.Arguments[1]));
2098                         }
2099                         break;
2100                     case "First":
2101                     case "FirstOrDefault":
2102                         isSupportedSequenceOperator = true;
2103                         if (mc.Arguments.Count == 1) {
2104                             return this.VisitFirst(mc.Arguments[0], null, true);
2105                         }
2106                         else if (mc.Arguments.Count == 2 &&
2107                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2108                             return this.VisitFirst(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), true);
2109                         }
2110                         break;
2111                     case "Single":
2112                     case "SingleOrDefault":
2113                         isSupportedSequenceOperator = true;
2114                         if (mc.Arguments.Count == 1) {
2115                             return this.VisitFirst(mc.Arguments[0], null, false);
2116                         }
2117                         else if (mc.Arguments.Count == 2 &&
2118                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2119                             return this.VisitFirst(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), false);
2120                         }
2121                         break;
2122                     case "Distinct":
2123                         isSupportedSequenceOperator = true;
2124                         if (mc.Arguments.Count == 1) {
2125                             return this.VisitDistinct(mc.Arguments[0]);
2126                         }
2127                         break;
2128                     case "Concat":
2129                         isSupportedSequenceOperator = true;
2130                         if (mc.Arguments.Count == 2) {
2131                             return this.VisitConcat(mc.Arguments[0], mc.Arguments[1]);
2132                         }
2133                         break;
2134                     case "Union":
2135                         isSupportedSequenceOperator = true;
2136                         if (mc.Arguments.Count == 2) {
2137                             return this.VisitUnion(mc.Arguments[0], mc.Arguments[1]);
2138                         }
2139                         break;
2140                     case "Intersect":
2141                         isSupportedSequenceOperator = true;
2142                         if (mc.Arguments.Count == 2) {
2143                             return this.VisitIntersect(mc.Arguments[0], mc.Arguments[1]);
2144                         }
2145                         break;
2146                     case "Except":
2147                         isSupportedSequenceOperator = true;
2148                         if (mc.Arguments.Count == 2) {
2149                             return this.VisitExcept(mc.Arguments[0], mc.Arguments[1]);
2150                         }
2151                         break;
2152                     case "Any":
2153                         isSupportedSequenceOperator = true;
2154                         if (mc.Arguments.Count == 1) {
2155                             return this.VisitQuantifier(mc.Arguments[0], null, true);
2156                         }
2157                         else if (mc.Arguments.Count == 2 &&
2158                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2159                             return this.VisitQuantifier(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), true);
2160                         }
2161                         break;
2162                     case "All":
2163                         isSupportedSequenceOperator = true;
2164                         if (mc.Arguments.Count == 2 &&
2165                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2166                             return this.VisitQuantifier(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), false);
2167                         }
2168                         break;
2169                     case "Count":
2170                         isSupportedSequenceOperator = true;
2171                         if (mc.Arguments.Count == 1) {
2172                             return this.VisitAggregate(mc.Arguments[0], null, SqlNodeType.Count, mc.Type);
2173                         }
2174                         else if (mc.Arguments.Count == 2 &&
2175                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2176                             return this.VisitAggregate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlNodeType.Count, mc.Type);
2177                         }
2178                         break;
2179                     case "LongCount":
2180                         isSupportedSequenceOperator = true;
2181                         if (mc.Arguments.Count == 1) {
2182                             return this.VisitAggregate(mc.Arguments[0], null, SqlNodeType.LongCount, mc.Type);
2183                         }
2184                         else if (mc.Arguments.Count == 2 &&
2185                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2186                             return this.VisitAggregate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlNodeType.LongCount, mc.Type);
2187                         }
2188                         break;
2189                     case "Sum":
2190                         isSupportedSequenceOperator = true;
2191                         if (mc.Arguments.Count == 1) {
2192                             return this.VisitAggregate(mc.Arguments[0], null, SqlNodeType.Sum, mc.Type);
2193                         }
2194                         else if (mc.Arguments.Count == 2 &&
2195                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2196                             return this.VisitAggregate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlNodeType.Sum, mc.Type);
2197                         }
2198                         break;
2199                     case "Min":
2200                         isSupportedSequenceOperator = true;
2201                         if (mc.Arguments.Count == 1) {
2202                             return this.VisitAggregate(mc.Arguments[0], null, SqlNodeType.Min, mc.Type);
2203                         }
2204                         else if (mc.Arguments.Count == 2 &&
2205                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2206                             return this.VisitAggregate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlNodeType.Min, mc.Type);
2207                         }
2208                         break;
2209                     case "Max":
2210                         isSupportedSequenceOperator = true;
2211                         if (mc.Arguments.Count == 1) {
2212                             return this.VisitAggregate(mc.Arguments[0], null, SqlNodeType.Max, mc.Type);
2213                         }
2214                         else if (mc.Arguments.Count == 2 &&
2215                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2216                             return this.VisitAggregate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlNodeType.Max, mc.Type);
2217                         }
2218                         break;
2219                     case "Average":
2220                         isSupportedSequenceOperator = true;
2221                         if (mc.Arguments.Count == 1) {
2222                             return this.VisitAggregate(mc.Arguments[0], null, SqlNodeType.Avg, mc.Type);
2223                         }
2224                         else if (mc.Arguments.Count == 2 &&
2225                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2226                             return this.VisitAggregate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlNodeType.Avg, mc.Type);
2227                         }
2228                         break;
2229                     case "GroupBy":
2230                         isSupportedSequenceOperator = true;
2231                         if (mc.Arguments.Count == 2 &&
2232                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2233                             return this.VisitGroupBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), null, null);
2234                         }
2235                         else if (mc.Arguments.Count == 3 &&
2236                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1 &&
2237                             this.IsLambda(mc.Arguments[2]) && this.GetLambda(mc.Arguments[2]).Parameters.Count == 1) {
2238                             return this.VisitGroupBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), this.GetLambda(mc.Arguments[2]), null);
2239                         }
2240                         else if (mc.Arguments.Count == 3 &&
2241                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1 &&
2242                             this.IsLambda(mc.Arguments[2]) && this.GetLambda(mc.Arguments[2]).Parameters.Count == 2) {
2243                             return this.VisitGroupBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), null, this.GetLambda(mc.Arguments[2]));
2244                         }
2245                         else if (mc.Arguments.Count == 4 &&
2246                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1 &&
2247                             this.IsLambda(mc.Arguments[2]) && this.GetLambda(mc.Arguments[2]).Parameters.Count == 1 &&
2248                             this.IsLambda(mc.Arguments[3]) && this.GetLambda(mc.Arguments[3]).Parameters.Count == 2) {
2249                             return this.VisitGroupBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), this.GetLambda(mc.Arguments[2]), this.GetLambda(mc.Arguments[3]));
2250                         }
2251                         break;
2252                     case "OrderBy":
2253                         isSupportedSequenceOperator = true;
2254                         if (mc.Arguments.Count == 2 &&
2255                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2256                             return this.VisitOrderBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlOrderType.Ascending);
2257                         }
2258                         break;
2259                     case "OrderByDescending":
2260                         isSupportedSequenceOperator = true;
2261                         if (mc.Arguments.Count == 2 &&
2262                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2263                             return this.VisitOrderBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlOrderType.Descending);
2264                         }
2265                         break;
2266                     case "ThenBy":
2267                         isSupportedSequenceOperator = true;
2268                         if (mc.Arguments.Count == 2 &&
2269                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2270                             return this.VisitThenBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlOrderType.Ascending);
2271                         }
2272                         break;
2273                     case "ThenByDescending":
2274                         isSupportedSequenceOperator = true;
2275                         if (mc.Arguments.Count == 2 &&
2276                             this.IsLambda(mc.Arguments[1]) && this.GetLambda(mc.Arguments[1]).Parameters.Count == 1) {
2277                             return this.VisitThenBy(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), SqlOrderType.Descending);
2278                         }
2279                         break;
2280                     case "Take":
2281                         isSupportedSequenceOperator = true;
2282                         if (mc.Arguments.Count == 2) {
2283                             return this.VisitTake(mc.Arguments[0], mc.Arguments[1]);
2284                         }
2285                         break;
2286                     case "Skip":
2287                         isSupportedSequenceOperator = true;
2288                         if (mc.Arguments.Count == 2) {
2289                             return this.VisitSkip(mc.Arguments[0], mc.Arguments[1]);
2290                         }
2291                         break;
2292                     case "Contains":
2293                         isSupportedSequenceOperator = true;
2294                         if (mc.Arguments.Count == 2) {
2295                             return this.VisitContains(mc.Arguments[0], mc.Arguments[1]);
2296                         }
2297                         break;
2298                     case "ToList":
2299                     case "AsEnumerable":
2300                     case "ToArray":
2301                         isSupportedSequenceOperator = true;
2302                         if (mc.Arguments.Count == 1) {
2303                             return this.Visit(mc.Arguments[0]);
2304                         }
2305                         break;
2306                 }
2307                 // If the operator is supported, but the particular overload is not,
2308                 // give an appropriate error message
2309                 if (isSupportedSequenceOperator) {
2310                     throw Error.QueryOperatorOverloadNotSupported(mc.Method.Name);
2311                 }
2312                 throw Error.QueryOperatorNotSupported(mc.Method.Name);
2313             }
2314             else {
2315                 throw Error.InvalidSequenceOperatorCall(declType);
2316             }
2317         }
2318
2319         private static bool IsDataManipulationCall(MethodCallExpression mc) {
2320             return mc.Method.IsStatic && mc.Method.DeclaringType == typeof(DataManipulation);
2321         }
2322
2323         private SqlNode VisitDataManipulationCall(MethodCallExpression mc) {
2324             if (IsDataManipulationCall(mc)) {
2325                 bool isSupportedDML = false;
2326                 switch (mc.Method.Name) {
2327                     case "Insert":
2328                         isSupportedDML = true;
2329                         if (mc.Arguments.Count == 2) {
2330                             return this.VisitInsert(mc.Arguments[0], this.GetLambda(mc.Arguments[1]));
2331                         }
2332                         else if (mc.Arguments.Count == 1) {
2333                             return this.VisitInsert(mc.Arguments[0], null);
2334                         }
2335                         break;
2336                     case "Update":
2337                         isSupportedDML = true;
2338                         if (mc.Arguments.Count == 3) {
2339                             return this.VisitUpdate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), this.GetLambda(mc.Arguments[2]));
2340                         }
2341                         else if (mc.Arguments.Count == 2) {
2342                             if (mc.Method.GetGenericArguments().Length == 1) {
2343                                 return this.VisitUpdate(mc.Arguments[0], this.GetLambda(mc.Arguments[1]), null);
2344                             }
2345                             else {
2346                                 return this.VisitUpdate(mc.Arguments[0], null, this.GetLambda(mc.Arguments[1]));
2347                             }
2348                         }
2349                         else if (mc.Arguments.Count == 1) {
2350                             return this.VisitUpdate(mc.Arguments[0], null, null);
2351                         }
2352                         break;
2353                     case "Delete":
2354                         isSupportedDML = true;
2355                         if (mc.Arguments.Count == 2) {
2356                             return this.VisitDelete(mc.Arguments[0], this.GetLambda(mc.Arguments[1]));
2357                         }
2358                         else if (mc.Arguments.Count == 1) {
2359                             return this.VisitDelete(mc.Arguments[0], null);
2360                         }
2361                         break;
2362                 }
2363                 if (isSupportedDML) {
2364                     throw Error.QueryOperatorOverloadNotSupported(mc.Method.Name);
2365                 }
2366                 throw Error.QueryOperatorNotSupported(mc.Method.Name);
2367             }
2368             throw Error.InvalidSequenceOperatorCall(mc.Method.Name);
2369         }
2370
2371         private SqlNode VisitFirst(Expression sequence, LambdaExpression lambda, bool isFirst) {
2372             SqlSelect select = this.LockSelect(this.VisitSequence(sequence));
2373             if (lambda != null) {
2374                 this.map[lambda.Parameters[0]] = (SqlAliasRef)select.Selection;
2375                 select.Where = this.VisitExpression(lambda.Body);
2376             }
2377             if (isFirst) {
2378                 select.Top = this.sql.ValueFromObject(1, false, this.dominatingExpression);
2379             }
2380             if (this.outerNode) {
2381                 return select;
2382             }
2383             SqlNodeType subType = (this.typeProvider.From(select.Selection.ClrType).CanBeColumn) ? SqlNodeType.ScalarSubSelect : SqlNodeType.Element;
2384             SqlSubSelect elem = sql.SubSelect(subType, select, sequence.Type);
2385             return elem;
2386         }
2387
2388         [SuppressMessage("Microsoft.Maintainability", "CA1506:AvoidExcessiveClassCoupling", Justification="These issues are related to our use of if-then and case statements for node types, which adds to the complexity count however when reviewed they are easy to navigate and understand.")]
2389         private SqlStatement VisitInsert(Expression item, LambdaExpression resultSelector) {
2390             if (item == null) {
2391                 throw Error.ArgumentNull("item");
2392             }
2393             this.dominatingExpression = item;
2394
2395             MetaTable metaTable = this.services.Model.GetTable(item.Type);
2396             Expression source = this.services.Context.GetTable(metaTable.RowType.Type).Expression;
2397
2398             MetaType itemMetaType = null;
2399             SqlNew sqlItem = null;
2400
2401             // construct insert assignments from 'item' info
2402             ConstantExpression conItem = item as ConstantExpression;
2403             if (conItem == null) {
2404                 throw Error.InsertItemMustBeConstant();
2405             }
2406             if (conItem.Value == null) {
2407                 throw Error.ArgumentNull("item");
2408             }
2409             // construct insert based on constant value
2410             List<SqlMemberAssign> bindings = new List<SqlMemberAssign>();
2411             itemMetaType = metaTable.RowType.GetInheritanceType(conItem.Value.GetType());
2412             SqlExpression sqlExprItem = sql.ValueFromObject(conItem.Value, true, source);
2413             foreach (MetaDataMember mm in itemMetaType.PersistentDataMembers) {
2414                 if (!mm.IsAssociation && !mm.IsDbGenerated && !mm.IsVersion) {
2415                     bindings.Add(new SqlMemberAssign(mm.Member, sql.Member(sqlExprItem, mm.Member)));
2416                 }
2417             }
2418             ConstructorInfo cons = itemMetaType.Type.GetConstructor(Type.EmptyTypes);
2419             System.Diagnostics.Debug.Assert(cons != null);
2420             sqlItem = sql.New(itemMetaType, cons, null, null, bindings, item);
2421
2422             SqlTable tab = sql.Table(metaTable, metaTable.RowType, this.dominatingExpression);
2423             SqlInsert sin = new SqlInsert(tab, sqlItem, item);
2424
2425             if (resultSelector == null) {
2426                 return sin;
2427             }
2428             else {
2429                 MetaDataMember id = itemMetaType.DBGeneratedIdentityMember;
2430                 bool isDbGenOnly = false;
2431                 if (id != null) {
2432                     isDbGenOnly = this.IsDbGeneratedKeyProjectionOnly(resultSelector.Body, id);
2433                     if (id.Type == typeof(Guid) && (this.converterStrategy & ConverterStrategy.CanOutputFromInsert) != 0) {
2434                         sin.OutputKey = new SqlColumn(id.Type, sql.Default(id), id.Name, id, null, this.dominatingExpression);
2435                         if (!isDbGenOnly) {
2436                             sin.OutputToLocal = true;
2437                         }
2438                     }
2439                 }
2440
2441                 SqlSelect result = null;
2442                 SqlSelect preResult = null;
2443                 SqlAlias tableAlias = new SqlAlias(tab);
2444                 SqlAliasRef tableAliasRef = new SqlAliasRef(tableAlias);
2445                 System.Diagnostics.Debug.Assert(resultSelector.Parameters.Count == 1);
2446                 this.map.Add(resultSelector.Parameters[0], tableAliasRef);
2447                 SqlExpression projection = this.VisitExpression(resultSelector.Body);
2448
2449                 // build select to return result
2450                 SqlExpression pred = null;
2451                 if (id != null) {
2452                     pred = sql.Binary(
2453                             SqlNodeType.EQ,
2454                             sql.Member(tableAliasRef, id.Member),
2455                             this.GetIdentityExpression(id, sin.OutputKey != null)
2456                             );
2457                 }
2458                 else {
2459                     SqlExpression itemExpression = this.VisitExpression(item);
2460                     pred = sql.Binary(SqlNodeType.EQ2V, tableAliasRef, itemExpression);
2461                 }
2462                 result = new SqlSelect(projection, tableAlias, resultSelector);
2463                 result.Where = pred;
2464
2465                 // Since we're only projecting back a single generated key, we can
2466                 // optimize the query to a simple selection (e.g. SELECT @@IDENTITY)
2467                 // rather than selecting back from the table.
2468                 if (id != null && isDbGenOnly) {
2469                     if (sin.OutputKey == null) {
2470                         SqlExpression exp = this.GetIdentityExpression(id, false);
2471                         if (exp.ClrType != id.Type) {
2472                             ProviderType sqlType = sql.Default(id);
2473                             exp = sql.ConvertTo(id.Type, sqlType, exp);
2474                         }
2475                         // The result selector passed in was bound to the table -
2476                         // we need to rebind to the single result as an array projection
2477                         ParameterExpression p = Expression.Parameter(id.Type, "p");
2478                         Expression[] init = new Expression[1] { Expression.Convert(p, typeof(object)) };
2479                         NewArrayExpression arrExp = Expression.NewArrayInit(typeof(object), init);
2480                         LambdaExpression rs = Expression.Lambda(arrExp, p);
2481                         this.map.Add(p, exp);
2482                         SqlExpression proj = this.VisitExpression(rs.Body);
2483                         preResult = new SqlSelect(proj, null, rs);
2484                     }
2485                     else {
2486                         // case handled in formatter automatically
2487                     }
2488                     result.DoNotOutput = true;
2489                 }
2490
2491                 // combine insert & result into block
2492                 SqlBlock block = new SqlBlock(this.dominatingExpression);
2493                 block.Statements.Add(sin);
2494                 if (preResult != null) {
2495                     block.Statements.Add(preResult);
2496                 }
2497                 block.Statements.Add(result);
2498                 return block;
2499             }
2500         }
2501
2502         private bool IsDbGeneratedKeyProjectionOnly(Expression projection, MetaDataMember keyMember) {
2503             NewArrayExpression array = projection as NewArrayExpression;
2504             if (array != null && array.Expressions.Count == 1) {
2505                 Expression exp = array.Expressions[0];
2506                 while (exp.NodeType == ExpressionType.Convert || exp.NodeType == ExpressionType.ConvertChecked) {
2507                     exp = ((UnaryExpression)exp).Operand;
2508                 }
2509                 MemberExpression mex = exp as MemberExpression;
2510                 if (mex != null && mex.Member == keyMember.Member) {
2511                     return true;
2512                 }
2513             }
2514             return false;
2515         }
2516
2517         private SqlExpression GetIdentityExpression(MetaDataMember id, bool isOutputFromInsert) {
2518             if (isOutputFromInsert) {
2519                 return new SqlVariable(id.Type, sql.Default(id), "@id", this.dominatingExpression);
2520             }
2521             else {
2522                 ProviderType sqlType = sql.Default(id);
2523                 if (!IsLegalIdentityType(sqlType.GetClosestRuntimeType())) {
2524                     throw Error.InvalidDbGeneratedType(sqlType.ToQueryString());
2525                 }
2526                 if ((this.converterStrategy & ConverterStrategy.CanUseScopeIdentity) != 0) {
2527                     return new SqlVariable(typeof(decimal), typeProvider.From(typeof(decimal)), "SCOPE_IDENTITY()", this.dominatingExpression);
2528                 }
2529                 else {
2530                     return new SqlVariable(typeof(decimal), typeProvider.From(typeof(decimal)), "@@IDENTITY", this.dominatingExpression);
2531                 }
2532             }
2533         }
2534
2535         private static bool IsLegalIdentityType(Type type) {
2536             switch (Type.GetTypeCode(type)) {
2537                 case TypeCode.SByte:
2538                 case TypeCode.Int16:
2539                 case TypeCode.Int32:
2540                 case TypeCode.Int64:
2541                 case TypeCode.Decimal:
2542                     return true;
2543             }
2544             return false;
2545         }
2546
2547         private SqlExpression GetRowCountExpression() {
2548             if ((this.converterStrategy & ConverterStrategy.CanUseRowStatus) != 0) {
2549                 return new SqlVariable(typeof(decimal), typeProvider.From(typeof(decimal)), "@@ROWCOUNT", this.dominatingExpression);
2550             }
2551             else {
2552                 return new SqlVariable(typeof(decimal), typeProvider.From(typeof(decimal)), "@ROWCOUNT", this.dominatingExpression);
2553             }
2554         }
2555
2556         private SqlStatement VisitUpdate(Expression item, LambdaExpression check, LambdaExpression resultSelector) {
2557             if (item == null) {
2558                 throw Error.ArgumentNull("item");
2559             }
2560             MetaTable metaTable = this.services.Model.GetTable(item.Type);
2561             Expression source = this.services.Context.GetTable(metaTable.RowType.Type).Expression;
2562             Type rowType = metaTable.RowType.Type;
2563
2564             bool saveAllowDeferred = this.allowDeferred;
2565             this.allowDeferred = false;
2566
2567             try {
2568                 Expression seq = source;
2569                 // construct identity predicate based on supplied item
2570                 ParameterExpression p = Expression.Parameter(rowType, "p");
2571                 LambdaExpression idPredicate = Expression.Lambda(Expression.Equal(p, item), p);
2572
2573                 // combine predicate and check expression into single find predicate
2574                 LambdaExpression findPredicate = idPredicate;
2575                 if (check != null) {
2576                     findPredicate = Expression.Lambda(Expression.And(Expression.Invoke(findPredicate, p), Expression.Invoke(check, p)), p);
2577                 }
2578                 seq = Expression.Call(typeof(Enumerable), "Where", new Type[] { rowType }, seq, findPredicate);
2579
2580                 // source 'query' is based on table + find predicate
2581                 SqlSelect ss = new RetypeCheckClause().VisitSelect(this.VisitSequence(seq));
2582
2583                 // construct update assignments from 'item' info
2584                 List<SqlAssign> assignments = new List<SqlAssign>();
2585                 ConstantExpression conItem = item as ConstantExpression;
2586                 if (conItem == null) {
2587                     throw Error.UpdateItemMustBeConstant();
2588                 }
2589                 if (conItem.Value == null) {
2590                     throw Error.ArgumentNull("item");
2591                 }
2592                 // get changes from data services to construct update command
2593                 Type entityType = conItem.Value.GetType();
2594                 MetaType metaType = this.services.Model.GetMetaType(entityType);
2595                 ITable table = this.services.Context.GetTable(metaType.InheritanceRoot.Type);
2596                 foreach (ModifiedMemberInfo mmi in table.GetModifiedMembers(conItem.Value)) {
2597                     MetaDataMember mdm = metaType.GetDataMember(mmi.Member);
2598                     assignments.Add(
2599                         new SqlAssign(
2600                             sql.Member(ss.Selection, mmi.Member),
2601                             new SqlValue(mdm.Type, this.typeProvider.From(mdm.Type), mmi.CurrentValue, true, source),
2602                             source
2603                             ));
2604                 }
2605
2606                 SqlUpdate upd = new SqlUpdate(ss, assignments, source);
2607
2608                 if (resultSelector == null) {
2609                     return upd;
2610                 }
2611
2612                 SqlSelect select = null;
2613
2614                 // build select to return result
2615                 seq = source;
2616                 seq = Expression.Call(typeof(Enumerable), "Where", new Type[] { rowType }, seq, idPredicate);
2617                 seq = Expression.Call(typeof(Enumerable), "Select", new Type[] { rowType, resultSelector.Body.Type }, seq, resultSelector);
2618                 select = this.VisitSequence(seq);
2619                 select.Where = sql.AndAccumulate(
2620                     sql.Binary(SqlNodeType.GT, this.GetRowCountExpression(), sql.ValueFromObject(0, false, this.dominatingExpression)),
2621                     select.Where
2622                     );
2623
2624                 // combine update & select into statement block
2625                 SqlBlock block = new SqlBlock(source);
2626                 block.Statements.Add(upd);
2627                 block.Statements.Add(select);
2628                 return block;
2629             }
2630             finally {
2631                 this.allowDeferred = saveAllowDeferred;
2632             }
2633         }
2634
2635         private SqlStatement VisitDelete(Expression item, LambdaExpression check) {
2636             if (item == null) {
2637                 throw Error.ArgumentNull("item");
2638             }
2639
2640             bool saveAllowDeferred = this.allowDeferred;
2641             this.allowDeferred = false;
2642
2643             try {
2644                 MetaTable metaTable = this.services.Model.GetTable(item.Type);
2645                 Expression source = this.services.Context.GetTable(metaTable.RowType.Type).Expression;
2646                 Type rowType = metaTable.RowType.Type;
2647
2648                 // construct identity predicate based on supplied item
2649                 ParameterExpression p = Expression.Parameter(rowType, "p");
2650                 LambdaExpression idPredicate = Expression.Lambda(Expression.Equal(p, item), p);
2651
2652                 // combine predicate and check expression into single find predicate
2653                 LambdaExpression findPredicate = idPredicate;
2654                 if (check != null) {
2655                     findPredicate = Expression.Lambda(Expression.And(Expression.Invoke(findPredicate, p), Expression.Invoke(check, p)), p);
2656                 }
2657                 Expression seq = Expression.Call(typeof(Enumerable), "Where", new Type[] { rowType }, source, findPredicate);
2658                 SqlSelect ss = new RetypeCheckClause().VisitSelect(this.VisitSequence(seq));
2659                 this.allowDeferred = saveAllowDeferred;
2660
2661                 SqlDelete sd = new SqlDelete(ss, source);
2662                 return sd;
2663             }
2664             finally {
2665                 this.allowDeferred = saveAllowDeferred;
2666             }
2667         }
2668         private class RetypeCheckClause : SqlVisitor {
2669             internal override SqlExpression VisitMethodCall(SqlMethodCall mc) {
2670                 if (mc.Arguments.Count==2 && mc.Method.Name=="op_Equality") {
2671                     var r = mc.Arguments[1];
2672                     if (r.NodeType == SqlNodeType.Value) {
2673                         var v = (SqlValue)r;
2674                         v.SetSqlType(mc.Arguments[0].SqlType);
2675                     }
2676                 }
2677                 return base.VisitMethodCall(mc);
2678             }
2679         }
2680
2681
2682         private SqlExpression VisitNewArrayInit(NewArrayExpression arr) {
2683             SqlExpression[] exprs = new SqlExpression[arr.Expressions.Count];
2684             for (int i = 0, n = exprs.Length; i < n; i++) {
2685                 exprs[i] = this.VisitExpression(arr.Expressions[i]);
2686             }
2687             return new SqlClientArray(arr.Type, this.typeProvider.From(arr.Type), exprs, this.dominatingExpression);
2688         }
2689
2690         private SqlExpression VisitListInit(ListInitExpression list) {
2691             if (null != list.NewExpression.Constructor && 0 != list.NewExpression.Arguments.Count) {
2692                 // Throw existing exception for unrecognized expressions if list
2693                 // init does not use a default constructor.
2694                 throw Error.UnrecognizedExpressionNode(list.NodeType);
2695             }
2696             SqlExpression[] exprs = new SqlExpression[list.Initializers.Count];
2697             for (int i = 0, n = exprs.Length; i < n; i++) {
2698                 if (1 != list.Initializers[i].Arguments.Count) {
2699                     // Throw existing exception for unrecognized expressions if element
2700                     // init is not adding a single element.
2701                     throw Error.UnrecognizedExpressionNode(list.NodeType);
2702                 }
2703                 exprs[i] = this.VisitExpression(list.Initializers[i].Arguments.Single());
2704             }
2705             return new SqlClientArray(list.Type, this.typeProvider.From(list.Type), exprs, this.dominatingExpression);
2706         }
2707     }
2708
2709     class SingleTableQueryVisitor : SqlVisitor {
2710         public bool IsValid;
2711         bool IsDistinct;
2712         List<MemberInfo> IdentityMembers;
2713
2714         void AddIdentityMembers(IEnumerable<MemberInfo> members) {
2715             System.Diagnostics.Debug.Assert(this.IdentityMembers == null, "We already have a set of keys -- why are we adding more?");
2716             this.IdentityMembers = new List<MemberInfo>(members);
2717         }
2718
2719         internal SingleTableQueryVisitor(): base() {
2720             this.IsValid = true;
2721         }
2722
2723         internal override SqlNode Visit(SqlNode node) {
2724             // recurse until we know we're invalid
2725             if (this.IsValid && node != null) {
2726                 return base.Visit(node);
2727             }
2728
2729             return node;
2730         }
2731
2732         internal override SqlTable VisitTable(SqlTable tab) {
2733             // if we're distinct, we don't care about joins
2734             if (this.IsDistinct) {
2735                 return tab;
2736             }
2737
2738             if (this.IdentityMembers != null) {
2739                 this.IsValid = false;
2740             } else {
2741                 this.AddIdentityMembers(tab.MetaTable.RowType.IdentityMembers.Select(m => m.Member));
2742             }
2743
2744             return tab;
2745         }
2746
2747         internal override SqlSource VisitSource(SqlSource source) {
2748             return base.VisitSource(source);
2749         }
2750
2751         internal override SqlSelect VisitSelect(SqlSelect select) {
2752             if (select.IsDistinct) {
2753                 this.IsDistinct = true;
2754                 // get all members from selection
2755                 this.AddIdentityMembers(select.Selection.ClrType.GetProperties());
2756                 return select;
2757             }
2758
2759             //
2760             //
2761             //
2762             //
2763             //
2764
2765             // We're not distinct, but let's check our sources...
2766             select.From = (SqlSource)base.Visit(select.From);
2767
2768             if (this.IdentityMembers == null || this.IdentityMembers.Count == 0) {
2769                 throw Error.SkipRequiresSingleTableQueryWithPKs();
2770             }
2771             else {
2772                 switch (select.Selection.NodeType) {
2773                     case SqlNodeType.Column:
2774                     case SqlNodeType.ColumnRef:
2775                     case SqlNodeType.Member: {
2776                             // we've got a bare member/column node, eg "select c.CustomerId"
2777                             // find out if it refers to the table's PK, of which there must be only 1
2778                             if (this.IdentityMembers.Count == 1) {
2779                                 MemberInfo column = this.IdentityMembers[0];
2780                                 this.IsValid &= IsColumnMatch(column, select.Selection);
2781                             }
2782                             else {
2783                                 this.IsValid = false;
2784                             }
2785
2786                             break;
2787                         }
2788                     case SqlNodeType.New:
2789                     case SqlNodeType.AliasRef: {
2790                             select.Selection = this.VisitExpression(select.Selection);
2791                             break;
2792                         }
2793                     case SqlNodeType.Treat:
2794                     case SqlNodeType.TypeCase: {
2795                             break;
2796                         }
2797                     default: {
2798                             this.IsValid = false;
2799                             break;
2800                         }
2801                 }
2802             }
2803
2804             return select;
2805         }
2806
2807         //
2808         //
2809         //
2810         //
2811         //
2812
2813         internal override SqlExpression VisitNew(SqlNew sox) {
2814             // check the args for the PKs
2815             foreach (MemberInfo column in this.IdentityMembers) {
2816                 // assume we're invalid unless we find a matching argument which is
2817                 // a bare column/columnRef to the PK
2818                 bool isMatch = false;
2819
2820                 // find a matching arg
2821                 foreach (SqlExpression expr in sox.Args) {
2822                     isMatch = IsColumnMatch(column, expr);
2823
2824                     if (isMatch) {
2825                         break;
2826                     }
2827                 }
2828
2829                 if (!isMatch) {
2830                     foreach (SqlMemberAssign ma in sox.Members) {
2831                         SqlExpression expr = ma.Expression;
2832
2833                         isMatch = IsColumnMatch(column, expr);
2834
2835                         if (isMatch) {
2836                             break;
2837                         }
2838                     }
2839                 }
2840
2841                 this.IsValid &= isMatch;
2842                 if (!this.IsValid) {
2843                     break;
2844                 }
2845             }
2846
2847             return sox;
2848         }
2849
2850         internal override SqlNode VisitUnion(SqlUnion su) {
2851             // we don't want to descend inward
2852
2853             // just check that it's not a UNION ALL
2854             if (su.All) {
2855                 this.IsValid = false;
2856             }
2857
2858             // UNIONs are distinct
2859             this.IsDistinct = true;
2860
2861             // get all members from selection
2862             this.AddIdentityMembers(su.GetClrType().GetProperties());
2863             return su;
2864         }
2865
2866         private static bool IsColumnMatch(MemberInfo column, SqlExpression expr) {
2867             MemberInfo memberInfo = null;
2868
2869             switch (expr.NodeType) {
2870                 case SqlNodeType.Column: {
2871                         memberInfo = ((SqlColumn)expr).MetaMember.Member;
2872                         break;
2873                     }
2874                 case SqlNodeType.ColumnRef: {
2875                         memberInfo = (((SqlColumnRef)expr).Column).MetaMember.Member;
2876                         break;
2877                     }
2878                 case SqlNodeType.Member: {
2879                         memberInfo = ((SqlMember)expr).Member;
2880                         break;
2881                     }
2882             }
2883
2884             return (memberInfo != null && memberInfo == column);
2885         }
2886     }
2887 }