/*
   +----------------------------------------------------------------------+
   | Copyright © The PHP Group and Contributors.                          |
   +----------------------------------------------------------------------+
   | This source file is subject to the Modified BSD License that is      |
   | bundled with this package in the file LICENSE, and is available      |
   | through the World Wide Web at <https://www.php.net/license/>.        |
   |                                                                      |
   | SPDX-License-Identifier: BSD-3-Clause                                |
   +----------------------------------------------------------------------+
   | Authors: Vadim Savchuk <vsavchuk@productengine.com>                  |
   |          Dmitry Lakhtyuk <dlakhtyuk@productengine.com>               |
   +----------------------------------------------------------------------+
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#if __cplusplus >= 201703L
#include <string_view>
#include <unicode/unistr.h>
#endif

extern "C" {
#include "php_intl.h"
#include "intl_convert.h"
}
#include "collator.h"
#include "collator_class.h"
#include "collator_sort.h"
#include "collator_convert.h"

/**
 * Declare 'index' which will point to sort key in sort key
 * buffer.
 */
typedef struct _collator_sort_key_index {
	char* key;       /* pointer to sort key */
	zval* zstr;     /* pointer to original string(hash-item) */
} collator_sort_key_index_t;

ZEND_EXTERN_MODULE_GLOBALS( intl )

static const size_t DEF_SORT_KEYS_BUF_SIZE = 1048576;
static const size_t DEF_SORT_KEYS_BUF_INCREMENT = 1048576;

static const size_t DEF_SORT_KEYS_INDX_BUF_SIZE = 1048576;
static const size_t DEF_SORT_KEYS_INDX_BUF_INCREMENT = 1048576;

static const size_t DEF_UTF16_BUF_SIZE = 1024;

static void collator_report_sort_error(Collator_object *co, const intl_error *sort_error)
{
	if (sort_error->custom_error_message) {
		intl_errors_set(
			COLLATOR_ERROR_P(co), sort_error->code,
			ZSTR_VAL(sort_error->custom_error_message));
	} else {
		intl_errors_set_code(COLLATOR_ERROR_P(co), sort_error->code);
	}
}

