path: root/tree-walk.h
AgeCommit message (Collapse)Author
2020-02-04tree-walk.c: break circular dependency with unpack-treesJeff King
The unpack-trees API depends on the tree-walk API. But we've recently introduced a dependency in tree-walk.c on MAX_UNPACK_TREES, which doesn't otherwise care about unpack-trees at all. Let's break that dependency by reversing the constants: we'll introduce a new MAX_TRAVERSE_TREES which belongs to the tree-walk API. And then we can define MAX_UNPACK_TREES in terms of that (since unpack-trees cannot possibly work with more trees than it can traverse at once via tree-walk). The value for both will remain at 8. This is somewhat arbitrary and probably more than is necessary, per ca885a4fe6 (read-tree() and unpack_trees(): use consistent limit, 2008-03-13), but there's not really any pressing need to reduce it. Suggested-by: Elijah Newren <> Signed-off-by: Jeff King <> Acked-by: Elijah Newren <> Signed-off-by: Junio C Hamano <>
2019-11-18tree-walk: move doc to tree-walk.hHeba Waly
Move the documentation from Documentation/technical/api-tree-walking.txt to tree-walk.h as it's easier for the developers to find the usage information beside the code instead of looking for it in another doc file. Documentation/technical/api-tree-walking.txt is removed because the information it has is now redundant and it'll be hard to keep it up to date and synchronized with the documentation in the header file. Signed-off-by: Heba Waly <> Signed-off-by: Junio C Hamano <>
2019-08-22Merge branch 'jk/tree-walk-overflow'Junio C Hamano
Codepaths to walk tree objects have been audited for integer overflows and hardened. * jk/tree-walk-overflow: tree-walk: harden make_traverse_path() length computations tree-walk: add a strbuf wrapper for make_traverse_path() tree-walk: accept a raw length for traverse_path_len() tree-walk: use size_t consistently tree-walk: drop oid from traverse_info setup_traverse_info(): stop copying oid
2019-08-01tree-walk: harden make_traverse_path() length computationsJeff King
The make_traverse_path() function isn't very careful about checking its output buffer boundaries. In fact, it doesn't even _know_ the size of the buffer it's writing to, and just assumes that the caller used traverse_path_len() correctly. And even then we assume that our traverse_info.pathlen components are all correct, and just blindly write into the buffer. Let's improve this situation a bit: - have the caller pass in their allocated buffer length, which we'll check against our own computations - check for integer underflow as we do our backwards-insertion of pathnames into the buffer - check that we do not run out items in our list to traverse before we've filled the expected number of bytes None of these should be triggerable in practice (especially since our switch to size_t everywhere in a previous commit), but it doesn't hurt to check our assumptions. Signed-off-by: Jeff King <> Signed-off-by: Junio C Hamano <>
2019-08-01tree-walk: add a strbuf wrapper for make_traverse_path()Jeff King
All but one of the callers of make_traverse_path() allocate a new heap buffer to store the path. Let's give them an easy way to write to a strbuf, which saves them from computing the length themselves (which is especially tricky when they want to add to the path). It will also make it easier for us to change the make_traverse_path() interface in a future patch to improve its bounds-checking. Signed-off-by: Jeff King <> Signed-off-by: Junio C Hamano <>
2019-08-01tree-walk: accept a raw length for traverse_path_len()Jeff King
We take a "struct name_entry", but only care about the length of the path name. Let's just take that length directly, making it easier to use the function from callers that sometimes do not have a name_entry at all. Signed-off-by: Jeff King <> Signed-off-by: Junio C Hamano <>
2019-08-01tree-walk: use size_t consistentlyJeff King
We store and manipulate the cumulative traverse_info.pathlen as an "int", which can overflow when we are fed ridiculously long pathnames (e.g., ones at the edge of 2GB or 4GB, even if the individual tree entry names are smaller than that). The results can be confusing, though after some prodding I was not able to use this integer overflow to cause an under-allocated buffer. Let's consistently use size_t to generate and store these, and make sure our addition doesn't overflow. Signed-off-by: Jeff King <> Signed-off-by: Junio C Hamano <>
2019-07-31tree-walk: drop oid from traverse_infoJeff King
As the previous commit shows, the presence of an oid in each level of the traverse_info is confusing and ultimately not necessary. Let's drop it to make it clear that it will not always be set (as well as convince us that it's unused, and let the compiler catch any merges with other branches that do add new uses). Since the oid is part of name_entry, we'll actually stop embedding a name_entry entirely, and instead just separately hold the pathname, its length, and the mode. This makes the resulting code slightly more verbose as we have to pass those elements around individually. But it also makes it more clear what each code path is going to use (and in most of the paths, we really only care about the pathname itself). A few of these conversions are noisier than they need to be, as they also take the opportunity to rename "len" to "namelen" for clarity (especially where we also have "pathlen" or "ce_len" alongside). Signed-off-by: Jeff King <> Signed-off-by: Junio C Hamano <>
2019-06-27tree-walk.c: remove the_repo from get_tree_entry_follow_symlinks()Nguyễn Thái Ngọc Duy
Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2019-06-27tree-walk.c: remove the_repo from get_tree_entry()Nguyễn Thái Ngọc Duy
Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2019-06-27tree-walk.c: remove the_repo from fill_tree_descriptor()Nguyễn Thái Ngọc Duy
While at there, clean up the_repo usage in builtin/merge-tree.c a tiny bit. Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2019-05-13Merge branch 'dl/no-extern-in-func-decl'Junio C Hamano
Mechanically and systematically drop "extern" from function declarlation. * dl/no-extern-in-func-decl: *.[ch]: manually align parameter lists *.[ch]: remove extern from function declarations using sed *.[ch]: remove extern from function declarations using spatch
2019-05-05*.[ch]: remove extern from function declarations using spatchDenton Liu
There has been a push to remove extern from function declarations. Remove some instances of "extern" for function declarations which are caught by Coccinelle. Note that Coccinelle has some difficulty with processing functions with `__attribute__` or varargs so some `extern` declarations are left behind to be dealt with in a future patch. This was the Coccinelle patch used: @@ type T; identifier f; @@ - extern T f(...); and it was run with: $ git ls-files \*.{c,h} | grep -v ^compat/ | xargs spatch --sp-file contrib/coccinelle/noextern.cocci --in-place Files under `compat/` are intentionally excluded as some are directly copied from external sources and we should avoid churning them as much as possible. Signed-off-by: Denton Liu <> Signed-off-by: Junio C Hamano <>
2019-04-08Use 'unsigned short' for mode, like diff_filespec doesElijah Newren
struct diff_filespec defines mode to be an 'unsigned short'. Several other places in the API which we'd like to interact with using a diff_filespec used a plain unsigned (or unsigned int). This caused problems when taking addresses, so switch to unsigned short. Signed-off-by: Elijah Newren <> Signed-off-by: Junio C Hamano <>
2019-02-07Merge branch 'dt/cat-file-batch-ambiguous'Junio C Hamano
"git cat-file --batch" reported a dangling symbolic link by mistake, when it wanted to report that a given name is ambiguous. * dt/cat-file-batch-ambiguous: t1512: test ambiguous cat-file --batch and --batch-output Do not print 'dangling' for cat-file in case of ambiguity
2019-01-29Merge branch 'bc/tree-walk-oid'Junio C Hamano
The code to walk tree objects has been taught that we may be working with object names that are not computed with SHA-1. * bc/tree-walk-oid: cache: make oidcpy always copy GIT_MAX_RAWSZ bytes tree-walk: store object_id in a separate member match-trees: use hashcpy to splice trees match-trees: compute buffer offset correctly when splicing tree-walk: copy object ID before use
2019-01-18Do not print 'dangling' for cat-file in case of ambiguityDavid Turner
The return values -1 and -2 from get_oid could mean two different things, depending on whether they were from an enum returned by get_tree_entry_follow_symlinks, or from a different code path. This caused 'dangling' to be printed from a git cat-file in the case of an ambiguous (-2) result. Unify the results of get_oid* and get_tree_entry_follow_symlinks to be one common type, with unambiguous values. Signed-off-by: David Turner <> Reported-by: Eric Wong <> Signed-off-by: Junio C Hamano <>
2019-01-15tree-walk: store object_id in a separate memberbrian m. carlson
When parsing a tree, we read the object ID directly out of the tree buffer. This is normally fine, but such an object ID cannot be used with oidcpy, which copies GIT_MAX_RAWSZ bytes, because if we are using SHA-1, there may not be that many bytes to copy. Instead, store the object ID in a separate struct member. Since we can no longer efficiently compute the path length, store that information as well in struct name_entry. Ensure we only copy the object ID into the new buffer if the path length is nonzero, as some callers will pass us an empty path with no object ID following it, and we will not want to read past the end of the buffer. Signed-off-by: brian m. carlson <> Signed-off-by: Junio C Hamano <>
2018-11-19tree-walk.c: make tree_entry_interesting() take an indexNguyễn Thái Ngọc Duy
In order to support :(attr) when matching pathspec on a tree, tree_entry_interesting() needs to take an index (because git_check_attr() needs it). This is the preparation step for it. This also makes it clearer what index we fall back to when looking up attributes during an unpack-trees operation: the source index. This also fixes revs->pruning.repo initialization that should have been done in 2abf350385 (revision.c: remove implicit dependency on the_index - 2018-09-21). Without it, skip_uninteresting() will dereference a NULL pointer through this call chain get_revision(revs) get_revision_internal get_revision_1 try_to_simplify_commit rev_compare_tree diff_tree_oid(..., &revs->pruning) ll_diff_tree_oid diff_tree_paths ll_diff_tree skip_uninteresting Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2018-08-15Add missing includes and forward declarationsElijah Newren
I looped over the toplevel header files, creating a temporary two-line C program for each consisting of #include "git-compat-util.h" #include $HEADER This patch is the result of manually fixing errors in compiling those tiny programs. Signed-off-by: Elijah Newren <> Signed-off-by: Junio C Hamano <>
2018-05-02tree-walk: convert get_tree_entry_follow_symlinks to object_idbrian m. carlson
Since the only caller of this function already uses struct object_id, update get_tree_entry_follow_symlinks to use it in parameters and internally. Signed-off-by: brian m. carlson <> Signed-off-by: Junio C Hamano <>
2018-03-14tree-walk: convert tree entry functions to object_idbrian m. carlson
Convert get_tree_entry and find_tree_entry to take pointers to struct object_id. Signed-off-by: brian m. carlson <> Signed-off-by: Junio C Hamano <>
2017-08-14tree-walk: convert fill_tree_descriptor() to object_idRené Scharfe
All callers of fill_tree_descriptor() have been converted to object_id already, so convert that function as well. As a nice side-effect we get rid of NULL checks in tree-diff.c, as fill_tree_descriptor() already does them for us. Helped-by: Johannes Sixt <> Signed-off-by: Rene Scharfe <> Reviewed-by: brian m. carlson <> Signed-off-by: Junio C Hamano <>
2016-09-27fsck: handle bad trees like other errorsDavid Turner
Instead of dying when fsck hits a malformed tree object, log the error like any other and continue. Now fsck can tell the user which tree is bad, too. Signed-off-by: David Turner <> Signed-off-by: Junio C Hamano <>
2016-04-25tree-walk: convert tree_entry_extract() to use struct object_idbrian m. carlson
Signed-off-by: brian m. carlson <> Signed-off-by: Junio C Hamano <>
2016-04-25struct name_entry: use struct object_id instead of unsigned char sha1[20]brian m. carlson
Signed-off-by: brian m. carlson <> Signed-off-by: Junio C Hamano <>
2016-01-05do_compare_entry: use already-computed pathDavid Turner
In traverse_trees, we generate the complete traverse path for a traverse_info. Later, in do_compare_entry, we used to go do a bunch of work to compare the traverse_info to a cache_entry's name without computing that path. But since we already have that path, we don't need to do all that work. Instead, we can just put the generated path into the traverse_info, and do the comparison more directly. We copy the path because prune_traversal might mutate `base`. This doesn't happen in any codepaths where do_compare_entry is called, but it's better to be safe. This makes git checkout much faster -- about 25% on Twitter's monorepo. Deeper directory trees are likely to benefit more than shallower ones. Signed-off-by: David Turner <> Signed-off-by: Junio C Hamano <>
2015-05-20tree-walk: learn get_tree_entry_follow_symlinksDavid Turner
Add a new function, get_tree_entry_follow_symlinks, to tree-walk.[ch]. The function is not yet used. It will be used to implement git cat-file --batch --follow-symlinks. The function locates an object by path, following symlinks in the repository. If the symlinks lead outside the repository, the function reports this to the caller. Signed-off-by: David Turner <> Signed-off-by: Ramsay Jones <> Signed-off-by: Junio C Hamano <>
2014-02-24tree-walk: finally switch over tree descriptors to contain a pre-parsed entryKirill Smelkov
This continues 4651ece8 (Switch over tree descriptors to contain a pre-parsed entry) and moves the only rest computational part mode = canon_mode(mode) from tree_entry_extract() to tree entry decode phase - to decode_tree_entry(). The reason to do it, is that canon_mode() is at least 2 conditional jumps for regular files, and that could be noticeable should canon_mode() be invoked several times. That does not matter for current Git codebase, where typical tree traversal is while (t->size) { sha1 = tree_entry_extract(t, &path, &mode); ... update_tree_entry(t); } i.e. we do t -> sha1,path.mode "extraction" only once per entry. In such cases, it does not matter performance-wise, where that mode canonicalization is done - either once in tree_entry_extract(), or once in decode_tree_entry() called by update_tree_entry() - it is approximately the same. But for future code, which could need to work with several tree_desc's in parallel, it could be handy to operate on tree_desc descriptors, and do "extracts" only when needed, or at all, access only relevant part of it through structure fields directly. And for such situations, having canon_mode() be done once in decode phase is better - we won't need to pay the performance price of 2 extra conditional jumps on every t->mode access. So let's move mode canonicalization to decode_tree_entry(). That was the final bit. Now after tree entry is decoded, it is fully ready and could be accessed either directly via field, or through tree_entry_extract() which this time got really "totally trivial". Signed-off-by: Kirill Smelkov <> Signed-off-by: Junio C Hamano <>
2013-06-17unpack-trees: don't shift conflicts left and rightRené Scharfe
If o->merge is set, the struct traverse_info member conflicts is shifted left in unpack_callback, then passed through traverse_trees_recursive to unpack_nondirectories, where it is shifted right before use. Stop the shifting and just pass the conflict bit mask as is. Rename the member to df_conflicts to prove that it isn't used anywhere else. Signed-off-by: René Scharfe <> Signed-off-by: Junio C Hamano <>
2011-10-27tree_entry_interesting(): give meaningful names to return valuesNguyễn Thái Ngọc Duy
It is a basic code hygiene to avoid magic constants that are unnamed. Besides, this helps extending the value later on for "interesting, but cannot decide if the entry truely matches yet" (ie. prefix matches) Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2011-10-27tree-walk.c: do not leak internal structure in tree_entry_len()Nguyễn Thái Ngọc Duy
tree_entry_len() does not simply take two random arguments and return a tree length. The two pointers must point to a tree item structure, or struct name_entry. Passing random pointers will return incorrect value. Force callers to pass struct name_entry instead of two pointers (with hope that they don't manually construct struct name_entry themselves) Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2011-08-29traverse_trees(): allow pruning with pathspecJunio C Hamano
The traverse_trees() machinery is primarily meant for merging two (or more) trees, and because a merge is a full tree operation, it doesn't support any pruning with pathspec. Since d1f2d7e (Make run_diff_index() use unpack_trees(), not read_tree(), 2008-01-19), however, we use unpack_trees() to traverse_trees() callchain to perform "diff-index", which could waste a lot of work traversing trees outside the user-supplied pathspec, only to discard at the blob comparison level in diff-lib.c::oneway_diff() which is way too late. Signed-off-by: Junio C Hamano <>
2011-02-03grep: drop pathspec_matches() in favor of tree_entry_interesting()Nguyễn Thái Ngọc Duy
Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2011-02-03tree_entry_interesting(): support wildcard matchingNguyễn Thái Ngọc Duy
never_interesting optimization is disabled if there is any wildcard pathspec, even if it only matches exactly on trees. Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2011-02-03diff-tree: convert base+baselen to writable strbufNguyễn Thái Ngọc Duy
In traversing trees, a full path is splitted into two parts: base directory and entry. They are however quite often concatenated whenever a full path is needed. Current code allocates a new buffer, do two memcpy(), use it, then release. Instead this patch turns "base" to a writable, extendable buffer. When a concatenation is needed, the callee only needs to append "entry" to base, use it, then truncate the entry out again. "base" must remain unchanged before and after entering a function. This avoids quite a bit of malloc() and memcpy(). Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2011-02-03Move tree_entry_interesting() to tree-walk.c and export itNguyễn Thái Ngọc Duy
Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2010-08-26Merge branch 'maint'Junio C Hamano
* maint: for-each-ref: fix objectname:short bug tree-walk: Correct bitrotted comment about tree_entry() Fix 'git log' early pager startup error case
2010-08-25tree-walk: Correct bitrotted comment about tree_entry()Elijah Newren
There was a code comment that referred to the "above two functions" but over time the functions immediately preceding the comment have changed. Just mention the relevant functions by name. Signed-off-by: Elijah Newren <> Signed-off-by: Junio C Hamano <>
2010-08-11unpack_trees: group error messages by typeMatthieu Moy
When an error is encountered, it calls add_rejected_file() which either - directly displays the error message and stops if in plumbing mode (i.e. if show_all_errors is not initialized at 1) - or stores it so that it will be displayed at the end with display_error_msgs(), Storing the files by error type permits to have a list of files for which there is the same error instead of having a serie of almost identical errors. As each bind_overlap error combines a file and an old file, a list cannot be done, therefore, theses errors are not stored but directly displayed. Signed-off-by: Matthieu Moy <> Signed-off-by: Junio C Hamano <>
2008-03-09Make 'traverse_trees()' traverse conflicting DF entries in parallelLinus Torvalds
This makes the traverse_trees() entry comparator routine use the more relaxed form of name comparison that considers files and directories with the same name identical. We pass in a separate mask for just the directory entries, so that the callback routine can decide (if it wants to) to only handle one or the other type, but generally most (all?) users are expected to really want to see the case of a name 'foo' showing up in one tree as a file and in another as a directory at the same time. In particular, moving 'unpack_trees()' over to use this tree traversal mechanism requires this. Signed-off-by: Linus Torvalds <> Signed-off-by: Junio C Hamano <>
2008-03-09Add return value to 'traverse_tree()' callbackLinus Torvalds
This allows the callback to return an error value, but it can also specify which of the tree entries that it actually used up by returning a positive mask value. Signed-off-by: Linus Torvalds <> Signed-off-by: Junio C Hamano <>
2008-03-09Make 'traverse_tree()' use linked structure rather than 'const char *base'Linus Torvalds
This makes the calling convention a bit less obvious, but a lot more flexible. Instead of allocating and extending a new 'base' string, we just link the top-most name into a linked list of the 'info' structure when traversing a subdirectory, and we can generate the basename by following the list. Perhaps even more importantly, the linked list of info structures also gives us a place to naturally save off other information than just the directory name. Signed-off-by: Linus Torvalds <> Signed-off-by: Junio C Hamano <>
2007-12-02rename: Break filepairs with different types.Junio C Hamano
When we consider if a path has been totally rewritten, we did not touch changes from symlinks to files or vice versa. But a change that modifies even the type of a blob surely should count as a complete rewrite. While we are at it, modernise diffcore-break to be aware of gitlinks (we do not want to touch them). Signed-off-by: Junio C Hamano <>
2007-11-14Fix rev-list when showing objects involving submodulesLinus Torvalds
The function mark_tree_uninteresting() assumed that the tree entries are blob when they are not trees. This is not so. Since we do not traverse into submodules (yet), the gitlinks should be ignored. In general, we should try to start moving away from using the "S_ISLNK()" like things for internal git state. It was a mistake to just assume the numbers all were same across all systems in the first place. This implementation converts to the "object_type", and then uses a case statement. Noticed by Ilari on IRC. Test script taken from an earlier version by Dscho. Signed-off-by: Linus Torvalds <> Signed-off-by: Junio C Hamano <>
2007-06-23Two trivial -Wcast-qual fixesJunio C Hamano
Luiz Fernando N. Capitulino noticed the one in tree-walk.h where we cast away constness while computing the legnth of a tree entry. Signed-off-by: Junio C Hamano <>
2007-05-13Remove stale non-static-inline prototype for tree_entry_extract()Matthieu Castet
When 4651ece8 made the function a "static inline", it should have removd the stale prototype but everybody missed that. Thomas Glanzmann noticed this broke compilation with Forte12 compiler on his Sun boxes. Signed-off-by: Junio C Hamano <>
2007-03-21Switch over tree descriptors to contain a pre-parsed entryLinus Torvalds
This makes the tree descriptor contain a "struct name_entry" as part of it, and it gets filled in so that it always contains a valid entry. On some benchmarks, it improves performance by up to 15%. That makes tree entry "extract" trivial, and means that we only actually need to decode each tree entry just once: we decode the first one when we initialize the tree descriptor, and each subsequent one when doing "update_tree_entry()". In particular, this means that we don't need to do strlen() both at extract time _and_ at update time. Finally, it also allows more sharing of code (entry_extract(), that wanted a "struct name_entry", just got totally trivial, along with the "tree_entry()" function). Signed-off-by: Linus Torvalds <> Signed-off-by: Junio C Hamano <>
2007-03-21Initialize tree descriptors with a helper function rather than by hand.Linus Torvalds
This removes slightly more lines than it adds, but the real reason for doing this is that future optimizations will require more setup of the tree descriptor, and so we want to do it in one place. Also renamed the "desc.buf" field to "desc.buffer" just to trigger compiler errors for old-style manual initializations, making sure I didn't miss anything. Signed-off-by: Linus Torvalds <> Signed-off-by: Junio C Hamano <>
2007-03-21Remove "pathlen" from "struct name_entry"Linus Torvalds
Since we have the "tree_entry_len()" helper function these days, and don't need to do a full strlen(), there's no point in saving the path length - it's just redundant information. Signed-off-by: Linus Torvalds <> Signed-off-by: Junio C Hamano <>