Spelling and grammar dots should not overlap
authordbates@webkit.org <dbates@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 20 Sep 2017 23:13:27 +0000 (23:13 +0000)
committerdbates@webkit.org <dbates@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 20 Sep 2017 23:13:27 +0000 (23:13 +0000)
https://bugs.webkit.org/show_bug.cgi?id=177265
<rdar://problem/34556424>

Reviewed by David Hyatt.

Source/WebCore:

A line may contain both spelling and grammar errors such that these errors overlap.
For example, "to mooof or not to mooof.". It is more pleasing aesthetically to
paint spelling and grammar dots such that they do not overlap. This also matches
AppKit's behavior.

A side benefit of this change is that it adds support infrastructure towards
implementing the CSS Pseudo-Elements Module Level 4 pseudo elements ::spelling-error
and ::grammar-error (see <https://bugs.webkit.org/show_bug.cgi?id=175784>).
It will also make it straightforward to add ::inactive-selection and allow us
to make ::selection conform to CSS Pseudo-Elements Module Level 4.

* CMakeLists.txt: Add file MarkerSubrange.cpp.
* WebCore.xcodeproj/project.pbxproj: Add files MarkerSubrange.{cpp, h}.
* rendering/InlineTextBox.cpp:
(WebCore::InlineTextBox::paintDocumentMarker): Modified to take a const MarkerSubrange&
instead of a RenderedDocumentMarker&.
(WebCore::InlineTextBox::paintTextMatchMarker): Modified to take a const MarkerSubrange&
instead of a RenderedDocumentMarker& and take a boolean as to whether the text match is active.
(WebCore::InlineTextBox::paintDocumentMarkers): Collect the subranges that need to be
painted, subdivide them preserving only the frontmost subrange when two or more subranges
overlap and paint the resulting subranges.
(WebCore::lineStyleForMarkerType): Deleted; converted to a lambda function inlined
in paintDocumentMarker() as this is the only place we made use of this function.
* rendering/InlineTextBox.h:
* rendering/MarkerSubrange.cpp: Added.
(WebCore::subdivide): Subdivides the specified list of subranges and returns a list of non-overlapping
subranges in paint order. The implementation of subdivide() is derived from an algorithm that
Said Abou-Hallawa came up with.
* rendering/MarkerSubrange.h: Added.
(WebCore::MarkerSubrange::MarkerSubrange):

Tools:

Add unit tests for the subdivision algorithm.

* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WebCore/MarkerSubrange.cpp: Added.
(WebCore::operator<<):
(WebCore::operator==):
(TestWebKitAPI::TEST):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@222298 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/CMakeLists.txt
Source/WebCore/ChangeLog
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/rendering/InlineTextBox.cpp
Source/WebCore/rendering/InlineTextBox.h
Source/WebCore/rendering/MarkerSubrange.cpp [new file with mode: 0644]
Source/WebCore/rendering/MarkerSubrange.h [new file with mode: 0644]
Tools/ChangeLog
Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
Tools/TestWebKitAPI/Tests/WebCore/MarkerSubrange.cpp [new file with mode: 0644]

index b1aed6f..e7c14b2 100644 (file)
@@ -2657,6 +2657,7 @@ set(WebCore_SOURCES
     rendering/LayoutDisallowedScope.cpp
     rendering/LayoutRepainter.cpp
     rendering/LayoutState.cpp
+    rendering/MarkerSubrange.cpp
     rendering/OrderIterator.cpp
     rendering/PointerEventsHitRules.cpp
     rendering/RenderAttachment.cpp
index 42f596a..8a6cf56 100644 (file)
@@ -1,3 +1,42 @@
+2017-09-20  Daniel Bates  <dabates@apple.com>
+
+        Spelling and grammar dots should not overlap
+        https://bugs.webkit.org/show_bug.cgi?id=177265
+        <rdar://problem/34556424>
+
+        Reviewed by David Hyatt.
+
+        A line may contain both spelling and grammar errors such that these errors overlap.
+        For example, "to mooof or not to mooof.". It is more pleasing aesthetically to
+        paint spelling and grammar dots such that they do not overlap. This also matches
+        AppKit's behavior.
+
+        A side benefit of this change is that it adds support infrastructure towards
+        implementing the CSS Pseudo-Elements Module Level 4 pseudo elements ::spelling-error
+        and ::grammar-error (see <https://bugs.webkit.org/show_bug.cgi?id=175784>).
+        It will also make it straightforward to add ::inactive-selection and allow us
+        to make ::selection conform to CSS Pseudo-Elements Module Level 4.
+
+        * CMakeLists.txt: Add file MarkerSubrange.cpp.
+        * WebCore.xcodeproj/project.pbxproj: Add files MarkerSubrange.{cpp, h}.
+        * rendering/InlineTextBox.cpp:
+        (WebCore::InlineTextBox::paintDocumentMarker): Modified to take a const MarkerSubrange&
+        instead of a RenderedDocumentMarker&.
+        (WebCore::InlineTextBox::paintTextMatchMarker): Modified to take a const MarkerSubrange&
+        instead of a RenderedDocumentMarker& and take a boolean as to whether the text match is active.
+        (WebCore::InlineTextBox::paintDocumentMarkers): Collect the subranges that need to be
+        painted, subdivide them preserving only the frontmost subrange when two or more subranges
+        overlap and paint the resulting subranges.
+        (WebCore::lineStyleForMarkerType): Deleted; converted to a lambda function inlined
+        in paintDocumentMarker() as this is the only place we made use of this function.
+        * rendering/InlineTextBox.h:
+        * rendering/MarkerSubrange.cpp: Added.
+        (WebCore::subdivide): Subdivides the specified list of subranges and returns a list of non-overlapping
+        subranges in paint order. The implementation of subdivide() is derived from an algorithm that
+        Said Abou-Hallawa came up with.
+        * rendering/MarkerSubrange.h: Added.
+        (WebCore::MarkerSubrange::MarkerSubrange):
+
 2017-09-20  Alex Christensen  <achristensen@webkit.org>
 
         Remove ActionType::CSSDisplayNoneStyleSheet
index 9b71090..63b246e 100644 (file)
                CE057FA61220731100A476D5 /* DocumentMarkerController.h in Headers */ = {isa = PBXBuildFile; fileRef = CE057FA41220731100A476D5 /* DocumentMarkerController.h */; settings = {ATTRIBUTES = (Private, ); }; };
                CE08C3D1152B599A0021B8C2 /* AlternativeTextController.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE08C3CF152B599A0021B8C2 /* AlternativeTextController.cpp */; };
                CE08C3D2152B599A0021B8C2 /* AlternativeTextController.h in Headers */ = {isa = PBXBuildFile; fileRef = CE08C3D0152B599A0021B8C2 /* AlternativeTextController.h */; settings = {ATTRIBUTES = (); }; };
+               CE1866441F72E5B400A0CAB6 /* MarkerSubrange.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE1866421F72E5B400A0CAB6 /* MarkerSubrange.cpp */; };
+               CE1866451F72E5B400A0CAB6 /* MarkerSubrange.h in Headers */ = {isa = PBXBuildFile; fileRef = CE1866431F72E5B400A0CAB6 /* MarkerSubrange.h */; settings = {ATTRIBUTES = (Private, ); }; };
                CE2849871CA360DF00B4A57F /* ContentSecurityPolicyDirectiveNames.h in Headers */ = {isa = PBXBuildFile; fileRef = CE2849861CA360DF00B4A57F /* ContentSecurityPolicyDirectiveNames.h */; };
                CE2849891CA3614600B4A57F /* ContentSecurityPolicyDirectiveNames.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE2849881CA3614600B4A57F /* ContentSecurityPolicyDirectiveNames.cpp */; };
                CE6DADF91C591E6A003F6A88 /* ContentSecurityPolicyResponseHeaders.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE6DADF71C591E6A003F6A88 /* ContentSecurityPolicyResponseHeaders.cpp */; };
                CE057FA41220731100A476D5 /* DocumentMarkerController.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DocumentMarkerController.h; sourceTree = "<group>"; };
                CE08C3CF152B599A0021B8C2 /* AlternativeTextController.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AlternativeTextController.cpp; sourceTree = "<group>"; };
                CE08C3D0152B599A0021B8C2 /* AlternativeTextController.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AlternativeTextController.h; sourceTree = "<group>"; };
+               CE1866421F72E5B400A0CAB6 /* MarkerSubrange.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = MarkerSubrange.cpp; sourceTree = "<group>"; };
+               CE1866431F72E5B400A0CAB6 /* MarkerSubrange.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = MarkerSubrange.h; sourceTree = "<group>"; };
                CE2849861CA360DF00B4A57F /* ContentSecurityPolicyDirectiveNames.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ContentSecurityPolicyDirectiveNames.h; path = csp/ContentSecurityPolicyDirectiveNames.h; sourceTree = "<group>"; };
                CE2849881CA3614600B4A57F /* ContentSecurityPolicyDirectiveNames.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ContentSecurityPolicyDirectiveNames.cpp; path = csp/ContentSecurityPolicyDirectiveNames.cpp; sourceTree = "<group>"; };
                CE5CB1B314EDAB6F00BB2795 /* EventSender.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = EventSender.h; sourceTree = "<group>"; };
                                2D9066040BE141D400956998 /* LayoutState.cpp */,
                                2D9066050BE141D400956998 /* LayoutState.h */,
                                9BA273F3172206BB0097CE47 /* LogicalSelectionOffsetCaches.h */,
