//go:build ignore

// Вставка в карту Go: что делает H1, а что H2.
//
// ЗАЧЕМ ЭТА ПРОГРАММА. Про Swiss Table обычно пишут, что хеш делится на H1 и
// H2, и на этом останавливаются. Из такой фразы не выводится ничего: непонятно,
// где H1 применяется, почему H2 попадает в управляющий байт, почему вставка
// обязана сначала ИСКАТЬ и что происходит, когда по дороге встретился удалённый
// слот. Здесь путь вставки выполняется по шагам и печатается целиком.
//
// ЧТО ЗДЕСЬ НАСТОЯЩЕЕ. Алгоритм — дословный перенос `table.PutSlot` из
// go1.24.7, `src/internal/runtime/maps/table.go`, вместе с разбором хеша
// (`h1(h) = h >> 7`, `h2(h) = h & 0x7f`, `map.go`), треугольным путём поиска
// (`makeProbeSeq`, `table.go`) и битовыми формулами группы (`group.go`).
// Порядок решений сохранён вплоть до правила «первый удалённый слот
// запоминается, но путь продолжается до свободного».
//
// ЧТО ЗДЕСЬ УСЛОВНО, И ПОЧЕМУ ИНАЧЕ НЕЛЬЗЯ. Хеш-функция взята другая: FNV-1a из
// `hash/fnv`. Карта хеширует своей внутренней функцией со случайным seed,
// который выбирается при создании карты, — снаружи её ни вызвать, ни
// воспроизвести. Взять детерминированную функцию — единственный способ
// напечатать числа, которые у читателя получатся такими же. На разбор хеша это
// не влияет: делится любое 64-битное число одинаково.
//
// Таблица тоже маленькая: 4 группы по 8 слотов вместо настоящей, которая для
// таких размеров ещё и не разбита на несколько таблиц. Сокращена ТОЛЬКО
// ширина, не правила.
//
// ЧЕМ ПОДПЁРТО. Блок 4 проверяет перенос: битовые формулы сверяются с честным
// перебором на всех 128 метках и на случайных группах, а треугольный путь — с
// утверждением исходника, что он обходит каждую группу ровно один раз. Блок 5
// сверяет наблюдаемую часть с настоящей `map[string]int`: то, что видно снаружи
// (len до и после повторной вставки), обязано совпасть.
//
// ЗАПУСК:
//
//	go run bench/gomap/insert.go
package main

import (
	"fmt"
	"hash/fnv"
	"math/bits"
	"math/rand"
	"strings"
)

// ------------------------------------------------------------ из group.go
//
// Дословно из go1.24.7, src/internal/runtime/maps/group.go.
//
//	  empty: 1 0 0 0 0 0 0 0
//	deleted: 1 1 1 1 1 1 1 0
//	   full: 0 h h h h h h h
//
// Про последнюю строку в group.go написано «h represents the H1 hash bits», и
// это единственное место, где сказано «H1». Код рядом говорит обратное:
// `PutSlot` пишет в управляющий байт `ctrl(h2(hash))`, поиск ищет `matchH2`, а
// `map.go` над самой функцией `h2` поясняет: «These are used as an occupied
// control byte». В управляющем байте лежит H2; комментарий в group.go
// разошёлся с кодом.

const (
	ctrlEmpty   = 0b10000000
	ctrlDeleted = 0b11111110

	bitsetLSB = 0x0101010101010101
	bitsetMSB = 0x8080808080808080

	slotsPerGroup = 8 // abi.SwissMapGroupSlots
	maxAvgLoad    = 7 // maxAvgGroupLoad из group.go: 7 занятых слотов на 8
)

func matchH2(g uint64, h uint8) uint64 {
	v := g ^ (bitsetLSB * uint64(h))
	return ((v - bitsetLSB) &^ v) & bitsetMSB
}

