Windows implementation of multiline RenderText

ui/gfx/render_text_win.cc

Index: ui/gfx/render_text_win.cc
diff --git a/ui/gfx/render_text_win.cc b/ui/gfx/render_text_win.cc
index ac018de3f446226f8e39276ee65f24ebf1e76478..f15bb25c4f1d11a093fc869a51f49612d47ad56b 100644
--- a/ui/gfx/render_text_win.cc
+++ b/ui/gfx/render_text_win.cc
@@ -154,6 +154,55 @@ ui::Range CharRangeToGlyphRange(const internal::TextRun& run,
   return result;
 }
 
+// Starting from |start_char|, finds the first character that doesn't fit the
+// given |width_cap|. If |width_cap| is reached, returns true and fills the
+// output arguments with overflow and rollback info. Otherwise returns false and
+// only fills |width|.
+// |overflow|: Index of the first character that doesn't fit the given width.
+// |width|: If the run doesn't fit, holds the width of [start_char, *overflow].
+//          Otherwise, holds the width of [start_char, run.range.end()).
+// |char_rollback_width|: Width of |*overflow|.
+// |word_rollback_pos|: Index of the last word break before |*overflow|.
+// |word_rollback_width|: Width of [*word_rollback_pos, *overflow].
+bool BreakRunAtWidth(const internal::TextRun& run,
+                     const BreakList<size_t>& breaks, size_t start_char,

[Alexei Svitkine (slow), 2013/08/08 15:01:03]

One parameter per line in the declaration, please.

[ckocagil, 2013/08/10 13:39:23]

Done.

+                     int width_cap, int* width, size_t* overflow,
+                     int* char_rollback_width, size_t* word_rollback_pos,
+                     int* word_rollback_width) {

[Alexei Svitkine (slow), 2013/08/08 15:01:03]

This is quite a lot of parameters to pass to this function. Maybe you can make a
struct RunBreakState that keeps all of these around (with line comments for the
members instead of commenting them above the signature). Or perhaps make another
helper class (RunBreaker) that keeps this state around and is responsible for
breaking a single run (rather than a line). WDYT?

[ckocagil, 2013/08/10 13:39:23]

There isn't a lot of state tracking and the function itself is straightforward,
so I think adding a class would add unnecessary complexity. I only added a
struct that holds the result fields. Does it look better now?

+  DCHECK(run.range.Contains(ui::Range(start_char)));
+  size_t current_word = start_char;
+  int current_word_x = 0; // x from |current_word|
+  int x = 0;
+
+  for (size_t i = start_char; i < run.range.end(); ++i) {
+    size_t next_word = std::max(breaks.GetBreak(i)->first, start_char);
+    if (next_word != current_word) {
+      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 > width_cap) {
+      *overflow = i;
+      *width = x;
+      *char_rollback_width = char_width;
+      *word_rollback_pos = current_word;
+      *word_rollback_width = current_word_x;
+      return true;
+    }
+  }
+
+  *width = x;
+  return false;
+}
+
 }  // namespace
 
 namespace internal {
@@ -197,6 +246,159 @@ int GetGlyphXBoundary(const internal::TextRun* run,
   return run->preceding_run_widths + x;
 }
 
+struct LineSegmentWin : LineSegment {
+  internal::TextRun* run;
+};
+
+// Internal class to help break a text into lines.
+class LineBreaker {
+ public:
+  LineBreaker() : preceding_line_heights_(0),
+                  pos_(0),
+                  text_x_(0),
+                  line_x_(0),
+                  current_pos_(0),
+                  current_delta_(0) {}
+
+  // 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 Break(const ScopedVector<internal::TextRun>& runs,
+             const BreakList<size_t>& words,
+             int max_width,
+             bool multiline,
+             int* visual_to_logical,
+             std::vector<internal::Line>* lines) {

[Alexei Svitkine (slow), 2013/08/08 15:01:03]

Instead of passing all of these params to a single Break() function, how about
making the API AddRun(run) and leave the iteration logic to the caller?

This way, the visual_to_logical stuff mapping and iteration can left to the
caller and this can process runs as they come, with maybe a Finalize() method
that returns the lines as output.

In this case, add the other parameters like |words|, |max_width|, etc to the
ctor.

[ckocagil, 2013/08/10 13:39:23]

Done.

+    SkipLine();
+
+    for (size_t i = 0; i < runs.size(); ++i) {
+      internal::TextRun* run = runs[visual_to_logical[i]];
+      ResetPos(run->range.start());
+      int width = multiline ? BreakRun(run, words, max_width) : run->width;
+      // Remaining part of the run fits the line, add it as well.
+      Advance(run->range.end(), width);
+      CommitSegment(run);
+    }
+
+    lines->swap(lines_);
+  }
+
+ private:
+  // 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, text-space coordinate of the run beginning is
+  // saved and the segment widths are applied in reverse order.
+  // e.g. {[5, 10], [10, 40]} will become {[35, 40], [5, 35]}.
+  struct RtlData {
+    int run_x_; // Beginning of the RTL run in text-space.
+    std::vector<LineSegment*> segments_;
+  };
+
+  // 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(internal::TextRun* run,
+               const BreakList<size_t>& words,
+               int max_width) {
+    int width = run->width;
+    size_t overflow;
+    int char_rollback_width;
+    size_t word_rollback_pos;
+    int word_rollback_width;
+    // Break the run until it fits the current line.
+    while (BreakRunAtWidth(*run, words, pos_, max_width - line_x_,
+                            &width, &overflow, &char_rollback_width,
+                            &word_rollback_pos, &word_rollback_width)) {
+      DCHECK(pos_ < run->range.end());
+      Advance(overflow + 1, 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 || word_rollback_width < width)
+        Rollback(word_rollback_pos, word_rollback_width);
+      else if (line_x_ > 0 || char_rollback_width < width)
+        Rollback(overflow, char_rollback_width);
+      CommitSegment(run);
+      SkipLine();
+    }
+
+    return width;
+  }
+
+  // Applies |rtl_data_|.
+  void PopRtl() {
+    int x = rtl_data_.run_x_;
+    while (!rtl_data_.segments_.empty()) {
+      LineSegment* segment = rtl_data_.segments_.back();
+      rtl_data_.segments_.pop_back();
+      segment->x_pos = ui::Range(x, x + segment->x_pos.length());
+      x += segment->x_pos.length();
+    }
+  }
+
+  void ResetPos(size_t new_pos) {
+    pos_ = new_pos;
+    current_pos_ = new_pos;
+    current_delta_ = 0;
+  }
+
+  void Advance(size_t new_pos, int amount) {
+    current_pos_ = new_pos;
+    current_delta_ += 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(internal::TextRun* run) {
+    if (pos_ == current_pos_) {
+      DCHECK(current_delta_ == 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_delta_);
+    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) {
+      if (pos_ == run->range.start())
+        rtl_data_.run_x_ = text_x_;
+      rtl_data_.segments_.push_back(segment);
+      if (current_pos_ == run->range.end())
+        PopRtl();
+    }
+    pos_ = current_pos_;
+    text_x_ += current_delta_;
+    line_x_ += current_delta_;
+    current_delta_ = 0;
+  }
+
+  std::vector<internal::Line> lines_;
+  int preceding_line_heights_;
+  size_t pos_;
+  int text_x_;
+  int line_x_;
+  size_t current_pos_;
+  int current_delta_;
+  RtlData rtl_data_;
+
+  DISALLOW_COPY_AND_ASSIGN(LineBreaker);
+};
+
 }  // namespace internal
 
 // static