/* {{{ collator_regular_compare_function */
static int collator_regular_compare_function(zval *result, zval *op1, zval *op2)
{
	int rc = SUCCESS;
	zval str1, str2;
	zval num1, num2;
	zval norm1, norm2;
	zval *num1_p = nullptr, *num2_p = nullptr;
	zval *norm1_p = nullptr, *norm2_p = nullptr;
	zval *str1_p = nullptr, *str2_p = nullptr;

	ZVAL_NULL(&str1);
	str1_p  = collator_convert_object_to_string( op1, &str1 );
	if( str1_p == nullptr ) {
		return FAILURE;
	}

	ZVAL_NULL(&str2);
	str2_p  = collator_convert_object_to_string( op2, &str2 );
	if( str2_p == nullptr ) {
		rc = FAILURE;
		goto cleanup;
	}

	/* If both args are strings AND either of args is not numeric string
	 * then use ICU-compare. Otherwise PHP-compare. */
	if( Z_TYPE_P(str1_p) == IS_STRING && Z_TYPE_P(str2_p) == IS_STRING &&
		( str1_p == ( num1_p = collator_convert_string_to_number_if_possible( str1_p, &num1 ) ) ||
		  str2_p == ( num2_p = collator_convert_string_to_number_if_possible( str2_p, &num2 ) ) ) )
	{
		/* Compare the strings using ICU. */
		ZEND_ASSERT(INTL_G(current_collator) != nullptr);
		ZVAL_LONG(result, ucol_strcoll(
					INTL_G(current_collator),
					INTL_ZSTR_VAL(Z_STR_P(str1_p)), INTL_ZSTR_LEN(Z_STR_P(str1_p)),
					INTL_ZSTR_VAL(Z_STR_P(str2_p)), INTL_ZSTR_LEN(Z_STR_P(str2_p)) ));
	}
	else
	{
		/* num1 is set if str1 and str2 are strings. */
		if( num1_p )
		{
			if( num1_p == str1_p )
			{
				/* str1 is string but not numeric string
				 * just convert it to utf8.
				 */
				norm1_p = collator_convert_zstr_utf16_to_utf8( str1_p, &norm1 );
				if( norm1_p == nullptr ) {
					rc = FAILURE;
					goto cleanup;
				}

				/* num2 is not set but str2 is string => do normalization. */
				norm2_p = collator_normalize_sort_argument( str2_p, &norm2 );
				if( norm2_p == nullptr ) {
					rc = FAILURE;
					goto cleanup;
				}
			}
			else
			{
				/* str1 is numeric strings => passthru to PHP-compare. */
				Z_TRY_ADDREF_P(num1_p);
				norm1_p = num1_p;

				/* str2 is numeric strings => passthru to PHP-compare. */
				Z_TRY_ADDREF_P(num2_p);
				norm2_p = num2_p;
			}
		}
		else
		{
			/* num1 is not set if str1 or str2 is not a string => do normalization. */
			norm1_p = collator_normalize_sort_argument( str1_p, &norm1 );
			if( norm1_p == nullptr ) {
				rc = FAILURE;
				goto cleanup;
			}

			/* if num1 is not set then num2 is not set as well => do normalization. */
			norm2_p = collator_normalize_sort_argument( str2_p, &norm2 );
			if( norm2_p == nullptr ) {
				rc = FAILURE;
				goto cleanup;
			}
		}

		rc = compare_function( result, norm1_p, norm2_p );
	}

cleanup:
	if( norm1_p )
		zval_ptr_dtor( norm1_p );

	if( norm2_p )
		zval_ptr_dtor( norm2_p );

	if( num1_p )
		zval_ptr_dtor( num1_p );

	if( num2_p )
		zval_ptr_dtor( num2_p );

	if( str1_p )
		zval_ptr_dtor( str1_p );

	if( str2_p )
		zval_ptr_dtor( str2_p );

	return rc;
}
/* }}} */

/* {{{ collator_numeric_compare_function
 * Convert input args to double and compare it.
 */
static int collator_numeric_compare_function(zval *result, zval *op1, zval *op2)
{
	zval num1, num2;
	zval *num1_p = nullptr;
	zval *num2_p = nullptr;

	if( Z_TYPE_P(op1) == IS_STRING )
	{
		num1_p = collator_convert_string_to_double( op1, &num1 );
		op1 = num1_p;
	}

	if( Z_TYPE_P(op2) == IS_STRING )
	{
		num2_p = collator_convert_string_to_double( op2, &num2 );
		op2 = num2_p;
	}

	ZVAL_LONG(result, numeric_compare_function(op1, op2));

	if( num1_p )
		zval_ptr_dtor( num1_p );
	if( num2_p )
		zval_ptr_dtor( num2_p );

	return SUCCESS;
}
/* }}} */

/* {{{ collator_icu_compare_function
 * Direct use of ucol_strcoll.
*/
static int collator_icu_compare_function(zval *result, zval *op1, zval *op2)
{
	zend_string *str1 = collator_zval_to_string(op1);
	if( str1 == nullptr ) {
		return FAILURE;
	}

	zend_string *str2 = collator_zval_to_string(op2);
	if( str2 == nullptr ) {
		zend_string_release(str1);
		return FAILURE;
	}

	/* Compare the strings using ICU. */
	ZEND_ASSERT(INTL_G(current_collator) != nullptr);
	ZVAL_LONG(result, ucol_strcoll(
				INTL_G(current_collator),
				INTL_ZSTR_VAL(str1), INTL_ZSTR_LEN(str1),
				INTL_ZSTR_VAL(str2), INTL_ZSTR_LEN(str2) ));

	zend_string_release(str1);
	zend_string_release(str2);

	return SUCCESS;
}
/* }}} */

