1
#include "facet-tree-index.h"
2
 
3
#include <kj/io.h>
4
#include <kj/memory.h>
5
#include <kj/test.h>
6
#include <kj/time.h>
7
 
8
namespace workerd::server {
9
namespace {
10
 
11
using kj::byte;
12
using kj::uint;
13
 
14
struct ExpectedChildInfo {
15
  uint id;
16
  kj::StringPtr name;
17
};
18
void expectChildren(
19
    FacetTreeIndex& index, uint parentId, kj::ArrayPtr<const ExpectedChildInfo> expected) {
20
  index.forEachChild(parentId, [&](uint id, kj::StringPtr name) {
21
    if (expected.size() == 0) {
22
      KJ_FAIL_EXPECT("unexpected child", id, name);
23
    } else {
24
      KJ_EXPECT(id == expected.front().id);
25
      KJ_EXPECT(name == expected.front().name);
26
      expected = expected.slice(1);
27
    }
28
  });
29
  KJ_EXPECT(expected.size() == 0, "missing child", expected.front().id, expected.front().name);
30
}
31
 
32
KJ_TEST("FacetTreeIndex basic functionality") {
33
  auto file = kj::newInMemoryFile(kj::nullClock());
34
 
35
  {
36
    // Test with new empty file
37
    FacetTreeIndex index(file->clone());
38
 
39
    // Get IDs for facets
40
    uint id1 = index.getId(0, "facet1");
41
    uint id2 = index.getId(0, "facet2");
42
    uint id3 = index.getId(id1, "child1");
43
    uint id4 = index.getId(id1, "child2");
44
    uint id5 = index.getId(id2, "child1");
45
 
46
    // Check that IDs are assigned correctly
47
    KJ_EXPECT(id1 == 1);
48
    KJ_EXPECT(id2 == 2);
49
    KJ_EXPECT(id3 == 3);
50
    KJ_EXPECT(id4 == 4);
51
    KJ_EXPECT(id5 == 5);
52
 
53
    // Check that IDs are stable
54
    KJ_EXPECT(index.getId(0, "facet1") == id1);
55
    KJ_EXPECT(index.getId(0, "facet2") == id2);
56
    KJ_EXPECT(index.getId(id1, "child1") == id3);
57
    KJ_EXPECT(index.getId(id1, "child2") == id4);
58
    KJ_EXPECT(index.getId(id2, "child1") == id5);
59
 
60
    // Test forEachChild().
61
    expectChildren(index, 0, {{1, "facet1"}, {2, "facet2"}});
62
    expectChildren(index, 1, {{3, "child1"}, {4, "child2"}});
63
    expectChildren(index, 2, {{5, "child1"}});
64
    expectChildren(index, 3, {});
65
    expectChildren(index, 4, {});
66
    expectChildren(index, 5, {});
67
  }
68
 
69
  {
70
    // Test with existing file (persistence)
71
    FacetTreeIndex index(file->clone());
72
 
73
    // Check that IDs are the same as before
74
    KJ_EXPECT(index.getId(0, "facet1") == 1);
75
    KJ_EXPECT(index.getId(0, "facet2") == 2);
76
    KJ_EXPECT(index.getId(1, "child1") == 3);
77
    KJ_EXPECT(index.getId(1, "child2") == 4);
78
    KJ_EXPECT(index.getId(2, "child1") == 5);
79
 
80
    // Add some new facets
81
    uint id6 = index.getId(3, "grandchild1");
82
    uint id7 = index.getId(3, "grandchild2");
83
 
84
    KJ_EXPECT(id6 == 6);
85
    KJ_EXPECT(id7 == 7);
86
 
87
    expectChildren(index, 0, {{1, "facet1"}, {2, "facet2"}});
88
    expectChildren(index, 1, {{3, "child1"}, {4, "child2"}});
89
    expectChildren(index, 2, {{5, "child1"}});
90
    expectChildren(index, 3, {{6, "grandchild1"}, {7, "grandchild2"}});
91
    expectChildren(index, 4, {});
92
    expectChildren(index, 5, {});
93
    expectChildren(index, 6, {});
94
    expectChildren(index, 7, {});
95
  }
96
 
97
  {
98
    // Test again with existing file
99
    FacetTreeIndex index(file->clone());
100
 
101
    // Check all IDs were preserved
102
    KJ_EXPECT(index.getId(0, "facet1") == 1);
103
    KJ_EXPECT(index.getId(0, "facet2") == 2);
104
    KJ_EXPECT(index.getId(1, "child1") == 3);
105
    KJ_EXPECT(index.getId(1, "child2") == 4);
106
    KJ_EXPECT(index.getId(2, "child1") == 5);
107
    KJ_EXPECT(index.getId(3, "grandchild1") == 6);
108
    KJ_EXPECT(index.getId(3, "grandchild2") == 7);
109
 
110
    expectChildren(index, 0, {{1, "facet1"}, {2, "facet2"}});
111
    expectChildren(index, 1, {{3, "child1"}, {4, "child2"}});
112
    expectChildren(index, 2, {{5, "child1"}});
113
    expectChildren(index, 3, {{6, "grandchild1"}, {7, "grandchild2"}});
114
    expectChildren(index, 4, {});
115
    expectChildren(index, 5, {});
116
    expectChildren(index, 6, {});
117
    expectChildren(index, 7, {});
118
  }
119
}
120
 
121
KJ_TEST("FacetTreeIndex error handling") {
122
  auto file = kj::newInMemoryFile(kj::nullClock());
123
  FacetTreeIndex index(file->clone());
124
 
125
  // Add some initial facets
126
  index.getId(0, "facet1");
127
  index.getId(0, "facet2");
128
 
129
  // Test error cases
130
 
131
  // Empty name
132
  KJ_EXPECT_THROW_MESSAGE("Facet name cannot be empty", index.getId(0, ""));
133
 
134
  // Invalid parent
135
  KJ_EXPECT_THROW_MESSAGE("Invalid parent ID", index.getId(999, "child"));
136
 
137
  // Same name but different parents should get different IDs
138
  uint id1 = index.getId(1, "sameName");
139
  uint id2 = index.getId(2, "sameName");
140
  KJ_EXPECT(id1 != id2);
141
 
142
  // Test name uniqueness per parent
143
  uint id3 = index.getId(1, "sameName");
144
  KJ_EXPECT(id3 == id1);
145
}
146
 
147
KJ_TEST("FacetTreeIndex corruption handling") {
148
  auto file = kj::newInMemoryFile(kj::nullClock());
149
 
150
  // Create a file with corrupted data
151
  {
152
    // Write valid header and some valid entries
153
    constexpr uint64_t MAGIC_NUMBER = 0xc4cdce5bc5b0ef57;
154
    file->write(0,
155
        kj::ArrayPtr<const byte>(
156
            reinterpret_cast<const byte*>(&MAGIC_NUMBER), sizeof(MAGIC_NUMBER)));
157
 
158
    // Write valid entry: parent=0, name="valid"
159
    uint16_t parent = 0;
160
    uint16_t nameLen = 5;
161
    byte entry[4 + 5] = {0};
162
    memcpy(entry, &parent, 2);
163
    memcpy(entry + 2, &nameLen, 2);
164
    memcpy(entry + 4, "valid", 5);
165
    file->write(sizeof(MAGIC_NUMBER), kj::ArrayPtr<const byte>(entry, sizeof(entry)));
166
 
167
    // Write corrupted entry: parent=999 (invalid), name="corrupt"
168
    uint16_t badParent = 999;
169
    uint16_t badNameLen = 7;
170
    byte badEntry[4 + 7] = {0};
171
    memcpy(badEntry, &badParent, 2);
172
    memcpy(badEntry + 2, &badNameLen, 2);
173
    memcpy(badEntry + 4, "corrupt", 7);
174
    file->write(
175
        sizeof(MAGIC_NUMBER) + sizeof(entry), kj::ArrayPtr<const byte>(badEntry, sizeof(badEntry)));
176
 
177
    // Write valid entry after corruption that should be ignored
178
    uint16_t ignoredParent = 0;
179
    uint16_t ignoredNameLen = 7;
180
    byte ignoredEntry[4 + 7] = {0};
181
    memcpy(ignoredEntry, &ignoredParent, 2);
182
    memcpy(ignoredEntry + 2, &ignoredNameLen, 2);
183
    memcpy(ignoredEntry + 4, "ignored", 7);
184
    file->write(sizeof(MAGIC_NUMBER) + sizeof(entry) + sizeof(badEntry),
185
        kj::ArrayPtr<const byte>(ignoredEntry, sizeof(ignoredEntry)));
186
  }
187
 
188
  // Open corrupted file
189
  {
190
    FacetTreeIndex index(file->clone());
191
 
192
    // Check that only valid entries were read
193
    KJ_EXPECT(index.getId(0, "valid") == 1);
194
 
195
    // The corrupted entry and everything after it should have been ignored
196
    // So this should create a new entry
197
    uint id = index.getId(0, "corrupt");
198
    KJ_EXPECT(id == 2);
199
 
200
    // Similarly, "ignored" should be new
201
    uint id2 = index.getId(0, "ignored");
202
    KJ_EXPECT(id2 == 3);
203
  }
204
 
205
  // Open yet again, make sure that the newly-added entries were written successfully.
206
  {
207
    FacetTreeIndex index(file->clone());
208
    KJ_EXPECT(index.getId(0, "valid") == 1);
209
    KJ_EXPECT(index.getId(0, "corrupt") == 2);
210
    KJ_EXPECT(index.getId(0, "ignored") == 3);
211
  }
212
}
213
 
214
KJ_TEST("FacetTreeIndex tree structure") {
215
  auto file = kj::newInMemoryFile(kj::nullClock());
216
 
217
  FacetTreeIndex index(file->clone());
218
 
219
  // Build a tree with multiple levels
220
  uint id1 = index.getId(0, "root1");
221
  uint id2 = index.getId(0, "root2");
222
 
223
  uint id3 = index.getId(id1, "level1_1");
224
  uint id4 = index.getId(id1, "level1_2");
225
  uint id5 = index.getId(id2, "level1_3");
226
 
227
  uint id6 = index.getId(id3, "level2_1");
228
  uint id7 = index.getId(id3, "level2_2");
229
  uint id8 = index.getId(id4, "level2_3");
230
 
231
  uint id9 = index.getId(id6, "level3_1");
232
 
233
  // Verify IDs
234
  KJ_EXPECT(id1 == 1);
235
  KJ_EXPECT(id2 == 2);
236
  KJ_EXPECT(id3 == 3);
237
  KJ_EXPECT(id4 == 4);
238
  KJ_EXPECT(id5 == 5);
239
  KJ_EXPECT(id6 == 6);
240
  KJ_EXPECT(id7 == 7);
241
  KJ_EXPECT(id8 == 8);
242
  KJ_EXPECT(id9 == 9);
243
 
244
  // Verify stable lookup
245
  KJ_EXPECT(index.getId(id1, "level1_1") == id3);
246
  KJ_EXPECT(index.getId(id3, "level2_1") == id6);
247
  KJ_EXPECT(index.getId(id6, "level3_1") == id9);
248
}
249
 
250
KJ_TEST("FacetTreeIndex handles truncated files correctly") {
251
  auto file = kj::newInMemoryFile(kj::nullClock());
252
 
253
  // Step 1: Create a file with a few entries
254
  {
255
    FacetTreeIndex index(file->clone());
256
    uint id1 = index.getId(0, "entry1");
257
    uint id2 = index.getId(0, "entry2");
258
    uint id3 = index.getId(0, "entry3");
259
 
260
    KJ_EXPECT(id1 == 1);
261
    KJ_EXPECT(id2 == 2);
262
    KJ_EXPECT(id3 == 3);
263
  }
264
 
265
  // Step 2: Corrupt the last entry by overwriting its nameLength field with an invalid large value
266
  auto fileSize = file->stat().size;
267
  uint offset =
268
      fileSize - 8;  // Go to the nameLength field of the last entry (2 bytes before "entry3")
269
 
270
  // Write an impossibly large nameLength value
271
  uint16_t hugeNameLength = 65000;  // Much larger than any valid name in our test file
272
  file->write(offset,
273
      kj::ArrayPtr<const byte>(
274
          reinterpret_cast<const byte*>(&hugeNameLength), sizeof(hugeNameLength)));
275
 
276
  // Step 3: Re-read the index and add a new entry
277
  {
278
    FacetTreeIndex index(file->clone());
279
 
280
    // First two entries should still be valid
281
    KJ_EXPECT(index.getId(0, "entry1") == 1);
282
    KJ_EXPECT(index.getId(0, "entry2") == 2);
283
 
284
    // The corrupted entry (entry3) should not be found, so this new entry
285
    // should get the ID 3 (reusing the ID that was intended for entry3)
286
    uint id = index.getId(0, "replacement");
287
    KJ_EXPECT(id == 3);
288
  }
289
 
290
  // Step 4: Re-read the file again and add yet another new entry
291
  {
292
    FacetTreeIndex index(file->clone());
293
 
294
    // Immediately get a new entry, without checking existing ones first
295
    // This should get ID 4, not reuse ID 3 again
296
    uint id = index.getId(0, "another");
297
 
298
    // Now check that all previous entries are remembered
299
    KJ_EXPECT(id == 4);
300
    KJ_EXPECT(index.getId(0, "entry1") == 1);
301
    KJ_EXPECT(index.getId(0, "entry2") == 2);
302
    KJ_EXPECT(index.getId(0, "replacement") == 3);
303
  }
304
}
305
 
306
}  // namespace
307
}  // namespace workerd::server