Generics

Generics, ou nome mais acadêmico — Polimorfismo Parametrizado (Parameterized Polymorphism), refere-se à realização de reutilização e flexibilidade de código através da parametrização de tipos. Em muitas linguagens de programação, o polimorfismo parametrizado é um conceito importante que permite que funções ou estruturas de dados processem diferentes tipos de dados sem a necessidade de escrever código separado para cada tipo. Originalmente Go não tinha o conceito de generics, mas desde seu nascimento, o pedido mais alto da comunidade sobre Go era adicionar generics. Finalmente, em 2022, a linguagem Go adicionou suporte a generics na versão 1.18.

Design

Quando a linguagem Go projetou generics, considerou os seguintes esquemas

• stenciling: Monomorfização, tipicamente como C++, Rust, que gera um código de modelo para cada tipo usado. O desempenho deste método é o melhor, sem nenhuma sobrecarga em tempo de execução, o desempenho é igual à chamada direta. A desvantagem é que desacelera drasticamente a velocidade de compilação (comparado ao próprio Go), e como é gerado código para cada tipo, também causa inchaço no volume do arquivo binário compilado.
• dictionaries: Gera apenas um conjunto de código e, ao mesmo tempo, gera um dicionário de tipos armazenado na seção de dados somente leitura durante a compilação. Ele armazena todas as informações de tipo que serão usadas. Ao chamar funções, consulta as informações de tipo com base no dicionário. Este método não desacelera a velocidade de compilação e não causa inchaço de volume, mas causa enorme sobrecarga em tempo de execução, e o desempenho dos generics é muito ruim.

Os dois métodos acima representam dois extremos. O esquema de implementação finalmente escolhido pela linguagem Go é Gcshape stenciling, que é uma escolha de compromisso. Para tipos com a mesma forma de memória (a forma é determinada pelo alocador de memória), usa monomorfização, gerando o mesmo código para eles. Por exemplo, type Int int e int são essencialmente o mesmo tipo, então compartilham um conjunto de código. Mas para ponteiros, embora todos os tipos de ponteiro tenham a mesma forma de memória, como *int, *Person são todos da mesma forma de memória, eles não podem compartilhar um conjunto de código, porque ao desreferenciar, o layout de memória do tipo alvo da operação é completamente diferente. Para isso, Go também usa dicionários para obter informações de tipo em tempo de execução, então os generics de Go também têm sobrecarga em tempo de execução.

Introdução

Primeiro, vamos ver um exemplo simples.

func Sum(a, b int) int {
   return a + b
}

Esta é uma função com funcionalidade muito simples, que soma dois inteiros do tipo int e retorna o resultado. Se quiser passar dois números de ponto flutuante do tipo float64 para soma, obviamente não é possível, porque os tipos não correspondem. Uma solução é definir uma nova função, como abaixo

func SumFloat64(a, b float64) float64 {
  return a + b
}

Então a questão é, se estiver desenvolvendo um pacote de ferramentas matemáticas para calcular a soma de dois números de todos os tipos numéricos, precisa escrever uma função para cada tipo? Obviamente isso não é muito possível, ou pode usar o tipo any mais reflexão para julgar, como abaixo

func SumAny(a, b any) (any, error) {
  tA, tB := reflect.ValueOf(a), reflect.ValueOf(b)
  if tA.Kind() != tB.Kind() {
    return nil, errors.New("disMatch type")
  }

  switch tA.Kind() {
  case reflect.Int:
  case reflect.Int32:
    ...
  }
}

Mas escrever assim é muito tedioso e o desempenho é baixo. Mas a lógica da função Sum é exatamente a mesma, apenas soma dois números. Neste momento, precisa-se usar generics. Então por que precisa de generics, generics são para resolver problemas onde a lógica de execução é independente do tipo, este tipo de problema não se importa com qual tipo é dado, apenas precisa completar a operação correspondente.

Sintaxe

A escrita de generics é a seguinte

func Sum[T int | float64](a, b T) T {
   return a + b
}

Parâmetro de tipo formal: T é um parâmetro de tipo formal, qual tipo específico o parâmetro formal é depende de qual tipo é passado

Restrição de tipo: int | float64 constitui uma restrição de tipo, esta restrição de tipo especifica quais tipos são permitidos, restringindo o intervalo de tipos do parâmetro de tipo formal

