Dr. Carlo Pescio
Meta-morfismo in C++

Pubblicato su C++ Informer No. 6, Gennaio 1999
Meta-morfismo in C++

Alcuni mesi fa, in un articolo apparso su Computer Programming [1], ho discusso l'utilizzo dell'ereditarieta' in rapporto alle caratteristiche di molti linguaggi di programmazione con type checking statico. Una delle principali caratteristiche di questi linguaggi (alla cui famiglia appartiene anche il C++) e' che gli oggetti non possono (in teoria) cambiare classe.
Vediamo un esempio: se abbiamo una semplice gerarchia, con classe base B e due distinte classi derivate C e D, possiamo naturalmente creare un oggetto di classe C e "vederlo" tramite un puntatore a B; questo e' il primo passo verso il polimorfismo in C++. Cio' che non possiamo fare, almeno non in modo banale, e' cambiare la classe di quell'oggetto e farlo diventare, ad esempio, di classe D, pur mantenendo la sua identita'. Cosa significa identita'? Diverse cose, ma dal punto di vista pragmatico significa che ogni puntatore esistente all'oggetto originale rimane valido, solo che ora punta ad un oggetto di un'altra classe.
In linguaggi con controllo dinamico sui tipi il cambio di classe non e' molto problematico; apparentemente, in C++ siamo invece costretti ad utilizzare modelli alternativi. Infatti, come ho spiegato piu' in dettaglio nel succitato [1], molto spesso possiamo riprogettare la nostra gerarchia di classi ed ottenere un modello che non richiede "cambi di classe" agli oggetti. D'altra parte, questo modello alternativo e' spesso basato su "classi ruolo" e richiede pertanto un livello di indirezione aggiuntivo. Di norma il rallentamento cosi' introdotto e' trascurabile, ma esistono situazioni in cui anche questo rallentamento non e' accettabile.
Diventa allora interessante esplorare qualche strategia alternativa; in quanto segue vedremo una tecnica che permette agli oggetti C++ di cambiare classe mantenendo la loro identita'. Discutero' prima i criteri che guidano l'implementazione e poi i limiti di validita' (in termini di standard ANSI/ISO e di compilatori "reali") della soluzione proposta.

Distruggere e ricreare
Cosa significa "cambiare classe mantenendo l'identita'"? In termini implementativi, significa prendere un oggetto, chiamare il suo distruttore senza rilasciare il blocco di memoria in cui l'oggetto risiede, e crearne uno nuovo nello stesso blocco di memoria. In tal modo, ogni puntatore all'oggetto precedente rimarra' valido, ma puntera' al nuovo oggetto. In realta' dobbiamo porre sin dall'inizio alcune restrizioni: per ora, immaginiamo semplicemente che la classe concreta originale dell'oggetto e la nuova classe concreta siano entrambe derivate dalla stessa classe base (che chiamero' MetaMorph), e che i puntatori esistenti che puntano all'oggetto in questione siano di tipo MetaMorph*.
In teoria potremmo pensare ad una funzione Become implementata come segue:
template< class T > T* Become( MetaMorph* p )
  {
  p->~MetaMorph() ;
  return( new( p ) T ) ;
  }

