/*
 * Copyright (C) 2007, 2008, 2009 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1.  Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 * 2.  Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
 *     its contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "third_party/blink/renderer/core/xml/xslt_unicode_sort.h"

#include <libxslt/templates.h>
#include <libxslt/xsltutils.h>
#include <memory>
#include "third_party/blink/renderer/platform/wtf/text/wtf_string.h"
#include "third_party/icu/source/common/unicode/uloc.h"
#include "third_party/icu/source/i18n/unicode/ucol.h"

namespace blink {

namespace {

class UCollatorDeleter {
 public:
  void operator()(UCollator* collator) { ucol_close(collator); }
};

struct UCollatorHolder {
  std::unique_ptr<UCollator, UCollatorDeleter> collator;
  char equivalent_locale[ULOC_FULLNAME_CAPACITY];
  bool lower_first = false;

  operator UCollator*() const { return collator.get(); }
};

}  // namespace

inline const xmlChar* ToXMLChar(const char* string) {
  return reinterpret_cast<const xmlChar*>(string);
}

// Based on default implementation from libxslt 1.1.22 and xsltICUSort.c
// example.
void XsltUnicodeSortFunction(xsltTransformContextPtr ctxt,
                             xmlNodePtr* sorts,
                             int nbsorts) {
#ifdef XSLT_REFACTORED
  xsltStyleItemSortPtr comp;
#else
  xsltStylePreCompPtr comp;
#endif
  xmlXPathObjectPtr* results_tab[XSLT_MAX_SORT];
  xmlXPathObjectPtr* results = nullptr;
  xmlNodeSetPtr list = nullptr;
  int depth;
  xmlNodePtr node;
  int tempstype[XSLT_MAX_SORT], temporder[XSLT_MAX_SORT];

  if (!ctxt || !sorts || nbsorts <= 0 || nbsorts >= XSLT_MAX_SORT)
    return;
  if (!sorts[0])
    return;
  comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
  if (!comp)
    return;

  list = ctxt->nodeList;
  if (!list || list->nodeNr <= 1)
    return;  // Nothing to do.

  for (int j = 0; j < nbsorts; ++j) {
    comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
    tempstype[j] = 0;
    if (!comp->stype && comp->has_stype) {
      comp->stype = xsltEvalAttrValueTemplate(
          ctxt, sorts[j], ToXMLChar("data-type"), XSLT_NAMESPACE);
      if (comp->stype) {
        tempstype[j] = 1;
        if (xmlStrEqual(comp->stype, ToXMLChar("text"))) {
          comp->number = 0;
        } else if (xmlStrEqual(comp->stype, ToXMLChar("number"))) {
          comp->number = 1;
        } else {
          xsltTransformError(
              ctxt, nullptr, sorts[j],
              "xsltDoSortFunction: no support for data-type = %s\n",
              comp->stype);
          comp->number = 0;  // Use default.
        }
      }
    }
    temporder[j] = 0;
    if (!comp->order && comp->has_order) {
      comp->order = xsltEvalAttrValueTemplate(
          ctxt, sorts[j], ToXMLChar("order"), XSLT_NAMESPACE);
      if (comp->order) {
        temporder[j] = 1;
        if (xmlStrEqual(comp->order, ToXMLChar("ascending"))) {
          comp->descending = 0;
        } else if (xmlStrEqual(comp->order, ToXMLChar("descending"))) {
          comp->descending = 1;
        } else {
          xsltTransformError(ctxt, nullptr, sorts[j],
                             "xsltDoSortFunction: invalid value %s for order\n",
                             comp->order);
          comp->descending = 0;  // Use default.
        }
      }
    }
  }

  int len = list->nodeNr;

  results_tab[0] = xsltComputeSortResult(ctxt, sorts[0]);
  for (int i = 1; i < XSLT_MAX_SORT; ++i)
    results_tab[i] = nullptr;

  results = results_tab[0];

  comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
  int descending = comp->descending;
  int number = comp->number;
  if (!results)
    return;

  // We are passing a language identifier to a function that expects a locale
  // identifier. The implementation of Collator should be lenient, and accept
  // both "en-US" and "en_US", for example. This lets an author to really
  // specify sorting rules, e.g. "de_DE@collation=phonebook", which isn't
  // possible with language alone.
  const char* lang =
      comp->has_lang ? reinterpret_cast<const char*>(comp->lang) : "en";

  UErrorCode status = U_ZERO_ERROR;
  char equivalent_locale[ULOC_FULLNAME_CAPACITY];
  UBool is_available;
  ucol_getFunctionalEquivalent(equivalent_locale, ULOC_FULLNAME_CAPACITY,
                               "collation", lang, &is_available, &status);
  if (U_FAILURE(status)) {
    strcpy(equivalent_locale, "root");
    status = U_ZERO_ERROR;
  }

  DEFINE_STATIC_LOCAL(std::unique_ptr<UCollatorHolder>, cached_collator, ());
  std::unique_ptr<UCollatorHolder> collator;
  if (cached_collator &&
      !strcmp(cached_collator->equivalent_locale, equivalent_locale) &&
      cached_collator->lower_first == comp->lower_first) {
    collator = std::move(cached_collator);
  } else {
    collator = std::make_unique<UCollatorHolder>();
    strncpy(collator->equivalent_locale, equivalent_locale,
            ULOC_FULLNAME_CAPACITY);
    collator->lower_first = comp->lower_first;

    collator->collator.reset(ucol_open(lang, &status));
    if (U_FAILURE(status)) {
      status = U_ZERO_ERROR;
      collator->collator.reset(ucol_open("", &status));
    }
    DCHECK(U_SUCCESS(status));
    ucol_setAttribute(*collator, UCOL_CASE_FIRST,
                      comp->lower_first ? UCOL_LOWER_FIRST : UCOL_UPPER_FIRST,
                      &status);
    DCHECK(U_SUCCESS(status));
    ucol_setAttribute(*collator, UCOL_NORMALIZATION_MODE, UCOL_ON, &status);
    DCHECK(U_SUCCESS(status));
  }

  // Shell's sort of node-set.
  for (int incr = len / 2; incr > 0; incr /= 2) {
    for (int i = incr; i < len; ++i) {
      int j = i - incr;
      if (!results[i])
        continue;

      while (j >= 0) {
        int tst;
        if (!results[j]) {
          tst = 1;
        } else {
          if (number) {
            // We make NaN smaller than number in accordance with
            // XSLT spec.
            if (xmlXPathIsNaN(results[j]->floatval)) {
              if (xmlXPathIsNaN(results[j + incr]->floatval))
                tst = 0;
              else
                tst = -1;
            } else if (xmlXPathIsNaN(results[j + incr]->floatval)) {
              tst = 1;
            } else if (results[j]->floatval == results[j + incr]->floatval) {
              tst = 0;
            } else if (results[j]->floatval > results[j + incr]->floatval) {
              tst = 1;
            } else {
              tst = -1;
            }
          } else {
            Vector<UChar> string1;
            Vector<UChar> string2;
            String::FromUTF8(
                reinterpret_cast<const char*>(results[j]->stringval))
                .AppendTo(string1);
            String::FromUTF8(
                reinterpret_cast<const char*>(results[j + incr]->stringval))
                .AppendTo(string2);
            tst = ucol_strcoll(*collator, string1.data(), string1.size(),
                               string2.data(), string2.size());
          }
          if (descending)
            tst = -tst;
        }
        if (tst == 0) {
          // Okay we need to use multi level sorts.
          depth = 1;
          while (depth < nbsorts) {
            if (!sorts[depth])
              break;
            comp = static_cast<xsltStylePreComp*>(sorts[depth]->psvi);
            if (!comp)
              break;
            int desc = comp->descending;
            int numb = comp->number;

            // Compute the result of the next level for the full
            // set, this might be optimized ... or not
            if (!results_tab[depth])
              results_tab[depth] = xsltComputeSortResult(ctxt, sorts[depth]);
            xmlXPathObjectPtr* res = results_tab[depth];
            if (!res)
              break;
            if (!res[j]) {
              if (res[j + incr])
                tst = 1;
            } else {
              if (numb) {
                // We make NaN smaller than number in accordance
                // with XSLT spec.
                if (xmlXPathIsNaN(res[j]->floatval)) {
                  if (xmlXPathIsNaN(res[j + incr]->floatval))
                    tst = 0;
                  else
                    tst = -1;
                } else if (xmlXPathIsNaN(res[j + incr]->floatval)) {
                  tst = 1;
                } else if (res[j]->floatval == res[j + incr]->floatval) {
                  tst = 0;
                } else if (res[j]->floatval > res[j + incr]->floatval) {
                  tst = 1;
                } else {
                  tst = -1;
                }
              } else {
                Vector<UChar> string1;
                Vector<UChar> string2;
                String::FromUTF8(
                    reinterpret_cast<const char*>(res[j]->stringval))
                    .AppendTo(string1);
                String::FromUTF8(
                    reinterpret_cast<const char*>(res[j + incr]->stringval))
                    .AppendTo(string2);
                tst = ucol_strcoll(*collator, string1.data(), string1.size(),
                                   string2.data(), string2.size());
              }
              if (desc)
                tst = -tst;
            }

            // if we still can't differenciate at this level try one
            // level deeper.
            if (tst != 0)
              break;
            depth++;
          }
        }
        if (tst == 0) {
          tst = results[j]->index > results[j + incr]->index;
        }
        if (tst > 0) {
          xmlXPathObjectPtr tmp = results[j];
          results[j] = results[j + incr];
          results[j + incr] = tmp;
          node = list->nodeTab[j];
          list->nodeTab[j] = list->nodeTab[j + incr];
          list->nodeTab[j + incr] = node;
          depth = 1;
          while (depth < nbsorts) {
            if (!sorts[depth])
              break;
            if (!results_tab[depth])
              break;
            xmlXPathObjectPtr* res = results_tab[depth];
            tmp = res[j];
            res[j] = res[j + incr];
            res[j + incr] = tmp;
            depth++;
          }
          j -= incr;
        } else {
          break;
        }
      }
    }
  }

  for (int j = 0; j < nbsorts; ++j) {
    comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
    if (tempstype[j] == 1) {
      // The data-type needs to be recomputed each time.
      xmlFree(const_cast<xmlChar*>(comp->stype));
      comp->stype = nullptr;
    }
    if (temporder[j] == 1) {
      // The order needs to be recomputed each time.
      xmlFree(const_cast<xmlChar*>(comp->order));
      comp->order = nullptr;
    }
    if (results_tab[j]) {
      for (int i = 0; i < len; ++i)
        xmlXPathFreeObject(results_tab[j][i]);
      xmlFree(results_tab[j]);
    }
  }

  cached_collator = std::move(collator);
}

}  // namespace blink