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