// Copyright (c) 2014 AlphaSierraPapa for the SharpDevelop Team
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy of this
// software and associated documentation files (the "Software"), to deal in the Software
// without restriction, including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
// to whom the Software is furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all copies or
// substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using Unity.CodeEditor.Utils;

namespace Unity.CodeEditor.Document
{
    /// <summary>
    /// Undo stack implementation.
    /// </summary>
    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1711:IdentifiersShouldNotHaveIncorrectSuffix")]
    internal sealed class UndoStack : INotifyPropertyChanged
    {
        /// undo stack is listening for changes
        internal const int StateListen = 0;
        /// undo stack is reverting/repeating a set of changes
        internal const int StatePlayback = 1;
        // undo stack is reverting/repeating a set of changes and modifies the document to do this
        internal const int StatePlaybackModifyDocument = 2;
        /// state is used for checking that noone but the UndoStack performs changes
        /// during Undo events
        internal int State { get; set; } = StateListen;

        private readonly Deque<IUndoableOperation> _undostack = new Deque<IUndoableOperation>();
        private readonly Deque<IUndoableOperation> _redostack = new Deque<IUndoableOperation>();
        private int _sizeLimit = int.MaxValue;

        private int _undoGroupDepth;
        private int _actionCountInUndoGroup;
        private int _optionalActionCount;
        private bool _allowContinue;

        #region IsOriginalFile implementation
        // implements feature request SD2-784 - File still considered dirty after undoing all changes

        /// <summary>
        /// Number of times undo must be executed until the original state is reached.
        /// Negative: number of times redo must be executed until the original state is reached.
        /// Special case: int.MinValue == original state is unreachable
        /// </summary>
        private int _elementsOnUndoUntilOriginalFile;

        /// <summary>
        /// Gets whether the document is currently in its original state (no modifications).
        /// </summary>
        internal bool IsOriginalFile { get; private set; } = true;

        private void RecalcIsOriginalFile()
        {
            var newIsOriginalFile = (_elementsOnUndoUntilOriginalFile == 0);
            if (newIsOriginalFile != IsOriginalFile)
            {
                IsOriginalFile = newIsOriginalFile;
                NotifyPropertyChanged("IsOriginalFile");
            }
        }

        /// <summary>
        /// Marks the current state as original. Discards any previous "original" markers.
        /// </summary>
        internal void MarkAsOriginalFile()
        {
            _elementsOnUndoUntilOriginalFile = 0;
            RecalcIsOriginalFile();
        }

        /// <summary>
        /// Discards the current "original" marker.
        /// </summary>
        internal void DiscardOriginalFileMarker()
        {
            _elementsOnUndoUntilOriginalFile = int.MinValue;
            RecalcIsOriginalFile();
        }

        private void FileModified(int newElementsOnUndoStack)
        {
            if (_elementsOnUndoUntilOriginalFile == int.MinValue)
                return;

            _elementsOnUndoUntilOriginalFile += newElementsOnUndoStack;
            if (_elementsOnUndoUntilOriginalFile > _undostack.Count)
                _elementsOnUndoUntilOriginalFile = int.MinValue;

            // don't call RecalcIsOriginalFile(): wait until end of undo group
        }
        #endregion

        /// <summary>
        /// Gets if the undo stack currently accepts changes.
        /// Is false while an undo action is running.
        /// </summary>
        internal bool AcceptChanges => State == StateListen;

        /// <summary>
        /// Gets if there are actions on the undo stack.
        /// Use the PropertyChanged event to listen to changes of this property.
        /// </summary>
        internal bool CanUndo => _undostack.Count > 0;

        /// <summary>
        /// Gets if there are actions on the redo stack.
        /// Use the PropertyChanged event to listen to changes of this property.
        /// </summary>
        internal bool CanRedo => _redostack.Count > 0;

        /// <summary>
        /// Gets/Sets the limit on the number of items on the undo stack.
        /// </summary>
        /// <remarks>The size limit is enforced only on the number of stored top-level undo groups.
        /// Elements within undo groups do not count towards the size limit.</remarks>
        internal int SizeLimit
        {
            get => _sizeLimit;
            set
            {
                if (value < 0)
                    ThrowUtil.CheckNotNegative(value, "value");
                if (_sizeLimit != value)
                {
                    _sizeLimit = value;
                    NotifyPropertyChanged("SizeLimit");
                    if (_undoGroupDepth == 0)
                        EnforceSizeLimit();
                }
            }
        }

        private void EnforceSizeLimit()
        {
            Debug.Assert(_undoGroupDepth == 0);
            while (_undostack.Count > _sizeLimit)
                _undostack.PopFront();
            while (_redostack.Count > _sizeLimit)
                _redostack.PopFront();
        }

