Changeset e37ef045516872af81e36339debad2296a2d7506

Timestamp:

04/28/08 11:42:00 (8 months ago)

Author:

dave <dave@…>

Parents:

afa46936e67e892eb5c8429bd0991a4630cbd71f, 8f4fd07de7bf767b30c219684608535cb9cb6f19

Children:

a2344576c2573c3b9a6fb40dfc614fd4cfe178f7

git-committer:

dave <dave@06fd6eb0-0002-0410-a719-e5602cce40bc> / 2008-04-28T01:42:00Z+0000

Message:

Merge branch 'master' into local-svn

git-svn-id: svn+ssh://davebalmain.com/home/dave/repos/ferret/trunk@1046 06fd6eb0-0002-0410-a719-e5602cce40bc

Files:

• c/.rake/.gitignore (modified) (1 diff)
• c/.rake/gcov.history (added)
• c/.rake/gcov_history.plot (added)
• c/.rake/gcov_results.erb (modified) (1 diff)
• c/Rakefile (modified) (11 diffs)
• c/include/internal.h (modified) (1 diff)
• c/include/search.h (modified) (1 diff)
• c/src/index.c (modified) (3 diffs)
• c/src/q_fuzzy.c (modified) (5 diffs)
• c/src/q_phrase.c (modified) (13 diffs)
• c/test/test.c (modified) (3 diffs)
• c/test/test_bitvector.c (modified) (13 diffs)
• c/test/test_q_fuzzy.c (modified) (9 diffs)
• c/test/test_search.c (modified) (13 diffs)
• ruby/Rakefile (modified) (2 diffs)

c/.rake/.gitignore

@@ -3 +3 @@
 copts
 gcov_results.html
+gcov_history.jpg
+gcov_history.data

c/.rake/gcov_results.erb

@@ -16 +16 @@
     <h1>Ferret gcov Results</h1>
     <table cellpadding="0" cellspacing="5">
-    <% $gcov_results.each do |percent, line_cnt, filename| %>
+    <% gcov_sorted_keys.each do |fn| %>
       <tr>
-        <th class="filename"><%= filename %></th>
+        <th class="filename"><%= fn %></th>
         <td class="result">
-          <div class="bar" style="width:<%=percent%>%;">&nbsp;<div>
+          <div class="bar" style="width:<%=$gcov_results.files[fn].percent%>%;">&nbsp;<div>
         </td>
       </tr>
     <% end %>
     </table>
+    <img src="gcov_history.jpg" alt="Overall gcov coverage results"/>
     <script type="text/javascript">
       var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");

c/Rakefile

@@ -3 +3 @@
 require 'rake'
 require 'rake/clean'
+require 'ostruct'
 
 class String
@@ -54 +55 @@
   sh script
 end
+
+###
+# Useful Constants
+###
+
+DAY = 24 * 60 * 60 # seconds in day
 
 ###
@@ -105 +112 @@
   basename
 end
-$gcov_results   = []
+
+$gcov_results   = OpenStruct.new(:files => {})
+def gcov_sorted_keys
+  $gcov_results.files.keys.sort {|fn1, fn2|
+      res = $gcov_results.files[fn1].percent <=>
+            $gcov_results.files[fn2].percent
+      res = fn2 <=> fn1 if res == 0
+      res
+  }.reverse
+end
 
 ###
@@ -172 +188 @@
   if copts != old_copts
     File.open(copts_file, 'w') {|f| f.write(Marshal.dump(copts))}
-    Rake::Task[:clean].invoke
+    Rake::Task[:scrub].invoke
   end
 end
@@ -190 +206 @@
                   '*.gcov',
                   'y.tab.c'])
-
 CLOBBER.include([ '*.a',
                   '**/*.o',
@@ -200 +215 @@
                   GCOV_DIR])
 
-task :default => :testall
-
+SCRUB = FileList[CLEAN, '**/*.o']
+desc "clean for rebuild"
+task :scrub do
+  SCRUB.each {|fn| rm_r fn rescue nil}
+end
+
+###
+# Test Helpers
+###
 def run_tests
   check_coptions
@@ -215 +237 @@
 end
 
+###
+# gcov Helpers
+###
+GCOV_HIST_FILE = ".rake/gcov.history"
+def load_gcov_history
+  Marshal.load(File.read(GCOV_HIST_FILE))
+end
+
+task :default => :testall
+
 desc "Run all tests"
 task :test do
