検索インデックスのhash table化

5 files changed, 337 insertions, 0 deletions

diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index 9ce564e..9a02ee0 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -22,6 +22,33 @@ if(MSVC)
 endif()
 add_test(NAME tiny-convmem-mcp.domain COMMAND tiny-convmem-domain-test)
 
+add_executable(tiny-convmem-search-index-test
+  search_index_test.c
+  "${PROJECT_SOURCE_DIR}/src/domain/message.c"
+  "${PROJECT_SOURCE_DIR}/src/domain/search.c"
+)
+target_include_directories(tiny-convmem-search-index-test PRIVATE "${PROJECT_SOURCE_DIR}/src")
+target_compile_features(tiny-convmem-search-index-test PRIVATE c_std_17)
+target_compile_definitions(tiny-convmem-search-index-test PRIVATE TINY_SEARCH_TEST_HASH_BITS=8)
+target_link_libraries(tiny-convmem-search-index-test PRIVATE tiny-convmem-base)
+if(MSVC)
+  target_compile_options(tiny-convmem-search-index-test PRIVATE /utf-8 /W4)
+endif()
+add_test(NAME tiny-convmem-mcp.search-index COMMAND tiny-convmem-search-index-test)
+
+add_executable(tiny-convmem-search-benchmark
+  search_index_benchmark.c
+  "${PROJECT_SOURCE_DIR}/src/domain/message.c"
+  "${PROJECT_SOURCE_DIR}/src/domain/search.c"
+)
+target_include_directories(tiny-convmem-search-benchmark PRIVATE "${PROJECT_SOURCE_DIR}/src")
+target_compile_features(tiny-convmem-search-benchmark PRIVATE c_std_17)
+target_link_libraries(tiny-convmem-search-benchmark PRIVATE tiny-convmem-base)
+if(MSVC)
+  target_compile_options(tiny-convmem-search-benchmark PRIVATE /utf-8 /W4)
+  target_link_libraries(tiny-convmem-search-benchmark PRIVATE psapi)
+endif()
+
 add_executable(tiny-convmem-mcpc-test mcpc_test.c)
 target_include_directories(tiny-convmem-mcpc-test PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}")
 target_compile_features(tiny-convmem-mcpc-test PRIVATE c_std_17)
@@ -111,6 +138,7 @@ if(TINY_CONVMEM_ENABLE_ASAN AND MSVC)
     TEST
       tiny-convmem-mcp.smoke
       tiny-convmem-mcp.domain
+      tiny-convmem-mcp.search-index
       tiny-convmem-mcp.mcpc
       tiny-convmem-mcp.protocol
       tiny-convmem-mcp.boundaries
diff --git a/tests/function-coverage.md b/tests/function-coverage.md
index 66c2e4a..8787918 100644
--- a/tests/function-coverage.md
+++ b/tests/function-coverage.md
@@ -10,6 +10,7 @@ byte/encoding logic is exposed through internal headers and tested directly.
 | `storage/codec.c` | `tiny_codec_put_u32`, `tiny_codec_put_u64`, `tiny_codec_get_u32`, `tiny_codec_get_u64`, `tiny_codec_crc32` | `boundaries`: offsets 0–15, integer limits, empty/NULL and known CRC |
 | `sys/system.c` | test-hook helpers; UTF adapters; `native_file`; argument, path, directory, file, clock and random APIs | `boundaries`, `storage`, `smoke`: NULL/invalid handle, Unicode paths, short I/O, operation failure, cleanup |
 | `domain/message.c` | `duplicate_string`, `copy_failed`, all `tiny_message_*`, role/tier parse/name, `tiny_utf8_valid`, `tiny_message_id_valid` | `domain`: enum failure, UTF-8 invalidity, ULID alphabet/length, deep copy and ownership |
