Bug 40197 - Enhance the hit testing to take a rectangle instead of a point
Summary: Enhance the hit testing to take a rectangle instead of a point
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar, Qt, QtTriaged
Depends on: 41081
Blocks: 36111 40477 44089
  Show dependency treegraph
 
Reported: 2010-06-04 18:15 PDT by Grace Kloba
Modified: 2010-09-23 17:08 PDT (History)
21 users (show)

See Also:


Attachments
first in-progress patch (28.99 KB, patch)
2010-06-06 12:37 PDT, Grace Kloba
no flags Details | Formatted Diff | Diff
remove the tab (28.99 KB, patch)
2010-06-06 12:44 PDT, Grace Kloba
no flags Details | Formatted Diff | Diff
rect-based hitTest prototype patch (94.19 KB, patch)
2010-06-09 20:31 PDT, Antonio Gomes
no flags Details | Formatted Diff | Diff
updated patch based on the comment (28.82 KB, patch)
2010-06-13 20:08 PDT, Grace Kloba
no flags Details | Formatted Diff | Diff
updated patch based on the comment (28.94 KB, patch)
2010-06-14 10:42 PDT, Grace Kloba
no flags Details | Formatted Diff | Diff
patch v1 - feature + tests (48.31 KB, patch)
2010-06-25 13:15 PDT, Antonio Gomes
no flags Details | Formatted Diff | Diff
patch v2 - feature + tests (53.32 KB, patch)
2010-07-07 13:34 PDT, Antonio Gomes
tonikitoo: commit-queue-
Details | Formatted Diff | Diff
patch v3 - feature + tests (53.59 KB, patch)
2010-07-19 19:17 PDT, Antonio Gomes
no flags Details | Formatted Diff | Diff
patch v4 - feature + tests (54.98 KB, patch)
2010-07-21 06:31 PDT, Antonio Gomes
tonikitoo: commit-queue-
Details | Formatted Diff | Diff
patch v5 - feature + tests (56.22 KB, patch)
2010-07-22 10:43 PDT, Antonio Gomes
no flags Details | Formatted Diff | Diff
patch v6 - feature + tests (57.60 KB, patch)
2010-07-23 12:11 PDT, Antonio Gomes
hyatt: review-
hyatt: commit-queue-
Details | Formatted Diff | Diff
patch v7 - feature + tests (57.38 KB, patch)
2010-07-26 07:16 PDT, Antonio Gomes
no flags Details | Formatted Diff | Diff
(commit=r64272, r=hyatt )patch v7.1 - feature + tests (57.46 KB, patch)
2010-07-27 15:53 PDT, Antonio Gomes
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Grace Kloba 2010-06-04 18:15:27 PDT
As discussed in the following thread, there is a need, especially on the mobile browsers, to support hit testing with a rectangle instead of just a point.

https://lists.webkit.org/pipermail/webkit-dev/2010-June/013055.html

We would like to explore in this area. The idea is to modify the HitTestResult to take a padding. If it is 0, it is the current point based hit testing. If it is non-zero, hit test logic will continue searching when it finds a candidate unless the rectangle is fully enclosed by the candidate. The result will be a list of Node in the z-order they are hit-tested. The caller will decide how to process them.