@@ -222,7 +424,15 @@ RenderTextWin::~RenderTextWin() {
 
 Size RenderTextWin::GetStringSize() {
   EnsureLayout();
-  return string_size_;
+  return Size(string_size_.width(), string_size_.height());

[Alexei Svitkine (slow), 2013/08/08 15:01:03]

This is equivalent to return string_size_;, no?

[ckocagil, 2013/08/10 13:39:23]

Oops, leftover from before. Done.

+}
+
+Size RenderTextWin::GetMultilineTextSize() {

[Alexei Svitkine (slow), 2013/08/08 15:01:03]

I think you should make GetStringSize() return the multiline size by default
when in multi-line mode.

i.e. remove this extra method and fold the logic.

(Else, you'd at least need to add implementations of this to the other render
text subclasses.)

[ckocagil, 2013/08/10 13:39:23]

But if GetStringSize returns the display width and not single line string width,
the controls using RenderText won't be able to know their preferred size. I
think users of RenderText will always need to know 1) the single-line size of
the text (for their preferred size) and 2) the multi-line height (for
GetHeightForWidth).

I will add empty NOTIMPLEMENTED() methods to all platforms that need them,
probably after the review to not make this CL any harder to review.

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Re-visiting this discussion (I didn't follow-up on this when you replied
originally). I'm still skeptical that we really need both.

I'm not following you when you say "GetStringSize returns the display width and
not single line string width". It seems GetStringSize does return the actual
width, not the display width (i.e. not the width of the display rect). Unless
you meant something else by saying "returns the display width"?

