// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using System.Collections.Immutable;
using System.Diagnostics;
using Microsoft.CodeAnalysis.Text;
using System.Collections.Generic;

namespace Microsoft.CodeAnalysis.CodeGen
{
    internal partial struct SwitchIntegralJumpTableEmitter
    {
        private struct SwitchBucket
        {
            // sorted case labels
            private readonly ImmutableArray<KeyValuePair<ConstantValue, object>> _allLabels;

            // range of sorted case labels within this bucket
            private readonly int _startLabelIndex;
            private readonly int _endLabelIndex;

            private readonly bool _isKnownDegenerate;

            /// <summary>
            ///  Degenerate buckets here are buckets with contiguous range of constants
            ///  leading to the same label. Like:
            ///
            ///      case 0:
            ///      case 1:
            ///      case 2:
            ///      case 3:
            ///           DoOneThing();
            ///           break;               
            ///
            ///      case 4:
            ///      case 5:
            ///      case 6:
            ///      case 7:
            ///           DoAnotherThing();
            ///           break;   
            ///  
            ///  NOTE: A trivial bucket with only one case constant is by definition degenerate.
            /// </summary>
            internal bool IsDegenerate
            {
                get
                {
                    return _isKnownDegenerate;
                }
            }

            internal SwitchBucket(ImmutableArray<KeyValuePair<ConstantValue, object>> allLabels, int index)
            {
                _startLabelIndex = index;
                _endLabelIndex = index;
                _allLabels = allLabels;
                _isKnownDegenerate = true;
            }

            private SwitchBucket(ImmutableArray<KeyValuePair<ConstantValue, object>> allLabels, int startIndex, int endIndex)
            {
                Debug.Assert((uint)startIndex < (uint)endIndex);

                _startLabelIndex = startIndex;
                _endLabelIndex = endIndex;
                _allLabels = allLabels;
                _isKnownDegenerate = false;
            }

            internal SwitchBucket(ImmutableArray<KeyValuePair<ConstantValue, object>> allLabels, int startIndex, int endIndex, bool isDegenerate)
            {
                Debug.Assert((uint)startIndex <= (uint)endIndex);
                Debug.Assert((uint)startIndex != (uint)endIndex || isDegenerate);

                _startLabelIndex = startIndex;
                _endLabelIndex = endIndex;
                _allLabels = allLabels;
                _isKnownDegenerate = isDegenerate;
            }

            internal uint LabelsCount
            {
                get
                {
                    return (uint)(_endLabelIndex - _startLabelIndex + 1);
                }
            }

            internal KeyValuePair<ConstantValue, object> this[int i]
            {
                get
                {
                    Debug.Assert(i < LabelsCount, "index out of range");
                    return _allLabels[i + _startLabelIndex];
                }
            }

            internal ulong BucketSize
            {
                get
                {
                    return GetBucketSize(this.StartConstant, this.EndConstant);
                }
            }

            // if a bucket could be split into two degenerate ones
            // specifies a label index where the second bucket would start
            // -1 indicates that the bucket cannot be split into degenerate ones
            //  0 indicates that the bucket is already degenerate
            // 
            // Code Review question: why are we supporting splitting only in two buckets. Why not in more?
            // Explanation:
            //  The input here is a "dense" bucket - the one that previous heuristics 
            //  determined as not worth splitting. 
            //
            //  A dense bucket has rough execution cost of 1 conditional branch (range check) 
            //  and 1 computed branch (which cost roughly the same as conditional one or perhaps more).
            //  The only way to surely beat that cost via splitting is if the bucket can be 
            //  split into 2 degenerate buckets. Then we have just 2 conditional branches.
            //
            //  3 degenerate buckets would require up to 3 conditional branches. 
            //  On some hardware computed jumps may cost significantly more than 
            //  conditional ones (because they are harder to predict or whatever), 
            //  so it could still be profitable, but I did not want to guess that.
            //
            //  Basically if we have 3 degenerate buckets that can be merged into a dense bucket, 
            //  we prefer a dense bucket, which we emit as "switch" opcode.
            //
            internal int DegenerateBucketSplit
            {
                get
                {
                    if (IsDegenerate)
                    {
                        return 0;
                    }

                    Debug.Assert(_startLabelIndex != _endLabelIndex, "1-sized buckets should be already known as degenerate.");

                    var allLabels = this._allLabels;
                    var split = 0;
                    var lastConst = this.StartConstant;
                    var lastLabel = allLabels[_startLabelIndex].Value;

                    for (int idx = _startLabelIndex + 1; idx <= _endLabelIndex; idx++)
                    {
                        var switchLabel = allLabels[idx];

                        if (lastLabel != switchLabel.Value ||
                            !IsContiguous(lastConst, switchLabel.Key))
                        {
                            if (split != 0)
                            {
                                // found another discontinuity, so cannot be split
                                return -1;
                            }

                            split = idx;
                            lastLabel = switchLabel.Value;
                        }

                        lastConst = switchLabel.Key;
                    }

                    return split;
                }
            }

