summaryrefslogtreecommitdiff
path: root/src/match.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/match.c')
-rw-r--r--src/match.c443
1 files changed, 443 insertions, 0 deletions
diff --git a/src/match.c b/src/match.c
new file mode 100644
index 0000000..f5ca1ad
--- /dev/null
+++ b/src/match.c
@@ -0,0 +1,443 @@
+/*
+** Copyright (c) 2007 D. Richard Hipp
+**
+** This program is free software; you can redistribute it and/or
+** modify it under the terms of the Simplified BSD License (also
+** known as the "2-Clause License" or "FreeBSD License".)
+
+** This program is distributed in the hope that it will be useful,
+** but without any warranty; without even the implied warranty of
+** merchantability or fitness for a particular purpose.
+**
+** Author contact information:
+** drh@hwaci.com
+** http://www.hwaci.com/drh/
+**
+*******************************************************************************
+**
+** This file contains code to implement string comparisons using a
+** variety of algorithm. The comparison algorithm can be any of:
+**
+** MS_EXACT The string must exactly match the pattern.
+**
+** MS_BRLIST The pattern is a space- and/or comma-separated
+** list of strings, any one of which may match
+** the input string.
+**
+** MS_GLOB Like BRLIST, except each component of the pattern
+** is a GLOB expression.
+**
+** MS_LIKE Like BRLIST, except each component of the pattern
+** is an SQL LIKE expression.
+**
+** MS_REGEXP Like BRLIST, except each component of the pattern
+** is a regular expression.
+**
+*/
+#include "config.h"
+#include <string.h>
+#include "match.h"
+
+#if INTERFACE
+/*
+** Types of comparisons that we are able to perform:
+*/
+typedef enum {
+ MS_EXACT=1, /* Exact string comparison */
+ MS_GLOB=2, /* Matches against a list of GLOB patterns. */
+ MS_LIKE=3, /* Matches against a list of LIKE patterns. */
+ MS_REGEXP=4, /* Matches against a list of regular expressions. */
+ MS_BRLIST=5, /* Matches any element of a list */
+} MatchStyle;
+
+/*
+** The following object represents a precompiled pattern to use for
+** string matching.
+**
+** * Create an instance of this object using match_create().
+** * Do comparisons using match_text().
+** * Destroy using match_free() when you are done.
+**
+*/
+struct Matcher {
+ MatchStyle style; /* Which algorithm to use */
+ int nPattern; /* How many patterns are their */
+ char **azPattern; /* List of patterns */
+ ReCompiled **aRe; /* List of compiled regular expressions */
+};
+
+#endif /*INTERFACE*/
+
+/*
+** Translate a "match style" text name into the MS_* enum value.
+** Return eDflt if no match is found.
+*/
+MatchStyle match_style(const char *zStyle, MatchStyle eDflt){
+ if( zStyle==0 ) return eDflt;
+ if( fossil_stricmp(zStyle, "brlist")==0 ) return MS_BRLIST;
+ if( fossil_stricmp(zStyle, "list")==0 ) return MS_BRLIST;
+ if( fossil_stricmp(zStyle, "regexp")==0 ) return MS_REGEXP;
+ if( fossil_stricmp(zStyle, "re")==0 ) return MS_REGEXP;
+ if( fossil_stricmp(zStyle, "glob")==0 ) return MS_GLOB;
+ if( fossil_stricmp(zStyle, "like")==0 ) return MS_LIKE;
+ if( fossil_stricmp(zStyle, "exact")==0 ) return MS_EXACT;
+ return eDflt;
+}
+
+
+/*
+** Create a new Matcher object using the pattern provided.
+*/
+Matcher *match_create(MatchStyle style, const char *zPat){
+ char cDel; /* Delimiter character */
+ int i; /* Loop counter */
+ Matcher *p; /* The new Matcher to be constructed */
+ char *zOne; /* One element of the pattern */
+
+ if( zPat==0 ) return 0;
+ p = fossil_malloc( sizeof(*p) );
+ memset(p, 0, sizeof(*p));
+ p->style = style;
+
+ if( style==MS_EXACT ){
+ p->nPattern = 1;
+ p->azPattern = fossil_malloc( sizeof(p->azPattern[0]) );
+ p->azPattern[0] = fossil_strdup(zPat);
+ return p;
+ }
+
+ while( 1 ){
+ /* Skip leading delimiters. */
+ for( ; fossil_isspace(*zPat) || *zPat==','; ++zPat );
+
+ /* Next non-delimiter character determines quoting. */
+ if( zPat[0]==0 ){
+ /* Terminate loop at end of string. */
+ break;
+ }else if( zPat[0]=='\'' || zPat[0]=='"' ){
+ /* If word is quoted, prepare to stop at end quote. */
+ cDel = zPat[0];
+ ++zPat;
+ }else{
+ /* If word is not quoted, prepare to stop at delimiter. */
+ cDel = ',';
+ }
+
+ /* Find the next delimiter character or end of string. */
+ for( i=0; zPat[i] && zPat[i]!=cDel; ++i ){
+ /* If delimiter is comma, also recognize spaces as delimiters. */
+ if( cDel==',' && fossil_isspace(zPat[i]) ){
+ break;
+ }
+
+ /* In regexp mode, ignore delimiters following backslashes. */
+ if( style==MS_REGEXP && zPat[i]=='\\' && zPat[i+1] ){
+ ++i;
+ }
+ }
+
+ /* zOne is a zero-terminated copy of the pattern, without delimiters */
+ zOne = fossil_strndup(zPat, i);
+ zPat += i;
+ if( zPat[0] ) zPat++;
+
+ /* Check for regular expression syntax errors. */
+ if( style==MS_REGEXP ){
+ ReCompiled *regexp;
+ const char *zFail = fossil_re_compile(&regexp, zOne, 0);
+ if( zFail ){
+ re_free(regexp);
+ continue;
+ }
+ p->nPattern++;
+ p->aRe = fossil_realloc(p->aRe, sizeof(p->aRe)*p->nPattern);
+ p->aRe[p->nPattern-1] = regexp;
+ fossil_free(zOne);
+ }else{
+ p->nPattern++;
+ p->azPattern = fossil_realloc(p->azPattern, sizeof(char*)*p->nPattern);
+ p->azPattern[p->nPattern-1] = zOne;
+ }
+ }
+ return p;
+}
+
+/*
+** Return non-zero (true) if the input string matches the pattern
+** described by the matcher.
+**
+** The return value is really the 1-based index of the particular
+** pattern that matched.
+*/
+int match_text(Matcher *p, const char *zText){
+ int i;
+ if( p==0 ){
+ return zText==0;
+ }
+ switch( p->style ){
+ case MS_BRLIST:
+ case MS_EXACT: {
+ for(i=0; i<p->nPattern; i++){
+ if( strcmp(p->azPattern[i], zText)==0 ) return i+1;
+ }
+ break;
+ }
+ case MS_GLOB: {
+ for(i=0; i<p->nPattern; i++){
+ if( sqlite3_strglob(p->azPattern[i], zText)==0 ) return i+1;
+ }
+ break;
+ }
+ case MS_LIKE: {
+ for(i=0; i<p->nPattern; i++){
+ if( sqlite3_strlike(p->azPattern[i], zText, 0)==0 ) return i+1;
+ }
+ break;
+ }
+ case MS_REGEXP: {
+ int nText = (int)strlen(zText);
+ for(i=0; i<p->nPattern; i++){
+ if( re_match(p->aRe[i], (const u8*)zText, nText) ) return i+1;
+ }
+ break;
+ }
+ }
+ return 0;
+}
+
+
+/*
+** Destroy a previously allocated Matcher object.
+*/
+void match_free(Matcher *p){
+ int i;
+ if( p==0 ) return;
+ if( p->style==MS_REGEXP ){
+ for(i=0; i<p->nPattern; i++) re_free(p->aRe[i]);
+ fossil_free(p->aRe);
+ }else{
+ for(i=0; i<p->nPattern; i++) fossil_free(p->azPattern[i]);
+ fossil_free(p->azPattern);
+ }
+ memset(p, 0, sizeof(*p));
+ fossil_free(p);
+}
+
+
+
+/*
+** Quote a tag string by surrounding it with double quotes and preceding
+** internal double quotes and backslashes with backslashes.
+*/
+static const char *tagQuote(
+ int len, /* Maximum length of zTag, or negative for unlimited */
+ const char *zTag /* Tag string */
+){
+ Blob blob = BLOB_INITIALIZER;
+ int i, j;
+ blob_zero(&blob);
+ blob_append(&blob, "\"", 1);
+ for( i=j=0; zTag[j] && (len<0 || j<len); ++j ){
+ if( zTag[j]=='\"' || zTag[j]=='\\' ){
+ if( j>i ){
+ blob_append(&blob, zTag+i, j-i);
+ }
+ blob_append(&blob, "\\", 1);
+ i = j;
+ }
+ }
+ if( j>i ){
+ blob_append(&blob, zTag+i, j-i);
+ }
+ blob_append(&blob, "\"", 1);
+ return blob_str(&blob);
+}
+
+/*
+** Construct the SQL expression that goes into the WHERE clause of a join
+** that involves the TAG table and that selects a particular tag out of
+** that table.
+**
+** This function is adapted from glob_expr() to support the MS_EXACT, MS_GLOB,
+** MS_LIKE, MS_REGEXP, and MS_BRLIST match styles.
+**
+** For MS_EXACT, the returned expression
+** checks for integer match against the tag ID which is looked up directly by
+** this function. For the other modes, the returned SQL expression performs
+** string comparisons against the tag names, so it is necessary to join against
+** the tag table to access the "tagname" column.
+**
+** Each pattern is adjusted to start with "sym-" and be anchored at end.
+**
+** In MS_REGEXP mode, backslash can be used to protect delimiter characters.
+** The backslashes are not removed from the regular expression.
+**
+** In addition to assembling and returning an SQL expression, this function
+** makes an English-language description of the patterns being matched, suitable
+** for display in the web interface.
+**
+** If any errors arise during processing, *zError is set to an error message.
+** Otherwise it is set to NULL.
+*/
+const char *match_tag_sqlexpr(
+ MatchStyle matchStyle, /* Match style code */
+ const char *zTag, /* Tag name, match pattern, or pattern list */
+ const char **zDesc, /* Output expression description string */
+ const char **zError /* Output error string */
+){
+ Blob expr = BLOB_INITIALIZER; /* SQL expression string assembly buffer */
+ Blob desc = BLOB_INITIALIZER; /* English description of match patterns */
+ Blob err = BLOB_INITIALIZER; /* Error text assembly buffer */
+ const char *zStart; /* Text at start of expression */
+ const char *zDelimiter; /* Text between expression terms */
+ const char *zEnd; /* Text at end of expression */
+ const char *zPrefix; /* Text before each match pattern */
+ const char *zSuffix; /* Text after each match pattern */
+ const char *zIntro; /* Text introducing pattern description */
+ const char *zPattern = 0; /* Previous quoted pattern */
+ const char *zFail = 0; /* Current failure message or NULL if okay */
+ const char *zOr = " or "; /* Text before final quoted pattern */
+ char cDel; /* Input delimiter character */
+ int i; /* Input match pattern length counter */
+
+ /* Optimize exact matches by looking up the ID in advance to create a simple
+ * numeric comparison. Bypass the remainder of this function. */
+ if( matchStyle==MS_EXACT ){
+ *zDesc = tagQuote(-1, zTag);
+ return mprintf("(tagid=%d)", db_int(-1,
+ "SELECT tagid FROM tag WHERE tagname='sym-%q'", zTag));
+ }
+
+ /* Decide pattern prefix and suffix strings according to match style. */
+ if( matchStyle==MS_GLOB ){
+ zStart = "(";
+ zDelimiter = " OR ";
+ zEnd = ")";
+ zPrefix = "tagname GLOB 'sym-";
+ zSuffix = "'";
+ zIntro = "glob pattern ";
+ }else if( matchStyle==MS_LIKE ){
+ zStart = "(";
+ zDelimiter = " OR ";
+ zEnd = ")";
+ zPrefix = "tagname LIKE 'sym-";
+ zSuffix = "'";
+ zIntro = "SQL LIKE pattern ";
+ }else if( matchStyle==MS_REGEXP ){
+ zStart = "(tagname REGEXP '^sym-(";
+ zDelimiter = "|";
+ zEnd = ")$')";
+ zPrefix = "";
+ zSuffix = "";
+ zIntro = "regular expression ";
+ }else/* if( matchStyle==MS_BRLIST )*/{
+ zStart = "tagname IN ('sym-";
+ zDelimiter = "','sym-";
+ zEnd = "')";
+ zPrefix = "";
+ zSuffix = "";
+ zIntro = "";
+ }
+
+ /* Convert the list of matches into an SQL expression and text description. */
+ blob_zero(&expr);
+ blob_zero(&desc);
+ blob_zero(&err);
+ while( 1 ){
+ /* Skip leading delimiters. */
+ for( ; fossil_isspace(*zTag) || *zTag==','; ++zTag );
+
+ /* Next non-delimiter character determines quoting. */
+ if( !*zTag ){
+ /* Terminate loop at end of string. */
+ break;
+ }else if( *zTag=='\'' || *zTag=='"' ){
+ /* If word is quoted, prepare to stop at end quote. */
+ cDel = *zTag;
+ ++zTag;
+ }else{
+ /* If word is not quoted, prepare to stop at delimiter. */
+ cDel = ',';
+ }
+
+ /* Find the next delimiter character or end of string. */
+ for( i=0; zTag[i] && zTag[i]!=cDel; ++i ){
+ /* If delimiter is comma, also recognize spaces as delimiters. */
+ if( cDel==',' && fossil_isspace(zTag[i]) ){
+ break;
+ }
+
+ /* In regexp mode, ignore delimiters following backslashes. */
+ if( matchStyle==MS_REGEXP && zTag[i]=='\\' && zTag[i+1] ){
+ ++i;
+ }
+ }
+
+ /* Check for regular expression syntax errors. */
+ if( matchStyle==MS_REGEXP ){
+ ReCompiled *regexp;
+ char *zTagDup = fossil_strndup(zTag, i);
+ zFail = fossil_re_compile(&regexp, zTagDup, 0);
+ re_free(regexp);
+ fossil_free(zTagDup);
+ }
+
+ /* Process success and error results. */
+ if( !zFail ){
+ /* Incorporate the match word into the output expression. %q is used to
+ * protect against SQL injection attacks by replacing ' with ''. */
+ blob_appendf(&expr, "%s%s%#q%s", blob_size(&expr) ? zDelimiter : zStart,
+ zPrefix, i, zTag, zSuffix);
+
+ /* Build up the description string. */
+ if( !blob_size(&desc) ){
+ /* First tag: start with intro followed by first quoted tag. */
+ blob_append(&desc, zIntro, -1);
+ blob_append(&desc, tagQuote(i, zTag), -1);
+ }else{
+ if( zPattern ){
+ /* Third and subsequent tags: append comma then previous tag. */
+ blob_append(&desc, ", ", 2);
+ blob_append(&desc, zPattern, -1);
+ zOr = ", or ";
+ }
+
+ /* Second and subsequent tags: store quoted tag for next iteration. */
+ zPattern = tagQuote(i, zTag);
+ }
+ }else{
+ /* On error, skip the match word and build up the error message buffer. */
+ if( !blob_size(&err) ){
+ blob_append(&err, "Error: ", 7);
+ }else{
+ blob_append(&err, ", ", 2);
+ }
+ blob_appendf(&err, "(%s%s: %s)", zIntro, tagQuote(i, zTag), zFail);
+ }
+
+ /* Advance past all consumed input characters. */
+ zTag += i;
+ if( cDel!=',' && *zTag==cDel ){
+ ++zTag;
+ }
+ }
+
+ /* Finalize and extract the pattern description. */
+ if( zPattern ){
+ blob_append(&desc, zOr, -1);
+ blob_append(&desc, zPattern, -1);
+ }
+ *zDesc = blob_str(&desc);
+
+ /* Finalize and extract the error text. */
+ *zError = blob_size(&err) ? blob_str(&err) : 0;
+
+ /* Finalize and extract the SQL expression. */
+ if( blob_size(&expr) ){
+ blob_append(&expr, zEnd, -1);
+ return blob_str(&expr);
+ }
+
+ /* If execution reaches this point, the pattern was empty. Return NULL. */
+ return 0;
+}
generated by cgit v1.3.1 (git 2.54.0) at 2026-10-17 06:24:01 +0000