Bug 33269 – Improve HTMLElement::tagPriority()

• Component: DOM
• Status: RESOLVED FIXED

[Kent Tamura]

HTMLElement::tagPriority() compares AtomicStringImpl pointers 18 times for a generic element such as <span>.

[Kent Tamura]

Created attachment 45992 [details]
Proposed patch

[WebKit Review Bot]

style-queue ran check-webkit-style on attachment 45992 [details] without any errors.

[Darin Adler]

Comment on attachment 45992 [details]
Proposed patch

> +struct Empty1IntHashTraits : HashTraits<int> {

This seems a slightly heavyweight wait of making this use a map. I wonder if there's some other clever approach that avoids custom hash traits.

One thing we could do is this:

    1) Increase all tag priorities by 1 in all the code.
    2) Use find and return a tag priority of 2 if we don't find anything, instead of using get.

I guess your way is probably better.

> +    static const bool emptyValueIsZero = false;
> +    static const bool needsDestruction = false;
> +    static int emptyValue() { return 1; }
> +    static void constructDeletedValue(int& slot) { slot = -1; }
> +    static bool isDeletedValue(int value) { return value == -1; }

There's no need for you to override needsDestruction, constructDeletedValue, or isDeletedValue. You can just use the inherited versions of those from the base class.

> +    DEFINE_STATIC_LOCAL(TagPriorityMap, tagPriorityMap, ());
> +    if (tagPriorityMap.isEmpty()) {
> +        tagPriorityMap.add(wbrTag.localName().impl(), 0);
> +
> +        tagPriorityMap.add(addressTag.localName().impl(), 3);
> +        tagPriorityMap.add(ddTag.localName().impl(), 3);
> +        tagPriorityMap.add(dtTag.localName().impl(), 3);
> +        tagPriorityMap.add(noscriptTag.localName().impl(), 3);
> +        tagPriorityMap.add(rpTag.localName().impl(), 3);
> +        tagPriorityMap.add(rtTag.localName().impl(), 3);
> +
> +        // 5 is same as <div>'s priority.
> +        tagPriorityMap.add(articleTag.localName().impl(), 5);
> +        tagPriorityMap.add(asideTag.localName().impl(), 5);
> +        tagPriorityMap.add(centerTag.localName().impl(), 5);
> +        tagPriorityMap.add(footerTag.localName().impl(), 5);
> +        tagPriorityMap.add(headerTag.localName().impl(), 5);
> +        tagPriorityMap.add(nobrTag.localName().impl(), 5);
> +        tagPriorityMap.add(rubyTag.localName().impl(), 5);
> +        tagPriorityMap.add(navTag.localName().impl(), 5);
> +        tagPriorityMap.add(sectionTag.localName().impl(), 5);
> +
> +        tagPriorityMap.add(noembedTag.localName().impl(), 10);
> +        tagPriorityMap.add(noframesTag.localName().impl(), 10);
> +
> +        // Return 1 for other tags. It's same as <span>.
> +        // This way custom tag name elements will behave like inline spans.
> +    }
>  
> -    // Same values as <span>.  This way custom tag name elements will behave like inline spans.
> -    return 1;
> +    return tagPriorityMap.get(localName().impl());
>  }

I think it would be best to put the code to initialize the map into a separate function, initializeTagPriorityMap, that takes the map as an argument. That will make the tagPriorityMap function easier to read and even ever so slightly more efficient since it will be smaller with better code locality.

Is there a guarantee that localName().impl() is never 0?

review- so you can at least take out the unneeded overrides

[Kent Tamura]

Created attachment 45999 [details]
Proposed patch (rev.2)

