Bug 74909 – Introduce RadioButtonGroup class to keep track of the group members and required state

• Status: RESOLVED
• Resolution: FIXED
• Component: Forms

[Kent Tamura]

If a document has a radio button group containing many radio buttons, the document rendering is very slow.

HTMLInputElement::updateCheckedRadioButtons() is called in attach() of a radio button, and the function iterates over all of radio buttons in the same group.  So, it's O(N^2).

See http://crbug.com/81553 and Bug 62840.

[Kent Tamura]

Created attachment 119989 [details]
Patch

[Kent Tamura]

Created attachment 119996 [details]
Patch 2

Avoid virtual function calls

[Dimitri Glazkov (Google)]

Comment on attachment 119996 [details]
Patch 2

Can we have a perf test for this? Seems like it should be fairly easy.

[Darin Adler]

Comment on attachment 119996 [details]
Patch 2

View in context: https://bugs.webkit.org/attachment.cgi?id=119996&action=review

It should be straightforward to put a test in LayoutTests/perf that shows that this was O(n^2) and is no longer O(n^2).

> Source/WebCore/ChangeLog:12
> +        We can skip this iteration in a case that validity status is not changed.

This is not a sufficient explanation.

> Source/WebCore/html/HTMLInputElement.cpp:188
> +    CheckedRadioButtons& radioButtons = checkedRadioButtons();
> +    bool radioGroupHadChecked = radioButtons.checkedButtonForGroup(name());
>      if (attached() && checked())
> -        checkedRadioButtons().addButton(this);
> +        radioButtons.addButton(this);
> +    bool radioGroupHasChecked = radioButtons.checkedButtonForGroup(name());
> +    if (radioGroupHadChecked == radioGroupHasChecked)
> +        return;

To understand the concept of this patch, one needs to look at RadioInputType::valueMissing. That’s where the rule about validity that is affected by radio button checking comes from. The division of code between HTMLInputElement and RadioInputType hides that, and it took me a long time to figure it out. There wasn’t even a comment that pointed specifically to “missing value” as the validity criterion that can change here. That’s a problem.

This patch doesn’t optimize all the cases it seems to attempt. By the time this function is called by HTMLInputElement::setChecked, the button has already been removed from checkedRadioButtons(). So it seems to me that setChecked(true) on a radio button that is already checked won’t get the optimization because radioGroupHadChecked will be false even though it should have been true. This case ought to be covered by a performance test.

Even for cases where the validity is in fact changing, I’d like to see us get rid of this massive performance cost for the very common case that the page is not using validity features at all. We shouldn’t walk the entire list of controls searching for other buttons in the group if nothing in the entire document is even looking at validity.

We should probably consider a design where we keep a complete set of all the radio buttons in a group for each group. We avoided that before and kept track of only the checked radio button, which was an elegant thing to do without validity. But now that we have added a feature where the checkedness of a radio button can affect all the other buttons, even unchecked ones, it’s no longer a good trick, at least for pages where validity is being used. It seems we should reconsider the data structure. We cannot get acceptable performance by walking the whole document the way we do in this function. The algorithm is proportional to the size of the entire document for radio buttons outside forms, not just the number of radio buttons, and that is unacceptable.

Even aside from the comments above I also think there are many things we should do to make the code readable and better. Not sure what order to do these in and what importance there is:

- Change the updateCheckedRadioButtons function’s name. The function does not “update” checked radio buttons. What it does is record the fact that this button is checked if it is, and uncheck the old checked button. It does only half the job, and HTMLInputElement::setChecked does the other half. Perhaps the reason it only does half the job is so it can be called by RadioInputType::attach and doesn’t waste time removing the button if it’s not already there, but if so that’s not a great reason. Maybe we need to refactor the function as well.

- Review HTMLInputElement::updateType and the code in HTMLInputElement::parseMappedAttribute for the name attribute, and figure out why it’s OK that these functions call CheckedRadioButtons::addButton directly without doing anything to update validity of other buttons in the group. My guess is that we could construct test cases showing there are bugs in those cases.

