revamp sub/3 to resolve most issues with gsub (and sub with "g")
The primary purpose of this commit is to rectify most problems with gsub (and also sub with "g"), and in particular
#1425 (\b), #2354 (lookahead), and #2532 (regex == "^(?!cd ).*$|^cd "; ""))

The revision also partly resolves #2148 and #1206 in that gsub no longer loops infinitely, but because the new gsub depends on match(_;"g"), the behavior when regex == "" is sometimes non-standard.

Since the new sub/3 relies on uniq/1, that has been added as well; this should be a non-issue as the line count of the revised builtin.jq has been significantly reduced overall.

Also, _nwise/1 has been tweaked to take advantage of TCO.
**Describe the bug**
When you pass the pattern `"^"` or `""` to gsub, it loops forever and eventually runs out of memory.

**To Reproduce**
```
$ echo '{"key": "value"}' | jq '.key|=gsub("^";"")'
error: cannot allocate memory
Aborted (core dumped)
$ echo '{"key": "value"}' | jq '.key|=gsub("";"")'
^C
$ echo '{"key": "value"}' | jq '.key|=gsub("^";"new-prefix")'
^C
$
```

**Expected behavior**
Once the match has been successful, it shouldn't be tried again for the same location.


**Environment (please complete the following information):**
```
$ cat /etc/issue ; jq -V ; echo ; dpkg -s jq | grep -e Version -e Package
Ubuntu 20.04 LTS \n \l

jq-1.6

Package: jq
Version: 1.6-1
$
```

**Additional context**
Add any other context about the problem here.

gsub loops infinitely with "^" or ""
diff --git a/src/builtin.jq b/src/builtin.jq
index a102fd51a0..4d54bc95b3 100644
--- a/src/builtin.jq
+++ b/src/builtin.jq
@@ -99,8 +99,10 @@ def scan(re):
 #
 # If input is an array, then emit a stream of successive subarrays of length n (or less),
 # and similarly for strings.
-def _nwise(a; $n): if a|length <= $n then a else a[0:$n] , _nwise(a[$n:]; $n) end;
-def _nwise($n): _nwise(.; $n);
+def _nwise($n):
+  def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
+  n;
+def _nwise(a; $n): a | _nwise($n);
 #
 # splits/1 produces a stream; split/1 is retained for backward compatibility.
 def splits($re; flags): . as $s
@@ -114,47 +116,33 @@ def splits($re): splits($re; null);
 # split emits an array for backward compatibility
 def split($re; flags): [ splits($re; flags) ];
 #
-# If s contains capture variables, then create a capture object and pipe it to s
-def sub($re; s):
-  . as $in
-  | [match($re)]
-  | if length == 0 then $in
-    else .[0]
-    | . as $r
-#  # create the "capture" object:
-    | reduce ( $r | .captures | .[] | select(.name != null) | { (.name) : .string } ) as $pair
-        ({}; . + $pair)
-    | $in[0:$r.offset] + s + $in[$r.offset+$r.length:]
-    end ;
+# stream-oriented
+def uniq(s):
+  foreach s as $x (null;
+    if . and $x == .[0] then .[1] = false
+    else [$x, true]
+    end;
+    if .[1] then .[0] else empty end);
 #
 # If s contains capture variables, then create a capture object and pipe it to s
-def sub($re; s; flags):
-  def subg: [explode[] | select(. != 103)] | implode;
-  # "fla" should be flags with all occurrences of g removed; gs should be non-nil if flags has a g
-  def sub1(fla; gs):
-    def mysub:
-      . as $in
-      | [match($re; fla)]
-      | if length == 0 then $in
-        else .[0] as $edit
-        | ($edit | .offset + .length) as $len
-        # create the "capture" object:
-        | reduce ( $edit | .captures | .[] | select(.name != null) | { (.name) : .string } ) as $pair
-            ({}; . + $pair)
-        | $in[0:$edit.offset]
-          + s
-          + ($in[$len:] | if length > 0 and gs then mysub else . end)
-        end ;
-    mysub ;
-    (flags | index("g")) as $gs
-    | (flags | if $gs then subg else . end) as $fla
-    | sub1($fla; $gs);
+def sub($re; s; $flags):
+   . as $in
+   | (reduce uniq(match($re; $flags)) as $edit
+        ({result: "", previous: 0};
+            $in[ .previous: ($edit | .offset) ] as $gap
+            # create the "capture" object
+            | (reduce ( $edit | .captures | .[] | select(.name != null) | { (.name) : .string } ) as $pair
+                 ({}; . + $pair) | s) as $insert
+            | .result += $gap + $insert
+	    | .previous = ($edit | .offset + .length ) )
+          | .result + $in[.previous:] )
+      // $in;
 #
 def sub($re; s): sub($re; s; "");