+                               CE1866421F72E5B400A0CAB6 /* MarkerSubrange.cpp */,
+                               CE1866431F72E5B400A0CAB6 /* MarkerSubrange.h */,
                                CDE7FC42181904B1002BBB77 /* OrderIterator.cpp */,
                                CDE7FC43181904B1002BBB77 /* OrderIterator.h */,
                                3774ABA30FA21EB400AD7DE9 /* OverlapTestRequestClient.h */,
                                7AE6C93C1BE0C60100E19E03 /* MainThreadSharedTimer.h in Headers */,
                                1A8F6BC60DB55CDC001DB794 /* ManifestParser.h in Headers */,
                                93309DF8099E64920056E581 /* markup.h in Headers */,
+                               CE1866451F72E5B400A0CAB6 /* MarkerSubrange.h in Headers */,
                                9728C3141268E4390041E89B /* MarkupAccumulator.h in Headers */,
                                00C60E3F13D76D7E0092A275 /* MarkupTokenizerInlines.h in Headers */,
                                FABE72F51059C1EB00D888CC /* MathMLAnnotationElement.h in Headers */,
                                7AE6C9381BE0C5C800E19E03 /* MainThreadSharedTimerCF.cpp in Sources */,
                                1A8F6BC50DB55CDC001DB794 /* ManifestParser.cpp in Sources */,
                                93309DF7099E64920056E581 /* markup.cpp in Sources */,
