b71f917cf602d0e00c0ffa38d5809db1aa14f582
[WebKit-https.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/Function.h>
30 #include <wtf/GetPtr.h>
31 #include <wtf/Hasher.h>
32 #include <wtf/NeverDestroyed.h>
33 #include <wtf/Optional.h>
34 #include <wtf/Vector.h>
35
36 namespace WebCore {
37
38 // Unclamped, unchecked, signed fixed-point number representing a value used for font variations.
39 // Sixteen bits in total, one sign bit, two fractional bits, means the smallest positive representable value is 0.25,
40 // the maximum representable value is 8191.75, and the minimum representable value is -8192.
41 class FontSelectionValue {
42 public:
43     typedef int16_t BackingType;
44
45     FontSelectionValue() = default;
46
47     // Explicit because it is lossy.
48     explicit FontSelectionValue(int x)
49         : m_backing(x * fractionalEntropy)
50     {
51     }
52
53     // Explicit because it is lossy.
54     explicit FontSelectionValue(float x)
55         : m_backing(x * fractionalEntropy)
56     {
57     }
58
59     operator float() const
60     {
61         // floats have 23 fractional bits, but only 14 fractional bits are necessary, so every value can be represented losslessly.
62         return m_backing / static_cast<float>(fractionalEntropy);
63     }
64
65     FontSelectionValue operator+(const FontSelectionValue other) const;
66     FontSelectionValue operator-(const FontSelectionValue other) const;
67     FontSelectionValue operator*(const FontSelectionValue other) const;
68     FontSelectionValue operator/(const FontSelectionValue other) const;
69     FontSelectionValue operator-() const;
70     bool operator==(const FontSelectionValue other) const;
71     bool operator!=(const FontSelectionValue other) const;
72     bool operator<(const FontSelectionValue other) const;
73     bool operator<=(const FontSelectionValue other) const;
74     bool operator>(const FontSelectionValue other) const;
75     bool operator>=(const FontSelectionValue other) const;
76
77     BackingType rawValue() const
78     {
79         return m_backing;
80     }
81
82     static FontSelectionValue maximumValue()
83     {
84         static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(std::numeric_limits<BackingType>::max(), RawTag::RawTag);
85         return result.get();
86     }
87
88     static FontSelectionValue minimumValue()
89     {
90         static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(std::numeric_limits<BackingType>::min(), RawTag::RawTag);
91         return result.get();
92     }
93
94     static FontSelectionValue clampFloat(float value)
95     {
96         if (value < static_cast<float>(FontSelectionValue::minimumValue()))
97             return FontSelectionValue::minimumValue();
98         if (value > static_cast<float>(FontSelectionValue::maximumValue()))
99             return FontSelectionValue::maximumValue();
100         return FontSelectionValue(value);
101     }
102
103 private:
104     enum class RawTag { RawTag };
105
106     FontSelectionValue(BackingType rawValue, RawTag)
107         : m_backing(rawValue)
108     {
109     }
110
111     static constexpr int fractionalEntropy = 4;
112     BackingType m_backing { 0 };
113 };
114
115 inline FontSelectionValue FontSelectionValue::operator+(const FontSelectionValue other) const
116 {
117     return FontSelectionValue(m_backing + other.m_backing, RawTag::RawTag);
118 }
119
120 inline FontSelectionValue FontSelectionValue::operator-(const FontSelectionValue other) const
121 {
122     return FontSelectionValue(m_backing - other.m_backing, RawTag::RawTag);
123 }
124
125 inline FontSelectionValue FontSelectionValue::operator*(const FontSelectionValue other) const
126 {
127     return FontSelectionValue(static_cast<int32_t>(m_backing) * other.m_backing / fractionalEntropy, RawTag::RawTag);
128 }
129
130 inline FontSelectionValue FontSelectionValue::operator/(const FontSelectionValue other) const
131 {
132     return FontSelectionValue(static_cast<int32_t>(m_backing) / other.m_backing * fractionalEntropy, RawTag::RawTag);
133 }
134
135 inline FontSelectionValue FontSelectionValue::operator-() const
136 {
137     return FontSelectionValue(-m_backing, RawTag::RawTag);
138 }
139
140 inline bool FontSelectionValue::operator==(const FontSelectionValue other) const
141 {
142     return m_backing == other.m_backing;
143 }
144
145 inline bool FontSelectionValue::operator!=(const FontSelectionValue other) const
146 {
147     return !operator==(other);
148 }
149
150 inline bool FontSelectionValue::operator<(const FontSelectionValue other) const
151 {
152     return m_backing < other.m_backing;
153 }
154
155 inline bool FontSelectionValue::operator<=(const FontSelectionValue other) const
156 {
157     return m_backing <= other.m_backing;
158 }
159
160 inline bool FontSelectionValue::operator>(const FontSelectionValue other) const
161 {
162     return m_backing > other.m_backing;
163 }
164
165 inline bool FontSelectionValue::operator>=(const FontSelectionValue other) const
166 {
167     return m_backing >= other.m_backing;
168 }
169
170 static inline FontSelectionValue italicThreshold()
171 {
172     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(20);
173     return result.get();
174 }
175
176 static inline bool isItalic(FontSelectionValue fontWeight)
177 {
178     return fontWeight >= italicThreshold();
179 }
180
181 static inline FontSelectionValue normalItalicValue()
182 {
183     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue();
184     return result.get();
185 }
186
187 static inline FontSelectionValue italicValue()
188 {
189     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(20);
190     return result.get();
191 }
192
193 static inline FontSelectionValue boldThreshold()
194 {
195     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(600);
196     return result.get();
197 }
198
199 static inline FontSelectionValue boldWeightValue()
200 {
201     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(700);
202     return result.get();
203 }
204
205 static inline FontSelectionValue normalWeightValue()
206 {
207     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(400);
208     return result.get();
209 }
210
211 static inline FontSelectionValue lightWeightValue()
212 {
213     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(200);
214     return result.get();
215 }
216
217 static inline bool isFontWeightBold(FontSelectionValue fontWeight)
218 {
219     return fontWeight >= boldThreshold();
220 }
221
222 static inline FontSelectionValue lowerWeightSearchThreshold()
223 {
224     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(400);
225     return result.get();
226 }
227
228 static inline FontSelectionValue upperWeightSearchThreshold()
229 {
230     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(500);
231     return result.get();
232 }
233
234 static inline FontSelectionValue ultraCondensedStretchValue()
235 {
236     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(50);
237     return result.get();
238 }
239
240 static inline FontSelectionValue extraCondensedStretchValue()
241 {
242     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(62.5f);
243     return result.get();
244 }
245
246 static inline FontSelectionValue condensedStretchValue()
247 {
248     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(75);
249     return result.get();
250 }
251
252 static inline FontSelectionValue semiCondensedStretchValue()
253 {
254     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(87.5f);
255     return result.get();
256 }
257
258 static inline FontSelectionValue normalStretchValue()
259 {
260     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(100);
261     return result.get();
262 }
263
264 static inline FontSelectionValue semiExpandedStretchValue()
265 {
266     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(112.5f);
267     return result.get();
268 }
269
270 static inline FontSelectionValue expandedStretchValue()
271 {
272     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(125);
273     return result.get();
274 }
275
276 static inline FontSelectionValue extraExpandedStretchValue()
277 {
278     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(150);
279     return result.get();
280 }
281
282 static inline FontSelectionValue ultraExpandedStretchValue()
283 {
284     static NeverDestroyed<FontSelectionValue> result = FontSelectionValue(200);
285     return result.get();
286 }
287
288 // [Inclusive, Inclusive]
289 struct FontSelectionRange {
290     FontSelectionRange(FontSelectionValue minimum, FontSelectionValue maximum)
291         : minimum(minimum)
292         , maximum(maximum)
293     {
294     }
295
296     bool operator==(const FontSelectionRange& other) const
297     {
298         return minimum == other.minimum
299             && maximum == other.maximum;
300     }
301
302     bool isValid() const
303     {
304         return minimum <= maximum;
305     }
306
307     void expand(const FontSelectionRange& other)
308     {
309         ASSERT(other.isValid());
310         if (!isValid())
311             *this = other;
312         else {
313             minimum = std::min(minimum, other.minimum);
314             maximum = std::max(maximum, other.maximum);
315         }
316         ASSERT(isValid());
317     }
318
319     bool includes(FontSelectionValue target) const
320     {
321         return target >= minimum && target <= maximum;
322     }
323
324     uint32_t uniqueValue() const
325     {
326         return minimum.rawValue() << 16 | maximum.rawValue();
327     }
328
329     FontSelectionValue minimum { FontSelectionValue(1) };
330     FontSelectionValue maximum { FontSelectionValue(0) };
331 };
332
333 struct FontSelectionRequest {
334     FontSelectionRequest() = default;
335
336     FontSelectionRequest(FontSelectionValue weight, FontSelectionValue width, FontSelectionValue slope)
337         : weight(weight)
338         , width(width)
339         , slope(slope)
340     {
341     }
342
343     bool operator==(const FontSelectionRequest& other) const
344     {
345         return weight == other.weight
346             && width == other.width
347             && slope == other.slope;
348     }
349
350     bool operator!=(const FontSelectionRequest& other) const
351     {
352         return !operator==(other);
353     }
354
355     FontSelectionValue weight;
356     FontSelectionValue width;
357     FontSelectionValue slope;
358 };
359
360 // Only used for HashMaps. We don't want to put the bool into FontSelectionRequest
361 // because FontSelectionRequest needs to be as small as possible because it's inside
362 // every FontDescription.
363 struct FontSelectionRequestKey {
364     FontSelectionRequestKey() = default;
365
366     FontSelectionRequestKey(FontSelectionRequest request)
367         : request(request)
368     {
369     }
370
371     explicit FontSelectionRequestKey(WTF::HashTableDeletedValueType)
372         : isDeletedValue(true)
373     {
374     }
375
376     bool isHashTableDeletedValue() const
377     {
378         return isDeletedValue;
379     }
380
381     bool operator==(const FontSelectionRequestKey& other) const
382     {
383         return request == other.request
384             && isDeletedValue == other.isDeletedValue;
385     }
386
387     FontSelectionRequest request;
388     bool isDeletedValue { false };
389 };
390
391 struct FontSelectionRequestKeyHash {
392     static unsigned hash(const FontSelectionRequestKey& key)
393     {
394         IntegerHasher hasher;
395         hasher.add(key.request.weight.rawValue());
396         hasher.add(key.request.width.rawValue());
397         hasher.add(key.request.slope.rawValue());
398         hasher.add(key.isDeletedValue);
399         return hasher.hash();
400     }
401
402     static bool equal(const FontSelectionRequestKey& a, const FontSelectionRequestKey& b)
403     {
404         return a == b;
405     }
406
407     static const bool safeToCompareToEmptyOrDeleted = true;
408 };
409
410 struct FontSelectionCapabilities {
411     FontSelectionCapabilities()
412     {
413     }
414
415     FontSelectionCapabilities(FontSelectionRange weight, FontSelectionRange width, FontSelectionRange slope)
416         : weight(weight)
417         , width(width)
418         , slope(slope)
419     {
420     }
421
422     void expand(const FontSelectionCapabilities& capabilities)
423     {
424         weight.expand(capabilities.weight);
425         width.expand(capabilities.width);
426         slope.expand(capabilities.slope);
427     }
428
429     bool operator==(const FontSelectionCapabilities& other) const
430     {
431         return weight == other.weight
432             && width == other.width
433             && slope == other.slope;
434     }
435
436     bool operator!=(const FontSelectionCapabilities& other) const
437     {
438         return !(*this == other);
439     }
440
441     FontSelectionRange weight { normalWeightValue(), normalWeightValue() };
442     FontSelectionRange width { normalStretchValue(), normalStretchValue() };
443     FontSelectionRange slope { normalItalicValue(), normalItalicValue() };
444 };
445
446 struct FontSelectionSpecifiedCapabilities {
447     FontSelectionCapabilities computeFontSelectionCapabilities() const
448     {
449         return FontSelectionCapabilities(computeWeight(), computeWidth(), computeSlope());
450     }
451
452     bool operator==(const FontSelectionSpecifiedCapabilities& other) const
453     {
454         return weight == other.weight
455             && width == other.width
456             && slope == other.slope;
457     }
458
459     bool operator!=(const FontSelectionSpecifiedCapabilities& other) const
460     {
461         return !(*this == other);
462     }
463
464     FontSelectionSpecifiedCapabilities& operator=(const FontSelectionCapabilities& other)
465     {
466         weight = other.weight;
467         width = other.width;
468         slope = other.slope;
469         return *this;
470     }
471
472     FontSelectionRange computeWeight() const
473     {
474         return weight.value_or(FontSelectionRange({ normalWeightValue(), normalWeightValue() }));
475     }
476
477     FontSelectionRange computeWidth() const
478     {
479         return width.value_or(FontSelectionRange({ normalStretchValue(), normalStretchValue() }));
480     }
481
482     FontSelectionRange computeSlope() const
483     {
484         return slope.value_or(FontSelectionRange({ normalItalicValue(), normalItalicValue() }));
485     }
486
487     std::optional<FontSelectionRange> weight;
488     std::optional<FontSelectionRange> width;
489     std::optional<FontSelectionRange> slope;
490 };
491
492 class FontSelectionAlgorithm {
493 public:
494     FontSelectionAlgorithm() = delete;
495
496     FontSelectionAlgorithm(FontSelectionRequest request, const Vector<FontSelectionCapabilities>& capabilities, std::optional<FontSelectionCapabilities> capabilitiesBounds = std::nullopt)
497         : m_request(request)
498         , m_capabilities(capabilities)
499         , m_filter(new bool[m_capabilities.size()])
500     {
501         ASSERT(!m_capabilities.isEmpty());
502         if (capabilitiesBounds)
503             m_capabilitiesBounds = capabilitiesBounds.value();
504         else {
505             for (auto capabilities : m_capabilities)
506                 m_capabilitiesBounds.expand(capabilities);
507         }
508         for (size_t i = 0; i < m_capabilities.size(); ++i)
509             m_filter[i] = true;
510     }
511
512     struct DistanceResult {
513         FontSelectionValue distance;
514         FontSelectionValue value;
515     };
516
517     DistanceResult stretchDistance(FontSelectionCapabilities) const;
518     DistanceResult styleDistance(FontSelectionCapabilities) const;
519     DistanceResult weightDistance(FontSelectionCapabilities) const;
520
521     size_t indexOfBestCapabilities();
522
523 private:
524     template <typename T>
525     using IterateActiveCapabilitiesWithReturnCallback = WTF::Function<std::optional<T>(FontSelectionCapabilities, size_t)>;
526
527     template <typename T>
528     inline std::optional<T> iterateActiveCapabilitiesWithReturn(const IterateActiveCapabilitiesWithReturnCallback<T>& callback)
529     {
530         for (size_t i = 0; i < m_capabilities.size(); ++i) {
531             if (!m_filter[i])
532                 continue;
533             if (auto result = callback(m_capabilities[i], i))
534                 return result;
535         }
536         return std::nullopt;
537     }
538
539     template <typename T>
540     inline void iterateActiveCapabilities(T callback)
541     {
542         iterateActiveCapabilitiesWithReturn<int>([&](FontSelectionCapabilities capabilities, size_t i) -> std::optional<int> {
543             callback(capabilities, i);
544             return std::nullopt;
545         });
546     }
547
548     void filterCapability(DistanceResult(FontSelectionAlgorithm::*computeDistance)(FontSelectionCapabilities) const, FontSelectionRange FontSelectionCapabilities::*inclusionRange);
549
550     FontSelectionRequest m_request;
551     FontSelectionCapabilities m_capabilitiesBounds;
552     const Vector<FontSelectionCapabilities>& m_capabilities;
553     std::unique_ptr<bool[]> m_filter;
554 };
555
556 }