bugabinga.net

package web

import (
	"math/rand/v2"
	"reflect"
	"strconv"
	"strings"
	"testing"

	"bugabinga.net/luci/internal/history"
	"bugabinga.net/luci/internal/inbox"
	"bugabinga.net/luci/internal/proquint"
	"bugabinga.net/luci/internal/runstate"
)

func TestBuildShortenerMatchesReference(t *testing.T) {
	tests := []struct {
		name           string
		events         []history.Event
		pending        []inbox.Pending
		active         []runstate.Active
		wantRunShort   map[string]string
		wantNoRunShort []string
		wantRevShort   map[string]string
		wantNoRevShort []string
	}{
		{
			name: "parse failures and zero aliases",
			events: []history.Event{
				{RunID: "0", Rev: "abcd"},
				{RunID: "+0", Rev: "abc"},
				{RunID: "not-a-number", Rev: "abcd0"},
			},
			pending:        []inbox.Pending{{ID: "9223372036854775808"}},
			active:         []runstate.Active{{RunID: "-0", Rev: "abce"}},
			wantNoRunShort: []string{"0", "+0", "-0", "not-a-number", "9223372036854775808"},
			wantRevShort:   map[string]string{"abcd0": "abcd0", "abce": "abce"},
			wantNoRevShort: []string{"abc"},
		},
		{
			name: "negative ids and block boundaries",
			events: []history.Event{
				{RunID: "0"},
				{RunID: "1"},
				{RunID: "65536"},
				{RunID: "-1"},
			},
			wantRunShort: map[string]string{
				"0":     proquint.Encode(0),
				"1":     proquint.Encode(1),
				"65536": proquint.Encode(65536)[:17],
				"-1":    proquint.Encode(-1)[:5],
			},
		},
		{
			name: "duplicate equivalent encodings",
			events: []history.Event{
				{RunID: "1"},
				{RunID: "0001"},
			},
			pending:        []inbox.Pending{{ID: "+1"}},
			wantNoRunShort: []string{"1", "0001", "+1"},
		},
		{
			name: "revision boundaries",
			events: []history.Event{
				{RunID: "1", Rev: "abc"},
				{RunID: "2", Rev: "abcd"},
				{RunID: "3", Rev: "abcd0"},
				{RunID: "4", Rev: "abce"},
				{RunID: "5", Rev: ""},
			},
			wantRevShort:   map[string]string{"abcd0": "abcd0", "abce": "abce"},
			wantNoRevShort: []string{"abc", "abcd"},
		},
	}

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			want := referenceShortener(test.events, test.pending, test.active)
			for range 100 {
				if got := buildShortener(test.events, test.pending, test.active); !reflect.DeepEqual(got, want) {
					t.Fatalf("shortener=%#v want %#v", got, want)
				}
			}
			got := buildShortener(test.events, test.pending, test.active)
			for id, short := range test.wantRunShort {
				if got.runShort[id] != short {
					t.Fatalf("run id %q shortened to %q want %q", id, got.runShort[id], short)
				}
			}
			for _, id := range test.wantNoRunShort {
				if _, ok := got.runShort[id]; ok {
					t.Fatalf("run id %q unexpectedly shortened to %q", id, got.runShort[id])
				}
			}
			for rev, short := range test.wantRevShort {
				if got.revShort[rev] != short {
					t.Fatalf("revision %q shortened to %q want %q", rev, got.revShort[rev], short)
				}
			}
			for _, rev := range test.wantNoRevShort {
				if _, ok := got.revShort[rev]; ok {
					t.Fatalf("revision %q unexpectedly shortened to %q", rev, got.revShort[rev])
				}
			}
		})
	}
}

func TestBuildShortenerMatchesReferenceRandomized(t *testing.T) {
	random := rand.New(rand.NewPCG(20260927, 1))
	for set := range 50 {
		events, pending, active := randomShortenerInputs(random, 1+random.IntN(80))
		want := referenceShortener(events, pending, active)
		for range 10 {
			if got := buildShortener(events, pending, active); !reflect.DeepEqual(got, want) {
				t.Fatalf("set %d: shortener=%#v want %#v", set, got, want)
			}
		}
	}
}

func randomShortenerInputs(random *rand.Rand, count int) ([]history.Event, []inbox.Pending, []runstate.Active) {
	events := make([]history.Event, 0, count)
	pending := make([]inbox.Pending, 0, count)
	active := make([]runstate.Active, 0, count)
	for i := range count {
		id := randomShortenerID(random, i)
		rev := randomShortenerRevision(random, i)
		switch i % 3 {
		case 0:
			events = append(events, history.Event{RunID: id, Rev: rev})
		case 1:
			pending = append(pending, inbox.Pending{ID: id})
		case 2:
			active = append(active, runstate.Active{RunID: id, Rev: rev})
		}
	}
	return events, pending, active
}

func randomShortenerID(random *rand.Rand, index int) string {
	switch index % 8 {
	case 0:
		return strconv.FormatInt(random.Int64(), 10)
	case 1:
		return "0"
	case 2:
		return "+0"
	case 3:
		return "-0"
	case 4:
		return "invalid-" + strconv.Itoa(random.IntN(8))
	case 5:
		return "9223372036854775808"
	case 6:
		return "000" + strconv.Itoa(random.IntN(4))
	default:
		return strconv.FormatInt(-random.Int64N(1<<32), 10)
	}
}

func randomShortenerRevision(random *rand.Rand, index int) string {
	length := index % 9
	if length == 0 {
		return ""
	}
	const hex = "0123456789abcdef"
	var text strings.Builder
	for range length {
		text.WriteByte(hex[random.IntN(len(hex))])
	}
	return text.String()
}

// referenceShortener preserves buildShortener's pre-optimization algorithm.
func referenceShortener(events []history.Event, pending []inbox.Pending, active []runstate.Active) shortener {
	ids := map[string]bool{}
	for _, event := range events {
		ids[event.RunID] = true
	}
	for _, current := range pending {
		ids[current.ID] = true
	}
	for _, current := range active {
		ids[current.RunID] = true
	}
	revs := map[string]bool{}
	for _, event := range events {
		if event.Rev != "" {
			revs[event.Rev] = true
		}
	}
	for _, current := range active {
		if current.Rev != "" {
			revs[current.Rev] = true
		}
	}
	runShort := map[string]string{}
	for id := range ids {
		blocks := strings.Split(proquint.Encode(parseID(id)), "-")
		for keep := 1; keep <= len(blocks); keep++ {
			prefix := strings.Join(blocks[:keep], "-")
			if referenceUniquePrefix(ids, prefix) {
				runShort[id] = prefix
				break
			}
		}
	}
	revShort := map[string]string{}
	for rev := range revs {
		for length := 4; length <= len(rev); length++ {
			if referenceUniqueHexPrefix(revs, rev[:length]) {
				revShort[rev] = rev[:length]
				break
			}
		}
	}
	return shortener{runShort: runShort, revShort: revShort}
}

func referenceUniquePrefix(ids map[string]bool, prefix string) bool {
	count := 0
	for id := range ids {
		if strings.HasPrefix(proquint.Encode(parseID(id)), prefix) {
			count++
		}
	}
	return count == 1
}

func referenceUniqueHexPrefix(revs map[string]bool, prefix string) bool {
	count := 0
	for rev := range revs {
		if strings.HasPrefix(rev, prefix) {
			count++
		}
	}
	return count == 1
}