Dr. Carlo Pescio
Misurare un array a compile-time

Pubblicato su C++ Informer No. 9, Settembre/Ottobre 1999

L'argomento discusso in questa puntata di "No Limits" nasce in modo un po' strano. Nel numero di Settembre 98 del C++ Users Journal, Bobby Schmidt presento' una tecnica per "misurare" un array monodimensionale usando i template. Nel numero di Febbraio 99, lo stesso autore pubblico' la lettera di uno sviluppatore Microsoft, che lamentava alcuni problemi della soluzione proposta. Bobby Schmidt lancio' la palla ai lettori, e la sfida venne prontamente raccolta da... me :-).
Nel numero di Luglio 99 (i soliti tempi epocali delle riviste, che mi piacerebbe riuscire a superare con Informer) sul C++ User Journal apparve la mia soluzione al problema, che in una sorta di rigurgito accademico :-) propose anche la sfida di una generalizzazione multidimensionale (che piu' che altro si rivela una sfida a scrivere codice accettato da qualche compilatore esistente).
Schmidt lascio' la mia sfida come esercizio per i lettori del CUJ. Voi lettori di Informer, invece, troverete di seguito tutta la storia, inclusa una discussione iniziale sullo stile di codifica, che in qualche modo giustifica le contorsioni che seguiranno.

Quanto e' grande l'array?
Prendiamo come esempio il seguente, orripilante :-) codice:
void f()
  {
  char a[ 100 ] ;
  FILE* f ;
  // ...
  fread( a, sizeof( char ), 100, f ) ;
  // ...
  }

Il lato oscuro del codice e' ovviamente l'uso di literal numerici, con i conseguenti problemi di manutenzione di cui ho naturalmente parlato nel Manuale di Stile. In particolare, e' facile aggiornare una delle due occorrenze di 100 senza aggiornare l'altra (soprattutto in funzioni piu' lunghe ed intricate, o quando a e' una variabile globale o un data member, ecc), ed e' altrettanto facile ricorrere alla forza bruta del search&replace e sostituire anche altre occorrenze di 100 che nulla hanno a che vedere con le due in questione. Ancora peggio, ovviamente, se le occorrenze sono numerose e se vi sono altre variabili che, almeno in una versione iniziale del programma, hanno "per caso" la stessa dimensione di a.

