git/notes.c

#define USE_THE_REPOSITORY_VARIABLE

#include "git-compat-util.h"
#include "config.h"
#include "environment.h"
#include "hex.h"
#include "notes.h"
#include "object-name.h"
#include "object-store-ll.h"
#include "utf8.h"
#include "strbuf.h"
#include "tree-walk.h"
#include "string-list.h"
#include "refs.h"

/*
 * Use a non-balancing simple 16-tree structure with struct int_node as
 * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
 * 16-array of pointers to its children.
 * The bottom 2 bits of each pointer is used to identify the pointer type
 * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
 * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
 * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
 * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
 *
 * The root node is a statically allocated struct int_node.
 */
struct int_node { … };

/*
 * Leaf nodes come in two variants, note entries and subtree entries,
 * distinguished by the LSb of the leaf node pointer (see above).
 * As a note entry, the key is the SHA1 of the referenced object, and the
 * value is the SHA1 of the note object.
 * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
 * referenced object, using the last byte of the key to store the length of
 * the prefix. The value is the SHA1 of the tree object containing the notes
 * subtree.
 */
struct leaf_node { … };

/*
 * A notes tree may contain entries that are not notes, and that do not follow
 * the naming conventions of notes. There are typically none/few of these, but
 * we still need to keep track of them. Keep a simple linked list sorted alpha-
 * betically on the non-note path. The list is populated when parsing tree
 * objects in load_subtree(), and the non-notes are correctly written back into
 * the tree objects produced by write_notes_tree().
 */
struct non_note { … };

#define PTR_TYPE_NULL …
#define PTR_TYPE_INTERNAL …
#define PTR_TYPE_NOTE …
#define PTR_TYPE_SUBTREE …

#define GET_PTR_TYPE(ptr) …
#define CLR_PTR_TYPE(ptr) …
#define SET_PTR_TYPE(ptr, type) …

#define GET_NIBBLE(n, sha1) …

#define KEY_INDEX …
#define FANOUT_PATH_SEPARATORS …
#define FANOUT_PATH_SEPARATORS_MAX …
#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) …

struct notes_tree default_notes_tree;

static struct string_list display_notes_refs = …;
static struct notes_tree **display_notes_trees;

static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
		struct int_node *node, unsigned int n);

/*
 * Search the tree until the appropriate location for the given key is found:
 * 1. Start at the root node, with n = 0
 * 2. If a[0] at the current level is a matching subtree entry, unpack that
 *    subtree entry and remove it; restart search at the current level.
 * 3. Use the nth nibble of the key as an index into a:
 *    - If a[n] is an int_node, recurse from #2 into that node and increment n
 *    - If a matching subtree entry, unpack that subtree entry (and remove it);
 *      restart search at the current level.
 *    - Otherwise, we have found one of the following:
 *      - a subtree entry which does not match the key
 *      - a note entry which may or may not match the key
 *      - an unused leaf node (NULL)
 *      In any case, set *tree and *n, and return pointer to the tree location.
 */
static void **note_tree_search(struct notes_tree *t, struct int_node **tree,
		unsigned char *n, const unsigned char *key_sha1)
{ … }

/*
 * To find a leaf_node:
 * Search to the tree location appropriate for the given key:
 * If a note entry with matching key, return the note entry, else return NULL.
 */
static struct leaf_node *note_tree_find(struct notes_tree *t,
		struct int_node *tree, unsigned char n,
		const unsigned char *key_sha1)
{ … }

/*
 * How to consolidate an int_node:
 * If there are > 1 non-NULL entries, give up and return non-zero.
 * Otherwise replace the int_node at the given index in the given parent node
 * with the only NOTE entry (or a NULL entry if no entries) from the given
 * tree, and return 0.
 */
static int note_tree_consolidate(struct int_node *tree,
	struct int_node *parent, unsigned char index)
{ … }

/*
 * To remove a leaf_node:
 * Search to the tree location appropriate for the given leaf_node's key:
 * - If location does not hold a matching entry, abort and do nothing.
 * - Copy the matching entry's value into the given entry.
 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
 * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
 */
static void note_tree_remove(struct notes_tree *t,
		struct int_node *tree, unsigned char n,
		struct leaf_node *entry)
{ … }

/*
 * To insert a leaf_node:
 * Search to the tree location appropriate for the given leaf_node's key:
 * - If location is unused (NULL), store the tweaked pointer directly there
 * - If location holds a note entry that matches the note-to-be-inserted, then
 *   combine the two notes (by calling the given combine_notes function).
 * - If location holds a note entry that matches the subtree-to-be-inserted,
 *   then unpack the subtree-to-be-inserted into the location.
 * - If location holds a matching subtree entry, unpack the subtree at that
 *   location, and restart the insert operation from that level.
 * - Else, create a new int_node, holding both the node-at-location and the
 *   node-to-be-inserted, and store the new int_node into the location.
 */
static int note_tree_insert(struct notes_tree *t, struct int_node *tree,
		unsigned char n, struct leaf_node *entry, unsigned char type,
		combine_notes_fn combine_notes)
{ … }

/* Free the entire notes data contained in the given tree */
static void note_tree_free(struct int_node *tree)
{ … }

static int non_note_cmp(const struct non_note *a, const struct non_note *b)
{ … }

/* note: takes ownership of path string */
static void add_non_note(struct notes_tree *t, char *path,
		unsigned int mode, const unsigned char *sha1)
{ … }

static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
		struct int_node *node, unsigned int n)
{ … }

