source: libcfa/src/collections/string_res.cfa@ 2f16569

//
// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// string_res -- variable-length, mutable run of text, with resource semantics
//
// Author           : Michael L. Brooks
// Created On       : Fri Sep 03 11:00:00 2021
// Last Modified By : Peter A. Buhr
// Last Modified On : Thu May  7 13:14:45 2026
// Update Count     : 135
//

#include "string_res.hfa"
#include "string_sharectx.hfa"
#include "stdlib.hfa"
#include <ctype.h>

// Workaround for observed performance penalty from calling CFA's alloc.
// Workaround is:  EndVbyte = TEMP_ALLOC(char, CurrSize)
// Should be:      EndVbyte = alloc(CurrSize)
#define TEMP_ALLOC(T, n) (( T * ) malloc( n * sizeof( T ) ))

#include <assert.h>
#include <complex.h>                                               // creal, cimag

//######################### VbyteHeap "header" #########################

#ifdef VbyteDebug
HandleNode *HeaderPtr;
#endif // VbyteDebug

struct VbyteHeap {
        int NoOfCompactions;                                                            // number of compactions of the byte area
        int NoOfExtensions;                                                                     // number of extensions in the size of the byte area
        int NoOfReductions;                                                                     // number of reductions in the size of the byte area
        
        int InitSize;                                                                           // initial number of bytes in the byte-string area
        int CurrSize;                                                                           // current number of bytes in the byte-string area
        char *StartVbyte;                                                                       // pointer to the `st byte of the start of the byte-string area
        char *EndVbyte;                                                                         // pointer to the next byte after the end of the currently used portion of byte-string area
        void *ExtVbyte;                                                                         // pointer to the next byte after the end of the byte-string area

        HandleNode Header;                                                                      // header node for handle list
}; // VbyteHeap


static void compaction( VbyteHeap & );                                  // compaction of the byte area
static void garbage( VbyteHeap &, int );                                // garbage collect the byte area
static void extend( VbyteHeap &, int );                                 // extend the size of the byte area
static void reduce( VbyteHeap &, int );                                 // reduce the size of the byte area

static void ?{}( VbyteHeap &, size_t = 1000 );
static void ^?{}( VbyteHeap & );

static int ByteCmp( char *, int, int, char *, int, int ); // compare 2 blocks of bytes
static char *VbyteAlloc( VbyteHeap &, int );                    // allocate a block bytes in the heap
static char *VbyteTryAdjustLast( VbyteHeap &, int );

static void AddThisAfter( HandleNode &, HandleNode & );
static void DeleteNode( HandleNode & );
static void MoveThisAfter( HandleNode &, const HandleNode & ); // move current handle after parameter handle


// Allocate the storage for the variable sized area and intialize the heap variables.

static void ?{}( VbyteHeap & s, size_t Size ) with(s) {
#ifdef VbyteDebug
        serr | "enter:VbyteHeap::VbyteHeap, s:" | &s | " Size:" | Size;
#endif // VbyteDebug
        NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
        InitSize = CurrSize = Size;
        StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
        ExtVbyte = (void *)( StartVbyte + CurrSize );
        Header.flink = Header.blink = &Header;
        Header.ulink = &s;
#ifdef VbyteDebug
        HeaderPtr = &Header;
        serr | "exit:VbyteHeap::VbyteHeap, s:" | &s;
#endif // VbyteDebug
} // VbyteHeap


// Release the dynamically allocated storage for the byte area.

static void ^?{}( VbyteHeap & s ) with(s) {
        free( StartVbyte );
} // ~VbyteHeap


//######################### HandleNode #########################


// Create a handle node. The handle is not linked into the handle list.  This is the responsibilitiy of the handle
// creator.

static void ?{}( HandleNode & s ) with(s) {
#ifdef VbyteDebug
        serr | "enter:HandleNode::HandleNode, s:" | &s;
#endif // VbyteDebug
        s = 0;
        lnth = 0;
#ifdef VbyteDebug
        serr | "exit:HandleNode::HandleNode, s:" | &s;
#endif // VbyteDebug
} // HandleNode

// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be
// in order by string address, but this is not a problem because a string with length zero does nothing during garbage
// collection.

static void ?{}( HandleNode & s, VbyteHeap & vh ) with(s) {
#ifdef VbyteDebug
        serr | "enter:HandleNode::HandleNode, s:" | &s;
#endif // VbyteDebug
        s = 0;
        lnth = 0;
        ulink = &vh;
        AddThisAfter( s, *vh.Header.blink );
#ifdef VbyteDebug
        serr | "exit:HandleNode::HandleNode, s:" | &s;
#endif // VbyteDebug
} // HandleNode


// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it
// is the responsibility of the creator to destroy it.

static void ^?{}( HandleNode & s ) with(s) {
#ifdef VbyteDebug
        serr | "enter:HandleNode::~HandleNode, s:" | & s;
        {
                serr | nlOff;
                serr | " lnth:" | lnth | " s:" | (void *)s | ",\"";
                for ( i; lnth ) {
                        serr | s[i];
                } // for
                serr | "\" flink:" | flink | " blink:" | blink | nl;
                serr | nlOn;
        }
#endif // VbyteDebug
        DeleteNode( s );
} // ~HandleNode


//######################### String Sharing Context #########################

static string_sharectx * ambient_string_sharectx;               // fickle top of stack
static string_sharectx default_string_sharectx = {NEW_SHARING}; // stable bottom of stack

