On Fri, May 29, 2020 at 6:21 PM Pip Cet <pip...@gmail.com> wrote:
> IIRC, minimum string alignment does not satisfy the triangle
> inequality anyway, so test_metric_conditions should probably not
> pretend to test it...
I did remember correctly, though of course that should have been
"optimal string alignment" :-). If you change the spellcheck.c
test_data array to include "abc", "ac", and "ca", the self-test will
fail, even without your patch.
I think we should just omit the triangle inequality test from the
self-test, as in the attached patch.
From bbb8b5cd7368f471bcbdbe451591e74315a5adcd Mon Sep 17 00:00:00 2001
From: Pip Cet <pip...@gmail.com>
Date: Sat, 30 May 2020 13:39:09 +0000
Subject: [PATCH] Don't test the triangle inequality in the spellcheck.c
self-test.
* spellcheck.c (test_data): Add problematic strings.
(test_metric_conditions): Don't test the triangle inequality
condition, which our distance function does not satisfy.
---
gcc/ChangeLog | 6 ++++++
gcc/spellcheck.c | 19 +++++--------------
2 files changed, 11 insertions(+), 14 deletions(-)
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4fc37369d39..e565d8ecadf 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2020-05-30 Pip Cet <pip...@gmail.com>
+
+ * spellcheck.c (test_data): Add problematic strings.
+ (test_metric_conditions): Don't test the triangle inequality
+ condition, which our distance function does not satisfy.
+
2020-05-28 Nicolas Bértolo <nicolasbert...@gmail.com>
* Makefile.in: don't look for libiberty in the "pic" subdirectory
diff --git a/gcc/spellcheck.c b/gcc/spellcheck.c
index 7891260a258..1d2df070445 100644
--- a/gcc/spellcheck.c
+++ b/gcc/spellcheck.c
@@ -438,13 +438,14 @@ static const char * const test_data[] = {
"food",
"boo",
"1234567890123456789012345678901234567890123456789012345678901234567890"
+ "abc",
+ "ac",
+ "ca",
};
/* Verify that get_edit_distance appears to be a sane distance function,
- i.e. the conditions for being a metric. This is done directly for a
- small set of examples, using test_data above. This is O(N^3) in the size
- of the array, due to the test for the triangle inequality, so we keep the
- array small. */
+ even though it doesn't satisfy the conditions for being a metric. This
+ is done directly for a small set of examples, using test_data above. */
static void
test_metric_conditions ()
@@ -468,16 +469,6 @@ test_metric_conditions ()
edit_distance_t dist_ji
= get_edit_distance (test_data[j], test_data[i]);
ASSERT_EQ (dist_ij, dist_ji);
-
- /* Triangle inequality. */
- for (int k = 0; k < num_test_cases; k++)
- {
- edit_distance_t dist_ik
- = get_edit_distance (test_data[i], test_data[k]);
- edit_distance_t dist_jk
- = get_edit_distance (test_data[j], test_data[k]);
- ASSERT_TRUE (dist_ik <= dist_ij + dist_jk);
- }
}
}
}
--
2.27.0.rc0
