1/*
2 * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
3 * Copyright (C) 2003, 2004, 2006, 2007, 2008, 2009, 2010 Apple Inc. All right reserved.
4 * Copyright (C) 2010 Google Inc. All rights reserved.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB. If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 *
21 */
22
23#pragma once
24
25#include "BidiRun.h"
26#include "RenderBlockFlow.h"
27#include "RenderChildIterator.h"
28#include "RenderInline.h"
29#include "RenderText.h"
30#include <wtf/StdLibExtras.h>
31
32namespace WebCore {
33
34struct BidiIsolatedRun {
35 BidiIsolatedRun(RenderObject& object, unsigned position, RenderElement& root, BidiRun& runToReplace)
36 : object(object)
37 , root(root)
38 , runToReplace(runToReplace)
39 , position(position)
40 {
41 }
42
43 RenderObject& object;
44 RenderElement& root;
45 BidiRun& runToReplace;
46 unsigned position;
47};
48
49// This class is used to RenderInline subtrees, stepping by character within the
50// text children. InlineIterator will use bidiNext to find the next RenderText
51// optionally notifying a BidiResolver every time it steps into/out of a RenderInline.
52class InlineIterator {
53public:
54 InlineIterator()
55 {
56 }
57
58 InlineIterator(RenderElement* root, RenderObject* o, unsigned p)
59 : m_root(root)
60 , m_renderer(o)
61 , m_pos(p)
62 , m_refersToEndOfPreviousNode(false)
63 {
64 }
65
66 void clear()
67 {
68 setRenderer(nullptr);
69 setOffset(0);
70 setNextBreakablePosition(std::numeric_limits<unsigned>::max());
71 }
72 void moveToStartOf(RenderObject& object)
73 {
74 moveTo(object, 0);
75 }
76
77 void moveTo(RenderObject& object, unsigned offset, Optional<unsigned> nextBreak = Optional<unsigned>())
78 {
79 setRenderer(&object);
80 setOffset(offset);
81 setNextBreakablePosition(nextBreak);
82 }
83
84 RenderObject* renderer() const { return m_renderer; }
85 void setRenderer(RenderObject* renderer) { m_renderer = renderer; }
86 unsigned offset() const { return m_pos; }
87 void setOffset(unsigned position);
88 RenderElement* root() const { return m_root; }
89 Optional<unsigned> nextBreakablePosition() const { return m_nextBreakablePosition; }
90 void setNextBreakablePosition(Optional<unsigned> position) { m_nextBreakablePosition = position; }
91 bool refersToEndOfPreviousNode() const { return m_refersToEndOfPreviousNode; }
92 void setRefersToEndOfPreviousNode();
93
94 void fastIncrementInTextNode();
95 void increment(InlineBidiResolver* = nullptr);
96 void fastDecrement();
97 bool atEnd() const;
98
99 bool atTextParagraphSeparator() const
100 {
101 return is<RenderText>(m_renderer) && m_renderer->preservesNewline() && downcast<RenderText>(*m_renderer).characterAt(m_pos) == '\n';
102 }
103
104 bool atParagraphSeparator() const
105 {
106 return (m_renderer && m_renderer->isBR()) || atTextParagraphSeparator();
107 }
108
109 UChar current() const;
110 UChar previousInSameNode() const;
111 ALWAYS_INLINE UCharDirection direction() const;
112
113private:
114 UChar characterAt(unsigned) const;
115
116 UCharDirection surrogateTextDirection(UChar currentCodeUnit) const;
117
118 RenderElement* m_root { nullptr };
119 RenderObject* m_renderer { nullptr };
120
121 Optional<unsigned> m_nextBreakablePosition;
122 unsigned m_pos { 0 };
123
124 // There are a couple places where we want to decrement an InlineIterator.
125 // Usually this take the form of decrementing m_pos; however, m_pos might be 0.
126 // However, we shouldn't ever need to decrement an InlineIterator more than
127 // once, so rather than implementing a decrement() function which traverses
128 // nodes, we can simply keep track of this state and handle it.
129 bool m_refersToEndOfPreviousNode { false };
130};
131
132inline bool operator==(const InlineIterator& it1, const InlineIterator& it2)
133{
134 return it1.offset() == it2.offset() && it1.renderer() == it2.renderer();
135}
136
137inline bool operator!=(const InlineIterator& it1, const InlineIterator& it2)
138{
139 return it1.offset() != it2.offset() || it1.renderer() != it2.renderer();
140}
141
142static inline UCharDirection embedCharFromDirection(TextDirection direction, EUnicodeBidi unicodeBidi)
143{
144 if (unicodeBidi == Embed)
145 return direction == TextDirection::RTL ? U_RIGHT_TO_LEFT_EMBEDDING : U_LEFT_TO_RIGHT_EMBEDDING;
146 return direction == TextDirection::RTL ? U_RIGHT_TO_LEFT_OVERRIDE : U_LEFT_TO_RIGHT_OVERRIDE;
147}
148
149template <class Observer>
150static inline void notifyObserverEnteredObject(Observer* observer, RenderObject* object)
151{
152 if (!observer || !object || !object->isRenderInline())
153 return;
154
155 const RenderStyle& style = object->style();
156 EUnicodeBidi unicodeBidi = style.unicodeBidi();
157 if (unicodeBidi == UBNormal) {
158 // http://dev.w3.org/csswg/css3-writing-modes/#unicode-bidi
159 // "The element does not open an additional level of embedding with respect to the bidirectional algorithm."
160 // Thus we ignore any possible dir= attribute on the span.
161 return;
162 }
163 if (isIsolated(unicodeBidi)) {
164 // Make sure that explicit embeddings are committed before we enter the isolated content.
165 observer->commitExplicitEmbedding();
166 observer->enterIsolate();
167 // Embedding/Override characters implied by dir= will be handled when
168 // we process the isolated span, not when laying out the "parent" run.
169 return;
170 }
171
172 if (!observer->inIsolate())
173 observer->embed(embedCharFromDirection(style.direction(), unicodeBidi), FromStyleOrDOM);
174}
175
176template <class Observer>
177static inline void notifyObserverWillExitObject(Observer* observer, RenderObject* object)
178{
179 if (!observer || !object || !object->isRenderInline())
180 return;
181
182 EUnicodeBidi unicodeBidi = object->style().unicodeBidi();
183 if (unicodeBidi == UBNormal)
184 return; // Nothing to do for unicode-bidi: normal
185 if (isIsolated(unicodeBidi)) {
186 observer->exitIsolate();
187 return;
188 }
189
190 // Otherwise we pop any embed/override character we added when we opened this tag.
191 if (!observer->inIsolate())
192 observer->embed(U_POP_DIRECTIONAL_FORMAT, FromStyleOrDOM);
193}
194
195static inline bool isIteratorTarget(RenderObject* object)
196{
197 ASSERT(object); // The iterator will of course return 0, but its not an expected argument to this function.
198 return object->isTextOrLineBreak() || object->isFloating() || object->isOutOfFlowPositioned() || object->isReplaced();
199}
200
201// This enum is only used for bidiNextShared()
202enum EmptyInlineBehavior {
203 SkipEmptyInlines,
204 IncludeEmptyInlines,
205};
206
207static bool isEmptyInline(const RenderInline& renderer)
208{
209 for (auto& current : childrenOfType<RenderObject>(renderer)) {
210 if (current.isFloatingOrOutOfFlowPositioned())
211 continue;
212 if (is<RenderText>(current)) {
213 if (!downcast<RenderText>(current).isAllCollapsibleWhitespace())
214 return false;
215 continue;
216 }
217 if (!is<RenderInline>(current) || !isEmptyInline(downcast<RenderInline>(current)))
218 return false;
219 }
220 return true;
221}
222
223// FIXME: This function is misleadingly named. It has little to do with bidi.
224// This function will iterate over inlines within a block, optionally notifying
225// a bidi resolver as it enters/exits inlines (so it can push/pop embedding levels).
226template <class Observer>
227static inline RenderObject* bidiNextShared(RenderElement& root, RenderObject* current, Observer* observer = nullptr, EmptyInlineBehavior emptyInlineBehavior = SkipEmptyInlines, bool* endOfInlinePtr = nullptr)
228{
229 RenderObject* next = nullptr;
230 // oldEndOfInline denotes if when we last stopped iterating if we were at the end of an inline.
231 bool oldEndOfInline = endOfInlinePtr ? *endOfInlinePtr : false;
232 bool endOfInline = false;
233
234 while (current) {
235 next = nullptr;
236 if (!oldEndOfInline && !isIteratorTarget(current)) {
237 next = downcast<RenderElement>(*current).firstChild();
238 notifyObserverEnteredObject(observer, next);
239 }
240
241 // We hit this when either current has no children, or when current is not a renderer we care about.
242 if (!next) {
243 // If it is a renderer we care about, and we're doing our inline-walk, return it.
244 if (emptyInlineBehavior == IncludeEmptyInlines && !oldEndOfInline && is<RenderInline>(*current)) {
245 next = current;
246 endOfInline = true;
247 break;
248 }
249
250 while (current && current != &root) {
251 notifyObserverWillExitObject(observer, current);
252
253 next = current->nextSibling();
254 if (next) {
255 notifyObserverEnteredObject(observer, next);
256 break;
257 }
258
259 current = current->parent();
260 if (emptyInlineBehavior == IncludeEmptyInlines && current && current != &root && is<RenderInline>(*current)) {
261 next = current;
262 endOfInline = true;
263 break;
264 }
265 }
266 }
267
268 if (!next)
269 break;
270
271 if (isIteratorTarget(next)
272 || (is<RenderInline>(*next) && (emptyInlineBehavior == IncludeEmptyInlines || isEmptyInline(downcast<RenderInline>(*next)))))
273 break;
274 current = next;
275 }
276
277 if (endOfInlinePtr)
278 *endOfInlinePtr = endOfInline;
279
280 return next;
281}
282
283template <class Observer>
284static inline RenderObject* bidiNextSkippingEmptyInlines(RenderElement& root, RenderObject* current, Observer* observer)
285{
286 // The SkipEmptyInlines callers never care about endOfInlinePtr.
287 return bidiNextShared(root, current, observer, SkipEmptyInlines);
288}
289
290// This makes callers cleaner as they don't have to specify a type for the observer when not providing one.
291static inline RenderObject* bidiNextSkippingEmptyInlines(RenderElement& root, RenderObject* current)
292{
293 InlineBidiResolver* observer = nullptr;
294 return bidiNextSkippingEmptyInlines(root, current, observer);
295}
296
297static inline RenderObject* bidiNextIncludingEmptyInlines(RenderElement& root, RenderObject* current, bool* endOfInlinePtr = nullptr)
298{
299 InlineBidiResolver* observer = nullptr; // Callers who include empty inlines, never use an observer.
300 return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr);
301}
302
303static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderElement& root, InlineBidiResolver* resolver = nullptr)
304{
305 RenderObject* renderer = root.firstChild();
306 if (!renderer)
307 return nullptr;
308
309 if (is<RenderInline>(*renderer)) {
310 notifyObserverEnteredObject(resolver, renderer);
311 if (!isEmptyInline(downcast<RenderInline>(*renderer)))
312 renderer = bidiNextSkippingEmptyInlines(root, renderer, resolver);
313 else {
314 // Never skip empty inlines.
315 if (resolver)
316 resolver->commitExplicitEmbedding();
317 return renderer;
318 }
319 }
320
321 // FIXME: Unify this with the bidiNext call above.
322 if (renderer && !isIteratorTarget(renderer))
323 renderer = bidiNextSkippingEmptyInlines(root, renderer, resolver);
324
325 if (resolver)
326 resolver->commitExplicitEmbedding();
327 return renderer;
328}
329
330// FIXME: This method needs to be renamed when bidiNext finds a good name.
331static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderElement& root)
332{
333 RenderObject* o = root.firstChild();
334 // If either there are no children to walk, or the first one is correct
335 // then just return it.
336 if (!o || o->isRenderInline() || isIteratorTarget(o))
337 return o;
338
339 return bidiNextIncludingEmptyInlines(root, o);
340}
341
342inline void InlineIterator::fastIncrementInTextNode()
343{
344 ASSERT(m_renderer);
345 ASSERT(m_pos <= downcast<RenderText>(*m_renderer).text().length());
346 ++m_pos;
347}
348
349inline void InlineIterator::setOffset(unsigned position)
350{
351 ASSERT(position <= UINT_MAX - 10); // Sanity check
352 m_pos = position;
353}
354
355inline void InlineIterator::setRefersToEndOfPreviousNode()
356{
357 ASSERT(!m_pos);
358 ASSERT(!m_refersToEndOfPreviousNode);
359 m_refersToEndOfPreviousNode = true;
360}
361
362// FIXME: This is used by RenderBlock for simplified layout, and has nothing to do with bidi
363// it shouldn't use functions called bidiFirst and bidiNext.
364class InlineWalker {
365public:
366 InlineWalker(RenderElement& root)
367 : m_root(root)
368 , m_current(nullptr)
369 , m_atEndOfInline(false)
370 {
371 // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well.
372 m_current = bidiFirstIncludingEmptyInlines(m_root);
373 }
374
375 RenderElement& root() { return m_root; }
376 RenderObject* current() { return m_current; }
377
378 bool atEndOfInline() { return m_atEndOfInline; }
379 bool atEnd() const { return !m_current; }
380
381 RenderObject* advance()
382 {
383 // FIXME: Support SkipEmptyInlines and observer parameters.
384 m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline);
385 return m_current;
386 }
387private:
388 RenderElement& m_root;
389 RenderObject* m_current;
390 bool m_atEndOfInline;
391};
392
393inline void InlineIterator::increment(InlineBidiResolver* resolver)
394{
395 if (!m_renderer)
396 return;
397 if (is<RenderText>(*m_renderer)) {
398 fastIncrementInTextNode();
399 if (m_pos < downcast<RenderText>(*m_renderer).text().length())
400 return;
401 }
402 // bidiNext can return nullptr
403 RenderObject* bidiNext = bidiNextSkippingEmptyInlines(*m_root, m_renderer, resolver);
404 if (bidiNext)
405 moveToStartOf(*bidiNext);
406 else
407 clear();
408}
409
410inline void InlineIterator::fastDecrement()
411{
412 ASSERT(!refersToEndOfPreviousNode());
413 if (m_pos)
414 setOffset(m_pos - 1);
415 else
416 setRefersToEndOfPreviousNode();
417}
418
419inline bool InlineIterator::atEnd() const
420{
421 return !m_renderer;
422}
423
424inline UChar InlineIterator::characterAt(unsigned index) const
425{
426 if (!is<RenderText>(m_renderer))
427 return 0;
428
429 return downcast<RenderText>(*m_renderer).characterAt(index);
430}
431
432inline UChar InlineIterator::current() const
433{
434 return characterAt(m_pos);
435}
436
437inline UChar InlineIterator::previousInSameNode() const
438{
439 return characterAt(m_pos - 1);
440}
441
442ALWAYS_INLINE UCharDirection InlineIterator::direction() const
443{
444 if (UNLIKELY(!m_renderer))
445 return U_OTHER_NEUTRAL;
446
447 if (LIKELY(is<RenderText>(*m_renderer))) {
448 UChar codeUnit = downcast<RenderText>(*m_renderer).characterAt(m_pos);
449 if (LIKELY(U16_IS_SINGLE(codeUnit)))
450 return u_charDirection(codeUnit);
451 return surrogateTextDirection(codeUnit);
452 }
453
454 if (m_renderer->isListMarker())
455 return m_renderer->style().isLeftToRightDirection() ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
456
457 return U_OTHER_NEUTRAL;
458}
459
460template<>
461inline void InlineBidiResolver::incrementInternal()
462{
463 m_current.increment(this);
464}
465
466static inline bool isIsolatedInline(RenderObject& object)
467{
468 return object.isRenderInline() && isIsolated(object.style().unicodeBidi());
469}
470
471static inline RenderObject* highestContainingIsolateWithinRoot(RenderObject& initialObject, RenderObject* root)
472{
473 RenderObject* containingIsolateObject = nullptr;
474 for (RenderObject* object = &initialObject; object && object != root; object = object->parent()) {
475 if (isIsolatedInline(*object))
476 containingIsolateObject = object;
477 }
478 return containingIsolateObject;
479}
480
481static inline unsigned numberOfIsolateAncestors(const InlineIterator& iter)
482{
483 unsigned count = 0;
484 typedef RenderObject* RenderObjectPtr;
485 for (RenderObjectPtr object = iter.renderer(), root = iter.root(); object && object != root; object = object->parent()) {
486 if (isIsolatedInline(*object))
487 count++;
488 }
489 return count;
490}
491
492// FIXME: This belongs on InlineBidiResolver, except it's a template specialization
493// of BidiResolver which knows nothing about RenderObjects.
494static inline void addPlaceholderRunForIsolatedInline(InlineBidiResolver& resolver, RenderObject& obj, unsigned pos, RenderElement& root)
495{
496 std::unique_ptr<BidiRun> isolatedRun = std::make_unique<BidiRun>(pos, pos, obj, resolver.context(), resolver.dir());
497 // FIXME: isolatedRuns() could be a hash of object->run and then we could cheaply
498 // ASSERT here that we didn't create multiple objects for the same inline.
499 resolver.setWhitespaceCollapsingTransitionForIsolatedRun(*isolatedRun, resolver.whitespaceCollapsingState().currentTransition());
500 resolver.isolatedRuns().append(BidiIsolatedRun(obj, pos, root, *isolatedRun));
501 resolver.runs().appendRun(WTFMove(isolatedRun));
502}
503
504class IsolateTracker {
505public:
506 explicit IsolateTracker(unsigned nestedIsolateCount)
507 : m_nestedIsolateCount(nestedIsolateCount)
508 , m_haveAddedFakeRunForRootIsolate(false)
509 {
510 }
511
512 void enterIsolate() { m_nestedIsolateCount++; }
513 void exitIsolate()
514 {
515 ASSERT(m_nestedIsolateCount >= 1);
516 m_nestedIsolateCount--;
517 if (!inIsolate())
518 m_haveAddedFakeRunForRootIsolate = false;
519 }
520 bool inIsolate() const { return m_nestedIsolateCount; }
521
522 // We don't care if we encounter bidi directional overrides.
523 void embed(UCharDirection, BidiEmbeddingSource) { }
524 void commitExplicitEmbedding() { }
525
526 void addFakeRunIfNecessary(RenderObject& obj, unsigned pos, unsigned end, RenderElement& root, InlineBidiResolver& resolver)
527 {
528 // We only need to add a fake run for a given isolated span once during each call to createBidiRunsForLine.
529 // We'll be called for every span inside the isolated span so we just ignore subsequent calls.
530 // We also avoid creating a fake run until we hit a child that warrants one, e.g. we skip floats.
531 if (RenderBlock::shouldSkipCreatingRunsForObject(obj))
532 return;
533 if (!m_haveAddedFakeRunForRootIsolate) {
534 // obj and pos together denote a single position in the inline, from which the parsing of the isolate will start.
535 // We don't need to mark the end of the run because this is implicit: it is either endOfLine or the end of the
536 // isolate, when we call createBidiRunsForLine it will stop at whichever comes first.
537 addPlaceholderRunForIsolatedInline(resolver, obj, pos, root);
538 }
539 m_haveAddedFakeRunForRootIsolate = true;
540 RenderBlockFlow::appendRunsForObject(nullptr, pos, end, obj, resolver);
541 }
542
543private:
544 unsigned m_nestedIsolateCount;
545 bool m_haveAddedFakeRunForRootIsolate;
546};
547
548template<>
549inline void InlineBidiResolver::appendRunInternal()
550{
551 if (!m_emptyRun && !m_eor.atEnd() && !m_reachedEndOfLine) {
552 // Keep track of when we enter/leave "unicode-bidi: isolate" inlines.
553 // Initialize our state depending on if we're starting in the middle of such an inline.
554 // FIXME: Could this initialize from this->inIsolate() instead of walking up the render tree?
555 IsolateTracker isolateTracker(numberOfIsolateAncestors(m_sor));
556 int start = m_sor.offset();
557 RenderObject* obj = m_sor.renderer();
558 while (obj && obj != m_eor.renderer() && obj != endOfLine.renderer()) {
559 if (isolateTracker.inIsolate())
560 isolateTracker.addFakeRunIfNecessary(*obj, start, obj->length(), *m_sor.root(), *this);
561 else
562 RenderBlockFlow::appendRunsForObject(&m_runs, start, obj->length(), *obj, *this);
563 // FIXME: start/obj should be an InlineIterator instead of two separate variables.
564 start = 0;
565 obj = bidiNextSkippingEmptyInlines(*m_sor.root(), obj, &isolateTracker);
566 }
567 if (obj) {
568 unsigned pos = obj == m_eor.renderer() ? m_eor.offset() : UINT_MAX;
569 if (obj == endOfLine.renderer() && endOfLine.offset() <= pos) {
570 m_reachedEndOfLine = true;
571 pos = endOfLine.offset();
572 }
573 // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
574 int end = obj->length() ? pos + 1 : 0;
575 if (isolateTracker.inIsolate())
576 isolateTracker.addFakeRunIfNecessary(*obj, start, obj->length(), *m_sor.root(), *this);
577 else
578 RenderBlockFlow::appendRunsForObject(&m_runs, start, end, *obj, *this);
579 }
580
581 m_eor.increment();
582 m_sor = m_eor;
583 }
584
585 m_direction = U_OTHER_NEUTRAL;
586 m_status.eor = U_OTHER_NEUTRAL;
587}
588
589template<>
590inline bool InlineBidiResolver::needsContinuePastEndInternal() const
591{
592 // We don't collect runs beyond the endOfLine renderer. Stop traversing when the iterator moves to the next renderer to prevent O(n^2).
593 return m_current.renderer() == endOfLine.renderer();
594}
595
596} // namespace WebCore
597