Il codice, seppur breve, non e' proprio immediato, quindi vediamo cosa dovrebbe fare. La prima riga chiama il distruttore dell'oggetto: assumiamo quindi che MetaMorph abbia un distruttore virtuale. Notiamo che si tratta di una chiamata esplicita al distruttore, non implicita attraverso una delete expression: questo e' fondamentale in quanto si vuole distruggere l'oggetto ma non rilasciare il blocco di memoria che lo ospita.
La seconda riga chiama il costruttore della nuova classe (il parametro T del template), usando la sintassi di placement. Il placement new non richiede l'allocazione di un blocco di memoria: l'oggetto viene costruito "in place", usando come area di memoria il primo parametro.
Purtroppo questo codice non funziona, per almeno due buone ragioni. La prima di queste e' che p e' il puntatore al sotto-oggetto MetaMorph, e non necessariamente il puntatore all'inizio dell'area di memoria che ospita l'oggetto. In molte implementazioni, p punterebbe all'inizio dell'area dati, ed i byte precedenti l'area puntata conterebbero il puntatore alla vtable. Se chiamiamo l'operatore new passando p come parametro, l'oggetto costruito risultera' sfasato rispetto a quello precedente: dove dovrebbe iniziare l'area dati troveremmo la vtable, con effetti imprecisati.
La seconda ragione va ricercata nelle dimensioni degli oggetti. Nessuno ci garantisce che la dimensione del blocco di memoria puntato da p (che normalmente e' deciso dal compilatore, in base alla classe concreta originale dell'oggetto) sia sufficiente per ospitare oggetti di classe T (la nuova classe concreta).
Esiste poi un ulteriore problema, dovuto alle carenze di molti compilatori. Un operatore new di libreria con sintassi di placement e' previsto dallo standard ISO, ma non tutti lo implementano. In ogni caso, se il compilatore e' allineato allo standard, il delete con sintassi di placement che fornisce non andrebbe bene per il nostro caso, e dovrebbe comunque essere ridefinito (per i dettagli sul placement delete potete consultare [2]).
Fortunatamente, tutti questi problemi sono superabili.

Oggetti completi ed allocatori
Il primo passo per "aggiustare" la nostra funzione Become sta nel risalire all'indirizzo del blocco di memoria "completo" che ospita l'oggetto puntato da p. Esistono diverse tecniche, ma la piu' semplice e portabile e' quella discussa nello spazio ANSI/ISO di questo mese, ovvero l'uso di dynamic_cast:
template< class T > T* Become( MetaMorph* p )
  {
  // Get pointer to complete object
  void* completeObject = dynamic_cast< void* >( p ) ;
  p->~MetaMorph() ;
  return( new( completeObject ) T ) ;
  }
Dobbiamo ora risolvere il problema della dimensione del blocco. In questo caso ho optato per una soluzione decisamente pragmatica ma efficace in molti casi reali: ridefinire l'operator new della classe MetaMorph, e garantire che ogni oggetto derivato da MetaMorph ottenga un blocco di uguale dimensione. Dimensione che puo' essere specificata come parte di MetaMorph stessa, e che dipende ovviamente da quali classi intendiamo derivare. Si tratta quindi di un accoppiamento tra classe base e classi derivate, ovviamente disdicevole, ma relativamente accettabile in tempi in cui lo spreco di memoria non sembra piu' preoccupare nessuno.
Vediamo quindi un'implementazione completa della classe MetaMorph:
class MetaMorph
  {
  public :
    typedef bool IsA_MetaMorph ;
    virtual ~MetaMorph() {} ;
    void* operator new( /*std::*/size_t s ) ;
    void operator delete( void* p ) ;
    void* operator new( /*std::*/size_t s, void* p ) ;
    // only on conforming compilers
    // void operator delete( void* ptr, void* ) ;
  private :
    // Private and not implemented
    void* operator new[]( /*std::*/size_t s ) ;
    void operator delete[]( void* p ) ;
    // Size and number of objects may be changed freely
    typedef FixedSizeAlloc< 512, 100 > Allocator ;
    static Allocator allocator ;
  } ;


MetaMorph::Allocator MetaMorph :: allocator ;


void* MetaMorph :: operator new( size_t s )
  {
  void* p = allocator.Alloc( s ) ;
  return( p ) ;
  }


void* MetaMorph :: operator new( /*std::*/size_t s, void* p )
  {
  return( p ) ;
  }


void MetaMorph :: operator delete( void* p )
  {
  allocator.Release( p ) ;
  }


// only on conforming compilers
// void MetaMorph :: operator delete( void* ptr, void* /*p*/ ) ;
//   {
//   allocator.Release( ptr ) ;
//   }


