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