Update/Internal/UpdateCommandOrderer.cs

//---------------------------------------------------------------------
// <copyright file="UpdateCommandOrderer.cs" company="Microsoft">
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------

namespace System.Data.Mapping.Update.Internal
{
    using System.Collections.Generic;
    using System.Data.Common.Utils;
    using System.Data.Metadata.Edm;
    using System.Diagnostics;
    using System.Linq;

    internal class UpdateCommandOrderer : Graph<UpdateCommand>
    {
        /// <summary>
        /// Gets comparer used to resolve identifiers to actual 'owning' key values (e.g. across referential constraints)
        /// </summary>
        private readonly ForeignKeyValueComparer _keyComparer;

        /// <summary>
        /// Maps from tables to all "source" referential constraints (where the table declares
        /// foreign keys)
        /// </summary>
        private readonly KeyToListMap<EntitySetBase, ReferentialConstraint> _sourceMap;

        /// <summary>
        /// Maps from tables to all "target" referential constraints (where the table is
        /// referenced by a foreign key)
        /// </summary>
        private readonly KeyToListMap<EntitySetBase, ReferentialConstraint> _targetMap;

        /// <summary>
        /// Tracks whether any function commands exist in the current payload.
        /// </summary>
        private readonly bool _hasFunctionCommands;

        /// <summary>
        /// Gets translator producing this graph.
        /// </summary>
        private readonly UpdateTranslator _translator;

        internal UpdateCommandOrderer(IEnumerable<UpdateCommand> commands, UpdateTranslator translator)
            : base(EqualityComparer<UpdateCommand>.Default)
        {
            _translator = translator;
            _keyComparer = new ForeignKeyValueComparer(_translator.KeyComparer);

            HashSet<EntitySet> tables = new HashSet<EntitySet>();
            HashSet<EntityContainer> containers = new HashSet<EntityContainer>();

            // add all vertices (one vertex for every command)
            foreach (UpdateCommand command in commands)
            {
                if (null != command.Table)
                {
                    tables.Add(command.Table);
                    containers.Add(command.Table.EntityContainer);
                }
                AddVertex(command);
                if (command.Kind == UpdateCommandKind.Function)
                {
                    _hasFunctionCommands = true;
                }
            }

            // figure out which foreign keys are interesting in this scope
            InitializeForeignKeyMaps(containers, tables, out _sourceMap, out _targetMap);

            // add edges for each ordering dependency amongst the commands
            AddServerGenDependencies();
            AddForeignKeyDependencies();
            if (_hasFunctionCommands)
            {
                AddModelDependencies();
            }
        }

        private static void InitializeForeignKeyMaps(HashSet<EntityContainer> containers, HashSet<EntitySet> tables, out KeyToListMap<EntitySetBase, ReferentialConstraint> sourceMap, out KeyToListMap<EntitySetBase, ReferentialConstraint> targetMap)
        {
            sourceMap = new KeyToListMap<EntitySetBase, ReferentialConstraint>(EqualityComparer<EntitySetBase>.Default);
            targetMap = new KeyToListMap<EntitySetBase, ReferentialConstraint>(EqualityComparer<EntitySetBase>.Default);

            // Retrieve relationship ends from each container to populate edges in dependency
            // graph
            foreach (EntityContainer container in containers)
            {
                foreach (EntitySetBase extent in container.BaseEntitySets)
                {
                    AssociationSet associationSet = extent as AssociationSet;

                    if (null != associationSet)
                    {
                        AssociationSetEnd source = null;
                        AssociationSetEnd target = null;

                        var ends = associationSet.AssociationSetEnds;

                        if (2 == ends.Count)
                        {
                            // source is equivalent to the "to" end of relationship, target is "from"
                            AssociationType associationType = associationSet.ElementType;
                            bool constraintFound = false;
                            ReferentialConstraint fkConstraint = null;
                            foreach (ReferentialConstraint constraint in associationType.ReferentialConstraints)
                            {
                                if (constraintFound) { Debug.Fail("relationship set should have at most one constraint"); }
                                else { constraintFound = true; }
                                source = associationSet.AssociationSetEnds[constraint.ToRole.Name];
                                target = associationSet.AssociationSetEnds[constraint.FromRole.Name];
                                fkConstraint = constraint;
                            }

                            Debug.Assert(constraintFound && null != target && null != source, "relationship set must have at least one constraint");
                            // only understand binary (foreign key) relationships between entity sets
                            if (null != target && null != source)
                            {
                                if (tables.Contains(target.EntitySet)&&
                                    tables.Contains(source.EntitySet))
                                {
                                    // Remember metadata
                                    sourceMap.Add(source.EntitySet, fkConstraint);
                                    targetMap.Add(target.EntitySet, fkConstraint);
                                }
                            }
                        }
                    }
                }
            }
        }

