lib/fstrcmp.c

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