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