Arrays with negative indexes

When we to deal with negative ranges in arrays and those ranges can be negative, we do shifts so we can use natural indexes. For example, if we’re given a range from -50 to 20, usually we allocate an array of 70 positions and when indexing an element we shift by +50 so the position -50 is actually stored on the position 0.

These days, while doing random stuff on the internet, I’ve figured that we can easily work with arrays not only starting from zero but starting from any integer we want. To illustrate that, I wrote this function which allocate sz elements of type T where the array’s first element is in min_index position:

template <typename T>
T* alloc(size_t sz, int min_index = 0)
{
	return (new T[sz]) - min_index;
}

An example of use:

int main()
{	
	char* p = alloc<char>(70, -50);
	
	p[-50] = 'h'; p[-49] = 'e'; 
	p[-48] = 'l'; p[-47] = 'l';
	p[-46] = 'o'; p[-45] = '\0';
	
	std::cout << &p[-50] << '\n';
	
	for (int i = -50; i < -45; ++i) {
		std::cout << p[i] << '\n';
	}
}

The result, as expected:

hello
h
e
l
l
o

Feature turning into bug

Me and one of Unicamp teams

Background

A few days ago, after a sub-regional phase of ACM ICPC, one integrant of a team I’m coaching claimed that there was a bug in their C++ compiler. The team had to solve a geometrical problem, and, for that he implemented a class representing a point and an overload for operator*:

 

class point
{
 public:
     double x, y;

     point(double d) : x(d), y(d) {}
     point(const point& p) : x(p.x), y(p.y) {}     

     point operator*(const point& p)
     {
         // ...
         return result;
     }
};

After coding, he’ve compiled the code and tested with sample input tests. But the results were wrong. After some time debugging he found that the problem was happening because in some part of the code, he was calling point::operator* passing a double as argument and he didn’t implement that overload for operator*. The question was: why the compiler didn’t issued errors?

Implicit object construction

C++ has a feature which allow us to construct a object implicitly when the object’s type have a constructor which accepts one argument. For example, if you have a function which takes a std::string as argument, you can call that function passing a c-style string:

void printstr(std::string s)
{
    std::cout << s << std::endl;
}

// ...

printstr("Foo bar baz"); // Implicitly passes std::string("Foo bar baz");

The Google C++ Style Guide states:

Normally, if a constructor takes one argument, it can be used as a conversion. For instance, if you define Foo::Foo(string name) and then pass a string to a function that expects a Foo, the constructor will be called to convert the string into a Foo and will pass the Foo to your function for you.

So, what happened on the contestant program was something like:

point pt;
double d;

// ...

pt = pt * d; // doesn't find an operator* receiving a double
             // so, it is evaluated as pt = pt * point(d);

This feature can lead in many undesired conversions, so it is recommended to “turn off” this type of object construction by declaring constructors with one single argument explicit. The Google C++ Style Guide requires that all single argument constructors to be explicit, except in cases in which the class is a transparent wrapper for other class.

So, the modified code would be something like:

class point
{
 public:
     double x, y;

     explicit point(double d) : x(d), y(d) {}
     point(const point& p) : x(p.x), y(p.y) {}     

     // ...  
};

Some Links

• Google C++ Style Guide
• Code without explicit http://ideone.com/5bq3h
• With explicit http://ideone.com/NnwWY

PHP’s sort functions are bad designed

Everyone knows that is possible to sort an array in O(N log N) where N is the array’s length.

We know also, that Quicksort has expected complexity of O(N log N) but in worst case its complextity is O(N^2), and Quicksort is used more than Mergesort (worst case O(N log N)) because constants are smaller and it requires no extra memory and is easy to avoid Quicksort running on the worst case.

The easiest way to avoid bad inputs for Quicksort is choosing the pivot randomly, which means that a malicious user cannot guess a permutation for cracking it.

What I found at the PHP source is that the pivot choosing is done by picking the element at middle of array.

