PostgreSQL Source Code  git master
varlena.h File Reference
#include "nodes/pg_list.h"
#include "utils/sortsupport.h"
Include dependency graph for varlena.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  ClosestMatchState
 

Typedefs

typedef struct ClosestMatchState ClosestMatchState
 

Functions

int varstr_cmp (const char *arg1, int len1, const char *arg2, int len2, Oid collid)
 
void varstr_sortsupport (SortSupport ssup, Oid typid, Oid collid)
 
int varstr_levenshtein (const char *source, int slen, const char *target, int tlen, int ins_c, int del_c, int sub_c, bool trusted)
 
int varstr_levenshtein_less_equal (const char *source, int slen, const char *target, int tlen, int ins_c, int del_c, int sub_c, int max_d, bool trusted)
 
ListtextToQualifiedNameList (text *textval)
 
bool SplitIdentifierString (char *rawstring, char separator, List **namelist)
 
bool SplitDirectoriesString (char *rawstring, char separator, List **namelist)
 
bool SplitGUCList (char *rawstring, char separator, List **namelist)
 
textreplace_text_regexp (text *src_text, text *pattern_text, text *replace_text, int cflags, Oid collation, int search_start, int n)
 
void initClosestMatch (ClosestMatchState *state, const char *source, int max_d)
 
void updateClosestMatch (ClosestMatchState *state, const char *candidate)
 
const char * getClosestMatch (ClosestMatchState *state)
 

Typedef Documentation

◆ ClosestMatchState

Function Documentation

◆ getClosestMatch()

const char* getClosestMatch ( ClosestMatchState state)

Definition at line 6201 of file varlena.c.

6202 {
6203  Assert(state);
6204 
6205  return state->match;
6206 }
Assert(fmt[strlen(fmt) - 1] !='\n')
Definition: regguts.h:323

References Assert().

Referenced by dblink_fdw_validator(), file_fdw_validator(), postgres_fdw_validator(), and postgresql_fdw_validator().

◆ initClosestMatch()

void initClosestMatch ( ClosestMatchState state,
const char *  source,
int  max_d 
)

Definition at line 6146 of file varlena.c.

6147 {
6148  Assert(state);
6149  Assert(max_d >= 0);
6150 
6151  state->source = source;
6152  state->min_d = -1;
6153  state->max_d = max_d;
6154  state->match = NULL;
6155 }
static rewind_source * source
Definition: pg_rewind.c:89

References Assert(), and source.

Referenced by dblink_fdw_validator(), file_fdw_validator(), postgres_fdw_validator(), and postgresql_fdw_validator().

◆ replace_text_regexp()

text* replace_text_regexp ( text src_text,
text pattern_text,
text replace_text,
int  cflags,
Oid  collation,
int  search_start,
int  n 
)

Definition at line 4203 of file varlena.c.

