src/ui/gfx/text_elider.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4 //
   5 // This file implements utility functions for eliding and formatting UI text.
   6 //
   7 // Note that several of the functions declared in text_elider.h are implemented
   8 // in this file using helper classes in an unnamed namespace.
   9
  10 #include "ui/gfx/text_elider.h"
  11
  12 #include <string>
  13 #include <vector>
  14
  15 #include "base/files/file_path.h"
  16 #include "base/i18n/break_iterator.h"
  17 #include "base/i18n/char_iterator.h"
  18 #include "base/i18n/rtl.h"
  19 #include "base/memory/scoped_ptr.h"
  20 #include "base/strings/string_split.h"
  21 #include "base/strings/string_util.h"
  22 #include "base/strings/sys_string_conversions.h"
  23 #include "base/strings/utf_string_conversions.h"
  24 #include "third_party/icu/source/common/unicode/rbbi.h"
  25 #include "third_party/icu/source/common/unicode/uloc.h"
  26 #include "ui/gfx/font_list.h"
  27 #include "ui/gfx/text_utils.h"
  28
  29 using base::ASCIIToUTF16;
  30 using base::UTF8ToUTF16;
  31 using base::WideToUTF16;
  32
  33 namespace gfx {
  34
  35 // U+2026 in utf8
  36 const char kEllipsis[] = "\xE2\x80\xA6";
  37 const base::char16 kEllipsisUTF16[] = { 0x2026, 0 };
  38 const base::char16 kForwardSlash = '/';
  39
  40 StringSlicer::StringSlicer(const base::string16& text,
  41              const base::string16& ellipsis,
  42              bool elide_in_middle,
  43              bool elide_at_beginning)
  44     : text_(text),
  45       ellipsis_(ellipsis),
  46       elide_in_middle_(elide_in_middle),
  47       elide_at_beginning_(elide_at_beginning) {
  48 }
  49
  50 base::string16 StringSlicer::CutString(size_t length, bool insert_ellipsis) {
  51   const base::string16 ellipsis_text = insert_ellipsis ? ellipsis_
  52                                                        : base::string16();
  53
  54   if (elide_at_beginning_)
  55     return ellipsis_text +
  56            text_.substr(FindValidBoundaryBefore(text_.length() - length));
  57
  58   if (!elide_in_middle_)
  59     return text_.substr(0, FindValidBoundaryBefore(length)) + ellipsis_text;
  60
  61   // We put the extra character, if any, before the cut.
  62   const size_t half_length = length / 2;
  63   const size_t prefix_length = FindValidBoundaryBefore(length - half_length);
  64   const size_t suffix_start_guess = text_.length() - half_length;
  65   const size_t suffix_start = FindValidBoundaryAfter(suffix_start_guess);
  66   const size_t suffix_length =
  67       half_length - (suffix_start_guess - suffix_start);
  68   return text_.substr(0, prefix_length) + ellipsis_text +
  69          text_.substr(suffix_start, suffix_length);
  70 }
  71
  72 size_t StringSlicer::FindValidBoundaryBefore(size_t index) const {
  73   DCHECK_LE(index, text_.length());
  74   if (index != text_.length())
  75     U16_SET_CP_START(text_.data(), 0, index);
  76   return index;
  77 }
  78
  79 size_t StringSlicer::FindValidBoundaryAfter(size_t index) const {
  80   DCHECK_LE(index, text_.length());
  81   if (index != text_.length())
  82     U16_SET_CP_LIMIT(text_.data(), 0, index, text_.length());
  83   return index;
  84 }
  85
  86 base::string16 ElideEmail(const base::string16& email,
  87                           const FontList& font_list,
  88                           float available_pixel_width) {
  89   if (GetStringWidthF(email, font_list) <= available_pixel_width)
  90     return email;
  91
  92   // Split the email into its local-part (username) and domain-part. The email
  93   // spec technically allows for @ symbols in the local-part (username) of the
  94   // email under some special requirements. It is guaranteed that there is no @
  95   // symbol in the domain part of the email however so splitting at the last @
  96   // symbol is safe.
  97   const size_t split_index = email.find_last_of('@');
  98   DCHECK_NE(split_index, base::string16::npos);
  99   base::string16 username = email.substr(0, split_index);
 100   base::string16 domain = email.substr(split_index + 1);
 101   DCHECK(!username.empty());
 102   DCHECK(!domain.empty());
 103
 104   // Subtract the @ symbol from the available width as it is mandatory.
 105   const base::string16 kAtSignUTF16 = ASCIIToUTF16("@");
 106   available_pixel_width -= GetStringWidthF(kAtSignUTF16, font_list);
 107
 108   // Check whether eliding the domain is necessary: if eliding the username
 109   // is sufficient, the domain will not be elided.
 110   const float full_username_width = GetStringWidthF(username, font_list);
 111   const float available_domain_width =
 112       available_pixel_width -
 113       std::min(full_username_width,
 114                GetStringWidthF(username.substr(0, 1) + kEllipsisUTF16,
 115                                font_list));
 116   if (GetStringWidthF(domain, font_list) > available_domain_width) {
 117     // Elide the domain so that it only takes half of the available width.
 118     // Should the username not need all the width available in its half, the
 119     // domain will occupy the leftover width.
 120     // If |desired_domain_width| is greater than |available_domain_width|: the
 121     // minimal username elision allowed by the specifications will not fit; thus
 122     // |desired_domain_width| must be <= |available_domain_width| at all cost.
 123     const float desired_domain_width =
 124         std::min(available_domain_width,
 125                  std::max(available_pixel_width - full_username_width,
 126                           available_pixel_width / 2));
 127     domain = ElideText(domain, font_list, desired_domain_width,
 128                        ELIDE_IN_MIDDLE);
 129     // Failing to elide the domain such that at least one character remains
 130     // (other than the ellipsis itself) remains: return a single ellipsis.
 131     if (domain.length() <= 1U)
 132       return base::string16(kEllipsisUTF16);
 133   }
 134
 135   // Fit the username in the remaining width (at this point the elided username
 136   // is guaranteed to fit with at least one character remaining given all the
 137   // precautions taken earlier).
 138   available_pixel_width -= GetStringWidthF(domain, font_list);
 139   username = ElideText(username, font_list, available_pixel_width,
 140                        ELIDE_AT_END);
 141
 142   return username + kAtSignUTF16 + domain;
 143 }
 144
 145 base::string16 ElideFilename(const base::FilePath& filename,
 146                              const FontList& font_list,
 147                              float available_pixel_width) {
 148 #if defined(OS_WIN)
 149   base::string16 filename_utf16 = filename.value();
 150   base::string16 extension = filename.Extension();
 151   base::string16 rootname = filename.BaseName().RemoveExtension().value();
 152 #elif defined(OS_POSIX)
 153   base::string16 filename_utf16 = WideToUTF16(base::SysNativeMBToWide(
 154       filename.value()));
 155   base::string16 extension = WideToUTF16(base::SysNativeMBToWide(
 156       filename.Extension()));
 157   base::string16 rootname = WideToUTF16(base::SysNativeMBToWide(
 158       filename.BaseName().RemoveExtension().value()));
 159 #endif
 160
 161   const float full_width = GetStringWidthF(filename_utf16, font_list);
 162   if (full_width <= available_pixel_width)
 163     return base::i18n::GetDisplayStringInLTRDirectionality(filename_utf16);
 164
 165   if (rootname.empty() || extension.empty()) {
 166     const base::string16 elided_name = ElideText(filename_utf16, font_list,
 167                                            available_pixel_width, ELIDE_AT_END);
 168     return base::i18n::GetDisplayStringInLTRDirectionality(elided_name);
 169   }
 170
 171   const float ext_width = GetStringWidthF(extension, font_list);
 172   const float root_width = GetStringWidthF(rootname, font_list);
 173
 174   // We may have trimmed the path.
 175   if (root_width + ext_width <= available_pixel_width) {
 176     const base::string16 elided_name = rootname + extension;
 177     return base::i18n::GetDisplayStringInLTRDirectionality(elided_name);
 178   }
 179
 180   if (ext_width >= available_pixel_width) {
 181     const base::string16 elided_name = ElideText(
 182         rootname + extension, font_list, available_pixel_width,
 183         ELIDE_IN_MIDDLE);
 184     return base::i18n::GetDisplayStringInLTRDirectionality(elided_name);
 185   }
 186
 187   float available_root_width = available_pixel_width - ext_width;
 188   base::string16 elided_name =
 189       ElideText(rootname, font_list, available_root_width, ELIDE_AT_END);
 190   elided_name += extension;
 191   return base::i18n::GetDisplayStringInLTRDirectionality(elided_name);
 192 }
 193
 194 base::string16 ElideText(const base::string16& text,
 195                          const FontList& font_list,
 196                          float available_pixel_width,
 197                          ElideBehavior elide_behavior) {
 198   if (text.empty())
 199     return text;
 200
 201   const float current_text_pixel_width = GetStringWidthF(text, font_list);
 202   const bool elide_in_middle = (elide_behavior == ELIDE_IN_MIDDLE);
 203   const bool elide_at_beginning = (elide_behavior == ELIDE_AT_BEGINNING);
 204   const bool insert_ellipsis = (elide_behavior != TRUNCATE_AT_END);
 205
 206   const base::string16 ellipsis = base::string16(kEllipsisUTF16);
 207   StringSlicer slicer(text, ellipsis, elide_in_middle, elide_at_beginning);
 208
 209   // Pango will return 0 width for absurdly long strings. Cut the string in
 210   // half and try again.
 211   // This is caused by an int overflow in Pango (specifically, in
 212   // pango_glyph_string_extents_range). It's actually more subtle than just
 213   // returning 0, since on super absurdly long strings, the int can wrap and
 214   // return positive numbers again. Detecting that is probably not worth it
 215   // (eliding way too much from a ridiculous string is probably still
 216   // ridiculous), but we should check other widths for bogus values as well.
 217   if (current_text_pixel_width <= 0 && !text.empty()) {
 218     const base::string16 cut =
 219       slicer.CutString(text.length() / 2, insert_ellipsis);
 220     return ElideText(cut, font_list, available_pixel_width, elide_behavior);
 221   }
 222
 223   if (current_text_pixel_width <= available_pixel_width)
 224     return text;
 225
 226   if (insert_ellipsis &&
 227       GetStringWidthF(ellipsis, font_list) > available_pixel_width)
 228     return base::string16();
 229
 230   // Use binary search to compute the elided text.
 231   size_t lo = 0;
 232   size_t hi = text.length() - 1;
 233   size_t guess;
 234   for (guess = (lo + hi) / 2; lo <= hi; guess = (lo + hi) / 2) {
 235     // We check the width of the whole desired string at once to ensure we
 236     // handle kerning/ligatures/etc. correctly.
 237     // TODO(skanuj) : Handle directionality of ellipsis based on adjacent
 238     // characters.  See crbug.com/327963.
 239     const base::string16 cut = slicer.CutString(guess, insert_ellipsis);
 240     const float guess_width = GetStringWidthF(cut, font_list);
 241     if (guess_width == available_pixel_width)
 242       break;
 243     if (guess_width > available_pixel_width) {
 244       hi = guess - 1;
 245       // Move back if we are on loop terminating condition, and guess is wider
 246       // than available.
 247       if (hi < lo)
 248         lo = hi;
 249     } else {
 250       lo = guess + 1;
 251     }
 252   }
 253
 254   return slicer.CutString(guess, insert_ellipsis);
 255 }
 256
 257 bool ElideString(const base::string16& input, int max_len,
 258                  base::string16* output) {
 259   DCHECK_GE(max_len, 0);
 260   if (static_cast<int>(input.length()) <= max_len) {
 261     output->assign(input);
 262     return false;
 263   }
 264
 265   switch (max_len) {
 266     case 0:
 267       output->clear();
 268       break;
 269     case 1:
 270       output->assign(input.substr(0, 1));
 271       break;
 272     case 2:
 273       output->assign(input.substr(0, 2));
 274       break;
 275     case 3:
 276       output->assign(input.substr(0, 1) + ASCIIToUTF16(".") +
 277                      input.substr(input.length() - 1));
 278       break;
 279     case 4:
 280       output->assign(input.substr(0, 1) + ASCIIToUTF16("..") +
 281                      input.substr(input.length() - 1));
 282       break;
 283     default: {
 284       int rstr_len = (max_len - 3) / 2;
 285       int lstr_len = rstr_len + ((max_len - 3) % 2);
 286       output->assign(input.substr(0, lstr_len) + ASCIIToUTF16("...") +
 287                      input.substr(input.length() - rstr_len));
 288       break;
 289     }
 290   }
 291
 292   return true;
 293 }
 294
 295 namespace {
 296
 297 // Internal class used to track progress of a rectangular string elide
 298 // operation.  Exists so the top-level ElideRectangleString() function
 299 // can be broken into smaller methods sharing this state.
 300 class RectangleString {
 301  public:
 302   RectangleString(size_t max_rows, size_t max_cols,
 303                   bool strict, base::string16 *output)
 304       : max_rows_(max_rows),
 305         max_cols_(max_cols),
 306         current_row_(0),
 307         current_col_(0),
 308         strict_(strict),
 309         suppressed_(false),
 310         output_(output) {}
 311
 312   // Perform deferred initializations following creation.  Must be called
 313   // before any input can be added via AddString().
 314   void Init() { output_->clear(); }
 315
 316   // Add an input string, reformatting to fit the desired dimensions.
 317   // AddString() may be called multiple times to concatenate together
 318   // multiple strings into the region (the current caller doesn't do
 319   // this, however).
 320   void AddString(const base::string16& input);
 321
 322   // Perform any deferred output processing.  Must be called after the
 323   // last AddString() call has occurred.
 324   bool Finalize();
 325
 326  private:
 327   // Add a line to the rectangular region at the current position,
 328   // either by itself or by breaking it into words.
 329   void AddLine(const base::string16& line);
 330
 331   // Add a word to the rectangular region at the current position,
 332   // either by itself or by breaking it into characters.
 333   void AddWord(const base::string16& word);
 334
 335   // Add text to the output string if the rectangular boundaries
 336   // have not been exceeded, advancing the current position.
 337   void Append(const base::string16& string);
 338
 339   // Set the current position to the beginning of the next line.  If
 340   // |output| is true, add a newline to the output string if the rectangular
 341   // boundaries have not been exceeded.  If |output| is false, we assume
 342   // some other mechanism will (likely) do similar breaking after the fact.
 343   void NewLine(bool output);
 344
 345   // Maximum number of rows allowed in the output string.
 346   size_t max_rows_;
 347
 348   // Maximum number of characters allowed in the output string.
 349   size_t max_cols_;
 350
 351   // Current row position, always incremented and may exceed max_rows_
 352   // when the input can not fit in the region.  We stop appending to
 353   // the output string, however, when this condition occurs.  In the
 354   // future, we may want to expose this value to allow the caller to
 355   // determine how many rows would actually be required to hold the
 356   // formatted string.
 357   size_t current_row_;
 358
 359   // Current character position, should never exceed max_cols_.
 360   size_t current_col_;
 361
 362   // True when we do whitespace to newline conversions ourselves.
 363   bool strict_;
 364
 365   // True when some of the input has been truncated.
 366   bool suppressed_;
 367
 368   // String onto which the output is accumulated.
 369   base::string16* output_;
 370
 371   DISALLOW_COPY_AND_ASSIGN(RectangleString);
 372 };
 373
 374 void RectangleString::AddString(const base::string16& input) {
 375   base::i18n::BreakIterator lines(input,
 376                                   base::i18n::BreakIterator::BREAK_NEWLINE);
 377   if (lines.Init()) {
 378     while (lines.Advance())
 379       AddLine(lines.GetString());
 380   } else {
 381     NOTREACHED() << "BreakIterator (lines) init failed";
 382   }
 383 }
 384
 385 bool RectangleString::Finalize() {
 386   if (suppressed_) {
 387     output_->append(ASCIIToUTF16("..."));
 388     return true;
 389   }
 390   return false;
 391 }
 392
 393 void RectangleString::AddLine(const base::string16& line) {
 394   if (line.length() < max_cols_) {
 395     Append(line);
 396   } else {
 397     base::i18n::BreakIterator words(line,
 398                                     base::i18n::BreakIterator::BREAK_SPACE);
 399     if (words.Init()) {
 400       while (words.Advance())
 401         AddWord(words.GetString());
 402     } else {
 403       NOTREACHED() << "BreakIterator (words) init failed";
 404     }
 405   }
 406   // Account for naturally-occuring newlines.
 407   ++current_row_;
 408   current_col_ = 0;
 409 }
 410
 411 void RectangleString::AddWord(const base::string16& word) {
 412   if (word.length() < max_cols_) {
 413     // Word can be made to fit, no need to fragment it.
 414     if (current_col_ + word.length() >= max_cols_)
 415       NewLine(strict_);
 416     Append(word);
 417   } else {
 418     // Word is so big that it must be fragmented.
 419     int array_start = 0;
 420     int char_start = 0;
 421     base::i18n::UTF16CharIterator chars(&word);
 422     while (!chars.end()) {
 423       // When boundary is hit, add as much as will fit on this line.
 424       if (current_col_ + (chars.char_pos() - char_start) >= max_cols_) {
 425         Append(word.substr(array_start, chars.array_pos() - array_start));
 426         NewLine(true);
 427         array_start = chars.array_pos();
 428         char_start = chars.char_pos();
 429       }
 430       chars.Advance();
 431     }
 432     // Add the last remaining fragment, if any.
 433     if (array_start != chars.array_pos())
 434       Append(word.substr(array_start, chars.array_pos() - array_start));
 435   }
 436 }
 437
 438 void RectangleString::Append(const base::string16& string) {
 439   if (current_row_ < max_rows_)
 440     output_->append(string);
 441   else
 442     suppressed_ = true;
 443   current_col_ += string.length();
 444 }
 445
 446 void RectangleString::NewLine(bool output) {
 447   if (current_row_ < max_rows_) {
 448     if (output)
 449       output_->append(ASCIIToUTF16("\n"));
 450   } else {
 451     suppressed_ = true;
 452   }
 453   ++current_row_;
 454   current_col_ = 0;
 455 }
 456
 457 // Internal class used to track progress of a rectangular text elide
 458 // operation.  Exists so the top-level ElideRectangleText() function
 459 // can be broken into smaller methods sharing this state.
 460 class RectangleText {
 461  public:
 462   RectangleText(const FontList& font_list,
 463                 float available_pixel_width,
 464                 int available_pixel_height,
 465                 WordWrapBehavior wrap_behavior,
 466                 std::vector<base::string16>* lines)
 467       : font_list_(font_list),
 468         line_height_(font_list.GetHeight()),
 469         available_pixel_width_(available_pixel_width),
 470         available_pixel_height_(available_pixel_height),
 471         wrap_behavior_(wrap_behavior),
 472         current_width_(0),
 473         current_height_(0),
 474         last_line_ended_in_lf_(false),
 475         lines_(lines),
 476         insufficient_width_(false),
 477         insufficient_height_(false) {}
 478
 479   // Perform deferred initializions following creation.  Must be called
 480   // before any input can be added via AddString().
 481   void Init() { lines_->clear(); }
 482
 483   // Add an input string, reformatting to fit the desired dimensions.
 484   // AddString() may be called multiple times to concatenate together
 485   // multiple strings into the region (the current caller doesn't do
 486   // this, however).
 487   void AddString(const base::string16& input);
 488
 489   // Perform any deferred output processing.  Must be called after the last
 490   // AddString() call has occured. Returns a combination of
 491   // |ReformattingResultFlags| indicating whether the given width or height was
 492   // insufficient, leading to elision or truncation.
 493   int Finalize();
 494
 495  private:
 496   // Add a line to the rectangular region at the current position,
 497   // either by itself or by breaking it into words.
 498   void AddLine(const base::string16& line);
 499
 500   // Wrap the specified word across multiple lines.
 501   int WrapWord(const base::string16& word);
 502
 503   // Add a long word - wrapping, eliding or truncating per the wrap behavior.
 504   int AddWordOverflow(const base::string16& word);
 505
 506   // Add a word to the rectangluar region at the current position.
 507   int AddWord(const base::string16& word);
 508
 509   // Append the specified |text| to the current output line, incrementing the
 510   // running width by the specified amount. This is an optimization over
 511   // |AddToCurrentLine()| when |text_width| is already known.
 512   void AddToCurrentLineWithWidth(const base::string16& text, float text_width);
 513
 514   // Append the specified |text| to the current output line.
 515   void AddToCurrentLine(const base::string16& text);
 516
 517   // Set the current position to the beginning of the next line.
 518   bool NewLine();
 519
 520   // The font list used for measuring text width.
 521   const FontList& font_list_;
 522
 523   // The height of each line of text.
 524   const int line_height_;
 525
 526   // The number of pixels of available width in the rectangle.
 527   const float available_pixel_width_;
 528
 529   // The number of pixels of available height in the rectangle.
 530   const int available_pixel_height_;
 531
 532   // The wrap behavior for words that are too long to fit on a single line.
 533   const WordWrapBehavior wrap_behavior_;
 534
 535   // The current running width.
 536   float current_width_;
 537
 538   // The current running height.
 539   int current_height_;
 540
 541   // The current line of text.
 542   base::string16 current_line_;
 543
 544   // Indicates whether the last line ended with \n.
 545   bool last_line_ended_in_lf_;
 546
 547   // The output vector of lines.
 548   std::vector<base::string16>* lines_;
 549
 550   // Indicates whether a word was so long that it had to be truncated or elided
 551   // to fit the available width.
 552   bool insufficient_width_;
 553
 554   // Indicates whether there were too many lines for the available height.
 555   bool insufficient_height_;
 556
 557   DISALLOW_COPY_AND_ASSIGN(RectangleText);
 558 };
 559
 560 void RectangleText::AddString(const base::string16& input) {
 561   base::i18n::BreakIterator lines(input,
 562                                   base::i18n::BreakIterator::BREAK_NEWLINE);
 563   if (lines.Init()) {
 564     while (!insufficient_height_ && lines.Advance()) {
 565       base::string16 line = lines.GetString();
 566       // The BREAK_NEWLINE iterator will keep the trailing newline character,
 567       // except in the case of the last line, which may not have one.  Remove
 568       // the newline character, if it exists.
 569       last_line_ended_in_lf_ = !line.empty() && line[line.length() - 1] == '\n';
 570       if (last_line_ended_in_lf_)
 571         line.resize(line.length() - 1);
 572       AddLine(line);
 573     }
 574   } else {
 575     NOTREACHED() << "BreakIterator (lines) init failed";
 576   }
 577 }
 578
 579 int RectangleText::Finalize() {
 580   // Remove trailing whitespace from the last line or remove the last line
 581   // completely, if it's just whitespace.
 582   if (!insufficient_height_ && !lines_->empty()) {
 583     TrimWhitespace(lines_->back(), TRIM_TRAILING, &lines_->back());
 584     if (lines_->back().empty() && !last_line_ended_in_lf_)
 585       lines_->pop_back();
 586   }
 587   if (last_line_ended_in_lf_)
 588     lines_->push_back(base::string16());
 589   return (insufficient_width_ ? INSUFFICIENT_SPACE_HORIZONTAL : 0) |
 590          (insufficient_height_ ? INSUFFICIENT_SPACE_VERTICAL : 0);
 591 }
 592
 593 void RectangleText::AddLine(const base::string16& line) {
 594   const float line_width = GetStringWidthF(line, font_list_);
 595   if (line_width <= available_pixel_width_) {
 596     AddToCurrentLineWithWidth(line, line_width);
 597   } else {
 598     // Iterate over positions that are valid to break the line at. In general,
 599     // these are word boundaries but after any punctuation following the word.
 600     base::i18n::BreakIterator words(line,
 601                                     base::i18n::BreakIterator::BREAK_LINE);
 602     if (words.Init()) {
 603       while (words.Advance()) {
 604         const bool truncate = !current_line_.empty();
 605         const base::string16& word = words.GetString();
 606         const int lines_added = AddWord(word);
 607         if (lines_added) {
 608           if (truncate) {
 609             // Trim trailing whitespace from the line that was added.
 610             const int line = lines_->size() - lines_added;
 611             TrimWhitespace(lines_->at(line), TRIM_TRAILING, &lines_->at(line));
 612           }
 613           if (ContainsOnlyWhitespace(word)) {
 614             // Skip the first space if the previous line was carried over.
 615             current_width_ = 0;
 616             current_line_.clear();
 617           }
 618         }
 619       }
 620     } else {
 621       NOTREACHED() << "BreakIterator (words) init failed";
 622     }
 623   }
 624   // Account for naturally-occuring newlines.
 625   NewLine();
 626 }
 627
 628 int RectangleText::WrapWord(const base::string16& word) {
 629   // Word is so wide that it must be fragmented.
 630   base::string16 text = word;
 631   int lines_added = 0;
 632   bool first_fragment = true;
 633   while (!insufficient_height_ && !text.empty()) {
 634     base::string16 fragment =
 635         ElideText(text, font_list_, available_pixel_width_,
 636                   TRUNCATE_AT_END);
 637     // At least one character has to be added at every line, even if the
 638     // available space is too small.
 639     if(fragment.empty())
 640       fragment = text.substr(0, 1);
 641     if (!first_fragment && NewLine())
 642       lines_added++;
 643     AddToCurrentLine(fragment);
 644     text = text.substr(fragment.length());
 645     first_fragment = false;
 646   }
 647   return lines_added;
 648 }
 649
 650 int RectangleText::AddWordOverflow(const base::string16& word) {
 651   int lines_added = 0;
 652
 653   // Unless this is the very first word, put it on a new line.
 654   if (!current_line_.empty()) {
 655     if (!NewLine())
 656       return 0;
 657     lines_added++;
 658   }
 659
 660   if (wrap_behavior_ == IGNORE_LONG_WORDS) {
 661     current_line_ = word;
 662     current_width_ = available_pixel_width_;
 663   } else if (wrap_behavior_ == WRAP_LONG_WORDS) {
 664     lines_added += WrapWord(word);
 665   } else {
 666     const ElideBehavior elide_behavior =
 667         (wrap_behavior_ == ELIDE_LONG_WORDS ? ELIDE_AT_END : TRUNCATE_AT_END);
 668     const base::string16 elided_word =
 669         ElideText(word, font_list_, available_pixel_width_, elide_behavior);
 670     AddToCurrentLine(elided_word);
 671     insufficient_width_ = true;
 672   }
 673
 674   return lines_added;
 675 }
 676
 677 int RectangleText::AddWord(const base::string16& word) {
 678   int lines_added = 0;
 679   base::string16 trimmed;
 680   TrimWhitespace(word, TRIM_TRAILING, &trimmed);
 681   const float trimmed_width = GetStringWidthF(trimmed, font_list_);
 682   if (trimmed_width <= available_pixel_width_) {
 683     // Word can be made to fit, no need to fragment it.
 684     if ((current_width_ + trimmed_width > available_pixel_width_) && NewLine())
 685       lines_added++;
 686     // Append the non-trimmed word, in case more words are added after.
 687     AddToCurrentLine(word);
 688   } else {
 689     lines_added = AddWordOverflow(wrap_behavior_ == IGNORE_LONG_WORDS ?
 690                                   trimmed : word);
 691   }
 692   return lines_added;
 693 }
 694
 695 void RectangleText::AddToCurrentLine(const base::string16& text) {
 696   AddToCurrentLineWithWidth(text, GetStringWidthF(text, font_list_));
 697 }
 698
 699 void RectangleText::AddToCurrentLineWithWidth(const base::string16& text,
 700                                               float text_width) {
 701   if (current_height_ >= available_pixel_height_) {
 702     insufficient_height_ = true;
 703     return;
 704   }
 705   current_line_.append(text);
 706   current_width_ += text_width;
 707 }
 708
 709 bool RectangleText::NewLine() {
 710   bool line_added = false;
 711   if (current_height_ < available_pixel_height_) {
 712     lines_->push_back(current_line_);
 713     current_line_.clear();
 714     line_added = true;
 715   } else {
 716     insufficient_height_ = true;
 717   }
 718   current_height_ += line_height_;
 719   current_width_ = 0;
 720   return line_added;
 721 }
 722
 723 }  // namespace
 724
 725 bool ElideRectangleString(const base::string16& input, size_t max_rows,
 726                           size_t max_cols, bool strict,
 727                           base::string16* output) {
 728   RectangleString rect(max_rows, max_cols, strict, output);
 729   rect.Init();
 730   rect.AddString(input);
 731   return rect.Finalize();
 732 }
 733
 734 int ElideRectangleText(const base::string16& input,
 735                        const FontList& font_list,
 736                        float available_pixel_width,
 737                        int available_pixel_height,
 738                        WordWrapBehavior wrap_behavior,
 739                        std::vector<base::string16>* lines) {
 740   RectangleText rect(font_list,
 741                      available_pixel_width,
 742                      available_pixel_height,
 743                      wrap_behavior,
 744                      lines);
 745   rect.Init();
 746   rect.AddString(input);
 747   return rect.Finalize();
 748 }
 749
 750 base::string16 TruncateString(const base::string16& string, size_t length) {
 751   if (string.size() <= length)
 752     // String fits, return it.
 753     return string;
 754
 755   if (length == 0)
 756     // No room for the elide string, return an empty string.
 757     return base::string16();
 758
 759   size_t max = length - 1;
 760
 761   // Added to the end of strings that are too big.
 762   static const base::char16 kElideString[] = { 0x2026, 0 };
 763
 764   if (max == 0)
 765     // Just enough room for the elide string.
 766     return kElideString;
 767
 768   // Use a line iterator to find the first boundary.
 769   UErrorCode status = U_ZERO_ERROR;
 770   scoped_ptr<icu::RuleBasedBreakIterator> bi(
 771       static_cast<icu::RuleBasedBreakIterator*>(
 772           icu::RuleBasedBreakIterator::createLineInstance(
 773               icu::Locale::getDefault(), status)));
 774   if (U_FAILURE(status))
 775     return string.substr(0, max) + kElideString;
 776   bi->setText(string.c_str());
 777   int32_t index = bi->preceding(static_cast<int32_t>(max));
 778   if (index == icu::BreakIterator::DONE) {
 779     index = static_cast<int32_t>(max);
 780   } else {
 781     // Found a valid break (may be the beginning of the string). Now use
 782     // a character iterator to find the previous non-whitespace character.
 783     icu::StringCharacterIterator char_iterator(string.c_str());
 784     if (index == 0) {
 785       // No valid line breaks. Start at the end again. This ensures we break
 786       // on a valid character boundary.
 787       index = static_cast<int32_t>(max);
 788     }
 789     char_iterator.setIndex(index);
 790     while (char_iterator.hasPrevious()) {
 791       char_iterator.previous();
 792       if (!(u_isspace(char_iterator.current()) ||
 793             u_charType(char_iterator.current()) == U_CONTROL_CHAR ||
 794             u_charType(char_iterator.current()) == U_NON_SPACING_MARK)) {
 795         // Not a whitespace character. Advance the iterator so that we
 796         // include the current character in the truncated string.
 797         char_iterator.next();
 798         break;
 799       }
 800     }
 801     if (char_iterator.hasPrevious()) {
 802       // Found a valid break point.
 803       index = char_iterator.getIndex();
 804     } else {
 805       // String has leading whitespace, return the elide string.
 806       return kElideString;
 807     }
 808   }
 809   return string.substr(0, index) + kElideString;
 810 }
 811
 812 }  // namespace gfx