-# repeated substitution of re (which may contain named captures)
+#
 def gsub($re; s; flags): sub($re; s; flags + "g");
 def gsub($re; s): sub($re; s; "g");
-
+#
 ########################################################################
 # generic iterator/generator
 def while(cond; update):
@@ -237,7 +225,6 @@ def tostream:
   getpath($p) |
   reduce path(.[]?) as $q ([$p, .]; [$p+$q]);
 
-
 # Assuming the input array is sorted, bsearch/1 returns
 # the index of the target if the target is in the input array; and otherwise
 #  (-1 - ix), where ix is the insertion point that would leave the array sorted.

diff --git a/tests/onig.test b/tests/onig.test
index daacae9cd7..aff4c6e605 100644
--- a/tests/onig.test
+++ b/tests/onig.test
@@ -75,6 +75,40 @@ gsub( "(.*)"; "";  "x")
 ""
 ""
 
+gsub( ""; "a";  "g")
+""
+"a"
+
+gsub( "^"; "";  "g")
+"a"
+"a"
+
+
+# The following is a regression test and should not be construed as a requirement other than that execution should terminate:
+gsub( ""; "a";  "g")
+"a"
+"aa"
+
+gsub( "$"; "a";  "g")
+"a"
+"aa"
+
+gsub( "^"; "a")
+""
+"a"
+
+gsub("(?=u)"; "u")
+"qux"
+"quux"
+
+gsub("^.*a"; "b")
+"aaa"
+"b"
+
+gsub("^.*?a"; "b")
+"aaa"
+"baa"
+
 [.[] | scan(", ")]
 ["a,b, c, d, e,f",", a,b, c, d, e,f, "]
 [", ",", ",", ",", ",", ",", ",", ",", "]
@@ -92,7 +126,20 @@ gsub("(?<x>.)[^a]*"; "+\(.x)-")
 "Abcabc"
 "+A-+a-"
 
+gsub("(?<x>.)(?<y>[0-9])"; "\(.x|ascii_downcase)\(.y)")
+"A1 B2 CD"
+"a1 b2 CD"
+
+gsub("\\b(?<x>.)"; "\(.x|ascii_downcase)")
+"ABC DEF"
+"aBC dEF"
+
 # utf-8
 sub("(?<x>.)"; "\(.x)!")
 "’"
 "’!"
+
+# splits and _nwise
+[splits("")]
+"ab"
+["","a","b"]

{"tests/onigtest": {"run": "PASS", "test": "FAIL", "fix": "PASS"}}
{"test_options": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "regset": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "callback_each_match": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "tests/utf8test": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "names": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "test_utf8": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "simple": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "tests/base64test": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "echo": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "tests/mantest": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "testc": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "test_syntax": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "test_back": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "bug_fix": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "tests/jqtest": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "scan": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "tests/shtest": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "encode": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "callout": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "listcap": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "tests/optionaltest": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "user_property": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "test_regset": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "testcu": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "count": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "syntax": {"run": "PASS", "test": "PASS", "fix": "PASS"}, "sql": {"run": "PASS", "test": "PASS", "fix": "PASS"}}
{"tests/onigtest": {"run": "PASS", "test": "FAIL", "fix": "PASS"}}
{"passed_count": 28, "failed_count": 0, "skipped_count": 0, "passed_tests": ["regset", "callback_each_match", "names", "test_utf8", "testc", "test_syntax", "sql", "bug_fix", "scan", "tests/onigtest", "encode", "listcap", "tests/optionaltest", "test_regset", "testcu", "count", "syntax", "test_options", "tests/utf8test", "simple", "tests/base64test", "tests/mantest", "test_back", "tests/jqtest", "tests/shtest", "callout", "user_property", "echo"], "failed_tests": [], "skipped_tests": []}
{"passed_count": 27, "failed_count": 1, "skipped_count": 0, "passed_tests": ["regset", "callback_each_match", "names", "test_utf8", "testc", "test_syntax", "sql", "bug_fix", "scan", "encode", "listcap", "tests/optionaltest", "test_regset", "testcu", "count", "syntax", "test_options", "tests/utf8test", "simple", "tests/base64test", "tests/mantest", "test_back", "tests/jqtest", "tests/shtest", "callout", "user_property", "echo"], "failed_tests": ["tests/onigtest"], "skipped_tests": []}
{"passed_count": 28, "failed_count": 0, "skipped_count": 0, "passed_tests": ["regset", "callback_each_match", "names", "test_utf8", "testc", "test_syntax", "sql", "bug_fix", "scan", "tests/onigtest", "encode", "listcap", "tests/optionaltest", "test_regset", "testcu", "count", "syntax", "test_options", "tests/utf8test", "simple", "tests/base64test", "tests/mantest", "test_back", "tests/jqtest", "tests/shtest", "callout", "user_property", "echo"], "failed_tests": [], "skipped_tests": []}