Closed
Bug 348681
Opened 18 years ago
Closed 15 years ago
Don't allow overlapping ranges in the selection
Categories
(Core :: DOM: Selection, defect)
Core
DOM: Selection
Tracking
()
RESOLVED
FIXED
mozilla1.9.2a1
People
(Reporter: brettw, Assigned: graememcc)
References
(Depends on 1 open bug)
Details
Attachments
(1 file, 2 obsolete files)
55.72 KB,
patch
|
roc
:
review+
roc
:
superreview+
|
Details | Diff | Splinter Review |
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.
Assignee | ||
Comment 1•16 years ago
|
||
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.)
Updated•16 years ago
|
QA Contact: selection
Assignee | ||
Comment 5•15 years ago
|
||
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.
Assignee | ||
Comment 7•15 years ago
|
||
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+
Assignee | ||
Comment 9•15 years ago
|
||
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.
Assignee | ||
Updated•15 years ago
|
Status: ASSIGNED → RESOLVED
Closed: 15 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla1.9.2a1
The test case for this bug has a bogus </head> tag where it should have a </title> tag (bug 546604).
You need to log in
before you can comment on or make changes to this bug.
Description
•