Changeset 6cc87c0

Timestamp:

Sep 20, 2021, 10:41:29 PM (3 years ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

ADT, ast-experimental, enum, forall-pointer-decay, master, pthread-emulation, qualifiedEnum

Children:

3bf3b6b

Parents:

6aa84e0

Message:

String bug fixes and new tests.

Enabled white-box visibility (DEBUG_ functions) into the string representation for heap-oriented tests.

string-gc/basicFillCompact

• newly testable, now with the DEBUG_ visibility, but was basically already working

string-gc/fillCompact_withSharedEdits

• new check for bug fixed here, where an append that triggers a compaction left substrings with dangling pointers

to the old text-pad range; fix is how string_res/assign now sequences growth-pushing operations before grabbing
pointers into the ranges of the old-version

string-overwrite

• new broad check a few of whose cases are fixed here; fixes are the adjustments to the case priorities and

edge-case classifications in string_res/assign "adjust all substring string and handle locations" section

Files:

• libcfa/src/containers/string_res.cfa (modified) (8 diffs)
• libcfa/src/containers/string_res.hfa (modified) (1 diff)
• tests/collections/.expect/string-gc.txt (added)
• tests/collections/.expect/string-overwrite.txt (added)
• tests/collections/string-gc.cfa (added)
• tests/collections/string-overwrite.cfa (added)

libcfa/src/containers/string_res.cfa

@@ -21 +21 @@
 
 
-#ifdef VbyteDebug
-extern HandleNode *HeaderPtr;
+
+
+
+
+
+
+// DON'T COMMIT:
+// #define VbyteDebug
+
+
+
+
+
+#ifdef VbyteDebug
+HandleNode *HeaderPtr;
 #endif // VbyteDebug
 
@@ -140 +153 @@
 
 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 +249 @@
 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 +298 @@
     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 +327 @@
             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 +687 @@
     } // if
 #ifdef VbyteDebug
-    serr | "exit:MoveThisAfter";
     {
         serr | "HandleList:";
@@ -650 +695 @@
                 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 +708 @@
 
 //######################### 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:

libcfa/src/containers/string_res.hfa

@@ -36 +36 @@
 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 );