Invariantes: a promessa que o código mantém

A promessa que vale sempre

No começo do curso você viu a árvore de busca binária. O que faz a busca dela ser rápida é uma regra que nunca pode falhar: em cada nó, tudo o que está à esquerda é menor, tudo o que está à direita é maior. Enquanto essa regra valer, a busca corta pela metade a cada passo. Essa regra que vale sempre, não importa quantas inserções e remoções aconteceram, é o que se chama de invariante. É a promessa central da estrutura. Se em algum momento um valor maior aparecer à esquerda, a árvore para de ser uma BST e a busca deixa de funcionar. A estrutura só é confiável porque a invariante é mantida a cada operação.

Invariantes estão em toda parte, não só em estruturas de dados. Uma conta bancária tem a invariante de que o saldo nunca cai abaixo do limite permitido. Uma lista de tarefas ordenada por prioridade tem a invariante de que a mais urgente está sempre na frente. Um carrinho de compras tem a invariante de que o total é sempre a soma dos itens. O ponto comum: são condições que devem ser verdadeiras antes e depois de qualquer operação. Durante uma operação, a invariante pode ser quebrada por um instante (no meio de uma inserção a árvore fica temporariamente inconsistente), mas ao fim ela precisa estar de volta. Quem garante isso é a interface, cada função dela cuida de deixar a promessa intacta.

A invariante vira teste

A grande utilidade prática de nomear as invariantes é que elas viram testes quase de graça. Se você sabe que a árvore deve manter menores à esquerda e maiores à direita, dá para escrever uma função que percorre a estrutura e confere isso, e chamá-la depois de cada inserção e remoção nos testes. Se a invariante estiver de pé, a operação preservou a promessa; se estiver quebrada, você achou um bug exatamente onde ele nasce, e não três telas depois, quando o sintoma aparece confuso. Testar contra invariantes é uma das formas mais poderosas de garantir que uma estrutura complexa continua correta enquanto ela cresce e o código muda.

// A invariante da conta: o saldo nunca fica abaixo do limite negativo.
// invariante:  saldo >= -limite

funcao sacar(conta, valor)
  novoSaldo <- conta.saldo - valor
  se novoSaldo < (-conta.limite) então
    retorne "saque negado"        // protege a invariante: não deixa quebrar
  fim
  conta.saldo <- novoSaldo
  retorne "ok"
fim

// Nos testes, depois de cada operação, cheque a promessa:
funcao invarianteVale(conta)
  retorne conta.saldo >= (-conta.limite)
fim
// se invarianteVale(conta) for falso em algum ponto, há um bug.

A função sacar protege a invariante recusando o que a quebraria. invarianteVale confere a promessa nos testes.

A invariante mora atrás da interface

Repare como as três ideias do módulo se encaixam. A invariante é uma promessa interna do módulo. Quem a protege é a interface: as funções públicas são desenhadas para nunca deixar a promessa quebrada no fim. E por isso a implementação fica escondida: se qualquer um pudesse mexer direto na estrutura interna, sem passar pela interface, poderia quebrar a invariante à toa, e o módulo perderia sua garantia. É por isso que se esconde o interior e se obriga o uso pela interface. A parede não existe só por organização, ela existe para proteger a promessa. Quem usa o módulo, em troca, ganha uma garantia em que pode confiar sem verificar toda vez, o que simplifica todo o código que depende dele.