1 #include "common.h"
2
3 #include "seafile-session.h"
4 #include "vc-common.h"
5
6 #include "log.h"
7 #include "seafile-error.h"
8
9 static GList *
10 merge_bases_many (SeafCommit *one, int n, SeafCommit **twos);
11
12 static gint
compare_commit_by_time(gconstpointer a,gconstpointer b,gpointer unused)13 compare_commit_by_time (gconstpointer a, gconstpointer b, gpointer unused)
14 {
15 const SeafCommit *commit_a = a;
16 const SeafCommit *commit_b = b;
17
18 /* Latest commit comes first in the list. */
19 return (commit_b->ctime - commit_a->ctime);
20 }
21
22 static gint
compare_commit(gconstpointer a,gconstpointer b)23 compare_commit (gconstpointer a, gconstpointer b)
24 {
25 const SeafCommit *commit_a = a;
26 const SeafCommit *commit_b = b;
27
28 return strcmp (commit_a->commit_id, commit_b->commit_id);
29 }
30
31 static gboolean
add_to_commit_hash(SeafCommit * commit,void * vhash,gboolean * stop)32 add_to_commit_hash (SeafCommit *commit, void *vhash, gboolean *stop)
33 {
34 GHashTable *hash = vhash;
35
36 char *key = g_strdup (commit->commit_id);
37 g_hash_table_replace (hash, key, key);
38
39 return TRUE;
40 }
41
42 static GHashTable *
commit_tree_to_hash(SeafCommit * head)43 commit_tree_to_hash (SeafCommit *head)
44 {
45 GHashTable *hash;
46 gboolean res;
47
48 hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
49
50 res = seaf_commit_manager_traverse_commit_tree (seaf->commit_mgr,
51 head->repo_id,
52 head->version,
53 head->commit_id,
54 add_to_commit_hash,
55 hash, FALSE);
56 if (!res)
57 goto fail;
58
59 return hash;
60
61 fail:
62 g_hash_table_destroy (hash);
63 return NULL;
64 }
65
66 static GList *
get_independent_commits(GList * commits)67 get_independent_commits (GList *commits)
68 {
69 SeafCommit **rslt;
70 GList *list, *result;
71 int cnt, i, j;
72 SeafCommit *c;
73
74 g_debug ("Get independent commits.\n");
75
76 cnt = g_list_length (commits);
77
78 rslt = calloc(cnt, sizeof(*rslt));
79 for (list = commits, i = 0; list; list = list->next)
80 rslt[i++] = list->data;
81 g_list_free (commits);
82
83 for (i = 0; i < cnt - 1; i++) {
84 for (j = i+1; j < cnt; j++) {
85 if (!rslt[i] || !rslt[j])
86 continue;
87 result = merge_bases_many(rslt[i], 1, &rslt[j]);
88 for (list = result; list; list = list->next) {
89 c = list->data;
90 /* If two commits have fast-forward relationship,
91 * drop the older one.
92 */
93 if (strcmp (rslt[i]->commit_id, c->commit_id) == 0) {
94 seaf_commit_unref (rslt[i]);
95 rslt[i] = NULL;
96 }
97 if (strcmp (rslt[j]->commit_id, c->commit_id) == 0) {
98 seaf_commit_unref (rslt[j]);
99 rslt[j] = NULL;
100 }
101 seaf_commit_unref (c);
102 }
103 }
104 }
105
106 /* Surviving ones in rslt[] are the independent results */
107 result = NULL;
108 for (i = 0; i < cnt; i++) {
109 if (rslt[i])
110 result = g_list_insert_sorted_with_data (result, rslt[i],
111 compare_commit_by_time,
112 NULL);
113 }
114 free(rslt);
115 return result;
116 }
117
118 typedef struct {
119 GList *result;
120 GHashTable *commit_hash;
121 } MergeTraverseData;
122
123 static gboolean
get_merge_bases(SeafCommit * commit,void * vdata,gboolean * stop)124 get_merge_bases (SeafCommit *commit, void *vdata, gboolean *stop)
125 {
126 MergeTraverseData *data = vdata;
127
128 /* Found a common ancestor.
129 * Dont traverse its parenets.
130 */
131 if (g_hash_table_lookup (data->commit_hash, commit->commit_id)) {
132 if (!g_list_find_custom (data->result, commit, compare_commit)) {
133 data->result = g_list_insert_sorted_with_data (data->result, commit,
134 compare_commit_by_time,
135 NULL);
136 seaf_commit_ref (commit);
137 }
138 *stop = TRUE;
139 }
140
141 return TRUE;
142 }
143
144 /*
145 * Merge "one" with commits in "twos".
146 * The ancestors returned may not be ancestors for all the input commits.
147 * They are common ancestors for one and some commits in twos array.
148 */
149 static GList *
merge_bases_many(SeafCommit * one,int n,SeafCommit ** twos)150 merge_bases_many (SeafCommit *one, int n, SeafCommit **twos)
151 {
152 GHashTable *commit_hash;
153 GList *result = NULL;
154 SeafCommit *commit;
155 int i;
156 MergeTraverseData data;
157 gboolean res;
158
159 for (i = 0; i < n; i++) {
160 if (one == twos[i])
161 return g_list_append (result, one);
162 }
163
164 /* First construct a hash table of all commit ids rooted at one. */
165 commit_hash = commit_tree_to_hash (one);
166 if (!commit_hash) {
167 g_warning ("Failed to load commit hash.\n");
168 return NULL;
169 }
170
171 data.commit_hash = commit_hash;
172 data.result = NULL;
173
174 for (i = 0; i < n; i++) {
175 res = seaf_commit_manager_traverse_commit_tree (seaf->commit_mgr,
176 twos[i]->repo_id,
177 twos[i]->version,
178 twos[i]->commit_id,
179 get_merge_bases,
180 &data, FALSE);
181 if (!res)
182 goto fail;
183 }
184
185 g_hash_table_destroy (commit_hash);
186 result = data.result;
187
188 if (!result || !result->next)
189 return result;
190
191 /* There are more than one. Try to find out independent ones. */
192 result = get_independent_commits (result);
193
194 return result;
195
196 fail:
197 result = data.result;
198 while (result) {
199 commit = result->data;
200 seaf_commit_unref (commit);
201 result = g_list_delete_link (result, result);
202 }
203 g_hash_table_destroy (commit_hash);
204 return NULL;
205 }
206
207 /*
208 * Returns common ancesstor for two branches.
209 * Any two commits should have a common ancestor.
210 * So returning NULL indicates an error, for e.g. corupt commit.
211 */
212 SeafCommit *
get_merge_base(SeafCommit * head,SeafCommit * remote)213 get_merge_base (SeafCommit *head, SeafCommit *remote)
214 {
215 GList *result, *iter;
216 SeafCommit *one, **twos;
217 int n, i;
218 SeafCommit *ret = NULL;
219
220 one = head;
221 twos = (SeafCommit **) calloc (1, sizeof(SeafCommit *));
222 twos[0] = remote;
223 n = 1;
224 result = merge_bases_many (one, n, twos);
225 free (twos);
226 if (!result || !result->next)
227 goto done;
228
229 /*
230 * More than one common ancestors.
231 * Loop until the oldest common ancestor is found.
232 */
233 while (1) {
234 n = g_list_length (result) - 1;
235 one = result->data;
236 twos = calloc (n, sizeof(SeafCommit *));
237 for (iter = result->next, i = 0; i < n; iter = iter->next, i++) {
238 twos[i] = iter->data;
239 }
240 g_list_free (result);
241
242 result = merge_bases_many (one, n, twos);
243 free (twos);
244 if (!result || !result->next)
245 break;
246 }
247
248 done:
249 if (result)
250 ret = result->data;
251 g_list_free (result);
252
253 return ret;
254 }
255
256 /*
257 * Returns true if src_head is ahead of dst_head.
258 */
259 gboolean
is_fast_forward(const char * repo_id,int version,const char * src_head,const char * dst_head)260 is_fast_forward (const char *repo_id, int version,
261 const char *src_head, const char *dst_head)
262 {
263 VCCompareResult res;
264
265 res = vc_compare_commits (repo_id, version, src_head, dst_head);
266
267 return (res == VC_FAST_FORWARD);
268 }
269
270 VCCompareResult
vc_compare_commits(const char * repo_id,int version,const char * c1,const char * c2)271 vc_compare_commits (const char *repo_id, int version,
272 const char *c1, const char *c2)
273 {
274 SeafCommit *commit1, *commit2, *ca;
275 VCCompareResult ret;
276
277 /* Treat the same as up-to-date. */
278 if (strcmp (c1, c2) == 0)
279 return VC_UP_TO_DATE;
280
281 commit1 = seaf_commit_manager_get_commit (seaf->commit_mgr, repo_id, version, c1);
282 if (!commit1)
283 return VC_INDEPENDENT;
284
285 commit2 = seaf_commit_manager_get_commit (seaf->commit_mgr, repo_id, version, c2);
286 if (!commit2) {
287 seaf_commit_unref (commit1);
288 return VC_INDEPENDENT;
289 }
290
291 ca = get_merge_base (commit1, commit2);
292
293 if (!ca)
294 ret = VC_INDEPENDENT;
295 else if (strcmp(ca->commit_id, commit1->commit_id) == 0)
296 ret = VC_UP_TO_DATE;
297 else if (strcmp(ca->commit_id, commit2->commit_id) == 0)
298 ret = VC_FAST_FORWARD;
299 else
300 ret = VC_INDEPENDENT;
301
302 if (ca) seaf_commit_unref (ca);
303 seaf_commit_unref (commit1);
304 seaf_commit_unref (commit2);
305 return ret;
306 }
307
308 /**
309 * Diff a specific file with parent(s).
310 * If @commit is a merge, both parents will be compared.
311 * @commit must have this file and it's id is given in @file_id.
312 *
313 * Returns 0 if there is no difference; 1 otherwise.
314 * If returns 0, @parent will point to the next commit to traverse.
315 * If I/O error occurs, @error will be set.
316 */
317 static int
diff_parents_with_path(SeafCommit * commit,const char * repo_id,const char * store_id,int version,const char * path,const char * file_id,char * parent,GError ** error)318 diff_parents_with_path (SeafCommit *commit,
319 const char *repo_id,
320 const char *store_id,
321 int version,
322 const char *path,
323 const char *file_id,
324 char *parent,
325 GError **error)
326 {
327 SeafCommit *p1 = NULL, *p2 = NULL;
328 char *file_id_p1 = NULL, *file_id_p2 = NULL;
329 int ret = 0;
330
331 p1 = seaf_commit_manager_get_commit (seaf->commit_mgr,
332 commit->repo_id,
333 commit->version,
334 commit->parent_id);
335 if (!p1) {
336 g_warning ("Failed to find commit %s.\n", commit->parent_id);
337 g_set_error (error, SEAFILE_DOMAIN, SEAF_ERR_GENERAL, " ");
338 return 0;
339 }
340
341 if (strcmp (p1->root_id, EMPTY_SHA1) == 0) {
342 seaf_commit_unref (p1);
343 return 1;
344 }
345
346 if (commit->second_parent_id) {
347 p2 = seaf_commit_manager_get_commit (seaf->commit_mgr,
348 commit->repo_id,
349 commit->version,
350 commit->second_parent_id);
351 if (!p2) {
352 g_warning ("Failed to find commit %s.\n", commit->second_parent_id);
353 seaf_commit_unref (p1);
354 g_set_error (error, SEAFILE_DOMAIN, SEAF_ERR_GENERAL, " ");
355 return 0;
356 }
357 }
358
359 if (!p2) {
360 file_id_p1 = seaf_fs_manager_path_to_obj_id (seaf->fs_mgr,
361 store_id,
362 version,
363 p1->root_id, path,
364 NULL,
365 error);
366 if (*error)
367 goto out;
368 if (!file_id_p1 || strcmp (file_id, file_id_p1) != 0)
369 ret = 1;
370 else
371 memcpy (parent, p1->commit_id, 41);
372 } else {
373 file_id_p1 = seaf_fs_manager_path_to_obj_id (seaf->fs_mgr,
374 store_id,
375 version,
376 p1->root_id, path,
377 NULL, error);
378 if (*error)
379 goto out;
380 file_id_p2 = seaf_fs_manager_path_to_obj_id (seaf->fs_mgr,
381 store_id,
382 version,
383 p2->root_id, path,
384 NULL, error);
385 if (*error)
386 goto out;
387
388 if (file_id_p1 && file_id_p2) {
389 if (strcmp(file_id, file_id_p1) != 0 &&
390 strcmp(file_id, file_id_p2) != 0)
391 ret = 1;
392 else if (strcmp(file_id, file_id_p1) == 0)
393 memcpy (parent, p1->commit_id, 41);
394 else
395 memcpy (parent, p2->commit_id, 41);
396 } else if (file_id_p1 && !file_id_p2) {
397 if (strcmp(file_id, file_id_p1) != 0)
398 ret = 1;
399 else
400 memcpy (parent, p1->commit_id, 41);
401 } else if (!file_id_p1 && file_id_p2) {
402 if (strcmp(file_id, file_id_p2) != 0)
403 ret = 1;
404 else
405 memcpy (parent, p2->commit_id, 41);
406 } else {
407 ret = 1;
408 }
409 }
410
411 out:
412 g_free (file_id_p1);
413 g_free (file_id_p2);
414
415 if (p1)
416 seaf_commit_unref (p1);
417 if (p2)
418 seaf_commit_unref (p2);
419
420 return ret;
421 }
422
423 static int
get_file_modifier_mtime_v0(const char * repo_id,const char * store_id,int version,const char * head,const char * path,char ** modifier,gint64 * mtime)424 get_file_modifier_mtime_v0 (const char *repo_id, const char *store_id, int version,
425 const char *head, const char *path,
426 char **modifier, gint64 *mtime)
427 {
428 char commit_id[41];
429 SeafCommit *commit = NULL;
430 char *file_id = NULL;
431 int changed;
432 int ret = 0;
433 GError *error = NULL;
434
435 *modifier = NULL;
436 *mtime = 0;
437
438 memcpy (commit_id, head, 41);
439
440 while (1) {
441 commit = seaf_commit_manager_get_commit (seaf->commit_mgr,
442 repo_id, version,
443 commit_id);
444 if (!commit) {
445 ret = -1;
446 break;
447 }
448
449 /* We hit the initial commit. */
450 if (!commit->parent_id)
451 break;
452
453 file_id = seaf_fs_manager_path_to_obj_id (seaf->fs_mgr,
454 store_id, version,
455 commit->root_id,
456 path,
457 NULL,
458 &error);
459 if (error) {
460 g_clear_error (&error);
461 ret = -1;
462 break;
463 }
464 /* We expect commit to have this file. */
465 if (!file_id) {
466 ret = -1;
467 break;
468 }
469
470 changed = diff_parents_with_path (commit,
471 repo_id, store_id, version,
472 path, file_id,
473 commit_id, &error);
474 if (error) {
475 g_clear_error (&error);
476 ret = -1;
477 break;
478 }
479
480 if (changed) {
481 *modifier = g_strdup (commit->creator_name);
482 *mtime = commit->ctime;
483 break;
484 } else {
485 /* If this commit doesn't change the file, commit_id will be set
486 * to the parent commit to traverse.
487 */
488 g_free (file_id);
489 seaf_commit_unref (commit);
490 }
491 }
492
493 g_free (file_id);
494 if (commit)
495 seaf_commit_unref (commit);
496 return ret;
497 }
498
499 static int
get_file_modifier_mtime_v1(const char * repo_id,const char * store_id,int version,const char * head,const char * path,char ** modifier,gint64 * mtime)500 get_file_modifier_mtime_v1 (const char *repo_id, const char *store_id, int version,
501 const char *head, const char *path,
502 char **modifier, gint64 *mtime)
503 {
504 SeafCommit *commit = NULL;
505 SeafDir *dir = NULL;
506 SeafDirent *dent = NULL;
507 int ret = 0;
508
509 commit = seaf_commit_manager_get_commit (seaf->commit_mgr,
510 repo_id, version,
511 head);
512 if (!commit) {
513 seaf_warning ("Failed to get commit %s.\n", head);
514 return -1;
515 }
516
517 char *parent = g_path_get_dirname (path);
518 if (strcmp(parent, ".") == 0) {
519 g_free (parent);
520 parent = g_strdup("");
521 }
522 char *filename = g_path_get_basename (path);
523
524 dir = seaf_fs_manager_get_seafdir_by_path (seaf->fs_mgr,
525 store_id, version,
526 commit->root_id,
527 parent, NULL);
528 if (!dir) {
529 seaf_warning ("dir %s doesn't exist in repo %s.\n", parent, repo_id);
530 ret = -1;
531 goto out;
532 }
533
534 GList *p;
535 for (p = dir->entries; p; p = p->next) {
536 SeafDirent *d = p->data;
537 if (strcmp (d->name, filename) == 0) {
538 dent = d;
539 break;
540 }
541 }
542
543 if (!dent) {
544 goto out;
545 }
546
547 *modifier = g_strdup(dent->modifier);
548 *mtime = dent->mtime;
549
550 out:
551 g_free (parent);
552 g_free (filename);
553 seaf_commit_unref (commit);
554 seaf_dir_free (dir);
555
556 return ret;
557 }
558
559 /**
560 * Get the user who last changed a file and the mtime.
561 * @head: head commit to start the search.
562 * @path: path of the file.
563 */
564 int
get_file_modifier_mtime(const char * repo_id,const char * store_id,int version,const char * head,const char * path,char ** modifier,gint64 * mtime)565 get_file_modifier_mtime (const char *repo_id,
566 const char *store_id,
567 int version,
568 const char *head,
569 const char *path,
570 char **modifier,
571 gint64 *mtime)
572 {
573 if (version > 0)
574 return get_file_modifier_mtime_v1 (repo_id, store_id, version,
575 head, path,
576 modifier, mtime);
577 else
578 return get_file_modifier_mtime_v0 (repo_id, store_id, version,
579 head, path,
580 modifier, mtime);
581 }
582
583 char *
gen_conflict_path(const char * origin_path,const char * modifier,gint64 mtime)584 gen_conflict_path (const char *origin_path,
585 const char *modifier,
586 gint64 mtime)
587 {
588 char time_buf[64];
589 time_t t = (time_t)mtime;
590 char *copy = g_strdup (origin_path);
591 GString *conflict_path = g_string_new (NULL);
592 char *dot, *ext;
593
594 strftime(time_buf, 64, "%Y-%m-%d-%H-%M-%S", localtime(&t));
595
596 dot = strrchr (copy, '.');
597
598 if (dot != NULL) {
599 *dot = '\0';
600 ext = dot + 1;
601 if (modifier)
602 g_string_printf (conflict_path, "%s (SFConflict %s %s).%s",
603 copy, modifier, time_buf, ext);
604 else
605 g_string_printf (conflict_path, "%s (SFConflict %s).%s",
606 copy, time_buf, ext);
607 } else {
608 if (modifier)
609 g_string_printf (conflict_path, "%s (SFConflict %s %s)",
610 copy, modifier, time_buf);
611 else
612 g_string_printf (conflict_path, "%s (SFConflict %s)",
613 copy, time_buf);
614 }
615
616 g_free (copy);
617 return g_string_free (conflict_path, FALSE);
618 }
619
620 char *
gen_conflict_path_wrapper(const char * repo_id,int version,const char * head,const char * in_repo_path,const char * original_path)621 gen_conflict_path_wrapper (const char *repo_id, int version,
622 const char *head, const char *in_repo_path,
623 const char *original_path)
624 {
625 char *modifier;
626 gint64 mtime;
627
628 /* XXX: this function is only used in client, so store_id is always
629 * the same as repo_id. This can be changed if it's also called in
630 * server.
631 */
632 if (get_file_modifier_mtime (repo_id, repo_id, version, head, in_repo_path,
633 &modifier, &mtime) < 0)
634 return NULL;
635
636 return gen_conflict_path (original_path, modifier, mtime);
637 }
638