4207 {
4208  text *ret_text;
4209  regex_t *re;
4210  int src_text_len = VARSIZE_ANY_EXHDR(src_text);
4211  int nmatches = 0;
4213  regmatch_t pmatch[10]; /* main match, plus \1 to \9 */
4214  int nmatch = lengthof(pmatch);
4215  pg_wchar *data;
4216  size_t data_len;
4217  int data_pos;
4218  char *start_ptr;
4219  int escape_status;
4220 
4221  initStringInfo(&buf);
4222 
4223  /* Convert data string to wide characters. */
4224  data = (pg_wchar *) palloc((src_text_len + 1) * sizeof(pg_wchar));
4225  data_len = pg_mb2wchar_with_len(VARDATA_ANY(src_text), data, src_text_len);
4226 
4227  /* Check whether replace_text has escapes, especially regexp submatches. */
4229 
4230  /* If no regexp submatches, we can use REG_NOSUB. */
4231  if (escape_status < 2)
4232  {
4233  cflags |= REG_NOSUB;
4234  /* Also tell pg_regexec we only want the whole-match location. */
4235  nmatch = 1;
4236  }
4237 
4238  /* Prepare the regexp. */
4239  re = RE_compile_and_cache(pattern_text, cflags, collation);
4240 
4241  /* start_ptr points to the data_pos'th character of src_text */
4242  start_ptr = (char *) VARDATA_ANY(src_text);
4243  data_pos = 0;
4244 
4245  while (search_start <= data_len)
4246  {
4247  int regexec_result;
4248 
4250 
4251  regexec_result = pg_regexec(re,
4252  data,
4253  data_len,
4254  search_start,
4255  NULL, /* no details */
4256  nmatch,
4257  pmatch,
4258  0);
4259 
4260  if (regexec_result == REG_NOMATCH)
4261  break;
4262 
4263  if (regexec_result != REG_OKAY)
4264  {
4265  char errMsg[100];
4266 
4267  pg_regerror(regexec_result, re, errMsg, sizeof(errMsg));
4268  ereport(ERROR,
4269  (errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
4270  errmsg("regular expression failed: %s", errMsg)));
4271  }
4272 
4273  /*
4274  * Count matches, and decide whether to replace this match.
4275  */
4276  nmatches++;
4277  if (n > 0 && nmatches != n)
4278  {
4279  /*
4280  * No, so advance search_start, but not start_ptr/data_pos. (Thus,
4281  * we treat the matched text as if it weren't matched, and copy it
4282  * to the output later.)
4283  */
4284  search_start = pmatch[0].rm_eo;
4285  if (pmatch[0].rm_so == pmatch[0].rm_eo)
4286  search_start++;
4287  continue;
4288  }
4289 
4290  /*
4291  * Copy the text to the left of the match position. Note we are given
4292  * character not byte indexes.
4293  */
4294  if (pmatch[0].rm_so - data_pos > 0)
4295  {
4296  int chunk_len;
4297 
4298  chunk_len = charlen_to_bytelen(start_ptr,
4299  pmatch[0].rm_so - data_pos);
4300  appendBinaryStringInfo(&buf, start_ptr, chunk_len);
4301 
4302  /*
4303  * Advance start_ptr over that text, to avoid multiple rescans of
4304  * it if the replace_text contains multiple back-references.
4305  */
4306  start_ptr += chunk_len;
4307  data_pos = pmatch[0].rm_so;
4308  }
4309 
4310  /*
4311  * Copy the replace_text, processing escapes if any are present.
4312  */
4313  if (escape_status > 0)
4315  start_ptr, data_pos);
4316  else
4318 
4319  /* Advance start_ptr and data_pos over the matched text. */
4320  start_ptr += charlen_to_bytelen(start_ptr,
4321  pmatch[0].rm_eo - data_pos);
4322  data_pos = pmatch[0].rm_eo;
4323 
4324  /*
4325  * If we only want to replace one occurrence, we're done.
4326  */
4327  if (n > 0)
4328  break;
4329 
4330  /*
4331  * Advance search position. Normally we start the next search at the
4332  * end of the previous match; but if the match was of zero length, we
4333  * have to advance by one character, or we'd just find the same match
4334  * again.
4335  */
4336  search_start = data_pos;
4337  if (pmatch[0].rm_so == pmatch[0].rm_eo)
4338  search_start++;
4339  }
4340 
4341  /*
4342  * Copy the text to the right of the last match.
4343  */
4344  if (data_pos < data_len)
4345  {
4346  int chunk_len;
4347 
4348  chunk_len = ((char *) src_text + VARSIZE_ANY(src_text)) - start_ptr;
4349  appendBinaryStringInfo(&buf, start_ptr, chunk_len);
4350  }
4351 
4352  ret_text = cstring_to_text_with_len(buf.data, buf.len);
4353  pfree(buf.data);
4354  pfree(data);
4355 
4356  return ret_text;
4357 }
#define lengthof(array)
Definition: c.h:777
int errcode(int sqlerrcode)
Definition: elog.c:858
int errmsg(const char *fmt,...)
Definition: elog.c:1069
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
unsigned int pg_wchar
Definition: mbprint.c:31
int pg_mb2wchar_with_len(const char *from, pg_wchar *to, int len)
Definition: mbutils.c:987
void pfree(void *pointer)
Definition: mcxt.c:1456
void * palloc(Size size)
Definition: mcxt.c:1226
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:121
const void * data
static char * buf
Definition: pg_test_fsync.c:67
size_t pg_regerror(int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size)
Definition: regerror.c:60
#define REG_NOMATCH
Definition: regex.h:138
#define REG_OKAY
Definition: regex.h:137
#define REG_NOSUB
Definition: regex.h:107
int pg_regexec(regex_t *re, const chr *string, size_t len, size_t search_start, rm_detail_t *details, size_t nmatch, regmatch_t pmatch[], int flags)
Definition: regexec.c:185
regex_t * RE_compile_and_cache(text *text_re, int cflags, Oid collation)
Definition: regexp.c:142
void appendBinaryStringInfo(StringInfo str, const void *data, int datalen)
Definition: stringinfo.c:227
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59
Definition: regex.h:56
regoff_t rm_eo
Definition: regex.h:86
regoff_t rm_so
Definition: regex.h:85
Definition: c.h:676
#define VARSIZE_ANY(PTR)
Definition: varatt.h:311
#define VARDATA_ANY(PTR)
Definition: varatt.h:324
#define VARSIZE_ANY_EXHDR(PTR)
Definition: varatt.h:317
static void appendStringInfoText(StringInfo str, const text *t)
Definition: varlena.c:3979
static int check_replace_text_has_escape(const text *replace_text)
Definition: varlena.c:4070
static void appendStringInfoRegexpSubstr(StringInfo str, text *replace_text, regmatch_t *pmatch, char *start_ptr, int data_pos)
Definition: varlena.c:4103
static int charlen_to_bytelen(const char *p, int n)
Definition: varlena.c:804
text * cstring_to_text_with_len(const char *s, int len)
Definition: varlena.c:194
Datum replace_text(PG_FUNCTION_ARGS)
Definition: varlena.c:3993

References appendBinaryStringInfo(), appendStringInfoRegexpSubstr(), appendStringInfoText(), buf, charlen_to_bytelen(), CHECK_FOR_INTERRUPTS, check_replace_text_has_escape(), cstring_to_text_with_len(), data, ereport, errcode(), errmsg(), ERROR, initStringInfo(), lengthof, palloc(), pfree(), pg_mb2wchar_with_len(), pg_regerror(), pg_regexec(), RE_compile_and_cache(), REG_NOMATCH, REG_NOSUB, REG_OKAY, replace_text(), regmatch_t::rm_eo, regmatch_t::rm_so, VARDATA_ANY, VARSIZE_ANY, and VARSIZE_ANY_EXHDR.

Referenced by textregexreplace(), textregexreplace_extended(), and textregexreplace_noopt().

◆ SplitDirectoriesString()

bool SplitDirectoriesString ( char *  rawstring,
char  separator,
List **  namelist 
)

Definition at line 3581 of file varlena.c.

