Please help me see whether this is exception-safe

[alan]

I have a set of classes, cell, cell_body, and cell_internal.

cell_internal is an abstract base class, intended to encapsulate
deferred computation.

cell is just a wrapped pointer around cell_body; this is the user's
interface to this code.
When a cell is created, it creates a cell_body and attaches a
shared_ptr member (value_) to the body. This shared_ptr should never
be changed; the cell can only have one cell_body during its lifetime.

The cell_body holds a pointer to a cell_internal; when the cell's
value is taken by the member get_value(), it calls cell_body's
get_value(), which calls cell_internal's virtual cell_value(). This
virtual cell_value then computes the correct value. Basically the
get_value() function performs the computation that has been deferred.

Copying a cell to a cell does not, in fact, copy the cell; instead,
the destination cell is "attached" to the source cell, so that
changing the value of one changes the value of the other. So:
cell<int> i, j;
i = j;
j = 1; //now i is also 1
Actually what is being attached are the cell_body's. A new
cell_internal derived class (cell_shadow) is created, whose virtual
get_value() simply calls the get_value() of the cell_body it is
constructed with.

I don't use cell_body directly because of the possibility of
temporaries. When a cell is destroyed, its cell_body may still
survive, for example when referred from a global variable.

I think I may need to do swap-copy, but I don't quite understand yet
where I need to put it.

/*
* */

#include <boost/shared_ptr.hpp>
#include <boost/scoped_ptr.hpp>

/* cell_internal
* Interface to handle the deferred computation
* */
template<class T>
class cell_internal{
public:
virtual T get_value(void) const=0;
virtual ~cell_internal(){};
};

template<class T>
struct cell_internal_ptr{
typedef boost::shared_ptr< const cell_internal<T> > type;
};

/* cell_constant
* Handles constant numeric values
* */
template<class T>
class cell_constant: public cell_internal<T>{
T c_;
public:
cell_constant<T>(const T& v): c_(v) {};
T get_value(void) const {return c_;};
};

/* cell_body
* The actual cell structure
* */
template<class T>
class cell_body{
typename cell_internal_ptr<T>::type value_;
public:
cell_body(const cell_internal<T>* v): value_(v) {};
cell_body(const typename cell_internal_ptr<T>::type v): value_(v) {}
T get_value(void) const {
return value_->get_value();
};
void set(const cell_internal<T>* v){
value_.reset(v);
}
};

template<class T>
struct cell_body_ptr{
typedef boost::shared_ptr< const cell_body<T> > type;
};

/* cell_shadow
* Shadows a given cell_body
* */
template<class T>
class cell_shadow: public cell_internal<T>{
boost::shared_ptr< const cell_body<T> > var_;
public:
cell_shadow<T>(const cell_body<T>* v) : var_(v){};
cell_shadow<T>(const boost::shared_ptr< cell_body<T> >& v):
var_(v){};
T get_value(void) const {return var_->get_value();};
};

/* cell_op
* Handles a binary operation
* */
template<class T, class BinaryOperation>
class cell_op: public cell_internal<T>{
boost::shared_ptr< const cell_body<T> > lhs_;
boost::shared_ptr< const cell_body<T> > rhs_;
public:
cell_op<T, BinaryOperation>( const boost::shared_ptr< const
cell_body<T> >& lhs,
const boost::shared_ptr< const cell_body<T> >& rhs
) :
lhs_(lhs),
rhs_(rhs) { };
cell_op<T, BinaryOperation>( cell_body<T>* lhs, cell_body<T>* rhs):
lhs_(lhs),
rhs_(rhs) { };
T get_value(void) const {
return BinaryOperation()(lhs_->get_value(), rhs_->get_value());
};
};

/* cell_singelop
* Handles a unary operation
* */
//template<class T, class UnaryOperation>
//class cell_singleop: public cell_internal<T>{
//};

