8000 Remove new coupling between NAMEDATALEN and MAX_LEVENSHTEIN_STRLEN. · postgrespro/postgres_cluster@a396144 · GitHub
[go: up one dir, main page]
Skip to content

Commit a396144

Browse files
tglsfdctglsfdc
committed
Remove new coupling between NAMEDATALEN and MAX_LEVENSHTEIN_STRLEN.
Commit e529cd4 introduced an Assert requiring NAMEDATALEN to be less than MAX_LEVENSHTEIN_STRLEN, which has been 255 for a long time. Since up to that instant we had always allowed NAMEDATALEN to be substantially more than that, this was ill-advised. It's debatable whether we need MAX_LEVENSHTEIN_STRLEN at all (versus putting a CHECK_FOR_INTERRUPTS into the loop), or whether it has to be so tight; but this patch takes the narrower approach of just not applying the MAX_LEVENSHTEIN_STRLEN limit to calls from the parser. Trusting the parser for this seems reasonable, first because the strings are limited to NAMEDATALEN which is unlikely to be hugely more than 256, and second because the maximum distance is tightly constrained by MAX_FUZZY_DISTANCE (though we'd forgotten to make use of that limit in one place). That means the cost is not really O(mn) but more like O(max(m,n)). Relaxing the limit for user-supplied calls is left for future research; given the lack of complaints to date, it doesn't seem very high priority. In passing, fix confusion between lengths-in-bytes and lengths-in-chars in comments and error messages. Per gripe from Kevin Day; solution suggested by Robert Haas. Back-patch to 9.5 where the unwanted restriction was introduced.
1 parent 647d87c commit a396144

File tree

4 files changed

+60
-45
lines changed

4 files changed

+60
-45
lines changed

‎contrib/fuzzystrmatch/fuzzystrmatch.c

Lines changed: 16 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -171,12 +171,12 @@ levenshtein_with_costs(PG_FUNCTION_ARGS)
171171
/* Extract a pointer to the actual character data */
172172
s_data = VARDATA_ANY(src);
173173
t_data = VARDATA_ANY(dst);
174-
/* Determine length of each string in bytes and characters */
174+
/* Determine length of each string in bytes */
175175
s_bytes = VARSIZE_ANY_EXHDR(src);
176176
t_bytes = VARSIZE_ANY_EXHDR(dst);
177177

178-
PG_RETURN_INT32(varstr_levenshtein(s_data, s_bytes, t_data, t_bytes, ins_c,
179-
del_c, sub_c));
178+
PG_RETURN_INT32(varstr_levenshtein(s_data, s_bytes, t_data, t_bytes,
179+
ins_c, del_c, sub_c, false));
180180
}
181181

182182

@@ -194,12 +194,12 @@ levenshtein(PG_FUNCTION_ARGS)
194194
/* Extract a pointer to the actual character data */
195195
s_data = VARDATA_ANY(src);
196196
t_data = VARDATA_ANY(dst);
197-
/* Determine length of each string in bytes and characters */
197+
/* Determine length of each string in bytes */
198198
s_bytes = VARSIZE_ANY_EXHDR(src);
199199
t_bytes = VARSIZE_ANY_EXHDR(dst);
200200

201-
PG_RETURN_INT32(varstr_levenshtein(s_data, s_bytes, t_data, t_bytes, 1, 1,
202-
1));
201+
PG_RETURN_INT32(varstr_levenshtein(s_data, s_bytes, t_data, t_bytes,
202+
1, 1, 1, false));
203203
}
204204

205205

@@ -221,13 +221,14 @@ levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS)
221221
/* Extract a pointer to the actual character data */
222222
s_data = VARDATA_ANY(src);
223223
t_data = VARDATA_ANY(dst);
224-
/* Determine length of each string in bytes and characters */
224+
/* Determine length of each string in bytes */
225225
s_bytes = VARSIZE_ANY_EXHDR(src);
226226
t_bytes = VARSIZE_ANY_EXHDR(dst);
227227

