//                           _       _
// __      _____  __ ___   ___  __ _| |_ ___
// \ \ /\ / / _ \/ _` \ \ / / |/ _` | __/ _ \
//  \ V  V /  __/ (_| |\ V /| | (_| | ||  __/
//   \_/\_/ \___|\__,_| \_/ |_|\__,_|\__\___|
//
//  Copyright © 2016 - 2024 Weaviate B.V. All rights reserved.
//
//  CONTACT: hello@weaviate.io
//

package hnsw

import (
	"context"
	"fmt"
	"math/rand"
	"os"
	"sort"
	"sync"
	"testing"
	"time"

	"github.com/sirupsen/logrus"
	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
	"github.com/weaviate/weaviate/adapters/repos/db/helpers"
	"github.com/weaviate/weaviate/adapters/repos/db/lsmkv"
	"github.com/weaviate/weaviate/adapters/repos/db/vector/common"
	"github.com/weaviate/weaviate/adapters/repos/db/vector/hnsw/distancer"
	"github.com/weaviate/weaviate/adapters/repos/db/vector/testinghelpers"
	"github.com/weaviate/weaviate/entities/cyclemanager"
	"github.com/weaviate/weaviate/entities/storobj"
	ent "github.com/weaviate/weaviate/entities/vectorindex/hnsw"
)

func TempVectorForIDThunk(vectors [][]float32) func(context.Context, uint64, *common.VectorSlice) ([]float32, error) {
	return func(ctx context.Context, id uint64, container *common.VectorSlice) ([]float32, error) {
		copy(container.Slice, vectors[int(id)])
		return vectors[int(id)], nil
	}
}

func TestDelete_WithoutCleaningUpTombstones(t *testing.T) {
	vectors := vectorsForDeleteTest()
	ctx := context.Background()
	var vectorIndex *hnsw

	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())
	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
		}, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
	})

	var control []uint64

	t.Run("vectors are cached correctly", func(t *testing.T) {
		assert.Equal(t, len(vectors), int(vectorIndex.cache.CountVectors()))
	})

	t.Run("doing a control search before delete with the respective allow list", func(t *testing.T) {
		allowList := helpers.NewAllowList()
		for i := range vectors {
			if i%2 == 0 {
				continue
			}

			allowList.Insert(uint64(i))
		}

		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, allowList)
		require.Nil(t, err)
		require.True(t, len(res) > 0)
		control = res
	})

	t.Run("deleting every even element", func(t *testing.T) {
		for i := range vectors {
			if i%2 != 0 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}
	})

	t.Run("start a search that should only contain the remaining elements", func(t *testing.T) {
		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, nil)
		require.Nil(t, err)
		require.True(t, len(res) > 0)

		for _, elem := range res {
			if elem%2 == 0 {
				t.Errorf("search result contained an even element: %d", elem)
			}
		}

		assert.Equal(t, control, res)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})

	t.Run("vector cache holds no vectors", func(t *testing.T) {
		assert.Equal(t, 0, int(vectorIndex.cache.CountVectors()))
	})
}

