Title: Circles and Ellipses revisited: coding techniques - 2

Author:

Date: 31 January 1997 08:55:00 +00:00 or Fri, 31 January 1997 08:55:00 +00:00

Summary: A second approach: In-store changes

Body:

As noted by Francis, it is possible to overlay objects in store with others of different types.[1] There are several options available to implement the overlays, such as the use of placement new, and memcpy(), some of which are illustrated here.

Classes used in illustration of in- store object change

The techniques illustrated below show how a given object constructed on the stack or in free store might be overwritten by one of a different type, and some of the effects involved. The examples use a base class B, with two publicly derived classes Dl and D2. They also use a morphing type U which is, roughly speaking, the union of Dl and D2. Variations to support morphing between Dl and D2 objects directly will be obvious. The effects are illustrated by use of a single function f(), implemented for all the above classes, and whose observed be-haviour depends on the state of the U object.

The object of type U can have its data area (members), and most importantly its pointer to its virtual function table (vtable) overlaid by a Dl or D2 at will, thus changing its observed data and functions. The overlay can be achieved by:

overloading assignment for the U class (supplying a version which assigns from a reference to a B, returning a reference to a U.)
providing a change() member function in U
providing a placement new: globally, in the base class B, or in the derived classes as well as:
creating a U in an initial Dl or D2 state by an appropriate constructor.

These options are illustrated in listings below. The semantics of the overlay are very simple in all these cases, such as bitwise copy using memcpy(); but copy constructors and/or addi-tional processing could also be used.

For example:

Use of overloaded assignment operator in "union" class

class B 
{ 
public:
  virtual void f()
  { cout << "B's f()\n"; }
};

class D1 : public B
{
public:
  void f() { cout << "Dl's f()\n"; }
};

class D2 : public B
{
public:
  void f() { cout << "D2's f()\n"; }
};

// define a union,
// just to get max of sizeof(Dl),
// sizeof(D2), ...
union Usz
{ unsigned char a[sizeof(D1)];
  unsigned char b[sizeof(D2)];
  // ... and any other derived types
};

class U 
{ 
public:
  virtual void f()
  { cout << "U's f()\n"; }
  U &operator=(B& b)
  { memcpy(this, &b, sizeof(U));
    return *this; } 
private:
    size_t a[ sizeof(Usz) ]; // filler
};

As above, making a more refined size calculation, and exercising the code

// B, D1, D2 etc as above
class U 
{
public:
  virtual void f()
  { cout << "U's f()\n"; )
  U &operator=(B& b)
  { memcpy( this, &b, sizeof(U) );
    return *this; } 
private:
  typedef union USZ // union is used to 
                    // get a filler size, to allow a U to 
                    // be overlaid by any D, ie max of 
                    // sizes of: Dl, D2, ... . 
  {
    char a[sizeof(Dl)]; 
    char b[sizeof(D2)]; 
    // ... and any other derived types 
  } Usz;
  class C { // for size adjustment only 
    virtual void vf() { return; }
  }; 
  char a[sizeof(Usz) - sizeof(C)]; // filler
};

int main()
{
  U u; 
  u.f();     // calls U's f()

  D1 d1; D2 d2; 
  u = d1; 
  u.f();     // calls U's f()
  U* up = &u; 
  up->f();   // call d1's f()
             // - iff U's f() virtual
  u = d2; 
  up->f();   // call D2's f()
             // - iff U's f() virtual
  ...
}

(Note: the method of calculation of the size of the filler in class U above is intended to mini-mise the size of the "union" objects - but it is less portable than the previous method shown.)

Change of U's effective type by a change() function:

// classes B ... U as above, with 
// additional U member, a change() 
// function: 
  U &change(int i) 
  {
    D1 d1; D2 d2; 
    if (i == 1)
      memcpy(this, &d1, sizeof(U)); 
    else if (i == 2)
      memcpy(this, &d2, sizeof(U));
    return *this;
  }

Create U as different types, by use of a global overload of operator new

// Global overload of operator new
void *operator new(size_t, void *p)
{
  return p;
}

// B, Dl, D2 as before
class U
{
public:
  U(double e = 0.0)
  {
    if ( e == 0 ) new (this) D1;
    else
    if ( e < 1 ) new (this) D2;
  }
  ...
};

As above, but with operator new overloaded in B, rather than globally

class B
{
public:
  void *operator new(size_t, void *p )
  {
    return p;
  }
  virtual void f()
  { cout << "B's f()\n"; }
};

The identical effect could be accom- plished by overloading operator new in each of the derived classes, Dl, D2, using identical code to the above overload in B.

Problem Opportunity pages