template< class T > T* Become( MetaMorph* p )
  {
  // Compile-time checking, T must be derived from MetaMorph
  typedef T::IsA_MetaMorph dummy ;
  // Get pointer to complete object
  void* completeObject = dynamic_cast< void* >( p ) ;
  p->~MetaMorph() ;
  return( new( completeObject ) T ) ;
  }

Come vedete ho ridefinito gli operatori new e delete, che ora fanno riferimento ad un allocatore a blocchi fissi (che vedremo tra poco). Ho definito anche un operatore new con sintassi di placement, che non deve far altro che restituire il suo parametro: la memoria e' gia' stata allocata. L'operatore delete di placement deve comportarsi come quello "normale": liberare il blocco tramite l'allocatore.
Ho aggiunto un controllo compile-time (con il typedef IsA_MetaMorph) per impedire che Become venga usata per convertire ad una classe non derivata da MetaMorph. Ho anche ridefinito (privati e non implementati) gli operatori new e delete per array, in quanto non possiamo utilizzare gli array in modo polimorfo. Notate che i vari operatori new hanno come tipo del parametro /*std::*/size_t: in compilatori conformi, size_t e' nel namespace std, e quindi il commento deve diventare codice; di nuovo, non tutti i compilatori sono gia' stati adeguatamente aggiornati.
Per la stessa ragione, la funzione Become non e' un member template di MetaMorph ma un template esterno. Se il vostro compilatore supporta in modo adeguato i member template, vi consiglio di spostare Become all'interno della classe cui logicamente appartiene.
A questo punto ci manca solo un allocatore a blocchi, che e' l'argomento del prossimo paragrafo.

Fixed size allocator
Creare un allocatore a blocchi e' relativamente semplice. Basta preallocare un certo numero di blocchi, concatenarli in una lista di blocchi liberi, e poi gestire il rilascio e la reintegrazione nella lista di ogni blocco allocato. Esistono diverse varianti implementative, tra cui ho scelto quella con la massima velocita' (acquisizione e rilascio di blocchi in O(1), adatta anche ad applicazioni critiche) a spese di un vincolo piuttosto forte (un numero massimo fissato a compile-time di oggetti allocabili). Esistono varianti piu' complesse che rimuovono questo vincolo mantenendo il tempo costante di acquisizione e rilascio (sempre per blocchi fissi), ma sono piu' complesse ed andrebbero decisamente oltre gli scopi di questa rubrica. Esistono anche altre possibilita', come l'uso di una vera e propria linked list anziche' di una "embedded" in un array. In ogni caso, si tratta di varianti cui potete pensare indipendentemente dal problema che stiamo affrontando.
L'unica reale difficolta' riguarda l'allineamento in memoria di ogni singolo blocco. Poiche' non sappiamo a priori quale deve essere l'allineamento richiesto (che dipendera' dalla classe concreta che andremo a costruire dentro il blocco), dobbiamo forzare il compilatore ad allineare ogni blocco secondo l'ipotesi peggiore.
Purtroppo non esiste una tecnica totalmente portabile per determinare e forzare questa "ipotesi peggiore"; per essere piu' precisi, esiste una soluzione all'interno dello standard, che tuttavia potrebbe non coprire i tipi custom introdotti dai vari compilatori, come __int64 o long long. Fortunatamente, e' semplice adattare la tecnica utilizzata in presenza di tipi custom.
L'idea di fondo e' di definire una union con campi di ogni tipo con requisiti di allineamento:

    union X
      {
      S s ;
      long next ;
      // dummy fields to force alignment
      double dummy1 ;
      void* dummy2 ;
      X* dummy3 ;
      typedef void (X::*f)() ;
      f dummy4 ;      // may add more fields to
      // force alignment...
      // e.g. __int64 or long long
      } ;
Nel codice di cui sopra, S e' una struttura avente la dimensione del blocco desiderato per l'allocatore. Il campo next della union e' utilizzato per realizzare la lista dei blocchi liberi, ed allo stesso tempo per forzare almeno l'allineamento sul long (cosi' come S forza almeno l'allineamento sulle struct). Seguono un campo double, void*, puntatore a classe, puntatore a funzione membro. Potete aggiungere altri campi dummy per i tipi custom del vostro compilatore.
Il risultato finale e' il seguente: un template che prende due parametri, rispettivamente la dimensione del blocco ed il numero massimo di oggetti allocabili.