void ?{}( string_sharectx & s, StringSharectx_Mode mode ) with( s ) {
        (older){ ambient_string_sharectx };
        if ( mode == NEW_SHARING ) {
                (activeHeap){ new( (size_t) 1000 ) };
        } else {
                verify( mode == NO_SHARING );
                (activeHeap){ 0p };
        }
        ambient_string_sharectx = & s;
}

void ^?{}( string_sharectx & s ) with( s ) {
        if ( activeHeap ) delete( activeHeap );

        // unlink s from older-list starting from ambient_string_sharectx
        // usually, s==ambient_string_sharectx and the loop runs zero times
        string_sharectx *& c = ambient_string_sharectx;
        while ( c != &s ) &c = &c->older;                                       // find s
        c = s.older;                                                                            // unlink
}

//######################### String Resource #########################


VbyteHeap * DEBUG_string_heap() {
        assert( ambient_string_sharectx->activeHeap && "No sharing context is active" );
        return ambient_string_sharectx->activeHeap;
}

size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) {
        return ((char *)heap->ExtVbyte) - heap->EndVbyte;
}

size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) {
        return heap->CurrSize;
}

const char * DEBUG_string_heap_start( VbyteHeap * heap ) {
        return heap->StartVbyte;
}

// Output operator
forall( ostype & | basic_ostream( ostype ) )
ostype & ?|?( ostype & out, const string_res & s ) {
        // CFA string is NOT null terminated, so print exactly lnth characters in a minimum width of 0.
        return out | wd( 0, s.Handle.lnth, s.Handle.s ) | nonl;
}

forall( ostype & | basic_ostream( ostype ) )
void ?|?( ostype & out, const string_res & s ) {
        (ostype &)(out | s);
        basic_ostream_table.ends( out );
}

// Input operator
forall( istype & | basic_istream( istype ) )
istype & ?|?( istype & in, string_res & s ) {
        // Reading into a temp before assigning to s is near zero overhead in typical cases because of sharing.
        // If s is a substring of something larger, simple assignment takes care of that case correctly.
        // But directly reading a variable amount of text into the middle of a larger context is not practical.
        string_res temp;

        // Read in chunks.  Often, one chunk is enough.  Keep the string that accumulates chunks last in the heap,
        // so available room is rest of heap.  When a chunk fills the heap, force growth then take the next chunk.
        for (bool cont = true; cont; ) {
                cont = false;

                // Append dummy content to temp, forcing expansion when applicable (occurs always on subsequent loops)
                // length 2 ensures room for at least one real char, plus scanf/pipe-cstr's null terminator
                temp += "--";
                assert( temp.Handle.ulink->EndVbyte == temp.Handle.s + temp.Handle.lnth );      // last in heap

                // reset, to overwrite the appended "--"
                temp.Handle.lnth -= 2;
                temp.Handle.ulink->EndVbyte -= 2;

                // rest of heap is available to read into
                int lenReadable = (char *)temp.Handle.ulink->ExtVbyte - temp.Handle.ulink->EndVbyte;
                assert (lenReadable >= 2);

                // get bytes
                try {
                        *(temp.Handle.ulink->EndVbyte) = '\0';   // pre-assign empty cstring
                        in | wdi( lenReadable, temp.Handle.ulink->EndVbyte );
                } catch (cstring_length *) {
                        cont = true;
                }
                int lenWasRead = strlen(temp.Handle.ulink->EndVbyte);

                // update metadata
                temp.Handle.lnth += lenWasRead;
                temp.Handle.ulink->EndVbyte += lenWasRead;
        }

        if ( temp.Handle.lnth > 0 ) s = temp;
        return in;
}

forall( istype & | basic_istream( istype ) )
istype & ?|?( istype & is, _Istream_Rquote f ) with( basic_istream_table, f.rstr ) {
        if ( eof( is ) ) throwResume ExceptionInst( end_of_file );
        int args;
  fini: {
                char rfmt[5] = { ' ', delimiters[0], '%', 'n', '\0' };
                int l = -1;                                                                             // may not be set in fmt
                args = fmt( is, rfmt, &l );                                             // remove leading whitespace and quote
          if ( eof( is ) || l == -1 ) break fini;

                // Change the remainder of the read into a getline by reseting the closing delimiter.
                if ( delimiters[1] != '\0' ) {
                        delimiters[0] = delimiters[1];
                        delimiters[1] = '\0';
                } // if
                flags.delimiter = true;
                return is | *(_Istream_Rstr *)&f;
        } // fini
        // read failed => no pattern match => set string to null
        if ( ! flags.ignore && s != 0p && args == 0 ) s[0] = '\0';
        if ( args == 1 && eof( is ) ) {                                         // data but scan ended at EOF
                clearerr( is );                                                                 // => reset EOF => detect again on next read
        } // if
        return is;
}

forall( istype & | basic_istream( istype ) )
istype & ?|?( istype & is, _Istream_Rstr f ) {
        // .---------------,
        // | | | | |...|0|0| null terminator and guard if missing
        // `---------------'
        enum { gwd = 128 + 1, wd = gwd - 1 };                           // guard and unguard width
        char cstr[gwd];                                                                         // read in chunks
        bool cont = false;

        _Istream_Cwidth cf = { cstr, (_Istream_str_base)f };
        if ( ! cf.flags.rwd ) cf.wd = wd;

        cstr[wd] = '\0';                                                                        // guard null terminate string
        try {
                cstr[0] = '\0';                                                                 // pre-assign as empty cstring
                is | cf;
        } catch( cstring_length * ) {
                cont = true;
        } finally {
                if ( ! cf.flags.ignore                                                  // ok to initialize string
//                       &&     cstr[0] != '\0'                                                 // something was read
                        ) {
                        *(f.s) = cstr;
                }
        } // try
        for ( ; cont; )  {                                                                      // overflow read ?
                cont = false;
                try {
                        cstr[0] = '\0';                                                         // pre-assign as empty cstring
                        is | cf;
                } catch( cstring_length * ) {
                        cont = true;                                                            // continue not allowed
                } finally {
                        if ( ! cf.flags.ignore && cstr[0] != '\0' ) { // something was read
                                *(f.s) += cstr;                                                 // build string chunk at a time
                        }
                } // try
        } // for
        return is;
} // ?|?