- Review HTMLInputElement::willMoveToNewOwnerDocument and HTMLInputElement::~HTMLInputElement and figure out why it’s OK that these functions call CheckedRadioButtons::removeButton without doing anything to update validity of other buttons in the group. Again, I suspect at least one of these is a bug. It’s also strange that ~HTMLInputElement removes the radio button from the document’s CheckedRadioButtons only, no the one from the form.

- Other functions that also manipulate the CheckedRadioButtons directly and probably handle the validation impact of this wrong include: HTMLFormControlElement::parseMappedAttribute for the form attribute, HTMLFormControlElement::insertedIntoTree, and HTMLFormElement::registerFormElement.

- In the code that does update validity, currently part of the updateCheckedRadioButtons function, we need to add a comment to make it clear how checking a radio button relates to validity. Specifically, if a group gets into the state where there is no checked button this affects the valueMissing state of all the radio buttons in that group.

- Since the validity updating in updateCheckedRadioButtons is specific to RadioInputType, that function should move into RadioInputType and out of HTMLInputElement. As should all manipulation of the checkedRadioButtons().

- Since CheckedRadioButtons already takes care of checking checked(), we should remove the redundant call to that function from HTMLInputElement::updateCheckedRadioButtons, unless it’s a helpful performance optimization. We should also investigate why HTMLInputElement::updateCheckedRadioButtons has to check attached(). Presumably CheckedRadioButtons::addButton should add that check too. Callers that are calling addButton without checking attached are probably doing it wrong. Maybe all the code in HTMLInputElement::updateCheckedRadioButtons should move into CheckedRadioButtons?

- If we still have them, the loops in updateCheckedRadioButtons should use isRadioButton instead of checking type() == type() to see if something is a radio button.

- For the the loops in updateCheckedRadioButtons we use an efficient way to check name equality. Calling name() ends up calling the virtual formControlName() function, all just to get at a field of HTMLInputElement. I don’t think we should go through a virtual function each time. I think we probably could compare m_name directly as long as we figure out what to do about null vs. empty values. In general it’s not good to have functions in HTMLInputElement going through a virtual function just to get at the m_name field with a bit of null value handling. We should override the name function in HTMLInputElement so that you can get the name instantly without a function call if you already have an HTMLInputElement*. We should put the special handling for null into HTMLInputElement::parseMappedAttribute rather than in HTMLInputElement::formControlName.

- Document::m_formElementsWithState should change to hold HTMLFormControlElement* instead of Element*, and all the functions should likewise change. I think the looser type is a remnant of WML support.

- The function HTMLInputElement::setDefaultName is strange and only used by HTMLIsIndexElement, so I suggest making it protected and giving it a different name.

[Kent Tamura]

Thank you for the loooong comment.

I'll try to make a perf test.
I won't make a single large patch to address all of your comments.  I'll focus on some points in the next patch.