#include <assert.h>
#include <iostream>
#include <new>

template< /*std::*/size_t MAX_SIZE, long MAX_OBJ > class FixedSizeAlloc
  {
  public :
    FixedSizeAlloc()
      {
      firstFree = 0 ;
      freeBlocks = MAX_OBJ ;
      for( long i = 0; i < MAX_OBJ; i++ )
        {
        buf[ i ].next = i + 1 ;
        }
      } ;
    void* Alloc( size_t s = 0 ) // default dummy if no check desired
      {
      assert( s <= MAX_SIZE ) ;
      if( freeBlocks )
        {
        --freeBlocks ;
        int allocIndex = firstFree ;
        assert( ValidIndex( allocIndex ) ) ;
        firstFree = buf[ firstFree ].next ;
        return( buf + allocIndex ) ;
        }
      else
        {
        throw( std::bad_alloc( "no free blocks in FixedSizeAlloc" ) ) ;
        return( NULL ) ; // for dumb compilers
        }
      }
    void Release( void* p ) 
      {
      assert( BlockAligned( p ) ) ;
      long index = PtrToIndex( p ) ;
      assert( ValidIndex( index ) ) ;
      buf[ index ].next = firstFree ;
      firstFree = index ;
      ++freeBlocks ;
      }
  private :
    bool BlockAligned( void* p )
      {
      return( ( reinterpret_cast< char* >( p ) - reinterpret_cast< char* >( buf ) ) % sizeof( X ) == 0 ) ;
      }
    bool ValidIndex( long i )
      {
      return( i >= 0 && i < MAX_OBJ ) ;
      }
    int PtrToIndex( void* p )
      {
      return( ( reinterpret_cast< char* >( p ) - reinterpret_cast< char* >( buf ) ) / sizeof( X ) ) ;
      }
    struct S
      {
      char ch[ MAX_SIZE ] ;
      } ;
    union X
      {
      S s ;
      long next ;
      // dummy fields to force alignment
      double dummy1 ;
      void* dummy2 ;
      X* dummy3 ;
      typedef void (X::*f)() ;
      f dummy4 ;
      // may add more fields to
      // force alignment...
      // e.g. __int64 or long long
      } ;
    X buf[ MAX_OBJ ] ;
    long freeBlocks ;
    long firstFree ;
  } ;

Come vedete ho inserito un po' di assert per trovare piu' rapidamente alcuni errori (ad esempio il tentativo di rilasciare un blocco che non e' stato acquisito dall'allocatore), ed in accordo a quanto stabilito dallo standard anche il mio allocatore solleva l'eccezione bad_alloc quando esaurisce la memoria. Un punto un po' subdolo, che poteva facilmente sfuggire, e' l'uso di sizeof( X ) in ogni punto del codice in cui si fa riferimento alla dimensione effettiva del blocco. Usare MAX_SIZE in questi casi vanificherebbe tutto lo sforzo di allineare i blocchi.
Notiamo che la dimensione del blocco viene verificata, ovvero la richiesta di un blocco di dimensione superiore a quella prevista fa scattare una asserzione: questo ci permette di scoprire rapidamente i casi in cui le classi derivate da MetaMorph sono "troppo grandi" rispetto al blocco deciso da MetaMorph stessa. Si tratta di un controllo a run-time, che con un minimo di fatica potremmo spostare a compile-time: nella migliore tradizione, questa estensione viene lasciata "come esercizio".
Inoltre, l'allineamento viene in qualche modo "garantito" dalla union X di cui sopra ma non verificato. In realta' esiste una tecnica per verificare a compile-time che l'allineamento delle classi derivate da MetaMorph non sia superiore a quello garantito dalla union X, ma richiede un po' di spazio e verra' probabilmente discussa come argomento a se' in una futura puntata.

