Windows implementation of multiline RenderText

ui/gfx/render_text_win.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/gfx/render_text_win.h"
 
 #include <algorithm>
 
 #include "base/i18n/break_iterator.h"
 #include "base/i18n/rtl.h"
@@ skipping 136 matching lines @@
   } else {
     result = ui::Range(run.logical_clusters[run_range.start()],
         run_range.end() < run.range.length() ?
             run.logical_clusters[run_range.end()] : run.glyph_count);
   }
   DCHECK(!result.is_reversed());
   DCHECK(ui::Range(0, run.glyph_count).Contains(result));
   return result;
 }
 
+struct BreakRunResults {
+  // If |overflowed|, holds the width of [start_char, overflow_pos].
+  // Otherwise, holds the width of [start_char, run.range.end()).
+  int width;
+
+  // Index of the first character that doesn't fit the given width.
+  size_t overflow_pos;
+
+  // Width of the character at |overflow_pos|.
+  int char_rollback_width;
+
+  // Index of the last word break before |overflow_pos|.
+  size_t word_rollback_pos;
+
+  // Width of [word_rollback_pos, overflow_pos].
+  int word_rollback_width;
+};
+
+// Starting from |start_char|, finds the first character that doesn't fit the
+// given |available_width|. If |available_width| is reached, returns true and
+// fills all the fields in |results|. Otherwise returns false and only fills
+// |results->width|.
+bool BreakRunAtWidth(const internal::TextRun& run,
+                     const BreakList<size_t>& breaks,
+                     size_t start_char,
+                     int available_width,
+                     BreakRunResults* results) {
+  DCHECK(run.range.Contains(ui::Range(start_char)));
+  BreakList<size_t>::const_iterator current_word = breaks.GetBreak(start_char);
+  BreakList<size_t>::const_iterator next_word = current_word + 1;
+  // x distance from |current_word|.
+  int current_word_x = 0;
+  // x distance from |start_char|.
+  int x = 0;
+
+  for (size_t i = start_char; i < run.range.end(); ++i) {
+    if (next_word != breaks.breaks().end() && i >= next_word->first) {
+      current_word = next_word++;
+      current_word_x = 0;
+    }
+
+    ui::Range glyphs = CharRangeToGlyphRange(run, ui::Range(i, i + 1));
+    int char_width = 0;
+    for (size_t j = glyphs.start(); j < glyphs.end(); ++j)
+      char_width += run.advance_widths[j];
+
+    x += char_width;
+    current_word_x += char_width;
+
+    if (x > available_width) {
+      results->overflow_pos = i;
+      results->width = x;
+      results->char_rollback_width = char_width;
+      results->word_rollback_pos = std::max(current_word->first, start_char);
+      results->word_rollback_width = current_word_x;
+      return true;
+    }
+  }
+
+  results->width = x;
+  return false;
+}
+
 }  // namespace
 
 namespace internal {
 
 TextRun::TextRun()
   : font_style(0),
     strike(false),
     diagonal_strike(false),
     underline(false),
     width(0),
@@ skipping 23 matching lines @@
       run->glyph_count,
       run->logical_clusters.get(),
       run->visible_attributes.get(),
       run->advance_widths.get(),
       &run->script_analysis,
       &x);
   DCHECK(SUCCEEDED(hr));
   return run->preceding_run_widths + x;
 }
 
