On 2/19/07 12:37 AM, in article erbb9f$te5$1@aioe.org, "Kai-Uwe Bux"
<jkherciueh@gmx.net> wrote:

> Consider the virtual base class trick to make a class final:
>
> class protected_constructor {
>  protected:
>
>   protected_constructor ( void ) {}
>
> }; // protected_constructor
>
> #define FINAL_CLASS private virtual protected_constructor
>
> class X : FINAL_CLASS {};
>
> class Y : public X {};
>
> int main ( void ) {
>   X x; // fine: X is default constructible
>   Y y; // error: Y is not constructible
> }
>
>
> I wonder whether the standard needs to introduce something like an concept
> of inheritability.

I'm not sure where such a concept would ever be needed in the current
Standard - or if needed, why the Standard would not simply state that
a class's constructor must be public.

>
> a) Suppose a user defines an allocator type and uses the above to make it
> final. As far as I can see, the class so defined still can satisfy the
> allocator requirements. This would imply that container implementations
> that employ a derivation trick like
>
>   template < typename T, typename A, typename C >
>   class set {
>
>      struct tree_node : A {
>        ...
>      };
>
>      ...
>   }; // set
>
> to make use of empty base optimization are non-conforming. E.g., with my
> g++4.1.1, the following does not compile:
>
>
> #include <memory>
>
> template < typename T >
> struct bad_allocator : public std::allocator<T>, FINAL_CLASS {
>
>   bad_allocator ( void )
>     : std::allocator<T> ()
>   {}
>
>   bad_allocator ( bad_allocator const & other )
>     : std::allocator<T> ( other )
>   {}
>
>   template < typename S >
>   bad_allocator ( bad_allocator<S> const & other )
>     : std::allocator<T>( other )
>   {}
>
>   template < typename S >
>   struct rebind {
>     typedef bad_allocator<S> other;
>   };
>
> };
>
> #include <list>
>
> int main ( void ) {
>   std::list< int, bad_allocator<int> > the_list;
>   the_list.push_back( 2 );
> }
>
>
> When I leave out the FINAL_CLASS trick, it compiles just fine.

Removing "virtual" from the protected_constructor base class (while
leaving the constructor protected) also solves the problem - so the
protected constructor cannot be the reason why gcc failed to compile
the original program. Futhermore, the fact that though both the EDG
and Comeau compilers accept the original program strongly suggests
that that the compilation failure is unique to gcc.

And in fact, the original program does not violate any requirement for
allocator objects, but rather provides - by combining as it does class
templates, protected constructors and private virtual base classes, a
"torture-test' that simply overwhelms gcc's "concept-checking" code.
This concept-checking code - ironically - is meant to test the
parameterized types supplied by the user program for compliance with
the Standard's requirements. But as it turns out, it is only the
presence of this test that is preventiing an otherwise correct C++
program from compiling successfully.

Now a program that breaks a concept check test is not the same as a
program that fails a concept check test. In fact, since the concept
check was never performed - there is no reason to conclude that the
program has a problem at all. In this case, the problem lies with
gcc's well-intentioned - if not always completely effectual - "concept
checking" extension to the C++ Standard Library - and is not due to
any kind of unwritten "inheritable" requirement in the Standard.

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:

> On 2/19/07 12:37 AM, in article erbb9f$te5$1@aioe.org, "Kai-Uwe Bux"
> <jkherciueh@gmx.net> wrote:
>
>> Consider the virtual base class trick to make a class final:
>>
>> class protected_constructor {
>>  protected:
>>
>>   protected_constructor ( void ) {}
>>
>> }; // protected_constructor
>>
>> #define FINAL_CLASS private virtual protected_constructor
>>
>> class X : FINAL_CLASS {};
>>
>> class Y : public X {};
>>
>> int main ( void ) {
>>   X x; // fine: X is default constructible
>>   Y y; // error: Y is not constructible
>> }
>>
>>
>> I wonder whether the standard needs to introduce something like an
>> concept of inheritability.
>
> I'm not sure where such a concept would ever be needed in the current
> Standard - or if needed, why the Standard would not simply state that
> a class's constructor must be public.
>
>>
>> a) Suppose a user defines an allocator type and uses the above to make it
>> final. As far as I can see, the class so defined still can satisfy the
>> allocator requirements. This would imply that container implementations
>> that employ a derivation trick like
>>
>>   template < typename T, typename A, typename C >
>>   class set {
>>
>>      struct tree_node : A {
>>        ...
>>      };
>>
>>      ...
>>   }; // set
>>
>> to make use of empty base optimization are non-conforming. E.g., with my
>> g++4.1.1, the following does not compile:
>>
>>
>> #include <memory>
>>
>> template < typename T >
>> struct bad_allocator : public std::allocator<T>, FINAL_CLASS {
>>
>>   bad_allocator ( void )
>>     : std::allocator<T> ()
>>   {}
>>
>>   bad_allocator ( bad_allocator const & other )
>>     : std::allocator<T> ( other )
>>   {}
>>
>>   template < typename S >
>>   bad_allocator ( bad_allocator<S> const & other )
>>     : std::allocator<T>( other )
>>   {}
>>
>>   template < typename S >
>>   struct rebind {
>>     typedef bad_allocator<S> other;
>>   };
>>
>> };
>>
>> #include <list>
>>
>> int main ( void ) {
>>   std::list< int, bad_allocator<int> > the_list;
>>   the_list.push_back( 2 );
>> }
>>
>>
>> When I leave out the FINAL_CLASS trick, it compiles just fine.
>
> Removing "virtual" from the protected_constructor base class (while
> leaving the constructor protected) also solves the problem - so the
> protected constructor cannot be the reason why gcc failed to compile
> the original program.

Yes. So?

> Futhermore, the fact that though both the EDG
> and Comeau compilers accept the original program strongly suggests
> that that the compilation failure is unique to gcc.
>
> And in fact, the original program does not violate any requirement for
> allocator objects, but rather provides - by combining as it does class
> templates, protected constructors and private virtual base classes, a
> "torture-test' that simply overwhelms gcc's "concept-checking" code.
> This concept-checking code - ironically - is meant to test the
> parameterized types supplied by the user program for compliance with
> the Standard's requirements. But as it turns out, it is only the
> presence of this test that is preventiing an otherwise correct C++
> program from compiling successfully.

The failure of g++ is not related in any form to concept checking code. It
stems from the following trick used by the g++ folks to reduce the size of
a container class. It replaced a more involved template-based machinery
used in SGI-STL to optimize away instance-less allocators.

Consider the following basic layout for a single linked list:

template < typename T, typename Alloc >
struct slist {

  typedef T value_type;
  typedef
  typename Alloc::template rebind<value_type>::other
  allocator_type;

 private:

  struct node {

    value_type the_data;
    node *     the_next;

  };

  typedef
  typename Alloc::template rebind<node>::other
  node_allocator;

  node *         the_head_ptr;
  node_allocator the_allocator;

 public:

  slist ( Alloc alloc = Alloc() )
    : the_head_ptr ( 0 )
    , the_allocator ( alloc )
  {}

};

This requires an actual data field for the allocator. In practice, most
allocator classes are empty. Adding a byte just for that is wasteful. The
g++ folks therefore do something like this:

template < typename T, typename Alloc >
struct slist {

  typedef T value_type;
  typedef
  typename Alloc::template rebind<value_type>::other
  allocator_type;

 private:

  struct node {

    value_type the_data;
    node *     the_next;

  };

  typedef
  typename Alloc::template rebind<node>::other
  node_allocator;

  struct ancor : public node_allocator {

    node * the_head_ptr;

    ancor ( Alloc alloc )
      : node_allocator ( alloc )
      , the_head_ptr ( 0 )
    {}

  };

  ancor the_list_head;

 public:

  slist ( Alloc alloc = Alloc() )
    : the_list_head ( alloc )
  {}

};

Now, the compiler can use empty-base class optimization to do away with the
allocator subobject. The g++ folks do exactly this and none of it is part
of the concept checking machinery in the g++ library implementation.

But my question is not about the compliance of g++. My question is whether
the standard _should_ allow library implementors to use such optimization
tricks. As it stands, it seems that you cannot do this.


