LibLine: Support multi-character key callbacks

5 files changed, 259 insertions, 89 deletions

diff --git a/Libraries/LibLine/CMakeLists.txt b/Libraries/LibLine/CMakeLists.txt
index 2c37e87e1e..41da2dee0b 100644
--- a/Libraries/LibLine/CMakeLists.txt
+++ b/Libraries/LibLine/CMakeLists.txt
@@ -1,6 +1,7 @@
 set(SOURCES
     Editor.cpp
     InternalFunctions.cpp
+    KeyCallbackMachine.cpp
     SuggestionManager.cpp
     XtermSuggestionDisplay.cpp
 )
diff --git a/Libraries/LibLine/Editor.cpp b/Libraries/LibLine/Editor.cpp
index a5955ba8e7..bd97454e76 100644
--- a/Libraries/LibLine/Editor.cpp
+++ b/Libraries/LibLine/Editor.cpp
@@ -80,9 +80,9 @@ Configuration Configuration::from_config(const StringView& libname)
         GenericLexer key_lexer(binding_key);
         auto has_ctrl = false;
         auto alt = false;
-        unsigned key = 0;
+        Vector<Key> keys;
 
-        while (!key && !key_lexer.is_eof()) {
+        while (!key_lexer.is_eof()) {
             if (key_lexer.next_is("alt+")) {
                 alt = key_lexer.consume_specific("alt+");
                 continue;
@@ -100,21 +100,24 @@ Configuration Configuration::from_config(const StringView& libname)
                 continue;
             }
             // FIXME: Support utf?
-            key = key_lexer.consume();
-        }
+            unsigned key = key_lexer.consume();
+            if (has_ctrl)
+                key = ctrl(key);
 
-        if (has_ctrl)
-            key = ctrl(key);
+            keys.append(Key { key, alt ? Key::Alt : Key::None });
+            alt = false;
+            has_ctrl = false;
+        }
 
         auto value = config_file->read_entry("keybinds", binding_key);
         if (value.starts_with("internal:")) {
             configuration.set(KeyBinding {
-                Key { key, alt ? Key::Alt : Key::None },
+                keys,
                 KeyBinding::Kind::InternalFunction,
                 value.substring(9, value.length() - 9) });
         } else {
             configuration.set(KeyBinding {
-                Key { key, alt ? Key::Alt : Key::None },
+                keys,
                 KeyBinding::Kind::Insertion,
                 value });
         }
@@ -146,16 +149,16 @@ void Editor::set_default_keybinds()
     register_key_input_callback('\n', EDITOR_INTERNAL_FUNCTION(finish));
 
     // ^[.: alt-.: insert last arg of previous command (similar to `!$`)
-    register_key_input_callback({ '.', Key::Alt }, EDITOR_INTERNAL_FUNCTION(insert_last_words));
-    register_key_input_callback({ 'b', Key::Alt }, EDITOR_INTERNAL_FUNCTION(cursor_left_word));
-    register_key_input_callback({ 'f', Key::Alt }, EDITOR_INTERNAL_FUNCTION(cursor_right_word));
+    register_key_input_callback(Key { '.', Key::Alt }, EDITOR_INTERNAL_FUNCTION(insert_last_words));
+    register_key_input_callback(Key { 'b', Key::Alt }, EDITOR_INTERNAL_FUNCTION(cursor_left_word));
+    register_key_input_callback(Key { 'f', Key::Alt }, EDITOR_INTERNAL_FUNCTION(cursor_right_word));
     // ^[^H: alt-backspace: backward delete word
