694894 - Array try_shift incorrectly assumes first elem of m_denseArray is not atomNotFound

Status: RESOLVED FIXED

(Tamarin Graveyard :: Library, defect)

Description

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

Exposed by tests from Bug 693431 and related to Bug 684211

Consider the following:

  var d = [];
  d[0] = 1;
  d[1] = 1;
  delete d[0];
  var dv = d.AS3::shift();
  print(dv is Array);

In a DebugDebugger build, this assert fails:

  Assertion failed: "((((avmplus::Atom)(uintptr_t(atom) & 7)) != kUnusedAtomTag))" ("../core/AvmCore.cpp":2646)

The problem is that the first element of m_denseArray has been set to atomNotFound == 0 by the 'delete d[0]' statement, but when we get to ArrayObject::try_shift, we end up in this code:

            else if (m_denseArray.length() > 0)
            {
                // [...]
                result = m_denseArray.removeFirst();
                --m_denseUsed;
            }

(Argh, do we need a loop here, how ugly.  It has to go either here or in delete though.  That or we stop supporting dense arrays with holes.)

Comment 1

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

Attachment: patch A v1: fix by looping on shift

Some quick notes:
1. The loop here is inductive on denseLen, so we get easy termination argument.

2. We could strengthen the rep invariant to include the rule that a dense array never starts on a hole, and then enforce that invariant within delete.  But that would not remove the need to include a loop here, since we would still need to uphold that invariant within this code as well.  I don't think such a rep invariant would buy us much, so I'm not going to try to implement it.

QRB: Where should we target tbis patch?

Comment 2

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

Attachment: patch A v2: fix by looping on try_shift

small fix: only non-hole atoms contribute to the m_denseUsed measure.

Comment 3

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

Comment on attachment 567382 [details] [diff] [review]
patch A v2: fix by looping on try_shift

(retracting review request; i need to go back and double-check my understanding of what the spec for shift is.  Even if there's a hole, I suspect I am not supposed to loop, but rather just set v to undefinedAtom.)

Comment 4

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

Attachment: patch A v3: direct non-looping fix

Its a bit more revision to the flow than I would have liked for a straight-line fix, but hey, at least it gets the semantics more correct than the v1 or v2 did.  :)

Comment 5

[Tamarin Bot]

changeset: 6660:2d410bbd0312
user:      Felix S Klock II <[e-mail]>
summary:   Bug 694894: handle case when first element of shifted array is atomNotFound (r=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/2d410bbd0312

Comment 6

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

(i was waiting to close this to see if there was a response from qrb to target it to e.g. Anza.  At this point I'm assuming its fine if this just lands in Brannan and no sooner.)