1 files changed, 240 insertions, 0 deletions
diff --git a/dom/xslt/xslt/txNodeSorter.cpp b/dom/xslt/xslt/txNodeSorter.cpp
new file mode 100644
index 0000000000..05a0d97957
--- /dev/null
+++ b/dom/xslt/xslt/txNodeSorter.cpp
@@ -0,0 +1,240 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "txNodeSorter.h"
+#include "txExecutionState.h"
+#include "txXPathResultComparator.h"
+#include "nsGkAtoms.h"
+#include "txNodeSetContext.h"
+#include "txExpr.h"
+#include "txStringUtils.h"
+#include "nsQuickSort.h"
+
+#include "mozilla/CheckedInt.h"
+#include "mozilla/UniquePtrExtensions.h"
+
+using mozilla::CheckedUint32;
+using mozilla::MakeUnique;
+using mozilla::MakeUniqueFallible;
+using mozilla::UniquePtr;
+
+/*
+ * Sorts Nodes as specified by the W3C XSLT 1.0 Recommendation
+ */
+
+txNodeSorter::txNodeSorter() : mNKeys(0) {}
+
+txNodeSorter::~txNodeSorter() {
+  txListIterator iter(&mSortKeys);
+  while (iter.hasNext()) {
+    SortKey* key = (SortKey*)iter.next();
+    delete key->mComparator;
+    delete key;
+  }
+}
+
+nsresult txNodeSorter::addSortElement(Expr* aSelectExpr, Expr* aLangExpr,
+                                      Expr* aDataTypeExpr, Expr* aOrderExpr,
+                                      Expr* aCaseOrderExpr,
+                                      txIEvalContext* aContext) {
+  UniquePtr<SortKey> key(new SortKey);
+  nsresult rv = NS_OK;
+
+  // Select
+  key->mExpr = aSelectExpr;
+
+  // Order
+  bool ascending = true;
+  if (aOrderExpr) {
+    nsAutoString attrValue;
+    rv = aOrderExpr->evaluateToString(aContext, attrValue);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    if (TX_StringEqualsAtom(attrValue, nsGkAtoms::descending)) {
+      ascending = false;
+    } else if (!TX_StringEqualsAtom(attrValue, nsGkAtoms::ascending)) {
+      // XXX ErrorReport: unknown value for order attribute
+      return NS_ERROR_XSLT_BAD_VALUE;
+    }
+  }
+
+  // Create comparator depending on datatype
+  nsAutoString dataType;
+  if (aDataTypeExpr) {
+    rv = aDataTypeExpr->evaluateToString(aContext, dataType);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  if (!aDataTypeExpr || TX_StringEqualsAtom(dataType, nsGkAtoms::text)) {
+    // Text comparator
+
+    // Language
+    nsAutoString lang;
+    if (aLangExpr) {
+      rv = aLangExpr->evaluateToString(aContext, lang);
+      NS_ENSURE_SUCCESS(rv, rv);
+    }
+
+    // Case-order
+    bool upperFirst = false;
+    if (aCaseOrderExpr) {
+      nsAutoString attrValue;
+
+      rv = aCaseOrderExpr->evaluateToString(aContext, attrValue);
+      NS_ENSURE_SUCCESS(rv, rv);
+
+      if (TX_StringEqualsAtom(attrValue, nsGkAtoms::upperFirst)) {
+        upperFirst = true;
+      } else if (!TX_StringEqualsAtom(attrValue, nsGkAtoms::lowerFirst)) {
+        // XXX ErrorReport: unknown value for case-order attribute
+        return NS_ERROR_XSLT_BAD_VALUE;
+      }
+    }
+
+    key->mComparator =
+        new txResultStringComparator(ascending, upperFirst, lang);
+  } else if (TX_StringEqualsAtom(dataType, nsGkAtoms::number)) {
+    // Number comparator
+    key->mComparator = new txResultNumberComparator(ascending);
+  } else {
+    // XXX ErrorReport: unknown data-type
+    return NS_ERROR_XSLT_BAD_VALUE;
+  }
+
+  // mSortKeys owns key now.
+  mSortKeys.add(key.release());
+  mNKeys++;
+
+  return NS_OK;
+}
+
+nsresult txNodeSorter::sortNodeSet(txNodeSet* aNodes, txExecutionState* aEs,
+                                   txNodeSet** aResult) {
+  if (mNKeys == 0 || aNodes->isEmpty()) {
+    RefPtr<txNodeSet> ref(aNodes);
+    ref.forget(aResult);
+
+    return NS_OK;
+  }
+
+  *aResult = nullptr;
+
+  RefPtr<txNodeSet> sortedNodes;
+  nsresult rv = aEs->recycler()->getNodeSet(getter_AddRefs(sortedNodes));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // Create and set up memoryblock for sort-values and indexarray
+  CheckedUint32 len = aNodes->size();
+  CheckedUint32 numSortValues = len * mNKeys;
+  CheckedUint32 sortValuesSize = numSortValues * sizeof(txObject*);
+  if (!sortValuesSize.isValid()) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  auto indexes = MakeUniqueFallible<uint32_t[]>(len.value());
+  auto sortValues = MakeUniqueFallible<txObject*[]>(numSortValues.value());
+  if (!indexes || !sortValues) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  uint32_t i;
+  for (i = 0; i < len.value(); ++i) {
+    indexes[i] = i;
+  }
+  memset(sortValues.get(), 0, sortValuesSize.value());
+
+  auto nodeSetContext = MakeUnique<txNodeSetContext>(aNodes, aEs);
+
+  // Sort the indexarray
+  SortData sortData;
+  sortData.mNodeSorter = this;
+  sortData.mContext = nodeSetContext.get();
+  sortData.mSortValues = sortValues.get();
+  sortData.mRv = NS_OK;
+
+  aEs->pushEvalContext(nodeSetContext.release());
+
+  NS_QuickSort(indexes.get(), len.value(), sizeof(uint32_t), compareNodes,
+               &sortData);
+
+  // Delete these here so we don't have to deal with them at every possible
+  // failurepoint
+  for (i = 0; i < numSortValues.value(); ++i) {
+    delete sortValues[i];
+  }
+
+  if (NS_FAILED(sortData.mRv)) {
+    // The txExecutionState owns the evalcontext so no need to handle it
+    return sortData.mRv;
+  }
+
+  // Insert nodes in sorted order in new nodeset
+  for (i = 0; i < len.value(); ++i) {
+    rv = sortedNodes->append(aNodes->get(indexes[i]));
+    if (NS_FAILED(rv)) {
+      // The txExecutionState owns the evalcontext so no need to handle it
+      return rv;
+    }
+  }
+
+  delete aEs->popEvalContext();
+
+  sortedNodes.forget(aResult);
+
+  return NS_OK;
+}
+
+// static
+int txNodeSorter::compareNodes(const void* aIndexA, const void* aIndexB,
+                               void* aSortData) {
+  SortData* sortData = static_cast<SortData*>(aSortData);
+  NS_ENSURE_SUCCESS(sortData->mRv, -1);
+
+  txListIterator iter(&sortData->mNodeSorter->mSortKeys);
+  uint32_t indexA = *static_cast<const uint32_t*>(aIndexA);
+  uint32_t indexB = *static_cast<const uint32_t*>(aIndexB);
+  txObject** sortValuesA =
+      sortData->mSortValues + indexA * sortData->mNodeSorter->mNKeys;
+  txObject** sortValuesB =
+      sortData->mSortValues + indexB * sortData->mNodeSorter->mNKeys;
+
+  unsigned int i;
+  // Step through each key until a difference is found
+  for (i = 0; i < sortData->mNodeSorter->mNKeys; ++i) {
+    SortKey* key = (SortKey*)iter.next();
+    // Lazy create sort values
+    if (!sortValuesA[i] &&
+        !calcSortValue(sortValuesA[i], key, sortData, indexA)) {
+      return -1;
+    }
+    if (!sortValuesB[i] &&
+        !calcSortValue(sortValuesB[i], key, sortData, indexB)) {
+      return -1;
+    }
+
+    // Compare node values
+    int compRes =
+        key->mComparator->compareValues(sortValuesA[i], sortValuesB[i]);
+    if (compRes != 0) return compRes;
+  }
+  // All keys have the same value for these nodes
+
+  return indexA - indexB;
+}
+
+// static
+bool txNodeSorter::calcSortValue(txObject*& aSortValue, SortKey* aKey,
+                                 SortData* aSortData, uint32_t aNodeIndex) {
+  aSortData->mContext->setPosition(aNodeIndex + 1);  // position is 1-based
+
+  nsresult rv = aKey->mComparator->createSortableValue(
+      aKey->mExpr, aSortData->mContext, aSortValue);
+  if (NS_FAILED(rv)) {
+    aSortData->mRv = rv;
+    return false;
+  }
+
+  return true;
+}