        // Adds edges to dependency graph for server-generated values.
        //
        // Determines which commands produce identifiers (key parts) and which commands
        // consume them. Producers are potentially edge predecessors and consumers are potentially
        // edge successors. The command objects report the identifiers they produce (OutputIdentifiers)
        // and the identifiers they consume (InputIdentifiers)
        private void AddServerGenDependencies()
        {
            // Identify all "shared" output parameters (e.g., SQL Server identifiers)
            Dictionary<int, UpdateCommand> predecessors = new Dictionary<int, UpdateCommand>();
            foreach (UpdateCommand command in this.Vertices)
            {
                foreach (int output in command.OutputIdentifiers)
                {
                    try
                    {
                        predecessors.Add(output, command);
                    }
                    catch (ArgumentException duplicateKey)
                    {
                        // throw an exception indicating that a key value is generated in two locations
                        // in the store
                        throw EntityUtil.Update(System.Data.Entity.Strings.Update_AmbiguousServerGenIdentifier, duplicateKey, command.GetStateEntries(_translator));
                    }
                }
            }

            // Identify all dependent input parameters
            foreach (UpdateCommand command in this.Vertices)
            {
                foreach (int input in command.InputIdentifiers)
                {
                    UpdateCommand from;
                    if (predecessors.TryGetValue(input, out from))
                    {
                        AddEdge(from, command);
                    }
                }
            }
        }

        // Adds edges to dependency graph based on foreign keys.
        private void AddForeignKeyDependencies()
        {
            KeyToListMap<ForeignKeyValue, UpdateCommand> predecessors = DetermineForeignKeyPredecessors();
            AddForeignKeyEdges(predecessors);
        }

