LibSQL+SQLServer: Implement first cut of SELECT ... ORDER BY foo

Ordering is done by replacing the straight Vector holding the query
result in the SQLResult object with a dedicated Vector subclass that
inserts result rows according to their sort key using a binary search.
This is done in the ResultSet class.

There are limitations:
- "SELECT ... ORDER BY 1" (or 2 or 3 etc) is supposed to sort by the
n-th result column. This doesn't work yet
- "SELECT ... column-expression alias ... ORDER BY alias" is supposed to
sort by the column with the given alias. This doesn't work yet

What does work however is something like
```SELECT foo FROM bar SORT BY quux```
i.e. sorted by a column not in the result set. Once functions are
supported it should be possible to sort by random functions.

5 files changed, 93 insertions, 5 deletions

diff --git a/Userland/Libraries/LibSQL/AST/Select.cpp b/Userland/Libraries/LibSQL/AST/Select.cpp
index d890f1c7e9..9db06f02ab 100644
--- a/Userland/Libraries/LibSQL/AST/Select.cpp
+++ b/Userland/Libraries/LibSQL/AST/Select.cpp
@@ -7,6 +7,7 @@
 #include <LibSQL/AST/AST.h>
 #include <LibSQL/Database.h>
 #include <LibSQL/Meta.h>
+#include <LibSQL/ResultSet.h>
 #include <LibSQL/Row.h>
 
 namespace SQL::AST {
@@ -77,6 +78,14 @@ RefPtr<SQLResult> Select::execute(ExecutionContext& context) const
         }
     }
 
+    bool has_ordering { false };
+    AK::NonnullRefPtr<TupleDescriptor> sort_descriptor = AK::adopt_ref(*new TupleDescriptor);
+    for (auto& term : m_ordering_term_list) {
+        sort_descriptor->append(TupleElementDescriptor { .order = term.order() });
+        has_ordering = true;
+    }
+    Tuple sort_key(sort_descriptor);
+
     for (auto& row : rows) {
         context.current_row = &row;
         if (where_clause()) {
@@ -93,7 +102,17 @@ RefPtr<SQLResult> Select::execute(ExecutionContext& context) const
                 return context.result;
             tuple.append(value);
         }
-        context.result->append(tuple);
+
+        if (has_ordering) {
+            sort_key.clear();
+            for (auto& term : m_ordering_term_list) {
+                auto value = term.expression()->evaluate(context);
+                if (context.result->has_error())
+                    return context.result;
+                sort_key.append(value);
+            }
+        }
+        context.result->insert(tuple, sort_key);
     }
     return context.result;
 }
diff --git a/Userland/Libraries/LibSQL/CMakeLists.txt b/Userland/Libraries/LibSQL/CMakeLists.txt
index 395890f602..5bc6b4dc47 100644
--- a/Userland/Libraries/LibSQL/CMakeLists.txt
+++ b/Userland/Libraries/LibSQL/CMakeLists.txt
@@ -17,6 +17,7 @@ set(SOURCES
     Index.cpp
     Key.cpp
     Meta.cpp
+    ResultSet.cpp
     Row.cpp
     Serializer.cpp
     SQLClient.cpp
diff --git a/Userland/Libraries/LibSQL/ResultSet.cpp b/Userland/Libraries/LibSQL/ResultSet.cpp
new file mode 100644
index 0000000000..ee793bfbb2
--- /dev/null
+++ b/Userland/Libraries/LibSQL/ResultSet.cpp
@@ -0,0 +1,38 @@
+/*
+ * Copyright (c) 2022, Jan de Visser <jan@de-visser.net>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibSQL/ResultSet.h>
+
+namespace SQL {
+
+size_t ResultSet::binary_search(Tuple const& sort_key, size_t low, size_t high)
+{
+    if (high <= low) {
+        auto compare = sort_key.compare(at(low).sort_key);
+        return (compare > 0) ? low + 1 : low;
+    }
+
+    auto mid = (low + high) / 2;
+    auto compare = sort_key.compare(at(mid).sort_key);
+    if (compare == 0)
+        return mid + 1;
+
+    if (compare > 0)
+        return binary_search(sort_key, mid + 1, high);
+    return binary_search(sort_key, low, mid);
+}
+
+void ResultSet::insert_row(Tuple const& row, Tuple const& sort_key)
+{
+    if ((sort_key.size() == 0) || is_empty()) {
+        empend(row, sort_key);
+        return;
+    }
+    auto ix = binary_search(sort_key, 0, size() - 1);
+    insert(ix, ResultRow { row, sort_key });
+}
+
+}
diff --git a/Userland/Libraries/LibSQL/ResultSet.h b/Userland/Libraries/LibSQL/ResultSet.h
new file mode 100644
index 0000000000..8a9e60399c
--- /dev/null
+++ b/Userland/Libraries/LibSQL/ResultSet.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright (c) 2022, Jan de Visser <jan@de-visser.net>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/Vector.h>
+#include <LibSQL/Tuple.h>
+#include <LibSQL/Type.h>
+
+namespace SQL {
+
+struct ResultRow {
+    Tuple row;
+    Tuple sort_key;
+};
+
+class ResultSet : public Vector<ResultRow> {
+public:
+    ResultSet() = default;
+    void insert_row(Tuple const& row, Tuple const& sort_key);
+
+private:
+    size_t binary_search(Tuple const& sort_key, size_t low, size_t high);
+};
+
+}
diff --git a/Userland/Libraries/LibSQL/SQLResult.h b/Userland/Libraries/LibSQL/SQLResult.h
index 8072f67b0a..6847da8a62 100644
--- a/Userland/Libraries/LibSQL/SQLResult.h
+++ b/Userland/Libraries/LibSQL/SQLResult.h
@@ -10,6 +10,7 @@
 #include <AK/NonnullOwnPtrVector.h>
 #include <AK/Vector.h>
 #include <LibCore/Object.h>
+#include <LibSQL/ResultSet.h>
 #include <LibSQL/Tuple.h>
 #include <LibSQL/Type.h>
 
@@ -110,10 +111,10 @@ class SQLResult : public Core::Object {
     C_OBJECT(SQLResult)
 
 public:
-    void append(Tuple const& tuple)
+    void insert(Tuple const& row, Tuple const& sort_key)
     {
         m_has_results = true;
-        m_result_set.append(tuple);
+        m_result_set.insert_row(row, sort_key);
     }
 
     SQLCommand command() const { return m_command; }
@@ -129,7 +130,7 @@ public:
     bool has_error() const { return m_error.code != SQLErrorCode::NoError; }
     SQLError const& error() const { return m_error; }
     bool has_results() const { return m_has_results; }
-    Vector<Tuple> const& results() const { return m_result_set; }
+    ResultSet const& results() const { return m_result_set; }
 
 private:
     SQLResult() = default;
@@ -161,7 +162,7 @@ private:
     int m_insert_count { 0 };
     int m_delete_count { 0 };
     bool m_has_results { false };
-    Vector<Tuple> m_result_set;
+    ResultSet m_result_set;
 };
 
 }