Argumento de tipo: Sum[int](1,2), especifica manualmente o tipo int, int é o argumento de tipo.

Primeiro uso, especificar explicitamente qual tipo usar, como abaixo

Sum[int](2012, 2022)

Segundo uso, não especificar o tipo, deixar o compilador inferir por si mesmo, como abaixo

Sum(3.1415926, 1.114514)

Este é um slice genérico, a restrição de tipo é int | int32 | int64

type GenericSlice[T int | int32 | int64] []T

Aqui ao usar não se pode omitir o argumento de tipo

GenericSlice[int]{1, 2, 3}

Este é uma tabela hash genérica, o tipo da chave deve ser comparável, então usa a interface comparable, a restrição de tipo do valor é V int | string | byte

type GenericMap[K comparable, V int | string | byte] map[K]V

Uso

gmap1 := GenericMap[int, string]{1: "hello world"}
gmap2 := make(GenericMap[string, byte], 0)

Este é uma struct genérica, a restrição de tipo é T int | string

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

Uso

GenericStruct[int]{
   Name: "jack",
   Id:   1024,
}
GenericStruct[string]{
   Name: "Mike",
   Id:   "1024",
}

Este é um exemplo de parâmetro formal de slice genérico

type Company[T int | string, S []T] struct {
   Name  string
   Id    T
   Stuff S
}

// também pode ser como abaixo
type Company[T int | string, S []int | []string] struct {
  Name  string
  Id    T
  Stuff S
}

Uso

Company[int, []int]{
   Name:  "lili",
   Id:    1,
   Stuff: []int{1},
}

TIP

Em structs genéricas, é mais recomendada esta escrita

type Company[T int | string, S int | string] struct {
  Name  string
  Id    T
  Stuff []S
}

SayAble é uma interface genérica, Person implementa esta interface.

type SayAble[T int | string] interface {
   Say() T
}

type Person[T int | string] struct {
   msg T
}

func (p Person[T]) Say() T {
   return p.msg
}

func main() {
  var s SayAble[string]
  s = Person[string]{"hello world"}
  fmt.Println(s.Say())
}

Interface Genérica

Interfaces genéricas podem fornecer melhor capacidade de abstração e restrição, abaixo está um exemplo

func PrintObj[T fmt.Stringer](s T) {
	fmt.Println(s.String())
}

type Person struct {
	Name string
}

func (p Person) String() string {
	return fmt.Sprintf("Person: %s", p.Name)
}

func main() {
	PrintObj(Person{Name: "Alice"})
}

Também pode usar interfaces não genéricas como parâmetro de tipo formal genérico

func Write[W io.Writer](w W, bs []byte) (int, error) {
	return w.Write(bs)
}

Asserção de Tipo Genérica

Podemos usar generics para fazer asserção de tipo em tipos any, por exemplo, a função abaixo pode asserir todos os tipos.

func Assert[T any](v any) (bool, T) {
	var av T
	if v == nil {
		return false, av
	}
	av, ok := v.(T)
	return ok, av
}

Conjunto de Tipos

Após a versão 1.18, a definição de interface mudou para conjunto de tipos (type set), interfaces contendo conjunto de tipos também são chamadas de General interfaces ou interfaces gerais.

An interface type defines a type set

Conjunto de tipos só pode ser usado para restrições de tipo em generics, não pode ser usado para declaração de tipo, conversão de tipo, asserção de tipo. Como um conjunto, o conjunto de tipos terá conjunto vazio, união, interseção, a seguir serão explicados estes três casos.

União

O tipo de interface SignedInt é um conjunto de tipos, a união dos tipos inteiros com sinal é SignedInt, inversamente SignedInt é o superconjunto deles.

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

Tipos de dados básicos são assim, o mesmo vale para outras interfaces gerais

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnSignedInt interface {
  uint8 | uint16 | uint32 | uint64
}

type Integer interface {
  SignedInt | UnSignedInt
}

Interseção

O conjunto de tipos de uma interface não vazia é a interseção dos conjuntos de tipos de todos os seus elementos. Traduzindo em linguagem humana: se uma interface contém múltiplos conjuntos de tipos não vazios, então esta interface é a interseção desses conjuntos de tipos. Exemplo abaixo

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

type Integer interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type Number interface {
  SignedInt
  Integer
}

A interseção no exemplo certamente é SignedInt,