func matchEmpty(g uint64) uint64          { return (g &^ (g << 6)) & bitsetMSB }
func matchEmptyOrDeleted(g uint64) uint64 { return g & bitsetMSB }

// first — номер слота по младшему выставленному биту (bitsetFirst из group.go).
func first(mask uint64) int { return bits.TrailingZeros64(mask) >> 3 }

// removeFirst гасит младший выставленный бит (bitset.removeFirst).
func removeFirst(mask uint64) uint64 { return mask & (mask - 1) }

// ------------------------------------------------------------ из map.go

// h1 — старшие 57 бит хеша. Ими выбирается группа и задаётся путь поиска.
func h1(h uint64) uint64 { return h >> 7 }

// h2 — младшие 7 бит хеша. Они ложатся в управляющий байт как метка слота.
func h2(h uint64) uint8 { return uint8(h & 0x7f) }

// ------------------------------------------------------------ из table.go

// probeSeq — треугольный путь по группам, p(i) = (i²+i)/2 + hash (mod mask+1).
type probeSeq struct {
	mask   uint64
	offset uint64
	index  uint64
}

func makeProbeSeq(hash, mask uint64) probeSeq {
	return probeSeq{mask: mask, offset: hash & mask}
}

func (s probeSeq) next() probeSeq {
	s.index++
	s.offset = (s.offset + s.index) & s.mask
	return s
}

// ------------------------------------------------------------ таблица

type slot struct {
	key string
	val int
}

type table struct {
	mask       uint64 // число групп минус один
	ctrl       []uint64
	slots      [][slotsPerGroup]slot
	growthLeft int
	used       int
}

func newTable(groups int) *table {
	t := &table{
		mask:  uint64(groups - 1),
		ctrl:  make([]uint64, groups),
		slots: make([][slotsPerGroup]slot, groups),
	}
	for i := range t.ctrl {
		t.ctrl[i] = bitsetLSB * uint64(ctrlEmpty) // все слоты свободны
	}
	t.growthLeft = groups * slotsPerGroup * maxAvgLoad / slotsPerGroup
	return t
}

// clone — честная копия. Нужна, чтобы каждый сценарий начинался с одного и
// того же состояния. Первая версия делала `snap := *t`, и это было ошибкой:
// в table лежат срезы, у копии структуры массив под ними тот же самый, так что
// запись одного сценария оказывалась видна следующему. В напечатанной трассе
// это выглядело так, будто вставка нового ключа обернулась обновлением
// существующего, — программа сама себе противоречила, и потому ошибку было
// видно.
func (t *table) clone() *table {
	c := &table{
		mask:       t.mask,
		ctrl:       append([]uint64(nil), t.ctrl...),
		slots:      append([][slotsPerGroup]slot(nil), t.slots...),
		growthLeft: t.growthLeft,
		used:       t.used,
	}
	return c
}

func (t *table) ctrlByte(g, i int) uint8 { return uint8(t.ctrl[g] >> (8 * i)) }

func (t *table) setCtrl(g, i int, c uint8) {
	t.ctrl[g] &^= 0xff << (8 * i)
	t.ctrl[g] |= uint64(c) << (8 * i)
}

func hash(key string) uint64 {
	h := fnv.New64a()
	_, _ = h.Write([]byte(key))
	return h.Sum64()
}

// step — одна запись трассы. Печатается и она же уезжает в картинку.
type step struct {
	group    int
	kind     string // probe-match, probe-full, probe-deleted, probe-empty, write, update, grow
	slotIdx  int
	comment  string
	candidat []int // слоты, у которых совпала метка

	// Где путь ДОШЁЛ до свободного слота. Может отличаться от group: если по
	// дороге попался удалённый слот, ключ ложится в него, а не сюда. Без этих
	// двух полей трасса умалчивала самое интересное — что путь побывал в одной
	// группе, а запись случилась в другой.
	endGroup int
	endSlot  int
}