/* {{{ collator_compare_func
 * Taken from PHP7 source (array_data_compare).
 */
static int collator_compare_func(Bucket *f, Bucket *s)
{
	zval result;
	zval *first = &f->val;
	zval *second = &s->val;

	ZEND_ASSERT(INTL_G(current_collator_error) != nullptr);
	if( EG(exception) || U_FAILURE( INTL_ERROR_CODE(*INTL_G(current_collator_error)) ) ) {
		return 0;
	}

	if( INTL_G(compare_func)( &result, first, second) == FAILURE )
		return 0;

	if( Z_TYPE(result) == IS_DOUBLE )
	{
		if( Z_DVAL(result) < 0 )
			return -1;
		else if( Z_DVAL(result) > 0 )
			return 1;
		else
			return 0;
	}

	convert_to_long(&result);

	if( Z_LVAL(result) < 0 )
		return -1;
	else if( Z_LVAL(result) > 0 )
		return 1;

	return 0;
}
/* }}} */

/* {{{ Compare sort keys */
static int collator_cmp_sort_keys( const void *p1, const void *p2 )
{
	char* key1 = ((collator_sort_key_index_t*)p1)->key;
	char* key2 = ((collator_sort_key_index_t*)p2)->key;

	return strcmp( key1, key2 );
}
/* }}} */

/* {{{ Choose compare function according to sort flags. */
static collator_compare_func_t collator_get_compare_function( const zend_long sort_flags )
{
	collator_compare_func_t func;

	switch( sort_flags )
	{
		case COLLATOR_SORT_NUMERIC:
			func = collator_numeric_compare_function;
			break;

		case COLLATOR_SORT_STRING:
			func = collator_icu_compare_function;
			break;

		case COLLATOR_SORT_REGULAR:
		default:
			func = collator_regular_compare_function;
			break;
	}

	return func;
}
/* }}} */

/* {{{ Common code shared by collator_sort() and collator_asort() API functions. */
static void collator_sort_internal( int renumber, INTERNAL_FUNCTION_PARAMETERS )
{
	UCollator*     saved_collator;
	intl_error*    saved_collator_error;
	intl_error     sort_error;
	collator_compare_func_t saved_compare_func;
	zval*          array            = nullptr;
	HashTable*     hash             = nullptr;
	zend_array*    sorted           = nullptr;
	zend_long           sort_flags       = COLLATOR_SORT_REGULAR;

	COLLATOR_METHOD_INIT_VARS

	/* Parse parameters. */
	if( zend_parse_method_parameters( ZEND_NUM_ARGS(), getThis(), "Oa|l",
		&object, Collator_ce_ptr, &array, &sort_flags ) == FAILURE )
	{
		RETURN_THROWS();
	}

	/* Fetch the object. */
	COLLATOR_METHOD_FETCH_OBJECT;

	if (!co->ucoll) {
		zend_throw_error(NULL, "Object not initialized");
		RETURN_THROWS();
	}

	hash = Z_ARRVAL_P( array );

	/* Copy array, so the in-place modifications will not be visible to the callback function */
	sorted = zend_array_dup( hash );

	/* Convert strings in the specified array from UTF-8 to UTF-16. */
	collator_convert_hash_from_utf8_to_utf16( sorted, COLLATOR_ERROR_CODE_P( co ) );
	if( U_FAILURE( COLLATOR_ERROR_CODE( co ) ) ) {
		zend_array_destroy( sorted );
	}
	COLLATOR_CHECK_STATUS( co, "Error converting hash from UTF-8 to UTF-16" );

	intl_error_init( &sort_error );

	/* Save specified collator in the request-global (?) variable. */
	saved_collator = INTL_G( current_collator );
	saved_collator_error = INTL_G( current_collator_error );
	saved_compare_func = INTL_G( compare_func );
	INTL_G( current_collator ) = co->ucoll;
	INTL_G( current_collator_error ) = &sort_error;
	INTL_G( compare_func ) = collator_get_compare_function( sort_flags );

	/* Sort specified array. */
	zend_hash_sort( sorted, collator_compare_func, renumber );

	/* Restore saved collator. */
	INTL_G( current_collator ) = saved_collator;
	INTL_G( current_collator_error ) = saved_collator_error;
	INTL_G( compare_func ) = saved_compare_func;

	if( EG(exception) ) {
		zend_array_destroy( sorted );
		intl_error_reset( &sort_error );
		RETURN_THROWS();
	}

	if( U_FAILURE( INTL_ERROR_CODE(sort_error) ) ) {
		zend_array_destroy( sorted );
		collator_report_sort_error(co, &sort_error);
		intl_error_reset( &sort_error );
		RETURN_FALSE;
	}

	intl_error_reset( &sort_error );

	/* Convert strings in the specified array back to UTF-8. */
	collator_convert_hash_from_utf16_to_utf8( sorted, COLLATOR_ERROR_CODE_P( co ) );
	if( U_FAILURE( COLLATOR_ERROR_CODE( co ) ) ) {
		zend_array_destroy( sorted );
	}
	COLLATOR_CHECK_STATUS( co, "Error converting hash from UTF-16 to UTF-8" );

	zval garbage;
	ZVAL_COPY_VALUE( &garbage, array );
	ZVAL_ARR( array, sorted );
	zval_ptr_dtor( &garbage );

	RETURN_TRUE;
}
/* }}} */

