From bc42812715fb56e72717bf18809dd9ba59771b3a Mon Sep 17 00:00:00 2001 From: Stephen Dolan Date: Thu, 16 May 2013 15:07:53 +0100 Subject: Remove the insane "fold" operation, replace with saner "reduce". --- builtin.c | 6 +++--- compile.c | 23 ++++++++++++++++------- compile.h | 2 +- docs/content/3.manual/manual.yml | 34 ++++++++++++---------------------- lexer.l | 2 +- parser.y | 6 +++--- tests/all.test | 2 +- 7 files changed, 37 insertions(+), 38 deletions(-) diff --git a/builtin.c b/builtin.c index 48d71109..071cb564 100644 --- a/builtin.c +++ b/builtin.c @@ -554,10 +554,10 @@ static const char* const jq_builtins[] = { "def unique: group_by(.) | map(.[0]);", "def max_by(f): _max_by_impl(map([f]));", "def min_by(f): _min_by_impl(map([f]));", - "def add: fold null as $sum (.[] | $sum + .);", + "def add: reduce .[] as $x (null; . + $x);", "def del(f): delpaths([path(f)]);", - "def _assign(paths; value): value as $v | fold . as $obj (path(paths) as $p | $obj | setpath($p; $v));", - "def _modify(paths; update): fold . as $obj (path(paths) as $p | $obj | setpath($p; getpath($p) | update));", + "def _assign(paths; value): value as $v | reduce path(paths) as $p (.; setpath($p; $v));", + "def _modify(paths; update): reduce path(paths) as $p (.; setpath($p; getpath($p) | update));", "def recurse(f): ., (f | select(. != null) | recurse(f));", "def to_entries: [keys[] as $k | {key: $k, value: .[$k]}];", "def from_entries: map({(.key): .value}) | add;", diff --git a/compile.c b/compile.c index 1f8be905..95cd59e5 100644 --- a/compile.c +++ b/compile.c @@ -320,15 +320,24 @@ block gen_collect(block expr) { gen_op_var_bound(LOADV, array_var)); } -block gen_fold(const char* varname, block init, block fold) { - block loop = BLOCK(fold, gen_op_var_unbound(STOREV, varname), gen_op_simple(BACKTRACK)); +block gen_reduce(const char* varname, block source, block init, block body) { + block res_var = block_bind(gen_op_var_unbound(STOREV, "reduce"), + gen_noop(), OP_HAS_VARIABLE); + + block loop = BLOCK(gen_op_simple(DUP), + source, + block_bind(gen_op_var_unbound(STOREV, varname), + BLOCK(gen_op_var_bound(LOADVN, res_var), + body, + gen_op_var_bound(STOREV, res_var)), + OP_HAS_VARIABLE), + gen_op_simple(BACKTRACK)); return BLOCK(gen_op_simple(DUP), init, - block_bind(gen_op_var_unbound(STOREV, varname), - BLOCK(gen_op_target(FORK, loop), - loop, - gen_op_var_unbound(LOADV, varname)), - OP_HAS_VARIABLE)); + res_var, + gen_op_target(FORK, loop), + loop, + gen_op_var_bound(LOADVN, res_var)); } block gen_definedor(block a, block b) { diff --git a/compile.h b/compile.h index f3f70b44..152384a7 100644 --- a/compile.h +++ b/compile.h @@ -34,7 +34,7 @@ block gen_call(const char* name, block body); block gen_subexp(block a); block gen_both(block a, block b); block gen_collect(block expr); -block gen_fold(const char* varname, block init, block body); +block gen_reduce(const char* varname, block source, block init, block body); block gen_definedor(block a, block b); block gen_condbranch(block iftrue, block iffalse); block gen_and(block a, block b); diff --git a/docs/content/3.manual/manual.yml b/docs/content/3.manual/manual.yml index 7038b5fc..9b8a7b4a 100644 --- a/docs/content/3.manual/manual.yml +++ b/docs/content/3.manual/manual.yml @@ -1016,7 +1016,7 @@ sections: (many jq functions such as `map` and `find` are in fact written in jq). - Finally, jq has a `fold` operation, which is very powerful but a + Finally, jq has a `reduce` operation, which is very powerful but a bit tricky. Again, it's mostly used internally, to define some useful bits of jq's standard library. @@ -1126,36 +1126,26 @@ sections: input: '[[1,2],[10,20]]' output: ['[[1,2,1,2], [10,20,1,2]]'] - - title: Fold + - title: Reduce body: | - The `fold` syntax in jq allows you to combine all of the + The `reduce` syntax in jq allows you to combine all of the results of an expression by accumulating them into a single answer. As an example, we'll pass `[3,2,1]` to this expression: - fold 0 as $sum (.[] | $sum + .) + reduce .[] as $item (0; . + $item) - The variable `$sum` is first given the value `0`. The body - of the fold (i.e. `.[] | $sum + .`) is evaluated. `.[]` - produces three results, `3`, `2`, and `1`. For the first - one, `$sum + .` gives `3`. + For each result that `.[]` produces, `. + $item` is run to + accumulate a running total, starting from 0. In this + example, `.[]` produces the results 3, 2, and 1, so the + effect is similar to running something like this: - Having produced this answer, jq backtracks to find the next - result as per usual. However, this time, `$sum` is set to - the previous value of the body, so `$sum + .` gives - `5`. After the final backtracking, `$sum + .` gives - `6`. This final value is used as the value of the entire - `fold` expression, so the above filter returns `6`. - - More formally, in order to evaluate `fold INIT as $VAR - (BODY)`, jq first sets `$VAR` to the value of `INIT`. It - then runs through `BODY`. Each time `BODY` produces a value, - `$VAR` is set to that value and jq backtracks to find the - next one. When `BODY` stops producing values, the final - value of `$VAR` is the result of the entire expression. + 0 | (3 as $item | . + $item) | + (2 as $item | . + $item) | + (1 as $item | . + $item) examples: - - program: 'fold 0 as $sum (.[] | $sum + .)' + - program: 'reduce .[] as $item (0; . + $item)' input: '[10,2,5,3]' output: ['20'] diff --git a/lexer.l b/lexer.l index 59e527db..3000bafa 100644 --- a/lexer.l +++ b/lexer.l @@ -49,7 +49,7 @@ struct lexer_param; "and" { return AND; } "or" { return OR; } "end" { return END; } -"fold" { return FOLD; } +"reduce" { return REDUCE; } "//" { return DEFINEDOR; } "|=" { return SETPIPE; } "+=" { return SETPLUS; } diff --git a/parser.y b/parser.y index 592a428b..bc703e92 100644 --- a/parser.y +++ b/parser.y @@ -58,7 +58,7 @@ struct lexer_param; %token THEN "then" %token ELSE "else" %token ELSE_IF "elif" -%token FOLD "fold" +%token REDUCE "reduce" %token END "end" %token AND "and" %token OR "or" @@ -226,8 +226,8 @@ Term "as" '$' IDENT '|' Exp { jv_free($4); } | -"fold" Term "as" '$' IDENT '(' Exp ')' { - $$ = gen_fold(jv_string_value($5), $2, $7); +"reduce" Term "as" '$' IDENT '(' Exp ';' Exp ')' { + $$ = gen_reduce(jv_string_value($5), $2, $7, $9); jv_free($5); } | diff --git a/tests/all.test b/tests/all.test index 90ab7db7..cc97961f 100644 --- a/tests/all.test +++ b/tests/all.test @@ -379,7 +379,7 @@ def fac: if . == 1 then 1 else . * (. - 1 | fac) end; [.[] | fac] # [] # 1001 -fold 0 as $s (.[] | $s + .) +reduce .[] as $x (0; . + $x) [1,2,4] 7 -- cgit v1.2.3