228-
PG_RETURN_INT32(varstr_levenshtein_less_equal(s_data, s_bytes, t_data,
229-
t_bytes, ins_c, del_c,
230-
sub_c, max_d));
228+
PG_RETURN_INT32(varstr_levenshtein_less_equal(s_data, s_bytes,
229+
t_data, t_bytes,
230+
ins_c, del_c, sub_c,
231+
max_d, false));
231232
}
232233

233234

@@ -246,12 +247,14 @@ levenshtein_less_equal(PG_FUNCTION_ARGS)
246247
/* Extract a pointer to the actual character data */
247248
s_data = VARDATA_ANY(src);
248249
t_data = VARDATA_ANY(dst);
249-
/* Determine length of each string in bytes and characters */
250+
/* Determine length of each string in bytes */
250251
s_bytes = VARSIZE_ANY_EXHDR(src);
251252
t_bytes = VARSIZE_ANY_EXHDR(dst);
252253

253-
PG_RETURN_INT32(varstr_levenshtein_less_equal(s_data, s_bytes, t_data,
254-
t_bytes, 1, 1, 1, max_d));
254+
PG_RETURN_INT32(varstr_levenshtein_less_equal(s_data, s_bytes,
255+
t_data, t_bytes,
256+
1, 1, 1,
257+
max_d, false));
255258
}
256259

257260

‎src/backend/parser/parse_relation.c

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -550,7 +550,8 @@ updateFuzzyAttrMatchState(int fuzzy_rte_penalty,
550550
varstr_levenshtein_less_equal(actual, strlen(actual), match, matchlen,
551551
1, 1, 1,
552552
fuzzystate->distance + 1
553-
- fuzzy_rte_penalty);
553+
- fuzzy_rte_penalty,
554+
true);
554555

555556
/*
556557
* If more than half the characters are different, don't treat it as a
@@ -843,10 +844,12 @@ searchRangeTableForCol(ParseState *pstate, const char *alias, char *colname,
843844
*/
844845
if (alias != NULL)
845846
fuzzy_rte_penalty =
846-
varstr_levenshtein(alias, strlen(alias),
847-
rte->eref->aliasname,
848-
strlen(rte->eref->aliasname),
849-
1, 1, 1);
847+
varstr_levenshtein_less_equal(alias, strlen(alias),
848+
rte->eref->aliasname,
849+
strlen(rte->eref->aliasname),
850+
1, 1, 1,
851+
MAX_FUZZY_DISTANCE + 1,
852+
true);
850853