-    register_key_input_callback({ '\b', Key::Alt }, EDITOR_INTERNAL_FUNCTION(erase_alnum_word_backwards));
-    register_key_input_callback({ 'd', Key::Alt }, EDITOR_INTERNAL_FUNCTION(erase_alnum_word_forwards));
-    register_key_input_callback({ 'c', Key::Alt }, EDITOR_INTERNAL_FUNCTION(capitalize_word));
-    register_key_input_callback({ 'l', Key::Alt }, EDITOR_INTERNAL_FUNCTION(lowercase_word));
-    register_key_input_callback({ 'u', Key::Alt }, EDITOR_INTERNAL_FUNCTION(uppercase_word));
-    register_key_input_callback({ 't', Key::Alt }, EDITOR_INTERNAL_FUNCTION(transpose_words));
+    register_key_input_callback(Key { '\b', Key::Alt }, EDITOR_INTERNAL_FUNCTION(erase_alnum_word_backwards));
+    register_key_input_callback(Key { 'd', Key::Alt }, EDITOR_INTERNAL_FUNCTION(erase_alnum_word_forwards));
+    register_key_input_callback(Key { 'c', Key::Alt }, EDITOR_INTERNAL_FUNCTION(capitalize_word));
+    register_key_input_callback(Key { 'l', Key::Alt }, EDITOR_INTERNAL_FUNCTION(lowercase_word));
+    register_key_input_callback(Key { 'u', Key::Alt }, EDITOR_INTERNAL_FUNCTION(uppercase_word));
+    register_key_input_callback(Key { 't', Key::Alt }, EDITOR_INTERNAL_FUNCTION(transpose_words));
 }
 
 Editor::Editor(Configuration configuration)
@@ -253,20 +256,15 @@ void Editor::register_key_input_callback(const KeyBinding& binding)
             dbg() << "LibLine: Unknown internal function '" << binding.binding << "'";
             return;
         }
-        return register_key_input_callback(binding.key, move(internal_function));
+        return register_key_input_callback(binding.keys, move(internal_function));
     }
 