        /// <summary>
        /// If an undo group is open, gets the group descriptor of the current top-level
        /// undo group.
        /// If no undo group is open, gets the group descriptor from the previous undo group.
        /// </summary>
        /// <remarks>The group descriptor can be used to join adjacent undo groups:
        /// use a group descriptor to mark your changes, and on the second action,
        /// compare LastGroupDescriptor and use <see cref="StartContinuedUndoGroup"/> if you
        /// want to join the undo groups.</remarks>
        internal object LastGroupDescriptor { get; private set; }

        /// <summary>
        /// Starts grouping changes.
        /// Maintains a counter so that nested calls are possible.
        /// </summary>
        internal void StartUndoGroup()
        {
            StartUndoGroup(null);
        }

        /// <summary>
        /// Starts grouping changes.
        /// Maintains a counter so that nested calls are possible.
        /// </summary>
        /// <param name="groupDescriptor">An object that is stored with the undo group.
        /// If this is not a top-level undo group, the parameter is ignored.</param>
        internal void StartUndoGroup(object groupDescriptor)
        {
            if (_undoGroupDepth == 0)
            {
                _actionCountInUndoGroup = 0;
                _optionalActionCount = 0;
                LastGroupDescriptor = groupDescriptor;
            }
            _undoGroupDepth++;
            //Util.LoggingService.Debug("Open undo group (new depth=" + undoGroupDepth + ")");
        }

        /// <summary>
        /// Starts grouping changes, continuing with the previously closed undo group if possible.
        /// Maintains a counter so that nested calls are possible.
        /// If the call to StartContinuedUndoGroup is a nested call, it behaves exactly
        /// as <see cref="StartUndoGroup()"/>, only top-level calls can continue existing undo groups.
        /// </summary>
        /// <param name="groupDescriptor">An object that is stored with the undo group.
        /// If this is not a top-level undo group, the parameter is ignored.</param>
        internal void StartContinuedUndoGroup(object groupDescriptor = null)
        {
            if (_undoGroupDepth == 0)
            {
                _actionCountInUndoGroup = (_allowContinue && _undostack.Count > 0) ? 1 : 0;
                _optionalActionCount = 0;
                LastGroupDescriptor = groupDescriptor;
            }
            _undoGroupDepth++;
            //Util.LoggingService.Debug("Continue undo group (new depth=" + undoGroupDepth + ")");
        }

        /// <summary>
        /// Stops grouping changes.
        /// </summary>
        internal void EndUndoGroup()
        {
            if (_undoGroupDepth == 0) throw new InvalidOperationException("There are no open undo groups");
            _undoGroupDepth--;
            //Util.LoggingService.Debug("Close undo group (new depth=" + undoGroupDepth + ")");
            if (_undoGroupDepth == 0)
            {
                Debug.Assert(State == StateListen || _actionCountInUndoGroup == 0);
                _allowContinue = true;
                if (_actionCountInUndoGroup == _optionalActionCount)
                {
                    // only optional actions: don't store them
                    for (var i = 0; i < _optionalActionCount; i++)
                    {
                        _undostack.PopBack();
                    }
                    _allowContinue = false;
                }
                else if (_actionCountInUndoGroup > 1)
                {
                    // combine all actions within the group into a single grouped action
                    _undostack.PushBack(new UndoOperationGroup(_undostack, _actionCountInUndoGroup));
                    FileModified(-_actionCountInUndoGroup + 1 + _optionalActionCount);
                }
                //if (state == StateListen) {
                EnforceSizeLimit();
                RecalcIsOriginalFile(); // can raise event
                                        //}
            }
        }

        /// <summary>
        /// Throws an InvalidOperationException if an undo group is current open.
        /// </summary>
        private void ThrowIfUndoGroupOpen()
        {
            if (_undoGroupDepth != 0)
            {
                _undoGroupDepth = 0;
                throw new InvalidOperationException("No undo group should be open at this point");
            }
            if (State != StateListen)
            {
                throw new InvalidOperationException("This method cannot be called while an undo operation is being performed");
            }
        }

        private List<TextDocument> _affectedDocuments;

        internal void RegisterAffectedDocument(TextDocument document)
        {
            if (_affectedDocuments == null)
                _affectedDocuments = new List<TextDocument>();
            if (!_affectedDocuments.Contains(document))
            {
                _affectedDocuments.Add(document);
                document.BeginUpdate();
            }
        }

        private void CallEndUpdateOnAffectedDocuments()
        {
            if (_affectedDocuments != null)
            {
                foreach (var doc in _affectedDocuments)
                {
                    doc.EndUpdate();
                }
                _affectedDocuments = null;
            }
        }