Here is the code (link line 76):

ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
{
	void           *begin_stack[QSORT_STACK_SIZE];
	void           *end_stack[QSORT_STACK_SIZE];
	register char  *begin;
	register char  *end;
	register char  *seg1;
	register char  *seg2;
	register char  *seg2p;
	register int    loop;
	uint            offset;

	begin_stack[0] = (char *) base;
	end_stack[0]   = (char *) base + ((nmemb - 1) * siz);

	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];
		end   = end_stack[loop];

		while (begin < end) {
			offset = (end - begin) >> 1; // HERE: choosing the current subarray's middle element 
			_zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);

			seg1 = begin + siz;
			seg2 = end;

			while (1) {
				for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
				     seg1 += siz);

				for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
				     seg2 -= siz);

				if (seg1 >= seg2)
					break;

				_zend_qsort_swap(seg1, seg2, siz);

				seg1 += siz;
				seg2 -= siz;
			}

			_zend_qsort_swap(begin, seg2, siz);

			seg2p = seg2;

			if ((seg2p - begin) <= (end - seg2p)) {
				if ((seg2p + siz) < end) {
					begin_stack[loop] = seg2p + siz;
					end_stack[loop++] = end;
				}
				end = seg2p - siz;
			}
			else {
				if ((seg2p - siz) > begin) {
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - siz;
				}
				begin = seg2p + siz;
			}
		}
	}
}

The pivot is named offset here.

Tests

I used the usort() function for counting how many comparisons was needed to sort the array in my cmp() function.
So, lets see the tests:

<?php

$counter = 0; // counts how many comparisons
function cmp($a, $b)
{
	global $counter;
	++$counter;
	return $a - $b;
}

$normal = array();
for ($i = 0; $i < 15; ++$i) {
	$normal[] = $i;
}
shuffle($normal);

$counter = 0;
print "<pre>Normal array:\n";
usort($normal, 'cmp');
print $counter . " comparisons\n\n";

$malicious = array(2, 9, 4, 12, 6, 11, 8, 1, 3, 5, 7, 9, 10, 14, 12);

$counter = 0;
print "Malicious array:\n";
usort($malicious, 'cmp');
print $counter . " comparisons\n</pre>";

?>

And the results:
Normal array:
64 comparisons // variable because of the shuffle

Malicious array:
208 comparisons // constant


It means that the PHP’s sort() family depends on the input array’s length and content while a Randomized Quicksort depends only on the input array’s length.

As we can see, usort() sorted the randomly generated array of length 20 very fast with a few number of comparisons, but in the case of a manipulated array of length 20, the number of comparisons are much more.

In the same way, taking an array of length 10.000, these functions do around 50.000.000 comparisons when the expected is around 132.000. This can be a problem if some “bad” guy inserts manipulated data which your script will sort.

Solution

The naive solution is shuffle()‘n the array before sorting.

<?php

$malicious = array(11, 3, 20, 5, 13, 7, 17, 9, 15, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 19);
shuffle($malicious);

$counter = 0;
print "No longer malicious:\n";
usort($malicious, 'cmp');
print $counter . " coparisons\n</pre>";

?>

Output:
No longer malicious:
76 comparisons


References

zend_qsort source
PHP: sort() function
PHP: usort() function
PHP: shuffle() function
Quicksort – Wikipedia
Mergesort – Wikipedia

Fast and Easy Levenshtein distance using a Trie (in C++)

I implemented this clever algorithm described on Steven Hanov’s blog in C++. Actually this algorithm is a bit different from the original because I wanted to know what is the least Levenshtein distance given a word.

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

/*
 * Algorithm: Edit distance using a trie-tree (Dynamic Programming)
 * Author: Murilo Adriano Vasconcelos <muriloufg@gmail.com>
 */

using namespace std;

// Trie's node
struct trie
{
	typedef map<char, trie*> next_t;