// Empty constructor
void ?{}(string_res & s) with(s) {
        if( ambient_string_sharectx->activeHeap ) {
                (Handle){ * ambient_string_sharectx->activeHeap };
                (shareSet_owns_ulink){ false };
                verify( Handle.s == 0p && Handle.lnth == 0 );
        } else {
                (Handle){ * new( (size_t) 10 ) };  // TODO: can I lazily avoid allocating for empty string
                (shareSet_owns_ulink){ true };
                Handle.s = Handle.ulink->StartVbyte;
                verify( Handle.lnth == 0 );
        }
        s.shareSet_prev = &s;
        s.shareSet_next = &s;
                }

static void eagerCopyCtorHelper(string_res & s, const char * rhs, size_t rhslnth) with(s) {
        if( ambient_string_sharectx->activeHeap ) {
                (Handle){ * ambient_string_sharectx->activeHeap };
                (shareSet_owns_ulink){ false };
        } else {
                (Handle){ * new( rhslnth ) };
                (shareSet_owns_ulink){ true };
        }
        Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
        Handle.lnth = rhslnth;
        memmove( Handle.s, rhs, rhslnth );
        s.shareSet_prev = &s;
        s.shareSet_next = &s;
}

// Constructor from a raw buffer and size
void ?{}(string_res & s, const char * rhs, size_t rhslnth) with(s) {
        eagerCopyCtorHelper(s, rhs, rhslnth);
}

void ?{}( string_res & s, ssize_t rhs ) {
        char buf[64];
        int l;
        snprintf( buf, sizeof(buf)-1, "%zd%n", rhs, &l );
        ( s ){ buf, l };
}
void ?{}( string_res & s, size_t rhs ) {
        char buf[64];
        int l;
        snprintf( buf, sizeof(buf)-1, "%zu%n", rhs, &l );
        ( s ){ buf, l };
}
void ?{}( string_res & s, double rhs ) {
        char buf[64];
        int l;
        snprintf( buf, sizeof(buf)-1, "%g%n", rhs, &l );
        ( s ){ buf, l };
}
void ?{}( string_res & s, long double rhs ) {
        char buf[64];
        int l;
        snprintf( buf, sizeof(buf)-1, "%Lg%n", rhs, &l );
        ( s ){ buf, l };
}
void ?{}( string_res & s, double _Complex rhs ) {
        char buf[64];
        int l;
        snprintf( buf, sizeof(buf)-1, "%g+%gi%n", creal( rhs ), cimag( rhs ), &l );
        ( s ){ buf, l };
}
void ?{}( string_res & s, long double _Complex rhs ) {
        char buf[64];
        int l;
        snprintf( buf, sizeof(buf)-1, "%Lg+%Lgi%n", creall( rhs ), cimagl( rhs ), &l );
        ( s ){ buf, l };
}

// private ctor (not in header): use specified heap (ignore ambient) and copy chars in
void ?{}( string_res & s, VbyteHeap & heap, const char * rhs, size_t rhslnth ) with(s) {
        (Handle){ heap };
        Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
        Handle.lnth = rhslnth;
        (s.shareSet_owns_ulink){ false };
        memmove( Handle.s, rhs, rhslnth );
        s.shareSet_prev = &s;
        s.shareSet_next = &s;
}


// General copy constructor
void ?{}(string_res & s, const string_res & s2, StrResInitMode mode, size_t start, size_t len ) {
        size_t end = start + len;
        verify( start <= end && end <= s2.Handle.lnth );

        if (s2.Handle.ulink != ambient_string_sharectx->activeHeap && mode == COPY_VALUE) {
                // crossing heaps (including private): copy eagerly
                eagerCopyCtorHelper(s, s2.Handle.s + start, end - start);
                verify(s.shareSet_prev == &s);
                verify(s.shareSet_next == &s);
        } else {
                (s.Handle){};
                s.Handle.s = s2.Handle.s + start;
                s.Handle.lnth = end - start;
                s.Handle.ulink = s2.Handle.ulink;

                AddThisAfter(s.Handle, s2.Handle );                     // insert this handle after rhs handle
                // ^ bug?  skip others at early point in string

                if (mode == COPY_VALUE) {
                        verify(s2.Handle.ulink == ambient_string_sharectx->activeHeap);
                        // requested logical copy in same heap: defer copy until write

                        (s.shareSet_owns_ulink){ false };

                        // make s alone in its shareSet
                        s.shareSet_prev = &s;
                        s.shareSet_next = &s;
                } else {
                        verify( mode == SHARE_EDITS );
                        // sharing edits with source forces same heap as source (ignore context)

                        (s.shareSet_owns_ulink){ s2.shareSet_owns_ulink };

                        // s2 is logically const but not implementation const
                        string_res & s2mod = (string_res &) s2;

                        // insert s after s2 on shareSet
                        s.shareSet_next = s2mod.shareSet_next;
                        s.shareSet_prev = &s2mod;
                        s.shareSet_next->shareSet_prev = &s;
                        s.shareSet_prev->shareSet_next = &s;
                }
        }
}

