[boost] bug in boost::variant?

Subject: [boost] bug in boost::variant?
From: Zachary Turner (divisortheory_at_[hidden])
Date: 2009-12-10 23:11:25

I'm using boost 1.41.  I use a variant to store a symbolic representation of
an algebraic expression, wrapped inside of a master "node" class.  Like
this:

struct expr_node
{
    friend class constant;
    friend class variable;
    friend class arithmetic_op;
    friend class exponent;
    friend class special_func;
    friend class negative;
public:
    template<class T>
    expr_node(const T& expr)
        : expr_(expr)
    {
    }

    expr_node& operator=(const expr_node& rhs)
    {
        expr_ = rhs;
        return *this;
    }

private:
    typedef boost::variant<constant, variable, arithmetic_op, exponent,
special_func, negative> node_type;

    node_type expr_;
};

Of course, this is a recursive definition, because exponent, arithmetic_op,
etc also contain expr_node members.

At some point, I flatten the tree structure across either addition or
multiplication, the result of which is a std::list<expr_node>.  So in this
example, if my expression is

2 * x * 2 * x^x * (2+x)^2 * (1 + x)

this becomes the list [2, x, 2, x^x, (2+x)^2, 1+x].  I then use
std::partition() to organize this list into the desired order according to
the node type.  This is where the strange behavior comes in.  As you can see
there are no negatives in this expression, and indeed, I can verify this is
indeed the case in my code as well with:

bool expr_node::is_negative() const { return boost::get<negative>(&expr_); }
...
BOOST_ASSERT(std::find_if(terms.begin(), terms.end(),
boost::bind(&expr_node::is_negative, _1)) == terms.end());

This assert passes.  However, Immediately executing

std::partition(terms.begin(), terms.end(),
boost::bind(&expr_node::is_constant, _1));
BOOST_ASSERT(std::find_if(terms.begin(), terms.end(),
boost::bind(&expr_node::is_negative, _1)) == terms.end());

triggers the assert.  So something is going wrong involving copying the
variants.  Every class has both a copy constructor and an assignment
operator.

Examining the exact contents of the list both before and after the
partition, the which_ fields are [0,1,0,3,3,2] (before), and [0,5,5,3,3,2]
(after).

Putting a breakpoint in all of the negative constructors, I can get a
callstack for the first time a 'negative' is constructed.  The callstack is
as follows:

negative::negative(const expr_node & arg={...})  Line 747    C++
node_type::convert_construct<expr_node const >(const expr_node &
operand={...}, int __formal=1, int __formal=1)  Line 1298 + 0xf bytes    C++
node_type::node_type<expr_node>(const expr_node & operand={...})  Line
1367    C++
node_type::assign<expr_node>(const expr_node & rhs={...})  Line 1609 + 0xc
bytes    C++
node_type::operator=<expr_node>(const expr_node & rhs={...})  Line 1620
C++
expr_node::operator=(const expr_node & rhs={...})  Line 171    C++
std::swap<expr_node>(expr_node & _Left={...}, expr_node & _Right={...})
Line 23    C++
std::iter_swap<term_list::_Iterator<0>,term_list::_Iterator<0>
>(term_list::_Iterator<0> _Left={...}, term_list::_Iterator<0>
_Right={...})  Line 594 + 0x17 bytes    C++
std::_Partition<term_list::_Iterator<0>,boost::_bi::bind_t<bool,boost::_mfi::cmf0<bool,expr_node>,boost::_bi::list1<boost::arg<1>
> > >(term_list::_Iterator<0> _First={...}, term_list::_Iterator<0>
_Last={...},
boost::_bi::bind_t<bool,boost::_mfi::cmf0<bool,expr_node>,boost::_bi::list1<boost::arg<1>
> > _Pred={...})  Line 1838 + 0x4d bytes    C++
std::partition<term_list::_Iterator<1>,boost::_bi::bind_t<bool,boost::_mfi::cmf0<bool,expr_node>,boost::_bi::list1<boost::arg<1>
> > >(term_list::_Iterator<1> _First={expr_={...} }, term_list::_Iterator<1>
_Last={expr_={...} },
boost::_bi::bind_t<bool,boost::_mfi::cmf0<bool,expr_node>,boost::_bi::list1<boost::arg<1>
> > _Pred={...})  Line 1847 + 0x64 bytes    C++
expr_node::organize()  Line 213 + 0x77 bytes    C++

Perhaps it's related to the implementation of swap() for variants?   If a
more detailed code sample is needed, I can upload this entire program to a
web server for someone to download.

Zach