(In reply to comment #4)
> To understand the concept of this patch, one needs to look at RadioInputType::valueMissing. That’s where the rule about validity that is affected by radio button checking comes from. The division of code between HTMLInputElement and RadioInputType hides that, and it took me a long time to figure it out. There wasn’t even a comment that pointed specifically to “missing value” as the validity criterion that can change here. That’s a problem.

Ok, I should have used InputType::valueMissing(), or HTMLFromControlEement::isValidFormControlElement() for readability.


> This patch doesn’t optimize all the cases it seems to attempt. By the time this function is called by HTMLInputElement::setChecked, the button has already been removed from checkedRadioButtons(). So it seems to me that setChecked(true) on a radio button that is already checked won’t get the optimization because radioGroupHadChecked will be false even though it should have been true. This case ought to be covered by a performance test.

You're right. The patch improves only a specific case.


> Even for cases where the validity is in fact changing, I’d like to see us get rid of this massive performance cost for the very common case that the page is not using validity features at all. We shouldn’t walk the entire list of controls searching for other buttons in the group if nothing in the entire document is even looking at validity.

If we can check existence of 'required' attribute in a radio group in O(1), we can skip the iteration in a case of no 'required'.  


> We should probably consider a design where we keep a complete set of all the radio buttons in a group for each group. We avoided that before and kept track of only the checked radio button, which was an elegant thing to do without validity. But now that we have added a feature where the checkedness of a radio button can affect all the other buttons, even unchecked ones, it’s no longer a good trick, at least for pages where validity is being used. It seems we should reconsider the data structure. We cannot get acceptable performance by walking the whole document the way we do in this function. The algorithm is proportional to the size of the entire document for radio buttons outside forms, not just the number of radio buttons, and that is unacceptable.

I'd like to avoid keeping a complete set of radio buttons if possible. I'll try to make alternative solution.


> Even aside from the comments above I also think there are many things we should do to make the code readable and better. Not sure what order to do these in and what importance there is:

> - Change the updateCheckedRadioButtons function’s name. The function does not “update” checked radio buttons. What it does is record the fact that this button is checked if it is, and uncheck the old checked button. It does only half the job, and HTMLInputElement::setChecked does the other half. Perhaps the reason it only does half the job is so it can be called by RadioInputType::attach and doesn’t waste time removing the button if it’s not already there, but if so that’s not a great reason. Maybe we need to refactor the function as well.
> 

> - Review HTMLInputElement::updateType and the code in HTMLInputElement::parseMappedAttribute for the name attribute, and figure out why it’s OK that these functions call CheckedRadioButtons::addButton directly without doing anything to update validity of other buttons in the group. My guess is that we could construct test cases showing there are bugs in those cases.

It's not ok. I found this problem yesterday and filed Bug 74914.

> - Review HTMLInputElement::willMoveToNewOwnerDocument and HTMLInputElement::~HTMLInputElement and figure out why it’s OK that these functions call CheckedRadioButtons::removeButton without doing anything to update validity of other buttons in the group. Again, I suspect at least one of these is a bug. It’s also strange that ~HTMLInputElement removes the radio button from the document’s CheckedRadioButtons only, no the one from the form.

I think it's not ok too. Whenever updating a CheckedRadioButtons, we should update the validity state of radio butons in the same group.

> - Other functions that also manipulate the CheckedRadioButtons directly and probably handle the validation impact of this wrong include: HTMLFormControlElement::parseMappedAttribute for the form attribute, HTMLFormControlElement::insertedIntoTree, and HTMLFormElement::registerFormElement.

ditto.

> - In the code that does update validity, currently part of the updateCheckedRadioButtons function, we need to add a comment to make it clear how checking a radio button relates to validity. Specifically, if a group gets into the state where there is no checked button this affects the valueMissing state of all the radio buttons in that group.
> 

> - Since the validity updating in updateCheckedRadioButtons is specific to RadioInputType, that function should move into RadioInputType and out of HTMLInputElement. As should all manipulation of the checkedRadioButtons().

Indeed!

> - Since CheckedRadioButtons already takes care of checking checked(), we should remove the redundant call to that function from HTMLInputElement::updateCheckedRadioButtons, unless it’s a helpful performance optimization. We should also investigate why HTMLInputElement::updateCheckedRadioButtons has to check attached(). Presumably CheckedRadioButtons::addButton should add that check too. Callers that are calling addButton without checking attached are probably doing it wrong. Maybe all the code in HTMLInputElement::updateCheckedRadioButtons should move into CheckedRadioButtons?

> - If we still have them, the loops in updateCheckedRadioButtons should use isRadioButton instead of checking type() == type() to see if something is a radio button.

> - For the the loops in updateCheckedRadioButtons we use an efficient way to check name equality. Calling name() ends up calling the virtual formControlName() function, all just to get at a field of HTMLInputElement. I don’t think we should go through a virtual function each time. I think we probably could compare m_name directly as long as we figure out what to do about null vs. empty values. In general it’s not good to have functions in HTMLInputElement going through a virtual function just to get at the m_name field with a bit of null value handling. We should override the name function in HTMLInputElement so that you can get the name instantly without a function call if you already have an HTMLInputElement*. We should put the special handling for null into HTMLInputElement::parseMappedAttribute rather than in HTMLInputElement::formControlName.
> 
> - Document::m_formElementsWithState should change to hold HTMLFormControlElement* instead of Element*, and all the functions should likewise change. I think the looser type is a remnant of WML support.
> 
> - The function HTMLInputElement::setDefaultName is strange and only used by HTMLIsIndexElement, so I suggest making it protected and giving it a different name.

[Kent Tamura]

I'm trying to change the CheckedRadioButtons::m_nameToCheckedRadioButtomMap so that it maps names to the following struct.

struct {
    HTMLInputElmeent* checkedControl;
    size_t memberCount;
    size_t requiredCount;
};

We need to keep the number of radio buttons with "required" attribute to check if the group needs validation.

[Darin Adler]

(In reply to comment #6)
> I'm trying to change the CheckedRadioButtons::m_nameToCheckedRadioButtomMap so that it maps names to the following struct.
> 
> struct {
>     HTMLInputElement* checkedControl;
>     size_t memberCount;
>     size_t requiredCount;
> };
> 
> We need to keep the number of radio buttons with "required" attribute to check if the group needs validation.

I think I would name this struct or class RadioButtonGroup. Then the map would be a map from a name to the radio button group of that name.

[Kent Tamura]

Created attachment 121991 [details]
WIP

[Kent Tamura]

(In reply to comment #8)
> Created an attachment (id=121991) [details]
> WIP

This is not ready for review. But comments are welcome.

[Darin Adler]

Comment on attachment 121991 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=121991&action=review

> Source/WebCore/dom/CheckedRadioButtons.cpp:126
> +    if (!m_members.size())
> +        return;

This check is not needed. An empty set can’t contain a member.

> Source/WebCore/dom/CheckedRadioButtons.cpp:127
> +    m_members.remove(element);

It’s not efficient to do a contains and then a remove; it does two table lookups when we could do only one. Instead, we should do a find, and then use iterator to remove the set element.

> Source/WebCore/dom/CheckedRadioButtons.cpp:129
> +    if (!m_members.size())
> +        return;

This can leave m_requiredCount set to non-zero and m_checkedButton set to non-zero, so it’s wrong to return early here.

> Source/WebCore/dom/CheckedRadioButtons.cpp:141
> +    return;

No need for this.

> Source/WebCore/dom/CheckedRadioButtons.cpp:163
> +// Provide empty constructor and destructor in order to avoid that a compiler
> +// generates them and requires RadioButtonGroup class during compiling Document.cpp.

Mentioning Document.cpp seems a little too specific here. Otherwise, a useful comment. I would say “explicitly define” rather than “provide”.

Also grammar mistake “avoid that a compiler generates them”. Could instead say in order to “prevent the compiler from generating them as inlines”.

> Source/WebCore/dom/CheckedRadioButtons.cpp:182
> +    NameToGroupMap::iterator i = m_nameToGroupMap->find(element->name().impl());
> +    if (i == m_nameToGroupMap->end())
> +        i = m_nameToGroupMap->set(element->name().impl(), RadioButtonGroup::create()).first;

The right idiom here is to use add, not find/set. Check for null for the value and then call create.

> Source/WebCore/dom/CheckedRadioButtons.cpp:196
> +    NameToGroupMap::iterator i = m_nameToGroupMap->find(element->name().impl());
> +    ASSERT(i != m_nameToGroupMap->end());
> +    i->second->updateCheckedState(element);

I suggest using get instead of find here.

> Source/WebCore/dom/CheckedRadioButtons.cpp:209
> +    NameToGroupMap::iterator i = m_nameToGroupMap->find(element->name().impl());
> +    ASSERT(i != m_nameToGroupMap->end());
> +    i->second->requiredAttributeChanged(element);

Also here. Use get instead of find.

> Source/WebCore/dom/CheckedRadioButtons.cpp:219
> +    NameToGroupMap::iterator i = m_nameToGroupMap->find(name.impl());
> +    return i == m_nameToGroupMap->end() ? 0 : i->second->checkedButton();

I suggest get instead of find.

> Source/WebCore/html/HTMLFormControlElement.h:118
> +    virtual void requiredAttributeChanged();

use OVERRIDE please

[Kent Tamura]

Created attachment 122595 [details]
Patch 3

[Kent Tamura]

Darin, would you take a look at the patch please?

[Darin Adler]

Comment on attachment 122595 [details]
Patch 3

View in context: https://bugs.webkit.org/attachment.cgi?id=122595&action=review

Seems OK, with room for improvement.

> Source/WebCore/dom/CheckedRadioButtons.cpp:34
> +    HTMLInputElement* checkedButton() { return m_checkedButton; }

Could be const.

> Source/WebCore/dom/CheckedRadioButtons.cpp:65
> +    if (m_members.contains(element))
> +        return;
> +
> +    m_members.add(element);

Calling contains followed by add does two hash table lookups. But add is written so it already does nothing if the set already contains the new member and it returns a boolean that indicates that happened.

The same thing can be done like this:

    if (!m_members.add(element).second)
        return;

I know that’s not terribly readable but it’s faster than contains/add. At some point we’ll rename “second” to “newEntryAdded” or something like that.

> Source/WebCore/dom/CheckedRadioButtons.cpp:66
> +    bool updateValidityStatusInGroup = false;

This is a verb phrase, and would be better if it was not. Maybe mustUpdateValidityForAllMembers, or something like that.

> Source/WebCore/dom/CheckedRadioButtons.cpp:69
> +        if (++m_requiredCount == 1)
> +            updateValidityStatusInGroup = true;

Why? The fact that a group changing from not-required to required creates the need to update the validity status of all radio buttons in a group is not self-evident; it needs a comment. Unless the code can somehow be structured so that it is self-evident.

For example, I would think that if the group has a checked button already, making the group required does not require updating the validity status. I am possibly wrong, but if so, reading this code wouldn’t clear things up for me.

> Source/WebCore/dom/CheckedRadioButtons.cpp:75
> +        ASSERT(oldCheckedButton != element);
> +        if (oldCheckedButton != element) {

There seems no chance this assertion will be false, so I think we should omit the if statement. The function already checks if the set contains the new element, and I believe m_checkedButton won’t ever be set to something not in the set.

> Source/WebCore/dom/CheckedRadioButtons.cpp:80
> +            else if (isRequired())
> +                updateValidityStatusInGroup = true;

What this code does is not self-evident; it needs a comment. I gather that what’s happening is that a group that has no checked button is now acquiring a checked button, and that means the other buttons in the group are now valid. But that required careful study to determine and was not obvious from the code structure. Perhaps the code can somehow be structured so that it is self-evident but otherwise we should add a suitable comment.

> Source/WebCore/dom/CheckedRadioButtons.cpp:86
> +    else if (isRequired())
> +        element->setNeedsValidityCheck();

Again, not clear why this is needed so needs a comment or different code structure.

> Source/WebCore/dom/CheckedRadioButtons.cpp:89
> +void RadioButtonGroup::updateCheckedState(HTMLInputElement* element)

Why not name this button instead of element? Generally speaking if the function can only be called with a radio button I think it’s good that we name the function that way.

> Source/WebCore/dom/CheckedRadioButtons.cpp:98
> +    if (element->checked()) {
> +        HTMLInputElement* oldCheckedButton = m_checkedButton;
> +        m_checkedButton = element;
> +        if (oldCheckedButton)
> +            oldCheckedButton->setChecked(false);
> +        else if (isRequired())
> +            updateButtonsValidity();

We need to find a way to share this logic with the “add already checked button” code above in RadioButtonGroup::add. It’s identical, except for the coalescing of the updateButtonsValidity call.

Should we also be asserting that element != m_checkedButton?

> Source/WebCore/dom/CheckedRadioButtons.cpp:105
> +        if (m_checkedButton == element) {
> +            m_checkedButton = 0;
> +            if (isRequired())
> +                updateButtonsValidity();
> +        }
> +    }

I’d like to see this share code with the remove function.

> Source/WebCore/dom/CheckedRadioButtons.cpp:113
> +    if (element->required()) {
> +        if (++m_requiredCount == 1)
> +            updateButtonsValidity();

I’d like to see this share code with the add function.

> Source/WebCore/dom/CheckedRadioButtons.cpp:118
> +        ASSERT(m_requiredCount);
> +        if (!--m_requiredCount)
> +            updateButtonsValidity();
> +    }

I’d like to see this share code with the remove function.

> Source/WebCore/dom/CheckedRadioButtons.cpp:133
> +    if (element->checked()) {
> +        m_checkedButton = 0;

Why check checked() rather than checking == m_checkedButton?

> Source/WebCore/dom/CheckedRadioButtons.cpp:152
> +void RadioButtonGroup::updateButtonsValidity()
> +{
> +    typedef HashSet<HTMLInputElement*>::const_iterator Iterator;
> +    Iterator end = m_members.end();
> +    for (Iterator it = m_members.begin(); it != end; ++it) {
> +        HTMLInputElement* control = *it;
> +        ASSERT(control->isRadioButton());
> +        control->setNeedsValidityCheck();
> +    }
> +}

I don’t like the difference in terminology here. This does not update the validity of the radio buttons. It sets a flag saying they need a validity check. That’s why the HTMLInputElement function is not named updateValidity.

> Source/WebCore/dom/CheckedRadioButtons.cpp:162
> +// Explicity define empty constructor and destructor in order to prevent the
> +// compiler from generating them as inlines and requiring RadioButtonGroup.

This comment should include the phrase “so we don’t need to define RadioButtonGroup in the header”. I don’t think that “requiring RadioButtonGroup” is clear enough.

> Source/WebCore/dom/CheckedRadioButtons.cpp:182
> +    NameToGroupMap::iterator it = m_nameToGroupMap->add(element->name().impl(), PassOwnPtr<RadioButtonGroup>()).first;
> +    if (!it->second)
> +        it->second = RadioButtonGroup::create();
> +    it->second->add(element);

I normally write these like this:

    RefPtr<RadioButtonGroup>& group = m_nameToGroupMap->add(element->name().impl(), PassOwnPtr<RadioButtonGroup>()).first->second;
    if (!group)
        group = RadioButtonGroup::create();
    group->add(element);

Your way has at least one advantage over mine; the iterator gets checked after the call to RadioButtonGroup::create, so if something crazy happens we will find out in debug builds. But I like mine better for readability.

> Source/WebCore/dom/CheckedRadioButtons.cpp:188
> +    if (!shouldMakeRadioGroup(element))
> +        return;

Is it more efficient to check shouldMakeRadioGroup, or to let the rest of the code run and end up doing nothing since the element is not in the set in the group? I would normally lean toward the latter.

> Source/WebCore/dom/CheckedRadioButtons.cpp:201
> +    if (!shouldMakeRadioGroup(element))
>          return;

Same comment as above.

> Source/WebCore/dom/CheckedRadioButtons.cpp:224
> +    if (!shouldMakeRadioGroup(element))
> +        return false;

Is all the logic in the shouldMakeRadioGroup function needed here? I worry that this is more overhead than we need.

> Source/WebCore/dom/CheckedRadioButtons.cpp:235
> +    if (!shouldMakeRadioGroup(element))
>          return;

Does this improve performance? I’d suggest leaving it out unless we think it does.

> Source/WebCore/dom/CheckedRadioButtons.cpp:248
> +    it->second->remove(element);
> +    if (it->second->isEmpty()) {
> +        m_nameToGroupMap->remove(it);
> +        if (m_nameToGroupMap->isEmpty())
> +            m_nameToGroupMap.clear();
> +    }

Deallocating these makes performance bad if we go from 0 to 1 and back and forth. Not deallocating them makes memory use bad if we have transient groups and leave behind empty data structures. I am not sure which is the right tradeoff.

> Source/WebCore/dom/CheckedRadioButtons.h:33
> +// FIXME: Rename the class.

This would be a better FIXME if it stated explicitly what we think is wrong with the current name.

> Source/WebCore/html/CheckboxInputType.cpp:54
> -    return !element()->checked();
> +    return element()->isRequiredFormControl() && !element()->checked();

It’s wasteful that isRequiredFormControl is a virtual function dispatch here. It’s nothing new, though.

> Source/WebCore/html/FileInputType.cpp:132
> -    return value.isEmpty();
> +    return element()->isRequiredFormControl() && value.isEmpty();

Ditto.

> Source/WebCore/html/HTMLFormControlElement.cpp:136
> +    // Updates for :required :optional classes.
> +    setNeedsStyleRecalc();

This comment, which you moved but did not change, is confusing grammar-wise. The phrase “updates for” could be a noun phrase. I would write:

    // Style recalculation is needed because style selectors may include :required and :optional pseudo-classes.

> Source/WebCore/html/HTMLInputElement.h:75
> +    virtual bool isRequiredFormControl() const OVERRIDE;

It’s unfortunate that this public function is virtual. Any caller that has an HTMLInputElement* could instead call a non-virtual version.

> Source/WebCore/html/RadioInputType.cpp:51
> -    return !element()->checkedRadioButtons().checkedButtonForGroup(element()->name());
> +    return element()->checkedRadioButtons().isInRequiredGroup(element()) && !element()->checkedRadioButtons().checkedButtonForGroup(element()->name());

Can a single radio button, not in a group, still be required? Or is that nonsense? If it is, do we have test cases for that?

[Kent Tamura]

Created attachment 123691 [details]
Patch for landing

[Kent Tamura]

Comment on attachment 122595 [details]
Patch 3

View in context: https://bugs.webkit.org/attachment.cgi?id=122595&action=review

>> Source/WebCore/dom/CheckedRadioButtons.cpp:34
>> +    HTMLInputElement* checkedButton() { return m_checkedButton; }
> 
> Could be const.

Done.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:65
>> +    m_members.add(element);
> 
> Calling contains followed by add does two hash table lookups. But add is written so it already does nothing if the set already contains the new member and it returns a boolean that indicates that happened.
> 
> The same thing can be done like this:
> 
>     if (!m_members.add(element).second)
>         return;
> 
> I know that’s not terribly readable but it’s faster than contains/add. At some point we’ll rename “second” to “newEntryAdded” or something like that.

Done.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:69
>> +            updateValidityStatusInGroup = true;
> 
> Why? The fact that a group changing from not-required to required creates the need to update the validity status of all radio buttons in a group is not self-evident; it needs a comment. Unless the code can somehow be structured so that it is self-evident.
> 
> For example, I would think that if the group has a checked button already, making the group required does not require updating the validity status. I am possibly wrong, but if so, reading this code wouldn’t clear things up for me.

You're right.  We need to update validity only if the group becomes required and has no checked button.

I update the RadioButtonGroup code like

bool wasValid = isValid();
 .....
if (wasValid != isValid())
    updateButtonValdity();

I think this change improved the code readability significantly.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:75
>> +        if (oldCheckedButton != element) {
> 
> There seems no chance this assertion will be false, so I think we should omit the if statement. The function already checks if the set contains the new element, and I believe m_checkedButton won’t ever be set to something not in the set.

done.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:89
>> +void RadioButtonGroup::updateCheckedState(HTMLInputElement* element)
> 
> Why not name this button instead of element? Generally speaking if the function can only be called with a radio button I think it’s good that we name the function that way.

Done.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:98
>> +            updateButtonsValidity();
> 
> We need to find a way to share this logic with the “add already checked button” code above in RadioButtonGroup::add. It’s identical, except for the coalescing of the updateButtonsValidity call.
> 
> Should we also be asserting that element != m_checkedButton?

I added RadioButtonGroup::setCheckedButton() to share the code.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:133
>> +        m_checkedButton = 0;
> 
> Why check checked() rather than checking == m_checkedButton?

I changed this to if (m_checkedButton == button).

>> Source/WebCore/dom/CheckedRadioButtons.cpp:152
>> +}
> 
> I don’t like the difference in terminology here. This does not update the validity of the radio buttons. It sets a flag saying they need a validity check. That’s why the HTMLInputElement function is not named updateValidity.

I renamed it to setNeedsValidityCheckForAllButtons().

>> Source/WebCore/dom/CheckedRadioButtons.cpp:162
>> +// compiler from generating them as inlines and requiring RadioButtonGroup.
> 
> This comment should include the phrase “so we don’t need to define RadioButtonGroup in the header”. I don’t think that “requiring RadioButtonGroup” is clear enough.

Done.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:182
>> +    it->second->add(element);
> 
> I normally write these like this:
> 
>     RefPtr<RadioButtonGroup>& group = m_nameToGroupMap->add(element->name().impl(), PassOwnPtr<RadioButtonGroup>()).first->second;
>     if (!group)
>         group = RadioButtonGroup::create();
>     group->add(element);
> 
> Your way has at least one advantage over mine; the iterator gets checked after the call to RadioButtonGroup::create, so if something crazy happens we will find out in debug builds. But I like mine better for readability.

Done.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:188
>> +        return;
> 
> Is it more efficient to check shouldMakeRadioGroup, or to let the rest of the code run and end up doing nothing since the element is not in the set in the group? I would normally lean toward the latter.

I thought the cost of HashMap<AtomicStringImpl*,...>::get() was higher than the cost of shouldMakeRadioGroup() because the key type is string and string hash is not a light operation.  I found HashMap<AtomicStringImpl*,...> didn't use StringHash, but PtrHash. Also, a radio button group owner (<form> or document) typically has a little number of groups.  I understand the hash lookup cost is not expensive here.

However, checking shouldMakeRadioGroup() is required.  For example, updateCheckedState() is called for a checkbox and a radio button not in a document tree, which might have a valid name(). We don't need to check name().isEmpty() here, but I think using a single function is good for simplicity and some assertions are helpful for avoiding inconsistent state of m_nameToGroupMap by future changes.

>> Source/WebCore/dom/CheckedRadioButtons.cpp:224
>> +        return false;
> 
> Is all the logic in the shouldMakeRadioGroup function needed here? I worry that this is more overhead than we need.

Changed to if (!element->inDocument()).
isInRequiredGroup() is called only by RadioInputType.  We don't need to check isRadioButton().

>> Source/WebCore/dom/CheckedRadioButtons.cpp:248
>> +    }
> 
> Deallocating these makes performance bad if we go from 0 to 1 and back and forth. Not deallocating them makes memory use bad if we have transient groups and leave behind empty data structures. I am not sure which is the right tradeoff.

I adde a FIXME comment.  We can't do it for now because m_nameToGroupMap doesn't own AtomicStringImpl objects.

>> Source/WebCore/dom/CheckedRadioButtons.h:33
>> +// FIXME: Rename the class.
> 
> This would be a better FIXME if it stated explicitly what we think is wrong with the current name.

Done.

>> Source/WebCore/html/CheckboxInputType.cpp:54
>> +    return element()->isRequiredFormControl() && !element()->checked();
> 
> It’s wasteful that isRequiredFormControl is a virtual function dispatch here. It’s nothing new, though.

Done.
We already have non-virtual required(). There are no reasons to use isRequiredFormControl().

>> Source/WebCore/html/HTMLFormControlElement.cpp:136
>> +    setNeedsStyleRecalc();
> 
> This comment, which you moved but did not change, is confusing grammar-wise. The phrase “updates for” could be a noun phrase. I would write:
> 
>     // Style recalculation is needed because style selectors may include :required and :optional pseudo-classes.

Done.

>> Source/WebCore/html/HTMLInputElement.h:75
>> +    virtual bool isRequiredFormControl() const OVERRIDE;
> 
> It’s unfortunate that this public function is virtual. Any caller that has an HTMLInputElement* could instead call a non-virtual version.

Reverted this part.

>> Source/WebCore/html/RadioInputType.cpp:51
>> +    return element()->checkedRadioButtons().isInRequiredGroup(element()) && !element()->checkedRadioButtons().checkedButtonForGroup(element()->name());
> 
> Can a single radio button, not in a group, still be required? Or is that nonsense? If it is, do we have test cases for that?

According to the HTML specification, such radio button can't be valueMissing().
I added a test case to fast/forms/ValidityState-valueMissing-radio.html.

[WebKit Review Bot]

Comment on attachment 123691 [details]
Patch for landing

Rejecting attachment 123691 [details] from commit-queue.

New failing tests:
media/audio-garbage-collect.html
Full output: http://queues.webkit.org/results/11212753

[Kent Tamura]

Committed r105710: <http://trac.webkit.org/changeset/105710>