	// The set with all the letters which this node is prefix
	next_t next;

	// If word is equal to "" is because there is no word in the
	//	dictionary which ends here.
	string word;

	trie() : next(map<char, trie*>()) {}

	void insert(string w)
	{
		w = string("$") + w;
		
		int sz = w.size();
		
		trie* n = this;
		for (int i = 0; i < sz; ++i) {
			if (n->next.find(w[i]) == n->next.end()) {
				n->next[w[i]] = new trie();
			}

			n = n->next[w[i]];
		}

		n->word = w;
	}
};

// The tree
trie tree;

// The minimum cost of a given word to be changed to a word of the dictionary
int min_cost;

//
void search_impl(trie* tree, char ch, vector<int> last_row, const string& word)
{
	int sz = last_row.size();

	vector<int> current_row(sz);
	current_row[0] = last_row[0] + 1;

	// Calculate the min cost of insertion, deletion, match or substution
	int insert_or_del, replace;
	for (int i = 1; i < sz; ++i) {
		insert_or_del = min(current_row[i-1] + 1, last_row[i] + 1);
		replace = (word[i-1] == ch) ? last_row[i-1] : (last_row[i-1] + 1);

		current_row[i] = min(insert_or_del, replace);
	}

	// When we find a cost that is less than the min_cost, is because
	// it is the minimum until the current row, so we update
	if ((current_row[sz-1] < min_cost) && (tree->word != "")) {
		min_cost = current_row[sz-1];
	}

	// If there is an element wich is smaller than the current minimum cost,
	// 	we can have another cost smaller than the current minimum cost
	if (*min_element(current_row.begin(), current_row.end()) < min_cost) {
		for (trie::next_t::iterator it = tree->next.begin(); it != tree->next.end(); ++it) {
			search_impl(it->second, it->first, current_row, word);
		}
	}
}

int search(string word)
{
	word = string("$") + word;
	
	int sz = word.size();
	min_cost = 0x3f3f3f3f;

	vector<int> current_row(sz + 1);

	// Naive DP initialization
	for (int i = 0; i < sz; ++i) current_row[i] = i;
	current_row[sz] = sz;
	
	
	
	// For each letter in the root map wich matches with a
	// 	letter in word, we must call the search
	for (int i = 0 ; i < sz; ++i) {
		if (tree.next.find(word[i]) != tree.next.end()) {
			search_impl(tree.next[word[i]], word[i], current_row, word);
		}
	}

	return min_cost;
}

The modification for match all words within a given Leveshtein distance and returning that set is trivial. Just modify the line 72 for storing that word if its Leveshtein distance is less than or equal to a given distance.

For more details, read this: Fast and Easy Levenshtein distance using a Trie
See ya!

Nunca retorne ponteiros para atributos de uma classe nem deixem atributos com acesso ‘public’

Esse post surgiu de uma dúvida que tive:

Como será que é feita a “proteção” dos atributos e funções-membro de classes em C++?

Com isso resolvi fazer  alguns testes e eis a classe de teste:

#include <iostream>
#include <string>

class security
{
private:
	std::string name;
	std::string password;
	int id;
	/* more stuff */
public:
	security() : name("John"), password("s3cr3t"), id(10) {}

	std::string* name_ptr() { return &name; }

	void print_pass()
	{
		std::cout << "The current password is: " << password << std::endl;
	}
};

A pergunta é: aonde pode estar o perigo nesse código (obviamente além de ter uma função-membro que imprime a senha na tela)?

Onde mora o perigo

O perigo maior reside na função-membro name_ptr(). Essa função por algum motivo (talvez o desenvolvedor queria fazer de name_ptr() um getter/setter por exemplo) delega um ponteiro para o atributo name.
Por ela retornar um ponteiro para um atributo da classe, acabamos com o sistema de proteção de acesso a atributos/funções-membro do C++:

