690132 - ArrayObject::try_splice assumes deletedItems array has no holes

Status: RESOLVED FIXED

(Tamarin Graveyard :: Library, defect)

Description

[Felix S. Klock II [:pnkfelix, :fklock]]

This bit of code in ArrayObject::try_splice has a subtle bug:

  ArrayObject* deletedItems = toplevel()->arrayClass()->newArray(0);
  deletedItems->m_denseArray.splice(0, deleteCount, 0,
                                    this->m_denseArray, insertPoint);
  deletedItems->m_denseStart = 0;
  deletedItems->m_denseUsed = deleteCount;
  deletedItems->m_length = deleteCount;


The bug is that it is setting m_denseUsed to deleteCount.  But the deleteCount may be an over-estimate of the actual number of used elements in the deletedItems, because the m_denseArray may contain "holes" (i.e. atomNotFound).

At the moment, this probably only means that the dense/sparse policy decisions may be misinformed.  But a bug like this also makes it hard for me to do experiments like Bug 689828, because I am trying to confirm that my instrumentation is valid by check-summing against state like this.

Comment 1

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patch A: trivial fix

I'm not worried about the overhead of invoking calcDenseUsed(), because we also use that same method to fix up this->m_denseUsed a few lines down.

Comment 2

[Lars T Hansen]

Comment on attachment 563206 [details] [diff] [review]
patch A: trivial fix

I think you're probably right not to worry about that cost.

That said, I think it is the case that if "this" is simple by the current definition (it is dense with a start at zero and denseUsed == length) then the number of extracted elements is equal to deleteCount.  Even if that invariant is not useful here & now it may be useful by and by.

Comment 3

[Tamarin Bot]

changeset: 6608:dfa5e5cfe076
user:      Felix S Klock II <[e-mail]>
summary:   Bug 690132: try_splice deleteItems can have holes (r=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/dfa5e5cfe076