Note: There are a few cases of duplicates in user autocompletion which are being worked on.

Don't allow overlapping ranges in the selection

RESOLVED FIXED in mozilla1.9.2a1



11 years ago
6 years ago


(Reporter: Brett Wilson, Assigned: graememcc)


(Depends on: 1 bug)

Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)



(1 attachment, 2 obsolete attachments)



11 years ago
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

9 years ago
Created attachment 333300 [details] [diff] [review]
V1 for review
Assignee: selection → graememcc_firefox
Attachment #333300 - Flags: superreview?(roc)
Attachment #333300 - Flags: review?(roc)
+  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)

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.
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.
(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.)


9 years ago
QA Contact: selection

Comment 5

8 years ago
Created attachment 373899 [details] [diff] [review]

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.
Attachment #333300 - Attachment is obsolete: true
Attachment #373899 - Flags: superreview?(roc)
Attachment #373899 - Flags: review?(roc)
Attachment #333300 - Flags: superreview?(roc)
Attachment #333300 - Flags: review?(roc)
+  // 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

8 years ago
Created attachment 376394 [details] [diff] [review]

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?
Attachment #373899 - Attachment is obsolete: true
Attachment #376394 - Flags: superreview?(roc)
Attachment #376394 - Flags: review?(roc)
Attachment #373899 - Flags: superreview?(roc)
Attachment #373899 - Flags: review?(roc)
Comment on attachment 376394 [details] [diff] [review]

+//    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.
Attachment #376394 - Flags: superreview?(roc)
Attachment #376394 - Flags: superreview+
Attachment #376394 - Flags: review?(roc)
Attachment #376394 - Flags: review+

Comment 9

8 years ago
Pushed which turned out not to be the patch in which I'd fixed the comment, so pushed to fix. 

Sigh. Not the cleanest start to my commiting career.


8 years ago
Last Resolved: 8 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla1.9.2a1


8 years ago
Depends on: 510575


8 years ago
Depends on: 493111
Depends on: 517968
The test case for this bug has a bogus </head> tag where it should have a </title> tag (bug 546604).


6 years ago
Depends on: 673785
You need to log in before you can comment on or make changes to this bug.