/*
 * Determine optimal on-disk fanout for this part of the notes tree
 *
 * Given a (sub)tree and the level in the internal tree structure, determine
 * whether or not the given existing fanout should be expanded for this
 * (sub)tree.
 *
 * Values of the 'fanout' variable:
 * - 0: No fanout (all notes are stored directly in the root notes tree)
 * - 1: 2/38 fanout
 * - 2: 2/2/36 fanout
 * - 3: 2/2/2/34 fanout
 * etc.
 */
static unsigned char determine_fanout(struct int_node *tree, unsigned char n,
		unsigned char fanout)
{ … }

/* hex oid + '/' between each pair of hex digits + NUL */
#define FANOUT_PATH_MAX …

static void construct_path_with_fanout(const unsigned char *hash,
		unsigned char fanout, char *path)
{ … }

static int for_each_note_helper(struct notes_tree *t, struct int_node *tree,
		unsigned char n, unsigned char fanout, int flags,
		each_note_fn fn, void *cb_data)
{ … }

struct tree_write_stack { … };

static inline int matches_tree_write_stack(struct tree_write_stack *tws,
		const char *full_path)
{ … }

static void write_tree_entry(struct strbuf *buf, unsigned int mode,
		const char *path, unsigned int path_len, const
		unsigned char *hash)
{ … }

static void tree_write_stack_init_subtree(struct tree_write_stack *tws,
		const char *path)
{ … }

static int tree_write_stack_finish_subtree(struct tree_write_stack *tws)
{ … }

static int write_each_note_helper(struct tree_write_stack *tws,
		const char *path, unsigned int mode,
		const struct object_id *oid)
{ … }

struct write_each_note_data { … };

static int write_each_non_note_until(const char *note_path,
		struct write_each_note_data *d)
{ … }

static int write_each_note(const struct object_id *object_oid UNUSED,
		const struct object_id *note_oid, char *note_path,
		void *cb_data)
{ … }

struct note_delete_list { … };

static int prune_notes_helper(const struct object_id *object_oid,
			      const struct object_id *note_oid UNUSED,
			      char *note_path UNUSED,
			      void *cb_data)
{ … }

int combine_notes_concatenate(struct object_id *cur_oid,
			      const struct object_id *new_oid)
{ … }

int combine_notes_overwrite(struct object_id *cur_oid,
			    const struct object_id *new_oid)
{ … }

int combine_notes_ignore(struct object_id *cur_oid UNUSED,
			 const struct object_id *new_oid UNUSED)
{ … }

/*
 * Add the lines from the named object to list, with trailing
 * newlines removed.
 */
static int string_list_add_note_lines(struct string_list *list,
				      const struct object_id *oid)
{ … }

static int string_list_join_lines_helper(struct string_list_item *item,
					 void *cb_data)
{ … }

int combine_notes_cat_sort_uniq(struct object_id *cur_oid,
				const struct object_id *new_oid)
{ … }

static int string_list_add_one_ref(const char *refname, const char *referent UNUSED,
				   const struct object_id *oid UNUSED,
				   int flag UNUSED, void *cb)
{ … }

/*
 * The list argument must have strdup_strings set on it.
 */
void string_list_add_refs_by_glob(struct string_list *list, const char *glob)
{ … }

void string_list_add_refs_from_colon_sep(struct string_list *list,
					 const char *globs)
{ … }

static int notes_display_config(const char *k, const char *v,
				const struct config_context *ctx UNUSED,
				void *cb)
{ … }

char *default_notes_ref(struct repository *repo)
{ … }

void init_notes(struct notes_tree *t, const char *notes_ref,
		combine_notes_fn combine_notes, int flags)
{ … }

struct notes_tree **load_notes_trees(struct string_list *refs, int flags)
{ … }

void init_display_notes(struct display_notes_opt *opt)
{ … }

void release_display_notes(struct display_notes_opt *opt)
{ … }

void enable_default_display_notes(struct display_notes_opt *opt, int *show_notes)
{ … }

void enable_ref_display_notes(struct display_notes_opt *opt, int *show_notes,
		const char *ref) { … }

void disable_display_notes(struct display_notes_opt *opt, int *show_notes)
{ … }

void load_display_notes(struct display_notes_opt *opt)
{ … }

int add_note(struct notes_tree *t, const struct object_id *object_oid,
		const struct object_id *note_oid, combine_notes_fn combine_notes)
{ … }

int remove_note(struct notes_tree *t, const unsigned char *object_sha1)
{ … }

const struct object_id *get_note(struct notes_tree *t,
		const struct object_id *oid)
{ … }

int for_each_note(struct notes_tree *t, int flags, each_note_fn fn,
		void *cb_data)
{ … }

int write_notes_tree(struct notes_tree *t, struct object_id *result)
{ … }

void prune_notes(struct notes_tree *t, int flags)
{ … }

void free_notes(struct notes_tree *t)
{ … }

/*
 * Fill the given strbuf with the notes associated with the given object.
 *
 * If the given notes_tree structure is not initialized, it will be auto-
 * initialized to the default value (see documentation for init_notes() above).
 * If the given notes_tree is NULL, the internal/default notes_tree will be
 * used instead.
 *
 * (raw != 0) gives the %N userformat; otherwise, the note message is given
 * for human consumption.
 */
static void format_note(struct notes_tree *t, const struct object_id *object_oid,
			struct strbuf *sb, const char *output_encoding, int raw)
{ … }

void format_display_notes(const struct object_id *object_oid,
			  struct strbuf *sb, const char *output_encoding, int raw)
{ … }

int copy_note(struct notes_tree *t,
	      const struct object_id *from_obj, const struct object_id *to_obj,
	      int force, combine_notes_fn combine_notes)
{ … }

void expand_notes_ref(struct strbuf *sb)
{ … }

void expand_loose_notes_ref(struct strbuf *sb)
{ … }