> Now a program that breaks a concept check test is not the same as a
> program that fails a concept check test. In fact, since the concept
> check was never performed - there is no reason to conclude that the
> program has a problem at all. In this case, the problem lies with
> gcc's well-intentioned - if not always completely effectual - "concept
> checking" extension to the C++ Standard Library - and is not due to
> any kind of unwritten "inheritable" requirement in the Standard.

I did not claim that the standard has an unwritten inheritable requirement.
I was suggesting putting in such a requirement to legalize some
optimization tricks for library implementors. I think there is little to no
chance that users make allocator classes final. So adding inheritability to
the allocator requirements is unlikely to break any existing code.


Best

Kai-Uwe Bux

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Feb 23, 7:50 am, jkherci...@gmx.net (Kai-Uwe Bux) wrote:
> I was suggesting putting in such a requirement to legalize some
> optimization tricks for library implementors. I think there is little to no
> chance that users make allocator classes final. So adding inheritability to
> the allocator requirements is unlikely to break any existing code.

By doing this one might consider to extend this requirement to
all currently available standard traits/policy classes.

But I don't think that either your proposal nor mine extended version
is actually necessary (at least currently). Taking the most recent
version of the type traits proposal into account, that is

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2157.html

one recognizes that the current definition of is_empty will exactly
exclude your case, namely be referencing the condition from
20.4.5.6 (Member introspection):

"T has no virtual base classes"

So it's just a question of the time that current libraries will adapt
their
internal decision logic which classes could legally be used for
empty-base-class optimization techniques.

Greetings from Bremen,

Daniel Kr   gler



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Consider the virtual base class trick to make a class final:

class protected_constructor {
 protected:

  protected_constructor ( void ) {}

}; // protected_constructor

#define FINAL_CLASS private virtual protected_constructor

class X : FINAL_CLASS {};

class Y : public X {};

int main ( void ) {
  X x; // fine: X is default constructible
  Y y; // error: Y is not constructible
}


I wonder whether the standard needs to introduce something like an concept
of inheritability.


a) Suppose a user defines an allocator type and uses the above to make it
final. As far as I can see, the class so defined still can satisfy the
allocator requirements. This would imply that container implementations
that employ a derivation trick like

  template < typename T, typename A, typename C >
  class set {

     struct tree_node : A {
       ...
     };

     ...
  }; // set

to make use of empty base optimization are non-conforming. E.g., with my
g++4.1.1, the following does not compile:


#include <memory>

template < typename T >
struct bad_allocator : public std::allocator<T>, FINAL_CLASS {

  bad_allocator ( void )
    : std::allocator<T> ()
  {}

  bad_allocator ( bad_allocator const & other )
    : std::allocator<T> ( other )
  {}

  template < typename S >
  bad_allocator ( bad_allocator<S> const & other )
    : std::allocator<T>( other )
  {}

  template < typename S >
  struct rebind {
    typedef bad_allocator<S> other;
  };

};

#include <list>

int main ( void ) {
  std::list< int, bad_allocator<int> > the_list;
  the_list.push_back( 2 );
}


When I leave out the FINAL_CLASS trick, it compiles just fine.


b) Also, I wonder, if there is any guarantee in the standard that
std::vector<> is not made final using the trick above. The reason to worry
is [17.4.4.7/1]

  It is unspecified whether a class in the C++ Standard Library is itself
  derived from other classes (with namesreserved to the implementation).

Alf Steinbach recently allerted me to [17.3.1.2]

  The library can be extended by a C++ program. Each clause, as applicable,
  describes the requirements that such extensions must meet. Such extensions
  are generally one of the following:
   ...
   ? Derived classes
   ...

However, [17.3.1.2] is informative and does not create requirements.


If the standard defined the inheritable concept, as it defines the
copy-constructible and assignable concepts, it could just state that user
defined allocators need to be inheritable. It could also assert that
library classes are inheritable unless explicitly specified otherwise.


Questions: Does the standard already imply that the bad_allocator template
from above does not meet the allocator requirements? Is it already clear
from the standard that std::vector<> (or, more drastically,
std::unary_function<>) are inheritable (meaning that constructible classes
can be derived from there)?

Also: a) If so, where would I find the corresponding provisions?
      b) If not, is that defect, or is it intentional?


Thanks

Kai-Uwe Bux

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]