func TestDelete_WithCleaningUpTombstonesOnce(t *testing.T) {
	// there is a single bulk clean event after all the deletes
	vectors := vectorsForDeleteTest()
	ctx := context.Background()
	var vectorIndex *hnsw

	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
		}, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
	})

	var control []uint64
	var bfControl []uint64

	t.Run("doing a control search before delete with the respective allow list", func(t *testing.T) {
		allowList := helpers.NewAllowList()
		for i := range vectors {
			if i%2 == 0 {
				continue
			}

			allowList.Insert(uint64(i))
		}

		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, allowList)
		require.Nil(t, err)
		require.True(t, len(res) > 0)
		require.Len(t, res, 20)
		control = res
	})

	t.Run("brute force control", func(t *testing.T) {
		bf := bruteForceCosine(vectors, []float32{0.1, 0.1, 0.1}, 100)
		bfControl = make([]uint64, len(bf))
		i := 0
		for _, elem := range bf {
			if elem%2 == 0 {
				continue
			}

			bfControl[i] = elem
			i++
		}

		if i > 20 {
			i = 20
		}

		bfControl = bfControl[:i]
		assert.Equal(t, bfControl, control, "control should match bf control")
	})

	fmt.Printf("entrypoint before %d\n", vectorIndex.entryPointID)
	t.Run("deleting every even element", func(t *testing.T) {
		for i := range vectors {
			if i%2 != 0 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}
	})

	t.Run("running the cleanup", func(t *testing.T) {
		err := vectorIndex.CleanUpTombstonedNodes(neverStop)
		require.Nil(t, err)
	})

	t.Run("start a search that should only contain the remaining elements", func(t *testing.T) {
		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, nil)
		require.Nil(t, err)
		require.True(t, len(res) > 0)

		for _, elem := range res {
			if elem%2 == 0 {
				t.Errorf("search result contained an even element: %d", elem)
			}
		}

		assert.Equal(t, control, res)
	})

	t.Run("verify the graph no longer has any tombstones", func(t *testing.T) {
		assert.Len(t, vectorIndex.tombstones, 0)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}

func TestDelete_WithCleaningUpTombstonesTwiceConcurrently(t *testing.T) {
	// there is a single bulk clean event after all the deletes
	vectors := vectorsForDeleteTest()
	ctx := context.Background()
	var vectorIndex *hnsw

	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
		}, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
	})

	t.Run("deleting every even element", func(t *testing.T) {
		for i := range vectors {
			if i%2 != 0 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}
	})

	t.Run("running two cleanups concurrently", func(t *testing.T) {
		var wg sync.WaitGroup
		results := make(chan error, 2)

		for i := 0; i < 2; i++ {
			wg.Add(1)
			go func() {
				defer wg.Done()
				err := vectorIndex.CleanUpTombstonedNodes(neverStop)
				results <- err
			}()
		}

		wg.Wait()
		close(results)

		var errors []error
		for err := range results {
			errors = append(errors, err)
		}

		require.Len(t, errors, 2, "Expected exactly two results")

		successCount := 0
		alreadyRunningCount := 0
		for _, err := range errors {
			if err == nil {
				successCount++
			} else if err.Error() == "tombstone cleanup already running" {
				alreadyRunningCount++
			} else {
				t.Errorf("Unexpected error: %v", err)
			}
		}

		// There is a possibility the first cleanup completes before the second one starts
		assert.GreaterOrEqual(t, successCount, 1, "Expected at least one successful cleanup")
		assert.LessOrEqual(t, alreadyRunningCount, 1, "Expected at most one 'already running' error")
		stats, err := vectorIndex.Stats()
		require.Nil(t, err)
		hnswStats, ok := stats.(*HnswStats)
		require.True(t, ok)
		assert.Equal(t, 0, hnswStats.NumTombstones, "Expected no tombstones after cleanup")
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}

func TestDelete_WithConcurrentEntrypointDeletionAndTombstoneCleanup(t *testing.T) {
	var vectors [][]float32
	for i := 0; i < 100; i++ {
		vectors = append(vectors, []float32{rand.Float32(), rand.Float32(), rand.Float32()})
	}
	var vectorIndex *hnsw
	store := testinghelpers.NewDummyStore(t)
	ctx := context.Background()
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, ent.UserConfig{
			MaxConnections:        30,
			EFConstruction:        128,
			VectorCacheMaxObjects: 100000,
		}, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index
		vectorIndex.logger = logrus.New()

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
	})

	t.Run("concurrent entrypoint deletion and tombstone cleanup", func(t *testing.T) {
		var wg sync.WaitGroup
		wg.Add(2)

		go func() {
			defer wg.Done()
			err := vectorIndex.CleanUpTombstonedNodes(neverStop)
			require.Nil(t, err)
		}()

		go func() {
			defer wg.Done()
			for i := range vectors {
				err := vectorIndex.Delete(uint64(i))
				require.Nil(t, err)
			}
		}()

		wg.Wait()
	})

	t.Run("inserting more vectors (with largers ids)", func(t *testing.T) {
		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(len(vectors)+i), vec)
			require.Nil(t, err)
		}
	})

	t.Run("concurrent entrypoint deletion and tombstone cleanup", func(t *testing.T) {
		var wg sync.WaitGroup
		wg.Add(2)

		go func() {
			defer wg.Done()
			err := vectorIndex.CleanUpTombstonedNodes(neverStop)
			require.Nil(t, err)
		}()

		go func() {
			defer wg.Done()
			for i := range vectors {
				err := vectorIndex.Delete(uint64(len(vectors) + i))
				require.Nil(t, err)
			}
		}()

		wg.Wait()
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}

func TestDelete_WithCleaningUpTombstonesInBetween(t *testing.T) {
	// there is a single bulk clean event after all the deletes
	vectors := vectorsForDeleteTest()
	var vectorIndex *hnsw
	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())
	ctx := context.Background()

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
		}, cyclemanager.NewCallbackGroupNoop(), store)
		// makes sure index is build only with level 0. To be removed after fixing WEAVIATE-179
		index.randFunc = func() float64 { return 0.1 }

		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
	})

	var control []uint64

	t.Run("doing a control search before delete with the respective allow list", func(t *testing.T) {
		allowList := helpers.NewAllowList()
		for i := range vectors {
			if i%2 == 0 {
				continue
			}

			allowList.Insert(uint64(i))
		}

		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, allowList)
		require.Nil(t, err)
		require.True(t, len(res) > 0)

		control = res
	})

	t.Run("deleting every even element", func(t *testing.T) {
		for i := range vectors {
			if i%10 == 0 {
				// occasionally run clean up
				err := vectorIndex.CleanUpTombstonedNodes(neverStop)
				require.Nil(t, err)
			}

			if i%2 != 0 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}

		// finally run one final cleanup
		err := vectorIndex.CleanUpTombstonedNodes(neverStop)
		require.Nil(t, err)
	})

	t.Run("start a search that should only contain the remaining elements", func(t *testing.T) {
		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, nil)
		require.Nil(t, err)
		require.True(t, len(res) > 0)

		for _, elem := range res {
			if elem%2 == 0 {
				t.Errorf("search result contained an even element: %d", elem)
			}
		}

		assert.Equal(t, control, res)
	})

	t.Run("verify the graph no longer has any tombstones", func(t *testing.T) {
		assert.Len(t, vectorIndex.tombstones, 0)
	})

	t.Run("delete the remaining elements", func(t *testing.T) {
		for i := range vectors {
			if i%2 == 0 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}

		err := vectorIndex.CleanUpTombstonedNodes(neverStop)
		require.Nil(t, err)
	})

	t.Run("try to insert again and search", func(t *testing.T) {
		for i := 0; i < 5; i++ {
			err := vectorIndex.Add(ctx, uint64(i), vectors[i])
			require.Nil(t, err)
		}

		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, nil)
		require.Nil(t, err)
		assert.ElementsMatch(t, []uint64{0, 1, 2, 3, 4}, res)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})

	store.Shutdown(context.Background())
}

func createIndexImportAllVectorsAndDeleteEven(t *testing.T, vectors [][]float32, store *lsmkv.Store) (index *hnsw, remainingResult []uint64) {
	ctx := context.Background()
	index, err := New(Config{
		RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
		ID:                    "delete-test",
		MakeCommitLoggerThunk: MakeNoopCommitLogger,
		DistanceProvider:      distancer.NewCosineDistanceProvider(),
		VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
			return vectors[int(id)], nil
		},
		TempVectorForIDThunk: TempVectorForIDThunk(vectors),
	}, ent.UserConfig{
		MaxConnections: 30,
		EFConstruction: 128,

		// The actual size does not matter for this test, but if it defaults to
		// zero it will constantly think it's full and needs to be deleted - even
		// after just being deleted, so make sure to use a positive number here.
		VectorCacheMaxObjects: 100000,
	}, cyclemanager.NewCallbackGroupNoop(), store)
	require.Nil(t, err)

	// makes sure index is build only with level 0. To be removed after fixing WEAVIATE-179
	index.randFunc = func() float64 { return 0.1 }

	// to speed up test execution, size of nodes array is decreased
	// from default 25k to little over number of vectors
	index.nodes = make([]*vertex, int(1.2*float64(len(vectors))))

	for i, vec := range vectors {
		err := index.Add(ctx, uint64(i), vec)
		require.Nil(t, err)
	}

	for i := range vectors {
		if i%2 != 0 {
			continue
		}
		err := index.Delete(uint64(i))
		require.Nil(t, err)
	}

	res, _, err := index.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, len(vectors), nil)
	require.Nil(t, err)
	require.True(t, len(res) > 0)

	for _, elem := range res {
		if elem%2 == 0 {
			t.Errorf("search result contained an even element: %d", elem)
		}
	}

	return index, res
}

func genStopAtFunc(i int) func() bool {
	counter := 0
	mutex := &sync.Mutex{}
	return func() bool {
		mutex.Lock()
		defer mutex.Unlock()
		if counter < i {
			counter++
			return false
		}

		return true
	}
}

