ab47057a14c1779e58fb9720e39ad38a1b74d7ec
[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 <algorithm>
30 #include <tuple>
31 #include <wtf/Hasher.h>
32 #include <wtf/Optional.h>
33 #include <wtf/text/TextStream.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, smallest positive value is 0.25,
39 // maximum value is 8191.75, and minimum value is -8192.
40 class FontSelectionValue {
41 public:
42     using BackingType = int16_t;
43
44     FontSelectionValue() = default;
45
46     // Explicit because it won't work correctly for values outside the representable range.
47     explicit constexpr FontSelectionValue(int);
48
49     // Explicit because it won't work correctly for values outside the representable range and because precision can be lost.
50     explicit constexpr FontSelectionValue(float);
51
52     // Precision can be lost, but value will be clamped to the representable range.
53     static constexpr FontSelectionValue clampFloat(float);
54
55     // Since floats have 23 mantissa bits, every value can be represented losslessly.
56     constexpr operator float() const;
57
58     static constexpr FontSelectionValue maximumValue();
59     static constexpr FontSelectionValue minimumValue();
60
61     friend constexpr FontSelectionValue operator+(FontSelectionValue, FontSelectionValue);
62     friend constexpr FontSelectionValue operator-(FontSelectionValue, FontSelectionValue);
63     friend constexpr FontSelectionValue operator*(FontSelectionValue, FontSelectionValue);
64     friend constexpr FontSelectionValue operator/(FontSelectionValue, FontSelectionValue);
65     friend constexpr FontSelectionValue operator-(FontSelectionValue);
66
67     constexpr BackingType rawValue() const { return m_backing; }
68
69 private:
70     enum class RawTag { RawTag };
71     constexpr FontSelectionValue(int, RawTag);
72
73     static constexpr int fractionalEntropy = 4;
74     BackingType m_backing { 0 };
75 };
76
77 constexpr FontSelectionValue::FontSelectionValue(int x)
78     : m_backing(x * fractionalEntropy)
79 {
80     // FIXME: Should we assert the passed in value was in range?
81 }
82
83 constexpr FontSelectionValue::FontSelectionValue(float x)
84     : m_backing(x * fractionalEntropy)
85 {
86     // FIXME: Should we assert the passed in value was in range?
87 }
88
89 constexpr FontSelectionValue::operator float() const
90 {
91     return m_backing / static_cast<float>(fractionalEntropy);
92 }
93
94 constexpr FontSelectionValue FontSelectionValue::maximumValue()
95 {
96     return { std::numeric_limits<BackingType>::max(), RawTag::RawTag };
97 }
98
99 constexpr FontSelectionValue FontSelectionValue::minimumValue()
100 {
101     return { std::numeric_limits<BackingType>::min(), RawTag::RawTag };
102 }
103
104 constexpr FontSelectionValue FontSelectionValue::clampFloat(float value)
105 {
106     return FontSelectionValue { std::max<float>(minimumValue(), std::min<float>(value, maximumValue())) };
107 }
108
109 constexpr FontSelectionValue::FontSelectionValue(int rawValue, RawTag)
110     : m_backing(rawValue)
111 {
112 }
113
114 constexpr FontSelectionValue operator+(FontSelectionValue a, FontSelectionValue b)
115 {
116     return { a.m_backing + b.m_backing, FontSelectionValue::RawTag::RawTag };
117 }
118
119 constexpr FontSelectionValue operator-(FontSelectionValue a, FontSelectionValue b)
120 {
121     return { a.m_backing - b.m_backing, FontSelectionValue::RawTag::RawTag };
122 }
123
124 constexpr FontSelectionValue operator*(FontSelectionValue a, FontSelectionValue b)
125 {
126     return { a.m_backing * b.m_backing / FontSelectionValue::fractionalEntropy, FontSelectionValue::RawTag::RawTag };
127 }
128
129 constexpr FontSelectionValue operator/(FontSelectionValue a, FontSelectionValue b)
130 {
131     return { a.m_backing * FontSelectionValue::fractionalEntropy / b.m_backing, FontSelectionValue::RawTag::RawTag };
132 }
133
134 constexpr FontSelectionValue operator-(FontSelectionValue value)
135 {
136     return { -value.m_backing, FontSelectionValue::RawTag::RawTag };
137 }
138
139 constexpr bool operator==(FontSelectionValue a, FontSelectionValue b)
140 {
141     return a.rawValue() == b.rawValue();
142 }
143
144 constexpr bool operator!=(FontSelectionValue a, FontSelectionValue b)
145 {
146     return a.rawValue() != b.rawValue();
147 }
148
149 constexpr bool operator<(FontSelectionValue a, FontSelectionValue b)
150 {
151     return a.rawValue() < b.rawValue();
152 }
153
154 constexpr bool operator<=(FontSelectionValue a, FontSelectionValue b)
155 {
156     return a.rawValue() <= b.rawValue();
157 }
158
159 constexpr bool operator>(FontSelectionValue a, FontSelectionValue b)
160 {
161     return a.rawValue() > b.rawValue();
162 }
163
164 constexpr bool operator>=(FontSelectionValue a, FontSelectionValue b)
165 {
166     return a.rawValue() >= b.rawValue();
167 }
168
169 constexpr FontSelectionValue italicThreshold()
170 {
171     return FontSelectionValue { 20 };
172 }
173
174 constexpr bool isItalic(Optional<FontSelectionValue> fontWeight)
175 {
176     return fontWeight && fontWeight.value() >= italicThreshold();
177 }
178
179 constexpr FontSelectionValue normalItalicValue()
180 {
181     return FontSelectionValue { 0 };
182 }
183
184 constexpr FontSelectionValue italicValue()
185 {
186     return FontSelectionValue { 20 };
187 }
188
189 constexpr FontSelectionValue boldThreshold()
190 {
191     return FontSelectionValue { 600 };
192 }
193
194 constexpr FontSelectionValue boldWeightValue()
195 {
196     return FontSelectionValue { 700 };
197 }
198
199 constexpr FontSelectionValue normalWeightValue()
200 {
201     return FontSelectionValue { 400 };
202 }
203
204 constexpr FontSelectionValue lightWeightValue()
205 {
206     return FontSelectionValue { 200 };
207 }
208
209 constexpr bool isFontWeightBold(FontSelectionValue fontWeight)
210 {
211     return fontWeight >= boldThreshold();
212 }
213
214 constexpr FontSelectionValue lowerWeightSearchThreshold()
215 {
216     return FontSelectionValue { 400 };
217 }
218
219 constexpr FontSelectionValue upperWeightSearchThreshold()
220 {
221     return FontSelectionValue { 500 };
222 }
223
224 constexpr FontSelectionValue ultraCondensedStretchValue()
225 {
226     return FontSelectionValue { 50 };
227 }
228
229 constexpr FontSelectionValue extraCondensedStretchValue()
230 {
231     return FontSelectionValue { 62.5f };
232 }
233
234 constexpr FontSelectionValue condensedStretchValue()
235 {
236     return FontSelectionValue { 75 };
237 }
238
239 constexpr FontSelectionValue semiCondensedStretchValue()
240 {
241     return FontSelectionValue { 87.5f };
242 }
243
244 constexpr FontSelectionValue normalStretchValue()
245 {
246     return FontSelectionValue { 100 };
247 }
248
249 constexpr FontSelectionValue semiExpandedStretchValue()
250 {
251     return FontSelectionValue { 112.5f };
252 }
253
254 constexpr FontSelectionValue expandedStretchValue()
255 {
256     return FontSelectionValue { 125 };
257 }
258
259 constexpr FontSelectionValue extraExpandedStretchValue()
260 {
261     return FontSelectionValue { 150 };
262 }
263
264 constexpr FontSelectionValue ultraExpandedStretchValue()
265 {
266     return FontSelectionValue { 200 };
267 }
268
269 // [Inclusive, Inclusive]
270 struct FontSelectionRange {
271     using Value = FontSelectionValue;
272
273     constexpr FontSelectionRange(Value minimum, Value maximum)
274         : minimum(minimum)
275         , maximum(maximum)
276     {
277     }
278
279     explicit constexpr FontSelectionRange(Value value)
280         : minimum(value)
281         , maximum(value)
282     {
283     }
284
285     constexpr bool operator==(const FontSelectionRange& other) const
286     {
287         return WTF::tie(minimum, maximum) == WTF::tie(other.minimum, other.maximum);
288     }
289
290     constexpr bool isValid() const
291     {
292         return minimum <= maximum;
293     }
294
295     void expand(const FontSelectionRange& other)
296     {
297         ASSERT(other.isValid());
298         if (!isValid())
299             *this = other;
300         else {
301             minimum = std::min(minimum, other.minimum);
302             maximum = std::max(maximum, other.maximum);
303         }
304         ASSERT(isValid());
305     }
306
307     constexpr bool includes(Value target) const
308     {
309         return target >= minimum && target <= maximum;
310     }
311
312     // FIXME: This name is not so great. Move this into the add function below
313     // once we move FontPlatformDataCacheKeyHash from IntegerHasher to Hasher,
314     // and then it doesn't need to have a name.
315     constexpr uint32_t uniqueValue() const
316     {
317         return minimum.rawValue() << 16 | maximum.rawValue();
318     }
319
320     Value minimum { 1 };
321     Value maximum { 0 };
322 };
323
324 inline void add(Hasher& hasher, const FontSelectionRange& range)
325 {
326     add(hasher, range.uniqueValue());
327 }
328
329 struct FontSelectionRequest {
330     using Value = FontSelectionValue;
331
332     Value weight;
333     Value width;
334     // FIXME: We are using an optional here to be able to distinguish between an explicit
335     // or implicit slope (for "italic" and "oblique") and the "normal" value which has no
336     // slope. The "italic" and "oblique" values can be distinguished by looking at the
337     // "fontStyleAxis" on the FontDescription. We should come up with a tri-state member
338     // so that it's a lot clearer whether we're dealing with a "normal", "italic" or explicit
339     // "oblique" font style. See webkit.org/b/187774.
340     Optional<Value> slope;
341
342     std::tuple<Value, Value, Optional<Value>> tied() const
343     {
344         return WTF::tie(weight, width, slope);
345     }
346 };
347
348 inline TextStream& operator<<(TextStream& ts, const FontSelectionValue& fontSelectionValue)
349 {
350     ts << TextStream::FormatNumberRespectingIntegers(fontSelectionValue.rawValue());
351     return ts;
352 }
353
354 inline TextStream& operator<<(TextStream& ts, const Optional<FontSelectionValue>& optionalFontSelectionValue)
355 {
356     ts << optionalFontSelectionValue.value_or(normalItalicValue());
357     return ts;
358 }
359
360 inline bool operator==(const FontSelectionRequest& a, const FontSelectionRequest& b)
361 {
362     return a.tied() == b.tied();
363 }
364
365 inline bool operator!=(const FontSelectionRequest& a, const FontSelectionRequest& b)
366 {
367     return !(a == b);
368 }
369
370 inline void add(Hasher& hasher, const FontSelectionRequest& request)
371 {
372     add(hasher, request.tied());
373 }
374
375 struct FontSelectionCapabilities {
376     using Range = FontSelectionRange;
377
378     FontSelectionCapabilities& operator=(const FontSelectionCapabilities&) = default;
379
380     constexpr std::tuple<Range, Range, Range> tied() const
381     {
382         return WTF::tie(weight, width, slope);
383     }
384
385     void expand(const FontSelectionCapabilities& capabilities)
386     {
387         weight.expand(capabilities.weight);
388         width.expand(capabilities.width);
389         slope.expand(capabilities.slope);
390     }
391
392     Range weight { normalWeightValue() };
393     Range width { normalStretchValue() };
394     Range slope { normalItalicValue() };
395 };
396
397 constexpr bool operator==(const FontSelectionCapabilities& a, const FontSelectionCapabilities& b)
398 {
399     return a.tied() == b.tied();
400 }
401
402 constexpr bool operator!=(const FontSelectionCapabilities& a, const FontSelectionCapabilities& b)
403 {
404     return !(a == b);
405 }
406
407 struct FontSelectionSpecifiedCapabilities {
408     using Capabilities = FontSelectionCapabilities;
409     using Range = FontSelectionRange;
410     using OptionalRange = Optional<Range>;
411
412     constexpr Capabilities computeFontSelectionCapabilities() const
413     {
414         return { computeWeight(), computeWidth(), computeSlope() };
415     }
416
417     constexpr std::tuple<OptionalRange&, OptionalRange&, OptionalRange&> tied()
418     {
419         return WTF::tie(weight, width, slope);
420     }
421
422     constexpr std::tuple<const OptionalRange&, const OptionalRange&, const OptionalRange&> tied() const
423     {
424         return WTF::tie(weight, width, slope);
425     }
426
427     FontSelectionSpecifiedCapabilities& operator=(const Capabilities& other)
428     {
429         tied() = other.tied();
430         return *this;
431     }
432
433     constexpr Range computeWeight() const
434     {
435         return weight.value_or(Range { normalWeightValue() });
436     }
437
438     constexpr Range computeWidth() const
439     {
440         return width.value_or(Range { normalStretchValue() });
441     }
442
443     constexpr Range computeSlope() const
444     {
445         return slope.value_or(Range { normalItalicValue() });
446     }
447
448     OptionalRange weight;
449     OptionalRange width;
450     OptionalRange slope;
451 };
452
453 constexpr bool operator==(const FontSelectionSpecifiedCapabilities& a, const FontSelectionSpecifiedCapabilities& b)
454 {
455     return a.tied() == b.tied();
456 }
457
458 constexpr bool operator!=(const FontSelectionSpecifiedCapabilities& a, const FontSelectionSpecifiedCapabilities& b)
459 {
460     return !(a == b);
461 }
462
463 class FontSelectionAlgorithm {
464 public:
465     using Capabilities = FontSelectionCapabilities;
466
467     FontSelectionAlgorithm() = delete;
468     FontSelectionAlgorithm(FontSelectionRequest, const Vector<Capabilities>&, Optional<Capabilities> capabilitiesBounds = WTF::nullopt);
469
470     struct DistanceResult {
471         FontSelectionValue distance;
472         FontSelectionValue value;
473     };
474     DistanceResult stretchDistance(Capabilities) const;
475     DistanceResult styleDistance(Capabilities) const;
476     DistanceResult weightDistance(Capabilities) const;
477
478     size_t indexOfBestCapabilities();
479
480 private:
481     using DistanceFunction = DistanceResult (FontSelectionAlgorithm::*)(Capabilities) const;
482     using CapabilitiesRange = FontSelectionRange Capabilities::*;
483     FontSelectionValue bestValue(const bool eliminated[], DistanceFunction) const;
484     void filterCapability(bool eliminated[], DistanceFunction, CapabilitiesRange);
485
486     FontSelectionRequest m_request;
487     Capabilities m_capabilitiesBounds;
488     const Vector<Capabilities>& m_capabilities;
489 };
490
491 }