Команда Go for Devs подготовила перевод статьи Акселя Вагнера о том, как generic интерфейсы в Go открывают новые возможности и новые сложности. В статье разбираются паттерны, ограничения и компромиссы: от self reference интерфейсов до дилеммы с ресивер-указателями.

Есть одна идея, которая не приходит в голову, пока впервые о ней не услышишь: так как интерфейсы сами по себе являются типами, у них тоже могут быть параметризованные типы. Эта мысль оказывается удивительно мощной, когда речь идёт о выражении ограничений для generic функций и типов. В этом посте мы разберём её на практике, показав, как использовать интерфейсы с параметрами типа в нескольких распространённых сценариях.

Простой TreeSet

В качестве примера предположим, что нам нужна generic версия бинарного дерева поиска. Элементы, которые хранятся в таком дереве, должны быть упорядоченными, поэтому для параметра типа необходимо задать ограничение, определяющее способ сравнения. Простейший вариант — использовать ограничение cmp.Ordered, добавленное в Go 1.21. Оно ограничивает параметр типа упорядоченными типами (строки и числа) и позволяет методам такого типа использовать встроенные операторы сравнения.

// The zero value of a Tree is a ready-to-use empty tree.
type Tree[E cmp.Ordered] struct {
    root *node[E]
}

func (t *Tree[E]) Insert(element E) {
    t.root = t.root.insert(element)
}

type node[E cmp.Ordered] struct {
    value E
    left  *node[E]
    right *node[E]
}

func (n *node[E]) insert(element E) *node[E] {
    if n == nil {
        return &node[E]{value: element}
    }
    switch {
    case element < n.value:
        n.left = n.left.insert(element)
    case element > n.value:
        n.right = n.right.insert(element)
    }
    return n
}

(песочница)

Однако у такого подхода есть минус: он работает только для базовых типов, для которых определён оператор <; вы не сможете вставлять struct-типы, такие как time.Time.

Это можно исправить, если заставить пользователя передать функцию сравнения:

// A FuncTree must be created with NewTreeFunc.
type FuncTree[E any] struct {
    root *funcNode[E]
    cmp  func(E, E) int
}

func NewFuncTree[E any](cmp func(E, E) int) *FuncTree[E] {
    return &FuncTree[E]{cmp: cmp}
}

func (t *FuncTree[E]) Insert(element E) {
    t.root = t.root.insert(t.cmp, element)
}

type funcNode[E any] struct {
    value E
    left  *funcNode[E]
    right *funcNode[E]
}

func (n *funcNode[E]) insert(cmp func(E, E) int, element E) *funcNode[E] {
    if n == nil {
        return &funcNode[E]{value: element}
    }
    sign := cmp(element, n.value)
    switch {
    case sign < 0:
        n.left = n.left.insert(cmp, element)
    case sign > 0:
        n.right = n.right.insert(cmp, element)
    }
    return n
}

(песочница)

Это работает, но тоже имеет свои недостатки. Мы больше не можем использовать нулевое значение нашего контейнера, потому что ему нужна явно инициализированная функция сравнения. А наличие поля-функции усложняет компилятору встраивание вызовов сравнения, что может привести к заметным накладным расходам во время выполнения.

Использование метода у типа элемента решает эти проблемы, поскольку методы непосредственно связаны с типом. Метод не нужно передавать явно, и компилятор видит, какой именно вызов выполняется, и может его встроить. Но как выразить ограничение так, чтобы требовать от типов элементов наличия нужного метода?

Использование ресивера в ограничениях

Первое, что приходит в голову, — определить обычный интерфейс с методом Compare:

type Comparer interface {
    Compare(Comparer) int
}

Однако быстро становится ясно, что это плохо работает. Чтобы реализовать такой интерфейс, параметр метода сам должен быть типа Comparer. Это означает не только то, что в реализации метода придётся приводить параметр к собственному типу (type assertion), но и то, что каждому типу придётся явно ссылаться на наш пакет и упоминать по имени тип Comparer (иначе сигнатуры методов не совпадут). Это не слишком ортогонально.

