347165 - Provide a faster internal method for accessing form control elements

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[jpl24]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1b1) Gecko/20060710 Firefox/2.0b1
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1b1) Gecko/20060710 Firefox/2.0b1

Follow up to bug 302186

bz's comment:

> >+nsHTMLFormElement::ResetDefaultSubmitElement(PRBool aNotify)
> >+  nsCOMPtr<nsISimpleEnumerator> formControls;
> 
> I really wish we had a faster "internal" way of doing it.  This is ok for now,
> but want to file a followup bug on improving both this and the code in
> nsHTMLInputElement, perhaps?

Reproducible: Always

Comment 1

[Boris Zbarsky [:bzbarsky]]

Not a style system thing at all.  ;)

Comment 2

[jpl24]

I shouldn't pick components before drinking coffee in the morning. I'll take care of this one after bug 302186 lands.

Comment 3

[jpl24]

Hmmm, I thought that would assign it to me. I guess I don't have the privileges to do that.

Comment 4

[Boris Zbarsky [:bzbarsky]]

You have to change the assignee field to affect who the bug's assigned to.  I just gave you the bits to do that, for what it's worth.

Comment 5

[jpl24]

So what the nsFormControlIterator does is to perform an insertion sort on the list of elements not-in-elements list, and then lazily merges the list with the existing sorted list of elements.

Unfortunately, because image input elements are in the non-in-elements list we can't just iterate over the elements list. However, we should be able to do slightly better than the nsFormControlIterator in this case because we only care about a subset of the possible elements. Hmmm.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Even having the same algorithm, but returning nsIContent* (no addref) instead of the COM enumerator stuff would be great.

Comment 7

[jpl24]

There are currently three users of GetControlEnumerator

1) nsHTMLFormElement uses it to find the new default submit button.
2) nsHTMLInputElement uses it to find the number of text input elements.
3) Accessable code uses it to get the default submit button.

Interestingly, these uses are all fairly different, but none actually needs the fully sorted list of elements. I was thinking instead of adding a public function to return a sorted element array, I would add a public function to count the number of text input elements. This would satisfy usage 2. For 1, I would change the internal code to directly search through the two arrays.

What are the rules with regard to linking of accessable code with layout code? Should I leave the public COM enumerator function, or directly use the GetDefaultSubmitElement? If possible it'd be a nice code size win to remove all the enumerator code.

Or, as option 2 I could write a generic function which returns a sorted list of  form controls. I'd prefer option 1 however, as it should be faster and less code overall. Any thoughts?

Comment 8

[Boris Zbarsky [:bzbarsky]]

Hmm.. getting rid of all this code is _really_ tempting, but right now it has a certain flexibility...  I'd be maybe kinda in favor of leaving _something_ that lets the caller pass in an nsCOMArray<nsIFormControl> and fills it in with the controls.  jst, sicking, peterv, what do you think?

Having a function that outputs the number of text controls, or even just whether there is exactly one, might be a good idea no matter what.

As for accessibility, it should just use GetDefaultSubmitElement().  That's a virtual method, so no linkage issues.

Comment 9

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

It seems like all those three uses could simply use the elements array. I.e. they never care about the nodes that end up in nsFormControlList::mNotInElements. If so I don't think we should worry about getting the sorted list of the merge of mNotInElements and mElements.

Comment 10

[Boris Zbarsky [:bzbarsky]]

Use #1 and use #3 want nodes that are in mNotInElements -- image inputs.

Comment 11

[jpl24]

Attachment: testcase

Single input test cases for me not to break.

Comment 12

[jpl24]

The WF2 patch in bug 345822 is also using the enumerator internally.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Yeah.  That use is not order-dependent, so it could just walk elements and non-elements.

Comment 14

[Boris Zbarsky [:bzbarsky]]

Once this is fixed, bug 349355 needs revisiting.  Can't add a dep because it causes a dep loop.  :(

Comment 15

[jpl24]

I'd really like to remove the enumerator as it appears to be a good way to iterate over form elements, but it usually does way more than you want.

Would an acceptable path forward be to remove the enumerator and fix current users(I have a patch for this), and then file a follow up bug to discuss if and what to replace it with? If we decide to replace it with a new method I'll commit to implementing it.

Comment 16

