bubblesort the metadata entries during postprocessing

since we do this here, we no longer need to worry about doing it during initial entry creation, so that's good. that had been on the mental "maybe later" checklist for a while.

the various innovations in entry processing now make it possible to pass
through most of the formatting in hex.e, so that's done now (suffix comments that aren't instruction decodings still need to be made to work)

there's also a new entry type which will be part of the comment parameter system. that's not fully working yet, but this was a bunch of really subtle debugging, so it makes a good spot to checkpoint at.

Force-Push: yes
Change-Id: I2aff7276368eaad7e5c280a58834605e294dcd74

1 files changed, 160 insertions, 59 deletions

diff --git a/transform.e b/transform.e
index 7560752..ea93ec3 100644
--- a/transform.e
+++ b/transform.e
@@ -2738,6 +2738,7 @@ allocate-transformation-state s" transformation-state" variable
 : hex-output-metadata-entry-type-string-literal 5 ;
 : hex-output-metadata-entry-type-raw-string-literal 6 ;
 : hex-output-metadata-entry-type-alignment 7 ;
+: hex-output-metadata-entry-type-provide-substring-hex64 8 ;
 
 ~   Initialize the contents of the output metadata to all zeroes. This is
 ~ called from hex-transform at its top level, at the very start, to make sure
@@ -2982,6 +2983,16 @@ allocate-transformation-state s" transformation-state" variable
 
   s" swap" find entry-to-execution-token , ;
 
+: is-comment-entry
+  hex-output-metadata-entry-type @
+  dup hex-output-metadata-entry-type-line-comment =
+  swap hex-output-metadata-entry-type-suffix-comment =
+  || ;
+
+: is-provide-substring-entry
+  hex-output-metadata-entry-type @
+  hex-output-metadata-entry-type-provide-substring-hex64 = ;
+
 : is-fresh-line@
   transformation-state transformation-state-output-metadata @
   hex-output-metadata-is-fresh-line @ ;
@@ -3018,66 +3029,134 @@ allocate-transformation-state s" transformation-state" variable
 ~   Any time output is performed, all existing entries are post-processed.
 ~ Therefore, the post-processing is required to be idempotent, and is.
 : postprocess-metadata-entries