func TestDelete_WithCleaningUpTombstonesStopped(t *testing.T) {
	ctx := context.Background()
	vectors := vectorsForDeleteTest()
	var index *hnsw
	var possibleStopsCount int
	// due to not yet resolved bug (https://semi-technology.atlassian.net/browse/WEAVIATE-179)
	// db can return less vectors than are actually stored after tombstones cleanup
	// controlRemainingResult contains all odd vectors (before cleanup was performed)
	// controlRemainingResultAfterCleanup contains most of odd vectors (after cleanup was performed)
	//
	// this test verifies if partial cleanup will not change search output, therefore depending on
	// where cleanup method was stopped, subset of controlRemainingResult is expected, though all
	// vectors from controlRemainingResultAfterCleanup should be returned
	// TODO to be simplified after fixing WEAVIATE-179, all results should be the same
	var controlRemainingResult []uint64
	var controlRemainingResultAfterCleanup []uint64
	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("create control index", func(t *testing.T) {
		index, controlRemainingResult = createIndexImportAllVectorsAndDeleteEven(t, vectors, store)
	})

	t.Run("count all cleanup tombstones stops", func(t *testing.T) {
		counter := 0
		mutex := &sync.Mutex{}
		countingStopFunc := func() bool {
			mutex.Lock()
			counter++
			mutex.Unlock()
			return false
		}

		err := index.CleanUpTombstonedNodes(countingStopFunc)
		require.Nil(t, err)

		possibleStopsCount = counter
	})

	t.Run("search remaining elements after cleanup", func(t *testing.T) {
		res, _, err := index.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, len(vectors), nil)
		require.Nil(t, err)
		require.True(t, len(res) > 0)

		for _, elem := range res {
			if elem%2 == 0 {
				t.Errorf("search result contained an even element: %d", elem)
			}
		}
		controlRemainingResultAfterCleanup = res
	})

	t.Run("destroy the control index", func(t *testing.T) {
		require.Nil(t, index.Drop(context.Background()))
	})

	for i := 0; i < possibleStopsCount; i++ {
		index, _ = createIndexImportAllVectorsAndDeleteEven(t, vectors, store)

		t.Run("stop cleanup at place", func(t *testing.T) {
			require.Nil(t, index.CleanUpTombstonedNodes(genStopAtFunc(i)))
		})

		t.Run("search remaining elements after partial cleanup", func(t *testing.T) {
			res, _, err := index.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, len(vectors), nil)
			require.Nil(t, err)
			require.Subset(t, controlRemainingResult, res)
			require.Subset(t, res, controlRemainingResultAfterCleanup)
		})

		t.Run("run complete cleanup", func(t *testing.T) {
			require.Nil(t, index.CleanUpTombstonedNodes(neverStop))
		})

		t.Run("search remaining elements after complete cleanup", func(t *testing.T) {
			res, _, err := index.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, len(vectors), nil)
			require.Nil(t, err)
			require.Subset(t, controlRemainingResult, res)
			require.Subset(t, res, controlRemainingResultAfterCleanup)
		})

		t.Run("destroy the index", func(t *testing.T) {
			require.Nil(t, index.Drop(context.Background()))
		})
	}
}

func TestDelete_WithCleaningUpTombstonesStoppedShouldNotRemoveTombstoneMarks(t *testing.T) {
	ctx := context.Background()
	vectors := vectorsForDeleteTest()
	var index *hnsw
	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("create control index", func(t *testing.T) {
		index, _ = createIndexImportAllVectorsAndDeleteEven(t, vectors, store)
	})

	t.Run("count all cleanup tombstones stops", func(t *testing.T) {
		counter := 0
		mutex := &sync.Mutex{}
		countingStopFunc := func() bool {
			mutex.Lock()
			counter++
			counterCpy := counter
			mutex.Unlock()
			return counterCpy > 30 && counterCpy < 40
		}

		err := index.CleanUpTombstonedNodes(countingStopFunc)
		require.Nil(t, err)
	})

	time.Sleep(1000 * time.Millisecond)

	t.Run("even ids are not coming back and tombstones are not removed completely", func(t *testing.T) {
		ids, _, _ := index.SearchByVector(ctx, vectors[0], len(vectors), nil)
		for _, id := range ids {
			assert.Equal(t, 1, int(id%2))
		}
		assert.True(t, len(index.tombstones) > 0)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, index.Drop(context.Background()))
	})
}