int main()
{
	security obj;

	std::string* name = obj.name_ptr();
	std::cout << "Name: " << *name << std::endl;

	std::string* password = (std::string*)(name + 1);
	std::cout << "Password was: " << *password << std::endl;

	// Changing password
	*password = "l33t";

	obj.print_pass(); // whoa!!

	// For other data types
	int* id = (int*)(password + 1);
	std::cout << "ID: " << *id << std::endl;

	return 0;
}

Ou seja, a partir do ponteiro retornado por obj.name_ptr(), através de aritmética de ponteiros[0], podemos acessar qualquer outro atributo de um objeto da classe security, mesmo que estes não sejam public. Como podemos ver no exemplo acima, a partir do atributo name, podemos facilmente obter acesso aos outros atributos.

Outra falha é quando deixamos algum atributo como public:

#include <iostream>
#include <string>

class security
{
public:
	std::string name;
private:
	std::string password;
	int id;

	/* more stuff */

public:

	security() : name("John"), password("s3cr3t"), id(10) {}

	void print_pass()
	{
		std::cout << "The current password is: " << password << std::endl;
	}
};

Dessa maneira podemos também obter o endereço de name, agora apenas usando o operador & unário:

int main()
{
	security obj;

	std::string* name = &(obj.name);
	std::cout << "Name: " << *name << std::endl;

	std::string* password = (std::string*)(name + 1);
	std::cout << "Password was: " << *password << std::endl;

	// Changing password
	*password = "l33t";

	obj.print_pass(); // whoa!!

	// For other data types
	int* id = (int*)(password + 1);
	std::cout << "ID: " << *id << std::endl;

	return 0;
}

Observem que na linha 5, peguei o endereço do atributo name e fiz a mesma coisa do exemplo anterior.

Para os dois exemplos a saída é a mesma:

Name: John
Password was: s3cr3t
The current password is: l33t
ID: 10

Voltando à minha dúvida inicial…

Conclusão: pelo menos no compilador g++, a proteção é feita apenas pelo compilador (compile-time) e nenhum outro tipo de impedimento é usado. Ou seja, se você “adivinhar” o endereço de memória de um atributo de um objeto, você poderá ter acesso total à ele e aos outros atributos desse objeto.

Então, na hora de desenvolvermos nossas classes em C++, nada de retornar ponteiros para atributos de um objeto, nem de deixar atributos public quando se tem outros atributos não-public.

Update

Logo depois de eu fazer esse post, o WP automaticamente postou em meu Twitter e Facebook o link para este post. No Facebook recebi um comentário de um excelente programador o Maurício Collares (ou MauricioC no TopCoder[1]). Acho pertinente colar o comentário e também minha reposta aqui uma vez que estou vendo que esse post está tendo uma grande quantidade de leituras.

Maurício Collares Neto: Não sei se entendi qual o problema de alguém que já tem acesso de leitura à posicao “secreta” de memória (no sentido de não tomar um SIGSEGV) acessar tal posicao. Private e public são anotacoes existentes por motivos de Engenharia de Software, para evitar quebra de abstracoes; a grande maioria das linguagens oferece um jeito “fácil” de quebrar tal abstracao caso você precise fazê-lo (vide instrospeccao em Java).

Além disso, se você tem o endereco da da instäncia da classe (que pode ser obtido mesmo que vocë náo tenha nenhum membro público), você já tem acesso ao endereco de memória de todas as outras variáveis, do mesmo jeito; membros de classes são só syntactic sugar pra aritmética de ponteiros.

Murilo Adriano Vasconcelos: Interessante, eu não tinha pensado no fato de através do endereço do objeto podemos facilmente acessar qualquer atributo do objeto. E pensando melhor, mesmo que não houvesse esse tipo de facilidade no ponto de vista de objetos, teríamos acesso de alguma forma no no ponto de vista de processos, já que os processos tem total acesso às àreas de memória alocadas por ele.

