summaryrefslogtreecommitdiffstats
path: root/dom/base/ChildIterator.h
blob: f78ba7ca3dc4f6f6d71c380ba1b7f42018cc2802 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
 * You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ChildIterator_h
#define ChildIterator_h

#include "nsIContent.h"

/**
 * Iterates over the children on a node. If a child is an insertion point,
 * iterates over the children inserted there instead, or the default content
 * if no children are inserted there.
 *
 * The FlattenedChildIterator expands any anonymous content bound from an XBL
 * binding's <xbl:content> element.
 */

#include <stdint.h>
#include "nsAutoPtr.h"

class nsIContent;

namespace mozilla {
namespace dom {

// This class iterates normal DOM child nodes of a given DOM node with
// <xbl:children> nodes replaced by the elements that have been filtered into that
// insertion point. Any bindings on the given element are ignored for purposes
// of determining which insertion point children are filtered into. The iterator
// can be initialized to start at the end by providing false for aStartAtBeginning
// in order to start iterating in reverse from the last child.
class ExplicitChildIterator
{
public:
  explicit ExplicitChildIterator(const nsIContent* aParent,
                                 bool aStartAtBeginning = true)
    : mParent(aParent),
      mChild(nullptr),
      mDefaultChild(nullptr),
      mIndexInInserted(0),
      mIsFirst(aStartAtBeginning)
  {
  }

  ExplicitChildIterator(const ExplicitChildIterator& aOther)
    : mParent(aOther.mParent), mChild(aOther.mChild),
      mDefaultChild(aOther.mDefaultChild),
      mIndexInInserted(aOther.mIndexInInserted), mIsFirst(aOther.mIsFirst) {}

  ExplicitChildIterator(ExplicitChildIterator&& aOther)
    : mParent(aOther.mParent), mChild(aOther.mChild),
      mDefaultChild(aOther.mDefaultChild),
      mIndexInInserted(aOther.mIndexInInserted), mIsFirst(aOther.mIsFirst) {}

  nsIContent* GetNextChild();

  // Looks for aChildToFind respecting insertion points until aChildToFind is
  // found.  This version can take shortcuts that the two-argument version
  // can't, so can be faster (and in fact can be O(1) instead of O(N) in many
  // cases).
  bool Seek(nsIContent* aChildToFind);

  // Looks for aChildToFind respecting insertion points until aChildToFind is found.
  // or aBound is found. If aBound is nullptr then the seek is unbounded. Returns
  // whether aChildToFind was found as an explicit child prior to encountering
  // aBound.
  bool Seek(nsIContent* aChildToFind, nsIContent* aBound)
  {
    // It would be nice to assert that we find aChildToFind, but bz thinks that
    // we might not find aChildToFind when called from ContentInserted
    // if first-letter frames are about.

    // We can't easily take shortcuts here because we'd have to have a way to
    // compare aChildToFind to aBound.
    nsIContent* child;
    do {
      child = GetNextChild();
    } while (child && child != aChildToFind && child != aBound);

    return child == aChildToFind;
  }

  // Returns the current target of this iterator (which might be an explicit
  // child of the node, fallback content of an insertion point or
  // a node distributed to an insertion point.
  nsIContent* Get() const;

  // The inverse of GetNextChild. Properly steps in and out of insertion
  // points.
  nsIContent* GetPreviousChild();

protected:
  // The parent of the children being iterated. For the FlattenedChildIterator,
  // if there is a binding attached to the original parent, mParent points to
  // the <xbl:content> element for the binding.
  const nsIContent* mParent;

  // The current child. When we encounter an insertion point,
  // mChild remains as the insertion point whose content we're iterating (and
  // our state is controled by mDefaultChild or mIndexInInserted depending on
  // whether the insertion point expands to its default content or not).
  nsIContent* mChild;

  // If non-null, this points to the current default content for the current
  // insertion point that we're iterating (i.e. mChild, which must be an
  // nsXBLChildrenElement or HTMLContentElement). Once this transitions back
  // to null, we continue iterating at mChild's next sibling.
  nsIContent* mDefaultChild;

  // If not zero, we're iterating inserted children for an insertion point. This
  // is an index into mChild's inserted children array (mChild must be an
  // nsXBLChildrenElement). The index is one past the "current" child (as
  // opposed to mChild which represents the "current" child).
  uint32_t mIndexInInserted;

  // A flag to let us know that we haven't started iterating yet.
  bool mIsFirst;
};

// Iterates over the flattened children of a node, which accounts for anonymous
// children and nodes moved by insertion points. If a node has anonymous
// children, those are iterated over.  The iterator can be initialized to start
// at the end by providing false for aStartAtBeginning in order to start
// iterating in reverse from the last child.
class FlattenedChildIterator : public ExplicitChildIterator
{
public:
  explicit FlattenedChildIterator(const nsIContent* aParent,
                                  bool aStartAtBeginning = true)
    : ExplicitChildIterator(aParent, aStartAtBeginning), mXBLInvolved(false)
  {
    Init(false);
  }

  FlattenedChildIterator(FlattenedChildIterator&& aOther)
    : ExplicitChildIterator(Move(aOther)), mXBLInvolved(aOther.mXBLInvolved) {}

  FlattenedChildIterator(const FlattenedChildIterator& aOther)
    : ExplicitChildIterator(aOther), mXBLInvolved(aOther.mXBLInvolved) {}