// put повторяет table.PutSlot: сначала ищет ключ, потом место.
func (t *table) put(key string, val int) (trace []step) {
	h := hash(key)
	mark := h2(h)
	seq := makeProbeSeq(h1(h), t.mask)

	firstDeletedGroup, firstDeletedSlot := -1, -1

	for {
		g := int(seq.offset)
		word := t.ctrl[g]

		// 1. Есть ли уже такой ключ? Сначала метка, потом полное сравнение.
		match := matchH2(word, mark)
		var cands []int
		for m := match; m != 0; m = removeFirst(m) {
			cands = append(cands, first(m))
		}
		for m := match; m != 0; m = removeFirst(m) {
			i := first(m)
			if t.slots[g][i].key == key {
				t.slots[g][i].val = val
				trace = append(trace, step{group: g, kind: "update", slotIdx: i, candidat: cands,
					comment: "метка совпала и ключ совпал целиком — это тот же ключ. Значение переписывается на месте: нового слота не появляется, len не растёт."})
				return
			}
		}
		if len(cands) > 0 {
			trace = append(trace, step{group: g, kind: "probe-match", slotIdx: -1, candidat: cands,
				comment: "метка совпала, но ключ при полном сравнении оказался чужим. Семь бит — не ответ, а сужение круга: это ложное совпадение, поиск продолжается в этой же группе."})
		}

		// 2. Ключа здесь нет. Конец ли это пути?
		free := matchEmptyOrDeleted(word)
		if free == 0 {
			trace = append(trace, step{group: g, kind: "probe-full", slotIdx: -1, candidat: cands,
				comment: "в группе нет ни одного свободного или удалённого слота — она занята целиком. Остановиться нельзя: ключ мог осесть дальше по пути."})
			seq = seq.next()
			continue
		}
		i := first(free)
		if t.ctrlByte(g, i) == ctrlDeleted {
			if firstDeletedGroup < 0 {
				firstDeletedGroup, firstDeletedSlot = g, i
			}
			trace = append(trace, step{group: g, kind: "probe-deleted", slotIdx: i, candidat: cands,
				comment: "первый незанятый слот здесь — удалённый. Место запоминается, но путь продолжается: пока не встретился свободный слот, нельзя утверждать, что такого ключа в таблице нет."})
			seq = seq.next()
			continue
		}

		// 3. Свободный слот: путь окончен, ключа в таблице нет.
		endG, endI := g, i
		useG, useI := g, i
		reused := false
		if firstDeletedGroup >= 0 {
			useG, useI = firstDeletedGroup, firstDeletedSlot
			reused = true
			t.growthLeft++ // ниже вычтется обратно: удалённый слот уже был учтён
		}

		if t.growthLeft <= 0 {
			trace = append(trace, step{group: g, kind: "grow", slotIdx: i, candidat: cands,
				comment: "место есть, но запаса роста не осталось: занято 7/8. Таблица пересобирается, и только потом ключ ложится на место."})
			return
		}

		t.slots[useG][useI] = slot{key: key, val: val}
		t.setCtrl(useG, useI, mark)
		t.growthLeft--
		t.used++

		why := "свободный слот — конец пути: будь такой ключ в таблице, он лежал бы не дальше этого места. Ключ и значение ложатся в слот, а в управляющий байт пишется метка — младшие 7 бит хеша."
		if reused {
			why = fmt.Sprintf("свободный слот нашёлся в группе %d — значит, такого ключа в таблице точно нет. Только теперь можно вернуться к запомненному удалённому слоту в группе %d и занять его: он ближе к началу пути, и запас роста на него не тратится.", endG, useG)
		}
		trace = append(trace, step{group: useG, kind: "write", slotIdx: useI, candidat: cands,
			endGroup: endG, endSlot: endI, comment: why})
		return
	}
}

