From 7dbbdc150292fa9076ce8e3b2c6a8937214d03e0 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Fri, 30 Nov 2018 18:04:10 +0100 Subject: src: provide suggestion for misspelled object name MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Use this from the lookup path, to check for misspellings: # nft add table filter # nft add chain filtre test Error: No such file or directory; did you mean table ‘filter’ in family ip? add chain filtre test ^^^^^^ Signed-off-by: Pablo Neira Ayuso --- include/misspell.h | 13 ++++++++ src/Makefile.am | 1 + src/misspell.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/rule.c | 25 +++++++++++++-- 4 files changed, 127 insertions(+), 3 deletions(-) create mode 100644 include/misspell.h create mode 100644 src/misspell.c diff --git a/include/misspell.h b/include/misspell.h new file mode 100644 index 00000000..ba01e741 --- /dev/null +++ b/include/misspell.h @@ -0,0 +1,13 @@ +#ifndef _MISSPELL_H_ +#define _MISSPELL_H_ + +struct string_misspell_state { + unsigned int min_distance; + void *obj; +}; + +void string_misspell_init(struct string_misspell_state *st); +int string_misspell_update(const char *a, const char *b, + void *obj, struct string_misspell_state *st); + +#endif diff --git a/src/Makefile.am b/src/Makefile.am index 31d076cd..8e1a4d87 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -47,6 +47,7 @@ libnftables_la_SOURCES = \ netlink.c \ netlink_linearize.c \ netlink_delinearize.c \ + misspell.c \ monitor.c \ segtree.c \ rbtree.c \ diff --git a/src/misspell.c b/src/misspell.c new file mode 100644 index 00000000..23290819 --- /dev/null +++ b/src/misspell.c @@ -0,0 +1,91 @@ +#include +#include +#include +#include +#include + +enum string_distance_function { + DELETION = 0, /* m1 */ + INSERTION, /* m2 */ + TRANSFORMATION, /* m3 */ +}; +#define DISTANCE_MAX (TRANSFORMATION + 1) + +static unsigned int min_distance(unsigned int *cost) +{ + unsigned int min = UINT_MAX; + int k; + + for (k = 0; k < DISTANCE_MAX; k++) { + if (cost[k] < min) + min = cost[k]; + } + + return min; +} + +/* A simple implementation of "The string-to-string correction problem (1974)" + * by Robert A. Wagner. + */ +static unsigned int string_distance(const char *a, const char *b) +{ + unsigned int len_a = strlen(a); + unsigned int len_b = strlen(b); + unsigned int *distance; + unsigned int i, j, ret; + + distance = xzalloc((len_a + 1) * (len_b + 1) * sizeof(unsigned int)); + +#define DISTANCE(__i, __j) distance[(__i) * len_b + (__j)] + + for (i = 0; i <= len_a; i++) + DISTANCE(i, 0) = i; + for (j = 0; j <= len_b; j++) + DISTANCE(0, j) = j; + + for (i = 1; i <= len_a; i++) { + for (j = 1; j <= len_b; j++) { + unsigned int subcost = (a[i] == b[j]) ? 0 : 1; + unsigned int cost[3]; + + cost[DELETION] = DISTANCE(i - 1, j) + 1; + cost[INSERTION] = DISTANCE(i, j - 1) + 1; + cost[TRANSFORMATION] = DISTANCE(i - 1, j - 1) + subcost; + DISTANCE(i, j) = min_distance(cost); + + if (i > 1 && j > 1 && + a[i] == b[j - 1] && + a[i - 1] == b[j]) + DISTANCE(i, j) = + min(DISTANCE(i, j), + DISTANCE(i - 2, j - 2) + subcost); + } + } + + ret = DISTANCE(len_a, len_b); + + xfree(distance); + + return ret; +} + +void string_misspell_init(struct string_misspell_state *st) +{ + st->obj = NULL; + st->min_distance = UINT_MAX; +} + +int string_misspell_update(const char *a, const char *b, + void *obj, struct string_misspell_state *st) +{ + unsigned int distance; + + distance = string_distance(a, b); + + if (distance < st->min_distance) { + st->min_distance = distance; + st->obj = obj; + return 1; + } + return 0; +} diff --git a/src/rule.c b/src/rule.c index 1fffa39a..c244d0ba 100644 --- a/src/rule.c +++ b/src/rule.c @@ -22,6 +22,7 @@ #include #include #include +#include #include #include @@ -354,18 +355,24 @@ struct set *set_lookup_fuzzy(const char *set_name, const struct nft_cache *cache, const struct table **t) { + struct string_misspell_state st; struct table *table; struct set *set; + string_misspell_init(&st); + list_for_each_entry(table, &cache->list, list) { list_for_each_entry(set, &table->sets, list) { if (!strcmp(set->handle.set.name, set_name)) { *t = table; return set; } + if (string_misspell_update(set->handle.set.name, + set_name, set, &st)) + *t = table; } } - return NULL; + return st.obj; } struct set *set_lookup_global(uint32_t family, const char *table, @@ -784,18 +791,24 @@ struct chain *chain_lookup_fuzzy(const struct handle *h, const struct nft_cache *cache, const struct table **t) { + struct string_misspell_state st; struct table *table; struct chain *chain; + string_misspell_init(&st); + list_for_each_entry(table, &cache->list, list) { list_for_each_entry(chain, &table->chains, list) { if (!strcmp(chain->handle.chain.name, h->chain.name)) { *t = table; return chain; } + if (string_misspell_update(chain->handle.chain.name, + h->chain.name, chain, &st)) + *t = table; } } - return NULL; + return st.obj; } const char *family2str(unsigned int family) @@ -1142,13 +1155,19 @@ struct table *table_lookup(const struct handle *h, struct table *table_lookup_fuzzy(const struct handle *h, const struct nft_cache *cache) { + struct string_misspell_state st; struct table *table; + string_misspell_init(&st); + list_for_each_entry(table, &cache->list, list) { if (!strcmp(table->handle.table.name, h->table.name)) return table; + + string_misspell_update(table->handle.table.name, + h->table.name, table, &st); } - return NULL; + return st.obj; } const char *table_flags_name[TABLE_FLAGS_MAX] = { -- cgit v1.2.3