On Wed, Aug 12, 2015 at 9:11 PM, Alex Rousskov < rouss...@measurement-factory.com> wrote:
> On 08/12/2015 09:36 AM, Kinkie wrote:
>
> > So I went ahead and just implemented it, starting from your observations.
> > It's a bit more complex that your proposal, as I took the chance to
> > implement bidirectional forward and reverse iterators.
> > The attached patch is in changeset 14235 of
> > lp:~kinkie/squid/coverity-fixes, but since the code is quite well
> > self-contained I'd like to submit it for audit as a standalone unit; If
>
> Yes, submitting Enum iterators for review as a stand-alone patch is the
> right thing to do. Hiding this and other significant changes under
> "coverity fixes" cover is wrong IMO, even if those changes were prompted
> by something Coverity has detected.
>
> I would encourage you to show actual Squid usage examples (besides
> artificial test cases), either in the patch itself or in the patch cover
> email.
>
./src/HttpHdrCc.cc:HttpHdrCcType &operator++ (HttpHdrCcType &aHeader)
./src/HttpHdrSc.cc:http_hdr_sc_type &operator++ (http_hdr_sc_type &aHeader)
./src/HttpHdrScTarget.cc:http_hdr_sc_type &operator++ (http_hdr_sc_type
&aHeader);
./src/HttpMsg.cc:HttpMsgParseState &operator++ (HttpMsgParseState &aState)
./src/errorpage.cc:err_type &operator++ (err_type &anErr)
./src/http/RequestMethod.cc:operator++ (Http::MethodType &aMethod)
./src/mem/old_api.cc:mem_type &operator++ (mem_type &aMem)
These are all used to iterate over enums from what I can tell. There are
for sure more cases using different techniques, that are less trivial to
detect.
> Also, please adjust the WholeEnum documentation. It is currently too
> similar to EnumRange, including the identical first/summary line. It is
> often best to document children classes in terms of parent classes
> rather then repeating everything the parent documentation [currently]
> says IMO. For example:
>
> /// EnumRange for iterating all enum values, from enumBegin_ up to, but
> // not including, enumEnd_. The two markers must be present in the enum.
> template <typename Enum>
> class WholeEnum ...
>
>
> If you have not considered implementing WholeEnum without inheritance,
> please do so. I speculate that lack of any data members may help inline
> WholeEnum. Please note that I am just asking you to _consider_ this. I
> do not have enough information to insist on it.
>
As all classes are nonvirtual and everything is in the same translation
unit, for now I would skip that. and avoid the code duplication.
> > + typedef typename std::underlying_type<Enum>::type value_t;
> > + value_t current_value;
>
> This type and data member is more about iteration position than "value"
> (in STL sense). AFAICT, STL calls this type "iterator_type" and the data
> member "current". I think that naming is better than yours.
>
Ok
>
>
> > + reverse_iterator rbegin() const { auto i = reverse_iterator(end_);
> ++i; return i; }
> > + reverse_iterator rend() const { auto i = reverse_iterator(begin_);
> ++i; return i; }
>
> If these methods can be implemented simply as
>
> reverse_iterator rbegin() const { return ++reverse_iterator(end_); }
> reverse_iterator rend() const { return ++reverse_iterator(begin_); }
>
> then please simplify.
>
Ok.
> I do not understand how rend() would actually work when iterating whole
> enums! For a typical enum that starts with a zero-valued item, will the
> rend() position (called current_value in your code) go negative?? Is
> that actually guaranteed to work by the standard? If not, we may need to
> require a begin-1 marker (which may be negative if needed)!
>
It'll go negative, or in case of unsigned underlyng_type, wrap. It'll still
work (added a test for that), to be sure.
> Are you sure you need reverse iterators at all?
>
No, not sure; I added them mostly for completeness sake.
> [ EnumRange is not suitable for iterating up to the end of an enum that
> does not have an end+1 marker. This limitation is not a bug, but may be
> another reason to require all enums to have markers. ]
>
I've added documentation to highlight that corner case so it doesn't come
unexpected.
I've considered changing it so that it includes the last value in the
range, but in the end decided against it as it's inconsistent with common
behavior.
In some cases it may not be feasible to have markers. Maybe the enum comes
from a library, or maybe markers may hurt some code path for all we know.
As long as the behavior is well documented and consistent, I don't think
it'll be a problem.
> If possible, please add and use a global function to guess EnumRange
> template parameter value from the actual function parameter types and
> return the right EnumRange object, to avoid writing Enum type three
> times when using EnumRangeT<>.
>
> template <typename Enum>
> EnumRangeT<Enum> EnumRange(Enum begin, Enum end) {
> return EnumRangeT<Enum>(begin, end);
> }
>
>
Done.
I'm attaching the resulting files. If that's OK by you, I'll start using
them and merge together with the next round of coverity-fixes.
>
> HTH,
>
> Alex.
>
>
>
> > On 08/05/2015 07:58 PM, Kinkie wrote:
> >
> >> What I understand from the changes you propose is that:
> >
> >> 1. instead of having explicit begin/end markers passed as template
> >> arguments you propose to have a convention on begin/end markers.
> >
> > There are several different things/layers mixed up here:
> >
> > * If we want to use range loops for enums [in a sane way], then our
> > enums should have begin/end markers. Many already do, but we will have
> > to standardize their names and fill the gaps.
> >
> > * The begin/end parameters should not be template parameters.
> >
> > * If we need to iterate sub-ranges, then we should add EnumRangeT<Enum>
> > class with begin/end as constructor parameters (see below).
> >
> >
> >> 2. you skip the typedef fixing these parameters in favor of letting the
> >> template parameters appear in the calls.
> >
> > There are two separate issues/layers here:
> >
> > * Naming an expression is a good idea, especially if that name is going
> > to be used multiple times.
> >
> > * Fewer template parameters are generally better if they can accomplish
> > the same thing as more template parameters.
> >
> >
> >> 1. looks interesting, especially as an enum missing those markers will
> >> fail to compile. Maybe both approaches can be combined by using default
> >> template arguments, what do you think?
> >> template <typename C, C first = C::enumBegin_, C last_plus_one =
> >> C::enumEnd_>
> >
> > I think we should not specify iteration range boundaries as template
> > parameters.
> >
> >
> >> 3. we could maybe combine the benefits of beautiful range-for and ugly
> >> explicit-for also for shorter ranges by having (in the class-based
> >> variant), on top of what you have already proposed (untested)
> >
> > Yes, if sub-range iteration using range loops is needed, then we should
> > add EnumRangeT<Enum> class that does it. Sorry if I have not mentioned
> > that explicitly.
> >
> > Your sketch for that class is fine, but it will be a EnumRangeT class,
> > separate from simpler WholeEnum, and we would try to define a function
> > that will create that EnumRangeT object so that we only have to type
> > "Numbers" zero or two times as illustrated below:
> >
> > template <typename Enum>
> > inline
> > EnumRangeT<Enum> EnumRange(const Enum from, const Enum to) {
> > return EnumRangeT<Enum>(from, to);
> > }
> >
> >
> > So that instead of:
> >
> >> for (auto i : WholeEnum<Numbers>(Numbers::one, Numbers::three)) {
> >> // do stuff
> >> }
> >
> > we could do:
> >
> > // iterating sub-range of a class enum:
> > for (auto i: EnumRange(Numbers::one, Numbers::three)) ...
> >
> > // iterating sub-range of a global C enum:
> > for (auto i: EnumRange(one, three)) ...
> >
> > // iterating a whole enum:
> > for (auto i: WholeEnum<Numbers>()) ...
> >
> >
> > Again, the above range objects can be named (and the first two should be
> > named if they are used more than once). For example:
> >
> > WholeEnum<Numbers> AllNumbers() { return WholeEnum<Numbers>(); }
> >
> > EnumRange<Numbers> FooBarNumbers() { return EnumRange(Numbers::foo,
> > Numbers::bar); }
> >
> >
> >
> >> It looks to me that I have crossed an itch you feel as well,
> >
> > No, I am just trying to help you scratch your itch without scarring
> > Squid code. I do not know whether your itch is real or imaginary.
> >
> >
> > Cheers,
> >
> > Alex.
> >
>
>
--
Francesco
#ifndef SQUID_BASE_ENUMITERATOR_H
#define SQUID_BASE_ENUMITERATOR_H
/*
* Copyright (C) 1996-2015 The Squid Software Foundation and contributors
*
* Squid software is distributed under GPLv2+ license and includes
* contributions from numerous individuals and organizations.
* Please see the COPYING and CONTRIBUTORS files for details.
*/
#include <iterator>
#include <type_traits>
/* code shared between forward and reverse iterators */
template <typename Enum>
class EnumIteratorBase : public std::iterator<std::bidirectional_iterator_tag, Enum>
{
public:
explicit EnumIteratorBase(Enum e) : current(static_cast<iterator_type>(e)) {}
bool operator==(const EnumIteratorBase &i) const {
return current == i.current;
}
bool operator!=(const EnumIteratorBase &i) const {
return current != i.current;
}
Enum operator*() const {
return static_cast<Enum>(current);
}
protected:
typedef typename std::underlying_type<Enum>::type iterator_type;
iterator_type current;
};
/** iterator over an enum type
*
*/
template <typename Enum>
class EnumIterator : public EnumIteratorBase<Enum>
{
public:
explicit EnumIterator(Enum e) : EnumIteratorBase<Enum>(e) {}
// prefix increment
EnumIterator& operator++() {
++ EnumIteratorBase<Enum>::current;
return *this;
}
// postfix increment
EnumIterator& operator++(int) {
EnumIterator rv(*this);
++ EnumIteratorBase<Enum>::current;
return rv;
}
// prefix decrement
EnumIterator& operator--() {
-- EnumIteratorBase<Enum>::current;
return *this;
}
// postfix decrement
EnumIterator& operator--(int) {
EnumIterator rv(*this);
-- EnumIteratorBase<Enum>::current;
return rv;
}
};
template <typename Enum>
class ReverseEnumIterator : public EnumIteratorBase<Enum>
{
public:
explicit ReverseEnumIterator(Enum e) : EnumIteratorBase<Enum>(e) {}
// prefix increment
ReverseEnumIterator& operator++() {
-- EnumIteratorBase<Enum>::current;
return *this;
}
// postfix increment
ReverseEnumIterator& operator++(int) {
ReverseEnumIterator rv(*this);
-- EnumIteratorBase<Enum>::current;
return rv;
}
// prefix decrement
ReverseEnumIterator& operator--() {
++ EnumIteratorBase<Enum>::current;
return *this;
}
// postfix decrement
ReverseEnumIterator& operator--(int) {
ReverseEnumIterator rv(*this);
++ EnumIteratorBase<Enum>::current;
return rv;
}
};
/** Class expressing a range of an enum
*
* This class is suited to use range-for over a continuous portion of an enum.
* This class requires that the underlying enum values be represented by
* continuous values of an integral type.
* Typical use:
* for ( auto enumvalue : EnumRangeT<EnumType>(EnumType::somevalue,
* EnumType::someOtherValue) )
* { do_stuff(); }
* Note that EnumIterator<enum>(EnumType::firstmember,EnumType::lastmember)
* will miss EnumType::lastmember while iterating. If you need to iterate
* over all of EnumType, use class WholeEnum. Otherwise you'll have to
* explicitly address lastmember outside the iteration loop.
*/
template <typename Enum>
class EnumRangeT
{
public:
typedef EnumIterator<Enum> iterator;
typedef ReverseEnumIterator<Enum> reverse_iterator;
EnumRangeT(Enum first, Enum one_past_last) : begin_(first), end_(one_past_last) { }
iterator begin() const { return iterator(begin_);}
iterator end() const { return iterator(end_);}
reverse_iterator rbegin() const { return ++reverse_iterator(end_); }
reverse_iterator rend() const { return ++reverse_iterator(begin_); }
private:
Enum begin_;
Enum end_;
};
/// convenience function to deduce the right type for instantiating EnumRangeT
template <typename Enum>
EnumRangeT<Enum> EnumRange(Enum begin, Enum one_past_end)
{
return EnumRangeT<Enum>(begin,one_past_end);
}
/** Class for iterating all enum values, from Enum::enumBegin_ up to, but
* not including, Enum::enumEnd_. Both markers must be present as enum values.
*
* This class requires that the underlying enum values be represented by
* continuous values of an integral type.
* Typical use: for( auto enumvalue : WholeEnum<EnumType>() ) { do_stuff(); }
*/
template <typename Enum>
class WholeEnum : public EnumRangeT<Enum>
{
public:
WholeEnum() : EnumRangeT<Enum>(Enum::enumBegin_, Enum::enumEnd_) {}
};
#endif /* SQUID_BASE_ENUMITERATOR_H */
testEnumIterator.cc
Description: Binary data
#ifndef SQUID_TESTENUMITERATOR_H_
#define SQUID_TESTENUMITERATOR_H_
/*
* Copyright (C) 1996-2015 The Squid Software Foundation and contributors
*
* Squid software is distributed under GPLv2+ license and includes
* contributions from numerous individuals and organizations.
* Please see the COPYING and CONTRIBUTORS files for details.
*/
#include "base/EnumIterator.h"
#include <cppunit/extensions/HelperMacros.h>
class testEnumIterator : public CPPUNIT_NS::TestFixture
{
CPPUNIT_TEST_SUITE( testEnumIterator );
CPPUNIT_TEST( testForwardIter );
CPPUNIT_TEST( testReverseIter );
CPPUNIT_TEST( testBidirectionalIter );
CPPUNIT_TEST( testRangeFor );
CPPUNIT_TEST( testRangeForRange );
CPPUNIT_TEST( testUnsignedEnum );
CPPUNIT_TEST_SUITE_END();
protected:
void testForwardIter();
void testReverseIter();
void testBidirectionalIter();
void testRangeFor();
void testRangeForRange();
void testUnsignedEnum();
};
#endif /* SQUID_TESTENUMITERATOR_H_ */
_______________________________________________ squid-dev mailing list squid-dev@lists.squid-cache.org http://lists.squid-cache.org/listinfo/squid-dev