static void assignEditSet(string_res & s, string_res * shareSetStartPeer, string_res * shareSetEndPeer,
                                                  char * resultSesStart,
                                                  size_t resultSesLnth,
                                                  HandleNode * resultPadPosition, size_t bsize ) {

        char * beforeBegin = shareSetStartPeer->Handle.s;
        size_t beforeLen = s.Handle.s - beforeBegin;

        char * afterBegin = s.Handle.s + s.Handle.lnth;
        size_t afterLen = shareSetEndPeer->Handle.s + shareSetEndPeer->Handle.lnth - afterBegin;

        size_t oldLnth = s.Handle.lnth;

        s.Handle.s = resultSesStart + beforeLen;
        s.Handle.lnth = bsize;
        if (resultPadPosition)
                MoveThisAfter( s.Handle, *resultPadPosition );

        // adjust all substring string and handle locations, and check if any substring strings are outside the new base string
        char *limit = resultSesStart + resultSesLnth;
        for ( string_res * p = s.shareSet_next; p != &s; p = p->shareSet_next ) {
                verify (p->Handle.s >= beforeBegin);
                if ( p->Handle.s >= afterBegin ) {
                        verify ( p->Handle.s <= afterBegin + afterLen );
                        verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
                        // p starts after the edit
                        // take start and end as end-anchored
                        size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s;
                        p->Handle.s = limit - startOffsetFromEnd;
                        // p->Handle.lnth unaffected
                } else if ( p->Handle.s <= beforeBegin + beforeLen ) {
                        // p starts before, or at the start of, the edit
                        if ( p->Handle.s + p->Handle.lnth <= beforeBegin + beforeLen ) {
                                // p ends before the edit
                                // take end as start-anchored too
                                // p->Handle.lnth unaffected
                        } else if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
                                // p ends during the edit; p does not include the last character replaced
                                // clip end of p to end at start of edit
                                p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin );
                        } else {
                                // p ends after the edit
                                verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
                                // take end as end-anchored
                                // stretch-shrink p according to the edit
                                p->Handle.lnth += s.Handle.lnth;
                                p->Handle.lnth -= oldLnth;
                        }
                        // take start as start-anchored
                        size_t startOffsetFromStart = p->Handle.s - beforeBegin;
                        p->Handle.s = resultSesStart + startOffsetFromStart;
                } else {
                        verify ( p->Handle.s < afterBegin );
                        // p starts during the edit
                        verify( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
                        if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
                                // p ends during the edit; p does not include the last character replaced
                                // set p to empty string at start of edit
                                p->Handle.s = s.Handle.s;
                                p->Handle.lnth = 0;
                        } else {
                                // p includes the end of the edit
                                // clip start of p to start at end of edit
                                int charsToClip = afterBegin - p->Handle.s;
                                p->Handle.s = s.Handle.s + s.Handle.lnth;
                                p->Handle.lnth -= charsToClip;
                        }
                }
                if (resultPadPosition)
                        MoveThisAfter( p->Handle, *resultPadPosition ); // move substring handle to maintain sorted order by string position
        }
}

// traverse the share-edit set (SES) to recover the range of a base string to which `s` belongs
static void locateInShareSet( string_res & s, string_res *& shareSetStartPeer, string_res *& shareSetEndPeer ) {
        shareSetStartPeer = & s;
        shareSetEndPeer = & s;
        for (string_res * editPeer = s.shareSet_next; editPeer != &s; editPeer = editPeer->shareSet_next) {
                if ( editPeer->Handle.s < shareSetStartPeer->Handle.s ) {
                        shareSetStartPeer = editPeer;
                }
                if ( shareSetEndPeer->Handle.s + shareSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
                        shareSetEndPeer = editPeer;
                }
        }
}