Un esempio di utilizzo
Vediamo un semplice caso di utilizzo: una classe base Rect da cui deriviamo una classe Square. Cambiando altezza o larghezza di un rettangolo possiamo ottenere un quadrato, e viceversa. Questo e' realizzato facendo effettivamente cambiare classe agli oggetti, pur mantenendo la loro identita'. Ho poi definito una funzione virtuale per il calcolo del perimetro, che a titolo di esempio e' ridefinita in Square dove e' leggermente piu' efficiente. Poiche' si tratta solo di un esempio dimostrativo, ho semplificato l'implementazione ipotizzando un vertice fissato nell'origine. Una implementazione piu' estesa ma decisamente migliore avrebbe previsto una classe base "quadrilatero" derivata da MetaMorph, da cui derivare sia Rect che Square (evitando cosi' di avere anche i dati di Rect in ogni Square). L'obiettivo qui e' solo di portare un semplice esempio di utilizzo.

class Rect : public MetaMorph
  {
  public :
    Rect() ; 
    Rect( int w_, int h_ ) ;
    virtual void SetW( int w_ ) ;
    virtual void SetH( int h_ ) ;
    virtual int Perimeter() ;
  private :
    int w ;
    int h ; 
  } ;

class Square : public Rect
  {
  public :
    Square() ;
    Square( int s_ ) ;
    virtual void SetW( int w ) ;
    virtual void SetH( int h_ ) ;
    virtual void SetSide( int s_ ) ;
    virtual int Perimeter() ;
  private :
    int s ;
  } ;


Rect :: Rect() 
  { 
  w = 0 ;
  h = 0 ;
  }

Rect :: Rect( int w_, int h_ )
  {
  w = w_ ;
  h = h_ ;
  }

void Rect :: SetW( int w_ )
  {
  if( w_ != h )
    w = w_ ;
  else
    {
    Square* q = Become< Square >( this ) ;
    q->SetSide( w_ ) ;
    }
  }

void Rect :: SetH( int h_ )
  {
  if( h_ != w )
    h = h_ ;
  else
    {
    Square* q = Become< Square >( this ) ;
    q->SetSide( h_ ) ;
    }
  }

int Rect :: Perimeter()
  { 
  std::cout << "Rect :: Perimeter()" << std::endl ;
  return( 2 * ( w + h ) ) ;
  }


Square :: Square()
  {
  s = 0 ;
  }

Square :: Square( int s_ )
  {
  s = s_ ;
  }

void Square :: SetW( int w )
  {
  if( w != s )
    {
    int h = s ;
    Rect* r = Become< Rect >( this ) ;
    r->SetW( w ) ;
    r->SetH( h ) ;
    }
  }

void Square :: SetH( int h )
  {
  if( h != s )
    {
    int w = s ;
    Rect* r = Become< Rect >( this ) ;
    r->SetW( w ) ;
    r->SetH( h ) ;
    }
  }

void Square :: SetSide( int s_ )
  {
  s = s_ ;
  }

int Square :: Perimeter()
  { 
  std::cout << "Square :: Perimeter()" << std::endl ;
  return( 4 * s ) ;
  }

int main()
  {
  Rect* r = new Rect( 30, 40 ) ;
  std::cout << r->Perimeter() << std::endl ;
  r->SetW( 40 ) ;
  std::cout << r->Perimeter() << std::endl ;
  r->SetH( 10 ) ;
  std::cout << r->Perimeter() << std::endl ;
  // Wait for a key
  std::cin.get() ;
  return( 0 ) ;
  }
Provando ad eseguire il programmino vedrete che l'oggetto puntato da R e' inizialmente un Rect, poi diventa uno Square, poi torna ad essere un Rect. Come potete notare, cambiare la classe di un oggetto e' diventata un'operazione del tutto banale, per cui basta una chiamata di funzione.