There are several problems with such ap- proaches which overlay instances of one type with another. These can be summarised:

typeid() can report a misleading (wrong) type
results can differ between Object.foo(), and (&Object)->foo()
in particular, due to the above, results can differ between creating an object on the stack, accessing it by its name, and an identical object in free store, accessed by a pointer
assumptions on the implementation of polymorphism limit portability
sizeof() could report a misleading (wrong) size
use of (non-morphing) raw pointers could cause problems
arrays of morphing types need special consideration

Some of these problems are discussed in more detail below.

The typeid() problem

In the discussion of the circle/ellipse problem, The Harpist pointed out a problem with this kind of (store overlay) approach, which in this "Man" example could be represented:

Schoolboy S;
S.setAge(40) ;
if ( typeid(S) == typeid(MiddleAge)
{
  cout << "Type changed" << endl;
}

That is, given a setAge() function which could act on S, would the compiler/optimiser system be expected to respect possible changes to the type of object which we are overlaying onto the storage area originally set up for S as a Schoolboy? The Harpist points out that the system might reasonably assume that it could identify the type needed for the typeid call on the basis that an S was created, with no poly-morphic behaviour being invoked by use of a reference or pointer. [2] (This is true even if the type is declared volatile, as in:

volatile Schoolboy S;

Different behaviour between Object.foo(). and (&Obiect)->foo()

Closely related to the above problem, and per-haps of more general concern, is that the com- piler will be inclined to make this kind of optimisation for any function invoked with the syntax Object.foo() ignoring the fact that the object has changed beneath its feet; and that execution via a pointer syntax will give a dif-ferent result. That is:

T Object, *p;
p = &Object;
Object.foo();  // gives different
               // result from
p->foo();      // pointer invocation

Nevertheless, where this could cause problems, they could be overcome by writing the code so that foo() always invoked the same function, irrespective of how it was invoked. (This could be done by rolling one's own virtual function mechanism, with foo() defined in a base class as forwarding its function call by dereferenc-ing a pointer to function, this pointer being set up appropriately by the derived class constructors.)

Aside (casting)

The examples could have implemented casting in the form of overloads for operator type(). Some related points can be noted:

It is possible to suppress such casts by declaring them protected or private, just as it is possible to similarly prevent copying by assignment or construction
However casting is treated, it will be incomplete, as one might like to be able to implement or restrict pointer casts as well as casts of class types; in particular it would be desirable to change the type of a raw pointer in synchronism with the effective type of the object that it pointed to. Also, it is not possible to overload the new-style casts.

Perhaps template<typename T> operator T(); would help here as a member conver-sion operator? - Ed.

Problems with arrays

Arrays of such morphing types need special consideration in respect of space efficiency. (If implemented as a simple array of "U"s), and element access using a pointer to an element of a sub-type (eg a "D1 *").

Assumptions about implementation of polymorphism

Where virtual functions are used, these tech- niques would typically assume an implementa-tion mechanism with a pointer to the virtual function table being at a fixed offset in all ob-jects. This is a reasonable working assumption, but code which made it would fail if, for in-stance, various sized classes were used and the compiler placed the pointer at the end of each object.

Several implementations do precisely that Ed.

Differences between stack and freestore behaviour

Many of the problems noted above arise when a morphable object is created on the stack (and accessed by its name), but not when it is created on free store (and accessed via a pointer).

Continue (y/n)?

One might be inclined to reject techniques which overlay store, particularly on the stack, where the corresponding object name can be assumed by the compiler to have a fixed type. But where the potential problems above are recognised and are accepted, they can be avoided by careful coding.

Conclusion

Several approaches to the problem of morphing objects are possible. By building different behaviours into a given type, the de-sired effects can largely be achieved. Many such approaches are possible, but they suffer from the limitations mentioned above.

The approach suggested here is that the appli- cation model should assume that there is a con-stant type for the mutable object involved -Man or Conic in the above examples - even if states in the life history are modelled by other classes. These other classes would typically be related to the superclass by derivation and/or use of the handle-body idiom. One option here is to use Coplien's Envelope-Letter idiom, as will be described in the next article in this se-ries. With this kind of approach, the system provided typeid() will always return the same type irrespective of the state of the handle ob-ject involved; user-provided additions can re-port on sub-state information if required. Merits of the technique include the fact that the model is simple, flexible, and can map state transitons directly in code.

References

[1] Francis Glassborow, "Circle & Ellipse - Creating Polymorphic Ob- jects", Overload, Issue 8, pp 26 - 28
[2] The Harpist, "Joy Unconfined - reflections on three issues", Overload, Issue 9, pp 11 - 13

Notes:

More fields may be available via dynamicdata ..