Using a C++ polymorphic hierarchy with Bison

[Hans Aberg]

Here are some of my conclusions, which might be useful in connection with
Bison, on using a C++ polymorphic class hierarchy:

1. It is important to use the reference classes ref<A>, not only for use
with any potential Bison static typing, but this helps to reduce the amount
of dynamic_cast's in the program itself. Also, my compiler can zip out the
dynamic_cast when the static type is available, i.e., when D is derived
from B, and one has a conversion from D to B, so that it does not take up
any runtime. The same then applies to conversions from ref<D> to ref<B>.
One then only saves computing time using a static_cast when there is a B to
D conversion of a pointer/reference one surely knows is already a D.

2. If one wants to use static_cast, then one can not let the base classes
be virtual. Non-virtual base classes also seems to avoid a small conversion
before each virtual function call. On the other hand, a reference counted
base class should normally be virtual, otherwise funny things will happen
in multiple inheritance.

So if computing time is critical, it seems best to avoid virtual base
classes, and on the smae time, by a hands-on check, making sure that no
multiple inheritance of classes both containing the reference base occurs.
But on the other hand, virtual base classes might not be possible to avoid
if one picks down a library where the reference class is virtual, in which
case dynamic_cast must be used.

I have made a ref<A> class which, as far as possible, hides away the
reference count when doing normal programming in the hierarchy. The
reference count is in a root class, which is called "object":

-- In header file:

class ref {
protected:
  A* data_;
  static A null_;

public:
  typedef A&         reference;
  typedef A*         pointer;
  typedef const A&   const_reference;
  typedef const A*   const_pointer;

  typedef ref<A> This;

  ref() : data_(0) {}
  ~ref() { shed(); }

  ref(const ref& x) : data_(x.copy()) {}
  ref& operator=(const ref& x) {
    if (data_ != x.data_) { shed(); data_ = x.copy(); }
    return *this;
  }

  // Conversion constructors.
  ref(A* ap) : data_(ap) {}
  ref(const A* ap) : data_(ap->copy()) {}
  ref(const A& a) : data_(a.copy()) {}

  template<class B>
  explicit ref(B* bp, bool dynamic = true)
   : data_(dynamic? dynamic_cast<A*>(bp) : static_cast<A*>(bp)) {}

  template<class B>
  explicit ref(const B& br, bool dynamic = true)
   : data_(dynamic? dynamic_cast<A*>(br.copy()) :
static_cast<A*>(br.copy())) {}

  ref<A> clone() const { return (data_ == 0)? 0 : data_->clone(); }
  A* copy() const { return (data_ == 0)? 0 : data_->copy(); }

  void shed() { if (data_ != 0)  data_->shed(); }

  bool is_null() const { return (data_ == 0); }

  // Operators that return pointer 0 when applicable:

  operator A*() { return data_; }
  operator const A*() const { return data_; }

  // Operators that return reference to an object A() when applicable:

  // Return a pointer to the referenced object, or if 0, the A::null_ object:
  A* operator->() { return (data_ == 0)? &null_ : data_; }
  const A* operator->() const { return (data_ == 0)? &null_ : data_; }

  // Return a reference to the referenced object, or if 0, the A::null_ object:
  A& operator*() { return (data_ == 0)? null_ : *data_; }
  const A& operator*() const { return (data_ == 0)? null_ : *data_; }

  // Create an independent copy of the referenced object.
  ref<A> detach() {
    if (data_ != 0 && data_->count() > 1) { data_->shed(); data_ =
data_->clone(); }
    return copy();
  }
  const ref<A> detach() const {
    if (data_ != 0 && data_->count() > 1) { data_->shed(); data_ =
data_->clone(); }
    return copy();
  }

  // If 0, mutate to new A(). Return a reference to an independent copy of the
  // referenced object.
  A& operator+() {
    if (data_ == 0)  data_ = new A();
    else if (data_->count() > 1) { data_->shed(); data_ = data_->clone(); }
    return *data_;
  }
  const A& operator+() const {
    if (data_ == 0)  data_ = new A();
    else if (data_->count() > 1) { data_->shed(); data_ = data_->clone(); }
    return *data_;
  }
};


template<class A, class B>
A* cast_pointer(ref<B>& ar) { return dynamic_cast<A*>((B*)ar); }

template<class A, class B>
const A* cast_pointer(const ref<B>& ar) { return dynamic_cast<const
A*>((const B*)ar); }