+| `domain/search.c` | Unicode decode/score、open-addressing lookup/rehash、transactional delta merge、candidate union | `domain`, `search-index`: ASCII/日本語、8-bit hash衝突、複数rehash、allocation failure全位置、leak balance |
 | `domain/search.c` | `decode_codepoints`, `gram_hash`, `find_bucket`, `add_gram`, `index_text`, all `tiny_search_*` | `domain`: ASCII case folding, Unicode grams/tags, candidates, scoring and ownership |
 | `storage/store.c` | error/I/O helpers, ULID, entry growth/search, record codec, replay/snapshot/recovery, all `tiny_store_*` | `storage`, `lifecycle`: lock, append/reopen, corruption, rebuild rollback, Unicode path |
 | `mcp/json.c` | `reserve`, all `tiny_json_*` | `boundaries`: empty append, growth, control escaping, signed/unsigned integer limits, OOM |
diff --git a/tests/mcp_protocol_test.py b/tests/mcp_protocol_test.py
index 118043f..f739168 100644
--- a/tests/mcp_protocol_test.py
+++ b/tests/mcp_protocol_test.py
@@ -81,6 +81,15 @@ def tool_payload(response: Mapping[str, Any], expect_error: bool = False) -> dic
     return json.loads(result["content"][0]["text"])
 
 
+def assert_stable_recency_order(messages: list[dict[str, Any]]) -> None:
+    for left, right in zip(messages, messages[1:]):
+        left_time = int(left["timestamp"])
+        right_time = int(right["timestamp"])
+        assert left_time > right_time or (
+            left_time == right_time and left["message_id"] <= right["message_id"]
+        ), (left, right)
+
+
 def main() -> None:
     parser = argparse.ArgumentParser()
     parser.add_argument("--server", type=Path, required=True)
@@ -156,6 +165,22 @@ def main() -> None:
         next_id += 1
         assert len(history) == 20
 
+        ranked = tool_payload(
+            tool_call(
+                server,
+                next_id,
+                "search_messages",
+                {"query": "needle target", "limit": 100},
+            )
+        )["results"]
+        next_id += 1
+        assert len(ranked) == 30
+        assert all(item["session_id"] == "target" for item in ranked[:20])
+        assert all(item["session_id"] == "other" for item in ranked[20:])
+        assert_stable_recency_order(ranked[:20])
+        assert_stable_recency_order(ranked[20:])
+        ranked_ids_before = [item["message_id"] for item in ranked]
+
         for index in range(args.iterations):
             arguments: dict[str, Any] = {"query": "needle"}
             if index % 2:
@@ -192,6 +217,18 @@ def main() -> None:
         next_id += 1
         tool_payload(tool_call(server, next_id, "rebuild_index", {}))
         next_id += 1
+        ranked_after_rebuild = tool_payload(
+            tool_call(
+                server,
+                next_id,
+                "search_messages",
+                {"query": "needle target", "limit": 100},
+            )
+        )["results"]
+        next_id += 1
+        assert [item["message_id"] for item in ranked_after_rebuild] == [
+            message_id for message_id in ranked_ids_before if message_id != message_ids[0]
+        ]
         assert tool_payload(tool_call(server, next_id, "get_system_health", {}))["status"] == "OK"
         next_id += 1
 