Il consiglio abituale (che e' generalmente anche il mio) e' di usare delle costanti simboliche anziche' dei literal. In questo caso avremmo:

void f()
  {
  const int MaxSize = 100 ;
  char a[ MaxSize ] ;
  FILE* f ;
  // ...
  fread( a, sizeof( char ), MaxSize, f ) ;
  // ...
  }
Questo ci protegge da una categoria di errori molto ampia, anche se molti programmatori, scrivendo il codice un po' in fretta, non hanno voglia/tempo di introdurre costanti simboliche al posto dei literal numerici.
La soluzione sopra non e' comunque perfetta, perche' e' ancora possibile scrivere cose del tipo:

void f()
  {
  const int MaxLen = 100 ;
  char a[ MaxLen ] ;
  const int MaxPath = 50 ;
  char b[ MaxPath ] ;
  FILE* f ;
  // ...
  fread( a, sizeof( char ), MaxPath, f ) ;
  // ...
  }
ovvero usare la costante sbagliata. Sarebbe bello se potessimo semplicemente dire "usa la lunghezza di a", cosi' come scriviamo "sizeof( char )" invece di scrivere 1 e senza necessita' di introdurre costanti simboliche. (In tutta onesta', neppure questa soluzione sarebbe immune da problemi di manutenzione, che vi lascio immaginare come esercizio; diciamo che e' comunque una delle piu' resilienti).

La (brutta :-) macro LENGTHOF
I programmatori piu' esperti avranno ormai detto "ma c'e' un modo facile per farlo...", ovvero usare una macro come la seguente:

#define LENGTHOF( a ) ( sizeof( a ) / sizeof( *a ) )
La macro divide la dimensione (in char) dell'array per la dimensione (in char) di un elemento (il primo) dell'array, ottenendo quindi il numero di elementi dell'array.
La macro ha pero' due difetti. Il primo e' legato alla natura perfida :-) delle macro: poiche' vengono valutate dal preprocessore, le macro ignorano ogni idea di scope, e si estendono ovunque nell'unita' di compilazione. E' un problema che in qualche modo potremmo anche tollerare.
Il secondo difetto, molto piu' serio in questo contesto, e' l'incapacita' della suddetta macro di distinguere tra puntatori ed array (che non sono la stessa cosa, per quanto alcuni pensino il contrario):

char* p = new char[ 100 ] ;
int x = LENGTHOF( p ) ; // ovviamente NON e' 100
Una buona soluzione al problema di LENGTHOF dovrebbe dare un errore di compilazione se applicata ad un puntatore, in quanto applicabile solo ad un array.

La soluzione di Schmidt
L'idea di fondo di quanto stiamo per vedere e' semplice: usare la deduzione implicita dei parametri di una template function per trovare il numero di elementi dell'array. Allo stesso tempo, dobbiamo scrivere la funzione template in modo da accettare solo array e non puntatori, ed in modo da evitare sia costose copie sia la degenerazione di un array nel puntatore al suo primo elemento.
Warning: il codice seguente richiede un buon compilatore; questo elimina dalla discussione il pur diffuso Visual C++, sino alla versione 6. Potete invece usare il GCC 2.95 per le vostre prove.

template< class T, size_t L > inline size_t lengthof( T (&)[ L ] )
  {
  return( L ) ;
  }
La inusuale sintassi T (&)[ L ] dichiara un reference senza nome ad un array di L elementi di tipo T. Potevamo ovviamente dare un nome al parametro, scrivendo ad es. T (&a)[ L ], ma avremmo ricevuto un warning dal compilatore, in quanto il parametro non viene utilizzato: di fatto, a noi interessa solo L, che il compilatore e' cosi' gentile da dedurre per noi.
Con l'ausilio di lengthof, il nostro esempio originale diventa:
void f()
  {
  char a[ 100 ] ;
  FILE* f ;
  // ...
  fread( a, sizeof( char ), lengthof( a ), f ) ;
  // ...
  }

Vi lascio il compito di decidere se valga o meno la pena di passare ad una costante simbolica anche in questo caso, ma sicuramente possiamo osservare una migliorata manutenibilita'. I lettori piu' attenti potranno pensare a come utilizzare una variante di quanto sopra per scrivere un wrapper per fread, che consenta di scrivere cio' che e' realmente indispensabile:
fread_all( a, f ) ;

lasciando tutto il resto a carico del compilatore.

La soluzione di Schmidt, come anticipato, non e' perfetta. In particolare, il succitato sviluppatore Microsoft (che avra' usato un compilatore non Microsoft per provarla :-) faceva notare due problemi, nessuno dei quali presenti nella (brutta) macro LENGTHOF:

1) Non funziona se il tipo T e' una local class, ad esempio:
void f()
  {
  class A
    {
    // ...
    } ;

  A x[ 100 ] ;
  lengthof( x ) ; // errore di compilazione
  }

Questo avviene in quanto non e' possibile istanziare un template su argomenti che non hanno external linkage, come le local class.
Si tratta a mio avviso di un problema minore, perche' le local class non sono molto utilizzate, e sicuramente accetterei di buon grado questo limite in cambio della maggior sicurezza rispetto a LENGTHOF.

2) Il risultato non e' una compile-time constant, ovvero non posso scrivere:
void f()
  {
  char a[ 100 ] ;
  int b[ lengthof( a ) ] ; // stessa lunghezza di a, ma int; purtroppo errore!
  }

la chiamata di una funzione, infatti, non da' come risultato una compile-time constant utilizzabile (ad es.) per dimensionare un array.
Siccome parte della convenienza di lengthof sta proprio nella possibilita' di scrivere codice piu' chiaro e manutenibile anche senza costringere il programmatore a fare qualcosa che tipicamente non vuole fare (dichiarare tutte le costanti simboliche del caso), l'impossibilita' di usare lengthof in una situazione molto comune (dichiarare un array grande quanto un altro) e' decisamente fastidiosa.

