Optimize Font CodePath selection and more unit testing.

Source/core/platform/graphics/Font.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2000 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2003, 2006, 2010, 2011 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
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
@@ skipping 10 matching lines @@
  *
  */
 
 #include "config.h"
 #include "core/platform/graphics/Font.h"
 
 #include "core/platform/graphics/FloatRect.h"
 #include "core/platform/graphics/TextRun.h"
 #include "core/platform/graphics/WidthIterator.h"
 #include "core/platform/text/transcoder/FontTranscoder.h"
-#include <wtf/MainThread.h>
-#include <wtf/MathExtras.h>
-#include <wtf/text/StringBuilder.h>
-#include <wtf/UnusedParam.h>
+#include "wtf/MainThread.h"
+#include "wtf/MathExtras.h"
+#include "wtf/StdLibExtras.h"
+#include "wtf/UnusedParam.h"
+#include "wtf/text/StringBuilder.h"
 
 using namespace WTF;
 using namespace Unicode;
 
 namespace WTF {
 
 // allow compilation of OwnPtr<TextLayout> in source files that don't have access to the TextLayout class definition
 template <> void deleteOwnedPtr<WebCore::TextLayout>(WebCore::TextLayout* ptr)
 {
     WebCore::Font::deleteLayout(ptr);
@@ skipping 301 matching lines @@
     if (!run.characterScanForCodePath())
         return Simple;
 
     if (run.is8Bit())
         return Simple;
 
     // Start from 0 since drawing and highlighting also measure the characters before run->from.
     return characterRangeCodePath(run.characters16(), run.length());
 }
 
+static inline UChar keyExtractor(const UChar* value)
+{
+    return *value;
+}
+
 Font::CodePath Font::characterRangeCodePath(const UChar* characters, unsigned len)
 {
-    // FIXME: Should use a UnicodeSet in ports where ICU is used. Note that we 
-    // can't simply use UnicodeCharacter Property/class because some characters
-    // are not 'combining', but still need to go to the complex path.
-    // Alternatively, we may as well consider binary search over a sorted
-    // list of ranges.
+    static UChar complexCodePathRanges[] = {
+        // U+02E5 through U+02E9 (Modifier Letters : Tone letters)
+        0x2E5, 0x2E9,
+        // U+0300 through U+036F Combining diacritical marks
+        0x300, 0x36F,
+        // U+0591 through U+05CF excluding U+05BE Hebrew combining marks, ...
+        0x0591, 0x05BD,
+        // ... Hebrew punctuation Paseq, Sof Pasuq and Nun Hafukha
+        0x05BF, 0x05CF,
+        // U+0600 through U+109F Arabic, Syriac, Thaana, NKo, Samaritan, Mandaic,
+        // Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada,
+        // Malayalam, Sinhala, Thai, Lao, Tibetan, Myanmar
+        0x0600, 0x109F,
+        // U+1100 through U+11FF Hangul Jamo (only Ancient Korean should be left
+        // here if you precompose; Modern Korean will be precomposed as a result of step A)
+        0x1100, 0x11FF,
+        // U+135D through U+135F Ethiopic combining marks
+        0x135D, 0x135F,
+        // U+1780 through U+18AF Tagalog, Hanunoo, Buhid, Taghanwa,Khmer, Mongolian
+        0x1700, 0x18AF,
+        // U+1900 through U+194F Limbu (Unicode 4.0)
+        0x1900, 0x194F,
+        // U+1980 through U+19DF New Tai Lue
+        0x1980, 0x19DF,
+        // U+1A00 through U+1CFF Buginese, Tai Tham, Balinese, Batak, Lepcha, Vedic
+        0x1A00, 0x1CFF,
+        // U+1DC0 through U+1DFF Comining diacritical mark supplement
+        0x1DC0, 0x1DFF,
+        // U+20D0 through U+20FF Combining marks for symbols
+        0x20D0, 0x20FF,
+        // U+2CEF through U+2CF1 Combining marks for Coptic
+        0x2CEF, 0x2CF1,
+        // U+302A through U+302F Ideographic and Hangul Tone marks
+        0x302A, 0x302F,
+        // U+A67C through U+A67D Combining marks for old Cyrillic
+        0xA67C, 0xA67D,
+        // U+A6F0 through U+A6F1 Combining mark for Bamum
+        0xA6F0, 0xA6F1,
+        // U+A800 through U+ABFF Nagri, Phags-pa, Saurashtra, Devanagari Extended,
+        // Hangul Jamo Ext. A, Javanese, Myanmar Extended A, Tai Viet, Meetei Mayek
+        0xA800, 0xABFF,
+        // U+D7B0 through U+D7FF Hangul Jamo Ext. B
+        0xD7B0, 0xD7FF,
+        // U+FE00 through U+FE0F Unicode variation selectors
+        0xFE00, 0xFE0F,
+        // U+FE20 through U+FE2F Combining half marks
+        0xFE20, 0xFE2F,
+    };
+    static size_t complexCodePathRangesCount = WTF_ARRAY_LENGTH(complexCodePathRanges);
+
     CodePath result = Simple;
     for (unsigned i = 0; i < len; i++) {
         const UChar c = characters[i];
-        if (c < 0x2E5) // U+02E5 through U+02E9 (Modifier Letters : Tone letters)  
+
+        // Shortcut for common case
+        if (c < 0x2E5)
             continue;
-        if (c <= 0x2E9) 
-            return Complex;
-
-        if (c < 0x300) // U+0300 through U+036F Combining diacritical marks
-            continue;
-        if (c <= 0x36F)
-            return Complex;
-
-        if (c < 0x0591 || c == 0x05BE) // U+0591 through U+05CF excluding U+05BE Hebrew combining marks, Hebrew punctuation Paseq, Sof Pasuq and Nun Hafukha
-            continue;
-        if (c <= 0x05CF)
-            return Complex;
-
-        // U+0600 through U+109F Arabic, Syriac, Thaana, NKo, Samaritan, Mandaic,
-        // Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, 
-        // Malayalam, Sinhala, Thai, Lao, Tibetan, Myanmar
-        if (c < 0x0600) 
-            continue;
-        if (c <= 0x109F)
-            return Complex;
-
-        // U+1100 through U+11FF Hangul Jamo (only Ancient Korean should be left here if you precompose;
-        // Modern Korean will be precomposed as a result of step A)
-        if (c < 0x1100)
-            continue;
-        if (c <= 0x11FF)
-            return Complex;
-
-        if (c < 0x135D) // U+135D through U+135F Ethiopic combining marks
-            continue;
-        if (c <= 0x135F)
-            return Complex;
-
-        if (c < 0x1700) // U+1780 through U+18AF Tagalog, Hanunoo, Buhid, Taghanwa,Khmer, Mongolian
-            continue;
-        if (c <= 0x18AF)
-            return Complex;
-
-        if (c < 0x1900) // U+1900 through U+194F Limbu (Unicode 4.0)
-            continue;
-        if (c <= 0x194F)
-            return Complex;
-
-        if (c < 0x1980) // U+1980 through U+19DF New Tai Lue
-            continue;
-        if (c <= 0x19DF)
-            return Complex;
-
-        if (c < 0x1A00) // U+1A00 through U+1CFF Buginese, Tai Tham, Balinese, Batak, Lepcha, Vedic
-            continue;
-        if (c <= 0x1CFF)
-            return Complex;
-
-        if (c < 0x1DC0) // U+1DC0 through U+1DFF Comining diacritical mark supplement
-            continue;
-        if (c <= 0x1DFF)
-            return Complex;
 
         // U+1E00 through U+2000 characters with diacritics and stacked diacritics
-        if (c <= 0x2000) {
+        if (c >= 0x1E00 && c <= 0x2000) {
             result = SimpleWithGlyphOverflow;
             continue;
         }
 
-        if (c < 0x20D0) // U+20D0 through U+20FF Combining marks for symbols
-            continue;
-        if (c <= 0x20FF)
-            return Complex;
-
-        if (c < 0x2CEF) // U+2CEF through U+2CF1 Combining marks for Coptic
-            continue;
-        if (c <= 0x2CF1)
-            return Complex;
-
-        if (c < 0x302A) // U+302A through U+302F Ideographic and Hangul Tone marks
-            continue;
-        if (c <= 0x302F)
-            return Complex;
-
-        if (c < 0xA67C) // U+A67C through U+A67D Combining marks for old Cyrillic
-            continue;
-        if (c <= 0xA67D)
-            return Complex;
-
-        if (c < 0xA6F0) // U+A6F0 through U+A6F1 Combining mark for Bamum
-            continue;
-        if (c <= 0xA6F1)
-            return Complex;
-
-       // U+A800 through U+ABFF Nagri, Phags-pa, Saurashtra, Devanagari Extended,
-       // Hangul Jamo Ext. A, Javanese, Myanmar Extended A, Tai Viet, Meetei Mayek,
-        if (c < 0xA800) 
-            continue;
-        if (c <= 0xABFF)
-            return Complex;
-
-        if (c < 0xD7B0) // U+D7B0 through U+D7FF Hangul Jamo Ext. B
-            continue;
-        if (c <= 0xD7FF)
-            return Complex;
-
-        if (c <= 0xDBFF) {
-            // High surrogate
-
+        // Surrogate pairs
+        if (c > 0xD7FF && c <= 0xDBFF) {
             if (i == len - 1)
                 continue;
 
             UChar next = characters[++i];
             if (!U16_IS_TRAIL(next))
                 continue;
 
             UChar32 supplementaryCharacter = U16_GET_SUPPLEMENTARY(c, next);
 
             if (supplementaryCharacter < 0x1F1E6) // U+1F1E6 through U+1F1FF Regional Indicator Symbols
                 continue;
             if (supplementaryCharacter <= 0x1F1FF)
                 return Complex;
 
             if (supplementaryCharacter < 0xE0100) // U+E0100 through U+E01EF Unicode variation selectors.
                 continue;
             if (supplementaryCharacter <= 0xE01EF)
                 return Complex;
 
             // FIXME: Check for Brahmi (U+11000 block), Kaithi (U+11080 block) and other complex scripts
             // in plane 1 or higher.
 
             continue;
         }
 
-        if (c < 0xFE00) // U+FE00 through U+FE0F Unicode variation selectors
+        // Search for other Complex cases
+        UChar* boundingCharacter = approximateBinarySearch<UChar, UChar>(
+            (UChar*)complexCodePathRanges, complexCodePathRangesCount, c, keyExtractor);
+        // Exact matches are complex
+        if (*boundingCharacter == c)
+            return Complex;
+        bool isEndOfRange = ((boundingCharacter - complexCodePathRanges) % 2);
+        if (*boundingCharacter < c) {
+            // Determine if we are in a range or out
+            if (!isEndOfRange)
+                return Complex;
             continue;
-        if (c <= 0xFE0F)
-            return Complex;
-
-        if (c < 0xFE20) // U+FE20 through U+FE2F Combining half marks
-            continue;
-        if (c <= 0xFE2F)
+        }
+        ASSERT(*boundingCharacter > c);
+        // Determine if we are in a range or out - opposite condition to above
+        if (isEndOfRange)
             return Complex;
     }
+
     return result;
 }
 
 bool Font::isCJKIdeograph(UChar32 c)
 {
     // The basic CJK Unified Ideographs block.
     if (c >= 0x4E00 && c <= 0x9FFF)
         return true;
     
     // CJK Unified Ideographs Extension A.
     if (c >= 0x3400 && c <= 0x4DBF)
         return true;
     
-    // CJK Radicals Supplement.
-    if (c >= 0x2E80 && c <= 0x2EFF)
-        return true;
-    
-    // Kangxi Radicals.
-    if (c >= 0x2F00 && c <= 0x2FDF)
+    // CJK Radicals Supplement and Kangxi Radicals.
+    if (c >= 0x2E80 && c <= 0x2FDF)
         return true;
     
     // CJK Strokes.
     if (c >= 0x31C0 && c <= 0x31EF)
         return true;
     
     // CJK Compatibility Ideographs.
     if (c >= 0xF900 && c <= 0xFAFF)
         return true;
     
@@ skipping 34 matching lines @@
 
     if (c >= 0x2156 && c <= 0x215A)
         return true;
 
     if (c >= 0x2160 && c <= 0x216B)
         return true;
 
     if (c >= 0x2170 && c <= 0x217B)
         return true;
 
-    if ((c == 0x217F) || (c == 0x2189) || (c == 0x2307) || (c == 0x2312) || (c == 0x23BE) || (c == 0x23BF))
+    if ((c == 0x217F) || (c == 0x2189) || (c == 0x2307) || (c == 0x2312))
         return true;
 
-    if (c >= 0x23C0 && c <= 0x23CC)
+    if (c >= 0x23BE && c <= 0x23CC)
         return true;
 
     if ((c == 0x23CE) || (c == 0x2423))
         return true;
 
     if (c >= 0x2460 && c <= 0x2492)
         return true;
 
     if (c >= 0x249C && c <= 0x24FF)
         return true;
@@ skipping 30 matching lines @@
 
     if ((c == 0x26A0) || (c == 0x26BD) || (c == 0x26BE) || (c == 0x2713) || (c == 0x271A) || (c == 0x273F) || (c == 0x2740) || (c == 0x2756))
         return true;
 
     if (c >= 0x2776 && c <= 0x277F)
         return true;
 
     if (c == 0x2B1A)
         return true;
 
-    // Ideographic Description Characters.
-    if (c >= 0x2FF0 && c <= 0x2FFF)
-        return true;
-    
-    // CJK Symbols and Punctuation, excluding 0x3030.
-    if (c >= 0x3000 && c < 0x3030)
+    // Ideographic Description Characters, with CJK Symbols and Punctuation, excluding 0x3030.
+    // Then Hiragana 0x3040 .. 0x309F, Katakana 0x30A0 .. 0x30FF, Bopomofo 0x3100 .. 0x312F
+    if (c >= 0x2FF0 && c < 0x3030)
         return true;
 
-    if (c > 0x3030 && c <= 0x303F)
+    if (c > 0x3030 && c <= 0x312F)
         return true;
 
-    // Hiragana
-    if (c >= 0x3040 && c <= 0x309F)
-        return true;
-
-    // Katakana 
-    if (c >= 0x30A0 && c <= 0x30FF)
-        return true;
-
-    // Bopomofo
-    if (c >= 0x3100 && c <= 0x312F)
-        return true;
-
-    if (c >= 0x3190 && c <= 0x319F)
-        return true;
-
-    // Bopomofo Extended
-    if (c >= 0x31A0 && c <= 0x31BF)
+    // More Bopomofo and Bopomofo Extended 0x31A0 .. 0x31BF
+    if (c >= 0x3190 && c <= 0x31BF)
         return true;
  
-    // Enclosed CJK Letters and Months.
-    if (c >= 0x3200 && c <= 0x32FF)
-        return true;
-    
-    // CJK Compatibility.
-    if (c >= 0x3300 && c <= 0x33FF)
+    // Enclosed CJK Letters and Months (0x3200 .. 0x32FF).
+    // CJK Compatibility (0x3300 .. 0x33FF).
+    if (c >= 0x3200 && c <= 0x33FF)
         return true;
 
     if (c >= 0xF860 && c <= 0xF862)
         return true;
 
     // CJK Compatibility Forms.
     if (c >= 0xFE30 && c <= 0xFE4F)
         return true;
 
     if ((c == 0xFE10) || (c == 0xFE11) || (c == 0xFE12) || (c == 0xFE19))
@@ skipping 16 matching lines @@
 
     if (c >= 0x1F130 && c <= 0x1F149)
         return true;
 
     if (c >= 0x1F150 && c <= 0x1F169)
         return true;
 
     if (c >= 0x1F170 && c <= 0x1F189)
         return true;
 
-    if (c >= 0x1F200 && c <= 0x1F6F)
+    if (c >= 0x1F200 && c <= 0x1F6FF)
         return true;
 
     return isCJKIdeograph(c);
 }
 
 unsigned Font::expansionOpportunityCount(const LChar* characters, size_t length, TextDirection direction, bool& isAfterExpansion)
 {
     unsigned count = 0;
     if (direction == LTR) {
         for (size_t i = 0; i < length; ++i) {
@@ skipping 73 matching lines @@
 
     // Additional word-separator characters listed in CSS Text Level 3 Editor's Draft 3 November 2010.
     if (c == ethiopicWordspace || c == aegeanWordSeparatorLine || c == aegeanWordSeparatorDot
         || c == ugariticWordDivider || c == tibetanMarkIntersyllabicTsheg || c == tibetanMarkDelimiterTshegBstar)
         return false;
 
     return true;
 }
 
 }