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