15e85d504b2d979128bc1b28df75a7aa7f8b2c1d
[WebKit-https.git] / Source / WebCore / platform / graphics / StringTruncator.cpp
1 /*
2  * Copyright (C) 2005, 2006, 2007 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  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer. 
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution. 
13  * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission. 
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "config.h"
30 #include "StringTruncator.h"
31
32 #include "Font.h"
33 #include "TextBreakIterator.h"
34 #include "TextRun.h"
35 #include <wtf/Assertions.h>
36 #include <wtf/Vector.h>
37 #include <wtf/text/StringView.h>
38 #include <wtf/unicode/CharacterNames.h>
39
40 namespace WebCore {
41
42 #define STRING_BUFFER_SIZE 2048
43
44 typedef unsigned TruncationFunction(const String&, unsigned length, unsigned keepCount, UChar* buffer, bool shouldInsertEllipsis);
45
46 static inline int textBreakAtOrPreceding(TextBreakIterator* it, int offset)
47 {
48     if (isTextBreak(it, offset))
49         return offset;
50
51     int result = textBreakPreceding(it, offset);
52     return result == TextBreakDone ? 0 : result;
53 }
54
55 static inline int boundedTextBreakFollowing(TextBreakIterator* it, int offset, int length)
56 {
57     int result = textBreakFollowing(it, offset);
58     return result == TextBreakDone ? length : result;
59 }
60
61 static unsigned centerTruncateToBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool shouldInsertEllipsis)
62 {
63     ASSERT_WITH_SECURITY_IMPLICATION(keepCount < length);
64     ASSERT_WITH_SECURITY_IMPLICATION(keepCount < STRING_BUFFER_SIZE);
65     
66     unsigned omitStart = (keepCount + 1) / 2;
67     NonSharedCharacterBreakIterator it(StringView(string).substring(0, length));
68     unsigned omitEnd = boundedTextBreakFollowing(it, omitStart + (length - keepCount) - 1, length);
69     omitStart = textBreakAtOrPreceding(it, omitStart);
70
71 #if PLATFORM(IOS)
72     // FIXME: We should guard this code behind an editing behavior. Then we can remove the PLATFORM(IOS)-guard.
73
74     // Strip single character before ellipsis character, when that character is preceded by a space
75     if (omitStart > 1 && string[omitStart - 1] != space && omitStart > 2 && string[omitStart - 2] == space)
76         --omitStart;
77
78     // Strip whitespace before and after the ellipsis character
79     while (omitStart > 1 && string[omitStart - 1] == space)
80         --omitStart;
81
82     // Strip single character after ellipsis character, when that character is followed by a space
83     if ((length - omitEnd) > 1 && string[omitEnd] != space && (length - omitEnd) > 2 && string[omitEnd + 1] == space)
84         ++omitEnd;
85
86     while ((length - omitEnd) > 1 && string[omitEnd] == space)
87         ++omitEnd;
88 #endif
89
90     unsigned truncatedLength = shouldInsertEllipsis ? omitStart + 1 + (length - omitEnd) : length - (omitEnd - omitStart);
91     ASSERT(truncatedLength <= length);
92
93     StringView(string).substring(0, omitStart).getCharactersWithUpconvert(buffer);
94     if (shouldInsertEllipsis)
95         buffer[omitStart++] = horizontalEllipsis;
96     StringView(string).substring(omitEnd, length - omitEnd).getCharactersWithUpconvert(&buffer[omitStart + 1]);
97     return truncatedLength;
98 }
99
100 static unsigned rightTruncateToBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool shouldInsertEllipsis)
101 {
102     ASSERT_WITH_SECURITY_IMPLICATION(keepCount < length);
103     ASSERT_WITH_SECURITY_IMPLICATION(keepCount < STRING_BUFFER_SIZE);
104
105 #if PLATFORM(IOS)
106     // FIXME: We should guard this code behind an editing behavior. Then we can remove the PLATFORM(IOS)-guard.
107
108     // Strip single character before ellipsis character, when that character is preceded by a space
109     if (keepCount > 1 && string[keepCount - 1] != space && keepCount > 2 && string[keepCount - 2] == space)
110         --keepCount;
111
112     // Strip whitespace before the ellipsis character
113     while (keepCount > 1 && string[keepCount - 1] == space)
114         --keepCount;
115 #endif
116
117     NonSharedCharacterBreakIterator it(StringView(string).substring(0, length));
118     unsigned keepLength = textBreakAtOrPreceding(it, keepCount);
119     unsigned truncatedLength = shouldInsertEllipsis ? keepLength + 1 : keepLength;
120
121     StringView(string).substring(0, keepLength).getCharactersWithUpconvert(buffer);
122     if (shouldInsertEllipsis)
123         buffer[keepLength] = horizontalEllipsis;
124
125     return truncatedLength;
126 }
127
128 static unsigned rightClipToCharacterBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool)
129 {
130     ASSERT(keepCount < length);
131     ASSERT(keepCount < STRING_BUFFER_SIZE);
132
133     NonSharedCharacterBreakIterator it(StringView(string).substring(0, length));
134     unsigned keepLength = textBreakAtOrPreceding(it, keepCount);
135     StringView(string).substring(0, keepLength).getCharactersWithUpconvert(buffer);
136
137     return keepLength;
138 }
139
140 static unsigned rightClipToWordBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool)
141 {
142     ASSERT(keepCount < length);
143     ASSERT(keepCount < STRING_BUFFER_SIZE);
144
145     TextBreakIterator* it = wordBreakIterator(StringView(string).substring(0, length));
146     unsigned keepLength = textBreakAtOrPreceding(it, keepCount);
147     StringView(string).substring(0, keepLength).getCharactersWithUpconvert(buffer);
148
149 #if PLATFORM(IOS)
150     // FIXME: We should guard this code behind an editing behavior. Then we can remove the PLATFORM(IOS)-guard.
151     // Motivated by <rdar://problem/7439327> truncation should not include a trailing space
152     while ((keepLength > 0) && (string[keepLength - 1] == space))
153         --keepLength;
154 #endif
155     return keepLength;
156 }
157
158 static unsigned leftTruncateToBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool shouldInsertEllipsis)
159 {
160     ASSERT(keepCount < length);
161     ASSERT(keepCount < STRING_BUFFER_SIZE);
162
163     unsigned startIndex = length - keepCount;
164
165     NonSharedCharacterBreakIterator it(string);
166     unsigned adjustedStartIndex = startIndex;
167     startIndex = boundedTextBreakFollowing(it, startIndex, length - startIndex);
168
169     // Strip single character after ellipsis character, when that character is preceded by a space
170     if (adjustedStartIndex < length && string[adjustedStartIndex] != space
171         && adjustedStartIndex < length - 1 && string[adjustedStartIndex + 1] == space)
172         ++adjustedStartIndex;
173
174     // Strip whitespace after the ellipsis character
175     while (adjustedStartIndex < length && string[adjustedStartIndex] == space)
176         ++adjustedStartIndex;
177
178     if (shouldInsertEllipsis) {
179         buffer[0] = horizontalEllipsis;
180         StringView(string).substring(adjustedStartIndex, length - adjustedStartIndex + 1).getCharactersWithUpconvert(&buffer[1]);
181         return length - adjustedStartIndex + 1;
182     }
183     StringView(string).substring(adjustedStartIndex, length - adjustedStartIndex + 1).getCharactersWithUpconvert(&buffer[0]);
184     return length - adjustedStartIndex;
185 }
186
187 static float stringWidth(const Font& renderer, const UChar* characters, unsigned length, bool disableRoundingHacks)
188 {
189     TextRun run(characters, length);
190     if (disableRoundingHacks)
191         run.disableRoundingHacks();
192     return renderer.width(run);
193 }
194
195 static String truncateString(const String& string, float maxWidth, const Font& font, TruncationFunction truncateToBuffer, bool disableRoundingHacks, float* resultWidth = nullptr, bool shouldInsertEllipsis = true,  float customTruncationElementWidth = 0, bool alwaysTruncate = false)
196 {
197     if (string.isEmpty())
198         return string;
199
200     if (resultWidth)
201         *resultWidth = 0;
202
203     ASSERT(maxWidth >= 0);
204
205     float currentEllipsisWidth = shouldInsertEllipsis ? stringWidth(font, &horizontalEllipsis, 1, disableRoundingHacks) : customTruncationElementWidth;
206
207     UChar stringBuffer[STRING_BUFFER_SIZE];
208     unsigned truncatedLength;
209     unsigned keepCount;
210     unsigned length = string.length();
211
212     if (length > STRING_BUFFER_SIZE) {
213         if (shouldInsertEllipsis)
214             keepCount = STRING_BUFFER_SIZE - 1; // need 1 character for the ellipsis
215         else
216             keepCount = 0;
217         truncatedLength = centerTruncateToBuffer(string, length, keepCount, stringBuffer, shouldInsertEllipsis);
218     } else {
219         keepCount = length;
220         StringView(string).getCharactersWithUpconvert(stringBuffer);
221         truncatedLength = length;
222     }
223
224     float width = stringWidth(font, stringBuffer, truncatedLength, disableRoundingHacks);
225     if (!shouldInsertEllipsis && alwaysTruncate)
226         width += customTruncationElementWidth;
227     if ((width - maxWidth) < 0.0001) { // Ignore rounding errors.
228         if (resultWidth)
229             *resultWidth = width;
230         return string;
231     }
232
233     unsigned keepCountForLargestKnownToFit = 0;
234     float widthForLargestKnownToFit = currentEllipsisWidth;
235     
236     unsigned keepCountForSmallestKnownToNotFit = keepCount;
237     float widthForSmallestKnownToNotFit = width;
238     
239     if (currentEllipsisWidth >= maxWidth) {
240         keepCountForLargestKnownToFit = 1;
241         keepCountForSmallestKnownToNotFit = 2;
242     }
243     
244     while (keepCountForLargestKnownToFit + 1 < keepCountForSmallestKnownToNotFit) {
245         ASSERT_WITH_SECURITY_IMPLICATION(widthForLargestKnownToFit <= maxWidth);
246         ASSERT_WITH_SECURITY_IMPLICATION(widthForSmallestKnownToNotFit > maxWidth);
247
248         float ratio = (keepCountForSmallestKnownToNotFit - keepCountForLargestKnownToFit)
249             / (widthForSmallestKnownToNotFit - widthForLargestKnownToFit);
250         keepCount = static_cast<unsigned>(maxWidth * ratio);
251         
252         if (keepCount <= keepCountForLargestKnownToFit) {
253             keepCount = keepCountForLargestKnownToFit + 1;
254         } else if (keepCount >= keepCountForSmallestKnownToNotFit) {
255             keepCount = keepCountForSmallestKnownToNotFit - 1;
256         }
257         
258         ASSERT_WITH_SECURITY_IMPLICATION(keepCount < length);
259         ASSERT(keepCount > 0);
260         ASSERT_WITH_SECURITY_IMPLICATION(keepCount < keepCountForSmallestKnownToNotFit);
261         ASSERT_WITH_SECURITY_IMPLICATION(keepCount > keepCountForLargestKnownToFit);
262
263         truncatedLength = truncateToBuffer(string, length, keepCount, stringBuffer, shouldInsertEllipsis);
264
265         width = stringWidth(font, stringBuffer, truncatedLength, disableRoundingHacks);
266         if (!shouldInsertEllipsis)
267             width += customTruncationElementWidth;
268         if (width <= maxWidth) {
269             keepCountForLargestKnownToFit = keepCount;
270             widthForLargestKnownToFit = width;
271             if (resultWidth)
272                 *resultWidth = width;
273         } else {
274             keepCountForSmallestKnownToNotFit = keepCount;
275             widthForSmallestKnownToNotFit = width;
276         }
277     }
278     
279     if (keepCountForLargestKnownToFit == 0) {
280         keepCountForLargestKnownToFit = 1;
281     }
282     
283     if (keepCount != keepCountForLargestKnownToFit) {
284         keepCount = keepCountForLargestKnownToFit;
285         truncatedLength = truncateToBuffer(string, length, keepCount, stringBuffer, shouldInsertEllipsis);
286     }
287     
288     return String(stringBuffer, truncatedLength);
289 }
290
291 String StringTruncator::centerTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks)
292 {
293     return truncateString(string, maxWidth, font, centerTruncateToBuffer, !enableRoundingHacks);
294 }
295
296 String StringTruncator::rightTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks)
297 {
298     return truncateString(string, maxWidth, font, rightTruncateToBuffer, !enableRoundingHacks);
299 }
300
301 float StringTruncator::width(const String& string, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks)
302 {
303     return stringWidth(font, StringView(string).upconvertedCharacters(), string.length(), !enableRoundingHacks);
304 }
305
306 String StringTruncator::centerTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
307 {
308     return truncateString(string, maxWidth, font, centerTruncateToBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
309 }
310
311 String StringTruncator::rightTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
312 {
313     return truncateString(string, maxWidth, font, rightTruncateToBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
314 }
315
316 String StringTruncator::leftTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
317 {
318     return truncateString(string, maxWidth, font, leftTruncateToBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
319 }
320
321 String StringTruncator::rightClipToCharacter(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
322 {
323     return truncateString(string, maxWidth, font, rightClipToCharacterBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
324 }
325
326 String StringTruncator::rightClipToWord(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis,  float customTruncationElementWidth, bool alwaysTruncate)
327 {
328     return truncateString(string, maxWidth, font, rightClipToWordBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth, alwaysTruncate);
329 }
330
331 } // namespace WebCore