Testes gerativos: aritmética em C++ com Hegel
Este artigo faz parte de uma série que explora testes gerativos aplicados a diferentes casos exemplares em uma variedade de linguagens de programação.
Neste artigo, examinamos testes dos algoritmos aritméticos clássicos na linguagem C++ com o framework de testes Hegel.
Testes gerativos baseados em propriedades
Assumimos que o leitor está familiarizado com a prática dos testes de software e tem familiaridade mínima com o conceito de testes gerativos (generative tests) e testes baseados em propriedades (property based tests).
Neste artigo, usamos o framework Hegel, um projeto atualmente em desenvolvimento. Para saber mais sobre Hegel e acompanhar seu desenvolvimento, siga para o repositório oficial.
Aritmética em C++
Assumimos que o leitor está familiarizado com os algoritmos aritméticos clássicos para somar, multiplicar, subtrair e dividir, como se ensina na escola para calcular com papel e caneta.
Neste artigo, vamos trabalhar um “dígito” ou “palavra” `uint64_t” e estas definições em C++ para as rotinas aritméticas:
// r ← x + y
// retorna o "vai um"
auto sum ( span<uint64_t> r, span<uint64_t> x, span<uint64_t> y ) -> uint64_t;
// r ← x − y
// retorna o "empréstimo"
auto difference ( span<uint64_t> r, span<uint64_t> x, span<uint64_t> y ) -> uint64_t;
// r ← x × y
void product ( span<uint64_t> r, span<uint64_t> x, span<uint64_t> y );
// (q,r) ← x ÷ y
void division ( span<uint64_t> q, span<uint64_t> r, span<uint64_t> x, span<uint64_t> y );
// x = y ?
auto not_equal ( span<uint64_t> x, span<uint64_t> y ) -> bool;Para, digamos, somar x e y:
auto r = vector<uint64_t>( max( x.size(), y.size() ) );
auto carry = sum( r, x, y );onde nós preparamos em r um buffer para o resultado com espaço suficiente para todos os dígitos do resultado com o carry separado.
Além disso, especificamos que, caso o buffer tenha espaço para isso, o carry deve ser incorporado ao resultado:
auto r = vector<uint64_t>( max( x.size(), y.size() ) + 1 );
auto _ = sum( r, x, y );Testando aritmética em C++ com Hegel
O principal desafio do teste gerativo é estabelecer a expectativa: como a rotina de teste não predefine os valores da entrada, não pode embutir os valores esperados da saída. Mas calcular o valor da saída a partir da entrada é exatamente o que queremos testar. Como podemos testar sem saber dizer se o resultado está certo ou errado?
Com sorte, temos um “oráculo” capaz de dar a resposta; por exemplo, uma rotina antiga, lenta e segura, que nós vamos substituir por uma nova, rápida e complicada. Suponha que temos um “oráculo” para a soma; vamos verificar sum com o framework Hegel. Vamos assumir que not_equal está correta e usá-la para testar as demais rotinas.
#include <algorithm>
#include <cstdint>
#include <span>
#include <stdexcept>
#include <vector>
using std::ranges::max;
using std::runtime_error;
using std::span;
using std::vector;
#include <hegel/hegel.h>
using hegel::generators::integers;
using hegel::generators::vectors;
#include "library.h"
auto sum_oracle ( span<uint64_t> r, span<uint64_t> x, span<uint64_t> y ) -> uint64_t;
HEGEL_TEST(sum_differential)(hegel::TestCase& t) {
auto x = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto y = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto rz = max( x.size(), y.size() );
auto expected = vector<uint64_t>( rz+1 );
auto _ = sum_oracle( expected, x, y );
auto computed = vector<uint64_t>( rz+1 );
auto _ = sum( computed, x, y );
if ( not_equal( computed, expected ) )
throw runtime_error("computed != oracle");
}
int main() {
sum_differential();
return 0;
}Com a macro HEGEL_TEST(name) definimos um teste do framework Hegel. O objeto tipo hegel::TestCase dá acesso ao método TestCase::draw para obter valores do engine Hegel. O argumento de draw é um “gerador”. Neste teste, compomos um gerador vectors com um gerador integers<uint64_t> para gerar objetos std::vector<uint64_t>. Leia a expressão com cuidado e veja que passamos ao gerador vectors um segundo argumento; neste segundo argumento definimos min_size=1. Com isso, Hegel produz x e y não “vazios” quaisquer.
Em seguida, o teste aplica x e y a ambos o oráculo (para o resultado esperado) e a sum (para o resultado obtido), e verifica se são iguais.
Essa situação é ideal. Se temos um oráculo confiável, esse teste basta. Se ele for executado muitas e muitas vezes, com um bom engine de valores aleatórios, a certeza de que a rotina funciona será grande.
Às vezes, não existe máquina antiga ou oráculo com o qual testar a diferença; às vezes, mesmo tendo um oráculo, a nova máquina tem propriedades adicionais que a antiga não tinha.
Podemos, alternativamente, verificar que o resultado obtido possui propriedades universais, que valem sempre, para todos os resultados. Por exemplo, deve ser sempre verdade para qualquer : é o elemento “nulo” da soma.
HEGEL_TEST(sum_null_element)(hegel::TestCase& t) {
auto x = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto y = vector<uint64_t> { 0 };
auto rz = max( x.size(), y.size() );
auto r = vector<uint64_t>( rz+1 );
auto _ = sum( r, x, y );
if ( not_equal( r, x ) )
throw runtime_error("x + 0 != x");
}Outro exemplo: , ou seja, a soma é comutativa.
HEGEL_TEST(sum_commutativity)(hegel::TestCase& t) {
auto x = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto y = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto rz = max( x.size(), y.size() );
auto r1 = vector<uint64_t>( rz+1 );
auto _ = sum( r1, x, y );
auto r2 = vector<uint64_t>( rz+1 );
auto _ = sum( r2, y, x );
if ( not_equal( r2, r1 ) )
throw runtime_error("x + y != y + x");
}Podemos explorar relações entre rotinas; por exemplo, .
HEGEL_TEST(sum_difference_cancellation)(hegel::TestCase& t) {
auto x = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto y = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto rz = max( x.size(), y.size() );
auto r1 = vector<uint64_t>( rz+1 );
auto _ = sum( r1, x, y );
auto r2 = vector<uint64_t>( rz+1 );
auto _ = difference( r2, r1, x );
if ( not_equal( r2, y ) )
throw runtime_error("x + y - x != y");
}Outro exemplo: .
HEGEL_TEST(product_sum_distributivity)(hegel::TestCase& t) {
auto x = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto y = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto w = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
// y + w
auto yw = vector<uint64_t>( max(y.size(),w.size())+1 );
auto _ = sum( yw, y, w );
// x × (y + w)
auto xyw = vector<uint64_t>( x.size()+yw.size() );
product( xyw, x, yw );
// x × y
auto xy = vector<uint64_t>( x.size()+y.size() );
product( xy, x, y );
// x × w
auto xw = vector<uint64_t>( x.size()+w.size() );
product( xw, x, y );
// (x × y) + (x × w)
auto xyxw = vector<uint64_t>( max(xy.size(),xw.size())+1 );
auto _ = sum( xyxw, xy, xw );
if ( not_equal( xyxw, xyw ) )
throw runtime_error("x × (y + w) != (x × y) + (x × w)");
}Dessa forma, o conhecimento das propriedades e relações universais materializa-se em uma suíte de testes baseados nessas propriedades e relações universais. Por outra perspectiva, os “requisitos” da biblioteca materializam-se em testes que correspondem diretamente a esses “requisitos”, deixando a cargo do engine de testes a variação nos “inputs” particulares testados.
Para além das relações aritméticas, uma biblioteca de programação lida com os problemas típicos da programação. O que acontece se o buffer do resultado for curto, ou seja, não tiver espaço para todos os dígitos? O que acontece se ele for longo, ou seja, tiver mais espaço do que o necessário? E se esse buffer inicia com “lixo”?
Vamos considerar uma API robusta que aceita essas situações; se o buffer for longo, ele deve ser “zerado” para representar corretamente o número-resultado; se o buffer for curto, vamos produzir somente os dígitos com espaço disponível, “truncando” o resultado.
HEGEL_TEST(product_buffer)(hegel::TestCase& t) {
auto x = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto y = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
// exact buffer
auto exact = vector<uint64_t>( x.size()*y.size() );
product( exact, x, y );
// large buffer with garbage
auto large = t.draw( vectors( integers<uint64_t>(), {.min_size=exact.size()+1} ) );
product( large, x, y );
if ( not_equal( large, exact ) )
throw runtime_error("large != exact");
// short buffer with garbage
auto short_ = t.draw( vectors( integers<uint64_t>(), {.max_size=exact.size()-1} ) );
product( short_, x, y );
if ( not_equal( short_, span(exact).first(short_.size()) ) ) // see std::span::first
throw runtime_error("short != exact");
}O caso da divisão é interessante porque dois números são produzidos, o quociente e o resto, e existe uma relação interna entre eles: seja ; então .
HEGEL_TEST(division)(hegel::TestCase& t) {
auto x = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto y = t.draw( vectors( integers<uint64_t>(), {.min_size=1} ) );
auto zero = vector<uint64_t> { 0 };
t.assume( not_equal(y,zero) );
// q,r ← x ÷ y
auto q = vector<uint64_t>( x.size() );
auto r = vector<uint64_t>( x.size() );
division( r, r, x, y );
// q × y
auto qy = vector<uint64_t>( x.size() );
product( qy, q, y );
// × y + r
auto qyr = vector<uint64_t>( x.size() );
auto _ = sum( qyr, qy, r );
if ( not_equal( qyr, x ) )
throw runtime_error("q × y + r != x");
}Note o uso do método hegel::TestCase::assume. O algoritmo de divisão não está definido para . Precisamos informar ao engine Hegel esta pressuposição. Para uso, usamos TestCase::assume. Caso o argumento seja falso, Hegel saberá que esta variação é inválida, e tentará outra.
Prosseguimos assim, de propriedade em propriedade, de relação em relação, de “requisito” em “requisito”, tornando nossa suíte de teste mais robusta ao mesmo tempo que tornamos o “contrato” da nossa biblioteca ou programa mais explícito.
O que achou? Consegue pensar em mais propriedades para testar? Experimente brincar com este projeto-exercício!