mcs/class/referencesource/System.Data.Entity/System/Data/SqlClient/SqlGen/Sql8ExpressionRewriter.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="Sql8ExpressionRewriter.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Diagnostics;
  13 using System.Globalization;
  14
  15 using System.Data.Common;
  16 using System.Data.Common.CommandTrees;
  17 using System.Data.Common.CommandTrees.Internal;
  18
  19 using System.Data.Metadata.Edm;
  20 using System.Data.Common.CommandTrees.ExpressionBuilder;
  21
  22 namespace System.Data.SqlClient.SqlGen
  23 {
  24     /// <summary>
  25     /// Rewrites an expression tree to make it suitable for translation to SQL appropriate for SQL Server 2000
  26     /// In particular, it replaces expressions that are not directly supported on SQL Server 2000
  27     /// with alternative translations. The following expressions are translated:
  28     /// <list type="bullet">
  29     /// <item><see cref="DbExceptExpression"/></item>
  30     /// <item><see cref="DbIntersectExpression"/></item>
  31     /// <item><see cref="DbSkipExpression"/></item>
  32     /// </list>
  33     ///
  34     /// The other expressions are copied unmodified.
  35     /// The new expression belongs to a new query command tree.
  36     /// </summary>
  37     internal class Sql8ExpressionRewriter : DbExpressionRebinder
  38     {
  39         #region Entry Point
  40         /// <summary>
  41         /// The only entry point.
  42         /// Rewrites the given tree by replacing expressions that are not directly supported on SQL Server 2000
  43         /// with alterntive translations.
  44         /// </summary>
  45         /// <param name="originalTree">The tree to rewrite</param>
  46         /// <returns>The new tree</returns>
  47         internal static DbQueryCommandTree Rewrite(DbQueryCommandTree originalTree)
  48         {
  49             Debug.Assert(originalTree != null, "OriginalTree is null");
  50             Sql8ExpressionRewriter rewriter = new Sql8ExpressionRewriter(originalTree.MetadataWorkspace);
  51             DbExpression newQuery = rewriter.VisitExpression(originalTree.Query);
  52             return DbQueryCommandTree.FromValidExpression(originalTree.MetadataWorkspace, originalTree.DataSpace, newQuery);
  53         }
  54         #endregion
  55
  56         #region Constructor
  57         /// <summary>
  58         /// Private Constructor.
  59         /// </summary>
  60         /// <param name="metadata"></param>
  61         private Sql8ExpressionRewriter(MetadataWorkspace metadata)
  62             :base(metadata)
  63         {
  64         }
  65         #endregion
  66
  67         #region DbExpressionVisitor<DbExpression> Members
  68         /// <summary>
  69         /// <see cref="TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind, IList<DbPropertyExpression> sortExpressionsOverLeft, string sortExpressionsBindingVariableName)"/>
  70         /// </summary>
  71         /// <param name="e"></param>
  72         /// <returns></returns>
  73         public override DbExpression Visit(DbExceptExpression e)
  74         {
  75             return TransformIntersectOrExcept(VisitExpression(e.Left), VisitExpression(e.Right), DbExpressionKind.Except);
  76         }
  77
  78         /// <summary>
  79         /// <see cref="TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind, IList<DbPropertyExpression> sortExpressionsOverLeft, string sortExpressionsBindingVariableName)"/>
  80         /// </summary>
  81         /// <param name="e"></param>
  82         /// <returns></returns>
  83         public override DbExpression Visit(DbIntersectExpression e)
  84         {
  85             return TransformIntersectOrExcept(VisitExpression(e.Left), VisitExpression(e.Right), DbExpressionKind.Intersect);
  86         }
  87
  88         /// <summary>
  89         /// Logicaly, <see cref="DbSkipExpression"/> translates to:
  90         /// SELECT Y.x1, Y.x2, ..., Y.xn
  91         /// FROM (
  92         ///     SELECT X.x1, X.x2, ..., X.xn,
  93         ///     FROM input AS X
  94         ///        EXCEPT
  95         ///     SELECT TOP(count) Z.x1, Z.x2, ..., Z.xn
  96         ///     FROM input AS Z
  97         ///     ORDER BY sk1, sk2, ...
  98         ///     ) AS Y
  99         /// ORDER BY sk1, sk2, ...
 100         ///
 101         /// Here, input refers to the input of the <see cref="DbSkipExpression"/>, and count to the count property of the <see cref="DbSkipExpression"/>.
 102         /// The implementation of EXCEPT is non-duplicate eliminating, and does equality comparison only over the
 103         /// equality comparable columns of the input.
 104         ///
 105         /// This corresponds to the following expression tree:
 106         ///
 107         /// SORT
 108         ///  |
 109         /// NON-DISTINCT EXCEPT  (specially translated, <see cref="TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind, IList<DbPropertyExpression> sortExpressionsOverLeft, string sortExpressionsBindingVariableName)"/>
 110         ///  |
 111         ///  | - Left:  clone of input
 112         ///  | - Right:
 113         ///       |
 114         ///      Limit
 115         ///       |
 116         ///       | - Limit: Count
 117         ///       | - Input
 118         ///             |
 119         ///            Sort
 120         ///             |
 121         ///            input
 122         ///
 123         /// </summary>
 124         /// <param name="e"></param>
 125         /// <returns></returns>
 126         public override DbExpression Visit(DbSkipExpression e)
 127         {
 128             //Build the right input of the except
 129             DbExpression rightInput = VisitExpressionBinding(e.Input).Sort(VisitSortOrder(e.SortOrder)).Limit(VisitExpression(e.Count));
 130
 131             //Build the left input for the except
 132             DbExpression leftInput = VisitExpression(e.Input.Expression); //Another copy of the input
 133
 134             IList<DbSortClause> sortOrder = VisitSortOrder(e.SortOrder); //Another copy of the sort order
 135
 136             // Create a list of the sort expressions to be used for translating except
 137             IList<DbPropertyExpression> sortExpressions = new List<DbPropertyExpression>(e.SortOrder.Count);
 138             foreach (DbSortClause sortClause in sortOrder)
 139             {
 140                 //We only care about property expressions, not about constants
 141                 if (sortClause.Expression.ExpressionKind == DbExpressionKind.Property)
 142                 {
 143                     sortExpressions.Add((DbPropertyExpression)sortClause.Expression);
 144                 }
 145             }
 146
 147             DbExpression exceptExpression = TransformIntersectOrExcept(leftInput, rightInput, DbExpressionKind.Skip, sortExpressions, e.Input.VariableName);
 148
 149             DbExpression result = exceptExpression.BindAs(e.Input.VariableName).Sort(sortOrder);
 150
 151             return result;
 152         }
 153         #endregion
 154
 155         #region DbExpressionVisitor<DbExpression> Member Helpers
 156
 157         /// <summary>
 158         /// This method is invoked when tranforming <see cref="DbIntersectExpression"/> and <see cref="DbExceptExpression"/> by doing comparison over all input columns.
 159         /// <see cref="TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind, IList<DbPropertyExpression> sortExpressionsOverLeft, string sortExpressionsBindingVariableName)"/>
 160         /// </summary>
 161         /// <param name="left"></param>
 162         /// <param name="right"></param>
 163         /// <param name="expressionKind"></param>
 164         /// <returns></returns>
 165         private DbExpression TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind)
 166         {
 167             return TransformIntersectOrExcept( left,  right,  expressionKind, null, null);
 168         }
 169
 170         /// <summary>
 171         /// This method is used for translating <see cref="DbIntersectExpression"/> and <see cref="DbExceptExpression"/>,
 172         /// and for translating the "Except" part of <see cref="DbSkipExpression"/>.
 173         /// into the follwoing expression:
 174         ///
 175         /// A INTERSECT B, A EXCEPT B
 176         ///
 177         /// (DISTINCT)
 178         ///  |
 179         /// FILTER
 180         ///  |
 181         ///  | - Input: A
 182         ///  | - Predicate:(NOT)
 183         ///                 |
 184         ///                 ANY
 185         ///                 |
 186         ///                 | - Input: B
 187         ///                 | - Predicate:  (B.b1 = A.a1 or (B.b1 is null and A.a1 is null))
 188         ///                             AND (B.b2 = A.a2 or (B.b2 is null and A.a2 is null))
 189         ///                             AND ...
 190         ///                             AND (B.bn = A.an or (B.bn is null and A.an is null)))
 191         ///
 192         /// Here, A corresponds to right and B to left.
 193         /// (NOT) is present when transforming Except
 194         /// for the purpose of translating <see cref="DbExceptExpression"/> or <see cref="DbSkipExpression"/>.
 195         /// (DISTINCT) is present when transforming for the purpose of translating
 196         /// <see cref="DbExceptExpression"/> or <see cref="DbIntersectExpression"/>.
 197         ///
 198         /// For <see cref="DbSkipExpression"/>, the input to ANY is caped with project which projects out only
 199         /// the columns represented in the sortExpressionsOverLeft list and only these are used in the predicate.
 200         /// This is because we want to support skip over input with non-equal comarable columns and we have no way to recognize these.
 201         /// </summary>
 202         /// <param name="left"></param>
 203         /// <param name="right"></param>
 204         /// <param name="expressionKind"></param>
 205         /// <param name="sortExpressionsOverLeft">note that this list gets destroyed by this method</param>
 206         /// <param name="sortExpressionsBindingVariableName"></param>
 207         /// <returns></returns>
 208         private DbExpression TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind, IList<DbPropertyExpression> sortExpressionsOverLeft, string sortExpressionsBindingVariableName)
 209         {
 210             bool negate = (expressionKind == DbExpressionKind.Except) || (expressionKind == DbExpressionKind.Skip);
 211             bool distinct = (expressionKind == DbExpressionKind.Except) || (expressionKind == DbExpressionKind.Intersect);
 212
 213             DbExpressionBinding leftInputBinding = left.Bind();
 214             DbExpressionBinding rightInputBinding = right.Bind();
 215
 216             IList<DbPropertyExpression> leftFlattenedProperties = new List<DbPropertyExpression>();
 217             IList<DbPropertyExpression> rightFlattenedProperties = new List<DbPropertyExpression>();
 218
 219             FlattenProperties(leftInputBinding.Variable, leftFlattenedProperties);
 220             FlattenProperties(rightInputBinding.Variable, rightFlattenedProperties);
 221
 222             //For Skip, we need to ignore any columns that are not in the original sort list. We can recognize these by comparing the left flattened properties and
 223             // the properties in the list sortExpressionsOverLeft
 224             // If any such columns exist, we need to add an additional project, to keep the rest of the columns from being projected, as if any among these
 225             // are non equal comparable, SQL Server 2000 throws.
 226             if (expressionKind == DbExpressionKind.Skip)
 227             {
 228                 if (RemoveNonSortProperties(leftFlattenedProperties, rightFlattenedProperties, sortExpressionsOverLeft, leftInputBinding.VariableName, sortExpressionsBindingVariableName))
 229                 {
 230                    rightInputBinding = CapWithProject(rightInputBinding, rightFlattenedProperties);
 231                 }
 232             }
 233
 234             Debug.Assert(leftFlattenedProperties.Count == rightFlattenedProperties.Count, "The left and the right input to INTERSECT or EXCEPT have a different number of properties");
 235             Debug.Assert(leftFlattenedProperties.Count != 0, "The inputs to INTERSECT or EXCEPT have no properties");
 236
 237             //Build the predicate for the quantifier:
 238             //   (B.b1 = A.a1 or (B.b1 is null and A.a1 is null))
 239             //      AND (B.b2 = A.a2 or (B.b2 is null and A.a2 is null))
 240             //      AND ...
 241             //      AND (B.bn = A.an or (B.bn is null and A.an is null)))
 242             DbExpression existsPredicate = null;
 243
 244             for (int i = 0; i < leftFlattenedProperties.Count; i++)
 245             {
 246                 //A.ai == B.bi
 247                 DbExpression equalsExpression = leftFlattenedProperties[i].Equal(rightFlattenedProperties[i]);
 248
 249                 //A.ai is null AND B.bi is null
 250                 DbExpression leftIsNullExpression = leftFlattenedProperties[i].IsNull();
 251                 DbExpression rightIsNullExpression = rightFlattenedProperties[i].IsNull();
 252                 DbExpression bothNullExpression = leftIsNullExpression.And(rightIsNullExpression);
 253
 254                 DbExpression orExpression = equalsExpression.Or(bothNullExpression);
 255
 256                 if (i == 0)
 257                 {
 258                     existsPredicate = orExpression;
 259                 }
 260                 else
 261                 {
 262                     existsPredicate = existsPredicate.And(orExpression);
 263                 }
 264             }
 265
 266             //Build the quantifier
 267             DbExpression quantifierExpression = rightInputBinding.Any(existsPredicate);
 268
 269             DbExpression filterPredicate;
 270
 271             //Negate if needed
 272             if (negate)
 273             {
 274                 filterPredicate = quantifierExpression.Not();
 275             }
 276             else
 277             {
 278                 filterPredicate = quantifierExpression;
 279             }
 280
 281             //Build the filter
 282             DbExpression result = leftInputBinding.Filter(filterPredicate);
 283
 284             //Apply distinct in needed
 285             if (distinct)
 286             {
 287                 result = result.Distinct();
 288             }
 289
 290             return result;
 291         }
 292
 293         /// <summary>
 294         /// Adds the flattened properties on the input to the flattenedProperties list.
 295         /// </summary>
 296         /// <param name="input"></param>
 297         /// <param name="flattenedProperties"></param>
 298         private void FlattenProperties(DbExpression input, IList<DbPropertyExpression> flattenedProperties)
 299         {
 300             IList<EdmProperty> properties = TypeHelpers.GetProperties(input.ResultType);
 301             Debug.Assert(properties.Count != 0, "No nested properties when FlattenProperties called?");
 302
 303             for (int i = 0; i < properties.Count; i++)
 304             {
 305                 DbExpression propertyInput = input;
 306
 307                 DbPropertyExpression propertyExpression = propertyInput.Property(properties[i]);
 308                 if (TypeSemantics.IsPrimitiveType(properties[i].TypeUsage))
 309                 {
 310                     flattenedProperties.Add(propertyExpression);
 311                 }
 312                 else
 313                 {
 314                     Debug.Assert(TypeSemantics.IsEntityType(properties[i].TypeUsage) || TypeSemantics.IsRowType(properties[i].TypeUsage),
 315                         "The input to FlattenProperties is not of EntityType or RowType?");
 316
 317                     FlattenProperties(propertyExpression, flattenedProperties);
 318                 }
 319             }
 320         }
 321
 322
 323         /// <summary>
 324         /// Helper method for <see cref="TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind, IList<DbPropertyExpression> sortExpressionsOverLeft, string sortExpressionsBindingVariableName)"/>
 325         /// Removes all pairs of property expressions from list1 and list2, for which the property expression in list1
 326         /// does not have a 'matching' property expression in list2.
 327         /// The lists list1 and list2 are known to not create duplicate, and the purpose of the sortList is just for this method.
 328         /// Thus, to optimize the match process, we remove the seen property expressions from the sort list in <see cref="HasMatchInList"/>
 329         /// when iterating both list simultaneously.
 330         /// </summary>
 331         /// <param name="list1"></param>
 332         /// <param name="list2"></param>
 333         /// <param name="sortList"></param>
 334         /// <param name="list1BindingVariableName"></param>
 335         /// <param name="sortExpressionsBindingVariableName"></param>
 336         /// <returns></returns>
 337         private static bool RemoveNonSortProperties(IList<DbPropertyExpression> list1, IList<DbPropertyExpression> list2, IList<DbPropertyExpression> sortList, string list1BindingVariableName, string sortExpressionsBindingVariableName)
 338         {
 339             bool result = false;
 340             for (int i = list1.Count - 1; i >= 0; i--)
 341             {
 342                 if (!HasMatchInList(list1[i], sortList, list1BindingVariableName, sortExpressionsBindingVariableName))
 343                 {
 344                     list1.RemoveAt(i);
 345                     list2.RemoveAt(i);
 346                     result = true;
 347                 }
 348             }
 349             return result;
 350         }
 351
 352         /// <summary>
 353         /// Helper method for <see cref="RemoveNonSortProperties"/>
 354         /// Checks whether expr has a 'match' in the given list of property expressions.
 355         /// If it does, the matching expression is removed form the list, to speed up future matching.
 356         /// </summary>
 357         /// <param name="expr"></param>
 358         /// <param name="sortList"></param>
 359         /// <param name="exprBindingVariableName"></param>
 360         /// <param name="sortExpressionsBindingVariableName"></param>
 361         /// <returns></returns>
 362         private static bool HasMatchInList(DbPropertyExpression expr, IList<DbPropertyExpression> list, string exprBindingVariableName, string listExpressionsBindingVariableName)
 363         {
 364             for (int i=0; i<list.Count; i++)
 365             {
 366                 if (AreMatching(expr, list[i], exprBindingVariableName, listExpressionsBindingVariableName))
 367                 {
 368                     // This method is used for matching element of two list without duplicates,
 369                     // thus if match is found, remove it from the list, to speed up future matching.
 370                     list.RemoveAt(i);
 371                     return true;
 372                 }
 373             }
 374             return false;
 375         }
 376
 377         /// <summary>
 378         /// Determines whether two expressions match.
 379         /// They match if they are  of the shape
 380         ///   expr1 -> DbPropertyExpression(... (DbPropertyExpression(DbVariableReferenceExpression(expr1BindingVariableName), nameX), ..., name1)
 381         ///   expr1 -> DbPropertyExpression(... (DbPropertyExpression(DbVariableReferenceExpression(expr2BindingVariableName), nameX), ..., name1),
 382         ///
 383         /// i.e. if they only differ in the name of the binding.
 384         /// </summary>
 385         /// <param name="expr1"></param>
 386         /// <param name="expr2"></param>
 387         /// <param name="expr1BindingVariableName"></param>
 388         /// <param name="expr2BindingVariableName"></param>
 389         /// <returns></returns>
 390         private static bool AreMatching(DbPropertyExpression expr1, DbPropertyExpression expr2, string expr1BindingVariableName, string expr2BindingVariableName)
 391         {
 392             if (expr1.Property.Name != expr2.Property.Name)
 393             {
 394                 return false;
 395             }
 396
 397             if (expr1.Instance.ExpressionKind != expr2.Instance.ExpressionKind)
 398             {
 399                 return false;
 400             }
 401
 402             if (expr1.Instance.ExpressionKind == DbExpressionKind.Property)
 403             {
 404                 return AreMatching((DbPropertyExpression)expr1.Instance, (DbPropertyExpression)expr2.Instance, expr1BindingVariableName, expr2BindingVariableName);
 405             }
 406
 407             DbVariableReferenceExpression instance1 =  (DbVariableReferenceExpression)expr1.Instance;
 408             DbVariableReferenceExpression instance2 =  (DbVariableReferenceExpression)expr2.Instance;
 409
 410             return (String.Equals(instance1.VariableName, expr1BindingVariableName, StringComparison.Ordinal)
 411                 && String.Equals(instance2.VariableName, expr2BindingVariableName, StringComparison.Ordinal));
 412         }
 413
 414         /// <summary>
 415         /// Helper method for <see cref="TransformIntersectOrExcept(DbExpression left, DbExpression right, DbExpressionKind expressionKind, IList<DbPropertyExpression> sortExpressionsOverLeft, string sortExpressionsBindingVariableName)"/>
 416         /// Creates a <see cref="DbProjectExpression"/> over the given inputBinding that projects out the given flattenedProperties.
 417         /// and updates the flattenedProperties to be over the newly created project.
 418         /// </summary>
 419         /// <param name="inputBinding"></param>
 420         /// <param name="flattenedProperties"></param>
 421         /// <returns>An <see cref="DbExpressionBinding"/> over the newly created <see cref="DbProjectExpression"/></returns>
 422         private DbExpressionBinding CapWithProject(DbExpressionBinding inputBinding, IList<DbPropertyExpression> flattenedProperties)
 423         {
 424             List<KeyValuePair<string, DbExpression>> projectColumns = new List<KeyValuePair<string, DbExpression>>(flattenedProperties.Count);
 425
 426             //List of all the columnNames used in the projection.
 427             Dictionary<string, int> columnNames = new Dictionary<string, int>(flattenedProperties.Count);
 428
 429             foreach (DbPropertyExpression pe in flattenedProperties)
 430             {
 431                 //There may be conflicting property names, thus we may need to rename.
 432                 string name = pe.Property.Name;
 433                 int i;
 434                 if (columnNames.TryGetValue(name, out i))
 435                 {
 436                     string newName;
 437                     do
 438                     {
 439                         ++i;
 440                         newName = name + i.ToString(System.Globalization.CultureInfo.InvariantCulture);
 441                     } while (columnNames.ContainsKey(newName));
 442
 443                     columnNames[name] = i;
 444                     name = newName;
 445                 }
 446
 447                 // Add this column name to list of known names so that there are no subsequent
 448                 // collisions
 449                 columnNames[name] = 0;
 450                 projectColumns.Add(new KeyValuePair<string, DbExpression>(name, pe));
 451             }
 452
 453             //Build the project
 454             DbExpression rowExpr = DbExpressionBuilder.NewRow(projectColumns);
 455             DbProjectExpression projectExpression = inputBinding.Project(rowExpr);
 456
 457             //Create the new inputBinding
 458             DbExpressionBinding resultBinding = projectExpression.Bind();
 459
 460             //Create the list of flattenedProperties over the new project
 461             flattenedProperties.Clear();
 462             RowType rowExprType = (RowType)rowExpr.ResultType.EdmType;
 463
 464             foreach (KeyValuePair<string, DbExpression> column in projectColumns)
 465             {
 466                 EdmProperty prop = rowExprType.Properties[column.Key];
 467                 flattenedProperties.Add(resultBinding.Variable.Property(prop));
 468             }
 469             return resultBinding;
 470         }
 471
 472         #endregion
 473     }
 474 }