func TestDelete_InCompressedIndex_WithCleaningUpTombstonesOnce(t *testing.T) {
	ctx := context.Background()
	defaultUC := ent.NewDefaultUserConfig()
	var (
		vectorIndex *hnsw
		// there is a single bulk clean event after all the deletes
		vectors    = vectorsForDeleteTest()
		rootPath   = t.TempDir()
		userConfig = ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
			PQ: ent.PQConfig{
				Enabled: true,
				Encoder: ent.PQEncoder{
					Type:         ent.PQEncoderTypeTile,
					Distribution: ent.PQEncoderDistributionNormal,
				},
			},
			BQ: defaultUC.BQ,
			SQ: defaultUC.SQ,
		}
	)
	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              rootPath,
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				if int(id) >= len(vectors) {
					return nil, storobj.NewErrNotFoundf(id, "out of range")
				}
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, userConfig, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
		cfg := ent.PQConfig{
			Enabled: true,
			Encoder: ent.PQEncoder{
				Type:         ent.PQEncoderTypeTile,
				Distribution: ent.PQEncoderDistributionLogNormal,
			},
			BitCompression: false,
			Segments:       3,
			Centroids:      256,
			TrainingLimit:  100000,
		}
		userConfig.PQ = cfg
		index.compress(userConfig)
	})

	var control []uint64
	var bfControl []uint64

	t.Run("doing a control search before delete with the respective allow list", func(t *testing.T) {
		allowList := helpers.NewAllowList()
		for i := range vectors {
			if i%2 == 0 {
				continue
			}

			allowList.Insert(uint64(i))
		}

		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, allowList)
		require.Nil(t, err)
		require.True(t, len(res) > 0)
		require.Len(t, res, 20)
		control = res
	})

	t.Run("brute force control", func(t *testing.T) {
		bf := bruteForceCosine(vectors, []float32{0.1, 0.1, 0.1}, 100)
		bfControl = make([]uint64, len(bf))
		i := 0
		for _, elem := range bf {
			if elem%2 == 0 {
				continue
			}

			bfControl[i] = elem
			i++
		}

		if i > 20 {
			i = 20
		}

		bfControl = bfControl[:i]
		recall := float32(testinghelpers.MatchesInLists(bfControl, control)) / float32(len(bfControl))
		fmt.Println(recall)
		assert.True(t, recall > 0.6, "control should match bf control")
	})

	fmt.Printf("entrypoint before %d\n", vectorIndex.entryPointID)
	t.Run("deleting every even element", func(t *testing.T) {
		for i := range vectors {
			if i%2 != 0 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}
	})

	t.Run("running the cleanup", func(t *testing.T) {
		err := vectorIndex.CleanUpTombstonedNodes(neverStop)
		require.Nil(t, err)
	})

	t.Run("start a search that should only contain the remaining elements", func(t *testing.T) {
		res, _, err := vectorIndex.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, nil)
		require.Nil(t, err)
		require.True(t, len(res) > 0)

		for _, elem := range res {
			if elem%2 == 0 {
				t.Errorf("search result contained an even element: %d", elem)
			}
		}

		recall := float32(testinghelpers.MatchesInLists(res, control)) / float32(len(control))
		assert.True(t, recall > 0.6)
	})

	t.Run("verify the graph no longer has any tombstones", func(t *testing.T) {
		assert.Len(t, vectorIndex.tombstones, 0)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}

func TestDelete_ResetLockDoesNotLockForever(t *testing.T) {
	ctx := context.Background()
	var (
		vectorIndex *hnsw
		// there is a single bulk clean event after all the deletes
		vectors    = vectorsForDeleteTest()
		rootPath   = t.TempDir()
		userConfig = ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
			PQ: ent.PQConfig{
				Enabled: false,
				Encoder: ent.PQEncoder{
					Type:         ent.PQEncoderTypeTile,
					Distribution: ent.PQEncoderDistributionNormal,
				},
			},
		}
	)
	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              rootPath,
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				if int(id) >= len(vectors) {
					return nil, storobj.NewErrNotFoundf(id, "out of range")
				}
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, userConfig, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
	})

	fmt.Printf("entrypoint before %d\n", vectorIndex.entryPointID)
	deletedIds := make([]uint64, 0, len(vectors)/2)
	t.Run("deleting every even element", func(t *testing.T) {
		for i := range vectors {
			if i%2 != 0 {
				continue
			}

			deletedIds = append(deletedIds, uint64(i))
			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}
	})

	t.Run("running the cleanup and an delete, the delete should not take forever", func(t *testing.T) {
		var wg sync.WaitGroup
		wg.Add(2)

		go func() {
			defer wg.Done()
			allowList := helpers.NewAllowList(deletedIds...)
			ok, err := vectorIndex.reassignNeighborsOf(ctx, allowList, slowNeverStop)
			require.Nil(t, err)
			require.True(t, ok)
		}()
		elapsed := time.Duration(0)
		go func() {
			defer wg.Done()
			time.Sleep(time.Millisecond * 100)
			starting := time.Now()
			err := vectorIndex.Delete(vectorIndex.entryPointID)
			elapsed = time.Since(starting)
			require.Nil(t, err)
		}()
		wg.Wait()
		fmt.Printf("ms elapsed: %d\n", elapsed.Milliseconds())
		assert.LessOrEqual(t, elapsed.Milliseconds(), int64(180))
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}

func TestDelete_InCompressedIndex_WithCleaningUpTombstonesOnce_DoesNotCrash(t *testing.T) {
	ctx := context.Background()
	defaultUC := ent.NewDefaultUserConfig()
	var (
		vectorIndex *hnsw
		// there is a single bulk clean event after all the deletes
		vectors    = vectorsForDeleteTest()
		rootPath   = t.TempDir()
		userConfig = ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
			PQ: ent.PQConfig{
				Enabled: true,
				Encoder: ent.PQEncoder{
					Type:         ent.PQEncoderTypeTile,
					Distribution: ent.PQEncoderDistributionNormal,
				},
			},
			BQ: defaultUC.BQ,
			SQ: defaultUC.SQ,
		}
	)

	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              rootPath,
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				return vectors[int(id%uint64(len(vectors)))], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, userConfig, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
		cfg := ent.PQConfig{
			Enabled: true,
			Encoder: ent.PQEncoder{
				Type:         ent.PQEncoderTypeTile,
				Distribution: ent.PQEncoderDistributionLogNormal,
			},
			BitCompression: false,
			Segments:       3,
			Centroids:      256,
		}
		userConfig.PQ = cfg
		index.compress(userConfig)
		for i := len(vectors); i < 1000; i++ {
			err := vectorIndex.Add(ctx, uint64(i), vectors[i%len(vectors)])
			require.Nil(t, err)
		}
	})

	t.Run("deleting every even element", func(t *testing.T) {
		for i := range vectors {
			if i%2 != 0 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}
	})

	t.Run("running the cleanup", func(t *testing.T) {
		err := vectorIndex.CleanUpTombstonedNodes(neverStop)
		require.Nil(t, err)
	})

	t.Run("verify the graph no longer has any tombstones", func(t *testing.T) {
		assert.Len(t, vectorIndex.tombstones, 0)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}

// we need a certain number of elements so that we can make sure that nodes
// from all layers will eventually be deleted, otherwise our test only tests
// edge cases which aren't very common in real life, but ignore the most common
// deletes
func vectorsForDeleteTest() [][]float32 {
	return [][]float32{
		{0.27335858, 0.42670676, 0.12599982},
		{0.34369454, 0.78510034, 0.78000546},
		{0.2342731, 0.076864816, 0.6405078},
		{0.07597838, 0.7752282, 0.87022865},
		{0.78632426, 0.06902865, 0.7423889},
		{0.3055758, 0.3901508, 0.9399572},
		{0.48687622, 0.26338226, 0.06495104},
		{0.5384028, 0.35410047, 0.8821815},
		{0.25123185, 0.62722564, 0.86443096},
		{0.58484185, 0.13103616, 0.4034975},
		{0.0019696166, 0.46822622, 0.42492124},
		{0.42401955, 0.8278863, 0.5952888},
		{0.15367928, 0.70778894, 0.0070928824},
		{0.95760256, 0.45898128, 0.1541115},
		{0.9125976, 0.9021616, 0.21607016},
		{0.9876307, 0.5243228, 0.37294936},
		{0.8194746, 0.56142205, 0.5130103},
		{0.805065, 0.62250346, 0.63715476},
		{0.9969276, 0.5115748, 0.18916714},
		{0.16419733, 0.15029702, 0.36020836},
		{0.9660323, 0.35887036, 0.6072966},
		{0.72765416, 0.27891788, 0.9094314},
		{0.8626208, 0.3540126, 0.3100354},
		{0.7153876, 0.17094712, 0.7801294},
		{0.23180388, 0.107446484, 0.69542855},
		{0.54731685, 0.8949827, 0.68316746},
		{0.15049729, 0.1293767, 0.0574729},
		{0.89379513, 0.67022973, 0.57360715},
		{0.725353, 0.25326362, 0.44264215},
		{0.2568602, 0.4986094, 0.9759933},
		{0.7300015, 0.70019704, 0.49546525},
		{0.54314494, 0.2004176, 0.63803226},
		{0.6180191, 0.5260845, 0.9373999},
		{0.63356537, 0.81430644, 0.78373694},
		{0.69995105, 0.84198904, 0.17851257},
		{0.5197941, 0.11502675, 0.95129955},
		{0.15791401, 0.07516741, 0.113447875},
		{0.06811827, 0.4450082, 0.98595786},
		{0.7153448, 0.41833848, 0.06332495},
		{0.6704102, 0.28931814, 0.031580303},
		{0.47773632, 0.73334247, 0.6925025},
		{0.7976896, 0.9499536, 0.6394833},
		{0.3074854, 0.14025249, 0.35961738},
		{0.49956197, 0.093575336, 0.790093},
		{0.4641653, 0.21276893, 0.528895},
		{0.1021849, 0.9416305, 0.46738508},
		{0.3790398, 0.50099677, 0.98233247},
		{0.39650732, 0.020929832, 0.53968865},
		{0.77604437, 0.8554197, 0.24056046},
		{0.07174444, 0.28758526, 0.67587185},
		{0.22292718, 0.66624546, 0.6077909},
		{0.22090498, 0.36197436, 0.40415043},
		{0.04838009, 0.120789215, 0.17928012},
		{0.55166364, 0.3400502, 0.43698996},
		{0.7638108, 0.47014108, 0.23208627},
		{0.9239513, 0.8418566, 0.23518613},
		{0.289589, 0.85010827, 0.055741556},
		{0.32436147, 0.18756394, 0.4217864},
		{0.041671168, 0.37824047, 0.66486764},
		{0.5052222, 0.07982704, 0.64345413},
		{0.62675995, 0.20138603, 0.8231867},
		{0.86306876, 0.9698708, 0.11398846},
		{0.68566775, 0.22026269, 0.13525572},
		{0.57706076, 0.32325208, 0.6122228},
		{0.80035216, 0.18560356, 0.6328281},
		{0.87145543, 0.19380389, 0.8863942},
		{0.33777508, 0.6056442, 0.9110077},
		{0.3961719, 0.49714503, 0.14191929},
		{0.5344362, 0.8166916, 0.75880384},
		{0.015749464, 0.63223976, 0.5470922},
		{0.10512444, 0.2212036, 0.24995685},
		{0.10831311, 0.27044898, 0.8668174},
		{0.3272971, 0.6659298, 0.87119603},
		{0.42913893, 0.14528985, 0.69957525},
		{0.33012474, 0.81964344, 0.092787445},
		{0.093618214, 0.90637344, 0.94406706},
		{0.12161567, 0.75131124, 0.40563175},
		{0.9154454, 0.75925833, 0.8406739},
		{0.81649286, 0.9025715, 0.3105051},
		{0.2927649, 0.22649862, 0.9708593},
		{0.30813727, 0.0079439245, 0.39662006},
		{0.94943213, 0.36778906, 0.217876},
		{0.716794, 0.3811725, 0.18448676},
		{0.66879725, 0.29722908, 0.0031202603},
		{0.11104216, 0.13094379, 0.0787222},
		{0.8508966, 0.86416596, 0.15885831},
		{0.2303136, 0.56660503, 0.17114973},
		{0.8632685, 0.4229249, 0.1936724},
		{0.03060897, 0.35226125, 0.8115969},
	}
}

func TestDelete_EntrypointIssues(t *testing.T) {
	ctx := context.Background()
	// This test is motivated by flakyness of other tests. We seemed to have
	// experienced a failure with the following structure
	//
	// Entrypoint: 6
	// Max Level: 1
	// Tombstones map[]

	// Nodes and Connections:
	// Node 0
	// Level 0: Connections: [1 2 3 4 5 6 7 8]
	// Node 1
	// Level 0: Connections: [0 2 3 4 5 6 7 8]
	// Node 2
	// Level 0: Connections: [1 0 3 4 5 6 7 8]
	// Node 3
	// Level 0: Connections: [2 1 0 4 5 6 7 8]
	// Node 4
	// Level 0: Connections: [3 2 1 0 5 6 7 8]
	// Node 5
	// Level 0: Connections: [3 4 2 1 0 6 7 8]
	// Node 6
	// Level 0: Connections: [4 2 1 3 5 0 7 8]
	// Level 1: Connections: [7]
	// Node 7
	// Level 1: Connections: [6]
	// Level 0: Connections: [6 4 3 5 2 1 0 8]
	// Node 8
	// Level 0: Connections: [7 6 4 3 5 2 1 0]
	//
	// This test aims to rebuild this tree exactly (manually) and verifies that
	// deletion of the old entrypoint (element 6), works without issue
	//
	// The underlying test set can be found in vectors_for_test.go

	index, err := New(Config{
		RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
		ID:                    "delete-entrypoint-test",
		MakeCommitLoggerThunk: MakeNoopCommitLogger,
		DistanceProvider:      distancer.NewCosineDistanceProvider(),
		VectorForIDThunk:      testVectorForID,
	}, ent.UserConfig{
		MaxConnections: 30,
		EFConstruction: 128,

		// The actual size does not matter for this test, but if it defaults to
		// zero it will constantly think it's full and needs to be deleted - even
		// after just being deleted, so make sure to use a positive number here.
		VectorCacheMaxObjects: 100000,
	}, cyclemanager.NewCallbackGroupNoop(), testinghelpers.NewDummyStore(t))
	require.Nil(t, err)

	// manually build the index
	index.entryPointID = 6
	index.currentMaximumLayer = 1
	index.nodes = make([]*vertex, 50)
	index.nodes[0] = &vertex{
		id: 0,
		connections: [][]uint64{
			{1, 2, 3, 4, 5, 6, 7, 8},
		},
	}
	index.nodes[1] = &vertex{
		id: 1,
		connections: [][]uint64{
			{0, 2, 3, 4, 5, 6, 7, 8},
		},
	}
	index.nodes[2] = &vertex{
		id: 2,
		connections: [][]uint64{
			{1, 0, 3, 4, 5, 6, 7, 8},
		},
	}
	index.nodes[3] = &vertex{
		id: 3,
		connections: [][]uint64{
			{2, 1, 0, 4, 5, 6, 7, 8},
		},
	}
	index.nodes[4] = &vertex{
		id: 4,
		connections: [][]uint64{
			{3, 2, 1, 0, 5, 6, 7, 8},
		},
	}
	index.nodes[5] = &vertex{
		id: 5,
		connections: [][]uint64{
			{3, 4, 2, 1, 0, 6, 7, 8},
		},
	}
	index.nodes[6] = &vertex{
		id: 6,
		connections: [][]uint64{
			{4, 3, 1, 3, 5, 0, 7, 8},
			{7},
		},
		level: 1,
	}
	index.nodes[7] = &vertex{
		id: 7,
		connections: [][]uint64{
			{6, 4, 3, 5, 2, 1, 0, 8},
			{6},
		},
		level: 1,
	}
	index.nodes[8] = &vertex{
		id: 8,
		connections: [][]uint64{
			8: {7, 6, 4, 3, 5, 2, 1, 0},
		},
	}

	dumpIndex(index, "before delete")

	t.Run("delete some elements and permanently delete tombstoned elements",
		func(t *testing.T) {
			err := index.Delete(6)
			require.Nil(t, err)
			err = index.Delete(8)
			require.Nil(t, err)

			err = index.CleanUpTombstonedNodes(neverStop)
			require.Nil(t, err)
		})

	dumpIndex(index, "after delete")

	expectedResults := []uint64{
		3, 5, 4, // cluster 2
		7,       // cluster 3 with element 6 and 8 deleted
		2, 1, 0, // cluster 1
	}

	t.Run("verify that the results are correct", func(t *testing.T) {
		position := 3
		res, _, err := index.knnSearchByVector(ctx, testVectors[position], 50, 36, nil)
		require.Nil(t, err)
		assert.Equal(t, expectedResults, res)
	})

	// t.Fail()
	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, index.Drop(context.Background()))
	})
}