        // Finds all successors to the given predecessors and registers the resulting dependency edges in this
        // graph.
        //
        // - Commands (updates or inserts) inserting FK "sources" (referencing foreign key)
        // - Commands (updates or deletes) deleting FK "targets" (referenced by the foreign key)
        //
        // To avoid violating constraints, FK references must be created before their referees, and
        // cannot be deleted before their references.
        private void AddForeignKeyEdges(KeyToListMap<ForeignKeyValue, UpdateCommand> predecessors)
        {
            foreach (DynamicUpdateCommand command in this.Vertices.OfType<DynamicUpdateCommand>())
            {
                // register all source successors
                if (ModificationOperator.Update == command.Operator ||
                    ModificationOperator.Insert == command.Operator)
                {
                    foreach (ReferentialConstraint fkConstraint in _sourceMap.EnumerateValues(command.Table))
                    {
                        ForeignKeyValue fk;
                        if (ForeignKeyValue.TryCreateSourceKey(fkConstraint, command.CurrentValues, true, out fk))
                        {
                            // if this is an update and the source key is unchanged, there is no
                            // need to add a dependency (from the perspective of the target, the update
                            // is a no-op)
                            ForeignKeyValue originalFK;
                            if (ModificationOperator.Update != command.Operator ||
                                !ForeignKeyValue.TryCreateSourceKey(fkConstraint, command.OriginalValues, true, out originalFK) ||
                                !_keyComparer.Equals(originalFK, fk))
                            {
                                foreach (UpdateCommand predecessor in predecessors.EnumerateValues(fk))
                                {
                                    // don't add self-edges for FK dependencies, since a single operation
                                    // in the store is atomic
                                    if (predecessor != command)
                                    {
                                        AddEdge(predecessor, command);
                                    }
                                }
                            }
                        }
                    }
                }

                // register all target successors
                if (ModificationOperator.Update == command.Operator ||
                    ModificationOperator.Delete == command.Operator)
                {
                    foreach (ReferentialConstraint fkConstraint in _targetMap.EnumerateValues(command.Table))
                    {
                        ForeignKeyValue fk;
                        if (ForeignKeyValue.TryCreateTargetKey(fkConstraint, command.OriginalValues, false, out fk))
                        {
                            // if this is an update and the target key is unchanged, there is no
                            // need to add a dependency (from the perspective of the source, the update
                            // is a no-op)
                            ForeignKeyValue currentFK;
                            if (ModificationOperator.Update != command.Operator ||
                                !ForeignKeyValue.TryCreateTargetKey(fkConstraint, command.CurrentValues, false, out currentFK) ||
                                !_keyComparer.Equals(currentFK, fk))
                            {

                                foreach (UpdateCommand predecessor in predecessors.EnumerateValues(fk))
                                {
                                    // don't add self-edges for FK dependencies, since a single operation
                                    // in the store is atomic
                                    if (predecessor != command)
                                    {
                                        AddEdge(predecessor, command);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        // Builds a map from foreign key instances to commands, with an entry for every command that may need to
        // precede some other operation.
        //
        // Predecessor commands must precede other commands using those values. There are two kinds of
        // predecessor:
        //
        // - Commands (updates or inserts) inserting FK "targets" (referenced by the foreign key)
        // - Commands (updates or deletes) deleting FK "sources" (referencing the foreign key)
        //
        // To avoid violating constraints, FK values must be created before they are referenced, and
        // cannot be deleted before their references
        private KeyToListMap<ForeignKeyValue, UpdateCommand> DetermineForeignKeyPredecessors()
        {
            KeyToListMap<ForeignKeyValue, UpdateCommand> predecessors = new KeyToListMap<ForeignKeyValue, UpdateCommand>(
                _keyComparer);

            foreach (DynamicUpdateCommand command in this.Vertices.OfType<DynamicUpdateCommand>())
            {
                if (ModificationOperator.Update == command.Operator ||
                    ModificationOperator.Insert == command.Operator)
                {
                    foreach (ReferentialConstraint fkConstraint in _targetMap.EnumerateValues(command.Table))
                    {
                        ForeignKeyValue fk;
                        if (ForeignKeyValue.TryCreateTargetKey(fkConstraint, command.CurrentValues, true, out fk))
                        {
                            // if this is an update and the target key is unchanged, there is no
                            // need to add a dependency (from the perspective of the target, the update
                            // is a no-op)
                            ForeignKeyValue originalFK;
                            if (ModificationOperator.Update != command.Operator ||
                                !ForeignKeyValue.TryCreateTargetKey(fkConstraint, command.OriginalValues, true, out originalFK) ||
                                !_keyComparer.Equals(originalFK, fk))
                            {
                                predecessors.Add(fk, command);
                            }
                        }
                    }
                }

                // register all source predecessors
                if (ModificationOperator.Update == command.Operator ||
                    ModificationOperator.Delete == command.Operator)
                {
                    foreach (ReferentialConstraint fkConstraint in _sourceMap.EnumerateValues(command.Table))
                    {
                        ForeignKeyValue fk;
                        if (ForeignKeyValue.TryCreateSourceKey(fkConstraint, command.OriginalValues, false, out fk))
                        {
                            // if this is an update and the source key is unchanged, there is no
                            // need to add a dependency (from the perspective of the source, the update
                            // is a no-op)
                            ForeignKeyValue currentFK;
                            if (ModificationOperator.Update != command.Operator ||
                                !ForeignKeyValue.TryCreateSourceKey(fkConstraint, command.CurrentValues, false, out currentFK) ||
                                !_keyComparer.Equals(currentFK, fk))
                            {
                                predecessors.Add(fk, command);
                            }
                        }
                    }
                }
            }
            return predecessors;
        }

        /// <summary>
        /// For function commands, we infer constraints based on relationships and entities. For instance,
        /// we always insert an entity before inserting a relationship referencing that entity. When dynamic
        /// and function UpdateCommands are mixed, we also fall back on this same interpretation.
        /// </summary>
        private void AddModelDependencies()
        {
            KeyToListMap<EntityKey, UpdateCommand> addedEntities = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);
            KeyToListMap<EntityKey, UpdateCommand> deletedEntities = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);
            KeyToListMap<EntityKey, UpdateCommand> addedRelationships = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);
            KeyToListMap<EntityKey, UpdateCommand> deletedRelationships = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);

            foreach (UpdateCommand command in this.Vertices)
            {
                command.GetRequiredAndProducedEntities(_translator, addedEntities, deletedEntities, addedRelationships, deletedRelationships);
            }

            // Add entities before adding dependent relationships
            AddModelDependencies(producedMap: addedEntities, requiredMap: addedRelationships);

            // Delete dependent relationships before deleting entities
            AddModelDependencies(producedMap: deletedRelationships, requiredMap: deletedEntities);
        }

        private void AddModelDependencies(KeyToListMap<EntityKey, UpdateCommand> producedMap, KeyToListMap<EntityKey, UpdateCommand> requiredMap)
        {
            foreach (var keyAndCommands in requiredMap.KeyValuePairs)
            {
                EntityKey key = keyAndCommands.Key;
                List<UpdateCommand> commandsRequiringKey = keyAndCommands.Value;

                foreach (UpdateCommand commandProducingKey in producedMap.EnumerateValues(key))
                {
                    foreach (UpdateCommand commandRequiringKey in commandsRequiringKey)
                    {
                        // command cannot depend on itself and only function commands
                        // need to worry about model dependencies (dynamic commands know about foreign keys)
                        if (!object.ReferenceEquals(commandProducingKey, commandRequiringKey) &&
                            (commandProducingKey.Kind == UpdateCommandKind.Function ||
                             commandRequiringKey.Kind == UpdateCommandKind.Function))
                        {
                            // add a dependency
                            AddEdge(commandProducingKey, commandRequiringKey);
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Describes an update command's foreign key (source or target)
        /// </summary>
        private struct ForeignKeyValue
        {
            /// <summary>
            /// Constructor
            /// </summary>
            /// <param name="metadata">Sets Metadata</param>
            /// <param name="record">Record containing key value</param>
            /// <param name="isTarget">Indicates whether the source or target end of the constraint
            /// is being pulled</param>
            /// <param name="isInsert">Indicates whether this is an insert dependency or a delete
            /// dependency</param>
            private ForeignKeyValue(ReferentialConstraint metadata, PropagatorResult record,
                bool isTarget, bool isInsert)
            {
                Metadata = metadata;

                // construct key
                IList<EdmProperty> keyProperties = isTarget ? metadata.FromProperties :
                    metadata.ToProperties;
                PropagatorResult[] keyValues = new PropagatorResult[keyProperties.Count];
                bool hasNullMember = false;
                for (int i = 0; i < keyValues.Length; i++)
                {
                    keyValues[i] = record.GetMemberValue(keyProperties[i]);
                    if (keyValues[i].IsNull)
                    {
                        hasNullMember = true;
                        break;
                    }
                }

                if (hasNullMember)
                {
                    // set key to null to indicate that it is not behaving as a key
                    // (in SQL, keys with null parts do not participate in constraints)
                    Key = null;
                }
                else
                {
                    Key = new CompositeKey(keyValues);
                }

                IsInsert = isInsert;
            }

            /// <summary>
            /// Initialize foreign key object for the target of a foreign key.
            /// </summary>
            /// <param name="metadata">Sets Metadata</param>
            /// <param name="record">Record containing key value</param>
            /// <param name="isInsert">Indicates whether the key value is being inserted or deleted</param>
            /// <param name="key">Outputs key object</param>
            /// <returns>true if the record contains key values for this constraint; false otherwise</returns>
            internal static bool TryCreateTargetKey(ReferentialConstraint metadata, PropagatorResult record, bool isInsert, out ForeignKeyValue key)
            {
                key = new ForeignKeyValue(metadata, record, true, isInsert);
                if (null == key.Key)
                {
                    return false;
                }
                return true;
            }

            /// <summary>
            /// Initialize foreign key object for the source of a foreign key.
            /// </summary>
            /// <param name="metadata">Sets Metadata</param>
            /// <param name="record">Record containing key value</param>
            /// <param name="isInsert">Indicates whether the key value is being inserted or deleted</param>
            /// <param name="key">Outputs key object</param>
            /// <returns>true if the record contains key values for this constraint; false otherwise</returns>
            internal static bool TryCreateSourceKey(ReferentialConstraint metadata, PropagatorResult record, bool isInsert, out ForeignKeyValue key)
            {
                key = new ForeignKeyValue(metadata, record, false, isInsert);
                if (null == key.Key)
                {
                    return false;
                }
                return true;
            }

            /// <summary>
            /// Foreign key metadata.
            /// </summary>
            internal readonly ReferentialConstraint Metadata;

            /// <summary>
            /// Foreign key value.
            /// </summary>
            internal readonly CompositeKey Key;

            /// <summary>
            /// Indicates whether this is an inserted or deleted key value.
            /// </summary>
            internal readonly bool IsInsert;
        }

        /// <summary>
        /// Equality comparer for ForeignKey class.
        /// </summary>
        private class ForeignKeyValueComparer : IEqualityComparer<ForeignKeyValue>
        {
            private readonly IEqualityComparer<CompositeKey> _baseComparer;

            internal ForeignKeyValueComparer(IEqualityComparer<CompositeKey> baseComparer)
            {
                _baseComparer = EntityUtil.CheckArgumentNull(baseComparer, "baseComparer");
            }

            public bool Equals(ForeignKeyValue x, ForeignKeyValue y)
            {
                return x.IsInsert == y.IsInsert && x.Metadata == y.Metadata &&
                    _baseComparer.Equals(x.Key, y.Key);
            }

            public int GetHashCode(ForeignKeyValue obj)
            {
                return _baseComparer.GetHashCode(obj.Key);
            }
        }
    }
}