-  transformation-state transformation-state-output-metadata @
-  hex-output-metadata-first-entry
-  { dup @ } {
-    ~ (entry pointer)
-
-    ~ Is the entry a suffix comment with a non-zero data length?
-    dup hex-output-metadata-entry-type @
-    hex-output-metadata-entry-type-suffix-comment =
-    over hex-output-metadata-entry-data-length @ 0 != && {
-      ~ (entry pointer)
-      dup dup
-
-      ~   Find all the remaining entries, and the final terminator, and slide
-      ~ them forward by the length of one entry.
-      { dup @ } { hex-output-metadata-next-entry } while 8 +
-      ~ (entry pointer, entry pointer, entry array end pointer)
-      swap -
-      ~ (entry pointer, entry array tail length)
-      swap dup dup hex-output-metadata-next-entry 4 roll
-      ~ (entry pointer, entry pointer, adjusted entry pointer,
-      ~  entry array tail length)
-      memmove
-      ~ (entry pointer)
-
-      ~   We have a feature which lets a suffix comment be created with a
-      ~ negative length, which means it covers bytes before the current output
-      ~ point rather than after it. This logic here is the implementation of
-      ~ that feature.
-      dup hex-output-metadata-entry-data-start @ dup
-      2 pick hex-output-metadata-entry-data-length @ +
-      2dup min 3unroll max
-      ~ (entry pointer, low end of data, high end of data)
-
-      ~   Now we have the original entry at the original location, and a copy
-      ~ of it at the next location. We modify the original one in-place to
-      ~ turn it into a fresh-line entry at the low end of the data...
-      2 pick hex-output-metadata-entry-type
-      hex-output-metadata-entry-type-fresh-line swap !
-
-      2 pick hex-output-metadata-entry-data-start 3roll swap !
-      2 pick hex-output-metadata-entry-data-length 0 swap !
-      ~ (entry pointer, high end of data)
-
-      ~   ... then we modify the next entry in-place to set its location to
-      ~ the end of the data instead of the beginning, and its length to zero.
-      over hex-output-metadata-next-entry
-      ~ (entry pointer, high end of data, next entry pointer)
-
-      dup hex-output-metadata-entry-data-start 3roll swap !
-      hex-output-metadata-entry-data-length 0 swap !
-      ~ (entry pointer)
-
-      ~   This rule won't fire again on the fresh-line entry because it's of a
-      ~ different type, and it won't fire on the modified suffix-comment entry
-      ~ because its data length is zero. There's no other rules either, so our
-      ~ idempotence requirement is satisfied.
-    } if
+  1 { } {
+    0
+    ~ (did anything this iteration)
+
+    transformation-state transformation-state-output-metadata @
+    hex-output-metadata-first-entry
+    { dup @ } {
+      ~ (did anything, entry pointer)
+
+      ~ Is the entry a suffix comment with a non-zero data length?
+      dup hex-output-metadata-entry-type @
+      hex-output-metadata-entry-type-suffix-comment =
+      over hex-output-metadata-entry-data-length @ 0 != && {
+        ~   Split it into two entries so as not to rely on data length for
+        ~ formatting.
+        ~ (did anything, entry pointer)
+
+        ~   Find all the remaining entries, and the final terminator, and slide
+        ~ them forward by the length of one entry.
+        dup dup
+        { dup @ } { hex-output-metadata-next-entry } while 8 +
+        ~ (..., entry pointer, entry pointer, entry array end pointer)
+        swap -
+        ~ (..., entry pointer, entry array tail length)
+        swap dup dup hex-output-metadata-next-entry 4 roll
+        ~ (..., entry pointer, entry pointer, adjusted entry pointer,
+        ~  entry array tail length)
+        memmove
+        ~ (..., entry pointer)
+
+        ~   We have a feature which lets a suffix comment be created with a
+        ~ negative length, which means it covers bytes before the current output
+        ~ point rather than after it. This logic here is the implementation of
+        ~ that feature.
+        dup hex-output-metadata-entry-data-start @ dup
+        2 pick hex-output-metadata-entry-data-length @ +
+        2dup min 3unroll max
+        ~ (..., entry pointer, low end of data, high end of data)
+
+        ~   Now we have the original entry at the original location, and a copy
+        ~ of it at the next location. We modify the original one in-place to
+        ~ turn it into a fresh-line entry at the low end of the data...
+        2 pick hex-output-metadata-entry-type
+        hex-output-metadata-entry-type-fresh-line swap !
+        ~ (..., entry pointer, low end of data, high end of data)
+
+        2 pick hex-output-metadata-entry-data-start 3roll swap !
+        ~ (..., entry pointer, high end of data)
+        over hex-output-metadata-entry-data-length 0 swap !
+        ~ (..., entry pointer, high end of data)
+
+        ~   ... then we modify the next entry in-place to set its location to
+        ~ the end of the data instead of the beginning, and its length to zero.
+        over hex-output-metadata-next-entry
+        ~ (..., entry pointer, high end of data, next entry pointer)
+
+        dup hex-output-metadata-entry-data-start 3roll swap !
+        ~ (..., entry pointer, next entry pointer)
+        hex-output-metadata-entry-data-length 0 swap !
+        ~ (..., entry pointer)
+
+        ~   This rule won't fire again on the fresh-line entry because it's of a
+        ~ a different type, and it won't fire on the modified suffix-comment
+        ~ entry because its data length is zero.
+        ~
+        ~   It's possible the bubble-sort rule will fire on either of them.
+
+        ~ (did anything, entry pointer)
+        swap drop 1 swap
+      } if
+
+      ~   Do this entry and the next entry both exist, and they're out of
+      ~ order based on their data starts?
+      dup hex-output-metadata-next-entry dup @
+        { hex-output-metadata-entry-data-start @
+          over hex-output-metadata-entry-data-start @ > }
+        { drop 0 } if-else
+      {
+        ~   Swap the order of the two entries. Since this whole thing is in a
+        ~ loop, this functions as a bubble sort.
+        ~ (did anything, entry pointer)
+
+        ~ Copy the current entry to a scratch area.
+        dup dup dup hex-output-metadata-next-entry swap -
+        ~ (..., entry pointer, entry pointer, entry length)
+        swap-transform-variables here @ swap-transform-variables swap
+        ~ (..., entry pointer, entry pointer, scratch pointer, entry length)
+        memcopy
+        ~ (..., entry pointer)
+
+        ~ Copy the next entry over the current entry.
+        dup dup hex-output-metadata-next-entry dup
+        ~ (..., entry pointer, entry pointer, next entry pointer,
+        ~  next entry pointer)
+        3roll -
+        ~ (..., entry pointer, next entry pointer, entry length)
+        2 pick swap
+        ~ (..., entry pointer,
+        ~  next entry pointer, entry pointer, entry length)
+        memcopy
+        ~ (entry pointer)
+
+        ~ Copy the scratch area over the next entry.
+        dup hex-output-metadata-next-entry dup
+        ~ (..., entry pointer, next entry pointer, next entry pointer)
+        2 pick -
+        ~ (..., entry pointer, next entry pointer, entry length)
+        swap-transform-variables here @ swap-transform-variables 3unroll
+        ~ (..., entry pointer,
+        ~  scratch pointer, next entry pointer, entry length)
+        memcopy
+        ~ (..., entry pointer)
+
+        ~   This rule won't fire again on the same pair of entries because now
+        ~ they're in the correct order. It may fire again next iteration,
+        ~ but only until everything is sorted.
+        ~
+        ~   This rule does nothing to alter whether the suffix-comment rule
+        ~ will fire on either of the entries it swapped, so there's no
+        ~ possibility of an infinite loop through that one.
+
+        ~ (did anything, entry pointer)
+        swap drop 1 swap
+      } if
 
-    hex-output-metadata-next-entry
-  } while drop ;
+      hex-output-metadata-next-entry
+    } while drop
+  } while ;
 
 ~   This "replacement" is a little different from an alternate: When the code
 ~ under transformation attempts to compile its own version of sys-write, it
@@ -3188,6 +3267,19 @@ allocate-transformation-state s" transformation-state" variable
           0 current-column!
         } if
 
+        dup hex-output-metadata-entry-type @
+        hex-output-metadata-entry-type-provide-substring-hex64 = {
+          fresh-line
+          indentation-depth@ dup indent advance-current-column
+
+          ." ~ hex64 value 0x"
+          dup hex-output-metadata-entry-string @ .hex64
+
+          newline
+          1 is-fresh-line!
+          0 current-column!
+        } if
+
       } if
       hex-output-metadata-next-entry
     } while
@@ -4013,6 +4105,15 @@ allocate-transformation-state s" transformation-state" variable
     exit
   } if
 
+  dup s" provide-substring-hex64" stringcmp 0 = {
+    ~   Create a new "provide substring hex64" entry. Notice that we
+    ~ intentionally read one stack level deeper than anything of ours, which
+    ~ will be a value provided by the code the magic comment is embedded in.
+    drop 2 pick hex-output-metadata-entry-type-provide-substring-hex64 swap
+    add-hex-output-metadata-entry
+    exit
+  } if
+
   ~ If it has a nonzero length, create a new suffix-comment entry.
   over 0 != {
     hex-output-metadata-entry-type-suffix-comment swap