[Boris Zbarsky [:bzbarsky]]

Yeah, that seems OK to me.

Comment 17

[jpl24]

CCing Alex because his patch is using GetControlEnumerator

Comment 18

[jpl24]

Attachment: remove_enumerator_v1

Comment 19

[jpl24]

I realized that there was one last use of the enumerator, for form control submissions, that I thought should stay sorted. The HTML4 spec didn't specify this case, but maintaining existing behavior seemed best. I rewrote the sorting code to sort directly into an array instead of creating the enumerator. This function will also make it easy to add a public method that returns a sorted list of form controls.

This still won't be that fast because CompareFormControlPosition QIs its arguments and addrefs them.

Comment 20

[jpl24]

Attachment: submission ordering testcase

Test case for form control ordering on submission. Requires looking at the query string, which is rather lame but I couldn't think of a better way.

Comment 21

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The WF2 stuff is going to need access to a sorted array of controls too. So it'd be good to have some function that can be reused for different callsites.

Comment 22

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Oh, and form submission absolutely has to keep the same order as it does now. Chaning the order in any way is known to break lots of sites.

Comment 23

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 236896 [details] [diff] [review]
remove_enumerator_v1

>Index: content/html/content/src/nsHTMLFormElement.cpp
>+nsHTMLFormElement::FindDefaultSubmit() const
>+  // Find the first submit control in the elements list. This list is
>+  // in document order.

So I was wondering... The only caller is ResetDefaultSubmitElemen(), and the only caller of that is RemoveElement().  And RemoveElement() knows whether it removed the element from mElements or mNotInElements and where it used to be.  So we know it's pointless to search earlier than that in the relevant array.  Could it be worth it to propagate that information into here and use it to optimize?  Or too much complexity for little win?

>+  // The not-in-elements list is not in document order.

I have to ask... why not?  It seems like it would be pretty easy to do in nsHTMLFormElement::AddElement something like:

nsVoidArray & controlList = ShouldBeInElements(aChild) ?
   mControls->mElements : mControls->mNotInElements;

and then just go through the existing "ShouldBeInElements(aChild)" case, but use |controlList| throughout.  You might need to make mControls->mNotInElements an nsVoidArray, since nsSmallVoidArray has private inheritance from nsVoidArray.  Or you could make both arrays nsTArray<nsIFormControl*> and either just preallocate some space or not.  That does need an extra allocation, probably, but I think that's ok in this case.

sicking, do you have any array wisdom here?

In any case, if this list were sorted it seems like you could do better here and in nsFormControlList::GetSortedFormControls.

I haven't reviewed the sorting code details pending this stuff, but the rest looks good.  ;)

Comment 24

[jpl24]

(In reply to comment #21)
> The WF2 stuff is going to need access to a sorted array of controls too. So
> it'd be good to have some function that can be reused for different callsites.
> 
Sure, I'll add an internal function to get at this list. It'll just be a wrapper around getSortedFormControls.
 
> Could it be worth it to propagate that information into here and use it to
> optimize?  Or too much complexity for little win?

I'll try this out and see if it can be done in relatively little code. This could be important for loops removing elements one by one.

> 
> >+  // The not-in-elements list is not in document order.
> 
> I have to ask... why not? 

I just looked and couldn't see any reason why, other than to avoid sorting on insertion. I like this idea, this should be less code and faster. I'm a big fan of nsTArray, so I'm hoping the extra allocation overhead isn't too bad.

> I haven't reviewed the sorting code details pending this stuff, but the rest
> looks good.  ;)
> 

A wise plan, a lot of the sorting code should go away in the next version.

Comment 25

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I don't think it's worth it to use nsSmallVoidArray for either of the two arrays, since we can expect that it's resonably uncommon for either to contain exactly 1 element (which is the only case where nsSmallVoidArray saves memory).

Using nsVoidArray or nsTArray<> should not matter size-wise, so it seems like a good idea to use the latter since it's more typesafe.

Comment 26

[jpl24]

Attachment: remove_enumerator_v2(-w)

Comment 27

[jpl24]

Attachment: remove_enumerator_v2

Comment 28

[jpl24]

This addresses all the review comments so far.