func Do[T Number](n T) T {
   return n
}

Do[int](2)
DO[uint](2) // não consegue compilar

Conjunto Vazio

Conjunto vazio é quando não há interseção. Exemplo abaixo, Integer no exemplo abaixo é um conjunto de tipos vazio.

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnsignedInt interface {
  uint8 | uint16 | uint | uint32 | uint64
}

type Integer interface {
  SignedInt
  UnsignedInt
}

Como inteiros sem sinal e inteiros com sinal certamente não têm interseção, a interseção é um conjunto vazio. No exemplo abaixo, não importa qual tipo seja passado, não conseguirá compilar.

Do[Integer](1)
Do[Integer](-100)

Interface Vazia

Interface vazia é diferente de conjunto vazio. Interface vazia é o conjunto de todos os conjuntos de tipos, ou seja, contém todos os tipos.

func Do[T interface{}](n T) T {
   return n
}

func main() {
   Do[struct{}](struct{}{})
   Do[any]("abc")
}

No entanto, geralmente usamos any como parâmetro formal genérico, porque inerface{} não é bonito.

Tipo Base

Quando se usa a palavra-chave type para declarar um novo tipo, mesmo que seu tipo base esteja incluído no conjunto de tipos, quando passado ainda não conseguirá compilar.

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type TinyInt int8

func Do[T Int](n T) T {
   return n
}

func main() {
   Do[TinyInt](1) // não consegue compilar, mesmo que seu tipo base pertença ao intervalo do conjunto de tipos Int
}

Há duas soluções. A primeira é incorporar este tipo ao conjunto de tipos, mas isso não tem sentido, porque o tipo base de TinyInt e int8 é o mesmo, então há a segunda solução.

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64 | TinyInt
}

Usando o símbolo ~ para representar o tipo base, se o tipo base de um tipo pertence a este conjunto de tipos, então este tipo pertence a este conjunto de tipos, como mostrado abaixo

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64
}

Após a modificação, pode compilar.

func main() {
   Do[TinyInt](1) // pode compilar, porque TinyInt está no conjunto de tipos Int
}

Pontos de Atenção

Generics não podem ser usados como tipo base de um tipo

A seguinte escrita está errada, o parâmetro de tipo formal T não pode ser usado como tipo base

type GenericType[T int | int32 | int64] T

Embora a seguinte escrita seja permitida, não tem sentido e pode causar problemas de overflow de valores, então não é recomendada

type GenericType[T int | int32 | int64] int

Tipos genéricos não podem usar asserção de tipo

Usar asserção de tipo em tipos genéricos não conseguirá compilar. O problema que generics quer resolver é independente de tipo. Se um problema precisa fazer lógica diferente baseado em tipos diferentes, então não se deve usar generics, deve-se usar interface{} ou any.

func Sum[T int | float64](a, b T) T {
   ints,ok := a.(int) // não permitido
   switch a.(type) { // não permitido
   case int:
   case bool:
      ...
   }
   return a + b
}

Structs anônimos não suportam generics

Structs anônimos não suportam generics, o código abaixo não conseguirá compilar

testStruct := struct[T int | string] {
   Name string
   Id T
}[int]{
   Name: "jack",
   Id: 1
}

Funções anônimas não suportam generics personalizados

As duas escritas abaixo não conseguirão compilar

var sum[T int | string] func (a, b T) T
sum := func[T int | string](a,b T) T{
    ...
}

Mas pode usar tipos genéricos já existentes, por exemplo em closures

func Sum[T int | float64](a, b T) T {
  sub := func(c, d T) T {
    return c - d
  }
  return sub(a,b) + a + b
}

Não suporta métodos genéricos

Métodos não podem ter parâmetros de tipo formal genérico, mas o receiver pode ter parâmetros de tipo formal genérico. O código abaixo não conseguirá compilar

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

func (g GenericStruct[T]) name[S int | float64](a S) S {
   return a
}

Conjunto de tipos não pode ser usado como argumento de tipo

Qualquer interface com conjunto de tipos não pode ser usada como argumento de tipo.

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

func Do[T SignedInt](n T) T {
   return n
}

func main() {
   Do[SignedInt](1) // não consegue compilar
}

Problema de interseção em conjuntos de tipos

Para tipos não interface, a união de tipos não pode ter interseção. Por exemplo, no exemplo abaixo, TinyInt e ~int8 têm interseção.

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // não consegue compilar
}