func TestDelete_MoreEntrypointIssues(t *testing.T) {
	ctx := context.Background()
	vectors := [][]float32{
		{7, 1},
		{8, 2},
		{23, 14},
		{6.5, -1},
	}

	vecForID := func(ctx context.Context, id uint64) ([]float32, error) {
		return vectors[int(id)], nil
	}
	// This test is motivated by flakyness of other tests. We seemed to have
	// experienced a failure with the following structure
	//
	// ID: thing_geoupdatetestclass_single_location
	// Entrypoint: 2
	// Max Level: 1
	// Tombstones map[0:{} 1:{}]
	//
	// Nodes and Connections:
	//   Node 0
	//     Level 0: Connections: [1]
	//   Node 1
	//     Level 0: Connections: [0 2]
	//     Level 1: Connections: [2]
	//   Node 2
	//     Level 1: Connections: [1]
	//     Level 0: Connections: [1]

	index, err := New(Config{
		RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
		ID:                    "more-delete-entrypoint-flakyness-test",
		MakeCommitLoggerThunk: MakeNoopCommitLogger,
		DistanceProvider:      distancer.NewGeoProvider(),
		VectorForIDThunk:      vecForID,
		TempVectorForIDThunk:  TempVectorForIDThunk(vectors),
	}, ent.UserConfig{
		MaxConnections: 30,
		EFConstruction: 128,

		// The actual size does not matter for this test, but if it defaults to
		// zero it will constantly think it's full and needs to be deleted - even
		// after just being deleted, so make sure to use a positive number here.
		VectorCacheMaxObjects: 100000,
	}, cyclemanager.NewCallbackGroupNoop(), testinghelpers.NewDummyStore(t))
	require.Nil(t, err)

	// manually build the index
	index.entryPointID = 2
	index.currentMaximumLayer = 1
	index.tombstones = map[uint64]struct{}{
		0: {},
		1: {},
	}
	index.nodes = make([]*vertex, 50)
	index.nodes[0] = &vertex{
		id: 0,
		connections: [][]uint64{
			0: {1},
		},
	}
	index.nodes[1] = &vertex{
		id: 1,
		connections: [][]uint64{
			0: {0, 2},
			1: {2},
		},
	}
	index.nodes[2] = &vertex{
		id: 2,
		connections: [][]uint64{
			0: {1},
			1: {1},
		},
	}

	dumpIndex(index, "before adding another element")
	t.Run("adding a third element", func(t *testing.T) {
		vec, _ := testVectorForID(context.TODO(), 3)
		index.Add(ctx, 3, vec)
	})

	expectedResults := []uint64{
		3, 2,
	}

	t.Run("verify that the results are correct", func(t *testing.T) {
		position := 3
		res, _, err := index.knnSearchByVector(ctx, testVectors[position], 50, 36, nil)
		require.Nil(t, err)
		assert.Equal(t, expectedResults, res)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, index.Drop(context.Background()))
	})
}