/* {{{ Sort array using specified collator. */
U_CFUNC PHP_FUNCTION( collator_sort )
{
	collator_sort_internal( true, INTERNAL_FUNCTION_PARAM_PASSTHRU );
}
/* }}} */

static void collator_sortkey_swap(collator_sort_key_index_t *p, collator_sort_key_index_t *q) /* {{{ */
{
	collator_sort_key_index_t t;
	t = *p;
	*p = *q;
	*q = t;
}
/* }}} */

/* {{{ Equivalent to standard PHP sort using Collator.
 * Uses ICU ucol_getSortKey for performance.
 */
U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
{
	zval*       array                = nullptr;
	zval        garbage;
	HashTable*  hash                 = nullptr;
	zval*       hashData             = nullptr;                     /* currently processed item of input hash */

	char*       sortKeyBuf           = nullptr;                     /* buffer to store sort keys */
	uint32_t    sortKeyBufSize       = DEF_SORT_KEYS_BUF_SIZE;   /* buffer size */
	ptrdiff_t   sortKeyBufOffset     = 0;                        /* pos in buffer to store sort key */
	uint32_t    sortKeyLen           = 0;                        /* the length of currently processing key */
	uint32_t    bufLeft              = 0;
	uint32_t    bufIncrement         = 0;

	collator_sort_key_index_t* sortKeyIndxBuf = nullptr;            /* buffer to store 'indexes' which will be passed to 'qsort' */
	uint32_t    sortKeyIndxBufSize   = DEF_SORT_KEYS_INDX_BUF_SIZE;
	uint32_t    sortKeyIndxSize      = sizeof( collator_sort_key_index_t );

	uint32_t    sortKeyCount         = 0;
	uint32_t    j                    = 0;

	UChar*      utf16_buf            = nullptr;                     /* tmp buffer to hold current processing string in utf-16 */
	int         utf16_buf_size       = DEF_UTF16_BUF_SIZE;       /* the length of utf16_buf */
	int         utf16_len            = 0;                        /* length of converted string */

	COLLATOR_METHOD_INIT_VARS

	/* Parse parameters. */
	if( zend_parse_method_parameters( ZEND_NUM_ARGS(), getThis(), "Oa",
		&object, Collator_ce_ptr, &array ) == FAILURE )
	{
		RETURN_THROWS();
	}

	/* Fetch the object. */
	COLLATOR_METHOD_FETCH_OBJECT;

	if (!co || !co->ucoll) {
		intl_error_set_code( nullptr, COLLATOR_ERROR_CODE( co ) );
		intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ), "Object not initialized");
		zend_throw_error(NULL, "Object not initialized");

		RETURN_THROWS();
	}

	/*
	 * Sort specified array.
	 */
	hash = Z_ARRVAL_P( array );

	if( !hash || zend_hash_num_elements( hash ) == 0 )
		RETURN_TRUE;

	/* Create buffers */
	sortKeyBuf     = reinterpret_cast<char *>(ecalloc( sortKeyBufSize,     sizeof( char    ) ));
	sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(ecalloc( sortKeyIndxBufSize, sizeof( uint8_t ) ));
	utf16_buf      = eumalloc( utf16_buf_size );

	/* Iterate through input hash and create a sort key for each value. */
	ZEND_HASH_FOREACH_VAL(hash, hashData) {
		/* Convert current hash item from UTF-8 to UTF-16LE and save the result to utf16_buf. */

		utf16_len = utf16_buf_size;

		/* Process string values only. */
		if( Z_TYPE_P( hashData ) == IS_STRING )
		{
			intl_convert_utf8_to_utf16( &utf16_buf, &utf16_len, Z_STRVAL_P( hashData ), Z_STRLEN_P( hashData ), COLLATOR_ERROR_CODE_P( co ) );

			if( U_FAILURE( COLLATOR_ERROR_CODE( co ) ) )
			{
				intl_error_set_code( nullptr, COLLATOR_ERROR_CODE( co ) );
				intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ), "Sort with sort keys failed");

				if( utf16_buf )
					efree( utf16_buf );

				efree( sortKeyIndxBuf );
				efree( sortKeyBuf );

				RETURN_FALSE;
			}
		}
		else
		{
			/* Set empty string */
			utf16_len = 0;
			utf16_buf[utf16_len] = 0;
		}

		if( (utf16_len + 1) > utf16_buf_size )
			utf16_buf_size = utf16_len + 1;

		/* Get sort key, reallocating the buffer if needed. */
		bufLeft = sortKeyBufSize - sortKeyBufOffset;

		sortKeyLen = ucol_getSortKey( co->ucoll,
									  utf16_buf,
									  utf16_len,
									  (uint8_t*)sortKeyBuf + sortKeyBufOffset,
									  bufLeft );

		/* check for sortKeyBuf overflow, increasing its size of the buffer if needed */
		if( sortKeyLen > bufLeft )
		{
			bufIncrement = ( sortKeyLen > DEF_SORT_KEYS_BUF_INCREMENT ) ? sortKeyLen : DEF_SORT_KEYS_BUF_INCREMENT;

			sortKeyBufSize += bufIncrement;
			bufLeft += bufIncrement;

			sortKeyBuf = reinterpret_cast<char *>(erealloc( sortKeyBuf, sortKeyBufSize ));

			sortKeyLen = ucol_getSortKey( co->ucoll, utf16_buf, utf16_len, (uint8_t*)sortKeyBuf + sortKeyBufOffset, bufLeft );
		}

		/*  check sortKeyIndxBuf overflow, increasing its size of the buffer if needed */
		if( ( sortKeyCount + 1 ) * sortKeyIndxSize > sortKeyIndxBufSize )
		{
			bufIncrement = ( sortKeyIndxSize > DEF_SORT_KEYS_INDX_BUF_INCREMENT ) ? sortKeyIndxSize : DEF_SORT_KEYS_INDX_BUF_INCREMENT;

			sortKeyIndxBufSize += bufIncrement;

			sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(erealloc( sortKeyIndxBuf, sortKeyIndxBufSize ));
		}

		sortKeyIndxBuf[sortKeyCount].key = (char*)sortKeyBufOffset;    /* remember just offset, cause address */
		                                                               /* of 'sortKeyBuf' may be changed due to realloc. */
		sortKeyIndxBuf[sortKeyCount].zstr = hashData;

		sortKeyBufOffset += sortKeyLen;
		++sortKeyCount;

	} ZEND_HASH_FOREACH_END();

	/* update ptrs to point to valid keys. */
	for( j = 0; j < sortKeyCount; j++ )
		sortKeyIndxBuf[j].key = sortKeyBuf + (ptrdiff_t)sortKeyIndxBuf[j].key;

	/* sort it */
	zend_sort( sortKeyIndxBuf, sortKeyCount,
			sortKeyIndxSize, collator_cmp_sort_keys, (swap_func_t)collator_sortkey_swap);

	ZVAL_COPY_VALUE(&garbage, array);
	/* for resulting hash we'll assign new hash keys rather then reordering */
	array_init_size(array, sortKeyCount);
	zend_hash_real_init_packed(Z_ARRVAL_P(array));

	for( j = 0; j < sortKeyCount; j++ )
	{
		Z_TRY_ADDREF_P( sortKeyIndxBuf[j].zstr );
		zend_hash_next_index_insert( Z_ARRVAL_P(array), sortKeyIndxBuf[j].zstr);
	}

	if( utf16_buf )
		efree( utf16_buf );

	zval_ptr_dtor(&garbage);
	efree( sortKeyIndxBuf );
	efree( sortKeyBuf );

	RETURN_TRUE;
}
/* }}} */

