Boost logo

Boost :

Subject: Re: [boost] RFC: interest in Unicode codecs?
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-07-21 07:28:59

Eric Niebler wrote:
> Phil Endecott wrote:
>> Rogier van Dalen wrote:
>>> On Sat, Jul 18, 2009 at 15:20, Phil Endecott wrote:
>>>> The idea of an "iterator that knows where its end is" is something that
>>>> comes up fairly often; do the Range experts have any comments about it?
>>>> I think that in this case an iterator that can be incremented and
>>>> dereferenced in some limited way beyond its end would be sufficient.
>>>> ?For
>>>> example, a std::string normally has a 0 byte beyond its end so that
>>>> c_str()
>>>> can work, so it is safe (for some value of safe!) to keep advancing a
>>>> std::string::iterator until a 0 is seen, without looking for end().
>>>> ?A UTF-8
>>>> decoding algorithm that processes multi-byte characters by continuing
>>>> until
>>>> the top bit is not set would safely terminate in this case.
>>> (I don't think I'm a Range expert.) I think there are problems with
>>> this example. Adding '\0' at the end is not mandated by the standard,
>>> right?
>> My recollection is that the standard makes it hard to implement a
>> std::string that does not have a 0 after the last element, or that has
>> non-contiguous storage.
> I believe that as of C++03, std::string is required to have contiguous
> storage. The null-termination is another thing. The only guarantee is
> that the char* returned by c_str() is required to be null terminated. No
> such guarantee is made for the sequence traversed by std::string's
> iterators. Dereferencing the end iterator is verboten.

Here is an outline of a zero-overhead wrapper for std::string that I
hope guarantees that *end() == 0:

struct string_with_zero_beyond_end: std::string {
   typedef const char* const_iterator;
   const_iterator begin() const { return c_str(); }
   const_iterator end() const { return c_str() + length(); }

>> These are assumptions that I would probably be
>> happy to accept in my own internal-use code, but you are right to say
>> that they are probably not appropriate for library code. For library
>> code you would need to wrap the container with something that guarantees
>> this behaviour in a more solid way. Out of interest, does anyone know
>> if a std::vector that has been reserve()d guarantees anything about
>> dereferencing beyond-the-end iterators? It would be great if they were
>> allowed to be undefined yet certain not to segfault.
> Undefined behavior. Don't do it.

Something similar is possible.

>>> Also, '\0' could also occur in the middle of the sequence.
>> That doesn't cause a problem for this application.
> But not in general.

We're not concerned with "in general", we're concerned with this
particular problem of traversing bytes of UTF-8 efficiently with the
possibility of malformed (e.g. malicious) input, without having to
constantly check for end-of-input.

>>>> For iterators that don't offer this sort of behaviour you can provide a
>>>> wrapper that knows where end is and returns a sentinel 0 in that case.
>>> Wouldn't this end up requiring two if-statements? In general, a
>>> sentinel which is in the valid range of the value type would be an
>>> awkward sentinel.
>> No, the point is that it doesn't need any extra if statements at all.
>> The code is already looking for a top-bit-clear byte to indicate the end
>> of the multibyte character, and the 0 byte does that.
>>> However, I can see where you're coming from. Being able to tell from
>>> an iterator whether it's at the end of its range is often useful. Is
>>> operator*() is the right place to implement this functionality?
>>> Wouldn't a free function
>>> is_at_end(Iterator)
>>> make more sense?
>> Then you do have the extra if statement.
> If you write a generic algorithm that takes a ForwardRange or two
> ForwardIterators, you're not allowed to assume that the sequence is
> terminated with a sentry. Why? Because that's not part of the
> ForwardRange/ForwardIterator concept.
> You would be allowed to define a refinement, say
> ContiguousNullTerminatedIterator concept such that &*it is required to
> point to a contiguous block of memory that is terminated with a sentry
> at the position specified by the end iterator. You could also define a
> trait to detect conformance to the concept. Then you could use this
> trait to dispatch to an algorithm optimized for that trait.

I had something to detect contiguous storage to do the trick of casting
to an int and checking 4 or 8 top bits simultaneously.

> This seems like a lot of work for little gain to me, though. I'd like to
> see performance numbers to justify a design like that.

Cory Nelson reported that Windows 7 can decode UTF-8 3 times faster
than his code. I don't want Boost to end up with UTF-8 features that
are all lovely and generic and full of concepts but that run 3 times
slower on common types (strings, vector<char>, points) than they could
if they were less generic.


Boost list run by bdawes at, gregod at, cpdaniel at, john at