static string_res & assign_(string_res & s, const char * buffer, size_t bsize, const string_res & valSrc) {
        string_res * shareSetStartPeer;
        string_res * shareSetEndPeer;
        locateInShareSet( s, shareSetStartPeer, shareSetEndPeer );

        verify( shareSetEndPeer->Handle.s >= shareSetStartPeer->Handle.s );
        size_t origEditSetLength = shareSetEndPeer->Handle.s + shareSetEndPeer->Handle.lnth - shareSetStartPeer->Handle.s;
        verify( origEditSetLength >= s.Handle.lnth );

        if ( s.shareSet_owns_ulink ) {                           // assigning to private context
                // ok to overwrite old value within LHS
                char * prefixStartOrig = shareSetStartPeer->Handle.s;
                int prefixLen = s.Handle.s - prefixStartOrig;
                char * suffixStartOrig = s.Handle.s + s.Handle.lnth;
                int suffixLen = shareSetEndPeer->Handle.s + shareSetEndPeer->Handle.lnth - suffixStartOrig;

                int delta = bsize - s.Handle.lnth;
                if ( char * oldBytes = VbyteTryAdjustLast( *s.Handle.ulink, delta ) ) {
                        // growing: copy from old to new
                        char * dest = VbyteAlloc( *s.Handle.ulink, origEditSetLength + delta );
                        char *destCursor = dest;  memcpy(destCursor, prefixStartOrig, prefixLen);
                        destCursor += prefixLen;  memcpy(destCursor, buffer              , bsize        );
                        destCursor += bsize;      memcpy(destCursor, suffixStartOrig, suffixLen);
                        assignEditSet(s, shareSetStartPeer, shareSetEndPeer, 
                                                  dest,
                                                  origEditSetLength + delta,
                                                  0p, bsize);
                        free( oldBytes );
                } else {
                        // room is already allocated in-place: bubble suffix and overwite middle
                        memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen );
                        memcpy( s.Handle.s, buffer, bsize );

                        assignEditSet(s, shareSetStartPeer, shareSetEndPeer, 
                                                  shareSetStartPeer->Handle.s,
                                                  origEditSetLength + delta,
                                                  0p, bsize);
                }

        } else if (                                                                                // assigning to shared context
                s.Handle.lnth == origEditSetLength &&             // overwriting entire run of SES
                & valSrc &&                                                                        // sourcing from a managed string
                valSrc.Handle.ulink == s.Handle.ulink  ) {       // sourcing from same heap

                // SES's result will only use characters from the source string => reuse source
                assignEditSet(s, shareSetStartPeer, shareSetEndPeer, 
                                          valSrc.Handle.s,
                                          valSrc.Handle.lnth,
                                          &((string_res&)valSrc).Handle, bsize);
                
        } else {
                // overwriting a proper substring of some string: mash characters from old and new together (copy on write)
                // OR we are importing characters: need to copy eagerly (can't refer to source)

                // full string is from start of shareSetStartPeer thru end of shareSetEndPeer
                // `s` occurs in the middle of it, to be replaced
                // build up the new text in `pasting`

                string_res pasting = {
                        * s.Handle.ulink,                                                          // maintain same heap, regardless of context
                        shareSetStartPeer->Handle.s,                               // start of SES
                        s.Handle.s - shareSetStartPeer->Handle.s }; // length of SES, before s
                append( pasting,
                                buffer,                                                                                 // start of replacement for s
                                bsize );                                                                                   // length of replacement for s
                append( pasting,
                                s.Handle.s + s.Handle.lnth,                               // start of SES after s
                                shareSetEndPeer->Handle.s + shareSetEndPeer->Handle.lnth -
                                (s.Handle.s + s.Handle.lnth) );                   // length of SES, after s

                // The above string building can trigger compaction.
                // The reference points (that are arguments of the string building) may move during that building.
                // From s point on, they are stable.

                assignEditSet(s, shareSetStartPeer, shareSetEndPeer, 
                                          pasting.Handle.s,
                                          pasting.Handle.lnth,
                                          &pasting.Handle, bsize);
        }

        return s;
}

string_res & assign(string_res & s, const string_res & src, size_t maxlen) {
        return assign_(s, src.Handle.s, min(src.Handle.lnth, maxlen), *0p);
}

string_res & assign(string_res & s, const char * buffer, size_t bsize) {
        return assign_(s, buffer, bsize, *0p);
}

string_res & ?=?(string_res & s, char c) {
        return assign(s, &c, 1);
}

string_res & ?=?( string_res & s, ssize_t rhs ) {
        string_res rhs2 = rhs;
        s = rhs2;
        return s;
}
string_res & ?=?( string_res & s, size_t rhs ) {
        string_res rhs2 = rhs;
        s = rhs2;
        return s;
}
string_res & ?=?( string_res & s, double rhs ) {
        string_res rhs2 = rhs;
        s = rhs2;
        return s;
}
string_res & ?=?( string_res & s, long double rhs ) {
        string_res rhs2 = rhs;
        s = rhs2;
        return s;
}
string_res & ?=?( string_res & s, double _Complex rhs ) {
        string_res rhs2 = rhs;
        s = rhs2;
        return s;
}
string_res & ?=?( string_res & s, long double _Complex rhs ) {
        string_res rhs2 = rhs;
        s = rhs2;
        return s;
}

// Copy assignment operator
string_res & ?=?(string_res & s, const string_res & rhs) with( s ) {
        return assign_(s, rhs.Handle.s, rhs.Handle.lnth, rhs);
}

string_res & ?=?(string_res & s, string_res & rhs) with( s ) {
        const string_res & rhs2 = rhs;
        return s = rhs2;
}


// Destructor
void ^?{}(string_res & s) with(s) {
        // much delegated to implied ^VbyteSM

        // sever s from its share-edit peers, if any (four no-ops when already solo)
        s.shareSet_prev->shareSet_next = s.shareSet_next;
        s.shareSet_next->shareSet_prev = s.shareSet_prev;
        // s.shareSet_next = &s;
        // s.shareSet_prev = &s;

        if (shareSet_owns_ulink && s.shareSet_next == &s) { // last one out
                delete( s.Handle.ulink );
        }
}


// Returns the character at the given index
// With unicode support, this may be different from just the byte at the given
// offset from the start of the string.
char ?[?](const string_res & s, size_t index) with(s) {
        //TODO: Check if index is valid (no exceptions yet)
        return Handle.s[index];
}

void assignAt(const string_res & s, size_t index, char val) {
        // caution: not tested (not reachable by string-api-coverage interface)
        // equivalent form at string level is `s[index] = val`,
        // which uses the overload that returns a length-1 string
        string_res editZone = { s, SHARE_EDITS, index, 1 };
        assign(editZone, &val, 1);
}


///////////////////////////////////////////////////////////////////
// Concatenation

void append(string_res & str1, const char * buffer, size_t bsize) {
        size_t clnth = str1.Handle.lnth + bsize;
        if ( str1.Handle.s + str1.Handle.lnth == buffer ) { // already juxtapose ?
                // no-op
        } else {                                                                                        // must copy some text
                if ( str1.Handle.s + str1.Handle.lnth == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ?
                        VbyteAlloc( *str1.Handle.ulink, bsize );        // create room for 2nd part at the end of string area
                } else {                                                                                // copy the two parts
                        char * str1newBuf = VbyteAlloc( *str1.Handle.ulink, clnth );
                        char * str1oldBuf = str1.Handle.s;                      // must read after VbyteAlloc call in case it gs's
                        str1.Handle.s = str1newBuf;
                        memcpy( str1.Handle.s, str1oldBuf,  str1.Handle.lnth );
                } // if
                memcpy( str1.Handle.s + str1.Handle.lnth, buffer, bsize );
        } // if
        str1.Handle.lnth = clnth;
}

