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 Computer, 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 "platform/text/StringTruncator.h"
31
32#include "platform/fonts/Font.h"
33#include "platform/text/TextBreakIterator.h"
34#include "platform/text/TextRun.h"
35#include "wtf/Assertions.h"
36#include "wtf/unicode/CharacterNames.h"
37
38namespace blink {
39
40#define STRING_BUFFER_SIZE 2048
41
42typedef unsigned TruncationFunction(const String&, unsigned length, unsigned keepCount, UChar* buffer);
43
44static inline int textBreakAtOrPreceding(const NonSharedCharacterBreakIterator& it, int offset)
45{
46    if (it.isBreak(offset))
47        return offset;
48
49    int result = it.preceding(offset);
50    return result == TextBreakDone ? 0 : result;
51}
52
53static inline int boundedTextBreakFollowing(const NonSharedCharacterBreakIterator& it, int offset, int length)
54{
55    int result = it.following(offset);
56    return result == TextBreakDone ? length : result;
57}
58
59static unsigned centerTruncateToBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer)
60{
61    ASSERT(keepCount < length);
62    ASSERT(keepCount < STRING_BUFFER_SIZE);
63
64    unsigned omitStart = (keepCount + 1) / 2;
65    NonSharedCharacterBreakIterator it(string);
66    unsigned omitEnd = boundedTextBreakFollowing(it, omitStart + (length - keepCount) - 1, length);
67    omitStart = textBreakAtOrPreceding(it, omitStart);
68
69    unsigned truncatedLength = omitStart + 1 + (length - omitEnd);
70    ASSERT(truncatedLength <= length);
71
72    string.copyTo(buffer, 0, omitStart);
73    buffer[omitStart] = horizontalEllipsis;
74    string.copyTo(&buffer[omitStart + 1], omitEnd, length - omitEnd);
75
76    return truncatedLength;
77}
78
79static unsigned rightTruncateToBuffer(const String& string, unsigned length, unsigned keepCount, UChar* buffer)
80{
81    ASSERT(keepCount < length);
82    ASSERT(keepCount < STRING_BUFFER_SIZE);
83
84    NonSharedCharacterBreakIterator it(string);
85    unsigned keepLength = textBreakAtOrPreceding(it, keepCount);
86    unsigned truncatedLength = keepLength + 1;
87
88    string.copyTo(buffer, 0, keepLength);
89    buffer[keepLength] = horizontalEllipsis;
90
91    return truncatedLength;
92}
93
94static float stringWidth(const Font& renderer, const String& string)
95{
96    TextRun run(string);
97    return renderer.width(run);
98}
99
100static float stringWidth(const Font& renderer, const UChar* characters, unsigned length)
101{
102    TextRun run(characters, length);
103    return renderer.width(run);
104}
105
106static String truncateString(const String& string, float maxWidth, const Font& font, TruncationFunction truncateToBuffer)
107{
108    if (string.isEmpty())
109        return string;
110
111    ASSERT(maxWidth >= 0);
112
113    float currentEllipsisWidth = stringWidth(font, &horizontalEllipsis, 1);
114
115    UChar stringBuffer[STRING_BUFFER_SIZE];
116    unsigned truncatedLength;
117    unsigned keepCount;
118    unsigned length = string.length();
119
120    if (length > STRING_BUFFER_SIZE) {
121        keepCount = STRING_BUFFER_SIZE - 1; // need 1 character for the ellipsis
122        truncatedLength = centerTruncateToBuffer(string, length, keepCount, stringBuffer);
123    } else {
124        keepCount = length;
125        string.copyTo(stringBuffer, 0, length);
126        truncatedLength = length;
127    }
128
129    float width = stringWidth(font, stringBuffer, truncatedLength);
130    if (width <= maxWidth)
131        return string;
132
133    unsigned keepCountForLargestKnownToFit = 0;
134    float widthForLargestKnownToFit = currentEllipsisWidth;
135
136    unsigned keepCountForSmallestKnownToNotFit = keepCount;
137    float widthForSmallestKnownToNotFit = width;
138
139    if (currentEllipsisWidth >= maxWidth) {
140        keepCountForLargestKnownToFit = 1;
141        keepCountForSmallestKnownToNotFit = 2;
142    }
143
144    while (keepCountForLargestKnownToFit + 1 < keepCountForSmallestKnownToNotFit) {
145        ASSERT(widthForLargestKnownToFit <= maxWidth);
146        ASSERT(widthForSmallestKnownToNotFit > maxWidth);
147
148        float ratio = (keepCountForSmallestKnownToNotFit - keepCountForLargestKnownToFit)
149            / (widthForSmallestKnownToNotFit - widthForLargestKnownToFit);
150        keepCount = static_cast<unsigned>(maxWidth * ratio);
151
152        if (keepCount <= keepCountForLargestKnownToFit) {
153            keepCount = keepCountForLargestKnownToFit + 1;
154        } else if (keepCount >= keepCountForSmallestKnownToNotFit) {
155            keepCount = keepCountForSmallestKnownToNotFit - 1;
156        }
157
158        ASSERT(keepCount < length);
159        ASSERT(keepCount > 0);
160        ASSERT(keepCount < keepCountForSmallestKnownToNotFit);
161        ASSERT(keepCount > keepCountForLargestKnownToFit);
162
163        truncatedLength = truncateToBuffer(string, length, keepCount, stringBuffer);
164
165        width = stringWidth(font, stringBuffer, truncatedLength);
166        if (width <= maxWidth) {
167            keepCountForLargestKnownToFit = keepCount;
168            widthForLargestKnownToFit = width;
169        } else {
170            keepCountForSmallestKnownToNotFit = keepCount;
171            widthForSmallestKnownToNotFit = width;
172        }
173    }
174
175    if (!keepCountForLargestKnownToFit)
176        keepCountForLargestKnownToFit = 1;
177
178    if (keepCount != keepCountForLargestKnownToFit) {
179        keepCount = keepCountForLargestKnownToFit;
180        truncatedLength = truncateToBuffer(string, length, keepCount, stringBuffer);
181    }
182
183    return String(stringBuffer, truncatedLength);
184}
185
186String StringTruncator::centerTruncate(const String& string, float maxWidth, const Font& font)
187{
188    return truncateString(string, maxWidth, font, centerTruncateToBuffer);
189}
190
191String StringTruncator::rightTruncate(const String& string, float maxWidth, const Font& font)
192{
193    return truncateString(string, maxWidth, font, rightTruncateToBuffer);
194}
195
196float StringTruncator::width(const String& string, const Font& font)
197{
198    return stringWidth(font, string);
199}
200
201} // namespace blink
202