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