Лучше сделать сам интерфейс Comparer generic:

type Comparer[T any] interface {
    Compare(T) int
}

Теперь Comparer описывает целое семейство интерфейсов — по одному для каждого типа, с которым можно создать Comparer. Тип, реализующий Comparer[T], тем самым заявляет: «я могу сравнивать себя с T». Например, time.Time естественным образом реализует Comparer[time.Time], потому что у него есть подходящий метод Compare:

// Implements Comparer[Time]
func (t Time) Compare(u Time) int

Это лучше, но всё ещё не идеально. На самом деле нам нужно ограничение, которое говорит, что параметр типа можно сравнивать сам с собой: ограничение должно быть самореферентным. Важный нюанс: самореферентность не обязана быть частью определения интерфейса как такового; конкретно, ограничение для T в типе Comparer — просто any. Вместо этого самореферентность возникает из того, как мы используем Comparer в качестве ограничения для параметра типа MethodTree:

// The zero value of a MethodTree is a ready-to-use empty tree.
type MethodTree[E Comparer[E]] struct {
    root *methodNode[E]
}

func (t *MethodTree[E]) Insert(element E) {
    t.root = t.root.insert(element)
}

type methodNode[E Comparer[E]] struct {
    value E
    left  *methodNode[E]
    right *methodNode[E]
}

func (n *methodNode[E]) insert(element E) *methodNode[E] {
    if n == nil {
        return &methodNode[E]{value: element}
    }
    sign := element.Compare(n.value)
    switch {
    case sign < 0:
        n.left = n.left.insert(element)
    case sign > 0:
        n.right = n.right.insert(element)
    }
    return n
}

(песочница)

Поскольку time.Time реализует Comparer[time.Time], он теперь подходит как аргумент типа для этого контейнера, и мы по-прежнему можем использовать нулевое значение как пустой контейнер:

var t MethodTree[time.Time]
t.Insert(time.Now())

Для полной гибкости библиотека может предоставить все три варианта API. Чтобы не дублировать код, все версии могут пользоваться общей реализацией. В качестве таковой можно взять функциональный вариант — он самый общий:

type node[E any] struct {
    value E
    left  *node[E]
    right *node[E]
}

func (n *node[E]) insert(cmp func(E, E) int, element E) *node[E] {
    if n == nil {
        return &node[E]{value: element}
    }
    sign := cmp(element, n.value)
    switch {
    case sign < 0:
        n.left = n.left.insert(cmp, element)
    case sign > 0:
        n.right = n.right.insert(cmp, element)
    }
    return n
}

// Insert inserts element into the tree, if E implements cmp.Ordered.
func (t *Tree[E]) Insert(element E) {
    t.root = t.root.insert(cmp.Compare[E], element)
}

// Insert inserts element into the tree, using the provided comparison function.
func (t *FuncTree[E]) Insert(element E) {
    t.root = t.root.insert(t.cmp, element)
}

// Insert inserts element into the tree, if E implements Comparer[E].
func (t *MethodTree[E]) Insert(element E) {
    t.root = t.root.insert(E.Compare, element)
}

(песочница)

Важно отметить, что общая реализация (вариант на функциях) никак не ограничивается. Она должна оставаться максимально гибкой, чтобы служить общим ядром. Мы также не храним функцию сравнения в поле структуры. Вместо этого передаём её параметром, потому что аргументы функций компилятору было проще анализировать, чем поля структур.

Разумеется, некоторый шаблонный код всё равно останется: всем экспортируемым реализациям придётся повторить полный API с немного разными способами вызова. Но эта часть проста и для написания, и для чтения.

Комбинирование методов и множеств типов

Мы можем использовать нашу новую структуру дерева, чтобы реализовать упорядоченное множество с поиском элемента за логарифмическое время. Теперь представим, что нам нужен поиск за константное время; можно попытаться добиться этого, ведя обычную map параллельно с деревом:

