619273 - Move the selection state bit from frames to content nodes

Status: RESOLVED FIXED

(Core :: DOM: Selection, defect)

Description

[(no longer active)]

This will give us a few advantages, such as solving bug 602331 comment 6 (paragraph 2), preserving selections when hiding content and showing them again, and it could be possibly a bit more efficient too.  I will work on it after Firefox 4.

Comment 1

[(no longer active)]

Attachment: Part 1: Remove the NS_TEXT_IN_SELECTION flag

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

How can we just remove the setting of NS_FRAME_SELECTED_CONTENT in ReflowText? That should be needed.

Comment 3

[Mats Palmgren (inactive)]

It looks to me as the NS_FRAME_SELECTED_CONTENT bit is only an optimization
to avoid nsTextFrame::GetSelectionDetails when painting.
Using only the NS_TEXT_IN_SELECTION content bit would likely be too slow,
for example a <textarea> with thousands of lines.

The current design with two bits seems reasonable to me.  What needs to be
fixed is that NS_TEXT_IN_SELECTION isn't updated properly in some mutation
cases.  I don't see how removing the frame bit would help with that.

Comment 4

[Mats Palmgren (inactive)]

NS_TEXT_IN_SELECTION is updated by nsTextFrame::SetSelectedRange (only).
It's called from nsTypedSelection::selectFrames when doing stuff with
the Selection object, adding/removing ranges, collapsing/extending etc.
I can't find any code that deals general mutations or modifying Ranges...

A simple solution would be to set a "Selection is dirty" bit when any of
the above happens and then update the frame/content selection bits off
the refresh driver or something.  I don't think the bits needs to be
more accurate than what is needed for painting.  Would this approach be
too slow?  I guess we could optimize the case when all selection ranges
are collapsed.

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Mats Palmgren [:mats] from comment #3)
> It looks to me as the NS_FRAME_SELECTED_CONTENT bit is only an optimization
> to avoid nsTextFrame::GetSelectionDetails when painting.

nsFrame::DisplaySelectionOverlay uses it too, and it's used in some other places, like in BuildDisplayListForChild.

> Using only the NS_TEXT_IN_SELECTION content bit would likely be too slow,
> for example a <textarea> with thousands of lines.

Yes, we might need some kind of state bit for text frames.

> The current design with two bits seems reasonable to me.  What needs to be
> fixed is that NS_TEXT_IN_SELECTION isn't updated properly in some mutation
> cases.  I don't see how removing the frame bit would help with that.

Another thing that needs to be fixed is that right now creating frames doesn't set the NS_FRAME_SELECTED_CONTENT bit on the new frame. That causes bugs because of the uses of NS_FRAME_SELECTED_CONTENT noted above. (E.g. selected images may not appear selected after a reframe.) Checking for a selection every time you create a frame sounds like a performance hit. Getting rid of NS_FRAME_SELECTED_CONTENT would make this problem go away, probably without a performance hit.

Comment 6

[Mats Palmgren (inactive)]

Attachment: fix

Olli, can you review this?  The tricky code is the mutation event handlers
of nsRange, which you have reviewed in the past.

Patch overview:
Remove NS_FRAME_SELECTED_CONTENT frame bit (and NS_TEXT_IN_SELECTION bit
that we have for text nodes).
Add two new (general) bits on all nodes: NODE_RANGE_COMMON_ANCESTOR and
NODE_RANGE_COMMON_ANCESTOR_DESCENDANT.  ANCESTOR is set on the common
ancestor of the start/end nodes of a range *when it is in a Selection*.
This node has a hash table of ranges stored as a property.
All descendents (but not the ancestor itself) are marked with the
DESCENDANT bit.  These bits are updated when adding/removing a range
from a Selection and when nodes are removed/added into ranges.  If a
node has either of these bits, it *may* be selected.  If a node doesn't
have any of these bits it's definitely not selected, which is used to
quickly exclude most nodes from checks against range boundaries.
If it does have a bit, the ranges to check for selection is found on
the ancestor nodes with the ANCESTOR bit, and this avoids doing checks
against irrelevant ranges.  *I think* this should be good enough for
performance without having to cache state on the frames.