void append( string_res & s, const string_res & s2, size_t maxlen ) {
        append( s, s2.Handle.s, min( s2.Handle.lnth, maxlen ) );
}

///////////////////////////////////////////////////////////////////
// Repetition

void ?*=?(string_res & s, size_t factor) {
        string_res s2 = { s, COPY_VALUE };
        s = "";
        for (factor) s += s2;
}

//////////////////////////////////////////////////////////
// Comparisons

int strcmp$( const char * s1, size_t l1, const char * s2, size_t l2 ) {
        int ret = memcmp( s1, s2, min( l1, l2 ) );
        if ( ret != 0 ) return ret;
        return l1 - l2;
}

//////////////////////////////////////////////////////////
// Search

// int find$( const string_res & s, ssize_t start, ssize_t len, const string_res & k, ssize_t kstart, ssize_t klen ) {
//     if ( start < 0 ) start = s.Handle.lnth + start;          // adjust negative starting locations
//     if ( kstart < 0 ) kstart = k.Handle.lnth + kstart;

//      if ( start + len > s.Handle.lnth ) return start + 1;  // cannot be there
//      if ( kstart + len > k.Handle.lnth ) return start + 1;
//      if ( klen > len ) return start + 1;

//      int i, r;

//      for ( i = max( start, 1 ); ; i += 1 ) {
//              if ( i > s.Handle.lnth - k.Handle.lnth + 1 ) {
//                      r = s.Handle.lnth + 1;
//                      break;
//          } // exit
//              if ( HeapArea->ByteCmp( s.Handle.s, i, k.Handle.lnth, k.Handle.s, 1, k.Handle.lnth ) == 0 ) {
//                      r = i;
//                      break;
//          } // exit
//      } // for
//      return r;
// }

int find( const string_res & s, char search ) {
        return findFrom(s, 0, search);
}

int findFrom( const string_res & s, size_t fromPos, char search ) {
        // FIXME: This paricular overload (find of single char) is optimized to use memchr.
        // The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match.
        char * searchFrom = s.Handle.s + fromPos;
        size_t searchLnth = s.Handle.lnth - fromPos;
        int searchVal = search;
        char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth);
        if (foundAt == 0p) return s.Handle.lnth;
        else return foundAt - s.Handle.s;
}

int find(const string_res & s, const string_res & search) {
        return findFrom(s, 0, search);
}

int findFrom(const string_res & s, size_t fromPos, const string_res & search) {
        return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth);
}

int find(const string_res & s, const char * search) {
        return findFrom(s, 0, search);
}
int findFrom(const string_res & s, size_t fromPos, const char * search) {
        return findFrom(s, fromPos, search, strlen(search));
}

int find(const string_res & s, const char * search, size_t searchsize) {
        return findFrom(s, 0, search, searchsize);
}

int findFrom(const string_res & s, size_t fromPos, const char * search, size_t searchsize) {
        /* Remaining implementations essentially ported from Sunjay's work */

        // FIXME: This is a naive algorithm. We probably want to switch to someting
        // like Boyer-Moore in the future.
        // https://en.wikipedia.org/wiki/String_searching_algorithm

        // Always find the empty string
        if (searchsize == 0) {
                return 0;
        }

        for ( i; fromPos ~ s.Handle.lnth ) {
                size_t remaining = s.Handle.lnth - i;
                // Never going to find the search string if the remaining string is
                // smaller than search
                if (remaining < searchsize) {
                        break;
                }

                bool matched = true;
                for ( j; searchsize ) {
                        if (search[j] != s.Handle.s[i + j]) {
                                matched = false;
                                break;
                        }
                }
                if (matched) {
                        return i;
                }
        }
        return s.Handle.lnth;
}

bool includes(const string_res & s, const string_res & search) {
        return includes(s, search.Handle.s, search.Handle.lnth);
}

bool includes(const string_res & s, const char * search) {
        return includes(s, search, strlen(search));
}

bool includes(const string_res & s, const char * search, size_t searchsize) {
        return find(s, search, searchsize) < s.Handle.lnth;
}

bool startsWith(const string_res & s, const string_res & prefix) {
        return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
}

bool startsWith(const string_res & s, const char * prefix) {
        return startsWith(s, prefix, strlen(prefix));
}

bool startsWith(const string_res & s, const char * prefix, size_t prefixsize) {
        if (s.Handle.lnth < prefixsize) {
                return false;
        }
        return memcmp(s.Handle.s, prefix, prefixsize) == 0;
}

bool endsWith(const string_res & s, const string_res & suffix) {
        return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
}

bool endsWith(const string_res & s, const char * suffix) {
        return endsWith(s, suffix, strlen(suffix));
}

bool endsWith(const string_res & s, const char * suffix, size_t suffixsize) {
        if (s.Handle.lnth < suffixsize) {
                return false;
        }
        // Amount to offset the bytes pointer so that we are comparing the end of s
        // to suffix. s.bytes + offset should be the first byte to compare against suffix
        size_t offset = s.Handle.lnth - suffixsize;
        return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
}

/* Back to Mike's work */

///////////////////////////////////////////////////////////////////////////
// charclass, include, exclude

void ?{}( charclass_res & s, const string_res & chars) {
        (s){ chars.Handle.s, chars.Handle.lnth };
}

void ?{}( charclass_res & s, const char * chars ) {
        (s){ chars, strlen(chars) };
}