851854
/*
852855
* Scan for a matching column; if we find an exact match, we're

‎src/backend/utils/adt/levenshtein.c

Lines changed: 29 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -26,9 +26,16 @@
2626
#define MAX_LEVENSHTEIN_STRLEN 255
2727

2828
/*
29-
* Calculates Levenshtein distance metric between supplied csrings, which are
30-
* not necessarily null-terminated. Generally (1, 1, 1) penalty costs suffices
31-
* for common cases, but your mileage may vary.
29+
* Calculates Levenshtein distance metric between supplied strings, which are
30+
* not necessarily null-terminated.
31+
*
32+
* source: source string, of length slen bytes.
33+
* target: target string, of length tlen bytes.
34+
* ins_c, del_c, sub_c: costs to charge for character insertion, deletion,
35+
* and substitution respectively; (1, 1, 1) costs suffice for common
36+
* cases, but your mileage may vary.
37+
* max_d: if provided and >= 0, maximum distance we care about; see below.
38+
* trusted: caller is trusted and need not obey MAX_LEVENSHTEIN_STRLEN.
3239
*
3340
* One way to compute Levenshtein distance is to incrementally construct
3441
* an (m+1)x(n+1) matrix where cell (i, j) represents the minimum number
@@ -43,7 +50,7 @@
4350
* array.
4451
*
4552
* If max_d >= 0, we only need to provide an accurate answer when that answer
46-
* is less than or equal to the bound. From any cell in the matrix, there is
53+
* is less than or equal to max_d. From any cell in the matrix, there is
4754
* theoretical "minimum residual distance" from that cell to the last column
4855
* of the final row. This minimum residual distance is zero when the
4956
* untransformed portions of the strings are of equal length (because we might
@@ -58,12 +65,15 @@
5865
*/
5966
int
6067
#ifdef LEVENSHTEIN_LESS_EQUAL
61-
varstr_levenshtein_less_equal(const char *source, int slen, const char *target,
62-
int tlen, int ins_c, int del_c, int sub_c,
63-
int max_d)
68+
varstr_levenshtein_less_equal(const char *source, int slen,
69+
const char *target, int tlen,
70+
int ins_c, int del_c, int sub_c,
71+
int max_d, bool trusted)
6472
#else
65-
varstr_levenshtein(const char *source, int slen, const char *target, int tlen,
66-
int ins_c, int del_c, int sub_c)
73+
varstr_levenshtein(const char *source, int slen,
74+
const char *target, int tlen,
75+
int ins_c, int del_c, int sub_c,
76+
bool trusted)
6777
#endif
6878
{
6979
int m,
@@ -95,15 +105,7 @@ varstr_levenshtein(const char *source, int slen, const char *target, int tlen,
95105
#define STOP_COLUMN m
96106
#endif
97107

98-
/*
99-
* A common use for Levenshtein distance is to match attributes when
100-
* building diagnostic, user-visible messages. Restrict the size of
101-
* MAX_LEVENSHTEIN_STRLEN at compile time so that this is guaranteed to
102-
* work.
103-
*/
104-
StaticAssertStmt(NAMEDATALEN <= MAX_LEVENSHTEIN_STRLEN,
105-
"Levenshtein hinting mechanism restricts NAMEDATALEN");
106-
108+
/* Convert string lengths (in bytes) to lengths in characters */
107109
m = pg_mbstrlen_with_len(source, slen);
108110
n = pg_mbstrlen_with_len(target, tlen);
109111

@@ -118,14 +120,18 @@ varstr_levenshtein(const char *source, int slen, const char *target, int tlen,
118120

119121
/*
120122
* For security concerns, restrict excessive CPU+RAM usage. (This
121-
* implementation uses O(m) memory and has O(mn) complexity.)
123+
* implementation uses O(m) memory and has O(mn) complexity.) If
124+
* "trusted" is true, caller is responsible for not making excessive
125+
* requests, typically by using a small max_d along with strings that are
126+
* bounded, though not necessarily to MAX_LEVENSHTEIN_STRLEN exactly.
122127
*/
123-
if (m > MAX_LEVENSHTEIN_STRLEN ||
124-
n > MAX_LEVENSHTEIN_STRLEN)
128+
if (!trusted &&
129+
(m > MAX_LEVENSHTEIN_STRLEN ||
130+
n > MAX_LEVENSHTEIN_STRLEN))
125131
ereport(ERROR,
126132
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
127-
errmsg("argument exceeds the maximum length of %d bytes",
128-
MAX_LEVENSHTEIN_STRLEN)));
133+
errmsg("levenshtein argument exceeds maximum length of %d characters",
134+
MAX_LEVENSHTEIN_STRLEN)));
129135

130136
#ifdef LEVENSHTEIN_LESS_EQUAL
131137
/* Initialize start and stop columns. */

‎src/include/utils/builtins.h

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -810,11 +810,14 @@ extern Datum textoverlay_no_len(PG_FUNCTION_ARGS);
810810
extern Datum name_text(PG_FUNCTION_ARGS);
811811
extern Datum text_name(PG_FUNCTION_ARGS);
812812
extern int varstr_cmp(char *arg1, int len1, char *arg2, int len2, Oid collid);
813-
extern int varstr_levenshtein(const char *source, int slen, const char *target,
814-
int tlen, int ins_c, int del_c, int sub_c);
813+
extern int varstr_levenshtein(const char *source, int slen,
814+
const char *target, int tlen,
815+
int ins_c, int del_c, int sub_c,
816+
bool trusted);
815817
extern int varstr_levenshtein_less_equal(const char *source, int slen,
816-
const char *target, int tlen, int ins_c,
817-
int del_c, int sub_c, int max_d);
818+
const char *target, int tlen,
819+
int ins_c, int del_c, int sub_c,
820+
int max_d, bool trusted);
818821
extern List *textToQualifiedNameList(text *textval);
819822
extern bool SplitIdentifierString(char *rawstring, char separator,
820823
List **namelist);

0 commit comments

Comments
 (0)
0