3583 {
3584  char *nextp = rawstring;
3585  bool done = false;
3586 
3587  *namelist = NIL;
3588 
3589  while (scanner_isspace(*nextp))
3590  nextp++; /* skip leading whitespace */
3591 
3592  if (*nextp == '\0')
3593  return true; /* allow empty string */
3594 
3595  /* At the top of the loop, we are at start of a new directory. */
3596  do
3597  {
3598  char *curname;
3599  char *endp;
3600 
3601  if (*nextp == '"')
3602  {
3603  /* Quoted name --- collapse quote-quote pairs */
3604  curname = nextp + 1;
3605  for (;;)
3606  {
3607  endp = strchr(nextp + 1, '"');
3608  if (endp == NULL)
3609  return false; /* mismatched quotes */
3610  if (endp[1] != '"')
3611  break; /* found end of quoted name */
3612  /* Collapse adjacent quotes into one quote, and look again */
3613  memmove(endp, endp + 1, strlen(endp));
3614  nextp = endp;
3615  }
3616  /* endp now points at the terminating quote */
3617  nextp = endp + 1;
3618  }
3619  else
3620  {
3621  /* Unquoted name --- extends to separator or end of string */
3622  curname = endp = nextp;
3623  while (*nextp && *nextp != separator)
3624  {
3625  /* trailing whitespace should not be included in name */
3626  if (!scanner_isspace(*nextp))
3627  endp = nextp + 1;
3628  nextp++;
3629  }
3630  if (curname == endp)
3631  return false; /* empty unquoted name not allowed */
3632  }
3633 
3634  while (scanner_isspace(*nextp))
3635  nextp++; /* skip trailing whitespace */
3636 
3637  if (*nextp == separator)
3638  {
3639  nextp++;
3640  while (scanner_isspace(*nextp))
3641  nextp++; /* skip leading whitespace for next */
3642  /* we expect another name, so done remains false */
3643  }
3644  else if (*nextp == '\0')
3645  done = true;
3646  else
3647  return false; /* invalid syntax */
3648 
3649  /* Now safe to overwrite separator with a null */
3650  *endp = '\0';
3651 
3652  /* Truncate path if it's overlength */
3653  if (strlen(curname) >= MAXPGPATH)
3654  curname[MAXPGPATH - 1] = '\0';
3655 
3656  /*
3657  * Finished isolating current name --- add it to list
3658  */
3659  curname = pstrdup(curname);
3660  canonicalize_path(curname);
3661  *namelist = lappend(*namelist, curname);
3662 
3663  /* Loop back if we didn't reach end of string */
3664  } while (!done);
3665 
3666  return true;
3667 }
List * lappend(List *list, void *datum)
Definition: list.c:338
char * pstrdup(const char *in)
Definition: mcxt.c:1644
#define MAXPGPATH
#define NIL
Definition: pg_list.h:68
void canonicalize_path(char *path)
Definition: path.c:264
bool scanner_isspace(char ch)
Definition: scansup.c:117

References canonicalize_path(), lappend(), MAXPGPATH, NIL, pstrdup(), and scanner_isspace().

Referenced by load_libraries(), and PostmasterMain().

◆ SplitGUCList()

bool SplitGUCList ( char *  rawstring,
char  separator,
List **  namelist 
)

Definition at line 3702 of file varlena.c.

3704 {
3705  char *nextp = rawstring;
3706  bool done = false;
3707 
3708  *namelist = NIL;
3709 
3710  while (scanner_isspace(*nextp))
3711  nextp++; /* skip leading whitespace */
3712 
3713  if (*nextp == '\0')
3714  return true; /* allow empty string */
3715 
3716  /* At the top of the loop, we are at start of a new identifier. */
3717  do
3718  {
3719  char *curname;
3720  char *endp;
3721 
3722  if (*nextp == '"')
3723  {
3724  /* Quoted name --- collapse quote-quote pairs */
3725  curname = nextp + 1;
3726  for (;;)
3727  {
3728  endp = strchr(nextp + 1, '"');
3729  if (endp == NULL)
3730  return false; /* mismatched quotes */
3731  if (endp[1] != '"')
3732  break; /* found end of quoted name */
3733  /* Collapse adjacent quotes into one quote, and look again */
3734  memmove(endp, endp + 1, strlen(endp));
3735  nextp = endp;
3736  }
3737  /* endp now points at the terminating quote */
3738  nextp = endp + 1;
3739  }
3740  else
3741  {
3742  /* Unquoted name --- extends to separator or whitespace */
3743  curname = nextp;
3744  while (*nextp && *nextp != separator &&
3745  !scanner_isspace(*nextp))
3746  nextp++;
3747  endp = nextp;
3748  if (curname == nextp)
3749  return false; /* empty unquoted name not allowed */
3750  }
3751 
3752  while (scanner_isspace(*nextp))
3753  nextp++; /* skip trailing whitespace */
3754 
3755  if (*nextp == separator)
3756  {
3757  nextp++;
3758  while (scanner_isspace(*nextp))
3759  nextp++; /* skip leading whitespace for next */
3760  /* we expect another name, so done remains false */
3761  }
3762  else if (*nextp == '\0')
3763  done = true;
3764  else
3765  return false; /* invalid syntax */
3766 
3767  /* Now safe to overwrite separator with a null */
3768  *endp = '\0';
3769 
3770  /*
3771  * Finished isolating current name --- add it to list
3772  */
3773  *namelist = lappend(*namelist, curname);
3774 
3775  /* Loop back if we didn't reach end of string */
3776  } while (!done);
3777 
3778  return true;
3779 }

References lappend(), NIL, and scanner_isspace().

Referenced by check_debug_io_direct(), dumpFunc(), parse_hba_auth_opt(), pg_get_functiondef(), and PostmasterMain().

◆ SplitIdentifierString()

bool SplitIdentifierString ( char *  rawstring,
char  separator,
List **  namelist 
)

Definition at line 3454 of file varlena.c.