void ?{}( charclass_res & s, const char * chars, size_t charssize ) {
        (s.chars){ chars, charssize };
        // now sort it ?
}

void ^?{}( charclass_res & s ) {
        ^(s.chars){};
}

static bool test( const charclass_res & mask, char c ) {
        // instead, use sorted char list?
        for ( i; len(mask.chars) ) {
                if (mask.chars[i] == c) return true;
        }
        return false;
//      return contains( mask.chars, c );
}

int exclude(const string_res & s, const charclass_res & mask) {
        for ( i; len(s) ) {
                if ( test(mask, s[i]) ) return i;
        }
        return len(s);
}

int include(const string_res & s, const charclass_res & mask) {
        for ( i; len(s) ) {
                if ( ! test(mask, s[i]) ) return i;
        }
        return len(s);
}

//######################### VbyteHeap "implementation" #########################


// Add a new HandleNode node n after the current HandleNode node.

static void AddThisAfter( HandleNode & s, HandleNode & n ) with(s) {
#ifdef VbyteDebug
        serr | "enter:AddThisAfter, s:" | &s | " n:" | &n;
#endif // VbyteDebug
        // Performance note: we are on the critical path here. MB has ensured that the verifies don't contribute to runtime (are compiled away, like they're supposed to be).
        verify( n.ulink != 0p );
        verify( s.ulink == n.ulink );
        flink = n.flink;
        blink = &n;
        n.flink->blink = &s;
        n.flink = &s;
#ifdef VbyteDebug
        {
                serr | "HandleList:";
                serr | nlOff;
                for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
                        serr | "\tnode:" | ni | " lnth:" | ni->lnth | " s:" | (void *)ni->s | ",\"";
                        for ( i; ni->lnth ) {
                                serr | ni->s[i];
                        } // for
                        serr | "\" flink:" | ni->flink | " blink:" | ni->blink | nl;
                } // for
                serr | nlOn;
        }
        serr | "exit:AddThisAfter";
#endif // VbyteDebug
} // AddThisAfter


// Delete the current HandleNode node.

static void DeleteNode( HandleNode & s ) with(s) {
#ifdef VbyteDebug
        serr | "enter:DeleteNode, s:" | &s;
#endif // VbyteDebug
        flink->blink = blink;
        blink->flink = flink;
#ifdef VbyteDebug
        serr | "exit:DeleteNode";
#endif // VbyteDebug
} //  DeleteNode


// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
// allocation, the garbage collection routine is called.

static char * VbyteAlloc( VbyteHeap & s, int size ) with(s) {
#ifdef VbyteDebug
        serr | "enter:VbyteAlloc, size:" | size;
#endif // VbyteDebug
        uintptr_t NoBytes;
        char *r;

        NoBytes = ( uintptr_t )EndVbyte + size;
        if ( NoBytes > ( uintptr_t )ExtVbyte ) {                        // enough room for new byte-string ?
                garbage( s, size );                                                             // firer up the garbage collector
                verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte  && "garbage run did not free up required space" );
        } // if
        r = EndVbyte;
        EndVbyte += size;
#ifdef VbyteDebug
        serr | "exit:VbyteAlloc, r:" | (void *)r | " EndVbyte:" | (void *)EndVbyte | " ExtVbyte:" | ExtVbyte;
#endif // VbyteDebug
        return r;
} // VbyteAlloc


// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
// new allocations of its original size + delta bytes. Positive delta means bigger;
// negative means smaller.  A null return indicates that the original heap location has room for
// the requested growth.  A non-null return indicates that copying to a new location is required
// but has not been done; the returned value is the old heap storage location; `this` heap is
// modified to reference the new location.  In the copy-requred case, the caller should use
// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.

static char * VbyteTryAdjustLast( VbyteHeap & s, int delta ) with(s) {
        if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
                // room available
                EndVbyte += delta;
                return 0p;
        }

        char *oldBytes = StartVbyte;

        NoOfExtensions += 1;
        CurrSize *= 2;
        StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
        ExtVbyte = StartVbyte + CurrSize;

        return oldBytes;
}


// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
// the address in the byte string area.

static void MoveThisAfter( HandleNode & s, const HandleNode  & h ) with(s) {
#ifdef VbyteDebug
        serr | "enter:MoveThisAfter, s:" | & s | " h:" | & h;
#endif // VbyteDebug
        verify( h.ulink != 0p );
        verify( s.ulink == h.ulink );
        if ( s < h.s ) {                                        // check argument values
                // serr | "VbyteSM: Error - Cannot move byte string starting at:" | s | " after byte string starting at:"
                //        | ( h->s ) | " and keep handles in ascending order";
                // exit(-1 );
                verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
        } // if

        HandleNode *i;
        for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
        if ( & s != i->blink ) {
                DeleteNode( s );
                AddThisAfter( s, *i->blink );
        } // if
#ifdef VbyteDebug
        {
                serr | "HandleList:";
                serr | nlOff;
                for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
                        for ( i; n->lnth ) {
                                serr | n->s[i];
                        } // for
                        serr | "\" flink:" | n->flink | " blink:" | n->blink | nl;
                } // for
                serr | nlOn;
        }
        serr | "exit:MoveThisAfter";
#endif // VbyteDebug
} // MoveThisAfter


//######################### VbyteHeap #########################

// Compare two byte strings in the byte-string area. The routine returns the following values:
//
// 1 => Src1-byte-string > Src2-byte-string
// 0 => Src1-byte-string = Src2-byte-string
// -1 => Src1-byte-string < Src2-byte-string

