テキスト・エディタのインクリメンタル・サーチ

Emacs のインクリメンタル・サーチを真似してみます。 このサーチ法は、 1 文字入力するごとに、 パターンを 1 文字増やしながら同時に文字列を探します。 開始方法は 2 つあります。 isearch-forward (C-s) コマンドで現点から後方への検索を開始し、 isearch-backward (C-r) コマンドで前方への検索を開始します。 どちらにしても、 ISearchDialog のインスタンスを作成してキーボード入力を譲り渡します。 これのクラスは MiniBufferBase の派生クラスで、 tail にキーボード入力を戻すウィンドウを覚えています。 そして、 restart メッセージでインクリメンタル・サーチを開始します。

class ISearchForward < Interactive
  def self.name() :isearch_forward end

  def edit(arg)
    screen.activated_window_push ISearchDialog.new(window)
    minibuffer.restart(:search_forward)
  end
end

class ISearchBackward < Interactive
  def self.name() :isearch_backward end

  def edit(arg)
    screen.activated_window_push ISearchDialog.new(window)
    minibuffer.restart(:search_backward)
  end
end

キーボード入力とエコー領域への表示を ISearchDialog が担当し、 検索の仕組みは ISearchBuffer クラスが提供します。 ISearchBuffer は GapBuffer にインクリメンタル・サーチ機能をつけるためのラッピング・オブジェクトで、 Buffer の isearch 属性になっています。

class Buffer
  attr_reader :content, :isearch
  # 省略

  def initialize(name)
    # 省略
    @content = GapBuffer.new
    @isearch = ISearchBuffer.new(@content)
    # 省略
  end
end

ISearchBuffer は、 被検索バッファを content 属性に、 前に検索したパターンを history インスタンス変数に覚えておきます。 mode 属性は、 検索時用の局所的なモードです。 ここに検索中のコマンドとキー結合を定義しておきます。 restarted 以下の状態変数は、 エコー領域のプロンプトを Emacs 風の記述で表示するために使います。

class ISearchBuffer
  attr_reader :content, :pattern
  attr_accessor :mode

  def initialize(content)
    @content = content
    @mode = nil
    @journal = []
    @pattern = ''
    @history = ''
    @restarted = false
    @failing = false
    @wrapped = false
    @direction = @default = :search_forward
  end

isearch-forward (C-s) コマンドで始めたのか、 それとも isearch-backward (C-r) コマンドで始めたのかを記録して、 Undo (DEL) のためのジャーナリング・リストを空にして、 パターンも空文字列にします。

#@<インクリメンタル・サーチ開始@>=
  def restart(direction)
    @journal.clear
    @pattern.clear
    @restarted, @failing, @wrapped = true, false, false
    @direction = @default = direction
  end

検索の正常終了時に、 入力済みのパターンを @history インスタンス変数に覚えておきます。

#@<検索正常終了@>=
  def ok()
    @history = @pattern.dup
    @journal.clear
    @pattern.clear
  end

Undo (DEL) のためのジャーナリング・リストへ記録するのは、 現点、 パターン長、 3 つのプロンプト表示用状態変数です。

#@<ジャーナリング@>=
  def log(dot)
    @journal << [dot.point, @pattern.size, @failing, @wrapped, @direction]
  end

さて、 C-s C-s のように開始直後に開始時と同じキーをタイプすると、 覚えておいた @history インスタンス変数から入れ直します。 開始直後ではなく既にパターンを入力済みのときに search-repeat (C-s) か search-reverse (C-r) とタイプすると、 パターンを変更せずに再検索をかけます。 パターンが見つかってないときは、 C-s ならバッファの先頭へ戻り、 C-r ならバッファの末尾へ戻ってから再検索をかけます。 先頭や末尾へ戻ったときは wrapped 状態をオンにします。 log は後述するように、 インクリメンタル・サーチ専用のジャーナリング・ログを記録します。

#@<同じパターンで再検索@>=
  def again(dot, direction)
    log(dot)
    if @restarted && @default == direction
      @pattern = @history.dup
    end
    loc = dot.point
    if @failing && @direction == direction
      loc = :search_forward == direction ? 0 : content.size
      @wrapped = true
    end
    dot.point = search(content, loc, dot.point)
    if @failing
      @journal.pop
    end
  end

self-insert-command で文字をタイプすると、 パターンに追加します。 このとき、 追加後もパターンに一致し続けるときは、 一致点を動かしません。 一致しないときは次に一致する座標を探します。 その検索方向はインクリメンタル・サーチを始めたときのものに従います。

#@<パターンに一文字追加@>=
  def insert_char(dot, ch, count)
    log(dot)
    if failing?
      loc = dot.point
    elsif :search_forward == @default
      loc = dot.point - @pattern.size
    else
      loc = dot.point + @pattern.size
    end
    @pattern << ch
    dot.point = search(@default, loc, dot.point)
  end

パターンに追加できるのはキーボード入力からだけでなく、 yank-word (C-w) 一致している箇所の単語の後ろまでをパターンへ取り込むこともできます。 単語は空白で終わるものと決め打ちしています。 パターンへの取り込みは、 単語の終わりまで一度におこなうのではなく、 1 文字ずつ取り込んでいます。 こうすることで、 パターンの末尾の数文字を DEL で削ってタイプし直すことができるようにしています。

