1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 /*
8 Implementation description from https://etherpad.mozilla.org/dir-auto
9
10 Static case
11 ===========
12 When we see a new content node with @dir=auto from the parser, we set the
13 NodeHasDirAuto flag on the node. We won't have enough information to
14 decide the directionality of the node at this point.
15
16 When we bind a new content node to the document, if its parent has either of
17 the NodeAncestorHasDirAuto or NodeHasDirAuto flags, we set the
18 NodeAncestorHasDirAuto flag on the node.
19
20 When a new input with @type=text/search/tel/url/email and @dir=auto is added
21 from the parser, we resolve the directionality based on its @value.
22
23 When a new text node with non-neutral content is appended to a textarea
24 element with NodeHasDirAuto, if the directionality of the textarea element
25 is still unresolved, it is resolved based on the value of the text node.
26 Elements with unresolved directionality behave as LTR.
27
28 When a new text node with non-neutral content is appended to an element that
29 is not a textarea but has either of the NodeAncestorHasDirAuto or
30 NodeHasDirAuto flags, we walk up the parent chain while the
31 NodeAncestorHasDirAuto flag is present, and when we reach an element with
32 NodeHasDirAuto and no resolved directionality, we resolve the directionality
33 based on the contents of the text node and cease walking the parent chain.
34 Note that we should ignore elements with NodeHasDirAuto with resolved
35 directionality, so that the second text node in this example tree doesn't
36 affect the directionality of the div:
37
38 <div dir=auto>
39 <span>foo</span>
40 <span>بار</span>
41 </div>
42
43 The parent chain walk will be aborted if we hit a script or style element, or
44 if we hit an element with @dir=ltr or @dir=rtl.
45
46 I will call this algorithm "upward propagation".
47
48 Each text node should maintain a list of elements which have their
49 directionality determined by the first strong character of that text node.
50 This is useful to make dynamic changes more efficient. One way to implement
51 this is to have a per-document hash table mapping a text node to a set of
52 elements. I'll call this data structure TextNodeDirectionalityMap. The
53 algorithm for appending a new text node above needs to update this data
54 structure.
55
56 *IMPLEMENTATION NOTE*
57 In practice, the implementation uses two per-node properties:
58
59 dirAutoSetBy, which is set on a node with auto-directionality, and points to
60 the textnode that contains the strong character which determines the
61 directionality of the node.
62
63 textNodeDirectionalityMap, which is set on a text node and points to a hash
64 table listing the nodes whose directionality is determined by the text node.
65
66 Handling dynamic changes
67 ========================
68
69 We need to handle the following cases:
70
71 1. When the value of an input element with @type=text/search/tel/url/email is
72 changed, if it has NodeHasDirAuto, we update the resolved directionality.
73
74 2. When the dir attribute is changed from something else (including the case
75 where it doesn't exist) to auto on a textarea or an input element with
76 @type=text/search/tel/url/email, we set the NodeHasDirAuto flag and resolve
77 the directionality based on the value of the element.
78
79 3. When the dir attribute is changed from something else (including the case
80 where it doesn't exist) to auto on any element except case 1 above and the bdi
81 element, we run the following algorithm:
82 * We set the NodeHasDirAuto flag.
83 * If the element doesn't have the NodeAncestorHasDirAuto flag, we set the
84 NodeAncestorHasDirAuto flag on all of its child nodes. (Note that if the
85 element does have NodeAncestorHasDirAuto, all of its children should
86 already have this flag too. We can assert this in debug builds.)
87 * To resolve the directionality of the element, we run the algorithm explained
88 in
89 http://www.whatwg.org/specs/web-apps/current-work/multipage/elements.html#the-dir-attribute
90 (I'll call this the "downward propagation algorithm".) by walking the child
91 subtree in tree order. Note that an element with @dir=auto should not affect
92 other elements in its document with @dir=auto. So there is no need to walk up
93 the parent chain in this case. TextNodeDirectionalityMap needs to be updated
94 as appropriate.
95
96 3a. When the dir attribute is set to any valid value on an element that didn't
97 have a valid dir attribute before, this means that any descendant of that
98 element will not affect the directionality of any of its ancestors. So we need
99 to check whether any text node descendants of the element are listed in
100 TextNodeDirectionalityMap, and whether the elements whose direction they set
101 are ancestors of the element. If so, we need to rerun the downward propagation
102 algorithm for those ancestors.
103
104 4. When the dir attribute is changed from auto to something else (including
105 the case where it gets removed) on a textarea or an input element with
106 @type=text/search/tel/url/email, we unset the NodeHasDirAuto flag and
107 resolve the directionality based on the directionality of the value of the
108 @dir attribute on element itself or its parent element.
109
110 5. When the dir attribute is changed from auto to something else (including
111 the case where it gets removed) on any element except case 4 above and the bdi
112 element, we run the following algorithm:
113 * We unset the NodeHasDirAuto flag.
114 * If the element does not have the NodeAncestorHasDirAuto flag, we unset
115 the NodeAncestorHasDirAuto flag on all of its child nodes, except those
116 who are a descendant of another element with NodeHasDirAuto. (Note that if
117 the element has the NodeAncestorHasDirAuto flag, all of its child nodes
118 should still retain the same flag.)
119 * We resolve the directionality of the element based on the value of the @dir
120 attribute on the element itself or its parent element.
121 TextNodeDirectionalityMap needs to be updated as appropriate.
122
123 5a. When the dir attribute is removed or set to an invalid value on any
124 element (except a bdi element) with the NodeAncestorHasDirAuto flag which
125 previously had a valid dir attribute, it might have a text node descendant
126 that did not previously affect the directionality of any of its ancestors but
127 should now begin to affect them. We run the following algorithm:
128 * Walk up the parent chain from the element.
129 * For any element that appears in the TextNodeDirectionalityMap, remove the
130 element from the map and rerun the downward propagation algorithm
131 (see section 3).
132 * If we reach an element without either of the NodeHasDirAuto or
133 NodeAncestorHasDirAuto flags, abort the parent chain walk.
134
135 6. When an element with @dir=auto is added to the document, we should handle
136 it similar to the case 2/3 above.
137
138 7. When an element with NodeHasDirAuto or NodeAncestorHasDirAuto is
139 removed from the document, we should handle it similar to the case 4/5 above,
140 except that we don't need to handle anything in the child subtree. We should
141 also remove all of the occurrences of that node and its descendants from
142 TextNodeDirectionalityMap. (This is the conceptual description of what needs
143 to happen but in the implementation UnbindFromTree is going to be called on
144 all of the descendants so we don't need to descend into the child subtree).
145
146 8. When the contents of a text node is changed either from script or by the
147 user, we need to run the following algorithm:
148 * If the change has happened after the first character with strong
149 directionality in the text node, do nothing.
150 * If the text node is a child of a bdi, script or style element, do nothing.
151 * If the text node belongs to a textarea with NodeHasDirAuto, we need to
152 update the directionality of the textarea.
153 * Grab a list of elements affected by this text node from
154 TextNodeDirectionalityMap and re-resolve the directionality of each one of
155 them based on the new contents of the text node.
156 * If the text node does not exist in TextNodeDirectionalityMap, and it has the
157 NodeAncestorHasDirAuto flag set, this could potentially be a text node
158 which is going to start affecting the directionality of its parent @dir=auto
159 elements. In this case, we need to fall back to the (potentially expensive)
160 "upward propagation algorithm". The TextNodeDirectionalityMap data structure
161 needs to be update during this algorithm.
162 * If the new contents of the text node do not have any strong characters, and
163 the old contents used to, and the text node used to exist in
164 TextNodeDirectionalityMap and it has the NodeAncestorHasDirAuto flag set,
165 the elements associated with this text node inside TextNodeDirectionalityMap
166 will now get their directionality from another text node. In this case, for
167 each element in the list retrieved from TextNodeDirectionalityMap, run the
168 downward propagation algorithm (section 3), and remove the text node from
169 TextNodeDirectionalityMap.
170
171 9. When a new text node is injected into a document, we need to run the
172 following algorithm:
173 * If the contents of the text node do not have any characters with strong
174 direction, do nothing.
175 * If the text node is a child of a bdi, script or style element, do nothing.
176 * If the text node is appended to a textarea element with NodeHasDirAuto, we
177 need to update the directionality of the textarea.
178 * If the text node has NodeAncestorHasDirAuto, we need to run the "upward
179 propagation algorithm". The TextNodeDirectionalityMap data structure needs to
180 be update during this algorithm.
181
182 10. When a text node is removed from a document, we need to run the following
183 algorithm:
184 * If the contents of the text node do not have any characters with strong
185 direction, do nothing.
186 * If the text node is a child of a bdi, script or style element, do nothing.
187 * If the text node is removed from a textarea element with NodeHasDirAuto,
188 set the directionality to "ltr". (This is what the spec currently says, but
189 I'm filing a spec bug to get it fixed -- the directionality should depend on
190 the parent element here.)
191 * If the text node has NodeAncestorHasDirAuto, we need to look at the list
192 of elements being affected by this text node from TextNodeDirectionalityMap,
193 run the "downward propagation algorithm" (section 3) for each one of them,
194 while updating TextNodeDirectionalityMap along the way.
195
196 11. If the value of the @dir attribute on a bdi element is changed to an
197 invalid value (or if it's removed), determine the new directionality similar
198 to the case 3 above.
199
200 == Implemention Notes ==
201 When a new node gets bound to the tree, the BindToTree function gets called.
202 The reverse case is UnbindFromTree.
203 When the contents of a text node change, nsGenericDOMDataNode::SetTextInternal
204 gets called.
205 */
206
207 #include "mozilla/dom/DirectionalityUtils.h"
208
209 #include "nsINode.h"
210 #include "nsIContent.h"
211 #include "nsIDocument.h"
212 #include "mozilla/AutoRestore.h"
213 #include "mozilla/DebugOnly.h"
214 #include "mozilla/dom/Element.h"
215 #include "nsUnicodeProperties.h"
216 #include "nsTextFragment.h"
217 #include "nsAttrValue.h"
218 #include "nsTextNode.h"
219 #include "nsCheapSets.h"
220
221 namespace mozilla {
222
223 using mozilla::dom::Element;
224
225 /**
226 * Returns true if aElement is one of the elements whose text content should not
227 * affect its own direction, nor the direction of ancestors with dir=auto.
228 *
229 * Note that this does not include <bdi>, whose content does affect its own
230 * direction when it has dir=auto (which it has by default), so one needs to
231 * test for it separately, e.g. with DoesNotAffectDirectionOfAncestors.
232 * It *does* include textarea, because even if a textarea has dir=auto, it has
233 * unicode-bidi: plaintext and is handled automatically in bidi resolution.
234 */
DoesNotParticipateInAutoDirection(const Element * aElement)235 static bool DoesNotParticipateInAutoDirection(const Element* aElement) {
236 mozilla::dom::NodeInfo* nodeInfo = aElement->NodeInfo();
237 return (!aElement->IsHTMLElement() || nodeInfo->Equals(nsGkAtoms::script) ||
238 nodeInfo->Equals(nsGkAtoms::style) ||
239 nodeInfo->Equals(nsGkAtoms::textarea) ||
240 aElement->IsInAnonymousSubtree());
241 }
242
243 /**
244 * Returns true if aElement is one of the element whose text content should not
245 * affect the direction of ancestors with dir=auto (though it may affect its own
246 * direction, e.g. <bdi>)
247 */
DoesNotAffectDirectionOfAncestors(const Element * aElement)248 static bool DoesNotAffectDirectionOfAncestors(const Element* aElement) {
249 return (DoesNotParticipateInAutoDirection(aElement) ||
250 aElement->IsHTMLElement(nsGkAtoms::bdi) || aElement->HasFixedDir());
251 }
252
253 /**
254 * Returns the directionality of a Unicode character
255 */
GetDirectionFromChar(uint32_t ch)256 static Directionality GetDirectionFromChar(uint32_t ch) {
257 switch (mozilla::unicode::GetBidiCat(ch)) {
258 case eCharType_RightToLeft:
259 case eCharType_RightToLeftArabic:
260 return eDir_RTL;
261
262 case eCharType_LeftToRight:
263 return eDir_LTR;
264
265 default:
266 return eDir_NotSet;
267 }
268 }
269
NodeAffectsDirAutoAncestor(nsINode * aTextNode)270 inline static bool NodeAffectsDirAutoAncestor(nsINode* aTextNode) {
271 Element* parent = aTextNode->GetParentElement();
272 return (parent && !DoesNotParticipateInAutoDirection(parent) &&
273 parent->NodeOrAncestorHasDirAuto() &&
274 !aTextNode->IsInAnonymousSubtree());
275 }
276
GetDirectionFromText(const char16_t * aText,const uint32_t aLength,uint32_t * aFirstStrong)277 Directionality GetDirectionFromText(const char16_t* aText,
278 const uint32_t aLength,
279 uint32_t* aFirstStrong) {
280 const char16_t* start = aText;
281 const char16_t* end = aText + aLength;
282
283 while (start < end) {
284 uint32_t current = start - aText;
285 uint32_t ch = *start++;
286
287 if (NS_IS_HIGH_SURROGATE(ch) && start < end &&
288 NS_IS_LOW_SURROGATE(*start)) {
289 ch = SURROGATE_TO_UCS4(ch, *start++);
290 current++;
291 }
292
293 // Just ignore lone surrogates
294 if (!IS_SURROGATE(ch)) {
295 Directionality dir = GetDirectionFromChar(ch);
296 if (dir != eDir_NotSet) {
297 if (aFirstStrong) {
298 *aFirstStrong = current;
299 }
300 return dir;
301 }
302 }
303 }
304
305 if (aFirstStrong) {
306 *aFirstStrong = UINT32_MAX;
307 }
308 return eDir_NotSet;
309 }
310
GetDirectionFromText(const char * aText,const uint32_t aLength,uint32_t * aFirstStrong=nullptr)311 static Directionality GetDirectionFromText(const char* aText,
312 const uint32_t aLength,
313 uint32_t* aFirstStrong = nullptr) {
314 const char* start = aText;
315 const char* end = aText + aLength;
316
317 while (start < end) {
318 uint32_t current = start - aText;
319 unsigned char ch = (unsigned char)*start++;
320
321 Directionality dir = GetDirectionFromChar(ch);
322 if (dir != eDir_NotSet) {
323 if (aFirstStrong) {
324 *aFirstStrong = current;
325 }
326 return dir;
327 }
328 }
329
330 if (aFirstStrong) {
331 *aFirstStrong = UINT32_MAX;
332 }
333 return eDir_NotSet;
334 }
335
GetDirectionFromText(const nsTextFragment * aFrag,uint32_t * aFirstStrong=nullptr)336 static Directionality GetDirectionFromText(const nsTextFragment* aFrag,
337 uint32_t* aFirstStrong = nullptr) {
338 if (aFrag->Is2b()) {
339 return GetDirectionFromText(aFrag->Get2b(), aFrag->GetLength(),
340 aFirstStrong);
341 }
342
343 return GetDirectionFromText(aFrag->Get1b(), aFrag->GetLength(), aFirstStrong);
344 }
345
346 /**
347 * Set the directionality of a node with dir=auto as defined in
348 * http://www.whatwg.org/specs/web-apps/current-work/multipage/elements.html#the-directionality
349 *
350 * @param[in] changedNode If we call this method because the content of a text
351 * node is about to change, pass in the changed node, so that we
352 * know not to return it
353 * @return the text node containing the character that determined the direction
354 */
WalkDescendantsSetDirectionFromText(Element * aElement,bool aNotify=true,nsINode * aChangedNode=nullptr)355 static nsTextNode* WalkDescendantsSetDirectionFromText(
356 Element* aElement, bool aNotify = true, nsINode* aChangedNode = nullptr) {
357 MOZ_ASSERT(aElement, "Must have an element");
358 MOZ_ASSERT(aElement->HasDirAuto(), "Element must have dir=auto");
359
360 if (DoesNotParticipateInAutoDirection(aElement)) {
361 return nullptr;
362 }
363
364 nsIContent* child = aElement->GetFirstChild();
365 while (child) {
366 if (child->IsElement() &&
367 DoesNotAffectDirectionOfAncestors(child->AsElement())) {
368 child = child->GetNextNonChildNode(aElement);
369 continue;
370 }
371
372 if (child->NodeType() == nsINode::TEXT_NODE && child != aChangedNode) {
373 Directionality textNodeDir = GetDirectionFromText(child->GetText());
374 if (textNodeDir != eDir_NotSet) {
375 // We found a descendant text node with strong directional characters.
376 // Set the directionality of aElement to the corresponding value.
377 aElement->SetDirectionality(textNodeDir, aNotify);
378 return static_cast<nsTextNode*>(child);
379 }
380 }
381 child = child->GetNextNode(aElement);
382 }
383
384 // We walked all the descendants without finding a text node with strong
385 // directional characters. Set the directionality to LTR
386 aElement->SetDirectionality(eDir_LTR, aNotify);
387 return nullptr;
388 }
389
390 class nsTextNodeDirectionalityMap {
nsTextNodeDirectionalityMapDtor(void * aObject,nsAtom * aPropertyName,void * aPropertyValue,void * aData)391 static void nsTextNodeDirectionalityMapDtor(void* aObject,
392 nsAtom* aPropertyName,
393 void* aPropertyValue,
394 void* aData) {
395 nsINode* textNode = static_cast<nsINode*>(aObject);
396 textNode->ClearHasTextNodeDirectionalityMap();
397
398 nsTextNodeDirectionalityMap* map =
399 reinterpret_cast<nsTextNodeDirectionalityMap*>(aPropertyValue);
400 map->EnsureMapIsClear();
401 delete map;
402 }
403
404 public:
nsTextNodeDirectionalityMap(nsINode * aTextNode)405 explicit nsTextNodeDirectionalityMap(nsINode* aTextNode)
406 : mElementToBeRemoved(nullptr) {
407 MOZ_ASSERT(aTextNode, "Null text node");
408 MOZ_COUNT_CTOR(nsTextNodeDirectionalityMap);
409 aTextNode->SetProperty(nsGkAtoms::textNodeDirectionalityMap, this,
410 nsTextNodeDirectionalityMapDtor);
411 aTextNode->SetHasTextNodeDirectionalityMap();
412 }
413
~nsTextNodeDirectionalityMap()414 ~nsTextNodeDirectionalityMap() {
415 MOZ_COUNT_DTOR(nsTextNodeDirectionalityMap);
416 }
417
nsTextNodeDirectionalityMapPropertyDestructor(void * aObject,nsAtom * aProperty,void * aPropertyValue,void * aData)418 static void nsTextNodeDirectionalityMapPropertyDestructor(
419 void* aObject, nsAtom* aProperty, void* aPropertyValue, void* aData) {
420 nsTextNode* textNode = static_cast<nsTextNode*>(aPropertyValue);
421 nsTextNodeDirectionalityMap* map = GetDirectionalityMap(textNode);
422 if (map) {
423 map->RemoveEntryForProperty(static_cast<Element*>(aObject));
424 }
425 NS_RELEASE(textNode);
426 }
427
AddEntry(nsTextNode * aTextNode,Element * aElement)428 void AddEntry(nsTextNode* aTextNode, Element* aElement) {
429 if (!mElements.Contains(aElement)) {
430 mElements.Put(aElement);
431 NS_ADDREF(aTextNode);
432 aElement->SetProperty(nsGkAtoms::dirAutoSetBy, aTextNode,
433 nsTextNodeDirectionalityMapPropertyDestructor);
434 aElement->SetHasDirAutoSet();
435 }
436 }
437
RemoveEntry(nsTextNode * aTextNode,Element * aElement)438 void RemoveEntry(nsTextNode* aTextNode, Element* aElement) {
439 NS_ASSERTION(mElements.Contains(aElement),
440 "element already removed from map");
441
442 mElements.Remove(aElement);
443 aElement->ClearHasDirAutoSet();
444 aElement->DeleteProperty(nsGkAtoms::dirAutoSetBy);
445 }
446
RemoveEntryForProperty(Element * aElement)447 void RemoveEntryForProperty(Element* aElement) {
448 if (mElementToBeRemoved != aElement) {
449 mElements.Remove(aElement);
450 }
451 aElement->ClearHasDirAutoSet();
452 }
453
454 private:
455 nsCheapSet<nsPtrHashKey<Element>> mElements;
456 // Only used for comparison.
457 Element* mElementToBeRemoved;
458
GetDirectionalityMap(nsINode * aTextNode)459 static nsTextNodeDirectionalityMap* GetDirectionalityMap(nsINode* aTextNode) {
460 MOZ_ASSERT(aTextNode->NodeType() == nsINode::TEXT_NODE,
461 "Must be a text node");
462 nsTextNodeDirectionalityMap* map = nullptr;
463
464 if (aTextNode->HasTextNodeDirectionalityMap()) {
465 map = static_cast<nsTextNodeDirectionalityMap*>(
466 aTextNode->GetProperty(nsGkAtoms::textNodeDirectionalityMap));
467 }
468
469 return map;
470 }
471
SetNodeDirection(nsPtrHashKey<Element> * aEntry,void * aDir)472 static nsCheapSetOperator SetNodeDirection(nsPtrHashKey<Element>* aEntry,
473 void* aDir) {
474 MOZ_ASSERT(aEntry->GetKey()->IsElement(), "Must be an Element");
475 aEntry->GetKey()->SetDirectionality(
476 *reinterpret_cast<Directionality*>(aDir), true);
477 return OpNext;
478 }
479
480 struct nsTextNodeDirectionalityMapAndElement {
481 nsTextNodeDirectionalityMap* mMap;
482 nsCOMPtr<nsINode> mNode;
483 };
484
ResetNodeDirection(nsPtrHashKey<Element> * aEntry,void * aData)485 static nsCheapSetOperator ResetNodeDirection(nsPtrHashKey<Element>* aEntry,
486 void* aData) {
487 MOZ_ASSERT(aEntry->GetKey()->IsElement(), "Must be an Element");
488 // run the downward propagation algorithm
489 // and remove the text node from the map
490 nsTextNodeDirectionalityMapAndElement* data =
491 static_cast<nsTextNodeDirectionalityMapAndElement*>(aData);
492 nsINode* oldTextNode = data->mNode;
493 Element* rootNode = aEntry->GetKey();
494 nsTextNode* newTextNode = nullptr;
495 if (rootNode->GetParentNode() && rootNode->HasDirAuto()) {
496 newTextNode =
497 WalkDescendantsSetDirectionFromText(rootNode, true, oldTextNode);
498 }
499
500 AutoRestore<Element*> restore(data->mMap->mElementToBeRemoved);
501 data->mMap->mElementToBeRemoved = rootNode;
502 if (newTextNode) {
503 nsINode* oldDirAutoSetBy = static_cast<nsTextNode*>(
504 rootNode->GetProperty(nsGkAtoms::dirAutoSetBy));
505 if (oldDirAutoSetBy == newTextNode) {
506 // We're already registered.
507 return OpNext;
508 }
509 nsTextNodeDirectionalityMap::AddEntryToMap(newTextNode, rootNode);
510 } else {
511 rootNode->ClearHasDirAutoSet();
512 rootNode->DeleteProperty(nsGkAtoms::dirAutoSetBy);
513 }
514 return OpRemove;
515 }
516
TakeEntries(nsPtrHashKey<Element> * aEntry,void * aData)517 static nsCheapSetOperator TakeEntries(nsPtrHashKey<Element>* aEntry,
518 void* aData) {
519 AutoTArray<Element*, 8>* entries =
520 static_cast<AutoTArray<Element*, 8>*>(aData);
521 entries->AppendElement(aEntry->GetKey());
522 return OpRemove;
523 }
524
525 public:
UpdateAutoDirection(Directionality aDir)526 uint32_t UpdateAutoDirection(Directionality aDir) {
527 return mElements.EnumerateEntries(SetNodeDirection, &aDir);
528 }
529
ResetAutoDirection(nsINode * aTextNode)530 void ResetAutoDirection(nsINode* aTextNode) {
531 nsTextNodeDirectionalityMapAndElement data = {this, aTextNode};
532 mElements.EnumerateEntries(ResetNodeDirection, &data);
533 }
534
EnsureMapIsClear()535 void EnsureMapIsClear() {
536 AutoRestore<Element*> restore(mElementToBeRemoved);
537 AutoTArray<Element*, 8> entries;
538 mElements.EnumerateEntries(TakeEntries, &entries);
539 for (Element* el : entries) {
540 el->ClearHasDirAutoSet();
541 el->DeleteProperty(nsGkAtoms::dirAutoSetBy);
542 }
543 }
544
RemoveElementFromMap(nsTextNode * aTextNode,Element * aElement)545 static void RemoveElementFromMap(nsTextNode* aTextNode, Element* aElement) {
546 if (aTextNode->HasTextNodeDirectionalityMap()) {
547 GetDirectionalityMap(aTextNode)->RemoveEntry(aTextNode, aElement);
548 }
549 }
550
AddEntryToMap(nsTextNode * aTextNode,Element * aElement)551 static void AddEntryToMap(nsTextNode* aTextNode, Element* aElement) {
552 nsTextNodeDirectionalityMap* map = GetDirectionalityMap(aTextNode);
553 if (!map) {
554 map = new nsTextNodeDirectionalityMap(aTextNode);
555 }
556
557 map->AddEntry(aTextNode, aElement);
558 }
559
UpdateTextNodeDirection(nsINode * aTextNode,Directionality aDir)560 static uint32_t UpdateTextNodeDirection(nsINode* aTextNode,
561 Directionality aDir) {
562 MOZ_ASSERT(aTextNode->HasTextNodeDirectionalityMap(),
563 "Map missing in UpdateTextNodeDirection");
564 return GetDirectionalityMap(aTextNode)->UpdateAutoDirection(aDir);
565 }
566
ResetTextNodeDirection(nsTextNode * aTextNode,nsTextNode * aChangedTextNode)567 static void ResetTextNodeDirection(nsTextNode* aTextNode,
568 nsTextNode* aChangedTextNode) {
569 MOZ_ASSERT(aTextNode->HasTextNodeDirectionalityMap(),
570 "Map missing in ResetTextNodeDirection");
571 RefPtr<nsTextNode> textNode = aTextNode;
572 GetDirectionalityMap(textNode)->ResetAutoDirection(aChangedTextNode);
573 }
574
EnsureMapIsClearFor(nsINode * aTextNode)575 static void EnsureMapIsClearFor(nsINode* aTextNode) {
576 if (aTextNode->HasTextNodeDirectionalityMap()) {
577 GetDirectionalityMap(aTextNode)->EnsureMapIsClear();
578 }
579 }
580 };
581
RecomputeDirectionality(Element * aElement,bool aNotify)582 Directionality RecomputeDirectionality(Element* aElement, bool aNotify) {
583 MOZ_ASSERT(!aElement->HasDirAuto(),
584 "RecomputeDirectionality called with dir=auto");
585
586 Directionality dir = eDir_LTR;
587
588 if (aElement->HasValidDir()) {
589 dir = aElement->GetDirectionality();
590 } else {
591 Element* parent = aElement->GetParentElement();
592 if (parent) {
593 // If the element doesn't have an explicit dir attribute with a valid
594 // value, the directionality is the same as the parent element (but
595 // don't propagate the parent directionality if it isn't set yet).
596 Directionality parentDir = parent->GetDirectionality();
597 if (parentDir != eDir_NotSet) {
598 dir = parentDir;
599 }
600 } else {
601 // If there is no parent element and no dir attribute, the directionality
602 // is LTR.
603 dir = eDir_LTR;
604 }
605
606 aElement->SetDirectionality(dir, aNotify);
607 }
608 return dir;
609 }
610
SetDirectionalityOnDescendants(Element * aElement,Directionality aDir,bool aNotify)611 void SetDirectionalityOnDescendants(Element* aElement, Directionality aDir,
612 bool aNotify) {
613 for (nsIContent* child = aElement->GetFirstChild(); child;) {
614 if (!child->IsElement()) {
615 child = child->GetNextNode(aElement);
616 continue;
617 }
618
619 Element* element = child->AsElement();
620 if (element->HasValidDir() || element->HasDirAuto()) {
621 child = child->GetNextNonChildNode(aElement);
622 continue;
623 }
624 element->SetDirectionality(aDir, aNotify);
625 child = child->GetNextNode(aElement);
626 }
627 }
628
629 /**
630 * Walk the parent chain of a text node whose dir attribute has been removed and
631 * reset the direction of any of its ancestors which have dir=auto and whose
632 * directionality is determined by a text node descendant.
633 */
WalkAncestorsResetAutoDirection(Element * aElement,bool aNotify)634 void WalkAncestorsResetAutoDirection(Element* aElement, bool aNotify) {
635 nsTextNode* setByNode;
636 Element* parent = aElement->GetParentElement();
637
638 while (parent && parent->NodeOrAncestorHasDirAuto()) {
639 if (parent->HasDirAutoSet()) {
640 // If the parent has the DirAutoSet flag, its direction is determined by
641 // some text node descendant.
642 // Remove it from the map and reset its direction by the downward
643 // propagation algorithm
644 setByNode = static_cast<nsTextNode*>(
645 parent->GetProperty(nsGkAtoms::dirAutoSetBy));
646 if (setByNode) {
647 nsTextNodeDirectionalityMap::RemoveElementFromMap(setByNode, parent);
648 }
649 }
650 if (parent->HasDirAuto()) {
651 setByNode = WalkDescendantsSetDirectionFromText(parent, aNotify);
652 if (setByNode) {
653 nsTextNodeDirectionalityMap::AddEntryToMap(setByNode, parent);
654 }
655 break;
656 }
657 parent = parent->GetParentElement();
658 }
659 }
660
WalkDescendantsResetAutoDirection(Element * aElement)661 void WalkDescendantsResetAutoDirection(Element* aElement) {
662 nsIContent* child = aElement->GetFirstChild();
663 while (child) {
664 if (child->IsElement() && child->AsElement()->HasDirAuto()) {
665 child = child->GetNextNonChildNode(aElement);
666 continue;
667 }
668
669 if (child->NodeType() == nsINode::TEXT_NODE &&
670 child->HasTextNodeDirectionalityMap()) {
671 nsTextNodeDirectionalityMap::ResetTextNodeDirection(
672 static_cast<nsTextNode*>(child), nullptr);
673 // Don't call nsTextNodeDirectionalityMap::EnsureMapIsClearFor(child)
674 // since ResetTextNodeDirection may have kept elements in child's
675 // DirectionalityMap.
676 }
677 child = child->GetNextNode(aElement);
678 }
679 }
680
WalkDescendantsSetDirAuto(Element * aElement,bool aNotify)681 void WalkDescendantsSetDirAuto(Element* aElement, bool aNotify) {
682 // Only test for DoesNotParticipateInAutoDirection -- in other words, if
683 // aElement is a <bdi> which is having its dir attribute set to auto (or
684 // removed or set to an invalid value, which are equivalent to dir=auto for
685 // <bdi>, we *do* want to set AncestorHasDirAuto on its descendants, unlike
686 // in SetDirOnBind where we don't propagate AncestorHasDirAuto to a <bdi>
687 // being bound to an existing node with dir=auto.
688 if (!DoesNotParticipateInAutoDirection(aElement)) {
689 bool setAncestorDirAutoFlag =
690 #ifdef DEBUG
691 true;
692 #else
693 !aElement->AncestorHasDirAuto();
694 #endif
695
696 if (setAncestorDirAutoFlag) {
697 nsIContent* child = aElement->GetFirstChild();
698 while (child) {
699 if (child->IsElement() &&
700 DoesNotAffectDirectionOfAncestors(child->AsElement())) {
701 child = child->GetNextNonChildNode(aElement);
702 continue;
703 }
704
705 MOZ_ASSERT(
706 !aElement->AncestorHasDirAuto() || child->AncestorHasDirAuto(),
707 "AncestorHasDirAuto set on node but not its children");
708 child->SetAncestorHasDirAuto();
709 child = child->GetNextNode(aElement);
710 }
711 }
712 }
713
714 nsTextNode* textNode = WalkDescendantsSetDirectionFromText(aElement, aNotify);
715 if (textNode) {
716 nsTextNodeDirectionalityMap::AddEntryToMap(textNode, aElement);
717 }
718 }
719
WalkDescendantsClearAncestorDirAuto(Element * aElement)720 void WalkDescendantsClearAncestorDirAuto(Element* aElement) {
721 nsIContent* child = aElement->GetFirstChild();
722 while (child) {
723 if (child->IsElement() && child->AsElement()->HasDirAuto()) {
724 child = child->GetNextNonChildNode(aElement);
725 continue;
726 }
727
728 child->ClearAncestorHasDirAuto();
729 child = child->GetNextNode(aElement);
730 }
731 }
732
SetAncestorDirectionIfAuto(nsTextNode * aTextNode,Directionality aDir,bool aNotify=true)733 void SetAncestorDirectionIfAuto(nsTextNode* aTextNode, Directionality aDir,
734 bool aNotify = true) {
735 MOZ_ASSERT(aTextNode->NodeType() == nsINode::TEXT_NODE,
736 "Must be a text node");
737
738 Element* parent = aTextNode->GetParentElement();
739 while (parent && parent->NodeOrAncestorHasDirAuto()) {
740 if (DoesNotParticipateInAutoDirection(parent) || parent->HasFixedDir()) {
741 break;
742 }
743
744 if (parent->HasDirAuto()) {
745 bool resetDirection = false;
746 nsTextNode* directionWasSetByTextNode = static_cast<nsTextNode*>(
747 parent->GetProperty(nsGkAtoms::dirAutoSetBy));
748
749 if (!parent->HasDirAutoSet()) {
750 // Fast path if parent's direction is not yet set by any descendant
751 MOZ_ASSERT(!directionWasSetByTextNode,
752 "dirAutoSetBy property should be null");
753 resetDirection = true;
754 } else {
755 // If parent's direction is already set, we need to know if
756 // aTextNode is before or after the text node that had set it.
757 // We will walk parent's descendants in tree order starting from
758 // aTextNode to optimize for the most common case where text nodes are
759 // being appended to tree.
760 if (!directionWasSetByTextNode) {
761 resetDirection = true;
762 } else if (directionWasSetByTextNode != aTextNode) {
763 nsIContent* child = aTextNode->GetNextNode(parent);
764 while (child) {
765 if (child->IsElement() &&
766 DoesNotAffectDirectionOfAncestors(child->AsElement())) {
767 child = child->GetNextNonChildNode(parent);
768 continue;
769 }
770
771 if (child == directionWasSetByTextNode) {
772 // we found the node that set the element's direction after our
773 // text node, so we need to reset the direction
774 resetDirection = true;
775 break;
776 }
777
778 child = child->GetNextNode(parent);
779 }
780 }
781 }
782
783 if (resetDirection) {
784 if (directionWasSetByTextNode) {
785 nsTextNodeDirectionalityMap::RemoveElementFromMap(
786 directionWasSetByTextNode, parent);
787 }
788 parent->SetDirectionality(aDir, aNotify);
789 nsTextNodeDirectionalityMap::AddEntryToMap(aTextNode, parent);
790 SetDirectionalityOnDescendants(parent, aDir, aNotify);
791 }
792
793 // Since we found an element with dir=auto, we can stop walking the
794 // parent chain: none of its ancestors will have their direction set by
795 // any of its descendants.
796 return;
797 }
798 parent = parent->GetParentElement();
799 }
800 }
801
TextNodeWillChangeDirection(nsIContent * aTextNode,Directionality * aOldDir,uint32_t aOffset)802 bool TextNodeWillChangeDirection(nsIContent* aTextNode, Directionality* aOldDir,
803 uint32_t aOffset) {
804 if (!NodeAffectsDirAutoAncestor(aTextNode)) {
805 nsTextNodeDirectionalityMap::EnsureMapIsClearFor(aTextNode);
806 return false;
807 }
808
809 uint32_t firstStrong;
810 *aOldDir = GetDirectionFromText(aTextNode->GetText(), &firstStrong);
811 return (aOffset <= firstStrong);
812 }
813
TextNodeChangedDirection(nsTextNode * aTextNode,Directionality aOldDir,bool aNotify)814 void TextNodeChangedDirection(nsTextNode* aTextNode, Directionality aOldDir,
815 bool aNotify) {
816 Directionality newDir = GetDirectionFromText(aTextNode->GetText());
817 if (newDir == eDir_NotSet) {
818 if (aOldDir != eDir_NotSet && aTextNode->HasTextNodeDirectionalityMap()) {
819 // This node used to have a strong directional character but no
820 // longer does. ResetTextNodeDirection() will re-resolve the
821 // directionality of any elements whose directionality was
822 // determined by this node.
823 nsTextNodeDirectionalityMap::ResetTextNodeDirection(aTextNode, aTextNode);
824 }
825 } else {
826 // This node has a strong directional character. If it has a
827 // TextNodeDirectionalityMap property, it already determines the
828 // directionality of some element(s), so call UpdateTextNodeDirection to
829 // reresolve their directionality. If it has no map, or if
830 // UpdateTextNodeDirection returns zero, indicating that the map is
831 // empty, call SetAncestorDirectionIfAuto to find ancestor elements
832 // which should have their directionality determined by this node.
833 if (aTextNode->HasTextNodeDirectionalityMap() &&
834 nsTextNodeDirectionalityMap::UpdateTextNodeDirection(aTextNode,
835 newDir)) {
836 return;
837 }
838 SetAncestorDirectionIfAuto(aTextNode, newDir, aNotify);
839 }
840 }
841
SetDirectionFromNewTextNode(nsTextNode * aTextNode)842 void SetDirectionFromNewTextNode(nsTextNode* aTextNode) {
843 if (!NodeAffectsDirAutoAncestor(aTextNode)) {
844 return;
845 }
846
847 Element* parent = aTextNode->GetParentElement();
848 if (parent && parent->NodeOrAncestorHasDirAuto()) {
849 aTextNode->SetAncestorHasDirAuto();
850 }
851
852 Directionality dir = GetDirectionFromText(aTextNode->GetText());
853 if (dir != eDir_NotSet) {
854 SetAncestorDirectionIfAuto(aTextNode, dir);
855 }
856 }
857
ResetDirectionSetByTextNode(nsTextNode * aTextNode)858 void ResetDirectionSetByTextNode(nsTextNode* aTextNode) {
859 if (!NodeAffectsDirAutoAncestor(aTextNode)) {
860 nsTextNodeDirectionalityMap::EnsureMapIsClearFor(aTextNode);
861 return;
862 }
863
864 Directionality dir = GetDirectionFromText(aTextNode->GetText());
865 if (dir != eDir_NotSet && aTextNode->HasTextNodeDirectionalityMap()) {
866 nsTextNodeDirectionalityMap::ResetTextNodeDirection(aTextNode, aTextNode);
867 }
868 }
869
SetDirectionalityFromValue(Element * aElement,const nsAString & value,bool aNotify)870 void SetDirectionalityFromValue(Element* aElement, const nsAString& value,
871 bool aNotify) {
872 Directionality dir =
873 GetDirectionFromText(PromiseFlatString(value).get(), value.Length());
874 if (dir == eDir_NotSet) {
875 dir = eDir_LTR;
876 }
877
878 aElement->SetDirectionality(dir, aNotify);
879 }
880
OnSetDirAttr(Element * aElement,const nsAttrValue * aNewValue,bool hadValidDir,bool hadDirAuto,bool aNotify)881 void OnSetDirAttr(Element* aElement, const nsAttrValue* aNewValue,
882 bool hadValidDir, bool hadDirAuto, bool aNotify) {
883 if (aElement->IsHTMLElement(nsGkAtoms::input)) {
884 return;
885 }
886
887 if (aElement->AncestorHasDirAuto()) {
888 if (!hadValidDir) {
889 // The element is a descendant of an element with dir = auto, is
890 // having its dir attribute set, and previously didn't have a valid dir
891 // attribute.
892 // Check whether any of its text node descendants determine the
893 // direction of any of its ancestors, and redetermine their direction
894 WalkDescendantsResetAutoDirection(aElement);
895 } else if (!aElement->HasValidDir()) {
896 // The element is a descendant of an element with dir = auto and is
897 // having its dir attribute removed or set to an invalid value.
898 // Reset the direction of any of its ancestors whose direction is
899 // determined by a text node descendant
900 WalkAncestorsResetAutoDirection(aElement, aNotify);
901 }
902 } else if (hadDirAuto && !aElement->HasDirAuto()) {
903 // The element isn't a descendant of an element with dir = auto, and is
904 // having its dir attribute set to something other than auto.
905 // Walk the descendant tree and clear the AncestorHasDirAuto flag.
906 //
907 // N.B: For elements other than <bdi> it would be enough to test that the
908 // current value of dir was "auto" in BeforeSetAttr to know that we
909 // were unsetting dir="auto". For <bdi> things are more complicated,
910 // since it behaves like dir="auto" whenever the dir attribute is
911 // empty or invalid, so we would have to check whether the old value
912 // was not either "ltr" or "rtl", and the new value was either "ltr"
913 // or "rtl". Element::HasDirAuto() encapsulates all that, so doing it
914 // here is simpler.
915 WalkDescendantsClearAncestorDirAuto(aElement);
916 }
917
918 if (aElement->HasDirAuto()) {
919 WalkDescendantsSetDirAuto(aElement, aNotify);
920 } else {
921 if (aElement->HasDirAutoSet()) {
922 nsTextNode* setByNode = static_cast<nsTextNode*>(
923 aElement->GetProperty(nsGkAtoms::dirAutoSetBy));
924 nsTextNodeDirectionalityMap::RemoveElementFromMap(setByNode, aElement);
925 }
926 SetDirectionalityOnDescendants(
927 aElement, RecomputeDirectionality(aElement, aNotify), aNotify);
928 }
929 }
930
SetDirOnBind(mozilla::dom::Element * aElement,nsIContent * aParent)931 void SetDirOnBind(mozilla::dom::Element* aElement, nsIContent* aParent) {
932 // Set the AncestorHasDirAuto flag, unless this element shouldn't affect
933 // ancestors that have dir=auto
934 if (!DoesNotParticipateInAutoDirection(aElement) &&
935 !aElement->IsHTMLElement(nsGkAtoms::bdi) && aParent &&
936 aParent->NodeOrAncestorHasDirAuto()) {
937 aElement->SetAncestorHasDirAuto();
938
939 nsIContent* child = aElement->GetFirstChild();
940 if (child) {
941 // If we are binding an element to the tree that already has descendants,
942 // and the parent has NodeHasDirAuto or NodeAncestorHasDirAuto, we need
943 // to set NodeAncestorHasDirAuto on all the element's descendants, except
944 // for nodes that don't affect the direction of their ancestors.
945 do {
946 if (child->IsElement() &&
947 DoesNotAffectDirectionOfAncestors(child->AsElement())) {
948 child = child->GetNextNonChildNode(aElement);
949 continue;
950 }
951
952 child->SetAncestorHasDirAuto();
953 child = child->GetNextNode(aElement);
954 } while (child);
955
956 // We may also need to reset the direction of an ancestor with dir=auto
957 WalkAncestorsResetAutoDirection(aElement, true);
958 }
959 }
960
961 if (!aElement->HasDirAuto()) {
962 // if the element doesn't have dir=auto, set its own directionality from
963 // the dir attribute or by inheriting from its ancestors.
964 RecomputeDirectionality(aElement, false);
965 }
966 }
967
ResetDir(mozilla::dom::Element * aElement)968 void ResetDir(mozilla::dom::Element* aElement) {
969 if (aElement->HasDirAutoSet()) {
970 nsTextNode* setByNode = static_cast<nsTextNode*>(
971 aElement->GetProperty(nsGkAtoms::dirAutoSetBy));
972 nsTextNodeDirectionalityMap::RemoveElementFromMap(setByNode, aElement);
973 }
974
975 if (!aElement->HasDirAuto()) {
976 RecomputeDirectionality(aElement, false);
977 }
978 }
979
980 } // end namespace mozilla
981