← Back to branch summary

~ubuntu-branches/ubuntu/lucid/postgresql-8.4/lucid-proposed

« back to all changes in this revision

Viewing changes to src/backend/utils/adt/like_match.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/utils/adt/like_match.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * like_match.c
 
4
 *        LIKE pattern matching internal code.
 
5
 *
 
6
 * This file is included by like.c four times, to provide matching code for
 
7
 * (1) single-byte encodings, (2) UTF8, (3) other multi-byte encodings,
 
8
 * and (4) case insensitive matches in single byte encodings.
 
9
 * (UTF8 is a special case because we can use a much more efficient version
 
10
 * of NextChar than can be used for general multi-byte encodings.)
 
11
 *
 
12
 * Before the inclusion, we need to define following macros:
 
13
 *
 
14
 * NextChar
 
15
 * MatchText - to name of function wanted
 
16
 * do_like_escape - name of function if wanted - needs CHAREQ and CopyAdvChar
 
17
 * MATCH_LOWER - define iff using to_lower on text chars
 
18
 *
 
19
 * Copyright (c) 1996-2009, PostgreSQL Global Development Group
 
20
 *
 
21
 * IDENTIFICATION
 
22
 *      $PostgreSQL$
 
23
 *
 
24
 *-------------------------------------------------------------------------
 
25
 */
 
26
 
 
27
/*
 
28
**      Originally written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
 
29
**      Rich $alz is now <rsalz@bbn.com>.
 
30
**      Special thanks to Lars Mathiesen <thorinn@diku.dk> for the LABORT code.
 
31
**
 
32
**      This code was shamelessly stolen from the "pql" code by myself and
 
33
**      slightly modified :)
 
34
**
 
35
**      All references to the word "star" were replaced by "percent"
 
36
**      All references to the word "wild" were replaced by "like"
 
37
**
 
38
**      All the nice shell RE matching stuff was replaced by just "_" and "%"
 
39
**
 
40
**      As I don't have a copy of the SQL standard handy I wasn't sure whether
 
41
**      to leave in the '\' escape character handling.
 
42
**
 
43
**      Keith Parks. <keith@mtcc.demon.co.uk>
 
44
**
 
45
**      SQL92 lets you specify the escape character by saying
 
46
**      LIKE <pattern> ESCAPE <escape character>. We are a small operation
 
47
**      so we force you to use '\'. - ay 7/95
 
48
**
 
49
**      Now we have the like_escape() function that converts patterns with
 
50
**      any specified escape character (or none at all) to the internal
 
51
**      default escape character, which is still '\'. - tgl 9/2000
 
52
**
 
53
** The code is rewritten to avoid requiring null-terminated strings,
 
54
** which in turn allows us to leave out some memcpy() operations.
 
55
** This code should be faster and take less memory, but no promises...
 
56
** - thomas 2000-08-06
 
57
**
 
58
*/
 
59
 
 
60
 
 
61
/*--------------------
 
62
 *      Match text and p, return LIKE_TRUE, LIKE_FALSE, or LIKE_ABORT.
 
63
 *
 
64
 *      LIKE_TRUE: they match
 
65
 *      LIKE_FALSE: they don't match
 
66
 *      LIKE_ABORT: not only don't they match, but the text is too short.
 
67
 *
 
68
 * If LIKE_ABORT is returned, then no suffix of the text can match the
 
69
 * pattern either, so an upper-level % scan can stop scanning now.
 
70
 *--------------------
 
71
 */
 
72
 
 
73
#ifdef MATCH_LOWER
 
74
#define TCHAR(t) ((char) tolower((unsigned char) (t)))
 
75
#else
 
76
#define TCHAR(t) (t)
 
77
#endif
 
78
 
 
79
static int
 
80
MatchText(char *t, int tlen, char *p, int plen)
 
