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