1 //--------------------------------------------------------------------- 2 // <copyright file="KeyManager.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.Collections.Generic; 11 using System.Data.Common.Utils; 12 using System.Data.Entity; 13 using System.Diagnostics; 14 using NodeColor = System.Byte; 15 16 namespace System.Data.Mapping.Update.Internal 17 { 18 /// <summary> 19 /// Manages interactions between keys in the update pipeline (e.g. via referential constraints) 20 /// </summary> 21 internal class KeyManager 22 { 23 #region Fields 24 private readonly Dictionary<Tuple<EntityKey, string, bool>, int> _foreignKeyIdentifiers = new Dictionary<Tuple<EntityKey, string, bool>, int>(); 25 private readonly Dictionary<EntityKey, EntityKey> _valueKeyToTempKey = new Dictionary<EntityKey, EntityKey>(); 26 private readonly Dictionary<EntityKey, int> _keyIdentifiers = new Dictionary<EntityKey, int>(); 27 private readonly List<IdentifierInfo> _identifiers = new List<IdentifierInfo>() { new IdentifierInfo() }; 28 private readonly UpdateTranslator _translator; 29 private const NodeColor White = 0; 30 private const NodeColor Black = 1; 31 private const NodeColor Gray = 2; 32 #endregion 33 34 #region Constructors KeyManager(UpdateTranslator translator)35 internal KeyManager(UpdateTranslator translator) 36 { 37 _translator = EntityUtil.CheckArgumentNull(translator, "translator"); 38 } 39 #endregion 40 41 #region Methods 42 /// <summary> 43 /// Given an identifier, returns the canonical identifier for the clique including all identifiers 44 /// with the same value (via referential integrity constraints). 45 /// </summary> GetCliqueIdentifier(int identifier)46 internal int GetCliqueIdentifier(int identifier) 47 { 48 Partition partition = _identifiers[identifier].Partition; 49 if (null != partition) 50 { 51 return partition.PartitionId; 52 } 53 // if there is no explicit (count > 1) partition, the node is its own 54 // partition 55 return identifier; 56 } 57 58 /// <summary> 59 /// Indicate that the principal identifier controls the value for the dependent identifier. 60 /// </summary> AddReferentialConstraint(IEntityStateEntry dependentStateEntry, int dependentIdentifier, int principalIdentifier)61 internal void AddReferentialConstraint(IEntityStateEntry dependentStateEntry, int dependentIdentifier, int principalIdentifier) 62 { 63 IdentifierInfo dependentInfo = _identifiers[dependentIdentifier]; 64 65 // A value is trivially constrained to be itself 66 if (dependentIdentifier != principalIdentifier) 67 { 68 // track these as 'equivalent values'; used to determine canonical identifier for dependency 69 // ordering and validation of constraints 70 AssociateNodes(dependentIdentifier, principalIdentifier); 71 72 // remember the constraint 73 LinkedList<int>.Add(ref dependentInfo.References, principalIdentifier); 74 IdentifierInfo principalInfo = _identifiers[principalIdentifier]; 75 LinkedList<int>.Add(ref principalInfo.ReferencedBy, dependentIdentifier); 76 } 77 78 LinkedList<IEntityStateEntry>.Add(ref dependentInfo.DependentStateEntries, dependentStateEntry); 79 } 80 81 /// <summary> 82 /// Given an 'identifier' result, register it as the owner (for purposes of error reporting, 83 /// since foreign key results can sometimes get projected out after a join) 84 /// </summary> RegisterIdentifierOwner(PropagatorResult owner)85 internal void RegisterIdentifierOwner(PropagatorResult owner) 86 { 87 Debug.Assert(PropagatorResult.NullIdentifier != owner.Identifier, "invalid operation for a " + 88 "result without an identifier"); 89 90 _identifiers[owner.Identifier].Owner = owner; 91 } 92 93 /// <summary> 94 /// Checks if the given identifier has a registered 'owner' 95 /// </summary> TryGetIdentifierOwner(int identifier, out PropagatorResult owner)96 internal bool TryGetIdentifierOwner(int identifier, out PropagatorResult owner) 97 { 98 owner = _identifiers[identifier].Owner; 99 return null != owner; 100 } 101 102 /// <summary> 103 /// Gets identifier for an entity key member at the given offset (ordinal of the property 104 /// in the key properties for the relevant entity set) 105 /// </summary> GetKeyIdentifierForMemberOffset(EntityKey entityKey, int memberOffset, int keyMemberCount)106 internal int GetKeyIdentifierForMemberOffset(EntityKey entityKey, int memberOffset, int keyMemberCount) 107 { 108 int result; 109 110 // get offset for first element of key 111 if (!_keyIdentifiers.TryGetValue(entityKey, out result)) 112 { 113 result = _identifiers.Count; 114 for (int i = 0; i < keyMemberCount; i++) 115 { 116 _identifiers.Add(new IdentifierInfo()); 117 } 118 _keyIdentifiers.Add(entityKey, result); 119 } 120 121 // add memberOffset relative to first element of key 122 result += memberOffset; 123 return result; 124 } 125 126 /// <summary> 127 /// Creates identifier for a (non-key) entity member (or return existing identifier). 128 /// </summary> GetKeyIdentifierForMember(EntityKey entityKey, string member, bool currentValues)129 internal int GetKeyIdentifierForMember(EntityKey entityKey, string member, bool currentValues) 130 { 131 int result; 132 var position = Tuple.Create(entityKey, member, currentValues); 133 134 if (!_foreignKeyIdentifiers.TryGetValue(position, out result)) 135 { 136 result = _identifiers.Count; 137 _identifiers.Add(new IdentifierInfo()); 138 _foreignKeyIdentifiers.Add(position, result); 139 } 140 141 return result; 142 } 143 144 /// <summary> 145 /// Gets all relationship entries constrained by the given identifier. If there is a referential constraint 146 /// where the identifier is the principal, returns results corresponding to the constrained 147 /// dependent relationships. 148 /// </summary> GetDependentStateEntries(int identifier)149 internal IEnumerable<IEntityStateEntry> GetDependentStateEntries(int identifier) 150 { 151 return LinkedList<IEntityStateEntry>.Enumerate(_identifiers[identifier].DependentStateEntries); 152 } 153 154 /// <summary> 155 /// Given a value, returns the value for its principal owner. 156 /// </summary> GetPrincipalValue(PropagatorResult result)157 internal object GetPrincipalValue(PropagatorResult result) 158 { 159 int currentIdentifier = result.Identifier; 160 161 if (PropagatorResult.NullIdentifier == currentIdentifier) 162 { 163 // for non-identifiers, there is nothing to resolve 164 return result.GetSimpleValue(); 165 } 166 167 // find principals for this value 168 bool first = true; 169 object value = null; 170 foreach (int principal in GetPrincipals(currentIdentifier)) 171 { 172 PropagatorResult ownerResult = _identifiers[principal].Owner; 173 if (null != ownerResult) 174 { 175 if (first) 176 { 177 // result is taken from the first principal 178 value = ownerResult.GetSimpleValue(); 179 first = false; 180 } 181 else 182 { 183 // subsequent results are validated for consistency with the first 184 if (!ByValueEqualityComparer.Default.Equals(value, ownerResult.GetSimpleValue())) 185 { 186 throw EntityUtil.Constraint(System.Data.Entity.Strings.Update_ReferentialConstraintIntegrityViolation); 187 } 188 } 189 } 190 } 191 192 if (first) 193 { 194 // if there are no principals, return the current value directly 195 value = result.GetSimpleValue(); 196 } 197 return value; 198 } 199 200 /// <summary> 201 /// Gives all principals affecting the given identifier. 202 /// </summary> GetPrincipals(int identifier)203 internal IEnumerable<int> GetPrincipals(int identifier) 204 { 205 return WalkGraph(identifier, (info) => info.References, true); 206 } 207 208 209 /// <summary> 210 /// Gives all direct references of the given identifier 211 /// </summary> GetDirectReferences(int identifier)212 internal IEnumerable<int> GetDirectReferences(int identifier) 213 { 214 LinkedList<int> references = _identifiers[identifier].References; 215 foreach (int i in LinkedList<int>.Enumerate(references)) 216 { 217 yield return i; 218 } 219 } 220 221 /// <summary> 222 /// Gets all dependents affected by the given identifier. 223 /// </summary> GetDependents(int identifier)224 internal IEnumerable<int> GetDependents(int identifier) 225 { 226 return WalkGraph(identifier, (info) => info.ReferencedBy, false); 227 } 228 WalkGraph(int identifier, Func<IdentifierInfo, LinkedList<int>> successorFunction, bool leavesOnly)229 private IEnumerable<int> WalkGraph(int identifier, Func<IdentifierInfo, LinkedList<int>> successorFunction, bool leavesOnly) 230 { 231 var stack = new Stack<int>(); 232 stack.Push(identifier); 233 234 // using a non-recursive implementation to avoid overhead of recursive yields 235 while (stack.Count > 0) 236 { 237 int currentIdentifier = stack.Pop(); 238 LinkedList<int> successors = successorFunction(_identifiers[currentIdentifier]); 239 if (null != successors) 240 { 241 foreach (int successor in LinkedList<int>.Enumerate(successors)) 242 { 243 stack.Push(successor); 244 } 245 if (!leavesOnly) 246 { 247 yield return currentIdentifier; 248 } 249 } 250 else 251 { 252 yield return currentIdentifier; 253 } 254 } 255 } 256 257 /// <summary> 258 /// Checks whether the given identifier has any contributing principals. 259 /// </summary> HasPrincipals(int identifier)260 internal bool HasPrincipals(int identifier) 261 { 262 return null != _identifiers[identifier].References; 263 } 264 265 /// <summary> 266 /// Checks whether there is a cycle in the identifier graph. 267 /// </summary> ValidateReferentialIntegrityGraphAcyclic()268 internal void ValidateReferentialIntegrityGraphAcyclic() 269 { 270 // _identifierRefConstraints describes the referential integrity 271 // 'identifier' graph. How is a conflict 272 // even possible? The state manager does not enforce integrity 273 // constraints but rather forces them to be satisfied. In other words, 274 // the dependent entity takes the value of its parent. If a parent 275 // is also a child however, there is no way of determining which one 276 // controls the value. 277 278 // Standard DFS search 279 280 // Color nodes as we traverse the graph: White means we have not 281 // explored a node yet, Gray means we are currently visiting a node, and Black means 282 // we have finished visiting a node. 283 var color = new NodeColor[_identifiers.Count]; 284 285 for (int i = 0, n = _identifiers.Count; i < n; i++) 286 { 287 if (color[i] == White) 288 { 289 ValidateReferentialIntegrityGraphAcyclic(i, color, null); 290 } 291 } 292 } 293 294 /// <summary> 295 /// Registers an added entity so that it can be matched by a foreign key lookup. 296 /// </summary> RegisterKeyValueForAddedEntity(IEntityStateEntry addedEntry)297 internal void RegisterKeyValueForAddedEntity(IEntityStateEntry addedEntry) 298 { 299 Debug.Assert(null != addedEntry); 300 Debug.Assert(!addedEntry.IsRelationship); 301 Debug.Assert(!addedEntry.IsKeyEntry); 302 Debug.Assert(addedEntry.EntityKey.IsTemporary); 303 304 // map temp key to 'value' key (if all values of the key are non null) 305 EntityKey tempKey = addedEntry.EntityKey; 306 EntityKey valueKey; 307 var keyMembers = addedEntry.EntitySet.ElementType.KeyMembers; 308 var currentValues = addedEntry.CurrentValues; 309 310 object[] keyValues = new object[keyMembers.Count]; 311 bool hasNullValue = false; 312 313 for (int i = 0, n = keyMembers.Count; i < n; i++) 314 { 315 int ordinal = currentValues.GetOrdinal(keyMembers[i].Name); 316 if (currentValues.IsDBNull(ordinal)) 317 { 318 hasNullValue = true; 319 break; 320 } 321 else 322 { 323 keyValues[i] = currentValues.GetValue(ordinal); 324 } 325 } 326 327 if (hasNullValue) 328 { 329 return; 330 } 331 else 332 { 333 valueKey = keyValues.Length == 1 334 ? new EntityKey(addedEntry.EntitySet, keyValues[0]) 335 : new EntityKey(addedEntry.EntitySet, keyValues); 336 } 337 338 if (_valueKeyToTempKey.ContainsKey(valueKey)) 339 { 340 // null indicates that there are collisions on key values 341 _valueKeyToTempKey[valueKey] = null; 342 } 343 else 344 { 345 _valueKeyToTempKey.Add(valueKey, tempKey); 346 } 347 } 348 349 /// <summary> 350 /// There are three states: 351 /// 352 /// - No temp keys with the given value exists (return false, out null) 353 /// - A single temp key exists with the given value (return true, out non null) 354 /// - Multiple temp keys exist with the given value (return true, out null) 355 /// </summary> TryGetTempKey(EntityKey valueKey, out EntityKey tempKey)356 internal bool TryGetTempKey(EntityKey valueKey, out EntityKey tempKey) 357 { 358 return _valueKeyToTempKey.TryGetValue(valueKey, out tempKey); 359 } 360 ValidateReferentialIntegrityGraphAcyclic(int node, NodeColor[] color, LinkedList<int> parent)361 private void ValidateReferentialIntegrityGraphAcyclic(int node, NodeColor[] color, LinkedList<int> parent) 362 { 363 color[node] = Gray; // color the node to indicate we're visiting it 364 LinkedList<int>.Add(ref parent, node); 365 foreach (int successor in LinkedList<int>.Enumerate(_identifiers[node].References)) 366 { 367 switch (color[successor]) 368 { 369 case White: 370 // haven't seen this node yet; visit it 371 ValidateReferentialIntegrityGraphAcyclic(successor, color, parent); 372 break; 373 case Gray: 374 { 375 // recover all affected entities from the path (keep on walking 376 // until we hit the 'successor' again which bounds the cycle) 377 List<IEntityStateEntry> stateEntriesInCycle = new List<IEntityStateEntry>(); 378 foreach (int identifierInCycle in LinkedList<int>.Enumerate(parent)) 379 { 380 PropagatorResult owner = _identifiers[identifierInCycle].Owner; 381 if (null != owner) 382 { 383 stateEntriesInCycle.Add(owner.StateEntry); 384 } 385 386 if (identifierInCycle == successor) 387 { 388 // cycle complete 389 break; 390 } 391 } 392 393 throw EntityUtil.Update(Strings.Update_CircularRelationships, null, stateEntriesInCycle); 394 } 395 default: 396 // done 397 break; 398 } 399 } 400 color[node] = Black; // color the node to indicate we're done visiting it 401 } 402 #endregion 403 404 /// <summary> 405 /// Ensures firstId and secondId belong to the same partition 406 /// </summary> AssociateNodes(int firstId, int secondId)407 internal void AssociateNodes(int firstId, int secondId) 408 { 409 if (firstId == secondId) 410 { 411 // A node is (trivially) associated with itself 412 return; 413 } 414 Partition firstPartition = _identifiers[firstId].Partition; 415 if (null != firstPartition) 416 { 417 Partition secondPartition = _identifiers[secondId].Partition; 418 if (null != secondPartition) 419 { 420 // merge partitions 421 firstPartition.Merge(this, secondPartition); 422 } 423 else 424 { 425 // add y to existing x partition 426 firstPartition.AddNode(this, secondId); 427 } 428 } 429 else 430 { 431 Partition secondPartition = _identifiers[secondId].Partition; 432 if (null != secondPartition) 433 { 434 // add x to existing y partition 435 secondPartition.AddNode(this, firstId); 436 } 437 else 438 { 439 // Neither node is known 440 Partition.CreatePartition(this, firstId, secondId); 441 } 442 } 443 } 444 445 private sealed class Partition 446 { 447 internal readonly int PartitionId; 448 private readonly List<int> _nodeIds; 449 Partition(int partitionId)450 private Partition(int partitionId) 451 { 452 _nodeIds = new List<int>(2); 453 PartitionId = partitionId; 454 } 455 CreatePartition(KeyManager manager, int firstId, int secondId)456 internal static void CreatePartition(KeyManager manager, int firstId, int secondId) 457 { 458 Partition partition = new Partition(firstId); 459 partition.AddNode(manager, firstId); 460 partition.AddNode(manager, secondId); 461 } 462 AddNode(KeyManager manager, int nodeId)463 internal void AddNode(KeyManager manager, int nodeId) 464 { 465 Debug.Assert(!_nodeIds.Contains(nodeId), "don't add existing node to partition"); 466 _nodeIds.Add(nodeId); 467 manager._identifiers[nodeId].Partition = this; 468 } 469 Merge(KeyManager manager, Partition other)470 internal void Merge(KeyManager manager, Partition other) 471 { 472 if (other.PartitionId == this.PartitionId) 473 { 474 return; 475 } 476 foreach (int element in other._nodeIds) 477 { 478 // reparent the node 479 AddNode(manager, element); 480 } 481 } 482 } 483 484 /// <summary> 485 /// Simple linked list class. 486 /// </summary> 487 private sealed class LinkedList<T> 488 { 489 private readonly T _value; 490 private readonly LinkedList<T> _previous; 491 LinkedList(T value, LinkedList<T> previous)492 private LinkedList(T value, LinkedList<T> previous) 493 { 494 _value = value; 495 _previous = previous; 496 } 497 Enumerate(LinkedList<T> current)498 internal static IEnumerable<T> Enumerate(LinkedList<T> current) 499 { 500 while (null != current) 501 { 502 yield return current._value; 503 current = current._previous; 504 } 505 } 506 Add(ref LinkedList<T> list, T value)507 internal static void Add(ref LinkedList<T> list, T value) 508 { 509 list = new LinkedList<T>(value, list); 510 } 511 } 512 513 /// <summary> 514 /// Collects information relevant to a particular identifier. 515 /// </summary> 516 private sealed class IdentifierInfo 517 { 518 internal Partition Partition; 519 internal PropagatorResult Owner; 520 internal LinkedList<IEntityStateEntry> DependentStateEntries; 521 internal LinkedList<int> References; 522 internal LinkedList<int> ReferencedBy; 523 } 524 } 525 } 526