dom/xslt/xpath/txMozillaXPathTreeWalker.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 #include "txXPathTreeWalker.h"
   7 #include "nsAtom.h"
   8 #include "nsINode.h"
   9 #include "nsPrintfCString.h"
  10 #include "nsReadableUtils.h"
  11 #include "nsString.h"
  12 #include "nsTextFragment.h"
  13 #include "txXMLUtils.h"
  14 #include "txLog.h"
  15 #include "nsUnicharUtils.h"
  16 #include "nsAttrName.h"
  17 #include "nsNameSpaceManager.h"
  18 #include "nsTArray.h"
  19 #include "mozilla/Maybe.h"
  20 #include "mozilla/dom/Attr.h"
  21 #include "mozilla/dom/CharacterData.h"
  22 #include "mozilla/dom/Element.h"
  23 #include <stdint.h>
  24 #include <algorithm>
  25
  26 using namespace mozilla::dom;
  27 using mozilla::Maybe;
  28
  29 txXPathTreeWalker::txXPathTreeWalker(const txXPathTreeWalker& aOther) = default;
  30
  31 txXPathTreeWalker::txXPathTreeWalker(const txXPathNode& aNode)
  32     : mPosition(aNode) {}
  33
  34 void txXPathTreeWalker::moveToRoot() {
  35   if (mPosition.isDocument()) {
  36     return;
  37   }
  38
  39   Document* root = mPosition.mNode->GetUncomposedDoc();
  40   if (root) {
  41     mPosition.mIndex = txXPathNode::eDocument;
  42     mPosition.mNode = root;
  43   } else {
  44     nsINode* rootNode = mPosition.Root();
  45
  46     NS_ASSERTION(rootNode->IsContent(), "root of subtree wasn't an nsIContent");
  47
  48     mPosition.mIndex = txXPathNode::eContent;
  49     mPosition.mNode = rootNode;
  50   }
  51 }
  52
  53 bool txXPathTreeWalker::moveToElementById(const nsAString& aID) {
  54   if (aID.IsEmpty()) {
  55     return false;
  56   }
  57
  58   Document* doc = mPosition.mNode->GetUncomposedDoc();
  59
  60   nsCOMPtr<nsIContent> content;
  61   if (doc) {
  62     content = doc->GetElementById(aID);
  63   } else {
  64     // We're in a disconnected subtree, search only that subtree.
  65     nsINode* rootNode = mPosition.Root();
  66
  67     NS_ASSERTION(rootNode->IsContent(), "root of subtree wasn't an nsIContent");
  68
  69     content =
  70         nsContentUtils::MatchElementId(static_cast<nsIContent*>(rootNode), aID);
  71   }
  72
  73   if (!content) {
  74     return false;
  75   }
  76
  77   mPosition.mIndex = txXPathNode::eContent;
  78   mPosition.mNode = content;
  79
  80   return true;
  81 }
  82
  83 bool txXPathTreeWalker::moveToFirstAttribute() {
  84   if (!mPosition.isContent()) {
  85     return false;
  86   }
  87
  88   return moveToValidAttribute(0);
  89 }
  90
  91 bool txXPathTreeWalker::moveToNextAttribute() {
  92   // XXX an assertion should be enough here with the current code
  93   if (!mPosition.isAttribute()) {
  94     return false;
  95   }
  96
  97   return moveToValidAttribute(mPosition.mIndex + 1);
  98 }
  99
 100 bool txXPathTreeWalker::moveToValidAttribute(uint32_t aStartIndex) {
 101   NS_ASSERTION(!mPosition.isDocument(), "documents doesn't have attrs");
 102
 103   if (!mPosition.Content()->IsElement()) {
 104     return false;
 105   }
 106
 107   Element* element = mPosition.Content()->AsElement();
 108   uint32_t total = element->GetAttrCount();
 109   if (aStartIndex >= total) {
 110     return false;
 111   }
 112
 113   uint32_t index;
 114   for (index = aStartIndex; index < total; ++index) {
 115     const nsAttrName* name = element->GetAttrNameAt(index);
 116
 117     // We need to ignore XMLNS attributes.
 118     if (name->NamespaceID() != kNameSpaceID_XMLNS) {
 119       mPosition.mIndex = index;
 120
 121       return true;
 122     }
 123   }
 124   return false;
 125 }
 126
 127 bool txXPathTreeWalker::moveToNamedAttribute(nsAtom* aLocalName,
 128                                              int32_t aNSID) {
 129   if (!mPosition.isContent() || !mPosition.Content()->IsElement()) {
 130     return false;
 131   }
 132
 133   Element* element = mPosition.Content()->AsElement();
 134
 135   const nsAttrName* name;
 136   uint32_t i;
 137   for (i = 0; (name = element->GetAttrNameAt(i)); ++i) {
 138     if (name->Equals(aLocalName, aNSID)) {
 139       mPosition.mIndex = i;
 140
 141       return true;
 142     }
 143   }
 144   return false;
 145 }
 146
 147 bool txXPathTreeWalker::moveToFirstChild() {
 148   if (mPosition.isAttribute()) {
 149     return false;
 150   }
 151
 152   nsIContent* child = mPosition.mNode->GetFirstChild();
 153   if (!child) {
 154     return false;
 155   }
 156   mPosition.mIndex = txXPathNode::eContent;
 157   mPosition.mNode = child;
 158
 159   return true;
 160 }
 161
 162 bool txXPathTreeWalker::moveToLastChild() {
 163   if (mPosition.isAttribute()) {
 164     return false;
 165   }
 166
 167   nsIContent* child = mPosition.mNode->GetLastChild();
 168   if (!child) {
 169     return false;
 170   }
 171
 172   mPosition.mIndex = txXPathNode::eContent;
 173   mPosition.mNode = child;
 174
 175   return true;
 176 }
 177
 178 bool txXPathTreeWalker::moveToNextSibling() {
 179   if (!mPosition.isContent()) {
 180     return false;
 181   }
 182
 183   nsINode* sibling = mPosition.mNode->GetNextSibling();
 184   if (!sibling) {
 185     return false;
 186   }
 187
 188   mPosition.mNode = sibling;
 189
 190   return true;
 191 }
 192
 193 bool txXPathTreeWalker::moveToPreviousSibling() {
 194   if (!mPosition.isContent()) {
 195     return false;
 196   }
 197
 198   nsINode* sibling = mPosition.mNode->GetPreviousSibling();
 199   if (!sibling) {
 200     return false;
 201   }
 202
 203   mPosition.mNode = sibling;
 204
 205   return true;
 206 }
 207
 208 bool txXPathTreeWalker::moveToParent() {
 209   if (mPosition.isDocument()) {
 210     return false;
 211   }
 212
 213   if (mPosition.isAttribute()) {
 214     mPosition.mIndex = txXPathNode::eContent;
 215
 216     return true;
 217   }
 218
 219   nsINode* parent = mPosition.mNode->GetParentNode();
 220   if (!parent) {
 221     return false;
 222   }
 223
 224   mPosition.mIndex = mPosition.mNode->GetParent() ? txXPathNode::eContent
 225                                                   : txXPathNode::eDocument;
 226   mPosition.mNode = parent;
 227
 228   return true;
 229 }
 230
 231 txXPathNode::txXPathNode(const txXPathNode& aNode)
 232     : mNode(aNode.mNode),
 233       mRefCountRoot(aNode.mRefCountRoot),
 234       mIndex(aNode.mIndex) {
 235   MOZ_COUNT_CTOR(txXPathNode);
 236   if (mRefCountRoot) {
 237     NS_ADDREF(Root());
 238   }
 239 }
 240
 241 txXPathNode::~txXPathNode() {
 242   MOZ_COUNT_DTOR(txXPathNode);
 243   if (mRefCountRoot) {
 244     nsINode* root = Root();
 245     NS_RELEASE(root);
 246   }
 247 }
 248
 249 /* static */
 250 bool txXPathNodeUtils::getAttr(const txXPathNode& aNode, nsAtom* aLocalName,
 251                                int32_t aNSID, nsAString& aValue) {
 252   if (aNode.isDocument() || aNode.isAttribute() ||
 253       !aNode.Content()->IsElement()) {
 254     return false;
 255   }
 256
 257   return aNode.Content()->AsElement()->GetAttr(aNSID, aLocalName, aValue);
 258 }
 259
 260 /* static */
 261 already_AddRefed<nsAtom> txXPathNodeUtils::getLocalName(
 262     const txXPathNode& aNode) {
 263   if (aNode.isDocument()) {
 264     return nullptr;
 265   }
 266
 267   if (aNode.isContent()) {
 268     if (aNode.mNode->IsElement()) {
 269       RefPtr<nsAtom> localName = aNode.Content()->NodeInfo()->NameAtom();
 270       return localName.forget();
 271     }
 272
 273     if (aNode.mNode->IsProcessingInstruction()) {
 274       return NS_Atomize(aNode.mNode->NodeName());
 275     }
 276
 277     return nullptr;
 278   }
 279
 280   // This is an attribute node, so we necessarily come from an element.
 281   RefPtr<nsAtom> localName =
 282       aNode.Content()->AsElement()->GetAttrNameAt(aNode.mIndex)->LocalName();
 283
 284   return localName.forget();
 285 }
 286
 287 nsAtom* txXPathNodeUtils::getPrefix(const txXPathNode& aNode) {
 288   if (aNode.isDocument()) {
 289     return nullptr;
 290   }
 291
 292   if (aNode.isContent()) {
 293     // All other nsIContent node types but elements have a null prefix
 294     // which is what we want here.
 295     return aNode.Content()->NodeInfo()->GetPrefixAtom();
 296   }
 297
 298   return aNode.Content()->AsElement()->GetAttrNameAt(aNode.mIndex)->GetPrefix();
 299 }
 300
 301 /* static */
 302 void txXPathNodeUtils::getLocalName(const txXPathNode& aNode,
 303                                     nsAString& aLocalName) {
 304   if (aNode.isDocument()) {
 305     aLocalName.Truncate();
 306
 307     return;
 308   }
 309
 310   if (aNode.isContent()) {
 311     if (aNode.mNode->IsElement()) {
 312       mozilla::dom::NodeInfo* nodeInfo = aNode.Content()->NodeInfo();
 313       nodeInfo->GetName(aLocalName);
 314       return;
 315     }
 316
 317     if (aNode.mNode->IsProcessingInstruction()) {
 318       // PIs don't have a nodeinfo but do have a name
 319       // XXXbz Not actually true, but this function looks like it wants
 320       // different things from elements and PIs for "local name"...
 321       aLocalName = aNode.mNode->NodeName();
 322       return;
 323     }
 324
 325     aLocalName.Truncate();
 326
 327     return;
 328   }
 329
 330   aNode.Content()
 331       ->AsElement()
 332       ->GetAttrNameAt(aNode.mIndex)
 333       ->LocalName()
 334       ->ToString(aLocalName);
 335
 336   // Check for html
 337   if (aNode.Content()->NodeInfo()->NamespaceEquals(kNameSpaceID_None) &&
 338       aNode.Content()->IsHTMLElement()) {
 339     nsContentUtils::ASCIIToUpper(aLocalName);
 340   }
 341 }
 342
 343 /* static */
 344 void txXPathNodeUtils::getNodeName(const txXPathNode& aNode, nsAString& aName) {
 345   if (aNode.isDocument()) {
 346     aName.Truncate();
 347
 348     return;
 349   }
 350
 351   if (aNode.isContent()) {
 352     // Elements and PIs have a name
 353     if (aNode.mNode->IsElement() ||
 354         aNode.mNode->NodeType() == nsINode::PROCESSING_INSTRUCTION_NODE) {
 355       aName = aNode.Content()->NodeName();
 356       return;
 357     }
 358
 359     aName.Truncate();
 360
 361     return;
 362   }
 363
 364   aNode.Content()
 365       ->AsElement()
 366       ->GetAttrNameAt(aNode.mIndex)
 367       ->GetQualifiedName(aName);
 368 }
 369
 370 /* static */
 371 int32_t txXPathNodeUtils::getNamespaceID(const txXPathNode& aNode) {
 372   if (aNode.isDocument()) {
 373     return kNameSpaceID_None;
 374   }
 375
 376   if (aNode.isContent()) {
 377     return aNode.Content()->GetNameSpaceID();
 378   }
 379
 380   return aNode.Content()
 381       ->AsElement()
 382       ->GetAttrNameAt(aNode.mIndex)
 383       ->NamespaceID();
 384 }
 385
 386 /* static */
 387 void txXPathNodeUtils::getNamespaceURI(const txXPathNode& aNode,
 388                                        nsAString& aURI) {
 389   nsNameSpaceManager::GetInstance()->GetNameSpaceURI(getNamespaceID(aNode),
 390                                                      aURI);
 391 }
 392
 393 /* static */
 394 uint16_t txXPathNodeUtils::getNodeType(const txXPathNode& aNode) {
 395   if (aNode.isDocument()) {
 396     return txXPathNodeType::DOCUMENT_NODE;
 397   }
 398
 399   if (aNode.isContent()) {
 400     return aNode.mNode->NodeType();
 401   }
 402
 403   return txXPathNodeType::ATTRIBUTE_NODE;
 404 }
 405
 406 /* static */
 407 void txXPathNodeUtils::appendNodeValue(const txXPathNode& aNode,
 408                                        nsAString& aResult) {
 409   if (aNode.isAttribute()) {
 410     const nsAttrName* name =
 411         aNode.Content()->AsElement()->GetAttrNameAt(aNode.mIndex);
 412
 413     if (aResult.IsEmpty()) {
 414       aNode.Content()->AsElement()->GetAttr(name->NamespaceID(),
 415                                             name->LocalName(), aResult);
 416     } else {
 417       nsAutoString result;
 418       aNode.Content()->AsElement()->GetAttr(name->NamespaceID(),
 419                                             name->LocalName(), result);
 420       aResult.Append(result);
 421     }
 422
 423     return;
 424   }
 425
 426   if (aNode.isDocument() || aNode.mNode->IsElement() ||
 427       aNode.mNode->IsDocumentFragment()) {
 428     nsContentUtils::AppendNodeTextContent(aNode.mNode, true, aResult,
 429                                           mozilla::fallible);
 430
 431     return;
 432   }
 433
 434   MOZ_ASSERT(aNode.mNode->IsCharacterData());
 435   static_cast<CharacterData*>(aNode.Content())->AppendTextTo(aResult);
 436 }
 437
 438 /* static */
 439 bool txXPathNodeUtils::isWhitespace(const txXPathNode& aNode) {
 440   NS_ASSERTION(aNode.isContent() && isText(aNode), "Wrong type!");
 441
 442   return aNode.Content()->TextIsOnlyWhitespace();
 443 }
 444
 445 /* static */
 446 txXPathNode* txXPathNodeUtils::getOwnerDocument(const txXPathNode& aNode) {
 447   return new txXPathNode(aNode.mNode->OwnerDoc());
 448 }
 449
 450 const char gPrintfFmt[] = "id0x%" PRIxPTR;
 451 const char gPrintfFmtAttr[] = "id0x%" PRIxPTR "-%010i";
 452
 453 /* static */
 454 nsresult txXPathNodeUtils::getXSLTId(const txXPathNode& aNode,
 455                                      const txXPathNode& aBase,
 456                                      nsAString& aResult) {
 457   uintptr_t nodeid = ((uintptr_t)aNode.mNode) - ((uintptr_t)aBase.mNode);
 458   if (!aNode.isAttribute()) {
 459     CopyASCIItoUTF16(nsPrintfCString(gPrintfFmt, nodeid), aResult);
 460   } else {
 461     CopyASCIItoUTF16(nsPrintfCString(gPrintfFmtAttr, nodeid, aNode.mIndex),
 462                      aResult);
 463   }
 464
 465   return NS_OK;
 466 }
 467
 468 /* static */
 469 nsresult txXPathNodeUtils::getBaseURI(const txXPathNode& aNode,
 470                                       nsAString& aURI) {
 471   return aNode.mNode->GetBaseURI(aURI);
 472 }
 473
 474 /* static */
 475 int txXPathNodeUtils::comparePosition(const txXPathNode& aNode,
 476                                       const txXPathNode& aOtherNode) {
 477   // First check for equal nodes or attribute-nodes on the same element.
 478   if (aNode.mNode == aOtherNode.mNode) {
 479     if (aNode.mIndex == aOtherNode.mIndex) {
 480       return 0;
 481     }
 482
 483     NS_ASSERTION(!aNode.isDocument() && !aOtherNode.isDocument(),
 484                  "documents should always have a set index");
 485
 486     if (aNode.isContent() ||
 487         (!aOtherNode.isContent() && aNode.mIndex < aOtherNode.mIndex)) {
 488       return -1;
 489     }
 490
 491     return 1;
 492   }
 493
 494   // Get document for both nodes.
 495   Document* document = aNode.mNode->GetUncomposedDoc();
 496   Document* otherDocument = aOtherNode.mNode->GetUncomposedDoc();
 497
 498   // If the nodes have different current documents, compare the document
 499   // pointers.
 500   if (document != otherDocument) {
 501     return document < otherDocument ? -1 : 1;
 502   }
 503
 504   // Now either both nodes are in orphan trees, or they are both in the
 505   // same tree.
 506
 507   // Get parents up the tree.
 508   AutoTArray<nsINode*, 8> parents, otherParents;
 509   nsINode* node = aNode.mNode;
 510   nsINode* otherNode = aOtherNode.mNode;
 511   nsINode* parent;
 512   nsINode* otherParent;
 513   while (node && otherNode) {
 514     parent = node->GetParentNode();
 515     otherParent = otherNode->GetParentNode();
 516
 517     // Hopefully this is a common case.
 518     if (parent == otherParent) {
 519       if (!parent) {
 520         // Both node and otherNode are root nodes in respective orphan
 521         // tree.
 522         return node < otherNode ? -1 : 1;
 523       }
 524
 525       const Maybe<uint32_t> indexOfNode = parent->ComputeIndexOf(node);
 526       const Maybe<uint32_t> indexOfOtherNode =
 527           parent->ComputeIndexOf(otherNode);
 528       if (MOZ_LIKELY(indexOfNode.isSome() && indexOfOtherNode.isSome())) {
 529         return *indexOfNode < *indexOfOtherNode ? -1 : 1;
 530       }
 531       // XXX Keep the odd traditional behavior for now.
 532       return indexOfNode.isNothing() && indexOfOtherNode.isSome() ? -1 : 1;
 533     }
 534
 535     parents.AppendElement(node);
 536     otherParents.AppendElement(otherNode);
 537     node = parent;
 538     otherNode = otherParent;
 539   }
 540
 541   while (node) {
 542     parents.AppendElement(node);
 543     node = node->GetParentNode();
 544   }
 545   while (otherNode) {
 546     otherParents.AppendElement(otherNode);
 547     otherNode = otherNode->GetParentNode();
 548   }
 549
 550   // Walk back down along the parent-chains until we find where they split.
 551   int32_t total = parents.Length() - 1;
 552   int32_t otherTotal = otherParents.Length() - 1;
 553   NS_ASSERTION(total != otherTotal, "Can't have same number of parents");
 554
 555   int32_t lastIndex = std::min(total, otherTotal);
 556   int32_t i;
 557   parent = nullptr;
 558   for (i = 0; i <= lastIndex; ++i) {
 559     node = parents.ElementAt(total - i);
 560     otherNode = otherParents.ElementAt(otherTotal - i);
 561     if (node != otherNode) {
 562       if (!parent) {
 563         // The two nodes are in different orphan subtrees.
 564         NS_ASSERTION(i == 0, "this shouldn't happen");
 565         return node < otherNode ? -1 : 1;
 566       }
 567
 568       const Maybe<uint32_t> index = parent->ComputeIndexOf(node);
 569       const Maybe<uint32_t> otherIndex = parent->ComputeIndexOf(otherNode);
 570       if (MOZ_LIKELY(index.isSome() && otherIndex.isSome())) {
 571         NS_ASSERTION(*index != *otherIndex, "invalid index in comparePosition");
 572         return *index < *otherIndex ? -1 : 1;
 573       }
 574       NS_ASSERTION(false, "invalid index in comparePosition");
 575       // XXX Keep the odd traditional behavior for now.
 576       return index.isNothing() && otherIndex.isSome() ? -1 : 1;
 577     }
 578
 579     parent = node;
 580   }
 581
 582   // One node is a descendant of the other. The one with the shortest
 583   // parent-chain is first in the document.
 584   return total < otherTotal ? -1 : 1;
 585 }
 586
 587 /* static */
 588 txXPathNode* txXPathNativeNode::createXPathNode(nsIContent* aContent,
 589                                                 bool aKeepRootAlive) {
 590   nsINode* root = aKeepRootAlive ? txXPathNode::RootOf(aContent) : nullptr;
 591
 592   return new txXPathNode(aContent, txXPathNode::eContent, root);
 593 }
 594
 595 /* static */
 596 txXPathNode* txXPathNativeNode::createXPathNode(nsINode* aNode,
 597                                                 bool aKeepRootAlive) {
 598   uint16_t nodeType = aNode->NodeType();
 599   if (nodeType == nsINode::ATTRIBUTE_NODE) {
 600     auto* attr = static_cast<Attr*>(aNode);
 601
 602     NodeInfo* nodeInfo = attr->NodeInfo();
 603     Element* parent = attr->GetElement();
 604     if (!parent) {
 605       return nullptr;
 606     }
 607
 608     nsINode* root = aKeepRootAlive ? txXPathNode::RootOf(parent) : nullptr;
 609
 610     uint32_t i, total = parent->GetAttrCount();
 611     for (i = 0; i < total; ++i) {
 612       const nsAttrName* name = parent->GetAttrNameAt(i);
 613       if (nodeInfo->Equals(name->LocalName(), name->NamespaceID())) {
 614         return new txXPathNode(parent, i, root);
 615       }
 616     }
 617
 618     NS_ERROR("Couldn't find the attribute in its parent!");
 619
 620     return nullptr;
 621   }
 622
 623   uint32_t index;
 624   nsINode* root = aKeepRootAlive ? aNode : nullptr;
 625
 626   if (nodeType == nsINode::DOCUMENT_NODE) {
 627     index = txXPathNode::eDocument;
 628   } else {
 629     index = txXPathNode::eContent;
 630     if (root) {
 631       root = txXPathNode::RootOf(root);
 632     }
 633   }
 634
 635   return new txXPathNode(aNode, index, root);
 636 }
 637
 638 /* static */
 639 txXPathNode* txXPathNativeNode::createXPathNode(Document* aDocument) {
 640   return new txXPathNode(aDocument);
 641 }
 642
 643 /* static */
 644 nsINode* txXPathNativeNode::getNode(const txXPathNode& aNode) {
 645   if (!aNode.isAttribute()) {
 646     return aNode.mNode;
 647   }
 648
 649   const nsAttrName* name =
 650       aNode.Content()->AsElement()->GetAttrNameAt(aNode.mIndex);
 651
 652   nsAutoString namespaceURI;
 653   nsNameSpaceManager::GetInstance()->GetNameSpaceURI(name->NamespaceID(),
 654                                                      namespaceURI);
 655
 656   nsCOMPtr<Element> element = do_QueryInterface(aNode.mNode);
 657   nsDOMAttributeMap* map = element->Attributes();
 658   return map->GetNamedItemNS(namespaceURI,
 659                              nsDependentAtomString(name->LocalName()));
 660 }
 661
 662 /* static */
 663 nsIContent* txXPathNativeNode::getContent(const txXPathNode& aNode) {
 664   NS_ASSERTION(aNode.isContent(),
 665                "Only call getContent on nsIContent wrappers!");
 666   return aNode.Content();
 667 }
 668
 669 /* static */
 670 Document* txXPathNativeNode::getDocument(const txXPathNode& aNode) {
 671   NS_ASSERTION(aNode.isDocument(),
 672                "Only call getDocument on Document wrappers!");
 673   return aNode.Document();
 674 }