template<class A, class B>
A& cast_reference(ref<B>& ar) { return dynamic_cast<A&>(*(B*)ar); }

template<class A, class B>
const A& cast_reference(const ref<B>& ar) { return dynamic_cast<const
A&>(*(const B*)ar); }


#define ref_null(A) A ref<A>::null_

#define clone_header(A)  virtual A* clone() const { return new A(*this); }

#define copy_header(A) \
  virtual A* copy() const { increment_count(); return const_cast<A*>(this); }


template<class A>
inline std::istream& operator>>(std::istream& is, ref<A>& a) {
  return is >> (*a);
}

template<class A>
inline std::ostream& operator<<(std::ostream& os, const ref<A>& a) {
  return os << (*a);
}

template<class A>
inline relation compare(const ref<A>& x, const ref<A>& y) {
  return compare(*x, *y);
}

template<class A>
inline relation total(const ref<A>& x, const ref<A>& y) {
  return total(*x, *y);
}

template<class A>
inline bool operator==(const ref<A>& x, const ref<A>& y) {
  return (*x == *y);
}

template<class A>
inline bool operator!=(const ref<A>& x, const ref<A>& y) {
  return (*x != *y);
}

template<class A>
inline bool operator<(const ref<A>& x, const ref<A>& y) {
  return (*x < *y);
}

template<class A>
inline bool operator<=(const ref<A>& x, const ref<A>& y) {
  return (*x <= *y);
}

template<class A>
inline bool operator>(const ref<A>& x, const ref<A>& y) {
  return (*x > *y);
}

template<class A>
inline bool operator>=(const ref<A>& x, const ref<A>& y) {
  return (*x >= *y);
}


class object {
  typedef unsigned long count_type;
  mutable count_type count_;
public:
  object() : count_(1) {}
  virtual ~object() {}

  void increment_count() const { ++count_; }
  count_type count() const { return count_; }

  clone_header(object);
  copy_header(object);

  void shed() { if (--count_ == 0)  delete this; }

  virtual void write(std::ostream& os, write_style) const { os << "object"; }
};

inline std::ostream& operator<<(std::ostream& os, const object& a) {
  a.write(os, write_default);  return os;
}

-- In source file:

ref_null(object);

---------------------

The Bison sematic type would then be something like:

class semantic_type {
public:
  ...
  mli::ref<mli::object> object_;
  ...
};

#define YYSTYPE semantic_type


If one wants to add a new class D to the hierarchy, it should look like

-- In header file:

class D : public B { // B equal, or indirectly derived, from class object.
...
public:
  clone_header(D);
  copy_header(D);
  ...
};

-- In source file:

ref_null(D);

------------------

The return type of the D::clone() and D::copy() functions is D*. This kind
of virtual function overloading is important, as it preserves the static
type in the ref<D> classes, which then can be used to simplify or avoid the
dynamic_cast.

The reason for the presence of the ref_null(D) objects is that this version
of the class ref<A> here admits reference to 0 in some circumstances:
    ref<A> a(0);
    a->f(...);
in which case the ref<A>::operator->f() call will be translated into
A::null_.f(). For this reason, every class A for which ref<A> is to be used
must have an A::null_ object implemented which is done by the ref_null()
macro. If one has no need to reference null (0) this way, it is easy to
make a ref<A> class without it.

If one wants to convert objects between the ref<X> classes, one merely writes:
   ref<X> x;
   ref<Y> yd, ys;
   yd = ref<X>(x);         // dynamic_cast conversion
   ys = ref<X>(x, false);  // static_cast conversion; must know statically
                           // that x points to a Y object.

It is easy to program with the ref<A> class, without explicitly referencing
copy(). For example, if D is derived from B:

ref<B> D::f(const B& b) {
   D* d1p = new D(...);
   return d1p;  // automatically converts to a ref<B> object
   ...
   const B* bp = (B*)b; // Get the pointer that b points to.
   const B& br = *b;    // Get a reference to the object that b points to.
   ...
   D* d2p = cast_pointer<D>(b); // Same as:
   D* d2p = dynamic_cast<D*>((B*)b);
   D& d2r = cast_reference<D>(b); // Same as:
   D& d2r = dynamic_cast<D*>(*(B*)b);
   return *d2p;  // automatically converts to a ref<B> object.
   ...
   return *this;  // automatically converts to a ref<B> object.
};

