Hitting call stack limit when clone very large BinarySearchTree for GVL version 181

[sevriugin]

Version
Latest

Module (core, cmpapi, cli, stub, or testing)
core

Describe with reproduction steps – What is the expected behavior?

Hitting call stack limit when clone very large BinarySearchTree.

We can check it to clone map in the test

With the latest GVL updates 181 and 182 the core library is broken if we are using publisher restrictions with type all.

The issue is with restrictPurposeToLegalBasis that is building very deep BinarySearchTree for all vendors ids and with latest updates the lastEntry will be 4057.

The core library will try to clone this vector using Cloneable.clone method and we are hitting call stack limit even with Error.stackTraceLimit = Infinity;

The solution could be to update IAB TCF core library and avoid using recursion in Cloneable class.

There is an alternative approach to deep clone of the object using tasks. (see PR)

This solution is tested with very long BinarySearchTree with 4200 nodes

[ermurri]

FWIW, this issue was surfaced by an unexpected (unintended?) jump from the last "good" vendor ID of 1179 to 4056 and then now it seems to be incrementing from that ID and they just skipped an entire range. So, this bug may not have been seen for a while but the GVL release is causing it.

[sevriugin]

After several performance tests the proposed solution with TaskManager looks very slow. We could keep working to optimise it but also will consider to implement an alternative one - building a balanced (optimised) BinarySearchTree .

In the current implementation the BinarySearchTree depth is equal to the number of vendors in the restriction

  for (let i = 1; i <= lastEntry; i++) {
      if (!this.has(hash)) {
        this.map.set(hash, new BinarySearchTree());
        this.bitLength = 0;
      }
      this.map.get(hash).add(i);
  }

We can introduce a new static method for the BinarySearchTree class that will build for the same number of sorted values a balanced search tree with depth equal to log2 of number of vendors. In this case Clonable.clone will work with vendors ids around 4056 (and much above) as the tree depth will be equal 12 and not 4056

  static build(values?: number[]): BinarySearchTree | undefined {
    if (!values || values.length === 0) {
      return;
    } else if (values.length === 1) {
      const tree = new BinarySearchTree();
      tree.add(values[0]);
      return tree;
    } else {
      const rootIndex = values.length >> 1;
      const tree = new BinarySearchTree();
      tree.add(values[rootIndex]);
      const root = tree.getRoot();
      if (root) {
        if (rootIndex + 1 < values.length) {
          const rightTree = BinarySearchTree.build(values.slice(rootIndex + 1));
          root.right = rightTree ? rightTree.getRoot() : null;
        }

        if (rootIndex - 1 > 0 ) {
          const leftTree = BinarySearchTree.build(values.slice(0, rootIndex - 1));
          root.left = leftTree ? leftTree.getRoot(): null;
        }
      }
      return tree;
    }
  }

To implement build we also need to update BinarySearchTree class adding the root access public method

  public getRoot(): TreeNodeMaybe {
    return this.root;
  }

There is a test for BinarySearchTree.build(values) clone that works (no call stack limit hit), including console.log(JSON.stringify(tree)) that for the previous version of the tree with depth 4057 always fails with error

describe('Cloneable', (): void => {
  it('Clone BinarySearchTree', (done: () => void): void => {
    const lastEntry = 4057;
    const values = [...Array(lastEntry).keys()].map( (i) => i + 1);
    const tree = BinarySearchTree.build(values);
    expect(tree).to.be.a('object');

    console.log(JSON.stringify(tree));

    tree?.clone();
    done();
  });
});

[sevriugin]

PR created #385

[kenario]

v1.5.6-1 pre-release of the library has been published. You can download and use the pre-release into your cmp via npm install @iabtcf/core@next. If no issues are found in a two week time period, this pre-release will be considered stable and released as v1.5.6.

[kenario]

@sevriugin v1.5.6 of the library, which contains your changes, has been released.