8d6afb1f64625d4b1d479219d687b2b23ca303c7
[WebKit.git] / Source / WebCore / platform / graphics / FontSelectionAlgorithm.h
1 /*
2  * Copyright (C) 2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #pragma once
27
28 #include "TextFlags.h"
29 #include <wtf/GetPtr.h>
30 #include <wtf/Hasher.h>
31 #include <wtf/NeverDestroyed.h>
32 #include <wtf/Optional.h>
33 #include <wtf/Vector.h>
34
35 namespace WebCore {
36
37 // Unclamped, unchecked, signed fixed-point number representing a value used for font variations.
38 // Sixteen bits in total, one sign bit, two fractional bits, means the smallest positive representable value is 0.25,
39 // the maximum representable value is 8191.75, and the minimum representable value is -8192.
40 class FontSelectionValue {
41 public:
42     FontSelectionValue() = default;
43
44     // Explicit because it is lossy.
45     explicit FontSelectionValue(int x)
46         : m_backing(x * fractionalEntropy)
47     {
48     }
49
50     // Explicit because it is lossy.
51     explicit FontSelectionValue(float x)
52         : m_backing(x * fractionalEntropy)
53     {
54     }
55
56     operator float() const
57     {
58         // floats have 23 fractional bits, but only 14 fractional bits are necessary, so every value can be represented losslessly.
59         return m_backing / static_cast<float>(fractionalEntropy);
60     }
61
62     FontSelectionValue operator+(const FontSelectionValue other) const;
63     FontSelectionValue operator-(const FontSelectionValue other) const;
64     FontSelectionValue operator*(const FontSelectionValue other) const;
65     FontSelectionValue operator/(const FontSelectionValue other) const;
66     FontSelectionValue operator-() const;
67     bool operator==(const FontSelectionValue other) const;
68     bool operator!=(const FontSelectionValue other) const;
69     bool operator<(const FontSelectionValue other) const;
70     bool operator<=(const FontSelectionValue other) const;
71     bool operator>(const FontSelectionValue other) const;
72     bool operator>=(const FontSelectionValue other) const;
73
74     int16_t rawValue() const
75     {
76         return m_backing;
77     }
78
79     static FontSelectionValue maximumValue()
80     {
81         static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(std::numeric_limits<int16_t>::max(), RawTag::RawTag);
82         return result.get();
83     }
84
85     static FontSelectionValue minimumValue()
86     {
87         static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(std::numeric_limits<int16_t>::min(), RawTag::RawTag);
88         return result.get();
89     }
90
91 private:
92     enum class RawTag { RawTag };
93
94     FontSelectionValue(int16_t rawValue, RawTag)
95         : m_backing(rawValue)
96     {
97     }
98
99     static constexpr int fractionalEntropy = 4;
100     int16_t m_backing { 0 };
101 };
102
103 inline FontSelectionValue FontSelectionValue::operator+(const FontSelectionValue other) const
104 {
105     return FontSelectionValue(m_backing + other.m_backing, RawTag::RawTag);
106 }
107
108 inline FontSelectionValue FontSelectionValue::operator-(const FontSelectionValue other) const
109 {
110     return FontSelectionValue(m_backing - other.m_backing, RawTag::RawTag);
111 }
112
113 inline FontSelectionValue FontSelectionValue::operator*(const FontSelectionValue other) const
114 {
115     return FontSelectionValue(static_cast<int32_t>(m_backing) * other.m_backing / fractionalEntropy, RawTag::RawTag);
116 }
117
118 inline FontSelectionValue FontSelectionValue::operator/(const FontSelectionValue other) const
119 {
120     return FontSelectionValue(static_cast<int32_t>(m_backing) / other.m_backing * fractionalEntropy, RawTag::RawTag);
121 }
122
123 inline FontSelectionValue FontSelectionValue::operator-() const
124 {
125     return FontSelectionValue(-m_backing, RawTag::RawTag);
126 }
127
128 inline bool FontSelectionValue::operator==(const FontSelectionValue other) const
129 {
130     return m_backing == other.m_backing;
131 }
132
133 inline bool FontSelectionValue::operator!=(const FontSelectionValue other) const
134 {
135     return !operator==(other);
136 }
137
138 inline bool FontSelectionValue::operator<(const FontSelectionValue other) const
139 {
140     return m_backing < other.m_backing;
141 }
142
143 inline bool FontSelectionValue::operator<=(const FontSelectionValue other) const
144 {
145     return m_backing <= other.m_backing;
146 }
147
148 inline bool FontSelectionValue::operator>(const FontSelectionValue other) const
149 {
150     return m_backing > other.m_backing;
151 }
152
153 inline bool FontSelectionValue::operator>=(const FontSelectionValue other) const
154 {
155     return m_backing >= other.m_backing;
156 }
157
158 static inline FontSelectionValue italicThreshold()
159 {
160     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(20);
161     return result.get();
162 }
163
164 static inline FontSelectionValue boldThreshold()
165 {
166     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(600);
167     return result.get();
168 }
169
170 static inline FontSelectionValue weightSearchThreshold()
171 {
172     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(500);
173     return result.get();
174 }
175
176 // [Inclusive, Inclusive]
177 struct FontSelectionRange {
178     FontSelectionRange(FontSelectionValue minimum, FontSelectionValue maximum)
179         : minimum(minimum)
180         , maximum(maximum)
181     {
182     }
183
184     bool operator==(const FontSelectionRange& other) const
185     {
186         return minimum == other.minimum
187             && maximum == other.maximum;
188     }
189
190     bool isValid() const
191     {
192         return minimum <= maximum;
193     }
194
195     void expand(const FontSelectionRange& other)
196     {
197         ASSERT(other.isValid());
198         if (!isValid())
199             *this = other;
200         else {
201             minimum = std::min(minimum, other.minimum);
202             maximum = std::max(maximum, other.maximum);
203         }
204         ASSERT(isValid());
205     }
206
207     bool includes(FontSelectionValue target) const
208     {
209         return target >= minimum && target <= maximum;
210     }
211
212     FontSelectionValue minimum { FontSelectionValue(1) };
213     FontSelectionValue maximum { FontSelectionValue(0) };
214 };
215
216 struct FontSelectionRequest {
217     bool operator==(const FontSelectionRequest& other) const
218     {
219         return weight == other.weight
220             && width == other.width
221             && slope == other.slope;
222     }
223
224     bool operator!=(const FontSelectionRequest& other) const
225     {
226         return !operator==(other);
227     }
228
229     FontSelectionValue weight;
230     FontSelectionValue width;
231     FontSelectionValue slope;
232 };
233
234 // Only used for HashMaps. We don't want to put the bool into FontSelectionRequest
235 // because FontSelectionRequest needs to be as small as possible because it's inside
236 // every FontDescription.
237 struct FontSelectionRequestKey {
238     FontSelectionRequestKey() = default;
239
240     FontSelectionRequestKey(FontSelectionRequest request)
241         : request(request)
242     {
243     }
244
245     explicit FontSelectionRequestKey(WTF::HashTableDeletedValueType)
246         : isDeletedValue(true)
247     {
248     }
249
250     bool isHashTableDeletedValue() const
251     {
252         return isDeletedValue;
253     }
254
255     bool operator==(const FontSelectionRequestKey& other) const
256     {
257         return request == other.request
258             && isDeletedValue == other.isDeletedValue;
259     }
260
261     FontSelectionRequest request;
262     bool isDeletedValue { false };
263 };
264
265 struct FontSelectionRequestKeyHash {
266     static unsigned hash(const FontSelectionRequestKey& key)
267     {
268         IntegerHasher hasher;
269         hasher.add(key.request.weight.rawValue());
270         hasher.add(key.request.width.rawValue());
271         hasher.add(key.request.slope.rawValue());
272         hasher.add(key.isDeletedValue);
273         return hasher.hash();
274     }
275
276     static bool equal(const FontSelectionRequestKey& a, const FontSelectionRequestKey& b)
277     {
278         return a == b;
279     }
280
281     static const bool safeToCompareToEmptyOrDeleted = true;
282 };
283
284 struct FontSelectionCapabilities {
285     void expand(const FontSelectionCapabilities& capabilities)
286     {
287         weight.expand(capabilities.weight);
288         width.expand(capabilities.width);
289         slope.expand(capabilities.slope);
290     }
291
292     FontSelectionRange weight { FontSelectionValue(400), FontSelectionValue(400) };
293     FontSelectionRange width { FontSelectionValue(100), FontSelectionValue(100) };
294     FontSelectionRange slope { FontSelectionValue(), FontSelectionValue() };
295 };
296
297 class FontSelectionAlgorithm {
298 public:
299     FontSelectionAlgorithm() = delete;
300
301     FontSelectionAlgorithm(FontSelectionRequest request, const Vector<FontSelectionCapabilities>& capabilities, std::optional<FontSelectionCapabilities> capabilitiesBounds = std::nullopt)
302         : m_request(request)
303         , m_capabilities(capabilities)
304         , m_filter(new bool[m_capabilities.size()])
305     {
306         ASSERT(!m_capabilities.isEmpty());
307         if (capabilitiesBounds)
308             m_capabilitiesBounds = capabilitiesBounds.value();
309         else {
310             for (auto capabilities : m_capabilities)
311                 m_capabilitiesBounds.expand(capabilities);
312         }
313         for (size_t i = 0; i < m_capabilities.size(); ++i)
314             m_filter[i] = true;
315     }
316
317     struct DistanceResult {
318         FontSelectionValue distance;
319         FontSelectionValue value;
320     };
321
322     DistanceResult stretchDistance(FontSelectionCapabilities) const;
323     DistanceResult styleDistance(FontSelectionCapabilities) const;
324     DistanceResult weightDistance(FontSelectionCapabilities) const;
325
326     size_t indexOfBestCapabilities();
327
328 private:
329     template <typename T>
330     using IterateActiveCapabilitiesWithReturnCallback = std::function<std::optional<T>(FontSelectionCapabilities, size_t)>;
331
332     template <typename T>
333     inline std::optional<T> iterateActiveCapabilitiesWithReturn(IterateActiveCapabilitiesWithReturnCallback<T> callback)
334     {
335         for (size_t i = 0; i < m_capabilities.size(); ++i) {
336             if (!m_filter[i])
337                 continue;
338             if (auto result = callback(m_capabilities[i], i))
339                 return result;
340         }
341         return std::nullopt;
342     }
343
344     template <typename T>
345     inline void iterateActiveCapabilities(T callback)
346     {
347         iterateActiveCapabilitiesWithReturn<int>([&](FontSelectionCapabilities capabilities, size_t i) -> std::optional<int> {
348             callback(capabilities, i);
349             return std::nullopt;
350         });
351     }
352
353     void filterCapability(DistanceResult(FontSelectionAlgorithm::*computeDistance)(FontSelectionCapabilities) const, FontSelectionRange FontSelectionCapabilities::*inclusionRange);
354
355     FontSelectionRequest m_request;
356     FontSelectionCapabilities m_capabilitiesBounds;
357     const Vector<FontSelectionCapabilities>& m_capabilities;
358     std::unique_ptr<bool[]> m_filter;
359 };
360
361 FontSelectionRequest fontSelectionRequestForTraitsMask(FontTraitsMask, FontSelectionValue stretch);
362 FontSelectionCapabilities fontSelectionCapabilitiesForTraitsMask(FontTraitsMask, FontSelectionValue stretch);
363 FontSelectionCapabilities fontSelectionCapabilitiesForTraitsMask(FontTraitsMask, FontSelectionRange stretch);
364
365 }