/* ancestry.c: * * vim:smartindent ts=8:sts=2:sta:et:ai:shiftwidth=2 **************************************************************** * Copyright (C) 2003 Tom Lord * Copyright (C) 2005 Canonical Limited * Authors: Robert Collins * * See the file "COPYING" for further information about * the copyright and warranty status of this work. */ #include "hackerlab/bugs/exception.h" #include "hackerlab/bugs/panic.h" #include "hackerlab/char/str.h" #include "hackerlab/fs/file-names.h" #include "hackerlab/os/errno.h" #include "hackerlab/os/sys/wait.h" #include "hackerlab/vu/safe.h" #include "libawk/associative.h" #include "libawk/trim.h" #include "libfsutils/file-contents.h" #include "libfsutils/tmp-files.h" #include "libarch/archives.h" #include "libarch/arch-cache.h" #include "libarch/cached-archive.h" #include "libarch/libraries.h" #include "libarch/namespace.h" #include "libarch/merge-points.h" #include "libarch/ancestry.h" static arch_patch_id * arch_ancestry_from_revision (void * context, arch_patch_id * patch_id, int soft_errors); rel_table arch_trace_ancestry (void * context, struct arch_archive * arch, arch_patch_id * starting_patch_id, int merges) { rel_table answer = 0; int done = 0; arch_archive_connection_cache cache; arch_patch_id * patch_id = arch_patch_id_copy (starting_patch_id); arch_archive_connection_cache_init (&cache); if (arch) arch_archive_connection_cache_add (&cache, arch); while (!done) { struct arch_archive * this_arch = 0; this_arch = arch_archive_connection_cache_find_or_maybe_connect (&cache, arch_patch_id_archive (patch_id), 0); if (!this_arch) { rel_add_records (&answer, rel_make_record (arch_patch_id_patch_id(patch_id), "???", 0), 0); done = 1; } else { arch_patch_id * ancestor = NULL; if (!merges) rel_add_records (&answer, rel_make_record (arch_patch_id_patch_id(patch_id), arch_patch_id_patch_id(patch_id), 0), 0); else { enum arch_revision_type type; /* FIXME: grab ancestry here if it exists */ arch_revision_type (&type, 0, NULL, this_arch, patch_id); if (type == arch_continuation_revision) { rel_add_records (&answer, rel_make_record (arch_patch_id_patch_id(patch_id), arch_patch_id_patch_id(patch_id), 0), 0); } else { rel_table merges = 0; int x; merges = arch_archive_merge_points (this_arch, arch_patch_id_revision (patch_id), 0, 0, 0); for (x = 0; x < rel_n_records (merges); ++x) { rel_add_records (&answer, rel_make_record (arch_patch_id_patch_id(patch_id), merges[x][1], 0), 0); } rel_free_table (merges); } } ancestor = arch_patch_ancestor (talloc_context, patch_id, 0); if (!ancestor) { done = 1; } else { talloc_free (patch_id); patch_id = ancestor; } } } arch_archive_connection_cache_finalise (&cache, arch); talloc_steal (context, ar_base(answer)); return answer; } static int ancestry_parse_baz_1_is_patch_id (t_uchar const *record) { if (!str_cmp_prefix (ARCH_ANCESTRY_PATCH_PREFIX, record )) return -1; if (!str_cmp (ARCH_ANCESTRY_PATCH_PARTIAL, record )) return -1; return 0; } static t_uchar * ancestry_parse_baz_1_patch_id (t_uchar const *record) { if (!str_cmp_prefix (ARCH_ANCESTRY_PATCH_PREFIX, record )) return str_save (0, record + str_length (ARCH_ANCESTRY_PATCH_PREFIX)); if (!str_cmp (ARCH_ANCESTRY_PATCH_PARTIAL, record )) return str_save (0, record); return NULL; } static rel_table ancestry_parse_baz_1 (rel_table raw, int start_from) { rel_table result = NULL; int current_line; for (current_line = start_from; current_line < rel_n_records(raw); ++current_line) { if (ancestry_parse_baz_1_is_patch_id (raw[current_line][0])) { t_uchar *patch_id = ancestry_parse_baz_1_patch_id (raw[current_line][0]); rel_add_records(&result, rel_make_record (patch_id, 0), 0); lim_free (0, patch_id); } } return result; } static rel_table ancestry_parse(t_uchar const *content) { /* TODO: if it looks like its gpg, run it through gpg */ rel_table temp_table = rel_nl_split ((t_uchar *)content); rel_table answer = NULL; int start_record; for (start_record = 0; start_record < rel_n_records (temp_table); ++start_record) if (!str_cmp(ARCH_ANCESTRY_VERSION_BAZ_1, temp_table[start_record][0])) { answer = ancestry_parse_baz_1 (temp_table, start_record + 1); break; } rel_free_table (temp_table); return answer; } static rel_table partial_ancestry_from_full(rel_table full, arch_patch_id * patch_id) { rel_table result = NULL; int row = 0; while (row < rel_n_records (full) && str_cmp (arch_patch_id_patch_id (patch_id), full[row][0])) ++row; for (; row < rel_n_records (full); ++row) { rel_add_records (&result, rel_copy_record (full[row]), 0); } return result; } static assoc_table arch_ancestors = NULL; static arch_archive_connection_cache global_cache = { NULL }; /** * \brief get a cached patch ancestor. * \throw ENOENT if there is no cached entry * NULL for terminal revisions * a patch id for a specific ancestor. */ static arch_patch_id * arch_cached_patch_ancestor (void * context, arch_patch_id * patch_id) { t_uchar *result = assoc_ref (arch_ancestors, arch_patch_id_patch_id (patch_id)); invariant (str_cmp (arch_patch_id_patch_id (patch_id), ARCH_ANCESTRY_PATCH_PARTIAL)); if (result && str_cmp (result, ARCH_ANCESTRY_PATCH_PARTIAL)) { if (!str_length (result)) { /* penultimate ancestor - "" in the hash */ return NULL; } return talloc_steal (context, arch_patch_id_new (result)); } /* memory cache miss */ { t_uchar * ancestor_query = arch_cache_query_new (patch_id, "ancestor"); t_uchar * temp_result = NULL; if (ancestor_query && arch_cache_has_answer (ancestor_query)) { temp_result = arch_cache_get_line (ancestor_query); invariant (temp_result != NULL); result = trim_surrounding_ws (temp_result); } lim_free (0, ancestor_query); if (!result || !str_cmp (result, ARCH_ANCESTRY_PATCH_PARTIAL)) { lim_free (0, temp_result); /* not there either, return partial */ Throw (exception (ENOENT, "No cache entry")); } else { arch_patch_id * answer; if (!str_length (result)) answer = NULL; else answer = arch_patch_id_new (result); lim_free (0, temp_result); return talloc_steal (context, answer); } } } /** * \brief find the ancestory for patch_id * * find the ancestor for patch_id from: * - known ancestry data * - the archive * * maintains the in-core ancestry cache. * \throw ENOENT if the ancestor cannot be found, or any unexpected child * function exceptions raised during its operation. * \param context the talloc context to put results in * \param patch_id the patch to get the ancestor of * \param cached_only - only look in the baz cache. * \return the patch id. NULL is returned if there is no ancestor. */ arch_patch_id * arch_patch_ancestor (void * context, arch_patch_id * patch_id, int cached_only) { /* cache lookup */ arch_patch_id * answer = NULL; t_uchar *result = NULL; struct arch_archive *arch; int found = -1; struct exception * e; Try { answer = arch_cached_patch_ancestor (context, patch_id); found = 1; } Catch (e) { /* dont mask critical errors */ if (e->code < 0) Throw (e); talloc_free (e); if (cached_only) Throw (exception (ENOENT, "Could not retrieve ancestor")); found = 0; } if (found) return talloc_steal (context, answer); /* cache miss */ Try { answer = arch_ancestry_from_revision (context, patch_id, 1); found = 1; } Catch (e) { /* dont mask critical errors */ if (e->code < 0) Throw (e); talloc_free (e); found = 0; } if (found) return talloc_steal (context, answer); /* old api .. */ arch = arch_archive_connection_cache_find_or_maybe_connect (&global_cache, arch_patch_id_archive (patch_id), 1); if (arch) { /* FIXME: teach arch_ancestor_revision about soft errors */ result = arch_ancestor_revision (arch, arch_patch_id_revision (patch_id)); if (!result) { /* penultimate ancestor */ arch_ancestry_note_ancestor (patch_id, ""); return NULL; } else /* when ancestor_revision does soft errors.. if (str_cmp (result, ARCH_ANCESTRY_PATCH_PARTIAL)) */ { arch_ancestry_note_ancestor (patch_id, result); answer = talloc_steal (context, arch_patch_id_new (result)); lim_free (0, result); return answer; } } Throw (exception (ENOENT, "Could not retrieve ancestor")); } /* we've observed the ancestor patch_id: * "" for patch_id is the import rev. * ARCH_ANCESTRY_PATCH_PARTIAL for we are noting that we couldn't find the ancestor * $other_patch_id for a specific ancestor */ void arch_ancestry_note_ancestor (arch_patch_id * patch_id, t_uchar const *ancestor) { struct exception * e; invariant (ancestor != NULL); invariant (str_cmp (arch_patch_id_patch_id (patch_id), ARCH_ANCESTRY_PATCH_PARTIAL)); Try arch_cached_patch_ancestor (talloc_context, patch_id); Catch (e) { t_uchar * ancestor_query; /* dont mask critical errors */ if (e->code < 0) Throw (e); talloc_free (e); ancestor_query = arch_cache_query_new (patch_id, "ancestor"); arch_cache_put_line (ancestor_query, ancestor); assoc_set (&arch_ancestors, arch_patch_id_patch_id (patch_id), (t_uchar *)ancestor); lim_free (0, ancestor_query); } } static void arch_ancestry_insert_ancestry (rel_table revisions) { int row; if (!revisions) return; for (row=0; row < rel_n_records (revisions) - 1; ++row) { arch_patch_id * temp = arch_patch_id_new (revisions[row][0]); arch_ancestry_note_ancestor (temp, revisions[row + 1][0]); talloc_free (temp); } if (str_cmp(ARCH_ANCESTRY_PATCH_PARTIAL, revisions[rel_n_records (revisions) - 1][0])) { arch_patch_id * temp = arch_patch_id_new (revisions[rel_n_records (revisions) - 1][0]); arch_ancestry_note_ancestor (temp, ""); talloc_free (temp); } } /* append locally available ancestry data * precondition: there is at least one non-PARTIAL row in current_ancestry */ static rel_table ancestry_append_available (rel_table current_ancestry) { rel_table answer = NULL; t_uchar * fq_current; arch_patch_id * current; int position = 0; if (!rel_n_records(current_ancestry)) return NULL; fq_current = current_ancestry[position][0]; while (fq_current && str_cmp (ARCH_ANCESTRY_PATCH_PARTIAL, fq_current)) { rel_add_records (&answer, rel_copy_record (current_ancestry[position]), 0); ++position; if (rel_n_records (current_ancestry) > position) fq_current = current_ancestry[position][0]; else fq_current = NULL; } { struct exception * e; Try { current = talloc_steal (talloc_context, arch_patch_id_new (answer[rel_n_records(answer) - 1][0])); while (current && str_cmp (arch_patch_id_patch_id (current), ARCH_ANCESTRY_PATCH_PARTIAL)) { arch_patch_id *next = arch_patch_ancestor (talloc_context, current, 1); if (next) rel_add_records (&answer, rel_make_record (arch_patch_id_patch_id (next), 0), 0); talloc_free (current); current = next; } talloc_free (current); } Catch (e) { /* dont mask critical errors */ if (e->code < 0) Throw (e); talloc_free (e); } } return answer; } /* scan the network for the ancestry relating to patch_id. * stop when minimum_depth is reached, or if we join with * maybe_ancestor. */ static rel_table ancestry_scan (t_uchar const * patch_id, rel_table maybe_ancestor, int minimum_depth) { arch_patch_id * current = arch_patch_id_new (patch_id); rel_table answer = NULL; rel_table final = NULL; int depth = 0; arch_ancestry_insert_ancestry (maybe_ancestor); rel_add_records (&answer, rel_make_record ((t_uchar *)patch_id, 0), 0); while (minimum_depth == -1 || depth < minimum_depth) { /* pre-condition: * * current tell use the patch_id to append to the result. */ int partial = 0; arch_patch_id * next_revision = NULL; struct exception * e; Try { next_revision = arch_patch_ancestor (NULL, current, 0); } Catch (e) { /* dont mask critical errors */ if (e->code < 0) Throw (e); talloc_free (e); partial = -1; rel_add_records(&answer, rel_make_record (ARCH_ANCESTRY_PATCH_PARTIAL, 0), 0); } talloc_free (current); if (partial || !next_revision) current = NULL; else /* normal ancestor */ { rel_add_records (&answer, rel_make_record (arch_patch_id_patch_id (next_revision), 0), 0); current = next_revision; } ++depth; if (!current || partial) break; } talloc_free (current); final = ancestry_append_available (answer); rel_free_table (answer); arch_archive_connection_cache_finalise (&global_cache, NULL); return final; } static void ancestry_snap (struct arch_project_tree *tree, rel_table answer) { int ignore; int outfd; t_uchar * ancestry_file = file_name_in_vicinity (0, tree->root, ARCH_PROJECT_TREE_ANCESTRY_FILE); vu_unlink (&ignore, ancestry_file); outfd = safe_open (ancestry_file, (O_WRONLY | O_CREAT | O_EXCL), 0444); lim_free (0, ancestry_file); ancestry_write (answer, outfd, -1); safe_close (outfd); } void ancestry_write (rel_table answer, int outfd, int maximum_depth) { int position; if (maximum_depth < 1 || maximum_depth > rel_n_records(answer)) { maximum_depth = rel_n_records (answer); } safe_printfmt (outfd, ARCH_ANCESTRY_VERSION_BAZ_1"\n"); for (position = 0; position < maximum_depth ; ++position) { if (str_cmp (ARCH_ANCESTRY_PATCH_PARTIAL, answer[position][0])) safe_printfmt (outfd, ARCH_ANCESTRY_PATCH_PREFIX"%s\n", answer[position][0]); else safe_printfmt (outfd, "%s\n", answer[position][0]); } if (maximum_depth < rel_n_records (answer)) safe_printfmt (outfd, "%s\n", ARCH_ANCESTRY_PATCH_PARTIAL); } /* retrieve the patch ancestry for for patch_id from tree tree */ static rel_table patch_ancestry_from_tree (struct arch_project_tree *tree, arch_patch_id * patch_id, int minimum_depth) { rel_table answer = NULL; if (arch_project_tree_file_exists(tree, ARCH_PROJECT_TREE_ANCESTRY_FILE)) { t_uchar *candidate_text = arch_project_tree_file_contents(tree, ARCH_PROJECT_TREE_ANCESTRY_FILE); rel_table candidate = ancestry_parse(candidate_text); lim_free (0, candidate_text); answer = partial_ancestry_from_full (candidate, patch_id); rel_free_table (candidate); } return answer; } /* patch_ancestry: * retrieve the ancestry for the patch patch_id, looking for * a minimum depth as supplied. If there are more revisions * than minimum_depth trivially available, they will be supplied * to the caller. -1 means retrieve the entire ancestry. * 0 means retrieve as much as is immediately available. * * The ancestry is returned as a rel_table. it has one field * the patch-id for that element of the ancestry. The most * recent revisions are at the lowest entries in the * returned table. * * Once the ancestry is calculated, it is automatically * memoised to {arch}/+ancestry. * TODO: teach commit to update +ancestry in the archive * upon commit * * See http://wiki.gnuarch.org/moin.cgi/AncestryFileFormat * for the general format of these files. * * If soft_errors is 1, any failure encountered will result in * NULL for the result * If it is 2, failures will result in the current known history * being returned. * * history is established by the following lookup priority: * 1) If there is a {arch}/+ancestry file it is processed. * * 2) If there is a pristine tree available for patch_id, * it is consulted for a +ancestry file. * * 3) The file ancestry is looked for in the archive that the * patch belongs too - if it has such a archive, and its * registered. * * 4) The log message for the request revision is consulted * for its immediate ancestor, and then the search resumes * from there. */ /** * \brief get the revision-history for a specific patch. * \throw E* if no ancestry is available. * network access to revisions is presumed flakey and recoverable * errors are caught. unknown errors are propogated up. * \param optional_tree a tree to gather ancestry from * \param patch_id the patch to gather ancestry for * \param minimum depth the minimum amount of history to attempt to * retrieve. */ rel_table patch_ancestry (void * context, struct arch_project_tree *optional_tree, arch_patch_id * patch_id, int minimum_depth) { rel_table answer = NULL; /* look in the local tree */ if (optional_tree && arch_project_tree_file_exists(optional_tree, ARCH_PROJECT_TREE_ANCESTRY_FILE)) { int do_snap = 0; t_uchar *candidate_text = arch_project_tree_file_contents(optional_tree, ARCH_PROJECT_TREE_ANCESTRY_FILE); rel_table candidate = ancestry_parse(candidate_text); lim_free (0, candidate_text); answer = partial_ancestry_from_full (candidate, patch_id); if (!answer) { answer = ancestry_scan (arch_patch_id_patch_id (patch_id), candidate, minimum_depth); do_snap = -1; } rel_free_table (candidate); if (!answer) Throw (exception (ENOENT, "Empty or invalid cached ancestry file")); } else /* look in a reference tree */ { arch_project_tree_t * pristine_tree; pristine_tree = arch_library_find (NULL, patch_id, 1); if (pristine_tree) { answer = patch_ancestry_from_tree (pristine_tree, patch_id, minimum_depth); arch_project_tree_delete(pristine_tree); } } /* scan the network */ answer = ancestry_scan (arch_patch_id_patch_id (patch_id), NULL, minimum_depth); if (!answer) Throw (exception (ENOENT, "Empty or invalid cached ancestry file")); if (optional_tree && answer) ancestry_snap (optional_tree, answer); talloc_steal (context, ar_base (answer)); return answer; } /* insert a ancestry file to a revision * -1 depth means all known, * 0 means just the revisions data*/ void ancestry_upload_patch (struct arch_archive * arch, arch_patch_id * patch_id, int max_depth) { int infd = -1; /* working file */ t_uchar *tmp_file = talloc_tmp_file_name (talloc_context, ".", ",,ancestry"); t_uchar *tmp_gz_file = talloc_tmp_file_name (tmp_file, ".", ",,ancestry"); /* generate ancestry data */ rel_table ancestry = patch_ancestry (tmp_file, NULL, patch_id, max_depth); invariant (rel_n_records (ancestry) > 0); /* create a ancestry file */ { int outfd = safe_open (tmp_file, (O_WRONLY | O_CREAT | O_EXCL), 0444); ancestry_write (ancestry, outfd, max_depth); safe_close (outfd); } /* gzip it */ /* FIXME: magic etc etc config detection for gzip */ { /* FIXME: write a system replacement using ar */ t_uchar * command = str_alloc_cat_many (0, "gzip -c '", tmp_file, "' > '", tmp_gz_file, "'", str_end); int status = system (command); if (status == -1) { safe_printfmt (2, "Fork failed when running gzip\n"); exit (2); } if (!WIFEXITED (status)) { safe_printfmt (2, "Child process did not exit - caught a signal or something unexpected happened, status is (%d)\n", status); exit (2); } if (WEXITSTATUS (status)) { safe_printfmt (2, "gzipping ancestry file for upload to the archive failed, status is (%d)\n", WEXITSTATUS(status)); exit (2); } } /* unlink the old file */ safe_unlink (tmp_file); /* open the zip */ infd = safe_open (tmp_gz_file, O_RDONLY, 0); /* upload */ { t_uchar *error = NULL; arch_archive_put_ancestry (&error, arch, arch_patch_id_revision (patch_id), infd); } safe_close (infd); safe_unlink (tmp_gz_file); talloc_free (tmp_file); } /** * \brief get the ancestry data cache from a revision in the archive * \throw system errors only * \param patch_id the patch to get ancestors for * \param soft errors exit / return PARTIAL on error */ arch_patch_id * arch_ancestry_from_revision (void * context, arch_patch_id * patch_id, int soft_errors) { /* retrieve tarball */ struct arch_archive *arch = arch_archive_connection_cache_find_or_maybe_connect (&global_cache, arch_patch_id_archive (patch_id), soft_errors); t_uchar *tmp_gz_file = talloc_tmp_file_name (talloc_context, ".", ",,ancestry"); t_uchar *tmp_file = talloc_tmp_file_name (tmp_gz_file, ".", ",,ancestry"); if (arch) { int ignore; int outfd; int has_ancestry; arch_revision_type (NULL, NULL, &has_ancestry, arch, patch_id); if (!has_ancestry) { goto finished; } vu_unlink (&ignore, tmp_gz_file); outfd = safe_open (tmp_gz_file, (O_WRONLY | O_CREAT | O_EXCL), 0444); arch_archive_get_ancestry (outfd, arch, arch_patch_id_revision (patch_id)); safe_close (outfd); } else goto finished; /* ungzip it */ /* FIXME: magic etc etc config detection for gzip */ { /* FIXME: write a system replacement using ar and pipe the result */ t_uchar * command = str_alloc_cat_many (0, "gunzip -c '", tmp_gz_file, "' > '", tmp_file, "'", str_end); int status = system (command); if (status == -1) { safe_printfmt (2, "Fork failed when running gunzip\n"); exit (2); } if (!WIFEXITED (status)) { safe_printfmt (2, "Child process did not exit - caught a signal or something unexpected happened, status is (%d)\n", status); exit (2); } if (WEXITSTATUS (status)) { safe_printfmt (2, "un gzipping ancestry file from archive failed, status is (%d)\n", WEXITSTATUS(status)); exit (2); } } /* unlink the old file */ safe_unlink (tmp_gz_file); { t_uchar *ancestry_text = file_contents(tmp_file); rel_table ancestry = ancestry_parse(ancestry_text); arch_ancestry_insert_ancestry (ancestry); rel_free_table (ancestry); lim_free (0, ancestry_text); } safe_unlink (tmp_file); finished: talloc_free (tmp_gz_file); return arch_cached_patch_ancestor (context, patch_id); } /* tag: Tom Lord Thu Jun 26 18:41:53 2003 (ancestry.c) */