3456 {
3457  char *nextp = rawstring;
3458  bool done = false;
3459 
3460  *namelist = NIL;
3461 
3462  while (scanner_isspace(*nextp))
3463  nextp++; /* skip leading whitespace */
3464 
3465  if (*nextp == '\0')
3466  return true; /* allow empty string */
3467 
3468  /* At the top of the loop, we are at start of a new identifier. */
3469  do
3470  {
3471  char *curname;
3472  char *endp;
3473 
3474  if (*nextp == '"')
3475  {
3476  /* Quoted name --- collapse quote-quote pairs, no downcasing */
3477  curname = nextp + 1;
3478  for (;;)
3479  {
3480  endp = strchr(nextp + 1, '"');
3481  if (endp == NULL)
3482  return false; /* mismatched quotes */
3483  if (endp[1] != '"')
3484  break; /* found end of quoted name */
3485  /* Collapse adjacent quotes into one quote, and look again */
3486  memmove(endp, endp + 1, strlen(endp));
3487  nextp = endp;
3488  }
3489  /* endp now points at the terminating quote */
3490  nextp = endp + 1;
3491  }
3492  else
3493  {
3494  /* Unquoted name --- extends to separator or whitespace */
3495  char *downname;
3496  int len;
3497 
3498  curname = nextp;
3499  while (*nextp && *nextp != separator &&
3500  !scanner_isspace(*nextp))
3501  nextp++;
3502  endp = nextp;
3503  if (curname == nextp)
3504  return false; /* empty unquoted name not allowed */
3505 
3506  /*
3507  * Downcase the identifier, using same code as main lexer does.
3508  *
3509  * XXX because we want to overwrite the input in-place, we cannot
3510  * support a downcasing transformation that increases the string
3511  * length. This is not a problem given the current implementation
3512  * of downcase_truncate_identifier, but we'll probably have to do
3513  * something about this someday.
3514  */
3515  len = endp - curname;
3516  downname = downcase_truncate_identifier(curname, len, false);
3517  Assert(strlen(downname) <= len);
3518  strncpy(curname, downname, len); /* strncpy is required here */
3519  pfree(downname);
3520  }
3521 
3522  while (scanner_isspace(*nextp))
3523  nextp++; /* skip trailing whitespace */
3524 
3525  if (*nextp == separator)
3526  {
3527  nextp++;
3528  while (scanner_isspace(*nextp))
3529  nextp++; /* skip leading whitespace for next */
3530  /* we expect another name, so done remains false */
3531  }
3532  else if (*nextp == '\0')
3533  done = true;
3534  else
3535  return false; /* invalid syntax */
3536 
3537  /* Now safe to overwrite separator with a null */
3538  *endp = '\0';
3539 
3540  /* Truncate name if it's overlength */
3541  truncate_identifier(curname, strlen(curname), false);
3542 
3543  /*
3544  * Finished isolating current name --- add it to list
3545  */
3546  *namelist = lappend(*namelist, curname);
3547 
3548  /* Loop back if we didn't reach end of string */
3549  } while (!done);
3550 
3551  return true;
3552 }
const void size_t len
void truncate_identifier(char *ident, int len, bool warn)
Definition: scansup.c:93
char * downcase_truncate_identifier(const char *ident, int len, bool warn)
Definition: scansup.c:37

References Assert(), downcase_truncate_identifier(), lappend(), len, NIL, pfree(), scanner_isspace(), and truncate_identifier().

Referenced by check_createrole_self_grant(), check_datestyle(), check_log_destination(), check_search_path(), check_temp_tablespaces(), check_wal_consistency_checking(), ExtractExtensionList(), parse_extension_control_file(), parse_output_parameters(), parse_publication_options(), plpgsql_extra_checks_check_hook(), PrepareTempTablespaces(), recomputeNamespacePath(), stringToQualifiedNameList(), and textToQualifiedNameList().

◆ textToQualifiedNameList()

List* textToQualifiedNameList ( text textval)

Definition at line 3396 of file varlena.c.

3397 {
3398  char *rawname;
3399  List *result = NIL;
3400  List *namelist;
3401  ListCell *l;
3402 
3403  /* Convert to C string (handles possible detoasting). */
3404  /* Note we rely on being able to modify rawname below. */
3405  rawname = text_to_cstring(textval);
3406 
3407  if (!SplitIdentifierString(rawname, '.', &namelist))
3408  ereport(ERROR,
3409  (errcode(ERRCODE_INVALID_NAME),
3410  errmsg("invalid name syntax")));
3411 
3412  if (namelist == NIL)
3413  ereport(ERROR,
3414  (errcode(ERRCODE_INVALID_NAME),
3415  errmsg("invalid name syntax")));
3416 
3417  foreach(l, namelist)
3418  {
3419  char *curname = (char *) lfirst(l);
3420 
3421  result = lappend(result, makeString(pstrdup(curname)));
3422  }
3423 
3424  pfree(rawname);
3425  list_free(namelist);
3426 
3427  return result;
3428 }
void list_free(List *list)
Definition: list.c:1545
#define lfirst(lc)
Definition: pg_list.h:172
Definition: pg_list.h:54
String * makeString(char *str)
Definition: value.c:63
char * text_to_cstring(const text *t)
Definition: varlena.c:215
bool SplitIdentifierString(char *rawstring, char separator, List **namelist)
Definition: varlena.c:3454

References ereport, errcode(), errmsg(), ERROR, lappend(), lfirst, list_free(), makeString(), NIL, pfree(), pstrdup(), SplitIdentifierString(), and text_to_cstring().

Referenced by bt_metap(), bt_multi_page_stats(), bt_page_items_internal(), bt_page_stats_internal(), convert_table_name(), currtid_byrelname(), get_raw_page_internal(), get_rel_from_relname(), nextval(), pg_get_serial_sequence(), pg_get_viewdef_name(), pg_get_viewdef_name_ext(), pg_relpages(), pg_relpages_v1_5(), pgrowlocks(), pgstatindex(), pgstatindex_v1_5(), pgstattuple(), pgstattuple_v1_5(), row_security_active_name(), text_regclass(), ts_parse_byname(), and ts_token_type_byname().

◆ updateClosestMatch()

void updateClosestMatch ( ClosestMatchState state,
const char *  candidate 
)

Definition at line 6166 of file varlena.c.

