1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/base/src/DirectionalityUtils.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1027 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=2 sw=2 et tw=78: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/*
1.11 + Implementation description from https://etherpad.mozilla.org/dir-auto
1.12 +
1.13 + Static case
1.14 + ===========
1.15 + When we see a new content node with @dir=auto from the parser, we set the
1.16 + NodeHasDirAuto flag on the node. We won't have enough information to
1.17 + decide the directionality of the node at this point.
1.18 +
1.19 + When we bind a new content node to the document, if its parent has either of
1.20 + the NodeAncestorHasDirAuto or NodeHasDirAuto flags, we set the
1.21 + NodeAncestorHasDirAuto flag on the node.
1.22 +
1.23 + When a new input with @type=text/search/tel/url/email and @dir=auto is added
1.24 + from the parser, we resolve the directionality based on its @value.
1.25 +
1.26 + When a new text node with non-neutral content is appended to a textarea
1.27 + element with NodeHasDirAuto, if the directionality of the textarea element
1.28 + is still unresolved, it is resolved based on the value of the text node.
1.29 + Elements with unresolved directionality behave as LTR.
1.30 +
1.31 + When a new text node with non-neutral content is appended to an element that
1.32 + is not a textarea but has either of the NodeAncestorHasDirAuto or
1.33 + NodeHasDirAuto flags, we walk up the parent chain while the
1.34 + NodeAncestorHasDirAuto flag is present, and when we reach an element with
1.35 + NodeHasDirAuto and no resolved directionality, we resolve the directionality
1.36 + based on the contents of the text node and cease walking the parent chain.
1.37 + Note that we should ignore elements with NodeHasDirAuto with resolved
1.38 + directionality, so that the second text node in this example tree doesn't
1.39 + affect the directionality of the div:
1.40 +
1.41 + <div dir=auto>
1.42 + <span>foo</span>
1.43 + <span>بار</span>
1.44 + </div>
1.45 +
1.46 + The parent chain walk will be aborted if we hit a script or style element, or
1.47 + if we hit an element with @dir=ltr or @dir=rtl.
1.48 +
1.49 + I will call this algorithm "upward propagation".
1.50 +
1.51 + Each text node should maintain a list of elements which have their
1.52 + directionality determined by the first strong character of that text node.
1.53 + This is useful to make dynamic changes more efficient. One way to implement
1.54 + this is to have a per-document hash table mapping a text node to a set of
1.55 + elements. I'll call this data structure TextNodeDirectionalityMap. The
1.56 + algorithm for appending a new text node above needs to update this data
1.57 + structure.
1.58 +
1.59 + *IMPLEMENTATION NOTE*
1.60 + In practice, the implementation uses two per-node properties:
1.61 +
1.62 + dirAutoSetBy, which is set on a node with auto-directionality, and points to
1.63 + the textnode that contains the strong character which determines the
1.64 + directionality of the node.
1.65 +
1.66 + textNodeDirectionalityMap, which is set on a text node and points to a hash
1.67 + table listing the nodes whose directionality is determined by the text node.
1.68 +
1.69 + Handling dynamic changes
1.70 + ========================
1.71 +
1.72 + We need to handle the following cases:
1.73 +
1.74 + 1. When the value of an input element with @type=text/search/tel/url/email is
1.75 + changed, if it has NodeHasDirAuto, we update the resolved directionality.
1.76 +
1.77 + 2. When the dir attribute is changed from something else (including the case
1.78 + where it doesn't exist) to auto on a textarea or an input element with
1.79 + @type=text/search/tel/url/email, we set the NodeHasDirAuto flag and resolve
1.80 + the directionality based on the value of the element.
1.81 +
1.82 + 3. When the dir attribute is changed from something else (including the case
1.83 + where it doesn't exist) to auto on any element except case 1 above and the bdi
1.84 + element, we run the following algorithm:
1.85 + * We set the NodeHasDirAuto flag.
1.86 + * If the element doesn't have the NodeAncestorHasDirAuto flag, we set the
1.87 + NodeAncestorHasDirAuto flag on all of its child nodes. (Note that if the
1.88 + element does have NodeAncestorHasDirAuto, all of its children should
1.89 + already have this flag too. We can assert this in debug builds.)
1.90 + * To resolve the directionality of the element, we run the algorithm explained
1.91 + in http://www.whatwg.org/specs/web-apps/current-work/multipage/elements.html#the-dir-attribute
1.92 + (I'll call this the "downward propagation algorithm".) by walking the child
1.93 + subtree in tree order. Note that an element with @dir=auto should not affect
1.94 + other elements in its document with @dir=auto. So there is no need to walk up
1.95 + the parent chain in this case. TextNodeDirectionalityMap needs to be updated
1.96 + as appropriate.
1.97 +
1.98 + 3a. When the dir attribute is set to any valid value on an element that didn't
1.99 + have a valid dir attribute before, this means that any descendant of that
1.100 + element will not affect the directionality of any of its ancestors. So we need
1.101 + to check whether any text node descendants of the element are listed in
1.102 + TextNodeDirectionalityMap, and whether the elements whose direction they set
1.103 + are ancestors of the element. If so, we need to rerun the downward propagation
1.104 + algorithm for those ancestors.
1.105 +
1.106 + 4. When the dir attribute is changed from auto to something else (including
1.107 + the case where it gets removed) on a textarea or an input element with
1.108 + @type=text/search/tel/url/email, we unset the NodeHasDirAuto flag and
1.109 + resolve the directionality based on the directionality of the value of the @dir
1.110 + attribute on element itself or its parent element.
1.111 +
1.112 + 5. When the dir attribute is changed from auto to something else (including the
1.113 + case where it gets removed) on any element except case 4 above and the bdi
1.114 + element, we run the following algorithm:
1.115 + * We unset the NodeHasDirAuto flag.
1.116 + * If the element does not have the NodeAncestorHasDirAuto flag, we unset
1.117 + the NodeAncestorHasDirAuto flag on all of its child nodes, except those
1.118 + who are a descendant of another element with NodeHasDirAuto. (Note that if
1.119 + the element has the NodeAncestorHasDirAuto flag, all of its child nodes
1.120 + should still retain the same flag.)
1.121 + * We resolve the directionality of the element based on the value of the @dir
1.122 + attribute on the element itself or its parent element.
1.123 + TextNodeDirectionalityMap needs to be updated as appropriate.
1.124 +
1.125 + 5a. When the dir attribute is removed or set to an invalid value on any
1.126 + element (except a bdi element) with the NodeAncestorHasDirAuto flag which
1.127 + previously had a valid dir attribute, it might have a text node descendant that
1.128 + did not previously affect the directionality of any of its ancestors but should
1.129 + now begin to affect them.
1.130 + We run the following algorithm:
1.131 + * Walk up the parent chain from the element.
1.132 + * For any element that appears in the TextNodeDirectionalityMap, remove the
1.133 + element from the map and rerun the downward propagation algorithm
1.134 + (see section 3).
1.135 + * If we reach an element without either of the NodeHasDirAuto or
1.136 + NodeAncestorHasDirAuto flags, abort the parent chain walk.
1.137 +
1.138 + 6. When an element with @dir=auto is added to the document, we should handle it
1.139 + similar to the case 2/3 above.
1.140 +
1.141 + 7. When an element with NodeHasDirAuto or NodeAncestorHasDirAuto is
1.142 + removed from the document, we should handle it similar to the case 4/5 above,
1.143 + except that we don't need to handle anything in the child subtree. We should
1.144 + also remove all of the occurrences of that node and its descendants from
1.145 + TextNodeDirectionalityMap. (This is the conceptual description of what needs to
1.146 + happen but in the implementation UnbindFromTree is going to be called on all of
1.147 + the descendants so we don't need to descend into the child subtree).
1.148 +
1.149 + 8. When the contents of a text node is changed either from script or by the
1.150 + user, we need to run the following algorithm:
1.151 + * If the change has happened after the first character with strong
1.152 + directionality in the text node, do nothing.
1.153 + * If the text node is a child of a bdi, script or style element, do nothing.
1.154 + * If the text node belongs to a textarea with NodeHasDirAuto, we need to
1.155 + update the directionality of the textarea.
1.156 + * Grab a list of elements affected by this text node from
1.157 + TextNodeDirectionalityMap and re-resolve the directionality of each one of them
1.158 + based on the new contents of the text node.
1.159 + * If the text node does not exist in TextNodeDirectionalityMap, and it has the
1.160 + NodeAncestorHasDirAuto flag set, this could potentially be a text node
1.161 + which is going to start affecting the directionality of its parent @dir=auto
1.162 + elements. In this case, we need to fall back to the (potentially expensive)
1.163 + "upward propagation algorithm". The TextNodeDirectionalityMap data structure
1.164 + needs to be update during this algorithm.
1.165 + * If the new contents of the text node do not have any strong characters, and
1.166 + the old contents used to, and the text node used to exist in
1.167 + TextNodeDirectionalityMap and it has the NodeAncestorHasDirAuto flag set,
1.168 + the elements associated with this text node inside TextNodeDirectionalityMap
1.169 + will now get their directionality from another text node. In this case, for
1.170 + each element in the list retrieved from TextNodeDirectionalityMap, run the
1.171 + downward propagation algorithm (section 3), and remove the text node from
1.172 + TextNodeDirectionalityMap.
1.173 +
1.174 + 9. When a new text node is injected into a document, we need to run the
1.175 + following algorithm:
1.176 + * If the contents of the text node do not have any characters with strong
1.177 + direction, do nothing.
1.178 + * If the text node is a child of a bdi, script or style element, do nothing.
1.179 + * If the text node is appended to a textarea element with NodeHasDirAuto, we
1.180 + need to update the directionality of the textarea.
1.181 + * If the text node has NodeAncestorHasDirAuto, we need to run the "upward
1.182 + propagation algorithm". The TextNodeDirectionalityMap data structure needs to
1.183 + be update during this algorithm.
1.184 +
1.185 + 10. When a text node is removed from a document, we need to run the following
1.186 + algorithm:
1.187 + * If the contents of the text node do not have any characters with strong
1.188 + direction, do nothing.
1.189 + * If the text node is a child of a bdi, script or style element, do nothing.
1.190 + * If the text node is removed from a textarea element with NodeHasDirAuto,
1.191 + set the directionality to "ltr". (This is what the spec currently says, but I'm
1.192 + filing a spec bug to get it fixed -- the directionality should depend on the
1.193 + parent element here.)
1.194 + * If the text node has NodeAncestorHasDirAuto, we need to look at the list
1.195 + of elements being affected by this text node from TextNodeDirectionalityMap,
1.196 + run the "downward propagation algorithm" (section 3) for each one of them,
1.197 + while updating TextNodeDirectionalityMap along the way.
1.198 +
1.199 + 11. If the value of the @dir attribute on a bdi element is changed to an
1.200 + invalid value (or if it's removed), determine the new directionality similar
1.201 + to the case 3 above.
1.202 +
1.203 + == Implemention Notes ==
1.204 + When a new node gets bound to the tree, the BindToTree function gets called.
1.205 + The reverse case is UnbindFromTree.
1.206 + When the contents of a text node change, nsGenericDOMDataNode::SetTextInternal
1.207 + gets called.
1.208 + */
1.209 +
1.210 +#include "mozilla/dom/DirectionalityUtils.h"
1.211 +
1.212 +#include "nsINode.h"
1.213 +#include "nsIContent.h"
1.214 +#include "nsIDocument.h"
1.215 +#include "mozilla/DebugOnly.h"
1.216 +#include "mozilla/dom/Element.h"
1.217 +#include "nsIDOMHTMLDocument.h"
1.218 +#include "nsUnicodeProperties.h"
1.219 +#include "nsTextFragment.h"
1.220 +#include "nsAttrValue.h"
1.221 +#include "nsTextNode.h"
1.222 +#include "nsCheapSets.h"
1.223 +
1.224 +namespace mozilla {
1.225 +
1.226 +using mozilla::dom::Element;
1.227 +
1.228 +/**
1.229 + * Returns true if aElement is one of the elements whose text content should not
1.230 + * affect its own direction, nor the direction of ancestors with dir=auto.
1.231 + *
1.232 + * Note that this does not include <bdi>, whose content does affect its own
1.233 + * direction when it has dir=auto (which it has by default), so one needs to
1.234 + * test for it separately, e.g. with DoesNotAffectDirectionOfAncestors.
1.235 + * It *does* include textarea, because even if a textarea has dir=auto, it has
1.236 + * unicode-bidi: plaintext and is handled automatically in bidi resolution.
1.237 + */
1.238 +static bool
1.239 +DoesNotParticipateInAutoDirection(const Element* aElement)
1.240 +{
1.241 + nsINodeInfo* nodeInfo = aElement->NodeInfo();
1.242 + return (!aElement->IsHTML() ||
1.243 + nodeInfo->Equals(nsGkAtoms::script) ||
1.244 + nodeInfo->Equals(nsGkAtoms::style) ||
1.245 + nodeInfo->Equals(nsGkAtoms::textarea) ||
1.246 + aElement->IsInAnonymousSubtree());
1.247 +}
1.248 +
1.249 +static inline bool
1.250 +IsBdiWithoutDirAuto(const Element* aElement)
1.251 +{
1.252 + // We are testing for bdi elements without explicit dir="auto", so we can't
1.253 + // use the HasDirAuto() flag, since that will return true for bdi element with
1.254 + // no dir attribute or an invalid dir attribute
1.255 + return (aElement->IsHTML(nsGkAtoms::bdi) &&
1.256 + (!aElement->HasValidDir() || aElement->HasFixedDir()));
1.257 +}
1.258 +
1.259 +/**
1.260 + * Returns true if aElement is one of the element whose text content should not
1.261 + * affect the direction of ancestors with dir=auto (though it may affect its own
1.262 + * direction, e.g. <bdi>)
1.263 + */
1.264 +static bool
1.265 +DoesNotAffectDirectionOfAncestors(const Element* aElement)
1.266 +{
1.267 + return (DoesNotParticipateInAutoDirection(aElement) ||
1.268 + IsBdiWithoutDirAuto(aElement) ||
1.269 + aElement->HasFixedDir());
1.270 +}
1.271 +
1.272 +/**
1.273 + * Returns the directionality of a Unicode character
1.274 + */
1.275 +static Directionality
1.276 +GetDirectionFromChar(uint32_t ch)
1.277 +{
1.278 + switch(mozilla::unicode::GetBidiCat(ch)) {
1.279 + case eCharType_RightToLeft:
1.280 + case eCharType_RightToLeftArabic:
1.281 + return eDir_RTL;
1.282 +
1.283 + case eCharType_LeftToRight:
1.284 + return eDir_LTR;
1.285 +
1.286 + default:
1.287 + return eDir_NotSet;
1.288 + }
1.289 +}
1.290 +
1.291 +inline static bool NodeAffectsDirAutoAncestor(nsINode* aTextNode)
1.292 +{
1.293 + Element* parent = aTextNode->GetParentElement();
1.294 + return (parent &&
1.295 + !DoesNotParticipateInAutoDirection(parent) &&
1.296 + parent->NodeOrAncestorHasDirAuto());
1.297 +}
1.298 +
1.299 +/**
1.300 + * Various methods for returning the directionality of a string using the
1.301 + * first-strong algorithm defined in http://unicode.org/reports/tr9/#P2
1.302 + *
1.303 + * @param[out] aFirstStrong the offset to the first character in the string with
1.304 + * strong directionality, or UINT32_MAX if there is none (return
1.305 + value is eDir_NotSet).
1.306 + * @return the directionality of the string
1.307 + */
1.308 +static Directionality
1.309 +GetDirectionFromText(const char16_t* aText, const uint32_t aLength,
1.310 + uint32_t* aFirstStrong = nullptr)
1.311 +{
1.312 + const char16_t* start = aText;
1.313 + const char16_t* end = aText + aLength;
1.314 +
1.315 + while (start < end) {
1.316 + uint32_t current = start - aText;
1.317 + uint32_t ch = *start++;
1.318 +
1.319 + if (NS_IS_HIGH_SURROGATE(ch) &&
1.320 + start < end &&
1.321 + NS_IS_LOW_SURROGATE(*start)) {
1.322 + ch = SURROGATE_TO_UCS4(ch, *start++);
1.323 + current++;
1.324 + }
1.325 +
1.326 + // Just ignore lone surrogates
1.327 + if (!IS_SURROGATE(ch)) {
1.328 + Directionality dir = GetDirectionFromChar(ch);
1.329 + if (dir != eDir_NotSet) {
1.330 + if (aFirstStrong) {
1.331 + *aFirstStrong = current;
1.332 + }
1.333 + return dir;
1.334 + }
1.335 + }
1.336 + }
1.337 +
1.338 + if (aFirstStrong) {
1.339 + *aFirstStrong = UINT32_MAX;
1.340 + }
1.341 + return eDir_NotSet;
1.342 +}
1.343 +
1.344 +static Directionality
1.345 +GetDirectionFromText(const char* aText, const uint32_t aLength,
1.346 + uint32_t* aFirstStrong = nullptr)
1.347 +{
1.348 + const char* start = aText;
1.349 + const char* end = aText + aLength;
1.350 +
1.351 + while (start < end) {
1.352 + uint32_t current = start - aText;
1.353 + unsigned char ch = (unsigned char)*start++;
1.354 +
1.355 + Directionality dir = GetDirectionFromChar(ch);
1.356 + if (dir != eDir_NotSet) {
1.357 + if (aFirstStrong) {
1.358 + *aFirstStrong = current;
1.359 + }
1.360 + return dir;
1.361 + }
1.362 + }
1.363 +
1.364 + if (aFirstStrong) {
1.365 + *aFirstStrong = UINT32_MAX;
1.366 + }
1.367 + return eDir_NotSet;
1.368 +}
1.369 +
1.370 +static Directionality
1.371 +GetDirectionFromText(const nsTextFragment* aFrag,
1.372 + uint32_t* aFirstStrong = nullptr)
1.373 +{
1.374 + if (aFrag->Is2b()) {
1.375 + return GetDirectionFromText(aFrag->Get2b(), aFrag->GetLength(),
1.376 + aFirstStrong);
1.377 + }
1.378 +
1.379 + return GetDirectionFromText(aFrag->Get1b(), aFrag->GetLength(),
1.380 + aFirstStrong);
1.381 +}
1.382 +
1.383 +/**
1.384 + * Set the directionality of a node with dir=auto as defined in
1.385 + * http://www.whatwg.org/specs/web-apps/current-work/multipage/elements.html#the-directionality
1.386 + *
1.387 + * @param[in] changedNode If we call this method because the content of a text
1.388 + * node is about to change, pass in the changed node, so that we
1.389 + * know not to return it
1.390 + * @return the text node containing the character that determined the direction
1.391 + */
1.392 +static nsINode*
1.393 +WalkDescendantsSetDirectionFromText(Element* aElement, bool aNotify = true,
1.394 + nsINode* aChangedNode = nullptr)
1.395 +{
1.396 + MOZ_ASSERT(aElement, "Must have an element");
1.397 + MOZ_ASSERT(aElement->HasDirAuto(), "Element must have dir=auto");
1.398 +
1.399 + if (DoesNotParticipateInAutoDirection(aElement)) {
1.400 + return nullptr;
1.401 + }
1.402 +
1.403 + nsIContent* child = aElement->GetFirstChild();
1.404 + while (child) {
1.405 + if (child->IsElement() &&
1.406 + DoesNotAffectDirectionOfAncestors(child->AsElement())) {
1.407 + child = child->GetNextNonChildNode(aElement);
1.408 + continue;
1.409 + }
1.410 +
1.411 + if (child->NodeType() == nsIDOMNode::TEXT_NODE &&
1.412 + child != aChangedNode) {
1.413 + Directionality textNodeDir = GetDirectionFromText(child->GetText());
1.414 + if (textNodeDir != eDir_NotSet) {
1.415 + // We found a descendant text node with strong directional characters.
1.416 + // Set the directionality of aElement to the corresponding value.
1.417 + aElement->SetDirectionality(textNodeDir, aNotify);
1.418 + return child;
1.419 + }
1.420 + }
1.421 + child = child->GetNextNode(aElement);
1.422 + }
1.423 +
1.424 + // We walked all the descendants without finding a text node with strong
1.425 + // directional characters. Set the directionality to LTR
1.426 + aElement->SetDirectionality(eDir_LTR, aNotify);
1.427 + return nullptr;
1.428 +}
1.429 +
1.430 +class nsTextNodeDirectionalityMap
1.431 +{
1.432 + static void
1.433 + nsTextNodeDirectionalityMapDtor(void *aObject, nsIAtom* aPropertyName,
1.434 + void *aPropertyValue, void* aData)
1.435 + {
1.436 + nsINode* textNode = static_cast<nsINode * >(aObject);
1.437 + textNode->ClearHasTextNodeDirectionalityMap();
1.438 +
1.439 + nsTextNodeDirectionalityMap* map =
1.440 + reinterpret_cast<nsTextNodeDirectionalityMap * >(aPropertyValue);
1.441 + map->EnsureMapIsClear(textNode);
1.442 + delete map;
1.443 + }
1.444 +
1.445 +public:
1.446 + nsTextNodeDirectionalityMap(nsINode* aTextNode)
1.447 + {
1.448 + MOZ_ASSERT(aTextNode, "Null text node");
1.449 + MOZ_COUNT_CTOR(nsTextNodeDirectionalityMap);
1.450 + aTextNode->SetProperty(nsGkAtoms::textNodeDirectionalityMap, this,
1.451 + nsTextNodeDirectionalityMapDtor);
1.452 + aTextNode->SetHasTextNodeDirectionalityMap();
1.453 + }
1.454 +
1.455 + ~nsTextNodeDirectionalityMap()
1.456 + {
1.457 + MOZ_COUNT_DTOR(nsTextNodeDirectionalityMap);
1.458 + }
1.459 +
1.460 + void AddEntry(nsINode* aTextNode, Element* aElement)
1.461 + {
1.462 + if (!mElements.Contains(aElement)) {
1.463 + mElements.Put(aElement);
1.464 + aElement->SetProperty(nsGkAtoms::dirAutoSetBy, aTextNode);
1.465 + aElement->SetHasDirAutoSet();
1.466 + }
1.467 + }
1.468 +
1.469 + void RemoveEntry(nsINode* aTextNode, Element* aElement)
1.470 + {
1.471 + NS_ASSERTION(mElements.Contains(aElement),
1.472 + "element already removed from map");
1.473 +
1.474 + mElements.Remove(aElement);
1.475 + aElement->ClearHasDirAutoSet();
1.476 + aElement->UnsetProperty(nsGkAtoms::dirAutoSetBy);
1.477 + }
1.478 +
1.479 +private:
1.480 + nsCheapSet<nsPtrHashKey<Element> > mElements;
1.481 +
1.482 + static nsTextNodeDirectionalityMap* GetDirectionalityMap(nsINode* aTextNode)
1.483 + {
1.484 + MOZ_ASSERT(aTextNode->NodeType() == nsIDOMNode::TEXT_NODE,
1.485 + "Must be a text node");
1.486 + nsTextNodeDirectionalityMap* map = nullptr;
1.487 +
1.488 + if (aTextNode->HasTextNodeDirectionalityMap()) {
1.489 + map = static_cast<nsTextNodeDirectionalityMap * >
1.490 + (aTextNode->GetProperty(nsGkAtoms::textNodeDirectionalityMap));
1.491 + }
1.492 +
1.493 + return map;
1.494 + }
1.495 +
1.496 + static PLDHashOperator SetNodeDirection(nsPtrHashKey<Element>* aEntry, void* aDir)
1.497 + {
1.498 + MOZ_ASSERT(aEntry->GetKey()->IsElement(), "Must be an Element");
1.499 + aEntry->GetKey()->SetDirectionality(*reinterpret_cast<Directionality*>(aDir),
1.500 + true);
1.501 + return PL_DHASH_NEXT;
1.502 + }
1.503 +
1.504 + static PLDHashOperator ResetNodeDirection(nsPtrHashKey<Element>* aEntry, void* aData)
1.505 + {
1.506 + MOZ_ASSERT(aEntry->GetKey()->IsElement(), "Must be an Element");
1.507 + // run the downward propagation algorithm
1.508 + // and remove the text node from the map
1.509 + nsINode* oldTextNode = static_cast<Element*>(aData);
1.510 + Element* rootNode = aEntry->GetKey();
1.511 + nsINode* newTextNode = nullptr;
1.512 + if (oldTextNode && rootNode->HasDirAuto()) {
1.513 + newTextNode = WalkDescendantsSetDirectionFromText(rootNode, true,
1.514 + oldTextNode);
1.515 + }
1.516 + if (newTextNode) {
1.517 + nsTextNodeDirectionalityMap::AddEntryToMap(newTextNode, rootNode);
1.518 + } else {
1.519 + rootNode->ClearHasDirAutoSet();
1.520 + rootNode->UnsetProperty(nsGkAtoms::dirAutoSetBy);
1.521 + }
1.522 + return PL_DHASH_REMOVE;
1.523 + }
1.524 +
1.525 + static PLDHashOperator ClearEntry(nsPtrHashKey<Element>* aEntry, void* aData)
1.526 + {
1.527 + Element* rootNode = aEntry->GetKey();
1.528 + rootNode->ClearHasDirAutoSet();
1.529 + rootNode->UnsetProperty(nsGkAtoms::dirAutoSetBy);
1.530 + return PL_DHASH_REMOVE;
1.531 + }
1.532 +
1.533 +public:
1.534 + void UpdateAutoDirection(Directionality aDir)
1.535 + {
1.536 + mElements.EnumerateEntries(SetNodeDirection, &aDir);
1.537 + }
1.538 +
1.539 + void ClearAutoDirection()
1.540 + {
1.541 + mElements.EnumerateEntries(ResetNodeDirection, nullptr);
1.542 + }
1.543 +
1.544 + void ResetAutoDirection(nsINode* aTextNode)
1.545 + {
1.546 + mElements.EnumerateEntries(ResetNodeDirection, aTextNode);
1.547 + }
1.548 +
1.549 + void EnsureMapIsClear(nsINode* aTextNode)
1.550 + {
1.551 + DebugOnly<uint32_t> clearedEntries =
1.552 + mElements.EnumerateEntries(ClearEntry, aTextNode);
1.553 + MOZ_ASSERT(clearedEntries == 0, "Map should be empty already");
1.554 + }
1.555 +
1.556 + static void RemoveElementFromMap(nsINode* aTextNode, Element* aElement)
1.557 + {
1.558 + if (aTextNode->HasTextNodeDirectionalityMap()) {
1.559 + GetDirectionalityMap(aTextNode)->RemoveEntry(aTextNode, aElement);
1.560 + }
1.561 + }
1.562 +
1.563 + static void AddEntryToMap(nsINode* aTextNode, Element* aElement)
1.564 + {
1.565 + nsTextNodeDirectionalityMap* map = GetDirectionalityMap(aTextNode);
1.566 + if (!map) {
1.567 + map = new nsTextNodeDirectionalityMap(aTextNode);
1.568 + }
1.569 +
1.570 + map->AddEntry(aTextNode, aElement);
1.571 + }
1.572 +
1.573 + static void UpdateTextNodeDirection(nsINode* aTextNode, Directionality aDir)
1.574 + {
1.575 + MOZ_ASSERT(aTextNode->HasTextNodeDirectionalityMap(),
1.576 + "Map missing in UpdateTextNodeDirection");
1.577 + GetDirectionalityMap(aTextNode)->UpdateAutoDirection(aDir);
1.578 + }
1.579 +
1.580 + static void ClearTextNodeDirection(nsINode* aTextNode)
1.581 + {
1.582 + MOZ_ASSERT(aTextNode->HasTextNodeDirectionalityMap(),
1.583 + "Map missing in ResetTextNodeDirection");
1.584 + GetDirectionalityMap(aTextNode)->ClearAutoDirection();
1.585 + }
1.586 +
1.587 + static void ResetTextNodeDirection(nsINode* aTextNode)
1.588 + {
1.589 + MOZ_ASSERT(aTextNode->HasTextNodeDirectionalityMap(),
1.590 + "Map missing in ResetTextNodeDirection");
1.591 + GetDirectionalityMap(aTextNode)->ResetAutoDirection(aTextNode);
1.592 + }
1.593 +
1.594 + static void EnsureMapIsClearFor(nsINode* aTextNode)
1.595 + {
1.596 + if (aTextNode->HasTextNodeDirectionalityMap()) {
1.597 + GetDirectionalityMap(aTextNode)->EnsureMapIsClear(aTextNode);
1.598 + }
1.599 + }
1.600 +};
1.601 +
1.602 +Directionality
1.603 +RecomputeDirectionality(Element* aElement, bool aNotify)
1.604 +{
1.605 + MOZ_ASSERT(!aElement->HasDirAuto(),
1.606 + "RecomputeDirectionality called with dir=auto");
1.607 +
1.608 + Directionality dir = eDir_LTR;
1.609 +
1.610 + if (aElement->HasValidDir()) {
1.611 + dir = aElement->GetDirectionality();
1.612 + } else {
1.613 + Element* parent = aElement->GetParentElement();
1.614 + if (parent) {
1.615 + // If the element doesn't have an explicit dir attribute with a valid
1.616 + // value, the directionality is the same as the parent element (but
1.617 + // don't propagate the parent directionality if it isn't set yet).
1.618 + Directionality parentDir = parent->GetDirectionality();
1.619 + if (parentDir != eDir_NotSet) {
1.620 + dir = parentDir;
1.621 + }
1.622 + } else {
1.623 + // If there is no parent element and no dir attribute, the directionality
1.624 + // is LTR.
1.625 + dir = eDir_LTR;
1.626 + }
1.627 +
1.628 + aElement->SetDirectionality(dir, aNotify);
1.629 + }
1.630 + return dir;
1.631 +}
1.632 +
1.633 +void
1.634 +SetDirectionalityOnDescendants(Element* aElement, Directionality aDir,
1.635 + bool aNotify)
1.636 +{
1.637 + for (nsIContent* child = aElement->GetFirstChild(); child; ) {
1.638 + if (!child->IsElement()) {
1.639 + child = child->GetNextNode(aElement);
1.640 + continue;
1.641 + }
1.642 +
1.643 + Element* element = child->AsElement();
1.644 + if (element->HasValidDir() || element->HasDirAuto()) {
1.645 + child = child->GetNextNonChildNode(aElement);
1.646 + continue;
1.647 + }
1.648 + element->SetDirectionality(aDir, aNotify);
1.649 + child = child->GetNextNode(aElement);
1.650 + }
1.651 +}
1.652 +
1.653 +/**
1.654 + * Walk the parent chain of a text node whose dir attribute has been removed and
1.655 + * reset the direction of any of its ancestors which have dir=auto and whose
1.656 + * directionality is determined by a text node descendant.
1.657 + */
1.658 +void
1.659 +WalkAncestorsResetAutoDirection(Element* aElement, bool aNotify)
1.660 +{
1.661 + nsINode* setByNode;
1.662 + Element* parent = aElement->GetParentElement();
1.663 +
1.664 + while (parent && parent->NodeOrAncestorHasDirAuto()) {
1.665 + if (parent->HasDirAutoSet()) {
1.666 + // If the parent has the DirAutoSet flag, its direction is determined by
1.667 + // some text node descendant.
1.668 + // Remove it from the map and reset its direction by the downward
1.669 + // propagation algorithm
1.670 + setByNode =
1.671 + static_cast<nsINode*>(parent->GetProperty(nsGkAtoms::dirAutoSetBy));
1.672 + if (setByNode) {
1.673 + nsTextNodeDirectionalityMap::RemoveElementFromMap(setByNode, parent);
1.674 + }
1.675 + }
1.676 + if (parent->HasDirAuto()) {
1.677 + setByNode = WalkDescendantsSetDirectionFromText(parent, aNotify);
1.678 + if (setByNode) {
1.679 + nsTextNodeDirectionalityMap::AddEntryToMap(setByNode, parent);
1.680 + }
1.681 + break;
1.682 + }
1.683 + parent = parent->GetParentElement();
1.684 + }
1.685 +}
1.686 +
1.687 +void
1.688 +WalkDescendantsResetAutoDirection(Element* aElement)
1.689 +{
1.690 + nsIContent* child = aElement->GetFirstChild();
1.691 + while (child) {
1.692 + if (child->HasDirAuto()) {
1.693 + child = child->GetNextNonChildNode(aElement);
1.694 + continue;
1.695 + }
1.696 +
1.697 + if (child->HasTextNodeDirectionalityMap()) {
1.698 + nsTextNodeDirectionalityMap::ResetTextNodeDirection(child);
1.699 + nsTextNodeDirectionalityMap::EnsureMapIsClearFor(child);
1.700 + }
1.701 + child = child->GetNextNode(aElement);
1.702 + }
1.703 +}
1.704 +
1.705 +void
1.706 +WalkDescendantsSetDirAuto(Element* aElement, bool aNotify)
1.707 +{
1.708 + // Only test for DoesNotParticipateInAutoDirection -- in other words, if
1.709 + // aElement is a <bdi> which is having its dir attribute set to auto (or
1.710 + // removed or set to an invalid value, which are equivalent to dir=auto for
1.711 + // <bdi>, we *do* want to set AncestorHasDirAuto on its descendants, unlike
1.712 + // in SetDirOnBind where we don't propagate AncestorHasDirAuto to a <bdi>
1.713 + // being bound to an existing node with dir=auto.
1.714 + if (!DoesNotParticipateInAutoDirection(aElement)) {
1.715 +
1.716 + bool setAncestorDirAutoFlag =
1.717 +#ifdef DEBUG
1.718 + true;
1.719 +#else
1.720 + !aElement->AncestorHasDirAuto();
1.721 +#endif
1.722 +
1.723 + if (setAncestorDirAutoFlag) {
1.724 + nsIContent* child = aElement->GetFirstChild();
1.725 + while (child) {
1.726 + if (child->IsElement() &&
1.727 + DoesNotAffectDirectionOfAncestors(child->AsElement())) {
1.728 + child = child->GetNextNonChildNode(aElement);
1.729 + continue;
1.730 + }
1.731 +
1.732 + MOZ_ASSERT(!aElement->AncestorHasDirAuto() ||
1.733 + child->AncestorHasDirAuto(),
1.734 + "AncestorHasDirAuto set on node but not its children");
1.735 + child->SetAncestorHasDirAuto();
1.736 + child = child->GetNextNode(aElement);
1.737 + }
1.738 + }
1.739 + }
1.740 +
1.741 + nsINode* textNode = WalkDescendantsSetDirectionFromText(aElement, aNotify);
1.742 + if (textNode) {
1.743 + nsTextNodeDirectionalityMap::AddEntryToMap(textNode, aElement);
1.744 + }
1.745 +}
1.746 +
1.747 +void
1.748 +WalkDescendantsClearAncestorDirAuto(Element* aElement)
1.749 +{
1.750 + nsIContent* child = aElement->GetFirstChild();
1.751 + while (child) {
1.752 + if (child->HasDirAuto()) {
1.753 + child = child->GetNextNonChildNode(aElement);
1.754 + continue;
1.755 + }
1.756 +
1.757 + child->ClearAncestorHasDirAuto();
1.758 + child = child->GetNextNode(aElement);
1.759 + }
1.760 +}
1.761 +
1.762 +void SetAncestorDirectionIfAuto(nsINode* aTextNode, Directionality aDir,
1.763 + bool aNotify = true)
1.764 +{
1.765 + MOZ_ASSERT(aTextNode->NodeType() == nsIDOMNode::TEXT_NODE,
1.766 + "Must be a text node");
1.767 +
1.768 + Element* parent = aTextNode->GetParentElement();
1.769 + while (parent && parent->NodeOrAncestorHasDirAuto()) {
1.770 + if (DoesNotParticipateInAutoDirection(parent) || parent->HasFixedDir()) {
1.771 + break;
1.772 + }
1.773 +
1.774 + if (parent->HasDirAuto()) {
1.775 + bool resetDirection = false;
1.776 + nsINode* directionWasSetByTextNode =
1.777 + static_cast<nsINode*>(parent->GetProperty(nsGkAtoms::dirAutoSetBy));
1.778 +
1.779 + if (!parent->HasDirAutoSet()) {
1.780 + // Fast path if parent's direction is not yet set by any descendant
1.781 + MOZ_ASSERT(!directionWasSetByTextNode,
1.782 + "dirAutoSetBy property should be null");
1.783 + resetDirection = true;
1.784 + } else {
1.785 + // If parent's direction is already set, we need to know if
1.786 + // aTextNode is before or after the text node that had set it.
1.787 + // We will walk parent's descendants in tree order starting from
1.788 + // aTextNode to optimize for the most common case where text nodes are
1.789 + // being appended to tree.
1.790 + if (!directionWasSetByTextNode) {
1.791 + resetDirection = true;
1.792 + } else if (directionWasSetByTextNode != aTextNode) {
1.793 + nsIContent* child = aTextNode->GetNextNode(parent);
1.794 + while (child) {
1.795 + if (child->IsElement() &&
1.796 + DoesNotAffectDirectionOfAncestors(child->AsElement())) {
1.797 + child = child->GetNextNonChildNode(parent);
1.798 + continue;
1.799 + }
1.800 +
1.801 + if (child == directionWasSetByTextNode) {
1.802 + // we found the node that set the element's direction after our
1.803 + // text node, so we need to reset the direction
1.804 + resetDirection = true;
1.805 + break;
1.806 + }
1.807 +
1.808 + child = child->GetNextNode(parent);
1.809 + }
1.810 + }
1.811 + }
1.812 +
1.813 + if (resetDirection) {
1.814 + if (directionWasSetByTextNode) {
1.815 + nsTextNodeDirectionalityMap::RemoveElementFromMap(
1.816 + directionWasSetByTextNode, parent
1.817 + );
1.818 + }
1.819 + parent->SetDirectionality(aDir, aNotify);
1.820 + nsTextNodeDirectionalityMap::AddEntryToMap(aTextNode, parent);
1.821 + SetDirectionalityOnDescendants(parent, aDir, aNotify);
1.822 + }
1.823 +
1.824 + // Since we found an element with dir=auto, we can stop walking the
1.825 + // parent chain: none of its ancestors will have their direction set by
1.826 + // any of its descendants.
1.827 + return;
1.828 + }
1.829 + parent = parent->GetParentElement();
1.830 + }
1.831 +}
1.832 +
1.833 +bool
1.834 +TextNodeWillChangeDirection(nsIContent* aTextNode, Directionality* aOldDir,
1.835 + uint32_t aOffset)
1.836 +{
1.837 + if (!NodeAffectsDirAutoAncestor(aTextNode)) {
1.838 + nsTextNodeDirectionalityMap::EnsureMapIsClearFor(aTextNode);
1.839 + return false;
1.840 + }
1.841 +
1.842 + uint32_t firstStrong;
1.843 + *aOldDir = GetDirectionFromText(aTextNode->GetText(), &firstStrong);
1.844 + return (aOffset <= firstStrong);
1.845 +}
1.846 +
1.847 +void
1.848 +TextNodeChangedDirection(nsIContent* aTextNode, Directionality aOldDir,
1.849 + bool aNotify)
1.850 +{
1.851 + Directionality newDir = GetDirectionFromText(aTextNode->GetText());
1.852 + if (newDir == eDir_NotSet) {
1.853 + if (aOldDir != eDir_NotSet && aTextNode->HasTextNodeDirectionalityMap()) {
1.854 + // This node used to have a strong directional character but no
1.855 + // longer does. ResetTextNodeDirection() will re-resolve the
1.856 + // directionality of any elements whose directionality was
1.857 + // determined by this node.
1.858 + nsTextNodeDirectionalityMap::ResetTextNodeDirection(aTextNode);
1.859 + }
1.860 + } else {
1.861 + // This node has a strong directional character. If it has a
1.862 + // TextNodeDirectionalityMap property, it already determines the
1.863 + // directionality of some element(s), so call UpdateTextNodeDirection to
1.864 + // reresolve their directionality. Otherwise call
1.865 + // SetAncestorDirectionIfAuto to find ancestor elements which should
1.866 + // have their directionality determined by this node.
1.867 + if (aTextNode->HasTextNodeDirectionalityMap()) {
1.868 + nsTextNodeDirectionalityMap::UpdateTextNodeDirection(aTextNode, newDir);
1.869 + } else {
1.870 + SetAncestorDirectionIfAuto(aTextNode, newDir, aNotify);
1.871 + }
1.872 + }
1.873 +}
1.874 +
1.875 +void
1.876 +SetDirectionFromNewTextNode(nsIContent* aTextNode)
1.877 +{
1.878 + if (!NodeAffectsDirAutoAncestor(aTextNode)) {
1.879 + return;
1.880 + }
1.881 +
1.882 + Element* parent = aTextNode->GetParentElement();
1.883 + if (parent && parent->NodeOrAncestorHasDirAuto()) {
1.884 + aTextNode->SetAncestorHasDirAuto();
1.885 + }
1.886 +
1.887 + Directionality dir = GetDirectionFromText(aTextNode->GetText());
1.888 + if (dir != eDir_NotSet) {
1.889 + SetAncestorDirectionIfAuto(aTextNode, dir);
1.890 + }
1.891 +}
1.892 +
1.893 +void
1.894 +ResetDirectionSetByTextNode(nsTextNode* aTextNode, bool aNullParent)
1.895 +{
1.896 + if (!NodeAffectsDirAutoAncestor(aTextNode)) {
1.897 + nsTextNodeDirectionalityMap::EnsureMapIsClearFor(aTextNode);
1.898 + return;
1.899 + }
1.900 +
1.901 + Directionality dir = GetDirectionFromText(aTextNode->GetText());
1.902 + if (dir != eDir_NotSet && aTextNode->HasTextNodeDirectionalityMap()) {
1.903 + if (aNullParent) {
1.904 + nsTextNodeDirectionalityMap::ClearTextNodeDirection(aTextNode);
1.905 + } else {
1.906 + nsTextNodeDirectionalityMap::ResetTextNodeDirection(aTextNode);
1.907 + }
1.908 + }
1.909 +}
1.910 +
1.911 +void
1.912 +SetDirectionalityFromValue(Element* aElement, const nsAString& value,
1.913 + bool aNotify)
1.914 +{
1.915 + Directionality dir = GetDirectionFromText(PromiseFlatString(value).get(),
1.916 + value.Length());
1.917 + if (dir == eDir_NotSet) {
1.918 + dir = eDir_LTR;
1.919 + }
1.920 +
1.921 + aElement->SetDirectionality(dir, aNotify);
1.922 +}
1.923 +
1.924 +void
1.925 +OnSetDirAttr(Element* aElement, const nsAttrValue* aNewValue,
1.926 + bool hadValidDir, bool hadDirAuto, bool aNotify)
1.927 +{
1.928 + if (aElement->IsHTML(nsGkAtoms::input)) {
1.929 + return;
1.930 + }
1.931 +
1.932 + if (aElement->AncestorHasDirAuto()) {
1.933 + if (!hadValidDir) {
1.934 + // The element is a descendant of an element with dir = auto, is
1.935 + // having its dir attribute set, and previously didn't have a valid dir
1.936 + // attribute.
1.937 + // Check whether any of its text node descendants determine the
1.938 + // direction of any of its ancestors, and redetermine their direction
1.939 + WalkDescendantsResetAutoDirection(aElement);
1.940 + } else if (!aElement->HasValidDir()) {
1.941 + // The element is a descendant of an element with dir = auto and is
1.942 + // having its dir attribute removed or set to an invalid value.
1.943 + // Reset the direction of any of its ancestors whose direction is
1.944 + // determined by a text node descendant
1.945 + WalkAncestorsResetAutoDirection(aElement, aNotify);
1.946 + }
1.947 + } else if (hadDirAuto && !aElement->HasDirAuto()) {
1.948 + // The element isn't a descendant of an element with dir = auto, and is
1.949 + // having its dir attribute set to something other than auto.
1.950 + // Walk the descendant tree and clear the AncestorHasDirAuto flag.
1.951 + //
1.952 + // N.B: For elements other than <bdi> it would be enough to test that the
1.953 + // current value of dir was "auto" in BeforeSetAttr to know that we
1.954 + // were unsetting dir="auto". For <bdi> things are more complicated,
1.955 + // since it behaves like dir="auto" whenever the dir attribute is
1.956 + // empty or invalid, so we would have to check whether the old value
1.957 + // was not either "ltr" or "rtl", and the new value was either "ltr"
1.958 + // or "rtl". Element::HasDirAuto() encapsulates all that, so doing it
1.959 + // here is simpler.
1.960 + WalkDescendantsClearAncestorDirAuto(aElement);
1.961 + }
1.962 +
1.963 + if (aElement->HasDirAuto()) {
1.964 + WalkDescendantsSetDirAuto(aElement, aNotify);
1.965 + } else {
1.966 + if (aElement->HasDirAutoSet()) {
1.967 + nsINode* setByNode =
1.968 + static_cast<nsINode*>(aElement->GetProperty(nsGkAtoms::dirAutoSetBy));
1.969 + nsTextNodeDirectionalityMap::RemoveElementFromMap(setByNode, aElement);
1.970 + }
1.971 + SetDirectionalityOnDescendants(aElement,
1.972 + RecomputeDirectionality(aElement, aNotify),
1.973 + aNotify);
1.974 + }
1.975 +}
1.976 +
1.977 +void
1.978 +SetDirOnBind(mozilla::dom::Element* aElement, nsIContent* aParent)
1.979 +{
1.980 + // Set the AncestorHasDirAuto flag, unless this element shouldn't affect
1.981 + // ancestors that have dir=auto
1.982 + if (!DoesNotParticipateInAutoDirection(aElement) &&
1.983 + !aElement->IsHTML(nsGkAtoms::bdi) &&
1.984 + aParent && aParent->NodeOrAncestorHasDirAuto()) {
1.985 + aElement->SetAncestorHasDirAuto();
1.986 +
1.987 + nsIContent* child = aElement->GetFirstChild();
1.988 + if (child) {
1.989 + // If we are binding an element to the tree that already has descendants,
1.990 + // and the parent has NodeHasDirAuto or NodeAncestorHasDirAuto, we need
1.991 + // to set NodeAncestorHasDirAuto on all the element's descendants, except
1.992 + // for nodes that don't affect the direction of their ancestors.
1.993 + do {
1.994 + if (child->IsElement() &&
1.995 + DoesNotAffectDirectionOfAncestors(child->AsElement())) {
1.996 + child = child->GetNextNonChildNode(aElement);
1.997 + continue;
1.998 + }
1.999 +
1.1000 + child->SetAncestorHasDirAuto();
1.1001 + child = child->GetNextNode(aElement);
1.1002 + } while (child);
1.1003 +
1.1004 + // We may also need to reset the direction of an ancestor with dir=auto
1.1005 + WalkAncestorsResetAutoDirection(aElement, true);
1.1006 + }
1.1007 + }
1.1008 +
1.1009 + if (!aElement->HasDirAuto()) {
1.1010 + // if the element doesn't have dir=auto, set its own directionality from
1.1011 + // the dir attribute or by inheriting from its ancestors.
1.1012 + RecomputeDirectionality(aElement, false);
1.1013 + }
1.1014 +}
1.1015 +
1.1016 +void ResetDir(mozilla::dom::Element* aElement)
1.1017 +{
1.1018 + if (aElement->HasDirAutoSet()) {
1.1019 + nsINode* setByNode =
1.1020 + static_cast<nsINode*>(aElement->GetProperty(nsGkAtoms::dirAutoSetBy));
1.1021 + nsTextNodeDirectionalityMap::RemoveElementFromMap(setByNode, aElement);
1.1022 + }
1.1023 +
1.1024 + if (!aElement->HasDirAuto()) {
1.1025 + RecomputeDirectionality(aElement, false);
1.1026 + }
1.1027 +}
1.1028 +
1.1029 +} // end namespace mozilla
1.1030 +
