Author: brane
Date: Tue Feb 17 19:33:18 2015
New Revision: 1660474
URL: http://svn.apache.org/r1660474
Log:
On the svn-info-detail branch: Increase the range of the string
similarity test result and factor the similar-string search out
of svn_cl__check_prop_name into a separate client-local function.
* subversion/include/private/svn_string_private.h
(SVN_STRING__SIM_RANGE_MAX): New; parametrized the similarity range.
(svn_cstring__similarity): Update docstring and adjust return type.
(svn_string__similarity): Adjust return type.
* subversion/libsvn_subr/string.c
(svn_cstring__similarity): Adjust return type.
(svn_string__similarity): Adjust return type. Change the result range.
* subversion/svn/cl.h
(svn_cl__simcheck_context_t): New forward-declared struct.
(svn_cl__simcheck_t): New structure.
(svn_cl__similarity_check): New client-local function.
* subversion/svn/props.c
(simprop_context_t, simprop_t): Removed in favour of the new
svn_cl__simcheck_context_t and svn_cl__simcheck_t.
(simprop_key_diff, simprop_compare): Moved to similarity.c.
(svn_cl__check_svn_prop_name): Use the new similarity check API.
* subversion/svn/similarity.c: New file.
(svn_cl__simcheck_context_t): Defined here.
(simcheck_key_diff): Replaces simprop_key_diff from props.c.
(simcheck_compare): Replaces simprop_compare from props.c.
(svn_cl__similarity_check): Implement.
* subversion/tests/libsvn_subr/string-test.c
(test_string_similarity): Adjust test case to account for the
changed range of the result of svn_string__similarity.
Added:
subversion/branches/svn-info-detail/subversion/svn/similarity.c (with
props)
Modified:
subversion/branches/svn-info-detail/subversion/include/private/svn_string_private.h
subversion/branches/svn-info-detail/subversion/libsvn_subr/string.c
subversion/branches/svn-info-detail/subversion/svn/cl.h
subversion/branches/svn-info-detail/subversion/svn/props.c
subversion/branches/svn-info-detail/subversion/tests/libsvn_subr/string-test.c
Modified:
subversion/branches/svn-info-detail/subversion/include/private/svn_string_private.h
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-info-detail/subversion/include/private/svn_string_private.h?rev=1660474&r1=1660473&r2=1660474&view=diff
==============================================================================
---
subversion/branches/svn-info-detail/subversion/include/private/svn_string_private.h
(original)
+++
subversion/branches/svn-info-detail/subversion/include/private/svn_string_private.h
Tue Feb 17 19:33:18 2015
@@ -197,10 +197,17 @@ apr_uint64_t
svn__base36toui64(const char **next, const char *source);
/**
+ * The upper limit of the similarity range returned by
+ * svn_cstring__similarity() and svn_string__similarity().
+ */
+#define SVN_STRING__SIM_RANGE_MAX 1000000
+
+/**
* Computes the similarity score of STRA and STRB. Returns the ratio
* of the length of their longest common subsequence and the average
- * length of the strings, normalized to the range [0..1000].
- * The result is equivalent to Python's
+ * length of the strings, normalized to the range
+ * [0..SVN_STRING__SIM_RANGE_MAX]. The result is equivalent to
+ * Python's
*
* difflib.SequenceMatcher.ratio
*
@@ -225,7 +232,7 @@ svn__base36toui64(const char **next, con
* has O(strlen(STRA) * strlen(STRB)) worst-case performance,
* so do keep a rein on your enthusiasm.
*/
-unsigned int
+apr_size_t
svn_cstring__similarity(const char *stra, const char *strb,
svn_membuf_t *buffer, apr_size_t *rlcs);
@@ -233,7 +240,7 @@ svn_cstring__similarity(const char *stra
* Like svn_cstring__similarity, but accepts svn_string_t's instead
* of NUL-terminated character strings.
*/
-unsigned int
+apr_size_t
svn_string__similarity(const svn_string_t *stringa,
const svn_string_t *stringb,
svn_membuf_t *buffer, apr_size_t *rlcs);
Modified: subversion/branches/svn-info-detail/subversion/libsvn_subr/string.c
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-info-detail/subversion/libsvn_subr/string.c?rev=1660474&r1=1660473&r2=1660474&view=diff
==============================================================================
--- subversion/branches/svn-info-detail/subversion/libsvn_subr/string.c
(original)
+++ subversion/branches/svn-info-detail/subversion/libsvn_subr/string.c Tue Feb
17 19:33:18 2015
@@ -1300,7 +1300,7 @@ svn__base36toui64(const char **next, con
}
-unsigned int
+apr_size_t
svn_cstring__similarity(const char *stra, const char *strb,
svn_membuf_t *buffer, apr_size_t *rlcs)
{
@@ -1312,7 +1312,7 @@ svn_cstring__similarity(const char *stra
return svn_string__similarity(&stringa, &stringb, buffer, rlcs);
}
-unsigned int
+apr_size_t
svn_string__similarity(const svn_string_t *stringa,
const svn_string_t *stringb,
svn_membuf_t *buffer, apr_size_t *rlcs)
@@ -1401,9 +1401,9 @@ svn_string__similarity(const svn_string_
/* Return similarity ratio rounded to 4 significant digits */
if (total)
- return(unsigned int)((2000 * lcs + total/2) / total);
+ return ((2 * SVN_STRING__SIM_RANGE_MAX * lcs + total/2) / total);
else
- return 1000;
+ return SVN_STRING__SIM_RANGE_MAX;
}
apr_size_t
Modified: subversion/branches/svn-info-detail/subversion/svn/cl.h
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-info-detail/subversion/svn/cl.h?rev=1660474&r1=1660473&r2=1660474&view=diff
==============================================================================
--- subversion/branches/svn-info-detail/subversion/svn/cl.h (original)
+++ subversion/branches/svn-info-detail/subversion/svn/cl.h Tue Feb 17 19:33:18
2015
@@ -855,6 +855,48 @@ svn_cl__deprecated_merge_reintegrate(con
svn_client_ctx_t *ctx,
apr_pool_t *pool);
+
+/* Forward declaration of the similarity check context. */
+typedef struct svn_cl__simcheck_context_t svn_cl__simcheck_context_t;
+
+/* Token definition for the similarity check. */
+typedef struct svn_cl__simcheck_t
+{
+ /* The token we're checking for similarity. */
+ svn_string_t token;
+
+ /* User data associated with this token. */
+ const void *data;
+
+ /*
+ * The following fields are populated by svn_cl__similarity_check.
+ */
+
+ /* Similarity score [0..SVN_STRING__SIM_RANGE_MAX] */
+ apr_size_t score;
+
+ /* Number of characters of difference from the key. */
+ apr_size_t diff;
+
+ /* Similarity check context (private) */
+ svn_cl__simcheck_context_t *context;
+} svn_cl__simcheck_t;
+
+/* Find the entries in TOKENS that are most similar to KEY.
+ * TOKEN_COUNT is the number of entries in the (mutable) TOKENS array.
+ * Use SCRATCH_POOL for temporary allocations.
+ *
+ * On return, the TOKENS array will be sorted according to similarity
+ * to KEY, in descending order. The return value will be zero if the
+ * first token is an exact match; otherwise, it will be one more than
+ * the number of tokens that are at least two-thirds similar to KEY.
+ */
+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);
+
#ifdef __cplusplus
}
#endif /* __cplusplus */
Modified: subversion/branches/svn-info-detail/subversion/svn/props.c
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-info-detail/subversion/svn/props.c?rev=1660474&r1=1660473&r2=1660474&view=diff
==============================================================================
--- subversion/branches/svn-info-detail/subversion/svn/props.c (original)
+++ subversion/branches/svn-info-detail/subversion/svn/props.c Tue Feb 17
19:33:18 2015
@@ -112,59 +112,6 @@ svn_cl__check_boolean_prop_val(const cha
}
}
-
-/* Context for sorting property names */
-struct simprop_context_t
-{
- svn_string_t name; /* The name of the property we're comparing with */
- svn_membuf_t buffer; /* Buffer for similarity testing */
-};
-
-struct simprop_t
-{
- const char *propname; /* The original svn: property name */
- svn_string_t name; /* The property name without the svn: prefix */
- unsigned int score; /* The similarity score */
- apr_size_t diff; /* Number of chars different from context.name */
- struct simprop_context_t *context; /* Sorting context for qsort() */
-};
-
-/* Similarity test between two property names */
-static APR_INLINE unsigned int
-simprop_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 unsigned int 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 simprop_t */
-static int
-simprop_compare(const void *pkeya, const void *pkeyb)
-{
- struct simprop_t *const keya = *(struct simprop_t *const *)pkeya;
- struct simprop_t *const keyb = *(struct simprop_t *const *)pkeyb;
- struct simprop_context_t *const context = keya->context;
-
- if (keya->score == -1)
- keya->score = simprop_key_diff(&keya->name, &context->name,
- &context->buffer, &keya->diff);
- if (keyb->score == -1)
- keyb->score = simprop_key_diff(&keyb->name, &context->name,
- &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))));
-}
-
-
static const char*
force_prop_option_message(svn_cl__prop_use_t prop_use, const char *prop_name,
apr_pool_t *scratch_pool)
@@ -239,33 +186,34 @@ svn_cl__check_svn_prop_name(const char *
const char *const *const proplist = (revprop ? revprops : nodeprops);
const apr_size_t numprops = (revprop ? revprops_len : nodeprops_len);
- struct simprop_t **propkeys;
- struct simprop_t *propbuf;
+ svn_cl__simcheck_t **propkeys;
+ svn_cl__simcheck_t *propbuf;
apr_size_t i;
- struct simprop_context_t context;
+ svn_string_t propstring;
svn_string_t prefix;
+ svn_membuf_t buffer;
- context.name.data = propname;
- context.name.len = strlen(propname);
+ propstring.data = propname;
+ propstring.len = strlen(propname);
prefix.data = SVN_PROP_PREFIX;
prefix.len = strlen(SVN_PROP_PREFIX);
- svn_membuf__create(&context.buffer, 0, scratch_pool);
+ svn_membuf__create(&buffer, 0, scratch_pool);
/* First, check if the name is even close to being in the svn: namespace.
It must contain a colon in the right place, and we only allow
one-char typos or a single transposition. */
- if (context.name.len < prefix.len
- || context.name.data[prefix.len - 1] != prefix.data[prefix.len - 1])
+ if (propstring.len < prefix.len
+ || propstring.data[prefix.len - 1] != prefix.data[prefix.len - 1])
return SVN_NO_ERROR; /* Wrong prefix, ignore */
else
{
apr_size_t lcs;
- const apr_size_t name_len = context.name.len;
- context.name.len = prefix.len; /* Only check up to the prefix length */
- svn_string__similarity(&context.name, &prefix, &context.buffer, &lcs);
- context.name.len = name_len; /* Restore the original propname length */
+ const apr_size_t name_len = propstring.len;
+ propstring.len = prefix.len; /* Only check up to the prefix length */
+ svn_string__similarity(&propstring, &prefix, &buffer, &lcs);
+ propstring.len = name_len; /* Restore the original propname length */
if (lcs < prefix.len - 1)
return SVN_NO_ERROR; /* Wrong prefix, ignore */
@@ -292,55 +240,47 @@ svn_cl__check_svn_prop_name(const char *
we already know that it's the same and looking at it would only
skew the results. */
propkeys = apr_palloc(scratch_pool,
- numprops * sizeof(struct simprop_t*));
+ numprops * sizeof(svn_cl__simcheck_t*));
propbuf = apr_palloc(scratch_pool,
- numprops * sizeof(struct simprop_t));
- context.name.data += prefix.len;
- context.name.len -= prefix.len;
+ numprops * sizeof(svn_cl__simcheck_t));
+ propstring.data += prefix.len;
+ propstring.len -= prefix.len;
for (i = 0; i < numprops; ++i)
{
propkeys[i] = &propbuf[i];
- propbuf[i].propname = proplist[i];
- propbuf[i].name.data = proplist[i] + prefix.len;
- propbuf[i].name.len = strlen(propbuf[i].name.data);
- propbuf[i].score = (unsigned int)-1;
- propbuf[i].context = &context;
+ propbuf[i].token.data = proplist[i] + prefix.len;
+ propbuf[i].token.len = strlen(propbuf[i].token.data);
+ propbuf[i].data = proplist[i];
}
- qsort(propkeys, numprops, sizeof(*propkeys), simprop_compare);
-
- if (0 == propkeys[0]->diff)
- return SVN_NO_ERROR; /* We found an exact match. */
-
- /* See if we can suggest a sane alternative spelling */
- for (i = 0; i < numprops; ++i)
- if (propkeys[i]->score < 666) /* 2/3 similarity required */
- break;
-
- switch (i)
+ switch (svn_cl__similarity_check(
+ propstring.data, propkeys, numprops, scratch_pool))
{
case 0:
+ return SVN_NO_ERROR; /* We found an exact match. */
+
+ case 1:
/* The best alternative isn't good enough */
return svn_error_create(
SVN_ERR_CLIENT_PROPERTY_NAME, NULL,
wrong_prop_error_message(prop_use, propname, scratch_pool));
- case 1:
+ case 2:
/* There is only one good candidate */
return svn_error_createf(
SVN_ERR_CLIENT_PROPERTY_NAME, NULL,
_("'%s' is not a valid %s property name; did you mean '%s'?\n%s"),
- propname, SVN_PROP_PREFIX, propkeys[0]->propname,
+ propname, SVN_PROP_PREFIX, propkeys[0]->data,
force_prop_option_message(prop_use, propname, scratch_pool));
- case 2:
+ case 3:
/* Suggest a list of the most likely candidates */
return svn_error_createf(
SVN_ERR_CLIENT_PROPERTY_NAME, NULL,
_("'%s' is not a valid %s property name\n"
"Did you mean '%s' or '%s'?\n%s"),
propname, SVN_PROP_PREFIX,
- propkeys[0]->propname, propkeys[1]->propname,
+ propkeys[0]->data, propkeys[1]->data,
force_prop_option_message(prop_use, propname, scratch_pool));
default:
@@ -350,7 +290,7 @@ svn_cl__check_svn_prop_name(const char *
_("'%s' is not a valid %s property name\n"
"Did you mean '%s', '%s' or '%s'?\n%s"),
propname, SVN_PROP_PREFIX,
- propkeys[0]->propname, propkeys[1]->propname, propkeys[2]->propname,
+ propkeys[0]->data, propkeys[1]->data, propkeys[2]->data,
force_prop_option_message(prop_use, propname, scratch_pool));
}
}
Added: subversion/branches/svn-info-detail/subversion/svn/similarity.c
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-info-detail/subversion/svn/similarity.c?rev=1660474&view=auto
==============================================================================
--- subversion/branches/svn-info-detail/subversion/svn/similarity.c (added)
+++ subversion/branches/svn-info-detail/subversion/svn/similarity.c Tue Feb 17
19:33:18 2015
@@ -0,0 +1,124 @@
+/*
+ * 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 (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;
+}
Propchange: subversion/branches/svn-info-detail/subversion/svn/similarity.c
------------------------------------------------------------------------------
svn:eol-style = native
Modified:
subversion/branches/svn-info-detail/subversion/tests/libsvn_subr/string-test.c
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-info-detail/subversion/tests/libsvn_subr/string-test.c?rev=1660474&r1=1660473&r2=1660474&view=diff
==============================================================================
---
subversion/branches/svn-info-detail/subversion/tests/libsvn_subr/string-test.c
(original)
+++
subversion/branches/svn-info-detail/subversion/tests/libsvn_subr/string-test.c
Tue Feb 17 19:33:18 2015
@@ -686,10 +686,11 @@ test_string_similarity(apr_pool_t *pool)
unsigned int score;
} tests[] =
{
-#define SCORE(lcs, len) ((2000 * (lcs) + (len)/2) / (len))
+#define SCORE(lcs, len) \
+ ((2 * SVN_STRING__SIM_RANGE_MAX * (lcs) + (len)/2) / (len))
/* Equality */
- {"", "", 0, 1000},
+ {"", "", 0, SVN_STRING__SIM_RANGE_MAX},
{"quoth", "quoth", 5, SCORE(5, 5+5)},
/* Deletion at start */
@@ -743,17 +744,20 @@ test_string_similarity(apr_pool_t *pool)
for (t = tests; t->stra; ++t)
{
apr_size_t lcs;
- const unsigned int score =
+ const apr_size_t score =
svn_cstring__similarity(t->stra, t->strb, &buffer, &lcs);
/*
fprintf(stderr,
- "lcs %s ~ %s score %.3f (%"APR_SIZE_T_FMT
- ") expected %.3f (%"APR_SIZE_T_FMT"))\n",
- t->stra, t->strb, score/1000.0, lcs, t->score/1000.0, t->lcs);
+ "lcs %s ~ %s score %.6f (%"APR_SIZE_T_FMT
+ ") expected %.6f (%"APR_SIZE_T_FMT"))\n",
+ t->stra, t->strb, score/1.0/SVN_STRING__SIM_RANGE_MAX,
+ lcs, t->score/1.0/SVN_STRING__SIM_RANGE_MAX, t->lcs);
*/
if (score != t->score)
- return fail(pool, "%s ~ %s score %.3f <> expected %.3f",
- t->stra, t->strb, score/1000.0, t->score/1000.0);
+ return fail(pool, "%s ~ %s score %.6f <> expected %.6f",
+ t->stra, t->strb,
+ score/1.0/SVN_STRING__SIM_RANGE_MAX,
+ t->score/1.0/SVN_STRING__SIM_RANGE_MAX);
if (lcs != t->lcs)
return fail(pool,
@@ -766,7 +770,8 @@ test_string_similarity(apr_pool_t *pool)
{
const svn_string_t foo = {"svn:foo", 4};
const svn_string_t bar = {"svn:bar", 4};
- if (1000 != svn_string__similarity(&foo, &bar, &buffer, NULL))
+ if (SVN_STRING__SIM_RANGE_MAX
+ != svn_string__similarity(&foo, &bar, &buffer, NULL))
return fail(pool, "'%s'[:4] ~ '%s'[:4] found different",
foo.data, bar.data);
}
