mcs/class/referencesource/System.Data.Entity/System/Data/Objects/ELinq/OrderByLifter.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="OrderByLifter.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  Microsoft
   7 //---------------------------------------------------------------------
   8
   9 namespace System.Data.Objects.ELinq
  10 {
  11     using System.Data.Common.CommandTrees;
  12     using System.Data.Common.CommandTrees.ExpressionBuilder;
  13     using System.Data.Common.Utils;
  14     using System.Data.Metadata.Edm;
  15     using System.Diagnostics;
  16
  17     internal sealed partial class ExpressionConverter
  18     {
  19         /// <summary>
  20         /// A context-sensitive DbExpression builder class that simulates order preservation
  21         /// for operators (project, filter, oftype, skip and limit) that are not natively order
  22         /// preserving. The builder simulates order preservation by 'lifting' order keys in
  23         /// the expression tree. For instance, source.Sort(o).Where(f) is rewritten as
  24         /// source.Where(f).Sort(o) since otherwise the sort keys would be ignored.
  25         ///
  26         /// In general, the lifter works as follows:
  27         ///
  28         /// - The input to the operator is matched against a series of patterns for intrinsically
  29         ///   ordered expressions.
  30         /// - For each pattern, the lifter encodes the compensation required for each of the
  31         ///   lifting operators that can be applied.
  32         /// </summary>
  33         private sealed class OrderByLifter
  34         {
  35             private readonly AliasGenerator _aliasGenerator;
  36
  37             internal OrderByLifter(AliasGenerator aliasGenerator)
  38             {
  39                 _aliasGenerator = aliasGenerator;
  40             }
  41
  42             #region 'Public' builder methods.
  43             internal DbExpression Project(DbExpressionBinding input, DbExpression projection)
  44             {
  45                 OrderByLifterBase lifter = GetLifter(input.Expression);
  46                 return lifter.Project(input.Project(projection));
  47             }
  48
  49             internal DbExpression Filter(DbExpressionBinding input, DbExpression predicate)
  50             {
  51                 OrderByLifterBase lifter = GetLifter(input.Expression);
  52                 return lifter.Filter(input.Filter(predicate));
  53             }
  54
  55             internal DbExpression OfType(DbExpression argument, TypeUsage type)
  56             {
  57                 OrderByLifterBase lifter = GetLifter(argument);
  58                 return lifter.OfType(type);
  59             }
  60
  61             internal DbExpression Skip(DbExpressionBinding input, DbExpression skipCount)
  62             {
  63                 OrderByLifterBase lifter = GetLifter(input.Expression);
  64                 return lifter.Skip(skipCount);
  65             }
  66
  67             internal DbExpression Limit(DbExpression argument, DbExpression limit)
  68             {
  69                 OrderByLifterBase lifter = GetLifter(argument);
  70                 return lifter.Limit(limit);
  71             }
  72             #endregion
  73
  74             private OrderByLifterBase GetLifter(DbExpression root)
  75             {
  76                 return OrderByLifterBase.GetLifter(root, _aliasGenerator);
  77             }
  78
  79             private abstract class OrderByLifterBase
  80             {
  81                 protected readonly DbExpression _root;
  82                 protected readonly AliasGenerator _aliasGenerator;
  83
  84                 protected OrderByLifterBase(DbExpression root, AliasGenerator aliasGenerator)
  85                 {
  86                     _root = root;
  87                     _aliasGenerator = aliasGenerator;
  88                 }
  89
  90                 /// <summary>
  91                 /// Returns a lifter instance which supports lifting the intrinsic order of the given
  92                 /// source expression across specific operations (filter, project, oftype, skip, and limit)
  93                 /// </summary>
  94                 /// <remarks>
  95                 /// Lifting only occurs for expressions that are ordered. Each of the nested
  96                 /// OrderByLifterBase class implementations represents one or two of the ordered patterns with
  97                 /// the exception of the PassthroughOrderByLifter. The latter class represents expressions
  98                 /// without intrinsic order that therefore require no lifting.
  99                 /// </remarks>
 100                 internal static OrderByLifterBase GetLifter(DbExpression source, AliasGenerator aliasGenerator)
 101                 {
 102                     if (source.ExpressionKind == DbExpressionKind.Sort)
 103                     {
 104                         return new SortLifter((DbSortExpression)source, aliasGenerator);
 105                     }
 106                     if (source.ExpressionKind == DbExpressionKind.Project)
 107                     {
 108                         var project = (DbProjectExpression)source;
 109                         DbExpression projectInput = project.Input.Expression;
 110                         if (projectInput.ExpressionKind == DbExpressionKind.Sort)
 111                         {
 112                             return new ProjectSortLifter(project, (DbSortExpression)projectInput, aliasGenerator);
 113                         }
 114                         if (projectInput.ExpressionKind == DbExpressionKind.Skip)
 115                         {
 116                             return new ProjectSkipLifter(project, (DbSkipExpression)projectInput, aliasGenerator);
 117                         }
 118                         if (projectInput.ExpressionKind == DbExpressionKind.Limit)
 119                         {
 120                             var limit = (DbLimitExpression)projectInput;
 121                             DbExpression limitInput = limit.Argument;
 122                             if (limitInput.ExpressionKind == DbExpressionKind.Sort)
 123                             {
 124                                 return new ProjectLimitSortLifter(project, limit, (DbSortExpression)limitInput, aliasGenerator);
 125                             }
 126                             if (limitInput.ExpressionKind == DbExpressionKind.Skip)
 127                             {
 128                                 return new ProjectLimitSkipLifter(project, limit, (DbSkipExpression)limitInput, aliasGenerator);
 129                             }
 130                         }
 131                     }
 132                     if (source.ExpressionKind == DbExpressionKind.Skip)
 133                     {
 134                         return new SkipLifter((DbSkipExpression)source, aliasGenerator);
 135                     }
 136                     if (source.ExpressionKind == DbExpressionKind.Limit)
 137                     {
 138                         var limit = (DbLimitExpression)source;
 139                         DbExpression limitInput = limit.Argument;
 140                         if (limitInput.ExpressionKind == DbExpressionKind.Sort)
 141                         {
 142                             return new LimitSortLifter(limit, (DbSortExpression)limitInput, aliasGenerator);
 143                         }
 144                         if (limitInput.ExpressionKind == DbExpressionKind.Skip)
 145                         {
 146                             return new LimitSkipLifter(limit, (DbSkipExpression)limitInput, aliasGenerator);
 147                         }
 148                         if (limitInput.ExpressionKind == DbExpressionKind.Project)
 149                         {
 150                             var project = (DbProjectExpression)limitInput;
 151                             DbExpression projectInput = project.Input.Expression;
 152                             if (projectInput.ExpressionKind == DbExpressionKind.Sort)
 153                             {
 154                                 // source.Sort(o).Project(p).Limit(k).* is equivalent to transformation for
 155                                 // source.Sort(o).Limit(k).Project(p).*
 156                                 return new ProjectLimitSortLifter(project, limit, (DbSortExpression)projectInput, aliasGenerator);
 157                             }
 158                             if (projectInput.ExpressionKind == DbExpressionKind.Skip)
 159                             {
 160                                 // source.Skip(k, o).Project(p).Limit(k2).* is equivalent to transformation for
 161                                 // source.Skip(k, o).Limit(k2).Project(p).*
 162                                 return new ProjectLimitSkipLifter(project, limit, (DbSkipExpression)projectInput, aliasGenerator);
 163                             }
 164                         }
 165                     }
 166                     return new PassthroughOrderByLifter(source, aliasGenerator);
 167                 }
 168
 169                 #region Builder methods
 170                 internal abstract DbExpression Project(DbProjectExpression project);
 171                 internal abstract DbExpression Filter(DbFilterExpression filter);
 172                 internal virtual DbExpression OfType(TypeUsage type)
 173                 {
 174                     // s.OfType<T> is normally translated to s.Filter(e => e is T).Project(e => e as T)
 175                     DbExpressionBinding rootBinding = _root.BindAs(_aliasGenerator.Next());
 176                     DbExpression filter = this.Filter(rootBinding.Filter(rootBinding.Variable.IsOf(type)));
 177                     OrderByLifterBase filterLifter = GetLifter(filter, _aliasGenerator);
 178                     DbExpressionBinding filterBinding = filter.BindAs(_aliasGenerator.Next());
 179                     DbExpression project = filterLifter.Project(filterBinding.Project(filterBinding.Variable.TreatAs(type)));
 180                     return project;
 181                 }
 182                 internal abstract DbExpression Limit(DbExpression k);
 183                 internal abstract DbExpression Skip(DbExpression k);
 184                 #endregion
 185
 186                 #region Lambda composition: merge arguments to operators to create a single operator
 187                 protected DbProjectExpression ComposeProject(DbExpression input, DbProjectExpression first, DbProjectExpression second)
 188                 {
 189                     // source.Project(first).Project(second) -> source.Project(e => second(first(e)))
 190
 191                     // create lambda expression representing the second projection (e => second(e))
 192                     DbLambda secondLambda = DbExpressionBuilder.Lambda(second.Projection, second.Input.Variable);
 193
 194                     // invoke lambda with variable from the first projection
 195                     DbProjectExpression composed = first.Input.Project(secondLambda.Invoke(first.Projection));
 196
 197                     return RebindProject(input, composed);
 198                 }
 199
 200                 protected DbFilterExpression ComposeFilter(DbExpression input, DbProjectExpression first, DbFilterExpression second)
 201                 {
 202                     // source.Project(first).Filter(second) -> source.Filter(e => second(first(e)))
 203
 204                     // create lambda expression representing the filter (e => second(e))
 205                     DbLambda secondLambda = DbExpressionBuilder.Lambda(second.Predicate, second.Input.Variable);
 206
 207                     // invoke lambda with variable from the project
 208                     DbFilterExpression composed = first.Input.Filter(secondLambda.Invoke(first.Projection));
 209
 210                     return RebindFilter(input, composed);
 211                 }
 212                 #endregion
 213
 214                 #region Paging op reducers
 215                 protected DbSkipExpression AddToSkip(DbExpression input, DbSkipExpression skip, DbExpression plusK)
 216                 {
 217                     // source.Skip(k, o).Skip(k2) -> source.Skip(k + k2, o)
 218                     DbExpression newCount = CombineIntegers(skip.Count, plusK,
 219                         (l, r) => l + r);
 220                     return RebindSkip(input, skip, newCount);
 221                 }
 222
 223                 protected DbLimitExpression SubtractFromLimit(DbExpression input, DbLimitExpression limit, DbExpression minusK)
 224                 {
 225                     DbExpression newCount = CombineIntegers(limit.Limit, minusK,
 226                         (l, r) => r > l ? 0 : l - r); // can't limit to less than zero rows)
 227                     return DbExpressionBuilder.Limit(input, newCount);
 228                 }
 229
 230                 protected DbLimitExpression MinimumLimit(DbExpression input, DbLimitExpression limit, DbExpression k)
 231                 {
 232                     // source.Limit(k).Limit(k2) -> source.Limit(Min(k, k2))
 233                     DbExpression newCount = CombineIntegers(limit.Limit, k, Math.Min);
 234                     return DbExpressionBuilder.Limit(input, newCount);
 235                 }
 236
 237                 protected DbExpression CombineIntegers(DbExpression left, DbExpression right,
 238                     Func<int, int, int> combineConstants)
 239                 {
 240                     if (left.ExpressionKind == DbExpressionKind.Constant &&
 241                         right.ExpressionKind == DbExpressionKind.Constant)
 242                     {
 243                         object leftValue = ((DbConstantExpression)left).Value;
 244                         object rightValue = ((DbConstantExpression)right).Value;
 245                         if (leftValue is int && rightValue is int)
 246                         {
 247                             return left.ResultType.Constant(combineConstants((int)leftValue, (int)rightValue));
 248                         }
 249                     }
 250                     Debug.Fail("only valid for integer constants");
 251                     throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.UnexpectedLinqLambdaExpressionFormat);
 252                 }
 253                 #endregion
 254
 255                 #region Rebinders: take an operator and apply it to a different input
 256                 protected DbProjectExpression RebindProject(DbExpression input, DbProjectExpression project)
 257                 {
 258                     DbExpressionBinding inputBinding = input.BindAs(project.Input.VariableName);
 259                     return inputBinding.Project(project.Projection);
 260                 }
 261
 262                 protected DbFilterExpression RebindFilter(DbExpression input, DbFilterExpression filter)
 263                 {
 264                     DbExpressionBinding inputBinding = input.BindAs(filter.Input.VariableName);
 265                     return inputBinding.Filter(filter.Predicate);
 266                 }
 267
 268                 protected DbSortExpression RebindSort(DbExpression input, DbSortExpression sort)
 269                 {
 270                     DbExpressionBinding inputBinding = input.BindAs(sort.Input.VariableName);
 271                     return inputBinding.Sort(sort.SortOrder);
 272                 }
 273
 274                 protected DbSortExpression ApplySkipOrderToSort(DbExpression input, DbSkipExpression sortSpec)
 275                 {
 276                     DbExpressionBinding inputBinding = input.BindAs(sortSpec.Input.VariableName);
 277                     return inputBinding.Sort(sortSpec.SortOrder);
 278                 }
 279
 280                 protected DbSkipExpression ApplySortOrderToSkip(DbExpression input, DbSortExpression sort, DbExpression k)
 281                 {
 282                     DbExpressionBinding inputBinding = input.BindAs(sort.Input.VariableName);
 283                     return inputBinding.Skip(sort.SortOrder, k);
 284                 }
 285
 286                 protected DbSkipExpression RebindSkip(DbExpression input, DbSkipExpression skip, DbExpression k)
 287                 {
 288                     DbExpressionBinding inputBinding = input.BindAs(skip.Input.VariableName);
 289                     return inputBinding.Skip(skip.SortOrder, k);
 290                 }
 291                 #endregion
 292             }
 293
 294             /// <summary>
 295             /// Represents an expression of the form: source.Skip(k, o).Limit(k2)
 296             /// </summary>
 297             private class LimitSkipLifter : OrderByLifterBase
 298             {
 299                 private readonly DbLimitExpression _limit;
 300                 private readonly DbSkipExpression _skip;
 301                 private readonly DbExpression _source;
 302
 303                 internal LimitSkipLifter(DbLimitExpression limit, DbSkipExpression skip, AliasGenerator aliasGenerator)
 304                     : base(limit, aliasGenerator)
 305                 {
 306                     _limit = limit;
 307                     _skip = skip;
 308                     _source = skip.Input.Expression;
 309                 }
 310
 311                 internal override DbExpression Filter(DbFilterExpression filter)
 312                 {
 313                     // source.Skip(k, o).Limit(k2).Filter(f) ->
 314                     // source.Skip(k, o).Limit(k2).Filter(f).Sort(o)
 315                     return ApplySkipOrderToSort(filter, _skip);
 316                 }
 317
 318                 internal override DbExpression Project(DbProjectExpression project)
 319                 {
 320                     // the result is already ordered (no compensation is required)
 321                     return project;
 322                 }
 323
 324                 internal override DbExpression Limit(DbExpression k)
 325                 {
 326                     // source.Skip(k, o).Limit(k2).Limit(k3) ->
 327                     // source.Skip(k, o).Limit(Min(k2, k3)) where k2 and k3 are constants
 328                     // otherwise source.Skip(k, o).Limit(k2).Sort(o).Limit(k3)
 329                     if (_limit.Limit.ExpressionKind == DbExpressionKind.Constant &&
 330                         k.ExpressionKind == DbExpressionKind.Constant)
 331                     {
 332                         return MinimumLimit(_skip, _limit, k);
 333                     }
 334                     else
 335                     {
 336                         return ApplySkipOrderToSort(_limit, _skip).Limit(k);
 337                     }
 338                 }
 339
 340                 internal override DbExpression Skip(DbExpression k)
 341                 {
 342                     // source.Skip(k, o).Limit(k2).Skip(k3) ->
 343                     // source.Skip(k, o).Limit(k2).Skip(k3, o)
 344                     return RebindSkip(_limit, _skip, k);
 345                 }
 346             }
 347
 348             /// <summary>
 349             /// Represents an expression of the form: source.Sort(o).Limit(k)
 350             /// </summary>
 351             private class LimitSortLifter : OrderByLifterBase
 352             {
 353                 private readonly DbLimitExpression _limit;
 354                 private readonly DbSortExpression _sort;
 355                 private readonly DbExpression _source;
 356
 357                 internal LimitSortLifter(DbLimitExpression limit, DbSortExpression sort, AliasGenerator aliasGenerator)
 358                     : base(limit, aliasGenerator)
 359                 {
 360                     _limit = limit;
 361                     _sort = sort;
 362                     _source = sort.Input.Expression;
 363                 }
 364
 365                 internal override DbExpression Filter(DbFilterExpression filter)
 366                 {
 367                     // source.Sort(o).Limit(k).Filter(f) -> source.Sort(o).Limit(k).Filter(f).Sort(o)
 368                     return RebindSort(filter, _sort);
 369                 }
 370
 371                 internal override DbExpression Project(DbProjectExpression project)
 372                 {
 373                     // the result is already ordered (no compensation is required)
 374                     return project;
 375                 }
 376
 377                 internal override DbExpression Limit(DbExpression k)
 378                 {
 379                     // source.Sort(o).Limit(k).Limit(k2) -> source.Sort(o).Limit(Min(k, k2)) when k and k2 are constants
 380                     // otherwise -> source.Sort(o).Limit(k).Sort(o).Limit(k2)
 381                     if (_limit.Limit.ExpressionKind == DbExpressionKind.Constant &&
 382                         k.ExpressionKind == DbExpressionKind.Constant)
 383                     {
 384                         return MinimumLimit(_sort, _limit, k);
 385                     }
 386                     else
 387                     {
 388                         return RebindSort(_limit, _sort).Limit(k);
 389                     }
 390                 }
 391
 392                 internal override DbExpression Skip(DbExpression k)
 393                 {
 394                     // source.Sort(o).Limit(k).Skip(k2) -> source.Sort(o).Limit(k).Skip(k2, o)
 395                     return ApplySortOrderToSkip(_limit, _sort, k);
 396                 }
 397             }
 398
 399             /// <summary>
 400             /// Represents an expression of the form: source.Skip(k, o).Limit(k2).Project(p)
 401             /// </summary>
 402             /// <remarks>
 403             /// This class is also used to represent expressions of the form: source.Skip(k, o).Project(p).Limit(k).
 404             /// As a result, the rewrites must be spelled out entirely (the implementation cannot assume that
 405             /// _limit exists in a particular position in the tree)
 406             /// </remarks>
 407             private class ProjectLimitSkipLifter : OrderByLifterBase
 408             {
 409                 private readonly DbProjectExpression _project;
 410                 private readonly DbLimitExpression _limit;
 411                 private readonly DbSkipExpression _skip;
 412                 private readonly DbExpression _source;
 413
 414                 internal ProjectLimitSkipLifter(DbProjectExpression project, DbLimitExpression limit, DbSkipExpression skip, AliasGenerator aliasGenerator)
 415                     : base(project, aliasGenerator)
 416                 {
 417                     _project = project;
 418                     _limit = limit;
 419                     _skip = skip;
 420                     _source = skip.Input.Expression;
 421                 }
 422
 423                 internal override DbExpression Filter(DbFilterExpression filter)
 424                 {
 425                     // source.Skip(k, o).Limit(k2).Project(p).Filter(f) ->
 426                     // source.Skip(k, o).Limit(k2).Filter(e => f(p(e))).Sort(o).Project(p)
 427                     return RebindProject(
 428                         ApplySkipOrderToSort(
 429                             ComposeFilter(
 430                                 DbExpressionBuilder.Limit(_skip, _limit.Limit),
 431                                 _project,
 432                                 filter),
 433                             _skip),
 434                         _project);
 435                 }
 436
 437                 internal override DbExpression Project(DbProjectExpression project)
 438                 {
 439                     // source.Skip(k, o).Limit(k2).Project(p).Project(p2) ->
 440                     // source.Skip(k, o).Limit(k2).Project(e => p2(p(e)))
 441                     return ComposeProject(
 442                         DbExpressionBuilder.Limit(_skip, _limit.Limit),
 443                         _project,
 444                         project);
 445                 }
 446
 447                 internal override DbExpression Limit(DbExpression k)
 448                 {
 449                     // source.Skip(k, o).Limit(k2).Project(p).Limit(k3) ->
 450                     // source.Skip(k, o).Limit(Min(k2, k3)).Project(p) where k2 and k2 are constants
 451                     // otherwise -> source.Skip(k, o).Limit(k2).Sort(o).Limit(k3).Project(p)
 452                     if (_limit.Limit.ExpressionKind == DbExpressionKind.Constant &&
 453                         k.ExpressionKind == DbExpressionKind.Constant)
 454                     {
 455                         return RebindProject(
 456                             MinimumLimit(_skip, _limit, k),
 457                             _project);
 458                     }
 459                     else
 460                     {
 461                         return RebindProject(
 462                             DbExpressionBuilder.Limit(
 463                                 ApplySkipOrderToSort(
 464                                     DbExpressionBuilder.Limit(_skip, _limit.Limit),
 465                                     _skip),
 466                                 k),
 467                             _project);
 468                     }
 469                 }
 470
 471                 internal override DbExpression Skip(DbExpression k)
 472                 {
 473                     // source.Skip(k, o).Limit(k2).Project(p).Skip(k3) ->
 474                     // source.Skip(k + k3, o).Limit(k2 – k3).Project(p) when k, k2 and k3 are constants
 475                     // otherwise -> source.Skip(k, o).Limit(k2).Skip(k3, o).Project(p)
 476                     if (_skip.Count.ExpressionKind == DbExpressionKind.Constant &&
 477                         _limit.Limit.ExpressionKind == DbExpressionKind.Constant &&
 478                         k.ExpressionKind == DbExpressionKind.Constant)
 479                     {
 480                         return RebindProject(
 481                             SubtractFromLimit(
 482                                 AddToSkip(_source, _skip, k),
 483                                 _limit,
 484                                 k),
 485                             _project);
 486                     }
 487                     else
 488                     {
 489                         return RebindProject(
 490                             RebindSkip(
 491                                 DbExpressionBuilder.Limit(_skip, _limit.Limit),
 492                                 _skip,
 493                                 k),
 494                             _project);
 495                     }
 496                 }
 497             }
 498
 499             /// <summary>
 500             /// Represents an expression of the form: source.Sort(o).Limit(k).Project(p)
 501             /// </summary>
 502             /// <remarks>
 503             /// This class is also used to represent expressions of the form: source.Sort(o).Project(p).Limit(k).
 504             /// As a result, the rewrites must be spelled out entirely (the implementation cannot assume that
 505             /// _limit exists in a particular position in the tree)
 506             /// </remarks>
 507             private class ProjectLimitSortLifter : OrderByLifterBase
 508             {
 509                 private readonly DbProjectExpression _project;
 510                 private readonly DbLimitExpression _limit;
 511                 private readonly DbSortExpression _sort;
 512                 private readonly DbExpression _source;
 513
 514                 internal ProjectLimitSortLifter(DbProjectExpression project, DbLimitExpression limit, DbSortExpression sort, AliasGenerator aliasGenerator)
 515                     : base(project, aliasGenerator)
 516                 {
 517                     _project = project;
 518                     _limit = limit;
 519                     _sort = sort;
 520                     _source = sort.Input.Expression;
 521                 }
 522
 523                 internal override DbExpression Filter(DbFilterExpression filter)
 524                 {
 525                     // source.Sort(o).Limit(k).Project(p).Filter(f) -> source.Sort(o).Limit(k).Filter(e => f(p(e))).Sort(o).Project(p)
 526                     return RebindProject(
 527                         RebindSort(
 528                             ComposeFilter(
 529                                 DbExpressionBuilder.Limit(_sort, _limit.Limit),
 530                                 _project,
 531                                 filter),
 532                             _sort),
 533                         _project);
 534                 }
 535
 536                 internal override DbExpression Project(DbProjectExpression project)
 537                 {
 538                     // source.Sort(o).Limit(k).Project(p).Project(p2) -> source.Sort(o).Limit(k).Project(e => p2(p(e)))
 539                     return ComposeProject(
 540                         DbExpressionBuilder.Limit(_sort, _limit.Limit),
 541                         _project,
 542                         project);
 543                 }
 544
 545                 internal override DbExpression Limit(DbExpression k)
 546                 {
 547                     // source.Sort(o).Limit(k).Project(p).Limit(k2) -> source.Sort(o).Limit(Min(k, k2)).Project(p) where k and k2 are constants
 548                     // otherwise -> source.Sort(o).Limit(k).Sort(o).Limit(k2).Project(p)
 549                     if (_limit.Limit.ExpressionKind == DbExpressionKind.Constant &&
 550                         k.ExpressionKind == DbExpressionKind.Constant)
 551                     {
 552                         return RebindProject(
 553                             MinimumLimit(_sort, _limit, k),
 554                             _project);
 555                     }
 556                     else
 557                     {
 558                         return RebindProject(
 559                             DbExpressionBuilder.Limit(
 560                                 RebindSort(
 561                                     DbExpressionBuilder.Limit(_sort, _limit.Limit),
 562                                     _sort),
 563                                 k),
 564                             _project);
 565                     }
 566                 }
 567
 568                 internal override DbExpression Skip(DbExpression k)
 569                 {
 570                     // source.Sort(o).Limit(k).Project(p).Skip(k2) -> source.Sort(o).Limit(k).Skip(k2, o).Project(p)
 571                     return RebindProject(
 572                         ApplySortOrderToSkip(
 573                             DbExpressionBuilder.Limit(_sort, _limit.Limit),
 574                             _sort,
 575                             k),
 576                         _project);
 577                 }
 578             }
 579
 580             /// <summary>
 581             /// Represents an expression of the form: source.Skip(k, o).Project(p)
 582             /// </summary>
 583             private class ProjectSkipLifter : OrderByLifterBase
 584             {
 585                 private readonly DbProjectExpression _project;
 586                 private readonly DbSkipExpression _skip;
 587                 private readonly DbExpression _source;
 588
 589                 internal ProjectSkipLifter(DbProjectExpression project, DbSkipExpression skip, AliasGenerator aliasGenerator)
 590                     : base(project, aliasGenerator)
 591                 {
 592                     _project = project;
 593                     _skip = skip;
 594                     _source = _skip.Input.Expression;
 595                 }
 596
 597                 internal override DbExpression Filter(DbFilterExpression filter)
 598                 {
 599                     // source.Skip(k, o).Project(p).Filter(f) -> source.Skip(k, o).Filter(e => f(p(e))).Sort(o).Project(p)
 600                     return RebindProject(
 601                         ApplySkipOrderToSort(
 602                             ComposeFilter(_skip, _project, filter),
 603                             _skip),
 604                         _project);
 605                 }
 606
 607                 internal override DbExpression Limit(DbExpression k)
 608                 {
 609                     // the result is already ordered (no compensation is required)
 610                     return DbExpressionBuilder.Limit(_root, k);
 611                 }
 612
 613                 internal override DbExpression Project(DbProjectExpression project)
 614                 {
 615                     // source.Skip(k, o).Project(p).Project(p2) -> source.Skip(k, o).Project(e => p2(p(e)))
 616                     return ComposeProject(_skip, _project, project);
 617                 }
 618
 619                 internal override DbExpression Skip(DbExpression k)
 620                 {
 621                     // source.Skip(k, o).Project(p).Skip(k2) -> source.Skip(k + k2, o).Project(p) where k and k2 are constants,
 622                     // otherwise -> source.Skip(k, o).Skip(k2, o).Project(p)
 623                     if (_skip.Count.ExpressionKind == DbExpressionKind.Constant &&
 624                         k.ExpressionKind == DbExpressionKind.Constant)
 625                     {
 626                         return RebindProject(AddToSkip(_source, _skip, k), _project);
 627                     }
 628                     else
 629                     {
 630                         return RebindProject(RebindSkip(_skip, _skip, k), _project);
 631                     }
 632                 }
 633             }
 634
 635             /// <summary>
 636             /// Represents an expression of the form: source.Skip(k, o)
 637             /// </summary>
 638             private class SkipLifter : OrderByLifterBase
 639             {
 640                 private readonly DbSkipExpression _skip;
 641                 private readonly DbExpression _source;
 642
 643                 internal SkipLifter(DbSkipExpression skip, AliasGenerator aliasGenerator)
 644                     : base(skip, aliasGenerator)
 645                 {
 646                     _skip = skip;
 647                     _source = skip.Input.Expression;
 648                 }
 649
 650                 internal override DbExpression Filter(DbFilterExpression filter)
 651                 {
 652                     // source.Skip(k, o).Filter(f) -> source.Skip(k, o).Filter(f).Sort(o)
 653                     return ApplySkipOrderToSort(filter, _skip);
 654                 }
 655
 656                 internal override DbExpression Project(DbProjectExpression project)
 657                 {
 658                     // the result is already ordered (no compensation is required)
 659                     return project;
 660                 }
 661
 662                 internal override DbExpression Limit(DbExpression k)
 663                 {
 664                     // the result is already ordered (no compensation is required)
 665                     return DbExpressionBuilder.Limit(_root, k);
 666                 }
 667
 668                 internal override DbExpression Skip(DbExpression k)
 669                 {
 670                     // source.Skip(k, o).Skip(k2) -> source.Skip(k + k2, o) where k and k2 are both constants
 671                     // otherwise, -> source.Skip(k, o).Skip(k2, o)
 672                     if (_skip.Count.ExpressionKind == DbExpressionKind.Constant &&
 673                         k.ExpressionKind == DbExpressionKind.Constant)
 674                     {
 675                         return AddToSkip(_source, _skip, k);
 676                     }
 677                     else
 678                     {
 679                         return RebindSkip(_skip, _skip, k);
 680                     }
 681                 }
 682             }
 683
 684             /// <summary>
 685             /// Represents an expression of the form: source.Sort(o).Project(p)
 686             /// </summary>
 687             private class ProjectSortLifter : OrderByLifterBase
 688             {
 689                 private readonly DbProjectExpression _project;
 690                 private readonly DbSortExpression _sort;
 691                 private readonly DbExpression _source;
 692
 693                 internal ProjectSortLifter(DbProjectExpression project, DbSortExpression sort, AliasGenerator aliasGenerator)
 694                     : base(project, aliasGenerator)
 695                 {
 696                     _project = project;
 697                     _sort = sort;
 698                     _source = sort.Input.Expression;
 699                 }
 700
 701                 internal override DbExpression Project(DbProjectExpression project)
 702                 {
 703                     // source.Sort(o).Project(p).Project(p2) -> source.Sort(o).Project(e => p2(p(2)))
 704                     return ComposeProject(_sort, _project, project);
 705                 }
 706
 707                 internal override DbExpression Filter(DbFilterExpression filter)
 708                 {
 709                     // source.Sort(o).Project(p).Filter(f) -> source.Filter(e => f(p(e))).Sort(o).Project(p)
 710                     return RebindProject(
 711                         RebindSort(
 712                             ComposeFilter(_source, _project, filter),
 713                             _sort),
 714                         _project);
 715                 }
 716
 717                 internal override DbExpression Limit(DbExpression k)
 718                 {
 719                     // the result is already ordered (no compensation is required)
 720                     return DbExpressionBuilder.Limit(_root, k);
 721                 }
 722
 723                 internal override DbExpression Skip(DbExpression k)
 724                 {
 725                     // source.Sort(o).Project(p).Skip(k) -> source.Skip(k, o).Project(p)
 726                     return RebindProject(ApplySortOrderToSkip(_source, _sort, k), _project);
 727                 }
 728             }
 729
 730             /// <summary>
 731             /// Represents an expression for which there is an explicit order by: source.Sort(o)
 732             /// </summary>
 733             private class SortLifter : OrderByLifterBase
 734             {
 735                 private readonly DbSortExpression _sort;
 736                 private readonly DbExpression _source;
 737
 738                 internal SortLifter(DbSortExpression sort, AliasGenerator aliasGenerator)
 739                     : base(sort, aliasGenerator)
 740                 {
 741                     _sort = sort;
 742                     _source = sort.Input.Expression;
 743                 }
 744
 745                 internal override DbExpression Project(DbProjectExpression project)
 746                 {
 747                     // the result is already ordered (no compensation is required)
 748                     return project;
 749                 }
 750
 751                 internal override DbExpression Filter(DbFilterExpression filter)
 752                 {
 753                     // source.Sort(o).Filter(f) -> source.Filter(f).Sort(o)
 754                     return RebindSort(RebindFilter(_source, filter), _sort);
 755                 }
 756
 757                 internal override DbExpression Limit(DbExpression k)
 758                 {
 759                     // the result is already ordered (no compensation is required)
 760                     return DbExpressionBuilder.Limit(_root, k);
 761                 }
 762
 763                 internal override DbExpression Skip(DbExpression k)
 764                 {
 765                     // source.Sort(o).Skip(k) -> source.Skip(k, o)
 766                     return ApplySortOrderToSkip(_source, _sort, k);
 767                 }
 768             }
 769
 770             /// <summary>
 771             /// Used for sources that do not have any intrinsic order.
 772             /// </summary>
 773             private class PassthroughOrderByLifter : OrderByLifterBase
 774             {
 775                 internal PassthroughOrderByLifter(DbExpression source, AliasGenerator aliasGenerator)
 776                     : base(source, aliasGenerator)
 777                 {
 778                 }
 779
 780                 internal override DbExpression Project(DbProjectExpression project)
 781                 {
 782                     return project;
 783                 }
 784
 785                 internal override DbExpression Filter(DbFilterExpression filter)
 786                 {
 787                     return filter;
 788                 }
 789
 790                 internal override DbExpression OfType(TypeUsage type)
 791                 {
 792                     return DbExpressionBuilder.OfType(_root, type);
 793                 }
 794
 795                 internal override DbExpression Limit(DbExpression k)
 796                 {
 797                     return DbExpressionBuilder.Limit(_root, k);
 798                 }
 799
 800                 internal override DbExpression Skip(DbExpression k)
 801                 {
 802                     // since the source has no intrinsic order, we need to throw (skip
 803                     // requires order)
 804                     throw EntityUtil.NotSupported(System.Data.Entity.Strings.ELinq_SkipWithoutOrder);
 805                 }
 806             }
 807         }
 808     }
 809 }