std.prune causes max stack frames exceeded error

[redbaron]

Following case works fine without std.prune, but fails when pruning:

local d = { isD: true, f: 42 };
local mkN(d) = { isD: false, z: d.f };

local items = [d, mkN(d)];

local mapN = function(d, n) n + { z: d.f + d.f };

local comp = {
  getD:: [i for i in self.items if i.isD ][0],
  items: items,
};

local res = { abc: comp } + { abc+: {
  local d = self.getD,
  items: [if i.isD then i else mapN(d, i) for i in super.items]
}};

// local f = function(x) x;  // no prune works
local f = std.prune;

{ [key]: res[key] + { items: std.map(f, super.items) } for key in std.objectFields(res) }

[redbaron]

If I change last line to

{ [key]: res[key] + { items: std.map(f, res[key].items) } for key in std.objectFields(res) }

it works

[sparkprime]

Whittled it down a bit more:

abc { items: [(super.items[0])] }
local abc = {
  getD:: [i for i in self.items if i.isD ][0],
  items: [{ isD: true, f: 42 }, { isD: false, z: 42 }],
} + {
  items: [if i.isD then i else local s = self; i + { z: s.getD.f + s.getD.f } for i in super.items]
};

// local f = function(x) x;  // no prune works
local f = std.prune;

abc + { items: std.map(f, super.items) }

[sparkprime]

And a bit more:

local abc = {
  local s = self,
  getD:: [i for i in self.items if i.isD ][0],
  items: [
    { isD: true, f: 42 },
    { isD: false, z: s.getD.f + s.getD.f }
  ],
};

// local f = function(x) x;  // no prune works
local f = std.prune;

abc + { items: std.map(f, super.items) }

[sparkprime]

There is definitely a circular reference here - items is defined in terms of getD and getD in terms of items. It's probably a harmless one, but maybe std.prune is more aggressive at evaluating things it does not need to evaluate. I'm still looking into it.

[sparkprime]

Ok, it's to do with lazy arrays and std.prune forcing all elements. The simplest example is:

jsonnet -e 'std.prune([0, 1, error "too many"])[0]'

vs

jsonnet -e '[0, 1, error "too many"][0]'

The former has to step over all elements of the array to remove the nulls from it.

[sparkprime]

In your case, you have an array where the later elements depend on the former elements, so pruning that array forces all elements and creates the infinite loop.

[sparkprime]

You can also break the cycle by changing the last line to copy rather than override the items:

{
  [key]: {
    { items: std.map(f, res[key].items) }
  }
  for key in std.objectFields(res)
}

[redbaron]

In your case, you have an array where the later elements depend on the former elements, so pruning that array forces all elements and creates the infinite loop.

Example with error "to many" can't produce valid output, but in my case, omitting std.prune allows jsonnet to produce output. does it mean that prune can't be done as a library func?

[redbaron]

You can also break the cycle by changing the last line to copy rather than override the items:

this is not like for like , in original case there are more fields than just .items and they need to be preserved.

[sparkprime]

It's not possible to create a self-referential array that can be pruned, however prune is implemented, because you have to evaluate every element to see if it is null or not.

[sparkprime]

A closer example would be std.prune(local arr = [1, arr[1]]; arr)

[sparkprime]

Actually it's more like local arr = [1, arr[1]]; std.prune(arr)[0]

[redbaron]

A closer example would be std.prune(local arr = [1, arr[1]]; arr)

this exceeds max stack frames with or without prune

Actually it's more like local arr = [1, std.prune(arr)[1]]; arr[0]

this works with or without prune :)

[sparkprime]

yes I updated it :)

[sparkprime]

The cycle in your case is more complicated than that though. Let me look a bit deeper.

[redbaron]

I still don't see how mini examples are similar to slimmed down example of my case your provided earlier. My case doesn't pick elements, yet it managed to print all fields and all objects just fine, but pruning sends it into infinite loop

[sparkprime]

You're not actually pruning an array at any point, you only ever prune objects, and those objects don't contain an array. So my explanation of this is probably wrong.

[redbaron]

I would assume that printing final json works exactly like object comprehension: iterating over each key and looking up value of that key, but seems that evaluation rules are subtly different.

[sparkprime]

std.toString() causes the same problem as std.prune()

[sparkprime]

This is what I'm poking at now:

local abc = {
  local s = self,
  getD:: [i for i in self.items if i.isD][0],
  items: [
    { isD: true, f: 42 },
    { isD: false, z: s.getD.f }
  ],
};

(abc + { items: [super.items[0], std.prune(super.items[1])] })

[redbaron]

~Another workaround:~ doesn't really work when changing order of elements in abc.items and making getD iterate over whole array as a result

local first(lst, t) =
  if lst == [] then null else
    if t(lst[0]) then lst[0] else first(std.slice(lst,1, std.length(lst),1),t);

local abc = {
  local s = self,
  getD:: first(self.items, function(i) i.isD),
  items: [
    { isD: true, f: 42 },
    { isD: false, z: s.getD.f }
  ],
};
(abc + { items: [super.items[0], std.prune(super.items[1])] })

[sparkprime]

Now I think it might be more fundamental:

dcunnin@casterly:~$ jsonnet -e '[x for x in [1, 2, error "foo"]][0]'
1
dcunnin@casterly:~$ jsonnet -e '[x for x in [1, 2, error "foo"] if x > 0][0]'
RUNTIME ERROR: foo
        <cmdline>:1:20-31       thunk <x>
        <cmdline>:1:36  function <$aux_0>
        <cmdline>:1:2

[sparkprime]

Ok there is a cycle, but it is hard to see because there are 2 places where a dependency occurs and you might not expect it. The first is that [i for i in self.items if i.isD][0] evaluates i[1] even if i[0].isD. I need to check the spec to see if that is correct. The second is a similar case (inside prune) where an if is used in an object comprehension https://github.com/google/jsonnet/blob/master/stdlib/std.jsonnet#L1222

[sparkprime]

The spec agrees with that behavior. A simple explanation as to why [0, error "foo"] is OK but [x for x in [0, error "foo"] if x > 0] is not, is that the former can have a std.length() of 2 whereas it's not possible to compute the length of the latter without tripping the error.

[sparkprime]

In your case the "error" is non-termination due to infinite recursion but the argument is the same. Basically, std.prune() is adding one more dependency that is completing your cycle, and that's unavoidable.

[sparkprime]

By the way if you replace the last line with std.prune(res) it will work.

[sparkprime]

Or { [key]: std.prune(res[key]) for key in std.objectFields(res) }

[redbaron]

std.toString() causes the same problem as std.prune()

~I was talking about "printing" as in jsonnet prints final result to console. to generate that very sequence of symbols, I'd imagine it need to do internally something very similar to what std.prune is doing: iterate over all keys and fields and recursively "print" them. What I can't understand is why "printing" iteration doesn't cause infinite loop, but prunning does~

OK I see, std.prune doesn't just iterate over fields, it also changes what is evaluated and what is not.

[sparkprime]

Ok we got to the bottom of it. I think the best advice I can give you is to simplify your code. Maybe something like this:

local getD(items) = [i for i in items if i.isD][0];

local abc = {
  local s = self,
  itemsWithoutZ:: [
    { isD: true, f: 42 },
    { isD: false }
  ],
  items: [
    if i.isD then
        i
    else
        i { z: getD(s.itemsWithoutZ) }
    for i in self.itemsWithoutZ
  ],
};

(abc + { items: std.map(std.prune, super.items) })

[redbaron]

Thanks for your help and clarification.