diff options
author | Nicolas Williams <nico@cryptonector.com> | 2021-10-21 00:15:12 -0500 |
---|---|---|
committer | Nicolas Williams <nico@cryptonector.com> | 2021-10-24 16:23:26 -0500 |
commit | 0c3455d3290fa03da8c01c135dd7126a80ed28a8 (patch) | |
tree | 2afb78228b16aaf0d28d5118edb8daab3b79234b | |
parent | 1a1804afcb88cdc3f1f0e74e83385146b55ae205 (diff) | |
download | jq-0c3455d3290fa03da8c01c135dd7126a80ed28a8.tar.gz |
Fix accidentally quadratic behavior in setpath
We need to be careful to not grab an extra reference when mutating
data structures because that means we make extra copies. Doing that
every time in `jv_setpath()` is really painful, as that function is used
in `_modify/2`, which is used in `|=` and all modify-assign operators.
`_modify` also grabs additional references, so this is not the only fix
needed for the modify-assign operators to not be accidentally quadratic.
-rw-r--r-- | src/jv_aux.c | 32 |
1 files changed, 30 insertions, 2 deletions
diff --git a/src/jv_aux.c b/src/jv_aux.c index eca2345..994285a 100644 --- a/src/jv_aux.c +++ b/src/jv_aux.c @@ -351,8 +351,36 @@ jv jv_setpath(jv root, jv path, jv value) { } jv pathcurr = jv_array_get(jv_copy(path), 0); jv pathrest = jv_array_slice(path, 1, jv_array_length(jv_copy(path))); - return jv_set(root, pathcurr, - jv_setpath(jv_get(jv_copy(root), jv_copy(pathcurr)), pathrest, value)); + + /* + * We need to be careful not to make extra copies since that leads to + * quadratic behavior (e.g., when growing large data structures in a + * reduction with `setpath/2`, i.e., with `|=`. + */ + if (jv_get_kind(pathcurr) == JV_KIND_OBJECT) { + // Assignment to slice -- dunno yet how to avoid the extra copy + return jv_set(root, pathcurr, + jv_setpath(jv_get(jv_copy(root), jv_copy(pathcurr)), pathrest, value)); + } + + jv subroot = jv_get(jv_copy(root), jv_copy(pathcurr)); + if (!jv_is_valid(subroot)) { + jv_free(pathcurr); + jv_free(pathrest); + jv_free(value); + return subroot; + } + + // To avoid the extra copy we drop the reference from `root` by setting that + // to null first. + root = jv_set(root, jv_copy(pathcurr), jv_null()); + if (!jv_is_valid(root)) { + jv_free(pathcurr); + jv_free(pathrest); + jv_free(value); + return root; + } + return jv_set(root, pathcurr, jv_setpath(subroot, pathrest, value)); } jv jv_getpath(jv root, jv path) { |