I also realized that the last-element optimization in addElement wasn't right in the case where the new child and the old default submit control were not in the same lists(in-elements vs. not-in-elements). I'll attach a testcase that shows this. Since I was working on that function anyway I went ahead and fixed that in this patch too.

Comment 29

[jpl24]

Attachment: Add element testcase

Comment 30

[jpl24]

Or I could split that into another bug, not sure which makes the most sense.

Comment 31

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 238328 [details] [diff] [review]
remove_enumerator_v2(-w)

A couple of nits, but in general this looks great!

>Index: content/html/content/src/nsHTMLFormElement.cpp
>+   * @param aPrevDefaultInElements Whether the previous default submit control
>+   *                               was in the elements list.

So if this is false, it was in the non-elements list, right?  That should be clearly documented here, I think.

>+   * @param aPrevDefaultIndex The index of the previous default submit control.

And here we should say that this index is within the list determined by aPrevDefaultInElements.

This applies to the comments for both ResetDefaultSubmitElement and FindDefaultSubmit.

>@@ -1287,19 +1295,22 @@ nsHTMLFormElement::AddElement(nsIFormCon
>     // default submit element. To speed up parsing, the special case
>     // of the last element in a form that already has a default submit
>-    // element is ignored as it cannot be the default submit element.
>+    // element where the previous default submit element resides in the
>+    // same list as the new child is ignored.

Maybe more like:

  "To speed up parsing, the special case of a form that already
   has a default submit that's in the same list as the new child
   is ignored, since the new child then cannot be the default
   submit element."

That said, maybe we should actually keep track of the first submits in both mInElements and mNotInElements?  With the current setup I worry that a single submit followed by a bunch of image inputs will make life unhappy.  For example, we could store the indices in both, rather than the element pointers.  We'd need to maintain the indices a little on insertion and removal, and change GetDefaultSubmitElement to compare the two indices and return the right thing... but then in this code we could simply do an index compare and be done with it.  A separate bug on this, though.  What you have here is good enough for this one.

>+    if (!mDefaultSubmitElement ||
>+        ((!lastElement ||
>+         ShouldBeInElements(mDefaultSubmitElement) != childInElements) &&

The "Should..." part should be indented one more space, no?

>         CompareFormControlPosition(aChild, mDefaultSubmitElement) < 0)) {

As should this line.

>+nsHTMLFormElement::HasSingleTextControl() const
>+    nsIFormControl* currentControl = mControls->mElements[i];

You don't really need this temporary.  Or does it help you avoid the 80-col thing?  If so, keep it.

> nsFormControlList::nsFormControlList(nsHTMLFormElement* aForm) :

I think you should init the size of mElements here, as we used to do.  The default size of an nsAutoVoidArray is 8, so just do:

   nsFormControlList::nsFormControlList(nsHTMLFormElement* aForm) :
     mForm(aForm),
     mElements(8)   
   {

> nsFormControlList::Clear()

>+    nsIFormControl* f = mElements.ElementAt(i);
>+    f->SetForm(nsnull, PR_FALSE, PR_TRUE);

Again, no need for the temporary, esp. if you use [i] instead of ElementAt(i)

>+    nsIFormControl* f = mNotInElements.ElementAt(i);

And here.

> nsFormControlList::Item(PRUint32 aIndex, nsIDOMNode** aReturn)
>+    nsIFormControl *control = mElements.ElementAt(aIndex);
>     return CallQueryInterface(control, aReturn);

And here, too.

>+nsFormControlList::GetSortedControls(nsTArray<nsIFormControl*>& aControls) const
>+  while (elementsIdx < elementsLen || notInElementsIdx < notInElementsLen) {

I think we can do a better job of optimizing the (common) case of different lengths here.  Something like this:

  while (elementsIdx < elementsLen ||
         notInElementsIdx < notInElementsLen) {
    // Check whether we're done with mElements
    if (elementsIdx == elementsLen) {
      NS_ASSERTION(notInElementsIdx < notInElementsLen,
                  "How'd that happen?");
      // Append the remaining mNotInElements elements
      if (!aControls.AppendElements(mNotInElements.Elements() +
                                      notInElementsIdx,
                                    notInElementsLen -
                                      notInElementsIdx)) {
        return NS_ERROR_OUT_OF_MEMORY;
      }
      break;
    }

Then similarly for the case of notInElementsIdx == notInElementsLen, and then fall through to the case when we still have both arrays to deal with.  That way once you get to the end of one of the arrays you'll just do a single append and be done with it.  If you think that this is sufficiently more complex than what you have, let's not worry about it, though; I'm not sure how much it really optimizes.  ;)  Let me know.
        
>+  for (PRUint32 i = 0; i < aControls.Length() - 1; ++i) {

Have to be a little careful here.  For example, if aControls.Length() == 0 this will go from 0 to PR_UINT32_MAX.  You probably want to put this whole for loop inside a |if (aControls.Length() > 0)|.

Comment 32

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 238328 [details] [diff] [review]
remove_enumerator_v2(-w)

r- just to get it out of my list, pending the nits being picked.

Comment 33

[jpl24]

(In reply to comment #31)

> That said, maybe we should actually keep track of the first submits in both
> mInElements and mNotInElements?

I agree, parsing performance could be pretty bad for certain forms. bug 353980 filed for this issue.

> I think we can do a better job of optimizing the (common) case of different
> lengths here. 

Interesting. I don't think this will be a huge amount faster than the code I had as it doesn't avoid any control comparisons or allocations, but it isn't any more complicated than what I had, and certainly is slightly faster, so I went with it.

Everything else fixed per comments. Patch in a moment.

Comment 34

[jpl24]

Attachment: remove_enumerator_v3

Comment 35

[jpl24]

Attachment: remove_enumerator_v3(-w)

Comment 36

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 238832 [details] [diff] [review]
remove_enumerator_v3

>Index: content/html/content/src/nsHTMLFormElement.cpp

>+nsHTMLFormElement::FindDefaultSubmit(PRBool aPrevDefaultInElements,

>+    if (currControl->IsSubmitControl() && (!defaultSubmit ||
>+        CompareFormControlPosition(currControl, defaultSubmit) < 0)) {
>+      defaultSubmit = currControl;
>+      break;

So... now that mNotInElements is sorted, we can break out as soon as we hit an submit control, no?  Something like:

  if (currControl->IsSubmitControl()) {
    if (!defaultSubmit ||
        CompareFormControlPosition(currControl, defaultSubmit) < 0) {
      defaultSubmit = currControl;
    }
    break;
  }

Should save us a bit of walking.  If you'd rather defer this to just fixing bug 352980 I'm OK with that too, but I think this is a simple change with a good win in edge cases of a long mNotInElements.

>+nsFormControlList::GetSortedControls(nsTArray<nsIFormControl*>& 
>+    else if (notInElementsIdx == notInElementsLen) {

No need for the |else|.  The previous |if| has an unconditional break.

>+    // Both lists have elements left.
>+    else {

And this |else| could be removed, and its body outdented.

r+sr=bzbarsky with those nits picked.  Thanks again for being patient, and I'm sorry I didn't catch the FindDefaultSubmit thing last time around.  :(

Comment 37

[jpl24]

> r+sr=bzbarsky with those nits picked.  Thanks again for being patient, and I'm
> sorry I didn't catch the FindDefaultSubmit thing last time around.  :(
> 

Not a problem at all, I really appreciate the thorough reviews. Nits fixed, patch coming momentarily.

Comment 38

[jpl24]

Attachment: remove_enumerator_v4

Comment 39

[Boris Zbarsky [:bzbarsky]]

Fix checked in on trunk for 1.9 alpha 1.

Comment 40

[[e-mail]]

Comment on attachment 238965 [details] [diff] [review]
remove_enumerator_v4

>+#ifdef DEBUG
>+  if (!aControls.IsEmpty()) {
>+    for (PRUint32 i = 0; i < aControls.Length() - 1; ++i) {
>+      NS_ASSERTION(CompareFormControlPosition(aControls[i],
>+                     aControls[i + 1]) < 0,
>+                   "Form controls sorted incorrectly");
>+    }
>+  }
>+#endif
What does it mean if I hit this assertion entering a new bug into Bugzilla?

Comment 41

[Boris Zbarsky [:bzbarsky]]

> What does it mean if I hit this assertion entering a new bug into Bugzilla?

It means Bugzilla's HTML sucks.  See bug 353415 (which is on the regression list for this bug).