81
{
 
82
        /* Fast path for match-everything pattern */
 
83
        if ((plen == 1) && (*p == '%'))
 
84
                return LIKE_TRUE;
 
85
 
 
86
        /*
 
87
         * In this loop, we advance by char when matching wildcards (and thus on
 
88
         * recursive entry to this function we are properly char-synced). On other
 
89
         * occasions it is safe to advance by byte, as the text and pattern will
 
90
         * be in lockstep. This allows us to perform all comparisons  between the
 
91
         * text and pattern on a byte by byte basis, even for multi-byte
 
92
         * encodings.
 
93
         */
 
94
 
 
95
        while ((tlen > 0) && (plen > 0))
 
96
        {
 
97
                if (*p == '\\')
 
98
                {
 
99
                        /* Next pattern byte must match literally, whatever it is */
 
100
                        NextByte(p, plen);
 
101
                        /* ... and there had better be one, per SQL standard */
 
102
                        if (plen <= 0)
 
103
                                ereport(ERROR,
 
104
                                                (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
 
105
                                                 errmsg("LIKE pattern must not end with escape character")));
 
106
                        if (TCHAR(*p) != TCHAR(*t))
 
107
                                return LIKE_FALSE;
 
108
                }
 
109
                else if (*p == '%')
 
110
                {
 
111
                        /*
 
112
                         * % processing is essentially a search for a match for what
 
113
                         * follows the %, plus a recursive match of the remainder. We
 
114
                         * succeed if and only if both conditions are met.
 
115
                         */
 
116
 
 
117
                        /* %% is the same as % according to the SQL standard */
 
118
                        /* Advance past all %'s */
 
119
                        while ((plen > 0) && (*p == '%'))
 
120
                                NextByte(p, plen);
 
121
                        /* Trailing percent matches everything. */
 
122
                        if (plen <= 0)
 
123
                                return LIKE_TRUE;
 
124
 
 
125
                        /*
 
126
                         * Otherwise, scan for a text position at which we can match the
 
127
                         * rest of the pattern.
 
128
                         */
 
129
                        if (*p == '_')
 
130
 
 
131
                        {
 
132
                                /* %_ is the same as _% - avoid matching _ repeatedly */
 
133
 
 
134
                                NextChar(t, tlen);
 
135
                                NextByte(p, plen);
 
136
 
 
137
                                if (tlen <= 0)
 
138
                                {
 
139
                                        return (plen <= 0) ? LIKE_TRUE : LIKE_ABORT;
 
140
                                }
 
141
                                else if (plen <= 0)
 
142
                                {
 
143
                                        return LIKE_FALSE;
 
144
                                }
 
145
 
 
146
                                while (tlen > 0)
 
147
                                {
 
148
                                        int                     matched = MatchText(t, tlen, p, plen);
 
149
 
 
150
                                        if (matched != LIKE_FALSE)
 
151
                                                return matched; /* TRUE or ABORT */
 
152
 
 
153
                                        NextChar(t, tlen);
 
154
                                }
 
155
                        }
 
156
                        else
 
157
                        {
 
158
 
 
159
                                char            firstpat = TCHAR(*p);
 
160
 
 
161
                                if (*p == '\\')
 
162
                                {
 
163
                                        if (plen < 2)
 
164
                                                return LIKE_FALSE;
 
165
                                        firstpat = TCHAR(p[1]);
 
166
                                }
 
167
 
 
168
                                while (tlen > 0)
 
169
                                {
 
170
                                        /*
 
171
                                         * Optimization to prevent most recursion: don't recurse
 
172
                                         * unless first pattern byte matches first text byte.
 
173
                                         */
 
174
                                        if (TCHAR(*t) == firstpat)
 
175
                                        {
 
176
                                                int                     matched = MatchText(t, tlen, p, plen);
 
177
 
 
178
                                                if (matched != LIKE_FALSE)
 
179
                                                        return matched;         /* TRUE or ABORT */
 
180
                                        }
 
181
 
 
182
                                        NextChar(t, tlen);
 
183
 
 
184
                                }
 
185
                        }
 
186
 
 
187
                        /*
 
188
                         * End of text with no match, so no point in trying later places
 
189
                         * to start matching this pattern.
 
190
                         */
 
191
                        return LIKE_ABORT;
 
192
                }
 
193
                else if (*p == '_')
 
194
                {
 
195
                        NextChar(t, tlen);
 
196
                        NextByte(p, plen);
 
197
                        continue;
 
198
                }
 
199
                else if (TCHAR(*t) != TCHAR(*p))
 
200
                {
 
201
                        /*
 
202
                         * Not the single-character wildcard and no explicit match? Then
 
203
                         * time to quit...
 
204
                         */
 
205
                        return LIKE_FALSE;
 
206
                }
 
207
 
 
208
                /*
 
209
                 * It is safe to use NextByte instead of NextChar here, even for
 
210
                 * multi-byte character sets, because we are not following immediately
 
211
                 * after a wildcard character. If we are in the middle of a multibyte
 
212
                 * character, we must already have matched at least one byte of the
 
213
                 * character from both text and pattern; so we cannot get out-of-sync
 
214
                 * on character boundaries.  And we know that no backend-legal
 
215
                 * encoding allows ASCII characters such as '%' to appear as non-first
 
216
                 * bytes of characters, so we won't mistakenly detect a new wildcard.
 
217
                 */
 
218
                NextByte(t, tlen);
 
219
                NextByte(p, plen);
 
220
        }
 
221
 
 
222
        if (tlen > 0)
 
223
                return LIKE_FALSE;              /* end of pattern, but not of text */
 
224
 
 
225
        /* End of input string.  Do we have matching pattern remaining? */
 
226
        while ((plen > 0) && (*p == '%'))       /* allow multiple %'s at end of
 
227
                                                                                 * pattern */
 
228
                NextByte(p, plen);
 
229
 
 
230
        if (plen <= 0)
 
231
                return LIKE_TRUE;
 
232
 
 
233
        /*
 
234
         * End of text with no match, so no point in trying later places to start
 
235
         * matching this pattern.
 
236
         */
 
237
        return LIKE_ABORT;
 
238
}       /* MatchText() */
 
239
 
 
240
/*
 
241
 * like_escape() --- given a pattern and an ESCAPE string,
 
242
 * convert the pattern to use Postgres' standard backslash escape convention.
 
243
 */
 
244
#ifdef do_like_escape
 
245
 
 
246
static text *
 
247
do_like_escape(text *pat, text *esc)
 
248
{
 
249
        text       *result;
 
250
        char       *p,
 
251
                           *e,
 
252
                           *r;
 
253
        int                     plen,
 
254
                                elen;
 
255
        bool            afterescape;
 
256
 
 
257
        p = VARDATA_ANY(pat);
 
258
        plen = VARSIZE_ANY_EXHDR(pat);
 
259
        e = VARDATA_ANY(esc);
 
260
        elen = VARSIZE_ANY_EXHDR(esc);
 
261
 
 
262
        /*
 
263
         * Worst-case pattern growth is 2x --- unlikely, but it's hardly worth
 
264
         * trying to calculate the size more accurately than that.
 
265
         */
 
266
        result = (text *) palloc(plen * 2 + VARHDRSZ);
 
267
        r = VARDATA(result);
 
268
 
 
269
        if (elen == 0)
 
270
        {
 
271
                /*
 
272
                 * No escape character is wanted.  Double any backslashes in the
 
273
                 * pattern to make them act like ordinary characters.
 
274
                 */
 
275
                while (plen > 0)
 
276
                {
 
277
                        if (*p == '\\')
 
278
                                *r++ = '\\';
 
279
                        CopyAdvChar(r, p, plen);
 
280
                }
 
281
        }
 
282
        else
 
283
        {
 
284
                /*
 
285
                 * The specified escape must be only a single character.
 
286
                 */
 
287
                NextChar(e, elen);
 
288
                if (elen != 0)
 
289
                        ereport(ERROR,
 
290
                                        (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
 
291
                                         errmsg("invalid escape string"),
 
292
                                  errhint("Escape string must be empty or one character.")));
 
293
 
 
294
                e = VARDATA_ANY(esc);
 
295
 
 
296
                /*
 
297
                 * If specified escape is '\', just copy the pattern as-is.
 
298
                 */
 
299
                if (*e == '\\')
 
300
                {
 
301
                        memcpy(result, pat, VARSIZE_ANY(pat));
 
302
                        return result;
 
303
                }
 
304
 
 
305
                /*
 
306
                 * Otherwise, convert occurrences of the specified escape character to
 
307
                 * '\', and double occurrences of '\' --- unless they immediately
 
308
                 * follow an escape character!
 
309
                 */
 
310
                afterescape = false;
 
311
                while (plen > 0)
 
312
                {
 
313
                        if (CHAREQ(p, e) && !afterescape)
 
314
                        {
 
315
                                *r++ = '\\';
 
316
                                NextChar(p, plen);
 
317
                                afterescape = true;
 
318
                        }
 
319
                        else if (*p == '\\')
 
320
                        {
 
321
                                *r++ = '\\';
 
322
                                if (!afterescape)
 
323
                                        *r++ = '\\';
 
324
                                NextChar(p, plen);
 
325
                                afterescape = false;
 
326
                        }
 
327
                        else
 
328
                        {
 
329
                                CopyAdvChar(r, p, plen);
 
330
                                afterescape = false;
 
331
                        }
 
332
                }
 
333
        }
 
334
 
 
335
        SET_VARSIZE(result, r - ((char *) result));
 
336
 
 
337
        return result;
 
338
}
 
339
#endif   /* do_like_escape */
 
340
 
 
341
#ifdef CHAREQ
 
342
#undef CHAREQ
 
343
#endif
 
344
 
 
345
#undef NextChar
 
346
#undef CopyAdvChar
 
347
#undef MatchText
 
348
 
 
349
#ifdef do_like_escape
 
350
#undef do_like_escape
 
351
#endif
 
352
 
 
353
#undef TCHAR
 
354
 
 
355
#ifdef MATCH_LOWER
 
356
#undef MATCH_LOWER
 
357
 
 
358
#endif