Re: [boost] [intrusive] Interface for hooking into client code improvable?

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-08-10 09:17:04

Ion Gaztañaga wrote:
> Tobias Schwinger wrote:
>> The only potential problem I see is that
>>
>>     container< a_policy, another_policy >
>>
>> and
>>
>>     container< another_policy, a_policy >
>>
>> are distinct types and some compiler might not factor out redundant code 
>> properly. It can be dealt with in two ways:
> 
> This is quite frightening to me. There is another way to minimize bloat:

Sorry to frighten you. This is a non-issue (it didn't occur to me 
yesterday - must've been too late in my timezone), as we can use 
'container_xyz_impl' containing the actual code and pass the information 
from the policy into it in a defined order (see below for details).

Also, please keep in mind that we are talking about a workaround, 
because decent compilers should factor out redundant machine code 
automatically.

> typedef define_container< another_policy, a_policy >::type Container;
> 
> The combination is concentrated in the auxiliary define_container but 
> the resulting container is exactly the same. But it's not as easy to use 
> as the straight policy approach.
> 
> Another question is that Intrusive has already received a review, and 
> such important breaking change would need at least consensus from Boosters.

If it simplifies the usage it won't be that hard to reach. Of course 
it's best to make such changes before the official release with 1.35.

> This option has also the problem of instantiating different containers 
> with the same options, just because "options" will be a user type. 
> Another approach can be:
> 
> list<T, list_options<Policy1, Policy2, Policy3>::type>
>
> where the created type is unique type even if policies are passed in 
> different order, because list_options does the job of creating a unique 
> options type for the same policies.

Well, having the library do that internally would be "option b" from my 
previous post.

But wait - it's not necessary because

     'policies::a_specific_option'

and

     'different_type_for_same_policies::a_specific_option'

are guaranteed to be identical. Those types can be used to select the 
code and the problem should be solved (see code).

Also note that one can provide "factorization aid" at every granularity 
desired putting the code into several templates only dependending on the 
types needed (not done in the sample code).

> The question is if the use of policies will simplify the life of the 
> average programmer or if specifying "normal" (meaning raw) template
> parameters will be easier.

The most important one.

First of all, I would avoid that buzzword (yes, I used it too) but it 
might easily provoke the false impression of the "Alexandrescu-inspired 
kill all birds there are with one stone" kind of thing ;-). "Named 
template arguments" probably cuts it better.

Second, the current usage is quite far away from "normally specifying 
template arguments", isn't it?

So it comes down to whether we prefer to write e.g.

(variant 1)

     container< type::value_traits<type>, a_default, another_default,
        false >

or (variant 2)

     struct my_settings : defaults
     {
         static bool const constant_time_size_operation = false;
     };

     container< type, my_settings >

or (variant 3)

     container< type, constant_time_size_operation<false> >

Is it easier to write customize a container with variant 1, 2 or 3?

With variant 1 you have to know the defaults and the position of the 
option to change.

With variant 2 you have to know how to define the traits (which might 
become more complicated in practice - as mentioned in the previous 
post), plus the name of the option to change and how to specify it.

With variant 3 you only need to know the name of the option to change 
and how to specify it (where it seems easier to pass something as a 
template argument than to define it within a traits class).

Now imagine being unfamiliar with Intrusive, reading the code (and the 
source file uses a whole bunch of libraries -- you gotta get this one 
bug fixed, the author is on vacation and the customer's angrily awaiting 
the already-delayed deployment ;-) ).

Which one is the easiest to understand (ideally without reading through 
the docs)?

So variant 1 is certainly the least expressive: "What the heck does that 
'false' say?" and the defaults might not be identifiable as such and 
cause similar questions.

Variant 2 is self-explanatory but too verbose, thus probably making the 
customization of the container seem more important than it actually is - 
the constant time size operation might got disabled because it's not 
needed - just a nuance for optimization.

Variant 3 doesn't have any of these drawbacks.

Regards,
Tobias


// Defaults

struct container_xyz_defaults
{
    static bool const constant_time_size = true;

    typedef void tag;

    template<typename T>
    struct value_traits
    {
        typedef T* pointer_type;
        typedef T& reference;
        // ...
    };
    // ...
};

// Setters

template<bool Enabled>
struct constant_time_size
{
    template<class Base>
    struct apply_options : Base
    {
        static bool const constant_time_size = Enabled;
    };
};

template<typename T>
struct tag
{
    template<class Base>
    struct apply_options : Base
    {
        typedef T tag;
    };
};

template<typename T>
struct offset_ptr {}; // just pretend it's there...

struct offset_ptr_storage
{
    template<class Base>
    struct apply_options : Base
    {
        template<typename T>
        struct value_traits
        {
            typedef offset_ptr<T> pointer_type;
            typedef T& reference;
            // ...
        };
    };
};

struct none_specified
{
    template<class Base>
    struct apply_options : Base
    { };
};

// ...

namespace detail
{

    template<typename ValueTraits, typename Tag, bool ConstantTimeSize>
    class container_xyz_impl
    {
        // ...
      public:
        typedef Tag tag;
        typedef typename ValueTraits::pointer_type pointer_type;
        static bool const constant_time_size = ConstantTimeSize;
        // ...

        // <--- member functions go here
    };

    template<typename T, class Policy1, class Policy2, class Policy3,
        class Policy4>
    class container_xyz_impl_spec
    {
        // join policies
        typedef
            typename Policy4::template apply_options<
                typename Policy3::template apply_options<
                    typename Policy2::template apply_options<
                        typename Policy1::template apply_options<
                            container_xyz_defaults
            >   >   >   > policies;

        // specialize value_traits and extract props
        typedef typename policies::template value_traits<T> value_traits;
        typedef typename policies::tag tag;
        static bool const constant_time_size = policies::constant_time_size;

      public:

        typedef container_xyz_impl<value_traits,tag,constant_time_size> type;
    }; 

} // namespace detail

template<typename T, class Policy1 = none_specified, 
    class Policy2 = none_specified, class Policy3 = none_specified,
    class Policy4 = none_specified >
class container_xyz
  : public detail::container_xyz_impl_spec<
      T,Policy1,Policy2,Policy3,Policy4 >::type
{
  public:

    // <-- dumb, forwarding inline ctor comes here 

    // Note: If inheritance does not work to make code generation behave,
    // another option is to hold the implementing class by value and add
    // more dumb, forwarding inline functions.
};

// Demonstrate it

#include <iostream>
#include <typeinfo>

template<class C>
void show_config(char const * name)
{
    std::cout << 
    name << ":" << std::endl <<
    "  tag: " << typeid( typename C::tag ).name() << std::endl <<
    "  pointer_type: " << typeid( typename C::pointer_type ).name() << std::endl <<
    "  constant_time_size: " << C::constant_time_size << std::endl <<
    std::endl;
}

int main()
{
    show_config<   container_xyz< int, constant_time_size<false> >   >
                 ("container_xyz< int, constant_time_size<false> >");

    show_config<   container_xyz< int, offset_ptr_storage >   >
                 ("container_xyz< int, offset_ptr_storage >");

    show_config<   container_xyz< int, offset_ptr_storage, tag<int> >   >
                 ("container_xyz< int, offset_ptr_storage, tag<int> >");

    return 0;
}