iOS/Pods/Realm/include/core/realm/query_expression.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 This file lets you write queries in C++ syntax like: Expression* e = (first + 1 / second >= third + 12.3);
  21
  22 Type conversion/promotion semantics is the same as in the C++ expressions, e.g float + int > double == float +
  23 (float)int > double.
  24
  25
  26 Grammar:
  27 -----------------------------------------------------------------------------------------------------------------------
  28     Expression:         Subexpr2<T>  Compare<Cond, T>  Subexpr2<T>
  29                         operator! Expression
  30
  31     Subexpr2<T>:        Value<T>
  32                         Columns<T>
  33                         Subexpr2<T>  Operator<Oper<T>  Subexpr2<T>
  34                         power(Subexpr2<T>) // power(x) = x * x, as example of unary operator
  35
  36     Value<T>:           T
  37
  38     Operator<Oper<T>>:  +, -, *, /
  39
  40     Compare<Cond, T>:   ==, !=, >=, <=, >, <
  41
  42     T:                  bool, int, int64_t, float, double, StringData
  43
  44
  45 Class diagram
  46 -----------------------------------------------------------------------------------------------------------------------
  47 Subexpr2
  48     void evaluate(size_t i, ValueBase* destination)
  49
  50 Compare: public Subexpr2
  51     size_t find_first(size_t start, size_t end)     // main method that executes query
  52
  53     unique_ptr<Subexpr2> m_left;                               // left expression subtree
  54     unique_ptr<Subexpr2> m_right;                              // right expression subtree
  55
  56 Operator: public Subexpr2
  57     void evaluate(size_t i, ValueBase* destination)
  58     unique_ptr<Subexpr2> m_left;                               // left expression subtree
  59     unique_ptr<Subexpr2> m_right;                              // right expression subtree
  60
  61 Value<T>: public Subexpr2
  62     void evaluate(size_t i, ValueBase* destination)
  63     T m_v[8];
  64
  65 Columns<T>: public Subexpr2
  66     void evaluate(size_t i, ValueBase* destination)
  67     SequentialGetter<T> sg;                         // class bound to a column, lets you read values in a fast way
  68     Table* m_table;
  69
  70 class ColumnAccessor<>: public Columns<double>
  71
  72
  73 Call diagram:
  74 -----------------------------------------------------------------------------------------------------------------------
  75 Example of 'table.first > 34.6 + table.second':
  76
  77 size_t Compare<Greater>::find_first()-------------+
  78          |                                        |
  79          |                                        |
  80          |                                        |
  81          +--> Columns<float>::evaluate()          +--------> Operator<Plus>::evaluate()
  82                                                                 |               |
  83                                                Value<float>::evaluate()    Columns<float>::evaluate()
  84
  85 Operator, Value and Columns have an evaluate(size_t i, ValueBase* destination) method which returns a Value<T>
  86 containing 8 values representing table rows i...i + 7.
  87
  88 So Value<T> contains 8 concecutive values and all operations are based on these chunks. This is
  89 to save overhead by virtual calls needed for evaluating a query that has been dynamically constructed at runtime.
  90
  91
  92 Memory allocation:
  93 -----------------------------------------------------------------------------------------------------------------------
  94 Subexpressions created by the end-user are stack allocated. They are cloned to the heap when passed to UnaryOperator,
  95 Operator, and Compare. Those types own the clones and deallocate them when destroyed.
  96
  97
  98 Caveats, notes and todos
  99 -----------------------------------------------------------------------------------------------------------------------
 100     * Perhaps disallow columns from two different tables in same expression
 101     * The name Columns (with s) an be confusing because we also have Column (without s)
 102     * We have Columns::m_table, Query::m_table and ColumnAccessorBase::m_table that point at the same thing, even with
 103       ColumnAccessor<> extending Columns. So m_table is redundant, but this is in order to keep class dependencies and
 104       entanglement low so that the design is flexible (if you perhaps later want a Columns class that is not dependent
 105       on ColumnAccessor)
 106
 107 Nulls
 108 -----------------------------------------------------------------------------------------------------------------------
 109 First note that at array level, nulls are distinguished between non-null in different ways:
 110 String:
 111     m_data == 0 && m_size == 0
 112
 113 Integer, Bool, OldDateTime stored in ArrayIntNull:
 114     value == get(0) (entry 0 determins a magic value that represents nulls)
 115
 116 Float/double:
 117     null::is_null(value) which tests if value bit-matches one specific bit pattern reserved for null
 118
 119 The Columns class encapsulates all this into a simple class that, for any type T has
 120     evaluate(size_t index) that reads values from a column, taking nulls in count
 121     get(index)
 122     set(index)
 123     is_null(index)
 124     set_null(index)
 125 */
 126
 127 #ifndef REALM_QUERY_EXPRESSION_HPP
 128 #define REALM_QUERY_EXPRESSION_HPP
 129
 130 #include <realm/column_link.hpp>
 131 #include <realm/column_linklist.hpp>
 132 #include <realm/column_table.hpp>
 133 #include <realm/column_type_traits.hpp>
 134 #include <realm/impl/sequential_getter.hpp>
 135 #include <realm/link_view.hpp>
 136 #include <realm/metrics/query_info.hpp>
 137 #include <realm/query_operators.hpp>
 138 #include <realm/util/optional.hpp>
 139 #include <realm/util/serializer.hpp>
 140
 141 #include <numeric>
 142
 143 // Normally, if a next-generation-syntax condition is supported by the old query_engine.hpp, a query_engine node is
 144 // created because it's faster (by a factor of 5 - 10). Because many of our existing next-generation-syntax unit
 145 // unit tests are indeed simple enough to fallback to old query_engine, query_expression gets low test coverage. Undef
 146 // flag to get higher query_expression test coverage. This is a good idea to try out each time you develop on/modify
 147 // query_expression.
 148
 149 #define REALM_OLDQUERY_FALLBACK
 150
 151 namespace realm {
 152
 153 template <class T>
 154 T minimum(T a, T b)
 155 {
 156     return a < b ? a : b;
 157 }
 158
 159 #ifdef REALM_OLDQUERY_FALLBACK
 160 // Hack to avoid template instantiation errors. See create(). Todo, see if we can simplify only_numeric somehow
 161 namespace _impl {
 162
 163 template <class T, class U>
 164 inline T only_numeric(U in)
 165 {
 166     return static_cast<T>(util::unwrap(in));
 167 }
 168
 169 template <class T>
 170 inline int only_numeric(const StringData&)
 171 {
 172     REALM_ASSERT(false);
 173     return 0;
 174 }
 175
 176 template <class T>
 177 inline int only_numeric(const BinaryData&)
 178 {
 179     REALM_ASSERT(false);
 180     return 0;
 181 }
 182
 183 template <class T>
 184 inline StringData only_string(T in)
 185 {
 186     REALM_ASSERT(false);
 187     static_cast<void>(in);
 188     return StringData();
 189 }
 190
 191 inline StringData only_string(StringData in)
 192 {
 193     return in;
 194 }
 195
 196 template <class T, class U>
 197 inline T no_timestamp(U in)
 198 {
 199     return static_cast<T>(util::unwrap(in));
 200 }
 201
 202 template <class T>
 203 inline int no_timestamp(const Timestamp&)
 204 {
 205     REALM_ASSERT(false);
 206     return 0;
 207 }
 208
 209 } // namespace _impl
 210
 211 #endif // REALM_OLDQUERY_FALLBACK
 212
 213 template <class T>
 214 struct Plus {
 215     T operator()(T v1, T v2) const
 216     {
 217         return v1 + v2;
 218     }
 219     static std::string description()
 220     {
 221         return "plus";
 222     }
 223     typedef T type;
 224 };
 225
 226 template <class T>
 227 struct Minus {
 228     T operator()(T v1, T v2) const
 229     {
 230         return v1 - v2;
 231     }
 232     static std::string description()
 233     {
 234         return "minus";
 235     }
 236     typedef T type;
 237 };
 238
 239 template <class T>
 240 struct Div {
 241     T operator()(T v1, T v2) const
 242     {
 243         return v1 / v2;
 244     }
 245     static std::string description()
 246     {
 247         return "divided by";
 248     }
 249     typedef T type;
 250 };
 251
 252 template <class T>
 253 struct Mul {
 254     T operator()(T v1, T v2) const
 255     {
 256         return v1 * v2;
 257     }
 258     static std::string description()
 259     {
 260         return "multiplied by";
 261     }
 262     typedef T type;
 263 };
 264
 265 // Unary operator
 266 template <class T>
 267 struct Pow {
 268     T operator()(T v) const
 269     {
 270         return v * v;
 271     }
 272     static std::string description()
 273     {
 274         return "to the power of";
 275     }
 276     typedef T type;
 277 };
 278
 279 // Finds a common type for T1 and T2 according to C++ conversion/promotion in arithmetic (float + int => float, etc)
 280 template <class T1, class T2, bool T1_is_int = std::numeric_limits<T1>::is_integer || std::is_same<T1, null>::value,
 281           bool T2_is_int = std::numeric_limits<T2>::is_integer || std::is_same<T2, null>::value,
 282           bool T1_is_widest = (sizeof(T1) > sizeof(T2) || std::is_same<T2, null>::value)>
 283 struct Common;
 284 template <class T1, class T2, bool b>
 285 struct Common<T1, T2, b, b, true> {
 286     typedef T1 type;
 287 };
 288 template <class T1, class T2, bool b>
 289 struct Common<T1, T2, b, b, false> {
 290     typedef T2 type;
 291 };
 292 template <class T1, class T2, bool b>
 293 struct Common<T1, T2, false, true, b> {
 294     typedef T1 type;
 295 };
 296 template <class T1, class T2, bool b>
 297 struct Common<T1, T2, true, false, b> {
 298     typedef T2 type;
 299 };
 300
 301
 302 struct RowIndex {
 303     enum DetachedTag {
 304         Detached,
 305     };
 306
 307     explicit RowIndex()
 308         : m_row_index(npos)
 309     {
 310     }
 311     explicit RowIndex(size_t row_index)
 312         : m_row_index(row_index)
 313     {
 314     }
 315     RowIndex(DetachedTag)
 316         : m_row_index()
 317     {
 318     }
 319
 320     bool is_attached() const
 321     {
 322         return bool(m_row_index);
 323     }
 324     bool is_null() const
 325     {
 326         return is_attached() && *m_row_index == npos;
 327     }
 328
 329     bool operator==(const RowIndex& other) const
 330     {
 331         // Row indexes that are detached are never equal to any other row index.
 332         if (!is_attached() || !other.is_attached())
 333             return false;
 334         return m_row_index == other.m_row_index;
 335     }
 336     bool operator!=(const RowIndex& other) const
 337     {
 338         return !(*this == other);
 339     }
 340     template <class C, class T>
 341     friend std::basic_ostream<C, T>& operator<<(std::basic_ostream<C, T>&, const RowIndex&);
 342
 343 private:
 344     util::Optional<size_t> m_row_index;
 345 };
 346
 347 template <class C, class T>
 348 inline std::basic_ostream<C, T>& operator<<(std::basic_ostream<C, T>& out, const RowIndex& r)
 349 {
 350     if (!r.is_attached()) {
 351         out << "detached row";
 352     } else if (r.is_null()) {
 353         out << "null row";
 354     } else {
 355         out << r.m_row_index;
 356     }
 357     return out;
 358 }
 359
 360 struct ValueBase {
 361     static const size_t default_size = 8;
 362     virtual void export_bool(ValueBase& destination) const = 0;
 363     virtual void export_Timestamp(ValueBase& destination) const = 0;
 364     virtual void export_int(ValueBase& destination) const = 0;
 365     virtual void export_float(ValueBase& destination) const = 0;
 366     virtual void export_int64_t(ValueBase& destination) const = 0;
 367     virtual void export_double(ValueBase& destination) const = 0;
 368     virtual void export_StringData(ValueBase& destination) const = 0;
 369     virtual void export_BinaryData(ValueBase& destination) const = 0;
 370     virtual void export_RowIndex(ValueBase& destination) const = 0;
 371     virtual void export_null(ValueBase& destination) const = 0;
 372     virtual void import(const ValueBase& destination) = 0;
 373
 374     // If true, all values in the class come from a link list of a single field in the parent table (m_table). If
 375     // false, then values come from successive rows of m_table (query operations are operated on in bulks for speed)
 376     bool m_from_link_list;
 377
 378     // Number of values stored in the class.
 379     size_t m_values;
 380 };
 381
 382 class Expression {
 383 public:
 384     Expression()
 385     {
 386     }
 387     virtual ~Expression()
 388     {
 389     }
 390
 391     virtual size_t find_first(size_t start, size_t end) const = 0;
 392     virtual void set_base_table(const Table* table) = 0;
 393     virtual void verify_column() const = 0;
 394     virtual const Table* get_base_table() const = 0;
 395     virtual std::string description() const = 0;
 396
 397     virtual std::unique_ptr<Expression> clone(QueryNodeHandoverPatches*) const = 0;
 398     virtual void apply_handover_patch(QueryNodeHandoverPatches&, Group&)
 399     {
 400     }
 401 };
 402
 403 template <typename T, typename... Args>
 404 std::unique_ptr<Expression> make_expression(Args&&... args)
 405 {
 406     return std::unique_ptr<Expression>(new T(std::forward<Args>(args)...));
 407 }
 408
 409 class Subexpr {
 410 public:
 411     virtual ~Subexpr()
 412     {
 413     }
 414
 415     virtual std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* = nullptr) const = 0;
 416     virtual void apply_handover_patch(QueryNodeHandoverPatches&, Group&)
 417     {
 418     }
 419
 420     // When the user constructs a query, it always "belongs" to one single base/parent table (regardless of
 421     // any links or not and regardless of any queries assembled with || or &&). When you do a Query::find(),
 422     // then Query::m_table is set to this table, and set_base_table() is called on all Columns and LinkMaps in
 423     // the query expression tree so that they can set/update their internals as required.
 424     //
 425     // During thread-handover of a Query, set_base_table() is also called to make objects point at the new table
 426     // instead of the old one from the old thread.
 427     virtual void set_base_table(const Table*)
 428     {
 429     }
 430
 431     virtual void verify_column() const = 0;
 432     virtual std::string description() const = 0;
 433
 434     // Recursively fetch tables of columns in expression tree. Used when user first builds a stand-alone expression
 435     // and
 436     // binds it to a Query at a later time
 437     virtual const Table* get_base_table() const
 438     {
 439         return nullptr;
 440     }
 441
 442     virtual void evaluate(size_t index, ValueBase& destination) = 0;
 443 };
 444
 445 template <typename T, typename... Args>
 446 std::unique_ptr<Subexpr> make_subexpr(Args&&... args)
 447 {
 448     return std::unique_ptr<Subexpr>(new T(std::forward<Args>(args)...));
 449 }
 450
 451 template <class T>
 452 class Columns;
 453 template <class T>
 454 class Value;
 455 class ConstantStringValue;
 456 template <class T>
 457 class Subexpr2;
 458 template <class oper, class TLeft = Subexpr, class TRight = Subexpr>
 459 class Operator;
 460 template <class oper, class TLeft = Subexpr>
 461 class UnaryOperator;
 462 template <class oper, class TLeft = Subexpr>
 463 class SizeOperator;
 464 template <class TCond, class T, class TLeft = Subexpr, class TRight = Subexpr>
 465 class Compare;
 466 template <bool has_links>
 467 class UnaryLinkCompare;
 468 class ColumnAccessorBase;
 469
 470
 471 // Handle cases where left side is a constant (int, float, int64_t, double, StringData)
 472 template <class Cond, class L, class R>
 473 Query create(L left, const Subexpr2<R>& right)
 474 {
 475 // Purpose of below code is to intercept the creation of a condition and test if it's supported by the old
 476 // query_engine.hpp which is faster. If it's supported, create a query_engine.hpp node, otherwise create a
 477 // query_expression.hpp node.
 478 //
 479 // This method intercepts only Value <cond> Subexpr2. Interception of Subexpr2 <cond> Subexpr is elsewhere.
 480
 481 #ifdef REALM_OLDQUERY_FALLBACK // if not defined, then never fallback to query_engine.hpp; always use query_expression
 482     const Columns<R>* column = dynamic_cast<const Columns<R>*>(&right);
 483     // TODO: recognize size operator expressions
 484     // auto size_operator = dynamic_cast<const SizeOperator<Size<StringData>, Subexpr>*>(&right);
 485
 486     if (column && ((std::numeric_limits<L>::is_integer && std::numeric_limits<R>::is_integer) ||
 487                    (std::is_same<L, double>::value && std::is_same<R, double>::value) ||
 488                    (std::is_same<L, float>::value && std::is_same<R, float>::value) ||
 489                    (std::is_same<L, Timestamp>::value && std::is_same<R, Timestamp>::value) ||
 490                    (std::is_same<L, StringData>::value && std::is_same<R, StringData>::value) ||
 491                    (std::is_same<L, BinaryData>::value && std::is_same<R, BinaryData>::value)) &&
 492         !column->links_exist()) {
 493         const Table* t = column->get_base_table();
 494         Query q = Query(*t);
 495
 496         if (std::is_same<Cond, Less>::value)
 497             q.greater(column->column_ndx(), _impl::only_numeric<R>(left));
 498         else if (std::is_same<Cond, Greater>::value)
 499             q.less(column->column_ndx(), _impl::only_numeric<R>(left));
 500         else if (std::is_same<Cond, Equal>::value)
 501             q.equal(column->column_ndx(), left);
 502         else if (std::is_same<Cond, NotEqual>::value)
 503             q.not_equal(column->column_ndx(), left);
 504         else if (std::is_same<Cond, LessEqual>::value)
 505             q.greater_equal(column->column_ndx(), _impl::only_numeric<R>(left));
 506         else if (std::is_same<Cond, GreaterEqual>::value)
 507             q.less_equal(column->column_ndx(), _impl::only_numeric<R>(left));
 508         else if (std::is_same<Cond, EqualIns>::value)
 509             q.equal(column->column_ndx(), _impl::only_string(left), false);
 510         else if (std::is_same<Cond, NotEqualIns>::value)
 511             q.not_equal(column->column_ndx(), _impl::only_string(left), false);
 512         else if (std::is_same<Cond, BeginsWith>::value)
 513             q.begins_with(column->column_ndx(), _impl::only_string(left));
 514         else if (std::is_same<Cond, BeginsWithIns>::value)
 515             q.begins_with(column->column_ndx(), _impl::only_string(left), false);
 516         else if (std::is_same<Cond, EndsWith>::value)
 517             q.ends_with(column->column_ndx(), _impl::only_string(left));
 518         else if (std::is_same<Cond, EndsWithIns>::value)
 519             q.ends_with(column->column_ndx(), _impl::only_string(left), false);
 520         else if (std::is_same<Cond, Contains>::value)
 521             q.contains(column->column_ndx(), _impl::only_string(left));
 522         else if (std::is_same<Cond, ContainsIns>::value)
 523             q.contains(column->column_ndx(), _impl::only_string(left), false);
 524         else if (std::is_same<Cond, Like>::value)
 525             q.like(column->column_ndx(), _impl::only_string(left));
 526         else if (std::is_same<Cond, LikeIns>::value)
 527             q.like(column->column_ndx(), _impl::only_string(left), false);
 528         else {
 529             // query_engine.hpp does not support this Cond. Please either add support for it in query_engine.hpp or
 530             // fallback to using use 'return new Compare<>' instead.
 531             REALM_ASSERT(false);
 532         }
 533         // Return query_engine.hpp node
 534         return q;
 535     }
 536     else
 537 #endif
 538     {
 539         // Return query_expression.hpp node
 540         using CommonType = typename Common<L, R>::type;
 541         using ValueType =
 542             typename std::conditional<std::is_same<L, StringData>::value, ConstantStringValue, Value<L>>::type;
 543         return make_expression<Compare<Cond, CommonType>>(make_subexpr<ValueType>(left), right.clone());
 544     }
 545 }
 546
 547
 548 // All overloads where left-hand-side is Subexpr2<L>:
 549 //
 550 // left-hand-side       operator                              right-hand-side
 551 // Subexpr2<L>          +, -, *, /, <, >, ==, !=, <=, >=      R, Subexpr2<R>
 552 //
 553 // For L = R = {int, int64_t, float, double, StringData, Timestamp}:
 554 template <class L, class R>
 555 class Overloads {
 556     typedef typename Common<L, R>::type CommonType;
 557
 558     std::unique_ptr<Subexpr> clone_subexpr() const
 559     {
 560         return static_cast<const Subexpr2<L>&>(*this).clone();
 561     }
 562
 563 public:
 564     // Arithmetic, right side constant
 565     Operator<Plus<CommonType>> operator+(R right) const
 566     {
 567         return {clone_subexpr(), make_subexpr<Value<R>>(right)};
 568     }
 569     Operator<Minus<CommonType>> operator-(R right) const
 570     {
 571         return {clone_subexpr(), make_subexpr<Value<R>>(right)};
 572     }
 573     Operator<Mul<CommonType>> operator*(R right) const
 574     {
 575         return {clone_subexpr(), make_subexpr<Value<R>>(right)};
 576     }
 577     Operator<Div<CommonType>> operator/(R right) const
 578     {
 579         return {clone_subexpr(), make_subexpr<Value<R>>(right)};
 580     }
 581
 582     // Arithmetic, right side subexpression
 583     Operator<Plus<CommonType>> operator+(const Subexpr2<R>& right) const
 584     {
 585         return {clone_subexpr(), right.clone()};
 586     }
 587     Operator<Minus<CommonType>> operator-(const Subexpr2<R>& right) const
 588     {
 589         return {clone_subexpr(), right.clone()};
 590     }
 591     Operator<Mul<CommonType>> operator*(const Subexpr2<R>& right) const
 592     {
 593         return {clone_subexpr(), right.clone()};
 594     }
 595     Operator<Div<CommonType>> operator/(const Subexpr2<R>& right) const
 596     {
 597         return {clone_subexpr(), right.clone()};
 598     }
 599
 600     // Compare, right side constant
 601     Query operator>(R right)
 602     {
 603         return create<Less>(right, static_cast<Subexpr2<L>&>(*this));
 604     }
 605     Query operator<(R right)
 606     {
 607         return create<Greater>(right, static_cast<Subexpr2<L>&>(*this));
 608     }
 609     Query operator>=(R right)
 610     {
 611         return create<LessEqual>(right, static_cast<Subexpr2<L>&>(*this));
 612     }
 613     Query operator<=(R right)
 614     {
 615         return create<GreaterEqual>(right, static_cast<Subexpr2<L>&>(*this));
 616     }
 617     Query operator==(R right)
 618     {
 619         return create<Equal>(right, static_cast<Subexpr2<L>&>(*this));
 620     }
 621     Query operator!=(R right)
 622     {
 623         return create<NotEqual>(right, static_cast<Subexpr2<L>&>(*this));
 624     }
 625
 626     // Purpose of this method is to intercept the creation of a condition and test if it's supported by the old
 627     // query_engine.hpp which is faster. If it's supported, create a query_engine.hpp node, otherwise create a
 628     // query_expression.hpp node.
 629     //
 630     // This method intercepts Subexpr2 <cond> Subexpr2 only. Value <cond> Subexpr2 is intercepted elsewhere.
 631     template <class Cond>
 632     Query create2(const Subexpr2<R>& right)
 633     {
 634 #ifdef REALM_OLDQUERY_FALLBACK // if not defined, never fallback query_engine; always use query_expression
 635         // Test if expressions are of type Columns. Other possibilities are Value and Operator.
 636         const Columns<R>* left_col = dynamic_cast<const Columns<R>*>(static_cast<Subexpr2<L>*>(this));
 637         const Columns<R>* right_col = dynamic_cast<const Columns<R>*>(&right);
 638
 639         // query_engine supports 'T-column <op> <T-column>' for T = {int64_t, float, double}, op = {<, >, ==, !=, <=,
 640         // >=},
 641         // but only if both columns are non-nullable, and aren't in linked tables.
 642         if (left_col && right_col && std::is_same<L, R>::value && !left_col->is_nullable() &&
 643             !right_col->is_nullable() && !left_col->links_exist() && !right_col->links_exist() &&
 644             !std::is_same<L, Timestamp>::value) {
 645             const Table* t = left_col->get_base_table();
 646             Query q = Query(*t);
 647
 648             if (std::numeric_limits<L>::is_integer || std::is_same<L, OldDateTime>::value) {
 649                 if (std::is_same<Cond, Less>::value)
 650                     q.less_int(left_col->column_ndx(), right_col->column_ndx());
 651                 else if (std::is_same<Cond, Greater>::value)
 652                     q.greater_int(left_col->column_ndx(), right_col->column_ndx());
 653                 else if (std::is_same<Cond, Equal>::value)
 654                     q.equal_int(left_col->column_ndx(), right_col->column_ndx());
 655                 else if (std::is_same<Cond, NotEqual>::value)
 656                     q.not_equal_int(left_col->column_ndx(), right_col->column_ndx());
 657                 else if (std::is_same<Cond, LessEqual>::value)
 658                     q.less_equal_int(left_col->column_ndx(), right_col->column_ndx());
 659                 else if (std::is_same<Cond, GreaterEqual>::value)
 660                     q.greater_equal_int(left_col->column_ndx(), right_col->column_ndx());
 661                 else {
 662                     REALM_ASSERT(false);
 663                 }
 664             }
 665             else if (std::is_same<L, float>::value) {
 666                 if (std::is_same<Cond, Less>::value)
 667                     q.less_float(left_col->column_ndx(), right_col->column_ndx());
 668                 else if (std::is_same<Cond, Greater>::value)
 669                     q.greater_float(left_col->column_ndx(), right_col->column_ndx());
 670                 else if (std::is_same<Cond, Equal>::value)
 671                     q.equal_float(left_col->column_ndx(), right_col->column_ndx());
 672                 else if (std::is_same<Cond, NotEqual>::value)
 673                     q.not_equal_float(left_col->column_ndx(), right_col->column_ndx());
 674                 else if (std::is_same<Cond, LessEqual>::value)
 675                     q.less_equal_float(left_col->column_ndx(), right_col->column_ndx());
 676                 else if (std::is_same<Cond, GreaterEqual>::value)
 677                     q.greater_equal_float(left_col->column_ndx(), right_col->column_ndx());
 678                 else {
 679                     REALM_ASSERT(false);
 680                 }
 681             }
 682             else if (std::is_same<L, double>::value) {
 683                 if (std::is_same<Cond, Less>::value)
 684                     q.less_double(left_col->column_ndx(), right_col->column_ndx());
 685                 else if (std::is_same<Cond, Greater>::value)
 686                     q.greater_double(left_col->column_ndx(), right_col->column_ndx());
 687                 else if (std::is_same<Cond, Equal>::value)
 688                     q.equal_double(left_col->column_ndx(), right_col->column_ndx());
 689                 else if (std::is_same<Cond, NotEqual>::value)
 690                     q.not_equal_double(left_col->column_ndx(), right_col->column_ndx());
 691                 else if (std::is_same<Cond, LessEqual>::value)
 692                     q.less_equal_double(left_col->column_ndx(), right_col->column_ndx());
 693                 else if (std::is_same<Cond, GreaterEqual>::value)
 694                     q.greater_equal_double(left_col->column_ndx(), right_col->column_ndx());
 695                 else {
 696                     REALM_ASSERT(false);
 697                 }
 698             }
 699             else {
 700                 REALM_ASSERT(false);
 701             }
 702             // Return query_engine.hpp node
 703             return q;
 704         }
 705         else
 706 #endif
 707         {
 708             // Return query_expression.hpp node
 709             return make_expression<Compare<Cond, typename Common<L, R>::type>>(clone_subexpr(), right.clone());
 710         }
 711     }
 712
 713     // Compare, right side subexpression
 714     Query operator==(const Subexpr2<R>& right)
 715     {
 716         return create2<Equal>(right);
 717     }
 718     Query operator!=(const Subexpr2<R>& right)
 719     {
 720         return create2<NotEqual>(right);
 721     }
 722     Query operator>(const Subexpr2<R>& right)
 723     {
 724         return create2<Greater>(right);
 725     }
 726     Query operator<(const Subexpr2<R>& right)
 727     {
 728         return create2<Less>(right);
 729     }
 730     Query operator>=(const Subexpr2<R>& right)
 731     {
 732         return create2<GreaterEqual>(right);
 733     }
 734     Query operator<=(const Subexpr2<R>& right)
 735     {
 736         return create2<LessEqual>(right);
 737     }
 738 };
 739
 740 // With this wrapper class we can define just 20 overloads inside Overloads<L, R> instead of 5 * 20 = 100. Todo: We
 741 // can
 742 // consider if it's simpler/better to remove this class completely and just list all 100 overloads manually anyway.
 743 template <class T>
 744 class Subexpr2 : public Subexpr,
 745                  public Overloads<T, const char*>,
 746                  public Overloads<T, int>,
 747                  public Overloads<T, float>,
 748                  public Overloads<T, double>,
 749                  public Overloads<T, int64_t>,
 750                  public Overloads<T, StringData>,
 751                  public Overloads<T, bool>,
 752                  public Overloads<T, Timestamp>,
 753                  public Overloads<T, OldDateTime>,
 754                  public Overloads<T, null> {
 755 public:
 756     virtual ~Subexpr2()
 757     {
 758     }
 759
 760 #define RLM_U2(t, o) using Overloads<T, t>::operator o;
 761 #define RLM_U(o)                                                                                                     \
 762     RLM_U2(int, o)                                                                                                   \
 763     RLM_U2(float, o)                                                                                                 \
 764     RLM_U2(double, o)                                                                                                \
 765     RLM_U2(int64_t, o)                                                                                               \
 766     RLM_U2(StringData, o) RLM_U2(bool, o) RLM_U2(OldDateTime, o) RLM_U2(Timestamp, o) RLM_U2(null, o)
 767     RLM_U(+) RLM_U(-) RLM_U(*) RLM_U(/) RLM_U(>) RLM_U(<) RLM_U(==) RLM_U(!=) RLM_U(>=) RLM_U(<=)
 768 };
 769
 770 // Subexpr2<Link> only provides equality comparisons. Their implementations can be found later in this file.
 771 template <>
 772 class Subexpr2<Link> : public Subexpr {
 773 };
 774
 775 template <>
 776 class Subexpr2<StringData> : public Subexpr, public Overloads<StringData, StringData> {
 777 public:
 778     Query equal(StringData sd, bool case_sensitive = true);
 779     Query equal(const Subexpr2<StringData>& col, bool case_sensitive = true);
 780     Query not_equal(StringData sd, bool case_sensitive = true);
 781     Query not_equal(const Subexpr2<StringData>& col, bool case_sensitive = true);
 782     Query begins_with(StringData sd, bool case_sensitive = true);
 783     Query begins_with(const Subexpr2<StringData>& col, bool case_sensitive = true);
 784     Query ends_with(StringData sd, bool case_sensitive = true);
 785     Query ends_with(const Subexpr2<StringData>& col, bool case_sensitive = true);
 786     Query contains(StringData sd, bool case_sensitive = true);
 787     Query contains(const Subexpr2<StringData>& col, bool case_sensitive = true);
 788     Query like(StringData sd, bool case_sensitive = true);
 789     Query like(const Subexpr2<StringData>& col, bool case_sensitive = true);
 790 };
 791
 792 /*
 793 This class is used to store N values of type T = {int64_t, bool, OldDateTime or StringData}, and allows an entry
 794 to be null too. It's used by the Value class for internal storage.
 795
 796 To indicate nulls, we could have chosen a separate bool vector or some other bitmask construction. But for
 797 performance, we customize indication of nulls to match the same indication that is used in the persisted database
 798 file
 799
 800 Queries in query_expression.hpp execute by processing chunks of 8 rows at a time. Assume you have a column:
 801
 802     price (int) = {1, 2, 3, null, 1, 6, 6, 9, 5, 2, null}
 803
 804 And perform a query:
 805
 806     Query q = (price + 2 == 5);
 807
 808 query_expression.hpp will then create a NullableVector<int> = {5, 5, 5, 5, 5, 5, 5, 5} and then read values
 809 NullableVector<int> = {1, 2, 3, null, 1, 6, 6, 9} from the column, and then perform `+` and `==` on these chunks.
 810
 811 See the top of this file for more information on all this.
 812
 813 Assume the user specifies the null constant in a query:
 814
 815 Query q = (price == null)
 816
 817 The query system will then construct a NullableVector of type `null` (NullableVector<null>). This allows compile
 818 time optimizations for these cases.
 819 */
 820
 821 template <class T, size_t prealloc = 8>
 822 struct NullableVector {
 823     using Underlying = typename util::RemoveOptional<T>::type;
 824     using t_storage =
 825         typename std::conditional<std::is_same<Underlying, bool>::value || std::is_same<Underlying, int>::value,
 826                                   int64_t, Underlying>::type;
 827
 828     NullableVector()
 829     {
 830     }
 831
 832     NullableVector& operator=(const NullableVector& other)
 833     {
 834         if (this != &other) {
 835             init(other.m_size);
 836             realm::safe_copy_n(other.m_first, other.m_size, m_first);
 837             m_null = other.m_null;
 838         }
 839         return *this;
 840     }
 841
 842     NullableVector(const NullableVector& other)
 843     {
 844         init(other.m_size);
 845         realm::safe_copy_n(other.m_first, other.m_size, m_first);
 846         m_null = other.m_null;
 847     }
 848
 849     ~NullableVector()
 850     {
 851         dealloc();
 852     }
 853
 854     T operator[](size_t index) const
 855     {
 856         REALM_ASSERT_3(index, <, m_size);
 857         return static_cast<T>(m_first[index]);
 858     }
 859
 860     inline bool is_null(size_t index) const
 861     {
 862         REALM_ASSERT((std::is_same<t_storage, int64_t>::value));
 863         return m_first[index] == m_null;
 864     }
 865
 866     inline void set_null(size_t index)
 867     {
 868         REALM_ASSERT((std::is_same<t_storage, int64_t>::value));
 869         m_first[index] = m_null;
 870     }
 871
 872     template <typename Type = t_storage>
 873     typename std::enable_if<std::is_same<Type, int64_t>::value, void>::type set(size_t index, t_storage value)
 874     {
 875         REALM_ASSERT((std::is_same<t_storage, int64_t>::value));
 876
 877         // If value collides with magic null value, then switch to a new unique representation for null
 878         if (REALM_UNLIKELY(value == m_null)) {
 879             // adding a prime will generate 2^64 unique values. Todo: Only works on 2's complement architecture
 880             uint64_t candidate = static_cast<uint64_t>(m_null) + 0xfffffffbULL;
 881             while (std::find(m_first, m_first + m_size, static_cast<int64_t>(candidate)) != m_first + m_size)
 882                 candidate += 0xfffffffbULL;
 883             std::replace(m_first, m_first + m_size, m_null, static_cast<int64_t>(candidate));
 884         }
 885         m_first[index] = value;
 886     }
 887
 888     template <typename Type = T>
 889     typename std::enable_if<realm::is_any<Type, float, double, OldDateTime, BinaryData, StringData, RowIndex,
 890                                           Timestamp, ConstTableRef, null>::value,
 891                             void>::type
 892     set(size_t index, t_storage value)
 893     {
 894         m_first[index] = value;
 895     }
 896
 897     inline util::Optional<T> get(size_t index) const
 898     {
 899         if (is_null(index))
 900             return util::none;
 901
 902         return util::make_optional((*this)[index]);
 903     }
 904
 905     inline void set(size_t index, util::Optional<Underlying> value)
 906     {
 907         if (value) {
 908             Underlying v = *value;
 909             set(index, v);
 910         }
 911         else {
 912             set_null(index);
 913         }
 914     }
 915
 916     void fill(T value)
 917     {
 918         for (size_t t = 0; t < m_size; t++) {
 919             if (std::is_same<T, null>::value)
 920                 set_null(t);
 921             else
 922                 set(t, value);
 923         }
 924     }
 925
 926     void init(size_t size)
 927     {
 928         if (size == m_size)
 929             return;
 930
 931         dealloc();
 932         m_size = size;
 933         if (m_size > 0) {
 934             if (m_size > prealloc)
 935                 m_first = reinterpret_cast<t_storage*>(new t_storage[m_size]);
 936             else
 937                 m_first = m_cache;
 938         }
 939     }
 940
 941     void init(size_t size, T values)
 942     {
 943         init(size);
 944         fill(values);
 945     }
 946
 947     void dealloc()
 948     {
 949         if (m_first) {
 950             if (m_size > prealloc)
 951                 delete[] m_first;
 952             m_first = nullptr;
 953         }
 954     }
 955
 956     t_storage m_cache[prealloc];
 957     t_storage* m_first = &m_cache[0];
 958     size_t m_size = 0;
 959
 960     int64_t m_null = reinterpret_cast<int64_t>(&m_null); // choose magic value to represent nulls
 961 };
 962
 963 // Double
 964 // NOTE: fails in gcc 4.8 without `inline`. Do not remove. Same applies for all methods below.
 965 template <>
 966 inline bool NullableVector<double>::is_null(size_t index) const
 967 {
 968     return null::is_null_float(m_first[index]);
 969 }
 970
 971 template <>
 972 inline void NullableVector<double>::set_null(size_t index)
 973 {
 974     m_first[index] = null::get_null_float<double>();
 975 }
 976
 977 // Float
 978 template <>
 979 inline bool NullableVector<float>::is_null(size_t index) const
 980 {
 981     return null::is_null_float(m_first[index]);
 982 }
 983
 984 template <>
 985 inline void NullableVector<float>::set_null(size_t index)
 986 {
 987     m_first[index] = null::get_null_float<float>();
 988 }
 989
 990
 991 // Null
 992 template <>
 993 inline void NullableVector<null>::set_null(size_t)
 994 {
 995     return;
 996 }
 997 template <>
 998 inline bool NullableVector<null>::is_null(size_t) const
 999 {
1000     return true;
1001 }
1002
1003
1004 // OldDateTime
1005 template <>
1006 inline bool NullableVector<OldDateTime>::is_null(size_t index) const
1007 {
1008     return m_first[index].get_olddatetime() == m_null;
1009 }
1010
1011
1012 template <>
1013 inline void NullableVector<OldDateTime>::set_null(size_t index)
1014 {
1015     m_first[index] = m_null;
1016 }
1017
1018 // StringData
1019
1020 template <>
1021 inline bool NullableVector<StringData>::is_null(size_t index) const
1022 {
1023     return m_first[index].is_null();
1024 }
1025
1026 template <>
1027 inline void NullableVector<StringData>::set_null(size_t index)
1028 {
1029     m_first[index] = StringData();
1030 }
1031
1032 // BinaryData
1033
1034 template <>
1035 inline bool NullableVector<BinaryData>::is_null(size_t index) const
1036 {
1037     return m_first[index].is_null();
1038 }
1039
1040 template <>
1041 inline void NullableVector<BinaryData>::set_null(size_t index)
1042 {
1043     m_first[index] = BinaryData();
1044 }
1045
1046 // RowIndex
1047 template <>
1048 inline bool NullableVector<RowIndex>::is_null(size_t index) const
1049 {
1050     return m_first[index].is_null();
1051 }
1052 template <>
1053 inline void NullableVector<RowIndex>::set_null(size_t index)
1054 {
1055     m_first[index] = RowIndex();
1056 }
1057
1058
1059 // Timestamp
1060
1061 template <>
1062 inline bool NullableVector<Timestamp>::is_null(size_t index) const
1063 {
1064     return m_first[index].is_null();
1065 }
1066
1067 template <>
1068 inline void NullableVector<Timestamp>::set_null(size_t index)
1069 {
1070     m_first[index] = Timestamp{};
1071 }
1072
1073 // ConstTableRef
1074 template <>
1075 inline bool NullableVector<ConstTableRef>::is_null(size_t index) const
1076 {
1077     return !bool(m_first[index]);
1078 }
1079 template <>
1080 inline void NullableVector<ConstTableRef>::set_null(size_t index)
1081 {
1082     m_first[index].reset();
1083 }
1084
1085 template <typename Operator>
1086 struct OperatorOptionalAdapter {
1087     template <typename L, typename R>
1088     util::Optional<typename Operator::type> operator()(const util::Optional<L>& left, const util::Optional<R>& right)
1089     {
1090         if (!left || !right)
1091             return util::none;
1092         return Operator()(*left, *right);
1093     }
1094
1095     template <typename T>
1096     util::Optional<typename Operator::type> operator()(const util::Optional<T>& arg)
1097     {
1098         if (!arg)
1099             return util::none;
1100         return Operator()(*arg);
1101     }
1102 };
1103
1104
1105 struct TrueExpression : Expression {
1106     size_t find_first(size_t start, size_t end) const override
1107     {
1108         REALM_ASSERT(start <= end);
1109         if (start != end)
1110             return start;
1111
1112         return realm::not_found;
1113     }
1114     void set_base_table(const Table*) override
1115     {
1116     }
1117     const Table* get_base_table() const override
1118     {
1119         return nullptr;
1120     }
1121     void verify_column() const override
1122     {
1123     }
1124     std::string description() const override
1125     {
1126         return "TRUEPREDICATE";
1127     }
1128     std::unique_ptr<Expression> clone(QueryNodeHandoverPatches*) const override
1129     {
1130         return std::unique_ptr<Expression>(new TrueExpression(*this));
1131     }
1132 };
1133
1134
1135 struct FalseExpression : Expression {
1136     size_t find_first(size_t, size_t) const override
1137     {
1138         return realm::not_found;
1139     }
1140     void set_base_table(const Table*) override
1141     {
1142     }
1143     void verify_column() const override
1144     {
1145     }
1146     std::string description() const override
1147     {
1148         return "FALSEPREDICATE";
1149     }
1150     const Table* get_base_table() const override
1151     {
1152         return nullptr;
1153     }
1154     std::unique_ptr<Expression> clone(QueryNodeHandoverPatches*) const override
1155     {
1156         return std::unique_ptr<Expression>(new FalseExpression(*this));
1157     }
1158 };
1159
1160
1161 // Stores N values of type T. Can also exchange data with other ValueBase of different types
1162 template <class T>
1163 class Value : public ValueBase, public Subexpr2<T> {
1164 public:
1165     Value()
1166     {
1167         init(false, ValueBase::default_size, T());
1168     }
1169     Value(T v)
1170     {
1171         init(false, ValueBase::default_size, v);
1172     }
1173
1174     Value(bool from_link_list, size_t values)
1175     {
1176         init(from_link_list, values, T());
1177     }
1178
1179     Value(bool from_link_list, size_t values, T v)
1180     {
1181         init(from_link_list, values, v);
1182     }
1183
1184     Value(const Value&) = default;
1185     Value& operator=(const Value&) = default;
1186
1187     void init(bool from_link_list, size_t values, T v)
1188     {
1189         m_storage.init(values, v);
1190         ValueBase::m_from_link_list = from_link_list;
1191         ValueBase::m_values = values;
1192     }
1193
1194     void init(bool from_link_list, size_t values)
1195     {
1196         m_storage.init(values);
1197         ValueBase::m_from_link_list = from_link_list;
1198         ValueBase::m_values = values;
1199     }
1200
1201     void verify_column() const override
1202     {
1203     }
1204
1205     virtual std::string description() const override
1206     {
1207         if (ValueBase::m_from_link_list) {
1208             return util::serializer::print_value(util::to_string(ValueBase::m_values)
1209                                         + (ValueBase::m_values == 1 ? " value" : " values"));
1210         }
1211         if (m_storage.m_size > 0) {
1212             return util::serializer::print_value(m_storage[0]);
1213         }
1214         return "";
1215     }
1216
1217     void evaluate(size_t, ValueBase& destination) override
1218     {
1219         destination.import(*this);
1220     }
1221
1222
1223     template <class TOperator>
1224     REALM_FORCEINLINE void fun(const Value* left, const Value* right)
1225     {
1226         OperatorOptionalAdapter<TOperator> o;
1227
1228         if (!left->m_from_link_list && !right->m_from_link_list) {
1229             // Operate on values one-by-one (one value is one row; no links)
1230             size_t min = std::min(left->m_values, right->m_values);
1231             init(false, min);
1232
1233             for (size_t i = 0; i < min; i++) {
1234                 m_storage.set(i, o(left->m_storage.get(i), right->m_storage.get(i)));
1235             }
1236         }
1237         else if (left->m_from_link_list && right->m_from_link_list) {
1238             // FIXME: Many-to-many links not supported yet. Need to specify behaviour
1239             REALM_ASSERT_DEBUG(false);
1240         }
1241         else if (!left->m_from_link_list && right->m_from_link_list) {
1242             // Right values come from link. Left must come from single row.
1243             REALM_ASSERT_DEBUG(left->m_values > 0);
1244             init(true, right->m_values);
1245
1246             auto left_value = left->m_storage.get(0);
1247             for (size_t i = 0; i < right->m_values; i++) {
1248                 m_storage.set(i, o(left_value, right->m_storage.get(i)));
1249             }
1250         }
1251         else if (left->m_from_link_list && !right->m_from_link_list) {
1252             // Same as above, but with left values coming from links
1253             REALM_ASSERT_DEBUG(right->m_values > 0);
1254             init(true, left->m_values);
1255
1256             auto right_value = right->m_storage.get(0);
1257             for (size_t i = 0; i < left->m_values; i++) {
1258                 m_storage.set(i, o(left->m_storage.get(i), right_value));
1259             }
1260         }
1261     }
1262
1263     template <class TOperator>
1264     REALM_FORCEINLINE void fun(const Value* value)
1265     {
1266         init(value->m_from_link_list, value->m_values);
1267
1268         OperatorOptionalAdapter<TOperator> o;
1269         for (size_t i = 0; i < value->m_values; i++) {
1270             m_storage.set(i, o(value->m_storage.get(i)));
1271         }
1272     }
1273
1274
1275     // Below import and export methods are for type conversion between float, double, int64_t, etc.
1276     template <class D>
1277     typename std::enable_if<std::is_convertible<T, D>::value>::type REALM_FORCEINLINE
1278     export2(ValueBase& destination) const
1279     {
1280         Value<D>& d = static_cast<Value<D>&>(destination);
1281         d.init(ValueBase::m_from_link_list, ValueBase::m_values, D());
1282         for (size_t t = 0; t < ValueBase::m_values; t++) {
1283             if (m_storage.is_null(t))
1284                 d.m_storage.set_null(t);
1285             else {
1286                 d.m_storage.set(t, static_cast<D>(m_storage[t]));
1287             }
1288         }
1289     }
1290
1291     template <class D>
1292     typename std::enable_if<!std::is_convertible<T, D>::value>::type REALM_FORCEINLINE export2(ValueBase&) const
1293     {
1294         // export2 is instantiated for impossible conversions like T=StringData, D=int64_t. These are never
1295         // performed at runtime but would result in a compiler error if we did not provide this implementation.
1296         REALM_ASSERT_DEBUG(false);
1297     }
1298
1299     REALM_FORCEINLINE void export_Timestamp(ValueBase& destination) const override
1300     {
1301         export2<Timestamp>(destination);
1302     }
1303
1304     REALM_FORCEINLINE void export_bool(ValueBase& destination) const override
1305     {
1306         export2<bool>(destination);
1307     }
1308
1309     REALM_FORCEINLINE void export_int64_t(ValueBase& destination) const override
1310     {
1311         export2<int64_t>(destination);
1312     }
1313
1314     REALM_FORCEINLINE void export_float(ValueBase& destination) const override
1315     {
1316         export2<float>(destination);
1317     }
1318
1319     REALM_FORCEINLINE void export_int(ValueBase& destination) const override
1320     {
1321         export2<int>(destination);
1322     }
1323
1324     REALM_FORCEINLINE void export_double(ValueBase& destination) const override
1325     {
1326         export2<double>(destination);
1327     }
1328     REALM_FORCEINLINE void export_StringData(ValueBase& destination) const override
1329     {
1330         export2<StringData>(destination);
1331     }
1332     REALM_FORCEINLINE void export_BinaryData(ValueBase& destination) const override
1333     {
1334         export2<BinaryData>(destination);
1335     }
1336     REALM_FORCEINLINE void export_RowIndex(ValueBase& destination) const override
1337     {
1338         export2<RowIndex>(destination);
1339     }
1340     REALM_FORCEINLINE void export_null(ValueBase& destination) const override
1341     {
1342         Value<null>& d = static_cast<Value<null>&>(destination);
1343         d.init(m_from_link_list, m_values);
1344     }
1345
1346     REALM_FORCEINLINE void import(const ValueBase& source) override
1347     {
1348         if (std::is_same<T, int>::value)
1349             source.export_int(*this);
1350         else if (std::is_same<T, Timestamp>::value)
1351             source.export_Timestamp(*this);
1352         else if (std::is_same<T, bool>::value)
1353             source.export_bool(*this);
1354         else if (std::is_same<T, float>::value)
1355             source.export_float(*this);
1356         else if (std::is_same<T, double>::value)
1357             source.export_double(*this);
1358         else if (std::is_same<T, int64_t>::value || std::is_same<T, bool>::value ||
1359                  std::is_same<T, OldDateTime>::value)
1360             source.export_int64_t(*this);
1361         else if (std::is_same<T, StringData>::value)
1362             source.export_StringData(*this);
1363         else if (std::is_same<T, BinaryData>::value)
1364             source.export_BinaryData(*this);
1365         else if (std::is_same<T, RowIndex>::value)
1366             source.export_RowIndex(*this);
1367         else if (std::is_same<T, null>::value)
1368             source.export_null(*this);
1369         else
1370             REALM_ASSERT_DEBUG(false);
1371     }
1372
1373     // Given a TCond (==, !=, >, <, >=, <=) and two Value<T>, return index of first match
1374     template <class TCond>
1375     REALM_FORCEINLINE static size_t compare(Value<T>* left, Value<T>* right)
1376     {
1377         TCond c;
1378
1379         if (!left->m_from_link_list && !right->m_from_link_list) {
1380             // Compare values one-by-one (one value is one row; no link lists)
1381             size_t min = minimum(left->ValueBase::m_values, right->ValueBase::m_values);
1382             for (size_t m = 0; m < min; m++) {
1383
1384                 if (c(left->m_storage[m], right->m_storage[m], left->m_storage.is_null(m),
1385                       right->m_storage.is_null(m)))
1386                     return m;
1387             }
1388         }
1389         else if (left->m_from_link_list && right->m_from_link_list) {
1390             // FIXME: Many-to-many links not supported yet. Need to specify behaviour
1391             REALM_ASSERT_DEBUG(false);
1392         }
1393         else if (!left->m_from_link_list && right->m_from_link_list) {
1394             // Right values come from link list. Left must come from single row. Semantics: Match if at least 1
1395             // linked-to-value fulfills the condition
1396             REALM_ASSERT_DEBUG(left->m_values > 0);
1397             for (size_t r = 0; r < right->m_values; r++) {
1398                 if (c(left->m_storage[0], right->m_storage[r], left->m_storage.is_null(0),
1399                       right->m_storage.is_null(r)))
1400                     return 0;
1401             }
1402         }
1403         else if (left->m_from_link_list && !right->m_from_link_list) {
1404             // Same as above, but with left values coming from link list.
1405             REALM_ASSERT_DEBUG(right->m_values > 0);
1406             for (size_t l = 0; l < left->m_values; l++) {
1407                 if (c(left->m_storage[l], right->m_storage[0], left->m_storage.is_null(l),
1408                       right->m_storage.is_null(0)))
1409                     return 0;
1410             }
1411         }
1412
1413         return not_found; // no match
1414     }
1415
1416     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches*) const override
1417     {
1418         return make_subexpr<Value<T>>(*this);
1419     }
1420
1421     NullableVector<T> m_storage;
1422 };
1423
1424 class ConstantStringValue : public Value<StringData> {
1425 public:
1426     ConstantStringValue(const StringData& string)
1427         : Value()
1428         , m_string(string.is_null() ? util::none : util::make_optional(std::string(string)))
1429     {
1430         init(false, ValueBase::default_size, m_string);
1431     }
1432
1433     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches*) const override
1434     {
1435         return std::unique_ptr<Subexpr>(new ConstantStringValue(*this));
1436     }
1437
1438 private:
1439     ConstantStringValue(const ConstantStringValue& other)
1440         : Value()
1441         , m_string(other.m_string)
1442     {
1443         init(other.m_from_link_list, other.m_values, m_string);
1444     }
1445
1446     util::Optional<std::string> m_string;
1447 };
1448
1449 // All overloads where left-hand-side is L:
1450 //
1451 // left-hand-side       operator                              right-hand-side
1452 // L                    +, -, *, /, <, >, ==, !=, <=, >=      Subexpr2<R>
1453 //
1454 // For L = R = {int, int64_t, float, double, Timestamp}:
1455 // Compare numeric values
1456 template <class R>
1457 Query operator>(double left, const Subexpr2<R>& right)
1458 {
1459     return create<Greater>(left, right);
1460 }
1461 template <class R>
1462 Query operator>(float left, const Subexpr2<R>& right)
1463 {
1464     return create<Greater>(left, right);
1465 }
1466 template <class R>
1467 Query operator>(int left, const Subexpr2<R>& right)
1468 {
1469     return create<Greater>(left, right);
1470 }
1471 template <class R>
1472 Query operator>(int64_t left, const Subexpr2<R>& right)
1473 {
1474     return create<Greater>(left, right);
1475 }
1476 template <class R>
1477 Query operator>(Timestamp left, const Subexpr2<R>& right)
1478 {
1479     return create<Greater>(left, right);
1480 }
1481
1482 template <class R>
1483 Query operator<(double left, const Subexpr2<R>& right)
1484 {
1485     return create<Less>(left, right);
1486 }
1487 template <class R>
1488 Query operator<(float left, const Subexpr2<R>& right)
1489 {
1490     return create<Less>(left, right);
1491 }
1492 template <class R>
1493 Query operator<(int left, const Subexpr2<R>& right)
1494 {
1495     return create<Less>(left, right);
1496 }
1497 template <class R>
1498 Query operator<(int64_t left, const Subexpr2<R>& right)
1499 {
1500     return create<Less>(left, right);
1501 }
1502 template <class R>
1503 Query operator<(Timestamp left, const Subexpr2<R>& right)
1504 {
1505     return create<Less>(left, right);
1506 }
1507 template <class R>
1508 Query operator==(double left, const Subexpr2<R>& right)
1509 {
1510     return create<Equal>(left, right);
1511 }
1512 template <class R>
1513 Query operator==(float left, const Subexpr2<R>& right)
1514 {
1515     return create<Equal>(left, right);
1516 }
1517 template <class R>
1518 Query operator==(int left, const Subexpr2<R>& right)
1519 {
1520     return create<Equal>(left, right);
1521 }
1522 template <class R>
1523 Query operator==(int64_t left, const Subexpr2<R>& right)
1524 {
1525     return create<Equal>(left, right);
1526 }
1527 template <class R>
1528 Query operator==(Timestamp left, const Subexpr2<R>& right)
1529 {
1530     return create<Equal>(left, right);
1531 }
1532 template <class R>
1533 Query operator>=(double left, const Subexpr2<R>& right)
1534 {
1535     return create<GreaterEqual>(left, right);
1536 }
1537 template <class R>
1538 Query operator>=(float left, const Subexpr2<R>& right)
1539 {
1540     return create<GreaterEqual>(left, right);
1541 }
1542 template <class R>
1543 Query operator>=(int left, const Subexpr2<R>& right)
1544 {
1545     return create<GreaterEqual>(left, right);
1546 }
1547 template <class R>
1548 Query operator>=(int64_t left, const Subexpr2<R>& right)
1549 {
1550     return create<GreaterEqual>(left, right);
1551 }
1552 template <class R>
1553 Query operator>=(Timestamp left, const Subexpr2<R>& right)
1554 {
1555     return create<GreaterEqual>(left, right);
1556 }
1557 template <class R>
1558 Query operator<=(double left, const Subexpr2<R>& right)
1559 {
1560     return create<LessEqual>(left, right);
1561 }
1562 template <class R>
1563 Query operator<=(float left, const Subexpr2<R>& right)
1564 {
1565     return create<LessEqual>(left, right);
1566 }
1567 template <class R>
1568 Query operator<=(int left, const Subexpr2<R>& right)
1569 {
1570     return create<LessEqual>(left, right);
1571 }
1572 template <class R>
1573 Query operator<=(int64_t left, const Subexpr2<R>& right)
1574 {
1575     return create<LessEqual>(left, right);
1576 }
1577 template <class R>
1578 Query operator<=(Timestamp left, const Subexpr2<R>& right)
1579 {
1580     return create<LessEqual>(left, right);
1581 }
1582 template <class R>
1583 Query operator!=(double left, const Subexpr2<R>& right)
1584 {
1585     return create<NotEqual>(left, right);
1586 }
1587 template <class R>
1588 Query operator!=(float left, const Subexpr2<R>& right)
1589 {
1590     return create<NotEqual>(left, right);
1591 }
1592 template <class R>
1593 Query operator!=(int left, const Subexpr2<R>& right)
1594 {
1595     return create<NotEqual>(left, right);
1596 }
1597 template <class R>
1598 Query operator!=(int64_t left, const Subexpr2<R>& right)
1599 {
1600     return create<NotEqual>(left, right);
1601 }
1602 template <class R>
1603 Query operator!=(Timestamp left, const Subexpr2<R>& right)
1604 {
1605     return create<NotEqual>(left, right);
1606 }
1607
1608 // Arithmetic
1609 template <class R>
1610 Operator<Plus<typename Common<R, double>::type>> operator+(double left, const Subexpr2<R>& right)
1611 {
1612     return {make_subexpr<Value<double>>(left), right.clone()};
1613 }
1614 template <class R>
1615 Operator<Plus<typename Common<R, float>::type>> operator+(float left, const Subexpr2<R>& right)
1616 {
1617     return {make_subexpr<Value<float>>(left), right.clone()};
1618 }
1619 template <class R>
1620 Operator<Plus<typename Common<R, int>::type>> operator+(int left, const Subexpr2<R>& right)
1621 {
1622     return {make_subexpr<Value<int>>(left), right.clone()};
1623 }
1624 template <class R>
1625 Operator<Plus<typename Common<R, int64_t>::type>> operator+(int64_t left, const Subexpr2<R>& right)
1626 {
1627     return {make_subexpr<Value<int64_t>>(left), right.clone()};
1628 }
1629 template <class R>
1630 Operator<Minus<typename Common<R, double>::type>> operator-(double left, const Subexpr2<R>& right)
1631 {
1632     return {make_subexpr<Value<double>>(left), right.clone()};
1633 }
1634 template <class R>
1635 Operator<Minus<typename Common<R, float>::type>> operator-(float left, const Subexpr2<R>& right)
1636 {
1637     return {make_subexpr<Value<float>>(left), right.clone()};
1638 }
1639 template <class R>
1640 Operator<Minus<typename Common<R, int>::type>> operator-(int left, const Subexpr2<R>& right)
1641 {
1642     return {make_subexpr<Value<int>>(left), right.clone()};
1643 }
1644 template <class R>
1645 Operator<Minus<typename Common<R, int64_t>::type>> operator-(int64_t left, const Subexpr2<R>& right)
1646 {
1647     return {make_subexpr<Value<int64_t>>(left), right.clone()};
1648 }
1649 template <class R>
1650 Operator<Mul<typename Common<R, double>::type>> operator*(double left, const Subexpr2<R>& right)
1651 {
1652     return {make_subexpr<Value<double>>(left), right.clone()};
1653 }
1654 template <class R>
1655 Operator<Mul<typename Common<R, float>::type>> operator*(float left, const Subexpr2<R>& right)
1656 {
1657     return {make_subexpr<Value<float>>(left), right.clone()};
1658 }
1659 template <class R>
1660 Operator<Mul<typename Common<R, int>::type>> operator*(int left, const Subexpr2<R>& right)
1661 {
1662     return {make_subexpr<Value<int>>(left), right.clone()};
1663 }
1664 template <class R>
1665 Operator<Mul<typename Common<R, int64_t>::type>> operator*(int64_t left, const Subexpr2<R>& right)
1666 {
1667     return {make_subexpr<Value<int64_t>>(left), right.clone()};
1668 }
1669 template <class R>
1670 Operator<Div<typename Common<R, double>::type>> operator/(double left, const Subexpr2<R>& right)
1671 {
1672     return {make_subexpr<Value<double>>(left), right.clone()};
1673 }
1674 template <class R>
1675 Operator<Div<typename Common<R, float>::type>> operator/(float left, const Subexpr2<R>& right)
1676 {
1677     return {make_subexpr<Value<float>>(left), right.clone()};
1678 }
1679 template <class R>
1680 Operator<Div<typename Common<R, int>::type>> operator/(int left, const Subexpr2<R>& right)
1681 {
1682     return {make_subexpr<Value<int>>(left), right.clone()};
1683 }
1684 template <class R>
1685 Operator<Div<typename Common<R, int64_t>::type>> operator/(int64_t left, const Subexpr2<R>& right)
1686 {
1687     return {make_subexpr<Value<int64_t>>(left), right.clone()};
1688 }
1689
1690 // Unary operators
1691 template <class T>
1692 UnaryOperator<Pow<T>> power(const Subexpr2<T>& left)
1693 {
1694     return {left.clone()};
1695 }
1696
1697 // Classes used for LinkMap (see below).
1698 struct LinkMapFunction {
1699     // Your consume() method is given row index of the linked-to table as argument, and you must return whether or
1700     // not you want the LinkMapFunction to exit (return false) or continue (return true) harvesting the link tree
1701     // for the current main table row index (it will be a link tree if you have multiple type_LinkList columns
1702     // in a link()->link() query.
1703     virtual bool consume(size_t row_index) = 0;
1704 };
1705
1706 struct FindNullLinks : public LinkMapFunction {
1707     bool consume(size_t row_index) override
1708     {
1709         static_cast<void>(row_index);
1710         m_has_link = true;
1711         return false; // we've found a row index, so this can't be a null-link, so exit link harvesting
1712     }
1713
1714     bool m_has_link = false;
1715 };
1716
1717 struct MakeLinkVector : public LinkMapFunction {
1718     MakeLinkVector(std::vector<size_t>& result)
1719         : m_links(result)
1720     {
1721     }
1722
1723     bool consume(size_t row_index) override
1724     {
1725         m_links.push_back(row_index);
1726         return true; // continue evaluation
1727     }
1728     std::vector<size_t>& m_links;
1729 };
1730
1731 struct CountLinks : public LinkMapFunction {
1732     bool consume(size_t) override
1733     {
1734         m_link_count++;
1735         return true;
1736     }
1737
1738     size_t result() const
1739     {
1740         return m_link_count;
1741     }
1742
1743     size_t m_link_count = 0;
1744 };
1745
1746
1747 /*
1748 The LinkMap and LinkMapFunction classes are used for query conditions on links themselves (contrary to conditions on
1749 the value payload they point at).
1750
1751 MapLink::map_links() takes a row index of the link column as argument and follows any link chain stated in the query
1752 (through the link()->link() methods) until the final payload table is reached, and then applies LinkMapFunction on
1753 the linked-to row index(es).
1754
1755 If all link columns are type_Link, then LinkMapFunction is only invoked for a single row index. If one or more
1756 columns are type_LinkList, then it may result in multiple row indexes.
1757
1758 The reason we use this map pattern is that we can exit the link-tree-traversal as early as possible, e.g. when we've
1759 found the first link that points to row '5'. Other solutions could be a std::vector<size_t> harvest_all_links(), or an
1760 iterator pattern. First solution can't exit, second solution requires internal state.
1761 */
1762 class LinkMap {
1763 public:
1764     LinkMap() = default;
1765     LinkMap(const Table* table, std::vector<size_t> columns)
1766         : m_link_column_indexes(std::move(columns))
1767     {
1768         set_base_table(table);
1769     }
1770
1771     LinkMap(LinkMap const& other, QueryNodeHandoverPatches* patches)
1772         : LinkMap(other)
1773     {
1774         if (!patches)
1775             return;
1776
1777         m_link_column_indexes.clear();
1778         const Table* table = base_table();
1779         m_tables.clear();
1780         for (auto column : m_link_columns) {
1781             m_link_column_indexes.push_back(column->get_column_index());
1782             if (table->get_real_column_type(m_link_column_indexes.back()) == col_type_BackLink)
1783                 table = &static_cast<const BacklinkColumn*>(column)->get_origin_table();
1784             else
1785                 table = &static_cast<const LinkColumnBase*>(column)->get_target_table();
1786         }
1787     }
1788
1789     void set_base_table(const Table* table)
1790     {
1791         if (table == base_table())
1792             return;
1793
1794         m_tables.clear();
1795         m_tables.push_back(table);
1796         m_link_columns.clear();
1797         m_link_types.clear();
1798         m_only_unary_links = true;
1799
1800         for (size_t link_column_index : m_link_column_indexes) {
1801             // Link column can be either LinkList or single Link
1802             const Table* t = m_tables.back();
1803             ColumnType type = t->get_real_column_type(link_column_index);
1804             REALM_ASSERT(Table::is_link_type(type) || type == col_type_BackLink);
1805             m_link_types.push_back(type);
1806
1807             if (type == col_type_LinkList) {
1808                 const LinkListColumn& cll = t->get_column_link_list(link_column_index);
1809                 m_link_columns.push_back(&cll);
1810                 m_only_unary_links = false;
1811                 m_tables.push_back(&cll.get_target_table());
1812             }
1813             else if (type == col_type_Link) {
1814                 const LinkColumn& cl = t->get_column_link(link_column_index);
1815                 m_link_columns.push_back(&cl);
1816                 m_tables.push_back(&cl.get_target_table());
1817             }
1818             else if (type == col_type_BackLink) {
1819                 const BacklinkColumn& bl = t->get_column_backlink(link_column_index);
1820                 m_link_columns.push_back(&bl);
1821                 m_only_unary_links = false;
1822                 m_tables.push_back(&bl.get_origin_table());
1823             }
1824         }
1825     }
1826
1827     void verify_columns() const
1828     {
1829         for (size_t i = 0; i < m_link_column_indexes.size(); i++) {
1830             m_tables[i]->verify_column(m_link_column_indexes[i], m_link_columns[i]);
1831         }
1832     }
1833
1834     virtual std::string description() const
1835     {
1836         std::string s;
1837         for (size_t i = 0; i < m_link_column_indexes.size(); ++i) {
1838             if (i < m_tables.size() && m_tables[i]) {
1839                 if (m_link_types[i] == col_type_BackLink) {
1840                     s += "backlink";
1841                 } else if (m_link_column_indexes[i] < m_tables[i]->get_column_count()) {
1842                     s += std::string(m_tables[i]->get_column_name(m_link_column_indexes[i]));
1843                 }
1844                 if (i != m_link_column_indexes.size() - 1) {
1845                     s += util::serializer::value_separator;
1846                 }
1847             }
1848         }
1849         return s;
1850     }
1851
1852     std::vector<size_t> get_links(size_t index)
1853     {
1854         std::vector<size_t> res;
1855         get_links(index, res);
1856         return res;
1857     }
1858
1859     size_t count_links(size_t row)
1860     {
1861         CountLinks counter;
1862         map_links(row, counter);
1863         return counter.result();
1864     }
1865
1866     void map_links(size_t row, LinkMapFunction& lm)
1867     {
1868         map_links(0, row, lm);
1869     }
1870
1871     bool only_unary_links() const
1872     {
1873         return m_only_unary_links;
1874     }
1875
1876     const Table* base_table() const
1877     {
1878         return m_tables.empty() ? nullptr : m_tables[0];
1879     }
1880
1881     const Table* target_table() const
1882     {
1883         REALM_ASSERT(!m_tables.empty());
1884         return m_tables.back();
1885     }
1886
1887     std::vector<const ColumnBase*> m_link_columns;
1888
1889 private:
1890     void map_links(size_t column, size_t row, LinkMapFunction& lm)
1891     {
1892         bool last = (column + 1 == m_link_columns.size());
1893         ColumnType type = m_link_types[column];
1894         if (type == col_type_Link) {
1895             const LinkColumn& cl = *static_cast<const LinkColumn*>(m_link_columns[column]);
1896             size_t r = to_size_t(cl.get(row));
1897             if (r == 0)
1898                 return;
1899             r--; // LinkColumn stores link to row N as N + 1
1900             if (last) {
1901                 bool continue2 = lm.consume(r);
1902                 if (!continue2)
1903                     return;
1904             }
1905             else
1906                 map_links(column + 1, r, lm);
1907         }
1908         else if (type == col_type_LinkList) {
1909             const LinkListColumn& cll = *static_cast<const LinkListColumn*>(m_link_columns[column]);
1910             ConstLinkViewRef lvr = cll.get(row);
1911             for (size_t t = 0; t < lvr->size(); t++) {
1912                 size_t r = lvr->get(t).get_index();
1913                 if (last) {
1914                     bool continue2 = lm.consume(r);
1915                     if (!continue2)
1916                         return;
1917                 }
1918                 else
1919                     map_links(column + 1, r, lm);
1920             }
1921         }
1922         else if (type == col_type_BackLink) {
1923             const BacklinkColumn& bl = *static_cast<const BacklinkColumn*>(m_link_columns[column]);
1924             size_t count = bl.get_backlink_count(row);
1925             for (size_t i = 0; i < count; ++i) {
1926                 size_t r = bl.get_backlink(row, i);
1927                 if (last) {
1928                     bool continue2 = lm.consume(r);
1929                     if (!continue2)
1930                         return;
1931                 }
1932                 else
1933                     map_links(column + 1, r, lm);
1934             }
1935         }
1936     }
1937
1938
1939     void get_links(size_t row, std::vector<size_t>& result)
1940     {
1941         MakeLinkVector mlv = MakeLinkVector(result);
1942         map_links(row, mlv);
1943     }
1944
1945     std::vector<size_t> m_link_column_indexes;
1946     std::vector<ColumnType> m_link_types;
1947     std::vector<const Table*> m_tables;
1948     bool m_only_unary_links = true;
1949
1950     template <class>
1951     friend Query compare(const Subexpr2<Link>&, const ConstRow&);
1952 };
1953
1954 template <class T, class S, class I>
1955 Query string_compare(const Subexpr2<StringData>& left, T right, bool case_insensitive);
1956 template <class S, class I>
1957 Query string_compare(const Subexpr2<StringData>& left, const Subexpr2<StringData>& right, bool case_insensitive);
1958
1959 template <class T>
1960 Value<T> make_value_for_link(bool only_unary_links, size_t size)
1961 {
1962     Value<T> value;
1963     if (only_unary_links) {
1964         REALM_ASSERT(size <= 1);
1965         value.init(false, 1);
1966         value.m_storage.set_null(0);
1967     }
1968     else {
1969         value.init(true, size);
1970     }
1971     return value;
1972 }
1973
1974
1975 // If we add a new Realm type T and quickly want Query support for it, then simply inherit from it like
1976 // `template <> class Columns<T> : public SimpleQuerySupport<T>` and you're done. Any operators of the set
1977 // { ==, >=, <=, !=, >, < } that are supported by T will be supported by the "query expression syntax"
1978 // automatically. NOTE: This method of Query support will be slow because it goes through Table::get<T>.
1979 // To get faster Query support, either add SequentialGetter support (faster) or create a query_engine.hpp
1980 // node for it (super fast).
1981
1982 template <class T>
1983 class SimpleQuerySupport : public Subexpr2<T> {
1984 public:
1985     SimpleQuerySupport(size_t column, const Table* table, std::vector<size_t> links = {})
1986         : m_column_ndx(column)
1987         , m_link_map(table, std::move(links))
1988     {
1989         m_column = &m_link_map.target_table()->get_column_base(m_column_ndx);
1990     }
1991
1992     bool is_nullable() const noexcept
1993     {
1994         return m_link_map.base_table()->is_nullable(m_column->get_column_index());
1995     }
1996
1997     const Table* get_base_table() const override
1998     {
1999         return m_link_map.base_table();
2000     }
2001
2002     void set_base_table(const Table* table) override
2003     {
2004         if (table != get_base_table()) {
2005             m_link_map.set_base_table(table);
2006             m_column = &m_link_map.target_table()->get_column_base(m_column_ndx);
2007         }
2008     }
2009
2010     void verify_column() const override
2011     {
2012         // verify links
2013         m_link_map.verify_columns();
2014         // verify target table
2015         const Table* target_table = m_link_map.target_table();
2016         if (target_table && m_column_ndx != npos) {
2017             target_table->verify_column(m_column_ndx, m_column);
2018         }
2019     }
2020
2021     void evaluate(size_t index, ValueBase& destination) override
2022     {
2023         Value<T>& d = static_cast<Value<T>&>(destination);
2024         size_t col = column_ndx();
2025
2026         if (links_exist()) {
2027             std::vector<size_t> links = m_link_map.get_links(index);
2028             Value<T> v = make_value_for_link<T>(m_link_map.only_unary_links(), links.size());
2029
2030             for (size_t t = 0; t < links.size(); t++) {
2031                 size_t link_to = links[t];
2032                 v.m_storage.set(t, m_link_map.target_table()->template get<T>(col, link_to));
2033             }
2034             destination.import(v);
2035         }
2036         else {
2037             // Not a link column
2038             const Table* target_table = m_link_map.target_table();
2039             for (size_t t = 0; t < destination.m_values && index + t < target_table->size(); t++) {
2040                 d.m_storage.set(t, target_table->get<T>(col, index + t));
2041             }
2042         }
2043     }
2044
2045     bool links_exist() const
2046     {
2047         return m_link_map.m_link_columns.size() > 0;
2048     }
2049
2050     virtual std::string description() const override
2051     {
2052         std::string desc;
2053         if (links_exist()) {
2054             desc = m_link_map.description() + util::serializer::value_separator;
2055         }
2056         const Table* target_table = m_link_map.target_table();
2057         if (target_table && target_table->is_attached()) {
2058             desc += std::string(target_table->get_column_name(m_column_ndx));
2059         }
2060         return desc;
2061     }
2062
2063     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches = nullptr) const override
2064     {
2065         return make_subexpr<Columns<T>>(static_cast<const Columns<T>&>(*this), patches);
2066     }
2067
2068     SimpleQuerySupport(SimpleQuerySupport const& other, QueryNodeHandoverPatches* patches)
2069         : Subexpr2<T>(other)
2070         , m_column_ndx(other.m_column_ndx)
2071         , m_column(other.m_column)
2072         , m_link_map(other.m_link_map, patches)
2073     {
2074         if (patches && m_column) {
2075             m_column_ndx = column_ndx();
2076             m_column = nullptr;
2077         }
2078     }
2079
2080     size_t column_ndx() const
2081     {
2082         return m_column->get_column_index();
2083     }
2084
2085     SizeOperator<Size<T>> size()
2086     {
2087         return SizeOperator<Size<T>>(this->clone(nullptr));
2088     }
2089
2090 private:
2091     // Column index of payload column of m_table
2092     mutable size_t m_column_ndx;
2093     const ColumnBase* m_column;
2094     LinkMap m_link_map;
2095 };
2096
2097
2098 template <>
2099 class Columns<Timestamp> : public SimpleQuerySupport<Timestamp> {
2100     using SimpleQuerySupport::SimpleQuerySupport;
2101 };
2102
2103 template <>
2104 class Columns<BinaryData> : public SimpleQuerySupport<BinaryData> {
2105     using SimpleQuerySupport::SimpleQuerySupport;
2106 };
2107
2108 template <>
2109 class Columns<StringData> : public SimpleQuerySupport<StringData> {
2110 public:
2111     Columns(size_t column, const Table* table, std::vector<size_t> links = {})
2112         : SimpleQuerySupport(column, table, links)
2113     {
2114     }
2115
2116     Columns(Columns const& other, QueryNodeHandoverPatches* patches = nullptr)
2117         : SimpleQuerySupport(other, patches)
2118     {
2119     }
2120
2121     Columns(Columns&& other)
2122         : SimpleQuerySupport(other)
2123     {
2124     }
2125 };
2126
2127 template <class T, class S, class I>
2128 Query string_compare(const Subexpr2<StringData>& left, T right, bool case_sensitive)
2129 {
2130     StringData sd(right);
2131     if (case_sensitive)
2132         return create<S>(sd, left);
2133     else
2134         return create<I>(sd, left);
2135 }
2136
2137 template <class S, class I>
2138 Query string_compare(const Subexpr2<StringData>& left, const Subexpr2<StringData>& right, bool case_sensitive)
2139 {
2140     if (case_sensitive)
2141         return make_expression<Compare<S, StringData>>(right.clone(), left.clone());
2142     else
2143         return make_expression<Compare<I, StringData>>(right.clone(), left.clone());
2144 }
2145
2146 // Columns<String> == Columns<String>
2147 inline Query operator==(const Columns<StringData>& left, const Columns<StringData>& right)
2148 {
2149     return string_compare<Equal, EqualIns>(left, right, true);
2150 }
2151
2152 // Columns<String> != Columns<String>
2153 inline Query operator!=(const Columns<StringData>& left, const Columns<StringData>& right)
2154 {
2155     return string_compare<NotEqual, NotEqualIns>(left, right, true);
2156 }
2157
2158 // String == Columns<String>
2159 template <class T>
2160 Query operator==(T left, const Columns<StringData>& right)
2161 {
2162     return operator==(right, left);
2163 }
2164
2165 // String != Columns<String>
2166 template <class T>
2167 Query operator!=(T left, const Columns<StringData>& right)
2168 {
2169     return operator!=(right, left);
2170 }
2171
2172 // Columns<String> == String
2173 template <class T>
2174 Query operator==(const Columns<StringData>& left, T right)
2175 {
2176     return string_compare<T, Equal, EqualIns>(left, right, true);
2177 }
2178
2179 // Columns<String> != String
2180 template <class T>
2181 Query operator!=(const Columns<StringData>& left, T right)
2182 {
2183     return string_compare<T, NotEqual, NotEqualIns>(left, right, true);
2184 }
2185
2186
2187 inline Query operator==(const Columns<BinaryData>& left, BinaryData right)
2188 {
2189     return create<Equal>(right, left);
2190 }
2191
2192 inline Query operator==(BinaryData left, const Columns<BinaryData>& right)
2193 {
2194     return create<Equal>(left, right);
2195 }
2196
2197 inline Query operator!=(const Columns<BinaryData>& left, BinaryData right)
2198 {
2199     return create<NotEqual>(right, left);
2200 }
2201
2202 inline Query operator!=(BinaryData left, const Columns<BinaryData>& right)
2203 {
2204     return create<NotEqual>(left, right);
2205 }
2206
2207
2208 // This class is intended to perform queries on the *pointers* of links, contrary to performing queries on *payload*
2209 // in linked-to tables. Queries can be "find first link that points at row X" or "find first null-link". Currently
2210 // only "find first null link" and "find first non-null link" is supported. More will be added later. When we add
2211 // more, I propose to remove the <bool has_links> template argument from this class and instead template it by
2212 // a criteria-class (like the FindNullLinks class below in find_first()) in some generalized fashion.
2213 template <bool has_links>
2214 class UnaryLinkCompare : public Expression {
2215 public:
2216     UnaryLinkCompare(LinkMap lm)
2217         : m_link_map(std::move(lm))
2218     {
2219     }
2220
2221     void set_base_table(const Table* table) override
2222     {
2223         m_link_map.set_base_table(table);
2224     }
2225
2226     void verify_column() const override
2227     {
2228         m_link_map.verify_columns();
2229     }
2230
2231     // Return main table of query (table on which table->where()... is invoked). Note that this is not the same as
2232     // any linked-to payload tables
2233     const Table* get_base_table() const override
2234     {
2235         return m_link_map.base_table();
2236     }
2237
2238     size_t find_first(size_t start, size_t end) const override
2239     {
2240         for (; start < end;) {
2241             FindNullLinks fnl;
2242             m_link_map.map_links(start, fnl);
2243             if (fnl.m_has_link == has_links)
2244                 return start;
2245
2246             start++;
2247         }
2248
2249         return not_found;
2250     }
2251
2252     virtual std::string description() const override
2253     {
2254         return m_link_map.description() + (has_links ? " != NULL" : " == NULL");
2255     }
2256
2257     std::unique_ptr<Expression> clone(QueryNodeHandoverPatches* patches) const override
2258     {
2259         return std::unique_ptr<Expression>(new UnaryLinkCompare(*this, patches));
2260     }
2261
2262 private:
2263     UnaryLinkCompare(const UnaryLinkCompare& other, QueryNodeHandoverPatches* patches = nullptr)
2264         : Expression(other)
2265         , m_link_map(other.m_link_map, patches)
2266     {
2267     }
2268
2269     mutable LinkMap m_link_map;
2270 };
2271
2272 class LinkCount : public Subexpr2<Int> {
2273 public:
2274     LinkCount(LinkMap link_map)
2275         : m_link_map(std::move(link_map))
2276     {
2277     }
2278     LinkCount(LinkCount const& other, QueryNodeHandoverPatches* patches)
2279         : Subexpr2<Int>(other)
2280         , m_link_map(other.m_link_map, patches)
2281     {
2282     }
2283
2284     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2285     {
2286         return make_subexpr<LinkCount>(*this, patches);
2287     }
2288
2289     const Table* get_base_table() const override
2290     {
2291         return m_link_map.base_table();
2292     }
2293
2294     void set_base_table(const Table* table) override
2295     {
2296         m_link_map.set_base_table(table);
2297     }
2298
2299     void verify_column() const override
2300     {
2301         m_link_map.verify_columns();
2302     }
2303
2304     void evaluate(size_t index, ValueBase& destination) override
2305     {
2306         size_t count = m_link_map.count_links(index);
2307         destination.import(Value<Int>(false, 1, count));
2308     }
2309
2310     virtual std::string description() const override
2311     {
2312         return m_link_map.description() + util::serializer::value_separator + "@count";
2313     }
2314
2315 private:
2316     LinkMap m_link_map;
2317 };
2318
2319 template <class oper, class TExpr>
2320 class SizeOperator : public Subexpr2<Int> {
2321 public:
2322     SizeOperator(std::unique_ptr<TExpr> left)
2323         : m_expr(std::move(left))
2324     {
2325     }
2326
2327     // See comment in base class
2328     void set_base_table(const Table* table) override
2329     {
2330         m_expr->set_base_table(table);
2331     }
2332
2333     void verify_column() const override
2334     {
2335         m_expr->verify_column();
2336     }
2337
2338     // Recursively fetch tables of columns in expression tree. Used when user first builds a stand-alone expression
2339     // and binds it to a Query at a later time
2340     const Table* get_base_table() const override
2341     {
2342         return m_expr->get_base_table();
2343     }
2344
2345     // destination = operator(left)
2346     void evaluate(size_t index, ValueBase& destination) override
2347     {
2348         REALM_ASSERT_DEBUG(dynamic_cast<Value<Int>*>(&destination) != nullptr);
2349         Value<Int>* d = static_cast<Value<Int>*>(&destination);
2350         REALM_ASSERT(d);
2351
2352         Value<T> v;
2353         m_expr->evaluate(index, v);
2354
2355         size_t sz = v.m_values;
2356         d->init(v.m_from_link_list, sz);
2357
2358         for (size_t i = 0; i < sz; i++) {
2359             auto elem = v.m_storage.get(i);
2360             if (!elem) {
2361                 d->m_storage.set_null(i);
2362             }
2363             else {
2364                 d->m_storage.set(i, oper()(*elem));
2365             }
2366         }
2367     }
2368
2369     std::string description() const override
2370     {
2371         if (m_expr) {
2372             return m_expr->description() + util::serializer::value_separator + "@size";
2373         }
2374         return "@size";
2375     }
2376
2377     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2378     {
2379         return std::unique_ptr<Subexpr>(new SizeOperator(*this, patches));
2380     }
2381
2382     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
2383     {
2384         m_expr->apply_handover_patch(patches, group);
2385     }
2386
2387 private:
2388     SizeOperator(const SizeOperator& other, QueryNodeHandoverPatches* patches)
2389         : m_expr(other.m_expr->clone(patches))
2390     {
2391     }
2392
2393     typedef typename oper::type T;
2394     std::unique_ptr<TExpr> m_expr;
2395 };
2396
2397 struct ConstantRowValueHandoverPatch : public QueryNodeHandoverPatch {
2398     std::unique_ptr<RowBaseHandoverPatch> row_patch;
2399 };
2400
2401 class ConstantRowValue : public Subexpr2<Link> {
2402 public:
2403     ConstantRowValue(const ConstRow& row)
2404         : m_row(row)
2405     {
2406     }
2407
2408     void set_base_table(const Table*) override
2409     {
2410     }
2411
2412     void verify_column() const override
2413     {
2414     }
2415
2416     const Table* get_base_table() const override
2417     {
2418         return nullptr;
2419     }
2420
2421     void evaluate(size_t, ValueBase& destination) override
2422     {
2423         if (m_row.is_attached()) {
2424             Value<RowIndex> v(RowIndex(m_row.get_index()));
2425             destination.import(v);
2426         }
2427         else {
2428             Value<RowIndex> v(RowIndex::Detached);
2429             destination.import(v);
2430         }
2431     }
2432
2433     virtual std::string description() const override
2434     {
2435         if (!m_row.is_attached()) {
2436             return util::serializer::print_value("detached object");
2437         }
2438         return util::serializer::print_value(m_row.get_index());
2439     }
2440
2441     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2442     {
2443         return std::unique_ptr<Subexpr>(new ConstantRowValue(*this, patches));
2444     }
2445
2446     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
2447     {
2448         REALM_ASSERT(patches.size());
2449         std::unique_ptr<QueryNodeHandoverPatch> abstract_patch = std::move(patches.back());
2450         patches.pop_back();
2451
2452         auto patch = dynamic_cast<ConstantRowValueHandoverPatch*>(abstract_patch.get());
2453         REALM_ASSERT(patch);
2454
2455         m_row.apply_and_consume_patch(patch->row_patch, group);
2456     }
2457
2458 private:
2459     ConstantRowValue(const ConstantRowValue& source, QueryNodeHandoverPatches* patches)
2460         : m_row(patches ? ConstRow() : source.m_row)
2461     {
2462         if (!patches)
2463             return;
2464
2465         std::unique_ptr<ConstantRowValueHandoverPatch> patch(new ConstantRowValueHandoverPatch);
2466         ConstRow::generate_patch(source.m_row, patch->row_patch);
2467         patches->emplace_back(patch.release());
2468     }
2469
2470     ConstRow m_row;
2471 };
2472
2473 template <typename T>
2474 class SubColumns;
2475
2476 // This is for LinkList and BackLink too since they're declared as typedefs of Link.
2477 template <>
2478 class Columns<Link> : public Subexpr2<Link> {
2479 public:
2480     Query is_null()
2481     {
2482         if (m_link_map.m_link_columns.size() > 1)
2483             throw std::runtime_error("Combining link() and is_null() is currently not supported");
2484         // Todo, it may be useful to support the above, but we would need to figure out an intuitive behaviour
2485         return make_expression<UnaryLinkCompare<false>>(m_link_map);
2486     }
2487
2488     Query is_not_null()
2489     {
2490         if (m_link_map.m_link_columns.size() > 1)
2491             throw std::runtime_error("Combining link() and is_not_null() is currently not supported");
2492         // Todo, it may be useful to support the above, but we would need to figure out an intuitive behaviour
2493         return make_expression<UnaryLinkCompare<true>>(m_link_map);
2494     }
2495
2496     LinkCount count() const
2497     {
2498         return LinkCount(m_link_map);
2499     }
2500
2501     template <typename C>
2502     SubColumns<C> column(size_t column_ndx) const
2503     {
2504         return SubColumns<C>(Columns<C>(column_ndx, m_link_map.target_table()), m_link_map);
2505     }
2506
2507     const LinkMap& link_map() const
2508     {
2509         return m_link_map;
2510     }
2511
2512     const Table* get_base_table() const override
2513     {
2514         return m_link_map.base_table();
2515     }
2516     void set_base_table(const Table* table) override
2517     {
2518         m_link_map.set_base_table(table);
2519     }
2520
2521     void verify_column() const override
2522     {
2523         m_link_map.verify_columns();
2524     }
2525
2526     std::string description() const override
2527     {
2528         return m_link_map.description();
2529     }
2530
2531     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2532     {
2533         return std::unique_ptr<Subexpr>(new Columns<Link>(*this, patches));
2534     }
2535
2536     void evaluate(size_t index, ValueBase& destination) override;
2537
2538
2539 private:
2540     LinkMap m_link_map;
2541     friend class Table;
2542
2543     Columns(size_t column_ndx, const Table* table, const std::vector<size_t>& links = {})
2544         : m_link_map(table, links)
2545     {
2546         static_cast<void>(column_ndx);
2547     }
2548     Columns(const Columns& other, QueryNodeHandoverPatches* patches)
2549         : Subexpr2<Link>(other)
2550         , m_link_map(other.m_link_map, patches)
2551     {
2552     }
2553 };
2554
2555 template <typename T>
2556 class ListColumns;
2557 template <typename T, typename Operation>
2558 class ListColumnAggregate;
2559 namespace aggregate_operations {
2560 template <typename T>
2561 class Minimum;
2562 template <typename T>
2563 class Maximum;
2564 template <typename T>
2565 class Sum;
2566 template <typename T>
2567 class Average;
2568 }
2569
2570 template <>
2571 class Columns<SubTable> : public Subexpr2<SubTable> {
2572 public:
2573     const Table* get_base_table() const override
2574     {
2575         return m_link_map.base_table();
2576     }
2577
2578     void set_base_table(const Table* table) override
2579     {
2580         m_link_map.set_base_table(table);
2581         m_column = &m_link_map.target_table()->get_column_table(m_column_ndx);
2582     }
2583
2584     void verify_column() const override
2585     {
2586         m_link_map.verify_columns();
2587         m_link_map.target_table()->verify_column(m_column_ndx, m_column);
2588     }
2589
2590     std::string description() const override
2591     {
2592         return m_link_map.description();
2593     }
2594
2595     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2596     {
2597         return std::unique_ptr<Subexpr>(new Columns<SubTable>(*this, patches));
2598     }
2599
2600     void evaluate(size_t index, ValueBase& destination) override
2601     {
2602         evaluate_internal(index, destination, ValueBase::default_size);
2603     }
2604
2605     void evaluate_internal(size_t index, ValueBase& destination, size_t nb_elements);
2606
2607     template <typename T>
2608     ListColumns<T> column(size_t ndx) const
2609     {
2610         return ListColumns<T>(ndx, Columns<SubTable>(*this, nullptr));
2611     }
2612
2613     template <typename T>
2614     ListColumns<T> list() const
2615     {
2616         return column<T>(0);
2617     }
2618
2619     SizeOperator<Size<ConstTableRef>> size()
2620     {
2621         return SizeOperator<Size<ConstTableRef>>(this->clone(nullptr));
2622     }
2623
2624 private:
2625     LinkMap m_link_map;
2626     size_t m_column_ndx;
2627     const SubtableColumn* m_column = nullptr;
2628     friend class Table;
2629     template <class T>
2630     friend class ListColumnsBase;
2631     template <class T, class U>
2632     friend class ListColumnAggregate;
2633
2634     Columns(size_t column_ndx, const Table* table, const std::vector<size_t>& links = {})
2635         : m_link_map(table, links)
2636         , m_column_ndx(column_ndx)
2637         , m_column(&m_link_map.target_table()->get_column_table(column_ndx))
2638     {
2639     }
2640
2641     Columns(const Columns<SubTable>& other, QueryNodeHandoverPatches* patches)
2642         : Subexpr2<SubTable>(other)
2643         , m_link_map(other.m_link_map, patches)
2644         , m_column_ndx(other.m_column_ndx)
2645         , m_column(other.m_column)
2646     {
2647         if (m_column && patches)
2648             m_column_ndx = m_column->get_column_index();
2649     }
2650 };
2651
2652 template <typename T>
2653 class ListColumnsBase : public Subexpr2<T> {
2654 public:
2655     ListColumnsBase(size_t column_ndx, Columns<SubTable> column)
2656         : m_column_ndx(column_ndx)
2657         , m_subtable_column(std::move(column))
2658     {
2659     }
2660
2661     ListColumnsBase(const ListColumnsBase& other, QueryNodeHandoverPatches* patches)
2662         : m_column_ndx(other.m_column_ndx)
2663         , m_subtable_column(other.m_subtable_column, patches)
2664     {
2665     }
2666
2667     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2668     {
2669         return make_subexpr<ListColumns<T>>(*this, patches);
2670     }
2671
2672     const Table* get_base_table() const override
2673     {
2674         return m_subtable_column.get_base_table();
2675     }
2676
2677     void set_base_table(const Table* table) override
2678     {
2679         m_subtable_column.set_base_table(table);
2680     }
2681
2682     void verify_column() const override
2683     {
2684         m_subtable_column.verify_column();
2685     }
2686
2687     void evaluate(size_t index, ValueBase& destination) override
2688     {
2689         Value<ConstTableRef> subtables;
2690         m_subtable_column.evaluate_internal(index, subtables, 1);
2691         size_t sz = 0;
2692         for (size_t i = 0; i < subtables.m_values; i++) {
2693             auto val = subtables.m_storage[i];
2694             if (val)
2695                 sz += val->size();
2696         }
2697         auto v = make_value_for_link<typename util::RemoveOptional<T>::type>(false, sz);
2698         size_t k = 0;
2699         for (size_t i = 0; i < subtables.m_values; i++) {
2700             auto table = subtables.m_storage[i];
2701             if (table) {
2702                 size_t s = table->size();
2703                 for (size_t j = 0; j < s; j++) {
2704                     if (!table->is_null(m_column_ndx, j)) {
2705                         v.m_storage.set(k++, table->get<T>(m_column_ndx, j));
2706                     }
2707                 }
2708             }
2709         }
2710         destination.import(v);
2711     }
2712
2713     virtual std::string description() const override
2714     {
2715         const Table* table = get_base_table();
2716         if (table && table->is_attached()) {
2717             if (m_subtable_column.m_column) {
2718                 return std::string(table->get_column_name(m_subtable_column.m_column_ndx));
2719
2720             }
2721             else {
2722                 return std::string(table->get_column_name(m_column_ndx));
2723             }
2724         }
2725         return "";
2726     }
2727
2728     ListColumnAggregate<T, aggregate_operations::Minimum<T>> min() const
2729     {
2730         return {m_column_ndx, m_subtable_column};
2731     }
2732
2733     ListColumnAggregate<T, aggregate_operations::Maximum<T>> max() const
2734     {
2735         return {m_column_ndx, m_subtable_column};
2736     }
2737
2738     ListColumnAggregate<T, aggregate_operations::Sum<T>> sum() const
2739     {
2740         return {m_column_ndx, m_subtable_column};
2741     }
2742
2743     ListColumnAggregate<T, aggregate_operations::Average<T>> average() const
2744     {
2745         return {m_column_ndx, m_subtable_column};
2746     }
2747
2748
2749 private:
2750     // Storing the column index here could be a potential problem if the column
2751     // changes id due to insertion/deletion.
2752     size_t m_column_ndx;
2753     Columns<SubTable> m_subtable_column;
2754 };
2755
2756 template <class T>
2757 class ListColumns : public ListColumnsBase<T> {
2758 public:
2759     using ListColumnsBase<T>::ListColumnsBase;
2760 };
2761
2762 template <>
2763 class ListColumns<StringData> : public ListColumnsBase<StringData> {
2764 public:
2765     ListColumns(size_t column_ndx, Columns<SubTable> column)
2766         : ListColumnsBase(column_ndx, column)
2767     {
2768     }
2769
2770     ListColumns(const ListColumnsBase& other, QueryNodeHandoverPatches* patches)
2771         : ListColumnsBase(other, patches)
2772     {
2773     }
2774
2775     ListColumns(ListColumns&& other)
2776         : ListColumnsBase(other)
2777     {
2778     }
2779 };
2780
2781 template <typename T, typename Operation>
2782 class ListColumnAggregate : public Subexpr2<typename Operation::ResultType> {
2783 public:
2784     using R = typename Operation::ResultType;
2785
2786     ListColumnAggregate(size_t column_ndx, Columns<SubTable> column)
2787         : m_column_ndx(column_ndx)
2788         , m_subtable_column(std::move(column))
2789     {
2790     }
2791
2792     ListColumnAggregate(const ListColumnAggregate& other, QueryNodeHandoverPatches* patches)
2793         : m_column_ndx(other.m_column_ndx)
2794         , m_subtable_column(other.m_subtable_column, patches)
2795     {
2796     }
2797
2798     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2799     {
2800         return make_subexpr<ListColumnAggregate>(*this, patches);
2801     }
2802
2803     const Table* get_base_table() const override
2804     {
2805         return m_subtable_column.get_base_table();
2806     }
2807
2808     void set_base_table(const Table* table) override
2809     {
2810         m_subtable_column.set_base_table(table);
2811     }
2812
2813     void verify_column() const override
2814     {
2815         m_subtable_column.verify_column();
2816     }
2817
2818     void evaluate(size_t index, ValueBase& destination) override
2819     {
2820         Value<ConstTableRef> subtables;
2821         m_subtable_column.evaluate_internal(index, subtables, 1);
2822         REALM_ASSERT_DEBUG(subtables.m_values > 0 || subtables.m_from_link_list);
2823         size_t sz = subtables.m_values;
2824         // The result is an aggregate value for each table
2825         auto v = make_value_for_link<R>(!subtables.m_from_link_list, sz);
2826         for (unsigned i = 0; i < sz; i++) {
2827             auto table = subtables.m_storage[i];
2828             Operation op;
2829             if (table) {
2830                 size_t s = table->size();
2831                 for (unsigned j = 0; j < s; j++) {
2832                     op.accumulate(table->get<T>(m_column_ndx, j));
2833                 }
2834             }
2835             if (op.is_null()) {
2836                 v.m_storage.set_null(i);
2837             }
2838             else {
2839                 v.m_storage.set(i, op.result());
2840             }
2841         }
2842         destination.import(v);
2843     }
2844
2845     virtual std::string description() const override
2846     {
2847         const Table* table = get_base_table();
2848         if (table && table->is_attached()) {
2849             return std::string(table->get_column_name(m_column_ndx)) + util::serializer::value_separator + Operation::description() + "()";
2850         }
2851         return "";
2852     }
2853
2854 private:
2855     size_t m_column_ndx;
2856     Columns<SubTable> m_subtable_column;
2857 };
2858
2859 template <class Operator>
2860 Query compare(const Subexpr2<Link>& left, const ConstRow& row)
2861 {
2862     static_assert(std::is_same<Operator, Equal>::value || std::is_same<Operator, NotEqual>::value,
2863                   "Links can only be compared for equality.");
2864     const Columns<Link>* column = dynamic_cast<const Columns<Link>*>(&left);
2865     if (column) {
2866         const LinkMap& link_map = column->link_map();
2867         REALM_ASSERT(link_map.target_table() == row.get_table() || !row.is_attached());
2868 #ifdef REALM_OLDQUERY_FALLBACK
2869         if (link_map.m_link_columns.size() == 1) {
2870             // We can fall back to Query::links_to for != and == operations on links, but only
2871             // for == on link lists. This is because negating query.links_to() is equivalent to
2872             // to "ALL linklist != row" rather than the "ANY linklist != row" semantics we're after.
2873             if (link_map.m_link_types[0] == col_type_Link ||
2874                 (link_map.m_link_types[0] == col_type_LinkList && std::is_same<Operator, Equal>::value)) {
2875                 const Table* t = column->get_base_table();
2876                 Query query(*t);
2877
2878                 if (std::is_same<Operator, NotEqual>::value) {
2879                     // Negate the following `links_to`.
2880                     query.Not();
2881                 }
2882                 query.links_to(link_map.m_link_column_indexes[0], row);
2883                 return query;
2884             }
2885         }
2886 #endif
2887     }
2888     return make_expression<Compare<Operator, RowIndex>>(left.clone(), make_subexpr<ConstantRowValue>(row));
2889 }
2890
2891 inline Query operator==(const Subexpr2<Link>& left, const ConstRow& row)
2892 {
2893     return compare<Equal>(left, row);
2894 }
2895 inline Query operator!=(const Subexpr2<Link>& left, const ConstRow& row)
2896 {
2897     return compare<NotEqual>(left, row);
2898 }
2899 inline Query operator==(const ConstRow& row, const Subexpr2<Link>& right)
2900 {
2901     return compare<Equal>(right, row);
2902 }
2903 inline Query operator!=(const ConstRow& row, const Subexpr2<Link>& right)
2904 {
2905     return compare<NotEqual>(right, row);
2906 }
2907
2908 template <class Operator>
2909 Query compare(const Subexpr2<Link>& left, null)
2910 {
2911     static_assert(std::is_same<Operator, Equal>::value || std::is_same<Operator, NotEqual>::value,
2912                   "Links can only be compared for equality.");
2913     return make_expression<Compare<Operator, RowIndex>>(left.clone(), make_subexpr<Value<RowIndex>>());
2914 }
2915
2916 inline Query operator==(const Subexpr2<Link>& left, null)
2917 {
2918     return compare<Equal>(left, null());
2919 }
2920 inline Query operator!=(const Subexpr2<Link>& left, null)
2921 {
2922     return compare<NotEqual>(left, null());
2923 }
2924 inline Query operator==(null, const Subexpr2<Link>& right)
2925 {
2926     return compare<Equal>(right, null());
2927 }
2928 inline Query operator!=(null, const Subexpr2<Link>& right)
2929 {
2930     return compare<NotEqual>(right, null());
2931 }
2932
2933
2934 template <class T>
2935 class Columns : public Subexpr2<T> {
2936 public:
2937     using ColType = typename ColumnTypeTraits<T>::column_type;
2938
2939     Columns(size_t column, const Table* table, std::vector<size_t> links = {})
2940         : m_link_map(table, std::move(links))
2941         , m_column_ndx(column)
2942         , m_nullable(m_link_map.target_table()->is_nullable(m_column_ndx))
2943     {
2944     }
2945
2946     Columns(const Columns& other, QueryNodeHandoverPatches* patches = nullptr)
2947         : m_link_map(other.m_link_map, patches)
2948         , m_column_ndx(other.m_column_ndx)
2949         , m_nullable(other.m_nullable)
2950     {
2951         if (!other.m_sg)
2952             return;
2953
2954         if (patches) {
2955             m_column_ndx = other.get_column_base().get_column_index();
2956         }
2957         else {
2958             if (m_nullable && std::is_same<typename ColType::value_type, int64_t>::value) {
2959                 init<IntNullColumn>(&other.get_column_base());
2960             }
2961             else {
2962                 init<ColType>(&other.get_column_base());
2963             }
2964         }
2965     }
2966
2967     Columns& operator=(const Columns& other)
2968     {
2969         if (this != &other) {
2970             m_link_map = other.m_link_map;
2971             m_sg.reset();
2972             m_column_ndx = other.m_column_ndx;
2973             m_nullable = other.m_nullable;
2974         }
2975         return *this;
2976     }
2977
2978     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
2979     {
2980         return make_subexpr<Columns<T>>(*this, patches);
2981     }
2982
2983     // See comment in base class
2984     void set_base_table(const Table* table) override
2985     {
2986         if (m_sg && table == get_base_table())
2987             return;
2988
2989         m_link_map.set_base_table(table);
2990         m_nullable = m_link_map.target_table()->is_nullable(m_column_ndx);
2991
2992         const ColumnBase* c = &m_link_map.target_table()->get_column_base(m_column_ndx);
2993         if (m_nullable && std::is_same<typename ColType::value_type, int64_t>::value) {
2994             init<IntNullColumn>(c);
2995         }
2996         else {
2997             init<ColType>(c);
2998         }
2999     }
3000
3001     void verify_column() const override
3002     {
3003         // verify links
3004         m_link_map.verify_columns();
3005         // verify target table
3006         const Table* target_table = m_link_map.target_table();
3007         if (target_table && m_column_ndx != npos) {
3008             target_table->verify_column(m_column_ndx, &get_column_base());
3009         }
3010     }
3011
3012     template <class ActualColType>
3013     void init(const ColumnBase* c)
3014     {
3015         REALM_ASSERT_DEBUG(dynamic_cast<const ActualColType*>(c));
3016         if (m_sg == nullptr) {
3017             m_sg.reset(new SequentialGetter<ActualColType>());
3018         }
3019         static_cast<SequentialGetter<ActualColType>&>(*m_sg).init(static_cast<const ActualColType*>(c));
3020     }
3021
3022     // Recursively fetch tables of columns in expression tree. Used when user first builds a stand-alone expression
3023     // and binds it to a Query at a later time
3024     const Table* get_base_table() const override
3025     {
3026         return m_link_map.base_table();
3027     }
3028
3029     template <class ColType2 = ColType>
3030     void evaluate_internal(size_t index, ValueBase& destination)
3031     {
3032         REALM_ASSERT_DEBUG(m_sg.get());
3033         REALM_ASSERT_DEBUG(dynamic_cast<SequentialGetter<ColType2>*>(m_sg.get()));
3034
3035         using U = typename ColType2::value_type;
3036         auto sgc = static_cast<SequentialGetter<ColType2>*>(m_sg.get());
3037         REALM_ASSERT_DEBUG(sgc->m_column);
3038
3039         if (links_exist()) {
3040             // LinkList with more than 0 values. Create Value with payload for all fields
3041
3042             std::vector<size_t> links = m_link_map.get_links(index);
3043             auto v = make_value_for_link<typename util::RemoveOptional<U>::type>(m_link_map.only_unary_links(),
3044                                                                                  links.size());
3045
3046             for (size_t t = 0; t < links.size(); t++) {
3047                 size_t link_to = links[t];
3048                 sgc->cache_next(link_to);
3049
3050                 if (sgc->m_column->is_null(link_to))
3051                     v.m_storage.set_null(t);
3052                 else
3053                     v.m_storage.set(t, sgc->get_next(link_to));
3054             }
3055             destination.import(v);
3056         }
3057         else {
3058             // Not a Link column
3059             // make sequential getter load the respective leaf to access data at column row 'index'
3060             sgc->cache_next(index);
3061             size_t colsize = sgc->m_column->size();
3062
3063             // Now load `ValueBase::default_size` rows from from the leaf into m_storage. If it's an integer
3064             // leaf, then it contains the method get_chunk() which copies these values in a super fast way (first
3065             // case of the `if` below. Otherwise, copy the values one by one in a for-loop (the `else` case).
3066             if (std::is_same<U, int64_t>::value && index + ValueBase::default_size <= sgc->m_leaf_end) {
3067                 Value<int64_t> v;
3068
3069                 // If you want to modify 'default_size' then update Array::get_chunk()
3070                 REALM_ASSERT_3(ValueBase::default_size, ==, 8);
3071
3072                 auto sgc_2 = static_cast<SequentialGetter<ColType>*>(m_sg.get());
3073                 sgc_2->m_leaf_ptr->get_chunk(index - sgc->m_leaf_start, v.m_storage.m_first);
3074
3075                 destination.import(v);
3076             }
3077             else {
3078                 size_t rows = colsize - index;
3079                 if (rows > ValueBase::default_size)
3080                     rows = ValueBase::default_size;
3081                 Value<typename util::RemoveOptional<U>::type> v(false, rows);
3082
3083                 for (size_t t = 0; t < rows; t++)
3084                     v.m_storage.set(t, sgc->get_next(index + t));
3085
3086                 destination.import(v);
3087             }
3088         }
3089     }
3090
3091     virtual std::string description() const override
3092     {
3093         std::string desc = "";
3094         if (links_exist()) {
3095             desc = m_link_map.description() + util::serializer::value_separator;
3096         }
3097         const Table* target_table = m_link_map.target_table();
3098         if (target_table && target_table->is_attached() && m_column_ndx != npos) {
3099             desc += std::string(target_table->get_column_name(m_column_ndx));
3100             return desc;
3101         }
3102         return "";
3103     }
3104
3105     // Load values from Column into destination
3106     void evaluate(size_t index, ValueBase& destination) override
3107     {
3108         if (m_nullable && std::is_same<typename ColType::value_type, int64_t>::value) {
3109             evaluate_internal<IntNullColumn>(index, destination);
3110         }
3111         else {
3112             evaluate_internal<ColType>(index, destination);
3113         }
3114     }
3115
3116     bool links_exist() const
3117     {
3118         return m_link_map.m_link_columns.size() > 0;
3119     }
3120
3121     bool is_nullable() const
3122     {
3123         return m_nullable;
3124     }
3125
3126     size_t column_ndx() const noexcept
3127     {
3128         return m_sg ? get_column_base().get_column_index() : m_column_ndx;
3129     }
3130
3131 private:
3132     LinkMap m_link_map;
3133
3134     // Fast (leaf caching) value getter for payload column (column in table on which query condition is executed)
3135     std::unique_ptr<SequentialGetterBase> m_sg;
3136
3137     // Column index of payload column of m_table
3138     size_t m_column_ndx;
3139
3140     // set to false by default for stand-alone Columns declaration that are not yet associated with any table
3141     // or oclumn. Call init() to update it or use a constructor that takes table + column index as argument.
3142     bool m_nullable = false;
3143
3144     const ColumnBase& get_column_base() const noexcept
3145     {
3146         if (m_nullable && std::is_same<int64_t, T>::value)
3147             return *static_cast<SequentialGetter<IntNullColumn>&>(*m_sg).m_column;
3148         else
3149             return *static_cast<SequentialGetter<ColType>&>(*m_sg).m_column;
3150     }
3151 };
3152
3153 template <typename T, typename Operation>
3154 class SubColumnAggregate;
3155
3156 template <typename T>
3157 class SubColumns : public Subexpr {
3158 public:
3159     SubColumns(Columns<T> column, LinkMap link_map)
3160         : m_column(std::move(column))
3161         , m_link_map(std::move(link_map))
3162     {
3163     }
3164
3165     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches*) const override
3166     {
3167         return make_subexpr<SubColumns<T>>(*this);
3168     }
3169
3170     const Table* get_base_table() const override
3171     {
3172         return m_link_map.base_table();
3173     }
3174
3175     void set_base_table(const Table* table) override
3176     {
3177         m_link_map.set_base_table(table);
3178         m_column.set_base_table(m_link_map.target_table());
3179     }
3180
3181     void verify_column() const override
3182     {
3183         m_link_map.verify_columns();
3184         m_column.verify_column();
3185     }
3186
3187     void evaluate(size_t, ValueBase&) override
3188     {
3189         // SubColumns can only be used in an expression in conjunction with its aggregate methods.
3190         REALM_ASSERT(false);
3191     }
3192
3193     virtual std::string description() const override
3194     {
3195         return ""; // by itself there are no conditions, see SubColumnAggregate
3196     }
3197
3198     SubColumnAggregate<T, aggregate_operations::Minimum<T>> min() const
3199     {
3200         return {m_column, m_link_map};
3201     }
3202
3203     SubColumnAggregate<T, aggregate_operations::Maximum<T>> max() const
3204     {
3205         return {m_column, m_link_map};
3206     }
3207
3208     SubColumnAggregate<T, aggregate_operations::Sum<T>> sum() const
3209     {
3210         return {m_column, m_link_map};
3211     }
3212
3213     SubColumnAggregate<T, aggregate_operations::Average<T>> average() const
3214     {
3215         return {m_column, m_link_map};
3216     }
3217
3218 private:
3219     Columns<T> m_column;
3220     LinkMap m_link_map;
3221 };
3222
3223 template <typename T, typename Operation>
3224 class SubColumnAggregate : public Subexpr2<typename Operation::ResultType> {
3225 public:
3226     SubColumnAggregate(Columns<T> column, LinkMap link_map)
3227         : m_column(std::move(column))
3228         , m_link_map(std::move(link_map))
3229     {
3230     }
3231     SubColumnAggregate(SubColumnAggregate const& other, QueryNodeHandoverPatches* patches)
3232         : m_column(other.m_column, patches)
3233         , m_link_map(other.m_link_map, patches)
3234     {
3235     }
3236
3237     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
3238     {
3239         return make_subexpr<SubColumnAggregate>(*this, patches);
3240     }
3241
3242     const Table* get_base_table() const override
3243     {
3244         return m_link_map.base_table();
3245     }
3246
3247     void set_base_table(const Table* table) override
3248     {
3249         m_link_map.set_base_table(table);
3250         m_column.set_base_table(m_link_map.target_table());
3251     }
3252
3253     void verify_column() const override
3254     {
3255         m_link_map.verify_columns();
3256         m_column.verify_column();
3257     }
3258
3259     void evaluate(size_t index, ValueBase& destination) override
3260     {
3261         std::vector<size_t> links = m_link_map.get_links(index);
3262         std::sort(links.begin(), links.end());
3263
3264         Operation op;
3265         for (size_t link_index = 0; link_index < links.size();) {
3266             Value<T> value;
3267             size_t link = links[link_index];
3268             m_column.evaluate(link, value);
3269
3270             // Columns<T>::evaluate fetches values in chunks of ValueBase::default_size. Process all values
3271             // within the chunk that came from rows that we link to.
3272             const auto& value_storage = value.m_storage;
3273             for (size_t value_index = 0; value_index < value.m_values;) {
3274                 if (!value_storage.is_null(value_index)) {
3275                     op.accumulate(value_storage[value_index]);
3276                 }
3277                 if (++link_index >= links.size()) {
3278                     break;
3279                 }
3280
3281                 size_t previous_link = link;
3282                 link = links[link_index];
3283                 value_index += link - previous_link;
3284             }
3285         }
3286         if (op.is_null()) {
3287             destination.import(Value<null>(false, 1, null()));
3288         }
3289         else {
3290             destination.import(Value<typename Operation::ResultType>(false, 1, op.result()));
3291         }
3292     }
3293
3294     virtual std::string description() const override
3295     {
3296         return m_link_map.description() + util::serializer::value_separator + Operation::description() + util::serializer::value_separator + m_column.description();
3297     }
3298
3299 private:
3300     Columns<T> m_column;
3301     LinkMap m_link_map;
3302 };
3303
3304 struct SubQueryCountHandoverPatch : QueryNodeHandoverPatch {
3305     QueryHandoverPatch m_query;
3306 };
3307
3308 class SubQueryCount : public Subexpr2<Int> {
3309 public:
3310     SubQueryCount(Query q, LinkMap link_map)
3311         : m_query(std::move(q))
3312         , m_link_map(std::move(link_map))
3313     {
3314     }
3315
3316     const Table* get_base_table() const override
3317     {
3318         return m_link_map.base_table();
3319     }
3320
3321     void set_base_table(const Table* table) override
3322     {
3323         m_link_map.set_base_table(table);
3324     }
3325
3326     void verify_column() const override
3327     {
3328         m_link_map.verify_columns();
3329     }
3330
3331     void evaluate(size_t index, ValueBase& destination) override
3332     {
3333         std::vector<size_t> links = m_link_map.get_links(index);
3334         std::sort(links.begin(), links.end());
3335
3336         size_t count = std::accumulate(links.begin(), links.end(), size_t(0), [this](size_t running_count, size_t link) {
3337             return running_count + m_query.count(link, link + 1, 1);
3338         });
3339
3340         destination.import(Value<Int>(false, 1, size_t(count)));
3341     }
3342
3343     virtual std::string description() const override
3344     {
3345         return m_link_map.description() + util::serializer::value_separator + "SUBQUERY(" + m_query.get_description() + ")"
3346             + util::serializer::value_separator + "@count";
3347     }
3348
3349     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
3350     {
3351         if (patches)
3352             return std::unique_ptr<Subexpr>(new SubQueryCount(*this, patches));
3353
3354         return make_subexpr<SubQueryCount>(*this);
3355     }
3356
3357     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
3358     {
3359         REALM_ASSERT(patches.size());
3360         std::unique_ptr<QueryNodeHandoverPatch> abstract_patch = std::move(patches.back());
3361         patches.pop_back();
3362
3363         auto patch = dynamic_cast<SubQueryCountHandoverPatch*>(abstract_patch.get());
3364         REALM_ASSERT(patch);
3365
3366         m_query.apply_patch(patch->m_query, group);
3367     }
3368
3369 private:
3370     SubQueryCount(const SubQueryCount& other, QueryNodeHandoverPatches* patches)
3371         : m_link_map(other.m_link_map, patches)
3372     {
3373         std::unique_ptr<SubQueryCountHandoverPatch> patch(new SubQueryCountHandoverPatch);
3374         m_query = Query(other.m_query, patch->m_query, ConstSourcePayload::Copy);
3375         patches->emplace_back(patch.release());
3376     }
3377
3378     Query m_query;
3379     LinkMap m_link_map;
3380 };
3381
3382 // The unused template parameter is a hack to avoid a circular dependency between table.hpp and query_expression.hpp.
3383 template <class>
3384 class SubQuery {
3385 public:
3386     SubQuery(Columns<Link> link_column, Query query)
3387         : m_query(std::move(query))
3388         , m_link_map(link_column.link_map())
3389     {
3390         REALM_ASSERT(m_link_map.target_table() == m_query.get_table());
3391     }
3392
3393     SubQueryCount count() const
3394     {
3395         return SubQueryCount(m_query, m_link_map);
3396     }
3397
3398 private:
3399     Query m_query;
3400     LinkMap m_link_map;
3401 };
3402
3403 namespace aggregate_operations {
3404 template <typename T, typename Derived, typename R = T>
3405 class BaseAggregateOperation {
3406     static_assert(std::is_same<T, Int>::value || std::is_same<T, Float>::value || std::is_same<T, Double>::value,
3407                   "Numeric aggregates can only be used with subcolumns of numeric types");
3408
3409 public:
3410     using ResultType = R;
3411
3412     void accumulate(T value)
3413     {
3414         m_count++;
3415         m_result = Derived::apply(m_result, value);
3416     }
3417
3418     bool is_null() const
3419     {
3420         return m_count == 0;
3421     }
3422     ResultType result() const
3423     {
3424         return m_result;
3425     }
3426
3427 protected:
3428     size_t m_count = 0;
3429     ResultType m_result = Derived::initial_value();
3430 };
3431
3432 template <typename T>
3433 class Minimum : public BaseAggregateOperation<T, Minimum<T>> {
3434 public:
3435     static T initial_value()
3436     {
3437         return std::numeric_limits<T>::max();
3438     }
3439     static T apply(T a, T b)
3440     {
3441         return std::min(a, b);
3442     }
3443     static std::string description()
3444     {
3445         return "@min";
3446     }
3447 };
3448
3449 template <typename T>
3450 class Maximum : public BaseAggregateOperation<T, Maximum<T>> {
3451 public:
3452     static T initial_value()
3453     {
3454         return std::numeric_limits<T>::min();
3455     }
3456     static T apply(T a, T b)
3457     {
3458         return std::max(a, b);
3459     }
3460     static std::string description()
3461     {
3462         return "@max";
3463     }
3464 };
3465
3466 template <typename T>
3467 class Sum : public BaseAggregateOperation<T, Sum<T>> {
3468 public:
3469     static T initial_value()
3470     {
3471         return T();
3472     }
3473     static T apply(T a, T b)
3474     {
3475         return a + b;
3476     }
3477     bool is_null() const
3478     {
3479         return false;
3480     }
3481     static std::string description()
3482     {
3483         return "@sum";
3484     }
3485 };
3486
3487 template <typename T>
3488 class Average : public BaseAggregateOperation<T, Average<T>, double> {
3489     using Base = BaseAggregateOperation<T, Average<T>, double>;
3490
3491 public:
3492     static double initial_value()
3493     {
3494         return 0;
3495     }
3496     static double apply(double a, T b)
3497     {
3498         return a + b;
3499     }
3500     double result() const
3501     {
3502         return Base::m_result / Base::m_count;
3503     }
3504     static std::string description()
3505     {
3506         return "@avg";
3507     }
3508
3509 };
3510 }
3511
3512 template <class oper, class TLeft>
3513 class UnaryOperator : public Subexpr2<typename oper::type> {
3514 public:
3515     UnaryOperator(std::unique_ptr<TLeft> left)
3516         : m_left(std::move(left))
3517     {
3518     }
3519
3520     UnaryOperator(const UnaryOperator& other, QueryNodeHandoverPatches* patches)
3521         : m_left(other.m_left->clone(patches))
3522     {
3523     }
3524
3525     UnaryOperator& operator=(const UnaryOperator& other)
3526     {
3527         if (this != &other) {
3528             m_left = other.m_left->clone();
3529         }
3530         return *this;
3531     }
3532
3533     UnaryOperator(UnaryOperator&&) = default;
3534     UnaryOperator& operator=(UnaryOperator&&) = default;
3535
3536     // See comment in base class
3537     void set_base_table(const Table* table) override
3538     {
3539         m_left->set_base_table(table);
3540     }
3541
3542     void verify_column() const override
3543     {
3544         m_left->verify_column();
3545     }
3546
3547     // Recursively fetch tables of columns in expression tree. Used when user first builds a stand-alone expression
3548     // and binds it to a Query at a later time
3549     const Table* get_base_table() const override
3550     {
3551         return m_left->get_base_table();
3552     }
3553
3554     // destination = operator(left)
3555     void evaluate(size_t index, ValueBase& destination) override
3556     {
3557         Value<T> result;
3558         Value<T> left;
3559         m_left->evaluate(index, left);
3560         result.template fun<oper>(&left);
3561         destination.import(result);
3562     }
3563
3564     virtual std::string description() const override
3565     {
3566         if (m_left) {
3567             return m_left->description();
3568         }
3569         return "";
3570     }
3571
3572     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
3573     {
3574         return make_subexpr<UnaryOperator>(*this, patches);
3575     }
3576
3577     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
3578     {
3579         m_left->apply_handover_patch(patches, group);
3580     }
3581
3582 private:
3583     typedef typename oper::type T;
3584     std::unique_ptr<TLeft> m_left;
3585 };
3586
3587
3588 template <class oper, class TLeft, class TRight>
3589 class Operator : public Subexpr2<typename oper::type> {
3590 public:
3591     Operator(std::unique_ptr<TLeft> left, std::unique_ptr<TRight> right)
3592         : m_left(std::move(left))
3593         , m_right(std::move(right))
3594     {
3595     }
3596
3597     Operator(const Operator& other, QueryNodeHandoverPatches* patches)
3598         : m_left(other.m_left->clone(patches))
3599         , m_right(other.m_right->clone(patches))
3600     {
3601     }
3602
3603     Operator& operator=(const Operator& other)
3604     {
3605         if (this != &other) {
3606             m_left = other.m_left->clone();
3607             m_right = other.m_right->clone();
3608         }
3609         return *this;
3610     }
3611
3612     Operator(Operator&&) = default;
3613     Operator& operator=(Operator&&) = default;
3614
3615     // See comment in base class
3616     void set_base_table(const Table* table) override
3617     {
3618         m_left->set_base_table(table);
3619         m_right->set_base_table(table);
3620     }
3621
3622     void verify_column() const override
3623     {
3624         m_left->verify_column();
3625         m_right->verify_column();
3626     }
3627
3628     // Recursively fetch tables of columns in expression tree. Used when user first builds a stand-alone expression
3629     // and
3630     // binds it to a Query at a later time
3631     const Table* get_base_table() const override
3632     {
3633         const Table* l = m_left->get_base_table();
3634         const Table* r = m_right->get_base_table();
3635
3636         // Queries do not support multiple different tables; all tables must be the same.
3637         REALM_ASSERT(l == nullptr || r == nullptr || l == r);
3638
3639         // nullptr pointer means expression which isn't yet associated with any table, or is a Value<T>
3640         return l ? l : r;
3641     }
3642
3643     // destination = operator(left, right)
3644     void evaluate(size_t index, ValueBase& destination) override
3645     {
3646         Value<T> result;
3647         Value<T> left;
3648         Value<T> right;
3649         m_left->evaluate(index, left);
3650         m_right->evaluate(index, right);
3651         result.template fun<oper>(&left, &right);
3652         destination.import(result);
3653     }
3654
3655     virtual std::string description() const override
3656     {
3657         std::string s;
3658         if (m_left) {
3659             s += m_left->description();
3660         }
3661         s += oper::description();
3662         if (m_right) {
3663             s += m_right->description();
3664         }
3665         return s;
3666     }
3667
3668     std::unique_ptr<Subexpr> clone(QueryNodeHandoverPatches* patches) const override
3669     {
3670         return make_subexpr<Operator>(*this, patches);
3671     }
3672
3673     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
3674     {
3675         m_right->apply_handover_patch(patches, group);
3676         m_left->apply_handover_patch(patches, group);
3677     }
3678
3679 private:
3680     typedef typename oper::type T;
3681     std::unique_ptr<TLeft> m_left;
3682     std::unique_ptr<TRight> m_right;
3683 };
3684
3685
3686 template <class TCond, class T, class TLeft, class TRight>
3687 class Compare : public Expression {
3688 public:
3689     Compare(std::unique_ptr<TLeft> left, std::unique_ptr<TRight> right)
3690         : m_left(std::move(left))
3691         , m_right(std::move(right))
3692     {
3693     }
3694
3695     // See comment in base class
3696     void set_base_table(const Table* table) override
3697     {
3698         m_left->set_base_table(table);
3699         m_right->set_base_table(table);
3700     }
3701
3702     void verify_column() const override
3703     {
3704         m_left->verify_column();
3705         m_right->verify_column();
3706     }
3707
3708     // Recursively fetch tables of columns in expression tree. Used when user first builds a stand-alone expression
3709     // and
3710     // binds it to a Query at a later time
3711     const Table* get_base_table() const override
3712     {
3713         const Table* l = m_left->get_base_table();
3714         const Table* r = m_right->get_base_table();
3715
3716         // All main tables in each subexpression of a query (table.columns() or table.link()) must be the same.
3717         REALM_ASSERT(l == nullptr || r == nullptr || l == r);
3718
3719         // nullptr pointer means expression which isn't yet associated with any table, or is a Value<T>
3720         return l ? l : r;
3721     }
3722
3723     size_t find_first(size_t start, size_t end) const override
3724     {
3725         size_t match;
3726         Value<T> right;
3727         Value<T> left;
3728
3729         for (; start < end;) {
3730             m_left->evaluate(start, left);
3731             m_right->evaluate(start, right);
3732             match = Value<T>::template compare<TCond>(&left, &right);
3733
3734             if (match != not_found && match + start < end)
3735                 return start + match;
3736
3737             size_t rows =
3738                 (left.m_from_link_list || right.m_from_link_list) ? 1 : minimum(right.m_values, left.m_values);
3739             start += rows;
3740         }
3741
3742         return not_found; // no match
3743     }
3744
3745     virtual std::string description() const override
3746     {
3747         if (std::is_same<TCond, BeginsWith>::value
3748             || std::is_same<TCond, BeginsWithIns>::value
3749             || std::is_same<TCond, EndsWith>::value
3750             || std::is_same<TCond, EndsWithIns>::value
3751             || std::is_same<TCond, Contains>::value
3752             || std::is_same<TCond, ContainsIns>::value
3753             || std::is_same<TCond, Like>::value
3754             || std::is_same<TCond, LikeIns>::value) {
3755             // these string conditions have the arguments reversed but the order is important
3756             // operations ==, and != can be reversed because the produce the same results both ways
3757             return util::serializer::print_value(m_right->description() + " " + TCond::description()
3758                                                  + " " + m_left->description());
3759         }
3760         return util::serializer::print_value(m_left->description() + " " + TCond::description()
3761                                              + " " + m_right->description());
3762     }
3763
3764     std::unique_ptr<Expression> clone(QueryNodeHandoverPatches* patches) const override
3765     {
3766         return std::unique_ptr<Expression>(new Compare(*this, patches));
3767     }
3768
3769     void apply_handover_patch(QueryNodeHandoverPatches& patches, Group& group) override
3770     {
3771         m_right->apply_handover_patch(patches, group);
3772         m_left->apply_handover_patch(patches, group);
3773     }
3774
3775 private:
3776     Compare(const Compare& other, QueryNodeHandoverPatches* patches)
3777         : m_left(other.m_left->clone(patches))
3778         , m_right(other.m_right->clone(patches))
3779     {
3780     }
3781
3782     std::unique_ptr<TLeft> m_left;
3783     std::unique_ptr<TRight> m_right;
3784 };
3785 }
3786 #endif // REALM_QUERY_EXPRESSION_HPP