func TestDelete_TombstonedEntrypoint(t *testing.T) {
	ctx := context.Background()
	vecForID := func(ctx context.Context, id uint64) ([]float32, error) {
		// always return same vec  for all elements
		return []float32{0.1, 0.2}, nil
	}
	index, err := New(Config{
		RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
		ID:                    "tombstoned-entrypoint-test",
		MakeCommitLoggerThunk: MakeNoopCommitLogger,
		DistanceProvider:      distancer.NewCosineDistanceProvider(),
		VectorForIDThunk:      vecForID,
		TempVectorForIDThunk:  TempVectorForIDThunk([][]float32{{0.1, 0.2}}),
	}, ent.UserConfig{
		MaxConnections: 30,
		EFConstruction: 128,
		// explicitly turn off, so we only focus on the tombstoned periods
		CleanupIntervalSeconds: 0,

		// The actual size does not matter for this test, but if it defaults to
		// zero it will constantly think it's full and needs to be deleted - even
		// after just being deleted, so make sure to use a positive number here.
		VectorCacheMaxObjects: 100000,
	}, cyclemanager.NewCallbackGroupNoop(), testinghelpers.NewDummyStore(t))
	require.Nil(t, err)

	objVec := []float32{0.1, 0.2}
	searchVec := []float32{0.05, 0.05}

	require.Nil(t, index.Add(ctx, 0, objVec))
	require.Nil(t, index.Delete(0))
	require.Nil(t, index.Add(ctx, 1, objVec))

	res, _, err := index.SearchByVector(ctx, searchVec, 100, nil)
	require.Nil(t, err)
	assert.Equal(t, []uint64{1}, res, "should contain the only result")

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, index.Drop(context.Background()))
	})
}