Assim, e com o que você disse, fica totalmente anula o sentido do título do post (já que, por exemplo, seria o mesmo que dizer “Nunca instancie objetos”, um absurdo), porém poderei fazer uma atualização no post no sentido de apenas expor essa “feature” adicionando essa idéia de através de uma instância da classe acessar os outros atributos.

De qualquer forma, valeu pelo comentário, pena que foi só aqui no FB e não no blog, onde mais pessoas poderiam ter acesso à essa conversa.

Referências

[0] - Aritmética de ponteiros em C e C++ (Wikipedia)

[1] – TopCoder

Políticas de Controle de Comportamento em C++

Trabalhando no meu projeto na Boost, fui requisitado a implementar uma função para calcular o logaritmo na base 2 de números inteiros. De prontidão pesquisei qual a melhor forma e implementei-a da maneira mais otimizada possível. Fiz um Request For Comments (RFC) na mail list da Boost para saber opiniões sobre qual deveria ser o nome de tal função. Bom, depois de alguma conversa ficou (ao menos por enquanto) decidido que o melhor nome é ilog2.

Bom mas havia um problema logaritmo de 0 é indefinido. E na documentação eu coloquei:

If `value` is equal to 0, the value returned is undefined

Foi aí que um contribuidor da Boost chamado Paul Bristow recomendou a mim que fizesse com que esse comportamento (ilog2(0)) pudesse ser controlável através de políticas, mais especificamente usando boost::math::policies. Resisti um pouco no começo mas cedi e achei bastante interessante.

O que são políticas de tratamento de comportamento?

Basicamente são meios de controlar o comportamento de um algoritmo em certas situações (como o ilog2(0) por exemplo).

Um exemplo de política muito utilizada na biblioteca padrão são as classes que usam std::allocator.

Em C++ podemos implementar políticas facilmente em tempo de compilação.

Implementando Políticas

Vamos então implementar um modelo de política bem simples. Tomei por base as Policies da biblioteca Math da Boost, porém muito mais simplificada por questão de didática.

#ifndef POLICIES_HPP_INCLUDED
#define POLICIES_HPP_INCLUDED

#include <cerrno>      // errno
#include <stdexcept> // std::domain_error

namespace policies
{

// Nossa política
enum error_policy_type
{
	ignore_error = 0,
	errno_on_error,
	throw_on_error,
	user_error
};

// continua

Esse enum define a regra que queremos utilizar em nossa política.

• ignore_error: ignora o erro e retorna um valor padrão.
• errno_on_error: seta errno e retorna um valor padrão.
• throw_on_error: dispara uma exceção.
• user_error: executa uma função customizada definida pelo usuário, note que a declaração dessa função já existe, tendo apenas que ser feita a definição dessa função.

No caso defini 4 tipos de erros mas pode-se ter mais coisas como “dialog_on_error” se seu projeto utiliza GUI e você quer que apareça uma dialog box informando algo, de qualquer maneira pode-se também usar o user_error se for aplicável.

// continuação

template <int P>
struct domain_error
{
	const static int policy = P;
};

template <int P>
struct overflow_error
{
	const static int policy = P;
};

Aqui declaramos nossos tipos de erro. É basicamente um wrapper para nossas constantes declaradas no enum anterior. P é a política que queremos aplicar. Por exemplo typedef overflow_error<errno_on_error> my_pol;, my_pol é uma política que para tratar overflow_error seguindo a regra errno_on_error. Novamente podemos ter vários tipos de erros que queiramos tratar, coloquei esses dois como exemplo. Notemos também que para simplicidade não tratei os possíveis valores que P pode assumir.

typedef domain_error<ignore_error> default_domain_policy;
typedef overflow_error<errno_on_error> default_overflow_policy;

Aqui definimos quais as políticas padrões para cada tipo de erro. No caso definimos que a política padrão que deve ser seguida quando um domain_error for lançado é a ignore_error. Veremos mais para frente sugestões de como tratar cada política.

// Only the declaration, must be defined somewhere
template <typename T>
T user_domain_error(const char* function, const char* message, const T& val);

template <typename T>
T user_overflow_error(const char* function, const char* message, const T& val);

Aqui nós apenas declaramos os protótipos das funções que serão chamadas quando um user_error for lançado. Se alguém usar a política user_error, este deverá codificar essas funções em algum outro lugar.

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<ignore_error>&)
{
	// Simply ignoring the error
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<errno_on_error>&)
{
	// Sets errno to Error DOMain
	errno = EDOM;
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<throw_on_error>&)
{
	throw std::domain_error(message);
	
	// This will never be returned
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<user_error>&)
{
	return user_domain_error(function, message, val);
}

}