+                               CE1866441F72E5B400A0CAB6 /* MarkerSubrange.cpp in Sources */,
                                9728C3131268E4390041E89B /* MarkupAccumulator.cpp in Sources */,
                                FABE72F41059C1EB00D888CC /* MathMLAnnotationElement.cpp in Sources */,
                                FABE72F41059C1EB00D999DD /* MathMLElement.cpp in Sources */,
index 575fa06..3b10867 100644 (file)
@@ -1,7 +1,7 @@
 /*
  * (C) 1999 Lars Knoll (knoll@kde.org)
  * (C) 2000 Dirk Mueller (mueller@kde.org)
- * Copyright (C) 2004-2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2004-2017 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -34,6 +34,7 @@
 #include "HitTestResult.h"
 #include "ImageBuffer.h"
 #include "InlineTextBoxStyle.h"
+#include "MarkerSubrange.h"
 #include "Page.h"
 #include "PaintInfo.h"
 #include "RenderBlock.h"
@@ -782,29 +783,7 @@ void InlineTextBox::paintDecoration(GraphicsContext& context, const FontCascade&
         context.concatCTM(rotation(boxRect, Counterclockwise));
 }
 
-static GraphicsContext::DocumentMarkerLineStyle lineStyleForMarkerType(DocumentMarker::MarkerType markerType)
-{
-    switch (markerType) {
-    case DocumentMarker::Spelling:
-        return GraphicsContext::DocumentMarkerSpellingLineStyle;
-    case DocumentMarker::Grammar:
-        return GraphicsContext::DocumentMarkerGrammarLineStyle;
-    case DocumentMarker::CorrectionIndicator:
-        return GraphicsContext::DocumentMarkerAutocorrectionReplacementLineStyle;
-    case DocumentMarker::DictationAlternatives:
-        return GraphicsContext::DocumentMarkerDictationAlternativesLineStyle;
-#if PLATFORM(IOS)
-    case DocumentMarker::DictationPhraseWithAlternatives:
-        // FIXME: Rename TextCheckingDictationPhraseWithAlternativesLineStyle and remove the PLATFORM(IOS)-guard.
-        return GraphicsContext::TextCheckingDictationPhraseWithAlternativesLineStyle;
-#endif
-    default:
-        ASSERT_NOT_REACHED();
-        return GraphicsContext::DocumentMarkerSpellingLineStyle;
-    }
-}
-
-void InlineTextBox::paintDocumentMarker(GraphicsContext& context, const FloatPoint& boxOrigin, RenderedDocumentMarker& marker, const RenderStyle& style, const FontCascade& font)
+void InlineTextBox::paintDocumentMarker(GraphicsContext& context, const FloatPoint& boxOrigin, const MarkerSubrange& subrange, const RenderStyle& style, const FontCascade& font)
 {
     // Never print spelling/grammar markers (5327887)
     if (renderer().document().printing())
@@ -818,16 +797,16 @@ void InlineTextBox::paintDocumentMarker(GraphicsContext& context, const FloatPoi
 
     // Determine whether we need to measure text
     bool markerSpansWholeBox = true;
-    if (m_start <= marker.startOffset())
+    if (m_start <= subrange.startOffset)
         markerSpansWholeBox = false;
-    if ((end() + 1) != marker.endOffset()) // end points at the last char, not past it
+    if ((end() + 1) != subrange.endOffset) // End points at the last char, not past it
         markerSpansWholeBox = false;
     if (m_truncation != cNoTruncation)
         markerSpansWholeBox = false;
 
     if (!markerSpansWholeBox) {
-        unsigned startPosition = clampedOffset(marker.startOffset());
-        unsigned endPosition = clampedOffset(marker.endOffset());
+        unsigned startPosition = clampedOffset(subrange.startOffset);
+        unsigned endPosition = clampedOffset(subrange.endOffset);
         
         if (m_truncation != cNoTruncation)
             endPosition = std::min(endPosition, static_cast<unsigned>(m_truncation));
@@ -845,6 +824,27 @@ void InlineTextBox::paintDocumentMarker(GraphicsContext& context, const FloatPoi
         width = markerRect.width();
     }
     
+    auto lineStyleForSubrangeType = [] (MarkerSubrange::Type type) {
+        switch (type) {
+        case MarkerSubrange::SpellingError:
+            return GraphicsContext::DocumentMarkerSpellingLineStyle;
+        case MarkerSubrange::GrammarError:
+            return GraphicsContext::DocumentMarkerGrammarLineStyle;
+        case MarkerSubrange::Correction:
+            return GraphicsContext::DocumentMarkerAutocorrectionReplacementLineStyle;
+        case MarkerSubrange::DictationAlternatives:
+            return GraphicsContext::DocumentMarkerDictationAlternativesLineStyle;
+#if PLATFORM(IOS)
+        case MarkerSubrange::DictationPhraseWithAlternatives:
+            // FIXME: Rename TextCheckingDictationPhraseWithAlternativesLineStyle and remove the PLATFORM(IOS)-guard.
+            return GraphicsContext::TextCheckingDictationPhraseWithAlternativesLineStyle;
+#endif
+        default:
+            ASSERT_NOT_REACHED();
+            return GraphicsContext::DocumentMarkerSpellingLineStyle;
+        }
+    };
+
     // IMPORTANT: The misspelling underline is not considered when calculating the text bounds, so we have to
     // make sure to fit within those bounds.  This means the top pixel(s) of the underline will overlap the
     // bottom pixel(s) of the glyphs in smaller font sizes.  The alternatives are to increase the line spacing (bad!!)
@@ -862,15 +862,15 @@ void InlineTextBox::paintDocumentMarker(GraphicsContext& context, const FloatPoi
         // In larger fonts, though, place the underline up near the baseline to prevent a big gap.
         underlineOffset = baseline + 2;
     }
-    context.drawLineForDocumentMarker(FloatPoint(boxOrigin.x() + start, boxOrigin.y() + underlineOffset), width, lineStyleForMarkerType(marker.type()));
+    context.drawLineForDocumentMarker(FloatPoint(boxOrigin.x() + start, boxOrigin.y() + underlineOffset), width, lineStyleForSubrangeType(subrange.type));
 }
 
-void InlineTextBox::paintTextMatchMarker(GraphicsContext& context, const FloatPoint& boxOrigin, RenderedDocumentMarker& marker, const RenderStyle& style, const FontCascade& font)
+void InlineTextBox::paintTextMatchMarker(GraphicsContext& context, const FloatPoint& boxOrigin, const MarkerSubrange& subrange, const RenderStyle& style, const FontCascade& font, bool isActiveMatch)
 {
     if (!renderer().frame().editor().markedTextMatchesAreHighlighted())
         return;
 
-    Color color = marker.isActiveMatch() ? renderer().theme().platformActiveTextSearchHighlightColor() : renderer().theme().platformInactiveTextSearchHighlightColor();
+    auto color = isActiveMatch ? renderer().theme().platformActiveTextSearchHighlightColor() : renderer().theme().platformInactiveTextSearchHighlightColor();
     GraphicsContextStateSaver stateSaver(context);
     updateGraphicsContext(context, TextPaintStyle(color)); // Don't draw text at all!
 
@@ -879,8 +879,8 @@ void InlineTextBox::paintTextMatchMarker(GraphicsContext& context, const FloatPo
     LayoutUnit deltaY = renderer().style().isFlippedLinesWritingMode() ? selectionBottom() - logicalBottom() : logicalTop() - selectionTop();
     LayoutRect selectionRect = LayoutRect(boxOrigin.x(), boxOrigin.y() - deltaY, 0, this->selectionHeight());
 
-    unsigned sPos = clampedOffset(marker.startOffset());
-    unsigned ePos = clampedOffset(marker.endOffset());
+    unsigned sPos = clampedOffset(subrange.startOffset);
+    unsigned ePos = clampedOffset(subrange.endOffset);
     TextRun run = constructTextRun(style);
     font.adjustSelectionRectForText(run, selectionRect, sPos, ePos);
 
@@ -889,7 +889,7 @@ void InlineTextBox::paintTextMatchMarker(GraphicsContext& context, const FloatPo
 
     context.fillRect(snapRectToDevicePixelsWithWritingDirection(selectionRect, renderer().document().deviceScaleFactor(), run.ltr()), color);
 }
-    
+
 void InlineTextBox::paintDocumentMarkers(GraphicsContext& context, const FloatPoint& boxOrigin, const RenderStyle& style, const FontCascade& font, bool background)
 {
     if (!renderer().textNode())
@@ -897,6 +897,30 @@ void InlineTextBox::paintDocumentMarkers(GraphicsContext& context, const FloatPo
 
     Vector<RenderedDocumentMarker*> markers = renderer().document().markers().markersFor(renderer().textNode());
 
+    auto markerTypeForSubrangeType = [] (DocumentMarker::MarkerType type) {
+        switch (type) {
+        case DocumentMarker::Spelling:
+            return MarkerSubrange::SpellingError;
+        case DocumentMarker::Grammar:
+            return MarkerSubrange::GrammarError;
+        case DocumentMarker::CorrectionIndicator:
+            return MarkerSubrange::Correction;
+        case DocumentMarker::TextMatch:
+            return MarkerSubrange::TextMatch;
+        case DocumentMarker::DictationAlternatives:
+            return MarkerSubrange::DictationAlternatives;
+#if PLATFORM(IOS)
+        case DocumentMarker::DictationPhraseWithAlternatives:
+            return MarkerSubrange::DictationPhraseWithAlternatives;
+#endif
+        default:
+            return MarkerSubrange::Unmarked;
+        }
+    };
+
+    Vector<MarkerSubrange> subranges;
+    subranges.reserveInitialCapacity(markers.size());
+
     // Give any document markers that touch this run a chance to draw before the text has been drawn.
     // Note end() points at the last char, not one past it like endOffset and ranges do.
     for (auto* marker : markers) {
@@ -939,19 +963,13 @@ void InlineTextBox::paintDocumentMarkers(GraphicsContext& context, const FloatPo
             case DocumentMarker::Spelling:
             case DocumentMarker::CorrectionIndicator:
             case DocumentMarker::DictationAlternatives:
-                paintDocumentMarker(context, boxOrigin, *marker, style, font);
-                break;
             case DocumentMarker::Grammar:
-                paintDocumentMarker(context, boxOrigin, *marker, style, font);
-                break;
 #if PLATFORM(IOS)
             // FIXME: See <rdar://problem/8933352>. Also, remove the PLATFORM(IOS)-guard.
             case DocumentMarker::DictationPhraseWithAlternatives:
-                paintDocumentMarker(context, boxOrigin, *marker, style, font);
-                break;
 #endif
             case DocumentMarker::TextMatch:
-                paintTextMatchMarker(context, boxOrigin, *marker, style, font);
+                subranges.uncheckedAppend({ marker->startOffset(), marker->endOffset(), markerTypeForSubrangeType(marker->type()), marker });
                 break;
             case DocumentMarker::Replacement:
                 break;
@@ -962,7 +980,13 @@ void InlineTextBox::paintDocumentMarkers(GraphicsContext& context, const FloatPo
             default:
                 ASSERT_NOT_REACHED();
         }
+    }
 
+    for (auto& subrange : subdivide(subranges, OverlapStrategy::Frontmost)) {
+        if (subrange.type == MarkerSubrange::TextMatch)
+            paintTextMatchMarker(context, boxOrigin, subrange, style, font, subrange.marker->isActiveMatch());
+        else
+            paintDocumentMarker(context, boxOrigin, subrange, style, font);
     }
 }
 
index 2274dc7..0875280 100644 (file)
@@ -1,7 +1,7 @@
 /*
  * (C) 1999 Lars Knoll (knoll@kde.org)
  * (C) 2000 Dirk Mueller (mueller@kde.org)
- * Copyright (C) 2004, 2005, 2006, 2009, 2010, 2011, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2004-2017 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
 
 namespace WebCore {
 
-struct CompositionUnderline;
 class RenderCombineText;
 class RenderedDocumentMarker;
 class TextPainter;
+struct CompositionUnderline;
+struct MarkerSubrange;
 struct TextPaintStyle;
 
 const unsigned short cNoTruncation = USHRT_MAX;
@@ -161,8 +162,8 @@ private:
     void paintDecoration(GraphicsContext&, const FontCascade&, RenderCombineText*, const TextRun&, const FloatPoint& textOrigin, const FloatRect& boxRect,
         TextDecoration, TextPaintStyle, const ShadowData*, const FloatRect& clipOutRect);
     void paintSelection(GraphicsContext&, const FloatPoint& boxOrigin, const RenderStyle&, const FontCascade&, const Color& textColor);
-    void paintDocumentMarker(GraphicsContext&, const FloatPoint& boxOrigin, RenderedDocumentMarker&, const RenderStyle&, const FontCascade&);
-    void paintTextMatchMarker(GraphicsContext&, const FloatPoint& boxOrigin, RenderedDocumentMarker&, const RenderStyle&, const FontCascade&);
+    void paintDocumentMarker(GraphicsContext&, const FloatPoint& boxOrigin, const MarkerSubrange&, const RenderStyle&, const FontCascade&);
+    void paintTextMatchMarker(GraphicsContext&, const FloatPoint& boxOrigin, const MarkerSubrange&, const RenderStyle&, const FontCascade&, bool isActiveMatch);
 
     ExpansionBehavior expansionBehavior() const;
 
diff --git a/Source/WebCore/rendering/MarkerSubrange.cpp b/Source/WebCore/rendering/MarkerSubrange.cpp
new file mode 100644 (file)
index 0000000..32cbf96
--- /dev/null
@@ -0,0 +1,94 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "MarkerSubrange.h"
+
+#include <wtf/HashSet.h>
+#include <algorithm>
+
+namespace WebCore {
+
+Vector<MarkerSubrange> subdivide(const Vector<MarkerSubrange>& subranges, OverlapStrategy overlapStrategy)
+{
+    if (subranges.isEmpty())
+        return { };
+
+    struct Offset {
+        enum Kind { Begin, End };
+        Kind kind;
+        unsigned value; // Copy of subrange.startOffset/endOffset to avoid the need to branch based on kind.
+        const MarkerSubrange* subrange;
+    };
+
+    // 1. Build table of all offsets.
+    Vector<Offset> offsets;
+    ASSERT(subranges.size() < std::numeric_limits<unsigned>::max() / 2);
+    unsigned numberOfSubranges = subranges.size();
+    unsigned numberOfOffsets = 2 * numberOfSubranges;
+    offsets.reserveInitialCapacity(numberOfOffsets);
+    for (auto& subrange : subranges) {
+        offsets.uncheckedAppend({ Offset::Begin, subrange.startOffset, &subrange });
+        offsets.uncheckedAppend({ Offset::End, subrange.endOffset, &subrange });
+    }
+
+    // 2. Sort offsets such that begin offsets are in paint order and end offsets are in reverse paint order.
+    std::sort(offsets.begin(), offsets.end(), [] (const Offset& a, const Offset& b) {
+        return a.value < b.value || (a.value == b.value && a.kind == b.kind && a.kind == Offset::Begin && a.subrange->type < b.subrange->type)
+        || (a.value == b.value && a.kind == b.kind && a.kind == Offset::End && a.subrange->type > b.subrange->type);
+    });
+
+    // 3. Compute intersection.
+    Vector<MarkerSubrange> result;
+    result.reserveInitialCapacity(numberOfSubranges);
+    HashSet<const MarkerSubrange*> processedSubranges;
+    unsigned offsetSoFar = offsets[0].value;
+    for (unsigned i = 1; i < numberOfOffsets; ++i) {
+        if (offsets[i].value > offsets[i - 1].value) {
+            if (overlapStrategy == OverlapStrategy::Frontmost) {
+                std::optional<unsigned> frontmost;
+                for (unsigned j = 0; j < i; ++j) {
+                    if (!processedSubranges.contains(offsets[j].subrange))
+                        frontmost = j;
+                }
+                if (frontmost)
+                    result.append({ offsetSoFar, offsets[i].value, offsets[frontmost.value()].subrange->type, offsets[frontmost.value()].subrange->marker });
+            } else {
+                for (unsigned j = 0; j < i; ++j) {
+                    if (!processedSubranges.contains(offsets[j].subrange))
+                        result.append({ offsetSoFar, offsets[i].value, offsets[j].subrange->type, offsets[j].subrange->marker });
+                }
+            }
+            offsetSoFar = offsets[i].value;
+        }
+        if (offsets[i].kind == Offset::End)
+            processedSubranges.add(offsets[i].subrange);
+    }
+    return result;
+}
+
+}
+
+
diff --git a/Source/WebCore/rendering/MarkerSubrange.h b/Source/WebCore/rendering/MarkerSubrange.h
new file mode 100644 (file)
index 0000000..dd52118
--- /dev/null
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+class RenderedDocumentMarker;
+
+struct MarkerSubrange {
+    // Sorted by paint order
+    enum Type {
+        Unmarked,
+        GrammarError,
+        Correction,
+        SpellingError,
+        TextMatch,
+        DictationAlternatives,
+#if PLATFORM(IOS)
+        // FIXME: See <rdar://problem/8933352>. Also, remove the PLATFORM(IOS)-guard.
+        DictationPhraseWithAlternatives,
+#endif
+    };
+#if !COMPILER_SUPPORTS(NSDMI_FOR_AGGREGATES)
+    MarkerSubrange() = default;
+    MarkerSubrange(unsigned startOffset, unsigned endOffset, Type type, const RenderedDocumentMarker* marker = nullptr)
+        : startOffset { startOffset }
+        , endOffset { endOffset }
+        , type { type }
+        , marker { marker }
+    {
+    }
+#endif
+    unsigned startOffset;
+    unsigned endOffset;
+    Type type;
+    const RenderedDocumentMarker* marker { nullptr };
+};
+
+enum class OverlapStrategy { None, Frontmost };
+WEBCORE_EXPORT Vector<MarkerSubrange> subdivide(const Vector<MarkerSubrange>&, OverlapStrategy = OverlapStrategy::None);
+
+}
+
index 9906e91..007e32f 100644 (file)
@@ -1,3 +1,19 @@
+2017-09-20  Daniel Bates  <dabates@apple.com>
+
+        Spelling and grammar dots should not overlap
+        https://bugs.webkit.org/show_bug.cgi?id=177265
+        <rdar://problem/34556424>
+
+        Reviewed by David Hyatt.
+
+        Add unit tests for the subdivision algorithm.
+
+        * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+        * TestWebKitAPI/Tests/WebCore/MarkerSubrange.cpp: Added.
+        (WebCore::operator<<):
+        (WebCore::operator==):
+        (TestWebKitAPI::TEST):
+
 2017-09-20  Filip Pizlo  <fpizlo@apple.com>
 
         WSL should not type-check functions in the standard library that it does not use
index f1db8e0..afb582f 100644 (file)
                CDE195B51CFE0B880053D256 /* FullscreenTopContentInset.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = CDE195B21CFE0ADE0053D256 /* FullscreenTopContentInset.html */; };
                CE06DF9B1E1851F200E570C9 /* SecurityOrigin.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE06DF9A1E1851F200E570C9 /* SecurityOrigin.cpp */; };
                CE14F1A4181873B0001C2705 /* WillPerformClientRedirectToURLCrash.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = CE14F1A2181873B0001C2705 /* WillPerformClientRedirectToURLCrash.html */; };
