"def halt_error: halt_error(5);\n"
"def error(msg): msg|error;\n"
"def map(f): [.[] | f];\n"
"def select(f): if f then . else empty end;\n"
"def sort_by(f): _sort_by_impl(map([f]));\n"
"def group_by(f): _group_by_impl(map([f]));\n"
"def unique: group_by(.) | map(.[0]);\n"
"def unique_by(f): group_by(f) | map(.[0]);\n"
"def max_by(f): _max_by_impl(map([f]));\n"
"def min_by(f): _min_by_impl(map([f]));\n"
"def add: reduce .[] as $x (null; . + $x);\n"
"def del(f): delpaths([path(f)]);\n"
"def abs: if . < 0 then - . else . end;\n"
"def _assign(paths; $value): reduce path(paths) as $p (.; setpath($p; $value));\n"
"def _modify(paths; update):\n"
"    reduce path(paths) as $p ([., []];\n"
"        . as $dot\n"
"      | null\n"
"      | label $out\n"
"      | ($dot[0] | getpath($p)) as $v\n"
"      | (\n"
"          (   $$$$v\n"
"            | update\n"
"            | (., break $out) as $v\n"
"            | $$$$dot\n"
"            | setpath([0] + $p; $v)\n"
"          ),\n"
"          (\n"
"              $$$$dot\n"
"            | setpath([1, (.[1] | length)]; $p)\n"
"          )\n"
"        )\n"
"    ) | . as $dot | $dot[0] | delpaths($dot[1]);\n"
"def map_values(f): .[] |= f;\n"
"\n"
"# recurse\n"
"def recurse(f): def r: ., (f | r); r;\n"
"def recurse(f; cond): def r: ., (f | select(cond) | r); r;\n"
"def recurse: recurse(.[]?);\n"
"\n"
"def to_entries: [keys_unsorted[] as $k | {key: $k, value: .[$k]}];\n"
"def from_entries: map({(.key // .Key // .name // .Name): (if has(\"value\") then .value else .Value end)}) | add | .//={};\n"
"def with_entries(f): to_entries | map(f) | from_entries;\n"
"def reverse: [.[length - 1 - range(0;length)]];\n"
"def indices($i): if type == \"array\" and ($i|type) == \"array\" then .[$i]\n"
"  elif type == \"array\" then .[[$i]]\n"
"  elif type == \"string\" and ($i|type) == \"string\" then _strindices($i)\n"
"  else .[$i] end;\n"
"def index($i):   indices($i) | .[0];       # TODO: optimize\n"
"def rindex($i):  indices($i) | .[-1:][0];  # TODO: optimize\n"
"def paths: path(recurse)|select(length > 0);\n"
"def paths(node_filter): path(recurse|select(node_filter))|select(length > 0);\n"
"def isfinite: type == \"number\" and (isinfinite | not);\n"
"def arrays: select(type == \"array\");\n"
"def objects: select(type == \"object\");\n"
"def iterables: select(type|. == \"array\" or . == \"object\");\n"
"def booleans: select(type == \"boolean\");\n"
"def numbers: select(type == \"number\");\n"
"def normals: select(isnormal);\n"
"def finites: select(isfinite);\n"
"def strings: select(type == \"string\");\n"
"def nulls: select(. == null);\n"
"def values: select(. != null);\n"
"def scalars: select(type|. != \"array\" and . != \"object\");\n"
"def join($x): reduce .[] as $i (null;\n"
"            (if .==null then \"\" else .+$x end) +\n"
"            ($i | if type==\"boolean\" or type==\"number\" then tostring else .//\"\" end)\n"
"        ) // \"\";\n"
"def _flatten($x): reduce .[] as $i ([]; if $i | type == \"array\" and $x != 0 then . + ($i | _flatten($x-1)) else . + [$i] end);\n"
"def flatten($x): if $x < 0 then error(\"flatten depth must not be negative\") else _flatten($x) end;\n"
"def flatten: _flatten(-1);\n"
"def range($x): range(0;$x);\n"
"def fromdateiso8601: strptime(\"%Y-%m-%dT%H:%M:%SZ\")|mktime;\n"
"def todateiso8601: strftime(\"%Y-%m-%dT%H:%M:%SZ\");\n"
"def fromdate: fromdateiso8601;\n"
"def todate: todateiso8601;\n"
"def match(re; mode): _match_impl(re; mode; false)|.[];\n"
"def match($val): ($val|type) as $vt | if $vt == \"string\" then match($val; null)\n"
"   elif $vt == \"array\" and ($val | length) > 1 then match($val[0]; $val[1])\n"
"   elif $vt == \"array\" and ($val | length) > 0 then match($val[0]; null)\n"
"   else error( $vt + \" not a string or array\") end;\n"
"def test(re; mode): _match_impl(re; mode; true);\n"
"def test($val): ($val|type) as $vt | if $vt == \"string\" then test($val; null)\n"
"   elif $vt == \"array\" and ($val | length) > 1 then test($val[0]; $val[1])\n"
"   elif $vt == \"array\" and ($val | length) > 0 then test($val[0]; null)\n"
"   else error( $vt + \" not a string or array\") end;\n"
"def capture(re; mods): match(re; mods) | reduce ( .captures | .[] | select(.name != null) | { (.name) : .string } ) as $pair ({}; . + $pair);\n"
"def capture($val): ($val|type) as $vt | if $vt == \"string\" then capture($val; null)\n"
"   elif $vt == \"array\" and ($val | length) > 1 then capture($val[0]; $val[1])\n"
"   elif $vt == \"array\" and ($val | length) > 0 then capture($val[0]; null)\n"
"   else error( $vt + \" not a string or array\") end;\n"
"def scan($re; $flags):\n"
"  match($re; \"g\" + $flags)\n"
"    | if (.captures|length > 0)\n"
"      then [ .captures | .[] | .string ]\n"
"      else .string\n"
"      end;\n"
"def scan($re): scan($re; null);\n"
"#\n"
"# If input is an array, then emit a stream of successive subarrays of length n (or less),\n"
"# and similarly for strings.\n"
"def _nwise($n):\n"
"  def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;\n"
"  n;\n"
"def _nwise(a; $n): a | _nwise($n);\n"
"#\n"
"# splits/1 produces a stream; split/1 is retained for backward compatibility.\n"
"def splits($re; flags): . as $s\n"
"#  # multiple occurrences of \"g\" are acceptable\n"
"  | [ match($re; \"g\" + flags) | (.offset, .offset + .length) ]\n"
"  | [0] + . +[$s|length]\n"
"  | _nwise(2)\n"
"  | $s[.[0]:.[1] ] ;\n"
"def splits($re): splits($re; null);\n"
"#\n"
"# split emits an array for backward compatibility\n"
"def split($re; flags): [ splits($re; flags) ];\n"
"#\n"
"# If s contains capture variables, then create a capture object and pipe it to s, bearing\n"
"# in mind that s could be a stream\n"
"def sub($re; s; $flags):\n"
"   . as $in\n"
"   | (reduce match($re; $flags) as $edit\n"
"        ({result: [], previous: 0};\n"
"            $in[ .previous: ($edit | .offset) ] as $gap\n"
"            # create the \"capture\" objects (one per item in s)\n"
"            | [reduce ( $edit | .captures | .[] | select(.name != null) | { (.name) : .string } ) as $pair\n"
"                 ({}; . + $pair) | s ] as $inserts\n"
"            | reduce range(0; $inserts|length) as $ix (.; .result[$ix] += $gap + $inserts[$ix])\n"
"            | .previous = ($edit | .offset + .length ) )\n"
"          | .result[] + $in[.previous:] )\n"
"      // $in;\n"
"#\n"
"def sub($re; s): sub($re; s; \"\");\n"
"#\n"
"def gsub($re; s; flags): sub($re; s; flags + \"g\");\n"
"def gsub($re; s): sub($re; s; \"g\");\n"
"#\n"
"########################################################################\n"
"# generic iterator/generator\n"
"def while(cond; update):\n"
"     def _while:\n"
"         if cond then ., (update | _while) else empty end;\n"
"     _while;\n"
"def until(cond; next):\n"
"     def _until:\n"
"         if cond then . else (next|_until) end;\n"
"     _until;\n"
"def limit($n; exp):\n"
"    if $n > 0 then label $out | foreach exp as $item ($n; .-1; $item, if . <= 0 then break $out else empty end)\n"
"    elif $n == 0 then empty\n"
"    else exp end;\n"
"# range/3, with a `by` expression argument\n"
"def range($init; $upto; $by):\n"
"    if $by > 0 then $init|while(. < $upto; . + $by)\n"
"  elif $by < 0 then $init|while(. > $upto; . + $by)\n"
"  else empty end;\n"
"def first(g): label $out | g | ., break $out;\n"
"def isempty(g): first((g|false), true);\n"
"def all(generator; condition): isempty(generator|condition and empty);\n"
"def any(generator; condition): isempty(generator|condition or empty)|not;\n"
"def all(condition): all(.[]; condition);\n"
"def any(condition): any(.[]; condition);\n"
"def all: all(.[]; .);\n"
"def any: any(.[]; .);\n"
"def last(g): reduce g as $item (null; $item);\n"
"def nth($n; g):\n"
"  if $n < 0 then error(\"nth doesn't support negative indices\")\n"
"  else label $out | foreach g as $item ($n + 1; . - 1; if . <= 0 then $item, break $out else empty end) end;\n"
"def first: .[0];\n"
"def last: .[-1];\n"
"def nth($n): .[$n];\n"
"def combinations:\n"
"    if length == 0 then [] else\n"
"        .[0][] as $x\n"
"          | (.[1:] | combinations) as $y\n"
"          | [$x] + $y\n"
"    end;\n"
"def combinations(n):\n"
"    . as $dot\n"
"      | [range(n) | $dot]\n"
"      | combinations;\n"
"# transpose a possibly jagged matrix, quickly;\n"
"# rows are padded with nulls so the result is always rectangular.\n"
"def transpose: [range(0; map(length)|max // 0) as $i | [.[][$i]]];\n"
"def in(xs): . as $x | xs | has($x);\n"
"def inside(xs): . as $x | xs | contains($x);\n"
"def repeat(exp):\n"
"     def _repeat:\n"
"         exp, _repeat;\n"
"     _repeat;\n"
"def inputs: try repeat(input) catch if .==\"break\" then empty else error end;\n"
"# like ruby's downcase - only characters A to Z are affected\n"
"def ascii_downcase:\n"
"  explode | map( if 65 <= . and . <= 90 then . + 32  else . end) | implode;\n"
"# like ruby's upcase - only characters a to z are affected\n"
"def ascii_upcase:\n"
"  explode | map( if 97 <= . and . <= 122 then . - 32  else . end) | implode;\n"
"\n"
"# Streaming utilities\n"
"def truncate_stream(stream):\n"
"  . as $n | null | stream | . as $input | if (.[0]|length) > $n then setpath([0];$input[0][$n:]) else empty end;\n"
"def fromstream(i): {x: null, e: false} as $init |\n"
"  # .x = object being built; .e = emit and reset state\n"
"  foreach i as $i ($init\n"
"  ; if .e then $init else . end\n"
"  | if $i|length == 2\n"
"    then setpath([\"e\"]; $i[0]|length==0) | setpath([\"x\"]+$i[0]; $i[1])\n"
"    else setpath([\"e\"]; $i[0]|length==1) end\n"
"  ; if .e then .x else empty end);\n"
"def tostream:\n"
"  path(def r: (.[]?|r), .; r) as $p |\n"
"  getpath($p) |\n"
"  reduce path(.[]?) as $q ([$p, .]; [$p+$q]);\n"
"\n"
"# Assuming the input array is sorted, bsearch/1 returns\n"
"# the index of the target if the target is in the input array; and otherwise\n"
"#  (-1 - ix), where ix is the insertion point that would leave the array sorted.\n"
"# If the input is not sorted, bsearch will terminate but with irrelevant results.\n"
"def bsearch($target):\n"
"  if length == 0 then -1\n"
"  elif length == 1 then\n"
"     if $target == .[0] then 0 elif $target < .[0] then -1 else -2 end\n"
"  else . as $in\n"
"    # state variable: [start, end, answer]\n"
"    # where start and end are the upper and lower offsets to use.\n"
"    | [0, length-1, null]\n"
"    | until( .[0] > .[1] ;\n"
"             if .[2] != null then (.[1] = -1)               # i.e. break\n"
"             else\n"
"               ( ( (.[1] + .[0]) / 2 ) | floor ) as $mid\n"
"               | $in[$mid] as $monkey\n"
"               | if $monkey == $target  then (.[2] = $mid)   # success\n"
"                 elif .[0] == .[1]     then (.[1] = -1)     # failure\n"
"                 elif $monkey < $target then (.[0] = ($mid + 1))\n"
"                 else (.[1] = ($mid - 1))\n"
"                 end\n"
"             end )\n"
"    | if .[2] == null then          # compute the insertion point\n"
"         if $in[ .[0] ] < $target then (-2 -.[0])\n"
"         else (-1 -.[0])\n"
"         end\n"
"      else .[2]\n"
"      end\n"
"  end;\n"
"\n"
"# Apply f to composite entities recursively, and to atoms\n"
"def walk(f):\n"
"  def w:\n"
"    if type == \"object\"\n"
"    then map_values(w)\n"
"    elif type == \"array\" then map(w)\n"
"    else .\n"
"    end\n"
"    | f;\n"
"  w;\n"
"\n"
"# pathexps could be a stream of dot-paths\n"
"def pick(pathexps):\n"
"  . as $in\n"
"  | reduce path(pathexps) as $a (null;\n"
"      setpath($a; $in|getpath($a)) );\n"
"\n"
"# ensure the output of debug(m1,m2) is kept together:\n"
"def debug(msgs): (msgs | debug | empty), .;\n"
"\n"
"# SQL-ish operators here:\n"
"def INDEX(stream; idx_expr):\n"
"  reduce stream as $row ({}; .[$row|idx_expr|tostring] = $row);\n"
"def INDEX(idx_expr): INDEX(.[]; idx_expr);\n"
"def JOIN($idx; idx_expr):\n"
"  [.[] | [., $idx[idx_expr]]];\n"
"def JOIN($idx; stream; idx_expr):\n"
"  stream | [., $idx[idx_expr]];\n"
"def JOIN($idx; stream; idx_expr; join_expr):\n"
"  stream | [., $idx[idx_expr]] | join_expr;\n"
"def IN(s): any(s == .; .);\n"
"def IN(src; s): any(src == s; .);\n"