/src/git/tree-walk.h

Source
#ifndef TREE_WALK_H
#define TREE_WALK_H

#include "hash.h"

struct index_state;
struct repository;

/**
 * The tree walking API is used to traverse and inspect trees.
 */

/**
 * An entry in a tree. Each entry has a sha1 identifier, pathname, and mode.
 */
struct name_entry {
  struct object_id oid;
  const char *path;
  int pathlen;
  unsigned int mode;
};

/**
 * A semi-opaque data structure used to maintain the current state of the walk.
 */
struct tree_desc {
  const struct git_hash_algo *algo;
  /*
   * pointer into the memory representation of the tree. It always
   * points at the current entry being visited.
   */
  const void *buffer;

  /* points to the current entry being visited. */
  struct name_entry entry;

  /* counts the number of bytes left in the `buffer`. */
  unsigned int size;

  /* option flags passed via init_tree_desc_gently() */
  enum tree_desc_flags {
    TREE_DESC_RAW_MODES = (1 << 0),
  } flags;
};

/**
 * Decode the entry currently being visited (the one pointed to by
 * `tree_desc's` `entry` member) and return the sha1 of the entry. The
 * `pathp` and `modep` arguments are set to the entry's pathname and mode
 * respectively.
 */
static inline const struct object_id *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned short *modep)
{
  *pathp = desc->entry.path;
  *modep = desc->entry.mode;
  return &desc->entry.oid;
}

/**
 * Calculate the length of a tree entry's pathname. This utilizes the
 * memory structure of a tree entry to avoid the overhead of using a
 * generic strlen().
 */
static inline int tree_entry_len(const struct name_entry *ne)
{
  return ne->pathlen;
}

/*
 * The _gently versions of these functions warn and return false on a
 * corrupt tree entry rather than dying,
 */

/**
 * Walk to the next entry in a tree. This is commonly used in conjunction
 * with `tree_entry_extract` to inspect the current entry.
 */
void update_tree_entry(struct tree_desc *);

int update_tree_entry_gently(struct tree_desc *);

/**
 * Initialize a `tree_desc` and decode its first entry. The buffer and
 * size parameters are assumed to be the same as the buffer and size
 * members of `struct tree`.
 */
void init_tree_desc(struct tree_desc *desc, const struct object_id *tree_oid,
        const void *buf, unsigned long size);

int init_tree_desc_gently(struct tree_desc *desc, const struct object_id *oid,
        const void *buf, unsigned long size,
        enum tree_desc_flags flags);

/*
 * Visit the next entry in a tree. Returns 1 when there are more entries
 * left to visit and 0 when all entries have been visited. This is
 * commonly used in the test of a while loop.
 */
int tree_entry(struct tree_desc *, struct name_entry *);

int tree_entry_gently(struct tree_desc *, struct name_entry *);

/**
 * Initialize a `tree_desc` and decode its first entry given the
 * object ID of a tree. Returns the `buffer` member if the latter
 * is a valid tree identifier and NULL otherwise.
 */
void *fill_tree_descriptor(struct repository *r,
         struct tree_desc *desc,
         const struct object_id *oid);

struct traverse_info;
typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *);

/**
 * Traverse `n` number of trees in parallel. The `fn` callback member of
 * `traverse_info` is called once for each tree entry.
 */
int traverse_trees(struct index_state *istate, int n, struct tree_desc *t, struct traverse_info *info);

enum get_oid_result get_tree_entry_follow_symlinks(struct repository *r, struct object_id *tree_oid, const char *name, struct object_id *result, struct strbuf *result_path, unsigned short *mode);

/**
 * A structure used to maintain the state of a traversal.
 */
struct traverse_info {
  const char *traverse_path;

  /*
   * points to the traverse_info which was used to descend into the
   * current tree. If this is the top-level tree `prev` will point to
   * a dummy traverse_info.
   */
  struct traverse_info *prev;

  /* is the entry for the current tree (if the tree is a subtree). */
  const char *name;

  size_t namelen;
  unsigned mode;