6167 {
6168  int dist;
6169 
6170  Assert(state);
6171 
6172  if (state->source == NULL || state->source[0] == '\0' ||
6173  candidate == NULL || candidate[0] == '\0')
6174  return;
6175 
6176  /*
6177  * To avoid ERROR-ing, we check the lengths here instead of setting
6178  * 'trusted' to false in the call to varstr_levenshtein_less_equal().
6179  */
6180  if (strlen(state->source) > MAX_LEVENSHTEIN_STRLEN ||
6181  strlen(candidate) > MAX_LEVENSHTEIN_STRLEN)
6182  return;
6183 
6184  dist = varstr_levenshtein_less_equal(state->source, strlen(state->source),
6185  candidate, strlen(candidate), 1, 1, 1,
6186  state->max_d, true);
6187  if (dist <= state->max_d &&
6188  dist <= strlen(state->source) / 2 &&
6189  (state->min_d == -1 || dist < state->min_d))
6190  {
6191  state->min_d = dist;
6192  state->match = candidate;
6193  }
6194 }
#define MAX_LEVENSHTEIN_STRLEN
Definition: levenshtein.c:26
int varstr_levenshtein_less_equal(const char *source, int slen, const char *target, int tlen, int ins_c, int del_c, int sub_c, int max_d, bool trusted)

References Assert(), MAX_LEVENSHTEIN_STRLEN, and varstr_levenshtein_less_equal().

Referenced by dblink_fdw_validator(), file_fdw_validator(), postgres_fdw_validator(), and postgresql_fdw_validator().

◆ varstr_cmp()

int varstr_cmp ( const char *  arg1,
int  len1,
const char *  arg2,
int  len2,
Oid  collid 
)

Definition at line 1536 of file varlena.c.

1537 {
1538  int result;
1539 
1541 
1542  /*
1543  * Unfortunately, there is no strncoll(), so in the non-C locale case we
1544  * have to do some memory copying. This turns out to be significantly
1545  * slower, so we optimize the case where LC_COLLATE is C. We also try to
1546  * optimize relatively-short strings by avoiding palloc/pfree overhead.
1547  */
1548  if (lc_collate_is_c(collid))
1549  {
1550  result = memcmp(arg1, arg2, Min(len1, len2));
1551  if ((result == 0) && (len1 != len2))
1552  result = (len1 < len2) ? -1 : 1;
1553  }
1554  else
1555  {
1556  pg_locale_t mylocale;
1557 
1558  mylocale = pg_newlocale_from_collation(collid);
1559 
1560  /*
1561  * memcmp() can't tell us which of two unequal strings sorts first,
1562  * but it's a cheap way to tell if they're equal. Testing shows that
1563  * memcmp() followed by strcoll() is only trivially slower than
1564  * strcoll() by itself, so we don't lose much if this doesn't work out
1565  * very often, and if it does - for example, because there are many
1566  * equal strings in the input - then we win big by avoiding expensive
1567  * collation-aware comparisons.
1568  */
1569  if (len1 == len2 && memcmp(arg1, arg2, len1) == 0)
1570  return 0;
1571 
1572  result = pg_strncoll(arg1, len1, arg2, len2, mylocale);
1573 
1574  /* Break tie if necessary. */
1575  if (result == 0 && pg_locale_deterministic(mylocale))
1576  {
1577  result = memcmp(arg1, arg2, Min(len1, len2));
1578  if ((result == 0) && (len1 != len2))
1579  result = (len1 < len2) ? -1 : 1;
1580  }
1581  }
1582 
1583  return result;
1584 }
#define Min(x, y)
Definition: c.h:993
Oid collid
int pg_strncoll(const char *arg1, size_t len1, const char *arg2, size_t len2, pg_locale_t locale)
Definition: pg_locale.c:2061
bool lc_collate_is_c(Oid collation)
Definition: pg_locale.c:1307
pg_locale_t pg_newlocale_from_collation(Oid collid)
Definition: pg_locale.c:1514
bool pg_locale_deterministic(pg_locale_t locale)
Definition: pg_locale.c:1494
static void check_collation_set(Oid collid)
Definition: varlena.c:1507

References check_collation_set(), collid, lc_collate_is_c(), Min, pg_locale_deterministic(), pg_newlocale_from_collation(), and pg_strncoll().

Referenced by bpchar_larger(), bpchar_smaller(), bpcharcmp(), bpchareq(), bpcharge(), bpchargt(), bpcharle(), bpcharlt(), bpcharne(), btnametextcmp(), bttextnamecmp(), citextcmp(), compareJsonbScalarValue(), gin_compare_jsonb(), make_greater_string(), namecmp(), nameeqtext(), namenetext(), spg_text_leaf_consistent(), text_cmp(), texteqname(), and textnename().

◆ varstr_levenshtein()

int varstr_levenshtein ( const char *  source,
int  slen,
const char *  target,
int  tlen,
int  ins_c,
int  del_c,
int  sub_c,
bool  trusted 
)

Definition at line 73 of file levenshtein.c.