type OrderedSet[E Comparer[E]] struct {
    tree     MethodTree[E] // for efficient iteration in order
    elements map[E]bool    // for (near) constant time lookup
}

func (s *OrderedSet[E]) Has(e E) bool {
    return s.elements[e]
}

func (s *OrderedSet[E]) Insert(e E) {
    if s.elements == nil {
        s.elements = make(map[E]bool)
    }
    if s.elements[e] {
        return
    }
    s.elements[e] = true
    s.tree.Insert(e)
}

func (s *OrderedSet[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        s.tree.root.all(yield)
    }
}

func (n *node[E]) all(yield func(E) bool) bool {
    return n == nil || (n.left.all(yield) && yield(n.value) && n.right.all(yield))
}

(песочница)

Однако при компиляции этого кода мы получим ошибку:

invalid map key type E (missing comparable constraint)

Из сообщения следует, что нам нужно дополнительно ограничить параметр типа, чтобы его можно было использовать в качестве ключа map. Ограничение comparable — это специальное предопределённое ограничение, которому удовлетворяют все типы, для которых определены операторы равенства == и !=. В Go это также множество типов, которые можно использовать как ключи встроенного типа map.

Есть три способа добавить это ограничение к нашему параметру типа — у каждого свои компромиссы:

Первый: можно встроить comparable в изначальное определение Comparer (песочница):

type Comparer[E any] interface {
    comparable
    Compare(E) int
}

У этого подхода есть минус – он сделает наши типы Tree пригодными только для типов, удовлетворяющих comparable. В целом мы не хотим лишний раз сужать generic типы.

Второй: можно ввести новое определение ограничения (песочница).

type Comparer[E any] interface {
    Compare(E) int
}

type ComparableComparer[E any] interface {
    comparable
    Comparer[E]
}

Выглядит лаконично, но добавляет новый идентификатор (ComparableComparer) в наш API. Получается сложновато с названием.

Третий: можно добавить ограничение inline в более строгий тип (песочница):

type OrderedSet[E interface {
    comparable
    Comparer[E]
}] struct {
    tree     Tree[E]
    elements map[E]struct{}
}

Такой код может быть труднее читать, особенно если это приходится делать часто. К тому же так сложнее переиспользовать ограничение в других местах.

Какой вариант выбрать — вопрос стиля и в итоге дело личных предпочтений.

(Не) накладывая ограничения на generic интерфейсы

На этом этапе стоит обсудить ограничения для generic интерфейсов. Возможно, вы захотите определить интерфейс для generic типа контейнера. Например, у вас есть алгоритм, которому требуется структура данных «множество». Существует множество реализаций множеств с разными компромиссами. Определив интерфейс для нужных вам операций над множеством, вы добавляете гибкость своему пакету, оставляя пользователю право выбрать, какие компромиссы подходят его конкретному приложению:

type Set[E any] interface {
    Insert(E)
    Delete(E)
    Has(E) bool
    All() iter.Seq[E]
}

Естественный вопрос здесь — каким должно быть ограничение у этого интерфейса. По возможности параметры типа в generic интерфейсах должны использовать any как ограничение, разрешая произвольные типы.

Исходя из сказанного выше, причины очевидны: разные конкретные реализации могут требовать разных ограничений. Все рассмотренные нами ранее типы Tree, а также тип OrderedSet, могут реализовать Set для своих типов элементов, хотя у этих типов разные ограничения.

Смысл определения интерфейса — предоставить реализацию на усмотрение пользователя. Поскольку невозможно предсказать, какие ограничения захочет наложить пользователь на свою реализацию, старайтесь оставлять любые ограничения (строже, чем any) конкретным реализациям, а не интерфейсам.

Ресивер-указатель

Попробуем использовать интерфейс Set в примере. Рассмотрим функцию, которая удаляет дубликаты из последовательности:

