OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "core/layout/ng/inline/ng_line_breaker.h" | 5 #include "core/layout/ng/inline/ng_line_breaker.h" |
6 | 6 |
| 7 #include "core/layout/ng/inline/ng_inline_break_token.h" |
7 #include "core/layout/ng/inline/ng_inline_layout_algorithm.h" | 8 #include "core/layout/ng/inline/ng_inline_layout_algorithm.h" |
8 #include "core/layout/ng/inline/ng_inline_node.h" | 9 #include "core/layout/ng/inline/ng_inline_node.h" |
9 #include "core/layout/ng/inline/ng_text_fragment.h" | 10 #include "core/layout/ng/inline/ng_text_fragment.h" |
10 #include "core/layout/ng/ng_box_fragment.h" | 11 #include "core/layout/ng/ng_box_fragment.h" |
11 #include "core/layout/ng/ng_break_token.h" | 12 #include "core/layout/ng/ng_break_token.h" |
12 #include "core/layout/ng/ng_constraint_space.h" | 13 #include "core/layout/ng/ng_constraint_space.h" |
13 #include "core/layout/ng/ng_fragment_builder.h" | 14 #include "core/layout/ng/ng_fragment_builder.h" |
14 #include "core/layout/ng/ng_layout_opportunity_iterator.h" | 15 #include "core/layout/ng/ng_layout_opportunity_iterator.h" |
15 #include "core/style/ComputedStyle.h" | 16 #include "core/style/ComputedStyle.h" |
| 17 #include "platform/fonts/shaping/HarfBuzzShaper.h" |
| 18 #include "platform/fonts/shaping/ShapingLineBreaker.h" |
16 #include "platform/text/TextBreakIterator.h" | 19 #include "platform/text/TextBreakIterator.h" |
17 | 20 |
18 namespace blink { | 21 namespace blink { |
19 | 22 |
20 static bool IsHangable(UChar ch) { | 23 namespace { |
21 return ch == ' '; | 24 |
22 } | 25 // Use a mock of ShapingLineBreaker for test/debug purposes. |
23 | 26 #define MOCK_SHAPE_LINE |
24 void NGLineBreaker::BreakLines(NGInlineLayoutAlgorithm* algorithm, | 27 |
25 const String& text_content, | 28 #if defined(MOCK_SHAPE_LINE) |
26 unsigned current_offset) { | 29 // The mock for ShapingLineBreaker::ShapeLine(). |
27 DCHECK(!text_content.IsEmpty()); | 30 // Given the design of ShapingLineBreaker, expected semantics are: |
28 LazyLineBreakIterator line_break_iterator(text_content, locale_); | 31 // - The returned offset is always > item.StartOffset(). |
29 const unsigned end_offset = text_content.length(); | 32 // - offset < item.EndOffset(): |
30 while (current_offset < end_offset) { | 33 // - width <= available_width: the break opportunity to fit is found. |
31 // Find the next break opportunity. | 34 // - width > available_width: the first break opportunity did not fit. |
32 int tmp_next_breakable_offset = -1; | 35 // - offset == item.EndOffset(): |
33 line_break_iterator.IsBreakable(current_offset + 1, | 36 // - width <= available_width: the break opportunity at the end of the item |
34 tmp_next_breakable_offset); | 37 // fits. |
35 current_offset = | 38 // - width > available_width: the first break opportunity is at the end of |
36 tmp_next_breakable_offset >= 0 ? tmp_next_breakable_offset : end_offset; | 39 // the item and it does not fit. |
37 DCHECK_LE(current_offset, end_offset); | 40 // - offset > item.EndOffset():, the first break opportunity is beyond the |
38 | 41 // end of item and thus cannot measure. In this case, inline_size shows the |
39 // Advance the break opportunity to the end of hangable characters; e.g., | 42 // width until the end of the item. It may fit or may not. |
40 // spaces. | 43 std::pair<unsigned, LayoutUnit> ShapeLineMock( |
41 // Unlike the ICU line breaker, LazyLineBreakIterator breaks before | 44 const NGInlineItem& item, |
42 // breakable spaces, and expect the line breaker to handle spaces | 45 unsigned offset, |
43 // differently. This logic computes in the ICU way; break after spaces, and | 46 LayoutUnit available_width, |
44 // handle spaces as hangable characters. | 47 const LazyLineBreakIterator& break_iterator) { |
45 unsigned start_of_hangables = current_offset; | 48 bool has_break_opportunities = false; |
46 while (current_offset < end_offset && | 49 LayoutUnit inline_size; |
47 IsHangable(text_content[current_offset])) | 50 while (true) { |
48 current_offset++; | 51 unsigned next_break = break_iterator.NextBreakOpportunity(offset + 1); |
49 | 52 LayoutUnit next_inline_size = |
50 // Set the end to the next break opportunity. | 53 inline_size + |
51 algorithm->SetEnd(current_offset); | 54 item.InlineSize(offset, std::min(next_break, item.EndOffset())); |
52 | 55 if (next_inline_size > available_width) { |
53 // If there are more available spaces, mark the break opportunity and fetch | 56 if (!has_break_opportunities) |
54 // more text. | 57 return std::make_pair(next_break, next_inline_size); |
55 // TODO(layout-ng): check if the height of the linebox can fit within | 58 return std::make_pair(offset, inline_size); |
56 // the current opportunity. | 59 } |
57 if (algorithm->CanFitOnLine()) { | 60 if (next_break >= item.EndOffset()) |
58 algorithm->SetBreakOpportunity(); | 61 return std::make_pair(next_break, next_inline_size); |
| 62 offset = next_break; |
| 63 inline_size = next_inline_size; |
| 64 has_break_opportunities = true; |
| 65 } |
| 66 } |
| 67 #endif |
| 68 |
| 69 LineBreakType GetLineBreakType(const ComputedStyle& style) { |
| 70 if (style.AutoWrap()) { |
| 71 if (style.WordBreak() == kBreakAllWordBreak || |
| 72 style.WordBreak() == kBreakWordBreak) |
| 73 return LineBreakType::kBreakAll; |
| 74 if (style.WordBreak() == kKeepAllWordBreak) |
| 75 return LineBreakType::kKeepAll; |
| 76 } |
| 77 return LineBreakType::kNormal; |
| 78 } |
| 79 |
| 80 } // namespace |
| 81 |
| 82 NGLineBreaker::NGLineBreaker(NGInlineNode* node, |
| 83 const NGConstraintSpace* space, |
| 84 NGInlineBreakToken* break_token) |
| 85 : node_(node), constraint_space_(space), item_index_(0), offset_(0) { |
| 86 if (break_token) { |
| 87 item_index_ = break_token->ItemIndex(); |
| 88 offset_ = break_token->TextOffset(); |
| 89 node->AssertOffset(item_index_, offset_); |
| 90 } |
| 91 } |
| 92 |
| 93 void NGLineBreaker::NextLine(NGInlineItemResults* item_results, |
| 94 NGInlineLayoutAlgorithm* algorithm) { |
| 95 BreakLine(item_results, algorithm); |
| 96 |
| 97 // TODO(kojii): When editing, or caret is enabled, trailing spaces at wrap |
| 98 // point should not be removed. For other cases, we can a) remove, b) leave |
| 99 // characters without glyphs, or c) leave both characters and glyphs without |
| 100 // measuring. Need to decide which one works the best. |
| 101 SkipCollapsibleWhitespaces(); |
| 102 } |
| 103 |
| 104 void NGLineBreaker::BreakLine(NGInlineItemResults* item_results, |
| 105 NGInlineLayoutAlgorithm* algorithm) { |
| 106 DCHECK(item_results->IsEmpty()); |
| 107 const Vector<NGInlineItem>& items = node_->Items(); |
| 108 const String& text = node_->Text(); |
| 109 const ComputedStyle& style = node_->Style(); |
| 110 LazyLineBreakIterator break_iterator(text, style.LocaleForLineBreakIterator(), |
| 111 GetLineBreakType(style)); |
| 112 #if !defined(MOCK_SHAPE_LINE) |
| 113 HarfBuzzShaper shaper(text.Characters16(), text.length()); |
| 114 #endif |
| 115 LayoutUnit available_width = algorithm->AvailableWidth(); |
| 116 LayoutUnit position; |
| 117 while (item_index_ < items.size()) { |
| 118 const NGInlineItem& item = items[item_index_]; |
| 119 item_results->push_back( |
| 120 NGInlineItemResult(item_index_, offset_, item.EndOffset())); |
| 121 NGInlineItemResult* item_result = &item_results->back(); |
| 122 |
| 123 // If the start offset is at the item boundary, try to add the entire item. |
| 124 if (offset_ == item.StartOffset()) { |
| 125 if (item.Type() == NGInlineItem::kText) { |
| 126 item_result->inline_size = item.InlineSize(); |
| 127 } else if (item.Type() == NGInlineItem::kAtomicInline) { |
| 128 LayoutAtomicInline(item, item_result); |
| 129 } else if (item.Type() == NGInlineItem::kFloating) { |
| 130 algorithm->LayoutAndPositionFloat(position, item.GetLayoutObject()); |
| 131 // Floats may change the available width if they fit. |
| 132 available_width = algorithm->AvailableWidth(); |
| 133 // Floats are already positioned in the container_builder. |
| 134 item_results->pop_back(); |
| 135 offset_ = item.EndOffset(); |
| 136 item_index_++; |
| 137 continue; |
| 138 } else { |
| 139 offset_ = item.EndOffset(); |
| 140 item_index_++; |
| 141 continue; |
| 142 } |
| 143 LayoutUnit next_position = position + item_result->inline_size; |
| 144 if (next_position <= available_width) { |
| 145 offset_ = item.EndOffset(); |
| 146 item_index_++; |
| 147 position = next_position; |
| 148 continue; |
| 149 } |
| 150 |
| 151 // The entire item does not fit. Handle non-text items as overflow, |
| 152 // since only text item is breakable. |
| 153 if (item.Type() != NGInlineItem::kText) { |
| 154 offset_ = item.EndOffset(); |
| 155 item_index_++; |
| 156 return HandleOverflow(item_results, break_iterator); |
| 157 } |
| 158 } |
| 159 |
| 160 // Either the start or the break is in the mid of a text item. |
| 161 DCHECK_EQ(item.Type(), NGInlineItem::kText); |
| 162 DCHECK_LT(offset_, item.EndOffset()); |
| 163 break_iterator.SetLocale(item.Style()->LocaleForLineBreakIterator()); |
| 164 break_iterator.SetBreakType(GetLineBreakType(*item.Style())); |
| 165 #if defined(MOCK_SHAPE_LINE) |
| 166 unsigned break_offset; |
| 167 std::tie(break_offset, item_result->inline_size) = ShapeLineMock( |
| 168 item, offset_, available_width - position, break_iterator); |
| 169 #else |
| 170 // TODO(kojii): We need to instantiate ShapingLineBreaker here because it |
| 171 // has item-specific info as context. Should they be part of ShapeLine() to |
| 172 // instantiate once, or is this just fine since instatiation is not |
| 173 // expensive? |
| 174 DCHECK_EQ(item.TextShapeResult()->StartIndexForResult(), |
| 175 item.StartOffset()); |
| 176 DCHECK_EQ(item.TextShapeResult()->EndIndexForResult(), item.EndOffset()); |
| 177 ShapingLineBreaker breaker(&shaper, &item.Style()->GetFont(), |
| 178 item.TextShapeResult(), &break_iterator); |
| 179 unsigned break_offset; |
| 180 item_result->shape_result = |
| 181 breaker.ShapeLine(offset_, available_width - position, &break_offset); |
| 182 item_result->inline_size = item_result->shape_result->SnappedWidth(); |
| 183 #endif |
| 184 DCHECK_GT(break_offset, offset_); |
| 185 position += item_result->inline_size; |
| 186 |
| 187 // If the break found within the item, break here. |
| 188 if (break_offset < item.EndOffset()) { |
| 189 offset_ = item_result->end_offset = break_offset; |
| 190 if (position <= available_width) |
| 191 break; |
| 192 // The first break opportunity of the item does not fit. |
| 193 } else { |
| 194 // No break opporunity in the item, or the first break opportunity is at |
| 195 // the end of the item. If it fits, continue to the next item. |
| 196 offset_ = item_result->end_offset = item.EndOffset(); |
| 197 item_index_++; |
| 198 if (position <= available_width) |
| 199 continue; |
| 200 } |
| 201 |
| 202 // We need to look at next item if we're overflowing, and the break |
| 203 // opportunity is beyond this item. |
| 204 if (break_offset > item.EndOffset()) |
59 continue; | 205 continue; |
60 } | 206 return HandleOverflow(item_results, break_iterator); |
61 | 207 } |
62 // Compute hangable characters if exists. | 208 } |
63 if (current_offset != start_of_hangables) { | 209 |
64 algorithm->SetStartOfHangables(start_of_hangables); | 210 void NGLineBreaker::LayoutAtomicInline(const NGInlineItem& item, |
65 // If text before hangables can fit, include it in the current line. | 211 NGInlineItemResult* item_result) { |
66 if (algorithm->CanFitOnLine()) | 212 DCHECK_EQ(item.Type(), NGInlineItem::kAtomicInline); |
67 algorithm->SetBreakOpportunity(); | 213 NGBlockNode* node = new NGBlockNode(item.GetLayoutObject()); |
68 } | 214 const ComputedStyle& style = node->Style(); |
69 | 215 NGConstraintSpaceBuilder constraint_space_builder(constraint_space_); |
70 if (!algorithm->HasBreakOpportunity()) { | 216 RefPtr<NGConstraintSpace> constraint_space = |
71 // The first word (break opportunity) did not fit on the line. | 217 constraint_space_builder.SetIsNewFormattingContext(true) |
72 // Create a line including items that don't fit, allowing them to | 218 .SetIsShrinkToFit(true) |
73 // overflow. | 219 .SetTextDirection(style.Direction()) |
74 if (!algorithm->CreateLine()) | 220 .ToConstraintSpace(FromPlatformWritingMode(style.GetWritingMode())); |
75 return; | 221 item_result->layout_result = node->Layout(constraint_space.Get()); |
76 } else { | 222 |
77 if (!algorithm->CreateLineUpToLastBreakOpportunity()) | 223 item_result->inline_size = |
78 return; | 224 NGBoxFragment(constraint_space_->WritingMode(), |
79 | 225 ToNGPhysicalBoxFragment( |
80 // Items after the last break opportunity were sent to the next line. | 226 item_result->layout_result->PhysicalFragment().Get())) |
81 // Set the break opportunity, or create a line if the word doesn't fit. | 227 .InlineSize(); |
82 if (algorithm->HasItems()) { | 228 } |
83 if (algorithm->CanFitOnLine()) | 229 |
84 algorithm->SetBreakOpportunity(); | 230 // Handles when the last item overflows. |
85 else if (!algorithm->CreateLine()) | 231 // At this point, item_results does not fit into the current line, and there |
86 return; | 232 // are no break opportunities in item_results.back(). |
87 } | 233 void NGLineBreaker::HandleOverflow( |
88 } | 234 NGInlineItemResults* item_results, |
89 } | 235 const LazyLineBreakIterator& break_iterator) { |
90 | 236 DCHECK_GT(offset_, 0u); |
91 // If inline children ended with items left in the line builder, create a line | 237 |
92 // for them. | 238 // Find the last break opportunity. If none, let this line overflow. |
93 if (algorithm->HasItems()) | 239 unsigned line_start_offset = item_results->front().start_offset; |
94 algorithm->CreateLine(); | 240 unsigned break_offset = |
| 241 break_iterator.PreviousBreakOpportunity(offset_ - 1, line_start_offset); |
| 242 if (!break_offset || break_offset <= line_start_offset) { |
| 243 AppendCloseTags(item_results); |
| 244 return; |
| 245 } |
| 246 |
| 247 // Truncate the end of the line to the break opportunity. |
| 248 const Vector<NGInlineItem>& items = node_->Items(); |
| 249 unsigned new_end = item_results->size(); |
| 250 while (true) { |
| 251 NGInlineItemResult* item_result = &(*item_results)[--new_end]; |
| 252 if (item_result->start_offset < break_offset) { |
| 253 // The break is at the mid of the item. Adjust the end_offset to the new |
| 254 // break offset. |
| 255 const NGInlineItem& item = items[item_result->item_index]; |
| 256 item.AssertEndOffset(break_offset); |
| 257 DCHECK_EQ(item.Type(), NGInlineItem::kText); |
| 258 DCHECK_NE(item_result->end_offset, break_offset); |
| 259 item_result->end_offset = break_offset; |
| 260 item_result->inline_size = |
| 261 item.InlineSize(item_result->start_offset, item_result->end_offset); |
| 262 // TODO(kojii): May need to reshape. Add to ShapingLineBreaker? |
| 263 new_end++; |
| 264 break; |
| 265 } |
| 266 if (item_result->start_offset == break_offset) { |
| 267 // The new break offset is at the item boundary. Remove items up to the |
| 268 // new break offset. |
| 269 // TODO(kojii): Remove open tags as well. |
| 270 break; |
| 271 } |
| 272 } |
| 273 DCHECK_GT(new_end, 0u); |
| 274 |
| 275 // TODO(kojii): Should we keep results for the next line? We don't need to |
| 276 // re-layout atomic inlines. |
| 277 // TODO(kojii): Removing processed floats is likely a problematic. Keep |
| 278 // floats in this line, or keep it for the next line. |
| 279 item_results->Shrink(new_end); |
| 280 |
| 281 // Update the current item index and offset to the new break point. |
| 282 const NGInlineItemResult& last_item_result = item_results->back(); |
| 283 offset_ = last_item_result.end_offset; |
| 284 item_index_ = last_item_result.item_index; |
| 285 if (items[item_index_].EndOffset() == offset_) |
| 286 item_index_++; |
| 287 } |
| 288 |
| 289 void NGLineBreaker::SkipCollapsibleWhitespaces() { |
| 290 const Vector<NGInlineItem>& items = node_->Items(); |
| 291 if (item_index_ >= items.size()) |
| 292 return; |
| 293 const NGInlineItem& item = items[item_index_]; |
| 294 if (item.Type() != NGInlineItem::kText || !item.Style()->CollapseWhiteSpace()) |
| 295 return; |
| 296 |
| 297 DCHECK_LT(offset_, item.EndOffset()); |
| 298 if (node_->Text()[offset_] == kSpaceCharacter) { |
| 299 // Skip one whitespace. Collapsible spaces are collapsed to single space in |
| 300 // NGInlineItemBuilder, so this removes all collapsible spaces. |
| 301 offset_++; |
| 302 if (offset_ == item.EndOffset()) |
| 303 item_index_++; |
| 304 } |
| 305 } |
| 306 |
| 307 void NGLineBreaker::AppendCloseTags(NGInlineItemResults* item_results) { |
| 308 const Vector<NGInlineItem>& items = node_->Items(); |
| 309 for (; item_index_ < items.size(); item_index_++) { |
| 310 const NGInlineItem& item = items[item_index_]; |
| 311 if (item.Type() != NGInlineItem::kCloseTag) |
| 312 break; |
| 313 DCHECK_EQ(offset_, item.EndOffset()); |
| 314 item_results->push_back(NGInlineItemResult(item_index_, offset_, offset_)); |
| 315 } |
| 316 } |
| 317 |
| 318 RefPtr<NGInlineBreakToken> NGLineBreaker::CreateBreakToken() const { |
| 319 const Vector<NGInlineItem>& items = node_->Items(); |
| 320 if (item_index_ >= items.size()) |
| 321 return nullptr; |
| 322 return NGInlineBreakToken::Create(node_, item_index_, offset_); |
95 } | 323 } |
96 | 324 |
97 } // namespace blink | 325 } // namespace blink |
OLD | NEW |