[ruby/reline] Improve key binding match/matching check

(https://github.com/ruby/reline/pull/709)

* Improve key binding match/matching check

* Rename key_actors to default_key_bindings

* Make key_stroke.expand always return a value

* Update add_default_key_binding to use a add_default_key_binding_by_keymap internally

Co-authored-by: Stan Lo <stan001212@gmail.com>

---------

https://github.com/ruby/reline/commit/353ec236e2

Co-authored-by: Stan Lo <stan001212@gmail.com>

10 files changed, 112 insertions, 161 deletions

diff --git a/lib/reline.rb b/lib/reline.rb
index 796e637e85..33a1cfc625 100644
--- a/lib/reline.rb
+++ b/lib/reline.rb
@@ -19,20 +19,10 @@ module Reline
   class ConfigEncodingConversionError < StandardError; end
 
   Key = Struct.new(:char, :combined_char, :with_meta) do
-    def match?(other)
-      case other
-      when Reline::Key
-        (other.char.nil? or char.nil? or char == other.char) and
-        (other.combined_char.nil? or combined_char.nil? or combined_char == other.combined_char) and
-        (other.with_meta.nil? or with_meta.nil? or with_meta == other.with_meta)
-      when Integer, Symbol
-        (combined_char and combined_char == other) or
-        (combined_char.nil? and char and char == other)
-      else
-        false
-      end
+    # For dialog_proc `key.match?(dialog.name)`
+    def match?(sym)
+      combined_char.is_a?(Symbol) && combined_char == sym
     end
-    alias_method :==, :match?
   end
   CursorPos = Struct.new(:x, :y)
   DialogRenderInfo = Struct.new(
@@ -400,9 +390,8 @@ module Reline
         end
         case result
         when :matched
-          expanded = key_stroke.expand(buffer).map{ |expanded_c|
-            Reline::Key.new(expanded_c, expanded_c, false)
-          }
+          expanded, rest_bytes = key_stroke.expand(buffer)
+          rest_bytes.reverse_each { |c| io_gate.ungetc(c) }
           block.(expanded)
           break
         when :matching
@@ -416,9 +405,8 @@ module Reline
           if buffer.size == 1 and c == "\e".ord
             read_escaped_key(keyseq_timeout, c, block)
           else
-            expanded = buffer.map{ |expanded_c|
-              Reline::Key.new(expanded_c, expanded_c, false)
-            }
+            expanded, rest_bytes = key_stroke.expand(buffer)
+            rest_bytes.reverse_each { |c| io_gate.ungetc(c) }
             block.(expanded)
           end
           break
@@ -442,9 +430,8 @@ module Reline
           return :next
         when :matched
           buffer << succ_c
-          expanded = key_stroke.expand(buffer).map{ |expanded_c|
-            Reline::Key.new(expanded_c, expanded_c, false)
-          }
+          expanded, rest_bytes = key_stroke.expand(buffer)
+          rest_bytes.reverse_each { |c| io_gate.ungetc(c) }
           block.(expanded)
           return :break
         end
diff --git a/lib/reline/config.rb b/lib/reline/config.rb
index 62c6d105b3..774b06b6fd 100644
--- a/lib/reline/config.rb
+++ b/lib/reline/config.rb
@@ -29,18 +29,20 @@ class Reline::Config
   attr_accessor :autocompletion
 
   def initialize
-    @additional_key_bindings = {} # from inputrc
-    @additional_key_bindings[:emacs] = {}
-    @additional_key_bindings[:vi_insert] = {}
-    @additional_key_bindings[:vi_command] = {}
-    @oneshot_key_bindings = {}
+    @additional_key_bindings = { # from inputrc
+      emacs: Reline::KeyActor::Base.new,
+      vi_insert: Reline::KeyActor::Base.new,
+      vi_command: Reline::KeyActor::Base.new
+    }
+    @oneshot_key_bindings = Reline::KeyActor::Base.new
     @editing_mode_label = :emacs
     @keymap_label = :emacs
     @keymap_prefix = []
-    @key_actors = {}
-    @key_actors[:emacs] = Reline::KeyActor::Emacs.new
-    @key_actors[:vi_insert] = Reline::KeyActor::ViInsert.new
-    @key_actors[:vi_command] = Reline::KeyActor::ViCommand.new
+    @default_key_bindings = {
+      emacs: Reline::KeyActor::Base.new(Reline::KeyActor::EMACS_MAPPING),
+      vi_insert: Reline::KeyActor::Base.new(Reline::KeyActor::VI_INSERT_MAPPING),
+      vi_command: Reline::KeyActor::Base.new(Reline::KeyActor::VI_COMMAND_MAPPING)
+    }
     @vi_cmd_mode_string = '(cmd)'
     @vi_ins_mode_string = '(ins)'
     @emacs_mode_string = '@'
@@ -62,7 +64,7 @@ class Reline::Config
   end
 
   def editing_mode
-    @key_actors[@editing_mode_label]
+    @default_key_bindings[@editing_mode_label]
   end
 
   def editing_mode=(val)
@@ -74,7 +76,7 @@ class Reline::Config
   end
 
   def keymap
-    @key_actors[@keymap_label]
+    @default_key_bindings[@keymap_label]
   end
 
   def loaded?
@@ -133,14 +135,14 @@ class Reline::Config
 
   def key_bindings
     # The key bindings for each editing mode will be overwritten by the user-defined ones.
-    kb = @key_actors[@editing_mode_label].default_key_bindings.dup
-    kb.merge!(@additional_key_bindings[@editing_mode_label])
-    kb.merge!(@oneshot_key_bindings)
-    kb
+    Reline::KeyActor::Composite.new([@oneshot_key_bindings, @additional_key_bindings[@editing_mode_label], @default_key_bindings[@editing_mode_label]])
   end
 
   def add_oneshot_key_binding(keystroke, target)
-    @oneshot_key_bindings[keystroke] = target
+    # IRB sets invalid keystroke [Reline::Key]. We should ignore it.
+    return unless keystroke.all? { |c| c.is_a?(Integer) }
+
+    @oneshot_key_bindings.add(keystroke, target)
   end
 
   def reset_oneshot_key_bindings
@@ -148,11 +150,11 @@ class Reline::Config
   end
 
   def add_default_key_binding_by_keymap(keymap, keystroke, target)
-    @key_actors[keymap].default_key_bindings[keystroke] = target
+    @default_key_bindings[keymap].add(keystroke, target)
   end
 
   def add_default_key_binding(keystroke, target)
-    @key_actors[@keymap_label].default_key_bindings[keystroke] = target
+    add_default_key_binding_by_keymap(@keymap_label, keystroke, target)
   end
 
   def read_lines(lines, file = nil)
@@ -192,7 +194,7 @@ class Reline::Config
         func_name = func_name.split.first
         keystroke, func = bind_key(key, func_name)
         next unless keystroke
-        @additional_key_bindings[@keymap_label][@keymap_prefix + keystroke] = func
+        @additional_key_bindings[@keymap_label].add(@keymap_prefix + keystroke, func)
       end
     end
     unless if_stack.empty?
diff --git a/lib/reline/key_actor.rb b/lib/reline/key_actor.rb
index ebe09d2009..0ac7604556 100644
--- a/lib/reline/key_actor.rb
+++ b/lib/reline/key_actor.rb
@@ -2,6 +2,7 @@ module Reline::KeyActor
 end
 
 require 'reline/key_actor/base'
+require 'reline/key_actor/composite'
 require 'reline/key_actor/emacs'
 require 'reline/key_actor/vi_command'
 require 'reline/key_actor/vi_insert'
diff --git a/lib/reline/key_actor/base.rb b/lib/reline/key_actor/base.rb
index 194e98938c..ee28c7681e 100644
--- a/lib/reline/key_actor/base.rb
+++ b/lib/reline/key_actor/base.rb
@@ -1,15 +1,31 @@
 class Reline::KeyActor::Base
-  MAPPING = Array.new(256)
+  def initialize(mapping = [])
+    @mapping = mapping
+    @matching_bytes = {}
+    @key_bindings = {}
+  end
 
   def get_method(key)
-    self.class::MAPPING[key]
+    @mapping[key]
+  end
+
+  def add(key, func)
+    (1...key.size).each do |size|
+      @matching_bytes[key.take(size)] = true
+    end
+    @key_bindings[key] = func
+  end
+
+  def matching?(key)
+    @matching_bytes[key]
   end
 
-  def initialize
-    @default_key_bindings = {}
+  def get(key)
+    @key_bindings[key]
   end
 
-  def default_key_bindings
-    @default_key_bindings
+  def clear
+    @matching_bytes.clear
+    @key_bindings.clear
   end
 end
diff --git a/lib/reline/key_actor/composite.rb b/lib/reline/key_actor/composite.rb
new file mode 100644
index 0000000000..37e94ce6cf
--- /dev/null
+++ b/lib/reline/key_actor/composite.rb
@@ -0,0 +1,17 @@
+class Reline::KeyActor::Composite
+  def initialize(key_actors)
+    @key_actors = key_actors
+  end
+
+  def matching?(key)
+    @key_actors.any? { |key_actor| key_actor.matching?(key) }
+  end
+
+  def get(key)
+    @key_actors.each do |key_actor|
+      func = key_actor.get(key)
+      return func if func
+    end
+    nil
+  end
+end
diff --git a/lib/reline/key_actor/emacs.rb b/lib/reline/key_actor/emacs.rb
index d7354520b0..ad84ee1d99 100644
--- a/lib/reline/key_actor/emacs.rb
+++ b/lib/reline/key_actor/emacs.rb
@@ -1,5 +1,5 @@
-class Reline::KeyActor::Emacs < Reline::KeyActor::Base
-  MAPPING = [
+module Reline::KeyActor
+  EMACS_MAPPING = [
     #   0 ^@
     :em_set_mark,
     #   1 ^A
diff --git a/lib/reline/key_actor/vi_command.rb b/lib/reline/key_actor/vi_command.rb
index 06bb0ba8e4..d972c5e67f 100644
--- a/lib/reline/key_actor/vi_command.rb
+++ b/lib/reline/key_actor/vi_command.rb
@@ -1,5 +1,5 @@
-class Reline::KeyActor::ViCommand < Reline::KeyActor::Base
-  MAPPING = [
+module Reline::KeyActor
+  VI_COMMAND_MAPPING = [
     #   0 ^@
     :ed_unassigned,
     #   1 ^A
diff --git a/lib/reline/key_actor/vi_insert.rb b/lib/reline/key_actor/vi_insert.rb
index f8ccf468c6..312df1646b 100644
--- a/lib/reline/key_actor/vi_insert.rb
+++ b/lib/reline/key_actor/vi_insert.rb
@@ -1,5 +1,5 @@
-class Reline::KeyActor::ViInsert < Reline::KeyActor::Base
-  MAPPING = [
+module Reline::KeyActor
+  VI_INSERT_MAPPING = [
     #   0 ^@
     :ed_unassigned,
     #   1 ^A
diff --git a/lib/reline/key_stroke.rb b/lib/reline/key_stroke.rb
index bceffbb53f..419ddd8cea 100644
--- a/lib/reline/key_stroke.rb
+++ b/lib/reline/key_stroke.rb
@@ -7,139 +7,69 @@ class Reline::KeyStroke
     @config = config
   end
 
-  def compress_meta_key(ary)
-    return ary unless @config.convert_meta
-    ary.inject([]) { |result, key|
-      if result.size > 0 and result.last == "\e".ord
-        result[result.size - 1] = Reline::Key.new(key, key | 0b10000000, true)
-      else
-        result << key
-      end
-      result
-    }
-  end
-
-  def start_with?(me, other)
-    compressed_me = compress_meta_key(me)
-    compressed_other = compress_meta_key(other)
-    i = 0
-    loop do
-      my_c = compressed_me[i]
-      other_c = compressed_other[i]
-      other_is_last = (i + 1) == compressed_other.size
-      me_is_last = (i + 1) == compressed_me.size
-      if my_c != other_c
-        if other_c == "\e".ord and other_is_last and my_c.is_a?(Reline::Key) and my_c.with_meta
-          return true
-        else
-          return false
-        end
-      elsif other_is_last
-        return true
-      elsif me_is_last
-        return false
-      end
-      i += 1
-    end
-  end
-
-  def equal?(me, other)
-    case me
-    when Array
-      compressed_me = compress_meta_key(me)
-      compressed_other = compress_meta_key(other)
-      compressed_me.size == compressed_other.size and [compressed_me, compressed_other].transpose.all?{ |i| equal?(i[0], i[1]) }
-    when Integer
-      if other.is_a?(Reline::Key)
-        if other.combined_char == "\e".ord
-          false
-        else
-          other.combined_char == me
-        end
-      else
-        me == other
-      end
-    when Reline::Key
-      if other.is_a?(Integer)
-        me.combined_char == other
-      else
-        me == other
-      end
-    end
-  end
-
   def match_status(input)
-    key_mapping.keys.select { |lhs|
-      start_with?(lhs, input)
-    }.tap { |it|
-      return :matched  if it.size == 1 && equal?(it[0], input)
-      return :matching if it.size == 1 && !equal?(it[0], input)
-      return :matched  if it.max_by(&:size)&.size&.< input.size
-      return :matching if it.size > 1
-    }
-    if key_mapping.keys.any? { |lhs| start_with?(input, lhs) }
+    if key_mapping.matching?(input)
+      :matching
+    elsif key_mapping.get(input)
+      :matched
+    elsif input[0] == ESC_BYTE
+      match_unknown_escape_sequence(input, vi_mode: @config.editing_mode_is?(:vi_insert, :vi_command))
+    elsif input.size == 1
       :matched
     else
-      match_unknown_escape_sequence(input).first
+      :unmatched
     end
   end
 
   def expand(input)
-    lhs = key_mapping.keys.select { |item| start_with?(input, item) }.sort_by(&:size).last
-    unless lhs
-      status, size = match_unknown_escape_sequence(input)
-      case status
-      when :matched
-        return [:ed_unassigned] + expand(input.drop(size))
-      when :matching
-        return [:ed_unassigned]
-      else
-        return input
-      end
+    matched_bytes = nil
+    (1..input.size).each do |i|
+      bytes = input.take(i)
+      matched_bytes = bytes if match_status(bytes) != :unmatched
     end
-    rhs = key_mapping[lhs]
+    return [[], []] unless matched_bytes
 
-    case rhs
-    when String
-      rhs_bytes = rhs.bytes
-      expand(expand(rhs_bytes) + expand(input.drop(lhs.size)))
-    when Symbol
-      [rhs] + expand(input.drop(lhs.size))
-    when Array
-      rhs
+    func = key_mapping.get(matched_bytes)
+    if func.is_a?(Array)
+      keys = func.map { |c| Reline::Key.new(c, c, false) }
+    elsif func
+      keys = [Reline::Key.new(func, func, false)]
+    elsif matched_bytes.size == 1
+      keys = [Reline::Key.new(matched_bytes.first, matched_bytes.first, false)]
+    elsif matched_bytes.size == 2 && matched_bytes[0] == ESC_BYTE
+      keys = [Reline::Key.new(matched_bytes[1], matched_bytes[1] | 0b10000000, true)]
+    else
+      keys = []
     end
+
+    [keys, input.drop(matched_bytes.size)]
   end
 
   private
 
   # returns match status of CSI/SS3 sequence and matched length
-  def match_unknown_escape_sequence(input)
+  def match_unknown_escape_sequence(input, vi_mode: false)
     idx = 0
-    return [:unmatched, nil] unless input[idx] == ESC_BYTE
+    return :unmatched unless input[idx] == ESC_BYTE
     idx += 1
     idx += 1 if input[idx] == ESC_BYTE
 
     case input[idx]
     when nil
-      return [:matching, nil]
+      return :matching
     when 91 # == '['.ord
-      # CSI sequence
+      # CSI sequence `ESC [ ... char`
       idx += 1
       idx += 1 while idx < input.size && CSI_PARAMETER_BYTES_RANGE.cover?(input[idx])
       idx += 1 while idx < input.size && CSI_INTERMEDIATE_BYTES_RANGE.cover?(input[idx])
-      input[idx] ? [:matched, idx + 1] : [:matching, nil]
     when 79 # == 'O'.ord
-      # SS3 sequence
-      input[idx + 1] ? [:matched, idx + 2] : [:matching, nil]
+      # SS3 sequence `ESC O char`
+      idx += 1
     else
-      if idx == 1
-        # `ESC char`, make it :unmatched so that it will be handled correctly in `read_2nd_character_of_key_sequence`
-        [:unmatched, nil]
-      else
-        # `ESC ESC char`
-        [:matched, idx + 1]
-      end
+      # `ESC char` or `ESC ESC char`
+      return :unmatched if vi_mode
     end
+    input[idx + 1] ? :unmatched : input[idx] ? :matched : :matching
   end
 
   def key_mapping
diff --git a/lib/reline/line_editor.rb b/lib/reline/line_editor.rb
index c2f5f0622e..6038d8a4fa 100644
--- a/lib/reline/line_editor.rb
+++ b/lib/reline/line_editor.rb
@@ -684,10 +684,8 @@ class Reline::LineEditor
           @trap_key.each do |t|
             @config.add_oneshot_key_binding(t, @name)
           end
-        elsif @trap_key.is_a?(Array)
+        else
           @config.add_oneshot_key_binding(@trap_key, @name)
-        elsif @trap_key.is_a?(Integer) or @trap_key.is_a?(Reline::Key)
-          @config.add_oneshot_key_binding([@trap_key], @name)
         end
       end
       dialog_render_info