📐 Thorsten Ball

// Промпт Thorsten-стиля для добавления узла в AST

/*
Вот структура AST узла:
type Node struct {
    Type     NodeType
    Children []*Node
    Parent   *Node   // nil только для root
    Value    string
}

Инварианты системы (должны соблюдаться ВСЕГДА):
1. node.Parent != nil для всех узлов кроме root
2. Если A.Children содержит B, то B.Parent == A
3. Никаких циклических ссылок в дереве

Задача: реализуй функцию AddChild(parent, child *Node).
Реализация должна обеспечивать выполнение всех трёх инвариантов.
*/

// То что CC сгенерирует — корректное по определению:
func AddChild(parent, child *Node) error {
    if parent == nil {
        return errors.New("parent cannot be nil")
    }
    if child == nil {
        return errors.New("child cannot be nil")
    }
    // Проверка на цикл (инвариант 3)
    if isAncestor(child, parent) {
        return errors.New("adding child would create a cycle")
    }
    // Обновляем parent ссылку (инвариант 1 и 2)
    if child.Parent != nil {
        // Убираем из предыдущего parent
        child.Parent.removeChild(child)
    }
    child.Parent = parent
    parent.Children = append(parent.Children, child)
    return nil
}

// CC вывел этот код потому что знал инвариант 2 и 3 —
// а не потому что мы сказали "обнови Parent поле"

// Плохо: CC напишет код который может передать неправильный тип
function processPayment(amount: number, currency: string) { ... }
processPayment(100, "XYZ");  // компилятор пропустит, но бизнес-логика сломается

// Хорошо: инвариант "валюта должна быть из известного списка" — в типах
type SupportedCurrency = "RUB" | "USD" | "EUR";

function processPayment(amount: number, currency: SupportedCurrency) { ... }
// processPayment(100, "XYZ");  // TypeScript ERROR: "XYZ" не входит в тип
// CC не сможет передать невалидную валюту — компилятор не даст

// Инвариант "ID не перепутать" через брендированные типы
type UserId = number & { readonly __brand: "UserId" };
type OrderId = number & { readonly __brand: "OrderId" };

function getUser(id: UserId): User { ... }
// getUser(orderId);  // TypeScript ERROR: OrderId !== UserId
// CC случайно не перепутает ID разных сущностей

# Промпт Thorsten-стиля для алгоритмической задачи

"Вот определение структуры данных:

type BTree struct {
    root *BTreeNode
    order int  // максимальное количество ключей в узле
}

type BTreeNode struct {
    keys     []int
    children []*BTreeNode
    isLeaf   bool
}

Инварианты B-дерева (должны соблюдаться после каждой операции):
1. Каждый узел имеет не более (order) ключей
2. Каждый не-root узел имеет не менее (order/2) ключей
3. Все листовые узлы на одной глубине
4. Для каждого ключа k в узле: все ключи в левом поддереве < k < все ключи в правом поддереве

Реализуй операцию Insert(key int) с временной сложностью O(log n).
При реализации сохраняй все 4 инварианта.
Если вставка нарушает инвариант 1 — делай split узла."

# CC теперь знает:
# - что такое инвариант для этой структуры
# - какая требуемая сложность
# - когда нужен split
# Результат будет корректным по определению инвариантов

// Результат CC на основе инвариантного промпта
func (t *BTree) Insert(key int) {
    if t.root == nil {
        t.root = &BTreeNode{keys: []int{key}, isLeaf: true}
        return
    }

    // Если root переполнен — сначала split (инвариант 1)
    if len(t.root.keys) == t.order {
        newRoot := &BTreeNode{isLeaf: false}
        newRoot.children = append(newRoot.children, t.root)
        t.splitChild(newRoot, 0)
        t.root = newRoot
    }

    t.insertNonFull(t.root, key)
}

func (t *BTree) insertNonFull(node *BTreeNode, key int) {
    i := len(node.keys) - 1

    if node.isLeaf {
        // Вставляем в отсортированной позиции (инвариант 4)
        node.keys = append(node.keys, 0)
        for i >= 0 && key < node.keys[i] {
            node.keys[i+1] = node.keys[i]
            i--
        }
        node.keys[i+1] = key
        return
    }

    // Находим нужное поддерево (инвариант 4)
    for i >= 0 && key < node.keys[i] {
        i--
    }
    i++

    // Если дочерний узел переполнен — split перед спуском (инвариант 1)
    if len(node.children[i].keys) == t.order {
        t.splitChild(node, i)
        if key > node.keys[i] {
            i++
        }
    }
    t.insertNonFull(node.children[i], key)
}

