fzf/fzf

#!/usr/bin/env ruby
# encoding: utf-8
#
#     ____      ____
#    / __/___  / __/
#   / /_/_  / / /_
#  / __/ / /_/ __/
# /_/   /___/_/    Fuzzy finder for your shell
#
# URL:         https://github.com/junegunn/fzf
# Author:      Junegunn Choi
# License:     MIT
# Last update: November 17, 2013
#
# Copyright (c) 2013 Junegunn Choi
#
# MIT License
#
# Permission is hereby granted, free of charge, to any person obtaining
# a copy of this software and associated documentation files (the
# "Software"), to deal in the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, sublicense, and/or sell copies of the Software, and to
# permit persons to whom the Software is furnished to do so, subject to
# the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
# LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
# OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
# WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

require 'thread'
require 'curses'
require 'set'

class FZF
  C = Curses
  attr_reader :rxflag, :sort, :color, :multi

  class AtomicVar
    def initialize value
      @value = value
      @mutex = Mutex.new
    end

    def get
      @mutex.synchronize { @value }
    end

    def set value = nil
      if block_given?
        @mutex.synchronize { @value = yield @value }
      else
        @mutex.synchronize { @value = value }
      end
    end

    def method_missing sym, *args, &blk
      @mutex.synchronize { @value.send(sym, *args, &blk) }
    end
  end

  def initialize argv, source = $stdin
    usage 0 unless (%w[--help -h] & argv).empty?
    @rxflag = argv.delete('+i') ? 0 : Regexp::IGNORECASE
    @sort   = %w[+s --no-sort].map   { |e| argv.delete e }.compact.empty? ?
      ENV.fetch('FZF_DEFAULT_SORT', 1000).to_i : nil
    @color  = %w[+c --no-color].map  { |e| argv.delete e }.compact.empty?
    @multi  = !%w[-m --multi].map    { |e| argv.delete e }.compact.empty?
    @xmode  = !%w[-x --extended].map { |e| argv.delete e }.compact.empty?
    rest    = argv.join ' '
    if sort = rest.match(/(-s|--sort=?) ?([0-9]+)/)
      usage 1 unless @sort
      @sort = sort[2].to_i
      rest  = rest.delete sort[0]
    end
    usage 1 unless rest.empty?

    @source   = source
    @mtx      = Mutex.new
    @cv       = ConditionVariable.new
    @events   = {}
    @new      = []
    @queue    = Queue.new
    @cursor_x = AtomicVar.new(0)
    @query    = AtomicVar.new('')
    @matches  = AtomicVar.new([])
    @count    = AtomicVar.new(0)
    @vcursor  = AtomicVar.new(0)
    @vcursors = AtomicVar.new(Set.new)
    @spinner  = AtomicVar.new('-\|/-\|/'.split(//))
    @selects  = AtomicVar.new({}) # ordered >= 1.9
    @main     = Thread.current
    @stdout   = $stdout.clone
    @plcount  = 0
  end

  def start
    $stdout.reopen($stderr)

    init_screen
    start_reader
    start_renderer
    start_search
    start_loop
  end

  def usage x
    $stderr.puts %[usage: fzf [options]

    -m, --multi      Enable multi-select
    -x, --extended   Extended-search mode
    -s, --sort=MAX   Maximum number of matched items to sort. Default: 1000
    +s, --no-sort    Do not sort the result. Keep the sequence unchanged.
    +i               Case-sensitive match
    +c, --no-color   Disable colors]
    exit x
  end

  case RUBY_PLATFORM
  when /darwin/
    module UConv
      CHOSUNG   = 0x1100
      JUNGSUNG  = 0x1161
      JONGSUNG  = 0x11A7
      CHOSUNGS  = 19
      JUNGSUNGS = 21
      JONGSUNGS = 28
      JJCOUNT   = JUNGSUNGS * JONGSUNGS
      NFC_BEGIN = 0xAC00
      NFC_END   = NFC_BEGIN + CHOSUNGS * JUNGSUNGS * JONGSUNGS

      def self.nfd str
        str.split(//).map do |c|
          cp = c.ord
          if cp >= NFC_BEGIN && cp < NFC_END
            chr = ''
            idx  = cp - NFC_BEGIN
            cho  = CHOSUNG  + idx / JJCOUNT
            jung = JUNGSUNG + (idx % JJCOUNT) / JONGSUNGS
            jong = JONGSUNG + idx % JONGSUNGS
            chr << cho << jung
            chr << jong if jong != JONGSUNG
            chr
          else
            c
          end
        end
      end

      def self.to_nfc arr
        [NFC_BEGIN + arr[0] * JJCOUNT +
         (arr[1] || 0) * JONGSUNGS +
         (arr[2] || 0)].pack('U*')
      end

      if String.method_defined?(:each_char)
        def self.split str
          str.each_char.to_a
        end
      else
        def self.split str
          str.split('')
        end
      end

      def self.nfc str, offsets = []
        ret  = ''
        omap = []
        pend = []
        split(str).each_with_index do |c, idx|
          cp =
            begin
              c.ord
            rescue Exception
              next
            end
          omap << ret.length
          unless pend.empty?
            if cp >= JUNGSUNG && cp < JUNGSUNG + JUNGSUNGS
              pend << cp - JUNGSUNG
              next
            elsif cp >= JONGSUNG && cp < JONGSUNG + JONGSUNGS
              pend << cp - JONGSUNG
              next
            else
              omap[-1] = omap[-1] + 1
              ret << to_nfc(pend)
              pend.clear
            end
          end
          if cp >= CHOSUNG && cp < CHOSUNG + CHOSUNGS
            pend << cp - CHOSUNG
          else
            ret << c
          end
        end
        ret << to_nfc(pend) unless pend.empty?
        return [ret,
                offsets.map { |pair|
                  b, e = pair
                  [omap[b] || 0, omap[e] || ((omap.last || 0) + 1)] }]
      end
    end

    def convert_item item
      UConv.nfc(*item)
    end

    class Matcher
      def query_chars q
        UConv.nfd(q)
      end

      def sanitize q
        UConv.nfd(q).join
      end
    end
  else
    def convert_item item
      item
    end

    class Matcher
      def query_chars q
        q.split(//)
      end

      def sanitize q
        q
      end
    end
  end

  def emit event
    @mtx.synchronize do
      @events[event] = yield
      @cv.broadcast
    end
  end

  def max_items; C.lines - 2; end
  def cursor_y;  C.lines - 1; end
  def cprint str, col
    C.attron(col) do
      addstr_safe str
    end if str
  end
  def addstr_safe str
    C.addstr str.gsub("\0", '')
  end

  def print_input
    C.setpos cursor_y, 0
    C.clrtoeol
    cprint '> ', color(:prompt, true)
    C.attron(C::A_BOLD) do
      C.addstr @query.get
    end
  end

  def print_info msg = nil
    C.setpos cursor_y - 1, 0
    C.clrtoeol
    prefix =
      if spinner = @spinner.first
        cprint spinner, color(:spinner, true)
        ' '
      else
        '  '
      end
    C.attron color(:info, false) do
      C.addstr "#{prefix}#{@matches.length}/#{@count.get}"
      if (selected = @selects.length) > 0
        C.addstr " (#{selected})"
      end
      C.addstr msg if msg
    end
  end

  def refresh
    C.setpos cursor_y, 2 + width(@query[0, @cursor_x.get])
    C.refresh
  end

  def ctrl char
    char.to_s.ord - 'a'.ord + 1
  end

  def format line, limit, offsets
    offsets ||= []
    maxe = offsets.map { |e| e.last }.max || 0

    # Overflow
    if width(line) > limit
      ewidth = width(line[0...maxe])
      # Stri..
      if ewidth <= limit - 2
        line, _ = trim line, limit - 2, false
        line << '..'
      # ..ring
      else
        # ..ri..
        line = line[0...maxe] + '..' if ewidth < width(line) - 2
        line, diff = trim line, limit - 2, true
        offsets = offsets.map { |pair|
          b, e = pair
          b += 2 - diff
          e += 2 - diff
          b = [2, b].max
          [b, e]
        }
        line = '..' + line
      end
    end

    tokens = []
    index = 0
    offsets.select  { |pair| pair.first < pair.last }.
            sort_by { |pair| pair }.each do |pair|
      b, e = pair.map { |x| [index, x].max }
      tokens << [line[index...b], false]
      tokens << [line[b...e], true]
      index = e
    end
    tokens << [line[index..-1], false]
    tokens.reject { |pair| pair.first.empty? }
  end

  def print_item row, tokens, chosen, selected
    # Cursor
    C.setpos row, 0
    C.clrtoeol
    cprint chosen ? '>' : ' ', color(:cursor, true)
    cprint selected ? '>' : ' ',
      chosen ? color(:chosen) : (selected ? color(:selected, true) : 0)

    # Highlighted item
    C.attron color(:chosen, true) if chosen
    tokens.each do |pair|
      token, highlighted = pair

      if highlighted
        cprint   token, color(chosen ? :match! : :match, chosen)
        C.attron color(:chosen, true) if chosen
      else
        addstr_safe token
      end
    end
    C.attroff color(:chosen, true) if chosen
  end

  def sort_by_rank list
    list.sort_by { |tuple|
      line, offsets = tuple
      matchlen = 0
      pe = nil
      offsets.sort.each do |pair|
        b, e = pair
        b    = pe if pe && pe > b
        pe   = e
        matchlen += e - b
      end
      [matchlen, line.length, line]
    }
  end

  if RUBY_VERSION.split('.').map { |e| e.rjust(3, '0') }.join > '001009'
    @@wrx = Regexp.new '\p{Han}|\p{Katakana}|\p{Hiragana}|\p{Hangul}'
    def width str
      str.gsub(@@wrx, '  ').length
    end

    def trim str, len, left
      width = width str
      diff  = 0
      while width > len
        width -= (left ? str[0, 1] : str[-1, 1]) =~ @@wrx ? 2 : 1
        str    = left ? str[1..-1] : str[0...-1]
        diff  += 1
      end
      [str, diff]
    end
  else
    def width str
      str.length
    end

    def trim str, len, left
      diff = str.length - len
      if diff > 0
        [left ? str[diff..-1] : str[0...-diff], diff]
      else
        [str, 0]
      end
    end

    class ::String
      def ord
        self.unpack('c').first
      end
    end

    class ::Fixnum
      def ord
        self
      end
    end
  end

  def init_screen
    C.init_screen
    C.start_color
    dbg =
      if C.respond_to?(:use_default_colors)
        C.use_default_colors
        -1
      else
        C::COLOR_BLACK
      end
    C.raw
    C.noecho

    if @color
      if C.can_change_color?
        C.init_pair 1, 110, dbg
        C.init_pair 2, 108, dbg
        C.init_pair 3, 254, 236
        C.init_pair 4, 151, 236
        C.init_pair 5, 148, dbg
        C.init_pair 6, 144, dbg
        C.init_pair 7, 161, 236
        C.init_pair 8, 168, 236
      else
        C.init_pair 1, C::COLOR_BLUE,    dbg
        C.init_pair 2, C::COLOR_GREEN,   dbg
        C.init_pair 3, C::COLOR_YELLOW,  C::COLOR_BLACK
        C.init_pair 4, C::COLOR_GREEN,   C::COLOR_BLACK
        C.init_pair 5, C::COLOR_GREEN,   dbg
        C.init_pair 6, C::COLOR_WHITE,   dbg
        C.init_pair 7, C::COLOR_RED,     C::COLOR_BLACK
        C.init_pair 8, C::COLOR_MAGENTA, C::COLOR_BLACK
      end

      def self.color sym, bold = false
        C.color_pair([:prompt, :match, :chosen, :match!,
                      :spinner, :info, :cursor, :selected].index(sym) + 1) |
          (bold ? C::A_BOLD : 0)
      end
    else
      def self.color sym, bold = false
        case sym
        when :chosen
          bold ? C::A_REVERSE : 0
        when :match
          C::A_UNDERLINE
        when :match!
          C::A_REVERSE | C::A_UNDERLINE
        else
          0
        end | (bold ? C::A_BOLD : 0)
      end
    end
  end

  def start_reader
    stream =
      if @source.tty?
        if default_command = ENV['FZF_DEFAULT_COMMAND']
          IO.popen(default_command)
        elsif !`which find`.empty?
          IO.popen("find * -path '*/\\.*' -prune -o -type f -print -o -type l -print 2> /dev/null")
        else
          exit 1
        end
      else
        @source
      end

    Thread.new do
      while line = stream.gets
        emit(:new) { @new << line.chomp }
      end
      emit(:loaded) { true }
      @spinner.clear
    end
  end

  def start_search
    matcher  = (@xmode ? ExtendedFuzzyMatcher : FuzzyMatcher).new @rxflag
    searcher = Thread.new {
      lists   = []
      events  = {}
      fcache  = {}
      q       = ''
      delay   = -5

      begin
        while true
          @mtx.synchronize do
            while true
              events.merge! @events

              if @events.empty? # No new events
                @cv.wait @mtx
                next
              end
              @events.clear
              break
            end

            if events[:new]
              lists << @new
              @count.set { |c| c + @new.length }
              @spinner.set { |spinner|
                if e = spinner.shift
                  spinner.push e
                end; spinner
              }
              @new = []
              fcache.clear
            end
          end#mtx

          new_search = events[:key] || events.delete(:new)
          user_input = events[:key]
          progress   = 0
          started_at = Time.now

          if new_search && !lists.empty?
            q, cx = events.delete(:key) || [q, 0]
            empty = matcher.empty?(q)
            matches = fcache[q] ||=
              begin
                found = []
                skip  = false
                cnt   = 0
                lists.each do |list|
                  cnt += list.length
                  skip = @mtx.synchronize { @events[:key] }
                  break if skip

                  if !empty && (progress = 100 * cnt / @count.get) < 100 && Time.now - started_at > 0.5
                    render { print_info " (#{progress}%)" }
                  end

                  found.concat(q.empty? ? list :
                               matcher.match(list, q, q[0, cx], q[cx..-1]))
                end
                next if skip
                @sort ? found : found.reverse
              end

            if !empty && @sort && matches.length <= @sort
              matches = sort_by_rank(matches)
            end

            # Atomic update
            @matches.set matches
          end#new_search

          # This small delay reduces the number of partial lists
          sleep((delay = [20, delay + 5].min) * 0.01) unless user_input

          update_list new_search
        end#while
      rescue Exception => e
        @main.raise e
      end
    }
  end

  def pick
    items = @matches[0, max_items]
    curr = [0, [@vcursor.get, items.length - 1].min].max
    [*items.fetch(curr, [])][0]
  end

  def update_list wipe
    render do
      items = @matches[0, max_items]

      # Wipe
      if items.length < @plcount
        @plcount.downto(items.length) do |idx|
          C.setpos cursor_y - idx - 2, 0
          C.clrtoeol
        end
      end
      @plcount = items.length

      maxc    = C.cols - 3
      vcursor = @vcursor.set { |v| [0, [v, items.length - 1].min].max }
      cleanse = Set[vcursor]
      @vcursors.set { |vs|
        cleanse.merge vs
        Set.new
      }
      items.each_with_index do |item, idx|
        next unless wipe || cleanse.include?(idx)
        row           = cursor_y - idx - 2
        chosen        = idx == vcursor
        selected      = @selects.include?([*item][0])
        line, offsets = convert_item item
        tokens        = format line, maxc, offsets
        print_item row, tokens, chosen, selected
      end
      print_info
    end
  end

  def start_renderer
    Thread.new do
      begin
        while blk = @queue.shift
          blk.call
          refresh
        end
      rescue Exception => e
        @main.raise e
      end
    end
  end

  def render &blk
    @queue.push blk
    nil
  end

  def start_loop
    got = nil
    begin
      tty     = IO.open(IO.sysopen('/dev/tty'), 'r')
      input   = ''
      cursor  = 0
      backword = proc {
        cursor = (input[0, cursor].rindex(/\s\S/) || -1) + 1
      }
      actions = {
        :nop     => proc { nil },
        ctrl(:c) => proc { exit 1 },
        ctrl(:d) => proc { exit 1 if input.empty? },
        ctrl(:m) => proc {
          got = pick
          exit 0
        },
        ctrl(:u) => proc { input = input[cursor..-1]; cursor = 0 },
        ctrl(:a) => proc { cursor = 0; nil },
        ctrl(:e) => proc { cursor = input.length; nil },
        ctrl(:j) => proc { @vcursor.set { |v| @vcursors << v; v - 1 }; update_list false },
        ctrl(:k) => proc { @vcursor.set { |v| @vcursors << v; v + 1 }; update_list false },
        ctrl(:w) => proc {
          pcursor = cursor
          backword.call
          input = input[0...cursor] + input[pcursor..-1]
        },
        127 => proc { input[cursor -= 1] = '' if cursor > 0 },
        9   => proc { |o|
          if @multi && sel = pick
            if @selects.has_key? sel
              @selects.delete sel
            else
              @selects[sel] = 1
            end
            @vcursor.set { |v|
              @vcursors << v
              v + (o == :stab ? 1 : -1)
            }
            update_list false
          end
        },
        :left  => proc { cursor = [0, cursor - 1].max; nil },
        :right => proc { cursor = [input.length, cursor + 1].min; nil },
        :alt_b => proc { backword.call; nil },
        :alt_f => proc {
          cursor += (input[cursor..-1].index(/(\S\s)|(.$)/) || -1) + 1
          nil
        },
      }
      actions[ctrl(:b)] = actions[:left]
      actions[ctrl(:f)] = actions[:right]
      actions[ctrl(:h)] = actions[127]
      actions[ctrl(:n)] = actions[ctrl(:j)]
      actions[ctrl(:p)] = actions[ctrl(:k)]
      actions[:stab]    = actions[9]

      while true
        @cursor_x.set cursor
        render { print_input }

        ord = tty.getc.ord
        ord =
          case ord = tty.getc.ord
          when 91
            case tty.getc.ord
            when 68 then :left
            when 67 then :right
            when 66 then ctrl(:j)
            when 65 then ctrl(:k)
            when 90 then :stab
            else :nop
            end
          when 'b'.ord
            :alt_b
          when 'f'.ord
            :alt_f
          else
            ord
          end if ord == 27

        upd = actions.fetch(ord, proc { |ord|
          char = [ord].pack('U*')
          if char =~ /[[:print:]]/
            input.insert cursor, char
            cursor += 1
          end
        }).call(ord)

        # Dispatch key event
        emit(:key) { [@query.set(input.dup), cursor] } if upd
      end
    ensure
      C.close_screen
      if got
        if @selects.empty?
          @stdout.puts got
        else
          @selects.each do |sel, _|
            @stdout.puts sel
          end
        end
      end
    end
  end

  class FuzzyMatcher < Matcher
    attr_reader :caches, :rxflag

    def initialize rxflag
      @caches = Hash.new { |h, k| h[k] = {} }
      @regexp = {}
      @rxflag = rxflag
    end

    def empty? q
      q.empty?
    end

    def fuzzy_regex q
      @regexp[q] ||= begin
        q = q.downcase if @rxflag != 0
        Regexp.new(query_chars(q).inject('') { |sum, e|
          e = Regexp.escape e
          sum << (e.length > 1 ? "(?:#{e}).*?" :  # FIXME: not equivalent
                                 "#{e}[^#{e}]*?")
        }, @rxflag)
      end
    end

    def match list, q, prefix, suffix
      regexp = fuzzy_regex q

      cache = @caches[list.object_id]
      prefix_cache = nil
      (prefix.length - 1).downto(1) do |len|
        break if prefix_cache = cache[prefix[0, len]]
      end

      suffix_cache = nil
      0.upto(suffix.length - 1) do |idx|
        break if suffix_cache = cache[suffix[idx..-1]]
      end unless suffix.empty?

      partial_cache = [prefix_cache,
                       suffix_cache].compact.sort_by { |e| e.length }.first
      cache[q] ||= (partial_cache ?
                    partial_cache.map { |e| e.first } : list).map { |line|
        # Ignore errors: e.g. invalid byte sequence in UTF-8
        md = line.match(regexp) rescue nil
        md && [line, [md.offset(0)]]
      }.compact
    end
  end

  class ExtendedFuzzyMatcher < FuzzyMatcher
    def initialize rxflag
      super
      @regexps = {}
    end

    def empty? q
      parse(q).empty?
    end

    def parse q
      q = q.strip
      @regexps[q] ||= q.split(/\s+/).map { |w|
        invert =
          if w =~ /^!/
            w = w[1..-1]
            true
          end

        [ @regexp[w] ||=
            case w
            when ''
              nil
            when /^'/
              w.length > 1 ?
                Regexp.new(sanitize(Regexp.escape(w[1..-1])), rxflag) : nil
            when /^\^/
              w.length > 1 ?
                Regexp.new('^' << sanitize(Regexp.escape(w[1..-1])), rxflag) : nil
            when /\$$/
              w.length > 1 ?
                Regexp.new(sanitize(Regexp.escape(w[0..-2])) << '$', rxflag) : nil
            else
              fuzzy_regex w
            end, invert ]
      }.select { |pair| pair.first }
    end

    def match list, q, prefix, suffix
      regexps = parse q
      # Look for prefix cache
      cache  = @caches[list.object_id]
      prefix = prefix.strip.sub(/\$\S*$/, '').sub(/(^|\s)!\S*$/, '')
      prefix_cache = nil
      (prefix.length - 1).downto(1) do |len|
        break if prefix_cache = cache[Set[@regexps[prefix[0, len]]]]
      end

      cache[Set[regexps]] ||= (prefix_cache ?
                               prefix_cache.map { |e| e.first } :
                               list).map { |line|
        offsets = []
        regexps.all? { |pair|
          regexp, invert = pair
          md = line.match(regexp) rescue nil
          if md && !invert
            offsets << md.offset(0)
          elsif !md && invert
            true
          end
        } && [line, offsets]
      }.select { |e| e }
    end
  end
end#FZF

FZF.new(ARGV, $stdin).start if ENV.fetch('FZF_EXECUTABLE', '1') == '1'