Changeset cafd8d281bdf982e2ac0b84d57dfbf9fed46603c

Timestamp:

04/22/08 00:10:15 (9 months ago)

Author:

dave <dave@…>

Parents:

8c94483694f5774d39acb4072885476c45d9b571

Children:

c929863ac8839608b81f31d8c7877cb11792961e, 83fedc095fb017076709f408095674cd9fd05ecc, c93e31a2e50bb75c511e0b1553d7311ec0335cce

git-committer:

dave <dave@06fd6eb0-0002-0410-a719-e5602cce40bc> / 2008-04-21T14:10:15Z+0000

Message:

Started detailed documentation of the QueryParser

In writing the documentation I've spotted a pretty serious bug in the
QueryParser. Fields need to be pushed onto a stack as they are specified,
otherwise the parser is quite broken for multi-level, multi-field queries. I'll
fix this first thing tomorrow before finishing this documentation. Comments on
the documentation are welcome.

git-svn-id: svn+ssh://davebalmain.com/home/dave/repos/ferret/trunk@1031 06fd6eb0-0002-0410-a719-e5602cce40bc

Files:

• TODO (modified) (3 diffs)
• c/TODO (modified) (1 diff)
• c/src/q_parser.c (modified) (7 diffs)
• c/src/q_parser.y (modified) (2 diffs)

TODO

@@ -20 +20 @@
     useful for storing field names so that no objects need to strdup the
     field-names but can just store the symbol representative instead.
+    + this has been done but it can be improved using actual Symbol structs
+      instead of plain char*
   - Make threading optional at compile time
   - to_json should limit output to prevent memory overflow on large indexes.
@@ -34 +36 @@
   - Auto-loading of documents during search. ie actual documents get returned
     instead of document numbers.
-  - update benchmark suite to use getrusage.u
 
 * Ruby bindings
@@ -106 +107 @@
   + Working Query:  field1:value1 AND NOT field2:value2
   + Failing Query:    field1:value1 AND ( NOT field2:value2 )
-
+* update benchmark suite to use getrusage

c/TODO

@@ -4 +4 @@
 
 benchmarks
-* string actions when length is known
 * standard tokenizer
-* writevint

c/src/q_parser.c

@@ -99 +99 @@
 
 /* Copy the first part of user declarations.  */
-#line 1 "src/q_parser.y"
+#line 3 "src/q_parser.y"
 
 #include <string.h>
@@ -149 +149 @@
 #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
 typedef union YYSTYPE