type TinyInt int8

Mas para tipos interface, é permitido ter interseção, como no exemplo abaixo

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // pode compilar
}

type TinyInt interface {
  int8
}

Conjunto de tipos não pode se incorporar direta ou indiretamente a si mesmo

No exemplo abaixo, Floats se incorpora diretamente a si mesmo, e Double se incorpora a Floats, então indiretamente se incorpora a si mesmo.

type Floats interface {  // código não consegue compilar
   Floats | Double
}

type Double interface {
   Floats
}

A interface comparable não pode ser incorporada em conjunto de tipos

Da mesma forma, também não pode ser incorporada em restrições de tipo, então basicamente é usada sozinha.

func Do[T comparable | Integer](n T) T { //não consegue compilar
   return n
}

type Number interface { // não consegue compilar
  Integer | comparable
}

type Comparable interface { // pode compilar mas não tem sentido
  comparable
}

Conjunto de métodos não pode ser incorporado em conjunto de tipos

Qualquer interface que contenha métodos não pode ser incorporada em conjunto de tipos

type I interface {
    int | fmt.Stringer // cannot use fmt.Stringer in union (fmt.Stringer contains methods)
}

Mas eles podem fazer interseção, embora fazer isso não tenha sentido

type I interface {
    int
    fmt.Stringer
}

Uso

Estruturas de dados são o cenário de uso mais comum de generics. A seguir, serão mostrados dois exemplos de estruturas de dados para demonstrar como usar generics.

Fila

A seguir, implementa-se uma fila simples usando generics. Primeiro declara-se o tipo de fila, o tipo dos elementos na fila pode ser qualquer um, então a restrição de tipo é any

type Queue[T any] []T

Total de apenas quatro métodos Pop, Peek, Push, Size, código abaixo.

type Queue[T any] []T

func (q *Queue[T]) Push(e T) {
  *q = append(*q, e)
}

func (q *Queue[T]) Pop(e T) (_ T) {
  if q.Size() > 0 {
    res := q.Peek()
    *q = (*q)[1:]
    return res
  }
  return
}

func (q *Queue[T]) Peek() (_ T) {
  if q.Size() > 0 {
    return (*q)[0]
  }
  return
}

func (q *Queue[T]) Size() int {
  return len(*q)
}

Nos métodos Pop e Peek, pode-se ver que o valor de retorno é _ T, esta é a forma de usar valor de retorno nomeado, mas usando underscore _ para indicar que é anônimo. Isso não é fazer algo desnecessário, mas para representar o valor zero genérico. Como se usa generics, quando a fila está vazia, precisa retornar o valor zero, mas como o tipo é desconhecido, não é possível retornar um tipo específico. Através da forma acima, pode-se retornar o valor zero genérico. Também se pode declarar uma variável genérica para resolver o problema do valor zero. Para uma variável genérica, seu valor padrão é o valor zero daquele tipo, como abaixo

func (q *Queue[T]) Pop(e T) T {
    var res T
  if q.Size() > 0 {
    res = q.Peek()
    *q = (*q)[1:]
    return res
  }
  return res
}

Heap

No exemplo da fila acima, como não há nenhum requisito para os elementos, a restrição de tipo é any. Mas heap é diferente. Heap é uma estrutura de dados especial que pode julgar o valor máximo ou mínimo em tempo O(1), então tem um requisito para os elementos, que devem ser tipos ordenáveis. Mas os tipos ordenáveis embutidos são apenas números e strings, então na inicialização do heap, precisa-se passar um comparador personalizado. O comparador é fornecido pelo chamador e o comparador também deve usar generics, como abaixo

type Comparator[T any] func(a, b T) int

Abaixo está uma implementação simples de heap binário. Primeiro declara-se a struct genérica, ainda usando any para restrição, assim pode armazenar qualquer tipo

type Comparator[T any] func(a, b T) int

type BinaryHeap[T any] struct {
  s []T
  c Comparator[T]
}

Implementação de alguns métodos

func (heap *BinaryHeap[T]) Peek() (_ T) {
  if heap.Size() > 0 {
    return heap.s[0]
  }
  return
}