Limiti di validita' della tecnica
La tecnica di cui sopra non e' universalmente utilizzabile. In realta' possiamo identificare tre situazioni: una piuttosto ristretta in cui il suo funzionamento e' garantito dallo standard. Una piuttosto ampia in cui non e' garantito, ma funziona lo stesso con quasi tutti i compilatori (il "quasi" implica che potrebbe esisterne qualcuno che non conosco su cui non funziona). Ed una terza in cui proprio non funziona. Iniziamo dai requisiti piu' elementari. Ogni classe usata come parametro del template Become deve avere un costruttore di default. Possiamo rilassare questo requisito con un overloading di Become, in modo da supportare costruttori con uno, due, tre parametri ecc, ma dovremo comunque porre un limite in quanto non abbiamo template variadici. Inoltre, gli oggetti che passiamo come parametro a Become devono essere stati allocati con new, o scattera' una asserzione. Vediamo ora quando il codice di cui sopra "funziona sicuramente". Purtroppo dobbiamo essere piuttosto restrittivi. Dobbiamo infatti essere certi che tutti i puntatori ad un oggetto esistenti al momento del cambio di classe siano uguali, e che puntino al sotto-oggetto di classe MetaMorph. In pratica, possiamo derivare molte classi da MetaMorph, ma solo con ereditarieta' singola, e possiamo mantenere puntatori alle istanze delle classi derivate solo attraverso l'interfaccia MetaMorph. Questo significa, ad esempio, che il codice di esempio visto sopra potrebbe non funzionare, perche' manteniamo un puntatore a Rect, non a MetaMorph. Se volete rimanere totalmente portabili, dovete quindi creare una classe MetaMorph per ogni classe base dei vostri oggetti metamorfici, in pratica fondendo il codice di MetaMorph e quello della vostra attuale classe base. Avremmo quindi una MetaMorphShape per le shape metamorfiche, una MetaMorphPerson per le persone metamorfiche, eccetera. Potremmo cavarcela trasformando MetaMorph in un template, derivato dalla classe che prende come parametro. Tuttavia, la situazione e' piu' rosea se ci interessa solo "quello che succede in pratica". In tal caso dobbiamo solo evitare l'uso dell'ereditarieta' multipla in unione a MetaMorph: quindi ogni oggetto derivato da MetaMorph dovra' far parte di una gerarchia di ereditarieta' singola. La restrizione sul tipo dei puntatori che possiamo mantenere non sussiste, nella pratica, perche' usando l'ereditarieta' singola ogni oggetto ha un solo indirizzo. Puntatori di tipo diverso allo stesso oggetto (ad es. uno per ogni livello di derivazione) avranno lo stesso valore. Questo non e' vero nel caso di ereditarieta' multipla, che potrebbe facilmente portare ad effetti imprecisati se usata con oggetti metamorfici.

Conclusioni
Esistono situazioni in cui vale la pena di usare oggetti metamorfici? In effetti si. Pensate ad una applicazione in cui esiste un grafo di oggetti piuttosto complesso, dove ogni elemento e' puntato da parecchi altri. Supponiamo che il modello naturale porti ad una situazione di "cambio di classe" (il caso delle Shape e' piuttosto emblematico), e che avere gli oggetti "della classe giusta" comporti ottimizzazioni notevoli nelle operazioni. E supponiamo anche che l'applicazione sia abbastanza CPU-intensive da mal tollerare il livello di indirezione ulteriore delle classi ruolo o proxy, o il riaggiustamento di tutti i puntatori causato da un new-delete. Ci troveremmo in una situazione ideale per gli oggetti metamorfici, il cui prezzo (spreco di memoria per gli oggetti piccoli) sarebbe probabilmente piu' che compensato dai benefici. Come sempre, il C++ si rivela un linguaggio estremamente potente, dove la parola "impossibile" si applica di rado, e dove un buon programmatore puo' trovare il miglior trade/off nella soluzione ad ogni problema.

Bibliografia
[1] Carlo Pescio, "Ereditarieta' nei progetti reali", Computer Programming No. 71.
[2] Carlo Pescio, "Delete: cosa cambia", rubrica ANSI/ISO C++ in C++ Informer No. 3.

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.