1 //--------------------------------------------------------------------- 2 // <copyright file="Propagator.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 // 6 // @owner Microsoft 7 // @backupOwner Microsoft 8 //--------------------------------------------------------------------- 9 10 namespace System.Data.Mapping.Update.Internal 11 { 12 using System.Data.Common.CommandTrees; 13 using System.Data.Common.Utils; 14 using System.Data.Metadata.Edm; 15 using System.Diagnostics; 16 17 /// <summary> 18 /// <para> 19 /// Comments assume there is a map between the CDM and store. Other maps are possible, but 20 /// for simplicity, we discuss the 'from' portion of the map as the C-Space and the 'to' portion 21 /// of the map as the S-Space. 22 /// </para> 23 /// <para> 24 /// This class translates C-Space change requests into S-Space change requests given a C-Space change 25 /// request, an update view loader, and a target table. It has precisely one entry 26 /// point, the static <see cref="Propagate"/> method. It performs the translation by evaluating an update 27 /// mapping view w.r.t. change requests (propagating a change request through the view). 28 /// </para> 29 /// </summary> 30 /// <remarks> 31 /// <para> 32 /// This class implements propagation rules for the following relational operators in the update mapping 33 /// view: 34 /// </para> 35 /// <list> 36 /// <item>Projection</item> 37 /// <item>Selection (filter)</item> 38 /// <item>Union all</item> 39 /// <item>Inner equijoin</item> 40 /// <item>Left outer equijoin</item> 41 /// </list> 42 /// </remarks> 43 internal partial class Propagator : UpdateExpressionVisitor<ChangeNode> 44 { 45 #region Constructors 46 /// <summary> 47 /// Construct a new propagator. 48 /// </summary> 49 /// <param name="parent">UpdateTranslator supporting retrieval of changes for C-Space 50 /// extents referenced in the update mapping view.</param> 51 /// <param name="table">Table for which updates are being produced.</param> Propagator(UpdateTranslator parent, EntitySet table)52 private Propagator(UpdateTranslator parent, EntitySet table) 53 { 54 // Initialize propagator state. 55 EntityUtil.CheckArgumentNull(parent, "parent"); 56 EntityUtil.CheckArgumentNull(table, "table"); 57 58 m_updateTranslator = parent; 59 m_table = table; 60 } 61 #endregion 62 63 #region Fields 64 private readonly UpdateTranslator m_updateTranslator; 65 private readonly EntitySet m_table; 66 private static readonly string s_visitorName = typeof(Propagator).FullName; 67 #endregion 68 69 #region Properties 70 /// <summary> 71 /// Gets context for updates performed by this propagator. 72 /// </summary> 73 internal UpdateTranslator UpdateTranslator 74 { 75 get { return m_updateTranslator; } 76 } 77 78 override protected string VisitorName 79 { 80 get { return s_visitorName; } 81 } 82 #endregion 83 84 #region Methods 85 /// <summary> 86 /// Propagate changes from C-Space (contained in <paramref name="parent" /> to the S-Space. 87 /// </summary> 88 /// <remarks> 89 /// See Walker class for an explanation of this coding pattern. 90 /// </remarks> 91 /// <param name="parent">Grouper supporting retrieval of changes for C-Space 92 /// extents referenced in the update mapping view.</param> 93 /// <param name="table">Table for which updates are being produced.</param> 94 /// <param name="umView">Update mapping view to propagate.</param> 95 /// <returns>Changes in S-Space.</returns> Propagate(UpdateTranslator parent, EntitySet table, DbQueryCommandTree umView)96 static internal ChangeNode Propagate(UpdateTranslator parent, EntitySet table, DbQueryCommandTree umView) 97 { 98 // Construct a new instance of a propagator, which implements a visitor interface 99 // for expression nodes (nodes in the update mapping view) and returns changes nodes 100 // (seeded by C-Space extent changes returned by the grouper). 101 DbExpressionVisitor<ChangeNode> propagator = new Propagator(parent, table); 102 103 // Walk the update mapping view using the visitor pattern implemented in this class. 104 // The update mapping view describes the S-Space table we're targeting, so the result 105 // returned for the root of view corresponds to changes propagated to the S-Space. 106 return umView.Query.Accept(propagator); 107 } 108 109 /// <summary> 110 /// Utility method constructs a new empty change node. 111 /// </summary> 112 /// <param name="node">Update mapping view node associated with the change.</param> 113 /// <returns>Empty change node with the appropriate type for the view node.</returns> BuildChangeNode(DbExpression node)114 private static ChangeNode BuildChangeNode(DbExpression node) 115 { 116 TypeUsage nodeType = node.ResultType; 117 TypeUsage elementType = MetadataHelper.GetElementType(nodeType); 118 return new ChangeNode(elementType); 119 } 120 121 #region Visitor implementation 122 Visit(DbCrossJoinExpression node)123 public override ChangeNode Visit(DbCrossJoinExpression node) 124 { 125 throw EntityUtil.NotSupported(System.Data.Entity.Strings.Update_UnsupportedJoinType(node.ExpressionKind)); 126 } 127 128 /// <summary> 129 /// Propagates changes across a join expression node by implementing progation rules w.r.t. inputs 130 /// from the left- and right- hand sides of the join. The work is actually performed 131 /// by the <see cref="JoinPropagator" />. 132 /// </summary> 133 /// <param name="node">A join expression node.</param> 134 /// <returns>Results propagated to the given join expression node.</returns> Visit(DbJoinExpression node)135 public override ChangeNode Visit(DbJoinExpression node) 136 { 137 EntityUtil.CheckArgumentNull(node, "node"); 138 139 if (DbExpressionKind.InnerJoin != node.ExpressionKind && DbExpressionKind.LeftOuterJoin != node.ExpressionKind) 140 { 141 throw EntityUtil.NotSupported(System.Data.Entity.Strings.Update_UnsupportedJoinType(node.ExpressionKind)); 142 } 143 144 // There are precisely two inputs to the join which we treat as the left and right children. 145 DbExpression leftExpr = node.Left.Expression; 146 DbExpression rightExpr = node.Right.Expression; 147 148 // Get the results of propagating changes to the left and right inputs to the join. 149 ChangeNode left = Visit(leftExpr); 150 ChangeNode right = Visit(rightExpr); 151 152 // Construct a new join propagator, passing in the left and right results, the actual 153 // join expression, and this parent propagator. 154 JoinPropagator evaluator = new JoinPropagator(left, right, node, this); 155 156 // Execute propagation. 157 ChangeNode result = evaluator.Propagate(); 158 159 return result; 160 } 161 162 /// <summary> 163 /// Given the results returned for the left and right inputs to a union, propagates changes 164 /// through the union. 165 /// 166 /// Propagation rule (U = union node, L = left input, R = right input, D(x) = deleted rows 167 /// in x, I(x) = inserted rows in x) 168 /// 169 /// U = L union R 170 /// D(U) = D(L) union D(R) 171 /// I(U) = I(L) union I(R) 172 /// </summary> 173 /// <param name="node">Union expression node in the update mapping view.</param> 174 /// <returns>Result of propagating changes to this union all node.</returns> Visit(DbUnionAllExpression node)175 public override ChangeNode Visit(DbUnionAllExpression node) 176 { 177 EntityUtil.CheckArgumentNull(node, "node"); 178 179 // Initialize an empty change node result for the union all node 180 ChangeNode result = BuildChangeNode(node); 181 182 // Retrieve result of propagating changes to the left and right children. 183 ChangeNode left = Visit(node.Left); 184 ChangeNode right = Visit(node.Right); 185 186 // Implement insertion propagation rule I(U) = I(L) union I(R) 187 result.Inserted.AddRange(left.Inserted); 188 result.Inserted.AddRange(right.Inserted); 189 190 // Implement deletion progation rule D(U) = D(L) union D(R) 191 result.Deleted.AddRange(left.Deleted); 192 result.Deleted.AddRange(right.Deleted); 193 194 // The choice of side for the placeholder is arbitrary, since CQTs enforce type compatibility 195 // for the left and right hand sides of the union. 196 result.Placeholder = left.Placeholder; 197 198 return result; 199 } 200 201 /// <summary> 202 /// Propagate projection. 203 /// 204 /// Propagation rule (P = projection node, S = projection input, D(x) = deleted rows in x, 205 /// I(x) = inserted rows in x) 206 /// 207 /// P = Proj_f S 208 /// D(P) = Proj_f D(S) 209 /// I(P) = Proj_f I(S) 210 /// </summary> 211 /// <param name="node">Projection expression node.</param> 212 /// <returns>Result of propagating changes to the projection expression node.</returns> Visit(DbProjectExpression node)213 public override ChangeNode Visit(DbProjectExpression node) 214 { 215 EntityUtil.CheckArgumentNull(node, "node"); 216 217 // Initialize an empty change node result for the projection node. 218 ChangeNode result = BuildChangeNode(node); 219 220 // Retrieve result of propagating changes to the input of the projection. 221 ChangeNode input = Visit(node.Input.Expression); 222 223 // Implement propagation rule for insert I(P) = Proj_f I(S) 224 foreach(PropagatorResult row in input.Inserted) 225 { 226 result.Inserted.Add(Project(node, row, result.ElementType)); 227 } 228 229 // Implement propagation rule for delete D(P) = Proj_f D(S) 230 foreach(PropagatorResult row in input.Deleted) 231 { 232 result.Deleted.Add(Project(node, row, result.ElementType)); 233 } 234 235 // Generate a placeholder for the projection node by projecting values in the 236 // placeholder for the input node. 237 result.Placeholder = Project(node, input.Placeholder, result.ElementType); 238 239 return result; 240 } 241 242 /// <summary> 243 /// Performs projection for a single row. Evaluates each projection argument against the specified 244 /// row, returning a result with the specified type. 245 /// </summary> 246 /// <param name="node">Projection expression.</param> 247 /// <param name="row">Row to project.</param> 248 /// <param name="resultType">Type of the projected row.</param> 249 /// <returns>Projected row.</returns> Project(DbProjectExpression node, PropagatorResult row, TypeUsage resultType)250 private PropagatorResult Project(DbProjectExpression node, PropagatorResult row, TypeUsage resultType) 251 { 252 EntityUtil.CheckArgumentNull(node, "node"); 253 254 Debug.Assert(null != node.Projection, "CQT validates DbProjectExpression.Projection property"); 255 256 DbNewInstanceExpression projection = node.Projection as DbNewInstanceExpression; 257 258 if (null == projection) 259 { 260 throw EntityUtil.NotSupported(System.Data.Entity.Strings.Update_UnsupportedProjection(node.Projection.ExpressionKind)); 261 } 262 263 // Initialize empty structure containing space for every element of the projection. 264 PropagatorResult[] projectedValues = new PropagatorResult[projection.Arguments.Count]; 265 266 // Extract value from the input row for every projection argument requested. 267 for (int ordinal = 0; ordinal < projectedValues.Length; ordinal++) 268 { 269 projectedValues[ordinal] = Evaluator.Evaluate(projection.Arguments[ordinal], row, this); 270 } 271 272 // Return a new row containing projected values. 273 PropagatorResult projectedRow = PropagatorResult.CreateStructuralValue(projectedValues, (StructuralType)resultType.EdmType, false); 274 275 return projectedRow; 276 } 277 278 /// <summary> 279 /// Propagation rule (F = filter node, S = input to filter, I(x) = rows inserted 280 /// into x, D(x) = rows deleted from x, Sigma_p = filter predicate) 281 /// 282 /// F = Sigma_p S 283 /// D(F) = Sigma_p D(S) 284 /// I(F) = Sigma_p I(S) 285 /// </summary> 286 /// <param name="node"></param> 287 /// <returns></returns> Visit(DbFilterExpression node)288 public override ChangeNode Visit(DbFilterExpression node) 289 { 290 EntityUtil.CheckArgumentNull(node, "node"); 291 292 // Initialize an empty change node for this filter node. 293 ChangeNode result = BuildChangeNode(node); 294 295 // Retrieve result of propagating changes to the input of the filter. 296 ChangeNode input = Visit(node.Input.Expression); 297 298 // Implement insert propagation rule I(F) = Sigma_p I(S) 299 result.Inserted.AddRange(Evaluator.Filter(node.Predicate, input.Inserted, this)); 300 301 // Implement delete propagation rule D(F) = Sigma_p D(S 302 result.Deleted.AddRange(Evaluator.Filter(node.Predicate, input.Deleted, this)); 303 304 // The placeholder for a filter node is identical to that of the input, which has an 305 // identical shape (type). 306 result.Placeholder = input.Placeholder; 307 308 return result; 309 } 310 311 /// <summary> 312 /// Handles extent expressions (these are the terminal nodes in update mapping views). This handler 313 /// retrieves the changes from the grouper. 314 /// </summary> 315 /// <param name="node">Extent expression node</param> 316 /// <returns></returns> Visit(DbScanExpression node)317 public override ChangeNode Visit(DbScanExpression node) 318 { 319 EntityUtil.CheckArgumentNull(node, "node"); 320 321 // Gets modifications requested for this extent from the grouper. 322 EntitySetBase extent = node.Target; 323 ChangeNode extentModifications = UpdateTranslator.GetExtentModifications(extent); 324 325 if (null == extentModifications.Placeholder) 326 { 327 // Bootstrap placeholder (essentially a record for the extent populated with default values). 328 extentModifications.Placeholder = ExtentPlaceholderCreator.CreatePlaceholder(extent, UpdateTranslator); 329 } 330 331 return extentModifications; 332 } 333 #endregion 334 #endregion 335 } 336 } 337