+struct LineSegmentWin : LineSegment {
+  const internal::TextRun* run;
+};
+
+// Internal class to help break a text into lines.
+class LineBreaker {
+ public:
+  LineBreaker(int max_width, bool multiline, const BreakList<size_t>* words)
+      : max_width_(max_width),
+        multiline_(multiline),
+        words_(words),
+        preceding_line_heights_(0),
+        pos_(0),
+        text_x_(0),
+        line_x_(0),
+        current_pos_(0),
+        current_width_(0) {
+    SkipLine();
+  }
+
+  // Breaks the given |runs| into |lines|. Should be called at most once for
+  // each instance. If |multiline| is false, doesn't do any breaking and fills
+  // |lines| with a single Line.
+  void AddRun(const internal::TextRun& run) {
+    ResetPos(run.range.start());
+    int width = run.width;
+    if (multiline_ && line_x_ + width > max_width_)
+      width = BreakRun(run);
+    // Remaining part of the run fits the line, add it as well.
+    Advance(run.range.end(), width);
+    CommitSegment(run);
+  }
+
+  // Finishes line breaking and outputs the results. Can be called at most once.
+  void Finalize(std::vector<internal::Line>* lines) {
+    DCHECK(!lines_.empty());
+    lines->swap(lines_);
+  }
+
+ private:
+  // Breaks a run into segments of at most |max_width| width, adds the segments,
+  // returns the width of the final segment that fits the current line.
+  int BreakRun(const internal::TextRun& run) {
+    BreakRunResults results;
+    memset(&results, 0, sizeof(results));
+
+    // Break the run until it fits the current line.
+    while (BreakRunAtWidth(run, *words_, pos_, max_width_ - line_x_,
+                           &results)) {
+      DCHECK(pos_ < run.range.end());
+      Advance(results.overflow_pos + 1, results.width);
+      // First, try rolling back one word to move it to the next line. If
+      // it's not possible, roll back one character. If neither of these
+      // could be done, don't do any rollback since each line must have at
+      // least one character.
+      if (line_x_ > 0 || results.word_rollback_width < results.width)
+        Rollback(results.word_rollback_pos, results.word_rollback_width);
+      else if (line_x_ > 0 || results.char_rollback_width < results.width)
+        Rollback(results.overflow_pos, results.char_rollback_width);
+      CommitSegment(run);
+      SkipLine();
+    }
+
+    return results.width;
+  }
+
+  // RTL runs are broken in logical order but displayed in visual order. To find
+  // the text-space coordinate (where it would fall in a single-line text)
+  // |x_pos| of RTL segments, segment widths are applied in reverse order.
+  // e.g. {[5, 10], [10, 40]} will become {[35, 40], [5, 35]}.
+  void PopRtl() {
+    if (rtl_segments_.empty())
+      return;
+    int x = rtl_segments_[0]->x_pos.start();
+    for (size_t i = rtl_segments_.size(); i > 0; --i) {
+      LineSegment* segment = rtl_segments_[i - 1];
+      segment->x_pos = ui::Range(x, x + segment->x_pos.length());
+      x += segment->x_pos.length();
+    }
+    rtl_segments_.clear();
+  }
+
+  void ResetPos(size_t new_pos) {
+    pos_ = new_pos;
+    current_pos_ = new_pos;
+    current_width_ = 0;
+  }
+
+  void Advance(size_t new_pos, int amount) {
+    current_pos_ = new_pos;
+    current_width_ += amount;
+  }
+
+  void Rollback(size_t new_pos, int amount) {
+    Advance(new_pos, -amount);
+  }
+
+  void SkipLine() {
+    if (!lines_.empty())
+      preceding_line_heights_ += lines_.back().height;
+    line_x_ = 0;
+    lines_.push_back(internal::Line());
+  }
+
+  void CommitSegment(const internal::TextRun& run) {
+    if (pos_ == current_pos_) {
+      DCHECK(current_width_ == 0);
+      return;
+    }
+    internal::LineSegmentWin* segment = new internal::LineSegmentWin;
+    segment->run = &run;
+    segment->char_pos = ui::Range(pos_, current_pos_);
+    segment->x_pos = ui::Range(text_x_, text_x_ + current_width_);
+    lines_.back().segments.push_back(segment);
+    lines_.back().width += segment->x_pos.length();
+    lines_.back().height = std::max(lines_.back().height,
+                                    segment->run->font.GetHeight());
+    lines_.back().baseline = std::max(lines_.back().baseline,
+                                      segment->run->font.GetBaseline());
+    lines_.back().preceding_heights = preceding_line_heights_;
+    if (run.script_analysis.fRTL) {
+      rtl_segments_.push_back(segment);
+      if (current_pos_ == run.range.end())
+        PopRtl();
+    }
+    pos_ = current_pos_;
+    text_x_ += current_width_;
+    line_x_ += current_width_;
+    current_width_ = 0;
+  }
+
+  int max_width_;
+  bool multiline_;
+  const BreakList<size_t>* words_;
+
+  // Stores the resulting lines.
+  std::vector<internal::Line> lines_;
+
+  // Position information of the last committed segment. |pos_| is the segment's
+  // end character position. |text_x_| is the text-space and |line_x| is the

[Alexei Svitkine (slow), 2013/08/13 20:56:32]

Nit: |line_x| -> |line_x_|

[ckocagil, 2013/08/14 11:40:25]

Done.

+  // line-space x coordinate of |pos_|.
+  size_t pos_;
+  int text_x_;
+  int line_x_;
+  int preceding_line_heights_;
+
+  // The end character position and width of the current segment to be
+  // committed. The segment will have the character range [pos_, current_pos_)
+  // and width |current_width_|.
+  size_t current_pos_;
+  int current_width_;
+
+  // Segments to be applied by |PopRtl()|.
+  std::vector<LineSegment*> rtl_segments_;
+
+  DISALLOW_COPY_AND_ASSIGN(LineBreaker);
+};
+
 }  // namespace internal
 
 // static
 HDC RenderTextWin::cached_hdc_ = NULL;
 
 // static
 std::map<std::string, Font> RenderTextWin::successful_substitute_fonts_;
 
 RenderTextWin::RenderTextWin()
     : RenderText(),
       common_baseline_(0),
       needs_layout_(false) {
   set_truncate_length(kMaxUniscribeTextLength);
 
   memset(&script_control_, 0, sizeof(script_control_));
   memset(&script_state_, 0, sizeof(script_state_));
 
   MoveCursorTo(EdgeSelectionModel(CURSOR_LEFT));
 }
 
 RenderTextWin::~RenderTextWin() {
 }
 
 Size RenderTextWin::GetStringSize() {
   EnsureLayout();
   return string_size_;
 }
 
