Function denormalize throws RangeError: Maximum call stack size exceeded - support selecting normalized objects by id

[zeraien]

I still haven't been able to figure out how or why, but sometimes the function denormalize in normalizers/denormalize.js, will go into an infinite recursion loop while loading data.

Uncaught RangeError: Maximum call stack size exceeded
    at denormalize.js:21
    at Array.reduce (<anonymous>)
    at denormalize (denormalize.js:21)
    at denormalize (denormalize.js:7)
    at denormalize.js:24
    at Array.reduce (<anonymous>)
    at denormalize (denormalize.js:21)
    at denormalize (denormalize.js:7)
    at denormalize.js:12
    at Array.map (<anonymous>)

Not sure where to start debugging it...
The trace starts in getQuerySelector, so I'm trying to use that to obtain the result of a normalized request.

[klis87]

I probably know what this is... see #317

Probably you have very many items in data, as well as very nested data for this query. Above issue would solve it. This could be also a different problem, but I cannot help without seeing data.

[zeraien]

Here is my data, I will continue debugging but if you see something that strikes your eyes. It might be that I'm trying to get the normalized data directly from the normalizedData dict... I still haven't figured out a way to get the normalized objects out of there ;)
https://pastebin.com/N4AYGa7m

[klis87]

@zeraien do you mean that you are reading normalizedData from requestsReducer on your own? this is internal implementation detail and should not be read manually

getQuery denormalizes data automatically, you don't need to think about it
pasted data doesnt look scary, I tested this with 10 000 items + and it still worked and still was fast, so probably you are doing sth unexpected, some snippet with get the normalized data directly from the normalizedData would probably help :)

[zeraien]

@zeraien do you mean that you are reading normalizedData from requestsReducer on your own? this is internal implementation detail and should not be read manually

getQuery denormalizes data automatically, you don't need to think about it
pasted data doesnt look scary, I tested this with 10 000 items + and it still worked and still was fast, so probably you are doing sth unexpected, some snippet with get the normalized data directly from the normalizedData would probably help :)

Well, sometimes I just need to obtain objects by ID from the cache, because it's not always that objects are in a request, maybe you just need a related object in a different context, but now of course I realize that it's not a good idea because the data in the normalizedData is normalized! I'll do some more digging and see if I can figure it out, it may very well not be an issue with your code, but with mine (most likely) hehe.

[zeraien]

I'm starting to think there might be something weird going on with the denormalize function after all.

Here is what path looks like after a few iterations...
.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints.parcels.activities.waypoints

As you can see it's repeating. I will do more digging.

[zeraien]

Ok, so I found the cause. It's a recursion bug alright
Here is an abridged version of my JSON that causes the recursion loop:

{
	"id": "zVid0ty",
	"date": "2019-12-27",
	"barcode": "49394dcd-cd1b-46e8-82a2-2544c828d199",
	"identifier": "rdT6T9uz",
	"activities": [{
		"id": "A1ibDFG2"
	}, {
		"id": "40i9vHdK"
	}],
	"parcels": [{
		"id": "xwiA3sO",
		"activities": [{
			"id": "A1ibDFG2"
		}, {
			"id": "40i9vHdK"
		}]
	}]
}

If I remove the activities key from parcels, the problem disappears. You can argue that activities have no business being in parcels since they are already up on the top level, but it should probably still not crash :)

This works:

{
	"id": "zVid0ty",
	"date": "2019-12-27",
	"barcode": "49394dcd-cd1b-46e8-82a2-2544c828d199",
	"identifier": "rdT6T9uz",
	"activities": [{
		"id": "A1ibDFG2"
	}, {
		"id": "40i9vHdK"
	}],
	"parcels": [{
		"id": "xwiA3sO",
		"activities": null
	}]
}

[zeraien]

Finally I narrowed down that the following normalizedData causes recursive loop when calling denormalize("@@zVid0ty", normalizedData, {}), or in fact using any of the ids...

The activities both reference parcel, which also reference those same activities...

{
  
    '@@xwiA3sO': {
      id: 'xwiA3sO',
      type: 'parcel',
      activities: [
        '@@A1ibDFG2',
        '@@40i9vHdK'
      ],
    },
    '@@zVid0ty': {
      id: 'zVid0ty',
      type: 'consignment',
      activities: [
        '@@A1ibDFG2',
        '@@40i9vHdK'
      ],
      parcels: [
        '@@xwiA3sO'
      ],
    },
    '@@40i9vHdK': {
      id: '40i9vHdK',
      type: 'activity',
      parcels: [
        '@@xwiA3sO'
      ],
    },
    '@@A1ibDFG2': {
      id: 'A1ibDFG2',
      type: 'activity',
      parcels: [
        '@@xwiA3sO'
      ],
    }
}

