Generic интерфейсы в Go: просто, но сложно

Команда 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.

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

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

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

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