Userland: Add new app called Assistant

'Assistant' is similar to macOS spotlight where you can quickly open a
text input, start typing, and hit 'enter' to launch apps or open
directories.

7 files changed, 620 insertions, 0 deletions

diff --git a/Userland/Applications/Assistant/CMakeLists.txt b/Userland/Applications/Assistant/CMakeLists.txt
new file mode 100644
index 0000000000..3a807ef3a8
--- /dev/null
+++ b/Userland/Applications/Assistant/CMakeLists.txt
@@ -0,0 +1,14 @@
+serenity_component(
+    Assistant
+    RECOMMENDED
+    TARGETS Assistant
+)
+
+set(SOURCES
+    Providers.cpp
+    FuzzyMatch.cpp
+    main.cpp
+    )
+
+serenity_app(Assistant ICON app-run)
+target_link_libraries(Assistant LibCore LibDesktop LibGUI LibJS LibThreading)
diff --git a/Userland/Applications/Assistant/FuzzyMatch.cpp b/Userland/Applications/Assistant/FuzzyMatch.cpp
new file mode 100644
index 0000000000..e6c2814cb4
--- /dev/null
+++ b/Userland/Applications/Assistant/FuzzyMatch.cpp
@@ -0,0 +1,122 @@
+/*
+ * Copyright (c) 2021, Spencer Dixon <spencercdixon@gmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "FuzzyMatch.h"
+#include <string.h>
+
+namespace Assistant {
+
+static constexpr const int RECURSION_LIMIT = 10;
+static constexpr const int MAX_MATCHES = 256;
+
+// Bonuses and penalties are used to build up a final score for the match.
+static constexpr const int SEQUENTIAL_BONUS = 15;            // bonus for adjacent matches (needle: 'ca', haystack: 'cat')
+static constexpr const int SEPARATOR_BONUS = 30;             // bonus if match occurs after a separator ('_' or ' ')
+static constexpr const int CAMEL_BONUS = 30;                 // bonus if match is uppercase and prev is lower (needle: 'myF' haystack: '/path/to/myFile.txt')
+static constexpr const int FIRST_LETTER_BONUS = 20;          // bonus if the first letter is matched (needle: 'c' haystack: 'cat')
+static constexpr const int LEADING_LETTER_PENALTY = -5;      // penalty applied for every letter in str before the first match
+static constexpr const int MAX_LEADING_LETTER_PENALTY = -15; // maximum penalty for leading letters
+static constexpr const int UNMATCHED_LETTER_PENALTY = -1;    // penalty for every letter that doesn't matter
+
+static FuzzyMatchResult fuzzy_match_recursive(String const& needle, String const& haystack, size_t needle_idx, size_t haystack_idx,
+    u8 const* src_matches, u8* matches, int next_match, int& recursion_count)
+{
+    int out_score = 0;
+
+    ++recursion_count;
+    if (recursion_count >= RECURSION_LIMIT)
+        return { false, out_score };
+
+    if (needle.length() == needle_idx || haystack.length() == haystack_idx)
+        return { false, out_score };
+
+    bool had_recursive_match = false;
+    constexpr size_t recursive_match_limit = 256;
+    u8 best_recursive_matches[recursive_match_limit];
+    int best_recursive_score = 0;
+
+    bool first_match = true;
+    while (needle_idx < needle.length() && haystack_idx < haystack.length()) {
+
+        if (needle.substring(needle_idx, 1).to_lowercase() == haystack.substring(haystack_idx, 1).to_lowercase()) {
+            if (next_match >= MAX_MATCHES)
+                return { false, out_score };
+
+            if (first_match && src_matches) {
+                memcpy(matches, src_matches, next_match);
+                first_match = false;
+            }
+
+            u8 recursive_matches[recursive_match_limit];
+            auto result = fuzzy_match_recursive(needle, haystack, needle_idx, haystack_idx + 1, matches, recursive_matches, next_match, recursion_count);
+            if (result.matched) {
+                if (!had_recursive_match || result.score > best_recursive_score) {
+                    memcpy(best_recursive_matches, recursive_matches, recursive_match_limit);
+                    best_recursive_score = result.score;
+                }
+                had_recursive_match = true;
+                matches[next_match++] = haystack_idx;
+            }
+            needle_idx++;
+        }
+        haystack_idx++;
+    }
+
+    bool matched = needle_idx == needle.length();
+    if (matched) {
+        out_score = 100;
+
+        int penalty = LEADING_LETTER_PENALTY * matches[0];
+        if (penalty < MAX_LEADING_LETTER_PENALTY)
+            penalty = MAX_LEADING_LETTER_PENALTY;
+        out_score += penalty;
+
+        int unmatched = haystack.length() - next_match;
+        out_score += UNMATCHED_LETTER_PENALTY * unmatched;
+
+        for (int i = 0; i < next_match; i++) {
+            u8 current_idx = matches[i];
+
+            if (i > 0) {
+                u8 previous_idx = matches[i - 1];
+                if (current_idx == previous_idx)
+                    out_score += SEQUENTIAL_BONUS;
+            }
+
+            if (current_idx > 0) {
+                auto current_character = haystack.substring(current_idx, 1);
+                auto neighbor_character = haystack.substring(current_idx - 1, 1);
+
+                if (neighbor_character != neighbor_character.to_uppercase() && current_character != current_character.to_lowercase())
+                    out_score += CAMEL_BONUS;
+
+                if (neighbor_character == "_" || neighbor_character == " ")
+                    out_score += SEPARATOR_BONUS;
+            } else {
+                out_score += FIRST_LETTER_BONUS;
+            }
+        }
+
+        if (had_recursive_match && (!matched || best_recursive_score > out_score)) {
+            memcpy(matches, best_recursive_matches, MAX_MATCHES);
+            out_score = best_recursive_score;
+            return { true, out_score };
+        } else if (matched) {
+            return { true, out_score };
+        }
+    }
+
+    return { false, out_score };
+}
+
+FuzzyMatchResult fuzzy_match(String needle, String haystack)
+{
+    int recursion_count = 0;
+    u8 matches[MAX_MATCHES];
+    return fuzzy_match_recursive(needle, haystack, 0, 0, nullptr, matches, 0, recursion_count);
+}
+
+}
diff --git a/Userland/Applications/Assistant/FuzzyMatch.h b/Userland/Applications/Assistant/FuzzyMatch.h
new file mode 100644
index 0000000000..9a471a322a
--- /dev/null
+++ b/Userland/Applications/Assistant/FuzzyMatch.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright (c) 2021, Spencer Dixon <spencercdixon@gmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/String.h>
+#include <AK/Tuple.h>
+
+namespace Assistant {
+
+struct FuzzyMatchResult {
+    bool matched { false };
+    int score { 0 };
+};
+
+// This fuzzy_match algorithm is based off a similar algorithm used by Sublime Text. The key insight is that instead
+// of doing a total in the distance between characters (I.E. Levenshtein Distance), we apply some meaningful heuristics
+// related to our dataset that we're trying to match to build up a score. Scores can then be sorted and displayed
+// with the highest at the top.
+//
+// Scores are not normalized between any values and have no particular meaning. The starting value is 100 and when we
+// detect good indicators of a match we add to the score. When we detect bad indicators, we penalize the match and subtract
+// from its score. Therefore, the longer the needle/haystack the greater the range of scores could be.
+FuzzyMatchResult fuzzy_match(String needle, String haystack);
+
+}
diff --git a/Userland/Applications/Assistant/Providers.cpp b/Userland/Applications/Assistant/Providers.cpp
new file mode 100644
index 0000000000..70bd9cd289
--- /dev/null
+++ b/Userland/Applications/Assistant/Providers.cpp
@@ -0,0 +1,78 @@
+/*
+ * Copyright (c) 2021, Spencer Dixon <spencercdixon@gmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "Providers.h"
+#include "FuzzyMatch.h"
+#include <LibGUI/Clipboard.h>
+#include <LibGUI/FileIconProvider.h>
+#include <LibJS/Interpreter.h>
+#include <LibJS/Lexer.h>
+#include <LibJS/Parser.h>
+#include <LibJS/Runtime/GlobalObject.h>
+
+namespace Assistant {
+
+void AppResult::activate() const
+{
+    m_app_file->spawn();
+}
+
+void CalculatorResult::activate() const
+{
+    GUI::Clipboard::the().set_plain_text(title());
+}
+
+void AppProvider::query(String const& query, Function<void(Vector<NonnullRefPtr<Result>>)> on_complete)
+{
+    if (query.starts_with("="))
+        return;
+
+    Vector<NonnullRefPtr<Result>> results;
+
+    Desktop::AppFile::for_each([&](NonnullRefPtr<Desktop::AppFile> app_file) {
+        auto match_result = fuzzy_match(query, app_file->name());
+        if (!match_result.matched)
+            return;
+
+        auto icon = GUI::FileIconProvider::icon_for_executable(app_file->executable());
+        results.append(adopt_ref(*new AppResult(icon.bitmap_for_size(16), app_file->name(), app_file, match_result.score)));
+    });
+
+    on_complete(results);
+}
+
+void CalculatorProvider::query(String const& query, Function<void(Vector<NonnullRefPtr<Result>>)> on_complete)
+{
+    if (!query.starts_with("="))
+        return;
+
+    auto vm = JS::VM::create();
+    auto interpreter = JS::Interpreter::create<JS::GlobalObject>(*vm);
+
+    auto source_code = query.substring(1);
+    auto parser = JS::Parser(JS::Lexer(source_code));
+    auto program = parser.parse_program();
+    if (parser.has_errors())
+        return;
+
+    interpreter->run(interpreter->global_object(), *program);
+    if (interpreter->exception())
+        return;
+
+    auto result = interpreter->vm().last_value();
+    String calculation;
+    if (!result.is_number()) {
+        calculation = "0";
+    } else {
+        calculation = result.to_string_without_side_effects();
+    }
+
+    Vector<NonnullRefPtr<Result>> results;
+    results.append(adopt_ref(*new CalculatorResult(calculation)));
+    on_complete(results);
+}
+
+}
diff --git a/Userland/Applications/Assistant/Providers.h b/Userland/Applications/Assistant/Providers.h
new file mode 100644
index 0000000000..42a0e1e5e3
--- /dev/null
+++ b/Userland/Applications/Assistant/Providers.h
@@ -0,0 +1,95 @@
+/*
+ * Copyright (c) 2021, Spencer Dixon <spencercdixon@gmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/String.h>
+#include <LibDesktop/AppFile.h>
+#include <LibGUI/Desktop.h>
+#include <LibJS/Interpreter.h>
+#include <LibJS/Runtime/VM.h>
+
+namespace Assistant {
+
+class Result : public RefCounted<Result> {
+public:
+    enum class Kind {
+        Unknown,
+        App,
+        Calculator,
+    };
+
+    virtual ~Result() = default;
+
+    virtual void activate() const = 0;
+
+    RefPtr<Gfx::Bitmap> bitmap() { return m_bitmap; }
+    String const& title() const { return m_title; }
+    Kind kind() const { return m_kind; }
+    int score() const { return m_score; }
+    bool equals(Result const& other) const
+    {
+        return title() == other.title() && kind() == other.kind();
+    }
+
+protected:
+    Result(RefPtr<Gfx::Bitmap> bitmap, String title, int score = 0, Kind kind = Kind::Unknown)
+        : m_bitmap(move(bitmap))
+        , m_title(move(title))
+        , m_score(score)
+        , m_kind(kind)
+    {
+    }
+
+private:
+    RefPtr<Gfx::Bitmap> m_bitmap;
+    String m_title;
+    int m_score { 0 };
+    Kind m_kind;
+};
+
+class AppResult : public Result {
+public:
+    AppResult(RefPtr<Gfx::Bitmap> bitmap, String title, NonnullRefPtr<Desktop::AppFile> af, int score)
+        : Result(move(bitmap), move(title), score, Kind::App)
+        , m_app_file(move(af))
+    {
+    }
+    ~AppResult() override = default;
+    void activate() const override;
+
+private:
+    NonnullRefPtr<Desktop::AppFile> m_app_file;
+};
+
+class CalculatorResult : public Result {
+public:
+    explicit CalculatorResult(String title)
+        : Result(GUI::Icon::default_icon("app-calculator").bitmap_for_size(16), move(title), 100, Kind::Calculator)
+    {
+    }
+    ~CalculatorResult() override = default;
+    void activate() const override;
+};
+
+class Provider {
+public:
+    virtual ~Provider() = default;
+
+    virtual void query(const String&, Function<void(Vector<NonnullRefPtr<Result>>)> on_complete) = 0;
+};
+
+class AppProvider : public Provider {
+public:
+    void query(String const& query, Function<void(Vector<NonnullRefPtr<Result>>)> on_complete) override;
+};
+
+class CalculatorProvider : public Provider {
+public:
+    void query(String const& query, Function<void(Vector<NonnullRefPtr<Result>>)> on_complete) override;
+};
+
+}
diff --git a/Userland/Applications/Assistant/main.cpp b/Userland/Applications/Assistant/main.cpp
new file mode 100644
index 0000000000..22e33c397f
--- /dev/null
+++ b/Userland/Applications/Assistant/main.cpp
@@ -0,0 +1,279 @@
+/*
+ * Copyright (c) 2021, Spencer Dixon <spencercdixon@gmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "Providers.h"
+#include <AK/QuickSort.h>
+#include <AK/String.h>
+#include <LibGUI/Application.h>
+#include <LibGUI/BoxLayout.h>
+#include <LibGUI/Event.h>
+#include <LibGUI/Icon.h>
+#include <LibGUI/ImageWidget.h>
+#include <LibGUI/Label.h>
+#include <LibGUI/Painter.h>
+#include <LibGUI/TextBox.h>
+#include <LibGfx/Palette.h>
+#include <LibThreading/Lock.h>
+
+namespace Assistant {
+
+struct AppState {
+    size_t selected_index { 0 };
+    Vector<NonnullRefPtr<Result>> results;
+    size_t visible_result_count { 0 };
+
+    Threading::Lock lock;
+    String last_query;
+};
+
+class ResultRow final : public GUI::Widget {
+    C_OBJECT(ResultRow)
+public:
+    ResultRow()
+    {
+        auto& layout = set_layout<GUI::HorizontalBoxLayout>();
+        layout.set_spacing(12);
+        layout.set_margins({ 4, 4, 4, 4 });
+
+        m_image = add<GUI::ImageWidget>();
+
+        m_label_container = add<GUI::Widget>();
+        m_label_container->set_layout<GUI::VerticalBoxLayout>();
+        m_label_container->set_fixed_height(30);
+
+        m_title = m_label_container->add<GUI::Label>();
+        m_title->set_text_alignment(Gfx::TextAlignment::CenterLeft);
+
+        set_shrink_to_fit(true);
+        set_fill_with_background_color(true);
+        set_global_cursor_tracking(true);
+        set_greedy_for_hits(true);
+    }
+
+    void set_image(RefPtr<Gfx::Bitmap> bitmap)
+    {
+        m_image->set_bitmap(bitmap);
+    }
+    void set_title(String text)
+    {
+        m_title->set_text(move(text));
+    }
+    void set_subtitle(String text)
+    {
+        if (!m_subtitle) {
+            m_subtitle = m_label_container->add<GUI::Label>();
+            m_subtitle->set_text_alignment(Gfx::TextAlignment::CenterLeft);
+        }
+
+        m_subtitle->set_text(move(text));
+    }
+    void set_is_highlighted(bool value)
+    {
+        if (m_is_highlighted == value)
+            return;
+
+        m_is_highlighted = value;
+        m_title->set_font_weight(value ? 700 : 400);
+    }
+
+    Function<void()> on_selected;
+
+private:
+    void mousedown_event(GUI::MouseEvent&) override
+    {
+        set_background_role(ColorRole::MenuBase);
+    }
+
+    void mouseup_event(GUI::MouseEvent&) override
+    {
+        set_background_role(ColorRole::NoRole);
+        on_selected();
+    }
+
+    void enter_event(Core::Event&) override
+    {
+        set_background_role(ColorRole::HoverHighlight);
+    }
+
+    void leave_event(Core::Event&) override
+    {
+        set_background_role(ColorRole::NoRole);
+    }
+
+    RefPtr<GUI::ImageWidget> m_image;
+    RefPtr<GUI::Widget> m_label_container;
+    RefPtr<GUI::Label> m_title;
+    RefPtr<GUI::Label> m_subtitle;
+    bool m_is_highlighted { false };
+};
+
+class Database {
+public:
+    explicit Database(AppState& state)
+        : m_state(state)
+    {
+    }
+
+    Function<void(Vector<NonnullRefPtr<Result>>)> on_new_results;
+
+    void search(String const& query)
+    {
+
+        m_app_provider.query(query, [=, this](auto results) {
+            recv_results(query, results);
+        });
+
+        m_calculator_provider.query(query, [=, this](auto results) {
+            recv_results(query, results);
+        });
+    }
+
+private:
+    void recv_results(String const& query, Vector<NonnullRefPtr<Result>> const& results)
+    {
+        {
+            Threading::Locker db_locker(m_lock);
+            auto it = m_result_cache.find(query);
+            if (it == m_result_cache.end()) {
+                m_result_cache.set(query, {});
+            }
+            it = m_result_cache.find(query);
+
+            for (auto& result : results) {
+                auto found = it->value.find_if([result](auto& other) {
+                    return result->equals(other);
+                });
+
+                if (found.is_end())
+                    it->value.append(result);
+            }
+        }
+
+        Threading::Locker state_locker(m_state.lock);
+        auto new_results = m_result_cache.find(m_state.last_query);
+        if (new_results == m_result_cache.end())
+            return;
+
+        dual_pivot_quick_sort(new_results->value, 0, static_cast<int>(new_results->value.size() - 1), [](auto& a, auto& b) {
+            return a->score() > b->score();
+        });
+
+        on_new_results(new_results->value);
+    }
+
+    AppState& m_state;
+
+    AppProvider m_app_provider;
+    CalculatorProvider m_calculator_provider;
+
+    Threading::Lock m_lock;
+    HashMap<String, Vector<NonnullRefPtr<Result>>> m_result_cache;
+};
+
+}
+
+static constexpr size_t MAX_SEARCH_RESULTS = 6;
+
+int main(int argc, char** argv)
+{
+    if (pledge("stdio recvfd sendfd rpath unix proc exec", nullptr) < 0) {
+        perror("pledge");
+        return 1;
+    }
+
+    auto app = GUI::Application::construct(argc, argv);
+    auto window = GUI::Window::construct();
+
+    Assistant::AppState app_state;
+    Assistant::Database db { app_state };
+
+    auto& container = window->set_main_widget<GUI::Widget>();
+    container.set_fill_with_background_color(true);
+    auto& layout = container.set_layout<GUI::VerticalBoxLayout>();
+    layout.set_margins({ 8, 8, 8, 0 });
+
+    auto& text_box = container.add<GUI::TextBox>();
+    auto& results_container = container.add<GUI::Widget>();
+    auto& results_layout = results_container.set_layout<GUI::VerticalBoxLayout>();
+    results_layout.set_margins({ 0, 10, 0, 10 });
+
+    auto mark_selected_item = [&]() {
+        for (size_t i = 0; i < app_state.visible_result_count; ++i) {
+            auto& row = dynamic_cast<Assistant::ResultRow&>(results_container.child_widgets()[i]);
+            row.set_is_highlighted(i == app_state.selected_index);
+        }
+    };
+
+    text_box.on_change = [&]() {
+        {
+            Threading::Locker locker(app_state.lock);
+            if (app_state.last_query == text_box.text())
+                return;
+
+            app_state.last_query = text_box.text();
+        }
+
+        db.search(text_box.text());
+    };
+    text_box.on_return_pressed = [&]() {
+        app_state.results[app_state.selected_index]->activate();
+        exit(0);
+    };
+    text_box.on_up_pressed = [&]() {
+        if (app_state.selected_index == 0)
+            app_state.selected_index = app_state.visible_result_count - 1;
+        else if (app_state.selected_index > 0)
+            app_state.selected_index -= 1;
+
+        mark_selected_item();
+    };
+    text_box.on_down_pressed = [&]() {
+        if ((app_state.visible_result_count - 1) == app_state.selected_index)
+            app_state.selected_index = 0;
+        else if (app_state.visible_result_count > app_state.selected_index)
+            app_state.selected_index += 1;
+
+        mark_selected_item();
+    };
+    text_box.on_escape_pressed = []() {
+        exit(0);
+    };
+
+    db.on_new_results = [&](auto results) {
+        app_state.selected_index = 0;
+        app_state.results = results;
+        app_state.visible_result_count = min(results.size(), MAX_SEARCH_RESULTS);
+        results_container.remove_all_children();
+
+        for (size_t i = 0; i < app_state.visible_result_count; ++i) {
+            auto result = app_state.results[i];
+            auto& match = results_container.add<Assistant::ResultRow>();
+            match.set_image(result->bitmap());
+            match.set_title(result->title());
+            match.on_selected = [result_copy = result]() {
+                result_copy->activate();
+                exit(0);
+            };
+
+            if (result->kind() == Assistant::Result::Kind::Calculator) {
+                match.set_subtitle("'Enter' will copy to clipboard");
+            }
+        }
+
+        mark_selected_item();
+
+        auto window_height = app_state.visible_result_count * 40 + text_box.height() + 28;
+        window->resize(GUI::Desktop::the().rect().width() / 3, window_height);
+    };
+
+    window->set_frameless(true);
+    window->resize(GUI::Desktop::the().rect().width() / 3, 46);
+    window->center_on_screen();
+    window->move_to(window->x(), window->y() - (GUI::Desktop::the().rect().height() * 0.33));
+    window->show();
+
+    return app->exec();
+}
diff --git a/Userland/Libraries/LibDesktop/AppFile.cpp b/Userland/Libraries/LibDesktop/AppFile.cpp
index dee54d7631..e5f901284c 100644
--- a/Userland/Libraries/LibDesktop/AppFile.cpp
+++ b/Userland/Libraries/LibDesktop/AppFile.cpp
@@ -9,6 +9,9 @@
 #include <LibCore/ConfigFile.h>
 #include <LibCore/DirIterator.h>
 #include <LibDesktop/AppFile.h>
+#include <errno.h>
+#include <serenity.h>
+#include <spawn.h>
 
 namespace Desktop {