func (heap *BinaryHeap[T]) Pop() (_ T) {
  size := heap.Size()
  if size > 0 {
    res := heap.s[0]
    heap.s[0], heap.s[size-1] = heap.s[size-1], heap.s[0]
    heap.s = heap.s[:size-1]
    heap.down(0)
    return res
  }
  return
}

func (heap *BinaryHeap[T]) Push(e T) {
  heap.s = append(heap.s, e)
  heap.up(heap.Size() - 1)
}

func (heap *BinaryHeap[T]) up(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  for parentIndex := i>>1 - 1; parentIndex >= 0; parentIndex = i>>1 - 1 {
    // greater than or equal to
    if heap.compare(heap.s[i], heap.s[parentIndex]) >= 0 {
      break
    }
    heap.s[i], heap.s[parentIndex] = heap.s[parentIndex], heap.s[i]
    i = parentIndex
  }
}

func (heap *BinaryHeap[T]) down(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  size := heap.Size()
  for lsonIndex := i<<1 + 1; lsonIndex < size; lsonIndex = i<<1 + 1 {
    rsonIndex := lsonIndex + 1

    if rsonIndex < size && heap.compare(heap.s[rsonIndex], heap.s[lsonIndex]) < 0 {
      lsonIndex = rsonIndex
    }

    // less than or equal to
    if heap.compare(heap.s[i], heap.s[lsonIndex]) <= 0 {
      break
    }
    heap.s[i], heap.s[lsonIndex] = heap.s[lsonIndex], heap.s[i]
    i = lsonIndex
  }
}

func (heap *BinaryHeap[T]) Size() int {
  return len(heap.s)
}

func NewHeap[T any](n int, c Comparator[T]) BinaryHeap[T] {
	var heap BinaryHeap[T]
	heap.s = make([]T, 0, n)
	heap.Comparator = c
	return heap
}

Uso como abaixo

type Person struct {
  Age  int
  Name string
}

func main() {
  heap := NewHeap[Person](10, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)
  })
  heap.Push(Person{Age: 10, Name: "John"})
  heap.Push(Person{Age: 18, Name: "mike"})
  heap.Push(Person{Age: 9, Name: "lili"})
  heap.Push(Person{Age: 32, Name: "miki"})
  fmt.Println(heap.Peek())
  fmt.Println(heap.Pop())
  fmt.Println(heap.Peek())
}

Saída

{9 lili}
{9 lili}
{10 John}

Com o suporte de generics, tipos originalmente não ordenáveis podem usar heap após passar um comparador. Fazer isso certamente é mais elegante e conveniente do que usar interface{} para conversão de tipo e asserção como antes.

Pool de Objetos

O pool de objetos original só pode usar o tipo any, toda vez que é retirado precisa fazer asserção de tipo. Após uma simples modificação com generics, pode-se economizar este trabalho.

package main

import (
	"bytes"
	"fmt"
	"sync"
)

func NewPool[T any](newFn func() T) *Pool[T] {
	return &Pool[T]{
		pool: &sync.Pool{
			New: func() interface{} {
				return newFn()
			},
		},
	}
}

type Pool[T any] struct {
	pool *sync.Pool
}

func (p *Pool[T]) Put(v T) {
	p.pool.Put(v)
}

func (p *Pool[T]) Get() T {
	var v T
	get := p.pool.Get()
	if get != nil {
		v, _ = get.(T)
	}
	return v
}

func main() {
	bufferPool := NewPool(func() *bytes.Buffer {
		return bytes.NewBuffer(nil)
	})

	for range 100 {
		buffer := bufferPool.Get()
		buffer.WriteString("Hello, World!")
		fmt.Println(buffer.String())
		buffer.Reset()
		bufferPool.Put(buffer)
	}
}

Resumo

Uma das grandes características do Go é a velocidade de compilação muito rápida. Compilar rápido é porque se faz pouca otimização durante a compilação. A adição de generics fará com que o trabalho do compilador aumente e se torne mais complexo, o que inevitavelmente fará a velocidade de compilação diminuir. Na verdade, quando o go1.18 acabou de lançar generics, realmente fez a compilação mais lenta. A equipe Go queria adicionar generics mas não queria desacelerar muito a velocidade de compilação. Se os desenvolvedores usam com facilidade, o compilador sofre; inversamente, se o compilador fica relaxado (o mais relaxado seria simplesmente não ter generics), os desenvolvedores sofrem. Os generics atuais são o produto do compromisso entre esses dois lados.