func (t *table) del(key string) bool {
	h := hash(key)
	mark := h2(h)
	seq := makeProbeSeq(h1(h), t.mask)
	for {
		g := int(seq.offset)
		word := t.ctrl[g]
		for m := matchH2(word, mark); m != 0; m = removeFirst(m) {
			i := first(m)
			if t.slots[g][i].key == key {
				t.slots[g][i] = slot{}
				// Правило из map.go: если в группе есть свободный слот, удалённый
				// можно пометить свободным; иначе — только «удалён».
				if matchEmpty(word) != 0 {
					t.setCtrl(g, i, ctrlEmpty)
					t.growthLeft++
				} else {
					t.setCtrl(g, i, ctrlDeleted)
				}
				t.used--
				return true
			}
		}
		if matchEmpty(word) != 0 {
			return false
		}
		seq = seq.next()
	}
}

// ------------------------------------------------------------ печать

func stateRune(c uint8) string {
	switch {
	case c == ctrlEmpty:
		return "  ····"
	case c == ctrlDeleted:
		return "  удал"
	default:
		return fmt.Sprintf("  0x%02x", c)
	}
}

func (t *table) dump(indent string) {
	for g := range t.ctrl {
		var parts []string
		for i := 0; i < slotsPerGroup; i++ {
			parts = append(parts, stateRune(t.ctrlByte(g, i)))
		}
		fmt.Printf("%sгруппа %d %s\n", indent, g, strings.Join(parts, ""))
	}
}

func header(n int, title string) {
	fmt.Printf("\n=== БЛОК %d. %s ===\n\n", n, title)
}

// ------------------------------------------------------------ блок 1

func blockSplit(keys []string) {
	header(1, "КАК ДЕЛИТСЯ ХЕШ")
	fmt.Println("  h1 = h >> 7   (старшие 57 бит)   — выбирает группу и задаёт путь")
	fmt.Println("  h2 = h & 0x7f (младшие  7 бит)   — ложится в управляющий байт")
	fmt.Println()
	fmt.Printf("  %-8s %-20s %-8s %-6s %s\n", "ключ", "хеш", "h2", "группа", "младшие 16 бит хеша")
	for _, k := range keys {
		h := hash(k)
		fmt.Printf("  %-8s 0x%016x 0x%02x   %-6d %s|%s\n",
			k, h, h2(h), h1(h)&3,
			fmt.Sprintf("%09b", (h>>7)&0x1ff), fmt.Sprintf("%07b", h&0x7f))
	}
	fmt.Println()
	fmt.Println("  Столбец справа — это одно и то же число, разрезанное по седьмому биту:")
	fmt.Println("  слева от черты уходит в h1, справа — в h2. Ни один бит не участвует")
	fmt.Println("  в обеих ролях, поэтому совпадение метки ничего не говорит о группе,")
	fmt.Println("  а номер группы ничего не говорит о метке.")
}

// ------------------------------------------------------------ блок 2

func printTrace(title, key string, t *table, trace []step) {
	h := hash(key)
	fmt.Printf("  %s\n", title)
	fmt.Printf("    m[%q] = …\n", key)
	fmt.Printf("    хеш 0x%016x   h1 = 0x%014x   h2 = 0x%02x   старт: группа %d\n",
		h, h1(h), h2(h), h1(h)&t.mask)
	for i, s := range trace {
		fmt.Printf("    шаг %d · группа %d · %s\n", i+1, s.group, s.kind)
		if len(s.candidat) > 0 {
			fmt.Printf("            метка совпала в слотах: %v\n", s.candidat)
		}
		if s.kind == "write" || s.kind == "update" || s.kind == "probe-deleted" {
			fmt.Printf("            слот %d\n", s.slotIdx)
		}
		if s.kind == "write" && s.endGroup != s.group {
			fmt.Printf("            путь дошёл до свободного слота в группе %d, слот %d,\n", s.endGroup, s.endSlot)
			fmt.Printf("            но запись — в группу %d: там ждал удалённый слот\n", s.group)
		}
		fmt.Printf("            %s\n", s.comment)
	}
	fmt.Printf("    len после операции: %d\n\n", t.used)
}