func TestDelete_Flakyness_gh_1369(t *testing.T) {
	ctx := context.Background()
	// parse a snapshot form a flaky test
	snapshotBefore := []byte(`{"labels":["ran a cleanup cycle"],"id":"delete-test","entrypoint":3,"currentMaximumLayer":3,"tombstones":{},"nodes":[{"id":1,"level":0,"connections":{"0":[11,25,33,3,29,32,5,19,30,7,17,27,21,31,36,34,35,23,15,9,13]}},{"id":3,"level":3,"connections":{"0":[1,29,11,5,25,33,19,32,7,17,30,21,35,31,27,36,23,34,9,15,13],"1":[29,36,13],"2":[29,36],"3":[36]}},{"id":5,"level":0,"connections":{"0":[29,19,7,32,35,21,1,31,3,33,23,25,11,17,36,27,30,9,15,34,13]}},{"id":7,"level":0,"connections":{"0":[32,19,21,31,5,35,23,29,33,36,17,1,9,27,25,30,11,3,15,13,34]}},{"id":9,"level":0,"connections":{"0":[36,23,31,21,15,17,27,7,32,35,30,13,19,33,5,25,29,11,1,34,3]}},{"id":11,"level":0,"connections":{"0":[25,33,1,30,17,3,27,32,34,29,19,7,5,36,15,21,31,23,9,13,35]}},{"id":13,"level":1,"connections":{"0":[15,27,34,36,30,17,9,33,25,31,23,21,11,32,7,1,19,35,5,29,3],"1":[36,29,3]}},{"id":15,"level":0,"connections":{"0":[13,27,36,17,30,9,34,33,31,23,25,21,32,11,7,1,19,35,5,29,3]}},{"id":17,"level":0,"connections":{"0":[27,30,36,33,15,32,25,31,9,11,21,7,23,1,34,13,19,5,29,35,3]}},{"id":19,"level":0,"connections":{"0":[5,7,32,29,35,21,31,23,1,33,17,3,25,36,11,27,9,30,15,34,13]}},{"id":21,"level":0,"connections":{"0":[31,23,7,35,32,19,9,36,5,17,27,33,29,30,15,1,25,11,3,13,34]}},{"id":23,"level":0,"connections":{"0":[31,21,9,35,7,36,32,19,17,5,27,33,15,29,30,25,1,13,11,3,34]}},{"id":25,"level":0,"connections":{"0":[11,33,1,30,17,27,32,3,34,29,7,19,36,5,15,21,31,23,9,13,35]}},{"id":27,"level":0,"connections":{"0":[17,30,36,15,33,25,13,9,34,32,11,31,21,7,23,1,19,5,29,35,3]}},{"id":29,"level":2,"connections":{"0":[5,19,32,7,3,1,33,35,21,25,31,11,23,17,30,36,27,9,15,34,13],"1":[3,36,13],"2":[3,36]}},{"id":30,"level":0,"connections":{"0":[27,17,33,25,15,36,11,34,32,1,13,9,31,7,21,23,19,29,5,3,35]}},{"id":31,"level":0,"connections":{"0":[21,23,7,32,35,9,36,19,17,5,27,33,29,30,15,25,1,11,13,3,34]}},{"id":32,"level":0,"connections":{"0":[7,19,21,31,5,33,29,17,23,1,35,36,25,27,30,11,9,3,15,34,13]}},{"id":33,"level":0,"connections":{"0":[25,11,1,17,30,32,27,7,19,36,29,5,21,31,3,34,15,23,9,35,13]}},{"id":34,"level":0,"connections":{"0":[30,27,15,13,25,17,11,33,36,1,32,9,31,7,21,3,23,19,29,5,35]}},{"id":35,"level":0,"connections":{"0":[21,7,31,23,19,5,32,29,9,36,17,33,1,27,25,30,3,11,15,13,34]}},{"id":36,"level":3,"connections":{"0":[17,9,27,15,31,23,21,30,32,7,33,13,25,19,35,11,34,1,5,29,3],"1":[13,29,3],"2":[29,3],"3":[3]}}]}
`)

	vectors := vectorsForDeleteTest()
	vecForID := func(ctx context.Context, id uint64) ([]float32, error) {
		return vectors[int(id)], nil
	}

	index, err := NewFromJSONDumpMap(snapshotBefore, vecForID)
	require.Nil(t, err)
	index.forbidFlat = true

	var control []uint64
	t.Run("control search before delete with the respective allow list", func(t *testing.T) {
		allowList := helpers.NewAllowList()
		for i := range vectors {
			if i%2 == 0 {
				continue
			}

			allowList.Insert(uint64(i))
		}

		res, _, err := index.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, allowList)
		require.Nil(t, err)
		require.True(t, len(res) > 0)

		control = res
	})

	t.Run("delete the remaining even entries", func(t *testing.T) {
		require.Nil(t, index.Delete(30))
		require.Nil(t, index.Delete(32))
		require.Nil(t, index.Delete(34))
		require.Nil(t, index.Delete(36))
	})

	t.Run("verify against control BEFORE Tombstone Cleanup", func(t *testing.T) {
		res, _, err := index.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, nil)
		require.Nil(t, err)
		require.True(t, len(res) > 0)
		assert.Equal(t, control, res)
	})

	t.Run("clean up tombstoned nodes", func(t *testing.T) {
		require.Nil(t, index.CleanUpTombstonedNodes(neverStop))
	})

	t.Run("verify against control AFTER Tombstone Cleanup", func(t *testing.T) {
		res, _, err := index.SearchByVector(ctx, []float32{0.1, 0.1, 0.1}, 20, nil)
		require.Nil(t, err)
		require.True(t, len(res) > 0)
		assert.Equal(t, control, res)
	})

	t.Run("now delete the entrypoint", func(t *testing.T) {
		require.Nil(t, index.Delete(index.entryPointID))
	})

	t.Run("clean up tombstoned nodes", func(t *testing.T) {
		require.Nil(t, index.CleanUpTombstonedNodes(neverStop))
	})

	t.Run("now delete the entrypoint", func(t *testing.T) {
		// this verifies that our findNewLocalEntrypoint also works when the global
		// entrypoint is affected
		require.Nil(t, index.Delete(index.entryPointID))
	})

	t.Run("clean up tombstoned nodes", func(t *testing.T) {
		require.Nil(t, index.CleanUpTombstonedNodes(neverStop))
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, index.Drop(context.Background()))
	})
}

func bruteForceCosine(vectors [][]float32, query []float32, k int) []uint64 {
	type distanceAndIndex struct {
		distance float32
		index    uint64
	}

	distances := make([]distanceAndIndex, len(vectors))

	d := distancer.NewCosineDistanceProvider().New(distancer.Normalize(query))
	for i, vec := range vectors {
		dist, _ := d.Distance(distancer.Normalize(vec))
		distances[i] = distanceAndIndex{
			index:    uint64(i),
			distance: dist,
		}
	}

	sort.Slice(distances, func(a, b int) bool {
		return distances[a].distance < distances[b].distance
	})

	if len(distances) < k {
		k = len(distances)
	}

	out := make([]uint64, k)
	for i := 0; i < k; i++ {
		out[i] = distances[i].index
	}

	return out
}

func neverStop() bool {
	return false
}

func slowNeverStop() bool {
	time.Sleep(time.Millisecond * 10)
	return false
}

// This test simulates what happens when the EP is removed from the
// VectorForID-serving store
func Test_DeleteEPVecInUnderlyingObjectStore(t *testing.T) {
	ctx := context.Background()
	var vectorIndex *hnsw

	vectors := [][]float32{
		{1, 1},
		{2, 2},
		{3, 3},
	}

	vectorErrors := []error{
		nil,
		nil,
		nil,
	}
	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
			ID:                    "delete-ep-in-underlying-store-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewL2SquaredProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				fmt.Printf("vec for pos=%d is %v\n", id, vectors[int(id)])
				return vectors[int(id)], vectorErrors[int(id)]
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
		}, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}

		fmt.Printf("ep is %d\n", vectorIndex.entryPointID)
	})

	t.Run("simulate ep vec deletion in object store", func(t *testing.T) {
		vectors[0] = nil
		vectorErrors[0] = storobj.NewErrNotFoundf(0, "deleted")
		vectorIndex.cache.Delete(context.Background(), 0)
	})

	t.Run("try to insert a fourth vector", func(t *testing.T) {
		vectors = append(vectors, []float32{4, 4})
		vectorErrors = append(vectorErrors, nil)

		pos := len(vectors) - 1
		err := vectorIndex.Add(ctx, uint64(pos), vectors[pos])
		require.Nil(t, err)
	})
}