La mia soluzione
Come ormai saprete, superare i limiti convenzionali del C++ e' per me diventata una specie di missione :-), ed una volta letto il numero di settembre di CUJ non ho potuto evitare di cadere in tentazione.
Il problema sembra difficile, perche' da un lato abbiamo bisogno di una chiamata di funzione per sfruttare la deduzione implicita dei parametri (che in C++ esiste solo per le template function), dall'altra proprio la presenza di una chiamata di funzione ci impedisce di avere una costante compile-time.
A dire il vero la soluzione che ho poi proposto al CUJ e' piuttosto semplice, basta conoscere un risvolto apparentemente minore del C++ ed avere un po' di fantasia.
Se vogliamo ottenere una costante compile-time, il C++ non ci mette a disposizione molte possibilita': in particolare (si veda lo standard al punto 5.19 per i dettagli), una espressione aritmetica costante puo' avere tra i suoi parametri solo dei literal, delle costanti inizializzate, dei parametri non-tipo dei template, e... delle chiamate a sizeof.
Sinora l'uso di sizeof nell'aritmetica compile-time e' stato piuttosto limitato, ma sizeof ha una importante proprieta': se applichiamo sizeof ad una chiamata di funzione, la funzione non viene chiamata, ed il risultato e' una compile-time constant che ha come valore la dimensione (in char) del tipo del risultato.
In altre parole, se avessimo:
int f( double x ) ;

allora sizeof( f( 4.2 ) ) sarebbe una costante compile-time avente come valore sizeof( int ), ed f non verrebbe chiamata.
Come possiamo utilizzare tutto questo per risolvere il problema originale, ovvero misurare l'array a compile-time? Creando una funzione template che abbia un risultato la cui grandezza (non il valore!) sia uguale alla dimensione dell'array:

template< int N > struct Sized
  {
  char x[ N ] ;
  } ;

template< class T, int N > Sized< N > lengthof( T (&)[ N ] ) ;

// esempio
void f()
  {
  int a[ 100 ] ;
  double b[ sizeof( lengthof( a ) ) ] ; // stessa dimensione di a
  }
Analizziamo bene il codice, che e' una variante di quanto ho originariamente proposto al CUJ. Il template Sized ha l'unico compito di fornire una struttura di dimensione specificata. La funzione lengthof ha gli stessi parametri di quella proposta da Schmidt, ma un diverso tipo del risultato. Se Schmidt usava size_t per il risultato, e faceva restituire a lengthof la dimensione dell'array, io uso Sized< N > per il risultato.
Di conseguenza, una chiamata come lengthof( a ) ha come tipo del risultato Sized< N >, dove N e' il numero di elementi di a. A questo punto sizeof( lengthof( a ) ) restituisce N come costante compile time, come possiamo vedere nell'esempio sopra.
Nel codice che ho spedito al CUJ la funzione lengthof era anche implementata. A posteriori, ho realizzato che l'implementazione e' inutile, in quanto la funzione non viene mai chiamata, e sizeof ha solo bisogno del prototipo per operare correttamente.
Non vi nascondo che la sintassi e' un po' scomoda, e personalmente rinominerei lengthof in LengthofHelper ed userei una macro LENGTHOF scritta come segue:

#define LENGTHOF( a ) sizeof( LengthofHelper( a ) )
Ma lascio la decisione a voi. Potreste in alternativa trovare un nome piu' leggibile per lengthof nel contesto di sizeof, ad es. sizeof( thearray( a ) ) o qualcosa di simile.

Estensioni multidimensionali
Il mio breve intervento sul CUJ si concludeva con una sfida, ovvero fornire una estensione di quanto presentato per gli array multidimensionali. Come accennavo, Schmidt ha lasciato l'esercizio ai lettori, e non pochi hanno recuperato il mio indirizzo di email da altri articoli per chiedermi una soluzione. A questo punto, ho pensato di praticare quello che predico sempre (il riuso del codice :-) e di proporre il risultato finale anche ai lettori di C++ Informer.

L'obiettivo e' scrivere un analogo di lengthof, che mantenendo gli stessi criteri di type safety sia in grado di operare su array multidimensionali. Il codice seguente illustra un possibile utilizzo, ipotizzando delle macro opportune:

int xx[ 11 ][ 12 ][ 13 ][ 14 ] ;

const int r = RANK( xx ) ; // restituisce il numero di dimensioni di xx (4)

const int l = LENGTHOF( xx ) ; // 11
const int l0 = LENGHTOF_ALONG( xx, 0 ) ; // sempre 11, size lungo l'asse 0
const int l1 = LENGHTOF_ALONG( xx, 2 ) ; // 13, size lungo l'asse 2
// ecc
Ovviamente, vorrei che la richiesta della size lungo un asse con indice scorretto (es. LENGHTOF_DIM( xx, 20 ) ) desse luogo ad un errore di compilazione, e che tutti i risultati fossero delle costanti compile-time.