In general, a referenced object B&, const or not, will be converted using a
copy(), incrementing the reference count. And a non-const pointer object B*
will not increase the reference count (but a const pointer will). Thus, one
can pretty much hide away that one is in fact working with a reference
count, and stick with more normal C++ syntax.

Instead of the ref<A>::data() function, one might try:
  A* ref<A>::operator&() { return data_; }
  const A* ref<A>::operator&() const { return data_; }
But it then turns out that it causes conflicts with other container
classes, such as std::list, if one nests them std::list<ref<A> >. So that
seems best to avoid.

One should also be aware of, that even though one can write a copy constructor
    ref<A>::ref(ref<A>&);
the C++ standard is such that it may not be called when one would expect
to, for example, in a function
    ... f(ref<A>& a) {
       // ref<A>::ref(ref<A>&), even if explicitly defined, is not applied
to a.
       ...
    }
This makes it hard to regulate the dynamic behavior of a reference count in
C++. Therefore, one ends up relying on the const copy constructor
    ref<A>::ref(const ref<A>&);
and functions typed
    ... g(..., const ref<A>&, ...);
which gurantees a caol to the const copy contructor. A similar problem
happens with the conversion operator
    ref<A>::operator B&().
Therefore, avoid that one too.

I found it useful to add some more sporadic functions: operator+() which
works as operator*(), except that if 0, a new objects is created, and
otherwise, an independent copy is created, so that mutations can take
place. The detach() function does the same, except that no new object is
created in the case of 0. I am, in fact, using both. By the use of these
operators, I can ensure that no operator new() is called in mutative
circumstances unless really needed.

The object::write(), and operator<<() functions are just examples how the
whole class hierarchy can be made printable, and as well all ref<A>
objects. If all classes derivable from a class B be should be made
readable, then I would add:

class R : public ... {
public:
  ...
  virtual void read(std::istream&);
  ...
};


inline std::istream& operator>>(std::istream& is, R& r) {
  r.read(is);  return is;
}

The only class made readable that I have, is the one which uses a Flex
lexer and a Bison parser to create objects in the hierarchy. The parser is
then initiated by making an instaination object of this readable class, and
then read it. My syntactic setup is as follows:
  R r(...);
  std::istream is; // Say a file or standard input.
  is >> r;
  if (!is) {
    std::cerr << "Could not read..." << std::endl;
    return EXIT_FAILURE;
  }


If one should be able to compare two objects of class ref<A>, then I add:

-- In header:

typedef int relation;

const relation unrelated = -2;
const relation less = -1;
const relation equal = 0;
const relation greater = 1;

...

class A : ... {
public:
  ...
  virtual relation compare(const formula&) const;
  virtual relation total(const formula&) const;
  ...
};


inline relation compare(const formula& x, const formula& y) {
  return x.compare(y);
}

inline relation total(const formula& x, const formula& y) {
  return x.total(y);
}

inline bool operator==(const formula& x, const formula& y) {
  return x.compare(y) == equal;
}

inline bool operator!=(const formula& x, const formula& y) {
  return x.compare(y) != equal;
}

inline bool operator<(const formula& x, const formula& y) {
  return x.compare(y) == less;
}

inline bool operator<=(const formula& x, const formula& y) {
  relation r = x.compare(y);
  return (r == less) || (r == equal);
}

inline bool operator>(const formula& x, const formula& y) {
  return x.compare(y) == greater;
}

inline bool operator>=(const formula& x, const formula& y) {
  relation r = x.compare(y);
  return (r == greater) || (r == equal);
}

-----------------

If one looks above, I added template functions to the ref<A> class, which
merely redefine the compare(), total(), and C++ comparison operators in
terms of the corresponding class A functions. I am then free do define them
as I want in the class hierarchy.

The rest, how I implement comparisons, is just my own personal choice: I
noticed that it is often important to have access to a total order, for
insertions in a container like std::map and lookup sorting, which explains
the total() function. The semantic comparisons instead use a function
compare(), which may return a value "unrelated"; so this does not impose a
total order. I use the function compare(), instead of defining it in
directly in terms of say operator<(), in order to avoid extra function
calls in the comparisons.

One can easily add more templates supporting the ref<A> class, for example:

template<class A>
inline bool operator+(const ref<A>& x, const ref<A>& y) {
  return ((*x) + (*y));
}

template<class A>
inline bool operator*(const ref<A>& x, const ref<A>& y) {
  return ((*x) * (*y));
}

And so on.

  Hans Aberg