// ------------------------------------------------------------ блок 3
//
// Данные для картинки печатаются здесь же, а не переносятся в неё руками.
// Правило простое: если число видно читателю, оно должно быть в записи
// прогона. Копировать глазами таблицу из восьми слотов на четыре группы —
// верный способ ошибиться в одном байте и не заметить.

func jsonSlots(t *table) string {
	var groups []string
	for g := range t.ctrl {
		var cells []string
		for i := 0; i < slotsPerGroup; i++ {
			c := t.ctrlByte(g, i)
			switch {
			case c == ctrlEmpty:
				cells = append(cells, `{"s":"empty"}`)
			case c == ctrlDeleted:
				cells = append(cells, `{"s":"deleted"}`)
			default:
				cells = append(cells, fmt.Sprintf(`{"s":"used","h2":%d,"k":%q}`, c, t.slots[g][i].key))
			}
		}
		groups = append(groups, "  ["+strings.Join(cells, ",")+"]")
	}
	return "[\n" + strings.Join(groups, ",\n") + "\n ]"
}

func jsonTrace(key string, t *table, trace []step) string {
	h := hash(key)
	var steps []string
	for _, s := range trace {
		steps = append(steps, fmt.Sprintf(
			`  {"group":%d,"kind":%q,"slot":%d,"endGroup":%d,"endSlot":%d,"cands":%s}`,
			s.group, s.kind, s.slotIdx, s.endGroup, s.endSlot, jsonInts(s.candidat)))
	}
	return fmt.Sprintf("{\n \"key\":%q,\n \"hash\":\"0x%016x\",\n \"h1\":\"0x%x\",\n \"h2\":%d,\n \"start\":%d,\n \"lenBefore\":%d,\n \"steps\":[\n%s\n ]\n}",
		key, h, h1(h), h2(h), h1(h)&t.mask, t.used, strings.Join(steps, ",\n"))
}

func jsonInts(xs []int) string {
	if len(xs) == 0 {
		return "[]"
	}
	parts := make([]string, len(xs))
	for i, x := range xs {
		parts[i] = fmt.Sprint(x)
	}
	return "[" + strings.Join(parts, ",") + "]"
}

// ------------------------------------------------------------ блок 4

func blockSelfCheck() {
	header(4, "ПРОВЕРКА ПЕРЕНОСА")

	// 4.1. Битовые формулы против честного перебора.
	rng := rand.New(rand.NewSource(20260902))
	bad := 0
	for n := 0; n < 200000; n++ {
		var b [slotsPerGroup]uint8
		var word uint64
		for i := range b {
			switch rng.Intn(4) {
			case 0:
				b[i] = ctrlEmpty
			case 1:
				b[i] = ctrlDeleted
			default:
				b[i] = uint8(rng.Intn(128))
			}
			word |= uint64(b[i]) << (8 * i)
		}
		h := uint8(rng.Intn(128))
		var wantH2, wantEmpty, wantEOD []int
		for i, c := range b {
			if c == h {
				wantH2 = append(wantH2, i)
			}
			if c == ctrlEmpty {
				wantEmpty = append(wantEmpty, i)
			}
			if c == ctrlEmpty || c == ctrlDeleted {
				wantEOD = append(wantEOD, i)
			}
		}
		gotH2 := setBits(matchH2(word, h))
		if !covers(gotH2, wantH2) || !equal(setBits(matchEmpty(word)), wantEmpty) ||
			!equal(setBits(matchEmptyOrDeleted(word)), wantEOD) {
			bad++
		}
	}
	fmt.Printf("  формулы группы против перебора, 200 000 случайных групп: расхождений %d\n", bad)
	fmt.Println("  (matchH2 сверяется на «не пропустил ни одного настоящего совпадения»:")
	fmt.Println("   лишние кандидаты формуле разрешены и стоят одного сравнения ключа)")

	// 4.2. Треугольный путь обходит каждую группу ровно один раз.
	fmt.Println()
	for _, groups := range []int{4, 8, 16, 64, 1024} {
		mask := uint64(groups - 1)
		ok := true
		for start := uint64(0); start < uint64(groups) && ok; start++ {
			seen := make(map[uint64]bool, groups)
			s := makeProbeSeq(start, mask)
			for i := 0; i < groups; i++ {
				if seen[s.offset] {
					ok = false
					break
				}
				seen[s.offset] = true
				s = s.next()
			}
			if len(seen) != groups {
				ok = false
			}
		}
		fmt.Printf("  путь по %4d группам обходит каждую ровно один раз: %v\n", groups, ok)
	}
}