/* cell
* Acts as the user's interface to the cell_body
* Effectively just a wrapper around a pointer to the cell_body
* IMPORTANT. Each cell will have one, and only one, cell_body
* during its lifetime. A cell_body, however, may outlive its
* cell (for example if the cell is a local variable that is
* then used in the formula for a global variable - at the end
* of the function the local cell is destroyed, but the cell_body
* is retained via a cell_shadow by the formula for the global).
* */
template<class T>
class cell{
void set(const cell_internal<T>* v){
value_->set(v);
}
boost::shared_ptr< cell_body<T> > value_;
public:
cell<T>(const cell<T>& v){
value_.reset(new cell_body<T>(new cell_shadow<T>(v.value_)));
}
cell<T>(const T& v=T()){
value_.reset(new cell_body<T>(new cell_constant<T>(v)));
}
cell<T>(const typename cell_internal_ptr<T>::type& v){
value_.reset(new cell_body<T>(v));
}
cell<T>(const cell_internal<T>* v){
value_.reset(new cell_body<T>(v));
}

cell<T>& operator=(const cell<T>& v){
if(&v != this){
set(new cell_shadow<T>(v.value_));
}
}
cell<T>& operator=(const T& v){
set(new cell_constant<T>(v));
}
cell<T>& operator=(const typename cell_internal_ptr<T>::type& v){
set(&(*v));
}

cell<T> operator+(const cell<T>& rhs) const {
return cell<T>(
new cell_op<T, std:lus<T> >(
value_,
rhs.value_
)
);
};

T get_value(void) const {return value_->get_value();}
};

template<class T>
inline cell<T> operator+(const cell<T>& lhs, const T& rhs){
return lhs + cell<T>(rhs);
}

template<class T>
inline cell<T> operator+(const T& lhs, const cell<T>& rhs){
return cell<T>(lhs) + rhs;
}

 

[Kira Yamato]

I have a set of classes, cell, cell_body, and cell_internal.

cell_internal is an abstract base class, intended to encapsulate
deferred computation.

cell is just a wrapped pointer around cell_body; this is the user's
interface to this code.
When a cell is created, it creates a cell_body and attaches a
shared_ptr member (value_) to the body. This shared_ptr should never
be changed; the cell can only have one cell_body during its lifetime.

The cell_body holds a pointer to a cell_internal; when the cell's
value is taken by the member get_value(), it calls cell_body's
get_value(), which calls cell_internal's virtual cell_value(). This
virtual cell_value then computes the correct value. Basically the
get_value() function performs the computation that has been deferred.

Copying a cell to a cell does not, in fact, copy the cell; instead,
the destination cell is "attached" to the source cell, so that
changing the value of one changes the value of the other. So:
cell<int> i, j;
i = j;
j = 1; //now i is also 1

If assignment to j can change i too, then this is telling me that
cell<int> is acting like a pointer. So, please define it like a
pointer class.

One important principle I recently picked up is the principle of least
surprise. If it is intended to quake like a duck, then please call it
a duck. So, if cell<int> acts like a pointer, then code it with syntax
like that of a pointer, so that readers of your code won't have to rely
on optional comments like "now i is also 1" to know that it behaves
like a pointer.

Try this:

cell_ptr<int> i, j;
i = j;
*j = 1;

and declare the operator *() for the class cell_ptr.

This is much clearer.

 

[alan]

If assignment to j can change i too, then this is telling me that
cell<int> is acting like a pointer. So, please define it like a
pointer class.

One important principle I recently picked up is the principle of least
surprise. If it is intended to quake like a duck, then please call it
a duck. So, if cell<int> acts like a pointer, then code it with syntax
like that of a pointer, so that readers of your code won't have to rely
on optional comments like "now i is also 1" to know that it behaves
like a pointer.

Try this:

cell_ptr<int> i, j;
i = j;
*j = 1;

and declare the operator *() for the class cell_ptr.

This is much clearer.

