1 // Copyright 2017 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 #include "third_party/blink/renderer/core/editing/bidi_adjustment.h"
6
7 #include <unicode/ubidi.h>
8
9 #include "third_party/blink/renderer/core/editing/inline_box_position.h"
10 #include "third_party/blink/renderer/core/editing/ng_flat_tree_shorthands.h"
11 #include "third_party/blink/renderer/core/editing/selection_template.h"
12 #include "third_party/blink/renderer/core/editing/visible_position.h"
13 #include "third_party/blink/renderer/core/layout/api/line_layout_block_flow.h"
14 #include "third_party/blink/renderer/core/layout/line/inline_box.h"
15 #include "third_party/blink/renderer/core/layout/line/root_inline_box.h"
16 #include "third_party/blink/renderer/core/layout/ng/inline/ng_caret_position.h"
17 #include "third_party/blink/renderer/platform/text/text_direction.h"
18
19 namespace blink {
20
21 namespace {
22
23 // |AbstractInlineBox| provides abstraction of leaf nodes (text and atomic
24 // inlines) in both legacy and NG inline layout, so that the same bidi
25 // adjustment algorithm can be applied on both types of inline layout.
26 class AbstractInlineBox {
27 STACK_ALLOCATED();
28
29 public:
AbstractInlineBox()30 AbstractInlineBox() : type_(InstanceType::kNull) {}
31
AbstractInlineBox(const InlineBox & box)32 explicit AbstractInlineBox(const InlineBox& box)
33 : type_(InstanceType::kOldLayout), inline_box_(&box) {}
AbstractInlineBox(const NGInlineCursor & cursor)34 explicit AbstractInlineBox(const NGInlineCursor& cursor)
35 : type_(InstanceType::kNG),
36 line_cursor_(CreateLineRootedCursor(cursor)) {}
37
IsNotNull() const38 bool IsNotNull() const { return type_ != InstanceType::kNull; }
IsNull() const39 bool IsNull() const { return !IsNotNull(); }
IsOldLayout() const40 bool IsOldLayout() const { return type_ == InstanceType::kOldLayout; }
IsNG() const41 bool IsNG() const { return type_ == InstanceType::kNG; }
42
operator ==(const AbstractInlineBox & other) const43 bool operator==(const AbstractInlineBox& other) const {
44 if (type_ != other.type_)
45 return false;
46 switch (type_) {
47 case InstanceType::kNull:
48 return true;
49 case InstanceType::kOldLayout:
50 return inline_box_ == other.inline_box_;
51 case InstanceType::kNG:
52 return line_cursor_ == other.line_cursor_;
53 }
54 NOTREACHED();
55 return false;
56 }
57
58 // Returns containing block rooted cursor instead of line rooted cursor for
59 // ease of handling, e.g. equiality check, move to next/previous line, etc.
GetCursor() const60 NGInlineCursor GetCursor() const {
61 NGInlineCursor cursor;
62 cursor.MoveTo(line_cursor_);
63 return cursor;
64 }
65
GetInlineBox() const66 const InlineBox& GetInlineBox() const {
67 DCHECK(IsOldLayout());
68 DCHECK(inline_box_);
69 return *inline_box_;
70 }
71
BidiLevel() const72 UBiDiLevel BidiLevel() const {
73 DCHECK(IsNotNull());
74 return IsOldLayout() ? GetInlineBox().BidiLevel()
75 : line_cursor_.Current().BidiLevel();
76 }
77
Direction() const78 TextDirection Direction() const {
79 DCHECK(IsNotNull());
80 return IsOldLayout() ? GetInlineBox().Direction()
81 : line_cursor_.Current().ResolvedDirection();
82 }
83
PrevLeafChild() const84 AbstractInlineBox PrevLeafChild() const {
85 DCHECK(IsNotNull());
86 if (IsOldLayout()) {
87 const InlineBox* result = GetInlineBox().PrevLeafChild();
88 return result ? AbstractInlineBox(*result) : AbstractInlineBox();
89 }
90 NGInlineCursor cursor(line_cursor_);
91 cursor.MoveToPreviousInlineLeaf();
92 return cursor ? AbstractInlineBox(cursor) : AbstractInlineBox();
93 }
94
PrevLeafChildIgnoringLineBreak() const95 AbstractInlineBox PrevLeafChildIgnoringLineBreak() const {
96 DCHECK(IsNotNull());
97 if (IsOldLayout()) {
98 const InlineBox* result = GetInlineBox().PrevLeafChildIgnoringLineBreak();
99 return result ? AbstractInlineBox(*result) : AbstractInlineBox();
100 }
101 NGInlineCursor cursor(line_cursor_);
102 cursor.MoveToPreviousInlineLeafIgnoringLineBreak();
103 return cursor ? AbstractInlineBox(cursor) : AbstractInlineBox();
104 }
105
NextLeafChild() const106 AbstractInlineBox NextLeafChild() const {
107 DCHECK(IsNotNull());
108 if (IsOldLayout()) {
109 const InlineBox* result = GetInlineBox().NextLeafChild();
110 return result ? AbstractInlineBox(*result) : AbstractInlineBox();
111 }
112 NGInlineCursor cursor(line_cursor_);
113 cursor.MoveToNextInlineLeaf();
114 return cursor ? AbstractInlineBox(cursor) : AbstractInlineBox();
115 }
116
NextLeafChildIgnoringLineBreak() const117 AbstractInlineBox NextLeafChildIgnoringLineBreak() const {
118 DCHECK(IsNotNull());
119 if (IsOldLayout()) {
120 const InlineBox* result = GetInlineBox().NextLeafChildIgnoringLineBreak();
121 return result ? AbstractInlineBox(*result) : AbstractInlineBox();
122 }
123 NGInlineCursor cursor(line_cursor_);
124 cursor.MoveToNextInlineLeafIgnoringLineBreak();
125 return cursor ? AbstractInlineBox(cursor) : AbstractInlineBox();
126 }
127
ParagraphDirection() const128 TextDirection ParagraphDirection() const {
129 DCHECK(IsNotNull());
130 if (IsOldLayout())
131 return ParagraphDirectionOf(GetInlineBox());
132 return GetLineBox(line_cursor_).Current().BaseDirection();
133 }
134
135 private:
CreateLineRootedCursor(const NGInlineCursor & cursor)136 static NGInlineCursor CreateLineRootedCursor(const NGInlineCursor& cursor) {
137 NGInlineCursor line_cursor = GetLineBox(cursor).CursorForDescendants();
138 line_cursor.MoveTo(cursor);
139 return line_cursor;
140 }
141
142 // Returns containing line box of |cursor| even if |cursor| is scoped inside
143 // line.
GetLineBox(const NGInlineCursor & cursor)144 static NGInlineCursor GetLineBox(const NGInlineCursor& cursor) {
145 NGInlineCursor line_box;
146 line_box.MoveTo(cursor);
147 line_box.MoveToContainingLine();
148 return line_box;
149 }
150
151 enum class InstanceType { kNull, kOldLayout, kNG };
152 InstanceType type_;
153
154 // Only one of |inline_box_| or |line_cursor_| is used, but we cannot make
155 // them union because of non-trivial destructor.
156 const InlineBox* inline_box_;
157
158 // Because of |MoveToContainingLine()| isn't cheap and we avoid to call each
159 // |MoveTo{Next,Previous}InlineLeaf()|, we hold containing line rooted cursor
160 // instead of containing block rooted cursor.
161 NGInlineCursor line_cursor_;
162 };
163
164 // |SideAffinity| represents the left or right side of a leaf inline
165 // box/fragment. For example, with text box/fragment "abc", "|abc" is the left
166 // side, and "abc|" is the right side.
167 enum SideAffinity { kLeft, kRight };
168
169 // Returns whether |box_position| is at the left or right side of its InlineBox.
GetSideAffinity(const InlineBoxPosition & box_position)170 SideAffinity GetSideAffinity(const InlineBoxPosition& box_position) {
171 DCHECK(box_position.inline_box);
172 const InlineBox* box = box_position.inline_box;
173 const int offset = box_position.offset_in_box;
174 DCHECK(offset == box->CaretLeftmostOffset() ||
175 offset == box->CaretRightmostOffset());
176 return offset == box->CaretLeftmostOffset() ? SideAffinity::kLeft
177 : SideAffinity::kRight;
178 }
179
180 // Returns whether |caret_position| is at the start of its fragment.
IsAtFragmentStart(const NGCaretPosition & caret_position)181 bool IsAtFragmentStart(const NGCaretPosition& caret_position) {
182 switch (caret_position.position_type) {
183 case NGCaretPositionType::kBeforeBox:
184 return true;
185 case NGCaretPositionType::kAfterBox:
186 return false;
187 case NGCaretPositionType::kAtTextOffset:
188 DCHECK(caret_position.text_offset.has_value());
189 return *caret_position.text_offset ==
190 caret_position.cursor.Current().TextStartOffset();
191 }
192 NOTREACHED();
193 return false;
194 }
195
196 // Returns whether |caret_position| is at the end of its fragment.
IsAtFragmentEnd(const NGCaretPosition & caret_position)197 bool IsAtFragmentEnd(const NGCaretPosition& caret_position) {
198 switch (caret_position.position_type) {
199 case NGCaretPositionType::kBeforeBox:
200 return false;
201 case NGCaretPositionType::kAfterBox:
202 return true;
203 case NGCaretPositionType::kAtTextOffset:
204 DCHECK(caret_position.text_offset.has_value());
205 return *caret_position.text_offset ==
206 caret_position.cursor.Current().TextEndOffset();
207 }
208 NOTREACHED();
209 return false;
210 }
211
212 // Returns whether |caret_position| is at the left or right side of fragment.
GetSideAffinity(const NGCaretPosition & caret_position)213 SideAffinity GetSideAffinity(const NGCaretPosition& caret_position) {
214 DCHECK(!caret_position.IsNull());
215 DCHECK(IsAtFragmentStart(caret_position) || IsAtFragmentEnd(caret_position));
216 const bool is_at_start = IsAtFragmentStart(caret_position);
217 const bool is_at_left_side =
218 is_at_start == IsLtr(caret_position.cursor.Current().ResolvedDirection());
219 return is_at_left_side ? SideAffinity::kLeft : SideAffinity::kRight;
220 }
221
222 // An abstraction of a caret position that is at the left or right side of a
223 // leaf inline box/fragment. The abstraction allows the object to be used in
224 // bidi adjustment algorithm for both legacy and NG.
225 class AbstractInlineBoxAndSideAffinity {
226 STACK_ALLOCATED();
227
228 public:
AbstractInlineBoxAndSideAffinity(const AbstractInlineBox & box,SideAffinity side)229 AbstractInlineBoxAndSideAffinity(const AbstractInlineBox& box,
230 SideAffinity side)
231 : box_(box), side_(side) {
232 DCHECK(box_.IsNotNull());
233 }
234
AbstractInlineBoxAndSideAffinity(const InlineBoxPosition & box_position)235 explicit AbstractInlineBoxAndSideAffinity(
236 const InlineBoxPosition& box_position)
237 : box_(*box_position.inline_box), side_(GetSideAffinity(box_position)) {
238 DCHECK(box_position.inline_box);
239 }
240
AbstractInlineBoxAndSideAffinity(const NGCaretPosition & caret_position)241 explicit AbstractInlineBoxAndSideAffinity(
242 const NGCaretPosition& caret_position)
243 : box_(caret_position.cursor), side_(GetSideAffinity(caret_position)) {
244 DCHECK(!caret_position.IsNull());
245 }
246
ToInlineBoxPosition() const247 InlineBoxPosition ToInlineBoxPosition() const {
248 DCHECK(box_.IsOldLayout());
249 const InlineBox& inline_box = box_.GetInlineBox();
250 return InlineBoxPosition(&inline_box,
251 side_ == SideAffinity::kLeft
252 ? inline_box.CaretLeftmostOffset()
253 : inline_box.CaretRightmostOffset());
254 }
255
ToNGCaretPosition() const256 NGCaretPosition ToNGCaretPosition() const {
257 DCHECK(box_.IsNG());
258 const bool is_at_start = IsLtr(box_.Direction()) == AtLeftSide();
259 NGInlineCursor cursor(box_.GetCursor());
260
261 if (!cursor.Current().IsText()) {
262 return {cursor,
263 is_at_start ? NGCaretPositionType::kBeforeBox
264 : NGCaretPositionType::kAfterBox,
265 base::nullopt};
266 }
267
268 return {cursor, NGCaretPositionType::kAtTextOffset,
269 is_at_start ? cursor.Current().TextStartOffset()
270 : cursor.Current().TextEndOffset()};
271 }
272
GetPosition() const273 PositionInFlatTree GetPosition() const {
274 DCHECK(box_.IsNotNull());
275 if (box_.IsNG())
276 return ToPositionInFlatTree(ToNGCaretPosition().ToPositionInDOMTree());
277
278 const InlineBoxPosition inline_box_position = ToInlineBoxPosition();
279 const LineLayoutItem item =
280 inline_box_position.inline_box->GetLineLayoutItem();
281 const int text_start_offset =
282 item.IsText() ? LineLayoutText(item).TextStartOffset() : 0;
283 const int offset_in_node =
284 text_start_offset + inline_box_position.offset_in_box;
285 return PositionInFlatTree::EditingPositionOf(item.GetNode(),
286 offset_in_node);
287 }
288
GetBox() const289 AbstractInlineBox GetBox() const { return box_; }
AtLeftSide() const290 bool AtLeftSide() const { return side_ == SideAffinity::kLeft; }
AtRightSide() const291 bool AtRightSide() const { return side_ == SideAffinity::kRight; }
292
293 private:
294 AbstractInlineBox box_;
295 SideAffinity side_;
296 };
297
298 struct TraverseRight;
299
300 // "Left" traversal strategy
301 struct TraverseLeft {
302 STATIC_ONLY(TraverseLeft);
303
304 using Backwards = TraverseRight;
305
Forwardblink::__anon08fd34980111::TraverseLeft306 static AbstractInlineBox Forward(const AbstractInlineBox& box) {
307 return box.PrevLeafChild();
308 }
309
ForwardIgnoringLineBreakblink::__anon08fd34980111::TraverseLeft310 static AbstractInlineBox ForwardIgnoringLineBreak(
311 const AbstractInlineBox& box) {
312 return box.PrevLeafChildIgnoringLineBreak();
313 }
314
315 static AbstractInlineBox Backward(const AbstractInlineBox& box);
316 static AbstractInlineBox BackwardIgnoringLineBreak(
317 const AbstractInlineBox& box);
318
ForwardSideAffinityblink::__anon08fd34980111::TraverseLeft319 static SideAffinity ForwardSideAffinity() { return SideAffinity::kLeft; }
320 };
321
322 // "Left" traversal strategy
323 struct TraverseRight {
324 STATIC_ONLY(TraverseRight);
325
326 using Backwards = TraverseLeft;
327
Forwardblink::__anon08fd34980111::TraverseRight328 static AbstractInlineBox Forward(const AbstractInlineBox& box) {
329 return box.NextLeafChild();
330 }
331
ForwardIgnoringLineBreakblink::__anon08fd34980111::TraverseRight332 static AbstractInlineBox ForwardIgnoringLineBreak(
333 const AbstractInlineBox& box) {
334 return box.NextLeafChildIgnoringLineBreak();
335 }
336
Backwardblink::__anon08fd34980111::TraverseRight337 static AbstractInlineBox Backward(const AbstractInlineBox& box) {
338 return Backwards::Forward(box);
339 }
340
BackwardIgnoringLineBreakblink::__anon08fd34980111::TraverseRight341 static AbstractInlineBox BackwardIgnoringLineBreak(
342 const AbstractInlineBox& box) {
343 return Backwards::ForwardIgnoringLineBreak(box);
344 }
345
ForwardSideAffinityblink::__anon08fd34980111::TraverseRight346 static SideAffinity ForwardSideAffinity() { return SideAffinity::kRight; }
347 };
348
349 // static
Backward(const AbstractInlineBox & box)350 AbstractInlineBox TraverseLeft::Backward(const AbstractInlineBox& box) {
351 return Backwards::Forward(box);
352 }
353
354 // static
BackwardIgnoringLineBreak(const AbstractInlineBox & box)355 AbstractInlineBox TraverseLeft::BackwardIgnoringLineBreak(
356 const AbstractInlineBox& box) {
357 return Backwards::ForwardIgnoringLineBreak(box);
358 }
359
360 template <typename TraversalStrategy>
361 using Backwards = typename TraversalStrategy::Backwards;
362
363 template <typename TraversalStrategy>
AbstractInlineBoxAndForwardSideAffinity(const AbstractInlineBox & box)364 AbstractInlineBoxAndSideAffinity AbstractInlineBoxAndForwardSideAffinity(
365 const AbstractInlineBox& box) {
366 return AbstractInlineBoxAndSideAffinity(
367 box, TraversalStrategy::ForwardSideAffinity());
368 }
369
370 template <typename TraversalStrategy>
AbstractInlineBoxAndBackwardSideAffinity(const AbstractInlineBox & box)371 AbstractInlineBoxAndSideAffinity AbstractInlineBoxAndBackwardSideAffinity(
372 const AbstractInlineBox& box) {
373 return AbstractInlineBoxAndForwardSideAffinity<Backwards<TraversalStrategy>>(
374 box);
375 }
376
377 // Template algorithms for traversing in bidi runs
378
379 // Traverses from |start|, and returns the first box with bidi level less than
380 // or equal to |bidi_level| (excluding |start| itself). Returns a null box when
381 // such a box doesn't exist.
382 template <typename TraversalStrategy>
FindBidiRun(const AbstractInlineBox & start,unsigned bidi_level)383 AbstractInlineBox FindBidiRun(const AbstractInlineBox& start,
384 unsigned bidi_level) {
385 DCHECK(start.IsNotNull());
386 for (AbstractInlineBox runner = TraversalStrategy::Forward(start);
387 runner.IsNotNull(); runner = TraversalStrategy::Forward(runner)) {
388 if (runner.BidiLevel() <= bidi_level)
389 return runner;
390 }
391 return AbstractInlineBox();
392 }
393
394 // Traverses from |start|, and returns the last non-linebreak box with bidi
395 // level greater than |bidi_level| (including |start| itself).
396 template <typename TraversalStrategy>
FindBoundaryOfBidiRunIgnoringLineBreak(const AbstractInlineBox & start,unsigned bidi_level)397 AbstractInlineBox FindBoundaryOfBidiRunIgnoringLineBreak(
398 const AbstractInlineBox& start,
399 unsigned bidi_level) {
400 DCHECK(start.IsNotNull());
401 AbstractInlineBox last_runner = start;
402 for (AbstractInlineBox runner =
403 TraversalStrategy::ForwardIgnoringLineBreak(start);
404 runner.IsNotNull();
405 runner = TraversalStrategy::ForwardIgnoringLineBreak(runner)) {
406 if (runner.BidiLevel() <= bidi_level)
407 return last_runner;
408 last_runner = runner;
409 }
410 return last_runner;
411 }
412
413 // Traverses from |start|, and returns the last box with bidi level greater than
414 // or equal to |bidi_level| (including |start| itself). Line break boxes may or
415 // may not be ignored, depending of the passed |forward| function.
FindBoundaryOfEntireBidiRunInternal(const AbstractInlineBox & start,unsigned bidi_level,AbstractInlineBox (* forward)(const AbstractInlineBox &))416 AbstractInlineBox FindBoundaryOfEntireBidiRunInternal(
417 const AbstractInlineBox& start,
418 unsigned bidi_level,
419 AbstractInlineBox (*forward)(const AbstractInlineBox&)) {
420 DCHECK(start.IsNotNull());
421 AbstractInlineBox last_runner = start;
422 for (AbstractInlineBox runner = forward(start); runner.IsNotNull();
423 runner = forward(runner)) {
424 if (runner.BidiLevel() < bidi_level)
425 return last_runner;
426 last_runner = runner;
427 }
428 return last_runner;
429 }
430
431 // Variant of |FindBoundaryOfEntireBidiRun| preserving line break boxes.
432 template <typename TraversalStrategy>
FindBoundaryOfEntireBidiRun(const AbstractInlineBox & start,unsigned bidi_level)433 AbstractInlineBox FindBoundaryOfEntireBidiRun(const AbstractInlineBox& start,
434 unsigned bidi_level) {
435 return FindBoundaryOfEntireBidiRunInternal(start, bidi_level,
436 TraversalStrategy::Forward);
437 }
438
439 // Variant of |FindBoundaryOfEntireBidiRun| ignoring line break boxes.
440 template <typename TraversalStrategy>
FindBoundaryOfEntireBidiRunIgnoringLineBreak(const AbstractInlineBox & start,unsigned bidi_level)441 AbstractInlineBox FindBoundaryOfEntireBidiRunIgnoringLineBreak(
442 const AbstractInlineBox& start,
443 unsigned bidi_level) {
444 return FindBoundaryOfEntireBidiRunInternal(
445 start, bidi_level, TraversalStrategy::ForwardIgnoringLineBreak);
446 }
447
448 // Adjustment algorithm at the end of caret position resolution.
449 template <typename TraversalStrategy>
450 class CaretPositionResolutionAdjuster {
451 STATIC_ONLY(CaretPositionResolutionAdjuster);
452
453 public:
UnadjustedCaretPosition(const AbstractInlineBox & box)454 static AbstractInlineBoxAndSideAffinity UnadjustedCaretPosition(
455 const AbstractInlineBox& box) {
456 return AbstractInlineBoxAndBackwardSideAffinity<TraversalStrategy>(box);
457 }
458
459 // Returns true if |box| starts different direction of embedded text run.
460 // See [1] for details.
461 // [1] UNICODE BIDIRECTIONAL ALGORITHM, http://unicode.org/reports/tr9/
462 static bool IsStartOfDifferentDirection(const AbstractInlineBox&);
463
AdjustForPrimaryDirectionAlgorithm(const AbstractInlineBox & box)464 static AbstractInlineBoxAndSideAffinity AdjustForPrimaryDirectionAlgorithm(
465 const AbstractInlineBox& box) {
466 if (IsStartOfDifferentDirection(box))
467 return UnadjustedCaretPosition(box);
468
469 const unsigned level = TraversalStrategy::Backward(box).BidiLevel();
470 const AbstractInlineBox forward_box =
471 FindBidiRun<TraversalStrategy>(box, level);
472
473 // For example, abc FED 123 ^ CBA when adjusting right side of 123
474 if (forward_box.IsNotNull() && forward_box.BidiLevel() == level)
475 return UnadjustedCaretPosition(box);
476
477 // For example, abc 123 ^ CBA when adjusting right side of 123
478 const AbstractInlineBox result_box =
479 FindBoundaryOfEntireBidiRun<Backwards<TraversalStrategy>>(box, level);
480 return AbstractInlineBoxAndBackwardSideAffinity<TraversalStrategy>(
481 result_box);
482 }
483
AdjustFor(const AbstractInlineBox & box)484 static AbstractInlineBoxAndSideAffinity AdjustFor(
485 const AbstractInlineBox& box) {
486 DCHECK(box.IsNotNull());
487
488 const TextDirection primary_direction = box.ParagraphDirection();
489 if (box.Direction() == primary_direction)
490 return AdjustForPrimaryDirectionAlgorithm(box);
491
492 const unsigned char level = box.BidiLevel();
493 const AbstractInlineBox backward_box =
494 TraversalStrategy::BackwardIgnoringLineBreak(box);
495 if (backward_box.IsNull() || backward_box.BidiLevel() < level) {
496 // Backward side of a secondary run. Set to the forward side of the entire
497 // run.
498 const AbstractInlineBox result_box =
499 FindBoundaryOfEntireBidiRunIgnoringLineBreak<TraversalStrategy>(
500 box, level);
501 return AbstractInlineBoxAndForwardSideAffinity<TraversalStrategy>(
502 result_box);
503 }
504
505 if (backward_box.BidiLevel() <= level)
506 return UnadjustedCaretPosition(box);
507
508 // Forward side of a "tertiary" run. Set to the backward side of that run.
509 const AbstractInlineBox result_box =
510 FindBoundaryOfBidiRunIgnoringLineBreak<Backwards<TraversalStrategy>>(
511 box, level);
512 return AbstractInlineBoxAndBackwardSideAffinity<TraversalStrategy>(
513 result_box);
514 }
515 };
516
517 // TODO(editing-dev): Try to unify the algorithms for both directions.
518 template <>
IsStartOfDifferentDirection(const AbstractInlineBox & box)519 bool CaretPositionResolutionAdjuster<TraverseLeft>::IsStartOfDifferentDirection(
520 const AbstractInlineBox& box) {
521 DCHECK(box.IsNotNull());
522 const AbstractInlineBox backward_box = TraverseRight::Forward(box);
523 if (backward_box.IsNull())
524 return true;
525 return backward_box.BidiLevel() >= box.BidiLevel();
526 }
527
528 template <>
529 bool CaretPositionResolutionAdjuster<
IsStartOfDifferentDirection(const AbstractInlineBox & box)530 TraverseRight>::IsStartOfDifferentDirection(const AbstractInlineBox& box) {
531 DCHECK(box.IsNotNull());
532 const AbstractInlineBox backward_box = TraverseLeft::Forward(box);
533 if (backward_box.IsNull())
534 return true;
535 if (backward_box.Direction() == box.Direction())
536 return true;
537 return backward_box.BidiLevel() > box.BidiLevel();
538 }
539
540 // Adjustment algorithm at the end of hit tests.
541 template <typename TraversalStrategy>
542 class HitTestAdjuster {
543 STATIC_ONLY(HitTestAdjuster);
544
545 public:
UnadjustedHitTestPosition(const AbstractInlineBox & box)546 static AbstractInlineBoxAndSideAffinity UnadjustedHitTestPosition(
547 const AbstractInlineBox& box) {
548 return AbstractInlineBoxAndBackwardSideAffinity<TraversalStrategy>(box);
549 }
550
AdjustFor(const AbstractInlineBox & box)551 static AbstractInlineBoxAndSideAffinity AdjustFor(
552 const AbstractInlineBox& box) {
553 // TODO(editing-dev): Fix handling of left on 12CBA
554 if (box.Direction() == box.ParagraphDirection())
555 return UnadjustedHitTestPosition(box);
556
557 const UBiDiLevel level = box.BidiLevel();
558
559 const AbstractInlineBox backward_box =
560 TraversalStrategy::BackwardIgnoringLineBreak(box);
561 if (backward_box.IsNotNull() && backward_box.BidiLevel() == level)
562 return UnadjustedHitTestPosition(box);
563
564 if (backward_box.IsNotNull() && backward_box.BidiLevel() > level) {
565 // e.g. left of B in aDC12BAb when adjusting left side
566 const AbstractInlineBox backward_most_box =
567 FindBoundaryOfBidiRunIgnoringLineBreak<Backwards<TraversalStrategy>>(
568 backward_box, level);
569 return AbstractInlineBoxAndForwardSideAffinity<TraversalStrategy>(
570 backward_most_box);
571 }
572
573 // backward_box.IsNull() || backward_box.BidiLevel() < level
574 // e.g. left of D in aDC12BAb when adjusting left side
575 const AbstractInlineBox forward_most_box =
576 FindBoundaryOfEntireBidiRunIgnoringLineBreak<TraversalStrategy>(box,
577 level);
578 return box.Direction() == forward_most_box.Direction()
579 ? AbstractInlineBoxAndForwardSideAffinity<TraversalStrategy>(
580 forward_most_box)
581 : AbstractInlineBoxAndBackwardSideAffinity<TraversalStrategy>(
582 forward_most_box);
583 }
584 };
585
586 // Adjustment algorithm at the end of creating range selection
587 class RangeSelectionAdjuster {
588 STATIC_ONLY(RangeSelectionAdjuster);
589
590 public:
AdjustFor(const PositionInFlatTreeWithAffinity & visible_base,const PositionInFlatTreeWithAffinity & visible_extent)591 static SelectionInFlatTree AdjustFor(
592 const PositionInFlatTreeWithAffinity& visible_base,
593 const PositionInFlatTreeWithAffinity& visible_extent) {
594 const SelectionInFlatTree& unchanged_selection =
595 SelectionInFlatTree::Builder()
596 .SetBaseAndExtent(visible_base.GetPosition(),
597 visible_extent.GetPosition())
598 .Build();
599
600 if (RuntimeEnabledFeatures::BidiCaretAffinityEnabled()) {
601 if (NGInlineFormattingContextOf(visible_base.GetPosition()) ||
602 NGInlineFormattingContextOf(visible_extent.GetPosition()))
603 return unchanged_selection;
604 }
605
606 RenderedPosition base = RenderedPosition::Create(visible_base);
607 RenderedPosition extent = RenderedPosition::Create(visible_extent);
608
609 if (base.IsNull() || extent.IsNull() || base == extent ||
610 (!base.AtBidiBoundary() && !extent.AtBidiBoundary())) {
611 return unchanged_selection;
612 }
613
614 if (base.AtBidiBoundary()) {
615 if (ShouldAdjustBaseAtBidiBoundary(base, extent)) {
616 const PositionInFlatTree adjusted_base =
617 CreateVisiblePosition(base.GetPosition()).DeepEquivalent();
618 return SelectionInFlatTree::Builder()
619 .SetBaseAndExtent(adjusted_base, visible_extent.GetPosition())
620 .Build();
621 }
622 return unchanged_selection;
623 }
624
625 if (ShouldAdjustExtentAtBidiBoundary(base, extent)) {
626 const PositionInFlatTree adjusted_extent =
627 CreateVisiblePosition(extent.GetPosition()).DeepEquivalent();
628 return SelectionInFlatTree::Builder()
629 .SetBaseAndExtent(visible_base.GetPosition(), adjusted_extent)
630 .Build();
631 }
632
633 return unchanged_selection;
634 }
635
636 private:
637 class RenderedPosition {
638 STACK_ALLOCATED();
639
640 public:
641 RenderedPosition() = default;
642 static RenderedPosition Create(const PositionInFlatTreeWithAffinity&);
643
IsNull() const644 bool IsNull() const { return box_.IsNull(); }
operator ==(const RenderedPosition & other) const645 bool operator==(const RenderedPosition& other) const {
646 return box_ == other.box_ &&
647 bidi_boundary_type_ == other.bidi_boundary_type_;
648 }
649
AtBidiBoundary() const650 bool AtBidiBoundary() const {
651 return bidi_boundary_type_ != BidiBoundaryType::kNotBoundary;
652 }
653
654 // Given |other|, which is a boundary of a bidi run, returns true if |this|
655 // can be the other boundary of that run by checking some conditions.
IsPossiblyOtherBoundaryOf(const RenderedPosition & other) const656 bool IsPossiblyOtherBoundaryOf(const RenderedPosition& other) const {
657 DCHECK(other.AtBidiBoundary());
658 if (!AtBidiBoundary())
659 return false;
660 if (bidi_boundary_type_ == other.bidi_boundary_type_)
661 return false;
662 return box_.BidiLevel() >= other.box_.BidiLevel();
663 }
664
665 // Callable only when |this| is at boundary of a bidi run. Returns true if
666 // |other| is in that bidi run.
BidiRunContains(const RenderedPosition & other) const667 bool BidiRunContains(const RenderedPosition& other) const {
668 DCHECK(AtBidiBoundary());
669 DCHECK(!other.IsNull());
670 UBiDiLevel level = box_.BidiLevel();
671 if (level > other.box_.BidiLevel())
672 return false;
673 const AbstractInlineBox boundary_of_other =
674 bidi_boundary_type_ == BidiBoundaryType::kLeftBoundary
675 ? FindBoundaryOfEntireBidiRunIgnoringLineBreak<TraverseLeft>(
676 other.box_, level)
677 : FindBoundaryOfEntireBidiRunIgnoringLineBreak<TraverseRight>(
678 other.box_, level);
679 return box_ == boundary_of_other;
680 }
681
GetPosition() const682 PositionInFlatTree GetPosition() const {
683 DCHECK(AtBidiBoundary());
684 DCHECK(box_.IsNotNull());
685 const SideAffinity side =
686 bidi_boundary_type_ == BidiBoundaryType::kLeftBoundary
687 ? SideAffinity::kLeft
688 : SideAffinity::kRight;
689 return AbstractInlineBoxAndSideAffinity(box_, side).GetPosition();
690 }
691
692 private:
693 enum class BidiBoundaryType { kNotBoundary, kLeftBoundary, kRightBoundary };
RenderedPosition(const AbstractInlineBox & box,BidiBoundaryType type)694 RenderedPosition(const AbstractInlineBox& box, BidiBoundaryType type)
695 : box_(box), bidi_boundary_type_(type) {}
696
GetPotentialBidiBoundaryType(const InlineBoxPosition & box_position)697 static BidiBoundaryType GetPotentialBidiBoundaryType(
698 const InlineBoxPosition& box_position) {
699 DCHECK(box_position.inline_box);
700 const InlineBox& box = *box_position.inline_box;
701 const int offset = box_position.offset_in_box;
702 if (offset == box.CaretLeftmostOffset())
703 return BidiBoundaryType::kLeftBoundary;
704 if (offset == box.CaretRightmostOffset())
705 return BidiBoundaryType::kRightBoundary;
706 return BidiBoundaryType::kNotBoundary;
707 }
708
GetPotentialBidiBoundaryType(const NGCaretPosition & caret_position)709 static BidiBoundaryType GetPotentialBidiBoundaryType(
710 const NGCaretPosition& caret_position) {
711 DCHECK(!caret_position.IsNull());
712 DCHECK(!RuntimeEnabledFeatures::BidiCaretAffinityEnabled());
713 if (!IsAtFragmentStart(caret_position) &&
714 !IsAtFragmentEnd(caret_position))
715 return BidiBoundaryType::kNotBoundary;
716 return GetSideAffinity(caret_position) == SideAffinity::kLeft
717 ? BidiBoundaryType::kLeftBoundary
718 : BidiBoundaryType::kRightBoundary;
719 }
720
721 // Helper function for Create().
CreateUncanonicalized(const PositionInFlatTreeWithAffinity & position)722 static RenderedPosition CreateUncanonicalized(
723 const PositionInFlatTreeWithAffinity& position) {
724 if (position.IsNull() || !position.AnchorNode()->GetLayoutObject())
725 return RenderedPosition();
726 const PositionInFlatTreeWithAffinity adjusted =
727 ComputeInlineAdjustedPosition(position);
728 if (adjusted.IsNull())
729 return RenderedPosition();
730
731 if (NGInlineFormattingContextOf(adjusted.GetPosition())) {
732 const NGCaretPosition caret_position = ComputeNGCaretPosition(adjusted);
733 if (caret_position.IsNull())
734 return RenderedPosition();
735 return RenderedPosition(AbstractInlineBox(caret_position.cursor),
736 GetPotentialBidiBoundaryType(caret_position));
737 }
738
739 const InlineBoxPosition box_position = ComputeInlineBoxPosition(adjusted);
740 if (!box_position.inline_box)
741 return RenderedPosition();
742 return RenderedPosition(AbstractInlineBox(*box_position.inline_box),
743 GetPotentialBidiBoundaryType(box_position));
744 }
745
746 AbstractInlineBox box_;
747 BidiBoundaryType bidi_boundary_type_ = BidiBoundaryType::kNotBoundary;
748 };
749
ShouldAdjustBaseAtBidiBoundary(const RenderedPosition & base,const RenderedPosition & extent)750 static bool ShouldAdjustBaseAtBidiBoundary(const RenderedPosition& base,
751 const RenderedPosition& extent) {
752 DCHECK(base.AtBidiBoundary());
753 if (extent.IsPossiblyOtherBoundaryOf(base))
754 return false;
755 return base.BidiRunContains(extent);
756 }
757
ShouldAdjustExtentAtBidiBoundary(const RenderedPosition & base,const RenderedPosition & extent)758 static bool ShouldAdjustExtentAtBidiBoundary(const RenderedPosition& base,
759 const RenderedPosition& extent) {
760 if (!extent.AtBidiBoundary())
761 return false;
762 return extent.BidiRunContains(base);
763 }
764 };
765
766 RangeSelectionAdjuster::RenderedPosition
Create(const PositionInFlatTreeWithAffinity & position)767 RangeSelectionAdjuster::RenderedPosition::Create(
768 const PositionInFlatTreeWithAffinity& position) {
769 const RenderedPosition uncanonicalized = CreateUncanonicalized(position);
770 const BidiBoundaryType potential_type = uncanonicalized.bidi_boundary_type_;
771 if (potential_type == BidiBoundaryType::kNotBoundary)
772 return uncanonicalized;
773 const AbstractInlineBox& box = uncanonicalized.box_;
774 DCHECK(box.IsNotNull());
775
776 // When at bidi boundary, ensure that |box_| belongs to the higher-level bidi
777 // run.
778
779 // For example, abc FED |ghi should be changed into abc FED| ghi
780 if (potential_type == BidiBoundaryType::kLeftBoundary) {
781 const AbstractInlineBox prev_box = box.PrevLeafChildIgnoringLineBreak();
782 if (prev_box.IsNotNull() && prev_box.BidiLevel() > box.BidiLevel())
783 return RenderedPosition(prev_box, BidiBoundaryType::kRightBoundary);
784 BidiBoundaryType type =
785 prev_box.IsNotNull() && prev_box.BidiLevel() == box.BidiLevel()
786 ? BidiBoundaryType::kNotBoundary
787 : BidiBoundaryType::kLeftBoundary;
788 return RenderedPosition(box, type);
789 }
790
791 // potential_type == BidiBoundaryType::kRightBoundary
792 // For example, abc| FED ghi should be changed into abc |FED ghi
793 const AbstractInlineBox next_box = box.NextLeafChildIgnoringLineBreak();
794 if (next_box.IsNotNull() && next_box.BidiLevel() > box.BidiLevel())
795 return RenderedPosition(next_box, BidiBoundaryType::kLeftBoundary);
796 BidiBoundaryType type =
797 next_box.IsNotNull() && next_box.BidiLevel() == box.BidiLevel()
798 ? BidiBoundaryType::kNotBoundary
799 : BidiBoundaryType::kRightBoundary;
800 return RenderedPosition(box, type);
801 }
802
803 } // namespace
804
AdjustForCaretPositionResolution(const InlineBoxPosition & caret_position)805 InlineBoxPosition BidiAdjustment::AdjustForCaretPositionResolution(
806 const InlineBoxPosition& caret_position) {
807 const AbstractInlineBoxAndSideAffinity unadjusted(caret_position);
808 const AbstractInlineBoxAndSideAffinity adjusted =
809 unadjusted.AtLeftSide()
810 ? CaretPositionResolutionAdjuster<TraverseRight>::AdjustFor(
811 unadjusted.GetBox())
812 : CaretPositionResolutionAdjuster<TraverseLeft>::AdjustFor(
813 unadjusted.GetBox());
814 return adjusted.ToInlineBoxPosition();
815 }
816
AdjustForCaretPositionResolution(const NGCaretPosition & caret_position)817 NGCaretPosition BidiAdjustment::AdjustForCaretPositionResolution(
818 const NGCaretPosition& caret_position) {
819 DCHECK(!RuntimeEnabledFeatures::BidiCaretAffinityEnabled());
820 const AbstractInlineBoxAndSideAffinity unadjusted(caret_position);
821 const AbstractInlineBoxAndSideAffinity adjusted =
822 unadjusted.AtLeftSide()
823 ? CaretPositionResolutionAdjuster<TraverseRight>::AdjustFor(
824 unadjusted.GetBox())
825 : CaretPositionResolutionAdjuster<TraverseLeft>::AdjustFor(
826 unadjusted.GetBox());
827 return adjusted.ToNGCaretPosition();
828 }
829
AdjustForHitTest(const InlineBoxPosition & caret_position)830 InlineBoxPosition BidiAdjustment::AdjustForHitTest(
831 const InlineBoxPosition& caret_position) {
832 const AbstractInlineBoxAndSideAffinity unadjusted(caret_position);
833 const AbstractInlineBoxAndSideAffinity adjusted =
834 unadjusted.AtLeftSide()
835 ? HitTestAdjuster<TraverseRight>::AdjustFor(unadjusted.GetBox())
836 : HitTestAdjuster<TraverseLeft>::AdjustFor(unadjusted.GetBox());
837 return adjusted.ToInlineBoxPosition();
838 }
839
AdjustForHitTest(const NGCaretPosition & caret_position)840 NGCaretPosition BidiAdjustment::AdjustForHitTest(
841 const NGCaretPosition& caret_position) {
842 DCHECK(!RuntimeEnabledFeatures::BidiCaretAffinityEnabled());
843 const AbstractInlineBoxAndSideAffinity unadjusted(caret_position);
844 const AbstractInlineBoxAndSideAffinity adjusted =
845 unadjusted.AtLeftSide()
846 ? HitTestAdjuster<TraverseRight>::AdjustFor(unadjusted.GetBox())
847 : HitTestAdjuster<TraverseLeft>::AdjustFor(unadjusted.GetBox());
848 return adjusted.ToNGCaretPosition();
849 }
850
AdjustForRangeSelection(const PositionInFlatTreeWithAffinity & base,const PositionInFlatTreeWithAffinity & extent)851 SelectionInFlatTree BidiAdjustment::AdjustForRangeSelection(
852 const PositionInFlatTreeWithAffinity& base,
853 const PositionInFlatTreeWithAffinity& extent) {
854 return RangeSelectionAdjuster::AdjustFor(base, extent);
855 }
856
857 // TODO(xiaochengh): Move this function to a better place
ParagraphDirectionOf(const InlineBox & box)858 TextDirection ParagraphDirectionOf(const InlineBox& box) {
859 const ComputedStyle& block_style = *box.Root().Block().Style();
860 if (block_style.GetUnicodeBidi() != UnicodeBidi::kPlaintext)
861 return block_style.Direction();
862
863 // There is no reliable way to get the paragraph direction in legacy
864 // layout when 'unicode-bidi: plaintext' is set. Use the lowest-level
865 // inline box's direction as a workaround.
866 UBiDiLevel min_level = 128;
867 for (const InlineBox* runner = box.Root().FirstLeafChild(); runner;
868 runner = runner->NextLeafChild()) {
869 min_level = std::min(min_level, runner->BidiLevel());
870 }
871 return DirectionFromLevel(min_level);
872 }
873
874 } // namespace blink
875