func setBits(mask uint64) []int {
	var out []int
	for i := 0; i < slotsPerGroup; i++ {
		if mask&(1<<(8*i+7)) != 0 {
			out = append(out, i)
		}
	}
	return out
}

func equal(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func contains(xs []string, x string) bool {
	for _, v := range xs {
		if v == x {
			return true
		}
	}
	return false
}

// covers — все ожидаемые слоты названы (лишние формуле разрешены).
func covers(got, want []int) bool {
	set := map[int]bool{}
	for _, g := range got {
		set[g] = true
	}
	for _, w := range want {
		if !set[w] {
			return false
		}
	}
	return true
}

// ------------------------------------------------------------ блок 5

func blockAgainstRealMap() {
	header(5, "СВЕРКА С НАСТОЯЩЕЙ КАРТОЙ")
	fmt.Println("  Внутренности воспроизведены, поэтому наблюдаемая часть обязана совпасть")
	fmt.Println("  с тем, что делает настоящая map[string]int. Проверяется то, что видно")
	fmt.Println("  снаружи: как len отвечает на вставку нового ключа, на повторную вставку")
	fmt.Println("  того же ключа и на вставку после удаления.")
	fmt.Println()

	real := map[string]int{}
	model := newTable(4)

	type op struct {
		kind string
		key  string
	}
	ops := []op{
		{"put", "alpha"}, {"put", "bravo"}, {"put", "delta"},
		{"put", "alpha"}, // повторная вставка того же ключа
		{"del", "bravo"},
		{"put", "echo"},
		{"put", "bravo"}, // вставка после удаления
	}

	mismatch := 0
	for _, o := range ops {
		switch o.kind {
		case "put":
			real[o.key] = 1
			model.put(o.key, 1)
		case "del":
			delete(real, o.key)
			model.del(o.key)
		}
		mark := "="
		if len(real) != model.used {
			mark = "РАСХОЖДЕНИЕ"
			mismatch++
		}
		fmt.Printf("  %-4s %-7s  len настоящей: %d   len модели: %d   %s\n",
			o.kind, o.key, len(real), model.used, mark)
	}
	fmt.Printf("\n  расхождений: %d\n", mismatch)
}

// ------------------------------------------------------------ подбор ключей

// findKeys подбирает ключи под нужные сценарии на настоящих хешах, а не
// подгоняет числа: перебираются короткие имена вида k0, k1, …, и берутся
// первые, у которых складывается нужная ситуация.
func candidates(n int) []string {
	out := make([]string, 0, n)
	for i := 0; i < n; i++ {
		out = append(out, fmt.Sprintf("k%d", i))
	}
	return out
}

func main() {
	fmt.Println("ВСТАВКА В КАРТУ GO: ЧТО ДЕЛАЕТ H1, А ЧТО H2")
	fmt.Println()
	fmt.Println("Алгоритм — перенос table.PutSlot из go1.24.7. Хеш-функция взята")
	fmt.Println("детерминированная (FNV-1a), потому что внутренний хеш карты сеется")
	fmt.Println("случайно при её создании и снаружи не воспроизводится. Таблица")
	fmt.Println("сокращена до 4 групп по 8 слотов; сокращена только ширина, не правила.")

	blockSplit([]string{"alpha", "bravo", "delta", "echo", "foxtrot"})

	// --- строим таблицу настоящими вставками
	header(2, "ТРАССА ВСТАВКИ")

	t := newTable(4)
	var base []string
	for _, k := range candidates(400) {
		if len(base) == 22 {
			break
		}
		base = append(base, k)
		t.put(k, 1)
	}
	fmt.Printf("  Исходное состояние: вставлено %d ключей (%s …), занято %d из 32 слотов,\n",
		len(base), strings.Join(base[:3], ", "), t.used)
	fmt.Printf("  запас роста %d. В каждом занятом слоте показана его метка — h2.\n\n", t.growthLeft)
	t.dump("  ")
	fmt.Println()

	// Собранные сценарии уезжают в блок 3 — данные для картинки.
	type shot struct {
		id    string
		title string
		base  *table
		key   string
		trace []step
	}
	var shots []shot

	// СЦЕНАРИЙ А: обычная вставка нового ключа.
	fresh := ""
	for _, k := range candidates(4000) {
		h := hash(k)
		g := int(h1(h) & t.mask)
		if matchEmpty(t.ctrl[g]) != 0 && matchH2(t.ctrl[g], h2(h)) == 0 && !contains(base, k) {
			fresh = k
			break
		}
	}
	w := t.clone()
	tr := w.put(fresh, 1)
	printTrace("СЦЕНАРИЙ А · новый ключ, в стартовой группе есть место", fresh, w, tr)
	shots = append(shots, shot{"plain", "новый ключ, в стартовой группе есть место", t, fresh, tr})

	// СЦЕНАРИЙ Б: ложное совпадение метки.
	falseHit := ""
	for _, k := range candidates(20000) {
		h := hash(k)
		g := int(h1(h) & t.mask)
		if matchH2(t.ctrl[g], h2(h)) != 0 && matchEmptyOrDeleted(t.ctrl[g]) != 0 && !contains(base, k) {
			falseHit = k
			break
		}
	}
	if falseHit != "" {
		w = t.clone()
		tr = w.put(falseHit, 1)
		printTrace("СЦЕНАРИЙ Б · метка совпала, а ключ чужой", falseHit, w, tr)
		shots = append(shots, shot{"falsehit", "метка совпала, а ключ чужой", t, falseHit, tr})
	}

	// СЦЕНАРИЙ В: повторная вставка существующего ключа.
	w = t.clone()
	tr = w.put(base[0], 42)
	printTrace("СЦЕНАРИЙ В · ключ уже есть: значение переписывается на месте", base[0], w, tr)
	shots = append(shots, shot{"update", "ключ уже есть: значение переписывается на месте", t, base[0], tr})

	// СЦЕНАРИЙ Г: стартовая группа занята целиком — путь идёт дальше.
	//
	// Первый заход брал первый попавшийся ключ, стартующий в полной группе, и
	// не проверял, нет ли такого ключа уже в таблице. Попался ключ, который в
	// ней лежал, — и вместо пути по группам напечаталось обновление на месте.
	// Отсюда условие `!inTable`: сценарий про путь, а не про совпадение.
	full := ""
	for _, k := range candidates(20000) {
		if contains(base, k) {
			continue
		}
		g := int(h1(hash(k)) & t.mask)
		if matchEmptyOrDeleted(t.ctrl[g]) == 0 {
			full = k
			break
		}
	}
	if full != "" {
		w = t.clone()
		tr = w.put(full, 1)
		printTrace("СЦЕНАРИЙ Г · стартовая группа занята целиком", full, w, tr)
		shots = append(shots, shot{"probe", "стартовая группа занята целиком", t, full, tr})
	}

	// СЦЕНАРИЙ Д: по дороге встретился удалённый слот.
	dt, dkey, dtrace := blockDeleted()
	shots = append(shots, shot{"deleted", "по дороге лежит удалённый слот", dt, dkey, dtrace})

	header(3, "ДАННЫЕ ДЛЯ КАРТИНКИ")
	fmt.Println("  Ровно то, что показывает MapInsert. Переносится в компонент как есть.")
	for _, sh := range shots {
		fmt.Printf("\n--- %s · %s\n", sh.id, sh.title)
		fmt.Println("  таблица до вставки:")
		fmt.Println(jsonSlots(sh.base))
		fmt.Println("  трасса:")
		fmt.Println(jsonTrace(sh.key, sh.base, sh.trace))
	}

	blockSelfCheck()
	blockAgainstRealMap()

	fmt.Println()
	fmt.Println("Все строки выше напечатаны этой программой. Правила — из go1.24.7:")
	fmt.Println("internal/runtime/maps/{map.go,table.go,group.go}.")
}

// blockDeleted строит расклад, в котором путь вставки ПРОХОДИТ через удалённый
// слот раньше, чем доходит до свободного. Только в таком раскладе видно правило
// из PutSlot: первый удалённый слот запоминается, но путь на нём не кончается.
//
// Расклад не рисуется байтами, а достигается настоящими вставками и удалением.
// Подобрать его пришлось по треугольному пути: из группы 1 он идёт
// 1 → 2 → 0 → 3. Значит, группы 1 и 0 должны быть полными, удалённый слот —
// в группе 2, а свободный — только в группе 3.
//
// Первый заход этого не учёл: ключ стартовал в группе 0, путь пошёл 0 → 1 → 3,
// и группу 2 с удалённым слотом просто миновал. Трасса получалась верной, но
// показывала не то правило, ради которого написана.
func blockDeleted() (*table, string, []step) {
	t := newTable(4)

	byGroup := map[int][]string{}
	for _, k := range candidates(6000) {
		g := int(h1(hash(k)) & t.mask)
		byGroup[g] = append(byGroup[g], k)
	}

	// Группы 1 и 0 — под завязку, группа 2 — под завязку и потом одно удаление,
	// в группе 3 остаётся свободное место.
	var placed []string
	fill := func(g, n int) []string {
		var got []string
		for _, k := range byGroup[g] {
			if len(got) == n {
				break
			}
			if int(h1(hash(k))&t.mask) != g {
				continue
			}
			t.put(k, 1)
			got = append(got, k)
			placed = append(placed, k)
		}
		return got
	}
	fill(0, 8)
	fill(1, 8)
	inTwo := fill(2, 8)
	fill(3, 2)

	fmt.Println("  СЦЕНАРИЙ Д · по дороге лежит удалённый слот")
	fmt.Println()
	fmt.Println("    Состояние построено вставками и удалением, а не расстановкой байтов.")
	fmt.Printf("    Группы 0, 1 и 2 заполнены целиком; в группе 2 удаляется ключ %q.\n", inTwo[3])
	t.del(inTwo[3])
	fmt.Println()
	t.dump("    ")
	fmt.Println()
	fmt.Println("    Удалённый слот помечен «удал», а не «····»: группа была полной, и")
	fmt.Println("    пометить слот свободным нельзя — это оборвало бы чужие пути поиска.")
	fmt.Println("    Свободные слоты остались только в группе 3.")
	fmt.Println()

	// Ключ, стартующий в группе 1: треугольный путь ведёт 1 → 2 → 0 → 3, то есть
	// удалённый слот встретится раньше свободного.
	target := ""
	for _, k := range byGroup[1] {
		if !contains(placed, k) && int(h1(hash(k))&t.mask) == 1 {
			target = k
			break
		}
	}
	before := t.clone()
	tr := t.put(target, 1)
	printTrace("вставка ключа, стартующего в полной группе 1", target, t, tr)
	fmt.Println("    Освободившееся место переиспользовано, и запас роста на него не потрачен.")
	fmt.Println()
	t.dump("    ")
	fmt.Println()
	return before, target, tr
}