Switch to needle/haystack names for clarity

"str" and "abbrev" are not as clear as "haystack" and "needle",
respectively, so let's switch to the latter.

I'm doing this just inside the match.c functions, as this is where the
potential for confusion is most ripe. "abbrev" is still used in some other
places, such as in matcher.c, but there things seem less likely to
confuse, so I am leaving that as-is for now.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Short-circuit if needle can't possibly fit inside haystack

This is a cheap little optimization that prevents us form scanning (or
further recursing) if we're too close to the end of the haystack to
possibly encounter the rest of the needle. As it only applies towards
the end of the string, it's not going to make a huge impact, but every
little bit helps.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Prepare to memoize intermediate recursive results

This commit doesn't actually add memoization yet, but puts the basic
structure in place to do so. This will save us from re-doing a great
deal of work in some pathological edge cases (eg. searching for
"aaaaaaaaaaaa" in a string like "aaaaaaaaaaaaaaaaaaaaaaaaaa").

Related:

  https://wincent.com/issues/2094

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Add memoization to match.c

This is a first-cut attempt at crude memoization for match.c, which
enables Command-T to better hand "pathological" inputs like:

  needle   : "aaaaaaaaaaaaaaaaa"
  haystack : "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

With memoization, we're much closer to our desired theoretical
worst-case quadratic runtime for this kind of input.

In order to make this fast, we're using a stack-allocated dynamic array
(possible in C99). The size is suitably small (needle length times
haystack length).

We want to remember the score for any given needle index/haystack index
pair, so we just use an array of doubles -- ideally I would have used a
proper multidimensional array, but I am not sure it's possible to do
that with dynamic stack-based allocation in a way that allows me to
declare a useful pointer to it in a struct -- and index into it on
needle index * length + haystack index. This could likely use some
commenting to make clearer what is going on.

We initialize the array with DBL_MAX to distinguish between
previously-calculated scores of "0.0" and merely missing scores.

I added some boundary checking to make it easier to reason about the
state of the recursive call (ie. by not even making it in the case where
we have zero-length needle or haystack).

Consider this a work-in-progress for now. I am going to follow up with
some benchmarks so that I can test this against what was there before
for both "pathological" and "non-pathological" workloads.

Related:

  https://wincent.com/issues/2094

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Update Gemfile source

To silence these warnings:

  The source :rubygems is deprecated because HTTP requests are insecure.
  Please change your source to 'https://rubygems.org' if possible, or
  'http://rubygems.org' if not.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Update Bundle

The only issue of note was that I had to specify and peg nokogiri at a
version that supports Ruby 1.8.7; see:

  http://www.redmine.org/boards/2/topics/38243

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Add benchmarks

Here are the baseline results after recent optimizations:

                          user     system      total        real
  pathological        2.940000   0.000000   2.940000 (  2.958157)
  command-t           3.620000   0.030000   3.650000 (  3.652865)
  chromium (subset)   3.410000   0.020000   3.430000 (  3.437180)
  chromium (whole)   10.160000   0.050000  10.210000 ( 10.229278)