@@ -229 +261 @@
 task :gcov => :do_gcov do
   puts "\ngcov Results\n=============\n"
-  $gcov_results.each do |percent, line_cnt, fn|
-    puts "%25s %6.2f%% (%4d)" % [fn, percent, line_cnt]
-  end
-end
-
-task :gcov2html => :do_gcov do
+  total_lines = 0
+  total_lines_covered = 0
+  gcov_sorted_keys.each do |fn|
+    res = $gcov_results.files[fn]
+    puts "%25s %6.2f%% (%4d)" % [fn, res.percent, res.line_count]
+  end
+  puts "Total Lines:         %s" % $gcov_results.total_lines
+  puts "Total Lines covered: %s (%0.2f%%)" % 
+            [$gcov_results.covered_lines, $gcov_results.percent]
+end
+
+desc "Generate .rake/gcov_results.html"
+task :gcov2html => [:do_gcov, '.rake/gcov_history.jpg'] do
   puts "Generating .rake/gcov_results.html..."
   File.open('.rake/gcov_results.html', 'w') do |f|
@@ -241 +280 @@
 end
 
+file '.rake/gcov_history.data' => GCOV_HIST_FILE do |t|
+  history = load_gcov_history
+  start = history.start_date
+  File.open(t.name, 'w') do |f|
+    history.data.each do |d|
+      f.write "%s %.2f\n" %
+        [Time.at((d.day + start) * DAY).strftime("%Y-%m-%d"), d.percent]
+    end
+  end
+end
+
+file '.rake/gcov_history.jpg' => '.rake/gcov_history.data' do |t|
+  sh "gnuplot .rake/gcov_history.plot"
+end
+
 task :do_gcov do
   CFLAGS << " -fprofile-arcs -ftest-coverage"
   run_tests
-  gcov_results = []
+  gcov_result_map = {}
   gcov_scanner = /File '([^']+)'\nLines executed:(\d+.\d+)% of (\d+)/
+  total_lines = covered_lines = 0
   OBJS.each do |obj|
     bn = obj.pathmap('%n')
@@ -256 +311 @@
     gcov_cmd = "gcov -o .gcov/ #{obj}"
     details = IO.popen(gcov_cmd).read.scan(gcov_scanner)
-    details.each do |filename, percent, line_cnt|
+    details.each do |filename, percent, line_count|
       next if filename =~ /^\//
-      $gcov_results << [percent.to_f, line_cnt, filename]
-    end
-  end
-  $gcov_results = $gcov_results.sort_by{|res| res[0]}.reverse
+      line_count = line_count.to_i
+      percent = percent.to_f
+      $gcov_results.files[filename] = OpenStruct.new(:percent => percent,
+                                                     :line_count => line_count)
+      total_lines += line_count
+      covered_lines += (0.01 * percent * line_count).to_i
+    end
+  end
+  $gcov_results.total_lines = total_lines
+  $gcov_results.covered_lines = covered_lines
+  $gcov_results.percent = percent = 100.0 * covered_lines /total_lines
+  history = load_gcov_history
+  today = Time.now.to_i/DAY - history.start_date
+  history.data.pop if history.data.last.day == today
+  history.data << OpenStruct.new(:day => today,
+                                 :total => total_lines,
+                                 :covered => covered_lines,
+                                 :percent => percent)
+  File.open(GCOV_HIST_FILE, 'w') {|f| f.write(Marshal.dump(history))}
 end
 
@@ -451 +521 @@
   desc "Publish the gcoverage results"
   task :gcov => :gcov2html do
-    sh %{scp .rake/gcov_results.html www@davebalmain.com:/var/www/ferret}
+    sh "scp .rake/gcov_results.html .rake/gcov_history.jpg " + 
+         "www@davebalmain.com:/var/www/ferret"
   end
 end

c/include/internal.h

@@ -738 +738 @@
 #define phq_append_multi_term                   frt_phq_append_multi_term
 #define phq_new                                 frt_phq_new
+#define phq_set_slop                            frt_phq_set_slop
 #define pl_add_occ                              frt_pl_add_occ
 #define pl_cmp                                  frt_pl_cmp

c/include/search.h

@@ -326 +326 @@
 extern void frt_phq_add_term_abs(FrtQuery *self, const char *term, int position);
 extern void frt_phq_append_multi_term(FrtQuery *self, const char *term);
