class FuzzyFileFinder

The “fuzzy” file finder provides a way for searching a directory tree with only a partial name. This is similar to the “cmd-T” feature in TextMate (macromates.com).

Usage:

finder = FuzzyFileFinder.new
finder.search("app/blogcon") do |match|
  puts match[:highlighted_path]
end

In the above example, all files matching “app/blogcon” will be yielded to the block. The given pattern is reduced to a regular expression internally, so that any file that contains those characters in that order (even if there are other characters in between) will match.

In other words, “app/blogcon” would match any of the following (parenthesized strings indicate how the match was made):

And so forth.

Attributes

ceiling[R]

The maximum number of files beneath all roots

files[R]

The list of files beneath all roots

ignores[R]

The list of glob patterns to ignore.

roots[R]

The roots directory trees to search.

shared_prefix[R]

The prefix shared by all roots.

Public Class Methods

new( params = {} ) click to toggle source

Initializes a new FuzzyFileFinder. This will scan the given directories, using ceiling as the maximum number of entries to scan. If there are more than ceiling entries a TooManyEntries exception will be raised.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 105
def initialize( params = {} )
  @ceiling = params[:ceiling] || 10_000
  @ignores = Array(params[:ignores])

  if params[:directories]
    directories = Array(params[:directories])
    directories << "." if directories.empty?
  else
    directories = ['.']
  end

  @recursive = params[:recursive].nil? ? true : params[:recursive]

  # expand any paths with ~
  root_dirnames = directories.map { |d|
    File.realpath(d)
  }.select { |d|
    File.directory?(d)
  }.uniq

  @roots = root_dirnames.map { |d| Directory.new(d, true) }
  @shared_prefix = determine_shared_prefix
  @shared_prefix_re = Regexp.new("^#{Regexp.escape(shared_prefix)}" + (shared_prefix.empty? ? "" : "/"))

  @files = []
  @directories = {}  # To detect link cycles

  rescan!
end

Public Instance Methods

find(pattern, max=nil) click to toggle source

Takes the given pattern (which must be a string, formatted as described in search), and returns up to max matches in an Array. If max is nil, all matches will be returned.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 202
def find(pattern, max=nil)
  results = []
  search(pattern) do |match|
    results << match
    break if max && results.length >= max
  end
  return results
end
rescan!() click to toggle source

Rescans the subtree. If the directory contents every change, you’ll need to call this to force the finder to be aware of the changes.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 138
def rescan!
  @files.clear
  roots.each { |root| follow_tree(root) }
end

Private Instance Methods

build_match_result(match, inside_segments) click to toggle source

Given a MatchData object match and a number of “inside” segments to support, compute both the match score and the highlighted match string. The “inside segments” refers to how many patterns were matched in this one match. For a file name, this will always be one. For directories, it will be one for each directory segment in the original pattern.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 269
def build_match_result(match, inside_segments)
  runs = []
  inside_chars = total_chars = 0
  match.captures.each_with_index do |capture, index|
    if capture.length > 0
      # odd-numbered captures are matches inside the pattern.
      # even-numbered captures are matches between the pattern's elements.
      inside = index % 2 != 0

      total_chars += capture.gsub(%r(/), "").length # ignore '/' delimiters
      inside_chars += capture.length if inside

      if runs.last && runs.last.inside == inside
        runs.last.string << capture
      else
        runs << CharacterRun.new(capture, inside)
      end
    end
  end

  # Determine the score of this match.
  # 1. fewer "inside runs" (runs corresponding to the original pattern)
  #    is better.
  # 2. better coverage of the actual path name is better

  inside_runs = runs.select { |r| r.inside }
  run_ratio = inside_runs.length.zero? ? 1 : inside_segments / inside_runs.length.to_f

  char_ratio = total_chars.zero? ? 1 : inside_chars.to_f / total_chars

  score = run_ratio * char_ratio

  return { :score => score, :result => runs.join }
end
determine_shared_prefix() click to toggle source
# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 346
def determine_shared_prefix
  # the common case: if there is only a single root, then the entire
  # name of the root is the shared prefix.
  return roots.first.name if roots.length == 1

  split_roots = roots.map { |root| root.name.split(%r{/}) }
  segments = split_roots.map { |root| root.length }.max
  master = split_roots.pop

  segments.times do |segment|
    if !split_roots.all? { |root| root[segment] == master[segment] }
      return master[0,segment].join("/")
    end
  end

  # shouldn't ever get here, since we uniq the root list before
  # calling this method, but if we do, somehow...
  return roots.first.name
end
follow_tree(directory) click to toggle source

Recursively scans directory and all files and subdirectories beneath it, depth-first.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 220
def follow_tree(directory)
  real_dir = File.realpath(directory.name)
  if ! @directories[real_dir]
    @directories[real_dir] = true

    Dir.entries(directory.name).each do |entry|
      next  if entry[0,1] == "."
      raise TooManyEntries if files.length > ceiling

      full = File.join(directory.name, entry)
      next  if ignore?(full)

      if File.directory?(full)
        if @recursive
          follow_tree(Directory.new(full))
        end
      else
        files.push(FileSystemEntry.new(directory, entry))
      end
    end
  end
end
ignore?(name) click to toggle source

Returns true if the given name matches any of the ignore patterns.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 245
def ignore?(name)
  n = name.sub(@shared_prefix_re, "")
  ignores.any? { |pattern| File.fnmatch(pattern, n) }
end
make_pattern(pattern) click to toggle source

Takes the given pattern string “foo” and converts it to a new string “(f)(*?)(o)(*?)(o)” that can be used to create a regular expression.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 253
def make_pattern(pattern)
  pattern = pattern.split(//)
  pattern << "" if pattern.empty?

  pattern.inject("") do |regex, character|
    regex << "([^/]*?)" if regex.length > 0
    regex << "(" << Regexp.escape(character) << ")"
  end
end
match_file(file, file_regex, path_match) { |result| ... } click to toggle source

Match file against file_regex. If it matches, yield the match metadata to the block.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 327
def match_file(file, file_regex, path_match, &block)
  if file_match = file.name.match(file_regex)
    match_result = build_match_result(file_match, 1)
    full_match_result = path_match[:result].empty? ? match_result[:result] : File.join(path_match[:result], match_result[:result])
    shortened_path = path_match[:result].gsub(/[^\/]+/) { |m| m.index("(") ? m : m[0,1] }
    abbr = shortened_path.empty? ? match_result[:result] : File.join(shortened_path, match_result[:result])

    result = { :path => file.path,
               :abbr => abbr,
               :directory => file.parent.name,
               :name => file.name,
               :highlighted_directory => path_match[:result],
               :highlighted_name => match_result[:result],
               :highlighted_path => full_match_result,
               :score => path_match[:score] * match_result[:score] }
    yield result
  end
end
match_path(path, path_matches, path_regex, path_segments) click to toggle source

Match the given path against the regex, caching the result in path_matches. If path is already cached in the path_matches cache, just return the cached value.

# File lib/diakonos/vendor/fuzzy_file_finder.rb, line 307
def match_path(path, path_matches, path_regex, path_segments)
  return path_matches[path] if path_matches.key?(path)

  name_with_slash = path.name + "/" # add a trailing slash for matching the prefix
  matchable_name = name_with_slash.sub(@shared_prefix_re, "")
  matchable_name.chop! # kill the trailing slash

  if path_regex
    match = matchable_name.match(path_regex)

    path_matches[path] =
      match && build_match_result(match, path_segments) ||
      { :score => 1, :result => matchable_name, :missed => true }
  else
    path_matches[path] = { :score => 1, :result => matchable_name }
  end
end