-#line 29 "src/q_parser.y"
+#line 31 "src/q_parser.y"
 {
     Query *query;
@@ -169 +169 @@
 
 /* Copy the second part of user declarations.  */
-#line 37 "src/q_parser.y"
+#line 39 "src/q_parser.y"
 
 static int yylex(YYSTYPE *lvalp, QParser *qp);
@@ -549 +549 @@
 static const yytype_uint8 yyrline[] =
 {
-       0,   131,   131,   132,   134,   135,   136,   137,   139,   140,
-     141,   143,   144,   146,   147,   148,   149,   150,   151,   152,
-     154,   155,   156,   158,   160,   160,   162,   162,   162,   165,
-     166,   168,   169,   170,   171,   173,   174,   175,   176,   177,
-     179,   180,   181,   182,   183,   184,   185,   186,   187,   188,
-     189,   190
+       0,   133,   133,   134,   136,   137,   138,   139,   141,   142,
+     143,   145,   146,   148,   149,   150,   151,   152,   153,   154,
+     156,   157,   158,   160,   162,   162,   164,   164,   164,   167,
+     168,   170,   171,   172,   173,   175,   176,   177,   178,   179,
+     181,   182,   183,   184,   185,   186,   187,   188,   189,   190,
+     191,   192
 };
 #endif
@@ -1213 +1213 @@
     {
       case 27: /* "bool_q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1218 "src/q_parser.c"
         break;
       case 28: /* "bool_clss" */
-#line 128 "src/q_parser.y"
+#line 130 "src/q_parser.y"
         { if ((yyvaluep->bclss) && qp->destruct) bca_destroy((yyvaluep->bclss)); };
 #line 1223 "src/q_parser.c"
         break;
       case 29: /* "bool_cls" */
-#line 127 "src/q_parser.y"
+#line 129 "src/q_parser.y"
         { if ((yyvaluep->bcls) && qp->destruct) bc_deref((yyvaluep->bcls)); };
 #line 1228 "src/q_parser.c"
         break;
       case 30: /* "boosted_q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1233 "src/q_parser.c"
         break;
       case 31: /* "q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1238 "src/q_parser.c"
         break;
       case 32: /* "term_q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1243 "src/q_parser.c"
         break;
       case 33: /* "wild_q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1248 "src/q_parser.c"
         break;
       case 34: /* "field_q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1253 "src/q_parser.c"
         break;
       case 39: /* "phrase_q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1258 "src/q_parser.c"
         break;
       case 40: /* "ph_words" */
-#line 129 "src/q_parser.y"
+#line 131 "src/q_parser.y"
         { if ((yyvaluep->phrase) && qp->destruct) ph_destroy((yyvaluep->phrase)); };
 #line 1263 "src/q_parser.c"
         break;
       case 41: /* "range_q" */
-#line 126 "src/q_parser.y"
+#line 128 "src/q_parser.y"
         { if ((yyvaluep->query) && qp->destruct) q_deref((yyvaluep->query)); };
 #line 1268 "src/q_parser.c"
@@ -1574 +1574 @@
     {
         case 2:
-#line 131 "src/q_parser.y"
+#line 133 "src/q_parser.y"
     {   qp->result = (yyval.query) = NULL; }
     break;
 
   case 3:
-#line 132 "src/q_parser.y"
+#line 134 "src/q_parser.y"
     { T qp->result = (yyval.query) = get_bool_q((yyvsp[(1) - (1)].bclss)); E }
     break;
 
   case 4:
-#line 134 "src/q_parser.y"
+#line 136 "src/q_parser.y"
     { T (yyval.bclss) = first_cls((yyvsp[(1) - (1)].bcls)); E }
     break;
 
   case 5:
-#line 135 "src/q_parser.y"
+#line 137 "src/q_parser.y"
     { T (yyval.bclss) = add_and_cls((yyvsp[(1) - (3)].bclss), (yyvsp[(3) - (3)].bcls)); E }
     break;
 
   case 6:
-#line 136 "src/q_parser.y"
+#line 138 "src/q_parser.y"
     { T (yyval.bclss) = add_or_cls((yyvsp[(1) - (3)].bclss), (yyvsp[(3) - (3)].bcls)); E }
     break;
 
   case 7:
-#line 137 "src/q_parser.y"
+#line 139 "src/q_parser.y"
     { T (yyval.bclss) = add_default_cls(qp, (yyvsp[(1) - (2)].bclss), (yyvsp[(2) - (2)].bcls)); E }
     break;
 
   case 8:
-#line 139 "src/q_parser.y"
+#line 141 "src/q_parser.y"
     { T (yyval.bcls) = get_bool_cls((yyvsp[(2) - (2)].query), BC_MUST); E }
     break;
 
   case 9:
-#line 140 "src/q_parser.y"
+#line 142 "src/q_parser.y"
     { T (yyval.bcls) = get_bool_cls((yyvsp[(2) - (2)].query), BC_MUST_NOT); E }
     break;
 
   case 10:
-#line 141 "src/q_parser.y"
+#line 143 "src/q_parser.y"
     { T (yyval.bcls) = get_bool_cls((yyvsp[(1) - (1)].query), BC_SHOULD); E }
     break;
 
   case 12:
-#line 144 "src/q_parser.y"
+#line 146 "src/q_parser.y"
     { T if ((yyvsp[(1) - (3)].query)) sscanf((yyvsp[(3) - (3)].str),"%f",&((yyvsp[(1) - (3)].query)->boost));  (yyval.query)=(yyvsp[(1) - (3)].query); E }
     break;
 
   case 14:
-#line 147 "src/q_parser.y"
+#line 149 "src/q_parser.y"
     { T (yyval.query) = bq_new_max(true, qp->max_clauses); E }
     break;
 
   case 15:
-#line 148 "src/q_parser.y"
+#line 150 "src/q_parser.y"
     { T (yyval.query) = get_bool_q((yyvsp[(2) - (3)].bclss)); E }
     break;
 
   case 20:
-#line 154 "src/q_parser.y"
+#line 156 "src/q_parser.y"
     { FLDS((yyval.query), get_term_q(qp, field, (yyvsp[(1) - (1)].str))); Y}
     break;
 
   case 21:
-#line 155 "src/q_parser.y"
+#line 157 "src/q_parser.y"
     { FLDS((yyval.query), get_fuzzy_q(qp, field, (yyvsp[(1) - (3)].str), (yyvsp[(3) - (3)].str))); Y}
     break;
 
   case 22:
-#line 156 "src/q_parser.y"
+#line 158 "src/q_parser.y"
     { FLDS((yyval.query), get_fuzzy_q(qp, field, (yyvsp[(1) - (2)].str), NULL)); Y}
     break;
 
   case 23:
-#line 158 "src/q_parser.y"
+#line 160 "src/q_parser.y"
     { FLDS((yyval.query), get_wild_q(qp, field, (yyvsp[(1) - (1)].str))); Y}
     break;
 
   case 24:
-#line 160 "src/q_parser.y"
+#line 162 "src/q_parser.y"
     { qp->fields = qp->def_fields; }
     break;
 
   case 25:
-#line 161 "src/q_parser.y"
+#line 163 "src/q_parser.y"
     { (yyval.query) = (yyvsp[(3) - (4)].query); }
     break;
 
   case 26:
-#line 162 "src/q_parser.y"
+#line 164 "src/q_parser.y"
     { qp->fields = qp->all_fields; }
     break;
 
   case 27:
-#line 162 "src/q_parser.y"
+#line 164 "src/q_parser.y"
     {qp->fields = qp->def_fields;}
     break;
 
   case 28:
-#line 163 "src/q_parser.y"
+#line 165 "src/q_parser.y"
     { (yyval.query) = (yyvsp[(4) - (5)].query); }
     break;
 
   case 29:
-#line 165 "src/q_parser.y"
+#line 167 "src/q_parser.y"
     { (yyval.hashset) = first_field(qp, (yyvsp[(1) - (1)].str)); }
     break;
 
   case 30:
-#line 166 "src/q_parser.y"
+#line 168 "src/q_parser.y"
     { (yyval.hashset) = add_field(qp, (yyvsp[(3) - (3)].str));}
     break;
 
   case 31:
-#line 168 "src/q_parser.y"
+#line 170 "src/q_parser.y"
     { (yyval.query) = get_phrase_q(qp, (yyvsp[(2) - (3)].phrase), NULL); }
     break;
 
   case 32:
-#line 169 "src/q_parser.y"
+#line 171 "src/q_parser.y"
     { (yyval.query) = get_phrase_q(qp, (yyvsp[(2) - (5)].phrase), (yyvsp[(5) - (5)].str)); }
     break;
 
   case 33:
-#line 170 "src/q_parser.y"
+#line 172 "src/q_parser.y"
     { (yyval.query) = NULL; }
     break;
 
   case 34:
-#line 171 "src/q_parser.y"
+#line 173 "src/q_parser.y"
     { (yyval.query) = NULL; (void)(yyvsp[(4) - (4)].str);}
     break;
 
   case 35:
-#line 173 "src/q_parser.y"
+#line 175 "src/q_parser.y"
     { (yyval.phrase) = ph_first_word((yyvsp[(1) - (1)].str)); }
     break;
 
   case 36:
-#line 174 "src/q_parser.y"
+#line 176 "src/q_parser.y"
     { (yyval.phrase) = ph_first_word(NULL); }
     break;
 
   case 37:
-#line 175 "src/q_parser.y"
+#line 177 "src/q_parser.y"
     { (yyval.phrase) = ph_add_word((yyvsp[(1) - (2)].phrase), (yyvsp[(2) - (2)].str)); }
     break;
 
   case 38:
-#line 176 "src/q_parser.y"
+#line 178 "src/q_parser.y"
     { (yyval.phrase) = ph_add_word((yyvsp[(1) - (3)].phrase), NULL); }
     break;
 
   case 39:
-#line 177 "src/q_parser.y"
+#line 179 "src/q_parser.y"
     { (yyval.phrase) = ph_add_multi_word((yyvsp[(1) - (3)].phrase), (yyvsp[(3) - (3)].str));  }
     break;
 
   case 40:
-#line 179 "src/q_parser.y"
+#line 181 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(2) - (4)].str),  (yyvsp[(3) - (4)].str),  true,  true)); Y}
     break;
 
   case 41:
-#line 180 "src/q_parser.y"
+#line 182 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(2) - (4)].str),  (yyvsp[(3) - (4)].str),  true,  false)); Y}
     break;
 
   case 42:
-#line 181 "src/q_parser.y"
+#line 183 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(2) - (4)].str),  (yyvsp[(3) - (4)].str),  false, true)); Y}
     break;
 
   case 43:
-#line 182 "src/q_parser.y"
+#line 184 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(2) - (4)].str),  (yyvsp[(3) - (4)].str),  false, false)); Y}
     break;
 
   case 44:
-#line 183 "src/q_parser.y"
+#line 185 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, NULL,(yyvsp[(2) - (3)].str),  false, false)); Y}
     break;
 
   case 45:
-#line 184 "src/q_parser.y"
+#line 186 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, NULL,(yyvsp[(2) - (3)].str),  false, true)); Y}
     break;
 
   case 46:
-#line 185 "src/q_parser.y"
+#line 187 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(2) - (3)].str),  NULL,true,  false)); Y}
     break;
 
   case 47:
-#line 186 "src/q_parser.y"
+#line 188 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(2) - (3)].str),  NULL,false, false)); Y}
     break;
 
   case 48:
-#line 187 "src/q_parser.y"
+#line 189 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, NULL,(yyvsp[(2) - (2)].str),  false, false)); Y}
     break;
 
   case 49:
-#line 188 "src/q_parser.y"
+#line 190 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, NULL,(yyvsp[(3) - (3)].str),  false, true)); Y}
     break;
 
   case 50:
-#line 189 "src/q_parser.y"
+#line 191 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(3) - (3)].str),  NULL,true,  false)); Y}
     break;
 
   case 51:
-#line 190 "src/q_parser.y"
+#line 192 "src/q_parser.y"
     { FLDS((yyval.query), get_r_q(qp, field, (yyvsp[(2) - (2)].str),  NULL,false, false)); Y}
     break;
@@ -2009 +2009 @@
 
 
-#line 192 "src/q_parser.y"
+#line 194 "src/q_parser.y"
 
 

c/src/q_parser.y

@@ +1 @@
+/*****************************************************************************
+ * QueryParser
+ * ===========
+ *
+ * Synopsis
+ * --------
+ *
+ * === qp_parse
+ *
+ * The main QueryParser method is +qp_parse+. It gets called with a the query
+ * string. The first thing it does is to clean the query string if
+ * ((QueryParser *)self)->clean_str is set to true. The cleaning is done with
+ * the qp_clean_str.
+ * 
+ * It then calls the yacc parser which will set self->result to the parsed
+ * query. If parsing fails in anyway, self->result should be set to NULL, in
+ * which case qp_parse does one of two things, depending on the value of
+ * self->handle_parse_errors. If it is set to true, qp_parse attempts to do a
+ * very basic parsing of the query by ignoring all special characters and
+ * parsing the query as a plain boolean query. If it is set to false, qp_parse
+ * will raise a PARSE_ERROR.
+ * 
+ * === The Lexer
+ *
+ * yylex is the lexing method called by the QueryParser. It breaks the query
+ * up into special characters ( "&:()[]{}!\"~^|<>=*?+-" ) and tokens (QWRD,
+ * WILD_STR, AND['AND', '&&'], OR['OR', '||'], REQ['REQ', '+'], NOT['NOT',
+ * '-', '~']). QWRD tokens are query word tokens which are made up of
+ * characters other than the special characters. They can also contain special
+ * characters when escaped with a backslash '\'. WILD_STR is the same as QWRD
+ * except that it may also contain '?' and '*' characters.
+ *
+ * === The Parser
+ *
+ * For a better understanding of the how the query parser works, it is a good
+ * idea to study the Ferret Query Language (FQL) described below. Once you
+ * understand FQL the one tricky part that needs to be mentioned is how fields
+ * are handled. The QueryParser knows about two sets of fields, the default
+ * search fields and the set of all fields in the index. When no fields are
+ * specified then the default fields are used. The '*:' field specifier will
+ * search all fields contained in the all_fields set. Otherwise all fields
+ * specified in the field descripter separated by '|' will be searched. For
+ * example 'title|content:' will search the title and content fields. When
+ * fields are specified like this, the parser will push the fields onto a
+ * stack and all queries modified by the field specifier will be applied to
+ * the fields on top of the stack. This is where the FLDS macro comes into
+ * place. It takes the current query building function in the parser and calls
+ * it for all fields on top of the stack.
+ * 
+ * Ferret Query Language (FQL)
+ * ===========================
+ *
+ * FIXME to be continued...
+ *****************************************************************************/
 %{
 #include <string.h>
@@ -878 +932 @@
 }
 
+/*****************************************************************************
+ * qp_clean_str method which basically scans the query string and ensures that
+ * all open and close parentheses '()' and quotes '"' are balanced. It does
+ * this be inserting or appending extra parentheses or quotes which is not
+ * necessarily going to be exactly what the user wanted but it will help
+ * prevent the parser from failing so it's the best we can do at this stage.
+ * It also checks 
+ *****************************************************************************/
 char *qp_clean_str(char *str)
 {