Actually, no, it does not act very much like a pointer.
For example:
cell<int> i, j;
i = j + 1;
j = 1; //i.get_value() becomes 2
j = 3; //i.get_value() becomes 4

In order to get the current value, you get it with method get_value().

Basically I'm overloading the operator= with its meaning in math - "i
is *defined* as j plus 1", not "until I say otherwise, give i the
value of j", which would be a pointer.

Of course, cell_ptr could be defined as just a wrapper around cell,
with operator* returning the cell, but then it would just be a typedef
cell<T>*

 

[Kira Yamato]

Actually, no, it does not act very much like a pointer.
For example:
cell<int> i, j;
i = j + 1;
j = 1; //i.get_value() becomes 2
j = 3; //i.get_value() becomes 4

In order to get the current value, you get it with method get_value().

Basically I'm overloading the operator= with its meaning in math - "i
is *defined* as j plus 1", not "until I say otherwise, give i the
value of j", which would be a pointer.

I see. So, your assignment operator is essentially just building an
mathematical expression tree to be evaluated only when it is called to.
So, I will retract my last comment.

Onto another possible issue, I'm also curious what your code will do if
you write
i = j;
j = i;
val = j.get_value();
or maybe even with just
i = i;
val = i.get_value();
Essentially, the question is what if instead of an expression tree, you
have an expression graph with cycles?

 

[alan]

I see. So, your assignment operator is essentially just building an
mathematical expression tree to be evaluated only when it is called to.
So, I will retract my last comment.

Onto another possible issue, I'm also curious what your code will do if
you write
i = j;
j = i;
val = j.get_value();
or maybe even with just
i = i;
val = i.get_value();
Essentially, the question is what if instead of an expression tree, you
have an expression graph with cycles?

It would crash. Same for i = i + 1, for that matter (I have since
made a modification where += would only modify the expression tree but
that would be a special case).

In any case, how *would* you evaluate a node on an expression graph
with cycles? I can't think of a way, so my code doesn't even begin to
try to catch that error (since that would require a search through the
graph to detect cycles). It may be possible to do such a search, but
maybe as a later add-on.

Arguably an expression graph where some expressions are equivalent to
ternary operators (cond ? then : else) would be validly computable,
but then I think if I do create such a node, it wouldn't crash.

 

[Kira Yamato]

It would crash. Same for i = i + 1, for that matter (I have since
made a modification where += would only modify the expression tree but
that would be a special case).

In any case, how *would* you evaluate a node on an expression graph
with cycles?

There is no way. You got a logically self-reference here.

I can't think of a way, so my code doesn't even begin to
try to catch that error (since that would require a search through the
graph to detect cycles). It may be possible to do such a search, but
maybe as a later add-on.

There is a cheap but inelegant way to detect cycles in a directed graph
such as the tree. Add a boolean variable acting as a flag to each node
of the tree. In default, this flag is off for all nodes. During a
computation, as you tranverse down a node, flag the parent node; and as
you tranverse back up, de-flag the child node. So, if you ever
encounter a flagged node as you tranverse down a tree, you know you are
revisiting that node and hence you got a cycle. But be careful that
you do not immediately throw an exception when you detect a cycle in
the middle of a computation. Instead, you must tranverse all the way
back up to the root node in order to de-flag all the nodes back.

This solution is not elegant because you have to carry around an
utility variable in your node class. Also, it could be error-prone if
you do not maintain the flags in off-state before you begin computation.

There is another elegant but expensive way too. Before the
computation, setup an empty dictionary which will store the address of
visited nodes. Before you tranverse down a node, first lookup in the
dictionary for the child node's address. If it does not exist in the
dictionary, then push that child node's address into the dictionary and
tranverse down. Otherwise, if it exists in the dictionary, then you
are revisiting that child node. In this case, you can just immediately
throw an exception. Then as you tranverse up, remove the child node's
address from the dictionary.

The 2nd solution is expensive because of the many dictionary pushing
and lookup.

Perhaps someone can offer a middle ground solution.