+               CE1866491F72E8F100A0CAB6 /* MarkerSubrange.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE1866471F72E8F100A0CAB6 /* MarkerSubrange.cpp */; };
                CE3524F81B1431F60028A7C5 /* TextFieldDidBeginAndEndEditing_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE3524F21B142B8D0028A7C5 /* TextFieldDidBeginAndEndEditing_Bundle.cpp */; };
                CE3524F91B1441C40028A7C5 /* TextFieldDidBeginAndEndEditing.cpp in Sources */ = {isa = PBXBuildFile; fileRef = CE3524F11B142B8D0028A7C5 /* TextFieldDidBeginAndEndEditing.cpp */; };
                CE3524FA1B1443890028A7C5 /* input-focus-blur.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = CE3524F51B142BBB0028A7C5 /* input-focus-blur.html */; };
                CDE195B31CFE0ADE0053D256 /* FullscreenTopContentInset.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = FullscreenTopContentInset.mm; sourceTree = "<group>"; };
                CE06DF9A1E1851F200E570C9 /* SecurityOrigin.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SecurityOrigin.cpp; sourceTree = "<group>"; };
                CE14F1A2181873B0001C2705 /* WillPerformClientRedirectToURLCrash.html */ = {isa = PBXFileReference; lastKnownFileType = text.html; path = WillPerformClientRedirectToURLCrash.html; sourceTree = "<group>"; };
