Bug 1216001 part 1 - Optimize nsRange::IsNodeSelected. r=bz
☠☠ backed out by d8804baafb3f ☠ ☠
authorMats Palmgren <mats@mozilla.com>
Fri, 12 Feb 2016 02:13:57 +0100
changeset 284075 c1646ffa71b40babef414c91078eaee3d5e9b0d7
parent 284074 bc43896028798d7be1607e785a33e445f4ac2268
child 284076 a30593ebd58e6bf9f31db4a1c9d9382d2591940a
push id29995
push usercbook@mozilla.com
push dateFri, 12 Feb 2016 14:16:12 +0000
treeherdermozilla-central@218d16a9ddcc [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbz
bugs1216001
milestone47.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1216001 part 1 - Optimize nsRange::IsNodeSelected. r=bz
dom/base/nsRange.cpp
dom/base/nsRange.h
mfbt/BinarySearch.h
--- a/dom/base/nsRange.cpp
+++ b/dom/base/nsRange.cpp
@@ -146,43 +146,92 @@ GetNextRangeCommonAncestor(nsINode* aNod
     if (!aNode->IsDescendantOfCommonAncestorForRangeInSelection()) {
       return nullptr;
     }
     aNode = aNode->GetParentNode();
   }
   return aNode;
 }
 
