1/*
2 * Copyright (C) 2005, 2006, 2007, 2014 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
40namespace WebCore {
41
42#define STRING_BUFFER_SIZE 2048
43
44typedef unsigned TruncationFunction(const String&, unsigned length, unsigned keepCount, UChar* buffer, bool shouldInsertEllipsis);
45
46static 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
55static inline int boundedTextBreakFollowing(TextBreakIterator* it, int offset, int length)
56{
57    int result = textBreakFollowing(it, offset);
58    return result == TextBreakDone ? length : result;
59}
60
61static 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    // Or just turn it on for all platforms. It seems like good behavior everywhere. Might be better to generalize
74    // it to handle all whitespace, not just "space".
75
76    // Strip single character before ellipsis character, when that character is preceded by a space
77    if (omitStart > 1 && string[omitStart - 1] != space && omitStart > 2 && string[omitStart - 2] == space)
78        --omitStart;
79
80    // Strip whitespace before and after the ellipsis character
81    while (omitStart > 1 && string[omitStart - 1] == space)
82        --omitStart;
83
84    // Strip single character after ellipsis character, when that character is followed by a space
85    if ((length - omitEnd) > 1 && string[omitEnd] != space && (length - omitEnd) > 2 && string[omitEnd + 1] == space)
86        ++omitEnd;
87
88    while ((length - omitEnd) > 1 && string[omitEnd] == space)
89        ++omitEnd;
90#endif
91
92    unsigned truncatedLength = omitStart + shouldInsertEllipsis + (length - omitEnd);
93    ASSERT(truncatedLength <= length);
94
95    StringView(string).substring(0, omitStart).getCharactersWithUpconvert(buffer);
96    if (shouldInsertEllipsis)
97        buffer[omitStart++] = horizontalEllipsis;
98    StringView(string).substring(omitEnd, length - omitEnd).getCharactersWithUpconvert(&buffer[omitStart]);
99    return truncatedLength;
100}
101
102static unsigned rightTruncateToBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool shouldInsertEllipsis)
103{
104    ASSERT_WITH_SECURITY_IMPLICATION(keepCount < length);
105    ASSERT_WITH_SECURITY_IMPLICATION(keepCount < STRING_BUFFER_SIZE);
106
107#if PLATFORM(IOS)
108    // FIXME: We should guard this code behind an editing behavior. Then we can remove the PLATFORM(IOS)-guard.
109    // Or just turn it on for all platforms. It seems like good behavior everywhere. Might be better to generalize
110    // it to handle all whitespace, not just "space".
111
112    // Strip single character before ellipsis character, when that character is preceded by a space
113    if (keepCount > 1 && string[keepCount - 1] != space && keepCount > 2 && string[keepCount - 2] == space)
114        --keepCount;
115
116    // Strip whitespace before the ellipsis character
117    while (keepCount > 1 && string[keepCount - 1] == space)
118        --keepCount;
119#endif
120
121    NonSharedCharacterBreakIterator it(StringView(string).substring(0, length));
122    unsigned keepLength = textBreakAtOrPreceding(it, keepCount);
123    unsigned truncatedLength = shouldInsertEllipsis ? keepLength + 1 : keepLength;
124
125    StringView(string).substring(0, keepLength).getCharactersWithUpconvert(buffer);
126    if (shouldInsertEllipsis)
127        buffer[keepLength] = horizontalEllipsis;
128
129    return truncatedLength;
130}
131
132static unsigned rightClipToCharacterBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool)
133{
134    ASSERT(keepCount < length);
135    ASSERT(keepCount < STRING_BUFFER_SIZE);
136
137    NonSharedCharacterBreakIterator it(StringView(string).substring(0, length));
138    unsigned keepLength = textBreakAtOrPreceding(it, keepCount);
139    StringView(string).substring(0, keepLength).getCharactersWithUpconvert(buffer);
140
141    return keepLength;
142}
143
144static unsigned rightClipToWordBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool)
145{
146    ASSERT(keepCount < length);
147    ASSERT(keepCount < STRING_BUFFER_SIZE);
148
149    TextBreakIterator* it = wordBreakIterator(StringView(string).substring(0, length));
150    unsigned keepLength = textBreakAtOrPreceding(it, keepCount);
151    StringView(string).substring(0, keepLength).getCharactersWithUpconvert(buffer);
152
153#if PLATFORM(IOS)
154    // FIXME: We should guard this code behind an editing behavior. Then we can remove the PLATFORM(IOS)-guard.
155    // Or just turn it on for all platforms. It seems like good behavior everywhere. Might be better to generalize
156    // it to handle all whitespace, not just "space".
157
158    // Motivated by <rdar://problem/7439327> truncation should not include a trailing space
159    while (keepLength && string[keepLength - 1] == space)
160        --keepLength;
161#endif
162
163    return keepLength;
164}
165
166static unsigned leftTruncateToBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer, bool shouldInsertEllipsis)
167{
168    ASSERT(keepCount < length);
169    ASSERT(keepCount < STRING_BUFFER_SIZE);
170
171    unsigned startIndex = length - keepCount;
172
173    NonSharedCharacterBreakIterator it(string);
174    unsigned adjustedStartIndex = startIndex;
175    startIndex = boundedTextBreakFollowing(it, startIndex, length - startIndex);
176
177    // Strip single character after ellipsis character, when that character is preceded by a space
178    if (adjustedStartIndex < length && string[adjustedStartIndex] != space
179        && adjustedStartIndex < length - 1 && string[adjustedStartIndex + 1] == space)
180        ++adjustedStartIndex;
181
182    // Strip whitespace after the ellipsis character
183    while (adjustedStartIndex < length && string[adjustedStartIndex] == space)
184        ++adjustedStartIndex;
185
186    if (shouldInsertEllipsis) {
187        buffer[0] = horizontalEllipsis;
188        StringView(string).substring(adjustedStartIndex, length - adjustedStartIndex + 1).getCharactersWithUpconvert(&buffer[1]);
189        return length - adjustedStartIndex + 1;
190    }
191    StringView(string).substring(adjustedStartIndex, length - adjustedStartIndex + 1).getCharactersWithUpconvert(&buffer[0]);
192    return length - adjustedStartIndex;
193}
194
195static float stringWidth(const Font& renderer, const UChar* characters, unsigned length, bool disableRoundingHacks)
196{
197    TextRun run(characters, length);
198    if (disableRoundingHacks)
199        run.disableRoundingHacks();
200    return renderer.width(run);
201}
202
203static 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)
204{
205    if (string.isEmpty())
206        return string;
207
208    if (resultWidth)
209        *resultWidth = 0;
210
211    ASSERT(maxWidth >= 0);
212
213    float currentEllipsisWidth = shouldInsertEllipsis ? stringWidth(font, &horizontalEllipsis, 1, disableRoundingHacks) : customTruncationElementWidth;
214
215    UChar stringBuffer[STRING_BUFFER_SIZE];
216    unsigned truncatedLength;
217    unsigned keepCount;
218    unsigned length = string.length();
219
220    if (length > STRING_BUFFER_SIZE) {
221        if (shouldInsertEllipsis)
222            keepCount = STRING_BUFFER_SIZE - 1; // need 1 character for the ellipsis
223        else
224            keepCount = 0;
225        truncatedLength = centerTruncateToBuffer(string, length, keepCount, stringBuffer, shouldInsertEllipsis);
226    } else {
227        keepCount = length;
228        StringView(string).getCharactersWithUpconvert(stringBuffer);
229        truncatedLength = length;
230    }
231
232    float width = stringWidth(font, stringBuffer, truncatedLength, disableRoundingHacks);
233    if (!shouldInsertEllipsis && alwaysTruncate)
234        width += customTruncationElementWidth;
235    if ((width - maxWidth) < 0.0001) { // Ignore rounding errors.
236        if (resultWidth)
237            *resultWidth = width;
238        return string;
239    }
240
241    unsigned keepCountForLargestKnownToFit = 0;
242    float widthForLargestKnownToFit = currentEllipsisWidth;
243
244    unsigned keepCountForSmallestKnownToNotFit = keepCount;
245    float widthForSmallestKnownToNotFit = width;
246
247    if (currentEllipsisWidth >= maxWidth) {
248        keepCountForLargestKnownToFit = 1;
249        keepCountForSmallestKnownToNotFit = 2;
250    }
251
252    while (keepCountForLargestKnownToFit + 1 < keepCountForSmallestKnownToNotFit) {
253        ASSERT_WITH_SECURITY_IMPLICATION(widthForLargestKnownToFit <= maxWidth);
254        ASSERT_WITH_SECURITY_IMPLICATION(widthForSmallestKnownToNotFit > maxWidth);
255
256        float ratio = (keepCountForSmallestKnownToNotFit - keepCountForLargestKnownToFit)
257            / (widthForSmallestKnownToNotFit - widthForLargestKnownToFit);
258        keepCount = static_cast<unsigned>(maxWidth * ratio);
259
260        if (keepCount <= keepCountForLargestKnownToFit)
261            keepCount = keepCountForLargestKnownToFit + 1;
262        else if (keepCount >= keepCountForSmallestKnownToNotFit)
263            keepCount = keepCountForSmallestKnownToNotFit - 1;
264
265        ASSERT_WITH_SECURITY_IMPLICATION(keepCount < length);
266        ASSERT(keepCount > 0);
267        ASSERT_WITH_SECURITY_IMPLICATION(keepCount < keepCountForSmallestKnownToNotFit);
268        ASSERT_WITH_SECURITY_IMPLICATION(keepCount > keepCountForLargestKnownToFit);
269
270        truncatedLength = truncateToBuffer(string, length, keepCount, stringBuffer, shouldInsertEllipsis);
271
272        width = stringWidth(font, stringBuffer, truncatedLength, disableRoundingHacks);
273        if (!shouldInsertEllipsis)
274            width += customTruncationElementWidth;
275        if (width <= maxWidth) {
276            keepCountForLargestKnownToFit = keepCount;
277            widthForLargestKnownToFit = width;
278            if (resultWidth)
279                *resultWidth = width;
280        } else {
281            keepCountForSmallestKnownToNotFit = keepCount;
282            widthForSmallestKnownToNotFit = width;
283        }
284    }
285
286    if (keepCountForLargestKnownToFit == 0) {
287        keepCountForLargestKnownToFit = 1;
288    }
289
290    if (keepCount != keepCountForLargestKnownToFit) {
291        keepCount = keepCountForLargestKnownToFit;
292        truncatedLength = truncateToBuffer(string, length, keepCount, stringBuffer, shouldInsertEllipsis);
293    }
294
295    return String(stringBuffer, truncatedLength);
296}
297
298String StringTruncator::centerTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks)
299{
300    return truncateString(string, maxWidth, font, centerTruncateToBuffer, !enableRoundingHacks);
301}
302
303String StringTruncator::rightTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks)
304{
305    return truncateString(string, maxWidth, font, rightTruncateToBuffer, !enableRoundingHacks);
306}
307
308float StringTruncator::width(const String& string, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks)
309{
310    return stringWidth(font, StringView(string).upconvertedCharacters(), string.length(), !enableRoundingHacks);
311}
312
313String StringTruncator::centerTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
314{
315    return truncateString(string, maxWidth, font, centerTruncateToBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
316}
317
318String StringTruncator::rightTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
319{
320    return truncateString(string, maxWidth, font, rightTruncateToBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
321}
322
323String StringTruncator::leftTruncate(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
324{
325    return truncateString(string, maxWidth, font, leftTruncateToBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
326}
327
328String StringTruncator::rightClipToCharacter(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis, float customTruncationElementWidth)
329{
330    return truncateString(string, maxWidth, font, rightClipToCharacterBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth);
331}
332
333String StringTruncator::rightClipToWord(const String& string, float maxWidth, const Font& font, EnableRoundingHacksOrNot enableRoundingHacks, float& resultWidth, bool shouldInsertEllipsis,  float customTruncationElementWidth, bool alwaysTruncate)
334{
335    return truncateString(string, maxWidth, font, rightClipToWordBuffer, !enableRoundingHacks, &resultWidth, shouldInsertEllipsis, customTruncationElementWidth, alwaysTruncate);
336}
337
338} // namespace WebCore
339