+               CE1866471F72E8F100A0CAB6 /* MarkerSubrange.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = MarkerSubrange.cpp; sourceTree = "<group>"; };
                CE32C7C718184C4900CD8C28 /* WillPerformClientRedirectToURLCrash.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = WillPerformClientRedirectToURLCrash.mm; sourceTree = "<group>"; };
                CE3524F11B142B8D0028A7C5 /* TextFieldDidBeginAndEndEditing.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TextFieldDidBeginAndEndEditing.cpp; sourceTree = "<group>"; };
                CE3524F21B142B8D0028A7C5 /* TextFieldDidBeginAndEndEditing_Bundle.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TextFieldDidBeginAndEndEditing_Bundle.cpp; sourceTree = "<group>"; };
                                7A909A751D877475007E10F8 /* IntSize.cpp */,
                                14464012167A8305000BD218 /* LayoutUnit.cpp */,
                                076E507E1F45031E006E9F5A /* Logging.cpp */,
+                               CE1866471F72E8F100A0CAB6 /* MarkerSubrange.cpp */,
                                A5B149DD1F5A19DC00C6DAFF /* MIMETypeRegistry.cpp */,
                                CD225C071C45A69200140761 /* ParsedContentRange.cpp */,
                                F418BE141F71B7DC001970E6 /* RoundedRectTests.cpp */,
                                7CCE7ED11A411A7E00447C4C /* StringTruncator.mm in Sources */,
                                ECA680CE1E68CC0900731D20 /* StringUtilities.mm in Sources */,
                                CE4D5DE71F6743BA0072CFC6 /* StringWithDirection.cpp in Sources */,