Essas são as funções chamadas para lançar um domain_error. Note que para cada política definimos uma função para tratá-la. Por questão de simplicidade, defini apenas as funções que tratam as políticas de domain_error, para overflow_error por exemplo, precisaríamos definir raise_overflow_error() com sobrecargas para cada política diferente.

O protótipo das funções pode ser modificado de acordo com o que você necessitar. Aqui defini quatro parâmetros:

• function – o nome da função que causou o comportamento (erro)
• message – a descrição do que causou o comportamento.
• val – o valor que essa função deve retornar (quando aplicável)
• const policies::domain_error& – utilizado para fazer a sobrecarga de função, onde X é a política a ser tratada.

Pode paracer meio desgastante porém depois de pronto, seu sistema complexo pode se beneficiar com transparência das políticas que não devem ser tantas.

A Boost Math por exemplo define apenas 6 tipos de erros e as mesmas 4 políticas que estou usando como exemplo.

Exemplo de uso

Agora suponhamos que tenhamos que implementar uma função que faz a divisão de dois elementos a e b (ohhh divisão!). Essa função, chamada divide, está sendo representada abaixo.

Como sabemos, divisão por zero não existe, então para uma solução elegante para nossa função super complexa, iremos utilizar as nossas políticas.

#include "policies.hpp"

template <typename T, typename Policy>
T divide(T a, T b, const Policy& pol)
{
	if (b == 0) {
		return policies::raise_domain_error("divide(a, b)", 
			"Cannot divide by zero", 
			T(0),   // Value to be returned  
			pol  // Our policy
		);
	}
	
	return a / b;
}

template <typename T>
inline T divide(T a, T b)
{
	return divide(a, b, policies::default_policy());
}

Como pudemos notar, declarei duas funções divide, uma aceitando dois parâmetros que serão computados e a outra aceitando um parâmetro a mais que é a política a ser utilizada. A versão de dois parâmetros na verdade é somente um forwarder para a outra passando a política padrão para ser utilizada. O valor padrão a ser retornado é 0, como podemos notar em T(0).

O “mau” comportamento ocorre quando b == 0, então, se essa condição for satisfeita, simplesmente lançamos um domain_error utilizando a função raise_domain_error.

Para o usuário da função isso é transparente se ele não quiser trabalhar com as políticas, já que uma política padrão é adotada e um valor padrão é retornado.

int main()
{	
	using namespace policies;
	
        // Default policy, zero is returned
	assert((divide(1, 0) == 0));

	typedef domain_error<errno_on_error> errno_pol;
	typedef domain_error<ignore_error>   ignore_pol;
	typedef domain_error<throw_on_error> throw_pol;
	
	// Testing errno_on_error policy, errno is set equal EDOM
	errno = 0;
	divide(1, 0, errno_pol());
	assert((errno == EDOM));
	
	// Testing ignore_error policy, zero is returned
	assert((divide(1, 0, ignore_pol()) == 0));
	
	// Testing throw_on_error policy, a std::domain_error is threw
	try {
		divide(1, 0, throw_pol());
		
		// Never is threw
		throw "error 0";
	}
	catch (std::domain_error&) {
		// FINE!!!
        // Sucessfully caught!
	}
	catch (...) {
                // Bad!
		throw "error 1";
	}
	
	return 0;
}

