lib/fstrcmp.c

   1 /* Functions to make fuzzy comparisons between strings
   2    Copyright (C) 1988-1989, 1992-1993, 1995, 2001-2003, 2006, 2008
   3    Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18
  19    Derived from GNU diff 2.7, analyze.c et al.
  20
  21    The basic idea is to consider two vectors as similar if, when
  22    transforming the first vector into the second vector through a
  23    sequence of edits (inserts and deletes of one element each),
  24    this sequence is short - or equivalently, if the ordered list
  25    of elements that are untouched by these edits is long.  For a
  26    good introduction to the subject, read about the "Levenshtein
  27    distance" in Wikipedia.
  28
  29    The basic algorithm is described in:
  30    "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
  31    Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
  32    see especially section 4.2, which describes the variation used below.
  33
  34    The basic algorithm was independently discovered as described in:
  35    "Algorithms for Approximate String Matching", E. Ukkonen,
  36    Information and Control Vol. 64, 1985, pp. 100-118.
  37
  38    Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
  39    heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
  40    at the price of producing suboptimal output for large inputs with
  41    many differences.  */
  42
  43 #include <config.h>
  44
  45 /* Specification.  */
  46 #include "fstrcmp.h"
  47
  48 #include <string.h>
  49 #include <stdbool.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <limits.h>
  53
  54 #include "glthread/lock.h"
  55 #include "glthread/tls.h"
  56 #include "minmax.h"
  57 #include "xalloc.h"
  58
  59 #ifndef uintptr_t
  60 # define uintptr_t unsigned long
  61 #endif
  62
  63
  64 #define ELEMENT char
  65 #define EQUAL(x,y) ((x) == (y))
  66 #define OFFSET int
  67 #define EXTRA_CONTEXT_FIELDS \
  68   /* The number of elements inserted or deleted. */ \
  69   int xvec_edit_count; \
  70   int yvec_edit_count;
  71 #define NOTE_DELETE(ctxt, xoff) ctxt->xvec_edit_count++
  72 #define NOTE_INSERT(ctxt, yoff) ctxt->yvec_edit_count++
  73 /* We don't need USE_HEURISTIC, since it is unlikely in typical uses of
  74    fstrcmp().  */
  75 #include "diffseq.h"
  76
  77
  78 /* Because fstrcmp is typically called multiple times, attempt to minimize
  79    the number of memory allocations performed.  Thus, let a call reuse the
  80    memory already allocated by the previous call, if it is sufficient.
  81    To make it multithread-safe, without need for a lock that protects the
  82    already allocated memory, store the allocated memory per thread.  Free
  83    it only when the thread exits.  */
  84
  85 static gl_tls_key_t buffer_key; /* TLS key for a 'int *' */
  86 static gl_tls_key_t bufmax_key; /* TLS key for a 'size_t' */
  87
  88 static void
  89 keys_init (void)
  90 {
  91   gl_tls_key_init (buffer_key, free);
  92   gl_tls_key_init (bufmax_key, NULL);
  93   /* The per-thread initial values are NULL and 0, respectively.  */
  94 }
  95
  96 /* Ensure that keys_init is called once only.  */
  97 gl_once_define(static, keys_init_once)
  98
  99
 100 /* NAME
 101         fstrcmp - fuzzy string compare
 102
 103    SYNOPSIS
 104         double fstrcmp(const char *, const char *);
 105
 106    DESCRIPTION
 107         The fstrcmp function may be used to compare two string for
 108         similarity.  It is very useful in reducing "cascade" or
 109         "secondary" errors in compilers or other situations where
 110         symbol tables occur.
 111
 112    RETURNS
 113         double; 0 if the strings are entirly dissimilar, 1 if the
 114         strings are identical, and a number in between if they are
 115         similar.  */
 116
 117 double
 118 fstrcmp (const char *string1, const char *string2)
 119 {
 120   struct context ctxt;
 121   int xvec_length;
 122   int yvec_length;
 123   int i;
 124
 125   size_t fdiag_len;
 126   int *buffer;
 127   size_t bufmax;
 128
 129   /* set the info for each string.  */
 130   ctxt.xvec = string1;
 131   xvec_length = strlen (string1);
 132   ctxt.yvec = string2;
 133   yvec_length = strlen (string2);
 134
 135   /* short-circuit obvious comparisons */
 136   if (xvec_length == 0 && yvec_length == 0)
 137     return 1.0;
 138   if (xvec_length == 0 || yvec_length == 0)
 139     return 0.0;
 140
 141   /* Set TOO_EXPENSIVE to be approximate square root of input size,
 142      bounded below by 256.  */
 143   ctxt.too_expensive = 1;
 144   for (i = xvec_length + yvec_length;
 145        i != 0;
 146        i >>= 2)
 147     ctxt.too_expensive <<= 1;
 148   if (ctxt.too_expensive < 256)
 149     ctxt.too_expensive = 256;
 150
 151   /* Allocate memory for fdiag and bdiag from a thread-local pool.  */
 152   fdiag_len = xvec_length + yvec_length + 3;
 153   gl_once (keys_init_once, keys_init);
 154   buffer = (int *) gl_tls_get (buffer_key);
 155   bufmax = (size_t) (uintptr_t) gl_tls_get (bufmax_key);
 156   if (fdiag_len > bufmax)
 157     {
 158       /* Need more memory.  */
 159       bufmax = 2 * bufmax;
 160       if (fdiag_len > bufmax)
 161         bufmax = fdiag_len;
 162       /* Calling xrealloc would be a waste: buffer's contents does not need
 163          to be preserved.  */
 164       if (buffer != NULL)
 165         free (buffer);
 166       buffer = (int *) xnmalloc (bufmax, 2 * sizeof (int));
 167       gl_tls_set (buffer_key, buffer);
 168       gl_tls_set (bufmax_key, (void *) (uintptr_t) bufmax);
 169     }
 170   ctxt.fdiag = buffer + yvec_length + 1;
 171   ctxt.bdiag = ctxt.fdiag + fdiag_len;
 172
 173   /* Now do the main comparison algorithm */
 174   ctxt.xvec_edit_count = 0;
 175   ctxt.yvec_edit_count = 0;
 176   compareseq (0, xvec_length, 0, yvec_length, 0,
 177               &ctxt);
 178
 179   /* The result is
 180         ((number of chars in common) / (average length of the strings)).
 181      This is admittedly biased towards finding that the strings are
 182      similar, however it does produce meaningful results.  */
 183   return ((double) (xvec_length + yvec_length
 184                     - ctxt.yvec_edit_count - ctxt.xvec_edit_count)
 185           / (xvec_length + yvec_length));
 186 }