tree_test.go

     1  // Copyright 2025 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package token
     6  
     7  import (
     8  	"math/rand/v2"
     9  	"slices"
    10  	"testing"
    11  )
    12  
    13  // TestTree provides basic coverage of the AVL tree operations.
    14  func TestTree(t *testing.T) {
    15  	// Use a reproducible PRNG.
    16  	seed1, seed2 := rand.Uint64(), rand.Uint64()
    17  	t.Logf("random seeds: %d, %d", seed1, seed2)
    18  	rng := rand.New(rand.NewPCG(seed1, seed2))
    19  
    20  	// Create a number of Files of arbitrary size.
    21  	files := make([]*File, 500)
    22  	var base int
    23  	for i := range files {
    24  		base++
    25  		size := 1000
    26  		files[i] = &File{base: base, size: size}
    27  		base += size
    28  	}
    29  
    30  	// Add them all to the tree in random order.
    31  	var tr tree
    32  	{
    33  		files2 := slices.Clone(files)
    34  		Shuffle(rng, files2)
    35  		for _, f := range files2 {
    36  			tr.add(f)
    37  		}
    38  	}
    39  
    40  	// Randomly delete a subset of them.
    41  	for range 100 {
    42  		i := rng.IntN(len(files))
    43  		file := files[i]
    44  		if file == nil {
    45  			continue // already deleted
    46  		}
    47  		files[i] = nil
    48  
    49  		pn, _ := tr.locate(file.key())
    50  		if (*pn).file != file {
    51  			t.Fatalf("locate returned wrong file")
    52  		}
    53  		tr.delete(pn)
    54  	}
    55  
    56  	// Check some position lookups within each file.
    57  	for _, file := range files {
    58  		if file == nil {
    59  			continue // deleted
    60  		}
    61  		for _, pos := range []int{
    62  			file.base,               // start
    63  			file.base + file.size/2, // midpoint
    64  			file.base + file.size,   // end
    65  		} {
    66  			pn, _ := tr.locate(key{pos, pos})
    67  			if (*pn).file != file {
    68  				t.Fatalf("lookup %s@%d returned wrong file %s",
    69  					file.name, pos,
    70  					(*pn).file.name)
    71  			}
    72  		}
    73  	}
    74  
    75  	// Check that the sequence is the same.
    76  	files = slices.DeleteFunc(files, func(f *File) bool { return f == nil })
    77  	if !slices.Equal(slices.Collect(tr.all()), files) {
    78  		t.Fatalf("incorrect tree.all sequence")
    79  	}
    80  }
    81  
    82  func Shuffle[T any](rng *rand.Rand, slice []*T) {
    83  	rng.Shuffle(len(slice), func(i, j int) {
    84  		slice[i], slice[j] = slice[j], slice[i]
    85  	})
    86  }
    87
View as plain text