We have some working in progress code. We can provide a patch for easy discussion.
Comment 1 David Kilzer (:ddkilzer) 2010-06-05 02:48:58 PDT
<rdar://problem/7244301>
Comment 2 Grace Kloba 2010-06-06 10:14:26 PDT
I would like to modify hitTestResultAtPoint() with an extra parameter. How do I re-generate WebCore.base.exp?
Comment 3 mitz 2010-06-06 10:17:50 PDT
(In reply to comment #2)
> I would like to modify hitTestResultAtPoint() with an extra parameter. How do I re-generate WebCore.base.exp?

That file is not generated. After you change the method prototype, when you try to build you will get link errors including the mangled names for the old, and then for the new method prototypes . You then need to add the new name to the exports file, remove the old name, and sort the file in ASCII order.
Comment 4 Grace Kloba 2010-06-06 12:37:53 PDT
Created attachment 57979 [details]
first in-progress patch

This is an in-progress patch. The goal is to get the feedback from the broader audience.

The key change is EventHandler::hitTestResultAtPoint(). If the pointPadding is (0, 0), the functionality should be identical as before. If pointPadding is not empty, we will do a region test. Inside the returned HitTestResult, besides innerNode() you can also get a list of Node overlapped with the "fat" point by calling rawNodeList(). The Nodes are ordered based on z-order.

There are couple of open issues.
1. currently all the Nodes are in the same widget/frame as the innerNode(), do we need to support Nodes from different frames? (See code in EventHandler.cpp)

2. currently it doesn't extend isPointInOverflowControl() for the region test, is it needed? (See RenderBlock.cpp)

3. currently it doesn't support SVG. (See RenderSVGRoot.cpp)

4. currently there is no special treatment for transform3D as I don't know what to do. (See RenderLayer.cpp)

5. need suggestion on writing layout test
Comment 5 WebKit Review Bot 2010-06-06 12:39:53 PDT
Attachment 57979 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style', '--no-squash']" exit_code: 1
WebCore/rendering/HitTestResult.cpp:381:  Tab found; better to use spaces  [whitespace/tab] [1]
Total errors found: 1 in 18 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 6 Grace Kloba 2010-06-06 12:44:19 PDT
Created attachment 57980 [details]
remove the tab
Comment 7 Antonio Gomes 2010-06-09 20:31:56 PDT
Created attachment 58324 [details]
rect-based hitTest prototype patch

Hi Grace. Since I also starting to look at the same problem (last Monday), I ended up with a similar patch/prototype, but whose approach is different enough that I think it might be good to upload it so we could compare the differences and decide the way to go.

Summary of my prototype patch: main idea is to really have a rect-based HitTest system. So all revelant XXXAtPoint methods were modified to receive a Rect as parameter, instead of pointer, and renamed accordingly to XXXAtArea.

Details:
- EventHandler::hitTestResultAtPoint was also the codepath start point for my approach.

- EventHandler::hitTestResultAtArea method was added, and the previosly existing hitTestResultAtPoint just falls back to it.

- nodeAtPoint methods throughout the rendering code were renamed to nodeAtArea,
and changed to take a rect ("hitTestArea") as parameter, instead of a point ("x" and "y"). Method bodies were also adapted accordingly where needed.
    
- Base rendering classes like RenderObject and InlineBox still have nodeAtPoint
methods, but falling back to nodeAtArea, and of course, passing something like IntRect(x, y, 1, 1) as the hit area to it.
    
- The various updateHitTestResult methods were changed so that each Node whose render bounds intersects the hit test area are added into a Vector in the HitTestResult class.
    
- A new constructor was added HitTestResult class, receiving a IntRect as parameter.Previous existing constructors that receive a IntPoint now fallback to the new one passing IntRect(point, IntSize(1, 1)).
    
Limitations:
- SVG classes were not modified yet.

I ran layout tests on a Mac with the patch applied and there was no regressions. However, I have not had time to think of a good testing infrastructure for it, so no new tests were added so far.
Comment 8 Antonio Gomes 2010-06-09 20:47:32 PDT
Although I strongly believe that both approaches here end up in the same results (even as-are), I will try to summarize the basic difference between grace's (attachment 57980 [details]) and mine (attachment 58324 [details]).

From my understanding, the former makes the HitTest system "rect-aware" in the sense that it keeps the core logic of nodeAtPoint methods as point-based, but adjusts them to take a rect (a point + a padding area) into consideration.

On the other hand, the later makes the HitTest really rect-based in the sense that it changes all nodeAtPoint existent methods to be nodeAtArea ones, and of course their method so their method bodies where needed. 

The difference is silly, but exists. We have just to decide how to proceed from that point on. Whatever direction is decided, I am up to join efforts with Grace to fix it.

Please, comments needed...
Comment 9 Grace Kloba 2010-06-10 10:40:01 PDT
Thanks Antonio to provide another patch. Here is what I thought.

The difference between the point with a padding or rectangle is just name difference. We should be easily to reach agreement with which direction we want to take. I don't have the strong preference. The reason I chose to use point with a padding is that it preserves the old code. So less changes to make. And I think it matches what happened on a mobile device. When user touches the screen, it is a point with a fuzzy size.

The big difference I see is as following.

In the first patch I provided, the traversing for nodeAtPoint is not stopped when the "fat" point intersects with the node bounds. The traversing only stops when the "fat" point is fully enclosed by the node bounds. In the latter patch Antonio provided, if I understand correctly, the traversing breaks when the rectangle intersects with the node bounds.

Here is an example,

<div id="a">
  <div id="b">
    <div id="c"> one </div>
    <div id="d"> two </div>
  </div>
  <div id="e"> three
  </div>
</div>

assuming the point is in-between "one" and "two", and the rectangle covers half "one" and half "two".

With the first patch, the returned node list will contain the nodes in this order, "d" "c" "b". When we detect the "fat" point intersects with "d", we continue the search as the "fat" point is not fully contained by "d". We found "c", and then go back to hit test "b"'s background. Now the "fat" point is fully contained. The search stops.

If I read the latter patch correctly, the nodes returned will be in this order, "d" "b" "a". When the rectangle intersects with "d", it returned. Its parent "b" and "a" are added into the list.
Comment 10 Antonio Gomes 2010-06-10 13:27:49 PDT
I have no preference, since both fit well for the needs, Grace.

> The big difference I see is as following.
> In the first patch I provided, the traversing for nodeAtPoint is not stopped when the "fat" point intersects with the node bounds. The traversing only stops when the "fat" point is fully enclosed by the node bounds. In the latter patch Antonio provided, if I understand correctly, the traversing breaks when the rectangle intersects with the node bounds.

If it does way, yes it should be fix{ed,able}. I will re-check now.
Comment 11 Dave Hyatt 2010-06-10 14:23:50 PDT
I like the point padding approach (Grace's patch), mainly because it's very minimally intrusive, and it lets the code read in such a way that someone just looking at point-based hit testing doesn't get confused by the "area' terminology.

Both patches seem to be using Vector node lists to collect the nodes.  It seems like a HashSet would be better to avoid crawling the list looking for the Node before adding it.
Comment 12 Dave Hyatt 2010-06-10 14:27:12 PDT
By the way, one caveat with collecting multiple nodes is that you may need to distinguish between hit test layers (e.g., background of one element vs. foreground of another).  If I'm understanding this right, the patches just collect the nodes and don't really distinguish between a foreground hit and a background hit.  I suspect that information may end up being needed but am not sure.
Comment 13 Grace Kloba 2010-06-10 15:19:23 PDT
(In reply to comment #12)
> By the way, one caveat with collecting multiple nodes is that you may need to distinguish between hit test layers (e.g., background of one element vs. foreground of another).  If I'm understanding this right, the patches just collect the nodes and don't really distinguish between a foreground hit and a background hit.  I suspect that information may end up being needed but am not sure.

That is an interesting point. The hit test layer info may be useful when processing the nodes. But I don't know yet. 

The current traversing honors when the node is hit. So the foreground will be added first. And if background is also hit, it will be ignored.

BTW, I think the early comment of HashSet vs. Vector is valid. I will change the code in the next path.

I would like to get more feedback before providing the next path.
Comment 14 Antonio Gomes 2010-06-11 07:24:22 PDT
Comment on attachment 57980 [details]
remove the tab

patch looks promissing, as I mentioned earlier. Some comments and questions below.

> +        if (result.isRegionTest()) {
> +            ASSERT(renderer()->node() || renderer()->isAnonymous());
> +            result.addRawNode(renderer()->node());
> +            if (!result.containedBy(x, y, boundsRect))
> +                return false;
> +        }

You seem to been doing this in 6 or 7 other places. Code looks exactly the same. Why not put this code in updateHitTestResult? Even less code modified in the end.

> +bool HitTestResult::intersects(int x, int y, const IntRect& other) const
> +{
> +    IntRect pointRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
> +    return other.intersects(pointRect);
> +}
> +
> +bool HitTestResult::containedBy(int x, int y, const IntRect& other) const
> +{
> +    IntRect pointRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
> +    return other.contains(pointRect);
> +}
> +

I would make an inline or a static method for this line:
IntRect pointRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);

> +void HitTestResult::merge(const HitTestResult& other)
> +{
> +    if (!m_innerNode && other.innerNode()) {
> +        m_innerNode = other.innerNode();
> +        m_innerNonSharedNode = other.innerNonSharedNode();
> +        m_localPoint = other.localPoint();
> +        m_innerURLElement = other.URLElement();
> +        m_scrollbar = other.scrollbar();
> +         m_isOverWidget = other.isOverWidget();
> +    }

as far as I could see, merge is only used on Region test, right? If so, i would bail out earlier here if not region test or ASSERT for safety.

Also, HitTestResult overwrites the "=" operator. Why not just do use it? Is it because you do not want other's m_rawNodeList to be assigned to it?

> +    const Vector<RefPtr<Node> >& list = other.rawNodeList();
> +    Vector<RefPtr<Node> >::const_iterator last = list.end();
> +    for (Vector<RefPtr<Node> >::const_iterator it = list.begin(); it != last; ++it)
> +        addRawNode(it->get());
> +}
> +
> +void HitTestResult::addRawNode(Node* node)
> +{
> +    if (!node)
> +        return;

bail out here to if not region test?

Also, current logic only needs height and width of the padding rect . Why not use a IntSize instead of a IntRect?
Comment 15 Antonio Gomes 2010-06-11 09:23:04 PDT
(In reply to comment #11)
> I like the point padding approach (Grace's patch), mainly because it's very minimally intrusive, and it lets the code read in such a way that someone just looking at point-based hit testing doesn't get confused by the "area' terminology.
> 
> Both patches seem to be using Vector node lists to collect the nodes.  It seems like a HashSet would be better to avoid crawling the list looking for the Node before adding it.

> By the way, one caveat with collecting multiple nodes is that you may need to distinguish between hit test layers (e.g., background of one element vs. foreground of another).  If I'm understanding this right, the patches just collect the nodes and don't really distinguish between a foreground hit and a background hit.  I suspect that information may end up being needed but am not sure.

About hyatt's suggestion, I have one concern: by using a Vector we
have for free the z-order (background elements are hittest'ed before foreground nes- see RenderLayer::hitTestLayer). With a hash we would gain performance on adding a new node to the rawNodeList, since we would not need to traverse it to verify if it has been already added, but lose the order.

@hyatt, please correct if I am wrong.
Comment 16 Grace Kloba 2010-06-11 09:33:25 PDT
(In reply to comment #15)
> (In reply to comment #11)
> > I like the point padding approach (Grace's patch), mainly because it's very minimally intrusive, and it lets the code read in such a way that someone just looking at point-based hit testing doesn't get confused by the "area' terminology.
> > 
> > Both patches seem to be using Vector node lists to collect the nodes.  It seems like a HashSet would be better to avoid crawling the list looking for the Node before adding it.
> 
> > By the way, one caveat with collecting multiple nodes is that you may need to distinguish between hit test layers (e.g., background of one element vs. foreground of another).  If I'm understanding this right, the patches just collect the nodes and don't really distinguish between a foreground hit and a background hit.  I suspect that information may end up being needed but am not sure.
> 
> About hyatt's suggestion, I have one concern: by using a Vector we
> have for free the z-order (background elements are hittest'ed before foreground nes- see RenderLayer::hitTestLayer). With a hash we would gain performance on adding a new node to the rawNodeList, since we would not need to traverse it to verify if it has been already added, but lose the order.
> 
> @hyatt, please correct if I am wrong.

I agree with Antonio. In my original checkin comment, I mentioned that all the Nodes are ordered based on z-order. This is important for the caller to filter through them to find the final Node.
Comment 17 Grace Kloba 2010-06-11 09:42:06 PDT
(In reply to comment #14)
> (From update of attachment 57980 [details])
> patch looks promissing, as I mentioned earlier. Some comments and questions below.
> 
> > +        if (result.isRegionTest()) {
> > +            ASSERT(renderer()->node() || renderer()->isAnonymous());
> > +            result.addRawNode(renderer()->node());
> > +            if (!result.containedBy(x, y, boundsRect))
> > +                return false;
> > +        }
> 
> You seem to been doing this in 6 or 7 other places. Code looks exactly the same. Why not put this code in updateHitTestResult? Even less code modified in the end.
> 

This is only done when we test two rectangle intersection. If updateHitTestResult is called as a result of nodeAtPoint() return true or similar, we won't do this.

Also we need to do rectangle containedBy test to decide whether it will continue the traverse or break. The rect is not available in all the cases.

> > +bool HitTestResult::containedBy(int x, int y, const IntRect& other) const
> > +{
> > +    IntRect pointRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
> > +    return other.contains(pointRect);
> > +}
> > +
> 
> I would make an inline or a static method for this line:
> IntRect pointRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
> 

Sure, inline private method is fine.

> > +void HitTestResult::merge(const HitTestResult& other)
> > +{
> > +    if (!m_innerNode && other.innerNode()) {
> > +        m_innerNode = other.innerNode();
> > +        m_innerNonSharedNode = other.innerNonSharedNode();
> > +        m_localPoint = other.localPoint();
> > +        m_innerURLElement = other.URLElement();
> > +        m_scrollbar = other.scrollbar();
> > +         m_isOverWidget = other.isOverWidget();
> > +    }
> 
> as far as I could see, merge is only used on Region test, right? If so, i would bail out earlier here if not region test or ASSERT for safety.
> 

Done.

> Also, HitTestResult overwrites the "=" operator. Why not just do use it? Is it because you do not want other's m_rawNodeList to be assigned to it?
> 

Merge is combination while "=" is replacement.

> > +void HitTestResult::addRawNode(Node* node)
> > +{
> > +    if (!node)
> > +        return;
> 
> bail out here to if not region test?
> 

Done.

> Also, current logic only needs height and width of the padding rect . Why not use a IntSize instead of a IntRect?

Which IntRect do you refer to?
Comment 18 Antonio Gomes 2010-06-11 11:10:07 PDT
Comment on attachment 57980 [details]
remove the tab

> +bool HitTestResult::intersects(int x, int y, const IntRect& other) const
> +{
> +    IntRect pointRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
> +    return other.intersects(pointRect);
> +}

Do you really need pass 'x' and 'y' for intersects? The are the same as the original hit test point it seems.

maybe:

bool HitTestResult::intersects(const IntRect& other) const
{
    IntRect pointRect(m_point.x() - m_pointPadding.width(), m_point.y() - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
    return other.intersects(pointRect);
}

with call sites changed to pass just the 'other' rect?
Comment 19 Dave Hyatt 2010-06-11 13:31:51 PDT
ListHashSet lets you preserve ordering while still having hash lookups.
Comment 20 Grace Kloba 2010-06-12 18:15:36 PDT
> Do you really need pass 'x' and 'y' for intersects? The are the same as the original hit test point it seems.
> 

I believe I do. Most of the time, "x" and "y" are passed into nodeAtPoint as they have been translated to local. Otherwise, the original code can always get x/y from HitTestResult.
Comment 21 Grace Kloba 2010-06-12 18:16:13 PDT
(In reply to comment #19)
> ListHashSet lets you preserve ordering while still having hash lookups.

Sounds good. I will use it in the next patch.
Comment 22 Grace Kloba 2010-06-13 20:08:04 PDT
Created attachment 58617 [details]
updated patch based on the comment
Comment 23 WebKit Review Bot 2010-06-13 20:11:08 PDT
Attachment 58617 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style', '--no-squash']" exit_code: 1
WebCore/rendering/HitTestResult.h:28:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 18 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 24 Antonio Gomes 2010-06-14 08:27:51 PDT
Comment on attachment 58617 [details]
updated patch based on the comment

Good progresses! Please see some more questions and comments below.

> +bool HitTestResult::addRawNodeForRegionTest(Node* node, int x, int y, const IntRect& rect)
> +{
> +    if (!isRegionTest() || !node)
> +        return false;
> +
> +    m_rawNodeList.add(node);
> +
> +    return !rect.contains(pointRect(x, y));
> +}

I'd add a comment here explaning why it is important to return true only if rect encloses pointRect(x,y): because call side can stop hittest in such cases.

> +    IntSize pointPadding() const { return m_pointPadding; }

maybe just padding()?

> +    IntRect pointRect(int x, int y) const;
> +    IntRect pointRect(const IntPoint&) const;

maybe rename these to hit{Area,Region}FromPoint ? pointRect is kinda meaningless.

> +inline IntRect HitTestResult::pointRect(int x, int y) const
> +{
> +    return IntRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
> +}

hum, I missed the point on why +1 here. Could you explain? If that for cases when padding is IntSize(0,0)

if that is the case, just set it to IntSize(1,1) in the point-only constructor.

HitTestResult::HitTestResult(const IntPoint& point)
    : m_point(point)
    , m_padding(1, 1)
    , m_isOverWidget(false)
{
}


I will work on tests on top of this one for now.
Comment 25 Grace Kloba 2010-06-14 08:41:50 PDT
(In reply to comment #24)
> (From update of attachment 58617 [details])
> Good progresses! Please see some more questions and comments below.
> 
> > +bool HitTestResult::addRawNodeForRegionTest(Node* node, int x, int y, const IntRect& rect)
> > +{
> > +    if (!isRegionTest() || !node)
> > +        return false;
> > +
> > +    m_rawNodeList.add(node);
> > +
> > +    return !rect.contains(pointRect(x, y));
> > +}
> 
> I'd add a comment here explaning why it is important to return true only if rect encloses pointRect(x,y): because call side can stop hittest in such cases.
> 

I was thinking of adding a comment in the header file. But I noticed that most of the WebKit methods do not have comments. Not sure whether it is style or not. Anyway, I will add one in the header file for this. 

> > +    IntSize pointPadding() const { return m_pointPadding; }
> 
> maybe just padding()?
> 

I assume you meant both variable and method name. Sure I can change it if it makes more sense.

> > +    IntRect pointRect(int x, int y) const;
> > +    IntRect pointRect(const IntPoint&) const;
> 
> maybe rename these to hit{Area,Region}FromPoint ? pointRect is kinda meaningless.
> 

Done.

> > +inline IntRect HitTestResult::pointRect(int x, int y) const
> > +{
> > +    return IntRect(x - m_pointPadding.width(), y - m_pointPadding.height(), 2 * m_pointPadding.width() + 1, 2 * m_pointPadding.height() + 1);
> > +}
> 
> hum, I missed the point on why +1 here. Could you explain? If that for cases when padding is IntSize(0,0)
> 

As IntRect is left inclusive and right exclusive, seeing IntRect::contains(x, y), I think we should do (2 * padding + 1).

> if that is the case, just set it to IntSize(1,1) in the point-only constructor.
> 
> HitTestResult::HitTestResult(const IntPoint& point)
>     : m_point(point)
>     , m_padding(1, 1)
>     , m_isOverWidget(false)
> {
> }
> 
> 
> I will work on tests on top of this one for now.
Comment 26 Grace Kloba 2010-06-14 09:31:04 PDT
Off topic question. I try to run "check-webkit-style" myself. But I get the following error. Anyone know how to fix it? Thanks in advance.

$ WebKitTools/Scripts/check-webkit-style 
Traceback (most recent call last):
  File "WebKitTools/Scripts/check-webkit-style", line 51, in ?
    from webkitpy.style_references import detect_checkout
  File "/Development/appleWebKit/WebKitTools/Scripts/webkitpy/style_references.py", line 56
    return None if scm is None else WebKitCheckout(scm)
Comment 27 David Kilzer (:ddkilzer) 2010-06-14 09:33:02 PDT
(In reply to comment #26)
> Off topic question. I try to run "check-webkit-style" myself. But I get the following error. Anyone know how to fix it? Thanks in advance.
> 
> $ WebKitTools/Scripts/check-webkit-style 
> Traceback (most recent call last):
>   File "WebKitTools/Scripts/check-webkit-style", line 51, in ?
>     from webkitpy.style_references import detect_checkout
>   File "/Development/appleWebKit/WebKitTools/Scripts/webkitpy/style_references.py", line 56
>     return None if scm is None else WebKitCheckout(scm)

It looks like you're not in (the top directory of) the WebKit source when you're running the command.
Comment 28 Grace Kloba 2010-06-14 09:36:23 PDT
(In reply to comment #27)
> It looks like you're not in (the top directory of) the WebKit source when you're running the command.

Thanks for the prompt reply. I am at the directory where I call the other script, like "WebKitTools/Scripts/build-webkit". Any other thing I should try?
Comment 29 David Kilzer (:ddkilzer) 2010-06-14 09:47:54 PDT
(In reply to comment #28)
> (In reply to comment #27)
> > It looks like you're not in (the top directory of) the WebKit source when you're running the command.
> 
> Thanks for the prompt reply. I am at the directory where I call the other script, like "WebKitTools/Scripts/build-webkit". Any other thing I should try?

Ping David Levin on IRC?  Are you passing any paths on the command line?  Review "check-webkit-style -h"?
Comment 30 Simon Fraser (smfr) 2010-06-14 10:00:56 PDT
(In reply to comment #25)
> I was thinking of adding a comment in the header file. But I noticed that most of the WebKit methods do not have comments. Not sure whether it is style or not. Anyway, I will add one in the header file for this. 

This is not a good convention to follow. Please add comments!
Comment 31 Grace Kloba 2010-06-14 10:42:31 PDT
Created attachment 58669 [details]
updated patch based on the comment

I still have trouble running check-webkit-style script. Still wait for answer from IRC.
Comment 32 Antonio Gomes 2010-06-25 13:15:22 PDT
Created attachment 59789 [details]
patch v1 - feature + tests

This new patch (named 'v1') comprises previous work done by Grace (see obsolete patches), as well as a testing infrastructure for the rect-based hit test feature.

As ways to expose the functionality, the patch:

- adds a nodesFromRect method to the Document class, exposing the funcionality to the DOM. Method returns a NodeList with all nodes that intersect the given hit-tested area.
- extends hitTestResultAtPoint method of the EventHandler with an extra 'padding' parameter, defaulting to IntSize(0,0). The rect-based hit test is performed when a non-zero padding is passed in.

If padding is IntSize(0,0) or omitted, point based HitTest is performed.
Comment 33 Antonio Gomes 2010-06-25 13:32:32 PDT
(In reply to comment #32)
> Created an attachment (id=59789) [details]
> patch v1 - feature + tests

Things yet to be done (probably in follow up work):

- Adds more test coverage for:
* transformed content case;
* <iframe> hit test case;
* etc.

- refine our DOM API for this. It is currently Document::nodesFromRect(int x, int y, int horizontalPadding, int verticalPaddin), taking vertical and horizontal padding values.

fwiw, firefox' is similarly padding-based, but takes padding for each of the four directions, and looks like:

nsIDOMNodeList nodesFromRect(in float aX, in float aY, in float aTopSize,  in float aRightSize, in float aBottomSize, in float aLeftSize, ...);

On IRC, there was a brief discussion between Hyatt and I about what would be the ideal API. Maybe rect coordinates (i.e. x, y, width and height).

Again I think these could come in follow up bugs, as the feature gets more mature.
Comment 34 WebKit Review Bot 2010-06-25 15:12:28 PDT
Attachment 59789 [details] did not build on chromium:
Build output: http://webkit-commit-queue.appspot.com/results/3339708
Comment 35 Antonio Gomes 2010-07-06 22:55:59 PDT
So I have one pending issue before uploading a newer version of the patch.

The point is: in the current hit test implementation (point based) the logic is that it performs the hit test in a top-down recursive way (from higher to lower layers), and "stops" when the hit test point is contained by a RenderXXX area. 

For example, @nodeAtPoint from RenderBox.cpp: 

...
// Check our bounds next. For this purpose always assume that we can only be hit in the
// foreground phase (which is true for replaced elements like images).
if ( ... && IntRect(tx, ty, width(), height()).contains(xPos, yPos)) {
    updateHitTestResult(result, IntPoint(xPos - tx, yPos - ty));
    return true;
}
...

Note the use of "contains". If the hit point is is contained by the current node boundary, hit test stops (returns 'true'), it is a success and the current node() is the hit one!

However for the rect based hit test, we can not just return true if hit test rect intersects the boundary of the current node being tested. Reason: we have to continue hit testing to see if it intersecs other nodes. So we return  normally false. (the exception is when the hit test rect is fully enclosed by
the node being tested, when then true is returned and the hit test stops).

The problem is that in RenderLayer::hitTestContests we have

bool RenderLayer::hitTestContents(...)
{
  if (!renderer()->hitTest(request, result, hitTestPoint,
                          layerBounds.x() - renderBoxX(),
                          layerBounds.y() - renderBoxY(), 
                          hitTestFilter)) {
      // It's wrong to set innerNode, but then claim that you didn't hit anything.
      ASSERT(!result.innerNode());
      return false;
  }
  ...
}

this ASSERT controverses the rect-based hit test, once we in such mode,  returning 'false' does not necesseraly mean that nothing was hit.

Would it make sense to modify the assert condition, so we do not hit that?
Comment 36 Simon Fraser (smfr) 2010-07-07 09:56:37 PDT
(In reply to comment #35)

> The problem is that in RenderLayer::hitTestContests we have
> 
> bool RenderLayer::hitTestContents(...)
> {
>   if (!renderer()->hitTest(request, result, hitTestPoint,
>                           layerBounds.x() - renderBoxX(),
>                           layerBounds.y() - renderBoxY(), 
>                           hitTestFilter)) {
>       // It's wrong to set innerNode, but then claim that you didn't hit anything.
>       ASSERT(!result.innerNode());
>       return false;
>   }
>   ...
> }
> 
> this ASSERT controverses the rect-based hit test, once we in such mode,  returning 'false' does not necesseraly mean that nothing was hit.
> 
> Would it make sense to modify the assert condition, so we do not hit that?

Well, the question is what does result.innerNode() mean when doing area hit testing? Since you're returning a list of nodes, I don't see why you'd bother with result.innerNode() at all.

So you may need more conditional behavior inside the hit testing code when doing area hit testing.
Comment 37 Antonio Gomes 2010-07-07 13:34:59 PDT
Created attachment 60772 [details]
patch v2 - feature + tests

Patch improves v1 in:

- stability - fix an ASSERT condition leding tests to fail in debug bug.
- quality - better comments in the code, and more detailed ChangeLog entry.
Comment 38 Dave Hyatt 2010-07-07 14:10:20 PDT
Comment on attachment 60772 [details]
patch v2 - feature + tests

How much are HitTestResults copied?  I think we try to avoid copying them, but we'll definitely get more expensive with having to copy m_rawNodeList now.'
Comment 39 Antonio Gomes 2010-07-08 06:22:50 PDT
(In reply to comment #38)
> (From update of attachment 60772 [details])
> How much are HitTestResults copied?  I think we try to avoid copying them, but we'll definitely get more expensive with having to copy m_rawNodeList now.'

In the common case (current point based hit test) there is no behavior change at all. So it will be copied as much as it's being copied now (so same cost plus the cost of copying an empty ListHashSet). Is that empty object your concern? If so, I'd be glad to measure any possible perf regression on it.

For the rect based hit test case we are adding, we are not copying HitTestResult objects, but using an operation we called 'append'. e.g. in x.append(y) the listhashset of y is appended to x's. O(n) cost.

Let me know if I misunderstood your concern.
Comment 40 Antonio Gomes 2010-07-19 19:17:13 PDT
Created attachment 62029 [details]
patch v3 - feature + tests

Difference from patch v2 (attachment 60772 [details]):

- Fixed a bug where input elements were not being hit at all: HitTestResult::addRawNodeForRegionTest is no-op if null'ed Node is passed as parameter, however it was returning 'false', which means that hit test should stop. Now it is returning the proper value (i.e. true) and subsequent hit test processing keeps happenning.

- Fixed an unconditional behavior change in EventHandler::hitTestResultAtPoint: receiving a zero-padding (IntSize(0,0)) still performs a rect-based hit test. The logic was then adapted to consider negative paddings as invalid for rect hit testing purposes.

- Better changeLog entry: it is now more descriptive.
Comment 41 Kenneth Rohde Christiansen 2010-07-19 20:06:30 PDT
Comment on attachment 62029 [details]
patch v3 - feature + tests

LayoutTests/fast/dom/resources/nodesFromRect.js:15
 +    var nodes = document.nodesFromRect(x, y, hPadding, vPadding, true /* ignoreClipping */);
isn't this centerX and centerY? 

WebCore/dom/Document.cpp:1038
 +  // * make it receive a real Rect, i.e. nodesFromRect(x, y, w, h);
why Rect with uppercase?

WebCore/dom/Document.cpp:1039
 +  // * make it receive the expading size of each direction separatedly,
a d too much in separately

WebCore/dom/Document.cpp:1055
 +      float zoomFactor = frameView->pageZoomFactor();
What about scale? The QGraphicsWebView can have a scale set which will be applied to the QPainter - will that work?

WebCore/dom/Document.cpp:1056
 +      IntPoint point = roundedIntPoint(FloatPoint(x * zoomFactor  + view()->scrollX(), y * zoomFactor + view()->scrollY()));
Is there any need to specify that it is an int point?

WebCore/dom/Document.cpp:1059
 +      if (!ignoreClipping && !frameView->visibleContentRect().intersects(IntRect(point, padding)))
Maybe a simple comment over complex if's like this would make the code a bit easily understandable

WebCore/dom/Document.h:305
 +      PassRefPtr<NodeList> nodesFromRect(int x, int y, int hPadding, int vPadding, bool ignoreClipping) const;
centerX, centerY?

WebCore/page/EventHandler.h:108
 +      HitTestResult hitTestResultAtPoint(const IntPoint&, bool allowShadowContent, bool ignoreClipping = false, HitTestScrollbars scrollbars = DontHitTestScrollbars, const IntSize& padding = IntSize(-1, -1));
I believe that we have something like IntPoint::zero() or zeroPoint or so, maybe we want a special constructor for this? Darin?

WebCore/rendering/HitTestResult.cpp:56
 +  HitTestResult::HitTestResult(const IntPoint& point, const IntSize& padding)
centerPoint?

WebCore/rendering/HitTestResult.h:45
 +      // hit test.
Just write that on one line

WebCore/rendering/HitTestResult.h:59
 +      bool isRegionTest() const { return m_isRegionTest && hasValidPadding(); }
You talk about rect based hit testing, and here you call it region? Is it region or is it rect?

WebCore/rendering/HitTestResult.h:97
 +      inline bool hasValidPadding() const { return m_padding.width() >= 0 && m_padding.height() >= 0; }
wouldn't hasPadding be sufficient? Padding, region, rect... it is a bit confusing

WebCore/rendering/RenderBlock.cpp:3756
 +          // TODO: isPointInOverflowControl() doesn't handle region test yet.
I think we only allow FIXME:

WebCore/rendering/RenderBlock.cpp:3847
 +                  hitTestContents(request, result, x, y, finalX, finalY, hitTestAction);
no return needed here? 

WebCore/rendering/RenderLineBoxList.cpp:256
 +          if (y + result.padding().height() >= ty + curr->root()->topVisibleOverflow() && y - result.padding().height() < ty + curr->root()->bottomVisibleOverflow()) {
there lines are quite long

WebCore/rendering/RenderSVGRoot.cpp:323
 +              // TODO: nodeAtFloatPoint() doesn't handle region test yet.
I believe we only use FIXME
Comment 42 Antonio Gomes 2010-07-21 06:31:06 PDT
Created attachment 62175 [details]
patch v4 - feature + tests

Adressing Kenneth's comments.

> WebCore/dom/Document.cpp:1055
>  +      float zoomFactor = frameView->pageZoomFactor();
> What about scale? The QGraphicsWebView can have a scale set which will be applied to the QPainter - will that work?

I do not know we have to scale the padding area based on the current zoom factor. The centerPoint has to consider scale, not the padding (since our thumb and index finger do not enlarge :)
 
> WebCore/dom/Document.cpp:1056
>  +      IntPoint point = roundedIntPoint(FloatPoint(x * zoomFactor  + view()->scrollX(), y * zoomFactor + view()->scrollY()));
> Is there any need to specify that it is an int point?

All hit testing system is based on int value, so we cast back it from FroatPoint to IntPoint.

> WebCore/page/EventHandler.h:108
>  +      HitTestResult hitTestResultAtPoint(const IntPoint&, bool allowShadowContent, bool ignoreClipping = false, HitTestScrollbars scrollbars = DontHitTestScrollbars, const IntSize& padding = IntSize(-1, -1));
> I believe that we have something like IntPoint::zero() or zeroPoint or so, maybe we want a special constructor for this? Darin?

I tried to convince Darin Adler about the usage of a static IntSize::invalid { return IntSize(-1, -1); } and IntSize::isValid() const { return m_width >= 0 && m_height >= 0; } without success. See bug 42653.

I left it as it was.
 
> WebCore/rendering/HitTestResult.h:59
>  +      bool isRegionTest() const { return m_isRegionTest && hasValidPadding(); }
> You talk about rect based hit testing, and here you call it region? Is it region or is it rect?

You are right. I change any reference to region to rectBased. For example: isRegionTest became isRectBasedTest
 
> WebCore/rendering/HitTestResult.h:97
>  +      inline bool hasValidPadding() const { return m_padding.width() >= 0 && m_padding.height() >= 0; }
> wouldn't hasPadding be sufficient? Padding, region, rect... it is a bit confusing

This method has gone.

> WebCore/rendering/RenderBlock.cpp:3847
>  +                  hitTestContents(request, result, x, y, finalX, finalY, hitTestAction);
> no return needed here? 

No return needed here, since the caller site handles it.

Furthers changes:

1) Renamed HitTestResult::addRawNodeForRegionTest to addNodeToRectBasedTestResult
2) Renamed HitTestResult::isRegionTest to isRectBasedTest
3) Renamed HitTestResult::rawNodeList to rectBasedTestResult
4) Renamed HitTestResult::regionFromPoint to rectFromPoint
5) Made addRawNodeForRegionTest no-op in case of non rect-based hit tests.
Comment 43 Antonio Gomes 2010-07-21 12:41:08 PDT
Guys, ping review?

Bots failed to apply attachment 62175 [details] due to ChangeLog problems, but as the previous one it is building cross-port locally.

By the way, to keep working progressing, I've started the follow up work of this patch, while it sits waiting for review. Find it in [1].

[1] http://gitorious.org/~tonikitoo/qtwebkit/tonikitoos-clone/commits/smartTap

It includes a prototype of QtWebKit making use of this feature. See TouchFixer commit. It is simple and pretty functional.
Comment 44 Antonio Gomes 2010-07-22 10:43:38 PDT
Created attachment 62313 [details]
patch v5 - feature + tests

- Fixed 3 failing layout tests with v4 (attachment 62175 [details]): Assigning HitTest::padding to IntSize(-1, -1) - invalid - for non rect-based hit tests.
* editing/pasteboard/files-during-page-drags.html
* fast/css/nested-layers-with-hover.html
* fast/events/onclick-list-marker.html

No regression on Mac on the layout test suite!

- update to ToT
Comment 45 Antonio Gomes 2010-07-23 12:11:17 PDT
Created attachment 62453 [details]
patch v6 - feature + tests

Changes from v5:

1) it avoids copying unnecessery class members by not using the copy constructor when applicable. It uses constructions like:

HitTestResult tempResult(result.point(), result.padding());
instead of:
HitTestResult tempResult(result); <- copy constructor

2) On assignment and copy constructor, the ListHashSet only gets copied if it is a rect based hit test, for performance reasons.

It specially matches the concern expressed in comment #38.

Again for the comon case of non
Comment 46 Dave Hyatt 2010-07-23 12:25:24 PDT
Comment on attachment 62453 [details]
patch v6 - feature + tests

"void static dumpHitTestResult(const HitTestResult& result)"

I really don't like this function sitting in Document.  It has nothing to do with Document.  I'd prefer it either be removed or put in more of a debugging file (if it's a bit like render tree dumping especially).  It really seems to me like it should just be removed, especially if nodesFromRect is testable via layout tests.

Let's use 0,0 as the default value for padding instead of -1,-1 and make rect-based hit testing be activated if either value of padding is > 0 (rather than >= 0).  We don't want to fall into rect-based hit testing because somebody passed 0 values for padding in to these functions.

Everything else looks good to me.
Comment 47 Dave Hyatt 2010-07-23 12:29:22 PDT
And to clarify, I still think padding of 0 should work with nodesForRect, which means you have to special case the 0 padding case (or just hack it so you force rect based testing on for that hit test by setting the boolean explicitly).
Comment 48 Dave Hyatt 2010-07-23 12:31:32 PDT
Comment on attachment 62453 [details]
patch v6 - feature + tests

Another question... shouldn't the padding be unsigned?  It seems like you shouldn't allow negative padding values at the IDL level.
Comment 49 Antonio Gomes 2010-07-26 07:16:25 PDT
Created attachment 62569 [details]
patch v7 - feature + tests

(In reply to comment #46)
> (From update of attachment 62453 [details])
> "void static dumpHitTestResult(const HitTestResult& result)"
> I really don't like this function sitting in Document.  It has nothing to do with Document.  I'd prefer it either be removed or ...

Removed. It was useful for debuggind, and does not need to get checked in.

> Let's use 0,0 as the default value for padding instead of -1,-1 and make rect-based hit testing be activated if either value of padding is > 0 (rather than >= 0).  We don't want to fall into rect-based hit testing because somebody passed 0 values for padding in to these functions.

Done: default 0,0 padding wont trigger a rect-based hit test anymore.

> And to clarify, I still think padding of 0 should work with nodesForRect, which means you have to special case the 0 padding case (or just hack it so you force rect based testing on for that hit test by setting the boolean explicitly).

Added a special "handler" for nodesFromRect(x, y, 0, 0) as suggested: handleZeroPadding as a private method to Document class.

(In reply to comment #48)
> Another question... shouldn't the padding be unsigned?  It seems like you shouldn't allow negative padding values at the IDL level.

Done.

> Everything else looks good to me.

Thank you, Dave.
Comment 50 Antonio Gomes 2010-07-27 15:53:45 PDT
Created attachment 62761 [details]
(commit=r64272, r=hyatt )patch v7.1 - feature + tests

Same as patch v2 (attachment 62569 [details]) but fixed a typo in a comment.

see comment $49 for summary.
Comment 51 Dave Hyatt 2010-07-28 11:46:37 PDT
Comment on attachment 62761 [details]
(commit=r64272, r=hyatt )patch v7.1 - feature + tests

r=me
Comment 52 Antonio Gomes 2010-07-29 06:57:37 PDT
Comment on attachment 62761 [details]
(commit=r64272, r=hyatt )patch v7.1 - feature + tests

Clearing flags on attachment: 62761

Committed r64272: <http://trac.webkit.org/changeset/64272>

$ git svn dcommit 
Committing to http://svn.webkit.org/repository/webkit/trunk ...


	M	LayoutTests/ChangeLog
	M	LayoutTests/fast/dom/Window/window-properties-expected.txt
	A	LayoutTests/fast/dom/nodesFromRect-basic-expected.txt
	A	LayoutTests/fast/dom/nodesFromRect-basic.html
	A	LayoutTests/fast/dom/resources/nodesFromRect.css
	A	LayoutTests/fast/dom/resources/nodesFromRect.js
	M	LayoutTests/platform/qt/fast/dom/Window/window-properties-expected.txt
	M	WebCore/ChangeLog
	M	WebCore/WebCore.exp.in
	M	WebCore/config.h
	M	WebCore/dom/Document.cpp
	M	WebCore/dom/Document.h
	M	WebCore/dom/Document.idl
	M	WebCore/page/EventHandler.cpp
	M	WebCore/page/EventHandler.h
	M	WebCore/rendering/EllipsisBox.cpp
	M	WebCore/rendering/HitTestResult.cpp
	M	WebCore/rendering/HitTestResult.h
	M	WebCore/rendering/InlineFlowBox.cpp
	M	WebCore/rendering/InlineTextBox.cpp
	M	WebCore/rendering/RenderBlock.cpp
	M	WebCore/rendering/RenderBox.cpp
	M	WebCore/rendering/RenderImage.cpp
	M	WebCore/rendering/RenderLayer.cpp
	M	WebCore/rendering/RenderLineBoxList.cpp
	M	WebCore/rendering/RenderSVGRoot.cpp
	M	WebCore/rendering/RenderTable.cpp
	M	WebCore/rendering/RenderTableSection.cpp
	M	WebCore/rendering/RenderWidget.cpp
Committed r64272
Comment 53 Simon Hausmann 2010-08-04 03:09:49 PDT
Revision r64272 cherry-picked into qtwebkit-2.1 with commit bcfea5aad4658f9f84af4459cda7989ca45f6ebc
Comment 54 Steve Block 2010-08-04 09:59:00 PDT
I'm in the process of merging this with the Android hit-testing and noticed the checks for >= 0 in HitTestResult::paddingWidth() and HitTestResult::paddingHeight(). It looks to me like these checks are superfluous, as in the HitTestResult constructor, m_padding is not set if either the width or height of the supplied padding is < 0. If not set, the width and height default to 0. So these checks will always be true.

Am I missing something?

Thanks,
Steve
Comment 55 Antonio Gomes 2010-08-04 10:19:17 PDT
(In reply to comment #54)
> I'm in the process of merging this with the Android hit-testing and noticed the checks for >= 0 in HitTestResult::paddingWidth() and HitTestResult::paddingHeight(). It looks to me like these checks are superfluous, as in the HitTestResult constructor, m_padding is not set if either the width or height of the supplied padding is < 0. If not set, the width and height default to 0. So these checks will always be true.
> 
> Am I missing something?

Hi Steve.

I think you are right. This bits of code might likely missing to be updated after the last suggestion I addressed from Hyatt. I will check more carefully now, and fix that in a follow up bug, if it turns our unneeded.
Comment 56 Antonio Gomes 2010-08-04 19:51:10 PDT
(In reply to comment #55)
> (In reply to comment #54)
> > I'm in the process of merging this with the Android hit-testing and noticed the checks for >= 0 in HitTestResult::paddingWidth() and HitTestResult::paddingHeight(). It looks to me like these checks are superfluous, as in the HitTestResult constructor, m_padding is not set if either the width or height of the supplied padding is < 0. If not set, the width and height default to 0. So these checks will always be true.
> > 
> > Am I missing something?
> 
> Hi Steve.
> 
> I think you are right. This bits of code might likely missing to be updated after the last suggestion I addressed from Hyatt. I will check more carefully now, and fix that in a follow up bug, if it turns our unneeded.

Filed bug 43534.
Comment 57 Antonio Gomes 2010-09-23 17:08:52 PDT
Just a heads up here: bug 46336 is about to change the Document::nodesFromRect API to be more flexible: instead of receiving a IntSize as 'padding', one will be able to specify the padding for each four directions (top, right, bottom and left).

HitTestResult will also be adjusted accordingly.

 See also the thread https://lists.webkit.org/pipermail/webkit-dev/2010-September/014457.html in webkit-dev.