// 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.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Threading;
using Microsoft.CodeAnalysis;
 
namespace Roslyn.Utilities;
 
/// <summary>
/// Stores the "path" from the root of a tree to a node, allowing the node to be recovered in a
/// later snapshot of the tree, under certain circumstances.
/// 
/// The implementation stores the child indices to represent the path, so any edit which affects
/// the child indices could render this object unable to recover its node.  NOTE: One thing C#
/// IDE has done in the past to do a better job of this is to store the fully qualified name of
/// the member to at least be able to descend into the same member.  We could apply the same sort
/// of logic here.
/// </summary>
internal sealed record class SyntaxPath
{
    // A path is made up of 'segments' that lead from root all the way down to the node. The
    // segment contains the index of the node in its parent, as well as the kind of the node.
    // The latter is not strictly necessary.  However, it ensures that resolving the path against
    // a different tree will either return the same type of node as the original, or will fail.  
    private readonly struct PathSegment
    {
        public int Ordinal { get; }
        public int Kind { get; }
 
        public PathSegment(int ordinal, int kind)
            : this()
        {
            this.Ordinal = ordinal;
            this.Kind = kind;
        }
    }
 
    private readonly List<PathSegment> _segments = [];
    private readonly int _kind;
    private readonly bool _trackKinds;
 
    public SyntaxPath(SyntaxNodeOrToken nodeOrToken, bool trackKinds = true)
    {
        _trackKinds = trackKinds;
        _kind = nodeOrToken.RawKind;
        AddSegment(nodeOrToken);
        _segments.TrimExcess();
    }
 
    private void AddSegment(SyntaxNodeOrToken nodeOrToken)
    {
        var parent = nodeOrToken.Parent;
        if (parent != null)
        {
            AddSegment(parent);
 
            // TODO(cyrusn): Is there any way to optimize this for large lists?  I would like to
            // be able to do a binary search.  However, there's no easy way to tell if a node
            // comes before or after another node when searching through a list.  To determine
            // the location of a node, a linear walk is still needed to find it in its parent
            // collection.
 
            var ordinal = 0;
            var kind = nodeOrToken.RawKind;
            foreach (var child in parent.ChildNodesAndTokens())
            {
                if (nodeOrToken == child)
                {
                    _segments.Add(new PathSegment(ordinal, nodeOrToken.RawKind));
                    return;
                }
 
                if (!_trackKinds || child.RawKind == kind)
                {
                    ordinal++;
                }
            }
 
            throw ExceptionUtilities.Unreachable();
        }
    }
 
    /// <summary>
    /// Attempts to recover the node at this path in the provided tree.  If the node is found
    /// then 'true' is returned, otherwise the result is 'false' and 'node' will be null.
    /// </summary>
    public bool TryResolve(SyntaxNode? root, out SyntaxNodeOrToken nodeOrToken)
    {
        nodeOrToken = default;
 
        var current = (SyntaxNodeOrToken)root;
        foreach (var segment in _segments)
        {
            current = FindChild(current, segment);
 
            if (current.RawKind == 0)
            {
                return false;
            }
        }
 
        if (!_trackKinds || current.RawKind == _kind)
        {
            nodeOrToken = current;
            return true;
        }
 
        return false;
    }
 
    private SyntaxNodeOrToken FindChild(SyntaxNodeOrToken current, PathSegment segment)
    {
        var ordinal = segment.Ordinal;
        foreach (var child in current.ChildNodesAndTokens())
        {
            if (!_trackKinds || child.RawKind == segment.Kind)
            {
                if (ordinal == 0)
                {
                    return child;
                }
                else
                {
                    ordinal--;
                }
            }
        }
 
        return default;
    }
 
    public bool TryResolve<TNode>(SyntaxTree syntaxTree, CancellationToken cancellationToken, [NotNullWhen(true)] out TNode? node)
        where TNode : SyntaxNode
    {
        return TryResolve(syntaxTree.GetRoot(cancellationToken), out node);
    }
 
    public bool TryResolve<TNode>(SyntaxNode? root, [NotNullWhen(true)] out TNode? node)
        where TNode : SyntaxNode
    {
        if (TryResolve(root, out var nodeOrToken) &&
            nodeOrToken.IsNode &&
            nodeOrToken.AsNode() is TNode n)
        {
            node = n;
            return true;
        }
 
        node = null;
        return false;
    }
 
    public bool Equals(SyntaxPath? other)
    {
        if (other == null)
        {
            return false;
        }
 
        if (object.ReferenceEquals(this, other))
        {
            return true;
        }
 
        return
            _trackKinds == other._trackKinds &&
            _kind == other._kind &&
            _segments.SequenceEqual(other._segments, static (x, y) => x.Equals(y));
    }
 
    public override int GetHashCode()
        => Hash.Combine(_trackKinds, Hash.Combine(_kind, GetSegmentHashCode()));
 
    private int GetSegmentHashCode()
    {
        var hash = 1;
 
        foreach (var segment in _segments)
            hash = Hash.Combine(Hash.Combine(segment.Kind, segment.Ordinal), hash);
 
        return hash;
    }
}