// Unique удаляет дублирующиеся элементы из входной последовательности,
// выдавая только первое вхождение каждого элемента.
func Unique[E comparable](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        seen := make(map[E]bool)
        for v := range input {
            if seen[v] {
                continue
            }
            if !yield(v) {
                return
            }
            seen[v] = true
        }
    }
}

(песочница)

Здесь в роли простого множества элементов типа E используется map[E]bool. Соответственно, это работает только для типов, которые сравнимы и для которых определены встроенные операторы равенства. Если мы хотим generic решение на произвольные типы, нужно заменить map на generic множество:

// Unique удаляет дублирующиеся элементы из входной последовательности,
// выдавая только первое вхождение каждого элемента.
func Unique[E any](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        var seen Set[E]
        for v := range input {
            if seen.Has(v) {
                continue
            }
            if !yield(v) {
                return
            }
            seen.Insert(v)
        }
    }
}

(песочница)

Однако это не работает. Set[E] — интерфейсный тип, и переменная seen будет инициализирована значением nil. Нам нужна конкретная реализация интерфейса Set[E]. Но, как мы уже видели в этой статье, не существует общей реализации множества, которая подошла бы для любого типа элементов.

Нам придётся попросить пользователя передать конкретную реализацию, которую мы сможем использовать, как дополнительный параметр типа:

// Unique удаляет дублирующиеся элементы из входной последовательности,
// выдавая только первое вхождение каждого элемента.
func Unique[E any, S Set[E]](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        var seen S
        for v := range input {
            if seen.Has(v) {
                continue
            }
            if !yield(v) {
                return
            }
            seen.Insert(v)
        }
    }
}

(песочница)

Но если инстанцировать это нашей реализацией множества, мы столкнёмся с ещё одной проблемой:

// OrderedSet[E] does not satisfy Set[E] (method All has pointer receiver)
Unique[E, OrderedSet[E]](slices.Values(s))
// panic: invalid memory address or nil pointer dereference
Unique[E, *OrderedSet[E]](slices.Values(s))

Первая проблема очевидна из сообщения об ошибке: наше ограничение требует, чтобы аргумент типа Sреализовывал интерфейс Set[E]. Поскольку методы OrderedSet используют ресивер-указатели, аргументом типа должен быть также указательный тип.

Попытавшись сделать так, мы упираемся во вторую проблему. Она возникает из-за того, что в реализации мы объявляем переменную:

var seen S

Если S — это *OrderedSet[E], переменная, как и раньше, инициализируется nil. Вызов seen.Insert приводит к панике.

Если у нас есть только указательный тип, мы не можем получить валидную переменную значимого (value) типа. А если есть только значимый тип, мы не можем вызывать методы с ресивер-указателем. Следствие: нам нужны и значимый, и указательный тип. Значит, придётся ввести дополнительный параметр типа PS с новым ограничением PtrToSet.

// PtrToSet реализуется указательным типом, который реализует интерфейс Set[E].
type PtrToSet[S, E any] interface {
    *S
    Set[E]
}

// Unique удаляет дублирующиеся элементы из входной последовательности,
// выдавая только первое вхождение каждого элемента.
func Unique[E, S any, PS PtrToSet[S, E]](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        // We convert to PS, as only that is constrained to have the methods.
        // The conversion is allowed, because the type set of PS only contains *S.
        seen := PS(new(S))
        for v := range input {
            if seen.Has(v) {
                continue
            }
            if !yield(v) {
                return
            }
            seen.Insert(v)
        }
    }
}

(песочница)

Хитрость здесь — в связывании двух параметров типов в сигнатуре функции через дополнительный параметр типа в интерфейсе PtrToSet. Сам S не имеет ограничений, но PS обязан иметь тип *S и содержать нужные нам методы. По сути, мы накладываем на S требование иметь определённые методы, причём эти методы должны использовать получатель-указатель.

Хотя определение функции с таким ограничением требует дополнительного параметра типа, важно, что это не усложняет код, который её использует: пока этот дополнительный параметр стоит в конце списка параметров типа, его можно вывести автоматически:

