1/* 2 * Copyright (c) 2006 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23#include "QEQuery.h" 24#include "kext_tools_util.h" 25 26/******************************************************************************* 27* The internal query engine object definition. 28*******************************************************************************/ 29struct __QEQuery { 30 31 /* queryRoot: the outermost query element, always an OR group 32 */ 33 CFMutableDictionaryRef queryRoot; 34 35 /* queryStack, queryStackTop: a lifo stack of query elements representing 36 * open groups (the root is always considered open for appending). 37 */ 38 CFMutableArrayRef queryStack; 39 CFMutableDictionaryRef queryStackTop; 40 41 /* The number of explicit OR groups that are open. 42 */ 43 uint32_t nestingLevel; 44 45 /* Is an AND or OR operator pending? 46 */ 47 Boolean logicOpActive; 48 49 /* End evaluation as soon as truth value known? (on by default) 50 */ 51 Boolean shortCircuitEval; 52 53 /* The last error to happen with this query. 54 */ 55 QEQueryError lastError; 56 57 /* Client-defined synonyms to their underlying operator equivalents. 58 */ 59 CFMutableDictionaryRef synonyms; 60 61 /* Lookup operators by default token to client-defined token (which 62 * may be the default). 63 */ 64 CFMutableDictionaryRef operators; 65 66 /* parse, eval callbacks keyed by client-registered keyword. 67 */ 68 CFMutableDictionaryRef parseCallbacks; 69 CFMutableDictionaryRef evaluationCallbacks; 70 71 /* Client-defined data passed to all callbacks. 72 */ 73 void * userData; 74}; 75 76/******************************************************************************* 77* Internal query element keys for the basic operators and such. 78******************************************************************************** 79* IMPORTANT NOTE ABOUT GROUPS 80* "Or" groups are always explicit, except for the query root. "And" groups are 81* always implicit, and are created as soon as an "and" operator is seen. The 82* query engine promotes the element preceding the "and" into the new "and" 83* group. When an "or" group is closed, several checks are made to close implicit 84* "and" groups as well as any trivial groups of one element. 85* See QEQueryEndGroup() and particularly _QEQueryPopGroupAndCoalesce() for 86* the gory details. 87*******************************************************************************/ 88#define kQEQueryKeyPredicate CFSTR("_QEQueryPredicate") 89#define kQEQueryKeyArguments CFSTR("_QEQueryArguments") 90 91#define kQEQueryKeyNegated CFSTR("_QEQueryNegated") 92 93#define kQEQueryPredicateAnd CFSTR("_QEQueryAndGroup") 94#define kQEQueryPredicateOr CFSTR("_QEQueryOrGroup") 95 96#define kMsgStringConversionError "string conversion error" 97 98/******************************************************************************* 99* Internal function prototypes. 100*******************************************************************************/ 101Boolean _QEQueryStartGroup( 102 QEQueryRef query, 103 Boolean andFlag, 104 Boolean negated); 105CFMutableDictionaryRef _QEQueryCreateGroup(Boolean andFlag); 106CF_RETURNS_RETAINED CFMutableDictionaryRef _QEQueryYankElement(QEQueryRef query); 107Boolean _QEQueryStackTopIsAndGroup(QEQueryRef query); 108Boolean _QEQueryStackTopIsOrGroup(QEQueryRef query); 109Boolean _QEQueryStackTopHasCount(QEQueryRef query, CFIndex count); 110Boolean _QEQueryPushGroup(QEQueryRef query, Boolean negated, Boolean andFlag); 111Boolean _QEQueryPopGroup(QEQueryRef query); 112Boolean _QEQueryPopGroupAndCoalesce( 113 QEQueryRef query, 114 Boolean onlyIfCanCoalesce); 115 116CFStringRef _QEQueryOperatorForToken( 117 QEQueryRef query, 118 CFStringRef token); 119CF_RETURNS_RETAINED CFStringRef _QEPredicateForString( 120 QEQueryRef query, 121 char * string); 122QEQueryParseCallback _QEQueryParseCallbackForPredicate( 123 QEQueryRef query, 124 CFStringRef predicate); 125QEQueryEvaluationCallback _QEQueryEvaluationCallbackForPredicate( 126 QEQueryRef query, 127 CFStringRef predicate); 128 129Boolean _QEQueryElementIsNegated(CFDictionaryRef element); 130void _QEQueryElementNegate(CFMutableDictionaryRef element); 131 132#pragma mark Creation/Setup/Destruction 133 134/******************************************************************************* 135* 136*******************************************************************************/ 137QEQueryRef 138QEQueryCreate(void * userData) 139{ 140 struct __QEQuery * result = NULL; // returned 141 Boolean ok = false; 142 143 result = (QEQueryRef)malloc(sizeof(struct __QEQuery)); 144 if (!result) { 145 goto finish; 146 } 147 148 bzero(result, sizeof(struct __QEQuery)); 149 150 result->userData = userData; 151 152 result->queryRoot = _QEQueryCreateGroup(false /* andGroup */); 153 if (!result->queryRoot) { 154 goto finish; 155 } 156 157 result->queryStack = CFArrayCreateMutable(kCFAllocatorDefault, 158 0, &kCFTypeArrayCallBacks); 159 if (!result->queryStack) { 160 goto finish; 161 } 162 163 result->parseCallbacks = CFDictionaryCreateMutable(kCFAllocatorDefault, 164 0 /* no limit */, &kCFTypeDictionaryKeyCallBacks, 165 &kCFTypeDictionaryValueCallBacks); 166 if (!result->parseCallbacks) { 167 goto finish; 168 } 169 170 result->operators = CFDictionaryCreateMutable(kCFAllocatorDefault, 171 0 /* no limit */, &kCFTypeDictionaryKeyCallBacks, 172 &kCFTypeDictionaryValueCallBacks); 173 if (!result->operators) { 174 goto finish; 175 } 176 177 result->synonyms = CFDictionaryCreateMutable(kCFAllocatorDefault, 178 0 /* no limit */, &kCFTypeDictionaryKeyCallBacks, 179 &kCFTypeDictionaryValueCallBacks); 180 if (!result->synonyms) { 181 goto finish; 182 } 183 184 result->evaluationCallbacks = CFDictionaryCreateMutable(kCFAllocatorDefault, 185 0 /* no limit */, &kCFTypeDictionaryKeyCallBacks, 186 &kCFTypeDictionaryValueCallBacks); 187 if (!result->evaluationCallbacks) { 188 goto finish; 189 } 190 191 CFArrayAppendValue(result->queryStack, result->queryRoot); 192 result->queryStackTop = result->queryRoot; 193 194 result->nestingLevel = 0; 195 result->logicOpActive = false; 196 result->shortCircuitEval = true; 197 198 QEQuerySetOperators(result, NULL, NULL, NULL, NULL, NULL); 199 200 ok = true; 201 202finish: 203 if (!ok && result) { 204 QEQueryFree(result); 205 result = NULL; 206 } 207 return result; 208} 209 210/******************************************************************************* 211* 212*******************************************************************************/ 213void 214QEQueryFree(QEQueryRef query) 215{ 216 if (query->queryRoot) CFRelease(query->queryRoot); 217 if (query->queryStack) CFRelease(query->queryStack); 218 if (query->operators) CFRelease(query->operators); 219 if (query->parseCallbacks) CFRelease(query->parseCallbacks); 220 if (query->evaluationCallbacks) CFRelease(query->evaluationCallbacks); 221 if (query->synonyms) CFRelease(query->synonyms); 222 free(query); 223 return; 224} 225 226/******************************************************************************* 227* 228*******************************************************************************/ 229void 230QEQueryEmptyParseDictionaries(QEQueryRef query) 231{ 232 CFDictionaryRemoveAllValues(query->parseCallbacks); 233 CFDictionaryRemoveAllValues(query->evaluationCallbacks); 234 CFDictionaryRemoveAllValues(query->synonyms); 235 return; 236} 237 238/******************************************************************************* 239* QEQuerySetOperators() -- all operators must have a definition, so if NULL is 240* passed for any, the basic token defined in the header file is assigned. 241*******************************************************************************/ 242void 243QEQuerySetOperators(QEQueryRef query, 244 CFStringRef andPredicate, 245 CFStringRef orPredicate, 246 CFStringRef notPredicate, 247 CFStringRef groupStartPredicate, 248 CFStringRef groupEndPredicate) 249{ 250 CFDictionarySetValue(query->operators, CFSTR(kQEQueryTokenAnd), 251 andPredicate ? andPredicate : CFSTR(kQEQueryTokenAnd)); 252 CFDictionarySetValue(query->operators, CFSTR(kQEQueryTokenOr), 253 orPredicate ? orPredicate : CFSTR(kQEQueryTokenOr)); 254 CFDictionarySetValue(query->operators, CFSTR(kQEQueryTokenNot), 255 notPredicate ? notPredicate : CFSTR(kQEQueryTokenNot)); 256 CFDictionarySetValue(query->operators, CFSTR(kQEQueryTokenGroupStart), 257 groupStartPredicate ? groupStartPredicate : CFSTR(kQEQueryTokenGroupStart)); 258 CFDictionarySetValue(query->operators, CFSTR(kQEQueryTokenGroupEnd), 259 groupEndPredicate ? groupEndPredicate : CFSTR(kQEQueryTokenGroupEnd)); 260 return; 261} 262 263/******************************************************************************* 264* 265*******************************************************************************/ 266void 267QEQuerySetParseCallbackForPredicate( 268 QEQueryRef query, 269 CFStringRef predicate, 270 QEQueryParseCallback parseCallback) 271{ 272 CFDataRef pCallback = NULL; 273 274 if (parseCallback) { 275 pCallback = CFDataCreate(kCFAllocatorDefault, 276 (void *)&parseCallback, sizeof(QEQueryParseCallback)); 277 if (!pCallback) { 278 goto finish; 279 } 280 CFDictionarySetValue(query->parseCallbacks, predicate, pCallback); 281 } else { 282 CFDictionaryRemoveValue(query->parseCallbacks, predicate); 283 } 284 285finish: 286 if (pCallback) CFRelease(pCallback); 287 return; 288} 289 290/******************************************************************************* 291* 292*******************************************************************************/ 293void 294QEQuerySetEvaluationCallbackForPredicate( 295 QEQueryRef query, 296 CFStringRef predicate, 297 QEQueryEvaluationCallback evaluationCallback) 298{ 299 CFDataRef eCallback = NULL; 300 301 if (evaluationCallback) { 302 eCallback = CFDataCreate(kCFAllocatorDefault, 303 (void *)&evaluationCallback, sizeof(QEQueryEvaluationCallback)); 304 if (!eCallback) { 305 goto finish; 306 } 307 CFDictionarySetValue(query->evaluationCallbacks, predicate, eCallback); 308 } else { 309 CFDictionaryRemoveValue(query->evaluationCallbacks, predicate); 310 } 311 312finish: 313 if (eCallback) CFRelease(eCallback); 314 return; 315} 316 317/******************************************************************************* 318* 319*******************************************************************************/ 320void 321QEQuerySetSynonymForPredicate( 322 QEQueryRef query, 323 CFStringRef synonym, 324 CFStringRef predicate) 325{ 326 if (predicate) { 327 CFDictionarySetValue(query->synonyms, synonym, predicate); 328 } else { 329 CFDictionaryRemoveValue(query->synonyms, synonym); 330 } 331 return; 332} 333 334/******************************************************************************* 335* 336*******************************************************************************/ 337Boolean 338QEQueryIsComplete(QEQueryRef query) 339{ 340 if (!query->nestingLevel && 341 !query->logicOpActive && 342 query->lastError == kQEQueryErrorNone) { 343 344 return true; 345 } 346 return false; 347} 348 349/******************************************************************************* 350* 351*******************************************************************************/ 352QEQueryError 353QEQueryLastError(QEQueryRef query) 354{ 355 return query->lastError; 356} 357 358#pragma mark Evaluation 359 360/******************************************************************************* 361* 362*******************************************************************************/ 363void 364QEQuerySetShortCircuits( 365 QEQueryRef query, 366 Boolean flag) 367{ 368 query->shortCircuitEval = flag; 369} 370 371/******************************************************************************* 372* 373*******************************************************************************/ 374Boolean 375QEQueryGetShortCircuits(QEQueryRef query) 376{ 377 return query->shortCircuitEval; 378} 379 380/******************************************************************************* 381* 382*******************************************************************************/ 383Boolean 384_QEQueryElementEvaluate( 385 QEQueryRef query, 386 CFDictionaryRef element, 387 void * object) 388{ 389 Boolean result = false; 390 CFStringRef predicate = NULL; 391 CFArrayRef elements = NULL; 392 CFIndex count, i; 393 394 predicate = CFDictionaryGetValue(element, kQEQueryKeyPredicate); 395 396 397 if (CFEqual(predicate, kQEQueryPredicateAnd)) { 398 elements = QEQueryElementGetArguments(element); 399 400 /* Empty groups can't normally be created, except for the 401 * root query, but empty groups are trivially true; basically, 402 * an empty group is true. 403 */ 404 count = CFArrayGetCount(elements); if (!count) { 405 result = true; 406 } 407 408 /* If any element in an AND group is false, stop evaluating the 409 * group and return false, else return true. 410 */ 411 for (i = 0; i < count; i++) { 412 CFDictionaryRef thisElement = CFArrayGetValueAtIndex(elements, i); 413 if (!_QEQueryElementEvaluate(query, thisElement, object)) { 414 if (query->shortCircuitEval) { 415 goto finish; 416 } 417 } 418 } 419 result = true; 420 } else if (CFEqual(predicate, kQEQueryPredicateOr)) { 421 elements = QEQueryElementGetArguments(element); 422 423 /* Empty groups can't normally be created, except for the 424 * root query, but empty groups are trivially true; basically, 425 * an empty group is true. 426 */ 427 count = CFArrayGetCount(elements); 428 if (!count) { 429 result = true; 430 } 431 432 /* If any element in an OR group is true, stop evaluating the 433 * group and return true, else return false. 434 */ 435 for (i = 0; i < count; i++) { 436 CFDictionaryRef thisElement = CFArrayGetValueAtIndex(elements, i); 437 if (_QEQueryElementEvaluate(query, thisElement, object)) { 438 result = true; 439 if (query->shortCircuitEval) { 440 goto finish; 441 } 442 } 443 } 444 } else { 445 446 /* Look for a client callback. 447 */ 448 QEQueryEvaluationCallback evalCallback = 449 _QEQueryEvaluationCallbackForPredicate(query, predicate); 450 if (evalCallback) { 451 result = evalCallback(element, object, query->userData, 452 &query->lastError); 453 } else { 454 query->lastError = kQEQueryErrorNoEvaluationCallback; 455 } 456 } 457 458finish: 459 460 /* Flip the result if the element is negated. 461 */ 462 if (_QEQueryElementIsNegated(element)) { 463 result = !result; 464 } 465 466 /* Set the result to false upon any error. 467 */ 468 if (query->lastError != kQEQueryErrorNone) { 469 result = false; 470 } 471 return result; 472} 473 474/******************************************************************************* 475* 476*******************************************************************************/ 477Boolean 478QEQueryEvaluate( 479 QEQueryRef query, 480 void * object) 481{ 482 Boolean result = false; 483 if (!QEQueryIsComplete(query) || query->lastError != kQEQueryErrorNone) { 484 goto finish; 485 } 486 result = _QEQueryElementEvaluate(query, query->queryRoot, object); 487finish: 488 return result; 489} 490 491#pragma mark Command-Line Argument Processing 492 493/******************************************************************************* 494* 495*******************************************************************************/ 496Boolean 497QEQueryAppendElementFromArgs( 498 QEQueryRef query, 499 int argc, 500 char * const argv[], 501 uint32_t * num_used) 502{ 503 Boolean result = false; 504 uint32_t index = 0; 505 Boolean negated = false; 506 CFMutableDictionaryRef element = NULL; // must release 507 CFStringRef predicate = NULL; // must release 508 509 if (!argv[index]) { 510 goto finish; 511 } 512 513 predicate = _QEPredicateForString(query, argv[index]); 514 515 if (CFEqual(predicate, 516 CFDictionaryGetValue(query->operators, CFSTR(kQEQueryTokenNot)))) { 517 518 index++; 519 negated = true; 520 521 if (!argv[index]) { 522 query->lastError = kQEQueryErrorSyntax; 523 goto finish; 524 } 525 526 } 527 528 if (predicate) CFRelease(predicate); 529 predicate = _QEPredicateForString(query, argv[index]); 530 531 /* This is not an 'else'! Not applies to most of the following. 532 */ 533 if (CFEqual(predicate, 534 CFDictionaryGetValue(query->operators, CFSTR(kQEQueryTokenAnd)))) { 535 536 if (negated) { 537 query->lastError = kQEQueryErrorSyntax; 538 goto finish; 539 } 540 if (!QEQueryAppendAndOperator(query)) { 541 goto finish; 542 } 543 index++; 544 } else if (CFEqual(predicate, 545 CFDictionaryGetValue(query->operators, CFSTR(kQEQueryTokenOr)))) { 546 547 if (negated) { 548 query->lastError = kQEQueryErrorSyntax; 549 goto finish; 550 } 551 if (!QEQueryAppendOrOperator(query)) { 552 goto finish; 553 } 554 index++; 555 } else if (CFEqual(predicate, 556 CFDictionaryGetValue(query->operators, CFSTR(kQEQueryTokenGroupStart)))) { 557 558 if (!_QEQueryStartGroup(query, false /* 'and' group */, negated)) { 559 // called function sets query->lastError 560 goto finish; 561 } 562 index++; 563 } else if (CFEqual(predicate, 564 CFDictionaryGetValue(query->operators, CFSTR(kQEQueryTokenGroupEnd)))) { 565 566 if (!QEQueryEndGroup(query)) { 567 // called function sets query->lastError 568 goto finish; 569 } 570 index++; 571 } else { 572 QEQueryParseCallback parseCallback = NULL; 573 uint32_t callbackNumUsed = 0; 574 575 element = QEQueryCreateElement(query, predicate, NULL, negated); 576 if (!element) { 577 // called function sets query->lastError 578 goto finish; 579 } 580 581 parseCallback = _QEQueryParseCallbackForPredicate(query, predicate); 582 if (!parseCallback) { 583 query->lastError = kQEQueryErrorNoParseCallback; 584 goto finish; 585 } 586 587 /* Base args off index in case we consumed a NOT. 588 */ 589 if (!parseCallback(element, argc - index, &argv[index], 590 &callbackNumUsed, query->userData, &query->lastError)) { 591 592 // user callback sets query->lastError 593 goto finish; 594 } 595 596 index += callbackNumUsed; 597 598 if (!QEQueryAppendElement(query, element)) { 599 // called function sets query->lastError 600 goto finish; 601 } 602 } 603 604 result = true; 605 606finish: 607 if (num_used) { 608 if (result) { 609 *num_used += index; 610 } else if (negated) { 611 *num_used += 1; 612 } 613 } 614 if (element) CFRelease(element); 615 if (predicate) CFRelease(predicate); 616 return result; 617} 618 619#pragma mark Hand-Building Queries 620 621/******************************************************************************* 622* 623*******************************************************************************/ 624CFMutableDictionaryRef 625QEQueryCreateElement( 626 QEQueryRef query, 627 CFStringRef predicate, 628 CFArrayRef arguments, 629 Boolean negated) 630{ 631 CFMutableDictionaryRef result = NULL; 632 CFStringRef synonym = NULL; // do not release (or retain!) 633 634 if (!predicate) { 635 goto finish; 636 } 637 638 result = CFDictionaryCreateMutable(kCFAllocatorDefault, 639 0 /* no limit */, &kCFTypeDictionaryKeyCallBacks, 640 &kCFTypeDictionaryValueCallBacks); 641 if (!result) { 642 query->lastError = kQEQueryErrorNoMemory; 643 goto finish; 644 } 645 646 synonym = CFDictionaryGetValue(query->synonyms, predicate); 647 if (synonym) { 648 predicate = synonym; 649 } 650 651 QEQueryElementSetPredicate(result, predicate); 652 653 if (arguments) { 654 QEQueryElementSetArgumentsArray(result, arguments); 655 } 656 657 if (negated) { 658 CFDictionarySetValue(result, kQEQueryKeyNegated, 659 kCFBooleanTrue); 660 } 661 662finish: 663 return result; 664} 665 666/******************************************************************************* 667* 668*******************************************************************************/ 669Boolean 670QEQueryAppendElement( 671 QEQueryRef query, 672 CFMutableDictionaryRef element) 673{ 674 Boolean result = false; 675 CFMutableArrayRef elements = NULL; 676 677 /* If there is no logic operator active, and the current group has 678 * at least one item, treat this as being ANDed to the current group. 679 */ 680 if (!query->logicOpActive && !_QEQueryStackTopHasCount(query, 0)) { 681 if (!QEQueryAppendAndOperator(query)) { 682 // called function sets query->lastError 683 goto finish; 684 } 685 } 686 687 elements = (CFMutableArrayRef)CFDictionaryGetValue( 688 query->queryStackTop, kQEQueryKeyArguments); 689 690 CFArrayAppendValue(elements, (const void *)element); 691 query->logicOpActive = false; 692 693 result = true; 694finish: 695 return result; 696} 697 698/******************************************************************************* 699* 700*******************************************************************************/ 701Boolean 702QEQueryAppendAndOperator(QEQueryRef query) 703{ 704 Boolean result = false; 705 706 if (query->logicOpActive) { 707 query->lastError = kQEQueryErrorSyntax; 708 goto finish; 709 } 710 711 query->logicOpActive = true; 712 713 if (_QEQueryStackTopIsOrGroup(query)) { 714 if (!_QEQueryStartGroup(query, true /* 'and' group */, 715 false /* negated */)) { 716 717 // called function sets query->lastError 718 goto finish; 719 } 720 } 721 722 result = true; 723 724finish: 725 return result; 726} 727 728/******************************************************************************* 729* 730*******************************************************************************/ 731Boolean 732QEQueryAppendOrOperator(QEQueryRef query) 733{ 734 Boolean result = false; 735 736 if (query->logicOpActive) { 737 query->lastError = kQEQueryErrorSyntax; 738 goto finish; 739 } 740 741 query->logicOpActive = true; 742 743 if (_QEQueryStackTopIsAndGroup(query)) { 744 if (!_QEQueryPopGroup(query)) { 745 goto finish; 746 } 747 } 748 749 result = true; 750 751finish: 752 return result; 753} 754 755/******************************************************************************* 756* 757*******************************************************************************/ 758Boolean 759QEQueryStartGroup( 760 QEQueryRef query, 761 Boolean negated) 762{ 763 return _QEQueryStartGroup(query, false /* not an 'and' group */, negated); 764} 765 766/******************************************************************************* 767* 768*******************************************************************************/ 769Boolean 770_QEQueryStartGroup( 771 QEQueryRef query, 772 Boolean andFlag, 773 Boolean negated) 774{ 775 Boolean result = false; 776 777 if (!query->logicOpActive && _QEQueryStackTopIsOrGroup(query)) { 778 if (!_QEQueryPushGroup(query, false /* negated */, 779 true /* 'and' group */)) { 780 781 // called function sets query->lastError 782 goto finish; 783 } 784 } 785 786 if (!_QEQueryPushGroup(query, negated, andFlag)) { 787 // called function sets query->lastError 788 goto finish; 789 } 790 791 result = true; 792finish: 793 return result; 794} 795 796/******************************************************************************* 797* 798*******************************************************************************/ 799Boolean 800QEQueryEndGroup(QEQueryRef query) 801{ 802 Boolean result = false; 803 804 /* A complete query has no open groups. 805 */ 806 if (QEQueryIsComplete(query)) { 807 query->lastError = kQEQueryErrorGroupNesting; 808 goto finish; 809 } 810 811 /* Don't allow empty parentheses within an explicit group. 812 * Why? Well, find(1) doesn't. 813 */ 814 if (_QEQueryStackTopHasCount(query, 0)) { 815 query->lastError = kQEQueryErrorEmptyGroup; 816 goto finish; 817 } 818 819 /* If we are in an implicit group binding AND operators, end it 820 * now so that the explicit group binding OR operators can be ended. 821 */ 822 if (_QEQueryStackTopIsAndGroup(query)) { 823 if (!_QEQueryPopGroup(query)) { 824 // called function sets query->lastError 825 goto finish; 826 } 827 } 828 829 /* Two nested AND groups is an internal logic error. 830 */ 831 if (_QEQueryStackTopIsAndGroup(query)) { 832 query->lastError = kQEQueryErrorGroupNesting; 833 goto finish; 834 } 835 836 /* Now, if the topmost group is not an OR group, something else 837 * is wrong with out internal logic. 838 */ 839 if (!_QEQueryStackTopIsOrGroup(query)) { 840 query->lastError = kQEQueryErrorGroupNesting; 841 goto finish; 842 } 843 844 /* At last we can do something! Pop that OR group off the stack to close 845 * it, and if it only contains one element, coalesce it into its parent. 846 */ 847 if (!_QEQueryPopGroupAndCoalesce(query, false /* pop only if can coalesce */)) { 848 query->lastError = kQEQueryErrorGroupNesting; 849 goto finish; 850 } 851 852 /* Decrement the stack's OR group nesting level. 853 */ 854 query->nestingLevel--; 855 856 /* Now, if we are left with an AND group at the top of the stack, see if 857 * we can coalesce that too. 858 */ 859 if (_QEQueryStackTopIsAndGroup(query)) { 860 if (!_QEQueryPopGroupAndCoalesce(query, true /* pop only if can coalesce */)) { 861 query->lastError = kQEQueryErrorGroupNesting; 862 goto finish; 863 } 864 } 865 866 result = true; 867finish: 868 return result; 869} 870 871 872#pragma mark Query Elements 873 874/******************************************************************************* 875* 876*******************************************************************************/ 877CFStringRef 878QEQueryElementGetPredicate(CFDictionaryRef element) 879{ 880 return CFDictionaryGetValue(element, kQEQueryKeyPredicate); 881} 882 883/******************************************************************************* 884* 885*******************************************************************************/ 886CFMutableArrayRef 887QEQueryElementGetArguments(CFDictionaryRef element) 888{ 889 CFMutableDictionaryRef dict = (CFMutableDictionaryRef)element; 890 CFMutableArrayRef args = (CFMutableArrayRef)CFDictionaryGetValue( 891 element, kQEQueryKeyArguments); 892 if (!args) { 893 args = CFArrayCreateMutable(kCFAllocatorDefault, 894 0, &kCFTypeArrayCallBacks); 895 if (!args) { 896 goto finish; 897 } 898 QEQueryElementSetArgumentsArray(dict, args); 899 CFRelease(args); 900 } 901finish: 902 return args; 903} 904 905/******************************************************************************* 906* 907*******************************************************************************/ 908CFTypeRef 909QEQueryElementGetArgumentAtIndex( 910 CFDictionaryRef element, 911 CFIndex i) 912{ 913 CFArrayRef arguments = QEQueryElementGetArguments(element); 914 return CFArrayGetValueAtIndex(arguments, i); 915} 916 917/******************************************************************************* 918* 919*******************************************************************************/ 920void 921QEQueryElementSetPredicate( 922 CFMutableDictionaryRef element, 923 CFStringRef predicate) 924{ 925 CFDictionarySetValue(element, kQEQueryKeyPredicate, predicate); 926 return; 927} 928 929/******************************************************************************* 930* 931*******************************************************************************/ 932void 933QEQueryElementSetArgumentsArray( 934 CFMutableDictionaryRef element, 935 CFArrayRef arguments) 936{ 937 CFDictionarySetValue(element, kQEQueryKeyArguments, arguments); 938 return; 939} 940 941/******************************************************************************* 942* 943*******************************************************************************/ 944void 945QEQueryElementAppendArgument( 946 CFMutableDictionaryRef element, 947 CFTypeRef argument) 948{ 949 CFMutableArrayRef arguments = (CFMutableArrayRef)QEQueryElementGetArguments(element); 950 CFArrayAppendValue(arguments, argument); 951 return; 952} 953 954/******************************************************************************* 955* 956*******************************************************************************/ 957Boolean 958QEQueryElementSetArguments( 959 CFMutableDictionaryRef element, 960 uint32_t numArgs, 961 ...) 962{ 963 Boolean result = false; 964 CFMutableArrayRef arguments = NULL; 965 va_list ap; 966 uint32_t i; 967 968 if (!numArgs) { 969 goto finish; 970 } 971 972 arguments = QEQueryElementGetArguments(element); 973 if (!arguments) { 974 arguments = CFArrayCreateMutable(kCFAllocatorDefault, 975 0, &kCFTypeArrayCallBacks); 976 if (!arguments) { 977 goto finish; 978 } 979 CFDictionarySetValue(element, kQEQueryKeyArguments, arguments); 980 CFRelease(arguments); 981 } 982 983 va_start(ap, numArgs); 984 for (i = 0; i < numArgs; i++) { 985 char * arg = va_arg(ap, char *); 986 if (arg) { 987 CFStringRef string = CFStringCreateWithCString(kCFAllocatorDefault, 988 arg, kCFStringEncodingUTF8); 989 if (!string) { 990 goto finish; 991 } 992 CFArrayAppendValue(arguments, string); 993 CFRelease(string); 994 } 995 } 996 997 result = true; 998 999finish: 1000 va_end(ap); 1001 return result; 1002} 1003 1004#pragma mark Debug Printing (Crufty) 1005 1006/******************************************************************************/ 1007 1008void 1009_QEQueryElementPrint(CFDictionaryRef element, Boolean printOuterDelimiter) 1010{ 1011 CFIndex count, i; 1012 char * andGroupOpen = "{"; 1013 char * andGroupClose = "}"; 1014 CFTypeRef value = NULL; 1015 1016 if (_QEQueryElementIsNegated(element)) { 1017 printf("-not "); 1018 } 1019 1020 value = CFDictionaryGetValue(element, kQEQueryKeyPredicate); 1021 if (CFEqual(value, kQEQueryPredicateAnd) || 1022 CFEqual(value, kQEQueryPredicateOr)) { 1023 1024 Boolean andGroup = CFEqual(value, kQEQueryPredicateAnd); 1025 CFArrayRef elements = CFDictionaryGetValue(element, kQEQueryKeyArguments); 1026 1027 if (elements) { 1028 count = CFArrayGetCount(elements); 1029 if (count) { 1030 if (printOuterDelimiter) { 1031 printf("%s", andGroup ? andGroupOpen : "(");fflush(stdout); 1032 } 1033 for (i = 0; i < count; i++) { 1034 if (i) { 1035 printf(" %s ", andGroup ? "-and" : "-or");fflush(stdout); 1036 } 1037 _QEQueryElementPrint(CFArrayGetValueAtIndex(elements, i), 1038 true); 1039 } 1040 if (printOuterDelimiter) { 1041 printf("%s", andGroup ? andGroupClose : ")");fflush(stdout); 1042 } 1043 } 1044 } 1045 } else { 1046 char * predicate = NULL; 1047 CFArrayRef arguments = NULL; 1048 1049 predicate = createUTF8CStringForCFString(value); 1050 if (!predicate) { 1051 fprintf(stderr, "%s", kMsgStringConversionError);fflush(stderr); 1052 goto finish; 1053 } 1054 1055 printf("%s", predicate);fflush(stdout); 1056 free(predicate); 1057 1058 arguments = CFDictionaryGetValue(element, kQEQueryKeyArguments); 1059 if (arguments) { 1060 count = CFArrayGetCount(arguments); 1061 if (count) { 1062 for (i = 0; i < count; i++) { 1063 CFStringRef argString = CFArrayGetValueAtIndex(arguments, i); 1064 if (CFGetTypeID(argString) == CFStringGetTypeID()) { 1065 char * arg = createUTF8CStringForCFString(argString); 1066 if (!arg) { 1067 fprintf(stderr, "%s", kMsgStringConversionError);fflush(stderr); 1068 goto finish; 1069 } 1070 printf(" %s", arg);fflush(stdout); 1071 free(arg); 1072 } else { 1073 printf(" <non-string>");fflush(stdout); 1074 } 1075 } 1076 } 1077 } 1078 } 1079finish: 1080 return; 1081} 1082 1083/******************************************************************************* 1084* 1085*******************************************************************************/ 1086//extern void printPList(FILE * stream, CFTypeRef plist); 1087 1088void 1089QEQueryPrint(QEQueryRef query) 1090{ 1091// printPList(stdout, query->queryRoot); 1092 _QEQueryElementPrint(query->queryRoot, false); 1093 printf("\n"); 1094 return; 1095} 1096 1097#pragma mark Internal Functions 1098 1099/******************************************************************************* 1100* _QEQueryCreateGroup() creates a grouping dictionary and returns it. Returns 1101* NULL on failure. 1102*******************************************************************************/ 1103CFMutableDictionaryRef 1104_QEQueryCreateGroup(Boolean andFlag) 1105{ 1106 CFMutableDictionaryRef result = NULL; // returned 1107 CFMutableArrayRef elements = NULL; // must release 1108 Boolean ok = false; 1109 1110 result = CFDictionaryCreateMutable(kCFAllocatorDefault, 1111 0 /* no limit */, &kCFTypeDictionaryKeyCallBacks, 1112 &kCFTypeDictionaryValueCallBacks); 1113 if (!result) { 1114 goto finish; 1115 } 1116 1117 CFDictionarySetValue(result, kQEQueryKeyPredicate, 1118 andFlag ? kQEQueryPredicateAnd : kQEQueryPredicateOr); 1119 1120 elements = CFArrayCreateMutable(kCFAllocatorDefault, 1121 0, &kCFTypeArrayCallBacks); 1122 if (!elements) { 1123 goto finish; 1124 } 1125 1126 CFDictionarySetValue(result, kQEQueryKeyArguments, elements); 1127 1128 CFRelease(elements); 1129 elements = NULL; 1130 1131 ok = true; 1132 1133finish: 1134 if (!ok) { 1135 if (result) { 1136 CFRelease(result); 1137 result = NULL; 1138 } 1139 } 1140 return result; 1141} 1142 1143/******************************************************************************* 1144* _QEQueryYankElement() pulls the last element, if any, from the group at the 1145* top of the query's group stack, and returns it. It's used to pull an 1146* element from an OR group when a higher-precendence AND operator is 1147* encountered. 1148*******************************************************************************/ 1149CFMutableDictionaryRef 1150_QEQueryYankElement(QEQueryRef query) 1151{ 1152 CFMutableDictionaryRef result = NULL; 1153 CFMutableArrayRef elements = NULL; 1154 CFIndex count; 1155 1156 elements = (CFMutableArrayRef)CFDictionaryGetValue( 1157 query->queryStackTop, kQEQueryKeyArguments); 1158 count = CFArrayGetCount(elements); 1159 1160 if (count) { 1161 result = (CFMutableDictionaryRef)CFArrayGetValueAtIndex( 1162 elements, count - 1); 1163 CFRetain(result); 1164 CFArrayRemoveValueAtIndex(elements, count - 1); 1165 } 1166 1167 return result; 1168} 1169 1170/******************************************************************************* 1171* 1172*******************************************************************************/ 1173Boolean 1174_QEQueryStackTopIsAndGroup(QEQueryRef query) 1175{ 1176 CFStringRef predicate = CFDictionaryGetValue(query->queryStackTop, 1177 kQEQueryKeyPredicate); 1178 if (predicate && CFEqual(predicate, kQEQueryPredicateAnd)) { 1179 return true; 1180 } 1181 return false; 1182} 1183 1184/******************************************************************************* 1185* 1186*******************************************************************************/ 1187Boolean 1188_QEQueryStackTopIsOrGroup(QEQueryRef query) 1189{ 1190 CFStringRef predicate = CFDictionaryGetValue(query->queryStackTop, 1191 kQEQueryKeyPredicate); 1192 if (predicate && CFEqual(predicate, kQEQueryPredicateOr)) { 1193 return true; 1194 } 1195 return false; 1196} 1197 1198/******************************************************************************* 1199* 1200*******************************************************************************/ 1201Boolean 1202_QEQueryStackTopHasCount(QEQueryRef query, CFIndex count) 1203{ 1204 CFArrayRef elements = CFDictionaryGetValue(query->queryStackTop, 1205 kQEQueryKeyArguments); 1206 if (elements && CFArrayGetCount(elements) == count) { 1207 return true; 1208 } else if (!elements && (count == 0)) { 1209 return true; 1210 } 1211 return false; 1212} 1213 1214/******************************************************************************* 1215* 1216*******************************************************************************/ 1217Boolean 1218_QEQueryPushGroup( 1219 QEQueryRef query, 1220 Boolean negated, 1221 Boolean andFlag) 1222{ 1223 Boolean result = false; 1224 CFMutableDictionaryRef newGroup = NULL; 1225 CFMutableDictionaryRef yankedElement = NULL; 1226 CFMutableArrayRef elements = NULL; 1227 1228 newGroup = _QEQueryCreateGroup(andFlag); 1229 if (!newGroup) { 1230 query->lastError = kQEQueryErrorNoMemory; 1231 goto finish; 1232 } 1233 1234 if (negated) { 1235 CFDictionarySetValue(newGroup, kQEQueryKeyNegated, kCFBooleanTrue); 1236 } 1237 1238 if (andFlag) { 1239 yankedElement = _QEQueryYankElement(query); 1240 } else { 1241 query->nestingLevel++; 1242 } 1243 1244 elements = (CFMutableArrayRef)CFDictionaryGetValue( 1245 query->queryStackTop, kQEQueryKeyArguments); 1246 1247 CFArrayAppendValue(elements, (const void *)newGroup); 1248 CFArrayAppendValue(query->queryStack, (const void *)newGroup); 1249 query->queryStackTop = newGroup; 1250 1251 if (yankedElement) { 1252 QEQueryAppendElement(query, yankedElement); 1253 CFRelease(yankedElement); 1254 } 1255 1256 result = true; 1257 1258finish: 1259 return result; 1260} 1261 1262/******************************************************************************* 1263* 1264*******************************************************************************/ 1265Boolean 1266_QEQueryPopGroup(QEQueryRef query) 1267{ 1268 Boolean result = false; 1269 CFIndex stackDepth; 1270 1271 stackDepth = CFArrayGetCount(query->queryStack); 1272 if (stackDepth < 2) { 1273// fprintf(stderr, "query stack error\n"); 1274 query->lastError = kQEQueryErrorGroupNesting; 1275 goto finish; 1276 } 1277 CFArrayRemoveValueAtIndex(query->queryStack, stackDepth - 1); 1278 query->queryStackTop = (CFMutableDictionaryRef)CFArrayGetValueAtIndex( 1279 query->queryStack, stackDepth - 2); 1280 1281 result = true; 1282finish: 1283 return result; 1284} 1285 1286/******************************************************************************* 1287* 1288*******************************************************************************/ 1289Boolean 1290_QEQueryPopGroupAndCoalesce( 1291 QEQueryRef query, 1292 Boolean onlyIfCanCoalesce) 1293{ 1294 Boolean result = false; 1295 CFMutableArrayRef topArgs = NULL; 1296 CFMutableDictionaryRef singleElement = NULL; 1297 CFMutableDictionaryRef groupOfOne = NULL; 1298 Boolean canCoalesce = false; 1299 1300 topArgs = QEQueryElementGetArguments(query->queryStackTop); 1301 1302 canCoalesce = (_QEQueryStackTopHasCount(query, 1) && 1303 (query->queryStackTop != query->queryRoot)); 1304 if (onlyIfCanCoalesce && !canCoalesce) { 1305 result = true; 1306 goto finish; 1307 } 1308 1309 if (canCoalesce) { 1310 singleElement = (CFMutableDictionaryRef)CFArrayGetValueAtIndex(topArgs, 0); 1311 CFRetain(singleElement); 1312 } 1313 1314 if (!_QEQueryPopGroup(query)) { 1315 // called function sets query->lastError 1316 goto finish; 1317 } 1318 1319 topArgs = QEQueryElementGetArguments(query->queryStackTop); 1320 1321 if (canCoalesce) { 1322 groupOfOne = _QEQueryYankElement(query); 1323 if (!groupOfOne) { 1324 query->lastError = kQEQueryErrorGroupNesting; 1325 goto finish; 1326 } 1327 CFRelease(groupOfOne); 1328 if (_QEQueryElementIsNegated(groupOfOne)) { 1329 _QEQueryElementNegate(singleElement); 1330 } 1331 CFArrayAppendValue(topArgs, singleElement); 1332 } 1333 1334 result = true; 1335finish: 1336 if (singleElement) CFRelease(singleElement); 1337 return result; 1338} 1339 1340/******************************************************************************* 1341* 1342*******************************************************************************/ 1343CFStringRef _QEQueryOperatorForToken( 1344 QEQueryRef query, 1345 CFStringRef token) 1346{ 1347 return CFDictionaryGetValue(query->operators, token); 1348} 1349 1350/******************************************************************************* 1351* 1352*******************************************************************************/ 1353CFStringRef _QEPredicateForString( 1354 QEQueryRef query, 1355 char * string) 1356{ 1357 CFStringRef predicate = NULL; 1358 CFStringRef synonym = NULL; // do not release 1359 1360 predicate = CFStringCreateWithCString(kCFAllocatorDefault, 1361 string, kCFStringEncodingUTF8); 1362 if (!predicate) { 1363 goto finish; 1364 } 1365 1366 synonym = CFDictionaryGetValue(query->synonyms, predicate); 1367 if (synonym) { 1368 CFRelease(predicate); 1369 predicate = CFRetain(synonym); 1370 } 1371 1372finish: 1373 return predicate; 1374} 1375 1376/******************************************************************************* 1377* 1378*******************************************************************************/ 1379QEQueryParseCallback 1380_QEQueryParseCallbackForPredicate( 1381 QEQueryRef query, 1382 CFStringRef predicate) 1383{ 1384 QEQueryParseCallback result = NULL; 1385 CFDataRef callbackData = NULL; 1386 const void * dataPtr = NULL; 1387 QEQueryParseCallback * callback = NULL; 1388 1389 callbackData = CFDictionaryGetValue(query->parseCallbacks, predicate); 1390 if (!callbackData) { 1391 goto finish; 1392 } 1393 dataPtr = CFDataGetBytePtr(callbackData); 1394 callback = (QEQueryParseCallback *)dataPtr; 1395 result = *callback; 1396finish: 1397 return result; 1398} 1399 1400/******************************************************************************* 1401* 1402*******************************************************************************/ 1403QEQueryEvaluationCallback 1404_QEQueryEvaluationCallbackForPredicate( 1405 QEQueryRef query, 1406 CFStringRef predicate) 1407{ 1408 QEQueryEvaluationCallback result = NULL; 1409 CFDataRef callbackData = NULL; 1410 const void * dataPtr = NULL; 1411 QEQueryEvaluationCallback * callback = NULL; 1412 1413 callbackData = CFDictionaryGetValue(query->evaluationCallbacks, predicate); 1414 if (!callbackData) { 1415 goto finish; 1416 } 1417 dataPtr = CFDataGetBytePtr(callbackData); 1418 callback = (QEQueryEvaluationCallback *)dataPtr; 1419 result = *callback; 1420finish: 1421 return result; 1422} 1423 1424/******************************************************************************* 1425* 1426*******************************************************************************/ 1427Boolean 1428_QEQueryElementIsNegated(CFDictionaryRef element) 1429{ 1430 if (CFDictionaryGetValue(element, kQEQueryKeyNegated)) { 1431 return true; 1432 } 1433 return false; 1434} 1435 1436/******************************************************************************* 1437* 1438*******************************************************************************/ 1439void 1440_QEQueryElementNegate(CFMutableDictionaryRef element) 1441{ 1442 if (CFDictionaryGetValue(element, kQEQueryKeyNegated)) { 1443 CFDictionaryRemoveValue(element, kQEQueryKeyNegated); 1444 } else { 1445 CFDictionarySetValue(element, kQEQueryKeyNegated, 1446 kCFBooleanTrue); 1447 } 1448 return; 1449} 1450