subversion/svn/similarity.c

/*
 * similarity.c: Utility functions for finding similar strings in lists
 *
 * ====================================================================
 *    Licensed to the Apache Software Foundation (ASF) under one
 *    or more contributor license agreements.  See the NOTICE file
 *    distributed with this work for additional information
 *    regarding copyright ownership.  The ASF licenses this file
 *    to you under the Apache License, Version 2.0 (the
 *    "License"); you may not use this file except in compliance
 *    with the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing,
 *    software distributed under the License is distributed on an
 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *    KIND, either express or implied.  See the License for the
 *    specific language governing permissions and limitations
 *    under the License.
 * ====================================================================
 */

/* ==================================================================== */



/*** Includes. ***/

#include <stdlib.h>

#include "svn_string.h"
#include "cl.h"

#include "private/svn_string_private.h"

#include "svn_private_config.h"


/* Context for token similarity checking */
struct svn_cl__simcheck_context_t
{
  svn_string_t key;             /* The token we're comparing with */
  svn_membuf_t buffer;          /* Buffer for similarity testing */
};


/* Similarity test between two property names */
static APR_INLINE apr_size_t
simcheck_key_diff(const svn_string_t *key, const svn_string_t *ctx,
                 svn_membuf_t *buffer, apr_size_t *diff)
{
  apr_size_t lcs;
  const apr_size_t score = svn_string__similarity(key, ctx, buffer, &lcs);
  if (key->len > ctx->len)
    *diff = key->len - lcs;
  else
    *diff = ctx->len - lcs;
  return score;
}


/* Key comparator for qsort for svn_cl__simcheck_t */
static int
simcheck_compare(const void *pkeya, const void *pkeyb)
{
  svn_cl__simcheck_t *const keya = *(svn_cl__simcheck_t *const *)pkeya;
  svn_cl__simcheck_t *const keyb = *(svn_cl__simcheck_t *const *)pkeyb;
  svn_cl__simcheck_context_t *const context = keya->context;

  if (keya->score == -1)
    keya->score = simcheck_key_diff(&keya->token, &context->key,
                                    &context->buffer, &keya->diff);
  if (keyb->score == -1)
    keyb->score = simcheck_key_diff(&keyb->token, &context->key,
                                    &context->buffer, &keyb->diff);

  return (keya->score < keyb->score ? 1
          : (keya->score > keyb->score ? -1
             : (keya->diff > keyb->diff ? 1
                : (keya->diff < keyb->diff ? -1 : 0))));
}

apr_size_t
svn_cl__similarity_check(const char *key,
                         svn_cl__simcheck_t **tokens,
                         apr_size_t token_count,
                         apr_pool_t *scratch_pool)
{
  apr_size_t result;
  apr_size_t i;

  svn_cl__simcheck_context_t context;
  context.key.data = key;
  context.key.len = strlen(key);
  svn_membuf__create(&context.buffer, 0, scratch_pool);

  /* Populate the score, diff and context members. */
  for (i = 0; i < token_count; ++i)
    {
      svn_cl__simcheck_t *const token = tokens[i];
      token->score = -1;
      token->diff = 0;
      token->context = &context;
    }

  /* Sort the tokens by similarity. */
  qsort(tokens, token_count, sizeof(*tokens), simcheck_compare);

  /* Remove references to the context, since it points to the stack,
     and calculate the number of results that are at least two-thirds
     similar to the key. */
  for (i = 0, result = 1; i < token_count; ++i)
    {
      svn_cl__simcheck_t *const token = tokens[i];
      token->context = NULL;
      /* If you update this factor, consider updating
       * ../libsvn_subr/cmdline.c:most_similar(). */
      if (token->score >= (2 * SVN_STRING__SIM_RANGE_MAX + 1) / 3)
        ++result;
    }

  if (0 == tokens[0]->diff)
    return 0;                   /* We found an exact match. */
  return result;
}