Closed Bug 348681 Opened 18 years ago Closed 15 years ago

Don't allow overlapping ranges in the selection

Categories

(Core :: DOM: Selection, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla1.9.2a1

People

(Reporter: brettw, Assigned: graememcc)

References

(Depends on 1 open bug)

Details

Attachments

(1 file, 2 obsolete files)

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.
Attached patch V1 for review (obsolete) — Splinter Review
Assignee: selection → graememcc_firefox
Status: NEW → ASSIGNED
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)
+    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.
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.)
QA Contact: selection
Attached patch v2 (obsolete) — Splinter 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.
Attached patch v3Splinter 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]
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.
Attachment #376394 - Flags: superreview?(roc)
Attachment #376394 - Flags: superreview+
Attachment #376394 - Flags: review?(roc)
Attachment #376394 - Flags: review+
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.
Status: ASSIGNED → RESOLVED
Closed: 15 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla1.9.2a1
Depends on: 510575
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).
Depends on: 673785
You need to log in before you can comment on or make changes to this bug.