Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 1 | #ifndef TREE_WALK_H |
| 2 | #define TREE_WALK_H |
| 3 | |
brian m. carlson | ea82b2a | 2019-01-15 00:39:44 +0000 | [diff] [blame] | 4 | #include "cache.h" |
Elijah Newren | ef3ca95 | 2018-08-15 10:54:05 -0700 | [diff] [blame] | 5 | |
Jeff King | 5290d45 | 2020-02-01 06:39:22 -0500 | [diff] [blame] | 6 | #define MAX_TRAVERSE_TREES 8 |
| 7 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 8 | /** |
| 9 | * The tree walking API is used to traverse and inspect trees. |
| 10 | */ |
| 11 | |
| 12 | /** |
| 13 | * An entry in a tree. Each entry has a sha1 identifier, pathname, and mode. |
| 14 | */ |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 15 | struct name_entry { |
brian m. carlson | ea82b2a | 2019-01-15 00:39:44 +0000 | [diff] [blame] | 16 | struct object_id oid; |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 17 | const char *path; |
brian m. carlson | ea82b2a | 2019-01-15 00:39:44 +0000 | [diff] [blame] | 18 | int pathlen; |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 19 | unsigned int mode; |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 20 | }; |
| 21 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 22 | /** |
| 23 | * A semi-opaque data structure used to maintain the current state of the walk. |
| 24 | */ |
Linus Torvalds | 4651ece | 2007-03-21 10:09:56 -0700 | [diff] [blame] | 25 | struct tree_desc { |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 26 | /* |
| 27 | * pointer into the memory representation of the tree. It always |
| 28 | * points at the current entry being visited. |
| 29 | */ |
Linus Torvalds | 4651ece | 2007-03-21 10:09:56 -0700 | [diff] [blame] | 30 | const void *buffer; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 31 | |
| 32 | /* points to the current entry being visited. */ |
Linus Torvalds | 4651ece | 2007-03-21 10:09:56 -0700 | [diff] [blame] | 33 | struct name_entry entry; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 34 | |
| 35 | /* counts the number of bytes left in the `buffer`. */ |
Linus Torvalds | 4651ece | 2007-03-21 10:09:56 -0700 | [diff] [blame] | 36 | unsigned int size; |
| 37 | }; |
| 38 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 39 | /** |
| 40 | * Decode the entry currently being visited (the one pointed to by |
| 41 | * `tree_desc's` `entry` member) and return the sha1 of the entry. The |
| 42 | * `pathp` and `modep` arguments are set to the entry's pathname and mode |
| 43 | * respectively. |
| 44 | */ |
Elijah Newren | 5ec1e72 | 2019-04-05 08:00:12 -0700 | [diff] [blame] | 45 | static inline const struct object_id *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned short *modep) |
Linus Torvalds | 4651ece | 2007-03-21 10:09:56 -0700 | [diff] [blame] | 46 | { |
| 47 | *pathp = desc->entry.path; |
Kirill Smelkov | 7146e66 | 2014-02-06 15:36:31 +0400 | [diff] [blame] | 48 | *modep = desc->entry.mode; |
brian m. carlson | ea82b2a | 2019-01-15 00:39:44 +0000 | [diff] [blame] | 49 | return &desc->entry.oid; |
Linus Torvalds | 4651ece | 2007-03-21 10:09:56 -0700 | [diff] [blame] | 50 | } |
| 51 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 52 | /** |
| 53 | * Calculate the length of a tree entry's pathname. This utilizes the |
| 54 | * memory structure of a tree entry to avoid the overhead of using a |
| 55 | * generic strlen(). |
| 56 | */ |
Nguyễn Thái Ngọc Duy | 0de1633 | 2011-10-24 17:36:09 +1100 | [diff] [blame] | 57 | static inline int tree_entry_len(const struct name_entry *ne) |
Linus Torvalds | 304de2d | 2007-03-17 20:06:24 -0700 | [diff] [blame] | 58 | { |
brian m. carlson | ea82b2a | 2019-01-15 00:39:44 +0000 | [diff] [blame] | 59 | return ne->pathlen; |
Linus Torvalds | 304de2d | 2007-03-17 20:06:24 -0700 | [diff] [blame] | 60 | } |
| 61 | |
David Turner | 8354fa3 | 2016-09-27 16:59:51 -0400 | [diff] [blame] | 62 | /* |
| 63 | * The _gently versions of these functions warn and return false on a |
| 64 | * corrupt tree entry rather than dying, |
| 65 | */ |
| 66 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 67 | /** |
| 68 | * Walk to the next entry in a tree. This is commonly used in conjunction |
| 69 | * with `tree_entry_extract` to inspect the current entry. |
| 70 | */ |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 71 | void update_tree_entry(struct tree_desc *); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 72 | |
David Turner | 8354fa3 | 2016-09-27 16:59:51 -0400 | [diff] [blame] | 73 | int update_tree_entry_gently(struct tree_desc *); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 74 | |
| 75 | /** |
| 76 | * Initialize a `tree_desc` and decode its first entry. The buffer and |
| 77 | * size parameters are assumed to be the same as the buffer and size |
| 78 | * members of `struct tree`. |
| 79 | */ |
Linus Torvalds | 6fda5e5 | 2007-03-21 10:08:25 -0700 | [diff] [blame] | 80 | void init_tree_desc(struct tree_desc *desc, const void *buf, unsigned long size); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 81 | |
David Turner | 8354fa3 | 2016-09-27 16:59:51 -0400 | [diff] [blame] | 82 | int init_tree_desc_gently(struct tree_desc *desc, const void *buf, unsigned long size); |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 83 | |
Elijah Newren | 2244eab | 2010-08-24 20:53:11 -0600 | [diff] [blame] | 84 | /* |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 85 | * Visit the next entry in a tree. Returns 1 when there are more entries |
| 86 | * left to visit and 0 when all entries have been visited. This is |
| 87 | * commonly used in the test of a while loop. |
Elijah Newren | 2244eab | 2010-08-24 20:53:11 -0600 | [diff] [blame] | 88 | */ |
Linus Torvalds | 4c068a9 | 2006-05-30 09:45:45 -0700 | [diff] [blame] | 89 | int tree_entry(struct tree_desc *, struct name_entry *); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 90 | |
David Turner | 8354fa3 | 2016-09-27 16:59:51 -0400 | [diff] [blame] | 91 | int tree_entry_gently(struct tree_desc *, struct name_entry *); |
Linus Torvalds | 4c068a9 | 2006-05-30 09:45:45 -0700 | [diff] [blame] | 92 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 93 | /** |
| 94 | * Initialize a `tree_desc` and decode its first entry given the |
| 95 | * object ID of a tree. Returns the `buffer` member if the latter |
| 96 | * is a valid tree identifier and NULL otherwise. |
| 97 | */ |
Nguyễn Thái Ngọc Duy | 5e57580 | 2019-06-27 16:28:48 +0700 | [diff] [blame] | 98 | void *fill_tree_descriptor(struct repository *r, |
| 99 | struct tree_desc *desc, |
| 100 | const struct object_id *oid); |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 101 | |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 102 | struct traverse_info; |
Linus Torvalds | 91e4f03 | 2008-03-05 20:06:18 -0800 | [diff] [blame] | 103 | typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 104 | |
| 105 | /** |
| 106 | * Traverse `n` number of trees in parallel. The `fn` callback member of |
| 107 | * `traverse_info` is called once for each tree entry. |
| 108 | */ |
Nguyễn Thái Ngọc Duy | 67022e0 | 2018-11-18 17:47:57 +0100 | [diff] [blame] | 109 | int traverse_trees(struct index_state *istate, int n, struct tree_desc *t, struct traverse_info *info); |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 110 | |
Nguyễn Thái Ngọc Duy | 0dd1f0c | 2019-06-27 16:28:50 +0700 | [diff] [blame] | 111 | 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); |
David Turner | 275721c | 2015-05-20 13:03:38 -0400 | [diff] [blame] | 112 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 113 | /** |
| 114 | * A structure used to maintain the state of a traversal. |
| 115 | */ |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 116 | struct traverse_info { |
David Turner | d9c2bd5 | 2015-12-21 17:34:20 -0500 | [diff] [blame] | 117 | const char *traverse_path; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 118 | |
| 119 | /* |
| 120 | * points to the traverse_info which was used to descend into the |
| 121 | * current tree. If this is the top-level tree `prev` will point to |
| 122 | * a dummy traverse_info. |
| 123 | */ |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 124 | struct traverse_info *prev; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 125 | |
| 126 | /* is the entry for the current tree (if the tree is a subtree). */ |
Jeff King | 9055384 | 2019-07-31 00:38:15 -0400 | [diff] [blame] | 127 | const char *name; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 128 | |
Jeff King | 9055384 | 2019-07-31 00:38:15 -0400 | [diff] [blame] | 129 | size_t namelen; |
| 130 | unsigned mode; |
| 131 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 132 | /* is the length of the full path for the current tree. */ |
Jeff King | 3780608 | 2019-07-31 00:38:18 -0400 | [diff] [blame] | 133 | size_t pathlen; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 134 | |
Junio C Hamano | 2842c0f | 2011-08-29 12:26:05 -0700 | [diff] [blame] | 135 | struct pathspec *pathspec; |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 136 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 137 | /* can be used by callbacks to maintain directory-file conflicts. */ |
René Scharfe | 603d249 | 2013-06-16 01:44:43 +0200 | [diff] [blame] | 138 | unsigned long df_conflicts; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 139 | |
| 140 | /* a callback called for each entry in the tree. |
| 141 | * |
| 142 | * The arguments passed to the traverse callback are as follows: |
| 143 | * |
| 144 | * - `n` counts the number of trees being traversed. |
| 145 | * |
| 146 | * - `mask` has its nth bit set if something exists in the nth entry. |
| 147 | * |
| 148 | * - `dirmask` has its nth bit set if the nth tree's entry is a directory. |
| 149 | * |
| 150 | * - `entry` is an array of size `n` where the nth entry is from the nth tree. |
| 151 | * |
| 152 | * - `info` maintains the state of the traversal. |
| 153 | * |
| 154 | * Returning a negative value will terminate the traversal. Otherwise the |
| 155 | * return value is treated as an update mask. If the nth bit is set the nth tree |
| 156 | * will be updated and if the bit is not set the nth tree entry will be the |
| 157 | * same in the next callback invocation. |
| 158 | */ |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 159 | traverse_callback_t fn; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 160 | |
| 161 | /* can be anything the `fn` callback would want to use. */ |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 162 | void *data; |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 163 | |
| 164 | /* tells whether to stop at the first error or not. */ |
Matthieu Moy | e6c111b | 2010-08-11 10:38:07 +0200 | [diff] [blame] | 165 | int show_all_errors; |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 166 | }; |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 167 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 168 | /** |
| 169 | * Find an entry in a tree given a pathname and the sha1 of a tree to |
| 170 | * search. Returns 0 if the entry is found and -1 otherwise. The third |
| 171 | * and fourth parameters are set to the entry's sha1 and mode respectively. |
| 172 | */ |
Nguyễn Thái Ngọc Duy | 50ddb08 | 2019-06-27 16:28:49 +0700 | [diff] [blame] | 173 | int get_tree_entry(struct repository *, const struct object_id *, const char *, struct object_id *, unsigned short *); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 174 | |
| 175 | /** |
| 176 | * Generate the full pathname of a tree entry based from the root of the |
| 177 | * traversal. For example, if the traversal has recursed into another |
| 178 | * tree named "bar" the pathname of an entry "baz" in the "bar" |
| 179 | * tree would be "bar/baz". |
| 180 | */ |
Jeff King | 5aa02f9 | 2019-07-31 00:38:25 -0400 | [diff] [blame] | 181 | char *make_traverse_path(char *path, size_t pathlen, const struct traverse_info *info, |
Jeff King | 9055384 | 2019-07-31 00:38:15 -0400 | [diff] [blame] | 182 | const char *name, size_t namelen); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 183 | |
| 184 | /** |
| 185 | * Convenience wrapper to `make_traverse_path` into a strbuf. |
| 186 | */ |
Jeff King | c43ab06 | 2019-07-31 00:38:23 -0400 | [diff] [blame] | 187 | void strbuf_make_traverse_path(struct strbuf *out, |
| 188 | const struct traverse_info *info, |
| 189 | const char *name, size_t namelen); |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 190 | |
| 191 | /** |
| 192 | * Initialize a `traverse_info` given the pathname of the tree to start |
| 193 | * traversing from. |
| 194 | */ |
Denton Liu | 5545442 | 2019-04-29 04:28:14 -0400 | [diff] [blame] | 195 | void setup_traverse_info(struct traverse_info *info, const char *base); |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 196 | |
Heba Waly | bbcfa30 | 2019-11-17 21:04:57 +0000 | [diff] [blame] | 197 | /** |
| 198 | * Calculate the length of a pathname returned by `make_traverse_path`. |
| 199 | * This utilizes the memory structure of a tree entry to avoid the |
| 200 | * overhead of using a generic strlen(). |
| 201 | */ |
Jeff King | b3b3cbc | 2019-07-31 00:38:20 -0400 | [diff] [blame] | 202 | static inline size_t traverse_path_len(const struct traverse_info *info, |
| 203 | size_t namelen) |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 204 | { |
Jeff King | b3b3cbc | 2019-07-31 00:38:20 -0400 | [diff] [blame] | 205 | return st_add(info->pathlen, namelen); |
Linus Torvalds | 40d934d | 2008-03-05 18:59:29 -0800 | [diff] [blame] | 206 | } |
Junio C Hamano | 4dcff63 | 2006-04-19 14:05:47 -0700 | [diff] [blame] | 207 | |
Nguyễn Thái Ngọc Duy | d688cf0 | 2011-10-24 17:36:10 +1100 | [diff] [blame] | 208 | /* in general, positive means "kind of interesting" */ |
| 209 | enum interesting { |
| 210 | all_entries_not_interesting = -1, /* no, and no subsequent entries will be either */ |
| 211 | entry_not_interesting = 0, |
| 212 | entry_interesting = 1, |
| 213 | all_entries_interesting = 2 /* yes, and all subsequent entries will be */ |
| 214 | }; |
| 215 | |
Nguyễn Thái Ngọc Duy | 67022e0 | 2018-11-18 17:47:57 +0100 | [diff] [blame] | 216 | enum interesting tree_entry_interesting(struct index_state *istate, |
| 217 | const struct name_entry *, |
| 218 | struct strbuf *, int, |
| 219 | const struct pathspec *ps); |
Nguyễn Thái Ngọc Duy | 2c389fc | 2010-12-15 22:02:40 +0700 | [diff] [blame] | 220 | |
Junio C Hamano | 1b0c717 | 2006-03-29 22:55:43 -0800 | [diff] [blame] | 221 | #endif |