+                               CE1866491F72E8F100A0CAB6 /* MarkerSubrange.cpp in Sources */,
                                7CCE7ED21A411A7E00447C4C /* SubresourceErrorCrash.mm in Sources */,
                                7CCE7EA81A411A1900447C4C /* SyntheticBackingScaleFactorWindow.m in Sources */,
                                7CCE7F161A411AE600447C4C /* TerminateTwice.cpp in Sources */,
diff --git a/Tools/TestWebKitAPI/Tests/WebCore/MarkerSubrange.cpp b/Tools/TestWebKitAPI/Tests/WebCore/MarkerSubrange.cpp
new file mode 100644 (file)
index 0000000..d8d0ffd
--- /dev/null
@@ -0,0 +1,178 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include "Test.h"
+#include <WebCore/MarkerSubrange.h>
+#include <WebCore/RenderedDocumentMarker.h>
+
+using namespace WebCore;
+
+namespace WebCore {
+
+std::ostream& operator<<(std::ostream& os, MarkerSubrange::Type type)
+{
+    switch (type) {
+    case MarkerSubrange::Unmarked:
+        return os << "Unmarked";
+    case MarkerSubrange::GrammarError:
+        return os << "GrammarError";
+    case MarkerSubrange::Correction:
+        return os << "Correction";
+    case MarkerSubrange::SpellingError:
+        return os << "SpellingError";
+    case MarkerSubrange::TextMatch:
+        return os << "TextMatch";
+    case MarkerSubrange::DictationAlternatives:
+        return os << "DictationAlternatives";
+#if PLATFORM(IOS)
+        // FIXME: See <rdar://problem/8933352>. Also, remove the PLATFORM(IOS)-guard.
+    case MarkerSubrange::DictationPhraseWithAlternatives:
+        return os << "DictationPhraseWithAlternatives";
+#endif
+    }
+}
+
+std::ostream& operator<<(std::ostream& os, const MarkerSubrange& subrange)
+{
+    os << "(" << subrange.startOffset << ", " << subrange.endOffset << ", " << subrange.type;
+    if (subrange.marker)
+        os << static_cast<const void*>(subrange.marker);
+    return os << ")";
+}
+
+bool operator==(const MarkerSubrange& a, const MarkerSubrange& b)
+{
+    return a.startOffset == b.startOffset && a.endOffset == b.endOffset && a.type == b.type && a.marker == b.marker;
+}
+
+}
+
+namespace TestWebKitAPI {
+
+TEST(MarkerSubrange, SubdivideEmpty)
+{
+    EXPECT_EQ(0U, subdivide({ }).size());
+    EXPECT_EQ(0U, subdivide({ }, OverlapStrategy::Frontmost).size());
+}
+
+TEST(MarkerSubrange, SubdivideSimple)
+{
+    MarkerSubrange subrange { 0, 9, MarkerSubrange::SpellingError };
+    auto results = subdivide({ subrange });
+    ASSERT_EQ(1U, results.size());
+    EXPECT_EQ(subrange, results[0]);
+}
+
+TEST(MarkerSubrange, SubdivideSpellingAndGrammarSimple)
+{
+    RenderedDocumentMarker grammarErrorMarker { DocumentMarker { DocumentMarker::Grammar, 7, 8 } };
+    Vector<MarkerSubrange> expectedSubranges {
+        MarkerSubrange { grammarErrorMarker.startOffset(), grammarErrorMarker.endOffset(), MarkerSubrange::GrammarError, &grammarErrorMarker },
+        MarkerSubrange { 22, 32, MarkerSubrange::SpellingError },
+    };
+    auto results = subdivide(expectedSubranges);
+    ASSERT_EQ(expectedSubranges.size(), results.size());
+    for (size_t i = 0; i < expectedSubranges.size(); ++i)
+        EXPECT_EQ(expectedSubranges[i], results[i]);
+}
+
+TEST(MarkerSubrange, SubdivideSpellingAndGrammarOverlap)
+{
+    Vector<MarkerSubrange> subranges {
+        MarkerSubrange { 0, 40, MarkerSubrange::GrammarError },
+        MarkerSubrange { 2, 17, MarkerSubrange::SpellingError },
+        MarkerSubrange { 20, 40, MarkerSubrange::SpellingError },
+        MarkerSubrange { 41, 45, MarkerSubrange::SpellingError },
+    };
+    Vector<MarkerSubrange> expectedSubranges {
+        MarkerSubrange { 0, 2, MarkerSubrange::GrammarError },
+        MarkerSubrange { 2, 17, MarkerSubrange::GrammarError },
+        MarkerSubrange { 2, 17, MarkerSubrange::SpellingError },
+        MarkerSubrange { 17, 20, MarkerSubrange::GrammarError },
+        MarkerSubrange { 20, 40, MarkerSubrange::GrammarError },
+        MarkerSubrange { 20, 40, MarkerSubrange::SpellingError },
+        MarkerSubrange { 41, 45, MarkerSubrange::SpellingError },
+    };
+    auto results = subdivide(subranges);
+    ASSERT_EQ(expectedSubranges.size(), results.size());
+    for (size_t i = 0; i < expectedSubranges.size(); ++i)
+        EXPECT_EQ(expectedSubranges[i], results[i]);
+}
+
+TEST(MarkerSubrange, SubdivideSpellingAndGrammarOverlapFrontmost)
+{
+    Vector<MarkerSubrange> subranges {
+        MarkerSubrange { 0, 40, MarkerSubrange::GrammarError },
+        MarkerSubrange { 2, 17, MarkerSubrange::SpellingError },
+        MarkerSubrange { 20, 40, MarkerSubrange::SpellingError },
+        MarkerSubrange { 41, 45, MarkerSubrange::SpellingError },
+    };
+    Vector<MarkerSubrange> expectedSubranges {
+        MarkerSubrange { 0, 2, MarkerSubrange::GrammarError },
+        MarkerSubrange { 2, 17, MarkerSubrange::SpellingError },
+        MarkerSubrange { 17, 20, MarkerSubrange::GrammarError },
+        MarkerSubrange { 20, 40, MarkerSubrange::SpellingError },
+        MarkerSubrange { 41, 45, MarkerSubrange::SpellingError },
+    };
+    auto results = subdivide(subranges, OverlapStrategy::Frontmost);
+    ASSERT_EQ(expectedSubranges.size(), results.size());
+    for (size_t i = 0; i < expectedSubranges.size(); ++i)
+        EXPECT_EQ(expectedSubranges[i], results[i]);
+}
+
+TEST(MarkerSubrange, SubdivideSpellingAndGrammarComplicatedFrontmost)
+{
+    Vector<MarkerSubrange> subranges {
+        MarkerSubrange { 0, 6, MarkerSubrange::SpellingError },
+        MarkerSubrange { 0, 46, MarkerSubrange::GrammarError },
+        MarkerSubrange { 7, 16, MarkerSubrange::SpellingError },
+        MarkerSubrange { 22, 27, MarkerSubrange::SpellingError },
+        MarkerSubrange { 34, 44, MarkerSubrange::SpellingError },
+        MarkerSubrange { 46, 50, MarkerSubrange::SpellingError },
+        MarkerSubrange { 51, 58, MarkerSubrange::SpellingError },
+        MarkerSubrange { 59, 63, MarkerSubrange::GrammarError },
+    };
+    Vector<MarkerSubrange> expectedSubranges {
+        MarkerSubrange { 0, 6, MarkerSubrange::SpellingError },
+        MarkerSubrange { 6, 7, MarkerSubrange::GrammarError },
+        MarkerSubrange { 7, 16, MarkerSubrange::SpellingError },
+        MarkerSubrange { 16, 22, MarkerSubrange::GrammarError },
+        MarkerSubrange { 22, 27, MarkerSubrange::SpellingError },
+        MarkerSubrange { 27, 34, MarkerSubrange::GrammarError },
+        MarkerSubrange { 34, 44, MarkerSubrange::SpellingError },
+        MarkerSubrange { 44, 46, MarkerSubrange::GrammarError },
+        MarkerSubrange { 46, 50, MarkerSubrange::SpellingError },
+        MarkerSubrange { 51, 58, MarkerSubrange::SpellingError },
+        MarkerSubrange { 59, 63, MarkerSubrange::GrammarError },
+    };
+    auto results = subdivide(subranges, OverlapStrategy::Frontmost);
+    ASSERT_EQ(expectedSubranges.size(), results.size());
+    for (size_t i = 0; i < expectedSubranges.size(); ++i)
+        EXPECT_EQ(expectedSubranges[i], results[i]);
+}
+
+}