1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef MINIKIN_LINE_BREAKER_UTIL_H
18 #define MINIKIN_LINE_BREAKER_UTIL_H
19
20 #include <vector>
21
22 #include "minikin/Hyphenator.h"
23 #include "minikin/MeasuredText.h"
24 #include "minikin/U16StringPiece.h"
25
26 #include "HyphenatorMap.h"
27 #include "LayoutUtils.h"
28 #include "Locale.h"
29 #include "LocaleListCache.h"
30 #include "MinikinInternal.h"
31 #include "WordBreaker.h"
32
33 namespace minikin {
34
35 // ParaWidth is used to hold cumulative width from beginning of paragraph. Note that for very large
36 // paragraphs, accuracy could degrade using only 32-bit float. Note however that float is used
37 // extensively on the Java side for this. This is a typedef so that we can easily change it based
38 // on performance/accuracy tradeoff.
39 typedef double ParaWidth;
40
41 // Hyphenates a string potentially containing non-breaking spaces.
42 std::vector<HyphenationType> hyphenate(const U16StringPiece& string, const Hyphenator& hypenator);
43
44 // This function determines whether a character is a space that disappears at end of line.
45 // It is the Unicode set: [[:General_Category=Space_Separator:]-[:Line_Break=Glue:]], plus '\n'.
46 // Note: all such characters are in the BMP, so it's ok to use code units for this.
isLineEndSpace(uint16_t c)47 inline bool isLineEndSpace(uint16_t c) {
48 return c == '\n' || c == ' ' // SPACE
49 || c == 0x1680 // OGHAM SPACE MARK
50 || (0x2000 <= c && c <= 0x200A && c != 0x2007) // EN QUAD, EM QUAD, EN SPACE, EM SPACE,
51 // THREE-PER-EM SPACE, FOUR-PER-EM SPACE,
52 // SIX-PER-EM SPACE, PUNCTUATION SPACE,
53 // THIN SPACE, HAIR SPACE
54 || c == 0x205F // MEDIUM MATHEMATICAL SPACE
55 || c == 0x3000;
56 }
57
getEffectiveLocale(uint32_t localeListId)58 inline Locale getEffectiveLocale(uint32_t localeListId) {
59 const LocaleList& localeList = LocaleListCache::getById(localeListId);
60 return localeList.empty() ? Locale() : localeList[0];
61 }
62
63 // Retrieves hyphenation break points from a word.
populateHyphenationPoints(const U16StringPiece & textBuf,const Run & run,const Hyphenator & hyphenator,const Range & contextRange,const Range & hyphenationTargetRange,std::vector<HyphenBreak> * out,LayoutPieces * pieces)64 inline void populateHyphenationPoints(
65 const U16StringPiece& textBuf, // A text buffer.
66 const Run& run, // A run of this region.
67 const Hyphenator& hyphenator, // A hyphenator to be used for hyphenation.
68 const Range& contextRange, // A context range for measuring hyphenated piece.
69 const Range& hyphenationTargetRange, // An actual range for the hyphenation target.
70 std::vector<HyphenBreak>* out, // An output to be appended.
71 LayoutPieces* pieces) { // An output of layout pieces. Maybe null.
72 if (!run.getRange().contains(contextRange) || !contextRange.contains(hyphenationTargetRange)) {
73 return;
74 }
75
76 const std::vector<HyphenationType> hyphenResult =
77 hyphenate(textBuf.substr(hyphenationTargetRange), hyphenator);
78 for (uint32_t i = hyphenationTargetRange.getStart(); i < hyphenationTargetRange.getEnd(); ++i) {
79 const HyphenationType hyph = hyphenResult[hyphenationTargetRange.toRangeOffset(i)];
80 if (hyph == HyphenationType::DONT_BREAK) {
81 continue; // Not a hyphenation point.
82 }
83
84 auto hyphenPart = contextRange.split(i);
85 U16StringPiece firstText = textBuf.substr(hyphenPart.first);
86 U16StringPiece secondText = textBuf.substr(hyphenPart.second);
87 const float first =
88 run.measureHyphenPiece(firstText, Range(0, firstText.size()),
89 StartHyphenEdit::NO_EDIT /* start hyphen edit */,
90 editForThisLine(hyph) /* end hyphen edit */, pieces);
91 const float second =
92 run.measureHyphenPiece(secondText, Range(0, secondText.size()),
93 editForNextLine(hyph) /* start hyphen edit */,
94 EndHyphenEdit::NO_EDIT /* end hyphen edit */, pieces);
95
96 out->emplace_back(i, hyph, first, second);
97 }
98 }
99
100 // Processes and retrieve informations from characters in the paragraph.
101 struct CharProcessor {
102 // The number of spaces.
103 uint32_t rawSpaceCount = 0;
104
105 // The number of spaces minus trailing spaces.
106 uint32_t effectiveSpaceCount = 0;
107
108 // The sum of character width from the paragraph start.
109 ParaWidth sumOfCharWidths = 0.0;
110
111 // The sum of character width from the paragraph start minus trailing line end spaces.
112 // This means that the line width from the paragraph start if we decided break now.
113 ParaWidth effectiveWidth = 0.0;
114
115 // The total amount of character widths at the previous word break point.
116 ParaWidth sumOfCharWidthsAtPrevWordBreak = 0.0;
117
118 // The next word break offset.
119 uint32_t nextWordBreak = 0;
120
121 // The previous word break offset.
122 uint32_t prevWordBreak = 0;
123
124 // The width of a space. May be 0 if there are no spaces.
125 // Note: if there are multiple different widths for spaces (for example, because of mixing of
126 // fonts), it's only guaranteed to pick one.
127 float spaceWidth = 0.0f;
128
129 // The current hyphenator.
130 const Hyphenator* hyphenator = nullptr;
131
132 // Retrieve the current word range.
wordRangeCharProcessor133 inline Range wordRange() const { return breaker.wordRange(); }
134
135 // Retrieve the current context range.
contextRangeCharProcessor136 inline Range contextRange() const { return Range(prevWordBreak, nextWordBreak); }
137
138 // Returns the width from the last word break point.
widthFromLastWordBreakCharProcessor139 inline ParaWidth widthFromLastWordBreak() const {
140 return effectiveWidth - sumOfCharWidthsAtPrevWordBreak;
141 }
142
143 // Returns the break penalty for the current word break point.
wordBreakPenaltyCharProcessor144 inline int wordBreakPenalty() const { return breaker.breakBadness(); }
145
CharProcessorCharProcessor146 CharProcessor(const U16StringPiece& text) { breaker.setText(text.data(), text.size()); }
147
148 // The user of CharProcessor must call updateLocaleIfNecessary with valid locale at least one
149 // time before feeding characters.
updateLocaleIfNecessaryCharProcessor150 void updateLocaleIfNecessary(const Run& run) {
151 uint32_t newLocaleListId = run.getLocaleListId();
152 if (localeListId != newLocaleListId) {
153 Locale locale = getEffectiveLocale(newLocaleListId);
154 nextWordBreak = breaker.followingWithLocale(locale, run.getRange().getStart());
155 hyphenator = HyphenatorMap::lookup(locale);
156 localeListId = newLocaleListId;
157 }
158 }
159
160 // Process one character.
feedCharCharProcessor161 void feedChar(uint32_t idx, uint16_t c, float w, bool canBreakHere) {
162 if (idx == nextWordBreak) {
163 if (canBreakHere) {
164 prevWordBreak = nextWordBreak;
165 sumOfCharWidthsAtPrevWordBreak = sumOfCharWidths;
166 }
167 nextWordBreak = breaker.next();
168 }
169 if (isWordSpace(c)) {
170 rawSpaceCount += 1;
171 spaceWidth = w;
172 }
173 sumOfCharWidths += w;
174 if (isLineEndSpace(c)) {
175 // If we break a line on a line-ending space, that space goes away. So postBreak
176 // and postSpaceCount, which keep the width and number of spaces if we decide to
177 // break at this point, don't need to get adjusted.
178 } else {
179 effectiveSpaceCount = rawSpaceCount;
180 effectiveWidth = sumOfCharWidths;
181 }
182 }
183
184 private:
185 // The current locale list id.
186 uint32_t localeListId = LocaleListCache::kInvalidListId;
187
188 WordBreaker breaker;
189 };
190 } // namespace minikin
191
192 #endif // MINIKIN_LINE_BREAKER_UTIL_H
193