// Тест написан CC после реализации Insert
func TestBTreeInsert_MaintainsInvariant1(t *testing.T) {
    tree := NewBTree(3) // order = 3, max 3 ключа в узле

    // Вставить больше ключей чем влезет в один узел
    for i := 1; i <= 10; i++ {
        tree.Insert(i)
    }

    // Проверяем инвариант 1: ни один узел не переполнен
    assertNoNodeExceedsOrder(t, tree.root, tree.order)
}

// Thorsten добавляет: ВРЕМЕННО ломаем реализацию
// func (t *BTree) Insert(key int) {
//     // Намеренно убираем проверку на переполнение root
//     // if len(t.root.keys) == t.order { ... split ... }
//     t.insertNonFull(t.root, key)  // без split → инвариант 1 нарушится
// }
//
// Запускаем: go test -run TestBTreeInsert_MaintainsInvariant1
// ОЖИДАЕМ: FAIL — "node has 4 keys, exceeds order 3"
// ПОЛУЧАЕМ: FAIL ✓ → тест работает
//
// Возвращаем реализацию → PASS ✓

func assertNoNodeExceedsOrder(t *testing.T, node *BTreeNode, order int) {
    t.Helper()
    if node == nil {
        return
    }
    if len(node.keys) > order {
        t.Errorf("node has %d keys, exceeds order %d", len(node.keys), order)
    }
    for _, child := range node.children {
        assertNoNodeExceedsOrder(t, child, order)
    }
}

# Из книги Thorsten: строим лексер поэтапно

# Шаг 1: базовый токенизатор
"Реализуй Lexer который разбивает строку на токены.
 Пока только: числа (INTEGER) и операторы (+, -, *, /).
 Игнорируй пробелы.
 Напиши тест для: '3 + 4 * 2'."

# [тест проходит] → переходим к шагу 2

# Шаг 2: добавить идентификаторы
"Лексер работает для чисел и операторов.
 Добавь: идентификаторы (letters + digits, starts with letter).
 Ключевые слова: 'let', 'fn', 'return' — отдельные TokenType.
 Добавь тест для: 'let x = 5 + y'."

# [тест проходит] → переходим к шагу 3

# Шаг 3: строки и escaping
"Лексер работает для чисел, операторов, идентификаторов.
 Добавь: строковые литералы в двойных кавычках.
 Обработай: \" (escape кавычка внутри строки), \n, \t.
 Добавь тест для: 'let s = \"hello\\nworld\"'."

# Каждый шаг атомарный — можно откатить если что-то пошло не так
# CC никогда не получает "сделай весь лексер с нуля"

package btree

// BTreeNode представляет узел B-дерева.
//
// ИНВАРИАНТЫ (всегда истинно для корректного дерева):
//   - len(keys) <= order для каждого узла
//   - len(keys) >= order/2 для не-root не-leaf узлов
//   - len(children) == len(keys)+1 для внутренних узлов
//   - len(children) == 0 для leaf узлов
//   - keys отсортированы по возрастанию
type BTreeNode struct {
    keys     []int
    children []*BTreeNode
    isLeaf   bool
}

// verify проверяет все инварианты узла в debug-режиме.
// Вызывается только в тестах и при -race флаге.
func (n *BTreeNode) verify(order int) error {
    if len(n.keys) > order {
        return fmt.Errorf("invariant violated: node has %d keys, max %d",
            len(n.keys), order)
    }
    if !n.isLeaf && len(n.children) != len(n.keys)+1 {
        return fmt.Errorf("invariant violated: internal node has %d children for %d keys",
            len(n.children), len(n.keys))
    }
    for i := 1; i < len(n.keys); i++ {
        if n.keys[i] <= n.keys[i-1] {
            return fmt.Errorf("invariant violated: keys not sorted at position %d", i)
        }
    }
    return nil
}

// Insert добавляет ключ сохраняя все инварианты B-дерева.
//
// POST-CONDITION: после Insert:
//   - key присутствует в дереве (Search(key) == true)
//   - все инварианты BTreeNode сохранены
//   - высота дерева не уменьшилась
func (t *BTree) Insert(key int) {
    // ... реализация ...

    // В тестах: проверяем post-condition
    if isTestMode() {
        if err := t.root.verify(t.order); err != nil {
            panic(fmt.Sprintf("Insert broke invariant: %v", err))
        }
    }
}