Add until(cond; next); fix #639

3 files changed, 26 insertions, 0 deletions

diff --git a/builtin.c b/builtin.c
index 0629ca99..dc355353 100644
--- a/builtin.c
+++ b/builtin.c
@@ -1090,6 +1090,10 @@ static const char* const jq_builtins[] = {
   "     def _while: "
   "         if cond then ., (update | _while) else empty end; "
   "     try _while catch if .==\"break\" then empty else . end;",
+  "def until(cond; next): "
+  "     def _until: "
+  "         if cond then . else (next|_until) end;"
+  "     _until;",
   "def limit($n; exp): if $n < 0 then exp else foreach exp as $item ([$n, null]; if .[0] < 1 then break else [.[0] -1, $item] end; .[1]) end;",
   "def first(g): foreach g as $item ([false, null]; if .[0]==true then break else [true, $item] end; .[1]);",
   "def last(g): reduce g as $item (null; $item);",
diff --git a/docs/content/3.manual/manual.yml b/docs/content/3.manual/manual.yml
index ea0514ed..42c6c98c 100644
--- a/docs/content/3.manual/manual.yml
+++ b/docs/content/3.manual/manual.yml
@@ -1270,6 +1270,24 @@ sections:
             input: '1'
             output: ['[1,2,4,8,16,32,64]']
 
+      - title: "`until(cond; next)`"
+        body: |
+
+          The `until(cond; next)` function allows you to repeatedly
+          apply the expression `next`, initially to `.` then to its own
+          output, until `cond` is true.  For example, this can be used
+          to implement a factorial function (see below).
+
+          Note that `until(cond; next)` is internally defined as a
+          recursive jq function.  Recursive calls within `until()` will
+          not consume additional memory if `next` produces at most one
+          output for each input.  See advanced topics below.
+
+        examples:
+          - program: '[.,1]|until(.[0] < 1; [.[0] - 1, .[1] * .[0]])|.[1]'
+            input: '4'
+            output: ['24']
+
 
       - title: "`recurse(f)`, `recurse`, `recurse(f; condition)`, `recurse_down`"
         body: |
diff --git a/tests/all.test b/tests/all.test
index c4c3b0df..8d27d331 100644
--- a/tests/all.test
+++ b/tests/all.test
@@ -250,6 +250,10 @@ null
 1
 [1,2,4,8]
 
+[.[]|[.,1]|until(.[0] < 1; [.[0] - 1, .[1] * .[0]])|.[1]]
+[1,2,3,4,5]
+[1,2,6,24,120]
+
 [foreach .[] as $item ([3, null]; if .[0] < 1 then break else [.[0] -1, $item] end; .[1])]
 [11,22,33,44,55,66,77,88,99]
 [11,22,33]