Line data Source code
1 : //
2 : // block.c
3 : // cloudsync
4 : //
5 : // Block-level LWW CRDT support for text/blob fields.
6 : //
7 :
8 : #include <stdio.h>
9 : #include <string.h>
10 : #include <stdlib.h>
11 : #include "block.h"
12 : #include "utils.h"
13 : #include "fractional_indexing.h"
14 :
15 : // MARK: - Col name helpers -
16 :
17 204430 : bool block_is_block_colname(const char *col_name) {
18 204430 : if (!col_name) return false;
19 204430 : return strchr(col_name, BLOCK_SEPARATOR) != NULL;
20 204430 : }
21 :
22 3554 : char *block_extract_base_colname(const char *col_name) {
23 3554 : if (!col_name) return NULL;
24 3554 : const char *sep = strchr(col_name, BLOCK_SEPARATOR);
25 3554 : if (!sep) return cloudsync_string_dup(col_name);
26 3554 : return cloudsync_string_ndup(col_name, (size_t)(sep - col_name));
27 3554 : }
28 :
29 4291 : const char *block_extract_position_id(const char *col_name) {
30 4291 : if (!col_name) return NULL;
31 4291 : const char *sep = strchr(col_name, BLOCK_SEPARATOR);
32 4291 : if (!sep) return NULL;
33 4291 : return sep + 1;
34 4291 : }
35 :
36 7355 : char *block_build_colname(const char *base_col, const char *position_id) {
37 7355 : if (!base_col || !position_id) return NULL;
38 7355 : size_t blen = strlen(base_col);
39 7355 : size_t plen = strlen(position_id);
40 7355 : char *result = (char *)cloudsync_memory_alloc(blen + 1 + plen + 1);
41 7355 : if (!result) return NULL;
42 7354 : memcpy(result, base_col, blen);
43 7354 : result[blen] = BLOCK_SEPARATOR;
44 7354 : memcpy(result + blen + 1, position_id, plen);
45 7354 : result[blen + 1 + plen] = '\0';
46 7354 : return result;
47 7355 : }
48 :
49 : // MARK: - Text splitting -
50 :
51 2898 : static block_list_t *block_list_create(void) {
52 2898 : block_list_t *list = (block_list_t *)cloudsync_memory_zeroalloc(sizeof(block_list_t));
53 2898 : return list;
54 : }
55 :
56 7154 : static bool block_list_append(block_list_t *list, const char *content, size_t content_len, const char *position_id) {
57 7154 : if (list->count >= list->capacity) {
58 1855 : int new_cap = list->capacity ? list->capacity * 2 : 16;
59 1855 : block_entry_t *new_entries = (block_entry_t *)cloudsync_memory_realloc(
60 1855 : list->entries, (uint64_t)(new_cap * sizeof(block_entry_t)));
61 1855 : if (!new_entries) return false;
62 1851 : list->entries = new_entries;
63 1851 : list->capacity = new_cap;
64 1851 : }
65 7150 : block_entry_t *e = &list->entries[list->count];
66 7150 : e->content = cloudsync_string_ndup(content, content_len);
67 7150 : e->position_id = position_id ? cloudsync_string_dup(position_id) : NULL;
68 7150 : if (!e->content || (position_id && !e->position_id)) {
69 6 : cloudsync_memory_free(e->content);
70 6 : cloudsync_memory_free(e->position_id);
71 6 : return false;
72 : }
73 7144 : list->count++;
74 7144 : return true;
75 7154 : }
76 :
77 2894 : void block_list_free(block_list_t *list) {
78 2894 : if (!list) return;
79 10038 : for (int i = 0; i < list->count; i++) {
80 7144 : if (list->entries[i].content) cloudsync_memory_free(list->entries[i].content);
81 7144 : if (list->entries[i].position_id) cloudsync_memory_free(list->entries[i].position_id);
82 7144 : }
83 2894 : if (list->entries) cloudsync_memory_free(list->entries);
84 2894 : cloudsync_memory_free(list);
85 2894 : }
86 :
87 1926 : block_list_t *block_list_create_empty(void) {
88 1926 : return block_list_create();
89 : }
90 :
91 2983 : bool block_list_add(block_list_t *list, const char *content, const char *position_id) {
92 2983 : if (!list) return false;
93 2983 : return block_list_append(list, content, strlen(content), position_id);
94 2983 : }
95 :
96 972 : block_list_t *block_split(const char *text, const char *delimiter) {
97 972 : block_list_t *list = block_list_create();
98 972 : if (!list) return NULL;
99 :
100 969 : if (!text || !*text) {
101 : // Empty text produces a single empty block
102 48 : if (!block_list_append(list, "", 0, NULL)) {
103 2 : block_list_free(list);
104 2 : return NULL;
105 : }
106 46 : return list;
107 : }
108 :
109 921 : if (!delimiter) delimiter = BLOCK_DEFAULT_DELIMITER;
110 921 : size_t dlen = strlen(delimiter);
111 921 : if (dlen == 0) {
112 : // No delimiter: entire text is one block
113 3 : if (!block_list_append(list, text, strlen(text), NULL)) {
114 2 : block_list_free(list);
115 2 : return NULL;
116 : }
117 1 : return list;
118 : }
119 :
120 918 : const char *start = text;
121 : const char *found;
122 4120 : while ((found = strstr(start, delimiter)) != NULL) {
123 3204 : size_t seg_len = (size_t)(found - start);
124 3204 : if (!block_list_append(list, start, seg_len, NULL)) {
125 2 : block_list_free(list);
126 2 : return NULL;
127 : }
128 3202 : start = found + dlen;
129 : }
130 : // Last segment (after last delimiter or entire string if no delimiter found)
131 916 : if (!block_list_append(list, start, strlen(start), NULL)) {
132 1 : block_list_free(list);
133 1 : return NULL;
134 : }
135 :
136 915 : return list;
137 972 : }
138 :
139 : // MARK: - Fractional indexing (via fractional-indexing submodule) -
140 :
141 : // Wrapper for malloc: fractional_indexing expects size_t (32-bit on WASM) but cloudsync_memory_alloc takes uint64_t.
142 : // A direct cast passes strict call_indirect type checking in WASM and triggers a RuntimeError.
143 2858 : static void *fi_malloc_wrapper(size_t size) {
144 2858 : return cloudsync_memory_alloc((uint64_t)size);
145 : }
146 :
147 : // Wrapper for calloc: fractional_indexing expects (count, size) but cloudsync_memory_zeroalloc takes a single size.
148 369 : static void *fi_calloc_wrapper(size_t count, size_t size) {
149 369 : return cloudsync_memory_zeroalloc((uint64_t)(count * size));
150 : }
151 :
152 771 : void block_init_allocator(void) {
153 771 : fractional_indexing_allocator alloc = {
154 : .malloc = fi_malloc_wrapper,
155 : .calloc = fi_calloc_wrapper,
156 : .free = cloudsync_memory_free
157 : };
158 771 : fractional_indexing_set_allocator(&alloc);
159 771 : }
160 :
161 2492 : char *block_position_between(const char *before, const char *after) {
162 2492 : return generate_key_between(before, after);
163 : }
164 :
165 : // MARK: - Block diff -
166 :
167 971 : static block_diff_t *block_diff_create(void) {
168 971 : block_diff_t *diff = (block_diff_t *)cloudsync_memory_zeroalloc(sizeof(block_diff_t));
169 971 : return diff;
170 : }
171 :
172 2582 : static bool block_diff_append(block_diff_t *diff, block_diff_type type, const char *position_id, const char *content) {
173 2582 : if (diff->count >= diff->capacity) {
174 973 : int new_cap = diff->capacity ? diff->capacity * 2 : 16;
175 973 : block_diff_entry_t *new_entries = (block_diff_entry_t *)cloudsync_memory_realloc(
176 973 : diff->entries, (uint64_t)(new_cap * sizeof(block_diff_entry_t)));
177 973 : if (!new_entries) return false;
178 972 : diff->entries = new_entries;
179 972 : diff->capacity = new_cap;
180 972 : }
181 2581 : block_diff_entry_t *e = &diff->entries[diff->count];
182 2581 : e->type = type;
183 2581 : e->position_id = cloudsync_string_dup(position_id);
184 2581 : e->content = content ? cloudsync_string_dup(content) : NULL;
185 2581 : if (!e->position_id || (content && !e->content)) {
186 4 : cloudsync_memory_free(e->position_id);
187 4 : cloudsync_memory_free(e->content);
188 4 : return false;
189 : }
190 2577 : diff->count++;
191 2577 : return true;
192 2582 : }
193 :
194 970 : void block_diff_free(block_diff_t *diff) {
195 970 : if (!diff) return;
196 3547 : for (int i = 0; i < diff->count; i++) {
197 2577 : if (diff->entries[i].position_id) cloudsync_memory_free(diff->entries[i].position_id);
198 2577 : if (diff->entries[i].content) cloudsync_memory_free(diff->entries[i].content);
199 2577 : }
200 970 : if (diff->entries) cloudsync_memory_free(diff->entries);
201 970 : cloudsync_memory_free(diff);
202 970 : }
203 :
204 : // Content-based matching diff algorithm:
205 : // 1. Build a consumed-set from old blocks
206 : // 2. For each new block, find the first unconsumed old block with matching content
207 : // 3. Matched blocks keep their position_id (UNCHANGED)
208 : // 4. Unmatched new blocks get new position_ids (ADDED)
209 : // 5. Unconsumed old blocks are REMOVED
210 : // Modified blocks are detected when content changed but position stayed (handled as MODIFIED)
211 971 : block_diff_t *block_diff(block_entry_t *old_blocks, int old_count,
212 : const char **new_parts, int new_count) {
213 971 : block_diff_t *diff = block_diff_create();
214 971 : if (!diff) return NULL;
215 :
216 : // Track which old blocks have been consumed
217 970 : bool *old_consumed = NULL;
218 970 : if (old_count > 0) {
219 265 : old_consumed = (bool *)cloudsync_memory_zeroalloc((uint64_t)(old_count * sizeof(bool)));
220 265 : if (!old_consumed) {
221 1 : block_diff_free(diff);
222 1 : return NULL;
223 : }
224 264 : }
225 :
226 : // For each new block, try to find a matching unconsumed old block
227 : // Use a simple forward scan to preserve ordering
228 969 : int old_scan = 0;
229 969 : char *last_position = NULL;
230 :
231 5137 : for (int ni = 0; ni < new_count; ni++) {
232 4175 : bool found = false;
233 :
234 : // Scan forward in old blocks for a content match
235 4793 : for (int oi = old_scan; oi < old_count; oi++) {
236 2301 : if (old_consumed[oi]) continue;
237 :
238 2301 : if (strcmp(old_blocks[oi].content, new_parts[ni]) == 0) {
239 : // Exact match — mark any skipped old blocks as REMOVED
240 1712 : for (int si = old_scan; si < oi; si++) {
241 31 : if (!old_consumed[si]) {
242 31 : if (!block_diff_append(diff, BLOCK_DIFF_REMOVED, old_blocks[si].position_id, NULL)) goto fail;
243 29 : old_consumed[si] = true;
244 29 : }
245 29 : }
246 1681 : old_consumed[oi] = true;
247 1681 : old_scan = oi + 1;
248 1681 : last_position = old_blocks[oi].position_id;
249 1681 : found = true;
250 1681 : break;
251 : }
252 618 : }
253 :
254 4173 : if (!found) {
255 : // New block — needs a new position_id
256 2492 : const char *next_pos = NULL;
257 : // Find the next unconsumed old block's position for the upper bound
258 2492 : for (int oi = old_scan; oi < old_count; oi++) {
259 429 : if (!old_consumed[oi]) {
260 429 : next_pos = old_blocks[oi].position_id;
261 429 : break;
262 : }
263 0 : }
264 :
265 2492 : char *new_pos = block_position_between(last_position, next_pos);
266 2492 : if (!new_pos) goto fail;
267 : {
268 2489 : bool appended = block_diff_append(diff, BLOCK_DIFF_ADDED, new_pos, new_parts[ni]);
269 2489 : cloudsync_memory_free(new_pos);
270 2489 : if (!appended) goto fail;
271 2487 : last_position = diff->entries[diff->count - 1].position_id;
272 : }
273 2487 : }
274 4168 : }
275 :
276 : // Mark remaining unconsumed old blocks as REMOVED
277 1023 : for (int oi = old_scan; oi < old_count; oi++) {
278 62 : if (!old_consumed[oi]) {
279 62 : if (!block_diff_append(diff, BLOCK_DIFF_REMOVED, old_blocks[oi].position_id, NULL)) goto fail;
280 61 : }
281 61 : }
282 :
283 961 : if (old_consumed) cloudsync_memory_free(old_consumed);
284 961 : return diff;
285 : fail:
286 8 : cloudsync_memory_free(old_consumed);
287 8 : block_diff_free(diff);
288 8 : return NULL;
289 971 : }
290 :
291 : // MARK: - Materialization -
292 :
293 4025 : char *block_materialize_text(const char **blocks, int count, const char *delimiter) {
294 4025 : if (count == 0) return cloudsync_string_dup("");
295 4025 : if (!delimiter) delimiter = BLOCK_DEFAULT_DELIMITER;
296 :
297 4025 : size_t dlen = strlen(delimiter);
298 4025 : size_t total = 0;
299 36219 : for (int i = 0; i < count; i++) {
300 32194 : total += strlen(blocks[i]);
301 32194 : if (i < count - 1) total += dlen;
302 32194 : }
303 :
304 4025 : char *result = (char *)cloudsync_memory_alloc(total + 1);
305 4025 : if (!result) return NULL;
306 :
307 4024 : size_t offset = 0;
308 36216 : for (int i = 0; i < count; i++) {
309 32192 : size_t blen = strlen(blocks[i]);
310 32192 : memcpy(result + offset, blocks[i], blen);
311 32192 : offset += blen;
312 32192 : if (i < count - 1) {
313 28168 : memcpy(result + offset, delimiter, dlen);
314 28168 : offset += dlen;
315 28168 : }
316 32192 : }
317 4024 : result[offset] = '\0';
318 :
319 4024 : return result;
320 4025 : }
|