Se estiver tudo certo, programa acima deve (após ser compilado) ser executado sem nenhuma saída e com nenhuma exceção.

Ficou agora faltando demonstrar apenas como usar as políticas com user_error.

#include <iostream>
#include "policies.hpp"
#include "divide.hpp"

namespace policies {
template <typename T>
T user_domain_error(const char* function, const char* message, const T& val)
{
	std::cout << "Problem on calling function "<< function << std::endl;
	std::cout << "Value " << val << " will be returned " << std::endl;
	
	// DialogBox db(message); or anything you want
	
	return val;
}
}

int main()
{
	policies::domain_error<policies::user_error> usr_err;
	divide(1, 0, usr_err);
        /*  Saída:
  	     Problem on calling function divide(a, b)
             Value 0 will be returned 
         */

	return 0;
}

Como pudemos ver, basta apenas definirmos a função user_domain_error do modo que quisermos para que possamos usar essa política. No caso acima apenas imprimimos uma mensagem com duas linhas e retornamos val.

Arquivos

policies.hpp
divide.hpp
policies_example.cpp
user_error.cpp

Referências

Boost Math Policies
ilog2 implementation
Policy Classes On Generic Programming Techniques from Boost

C++ Idioms: SFINAE

Introdução

Nesse post falarei sobre uma técnica (ou recurso) utilizada em  C++ que estou utilizando muito no meu projeto[0][1] na Boost Libraries[2] no GSoC, essa técnica é o SFINAE.

SFINAE[3] é uma sigla para “Substitution failure is not an error” que em uma tradução livre quer dizer “Falha na substituição não é um erro”. Segundo[3]:

SFINAE se refere a uma situação em C++ que uma substituição inválida de templates não é um erro.

Especificamente, na criação de um conjunto candidato para a resolução de sobrecarga, alguns (talvez todos) os candidatos deste conjunto pode ser resultante da substituição de argumentos templates deduzidos para os parâmetros de template. Se um erro ocorre durante a substituição, o compilador remove essa potencial sobrecarga do conjunto candidato ao invés de parar com um erro de compilação. Se restam um ou mais candidatos (i.é: pelo menos uma sobrecarga é válida), a resolução é feita e a invocação é bem formada.

Como funciona

Para entender melhor vejamos esse trecho de código:

template <typename T>
struct A
{
	typedef T type;
	T value;
};

template <>
struct A<bool>
{
};

template<typename T>
typename A<T>::type func(const A<T>& param)
{
	std::cout << param.value << std::endl;
}

Esse código compila sem warnings. A função template func() é sobrecarregada e retorna o tipo T. Mas você deve estar se perguntando, o que acontece quando T = bool? Esse é justo o ponto do SFINAE!
Para T = bool, typename A::type seria uma declaração inválida já que A não contém o tipo type declarado, porém, com SFINAE, essa sobrecarga é simplesmente descartada e para qualquer outro T que não bool, func(A) é uma chamada legal porque sua sobrecarga é gerada.

Aplicações

Como eu disse no começo deste post eu estou utilizando bastante SFINAE no meu projeto do Google Summer of Code com uma utilidade chamada enable_if[4] encontrado na Boost.

Enable_if é uma classe (ou struct) que “ativa” a declaração de algo (classe, função, etc) se uma condição for satisfeita por meio do SFINAE. Vou mostrar aqui uma maneira de fazer um enable_if like, e quem quiser saber mais sobre o enable_if da Boost é encorajado a ler[4][5].

Vamos ao código:

/* Cond é a condição de ativação
 * Type é o tipo que será declarado pelo membro type.
 */
