lib/TextSearchQuery.php

   1 <?php
   2 /**
   3  * A text search query, converting queries to PCRE and SQL matchers.
   4  *
   5  * This represents an enhanced "Google-like" text search query:
   6  * <dl>
   7  * <dt> default: case-insensitive glob-style search with special operators OR AND NOT -
   8  * <dt> wiki -test
   9  *   <dd> Match strings containing the substring 'wiki', and NOT containing the
  10  *        substring 'test'.
  11  * <dt> wiki word or page
  12  *   <dd> Match strings containing the substring 'wiki' AND either the substring
  13  *        'word' OR the substring 'page'.
  14  * <dt> auto-detect regex hints, glob-style or regex-style, and converts them
  15  *      to PCRE and SQL matchers:
  16  *   <dd> "^word$" => EXACT(phrase)
  17  *   <dd> "^word"  => STARTS_WITH(phrase)
  18  *   <dd> "word$"  => ENDS_WITH(phrase)
  19  *   <dd> "^word" ... => STARTS_WITH(word)
  20  *   <dd> "word$" ... => ENDS_WITH(word)
  21  *   <dd> "word*"  => STARTS_WITH(word)
  22  *   <dd> "*word"  => ENDS_WITH(word)
  23  *   <dd> "/^word.* /" => REGEX(^word.*)
  24  *   <dd> "word*word" => REGEX(word.*word)
  25  * </dl>
  26  *
  27  * The full query syntax, in order of precedence, is roughly:
  28  *
  29  * The unary 'NOT' or '-' operator (they are equivalent) negates the
  30  * following search clause.
  31  *
  32  * Search clauses may be joined with the (left-associative) binary operators
  33  * 'AND' and 'OR'. (case-insensitive)
  34  *
  35  * Two adjoining search clauses are joined with an implicit 'AND'.  This has
  36  * lower precedence than either an explicit 'AND' or 'OR', so "a b OR c"
  37  * parses as "a AND ( b OR c )", while "a AND b OR c" parses as
  38  * "( a AND b ) OR c" (due to the left-associativity of 'AND' and 'OR'.)
  39  *
  40  * Search clauses can be grouped with parentheses.
  41  *
  42  * Phrases (or other things which don't look like words) can be forced to
  43  * be interpreted as words by quoting them, either with single (') or double (")
  44  * quotes.  If you wan't to include the quote character within a quoted string,
  45  * double-up on the quote character: 'I''m hungry' is equivalent to
  46  * "I'm hungry".
  47  *
  48  * Force regex on "re:word" => posix-style, "/word/" => pcre-style
  49  * or use regex='glob' to use file wildcard-like matching. (not yet)
  50  *
  51  * The parsed tree is then converted to the needed PCRE (highlight,
  52  * simple backends) or SQL functions.
  53  *
  54  * @author: Jeff Dairiki
  55  * @author: Reini Urban (case and regex detection, enhanced sql callbacks)
  56  */
  57
  58 // regex-style: 'auto', 'none', 'glob', 'posix', 'pcre', 'sql'
  59 define ('TSQ_REGEX_NONE', 0);
  60 define ('TSQ_REGEX_AUTO', 1);
  61 define ('TSQ_REGEX_POSIX', 2);
  62 define ('TSQ_REGEX_GLOB', 4);
  63 define ('TSQ_REGEX_PCRE', 8);
  64 define ('TSQ_REGEX_SQL', 16);
  65
  66 define ('TSQ_TOK_VOID', 0);
  67 define ('TSQ_TOK_BINOP', 1);
  68 define ('TSQ_TOK_NOT', 2);
  69 define ('TSQ_TOK_LPAREN', 4);
  70 define ('TSQ_TOK_RPAREN', 8);
  71 define ('TSQ_TOK_WORD', 16);
  72 define ('TSQ_TOK_STARTS_WITH', 32);
  73 define ('TSQ_TOK_ENDS_WITH', 64);
  74 define ('TSQ_TOK_EXACT', 128);
  75 define ('TSQ_TOK_REGEX', 256);
  76 define ('TSQ_TOK_REGEX_GLOB', 512);
  77 define ('TSQ_TOK_REGEX_PCRE', 1024);
  78 define ('TSQ_TOK_REGEX_SQL', 2048);
  79 define ('TSQ_TOK_ALL', 4096);
  80 // all bits from word to the last.
  81 define ('TSQ_ALLWORDS', (4096 * 2) - 1 - (16 - 1));
  82
  83 /*
  84 define ('TSQ_NODE_ALL',   0);
  85 define ('TSQ_NODE_EXACT', 1);
  86 define ('TSQ_NODE_NOT',   2);
  87 define ('TSQ_NODE_WORD',  3);
  88 define ('TSQ_NODE_STARTS_WITH', 4);
  89 define ('TSQ_NODE_ENDS_WITH',   5);
  90 define ('TSQ_NODE_REGEX',       6);
  91 define ('TSQ_NODE_REGEX_GLOB',  7);
  92 define ('TSQ_NODE_REGEX_PCRE',  8);
  93 define ('TSQ_NODE_REGEX_SQL',   9);
  94 define ('TSQ_NODE_AND',        10);
  95 define ('TSQ_NODE_OR',         11);
  96 */
  97
  98
  99 class TextSearchQuery
 100 {
 101     /**
 102      * Create a new query.
 103      *
 104      * @param $search_query string The query.  Syntax is as described above.
 105      * Note that an empty $search_query will match anything.
 106      * @param $case_exact boolean
 107      * @param $regex string one of 'auto', 'none', 'glob', 'posix', 'pcre', 'sql'
 108      * @see TextSearchQuery
 109      */
 110     function TextSearchQuery($search_query, $case_exact = false, $regex = 'auto')
 111     {
 112         if ($regex == 'none' or !$regex)
 113             $this->_regex = 0;
 114         elseif (defined("TSQ_REGEX_" . strtoupper($regex)))
 115             $this->_regex = constant("TSQ_REGEX_" . strtoupper($regex)); else {
 116             trigger_error(fmt("Unsupported argument: %s=%s", 'regex', $regex));
 117             $this->_regex = 0;
 118         }
 119         $this->_regex_modifier = ($case_exact ? '' : 'i') . 'sS';
 120         $this->_case_exact = $case_exact;
 121         if ($regex != 'pcre') {
 122             $parser = new TextSearchQuery_Parser;
 123             $this->_tree = $parser->parse($search_query, $case_exact, $this->_regex);
 124             $this->_optimize(); // broken under certain circumstances: "word -word -word"
 125             if (defined("FULLTEXTSEARCH_STOPLIST"))
 126                 $this->_stoplist = FULLTEXTSEARCH_STOPLIST;
 127             else // default stoplist, localizable.
 128                 $this->_stoplist = _("(A|An|And|But|By|For|From|In|Is|It|Of|On|Or|The|To|With)");
 129         } else {
 130             $this->_tree = new TextSearchQuery_node_regex_pcre($search_query);
 131             if (preg_match("/^\/(.*)\/(\w*)$/", $search_query, $m)) {
 132                 $this->_tree->word = $m[1];
 133                 $this->_regex_modifier = $m[2]; // overrides case_exact
 134             }
 135         }
 136     }
 137
 138     function getType()
 139     {
 140         return 'text';
 141     }
 142
 143     function _optimize()
 144     {
 145         $this->_tree = $this->_tree->optimize();
 146     }
 147
 148     /**
 149      * Get a PCRE regexp which matches the query.
 150      */
 151     function asRegexp()
 152     {
 153         if (!isset($this->_regexp)) {
 154             if (!isset($this->_regex_modifier))
 155                 $this->_regex_modifier = ($this->_case_exact ? '' : 'i') . 'sS';
 156             if ($this->_regex)
 157                 $this->_regexp = '/' . $this->_tree->regexp() . '/' . $this->_regex_modifier;
 158             else
 159                 $this->_regexp = '/^' . $this->_tree->regexp() . '/' . $this->_regex_modifier;
 160         }
 161         return $this->_regexp;
 162     }
 163
 164     /**
 165      * Match query against string.
 166      * EXACT ("Term") ignores the case_exact setting.
 167      *
 168      * @param $string string The string to match.
 169      * @return boolean True if the string matches the query.
 170      */
 171     function match($string)
 172     {
 173         if ($this->_tree->_op == TSQ_TOK_ALL) return true;
 174         if ($this->_tree->_op == TSQ_TOK_EXACT) return $this->_tree->word == $string;
 175         return preg_match($this->asRegexp(), $string);
 176     }
 177
 178     /* How good does it match? Returns a number */
 179     function score($string)
 180     {
 181         $score = 0.0;
 182         $i = 10;
 183         foreach (array_unique($this->_tree->highlight_words()) as $word) {
 184             if ($nummatch = preg_match_all("/" . preg_quote($word, '/') . "/" .
 185                     $this->_regex_modifier,
 186                 $string, $out)
 187             )
 188                 $score += ($i-- * $nummatch);
 189         }
 190         return min(1.0, $score / 10.0);
 191     }
 192
 193
 194     /**
 195      * Get a regular expression suitable for highlighting matched words.
 196      *
 197      * This returns a PCRE regular expression which matches any non-negated
 198      * word in the query.
 199      *
 200      * @return string The PCRE regexp.
 201      */
 202     function getHighlightRegexp()
 203     {
 204         if (!isset($this->_hilight_regexp)) {
 205             $words = array_unique($this->_tree->highlight_words());
 206             if (!$words) {
 207                 $this->_hilight_regexp = false;
 208             } else {
 209                 foreach ($words as $key => $word)
 210                     $words[$key] = preg_quote($word, '/');
 211                 $this->_hilight_regexp = '(?' . ($this->_case_exact ? '' : 'i') . ':'
 212                     . join('|', $words) . ')';
 213             }
 214         }
 215         return $this->_hilight_regexp;
 216     }
 217
 218     /**
 219      * Make an SQL clause which matches the query.
 220      * Deprecated, use makeSqlClauseObj instead.
 221      *
 222      * @param $make_sql_clause_cb WikiCallback
 223      * A callback which takes a single word as an argument and
 224      * returns an SQL clause which will match exactly those records
 225      * containing the word.  The word passed to the callback will always
 226      * be in all lower case.
 227      *
 228      * Support db-specific extensions, like MATCH AGAINST or REGEX
 229      * mysql => 4.0.1 can also do Google: MATCH AGAINST IN BOOLEAN MODE
 230      * by using makeSqlClauseObj
 231      *
 232      * Old example usage:
 233      * <pre>
 234      *     function sql_title_match($word) {
 235      *         return sprintf("LOWER(title) like '%s'",
 236      *                        addslashes($word));
 237      *     }
 238      *
 239      *     ...
 240      *
 241      *     $query = new TextSearchQuery("wiki -page");
 242      *     $cb = new WikiFunctionCb('sql_title_match');
 243      *     $sql_clause = $query->makeSqlClause($cb);
 244      * </pre>
 245      * This will result in $sql_clause containing something like
 246      * "(LOWER(title) like 'wiki') AND NOT (LOWER(title) like 'page')".
 247      *
 248      * @return string The SQL clause.
 249      */
 250     function makeSqlClause($sql_clause_cb)
 251     {
 252         $this->_sql_clause_cb = $sql_clause_cb;
 253         return $this->_sql_clause($this->_tree);
 254     }
 255
 256     // deprecated: use _sql_clause_obj now.
 257     function _sql_clause($node)
 258     {
 259         switch ($node->_op) {
 260             case TSQ_TOK_WORD: // word => %word%
 261                 return $this->_sql_clause_cb->call($node->word);
 262             case TSQ_TOK_NOT:
 263                 return "NOT (" . $this->_sql_clause($node->leaves[0]) . ")";
 264             case TSQ_TOK_BINOP:
 265                 $subclauses = array();
 266                 foreach ($node->leaves as $leaf)
 267                     $subclauses[] = "(" . $this->_sql_clause($leaf) . ")";
 268                 return join(" $node->op ", $subclauses);
 269             default:
 270                 assert($node->_op == TSQ_TOK_VOID);
 271                 return '1=1';
 272         }
 273     }
 274
 275     /** Get away with the callback and use a db-specific search class instead.
 276      * @see WikiDB_backend_PearDB_search
 277      */
 278     function makeSqlClauseObj(&$sql_search_cb)
 279     {
 280         $this->_sql_clause_cb = $sql_search_cb;
 281         return $this->_sql_clause_obj($this->_tree);
 282     }
 283
 284     function _sql_clause_obj($node)
 285     {
 286         switch ($node->_op) {
 287             case TSQ_TOK_NOT:
 288                 return "NOT (" . $this->_sql_clause_cb->call($node->leaves[0]) . ")";
 289             case TSQ_TOK_BINOP:
 290                 $subclauses = array();
 291                 foreach ($node->leaves as $leaf)
 292                     $subclauses[] = "(" . $this->_sql_clause_obj($leaf) . ")";
 293                 return join(" $node->op ", $subclauses);
 294             case TSQ_TOK_VOID:
 295                 return '0=1';
 296             case TSQ_TOK_ALL:
 297                 return '1=1';
 298             default:
 299                 return $this->_sql_clause_cb->call($node);
 300         }
 301     }
 302
 303     /*
 304      postgresql tsearch2 uses no WHERE operators, just & | and ! in the searchstring
 305      */
 306     function makeTsearch2SqlClauseObj(&$sql_search_cb)
 307     {
 308         $this->_sql_clause_cb = $sql_search_cb;
 309         return $this->_Tsearch2Sql_clause_obj($this->_tree);
 310     }
 311
 312     function _Tsearch2Sql_clause_obj($node)
 313     {
 314         // TODO: "such a phrase"
 315         switch ($node->_op) {
 316             case TSQ_TOK_NOT:
 317                 return "!" . $node->leaves[0];
 318             case TSQ_TOK_BINOP:
 319                 $subclauses = array();
 320                 foreach ($node->leaves as $leaf)
 321                     $subclauses[] = $this->_Tsearch2Sql_clause_obj($leaf);
 322                 return join($node->_op == 'AND' ? "&" : "|", $subclauses);
 323             case TSQ_TOK_VOID:
 324                 return '';
 325             case TSQ_TOK_ALL:
 326                 return '1';
 327             default:
 328                 return $this->_sql_clause_cb->call($node);
 329         }
 330     }
 331
 332     function sql()
 333     {
 334         return '%' . $this->_sql_quote($this->word) . '%';
 335     }
 336
 337     /**
 338      * Get printable representation of the parse tree.
 339      *
 340      * This is for debugging only.
 341      * @return string Printable parse tree.
 342      */
 343     function asString()
 344     {
 345         return $this->_as_string($this->_tree);
 346     }
 347
 348     function _as_string($node, $indent = '')
 349     {
 350         switch ($node->_op) {
 351             case TSQ_TOK_WORD:
 352                 return $indent . "WORD: $node->word";
 353             case TSQ_TOK_VOID:
 354                 return $indent . "VOID";
 355             case TSQ_TOK_ALL:
 356                 return $indent . "ALL";
 357             default:
 358                 $lines = array($indent . $node->op . ":");
 359                 $indent .= "  ";
 360                 foreach ($node->leaves as $leaf)
 361                     $lines[] = $this->_as_string($leaf, $indent);
 362                 return join("\n", $lines);
 363         }
 364     }
 365 }
 366
 367 /**
 368  * This is a TextSearchQuery which matches nothing.
 369  */
 370 class NullTextSearchQuery extends TextSearchQuery
 371 {
 372     /**
 373      * Create a new query.
 374      *
 375      * @see TextSearchQuery
 376      */
 377     function NullTextSearchQuery()
 378     {
 379     }
 380
 381     function asRegexp()
 382     {
 383         return '/^(?!a)a/x';
 384     }
 385
 386     function match($string)
 387     {
 388         return false;
 389     }
 390
 391     function getHighlightRegexp()
 392     {
 393         return "";
 394     }
 395
 396     function makeSqlClause($make_sql_clause_cb)
 397     {
 398         return "(1 = 0)";
 399     }
 400
 401     function asString()
 402     {
 403         return "NullTextSearchQuery";
 404     }
 405 }
 406
 407
 408
 409 /**
 410  * A simple algebraic matcher for numeric attributes.
 411  *  NumericSearchQuery can do ("population < 20000 and area > 1000000", array("population", "area"))
 412  *  ->match(array('population' => 100000, 'area' => 10000000))
 413  *
 414  * Supports all mathematical PHP comparison operators, plus ':=' for equality.
 415  *   "(x < 2000000 and x >= 10000) or (x >= 100 and x < 2000)"
 416  *   "x := 100000" is the same as "x == 100000"
 417  *
 418  * Since this is basic numerics only, we simply try to get away with
 419  * replacing the variable values at the right positions and do an eval then.
 420  *
 421  * @package NumericSearchQuery
 422  * @author Reini Urban
 423  * @see SemanticAttributeSearchQuery
 424  */
 425 class NumericSearchQuery
 426 {
 427     /**
 428      * Create a new query.
 429      *   NumericSearchQuery("population > 20000 or population < 200", "population")
 430      *   NumericSearchQuery("population < 20000 and area > 1000000", array("population", "area"))
 431      *
 432      * With a single variable it is easy: The valid name must be matched elsewhere, just
 433      * replace the given number in match in the query.
 434      *   ->match(2000)
 435      *
 436      * With matching a struct we need strict names, no * as name is allowed.
 437      * So always when the placeholder is an array, the names of the target struct must match
 438      * and all vars be defined. Use the method can_match($struct) therefore.
 439      *
 440      * @access public
 441      * @param $search_query string   A numerical query with placeholders as variable.
 442      * @param $placeholders array or string  All placeholders in the query must be defined
 443      *     here, and will be replaced by the matcher.
 444      */
 445     function NumericSearchQuery($search_query, $placeholders)
 446     {
 447         // added some basic security checks against user input
 448         $this->_query = $search_query;
 449         $this->_placeholders = $placeholders;
 450
 451         // we should also allow the M_ constants
 452         $this->_allowed_functions = explode(':', 'abs:acos:acosh:asin:asinh:atan2:atan:atanh:base_convert:bindec:ceil:cos:cosh:decbin:dechex:decoct:deg2rad:exp:expm1:floor:fmod:getrandmax:hexdec:hypot:is_finite:is_infinite:is_nan:lcg_value:log10:log1p:log:max:min:mt_getrandmax:mt_rand:mt_srand:octdec:pi:pow:rad2deg:rand:round:sin:sinh:sqrt:srand:tan:tanh');
 453         $this->_allowed_operators = explode(',', '-,<,<=,>,>=,==,!=,*,+,/,(,),%,and,or,xor,<<,>>,===,!==,&,^,|,&&,||');
 454         $this->_parser_check = array();
 455         // check should be fast, so make a hash
 456         foreach ($this->_allowed_functions as $f)
 457             $this->_parser_check[$f] = 1;
 458         foreach ($this->_allowed_operators as $f)
 459             $this->_parser_check[$f] = 1;
 460         if (is_array($placeholders))
 461             foreach ($placeholders as $f)
 462                 $this->_parser_check[$f] = 1;
 463         else $this->_parser_check[$placeholders] = 1;
 464
 465         // This is a speciality: := looks like the attribute definition and is
 466         // therefore a dummy check for this definition.
 467         // php-4.2.2 has a problem with /\b:=\b/ matching "population := 1223400"
 468         $this->_query = preg_replace("/:=/", "==", $this->_query);
 469         $this->_query = $this->check_query($this->_query);
 470     }
 471
 472     function getType()
 473     {
 474         return 'numeric';
 475     }
 476
 477     /**
 478      * Check the symbolic definition query against unwanted functions and characters.
 479      * "population < 20000 and area > 1000000" vs
 480      *   "area > 1000000 and mail($me,file("/etc/passwd"),...)"
 481      * http://localhost/wikicvs/SemanticSearch?attribute=*&attr_op=<0 and find(1)>&s=-0.01&start_debug=1
 482      */
 483     function check_query($query)
 484     {
 485         $tmp = $query; // check for all function calls, in case the tokenizer is not available.
 486         while (preg_match("/([a-z][a-z0-9]+)\s*\((.*)$/i", $tmp, $m)) {
 487             if (!in_array($m[1], $this->_allowed_functions)
 488                 and !in_array($m[1], $this->_allowed_operators)
 489             ) {
 490                 trigger_error("Illegal function in query: " . $m[1], E_USER_WARNING);
 491                 return '';
 492             }
 493             $tmp = $m[2];
 494         }
 495
 496         // Strictly check for illegal functions and operators, which are no placeholders.
 497         if (function_exists('token_get_all')) {
 498             $parsed = token_get_all("<?$query?>");
 499             foreach ($parsed as $x) { // flat, non-recursive array
 500                 if (is_string($x) and !isset($this->_parser_check[$x])) {
 501                     // single char op or name
 502                     trigger_error("Illegal string or operator in query: \"$x\"", E_USER_WARNING);
 503                     $query = '';
 504                 } elseif (is_array($x)) {
 505                     $n = token_name($x[0]);
 506                     if ($n == 'T_OPEN_TAG' or $n == 'T_WHITESPACE'
 507                         or $n == 'T_CLOSE_TAG' or $n == 'T_LNUMBER'
 508                         or $n == 'T_CONST' or $n == 'T_DNUMBER'
 509                     ) continue;
 510                     if ($n == 'T_VARIABLE') { // but we do allow consts
 511                         trigger_error("Illegal variable in query: \"$x[1]\"", E_USER_WARNING);
 512                         $query = '';
 513                     }
 514                     if (is_string($x[1]) and !isset($this->_parser_check[$x[1]])) {
 515                         // multi-char char op or name
 516                         trigger_error("Illegal $n in query: \"$x[1]\"", E_USER_WARNING);
 517                         $query = '';
 518                     }
 519                 }
 520             }
 521             //echo "$query <br>";
 522             //$this->_parse_token($parsed);
 523             //echo "<br>\n";
 524             //var_dump($parsed);
 525             /*
 526     "_x > 0" =>
 527     { T_OPEN_TAG "<?"} { T_STRING "_x"} { T_WHITESPACE " "} ">" { T_WHITESPACE " "} { T_LNUMBER "0"} { T_CLOSE_TAG "?>"}
 528         Interesting: on-char ops, as ">" are not tokenized.
 529     "_x <= 0"
 530     { T_OPEN_TAG "< ?" } { T_STRING "_x" } { T_WHITESPACE " " } { T_IS_SMALLER_OR_EQUAL "<=" } { T_WHITESPACE " " } { T_LNUMBER "0" } { T_CLOSE_TAG "?>" }
 531              */
 532         } else {
 533             // Detect illegal characters besides nums, words and ops.
 534             // So attribute names can not be utf-8
 535             $c = "/([^\d\w.,\s" . preg_quote(join("", $this->_allowed_operators), "/") . "])/";
 536             if (preg_match($c, $query, $m)) {
 537                 trigger_error("Illegal character in query: " . $m[1], E_USER_WARNING);
 538                 return '';
 539             }
 540         }
 541         return $query;
 542     }
 543
 544     /**
 545      * Check the bound, numeric-only query against unwanted functions and sideeffects.
 546      * "4560000 < 20000 and 1456022 > 1000000"
 547      */
 548     function _live_check()
 549     {
 550         // TODO: check $this->_workquery again?
 551         return !empty($this->_workquery);
 552     }
 553
 554     /**
 555      * A numeric query can only operate with predefined variables. "x < 0 and y < 1"
 556      *
 557      * @return array The names as array of strings. => ('x', 'y') the placeholders.
 558      */
 559     function getVars()
 560     {
 561         if (is_array($this->_placeholders)) return $this->_placeholders;
 562         else return array($this->_placeholders);
 563     }
 564
 565     /**
 566      * Strip non-numeric chars from the variable (as the groupseperator) and replace
 567      * it in the symbolic query for evaluation.
 568      *
 569      * @access private
 570      * @param $value number   A numerical value: integer, float or string.
 571      * @param $x string       The variable name to be replaced in the query.
 572      * @return string
 573      */
 574     function _bind($value, $x)
 575     {
 576         // TODO: check is_number, is_float, is_integer and do casting
 577         $this->_bound[] = array('linkname' => $x,
 578             'linkvalue' => $value);
 579         $value = preg_replace("/[^-+0123456789.,]/", "", $value);
 580         //$c = "/\b".preg_quote($x,"/")."\b/";
 581         $this->_workquery = preg_replace("/\b" . preg_quote($x, "/") . "\b/", $value, $this->_workquery);
 582         // FIXME: do again a final check. now only numbers and some operators are allowed.
 583         return $this->_workquery;
 584     }
 585
 586     /* array of successfully bound vars, and in case of success, the resulting vars
 587      */
 588     function _bound()
 589     {
 590         return $this->_bound;
 591     }
 592
 593     /**
 594      * With an array of placeholders we need a hash to check against, if all required names are given.
 595      * Purpose: Be silent about missing vars, just return false.
 596     `*
 597      * @access public
 598      * @param $variable string or hash of name => value  The keys must satisfy all placeholders in the definition.
 599      * We want the full hash and not just the keys because a hash check is faster than the array of keys check.
 600      * @return boolean
 601      */
 602     function can_match(&$variables)
 603     {
 604         if (empty($this->_query))
 605             return false;
 606         $p =& $this->_placeholders;
 607         if (!is_array($variables) and !is_array($p))
 608             return $variables == $p; // This was easy.
 609         // Check if all placeholders have definitions. can be overdefined but not underdefined.
 610         if (!is_array($p)) {
 611             if (!isset($variables[$p])) return false;
 612         } else {
 613             foreach ($p as $x) {
 614                 if (!isset($variables[$x])) return false;
 615             }
 616         }
 617         return true;
 618     }
 619
 620     /**
 621      * We can match against a single variable or against a hash of variables.
 622      * With one placeholder we need just a number.
 623      * With an array of placeholders we need a hash.
 624      *
 625      * @access public
 626      * @param $variable number or array of name => value  The keys must satisfy all placeholders in the definition.
 627      * @return boolean
 628      */
 629     function match(&$variable)
 630     {
 631         $p =& $this->_placeholders;
 632         $this->_workquery = $this->_query;
 633         if (!is_array($p)) {
 634             if (is_array($variable)) { // which var to match? we cannot decide this here
 635                 if (!isset($variable[$p]))
 636                     trigger_error("Required NumericSearchQuery->match variable $x not defined.", E_USER_ERROR);
 637                 $this->_bind($variable[$p], $p);
 638             } else {
 639                 $this->_bind($variable, $p);
 640             }
 641         } else {
 642             foreach ($p as $x) {
 643                 if (!isset($variable[$x]))
 644                     trigger_error("Required NumericSearchQuery->match variable $x not defined.", E_USER_ERROR);
 645                 $this->_bind($variable[$x], $x);
 646             }
 647         }
 648         if (!$this->_live_check()) // check returned an error
 649             return false;
 650         $search = $this->_workquery;
 651         $result = false;
 652         //if (DEBUG & _DEBUG_VERBOSE)
 653         //    trigger_error("\$result = (boolean)($search);", E_USER_NOTICE);
 654         // We might have a numerical problem:
 655         // php-4.2.2 eval'ed as module: "9.636e+08 > 1000" false;
 656         // php-5.1.2 cgi true, 4.2.2 cgi true
 657         eval("\$result = (boolean)($search);");
 658         if ($result and is_array($p)) {
 659             return $this->_bound();
 660         }
 661         return $result;
 662     }
 663 }
 664
 665 ////////////////////////////////////////////////////////////////
 666 //
 667 // Remaining classes are private.
 668 //
 669 ////////////////////////////////////////////////////////////////
 670 /**
 671  * Virtual base class for nodes in a TextSearchQuery parse tree.
 672  *
 673  * Also serves as a 'VOID' (contentless) node.
 674  */
 675 class TextSearchQuery_node
 676 {
 677     var $op = 'VOID';
 678     var $_op = 0;
 679
 680     /**
 681      * Optimize this node.
 682      * @return object Optimized node.
 683      */
 684     function optimize()
 685     {
 686         return $this;
 687     }
 688
 689     /**
 690      * @return regexp matching this node.
 691      */
 692     function regexp()
 693     {
 694         return '';
 695     }
 696
 697     /**
 698      * @param bool True if this node has been negated (higher in the parse tree.)
 699      * @return array A list of all non-negated words contained by this node.
 700      */
 701     function highlight_words($negated = false)
 702     {
 703         return array();
 704     }
 705
 706     function sql()
 707     {
 708         return $this->word;
 709     }
 710
 711     function _sql_quote()
 712     {
 713         global $request;
 714         $word = preg_replace('/(?=[%_\\\\])/', "\\", $this->word);
 715         return $request->_dbi->_backend->qstr($word);
 716     }
 717 }
 718
 719 /**
 720  * A word. Exact or substring?
 721  */
 722 class TextSearchQuery_node_word
 723     extends TextSearchQuery_node
 724 {
 725     var $op = "WORD";
 726     var $_op = TSQ_TOK_WORD;
 727
 728     function TextSearchQuery_node_word($word)
 729     {
 730         $this->word = $word;
 731     }
 732
 733     function regexp()
 734     {
 735         return '(?=.*\b' . preg_quote($this->word, '/') . '\b)';
 736     }
 737
 738     function highlight_words($negated = false)
 739     {
 740         return $negated ? array() : array($this->word);
 741     }
 742
 743     function sql()
 744     {
 745         return '%' . $this->_sql_quote($this->word) . '%';
 746     }
 747 }
 748
 749 class TextSearchQuery_node_all
 750     extends TextSearchQuery_node
 751 {
 752     var $op = "ALL";
 753     var $_op = TSQ_TOK_ALL;
 754
 755     function regexp()
 756     {
 757         return '(?=.*)';
 758     }
 759
 760     function sql()
 761     {
 762         return '%';
 763     }
 764 }
 765
 766 class TextSearchQuery_node_starts_with
 767     extends TextSearchQuery_node_word
 768 {
 769     var $op = "STARTS_WITH";
 770     var $_op = TSQ_TOK_STARTS_WITH;
 771
 772     function regexp()
 773     {
 774         return '(?=.*\b' . preg_quote($this->word, '/') . ')';
 775     }
 776
 777     function sql()
 778     {
 779         return $this->_sql_quote($this->word) . '%';
 780     }
 781 }
 782
 783 // ^word: full phrase starts with
 784 class TextSearchQuery_phrase_starts_with
 785     extends TextSearchQuery_node_starts_with
 786 {
 787     function regexp()
 788     {
 789         return '(?=^' . preg_quote($this->word, '/') . ')';
 790     }
 791 }
 792
 793 class TextSearchQuery_node_ends_with
 794     extends TextSearchQuery_node_word
 795 {
 796     var $op = "ENDS_WITH";
 797     var $_op = TSQ_TOK_ENDS_WITH;
 798
 799     function regexp()
 800     {
 801         return '(?=.*' . preg_quote($this->word, '/') . '\b)';
 802     }
 803
 804     function sql()
 805     {
 806         return '%' . $this->_sql_quote($this->word);
 807     }
 808 }
 809
 810 // word$: full phrase ends with
 811 class TextSearchQuery_phrase_ends_with
 812     extends TextSearchQuery_node_ends_with
 813 {
 814     function regexp()
 815     {
 816         return '(?=' . preg_quote($this->word, '/') . '$)';
 817     }
 818 }
 819
 820 class TextSearchQuery_node_exact
 821     extends TextSearchQuery_node_word
 822 {
 823     var $op = "EXACT";
 824     var $_op = TSQ_TOK_EXACT;
 825
 826     function regexp()
 827     {
 828         return '(?=\b' . preg_quote($this->word, '/') . '\b)';
 829     }
 830
 831     function sql()
 832     {
 833         return $this->_sql_squote($this->word);
 834     }
 835 }
 836
 837 class TextSearchQuery_node_regex // posix regex. FIXME!
 838     extends TextSearchQuery_node_word
 839 {
 840     var $op = "REGEX"; // using REGEXP or ~ extension
 841     var $_op = TSQ_TOK_REGEX;
 842
 843     function regexp()
 844     {
 845         return '(?=.*\b' . $this->word . '\b)';
 846     }
 847
 848     function sql()
 849     {
 850         return $this->_sql_quote($this->word);
 851     }
 852 }
 853
 854 class TextSearchQuery_node_regex_glob
 855     extends TextSearchQuery_node_regex
 856 {
 857     var $op = "REGEX_GLOB";
 858     var $_op = TSQ_TOK_REGEX_GLOB;
 859
 860     function regexp()
 861     {
 862         return '(?=.*\b' . glob_to_pcre($this->word) . '\b)';
 863     }
 864 }
 865
 866 class TextSearchQuery_node_regex_pcre // how to handle pcre modifiers? /i
 867     extends TextSearchQuery_node_regex
 868 {
 869     var $op = "REGEX_PCRE";
 870     var $_op = TSQ_TOK_REGEX_PCRE;
 871
 872     function regexp()
 873     {
 874         return $this->word;
 875     }
 876 }
 877
 878 class TextSearchQuery_node_regex_sql
 879     extends TextSearchQuery_node_regex
 880 {
 881     var $op = "REGEX_SQL"; // using LIKE
 882     var $_op = TSQ_TOK_REGEX_SQL;
 883
 884     function regexp()
 885     {
 886         return str_replace(array("/%/", "/_/"), array(".*", "."), $this->word);
 887     }
 888
 889     function sql()
 890     {
 891         return $this->word;
 892     }
 893 }
 894
 895 /**
 896  * A negated clause.
 897  */
 898 class TextSearchQuery_node_not
 899     extends TextSearchQuery_node
 900 {
 901     var $op = "NOT";
 902     var $_op = TSQ_TOK_NOT;
 903
 904     function TextSearchQuery_node_not($leaf)
 905     {
 906         $this->leaves = array($leaf);
 907     }
 908
 909     function optimize()
 910     {
 911         $leaf = &$this->leaves[0];
 912         $leaf = $leaf->optimize();
 913         if ($leaf->_op == TSQ_TOK_NOT)
 914             return $leaf->leaves[0]; // ( NOT ( NOT x ) ) -> x
 915         return $this;
 916     }
 917
 918     function regexp()
 919     {
 920         $leaf = &$this->leaves[0];
 921         return '(?!' . $leaf->regexp() . ')';
 922     }
 923
 924     function highlight_words($negated = false)
 925     {
 926         return $this->leaves[0]->highlight_words(!$negated);
 927     }
 928 }
 929
 930 /**
 931  * Virtual base class for 'AND' and 'OR conjoins.
 932  */
 933 class TextSearchQuery_node_binop
 934     extends TextSearchQuery_node
 935 {
 936     var $_op = TSQ_TOK_BINOP;
 937
 938     function TextSearchQuery_node_binop($leaves)
 939     {
 940         $this->leaves = $leaves;
 941     }
 942
 943     function _flatten()
 944     {
 945         // This flattens e.g. (AND (AND a b) (OR c d) e)
 946         //        to (AND a b e (OR c d))
 947         $flat = array();
 948         foreach ($this->leaves as $leaf) {
 949             $leaf = $leaf->optimize();
 950             if ($this->op == $leaf->op)
 951                 $flat = array_merge($flat, $leaf->leaves);
 952             else
 953                 $flat[] = $leaf;
 954         }
 955         $this->leaves = $flat;
 956     }
 957
 958     function optimize()
 959     {
 960         $this->_flatten();
 961         assert(!empty($this->leaves));
 962         if (count($this->leaves) == 1)
 963             return $this->leaves[0]; // (AND x) -> x
 964         return $this;
 965     }
 966
 967     function highlight_words($negated = false)
 968     {
 969         $words = array();
 970         foreach ($this->leaves as $leaf)
 971             array_splice($words, 0, 0,
 972                 $leaf->highlight_words($negated));
 973         return $words;
 974     }
 975 }
 976
 977 /**
 978  * A (possibly multi-argument) 'AND' conjoin.
 979  */
 980 class TextSearchQuery_node_and
 981     extends TextSearchQuery_node_binop
 982 {
 983     var $op = "AND";
 984
 985     function optimize()
 986     {
 987         $this->_flatten();
 988
 989         // Convert (AND (NOT a) (NOT b) c d) into (AND (NOT (OR a b)) c d).
 990         // Since OR's are more efficient for regexp matching:
 991         //   (?!.*a)(?!.*b)  vs   (?!.*(?:a|b))
 992
 993         // Suck out the negated leaves.
 994         $nots = array();
 995         foreach ($this->leaves as $key => $leaf) {
 996             if ($leaf->_op == TSQ_TOK_NOT) {
 997                 $nots[] = $leaf->leaves[0];
 998                 unset($this->leaves[$key]);
 999             }
1000         }
1001
1002         // Combine the negated leaves into a single negated or.
1003         if ($nots) {
1004             $node = (new TextSearchQuery_node_not
1005             (new TextSearchQuery_node_or($nots)));
1006             array_unshift($this->leaves, $node->optimize());
1007         }
1008
1009         assert(!empty($this->leaves));
1010         if (count($this->leaves) == 1)
1011             return $this->leaves[0]; // (AND x) -> x
1012         return $this;
1013     }
1014
1015     /* FIXME!
1016      * Either we need all combinations of all words to be position independent,
1017      * or we have to use multiple match calls for each AND
1018      * (AND x y) => /(?(:x)(:y))|(?(:y)(:x))/
1019      */
1020     function regexp()
1021     {
1022         $regexp = '';
1023         foreach ($this->leaves as $leaf)
1024             $regexp .= $leaf->regexp();
1025         return $regexp;
1026     }
1027 }
1028
1029 /**
1030  * A (possibly multi-argument) 'OR' conjoin.
1031  */
1032 class TextSearchQuery_node_or
1033     extends TextSearchQuery_node_binop
1034 {
1035     var $op = "OR";
1036
1037     function regexp()
1038     {
1039         // We will combine any of our direct descendents which are WORDs
1040         // into a single (?=.*(?:word1|word2|...)) regexp.
1041
1042         $regexps = array();
1043         $words = array();
1044
1045         foreach ($this->leaves as $leaf) {
1046             if ($leaf->op == TSQ_TOK_WORD)
1047                 $words[] = preg_quote($leaf->word, '/');
1048             else
1049                 $regexps[] = $leaf->regexp();
1050         }
1051
1052         if ($words)
1053             array_unshift($regexps,
1054                 '(?=.*' . $this->_join($words) . ')');
1055
1056         return $this->_join($regexps);
1057     }
1058
1059     function _join($regexps)
1060     {
1061         assert(count($regexps) > 0);
1062
1063         if (count($regexps) > 1)
1064             return '(?:' . join('|', $regexps) . ')';
1065         else
1066             return $regexps[0];
1067     }
1068 }
1069
1070 ////////////////////////////////////////////////////////////////
1071 //
1072 // Parser:
1073 //   op's (and, or, not) are forced to lowercase in the tokenizer.
1074 //
1075 ////////////////////////////////////////////////////////////////
1076 class TextSearchQuery_Parser
1077 {
1078     /*
1079      * This is a simple recursive descent parser, based on the following grammar:
1080      *
1081      * toplist    :
1082      *        | toplist expr
1083      *        ;
1084      *
1085      *
1086      * list    : expr
1087      *        | list expr
1088      *        ;
1089      *
1090      * expr    : atom
1091      *        | expr BINOP atom
1092      *        ;
1093      *
1094      * atom    : '(' list ')'
1095      *        | NOT atom
1096      *        | WORD
1097      *        ;
1098      *
1099      * The terminal tokens are:
1100      *
1101      *
1102      * and|or          BINOP
1103      * -|not          NOT
1104      * (          LPAREN
1105      * )          RPAREN
1106      * /[^-()\s][^()\s]*  WORD
1107      * /"[^"]*"/      WORD
1108      * /'[^']*'/      WORD
1109      *
1110      * ^WORD              TextSearchQuery_phrase_starts_with
1111      * WORD*              STARTS_WITH
1112      * *WORD              ENDS_WITH
1113      * ^WORD$             EXACT
1114      * *                  ALL
1115      */
1116
1117     function parse($search_expr, $case_exact = false, $regex = TSQ_REGEX_AUTO)
1118     {
1119         $this->lexer = new TextSearchQuery_Lexer($search_expr, $case_exact, $regex);
1120         $this->_regex = $regex;
1121         $tree = $this->get_list('toplevel');
1122         // Assert failure when using the following URL in debug mode.
1123         // /TitleSearch?action=FullTextSearch&s=WFXSSProbe'")/>&case_exact=1&regex=sql
1124         //        assert($this->lexer->eof());
1125         unset($this->lexer);
1126         return $tree;
1127     }
1128
1129     function get_list($is_toplevel = false)
1130     {
1131         $list = array();
1132
1133         // token types we'll accept as words (and thus expr's) for the
1134         // purpose of error recovery:
1135         $accept_as_words = TSQ_TOK_NOT | TSQ_TOK_BINOP;
1136         if ($is_toplevel)
1137             $accept_as_words |= TSQ_TOK_LPAREN | TSQ_TOK_RPAREN;
1138
1139         while (($expr = $this->get_expr())
1140             || ($expr = $this->get_word($accept_as_words))) {
1141             $list[] = $expr;
1142         }
1143
1144         if (!$list) {
1145             if ($is_toplevel)
1146                 return new TextSearchQuery_node;
1147             else
1148                 return false;
1149         }
1150         if ($is_toplevel and count($list) == 1) {
1151             if ($this->lexer->query_str[0] == '^')
1152                 return new TextSearchQuery_phrase_starts_with($list[0]->word);
1153             else
1154                 return $list[0];
1155         }
1156         return new TextSearchQuery_node_and($list);
1157     }
1158
1159     function get_expr()
1160     {
1161         if (($expr = $this->get_atom()) === false) // protect against '0'
1162             return false;
1163
1164         $savedpos = $this->lexer->tell();
1165         // Bug#1791564: allow string '0'
1166         while (($op = $this->lexer->get(TSQ_TOK_BINOP)) !== false) {
1167             if (!($right = $this->get_atom())) {
1168                 break;
1169             }
1170
1171             if ($op == 'and')
1172                 $expr = new TextSearchQuery_node_and(array($expr, $right));
1173             else {
1174                 assert($op == 'or');
1175                 $expr = new TextSearchQuery_node_or(array($expr, $right));
1176             }
1177
1178             $savedpos = $this->lexer->tell();
1179         }
1180         $this->lexer->seek($savedpos);
1181
1182         return $expr;
1183     }
1184
1185
1186     function get_atom()
1187     {
1188         if ($atom = $this->get_word(TSQ_ALLWORDS)) // Bug#1791564 not involved: '*'
1189             return $atom;
1190
1191         $savedpos = $this->lexer->tell();
1192         if ($this->lexer->get(TSQ_TOK_LPAREN)) {
1193             if (($list = $this->get_list()) && $this->lexer->get(TSQ_TOK_RPAREN)) {
1194                 return $list;
1195             } else {
1196                 // Fix Bug#1792170
1197                 // Handle " ( " or "(test" without closing ")" as plain word
1198                 $this->lexer->seek($savedpos);
1199                 return new TextSearchQuery_node_word($this->lexer->get(-1));
1200             }
1201         } elseif ($this->lexer->get(TSQ_TOK_NOT)) {
1202             if (($atom = $this->get_atom()))
1203                 return new TextSearchQuery_node_not($atom);
1204         }
1205         $this->lexer->seek($savedpos);
1206         return false;
1207     }
1208
1209     function get_word($accept = TSQ_ALLWORDS)
1210     {
1211         // Performance shortcut for ( and ). This is always false
1212         if (!empty($this->lexer->tokens[$this->lexer->pos])) {
1213             list ($type, $val) = $this->lexer->tokens[$this->lexer->pos];
1214             if ($type == TSQ_TOK_LPAREN or $type == TSQ_TOK_RPAREN)
1215                 return false;
1216         }
1217         foreach (array("WORD", "STARTS_WITH", "ENDS_WITH", "EXACT",
1218                      "REGEX", "REGEX_GLOB", "REGEX_PCRE", "ALL") as $tok) {
1219             $const = constant("TSQ_TOK_" . $tok);
1220             // Bug#1791564: allow word '0'
1221             if ($accept & $const and
1222                 (($word = $this->lexer->get($const)) !== false)
1223             ) {
1224                 // phrase or word level?
1225                 if ($tok == 'STARTS_WITH' and $this->lexer->query_str[0] == '^')
1226                     $classname = "TextSearchQuery_phrase_" . strtolower($tok);
1227                 elseif ($tok == 'ENDS_WITH' and
1228                     string_ends_with($this->lexer->query_str, '$')
1229                 )
1230                     $classname = "TextSearchQuery_phrase_" . strtolower($tok); else
1231                     $classname = "TextSearchQuery_node_" . strtolower($tok);
1232                 return new $classname($word);
1233             }
1234         }
1235         return false;
1236     }
1237 }
1238
1239 class TextSearchQuery_Lexer
1240 {
1241     function TextSearchQuery_Lexer($query_str, $case_exact = false,
1242                                    $regex = TSQ_REGEX_AUTO)
1243     {
1244         $this->tokens = $this->tokenize($query_str, $case_exact, $regex);
1245         $this->query_str = $query_str;
1246         $this->pos = 0;
1247     }
1248
1249     function tell()
1250     {
1251         return $this->pos;
1252     }
1253
1254     function seek($pos)
1255     {
1256         $this->pos = $pos;
1257     }
1258
1259     function eof()
1260     {
1261         return $this->pos == count($this->tokens);
1262     }
1263
1264     /**
1265      * TODO: support more regex styles, esp. prefer the forced ones over auto
1266      * re: and // stuff
1267      */
1268     function tokenize($string, $case_exact = false, $regex = TSQ_REGEX_AUTO)
1269     {
1270         $tokens = array();
1271         $buf = $case_exact ? ltrim($string) : strtolower(ltrim($string));
1272         while (!empty($buf)) {
1273             if (preg_match('/^([()])\s*/', $buf, $m)) {
1274                 $val = $m[1];
1275                 $type = $m[1] == '(' ? TSQ_TOK_LPAREN : TSQ_TOK_RPAREN;
1276             } // * => ALL
1277             elseif ($regex & (TSQ_REGEX_AUTO | TSQ_REGEX_POSIX | TSQ_REGEX_GLOB)
1278                 and preg_match('/^\*\s*/', $buf, $m)
1279             ) {
1280                 $val = "*";
1281                 $type = TSQ_TOK_ALL;
1282             } // .* => ALL
1283             elseif ($regex & (TSQ_REGEX_PCRE)
1284                 and preg_match('/^\.\*\s*/', $buf, $m)
1285             ) {
1286                 $val = ".*";
1287                 $type = TSQ_TOK_ALL;
1288             } // % => ALL
1289             elseif ($regex & (TSQ_REGEX_SQL)
1290                 and preg_match('/^%\s*/', $buf, $m)
1291             ) {
1292                 $val = "%";
1293                 $type = TSQ_TOK_ALL;
1294             } // ^word
1295             elseif ($regex & (TSQ_REGEX_AUTO | TSQ_REGEX_POSIX | TSQ_REGEX_PCRE)
1296                 and preg_match('/^\^([^-()][^()\s]*)\s*/', $buf, $m)
1297             ) {
1298                 $val = $m[1];
1299                 $type = TSQ_TOK_STARTS_WITH;
1300             } // word*
1301             elseif ($regex & (TSQ_REGEX_AUTO | TSQ_REGEX_POSIX | TSQ_REGEX_GLOB)
1302                 and preg_match('/^([^-()][^()\s]*)\*\s*/', $buf, $m)
1303             ) {
1304                 $val = $m[1];
1305                 $type = TSQ_TOK_STARTS_WITH;
1306             } // *word
1307             elseif ($regex & (TSQ_REGEX_AUTO | TSQ_REGEX_POSIX | TSQ_REGEX_GLOB)
1308                 and preg_match('/^\*([^-()][^()\s]*)\s*/', $buf, $m)
1309             ) {
1310                 $val = $m[1];
1311                 $type = TSQ_TOK_ENDS_WITH;
1312             } // word$
1313             elseif ($regex & (TSQ_REGEX_AUTO | TSQ_REGEX_POSIX | TSQ_REGEX_PCRE)
1314                 and preg_match('/^([^-()][^()\s]*)\$\s*/', $buf, $m)
1315             ) {
1316                 $val = $m[1];
1317                 $type = TSQ_TOK_ENDS_WITH;
1318             } // ^word$
1319             elseif ($regex & (TSQ_REGEX_AUTO | TSQ_REGEX_POSIX | TSQ_REGEX_PCRE)
1320                 and preg_match('/^\^([^-()][^()\s]*)\$\s*/', $buf, $m)
1321             ) {
1322                 $val = $m[1];
1323                 $type = TSQ_TOK_EXACT;
1324             } elseif (preg_match('/^(and|or)\b\s*/i', $buf, $m)) {
1325                 $val = strtolower($m[1]);
1326                 $type = TSQ_TOK_BINOP;
1327             } elseif (preg_match('/^(-|not\b)\s*/i', $buf, $m)) {
1328                 $val = strtolower($m[1]);
1329                 $type = TSQ_TOK_NOT;
1330             } // "words "
1331             elseif (preg_match('/^ " ( (?: [^"]+ | "" )* ) " \s*/x', $buf, $m)) {
1332                 $val = str_replace('""', '"', $m[1]);
1333                 $type = TSQ_TOK_WORD;
1334             } // 'words '
1335             elseif (preg_match("/^ ' ( (?:[^']+|'')* ) ' \s*/x", $buf, $m)) {
1336                 $val = str_replace("''", "'", $m[1]);
1337                 $type = TSQ_TOK_WORD;
1338             } // word
1339             elseif (preg_match('/^([^-()][^()\s]*)\s*/', $buf, $m)) {
1340                 $val = $m[1];
1341                 $type = TSQ_TOK_WORD;
1342             } else {
1343                 assert(empty($buf));
1344                 break;
1345             }
1346             $buf = substr($buf, strlen($m[0]));
1347
1348             /* refine the simple parsing from above: bla*bla, bla?bla, ...
1349             if ($regex and $type == TSQ_TOK_WORD) {
1350                 if (substr($val,0,1) == "^")
1351                     $type = TSQ_TOK_STARTS_WITH;
1352                 elseif (substr($val,0,1) == "*")
1353                     $type = TSQ_TOK_ENDS_WITH;
1354                 elseif (substr($val,-1,1) == "*")
1355                     $type = TSQ_TOK_STARTS_WITH;
1356             }
1357             */
1358             $tokens[] = array($type, $val);
1359         }
1360         return $tokens;
1361     }
1362
1363     function get($accept)
1364     {
1365         if ($this->pos >= count($this->tokens))
1366             return false;
1367
1368         list ($type, $val) = $this->tokens[$this->pos];
1369         if (($type & $accept) == 0)
1370             return false;
1371
1372         $this->pos++;
1373         return $val;
1374     }
1375 }
1376
1377 // Local Variables:
1378 // mode: php
1379 // tab-width: 8
1380 // c-basic-offset: 4
1381 // c-hanging-comment-ender-p: nil
1382 // indent-tabs-mode: nil
1383 // End: