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