-    return register_key_input_callback(binding.key, [binding = String(binding.binding)](auto& editor) {
+    return register_key_input_callback(binding.keys, [binding = String(binding.binding)](auto& editor) {
         editor.insert(binding);
         return false;
     });
 }
 
-void Editor::register_key_input_callback(Key key, Function<bool(Editor&)> callback)
-{
-    m_key_callbacks.set(key, make<KeyCallback>(move(callback)));
-}
-
 static size_t code_point_length_in_utf8(u32 code_point)
 {
     if (code_point <= 0x7f)
@@ -556,13 +554,9 @@ void Editor::handle_interrupt_event()
 {
     m_was_interrupted = false;
 
-    auto cb = m_key_callbacks.get(ctrl('C'));
-    if (cb.has_value()) {
-        if (!cb.value()->callback(*this)) {
-            // Oh well.
-            return;
-        }
-    }
+    m_callback_machine.interrupted(*this);
+    if (!m_callback_machine.should_process_last_pressed_key())
+        return;
 
     fprintf(stderr, "^C");
     fflush(stderr);
@@ -657,12 +651,7 @@ void Editor::handle_read_event()
                 continue;
             default: {
                 m_state = InputState::Free;
-                auto cb = m_key_callbacks.get({ code_point, Key::Alt });
-                if (cb.has_value()) {
-                    if (!cb.value()->callback(*this)) {
-                        // There's nothing interesting to do here.
-                    }
-                }
+                m_callback_machine.key_pressed(*this, { code_point, Key::Alt });
                 cleanup_suggestions();
                 continue;
             }
@@ -772,12 +761,10 @@ void Editor::handle_read_event()
             continue;
         }
 
-        auto cb = m_key_callbacks.get(code_point);
-        if (cb.has_value()) {
-            if (!cb.value()->callback(*this)) {
-                continue;
-            }
-        }
+        m_callback_machine.key_pressed(*this, code_point);
+        if (!m_callback_machine.should_process_last_pressed_key())
+            continue;
+
         m_search_offset = 0; // reset search offset on any key
 
         if (code_point == '\t' || reverse_tab) {
diff --git a/Libraries/LibLine/Editor.h b/Libraries/LibLine/Editor.h
index efd7762340..076acdc830 100644
--- a/Libraries/LibLine/Editor.h
+++ b/Libraries/LibLine/Editor.h
@@ -41,6 +41,7 @@
 #include <LibCore/DirIterator.h>
 #include <LibCore/Notifier.h>
 #include <LibCore/Object.h>
+#include <LibLine/KeyCallbackMachine.h>
 #include <LibLine/Span.h>
 #include <LibLine/StringMetrics.h>
 #include <LibLine/Style.h>
@@ -53,33 +54,8 @@
 
 namespace Line {
 
-struct Key {
-    enum Modifier : int {
-        None = 0,
-        Alt = 1,
-    };
-
-    int modifiers { None };
-    unsigned key { 0 };
-
-    Key(unsigned c)
-        : modifiers(None)
-        , key(c) {};
-
-    Key(unsigned c, int modifiers)
-        : modifiers(modifiers)
-        , key(c)
-    {
-    }
-
-    bool operator==(const Key& other) const
-    {
-        return other.key == key && other.modifiers == modifiers;
-    }
-};
-
 struct KeyBinding {
-    Key key;
+    Vector<Key> keys;
     enum class Kind {
         InternalFunction,
         Insertion,
@@ -171,7 +147,8 @@ public:
     const Vector<String>& history() const { return m_history; }
 
     void register_key_input_callback(const KeyBinding&);
-    void register_key_input_callback(Key, Function<bool(Editor&)> callback);
+    void register_key_input_callback(Vector<Key> keys, Function<bool(Editor&)> callback) { m_callback_machine.register_key_input_callback(move(keys), move(callback)); }
+    void register_key_input_callback(Key key, Function<bool(Editor&)> callback) { register_key_input_callback(Vector<Key> { key }, move(callback)); }
 
     static StringMetrics actual_rendered_string_metrics(const StringView&);
     static StringMetrics actual_rendered_string_metrics(const Utf32View&);
@@ -283,14 +260,6 @@ private:
     // FIXME: Port to Core::Property
     void save_to(JsonObject&);
 
-    struct KeyCallback {
-        KeyCallback(Function<bool(Editor&)> cb)
-            : callback(move(cb))
-        {
-        }
-        Function<bool(Editor&)> callback;
-    };
-
     void handle_interrupt_event();
     void handle_read_event();
 
@@ -460,7 +429,7 @@ private:
     };
     TabDirection m_tab_direction { TabDirection::Forward };
 
-    HashMap<Key, NonnullOwnPtr<KeyCallback>> m_key_callbacks;
+    KeyCallbackMachine m_callback_machine;
 
     struct termios m_termios {
     };
@@ -500,13 +469,3 @@ private:
 };
 
 }
-
-namespace AK {
-
-template<>
-struct Traits<Line::Key> : public GenericTraits<Line::Key> {
-    static constexpr bool is_trivial() { return true; }
-    static unsigned hash(Line::Key k) { return pair_int_hash(k.key, k.modifiers); }
-};
-
-}
diff --git a/Libraries/LibLine/KeyCallbackMachine.cpp b/Libraries/LibLine/KeyCallbackMachine.cpp
new file mode 100644
index 0000000000..5679d098d9
--- /dev/null
+++ b/Libraries/LibLine/KeyCallbackMachine.cpp
@@ -0,0 +1,111 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <LibLine/Editor.h>
+
+namespace {
+constexpr u32 ctrl(char c) { return c & 0x3f; }
+}
+
+namespace Line {
+
+void KeyCallbackMachine::register_key_input_callback(Vector<Key> keys, Function<bool(Editor&)> callback)
+{
+    m_key_callbacks.set(keys, make<KeyCallback>(move(callback)));
+}
+
+void KeyCallbackMachine::key_pressed(Editor& editor, Key key)
+{
+#ifdef CALLBACK_MACHINE_DEBUG
+    dbgln("Key<{}, {}> pressed, seq_length={}, {} things in the matching vector", key.key, key.modifiers, m_sequence_length, m_current_matching_keys.size());
+#endif
+    if (m_sequence_length == 0) {
+        ASSERT(m_current_matching_keys.is_empty());
+
+        for (auto& it : m_key_callbacks) {
+            if (it.key.first() == key)
+                m_current_matching_keys.append(it.key);
+        }
+
+        if (m_current_matching_keys.is_empty()) {
+            m_should_process_this_key = true;
+            return;
+        }
+    }
+
+    ++m_sequence_length;
+    Vector<Vector<Key>> old_macthing_keys;
+    swap(m_current_matching_keys, old_macthing_keys);
+
+    for (auto& okey : old_macthing_keys) {
+        if (okey.size() < m_sequence_length)
+            continue;
+
+        if (okey[m_sequence_length - 1] == key)
+            m_current_matching_keys.append(okey);
+    }
+
+    if (m_current_matching_keys.is_empty()) {
+        // Insert any keys that were captured
+        if (!old_macthing_keys.is_empty()) {
+            auto& keys = old_macthing_keys.first();
+            for (size_t i = 0; i < m_sequence_length - 1; ++i)
+                editor.insert(keys[i].key);
+        }
+        m_sequence_length = 0;
+        m_should_process_this_key = true;
+        return;
+    }
+
+#ifdef CALLBACK_MACHINE_DEBUG
+    dbgln("seq_length={}, matching vector:", m_sequence_length);
+    for (auto& key : m_current_matching_keys) {
+        for (auto& k : key)
+            dbgln("    {}, {}", k.key, k.modifiers);
+        dbgln("");
+    }
+#endif
+
+    m_should_process_this_key = false;
+    for (auto& key : m_current_matching_keys) {
+        if (key.size() == m_sequence_length) {
+            m_should_process_this_key = m_key_callbacks.get(key).value()->callback(editor);
+            m_sequence_length = 0;
+            m_current_matching_keys.clear();
+            return;
+        }
+    }
+}
+
+void KeyCallbackMachine::interrupted(Editor& editor)
+{
+    m_sequence_length = 0;
+    m_current_matching_keys.clear();
+    if (auto callback = m_key_callbacks.get({ ctrl('C') }); callback.has_value())
+        m_should_process_this_key = callback.value()->callback(editor);
+}
+
+}
diff --git a/Libraries/LibLine/KeyCallbackMachine.h b/Libraries/LibLine/KeyCallbackMachine.h
new file mode 100644
index 0000000000..b0689904e8
--- /dev/null
+++ b/Libraries/LibLine/KeyCallbackMachine.h
@@ -0,0 +1,112 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/Function.h>
+#include <AK/HashMap.h>
+#include <AK/String.h>
+#include <AK/Vector.h>
+
+namespace Line {
+
+class Editor;
+
+struct Key {
+    enum Modifier : int {
+        None = 0,
+        Alt = 1,
+    };
+
+    int modifiers { None };
+    unsigned key { 0 };
+
+    Key(unsigned c)
+        : modifiers(None)
+        , key(c) {};
+
+    Key(unsigned c, int modifiers)
+        : modifiers(modifiers)
+        , key(c)
+    {
+    }
+
+    bool operator==(const Key& other) const
+    {
+        return other.key == key && other.modifiers == modifiers;
+    }
+
+    bool operator!=(const Key& other) const
+    {
+        return !(*this == other);
+    }
+};
+
+struct KeyCallback {
+    KeyCallback(Function<bool(Editor&)> cb)
+        : callback(move(cb))
+    {
+    }
+    Function<bool(Editor&)> callback;
+};
+
+class KeyCallbackMachine {
+public:
+    void register_key_input_callback(Vector<Key>, Function<bool(Editor&)> callback);
+    void key_pressed(Editor&, Key);
+    void interrupted(Editor&);
+    bool should_process_last_pressed_key() const { return m_should_process_this_key; }
+
+private:
+    HashMap<Vector<Key>, NonnullOwnPtr<KeyCallback>> m_key_callbacks;
+    Vector<Vector<Key>> m_current_matching_keys;
+    size_t m_sequence_length { 0 };
+    bool m_should_process_this_key { true };
+};
+
+}
+
+namespace AK {
+
+template<>
+struct Traits<Line::Key> : public GenericTraits<Line::Key> {
+    static constexpr bool is_trivial() { return true; }
+    static unsigned hash(Line::Key k) { return pair_int_hash(k.key, k.modifiers); }
+};
+
+template<>
+struct Traits<Vector<Line::Key>> : public GenericTraits<Vector<Line::Key>> {
+    static constexpr bool is_trivial() { return false; }
+    static unsigned hash(const Vector<Line::Key>& ks)
+    {
+        unsigned h = 0;
+        for (auto& k : ks)
+            h ^= Traits<Line::Key>::hash(k);
+        return h;
+    }
+};
+
+}