Tipos que programam: construindo um encoder Base64 em tempo de compilação

Introdução

Acredito que todos que trabalham diariamente com TypeScript já perceberam o quão poderoso é o sistema de tipagem fornecido pela linguagem. Ele funciona não apenas como uma camada de segurança em tempo de compilação e desenvolvimento, mas também como uma verdadeira meta-linguagem Turing-completa, capaz de expressar lógica, transformar valores e até executar cálculos complexos, tudo antes mesmo do código rodar.

Neste artigo, iremos explorar esse poder na prática, construindo um encoder de string para Base64 utilizando somente o sistema de tipos do TypeScript. Usaremos ferramentas como template literal types, conditional types e tipos recursivos, mostrando como o compilador pode ser usado como um pequeno motor de execução funcional.

Mais do que uma simples curiosidade, este exercício revela como o sistema de tipos do TypeScript pode ser usado como um ambiente de meta-programação estática, capaz de descrever e executar transformações determinísticas de dados sem depender de runtime algum. Ao final, veremos não só como o Base64 funciona por baixo dos panos, mas também como o TypeScript, quando levado ao limite, se transforma em uma linguagem de programação dentro da própria linguagem.

Vale mencionar que escrevi a primeira versão desse encoder durante a pandemia, acomo um experimento pessoal para entender até onde o TypeScript permitia ir.
Estou revisitando esse código agora, anos depois, e é bem possível que várias partes possam ser simplificadas ou otimizadas usando recursos mais modernos do TS (como melhorias em template literal types, inferências e limites de recursão).
O objetivo aqui não é apresentar “a forma perfeita”, mas compartilhar o processo e a criatividade envolvida no experimento original.

Para quem é este artigo

Este é um artigo de nível intermediário/avançado em TypeScript.

Vou assumir que você já está confortável com:

• Generics;
• Union e intersection types;
• Template literal types;
• Conditional types;
• Tuplas e tipos recursivos.

Não vou explicar esses conceitos do zero; a ideia aqui é ver como combinar essas ferramentas para construir um encoder Base64 em tempo de compilação e, de quebra, explorar o sistema de tipos do TypeScript como uma pequena linguagem funcional dentro da própria linguagem.

Base64, o que é? Como funciona?

Segundo a Wikipédia, o Base64 é descrito como “um método para codificação de dados para transferência na Internet (codificação MIME para transferência de conteúdo). É utilizado frequentemente para transmitir dados binários por meios de transmissão que lidam apenas com texto, como por exemplo para enviar arquivos anexos por e-mail.”
Agora que sabemos que se trata de um método de codificação de dados, precisamos entender como ele funciona de fato e quais são as regras para essa conversão.

Regras do Base64

Para converter algo, seja um arquivo binário ou um simples texto, deve-se primeiro transformar o conteúdo em sua representação binária. Por exemplo, as strings a, b e c, convertidas seguindo a tabela ASCII, são respectivamente:

• a → 01100001
• b → 01100010
• c → 01100011

Depois disso, juntamos esses octetos, formando grupos de 3 bytes (24 bits):

01100001 01100010 01100011

Ou seja,

011000010110001001100011

Esses 24 bits são então divididos em 4 grupos de 6 bits:

011000 010110 001001 100011

Como cada grupo de 6 bits possui exatamente 64 combinações possíveis (2⁶ = 64), daí o “64” em Base64, cada grupo pode ser mapeado para um caractere específico da tabela Base64.

E quando não é múltiplo de 3 bytes? (bits de preenchimento e =)

Até aqui, vimos o caso “perfeito”, em que a entrada tem um número de bytes múltiplo de 3, gerando exatamente 24 bits por bloco. Mas e quando a string não tem 3, 6, 9… bytes?

O Base64 resolve isso usando bits de preenchimento com zeros e, em seguida, caracteres = no final da string para sinalizar que houve esse preenchimento artificial.

A regra é:

• A codificação trabalha sempre com blocos de 3 bytes (24 bits).
• Se a quantidade de bytes não é múltiplo de 3, o último bloco é completado com zeros à direita para fechar os 24 bits.
• Depois disso, o resultado Base64 é completado com:
  • == se a entrada terminou com 1 byte restante.
  • = se a entrada terminou com 2 bytes restantes.
  • nada se terminou com 3 bytes certinhos.

Por exemplo, para a string "a":

1. 'a' em ASCII é 01100001 (8 bits).
2. Para formar 24 bits, o encoder adiciona 16 zeros à direita:

01100001 00000000 00000000

1. Isso é dividido em 4 grupos de 6 bits:

011000 010000 000000 000000

1. Esses valores mapeiam para os caracteres YQAA na tabela Base64.
2. Como só havia 1 byte real na entrada, os dois últimos caracteres (AA) são resultado puro do preenchimento com zeros. Eles são substituídos por ==, gerando o resultado final:

"a" → "YQ=="

Da mesma forma, quando temos 2 bytes no último bloco, apenas 1 caractere é substituído por =. Esses = não são “valores” propriamente ditos, mas uma forma de indicar que parte dos bits no último grupo foi preenchida só para completar o tamanho do bloco.

Construindo o encoder

Mapa ASCII em bits

O primeiro passo é definir a representação binária dos caracteres ASCII.

