iOS/Pods/Realm/Realm/RLMQueryUtil.mm

   1 ////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Copyright 2014 Realm Inc.
   4 //
   5 // Licensed under the Apache License, Version 2.0 (the "License");
   6 // you may not use this file except in compliance with the License.
   7 // You may obtain a copy of the License at
   8 //
   9 // http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing, software
  12 // distributed under the License is distributed on an "AS IS" BASIS,
  13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 // See the License for the specific language governing permissions and
  15 // limitations under the License.
  16 //
  17 ////////////////////////////////////////////////////////////////////////////
  18
  19 #import "RLMQueryUtil.hpp"
  20
  21 #import "RLMArray.h"
  22 #import "RLMObjectSchema_Private.h"
  23 #import "RLMObject_Private.hpp"
  24 #import "RLMPredicateUtil.hpp"
  25 #import "RLMProperty_Private.h"
  26 #import "RLMSchema.h"
  27 #import "RLMUtil.hpp"
  28
  29 #import "object_store.hpp"
  30 #import "results.hpp"
  31
  32 #include <realm/query_engine.hpp>
  33 #include <realm/query_expression.hpp>
  34 #include <realm/util/cf_ptr.hpp>
  35 #include <realm/util/overload.hpp>
  36
  37 using namespace realm;
  38
  39 NSString * const RLMPropertiesComparisonTypeMismatchException = @"RLMPropertiesComparisonTypeMismatchException";
  40 NSString * const RLMUnsupportedTypesFoundInPropertyComparisonException = @"RLMUnsupportedTypesFoundInPropertyComparisonException";
  41
  42 NSString * const RLMPropertiesComparisonTypeMismatchReason = @"Property type mismatch between %@ and %@";
  43 NSString * const RLMUnsupportedTypesFoundInPropertyComparisonReason = @"Comparison between %@ and %@";
  44
  45 // small helper to create the many exceptions thrown when parsing predicates
  46 static NSException *RLMPredicateException(NSString *name, NSString *format, ...) {
  47     va_list args;
  48     va_start(args, format);
  49     NSString *reason = [[NSString alloc] initWithFormat:format arguments:args];
  50     va_end(args);
  51
  52     return [NSException exceptionWithName:name reason:reason userInfo:nil];
  53 }
  54
  55 // check a precondition and throw an exception if it is not met
  56 // this should be used iff the condition being false indicates a bug in the caller
  57 // of the function checking its preconditions
  58 static void RLMPrecondition(bool condition, NSString *name, NSString *format, ...) {
  59     if (__builtin_expect(condition, 1)) {
  60         return;
  61     }
  62
  63     va_list args;
  64     va_start(args, format);
  65     NSString *reason = [[NSString alloc] initWithFormat:format arguments:args];
  66     va_end(args);
  67
  68     @throw [NSException exceptionWithName:name reason:reason userInfo:nil];
  69 }
  70
  71 // return the property for a validated column name
  72 RLMProperty *RLMValidatedProperty(RLMObjectSchema *desc, NSString *columnName) {
  73     RLMProperty *prop = desc[columnName];
  74     RLMPrecondition(prop, @"Invalid property name",
  75                     @"Property '%@' not found in object of type '%@'", columnName, desc.className);
  76     return prop;
  77 }
  78
  79 namespace {
  80 BOOL RLMPropertyTypeIsNumeric(RLMPropertyType propertyType) {
  81     switch (propertyType) {
  82         case RLMPropertyTypeInt:
  83         case RLMPropertyTypeFloat:
  84         case RLMPropertyTypeDouble:
  85             return YES;
  86         default:
  87             return NO;
  88     }
  89 }
  90
  91 // Equal and ContainsSubstring are used by QueryBuilder::add_string_constraint as the comparator
  92 // for performing diacritic-insensitive comparisons.
  93
  94 bool equal(CFStringCompareFlags options, StringData v1, StringData v2)
  95 {
  96     if (v1.is_null() || v2.is_null()) {
  97         return v1.is_null() == v2.is_null();
  98     }
  99
 100     auto s1 = util::adoptCF(CFStringCreateWithBytesNoCopy(kCFAllocatorSystemDefault, (const UInt8*)v1.data(), v1.size(),
 101                                                           kCFStringEncodingUTF8, false, kCFAllocatorNull));
 102     auto s2 = util::adoptCF(CFStringCreateWithBytesNoCopy(kCFAllocatorSystemDefault, (const UInt8*)v2.data(), v2.size(),
 103                                                           kCFStringEncodingUTF8, false, kCFAllocatorNull));
 104
 105     return CFStringCompare(s1.get(), s2.get(), options) == kCFCompareEqualTo;
 106 }
 107
 108 template <CFStringCompareFlags options>
 109 struct Equal {
 110     using CaseSensitive = Equal<options & ~kCFCompareCaseInsensitive>;
 111     using CaseInsensitive = Equal<options | kCFCompareCaseInsensitive>;
 112
 113     bool operator()(StringData v1, StringData v2, bool v1_null, bool v2_null) const
 114     {
 115         REALM_ASSERT_DEBUG(v1_null == v1.is_null());
 116         REALM_ASSERT_DEBUG(v2_null == v2.is_null());
 117
 118         return equal(options, v1, v2);
 119     }
 120
 121     // FIXME: Consider the options.
 122     static const char* description() { return "equal"; }
 123 };
 124
 125 bool contains_substring(CFStringCompareFlags options, StringData v1, StringData v2)
 126 {
 127     if (v2.is_null()) {
 128         // Everything contains NULL
 129         return true;
 130     }
 131
 132     if (v1.is_null()) {
 133         // NULL contains nothing (except NULL, handled above)
 134         return false;
 135     }
 136
 137     if (v2.size() == 0) {
 138         // Everything (except NULL, handled above) contains the empty string
 139         return true;
 140     }
 141
 142     auto s1 = util::adoptCF(CFStringCreateWithBytesNoCopy(kCFAllocatorSystemDefault, (const UInt8*)v1.data(), v1.size(),
 143                                                           kCFStringEncodingUTF8, false, kCFAllocatorNull));
 144     auto s2 = util::adoptCF(CFStringCreateWithBytesNoCopy(kCFAllocatorSystemDefault, (const UInt8*)v2.data(), v2.size(),
 145                                                           kCFStringEncodingUTF8, false, kCFAllocatorNull));
 146
 147     return CFStringFind(s1.get(), s2.get(), options).location != kCFNotFound;
 148 }
 149
 150 template <CFStringCompareFlags options>
 151 struct ContainsSubstring {
 152     using CaseSensitive = ContainsSubstring<options & ~kCFCompareCaseInsensitive>;
 153     using CaseInsensitive = ContainsSubstring<options | kCFCompareCaseInsensitive>;
 154
 155     bool operator()(StringData v1, StringData v2, bool v1_null, bool v2_null) const
 156     {
 157         REALM_ASSERT_DEBUG(v1_null == v1.is_null());
 158         REALM_ASSERT_DEBUG(v2_null == v2.is_null());
 159
 160         return contains_substring(options, v1, v2);
 161     }
 162
 163     // FIXME: Consider the options.
 164     static const char* description() { return "contains"; }
 165 };
 166
 167
 168 NSString *operatorName(NSPredicateOperatorType operatorType)
 169 {
 170     switch (operatorType) {
 171         case NSLessThanPredicateOperatorType:
 172             return @"<";
 173         case NSLessThanOrEqualToPredicateOperatorType:
 174             return @"<=";
 175         case NSGreaterThanPredicateOperatorType:
 176             return @">";
 177         case NSGreaterThanOrEqualToPredicateOperatorType:
 178             return @">=";
 179         case NSEqualToPredicateOperatorType:
 180             return @"==";
 181         case NSNotEqualToPredicateOperatorType:
 182             return @"!=";
 183         case NSMatchesPredicateOperatorType:
 184             return @"MATCHES";
 185         case NSLikePredicateOperatorType:
 186             return @"LIKE";
 187         case NSBeginsWithPredicateOperatorType:
 188             return @"BEGINSWITH";
 189         case NSEndsWithPredicateOperatorType:
 190             return @"ENDSWITH";
 191         case NSInPredicateOperatorType:
 192             return @"IN";
 193         case NSContainsPredicateOperatorType:
 194             return @"CONTAINS";
 195         case NSBetweenPredicateOperatorType:
 196             return @"BETWEEN";
 197         case NSCustomSelectorPredicateOperatorType:
 198             return @"custom selector";
 199     }
 200
 201     return [NSString stringWithFormat:@"unknown operator %lu", (unsigned long)operatorType];
 202 }
 203
 204 Table& get_table(Group& group, RLMObjectSchema *objectSchema)
 205 {
 206     return *ObjectStore::table_for_object_type(group, objectSchema.objectName.UTF8String);
 207 }
 208
 209 // A reference to a column within a query. Can be resolved to a Columns<T> for use in query expressions.
 210 class ColumnReference {
 211 public:
 212     ColumnReference(Query& query, Group& group, RLMSchema *schema, RLMProperty* property, const std::vector<RLMProperty*>& links = {})
 213     : m_links(links), m_property(property), m_schema(schema), m_group(&group), m_query(&query), m_table(query.get_table().get())
 214     {
 215         auto& table = walk_link_chain([](Table&, size_t, RLMPropertyType) { });
 216         m_index = table.get_column_index(m_property.name.UTF8String);
 217     }
 218
 219     template <typename T, typename... SubQuery>
 220     auto resolve(SubQuery&&... subquery) const
 221     {
 222         static_assert(sizeof...(SubQuery) < 2, "resolve() takes at most one subquery");
 223         set_link_chain_on_table();
 224         if (type() != RLMPropertyTypeLinkingObjects) {
 225             return m_table->template column<T>(index(), std::forward<SubQuery>(subquery)...);
 226         }
 227         else {
 228             return resolve_backlink<T>(std::forward<SubQuery>(subquery)...);
 229         }
 230     }
 231
 232     RLMProperty *property() const { return m_property; }
 233     size_t index() const { return m_index; }
 234     RLMPropertyType type() const { return property().type; }
 235     Group& group() const { return *m_group; }
 236
 237     RLMObjectSchema *link_target_object_schema() const
 238     {
 239         switch (type()) {
 240             case RLMPropertyTypeObject:
 241             case RLMPropertyTypeLinkingObjects:
 242                 return m_schema[property().objectClassName];
 243             default:
 244                 REALM_UNREACHABLE();
 245         }
 246     }
 247
 248     bool has_links() const { return m_links.size(); }
 249
 250     bool has_any_to_many_links() const {
 251         return std::any_of(begin(m_links), end(m_links),
 252                            [](RLMProperty *property) { return property.array; });
 253     }
 254
 255     ColumnReference last_link_column() const {
 256         REALM_ASSERT(!m_links.empty());
 257         return {*m_query, *m_group, m_schema, m_links.back(), {m_links.begin(), m_links.end() - 1}};
 258     }
 259
 260     ColumnReference column_ignoring_links(Query& query) const {
 261         return {query, *m_group, m_schema, m_property};
 262     }
 263
 264 private:
 265     template <typename T, typename... SubQuery>
 266     auto resolve_backlink(SubQuery&&... subquery) const
 267     {
 268         // We actually just want `if constexpr (std::is_same<T, Link>::value) { ... }`,
 269         // so fake it by tag-dispatching on the conditional
 270         return do_resolve_backlink<T>(std::is_same<T, Link>(), std::forward<SubQuery>(subquery)...);
 271     }
 272
 273     template <typename T, typename... SubQuery>
 274     auto do_resolve_backlink(std::true_type, SubQuery&&... subquery) const
 275     {
 276         return with_link_origin(m_property, [&](Table& table, size_t col) {
 277             return m_table->template column<T>(table, col, std::forward<SubQuery>(subquery)...);
 278         });
 279     }
 280
 281     template <typename T, typename... SubQuery>
 282     Columns<T> do_resolve_backlink(std::false_type, SubQuery&&...) const
 283     {
 284         // This can't actually happen as we only call resolve_backlink() if
 285         // it's RLMPropertyTypeLinkingObjects
 286         __builtin_unreachable();
 287     }
 288
 289     template<typename Func>
 290     Table& walk_link_chain(Func&& func) const
 291     {
 292         auto table = m_query->get_table().get();
 293         for (const auto& link : m_links) {
 294             if (link.type != RLMPropertyTypeLinkingObjects) {
 295                 auto index = table->get_column_index(link.name.UTF8String);
 296                 func(*table, index, link.type);
 297                 table = table->get_link_target(index).get();
 298             }
 299             else {
 300                 with_link_origin(link, [&](Table& link_origin_table, size_t link_origin_column) {
 301                     func(link_origin_table, link_origin_column, link.type);
 302                     table = &link_origin_table;
 303                 });
 304             }
 305         }
 306         return *table;
 307     }
 308
 309     template<typename Func>
 310     auto with_link_origin(RLMProperty *prop, Func&& func) const
 311     {
 312         RLMObjectSchema *link_origin_schema = m_schema[prop.objectClassName];
 313         Table& link_origin_table = get_table(*m_group, link_origin_schema);
 314         size_t link_origin_column = link_origin_table.get_column_index(prop.linkOriginPropertyName.UTF8String);
 315         return func(link_origin_table, link_origin_column);
 316     }
 317
 318     void set_link_chain_on_table() const
 319     {
 320         walk_link_chain([&](Table& current_table, size_t column, RLMPropertyType type) {
 321             if (type == RLMPropertyTypeLinkingObjects) {
 322                 m_table->backlink(current_table, column);
 323             }
 324             else {
 325                 m_table->link(column);
 326             }
 327         });
 328     }
 329
 330     std::vector<RLMProperty*> m_links;
 331     RLMProperty *m_property;
 332     RLMSchema *m_schema;
 333     Group *m_group;
 334     Query *m_query;
 335     Table *m_table;
 336     size_t m_index;
 337 };
 338
 339 class CollectionOperation {
 340 public:
 341     enum Type {
 342         Count,
 343         Minimum,
 344         Maximum,
 345         Sum,
 346         Average,
 347     };
 348
 349     CollectionOperation(Type type, ColumnReference link_column, util::Optional<ColumnReference> column)
 350         : m_type(type)
 351         , m_link_column(std::move(link_column))
 352         , m_column(std::move(column))
 353     {
 354         RLMPrecondition(m_link_column.property().array,
 355                         @"Invalid predicate", @"Collection operation can only be applied to a property of type RLMArray.");
 356
 357         switch (m_type) {
 358             case Count:
 359                 RLMPrecondition(!m_column, @"Invalid predicate", @"Result of @count does not have any properties.");
 360                 break;
 361             case Minimum:
 362             case Maximum:
 363             case Sum:
 364             case Average:
 365                 RLMPrecondition(m_column && RLMPropertyTypeIsNumeric(m_column->type()), @"Invalid predicate",
 366                                 @"%@ can only be applied to a numeric property.", name_for_type(m_type));
 367                 break;
 368         }
 369     }
 370
 371     CollectionOperation(NSString *operationName, ColumnReference link_column, util::Optional<ColumnReference> column = util::none)
 372         : CollectionOperation(type_for_name(operationName), std::move(link_column), std::move(column))
 373     {
 374     }
 375
 376     Type type() const { return m_type; }
 377     const ColumnReference& link_column() const { return m_link_column; }
 378     const ColumnReference& column() const { return *m_column; }
 379
 380     void validate_comparison(id value) const {
 381         switch (m_type) {
 382             case Count:
 383             case Average:
 384                 RLMPrecondition([value isKindOfClass:[NSNumber class]], @"Invalid operand",
 385                                 @"%@ can only be compared with a numeric value.", name_for_type(m_type));
 386                 break;
 387             case Minimum:
 388             case Maximum:
 389             case Sum:
 390                 RLMPrecondition(RLMIsObjectValidForProperty(value, m_column->property()), @"Invalid operand",
 391                                 @"%@ on a property of type %@ cannot be compared with '%@'",
 392                                 name_for_type(m_type), RLMTypeToString(m_column->type()), value);
 393                 break;
 394         }
 395     }
 396
 397     void validate_comparison(const ColumnReference& column) const {
 398         switch (m_type) {
 399             case Count:
 400                 RLMPrecondition(RLMPropertyTypeIsNumeric(column.type()), @"Invalid operand",
 401                                 @"%@ can only be compared with a numeric value.", name_for_type(m_type));
 402                 break;
 403             case Average:
 404             case Minimum:
 405             case Maximum:
 406             case Sum:
 407                 RLMPrecondition(RLMPropertyTypeIsNumeric(column.type()), @"Invalid operand",
 408                                 @"%@ on a property of type %@ cannot be compared with property of type '%@'",
 409                                 name_for_type(m_type), RLMTypeToString(m_column->type()), RLMTypeToString(column.type()));
 410                 break;
 411         }
 412     }
 413
 414 private:
 415     static Type type_for_name(NSString *name) {
 416         if ([name isEqualToString:@"@count"]) {
 417             return Count;
 418         }
 419         if ([name isEqualToString:@"@min"]) {
 420             return Minimum;
 421         }
 422         if ([name isEqualToString:@"@max"]) {
 423             return Maximum;
 424         }
 425         if ([name isEqualToString:@"@sum"]) {
 426             return Sum;
 427         }
 428         if ([name isEqualToString:@"@avg"]) {
 429             return Average;
 430         }
 431         @throw RLMPredicateException(@"Invalid predicate", @"Unsupported collection operation '%@'", name);
 432     }
 433
 434     static NSString *name_for_type(Type type) {
 435         switch (type) {
 436             case Count: return @"@count";
 437             case Minimum: return @"@min";
 438             case Maximum: return @"@max";
 439             case Sum: return @"@sum";
 440             case Average: return @"@avg";
 441         }
 442     }
 443
 444     Type m_type;
 445     ColumnReference m_link_column;
 446     util::Optional<ColumnReference> m_column;
 447 };
 448
 449 class QueryBuilder {
 450 public:
 451     QueryBuilder(Query& query, Group& group, RLMSchema *schema)
 452     : m_query(query), m_group(group), m_schema(schema) { }
 453
 454     void apply_predicate(NSPredicate *predicate, RLMObjectSchema *objectSchema);
 455
 456
 457     void apply_collection_operator_expression(RLMObjectSchema *desc, NSString *keyPath, id value, NSComparisonPredicate *pred);
 458     void apply_value_expression(RLMObjectSchema *desc, NSString *keyPath, id value, NSComparisonPredicate *pred);
 459     void apply_column_expression(RLMObjectSchema *desc, NSString *leftKeyPath, NSString *rightKeyPath, NSComparisonPredicate *predicate);
 460     void apply_subquery_count_expression(RLMObjectSchema *objectSchema, NSExpression *subqueryExpression,
 461                                          NSPredicateOperatorType operatorType, NSExpression *right);
 462     void apply_function_subquery_expression(RLMObjectSchema *objectSchema, NSExpression *functionExpression,
 463                                             NSPredicateOperatorType operatorType, NSExpression *right);
 464     void apply_function_expression(RLMObjectSchema *objectSchema, NSExpression *functionExpression,
 465                                    NSPredicateOperatorType operatorType, NSExpression *right);
 466
 467
 468     template <typename A, typename B>
 469     void add_numeric_constraint(RLMPropertyType datatype,
 470                                 NSPredicateOperatorType operatorType,
 471                                 A&& lhs, B&& rhs);
 472
 473     template <typename A, typename B>
 474     void add_bool_constraint(NSPredicateOperatorType operatorType, A lhs, B rhs);
 475
 476     void add_substring_constraint(null, Query condition);
 477     template<typename T>
 478     void add_substring_constraint(const T& value, Query condition);
 479     template<typename T>
 480     void add_substring_constraint(const Columns<T>& value, Query condition);
 481
 482     template <typename T>
 483     void add_string_constraint(NSPredicateOperatorType operatorType,
 484                                NSComparisonPredicateOptions predicateOptions,
 485                                Columns<String> &&column,
 486                                T value);
 487
 488     void add_string_constraint(NSPredicateOperatorType operatorType,
 489                                NSComparisonPredicateOptions predicateOptions,
 490                                StringData value,
 491                                Columns<String>&& column);
 492
 493     template <typename L, typename R>
 494     void add_constraint(RLMPropertyType type,
 495                         NSPredicateOperatorType operatorType,
 496                         NSComparisonPredicateOptions predicateOptions,
 497                         L lhs, R rhs);
 498     template <typename... T>
 499     void do_add_constraint(RLMPropertyType type, NSPredicateOperatorType operatorType,
 500                            NSComparisonPredicateOptions predicateOptions, T... values);
 501     void do_add_constraint(RLMPropertyType, NSPredicateOperatorType, NSComparisonPredicateOptions, id, realm::null);
 502
 503     void add_between_constraint(const ColumnReference& column, id value);
 504
 505     void add_binary_constraint(NSPredicateOperatorType operatorType, const ColumnReference& column, BinaryData value);
 506     void add_binary_constraint(NSPredicateOperatorType operatorType, const ColumnReference& column, id value);
 507     void add_binary_constraint(NSPredicateOperatorType operatorType, const ColumnReference& column, null);
 508     void add_binary_constraint(NSPredicateOperatorType operatorType, id value, const ColumnReference& column);
 509     void add_binary_constraint(NSPredicateOperatorType, const ColumnReference&, const ColumnReference&);
 510
 511     void add_link_constraint(NSPredicateOperatorType operatorType, const ColumnReference& column, RLMObject *obj);
 512     void add_link_constraint(NSPredicateOperatorType operatorType, const ColumnReference& column, realm::null);
 513     template<typename T>
 514     void add_link_constraint(NSPredicateOperatorType operatorType, T obj, const ColumnReference& column);
 515     void add_link_constraint(NSPredicateOperatorType, const ColumnReference&, const ColumnReference&);
 516
 517     template <CollectionOperation::Type Operation, typename... T>
 518     void add_collection_operation_constraint(RLMPropertyType propertyType, NSPredicateOperatorType operatorType, T... values);
 519     template <typename... T>
 520     void add_collection_operation_constraint(NSPredicateOperatorType operatorType,
 521                                              CollectionOperation collectionOperation, T... values);
 522
 523
 524     CollectionOperation collection_operation_from_key_path(RLMObjectSchema *desc, NSString *keyPath);
 525     ColumnReference column_reference_from_key_path(RLMObjectSchema *objectSchema, NSString *keyPath, bool isAggregate);
 526
 527 private:
 528     Query& m_query;
 529     Group& m_group;
 530     RLMSchema *m_schema;
 531 };
 532
 533 // add a clause for numeric constraints based on operator type
 534 template <typename A, typename B>
 535 void QueryBuilder::add_numeric_constraint(RLMPropertyType datatype,
 536                                           NSPredicateOperatorType operatorType,
 537                                           A&& lhs, B&& rhs)
 538 {
 539     switch (operatorType) {
 540         case NSLessThanPredicateOperatorType:
 541             m_query.and_query(lhs < rhs);
 542             break;
 543         case NSLessThanOrEqualToPredicateOperatorType:
 544             m_query.and_query(lhs <= rhs);
 545             break;
 546         case NSGreaterThanPredicateOperatorType:
 547             m_query.and_query(lhs > rhs);
 548             break;
 549         case NSGreaterThanOrEqualToPredicateOperatorType:
 550             m_query.and_query(lhs >= rhs);
 551             break;
 552         case NSEqualToPredicateOperatorType:
 553             m_query.and_query(lhs == rhs);
 554             break;
 555         case NSNotEqualToPredicateOperatorType:
 556             m_query.and_query(lhs != rhs);
 557             break;
 558         default:
 559             @throw RLMPredicateException(@"Invalid operator type",
 560                                          @"Operator '%@' not supported for type %@",
 561                                          operatorName(operatorType), RLMTypeToString(datatype));
 562     }
 563 }
 564
 565 template <typename A, typename B>
 566 void QueryBuilder::add_bool_constraint(NSPredicateOperatorType operatorType, A lhs, B rhs) {
 567     switch (operatorType) {
 568         case NSEqualToPredicateOperatorType:
 569             m_query.and_query(lhs == rhs);
 570             break;
 571         case NSNotEqualToPredicateOperatorType:
 572             m_query.and_query(lhs != rhs);
 573             break;
 574         default:
 575             @throw RLMPredicateException(@"Invalid operator type",
 576                                          @"Operator '%@' not supported for bool type", operatorName(operatorType));
 577     }
 578 }
 579
 580 void QueryBuilder::add_substring_constraint(null, Query) {
 581     // Foundation always returns false for substring operations with a RHS of null or "".
 582     m_query.and_query(std::unique_ptr<Expression>(new FalseExpression));
 583 }
 584
 585 template<typename T>
 586 void QueryBuilder::add_substring_constraint(const T& value, Query condition) {
 587     // Foundation always returns false for substring operations with a RHS of null or "".
 588     m_query.and_query(value.size()
 589                       ? std::move(condition)
 590                       : std::unique_ptr<Expression>(new FalseExpression));
 591 }
 592
 593 template<typename T>
 594 void QueryBuilder::add_substring_constraint(const Columns<T>& value, Query condition) {
 595     // Foundation always returns false for substring operations with a RHS of null or "".
 596     // We don't need to concern ourselves with the possibility of value traversing a link list
 597     // and producing multiple values per row as such expressions will have been rejected.
 598     m_query.and_query(const_cast<Columns<String>&>(value).size() != 0 && std::move(condition));
 599 }
 600
 601 template <typename T>
 602 void QueryBuilder::add_string_constraint(NSPredicateOperatorType operatorType,
 603                                          NSComparisonPredicateOptions predicateOptions,
 604                                          Columns<String> &&column,
 605                                          T value) {
 606     bool caseSensitive = !(predicateOptions & NSCaseInsensitivePredicateOption);
 607     bool diacriticSensitive = !(predicateOptions & NSDiacriticInsensitivePredicateOption);
 608
 609     if (diacriticSensitive) {
 610         switch (operatorType) {
 611             case NSBeginsWithPredicateOperatorType:
 612                 add_substring_constraint(value, column.begins_with(value, caseSensitive));
 613                 break;
 614             case NSEndsWithPredicateOperatorType:
 615                 add_substring_constraint(value, column.ends_with(value, caseSensitive));
 616                 break;
 617             case NSContainsPredicateOperatorType:
 618                 add_substring_constraint(value, column.contains(value, caseSensitive));
 619                 break;
 620             case NSEqualToPredicateOperatorType:
 621                 m_query.and_query(column.equal(value, caseSensitive));
 622                 break;
 623             case NSNotEqualToPredicateOperatorType:
 624                 m_query.and_query(column.not_equal(value, caseSensitive));
 625                 break;
 626             case NSLikePredicateOperatorType:
 627                 m_query.and_query(column.like(value, caseSensitive));
 628                 break;
 629             default:
 630                 @throw RLMPredicateException(@"Invalid operator type",
 631                                              @"Operator '%@' not supported for string type",
 632                                              operatorName(operatorType));
 633         }
 634         return;
 635     }
 636
 637     auto as_subexpr = util::overload([](StringData value) { return make_subexpr<ConstantStringValue>(value); },
 638                                      [](const Columns<String>& c) { return c.clone(); });
 639     auto left = as_subexpr(column);
 640     auto right = as_subexpr(value);
 641
 642     auto make_constraint = [&](auto comparator) {
 643         using Comparator = decltype(comparator);
 644         using CompareCS = Compare<typename Comparator::CaseSensitive, StringData>;
 645         using CompareCI = Compare<typename Comparator::CaseInsensitive, StringData>;
 646         if (caseSensitive) {
 647             return make_expression<CompareCS>(std::move(left), std::move(right));
 648         }
 649         else {
 650             return make_expression<CompareCI>(std::move(left), std::move(right));
 651         }
 652     };
 653
 654     switch (operatorType) {
 655         case NSBeginsWithPredicateOperatorType: {
 656             using C = ContainsSubstring<kCFCompareDiacriticInsensitive | kCFCompareAnchored>;
 657             add_substring_constraint(value, make_constraint(C{}));
 658             break;
 659         }
 660         case NSEndsWithPredicateOperatorType: {
 661             using C = ContainsSubstring<kCFCompareDiacriticInsensitive | kCFCompareAnchored | kCFCompareBackwards>;
 662             add_substring_constraint(value, make_constraint(C{}));
 663             break;
 664         }
 665         case NSContainsPredicateOperatorType: {
 666             using C = ContainsSubstring<kCFCompareDiacriticInsensitive>;
 667             add_substring_constraint(value, make_constraint(C{}));
 668             break;
 669         }
 670         case NSNotEqualToPredicateOperatorType:
 671             m_query.Not();
 672             REALM_FALLTHROUGH;
 673         case NSEqualToPredicateOperatorType:
 674             m_query.and_query(make_constraint(Equal<kCFCompareDiacriticInsensitive>{}));
 675             break;
 676         case NSLikePredicateOperatorType:
 677             @throw RLMPredicateException(@"Invalid operator type",
 678                                          @"Operator 'LIKE' not supported with diacritic-insensitive modifier.");
 679         default:
 680             @throw RLMPredicateException(@"Invalid operator type",
 681                                          @"Operator '%@' not supported for string type", operatorName(operatorType));
 682     }
 683 }
 684
 685 void QueryBuilder::add_string_constraint(NSPredicateOperatorType operatorType,
 686                                          NSComparisonPredicateOptions predicateOptions,
 687                                          StringData value,
 688                                          Columns<String>&& column) {
 689     switch (operatorType) {
 690         case NSEqualToPredicateOperatorType:
 691         case NSNotEqualToPredicateOperatorType:
 692             add_string_constraint(operatorType, predicateOptions, std::move(column), value);
 693             break;
 694         default:
 695             @throw RLMPredicateException(@"Invalid operator type",
 696                                          @"Operator '%@' is not supported for string type with key path on right side of operator",
 697                                          operatorName(operatorType));
 698     }
 699 }
 700
 701 id value_from_constant_expression_or_value(id value) {
 702     if (NSExpression *exp = RLMDynamicCast<NSExpression>(value)) {
 703         RLMPrecondition(exp.expressionType == NSConstantValueExpressionType,
 704                         @"Invalid value",
 705                         @"Expressions within predicate aggregates must be constant values");
 706         return exp.constantValue;
 707     }
 708     return value;
 709 }
 710
 711 void validate_and_extract_between_range(id value, RLMProperty *prop, id *from, id *to) {
 712     NSArray *array = RLMDynamicCast<NSArray>(value);
 713     RLMPrecondition(array, @"Invalid value", @"object must be of type NSArray for BETWEEN operations");
 714     RLMPrecondition(array.count == 2, @"Invalid value", @"NSArray object must contain exactly two objects for BETWEEN operations");
 715
 716     *from = value_from_constant_expression_or_value(array.firstObject);
 717     *to = value_from_constant_expression_or_value(array.lastObject);
 718     RLMPrecondition(RLMIsObjectValidForProperty(*from, prop) && RLMIsObjectValidForProperty(*to, prop),
 719                     @"Invalid value",
 720                     @"NSArray objects must be of type %@ for BETWEEN operations", RLMTypeToString(prop.type));
 721 }
 722
 723 void QueryBuilder::add_between_constraint(const ColumnReference& column, id value) {
 724     if (column.has_any_to_many_links()) {
 725         auto link_column = column.last_link_column();
 726         Query subquery = get_table(m_group, link_column.link_target_object_schema()).where();
 727         QueryBuilder(subquery, m_group, m_schema).add_between_constraint(column.column_ignoring_links(subquery), value);
 728
 729         m_query.and_query(link_column.resolve<Link>(std::move(subquery)).count() > 0);
 730         return;
 731     }
 732
 733     id from, to;
 734     validate_and_extract_between_range(value, column.property(), &from, &to);
 735
 736     RLMPropertyType type = column.type();
 737
 738     m_query.group();
 739     add_constraint(type, NSGreaterThanOrEqualToPredicateOperatorType, 0, column, from);
 740     add_constraint(type, NSLessThanOrEqualToPredicateOperatorType, 0, column, to);
 741     m_query.end_group();
 742 }
 743
 744 void QueryBuilder::add_binary_constraint(NSPredicateOperatorType operatorType,
 745                                          const ColumnReference& column,
 746                                          BinaryData value) {
 747     RLMPrecondition(!column.has_links(), @"Unsupported operator", @"NSData properties cannot be queried over an object link.");
 748
 749     size_t index = column.index();
 750     Query query = m_query.get_table()->where();
 751
 752     switch (operatorType) {
 753         case NSBeginsWithPredicateOperatorType:
 754             add_substring_constraint(value, query.begins_with(index, value));
 755             break;
 756         case NSEndsWithPredicateOperatorType:
 757             add_substring_constraint(value, query.ends_with(index, value));
 758             break;
 759         case NSContainsPredicateOperatorType:
 760             add_substring_constraint(value, query.contains(index, value));
 761             break;
 762         case NSEqualToPredicateOperatorType:
 763             m_query.equal(index, value);
 764             break;
 765         case NSNotEqualToPredicateOperatorType:
 766             m_query.not_equal(index, value);
 767             break;
 768         default:
 769             @throw RLMPredicateException(@"Invalid operator type",
 770                                          @"Operator '%@' not supported for binary type", operatorName(operatorType));
 771     }
 772 }
 773
 774 void QueryBuilder::add_binary_constraint(NSPredicateOperatorType operatorType, const ColumnReference& column, id value) {
 775     add_binary_constraint(operatorType, column, RLMBinaryDataForNSData(value));
 776 }
 777
 778 void QueryBuilder::add_binary_constraint(NSPredicateOperatorType operatorType, const ColumnReference& column, null) {
 779     add_binary_constraint(operatorType, column, BinaryData());
 780 }
 781
 782 void QueryBuilder::add_binary_constraint(NSPredicateOperatorType operatorType, id value, const ColumnReference& column) {
 783     switch (operatorType) {
 784         case NSEqualToPredicateOperatorType:
 785         case NSNotEqualToPredicateOperatorType:
 786             add_binary_constraint(operatorType, column, value);
 787             break;
 788         default:
 789             @throw RLMPredicateException(@"Invalid operator type",
 790                                          @"Operator '%@' is not supported for binary type with key path on right side of operator",
 791                                          operatorName(operatorType));
 792     }
 793 }
 794
 795 void QueryBuilder::add_binary_constraint(NSPredicateOperatorType, const ColumnReference&, const ColumnReference&) {
 796     @throw RLMPredicateException(@"Invalid predicate", @"Comparisons between two NSData properties are not supported");
 797 }
 798
 799 void QueryBuilder::add_link_constraint(NSPredicateOperatorType operatorType,
 800                                        const ColumnReference& column, RLMObject *obj) {
 801     RLMPrecondition(operatorType == NSEqualToPredicateOperatorType || operatorType == NSNotEqualToPredicateOperatorType,
 802                     @"Invalid operator type", @"Only 'Equal' and 'Not Equal' operators supported for object comparison");
 803
 804     if (operatorType == NSEqualToPredicateOperatorType) {
 805         m_query.and_query(column.resolve<Link>() == obj->_row);
 806     }
 807     else {
 808         m_query.and_query(column.resolve<Link>() != obj->_row);
 809     }
 810 }
 811
 812 void QueryBuilder::add_link_constraint(NSPredicateOperatorType operatorType,
 813                                        const ColumnReference& column,
 814                                        realm::null) {
 815     RLMPrecondition(operatorType == NSEqualToPredicateOperatorType || operatorType == NSNotEqualToPredicateOperatorType,
 816                     @"Invalid operator type", @"Only 'Equal' and 'Not Equal' operators supported for object comparison");
 817
 818     if (operatorType == NSEqualToPredicateOperatorType) {
 819         m_query.and_query(column.resolve<Link>() == null());
 820     }
 821     else {
 822         m_query.and_query(column.resolve<Link>() != null());
 823     }
 824 }
 825
 826 template<typename T>
 827 void QueryBuilder::add_link_constraint(NSPredicateOperatorType operatorType, T obj, const ColumnReference& column) {
 828     // Link constraints only support the equal-to and not-equal-to operators. The order of operands
 829     // is not important for those comparisons so we can delegate to the other implementation.
 830     add_link_constraint(operatorType, column, obj);
 831 }
 832
 833 void QueryBuilder::add_link_constraint(NSPredicateOperatorType, const ColumnReference&, const ColumnReference&) {
 834     // This is not actually reachable as this case is caught earlier, but this
 835     // overload is needed for the code to compile
 836     @throw RLMPredicateException(@"Invalid predicate", @"Comparisons between two RLMArray properties are not supported");
 837 }
 838
 839
 840 // iterate over an array of subpredicates, using @func to build a query from each
 841 // one and ORing them together
 842 template<typename Func>
 843 void process_or_group(Query &query, id array, Func&& func) {
 844     RLMPrecondition([array conformsToProtocol:@protocol(NSFastEnumeration)],
 845                     @"Invalid value", @"IN clause requires an array of items");
 846
 847     query.group();
 848
 849     bool first = true;
 850     for (id item in array) {
 851         if (!first) {
 852             query.Or();
 853         }
 854         first = false;
 855
 856         func(item);
 857     }
 858
 859     if (first) {
 860         // Queries can't be empty, so if there's zero things in the OR group
 861         // validation will fail. Work around this by adding an expression which
 862         // will never find any rows in a table.
 863         query.and_query(std::unique_ptr<Expression>(new FalseExpression));
 864     }
 865
 866     query.end_group();
 867 }
 868
 869 template <typename RequestedType>
 870 RequestedType convert(id value);
 871
 872 template <>
 873 Timestamp convert<Timestamp>(id value) {
 874     return RLMTimestampForNSDate(value);
 875 }
 876
 877 template <>
 878 bool convert<bool>(id value) {
 879     return [value boolValue];
 880 }
 881
 882 template <>
 883 Double convert<Double>(id value) {
 884     return [value doubleValue];
 885 }
 886
 887 template <>
 888 Float convert<Float>(id value) {
 889     return [value floatValue];
 890 }
 891
 892 template <>
 893 Int convert<Int>(id value) {
 894     return [value longLongValue];
 895 }
 896
 897 template <>
 898 String convert<String>(id value) {
 899     return RLMStringDataWithNSString(value);
 900 }
 901
 902 template <typename>
 903 realm::null value_of_type(realm::null) {
 904     return realm::null();
 905 }
 906
 907 template <typename RequestedType>
 908 auto value_of_type(id value) {
 909     return ::convert<RequestedType>(value);
 910 }
 911
 912 template <typename RequestedType>
 913 auto value_of_type(const ColumnReference& column) {
 914     return column.resolve<RequestedType>();
 915 }
 916
 917
 918 template <typename... T>
 919 void QueryBuilder::do_add_constraint(RLMPropertyType type, NSPredicateOperatorType operatorType,
 920                                      NSComparisonPredicateOptions predicateOptions, T... values)
 921 {
 922     static_assert(sizeof...(T) == 2, "do_add_constraint accepts only two values as arguments");
 923
 924     switch (type) {
 925         case RLMPropertyTypeBool:
 926             add_bool_constraint(operatorType, value_of_type<bool>(values)...);
 927             break;
 928         case RLMPropertyTypeDate:
 929             add_numeric_constraint(type, operatorType, value_of_type<realm::Timestamp>(values)...);
 930             break;
 931         case RLMPropertyTypeDouble:
 932             add_numeric_constraint(type, operatorType, value_of_type<Double>(values)...);
 933             break;
 934         case RLMPropertyTypeFloat:
 935             add_numeric_constraint(type, operatorType, value_of_type<Float>(values)...);
 936             break;
 937         case RLMPropertyTypeInt:
 938             add_numeric_constraint(type, operatorType, value_of_type<Int>(values)...);
 939             break;
 940         case RLMPropertyTypeString:
 941             add_string_constraint(operatorType, predicateOptions, value_of_type<String>(values)...);
 942             break;
 943         case RLMPropertyTypeData:
 944             add_binary_constraint(operatorType, values...);
 945             break;
 946         case RLMPropertyTypeObject:
 947         case RLMPropertyTypeLinkingObjects:
 948             add_link_constraint(operatorType, values...);
 949             break;
 950         default:
 951             @throw RLMPredicateException(@"Unsupported predicate value type",
 952                                          @"Object type %@ not supported", RLMTypeToString(type));
 953     }
 954 }
 955
 956 void QueryBuilder::do_add_constraint(RLMPropertyType, NSPredicateOperatorType, NSComparisonPredicateOptions, id, realm::null)
 957 {
 958     // This is not actually reachable as this case is caught earlier, but this
 959     // overload is needed for the code to compile
 960     @throw RLMPredicateException(@"Invalid predicate expressions",
 961                                  @"Predicate expressions must compare a keypath and another keypath or a constant value");
 962 }
 963
 964 bool is_nsnull(id value) {
 965     return !value || value == NSNull.null;
 966 }
 967
 968 template<typename T>
 969 bool is_nsnull(T) {
 970     return false;
 971 }
 972
 973 template <typename L, typename R>
 974 void QueryBuilder::add_constraint(RLMPropertyType type, NSPredicateOperatorType operatorType,
 975                                   NSComparisonPredicateOptions predicateOptions, L lhs, R rhs)
 976 {
 977     // The expression operators are only overloaded for realm::null on the rhs
 978     RLMPrecondition(!is_nsnull(lhs), @"Unsupported operator",
 979                     @"Nil is only supported on the right side of operators");
 980
 981     if (is_nsnull(rhs)) {
 982         do_add_constraint(type, operatorType, predicateOptions, lhs, realm::null());
 983     }
 984     else {
 985         do_add_constraint(type, operatorType, predicateOptions, lhs, rhs);
 986     }
 987 }
 988
 989 struct KeyPath {
 990     std::vector<RLMProperty *> links;
 991     RLMProperty *property;
 992     bool containsToManyRelationship;
 993 };
 994
 995 KeyPath key_path_from_string(RLMSchema *schema, RLMObjectSchema *objectSchema, NSString *keyPath)
 996 {
 997     RLMProperty *property;
 998     std::vector<RLMProperty *> links;
 999
1000     bool keyPathContainsToManyRelationship = false;
1001
1002     NSUInteger start = 0, length = keyPath.length, end = NSNotFound;
1003     do {
1004         end = [keyPath rangeOfString:@"." options:0 range:{start, length - start}].location;
1005         NSString *propertyName = [keyPath substringWithRange:{start, end == NSNotFound ? length - start : end - start}];
1006         property = objectSchema[propertyName];
1007         RLMPrecondition(property, @"Invalid property name",
1008                         @"Property '%@' not found in object of type '%@'",
1009                         propertyName, objectSchema.className);
1010
1011         if (property.array)
1012             keyPathContainsToManyRelationship = true;
1013
1014         if (end != NSNotFound) {
1015             RLMPrecondition(property.type == RLMPropertyTypeObject || property.type == RLMPropertyTypeLinkingObjects,
1016                             @"Invalid value", @"Property '%@' is not a link in object of type '%@'",
1017                             propertyName, objectSchema.className);
1018
1019             links.push_back(property);
1020             REALM_ASSERT(property.objectClassName);
1021             objectSchema = schema[property.objectClassName];
1022         }
1023
1024         start = end + 1;
1025     } while (end != NSNotFound);
1026
1027     return {std::move(links), property, keyPathContainsToManyRelationship};
1028 }
1029
1030 ColumnReference QueryBuilder::column_reference_from_key_path(RLMObjectSchema *objectSchema,
1031                                                              NSString *keyPathString, bool isAggregate)
1032 {
1033     auto keyPath = key_path_from_string(m_schema, objectSchema, keyPathString);
1034
1035     if (isAggregate && !keyPath.containsToManyRelationship) {
1036         @throw RLMPredicateException(@"Invalid predicate",
1037                                      @"Aggregate operations can only be used on key paths that include an array property");
1038     } else if (!isAggregate && keyPath.containsToManyRelationship) {
1039         @throw RLMPredicateException(@"Invalid predicate",
1040                                      @"Key paths that include an array property must use aggregate operations");
1041     }
1042
1043     return ColumnReference(m_query, m_group, m_schema, keyPath.property, std::move(keyPath.links));
1044 }
1045
1046 void validate_property_value(const ColumnReference& column,
1047                              __unsafe_unretained id const value,
1048                              __unsafe_unretained NSString *const err,
1049                              __unsafe_unretained RLMObjectSchema *const objectSchema,
1050                              __unsafe_unretained NSString *const keyPath) {
1051     RLMProperty *prop = column.property();
1052     if (prop.array) {
1053         RLMPrecondition([RLMObjectBaseObjectSchema(RLMDynamicCast<RLMObjectBase>(value)).className isEqualToString:prop.objectClassName],
1054                         @"Invalid value", err, prop.objectClassName, keyPath, objectSchema.className, value);
1055     }
1056     else {
1057         RLMPrecondition(RLMIsObjectValidForProperty(value, prop),
1058                         @"Invalid value", err, RLMTypeToString(prop.type), keyPath, objectSchema.className, value);
1059     }
1060     if (RLMObjectBase *obj = RLMDynamicCast<RLMObjectBase>(value)) {
1061         RLMPrecondition(!obj->_row.is_attached() || &column.group() == &obj->_realm.group,
1062                         @"Invalid value origin", @"Object must be from the Realm being queried");
1063     }
1064 }
1065
1066 template <typename RequestedType, CollectionOperation::Type OperationType>
1067 struct ValueOfTypeWithCollectionOperationHelper;
1068
1069 template <>
1070 struct ValueOfTypeWithCollectionOperationHelper<Int, CollectionOperation::Count> {
1071     static auto convert(const CollectionOperation& operation)
1072     {
1073         assert(operation.type() == CollectionOperation::Count);
1074         return operation.link_column().resolve<Link>().count();
1075     }
1076 };
1077
1078 #define VALUE_OF_TYPE_WITH_COLLECTION_OPERATOR_HELPER(OperationType, function) \
1079 template <typename T> \
1080 struct ValueOfTypeWithCollectionOperationHelper<T, OperationType> { \
1081     static auto convert(const CollectionOperation& operation) \
1082     { \
1083         REALM_ASSERT(operation.type() == OperationType); \
1084         auto targetColumn = operation.link_column().resolve<Link>().template column<T>(operation.column().index()); \
1085         return targetColumn.function(); \
1086     } \
1087 } \
1088
1089 VALUE_OF_TYPE_WITH_COLLECTION_OPERATOR_HELPER(CollectionOperation::Minimum, min);
1090 VALUE_OF_TYPE_WITH_COLLECTION_OPERATOR_HELPER(CollectionOperation::Maximum, max);
1091 VALUE_OF_TYPE_WITH_COLLECTION_OPERATOR_HELPER(CollectionOperation::Sum, sum);
1092 VALUE_OF_TYPE_WITH_COLLECTION_OPERATOR_HELPER(CollectionOperation::Average, average);
1093 #undef VALUE_OF_TYPE_WITH_COLLECTION_OPERATOR_HELPER
1094
1095 template <typename Requested, CollectionOperation::Type OperationType, typename T>
1096 auto value_of_type_with_collection_operation(T&& value) {
1097     return value_of_type<Requested>(std::forward<T>(value));
1098 }
1099
1100 template <typename Requested, CollectionOperation::Type OperationType>
1101 auto value_of_type_with_collection_operation(CollectionOperation operation) {
1102     using helper = ValueOfTypeWithCollectionOperationHelper<Requested, OperationType>;
1103     return helper::convert(operation);
1104 }
1105
1106 template <CollectionOperation::Type Operation, typename... T>
1107 void QueryBuilder::add_collection_operation_constraint(RLMPropertyType propertyType, NSPredicateOperatorType operatorType, T... values)
1108 {
1109     switch (propertyType) {
1110         case RLMPropertyTypeInt:
1111             add_numeric_constraint(propertyType, operatorType, value_of_type_with_collection_operation<Int, Operation>(values)...);
1112             break;
1113         case RLMPropertyTypeFloat:
1114             add_numeric_constraint(propertyType, operatorType, value_of_type_with_collection_operation<Float, Operation>(values)...);
1115             break;
1116         case RLMPropertyTypeDouble:
1117             add_numeric_constraint(propertyType, operatorType, value_of_type_with_collection_operation<Double, Operation>(values)...);
1118             break;
1119         default:
1120             REALM_ASSERT(false && "Only numeric property types should hit this path.");
1121     }
1122 }
1123
1124 template <typename... T>
1125 void QueryBuilder::add_collection_operation_constraint(NSPredicateOperatorType operatorType,
1126                                                   CollectionOperation collectionOperation, T... values)
1127 {
1128     static_assert(sizeof...(T) == 2, "add_collection_operation_constraint accepts only two values as arguments");
1129
1130     switch (collectionOperation.type()) {
1131         case CollectionOperation::Count:
1132             add_numeric_constraint(RLMPropertyTypeInt, operatorType,
1133                                    value_of_type_with_collection_operation<Int, CollectionOperation::Count>(values)...);
1134             break;
1135         case CollectionOperation::Minimum:
1136             add_collection_operation_constraint<CollectionOperation::Minimum>(collectionOperation.column().type(), operatorType, values...);
1137             break;
1138         case CollectionOperation::Maximum:
1139             add_collection_operation_constraint<CollectionOperation::Maximum>(collectionOperation.column().type(), operatorType, values...);
1140             break;
1141         case CollectionOperation::Sum:
1142             add_collection_operation_constraint<CollectionOperation::Sum>(collectionOperation.column().type(), operatorType, values...);
1143             break;
1144         case CollectionOperation::Average:
1145             add_collection_operation_constraint<CollectionOperation::Average>(collectionOperation.column().type(), operatorType, values...);
1146             break;
1147     }
1148 }
1149
1150 bool key_path_contains_collection_operator(NSString *keyPath) {
1151     return [keyPath rangeOfString:@"@"].location != NSNotFound;
1152 }
1153
1154 NSString *get_collection_operation_name_from_key_path(NSString *keyPath, NSString **leadingKeyPath,
1155                                                       NSString **trailingKey) {
1156     NSRange at  = [keyPath rangeOfString:@"@"];
1157     if (at.location == NSNotFound || at.location >= keyPath.length - 1) {
1158         @throw RLMPredicateException(@"Invalid key path", @"'%@' is not a valid key path'", keyPath);
1159     }
1160
1161     if (at.location == 0 || [keyPath characterAtIndex:at.location - 1] != '.') {
1162         @throw RLMPredicateException(@"Invalid key path", @"'%@' is not a valid key path'", keyPath);
1163     }
1164
1165     NSRange trailingKeyRange = [keyPath rangeOfString:@"." options:0 range:{at.location, keyPath.length - at.location} locale:nil];
1166
1167     *leadingKeyPath = [keyPath substringToIndex:at.location - 1];
1168     if (trailingKeyRange.location == NSNotFound) {
1169         *trailingKey = nil;
1170         return [keyPath substringFromIndex:at.location];
1171     } else {
1172         *trailingKey = [keyPath substringFromIndex:trailingKeyRange.location + 1];
1173         return [keyPath substringWithRange:{at.location, trailingKeyRange.location - at.location}];
1174     }
1175 }
1176
1177 CollectionOperation QueryBuilder::collection_operation_from_key_path(RLMObjectSchema *desc, NSString *keyPath) {
1178     NSString *leadingKeyPath;
1179     NSString *trailingKey;
1180     NSString *collectionOperationName = get_collection_operation_name_from_key_path(keyPath, &leadingKeyPath, &trailingKey);
1181
1182     ColumnReference linkColumn = column_reference_from_key_path(desc, leadingKeyPath, true);
1183     util::Optional<ColumnReference> column;
1184     if (trailingKey) {
1185         RLMPrecondition([trailingKey rangeOfString:@"."].location == NSNotFound, @"Invalid key path",
1186                         @"Right side of collection operator may only have a single level key");
1187         NSString *fullKeyPath = [leadingKeyPath stringByAppendingFormat:@".%@", trailingKey];
1188         column = column_reference_from_key_path(desc, fullKeyPath, true);
1189     }
1190
1191     return {collectionOperationName, std::move(linkColumn), std::move(column)};
1192 }
1193
1194 void QueryBuilder::apply_collection_operator_expression(RLMObjectSchema *desc,
1195                                                         NSString *keyPath, id value,
1196                                                         NSComparisonPredicate *pred) {
1197     CollectionOperation operation = collection_operation_from_key_path(desc, keyPath);
1198     operation.validate_comparison(value);
1199
1200     if (pred.leftExpression.expressionType == NSKeyPathExpressionType) {
1201         add_collection_operation_constraint(pred.predicateOperatorType, operation, operation, value);
1202     } else {
1203         add_collection_operation_constraint(pred.predicateOperatorType, operation, value, operation);
1204     }
1205 }
1206
1207 void QueryBuilder::apply_value_expression(RLMObjectSchema *desc,
1208                                           NSString *keyPath, id value,
1209                                           NSComparisonPredicate *pred)
1210 {
1211     if (key_path_contains_collection_operator(keyPath)) {
1212         apply_collection_operator_expression(desc, keyPath, value, pred);
1213         return;
1214     }
1215
1216     bool isAny = pred.comparisonPredicateModifier == NSAnyPredicateModifier;
1217     ColumnReference column = column_reference_from_key_path(desc, keyPath, isAny);
1218
1219     // check to see if this is a between query
1220     if (pred.predicateOperatorType == NSBetweenPredicateOperatorType) {
1221         add_between_constraint(std::move(column), value);
1222         return;
1223     }
1224
1225     // turn "key.path IN collection" into ored together ==. "collection IN key.path" is handled elsewhere.
1226     if (pred.predicateOperatorType == NSInPredicateOperatorType) {
1227         process_or_group(m_query, value, [&](id item) {
1228             id normalized = value_from_constant_expression_or_value(item);
1229             validate_property_value(column, normalized,
1230                                     @"Expected object of type %@ in IN clause for property '%@' on object of type '%@', but received: %@", desc, keyPath);
1231             add_constraint(column.type(), NSEqualToPredicateOperatorType, pred.options, column, normalized);
1232         });
1233         return;
1234     }
1235
1236     validate_property_value(column, value, @"Expected object of type %@ for property '%@' on object of type '%@', but received: %@", desc, keyPath);
1237     if (pred.leftExpression.expressionType == NSKeyPathExpressionType) {
1238         add_constraint(column.type(), pred.predicateOperatorType, pred.options, std::move(column), value);
1239     } else {
1240         add_constraint(column.type(), pred.predicateOperatorType, pred.options, value, std::move(column));
1241     }
1242 }
1243
1244 void QueryBuilder::apply_column_expression(RLMObjectSchema *desc,
1245                                            NSString *leftKeyPath, NSString *rightKeyPath,
1246                                            NSComparisonPredicate *predicate)
1247 {
1248     bool left_key_path_contains_collection_operator = key_path_contains_collection_operator(leftKeyPath);
1249     bool right_key_path_contains_collection_operator = key_path_contains_collection_operator(rightKeyPath);
1250     if (left_key_path_contains_collection_operator && right_key_path_contains_collection_operator) {
1251         @throw RLMPredicateException(@"Unsupported predicate", @"Key paths including aggregate operations cannot be compared with other aggregate operations.");
1252     }
1253
1254     if (left_key_path_contains_collection_operator) {
1255         CollectionOperation left = collection_operation_from_key_path(desc, leftKeyPath);
1256         ColumnReference right = column_reference_from_key_path(desc, rightKeyPath, false);
1257         left.validate_comparison(right);
1258         add_collection_operation_constraint(predicate.predicateOperatorType, left, left, std::move(right));
1259         return;
1260     }
1261     if (right_key_path_contains_collection_operator) {
1262         ColumnReference left = column_reference_from_key_path(desc, leftKeyPath, false);
1263         CollectionOperation right = collection_operation_from_key_path(desc, rightKeyPath);
1264         right.validate_comparison(left);
1265         add_collection_operation_constraint(predicate.predicateOperatorType, right, std::move(left), right);
1266         return;
1267     }
1268
1269     bool isAny = false;
1270     ColumnReference left = column_reference_from_key_path(desc, leftKeyPath, isAny);
1271     ColumnReference right = column_reference_from_key_path(desc, rightKeyPath, isAny);
1272
1273     // NOTE: It's assumed that column type must match and no automatic type conversion is supported.
1274     RLMPrecondition(left.type() == right.type(),
1275                     RLMPropertiesComparisonTypeMismatchException,
1276                     RLMPropertiesComparisonTypeMismatchReason,
1277                     RLMTypeToString(left.type()),
1278                     RLMTypeToString(right.type()));
1279
1280     // TODO: Should we handle special case where left row is the same as right row (tautology)
1281     add_constraint(left.type(), predicate.predicateOperatorType, predicate.options,
1282                    std::move(left), std::move(right));
1283 }
1284
1285 // Identify expressions of the form [SELF valueForKeyPath:]
1286 bool is_self_value_for_key_path_function_expression(NSExpression *expression)
1287 {
1288     if (expression.expressionType != NSFunctionExpressionType)
1289         return false;
1290
1291     if (expression.operand.expressionType != NSEvaluatedObjectExpressionType)
1292         return false;
1293
1294     return [expression.function isEqualToString:@"valueForKeyPath:"];
1295 }
1296
1297 // -[NSPredicate predicateWithSubtitutionVariables:] results in function expressions of the form [SELF valueForKeyPath:]
1298 // that apply_predicate cannot handle. Replace such expressions with equivalent NSKeyPathExpressionType expressions.
1299 NSExpression *simplify_self_value_for_key_path_function_expression(NSExpression *expression) {
1300     if (is_self_value_for_key_path_function_expression(expression)) {
1301         if (NSString *keyPath = [expression.arguments.firstObject keyPath]) {
1302             return [NSExpression expressionForKeyPath:keyPath];
1303         }
1304     }
1305     return expression;
1306 }
1307
1308 void QueryBuilder::apply_subquery_count_expression(RLMObjectSchema *objectSchema,
1309                                                    NSExpression *subqueryExpression, NSPredicateOperatorType operatorType, NSExpression *right) {
1310     if (right.expressionType != NSConstantValueExpressionType || ![right.constantValue isKindOfClass:[NSNumber class]]) {
1311         @throw RLMPredicateException(@"Invalid predicate expression", @"SUBQUERY(…).@count is only supported when compared with a constant number.");
1312     }
1313     int64_t value = [right.constantValue integerValue];
1314
1315     ColumnReference collectionColumn = column_reference_from_key_path(objectSchema, [subqueryExpression.collection keyPath], true);
1316     RLMObjectSchema *collectionMemberObjectSchema = m_schema[collectionColumn.property().objectClassName];
1317
1318     // Eliminate references to the iteration variable in the subquery.
1319     NSPredicate *subqueryPredicate = [subqueryExpression.predicate predicateWithSubstitutionVariables:@{ subqueryExpression.variable : [NSExpression expressionForEvaluatedObject] }];
1320     subqueryPredicate = transformPredicate(subqueryPredicate, simplify_self_value_for_key_path_function_expression);
1321
1322     Query subquery = RLMPredicateToQuery(subqueryPredicate, collectionMemberObjectSchema, m_schema, m_group);
1323     add_numeric_constraint(RLMPropertyTypeInt, operatorType,
1324                            collectionColumn.resolve<LinkList>(std::move(subquery)).count(), value);
1325 }
1326
1327 void QueryBuilder::apply_function_subquery_expression(RLMObjectSchema *objectSchema, NSExpression *functionExpression,
1328                                                       NSPredicateOperatorType operatorType, NSExpression *right) {
1329     if (![functionExpression.function isEqualToString:@"valueForKeyPath:"] || functionExpression.arguments.count != 1) {
1330         @throw RLMPredicateException(@"Invalid predicate", @"The '%@' function is not supported on the result of a SUBQUERY.", functionExpression.function);
1331     }
1332
1333     NSExpression *keyPathExpression = functionExpression.arguments.firstObject;
1334     if ([keyPathExpression.keyPath isEqualToString:@"@count"]) {
1335         apply_subquery_count_expression(objectSchema, functionExpression.operand,  operatorType, right);
1336     } else {
1337         @throw RLMPredicateException(@"Invalid predicate", @"SUBQUERY is only supported when immediately followed by .@count that is compared with a constant number.");
1338     }
1339 }
1340
1341 void QueryBuilder::apply_function_expression(RLMObjectSchema *objectSchema, NSExpression *functionExpression,
1342                                              NSPredicateOperatorType operatorType, NSExpression *right) {
1343     if (functionExpression.operand.expressionType == NSSubqueryExpressionType) {
1344         apply_function_subquery_expression(objectSchema, functionExpression, operatorType, right);
1345     } else {
1346         @throw RLMPredicateException(@"Invalid predicate", @"The '%@' function is not supported.", functionExpression.function);
1347     }
1348 }
1349
1350
1351 void QueryBuilder::apply_predicate(NSPredicate *predicate, RLMObjectSchema *objectSchema)
1352 {
1353     // Compound predicates.
1354     if ([predicate isMemberOfClass:[NSCompoundPredicate class]]) {
1355         NSCompoundPredicate *comp = (NSCompoundPredicate *)predicate;
1356
1357         switch ([comp compoundPredicateType]) {
1358             case NSAndPredicateType:
1359                 if (comp.subpredicates.count) {
1360                     // Add all of the subpredicates.
1361                     m_query.group();
1362                     for (NSPredicate *subp in comp.subpredicates) {
1363                         apply_predicate(subp, objectSchema);
1364                     }
1365                     m_query.end_group();
1366                 } else {
1367                     // NSCompoundPredicate's documentation states that an AND predicate with no subpredicates evaluates to TRUE.
1368                     m_query.and_query(std::unique_ptr<Expression>(new TrueExpression));
1369                 }
1370                 break;
1371
1372             case NSOrPredicateType: {
1373                 // Add all of the subpredicates with ors inbetween.
1374                 process_or_group(m_query, comp.subpredicates, [&](__unsafe_unretained NSPredicate *const subp) {
1375                     apply_predicate(subp, objectSchema);
1376                 });
1377                 break;
1378             }
1379
1380             case NSNotPredicateType:
1381                 // Add the negated subpredicate
1382                 m_query.Not();
1383                 apply_predicate(comp.subpredicates.firstObject, objectSchema);
1384                 break;
1385
1386             default:
1387                 @throw RLMPredicateException(@"Invalid compound predicate type",
1388                                              @"Only support AND, OR and NOT predicate types");
1389         }
1390     }
1391     else if ([predicate isMemberOfClass:[NSComparisonPredicate class]]) {
1392         NSComparisonPredicate *compp = (NSComparisonPredicate *)predicate;
1393
1394         // check modifier
1395         RLMPrecondition(compp.comparisonPredicateModifier != NSAllPredicateModifier,
1396                         @"Invalid predicate", @"ALL modifier not supported");
1397
1398         NSExpressionType exp1Type = compp.leftExpression.expressionType;
1399         NSExpressionType exp2Type = compp.rightExpression.expressionType;
1400
1401         if (compp.comparisonPredicateModifier == NSAnyPredicateModifier) {
1402             // for ANY queries
1403             RLMPrecondition(exp1Type == NSKeyPathExpressionType && exp2Type == NSConstantValueExpressionType,
1404                             @"Invalid predicate",
1405                             @"Predicate with ANY modifier must compare a KeyPath with RLMArray with a value");
1406         }
1407
1408         if (compp.predicateOperatorType == NSBetweenPredicateOperatorType || compp.predicateOperatorType == NSInPredicateOperatorType) {
1409             // Inserting an array via %@ gives NSConstantValueExpressionType, but including it directly gives NSAggregateExpressionType
1410             if (exp1Type == NSKeyPathExpressionType && (exp2Type == NSAggregateExpressionType || exp2Type == NSConstantValueExpressionType)) {
1411                 // "key.path IN %@", "key.path IN {…}", "key.path BETWEEN %@", or "key.path BETWEEN {…}".
1412                 exp2Type = NSConstantValueExpressionType;
1413             }
1414             else if (compp.predicateOperatorType == NSInPredicateOperatorType && exp1Type == NSConstantValueExpressionType && exp2Type == NSKeyPathExpressionType) {
1415                 // "%@ IN key.path" is equivalent to "ANY key.path IN %@". Rewrite the former into the latter.
1416                 compp = [NSComparisonPredicate predicateWithLeftExpression:compp.rightExpression rightExpression:compp.leftExpression
1417                                                                   modifier:NSAnyPredicateModifier type:NSEqualToPredicateOperatorType options:0];
1418                 exp1Type = NSKeyPathExpressionType;
1419                 exp2Type = NSConstantValueExpressionType;
1420             }
1421             else {
1422                 if (compp.predicateOperatorType == NSBetweenPredicateOperatorType) {
1423                     @throw RLMPredicateException(@"Invalid predicate",
1424                                                  @"Predicate with BETWEEN operator must compare a KeyPath with an aggregate with two values");
1425                 }
1426                 else if (compp.predicateOperatorType == NSInPredicateOperatorType) {
1427                     @throw RLMPredicateException(@"Invalid predicate",
1428                                                  @"Predicate with IN operator must compare a KeyPath with an aggregate");
1429                 }
1430             }
1431         }
1432
1433         if (exp1Type == NSKeyPathExpressionType && exp2Type == NSKeyPathExpressionType) {
1434             // both expression are KeyPaths
1435             apply_column_expression(objectSchema, compp.leftExpression.keyPath, compp.rightExpression.keyPath, compp);
1436         }
1437         else if (exp1Type == NSKeyPathExpressionType && exp2Type == NSConstantValueExpressionType) {
1438             // comparing keypath to value
1439             apply_value_expression(objectSchema, compp.leftExpression.keyPath, compp.rightExpression.constantValue, compp);
1440         }
1441         else if (exp1Type == NSConstantValueExpressionType && exp2Type == NSKeyPathExpressionType) {
1442             // comparing value to keypath
1443             apply_value_expression(objectSchema, compp.rightExpression.keyPath, compp.leftExpression.constantValue, compp);
1444         }
1445         else if (exp1Type == NSFunctionExpressionType) {
1446             apply_function_expression(objectSchema, compp.leftExpression, compp.predicateOperatorType, compp.rightExpression);
1447         }
1448         else if (exp1Type == NSSubqueryExpressionType) {
1449             // The subquery expressions that we support are handled by the NSFunctionExpressionType case above.
1450             @throw RLMPredicateException(@"Invalid predicate expression", @"SUBQUERY is only supported when immediately followed by .@count.");
1451         }
1452         else {
1453             @throw RLMPredicateException(@"Invalid predicate expressions",
1454                                          @"Predicate expressions must compare a keypath and another keypath or a constant value");
1455         }
1456     }
1457     else if ([predicate isEqual:[NSPredicate predicateWithValue:YES]]) {
1458         m_query.and_query(std::unique_ptr<Expression>(new TrueExpression));
1459     } else if ([predicate isEqual:[NSPredicate predicateWithValue:NO]]) {
1460         m_query.and_query(std::unique_ptr<Expression>(new FalseExpression));
1461     }
1462     else {
1463         // invalid predicate type
1464         @throw RLMPredicateException(@"Invalid predicate",
1465                                      @"Only support compound, comparison, and constant predicates");
1466     }
1467 }
1468 } // namespace
1469
1470 realm::Query RLMPredicateToQuery(NSPredicate *predicate, RLMObjectSchema *objectSchema,
1471                                  RLMSchema *schema, Group &group)
1472 {
1473     auto query = get_table(group, objectSchema).where();
1474
1475     // passing a nil predicate is a no-op
1476     if (!predicate) {
1477         return query;
1478     }
1479
1480     @autoreleasepool {
1481         QueryBuilder(query, group, schema).apply_predicate(predicate, objectSchema);
1482     }
1483
1484     // Test the constructed query in core
1485     std::string validateMessage = query.validate();
1486     RLMPrecondition(validateMessage.empty(), @"Invalid query", @"%.*s",
1487                     (int)validateMessage.size(), validateMessage.c_str());
1488     return query;
1489 }