        /// <summary>
        /// Call this method to undo the last operation on the stack
        /// </summary>
        internal void Undo()
        {
            ThrowIfUndoGroupOpen();
            if (_undostack.Count > 0)
            {
                // disallow continuing undo groups after undo operation
                LastGroupDescriptor = null; _allowContinue = false;
                // fetch operation to undo and move it to redo stack
                var uedit = _undostack.PopBack();
                _redostack.PushBack(uedit);
                State = StatePlayback;
                try
                {
                    RunUndo(uedit);
                }
                finally
                {
                    State = StateListen;
                    FileModified(-1);
                    CallEndUpdateOnAffectedDocuments();
                }
                RecalcIsOriginalFile();
                if (_undostack.Count == 0)
                    NotifyPropertyChanged("CanUndo");
                if (_redostack.Count == 1)
                    NotifyPropertyChanged("CanRedo");
            }
        }

        internal void RunUndo(IUndoableOperation op)
        {
            if (op is IUndoableOperationWithContext opWithCtx)
                opWithCtx.Undo(this);
            else
                op.Undo();
        }

        /// <summary>
        /// Call this method to redo the last undone operation
        /// </summary>
        internal void Redo()
        {
            ThrowIfUndoGroupOpen();
            if (_redostack.Count > 0)
            {
                LastGroupDescriptor = null;
                _allowContinue = false;
                var uedit = _redostack.PopBack();
                _undostack.PushBack(uedit);
                State = StatePlayback;
                try
                {
                    RunRedo(uedit);
                }
                finally
                {
                    State = StateListen;
                    FileModified(1);
                    CallEndUpdateOnAffectedDocuments();
                }
                RecalcIsOriginalFile();
                if (_redostack.Count == 0)
                    NotifyPropertyChanged("CanRedo");
                if (_undostack.Count == 1)
                    NotifyPropertyChanged("CanUndo");
            }
        }

        internal void RunRedo(IUndoableOperation op)
        {
            if (op is IUndoableOperationWithContext opWithCtx)
                opWithCtx.Redo(this);
            else
                op.Redo();
        }

        /// <summary>
        /// Call this method to push an UndoableOperation on the undostack.
        /// The redostack will be cleared if you use this method.
        /// </summary>
        internal void Push(IUndoableOperation operation)
        {
            Push(operation, false);
        }

        /// <summary>
        /// Call this method to push an UndoableOperation on the undostack.
        /// However, the operation will be only stored if the undo group contains a
        /// non-optional operation.
        /// Use this method to store the caret position/selection on the undo stack to
        /// prevent having only actions that affect only the caret and not the document.
        /// </summary>
        internal void PushOptional(IUndoableOperation operation)
        {
            if (_undoGroupDepth == 0)
                throw new InvalidOperationException("Cannot use PushOptional outside of undo group");
            Push(operation, true);
        }

        private void Push(IUndoableOperation operation, bool isOptional)
        {
            if (operation == null)
            {
                throw new ArgumentNullException(nameof(operation));
            }

            if (State == StateListen && _sizeLimit > 0)
            {
                var wasEmpty = _undostack.Count == 0;

                var needsUndoGroup = _undoGroupDepth == 0;
                if (needsUndoGroup) StartUndoGroup();
                _undostack.PushBack(operation);
                _actionCountInUndoGroup++;
                if (isOptional)
                    _optionalActionCount++;
                else
                    FileModified(1);
                if (needsUndoGroup) EndUndoGroup();
                if (wasEmpty)
                    NotifyPropertyChanged("CanUndo");
                ClearRedoStack();
            }
        }

        /// <summary>
        /// Call this method, if you want to clear the redo stack
        /// </summary>
        internal void ClearRedoStack()
        {
            if (_redostack.Count != 0)
            {
                _redostack.Clear();
                NotifyPropertyChanged("CanRedo");
                // if the "original file" marker is on the redo stack: remove it
                if (_elementsOnUndoUntilOriginalFile < 0)
                    _elementsOnUndoUntilOriginalFile = int.MinValue;
            }
        }

        /// <summary>
        /// Clears both the undo and redo stack.
        /// </summary>
        internal void ClearAll()
        {
            ThrowIfUndoGroupOpen();
            _actionCountInUndoGroup = 0;
            _optionalActionCount = 0;
            if (_undostack.Count != 0)
            {
                LastGroupDescriptor = null;
                _allowContinue = false;
                _undostack.Clear();
                NotifyPropertyChanged("CanUndo");
            }
            ClearRedoStack();
        }

        internal void Push(TextDocument document, DocumentChangeEventArgs e)
        {
            if (State == StatePlayback)
                throw new InvalidOperationException("Document changes during undo/redo operations are not allowed.");
            if (State == StatePlaybackModifyDocument)
                State = StatePlayback; // allow only 1 change per expected modification
            else
                Push(new DocumentChangeOperation(document, e));
        }

        /// <summary>
        /// Is raised when a property (CanUndo, CanRedo) changed.
        /// </summary>
        public event PropertyChangedEventHandler PropertyChanged;

        private void NotifyPropertyChanged(string propertyName)
        {
            var args = new PropertyChangedEventArgs(propertyName);
            PropertyChanged?.Invoke(this, args);
        }
    }
}