  /* is the length of the full path for the current tree. */
  size_t pathlen;

  struct pathspec *pathspec;

  /* can be used by callbacks to maintain directory-file conflicts. */
  unsigned long df_conflicts;

  /* a callback called for each entry in the tree.
   *
   * The arguments passed to the traverse callback are as follows:
   *
   * - `n` counts the number of trees being traversed.
   *
   * - `mask` has its nth bit set if something exists in the nth entry.
   *
   * - `dirmask` has its nth bit set if the nth tree's entry is a directory.
   *
   * - `entry` is an array of size `n` where the nth entry is from the nth tree.
   *
   * - `info` maintains the state of the traversal.
   *
   * Returning a negative value will terminate the traversal. Otherwise the
   * return value is treated as an update mask. If the nth bit is set the nth tree
   * will be updated and if the bit is not set the nth tree entry will be the
   * same in the next callback invocation.
   */
  traverse_callback_t fn;

  /* can be anything the `fn` callback would want to use. */
  void *data;

  /* tells whether to stop at the first error or not. */
  int show_all_errors;
};

/**
 * Walk trees starting with "tree_oid" to find the entry for "name", and
 * return the the object name and the mode of the found entry via the
 * "oid" and "mode" parameters.  Return 0 if the entry is found, and -1
 * otherwise.
 */
int get_tree_entry(struct repository *repo, const struct object_id *tree_oid,
       const char *name, struct object_id *oid,
       unsigned short *mode);

/**
 * Generate the full pathname of a tree entry based from the root of the
 * traversal. For example, if the traversal has recursed into another
 * tree named "bar" the pathname of an entry "baz" in the "bar"
 * tree would be "bar/baz".
 */
char *make_traverse_path(char *path, size_t pathlen, const struct traverse_info *info,
       const char *name, size_t namelen);

/**
 * Convenience wrapper to `make_traverse_path` into a strbuf.
 */
void strbuf_make_traverse_path(struct strbuf *out,
             const struct traverse_info *info,
             const char *name, size_t namelen);

/**
 * Initialize a `traverse_info` given the pathname of the tree to start
 * traversing from.
 */
void setup_traverse_info(struct traverse_info *info, const char *base);

/**
 * Calculate the length of a pathname returned by `make_traverse_path`.
 * This utilizes the memory structure of a tree entry to avoid the
 * overhead of using a generic strlen().
 */
static inline size_t traverse_path_len(const struct traverse_info *info,
               size_t namelen)
{
  return st_add(info->pathlen, namelen);
}

/* in general, positive means "kind of interesting" */
enum interesting {
  all_entries_not_interesting = -1, /* no, and no subsequent entries will be either */
  entry_not_interesting = 0,
  entry_interesting = 1,
  all_entries_interesting = 2 /* yes, and all subsequent entries will be */
};

enum interesting tree_entry_interesting(struct index_state *istate,
          const struct name_entry *,
          struct strbuf *,
          const struct pathspec *ps);

#endif

Coverage Report

Created: 2026-01-10 06:18