[zeraien]

And now I realise that I guess that data structure simply won't work since it will indeed be infinitely recursive... my stupid.

[klis87]

@zeraien if getQuery works then everything is fine

What you try to do is symptom we need new feature -> get object by id, the problem is that we need usedKeys etc which you can inspect in requestsReducer, it is possible some stuff will need to be refactored.

For now I hope you will solve it on the app level, but I will add this to TODO list so this will be built-in.

[klis87]

@zeraien I thought about it and there is 1 issue.
Imagine object like this fetched at /users/1

{
  id: 1,
  name: 'name',
  bestFriend: {
      id: 2,
      name: 'name 2',
      bestFriend: {
        id: 1,
        name: 'name',
      }
    }  
  } 
}

As you can see denormalizing would indeed cause endless loop. For queries it is not a problem thanks to usedKeys, which are automatically calculated based on query response structure and stored in reducer.

So based on the example information that nested user has only id and name key prevents this issue.

Now we want to allow to get an orbitrary object. For this case we dont have usedKeys, normalized object contains all used keys from all queries referencing a given object merged in 1 place. Then we don't have protection and can end up with recursive reference issue and so on.

Do you have any idea how we could solve that?

[klis87]

Also, the question is why do you even need to do that? Perhaps what you need is just action.meta.requestKey, so that you could have more queries of the same type stored inside reducer, like with multiple different ids.

[zeraien]

Good point, so it can indeed become an issue!
Well, there are a few solutions I guess, one is to turn relationships into function calls, so you need to call a function to get the relationship data...

{
  id: 2,
  name: 'friend 2',
  bestFriend: () => get("@@1") -> {id:1, name:'friend 1', bestFriend:  get()}
},
{
  id: 1,
  name: 'friend 1',
  bestFriend: () => get("@@2")
}

But that brings with it other complications, in theory, whoever has to work with that data structure risks going into an infinite loop themselves...

Another alternative is to simply cut the feed at level 2.

{
  id: 2,
  name: 'friend 2',
  bestFriend: {
      id: 1,
      name: 'friend 1'
    }  
  } 
},
{
  id: 1,
  name: 'friend 1',
  bestFriend: {
      id: 2,
      name: 'friend 2'
    }  
  } 
}

I guess you can check if the parent has the same key and then simply not include that key. But that risks mangling someone's data, although you could mitigate with a console warning...

Alternatively, simply find a way to detect the infinite loop and warn the user so they can change the API...

[klis87]

Relations has to be stored as strings, this has to be serializable.

Introducing a warning is 1 idea, but in our example API really is just fine, it just has recursive relationship but for queries with usedKeys this is not a problem at all. So we should not ask people to change API if API is fine :)

Another idea is to limit nesting depth, but like you said this would mangling data.

I think about catching this error indeed and showing a message like data has recursive structure, please provide usedKeys for this data to denormalize it properly which could be also documented

So actually app user would provide proper usedKeys for a give object oneself. I cannot see any other way.

But the most important question is, why do you even need this? Please provide use case, maybe I will give you another way to achieve what you need.

[zeraien]

I don't really need it, it was just my API was configured in this way and so I changed my API to compensate.
I am not quite sure about usedKeys, would we provide it in the action creator?

[klis87]

@zeraien usedKeys would be provided to new selector like getNormalizedObjectById

normally this selector would just get id and it would return proper object, but if leading to recursive error, this would be catched and warning would be shown in console.

then someone could do thing like:

const myObject = getNormalizedObjectById(state, { id: '1', usedKeys: {
  id: true,
  name: true,
  bestFriend: {
    id: true,
    name: true,
  }  
}}});

So usedKeys would be provided in easy to work with way by human, while library would convert it to the same structure as stored in reducer. Probably this would be used very sparingly, only when recursive relationship, but we would have an escape hatch so I could work on getNormalizedObjectById

[klis87]

actually this could be represented as graphql query, like:

{
  id
  name
  bestFriend {
    id
    name
  }
}

in theory such parsing could be also allowed via graphql driver

[klis87]

if I think about it more, this looks like graphql fragment concept, but for any api, including REST