diff --git a/tests/search_index_benchmark.c b/tests/search_index_benchmark.c
new file mode 100644
index 0000000..f17335a
--- /dev/null
+++ b/tests/search_index_benchmark.c
@@ -0,0 +1,110 @@
+#include "domain/message.h"
+#include "domain/search.h"
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#ifdef _WIN32
+#include <windows.h>
+#include <psapi.h>
+#endif
+
+#include "base/allocator.h"
+
+static double
+now_milliseconds(void)
+{
+  struct timespec value;
+  timespec_get(&value, TIME_UTC);
+  return (double)value.tv_sec * 1000.0 + (double)value.tv_nsec / 1000000.0;
+}
+
+static uint64_t
+peak_working_set(void)
+{
+#ifdef _WIN32
+  PROCESS_MEMORY_COUNTERS counters;
+  if (GetProcessMemoryInfo(GetCurrentProcess(), &counters, sizeof(counters)))
+    {
+      return (uint64_t)counters.PeakWorkingSetSize;
+    }
+#endif
+  return 0;
+}
+
+static char *
+make_content(size_t size)
+{
+  static const char alphabet[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ";
+  uint32_t state = UINT32_C(0x9e3779b9);
+  char *content;
+  size_t position;
+  if (size == SIZE_MAX)
+    {
+      return NULL;
+    }
+  content = malloc(size + 1);
+  if (!content)
+    {
+      return NULL;
+    }
+  for (position = 0; position < size; ++position)
+    {
+      state = state * UINT32_C(1664525) + UINT32_C(1013904223);
+      content[position] = alphabet[state % (sizeof(alphabet) - 1)];
+    }
+  content[size] = '\0';
+  return content;
+}
+
+int
+main(int argc, char **argv)
+{
+  tiny_message_t message;
+  size_t size, iterations, iteration;
+  char *content;
+  double started, elapsed;
+  if (argc != 3)
+    {
+      fprintf(stderr, "usage: %s SIZE_BYTES ITERATIONS\n", argv[0]);
+      return 2;
+    }
+  size = (size_t)strtoull(argv[1], NULL, 10);
+  iterations = (size_t)strtoull(argv[2], NULL, 10);
+  if (size == 0 || size > TINY_CONTENT_MAX || iterations == 0)
+    {
+      fprintf(stderr, "size or iterations is out of range\n");
+      return 2;
+    }
+  content = make_content(size);
+  if (!content)
+    {
+      return 1;
+    }
+  tiny_message_init(&message);
+  message.content = content;
+  started = now_milliseconds();
+  for (iteration = 0; iteration < iterations; ++iteration)
+    {
+      tiny_search_index_t *index = tiny_search_index_create();
+      if (!index || !tiny_search_index_add(index, &message, 0))
+        {
+          tiny_search_index_free(index);
+          free(content);
+          return 1;
+        }
+      tiny_search_index_free(index);
+    }
+  elapsed = now_milliseconds() - started;
+  printf("{\"size_bytes\":%zu,\"iterations\":%zu,\"total_ms\":%.3f,"
+         "\"mean_ms\":%.3f,\"peak_working_set_bytes\":%llu}\n",
+         size,
+         iterations,
+         elapsed,
+         elapsed / (double)iterations,
+         (unsigned long long)peak_working_set());
+  free(content);
+  return tiny_allocator_outstanding() == 0 ? 0 : 1;
+}
diff --git a/tests/search_index_test.c b/tests/search_index_test.c
new file mode 100644
index 0000000..5a477ad
--- /dev/null
+++ b/tests/search_index_test.c
@@ -0,0 +1,161 @@
+#include "domain/message.h"
+#include "domain/search.h"
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "base/allocator.h"
+
+static int failures;
+
+#define CHECK(value)                                                                               \
+  do                                                                                               \
+    {                                                                                              \
+      if (!(value))                                                                                \
+        {                                                                                          \
+          fprintf(stderr, "CHECK failed at line %d: %s\n", __LINE__, #value);                      \
+          failures++;                                                                              \
+        }                                                                                          \
+    }                                                                                              \
+  while (0)
+
+static tiny_message_t
+make_message(const char *content, char **tags, size_t tag_count)
+{
+  tiny_message_t message;
+  tiny_message_init(&message);
+  message.content = (char *)content;
+  message.metadata.tags = tags;
+  message.metadata.tag_count = tag_count;
+  return message;
+}
+
+static bool
+candidate_contains(tiny_search_index_t *index, const char *query, size_t expected)
+{
+  size_t *candidates = NULL;
+  size_t count = 0, position;
+  bool found = false;
+  if (!tiny_search_index_candidates(index, query, &candidates, &count))
+    {
+      return false;
+    }
+  for (position = 0; position < count; ++position)
+    {
+      if (candidates[position] == expected)
+        {
+          found = true;
+          break;
+        }
+    }
+  free(candidates);
+  return found;
+}
+
+static void
+test_collision_rehash_and_unicode(void)
+{
+  tiny_search_index_t *index = tiny_search_index_create();
+  char contents[300][4];
+  size_t position;
+  char *tags[] = { "設計メモ" };
+  tiny_message_t tagged = make_message("tagged content", tags, 1);
+  tiny_message_t duplicate = make_message("aaaaaa", NULL, 0);
+  size_t *candidates = NULL;
+  size_t count = 0;
+
+  CHECK(index != NULL);
+  for (position = 0; index && position < 300; ++position)
+    {
+      tiny_message_t message;
+      contents[position][0] = (char)('a' + (position / (26 * 26)) % 26);
+      contents[position][1] = (char)('a' + (position / 26) % 26);
+      contents[position][2] = (char)('a' + position % 26);
+      contents[position][3] = '\0';
+      message = make_message(contents[position], NULL, 0);
+      CHECK(tiny_search_index_add(index, &message, position));
+    }
+  for (position = 0; index && position < 300; ++position)
+    {
+      CHECK(candidate_contains(index, contents[position], position));
+    }
+
+  CHECK(tiny_search_index_add(index, &tagged, 300));
+  CHECK(candidate_contains(index, "設計", 300));
+  CHECK(candidate_contains(index, "TAGGED", 300));
+  CHECK(tiny_search_index_add(index, &duplicate, 301));
+  CHECK(tiny_search_index_candidates(index, "aaa", &candidates, &count));
+  {
+    size_t duplicate_hits = 0;
+    for (position = 0; position < count; ++position)
+      {
+        if (candidates[position] == 301)
+          {
+            duplicate_hits++;
+          }
+      }
+    CHECK(duplicate_hits == 1);
+  }
+  free(candidates);
+  candidates = NULL;
+  CHECK(tiny_search_index_candidates(index, "a", &candidates, &count));
+  CHECK(count == 302);
+  free(candidates);
+  tiny_search_index_free(index);
+}
+
+static void
+test_transactional_allocation_failure(void)
+{
+  const tiny_message_t baseline = make_message("baseline-only", NULL, 0);
+  char *tags[] = { "transaction-tag", "日本語追加" };
+  const tiny_message_t addition
+      = make_message("zyxwvutsrqponmlkjihgfedcba-transactional-new-token", tags, 2);
+  size_t failure_index;
+  bool reached_success = false;
+
+  for (failure_index = 0; failure_index < 512; ++failure_index)
+    {
+      tiny_search_index_t *index;
+      size_t baseline_allocations = tiny_allocator_outstanding();
+      tiny_allocator_reset();
+      index = tiny_search_index_create();
+      CHECK(index != NULL);
+      CHECK(tiny_search_index_add(index, &baseline, 0));
+
+      tiny_allocator_fail_after(failure_index);
+      if (tiny_search_index_add(index, &addition, 1))
+        {
+          tiny_allocator_reset();
+          CHECK(candidate_contains(index, "transactional-new-token", 1));
+          reached_success = true;
+          tiny_search_index_free(index);
+          CHECK(tiny_allocator_outstanding() == baseline_allocations);
+          break;
+        }
+
+      tiny_allocator_reset();
+      CHECK(candidate_contains(index, "baseline-only", 0));
+      CHECK(!candidate_contains(index, "transactional-new-token", 1));
+      CHECK(tiny_search_index_add(index, &addition, 1));
+      CHECK(candidate_contains(index, "transactional-new-token", 1));
+      tiny_search_index_free(index);
+      CHECK(tiny_allocator_outstanding() == baseline_allocations);
+    }
+  CHECK(reached_success);
+}
+
+int
+main(void)
+{
+  tiny_allocator_reset();
+  CHECK(tiny_allocator_outstanding() == 0);
+  test_collision_rehash_and_unicode();
+  CHECK(tiny_allocator_outstanding() == 0);
+  test_transactional_allocation_failure();
+  tiny_allocator_reset();
+  CHECK(tiny_allocator_outstanding() == 0);
+  return failures == 0 ? 0 : 1;
+}