+Size RenderTextWin::GetMultilineTextSize() {
+  EnsureLayout();
+  if (!multiline())
+    return Size(display_rect().width(), string_size_.height());
+  return Size(display_rect().width(),
+              lines().back().preceding_heights + lines().back().height);
+}
+
 int RenderTextWin::GetBaseline() {
   EnsureLayout();
   return common_baseline_;
 }
 
 SelectionModel RenderTextWin::FindCursorPosition(const Point& point) {
   if (text().empty())
     return SelectionModel();
 
   EnsureLayout();
@@ skipping 138 matching lines @@
                    GetGlyphXBoundary(run, layout_index, true));
 }
 
 std::vector<Rect> RenderTextWin::GetSubstringBounds(const ui::Range& range) {
   DCHECK(!needs_layout_);
   DCHECK(ui::Range(0, text().length()).Contains(range));
   ui::Range layout_range(TextIndexToLayoutIndex(range.start()),
                          TextIndexToLayoutIndex(range.end()));
   DCHECK(ui::Range(0, GetLayoutText().length()).Contains(layout_range));
 
-  std::vector<Rect> bounds;
+  std::vector<ui::Range> bounds;
+  std::vector<Rect> rects;
   if (layout_range.is_empty())
-    return bounds;
+    return rects;
 
-  // Add a Rect for each run/selection intersection.
+  // Add a Range for each run/selection intersection.
   // TODO(msw): The bounds should probably not always be leading the range ends.
   for (size_t i = 0; i < runs_.size(); ++i) {
     const internal::TextRun* run = runs_[visual_to_logical_[i]];
     ui::Range intersection = run->range.Intersect(layout_range);
     if (intersection.IsValid()) {
       DCHECK(!intersection.is_reversed());
       ui::Range range_x(GetGlyphXBoundary(run, intersection.start(), false),
                         GetGlyphXBoundary(run, intersection.end(), false));
-      Rect rect(range_x.GetMin(), 0, range_x.length(), run->font.GetHeight());
-      rect.set_origin(ToViewPoint(rect.origin()));
-      // Union this with the last rect if they're adjacent.
-      if (!bounds.empty() && rect.SharesEdgeWith(bounds.back())) {
-        rect.Union(bounds.back());
+      if (range_x.is_empty())
+        continue;
+      range_x = ui::Range(range_x.GetMin(), range_x.GetMax());
+      // Union this with the last range if they're adjacent.
+      DCHECK(bounds.empty() || bounds.back().GetMin() != range_x.GetMax());
+      if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {
+        range_x = ui::Range(bounds.back().GetMin(), range_x.GetMax());
         bounds.pop_back();
       }
-      bounds.push_back(rect);
+      bounds.push_back(range_x);
     }
   }
-  return bounds;
+  for (size_t i = 0; i < bounds.size(); ++i) {
+    std::vector<Rect> current_rects = TextBoundsToViewBounds(bounds[i]);
+    rects.insert(rects.end(), current_rects.begin(), current_rects.end());
+  }
+  return rects;
 }
 
 size_t RenderTextWin::TextIndexToLayoutIndex(size_t index) const {
   DCHECK_LE(index, text().length());
   ptrdiff_t i = obscured() ? ui::UTF16IndexToOffset(text(), 0, index) : index;
   CHECK_GE(i, 0);
   // Clamp layout indices to the length of the text actually used for layout.
   return std::min<size_t>(GetLayoutText().length(), i);
 }
 
@@ skipping 21 matching lines @@
          position < LayoutIndexToTextIndex(GetLayoutText().length()) &&
          GetGlyphBounds(position) != GetGlyphBounds(position - 1);
 }
 
 void RenderTextWin::ResetLayout() {
   // Layout is performed lazily as needed for drawing/metrics.
   needs_layout_ = true;
 }
 
 void RenderTextWin::EnsureLayout() {
-  if (!needs_layout_)
-    return;
-  // TODO(msw): Skip complex processing if ScriptIsComplex returns false.
-  ItemizeLogicalText();
-  if (!runs_.empty())
-    LayoutVisualText();
-  needs_layout_ = false;
+  if (needs_layout_) {
+    // TODO(msw): Skip complex processing if ScriptIsComplex returns false.
+    ItemizeLogicalText();
+    if (!runs_.empty())
+      LayoutVisualText();
+    needs_layout_ = false;
+    std::vector<internal::Line> lines;
+    set_lines(&lines);
+  }
+  // Compute lines if they're not valid. This is separate from the layout steps
+  // above to avoid text layout and shaping when we resize |display_rect_|.
+  if (lines().empty())
+    ComputeLines();
+}
+
+void RenderTextWin::ComputeLines() {
+  DCHECK(!needs_layout_);
+  std::vector<internal::Line> lines;
+  internal::LineBreaker line_breaker(display_rect().width(), multiline(),
+                                     multiline() ? &GetLineBreaks() : 0);
+  for (size_t i = 0; i < runs_.size(); ++i)
+    line_breaker.AddRun(*runs_[visual_to_logical_[i]]);
+  line_breaker.Finalize(&lines);
+  DCHECK(!lines.empty());
+  set_lines(&lines);
 }
 
 void RenderTextWin::DrawVisualText(Canvas* canvas) {
   DCHECK(!needs_layout_);
-
-  // Skia will draw glyphs with respect to the baseline.
-  Vector2d offset(GetTextOffset() + Vector2d(0, common_baseline_));
-
-  SkScalar x = SkIntToScalar(offset.x());
-  SkScalar y = SkIntToScalar(offset.y());
+  DCHECK(!multiline() || !lines().empty());
 
   std::vector<SkPoint> pos;
 
   internal::SkiaTextRenderer renderer(canvas);
   ApplyFadeEffects(&renderer);
   ApplyTextShadows(&renderer);
 
   bool smoothing_enabled;
   bool cleartype_enabled;
   GetCachedFontSmoothingSettings(&smoothing_enabled, &cleartype_enabled);
   // Note that |cleartype_enabled| corresponds to Skia's |enable_lcd_text|.
   renderer.SetFontSmoothingSettings(
       smoothing_enabled, cleartype_enabled && !background_is_transparent());
 
   ApplyCompositionAndSelectionStyles();
 
-  for (size_t i = 0; i < runs_.size(); ++i) {
-    // Get the run specified by the visual-to-logical map.
-    internal::TextRun* run = runs_[visual_to_logical_[i]];
+  for (size_t i = 0; i < lines().size(); ++i) {
+    const internal::Line& line = lines()[i];
+    Vector2d line_offset = GetLineOffset(i);
+    Vector2d text_offset = line_offset + Vector2d(0, line.baseline);
+    int preceding_segment_widths = 0;
 
-    // Skip painting empty runs and runs outside the display rect area.
-    if ((run->glyph_count == 0) || (x >= display_rect().right()) ||
-        (x + run->width <= display_rect().x())) {
-      x += run->width;
+    // Skip painting empty lines or lines outside the display rect area.
+    if (!display_rect().Intersects(Rect(PointAtOffsetFromOrigin(line_offset),
+                                        Size(line.width, line.height))))
       continue;
+
+    for (size_t j = 0; j < line.segments.size(); ++j) {
+      const internal::LineSegmentWin* segment =
+          static_cast<internal::LineSegmentWin*>(line.segments[j]);
+      const int segment_width = segment->x_pos.length();
+      const internal::TextRun* run = segment->run;
+      DCHECK(!segment->char_pos.is_empty());
+      DCHECK(run->range.Contains(segment->char_pos));
+      ui::Range glyphs = CharRangeToGlyphRange(*run, segment->char_pos);
+      if (glyphs.is_empty()) {
+        DCHECK(segment_width == 0);
+        continue;
+      }
+      // Skip painting segments outside the display rect area.
+      Rect segment_bounds(PointAtOffsetFromOrigin(line_offset) +
+                              Vector2d(preceding_segment_widths, 0),
+                          Size(segment_width, line.height));
+      if (!display_rect().Intersects(segment_bounds)) {
+        preceding_segment_widths += segment_width;
+        continue;
+      }
+
+      int segment_x = 0;
+      pos.resize(glyphs.length());
+      for (size_t g = glyphs.start(); g < glyphs.end(); ++g) {
+        pos[g - glyphs.start()].set(
+            SkIntToScalar(text_offset.x() + preceding_segment_widths +
+                          segment_x + run->offsets[g].du),
+            SkIntToScalar(text_offset.y() + run->offsets[g].dv));
+        segment_x += run->advance_widths[g];
+      }
+
+      renderer.SetTextSize(run->font.GetFontSize());
+      renderer.SetFontFamilyWithStyle(run->font.GetFontName(), run->font_style);
+
+      for (BreakList<SkColor>::const_iterator it =
+               colors().GetBreak(run->range.start());
+           it != colors().breaks().end() && it->first < run->range.end();
+           ++it) {
+        ui::Range intersection = colors().GetRange(it).Intersect(
+            segment->char_pos);
+        ui::Range colored_glyphs = CharRangeToGlyphRange(*run, intersection);
+        DCHECK(glyphs.Contains(colored_glyphs));
+        if (colored_glyphs.is_empty())
+          continue;
+        renderer.SetForegroundColor(it->second);
+        renderer.DrawPosText(&pos[colored_glyphs.start() - glyphs.start()],
+                             &run->glyphs[colored_glyphs.start()],
+                             colored_glyphs.length());
+        SkScalar width = (colored_glyphs.end() < glyphs.end()
+                          ? pos[colored_glyphs.end() - glyphs.start()].x()
+                          : pos[0].x() + SkIntToScalar(segment_width))
+            - pos[colored_glyphs.start() - glyphs.start()].x();
+        renderer.DrawDecorations(
+            pos[colored_glyphs.start() - glyphs.start()].x(), text_offset.y(),
+            SkScalarCeilToInt(width), run->underline, run->strike,
+            run->diagonal_strike);
+      }
+
+      preceding_segment_widths += segment_width;
     }
-
-    // Based on WebCore::skiaDrawText. |pos| contains the positions of glyphs.
-    // An extra terminal |pos| entry is added to simplify width calculations.
-    pos.resize(run->glyph_count + 1);
-    SkScalar glyph_x = x;
-    for (int glyph = 0; glyph < run->glyph_count; glyph++) {
-      pos[glyph].set(glyph_x + run->offsets[glyph].du,
-                     y + run->offsets[glyph].dv);
-      glyph_x += SkIntToScalar(run->advance_widths[glyph]);
-    }
-    pos.back().set(glyph_x, y);
-
-    renderer.SetTextSize(run->font.GetFontSize());
-    renderer.SetFontFamilyWithStyle(run->font.GetFontName(), run->font_style);
-
-    for (BreakList<SkColor>::const_iterator it =
-             colors().GetBreak(run->range.start());
-         it != colors().breaks().end() && it->first < run->range.end();
-         ++it) {
-      const ui::Range glyph_range = CharRangeToGlyphRange(*run,
-          colors().GetRange(it).Intersect(run->range));
-      if (glyph_range.is_empty())
-        continue;
-      renderer.SetForegroundColor(it->second);
-      renderer.DrawPosText(&pos[glyph_range.start()],
-                           &run->glyphs[glyph_range.start()],
-                           glyph_range.length());
-      const SkScalar width = pos[glyph_range.end()].x() -
-          pos[glyph_range.start()].x();
-      renderer.DrawDecorations(pos[glyph_range.start()].x(), y,
-                               SkScalarCeilToInt(width), run->underline,
-                               run->strike, run->diagonal_strike);
-    }
-
-    DCHECK_EQ(glyph_x - x, run->width);
-    x = glyph_x;
   }
 
   UndoCompositionAndSelectionStyles();
 }
 
 void RenderTextWin::ItemizeLogicalText() {
   runs_.clear();
   // Make |string_size_|'s height and |common_baseline_| tall enough to draw
   // often-used characters which are rendered with fonts in the font list.
   string_size_ = Size(0, font_list().GetHeight());
@@ skipping 357 matching lines @@
   size_t position = LayoutIndexToTextIndex(run->range.end());
   position = IndexOfAdjacentGrapheme(position, CURSOR_BACKWARD);
   return SelectionModel(position, CURSOR_FORWARD);
 }
 
 RenderText* RenderText::CreateInstance() {
   return new RenderTextWin;
 }
 
 }  // namespace gfx