#@<現点以後の単語をパターンに取り込み@>=
  def yank_word(dot)
    @restarted = false
    not @failing or return
    loc = content.find_first_in_forward(" \n\t", dot.point, false)
    if dot.point < loc
      a = content[dot.point ... loc].grapheme_clusters
      while ! a.empty?
        log(dot)
        @direction = :search_forward
        @failing = false
        @pattern << a.shift
        dot.point += 1
      end
    end
  end

文字列検索は content に任せます。 search の引数は、 成功時と失敗時の座標を指定し、 どちらかが search の戻り値になります。

#@<パターンを検索@>=
  def search(direction, loc, fail_loc)
    @restarted = false
    @direction = direction
    if ! @pattern.empty? && (loc = content.send(direction, @pattern, loc))
      @failing = false
      loc
    else
      @failing = true
      fail_loc
    end
  end

content 属性は GapBuffer クラスのインスタンスでした。

class GapBuffer
#@<search_forward@>
#@<search_backward@>
  # 省略
end

文字列の検索は力任せ法でやっています。 ギャップの前で探し、 ギャップに重なる分を探し、 ギャップの後を探します。 見つかったら、 一致した文字列の右端の座標を返します。 見つからなかったときは nil を返します。

#@<search_forward@>=
  def search_forward(str, loc)
    not str.empty? or return loc
    gs, ge, gap = @gap_start, @gap_end, @gap_end - @gap_start
    n = self.size
    while true
      j = loc + str.size
      if n - loc < str.size
        return nil
      elsif loc + str.size <= gs
        return j if @data[loc, str.size] == str
      elsif gs <= loc
        return j if @data[loc + gap, str.size] == str
      else
        return j if @data[loc ... gs] + @data[ge ... loc + str.size + gap] == str
      end
      loc += 1
    end
  end

前向き検索も同じです。 一致した文字列の左端の座標を返すのが異なっています。

#@<search_backward@>=
  def search_backward(str, loc)
    not str.empty? or return loc
    gs, ge, gap = @gap_start, @gap_end, @gap_end - @gap_start
    loc = [loc + str.size - 1, self.size].min
    while true
      j = loc - str.size
      if loc < str.size
        return nil
      elsif loc <= gs
        break j if @data[j, str.size] == str
      elsif gs <= j
        break j if @data[j + gap , str.size] == str
      else
        break j if @data[j ... gs] + @data[ge ... loc + gap] == str
      end
      loc -= 1
    end
  end

DEL キーで実行する undo では、 状態変数を一つ前に戻して、 パターンを前の状態へ切り詰めます。

#@<undo@>=
  def undo(dot)
    if ! @journal.empty?
      dot.point, size, @failing, @wrapped, @direction = @journal.pop
      @pattern[size ... @pattern.size] = ''
    end
    @restarted = false
  end

C-g キーは、 途中までパターンと一致していて、 残りが不一致のときは、 一致している分までパターンを入力を巻き戻します。 というのが GNU Emacs のふるまいなのですが、 ここでは横着しているので、 パターンとの一致部分がなくて検索しているときは、 前に一致した文字列の位置へ巻き戻す DEL と同じふるまいをしてしまいます。

#@<パターンの不一致分を巻き戻す@>=
  def clean(dot)
    while ! @journal.empty? && @journal.last[2]
      @journal.pop
    end
    undo(dot)
  end

C-g キーで、 検索が成功しているときは、 検索そのものをおこなわなかったことにして、 検索を開始した座標へ現点を戻します。

#@<検索をなかったものにする@>=
  def revert(dot)
    dot.point = @journal.first[0] if ! @journal.empty?
    @journal.clear
    @pattern.clear
  end

ISearchDialog がプロンプトを組み立てるために状態変数を読めるようにしておきます。

#@<状態変数読み取り@>=
  def failing?()
    @failing
  end

  def wrapped?()
    @wrapped
  end

  def backward?()
    @direction == :search_backward
  end

続いて、 ISearchDialog です。 これは MiniBufferBase の派生クラスです。 buffer の isearch 属性をバッファに指定し、 このオブジェクトでラッピングされた Window を window 属性にしています。 コマンドと isearch とを適切に結びつけて、 isearch の状態変数からプロンプトを作っていきます。

class ISearchDialog < MiniBufferBase
  def initialize(window)
    super
    @inactive = true
    @auto_exit_minibuffer = true
  end

  def buffer() tail.buffer.isearch end
  def window() tail end
  def restart(direction) buffer.restart(direction) end
  def insert_char(ch, count) buffer.insert_char(dot, ch, count) end
  def redisplay_setup() miniwindow.print(prompt, buffer.pattern) end
  def redisplay_teardown() nil end

  def exit_minibuffer()
    buffer.ok()
    miniwindow.clear
    screen.activated_window_pop()
  end

  def abort_recursive_edit()
    if buffer.failing?
      buffer.clean(dot)
    else
      buffer.revert(dot)
      miniwindow.clear
      screen.activated_window_pop()
    end
  end

  def guess_key(command)
    print_key(command)
    screen.redisplay()
    screen.refresh
    activate
  end

  def print_key(command)
    miniwindow.print(prompt, '%s %s' % [buffer.pattern, command])
  end

  def unbound(command)
    miniwindow.print(prompt, '%s (Unbound %s)' % [buffer.pattern, command])
  end

private

  def prompt()
    t = ''
    t << 'Failing ' if buffer.failing?
    t << 'Wrapped ' if buffer.wrapped?
    t << 'I-search'
    t << ' backward' if buffer.backward?
    t << ': '
  end
end