headers/private/file_systems/QueryParser.h

   1 /*
   2  * Copyright 2001-2014, Axel Dörfler, axeld@pinc-software.de.
   3  * Copyright 2010, Clemens Zeidler <haiku@clemens-zeidler.de>
   4  * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de.
   5  * This file may be used under the terms of the MIT License.
   6  */
   7 #ifndef _FILE_SYSTEMS_QUERY_PARSER_H
   8 #define _FILE_SYSTEMS_QUERY_PARSER_H
   9
  10
  11 /*!     Query parsing and evaluation
  12
  13         The pattern matching is roughly based on code originally written
  14         by J. Kercheval, and on code written by Kenneth Almquist, though
  15         it shares no code.
  16 */
  17
  18
  19 // The parser has a very static design, but it will do what is required.
  20 //
  21 // ParseOr(), ParseAnd(), ParseEquation() are guarantying the operator
  22 // precedence, that is =,!=,>,<,>=,<= .. && .. ||.
  23 // Apparently, the "!" (not) can only be used with brackets.
  24 //
  25 // If you think that there are too few NULL pointer checks in some places
  26 // of the code, just read the beginning of the query constructor.
  27 // The API is not fully available, just the Query and the Expression class
  28 // are.
  29
  30 #ifdef FS_SHELL
  31 #       include <new>
  32
  33 #       include "fssh_api_wrapper.h"
  34 #       include "fssh_auto_deleter.h"
  35 #else
  36 #       include <dirent.h>
  37 #       include <stdlib.h>
  38 #       include <string.h>
  39
  40 #       include <algorithm>
  41 #       include <new>
  42
  43 #       include <fs_interface.h>
  44 #       include <fs_query.h>
  45 #       include <TypeConstants.h>
  46
  47 #       include <util/SinglyLinkedList.h>
  48 #       include <util/Stack.h>
  49
  50 #       include <query_private.h>
  51
  52 #       include <lock.h>
  53 #endif  // !FS_SHELL
  54
  55 #include <file_systems/QueryParserUtils.h>
  56
  57
  58 //#define DEBUG_QUERY
  59
  60 #ifndef QUERY_RETURN_ERROR
  61 #       define QUERY_RETURN_ERROR(error)        return (error)
  62 #endif
  63
  64 #ifndef QUERY_REPORT_ERROR
  65 #       define QUERY_REPORT_ERROR(error)        do {} while (false)
  66 #endif
  67
  68 #ifndef QUERY_FATAL
  69 #       define QUERY_FATAL(message...)          panic(message)
  70 #endif
  71
  72 #ifndef QUERY_INFORM
  73 #       define QUERY_INFORM(message...)         dprintf(message)
  74 #endif
  75
  76 #ifndef QUERY_D
  77 #       define QUERY_D(block)
  78 #endif
  79
  80
  81 namespace QueryParser {
  82
  83
  84 template<typename QueryPolicy> class Equation;
  85 template<typename QueryPolicy> class Expression;
  86 template<typename QueryPolicy> class Term;
  87 template<typename QueryPolicy> class Query;
  88
  89
  90 enum ops {
  91         OP_NONE,
  92
  93         OP_AND,
  94         OP_OR,
  95
  96         OP_EQUATION,
  97                 // is only used for invalid equations
  98
  99         OP_EQUAL,
 100         OP_UNEQUAL,
 101         OP_GREATER_THAN,
 102         OP_LESS_THAN,
 103         OP_GREATER_THAN_OR_EQUAL,
 104         OP_LESS_THAN_OR_EQUAL,
 105 };
 106
 107
 108 template<typename QueryPolicy>
 109 union value {
 110         int64   Int64;
 111         uint64  Uint64;
 112         int32   Int32;
 113         uint32  Uint32;
 114         float   Float;
 115         double  Double;
 116         char    String[QueryPolicy::kMaxFileNameLength];
 117 };
 118
 119
 120 template<typename QueryPolicy>
 121 class Query {
 122 public:
 123                         typedef typename QueryPolicy::Entry Entry;
 124                         typedef typename QueryPolicy::Index Index;
 125                         typedef typename QueryPolicy::IndexIterator IndexIterator;
 126                         typedef typename QueryPolicy::Node Node;
 127                         typedef typename QueryPolicy::Context Context;
 128
 129 public:
 130                                                         Query(Context* context,
 131                                                                 Expression<QueryPolicy>* expression,
 132                                                                 uint32 flags, port_id port, uint32 token);
 133                                                         ~Query();
 134
 135         static  status_t                Create(Context* context, const char* queryString,
 136                                                                 uint32 flags, port_id port, uint32 token,
 137                                                                 Query<QueryPolicy>*& _query);
 138
 139                         status_t                Rewind();
 140         inline  status_t                GetNextEntry(struct dirent* dirent, size_t size);
 141
 142                         void                    LiveUpdate(Entry* entry, Node* node,
 143                                                                 const char* attribute, int32 type,
 144                                                                 const uint8* oldKey, size_t oldLength,
 145                                                                 const uint8* newKey, size_t newLength);
 146                         void                    LiveUpdateRenameMove(Entry* entry, Node* node,
 147                                                                 ino_t oldDirectoryID, const char* oldName,
 148                                                                 size_t oldLength, ino_t newDirectoryID,
 149                                                                 const char* newName, size_t newLength);
 150
 151                         Expression<QueryPolicy>* GetExpression() const
 152                                                                 { return fExpression; }
 153
 154                         uint32                  Flags() const
 155                                                                 { return fFlags; }
 156
 157 private:
 158                         status_t                _GetNextEntry(struct dirent* dirent, size_t size);
 159                         void                    _SendEntryNotification(Entry* entry,
 160                                                                 status_t (*notify)(port_id, int32, dev_t, ino_t,
 161                                                                         const char*, ino_t));
 162
 163 private:
 164                         Context*                fContext;
 165                         Expression<QueryPolicy>* fExpression;
 166                         Equation<QueryPolicy>* fCurrent;
 167                         IndexIterator*  fIterator;
 168                         Index                   fIndex;
 169                         Stack<Equation<QueryPolicy>*> fStack;
 170
 171                         uint32                  fFlags;
 172                         port_id                 fPort;
 173                         int32                   fToken;
 174                         bool                    fNeedsEntry;
 175 };
 176
 177
 178 /*!     Abstract base class for the operator/equation classes.
 179 */
 180 template<typename QueryPolicy>
 181 class Term {
 182 public:
 183                         typedef typename QueryPolicy::Entry Entry;
 184                         typedef typename QueryPolicy::Index Index;
 185                         typedef typename QueryPolicy::IndexIterator IndexIterator;
 186                         typedef typename QueryPolicy::Node Node;
 187                         typedef typename QueryPolicy::Context Context;
 188
 189 public:
 190                                                 Term(int8 op) : fOp(op), fParent(NULL) {}
 191         virtual                         ~Term() {}
 192
 193                         int8            Op() const { return fOp; }
 194
 195                         void            SetParent(Term<QueryPolicy>* parent)
 196                                                         { fParent = parent; }
 197                         Term<QueryPolicy>* Parent() const { return fParent; }
 198
 199         virtual status_t        Match(Entry* entry, Node* node,
 200                                                         const char* attribute = NULL, int32 type = 0,
 201                                                         const uint8* key = NULL, size_t size = 0) = 0;
 202         virtual void            Complement() = 0;
 203
 204         virtual void            CalculateScore(Index& index) = 0;
 205         virtual int32           Score() const = 0;
 206
 207         virtual status_t        InitCheck() = 0;
 208
 209         virtual bool            NeedsEntry() = 0;
 210
 211 #ifdef DEBUG_QUERY
 212         virtual void            PrintToStream() = 0;
 213 #endif
 214
 215 protected:
 216                         int8            fOp;
 217                         Term<QueryPolicy>* fParent;
 218 };
 219
 220
 221 /*!     An Equation object represents an "attribute-equation operator-value" pair.
 222
 223         Although an Equation object is quite independent from the volume on which
 224         the query is run, there are some dependencies that are produced while
 225         querying:
 226         The type/size of the value, the score, and if it has an index or not.
 227         So you could run more than one query on the same volume, but it might return
 228         wrong values when it runs concurrently on another volume.
 229         That's not an issue right now, because we run single-threaded and don't use
 230         queries more than once.
 231 */
 232 template<typename QueryPolicy>
 233 class Equation : public Term<QueryPolicy> {
 234 public:
 235                         typedef typename QueryPolicy::Entry Entry;
 236                         typedef typename QueryPolicy::Index Index;
 237                         typedef typename QueryPolicy::IndexIterator IndexIterator;
 238                         typedef typename QueryPolicy::Node Node;
 239                         typedef typename QueryPolicy::Context Context;
 240
 241 public:
 242                                                 Equation(char** expression);
 243         virtual                         ~Equation();
 244
 245         virtual status_t        InitCheck();
 246
 247                         status_t        ParseQuotedString(char** _start, char** _end);
 248                         char*           CopyString(char* start, char* end);
 249
 250         virtual status_t        Match(Entry* entry, Node* node,
 251                                                         const char* attribute = NULL, int32 type = 0,
 252                                                         const uint8* key = NULL, size_t size = 0);
 253         virtual void            Complement();
 254
 255                         status_t        PrepareQuery(Context* context, Index& index,
 256                                                         IndexIterator** iterator, bool queryNonIndexed);
 257                         status_t        GetNextMatching(Context* context,
 258                                                         IndexIterator* iterator, struct dirent* dirent,
 259                                                         size_t bufferSize);
 260
 261         virtual void            CalculateScore(Index &index);
 262         virtual int32           Score() const { return fScore; }
 263
 264         virtual bool            NeedsEntry();
 265
 266 #ifdef DEBUG_QUERY
 267         virtual void            PrintToStream();
 268 #endif
 269
 270 private:
 271                                                 Equation(const Equation& other);
 272                                                 Equation& operator=(const Equation& other);
 273                                                         // no implementation
 274
 275                         status_t        ConvertValue(type_code type);
 276                         bool            CompareTo(const uint8* value, size_t size);
 277                         uint8*          Value() const { return (uint8*)&fValue; }
 278                         status_t        MatchEmptyString();
 279
 280                         char*           fAttribute;
 281                         char*           fString;
 282                         union value<QueryPolicy> fValue;
 283                         type_code       fType;
 284                         size_t          fSize;
 285                         bool            fIsPattern;
 286
 287                         int32           fScore;
 288                         bool            fHasIndex;
 289 };
 290
 291
 292 /*!     The Operator class does not represent a generic operator, but only those
 293         that combine two equations, namely "or", and "and".
 294 */
 295 template<typename QueryPolicy>
 296 class Operator : public Term<QueryPolicy> {
 297 public:
 298                         typedef typename QueryPolicy::Entry Entry;
 299                         typedef typename QueryPolicy::Index Index;
 300                         typedef typename QueryPolicy::IndexIterator IndexIterator;
 301                         typedef typename QueryPolicy::Node Node;
 302                         typedef typename QueryPolicy::Context Context;
 303
 304 public:
 305                                                 Operator(Term<QueryPolicy>* left, int8 op,
 306                                                         Term<QueryPolicy>* right);
 307         virtual                         ~Operator();
 308
 309                         Term<QueryPolicy>* Left() const { return fLeft; }
 310                         Term<QueryPolicy>* Right() const { return fRight; }
 311
 312         virtual status_t        Match(Entry* entry, Node* node,
 313                                                         const char* attribute = NULL, int32 type = 0,
 314                                                         const uint8* key = NULL, size_t size = 0);
 315         virtual void            Complement();
 316
 317         virtual void            CalculateScore(Index& index);
 318         virtual int32           Score() const;
 319
 320         virtual status_t        InitCheck();
 321
 322         virtual bool            NeedsEntry();
 323
 324 #ifdef DEBUG_QUERY
 325         virtual void            PrintToStream();
 326 #endif
 327
 328 private:
 329                                                 Operator(const Operator& other);
 330                                                 Operator& operator=(const Operator& other);
 331                                                         // no implementation
 332
 333                         Term<QueryPolicy>* fLeft;
 334                         Term<QueryPolicy>* fRight;
 335 };
 336
 337
 338 template<typename QueryPolicy>
 339 class Expression {
 340 public:
 341                         typedef typename QueryPolicy::Entry Entry;
 342                         typedef typename QueryPolicy::Index Index;
 343                         typedef typename QueryPolicy::IndexIterator IndexIterator;
 344                         typedef typename QueryPolicy::Node Node;
 345                         typedef typename QueryPolicy::Context Context;
 346
 347 public:
 348                                                         Expression(char* expr);
 349                                                         ~Expression();
 350
 351                         status_t                InitCheck();
 352                         const char*             Position() const { return fPosition; }
 353                         Term<QueryPolicy>* Root() const { return fTerm; }
 354
 355 protected:
 356                         Term<QueryPolicy>* ParseOr(char** expr);
 357                         Term<QueryPolicy>* ParseAnd(char** expr);
 358                         Term<QueryPolicy>* ParseEquation(char** expr);
 359
 360                         bool                    IsOperator(char** expr, char op);
 361
 362 private:
 363                                                         Expression(const Expression& other);
 364                                                         Expression& operator=(const Expression& other);
 365                                                                 // no implementation
 366
 367                         char*                   fPosition;
 368                         Term<QueryPolicy>* fTerm;
 369 };
 370
 371
 372 //      #pragma mark -
 373
 374
 375 template<typename QueryPolicy>
 376 Equation<QueryPolicy>::Equation(char** expr)
 377         :
 378         Term<QueryPolicy>(OP_EQUATION),
 379         fAttribute(NULL),
 380         fString(NULL),
 381         fType(0),
 382         fIsPattern(false)
 383 {
 384         char* string = *expr;
 385         char* start = string;
 386         char* end = NULL;
 387
 388         // Since the equation is the integral part of any query, we're just parsing
 389         // the whole thing here.
 390         // The whitespace at the start is already removed in
 391         // Expression::ParseEquation()
 392
 393         if (*start == '"' || *start == '\'') {
 394                 // string is quoted (start has to be on the beginning of a string)
 395                 if (ParseQuotedString(&start, &end) < B_OK)
 396                         return;
 397
 398                 // set string to a valid start of the equation symbol
 399                 string = end + 2;
 400                 skipWhitespace(&string);
 401                 if (*string != '=' && *string != '<' && *string != '>'
 402                         && *string != '!') {
 403                         *expr = string;
 404                         return;
 405                 }
 406         } else {
 407                 // search the (in)equation for the actual equation symbol (and for other operators
 408                 // in case the equation is malformed)
 409                 while (*string && *string != '=' && *string != '<' && *string != '>'
 410                         && *string != '!' && *string != '&' && *string != '|') {
 411                         string++;
 412                 }
 413
 414                 // get the attribute string     (and trim whitespace), in case
 415                 // the string was not quoted
 416                 end = string - 1;
 417                 skipWhitespaceReverse(&end, start);
 418         }
 419
 420         // attribute string is empty (which is not allowed)
 421         if (start > end)
 422                 return;
 423
 424         // At this point, "start" points to the beginning of the string, "end"
 425         // points to the last character of the string, and "string" points to the
 426         // first character of the equation symbol
 427
 428         // test for the right symbol (as this doesn't need any memory)
 429         switch (*string) {
 430                 case '=':
 431                         Term<QueryPolicy>::fOp = OP_EQUAL;
 432                         break;
 433                 case '>':
 434                         Term<QueryPolicy>::fOp = *(string + 1) == '='
 435                                 ? OP_GREATER_THAN_OR_EQUAL : OP_GREATER_THAN;
 436                         break;
 437                 case '<':
 438                         Term<QueryPolicy>::fOp = *(string + 1) == '='
 439                                 ? OP_LESS_THAN_OR_EQUAL : OP_LESS_THAN;
 440                         break;
 441                 case '!':
 442                         if (*(string + 1) != '=')
 443                                 return;
 444                         Term<QueryPolicy>::fOp = OP_UNEQUAL;
 445                         break;
 446
 447                 // any invalid characters will be rejected
 448                 default:
 449                         *expr = string;
 450                         return;
 451         }
 452
 453         // lets change "start" to point to the first character after the symbol
 454         if (*(string + 1) == '=')
 455                 string++;
 456         string++;
 457         skipWhitespace(&string);
 458
 459         // allocate & copy the attribute string
 460
 461         fAttribute = CopyString(start, end);
 462         if (fAttribute == NULL)
 463                 return;
 464
 465         start = string;
 466         if (*start == '"' || *start == '\'') {
 467                 // string is quoted (start has to be on the beginning of a string)
 468                 if (ParseQuotedString(&start, &end) < B_OK)
 469                         return;
 470
 471                 string = end + 2;
 472                 skipWhitespace(&string);
 473         } else {
 474                 while (*string && *string != '&' && *string != '|' && *string != ')')
 475                         string++;
 476
 477                 end = string - 1;
 478                 skipWhitespaceReverse(&end, start);
 479         }
 480
 481         // at this point, "start" will point to the first character of the value,
 482         // "end" will point to its last character, and "start" to the first non-
 483         // whitespace character after the value string
 484
 485         fString = CopyString(start, end);
 486         if (fString == NULL)
 487                 return;
 488
 489         // patterns are only allowed for these operations (and strings)
 490         if (Term<QueryPolicy>::fOp == OP_EQUAL
 491                 || Term<QueryPolicy>::fOp == OP_UNEQUAL) {
 492                 fIsPattern = isPattern(fString);
 493                 if (fIsPattern && isValidPattern(fString) < B_OK) {
 494                         // we only want to have valid patterns; setting fString
 495                         // to NULL will cause InitCheck() to fail
 496                         free(fString);
 497                         fString = NULL;
 498                 }
 499         }
 500
 501         *expr = string;
 502 }
 503
 504
 505 template<typename QueryPolicy>
 506 Equation<QueryPolicy>::~Equation()
 507 {
 508         free(fAttribute);
 509         free(fString);
 510 }
 511
 512
 513 template<typename QueryPolicy>
 514 status_t
 515 Equation<QueryPolicy>::InitCheck()
 516 {
 517         if (fAttribute == NULL || fString == NULL
 518                 || Term<QueryPolicy>::fOp == OP_NONE) {
 519                 return B_BAD_VALUE;
 520         }
 521
 522         return B_OK;
 523 }
 524
 525
 526 template<typename QueryPolicy>
 527 status_t
 528 Equation<QueryPolicy>::ParseQuotedString(char** _start, char** _end)
 529 {
 530         char* start = *_start;
 531         char quote = *start++;
 532         char* end = start;
 533
 534         for (; *end && *end != quote; end++) {
 535                 if (*end == '\\')
 536                         end++;
 537         }
 538         if (*end == '\0')
 539                 return B_BAD_VALUE;
 540
 541         *_start = start;
 542         *_end = end - 1;
 543
 544         return B_OK;
 545 }
 546
 547
 548 template<typename QueryPolicy>
 549 char*
 550 Equation<QueryPolicy>::CopyString(char* start, char* end)
 551 {
 552         // end points to the last character of the string - and the length
 553         // also has to include the null-termination
 554         int32 length = end + 2 - start;
 555         // just to make sure; since that's the max. attribute name length and
 556         // the max. string in an index, it make sense to have it that way
 557         if (length > QueryPolicy::kMaxFileNameLength || length <= 0)
 558                 return NULL;
 559
 560         char* copy = (char*)malloc(length);
 561         if (copy == NULL)
 562                 return NULL;
 563
 564         memcpy(copy, start, length - 1);
 565         copy[length - 1] = '\0';
 566
 567         return copy;
 568 }
 569
 570
 571 template<typename QueryPolicy>
 572 status_t
 573 Equation<QueryPolicy>::ConvertValue(type_code type)
 574 {
 575         // Has the type already been converted?
 576         if (type == fType)
 577                 return B_OK;
 578
 579         char* string = fString;
 580
 581         switch (type) {
 582                 case B_MIME_STRING_TYPE:
 583                         type = B_STRING_TYPE;
 584                         // supposed to fall through
 585                 case B_STRING_TYPE:
 586                         strncpy(fValue.String, string, QueryPolicy::kMaxFileNameLength);
 587                         fValue.String[QueryPolicy::kMaxFileNameLength - 1] = '\0';
 588                         fSize = strlen(fValue.String);
 589                         break;
 590                 case B_INT32_TYPE:
 591                         fValue.Int32 = strtol(string, &string, 0);
 592                         fSize = sizeof(int32);
 593                         break;
 594                 case B_UINT32_TYPE:
 595                         fValue.Int32 = strtoul(string, &string, 0);
 596                         fSize = sizeof(uint32);
 597                         break;
 598                 case B_INT64_TYPE:
 599                         fValue.Int64 = strtoll(string, &string, 0);
 600                         fSize = sizeof(int64);
 601                         break;
 602                 case B_UINT64_TYPE:
 603                         fValue.Uint64 = strtoull(string, &string, 0);
 604                         fSize = sizeof(uint64);
 605                         break;
 606                 case B_FLOAT_TYPE:
 607                         fValue.Float = strtod(string, &string);
 608                         fSize = sizeof(float);
 609                         break;
 610                 case B_DOUBLE_TYPE:
 611                         fValue.Double = strtod(string, &string);
 612                         fSize = sizeof(double);
 613                         break;
 614                 default:
 615                         QUERY_FATAL("query value conversion to 0x%x requested!\n",
 616                                 (int)type);
 617                         // should we fail here or just do a safety int32 conversion?
 618                         return B_ERROR;
 619         }
 620
 621         fType = type;
 622
 623         // patterns are only allowed for string types
 624         if (fType != B_STRING_TYPE && fIsPattern)
 625                 fIsPattern = false;
 626
 627         return B_OK;
 628 }
 629
 630
 631 /*!     Returns true when the key matches the equation. You have to
 632         call ConvertValue() before this one.
 633 */
 634 template<typename QueryPolicy>
 635 bool
 636 Equation<QueryPolicy>::CompareTo(const uint8* value, size_t size)
 637 {
 638         int32 compare;
 639
 640         // fIsPattern is only true if it's a string type, and fOp OP_EQUAL, or
 641         // OP_UNEQUAL
 642         if (fIsPattern) {
 643                 // we have already validated the pattern, so we don't check for failing
 644                 // here - if something is broken, and matchString() returns an error,
 645                 // we just don't match
 646                 compare = matchString(fValue.String, (char*)value) == MATCH_OK ? 0 : 1;
 647         } else
 648                 compare = compareKeys(fType, value, size, Value(), fSize);
 649
 650         switch (Term<QueryPolicy>::fOp) {
 651                 case OP_EQUAL:
 652                         return compare == 0;
 653                 case OP_UNEQUAL:
 654                         return compare != 0;
 655                 case OP_LESS_THAN:
 656                         return compare < 0;
 657                 case OP_LESS_THAN_OR_EQUAL:
 658                         return compare <= 0;
 659                 case OP_GREATER_THAN:
 660                         return compare > 0;
 661                 case OP_GREATER_THAN_OR_EQUAL:
 662                         return compare >= 0;
 663         }
 664         QUERY_FATAL("Unknown/Unsupported operation: %d\n", Term<QueryPolicy>::fOp);
 665         return false;
 666 }
 667
 668
 669 template<typename QueryPolicy>
 670 void
 671 Equation<QueryPolicy>::Complement()
 672 {
 673         QUERY_D(if (fOp <= OP_EQUATION || fOp > OP_LESS_THAN_OR_EQUAL) {
 674                 QUERY_FATAL("op out of range!\n");
 675                 return;
 676         });
 677
 678         int8 complementOp[] = {OP_UNEQUAL, OP_EQUAL, OP_LESS_THAN_OR_EQUAL,
 679                         OP_GREATER_THAN_OR_EQUAL, OP_LESS_THAN, OP_GREATER_THAN};
 680         Term<QueryPolicy>::fOp = complementOp[Term<QueryPolicy>::fOp - OP_EQUAL];
 681 }
 682
 683
 684 template<typename QueryPolicy>
 685 status_t
 686 Equation<QueryPolicy>::MatchEmptyString()
 687 {
 688         // There is no matching attribute, we will just bail out if we
 689         // already know that our value is not of a string type.
 690         // If not, it will be converted to a string - and then be compared with "".
 691         // That's why we have to call ConvertValue() here - but it will be
 692         // a cheap call for the next time
 693         // TODO: Should we do this only for OP_UNEQUAL?
 694         if (fType != 0 && fType != B_STRING_TYPE)
 695                 return NO_MATCH;
 696
 697         status_t status = ConvertValue(B_STRING_TYPE);
 698         if (status == B_OK)
 699                 status = CompareTo((const uint8*)"", fSize) ? MATCH_OK : NO_MATCH;
 700
 701         return status;
 702 }
 703
 704
 705 /*!     Matches the node's attribute value with the equation.
 706         Returns MATCH_OK if it matches, NO_MATCH if not, < 0 if something went
 707         wrong.
 708 */
 709 template<typename QueryPolicy>
 710 status_t
 711 Equation<QueryPolicy>::Match(Entry* entry, Node* node,
 712         const char* attributeName, int32 type, const uint8* key, size_t size)
 713 {
 714         // get a pointer to the attribute in question
 715         union value<QueryPolicy> value;
 716         uint8* buffer = (uint8*)&value;
 717         const size_t bufferSize = sizeof(value);
 718
 719         // first, check if we are matching for a live query and use that value
 720         if (attributeName != NULL && !strcmp(fAttribute, attributeName)) {
 721                 if (key == NULL) {
 722                         if (type == B_STRING_TYPE)
 723                                 return MatchEmptyString();
 724
 725                         return NO_MATCH;
 726                 }
 727                 buffer = const_cast<uint8*>(key);
 728         } else if (!strcmp(fAttribute, "name")) {
 729                 // if not, check for "fake" attributes ("name", "size", "last_modified")
 730                 if (entry == NULL)
 731                         return B_ERROR;
 732                 buffer = (uint8*)QueryPolicy::EntryGetNameNoCopy(entry, buffer,
 733                         sizeof(value));
 734                 if (buffer == NULL)
 735                         return B_ERROR;
 736
 737                 type = B_STRING_TYPE;
 738                 size = strlen((const char*)buffer);
 739         } else if (!strcmp(fAttribute, "size")) {
 740                 value.Int64 = QueryPolicy::NodeGetSize(node);
 741                 type = B_INT64_TYPE;
 742         } else if (!strcmp(fAttribute, "last_modified")) {
 743                 value.Int32 = QueryPolicy::NodeGetLastModifiedTime(node);
 744                 type = B_INT32_TYPE;
 745         } else {
 746                 // then for attributes
 747                 size = bufferSize;
 748                 if (QueryPolicy::NodeGetAttribute(node, fAttribute, buffer, &size,
 749                                 &type) != B_OK) {
 750                         return MatchEmptyString();
 751                 }
 752         }
 753
 754         // prepare own value for use, if it is possible to convert it
 755         status_t status = ConvertValue(type);
 756         if (status == B_OK)
 757                 status = CompareTo(buffer, size) ? MATCH_OK : NO_MATCH;
 758
 759         QUERY_RETURN_ERROR(status);
 760 }
 761
 762
 763 template<typename QueryPolicy>
 764 void
 765 Equation<QueryPolicy>::CalculateScore(Index &index)
 766 {
 767         // As always, these values could be tuned and refined.
 768         // And the code could also need some real world testing :-)
 769
 770         // do we have to operate on a "foreign" index?
 771         if (Term<QueryPolicy>::fOp == OP_UNEQUAL
 772                 || QueryPolicy::IndexSetTo(index, fAttribute) < B_OK) {
 773                 fScore = 0;
 774                 return;
 775         }
 776
 777         // if we have a pattern, how much does it help our search?
 778         if (fIsPattern)
 779                 fScore = getFirstPatternSymbol(fString) << 3;
 780         else {
 781                 // Score by operator
 782                 if (Term<QueryPolicy>::fOp == OP_EQUAL) {
 783                         // higher than pattern="255 chars+*"
 784                         fScore = 2048;
 785                 } else {
 786                         // the pattern search is regarded cheaper when you have at
 787                         // least one character to set your index to
 788                         fScore = 5;
 789                 }
 790         }
 791
 792         // take index size into account
 793         fScore = QueryPolicy::IndexGetWeightedScore(index, fScore);
 794 }
 795
 796
 797 template<typename QueryPolicy>
 798 status_t
 799 Equation<QueryPolicy>::PrepareQuery(Context* /*context*/, Index& index,
 800         IndexIterator** iterator, bool queryNonIndexed)
 801 {
 802         status_t status = QueryPolicy::IndexSetTo(index, fAttribute);
 803
 804         // if we should query attributes without an index, we can just proceed here
 805         if (status != B_OK && !queryNonIndexed)
 806                 return B_ENTRY_NOT_FOUND;
 807
 808         type_code type;
 809
 810         // Special case for OP_UNEQUAL - it will always operate through the whole
 811         // index but we need the call to the original index to get the correct type
 812         if (status != B_OK || Term<QueryPolicy>::fOp == OP_UNEQUAL) {
 813                 // Try to get an index that holds all files (name)
 814                 // Also sets the default type for all attributes without index
 815                 // to string.
 816                 type = status < B_OK ? B_STRING_TYPE : QueryPolicy::IndexGetType(index);
 817
 818                 if (QueryPolicy::IndexSetTo(index, "name") != B_OK)
 819                         return B_ENTRY_NOT_FOUND;
 820
 821                 fHasIndex = false;
 822         } else {
 823                 fHasIndex = true;
 824                 type = QueryPolicy::IndexGetType(index);
 825         }
 826
 827         if (ConvertValue(type) < B_OK)
 828                 return B_BAD_VALUE;
 829
 830         *iterator = QueryPolicy::IndexCreateIterator(index);
 831         if (*iterator == NULL)
 832                 return B_NO_MEMORY;
 833
 834         if ((Term<QueryPolicy>::fOp == OP_EQUAL
 835                         || Term<QueryPolicy>::fOp == OP_GREATER_THAN
 836                         || Term<QueryPolicy>::fOp == OP_GREATER_THAN_OR_EQUAL || fIsPattern)
 837                 && fHasIndex) {
 838                 // set iterator to the exact position
 839
 840                 int32 keySize = QueryPolicy::IndexGetKeySize(index);
 841
 842                 // At this point, fIsPattern is only true if it's a string type, and fOp
 843                 // is either OP_EQUAL or OP_UNEQUAL
 844                 if (fIsPattern) {
 845                         // let's see if we can use the beginning of the key for positioning
 846                         // the iterator and adjust the key size; if not, just leave the
 847                         // iterator at the start and return success
 848                         keySize = getFirstPatternSymbol(fString);
 849                         if (keySize <= 0)
 850                                 return B_OK;
 851                 }
 852
 853                 if (keySize == 0) {
 854                         // B_STRING_TYPE doesn't have a fixed length, so it was set
 855                         // to 0 before - we compute the correct value here
 856                         if (fType == B_STRING_TYPE) {
 857                                 keySize = strlen(fValue.String);
 858
 859                                 // The empty string is a special case - we normally don't check
 860                                 // for the trailing null byte, in the case for the empty string
 861                                 // we do it explicitly, because there can't be keys in the
 862                                 // B+tree with a length of zero
 863                                 if (keySize == 0)
 864                                         keySize = 1;
 865                         } else
 866                                 QUERY_RETURN_ERROR(B_ENTRY_NOT_FOUND);
 867                 }
 868
 869                 status = QueryPolicy::IndexIteratorFind(*iterator, Value(), keySize);
 870                 if (Term<QueryPolicy>::fOp == OP_EQUAL && !fIsPattern)
 871                         return status;
 872                 else if (status == B_ENTRY_NOT_FOUND
 873                         && (fIsPattern || Term<QueryPolicy>::fOp == OP_GREATER_THAN
 874                                 || Term<QueryPolicy>::fOp == OP_GREATER_THAN_OR_EQUAL))
 875                         return B_OK;
 876
 877                 QUERY_RETURN_ERROR(status);
 878         }
 879
 880         return B_OK;
 881 }
 882
 883
 884 template<typename QueryPolicy>
 885 status_t
 886 Equation<QueryPolicy>::GetNextMatching(Context* context,
 887         IndexIterator* iterator, struct dirent* dirent, size_t bufferSize)
 888 {
 889         while (true) {
 890                 union value<QueryPolicy> indexValue;
 891                 size_t keyLength;
 892                 Entry* entry = NULL;
 893
 894                 status_t status = QueryPolicy::IndexIteratorGetNextEntry(iterator,
 895                         &indexValue, &keyLength, (size_t)sizeof(indexValue), &entry);
 896                 if (status != B_OK)
 897                         return status;
 898
 899                 // only compare against the index entry when this is the correct
 900                 // index for the equation
 901                 if (fHasIndex && !CompareTo((uint8*)&indexValue, keyLength)) {
 902                         // They aren't equal? Let the operation decide what to do. Since
 903                         // we always start at the beginning of the index (or the correct
 904                         // position), only some needs to be stopped if the entry doesn't
 905                         // fit.
 906                         if (Term<QueryPolicy>::fOp == OP_LESS_THAN
 907                                 || Term<QueryPolicy>::fOp == OP_LESS_THAN_OR_EQUAL
 908                                 || (Term<QueryPolicy>::fOp == OP_EQUAL && !fIsPattern))
 909                                 return B_ENTRY_NOT_FOUND;
 910
 911                         continue;
 912                 }
 913
 914                 // TODO: check user permissions here - but which one?!
 915                 // we could filter out all those where we don't have
 916                 // read access... (we should check for every parent
 917                 // directory if the X_OK is allowed)
 918                 // Although it's quite expensive to open all parents,
 919                 // it's likely that the application that runs the
 920                 // query will do something similar (and we don't have
 921                 // to do it for root, either).
 922
 923                 // go up in the tree until a &&-operator is found, and check if the
 924                 // node matches with the rest of the expression - we don't have to
 925                 // check ||-operators for that
 926                 Term<QueryPolicy>* term = this;
 927                 status = MATCH_OK;
 928
 929                 if (!fHasIndex)
 930                         status = Match(entry, QueryPolicy::EntryGetNode(entry));
 931
 932                 while (term != NULL && status == MATCH_OK) {
 933                         Operator<QueryPolicy>* parent
 934                                 = (Operator<QueryPolicy>*)term->Parent();
 935                         if (parent == NULL)
 936                                 break;
 937
 938                         if (parent->Op() == OP_AND) {
 939                                 // choose the other child of the parent
 940                                 Term<QueryPolicy>* other = parent->Right();
 941                                 if (other == term)
 942                                         other = parent->Left();
 943
 944                                 if (other == NULL) {
 945                                         QUERY_FATAL("&&-operator has only one child... "
 946                                                 "(parent = %p)\n", parent);
 947                                         break;
 948                                 }
 949                                 status = other->Match(entry, QueryPolicy::EntryGetNode(entry));
 950                                 if (status < 0) {
 951                                         QUERY_REPORT_ERROR(status);
 952                                         status = NO_MATCH;
 953                                 }
 954                         }
 955                         term = (Term<QueryPolicy>*)parent;
 956                 }
 957
 958                 if (status == MATCH_OK) {
 959                         ssize_t nameLength = QueryPolicy::EntryGetName(entry,
 960                                 dirent->d_name,
 961                                 (const char*)dirent + bufferSize - dirent->d_name);
 962                         if (nameLength < 0)
 963                                 QUERY_RETURN_ERROR(nameLength);
 964
 965                         dirent->d_dev = QueryPolicy::ContextGetVolumeID(context);
 966                         dirent->d_ino = QueryPolicy::EntryGetNodeID(entry);
 967                         dirent->d_pdev = dirent->d_dev;
 968                         dirent->d_pino = QueryPolicy::EntryGetParentID(entry);
 969                         dirent->d_reclen = sizeof(struct dirent) + strlen(dirent->d_name);
 970                 }
 971
 972                 if (status == MATCH_OK)
 973                         return B_OK;
 974         }
 975         QUERY_RETURN_ERROR(B_ERROR);
 976 }
 977
 978
 979 template<typename QueryPolicy>
 980 bool
 981 Equation<QueryPolicy>::NeedsEntry()
 982 {
 983         return strcmp(fAttribute, "name") == 0;
 984 }
 985
 986
 987 //      #pragma mark -
 988
 989
 990 template<typename QueryPolicy>
 991 Operator<QueryPolicy>::Operator(Term<QueryPolicy>* left, int8 op,
 992         Term<QueryPolicy>* right)
 993         :
 994         Term<QueryPolicy>(op),
 995         fLeft(left),
 996         fRight(right)
 997 {
 998         if (left)
 999                 left->SetParent(this);
1000         if (right)
1001                 right->SetParent(this);
1002 }
1003
1004
1005 template<typename QueryPolicy>
1006 Operator<QueryPolicy>::~Operator()
1007 {
1008         delete fLeft;
1009         delete fRight;
1010 }
1011
1012
1013 template<typename QueryPolicy>
1014 status_t
1015 Operator<QueryPolicy>::Match(Entry* entry, Node* node, const char* attribute,
1016         int32 type, const uint8* key, size_t size)
1017 {
1018         if (Term<QueryPolicy>::fOp == OP_AND) {
1019                 status_t status = fLeft->Match(entry, node, attribute, type, key,
1020                         size);
1021                 if (status != MATCH_OK)
1022                         return status;
1023
1024                 return fRight->Match(entry, node, attribute, type, key, size);
1025         } else {
1026                 // choose the term with the better score for OP_OR
1027                 Term<QueryPolicy>* first;
1028                 Term<QueryPolicy>* second;
1029                 if (fRight->Score() > fLeft->Score()) {
1030                         first = fLeft;
1031                         second = fRight;
1032                 } else {
1033                         first = fRight;
1034                         second = fLeft;
1035                 }
1036
1037                 status_t status = first->Match(entry, node, attribute, type, key,
1038                         size);
1039                 if (status != NO_MATCH)
1040                         return status;
1041
1042                 return second->Match(entry, node, attribute, type, key, size);
1043         }
1044 }
1045
1046
1047 template<typename QueryPolicy>
1048 void
1049 Operator<QueryPolicy>::Complement()
1050 {
1051         if (Term<QueryPolicy>::fOp == OP_AND)
1052                 Term<QueryPolicy>::fOp = OP_OR;
1053         else
1054                 Term<QueryPolicy>::fOp = OP_AND;
1055
1056         fLeft->Complement();
1057         fRight->Complement();
1058 }
1059
1060
1061 template<typename QueryPolicy>
1062 void
1063 Operator<QueryPolicy>::CalculateScore(Index &index)
1064 {
1065         fLeft->CalculateScore(index);
1066         fRight->CalculateScore(index);
1067 }
1068
1069
1070 template<typename QueryPolicy>
1071 int32
1072 Operator<QueryPolicy>::Score() const
1073 {
1074         if (Term<QueryPolicy>::fOp == OP_AND) {
1075                 // return the one with the better score
1076                 if (fRight->Score() > fLeft->Score())
1077                         return fRight->Score();
1078
1079                 return fLeft->Score();
1080         }
1081
1082         // for OP_OR, be honest, and return the one with the worse score
1083         if (fRight->Score() < fLeft->Score())
1084                 return fRight->Score();
1085
1086         return fLeft->Score();
1087 }
1088
1089
1090 template<typename QueryPolicy>
1091 status_t
1092 Operator<QueryPolicy>::InitCheck()
1093 {
1094         if ((Term<QueryPolicy>::fOp != OP_AND && Term<QueryPolicy>::fOp != OP_OR)
1095                 || fLeft == NULL || fLeft->InitCheck() < B_OK
1096                 || fRight == NULL || fRight->InitCheck() < B_OK)
1097                 return B_ERROR;
1098
1099         return B_OK;
1100 }
1101
1102
1103 template<typename QueryPolicy>
1104 bool
1105 Operator<QueryPolicy>::NeedsEntry()
1106 {
1107         return ((fLeft && fLeft->NeedsEntry()) || (fRight && fRight->NeedsEntry()));
1108 }
1109
1110
1111 //      #pragma mark -
1112
1113 #ifdef DEBUG_QUERY
1114
1115 template<typename QueryPolicy>
1116 void
1117 Operator<QueryPolicy>::PrintToStream()
1118 {
1119         QUERY_D(__out("( "));
1120         if (fLeft != NULL)
1121                 fLeft->PrintToStream();
1122
1123         const char* op;
1124         switch (Term<QueryPolicy>::fOp) {
1125                 case OP_OR: op = "OR"; break;
1126                 case OP_AND: op = "AND"; break;
1127                 default: op = "?"; break;
1128         }
1129         QUERY_D(__out(" %s ", op));
1130
1131         if (fRight != NULL)
1132                 fRight->PrintToStream();
1133
1134         QUERY_D(__out(" )"));
1135 }
1136
1137
1138 template<typename QueryPolicy>
1139 void
1140 Equation<QueryPolicy>::PrintToStream()
1141 {
1142         const char* symbol = "???";
1143         switch (Term<QueryPolicy>::fOp) {
1144                 case OP_EQUAL: symbol = "=="; break;
1145                 case OP_UNEQUAL: symbol = "!="; break;
1146                 case OP_GREATER_THAN: symbol = ">"; break;
1147                 case OP_GREATER_THAN_OR_EQUAL: symbol = ">="; break;
1148                 case OP_LESS_THAN: symbol = "<"; break;
1149                 case OP_LESS_THAN_OR_EQUAL: symbol = "<="; break;
1150         }
1151         QUERY_D(__out("[\"%s\" %s \"%s\"]", fAttribute, symbol, fString));
1152 }
1153
1154 #endif  // DEBUG_QUERY
1155
1156 //      #pragma mark -
1157
1158
1159 template<typename QueryPolicy>
1160 Expression<QueryPolicy>::Expression(char* expr)
1161 {
1162         if (expr == NULL)
1163                 return;
1164
1165         fTerm = ParseOr(&expr);
1166         if (fTerm != NULL && fTerm->InitCheck() < B_OK) {
1167                 QUERY_FATAL("Corrupt tree in expression!\n");
1168                 delete fTerm;
1169                 fTerm = NULL;
1170         }
1171         QUERY_D(if (fTerm != NULL) {
1172                 fTerm->PrintToStream();
1173                 QUERY_D(__out("\n"));
1174                 if (*expr != '\0')
1175                         PRINT(("Unexpected end of string: \"%s\"!\n", expr));
1176         });
1177         fPosition = expr;
1178 }
1179
1180
1181 template<typename QueryPolicy>
1182 Expression<QueryPolicy>::~Expression()
1183 {
1184         delete fTerm;
1185 }
1186
1187
1188 template<typename QueryPolicy>
1189 Term<QueryPolicy>*
1190 Expression<QueryPolicy>::ParseEquation(char** expr)
1191 {
1192         skipWhitespace(expr);
1193
1194         bool _not = false;
1195         if (**expr == '!') {
1196                 skipWhitespace(expr, 1);
1197                 if (**expr != '(')
1198                         return NULL;
1199
1200                 _not = true;
1201         }
1202
1203         if (**expr == ')') {
1204                 // shouldn't be handled here
1205                 return NULL;
1206         } else if (**expr == '(') {
1207                 skipWhitespace(expr, 1);
1208
1209                 Term<QueryPolicy>* term = ParseOr(expr);
1210
1211                 skipWhitespace(expr);
1212
1213                 if (**expr != ')') {
1214                         delete term;
1215                         return NULL;
1216                 }
1217
1218                 // If the term is negated, we just complement the tree, to get
1219                 // rid of the not, a.k.a. DeMorgan's Law.
1220                 if (_not)
1221                         term->Complement();
1222
1223                 skipWhitespace(expr, 1);
1224
1225                 return term;
1226         }
1227
1228         Equation<QueryPolicy>* equation
1229                 = new(std::nothrow) Equation<QueryPolicy>(expr);
1230         if (equation == NULL || equation->InitCheck() < B_OK) {
1231                 delete equation;
1232                 return NULL;
1233         }
1234         return equation;
1235 }
1236
1237
1238 template<typename QueryPolicy>
1239 Term<QueryPolicy>*
1240 Expression<QueryPolicy>::ParseAnd(char** expr)
1241 {
1242         Term<QueryPolicy>* left = ParseEquation(expr);
1243         if (left == NULL)
1244                 return NULL;
1245
1246         while (IsOperator(expr, '&')) {
1247                 Term<QueryPolicy>* right = ParseAnd(expr);
1248                 Term<QueryPolicy>* newParent = NULL;
1249
1250                 if (right == NULL
1251                         || (newParent = new(std::nothrow) Operator<QueryPolicy>(left,
1252                                 OP_AND, right)) == NULL) {
1253                         delete left;
1254                         delete right;
1255
1256                         return NULL;
1257                 }
1258                 left = newParent;
1259         }
1260
1261         return left;
1262 }
1263
1264
1265 template<typename QueryPolicy>
1266 Term<QueryPolicy>*
1267 Expression<QueryPolicy>::ParseOr(char** expr)
1268 {
1269         Term<QueryPolicy>* left = ParseAnd(expr);
1270         if (left == NULL)
1271                 return NULL;
1272
1273         while (IsOperator(expr, '|')) {
1274                 Term<QueryPolicy>* right = ParseAnd(expr);
1275                 Term<QueryPolicy>* newParent = NULL;
1276
1277                 if (right == NULL
1278                         || (newParent = new(std::nothrow) Operator<QueryPolicy>(left, OP_OR,
1279                                 right)) == NULL) {
1280                         delete left;
1281                         delete right;
1282
1283                         return NULL;
1284                 }
1285                 left = newParent;
1286         }
1287
1288         return left;
1289 }
1290
1291
1292 template<typename QueryPolicy>
1293 bool
1294 Expression<QueryPolicy>::IsOperator(char** expr, char op)
1295 {
1296         char* string = *expr;
1297
1298         if (*string == op && *(string + 1) == op) {
1299                 *expr += 2;
1300                 return true;
1301         }
1302         return false;
1303 }
1304
1305
1306 template<typename QueryPolicy>
1307 status_t
1308 Expression<QueryPolicy>::InitCheck()
1309 {
1310         if (fTerm == NULL)
1311                 return B_BAD_VALUE;
1312
1313         return B_OK;
1314 }
1315
1316
1317 //      #pragma mark -
1318
1319
1320 template<typename QueryPolicy>
1321 Query<QueryPolicy>::Query(Context* context, Expression<QueryPolicy>* expression,
1322         uint32 flags, port_id port, uint32 token)
1323         :
1324         fContext(context),
1325         fExpression(expression),
1326         fCurrent(NULL),
1327         fIterator(NULL),
1328         fIndex(context),
1329         fFlags(flags),
1330         fPort(port),
1331         fToken(token),
1332         fNeedsEntry(false)
1333 {
1334         // If the expression has a valid root pointer, the whole tree has
1335         // already passed the sanity check, so that we don't have to check
1336         // every pointer
1337         if (context == NULL || expression == NULL || expression->Root() == NULL)
1338                 return;
1339
1340         // create index on the stack and delete it afterwards
1341         fExpression->Root()->CalculateScore(fIndex);
1342         QueryPolicy::IndexUnset(fIndex);
1343
1344         fNeedsEntry = fExpression->Root()->NeedsEntry();
1345
1346         Rewind();
1347 }
1348
1349
1350 template<typename QueryPolicy>
1351 Query<QueryPolicy>::~Query()
1352 {
1353         delete fExpression;
1354 }
1355
1356
1357 template<typename QueryPolicy>
1358 /*static*/ status_t
1359 Query<QueryPolicy>::Create(Context* context, const char* queryString,
1360         uint32 flags, port_id port, uint32 token, Query<QueryPolicy>*& _query)
1361 {
1362         Expression<QueryPolicy>* expression
1363                 = new(std::nothrow) Expression<QueryPolicy>((char*)queryString);
1364         if (expression == NULL)
1365                 QUERY_RETURN_ERROR(B_NO_MEMORY);
1366
1367         if (expression->InitCheck() != B_OK) {
1368                 QUERY_INFORM("Could not parse query \"%s\", stopped at: \"%s\"\n",
1369                         queryString, expression->Position());
1370
1371                 delete expression;
1372                 QUERY_RETURN_ERROR(B_BAD_VALUE);
1373         }
1374
1375         Query<QueryPolicy>* query = new(std::nothrow) Query<QueryPolicy>(context,
1376                 expression, flags, port, token);
1377         if (query == NULL) {
1378                 delete expression;
1379                 QUERY_RETURN_ERROR(B_NO_MEMORY);
1380         }
1381
1382         _query = query;
1383         return B_OK;
1384 }
1385
1386
1387 template<typename QueryPolicy>
1388 status_t
1389 Query<QueryPolicy>::Rewind()
1390 {
1391         // free previous stuff
1392
1393         fStack.MakeEmpty();
1394
1395         QueryPolicy::IndexIteratorDelete(fIterator);
1396         fIterator = NULL;
1397         fCurrent = NULL;
1398
1399         // put the whole expression on the stack
1400
1401         Stack<Term<QueryPolicy>*> stack;
1402         stack.Push(fExpression->Root());
1403
1404         Term<QueryPolicy>* term;
1405         while (stack.Pop(&term)) {
1406                 if (term->Op() < OP_EQUATION) {
1407                         Operator<QueryPolicy>* op = (Operator<QueryPolicy>*)term;
1408
1409                         if (op->Op() == OP_OR) {
1410                                 stack.Push(op->Left());
1411                                 stack.Push(op->Right());
1412                         } else {
1413                                 // For OP_AND, we can use the scoring system to decide which
1414                                 // path to add
1415                                 if (op->Right()->Score() > op->Left()->Score())
1416                                         stack.Push(op->Right());
1417                                 else
1418                                         stack.Push(op->Left());
1419                         }
1420                 } else if (term->Op() == OP_EQUATION
1421                         || fStack.Push((Equation<QueryPolicy>*)term) != B_OK)
1422                         QUERY_FATAL("Unknown term on stack or stack error\n");
1423         }
1424
1425         return B_OK;
1426 }
1427
1428
1429 template<typename QueryPolicy>
1430 status_t
1431 Query<QueryPolicy>::GetNextEntry(struct dirent* dirent, size_t size)
1432 {
1433         if (fIterator != NULL)
1434                 QueryPolicy::IndexIteratorResume(fIterator);
1435
1436         status_t error = _GetNextEntry(dirent, size);
1437
1438         if (fIterator != NULL)
1439                 QueryPolicy::IndexIteratorSuspend(fIterator);
1440
1441         return error;
1442 }
1443
1444
1445 template<typename QueryPolicy>
1446 void
1447 Query<QueryPolicy>::LiveUpdate(Entry* entry, Node* node, const char* attribute,
1448         int32 type, const uint8* oldKey, size_t oldLength, const uint8* newKey,
1449         size_t newLength)
1450 {
1451         if (fPort < 0 || fExpression == NULL || attribute == NULL)
1452                 return;
1453
1454         // TODO: check if the attribute is part of the query at all...
1455
1456         // If no entry has been supplied, but the we need one for the evaluation
1457         // (i.e. the "name" attribute is used), we invoke ourselves for all entries
1458         // referring to the given node.
1459         if (entry == NULL && fNeedsEntry) {
1460                 entry = QueryPolicy::NodeGetFirstReferrer(node);
1461                 while (entry) {
1462                         LiveUpdate(entry, node, attribute, type, oldKey, oldLength, newKey,
1463                                 newLength);
1464                         entry = QueryPolicy::NodeGetNextReferrer(node, entry);
1465                 }
1466                 return;
1467         }
1468
1469         status_t oldStatus = fExpression->Root()->Match(entry, node, attribute,
1470                 type, oldKey, oldLength);
1471         status_t newStatus = fExpression->Root()->Match(entry, node, attribute,
1472                 type, newKey, newLength);
1473
1474         bool entryCreated = false;
1475         bool stillInQuery = false;
1476
1477         if (oldStatus != MATCH_OK) {
1478                 if (newStatus != MATCH_OK) {
1479                         // nothing has changed
1480                         return;
1481                 }
1482                 entryCreated = true;
1483         } else if (newStatus != MATCH_OK) {
1484                 // entry got removed
1485                 entryCreated = false;
1486         } else if ((fFlags & B_ATTR_CHANGE_NOTIFICATION) != 0) {
1487                 // The entry stays in the query
1488                 stillInQuery = true;
1489         } else
1490                 return;
1491
1492         // notify query listeners
1493         status_t (*notify)(port_id, int32, dev_t, ino_t, const char*, ino_t);
1494
1495         if (stillInQuery)
1496                 notify = notify_query_attr_changed;
1497         else if (entryCreated)
1498                 notify = notify_query_entry_created;
1499         else
1500                 notify = notify_query_entry_removed;
1501
1502         if (entry != NULL) {
1503                 _SendEntryNotification(entry, notify);
1504         } else {
1505                 entry = QueryPolicy::NodeGetFirstReferrer(node);
1506                 while (entry) {
1507                         _SendEntryNotification(entry, notify);
1508                         entry = QueryPolicy::NodeGetNextReferrer(node, entry);
1509                 }
1510         }
1511 }
1512
1513
1514 template<typename QueryPolicy>
1515 void
1516 Query<QueryPolicy>::LiveUpdateRenameMove(Entry* entry, Node* node,
1517         ino_t oldDirectoryID, const char* oldName, size_t oldLength,
1518         ino_t newDirectoryID, const char* newName, size_t newLength)
1519 {
1520         if (fPort < 0 || fExpression == NULL)
1521                 return;
1522
1523         // TODO: check if the attribute is part of the query at all...
1524
1525         status_t oldStatus = fExpression->Root()->Match(entry, node, "name",
1526                 B_STRING_TYPE, (const uint8*)oldName, oldLength);
1527         status_t newStatus = fExpression->Root()->Match(entry, node, "name",
1528                 B_STRING_TYPE, (const uint8*)newName, newLength);
1529
1530         if (oldStatus != MATCH_OK || oldStatus != newStatus)
1531                 return;
1532
1533         // The entry stays in the query, notify query listeners about the rename
1534         // or move
1535
1536         // We send a notification for the given entry, if any, or otherwise for
1537         // all entries referring to the node;
1538         if (entry != NULL) {
1539                 _SendEntryNotification(entry, notify_query_entry_removed);
1540                 _SendEntryNotification(entry, notify_query_entry_created);
1541         } else {
1542                 entry = QueryPolicy::NodeGetFirstReferrer(node);
1543                 while (entry) {
1544                         _SendEntryNotification(entry, notify_query_entry_removed);
1545                         _SendEntryNotification(entry, notify_query_entry_created);
1546                         entry = QueryPolicy::NodeGetNextReferrer(node, entry);
1547                 }
1548         }
1549 }
1550
1551
1552 template<typename QueryPolicy>
1553 status_t
1554 Query<QueryPolicy>::_GetNextEntry(struct dirent* dirent, size_t size)
1555 {
1556         // If we don't have an equation to use yet/anymore, get a new one
1557         // from the stack
1558         while (true) {
1559                 if (fIterator == NULL) {
1560                         if (!fStack.Pop(&fCurrent)
1561                                 || fCurrent == NULL)
1562                                 return B_ENTRY_NOT_FOUND;
1563
1564                         status_t status = fCurrent->PrepareQuery(fContext, fIndex,
1565                                 &fIterator, fFlags & B_QUERY_NON_INDEXED);
1566                         if (status == B_ENTRY_NOT_FOUND) {
1567                                 // try next equation
1568                                 continue;
1569                         }
1570
1571                         if (status != B_OK)
1572                                 return status;
1573                 }
1574                 if (fCurrent == NULL)
1575                         QUERY_RETURN_ERROR(B_ERROR);
1576
1577                 status_t status = fCurrent->GetNextMatching(fContext, fIterator, dirent,
1578                         size);
1579                 if (status != B_OK) {
1580                         QueryPolicy::IndexIteratorDelete(fIterator);
1581                         fIterator = NULL;
1582                         fCurrent = NULL;
1583                 } else {
1584                         // only return if we have another entry
1585                         return B_OK;
1586                 }
1587         }
1588 }
1589
1590
1591 template<typename QueryPolicy>
1592 void
1593 Query<QueryPolicy>::_SendEntryNotification(Entry* entry,
1594         status_t (*notify)(port_id, int32, dev_t, ino_t, const char*, ino_t))
1595 {
1596         char nameBuffer[QueryPolicy::kMaxFileNameLength];
1597         const char* name = QueryPolicy::EntryGetNameNoCopy(entry, nameBuffer,
1598                 sizeof(nameBuffer));
1599         if (name != NULL) {
1600                 notify(fPort, fToken, QueryPolicy::ContextGetVolumeID(fContext),
1601                         QueryPolicy::EntryGetParentID(entry), name,
1602                         QueryPolicy::EntryGetNodeID(entry));
1603         }
1604 }
1605
1606
1607 }       // namespace QueryParser
1608
1609
1610 #endif  // _FILE_SYSTEMS_QUERY_PARSER_H