initial commitHEADmaster

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;
+}