OverflowDetectionProblem

using System.Collections;
using NUnit.Framework;
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
using UnityEngine.TestTools;

namespace BurstHexasphere.Tests
{
    public class HashMapCorruption
    {
        [UnityTest]
        public IEnumerator Test()
        {
            //int numDivisions = 400; <= crashes on allocator overflow
            int numDivisions = 512; // doesn't crash, but memory is corrupted

            var originalPoints = GenerateOriginalPoints();
            var originalTriangles = GenerateOriginalTriangles(originalPoints, Allocator.TempJob);

            var trisPerJob = CalculateTrianglesCount(numDivisions);
            var trisN = trisPerJob * originalTriangles.Length;
            var pointsN = trisN / 2 + 2;

            var pointsHashMap = new NativeHashMap<float3, float3>(pointsN + 12, Allocator.TempJob);
            var tris = new NativeArray<Triangle>(trisN, Allocator.TempJob);

            Debug.Log($"Allocating NativeHashSet<float3> capacity = {pointsN + 12}");
            Debug.Log($"Allocating NativeArray<Triangle> capacity = {trisN + 12} x sizeof(Triangle) = 316");

            foreach (var pt in originalPoints)
                pointsHashMap.TryAdd(pt, pt);

            var tessellationJob = new TessellationJob
            {
                numDivisions = numDivisions,                  // read only
                trisPerThread = trisPerJob,                   // read only
                originalTriangles = originalTriangles,        // read only
                allPoints = pointsHashMap.AsParallelWriter(), // write
                tris = tris                                   // write
            };

            var handleTessellationJob = tessellationJob.Schedule(originalTriangles.Length, 1);
            originalTriangles.Dispose(handleTessellationJob);

            var pointToTriangle = new NativeHashMap<float3, TriangleSix>(pointsN * 6, Allocator.TempJob);
            Debug.Log($"Allocating NativeHashMap<float3, TriangleSix> capacity = {pointsN * 6}");

            var pointToTriangleJob = new CreatePointToTriangleJob
            {
                tris = tris,                                  // read only
                pointMap = pointToTriangle // write
            };

            var handlePointToTriangleJob = pointToTriangleJob.Schedule(handleTessellationJob);
            tris.Dispose(handlePointToTriangleJob);
            pointToTriangle.Dispose(handlePointToTriangleJob);

            yield return null;

            handlePointToTriangleJob.Complete();
            pointsHashMap.Dispose();
        }

        internal static float3[] GenerateOriginalPoints()
        {
            const float PHI = 1.61803399f;

            return new[]
            {
                new float3(1, PHI, 0),
                new float3(-1, PHI, 0),
                new float3(1, -PHI, 0),
                new float3(-1, -PHI, 0),
                new float3(0, 1, PHI),
                new float3(0, -1, PHI),
                new float3(0, 1, -PHI),
                new float3(0, -1, -PHI),
                new float3(PHI, 0, 1),
                new float3(-PHI, 0, 1),
                new float3(PHI, 0, -1),
                new float3(-PHI, 0, -1)
            };
        }

        internal static NativeArray<Triangle> GenerateOriginalTriangles(float3[] originalPoints, Allocator allocator)
        {
            return new NativeArray<Triangle>(new[]
            {
                new Triangle(originalPoints[0], originalPoints[1], originalPoints[4]),
                new Triangle(originalPoints[1], originalPoints[9], originalPoints[4]),
                new Triangle(originalPoints[4], originalPoints[9], originalPoints[5]),
                new Triangle(originalPoints[5], originalPoints[9], originalPoints[3]),
                new Triangle(originalPoints[2], originalPoints[3], originalPoints[7]),
                new Triangle(originalPoints[3], originalPoints[2], originalPoints[5]),
                new Triangle(originalPoints[7], originalPoints[10], originalPoints[2]),
                new Triangle(originalPoints[0], originalPoints[8], originalPoints[10]),
                new Triangle(originalPoints[0], originalPoints[4], originalPoints[8]),
                new Triangle(originalPoints[8], originalPoints[2], originalPoints[10]),
                new Triangle(originalPoints[8], originalPoints[4], originalPoints[5]),
                new Triangle(originalPoints[8], originalPoints[5], originalPoints[2]),
                new Triangle(originalPoints[1], originalPoints[0], originalPoints[6]),
                new Triangle(originalPoints[11], originalPoints[1], originalPoints[6]),
                new Triangle(originalPoints[3], originalPoints[9], originalPoints[11]),
                new Triangle(originalPoints[6], originalPoints[10], originalPoints[7]),
                new Triangle(originalPoints[3], originalPoints[11], originalPoints[7]),
                new Triangle(originalPoints[11], originalPoints[6], originalPoints[7]),
                new Triangle(originalPoints[6], originalPoints[0], originalPoints[10]),
                new Triangle(originalPoints[9], originalPoints[1], originalPoints[11])
            }, allocator);
        }

        internal static int CalculateTrianglesCount(int numDiv)
        {
            var trisN = 0;
            for (var i = 1; i <= numDiv; i++)
            {
                ++trisN;
                for (var j = 1; j < i; j++)
                    trisN += 2;
            }
            return trisN;
        }
    }


