git.r.bdr.sh - rbdr/dotfiles/blob - vim/tmp/command_t/ruby/command-t/match.c

   1 // Copyright 2010 Wincent Colaiuta. All rights reserved.
   2 //
   3 // Redistribution and use in source and binary forms, with or without
   4 // modification, are permitted provided that the following conditions are met:
   5 //
   6 // 1. Redistributions of source code must retain the above copyright notice,
   7 //    this list of conditions and the following disclaimer.
   8 // 2. Redistributions in binary form must reproduce the above copyright notice,
   9 //    this list of conditions and the following disclaimer in the documentation
  10 //    and/or other materials provided with the distribution.
  11 //
  12 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  13 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  14 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  15 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE
  16 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  17 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  18 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  19 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  20 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  21 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  22 // POSSIBILITY OF SUCH DAMAGE.
  23
  24 #include "match.h"
  25 #include "ext.h"
  26 #include "ruby_compat.h"
  27
  28 // use a struct to make passing params during recursion easier
  29 typedef struct
  30 {
  31     char    *str_p;                 // pointer to string to be searched
  32     long    str_len;                // length of same
  33     char    *abbrev_p;              // pointer to search string (abbreviation)
  34     long    abbrev_len;             // length of same
  35     double  max_score_per_char;
  36     int     dot_file;               // boolean: true if str is a dot-file
  37     int     always_show_dot_files;  // boolean
  38     int     never_show_dot_files;   // boolean
  39 } matchinfo_t;
  40
  41 double recursive_match(matchinfo_t *m,  // sharable meta-data
  42                        long str_idx,    // where in the path string to start
  43                        long abbrev_idx, // where in the search string to start
  44                        long last_idx,   // location of last matched character
  45                        double score)    // cumulative score so far
  46 {
  47     double seen_score = 0;      // remember best score seen via recursion
  48     int dot_file_match = 0;     // true if abbrev matches a dot-file
  49     int dot_search = 0;         // true if searching for a dot
  50
  51     for (long i = abbrev_idx; i < m->abbrev_len; i++)
  52     {
  53         char c = m->abbrev_p[i];
  54         if (c == '.')
  55             dot_search = 1;
  56         int found = 0;
  57         for (long j = str_idx; j < m->str_len; j++, str_idx++)
  58         {
  59             char d = m->str_p[j];
  60             if (d == '.')
  61             {
  62                 if (j == 0 || m->str_p[j - 1] == '/')
  63                 {
  64                     m->dot_file = 1;        // this is a dot-file
  65                     if (dot_search)         // and we are searching for a dot
  66                         dot_file_match = 1; // so this must be a match
  67                 }
  68             }
  69             else if (d >= 'A' && d <= 'Z')
  70                 d += 'a' - 'A'; // add 32 to downcase
  71             if (c == d)
  72             {
  73                 found = 1;
  74                 dot_search = 0;
  75
  76                 // calculate score
  77                 double score_for_char = m->max_score_per_char;
  78                 long distance = j - last_idx;
  79                 if (distance > 1)
  80                 {
  81                     double factor = 1.0;
  82                     char last = m->str_p[j - 1];
  83                     char curr = m->str_p[j]; // case matters, so get again
  84                     if (last == '/')
  85                         factor = 0.9;
  86                     else if (last == '-' ||
  87                             last == '_' ||
  88                             last == ' ' ||
  89                             (last >= '0' && last <= '9'))
  90                         factor = 0.8;
  91                     else if (last >= 'a' && last <= 'z' &&
  92                             curr >= 'A' && curr <= 'Z')
  93                         factor = 0.8;
  94                     else if (last == '.')
  95                         factor = 0.7;
  96                     else
  97                         // if no "special" chars behind char, factor diminishes
  98                         // as distance from last matched char increases
  99                         factor = (1.0 / distance) * 0.75;
 100                     score_for_char *= factor;
 101                 }
 102
 103                 if (++j < m->str_len)
 104                 {
 105                     // bump cursor one char to the right and
 106                     // use recursion to try and find a better match
 107                     double sub_score = recursive_match(m, j, i, last_idx, score);
 108                     if (sub_score > seen_score)
 109                         seen_score = sub_score;
 110                 }
 111
 112                 score += score_for_char;
 113                 last_idx = str_idx++;
 114                 break;
 115             }
 116         }
 117         if (!found)
 118             return 0.0;
 119     }
 120     if (m->dot_file)
 121     {
 122         if (m->never_show_dot_files ||
 123             (!dot_file_match && !m->always_show_dot_files))
 124             return 0.0;
 125     }
 126     return (score > seen_score) ? score : seen_score;
 127 }
 128
 129 // Match.new abbrev, string, options = {}
 130 VALUE CommandTMatch_initialize(int argc, VALUE *argv, VALUE self)
 131 {
 132     // process arguments: 2 mandatory, 1 optional
 133     VALUE str, abbrev, options;
 134     if (rb_scan_args(argc, argv, "21", &str, &abbrev, &options) == 2)
 135         options = Qnil;
 136     str             = StringValue(str);
 137     abbrev          = StringValue(abbrev); // already downcased by caller
 138
 139     // check optional options hash for overrides
 140     VALUE always_show_dot_files = CommandT_option_from_hash("always_show_dot_files", options);
 141     VALUE never_show_dot_files = CommandT_option_from_hash("never_show_dot_files", options);
 142
 143     matchinfo_t m;
 144     m.str_p                 = RSTRING_PTR(str);
 145     m.str_len               = RSTRING_LEN(str);
 146     m.abbrev_p              = RSTRING_PTR(abbrev);
 147     m.abbrev_len            = RSTRING_LEN(abbrev);
 148     m.max_score_per_char    = (1.0 / m.str_len + 1.0 / m.abbrev_len) / 2;
 149     m.dot_file              = 0;
 150     m.always_show_dot_files = always_show_dot_files == Qtrue;
 151     m.never_show_dot_files  = never_show_dot_files == Qtrue;
 152
 153     // calculate score
 154     double score = 1.0;
 155     if (m.abbrev_len == 0) // special case for zero-length search string
 156     {
 157         // filter out dot files
 158         if (!m.always_show_dot_files)
 159         {
 160             for (long i = 0; i < m.str_len; i++)
 161             {
 162                 char c = m.str_p[i];
 163                 if (c == '.' && (i == 0 || m.str_p[i - 1] == '/'))
 164                 {
 165                     score = 0.0;
 166                     break;
 167                 }
 168             }
 169         }
 170     }
 171     else // normal case
 172         score = recursive_match(&m, 0, 0, 0, 0.0);
 173
 174     // clean-up and final book-keeping
 175     rb_iv_set(self, "@score", rb_float_new(score));
 176     rb_iv_set(self, "@str", str);
 177     return Qnil;
 178 }
 179
 180 VALUE CommandTMatch_matches(VALUE self)
 181 {
 182     double score = NUM2DBL(rb_iv_get(self, "@score"));
 183     return score > 0 ? Qtrue : Qfalse;
 184 }
 185
 186 VALUE CommandTMatch_to_s(VALUE self)
 187 {
 188     return rb_iv_get(self, "@str");
 189 }