Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * contrib/pg_trgm/trgm_op.c
3 : : */
4 : : #include "postgres.h"
5 : :
6 : : #include <ctype.h>
7 : :
8 : : #include "catalog/pg_collation_d.h"
9 : : #include "catalog/pg_type.h"
10 : : #include "common/int.h"
11 : : #include "lib/qunique.h"
12 : : #include "miscadmin.h"
13 : : #include "trgm.h"
14 : : #include "tsearch/ts_locale.h"
15 : : #include "utils/formatting.h"
16 : : #include "utils/guc.h"
17 : : #include "utils/lsyscache.h"
18 : : #include "utils/memutils.h"
19 : : #include "utils/pg_crc.h"
20 : :
354 tgl@sss.pgh.pa.us 21 :CBC 4 : PG_MODULE_MAGIC_EXT(
22 : : .name = "pg_trgm",
23 : : .version = PG_VERSION
24 : : );
25 : :
26 : : /* GUC variables */
27 : : double similarity_threshold = 0.3f;
28 : : double word_similarity_threshold = 0.6f;
29 : : double strict_word_similarity_threshold = 0.5f;
30 : :
7958 teodor@sigaev.ru 31 : 2 : PG_FUNCTION_INFO_V1(set_limit);
5522 tgl@sss.pgh.pa.us 32 : 2 : PG_FUNCTION_INFO_V1(show_limit);
33 : 2 : PG_FUNCTION_INFO_V1(show_trgm);
34 : 2 : PG_FUNCTION_INFO_V1(similarity);
3651 teodor@sigaev.ru 35 : 2 : PG_FUNCTION_INFO_V1(word_similarity);
2916 36 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity);
5522 tgl@sss.pgh.pa.us 37 : 2 : PG_FUNCTION_INFO_V1(similarity_dist);
38 : 2 : PG_FUNCTION_INFO_V1(similarity_op);
3651 teodor@sigaev.ru 39 : 2 : PG_FUNCTION_INFO_V1(word_similarity_op);
40 : 3 : PG_FUNCTION_INFO_V1(word_similarity_commutator_op);
41 : 1 : PG_FUNCTION_INFO_V1(word_similarity_dist_op);
42 : 2 : PG_FUNCTION_INFO_V1(word_similarity_dist_commutator_op);
2916 43 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity_op);
44 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity_commutator_op);
45 : 1 : PG_FUNCTION_INFO_V1(strict_word_similarity_dist_op);
46 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity_dist_commutator_op);
47 : :
48 : : static int CMPTRGM_CHOOSE(const void *a, const void *b);
49 : : int (*CMPTRGM) (const void *a, const void *b) = CMPTRGM_CHOOSE;
50 : :
51 : : /* Trigram with position */
52 : : typedef struct
53 : : {
54 : : trgm trg;
55 : : int index;
56 : : } pos_trgm;
57 : :
58 : : /* Trigram bound type */
59 : : typedef uint8 TrgmBound;
60 : : #define TRGM_BOUND_LEFT 0x01 /* trigram is left bound of word */
61 : : #define TRGM_BOUND_RIGHT 0x02 /* trigram is right bound of word */
62 : :
63 : : /* Word similarity flags */
64 : : #define WORD_SIMILARITY_CHECK_ONLY 0x01 /* only check existence of similar
65 : : * search pattern in text */
66 : : #define WORD_SIMILARITY_STRICT 0x02 /* force bounds of extent to match
67 : : * word bounds */
68 : :
69 : : /*
70 : : * A growable array of trigrams
71 : : *
72 : : * The actual array of trigrams is in 'datum'. Note that the other fields in
73 : : * 'datum', i.e. datum->flags and the varlena length, are not kept up to date
74 : : * when items are added to the growable array. We merely reserve the space
75 : : * for them here. You must fill those other fields before using 'datum' as a
76 : : * proper TRGM datum.
77 : : */
78 : : typedef struct
79 : : {
80 : : TRGM *datum; /* trigram array */
81 : : int length; /* number of trigrams in the array */
82 : : int allocated; /* allocated size of 'datum' (# of trigrams) */
83 : : } growable_trgm_array;
84 : :
85 : : /*
86 : : * Allocate a new growable array.
87 : : *
88 : : * 'slen' is the size of the source string that we're extracting the trigrams
89 : : * from. It is used to choose the initial size of the array.
90 : : */
91 : : static void
54 heikki.linnakangas@i 92 : 116206 : init_trgm_array(growable_trgm_array *arr, int slen)
93 : : {
94 : : size_t init_size;
95 : :
96 : : /*
97 : : * In the extreme case, the input string consists entirely of one
98 : : * character words, like "a b c", where each word is expanded to two
99 : : * trigrams. This is not a strict upper bound though, because when
100 : : * IGNORECASE is defined, we convert the input string to lowercase before
101 : : * extracting the trigrams, which in rare cases can expand one input
102 : : * character into multiple characters.
103 : : */
104 : 116206 : init_size = (size_t) slen + 1;
105 : :
106 : : /*
107 : : * Guard against possible overflow in the palloc request. (We don't worry
108 : : * about the additive constants, since palloc can detect requests that are
109 : : * a little above MaxAllocSize --- we just need to prevent integer
110 : : * overflow in the multiplications.)
111 : : */
112 [ - + ]: 116206 : if (init_size > MaxAllocSize / sizeof(trgm))
54 heikki.linnakangas@i 113 [ # # ]:UBC 0 : ereport(ERROR,
114 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
115 : : errmsg("out of memory")));
116 : :
54 heikki.linnakangas@i 117 :CBC 116206 : arr->datum = palloc(CALCGTSIZE(ARRKEY, init_size));
118 : 116206 : arr->allocated = init_size;
119 : 116206 : arr->length = 0;
120 : 116206 : }
121 : :
122 : : /* Make sure the array can hold at least 'needed' more trigrams */
123 : : static void
124 : 128429 : enlarge_trgm_array(growable_trgm_array *arr, int needed)
125 : : {
126 : 128429 : size_t new_needed = (size_t) arr->length + needed;
127 : :
128 [ - + ]: 128429 : if (new_needed > arr->allocated)
129 : : {
130 : : /* Guard against possible overflow, like in init_trgm_array */
54 heikki.linnakangas@i 131 [ # # ]:UBC 0 : if (new_needed > MaxAllocSize / sizeof(trgm))
132 [ # # ]: 0 : ereport(ERROR,
133 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
134 : : errmsg("out of memory")));
135 : :
136 : 0 : arr->datum = repalloc(arr->datum, CALCGTSIZE(ARRKEY, new_needed));
137 : 0 : arr->allocated = new_needed;
138 : : }
54 heikki.linnakangas@i 139 :CBC 128429 : }
140 : :
141 : : /*
142 : : * Module load callback
143 : : */
144 : : void
3651 teodor@sigaev.ru 145 : 4 : _PG_init(void)
146 : : {
147 : : /* Define custom GUC variables. */
148 : 4 : DefineCustomRealVariable("pg_trgm.similarity_threshold",
149 : : "Sets the threshold used by the % operator.",
150 : : "Valid range is 0.0 .. 1.0.",
151 : : &similarity_threshold,
152 : : 0.3f,
153 : : 0.0,
154 : : 1.0,
155 : : PGC_USERSET,
156 : : 0,
157 : : NULL,
158 : : NULL,
159 : : NULL);
160 : 4 : DefineCustomRealVariable("pg_trgm.word_similarity_threshold",
161 : : "Sets the threshold used by the <% operator.",
162 : : "Valid range is 0.0 .. 1.0.",
163 : : &word_similarity_threshold,
164 : : 0.6f,
165 : : 0.0,
166 : : 1.0,
167 : : PGC_USERSET,
168 : : 0,
169 : : NULL,
170 : : NULL,
171 : : NULL);
2916 172 : 4 : DefineCustomRealVariable("pg_trgm.strict_word_similarity_threshold",
173 : : "Sets the threshold used by the <<% operator.",
174 : : "Valid range is 0.0 .. 1.0.",
175 : : &strict_word_similarity_threshold,
176 : : 0.5f,
177 : : 0.0,
178 : : 1.0,
179 : : PGC_USERSET,
180 : : 0,
181 : : NULL,
182 : : NULL,
183 : : NULL);
184 : :
1483 tgl@sss.pgh.pa.us 185 : 4 : MarkGUCPrefixReserved("pg_trgm");
3651 teodor@sigaev.ru 186 : 4 : }
187 : :
188 : : #define CMPCHAR(a,b) ( ((a)==(b)) ? 0 : ( ((a)<(b)) ? -1 : 1 ) )
189 : :
190 : : /*
191 : : * Functions for comparing two trgms while treating each char as "signed char" or
192 : : * "unsigned char".
193 : : */
194 : : static inline int
387 msawada@postgresql.o 195 : 7512472 : CMPTRGM_SIGNED(const void *a, const void *b)
196 : : {
197 : : #define CMPPCHAR_S(a,b,i) CMPCHAR( *(((const signed char*)(a))+i), *(((const signed char*)(b))+i) )
198 : :
199 [ + + ]: 5421967 : return CMPPCHAR_S(a, b, 0) ? CMPPCHAR_S(a, b, 0)
200 [ + + + + ]: 16368002 : : (CMPPCHAR_S(a, b, 1) ? CMPPCHAR_S(a, b, 1)
201 [ + + + + : 3433563 : : CMPPCHAR_S(a, b, 2));
+ + ]
202 : : }
203 : :
204 : : static inline int
387 msawada@postgresql.o 205 :UBC 0 : CMPTRGM_UNSIGNED(const void *a, const void *b)
206 : : {
207 : : #define CMPPCHAR_UNS(a,b,i) CMPCHAR( *(((const unsigned char*)(a))+i), *(((const unsigned char*)(b))+i) )
208 : :
209 [ # # ]: 0 : return CMPPCHAR_UNS(a, b, 0) ? CMPPCHAR_UNS(a, b, 0)
210 [ # # # # ]: 0 : : (CMPPCHAR_UNS(a, b, 1) ? CMPPCHAR_UNS(a, b, 1)
211 [ # # # # : 0 : : CMPPCHAR_UNS(a, b, 2));
# # ]
212 : : }
213 : :
214 : : /*
215 : : * This gets called on the first call. It replaces the function pointer so
216 : : * that subsequent calls are routed directly to the chosen implementation.
217 : : */
218 : : static int
387 msawada@postgresql.o 219 :CBC 4 : CMPTRGM_CHOOSE(const void *a, const void *b)
220 : : {
221 [ + - ]: 4 : if (GetDefaultCharSignedness())
222 : 4 : CMPTRGM = CMPTRGM_SIGNED;
223 : : else
387 msawada@postgresql.o 224 :UBC 0 : CMPTRGM = CMPTRGM_UNSIGNED;
225 : :
387 msawada@postgresql.o 226 :CBC 4 : return CMPTRGM(a, b);
227 : : }
228 : :
229 : : /*
230 : : * Deprecated function.
231 : : * Use "pg_trgm.similarity_threshold" GUC variable instead of this function.
232 : : */
233 : : Datum
7868 bruce@momjian.us 234 : 2 : set_limit(PG_FUNCTION_ARGS)
235 : : {
236 : 2 : float4 nlimit = PG_GETARG_FLOAT4(0);
237 : : char *nlimit_str;
238 : : Oid func_out_oid;
239 : : bool is_varlena;
240 : :
3649 teodor@sigaev.ru 241 : 2 : getTypeOutputInfo(FLOAT4OID, &func_out_oid, &is_varlena);
242 : :
243 : 2 : nlimit_str = OidOutputFunctionCall(func_out_oid, Float4GetDatum(nlimit));
244 : :
245 : 2 : SetConfigOption("pg_trgm.similarity_threshold", nlimit_str,
246 : : PGC_USERSET, PGC_S_SESSION);
247 : :
3651 248 : 2 : PG_RETURN_FLOAT4(similarity_threshold);
249 : : }
250 : :
251 : :
252 : : /*
253 : : * Get similarity threshold for given index scan strategy number.
254 : : */
255 : : double
2916 256 : 45437 : index_strategy_get_limit(StrategyNumber strategy)
257 : : {
258 [ + + + - ]: 45437 : switch (strategy)
259 : : {
260 : 32631 : case SimilarityStrategyNumber:
261 : 32631 : return similarity_threshold;
262 : 6828 : case WordSimilarityStrategyNumber:
263 : 6828 : return word_similarity_threshold;
264 : 5978 : case StrictWordSimilarityStrategyNumber:
265 : 5978 : return strict_word_similarity_threshold;
2916 teodor@sigaev.ru 266 :UBC 0 : default:
267 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
268 : : break;
269 : : }
270 : :
271 : : return 0.0; /* keep compiler quiet */
272 : : }
273 : :
274 : : /*
275 : : * Deprecated function.
276 : : * Use "pg_trgm.similarity_threshold" GUC variable instead of this function.
277 : : */
278 : : Datum
7868 bruce@momjian.us 279 :CBC 20000 : show_limit(PG_FUNCTION_ARGS)
280 : : {
3651 teodor@sigaev.ru 281 : 20000 : PG_RETURN_FLOAT4(similarity_threshold);
282 : : }
283 : :
284 : : static int
7868 bruce@momjian.us 285 : 3188693 : comp_trgm(const void *a, const void *b)
286 : : {
287 : 3188693 : return CMPTRGM(a, b);
288 : : }
289 : :
290 : : /*
291 : : * Finds first word in string, returns pointer to the word,
292 : : * endword points to the character after word
293 : : */
294 : : static char *
54 heikki.linnakangas@i 295 : 243532 : find_word(char *str, int lenstr, char **endword)
296 : : {
6121 bruce@momjian.us 297 : 243532 : char *beginword = str;
67 tmunro@postgresql.or 298 : 243532 : const char *endstr = str + lenstr;
299 : :
300 [ + + ]: 257216 : while (beginword < endstr)
301 : : {
302 : 142076 : int clen = pg_mblen_range(beginword, endstr);
303 : :
304 [ + + ]: 142076 : if (ISWORDCHR(beginword, clen))
305 : 128392 : break;
306 : 13684 : beginword += clen;
307 : : }
308 : :
309 [ + + ]: 243532 : if (beginword >= endstr)
6332 teodor@sigaev.ru 310 : 115140 : return NULL;
311 : :
312 : 128392 : *endword = beginword;
67 tmunro@postgresql.or 313 [ + + ]: 1112115 : while (*endword < endstr)
314 : : {
315 : 997069 : int clen = pg_mblen_range(*endword, endstr);
316 : :
317 [ + + ]: 997069 : if (!ISWORDCHR(*endword, clen))
318 : 13346 : break;
319 : 983723 : *endword += clen;
320 : : }
321 : :
6332 teodor@sigaev.ru 322 : 128392 : return beginword;
323 : : }
324 : :
325 : : /*
326 : : * Reduce a trigram (three possibly multi-byte characters) to a trgm,
327 : : * which is always exactly three bytes. If we have three single-byte
328 : : * characters, we just use them as-is; otherwise we form a hash value.
329 : : */
330 : : void
4725 tgl@sss.pgh.pa.us 331 : 1658 : compact_trigram(trgm *tptr, char *str, int bytelen)
332 : : {
6121 bruce@momjian.us 333 [ + + ]: 1658 : if (bytelen == 3)
334 : : {
335 : 1475 : CPTRGM(tptr, str);
336 : : }
337 : : else
338 : : {
339 : : pg_crc32 crc;
340 : :
4149 heikki.linnakangas@i 341 : 183 : INIT_LEGACY_CRC32(crc);
342 [ + + ]: 1340 : COMP_LEGACY_CRC32(crc, str, bytelen);
343 : 183 : FIN_LEGACY_CRC32(crc);
344 : :
345 : : /*
346 : : * use only 3 upper bytes from crc, hope, it's good enough hashing
347 : : */
6332 teodor@sigaev.ru 348 : 183 : CPTRGM(tptr, &crc);
349 : : }
350 : 1658 : }
351 : :
352 : : /*
353 : : * Adds trigrams from the word in 'str' (already padded if necessary).
354 : : */
355 : : static void
54 heikki.linnakangas@i 356 : 128456 : make_trigrams(growable_trgm_array *dst, char *str, int bytelen)
357 : : {
358 : : trgm *tptr;
6121 bruce@momjian.us 359 : 128456 : char *ptr = str;
360 : :
54 heikki.linnakangas@i 361 [ + + ]: 128456 : if (bytelen < 3)
362 : 27 : return;
363 : :
364 : : /* max number of trigrams = strlen - 2 */
365 : 128429 : enlarge_trgm_array(dst, bytelen - 2);
366 : 128429 : tptr = GETARR(dst->datum) + dst->length;
367 : :
368 [ - + ]: 128429 : if (pg_encoding_max_length(GetDatabaseEncoding()) == 1)
369 : : {
54 heikki.linnakangas@i 370 [ # # ]:UBC 0 : while (ptr < str + bytelen - 2)
371 : : {
372 : 0 : CPTRGM(tptr, ptr);
373 : 0 : ptr++;
6332 teodor@sigaev.ru 374 : 0 : tptr++;
375 : : }
376 : : }
377 : : else
378 : : {
379 : : int lenfirst,
380 : : lenmiddle,
381 : : lenlast;
382 : : char *endptr;
383 : :
384 : : /*
385 : : * Fast path as long as there are no multibyte characters
386 : : */
54 heikki.linnakangas@i 387 [ + - + - ]:CBC 128429 : if (!IS_HIGHBIT_SET(ptr[0]) && !IS_HIGHBIT_SET(ptr[1]))
388 : : {
389 [ + + ]: 1112045 : while (!IS_HIGHBIT_SET(ptr[2]))
390 : : {
391 : 1112007 : CPTRGM(tptr, ptr);
392 : 1112007 : ptr++;
393 : 1112007 : tptr++;
394 : :
395 [ + + ]: 1112007 : if (ptr == str + bytelen - 2)
396 : 128391 : goto done;
397 : : }
398 : :
399 : 38 : lenfirst = 1;
400 : 38 : lenmiddle = 1;
67 tmunro@postgresql.or 401 : 38 : lenlast = pg_mblen_unbounded(ptr + 2);
402 : : }
403 : : else
404 : : {
67 tmunro@postgresql.or 405 :UBC 0 : lenfirst = pg_mblen_unbounded(ptr);
54 heikki.linnakangas@i 406 [ # # ]: 0 : if (ptr + lenfirst >= str + bytelen)
407 : 0 : goto done;
67 tmunro@postgresql.or 408 : 0 : lenmiddle = pg_mblen_unbounded(ptr + lenfirst);
54 heikki.linnakangas@i 409 [ # # ]: 0 : if (ptr + lenfirst + lenmiddle >= str + bytelen)
410 : 0 : goto done;
67 tmunro@postgresql.or 411 : 0 : lenlast = pg_mblen_unbounded(ptr + lenfirst + lenmiddle);
412 : : }
413 : :
414 : : /*
415 : : * Slow path to handle any remaining multibyte characters
416 : : *
417 : : * As we go, 'ptr' points to the beginning of the current
418 : : * three-character string and 'endptr' points to just past it.
419 : : */
54 heikki.linnakangas@i 420 :CBC 38 : endptr = ptr + lenfirst + lenmiddle + lenlast;
421 [ + - ]: 199 : while (endptr <= str + bytelen)
422 : : {
423 : 199 : compact_trigram(tptr, ptr, endptr - ptr);
6332 teodor@sigaev.ru 424 : 199 : tptr++;
425 : :
426 : : /* Advance to the next character */
54 heikki.linnakangas@i 427 [ + + ]: 199 : if (endptr == str + bytelen)
428 : 38 : break;
429 : 161 : ptr += lenfirst;
430 : 161 : lenfirst = lenmiddle;
431 : 161 : lenmiddle = lenlast;
67 tmunro@postgresql.or 432 : 161 : lenlast = pg_mblen_unbounded(endptr);
54 heikki.linnakangas@i 433 : 161 : endptr += lenlast;
434 : : }
435 : : }
436 : :
54 heikki.linnakangas@i 437 :UBC 0 : done:
54 heikki.linnakangas@i 438 :CBC 128429 : dst->length = tptr - GETARR(dst->datum);
439 [ - + ]: 128429 : Assert(dst->length <= dst->allocated);
440 : : }
441 : :
442 : : /*
443 : : * Make array of trigrams without sorting and removing duplicate items.
444 : : *
445 : : * dst: where to return the array of trigrams.
446 : : * str: source string, of length slen bytes.
447 : : * bounds_p: where to return bounds of trigrams (if needed).
448 : : */
449 : : static void
450 : 116151 : generate_trgm_only(growable_trgm_array *dst, char *str, int slen, TrgmBound **bounds_p)
451 : : {
452 : : size_t buflen;
453 : : char *buf;
454 : : int bytelen;
455 : : char *bword,
456 : : *eword;
457 : 116151 : TrgmBound *bounds = NULL;
458 : 116151 : int bounds_allocated = 0;
459 : :
460 : 116151 : init_trgm_array(dst, slen);
461 : :
462 : : /*
463 : : * If requested, allocate an array for the bounds, with the same size as
464 : : * the trigram array.
465 : : */
466 [ + + ]: 116151 : if (bounds_p)
467 : : {
468 : 6662 : bounds_allocated = dst->allocated;
469 : 6662 : bounds = *bounds_p = palloc0_array(TrgmBound, bounds_allocated);
470 : : }
471 : :
472 [ + - + + ]: 116151 : if (slen + LPADDING + RPADDING < 3 || slen == 0)
473 : 1011 : return;
474 : :
475 : : /*
476 : : * Allocate a buffer for case-folded, blank-padded words.
477 : : *
478 : : * As an initial guess, allocate a buffer large enough to hold the
479 : : * original string with padding, which is always enough when compiled with
480 : : * !IGNORECASE. If the case-folding produces a string longer than the
481 : : * original, we'll grow the buffer.
482 : : */
483 : 115140 : buflen = (size_t) slen + 4;
484 : 115140 : buf = (char *) palloc(buflen);
485 : : if (LPADDING > 0)
486 : : {
7958 teodor@sigaev.ru 487 : 115140 : *buf = ' ';
488 : : if (LPADDING > 1)
7868 bruce@momjian.us 489 : 115140 : *(buf + 1) = ' ';
490 : : }
491 : :
6332 teodor@sigaev.ru 492 : 115140 : eword = str;
54 heikki.linnakangas@i 493 [ + + ]: 243532 : while ((bword = find_word(eword, slen - (eword - str), &eword)) != NULL)
494 : : {
495 : : int oldlen;
496 : :
497 : : /* Convert word to lower case before extracting trigrams from it */
498 : : #ifdef IGNORECASE
499 : : {
500 : : char *lowered;
501 : :
502 : 128392 : lowered = str_tolower(bword, eword - bword, DEFAULT_COLLATION_OID);
503 : 128392 : bytelen = strlen(lowered);
504 : :
505 : : /* grow the buffer if necessary */
506 [ - + ]: 128392 : if (bytelen > buflen - 4)
507 : : {
54 heikki.linnakangas@i 508 :UBC 0 : pfree(buf);
509 : 0 : buflen = (size_t) bytelen + 4;
510 : 0 : buf = (char *) palloc(buflen);
511 : : if (LPADDING > 0)
512 : : {
513 : 0 : *buf = ' ';
514 : : if (LPADDING > 1)
515 : 0 : *(buf + 1) = ' ';
516 : : }
517 : : }
54 heikki.linnakangas@i 518 :CBC 128392 : memcpy(buf + LPADDING, lowered, bytelen);
519 : 128392 : pfree(lowered);
520 : : }
521 : : #else
522 : : bytelen = eword - bword;
523 : : memcpy(buf + LPADDING, bword, bytelen);
524 : : #endif
525 : :
6121 bruce@momjian.us 526 : 128392 : buf[LPADDING + bytelen] = ' ';
527 : 128392 : buf[LPADDING + bytelen + 1] = ' ';
528 : :
529 : : /* Calculate trigrams marking their bounds if needed */
54 heikki.linnakangas@i 530 : 128392 : oldlen = dst->length;
531 : 128392 : make_trigrams(dst, buf, bytelen + LPADDING + RPADDING);
2916 teodor@sigaev.ru 532 [ + + ]: 128392 : if (bounds)
533 : : {
54 heikki.linnakangas@i 534 [ - + ]: 12398 : if (bounds_allocated < dst->length)
535 : : {
23 heikki.linnakangas@i 536 :UBC 0 : bounds = *bounds_p = repalloc0_array(bounds, TrgmBound, bounds_allocated, dst->allocated);
54 537 : 0 : bounds_allocated = dst->allocated;
538 : : }
539 : :
54 heikki.linnakangas@i 540 :CBC 12398 : bounds[oldlen] |= TRGM_BOUND_LEFT;
541 : 12398 : bounds[dst->length - 1] |= TRGM_BOUND_RIGHT;
542 : : }
543 : : }
544 : :
7958 teodor@sigaev.ru 545 : 115140 : pfree(buf);
546 : : }
547 : :
548 : : /*
549 : : * Make array of trigrams with sorting and removing duplicate items.
550 : : *
551 : : * str: source string, of length slen bytes.
552 : : *
553 : : * Returns the sorted array of unique trigrams.
554 : : */
555 : : TRGM *
3651 556 : 89895 : generate_trgm(char *str, int slen)
557 : : {
558 : : TRGM *trg;
559 : : growable_trgm_array arr;
560 : : int len;
561 : :
54 heikki.linnakangas@i 562 : 89895 : generate_trgm_only(&arr, str, slen, NULL);
563 : 89895 : len = arr.length;
564 : 89895 : trg = arr.datum;
3651 teodor@sigaev.ru 565 : 89895 : trg->flag = ARRKEY;
566 : :
567 : : /*
568 : : * Make trigrams unique.
569 : : */
4444 tgl@sss.pgh.pa.us 570 [ + + ]: 89895 : if (len > 1)
571 : : {
1132 peter@eisentraut.org 572 : 89883 : qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
2320 tmunro@postgresql.or 573 : 89883 : len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
574 : : }
575 : :
6955 tgl@sss.pgh.pa.us 576 : 89895 : SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
577 : :
7958 teodor@sigaev.ru 578 : 89895 : return trg;
579 : : }
580 : :
581 : : /*
582 : : * Make array of positional trigrams from two trigram arrays trg1 and trg2.
583 : : *
584 : : * trg1: trigram array of search pattern, of length len1. trg1 is required
585 : : * word which positions don't matter and replaced with -1.
586 : : * trg2: trigram array of text, of length len2. trg2 is haystack where we
587 : : * search and have to store its positions.
588 : : *
589 : : * Returns concatenated trigram array.
590 : : */
591 : : static pos_trgm *
3651 592 : 13128 : make_positional_trgm(trgm *trg1, int len1, trgm *trg2, int len2)
593 : : {
594 : : pos_trgm *result;
595 : : int i,
3566 rhaas@postgresql.org 596 : 13128 : len = len1 + len2;
597 : :
94 michael@paquier.xyz 598 :GNC 13128 : result = palloc_array(pos_trgm, len);
599 : :
3651 teodor@sigaev.ru 600 [ + + ]:CBC 121866 : for (i = 0; i < len1; i++)
601 : : {
602 : 108738 : memcpy(&result[i].trg, &trg1[i], sizeof(trgm));
603 : 108738 : result[i].index = -1;
604 : : }
605 : :
606 [ + + ]: 205226 : for (i = 0; i < len2; i++)
607 : : {
608 : 192098 : memcpy(&result[i + len1].trg, &trg2[i], sizeof(trgm));
609 : 192098 : result[i + len1].index = i;
610 : : }
611 : :
612 : 13128 : return result;
613 : : }
614 : :
615 : : /*
616 : : * Compare position trigrams: compare trigrams first and position second.
617 : : */
618 : : static int
619 : 1351335 : comp_ptrgm(const void *v1, const void *v2)
620 : : {
3566 rhaas@postgresql.org 621 : 1351335 : const pos_trgm *p1 = (const pos_trgm *) v1;
622 : 1351335 : const pos_trgm *p2 = (const pos_trgm *) v2;
623 : : int cmp;
624 : :
3651 teodor@sigaev.ru 625 : 1351335 : cmp = CMPTRGM(p1->trg, p2->trg);
626 [ + + ]: 1351335 : if (cmp != 0)
627 : 1311631 : return cmp;
628 : :
758 nathan@postgresql.or 629 : 39704 : return pg_cmp_s32(p1->index, p2->index);
630 : : }
631 : :
632 : : /*
633 : : * Iterative search function which calculates maximum similarity with word in
634 : : * the string. Maximum similarity is only calculated only if the flag
635 : : * WORD_SIMILARITY_CHECK_ONLY isn't set.
636 : : *
637 : : * trg2indexes: array which stores indexes of the array "found".
638 : : * found: array which stores true of false values.
639 : : * ulen1: count of unique trigrams of array "trg1".
640 : : * len2: length of array "trg2" and array "trg2indexes".
641 : : * len: length of the array "found".
642 : : * flags: set of boolean flags parameterizing similarity calculation.
643 : : * bounds: whether each trigram is left/right bound of word.
644 : : *
645 : : * Returns word similarity.
646 : : */
647 : : static float4
3651 teodor@sigaev.ru 648 : 13128 : iterate_word_similarity(int *trg2indexes,
649 : : bool *found,
650 : : int ulen1,
651 : : int len2,
652 : : int len,
653 : : uint8 flags,
654 : : TrgmBound *bounds)
655 : : {
656 : : int *lastpos,
657 : : i,
658 : 13128 : ulen2 = 0,
659 : 13128 : count = 0,
660 : 13128 : upper = -1,
661 : : lower;
662 : : float4 smlr_cur,
663 : 13128 : smlr_max = 0.0f;
664 : : double threshold;
665 : :
2916 666 [ + + - + ]: 13128 : Assert(bounds || !(flags & WORD_SIMILARITY_STRICT));
667 : :
668 : : /* Select appropriate threshold */
669 : 26256 : threshold = (flags & WORD_SIMILARITY_STRICT) ?
2880 tgl@sss.pgh.pa.us 670 [ + + ]: 13128 : strict_word_similarity_threshold :
671 : : word_similarity_threshold;
672 : :
673 : : /*
674 : : * Consider first trigram as initial lower bound for strict word
675 : : * similarity, or initialize it later with first trigram present for plain
676 : : * word similarity.
677 : : */
2916 teodor@sigaev.ru 678 [ + + ]: 13128 : lower = (flags & WORD_SIMILARITY_STRICT) ? 0 : -1;
679 : :
680 : : /* Memorise last position of each trigram */
94 michael@paquier.xyz 681 :GNC 13128 : lastpos = palloc_array(int, len);
3651 teodor@sigaev.ru 682 :CBC 13128 : memset(lastpos, -1, sizeof(int) * len);
683 : :
684 [ + + ]: 196656 : for (i = 0; i < len2; i++)
685 : : {
686 : : int trgindex;
687 : :
1287 dgustafsson@postgres 688 [ - + ]: 185312 : CHECK_FOR_INTERRUPTS();
689 : :
690 : : /* Get index of next trigram */
691 : 185312 : trgindex = trg2indexes[i];
692 : :
693 : : /* Update last position of this trigram */
3651 teodor@sigaev.ru 694 [ + + + + ]: 185312 : if (lower >= 0 || found[trgindex])
695 : : {
696 [ + + ]: 135783 : if (lastpos[trgindex] < 0)
697 : : {
698 : 133931 : ulen2++;
699 [ + + ]: 133931 : if (found[trgindex])
700 : 30756 : count++;
701 : : }
702 : 135783 : lastpos[trgindex] = i;
703 : : }
704 : :
705 : : /*
706 : : * Adjust upper bound if trigram is upper bound of word for strict
707 : : * word similarity, or if trigram is present in required substring for
708 : : * plain word similarity
709 : : */
2916 710 [ + + + + ]: 274369 : if ((flags & WORD_SIMILARITY_STRICT) ? (bounds[i] & TRGM_BOUND_RIGHT)
2880 tgl@sss.pgh.pa.us 711 : 89057 : : found[trgindex])
712 : : {
713 : : int prev_lower,
714 : : tmp_ulen2,
715 : : tmp_lower,
716 : : tmp_count;
717 : :
3651 teodor@sigaev.ru 718 : 25635 : upper = i;
719 [ + + ]: 25635 : if (lower == -1)
720 : : {
721 : 4695 : lower = i;
722 : 4695 : ulen2 = 1;
723 : : }
724 : :
725 : 25635 : smlr_cur = CALCSML(count, ulen1, ulen2);
726 : :
727 : : /* Also try to adjust lower bound for greater similarity */
728 : 25635 : tmp_count = count;
729 : 25635 : tmp_ulen2 = ulen2;
730 : 25635 : prev_lower = lower;
731 [ + + ]: 208575 : for (tmp_lower = lower; tmp_lower <= upper; tmp_lower++)
732 : : {
733 : : float smlr_tmp;
734 : : int tmp_trgindex;
735 : :
736 : : /*
737 : : * Adjust lower bound only if trigram is lower bound of word
738 : : * for strict word similarity, or consider every trigram as
739 : : * lower bound for plain word similarity.
740 : : */
2916 741 [ + + ]: 184724 : if (!(flags & WORD_SIMILARITY_STRICT)
742 [ + + ]: 145167 : || (bounds[tmp_lower] & TRGM_BOUND_LEFT))
743 : : {
744 : 59689 : smlr_tmp = CALCSML(tmp_count, ulen1, tmp_ulen2);
745 [ + + ]: 59689 : if (smlr_tmp > smlr_cur)
746 : : {
747 : 3511 : smlr_cur = smlr_tmp;
748 : 3511 : ulen2 = tmp_ulen2;
749 : 3511 : lower = tmp_lower;
750 : 3511 : count = tmp_count;
751 : : }
752 : :
753 : : /*
754 : : * If we only check that word similarity is greater than
755 : : * threshold we do not need to calculate a maximum
756 : : * similarity.
757 : : */
758 [ + + ]: 59689 : if ((flags & WORD_SIMILARITY_CHECK_ONLY)
759 [ + + ]: 37114 : && smlr_cur >= threshold)
760 : 1784 : break;
761 : : }
762 : :
3651 763 : 182940 : tmp_trgindex = trg2indexes[tmp_lower];
764 [ + + ]: 182940 : if (lastpos[tmp_trgindex] == tmp_lower)
765 : : {
766 : 180681 : tmp_ulen2--;
767 [ + + ]: 180681 : if (found[tmp_trgindex])
768 : 46578 : tmp_count--;
769 : : }
770 : : }
771 : :
772 [ + + ]: 25635 : smlr_max = Max(smlr_max, smlr_cur);
773 : :
774 : : /*
775 : : * if we only check that word similarity is greater than threshold
776 : : * we do not need to calculate a maximum similarity.
777 : : */
2916 778 [ + + + + ]: 25635 : if ((flags & WORD_SIMILARITY_CHECK_ONLY) && smlr_max >= threshold)
3651 779 : 1784 : break;
780 : :
781 [ + + ]: 40599 : for (tmp_lower = prev_lower; tmp_lower < lower; tmp_lower++)
782 : : {
783 : : int tmp_trgindex;
784 : :
785 : 16748 : tmp_trgindex = trg2indexes[tmp_lower];
786 [ + + ]: 16748 : if (lastpos[tmp_trgindex] == tmp_lower)
787 : 16000 : lastpos[tmp_trgindex] = -1;
788 : : }
789 : : }
790 : : }
791 : :
792 : 13128 : pfree(lastpos);
793 : :
794 : 13128 : return smlr_max;
795 : : }
796 : :
797 : : /*
798 : : * Calculate word similarity.
799 : : * This function prepare two arrays: "trg2indexes" and "found". Then this arrays
800 : : * are used to calculate word similarity using iterate_word_similarity().
801 : : *
802 : : * "trg2indexes" is array which stores indexes of the array "found".
803 : : * In other words:
804 : : * trg2indexes[j] = i;
805 : : * found[i] = true (or false);
806 : : * If found[i] == true then there is trigram trg2[j] in array "trg1".
807 : : * If found[i] == false then there is not trigram trg2[j] in array "trg1".
808 : : *
809 : : * str1: search pattern string, of length slen1 bytes.
810 : : * str2: text in which we are looking for a word, of length slen2 bytes.
811 : : * flags: set of boolean flags parameterizing similarity calculation.
812 : : *
813 : : * Returns word similarity.
814 : : */
815 : : static float4
816 : 13128 : calc_word_similarity(char *str1, int slen1, char *str2, int slen2,
817 : : uint8 flags)
818 : : {
819 : : bool *found;
820 : : pos_trgm *ptrg;
821 : : growable_trgm_array trg1;
822 : : growable_trgm_array trg2;
823 : : int len1,
824 : : len2,
825 : : len,
826 : : i,
827 : : j,
828 : : ulen1;
829 : : int *trg2indexes;
830 : : float4 result;
54 heikki.linnakangas@i 831 : 13128 : TrgmBound *bounds = NULL;
832 : :
833 : : /* Make positional trigrams */
834 : :
835 : 13128 : generate_trgm_only(&trg1, str1, slen1, NULL);
836 : 13128 : len1 = trg1.length;
837 [ + + ]: 13128 : generate_trgm_only(&trg2, str2, slen2, (flags & WORD_SIMILARITY_STRICT) ? &bounds : NULL);
838 : 13128 : len2 = trg2.length;
839 : :
840 : 13128 : ptrg = make_positional_trgm(GETARR(trg1.datum), len1, GETARR(trg2.datum), len2);
3651 teodor@sigaev.ru 841 : 13128 : len = len1 + len2;
842 : 13128 : qsort(ptrg, len, sizeof(pos_trgm), comp_ptrgm);
843 : :
54 heikki.linnakangas@i 844 : 13128 : pfree(trg1.datum);
845 : 13128 : pfree(trg2.datum);
846 : :
847 : : /*
848 : : * Merge positional trigrams array: enumerate each trigram and find its
849 : : * presence in required word.
850 : : */
94 michael@paquier.xyz 851 :GNC 13128 : trg2indexes = palloc_array(int, len2);
852 : 13128 : found = palloc0_array(bool, len);
853 : :
3651 teodor@sigaev.ru 854 :CBC 13128 : ulen1 = 0;
855 : 13128 : j = 0;
856 [ + + ]: 313964 : for (i = 0; i < len; i++)
857 : : {
858 [ + + ]: 300836 : if (i > 0)
859 : : {
3566 rhaas@postgresql.org 860 : 287708 : int cmp = CMPTRGM(ptrg[i - 1].trg, ptrg[i].trg);
861 : :
3651 teodor@sigaev.ru 862 [ + + ]: 287708 : if (cmp != 0)
863 : : {
864 [ + + ]: 253508 : if (found[j])
865 : 101137 : ulen1++;
866 : 253508 : j++;
867 : : }
868 : : }
869 : :
870 [ + + ]: 300836 : if (ptrg[i].index >= 0)
871 : : {
872 : 192098 : trg2indexes[ptrg[i].index] = j;
873 : : }
874 : : else
875 : : {
876 : 108738 : found[j] = true;
877 : : }
878 : : }
879 [ + + ]: 13128 : if (found[j])
880 : 7601 : ulen1++;
881 : :
882 : : /* Run iterative procedure to find maximum similarity with word */
883 : 13128 : result = iterate_word_similarity(trg2indexes, found, ulen1, len2, len,
884 : : flags, bounds);
885 : :
886 : 13128 : pfree(trg2indexes);
887 : 13128 : pfree(found);
888 : 13128 : pfree(ptrg);
889 : :
890 : 13128 : return result;
891 : : }
892 : :
893 : :
894 : : /*
895 : : * Extract the next non-wildcard part of a search string, i.e. a word bounded
896 : : * by '_' or '%' meta-characters, non-word characters or string end.
897 : : *
898 : : * str: source string, of length lenstr bytes (need not be null-terminated)
899 : : * buf: where to return the substring (must be long enough)
900 : : * *bytelen: receives byte length of the found substring
901 : : *
902 : : * Returns pointer to end+1 of the found substring in the source string.
903 : : * Returns NULL if no word found (in which case buf, bytelen is not set)
904 : : *
905 : : * If the found word is bounded by non-word characters or string boundaries
906 : : * then this function will include corresponding padding spaces into buf.
907 : : */
908 : : static const char *
5522 tgl@sss.pgh.pa.us 909 : 119 : get_wildcard_part(const char *str, int lenstr,
910 : : char *buf, int *bytelen)
911 : : {
912 : 119 : const char *beginword = str;
913 : : const char *endword;
67 tmunro@postgresql.or 914 : 119 : const char *endstr = str + lenstr;
5522 tgl@sss.pgh.pa.us 915 : 119 : char *s = buf;
4955 916 : 119 : bool in_leading_wildcard_meta = false;
917 : 119 : bool in_trailing_wildcard_meta = false;
5453 bruce@momjian.us 918 : 119 : bool in_escape = false;
919 : : int clen;
920 : :
921 : : /*
922 : : * Find the first word character, remembering whether preceding character
923 : : * was wildcard meta-character. Note that the in_escape state persists
924 : : * from this loop to the next one, since we may exit at a word character
925 : : * that is in_escape.
926 : : */
67 tmunro@postgresql.or 927 [ + + ]: 241 : while (beginword < endstr)
928 : : {
929 : 186 : clen = pg_mblen_range(beginword, endstr);
930 : :
5522 tgl@sss.pgh.pa.us 931 [ + + ]: 186 : if (in_escape)
932 : : {
67 tmunro@postgresql.or 933 [ + - ]: 3 : if (ISWORDCHR(beginword, clen))
5522 tgl@sss.pgh.pa.us 934 : 3 : break;
4955 tgl@sss.pgh.pa.us 935 :UBC 0 : in_escape = false;
936 : 0 : in_leading_wildcard_meta = false;
937 : : }
938 : : else
939 : : {
5522 tgl@sss.pgh.pa.us 940 [ + + ]:CBC 183 : if (ISESCAPECHAR(beginword))
941 : 3 : in_escape = true;
942 [ + - + + ]: 180 : else if (ISWILDCARDCHAR(beginword))
4955 943 : 104 : in_leading_wildcard_meta = true;
67 tmunro@postgresql.or 944 [ + + ]: 76 : else if (ISWORDCHR(beginword, clen))
5522 tgl@sss.pgh.pa.us 945 : 61 : break;
946 : : else
4955 947 : 15 : in_leading_wildcard_meta = false;
948 : : }
67 tmunro@postgresql.or 949 : 122 : beginword += clen;
950 : : }
951 : :
952 : : /*
953 : : * Handle string end.
954 : : */
5522 tgl@sss.pgh.pa.us 955 [ + + ]: 119 : if (beginword - str >= lenstr)
956 : 55 : return NULL;
957 : :
958 : : /*
959 : : * Add left padding spaces if preceding character wasn't wildcard
960 : : * meta-character.
961 : : */
4955 962 [ + + ]: 64 : if (!in_leading_wildcard_meta)
963 : : {
964 : : if (LPADDING > 0)
965 : : {
5522 966 : 15 : *s++ = ' ';
967 : : if (LPADDING > 1)
968 : 15 : *s++ = ' ';
969 : : }
970 : : }
971 : :
972 : : /*
973 : : * Copy data into buf until wildcard meta-character, non-word character or
974 : : * string boundary. Strip escapes during copy.
975 : : */
976 : 64 : endword = beginword;
67 tmunro@postgresql.or 977 [ + - ]: 244 : while (endword < endstr)
978 : : {
979 : 244 : clen = pg_mblen_range(endword, endstr);
5522 tgl@sss.pgh.pa.us 980 [ + + ]: 244 : if (in_escape)
981 : : {
67 tmunro@postgresql.or 982 [ + - ]: 3 : if (ISWORDCHR(endword, clen))
983 : : {
5522 tgl@sss.pgh.pa.us 984 : 3 : memcpy(s, endword, clen);
985 : 3 : s += clen;
986 : : }
987 : : else
988 : : {
989 : : /*
990 : : * Back up endword to the escape character when stopping at an
991 : : * escaped char, so that subsequent get_wildcard_part will
992 : : * restart from the escape character. We assume here that
993 : : * escape chars are single-byte.
994 : : */
4955 tgl@sss.pgh.pa.us 995 :UBC 0 : endword--;
5522 996 : 0 : break;
997 : : }
4955 tgl@sss.pgh.pa.us 998 :CBC 3 : in_escape = false;
999 : : }
1000 : : else
1001 : : {
5522 1002 [ - + ]: 241 : if (ISESCAPECHAR(endword))
5522 tgl@sss.pgh.pa.us 1003 :UBC 0 : in_escape = true;
5522 tgl@sss.pgh.pa.us 1004 [ + - + + ]:CBC 241 : else if (ISWILDCARDCHAR(endword))
1005 : : {
4955 1006 : 55 : in_trailing_wildcard_meta = true;
5522 1007 : 55 : break;
1008 : : }
67 tmunro@postgresql.or 1009 [ + + ]: 186 : else if (ISWORDCHR(endword, clen))
1010 : : {
5522 tgl@sss.pgh.pa.us 1011 : 177 : memcpy(s, endword, clen);
1012 : 177 : s += clen;
1013 : : }
1014 : : else
1015 : 9 : break;
1016 : : }
1017 : 180 : endword += clen;
1018 : : }
1019 : :
1020 : : /*
1021 : : * Add right padding spaces if next character isn't wildcard
1022 : : * meta-character.
1023 : : */
4955 1024 [ + + ]: 64 : if (!in_trailing_wildcard_meta)
1025 : : {
1026 : : if (RPADDING > 0)
1027 : : {
5522 1028 : 9 : *s++ = ' ';
1029 : : if (RPADDING > 1)
1030 : : *s++ = ' ';
1031 : : }
1032 : : }
1033 : :
1034 : 64 : *bytelen = s - buf;
1035 : 64 : return endword;
1036 : : }
1037 : :
1038 : : /*
1039 : : * Generates trigrams for wildcard search string.
1040 : : *
1041 : : * Returns array of trigrams that must occur in any string that matches the
1042 : : * wildcard string. For example, given pattern "a%bcd%" the trigrams
1043 : : * " a", "bcd" would be extracted.
1044 : : */
1045 : : TRGM *
1046 : 55 : generate_wildcard_trgm(const char *str, int slen)
1047 : : {
1048 : : TRGM *trg;
1049 : : growable_trgm_array arr;
1050 : : char *buf;
1051 : : int len,
1052 : : bytelen;
1053 : : const char *eword;
1054 : :
1055 [ + - - + ]: 55 : if (slen + LPADDING + RPADDING < 3 || slen == 0)
1056 : : {
54 heikki.linnakangas@i 1057 :UBC 0 : trg = (TRGM *) palloc(TRGMHDRSIZE);
1058 : 0 : trg->flag = ARRKEY;
1059 : 0 : SET_VARSIZE(trg, TRGMHDRSIZE);
5522 tgl@sss.pgh.pa.us 1060 : 0 : return trg;
1061 : : }
1062 : :
54 heikki.linnakangas@i 1063 :CBC 55 : init_trgm_array(&arr, slen);
1064 : :
1065 : : /* Allocate a buffer for blank-padded, but not yet case-folded, words */
94 michael@paquier.xyz 1066 :GNC 55 : buf = palloc_array(char, slen + 4);
1067 : :
1068 : : /*
1069 : : * Extract trigrams from each substring extracted by get_wildcard_part.
1070 : : */
5522 tgl@sss.pgh.pa.us 1071 :CBC 55 : eword = str;
1072 : 119 : while ((eword = get_wildcard_part(eword, slen - (eword - str),
54 heikki.linnakangas@i 1073 [ + + ]: 119 : buf, &bytelen)) != NULL)
1074 : : {
1075 : : char *word;
1076 : :
1077 : : #ifdef IGNORECASE
1078 : 64 : word = str_tolower(buf, bytelen, DEFAULT_COLLATION_OID);
1079 : 64 : bytelen = strlen(word);
1080 : : #else
1081 : : word = buf;
1082 : : #endif
1083 : :
1084 : : /*
1085 : : * count trigrams
1086 : : */
1087 : 64 : make_trigrams(&arr, word, bytelen);
1088 : :
1089 : : #ifdef IGNORECASE
1090 : 64 : pfree(word);
1091 : : #endif
1092 : : }
1093 : :
5522 tgl@sss.pgh.pa.us 1094 : 55 : pfree(buf);
1095 : :
1096 : : /*
1097 : : * Make trigrams unique.
1098 : : */
54 heikki.linnakangas@i 1099 : 55 : trg = arr.datum;
1100 : 55 : len = arr.length;
4444 tgl@sss.pgh.pa.us 1101 [ + + ]: 55 : if (len > 1)
1102 : : {
1132 peter@eisentraut.org 1103 : 17 : qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
2320 tmunro@postgresql.or 1104 : 17 : len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
1105 : : }
1106 : :
54 heikki.linnakangas@i 1107 : 55 : trg->flag = ARRKEY;
5522 tgl@sss.pgh.pa.us 1108 : 55 : SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
1109 : :
1110 : 55 : return trg;
1111 : : }
1112 : :
1113 : : uint32
6332 teodor@sigaev.ru 1114 : 34829 : trgm2int(trgm *ptr)
1115 : : {
6121 bruce@momjian.us 1116 : 34829 : uint32 val = 0;
1117 : :
1118 : 34829 : val |= *(((unsigned char *) ptr));
6332 teodor@sigaev.ru 1119 : 34829 : val <<= 8;
6121 bruce@momjian.us 1120 : 34829 : val |= *(((unsigned char *) ptr) + 1);
6332 teodor@sigaev.ru 1121 : 34829 : val <<= 8;
6121 bruce@momjian.us 1122 : 34829 : val |= *(((unsigned char *) ptr) + 2);
1123 : :
6332 teodor@sigaev.ru 1124 : 34829 : return val;
1125 : : }
1126 : :
1127 : : Datum
7868 bruce@momjian.us 1128 : 7 : show_trgm(PG_FUNCTION_ARGS)
1129 : : {
3290 noah@leadboat.com 1130 : 7 : text *in = PG_GETARG_TEXT_PP(0);
1131 : : TRGM *trg;
1132 : : Datum *d;
1133 : : ArrayType *a;
1134 : : trgm *ptr;
1135 : : int i;
1136 : :
1137 [ - + - - : 7 : trg = generate_trgm(VARDATA_ANY(in), VARSIZE_ANY_EXHDR(in));
- - - - -
+ - + ]
94 michael@paquier.xyz 1138 :GNC 7 : d = palloc_array(Datum, 1 + ARRNELEM(trg));
1139 : :
6821 tgl@sss.pgh.pa.us 1140 [ + + ]:CBC 44 : for (i = 0, ptr = GETARR(trg); i < ARRNELEM(trg); i++, ptr++)
1141 : : {
6121 bruce@momjian.us 1142 [ + - ]: 37 : text *item = (text *) palloc(VARHDRSZ + Max(12, pg_database_encoding_max_length() * 3));
1143 : :
1144 [ + - + - : 37 : if (pg_database_encoding_max_length() > 1 && !ISPRINTABLETRGM(ptr))
+ + + - +
- + + + -
+ - + + -
+ ]
1145 : : {
6332 teodor@sigaev.ru 1146 :UBC 0 : snprintf(VARDATA(item), 12, "0x%06x", trgm2int(ptr));
1147 : 0 : SET_VARSIZE(item, VARHDRSZ + strlen(VARDATA(item)));
1148 : : }
1149 : : else
1150 : : {
6332 teodor@sigaev.ru 1151 :CBC 37 : SET_VARSIZE(item, VARHDRSZ + 3);
1152 : 37 : CPTRGM(VARDATA(item), ptr);
1153 : : }
6821 tgl@sss.pgh.pa.us 1154 : 37 : d[i] = PointerGetDatum(item);
1155 : : }
1156 : :
1353 peter@eisentraut.org 1157 : 7 : a = construct_array_builtin(d, ARRNELEM(trg), TEXTOID);
1158 : :
6821 tgl@sss.pgh.pa.us 1159 [ + + ]: 44 : for (i = 0; i < ARRNELEM(trg); i++)
1160 : 37 : pfree(DatumGetPointer(d[i]));
1161 : :
7958 teodor@sigaev.ru 1162 : 7 : pfree(d);
1163 : 7 : pfree(trg);
7868 bruce@momjian.us 1164 [ - + ]: 7 : PG_FREE_IF_COPY(in, 0);
1165 : :
7958 teodor@sigaev.ru 1166 : 7 : PG_RETURN_POINTER(a);
1167 : : }
1168 : :
1169 : : float4
3651 1170 : 68910 : cnt_sml(TRGM *trg1, TRGM *trg2, bool inexact)
1171 : : {
1172 : : trgm *ptr1,
1173 : : *ptr2;
7868 bruce@momjian.us 1174 : 68910 : int count = 0;
1175 : : int len1,
1176 : : len2;
1177 : :
7958 teodor@sigaev.ru 1178 : 68910 : ptr1 = GETARR(trg1);
1179 : 68910 : ptr2 = GETARR(trg2);
1180 : :
1181 : 68910 : len1 = ARRNELEM(trg1);
1182 : 68910 : len2 = ARRNELEM(trg2);
1183 : :
1184 : : /* explicit test is needed to avoid 0/0 division when both lengths are 0 */
4778 tgl@sss.pgh.pa.us 1185 [ + + - + ]: 68910 : if (len1 <= 0 || len2 <= 0)
1186 : 1 : return (float4) 0.0;
1187 : :
7868 bruce@momjian.us 1188 [ + + + + ]: 876764 : while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
1189 : : {
1190 : 807855 : int res = CMPTRGM(ptr1, ptr2);
1191 : :
1192 [ + + ]: 807855 : if (res < 0)
7958 teodor@sigaev.ru 1193 : 183038 : ptr1++;
7868 bruce@momjian.us 1194 [ + + ]: 624817 : else if (res > 0)
7958 teodor@sigaev.ru 1195 : 214100 : ptr2++;
1196 : : else
1197 : : {
1198 : 410717 : ptr1++;
1199 : 410717 : ptr2++;
1200 : 410717 : count++;
1201 : : }
1202 : : }
1203 : :
1204 : : /*
1205 : : * If inexact then len2 is equal to count, because we don't know actual
1206 : : * length of second string in inexact search and we can assume that count
1207 : : * is a lower bound of len2.
1208 : : */
3651 1209 [ + + ]: 68909 : return CALCSML(count, len1, inexact ? count : len2);
1210 : : }
1211 : :
1212 : :
1213 : : /*
1214 : : * Returns whether trg2 contains all trigrams in trg1.
1215 : : * This relies on the trigram arrays being sorted.
1216 : : */
1217 : : bool
5522 tgl@sss.pgh.pa.us 1218 : 190 : trgm_contained_by(TRGM *trg1, TRGM *trg2)
1219 : : {
1220 : : trgm *ptr1,
1221 : : *ptr2;
1222 : : int len1,
1223 : : len2;
1224 : :
1225 : 190 : ptr1 = GETARR(trg1);
1226 : 190 : ptr2 = GETARR(trg2);
1227 : :
1228 : 190 : len1 = ARRNELEM(trg1);
1229 : 190 : len2 = ARRNELEM(trg2);
1230 : :
1231 [ + + + + ]: 622 : while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
1232 : : {
1233 : 599 : int res = CMPTRGM(ptr1, ptr2);
1234 : :
1235 [ + + ]: 599 : if (res < 0)
1236 : 167 : return false;
1237 [ + + ]: 432 : else if (res > 0)
1238 : 320 : ptr2++;
1239 : : else
1240 : : {
1241 : 112 : ptr1++;
1242 : 112 : ptr2++;
1243 : : }
1244 : : }
1245 [ + + ]: 23 : if (ptr1 - GETARR(trg1) < len1)
1246 : 4 : return false;
1247 : : else
1248 : 19 : return true;
1249 : : }
1250 : :
1251 : : /*
1252 : : * Return a palloc'd boolean array showing, for each trigram in "query",
1253 : : * whether it is present in the trigram array "key".
1254 : : * This relies on the "key" array being sorted, but "query" need not be.
1255 : : */
1256 : : bool *
4722 1257 : 2150 : trgm_presence_map(TRGM *query, TRGM *key)
1258 : : {
1259 : : bool *result;
1260 : 2150 : trgm *ptrq = GETARR(query),
1261 : 2150 : *ptrk = GETARR(key);
1262 : 2150 : int lenq = ARRNELEM(query),
1263 : 2150 : lenk = ARRNELEM(key),
1264 : : i;
1265 : :
94 michael@paquier.xyz 1266 :GNC 2150 : result = palloc0_array(bool, lenq);
1267 : :
1268 : : /* for each query trigram, do a binary search in the key array */
4722 tgl@sss.pgh.pa.us 1269 [ + + ]:CBC 507560 : for (i = 0; i < lenq; i++)
1270 : : {
1271 : 505410 : int lo = 0;
1272 : 505410 : int hi = lenk;
1273 : :
1274 [ + + ]: 2373653 : while (lo < hi)
1275 : : {
1276 : 1876282 : int mid = (lo + hi) / 2;
1277 : 1876282 : int res = CMPTRGM(ptrq, ptrk + mid);
1278 : :
1279 [ + + ]: 1876282 : if (res < 0)
1280 : 784082 : hi = mid;
1281 [ + + ]: 1092200 : else if (res > 0)
1282 : 1084161 : lo = mid + 1;
1283 : : else
1284 : : {
1285 : 8039 : result[i] = true;
1286 : 8039 : break;
1287 : : }
1288 : : }
1289 : 505410 : ptrq++;
1290 : : }
1291 : :
1292 : 2150 : return result;
1293 : : }
1294 : :
1295 : : Datum
7868 bruce@momjian.us 1296 : 31452 : similarity(PG_FUNCTION_ARGS)
1297 : : {
3290 noah@leadboat.com 1298 : 31452 : text *in1 = PG_GETARG_TEXT_PP(0);
1299 : 31452 : text *in2 = PG_GETARG_TEXT_PP(1);
1300 : : TRGM *trg1,
1301 : : *trg2;
1302 : : float4 res;
1303 : :
1304 [ - + - - : 31452 : trg1 = generate_trgm(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1));
- - - - +
+ + + ]
1305 [ - + - - : 31452 : trg2 = generate_trgm(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2));
- - - - -
+ - + ]
1306 : :
3651 teodor@sigaev.ru 1307 : 31452 : res = cnt_sml(trg1, trg2, false);
1308 : :
7958 1309 : 31452 : pfree(trg1);
1310 : 31452 : pfree(trg2);
7868 bruce@momjian.us 1311 [ - + ]: 31452 : PG_FREE_IF_COPY(in1, 0);
1312 [ - + ]: 31452 : PG_FREE_IF_COPY(in2, 1);
1313 : :
7958 teodor@sigaev.ru 1314 : 31452 : PG_RETURN_FLOAT4(res);
1315 : : }
1316 : :
1317 : : Datum
3651 1318 : 902 : word_similarity(PG_FUNCTION_ARGS)
1319 : : {
1320 : 902 : text *in1 = PG_GETARG_TEXT_PP(0);
1321 : 902 : text *in2 = PG_GETARG_TEXT_PP(1);
1322 : : float4 res;
1323 : :
1324 [ - + - - : 902 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
3566 rhaas@postgresql.org 1325 [ - + - - : 902 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1326 : : 0);
1327 : :
2916 teodor@sigaev.ru 1328 [ - + ]: 902 : PG_FREE_IF_COPY(in1, 0);
1329 [ - + ]: 902 : PG_FREE_IF_COPY(in2, 1);
1330 : 902 : PG_RETURN_FLOAT4(res);
1331 : : }
1332 : :
1333 : : Datum
1334 : 882 : strict_word_similarity(PG_FUNCTION_ARGS)
1335 : : {
1336 : 882 : text *in1 = PG_GETARG_TEXT_PP(0);
1337 : 882 : text *in2 = PG_GETARG_TEXT_PP(1);
1338 : : float4 res;
1339 : :
1340 [ - + - - : 882 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
1341 [ - + - - : 882 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1342 : : WORD_SIMILARITY_STRICT);
1343 : :
3651 1344 [ - + ]: 882 : PG_FREE_IF_COPY(in1, 0);
1345 [ - + ]: 882 : PG_FREE_IF_COPY(in2, 1);
1346 : 882 : PG_RETURN_FLOAT4(res);
1347 : : }
1348 : :
1349 : : Datum
5580 tgl@sss.pgh.pa.us 1350 : 1004 : similarity_dist(PG_FUNCTION_ARGS)
1351 : : {
1352 : 1004 : float4 res = DatumGetFloat4(DirectFunctionCall2(similarity,
1353 : : PG_GETARG_DATUM(0),
1354 : : PG_GETARG_DATUM(1)));
1355 : :
1356 : 1004 : PG_RETURN_FLOAT4(1.0 - res);
1357 : : }
1358 : :
1359 : : Datum
7868 bruce@momjian.us 1360 : 6000 : similarity_op(PG_FUNCTION_ARGS)
1361 : : {
5580 tgl@sss.pgh.pa.us 1362 : 6000 : float4 res = DatumGetFloat4(DirectFunctionCall2(similarity,
1363 : : PG_GETARG_DATUM(0),
1364 : : PG_GETARG_DATUM(1)));
1365 : :
3651 teodor@sigaev.ru 1366 : 6000 : PG_RETURN_BOOL(res >= similarity_threshold);
1367 : : }
1368 : :
1369 : : Datum
1370 : 1924 : word_similarity_op(PG_FUNCTION_ARGS)
1371 : : {
1372 : 1924 : text *in1 = PG_GETARG_TEXT_PP(0);
1373 : 1924 : text *in2 = PG_GETARG_TEXT_PP(1);
1374 : : float4 res;
1375 : :
1376 [ - + - - : 1924 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
3566 rhaas@postgresql.org 1377 [ - + - - : 1924 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1378 : : WORD_SIMILARITY_CHECK_ONLY);
1379 : :
3651 teodor@sigaev.ru 1380 [ - + ]: 1924 : PG_FREE_IF_COPY(in1, 0);
1381 [ - + ]: 1924 : PG_FREE_IF_COPY(in2, 1);
1382 : 1924 : PG_RETURN_BOOL(res >= word_similarity_threshold);
1383 : : }
1384 : :
1385 : : Datum
1386 : 2926 : word_similarity_commutator_op(PG_FUNCTION_ARGS)
1387 : : {
1388 : 2926 : text *in1 = PG_GETARG_TEXT_PP(0);
1389 : 2926 : text *in2 = PG_GETARG_TEXT_PP(1);
1390 : : float4 res;
1391 : :
1392 [ - + - - : 2926 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
3566 rhaas@postgresql.org 1393 [ - + - - : 2926 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1394 : : WORD_SIMILARITY_CHECK_ONLY);
1395 : :
3651 teodor@sigaev.ru 1396 [ - + ]: 2926 : PG_FREE_IF_COPY(in1, 0);
1397 [ - + ]: 2926 : PG_FREE_IF_COPY(in2, 1);
1398 : 2926 : PG_RETURN_BOOL(res >= word_similarity_threshold);
1399 : : }
1400 : :
1401 : : Datum
3651 teodor@sigaev.ru 1402 :UBC 0 : word_similarity_dist_op(PG_FUNCTION_ARGS)
1403 : : {
1404 : 0 : text *in1 = PG_GETARG_TEXT_PP(0);
1405 : 0 : text *in2 = PG_GETARG_TEXT_PP(1);
1406 : : float4 res;
1407 : :
1408 [ # # # # : 0 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
# # # # #
# # # ]
3566 rhaas@postgresql.org 1409 [ # # # # : 0 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
# # # # #
# # # ]
1410 : : 0);
1411 : :
3651 teodor@sigaev.ru 1412 [ # # ]: 0 : PG_FREE_IF_COPY(in1, 0);
1413 [ # # ]: 0 : PG_FREE_IF_COPY(in2, 1);
1414 : 0 : PG_RETURN_FLOAT4(1.0 - res);
1415 : : }
1416 : :
1417 : : Datum
3651 teodor@sigaev.ru 1418 :CBC 714 : word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
1419 : : {
1420 : 714 : text *in1 = PG_GETARG_TEXT_PP(0);
1421 : 714 : text *in2 = PG_GETARG_TEXT_PP(1);
1422 : : float4 res;
1423 : :
1424 [ - + - - : 714 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
3566 rhaas@postgresql.org 1425 [ - + - - : 714 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1426 : : 0);
1427 : :
2916 teodor@sigaev.ru 1428 [ - + ]: 714 : PG_FREE_IF_COPY(in1, 0);
1429 [ - + ]: 714 : PG_FREE_IF_COPY(in2, 1);
1430 : 714 : PG_RETURN_FLOAT4(1.0 - res);
1431 : : }
1432 : :
1433 : : Datum
1434 : 2530 : strict_word_similarity_op(PG_FUNCTION_ARGS)
1435 : : {
1436 : 2530 : text *in1 = PG_GETARG_TEXT_PP(0);
1437 : 2530 : text *in2 = PG_GETARG_TEXT_PP(1);
1438 : : float4 res;
1439 : :
1440 [ - + - - : 2530 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
1441 [ - + - - : 2530 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1442 : : WORD_SIMILARITY_CHECK_ONLY | WORD_SIMILARITY_STRICT);
1443 : :
1444 [ - + ]: 2530 : PG_FREE_IF_COPY(in1, 0);
1445 [ - + ]: 2530 : PG_FREE_IF_COPY(in2, 1);
1446 : 2530 : PG_RETURN_BOOL(res >= strict_word_similarity_threshold);
1447 : : }
1448 : :
1449 : : Datum
1450 : 2530 : strict_word_similarity_commutator_op(PG_FUNCTION_ARGS)
1451 : : {
1452 : 2530 : text *in1 = PG_GETARG_TEXT_PP(0);
1453 : 2530 : text *in2 = PG_GETARG_TEXT_PP(1);
1454 : : float4 res;
1455 : :
1456 [ - + - - : 2530 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
1457 [ - + - - : 2530 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1458 : : WORD_SIMILARITY_CHECK_ONLY | WORD_SIMILARITY_STRICT);
1459 : :
1460 [ - + ]: 2530 : PG_FREE_IF_COPY(in1, 0);
1461 [ - + ]: 2530 : PG_FREE_IF_COPY(in2, 1);
1462 : 2530 : PG_RETURN_BOOL(res >= strict_word_similarity_threshold);
1463 : : }
1464 : :
1465 : : Datum
2916 teodor@sigaev.ru 1466 :UBC 0 : strict_word_similarity_dist_op(PG_FUNCTION_ARGS)
1467 : : {
1468 : 0 : text *in1 = PG_GETARG_TEXT_PP(0);
1469 : 0 : text *in2 = PG_GETARG_TEXT_PP(1);
1470 : : float4 res;
1471 : :
1472 [ # # # # : 0 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
# # # # #
# # # ]
1473 [ # # # # : 0 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
# # # # #
# # # ]
1474 : : WORD_SIMILARITY_STRICT);
1475 : :
1476 [ # # ]: 0 : PG_FREE_IF_COPY(in1, 0);
1477 [ # # ]: 0 : PG_FREE_IF_COPY(in2, 1);
1478 : 0 : PG_RETURN_FLOAT4(1.0 - res);
1479 : : }
1480 : :
1481 : : Datum
2916 teodor@sigaev.ru 1482 :CBC 720 : strict_word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
1483 : : {
1484 : 720 : text *in1 = PG_GETARG_TEXT_PP(0);
1485 : 720 : text *in2 = PG_GETARG_TEXT_PP(1);
1486 : : float4 res;
1487 : :
1488 [ - + - - : 720 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
1489 [ - + - - : 720 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1490 : : WORD_SIMILARITY_STRICT);
1491 : :
3651 1492 [ - + ]: 720 : PG_FREE_IF_COPY(in1, 0);
1493 [ - + ]: 720 : PG_FREE_IF_COPY(in2, 1);
1494 : 720 : PG_RETURN_FLOAT4(1.0 - res);
1495 : : }
|
