Bug 3503 – form.elements[] not order-preserving when elements added via DOM

• Component: DOM
• Status: VERIFIED FIXED

[David Kilzer (:ddkilzer)]

Summary: 
When using JavaScript and the DOM to insert/replace elements within a form,
Safari displays the elements in the correct order, but the order of the elements
in the DOM itself (e.g., when the form elements are submitted back to a web
server) is not correct.   The new elements always appear at the end of the DOM
element list in the form.

Steps to Reproduce: 
See the first three test cases:

https://bugzilla.mozilla.org/attachment.cgi?id=122705
https://bugzilla.mozilla.org/attachment.cgi?id=141356
https://bugzilla.mozilla.org/attachment.cgi?id=147049

In this Mozilla bug:

https://bugzilla.mozilla.org/show_bug.cgi?id=204784

They demonstrate the bug in Safari (which was identical to the original behavior
in Firefox and Mozilla before they were fixed).

Expected Results: 
The DOM element order should be preserved.

Actual Results: 
The DOM element order is not preserved.  The new elements always appear at the
end of the DOM element list in the form.

Regression: 
Prior to Safari in Mac OS X 10.3.9, the behavior for these tests was not
well-defined (if these DOM operations, such as replaceChild(), were even supported).

To my knowledge, these tests have never worked with Safari.

Notes: 
I already used Safari's "Report Bugs to Apple..." tool to report this bug
against the updated Safari in Mac OS X 10.3.9 (sorry, I don't recall the version
or build number of Safari for that update).  The "Page Address" (URL) used in
that form is to this Bugzilla bug (referenced above):

https://bugzilla.mozilla.org/show_bug.cgi?id=204784

Apple Bug: rdar://4104411

[Anders Carlsson]

Created attachment 2356 [details]
Fix

Here's a patch that makes the three test cases work

[Joost de Valk (AlthA)]

fix works for me.

[David Kilzer (:ddkilzer)]

Thanks for creating a patch, Anders!

I noticed that the original Firefox/Mozilla patch does a binary search (O(log N)) to determine where to 
place the element in its data structure, while this patch does a linear search (O(N)).  In the interest of 
performance (priority #2 on the WebKit "Projects" page), is it possible to perform a binary search instead?

[Darin Adler]

Comment on attachment 2356 [details]
Fix

This patch looks good. I'm increasingly uncomfortable with the form element
class using vectors and inserting and removing elements from the middle of the
vectors. There's no obvious benefit of a vector over a list, and a list
supports high speed insertion and deletion. Except for the one use of this as a
vector in HTMLFormCollectionImpl::item. But I think that need not prevent us
from taking this patch; it's not even obvious what we should do.

But I'm concerned with another aspect of this patch.

I think that getFormElementByIndex might need to check the form() on the
element before counting it when computing the index. If for some reason the
form element is not associated with this form, we could end up with an index
that is past the end of the form element vector, with disastrous results. I'm
not sure if that case can arise, but I'm also not sure that it can't, and the
code change is very simple. Please fix that in the patch.

As far as the comments about linear vs. binary search, if you look at the
Mozilla code you'll see that inside that binary search they are doing an
operation that compares the relative positions of the DOM nodes. This operation
is going to be proportional to the tree distances between successive nodes. The
approach of iterating the entire DOM tree under the form element should be
relatively similar in complexity, and there's no real option to use a binary
search here.

On the other hand, there's a chance that the Mozilla code will handle cases
better where the form elements are not inside the <form> element. It's worth
making test cases of this sort to find that out, but we can file a new bug once
we do that if this fix has already been landed.

[Anders Carlsson]

Created attachment 2389 [details]
New patch

Here's a new patch that checks if the element has the same form before counting
it.

[Darin Adler]

Comment on attachment 2389 [details]
New patch

r=me

Minor comments:

1) No need to have an else after a return in getFormElementIndex.

2) To make things possibly more robust I suggest that
HTMLFormElementImpl::registerFormElement do the check this way:

    if (i < 0 || i >= (int)formElements.count())

If we like we could assert to catch problems with incorrect indices.

[Darin Adler]

I'm working on writing a test for this. In the future, we need tests ready for the layout-tests directory as 
well as patches before we can commit a fix.

[Darin Adler]

I'm concerned that this makes adding form elements O(n^2) where n is the number of elements inside the 
<form> element. That's true even when parsing the initial web page; could this create problems for us on 
pages with a lot of elements? Do we need to optimize the case where the element being added is the very 
last thing inside the form?

[Darin Adler]

Created attachment 2467 [details]
A third try

I attached a new patch that improves a few different things (using unsigned
consistently gets rid of some typecasts, for example) and also adds a special
case to avoid scanning the form's tree in the normal parsing case for speed.

It also include a regression test for the layout-test directory.

I suppose I should add a test case for the performance issue since I fixed
something that's just theoretically wrong.

One flaw is that items that hit my special case for speed end up after all the
items that are not anywhere inside the <form>, whereas otherwise they would be
after all the items in the <form> tree, but before any items that are outside
it. Not sure if this is bad enough that we need to track the number of items in
the tree somehow.

[Maciej Stachowiak]

r=me

[Joost de Valk (AlthA)]

Verified, reporter, please verify this bug with ToT webkit and mark it as verified.

[David Kilzer (:ddkilzer)]

Verified fixed using TOT (tip of tree) build of WebKit from CVS.

[Joost de Valk (AlthA)]

Fixed in 10.4.2

[Joost de Valk (AlthA)]

Hmm actually not... Was looking wrongly...