Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita396144

Browse files
committed
Remove new coupling between NAMEDATALEN and MAX_LEVENSHTEIN_STRLEN.
Commite529cd4 introduced an Assert requiring NAMEDATALEN to beless than MAX_LEVENSHTEIN_STRLEN, which has been 255 for a long time.Since up to that instant we had always allowed NAMEDATALEN to besubstantially more than that, this was ill-advised.It's debatable whether we need MAX_LEVENSHTEIN_STRLEN at all (versusputting a CHECK_FOR_INTERRUPTS into the loop), or whether it has to beso tight; but this patch takes the narrower approach of just not applyingthe MAX_LEVENSHTEIN_STRLEN limit to calls from the parser.Trusting the parser for this seems reasonable, first because the stringsare limited to NAMEDATALEN which is unlikely to be hugely more than 256,and second because the maximum distance is tightly constrained byMAX_FUZZY_DISTANCE (though we'd forgotten to make use of that limit in oneplace). 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-charsin comments and error messages.Per gripe from Kevin Day; solution suggested by Robert Haas. Back-patchto 9.5 where the unwanted restriction was introduced.
1 parent647d87c commita396144

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 bytesand 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 bytesand 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 bytesand 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 bytesand 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
#defineMAX_LEVENSHTEIN_STRLEN255
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 tothe bound. From any cell in the matrix, there is
53+
* is less than or equal tomax_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
#ifdefLEVENSHTEIN_LESS_EQUAL
61-
varstr_levenshtein_less_equal(constchar*source,intslen,constchar*target,
62-
inttlen,intins_c,intdel_c,intsub_c,
63-
intmax_d)
68+
varstr_levenshtein_less_equal(constchar*source,intslen,
69+
constchar*target,inttlen,
70+
intins_c,intdel_c,intsub_c,
71+
intmax_d,booltrusted)
6472
#else
65-
varstr_levenshtein(constchar*source,intslen,constchar*target,inttlen,
66-
intins_c,intdel_c,intsub_c)
73+
varstr_levenshtein(constchar*source,intslen,
74+
constchar*target,inttlen,
75+
intins_c,intdel_c,intsub_c,
76+
booltrusted)
6777
#endif
6878
{
6979
intm,
@@ -95,15 +105,7 @@ varstr_levenshtein(const char *source, int slen, const char *target, int tlen,
95105
#defineSTOP_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 exceedsthemaximum length of %dbytes",
128-
MAX_LEVENSHTEIN_STRLEN)));
133+
errmsg("levenshteinargument exceeds maximum length of %dcharacters",
134+
MAX_LEVENSHTEIN_STRLEN)));
129135

130136
#ifdefLEVENSHTEIN_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
externDatumname_text(PG_FUNCTION_ARGS);
811811
externDatumtext_name(PG_FUNCTION_ARGS);
812812
externintvarstr_cmp(char*arg1,intlen1,char*arg2,intlen2,Oidcollid);
813-
externintvarstr_levenshtein(constchar*source,intslen,constchar*target,
814-
inttlen,intins_c,intdel_c,intsub_c);
813+
externintvarstr_levenshtein(constchar*source,intslen,
814+
constchar*target,inttlen,
815+
intins_c,intdel_c,intsub_c,
816+
booltrusted);
815817
externintvarstr_levenshtein_less_equal(constchar*source,intslen,
816-
constchar*target,inttlen,intins_c,
817-
intdel_c,intsub_c,intmax_d);
818+
constchar*target,inttlen,
819+
intins_c,intdel_c,intsub_c,
820+
intmax_d,booltrusted);
818821
externList*textToQualifiedNameList(text*textval);
819822
externboolSplitIdentifierString(char*rawstring,charseparator,
820823
List**namelist);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp