Rare error on insert (need help reproducing) about rbush HOT 25 CLOSED

Details of this error's root cause and a fix is now available in #94. It successfully runs the code from #69 (comment)

@mourner I'd appreciate your review, as properly supporting infinity rectangles is an important requirement for my current app.

from rbush.

from rbush.

Unfortunately, i can't reprosuce it consistently. Problem appear after 1-2 hours of script working, so i have no idea what caused the problem.

p.s. Можно на русском подробно описать проблему? Мне так будет намного проще :)

from rbush.

Можно и на русском, но я не смогу принять баг и пофиксить без тест кейса — без него по умолчанию буду предполагать, что проблема на стороне приложения. Попробуй искусственно сделать Node-скрипт, который делает много добавлений и удалений, пока проблема не появится.

from rbush.

Это я понимаю, пока пробую заставить проблему стабильно повторяться. Есть игровой сервер, на старых режимах игры такая беда вылазила где-то через три дня, мы просто перегружали его и не особо страдали.

А вот в новом режиме вываливается такое стабильно, пока понял что косяк появляется если у новых нод большой размер. Тикет создал, чтобы поинтересоваться есть ли какие идеи на этот счёт.

Попробую сделать скрипт, чтобы стабильно повторять проблему.

from rbush.

Глядя на stack trace, у меня кажется есть идея, когда это может происходить. Попробую разобраться и пофиксить сегодня.

from rbush.

Спасибо, было бы замечательно :)

from rbush.

Не, все-таки не понимаю, как так получается. Нужен тест-кейс. Когда в следующий раз появится баг, можно более подробный дамп? Что находится в переменной node на которой возникает ошибка при node.children.push?

from rbush.

Попробую в течении пары дней повторить, пока эту логику выпилили. Как будет инфа, отпишусь

from rbush.

I'm also seeing a similar issue. Full stack trace:

Uncaught TypeError: Cannot read property 'push' of undefined
    at rbush._insert (modules.js?hash=eaece39…:33481)
    at rbush.insert (modules.js?hash=eaece39…:33300)
    at ol.structs.RBush.insert (modules.js?hash=eaece39…:33798)
    at ol.structs.RBush.update (modules.js?hash=eaece39…:33855)
    at ol.source.Vector.handleFeatureChange_ (modules.js?hash=eaece39…:68753)
    at ol.Feature.boundListener (modules.js?hash=eaece39…:12612)
    at ol.Feature.ol.events.EventTarget.dispatchEvent (modules.js?hash=eaece39…:13032)
    at ol.Feature.ol.Observable.changed (modules.js?hash=eaece39…:13199)
    at ol.Feature.handleGeometryChange_ (modules.js?hash=eaece39…:41615)
    at ol.geom.LineString.boundListener (modules.js?hash=eaece39…:12612)

Value of node at time of error:

maxX: 677304.9958616777,
maxY: 5817141.162886764,
minX: 675843.0655270431,
minY: 5816545.582488596,
value: ol.Feature

It appears infrequently - still trying to understand the behaviour that causes it.

from rbush.

@devonbarrett thanks for the info! This hints that for some weird reason, the _chooseSubtree method returns a bottom node of the tree (that represents the item), even though it should break on leaf nodes and never reach their children. Hard to understand when this happens though. Can you also try to set up a consistently reproducible test case in Node?

from rbush.

@dmitrypisanko новостей никаких?

from rbush.

Я в код на проде логирование добавил, пока не повторялось. Баг крайне спонтанный и трудно отловимый (

from rbush.

@devonbarrett @dmitrypisanko any news on a reproducible test case?

from rbush.

@mourner привет, больше не работаю над тем проектом, потому не могу ничего сказать. Но периодически бага появлялась, логов к сожалению нет :(

from rbush.

Hi @mourner !

I've been having the same issue, and noticed that only happens when having some items with Infinity bounds, and then doing updates (an update being removing the item, change its bounds, and then re-add it).

Here's the code I used to consistently repro it on node 8.11.3:

const rbush = require('rbush');

const rand = (min, max) =>
  Math.floor(Math.random() * (max - min + 1) + min)

const times = (n, fn) => {
  for (let i = 0; i < n; i++) fn(i)
}

const infinity = {
  minX: -Infinity,
  minY: -Infinity,
  maxX: Infinity,
  maxY: Infinity,
}

const createBounds = () => (Math.random() < 0.1 ? { ...infinity } : {
  minX: rand(-10000, 10000),
  minY: rand(-10000, 10000),
  maxX: rand(-10000, 10000),
  maxY: rand(-10000, 10000),
})

const createItem = () => ({
  ...createBounds(),
  value: Math.random()
})

const ITEMS = 1500
const UPDATES = 12000

const items = Array(ITEMS).fill(null).map(createItem)
const tree = rbush(6)

tree.load(items);

console.log(`${items.length} items loaded.`)

console.log(`Doing ${UPDATES} updates`)

times(UPDATES, (i) => {
  console.log(`update ${i + 1}`)
  const index = rand(0, items.length - 1)
  const item = items[index]

  tree.remove(item)

  const newItem = {
    ...item,
    ...createBounds()
  }

  items[index] = newItem

  tree.insert(newItem);
})

Worth noting that this error also happened to me when mistakenly added some items without the minX, minY, maxX, maxY props. Maybe the library should throw an error when doing that?

from rbush.

Hi!
I have this problem too. Need fix!

from rbush.

@borodaev If this is your case, we fixed it using Number.MAX_SAFE_INTEGER instead of Infinity.

from rbush.

@mjlescano, I got this problem on regular data sporadically

from rbush.

@borodaev I'd really appreciate it if you could catch a minimal test case that reproduces the failure for regular data.

from rbush.

FWIW, I get similar errors (undefined push/length properties) when min/max values are unknowingly NaN.

from rbush.

Any updates on this issue? I'm having a similar problem.

from rbush.

@pcezar-i9 we still don't have a minimal reproducible test case to track down the problem. Maybe you could help with that?

from rbush.

Unfortunately no, this happened twice on the application I'm working at, but the cases are very erratic and doesn't make sense.

from rbush.

Hi @mourner, I copied the code posted by @mjlescano into a new file and ran it, and it repeatably reproduces the defect in under a second (81 updates). I'm using rbush 2.0.2. Have you tried reproducing it this way?

update 77
update 78
update 79
update 80
update 81
/Users/rbl/Documents/test/node_modules/rbush/index.js:266
            for (i = 0, len = node.children.length; i < len; i++) {
                                            ^

TypeError: Cannot read property 'length' of undefined
    at rbush._chooseSubtree (/Users/rbl/Documents/test/node_modules/rbush/index.js:266:45)
    at rbush._insert (/Users/rbl/Documents/test/node_modules/rbush/index.js:299:25)
    at rbush.insert (/Users/rbl/Documents/test/node_modules/rbush/index.js:121:24)
    at times (/Users/rbl/Documents/test/rbush.js:55:8)
    at times (/Users/rbl/Documents/test/rbush.js:7:31)
    at Object.<anonymous> (/Users/rbl/Documents/test/rbush.js:41:1)
    at Module._compile (internal/modules/cjs/loader.js:701:30)
    at Object.Module._extensions..js (internal/modules/cjs/loader.js:712:10)
    at Module.load (internal/modules/cjs/loader.js:600:32)
    at tryModuleLoad (internal/modules/cjs/loader.js:539:12)

from rbush.