iOS/Pods/Realm/include/core/realm/query_engine.hpp

   1 /*************************************************************************
   2  *
   3  * Copyright 2016 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 /*
  20 A query consists of node objects, one for each query condition. Each node contains pointers to all other nodes:
  21
  22 node1        node2         node3
  23 ------       -----         -----
  24 node2*       node1*        node1*
  25 node3*       node3*        node2*
  26
  27 The construction of all this takes part in query.cpp. Each node has two important functions:
  28
  29     aggregate(start, end)
  30     aggregate_local(start, end)
  31
  32 The aggregate() function executes the aggregate of a query. You can call the method on any of the nodes
  33 (except children nodes of OrNode and SubtableNode) - it has the same behaviour. The function contains
  34 scheduling that calls aggregate_local(start, end) on different nodes with different start/end ranges,
  35 depending on what it finds is most optimal.
  36
  37 The aggregate_local() function contains a tight loop that tests the condition of its own node, and upon match
  38 it tests all other conditions at that index to report a full match or not. It will remain in the tight loop
  39 after a full match.
  40
  41 So a call stack with 2 and 9 being local matches of a node could look like this:
  42
  43 aggregate(0, 10)
  44     node1->aggregate_local(0, 3)
  45         node2->find_first_local(2, 3)
  46         node3->find_first_local(2, 3)
  47     node3->aggregate_local(3, 10)
  48         node1->find_first_local(4, 5)
  49         node2->find_first_local(4, 5)
  50         node1->find_first_local(7, 8)
  51         node2->find_first_local(7, 8)
  52
  53 find_first_local(n, n + 1) is a function that can be used to test a single row of another condition. Note that
  54 this is very simplified. There are other statistical arguments to the methods, and also, find_first_local() can be
  55 called from a callback function called by an integer Array.
  56
  57
  58 Template arguments in methods:
  59 ----------------------------------------------------------------------------------------------------
  60
  61 TConditionFunction: Each node has a condition from query_conditions.c such as Equal, GreaterEqual, etc
  62
  63 TConditionValue:    Type of values in condition column. That is, int64_t, float, int, bool, etc
  64
  65 TAction:            What to do with each search result, from the enums act_ReturnFirst, act_Count, act_Sum, etc
  66
  67 TResult:            Type of result of actions - float, double, int64_t, etc. Special notes: For act_Count it's
  68                     int64_t, for RLM_FIND_ALL it's int64_t which points at destination array.
  69
  70 TSourceColumn:      Type of source column used in actions, or *ignored* if no source column is used (like for
  71                     act_Count, act_ReturnFirst)
  72
  73
  74 There are two important classes used in queries:
  75 ----------------------------------------------------------------------------------------------------
  76 SequentialGetter    Column iterator used to get successive values with leaf caching. Used both for condition columns
  77                     and aggregate source column
  78
  79 AggregateState      State of the aggregate - contains a state variable that stores intermediate sum, max, min,
  80                     etc, etc.
  81
  82 */
  83
  84 #ifndef REALM_QUERY_ENGINE_HPP
  85 #define REALM_QUERY_ENGINE_HPP
  86
  87 #include <algorithm>
  88 #include <functional>
  89 #include <sstream>
  90 #include <string>
  91 #include <array>
  92
  93 #include <realm/array_basic.hpp>
  94 #include <realm/array_string.hpp>
  95 #include <realm/column_binary.hpp>
  96 #include <realm/column_fwd.hpp>
  97 #include <realm/column_link.hpp>
  98 #include <realm/column_linklist.hpp>
  99 #include <realm/column_mixed.hpp>
 100 #include <realm/column_string.hpp>
 101 #include <realm/column_string_enum.hpp>
 102 #include <realm/column_table.hpp>
 103 #include <realm/column_timestamp.hpp>
 104 #include <realm/column_type_traits.hpp>
 105 #include <realm/column_type_traits.hpp>
 106 #include <realm/impl/sequential_getter.hpp>
 107 #include <realm/link_view.hpp>
 108 #include <realm/metrics/query_info.hpp>
 109 #include <realm/query_conditions.hpp>
 110 #include <realm/query_operators.hpp>
 111 #include <realm/table.hpp>
 112 #include <realm/unicode.hpp>
 113 #include <realm/util/miscellaneous.hpp>
 114 #include <realm/util/serializer.hpp>
 115 #include <realm/util/shared_ptr.hpp>
 116 #include <realm/utilities.hpp>
 117
 118 #include <map>
 119
 120 #if REALM_X86_OR_X64_TRUE && defined(_MSC_FULL_VER) && _MSC_FULL_VER >= 160040219
 121 #include <immintrin.h>
 122 #endif
 123
 124 namespace realm {
 125
 126 // Number of matches to find in best condition loop before breaking out to probe other conditions. Too low value gives
 127 // too many constant time overheads everywhere in the query engine. Too high value makes it adapt less rapidly to
 128 // changes in match frequencies.
 129 const size_t findlocals = 64;
 130
 131 // Average match distance in linear searches where further increase in distance no longer increases query speed
 132 // (because time spent on handling each match becomes insignificant compared to time spent on the search).
 133 const size_t bestdist = 512;
 134
 135 // Minimum number of matches required in a certain condition before it can be used to compute statistics. Too high
 136 // value can spent too much time in a bad node (with high match frequency). Too low value gives inaccurate statistics.
 137 const size_t probe_matches = 4;
 138
 139 const size_t bitwidth_time_unit = 64;
 140
 141 typedef bool (*CallbackDummy)(int64_t);
 142
 143 class ParentNode {
 144     typedef ParentNode ThisType;
 145
 146 public:
 147     ParentNode() = default;
 148     virtual ~ParentNode() = default;
 149
 150     void gather_children(std::vector<ParentNode*>& v)
 151     {
 152         m_children.clear();
 153         size_t i = v.size();
 154         v.push_back(this);
 155
 156         if (m_child)
 157             m_child->gather_children(v);
 158
 159         m_children = v;
 160         m_children.erase(m_children.begin() + i);
 161         m_children.insert(m_children.begin(), this);
 162     }
 163
 164     double cost() const
 165     {
 166         return 8 * bitwidth_time_unit / m_dD +
 167                m_dT; // dt = 1/64 to 1. Match dist is 8 times more important than bitwidth
 168     }
 169
 170     size_t find_first(size_t start, size_t end);
 171
 172     virtual void init()
 173     {
 174         // Verify that the cached column accessor is still valid
 175         verify_column(); // throws
 176
 177         if (m_child)
 178             m_child->init();
 179
 180         m_column_action_specializer = nullptr;
 181     }
 182
 183     void set_table(const Table& table)
 184     {
 185         if (&table == m_table)
 186             return;
 187
 188         m_table.reset(&table);
 189         if (m_child)
 190             m_child->set_table(table);
 191         table_changed();
 192     }
 193
 194     virtual size_t find_first_local(size_t start, size_t end) = 0;
 195
 196     virtual void aggregate_local_prepare(Action TAction, DataType col_id, bool nullable);
 197
 198     template <Action TAction, class TSourceColumn>
 199     bool column_action_specialization(QueryStateBase* st, SequentialGetterBase* source_column, size_t r)
 200     {
 201         // TResult: type of query result
 202         // TSourceValue: type of aggregate source
 203         using TSourceValue = typename TSourceColumn::value_type;
 204         using TResult = typename ColumnTypeTraitsSum<TSourceValue, TAction>::sum_type;
 205
 206         // Sum of float column must accumulate in double
 207         static_assert(!(TAction == act_Sum &&
 208                         (std::is_same<TSourceColumn, float>::value && !std::is_same<TResult, double>::value)),
 209                       "");
 210
 211         TSourceValue av{};
 212         // uses_val test because compiler cannot see that IntegerColumn::get has no side effect and result is
 213         // discarded
 214         if (static_cast<QueryState<TResult>*>(st)->template uses_val<TAction>() && source_column != nullptr) {
 215             REALM_ASSERT_DEBUG(dynamic_cast<SequentialGetter<TSourceColumn>*>(source_column) != nullptr);
 216             av = static_cast<SequentialGetter<TSourceColumn>*>(source_column)->get_next(r);
 217         }
 218         REALM_ASSERT_DEBUG(dynamic_cast<QueryState<TResult>*>(st) != nullptr);
 219         bool cont = static_cast<QueryState<TResult>*>(st)->template match<TAction, 0>(r, 0, av);
 220         return cont;
 221     }
 222
 223     virtual size_t aggregate_local(QueryStateBase* st, size_t start, size_t end, size_t local_limit,
 224                                    SequentialGetterBase* source_column);
 225
 226
 227     virtual std::string validate()
 228     {
 229         if (error_code != "")
 230             return error_code;
 231         if (m_child == nullptr)
 232             return "";
 233         else
 234             return m_child->validate();
 235     }
 236
 237     ParentNode(const ParentNode& from)
 238         : ParentNode(from, nullptr)
 239     {
 240     }
 241
 242     ParentNode(const ParentNode& from, QueryNodeHandoverPatches* patches)
 243         : m_child(from.m_child ? from.m_child->clone(patches) : nullptr)
 244         , m_condition_column_idx(from.m_condition_column_idx)
 245         , m_dD(from.m_dD)
 246         , m_dT(from.m_dT)
 247         , m_probes(from.m_probes)
 248         , m_matches(from.m_matches)
 249         , m_table(patches ? ConstTableRef{} : from.m_table)
 250     {
 251     }
 252
 253     void add_child(std::unique_ptr<ParentNode> child)
 254     {
 255         if (m_child)
 256             m_child->add_child(std::move(child));
 257         else
 258             m_child = std::move(child);
 259     }
 260
 261     virtual std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* = nullptr) const = 0;
 262
 263     virtual void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group)
 264     {
 265         if (m_child)
 266             m_child->apply_handover_patch(patches, group);
 267     }
 268
 269     virtual void verify_column() const = 0;
 270
 271     virtual std::string describe_column() const
 272     {
 273         return describe_column(m_condition_column_idx);
 274     }
 275
 276     virtual std::string describe_column(size_t col_ndx) const
 277     {
 278         if (m_table && col_ndx != npos) {
 279             return std::string(m_table->get_column_name(col_ndx));
 280         }
 281         return "";
 282     }
 283
 284     virtual std::string describe() const
 285     {
 286         return "";
 287     }
 288
 289     virtual std::string describe_condition() const
 290     {
 291         return "matches";
 292     }
 293
 294     virtual std::string describe_expression() const
 295     {
 296         std::string s;
 297         s = describe();
 298         if (m_child) {
 299             s = s + " and " + m_child->describe_expression();
 300         }
 301         return s;
 302     }
 303
 304     std::unique_ptr<ParentNode> m_child;
 305     std::vector<ParentNode*> m_children;
 306     size_t m_condition_column_idx = npos; // Column of search criteria
 307
 308     double m_dD;       // Average row distance between each local match at current position
 309     double m_dT = 0.0; // Time overhead of testing index i + 1 if we have just tested index i. > 1 for linear scans, 0
 310     // for index/tableview
 311
 312     size_t m_probes = 0;
 313     size_t m_matches = 0;
 314
 315 protected:
 316     typedef bool (ParentNode::*Column_action_specialized)(QueryStateBase*, SequentialGetterBase*, size_t);
 317     Column_action_specialized m_column_action_specializer;
 318     ConstTableRef m_table;
 319     std::string error_code;
 320
 321     const ColumnBase& get_column_base(size_t ndx)
 322     {
 323         return m_table->get_column_base(ndx);
 324     }
 325
 326     template <class ColType>
 327     const ColType& get_column(size_t ndx)
 328     {
 329         auto& col = m_table->get_column_base(ndx);
 330         REALM_ASSERT_DEBUG(dynamic_cast<const ColType*>(&col));
 331         return static_cast<const ColType&>(col);
 332     }
 333
 334     ColumnType get_real_column_type(size_t ndx)
 335     {
 336         return m_table->get_real_column_type(ndx);
 337     }
 338
 339     template <class ColType>
 340     void copy_getter(SequentialGetter<ColType>& dst, size_t& dst_idx, const SequentialGetter<ColType>& src,
 341                      const QueryNodeHandoverPatches* patches)
 342     {
 343         if (src.m_column) {
 344             if (patches)
 345                 dst_idx = src.m_column->get_column_index();
 346             else
 347                 dst.init(src.m_column);
 348         }
 349     }
 350
 351     void do_verify_column(const ColumnBase* col, size_t col_ndx = npos) const
 352     {
 353         if (col_ndx == npos)
 354             col_ndx = m_condition_column_idx;
 355         if (m_table && col_ndx != npos) {
 356             m_table->verify_column(col_ndx, col);
 357         }
 358     }
 359
 360 private:
 361     virtual void table_changed() = 0;
 362 };
 363
 364 // For conditions on a subtable (encapsulated in subtable()...end_subtable()). These return the parent row as match if
 365 // and only if one or more subtable rows match the condition.
 366 class SubtableNode : public ParentNode {
 367 public:
 368     SubtableNode(size_t column, std::unique_ptr<ParentNode> condition)
 369         : m_condition(std::move(condition))
 370     {
 371         m_dT = 100.0;
 372         m_condition_column_idx = column;
 373     }
 374
 375     void init() override
 376     {
 377         ParentNode::init();
 378
 379         m_dD = 10.0;
 380
 381         // m_condition is first node in condition of subtable query.
 382         if (m_condition) {
 383             // Can't call init() here as usual since the subtable can be degenerate
 384             // m_condition->init(table);
 385             std::vector<ParentNode*> v;
 386             m_condition->gather_children(v);
 387         }
 388     }
 389
 390     void table_changed() override
 391     {
 392         m_col_type = m_table->get_real_column_type(m_condition_column_idx);
 393         REALM_ASSERT(m_col_type == col_type_Table || m_col_type == col_type_Mixed);
 394         if (m_col_type == col_type_Table)
 395             m_column = &m_table->get_column_table(m_condition_column_idx);
 396         else // Mixed
 397             m_column = &m_table->get_column_mixed(m_condition_column_idx);
 398     }
 399
 400     void verify_column() const override
 401     {
 402         if (m_table)
 403             m_table->verify_column(m_condition_column_idx, m_column);
 404     }
 405
 406     std::string validate() override
 407     {
 408         if (error_code != "")
 409             return error_code;
 410         if (m_condition == nullptr)
 411             return "Unbalanced subtable/end_subtable block";
 412         else
 413             return m_condition->validate();
 414     }
 415     std::string describe() const override
 416     {
 417         return "subtable expression";
 418     }
 419
 420
 421     size_t find_first_local(size_t start, size_t end) override
 422     {
 423         REALM_ASSERT(m_table);
 424         REALM_ASSERT(m_condition);
 425
 426         for (size_t s = start; s < end; ++s) {
 427             ConstTableRef subtable; // TBD: optimize this back to Table*
 428             if (m_col_type == col_type_Table)
 429                 subtable = static_cast<const SubtableColumn*>(m_column)->get_subtable_tableref(s);
 430             else {
 431                 subtable = static_cast<const MixedColumn*>(m_column)->get_subtable_tableref(s);
 432                 if (!subtable)
 433                     continue;
 434             }
 435
 436             if (subtable->is_degenerate())
 437                 return not_found;
 438
 439             m_condition->set_table(*subtable);
 440             m_condition->init();
 441             const size_t subsize = subtable->size();
 442             const size_t sub = m_condition->find_first(0, subsize);
 443
 444             if (sub != not_found)
 445                 return s;
 446         }
 447         return not_found;
 448     }
 449
 450     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
 451     {
 452         return std::unique_ptr<ParentNode>(new SubtableNode(*this, patches));
 453     }
 454
 455     SubtableNode(const SubtableNode& from, QueryNodeHandoverPatches* patches)
 456         : ParentNode(from, patches)
 457         , m_condition(from.m_condition ? from.m_condition->clone(patches) : nullptr)
 458         , m_column(from.m_column)
 459         , m_col_type(from.m_col_type)
 460     {
 461         if (m_column && patches)
 462             m_condition_column_idx = m_column->get_column_index();
 463     }
 464
 465     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
 466     {
 467         m_condition->apply_handover_patch(patches, group);
 468         ParentNode::apply_handover_patch(patches, group);
 469     }
 470
 471     std::unique_ptr<ParentNode> m_condition;
 472     const ColumnBase* m_column = nullptr;
 473     ColumnType m_col_type;
 474 };
 475
 476 namespace _impl {
 477
 478 template <class ColType>
 479 struct CostHeuristic;
 480
 481 template <>
 482 struct CostHeuristic<IntegerColumn> {
 483     static constexpr double dD()
 484     {
 485         return 100.0;
 486     }
 487     static constexpr double dT()
 488     {
 489         return 1.0 / 4.0;
 490     }
 491 };
 492
 493 template <>
 494 struct CostHeuristic<IntNullColumn> {
 495     static constexpr double dD()
 496     {
 497         return 100.0;
 498     }
 499     static constexpr double dT()
 500     {
 501         return 1.0 / 4.0;
 502     }
 503 };
 504
 505 // FIXME: Add AdaptiveStringColumn, BasicColumn, etc.
 506 }
 507
 508 class ColumnNodeBase : public ParentNode {
 509 protected:
 510     ColumnNodeBase(size_t column_idx)
 511     {
 512         m_condition_column_idx = column_idx;
 513     }
 514
 515     ColumnNodeBase(const ColumnNodeBase& from, QueryNodeHandoverPatches* patches)
 516         : ParentNode(from, patches)
 517         , m_last_local_match(from.m_last_local_match)
 518         , m_local_matches(from.m_local_matches)
 519         , m_local_limit(from.m_local_limit)
 520         , m_fastmode_disabled(from.m_fastmode_disabled)
 521         , m_action(from.m_action)
 522         , m_state(from.m_state)
 523         , m_source_column(from.m_source_column)
 524     {
 525     }
 526
 527     template <Action TAction, class ColType>
 528     bool match_callback(int64_t v)
 529     {
 530         using TSourceValue = typename ColType::value_type;
 531         using QueryStateType = typename ColumnTypeTraitsSum<TSourceValue, TAction>::sum_type;
 532
 533         size_t i = to_size_t(v);
 534         m_last_local_match = i;
 535         m_local_matches++;
 536
 537         auto state = static_cast<QueryState<QueryStateType>*>(m_state);
 538         auto source_column = static_cast<SequentialGetter<ColType>*>(m_source_column);
 539
 540         // Test remaining sub conditions of this node. m_children[0] is the node that called match_callback(), so skip
 541         // it
 542         for (size_t c = 1; c < m_children.size(); c++) {
 543             m_children[c]->m_probes++;
 544             size_t m = m_children[c]->find_first_local(i, i + 1);
 545             if (m != i)
 546                 return true;
 547         }
 548
 549         bool b;
 550         if (state->template uses_val<TAction>()) { // Compiler cannot see that IntegerColumn::Get has no side effect
 551             // and result is discarded
 552             TSourceValue av = source_column->get_next(i);
 553             b = state->template match<TAction, false>(i, 0, av);
 554         }
 555         else {
 556             b = state->template match<TAction, false>(i, 0, TSourceValue{});
 557         }
 558
 559         return b;
 560     }
 561
 562     // Aggregate bookkeeping
 563     size_t m_last_local_match = npos;
 564     size_t m_local_matches = 0;
 565     size_t m_local_limit = 0;
 566     bool m_fastmode_disabled = false;
 567     Action m_action;
 568     QueryStateBase* m_state = nullptr;
 569     SequentialGetterBase* m_source_column =
 570         nullptr; // Column of values used in aggregate (act_FindAll, actReturnFirst, act_Sum, etc)
 571 };
 572
 573 template <class ColType>
 574 class IntegerNodeBase : public ColumnNodeBase {
 575     using ThisType = IntegerNodeBase<ColType>;
 576
 577 public:
 578     using TConditionValue = typename ColType::value_type;
 579     static const bool nullable = ColType::nullable;
 580
 581     template <class TConditionFunction, Action TAction, DataType TDataType, bool Nullable>
 582     bool find_callback_specialization(size_t s, size_t end_in_leaf)
 583     {
 584         using AggregateColumnType = typename GetColumnType<TDataType, Nullable>::type;
 585         bool cont;
 586         size_t start_in_leaf = s - this->m_leaf_start;
 587         cont = this->m_leaf_ptr->template find<TConditionFunction, act_CallbackIdx>(
 588             m_value, start_in_leaf, end_in_leaf, this->m_leaf_start, nullptr,
 589             std::bind(std::mem_fn(&ThisType::template match_callback<TAction, AggregateColumnType>), this,
 590                       std::placeholders::_1));
 591         return cont;
 592     }
 593
 594 protected:
 595     using LeafType = typename ColType::LeafType;
 596     using LeafInfo = typename ColType::LeafInfo;
 597
 598     size_t aggregate_local_impl(QueryStateBase* st, size_t start, size_t end, size_t local_limit,
 599                                 SequentialGetterBase* source_column, int c)
 600     {
 601         REALM_ASSERT(m_children.size() > 0);
 602         m_local_matches = 0;
 603         m_local_limit = local_limit;
 604         m_last_local_match = start - 1;
 605         m_state = st;
 606
 607         // If there are no other nodes than us (m_children.size() == 1) AND the column used for our condition is
 608         // the same as the column used for the aggregate action, then the entire query can run within scope of that
 609         // column only, with no references to other columns:
 610         bool fastmode = should_run_in_fastmode(source_column);
 611         for (size_t s = start; s < end;) {
 612             cache_leaf(s);
 613
 614             size_t end_in_leaf;
 615             if (end > m_leaf_end)
 616                 end_in_leaf = m_leaf_end - m_leaf_start;
 617             else
 618                 end_in_leaf = end - m_leaf_start;
 619
 620             if (fastmode) {
 621                 bool cont;
 622                 size_t start_in_leaf = s - m_leaf_start;
 623                 cont = m_leaf_ptr->find(c, m_action, m_value, start_in_leaf, end_in_leaf, m_leaf_start,
 624                                         static_cast<QueryState<int64_t>*>(st));
 625                 if (!cont)
 626                     return not_found;
 627             }
 628             // Else, for each match in this node, call our IntegerNodeBase::match_callback to test remaining nodes
 629             // and/or extract
 630             // aggregate payload from aggregate column:
 631             else {
 632                 m_source_column = source_column;
 633                 bool cont = (this->*m_find_callback_specialized)(s, end_in_leaf);
 634                 if (!cont)
 635                     return not_found;
 636             }
 637
 638             if (m_local_matches == m_local_limit)
 639                 break;
 640
 641             s = end_in_leaf + m_leaf_start;
 642         }
 643
 644         if (m_local_matches == m_local_limit) {
 645             m_dD = (m_last_local_match + 1 - start) / (m_local_matches + 1.0);
 646             return m_last_local_match + 1;
 647         }
 648         else {
 649             m_dD = (end - start) / (m_local_matches + 1.0);
 650             return end;
 651         }
 652     }
 653
 654     IntegerNodeBase(TConditionValue value, size_t column_idx)
 655         : ColumnNodeBase(column_idx)
 656         , m_value(std::move(value))
 657     {
 658     }
 659
 660     IntegerNodeBase(const ThisType& from, QueryNodeHandoverPatches* patches)
 661         : ColumnNodeBase(from, patches)
 662         , m_value(from.m_value)
 663         , m_condition_column(from.m_condition_column)
 664         , m_find_callback_specialized(from.m_find_callback_specialized)
 665     {
 666         if (m_condition_column && patches)
 667             m_condition_column_idx = m_condition_column->get_column_index();
 668     }
 669
 670     void table_changed() override
 671     {
 672         m_condition_column = &get_column<ColType>(m_condition_column_idx);
 673     }
 674
 675     void verify_column() const override
 676     {
 677         do_verify_column(m_condition_column);
 678     }
 679
 680     void init() override
 681     {
 682         ColumnNodeBase::init();
 683
 684         m_dT = _impl::CostHeuristic<ColType>::dT();
 685         m_dD = _impl::CostHeuristic<ColType>::dD();
 686
 687         // Clear leaf cache
 688         m_leaf_end = 0;
 689         m_array_ptr.reset(); // Explicitly destroy the old one first, because we're reusing the memory.
 690         m_array_ptr.reset(new (&m_leaf_cache_storage) LeafType(m_table->get_alloc()));
 691     }
 692
 693     void get_leaf(const ColType& col, size_t ndx)
 694     {
 695         size_t ndx_in_leaf;
 696         LeafInfo leaf_info{&m_leaf_ptr, m_array_ptr.get()};
 697         col.get_leaf(ndx, ndx_in_leaf, leaf_info);
 698         m_leaf_start = ndx - ndx_in_leaf;
 699         m_leaf_end = m_leaf_start + m_leaf_ptr->size();
 700     }
 701
 702     void cache_leaf(size_t s)
 703     {
 704         if (s >= m_leaf_end || s < m_leaf_start) {
 705             get_leaf(*m_condition_column, s);
 706             size_t w = m_leaf_ptr->get_width();
 707             m_dT = (w == 0 ? 1.0 / REALM_MAX_BPNODE_SIZE : w / float(bitwidth_time_unit));
 708         }
 709     }
 710
 711     bool should_run_in_fastmode(SequentialGetterBase* source_column) const
 712     {
 713         return (m_children.size() == 1 &&
 714                 (source_column == nullptr ||
 715                  (!m_fastmode_disabled &&
 716                   static_cast<SequentialGetter<ColType>*>(source_column)->m_column == m_condition_column)));
 717     }
 718
 719     // Search value:
 720     TConditionValue m_value;
 721
 722     // Column on which search criteria are applied
 723     const ColType* m_condition_column = nullptr;
 724
 725     // Leaf cache
 726     using LeafCacheStorage = typename std::aligned_storage<sizeof(LeafType), alignof(LeafType)>::type;
 727     LeafCacheStorage m_leaf_cache_storage;
 728     std::unique_ptr<LeafType, PlacementDelete> m_array_ptr;
 729     const LeafType* m_leaf_ptr = nullptr;
 730     size_t m_leaf_start = npos;
 731     size_t m_leaf_end = 0;
 732     size_t m_local_end;
 733
 734     // Aggregate optimization
 735     using TFind_callback_specialized = bool (ThisType::*)(size_t, size_t);
 736     TFind_callback_specialized m_find_callback_specialized = nullptr;
 737 };
 738
 739
 740 // FIXME: Add specialization that uses index for TConditionFunction = Equal
 741 template <class ColType, class TConditionFunction>
 742 class IntegerNode : public IntegerNodeBase<ColType> {
 743     using BaseType = IntegerNodeBase<ColType>;
 744     using ThisType = IntegerNode<ColType, TConditionFunction>;
 745
 746 public:
 747     static const bool special_null_node = false;
 748     using TConditionValue = typename BaseType::TConditionValue;
 749
 750     IntegerNode(TConditionValue value, size_t column_ndx)
 751         : BaseType(value, column_ndx)
 752     {
 753     }
 754     IntegerNode(const IntegerNode& from, QueryNodeHandoverPatches* patches)
 755         : BaseType(from, patches)
 756     {
 757     }
 758
 759     void aggregate_local_prepare(Action action, DataType col_id, bool nullable) override
 760     {
 761         this->m_fastmode_disabled = (col_id == type_Float || col_id == type_Double);
 762         this->m_action = action;
 763         this->m_find_callback_specialized = get_specialized_callback(action, col_id, nullable);
 764     }
 765
 766     size_t aggregate_local(QueryStateBase* st, size_t start, size_t end, size_t local_limit,
 767                            SequentialGetterBase* source_column) override
 768     {
 769         constexpr int cond = TConditionFunction::condition;
 770         return this->aggregate_local_impl(st, start, end, local_limit, source_column, cond);
 771     }
 772
 773     size_t find_first_local(size_t start, size_t end) override
 774     {
 775         REALM_ASSERT(this->m_table);
 776
 777         while (start < end) {
 778
 779             // Cache internal leaves
 780             if (start >= this->m_leaf_end || start < this->m_leaf_start) {
 781                 this->get_leaf(*this->m_condition_column, start);
 782             }
 783
 784             // FIXME: Create a fast bypass when you just need to check 1 row, which is used alot from within core.
 785             // It should just call array::get and save the initial overhead of find_first() which has become quite
 786             // big. Do this when we have cleaned up core a bit more.
 787
 788             size_t end2;
 789             if (end > this->m_leaf_end)
 790                 end2 = this->m_leaf_end - this->m_leaf_start;
 791             else
 792                 end2 = end - this->m_leaf_start;
 793
 794             size_t s;
 795             s = this->m_leaf_ptr->template find_first<TConditionFunction>(this->m_value, start - this->m_leaf_start,
 796                                                                           end2);
 797
 798             if (s == not_found) {
 799                 start = this->m_leaf_end;
 800                 continue;
 801             }
 802             else
 803                 return s + this->m_leaf_start;
 804         }
 805
 806         return not_found;
 807     }
 808
 809     virtual std::string describe() const override
 810     {
 811         return this->describe_column() + " " + describe_condition() + " " + util::serializer::print_value(IntegerNodeBase<ColType>::m_value);
 812     }
 813
 814     virtual std::string describe_condition() const override
 815     {
 816         return TConditionFunction::description();
 817     }
 818
 819     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
 820     {
 821         return std::unique_ptr<ParentNode>(new IntegerNode<ColType, TConditionFunction>(*this, patches));
 822     }
 823
 824 protected:
 825     using TFind_callback_specialized = typename BaseType::TFind_callback_specialized;
 826
 827     static TFind_callback_specialized get_specialized_callback(Action action, DataType col_id, bool nullable)
 828     {
 829         switch (action) {
 830             case act_Count:
 831                 return get_specialized_callback_2_int<act_Count>(col_id, nullable);
 832             case act_Sum:
 833                 return get_specialized_callback_2<act_Sum>(col_id, nullable);
 834             case act_Max:
 835                 return get_specialized_callback_2<act_Max>(col_id, nullable);
 836             case act_Min:
 837                 return get_specialized_callback_2<act_Min>(col_id, nullable);
 838             case act_FindAll:
 839                 return get_specialized_callback_2_int<act_FindAll>(col_id, nullable);
 840             case act_CallbackIdx:
 841                 return get_specialized_callback_2_int<act_CallbackIdx>(col_id, nullable);
 842             default:
 843                 break;
 844         }
 845         REALM_ASSERT(false); // Invalid aggregate function
 846         return nullptr;
 847     }
 848
 849     template <Action TAction>
 850     static TFind_callback_specialized get_specialized_callback_2(DataType col_id, bool nullable)
 851     {
 852         switch (col_id) {
 853             case type_Int:
 854                 return get_specialized_callback_3<TAction, type_Int>(nullable);
 855             case type_Float:
 856                 return get_specialized_callback_3<TAction, type_Float>(nullable);
 857             case type_Double:
 858                 return get_specialized_callback_3<TAction, type_Double>(nullable);
 859             default:
 860                 break;
 861         }
 862         REALM_ASSERT(false); // Invalid aggregate source column
 863         return nullptr;
 864     }
 865
 866     template <Action TAction>
 867     static TFind_callback_specialized get_specialized_callback_2_int(DataType col_id, bool nullable)
 868     {
 869         if (col_id == type_Int) {
 870             return get_specialized_callback_3<TAction, type_Int>(nullable);
 871         }
 872         REALM_ASSERT(false); // Invalid aggregate source column
 873         return nullptr;
 874     }
 875
 876     template <Action TAction, DataType TDataType>
 877     static TFind_callback_specialized get_specialized_callback_3(bool nullable)
 878     {
 879         if (nullable) {
 880             return &BaseType::template find_callback_specialization<TConditionFunction, TAction, TDataType, true>;
 881         }
 882         else {
 883             return &BaseType::template find_callback_specialization<TConditionFunction, TAction, TDataType, false>;
 884         }
 885     }
 886 };
 887
 888
 889 // This node is currently used for floats and doubles only
 890 template <class ColType, class TConditionFunction>
 891 class FloatDoubleNode : public ParentNode {
 892 public:
 893     using TConditionValue = typename ColType::value_type;
 894     static const bool special_null_node = false;
 895
 896     FloatDoubleNode(TConditionValue v, size_t column_ndx)
 897         : m_value(v)
 898     {
 899         m_condition_column_idx = column_ndx;
 900         m_dT = 1.0;
 901     }
 902     FloatDoubleNode(null, size_t column_ndx)
 903         : m_value(null::get_null_float<TConditionValue>())
 904     {
 905         m_condition_column_idx = column_ndx;
 906         m_dT = 1.0;
 907     }
 908
 909     void table_changed() override
 910     {
 911         m_condition_column.init(&get_column<ColType>(m_condition_column_idx));
 912     }
 913
 914     void verify_column() const override
 915     {
 916         do_verify_column(m_condition_column.m_column);
 917     }
 918
 919     void init() override
 920     {
 921         ParentNode::init();
 922         m_dD = 100.0;
 923     }
 924
 925     size_t find_first_local(size_t start, size_t end) override
 926     {
 927         TConditionFunction cond;
 928
 929         auto find = [&](bool nullability) {
 930             bool m_value_nan = nullability ? null::is_null_float(m_value) : false;
 931             for (size_t s = start; s < end; ++s) {
 932                 TConditionValue v = m_condition_column.get_next(s);
 933                 REALM_ASSERT(!(null::is_null_float(v) && !nullability));
 934                 if (cond(v, m_value, nullability ? null::is_null_float<TConditionValue>(v) : false, m_value_nan))
 935                     return s;
 936             }
 937             return not_found;
 938         };
 939
 940         // This will inline the second case but no the first. Todo, use templated lambda when switching to c++14
 941         if (m_table->is_nullable(m_condition_column_idx))
 942             return find(true);
 943         else
 944             return find(false);
 945     }
 946
 947     virtual std::string describe() const override
 948     {
 949         return this->describe_column() + " " + describe_condition() + " " + util::serializer::print_value(FloatDoubleNode::m_value);
 950     }
 951     virtual std::string describe_condition() const override
 952     {
 953         return TConditionFunction::description();
 954     }
 955
 956     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
 957     {
 958         return std::unique_ptr<ParentNode>(new FloatDoubleNode(*this, patches));
 959     }
 960
 961     FloatDoubleNode(const FloatDoubleNode& from, QueryNodeHandoverPatches* patches)
 962         : ParentNode(from, patches)
 963         , m_value(from.m_value)
 964     {
 965         copy_getter(m_condition_column, m_condition_column_idx, from.m_condition_column, patches);
 966     }
 967
 968 protected:
 969     TConditionValue m_value;
 970     SequentialGetter<ColType> m_condition_column;
 971 };
 972
 973 template <class ColType, class TConditionFunction>
 974 class SizeNode : public ParentNode {
 975 public:
 976     SizeNode(int64_t v, size_t column)
 977         : m_value(v)
 978     {
 979         m_condition_column_idx = column;
 980     }
 981
 982     void table_changed() override
 983     {
 984         m_condition_column = &get_column<ColType>(m_condition_column_idx);
 985     }
 986
 987     void verify_column() const override
 988     {
 989         do_verify_column(m_condition_column);
 990     }
 991
 992     void init() override
 993     {
 994         ParentNode::init();
 995         m_dD = 10.0;
 996     }
 997
 998     size_t find_first_local(size_t start, size_t end) override
 999     {
1000         for (size_t s = start; s < end; ++s) {
1001             TConditionValue v = m_condition_column->get(s);
1002             if (v) {
1003                 int64_t sz = m_size_operator(v);
1004                 if (TConditionFunction()(sz, m_value))
1005                     return s;
1006             }
1007         }
1008         return not_found;
1009     }
1010
1011     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1012     {
1013         return std::unique_ptr<ParentNode>(new SizeNode(*this, patches));
1014     }
1015
1016     SizeNode(const SizeNode& from, QueryNodeHandoverPatches* patches)
1017         : ParentNode(from, patches)
1018         , m_value(from.m_value)
1019         , m_condition_column(from.m_condition_column)
1020     {
1021         if (m_condition_column && patches)
1022             m_condition_column_idx = m_condition_column->get_column_index();
1023     }
1024
1025 private:
1026     using TConditionValue = typename ColType::value_type;
1027
1028     int64_t m_value;
1029     const ColType* m_condition_column = nullptr;
1030     Size<TConditionValue> m_size_operator;
1031 };
1032
1033
1034 template <class TConditionFunction>
1035 class BinaryNode : public ParentNode {
1036 public:
1037     using TConditionValue = BinaryData;
1038     static const bool special_null_node = false;
1039
1040     BinaryNode(BinaryData v, size_t column)
1041         : m_value(v)
1042     {
1043         m_dT = 100.0;
1044         m_condition_column_idx = column;
1045     }
1046
1047     BinaryNode(null, size_t column)
1048         : BinaryNode(BinaryData{}, column)
1049     {
1050     }
1051
1052     void table_changed() override
1053     {
1054         m_condition_column = &get_column<BinaryColumn>(m_condition_column_idx);
1055     }
1056
1057     void verify_column() const override
1058     {
1059         do_verify_column(m_condition_column);
1060     }
1061
1062     void init() override
1063     {
1064         ParentNode::init();
1065
1066         m_dD = 100.0;
1067     }
1068
1069     size_t find_first_local(size_t start, size_t end) override
1070     {
1071         TConditionFunction condition;
1072         for (size_t s = start; s < end; ++s) {
1073             BinaryData value = m_condition_column->get(s);
1074             if (condition(m_value.get(), value))
1075                 return s;
1076         }
1077         return not_found;
1078     }
1079
1080     virtual std::string describe() const override
1081     {
1082         return this->describe_column() + " " + TConditionFunction::description() + " "
1083             + util::serializer::print_value(BinaryNode::m_value.get());
1084     }
1085
1086     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1087     {
1088         return std::unique_ptr<ParentNode>(new BinaryNode(*this, patches));
1089     }
1090
1091     BinaryNode(const BinaryNode& from, QueryNodeHandoverPatches* patches)
1092         : ParentNode(from, patches)
1093         , m_value(from.m_value)
1094         , m_condition_column(from.m_condition_column)
1095     {
1096         if (m_condition_column && patches)
1097             m_condition_column_idx = m_condition_column->get_column_index();
1098     }
1099
1100 private:
1101     OwnedBinaryData m_value;
1102     const BinaryColumn* m_condition_column;
1103 };
1104
1105
1106 template <class TConditionFunction>
1107 class TimestampNode : public ParentNode {
1108 public:
1109     using TConditionValue = Timestamp;
1110     static const bool special_null_node = false;
1111
1112     TimestampNode(Timestamp v, size_t column)
1113         : m_value(v)
1114     {
1115         m_condition_column_idx = column;
1116     }
1117
1118     TimestampNode(null, size_t column)
1119         : TimestampNode(Timestamp{}, column)
1120     {
1121     }
1122
1123     void table_changed() override
1124     {
1125         m_condition_column = &get_column<TimestampColumn>(m_condition_column_idx);
1126     }
1127
1128     void verify_column() const override
1129     {
1130         do_verify_column(m_condition_column);
1131     }
1132
1133     void init() override
1134     {
1135         ParentNode::init();
1136
1137         m_dD = 100.0;
1138     }
1139
1140     size_t find_first_local(size_t start, size_t end) override
1141     {
1142         size_t ret = m_condition_column->find<TConditionFunction>(m_value, start, end);
1143         return ret;
1144     }
1145
1146     virtual std::string describe() const override
1147     {
1148         return this->describe_column() + " " + TConditionFunction::description() + " " + util::serializer::print_value(TimestampNode::m_value);
1149     }
1150
1151     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1152     {
1153         return std::unique_ptr<ParentNode>(new TimestampNode(*this, patches));
1154     }
1155
1156     TimestampNode(const TimestampNode& from, QueryNodeHandoverPatches* patches)
1157         : ParentNode(from, patches)
1158         , m_value(from.m_value)
1159         , m_condition_column(from.m_condition_column)
1160     {
1161         if (m_condition_column && patches)
1162             m_condition_column_idx = m_condition_column->get_column_index();
1163     }
1164
1165 private:
1166     Timestamp m_value;
1167     const TimestampColumn* m_condition_column;
1168 };
1169
1170 class StringNodeBase : public ParentNode {
1171 public:
1172     using TConditionValue = StringData;
1173     static const bool special_null_node = true;
1174
1175     StringNodeBase(StringData v, size_t column)
1176         : m_value(v.is_null() ? util::none : util::make_optional(std::string(v)))
1177     {
1178         m_condition_column_idx = column;
1179     }
1180
1181     void table_changed() override
1182     {
1183         m_condition_column = &get_column_base(m_condition_column_idx);
1184         m_column_type = get_real_column_type(m_condition_column_idx);
1185     }
1186
1187     void verify_column() const override
1188     {
1189         do_verify_column(m_condition_column);
1190     }
1191
1192     void init() override
1193     {
1194         ParentNode::init();
1195
1196         m_dT = 10.0;
1197         m_probes = 0;
1198         m_matches = 0;
1199         m_end_s = 0;
1200         m_leaf_start = 0;
1201         m_leaf_end = 0;
1202     }
1203
1204     void clear_leaf_state()
1205     {
1206         m_leaf.reset(nullptr);
1207     }
1208
1209     StringNodeBase(const StringNodeBase& from, QueryNodeHandoverPatches* patches)
1210         : ParentNode(from, patches)
1211         , m_value(from.m_value)
1212         , m_condition_column(from.m_condition_column)
1213         , m_column_type(from.m_column_type)
1214         , m_leaf_type(from.m_leaf_type)
1215     {
1216         if (m_condition_column && patches)
1217             m_condition_column_idx = m_condition_column->get_column_index();
1218     }
1219
1220     virtual std::string describe() const override
1221     {
1222         StringData sd;
1223         if (bool(StringNodeBase::m_value)) {
1224             sd = StringData(StringNodeBase::m_value.value());
1225         }
1226         return this->describe_column() + " " + describe_condition() + " " + util::serializer::print_value(sd);
1227     }
1228
1229 protected:
1230     util::Optional<std::string> m_value;
1231
1232     const ColumnBase* m_condition_column = nullptr;
1233     ColumnType m_column_type;
1234
1235     // Used for linear scan through short/long-string
1236     std::unique_ptr<const ArrayParent> m_leaf;
1237     StringColumn::LeafType m_leaf_type;
1238     size_t m_end_s = 0;
1239     size_t m_leaf_start = 0;
1240     size_t m_leaf_end = 0;
1241
1242     inline StringData get_string(size_t s)
1243     {
1244         StringData t;
1245
1246         if (m_column_type == col_type_StringEnum) {
1247             // enum
1248             t = static_cast<const StringEnumColumn*>(m_condition_column)->get(s);
1249         }
1250         else {
1251             // short or long
1252             const StringColumn* asc = static_cast<const StringColumn*>(m_condition_column);
1253             REALM_ASSERT_3(s, <, asc->size());
1254             if (s >= m_end_s || s < m_leaf_start) {
1255                 // we exceeded current leaf's range
1256                 clear_leaf_state();
1257                 size_t ndx_in_leaf;
1258                 m_leaf = asc->get_leaf(s, ndx_in_leaf, m_leaf_type);
1259                 m_leaf_start = s - ndx_in_leaf;
1260
1261                 if (m_leaf_type == StringColumn::leaf_type_Small)
1262                     m_end_s = m_leaf_start + static_cast<const ArrayString&>(*m_leaf).size();
1263                 else if (m_leaf_type == StringColumn::leaf_type_Medium)
1264                     m_end_s = m_leaf_start + static_cast<const ArrayStringLong&>(*m_leaf).size();
1265                 else
1266                     m_end_s = m_leaf_start + static_cast<const ArrayBigBlobs&>(*m_leaf).size();
1267             }
1268
1269             if (m_leaf_type == StringColumn::leaf_type_Small)
1270                 t = static_cast<const ArrayString&>(*m_leaf).get(s - m_leaf_start);
1271             else if (m_leaf_type == StringColumn::leaf_type_Medium)
1272                 t = static_cast<const ArrayStringLong&>(*m_leaf).get(s - m_leaf_start);
1273             else
1274                 t = static_cast<const ArrayBigBlobs&>(*m_leaf).get_string(s - m_leaf_start);
1275         }
1276         return t;
1277     }
1278 };
1279
1280 // Conditions for strings. Note that Equal is specialized later in this file!
1281 template <class TConditionFunction>
1282 class StringNode : public StringNodeBase {
1283 public:
1284     StringNode(StringData v, size_t column)
1285         : StringNodeBase(v, column)
1286     {
1287         auto upper = case_map(v, true);
1288         auto lower = case_map(v, false);
1289         if (!upper || !lower) {
1290             error_code = "Malformed UTF-8: " + std::string(v);
1291         }
1292         else {
1293             m_ucase = std::move(*upper);
1294             m_lcase = std::move(*lower);
1295         }
1296     }
1297
1298     void init() override
1299     {
1300         clear_leaf_state();
1301
1302         m_dD = 100.0;
1303
1304         StringNodeBase::init();
1305     }
1306
1307
1308     size_t find_first_local(size_t start, size_t end) override
1309     {
1310         TConditionFunction cond;
1311
1312         for (size_t s = start; s < end; ++s) {
1313             StringData t = get_string(s);
1314
1315             if (cond(StringData(m_value), m_ucase.data(), m_lcase.data(), t))
1316                 return s;
1317         }
1318         return not_found;
1319     }
1320
1321     virtual std::string describe_condition() const override
1322     {
1323         return TConditionFunction::description();
1324     }
1325
1326     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1327     {
1328         return std::unique_ptr<ParentNode>(new StringNode<TConditionFunction>(*this, patches));
1329     }
1330
1331     StringNode(const StringNode& from, QueryNodeHandoverPatches* patches)
1332         : StringNodeBase(from, patches)
1333         , m_ucase(from.m_ucase)
1334         , m_lcase(from.m_lcase)
1335     {
1336     }
1337
1338 protected:
1339     std::string m_ucase;
1340     std::string m_lcase;
1341 };
1342
1343 // Specialization for Contains condition on Strings - we specialize because we can utilize Boyer-Moore
1344 template <>
1345 class StringNode<Contains> : public StringNodeBase {
1346 public:
1347     StringNode(StringData v, size_t column)
1348     : StringNodeBase(v, column), m_charmap()
1349     {
1350         if (v.size() == 0)
1351             return;
1352
1353         // Build a dictionary of char-to-last distances in the search string
1354         // (zero indicates that the char is not in needle)
1355         size_t last_char_pos = v.size()-1;
1356         for (size_t i = 0; i < last_char_pos; ++i) {
1357             // we never jump longer increments than 255 chars, even if needle is longer (to fit in one byte)
1358             uint8_t jump = last_char_pos-i < 255 ? static_cast<uint8_t>(last_char_pos-i) : 255;
1359
1360             unsigned char c = v[i];
1361             m_charmap[c] = jump;
1362         }
1363     }
1364
1365     void init() override
1366     {
1367         clear_leaf_state();
1368
1369         m_dD = 100.0;
1370
1371         StringNodeBase::init();
1372     }
1373
1374
1375     size_t find_first_local(size_t start, size_t end) override
1376     {
1377         Contains cond;
1378
1379         for (size_t s = start; s < end; ++s) {
1380             StringData t = get_string(s);
1381
1382             if (cond(StringData(m_value), m_charmap, t))
1383                 return s;
1384         }
1385         return not_found;
1386     }
1387
1388     virtual std::string describe_condition() const override
1389     {
1390         return Contains::description();
1391     }
1392
1393
1394     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1395     {
1396         return std::unique_ptr<ParentNode>(new StringNode<Contains>(*this, patches));
1397     }
1398
1399     StringNode(const StringNode& from, QueryNodeHandoverPatches* patches)
1400     : StringNodeBase(from, patches)
1401     , m_charmap(from.m_charmap)
1402     {
1403     }
1404
1405 protected:
1406     std::array<uint8_t, 256> m_charmap;
1407 };
1408
1409 // Specialization for ContainsIns condition on Strings - we specialize because we can utilize Boyer-Moore
1410 template <>
1411 class StringNode<ContainsIns> : public StringNodeBase {
1412 public:
1413     StringNode(StringData v, size_t column)
1414     : StringNodeBase(v, column), m_charmap()
1415     {
1416         auto upper = case_map(v, true);
1417         auto lower = case_map(v, false);
1418         if (!upper || !lower) {
1419             error_code = "Malformed UTF-8: " + std::string(v);
1420         }
1421         else {
1422             m_ucase = std::move(*upper);
1423             m_lcase = std::move(*lower);
1424         }
1425
1426         if (v.size() == 0)
1427             return;
1428
1429         // Build a dictionary of char-to-last distances in the search string
1430         // (zero indicates that the char is not in needle)
1431         size_t last_char_pos = m_ucase.size()-1;
1432         for (size_t i = 0; i < last_char_pos; ++i) {
1433             // we never jump longer increments than 255 chars, even if needle is longer (to fit in one byte)
1434             uint8_t jump = last_char_pos-i < 255 ? static_cast<uint8_t>(last_char_pos-i) : 255;
1435
1436             unsigned char uc = m_ucase[i];
1437             unsigned char lc = m_lcase[i];
1438             m_charmap[uc] = jump;
1439             m_charmap[lc] = jump;
1440         }
1441
1442     }
1443
1444     void init() override
1445     {
1446         clear_leaf_state();
1447
1448         m_dD = 100.0;
1449
1450         StringNodeBase::init();
1451     }
1452
1453
1454     size_t find_first_local(size_t start, size_t end) override
1455     {
1456         ContainsIns cond;
1457
1458         for (size_t s = start; s < end; ++s) {
1459             StringData t = get_string(s);
1460             // The current behaviour is to return all results when querying for a null string.
1461             // See comment above Query_NextGen_StringConditions on why every string including "" contains null.
1462             if (!bool(m_value)) {
1463                 return s;
1464             }
1465             if (cond(StringData(m_value), m_ucase.data(), m_lcase.data(), m_charmap, t))
1466                 return s;
1467         }
1468         return not_found;
1469     }
1470
1471     virtual std::string describe_condition() const override
1472     {
1473         return ContainsIns::description();
1474     }
1475
1476     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1477     {
1478         return std::unique_ptr<ParentNode>(new StringNode<ContainsIns>(*this, patches));
1479     }
1480
1481     StringNode(const StringNode& from, QueryNodeHandoverPatches* patches)
1482     : StringNodeBase(from, patches)
1483     , m_charmap(from.m_charmap)
1484     , m_ucase(from.m_ucase)
1485     , m_lcase(from.m_lcase)
1486     {
1487     }
1488
1489 protected:
1490     std::array<uint8_t, 256> m_charmap;
1491     std::string m_ucase;
1492     std::string m_lcase;
1493 };
1494
1495 class StringNodeEqualBase : public StringNodeBase {
1496 public:
1497     StringNodeEqualBase(StringData v, size_t column)
1498         : StringNodeBase(v, column)
1499     {
1500     }
1501     StringNodeEqualBase(const StringNodeEqualBase& from, QueryNodeHandoverPatches* patches)
1502         : StringNodeBase(from, patches)
1503     {
1504     }
1505     ~StringNodeEqualBase() noexcept override
1506     {
1507         deallocate();
1508     }
1509
1510     void deallocate() noexcept;
1511     void init() override;
1512     size_t find_first_local(size_t start, size_t end) override;
1513
1514     virtual std::string describe_condition() const override
1515     {
1516         return Equal::description();
1517     }
1518
1519 protected:
1520     inline BinaryData str_to_bin(const StringData& s) noexcept
1521     {
1522         return BinaryData(s.data(), s.size());
1523     }
1524
1525     virtual void _search_index_init() = 0;
1526     virtual size_t _find_first_local(size_t start, size_t end) = 0;
1527
1528     size_t m_key_ndx = not_found;
1529     size_t m_last_indexed;
1530
1531     // Used for linear scan through enum-string
1532     SequentialGetter<StringEnumColumn> m_cse;
1533
1534     // Used for index lookup
1535     std::unique_ptr<IntegerColumn> m_index_matches;
1536     bool m_index_matches_destroy = false;
1537     std::unique_ptr<SequentialGetter<IntegerColumn>> m_index_getter;
1538     size_t m_results_start;
1539     size_t m_results_end;
1540     size_t m_last_start;
1541 };
1542
1543
1544 // Specialization for Equal condition on Strings - we specialize because we can utilize indexes (if they exist) for
1545 // Equal.
1546 // Future optimization: make specialization for greater, notequal, etc
1547 template <>
1548 class StringNode<Equal> : public StringNodeEqualBase {
1549 public:
1550     using StringNodeEqualBase::StringNodeEqualBase;
1551
1552     void _search_index_init() override;
1553
1554     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1555     {
1556         return std::unique_ptr<ParentNode>(new StringNode<Equal>(*this, patches));
1557     }
1558
1559 private:
1560     size_t _find_first_local(size_t start, size_t end) override;
1561 };
1562
1563
1564 // Specialization for EqualIns condition on Strings - we specialize because we can utilize indexes (if they exist) for
1565 // EqualIns.
1566 template <>
1567 class StringNode<EqualIns> : public StringNodeEqualBase {
1568 public:
1569     StringNode(StringData v, size_t column)
1570         : StringNodeEqualBase(v, column)
1571     {
1572         auto upper = case_map(v, true);
1573         auto lower = case_map(v, false);
1574         if (!upper || !lower) {
1575             error_code = "Malformed UTF-8: " + std::string(v);
1576         }
1577         else {
1578             m_ucase = std::move(*upper);
1579             m_lcase = std::move(*lower);
1580         }
1581     }
1582
1583     void _search_index_init() override;
1584
1585     virtual std::string describe_condition() const override
1586     {
1587         return EqualIns::description();
1588     }
1589
1590     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1591     {
1592         return std::unique_ptr<ParentNode>(new StringNode(*this, patches));
1593     }
1594
1595     StringNode(const StringNode& from, QueryNodeHandoverPatches* patches)
1596         : StringNodeEqualBase(from, patches)
1597         , m_ucase(from.m_ucase)
1598         , m_lcase(from.m_lcase)
1599     {
1600     }
1601
1602 private:
1603     std::string m_ucase;
1604     std::string m_lcase;
1605
1606     size_t _find_first_local(size_t start, size_t end) override;
1607 };
1608
1609
1610 // OR node contains at least two node pointers: Two or more conditions to OR
1611 // together in m_conditions, and the next AND condition (if any) in m_child.
1612 //
1613 // For 'second.equal(23).begin_group().first.equal(111).Or().first.equal(222).end_group().third().equal(555)', this
1614 // will first set m_conditions[0] = left-hand-side through constructor, and then later, when .first.equal(222) is
1615 // invoked, invocation will set m_conditions[1] = right-hand-side through Query& Query::Or() (see query.cpp).
1616 // In there, m_child is also set to next AND condition (if any exists) following the OR.
1617 class OrNode : public ParentNode {
1618 public:
1619     OrNode(std::unique_ptr<ParentNode> condition)
1620     {
1621         m_dT = 50.0;
1622         if (condition)
1623             m_conditions.emplace_back(std::move(condition));
1624     }
1625
1626     OrNode(const OrNode& other, QueryNodeHandoverPatches* patches)
1627         : ParentNode(other, patches)
1628     {
1629         for (const auto& condition : other.m_conditions) {
1630             m_conditions.emplace_back(condition->clone(patches));
1631         }
1632     }
1633
1634     void table_changed() override
1635     {
1636         for (auto& condition : m_conditions) {
1637             condition->set_table(*m_table);
1638         }
1639     }
1640
1641     void verify_column() const override
1642     {
1643         for (auto& condition : m_conditions) {
1644             condition->verify_column();
1645         }
1646     }
1647     std::string describe() const override
1648     {
1649         if (m_conditions.size() >= 2) {
1650
1651         }
1652         std::string s;
1653         for (size_t i = 0; i < m_conditions.size(); ++i) {
1654             if (m_conditions[i]) {
1655                 s += m_conditions[i]->describe_expression();
1656                 if (i != m_conditions.size() - 1) {
1657                     s += " or ";
1658                 }
1659             }
1660         }
1661         if (m_conditions.size() > 1) {
1662             s = "(" + s + ")";
1663         }
1664         return s;
1665     }
1666
1667
1668     void init() override
1669     {
1670         ParentNode::init();
1671
1672         m_dD = 10.0;
1673
1674         m_start.clear();
1675         m_start.resize(m_conditions.size(), 0);
1676
1677         m_last.clear();
1678         m_last.resize(m_conditions.size(), 0);
1679
1680         m_was_match.clear();
1681         m_was_match.resize(m_conditions.size(), false);
1682
1683         std::vector<ParentNode*> v;
1684         for (auto& condition : m_conditions) {
1685             condition->init();
1686             v.clear();
1687             condition->gather_children(v);
1688         }
1689     }
1690
1691     size_t find_first_local(size_t start, size_t end) override
1692     {
1693         if (start >= end)
1694             return not_found;
1695
1696         size_t index = not_found;
1697
1698         for (size_t c = 0; c < m_conditions.size(); ++c) {
1699             // out of order search; have to discard cached results
1700             if (start < m_start[c]) {
1701                 m_last[c] = 0;
1702                 m_was_match[c] = false;
1703             }
1704             // already searched this range and didn't match
1705             else if (m_last[c] >= end)
1706                 continue;
1707             // already search this range and *did* match
1708             else if (m_was_match[c] && m_last[c] >= start) {
1709                 if (index > m_last[c])
1710                     index = m_last[c];
1711                 continue;
1712             }
1713
1714             m_start[c] = start;
1715             size_t fmax = std::max(m_last[c], start);
1716             size_t f = m_conditions[c]->find_first(fmax, end);
1717             m_was_match[c] = f != not_found;
1718             m_last[c] = f == not_found ? end : f;
1719             if (f != not_found && index > m_last[c])
1720                 index = m_last[c];
1721         }
1722
1723         return index;
1724     }
1725
1726     std::string validate() override
1727     {
1728         if (error_code != "")
1729             return error_code;
1730         if (m_conditions.size() == 0)
1731             return "Missing left-hand side of OR";
1732         if (m_conditions.size() == 1)
1733             return "Missing right-hand side of OR";
1734         std::string s;
1735         if (m_child != 0)
1736             s = m_child->validate();
1737         if (s != "")
1738             return s;
1739         for (size_t i = 0; i < m_conditions.size(); ++i) {
1740             s = m_conditions[i]->validate();
1741             if (s != "")
1742                 return s;
1743         }
1744         return "";
1745     }
1746
1747     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1748     {
1749         return std::unique_ptr<ParentNode>(new OrNode(*this, patches));
1750     }
1751
1752     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
1753     {
1754         for (auto it = m_conditions.rbegin(); it != m_conditions.rend(); ++it)
1755             (*it)->apply_handover_patch(patches, group);
1756
1757         ParentNode::apply_handover_patch(patches, group);
1758     }
1759
1760     std::vector<std::unique_ptr<ParentNode>> m_conditions;
1761
1762 private:
1763     // start index of the last find for each cond
1764     std::vector<size_t> m_start;
1765     // last looked at index of the lasft find for each cond
1766     // is a matching index if m_was_match is true
1767     std::vector<size_t> m_last;
1768     std::vector<bool> m_was_match;
1769 };
1770
1771
1772 class NotNode : public ParentNode {
1773 public:
1774     NotNode(std::unique_ptr<ParentNode> condition)
1775         : m_condition(std::move(condition))
1776     {
1777         m_dT = 50.0;
1778     }
1779
1780     void table_changed() override
1781     {
1782         m_condition->set_table(*m_table);
1783     }
1784
1785     void verify_column() const override
1786     {
1787         m_condition->verify_column();
1788     }
1789
1790     void init() override
1791     {
1792         ParentNode::init();
1793
1794         m_dD = 10.0;
1795
1796         std::vector<ParentNode*> v;
1797
1798         m_condition->init();
1799         v.clear();
1800         m_condition->gather_children(v);
1801
1802         // Heuristics bookkeeping:
1803         m_known_range_start = 0;
1804         m_known_range_end = 0;
1805         m_first_in_known_range = not_found;
1806     }
1807
1808     size_t find_first_local(size_t start, size_t end) override;
1809
1810     std::string validate() override
1811     {
1812         if (error_code != "")
1813             return error_code;
1814         if (m_condition == 0)
1815             return "Missing argument to Not";
1816         std::string s;
1817         if (m_child != 0)
1818             s = m_child->validate();
1819         if (s != "")
1820             return s;
1821         s = m_condition->validate();
1822         if (s != "")
1823             return s;
1824         return "";
1825     }
1826
1827     virtual std::string describe() const override
1828     {
1829         if (m_condition) {
1830             return "!(" + m_condition->describe_expression() + ")";
1831         }
1832         return "!()";
1833     }
1834
1835
1836     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1837     {
1838         return std::unique_ptr<ParentNode>(new NotNode(*this, patches));
1839     }
1840
1841     NotNode(const NotNode& from, QueryNodeHandoverPatches* patches)
1842         : ParentNode(from, patches)
1843         , m_condition(from.m_condition ? from.m_condition->clone(patches) : nullptr)
1844         , m_known_range_start(from.m_known_range_start)
1845         , m_known_range_end(from.m_known_range_end)
1846         , m_first_in_known_range(from.m_first_in_known_range)
1847     {
1848     }
1849
1850     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
1851     {
1852         m_condition->apply_handover_patch(patches, group);
1853         ParentNode::apply_handover_patch(patches, group);
1854     }
1855
1856     std::unique_ptr<ParentNode> m_condition;
1857
1858 private:
1859     // FIXME This heuristic might as well be reused for all condition nodes.
1860     size_t m_known_range_start;
1861     size_t m_known_range_end;
1862     size_t m_first_in_known_range;
1863
1864     bool evaluate_at(size_t rowndx);
1865     void update_known(size_t start, size_t end, size_t first);
1866     size_t find_first_loop(size_t start, size_t end);
1867     size_t find_first_covers_known(size_t start, size_t end);
1868     size_t find_first_covered_by_known(size_t start, size_t end);
1869     size_t find_first_overlap_lower(size_t start, size_t end);
1870     size_t find_first_overlap_upper(size_t start, size_t end);
1871     size_t find_first_no_overlap(size_t start, size_t end);
1872 };
1873
1874
1875 // Compare two columns with eachother row-by-row
1876 template <class ColType, class TConditionFunction>
1877 class TwoColumnsNode : public ParentNode {
1878 public:
1879     using TConditionValue = typename ColType::value_type;
1880
1881     TwoColumnsNode(size_t column1, size_t column2)
1882     {
1883         m_dT = 100.0;
1884         m_condition_column_idx1 = column1;
1885         m_condition_column_idx2 = column2;
1886     }
1887
1888     ~TwoColumnsNode() noexcept override
1889     {
1890         delete[] m_value.data();
1891     }
1892
1893     void table_changed() override
1894     {
1895         m_getter1.init(&get_column<ColType>(m_condition_column_idx1));
1896         m_getter2.init(&get_column<ColType>(m_condition_column_idx2));
1897     }
1898
1899     void verify_column() const override
1900     {
1901         do_verify_column(m_getter1.m_column, m_condition_column_idx1);
1902         do_verify_column(m_getter2.m_column, m_condition_column_idx2);
1903     }
1904
1905     void init() override
1906     {
1907         ParentNode::init();
1908         m_dD = 100.0;
1909     }
1910
1911     size_t find_first_local(size_t start, size_t end) override
1912     {
1913         size_t s = start;
1914
1915         while (s < end) {
1916             if (std::is_same<TConditionValue, int64_t>::value) {
1917                 // For int64_t we've created an array intrinsics named compare_leafs which template expands bitwidths
1918                 // of boths arrays to make Get faster.
1919                 m_getter1.cache_next(s);
1920                 m_getter2.cache_next(s);
1921
1922                 QueryState<int64_t> qs;
1923                 bool resume = m_getter1.m_leaf_ptr->template compare_leafs<TConditionFunction, act_ReturnFirst>(
1924                     m_getter2.m_leaf_ptr, s - m_getter1.m_leaf_start, m_getter1.local_end(end), 0, &qs,
1925                     CallbackDummy());
1926
1927                 if (resume)
1928                     s = m_getter1.m_leaf_end;
1929                 else
1930                     return to_size_t(qs.m_state) + m_getter1.m_leaf_start;
1931             }
1932             else {
1933 // This is for float and double.
1934
1935 #if 0 && defined(REALM_COMPILER_AVX)
1936 // AVX has been disabled because of array alignment (see https://app.asana.com/0/search/8836174089724/5763107052506)
1937 //
1938 // For AVX you can call things like if (sseavx<1>()) to test for AVX, and then utilize _mm256_movemask_ps (VC)
1939 // or movemask_cmp_ps (gcc/clang)
1940 //
1941 // See https://github.com/rrrlasse/realm/tree/AVX for an example of utilizing AVX for a two-column search which has
1942 // been benchmarked to: floats: 288 ms vs 552 by using AVX compared to 2-level-unrolled FPU loop. doubles: 415 ms vs
1943 // 475 (more bandwidth bound). Tests against SSE have not been performed; AVX may not pay off. Please benchmark
1944 #endif
1945
1946                 TConditionValue v1 = m_getter1.get_next(s);
1947                 TConditionValue v2 = m_getter2.get_next(s);
1948                 TConditionFunction C;
1949
1950                 if (C(v1, v2))
1951                     return s;
1952                 else
1953                     s++;
1954             }
1955         }
1956         return not_found;
1957     }
1958
1959     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
1960     {
1961         return std::unique_ptr<ParentNode>(new TwoColumnsNode<ColType, TConditionFunction>(*this, patches));
1962     }
1963
1964     TwoColumnsNode(const TwoColumnsNode& from, QueryNodeHandoverPatches* patches)
1965         : ParentNode(from, patches)
1966         , m_value(from.m_value)
1967         , m_condition_column(from.m_condition_column)
1968         , m_column_type(from.m_column_type)
1969         , m_condition_column_idx1(from.m_condition_column_idx1)
1970         , m_condition_column_idx2(from.m_condition_column_idx2)
1971     {
1972         if (m_condition_column)
1973             m_condition_column_idx = m_condition_column->get_column_index();
1974         copy_getter(m_getter1, m_condition_column_idx1, from.m_getter1, patches);
1975         copy_getter(m_getter2, m_condition_column_idx2, from.m_getter2, patches);
1976     }
1977
1978 private:
1979     BinaryData m_value;
1980     const BinaryColumn* m_condition_column = nullptr;
1981     ColumnType m_column_type;
1982
1983     size_t m_condition_column_idx1 = not_found;
1984     size_t m_condition_column_idx2 = not_found;
1985
1986     SequentialGetter<ColType> m_getter1;
1987     SequentialGetter<ColType> m_getter2;
1988 };
1989
1990
1991 // For Next-Generation expressions like col1 / col2 + 123 > col4 * 100.
1992 class ExpressionNode : public ParentNode {
1993
1994 public:
1995     ExpressionNode(std::unique_ptr<Expression>);
1996
1997     size_t find_first_local(size_t start, size_t end) override;
1998
1999     void table_changed() override;
2000     void verify_column() const override;
2001
2002     virtual std::string describe() const override;
2003
2004     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override;
2005     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override;
2006
2007 private:
2008     ExpressionNode(const ExpressionNode& from, QueryNodeHandoverPatches* patches);
2009
2010     std::unique_ptr<Expression> m_expression;
2011 };
2012
2013
2014 struct LinksToNodeHandoverPatch : public QueryNodeHandoverPatch {
2015     std::unique_ptr<RowBaseHandoverPatch> m_target_row;
2016     size_t m_origin_column;
2017 };
2018
2019 class LinksToNode : public ParentNode {
2020 public:
2021     LinksToNode(size_t origin_column_index, const ConstRow& target_row)
2022         : m_origin_column(origin_column_index)
2023         , m_target_row(target_row)
2024     {
2025         m_dD = 10.0;
2026         m_dT = 50.0;
2027     }
2028
2029     void table_changed() override
2030     {
2031         m_column_type = m_table->get_column_type(m_origin_column);
2032         m_column = &const_cast<Table*>(m_table.get())->get_column_link_base(m_origin_column);
2033         REALM_ASSERT(m_column_type == type_Link || m_column_type == type_LinkList);
2034     }
2035
2036     void verify_column() const override
2037     {
2038         do_verify_column(m_column, m_origin_column);
2039     }
2040
2041     virtual std::string describe() const override
2042     {
2043         return this->describe_column(m_origin_column) + " " + describe_condition() + " " + util::serializer::print_value(m_target_row.get_index());
2044     }
2045     virtual std::string describe_condition() const override
2046     {
2047         return "links to";
2048     }
2049
2050
2051     size_t find_first_local(size_t start, size_t end) override
2052     {
2053         REALM_ASSERT(m_column);
2054         if (!m_target_row.is_attached())
2055             return not_found;
2056
2057         if (m_column_type == type_Link) {
2058             LinkColumn& cl = static_cast<LinkColumn&>(*m_column);
2059             return cl.find_first(m_target_row.get_index() + 1, start,
2060                                  end); // LinkColumn stores link to row N as the integer N + 1
2061         }
2062         else if (m_column_type == type_LinkList) {
2063             LinkListColumn& cll = static_cast<LinkListColumn&>(*m_column);
2064
2065             for (size_t i = start; i < end; i++) {
2066                 LinkViewRef lv = cll.get(i);
2067                 if (lv->find(m_target_row.get_index()) != not_found)
2068                     return i;
2069             }
2070         }
2071
2072         return not_found;
2073     }
2074
2075     std::unique_ptr<ParentNode> clone(QueryNodeHandoverPatches* patches) const override
2076     {
2077         return std::unique_ptr<ParentNode>(patches ? new LinksToNode(*this, patches) : new LinksToNode(*this));
2078     }
2079
2080     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
2081     {
2082         REALM_ASSERT(patches.size());
2083         std::unique_ptr<QueryNodeHandoverPatch> abstract_patch = std::move(patches.back());
2084         patches.pop_back();
2085
2086         auto patch = dynamic_cast<LinksToNodeHandoverPatch*>(abstract_patch.get());
2087         REALM_ASSERT(patch);
2088
2089         m_origin_column = patch->m_origin_column;
2090         m_target_row.apply_and_consume_patch(patch->m_target_row, group);
2091
2092         ParentNode::apply_handover_patch(patches, group);
2093     }
2094
2095 private:
2096     size_t m_origin_column = npos;
2097     ConstRow m_target_row;
2098     LinkColumnBase* m_column = nullptr;
2099     DataType m_column_type;
2100
2101     LinksToNode(const LinksToNode& source, QueryNodeHandoverPatches* patches)
2102         : ParentNode(source, patches)
2103     {
2104         auto patch = std::make_unique<LinksToNodeHandoverPatch>();
2105         patch->m_origin_column = source.m_column->get_column_index();
2106         ConstRow::generate_patch(source.m_target_row, patch->m_target_row);
2107         patches->push_back(std::move(patch));
2108     }
2109 };
2110
2111 } // namespace realm
2112
2113 #endif // REALM_QUERY_ENGINE_HPP