So, this should fix bugs that we have on losing selection when content
is reframed.  It also improves cases where DOM mutations changes the
contents of a range, but there's still some cases where we need to
invalidate the frames for the selection to be painted/cleared.
I'm working on a patch on top of this that will fix that, but I prefer
to do that in a separate bug.

Comment 7

[Mats Palmgren (inactive)]

Attachment: fix an accessibility test

This test failed with the patch because it depends on bugs
in table selection which are now fixed.

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 569520 [details] [diff] [review]
fix



>+  // Set if the node is the common ancestor of the start/end nodes of a Range
>+  // that is in a Selection.
>+  NODE_RANGE_COMMON_ANCESTOR   = 0x00080000U,
>+
>+  // Set if the node is a descendant of a node with the above bit set.
>+  NODE_RANGE_COMMON_ANCESTOR_DESCENDANT = 0x00100000U,


So, these aren't actually for range, but selection.
Also, could you perhaps use boolean flags?


How do the flags handle case when there are several ranges in selection and they are
overlapping. Or is that case not possible? (IIRC it is not possible)


>+static void UnmarkDescendants(nsINode* aNode)
>+{
>+  // Unset NODE_RANGE_COMMON_ANCESTOR_DESCENDANT on aNode's descendants unless
>+  // aNode is a descendant of another range common ancestor.  Also, exclude
>+  // descendants of RANGE_COMMON_ANCESTORs nodes (but not that node itself).
>+  if (!aNode->HasFlag(NODE_RANGE_COMMON_ANCESTOR_DESCENDANT)) {
>+    nsCOMPtr<nsIContentIterator> iter;
>+    NS_NewPreContentIterator(getter_AddRefs(iter));
>+    iter->Init(aNode);
>+    iter->Next(); // we know |aNode| doesn't have any bit set
>+    while (!iter->IsDone()) {
>+      nsINode* node = iter->GetCurrentNode();
>+      node->UnsetFlags(NODE_RANGE_COMMON_ANCESTOR_DESCENDANT);
Why is this ok? Isn't it possible to have node in two different ranges?

>+nsFilteredContentIterator::NextSkipDescendants()
>+{
>+}
Add assertion here?


> void
>+nsFindContentIterator::NextSkipDescendants()
>+{
>+  if (mInnerIterator) {
>+    mInnerIterator->NextSkipDescendants();
>+    if (!mInnerIterator->IsDone())
>+      return;
>+
>+    // by construction, mOuterIterator is already on the next node
>+  }
>+  else {
>+    mOuterIterator->NextSkipDescendants();
>+  }
>+  MaybeSetupInnerIterator();  
>+}
Why is this needed? Does someone call nsFindContentIterator::NextSkipDescendants
or we there be just assertion?


Does this affect to performance of Bug 486072 or Bug 519657?

But I really would like to understand why the flag handling is ok is cases like
<div><span>Hello</span><span>World</span><span> ! </span></div>
              ^---------------^ ^---------------^
when one selection is removed modified. Perhaps I just missed something which keeps
the flag in the middle span (div would be the common ancestor)

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Actually, Bug 519657 may not be a problem anymore, but better to test that the patch doesn't
regress performance.

Comment 10

[Mats Palmgren (inactive)]

> So, these aren't actually for range, but selection.

Well, the node is a common ancestor for a *range*, but I'm only tracking
ranges that are part of a selection.  We could add SELECTED_:
  NODE_SELECTED_RANGE_COMMON_ANCESTOR
  NODE_SELECTED_RANGE_COMMON_ANCESTOR_DESCENDANT
but it does seem a bit long...

> Also, could you perhaps use boolean flags?

Sure, I can use mBoolFlags instead and add specific get/set accessors
if you prefer.  How about:

  IsSelectedRangeCommonAncestor()
  IsSelectedRangeCommonAncestorDescendant()

and corresponding Set/Clear methods?

or is node->IsCommonAncestorForSelectedRange() easier to read perhaps?
node->IsCommonAncestorForRangeInSelection() is even more accurate I guess...

> How do the flags handle case when there are several ranges in selection and
> they are
> overlapping. Or is that case not possible? (IIRC it is not possible)

Yeah, overlap isn't possible within a specific selection.  It is
possible between different selections though, for example when selecting
all text in a <textarea> that has misspelled words.
The code I'm adding is agnostic to which selection a range belongs to
though, so it would work also for overlapping ranges within a selection.

The ANCESTOR bit is set on the range's common ancestor, it doesn't imply
that the DESCENDANT bit is set.  The DESCENDANT bit is set on all nodes
that has one or more ancestors with the ANCESTOR bit.
Note that the DESCENDANT bit can be set on nodes that are not strictly
part of the selection. For example
<div><span>Hello</span><span>World</span><span> ! </span></div>
              ^---------------^
For this range, the div is the common ancestor and all three spans and
all text nodes will have the DESCENDANT bit (but not the div itself).


> >+static void UnmarkDescendants(nsINode* aNode)
> >+{
> >+  // Unset NODE_RANGE_COMMON_ANCESTOR_DESCENDANT on aNode's descendants unless
> >+  // aNode is a descendant of another range common ancestor.  Also, exclude
> >+  // descendants of RANGE_COMMON_ANCESTORs nodes (but not that node itself).
> >+  if (!aNode->HasFlag(NODE_RANGE_COMMON_ANCESTOR_DESCENDANT)) {
> >+    nsCOMPtr<nsIContentIterator> iter;
> >+    NS_NewPreContentIterator(getter_AddRefs(iter));
> >+    iter->Init(aNode);
> >+    iter->Next(); // we know |aNode| doesn't have any bit set
> >+    while (!iter->IsDone()) {
> >+      nsINode* node = iter->GetCurrentNode();
> >+      node->UnsetFlags(NODE_RANGE_COMMON_ANCESTOR_DESCENDANT);
> Why is this ok? Isn't it possible to have node in two different ranges?

UnmarkDescendants is a NOP if 'aNode' has the DESCENDANT bit.
If it doesn't, then 'aNode' (or any of its descendants) isn't part of a
selected range, so it's ok to clear it unconditionally, except in
descendant sub-trees that has the ANCESTOR bit, which it what the
NextSkipDescendants() call does.


> >+nsFilteredContentIterator::NextSkipDescendants()
> >+{
> >+}
> Add assertion here?

OK, will do.

> nsFindContentIterator::NextSkipDescendants
> or we there be just assertion?

OK, I will make it an assertion instead.

> Does this affect to performance of Bug 486072 or Bug 519657?

I'll take a look and get back to you.

> But I really would like to understand why the flag handling is ok is cases
> like
> <div><span>Hello</span><span>World</span><span> ! </span></div>
>               ^---------------^ ^---------------^
> when one selection is removed modified. Perhaps I just missed something
> which keeps
> the flag in the middle span (div would be the common ancestor)

Yes, the div is marked ANCESTOR and has both ranges in its hash table,
all three spans and all the text nodes are marked DESCENDANT.
Removing either range will end up in SetInSelection(false) for that
range, which calls UnregisterCommonAncestor which removes that range
from div's hash table; there's no difference on the node bits since
there's still a range with the div as the common ancestor.

Modifying a range so it has a different common ancestor, say:
  <div><span>Hello</span><span>World</span><span> ! </span></div>
                ^-^               ^---------------^
When the DoSetRange is called for the modified range, 
UnregisterCommonAncestor is called which removes this range from
the div, but since there's still a registered range UnmarkDescendants
isn't called.  DoSetRange then calls RegisterCommonAncestor
on the first span, which marks that span with the ANCESTOR bit.
Since this span already has the DESCENDANT bit, MarkDescendants
is a NOP.  So, the div and the first span has ANCESTOR, all nodes
except the div has DESCENDANT.

Let me know if you had any specific modifications in mind...

Comment 11

[Mats Palmgren (inactive)]

> Does this affect to performance of Bug 486072 or Bug 519657?

I don't see any difference in performance for the test in bug 486072 (it's slow).

The tests in bug 519657 doesn't seem to be a problem anymore, they seem reasonably
fast with and without the patch.  If anything, it seems slightly faster with the
patch, for example when drag-selecting text causing the textarea to scroll.

I think the new bits could actually help fixing Bug 486072 -- they can be
used to narrow the number of ranges you need to check to find overlaps
(if that's the problem).

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

(In reply to Mats Palmgren [:mats] from comment #10)
> or is node->IsCommonAncestorForSelectedRange() easier to read perhaps?
> node->IsCommonAncestorForRangeInSelection() is even more accurate I guess...
That latter is very clear, so I'd prefer that. I know it is a bit long.

> Yes, the div is marked ANCESTOR and has both ranges in its hash table,
> all three spans and all the text nodes are marked DESCENDANT.
> Removing either range will end up in SetInSelection(false) for that
> range, which calls UnregisterCommonAncestor which removes that range
> from div's hash table; there's no difference on the node bits since
> there's still a range with the div as the common ancestor
Ah, I must have missed the place where the bits are preserved in case selection contains
more than one range.

Comment 13

[Mats Palmgren (inactive)]

Attachment: fix v2

Addressed all review comments:
1. now using mBoolFlags, with the accessors:
     IsCommonAncestorForRangeInSelection()
     IsDescendantOfCommonAncestorForRangeInSelection()

2. made the unrelated content iterators that doesn't need to implement
   NextSkipDescendants() assert

Comment 14

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 574217 [details] [diff] [review]
fix v2

>+  bool IsSelectionDescendant() const {
{ should be in the next line.

>+struct FindSelectedRangeData {
{ should be in the next line

NODE_RANGE_COMMON_ANCESTOR_DESCENDANT mentioned still in few comments

How does this approach handle dynamic changes to DOM tree - I mean,
is it guaranteed that ClearDescendantOfCommonAncestorForRangeInSelection is
called always. /me reads the mutationobserver::* methods

>+static void MarkDescendants(nsINode* aNode)
>+{
>+  // Set NODE_RANGE_COMMON_ANCESTOR_DESCENDANT on our descendants unless aNode
>+  // is already marked as a range common ancestor or a descendant of one, 
>+  // in which case all of our descendants have the bit set already.
>+  if (!aNode->IsSelectionDescendant()) {
>+    nsCOMPtr<nsIContentIterator> iter;
>+    NS_NewPreContentIterator(getter_AddRefs(iter));
>+    iter->Init(aNode);
>+    iter->Next(); // don't set the DESCENDANT bit on |aNode|
>+    while (!iter->IsDone()) {
>+      nsINode* node = iter->GetCurrentNode();
>+      node->SetDescendantOfCommonAncestorForRangeInSelection();
>+      if (!node->IsCommonAncestorForRangeInSelection()) {
>+        iter->Next();
>+      }
>+      else {
} else {

>+static void UnmarkDescendants(nsINode* aNode)
>+{
>+  // Unset NODE_RANGE_COMMON_ANCESTOR_DESCENDANT on aNode's descendants unless
>+  // aNode is a descendant of another range common ancestor.  Also, exclude
>+  // descendants of RANGE_COMMON_ANCESTORs nodes (but not that node itself).
>+  if (!aNode->IsDescendantOfCommonAncestorForRangeInSelection()) {
>+    nsCOMPtr<nsIContentIterator> iter;
>+    NS_NewPreContentIterator(getter_AddRefs(iter));
This is rather slow. Is there any way to do marking without lots of addref/releasing.
Though, I'm not quite sure if marking/unmarking is that common.
I wonder if we should have non-addrefing-releasing contentiterator, basically a stack-only
class. Maybe that kind of change could be a followup bug.


>+    iter->Init(aNode);
>+    iter->Next(); // we know |aNode| doesn't have any bit set
>+    while (!iter->IsDone()) {
>+      nsINode* node = iter->GetCurrentNode();
>+      node->ClearDescendantOfCommonAncestorForRangeInSelection();
>+      if (!node->IsCommonAncestorForRangeInSelection()) {
>+        iter->Next();
>+      }
>+      else {
} else {


>@@ -312,16 +481,27 @@ nsRange::CharacterDataChanged(nsIDocumen
>       // splitText(), aInfo->mDetails->mNextSibling is the new text node
>       NS_ASSERTION(aInfo->mDetails->mType ==
>                    CharacterDataChangeInfo::Details::eSplit,
>                    "only a split can start before the end");
>       NS_ASSERTION(static_cast<PRUint32>(mEndOffset) <= aInfo->mChangeEnd + 1,
>                    "mEndOffset is beyond the end of this node");
>       newEndOffset = static_cast<PRUint32>(mEndOffset) - aInfo->mChangeStart;
>       newEndNode = aInfo->mDetails->mNextSibling;
>+
>+      bool isCommonAncestor = IsInSelection() && mStartParent == mEndParent;
>+      if (isCommonAncestor && !newStartNode) {
>+        // The split occurs inside the range.
>+        UnregisterCommonAncestor(mStartParent);
>+        RegisterCommonAncestor(mStartParent->GetParent());
>+        newEndNode->SetDescendantOfCommonAncestorForRangeInSelection();
>+      }
>+      else if (mEndParent->IsDescendantOfCommonAncestorForRangeInSelection()) {
} else if {

> nsIFrame::IsVisibleInSelection(nsISelection* aSelection)
> {
>-  if ((mState & NS_FRAME_SELECTED_CONTENT) == NS_FRAME_SELECTED_CONTENT)
>-    return true;
>+  if (!GetContent() || !GetContent()->IsSelectionDescendant())
>+    return false;
>   
I know the old code didn't have it, but
if (expr) {
  stmt;
}

>-  NS_IMETHOD  GetSelected(bool *aSelected) const = 0;
>+  bool IsSelected() const {
move { to the next line


>@@ -3803,16 +3821,19 @@ nsTypedSelection::AddItem(nsIRange *aIte
>   NS_ENSURE_SUCCESS(rv, rv);
> 
>   if (!temp.InsertElementAt(insertionPoint, RangeData(aItem)))
>     return NS_ERROR_OUT_OF_MEMORY;
> 
>   // Merge the leftovers back in to mRanges
>   if (!mRanges.InsertElementsAt(startIndex, temp))
>     return NS_ERROR_OUT_OF_MEMORY;
>+  for (PRUint32 i = 0; i < temp.Length(); ++i) {
>+    temp[i].mRange->SetInSelection(true);
>+  }
new line before |for|


>@@ -4907,23 +4912,17 @@ nsTextFrame::PaintTextWithSelectionColor
>         }
>       }
>     }
>     sdptr = sdptr->mNext;
>   }
>   *aAllTypes = allTypes;
> 
>   if (!allTypes) {
>-    // Nothing is selected in the given text range.
>-    if (aContentLength == aProvider.GetOriginalLength()) {
>-      // It's the full text range so we can remove the FRAME_SELECTED_CONTENT
>-      // bit to avoid going through this slow path until something is selected
>-      // in this frame again.
>-      RemoveStateBits(NS_FRAME_SELECTED_CONTENT);
>-    }
>+    // Nothing is selected in the given text range. XXX can this still occur?
>     return false;
>   }
Can it occur?
File a followup?

btw, how does this perform if you have a *huge* text node, something which is
split to thousands of lines and you select different parts of the text or resize the window so that
lines need to be re-wrapped. Same with <textarea>
Or, how is the performance if a div has *lots* of span elements as child elements, and each span contain some text and you select something which is
close to the end. Or maybe not lots of span elements, but different text nodes.
(I'm a bit worried about using nsContentUtils::ComparePoints to check if node is selected.)

Probably quite artificial test, but could you test how much modifying DOM inside a selection is slower than without selection.
Also, does marking/unmarking show up badly in the profiles?

Looks good, but I really hope some performance testing. Also, could you write some
tests for dynamic changes before landing this.

Comment 15

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

(In reply to Olli Pettay [:smaug] from comment #14)
> Comment on attachment 574217 [details] [diff] [review] [diff] [details] [review]
> >+static void UnmarkDescendants(nsINode* aNode)
> >+{
> >+  // Unset NODE_RANGE_COMMON_ANCESTOR_DESCENDANT on aNode's descendants unless
> >+  // aNode is a descendant of another range common ancestor.  Also, exclude
> >+  // descendants of RANGE_COMMON_ANCESTORs nodes (but not that node itself).
> >+  if (!aNode->IsDescendantOfCommonAncestorForRangeInSelection()) {
> >+    nsCOMPtr<nsIContentIterator> iter;
> >+    NS_NewPreContentIterator(getter_AddRefs(iter));
> This is rather slow. Is there any way to do marking without lots of
> addref/releasing.
> Though, I'm not quite sure if marking/unmarking is that common.
> I wonder if we should have non-addrefing-releasing contentiterator,
> basically a stack-only
> class. Maybe that kind of change could be a followup bug.

Would nsINode::GetNextNode work here?

Comment 16

[Olli Pettay [:smaug][[e-mail]]]

Yes, I think that would be useful here.
I always forget that we have that method, since I've never used it myself.

Thanks.

Comment 17

[Mats Palmgren (inactive)]

(In reply to Olli Pettay [:smaug] from comment #14)
> How does this approach handle dynamic changes to DOM tree - I mean,
> is it guaranteed that ClearDescendantOfCommonAncestorForRangeInSelection is
> called always.

Yes, the bits are set/unset in the mutation observer methods,
either directly or through DoSetRange.

(In reply to Ms2ger from comment #15)
> Would nsINode::GetNextNode work here?

Thanks!  nsINode::GetNextNode/GetNextNonChildNode is exactly what I need.

> >+    // Nothing is selected in the given text range. XXX can this still occur?
> >     return false;
> >   }
> Can it occur?
> File a followup?

Don't know yet, I'll file a followup bug.

> >+  bool IsSelected() const {
> move { to the next line

I'm keeping the hanging brace style here for consistency
with the existing inline methods in nsIFrame.h.

I fixed the other nits as suggested.

I'm doing performance tests and will get back to you with results.
No problems so far though.

Comment 18

[Mats Palmgren (inactive)]

Attachment: fix v3

Using nsINode::GetNextNode/GetNextNonChildNode instead of nsContentIterator.

Comment 19

[Mats Palmgren (inactive)]

Bah, I just discovered that nsRange::ContentAppended needs to be implemented too,
so there will be a a small additional patch to add that...

Comment 20

[Mats Palmgren (inactive)]

Attachment: fix v4

Using nsINode::GetNextNode/GetNextNonChildNode instead of nsContentIterator.
Added nsRange::ContentAppended to mark the child nodes if needed.

Comment 21

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 579655 [details] [diff] [review]
fix v4

Tricky to review.

Comment 22

[Mats Palmgren (inactive)]

Attachment: reftests

reftests for testing DOM mutations inside selection

Comment 23

[Mats Palmgren (inactive)]

Attachment: Performance testcase

"create" is about 10% slower with "create DOM while selected"
checked, on the other hand it's a few % faster with it unchecked
which should be the common case.
"select all" for <textarea> is significantly faster (~400%).
Other than that, performance seems to be about the same.

Comment 24

[Mats Palmgren (inactive)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e3766ee732cc
https://hg.mozilla.org/integration/mozilla-inbound/rev/a08580f18cb7
https://hg.mozilla.org/integration/mozilla-inbound/rev/0aa9c3a5b7e1

Comment 25

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/e3766ee732cc
https://hg.mozilla.org/mozilla-central/rev/a08580f18cb7
https://hg.mozilla.org/mozilla-central/rev/0aa9c3a5b7e1