Executando verificação de segurança...
10
iagobelo
7 min de leitura ·

Type-Level Programming na prática: construindo um encoder Base64 somente com tipos (TypeScript)

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 somente 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.

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

É interessante ver o que podemos construir utilizando somente o sistema de tipagem do TS, e mais do que isso, praticar esse tipo de exercício nos ajuda a construir um entendimento mais profundo dos poderes da linguagem ao mesmo tempo que também expõe seus limites práticos.

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

Carregando publicação patrocinada...
2
er1c3g

Muito bom, man! A maioria das pessoas não sabe do poder que o TypeScript tem e de como ele é flexível ao mesmo tempo. Ele tem um dos sistemas de tipos mais complexos que existem no mundo da programação atualmente, e alguns dizem que os tipos em si são uma linguagem própria. Teve um mano que fez Flappy Bird apenas em tipos do TypeScript.
Eu estou fazendo algo semelhante, mas estou criando o DOOM apenas com tipos de TypeScript, e o processo está sendo bem legal. Valeu por escrever esse post e compartilhar esse conhecimento que nem todo mundo tem noção.

1
iagobelo
  • Autor
    Autor

Valeu! Sem dúvidas, o sistema de tipagem do TS vai muito além do que a maioria sequer imagina!
Adoraria saber mais sobre esse seu projeto de criar DOOM somente com tipos do TS, se tiver algum repositório ou algo do tipo para compartilhar.