            private bool IsContiguous(ConstantValue lastConst, ConstantValue nextConst)
            {
                if (!lastConst.IsNumeric || !nextConst.IsNumeric)
                {
                    return false;
                }

                return GetBucketSize(lastConst, nextConst) == 2;
            }

            private static ulong GetBucketSize(ConstantValue startConstant, ConstantValue endConstant)
            {
                Debug.Assert(!BucketOverflowUInt64Limit(startConstant, endConstant));
                Debug.Assert(endConstant.Discriminator == startConstant.Discriminator);

                ulong bucketSize;

                if (startConstant.IsNegativeNumeric || endConstant.IsNegativeNumeric)
                {
                    Debug.Assert(endConstant.Int64Value >= startConstant.Int64Value);
                    bucketSize = unchecked((ulong)(endConstant.Int64Value - startConstant.Int64Value + 1));
                }
                else
                {
                    Debug.Assert(endConstant.UInt64Value >= startConstant.UInt64Value);
                    bucketSize = endConstant.UInt64Value - startConstant.UInt64Value + 1;
                }

                return bucketSize;
            }

            // Check if bucket size exceeds UInt64.MaxValue
            private static bool BucketOverflowUInt64Limit(ConstantValue startConstant, ConstantValue endConstant)
            {
                Debug.Assert(IsValidSwitchBucketConstantPair(startConstant, endConstant));

                if (startConstant.Discriminator == ConstantValueTypeDiscriminator.Int64)
                {
                    return startConstant.Int64Value == Int64.MinValue
                        && endConstant.Int64Value == Int64.MaxValue;
                }
                else if (startConstant.Discriminator == ConstantValueTypeDiscriminator.UInt64)
                {
                    return startConstant.UInt64Value == UInt64.MinValue
                        && endConstant.UInt64Value == UInt64.MaxValue;
                }

                return false;
            }

            // Virtual switch instruction has a max limit of Int32.MaxValue labels
            // Check if bucket size exceeds Int32.MaxValue
            private static bool BucketOverflow(ConstantValue startConstant, ConstantValue endConstant)
            {
                return BucketOverflowUInt64Limit(startConstant, endConstant)
                    || GetBucketSize(startConstant, endConstant) > Int32.MaxValue;
            }

            internal int StartLabelIndex
            {
                get
                {
                    return _startLabelIndex;
                }
            }

            internal int EndLabelIndex
            {
                get
                {
                    return _endLabelIndex;
                }
            }

            internal ConstantValue StartConstant
            {
                get
                {
                    return _allLabels[_startLabelIndex].Key;
                }
            }

            internal ConstantValue EndConstant
            {
                get
                {
                    return _allLabels[_endLabelIndex].Key;
                }
            }

            private static bool IsValidSwitchBucketConstant(ConstantValue constant)
            {
                return constant != null
                    && SwitchConstantValueHelper.IsValidSwitchCaseLabelConstant(constant)
                    && !constant.IsNull
                    && !constant.IsString;
            }

            private static bool IsValidSwitchBucketConstantPair(ConstantValue startConstant, ConstantValue endConstant)
            {
                return IsValidSwitchBucketConstant(startConstant)
                    && IsValidSwitchBucketConstant(endConstant)
                    && startConstant.IsUnsigned == endConstant.IsUnsigned;
            }

            private static bool IsSparse(uint labelsCount, ulong bucketSize)
            {
                // TODO: consider changing threshold bucket density to 33%
                return bucketSize >= labelsCount * 2;
            }

            internal static bool MergeIsAdvantageous(SwitchBucket bucket1, SwitchBucket bucket2)
            {
                var startConstant = bucket1.StartConstant;
                var endConstant = bucket2.EndConstant;

                if (BucketOverflow(startConstant, endConstant))
                {
                    // merged bucket would overflow
                    return false;
                }

                uint labelsCount = (uint)(bucket1.LabelsCount + bucket2.LabelsCount);
                ulong bucketSize = GetBucketSize(startConstant, endConstant);

                return !IsSparse(labelsCount, bucketSize);
            }

            /// <summary>
            /// Try to merge with the nextBucket.
            /// If merge results in a better bucket than two original ones, merge and return true.
            /// Else don't merge and return false.
            /// </summary>
            internal bool TryMergeWith(SwitchBucket prevBucket)
            {
                Debug.Assert(prevBucket._endLabelIndex + 1 == _startLabelIndex);
                if (MergeIsAdvantageous(prevBucket, this))
                {
                    this = new SwitchBucket(_allLabels, prevBucket._startLabelIndex, _endLabelIndex);
                    return true;
                }

                return false;
            }
        }
    }
}