func TestDelete_WithCleaningUpTombstonesOncePreservesMaxConnections(t *testing.T) {
	// there is a single bulk clean event after all the deletes
	vectors := vectorsForDeleteTest()
	ctx := context.Background()
	var vectorIndex *hnsw

	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	index, err := New(Config{
		RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
		ID:                    "delete-test",
		MakeCommitLoggerThunk: MakeNoopCommitLogger,
		DistanceProvider:      distancer.NewCosineDistanceProvider(),
		VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
			return vectors[int(id)], nil
		},
		TempVectorForIDThunk: TempVectorForIDThunk(vectors),
	}, ent.UserConfig{
		MaxConnections: 30,
		EFConstruction: 128,

		// The actual size does not matter for this test, but if it defaults to
		// zero it will constantly think it's full and needs to be deleted - even
		// after just being deleted, so make sure to use a positive number here.
		VectorCacheMaxObjects: 100000,
	}, cyclemanager.NewCallbackGroupNoop(), store)
	require.Nil(t, err)
	vectorIndex = index

	for i, vec := range vectors {
		err := vectorIndex.Add(ctx, uint64(i), vec)
		require.Nil(t, err)
	}

	require.Equal(t, 60, index.maximumConnectionsLayerZero)
	some := false
	for _, node := range index.nodes {
		if node == nil {
			continue
		}
		require.LessOrEqual(t, len(node.connections[0]), index.maximumConnectionsLayerZero)
		some = some || len(node.connections[0]) > index.maximumConnections
	}
	require.True(t, some)

	for i := range vectors {
		if i%2 != 0 {
			continue
		}

		err := vectorIndex.Delete(uint64(i))
		require.Nil(t, err)
	}

	err = vectorIndex.CleanUpTombstonedNodes(neverStop)
	require.Nil(t, err)
	require.Equal(t, 60, index.maximumConnectionsLayerZero)
	some = false
	for _, node := range index.nodes {
		if node == nil {
			continue
		}
		require.LessOrEqual(t, len(node.connections[0]), index.maximumConnectionsLayerZero)
		some = some || len(node.connections[0]) > index.maximumConnections
	}
	require.True(t, some)

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}

func TestDelete_WithCleaningUpTombstonesOnceRemovesAllRelatedConnections(t *testing.T) {
	// there is a single bulk clean event after all the deletes
	vectors := vectorsForDeleteTest()
	ctx := context.Background()
	var vectorIndex *hnsw
	store := testinghelpers.NewDummyStore(t)

	index, err := New(Config{
		RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
		ID:                    "delete-test",
		MakeCommitLoggerThunk: MakeNoopCommitLogger,
		DistanceProvider:      distancer.NewCosineDistanceProvider(),
		VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
			return vectors[int(id)], nil
		},
		TempVectorForIDThunk: TempVectorForIDThunk(vectors),
	}, ent.UserConfig{
		MaxConnections: 30,
		EFConstruction: 128,

		// The actual size does not matter for this test, but if it defaults to
		// zero it will constantly think it's full and needs to be deleted - even
		// after just being deleted, so make sure to use a positive number here.
		VectorCacheMaxObjects: 100000,
	}, cyclemanager.NewCallbackGroupNoop(), store)
	require.Nil(t, err)
	vectorIndex = index

	for i, vec := range vectors {
		err := vectorIndex.Add(ctx, uint64(i), vec)
		require.Nil(t, err)
	}

	for i := range vectors {
		if i%2 != 0 {
			continue
		}

		err := vectorIndex.Delete(uint64(i))
		require.Nil(t, err)
	}

	err = vectorIndex.CleanUpTombstonedNodes(neverStop)
	require.Nil(t, err)

	for i, node := range vectorIndex.nodes {
		if node == nil {
			continue
		}
		assert.NotEqual(t, 0, i%2)
		for level, connections := range node.connections {
			for _, id := range connections {
				assert.NotEqual(t, uint64(0), id%2)
				if id%2 == 0 {
					fmt.Println("at: ", vectorIndex.entryPointID, i, level, id)
				}
			}
		}
	}

	require.Nil(t, vectorIndex.Drop(context.Background()))
	store.Shutdown(context.Background())
}

func TestDelete_WithCleaningUpTombstonesWithHighConcurrency(t *testing.T) {
	ctx := context.Background()
	os.Setenv("TOMBSTONE_DELETION_CONCURRENCY", "100")
	defer os.Unsetenv("TOMBSTONE_DELETION_CONCURRENCY")
	// there is a single bulk clean event after all the deletes
	vectors, _ := testinghelpers.RandomVecs(3_000, 1, 1536)
	var vectorIndex *hnsw

	store := testinghelpers.NewDummyStore(t)
	defer store.Shutdown(context.Background())

	t.Run("import the test vectors", func(t *testing.T) {
		index, err := New(Config{
			RootPath:              "doesnt-matter-as-committlogger-is-mocked-out",
			ID:                    "delete-test",
			MakeCommitLoggerThunk: MakeNoopCommitLogger,
			DistanceProvider:      distancer.NewCosineDistanceProvider(),
			VectorForIDThunk: func(ctx context.Context, id uint64) ([]float32, error) {
				return vectors[int(id)], nil
			},
			TempVectorForIDThunk: TempVectorForIDThunk(vectors),
		}, ent.UserConfig{
			MaxConnections: 30,
			EFConstruction: 128,

			// The actual size does not matter for this test, but if it defaults to
			// zero it will constantly think it's full and needs to be deleted - even
			// after just being deleted, so make sure to use a positive number here.
			VectorCacheMaxObjects: 100000,
		}, cyclemanager.NewCallbackGroupNoop(), store)
		require.Nil(t, err)
		vectorIndex = index

		for i, vec := range vectors {
			err := vectorIndex.Add(ctx, uint64(i), vec)
			require.Nil(t, err)
		}
	})

	fmt.Printf("entrypoint before %d\n", vectorIndex.entryPointID)
	t.Run("deleting elements", func(t *testing.T) {
		for i := range vectors {
			if i < 10 {
				continue
			}

			err := vectorIndex.Delete(uint64(i))
			require.Nil(t, err)
		}
	})

	fmt.Printf("entrypoint after %d\n", vectorIndex.entryPointID)

	t.Run("running the cleanup", func(t *testing.T) {
		err := vectorIndex.CleanUpTombstonedNodes(neverStop)
		require.Nil(t, err)
	})

	t.Run("verify the graph no longer has any tombstones", func(t *testing.T) {
		assert.Len(t, vectorIndex.tombstones, 0)
	})

	t.Run("destroy the index", func(t *testing.T) {
		require.Nil(t, vectorIndex.Drop(context.Background()))
	})
}