78 {
79  int m,
80  n;
81  int *prev;
82  int *curr;
83  int *s_char_len = NULL;
84  int j;
85  const char *y;
86 
87  /*
88  * For varstr_levenshtein_less_equal, we have real variables called
89  * start_column and stop_column; otherwise it's just short-hand for 0 and
90  * m.
91  */
92 #ifdef LEVENSHTEIN_LESS_EQUAL
93  int start_column,
94  stop_column;
95 
96 #undef START_COLUMN
97 #undef STOP_COLUMN
98 #define START_COLUMN start_column
99 #define STOP_COLUMN stop_column
100 #else
101 #undef START_COLUMN
102 #undef STOP_COLUMN
103 #define START_COLUMN 0
104 #define STOP_COLUMN m
105 #endif
106 
107  /* Convert string lengths (in bytes) to lengths in characters */
108  m = pg_mbstrlen_with_len(source, slen);
109  n = pg_mbstrlen_with_len(target, tlen);
110 
111  /*
112  * We can transform an empty s into t with n insertions, or a non-empty t
113  * into an empty s with m deletions.
114  */
115  if (!m)
116  return n * ins_c;
117  if (!n)
118  return m * del_c;
119 
120  /*
121  * For security concerns, restrict excessive CPU+RAM usage. (This
122  * implementation uses O(m) memory and has O(mn) complexity.) If
123  * "trusted" is true, caller is responsible for not making excessive
124  * requests, typically by using a small max_d along with strings that are
125  * bounded, though not necessarily to MAX_LEVENSHTEIN_STRLEN exactly.
126  */
127  if (!trusted &&
128  (m > MAX_LEVENSHTEIN_STRLEN ||
130  ereport(ERROR,
131  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
132  errmsg("levenshtein argument exceeds maximum length of %d characters",
134 
135 #ifdef LEVENSHTEIN_LESS_EQUAL
136  /* Initialize start and stop columns. */
137  start_column = 0;
138  stop_column = m + 1;
139 
140  /*
141  * If max_d >= 0, determine whether the bound is impossibly tight. If so,
142  * return max_d + 1 immediately. Otherwise, determine whether it's tight
143  * enough to limit the computation we must perform. If so, figure out
144  * initial stop column.
145  */
146  if (max_d >= 0)
147  {
148  int min_theo_d; /* Theoretical minimum distance. */
149  int max_theo_d; /* Theoretical maximum distance. */
150  int net_inserts = n - m;
151 
152  min_theo_d = net_inserts < 0 ?
153  -net_inserts * del_c : net_inserts * ins_c;
154  if (min_theo_d > max_d)
155  return max_d + 1;
156  if (ins_c + del_c < sub_c)
157  sub_c = ins_c + del_c;
158  max_theo_d = min_theo_d + sub_c * Min(m, n);
159  if (max_d >= max_theo_d)
160  max_d = -1;
161  else if (ins_c + del_c > 0)
162  {
163  /*
164  * Figure out how much of the first row of the notional matrix we
165  * need to fill in. If the string is growing, the theoretical
166  * minimum distance already incorporates the cost of deleting the
167  * number of characters necessary to make the two strings equal in
168  * length. Each additional deletion forces another insertion, so
169  * the best-case total cost increases by ins_c + del_c. If the
170  * string is shrinking, the minimum theoretical cost assumes no
171  * excess deletions; that is, we're starting no further right than
172  * column n - m. If we do start further right, the best-case
173  * total cost increases by ins_c + del_c for each move right.
174  */
175  int slack_d = max_d - min_theo_d;
176  int best_column = net_inserts < 0 ? -net_inserts : 0;
177 
178  stop_column = best_column + (slack_d / (ins_c + del_c)) + 1;
179  if (stop_column > m)
180  stop_column = m + 1;
181  }
182  }
183 #endif
184 
185  /*
186  * In order to avoid calling pg_mblen() repeatedly on each character in s,
187  * we cache all the lengths before starting the main loop -- but if all
188  * the characters in both strings are single byte, then we skip this and
189  * use a fast-path in the main loop. If only one string contains
190  * multi-byte characters, we still build the array, so that the fast-path
191  * needn't deal with the case where the array hasn't been initialized.
192  */
193  if (m != slen || n != tlen)
194  {
195  int i;
196  const char *cp = source;
197 
198  s_char_len = (int *) palloc((m + 1) * sizeof(int));
199  for (i = 0; i < m; ++i)
200  {
201  s_char_len[i] = pg_mblen(cp);
202  cp += s_char_len[i];
203  }
204  s_char_len[i] = 0;
205  }
206 
207  /* One more cell for initialization column and row. */
208  ++m;
209  ++n;
210 
211  /* Previous and current rows of notional array. */
212  prev = (int *) palloc(2 * m * sizeof(int));
213  curr = prev + m;
214 
215  /*
216  * To transform the first i characters of s into the first 0 characters of
217  * t, we must perform i deletions.
218  */
219  for (int i = START_COLUMN; i < STOP_COLUMN; i++)
220  prev[i] = i * del_c;
221 
222  /* Loop through rows of the notional array */
223  for (y = target, j = 1; j < n; j++)
224  {
225  int *temp;
226  const char *x = source;
227  int y_char_len = n != tlen + 1 ? pg_mblen(y) : 1;
228  int i;
229 
230 #ifdef LEVENSHTEIN_LESS_EQUAL
231 
232  /*
233  * In the best case, values percolate down the diagonal unchanged, so
234  * we must increment stop_column unless it's already on the right end
235  * of the array. The inner loop will read prev[stop_column], so we
236  * have to initialize it even though it shouldn't affect the result.
237  */
238  if (stop_column < m)
239  {
240  prev[stop_column] = max_d + 1;
241  ++stop_column;
242  }
243 
244  /*
245  * The main loop fills in curr, but curr[0] needs a special case: to
246  * transform the first 0 characters of s into the first j characters
247  * of t, we must perform j insertions. However, if start_column > 0,
248  * this special case does not apply.
249  */
250  if (start_column == 0)
251  {
252  curr[0] = j * ins_c;
253  i = 1;
254  }
255  else
256  i = start_column;
257 #else
258  curr[0] = j * ins_c;
259  i = 1;
260 #endif
261 
262  /*
263  * This inner loop is critical to performance, so we include a
264  * fast-path to handle the (fairly common) case where no multibyte
265  * characters are in the mix. The fast-path is entitled to assume
266  * that if s_char_len is not initialized then BOTH strings contain
267  * only single-byte characters.
268  */
269  if (s_char_len != NULL)
270  {
271  for (; i < STOP_COLUMN; i++)
272  {
273  int ins;
274  int del;
275  int sub;
276  int x_char_len = s_char_len[i - 1];
277 
278  /*
279  * Calculate costs for insertion, deletion, and substitution.
280  *
281  * When calculating cost for substitution, we compare the last
282  * character of each possibly-multibyte character first,
283  * because that's enough to rule out most mis-matches. If we
284  * get past that test, then we compare the lengths and the
285  * remaining bytes.
286  */
287  ins = prev[i] + ins_c;
288  del = curr[i - 1] + del_c;
289  if (x[x_char_len - 1] == y[y_char_len - 1]
290  && x_char_len == y_char_len &&
291  (x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
292  sub = prev[i - 1];
293  else
294  sub = prev[i - 1] + sub_c;
295 
296  /* Take the one with minimum cost. */
297  curr[i] = Min(ins, del);
298  curr[i] = Min(curr[i], sub);
299 
300  /* Point to next character. */
301  x += x_char_len;
302  }
303  }
304  else
305  {
306  for (; i < STOP_COLUMN; i++)
307  {
308  int ins;
309  int del;
310  int sub;
311 
312  /* Calculate costs for insertion, deletion, and substitution. */
313  ins = prev[i] + ins_c;
314  del = curr[i - 1] + del_c;
315  sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
316 
317  /* Take the one with minimum cost. */
318  curr[i] = Min(ins, del);
319  curr[i] = Min(curr[i], sub);
320 
321  /* Point to next character. */
322  x++;
323  }
324  }
325 
326  /* Swap current row with previous row. */
327  temp = curr;
328  curr = prev;
329  prev = temp;
330 
331  /* Point to next character. */
332  y += y_char_len;
333 
334 #ifdef LEVENSHTEIN_LESS_EQUAL
335 
336  /*
337  * This chunk of code represents a significant performance hit if used
338  * in the case where there is no max_d bound. This is probably not
339  * because the max_d >= 0 test itself is expensive, but rather because
340  * the possibility of needing to execute this code prevents tight
341  * optimization of the loop as a whole.
342  */
343  if (max_d >= 0)
344  {
345  /*
346  * The "zero point" is the column of the current row where the
347  * remaining portions of the strings are of equal length. There
348  * are (n - 1) characters in the target string, of which j have
349  * been transformed. There are (m - 1) characters in the source
350  * string, so we want to find the value for zp where (n - 1) - j =
351  * (m - 1) - zp.
352  */
353  int zp = j - (n - m);
354 
355  /* Check whether the stop column can slide left. */
356  while (stop_column > 0)
357  {
358  int ii = stop_column - 1;
359  int net_inserts = ii - zp;
360 
361  if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c :
362  -net_inserts * del_c) <= max_d)
363  break;
364  stop_column--;
365  }
366 
367  /* Check whether the start column can slide right. */
368  while (start_column < stop_column)
369  {
370  int net_inserts = start_column - zp;
371 
372  if (prev[start_column] +
373  (net_inserts > 0 ? net_inserts * ins_c :
374  -net_inserts * del_c) <= max_d)
375  break;
376 
377  /*
378  * We'll never again update these values, so we must make sure
379  * there's nothing here that could confuse any future
380  * iteration of the outer loop.
381  */
382  prev[start_column] = max_d + 1;
383  curr[start_column] = max_d + 1;
384  if (start_column != 0)
385  source += (s_char_len != NULL) ? s_char_len[start_column - 1] : 1;
386  start_column++;
387  }
388 
389  /* If they cross, we're going to exceed the bound. */
390  if (start_column >= stop_column)
391  return max_d + 1;
392  }
393 #endif
394  }
395 
396  /*
397  * Because the final value was swapped from the previous row to the
398  * current row, that's where we'll find it.
399  */
400  return prev[m - 1];
401 }
int y
Definition: isn.c:72
int x
Definition: isn.c:71
int j
Definition: isn.c:74
int i
Definition: isn.c:73
#define START_COLUMN
#define STOP_COLUMN
int pg_mbstrlen_with_len(const char *mbstr, int limit)
Definition: mbutils.c:1058
int pg_mblen(const char *mbstr)
Definition: mbutils.c:1024
static bool rest_of_char_same(const char *s1, const char *s2, int len)
Definition: varlena.c:6110

References ereport, errcode(), errmsg(), ERROR, i, j, MAX_LEVENSHTEIN_STRLEN, Min, palloc(), pg_mblen(), pg_mbstrlen_with_len(), rest_of_char_same(), source, START_COLUMN, STOP_COLUMN, x, and y.

Referenced by levenshtein(), and levenshtein_with_costs().

◆ varstr_levenshtein_less_equal()

int varstr_levenshtein_less_equal ( const char *  source,
int  slen,
const char *  target,
int  tlen,
int  ins_c,
int  del_c,
int  sub_c,
int  max_d,
bool  trusted 
)

◆ varstr_sortsupport()

void varstr_sortsupport ( SortSupport  ssup,
Oid  typid,
Oid  collid 
)

Definition at line 1870 of file varlena.c.

1871 {
1872  bool abbreviate = ssup->abbreviate;
1873  bool collate_c = false;
1874  VarStringSortSupport *sss;
1875  pg_locale_t locale = 0;
1876 
1878 
1879  /*
1880  * If possible, set ssup->comparator to a function which can be used to
1881  * directly compare two datums. If we can do this, we'll avoid the
1882  * overhead of a trip through the fmgr layer for every comparison, which
1883  * can be substantial.
1884  *
1885  * Most typically, we'll set the comparator to varlenafastcmp_locale,
1886  * which uses strcoll() to perform comparisons. We use that for the
1887  * BpChar case too, but type NAME uses namefastcmp_locale. However, if
1888  * LC_COLLATE = C, we can make things quite a bit faster with
1889  * varstrfastcmp_c, bpcharfastcmp_c, or namefastcmp_c, all of which use
1890  * memcmp() rather than strcoll().
1891  */
1892  if (lc_collate_is_c(collid))
1893  {
1894  if (typid == BPCHAROID)
1895  ssup->comparator = bpcharfastcmp_c;
1896  else if (typid == NAMEOID)
1897  {
1898  ssup->comparator = namefastcmp_c;
1899  /* Not supporting abbreviation with type NAME, for now */
1900  abbreviate = false;
1901  }
1902  else
1903  ssup->comparator = varstrfastcmp_c;
1904 
1905  collate_c = true;
1906  }
1907  else
1908  {
1909  /*
1910  * We need a collation-sensitive comparison. To make things faster,
1911  * we'll figure out the collation based on the locale id and cache the
1912  * result.
1913  */
1915 
1916  /*
1917  * We use varlenafastcmp_locale except for type NAME.
1918  */
1919  if (typid == NAMEOID)
1920  {
1922  /* Not supporting abbreviation with type NAME, for now */
1923  abbreviate = false;
1924  }
1925  else
1927  }
1928 
1929  /*
1930  * Unfortunately, it seems that abbreviation for non-C collations is
1931  * broken on many common platforms; see pg_strxfrm_enabled().
1932  *
1933  * Even apart from the risk of broken locales, it's possible that there
1934  * are platforms where the use of abbreviated keys should be disabled at
1935  * compile time. Having only 4 byte datums could make worst-case
1936  * performance drastically more likely, for example. Moreover, macOS's
1937  * strxfrm() implementation is known to not effectively concentrate a
1938  * significant amount of entropy from the original string in earlier
1939  * transformed blobs. It's possible that other supported platforms are
1940  * similarly encumbered. So, if we ever get past disabling this
1941  * categorically, we may still want or need to disable it for particular
1942  * platforms.
1943  */
1944  if (!collate_c && !pg_strxfrm_enabled(locale))
1945  abbreviate = false;
1946 
1947  /*
1948  * If we're using abbreviated keys, or if we're using a locale-aware
1949  * comparison, we need to initialize a VarStringSortSupport object. Both
1950  * cases will make use of the temporary buffers we initialize here for
1951  * scratch space (and to detect requirement for BpChar semantics from
1952  * caller), and the abbreviation case requires additional state.
1953  */
1954  if (abbreviate || !collate_c)
1955  {
1956  sss = palloc(sizeof(VarStringSortSupport));
1957  sss->buf1 = palloc(TEXTBUFLEN);
1958  sss->buflen1 = TEXTBUFLEN;
1959  sss->buf2 = palloc(TEXTBUFLEN);
1960  sss->buflen2 = TEXTBUFLEN;
1961  /* Start with invalid values */
1962  sss->last_len1 = -1;
1963  sss->last_len2 = -1;
1964  /* Initialize */
1965  sss->last_returned = 0;
1966  sss->locale = locale;
1967 
1968  /*
1969  * To avoid somehow confusing a strxfrm() blob and an original string,
1970  * constantly keep track of the variety of data that buf1 and buf2
1971  * currently contain.
1972  *
1973  * Comparisons may be interleaved with conversion calls. Frequently,
1974  * conversions and comparisons are batched into two distinct phases,
1975  * but the correctness of caching cannot hinge upon this. For
1976  * comparison caching, buffer state is only trusted if cache_blob is
1977  * found set to false, whereas strxfrm() caching only trusts the state
1978  * when cache_blob is found set to true.
1979  *
1980  * Arbitrarily initialize cache_blob to true.
1981  */
1982  sss->cache_blob = true;
1983  sss->collate_c = collate_c;
1984  sss->typid = typid;
1985  ssup->ssup_extra = sss;
1986 
1987  /*
1988  * If possible, plan to use the abbreviated keys optimization. The
1989  * core code may switch back to authoritative comparator should
1990  * abbreviation be aborted.
1991  */
1992  if (abbreviate)
1993  {
1994  sss->prop_card = 0.20;
1995  initHyperLogLog(&sss->abbr_card, 10);
1996  initHyperLogLog(&sss->full_card, 10);
1997  ssup->abbrev_full_comparator = ssup->comparator;
2001  }
2002  }
2003 }
void initHyperLogLog(hyperLogLogState *cState, uint8 bwidth)
Definition: hyperloglog.c:66
static char * locale
Definition: initdb.c:140
bool pg_strxfrm_enabled(pg_locale_t locale)
Definition: pg_locale.c:2277
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
void * ssup_extra
Definition: sortsupport.h:87
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182
pg_locale_t locale
Definition: varlena.c:94
hyperLogLogState full_card
Definition: varlena.c:92
hyperLogLogState abbr_card
Definition: varlena.c:91
int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup)
Definition: tuplesort.c:3174
static bool varstr_abbrev_abort(int memtupcount, SortSupport ssup)
Definition: varlena.c:2434
static int varlenafastcmp_locale(Datum x, Datum y, SortSupport ssup)
Definition: varlena.c:2091
static int bpcharfastcmp_c(Datum x, Datum y, SortSupport ssup)
Definition: varlena.c:2046
static int namefastcmp_c(Datum x, Datum y, SortSupport ssup)
Definition: varlena.c:2079
static int namefastcmp_locale(Datum x, Datum y, SortSupport ssup)
Definition: varlena.c:2122
static Datum varstr_abbrev_convert(Datum original, SortSupport ssup)
Definition: varlena.c:2236
static int varstrfastcmp_c(Datum x, Datum y, SortSupport ssup)
Definition: varlena.c:2009
#define TEXTBUFLEN
Definition: varlena.c:112

References VarStringSortSupport::abbr_card, SortSupportData::abbrev_abort, SortSupportData::abbrev_converter, SortSupportData::abbrev_full_comparator, SortSupportData::abbreviate, bpcharfastcmp_c(), VarStringSortSupport::buf1, VarStringSortSupport::buf2, VarStringSortSupport::buflen1, VarStringSortSupport::buflen2, VarStringSortSupport::cache_blob, check_collation_set(), VarStringSortSupport::collate_c, collid, SortSupportData::comparator, VarStringSortSupport::full_card, initHyperLogLog(), VarStringSortSupport::last_len1, VarStringSortSupport::last_len2, VarStringSortSupport::last_returned, lc_collate_is_c(), VarStringSortSupport::locale, locale, namefastcmp_c(), namefastcmp_locale(), palloc(), pg_newlocale_from_collation(), pg_strxfrm_enabled(), VarStringSortSupport::prop_card, ssup_datum_unsigned_cmp(), SortSupportData::ssup_extra, TEXTBUFLEN, VarStringSortSupport::typid, varlenafastcmp_locale(), varstr_abbrev_abort(), varstr_abbrev_convert(), and varstrfastcmp_c().

Referenced by bpchar_sortsupport(), btbpchar_pattern_sortsupport(), btnamesortsupport(), bttext_pattern_sortsupport(), bttextsortsupport(), and bytea_sortsupport().