1/* Interface for NSPredicate for GNUStep
2   Copyright (C) 2005 Free Software Foundation, Inc.
3
4   Written by:  Dr. H. Nikolaus Schaller
5   Created: 2005
6   Modifications: Fred Kiefer <FredKiefer@gmx.de>
7   Date: May 2007
8   Modifications: Richard Frith-Macdoanld <rfm@gnu.org>
9   Date: June 2007
10
11   This file is part of the GNUstep Base Library.
12
13   This library is free software; you can redistribute it and/or
14   modify it under the terms of the GNU Lesser General Public
15   License as published by the Free Software Foundation; either
16   version 2 of the License, or (at your option) any later version.
17
18   This library is distributed in the hope that it will be useful,
19   but WITHOUT ANY WARRANTY; without even the implied warranty of
20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21   Lesser General Public License for more details.
22
23   You should have received a copy of the GNU Lesser General Public
24   License along with this library; if not, write to the Free
25   Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
26   Boston, MA 02110 USA.
27   */
28
29#import "common.h"
30
31#define	EXPOSE_NSComparisonPredicate_IVARS	1
32#define	EXPOSE_NSCompoundPredicate_IVARS	1
33#define	EXPOSE_NSExpression_IVARS	1
34
35#import "Foundation/NSComparisonPredicate.h"
36#import "Foundation/NSCompoundPredicate.h"
37#import "Foundation/NSExpression.h"
38#import "Foundation/NSPredicate.h"
39
40#import "Foundation/NSArray.h"
41#import "Foundation/NSDate.h"
42#import "Foundation/NSDictionary.h"
43#import "Foundation/NSEnumerator.h"
44#import "Foundation/NSException.h"
45#import "Foundation/NSKeyValueCoding.h"
46#import "Foundation/NSNull.h"
47#import "Foundation/NSScanner.h"
48#import "Foundation/NSValue.h"
49
50#import "GSPrivate.h"
51
52// For pow()
53#include <math.h>
54
55#if     defined(HAVE_UNICODE_UREGEX_H)
56#include <unicode/uregex.h>
57#endif
58
59/* Object to represent the expression beign evaluated.
60 */
61static NSExpression	*evaluatedObjectExpression = nil;
62
63extern void     GSPropertyListMake(id,NSDictionary*,BOOL,BOOL,unsigned,id*);
64
65@interface GSPredicateScanner : NSScanner
66{
67  NSEnumerator	*_args;		// Not retained.
68  unsigned	_retrieved;
69}
70
71- (id) initWithString: (NSString*)format
72		 args: (NSArray*)args;
73- (id) nextArg;
74- (BOOL) scanPredicateKeyword: (NSString *) key;
75- (NSPredicate *) parse;
76- (NSPredicate *) parsePredicate;
77- (NSPredicate *) parseAnd;
78- (NSPredicate *) parseNot;
79- (NSPredicate *) parseOr;
80- (NSPredicate *) parseComparison;
81- (NSExpression *) parseExpression;
82- (NSExpression *) parseFunctionalExpression;
83- (NSExpression *) parsePowerExpression;
84- (NSExpression *) parseMultiplicationExpression;
85- (NSExpression *) parseAdditionExpression;
86- (NSExpression *) parseBinaryExpression;
87- (NSExpression *) parseSimpleExpression;
88
89@end
90
91@interface GSTruePredicate : NSPredicate
92@end
93
94@interface GSFalsePredicate : NSPredicate
95@end
96
97@interface GSAndCompoundPredicate : NSCompoundPredicate
98@end
99
100@interface GSOrCompoundPredicate : NSCompoundPredicate
101@end
102
103@interface GSNotCompoundPredicate : NSCompoundPredicate
104@end
105
106@interface NSExpression (Private)
107- (id) _expressionWithSubstitutionVariables: (NSDictionary *)variables;
108@end
109
110@interface GSConstantValueExpression : NSExpression
111{
112  @public
113  id	_obj;
114}
115@end
116
117@interface GSEvaluatedObjectExpression : NSExpression
118@end
119
120@interface GSVariableExpression : NSExpression
121{
122  @public
123  NSString	*_variable;
124}
125@end
126
127@interface GSKeyPathExpression : NSExpression
128{
129  @public
130  NSString	*_keyPath;
131}
132@end
133
134@interface GSFunctionExpression : NSExpression
135{
136  @public
137  NSString		*_function;
138  NSArray		*_args;
139  unsigned int		_argc;
140  SEL                   _selector;
141  NSString              *_op;        // Not retained;
142}
143@end
144
145#if OS_API_VERSION(MAC_OS_X_VERSION_10_6, GS_API_LATEST)
146@interface GSBlockPredicate : NSPredicate
147{
148  GSBlockPredicateBlock _block;
149}
150
151- (instancetype) initWithBlock: (GSBlockPredicateBlock)block;
152@end
153
154
155@interface GSBoundBlockPredicate : GSBlockPredicate
156{
157  GS_GENERIC_CLASS(NSDictionary,NSString*,id)* _bindings;
158}
159- (instancetype) initWithBlock: (GSBlockPredicateBlock)block
160                      bindings: (GS_GENERIC_CLASS(NSDictionary,NSString*,id)*)bindings;
161@end
162#endif
163
164@implementation NSPredicate
165
166+ (NSPredicate *) predicateWithFormat: (NSString *) format, ...
167{
168  NSPredicate	*p;
169  va_list	va;
170
171  va_start(va, format);
172  p = [self predicateWithFormat: format arguments: va];
173  va_end(va);
174  return p;
175}
176
177+ (NSPredicate *) predicateWithFormat: (NSString *)format
178                        argumentArray: (NSArray *)args
179{
180  GSPredicateScanner	*s;
181  NSPredicate		*p;
182
183  s = [[GSPredicateScanner alloc] initWithString: format
184                                            args: args];
185  p = [s parse];
186  RELEASE(s);
187  return p;
188}
189
190+ (NSPredicate *) predicateWithFormat: (NSString *)format
191                            arguments: (va_list)args
192{
193  GSPredicateScanner	*s;
194  NSPredicate		*p;
195  const char            *ptr = [format UTF8String];
196  NSMutableArray        *arr = [NSMutableArray arrayWithCapacity: 10];
197
198  while (*ptr != 0)
199    {
200      char      c = *ptr++;
201
202      if (c == '%')
203        {
204          c = *ptr;
205          switch (c)
206            {
207              case '%':
208                ptr++;
209                break;
210
211              case 'K':
212              case '@':
213                ptr++;
214                [arr addObject: va_arg(args, id)];
215                break;
216
217              case 'c':
218                ptr++;
219                [arr addObject: [NSNumber numberWithChar:
220                  (char)va_arg(args, NSInteger)]];
221                break;
222
223              case 'C':
224                ptr++;
225                [arr addObject: [NSNumber numberWithShort:
226                  (short)va_arg(args, NSInteger)]];
227                break;
228
229              case 'd':
230              case 'D':
231              case 'i':
232                ptr++;
233                [arr addObject: [NSNumber numberWithInt:
234                  va_arg(args, int)]];
235                break;
236
237              case 'o':
238              case 'O':
239              case 'u':
240              case 'U':
241              case 'x':
242              case 'X':
243                ptr++;
244                [arr addObject: [NSNumber numberWithUnsignedInt:
245                  va_arg(args, unsigned)]];
246                break;
247
248              case 'e':
249              case 'E':
250              case 'f':
251              case 'g':
252              case 'G':
253                ptr++;
254                [arr addObject: [NSNumber numberWithDouble:
255                  va_arg(args, double)]];
256                break;
257
258              case 'h':
259                ptr++;
260                if (*ptr != 0)
261                  {
262                    c = *ptr;
263                    if (c == 'i')
264                      {
265                        [arr addObject: [NSNumber numberWithShort:
266                          (short)va_arg(args, NSInteger)]];
267                      }
268                    if (c == 'u')
269                      {
270                        [arr addObject: [NSNumber numberWithUnsignedShort:
271                          (unsigned short)va_arg(args, NSInteger)]];
272                      }
273                  }
274                break;
275
276              case 'q':
277                ptr++;
278                if (*ptr != 0)
279                  {
280                    c = *ptr;
281                    if (c == 'i')
282                      {
283                        [arr addObject: [NSNumber numberWithLongLong:
284                          va_arg(args, long long)]];
285                      }
286                    if (c == 'u' || c == 'x' || c == 'X')
287                      {
288                        [arr addObject: [NSNumber numberWithUnsignedLongLong:
289                          va_arg(args, unsigned long long)]];
290                      }
291                  }
292                break;
293            }
294        }
295      else if (c == '\'')
296        {
297          while (*ptr != 0)
298            {
299              if (*ptr++ == '\'')
300                {
301                  break;
302                }
303            }
304        }
305      else if (c == '"')
306        {
307          while (*ptr != 0)
308            {
309              if (*ptr++ == '"')
310                {
311                  break;
312                }
313            }
314        }
315    }
316  s = [[GSPredicateScanner alloc] initWithString: format
317                                            args: arr];
318  p = [s parse];
319  RELEASE(s);
320  return p;
321}
322
323+ (NSPredicate *) predicateWithValue: (BOOL)value
324{
325  if (value)
326    {
327      return AUTORELEASE([GSTruePredicate new]);
328    }
329  else
330    {
331      return AUTORELEASE([GSFalsePredicate new]);
332    }
333}
334
335// we don't ever instantiate NSPredicate
336
337- (id) copyWithZone: (NSZone *)z
338{
339  return NSCopyObject(self, 0, z);
340}
341
342- (BOOL) evaluateWithObject: (id)object
343{
344  [self subclassResponsibility: _cmd];
345  return NO;
346}
347
348- (NSString *) description
349{
350  return [self predicateFormat];
351}
352
353- (NSString *) predicateFormat
354{
355  [self subclassResponsibility: _cmd];
356  return nil;
357}
358
359- (NSPredicate *) predicateWithSubstitutionVariables: (NSDictionary *)variables
360{
361  return AUTORELEASE([self copy]);
362}
363
364#if OS_API_VERSION(MAC_OS_X_VERSION_10_5, GS_API_LATEST)
365- (BOOL) evaluateWithObject: (id)object
366      substitutionVariables: (GS_GENERIC_CLASS(NSDictionary, NSString*, id)*)variables
367{
368  return [[self predicateWithSubstitutionVariables: variables]
369                                evaluateWithObject: object];
370}
371#endif
372- (Class) classForCoder
373{
374  return [NSPredicate class];
375}
376
377- (void) encodeWithCoder: (NSCoder *) coder;
378{
379  // FIXME
380  [self subclassResponsibility: _cmd];
381}
382
383- (id) initWithCoder: (NSCoder *) coder;
384{
385  // FIXME
386  [self subclassResponsibility: _cmd];
387  return self;
388}
389
390#if OS_API_VERSION(MAC_OS_X_VERSION_10_6, GS_API_LATEST)
391+ (NSPredicate*)predicateWithBlock: (GSBlockPredicateBlock)block
392{
393  return [[[GSBlockPredicate alloc] initWithBlock: block] autorelease];
394}
395#endif
396@end
397
398@implementation GSTruePredicate
399
400- (id) copyWithZone: (NSZone *)z
401{
402  return RETAIN(self);
403}
404
405- (BOOL) evaluateWithObject: (id)object
406{
407  return YES;
408}
409
410- (NSString *) predicateFormat
411{
412  return @"TRUEPREDICATE";
413}
414
415@end
416
417@implementation GSFalsePredicate
418
419- (id) copyWithZone: (NSZone *)z
420{
421  return RETAIN(self);
422}
423
424- (BOOL) evaluateWithObject: (id)object
425{
426  return NO;
427}
428
429- (NSString *) predicateFormat
430{
431  return @"FALSEPREDICATE";
432}
433
434@end
435
436@implementation NSCompoundPredicate
437
438+ (NSPredicate *) andPredicateWithSubpredicates: (NSArray *)list
439{
440  return AUTORELEASE([[GSAndCompoundPredicate alloc]
441    initWithType: NSAndPredicateType subpredicates: list]);
442}
443
444+ (NSPredicate *) notPredicateWithSubpredicate: (NSPredicate *)predicate
445{
446  NSArray       *list;
447
448  list = [NSArray arrayWithObject: predicate];
449  return AUTORELEASE([[GSNotCompoundPredicate alloc]
450    initWithType: NSNotPredicateType subpredicates: list]);
451}
452
453+ (NSPredicate *) orPredicateWithSubpredicates: (NSArray *)list
454{
455  return AUTORELEASE([[GSOrCompoundPredicate alloc]
456    initWithType: NSOrPredicateType subpredicates: list]);
457}
458
459- (NSCompoundPredicateType) compoundPredicateType
460{
461  return _type;
462}
463
464- (id) initWithType: (NSCompoundPredicateType)type
465      subpredicates: (NSArray *)list
466{
467  if ((self = [super init]) != nil)
468    {
469      _type = type;
470      ASSIGNCOPY(_subs, list);
471    }
472  return self;
473}
474
475- (void) dealloc
476{
477  RELEASE(_subs);
478  [super dealloc];
479}
480
481- (id) copyWithZone: (NSZone *)z
482{
483  return [[[self class] alloc] initWithType: _type subpredicates: _subs];
484}
485
486- (NSArray *) subpredicates
487{
488  return _subs;
489}
490
491- (NSPredicate *) predicateWithSubstitutionVariables: (NSDictionary *)variables
492{
493  unsigned int count = [_subs count];
494  NSMutableArray *esubs = [NSMutableArray arrayWithCapacity: count];
495  unsigned int i;
496  NSPredicate  *p;
497
498  for (i = 0; i < count; i++)
499    {
500      [esubs addObject: [[_subs objectAtIndex: i]
501                            predicateWithSubstitutionVariables: variables]];
502    }
503
504  p = [[[self class] alloc] initWithType: _type subpredicates: esubs];
505  return AUTORELEASE(p);
506}
507
508- (Class) classForCoder
509{
510  return [NSCompoundPredicate class];
511}
512
513- (void) encodeWithCoder: (NSCoder *)coder
514{
515  // FIXME
516  [self subclassResponsibility: _cmd];
517}
518
519- (id) initWithCoder: (NSCoder *)coder
520{
521  // FIXME
522  [self subclassResponsibility: _cmd];
523  return self;
524}
525
526@end
527
528@implementation GSAndCompoundPredicate
529
530- (BOOL) evaluateWithObject: (id) object
531{
532  NSEnumerator	*e = [_subs objectEnumerator];
533  NSPredicate	*p;
534
535  while ((p = [e nextObject]) != nil)
536    {
537      if ([p evaluateWithObject: object] == NO)
538        {
539          return NO;  // any NO returns NO
540        }
541    }
542  return YES;  // all are true
543}
544
545- (NSString *) predicateFormat
546{
547  NSString	*fmt = @"";
548  NSEnumerator	*e = [_subs objectEnumerator];
549  NSPredicate	*sub;
550  unsigned	cnt = 0;
551
552  while ((sub = [e nextObject]) != nil)
553    {
554      // when to add ()? -> if sub is compound and of type "or"
555      if (cnt == 0)
556        {
557          fmt = [sub predicateFormat];  // first
558        }
559      else
560        {
561          if (cnt == 1
562            && [[_subs objectAtIndex: 0]
563              isKindOfClass: [NSCompoundPredicate class]]
564            && [(NSCompoundPredicate *)[_subs objectAtIndex: 0]
565              compoundPredicateType] == NSOrPredicateType)
566            {
567              // we need () around first OR on left side
568              fmt = [NSString stringWithFormat: @"(%@)", fmt];
569            }
570          if ([sub isKindOfClass: [NSCompoundPredicate class]]
571              && [(NSCompoundPredicate *) sub compoundPredicateType]
572              == NSOrPredicateType)
573            {
574              // we need () around right OR
575              fmt = [NSString stringWithFormat: @"%@ AND (%@)",
576                              fmt, [sub predicateFormat]];
577            }
578          else
579            {
580              fmt = [NSString stringWithFormat: @"%@ AND %@",
581                              fmt, [sub predicateFormat]];
582            }
583        }
584      cnt++;
585    }
586  return fmt;
587}
588
589@end
590
591@implementation GSOrCompoundPredicate
592
593- (BOOL) evaluateWithObject: (id)object
594{
595  NSEnumerator	*e = [_subs objectEnumerator];
596  NSPredicate	*p;
597
598  while ((p = [e nextObject]) != nil)
599    {
600      if ([p evaluateWithObject: object] == YES)
601        {
602          return YES;  // any YES returns YES
603        }
604    }
605  return NO;  // none is true
606}
607
608- (NSString *) predicateFormat
609{
610  NSString	*fmt = @"";
611  NSEnumerator	*e = [_subs objectEnumerator];
612  NSPredicate	*sub;
613
614  while ((sub = [e nextObject]) != nil)
615    {
616      if ([fmt length] > 0)
617        {
618          fmt = [NSString stringWithFormat: @"%@ OR %@",
619                          fmt, [sub predicateFormat]];
620        }
621      else
622        {
623          fmt = [sub predicateFormat];  // first
624        }
625    }
626  return fmt;
627}
628
629@end
630
631@implementation GSNotCompoundPredicate
632
633- (BOOL) evaluateWithObject: (id)object
634{
635  NSPredicate *sub = [_subs objectAtIndex: 0];
636
637  return ![sub evaluateWithObject: object];
638}
639
640- (NSString *) predicateFormat
641{
642  NSPredicate *sub = [_subs objectAtIndex: 0];
643
644  if ([sub isKindOfClass: [NSCompoundPredicate class]]
645    && [(NSCompoundPredicate *)sub compoundPredicateType]
646      != NSNotPredicateType)
647    {
648      return [NSString stringWithFormat: @"NOT(%@)", [sub predicateFormat]];
649    }
650  return [NSString stringWithFormat: @"NOT %@", [sub predicateFormat]];
651}
652
653@end
654
655@implementation NSComparisonPredicate
656
657+ (NSPredicate *) predicateWithLeftExpression: (NSExpression *)left
658                              rightExpression: (NSExpression *)right
659                               customSelector: (SEL) sel
660{
661  return AUTORELEASE([[self alloc] initWithLeftExpression: left
662                                          rightExpression: right
663                                           customSelector: sel]);
664}
665
666+ (NSPredicate *) predicateWithLeftExpression: (NSExpression *)left
667                              rightExpression: (NSExpression *)right
668                                     modifier: (NSComparisonPredicateModifier)modifier
669                                         type: (NSPredicateOperatorType)type
670                                      options: (NSUInteger)opts
671{
672  return AUTORELEASE([[self alloc] initWithLeftExpression: left
673                                          rightExpression: right
674                                                 modifier: modifier
675                                                     type: type
676                                                  options: opts]);
677}
678
679- (NSPredicate *) initWithLeftExpression: (NSExpression *)left
680                         rightExpression: (NSExpression *)right
681                          customSelector: (SEL)sel
682{
683  if ((self = [super init]) != nil)
684    {
685      ASSIGN(_left, left);
686      ASSIGN(_right, right);
687      _selector = sel;
688      _type = NSCustomSelectorPredicateOperatorType;
689    }
690  return self;
691}
692
693- (id) initWithLeftExpression: (NSExpression *)left
694              rightExpression: (NSExpression *)right
695                     modifier: (NSComparisonPredicateModifier)modifier
696                         type: (NSPredicateOperatorType)type
697                      options: (NSUInteger)opts
698{
699  if ((self = [super init]) != nil)
700    {
701      ASSIGN(_left, left);
702      ASSIGN(_right, right);
703      _modifier = modifier;
704      _type = type;
705      _options = opts;
706    }
707  return self;
708}
709
710- (void) dealloc;
711{
712  RELEASE(_left);
713  RELEASE(_right);
714  [super dealloc];
715}
716
717- (NSComparisonPredicateModifier) comparisonPredicateModifier
718{
719  return _modifier;
720}
721
722- (SEL) customSelector
723{
724  return _selector;
725}
726
727- (NSExpression *) leftExpression
728{
729  return _left;
730}
731
732- (NSUInteger) options
733{
734  return _options;
735}
736
737- (NSPredicateOperatorType) predicateOperatorType
738{
739  return _type;
740}
741
742- (NSExpression *) rightExpression
743{
744  return _right;
745}
746
747- (NSString *) predicateFormat
748{
749  NSString	*modi = @"";
750  NSString	*comp = @"?comparison?";
751  NSString	*opt = @"";
752
753  switch (_modifier)
754    {
755      case NSDirectPredicateModifier:
756        break;
757      case NSAnyPredicateModifier:
758        modi = @"ANY ";
759        break;
760      case NSAllPredicateModifier:
761        modi = @"ALL";
762        break;
763      default:
764        modi = @"?modifier?";
765        break;
766    }
767  switch (_type)
768    {
769      case NSLessThanPredicateOperatorType:
770        comp = @"<";
771        break;
772      case NSLessThanOrEqualToPredicateOperatorType:
773        comp = @"<=";
774        break;
775      case NSGreaterThanPredicateOperatorType:
776        comp = @">=";
777        break;
778      case NSGreaterThanOrEqualToPredicateOperatorType:
779        comp = @">";
780        break;
781      case NSEqualToPredicateOperatorType:
782        comp = @"=";
783        break;
784      case NSNotEqualToPredicateOperatorType:
785        comp = @"!=";
786        break;
787      case NSMatchesPredicateOperatorType:
788        comp = @"MATCHES";
789        break;
790      case NSLikePredicateOperatorType:
791        comp = @"LIKE";
792        break;
793      case NSBeginsWithPredicateOperatorType:
794        comp = @"BEGINSWITH";
795        break;
796      case NSEndsWithPredicateOperatorType:
797        comp = @"ENDSWITH";
798        break;
799      case NSInPredicateOperatorType:
800        comp = @"IN";
801        break;
802      case NSCustomSelectorPredicateOperatorType:
803        comp = NSStringFromSelector(_selector);
804        break;
805      case NSContainsPredicateOperatorType:
806        comp = @"CONTAINS";
807        break;
808      case NSBetweenPredicateOperatorType:
809        comp = @"BETWEEN";
810        break;
811    }
812  switch (_options)
813    {
814      case NSCaseInsensitivePredicateOption:
815        opt = @"[c]";
816        break;
817      case NSDiacriticInsensitivePredicateOption:
818        opt = @"[d]";
819        break;
820      case NSCaseInsensitivePredicateOption
821        | NSDiacriticInsensitivePredicateOption:
822        opt = @"[cd]";
823        break;
824      default:
825        //opt = @"[?options?]";
826        break;
827    }
828  return [NSString stringWithFormat: @"%@%@ %@%@ %@",
829           modi, _left, comp, opt, _right];
830}
831
832- (NSPredicate *) predicateWithSubstitutionVariables: (NSDictionary *)variables
833{
834  NSExpression *left;
835  NSExpression *right;
836
837  left = [_left _expressionWithSubstitutionVariables: variables];
838  right = [_right _expressionWithSubstitutionVariables: variables];
839  if (_type == NSCustomSelectorPredicateOperatorType)
840    {
841      return [NSComparisonPredicate predicateWithLeftExpression: left
842                                                rightExpression: right
843                                                 customSelector: _selector];
844    }
845  else
846    {
847      return [NSComparisonPredicate predicateWithLeftExpression: left
848                                                rightExpression: right
849                                                       modifier: _modifier
850                                                           type: _type
851                                                        options: _options];
852    }
853}
854
855#if	GS_USE_ICU == 1
856static BOOL
857GSICUStringMatchesRegex(NSString *string, NSString *regex, NSStringCompareOptions opts)
858{
859  BOOL result = NO;
860  UErrorCode error = 0;
861  uint32_t flags = 0;
862  NSUInteger stringLength = [string length];
863  NSUInteger regexLength = [regex length];
864  unichar *stringBuffer;
865  unichar *regexBuffer;
866  URegularExpression *icuregex = NULL;
867
868  stringBuffer = malloc(stringLength * sizeof(unichar));
869  if (NULL == stringBuffer) { return NO; }
870  regexBuffer = malloc(regexLength * sizeof(unichar));
871  if (NULL == regexBuffer) { free(stringBuffer); return NO; }
872
873  [string getCharacters: stringBuffer range: NSMakeRange(0, stringLength)];
874  [regex getCharacters: regexBuffer range: NSMakeRange(0, regexLength)];
875
876  flags |= UREGEX_DOTALL; // . is supposed to recognize newlines
877  if ((opts & NSCaseInsensitiveSearch) != 0) { flags |= UREGEX_CASE_INSENSITIVE; }
878
879  icuregex = uregex_open(regexBuffer, regexLength, flags, NULL, &error);
880  if (icuregex != NULL && U_SUCCESS(error))
881    {
882      uregex_setText(icuregex, stringBuffer, stringLength, &error);
883      result = uregex_matches(icuregex, 0, &error);
884    }
885  uregex_close(icuregex);
886
887  free(stringBuffer);
888  free(regexBuffer);
889
890  return result;
891}
892#endif
893
894- (double) doubleValueFor: (id)value
895{
896  if ([value isKindOfClass: [NSDate class]])
897    {
898      return [(NSDate*)value timeIntervalSinceReferenceDate];
899    }
900  else
901    {
902      return [value doubleValue];
903    }
904}
905
906- (BOOL) _evaluateLeftValue: (id)leftResult
907		 rightValue: (id)rightResult
908		     object: (id)object
909{
910  unsigned compareOptions = 0;
911  BOOL leftIsNil;
912  BOOL rightIsNil;
913
914  leftIsNil = (leftResult == nil || [leftResult isEqual: [NSNull null]]);
915  rightIsNil = (rightResult == nil || [rightResult isEqual: [NSNull null]]);
916  if (leftIsNil || rightIsNil)
917    {
918      if (leftIsNil == rightIsNil)
919        {
920          /* Both of the values are nil.
921           * The result is YES if equality is requested.
922           */
923          if (NSEqualToPredicateOperatorType == _type
924            || NSLessThanOrEqualToPredicateOperatorType == _type
925            || NSGreaterThanOrEqualToPredicateOperatorType == _type)
926            {
927              return YES;
928            }
929        }
930      else if (NSNotEqualToPredicateOperatorType == _type)
931        {
932          /* One, but not both of the values are nil.
933           * The result is YES if inequality is requested.
934           */
935          return YES;
936        }
937      return NO;
938    }
939
940  // Change predicate options into string options.
941  if (!(_options & NSDiacriticInsensitivePredicateOption))
942    {
943      compareOptions |= NSLiteralSearch;
944    }
945  if (_options & NSCaseInsensitivePredicateOption)
946    {
947      compareOptions |= NSCaseInsensitiveSearch;
948    }
949
950  /* This is a very optimistic implementation,
951   * hoping that the values are of the right type.
952   */
953  switch (_type)
954    {
955      case NSLessThanPredicateOperatorType:
956        {
957          double ld = [self doubleValueFor: leftResult];
958          double rd = [self doubleValueFor: rightResult];
959          return (ld < rd) ? YES : NO;
960        }
961      case NSLessThanOrEqualToPredicateOperatorType:
962        {
963          double ld = [self doubleValueFor: leftResult];
964          double rd = [self doubleValueFor: rightResult];
965          return (ld <= rd) ? YES : NO;
966        }
967      case NSGreaterThanPredicateOperatorType:
968        {
969          double ld = [self doubleValueFor: leftResult];
970          double rd = [self doubleValueFor: rightResult];
971          return (ld > rd) ? YES : NO;
972        }
973      case NSGreaterThanOrEqualToPredicateOperatorType:
974        {
975          double ld = [self doubleValueFor: leftResult];
976          double rd = [self doubleValueFor: rightResult];
977          return (ld >= rd) ? YES : NO;
978        }
979      case NSEqualToPredicateOperatorType:
980	return [leftResult isEqual: rightResult];
981      case NSNotEqualToPredicateOperatorType:
982	return ![leftResult isEqual: rightResult];
983      case NSMatchesPredicateOperatorType:
984#if	GS_USE_ICU == 1
985	return GSICUStringMatchesRegex(leftResult, rightResult, compareOptions);
986#else
987	return [leftResult compare: rightResult options: compareOptions]
988	  == NSOrderedSame ? YES : NO;
989#endif
990      case NSLikePredicateOperatorType:
991#if	GS_USE_ICU == 1
992	{
993	  NSString *regex;
994
995	  /* The right hand is a pattern with '?' meaning match one character,
996	   * and '*' meaning match zero or more characters, so translate that
997	   * into a regex.
998	   */
999	  regex = [rightResult stringByReplacingOccurrencesOfString: @"*"
1000							 withString: @".*"];
1001	  regex = [regex stringByReplacingOccurrencesOfString: @"?"
1002						   withString: @".?"];
1003	  regex = [NSString stringWithFormat: @"^%@$", regex];
1004	  return GSICUStringMatchesRegex(leftResult, regex, compareOptions);
1005	}
1006#else
1007	return [leftResult compare: rightResult options: compareOptions]
1008	  == NSOrderedSame ? YES : NO;
1009#endif
1010      case NSBeginsWithPredicateOperatorType:
1011	{
1012	  NSRange range = NSMakeRange(0, [rightResult length]);
1013
1014	  return ([leftResult compare: rightResult
1015			      options: compareOptions
1016				range: range] == NSOrderedSame ? YES : NO);
1017	}
1018      case NSEndsWithPredicateOperatorType:
1019	{
1020	  NSRange range;
1021          NSUInteger    ll = [leftResult length];
1022          NSUInteger    rl = [rightResult length];
1023
1024          if (ll < rl)
1025            {
1026              return NO;
1027            }
1028	  range = NSMakeRange(ll - rl, rl);
1029	  return ([leftResult compare: rightResult
1030			      options: compareOptions
1031				range: range] == NSOrderedSame ? YES : NO);
1032	}
1033      case NSInPredicateOperatorType:
1034	/* Handle special case where rightResult is a collection
1035	 * and leftResult an element of it.
1036	 */
1037	if (![rightResult isKindOfClass: [NSString class]])
1038	  {
1039	    NSEnumerator *e;
1040	    id value;
1041
1042	    if (![rightResult respondsToSelector: @selector(objectEnumerator)])
1043	      {
1044		[NSException raise: NSInvalidArgumentException
1045			    format: @"The right hand side for an IN operator "
1046		  @"must be a collection"];
1047	      }
1048
1049	    e = [rightResult objectEnumerator];
1050	    while ((value = [e nextObject]))
1051	      {
1052		if ([value isEqual: leftResult])
1053		  return YES;
1054	      }
1055
1056	    return NO;
1057	  }
1058	return ([rightResult rangeOfString: leftResult
1059				   options: compareOptions].location
1060	  != NSNotFound ? YES : NO);
1061      case NSCustomSelectorPredicateOperatorType:
1062	{
1063	  BOOL (*function)(id,SEL,id)
1064            = (BOOL (*)(id,SEL,id))[leftResult methodForSelector: _selector];
1065	  return function(leftResult, _selector, rightResult);
1066	}
1067      default:
1068	return NO;
1069    }
1070}
1071
1072- (BOOL) evaluateWithObject: (id)object
1073{
1074  id leftValue = [_left expressionValueWithObject: object context: nil];
1075  id rightValue = [_right expressionValueWithObject: object context: nil];
1076
1077  if (_modifier == NSDirectPredicateModifier)
1078    {
1079      return [self _evaluateLeftValue: leftValue
1080			   rightValue: rightValue
1081			       object: object];
1082    }
1083  else
1084    {
1085      BOOL result = (_modifier == NSAllPredicateModifier);
1086      NSEnumerator *e;
1087      id value;
1088
1089      if (![leftValue respondsToSelector: @selector(objectEnumerator)])
1090        {
1091          [NSException raise: NSInvalidArgumentException
1092                      format: @"The left hand side for an ALL or ANY operator must be a collection"];
1093        }
1094
1095      e = [leftValue objectEnumerator];
1096      while ((value = [e nextObject]))
1097        {
1098          BOOL eval = [self _evaluateLeftValue: value
1099				    rightValue: rightValue
1100					object: object];
1101          if (eval != result)
1102            return eval;
1103        }
1104
1105      return result;
1106    }
1107}
1108
1109- (id) copyWithZone: (NSZone *)z
1110{
1111  NSComparisonPredicate *copy;
1112
1113  copy = (NSComparisonPredicate *)NSCopyObject(self, 0, z);
1114  copy->_left = [_left copyWithZone: z];
1115  copy->_right = [_right copyWithZone: z];
1116  return copy;
1117}
1118
1119- (Class) classForCoder
1120{
1121  return [NSComparisonPredicate class];
1122}
1123
1124- (void) encodeWithCoder: (NSCoder *)coder
1125{
1126  // FIXME
1127  [self subclassResponsibility: _cmd];
1128}
1129
1130- (id) initWithCoder: (NSCoder *)coder
1131{
1132  // FIXME
1133  [self subclassResponsibility: _cmd];
1134  return self;
1135}
1136
1137@end
1138
1139
1140
1141@implementation NSExpression
1142
1143+ (void) initialize
1144{
1145  if (self == [NSExpression class] && nil == evaluatedObjectExpression)
1146    {
1147      evaluatedObjectExpression = [GSEvaluatedObjectExpression new];
1148    }
1149}
1150
1151+ (NSExpression *) expressionForConstantValue: (id)obj
1152{
1153  GSConstantValueExpression *e;
1154
1155  e = [[GSConstantValueExpression alloc]
1156          initWithExpressionType: NSConstantValueExpressionType];
1157  ASSIGN(e->_obj, obj);
1158  return AUTORELEASE(e);
1159}
1160
1161+ (NSExpression *) expressionForEvaluatedObject
1162{
1163  return evaluatedObjectExpression;
1164}
1165
1166+ (NSExpression *) expressionForFunction: (NSString *)name
1167                               arguments: (NSArray *)args
1168{
1169  GSFunctionExpression	*e;
1170  NSString		*s;
1171
1172  e = [[GSFunctionExpression alloc]
1173    initWithExpressionType: NSFunctionExpressionType];
1174  s = [NSString stringWithFormat: @"_eval_%@:", name];
1175  e->_selector = NSSelectorFromString(s);
1176  if (![e respondsToSelector: e->_selector])
1177    {
1178      [NSException raise: NSInvalidArgumentException
1179                   format: @"Unknown function implementation: %@", name];
1180    }
1181  ASSIGN(e->_function, name);
1182  e->_argc = [args count];
1183  ASSIGN(e->_args, args);
1184  if ([name isEqualToString: @"_add"]) e->_op = @"+";
1185  else if ([name isEqualToString: @"_sub"]) e->_op = @"-";
1186  else if ([name isEqualToString: @"_mul"]) e->_op = @"*";
1187  else if ([name isEqualToString: @"_div"]) e->_op = @"/";
1188  else if ([name isEqualToString: @"_pow"]) e->_op = @"**";
1189  return AUTORELEASE(e);
1190}
1191
1192+ (NSExpression *) expressionForKeyPath: (NSString *)path
1193{
1194  GSKeyPathExpression *e;
1195
1196  if (![path isKindOfClass: [NSString class]])
1197    {
1198      [NSException raise: NSInvalidArgumentException
1199		  format: @"Keypath is not NSString: %@", path];
1200    }
1201  e = [[GSKeyPathExpression alloc]
1202          initWithExpressionType: NSKeyPathExpressionType];
1203  ASSIGN(e->_keyPath, path);
1204  return AUTORELEASE(e);
1205}
1206
1207+ (NSExpression *) expressionForVariable: (NSString *)string
1208{
1209  GSVariableExpression *e;
1210
1211  e = [[GSVariableExpression alloc]
1212          initWithExpressionType: NSVariableExpressionType];
1213  ASSIGN(e->_variable, string);
1214  return AUTORELEASE(e);
1215}
1216
1217- (id) initWithExpressionType: (NSExpressionType)type
1218{
1219  if ((self = [super init]) != nil)
1220    {
1221      _type = type;
1222    }
1223  return self;
1224}
1225
1226- (id) copyWithZone: (NSZone *)z
1227{
1228  return NSCopyObject(self, 0, z);
1229}
1230
1231- (NSArray *) arguments
1232{
1233  [self subclassResponsibility: _cmd];
1234  return nil;
1235}
1236
1237- (id) constantValue
1238{
1239  [self subclassResponsibility: _cmd];
1240  return nil;
1241}
1242
1243- (NSString *) description
1244{
1245  [self subclassResponsibility: _cmd];
1246  return nil;
1247}
1248
1249- (NSExpressionType) expressionType
1250{
1251  return _type;
1252}
1253
1254- (id) expressionValueWithObject: (id)object
1255			 context: (NSMutableDictionary *)context
1256{
1257  [self subclassResponsibility: _cmd];
1258  return nil;
1259}
1260
1261- (NSString *) function
1262{
1263  [self subclassResponsibility: _cmd];
1264  return nil;
1265}
1266
1267- (NSString *) keyPath
1268{
1269  [self subclassResponsibility: _cmd];
1270  return nil;
1271}
1272
1273- (NSExpression *) operand
1274{
1275  [self subclassResponsibility: _cmd];
1276  return nil;
1277}
1278
1279- (NSString *) variable
1280{
1281  [self subclassResponsibility: _cmd];
1282  return nil;
1283}
1284
1285- (Class) classForCoder
1286{
1287  return [NSExpression class];
1288}
1289
1290- (void) encodeWithCoder: (NSCoder *)coder
1291{
1292  // FIXME
1293  [self subclassResponsibility: _cmd];
1294}
1295
1296- (id) initWithCoder: (NSCoder *)coder
1297{
1298  // FIXME
1299  [self subclassResponsibility: _cmd];
1300  return nil;
1301}
1302
1303- (id) _expressionWithSubstitutionVariables: (NSDictionary *)variables
1304{
1305  [self subclassResponsibility: _cmd];
1306  return nil;
1307}
1308
1309@end
1310
1311@implementation GSConstantValueExpression
1312
1313- (id) constantValue
1314{
1315  return _obj;
1316}
1317
1318- (NSString *) description
1319{
1320  if ([_obj isKindOfClass: [NSString class]])
1321    {
1322      NSMutableString	*result = nil;
1323
1324      /* Quote the result string as necessary.
1325       */
1326      GSPropertyListMake(_obj, nil, NO, YES, 2, &result);
1327      return result;
1328    }
1329  else if ([_obj isKindOfClass: [NSDate class]])
1330    {
1331      return [NSString stringWithFormat: @"CAST(%15.6f, \"NSDate\")",
1332                       [(NSDate*)_obj timeIntervalSinceReferenceDate]];
1333    }
1334  return [_obj description];
1335}
1336
1337- (id) expressionValueWithObject: (id)object
1338			 context: (NSMutableDictionary *)context
1339{
1340  return _obj;
1341}
1342
1343- (void) dealloc
1344{
1345  RELEASE(_obj);
1346  [super dealloc];
1347}
1348
1349- (id) copyWithZone: (NSZone*)zone
1350{
1351  GSConstantValueExpression *copy;
1352
1353  copy = (GSConstantValueExpression *)[super copyWithZone: zone];
1354  copy->_obj = [_obj copyWithZone: zone];
1355  return copy;
1356}
1357
1358- (id) _expressionWithSubstitutionVariables: (NSDictionary *)variables
1359{
1360  return self;
1361}
1362
1363@end
1364
1365@implementation GSEvaluatedObjectExpression
1366
1367- (NSString *) description
1368{
1369  return @"SELF";
1370}
1371
1372- (id) expressionValueWithObject: (id)object
1373			 context: (NSMutableDictionary *)context
1374{
1375  return object;
1376}
1377
1378- (id) _expressionWithSubstitutionVariables: (NSDictionary *)variables
1379{
1380  return self;
1381}
1382
1383- (NSString *) keyPath
1384{
1385  return @"SELF";
1386}
1387@end
1388
1389@implementation GSVariableExpression
1390
1391- (NSString *) description
1392{
1393  return [NSString stringWithFormat: @"$%@", _variable];
1394}
1395
1396- (id) expressionValueWithObject: (id)object
1397			 context: (NSMutableDictionary *)context
1398{
1399  return [context objectForKey: _variable];
1400}
1401
1402- (NSString *) variable
1403{
1404  return _variable;
1405}
1406
1407- (void) dealloc;
1408{
1409  RELEASE(_variable);
1410  [super dealloc];
1411}
1412
1413- (id) copyWithZone: (NSZone*)zone
1414{
1415  GSVariableExpression *copy;
1416
1417  copy = (GSVariableExpression *)[super copyWithZone: zone];
1418  copy->_variable = [_variable copyWithZone: zone];
1419  return copy;
1420}
1421
1422- (id) _expressionWithSubstitutionVariables: (NSDictionary *)variables
1423{
1424  id result = [variables objectForKey: _variable];
1425
1426  if (result != nil)
1427    {
1428      return [NSExpression expressionForConstantValue: result];
1429    }
1430  else
1431    {
1432      return self;
1433    }
1434}
1435
1436@end
1437
1438@implementation GSKeyPathExpression
1439
1440- (NSString *) description
1441{
1442  return _keyPath;
1443}
1444
1445- (id) expressionValueWithObject: (id)object
1446			 context: (NSMutableDictionary *)context
1447{
1448  return [object valueForKeyPath: _keyPath];
1449}
1450
1451- (NSString *) keyPath
1452{
1453  return _keyPath;
1454}
1455
1456- (void) dealloc;
1457{
1458  RELEASE(_keyPath);
1459  [super dealloc];
1460}
1461
1462- (id) copyWithZone: (NSZone*)zone
1463{
1464  GSKeyPathExpression *copy;
1465
1466  copy = (GSKeyPathExpression *)[super copyWithZone: zone];
1467  copy->_keyPath = [_keyPath copyWithZone: zone];
1468  return copy;
1469}
1470
1471- (id) _expressionWithSubstitutionVariables: (NSDictionary *)variables
1472{
1473  return self;
1474}
1475
1476@end
1477
1478@implementation GSFunctionExpression
1479
1480- (NSArray *) arguments
1481{
1482  return _args;
1483}
1484
1485- (NSString *) description
1486{
1487  if (nil != _op && 1 == [_args count])
1488    {
1489      GSFunctionExpression      *a0 = [_args objectAtIndex: 0];
1490
1491      if (YES == [a0 isKindOfClass: [self class]] && nil != a0->_op)
1492        {
1493          return [NSString stringWithFormat: @"%@(%@)", _op, a0];
1494        }
1495      return [NSString stringWithFormat: @"%@%@", _op, a0];
1496    }
1497
1498  if (nil != _op)
1499    {
1500      GSFunctionExpression      *a0 = [_args objectAtIndex: 0];
1501      GSFunctionExpression      *a1 = [_args objectAtIndex: 1];
1502
1503      if (YES == [a0 isKindOfClass: [self class]] && nil != a0->_op)
1504        {
1505          if (YES == [a1 isKindOfClass: [self class]] && nil != a1->_op)
1506            {
1507              return [NSString stringWithFormat: @"(%@) %@ (%@)", a0, _op, a1];
1508            }
1509          return [NSString stringWithFormat: @"(%@) %@ %@", a0, _op, a1];
1510        }
1511
1512      if (YES == [a1 isKindOfClass: [self class]] && nil != a1->_op)
1513        {
1514          return [NSString stringWithFormat: @"%@ %@ (%@)", a0, _op, a1];
1515        }
1516
1517      return [NSString stringWithFormat: @"%@ %@ %@", a0, _op, a1];
1518    }
1519  return [NSString stringWithFormat: @"%@(%@)", [self function], _args];
1520}
1521
1522- (NSString *) function
1523{
1524  return _function;
1525}
1526
1527- (NSString *) keyPath
1528{
1529  return nil;
1530}
1531
1532- (id) expressionValueWithObject: (id)object
1533			 context: (NSMutableDictionary *)context
1534{
1535  // temporary space
1536  NSMutableArray	*eargs = [NSMutableArray arrayWithCapacity: _argc];
1537  unsigned int i;
1538
1539  for (i = 0; i < _argc; i++)
1540    {
1541      [eargs addObject: [[_args objectAtIndex: i]
1542        expressionValueWithObject: object context: context]];
1543    }
1544  // apply method selector
1545  return [self performSelector: _selector
1546                    withObject: eargs];
1547}
1548
1549- (void) dealloc;
1550{
1551  RELEASE(_args);
1552  RELEASE(_function);
1553  [super dealloc];
1554}
1555
1556- (id) copyWithZone: (NSZone*)zone
1557{
1558  GSFunctionExpression *copy;
1559
1560  copy = (GSFunctionExpression *)[super copyWithZone: zone];
1561  copy->_function = [_function copyWithZone: zone];
1562  copy->_args = [_args copyWithZone: zone];
1563  return copy;
1564}
1565
1566- (NSEnumerator*) _enum: (NSArray *)expressions
1567{
1568  id    o;
1569
1570  /* Check to see if this is aggregating over a collection.
1571   */
1572  if (1 == _argc && [(o = [expressions lastObject])
1573    respondsToSelector: @selector(objectEnumerator)])
1574    {
1575      return [o objectEnumerator];
1576    }
1577  return [expressions objectEnumerator];
1578}
1579
1580- (id) _expressionWithSubstitutionVariables: (NSDictionary *)variables
1581{
1582  NSMutableArray *args = [NSMutableArray arrayWithCapacity: _argc];
1583  unsigned int i;
1584
1585  for (i = 0; i < _argc; i++)
1586    {
1587      [args addObject: [[_args objectAtIndex: i]
1588                           _expressionWithSubstitutionVariables: variables]];
1589    }
1590
1591   return [NSExpression expressionForFunction: _function arguments: args];
1592}
1593
1594- (id) _eval__chs: (NSArray *)expressions
1595{
1596  return [NSNumber numberWithInt: -[[expressions objectAtIndex: 0] intValue]];
1597}
1598
1599- (id) _eval__first: (NSArray *)expressions
1600{
1601  return [[expressions objectAtIndex: 0] objectAtIndex: 0];
1602}
1603
1604- (id) _eval__last: (NSArray *)expressions
1605{
1606  return [[expressions objectAtIndex: 0] lastObject];
1607}
1608
1609- (id) _eval__index: (NSArray *)expressions
1610{
1611  id left = [expressions objectAtIndex: 0];
1612  id right = [expressions objectAtIndex: 1];
1613
1614  if ([left isKindOfClass: [NSDictionary class]])
1615    {
1616      return [left objectForKey: right];
1617    }
1618  else
1619    {
1620      // raises exception if invalid
1621      return [left objectAtIndex: [right unsignedIntValue]];
1622    }
1623}
1624
1625- (id) _eval__pow: (NSArray *)expressions
1626{
1627  id left = [expressions objectAtIndex: 0];
1628  id right = [expressions objectAtIndex: 1];
1629
1630  return [NSNumber numberWithDouble:
1631    pow([left doubleValue], [right doubleValue])];
1632}
1633
1634- (id) _eval__mul: (NSArray *)expressions
1635{
1636  id left = [expressions objectAtIndex: 0];
1637  id right = [expressions objectAtIndex: 1];
1638
1639  return [NSNumber numberWithDouble: [left doubleValue] * [right doubleValue]];
1640}
1641
1642- (id) _eval__div: (NSArray *)expressions
1643{
1644  id left = [expressions objectAtIndex: 0];
1645  id right = [expressions objectAtIndex: 1];
1646
1647  return [NSNumber numberWithDouble: [left doubleValue] / [right doubleValue]];
1648}
1649
1650- (id) _eval__add: (NSArray *)expressions
1651{
1652  id left = [expressions objectAtIndex: 0];
1653  id right = [expressions objectAtIndex: 1];
1654
1655  return [NSNumber numberWithDouble: [left doubleValue] + [right doubleValue]];
1656}
1657
1658- (id) _eval__sub: (NSArray *)expressions
1659{
1660  id left = [expressions objectAtIndex: 0];
1661  id right = [expressions objectAtIndex: 1];
1662
1663  return [NSNumber numberWithDouble: [left doubleValue] - [right doubleValue]];
1664}
1665
1666- (id) _eval_count: (NSArray *)expressions
1667{
1668  NSAssert(_argc == 1, NSInternalInconsistencyException);
1669  return [NSNumber numberWithUnsignedInt:
1670    [[expressions objectAtIndex: 0] count]];
1671}
1672
1673- (id) _eval_avg: (NSArray *)expressions
1674{
1675  NSEnumerator  *e = [self _enum: expressions];
1676  double        sum = 0.0;
1677  unsigned      count = 0;
1678  id            o;
1679
1680  while (nil != (o = [e nextObject]))
1681    {
1682      sum += [o doubleValue];
1683      count++;
1684    }
1685  if (count == 0)
1686    {
1687      return [NSNumber numberWithDouble: 0.0];
1688    }
1689  return [NSNumber numberWithDouble: sum / count];
1690}
1691
1692- (id) _eval_max: (NSArray *)expressions
1693{
1694  NSEnumerator  *e = [self _enum: expressions];
1695  id            o = [e nextObject];
1696  double        max = (nil == o) ? 0.0 : [o doubleValue];
1697  double        cur;
1698
1699  while (nil != (o = [e nextObject]))
1700    {
1701      cur = [o doubleValue];
1702      if (max < cur)
1703        {
1704          max = cur;
1705        }
1706    }
1707  return [NSNumber numberWithDouble: max];
1708}
1709
1710- (id) _eval_min: (NSArray *)expressions
1711{
1712  NSEnumerator  *e = [self _enum: expressions];
1713  id            o = [e nextObject];
1714  double        min = (nil == o ? 0.0 : [o doubleValue]);
1715  double        cur;
1716
1717  while (nil != (o = [e nextObject]))
1718    {
1719      cur = [o doubleValue];
1720      if (min > cur)
1721        {
1722          min = cur;
1723        }
1724    }
1725  return [NSNumber numberWithDouble: min];
1726}
1727
1728- (id) _eval_sum: (NSArray *)expressions
1729{
1730  NSEnumerator  *e = [self _enum: expressions];
1731  double        sum = 0.0;
1732  id            o;
1733
1734  while (nil != (o = [e nextObject]))
1735    {
1736      sum += [o doubleValue];
1737    }
1738  return [NSNumber numberWithDouble: sum];
1739}
1740
1741- (id) _eval_CAST: (NSArray *)expressions
1742{
1743  id left = [expressions objectAtIndex: 0];
1744  id right = [expressions objectAtIndex: 1];
1745
1746  if ([right isEqualToString: @"NSDate"])
1747    {
1748      return [[NSDate alloc] initWithTimeIntervalSinceReferenceDate: [left doubleValue]];
1749    }
1750
1751  NSLog(@"Cast to unknown type %@", right);
1752  return nil;
1753}
1754
1755// add arithmetic functions: average, median, mode, stddev, sqrt, log, ln, exp, floor, ceiling, abs, trunc, random, randomn, now
1756
1757@end
1758
1759
1760
1761@implementation NSArray (NSPredicate)
1762
1763- (NSArray *) filteredArrayUsingPredicate: (NSPredicate *)predicate
1764{
1765  NSMutableArray	*result;
1766  NSEnumerator		*e = [self objectEnumerator];
1767  id			object;
1768
1769  result = [NSMutableArray arrayWithCapacity: [self count]];
1770  while ((object = [e nextObject]) != nil)
1771    {
1772      if ([predicate evaluateWithObject: object] == YES)
1773        {
1774          [result addObject: object];  // passes filter
1775        }
1776    }
1777  return GS_IMMUTABLE(result);
1778}
1779
1780@end
1781
1782@implementation NSMutableArray (NSPredicate)
1783
1784- (void) filterUsingPredicate: (NSPredicate *)predicate
1785{
1786  unsigned	count = [self count];
1787
1788  while (count-- > 0)
1789    {
1790      id	object = [self objectAtIndex: count];
1791
1792      if ([predicate evaluateWithObject: object] == NO)
1793        {
1794          [self removeObjectAtIndex: count];
1795        }
1796    }
1797}
1798
1799@end
1800
1801@implementation NSSet (NSPredicate)
1802
1803- (NSSet *) filteredSetUsingPredicate: (NSPredicate *)predicate
1804{
1805  NSMutableSet	*result;
1806  NSEnumerator	*e = [self objectEnumerator];
1807  id		object;
1808
1809  result = [NSMutableSet setWithCapacity: [self count]];
1810  while ((object = [e nextObject]) != nil)
1811    {
1812      if ([predicate evaluateWithObject: object] == YES)
1813        {
1814          [result addObject: object];  // passes filter
1815        }
1816    }
1817  return GS_IMMUTABLE(result);
1818}
1819
1820@end
1821
1822@implementation NSMutableSet (NSPredicate)
1823
1824- (void) filterUsingPredicate: (NSPredicate *)predicate
1825{
1826  NSMutableSet	*rejected;
1827  NSEnumerator	*e = [self objectEnumerator];
1828  id		object;
1829
1830  rejected = [NSMutableSet setWithCapacity: [self count]];
1831  while ((object = [e nextObject]) != nil)
1832    {
1833      if ([predicate evaluateWithObject: object] == NO)
1834        {
1835          [rejected addObject: object];
1836        }
1837    }
1838  [self minusSet: rejected];
1839}
1840
1841@end
1842
1843
1844
1845@implementation GSPredicateScanner
1846
1847- (id) initWithString: (NSString*)format
1848                 args: (NSArray*)args
1849{
1850  self = [super initWithString: format];
1851  if (self != nil)
1852    {
1853      _args = [args objectEnumerator];
1854    }
1855  return self;
1856}
1857
1858- (id) nextArg
1859{
1860  return [_args nextObject];
1861}
1862
1863- (BOOL) scanPredicateKeyword: (NSString *)key
1864{
1865  // save to back up
1866  unsigned loc = [self scanLocation];
1867  unichar c;
1868
1869  [self setCaseSensitive: NO];
1870  if (![self scanString: key intoString: NULL])
1871    {
1872      // no match
1873      return NO;
1874    }
1875
1876  if ([self isAtEnd])
1877    {
1878       // ok
1879      return YES;
1880    }
1881
1882  // Does the next character still belong to the token?
1883  c = [[self string] characterAtIndex: [self scanLocation]];
1884  if (![[NSCharacterSet alphanumericCharacterSet] characterIsMember: c])
1885    {
1886      // ok
1887      return YES;
1888    }
1889
1890  // back up
1891  [self setScanLocation: loc];
1892  // no match
1893  return NO;
1894}
1895
1896- (NSPredicate *) parse
1897{
1898  NSPredicate *r = nil;
1899
1900  NS_DURING
1901    {
1902      r = [self parsePredicate];
1903    }
1904  NS_HANDLER
1905    {
1906      NSLog(@"Parsing failed for %@ with %@", [self string], localException);
1907      [localException raise];
1908    }
1909  NS_ENDHANDLER
1910
1911  if (![self isAtEnd])
1912    {
1913      [NSException raise: NSInvalidArgumentException
1914		  format: @"Format string contains extra characters: \"%@\"",
1915		   [self string]];
1916    }
1917  return r;
1918}
1919
1920- (NSPredicate *) parsePredicate
1921{
1922  return [self parseAnd];
1923}
1924
1925- (NSPredicate *) parseAnd
1926{
1927  NSPredicate	*l = [self parseOr];
1928
1929  while ([self scanPredicateKeyword: @"AND"]
1930    || [self scanPredicateKeyword: @"&&"])
1931    {
1932      NSPredicate	*r = [self parseOr];
1933
1934      if ([r isKindOfClass: [NSCompoundPredicate class]]
1935        && [(NSCompoundPredicate *)r compoundPredicateType]
1936        == NSAndPredicateType)
1937        {
1938          NSCompoundPredicate   *right = (NSCompoundPredicate*)r;
1939
1940          // merge
1941          if ([l isKindOfClass:[NSCompoundPredicate class]]
1942            && [(NSCompoundPredicate *)l compoundPredicateType]
1943            == NSAndPredicateType)
1944            {
1945              NSCompoundPredicate       *left;
1946              NSMutableArray            *subs;
1947
1948              left = (NSCompoundPredicate*)l;
1949              subs = [[left subpredicates] mutableCopy];
1950              [subs addObjectsFromArray: [right subpredicates]];
1951              l = [NSCompoundPredicate andPredicateWithSubpredicates: subs];
1952              [subs release];
1953            }
1954          else
1955            {
1956              NSMutableArray            *subs;
1957
1958              subs = [[right subpredicates] mutableCopy];
1959              [subs insertObject: l atIndex: 0];
1960              l = [NSCompoundPredicate andPredicateWithSubpredicates: subs];
1961              [subs release];
1962            }
1963        }
1964      else if ([l isKindOfClass: [NSCompoundPredicate class]]
1965        && [(NSCompoundPredicate *)l compoundPredicateType]
1966        == NSAndPredicateType)
1967        {
1968          NSCompoundPredicate   *left;
1969          NSMutableArray        *subs;
1970
1971          left = (NSCompoundPredicate*)l;
1972          subs = [[left subpredicates] mutableCopy];
1973          [subs addObject: r];
1974          l = [NSCompoundPredicate andPredicateWithSubpredicates: subs];
1975          [subs release];
1976        }
1977      else
1978        {
1979          l = [NSCompoundPredicate andPredicateWithSubpredicates:
1980            [NSArray arrayWithObjects: l, r, nil]];
1981        }
1982    }
1983  return l;
1984}
1985
1986- (NSPredicate *) parseNot
1987{
1988  if ([self scanString: @"(" intoString: NULL])
1989    {
1990      NSPredicate *r = [self parsePredicate];
1991
1992      if (![self scanString: @")" intoString: NULL])
1993        {
1994          [NSException raise: NSInvalidArgumentException
1995                      format: @"Missing ) in compound predicate"];
1996        }
1997      return r;
1998    }
1999
2000  if ([self scanPredicateKeyword: @"NOT"] || [self scanPredicateKeyword: @"!"])
2001    {
2002      // -> NOT NOT x or NOT (y)
2003      return [NSCompoundPredicate
2004                 notPredicateWithSubpredicate: [self parseNot]];
2005    }
2006
2007  if ([self scanPredicateKeyword: @"TRUEPREDICATE"])
2008    {
2009      return [NSPredicate predicateWithValue: YES];
2010    }
2011  if ([self scanPredicateKeyword: @"FALSEPREDICATE"])
2012    {
2013      return [NSPredicate predicateWithValue: NO];
2014    }
2015
2016  return [self parseComparison];
2017}
2018
2019- (NSPredicate *) parseOr
2020{
2021  NSPredicate	*l = [self parseNot];
2022
2023  while ([self scanPredicateKeyword: @"OR"]
2024    || [self scanPredicateKeyword: @"||"])
2025    {
2026      NSPredicate	*r = [self parseNot];
2027
2028      if ([r isKindOfClass: [NSCompoundPredicate class]]
2029        && [(NSCompoundPredicate *)r compoundPredicateType]
2030        == NSOrPredicateType)
2031        {
2032          NSCompoundPredicate   *right = (NSCompoundPredicate*)r;
2033
2034          // merge
2035          if ([l isKindOfClass: [NSCompoundPredicate class]]
2036            && [(NSCompoundPredicate *)l compoundPredicateType]
2037            == NSOrPredicateType)
2038            {
2039              NSCompoundPredicate       *left = (NSCompoundPredicate*)l;
2040              NSMutableArray            *subs;
2041
2042              subs = [[left subpredicates] mutableCopy];
2043              [subs addObjectsFromArray: [right subpredicates]];
2044              l = [NSCompoundPredicate orPredicateWithSubpredicates: subs];
2045              [subs release];
2046            }
2047          else
2048            {
2049              NSMutableArray            *subs;
2050
2051              subs = [[right subpredicates] mutableCopy];
2052              [subs insertObject: l atIndex: 0];
2053              l = [NSCompoundPredicate orPredicateWithSubpredicates: subs];
2054              [subs release];
2055            }
2056        }
2057      else if ([l isKindOfClass: [NSCompoundPredicate class]]
2058        && [(NSCompoundPredicate *)l compoundPredicateType]
2059        == NSOrPredicateType)
2060        {
2061          NSCompoundPredicate   *left = (NSCompoundPredicate*)l;
2062          NSMutableArray        *subs;
2063
2064          subs = [[left subpredicates] mutableCopy];
2065          [subs addObject:r];
2066          l = [NSCompoundPredicate orPredicateWithSubpredicates: subs];
2067          [subs release];
2068        }
2069      else
2070        {
2071          l = [NSCompoundPredicate orPredicateWithSubpredicates:
2072            [NSArray arrayWithObjects: l, r, nil]];
2073        }
2074    }
2075  return l;
2076}
2077
2078- (NSPredicate *) parseComparison
2079{
2080  // there must always be a comparison
2081  NSComparisonPredicateModifier modifier = NSDirectPredicateModifier;
2082  NSPredicateOperatorType type = 0;
2083  unsigned opts = 0;
2084  NSExpression *left;
2085  NSExpression *right;
2086  NSPredicate *p;
2087  BOOL negate = NO;
2088  BOOL swap = NO;
2089
2090  if ([self scanPredicateKeyword: @"ANY"])
2091    {
2092      modifier = NSAnyPredicateModifier;
2093    }
2094  else if ([self scanPredicateKeyword: @"ALL"])
2095    {
2096      modifier = NSAllPredicateModifier;
2097    }
2098  else if ([self scanPredicateKeyword: @"NONE"])
2099    {
2100      modifier = NSAnyPredicateModifier;
2101      negate = YES;
2102    }
2103  else if ([self scanPredicateKeyword: @"SOME"])
2104    {
2105      modifier = NSAllPredicateModifier;
2106      negate = YES;
2107    }
2108
2109  left = [self parseExpression];
2110  if ([self scanString: @"!=" intoString: NULL]
2111    || [self scanString: @"<>" intoString: NULL])
2112    {
2113      type = NSNotEqualToPredicateOperatorType;
2114    }
2115  else if ([self scanString: @"<=" intoString: NULL]
2116    || [self scanString: @"=<" intoString: NULL])
2117    {
2118      type = NSLessThanOrEqualToPredicateOperatorType;
2119    }
2120  else if ([self scanString: @">=" intoString: NULL]
2121    || [self scanString: @"=>" intoString: NULL])
2122    {
2123      type = NSGreaterThanOrEqualToPredicateOperatorType;
2124    }
2125  else if ([self scanString: @"<" intoString: NULL])
2126    {
2127      type = NSLessThanPredicateOperatorType;
2128    }
2129  else if ([self scanString: @">" intoString: NULL])
2130    {
2131      type = NSGreaterThanPredicateOperatorType;
2132    }
2133  else if ([self scanString: @"==" intoString: NULL]
2134    || [self scanString: @"=" intoString: NULL])
2135    {
2136      type = NSEqualToPredicateOperatorType;
2137    }
2138  else if ([self scanPredicateKeyword: @"MATCHES"])
2139    {
2140      type = NSMatchesPredicateOperatorType;
2141    }
2142  else if ([self scanPredicateKeyword: @"LIKE"])
2143    {
2144      type = NSLikePredicateOperatorType;
2145    }
2146  else if ([self scanPredicateKeyword: @"BEGINSWITH"])
2147    {
2148      type = NSBeginsWithPredicateOperatorType;
2149    }
2150  else if ([self scanPredicateKeyword: @"ENDSWITH"])
2151    {
2152      type = NSEndsWithPredicateOperatorType;
2153    }
2154  else if ([self scanPredicateKeyword: @"IN"])
2155    {
2156      type = NSInPredicateOperatorType;
2157    }
2158  else if ([self scanPredicateKeyword: @"CONTAINS"])
2159    {
2160      type = NSInPredicateOperatorType;
2161      swap = YES;
2162    }
2163  else if ([self scanPredicateKeyword: @"BETWEEN"])
2164    {
2165      // Requires special handling to transfer into AND of
2166      // two normal comparison predicates
2167      NSExpression *exp = [self parseSimpleExpression];
2168      NSArray *a = (NSArray *)[exp constantValue];
2169      NSNumber *lower, *upper;
2170      NSExpression *lexp, *uexp;
2171      NSPredicate *lp, *up;
2172
2173      if (![a isKindOfClass: [NSArray class]])
2174        {
2175          [NSException raise: NSInvalidArgumentException
2176                       format: @"BETWEEN operator requires array argument"];
2177        }
2178
2179      lower = [a objectAtIndex: 0];
2180      upper = [a objectAtIndex: 1];
2181      lexp = [NSExpression expressionForConstantValue: lower];
2182      uexp = [NSExpression expressionForConstantValue: upper];
2183      lp = [NSComparisonPredicate predicateWithLeftExpression: left
2184                                  rightExpression: lexp
2185                                  modifier: modifier
2186                                  type: NSGreaterThanPredicateOperatorType
2187                                  options: opts];
2188      up = [NSComparisonPredicate predicateWithLeftExpression: left
2189                                  rightExpression: uexp
2190                                  modifier: modifier
2191                                  type: NSLessThanPredicateOperatorType
2192                                  options: opts];
2193      return [NSCompoundPredicate andPredicateWithSubpredicates:
2194                                       [NSArray arrayWithObjects: lp, up, nil]];
2195    }
2196  else
2197    {
2198      [NSException raise: NSInvalidArgumentException
2199                   format: @"Invalid comparison predicate: %@",
2200		   [[self string] substringFromIndex: [self scanLocation]]];
2201    }
2202
2203  if ([self scanString: @"[cd]" intoString: NULL])
2204    {
2205      opts = NSCaseInsensitivePredicateOption
2206        | NSDiacriticInsensitivePredicateOption;
2207    }
2208  else if ([self scanString: @"[c]" intoString: NULL])
2209    {
2210      opts = NSCaseInsensitivePredicateOption;
2211    }
2212  else if ([self scanString: @"[d]" intoString: NULL])
2213    {
2214      opts = NSDiacriticInsensitivePredicateOption;
2215    }
2216
2217  right = [self parseExpression];
2218  if (swap == YES)
2219    {
2220      NSExpression      *tmp = left;
2221
2222      left = right;
2223      right = tmp;
2224    }
2225
2226  p = [NSComparisonPredicate predicateWithLeftExpression: left
2227                             rightExpression: right
2228                             modifier: modifier
2229                             type: type
2230                             options: opts];
2231
2232  return negate ? [NSCompoundPredicate notPredicateWithSubpredicate: p] : p;
2233}
2234
2235- (NSExpression *) parseExpression
2236{
2237//  return [self parseAdditionExpression];
2238  return [self parseBinaryExpression];
2239}
2240
2241- (NSExpression *) parseIdentifierExpression
2242{
2243  static NSCharacterSet *_identifier;
2244  NSString      *ident;
2245
2246  // skip # as prefix if present (reserved words)
2247  (void)[self scanString: @"#" intoString: NULL];
2248  if (!_identifier)
2249    {
2250      ASSIGN(_identifier, [NSCharacterSet characterSetWithCharactersInString:
2251	 @"_$abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"]);
2252    }
2253
2254  if (![self scanCharactersFromSet: _identifier intoString: &ident])
2255    {
2256      [NSException raise: NSInvalidArgumentException
2257                  format: @"Missing identifier: %@",
2258                   [[self string] substringFromIndex: [self scanLocation]]];
2259    }
2260
2261  return [NSExpression expressionForKeyPath: ident];
2262}
2263
2264- (NSExpression *) parseSimpleExpression
2265{
2266  unsigned      location;
2267  double        dbl;
2268
2269  if ([self scanDouble: &dbl])
2270    {
2271      return [NSExpression expressionForConstantValue:
2272                               [NSNumber numberWithDouble: dbl]];
2273    }
2274
2275  // FIXME: handle integer, hex constants, 0x 0o 0b
2276  if ([self scanString: @"-" intoString: NULL])
2277    {
2278      return [NSExpression expressionForFunction: @"_chs"
2279        arguments: [NSArray arrayWithObject: [self parseExpression]]];
2280    }
2281
2282  if ([self scanString: @"(" intoString: NULL])
2283    {
2284      NSExpression *arg = [self parseExpression];
2285
2286      if (![self scanString: @")" intoString: NULL])
2287        {
2288          [NSException raise: NSInvalidArgumentException
2289                       format: @"Missing ) in expression"];
2290        }
2291      return arg;
2292    }
2293
2294  if ([self scanString: @"{" intoString: NULL])
2295    {
2296      NSMutableArray *a = [NSMutableArray arrayWithCapacity: 10];
2297
2298      if ([self scanString: @"}" intoString: NULL])
2299        {
2300          // empty
2301          return [NSExpression expressionForConstantValue: a];
2302        }
2303      // first element
2304      [a addObject: [self parseExpression]];
2305      while ([self scanString: @"," intoString: NULL])
2306        {
2307          // more elements
2308          [a addObject: [self parseExpression]];
2309        }
2310
2311      if (![self scanString: @"}" intoString: NULL])
2312        {
2313          [NSException raise: NSInvalidArgumentException
2314                      format: @"Missing } in aggregate"];
2315        }
2316      return [NSExpression expressionForConstantValue: a];
2317    }
2318
2319  if ([self scanPredicateKeyword: @"NULL"]
2320    || [self scanPredicateKeyword: @"NIL"])
2321    {
2322      return [NSExpression expressionForConstantValue: [NSNull null]];
2323    }
2324  if ([self scanPredicateKeyword: @"TRUE"]
2325    || [self scanPredicateKeyword: @"YES"])
2326    {
2327      return [NSExpression expressionForConstantValue:
2328        [NSNumber numberWithBool: YES]];
2329    }
2330  if ([self scanPredicateKeyword: @"FALSE"]
2331    || [self scanPredicateKeyword: @"NO"])
2332    {
2333      return [NSExpression expressionForConstantValue:
2334        [NSNumber numberWithBool: NO]];
2335    }
2336  if ([self scanPredicateKeyword: @"SELF"])
2337    {
2338      return [NSExpression expressionForEvaluatedObject];
2339    }
2340  if ([self scanString: @"$" intoString: NULL])
2341    {
2342      // variable
2343      NSExpression *var = [self parseIdentifierExpression];
2344
2345      if (![var keyPath])
2346        {
2347          [NSException raise: NSInvalidArgumentException
2348                      format: @"Invalid variable identifier: %@", var];
2349        }
2350      return [NSExpression expressionForVariable: [var keyPath]];
2351    }
2352
2353  location = [self scanLocation];
2354
2355  if ([self scanString: @"%" intoString: NULL])
2356    {
2357      if ([self isAtEnd] == NO)
2358        {
2359          unichar   c = [[self string] characterAtIndex: [self scanLocation]];
2360
2361          switch (c)
2362            {
2363              case '%':                         // '%%' is treated as '%'
2364                location = [self scanLocation];
2365                break;
2366
2367              case 'K':
2368                [self setScanLocation: [self scanLocation] + 1];
2369                return [NSExpression expressionForKeyPath:
2370                  [self nextArg]];
2371
2372              case '@':
2373              case 'c':
2374              case 'C':
2375              case 'd':
2376              case 'D':
2377              case 'i':
2378              case 'o':
2379              case 'O':
2380              case 'u':
2381              case 'U':
2382              case 'x':
2383              case 'X':
2384              case 'e':
2385              case 'E':
2386              case 'f':
2387              case 'g':
2388              case 'G':
2389                [self setScanLocation: [self scanLocation] + 1];
2390                return [NSExpression expressionForConstantValue:
2391                  [self nextArg]];
2392
2393              case 'h':
2394                (void)[self scanString: @"h" intoString: NULL];
2395                if ([self isAtEnd] == NO)
2396                  {
2397                    c = [[self string] characterAtIndex: [self scanLocation]];
2398                    if (c == 'i' || c == 'u')
2399                      {
2400                        [self setScanLocation: [self scanLocation] + 1];
2401                        return [NSExpression expressionForConstantValue:
2402                          [self nextArg]];
2403                      }
2404                  }
2405                break;
2406
2407              case 'q':
2408                (void)[self scanString: @"q" intoString: NULL];
2409                if ([self isAtEnd] == NO)
2410                  {
2411                    c = [[self string] characterAtIndex: [self scanLocation]];
2412                    if (c == 'i' || c == 'u' || c == 'x' || c == 'X')
2413                      {
2414                        [self setScanLocation: [self scanLocation] + 1];
2415                        return [NSExpression expressionForConstantValue:
2416                          [self nextArg]];
2417                      }
2418                  }
2419                break;
2420            }
2421        }
2422
2423      [self setScanLocation: location];
2424    }
2425
2426  if ([self scanString: @"\"" intoString: NULL])
2427    {
2428      NSCharacterSet	*skip = [self charactersToBeSkipped];
2429      NSString *str = nil;
2430
2431      [self setCharactersToBeSkipped: nil];
2432      if ([self scanUpToString: @"\"" intoString: &str] == NO)
2433	{
2434	  [self setCharactersToBeSkipped: skip];
2435          [NSException raise: NSInvalidArgumentException
2436                      format: @"Invalid double quoted literal at %u", location];
2437	}
2438      [self setCharactersToBeSkipped: skip];
2439      if (NO == [self scanString: @"\"" intoString: NULL])
2440        {
2441          [NSException raise: NSInvalidArgumentException
2442            format: @"Unterminated double quoted literal at %u", location];
2443        }
2444      return [NSExpression expressionForConstantValue: str];
2445    }
2446
2447  if ([self scanString: @"'" intoString: NULL])
2448    {
2449      NSCharacterSet	*skip = [self charactersToBeSkipped];
2450      NSString *str = nil;
2451
2452      [self setCharactersToBeSkipped: nil];
2453      if ([self scanUpToString: @"'" intoString: &str] == NO)
2454	{
2455	  [self setCharactersToBeSkipped: skip];
2456          [NSException raise: NSInvalidArgumentException
2457                      format: @"Invalid single quoted literal at %u", location];
2458	}
2459      [self setCharactersToBeSkipped: skip];
2460      if (NO == [self scanString: @"'" intoString: NULL])
2461        {
2462          [NSException raise: NSInvalidArgumentException
2463            format: @"Unterminated single quoted literal at %u", location];
2464        }
2465      return [NSExpression expressionForConstantValue: str];
2466    }
2467
2468  if ([self scanString: @"@" intoString: NULL])
2469    {
2470      NSExpression *e = [self parseIdentifierExpression];
2471
2472      if (![e keyPath])
2473        {
2474          [NSException raise: NSInvalidArgumentException
2475                      format: @"Invalid keypath identifier: %@", e];
2476        }
2477
2478      // prefix with keypath
2479      return [NSExpression expressionForKeyPath:
2480        [NSString stringWithFormat: @"@%@", [e keyPath]]];
2481    }
2482
2483  return [self parseIdentifierExpression];
2484}
2485
2486- (NSExpression *) parseFunctionalExpression
2487{
2488  NSExpression *left = [self parseSimpleExpression];
2489
2490  while (YES)
2491    {
2492      if ([self scanString: @"(" intoString: NULL])
2493        {
2494          // function - this parser allows for (max)(a, b, c) to be properly
2495          // recognized and even (%K)(a, b, c) if %K evaluates to "max"
2496          NSMutableArray *args = [NSMutableArray arrayWithCapacity: 5];
2497
2498          if (![left keyPath])
2499            {
2500              [NSException raise: NSInvalidArgumentException
2501                          format: @"Invalid function identifier: %@", left];
2502            }
2503
2504          if (![self scanString: @")" intoString: NULL])
2505            {
2506              // any arguments
2507              // first argument
2508              [args addObject: [self parseExpression]];
2509              while ([self scanString: @"," intoString: NULL])
2510                {
2511                  // more arguments
2512                  [args addObject: [self parseExpression]];
2513                }
2514
2515              if (![self scanString: @")" intoString: NULL])
2516                {
2517                  [NSException raise: NSInvalidArgumentException
2518                              format: @"Missing ) in function arguments"];
2519                }
2520            }
2521          left = [NSExpression expressionForFunction: [left keyPath]
2522                                           arguments: args];
2523        }
2524      else if ([self scanString: @"[" intoString: NULL])
2525        {
2526          // index expression
2527          if ([self scanPredicateKeyword: @"FIRST"])
2528            {
2529              left = [NSExpression expressionForFunction: @"_first"
2530                arguments: [NSArray arrayWithObject: [self parseExpression]]];
2531            }
2532          else if ([self scanPredicateKeyword: @"LAST"])
2533            {
2534              left = [NSExpression expressionForFunction: @"_last"
2535                arguments: [NSArray arrayWithObject: [self parseExpression]]];
2536            }
2537          else if ([self scanPredicateKeyword: @"SIZE"])
2538            {
2539              left = [NSExpression expressionForFunction: @"count"
2540                arguments: [NSArray arrayWithObject: [self parseExpression]]];
2541            }
2542          else
2543            {
2544              left = [NSExpression expressionForFunction: @"_index"
2545                arguments: [NSArray arrayWithObjects: left,
2546                [self parseExpression], nil]];
2547            }
2548          if (![self scanString: @"]" intoString: NULL])
2549            {
2550              [NSException raise: NSInvalidArgumentException
2551                          format: @"Missing ] in index argument"];
2552            }
2553        }
2554      else if ([self scanString: @"." intoString: NULL])
2555        {
2556          // keypath - this parser allows for (a).(b.c)
2557          // to be properly recognized
2558          // and even %K.((%K)) if the first %K evaluates to "a" and the
2559          // second %K to "b.c"
2560          NSExpression *right;
2561
2562          if (![left keyPath])
2563            {
2564              [NSException raise: NSInvalidArgumentException
2565                          format: @"Invalid left keypath: %@", left];
2566            }
2567          right = [self parseExpression];
2568          if (![right keyPath])
2569            {
2570              [NSException raise: NSInvalidArgumentException
2571                          format: @"Invalid right keypath: %@", left];
2572            }
2573
2574          if (evaluatedObjectExpression != left)
2575            {
2576              // concatenate
2577              left = [NSExpression expressionForKeyPath:
2578                        [NSString stringWithFormat: @"%@.%@",
2579                                  [left keyPath], [right keyPath]]];
2580            }
2581          else
2582            {
2583              left = [NSExpression expressionForKeyPath: [right keyPath]];
2584            }
2585        }
2586      else
2587        {
2588          // done with suffixes
2589          return left;
2590        }
2591    }
2592}
2593
2594- (NSExpression *) parsePowerExpression
2595{
2596  NSExpression *left = [self parseFunctionalExpression];
2597
2598  while (YES)
2599    {
2600      NSExpression *right;
2601
2602      if ([self scanString: @"**" intoString: NULL])
2603        {
2604          right = [self parseFunctionalExpression];
2605          left = [NSExpression expressionForFunction: @"_pow"
2606            arguments: [NSArray arrayWithObjects: left, right, nil]];
2607        }
2608      else
2609        {
2610          return left;
2611        }
2612    }
2613}
2614
2615- (NSExpression *) parseMultiplicationExpression
2616{
2617  NSExpression *left = [self parsePowerExpression];
2618
2619  while (YES)
2620    {
2621      NSExpression *right;
2622
2623      if ([self scanString: @"*" intoString: NULL])
2624        {
2625          right = [self parsePowerExpression];
2626          left = [NSExpression expressionForFunction: @"_mul"
2627            arguments: [NSArray arrayWithObjects: left, right, nil]];
2628        }
2629      else if ([self scanString: @"/" intoString: NULL])
2630        {
2631          right = [self parsePowerExpression];
2632          left = [NSExpression expressionForFunction: @"_div"
2633            arguments: [NSArray arrayWithObjects: left, right, nil]];
2634        }
2635      else
2636        {
2637          return left;
2638        }
2639    }
2640}
2641
2642- (NSExpression *) parseAdditionExpression
2643{
2644  NSExpression *left = [self parseMultiplicationExpression];
2645
2646  while (YES)
2647    {
2648      NSExpression *right;
2649
2650      if ([self scanString: @"+" intoString: NULL])
2651        {
2652          right = [self parseMultiplicationExpression];
2653          left = [NSExpression expressionForFunction: @"_add"
2654            arguments: [NSArray arrayWithObjects: left, right, nil]];
2655        }
2656      else if ([self scanString: @"-" intoString: NULL])
2657        {
2658          right = [self parseMultiplicationExpression];
2659          left = [NSExpression expressionForFunction: @"_sub"
2660            arguments: [NSArray arrayWithObjects: left, right, nil]];
2661        }
2662      else
2663        {
2664          return left;
2665        }
2666    }
2667}
2668
2669- (NSExpression *) parseBinaryExpression
2670{
2671  NSExpression *left = [self parseAdditionExpression];
2672
2673  while (YES)
2674    {
2675      NSExpression *right;
2676
2677      if ([self scanString: @":=" intoString: NULL])	// assignment
2678        {
2679          // check left to be a variable?
2680          right = [self parseAdditionExpression];
2681          // FIXME
2682        }
2683      else
2684        {
2685          return left;
2686        }
2687    }
2688}
2689@end
2690
2691
2692#if OS_API_VERSION(MAC_OS_X_VERSION_10_6, GS_API_LATEST)
2693
2694
2695@implementation GSBlockPredicate
2696
2697- (instancetype) initWithBlock: (GSBlockPredicateBlock)block
2698{
2699  if (nil == (self = [super init]))
2700    {
2701      return nil;
2702    }
2703  _block = (GSBlockPredicateBlock)[(id)block retain];
2704  return self;
2705}
2706
2707- (instancetype) predicateWithSubstitutionVariables:
2708  (GS_GENERIC_CLASS(NSDictionary,NSString*,id)*)variables
2709{
2710  return [[[GSBoundBlockPredicate alloc] initWithBlock: _block
2711                                              bindings: variables] autorelease];
2712}
2713
2714- (BOOL) evaluateWithObject: (id)object
2715      substitutionVariables: (GS_GENERIC_CLASS(NSDictionary,
2716                                               NSString*,id)*)variables
2717{
2718  return CALL_BLOCK(_block, object, variables);
2719}
2720
2721- (BOOL) evaluateWithObject: (id)object
2722{
2723  return [self evaluateWithObject: object
2724            substitutionVariables: nil];
2725}
2726
2727- (void) dealloc
2728{
2729  [(id)_block release];
2730  _block = NULL;
2731  [super dealloc];
2732}
2733
2734- (NSString*) predicateFormat
2735{
2736  return [NSString stringWithFormat: @"BLOCKPREDICATE(%p)", (void*)_block];
2737}
2738@end
2739
2740@implementation GSBoundBlockPredicate
2741
2742- (instancetype) initWithBlock: (GSBlockPredicateBlock)block
2743                      bindings: (GS_GENERIC_CLASS(NSDictionary,
2744                                                   NSString*,id)*)bindings
2745{
2746  if (nil == (self = [super initWithBlock: block]))
2747    {
2748      return nil;
2749    }
2750  ASSIGN(_bindings, bindings);
2751  return self;
2752}
2753
2754- (BOOL) evaluateWithObject: (id)object
2755{
2756  return [self evaluateWithObject: object
2757            substitutionVariables: _bindings];
2758}
2759
2760- (void) dealloc
2761{
2762  DESTROY(_bindings);
2763  [super dealloc];
2764}
2765@end
2766
2767#endif
2768