+extern void frt_phq_set_slop(FrtQuery *self, int slop);
 
 /***************************************************************************

c/src/index.c

@@ -366 +366 @@
 FieldInfo *fis_get_field(FieldInfos *fis, Symbol name)
 {
-    return (FieldInfo *)h_get(fis->field_dict, name);
+    return (FieldInfo *)h_get(fis->field_dict, I(name));
 }
 
 int fis_get_field_num(FieldInfos *fis, Symbol name)
 {
-    FieldInfo *fi = (FieldInfo *)h_get(fis->field_dict, name);
+    FieldInfo *fi = (FieldInfo *)h_get(fis->field_dict, I(name));
     if (fi) {
         return fi->number;
@@ -382 +382 @@
 FieldInfo *fis_get_or_add_field(FieldInfos *fis, Symbol name)
 {
-    FieldInfo *fi = (FieldInfo *)h_get(fis->field_dict, name);
+    FieldInfo *fi = (FieldInfo *)h_get(fis->field_dict, I(name));
     if (!fi) {
         fi = (FieldInfo*)fi_new(name, fis->store, fis->index, fis->term_vector);
@@ -4548 +4548 @@
                                   Symbol field)
 {
-    FieldInfo *fi = (FieldInfo *)h_get(ir->fis->field_dict, field);
+    FieldInfo *fi = (FieldInfo *)h_get(ir->fis->field_dict, I(field));
     FieldsReader *fr;
 

c/src/q_fuzzy.c

@@ -8 +8 @@
  * FuzzyStuff
  *
- * The main method here is the fuzq_score method which scores a term against
- * another term. The other methods all act in support.
+ * The main method here is the fuzq_score_mn method which scores a term
+ * against another term. The other methods all act in support.
+ *
+ * To learn more about the fuzzy scoring algorithm see;
+ *
+ *     http://en.wikipedia.org/wiki/Levenshtein_distance
  *
  ****************************************************************************/
 
+/**
+ * Calculate the maximum nomber of allowed edits (or maximum edit distance)
+ * for a word to be a match.
+ *
+ * Note that fuzq->text_len and m are both the lengths text *after* the prefix
+ * so `MIN(fuzq->text_len, m) + fuzq->pre_len)` actually gets the byte length
+ * of the shorter string out of the query string and the index term being
+ * compared.
+ */
 static INLINE int fuzq_calculate_max_distance(FuzzyQuery *fuzq, int m)
 {
@@ -18 +31 @@
 }
 
+/**
+ * The max-distance formula gets used a lot - it needs to be calculated for
+ * every possible match in the index - so we cache the results for all
+ * lengths up to the TYPICAL_LONGEST_WORD limit. For words longer than this we
+ * calculate the value live.
+ */
 static void fuzq_initialize_max_distances(FuzzyQuery *fuzq)
 {
@@ -26 +45 @@
 }
 
+/**
+ * Return the cached max-distance value if the word is within the
+ * TYPICAL_LONGEST_WORD limit.
+ */
 static INLINE int fuzq_get_max_distance(FuzzyQuery *fuzq, int m)
 {
@@ -33 +56 @@
 }
 
+/**
+ * Calculate the similarity score for the +target+ against the query.
+ *
+ * @params fuzq The Fuzzy Query
+ * @params target *the term to compare against minus the prefix
+ * @params m the string length of +target+
+ * @params n the string length of the query string minus length of the prefix
+ */
 static INLINE float fuzq_score_mn(FuzzyQuery *fuzq,
                                   const char *target,
@@ -173 +204 @@
     }
 
-    if (te == NULL) {
-        if (prefix) free(prefix);
-        return q;
-    }
+    assert(NULL != te);
 
     fuzq->scale_factor = (float)(1.0 / (1.0 - fuzq->min_sim));

c/src/q_phrase.c

@@ -117 +117 @@
 static bool pp_less_than(const PhPos *pp1, const PhPos *pp2)
 {
-    /* docs will all be equal when this method is used */
-    return pp1->position < pp2->position;
-    /*
-    if (PP(p)->doc == PP(p)->doc) {
-        return PP(p)->position < PP(p)->position;
+    if (pp1->position == pp2->position) {
+        return pp1->offset < pp2->offset;
     }
     else {
-        return PP(p)->doc < PP(p)->doc;
-    }
-    */
+        return pp1->position < pp2->position;
+    }
 }
 