Line	Count	Source
1		#ifndef TREE_WALK_H
2		#define TREE_WALK_H
3
4		#include "hash.h"
5
6		struct index_state;
7		struct repository;
8
9		/**
10		* The tree walking API is used to traverse and inspect trees.
11		*/
12
13		/**
14		* An entry in a tree. Each entry has a sha1 identifier, pathname, and mode.
15		*/
16		struct name_entry {
17		struct object_id oid;
18		const char *path;
19		int pathlen;
20		unsigned int mode;
21		};
22
23		/**
24		* A semi-opaque data structure used to maintain the current state of the walk.
25		*/
26		struct tree_desc {
27		const struct git_hash_algo *algo;
28		/*
29		* pointer into the memory representation of the tree. It always
30		* points at the current entry being visited.
31		*/
32		const void *buffer;
33
34		/* points to the current entry being visited. */
35		struct name_entry entry;
36
37		/* counts the number of bytes left in the `buffer`. */
38		unsigned int size;
39
40		/* option flags passed via init_tree_desc_gently() */
41		enum tree_desc_flags {
42		TREE_DESC_RAW_MODES = (1 << 0),
43		} flags;
44		};
45
46		/**
47		* Decode the entry currently being visited (the one pointed to by
48		* `tree_desc's` `entry` member) and return the sha1 of the entry. The
49		* `pathp` and `modep` arguments are set to the entry's pathname and mode
50		* respectively.
51		*/
52		static inline const struct object_id tree_entry_extract(struct tree_desc desc, const char *pathp, unsigned short modep)
53	0	{
54	0	*pathp = desc->entry.path;
55	0	*modep = desc->entry.mode;
56	0	return &desc->entry.oid;
57	0	} Unexecuted instantiation: dir.c:tree_entry_extract Unexecuted instantiation: object-name.c:tree_entry_extract Unexecuted instantiation: packfile.c:tree_entry_extract Unexecuted instantiation: path.c:tree_entry_extract Unexecuted instantiation: read-cache.c:tree_entry_extract Unexecuted instantiation: repository.c:tree_entry_extract Unexecuted instantiation: revision.c:tree_entry_extract Unexecuted instantiation: sparse-index.c:tree_entry_extract Unexecuted instantiation: submodule-config.c:tree_entry_extract Unexecuted instantiation: submodule.c:tree_entry_extract Unexecuted instantiation: tree-diff.c:tree_entry_extract Unexecuted instantiation: tree-walk.c:tree_entry_extract Unexecuted instantiation: tree.c:tree_entry_extract Unexecuted instantiation: attr.c:tree_entry_extract Unexecuted instantiation: bloom.c:tree_entry_extract Unexecuted instantiation: branch.c:tree_entry_extract Unexecuted instantiation: cache-tree.c:tree_entry_extract Unexecuted instantiation: diff-lib.c:tree_entry_extract Unexecuted instantiation: fsck.c:tree_entry_extract Unexecuted instantiation: line-log.c:tree_entry_extract Unexecuted instantiation: list-objects.c:tree_entry_extract Unexecuted instantiation: merge-ort.c:tree_entry_extract Unexecuted instantiation: notes.c:tree_entry_extract Unexecuted instantiation: sequencer.c:tree_entry_extract Unexecuted instantiation: unpack-trees.c:tree_entry_extract Unexecuted instantiation: match-trees.c:tree_entry_extract Unexecuted instantiation: merge.c:tree_entry_extract Unexecuted instantiation: reset.c:tree_entry_extract
58
59		/**
60		* Calculate the length of a tree entry's pathname. This utilizes the
61		* memory structure of a tree entry to avoid the overhead of using a
62		* generic strlen().
63		*/
64		static inline int tree_entry_len(const struct name_entry *ne)
65	0	{
66	0	return ne->pathlen;
67	0	} Unexecuted instantiation: dir.c:tree_entry_len Unexecuted instantiation: object-name.c:tree_entry_len Unexecuted instantiation: packfile.c:tree_entry_len Unexecuted instantiation: path.c:tree_entry_len Unexecuted instantiation: read-cache.c:tree_entry_len Unexecuted instantiation: repository.c:tree_entry_len Unexecuted instantiation: revision.c:tree_entry_len Unexecuted instantiation: sparse-index.c:tree_entry_len Unexecuted instantiation: submodule-config.c:tree_entry_len Unexecuted instantiation: submodule.c:tree_entry_len Unexecuted instantiation: tree-diff.c:tree_entry_len Unexecuted instantiation: tree-walk.c:tree_entry_len Unexecuted instantiation: tree.c:tree_entry_len Unexecuted instantiation: attr.c:tree_entry_len Unexecuted instantiation: bloom.c:tree_entry_len Unexecuted instantiation: branch.c:tree_entry_len Unexecuted instantiation: cache-tree.c:tree_entry_len Unexecuted instantiation: diff-lib.c:tree_entry_len Unexecuted instantiation: fsck.c:tree_entry_len Unexecuted instantiation: line-log.c:tree_entry_len Unexecuted instantiation: list-objects.c:tree_entry_len Unexecuted instantiation: merge-ort.c:tree_entry_len Unexecuted instantiation: notes.c:tree_entry_len Unexecuted instantiation: sequencer.c:tree_entry_len Unexecuted instantiation: unpack-trees.c:tree_entry_len Unexecuted instantiation: match-trees.c:tree_entry_len Unexecuted instantiation: merge.c:tree_entry_len Unexecuted instantiation: reset.c:tree_entry_len
68
69		/*
70		* The _gently versions of these functions warn and return false on a
71		* corrupt tree entry rather than dying,
72		*/
73
74		/**
75		* Walk to the next entry in a tree. This is commonly used in conjunction
76		* with `tree_entry_extract` to inspect the current entry.
77		*/
78		void update_tree_entry(struct tree_desc *);
79
80		int update_tree_entry_gently(struct tree_desc *);
81
82		/**
83		* Initialize a `tree_desc` and decode its first entry. The buffer and
84		* size parameters are assumed to be the same as the buffer and size
85		* members of `struct tree`.
86		*/
87		void init_tree_desc(struct tree_desc desc, const struct object_id tree_oid,
88		const void *buf, unsigned long size);
89
90		int init_tree_desc_gently(struct tree_desc desc, const struct object_id oid,
91		const void *buf, unsigned long size,
92		enum tree_desc_flags flags);
93
94		/*
95		* Visit the next entry in a tree. Returns 1 when there are more entries
96		* left to visit and 0 when all entries have been visited. This is
97		* commonly used in the test of a while loop.
98		*/
99		int tree_entry(struct tree_desc , struct name_entry );
100
101		int tree_entry_gently(struct tree_desc , struct name_entry );
102
103		/**
104		* Initialize a `tree_desc` and decode its first entry given the
105		* object ID of a tree. Returns the `buffer` member if the latter
106		* is a valid tree identifier and NULL otherwise.
107		*/
108		void fill_tree_descriptor(struct repository r,
109		struct tree_desc *desc,
110		const struct object_id *oid);
111
112		struct traverse_info;
113		typedef int (traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry entry, struct traverse_info *);
114
115		/**
116		* Traverse `n` number of trees in parallel. The `fn` callback member of
117		* `traverse_info` is called once for each tree entry.
118		*/
119		int traverse_trees(struct index_state istate, int n, struct tree_desc t, struct traverse_info *info);
120
121		enum get_oid_result get_tree_entry_follow_symlinks(struct repository r, struct object_id tree_oid, const char name, struct object_id result, struct strbuf result_path, unsigned short mode);
122
123		/**
124		* A structure used to maintain the state of a traversal.
125		*/
126		struct traverse_info {
127		const char *traverse_path;
128
129		/*
130		* points to the traverse_info which was used to descend into the
131		* current tree. If this is the top-level tree `prev` will point to
132		* a dummy traverse_info.
133		*/
134		struct traverse_info *prev;
135
136		/* is the entry for the current tree (if the tree is a subtree). */
137		const char *name;
138
139		size_t namelen;
140		unsigned mode;
141
142		/* is the length of the full path for the current tree. */
143		size_t pathlen;
144
145		struct pathspec *pathspec;
146
147		/* can be used by callbacks to maintain directory-file conflicts. */
148		unsigned long df_conflicts;
149
150		/* a callback called for each entry in the tree.
151		*
152		* The arguments passed to the traverse callback are as follows:
153		*
154		* - `n` counts the number of trees being traversed.
155		*
156		* - `mask` has its nth bit set if something exists in the nth entry.
157		*
158		* - `dirmask` has its nth bit set if the nth tree's entry is a directory.
159		*
160		* - `entry` is an array of size `n` where the nth entry is from the nth tree.
161		*
162		* - `info` maintains the state of the traversal.
163		*
164		* Returning a negative value will terminate the traversal. Otherwise the
165		* return value is treated as an update mask. If the nth bit is set the nth tree
166		* will be updated and if the bit is not set the nth tree entry will be the
167		* same in the next callback invocation.
168		*/
169		traverse_callback_t fn;
170
171		/* can be anything the `fn` callback would want to use. */
172		void *data;
173
174		/* tells whether to stop at the first error or not. */
175		int show_all_errors;
176		};
177
178		/**
179		* Walk trees starting with "tree_oid" to find the entry for "name", and
180		* return the the object name and the mode of the found entry via the
181		* "oid" and "mode" parameters. Return 0 if the entry is found, and -1
182		* otherwise.
183		*/
184		int get_tree_entry(struct repository repo, const struct object_id tree_oid,
185		const char name, struct object_id oid,
186		unsigned short *mode);
187
188		/**
189		* Generate the full pathname of a tree entry based from the root of the
190		* traversal. For example, if the traversal has recursed into another
191		* tree named "bar" the pathname of an entry "baz" in the "bar"
192		* tree would be "bar/baz".
193		*/
194		char make_traverse_path(char path, size_t pathlen, const struct traverse_info *info,
195		const char *name, size_t namelen);
196
197		/**
198		* Convenience wrapper to `make_traverse_path` into a strbuf.
199		*/
200		void strbuf_make_traverse_path(struct strbuf *out,
201		const struct traverse_info *info,
202		const char *name, size_t namelen);
203
204		/**
205		* Initialize a `traverse_info` given the pathname of the tree to start
206		* traversing from.
207		*/
208		void setup_traverse_info(struct traverse_info info, const char base);
209
210		/**
211		* Calculate the length of a pathname returned by `make_traverse_path`.
212		* This utilizes the memory structure of a tree entry to avoid the
213		* overhead of using a generic strlen().
214		*/
215		static inline size_t traverse_path_len(const struct traverse_info *info,
216		size_t namelen)
217	0	{
218	0	return st_add(info->pathlen, namelen);
219	0	} Unexecuted instantiation: dir.c:traverse_path_len Unexecuted instantiation: object-name.c:traverse_path_len Unexecuted instantiation: packfile.c:traverse_path_len Unexecuted instantiation: path.c:traverse_path_len Unexecuted instantiation: read-cache.c:traverse_path_len Unexecuted instantiation: repository.c:traverse_path_len Unexecuted instantiation: revision.c:traverse_path_len Unexecuted instantiation: sparse-index.c:traverse_path_len Unexecuted instantiation: submodule-config.c:traverse_path_len Unexecuted instantiation: submodule.c:traverse_path_len Unexecuted instantiation: tree-diff.c:traverse_path_len Unexecuted instantiation: tree-walk.c:traverse_path_len Unexecuted instantiation: tree.c:traverse_path_len Unexecuted instantiation: attr.c:traverse_path_len Unexecuted instantiation: bloom.c:traverse_path_len Unexecuted instantiation: branch.c:traverse_path_len Unexecuted instantiation: cache-tree.c:traverse_path_len Unexecuted instantiation: diff-lib.c:traverse_path_len Unexecuted instantiation: fsck.c:traverse_path_len Unexecuted instantiation: line-log.c:traverse_path_len Unexecuted instantiation: list-objects.c:traverse_path_len Unexecuted instantiation: merge-ort.c:traverse_path_len Unexecuted instantiation: notes.c:traverse_path_len Unexecuted instantiation: sequencer.c:traverse_path_len Unexecuted instantiation: unpack-trees.c:traverse_path_len Unexecuted instantiation: match-trees.c:traverse_path_len Unexecuted instantiation: merge.c:traverse_path_len Unexecuted instantiation: reset.c:traverse_path_len
220
221		/* in general, positive means "kind of interesting" */
222		enum interesting {
223		all_entries_not_interesting = -1, /* no, and no subsequent entries will be either */
224		entry_not_interesting = 0,
225		entry_interesting = 1,
226		all_entries_interesting = 2 /* yes, and all subsequent entries will be */
227		};
228
229		enum interesting tree_entry_interesting(struct index_state *istate,
230		const struct name_entry *,
231		struct strbuf *,
232		const struct pathspec *ps);
233
234		#endif