Bug 3503 - form.elements[] not order-preserving when elements added via DOM
Summary: form.elements[] not order-preserving when elements added via DOM
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 412
Hardware: Mac OS X 10.4
: P2 Major
Assignee: Darin Adler
URL: https://bugzilla.mozilla.org/show_bug...
Keywords: InRadar
Depends on:
Reported: 2005-06-13 09:03 PDT by David Kilzer (:ddkilzer)
Modified: 2006-02-09 20:02 PST (History)
1 user (show)

See Also:

Fix (3.16 KB, patch)
2005-06-15 03:18 PDT, Anders Carlsson
darin: review-
Details | Formatted Diff | Diff
New patch (3.24 KB, patch)
2005-06-16 09:54 PDT, Anders Carlsson
darin: review-
Details | Formatted Diff | Diff
A third try (6.76 KB, patch)
2005-06-18 19:07 PDT, Darin Adler
mjs: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description David Kilzer (:ddkilzer) 2005-06-13 09:03:09 PDT
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:


In this Mozilla bug:


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.

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.

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):


Apple Bug: rdar://4104411
Comment 1 Anders Carlsson 2005-06-15 03:18:11 PDT
Created attachment 2356 [details]

Here's a patch that makes the three test cases work
Comment 2 Joost de Valk (AlthA) 2005-06-15 04:06:36 PDT
fix works for me.
Comment 3 David Kilzer (:ddkilzer) 2005-06-15 21:16:50 PDT
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?
Comment 4 Darin Adler 2005-06-16 09:33:21 PDT
Comment on attachment 2356 [details]

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.
Comment 5 Anders Carlsson 2005-06-16 09:54:53 PDT
Created attachment 2389 [details]
New patch

Here's a new patch that checks if the element has the same form before counting
Comment 6 Darin Adler 2005-06-16 10:11:09 PDT
Comment on attachment 2389 [details]
New patch


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.
Comment 7 Darin Adler 2005-06-18 18:29:05 PDT
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.
Comment 8 Darin Adler 2005-06-18 18:44:36 PDT
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?
Comment 9 Darin Adler 2005-06-18 19:07:20 PDT
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.
Comment 10 Maciej Stachowiak 2005-06-19 21:57:44 PDT
Comment 11 Joost de Valk (AlthA) 2005-06-19 23:47:39 PDT
Verified, reporter, please verify this bug with ToT webkit and mark it as verified.
Comment 12 David Kilzer (:ddkilzer) 2005-06-20 04:13:37 PDT
Verified fixed using TOT (tip of tree) build of WebKit from CVS.
Comment 13 Joost de Valk (AlthA) 2005-07-13 22:59:22 PDT
Fixed in 10.4.2
Comment 14 Joost de Valk (AlthA) 2005-07-13 23:07:03 PDT
Hmm actually not... Was looking wrongly...