Re: [lucy-dev] Initial sketch of string iterators

[Nick Wellnhofer <we...@aevum.de>]

On Apr 13, 2013, at 04:01 , Marvin Humphrey <ma...@rectangular.com> wrote:

> *   The next patch, "Convert CB_Trim_{Top|Tail} to use iterators", looks
>    perfect as well.  No need to implement in concrete subclasses, I see. :)

Yes, that's the idea. If the switch to iterators is complete, adding a new string encoding should be really easy:

    * Implement the iterator class for the encoding.
    * Derive a new string class from CharBuf which only has to implement
      the iterator factory methods and Cat_Char.

> *   Should CharBufIterator#Next return 0 when it reaches the end of a string
>    instead of throwing an exception?  That would make it possible to iterate
>    through text values which are not expected to contain NUL without having
>    to call Has_Next() before each call to Next().

This seems like a worthwhile optimization. Here's how both versions would look like:

    CharBufIterator *iter = CB_Top(string);
    while (CBIter_Has_Next(iter)) {
        uint32_t code_point = CBIter_Next(iter);
        ...
    }

    CharBufIterator *iter = CB_Top(string);
    uint32_t code_point;
    while (0 != (code_point = CBIter_Next(iter))) {
        ...
    }

I find the Has_Next() version more readable but the second variant isn't too bad. The only thing I don't like is the choice of 0 as sentinel value. I'd prefer -1 or any positive value beyond the Unicode planes.

After reaching the end of the string, I can see two options which both have their pros and cons:

    * Change to a new iterator state ("beyond string boundary") and throw
      an exception on every subsequent access (like in your example below).
    * Keep returning the sentinel value on calls to Next() but allow to
      move backward via Prev(). This can result in an infinite loop in
      faulty code.

> *   I can imagine some possibilities for optimizing the internals, but those
>    are implementation details (which I imagine you left out on purpose).

Yes, the Prev() and Next() methods should decode characters directly without calling StrHelp_decode_utf8_char.

> It seems to me that the factory methods Top() and Tail() should be public,
> while ZTop() and ZTail() should have parcel exposure.  More generally, I've
> moved towards the position that while we want to have the core allocate
> objects on the stack for certain internal tasks, it would be unwise at this
> point for Clownfish to support stack object allocation as a public API.
> I'm actually hoping that as we overhaul Clownfish string handling that
> ZombieCharBuf can go away.  But what you've presented makes sense and fits
> perfectly within the current context.

I think the string iterators are good candidates for "zombie" objects. They're small and typically only used within a single function. But +1 for not exposing ZombieIterators publicly.

> How about something like this, which I think should have the same cost?
> 
> -    if (self->byte_offset >= char_buf->size) {
> -        THROW(ERR, "Iteration past end of string");
> -    }
> +    if (self->byte_offset > char_buf->size) {
> +        THROW(ERR, "Iteration past end of string");
> +    }
> +    else if (self->byte_offset == char_buf->size) {

Something like ++self->byte_offset would be needed here.

> +        return 0;
> +    }

See discussion above.

>> +ZombieUTF8Iterator*
>> +ZUTF8Iter_new(void *allocation, CharBuf *char_buf, size_t byte_offset) {
>> +    ZombieUTF8Iterator *self = (ZombieUTF8Iterator*)allocation;
>> +    self->ref.count   = 1;
> 
> Might want to go through VTable_Init_Obj(), no?  ;)

Sure ;)

Nick

Re: [lucy-dev] Initial sketch of string iterators

[Nick Wellnhofer <we...@aevum.de>]

On 14/04/2013 04:25, Marvin Humphrey wrote:
> Good point.  How about a symbolic value, `DONE`, or in full,
> `CFISH_CBITER_DONE` and eventually also `CFISH_STRITER_DONE`?

+1

>> After reaching the end of the string, I can see two options which both have
>> their pros and cons:
>>
>>      * Change to a new iterator state ("beyond string boundary") and throw
>>        an exception on every subsequent access (like in your example below).
>>      * Keep returning the sentinel value on calls to Next() but allow to
>>        move backward via Prev(). This can result in an infinite loop in
>>        faulty code.
>
> I don't have a strong opinion.

I lean towards the second option.

> What do you think of putting a flag into CharBuf/String which indicates how it
> should deallocated?
>
>      void
>      CB_destroy(CharBuf *self) {
>          if (!(self->flags & CB_HEAP_ALLOCATED)) {
>              THROW(ERR, "Can't Destroy non-heap-allocated CharBuf");
>          }
>          ...
>      }
>
> That would allow us to get rid of the Zombie classes.  Rationale: using
> subclassing to control memory allocation is odd, plus the name "Zombie" isn't
> the greatest.

I think it's a good idea but I wouldn't want to waste a whole word in 
the CharBuf struct just for a single flag.

Nick

Re: [lucy-dev] Initial sketch of string iterators

[Marvin Humphrey <ma...@rectangular.com>]

On Sat, Apr 13, 2013 at 8:15 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> The only thing I don't like is the choice of 0 as sentinel value. I'd prefer
> -1 or any positive value beyond the Unicode planes.

Good point.  How about a symbolic value, `DONE`, or in full,
`CFISH_CBITER_DONE` and eventually also `CFISH_STRITER_DONE`?

    while (CFISH_STRITER_DONE != (code_point = Cfish_StrIter_Next(iter))) {
        ...
    }

FWIW, I'm not a fan of sentinels like UINT32_MAX which don't make sense in
high-level languages with a single integer type.  I don't expect that we'll do
a lot of string iteration in high-level host languages, but it's nice to set a
precedent going forward that it's idiomatic for Clownfish iterators to have
symbolic sentinels if any.  Sentinel return values in C are a common source of
bugs -- e.g. testing for -1 when the function may indicate failure by
returning any negative number.

> After reaching the end of the string, I can see two options which both have
> their pros and cons:
>
>     * Change to a new iterator state ("beyond string boundary") and throw
>       an exception on every subsequent access (like in your example below).
>     * Keep returning the sentinel value on calls to Next() but allow to
>       move backward via Prev(). This can result in an infinite loop in
>       faulty code.

I don't have a strong opinion.

> I think the string iterators are good candidates for "zombie" objects.
> They're small and typically only used within a single function. But +1 for
> not exposing ZombieIterators publicly.

OK, we agree on the important stuff. :)

What do you think of putting a flag into CharBuf/String which indicates how it
should deallocated?

    void
    CB_destroy(CharBuf *self) {
        if (!(self->flags & CB_HEAP_ALLOCATED)) {
            THROW(ERR, "Can't Destroy non-heap-allocated CharBuf");
        }
        ...
    }

That would allow us to get rid of the Zombie classes.  Rationale: using
subclassing to control memory allocation is odd, plus the name "Zombie" isn't
the greatest.

On the other hand, if the zombies can't escape from the core, maybe it doesn't
matter so much.

Marvin Humphrey