Come anticipato in apertura, la vera sfida si e' dimostrata essere la stesura di codice compilabile da qualche compilatore reale. Scartato il Visual C++ sin dall'inizio, in quanto incapace di comprendere i reference ad array nei template, ho deciso di trovare una implementazione che superasse la compilazione almeno con il GCC 2.95. Cio' che vi presento e' il risultato di una lunga sequenza di errori inverosimili (codice compilato dal front-end ma che generava un assembly incomprensibile per il back-end, internal errors vari del compilatore, eccetera), a riprova che quando ci si spinge sui confini, non basta scrivere codice conforme allo standard, ma bisogna lottare con i limiti dei compilatori disponibili.

RANK
Una volta introdotto il template Sized, e compresa la tecnica del sizeof() applicato ad una helper function, la macro RANK ed il template sottostante sono poco piu' che un esercizio di metaprogrammazione:

template< class T > struct RankHelperStruct
  {
  enum { val = 0 } ;
  } ;

template< class T, int N > struct RankHelperStruct< T[ N ] >
  {
  enum { val = 1 + RankHelperStruct< T > :: val } ;
  } ;
template< class T > Sized< RankHelperStruct< T >::val > RankHelper( T& ) ;

#define RANK( x ) sizeof( RankHelper( x ) )

Vediamo come funziona; quando scriviamo qualcosa del tipo:
int xx[ 11 ][ 12 ][ 13 ][ 14 ] ;
const int a = RANK( xx ) ;

e' come se scrivessimo:
const int a = sizeof( Sized< RankHelperStruct< int[11][12][13][14] >::val > ) ;

Poiche' sizeof e Sized "si annullano" a vicenda, il risultato e' una costante compile-time con il valore di
RankHelperStruct< int[11][12][13][14] >::val 
Notiamo che e' necessario passare per Sized, altrimenti non riusciremmo a sfruttare la deduzione dei tipi per il parametro.
RankHelperStruct e' un semplice metaprogramma (vi rimando ad [1], disponibile sulla mia web page, per una introduzione all'argomento) che "conta" il numero di dimensioni. Il funzionamento e' piuttosto semplice: per un tipo base, il numero di dimensioni e' zero. Per un array, il numero di dimensioni e' dato da 1 + il numero di dimensioni del tipo degli elementi. Questo si esprime in un metaprogramma usando la specializzazione parziale dei template per la clausola con parametro di tipo array. Studiate un po' il codice e vedrete che e' di fatto molto semplice.

LENGHTOF_ALONG
Questo e' decisamente piu' complicato, o perlomeno e' stato piu' complicato superare i problemi dei compilatori. Lascio da parte i vari tentativi sprecati (in parte per ragioni di spazio, in parte per ragioni di memoria :-) per mostrarvi direttamente il risultato finale. Parte della difficolta' risiede nella mutua ricorsione tra la helper struct (analoga a quella usata per Rank) e la helper function.

template< int A, class T, int N > struct LengthofAlongHelperStruct ;

template< int A, class T, int N > LengthofAlongHelperStruct< A, T, N > LengthofAlongHelper( T(&)[ N ] ) ;

template< int A, class T, int N > struct LengthofAlongHelperStruct
  {
  enum { val = sizeof( LengthofAlongHelper< A - 1 >( *(new T[0]) ) ) } ;
  Sized< val > v ;
  } ;
template< class T, int N > struct LengthofAlongHelperStruct< 0, T, N >
  {
  enum { val = N } ;
  Sized< val > v ;
  } ;

#define LENGTHOF_ALONG( x, d ) sizeof( LengthofAlongHelper< d >( x ) )


Vediamo come funziona; quando scriviamo qualcosa del tipo:
int xx[ 11 ][ 12 ][ 13 ][ 14 ] ;
const int a = LENGTHOF_ALONG( xx, 2 ) ;

e' come se scrivessimo:
const int a = sizeof( LengthofAlongHelper< 2 >( x ) ) ;

ovvero
const int a = sizeof( LengthofAlongHelperStruct< 2, int[ 11 ][ 12 ][ 13 ][ 14 ], 11 > ) ;

