277 lines
13 KiB
C
277 lines
13 KiB
C
#include "c_NlpTrie.h"
|
|
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
|
|
/* --- 自定义测试断言宏 --- */
|
|
#define RUN_TEST(test_case, name) \
|
|
do { \
|
|
printf("[RUN] %s... ", name); \
|
|
if (test_case) { \
|
|
printf("\033[32mPASSED\033[0m\n"); \
|
|
} else { \
|
|
printf("\033[31mFAILED\033[0m (%s:%d)\n", __FILE__, __LINE__); \
|
|
return C_ERR_FAIL; \
|
|
} \
|
|
} while(0)
|
|
|
|
/**
|
|
* @brief c_NlpTrie 模块标准单元测试函数
|
|
* @return c_err_t 返回 C_ERR_OK 表示全部通过，返回 C_ERROR 表示有测试项失败
|
|
*/
|
|
c_err_t c_NlpTrie_UnitTest(void) {
|
|
c_NlpTrie_t trie;
|
|
c_err_t err;
|
|
|
|
printf("========================================\n");
|
|
printf(" STARTING c_NlpTrie UNIT TESTS \n");
|
|
printf("========================================\n");
|
|
|
|
/* 1. 防御性边界测试 (Null Pointer Protection) */
|
|
RUN_TEST(c_NlpTrie_Init(NULL) == C_ERR_PARAM, "Init with NULL pointer");
|
|
RUN_TEST(c_NlpTrie_Insert(NULL, "test") == C_ERR_PARAM, "Insert with NULL self");
|
|
RUN_TEST(c_NlpTrie_Insert(&trie, NULL) == C_ERR_PARAM, "Insert with NULL word (before init)");
|
|
RUN_TEST(c_NlpTrie_Contains(NULL, "test") == C_FALSE, "Search with NULL self");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(NULL, "test") == C_FALSE, "HasStartWith with NULL self");
|
|
|
|
/* 2. 初始化测试 (Initialization) */
|
|
err = c_NlpTrie_Init(&trie);
|
|
RUN_TEST(err == C_ERR_OK && trie.root != NULL, "Normal initialization");
|
|
|
|
/* 3. 基础插入与精确查找测试 (Basic Insert & Search) */
|
|
err = c_NlpTrie_Insert(&trie, "nlp");
|
|
RUN_TEST(err == C_ERR_OK, "Insert normal word 'nlp'");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "nlp") == C_TRUE, "Search existing word 'nlp'");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "nl") == C_FALSE, "Search non-existing shorter word 'nl'");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "nlps") == C_FALSE, "Search non-existing longer word 'nlps'");
|
|
|
|
/* 4. 前缀包含关系与空字符串测试 (Prefix & Edge cases) */
|
|
err = c_NlpTrie_Insert(&trie, "apple");
|
|
err |= c_NlpTrie_Insert(&trie, "app");
|
|
RUN_TEST(err == C_ERR_OK, "Insert words with shared prefix ('apple', 'app')");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "app") == C_TRUE, "Search shared prefix word 'app'");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "apple") == C_TRUE, "Search full word 'apple'");
|
|
|
|
// 空字符串通常作为根节点本身的结尾标记（如果允许插入）
|
|
err = c_NlpTrie_Insert(&trie, "");
|
|
RUN_TEST(err == C_ERR_OK, "Insert empty string ''");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "") == C_TRUE, "Search empty string ''");
|
|
|
|
/* 5. 256 全字符集测试 (UTF-8 Chinese & ASCII Symbols) */
|
|
// 包含：全角符号、大写英文、空格、数字、扩展 ASCII
|
|
err = c_NlpTrie_Insert(&trie, "自然语言处理_v2.0");
|
|
RUN_TEST(err == C_ERR_OK, "Insert complex UTF-8 word with symbols and numbers");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "自然语言处理_v2.0") == C_TRUE, "Search complex UTF-8 word");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "自然语言") == C_FALSE, "Search non-existing sub-word '自然语言'");
|
|
|
|
/* 6. 前缀查找功能测试 (HasStartWith) */
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "自然") == C_TRUE, "HasStartWith existing Chinese prefix");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "自然语言处理_v2.0") == C_TRUE, "HasStartWith full match as prefix");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "自燃") == C_FALSE, "HasStartWith non-existing Chinese prefix");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "nl") == C_TRUE, "HasStartWith existing English prefix");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "xyz") == C_FALSE, "HasStartWith non-existing English prefix");
|
|
|
|
/* 7. 销毁与悬空安全测试 (Destroy & Safety) */
|
|
c_NlpTrie_Destroy(&trie);
|
|
RUN_TEST(trie.root == NULL, "Trie root set to NULL after destroy");
|
|
|
|
// 销毁后的二次防御调用不应引发崩溃
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "nlp") == C_FALSE, "Search on destroyed trie");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "nlp") == C_FALSE, "HasStartWith on destroyed trie");
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
c_NlpTrie_Init(&trie);
|
|
/* 8. 最长前缀匹配测试 (LongestPrefixOf) */
|
|
char res_buf[128];
|
|
|
|
// 准备数据
|
|
c_NlpTrie_Insert(&trie, "自然");
|
|
c_NlpTrie_Insert(&trie, "自然语言");
|
|
c_NlpTrie_Insert(&trie, "自然语言处理");
|
|
c_NlpTrie_Insert(&trie, "nlp");
|
|
|
|
// 测试点 1：有多重匹配时，应当贪婪匹配最长的一个
|
|
c_NlpTrie_LongestPrefixOf(&trie, "自然语言处理核心技术", res_buf, sizeof(res_buf));
|
|
RUN_TEST(strcmp(res_buf, "自然语言处理") == 0, "LongestPrefixOf greedy match '自然语言处理'");
|
|
|
|
// 测试点 2：部分输入匹配，落到中途的有效单词上
|
|
c_NlpTrie_LongestPrefixOf(&trie, "自然语言学习", res_buf, sizeof(res_buf));
|
|
RUN_TEST(strcmp(res_buf, "自然语言") == 0, "LongestPrefixOf sub-match '自然语言'");
|
|
|
|
// 测试点 3：完全无法匹配的情况
|
|
c_NlpTrie_LongestPrefixOf(&trie, "人工智能", res_buf, sizeof(res_buf));
|
|
RUN_TEST(strcmp(res_buf, "") == 0, "LongestPrefixOf no match returns empty string");
|
|
|
|
// 测试点 4：英文前缀匹配
|
|
c_NlpTrie_LongestPrefixOf(&trie, "nlpsolver", res_buf, sizeof(res_buf));
|
|
RUN_TEST(strcmp(res_buf, "nlp") == 0, "LongestPrefixOf English word 'nlp'");
|
|
c_NlpTrie_Destroy(&trie);
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
|
|
/* 9. Autocomplete Prefix Matching Tests (KeysWithPrefix) */
|
|
c_NlpTrie_Init(&trie);
|
|
c_NlpStringList_t matches;
|
|
|
|
c_NlpTrie_Insert(&trie, "app");
|
|
c_NlpTrie_Insert(&trie, "apple");
|
|
c_NlpTrie_Insert(&trie, "apricot");
|
|
c_NlpTrie_Insert(&trie, "banana");
|
|
c_NlpTrie_Insert(&trie, "自然语言");
|
|
c_NlpTrie_Insert(&trie, "自然语言处理");
|
|
|
|
// Test Point 1: Match English Prefix 'ap' (Expect: app, apple, apricot)
|
|
err = c_NlpTrie_KeysWithPrefix(&trie, "ap", &matches);
|
|
RUN_TEST(err == C_ERR_OK && matches.count == 3, "KeysWithPrefix found 3 matches for 'ap'");
|
|
RUN_TEST(strcmp(matches.items[0], "app") == 0, "Matches item 0 is 'app'");
|
|
RUN_TEST(strcmp(matches.items[1], "apple") == 0, "Matches item 1 is 'apple'");
|
|
RUN_TEST(strcmp(matches.items[2], "apricot") == 0, "Matches item 2 is 'apricot'");
|
|
c_NlpStringList_Destroy(&matches);
|
|
|
|
// Test Point 2: Match UTF-8 Chinese Prefix (Expect: 自然语言, 自然语言处理)
|
|
err = c_NlpTrie_KeysWithPrefix(&trie, "自然", &matches);
|
|
RUN_TEST(err == C_ERR_OK && matches.count == 2, "KeysWithPrefix found 2 matches for '自然'");
|
|
c_NlpStringList_Destroy(&matches);
|
|
|
|
// Test Point 3: Search non-existent prefix (Expect: 0 items found, no memory leaks)
|
|
err = c_NlpTrie_KeysWithPrefix(&trie, "unknown", &matches);
|
|
RUN_TEST(err == C_ERR_OK && matches.count == 0, "KeysWithPrefix returned 0 items on empty mismatch");
|
|
c_NlpStringList_Destroy(&matches);
|
|
c_NlpTrie_Destroy(&trie);
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
c_NlpTrie_Init(&trie);
|
|
|
|
/* 13. Wildcard Query Traversal Validation (KeysThatMatch) */
|
|
c_NlpStringList_t query_results;
|
|
|
|
c_NlpTrie_Insert(&trie, "cat");
|
|
c_NlpTrie_Insert(&trie, "cot");
|
|
c_NlpTrie_Insert(&trie, "coat");
|
|
c_NlpTrie_Insert(&trie, "dog");
|
|
c_NlpTrie_Insert(&trie, "自然");
|
|
c_NlpTrie_Insert(&trie, "自燃");
|
|
|
|
// Test Case 1: Simple single wildcard slot match (Expect: "cat", "cot")
|
|
err = c_NlpTrie_KeysThatMatch(&trie, "c.t", &query_results);
|
|
RUN_TEST(err == C_ERR_OK && query_results.count == 2, "KeysThatMatch finds exactly 2 terms matching pattern 'c.t'");
|
|
RUN_TEST(strcmp(query_results.items[0], "cat") == 0, "First matching match found: 'cat'");
|
|
RUN_TEST(strcmp(query_results.items[1], "cot") == 0, "Second matching match found: 'cot'");
|
|
c_NlpStringList_Destroy(&query_results);
|
|
|
|
// Test Case 2: Full wildcard string constraint match length (Expect: "dog")
|
|
err = c_NlpTrie_KeysThatMatch(&trie, "...", &query_results);
|
|
RUN_TEST(err == C_ERR_OK && query_results.count == 3, "Pattern '...' pulls exact length matches ('cat', 'cot', 'dog')");
|
|
c_NlpStringList_Destroy(&query_results);
|
|
|
|
// Test Case 3: Complex multi-byte matching (Remember: in UTF-8, 1 Chinese Character = 3 Bytes)
|
|
// To match a single trailing Chinese character change on "自*", we need 3 dots "自..."
|
|
err = c_NlpTrie_KeysThatMatch(&trie, "自...", &query_results);
|
|
RUN_TEST(err == C_ERR_OK && query_results.count == 2, "Multi-byte pattern verification matches both '自然' and '自燃'");
|
|
c_NlpStringList_Destroy(&query_results);
|
|
|
|
// Test Case 4: Zero match behavior
|
|
err = c_NlpTrie_KeysThatMatch(&trie, "c..t", &query_results); // Matches "coat"
|
|
RUN_TEST(err == C_ERR_OK && query_results.count == 1, "Pattern 'c..t' correctly identifies structural length match 'coat'");
|
|
c_NlpStringList_Destroy(&query_results);
|
|
c_NlpTrie_Destroy(&trie);
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
/* 14. Dictionary Node Deletion & Path Pruning Verification (c_NlpTrie_Delete) */
|
|
c_NlpTrie_Init(&trie);
|
|
|
|
c_NlpTrie_Insert(&trie, "app");
|
|
c_NlpTrie_Insert(&trie, "apple");
|
|
c_NlpTrie_Insert(&trie, "banana");
|
|
|
|
// Test Point 1: Parameter validation checking
|
|
RUN_TEST(c_NlpTrie_Delete(NULL, "app") == C_ERR_PARAM, "Delete handles NULL self context pointer");
|
|
RUN_TEST(c_NlpTrie_Delete(&trie, NULL) == C_ERR_PARAM, "Delete handles NULL string inputs");
|
|
|
|
// Test Point 2: Deleting a word that is a prefix of another word ("app")
|
|
// Expected: "app" flag goes off, but "apple" nodes must stay intact
|
|
err = c_NlpTrie_Delete(&trie, "app");
|
|
RUN_TEST(err == C_ERR_OK, "Delete intermediate prefix word 'app' successfully");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "app") == C_FALSE, "Word 'app' is no longer searchable");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "apple") == C_TRUE, "Longer word 'apple' remains fully searchable");
|
|
|
|
// Test Point 3: Deleting a word that leaves isolated nodes behind ("apple")
|
|
// Expected: The path nodes matching 'l' and 'e' must be pruned to avoid memory leaks
|
|
err = c_NlpTrie_Delete(&trie, "apple");
|
|
RUN_TEST(err == C_ERR_OK, "Delete trailing leaf word 'apple' successfully");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "apple") == C_FALSE, "Word 'apple' is no longer searchable");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "ap") == C_FALSE, "Prefix path 'ap' is completely pruned");
|
|
|
|
// Test Point 4: Non-existent word cleanup verification
|
|
err = c_NlpTrie_Delete(&trie, "orange");
|
|
RUN_TEST(err == C_ERR_OK, "Deleting non-existent word exits cleanly without modification");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "banana") == C_TRUE, "Unrelated word 'banana' is unaffected");
|
|
|
|
c_NlpTrie_Destroy(&trie);
|
|
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
/* 15. Trie Flush Re-initialization Verification (c_NlpTrie_Clear) */
|
|
c_NlpTrie_Init(&trie);
|
|
|
|
c_NlpTrie_Insert(&trie, "nlp");
|
|
c_NlpTrie_Insert(&trie, "自然语言");
|
|
|
|
// Test Point 1: Parameter validation checking
|
|
RUN_TEST(c_NlpTrie_Clear(NULL) == C_ERR_PARAM, "Clear handles NULL self context pointer safely");
|
|
|
|
// Test Point 2: Execution clearance tracking
|
|
err = c_NlpTrie_Clear(&trie);
|
|
RUN_TEST(err == C_ERR_OK, "Clear flushes all sub-branch contents successfully");
|
|
RUN_TEST(trie.root != NULL, "Trie structural base root node is preserved");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "nlp") == C_FALSE, "Previously stored word 'nlp' is no longer found");
|
|
RUN_TEST(c_NlpTrie_HasStartWith(&trie, "自然") == C_FALSE, "Prefix indicators successfully cleared");
|
|
|
|
// Test Point 3: Verification of re-insertion stability post-clearance
|
|
err = c_NlpTrie_Insert(&trie, "reborn");
|
|
RUN_TEST(err == C_ERR_OK, "Trie accepts new entry additions seamlessly after being cleared");
|
|
RUN_TEST(c_NlpTrie_Contains(&trie, "reborn") == C_TRUE, "Newly added post-clearance key is fully searchable");
|
|
|
|
// Test Point 4: Idempotent clearing check (sequential empty clears)
|
|
err = c_NlpTrie_Clear(&trie);
|
|
err |= c_NlpTrie_Clear(&trie);
|
|
RUN_TEST(err == C_ERR_OK, "Continuous back-to-back clear calls execute safely with no side-effects");
|
|
|
|
c_NlpTrie_Destroy(&trie);
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
|
|
// 允许重复销毁（幂等性保护）
|
|
c_NlpTrie_Destroy(&trie);
|
|
|
|
printf("========================================\n");
|
|
printf("\033[32mALL c_NlpTrie TESTS PASSED SUCCESSFULLY!\033[0m\n");
|
|
printf("========================================\n");
|
|
|
|
return C_ERR_OK;
|
|
}
|
|
|
|
/* --- 测试执行入口 --- */
|
|
int main(void) {
|
|
// 执行单元测试
|
|
c_err_t result = c_NlpTrie_UnitTest();
|
|
if (result != C_ERR_OK) {
|
|
return -1;
|
|
}
|
|
return 0;
|
|
}
|