/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: sw=2 ts=2 et lcs=trail\:.,tab\:>~ :
* 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 "mozilla/ArrayUtils.h"
#include "mozStorageSQLFunctions.h"
#include "nsUnicharUtils.h"
#include <algorithm>
namespace mozilla {
namespace storage {
////////////////////////////////////////////////////////////////////////////////
//// Local Helper Functions
namespace {
/**
* Performs the LIKE comparison of a string against a pattern. For more detail
* see http://www.sqlite.org/lang_expr.html#like.
*
* @param aPatternItr
* An iterator at the start of the pattern to check for.
* @param aPatternEnd
* An iterator at the end of the pattern to check for.
* @param aStringItr
* An iterator at the start of the string to check for the pattern.
* @param aStringEnd
* An iterator at the end of the string to check for the pattern.
* @param aEscapeChar
* The character to use for escaping symbols in the pattern.
* @return 1 if the pattern is found, 0 otherwise.
*/
int likeCompare(nsAString::const_iterator aPatternItr,
nsAString::const_iterator aPatternEnd,
nsAString::const_iterator aStringItr,
nsAString::const_iterator aStringEnd, char16_t aEscapeChar) {
const char16_t MATCH_ALL('%');
const char16_t MATCH_ONE('_');
bool lastWasEscape = false;
while (aPatternItr != aPatternEnd) {
/**
* What we do in here is take a look at each character from the input
* pattern, and do something with it. There are 4 possibilities:
* 1) character is an un-escaped match-all character
* 2) character is an un-escaped match-one character
* 3) character is an un-escaped escape character
* 4) character is not any of the above
*/
if (!lastWasEscape && *aPatternItr == MATCH_ALL) {
// CASE 1
/**
* Now we need to skip any MATCH_ALL or MATCH_ONE characters that follow a
* MATCH_ALL character. For each MATCH_ONE character, skip one character
* in the pattern string.
*/
while (*aPatternItr == MATCH_ALL || *aPatternItr == MATCH_ONE) {
if (*aPatternItr == MATCH_ONE) {
// If we've hit the end of the string we are testing, no match
if (aStringItr == aStringEnd) return 0;
aStringItr++;
}
aPatternItr++;
}
// If we've hit the end of the pattern string, match
if (aPatternItr == aPatternEnd) return 1;
while (aStringItr != aStringEnd) {
if (likeCompare(aPatternItr, aPatternEnd, aStringItr, aStringEnd,
aEscapeChar)) {
// we've hit a match, so indicate this
return 1;
}
aStringItr++;
}
// No match
return 0;
} else if (!lastWasEscape && *aPatternItr == MATCH_ONE) {
// CASE 2
if (aStringItr == aStringEnd) {
// If we've hit the end of the string we are testing, no match
return 0;
}
aStringItr++;
lastWasEscape = false;
} else if (!lastWasEscape && *aPatternItr == aEscapeChar) {
// CASE 3
lastWasEscape = true;
} else {
// CASE 4
if (::ToUpperCase(*aStringItr) != ::ToUpperCase(*aPatternItr)) {
// If we've hit a point where the strings don't match, there is no match
return 0;
}
aStringItr++;
lastWasEscape = false;
}
aPatternItr++;
}
return aStringItr == aStringEnd;
}
/**
* Compute the Levenshtein Edit Distance between two strings.
*
* @param aStringS
* a string
* @param aStringT
* another string
* @param _result
* an outparam that will receive the edit distance between the arguments
* @return a Sqlite result code, e.g. SQLITE_OK, SQLITE_NOMEM, etc.
*/
int levenshteinDistance(const nsAString &aStringS, const nsAString &aStringT,
int *_result) {
// Set the result to a non-sensical value in case we encounter an error.
*_result = -1;
const uint32_t sLen = aStringS.Length();
const uint32_t tLen = aStringT.Length();
if (sLen == 0) {
*_result = tLen;
return SQLITE_OK;
}
if (tLen == 0) {
*_result = sLen;
return SQLITE_OK;
}
// Notionally, Levenshtein Distance is computed in a matrix. If we
// assume s = "span" and t = "spam", the matrix would look like this:
// s -->
// t s p a n
// | 0 1 2 3 4
// V s 1 * * * *
// p 2 * * * *
// a 3 * * * *
// m 4 * * * *
//
// Note that the row width is sLen + 1 and the column height is tLen + 1,
// where sLen is the length of the string "s" and tLen is the length of "t".
// The first row and the first column are initialized as shown, and
// the algorithm computes the remaining cells row-by-row, and
// left-to-right within each row. The computation only requires that
// we be able to see the current row and the previous one.
// Allocate memory for two rows.
AutoTArray<int, nsAutoString::kStorageSize> row1;
AutoTArray<int, nsAutoString::kStorageSize> row2;
// Declare the raw pointers that will actually be used to access the memory.
int *prevRow = row1.AppendElements(sLen + 1);
int *currRow = row2.AppendElements(sLen + 1);
// Initialize the first row.
for (uint32_t i = 0; i <= sLen; i++) prevRow[i] = i;
const char16_t *s = aStringS.BeginReading();
const char16_t *t = aStringT.BeginReading();
// Compute the empty cells in the "matrix" row-by-row, starting with
// the second row.
for (uint32_t ti = 1; ti <= tLen; ti++) {
// Initialize the first cell in this row.
currRow[0] = ti;
// Get the character from "t" that corresponds to this row.
const char16_t tch = t[ti - 1];
// Compute the remaining cells in this row, left-to-right,
// starting at the second column (and first character of "s").
for (uint32_t si = 1; si <= sLen; si++) {
// Get the character from "s" that corresponds to this column,
// compare it to the t-character, and compute the "cost".
const char16_t sch = s[si - 1];
int cost = (sch == tch) ? 0 : 1;
// ............ We want to calculate the value of cell "d" from
// ...ab....... the previously calculated (or initialized) cells
// ...cd....... "a", "b", and "c", where d = min(a', b', c').
// ............
int aPrime = prevRow[si - 1] + cost;
int bPrime = prevRow[si] + 1;
int cPrime = currRow[si - 1] + 1;
currRow[si] = std::min(aPrime, std::min(bPrime, cPrime));
}
// Advance to the next row. The current row becomes the previous
// row and we recycle the old previous row as the new current row.
// We don't need to re-initialize the new current row since we will
// rewrite all of its cells anyway.
int *oldPrevRow = prevRow;
prevRow = currRow;
currRow = oldPrevRow;
}
// The final result is the value of the last cell in the last row.
// Note that that's now in the "previous" row, since we just swapped them.
*_result = prevRow[sLen];
return SQLITE_OK;
}
// This struct is used only by registerFunctions below, but ISO C++98 forbids
// instantiating a template dependent on a locally-defined type. Boo-urns!
struct Functions {
const char *zName;
int nArg;
int enc;
void *pContext;
void (*xFunc)(::sqlite3_context *, int, sqlite3_value **);
};
} // namespace
////////////////////////////////////////////////////////////////////////////////
//// Exposed Functions
int registerFunctions(sqlite3 *aDB) {
Functions functions[] = {
{"lower", 1, SQLITE_UTF16, 0, caseFunction},
{"lower", 1, SQLITE_UTF8, 0, caseFunction},
{"upper", 1, SQLITE_UTF16, (void *)1, caseFunction},
{"upper", 1, SQLITE_UTF8, (void *)1, caseFunction},
{"like", 2, SQLITE_UTF16, 0, likeFunction},
{"like", 2, SQLITE_UTF8, 0, likeFunction},
{"like", 3, SQLITE_UTF16, 0, likeFunction},
{"like", 3, SQLITE_UTF8, 0, likeFunction},
{"levenshteinDistance", 2, SQLITE_UTF16, 0, levenshteinDistanceFunction},
{"levenshteinDistance", 2, SQLITE_UTF8, 0, levenshteinDistanceFunction},
};
int rv = SQLITE_OK;
for (size_t i = 0; SQLITE_OK == rv && i < ArrayLength(functions); ++i) {
struct Functions *p = &functions[i];
rv = ::sqlite3_create_function(aDB, p->zName, p->nArg, p->enc, p->pContext,
p->xFunc, nullptr, nullptr);
}
return rv;
}
////////////////////////////////////////////////////////////////////////////////
//// SQL Functions
void caseFunction(sqlite3_context *aCtx, int aArgc, sqlite3_value **aArgv) {
NS_ASSERTION(1 == aArgc, "Invalid number of arguments!");
nsAutoString data(
static_cast<const char16_t *>(::sqlite3_value_text16(aArgv[0])));
bool toUpper = ::sqlite3_user_data(aCtx) ? true : false;
if (toUpper)
::ToUpperCase(data);
else
::ToLowerCase(data);
// Set the result.
::sqlite3_result_text16(aCtx, data.get(), -1, SQLITE_TRANSIENT);
}
/**
* This implements the like() SQL function. This is used by the LIKE operator.
* The SQL statement 'A LIKE B' is implemented as 'like(B, A)', and if there is
* an escape character, say E, it is implemented as 'like(B, A, E)'.
*/
void likeFunction(sqlite3_context *aCtx, int aArgc, sqlite3_value **aArgv) {
NS_ASSERTION(2 == aArgc || 3 == aArgc, "Invalid number of arguments!");
if (::sqlite3_value_bytes(aArgv[0]) > SQLITE_MAX_LIKE_PATTERN_LENGTH) {
::sqlite3_result_error(aCtx, "LIKE or GLOB pattern too complex",
SQLITE_TOOBIG);
return;
}
if (!::sqlite3_value_text16(aArgv[0]) || !::sqlite3_value_text16(aArgv[1]))
return;
nsDependentString A(
static_cast<const char16_t *>(::sqlite3_value_text16(aArgv[1])));
nsDependentString B(
static_cast<const char16_t *>(::sqlite3_value_text16(aArgv[0])));
NS_ASSERTION(!B.IsEmpty(), "LIKE string must not be null!");
char16_t E = 0;
if (3 == aArgc)
E = static_cast<const char16_t *>(::sqlite3_value_text16(aArgv[2]))[0];
nsAString::const_iterator itrString, endString;
A.BeginReading(itrString);
A.EndReading(endString);
nsAString::const_iterator itrPattern, endPattern;
B.BeginReading(itrPattern);
B.EndReading(endPattern);
::sqlite3_result_int(
aCtx, likeCompare(itrPattern, endPattern, itrString, endString, E));
}
void levenshteinDistanceFunction(sqlite3_context *aCtx, int aArgc,
sqlite3_value **aArgv) {
NS_ASSERTION(2 == aArgc, "Invalid number of arguments!");
// If either argument is a SQL NULL, then return SQL NULL.
if (::sqlite3_value_type(aArgv[0]) == SQLITE_NULL ||
::sqlite3_value_type(aArgv[1]) == SQLITE_NULL) {
::sqlite3_result_null(aCtx);
return;
}
int aLen = ::sqlite3_value_bytes16(aArgv[0]) / sizeof(char16_t);
const char16_t *a =
static_cast<const char16_t *>(::sqlite3_value_text16(aArgv[0]));
int bLen = ::sqlite3_value_bytes16(aArgv[1]) / sizeof(char16_t);
const char16_t *b =
static_cast<const char16_t *>(::sqlite3_value_text16(aArgv[1]));
// Compute the Levenshtein Distance, and return the result (or error).
int distance = -1;
const nsDependentString A(a, aLen);
const nsDependentString B(b, bLen);
int status = levenshteinDistance(A, B, &distance);
if (status == SQLITE_OK) {
::sqlite3_result_int(aCtx, distance);
} else if (status == SQLITE_NOMEM) {
::sqlite3_result_error_nomem(aCtx);
} else {
::sqlite3_result_error(aCtx, "User function returned error code", -1);
}
}
} // namespace storage
} // namespace mozilla