(In reply to comment #3)
> (From update of attachment 45992 [details])
> > +    static const bool emptyValueIsZero = false;
> > +    static const bool needsDestruction = false;
> > +    static int emptyValue() { return 1; }
> > +    static void constructDeletedValue(int& slot) { slot = -1; }
> > +    static bool isDeletedValue(int value) { return value == -1; }
> 
> There's no need for you to override needsDestruction, constructDeletedValue, or
> isDeletedValue. You can just use the inherited versions of those from the base
> class.

ok, I removed them.

> I think it would be best to put the code to initialize the map into a separate
> function, initializeTagPriorityMap, that takes the map as an argument. That
> will make the tagPriorityMap function easier to read and even ever so slightly
> more efficient since it will be smaller with better code locality.

Done.

> Is there a guarantee that localName().impl() is never 0?

I think so for the current code though there is no ASSERTION for it.
However, 0 makes no problems because the HashMap key is AtomicStringImpl*. The generic PtrHash is used and tagPriorityMap.get(0) simply returns emptyValue().

[WebKit Review Bot]

style-queue ran check-webkit-style on attachment 45999 [details] without any errors.

[Darin Adler]

(In reply to comment #4)
> (In reply to comment #3)
> > Is there a guarantee that localName().impl() is never 0?
> 
> I think so for the current code though there is no ASSERTION for it.
> However, 0 makes no problems because the HashMap key is AtomicStringImpl*. The
> generic PtrHash is used and tagPriorityMap.get(0) simply returns emptyValue().

That's not true.

If you call tagPriorityMap.get(0) there’s a chance that you could get an uninitialized value from an empty hash table entry. There is no special check for the empty value and if the value you pass hashes to a slot that has a 0 in it, then it will return the value in that slot.

It is *not* safe to call get(0).

[Darin Adler]

Comment on attachment 45999 [details]
Proposed patch (rev.2)

> +// TagPriorityMap returns 1 for unregistered tags. It's same as <span>.
> +// This way custom tag name elements will behave like inline spans.

I think this comment should be at the bottom of initializeTagPriorityMap.

> +static const TagPriorityMap* initializeTagPriorityMap()

Given that this actually creates the map too, I suggest naming it createTagPriorityMap.

r=me assuming that localName().impl() is *not* ever 0

If it can be zero, then this patch is not OK.

[Kent Tamura]

I have confirmed that impl() never be null, and this is off-topic. But I'd like to understand this.

(In reply to comment #6)
> > However, 0 makes no problems because the HashMap key is AtomicStringImpl*. The
> > generic PtrHash is used and tagPriorityMap.get(0) simply returns emptyValue().
> 
> That's not true.
> 
> If you call tagPriorityMap.get(0) there’s a chance that you could get an
> uninitialized value from an empty hash table entry. There is no special check
> for the empty value and if the value you pass hashes to a slot that has a 0 in
> it, then it will return the value in that slot.
> 
> It is *not* safe to call get(0).

I read the code of HashTable.h and HashMap.h, and still wonder why it is not safe.
You are talking about a case of empty HashTable, and it's safe for non-empty HashTable, right?
In the empty case, HashTable::m_table is 0 and HashTable::lookup() seems to return (Value*)0 correctly for any keys. HashMap::get() returns emptyValue() for (Value*)0.
I couldn't find a case that HashMap::get() returns uninitialized value.

[Kent Tamura]

(In reply to comment #7)
> (From update of attachment 45999 [details])
> > +// TagPriorityMap returns 1 for unregistered tags. It's same as <span>.
> > +// This way custom tag name elements will behave like inline spans.
> 
> I think this comment should be at the bottom of initializeTagPriorityMap.

Moved it.

> 
> > +static const TagPriorityMap* initializeTagPriorityMap()
> 
> Given that this actually creates the map too, I suggest naming it
> createTagPriorityMap.

Renamed it.

> r=me assuming that localName().impl() is *not* ever 0
> 
> If it can be zero, then this patch is not OK.

I read the HTMLParser, HTMLTokenizer, HTMLDocument, Document classes carefully and confirmed localName() never be null.  I also confirmed all LayoutTests passed with ASSERT(localName().impl()).
I'll add this assertion and will commit it.

[Kent Tamura]

Landed as r52899 <http://trac.webkit.org/changeset/52899>

[Darin Adler]

(In reply to comment #8)
> I read the code of HashTable.h and HashMap.h, and still wonder why it is not
> safe.
> You are talking about a case of empty HashTable, and it's safe for non-empty
> HashTable, right?

I am talking about a non-empty map.

HashTable::lookup will hash the empty key and get a hash value of 0, then the loop will look at the 0'th bucket in the hash table and if it is an empty bucket, will return a pointer to it. I believe the empty bucket is guaranteed to have a key of zero, but could easily have a value that's non-zero.

That's how I understand the code. There may be something wrong with my analysis.

In general, I have long believed that both the empty and deleted values are illegal as arguments to the HashTable::lookup function. I believe we need assertions to catch cases like that to make correct programming with this class template easier.

[Kent Tamura]

(In reply to comment #11)

I catch you.

HashTraits<P*> has emptyValueisZero=true, and HashTable::checkKey() called by HashTable::lookup() has
  ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));

It's enough for the reason of the wrong HashMap::get(0).

Thank you!