    internal struct CreatePointToTriangleJob : IJob //ParallelFor
    {
        public NativeHashMap<float3, TriangleSix> pointMap;

        [Unity.Collections.ReadOnly]
        public NativeArray<Triangle> tris;

        public void Execute()
        {
            for (int i = 0; i < tris.Length; i++)
            {
                var triangle = tris[i];

                var r1 = pointMap.TryGetValue(triangle.a, out var t1);
                var r2 = pointMap.TryGetValue(triangle.b, out var t2);
                var r3 = pointMap.TryGetValue(triangle.c, out var t3);

                if (t1.n >= 6 || t2.n >= 6 || t3.n >= 6)
                {
                    unsafe
                    {
                        Debug.Log($"Memory corruption detected. TriangleSix's size = {sizeof(TriangleSix)} n that can be in [0..6] is wrong in at least one of these: t1 = {t1.n} t2 = {t2.n} t3 = {t3.n}");
                    }
                }

                t1.Add(triangle);
                t2.Add(triangle);
                t3.Add(triangle);

                pointMap[triangle.a] = t1;
                pointMap[triangle.b] = t2;
                pointMap[triangle.c] = t3;
            }
        }
    }

    [BurstCompile]
    internal struct TessellationJob : IJobParallelFor
    {
        public int numDivisions;
        public int trisPerThread;

        [ReadOnly]
        public NativeArray<Triangle> originalTriangles;

        [NativeDisableParallelForRestriction]
        public NativeArray<Triangle> tris;

        public NativeHashMap<float3, float3>.ParallelWriter allPoints;

        private unsafe void Subdivide(float3* segments, ref int n , float3 thiz, float3 point, int count)
        {
            segments[0] = thiz;
            n = 1;

            double3 delta = point - thiz;
            double3 thizd = thiz;

            var doubleCount = (double)count;
            for (var i = 1; i < count; i++)
            {
                segments[n++] = (float3)(thizd + delta * i / doubleCount);
            }

            segments[n++] = point;
        }

        public void Execute()
        {
            for (int i = 0; i < originalTriangles.Length; ++i)
                Execute(i);
        }

        public unsafe void Execute(int index)
        {
            var trisI = 0;
            var point0 = originalTriangles[index].a;

            var left = stackalloc float3[numDivisions + 1];
            var leftN = 0;
            var right = stackalloc float3[numDivisions + 1];
            var rightN = 0;
            var bottom = stackalloc float3[numDivisions + 1];
            bottom[0] = point0;
            var bottomN = 1;

            var prev = stackalloc float3[numDivisions + 1];

            Subdivide(left, ref leftN, point0, originalTriangles[index].b, numDivisions);
            Subdivide(right, ref rightN, point0, originalTriangles[index].c, numDivisions);

            for (var i = 0; i < leftN; i++)
                allPoints.TryAdd(left[i], left[i]);

            for (var i = 0; i < rightN; i++)
                allPoints.TryAdd(right[i], right[i]);

            var startTrisIndex = index * trisPerThread;
            for (var i = 1; i <= numDivisions; i++)
            {
                for (var k = 0; k < bottomN; k++)
                    prev[k] = bottom[k];

                Subdivide(bottom, ref bottomN, left[i], right [i], i);

                for (var j = 0; j < bottomN; j++)
                    allPoints.TryAdd(bottom[j], bottom[j]);

                tris[startTrisIndex + trisI] = new Triangle(prev [0], bottom [0], bottom [1]);
                trisI++;

                for (var j = 1; j < i; j++)
                {
                    tris[startTrisIndex + trisI] = new Triangle(prev [j], bottom [j], bottom [j + 1]);
                    trisI++;

                    tris[startTrisIndex + trisI] = new Triangle(prev [j - 1], prev [j], bottom [j]);
                    trisI++;
                }
            }
        }
    }

    public struct TriangleSix
    {
        public int n;

        Triangle a;
        Triangle b;
        Triangle c;
        Triangle d;
        Triangle e;
        Triangle f;

        public Triangle this[int indx]
        {
            get
            {
                switch (indx)
                {
                    case 0: return a;
                    case 1: return b;
                    case 2: return c;
                    case 3: return d;
                    case 4: return e;
                    case 5: return f;
                }

                return default;
            }
            set
            {
                switch (indx)
                {
                    case 0: a = value; return;
                    case 1: b = value; return;
                    case 2: c = value; return;
                    case 3: d = value; return;
                    case 4: e = value; return;
                    case 5: f = value; return;
                }
            }
        }

        public void Add(Triangle triangle)
        {
            Assert.IsTrue(n < 6);
            this[n++] = triangle;
        }
    }

    public struct Triangle
    {
        public readonly float3 a;
        public readonly float3 b;
        public readonly float3 c;

        public readonly float3 center;

        public bool wasAddedToSorted;

        public Triangle(float3 p1, float3 p2, float3 p3)
        {
            a = p1;
            b = p2;
            c = p3;

            center = (a + b + c) / 3.0f;

            wasAddedToSorted = false;
        }
    }
}