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