1
//---------------------------------------------------------------------
2 // <copyright file="KeyManager.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
7 // @backupOwner Microsoft
8 //---------------------------------------------------------------------
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
;
16 namespace System
.Data
.Mapping
.Update
.Internal
19 /// Manages interactions between keys in the update pipeline (e.g. via referential constraints)
21 internal class KeyManager
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;
35 internal KeyManager(UpdateTranslator translator
)
37 _translator
= EntityUtil
.CheckArgumentNull(translator
, "translator");
43 /// Given an identifier, returns the canonical identifier for the clique including all identifiers
44 /// with the same value (via referential integrity constraints).
46 internal int GetCliqueIdentifier(int identifier
)
48 Partition partition
= _identifiers
[identifier
].Partition
;
49 if (null != partition
)
51 return partition
.PartitionId
;
53 // if there is no explicit (count > 1) partition, the node is its own
59 /// Indicate that the principal identifier controls the value for the dependent identifier.
61 internal void AddReferentialConstraint(IEntityStateEntry dependentStateEntry
, int dependentIdentifier
, int principalIdentifier
)
63 IdentifierInfo dependentInfo
= _identifiers
[dependentIdentifier
];
65 // A value is trivially constrained to be itself
66 if (dependentIdentifier
!= principalIdentifier
)
68 // track these as 'equivalent values'; used to determine canonical identifier for dependency
69 // ordering and validation of constraints
70 AssociateNodes(dependentIdentifier
, principalIdentifier
);
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
);
78 LinkedList
<IEntityStateEntry
>.Add(ref dependentInfo
.DependentStateEntries
, dependentStateEntry
);
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)
85 internal void RegisterIdentifierOwner(PropagatorResult owner
)
87 Debug
.Assert(PropagatorResult
.NullIdentifier
!= owner
.Identifier
, "invalid operation for a " +
88 "result without an identifier");
90 _identifiers
[owner
.Identifier
].Owner
= owner
;
94 /// Checks if the given identifier has a registered 'owner'
96 internal bool TryGetIdentifierOwner(int identifier
, out PropagatorResult owner
)
98 owner
= _identifiers
[identifier
].Owner
;
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)
106 internal int GetKeyIdentifierForMemberOffset(EntityKey entityKey
, int memberOffset
, int keyMemberCount
)
110 // get offset for first element of key
111 if (!_keyIdentifiers
.TryGetValue(entityKey
, out result
))
113 result
= _identifiers
.Count
;
114 for (int i
= 0; i
< keyMemberCount
; i
++)
116 _identifiers
.Add(new IdentifierInfo());
118 _keyIdentifiers
.Add(entityKey
, result
);
121 // add memberOffset relative to first element of key
122 result
+= memberOffset
;
127 /// Creates identifier for a (non-key) entity member (or return existing identifier).
129 internal int GetKeyIdentifierForMember(EntityKey entityKey
, string member
, bool currentValues
)
132 var position
= Tuple
.Create(entityKey
, member
, currentValues
);
134 if (!_foreignKeyIdentifiers
.TryGetValue(position
, out result
))
136 result
= _identifiers
.Count
;
137 _identifiers
.Add(new IdentifierInfo());
138 _foreignKeyIdentifiers
.Add(position
, result
);
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.
149 internal IEnumerable
<IEntityStateEntry
> GetDependentStateEntries(int identifier
)
151 return LinkedList
<IEntityStateEntry
>.Enumerate(_identifiers
[identifier
].DependentStateEntries
);
155 /// Given a value, returns the value for its principal owner.
157 internal object GetPrincipalValue(PropagatorResult result
)
159 int currentIdentifier
= result
.Identifier
;
161 if (PropagatorResult
.NullIdentifier
== currentIdentifier
)
163 // for non-identifiers, there is nothing to resolve
164 return result
.GetSimpleValue();
167 // find principals for this value
170 foreach (int principal
in GetPrincipals(currentIdentifier
))
172 PropagatorResult ownerResult
= _identifiers
[principal
].Owner
;
173 if (null != ownerResult
)
177 // result is taken from the first principal
178 value = ownerResult
.GetSimpleValue();
183 // subsequent results are validated for consistency with the first
184 if (!ByValueEqualityComparer
.Default
.Equals(value, ownerResult
.GetSimpleValue()))
186 throw EntityUtil
.Constraint(System
.Data
.Entity
.Strings
.Update_ReferentialConstraintIntegrityViolation
);
194 // if there are no principals, return the current value directly
195 value = result
.GetSimpleValue();
201 /// Gives all principals affecting the given identifier.
203 internal IEnumerable
<int> GetPrincipals(int identifier
)
205 return WalkGraph(identifier
, (info
) => info
.References
, true);
210 /// Gives all direct references of the given identifier
212 internal IEnumerable
<int> GetDirectReferences(int identifier
)
214 LinkedList
<int> references
= _identifiers
[identifier
].References
;
215 foreach (int i
in LinkedList
<int>.Enumerate(references
))
222 /// Gets all dependents affected by the given identifier.
224 internal IEnumerable
<int> GetDependents(int identifier
)
226 return WalkGraph(identifier
, (info
) => info
.ReferencedBy
, false);
229 private IEnumerable
<int> WalkGraph(int identifier
, Func
<IdentifierInfo
, LinkedList
<int>> successorFunction
, bool leavesOnly
)
231 var stack
= new Stack
<int>();
232 stack
.Push(identifier
);
234 // using a non-recursive implementation to avoid overhead of recursive yields
235 while (stack
.Count
> 0)
237 int currentIdentifier
= stack
.Pop();
238 LinkedList
<int> successors
= successorFunction(_identifiers
[currentIdentifier
]);
239 if (null != successors
)
241 foreach (int successor
in LinkedList
<int>.Enumerate(successors
))
243 stack
.Push(successor
);
247 yield return currentIdentifier
;
252 yield return currentIdentifier
;
258 /// Checks whether the given identifier has any contributing principals.
260 internal bool HasPrincipals(int identifier
)
262 return null != _identifiers
[identifier
].References
;
266 /// Checks whether there is a cycle in the identifier graph.
268 internal void ValidateReferentialIntegrityGraphAcyclic()
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.
278 // Standard DFS search
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
];
285 for (int i
= 0, n
= _identifiers
.Count
; i
< n
; i
++)
287 if (color
[i
] == White
)
289 ValidateReferentialIntegrityGraphAcyclic(i
, color
, null);
295 /// Registers an added entity so that it can be matched by a foreign key lookup.
297 internal void RegisterKeyValueForAddedEntity(IEntityStateEntry addedEntry
)
299 Debug
.Assert(null != addedEntry
);
300 Debug
.Assert(!addedEntry
.IsRelationship
);
301 Debug
.Assert(!addedEntry
.IsKeyEntry
);
302 Debug
.Assert(addedEntry
.EntityKey
.IsTemporary
);
304 // map temp key to 'value' key (if all values of the key are non null)
305 EntityKey tempKey
= addedEntry
.EntityKey
;
307 var keyMembers
= addedEntry
.EntitySet
.ElementType
.KeyMembers
;
308 var currentValues
= addedEntry
.CurrentValues
;
310 object[] keyValues
= new object[keyMembers
.Count
];
311 bool hasNullValue
= false;
313 for (int i
= 0, n
= keyMembers
.Count
; i
< n
; i
++)
315 int ordinal
= currentValues
.GetOrdinal(keyMembers
[i
].Name
);
316 if (currentValues
.IsDBNull(ordinal
))
323 keyValues
[i
] = currentValues
.GetValue(ordinal
);
333 valueKey
= keyValues
.Length
== 1
334 ? new EntityKey(addedEntry
.EntitySet
, keyValues
[0])
335 : new EntityKey(addedEntry
.EntitySet
, keyValues
);
338 if (_valueKeyToTempKey
.ContainsKey(valueKey
))
340 // null indicates that there are collisions on key values
341 _valueKeyToTempKey
[valueKey
] = null;
345 _valueKeyToTempKey
.Add(valueKey
, tempKey
);
350 /// There are three states:
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)
356 internal bool TryGetTempKey(EntityKey valueKey
, out EntityKey tempKey
)
358 return _valueKeyToTempKey
.TryGetValue(valueKey
, out tempKey
);
361 private void ValidateReferentialIntegrityGraphAcyclic(int node
, NodeColor
[] color
, LinkedList
<int> parent
)
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
))
367 switch (color
[successor
])
370 // haven't seen this node yet; visit it
371 ValidateReferentialIntegrityGraphAcyclic(successor
, color
, parent
);
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
))
380 PropagatorResult owner
= _identifiers
[identifierInCycle
].Owner
;
383 stateEntriesInCycle
.Add(owner
.StateEntry
);
386 if (identifierInCycle
== successor
)
393 throw EntityUtil
.Update(Strings
.Update_CircularRelationships
, null, stateEntriesInCycle
);
400 color
[node
] = Black
; // color the node to indicate we're done visiting it
405 /// Ensures firstId and secondId belong to the same partition
407 internal void AssociateNodes(int firstId
, int secondId
)
409 if (firstId
== secondId
)
411 // A node is (trivially) associated with itself
414 Partition firstPartition
= _identifiers
[firstId
].Partition
;
415 if (null != firstPartition
)
417 Partition secondPartition
= _identifiers
[secondId
].Partition
;
418 if (null != secondPartition
)
421 firstPartition
.Merge(this, secondPartition
);
425 // add y to existing x partition
426 firstPartition
.AddNode(this, secondId
);
431 Partition secondPartition
= _identifiers
[secondId
].Partition
;
432 if (null != secondPartition
)
434 // add x to existing y partition
435 secondPartition
.AddNode(this, firstId
);
439 // Neither node is known
440 Partition
.CreatePartition(this, firstId
, secondId
);
445 private sealed class Partition
447 internal readonly int PartitionId
;
448 private readonly List
<int> _nodeIds
;
450 private Partition(int partitionId
)
452 _nodeIds
= new List
<int>(2);
453 PartitionId
= partitionId
;
456 internal static void CreatePartition(KeyManager manager
, int firstId
, int secondId
)
458 Partition partition
= new Partition(firstId
);
459 partition
.AddNode(manager
, firstId
);
460 partition
.AddNode(manager
, secondId
);
463 internal void AddNode(KeyManager manager
, int nodeId
)
465 Debug
.Assert(!_nodeIds
.Contains(nodeId
), "don't add existing node to partition");
466 _nodeIds
.Add(nodeId
);
467 manager
._identifiers
[nodeId
].Partition
= this;
470 internal void Merge(KeyManager manager
, Partition other
)
472 if (other
.PartitionId
== this.PartitionId
)
476 foreach (int element
in other
._nodeIds
)
479 AddNode(manager
, element
);
485 /// Simple linked list class.
487 private sealed class LinkedList
<T
>
489 private readonly T _value
;
490 private readonly LinkedList
<T
> _previous
;
492 private LinkedList(T
value, LinkedList
<T
> previous
)
495 _previous
= previous
;
498 internal static IEnumerable
<T
> Enumerate(LinkedList
<T
> current
)
500 while (null != current
)
502 yield return current
._value
;
503 current
= current
._previous
;
507 internal static void Add(ref LinkedList
<T
> list
, T
value)
509 list
= new LinkedList
<T
>(value, list
);
514 /// Collects information relevant to a particular identifier.
516 private sealed class IdentifierInfo
518 internal Partition Partition
;
519 internal PropagatorResult Owner
;
520 internal LinkedList
<IEntityStateEntry
> DependentStateEntries
;
521 internal LinkedList
<int> References
;
522 internal LinkedList
<int> ReferencedBy
;