int ByteCmp( char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth )  {
#ifdef VbyteDebug
        serr | "enter:ByteCmp, Src1Start:" | Src1Start | " Src1Lnth:" | Src1Lnth | " Src2Start:" | Src2Start | " Src2Lnth:" | Src2Lnth;
#endif // VbyteDebug
        int cmp;

  CharZip: for ( int i = 0; ; i += 1 ) {
                if ( i == Src2Lnth - 1 ) {
                        for ( ; ; i += 1 ) {
                                if ( i == Src1Lnth - 1 ) {
                                        cmp = 0;
                                        break CharZip;
                                } // exit
                                if ( Src1[Src1Start + i] != ' ') {
                                        // SUSPECTED BUG:  this could be be why Peter got the bug report about == " "  (why is this case here at all?)
                                        cmp = 1;
                                        break CharZip;
                                } // exit
                        } // for
                } // exit
                if ( i == Src1Lnth - 1 ) {
                        for ( ; ; i += 1 ) {
                                if ( i == Src2Lnth - 1 ) {
                                        cmp = 0;
                                        break CharZip;
                                } // exit
                                if ( Src2[Src2Start + i] != ' ') {
                                        cmp = -1;
                                        break CharZip;
                                } // exit
                        } // for
                } // exit
                if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
                        cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
                        break CharZip;
                } // exit
        } // for
#ifdef VbyteDebug
        serr | "exit:ByteCmp, cmp:" | cmp;
#endif // VbyteDebug
        return cmp;
} // ByteCmp


// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
// order by pointers into the byte-string area.  The strings associated with substrings do not have to be moved because
// the containing string has been moved. Hence, they only require that their string pointers be adjusted.

void compaction(VbyteHeap & s) with(s) {
        HandleNode *h;
        char *obase, *nbase, *limit;
        
        NoOfCompactions += 1;
        EndVbyte = StartVbyte;
        h = Header.flink;                                       // ignore header node
        for () {
                memmove( EndVbyte, h->s, h->lnth );
                obase = h->s;
                h->s = EndVbyte;
                nbase = h->s;
                EndVbyte += h->lnth;
                limit = obase + h->lnth;
                h = h->flink;
                
                // check if any substrings are allocated within a string
                
                for () {
                        if ( h == &Header ) break;                      // end of header list ?
                        if ( h->s >= limit ) break;                     // outside of current string ?
                        h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
                        h = h->flink;
                } // for
                if ( h == &Header ) break;                      // end of header list ?
        } // for
} // compaction


static double heap_expansion_freespace_threshold = 0.1;  // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage)
                                                                                                                 // probably an unreasonable default, but need to assess early-round tests on changing it

void TUNING_set_string_heap_liveness_threshold( double val ) {
        heap_expansion_freespace_threshold = 1.0 - val;
}


// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
// the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.

void garbage(VbyteHeap & s, int minreq ) with(s) {
#ifdef VbyteDebug
        serr | "enter:garbage";
        {
                serr | "HandleList:";
                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
                        serr | nlOff;
                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
                        for ( i; n->lnth ) {
                                serr | n->s[i];
                        } // for
                        serr | nlOn;
                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
                } // for
        }
#endif // VbyteDebug
        int AmountUsed, AmountFree;

        AmountUsed = 0;
        for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
                AmountUsed += i->lnth;
        } // for
        AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
        
        if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) || AmountFree < minreq ) {       // free space less than threshold or not enough to serve cur request

                extend( s, max( CurrSize, minreq ) );                           // extend the heap

                //  Peter says, "This needs work before it should be used."
                //  } else if ( AmountFree > CurrSize / 2 ) {           // free space greater than 3 times the initial allocation ? 
                //              reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory

                // `extend` implies a `compaction` during the copy

        } else {
                compaction(s);                                  // in-place
        }// if
#ifdef VbyteDebug
        {
                serr | "HandleList:";
                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
                        serr | nlOff;
                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
                        for ( i; n->lnth ) {
                                serr | n->s[i];
                        } // for
                        serr | nlOn;
                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
                } // for
        }
        serr | "exit:garbage";
#endif // VbyteDebug
} // garbage

#undef VbyteDebug



// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
// area is deleted.

void extend( VbyteHeap & s, int size ) with (s) {
#ifdef VbyteDebug
        serr | "enter:extend, size:" | size;
#endif // VbyteDebug
        char *OldStartVbyte;

        NoOfExtensions += 1;
        OldStartVbyte = StartVbyte;                             // save previous byte area
        
        CurrSize += size > InitSize ? size : InitSize;  // minimum extension, initial size
        StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
        ExtVbyte = (void *)( StartVbyte + CurrSize );
        compaction(s);                                  // copy from old heap to new & adjust pointers to new heap
        free( OldStartVbyte );                          // release old heap
#ifdef VbyteDebug
        serr | "exit:extend, CurrSize:" | CurrSize;
#endif // VbyteDebug
} // extend

//WIP
#if 0

// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
// area is deleted.

void VbyteHeap::reduce( int size ) {
#ifdef VbyteDebug
        serr | "enter:reduce, size:" | size;
#endif // VbyteDebug
        char *OldStartVbyte;

        NoOfReductions += 1;
        OldStartVbyte = StartVbyte;                             // save previous byte area
        
        CurrSize -= size;
        StartVbyte = EndVbyte = new char[CurrSize];
        ExtVbyte = (void *)( StartVbyte + CurrSize );
        compaction();                                   // copy from old heap to new & adjust pointers to new heap
        delete  OldStartVbyte;                          // release old heap
#ifdef VbyteDebug
        !serr | "exit:reduce, CurrSize:" | CurrSize;
#endif // VbyteDebug
} // reduce


#endif