On Sun, Dec 27, 2015 at 2:50 AM, Alex Rousskov
<[email protected]> wrote:
> On 12/26/2015 09:03 AM, Kinkie wrote:
>> Hi all,
>> the attached patch improves CharacterSet by adding a subtraction
>> operator, equality test and associated unit tests.
>
Hi Alex, thanks for taking the time.
> Perhaps this is different in C++11, but IIRC we are supposed to:
>
> 1. declare non-modifying operators such as "-" outside the class
That's typical but not mandatory. Changing all to reflect
> 2. declare an inequality operator "!=" when declaring an equality operator
If unequality is not tested.. Still, adding it is trivial, so I'm doing that.
> For #1, you can claim code consistency as an excuse because the "+"
> operator was already misplaced, but since no existing or proposed code
> uses the new operators (AFAIK), it seems like it would be a good idea to
> fix the wrong location before (or while) adding the new [unused] ones.
Done.
>
>
>> + if (this == &c) // identity test
>> + return true;
>
> I would remove this check as unneeded unless you are sure that the
> comparison with self is common enough to optimize for. If you keep this,
> please s/identity test/optimization: fast comparison with self/ because
> I do not think the term "identity test" is standard [enough] to be
> recognized by many readers and googling it does not help.
>
>
>> + auto e=chars_.cend();
>> + for (auto i = chars_.cbegin(), j = c.chars_.cbegin(); i != e; ++i, ++j)
>> {
>> + if (*i != *j)
>> + return false;
>> + }
>
> Is the existing Storage::operator "==" so bad that we need to hand-roll
> a loop [with a critical hidden assumption] like that? If hand-rolling is
> needed, please at least add a comment that the code assumes that all
> chars_ containers have the same length.
That's ignorance on my side; I now checked that
std::vector::operator== compares elements; replacing whole method with
call to that.
The assumption is not hidden, it's an invariant enforced by all constructors.
>> + /// remove all characters from the given CharacterSet to this one
>> + CharacterSet &operator -=(const CharacterSet &src);
>
> Please remove the "to this one" copy-paste typo.
>
> I recommend rephrasing the description to document what happens when the
> character cannot be removed because it is not in the "this" set. For
> example:
>
> /// set subtraction: remove all characters that are also in src
>
>
> "src" is a weird name for the parameter subtraction operator argument.
> You can cite code consistency as an excuse but consider using "other" or
> perhaps something like "banned" instead.
rhs? that's fairly common for operators
>> /// return a new CharacterSet containing the union of two sets, labeled
>> as the first argument
>> CharacterSet operator +(const CharacterSet &src) const;
> ...
>> + /// return a new CharacterSet containing the set of characters in the
>> first but not in the second
>> + CharacterSet operator -(const CharacterSet &src) const;
>
>
> It is funny that you preserved many bad things but decided to drop
> documentation about the label. Please add it.
>
> Please note that neither the old operator "+" nor the new operator "-"
> have two [explicit] arguments [until they are moved outside the class as
> discussed in #1 above] so the comment using words "first" and "second"
> is rather confusing!
Moved outside class; renamed parameters to lhs and rhs, reworked
doxygen comment.
>> +static
>> +std::ostream& operator<< (std::ostream &s, const CharacterSet &c)
>> +{
>> + s << "CharacterSet(" << c.name << ')';
>> + return s;
>> +}
>> +
>
> Perhaps this should be provided in the CharacterSet header, for all to
> use? You would have to split the definition from the declaration to
> avoid dragging iostream into the header, but this operator feels useful
> to me, even in its current "primitive" form.
I've thought about it, and decided not to, as it'd pull in iostream to
all users of CharacterSet.
This is mostly meant as a convenience to allow using
CPPUNIT_ASSERT_EQUAL which is more telling that CPPUNIT_ASSERT but
requires being able to print arguments.
>
>
>> - for (int j = 0; j < 255; ++j)
>> - if (j != '0')
>> + for (int j = 0; j < 255; ++j) {
>> + if (j != '0') {
>> CPPUNIT_ASSERT_EQUAL(false,t[j]);
>> + } else {
>> + CPPUNIT_ASSERT_EQUAL(true,t[j]);
>> + }
>> + }
>
> If polishing this code is in scope, consider fixing the loop boundary as
> well: There is nothing so special about character with codepoint 255 to
> exclude it AFAICT.
Right.
>> +void
>> +testCharacterSet::CharacterSetSubtract()
>> +{
>> + CharacterSet sample(NULL, "0123456789aAbBcCdDeEfFz");
>> + sample -= CharacterSet(NULL, "z");
>> + CPPUNIT_ASSERT_EQUAL(CharacterSet::HEXDIG, sample);
>> +}
>
>
> It would be good to have an A-B test where B has [some] characters not
> present in A.
>
> Since operator "-" operator is implemented using operator "-=" it may be
> better to test the former (if we have to pick between testing one or the
> other).
Ok.
Updated patch attached; thanks again!
--
Francesco
=== modified file 'src/base/CharacterSet.cc'
--- src/base/CharacterSet.cc 2015-01-13 07:25:36 +0000
+++ src/base/CharacterSet.cc 2015-12-27 08:57:06 +0000
@@ -10,46 +10,53 @@
#include "CharacterSet.h"
#include <algorithm>
#include <functional>
CharacterSet &
CharacterSet::operator +=(const CharacterSet &src)
{
Storage::const_iterator s = src.chars_.begin();
const Storage::const_iterator e = src.chars_.end();
Storage::iterator d = chars_.begin();
while (s != e) {
if (*s)
*d = 1;
++s;
++d;
}
return *this;
}
-CharacterSet
-CharacterSet::operator +(const CharacterSet &src) const
+CharacterSet &
+CharacterSet::operator -=(const CharacterSet &src)
{
- CharacterSet rv(*this);
- rv += src;
- return rv;
+ Storage::const_iterator s = src.chars_.begin();
+ const Storage::const_iterator e = src.chars_.end();
+ Storage::iterator d = chars_.begin();
+ while (s != e) {
+ if (*s)
+ *d = 0;
+ ++s;
+ ++d;
+ }
+ return *this;
}
CharacterSet &
CharacterSet::add(const unsigned char c)
{
chars_[static_cast<uint8_t>(c)] = 1;
return *this;
}
CharacterSet &
CharacterSet::addRange(unsigned char low, unsigned char high)
{
//manual loop splitting is needed to cover case where high is 255
// otherwise low will wrap, resulting in infinite loop
while (low < high) {
chars_[static_cast<uint8_t>(low)] = 1;
++low;
}
chars_[static_cast<uint8_t>(high)] = 1;
return *this;
@@ -64,54 +71,77 @@ CharacterSet::complement(const char *lab
std::logical_not<Storage::value_type>());
return result;
}
CharacterSet::CharacterSet(const char *label, const char * const c) :
name(label == NULL ? "anonymous" : label),
chars_(Storage(256,0))
{
const size_t clen = strlen(c);
for (size_t i = 0; i < clen; ++i)
add(c[i]);
}
CharacterSet::CharacterSet(const char *label, unsigned char low, unsigned char high) :
name(label == NULL ? "anonymous" : label),
chars_(Storage(256,0))
{
addRange(low,high);
}
+CharacterSet::CharacterSet(const char *label, std::initializer_list<std::pair<uint8_t, uint8_t>> ranges) :
+ name(label == NULL ? "anonymous" : label),
+ chars_(Storage(256,0))
+{
+ for (auto range: ranges)
+ addRange(range.first, range.second);
+}
+
+/** CharacterSet addition
+ *
+ * return a new CharacterSet containing the union of two sets
+ * labeled as the first argument
+ */
+CharacterSet
+operator+ (CharacterSet lhs, const CharacterSet &rhs)
+{
+ lhs += rhs;
+ return lhs;
+}
+
+/** CharacterSet addition
+ *
+ * return a new CharacterSet containing characters set in lhs but not in rhs,
+ * labeled as lhs
+ */
+CharacterSet
+operator- (CharacterSet lhs, const CharacterSet &rhs)
+{
+ lhs -= rhs;
+ return lhs;
+}
+
const CharacterSet
// RFC 5234
-CharacterSet::ALPHA("ALPHA", "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"),
- CharacterSet::BIT("BIT","01"),
- CharacterSet::CR("CR","\r"),
-#if __cplusplus == 201103L
-//CharacterSet::CTL("CTL",{{0x01,0x1f},{0x7f,0x7f}}),
-#endif
- CharacterSet::DIGIT("DIGIT","0123456789"),
- CharacterSet::DQUOTE("DQUOTE","\""),
- CharacterSet::HEXDIG("HEXDIG","0123456789aAbBcCdDeEfF"),
- CharacterSet::HTAB("HTAB","\t"),
- CharacterSet::LF("LF","\n"),
- CharacterSet::SP("SP"," "),
- CharacterSet::VCHAR("VCHAR", 0x21, 0x7e),
-// RFC 7230
- CharacterSet::WSP("WSP"," \t"),
-#if __cplusplus == 201103L
-//CharacterSet::CTEXT("ctext",{{0x09,0x09},{0x20,0x20},{0x2a,0x5b},{0x5d,0x7e},{0x80,0xff}}),
-#endif
- CharacterSet::TCHAR("TCHAR","!#$%&'*+-.^_`|~0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"),
- CharacterSet::SPECIAL("SPECIAL","()<>@,;:\\\"/[]?={}"),
-#if __cplusplus == 201103L
-//CharacterSet::QDTEXT("QDTEXT",{{0x09,0x09},{0x20,0x21},{0x23,0x5b},{0x5d,0x7e},{0x80,0xff}}),
-#endif
- CharacterSet::OBSTEXT("OBSTEXT",0x80,0xff),
-// RFC 7232
-#if __cplusplus == 201103L
-//CharacterSet::ETAGC("ETAGC",{{0x21,0x21},{0x23,0x7e},{0x80,0xff}}),
-#endif
-// RFC 7235
- CharacterSet::TOKEN68C("TOKEN68C","-._~+/0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
- ;
-
+ CharacterSet::ALPHA("ALPHA", "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"),
+ CharacterSet::BIT("BIT","01"),
+ CharacterSet::CR("CR","\r"),
+ CharacterSet::CTL("CTL",{{0x01,0x1f},{0x7f,0x7f}}),
+ CharacterSet::DIGIT("DIGIT","0123456789"),
+ CharacterSet::DQUOTE("DQUOTE","\""),
+ CharacterSet::HEXDIG("HEXDIG","0123456789aAbBcCdDeEfF"),
+ CharacterSet::HTAB("HTAB","\t"),
+ CharacterSet::LF("LF","\n"),
+ CharacterSet::SP("SP"," "),
+ CharacterSet::VCHAR("VCHAR", 0x21, 0x7e),
+ // RFC 7230
+ CharacterSet::WSP("WSP"," \t"),
+ CharacterSet::CTEXT("ctext",{{0x09,0x09},{0x20,0x20},{0x2a,0x5b},{0x5d,0x7e},{0x80,0xff}}),
+ CharacterSet::TCHAR("TCHAR","!#$%&'*+-.^_`|~0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"),
+ CharacterSet::SPECIAL("SPECIAL","()<>@,;:\\\"/[]?={}"),
+ CharacterSet::QDTEXT("QDTEXT",{{0x09,0x09},{0x20,0x21},{0x23,0x5b},{0x5d,0x7e},{0x80,0xff}}),
+ CharacterSet::OBSTEXT("OBSTEXT",0x80,0xff),
+ // RFC 7232
+ CharacterSet::ETAGC("ETAGC",{{0x21,0x21},{0x23,0x7e},{0x80,0xff}}),
+ // RFC 7235
+ CharacterSet::TOKEN68C("TOKEN68C","-._~+/0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
+ ;
=== modified file 'src/base/CharacterSet.h'
--- src/base/CharacterSet.h 2015-01-13 07:25:36 +0000
+++ src/base/CharacterSet.h 2015-12-27 09:34:41 +0000
@@ -1,123 +1,127 @@
/*
* 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.
*/
#ifndef _SQUID_SRC_PARSER_CHARACTERSET_H
#define _SQUID_SRC_PARSER_CHARACTERSET_H
+#include <initializer_list>
#include <vector>
/// optimized set of C chars, with quick membership test and merge support
class CharacterSet
{
public:
typedef std::vector<uint8_t> Storage;
/// define a character set with the given label ("anonymous" if NULL)
/// with specified initial contents
CharacterSet(const char *label, const char * const initial);
/// define a character set with the given label ("anonymous" if NULL)
/// containing characters defined in the supplied ranges
/// \see addRange
CharacterSet(const char *label, unsigned char low, unsigned char high);
+ /// define a character set with the given label ("anonymous" if NULL)
+ /// containing characters defined in the supplied list of low-high ranges
+ /// \see addRange
+ CharacterSet(const char *label, std::initializer_list<std::pair<uint8_t,uint8_t>> ranges);
+
/// whether a given character exists in the set
bool operator[](unsigned char c) const {return chars_[static_cast<uint8_t>(c)] != 0;}
/// add a given character to the character set
CharacterSet & add(const unsigned char c);
/// add a list of character ranges, expressed as pairs [low,high], including both ends
CharacterSet & addRange(unsigned char low, unsigned char high);
- /// add all characters from the given CharacterSet to this one
- CharacterSet &operator +=(const CharacterSet &src);
+ /// set addition: add all characters that are also in src
+ CharacterSet &operator +=(const CharacterSet &rhs);
- /// return a new CharacterSet containing the union of two sets
- CharacterSet operator +(const CharacterSet &src) const;
+ /// set subtraction: remove all characters that are also in src
+ CharacterSet &operator -=(const CharacterSet &rhs);
/// return a new CharacterSet containing characters not in this set
CharacterSet complement(const char *complementLabel = NULL) const;
/// change name; handy in const declarations that use operators
CharacterSet &rename(const char *label) { name = label; return *this; }
+ /// comparison operator. Ignores label
+ bool operator == (const CharacterSet &cs) const { return chars_ == cs.chars_; }
+ bool operator != (const CharacterSet &cs) const { return !operator==(cs); }
+
/// optional set label for debugging (default: "anonymous")
const char * name;
// common character sets, RFC 5234
// A-Za-z
static const CharacterSet ALPHA;
// 0-1
static const CharacterSet BIT;
// carriage return
static const CharacterSet CR;
// controls
-#if __cplusplus == 201103L
- // ready but disabled as needs C++11 constructor
- //static const CharacterSet CTL;
-#endif
+ static const CharacterSet CTL;
// 0-9
static const CharacterSet DIGIT;
// double quote
static const CharacterSet DQUOTE;
// 0-9aAbBcCdDeEfF
static const CharacterSet HEXDIG;
// horizontal tab
static const CharacterSet HTAB;
// line feed
static const CharacterSet LF;
// white space
static const CharacterSet SP;
// visible (printable) characters
static const CharacterSet VCHAR;
// <space><tab>
static const CharacterSet WSP;
// HTTP character sets, RFC 7230
// ctext
-#if __cplusplus == 201103L
- // ready but disabled as needs C++11 constructor
- //static const CharacterSet CTEXT;
-#endif
+ static const CharacterSet CTEXT;
// XXX: maybe field-vchar = VCHAR / obs-text
// any VCHAR except for SPECIAL
static const CharacterSet TCHAR;
// special VCHARs
static const CharacterSet SPECIAL;
// qdtext
-#if __cplusplus == 201103L
- // ready but disabled as needs C++11 constructor
- //static const CharacterSet QDTEXT;
-#endif
+ static const CharacterSet QDTEXT;
// obs-text
static const CharacterSet OBSTEXT;
// HTTP character sets, RFC 7232
// etagc
-#if __cplusplus == 201103L
- // ready but disabled as needs C++11 constructor
- //static const CharacterSet ETAGC;
-#endif
+ static const CharacterSet ETAGC;
// HTTP character sets, RFC 7235
// token68 (internal charaters only, excludes '=' terminator)
static const CharacterSet TOKEN68C;
private:
/** index of characters in this set
*
* \note guaranteed to be always 256 slots big, as forced in the
* constructor. This assumption is relied upon in operator[], add,
* operator+=
*/
Storage chars_;
};
+CharacterSet
+operator+ (CharacterSet lhs, const CharacterSet &rhs);
+
+CharacterSet
+operator- (CharacterSet lhs, const CharacterSet &rhs);
+
#endif /* _SQUID_SRC_PARSER_CHARACTERSET_H */
=== modified file 'src/tests/testCharacterSet.cc'
--- src/tests/testCharacterSet.cc 2015-08-03 02:08:22 +0000
+++ src/tests/testCharacterSet.cc 2015-12-27 09:28:07 +0000
@@ -1,90 +1,129 @@
/*
* 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 "squid.h"
#include "base/CharacterSet.h"
#include "testCharacterSet.h"
#include "unitTestMain.h"
#include <string>
+static
+std::ostream& operator<< (std::ostream &s, const CharacterSet &c)
+{
+ s << "CharacterSet(" << c.name << ')';
+ return s;
+}
+
CPPUNIT_TEST_SUITE_REGISTRATION( testCharacterSet );
void
testCharacterSet::CharacterSetConstruction()
{
{
CharacterSet t(NULL,"");
CPPUNIT_ASSERT_EQUAL(std::string("anonymous"),std::string(t.name));
}
{
CharacterSet t("test","");
CPPUNIT_ASSERT_EQUAL(std::string("test"),std::string(t.name));
}
{
CharacterSet t("test","");
- for (int j = 0; j < 255; ++j)
+ for (int j = 0; j < 256; ++j)
CPPUNIT_ASSERT_EQUAL(false,t[j]);
}
{
CharacterSet t("test","0");
CPPUNIT_ASSERT_EQUAL(true,t['0']);
- for (int j = 0; j < 255; ++j)
- if (j != '0')
+ for (int j = 0; j < 256; ++j) {
+ if (j != '0') {
CPPUNIT_ASSERT_EQUAL(false,t[j]);
+ } else {
+ CPPUNIT_ASSERT_EQUAL(true,t[j]);
+ }
+ }
}
}
void
testCharacterSet::CharacterSetAdd()
{
CharacterSet t("test","0");
t.add(0);
CPPUNIT_ASSERT_EQUAL(true,t['\0']);
CPPUNIT_ASSERT_EQUAL(true,t['0']);
}
void
testCharacterSet::CharacterSetAddRange()
{
CharacterSet t("test","");
t.addRange('0','9');
CPPUNIT_ASSERT_EQUAL(true,t['0']);
CPPUNIT_ASSERT_EQUAL(true,t['5']);
CPPUNIT_ASSERT_EQUAL(true,t['9']);
CPPUNIT_ASSERT_EQUAL(false,t['a']);
}
void
testCharacterSet::CharacterSetConstants()
{
CPPUNIT_ASSERT_EQUAL(true,CharacterSet::ALPHA['a']);
CPPUNIT_ASSERT_EQUAL(true,CharacterSet::ALPHA['z']);
CPPUNIT_ASSERT_EQUAL(true,CharacterSet::ALPHA['A']);
CPPUNIT_ASSERT_EQUAL(true,CharacterSet::ALPHA['Z']);
CPPUNIT_ASSERT_EQUAL(false,CharacterSet::ALPHA['5']);
}
void
testCharacterSet::CharacterSetUnion()
{
{
CharacterSet hex("hex","");
hex += CharacterSet::DIGIT;
hex += CharacterSet(NULL,"aAbBcCdDeEfF");
- for (int j = 0; j < 255; ++j)
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::HEXDIG, hex);
+ for (int j = 0; j < 256; ++j)
CPPUNIT_ASSERT_EQUAL(CharacterSet::HEXDIG[j],hex[j]);
}
{
CharacterSet hex(NULL,"");
hex = CharacterSet::DIGIT + CharacterSet(NULL,"aAbBcCdDeEfF");
- for (int j = 0; j < 255; ++j)
+ for (int j = 0; j < 256; ++j)
CPPUNIT_ASSERT_EQUAL(CharacterSet::HEXDIG[j],hex[j]);
}
}
+void
+testCharacterSet::CharacterSetEqualityOp()
+{
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::ALPHA, CharacterSet::ALPHA);
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::BIT, CharacterSet(NULL,"01"));
+ CPPUNIT_ASSERT_EQUAL(CharacterSet(NULL,"01"), CharacterSet(NULL,"01"));
+ CPPUNIT_ASSERT_EQUAL(CharacterSet(NULL,"01"), CharacterSet("","01"));
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::BIT, CharacterSet("bit",'0','1'));
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::BIT, CharacterSet("bit",{{'0','1'}}));
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::BIT, CharacterSet("bit",{{'0','0'},{'1','1'}}));
+}
+
+void
+testCharacterSet::CharacterSetSubtract()
+{
+ CharacterSet sample(NULL, "0123456789aAbBcCdDeEfFz");
+
+ sample -= CharacterSet(NULL, "z"); //character in set
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::HEXDIG, sample);
+
+ sample -= CharacterSet(NULL, "z"); // character not in set
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::HEXDIG, sample);
+
+ sample += CharacterSet(nullptr, "z");
+ // one in set, one not; test operator-
+ CPPUNIT_ASSERT_EQUAL(CharacterSet::HEXDIG, sample - CharacterSet(NULL, "qz"));
+}
=== modified file 'src/tests/testCharacterSet.h'
--- src/tests/testCharacterSet.h 2015-08-03 02:08:22 +0000
+++ src/tests/testCharacterSet.h 2015-12-26 15:40:43 +0000
@@ -1,33 +1,37 @@
/*
* 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.
*/
#ifndef SQUID_BASE_TESTCHARACTERSET_H
#define SQUID_BASE_TESTCHARACTERSET_H
#include <cppunit/extensions/HelperMacros.h>
class testCharacterSet : public CPPUNIT_NS::TestFixture
{
CPPUNIT_TEST_SUITE( testCharacterSet );
CPPUNIT_TEST( CharacterSetConstruction );
CPPUNIT_TEST( CharacterSetAdd );
CPPUNIT_TEST( CharacterSetAddRange );
+ CPPUNIT_TEST( CharacterSetEqualityOp );
CPPUNIT_TEST( CharacterSetConstants );
CPPUNIT_TEST( CharacterSetUnion );
+ CPPUNIT_TEST( CharacterSetSubtract );
CPPUNIT_TEST_SUITE_END();
protected:
void CharacterSetConstruction();
void CharacterSetAdd();
void CharacterSetAddRange();
void CharacterSetConstants();
void CharacterSetUnion();
+ void CharacterSetEqualityOp();
+ void CharacterSetSubtract();
};
#endif /* SQUID_BASE_TESTCHARACTERSET_H */
_______________________________________________
squid-dev mailing list
[email protected]
http://lists.squid-cache.org/listinfo/squid-dev
