Feature request #1710: Provide hints about fewest number of keystrokes required to target a specific file

Comments

1. Greg Hurrell 2010-10-12T10:45:04Z

   Thanks for the request, Joseph. I have two thoughts about this:

   1. Computational complexity

   One is that the amount of computation required to calculate this "shortest string" would be absolutely enormous. Consider a typical project with anywhere from a few hundred to several thousand files in it, and think about how many possible permutations of search strings you would need to consider and compare in order to determine the best/shortest string for each file.

   Imagine a path which has 40 or 50 characters in it, like spec/controllers/issues_controller_spec.rb; there are perhaps thousands of search strings of lengths ranging from as little as 1 to as many as 42 characters which could conceivably match this path:

   • one-letter strings: s, p, e, c, /, o, n, t, r, l, i, u, _, ., b
   • two-letter strings: sp, se, sc, s/, so, sn ... pe, pc, p/, po ...
   • three-letter stings: ...

   The number of permuations is absolutely enormous, and for each of these you would need to calculate a "score" between 0.0 and 1.0 indicating the ranking for that path given that search pattern. Multiply that by 4 or 5,000 paths in the project and we're already talking about millions of scores.

   Once you've got all these score you then need to grind through them and figure out which one is the shortest "winning" score for each path, and it's quite possible that there will be a tie and you'll then have to decide which one is the "best" or most intuitive one which you should show as a hint to the user. The amount of work needed to perform this comparison would grow exponentially as the number of files in the project increases.

   I don't actually think this could be viably done for anything but the most trivial projects; for real-world projects with typical file counts in the hundreds and thousands performance would quickly degrade to the point of being untenable.

   2. The right way to solve the problem

   My other thought is that if finding files with Command-T isn't intuitive and easy for you, then the solution is not having you look at or memorize a list of shortcuts (which in themselves may not seem at all intuitive to you; you may end up asking yourself, why did the program end up choosing those letters for that path?). I think instead you'd benefit much more from a deeper understanding of how results are scored, and when you understand the way the algorithm works, it becomes much easier to find what you're looking for.

   I'll try to sum it up for you in a nutshell here:

   • Command-T looks at characters in the entire path, not just the file name (ie. if you want to open foo/bar then you're not limited to typing "bar" but can type "fb" instead)
   • by including characters from the initial path components rather than just the filename you help narrow down the range of possible matches (ie. given file spec/models/issue_spec.rb you will probably narrow down the search more decisively by typing "smi" than by typing "iss")
   • some characters are weighted more heavily in the scoring algorithm; that is, characters which appear immediately after a slash or an underscore will be given more weight than those buried in the middle of a run of letters (ie. given file lib/authentication/ssl_wrapper.rb a string like "lasw" will score more highly than one like "bclr"; both of those strings match the path, but the first one is a "better" match because the matching characters fall after boundary characters)

   As a general rule of thumb the most important things to remember are:

   • characters that follow "boundary" markers (like "/" and "_") are the most important ones, and are the ones that you should prefer when typing your search string
   • as the number of files in the project grows, the more important it becomes to provide letters from higher up in the path components (eg. in a 10-file project then it is fine to type "bar" in order to find foo/bar, but in a 10,000-file project if you want to open foo/bing/bang/bong/buzz/bar then you'd best get in the habit of typing something like "fbbbbbar" rather than just "bar")

   Hope this helped.

2. anonymous 2010-10-12T21:37:39Z

   Wincent,

   Thanks for the thoughtful response. Agreed on point 1 - way too computationally complex.

   As an alternative, what if users could create their own file of mappings and command-T could process those are overrides to its own algorithm? That way, for those fifteen or so files that I am constantly going to, I can have those mappings memorized and count on just my fingers to get me where I need to go, rather than viewing the output from Command-T and verifying that I've highlighted the file I want.

   So, billing_report.php could have the mapping "br". I type in "br" and that file is auto-selected. Type "Enter" and bam, it opens. Just as easily I should be able to alternatively choose "bphp" as the mapping, update my mappings file, and have that work.

   What are your thoughts on this approach?

   -Joseph

3. Greg Hurrell 2010-10-13T06:37:49Z

   Take a look at ticket #1541 ('"Learn" from previous selections'). The idea proposed there is that the plug-in remembers which files you choose for any given search string and then in future searches adds a "bonus" to the score of such items when you enter that same search string again.

   So in your example, you type "br", wanting to open billing_report.php, and it's not the top search result so you actually end up using the cursor keys to move down and select it. The next time you type "br", Command-T applies a small bonus to billing_report.php, pushing it slightly higher up the results listing. You again use the cursor keys to move down and select it and so the bonus is bumped up a little higher. Next time you type "br", the bonus is big enough to make billing_report.php the top result.

   What do you think of that one? I'm inclined to think that this would be a nice, intuitive way to transparently give you the behavior you're looking for without obliging users to spend time maintaing a special mappings file.

   The only tricky part of this would be fine-tuning the implementation details (how much should the "bonus" fluctuate up or down when you select a file or later select a different one?) but nothing insurmountable.

4. joseph Created 2010-10-14T17:24:45Z, edited 2010-10-15T12:02:20Z

   The bonus is an interesting idea, though the bottom line is that it will take some time for the program to learn. Plus, what if I want to use a keystroke series that is not a match for the resource - it will never appear in the matches.

   I delved into the Command-T source code last night and put a little something together. Let me know what you think. My co-worker and I are already using this and we like it a good bit. Eager to hear your thoughts, Wincent.

   Inside controller.rb:

   Add this line near the other requires:

   require 'yaml'

   Change this function:

   def list_matches
     matches = @finder.sorted_matches_for @prompt.abbrev, :limit => match_limit
     override_file = "command-t-overrides.yaml"
     if File.file?(override_file)
       file_contents = IO.read(override_file)
       ruby_obj = YAML::load(file_contents)
       overrides = ruby_obj["overrides"]
       overrides.each_pair do |k,v|
         if @prompt.abbrev == k
           matches.insert(0, v)
         end
       end
     end
     @match_window.matches = matches
   end

   And then in my directory where I usually launch vim, I have my command-t-overrides.yaml file:

   overrides: {
     pr : scripts/billing/payment_report.php,
     br : scripts/billing/billing_report.php,
     cto : command-t-overrides.yaml
   } 

5. Greg Hurrell 2010-10-16T17:11:18Z

   Nice to see you could implement this without having to make deep changes to the algorithm, but instead just insert it at a higher layer.

   A few suggestions:

   • wouldn't command-t-overrides.yaml be better as an invisible dot-file?
   • do you really need to wrap things inside the "overrides" hash? (if the file contains only key-value pairs YAML::load will return a hash anyway); if you're envisioning additional future possible uses for this file, of which shortcut overrides would be just one, then it should probably be called .command-t.yaml and not have "overrides" in the file name at all
   • I'd suggest reading the overrides file once only at the beginning of the search, rather than for each key press (list_matches is called once for each new key press)

Add a comment

Comments are now closed for this issue.