template <bool Cond, typename Type = void>
struct enable_if_c
{
	typedef Type type;
};

/*
 * Especialização, quando Cond for false,
 * 	esse template vazio é invocado.
 */
template <typename Type>
struct enable_if_c<false, Type>
{
	// empty
};

Ou seja, sempre quando Cond for true, existirá um membro type declarado em enable_if_c, quando Cond for false o membro type não existirá.

Um exemplo de uso:

/*
 * Nossa função pega o bit mais significativo de value e retorna um bool.
 * 	***Note que nesse exemplo estamos assumindo que T é um tipo inteiro.***
 */

/*
 * Para retornar o bit mais significativo de um T com 4bytes (32 bits),
 * 	deslocamos 31 bits para a direita e fazemos um & com 1.
 */
template <typename T>
typename enable_if_c<sizeof(T) == 4, bool>::type msb(T value)
{
	std::cout << "Value have 4 bytes.\n";
	return (value >> 31) & T(1);
}

/*
 * Porém se T é um tipo de 1byte (8 bits) o deslocamento deve ser de
 * 	7 bits para pegarmos o bit mais significativo.
 */
template <typename T>
typename enable_if_c<sizeof(T) == 1, bool>::type msb(T value)
{
	std::cout << "Value have 1 byte.\n";
	return (value >> 7) & T(1);
}

Ou seja, a função de cima, é sobrecarregada para todos os tipos que tenham 32 bits (sizeof(T) == 4) e a de baixo é sobrecarregada para todos os tipos que tenham 8 bits (sizeof(T) == 1). Assim, no processo de resolução de sobrecarga, os outros tipos que não tem nem 8 nem 32 bits, são descartadas pois cairá na especialização enable_if_c que não possui um membro type (usado como retorno da função msb), comportamento citado anteriormente.

Para testar:

int main()
{
	int a = -3;
	unsigned b = 190000;
	char c = 129;
	uint16_t d = 10;
	uint64_t e = 10000000;
	
	std::cout << "Retorno int: " << msb(a) << std::endl;
	std::cout << "Retorno unsigned: " << msb(b) << std::endl;
	std::cout << "Retorno char: " << msb(c) << std::endl;
}

Se tentarmos executar com uma condição que não é true, teremos um erro em tempo de compilação, como podemos ver abaixo:

...
uint16_t d = 10;
uint64_t e = 10000000;

std::cout << "Ret: uint16_t: " << msb(d) << std::endl
std::cout << "Ret: uint64_t: " << msb(e) << std::endl;
...

/*
/Users/murilo/Documents/programming/blog/sfinae.cpp: In function ‘int main()’: /Users/murilo/Documents/programming/blog/sfinae.cpp:61: error: no matching function for call to ‘msb(uint16_t&)’ 
/Users/murilo/Documents/programming/blog/sfinae.cpp:62: error: no matching function for call to ‘msb(uint64_t&)’
*/

Alguns outros exemplos usando o enable_if da Boost você pode encontrar no meu projeto[1] na Boost onde utilizo enable_if aos montes.

Nesse post exemplifiquei SFINAE com funções, mas também é aplicável para classes. Um exemplo você pode ver aqui [6].

Até a próxima!

Referências

[0] – Estou no Google Summer of Code 2010 – http://murilo.wordpress.com/2010/05/03/estou-no-google-summer-of-code-2010
[1] – Source of Bits and Ints project – https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boost/integer
[2] – Boost C++ Libraries – http://www.boost.org/
[3] – Artigo “Substitution failure is not an error” na Wikipedia – http://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
[4] – Boost enable_if – http://www.boost.org/doc/libs/1_43_0/libs/utility/enable_if.html
[5] – enable_if.hpp – http://www.boost.org/doc/libs/1_35_0/boost/utility/enable_if.hpp
[6] – static_sign_extend.hpp at Boost Trac – https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boost/integer/static_sign_extend.hpp