+/**
+ * A Comparator suitable for mozilla::BinarySearchIf for searching a collection
+ * of nsRange* for an overlap of (mNode, mStartOffset) .. (mNode, mEndOffset).
+ */
+struct IsItemInRangeComparator
+{
+  nsINode* mNode;
+  uint32_t mStartOffset;
+  uint32_t mEndOffset;
+
+  int operator()(const nsRange* const aRange) const
+  {
+    int32_t cmp = nsContentUtils::ComparePoints(mNode, mEndOffset,
+                                                aRange->GetStartParent(),
+                                                aRange->StartOffset());
+    if (cmp == 1) {
+      cmp = nsContentUtils::ComparePoints(mNode, mStartOffset,
+                                          aRange->GetEndParent(),
+                                          aRange->EndOffset());
+      if (cmp == -1) {
+        return 0;
+      }
+      return 1;
+    }
+    return -1;
+  }
+};
+
 /* static */ bool
 nsRange::IsNodeSelected(nsINode* aNode, uint32_t aStartOffset,
                         uint32_t aEndOffset)
 {
   NS_PRECONDITION(aNode, "bad arg");
 
   nsINode* n = GetNextRangeCommonAncestor(aNode);
   NS_ASSERTION(n || !aNode->IsSelectionDescendant(),
                "orphan selection descendant");
+
+  // Collect the potential ranges and their selection objects.
+  RangeHashTable ancestorSelectionRanges;
+  nsTHashtable<nsPtrHashKey<Selection>> ancestorSelections;
+  uint32_t maxRangeCount = 0;
   for (; n; n = GetNextRangeCommonAncestor(n->GetParentNode())) {
     RangeHashTable* ranges =
       static_cast<RangeHashTable*>(n->GetProperty(nsGkAtoms::range));
     for (auto iter = ranges->ConstIter(); !iter.Done(); iter.Next()) {
       nsRange* range = iter.Get()->GetKey();
       if (range->IsInSelection() && !range->Collapsed()) {
-        int32_t cmp = nsContentUtils::ComparePoints(aNode, aEndOffset,
-                                                    range->GetStartParent(),
-                                                    range->StartOffset());
-        if (cmp == 1) {
-          cmp = nsContentUtils::ComparePoints(aNode, aStartOffset,
-                                              range->GetEndParent(),
-                                              range->EndOffset());
-          if (cmp == -1) {
-            return true;
-          }
+        ancestorSelectionRanges.PutEntry(range);
+        Selection* selection = range->mSelection;
+        ancestorSelections.PutEntry(selection);
+        maxRangeCount = std::max(maxRangeCount, selection->RangeCount());
+      }
+    }
+  }
+
+  if (!ancestorSelectionRanges.IsEmpty()) {
+    nsTArray<const nsRange*> sortedRanges(maxRangeCount);
+    for (auto iter = ancestorSelections.ConstIter(); !iter.Done(); iter.Next()) {
+      Selection* selection = iter.Get()->GetKey();
+      // Sort the found ranges for |selection| in document order
+      // (Selection::GetRangeAt returns its ranges ordered).
+      for (uint32_t i = 0, len = selection->RangeCount(); i < len; ++i) {
+        nsRange* range = selection->GetRangeAt(i);
+        if (ancestorSelectionRanges.Contains(range)) {
+          sortedRanges.AppendElement(range);
         }
       }
+      MOZ_ASSERT(!sortedRanges.IsEmpty());
+      // Binary search the now sorted ranges.
+      IsItemInRangeComparator comparator = { aNode, aStartOffset, aEndOffset };
+      size_t unused;
+      if (mozilla::BinarySearchIf(sortedRanges, 0, sortedRanges.Length(), comparator, &unused)) {
+        return true;
+      }
+      sortedRanges.ClearAndRetainStorage();
     }
   }
   return false;
 }
 
 /******************************************************
  * constructor/destructor
  ******************************************************/
--- a/dom/base/nsRange.h
+++ b/dom/base/nsRange.h
@@ -247,16 +247,24 @@ public:
  *
  *  XXX - callers responsibility to ensure node in same doc as range!
  *
  *****************************************************************************/
   static nsresult CompareNodeToRange(nsINode* aNode, nsRange* aRange,
                                      bool *outNodeBefore,
                                      bool *outNodeAfter);
 
+  /**
+   * Return true if any part of (aNode, aStartOffset) .. (aNode, aEndOffset)
+   * overlaps any nsRange in aNode's GetNextRangeCommonAncestor ranges (i.e.
+   * where aNode is a descendant of a range's common ancestor node).
+   * If a nsRange starts in (aNode, aEndOffset) or if it ends in
+   * (aNode, aStartOffset) then it is non-overlapping and the result is false
+   * for that nsRange.  Collapsed ranges always counts as non-overlapping.
+   */
   static bool IsNodeSelected(nsINode* aNode, uint32_t aStartOffset,
                              uint32_t aEndOffset);
 
   static void CollectClientRects(nsLayoutUtils::RectCallback* aCollector,
                                  nsRange* aRange,
                                  nsINode* aStartParent, int32_t aStartOffset,
                                  nsINode* aEndParent, int32_t aEndOffset,
                                  bool aClampToEdge, bool aFlushLayout);
@@ -293,16 +301,24 @@ protected:
    * ancestor for the range.  This method uses the selection bits and
    * nsGkAtoms::range property on the nodes to quickly find the ancestor.
    * That is, it's a faster version of GetCommonAncestor that only works
    * for ranges in a Selection.  The method will assert and the behavior
    * is undefined if called on a range where IsInSelection() is false.
    */
   nsINode* GetRegisteredCommonAncestor();
 
+  // Helper to IsNodeSelected.
+  static bool IsNodeInSortedRanges(nsINode* aNode,
+                                   uint32_t aStartOffset,
+                                   uint32_t aEndOffset,
+                                   const nsTArray<const nsRange*>& aRanges,
+                                   size_t aRangeStart,
+                                   size_t aRangeEnd);
+
   struct MOZ_STACK_CLASS AutoInvalidateSelection
   {
     explicit AutoInvalidateSelection(nsRange* aRange) : mRange(aRange)
     {
 #ifdef DEBUG
       mWasInSelection = mRange->IsInSelection();
 #endif
       if (!mRange->IsInSelection() || mIsNested) {
--- a/mfbt/BinarySearch.h
+++ b/mfbt/BinarySearch.h
@@ -42,17 +42,17 @@ namespace mozilla {
  *
  * the value.
  *
  * Example:
  *
  *   struct Comparator {
  *     int operator()(int val) const {
  *       if (mTarget < val) return -1;
- *       if (mValue > val) return 1;
+ *       if (mTarget > val) return 1;
  *       return 0;
  *     }
  *     Comparator(int target) : mTarget(target) {}
        const int mTarget;
  *   };
  *
  *   Vector<int> sortedInts = ...
  *