From: antirez Date: Wed, 1 Feb 2012 14:22:28 +0000 (+0100) Subject: SORT is now more deterministic: does not accept to compare by score items that have... X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/2c861050c17237a61fdaff4da2777c5d18ce979a SORT is now more deterministic: does not accept to compare by score items that have scores not representing a valid double. Also items with the same score are compared lexycographically. At the same time the scripting side introduced the ability to sort the output of SORT when sort uses the BY optimization, resulting in no specific ordering. Since in this case the user may use GET, and the result of GET can be null, converted into false as Lua data type, this commit also introduces the ability to sort Lua tables containining false, only if the first (faster) attempt at using just table.sort with a single argument fails. --- diff --git a/src/redis.c b/src/redis.c index a76a5618..8cb18e91 100644 --- a/src/redis.c +++ b/src/redis.c @@ -216,7 +216,7 @@ struct redisCommand redisCommandTable[] = { {"sync",syncCommand,1,"ars",0,NULL,0,0,0,0,0}, {"flushdb",flushdbCommand,1,"w",0,NULL,0,0,0,0,0}, {"flushall",flushallCommand,1,"w",0,NULL,0,0,0,0,0}, - {"sort",sortCommand,-2,"wm",0,NULL,1,1,1,0,0}, + {"sort",sortCommand,-2,"wmS",0,NULL,1,1,1,0,0}, {"info",infoCommand,-1,"r",0,NULL,0,0,0,0,0}, {"monitor",monitorCommand,1,"ars",0,NULL,0,0,0,0,0}, {"ttl",ttlCommand,2,"r",0,NULL,1,1,1,0,0}, diff --git a/src/redis.h b/src/redis.h index 3a5e3d4a..2fcdcb4d 100644 --- a/src/redis.h +++ b/src/redis.h @@ -627,6 +627,7 @@ struct redisServer { list *unblocked_clients; /* list of clients to unblock before next loop */ /* Sort parameters - qsort_r() is only available under BSD so we * have to take this state global, in order to pass it to sortCompare() */ + int sort_dontsort; int sort_desc; int sort_alpha; int sort_bypattern; diff --git a/src/scripting.c b/src/scripting.c index 92fb928a..2eac840c 100644 --- a/src/scripting.c +++ b/src/scripting.c @@ -140,7 +140,22 @@ void luaSortArray(lua_State *lua) { lua_pushstring(lua,"sort"); lua_gettable(lua,-2); /* Stack: array, table, table.sort */ lua_pushvalue(lua,-3); /* Stack: array, table, table.sort, array */ - lua_call(lua,1,0); /* Stack: array (sorted), table */ + if (lua_pcall(lua,1,0,0)) { + /* Stack: array, table, error */ + + /* We are not interested in the error, we assume that the problem is + * that there are 'false' elements inside the array, so we try + * again with a slower function but able to handle this case, that + * is: table.sort(table, __redis__compare_helper) */ + lua_pop(lua,1); /* Stack: array, table */ + lua_pushstring(lua,"sort"); /* Stack: array, table, sort */ + lua_gettable(lua,-2); /* Stack: array, table, table.sort */ + lua_pushvalue(lua,-3); /* Stack: array, table, table.sort, array */ + lua_getglobal(lua,"__redis__compare_helper"); + /* Stack: array, table, table.sort, array, __redis__compare_helper */ + lua_call(lua,2,0); + } + /* Stack: array (sorted), table */ lua_pop(lua,1); /* Stack: array (sorted) */ } @@ -228,7 +243,9 @@ int luaRedisGenericCommand(lua_State *lua, int raise_error) { * reply as expected. */ if ((cmd->flags & REDIS_CMD_SORT_FOR_SCRIPT) && (reply[0] == '*' && reply[1] != '-')) { - luaSortArray(lua); + /* Skip this step if command is SORT but output was already sorted */ + if (cmd->proc != sortCommand || server.sort_dontsort) + luaSortArray(lua); } sdsfree(reply); @@ -403,6 +420,18 @@ void scriptingInit(void) { lua_setglobal(lua,"math"); + /* Add a helper funciton that we use to sort the multi bulk output of non + * deterministic commands, when containing 'false' elements. */ + { + char *compare_func = "function __redis__compare_helper(a,b)\n" + " if a == false then a = '' end\n" + " if b == false then b = '' end\n" + " return a /* isnan() */ redisSortOperation *createSortOperation(int type, robj *pattern) { redisSortOperation *so = zmalloc(sizeof(*so)); @@ -102,7 +103,10 @@ int sortCompare(const void *s1, const void *s2) { } else if (so1->u.score < so2->u.score) { cmp = -1; } else { - cmp = 0; + /* Objects have the same score, but we don't want the comparison + * to be undefined, so we compare objects lexicographycally. + * This way the result of SORT is deterministic. */ + cmp = compareStringObjects(so1->obj,so2->obj); } } else { /* Alphanumeric sorting */ @@ -136,6 +140,7 @@ void sortCommand(redisClient *c) { long limit_start = 0, limit_count = -1, start, end; int j, dontsort = 0, vectorlen; int getop = 0; /* GET operation counter */ + int int_convertion_error = 0; robj *sortval, *sortby = NULL, *storekey = NULL; redisSortObject *vector; /* Resulting vector to sort */ @@ -266,7 +271,14 @@ void sortCommand(redisClient *c) { if (sortby) vector[j].u.cmpobj = getDecodedObject(byval); } else { if (byval->encoding == REDIS_ENCODING_RAW) { - vector[j].u.score = strtod(byval->ptr,NULL); + char *eptr; + + vector[j].u.score = strtod(byval->ptr,&eptr); + if (eptr[0] != '\0' || errno == ERANGE || + isnan(vector[j].u.score)) + { + int_convertion_error = 1; + } } else if (byval->encoding == REDIS_ENCODING_INT) { /* Don't need to decode the object if it's * integer-encoded (the only encoding supported) so @@ -295,6 +307,7 @@ void sortCommand(redisClient *c) { } if (end >= vectorlen) end = vectorlen-1; + server.sort_dontsort = dontsort; if (dontsort == 0) { server.sort_desc = desc; server.sort_alpha = alpha; @@ -308,7 +321,9 @@ void sortCommand(redisClient *c) { /* Send command output to the output buffer, performing the specified * GET/DEL/INCR/DECR operations if any. */ outputlen = getop ? getop*(end-start+1) : end-start+1; - if (storekey == NULL) { + if (int_convertion_error) { + addReplyError(c,"One or more scores can't be converted into double"); + } else if (storekey == NULL) { /* STORE option not specified, sent the sorting result to client */ addReplyMultiBulkLen(c,outputlen); for (j = start; j <= end; j++) { diff --git a/tests/unit/sort.tcl b/tests/unit/sort.tcl index 38813065..a50f0473 100644 --- a/tests/unit/sort.tcl +++ b/tests/unit/sort.tcl @@ -146,7 +146,7 @@ start_server { test "SORT with STORE does not create empty lists (github issue 224)" { r flushdb r lpush foo bar - r sort foo limit 10 10 store zap + r sort foo alpha limit 10 10 store zap r exists zap } {0}