lib/TextSearchQuery.php

   1 <?php rcs_id('$Id: TextSearchQuery.php,v 1.11 2004-11-26 18:39:01 rurban Exp $');
   2 /**
   3  * A text search query, converting queries to PCRE or 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> detects regex hints, glob-style or regex-style, and converts them to PCRE or SQL matchers
  15  *   <dd> "^word$" => EXACT(word)
  16  *   <dd> "^word"  => STARTS_WITH(word)
  17  *   <dd> "word*"  => STARTS_WITH(word)
  18  *   <dd> "*word"  => ENDS_WITH(word)
  19  *   <dd> "/^word.* /" => REGEX(^word.*)
  20  *   <dd> "word*word" => REGEX(word.*word)
  21  * </dl>
  22  *
  23  * The full query syntax, in order of precedence, is roughly:
  24  *
  25  * The unary 'NOT' or '-' operator (they are equivalent) negates the
  26  * following search clause.
  27  *
  28  * Search clauses may be joined with the (left-associative) binary operators
  29  * 'AND' and 'OR'.
  30  *
  31  * Two adjoining search clauses are joined with an implicit 'AND'.  This has
  32  * lower precedence than either an explicit 'AND' or 'OR', so "a b OR c"
  33  * parses as "a AND ( b OR c )", while "a AND b OR c" parses as
  34  * "( a AND b ) OR c" (due to the left-associativity of 'AND' and 'OR'.)
  35  *
  36  * Search clauses can be grouped with parentheses.
  37  *
  38  * Phrases (or other things which don't look like words) can be forced to
  39  * be interpreted as words by quoting them, either with single (') or double (")
  40  * quotes.  If you wan't to include the quote character within a quoted string,
  41  * double-up on the quote character: 'I''m hungry' is equivalent to
  42  * "I'm hungry".
  43  *
  44  * Force regex on "re:word" => posix-style, "/word/" => pcre-style
  45  * or use regex='glob' to use file wildcard-like matching. (not yet)
  46  *
  47  * The parseed tree is then converted to the needed PCRE (highlight, simple backends)
  48  * or SQL functions.
  49  *
  50  * @author: Jeff Dairiki
  51  * @author: Reini Urban (case and regex, enhanced sql callbacks)
  52  */
  53 class TextSearchQuery {
  54     /**
  55      * Create a new query.
  56      *
  57      * @param $search_query string The query.  Syntax is as described above.
  58      * Note that an empty $search_query will match anything.
  59      * @see TextSearchQuery
  60      * TODO: support $regex arg, try to detect regex from $search_query (glob-style)
  61      */
  62     function TextSearchQuery($search_query, $case_exact=false, $regex='auto') {
  63         $parser = new TextSearchQuery_Parser;
  64         $this->_isregex = $regex; // default: auto
  65         $this->_case_exact = $case_exact;
  66         $this->_tree = $parser->parse($search_query, $case_exact, $regex);
  67         $this->_optimize();
  68     }
  69
  70     function _optimize() {
  71         $this->_tree = $this->_tree->optimize();
  72     }
  73
  74     /**
  75      * Get a PCRE regexp which matches the query.
  76      */
  77     function asRegexp() {
  78         if (!isset($this->_regexp)) {
  79             if ($this->_isregex) // TODO: convert glob-style regex to pcre
  80                 $this->_regexp =  '/' . $this->_tree->regexp() . '/'.($this->_case_exact?'':'i').'sS';
  81             else
  82                 $this->_regexp =  '/^' . $this->_tree->regexp() . '/'.($this->_case_exact?'':'i').'sS';
  83         }
  84         return $this->_regexp;
  85     }
  86
  87     /**
  88      * Match query against string.
  89      *
  90      * @param $string string The string to match.
  91      * @return boolean True if the string matches the query.
  92      */
  93     function match($string) {
  94         return preg_match($this->asRegexp(), $string);
  95     }
  96
  97     /**
  98      * Get a regular expression suitable for highlighting matched words.
  99      *
 100      * This returns a PCRE regular expression which matches any non-negated
 101      * word in the query.
 102      *
 103      * @return string The PCRE regexp.
 104      */
 105     function getHighlightRegexp() {
 106         if (!isset($this->_hilight_regexp)) {
 107             $words = array_unique($this->_tree->highlight_words());
 108             if (!$words) {
 109                 $this->_hilight_regexp = false;
 110             }
 111             else {
 112                 foreach ($words as $key => $word)
 113                     $words[$key] = preg_quote($word, '/');
 114                 $this->_hilight_regexp = '(?:' . join('|', $words) . ')';
 115             }
 116         }
 117         return $this->_hilight_regexp;
 118     }
 119
 120     /**
 121      * Make an SQL clause which matches the query.
 122      *
 123      * @param $make_sql_clause_cb WikiCallback
 124      * A callback which takes a single word as an argument and
 125      * returns an SQL clause which will match exactly those records
 126      * containing the word.  The word passed to the callback will always
 127      * be in all lower case.
 128      *
 129      * TODO: support db-specific extensions, like MATCH AGAINST or REGEX
 130      *       mysql => 4.0.1 can also do Google: MATCH AGAINST IN BOOLEAN MODE
 131      *       How? WikiDB backend method?
 132      *       Case-sensitivity option.
 133      *
 134      * Example usage:
 135      * <pre>
 136      *     function sql_title_match($word) {
 137      *         return sprintf("LOWER(title) like '%s'",
 138      *                        addslashes($word));
 139      *     }
 140      *
 141      *     ...
 142      *
 143      *     $query = new TextSearchQuery("wiki -page");
 144      *     $cb = new WikiFunctionCb('sql_title_match');
 145      *     $sql_clause = $query->makeSqlClause($cb);
 146      * </pre>
 147      * This will result in $sql_clause containing something like
 148      * "(LOWER(title) like 'wiki') AND NOT (LOWER(title) like 'page')".
 149      *
 150      * @return string The PCRE regexp.
 151      */
 152     function makeSqlClause($sql_clause_cb) {
 153         $this->_sql_clause_cb = $make_sql_clause_cb;
 154         return $this->_sql_clause($this->_tree);
 155     }
 156
 157     // get away with the callback and use a db-specific search class instead.
 158     // "WikiDB_backend_PearDB_search"
 159     // methods named as the op's.
 160     function makeSqlClauseObj(&$sql_search_cb) {
 161         $this->_sql_clause_cb = $sql_search_cb;
 162         return $this->_sql_clause_obj($this->_tree);
 163     }
 164
 165     function _sql_clause($node) {
 166         switch ($node->op) {
 167 /*      case 'EXACT':       // word => word
 168             return $this->_sql_clause_cb->call($node->word);
 169         case 'STARTS_WITH': // word => word%
 170             return $this->_sql_clause_cb->call($node->word);
 171         case 'ENDS_WITH':   // word => %word
 172             return $this->_sql_clause_cb->call($node->word);
 173 */
 174         case 'WORD':        // word => %word%
 175             return $this->_sql_clause_cb->call($node->word);
 176         case 'NOT':
 177             return "NOT (" . $this->_sql_clause($node->leaves[0]) . ")";
 178         case 'AND':
 179         case 'OR':
 180             $subclauses = array();
 181             foreach ($node->leaves as $leaf)
 182                 $subclauses[] = "(" . $this->_sql_clause($leaf) . ")";
 183             return join(" $node->op ", $subclauses);
 184         default:
 185             assert($node->op == VOID);
 186             return '1=1';
 187         }
 188     }
 189
 190     function _sql_clause_obj($node) {
 191         switch ($node->op) {
 192         case 'NOT':
 193             return "NOT (" . $this->_sql_clause_cb->call($node->leaves[0]) . ")";
 194         case 'AND':
 195         case 'OR':
 196             $subclauses = array();
 197             foreach ($node->leaves as $leaf)
 198                 $subclauses[] = "(" . $this->_sql_clause_obj($leaf) . ")";
 199             return join(" $node->op ", $subclauses);
 200         case 'VOID':
 201             return '1=1';
 202         default:
 203             return $this->_sql_clause_cb->call($node);
 204         }
 205     }
 206
 207     /**
 208      * Get printable representation of the parse tree.
 209      *
 210      * This is for debugging only.
 211      * @return string Printable parse tree.
 212      */
 213     function asString() {
 214         return $this->_as_string($this->_tree);
 215     }
 216
 217     function _as_string($node, $indent = '') {
 218         switch ($node->op) {
 219         case 'WORD':
 220             return $indent . "WORD: $node->word";
 221         case 'VOID':
 222             return $indent . "VOID";
 223         default:
 224             $lines = array($indent . $node->op . ":");
 225             $indent .= "  ";
 226             foreach ($node->leaves as $leaf)
 227                 $lines[] = $this->_as_string($leaf, $indent);
 228             return join("\n", $lines);
 229         }
 230     }
 231 }
 232
 233 /**
 234  * This is a TextSearchQuery which matches nothing.
 235  */
 236 class NullTextSearchQuery extends TextSearchQuery {
 237     /**
 238      * Create a new query.
 239      *
 240      * @see TextSearchQuery
 241      */
 242     function NullTextSearchQuery() {}
 243     function asRegexp()         { return '/^(?!a)a/x'; }
 244     function match($string)     { return false; }
 245     function getHighlightRegexp() { return ""; }
 246     function makeSqlClause($make_sql_clause_cb) { return "(1 = 0)"; }
 247     function asString() { return "NullTextSearchQuery"; }
 248 };
 249
 250
 251 ////////////////////////////////////////////////////////////////
 252 //
 253 // Remaining classes are private.
 254 //
 255 ////////////////////////////////////////////////////////////////
 256 /**
 257  * Virtual base class for nodes in a TextSearchQuery parse tree.
 258  *
 259  * Also servers as a 'VOID' (contentless) node.
 260  */
 261 class TextSearchQuery_node
 262 {
 263     var $op = 'VOID';
 264
 265     /**
 266      * Optimize this node.
 267      * @return object Optimized node.
 268      */
 269     function optimize() {
 270         return $this;
 271     }
 272
 273     /**
 274      * @return regexp matching this node.
 275      */
 276     function regexp() {
 277         return '';
 278     }
 279
 280     /**
 281      * @param bool True if this node has been negated (higher in the parse tree.)
 282      * @return array A list of all non-negated words contained by this node.
 283      */
 284     function highlight_words($negated = false) {
 285         return array();
 286     }
 287 }
 288
 289 /**
 290  * A whitespace seperated word.
 291  */
 292 class TextSearchQuery_node_word
 293 extends TextSearchQuery_node {
 294     var $op = "WORD";
 295
 296     function TextSearchQuery_node_word($word) {
 297         $this->word = $word;
 298     }
 299
 300     function regexp() {
 301         return '(?=.*' . preg_quote($this->word, '/') . ')';
 302     }
 303
 304     function highlight_words($negated = false) {
 305         return $negated ? array() : array($this->word);
 306     }
 307 }
 308
 309 class TextSearchQuery_node_starts_with
 310 extends TextSearchQuery_node_word {
 311     var $op = "STARTS_WITH";
 312     function regexp() { return '(?=' . preg_quote($this->word, '/') . ')'; }
 313 }
 314 class TextSearchQuery_node_ends_with
 315 extends TextSearchQuery_node_word {
 316     var $op = "ENDS_WITH";
 317     function regexp() { return '(?=' . preg_quote($this->word, '/') . '.*)'; }
 318 }
 319 class TextSearchQuery_node_exact
 320 extends TextSearchQuery_node_word {
 321     var $op = "EXACT";
 322     function regexp() { return '(?=\B' . preg_quote($this->word, '/') . '\b)'; }
 323 }
 324 class TextSearchQuery_node_glob
 325 extends TextSearchQuery_node_word {
 326     var $op = "REGEX";
 327     function regexp() { return '(?=\B' . preg_quote(glob_to_pcre($this->word), '/') . '\b)'; }
 328 }
 329 class TextSearchQuery_node_regex
 330 extends TextSearchQuery_node_word {
 331     var $op = "REGEX";
 332     function regexp() { return '(?=\B' . preg_quote($this->word, '/') . '\b)'; }
 333 }
 334 // FIXME for SQL
 335 class TextSearchQuery_node_pcre
 336 extends TextSearchQuery_node_word {
 337     var $op = "REGEX";
 338     function regexp() { return '(?=\B' . preg_quote($this->word, '/') . '\b)'; }
 339 }
 340
 341 /**
 342  * A negated clause.
 343  */
 344 class TextSearchQuery_node_not
 345 extends TextSearchQuery_node
 346 {
 347     var $op = "NOT";
 348
 349     function TextSearchQuery_node_not($leaf) {
 350         $this->leaves = array($leaf);
 351     }
 352
 353     function optimize() {
 354         $leaf = &$this->leaves[0];
 355         $leaf = $leaf->optimize();
 356         if ($leaf->op == 'NOT')
 357             return $leaf->leaves[0]; // ( NOT ( NOT x ) ) -> x
 358         return $this;
 359     }
 360
 361     function regexp() {
 362         $leaf = &$this->leaves[0];
 363         return '(?!' . $leaf->regexp() . ')';
 364     }
 365
 366     function highlight_words($negated = false) {
 367         return $this->leaves[0]->highlight_words(!$negated);
 368     }
 369 }
 370
 371 /**
 372  * Virtual base class for 'AND' and 'OR conjoins.
 373  */
 374 class TextSearchQuery_node_binop
 375 extends TextSearchQuery_node
 376 {
 377     function TextSearchQuery_node_binop($leaves) {
 378         $this->leaves = $leaves;
 379     }
 380
 381     function _flatten() {
 382         // This flattens e.g. (AND (AND a b) (OR c d) e)
 383         //        to (AND a b e (OR c d))
 384         $flat = array();
 385         foreach ($this->leaves as $leaf) {
 386             $leaf = $leaf->optimize();
 387             if ($this->op == $leaf->op)
 388                 $flat = array_merge($flat, $leaf->leaves);
 389             else
 390                 $flat[] = $leaf;
 391         }
 392         $this->leaves = $flat;
 393     }
 394
 395     function optimize() {
 396         $this->_flatten();
 397         assert(!empty($this->leaves));
 398         if (count($this->leaves) == 1)
 399             return $this->leaves[0]; // (AND x) -> x
 400         return $this;
 401     }
 402
 403     function highlight_words($negated = false) {
 404         $words = array();
 405         foreach ($this->leaves as $leaf)
 406             array_splice($words,0,0,
 407                          $leaf->highlight_words($negated));
 408         return $words;
 409     }
 410 }
 411
 412 /**
 413  * A (possibly multi-argument) 'AND' conjoin.
 414  */
 415 class TextSearchQuery_node_and
 416 extends TextSearchQuery_node_binop
 417 {
 418     var $op = "AND";
 419
 420     function optimize() {
 421         $this->_flatten();
 422
 423         // Convert (AND (NOT a) (NOT b) c d) into (AND (NOT (OR a b)) c d).
 424         // Since OR's are more efficient for regexp matching:
 425         //   (?!.*a)(?!.*b)  vs   (?!.*(?:a|b))
 426
 427         // Suck out the negated leaves.
 428         $nots = array();
 429         foreach ($this->leaves as $key => $leaf) {
 430             if ($leaf->op == 'NOT') {
 431                 $nots[] = $leaf->leaves[0];
 432                 unset($this->leaves[$key]);
 433             }
 434         }
 435
 436         // Combine the negated leaves into a single negated or.
 437         if ($nots) {
 438             $node = ( new TextSearchQuery_node_not
 439                       (new TextSearchQuery_node_or($nots)) );
 440             array_unshift($this->leaves, $node->optimize());
 441         }
 442
 443         assert(!empty($this->leaves));
 444         if (count($this->leaves) == 1)
 445             return $this->leaves[0];  // (AND x) -> x
 446         return $this;
 447     }
 448
 449     function regexp() {
 450         $regexp = '';
 451         foreach ($this->leaves as $leaf)
 452             $regexp .= $leaf->regexp();
 453         return $regexp;
 454     }
 455 }
 456
 457 /**
 458  * A (possibly multi-argument) 'OR' conjoin.
 459  */
 460 class TextSearchQuery_node_or
 461 extends TextSearchQuery_node_binop
 462 {
 463     var $op = "OR";
 464
 465     function regexp() {
 466         // We will combine any of our direct descendents which are WORDs
 467         // into a single (?=.*(?:word1|word2|...)) regexp.
 468
 469         $regexps = array();
 470         $words = array();
 471
 472         foreach ($this->leaves as $leaf) {
 473             if ($leaf->op == 'WORD')
 474                 $words[] = preg_quote($leaf->word, '/');
 475             else
 476                 $regexps[] = $leaf->regexp();
 477         }
 478
 479         if ($words)
 480             array_unshift($regexps,
 481                           '(?=.*' . $this->_join($words) . ')');
 482
 483         return $this->_join($regexps);
 484     }
 485
 486     function _join($regexps) {
 487         assert(count($regexps) > 0);
 488
 489         if (count($regexps) > 1)
 490             return '(?:' . join('|', $regexps) . ')';
 491         else
 492             return $regexps[0];
 493     }
 494 }
 495
 496
 497 ////////////////////////////////////////////////////////////////
 498 //
 499 // Parser:
 500 //   op's (and, or, not) are forced to lowercase in the tokenizer.
 501 //
 502 ////////////////////////////////////////////////////////////////
 503 define ('TSQ_TOK_WORD',   1);
 504 define ('TSQ_TOK_BINOP',  2);
 505 define ('TSQ_TOK_NOT',    4);
 506 define ('TSQ_TOK_LPAREN', 8);
 507 define ('TSQ_TOK_RPAREN', 16);
 508 define ('TSQ_TOK_STARTS_WITH', 32);
 509 define ('TSQ_TOK_ENDS_WITH', 64);
 510 define ('TSQ_TOK_EXACT', 128);
 511 define ('TSQ_TOK_REGEX_POSIX', 256);
 512 define ('TSQ_TOK_REGEX_PCRE', 512);
 513 define ('TSQ_TOK_REGEX_GLOB', 1024);
 514
 515 class TextSearchQuery_Parser
 516 {
 517     /*
 518      * This is a simple recursive descent parser, based on the following grammar:
 519      *
 520      * toplist  :
 521      *          | toplist expr
 522      *          ;
 523      *
 524      *
 525      * list     : expr
 526      *          | list expr
 527      *          ;
 528      *
 529      * expr     : atom
 530      *          | expr BINOP atom
 531      *          ;
 532      *
 533      * atom     : '(' list ')'
 534      *          | NOT atom
 535      *          | WORD
 536      *          ;
 537      *
 538      * The terminal tokens are:
 539      *
 540      *
 541      * and|or             BINOP
 542      * -|not              NOT
 543      * (                  LPAREN
 544      * )                  RPAREN
 545      * /[^-()\s][^()\s]*  WORD
 546      * /"[^"]*"/          WORD
 547      * /'[^']*'/          WORD
 548      * ^WORD              STARTS_WITH
 549      * WORD*              STARTS_WITH
 550      * *WORD              ENDS_WITH
 551      * ^WORD$             EXACT
 552      * /regex/            PCRE-style REGEX
 553      * re:WORD            POSIX-style REGEX
 554      */
 555
 556     function parse ($search_expr, $case_exact=false, $regex='auto') {
 557         $this->lexer = new TextSearchQuery_Lexer($search_expr, $case_exact, $regex);
 558         $tree = $this->get_list('toplevel');
 559         assert($this->lexer->eof());
 560         unset($this->lexer);
 561         return $tree;
 562     }
 563
 564     function get_list ($is_toplevel = false) {
 565         $list = array();
 566
 567         // token types we'll accept as words (and thus expr's) for the
 568         // purpose of error recovery:
 569         $accept_as_words = TSQ_TOK_NOT | TSQ_TOK_BINOP;
 570         if ($is_toplevel)
 571             $accept_as_words |= TSQ_TOK_LPAREN | TSQ_TOK_RPAREN;
 572
 573         while ( ($expr = $this->get_expr())
 574                 || ($expr = $this->get_word($accept_as_words)) ) {
 575
 576             $list[] = $expr;
 577         }
 578
 579         if (!$list) {
 580             if ($is_toplevel)
 581                 return new TextSearchQuery_node;
 582             else
 583                 return false;
 584         }
 585         return new TextSearchQuery_node_and($list);
 586     }
 587
 588     function get_expr () {
 589         if ( !($expr = $this->get_atom()) )
 590             return false;
 591
 592         $savedpos = $this->lexer->tell();
 593         while ( ($op = $this->lexer->get(TSQ_TOK_BINOP)) ) {
 594             if ( ! ($right = $this->get_atom()) ) {
 595                 break;
 596             }
 597
 598             if ($op == 'and')
 599                 $expr = new TextSearchQuery_node_and(array($expr, $right));
 600             else {
 601                 assert($op == 'or');
 602                 $expr = new TextSearchQuery_node_or(array($expr, $right));
 603             }
 604
 605             $savedpos = $this->lexer->tell();
 606         }
 607         $this->lexer->seek($savedpos);
 608
 609         return $expr;
 610     }
 611
 612
 613     function get_atom() {
 614         if ($word = $this->get_word(TSQ_TOK_WORD + TSQ_TOK_STARTS_WITH + TSQ_TOK_ENDS_WITH
 615                                    + TSQ_TOK_EXACT + TSQ_TOK_REGEX_GLOB + TSQ_TOK_REGEX_PCRE
 616                                    + TSQ_TOK_REGEX_POSIX))
 617             return $word;
 618
 619         $savedpos = $this->lexer->tell();
 620         if ( $this->lexer->get(TSQ_TOK_LPAREN) ) {
 621             if ( ($list = $this->get_list()) && $this->lexer->get(TSQ_TOK_RPAREN) )
 622                 return $list;
 623         }
 624         elseif ( $this->lexer->get(TSQ_TOK_NOT) ) {
 625             if ( ($atom = $this->get_atom()) )
 626                 return new TextSearchQuery_node_not($atom);
 627         }
 628         $this->lexer->seek($savedpos);
 629         return false;
 630     }
 631
 632     function get_word($accept = TSQ_TOK_WORD) {
 633         if ( $accept & TSQ_TOK_WORD and ($word = $this->lexer->get(TSQ_TOK_WORD)) )
 634             return new TextSearchQuery_node_word($word);
 635         if ( $accept & TSQ_TOK_STARTS_WITH and ($word = $this->lexer->get(TSQ_TOK_STARTS_WITH)) )
 636             return new TextSearchQuery_node_starts_with($word);
 637         if ( $accept & TSQ_TOK_ENDS_WITH and ($word = $this->lexer->get(TSQ_TOK_ENDS_WITH)) )
 638             return new TextSearchQuery_node_ends_with($word);
 639         if ( $accept & TSQ_TOK_EXACT and ($word = $this->lexer->get(TSQ_TOK_EXACT)) )
 640             return new TextSearchQuery_node_exact($word);
 641         if ( $accept & TSQ_TOK_REGEX_GLOB and ($word = $this->lexer->get(TSQ_TOK_REGEX_GLOB)) )
 642             return new TextSearchQuery_node_glob($word);
 643         if ( $accept & TSQ_TOK_REGEX_POSIX and ($word = $this->lexer->get(TSQ_TOK_REGEX_POSIX)) )
 644             return new TextSearchQuery_node_regex($word);
 645         if ( $accept & TSQ_TOK_REGEX_PCRE and ($word = $this->lexer->get(TSQ_TOK_REGEX_PCRE)) )
 646             return new TextSearchQuery_node_pcre($word);
 647         return false;
 648     }
 649 }
 650
 651 //TODO: support glob-style regex: $regex='glob'
 652 class TextSearchQuery_Lexer {
 653     function TextSearchQuery_Lexer ($query_str, $case_exact=false, $regex='auto') {
 654         $this->tokens = $this->tokenize($query_str, $case_exact, $regex);
 655         $this->pos = 0;
 656     }
 657
 658     function tell() {
 659         return $this->pos;
 660     }
 661
 662     function seek($pos) {
 663         $this->pos = $pos;
 664     }
 665
 666     function eof() {
 667         return $this->pos == count($this->tokens);
 668     }
 669
 670     function tokenize($string, $case_exact=false, $regex='auto') {
 671         $tokens = array();
 672         $buf = $case_exact ? ltrim($string) : strtolower(ltrim($string));
 673         while (!empty($buf)) {
 674             if (preg_match('/^(and|or)\b\s*/i', $buf, $m)) {
 675                 $val = strtolower($m[1]);
 676                 $type = TSQ_TOK_BINOP;
 677             }
 678             elseif (preg_match('/^(-|not\b)\s*/i', $buf, $m)) {
 679                 $val = strtolower($m[1]);
 680                 $type = TSQ_TOK_NOT;
 681             }
 682             elseif (preg_match('/^([()])\s*/', $buf, $m)) {
 683                 $val = $m[1];
 684                 $type = $m[1] == '(' ? TSQ_TOK_LPAREN : TSQ_TOK_RPAREN;
 685             }
 686             elseif (preg_match('/^re:([^-()][^()\s]*)\s*/', $buf, $m)) {
 687                 $regex = true; // posix-style
 688                 $val = $m[1];
 689                 $type = TSQ_TOK_REGEX_POSIX;
 690             }
 691             elseif (preg_match('/^\/([^-()][^()\s]*)\/\s*/', $buf, $m)) {
 692                 $regex = true; // pcre-style
 693                 $val = $m[1];
 694                 $type = TSQ_TOK_REGEX_PCRE;
 695             }
 696             elseif ($regex and preg_match('/^\^([^-()][^()\s]*)\$\s*/', $buf, $m)) {
 697                 $val = $m[1];
 698                 $type = TSQ_TOK_EXACT;
 699             }
 700             elseif ($regex and preg_match('/^\^([^-()][^()\s]*)\s*/', $buf, $m)) {
 701                 $val = $m[1];
 702                 $type = TSQ_TOK_STARTS_WITH;
 703             }
 704             elseif ($regex and preg_match('/^([^-()][^()\s]*)\*\s*/', $buf, $m)) {
 705                 $val = $m[1];
 706                 $type = TSQ_TOK_STARTS_WITH;
 707             }
 708             elseif ($regex and preg_match('/^\*([^-()][^()\s]*)\s*/', $buf, $m)) {
 709                 $val = $m[1];
 710                 $type = TSQ_TOK_ENDS_WITH;
 711             }
 712             elseif (preg_match('/^ " ( (?: [^"]+ | "" )* ) " \s*/x', $buf, $m)) {
 713                 $val = str_replace('""', '"', $m[1]);
 714                 $type = TSQ_TOK_WORD;
 715             }
 716             elseif (preg_match("/^ ' ( (?:[^']+|'')* ) ' \s*/x", $buf, $m)) {
 717                 $val = str_replace("''", "'", $m[1]);
 718                 $type = TSQ_TOK_WORD;
 719             }
 720             elseif (preg_match('/^([^-()][^()\s]*)\s*/', $buf, $m)) {
 721                 $val = $m[1];
 722                 $type = TSQ_TOK_WORD;
 723             }
 724             else {
 725                 assert(empty($buf));
 726                 break;
 727             }
 728             $buf = substr($buf, strlen($m[0]));
 729
 730             /* refine the simple parsing from above: bla*bla, bla?bla
 731
 732             if ($regex and $type == TSQ_TOK_WORD) {
 733                 if (substr($val,0,1) == "^")
 734                     $type = TSQ_TOK_STARTS_WITH;
 735                 elseif (substr($val,0,1) == "*")
 736                     $type = TSQ_TOK_ENDS_WITH;
 737                 elseif (substr($val,-1,1) == "*")
 738                     $type = TSQ_TOK_STARTS_WITH;
 739             } */
 740             $tokens[] = array($type, $val);
 741         }
 742         return $tokens;
 743     }
 744
 745     function get($accept) {
 746         if ($this->pos >= count($this->tokens))
 747             return false;
 748
 749         list ($type, $val) = $this->tokens[$this->pos];
 750         if (($type & $accept) == 0)
 751             return false;
 752
 753         $this->pos++;
 754         return $val;
 755     }
 756 }
 757
 758 // Local Variables:
 759 // mode: php
 760 // tab-width: 8
 761 // c-basic-offset: 4
 762 // c-hanging-comment-ender-p: nil
 763 // indent-tabs-mode: nil
 764 // End:
 765 ?>