setIn() for numerical indexes fails on empty lists

[ariesshrimp]

I'd like to better understand the intended behavior of setIn() regarding integers used in the set path.

This is from @axefrog on #55

When the path does not match what exists already, what exists should be replaced with the best collection type for the path element type (a string would suggest a map key, whereas a number would suggest a list index, unless there is already a map at that location).

Consider this example:

setIn(
  ['a', 0],         // at: input.a[0]
  true,             // set: true
  from({a: []})     // for: {a:[]} ❌
); 
// expected result: from({ a: [true] }) 

This use of a numerical index throws the following error:

     Error: Index -1 is out of range
      at Object.setValueAtOrdinal 
(node_modules/@collectable/list/lib/commonjs/internals/values.js:15:15)

It looks like this is because the intended path violates a safeguards against setting values at indexes beyond the length of the list. For example:

setIn(
  ['a', 9],         // at: input.a[9]
  true,             // set: true
  from({a: []})     // for: { a: [] } ❌
); 
// what is this supposed to do? what goes in the first 8 indexes? 
// undefined? just crash

This has several implications:

1. You cannot set the last value of a list (that seems problematic). Solution: change the safeguard logic.
2. You cannot have arrays in the path of a deep setIn(), like so:

setIn(
  ['a', 0, 'b', 0, 'c'], // at: input.a[0].b[0].c
  true,                  // set: true
  from({a: []})          // for: {a:[]}
); 
// expected: from({ a: [ { b: [ { c: true} ]}]}) ❌

I'm not sure if [2] is confusing or not. I'm not sure whether people would want to do that or not. This comment from @axefrog suggests that something like that is desirable though. Maybe all that it means is that existing lists and indexes along the path should be settable, but not dynamically filled in where missing.

setIn() seems to work just as expected for existing lists and indexes:

setIn(
  ['a', 0, 'b', 4, 'c'],              // at: input.a[0].b[4].c
  true,                               // set: true
  from({ a: [ { b: [ 0, 1, 2, 3 ]}]}) // for: { a: [ { b: [ 0, 1, 2, 3 ]}]}
); 
// expected: from({ a: [ { b: [ 0, 1, 2, 3, { c: true} ]}]}) 👌🏻

[axefrog]

Solution: change the safeguard logic.

I'd agree with that. The safeguard logic should allow index n to pass validation and defer its resolution to the normal code path for appending values.

[ariesshrimp]

I'm guessing that in

function verifyIndex(size: number, index: number): number {
  index = normalizeIndex(size, index);
  return index === size ? -1 : index;
}

What we really want is index > size ? -1 : index

[axefrog]

Hey, sorry about the slow reply. Disappeared off my notifications list and then forgot it was here. Feel free to bump an issue if I'm ever slow to reply, or jump on Gitter and ping me (@axefrog). Same on Hangouts if you want to ping me directly.

Sounds about right, I guess. Only hesitation is that if a person has, for example, a list of length 3, then tries to set the value of index 7, the change you suggest would suggest insertion at index [3], which may not be what they expected, and feels wrong to me, somehow. I think insertion at the last index (list.size) is ok, but beyond that my instinct is that I'd expect an error, or to be forced to grow the list. I'm open to your thoughts on the topic.

[ariesshrimp]

@axefrog no worries.

Maybe I'm still confused about verifyIndex(). Do these examples look right? They purport to show that index > size ? -1 : index allows setting the last index, but does not allow setting an index beyond the size of the list. So trying to set index 7 for [1,2,3] would fail. Trying to set index 2 at [1,2,3] would pass.

// example of failed verification
// index: 7, size: 3 --- can't set an index beyond the end of the list
// is this the case you're worried about?

index > size ? -1 : index
7     > 3    ? -1 : 7
true         ? -1 : 7
-1

// example of accepted verification
// index: 2, size: 3 --- you can set the last member though
// i think this is desirable?

index > size ? -1 : index
2     > 3    ? -1 : 2
false        ? -1 : 2
2

[ariesshrimp]

I guess it's a little more complex actually because lists are 0 indexed.

// ---------------------
// index: 0, size: 0, list: [] --- you can set the last member
// i think this is desirable

index > size ? -1 : index
0     > 0    ? -1 : 0
false        ? -1 : 0
0 // this is right, this sets [ x ]

// ---------------------
// index: 1, size: 1, list: ['a'] --- but you can set one past the last member... 😖
// i think this is wrong

index > size ? -1 : index
1     > 1    ? -1 : 1
false        ? -1 : 1
1 // this isn't right. this would try to set [ 'a', x ]
// but that's beyond the end of the list

// index >= size would have the opposite problem
// so would index > size - 1

but still should not have the problem you described

[axefrog]

It's been a little while since I wrote that code, so I just dove back in to try and remember exactly what I had in mind when I write it. To recap, the code is:

export function verifyIndex(size: number, index: number): number {
  index = normalizeIndex(size, index);
  return index === size ? -1 : index;
}

export function normalizeIndex(size: number, index: number): number {
  return max(-1, min(size, index < 0 ? size + index : index));
}

There are a few things to keep in mind here:

1. If the index argument is negative, it's a backtracking offset from the end of the list
2. If -1 is returned, it indicates that the index was invalid
3. normalizeIndex() computes a new index argument to transform a backtracking index into an actual index, and to ensure that if the argument is ultimately out of bounds, -1 is returned. It caters for both a backtracking index that would push the index too far to the left of 0, and for clamping excessive upper indexes back to the list size, which retains the property that the index is out of bounds, while ensuring that it does not exceed the list size.
4. verifyIndex() just adds the extra step of ensuring that if the index is normalized to match the list size (exclusive upper bound), then it is converted to -1, thus verifying that the specified index is actual an existing location in the list.

There are two functions there because I found several scenarios where I needed to reuse the code for incorporating a backtracking index calculation into the normalized index but where it was still permissable to return an exclusive upper bound equal to the list size.

I would suggest changing setValueAtOrdinal() to use normalizeIndex() instead, and then if the normalized index equals the list size, divert further operations to appendValues() instead.

Just thinking, that of course would contradict my earlier suggestion that it is ok to set index 7 of a list of size 3. I'm open to suggestions on that one.

[axefrog]

Is this still an issue? If you've moved on, I'll go ahead and close this.