mcs/class/referencesource/System.Data.Linq/ChangeProcessor.cs

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Linq;
   4 using System.Reflection;
   5 using System.Text;
   6 using System.Diagnostics;
   7
   8 namespace System.Data.Linq {
   9     using System.Data.Linq.Mapping;
  10     using System.Data.Linq.Provider;
  11
  12     /// <summary>
  13     /// Describes the type of change the entity will undergo when submitted to the database.
  14     /// </summary>
  15     public enum ChangeAction {
  16         /// <summary>
  17         /// The entity will not be submitted.
  18         /// </summary>
  19         None = 0,
  20         /// <summary>
  21         /// The entity will be deleted.
  22         /// </summary>
  23         Delete,
  24         /// <summary>
  25         /// The entity will be inserted.
  26         /// </summary>
  27         Insert,
  28         /// <summary>
  29         /// The entity will be updated.
  30         /// </summary>
  31         Update
  32     }
  33
  34     internal class ChangeProcessor {
  35         CommonDataServices services;
  36         DataContext context;
  37         ChangeTracker tracker;
  38         ChangeDirector changeDirector;
  39         EdgeMap currentParentEdges;
  40         EdgeMap originalChildEdges;
  41         ReferenceMap originalChildReferences;
  42
  43         internal ChangeProcessor(CommonDataServices services, DataContext context) {
  44             this.services = services;
  45             this.context = context;
  46             this.tracker = services.ChangeTracker;
  47             this.changeDirector = services.ChangeDirector;
  48             this.currentParentEdges = new EdgeMap();
  49             this.originalChildEdges = new EdgeMap();
  50             this.originalChildReferences = new ReferenceMap();
  51         }
  52
  53         internal void SubmitChanges(ConflictMode failureMode) {
  54             this.TrackUntrackedObjects();
  55             // Must apply inferred deletions only after any untracked objects
  56             // are tracked
  57             this.ApplyInferredDeletions();
  58             this.BuildEdgeMaps();
  59
  60             var list = this.GetOrderedList();
  61
  62             ValidateAll(list);
  63
  64             int numUpdatesAttempted = 0;
  65             ChangeConflictSession conflictSession = new ChangeConflictSession(this.context);
  66             List<ObjectChangeConflict> conflicts = new List<ObjectChangeConflict>();
  67             List<TrackedObject> deletedItems = new List<TrackedObject>();
  68             List<TrackedObject> insertedItems = new List<TrackedObject>();
  69             List<TrackedObject> syncDependentItems = new List<TrackedObject>();
  70
  71             foreach (TrackedObject item in list) {
  72                 try {
  73                     if (item.IsNew) {
  74                         if (item.SynchDependentData()) {
  75                             syncDependentItems.Add(item);
  76                         }
  77                         changeDirector.Insert(item);
  78                         // store all inserted items for post processing
  79                         insertedItems.Add(item);
  80                     }
  81                     else if (item.IsDeleted) {
  82                         // Delete returns 1 if the delete was successfull, 0 if the row exists
  83                         // but wasn't deleted due to an OC conflict, or -1 if the row was
  84                         // deleted by another context (no OC conflict in this case)
  85                         numUpdatesAttempted++;
  86                         int ret = changeDirector.Delete(item);
  87                         if (ret == 0) {
  88                             conflicts.Add(new ObjectChangeConflict(conflictSession, item, false));
  89                         }
  90                         else {
  91                             // store all deleted items for post processing
  92                             deletedItems.Add(item);
  93                         }
  94                     }
  95                     else if (item.IsPossiblyModified) {
  96                         if (item.SynchDependentData()) {
  97                             syncDependentItems.Add(item);
  98                         }
  99                         if (item.IsModified) {
 100                             CheckForInvalidChanges(item);
 101                             numUpdatesAttempted++;
 102                             if (changeDirector.Update(item) <= 0) {
 103                                 conflicts.Add(new ObjectChangeConflict(conflictSession, item));
 104                             }
 105                         }
 106                     }
 107                 }
 108                 catch (ChangeConflictException) {
 109                     conflicts.Add(new ObjectChangeConflict(conflictSession, item));
 110                 }
 111                 if (conflicts.Count > 0 && failureMode == ConflictMode.FailOnFirstConflict) {
 112                     break;
 113                 }
 114             }
 115
 116             // if we have accumulated any failed updates, throw the exception now
 117             if (conflicts.Count > 0) {
 118                 // First we need to rollback any value that have already been auto-sync'd, since the values are no longer valid on the server
 119                 changeDirector.RollbackAutoSync();
 120                 // Also rollback any dependent items that were sync'd, since their parent values may have been rolled back
 121                 foreach (TrackedObject syncDependentItem in syncDependentItems) {
 122                     Debug.Assert(syncDependentItem.IsNew || syncDependentItem.IsPossiblyModified, "SynchDependent data should only be rolled back for new and modified objects.");
 123                     syncDependentItem.SynchDependentData();
 124                 }
 125                 this.context.ChangeConflicts.Fill(conflicts);
 126                 throw CreateChangeConflictException(numUpdatesAttempted, conflicts.Count);
 127             }
 128             else {
 129                 // No conflicts occurred, so we don't need to save the rollback values anymore
 130                 changeDirector.ClearAutoSyncRollback();
 131             }
 132
 133             // Only after all updates have been sucessfully processed do we want to make
 134             // post processing modifications to the objects and/or cache state.
 135             PostProcessUpdates(insertedItems, deletedItems);
 136         }
 137
 138         private void PostProcessUpdates(List<TrackedObject> insertedItems, List<TrackedObject> deletedItems) {
 139             // perform post delete processing
 140             foreach (TrackedObject deletedItem in deletedItems) {
 141                 // remove deleted item from identity cache
 142                 this.services.RemoveCachedObjectLike(deletedItem.Type, deletedItem.Original);
 143                 ClearForeignKeyReferences(deletedItem);
 144             }
 145
 146             // perform post insert processing
 147             foreach (TrackedObject insertedItem in insertedItems) {
 148                 object lookup = this.services.InsertLookupCachedObject(insertedItem.Type, insertedItem.Current);
 149                 if (lookup != insertedItem.Current) {
 150                     throw new DuplicateKeyException(insertedItem.Current, Strings.DatabaseGeneratedAlreadyExistingKey);
 151                 }
 152                 insertedItem.InitializeDeferredLoaders();
 153             }
 154         }
 155
 156         /// <summary>
 157         /// Clears out the foreign key values and parent object references for deleted objects on the child side of a relationship.
 158         /// For bi-directional relationships, also performs the following fixup:
 159         ///   - for 1:N we remove the deleted entity from the opposite EntitySet or collection
 160         ///   - for 1:1 we null out the back reference
 161         /// </summary>
 162         private void ClearForeignKeyReferences(TrackedObject to) {
 163             Debug.Assert(to.IsDeleted, "Foreign key reference cleanup should only happen on Deleted objects.");
 164             foreach (MetaAssociation assoc in to.Type.Associations) {
 165                 if (assoc.IsForeignKey) {
 166                     // If there is a member on the other side referring back to us (i.e. this is a bi-directional relationship),
 167                     // we want to do a cache lookup to find the other side, then will remove ourselves from that collection.
 168                     // This cache lookup is only possible if the other key is the primary key, since that is the only way items can be found in the cache.
 169                     if (assoc.OtherMember != null && assoc.OtherKeyIsPrimaryKey) {
 170                         Debug.Assert(assoc.OtherMember.IsAssociation, "OtherMember of the association is expected to also be an association.");
 171                         // Search the cache for the target of the association, since
 172                         // it might not be loaded on the object being deleted, and we
 173                         // don't want to force a load.
 174                         object[] keyValues = CommonDataServices.GetForeignKeyValues(assoc, to.Current);
 175                         object cached = this.services.IdentityManager.Find(assoc.OtherType, keyValues);
 176
 177                         if (cached != null) {
 178                             if (assoc.OtherMember.Association.IsMany) {
 179                                 // Note that going through the IList interface handles
 180                                 // EntitySet as well as POCO collections that implement IList
 181                                 // and are not FixedSize.
 182                                 System.Collections.IList collection = assoc.OtherMember.MemberAccessor.GetBoxedValue(cached) as System.Collections.IList;
 183                                 if (collection != null && !collection.IsFixedSize) {
 184                                     collection.Remove(to.Current);
 185                                     // Explicitly clear the foreign key values and parent object reference
 186                                     ClearForeignKeysHelper(assoc, to.Current);
 187                                 }
 188                             }
 189                             else {
 190                                 // Null out the other association.  Since this is a 1:1 association,
 191                                 // we're not concerned here with causing a deferred load, since the
 192                                 // target is already cached (since we're deleting it).
 193                                 assoc.OtherMember.MemberAccessor.SetBoxedValue(ref cached, null);
 194                                 // Explicitly clear the foreign key values and parent object reference
 195                                 ClearForeignKeysHelper(assoc, to.Current);
 196                             }
 197                         }
 198                         // else the item was not found in the cache, so there is no fixup that has to be done
 199                         // We are explicitly not calling ClearForeignKeysHelper because it breaks existing shipped behavior and we want to maintain backward compatibility
 200                     }
 201                     else {
 202                         // This is a unidirectional relationship or we have no way to look up the other side in the cache, so just clear our own side
 203                         ClearForeignKeysHelper(assoc, to.Current);
 204                     }
 205                 }
 206                 // else this is not the 1-side (foreign key) of the relationship, so there is nothing for us to do
 207             }
 208         }
 209
 210         // Ensure the the member and foreign keys are nulled so that after trackedInstance is deleted,
 211         // the object does not appear to be associated with the other side anymore. This prevents the deleted object
 212         // from referencing objects still in the cache, but also will prevent the related object from being implicitly loaded
 213         private static void ClearForeignKeysHelper(MetaAssociation assoc, object trackedInstance) {
 214             Debug.Assert(assoc.IsForeignKey, "Foreign key clearing should only happen on foreign key side of the association.");
 215             Debug.Assert(assoc.ThisMember.IsAssociation, "Expected ThisMember of an association to always be an association.");
 216
 217             // If this member is one of our deferred loaders, and it does not already have a value, explicitly set the deferred source to
 218             // null so that when we set the association member itself to null later, it doesn't trigger an implicit load.
 219             // This is only necessary if the value has not already been assigned or set, because otherwise we won't implicitly load anyway when the member is accessed.
 220             MetaDataMember thisMember = assoc.ThisMember;
 221
 222             if (thisMember.IsDeferred &&
 223                 !(thisMember.StorageAccessor.HasAssignedValue(trackedInstance) || thisMember.StorageAccessor.HasLoadedValue(trackedInstance)))
 224             {
 225                 // If this is a deferred member, set the value directly in the deferred accessor instead of going
 226                 // through the normal member accessor, so that we don't trigger an implicit load.
 227                 thisMember.DeferredSourceAccessor.SetBoxedValue(ref trackedInstance, null);
 228             }
 229
 230             // Notify the object that the relationship should be considered deleted.
 231             // This allows the object to do its own fixup even when we can't do it automatically.
 232             thisMember.MemberAccessor.SetBoxedValue(ref trackedInstance, null);
 233
 234             // Also set the foreign key values to null if possible
 235             for (int i = 0, n = assoc.ThisKey.Count; i < n; i++) {
 236                 MetaDataMember thisKey = assoc.ThisKey[i];
 237                 if (thisKey.CanBeNull) {
 238                     thisKey.StorageAccessor.SetBoxedValue(ref trackedInstance, null);
 239                 }
 240             }
 241         }
 242
 243         private static void ValidateAll(IEnumerable<TrackedObject> list) {
 244             foreach (var item in list) {
 245                 if (item.IsNew) {
 246                     item.SynchDependentData();
 247                     if (item.Type.HasAnyValidateMethod) {
 248                         SendOnValidate(item.Type, item, ChangeAction.Insert);
 249                     }
 250                 } else if (item.IsDeleted) {
 251                     if (item.Type.HasAnyValidateMethod) {
 252                         SendOnValidate(item.Type, item, ChangeAction.Delete);
 253                     }
 254                 } else if (item.IsPossiblyModified) {
 255                     item.SynchDependentData();
 256                     if (item.IsModified && item.Type.HasAnyValidateMethod) {
 257                         SendOnValidate(item.Type, item, ChangeAction.Update);
 258                     }
 259                 }
 260             }
 261         }
 262
 263         private static void SendOnValidate(MetaType type, TrackedObject item, ChangeAction changeAction) {
 264             if (type != null) {
 265                 SendOnValidate(type.InheritanceBase, item, changeAction);
 266
 267                 if (type.OnValidateMethod != null) {
 268                     try {
 269                         type.OnValidateMethod.Invoke(item.Current, new object[] { changeAction });
 270                     } catch (TargetInvocationException tie) {
 271                         if (tie.InnerException != null) {
 272                             throw tie.InnerException;
 273                         }
 274
 275                         throw;
 276                     }
 277                 }
 278             }
 279         }
 280
 281         internal string GetChangeText() {
 282             this.ObserveUntrackedObjects();
 283             // Must apply inferred deletions only after any untracked objects
 284             // are tracked
 285             this.ApplyInferredDeletions();
 286             this.BuildEdgeMaps();
 287
 288             // append change text only
 289             StringBuilder changeText = new StringBuilder();
 290             foreach (TrackedObject item in this.GetOrderedList()) {
 291                 if (item.IsNew) {
 292                     item.SynchDependentData();
 293                     changeDirector.AppendInsertText(item, changeText);
 294                 }
 295                 else if (item.IsDeleted) {
 296                     changeDirector.AppendDeleteText(item, changeText);
 297                 }
 298                 else if (item.IsPossiblyModified) {
 299                     item.SynchDependentData();
 300                     if (item.IsModified) {
 301                         changeDirector.AppendUpdateText(item, changeText);
 302                     }
 303                 }
 304             }
 305             return changeText.ToString();
 306         }
 307
 308         internal ChangeSet GetChangeSet() {
 309             List<object> newEntities = new List<object>();
 310             List<object> deletedEntities = new List<object>();
 311             List<object> changedEntities = new List<object>();
 312
 313             this.ObserveUntrackedObjects();
 314             // Must apply inferred deletions only after any untracked objects
 315             // are tracked
 316             this.ApplyInferredDeletions();
 317
 318             foreach (TrackedObject item in this.tracker.GetInterestingObjects()) {
 319                 if (item.IsNew) {
 320                     item.SynchDependentData();
 321                     newEntities.Add(item.Current);
 322                 }
 323                 else if (item.IsDeleted) {
 324                     deletedEntities.Add(item.Current);
 325                 }
 326                 else if (item.IsPossiblyModified) {
 327                     item.SynchDependentData();
 328                     if (item.IsModified) {
 329                         changedEntities.Add(item.Current);
 330                     }
 331                 }
 332             }
 333
 334             return new ChangeSet(newEntities.AsReadOnly(), deletedEntities.AsReadOnly(), changedEntities.AsReadOnly());
 335         }
 336
 337         // verify that primary key and db-generated values have not changed
 338         private static void CheckForInvalidChanges(TrackedObject tracked) {
 339             foreach (MetaDataMember mem in tracked.Type.PersistentDataMembers) {
 340                 if (mem.IsPrimaryKey || mem.IsDbGenerated || mem.IsVersion) {
 341                     if (tracked.HasChangedValue(mem)) {
 342                         if (mem.IsPrimaryKey) {
 343                             throw Error.IdentityChangeNotAllowed(mem.Name, tracked.Type.Name);
 344                         }
 345                         else {
 346                             throw Error.DbGeneratedChangeNotAllowed(mem.Name, tracked.Type.Name);
 347                         }
 348                     }
 349                 }
 350             }
 351         }
 352
 353         /// <summary>
 354         /// Create an ChangeConflictException with the best message
 355         /// </summary>
 356         static private ChangeConflictException CreateChangeConflictException(int totalUpdatesAttempted, int failedUpdates) {
 357             string msg = Strings.RowNotFoundOrChanged;
 358             if (totalUpdatesAttempted > 1) {
 359                 msg = Strings.UpdatesFailedMessage(failedUpdates, totalUpdatesAttempted);
 360             }
 361             return new ChangeConflictException(msg);
 362         }
 363
 364         internal void TrackUntrackedObjects() {
 365             Dictionary<object, object> visited = new Dictionary<object, object>();
 366
 367             // search for untracked new objects
 368             List<TrackedObject> items = new List<TrackedObject>(this.tracker.GetInterestingObjects());
 369             foreach (TrackedObject item in items) {
 370                 this.TrackUntrackedObjects(item.Type, item.Current, visited);
 371             }
 372         }
 373
 374         internal void ApplyInferredDeletions() {
 375             foreach (TrackedObject item in this.tracker.GetInterestingObjects()) {
 376                 if (item.CanInferDelete()) {
 377                     // based on DeleteOnNull specifications on the item's associations,
 378                     // a deletion can be inferred for this item.  The actual state transition
 379                     // is dependent on the current item state.
 380                     if (item.IsNew) {
 381                         item.ConvertToRemoved();
 382                     }
 383                     else if (item.IsPossiblyModified || item.IsModified) {
 384                         item.ConvertToDeleted();
 385                     }
 386                 }
 387             }
 388         }
 389
 390         private void TrackUntrackedObjects(MetaType type, object item, Dictionary<object, object> visited) {
 391             if (!visited.ContainsKey(item)) {
 392                 visited.Add(item, item);
 393                 TrackedObject tracked = this.tracker.GetTrackedObject(item);
 394                 if (tracked == null) {
 395                     tracked = this.tracker.Track(item);
 396                     tracked.ConvertToNew();
 397                 }
 398                 else if (tracked.IsDead || tracked.IsRemoved) {
 399                     // ignore
 400                     return;
 401                 }
 402
 403                 // search parents (objects we are dependent on)
 404                 foreach (RelatedItem parent in this.services.GetParents(type, item)) {
 405                     this.TrackUntrackedObjects(parent.Type, parent.Item, visited);
 406                 }
 407
 408                 // synch up primary key
 409                 if (tracked.IsNew) {
 410                     tracked.InitializeDeferredLoaders();
 411
 412                     if (!tracked.IsPendingGeneration(tracked.Type.IdentityMembers)) {
 413                         tracked.SynchDependentData();
 414                         object cached = this.services.InsertLookupCachedObject(tracked.Type, item);
 415                         if (cached != item) {
 416                             TrackedObject cachedTracked = this.tracker.GetTrackedObject(cached);
 417                             Debug.Assert(cachedTracked != null);
 418                             if (cachedTracked.IsDeleted || cachedTracked.CanInferDelete()) {
 419                                 // adding new object with same ID as object being deleted.. turn into modified
 420                                 tracked.ConvertToPossiblyModified(cachedTracked.Original);
 421                                 // turn deleted to dead...
 422                                 cachedTracked.ConvertToDead();
 423
 424                                 this.services.RemoveCachedObjectLike(tracked.Type, item);
 425                                 this.services.InsertLookupCachedObject(tracked.Type, item);
 426                             }
 427                             else if (!cachedTracked.IsDead) {
 428                                 throw new DuplicateKeyException(item, Strings.CantAddAlreadyExistingKey);
 429                             }
 430                         }
 431                     }
 432                     else {
 433                         // we may have a generated PK, however we set the PK on this new item to
 434                         // match a deleted item
 435                         object cached = this.services.GetCachedObjectLike(tracked.Type, item);
 436                         if (cached != null) {
 437                             TrackedObject cachedTracked = this.tracker.GetTrackedObject(cached);
 438                             Debug.Assert(cachedTracked != null);
 439                             if (cachedTracked.IsDeleted || cachedTracked.CanInferDelete()) {
 440                                 // adding new object with same ID as object being deleted.. turn into modified
 441                                 tracked.ConvertToPossiblyModified(cachedTracked.Original);
 442                                 // turn deleted to dead...
 443                                 cachedTracked.ConvertToDead();
 444
 445                                 this.services.RemoveCachedObjectLike(tracked.Type, item);
 446                                 this.services.InsertLookupCachedObject(tracked.Type, item);
 447                             }
 448                         }
 449                     }
 450                 }
 451
 452                 // search children (objects that are dependent on us)
 453                 foreach (RelatedItem child in this.services.GetChildren(type, item)) {
 454                     this.TrackUntrackedObjects(child.Type, child.Item, visited);
 455                 }
 456             }
 457         }
 458
 459         internal void ObserveUntrackedObjects() {
 460             Dictionary<object, object> visited = new Dictionary<object, object>();
 461
 462             List<TrackedObject> items = new List<TrackedObject>(this.tracker.GetInterestingObjects());
 463             foreach (TrackedObject item in items) {
 464                 this.ObserveUntrackedObjects(item.Type, item.Current, visited);
 465             }
 466         }
 467
 468         private void ObserveUntrackedObjects(MetaType type, object item, Dictionary<object, object> visited) {
 469             if (!visited.ContainsKey(item)) {
 470                 visited.Add(item, item);
 471                 TrackedObject tracked = this.tracker.GetTrackedObject(item);
 472                 if (tracked == null) {
 473                     tracked = this.tracker.Track(item);
 474                     tracked.ConvertToNew();
 475                 } else if (tracked.IsDead || tracked.IsRemoved) {
 476                     // ignore
 477                     return;
 478                 }
 479
 480                 // search parents (objects we are dependent on)
 481                 foreach (RelatedItem parent in this.services.GetParents(type, item)) {
 482                     this.ObserveUntrackedObjects(parent.Type, parent.Item, visited);
 483                 }
 484
 485                 // synch up primary key unless its generated.
 486                 if (tracked.IsNew) {
 487                      if (!tracked.IsPendingGeneration(tracked.Type.IdentityMembers)) {
 488                         tracked.SynchDependentData();
 489                      }
 490                 }
 491
 492                 // search children (objects that are dependent on us)
 493                 foreach (RelatedItem child in this.services.GetChildren(type, item)) {
 494                     this.ObserveUntrackedObjects(child.Type, child.Item, visited);
 495                 }
 496             }
 497         }
 498
 499         private TrackedObject GetOtherItem(MetaAssociation assoc, object instance) {
 500             if (instance == null)
 501                 return null;
 502             object other = null;
 503             // Don't load unloaded references
 504             if (assoc.ThisMember.StorageAccessor.HasAssignedValue(instance) ||
 505                 assoc.ThisMember.StorageAccessor.HasLoadedValue(instance)
 506                 ) {
 507                 other = assoc.ThisMember.MemberAccessor.GetBoxedValue(instance);
 508             }
 509             else if (assoc.OtherKeyIsPrimaryKey) {
 510                 // Maybe it's in the cache, but not yet attached through reference.
 511                 object[] foreignKeys = CommonDataServices.GetForeignKeyValues(assoc, instance);
 512                 other = this.services.GetCachedObject(assoc.OtherType, foreignKeys);
 513             }
 514             // else the other key is not the primary key so there is no way to try to look it up
 515             return (other != null) ? this.tracker.GetTrackedObject(other) : null;
 516         }
 517
 518         private bool HasAssociationChanged(MetaAssociation assoc, TrackedObject item) {
 519             if (item.Original != null && item.Current != null) {
 520                 if (assoc.ThisMember.StorageAccessor.HasAssignedValue(item.Current) ||
 521                     assoc.ThisMember.StorageAccessor.HasLoadedValue(item.Current)
 522                     ) {
 523                     return this.GetOtherItem(assoc, item.Current) != this.GetOtherItem(assoc, item.Original);
 524                 }
 525                 else {
 526                     object[] currentFKs = CommonDataServices.GetForeignKeyValues(assoc, item.Current);
 527                     object[] originaFKs = CommonDataServices.GetForeignKeyValues(assoc, item.Original);
 528                     for (int i = 0, n = currentFKs.Length; i < n; i++) {
 529                         if (!object.Equals(currentFKs[i], originaFKs[i]))
 530                             return true;
 531                     }
 532                 }
 533             }
 534             return false;
 535         }
 536
 537         private void BuildEdgeMaps() {
 538             this.currentParentEdges.Clear();
 539             this.originalChildEdges.Clear();
 540             this.originalChildReferences.Clear();
 541
 542             List<TrackedObject> list = new List<TrackedObject>(this.tracker.GetInterestingObjects());
 543             foreach (TrackedObject item in list) {
 544                 bool isNew = item.IsNew;
 545                 MetaType mt = item.Type;
 546                 foreach (MetaAssociation assoc in mt.Associations) {
 547                     if (assoc.IsForeignKey) {
 548                         TrackedObject otherItem = this.GetOtherItem(assoc, item.Current);
 549                         TrackedObject dbOtherItem = this.GetOtherItem(assoc, item.Original);
 550                         bool pointsToDeleted = (otherItem != null && otherItem.IsDeleted) || (dbOtherItem != null && dbOtherItem.IsDeleted);
 551                         bool pointsToNew = (otherItem != null && otherItem.IsNew);
 552
 553                         if (isNew || pointsToDeleted || pointsToNew || this.HasAssociationChanged(assoc, item)) {
 554                             if (otherItem != null) {
 555                                 this.currentParentEdges.Add(assoc, item, otherItem);
 556                             }
 557                             if (dbOtherItem != null) {
 558                                 if (assoc.IsUnique) {
 559                                     this.originalChildEdges.Add(assoc, dbOtherItem, item);
 560                                 }
 561                                 this.originalChildReferences.Add(dbOtherItem, item);
 562                             }
 563                         }
 564                     }
 565                 }
 566             }
 567         }
 568
 569         enum VisitState {
 570             Before,
 571             After
 572         }
 573
 574         private List<TrackedObject> GetOrderedList() {
 575             var objects = this.tracker.GetInterestingObjects().ToList();
 576
 577             // give list an initial order (most likely correct order) to avoid deadlocks in server
 578             var range = Enumerable.Range(0, objects.Count).ToList();
 579             range.Sort((int x, int y) => Compare(objects[x], x, objects[y], y));
 580             var ordered = range.Select(i => objects[i]).ToList();
 581
 582             // permute order if constraint dependencies requires some changes to come before others
 583             var visited = new Dictionary<TrackedObject, VisitState>();
 584             var list = new List<TrackedObject>();
 585             foreach (TrackedObject item in ordered) {
 586                 this.BuildDependencyOrderedList(item, list, visited);
 587             }
 588             return list;
 589         }
 590
 591         private static int Compare(TrackedObject x, int xOrdinal, TrackedObject y, int yOrdinal) {
 592             // deal with possible nulls
 593             if (x == y) {
 594                 return 0;
 595             }
 596             if (x == null) {
 597                 return -1;
 598             }
 599             else if (y == null) {
 600                 return 1;
 601             }
 602             // first order by action: Inserts first, Updates, Deletes last
 603             int xAction = x.IsNew ? 0 : x.IsDeleted ? 2 : 1;
 604             int yAction = y.IsNew ? 0 : y.IsDeleted ? 2 : 1;
 605             if (xAction < yAction) {
 606                 return -1;
 607             }
 608             else if (xAction > yAction) {
 609                 return 1;
 610             }
 611             // no need to order inserts (PK's may not even exist)
 612             if (x.IsNew) {
 613                 // keep original order
 614                 return xOrdinal.CompareTo(yOrdinal);
 615             }
 616             // second order by type
 617             if (x.Type != y.Type) {
 618                 return string.CompareOrdinal(x.Type.Type.FullName, y.Type.Type.FullName);
 619             }
 620             // lastly, order by PK values
 621             int result = 0;
 622             foreach (MetaDataMember mm in x.Type.IdentityMembers) {
 623                 object xValue = mm.StorageAccessor.GetBoxedValue(x.Current);
 624                 object yValue = mm.StorageAccessor.GetBoxedValue(y.Current);
 625                 if (xValue == null) {
 626                     if (yValue != null) {
 627                         return -1;
 628                     }
 629                 }
 630                 else {
 631                     IComparable xc = xValue as IComparable;
 632                     if (xc != null) {
 633                         result = xc.CompareTo(yValue);
 634                         if (result != 0) {
 635                             return result;
 636                         }
 637                     }
 638                 }
 639             }
 640             // they are the same? leave in original order
 641             return xOrdinal.CompareTo(yOrdinal);
 642         }
 643
 644         private void BuildDependencyOrderedList(TrackedObject item, List<TrackedObject> list, Dictionary<TrackedObject, VisitState> visited) {
 645             VisitState state;
 646             if (visited.TryGetValue(item, out state)) {
 647                 if (state == VisitState.Before) {
 648                     throw Error.CycleDetected();
 649                 }
 650                 return;
 651             }
 652
 653             visited[item] = VisitState.Before;
 654
 655             if (item.IsInteresting) {
 656                 if (item.IsDeleted) {
 657                     // if 'item' is deleted
 658                     //    all objects that used to refer to 'item' must be ordered before item
 659                     foreach (TrackedObject other in this.originalChildReferences[item]) {
 660                         if (other != item) {
 661                             this.BuildDependencyOrderedList(other, list, visited);
 662                         }
 663                     }
 664                 }
 665                 else {
 666                     // if 'item' is new or changed
 667                     //   for all objects 'other' that 'item' refers to along association 'assoc'
 668                     //      if 'other' is new then 'other' must be ordered before 'item'
 669                     //      if 'assoc' is pure one-to-one and some other item 'prevItem' used to refer to 'other'
 670                     //         then 'prevItem' must be ordered before 'item'
 671                     foreach (MetaAssociation assoc in item.Type.Associations) {
 672                         if (assoc.IsForeignKey) {
 673                             TrackedObject other = this.currentParentEdges[assoc, item];
 674                             if (other != null) {
 675                                 if (other.IsNew) {
 676                                     // if other is new, visit other first (since item's FK depends on it)
 677                                     if (other != item || item.Type.DBGeneratedIdentityMember != null) {
 678                                         this.BuildDependencyOrderedList(other, list, visited);
 679                                     }
 680                                 }
 681                                 else if ((assoc.IsUnique || assoc.ThisKeyIsPrimaryKey)) {
 682                                     TrackedObject prevItem = this.originalChildEdges[assoc, other];
 683                                     if (prevItem != null && other != item) {
 684                                         this.BuildDependencyOrderedList(prevItem, list, visited);
 685                                     }
 686                                 }
 687                             }
 688                         }
 689                     }
 690                 }
 691
 692                 list.Add(item);
 693             }
 694
 695             visited[item] = VisitState.After;
 696         }
 697
 698         class EdgeMap {
 699             Dictionary<MetaAssociation, Dictionary<TrackedObject, TrackedObject>> associations;
 700
 701             internal EdgeMap() {
 702                 this.associations = new Dictionary<MetaAssociation, Dictionary<TrackedObject, TrackedObject>>();
 703             }
 704
 705             internal void Add(MetaAssociation assoc, TrackedObject from, TrackedObject to) {
 706                 Dictionary<TrackedObject, TrackedObject> pairs;
 707                 if (!associations.TryGetValue(assoc, out pairs)) {
 708                     pairs = new Dictionary<TrackedObject, TrackedObject>();
 709                     associations.Add(assoc, pairs);
 710                 }
 711                 pairs.Add(from, to);
 712             }
 713
 714             internal TrackedObject this[MetaAssociation assoc, TrackedObject from] {
 715                 get {
 716                     Dictionary<TrackedObject, TrackedObject> pairs;
 717                     if (associations.TryGetValue(assoc, out pairs)) {
 718                         TrackedObject to;
 719                         if (pairs.TryGetValue(from, out to)) {
 720                             return to;
 721                         }
 722                     }
 723                     return null;
 724                 }
 725             }
 726             internal void Clear() {
 727                 this.associations.Clear();
 728             }
 729         }
 730
 731         class ReferenceMap {
 732             Dictionary<TrackedObject, List<TrackedObject>> references;
 733
 734             internal ReferenceMap() {
 735                 this.references = new Dictionary<TrackedObject, List<TrackedObject>>();
 736             }
 737
 738             internal void Add(TrackedObject from, TrackedObject to) {
 739                 List<TrackedObject> refs;
 740                 if (!references.TryGetValue(from, out refs)) {
 741                     refs = new List<TrackedObject>();
 742                     references.Add(from, refs);
 743                 }
 744                 if (!refs.Contains(to))
 745                     refs.Add(to);
 746             }
 747
 748             internal IEnumerable<TrackedObject> this[TrackedObject from] {
 749                 get {
 750                     List<TrackedObject> refs;
 751                     if (references.TryGetValue(from, out refs)) {
 752                         return refs;
 753                     }
 754                     return Empty;
 755                 }
 756             }
 757
 758             internal void Clear() {
 759                 this.references.Clear();
 760             }
 761
 762             private static TrackedObject[] Empty = new TrackedObject[] { };
 763         }
 764     }
 765 }