Mas, em vez de armazenar o byte inteiro 01101000, representamos cada byte como 4 pares de 2 bits:

type AsciiTable = {
  'a': ['01', '10', '00', '01'];
  'b': ['01', '10', '00', '10'];
  // ...
  '!': ['00', '10', '00', '01'];
};

Por que 2 bits por vez?

Porque o TypeScript não tem operações aritméticas de bitshift, então dividir em blocos de 2 bits nos permite compor bytes em sextetos declarativamente, apenas concatenando strings.

Convertendo 3 bytes para 4 sextetos

A magia acontece em FromCharArrayTo6BitBinaryArray.

Essa função de tipo pega 3 caracteres (C1, C2, C3) e remonta seus bits para gerar 4 grupos de 6 bits (o formato que o Base64 usa).

type FromCharArrayTo6BitBinaryArray<A extends string[]> =
  A extends [
    infer C1 extends keyof AsciiTable,
    infer C2 extends keyof AsciiTable,
    infer C3 extends keyof AsciiTable,
    ...infer Rest extends string[]
  ]
    ? `${AsciiBits<C1>[0]}${AsciiBits<C1>[1]}${AsciiBits<C1>[2]}-
       ${AsciiBits<C1>[3]}${AsciiBits<C2>[0]}${AsciiBits<C2>[1]}-
       ${AsciiBits<C2>[2]}${AsciiBits<C2>[3]}${AsciiBits<C3>[0]}-
       ${AsciiBits<C3>[1]}${AsciiBits<C3>[2]}${AsciiBits<C3>[3]}${Rest extends [] ? "" : `-${FromCharArrayTo6BitBinaryArray<Rest>}`}`
    : ...

O código é denso, mas a ideia é simples:

cada 3 bytes viram 4 blocos de 6 bits, com hífens entre eles (011110-000110-000101-...).

Esse formato é didático, pois mostra o que o encoder realmente faz: “desliza” os bits para a esquerda e reagrupa em sextetos.

Mapeando sextetos para caracteres Base64

Depois que temos a sequência de bits agrupada em 6, mapeamos cada sexteto para o caractere Base64 correspondente:

type Base64Chars = {
  '000000': 'A'; '000001': 'B'; '000010': 'C'; /* ... */ '111111': '/';
};

E um tipo recursivo simples:

type FromBinaryArrayToBase64Chars<A extends string[]> = 
  A extends [infer Head extends string, ...infer Tail extends string[]]
    ? `${Base64Chars[Head]}${FromBinaryArrayToBase64Chars<Tail>}`
    : "";

Padding: %3 em tempo de tipo

A cereja do bolo é o padding (= ou ==), que depende do comprimento da entrada.
Usamos aritmética baseada em tuplas para descobrir length % 3:

type Mod3<A extends unknown[]> = A extends [unknown, unknown, unknown, ...infer R extends unknown[]]
  ? Mod3<R>
  : A['length'];

type PaddingForArray<A extends unknown[], R = Mod3<A>> =
  R extends 1 ? "==" :
  R extends 2 ? "=" : "";

Nenhuma operação numérica real, apenas remoção recursiva de trios.

O encoder completo

Juntando tudo:

type Base64Encode<
  S extends string,
  CharArray extends string[] = Split<S>
> = `${FromBinaryArrayToBase64Chars<
  Split<FromCharArrayTo6BitBinaryArray<CharArray>, "-">
>}${PaddingForArray<CharArray>}`;

E temos:

type Result = Base64Encode<"xablau!">;
// "eGFibGF1IQ=="

type Bits = Base64EncodeWithoutBa64Chars<"xablau!">;
// 011110-000110-000101-100010-011011-000110-000101-110101

Testes

Podemos testar nosso encoder em tempo de compilação:

type Expect<T extends true> = T;

type _1 = Expect<Base64Encode<"f"> extends "Zg==" ? true : false>;
type _2 = Expect<Base64Encode<"fo"> extends "Zm8=" ? true : false>;
type _3 = Expect<Base64Encode<"foo"> extends "Zm9v" ? true : false>;
type _4 = Expect<Base64Encode<"xablau!"> extends "eGFibGF1IQ==" ? true : false>;

Esses testes rodam durante o type-check, e se algo falhar o compilador acusa erro.

Conclusão

O que vimos aqui não é sobre “reinventar a roda” do Base64, muito menos sobre substituir implementações de runtime. O objetivo foi outro: usar um problema bem definido e conhecido para enxergar o sistema de tipos do TypeScript como um ambiente de computação de verdade.

Ao construir um encoder Base64 só com tipos, a gente:

• Tratou o compilador como um interpretador funcional;
• Modelou bits, bytes e sextetos usando tuplas, strings e recursão;
• Usou o sistema de tipos para expressar uma transformação determinística de dados, e não somente para prevenir bugs.

Ao mesmo tempo, ele expõe os limites práticos: profundidade de recursão, verbosidade e custo de compilação. E tudo bem. A graça aqui não é usar isso em produção para cada problema, mas entender até onde dá para ir quando tratamos tipos como programa.

Caso queira brincar um pouco com o encoder, aqui está o link para o playground.

Comments

[Iasmim Vieira]

Excelente texto!