  bool XBLInvolved() { return mXBLInvolved; }

protected:
  /**
   * This constructor is a hack to help AllChildrenIterator which sometimes
   * doesn't want to consider XBL.
   */
  FlattenedChildIterator(const nsIContent* aParent, uint32_t aFlags,
                         bool aStartAtBeginning = true)
    : ExplicitChildIterator(aParent, aStartAtBeginning), mXBLInvolved(false)
  {
    bool ignoreXBL = aFlags & nsIContent::eAllButXBL;
    Init(ignoreXBL);
  }

  void Init(bool aIgnoreXBL);

  // For certain optimizations, nsCSSFrameConstructor needs to know if the
  // child list of the element that we're iterating matches its .childNodes.
  bool mXBLInvolved;
};

/**
 * AllChildrenIterator traverses the children of an element including before /
 * after content and optionally XBL children.  The iterator can be initialized
 * to start at the end by providing false for aStartAtBeginning in order to
 * start iterating in reverse from the last child.
 *
 * Note: it assumes that no mutation of the DOM or frame tree takes place during
 * iteration, and will break horribly if that is not true.
 */
class AllChildrenIterator : private FlattenedChildIterator
{
public:
  AllChildrenIterator(const nsIContent* aNode, uint32_t aFlags,
                      bool aStartAtBeginning = true) :
    FlattenedChildIterator(aNode, aFlags, aStartAtBeginning),
    mOriginalContent(aNode), mAnonKidsIdx(aStartAtBeginning ? UINT32_MAX : 0),
    mFlags(aFlags), mPhase(aStartAtBeginning ? eAtBegin : eAtEnd) { }

  AllChildrenIterator(AllChildrenIterator&& aOther)
    : FlattenedChildIterator(Move(aOther)),
      mOriginalContent(aOther.mOriginalContent),
      mAnonKids(Move(aOther.mAnonKids)), mAnonKidsIdx(aOther.mAnonKidsIdx),
      mFlags(aOther.mFlags), mPhase(aOther.mPhase)
#ifdef DEBUG
      , mMutationGuard(aOther.mMutationGuard)
#endif
      {}

#ifdef DEBUG
  ~AllChildrenIterator() { MOZ_ASSERT(!mMutationGuard.Mutated(0)); }
#endif

  // Returns the current target the iterator is at, or null if the iterator
  // doesn't point to any child node (either eAtBegin or eAtEnd phase).
  nsIContent* Get() const;

  // Seeks the given node in children of a parent element, starting from
  // the current iterator's position, and sets the iterator at the given child
  // node if it was found.
  bool Seek(nsIContent* aChildToFind);

  nsIContent* GetNextChild();
  nsIContent* GetPreviousChild();
  const nsIContent* Parent() const { return mOriginalContent; }

  enum IteratorPhase
  {
    eAtBegin,
    eAtBeforeKid,
    eAtExplicitKids,
    eAtAnonKids,
    eAtAfterKid,
    eAtEnd
  };
  IteratorPhase Phase() const { return mPhase; }

private:
  // Helpers.
  void AppendNativeAnonymousChildren();
  void AppendNativeAnonymousChildrenFromFrame(nsIFrame* aFrame);

  const nsIContent* mOriginalContent;

  // mAnonKids is an array of native anonymous children, mAnonKidsIdx is index
  // in the array. If mAnonKidsIdx < mAnonKids.Length() and mPhase is
  // eAtAnonKids then the iterator points at a child at mAnonKidsIdx index. If
  // mAnonKidsIdx == mAnonKids.Length() then the iterator is somewhere after
  // the last native anon child. If mAnonKidsIdx == UINT32_MAX then the iterator
  // is somewhere before the first native anon child.
  nsTArray<nsIContent*> mAnonKids;
  uint32_t mAnonKidsIdx;

  uint32_t mFlags;
  IteratorPhase mPhase;
#ifdef DEBUG
  // XXX we should really assert there are no frame tree changes as well, but
  // there's no easy way to do that.
  nsMutationGuard mMutationGuard;
#endif
};

/**
 * StyleChildrenIterator traverses the children of the element from the
 * perspective of the style system, particularly the children we need to traverse
 * during restyle. This is identical to AllChildrenIterator with
 * (eAllChildren | eSkipDocumentLevelNativeAnonymousContent), _except_ that we
 * detect and skip any native anonymous children that are used to implement
 * pseudo-elements (since the style system needs to cascade those using
 * different algorithms).
 *
 * Note: it assumes that no mutation of the DOM or frame tree takes place during
 * iteration, and will break horribly if that is not true.
 */
class StyleChildrenIterator : private AllChildrenIterator {
public:
  explicit StyleChildrenIterator(const nsIContent* aContent)
    : AllChildrenIterator(aContent,
                          nsIContent::eAllChildren |
                          nsIContent::eSkipDocumentLevelNativeAnonymousContent)
  {
    MOZ_COUNT_CTOR(StyleChildrenIterator);
  }
  ~StyleChildrenIterator() { MOZ_COUNT_DTOR(StyleChildrenIterator); }

  nsIContent* GetNextChild();

  // Returns true if we cannot find all the children we need to style by
  // traversing the siblings of the first child.
  static bool IsNeeded(const Element* aParent);
};

} // namespace dom
} // namespace mozilla

#endif