// Copyright (c) Microsoft Open Technologies, Inc. All rights reserved. See License.txt in the project root for license information.

namespace System.Data.Entity.Core.Mapping.Update.Internal
{
    using System.Collections.Generic;
    using System.Data.Entity.Core.Common.Utils;
    using System.Data.Entity.Core.Metadata.Edm;
    using System.Data.Entity.Core.Objects;
    using System.Data.Entity.Resources;
    using System.Data.Entity.Utilities;
    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);

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

            // add all vertices (one vertex for every command)
            foreach (var 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 (var container in containers)
            {
                foreach (var extent in container.BaseEntitySets)
                {
                    var 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"
                            var associationType = associationSet.ElementType;
                            var constraintFound = false;
                            ReferentialConstraint fkConstraint = null;
                            foreach (var 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)
            var predecessors = new Dictionary<int, UpdateCommand>();
            foreach (var command in Vertices)
            {
                foreach (var 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 new UpdateException(
                            Strings.Update_AmbiguousServerGenIdentifier, duplicateKey,
                            command.GetStateEntries(_translator).Cast<ObjectStateEntry>().Distinct());
                    }
                }
            }

            // Identify all dependent input parameters
            foreach (var command in Vertices)
            {
                foreach (var 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()
        {
            var 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 (var command in Vertices.OfType<DynamicUpdateCommand>())
            {
                // register all source successors
                if (ModificationOperator.Update == command.Operator
                    ||
                    ModificationOperator.Insert == command.Operator)
                {
                    foreach (var 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 (var 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 (var 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 (var 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()
        {
            var predecessors = new KeyToListMap<ForeignKeyValue, UpdateCommand>(
                _keyComparer);

            foreach (var command in Vertices.OfType<DynamicUpdateCommand>())
            {
                if (ModificationOperator.Update == command.Operator
                    ||
                    ModificationOperator.Insert == command.Operator)
                {
                    foreach (var 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 (var 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()
        {
            var addedEntities = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);
            var deletedEntities = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);
            var addedRelationships = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);
            var deletedRelationships = new KeyToListMap<EntityKey, UpdateCommand>(EqualityComparer<EntityKey>.Default);

            foreach (var command in 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)
            {
                var key = keyAndCommands.Key;
                var commandsRequiringKey = keyAndCommands.Value;

                foreach (var commandProducingKey in producedMap.EnumerateValues(key))
                {
                    foreach (var 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 (!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;
                var keyValues = new PropagatorResult[keyProperties.Count];
                var hasNullMember = false;
                for (var 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)
            {
                DebugCheck.NotNull(baseComparer);
                _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);
            }
        }
    }
}