Perhaps you meant that it currently doesn't cap the returned width to the
display rect's width? I think that's currently true, but it doesn't have to be -
we could change it (though not in this CL). But even if we don't, I think it's
okay if semantics are slightly different in multiline mode - i.e. if multiline
is set, return the equivalent of the current GetMultilineTextSize() from
GetStringSize().

Or is there something I'm missing about why we would want to keep the
non-multiline-aware GetStringSize() functionality in multi-line mode?

[ckocagil, 2013/08/28 19:16:26]

I said "_if_ GetStringSize returns the display width", that "if" is important
there :-)
In multi-line mode, there are two uses for the RenderText string size functions:
- Getting the single-line string size so that labels can pass this value to
View::GetPreferredSize().
- Getting the current multi-line height so that labels can pass this value to
View::GetHeightForWidth().

We can't give both values with a single function, so we need a new one. I don't
know Views well though, so please let me know if we don't need to supply both of
these values.

[Alexei Svitkine (slow), 2013/08/28 21:27:46]

I think for GetHeightForWidth() with different widths passed in, we would
already be resetting the display rect before querying the new size - so we can
similarly reset the multiline_ state for GetPreferredSize() and get the new
string size.

I think for now this CL shouldn't add the new API and instead make GetStringSize
return the multi-line size when in multi-line mode. If we do find that we need
the additional API (i.e. at the time that we make Label use it or something
else), then we can always re-visit this decision. But for now, let's not add the
new API for this.

[msw, 2013/08/30 00:42:28]

I think the uses of View's GetPreferredSize and GetHeightForWidth will make it
tough to have a single function, but following Alexei's advice for now should be
okay. Eventually, caching sizes for given/unlimited widths would likely be
helpful to avoid actually resizing text that's already displayed with a
different width.

[ckocagil, 2013/08/30 16:53:36]

Alexei's advice on change multiline mode to get single-line size is a good idea
(if it doesn't affect performance too much). However, I can't get rid of the
need for the single-line size in RenderText::GetCursorBounds() (see the
GetStringSize() call there). Thoughts?

[Alexei Svitkine (slow), 2013/08/30 17:07:25]

I think the current GetCursorBounds() logic is incorrect in multi-line mode. I
suspect more work will be needed to enable editable multi-line text to work (vs
just the support being added in this CL for drawing it).

Given the above, I think it's fine to file a bug and add a TODO to
GetCursorBounds() to make it work in multiline mode and keep it as-is for now
(i.e. still calling GetStringSize() which would give the wrong results in
multiline mode but will continue to work for single-line mode).

+  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() {
@@ -383,11 +593,12 @@ std::vector<Rect> RenderTextWin::GetSubstringBounds(const ui::Range& range) {
                          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]];
@@ -396,17 +607,23 @@ std::vector<Rect> RenderTextWin::GetSubstringBounds(const ui::Range& range) {
       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 {
@@ -448,23 +665,34 @@ void RenderTextWin::ResetLayout() {
 }
 
 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::DrawVisualText(Canvas* canvas) {
+void RenderTextWin::ComputeLines() {
   DCHECK(!needs_layout_);
+  std::vector<internal::Line> lines;
+  internal::LineBreaker line_breaker;
+  line_breaker.Break(runs_, multiline() ? GetLineBreaks() : BreakList<size_t>(),
+                     display_rect().width(), multiline(),
+                     visual_to_logical_.get(), &lines);
+  set_lines(&lines);

[Alexei Svitkine (slow), 2013/08/08 15:01:03]

Can you add a DCHECK() that !lines().empty()? (Else this function will keep
getting called from EnsureLayout() if it can return an empty list of lines).

[ckocagil, 2013/08/10 13:39:23]

Done.

+}
 
-  // 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());
+void RenderTextWin::DrawVisualText(Canvas* canvas) {
+  DCHECK(!needs_layout_);
+  DCHECK(!multiline() || !lines().empty());
 
   std::vector<SkPoint> pos;
 
@@ -479,54 +707,79 @@ void RenderTextWin::DrawVisualText(Canvas* canvas) {
   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]];
-
-    // 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;
+  ApplyCompositionAndSelectionStyles();
+
+  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 lines or lines outside the display rect area.
+    if (!display_rect().Intersects(Rect(PointAtOffsetFromOrigin(line_offset),
+                                        Size(line.width, line.height))))
       continue;
-    }
-
-    // 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())
+
+    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();
+      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;
-      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;
+      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;
+    }
   }
 
   UndoCompositionAndSelectionStyles();