// Третий аргумент типа выводится как *OrderedSet[int]
Unique[int, OrderedSet[int]](slices.Values(s))

Это общий паттерн, который стоит запомнить — пригодится и при чтении чужого кода, и в собственных разработках.

func SomeFunction[T any, PT interface{ *T; SomeMethods }]()

Если у вас есть два параметра типа, и один из них ограничен быть указателем на другой, такое ограничение гарантирует, что соответствующие методы используют ресивер-указатель.

Следует ли ограничивать ресивер-указатели?

На этом этапе вы можете чувствовать себя перегруженными. Всё выглядит довольно сложно, и неразумно ожидать, что каждый Go-программист будет разбираться в том, что происходит в этой сигнатуре функции. Нам также пришлось ввести ещё больше имён в наш API. Когда в самом начале предостерегали от добавления generic в Go, именно подобных вещей многие и опасались.

Поэтому, если вы запутались в подобных проблемах, стоит сделать шаг назад. Часто мы можем избежать этой сложности, если по-другому посмотреть на задачу. В нашем примере мы написали функцию, которая принимает iter.Seq[E] и возвращает iter.Seq[E] только с уникальными элементами. Но чтобы убрать дубликаты, нам понадобилось собрать уникальные элементы в множество. А раз для этого нужно выделить память под весь результат целиком, реальной выгоды от представления результата в виде потока мы не получаем.

Если переосмыслить задачу, можно вовсе избежать дополнительного параметра типа, используя Set[E] как обычное значение интерфейсного типа:

// InsertAll добавляет в set все уникальные элементы из seq.
func InsertAll[E any](set Set[E], seq iter.Seq[E]) {
    for v := range seq {
        set.Insert(v)
    }
}

(песочница)

Используя Set как обычный интерфейсный тип, мы явно даём понять, что вызывающий должен передать корректное значение своей конкретной реализации. Это очень распространённый паттерн. А если ему нужен iter.Seq[E], он может просто вызвать All() у множества и получить его.

Это немного усложняет жизнь вызвавшему код, но у такого подхода есть ещё одно преимущество по сравнению с ограничением на ресивер-указатели: вспомните, что мы начинали с map[E]bool как простого типа множества. На этой основе легко реализовать интерфейс Set[E]:

type HashSet[E comparable] map[E]bool

func (s HashSet[E]) Insert(v E)       { s[v] = true }
func (s HashSet[E]) Delete(v E)       { delete(s, v) }
func (s HashSet[E]) Has(v E) bool     { return s[v] }
func (s HashSet[E]) All() iter.Seq[E] { return maps.Keys(s) }

(песочница)

В этой реализации не используются ресивер-указатели. Так что, хотя она вполне корректна, она была бы непригодна при сложном ограничении на ресивер-указатели. Зато отлично работает с нашей версией InsertAll. Как и со многими другими ограничениями, требование использовать ресивер-указатели может оказаться чрезмерно жёстким для многих практических сценариев.

Русскоязычное GO сообщество

Друзья! Эту статью перевела команда «Go for Devs» — сообщества, где мы делимся практическими кейсами, инструментами для разработчиков и свежими новостями из мира Go. Подписывайтесь, чтобы быть в курсе и ничего не упустить!

Заключение

Надеюсь, это помогло показать некоторые паттерны и компромиссы, которые открывают параметры типов в интерфейсах. Это мощный инструмент, но у него есть и цена. Основные выводы:

• Используйте generic интерфейсы, чтобы выражать ограничения на получателя через self reference.

• Применяйте их для создания связанных ограничений между разными параметрами типов.

• Используйте их, чтобы абстрагироваться от разных реализаций с различными типами ограничений.

• Если вы оказались в ситуации, когда нужно накладывать ограничение на получателей-указателей, подумайте, можно ли переписать код так, чтобы избежать лишней сложности.

И как всегда — не переусложняйте: менее гибкое, но более простое и читаемое решение в итоге может оказаться самым разумным выбором.