// WPFMA-SDK needs Unity 2022.3 (VRChat's version); on older Unity this file is skipped and WPFMAUnityVersionNotice explains why.
#if UNITY_2022_3_OR_NEWER
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace WPFMA.Team
{
    /// <summary>
    /// Gets two copies of a scene or prefab ready for Unity's merge tool. Unity's own object IDs inside a file aren't
    /// the same in two editors (objects made together live get each editor's own IDs), so the merge tool would see
    /// "you both added a Wall" and keep two. Here every object is recognised by where it is - its name and its parent,
    /// like you would in the Hierarchy, and its components by type - and the other copy takes our IDs for the objects
    /// we both have. Objects only one side has keep theirs (renumbered if one happens to be in use already).
    /// </summary>
    internal static class TeamSceneAlign
    {
        private sealed class Doc
        {
            public int Class;
            public long Id;
            public bool Stripped;
            public string Text;
        }

        private sealed class Index
        {
            public readonly List<Doc> Docs = new List<Doc>();
            public readonly Dictionary<long, Doc> ById = new Dictionary<long, Doc>();
            public readonly Dictionary<long, string> KeyOf = new Dictionary<long, string>();
            public readonly Dictionary<string, long> IdOfKey = new Dictionary<string, long>();
            public readonly HashSet<string> Ambiguous = new HashSet<string>();
            public List<long> Roots;
            public readonly Dictionary<long, string> TransformKeys = new Dictionary<long, string>();
            public readonly Dictionary<long, string> InstanceKeys = new Dictionary<long, string>();
        }

        private const long Mask = 0x7FFFFFFFFFFFFFFF;
        private static readonly Regex Header = new Regex(@"^--- !u!(\d+) &(-?\d+)( stripped)?", RegexOptions.Compiled);
        private static readonly Regex HeaderLine = new Regex(@"(?m)^--- !u!(\d+) &(-?\d+)", RegexOptions.Compiled);
        private static readonly Regex LocalRef = new Regex(@"\{fileID: (-?\d+)\}", RegexOptions.Compiled);
        private static readonly Regex RefLine = new Regex(@"^\s*- \{fileID: (-?\d+)\}\s*$", RegexOptions.Compiled);

        private static bool IsTransform(int cls)
        {
            return cls == 4 || cls == 224;
        }

        // ---- Reading ------------------------------------------------------------------------------------------------

        private static Index Read(string text)
        {
            var index = new Index();
            var parts = Regex.Split(text, @"(?m)^(?=--- !u!)");
            foreach (var part in parts)
            {
                var match = Header.Match(part);
                if (!match.Success)
                    continue;
                var doc = new Doc { Class = int.Parse(match.Groups[1].Value), Id = long.Parse(match.Groups[2].Value), Stripped = match.Groups[3].Success, Text = part };
                index.Docs.Add(doc);
                index.ById[doc.Id] = doc;
            }
            var rootsDoc = index.Docs.FirstOrDefault(d => d.Class == 1660057539);
            index.Roots = rootsDoc != null ? RefList(rootsDoc.Text, "m_Roots") : null;
            return index;
        }

        private static long Ref(string text, string field)
        {
            var match = Regex.Match(text, "(?m)^\\s*" + Regex.Escape(field) + ": \\{fileID: (-?\\d+)\\}");
            return match.Success ? long.Parse(match.Groups[1].Value) : 0;
        }

        private static long SourceFile(string text, out string guid)
        {
            var match = Regex.Match(text, @"m_CorrespondingSourceObject: \{fileID: (-?\d+), guid: (\w+)");
            guid = match.Success ? match.Groups[2].Value : null;
            return match.Success ? long.Parse(match.Groups[1].Value) : 0;
        }

        private static List<long> RefList(string text, string field)
        {
            var list = new List<long>();
            var lines = text.Split('\n');
            bool inList = false;
            foreach (var raw in lines)
            {
                string line = raw.TrimEnd('\r');
                if (!inList)
                {
                    if (Regex.IsMatch(line, "^\\s*" + Regex.Escape(field) + ":\\s*$"))
                        inList = true;
                    continue;
                }
                var match = RefLine.Match(line);
                if (!match.Success)
                    break;
                list.Add(long.Parse(match.Groups[1].Value));
            }
            return list;
        }

        private static List<long> Components(string text)
        {
            return Regex.Matches(text, @"- component: \{fileID: (-?\d+)\}").Cast<Match>().Select(m => long.Parse(m.Groups[1].Value)).ToList();
        }

        private static string Name(Doc go)
        {
            if (go == null)
                return "?";
            var match = Regex.Match(go.Text, @"(?m)^  m_Name: ?(.*?)\r?$");
            return match.Success ? match.Groups[1].Value : "?";
        }

        private static string ScriptGuid(string text)
        {
            var match = Regex.Match(text, @"m_Script: \{fileID: -?\d+, guid: (\w+)");
            return match.Success ? match.Groups[1].Value : string.Empty;
        }

        // ---- Recognising objects --------------------------------------------------------------------------------

        private static string InstanceName(Index index, long instanceId)
        {
            Doc doc;
            if (!index.ById.TryGetValue(instanceId, out doc))
                return "?";
            var match = Regex.Match(doc.Text, @"propertyPath: m_Name\r?\n\s*value: ?(.*?)\r?\n");
            return match.Success ? match.Groups[1].Value : "?";
        }

        private static string SourcePrefab(Index index, long instanceId)
        {
            Doc doc;
            if (!index.ById.TryGetValue(instanceId, out doc))
                return "?";
            var match = Regex.Match(doc.Text, @"m_SourcePrefab: \{fileID: -?\d+, guid: (\w+)");
            return match.Success ? match.Groups[1].Value : "?";
        }

        /// <summary>The name a transform shows in the Hierarchy (a placed prefab's root uses its overridden name).</summary>
        private static string TransformName(Index index, long transformId)
        {
            Doc doc;
            if (!index.ById.TryGetValue(transformId, out doc))
                return "?";
            if (doc.Stripped)
                return InstanceName(index, Ref(doc.Text, "m_PrefabInstance"));
            Doc go;
            index.ById.TryGetValue(Ref(doc.Text, "m_GameObject"), out go);
            return Name(go);
        }

        private static List<long> Siblings(Index index, long father)
        {
            if (father == 0)
            {
                if (index.Roots != null)
                    return index.Roots;
                // Older scenes without a root list: every transform without a parent, in file order.
                return index.Docs.Where(d => IsTransform(d.Class) && !d.Stripped && Ref(d.Text, "m_Father") == 0).Select(d => d.Id).ToList();
            }
            Doc parent;
            if (index.ById.TryGetValue(father, out parent) && !parent.Stripped)
            {
                var children = RefList(parent.Text, "m_Children");
                if (children.Count > 0)
                    return children;
            }
            // Under a placed prefab (no children list): in file order.
            return index.Docs.Where(d => IsTransform(d.Class) && !d.Stripped && Ref(d.Text, "m_Father") == father).Select(d => d.Id).ToList();
        }

        private static string TransformKey(Index index, long transformId, int depth = 0)
        {
            string key;
            if (index.TransformKeys.TryGetValue(transformId, out key))
                return key;
            Doc doc;
            if (depth > 200 || !index.ById.TryGetValue(transformId, out doc))
                return "?" + transformId;
            if (doc.Stripped)
            {
                string guid;
                long source = SourceFile(doc.Text, out guid);
                key = InstanceKey(index, Ref(doc.Text, "m_PrefabInstance"), depth + 1) + ":" + source;
            }
            else
            {
                long father = Ref(doc.Text, "m_Father");
                string name = TransformName(index, transformId);
                int n = 0;
                foreach (var sibling in Siblings(index, father))
                {
                    if (sibling == transformId)
                        break;
                    if (TransformName(index, sibling) == name)
                        n++;
                }
                key = (father == 0 ? string.Empty : TransformKey(index, father, depth + 1)) + "/" + name + "#" + n;
            }
            index.TransformKeys[transformId] = key;
            return key;
        }

        private static string InstanceKey(Index index, long instanceId, int depth = 0)
        {
            string key;
            if (index.InstanceKeys.TryGetValue(instanceId, out key))
                return key;
            Doc doc;
            if (depth > 200 || !index.ById.TryGetValue(instanceId, out doc))
                return "?" + instanceId;
            long parent = Ref(doc.Text, "m_TransformParent");
            string guid = SourcePrefab(index, instanceId), name = InstanceName(index, instanceId);
            int n = 0;
            foreach (var other in index.Docs.Where(d => d.Class == 1001))
            {
                if (other.Id == instanceId)
                    break;
                if (Ref(other.Text, "m_TransformParent") == parent && SourcePrefab(index, other.Id) == guid && InstanceName(index, other.Id) == name)
                    n++;
            }
            key = (parent == 0 ? string.Empty : TransformKey(index, parent, depth + 1)) + "/[prefab " + guid + " " + name + "]#" + n;
            index.InstanceKeys[instanceId] = key;
            return key;
        }

        private static void AddKey(Index index, long id, string key)
        {
            if (key == null || index.KeyOf.ContainsKey(id))
                return;
            if (index.IdOfKey.ContainsKey(key))
            {
                index.Ambiguous.Add(key);
                return;
            }
            index.KeyOf[id] = key;
            index.IdOfKey[key] = id;
        }

        /// <summary>Gives every object in the file a name that's the same in any copy of it.</summary>
        private static void Recognise(Index index)
        {
            // Placed prefabs, and the bits of them the file mentions.
            foreach (var doc in index.Docs.Where(d => d.Class == 1001))
                AddKey(index, doc.Id, InstanceKey(index, doc.Id));
            foreach (var doc in index.Docs.Where(d => d.Stripped))
            {
                string guid;
                long source = SourceFile(doc.Text, out guid);
                AddKey(index, doc.Id, InstanceKey(index, Ref(doc.Text, "m_PrefabInstance")) + ":" + source + ":" + doc.Class);
            }

            // GameObjects (by their transform's place) and their components (by type, in order).
            foreach (var go in index.Docs.Where(d => d.Class == 1 && !d.Stripped))
            {
                var components = Components(go.Text);
                long transform = components.FirstOrDefault(c => index.ById.ContainsKey(c) && IsTransform(index.ById[c].Class));
                if (transform == 0)
                    continue;
                string key = TransformKey(index, transform);
                AddKey(index, go.Id, key + "|go");
                var seen = new Dictionary<string, int>();
                foreach (var component in components)
                {
                    Doc doc;
                    if (!index.ById.TryGetValue(component, out doc))
                        continue;
                    string type = doc.Class + ":" + ScriptGuid(doc.Text);
                    int n;
                    seen.TryGetValue(type, out n);
                    seen[type] = n + 1;
                    AddKey(index, component, key + "|" + type + "#" + n);
                }
            }

            // Components added to a placed prefab's objects.
            var added = new Dictionary<string, int>();
            foreach (var doc in index.Docs.Where(d => !d.Stripped && d.Class != 1 && !index.KeyOf.ContainsKey(d.Id)))
            {
                long owner = Ref(doc.Text, "m_GameObject");
                string ownerKey;
                if (owner == 0 || !index.KeyOf.TryGetValue(owner, out ownerKey))
                    continue;
                string type = ownerKey + "|added " + doc.Class + ":" + ScriptGuid(doc.Text);
                int n;
                added.TryGetValue(type, out n);
                added[type] = n + 1;
                AddKey(index, doc.Id, type + "#" + n);
            }

            // Everything else (scene settings and the like): by type, in order.
            var other = new Dictionary<int, int>();
            foreach (var doc in index.Docs.Where(d => !index.KeyOf.ContainsKey(d.Id)))
            {
                int n;
                other.TryGetValue(doc.Class, out n);
                other[doc.Class] = n + 1;
                AddKey(index, doc.Id, "doc " + doc.Class + "#" + n);
            }

            foreach (var key in index.Ambiguous)
            {
                long id;
                if (index.IdOfKey.TryGetValue(key, out id))
                {
                    index.IdOfKey.Remove(key);
                    index.KeyOf.Remove(id);
                }
            }
        }

        // ---- Lining up --------------------------------------------------------------------------------------------

        /// <summary>
        /// Returns <paramref name="other"/> with our IDs for every object we both have, and fresh IDs for its own
        /// objects whose ID we already use for something else. Unchanged if it isn't a Unity text file.
        /// </summary>
        internal static string AlignTo(string other, string ours)
        {
            if (string.IsNullOrEmpty(other) || !other.StartsWith("%YAML", StringComparison.Ordinal) || string.IsNullOrEmpty(ours) ||
                !ours.StartsWith("%YAML", StringComparison.Ordinal))
                return other;

            var mine = Read(ours);
            var theirs = Read(other);
            Recognise(mine);
            Recognise(theirs);

            var renamed = new Dictionary<long, long>();
            foreach (var pair in theirs.KeyOf)
            {
                long ourId;
                if (mine.IdOfKey.TryGetValue(pair.Value, out ourId) && ourId != pair.Key)
                    renamed[pair.Key] = ourId;
            }

            // Bits of a placed prefab we didn't line up: Unity works their ID out from the placement's ID.
            foreach (var doc in theirs.Docs.Where(d => d.Stripped && !renamed.ContainsKey(d.Id)))
            {
                long instance = Ref(doc.Text, "m_PrefabInstance");
                long newInstance;
                string guid;
                long source = SourceFile(doc.Text, out guid);
                if (!renamed.TryGetValue(instance, out newInstance) || ((instance ^ source) & Mask) != doc.Id)
                    continue;
                renamed[doc.Id] = (newInstance ^ source) & Mask;
            }

            // Their own objects whose ID is taken (by one of ours, or by what something of theirs now becomes).
            var taken = new HashSet<long>(mine.ById.Keys);
            foreach (var target in renamed.Values)
                taken.Add(target);
            var random = new Random();
            foreach (var doc in theirs.Docs)
            {
                // Only objects we don't have at all: anything we both have keeps (or already has) our ID, and
                // objects that couldn't be told apart are left alone rather than risk a copy.
                string key;
                if (renamed.ContainsKey(doc.Id) || !taken.Contains(doc.Id) || doc.Id < 100 ||
                    !theirs.KeyOf.TryGetValue(doc.Id, out key) || mine.IdOfKey.ContainsKey(key))
                    continue;
                long fresh;
                do
                    fresh = (long)(random.NextDouble() * 9e17) + 1000000000L;
                while (taken.Contains(fresh) || theirs.ById.ContainsKey(fresh));
                taken.Add(fresh);
                renamed[doc.Id] = fresh;
            }
            if (renamed.Count == 0)
                return other;

            string result = HeaderLine.Replace(other, m =>
            {
                long id = long.Parse(m.Groups[2].Value);
                long to;
                return renamed.TryGetValue(id, out to) ? "--- !u!" + m.Groups[1].Value + " &" + to : m.Value;
            });
            return LocalRef.Replace(result, m =>
            {
                long id = long.Parse(m.Groups[1].Value);
                long to;
                return renamed.TryGetValue(id, out to) ? "{fileID: " + to + "}" : m.Value;
            });
        }

        internal static byte[] AlignTo(byte[] other, string ours)
        {
            try
            {
                string text = Encoding.UTF8.GetString(other);
                string aligned = AlignTo(text, ours);
                return ReferenceEquals(aligned, text) ? other : Encoding.UTF8.GetBytes(aligned);
            }
            catch (Exception)
            {
                return other;
            }
        }
    }
}
#endif