/* {{{ Sort array using specified collator, maintaining index association. */
U_CFUNC PHP_FUNCTION( collator_asort )
{
	collator_sort_internal( false, INTERNAL_FUNCTION_PARAM_PASSTHRU );
}
/* }}} */

/* {{{ Get a sort key for a string from a Collator. */
U_CFUNC PHP_FUNCTION( collator_get_sort_key )
{
	char*            str      = nullptr;
	size_t           str_len  = 0;
	UChar*           ustr     = nullptr;
	int32_t          ustr_len = 0;
	int              key_len = 0;
	zend_string*     key_str;

	COLLATOR_METHOD_INIT_VARS

	/* Parse parameters. */
	if( zend_parse_method_parameters( ZEND_NUM_ARGS(), getThis(), "Os",
		&object, Collator_ce_ptr, &str, &str_len ) == FAILURE )
	{
		RETURN_THROWS();
	}

	/* Fetch the object. */
	COLLATOR_METHOD_FETCH_OBJECT;

	if (!co || !co->ucoll) {
		intl_error_set_code( nullptr, COLLATOR_ERROR_CODE( co ) );
		intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ), "Object not initialized");
		zend_throw_error(NULL, "Object not initialized");

		RETURN_THROWS();
	}

	/*
	 * Compare given strings (converting them to UTF-16 first).
	 */

	/* First convert the strings to UTF-16. */
	intl_convert_utf8_to_utf16(
		&ustr, &ustr_len, str, str_len, COLLATOR_ERROR_CODE_P( co ) );
	if( U_FAILURE( COLLATOR_ERROR_CODE( co ) ) )
	{
		/* Set global error code. */
		intl_error_set_code( nullptr, COLLATOR_ERROR_CODE( co ) );

		/* Set error messages. */
		intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ), "Error converting first argument to UTF-16");
		efree( ustr );
		RETURN_FALSE;
	}

	/* ucol_getSortKey is exception in that the key length includes the
	 * NUL terminator*/
	key_len = ucol_getSortKey(co->ucoll, ustr, ustr_len, nullptr, 0);
	if(!key_len) {
		efree( ustr );
		RETURN_FALSE;
	}
	key_str = zend_string_alloc(key_len, 0);
	key_len = ucol_getSortKey(co->ucoll, ustr, ustr_len, (uint8_t*)ZSTR_VAL(key_str), key_len);
	efree( ustr );
	if(!key_len) {
		zend_string_efree(key_str);
		RETURN_FALSE;
	}
	ZSTR_LEN(key_str) = key_len - 1;
	RETVAL_NEW_STR(key_str);
}
/* }}} */
