Last Comment Bug 348681 - Don't allow overlapping ranges in the selection
: Don't allow overlapping ranges in the selection
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: Selection (show other bugs)
: Trunk
: All All
: -- normal (vote)
: mozilla1.9.2a1
Assigned To: Graeme McCutcheon [:graememcc]
:
Mentors:
Depends on: 673785 493111 510575 517968
Blocks:
  Show dependency treegraph
 
Reported: 2006-08-14 19:07 PDT by Brett Wilson
Modified: 2011-07-24 15:33 PDT (History)
7 users (show)
graeme.mccutcheon: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
V1 for review (39.32 KB, patch)
2008-08-11 15:35 PDT, Graeme McCutcheon [:graememcc]
no flags Details | Diff | Splinter Review
v2 (55.44 KB, patch)
2009-04-21 12:51 PDT, Graeme McCutcheon [:graememcc]
no flags Details | Diff | Splinter Review
v3 (55.72 KB, patch)
2009-05-08 03:59 PDT, Graeme McCutcheon [:graememcc]
roc: review+
roc: superreview+
Details | Diff | Splinter Review

Description Brett Wilson 2006-08-14 19:07:22 PDT
The selection (layout/generic/nsSelection.cpp) holds a list of ranges. In the common case, there is only one range corresponding to what the user has selected. However, selections are also used for other things like spellcheck underlines where there are many ranges (this is the case even for "regular" table cell selection.

The behavior as of the filing of this bug is that overlapping ranges are allowed but identical ranges are not.

If we disallow overlapping ranges, we can simplify a lot of code. In nsSelection we currently keep lists sorted by end as well as beginning, and this duplicate list can go away. Lookups will be faster and the code will be simpler. We can also solve other problems: bug 346729 was cause by the ability to do this.
Comment 1 Graeme McCutcheon [:graememcc] 2008-08-11 15:35:21 PDT
Created attachment 333300 [details] [diff] [review]
V1 for review
Comment 2 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2008-08-11 19:44:33 PDT
+  nsresult CheckRangeOverlap(PRInt32 aIndex, nsIDOMNode* aBeginNode,
+                             PRInt32 aBeginOffset, nsIDOMNode* aEndNode,
+                             PRInt32 aEndOffset, OverlapType* aOutResult);

Return aOutResult directly? Document aIndex?

You forgot to "hg add" the testcase.

Document your invariants somewhere. There was a lot of documentation for the old approach, which you removed.

+  if (!aBeginNode)
+    return NS_ERROR_NULL_POINTER;

Is this really necessary?

I'm not sure what nsTypedSelection::CheckRangeOverlap is trying to compute. It seems that if aBeginNode/aBeginOffset is after the end of mRanges[aIndex], it will return RANGE_OVERLAPS, which seems wrong.
Comment 3 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2008-08-11 19:46:06 PDT
Also, you're making AddItem fail if the ranges overlap but aren't equal. I don't think that should fail. Instead, we probably should succeed but subtract the overlapping area from the range that's already in the list.
Comment 4 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2008-08-11 19:46:57 PDT
(Or else merge the two ranges and return the index of the merged range, although that might confuse code that expects the output index to refer to exactly the range it specified.)
Comment 5 Graeme McCutcheon [:graememcc] 2009-04-21 12:51:38 PDT
Created attachment 373899 [details] [diff] [review]
v2

Yeah, my old patch kind of sucked.

I need to run this through try server once I get my commit access, to look at reftests - my box at home is giving me wildly inconsistent results. I refuse to believe SVG and pagination failures are a result of this patch!

This implements the "add the range as it is passed, tweak the endpoints of the other ranges to accomodate" approach suggested above.

In the case where both endpoints overlap, and on trying to adjust the second endpoint we get a failure, and get a further failure trying to revert the adjustment to the first endpoint, I don't know what we can usefully do at this point. Currently, I'm just asserting, but I'm wondering if I should clear mRanges too, as it is now in a state of wrongness.
Comment 6 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2009-04-21 15:55:07 PDT
+  // disjoint, it is also implicitly sorted by the range endings. This allows
+  // us to perform binary searches when searching for a range, giving us
+  // O(log n) search time.
+  //
+  // An interval tree has been suggested as an alternative approach, as this
+  // would give us O(log n) time lookups, which would be better. However, this

Clarify the latter comment so that the difference between "lookups" and "searches" is clear.

+  if (! mRanges.InsertObjectAt(aItem, beginInsertionPoint))

No space after ! here and elsewhere

+      nsresult rv = rangeBeforeStart->SetEnd(aItem->GetStartParent(),
+                                             aItem->StartOffset());

This can result in the range becoming zero-length. Should we delete it?

+    if (NS_SUCCEEDED(rv))
+      rv = overlapRange->SetEnd(mRanges[endInsertionPoint]->GetEndParent(),
+                                mRanges[endInsertionPoint]->EndOffset());

{} around this statement.

I think I'd prefer to have some of this range-banging code factored out. How about defining a new helper function
  nsresult SubtractRange(nsIRange* aRange, nsIRange* aSubtract, nsCOMArray<nsIRange>* aOutput);
which subtracts aSubtract from aRange and adds 0, 1, or 2 ranges (which might include aRange) to aOutput.

Also we should change GetRangesForIntervalCOMArray to just return the indexes of the overlapping ranges in the range array.

Then you can implement AddItem by calling GetRangesForIntervalCOMArray to find the ranges that overlap the item you're going to add, copy them to a temporary array, remove them all from mRanges in one operation, iterate over them calling SubtractRange to remove aItem's range from each one and putting the output leftovers in a new temporary array, then insert the new item into the temporary array, then insert the temporary array back into mRanges.
Comment 7 Graeme McCutcheon [:graememcc] 2009-05-08 03:59:05 PDT
Created attachment 376394 [details] [diff] [review]
v3

Updated per comments.

What with removing all the overlapping elements in one go, this is now more destructive, so it isn't really possible to keep things reversible without a book-keeping overhead.

Is it worth looking at the other internal callers of GetRangesForIntervalCOMArray, and converting them to use the indices version?
Comment 8 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2009-05-09 02:06:27 PDT
Comment on attachment 376394 [details] [diff] [review]
v3

+//    A helper function that subtracts aSubtract from aRange, and adds
+//    0 or 1 RangeData objects representing the remaining non-overlapping
+//    difference to aOutput

This comment seems wrong. We can add 2 RangeData objects to aOutput.

(In reply to comment #7)
> Is it worth looking at the other internal callers of
> GetRangesForIntervalCOMArray, and converting them to use the indices version?

Not sure.
Comment 9 Graeme McCutcheon [:graememcc] 2009-05-09 14:39:06 PDT
Pushed http://hg.mozilla.org/mozilla-central/rev/3386a5757206 which turned out not to be the patch in which I'd fixed the comment, so pushed http://hg.mozilla.org/mozilla-central/rev/72030ec2e480 to fix. 

Sigh. Not the cleanest start to my commiting career.
Comment 10 Henri Sivonen (:hsivonen) (Not doing reviews or reading bugmail until 2016-08-01) 2010-02-22 08:05:02 PST
The test case for this bug has a bogus </head> tag where it should have a </title> tag (bug 546604).

Note You need to log in before you can comment on or make changes to this bug.