Index: libcfa/src/containers/string_res.cfa =================================================================== --- libcfa/src/containers/string_res.cfa (revision 6aa84e084b48dcf666a33d982e713b31e37674ce) +++ libcfa/src/containers/string_res.cfa (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) @@ -21,6 +21,19 @@ -#ifdef VbyteDebug -extern HandleNode *HeaderPtr; + + + + + + +// DON'T COMMIT: +// #define VbyteDebug + + + + + +#ifdef VbyteDebug +HandleNode *HeaderPtr; #endif // VbyteDebug @@ -140,4 +153,15 @@ VbyteHeap HeapArea; + +VbyteHeap * DEBUG_string_heap = & HeapArea; + +size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) { + return ((char*)heap->ExtVbyte) - heap->EndVbyte; +} + +const char * DEBUG_string_heap_start( VbyteHeap * heap ) { + return heap->StartVbyte; +} + // Returns the size of the string in bytes @@ -225,21 +249,42 @@ void assign(string_res &this, const char* buffer, size_t bsize) { + // traverse the incumbent share-edit set (SES) to recover the range of a base string to which `this` belongs + string_res * shareEditSetStartPeer = & this; + string_res * shareEditSetEndPeer = & this; + for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) { + if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) { + shareEditSetStartPeer = editPeer; + } + if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) { + shareEditSetEndPeer = editPeer; + } + } + + // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer + // `this` occurs in the middle of it, to be replaced + // build up the new text in `pasting` + + string_res pasting = { + shareEditSetStartPeer->Handle.s, // start of SES + this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this + append( pasting, + buffer, // start of replacement for this + bsize ); // length of replacement for this + append( pasting, + this.Handle.s + this.Handle.lnth, // start of SES after this + shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - + (this.Handle.s + this.Handle.lnth) ); // length of SES, after this + + // The above string building can trigger compaction. + // The reference points (that are arguments of the string building) may move during that building. + // From this point on, they are stable. + // So now, capture their values for use in the overlap cases, below. + // Do not factor these definitions with the arguments used above. + + char * beforeBegin = shareEditSetStartPeer->Handle.s; + size_t beforeLen = this.Handle.s - beforeBegin; + char * afterBegin = this.Handle.s + this.Handle.lnth; - - char * shareEditSetStart = this.Handle.s; - char * shareEditSetEnd = afterBegin; - for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) { - shareEditSetStart = min( shareEditSetStart, editPeer->Handle.s ); - shareEditSetEnd = max( shareEditSetStart, editPeer->Handle.s + editPeer->Handle.lnth); - } - - char * beforeBegin = shareEditSetStart; - size_t beforeLen = this.Handle.s - shareEditSetStart; - size_t afterLen = shareEditSetEnd - afterBegin; - - string_res pasting = { beforeBegin, beforeLen }; - append(pasting, buffer, bsize); - string_res after = { afterBegin, afterLen }; // juxtaposed with in-progress pasting - pasting += after; // optimized case + size_t afterLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - afterBegin; size_t oldLnth = this.Handle.lnth; @@ -253,12 +298,20 @@ for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) { assert (p->Handle.s >= beforeBegin); - if ( p->Handle.s < beforeBegin + beforeLen ) { - // p starts before the edit - if ( p->Handle.s + p->Handle.lnth < beforeBegin + beforeLen ) { + if ( p->Handle.s >= afterBegin ) { + assert ( p->Handle.s <= afterBegin + afterLen ); + assert ( 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 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 ); @@ -274,27 +327,20 @@ size_t startOffsetFromStart = p->Handle.s - beforeBegin; p->Handle.s = pasting.Handle.s + startOffsetFromStart; - } else if ( p->Handle.s < afterBegin ) { + } else { + assert ( p->Handle.s < afterBegin ); // p starts during the edit assert( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen ); if ( p->Handle.s + p->Handle.lnth < afterBegin ) { - // p ends during the edit + // 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 = this.Handle.s; p->Handle.lnth = 0; } else { - // p ends after the edit + // 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 = this.Handle.s + this.Handle.lnth; - p->Handle.lnth += this.Handle.lnth; - p->Handle.lnth -= oldLnth; + p->Handle.lnth -= charsToClip; } - } else { - assert ( p->Handle.s <= afterBegin + afterLen ); - assert ( 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 } MoveThisAfter( p->Handle, pasting.Handle ); // move substring handle to maintain sorted order by string position @@ -641,5 +687,4 @@ } // if #ifdef VbyteDebug - serr | "exit:MoveThisAfter"; { serr | "HandleList:"; @@ -650,8 +695,9 @@ serr | n->s[i]; } // for - serr | "\" flink:" | n->flink | " blink:" | n->blink; + serr | "\" flink:" | n->flink | " blink:" | n->blink | nl; } // for serr | nlOn; } + serr | "exit:MoveThisAfter"; #endif // VbyteDebug } // MoveThisAfter @@ -662,8 +708,4 @@ //######################### VbyteHeap ######################### - -#ifdef VbyteDebug -HandleNode *HeaderPtr = 0p; -#endif // VbyteDebug // Move characters from one location in the byte-string area to another. The routine handles the following situations: Index: libcfa/src/containers/string_res.hfa =================================================================== --- libcfa/src/containers/string_res.hfa (revision 6aa84e084b48dcf666a33d982e713b31e37674ce) +++ libcfa/src/containers/string_res.hfa (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) @@ -36,4 +36,8 @@ void ?{}( HandleNode &, VbyteHeap & ); // constructor for nodes in the handle list void ^?{}( HandleNode & ); // destructor for handle nodes + +extern VbyteHeap * DEBUG_string_heap; +size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ); +const char * DEBUG_string_heap_start( VbyteHeap * heap ); Index: tests/collections/.expect/string-gc.txt =================================================================== --- tests/collections/.expect/string-gc.txt (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) +++ tests/collections/.expect/string-gc.txt (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) @@ -0,0 +1,39 @@ +======================== basicFillCompact +hello! +hello!----| +hello!----|----| +hello!----|----|----| +--A +length of x:21 +padder from 6 to 11 +x from 0 to 21 +--B +length of x:996 +padder from 6 to 11 +x from 0 to 996 +--C +xinit from 0 to 6 +padder from 6 to 11 +x from 996 to 997 +--D +before append, x = q +after append, x = q----| +--E +xinit from 0 to 6 +padder from 6 to 11 +x from 11 to 17 +--F +983 bytes available before re-fill +1 bytes available after re-fill +--G +after re-fill, x = q----| +======================== fillCompact_withSharedEdits +x from 990 to 995 +y from 990 to 995 +- +before reassign, x = hello +before reassign, y = hello +after reassign, x = 0123456789 +after reassign, y = 0123456789 +x from 5 to 15 +y from 5 to 15 Index: tests/collections/.expect/string-overwrite.txt =================================================================== --- tests/collections/.expect/string-overwrite.txt (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) +++ tests/collections/.expect/string-overwrite.txt (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) @@ -0,0 +1,632 @@ +abcdeqqqqqklmnopqrstuvwxyz +abcde-----qqqqqklmnopqrstuvwxyz +------------------------------------------------------------------------ warmup +abcdefghijklmnopqrstuvwxyz + --! + ----------? +abcdefghijklxxxxxopqrstuvwxyz ( wit = klxxxxxopqrst witlen = 13 ) +abcdefghij?uvwxyz +------------------------------------------------------------------------ 1 +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghij=====klmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=====?klmnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghij==klmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij==?klmnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghij=klmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=?klmnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghijklmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?klmnopqrstuvwxyz +------------------------------------------------------------------------ 2 +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij=====mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=====?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij==mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij==?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij=mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghijmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ 3 +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijkl=====mnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?=====mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijkl==mnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?==mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijkl=mnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?=mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijklmnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ 4 +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghij=====klmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=====kl?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghij==klmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij==kl?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghij=klmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=kl?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghijklmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghijkl?mnopqrstuvwxyz +------------------------------------------------------------------------ 5 +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghijkl=====mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?kl=====mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghijkl==mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?kl==mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghijkl=mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?kl=mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ? +abcdefghijklmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?klmnopqrstuvwxyz +------------------------------------------------------------------------ 6 +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij=====mnopqrstuvwxyz ( wit = ===== witlen = 5 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij==mnopqrstuvwxyz ( wit = == witlen = 2 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij=mnopqrstuvwxyz ( wit = = witlen = 1 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ 7 +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij=====mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=====mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij==mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?==mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij=mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghijmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ 8 +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghij=====klmnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij=====?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghij==klmnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij==?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghij=klmnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij=?mnopqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijklmnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ 9 +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij=====mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=====mn?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij==mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij==mn?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghij=mnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=mn?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghijmnopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghijmn?opqrstuvwxyz +------------------------------------------------------------------------ 10 +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghij=====opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=====?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghij==opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij==?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghij=opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij=?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghijopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 11 +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijklmn=====opqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mn=====opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijklmn==opqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mn==opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijklmn=opqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mn=opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijklmnopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mnopqrstuvwxyz +------------------------------------------------------------------------ 12 +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghijkl=====opqrstuvwxyz ( wit = kl===== witlen = 7 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghijkl==opqrstuvwxyz ( wit = kl== witlen = 4 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghijkl=opqrstuvwxyz ( wit = kl= witlen = 3 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghijklopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 13 +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij=====mnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij=====?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij==mnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij==?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij=mnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij=?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijmnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 14 +abcdefghijklmnopqrstuvwxyz + ----! + ? +abcdefghij=====opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=====opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ? +abcdefghij==opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?==opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ? +abcdefghij=opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ? +abcdefghijopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 15 +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijkl=====opqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?=====opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijkl==opqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?==opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijkl=opqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?=opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijklopqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 16 +abcdefghijklmnopqrstuvwxyz + ! + ----? +abcdefghijkl=====mnopqrstuvwxyz ( wit = kl=====mn witlen = 9 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ----? +abcdefghijkl==mnopqrstuvwxyz ( wit = kl==mn witlen = 6 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ----? +abcdefghijkl=mnopqrstuvwxyz ( wit = kl=mn witlen = 5 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + ----? +abcdefghijklmnopqrstuvwxyz ( wit = klmn witlen = 4 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 17 +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghij=====opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=====opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghij==opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?==opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghij=opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + --? +abcdefghijopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 18 +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghij=====klmnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij=====kl?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghij==klmnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij==kl?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghij=klmnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij=kl?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ! + --? +abcdefghijklmnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghijkl?opqrstuvwxyz +------------------------------------------------------------------------ 19 +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghij=====mnopqrstuvwxyz ( wit = =====mn witlen = 7 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghij==mnopqrstuvwxyz ( wit = ==mn witlen = 4 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghij=mnopqrstuvwxyz ( wit = =mn witlen = 3 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ----? +abcdefghijmnopqrstuvwxyz ( wit = mn witlen = 2 ) +abcdefghij?opqrstuvwxyz +------------------------------------------------------------------------ 20 +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghijkl=====opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?kl=====opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghijkl==opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?kl==opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghijkl=opqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?kl=opqrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ? +abcdefghijklopqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?klopqrstuvwxyz +------------------------------------------------------------------------ 21 +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij=====mnopqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghij=====mn?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij==mnopqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghij==mn?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghij=mnopqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghij=mn?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijmnopqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghijmn?qrstuvwxyz +------------------------------------------------------------------------ 22 +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghij=====opqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghij=====?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghij==opqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghij==?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghij=opqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghij=?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghijopqrstuvwxyz ( wit = op witlen = 2 ) +abcdefghij?qrstuvwxyz +------------------------------------------------------------------------ 23 +abcdefghijklmnopqrstuvwxyz + ------! + --? +abcdefghij=====qrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=====qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ------! + --? +abcdefghij==qrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?==qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ------! + --? +abcdefghij=qrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?=qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ------! + --? +abcdefghijqrstuvwxyz ( wit = witlen = 0 ) +abcdefghij?qrstuvwxyz +------------------------------------------------------------------------ 24 +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijklmn=====qrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mn=====qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijklmn==qrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mn==qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijklmn=qrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mn=qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + --? +abcdefghijklmnqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?mnqrstuvwxyz +------------------------------------------------------------------------ 25 +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghijkl=====qrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?=====qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghijkl==qrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?==qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghijkl=qrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?=qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + ----! + ----? +abcdefghijklqrstuvwxyz ( wit = kl witlen = 2 ) +abcdefghij?qrstuvwxyz +------------------------------------------------------------------------ 26 +abcdefghijklmnopqrstuvwxyz + --! + ------? +abcdefghijkl=====opqrstuvwxyz ( wit = kl=====op witlen = 9 ) +abcdefghij?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ------? +abcdefghijkl==opqrstuvwxyz ( wit = kl==op witlen = 6 ) +abcdefghij?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ------? +abcdefghijkl=opqrstuvwxyz ( wit = kl=op witlen = 5 ) +abcdefghij?qrstuvwxyz +------------------------------------------------------------------------ +abcdefghijklmnopqrstuvwxyz + --! + ------? +abcdefghijklopqrstuvwxyz ( wit = klop witlen = 4 ) +abcdefghij?qrstuvwxyz Index: tests/collections/string-gc.cfa =================================================================== --- tests/collections/string-gc.cfa (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) +++ tests/collections/string-gc.cfa (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) @@ -0,0 +1,125 @@ +#include + +size_t bytesRemaining() { + return DEBUG_string_bytes_avail_until_gc( DEBUG_string_heap ); +} + +size_t heapOffsetStart( string_res & s ) { + const char * startByte = DEBUG_string_heap_start( DEBUG_string_heap ); + assert( s.Handle.s >= startByte ); + return s.Handle.s - startByte; +} + +void prtStrRep(const char * label, string_res & s) { + sout | label | "from" | heapOffsetStart(s) | "to" | (heapOffsetStart(s) + size(s)); +} +#define PRT_STR_REP(s) prtStrRep( #s, s ) + +void basicFillCompact() { + sout | "======================== basicFillCompact"; + string_res xinit = "hello!"; + string_res x = {xinit, COPY_VALUE}; + string_res padder = "----|"; + sout | x; + for( 3 ) { + x += padder; + sout | x; + } + + // x and padder overlap + sout | "--A"; + sout | "length of x:" | size(x); + PRT_STR_REP(padder); + PRT_STR_REP(x); + + while ( bytesRemaining() + 1 > 5 ) { // until room for "q" but not another "----|" thereafter + x += padder; + } + + // x and padder still overlap; now x is huge + sout | "--B"; + sout | "length of x:" | size(x); + PRT_STR_REP(padder); + PRT_STR_REP(x); + + assert( bytesRemaining() >= 1 ); + x = "q"; + + // x and padder no longer overlap; baseline xinit + sout | "--C"; + PRT_STR_REP(xinit); + PRT_STR_REP(padder); + PRT_STR_REP(x); + + // want the next edit to straddle the bound + assert( bytesRemaining() < size(padder) ); + + sout | "--D"; + sout | "before append, x = " | x; // q + x += padder; // trigger compaction + sout | "after append, x = " | x; // q----| + + // x and padder moved to the start + sout | "--E"; + PRT_STR_REP(xinit); + PRT_STR_REP(padder); + PRT_STR_REP(x); + + // plenty of room now + sout | "--F"; + sout | bytesRemaining() | "bytes available before re-fill"; + + // fill it again + string_res z = "zzz"; + while ( bytesRemaining() > 1 ) { + z += "."; + } + + sout | bytesRemaining() | "bytes available after re-fill"; + + // ensure not affected (shows it's not referencing an invalid location that hadn't been overwritten from the original value yet) + // black-box criterion that matches earlier "saw it move" + sout | "--G"; + sout | "after re-fill, x = " | x; // q----| + + // leave the heap basically empty, for the next test + z = ""; // turn used space into gargbage + string_res whatever = "asdf"; // trigger compaction + assert( bytesRemaining() > 100 ); +} + +void fillCompact_withSharedEdits() { + // do an assignment that causes a collection to happen, while there are edits shared (substrings) + + sout | "======================== fillCompact_withSharedEdits"; + + // mostly fill the pad + string_res z = "zzz"; + while ( bytesRemaining() > 10 ) { + z += "."; + } + z = ""; // leave compaction possible + + // setup + string_res x = "hello"; + string_res y = { x, SHARE_EDITS, 0, 5 }; + PRT_STR_REP(x); + PRT_STR_REP(y); + sout | "-"; + + sout | "before reassign, x = " | x; // hello + sout | "before reassign, y = " | y; // hello + + x = "0123456789"; // compact here + + sout | "after reassign, x = " | x; // 0123456789 + sout | "after reassign, y = " | y; // 0123456789 + + PRT_STR_REP(x); + PRT_STR_REP(y); +} + +int main() { + basicFillCompact(); + fillCompact_withSharedEdits(); +} Index: tests/collections/string-overwrite.cfa =================================================================== --- tests/collections/string-overwrite.cfa (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) +++ tests/collections/string-overwrite.cfa (revision 6cc87c0c8c3470f60ca93a524803cf323c2dbf05) @@ -0,0 +1,263 @@ +#include + +/* + +Modify a subrange of a string, while a witness is watching another subrange of the same string. + +Cases are the relative positions and overlaps of the modifier vs the witness. +MS = modifier start +ME = modifier end +WS = witness start +WE = witness end + +The dest does: + starts with the entire string being, initially, the alphabet; prints this entire alphabet + sets up modifier and witness as ranges within it, and prints a visualization of those ranges + does the main modification + prints the result of the main modification, which is always an unsurprising consequence of the modifier range, but shows little about what happened to the witness, particularly if the witness is/became empty + modifies the witness to be "?" + prints the result of this second modification, which implies what the witness included after the main modification + +Deriving the concrete list of cases.... + +By definition of a string, MS <= ME and WS <= WE. +This API's convention has Start positions being inclusive and end positions being exclusive. + +With 1 equivalence class: +MS = ME = WS = WE 1 + +With 2 equivalence classes: + < = = +MS rest 2 +WS rest 3 + + = < = +MS ME WS WE 4 +WS WE MS ME 5 +MS WS ME WE 6 + + = = < + rest ME 7 + rest WE 8 + +With 3 equivalence classes + < < = +MS ME WS WE 9 + WS ME WE 10 ++2 11, 12 + + < = < +MS WS ME WE 13 + WE ME 14 ++2 15, 16 + + = < < +MS WS WE ME 17 + ME WS WE 18 ++2 19, 20 + +With 4 equivalence classes + < < < +MS ME WS WE 21 + WS ME WE 22 + WE ME 23 ++3 24, 25, 26 + + + +*/ + + +void showOneReplacement(string & s, int ms, int me, int ws, int we, const char* replaceWith) { + + assert( ms >= 0 && ms <= me && me <= size(s) ); + assert( ws >= 0 && ws <= we && we <= size(s) ); + + string mod = s(ms, me)`shareEdits; + string wit = s(ws, we)`shareEdits; + + string modOld = mod; + string witOld = wit; + + // s, before the mode + sout | s; + + // visualize the pair of ranges + sout | nlOff; + for ( i; size(s) ) { + if( i < ms || i > me ) { + sout | ' '; + } else if ( i < me ) { + sout | '-'; + } else { + assert ( i == me ); + sout | '!'; + } + } sout | nl; + for ( i; size(s) ) { + if( i < ws || i > we ) { + sout | ' '; + } else if ( i < we ) { + sout | '-'; + } else { + assert ( i == we ); + sout | '?'; + } + } + sout | nl; + sout | nlOn; + + mod = replaceWith; // main replacement + sout | s | "( wit = " | wit | "witlen = " | size(wit) | " )"; + wit = "?"; // witness-revelaing replacement + sout | s; +} + +void runReplaceCases() { + char * alphabetTemplate = "abcdefghijklmnopqrstuvwxyz"; + struct { int ms; int me; int ws; int we; char *replaceWith; char *label; } cases[] = { + { 12, 14, 10, 20, "xxxxx", "warmup" }, +// { 12, 14, 12, 14, "xxxxx", "" }, // the bug that got me into this test (should be a dup with case 6) + { 10, 10, 10, 10, "=====", "1" }, + { 10, 10, 10, 10, "==" , "" }, + { 10, 10, 10, 10, "=" , "" }, + { 10, 10, 10, 10, "" , "" }, + { 10, 12, 12, 12, "=====", "2" }, + { 10, 12, 12, 12, "==" , "" }, + { 10, 12, 12, 12, "=" , "" }, + { 10, 12, 12, 12, "" , "" }, + { 12, 12, 10, 12, "=====", "3" }, + { 12, 12, 10, 12, "==" , "" }, + { 12, 12, 10, 12, "=" , "" }, + { 12, 12, 10, 12, "" , "" }, + { 10, 10, 12, 12, "=====", "4" }, + { 10, 10, 12, 12, "==" , "" }, + { 10, 10, 12, 12, "=" , "" }, + { 10, 10, 12, 12, "" , "" }, + { 12, 12, 10, 10, "=====", "5" }, + { 12, 12, 10, 10, "==" , "" }, + { 12, 12, 10, 10, "=" , "" }, + { 12, 12, 10, 10, "" , "" }, + { 10, 12, 10, 12, "=====", "6" }, + { 10, 12, 10, 12, "==" , "" }, + { 10, 12, 10, 12, "=" , "" }, + { 10, 12, 10, 12, "" , "" }, + { 10, 12, 10, 10, "=====", "7" }, + { 10, 12, 10, 10, "==" , "" }, + { 10, 12, 10, 10, "=" , "" }, + { 10, 12, 10, 10, "" , "" }, + { 10, 10, 10, 12, "=====", "8" }, + { 10, 10, 10, 12, "==" , "" }, + { 10, 10, 10, 12, "=" , "" }, + { 10, 10, 10, 12, "" , "" }, + { 10, 12, 14, 14, "=====", "9" }, + { 10, 12, 14, 14, "==" , "" }, + { 10, 12, 14, 14, "=" , "" }, + { 10, 12, 14, 14, "" , "" }, + { 10, 14, 12, 14, "=====", "10" }, + { 10, 14, 12, 14, "==" , "" }, + { 10, 14, 12, 14, "=" , "" }, // FORMERLY unrunnable bug: tries to print seemingly infinite string + { 10, 14, 12, 14, "" , "" }, // ditto + { 14, 14, 10, 12, "=====", "11" }, + { 14, 14, 10, 12, "==" , "" }, + { 14, 14, 10, 12, "=" , "" }, + { 14, 14, 10, 12, "" , "" }, + { 12, 14, 10, 14, "=====", "12" }, // correctness observation: watching klmn while mn |-> xxx gives klxxx because the mn is inside what I'm watching + { 12, 14, 10, 14, "==" , "" }, + { 12, 14, 10, 14, "=" , "" }, + { 12, 14, 10, 14, "" , "" }, + { 10, 12, 12, 14, "=====", "13" }, + { 10, 12, 12, 14, "==" , "" }, + { 10, 12, 12, 14, "=" , "" }, + { 10, 12, 12, 14, "" , "" }, + { 10, 14, 12, 12, "=====", "14" }, + { 10, 14, 12, 12, "==" , "" }, + { 10, 14, 12, 12, "=" , "" }, + { 10, 14, 12, 12, "" , "" }, + { 12, 14, 10, 12, "=====", "15" }, + { 12, 14, 10, 12, "==" , "" }, + { 12, 14, 10, 12, "=" , "" }, + { 12, 14, 10, 12, "" , "" }, + { 12, 12, 10, 14, "=====", "16" }, + { 12, 12, 10, 14, "==" , "" }, + { 12, 12, 10, 14, "=" , "" }, + { 12, 12, 10, 14, "" , "" }, + { 10, 14, 10, 12, "=====", "17" }, + { 10, 14, 10, 12, "==" , "" }, + { 10, 14, 10, 12, "=" , "" }, + { 10, 14, 10, 12, "" , "" }, + { 10, 10, 12, 14, "=====", "18" }, + { 10, 10, 12, 14, "==" , "" }, + { 10, 10, 12, 14, "=" , "" }, + { 10, 10, 12, 14, "" , "" }, + { 10, 12, 10, 14, "=====", "19" }, + { 10, 12, 10, 14, "==" , "" }, + { 10, 12, 10, 14, "=" , "" }, + { 10, 12, 10, 14, "" , "" }, + { 12, 14, 10, 10, "=====", "20" }, + { 12, 14, 10, 10, "==" , "" }, + { 12, 14, 10, 10, "=" , "" }, + { 12, 14, 10, 10, "" , "" }, + { 10, 12, 14, 16, "=====", "21" }, + { 10, 12, 14, 16, "==" , "" }, + { 10, 12, 14, 16, "=" , "" }, + { 10, 12, 14, 16, "" , "" }, + { 10, 14, 12, 16, "=====", "22" }, + { 10, 14, 12, 16, "==" , "" }, + { 10, 14, 12, 16, "=" , "" }, + { 10, 14, 12, 16, "" , "" }, + { 10, 16, 12, 14, "=====", "23" }, + { 10, 16, 12, 14, "==" , "" }, + { 10, 16, 12, 14, "=" , "" }, + { 10, 16, 12, 14, "" , "" }, + { 14, 16, 10, 12, "=====", "24" }, + { 14, 16, 10, 12, "==" , "" }, + { 14, 16, 10, 12, "=" , "" }, + { 14, 16, 10, 12, "" , "" }, + { 12, 16, 10, 14, "=====", "25" }, + { 12, 16, 10, 14, "==" , "" }, + { 12, 16, 10, 14, "=" , "" }, + { 12, 16, 10, 14, "" , "" }, + { 12, 14, 10, 16, "=====", "26" }, + { 12, 14, 10, 16, "==" , "" }, + { 12, 14, 10, 16, "=" , "" }, + { 12, 14, 10, 16, "" , "" }, +/* + { , , , , "=====", "NN" }, + { "==" , "" }, + { "=" , "" }, + { "" , "" }, +*/ + }; + for ( i; sizeof(cases)/sizeof(cases[0]) ) { + sout | "------------------------------------------------------------------------" | cases[i].label; + string replaceIn = alphabetTemplate; + showOneReplacement( replaceIn, cases[i].ms, cases[i].me, cases[i].ws, cases[i].we, cases[i].replaceWith ); + } +} + + +// void f( string & s, string & toEdit ) { + +// sout | s | "|" | toEdit | "|"; + +// s(14, 16) = "-"; +// sout | s | "|" | toEdit | "|"; +// } + +int main() { + // 0 1 2 + // 01234567890123456789012345 + string s = "abcdefghijklmnopqrstuvwxyz"; + + s(5,10) = "qqqqq"; // start=5, end=10, len=5 + + sout | s; + + + s(5,5) = "-----"; // start=5, end=5, len=0 + + sout | s; + + runReplaceCases(); +}