Short-circuiting for needles that can't possibly fit is a pretty big win
for some cases. The "pathological" case was basically untenable prior to
adding memoization (ie. it wouldn't finish in any reasonable timeframe),
although the memoization does appear to slow down the other cases by
about 3-4%.

The goal from here on will be to make the standard cases as fast and
faster than before, while still preserving the ability to handle the
pathological cases without grinding to a halt.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Emit PID at start of benchmark run

This allows us to track memory usage during the run. Turns out, it's
fine, sitting stable at just under 100 MB on this machine.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Terminate inner match.c loop as early as possible

We can save ourselves a decent chunk of work by terminating our inner
loop as soon as we detect that we're too close to the end of the
haystack to possibly match what's left of the needle. It doesn't seem
like much of a change, but when you factor in the elevated costs of
recursion, it ends up being a decent win.

With this change we go from:

                          user     system      total        real
  pathological        2.940000   0.000000   2.940000 (  2.958157)
  command-t           3.620000   0.030000   3.650000 (  3.652865)
  chromium (subset)   3.410000   0.020000   3.430000 (  3.437180)
  chromium (whole)   10.160000   0.050000  10.210000 ( 10.229278)

to:

                          user     system      total        real
  pathological        2.420000   0.000000   2.420000 (  2.450693)
  command-t           3.260000   0.030000   3.290000 (  3.299227)
  chromium (subset)   2.660000   0.020000   2.680000 (  2.672489)
  chromium (whole)    7.750000   0.050000   7.800000 (  7.827607)

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Fix off-by-one error in memoization indexing

I believe this was causing more cache lookups to miss than should have
been the case. At least with the meagre test data I was using, the
quality of the results wasn't being obviously affected.

With this change, the "pathological" test case gets much, much faster,
while the others remain more or less the same.

Old:

                          user     system      total        real
  pathological        2.420000   0.000000   2.420000 (  2.450693)
  command-t           3.260000   0.030000   3.290000 (  3.299227)
  chromium (subset)   2.660000   0.020000   2.680000 (  2.672489)
  chromium (whole)    7.750000   0.050000   7.800000 (  7.827607)

New:

                          user     system      total        real
  pathological        0.000000   0.000000   0.000000 (  0.004769)
  command-t           3.330000   0.030000   3.360000 (  3.368512)
  chromium (subset)   2.570000   0.020000   2.590000 (  2.591855)
  chromium (whole)    7.080000   0.040000   7.120000 (  7.119191)

The improvement is so marked that I am almost suspicious of it, but I
added logging of -- lengths and indices, hits and misses, loads and
stores -- and ran it over a simple test case and it looks like the right
values are being loaded/stored in the cache.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Add :special_wild_ignore option

This is a squashed version of this pull request:

  https://github.com/wincent/Command-T/pull/55

Specifically:

  https://github.com/myitcv/command-t/commit/754d91c597cc7666a8d458cc8f19e5dabb1d6dff
  https://github.com/myitcv/command-t/commit/3076cb1ca9d855b62e053e3a268e7200f8a957e8

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Drop "Special" from g:CommandTSpecialWildIgnore

As this is Command-T's only wildignore setting (ie. there is no
"non-special" variant), we can go with a shorter name here.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Update docs for g:CommandTWildIgnore setting

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Tidy up wildignore handling

The `#add_paths_for_directory` method was getting pretty long and ghastly,
so this commit removes the wildignore handling bits from that method and
moves them elsewhere.

Specifically, the shorter and simpler `#paths` method is now responsible
for setting the temporary wildignore setting and restoring the old
setting, if appropriate.

We now get the base wildignore setting only once, at initialize-time
(although you can force re-reading by doing a `:CommandTFlush`).

The logic for reading the wildignore setting has been moved into a
utility function on the CommandT::VIM module.

Overall, this is more verbose, but I think it makes the FileScanner code
cleaner overall.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Merge branch 'myitcv/special_wild_ignore' into next

* myitcv/special_wild_ignore:
  Tidy up wildignore handling
  Update docs for g:CommandTWildIgnore setting
  Drop "Special" from g:CommandTSpecialWildIgnore
  Add :special_wild_ignore option

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Fix a misalignment issue in the docs

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Switch to The One True Brace Style in C files

If you look carefully at the diff, you'll see that there were some
places where I was unthinkingly gravitating towards that style anyway,
so let's just give in and make the change.

The original brace style was most likely largely due to the influence of
Objective-C on me, of which I've written a fair bit in the last decade.

The new style is largely the result of my work at Causes, where we
happen to use The One True Brace Style in our JavaScript; the force of
habit is starting to make itself felt.

In addition to modifying the brace style, I tweaked a fair few lines for
readability, making a few things align and adding blank lines where I
felt it led to a better vertical rhythm. There are a couple of gnarly
and hard-to-read conditionals that could use some more work, but I
mostly just let Vim format those as it saw fit.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Update docs for 1.5 release

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Update vimscriptuploader submodule

This is necessary for compatibiity with the version of Mechanize that we
are using.

Signed-off-by: Wincent Colaiuta <win@wincent.com>