src/index.c


Log

Author Commit Date CI Message
Pierre-Olivier Latour 807566d5 2015-04-03T18:59:11 Entry argument passed to git_index_add_frombuffer() should be const
Damien PROFETA a275fbc0 2015-02-05T11:40:16 Add API to add a memory buffer to an index git_index_add_frombuffer enables now to store a memory buffer in the odb and to store an entry in the index directly if the index is attached to a repository.
Carlos Martín Nieto a291790a 2015-02-15T05:18:01 Merge pull request #2831 from ethomson/merge_lock merge: lock index during the merge (not just checkout)
Edward Thomson 41fae48d 2015-02-03T22:31:10 indexwriter: an indexwriter for repo operations Provide git_indexwriter_init_for_operation for the common locking pattern in merge, rebase, revert and cherry-pick.
Edward Thomson 55798fd1 2015-01-17T20:49:04 git_indexwriter: lock then write the index Introduce `git_indexwriter`, to allow us to lock the index while performing additional operations, then complete the write (or abort, unlocking the index).
Edward Thomson f1453c59 2015-02-12T12:19:37 Make our overflow check look more like gcc/clang's Make our overflow checking look more like gcc and clang's, so that we can substitute it out with the compiler instrinsics on platforms that support it. This means dropping the ability to pass `NULL` as an out parameter. As a result, the macros also get updated to reflect this as well.
Edward Thomson 2884cc42 2015-02-11T09:39:38 overflow checking: don't make callers set oom Have the ALLOC_OVERFLOW testing macros also simply set_oom in the case where a computation would overflow, so that callers don't need to.
Edward Thomson 392702ee 2015-02-09T23:41:13 allocations: test for overflow of requested size Introduce some helper macros to test integer overflow from arithmetic and set error message appropriately.
Jacques Germishuys b63b3b0e 2015-01-25T14:08:05 Ensure git_index_entry is not NULL before trying to free it
Edward Thomson 2fe8157e 2014-12-22T18:42:03 index: reuc and name entrycounts should be size_t For the REUC and NAME entries, we use size_t internally, and we take size_t for the get_byindex() functions, but the entrycount() functions strangely cast to an unsigned int instead.
Edward Thomson a64119e3 2014-11-25T18:13:00 checkout: disallow bad paths on win32 Disallow: 1. paths with trailing dot 2. paths with trailing space 3. paths with trailing colon 4. paths that are 8.3 short names of .git folders ("GIT~1") 5. paths that are reserved path names (COM1, LPT1, etc). 6. paths with reserved DOS characters (colons, asterisks, etc) These paths would (without \\?\ syntax) be elided to other paths - for example, ".git." would be written as ".git". As a result, writing these paths literally (using \\?\ syntax) makes them hard to operate with from the shell, Windows Explorer or other tools. Disallow these.
Vicent Marti 0d388adc 2014-11-25T00:58:03 index: Check for valid paths before creating an index entry
Carlos Martín Nieto 62a617dc 2014-11-06T16:16:46 iterator: submodules are determined by an index or tree We cannot know from looking at .gitmodules whether a directory is a submodule or not. We need the index or tree we are comparing against to tell us. Otherwise we have to assume the entry in .gitmodules is stale or otherwise invalid. Thus we pass the index of the repository into the workdir iterator, even if we do not want to compare against it. This follows what git does, which even for `git diff <tree>`, it will consider staged submodules as such.
Carlos Martín Nieto c2f8b215 2014-09-28T07:00:49 index: write out the tree cache extension Keeping the cache around after read-tree is only one part of the optimisation opportunities. In order to share the cache between program instances, we need to write the TREE extension to the index. Do so, taking the opportunity to rename 'entries' to 'entry_count' to match the name given in the format description. The included test is rather trivial, but works as a sanity check.
Carlos Martín Nieto 6843cebe 2014-07-10T14:10:39 index: fill the tree cache when reading from a tree When reading from a tree, we know what every tree is going to look like, so we can fill in the tree cache completely, making use of the index for modification of trees a lot quicker.
Carlos Martín Nieto 19c88310 2014-07-10T13:48:13 tree-cache: move to use a pool allocator This simplifies freeing the entries quite a bit; though there aren't that many failure paths right now, introducing filling the cache from a tree will introduce more. This makes sure not to leak memory on errors.
Jacques Germishuys ff97778a 2014-09-25T13:07:36 The raw index buffer content is not guaranteed to be aligned * Ensure alignment by copying the content into a structure on the stack
Carlos Martín Nieto 052a2ffd 2014-05-22T16:01:02 index: check for valid filemodes on add
Russell Belfer 0fc8e1f6 2014-04-28T14:34:55 Lay groundwork for updating stat cache in diff This reorganized the diff OID calculation to make it easier to correctly update the stat cache during a diff once the flags to do so are enabled. This includes marking the path of a git_index_entry as const so we can make a "fake" git_index_entry with a "const char *" path and not get warnings. I was a little surprised at how unobtrusive this change was, but I think it's probably a good thing.
Russell Belfer 17ef678c 2014-04-21T11:55:57 Fix some coverity-found issues
Russell Belfer ea642d61 2014-04-14T12:29:27 Fix race checking for existing index items In the threading tests, I was still seeing a race condition where the same item could end up being inserted multiple times into the index. Preserving the sorted-ness of the index outside of the `index_insert` call fixes the issue.
Russell Belfer 7d490872 2014-04-10T22:31:01 Attribute file cache refactor This is a big refactoring of the attribute file cache to be a bit simpler which in turn makes it easier to enforce a lock around any updates to the cache so that it can be used in a threaded env. Tons of changes to the attributes and ignores code.
Russell Belfer aba6b5ed 2014-03-14T21:59:26 Fix leak in git_index_conflict_cleanup I introduced a leak into conflict cleanup by removing items from inside the git_vector_remove_matching call. This simplifies the code to just use one common way for the two conflict cleanup APIs. When an index has an active snapshot, removing an item can cause an error (inserting into the deferred deletion vector), so I made the git_index_conflict_cleanup API return an error code. I felt like this wasn't so bad since it is just like the other APIs. I fixed up a couple of comments while I was changing the header.
Russell Belfer 52bb0476 2014-03-14T13:53:15 Clean up index snapshot function naming Clear up some of the various "find" functions and the snapshot API naming to be things I like more.
Russell Belfer 8a2834d3 2014-03-14T13:20:51 Index locking and entry allocation changes This makes the lock management on the index a little bit broader, having a number of routines hold the lock across looking up the item to be modified and actually making the modification. Still not true thread safety, but more pure index modifications are now safe which allows the simple cases (such as starting up a diff while index modifications are underway) safe enough to get the snapshot without hitting allocation problems. As part of this, I simplified the allocation of index entries to use a flex array and just put the path at the end of the index entry. This makes every entry self-contained and makes it a little easier to feel sure that pointers to strings aren't being accidentally copied and freed while other references are still being held.
Russell Belfer 3b4c401a 2014-02-10T13:20:08 Decouple index iterator sort from index This makes the index iterator honor the GIT_ITERATOR_IGNORE_CASE and GIT_ITERATOR_DONT_IGNORE_CASE flags without modifying the index data itself. To take advantage of this, I had to export a number of the internal index entry comparison functions. I also wrote some new tests to exercise the capability.
Russell Belfer dac16048 2014-02-08T16:42:26 Add mutex around index entries changes This surrounds any function that mutates the entries vector with a mutex so it can be safely snapshotted.
Russell Belfer 54edbb98 2014-02-07T16:48:27 Add index snapshot and use it for iterator
Russell Belfer 3dbee456 2014-02-07T14:10:35 Some index internals refactoring Again, laying groundwork for some index iterator changes, this contains a bunch of code refactorings for index internals that should make it easier down the line to add locking around index modifications. Also this removes the redundant prefix_position function and fixes some potential memory leaks.
Russell Belfer c67fd4c9 2014-02-07T11:20:36 Some vector utility tweaks This is just laying some groundwork for internal index changes that I'm working on.
Vicent Marti 923c8400 2014-04-04T14:24:08 Merge pull request #2215 from libgit2/rb/submodule-cache-fixes Improve submodule cache management
Jacques Germishuys 3b4ba278 2014-04-03T15:50:21 Const correctness!
Russell Belfer 8f4e5275 2014-04-01T16:46:25 More tests and fix submodule index refresh There was a little bug where the submodule cache thought that the index date was out of date even when it wasn't that was resulting in some extra scans of index data even when not needed. Mostly this commit adds a bunch of new tests including adding and removing submodules in the index and in the HEAD and seeing if we can automatically pick them up when refreshing.
Russell Belfer db0e7878 2014-03-28T16:50:49 Make submodule refresh a bit smarter This makes submodule cache refresh actually look at the timestamps from the data sources for submodules and reload as needed if they have changed since the last refresh.
Edward Thomson 05d47768 2014-03-10T22:30:41 Introduce git_merge_file for consumers
Brendan Forster 0782c89e 2014-03-10T14:40:07 corrected typo in error message
Ben Straub b1f2c2e2 2014-02-22T10:18:42 Prevent icc warning
Russell Belfer 72556cc6 2014-02-20T14:27:10 Address PR comments * Make GIT_INLINE an internal definition so it cannot be used in public headers * Fix language in CONTRIBUTING * Make index caps API use signed instead of unsigned values
Russell Belfer 3158e2fe 2014-02-07T15:24:39 Fix some Windows warnings This fixes a number of warnings with the Windows 64-bit build including a test failure in test_repo_message__message where an invalid pointer to a git_buf was being used.
Russell Belfer 43709ca8 2014-02-04T10:33:30 Fix typo setting sorted flag when reloading index This fixes a typo I made for setting the sorted flag on the index after a reload. That typo didn't actually cause any test failures so I'm also adding a test that explicitly checks that the index is correctly sorted after a reload when ignoring case and when not.
Russell Belfer 882c7742 2014-02-04T10:01:37 Convert pqueue to just be a git_vector This updates the git_pqueue to simply be a set of specialized init/insert/pop functions on a git_vector. To preserve the pqueue feature of having a fixed size heap, I converted the "sorted" field in git_vectors to a more general "flags" field so that pqueue could mix in it's own flag. This had a bunch of ramifications because a number of places were directly looking at the vector "sorted" field - I added a couple new git_vector helpers (is_sorted, set_sorted) so the specific representation of this information could be abstracted.
Russell Belfer b794cbcd 2014-01-30T11:38:25 Rename conflict to collision to prevent confusion
Edward Thomson b747eb14 2014-01-29T12:55:33 Give index_isrch the same semantics as index_srch In case insensitive index mode, we would stop at a prefixed entry, treating the provided search key length as a substring, not the length of the string to match.
Vicent Marti 1eefd356 2014-01-29T18:44:29 index: Implement folder-file checks
Vicent Marti 53bec813 2014-01-29T18:17:08 index: Compare with given len
Carlos Martín Nieto d541170c 2014-01-24T11:36:41 index: rename an entry's id to 'id' This was not converted when we converted the rest, so do it now.
Russell Belfer 26c1cb91 2013-12-09T09:44:03 One more rename/cleanup for callback err functions
Russell Belfer 25e0b157 2013-12-06T15:07:57 Remove converting user error to GIT_EUSER This changes the behavior of callbacks so that the callback error code is not converted into GIT_EUSER and instead we propagate the return value through to the caller. Instead of using the giterr_capture and giterr_restore functions, we now rely on all functions to pass back the return value from a callback. To avoid having a return value with no error message, the user can call the public giterr_set_str or some such function to set an error message. There is a new helper 'giterr_set_callback' that functions can invoke after making a callback which ensures that some error message was set in case the callback did not set one. In places where the sign of the callback return value is meaningful (e.g. positive to skip, negative to abort), only the negative values are returned back to the caller, obviously, since the other values allow for continuing the loop. The hardest parts of this were in the checkout code where positive return values were overloaded as meaningful values for checkout. I fixed this by adding an output parameter to many of the internal checkout functions and removing the overload. This added some code, but it is probably a better implementation. There is some funkiness in the network code where user provided callbacks could be returning a positive or a negative value and we want to rely on that to cancel the loop. There are still a couple places where an user error might get turned into GIT_EUSER there, I think, though none exercised by the tests.
Russell Belfer dab89f9b 2013-12-04T21:22:57 Further EUSER and error propagation fixes This continues auditing all the places where GIT_EUSER is being returned and making sure to clear any existing error using the new giterr_user_cancel helper. As a result, places that relied on intercepting GIT_EUSER but having the old error preserved also needed to be cleaned up to correctly stash and then retrieve the actual error. Additionally, as I encountered places where error codes were not being propagated correctly, I tried to fix them up. A number of those fixes are included in the this commit as well.
nulltoken bd15b513 2013-11-19T13:24:10 index: Free the index on git_index_open() failure
Edward Thomson 1d3a8aeb 2013-11-04T18:28:57 move mode_t to filebuf_open instead of _commit
Russell Belfer 8e5a8ef8 2013-11-01T09:51:01 Convert git_index_read to have a "force" flag This is a little more intuitive than the turned-around option that I originally wrote.
Russell Belfer 4bf630b6 2013-10-31T14:36:52 Make diff and status perform soft index reload This changes `git_index_read` to have two modes - a hard index reload that always resets the index to match the on-disk data (which was the old behavior) and a soft index reload that uses the timestamp / file size information and only replaces the index data if the file on disk has been modified. This then updates the git_status code to do a soft reload unless the new GIT_STATUS_OPT_NO_REFRESH flag is passed in. This also changes the behavior of the git_diff functions that use the index so that when an index is not explicitly passed in (i.e. when the functions call git_repository_index for you), they will also do a soft reload for you. This intentionally breaks the file signature of git_index_read because there has been some confusion about the behavior previously and it seems like all existing uses of the API should probably be examined to select the desired behavior.
Vicent Martí 95c148b2 2013-10-08T17:03:12 Merge pull request #1886 from libgit2/precompose-utf8 Add support for core.precomposeunicode on Mac
Russell Belfer 14997dc5 2013-10-08T12:45:43 More filemode cleanups for FAT on MacOS This cleans up some additional issues. The main change is that on a filesystem that doesn't support mode bits, libgit2 will now create new blobs with GIT_FILEMODE_BLOB always instead of being at the mercy to the filesystem driver to report executable or not. This means that if "core.filemode" lies and claims that filemode is not supported, then we will ignore the executable bit from the filesystem. Previously we would have allowed it. This adds an option to the new git_repository_reset_filesystem to recurse through submodules if desired. There may be other types of APIs that would like a "recurse submodules" option, but this one is particularly useful. This also has a number of cleanups, etc., for related things including trying to give better error messages when problems come up from the filesystem. For example, the FAT filesystem driver on MacOS appears to return errno EINVAL if you attempt to write a filename with invalid UTF-8 in it. We try to capture that with a better error message now.
nulltoken da7b78fa 2013-10-04T14:03:12 index: Make _read() cope with index file creation
Russell Belfer 1ca3e49f 2013-09-23T13:34:01 Clean up newly introduced warnings The attempt to "clean up warnings" seems to have introduced some new warnings on compliant compilers. This fixes those in a way that I suspect will also be okay for the non-compliant compilers. Also this fixes what appears to be an extra semicolon in the repo initialization template dir handling (and as part of that fix, handles the case where an error occurs correctly).
Linquize 66566516 2013-09-08T17:15:42 Fix warning
Russell Belfer f240acce 2013-09-05T11:20:12 Add more file mode permissions macros This adds some more macros for some standard operations on file modes, particularly related to permissions, and then updates a number of places around the code base to use the new macros.
Carlos Martín Nieto 3d276874 2013-08-19T10:30:44 index: report when it's locked Report the index being locked with its own error code in order to be able to differentiate, as a locked index is typically the result of a crashed process or concurrent access, both of which often require user intervention to fix.
Edward Thomson 57f31f05 2013-08-08T11:05:00 Fixes to safely reading the index Avoid wrapping around extension size when reading, avoid walking off the end of the buffer when reading names.
Russell Belfer a16e4172 2013-07-25T12:27:39 Fix rename detection to use actual blob size The size data in the index may not reflect the actual size of the blob data from the ODB when content filtering comes into play. This commit fixes rename detection to use the actual blob size when calculating data signatures instead of the value from the index. Because of a misunderstanding on my part, I first converted the git_index_add_bypath API to use the post-filtered blob data size in creating the index entry. I backed that change out, but I kept the overall refactoring of that routine and the new internal git_blob__create_from_paths API because it eliminates an extra stat() call from the code that adds a file to the index. The existing tests actually cover this code path, at least when running on Windows, so at this point I'm not adding new tests to cover the changes.
Rémi Duraffort 8d6ef4bf 2013-07-15T15:59:35 index: fix potential memory leaks
Russell Belfer 41f1f9d7 2013-06-27T16:52:00 Add API to get path to index file
Russell Belfer d2ce27dd 2013-06-24T23:16:06 Add public API for pathspec matching This adds a new public API for compiling pathspecs and matching them against the working directory, the index, or a tree from the repository. This also reworks the pathspec internals to allow the sharing of code between the existing internal usage of pathspec matching and the new external API. While this is working and the new API is ready for discussion, I think there is still an incorrect behavior in which patterns are always matched against the full path of an entry without taking the subdirectories into account (so "s*" will match "subdir/file" even though it wouldn't with core Git). Further enhancements are coming, but this was a good place to take a functional snapshot.
Russell Belfer 178aa39c 2013-07-03T11:42:43 Be more thread aware with some index updates The index isn't really thread safe for the most part, but we can easily be more careful and avoid double frees and the like, which are serious problems (as opposed to a lookup which might return the incorrect value but if the index in being updated, that is much harder to avoid).
Russell Belfer 22b6b82f 2013-06-20T12:16:06 Add status flags to force output sort order Files in status will, be default, be sorted according to the case insensitivity of the filesystem that we're running on. However, in some cases, this is not desirable. Even on case insensitive file systems, 'git status' at the command line will generally use a case sensitive sort (like 'ls'). Some GUIs prefer to display a list of file case insensitively even on case-sensitive platforms. This adds two new flags: GIT_STATUS_OPT_SORT_CASE_SENSITIVELY and GIT_STATUS_OPT_SORT_CASE_INSENSITIVELY that will override the default sort order of the status output and give the user control. This includes tests for exercising these new options and makes the examples/status.c program emulate core Git and always use a case sensitive sort.
Russell Belfer 7863523a 2013-06-19T15:54:19 Add tests and fix use of freed memory This adds some tests for updating the index and having it remove items to make sure that the iteration over the index still works even as earlier items are removed. In testing with valgrind, this found a path that would use the path string from the index entry after it had been freed. The bug fix is simply to copy the path of the index entry before doing any actual index manipulation.
Russell Belfer f30fff45 2013-06-19T15:27:25 Add index pathspec-based operations This adds three new public APIs for manipulating the index: 1. `git_index_add_all` is similar to `git add -A` and will add files in the working directory that match a pathspec to the index while honoring ignores, etc. 2. `git_index_remove_all` removes files from the index that match a pathspec. 3. `git_index_update_all` updates entries in the index based on the current contents of the working directory, either added the new information or removing the entry from the index.
Russell Belfer 6ea999bb 2013-06-13T15:52:12 Make index_insert keep existing case In a case insensitive index, if you attempt to add a file from disk with a different case pattern, the old case pattern in the index should be preserved. This fixes that (and a couple of minor warnings).
Vicent Marti 6de9b2ee 2013-06-12T21:10:33 util: It's called `memzero`
Vicent Marti eb58e2d0 2013-06-12T21:05:48 Merge remote-tracking branch 'arrbee/minor-paranoia' into development
Russell Belfer 2f77d8f1 2013-06-10T14:16:56 Fix some memory leaks
Russell Belfer 3e9e6cda 2013-06-07T09:54:33 Add safe memset and use it This adds a `git__memset` routine that will not be optimized away and updates the places where I memset() right before a free() call to use it.
Russell Belfer 03a89070 2013-05-31T21:49:40 Make git_index_read_tree preserve stat cache Instead of just blowing away the stat cache data when loading a new tree into the index, this checks if each loaded item has a corresponding existing item with the same OID and if so, copies the stat data from the old item to the new one so it will not be blown away.
Russell Belfer f658dc43 2013-05-31T14:09:58 Zero memory for major objects before freeing By zeroing out the memory when we free larger objects (i.e. those that serve as collections of other data, such as repos, odb, refdb), I'm hoping that it will be easier for libgit2 bindings to find errors in their object management code.
Edward Thomson 8c2458be 2013-05-31T11:41:33 improve test for index extension truncation
Russell Belfer 43efc449 2013-05-16T11:03:55 Ensure reuc vector is always valid In theory, if there was a problem reading the REUC data, the read_reuc() routine could have left uninitialized and invalid data in the git_index vector. This moves the line that inserts a new entry into the vector down to the bottom of the routine so we know all the content is already valid. Also, per @linquize, this uses calloc to ensure no uninitialized data.
Edward Thomson 0e0108f7 2013-05-17T15:59:57 introduce git_conflict_iterator
Russell Belfer 57908bb3 2013-05-16T11:03:55 Ensure reuc vector is always valid In theory, if there was a problem reading the REUC data, the read_reuc() routine could have left uninitialized and invalid data in the git_index vector. This moves the line that inserts a new entry into the vector down to the bottom of the routine so we know all the content is already valid. Also, per @linquize, this uses calloc to ensure no uninitialized data.
Russell Belfer 96c01991 2013-05-15T09:24:51 Remove entry dup/free functions and fix comments This removes the functions to duplicate and free copies of a git_index_entry and updates the comments to explain that you should just use the public definition of the struct as needed.
Russell Belfer 797dfb28 2013-05-13T16:09:33 Add APIs to dup and free git_index_entrys This adds git_index_entry_dup to make a copy of an existing entry and git_index_entry_free to release the memory of the copy. It also updates the documentation for git_index_get_bypath and git_index_get_byindex to make it clear that the returned structure should *not* be modified.
Vicent Martí 71596200 2013-05-15T15:47:46 Merge pull request #1588 from arrbee/fixes-for-checkout-and-diff Bug fixes for checkout and diff
Russell Belfer 72b3dd4a 2013-05-15T15:23:33 Use GIT_IDXENTRY_STAGE macro Since I added the GIT_IDXENTRY_STAGE macro to extract the stage from a git_index_entry, we probably don't need an internal inline function to do the same thing.
Russell Belfer dcb0f7c0 2013-05-15T14:54:02 Fix checkout of submodules with no .gitmodules It is possible for there to be a submodule in a repository with no .gitmodules file (for example, if the user forgot to commit the .gitmodules file). In this case, core Git will just create an empty directory as a placeholder for the submodule but otherwise ignore it. We were generating an error and stopping the checkout. This makes our behavior match that of core git.
nulltoken 1fed6b07 2013-05-13T21:57:37 Fix trailing whitespaces
Vicent Martí 03c28d92 2013-05-06T06:45:53 Merge pull request #1526 from arrbee/cleanup-error-return-without-msg Make sure error messages are set for most error returns
Edward Thomson d8041638 2013-05-02T17:22:13 fix some leaks
Russell Belfer 81b7dec4 2013-05-02T03:06:34 Fix some compile warnings and trailing whitespace
Vicent Marti e1807113 2013-05-01T15:31:23 merge: Warning noise
Russell Belfer ae99f5e2 2013-05-01T04:57:24 Make sure error messages get set
Edward Thomson 75d1c8c6 2013-04-30T17:33:11 move NAME and REUC extensions to sys/
Edward Thomson 0462fba5 2013-04-30T14:56:41 renames!
Edward Thomson bec65a5e 2013-04-01T22:16:21 merge!
Russell Belfer b7f167da 2013-04-29T13:52:12 Make git_oid_cmp public and add git_oid__cmp
Russell Belfer eac76c23 2013-04-22T14:27:36 Use config cache where possible This converts many of the config lookups that are done around the library to use the repository config cache. This was everything I could find that wasn't part of diff (which requires a larger fix).
Russell Belfer 2aee1aa4 2013-04-18T14:35:13 Fix uninitialized var warnings
Arkadiy Shapkin 10c06114 2013-03-17T04:46:46 Several warnings detected by static code analyzer fixed Implicit type conversion argument of function to size_t type Suspicious sequence of types castings: size_t -> int -> size_t Consider reviewing the expression of the 'A = B == C' kind. The expression is calculated as following: 'A = (B == C)' Unsigned type is never < 0
Russell Belfer 169dc616 2013-03-05T16:10:05 Make iterator APIs consistent with standards The iterator APIs are not currently consistent with the parameter ordering of the rest of the codebase. This rearranges the order of parameters, simplifies the naming of a number of functions, and makes somewhat better use of macros internally to clean up the iterator code. This also expands the test coverage of iterator functionality, making sure that case sensitive range-limited iteration works correctly.
Vicent Martí b8daa9e0 2013-03-04T16:19:38 Merge pull request #1380 from phkelley/index_icase Disable ignore_case when writing the index to a tree