@@ -168 +164 @@
     bool    first_time : 1;
     bool    more : 1;
+    bool    check_repeats : 1;
 } PhraseScorer;
 
@@ -235 +232 @@
     return raw_score * sim_decode_norm(
         self->similarity,
-        phsc->norms[phsc->phrase_pos[phsc->pp_first_idx]->doc]);
+        phsc->norms[self->doc]);
 }
 
@@ -279 +276 @@
     phsc_skip_to(self, doc_num);
 
-    phrase_freq = (self->doc == doc_num) ? phsc->freq : (float)0.0;
+    phrase_freq = (self->doc == doc_num) ? phsc->freq : 0.0f;
     return expl_new(sim_tf(self->similarity, phrase_freq),
                     "tf(phrase_freq=%f)", phrase_freq);
@@ -295 +292 @@
 }
 
-static Scorer *phsc_new(Weight *weight, TermDocEnum **term_pos_enum,
+static Scorer *phsc_new(Weight *weight,
+                        TermDocEnum **term_pos_enum,
                         PhrasePosition *positions, int pos_cnt,
-                        Similarity *similarity, uchar *norms)
+                        Similarity *similarity,
+                        uchar *norms,
+                        int slop)
 {
     int i;
     Scorer *self                = scorer_new(PhraseScorer, similarity);
+    HashSet *term_set           = NULL;
+
 
     PhSc(self)->weight          = weight;
@@ -308 +310 @@
     PhSc(self)->pp_first_idx    = 0;
     PhSc(self)->pp_cnt          = pos_cnt;
-    PhSc(self)->slop            = 0;
+    PhSc(self)->slop            = slop;
     PhSc(self)->first_time      = true;
     PhSc(self)->more            = true;
-
+    PhSc(self)->check_repeats   = false;
+    
+    if (slop) {
+        term_set = hs_new_str((free_ft)NULL);
+    }
     for (i = 0; i < pos_cnt; i++) {
+        /* check for repeats */
+        if (slop && !PhSc(self)->check_repeats) {
+            char **terms = positions[i].terms;
+            const int t_cnt = ary_size(terms);
+            int j;
+            for (j = 0; j < t_cnt; j++) {
+                if (hs_add(term_set, terms[j])) {
+                    PhSc(self)->check_repeats = true;
+                    goto repeat_check_done;
+                }
+            }
+        }
+repeat_check_done:
         PhSc(self)->phrase_pos[i] = pp_new(term_pos_enum[i], positions[i].pos);
+    }
+
+    if (slop) {
+        hs_destroy(term_set);
     }
 
@@ -376 +399 @@
                                        Similarity *similarity, uchar *norms)
 {
-    Scorer *self =
-        phsc_new(weight, term_pos_enum, positions, pp_cnt, similarity, norms);
+    Scorer *self = phsc_new(weight,
+                            term_pos_enum,
+                            positions,
+                            pp_cnt,
+                            similarity,
+                            norms,
+                            0);
 
     PhSc(self)->phrase_freq = &ephsc_phrase_freq;
@@ -386 +414 @@
  * SloppyPhraseScorer
  ***************************************************************************/
+
+static bool sphsc_check_repeats(PhPos *pp,
+                                PhPos **positions,
+                                const int p_cnt)
+{
+    int j;
+    for (j = 0; j < p_cnt; j++) {
+        PhPos *ppj = positions[j];
+        /* If offsets are equal, either we are at the current PhPos +pp+ or
+         * +pp+ and +ppj+ are supposed to match in the same position in which
+         * case we don't need to check. */
+        if (ppj->offset == pp->offset) {
+            continue;
+        }
+        /* the two phrase positions are matching on the same term
+         * which we want to avoid */
+        if ((ppj->position + ppj->offset) == (pp->position + pp->offset)) {
+            if (!pp_next_position(pp)) {
+                /* We have no matches for this document */
+                return false;
+            }
+            /* we changed the position so we need to start check again */
+            j = -1;
+        }
+    }
+    return true;
+}
 
 static float sphsc_phrase_freq(Scorer *self)
@@ -396 +451 @@
     int last_pos = 0, pos, next_pos, start, match_length, i;
     bool done = false;
+    bool check_repeats = phsc->check_repeats;
     float freq = 0.0;
 
     for (i = 0; i < pp_cnt; i++) {
         pp = phsc->phrase_pos[i];
-        pp_first_position(pp);
+        /* we should always have at least one position or this functions
+         * shouldn't have been called. */
+        assert(pp_first_position(pp));
+        if (check_repeats && i > 0) {
+            if (!sphsc_check_repeats(pp, phsc->phrase_pos, i - 1)) {
+                goto return_freq;
+            }
+        }
         if (pp->position > last_pos) {
             last_pos = pp->position;
@@ -413 +476 @@
         while (pos <= next_pos) {
             start = pos;        /* advance pp to min window */
-            if (!pp_next_position(pp)) {
-                done = true;    /* ran out of a positions for a term - done */
+            if (!pp_next_position(pp)
+                || (check_repeats
+                    && !sphsc_check_repeats(pp, phsc->phrase_pos, pp_cnt))) {
+                done = true;
                 break;
             }
@@ -431 +496 @@
         pq_push(pq, pp);        /* restore pq */
     } while (!done);
+
+return_freq:
 
     pq_destroy(pq);
@@ -442 +509 @@
                                         int slop, uchar *norms)
 {
-    Scorer *self =
-        phsc_new(weight, term_pos_enum, positions, pp_cnt, similarity, norms);
-
-    PhSc(self)->slop        = slop;
+    Scorer *self = phsc_new(weight,
+                            term_pos_enum,
+                            positions,
+                            pp_cnt,
+                            similarity,
+                            norms,
+                            slop);
+
     PhSc(self)->phrase_freq = &sphsc_phrase_freq;
     return self;
@@ -1125 +1196 @@
     }
 }
+
+void frt_phq_set_slop(FrtQuery *self, int slop)
+{
+    PhQ(self)->slop = slop;
+}

c/test/test.c

@@ -259 +259 @@
 
     dptr = suite->head;
-    fprintf(stdout, "%-15s\t\tTotal\tFail\tFailed %%\n", "Failed Tests");
+    fprintf(stdout, "%-24sTotal\tFail\tFailed %%\n", "Failed Tests");
     fprintf(stdout, "===================================================\n");
     while (dptr != NULL) {
@@ -265 +265 @@
             double percent =
                 ((double) dptr->failed / (double) dptr->num_test);
-            fprintf(stdout, "%-15s\t\t%5d\t%4d\t%6.2f%%\n", dptr->name,
+            fprintf(stdout, "%-24s%5d\t%4d\t%6.2f%%\n", dptr->name,
                     dptr->num_test, dptr->failed, percent * 100);
         }
@@ -456 +456 @@
         return true;
     }
+    fprintf(stderr, "diff = %g\n", diff);
 
     tc->failed = true;

c/test/test_bitvector.c

@@ -147 +147 @@
 }
 
+#define test_bveq(_bv1, _bv2)                                       \
+do {                                                                \
+    BitVector *_not_bv1, *_not_bv2;                                 \
+    Assert(bv_eq(_bv1, _bv2), "BitVectors are equal");              \
+    Assert(bv_eq(_bv2, _bv1), "BitVectors are equal");              \
+    Assert(bv_eq(_bv1, _bv1), "bv_eq on self should work");         \
+    Aiequal(bv_hash(_bv1), bv_hash(_bv2));                          \
+    /* test flipped bitvectors */                                   \
+    _not_bv1 = bv_not(_bv1); _not_bv2 = bv_not(_bv2);               \
+    bv_set(_not_bv1, 1100); /* should make no difference */         \
+    Assert(bv_eq(_not_bv1, _not_bv2), "BitVectors are equal");      \
+    Assert(bv_eq(_not_bv2, _not_bv1), "BitVectors are equal");      \
+    Assert(bv_eq(_not_bv1, _not_bv1), "bv_eq on self should work"); \
+    Aiequal(bv_hash(_not_bv1), bv_hash(_not_bv2));                  \
+    bv_destroy(_not_bv1); bv_destroy(_not_bv2);                     \
+} while (0)
+
+#define test_bvneq(_bv1, _bv2)                                      \
+do {                                                                \
+    BitVector *_not_bv1, *_not_bv2;                                 \
+    Assert(!bv_eq(_bv1, _bv2), "BitVectors are not equal");         \
+    Assert(!bv_eq(_bv2, _bv1), "BitVectors are not equal");         \
+    Assert(bv_hash(_bv1) != bv_hash(_bv2), "BitVectors not equal"); \
+    /* test flipped bitvectors */                                   \