A questo punto vediamo quale e' il ruolo di LengthofAlongHelperStruct: se il primo parametro (l'asse alla cui dimensione siamo interessati) e' zero, la dimensione si trova nell'ultimo parametro del template: infatti, nella prima chiamata abbiamo come ultimo parametro la dimensione secondo l'asse zero.
Altrimenti, LengthofAlongHelperStruct deve in qualche modo "semplificare" i parametri e fare una chiamata ricorsiva, ovviamente mantenendo i valori corretti nei parametri attuali.
La gestione della dimensione secondo l'asse zero e' implementata con la specializzazione parziale del template:
template< class T, int N > struct LengthofAlongHelperStruct< 0, T, N >
  {
  enum { val = N } ;
  Sized< val > v ;
  } ;
In questo caso si crea infatti una struttura di dimensione pari al valore dell'ultimo parametro, ed il solito giochino con sizeof() fa il resto.
Il difficile e' scrivere la clausola generale/ricorsiva. Il modo piu' semplice (per quanto si puo') di scriverla sarebbe il seguente:

template< int A, class T, int N > struct LengthofAlongHelperStruct
  {
  enum { val = sizeof( LengthofAlongHelper< A - 1 >( T() ) ) } ;
  Sized< val > v ;
  } ;
Ovvero: quando A e' maggiore di zero, la dimensione secondo l'asse A di un array con N elementi di tipo T e' uguale alla dimensione secondo l'asse (A - 1) del tipo T stesso (che deve essere a sua volta un array).
Purtroppo questo genera un errore di compilazione con GCC. Lo stesso avviene con diverse varianti che ho provato, sino a quando ho sostituito all'espressione T() (che dovrebbe generare un temporaneo di tipo T, ma che il compilatore interpreta come un cast) l'espressione seguente:
 (new T[0]) 
Notiamo che (new T[0]) ha come tipo T*, e quindi *(new T[0]) ha come tipo T, come si voleva. E' fondamentale usare T[0] e non semplicemente T, perche' quando T e', ad es., int[ 12 ], *( new T[ 0 ] ) ha come tipo int[ 12 ], ma *( new T ) ha come tipo int! Naturalmente, siccome l'unico scopo dell'espressione in questione e' di ottenere il tipo giusto nella chiamata ricorsiva del metaprogramma, un'espressione vale l'altra: non verra' mai chiamata a run-time, quindi non esiste il problema del costo di esecuzione o dell'apparente memory leak. Vi confesso comunque di aver buttato via un'oretta nella ricerca di una espressione che non facesse inchiodare, per una ragione o l'altra, il compilatore. Il metaprogramma dato sopra genera giustamente un errore di compilazione quando cerchiamo di chiedere la dimensione lungo un asse inesistente. Vi lascio come esercizio capire perche' (qualche "esercizio per il lettore" ci vuole sempre :-).

Conclusioni
Un problema apparentemente semplice (contare gli elementi di un array) si rivela in realta' molto complicato quando cerchiamo di affrontarlo nella sua totalita' (array multidimensionali), cercando di ottenere la necessaria type safety (assente nella LENGTHOF originale) e soprattutto di ottenere come risultato una costante compile-time.
In effetti, la metaprogrammazione template in C++ e' ancora allo stato "artistico", e le trovate creative si devono spesso unire a qualche virtuosismo per superare i limiti dei compilatori. Cio' non toglie che, con un po' di impegno, si possa utilizzare per scrivere codice totalmente standard-compliant (come quello visto sopra) che risolve problemi altrimenti impossibili da affrontare.

Bibliografia
[1] Carlo Pescio, "Algoritmi come Metaprogrammi Template in C++", Computer Programming No. 56.

Biografia
Carlo Pescio (pescio@eptacom.net) svolge attività di consulenza, progettazione e formazione in ambito internazionale. Ha svolto la funzione di Software Architect in grandi progetti per importanti aziende europee e statunitensi. È autore di numerosi articoli su temi di ingegneria del software, programmazione C++ e tecnologia ad oggetti, apparsi sui principali periodici statunitensi, nonché dei testi "C++ Manuale di Stile" ed "UML Manuale di Stile". Laureato in Scienze dell'Informazione, è membro dell'ACM, dell'IEEE e dell'IEEE Technical Council on Software Engineering.