fast-safe-stringify: Infinite loop when called on a Sequelize object

Okay, I need to move on for now, but here is where I got in debugging:

I set a conditional breakpoint for when the stack hits 100 length. A few highlights from the image:

• The 6th stack entry, Array(407) is the 407 domain objects I’m saving to the database
• The 7th stack entry, StageDefinition is one of our domain objects
• The 8th stack entry is StageDefinition’s collection pointing to N UnitDefinition domain objects
• The 9th stack entry is the array of those 7 UnitDefinition objects
• …repeat this pattern fro the UnitDefinition having N ActivityDefinitions having N TaskDefinitions having N TaskDefinitionPredecessor dependencies.

(Basically our domain model is a highly-inter-connected graph of a "project with a bunch of tasks, various levels/groupings of tasks (stage/unit/activity), and then dependencies (predecessors/successors) between the tasks. Obviously they become individuals rows in the database, but while in memory our ORM basically graph-izes all the references (intelligently/lazily/no+N+1-ily) so we can easily do things like critical path calculation, which is essentially walking a graph.)

As I continue looking down the stack entries, everything “looks right”, decirc is just continually finding “oh I haven’t seen that yet” references…although they are really all part of that original Array(407), each one just hasn’t been marked/added to the stack proper yet (i.e. as an explicit element that we know about-but-have-not-visited yet) because we’re not ‘done’ with each one).

I.e. even though the 6th stack entry of Array(407) has all of the instances as implicitly “already seen but not processed”, we process the 1st one (…and find 406 others), then do the 2nd one (…and find 405 others), then do the 3rd one (…and find 403 others), where each of these “…and find XXX others” is not actually linear, but itself recursing through “seen but not yet processed” values.

So, could we somehow pre-tell decirc “yes we know about all 407 of these, we are getting to them, but don’t recurse into them if you find them again”.

…i.e. here:

    if (Array.isArray(val)) {
      for (i = 0; i < val.length; i++) {
        // put all the vals in stack first, before recursing
        decirc(val[i], i, stack, val)
      }
    } else {

Put every element in val directly on the stack before calling decirc because otherwise the current “pre-recursion before we put val[i] in the stack” is going to not realize we already know about the other N values in val.

Basically some differentiation of nodes between “has seen and not yet visited/processed” (not currently in the code AFAIU) and “has finished visiting/actually processed” (an entry in stack AFAIU).

I am not an algorithms expert, but I vaguely recall seeing this distinction in graph traversal algorithms last time I was studying for interviews. 😛 😃

Perhaps the code is already doing this and I’m just missing it. Not sure.

Also fwiw I tried to re-create our graph with just a bunch of in-memory nodes with like 2-levels of 100 “parents” and 5 children-per-parent and failed to trigger this behavior. I think the input really does need to be pathologically circular, which is hard to create by hand (the graph I’m using is an actual one from production, hence the inherent size/complexity). I can try to synthesize also pathological input here & there/as I get time.

(Also, just to be clear, we never wanted fast-safe-stringify to actually output a sane value for this data structure/graph, it just happened to leak into a logger.error({ err: ... }, ...) without really meaning to, and then tada our CPU is pegged and the app is dead. We’ve since implemented toJSON on our entities and EntityManager to stop this from happening, but I followed up here as an extra/future precaution + FYI.)

…ah yeah, so this is really ugly, but just doing:

      if (stack[i] === val || (Array.isArray(stack[i]) && stack[i].includes(val))) {

Stopped the pathological behavior. I have no idea is the resulting behavior is correct (i.e. I didn’t inspect the output and it could be doing ‘wrong things’), just that it stops the “not technically infinite but just a lot of it” recursion.

Hopefully that is helpful…

@davidmarkclements sure.

Code to reproduce:

'use strict';

const Sequelize = require('sequelize');
const stringify = require('fast-safe-stringify');

const db = new Sequelize(
  'sequelize_test',
  'postgres',
  '1',
  {
    host: 'localhost',
    dialect: 'postgres',
    logging: false,
    operatorsAliases: false
  }
);

const users = db.define('users', {
  id: {
    type: Sequelize.INTEGER,
    autoIncrement: true,
    primaryKey: true
  }
}, { tableName: 'users', timestamps: false });

async function test() {
  const user = await users.findOne({ where: { id: 1 } });
  stringify(user);
}

test()
  .catch(err => console.log('ERROR', err))
  .then(() => console.log('DONE!'))
  .then(() => db.close());

I also have added logging for traverse:

function decirc (val, k, stack, parent) {
  console.log(' '.repeat(stack.length) + '> ' + k);

Sample log is attached. traversedProps.txt

buffer props are real Buffer objects: user._modelOptions.sequelize.connectionManager.pool._availableObjects._list.head.data.obj.connection.writer.buffer instanceof Buffer === true