Log

Author Commit Date CI Message
Edward Thomson ea702a0b 2019-12-04T14:25:36 release.md: note that we do two security releases Note that for security releases, we update the two most recent major release branches.
Edward Thomson ad1548e4 2019-12-04T13:51:03 Merge pull request #5317 from csware/size_t MSVC: Fix warning C4133 on x64: "function": Incompatible types - from "unsigned long *" to "size_t *"
Sven Strickroth bdf96512 2019-12-03T21:17:30 MSVC: Fix warning C4133 on x64: "function": Incompatible types - from "unsigned long *" to "size_t *" Signed-off-by: Sven Strickroth <email@cs-ware.de>
Edward Thomson 4fe52df6 2019-12-03T18:26:24 Merge pull request #5316 from libgit2/ethomson/publish_docs_on_master ci: only push docs from the libgit2/libgit2 repo
Edward Thomson 9c30fbed 2019-12-03T18:09:03 ci: only push docs from the libgit2/libgit2 repo Users may fork libgit2 and run libgit2's CI on that, which is delightful! However, if they do, we'll fail the documentation publish phase, which is correct (because we don't allow them to publish _their_ version of the docs) but regrettable (since it should not fail). Only run the documentation publish phase when we merge branches into the libgit2/libgit2 repo.
Edward Thomson 36bfc27a 2019-12-01T14:38:54 Merge pull request #5314 from pks-t/pks/dll-main-removal global: convert to fiber-local storage to fix exit races
Edward Thomson d298f9b2 2019-12-01T14:11:56 Merge pull request #5315 from kastiglione/dl/fix-copypaste-in-git_cherrypick_commit-docstring Fix copy&paste in git_cherrypick_commit docstring
Edward Thomson 7f6fdb82 2019-12-01T14:11:22 Merge pull request #5312 from pks-t/pks/patch-base85-overflow patch_parse: fix out-of-bounds reads caused by integer underflow
Dave Lee b7cf4b9e 2019-11-29T14:16:04 Fix copy&paste in git_cherrypick_commit docstring
Patrick Steinhardt 5c6180b5 2019-11-29T11:06:11 global: convert to fiber-local storage to fix exit races On Windows platforms, we automatically clean up the thread-local storage upon detaching a thread via `DllMain()`. The thing is that this happens for every thread of applications that link against the libgit2 DLL, even those that don't have anything to do with libgit2 itself. As a result, we cannot assume that these unsuspecting threads make use of our `git_libgit2_init()` and `git_libgit2_shutdow()` reference counting, which may lead to racy situations: Thread 1 Thread 2 git_libgit2_shutdown() DllMain(DETACH_THREAD) git__free_tls_data() git_atomic_dec() == 0 git__free_tls_data() TlsFree(_tls_index) TlsGetValue(_tls_index) Due to the second thread never having executed `git_libgit2_init()`, the first thread will clean up TLS data and as a result also free the `_tls_index` variable. When detaching the second thread, we unconditionally access the now-free'd `_tls_index` variable, which is obviously not going to work out well. Fix the issue by converting the code to use fiber-local storage instead of thread-local storage. While FLS will behave the exact same as TLS if no fibers are in use, it does allow us to specify a destructor similar to the one that is accepted by pthread_key_create(3P). Like this, we do not have to manually free indices anymore, but will let the FLS handle calling the destructor. This allows us to get rid of `DllMain()` completely, as we only used it to keep track of when threads were exiting and results in an overall simplification of TLS cleanup.
Edward Thomson 7f20778b 2019-11-29T09:14:04 Merge pull request #5311 from pks-t/pks/clar-trace-warning tests: fix compiler warning if tracing is disabled
Edward Thomson 61038425 2019-11-29T09:13:33 Merge pull request #5313 from pks-t/pks/config-invasive tests: config: only test parsing huge file with GITTEST_INVASIVE_SPEED
Patrick Steinhardt 361ebbcb 2019-11-28T15:36:40 tests: config: only test parsing huge file with GITTEST_INVASIVE_SPEED The test in config::stress::huge_section_with_many_values takes quite a long time to execute. Hide it behind the GITTEST_INVASIVE_SPEED environment varibale to not needlessly blow up execution time of tests. As this environment variable is being set by the continuous integration, we will execute it regularly anyway.
Patrick Steinhardt 33e6c402 2019-11-28T15:26:36 patch_parse: fix out-of-bounds reads caused by integer underflow The patch format for binary files is a simple Base85 encoding with a length byte as prefix that encodes the current line's length. For each line, we thus check whether the line's actual length matches its expected length in order to not faultily apply a truncated patch. This also acts as a check to verify that we're not reading outside of the line's string: if (encoded_len > ctx->parse_ctx.line_len - 1) { error = git_parse_err(...); goto done; } There is the possibility for an integer underflow, though. Given a line with a single prefix byte, only, `line_len` will be zero when reaching this check. As a result, subtracting one from that will result in an integer underflow, causing us to assume that there's a wealth of bytes available later on. Naturally, this may result in an out-of-bounds read. Fix the issue by checking both `encoded_len` and `line_len` for a non-zero value. The binary format doesn't make use of zero-length lines anyway, so we need to know that there are both encoded bytes and remaining characters available at all. This patch also adds a test that works based on the last error message. Checking error messages is usually too tightly coupled, but in fact parsing the patch failed even before the change. Thus the only possibility is to use e.g. Valgrind, but that'd result in us not catching issues when run without Valgrind. As a result, using the error message is considered a viable tradeoff as we know that we didn't start decoding Base85 in the first place.
Patrick Steinhardt 1d470a71 2019-11-28T14:45:15 tests: fix compiler warning if tracing is disabled If building libgit2's test suite with tracing disabled, then the compiler will emit a warning due to the unused `message_prefix` function. Fix the issue by wrapping the whole file into ifdef's for `GIT_TRACE` and providing separate empty function implementations for both `cl_global_trace_register` and `cl_global_trace_disable`.
Patrick Steinhardt fb439c97 2019-11-28T14:41:58 Merge pull request #5306 from herrerog/patchid diff: complete support for git patchid
Patrick Steinhardt 61176a9b 2019-11-28T14:31:16 Merge pull request #5243 from pks-t/pks/config-optimize-mem Memory optimizations for config entries
Gregory Herrero ece5bb5e 2019-11-07T14:10:00 diff: make patchid computation work with all types of commits. Current implementation of patchid is not computing a correct patchid when given a patch where, for example, a new file is added or removed. Some more corner cases need to be handled to have same behavior as git patch-id command. Add some more tests to cover those corner cases. Signed-off-by: Gregory Herrero <gregory.herrero@oracle.com>
Patrick Steinhardt 0b5540b9 2019-11-28T13:56:54 Merge pull request #5307 from palmin/hash_sha256 ssh: include sha256 host key hash when supported
Patrick Steinhardt dfea0713 2019-11-28T13:51:40 Merge pull request #5272 from tiennou/examples/cli-ification Various examples shape-ups
Patrick Steinhardt b63ad958 2019-11-28T13:19:50 Merge pull request #5309 from libgit2/ethomson/trace Improve trace support in tests
Patrick Steinhardt 0e5243b7 2019-11-28T12:42:36 Merge pull request #5123 from libgit2/ethomson/off_t Move `git_off_t` to `git_object_size_t`
Edward Thomson 7198d345 2019-11-28T15:12:05 Merge pull request #5310 from lberk/compat-git-attr-t Add compat typdef for git_attr_t
Lukas Berk 5ace4ccf 2019-11-27T22:40:17 Move deprecated git_attr_t typedef to previous attribute section
Lukas Berk 3739a15c 2019-11-27T21:31:25 Add attr.h include
Lukas Berk aea049b6 2019-11-27T20:05:32 Add compat typdef for git_attr_t Some libraries haven't updated to git_attr_value_t and break. Adding the comapt typedef as suggested.
Edward Thomson b7f70bc2 2019-11-27T12:36:17 tests: optionally show test execution tracing Only show test trace execution when the CLAR_TRACE_TESTS environment variable is set. This reduces the noise during tracing.
Edward Thomson 85efe896 2019-11-27T12:34:10 tests: display trace level with prefix in tests
Edward Thomson 625a3a49 2019-11-27T12:29:34 trace: enable tracing by default Tracing is meant to be extremely low-impact when not enabled. We currently ship no tracing calls in libgit2, but if / when we do, the tracing infrastructure is created to skip tracing as quickly as possible. It should compile to a simple test when tracing is off. Thus, there's on reason to not enable it by default.
Edward Thomson 7805122b 2019-11-27T14:22:27 Merge pull request #5308 from libgit2/ethomson/cifix CI Build Updates
Edward Thomson 05237ee5 2019-06-23T17:20:17 integer: use int64_t's for checks Use int64_t internally for type visibility.
Edward Thomson ee0c8618 2019-06-23T17:19:31 offmap: store off64_t's instead of git_off_t's Prefer `off64_t` to `git_off_t` internally for visibility.
Edward Thomson 6460e8ab 2019-06-23T18:13:29 internal: use off64_t instead of git_off_t Prefer `off64_t` internally.
Edward Thomson 8be12026 2019-06-23T17:09:22 mmap: use a 64-bit signed type `off64_t` for mmap Prefer `off64_t` to `git_off_t` for internal visibility.
Edward Thomson 7e1cc296 2019-11-25T13:17:42 mmap: remove unnecessary assertion 64 bit types are always 64 bit.
Edward Thomson c863b3c8 2019-11-24T16:49:23 ci: enable the VALGRIND flag on builds
Edward Thomson cb77423f 2019-11-24T16:22:31 valgrind: add valgrind hints in OpenSSL Provide usage hints to valgrind. We trust the data coming back from OpenSSL to have been properly initialized. (And if it has not, it's an OpenSSL bug, not a libgit2 bug.) We previously took the `VALGRIND` option to CMake as a hint to disable mmap. Remove that; it's broken. Now use it to pass on the `VALGRIND` definition so that sources can provide valgrind hints.
Edward Thomson 2ad3eb3e 2019-11-24T15:59:26 valgrind: add suppressions for undefined use valgrind will warn that OpenSSL will use undefined data in connect/read when talking to certain other TLS stacks. Thankfully, this only seems to occur when gcc is the compiler, so hopefully valgrind is just misunderstanding an optimization. Regardless, suppress this warning.
Edward Thomson 0005c77a 2019-11-24T15:49:49 test: add an azure repos test We currently talk to Azure Repos for executing an online test (online::clone::path_whitespace). Add a simpler test to talk to Azure Repos to make it obvious that strange test failures are not likely the whitespace in the path, but actually a function of talking to Azure Repos itself.
Edward Thomson b8e00b98 2019-11-23T21:17:15 ci: cache docker layers Our docker builds are getting expensive, let's cache some of this.
Edward Thomson 6df3ec4a 2019-11-23T21:14:32 valgrind: suppress libssh2_rsa_sha1_sign leaks
Edward Thomson c64b7aaa 2019-11-23T20:38:30 ci: build our own valgrind The valgrind in the PPA is broken and ignores `--exit-errorcode`. Build and install our own.
Edward Thomson 7adc32d5 2019-11-23T13:02:29 valgrind: suppress kexinit leaks
Edward Thomson fd831275 2019-11-23T12:40:46 ci: build shared libssh2
Edward Thomson 84807884 2019-11-23T12:40:02 ci: break dockerfile into stages Use a multi-stage docker build so that we can cache early stages and not need to download the apt-provided dependencies during every build (when only later stages change).
Edward Thomson 7a3d04dc 2019-11-23T12:14:23 ci: don't delete the apt cache Deleting the apt cache can be helpful for reducing the size of a container, but since we don't push it anywhere, it only hinders our ability to debug problems while working on the container. Keep it.
Edward Thomson f592c737 2019-11-23T11:55:50 ci: don't install libssh2 since we build it
Edward Thomson 5dc1be8d 2019-11-23T11:25:56 valgrind: suppress uninitialized reads in libcrypto libcrypto will read uninitialized memory as entropy. Suppress warnings from this behavior.
Edward Thomson 767990e9 2019-11-23T11:25:38 ci: show distribution information The lsb-release command is missing on our images; just show the information from the file instead of relying on it.
Edward Thomson 91ba65af 2019-11-23T10:58:38 ci: provide a default for xcode generator Provide a sane default for `CMAKE_GENERATOR` in the build script so that it can be invoked without having to set that in the environment.
Edward Thomson f94c9276 2019-10-27T22:20:38 example: use `git_object_size_t` for object size
Edward Thomson 4dffa295 2019-06-23T18:09:00 blame: use a size_t for the buffer
Edward Thomson 6c13cf6d 2019-11-22T15:18:54 filestamp: use `uint64_t` for object size Instead of using a signed type (`off_t`) use an unsigned `uint64_t` for the size of the files.
Edward Thomson fefefd1d 2019-06-23T16:42:14 odb: use `git_object_size_t` for object size Instead of using a signed type (`off_t`) use a new `git_object_size_t` for the sizes of objects.
Edward Thomson fb2198db 2019-06-23T16:23:59 futils_filesize: use `uint64_t` for object size Instead of using a signed type (`off_t`) use `uint64_t` for the maximum size of files.
Edward Thomson 4334b177 2019-06-23T15:43:38 blob: use `git_object_size_t` for object size Instead of using a signed type (`off_t`) use a new `git_object_size_t` for the sizes of objects.
Edward Thomson bed9fc6b 2019-06-23T15:16:47 odb: use `git_object_size_t` for object size Instead of using a signed type (`off_t`) use a new `git_object_size_t` for the sizes of objects.
Edward Thomson 9b04d0be 2019-11-22T15:04:09 types: introduce `git_object_size_t` Introduce `git_object_size_t`, an unsigned type that we can use for the maximum size of git objects.
Anders Borum 48c3f7e1 2019-11-20T11:21:14 ssh: include sha256 host key hash when supported
Gregory Herrero 048e94ad 2019-11-07T14:13:14 patch_parse: correct parsing of patch containing not shown binary data. When not shown binary data is added or removed in a patch, patch parser is currently returning 'error -1 - corrupt git binary header at line 4'. Fix it by correctly handling case where binary data is added/removed. Signed-off-by: Gregory Herrero <gregory.herrero@oracle.com>
Gregory Herrero b921964b 2019-11-07T13:08:51 diff_print: add support for GIT_DIFF_FORMAT_PATCH_ID. Git is generating patch-id using a stripped down version of a patch where hunk header and index information are not present. Signed-off-by: Gregory Herrero <gregory.herrero@oracle.com>
Gregory Herrero accd7848 2019-11-07T13:02:38 diff_print: add a new 'print_index' flag when printing diff. Add a new 'print_index' flag to let the caller decide whether or not 'index <oid>..<oid>' should be printed. Since patch id needs not to have index when hashing a patch, it will be useful soon. Signed-off-by: Gregory Herrero <gregory.herrero@oracle.com>
Edward Thomson 47dd665a 2019-11-16T15:21:56 Merge pull request #5303 from pks-t/pks/patch-path-in-body-only patch_parse: use paths from "---"/"+++" lines for binary patches
Edward Thomson cb6bc6f2 2019-11-16T15:17:54 Merge pull request #5285 from pcpthm/winhttp-308 Follow 308 redirect in WinHTTP transport
Edward Thomson 541b8fc5 2019-11-16T15:12:52 Merge pull request #5302 from tiennou/fix/p_lstat-errno fileops: correct error return on p_lstat failures when mkdir
Patrick Steinhardt de7659cc 2019-11-10T18:44:56 patch_parse: use paths from "---"/"+++" lines for binary patches For some patches, it is not possible to derive the old and new file paths from the patch header's first line, most importantly when they contain spaces. In such a case, we derive both paths from the "---" and "+++" lines, which allow for non-ambiguous parsing. We fail to use these paths when parsing binary patches without data, though, as we always expect the header paths to be filled in. Fix this by using the "---"/"+++" paths by default and only fall back to header paths if they aren't set. If neither of those paths are set, we just return an error. Add two tests to verify this behaviour, one of which would have previously caused a segfault.
Etienne Samson 0c2b0206 2019-11-09T09:41:13 fileops: correct error return on p_lstat failures when mkdir IIRC I got a strange return once from lstat, which translated in a weird error class/message being reported. As a safety measure, enforce a -1 return in that case.
Edward Thomson 01ea911b 2019-11-06T06:04:55 Merge pull request #5299 from pks-t/pks/config-mem-snapshots config_mem: implement support for snapshots
Edward Thomson a3d8a437 2019-11-06T06:04:37 Merge pull request #5298 from pks-t/pks/patch-whitespace-only-paths patch_parse: fix segfault when header path contains whitespace only
Etienne Samson fe42557a 2019-11-06T11:08:52 examples: buff up rev-list by adding OID support This allows the example to be used as a quick revwalk test harness.
Etienne Samson 313908f9 2019-11-06T11:08:49 examples: normalize decls and usage of options structs
Etienne Samson 4a4ad2bc 2019-11-06T11:08:45 examples: add comments to add.c
Etienne Samson d4a593ef 2019-11-06T11:17:52 examples: modernize add code
Etienne Samson c9a09b91 2019-11-06T11:16:47 examples: extract argument conversion helper
Etienne Samson 204a464f 2019-11-06T11:08:39 examples: fixup for-each-ref style
Etienne Samson c924f36a 2019-11-06T11:08:35 examples: keep track of whether we processed a "--" arg
Etienne Samson 025a9357 2019-11-06T11:08:30 examples: move "args" to its own header
Etienne Samson 745ccc8a 2019-11-06T11:08:26 examples: remove duplicate includes from common.c
Etienne Samson cd5e33fb 2019-11-06T11:08:23 global: DRY includes of assert.h
Etienne Samson 882220bf 2019-11-06T11:08:19 examples: add missing include barriers
Etienne Samson 4867523e 2019-11-06T11:08:15 examples: add *.h files to IDEs
Patrick Steinhardt 146e5bf7 2019-11-06T07:27:35 config_mem: implement support for snapshots Similar as in commit dadbb33b6 (Fix crash if snapshotting a config_snapshot, 2019-11-01), let's implement snapshots for in-memory configuration entries. As this deletes more code than it adds, it doesn't make any sense to not allow for this and allows users to treat config backends mostly the same.
Patrick Steinhardt de543e29 2019-11-05T22:44:27 patch_parse: fix segfault when header path contains whitespace only When parsing header paths from a patch, we reject any patches with empty paths as malformed patches. We perform the check whether a path is empty before sanitizing it, though, which may lead to a path becoming empty after the check, e.g. if we have trimmed whitespace. This may lead to a segfault later when any part of our patching logic actually references such a path, which may then be a `NULL` pointer. Fix the issue by performing the check after sanitizing. Add tests to catch the issue as they would have produced a segfault previosuly.
Patrick Steinhardt b7dcea04 2019-09-26T15:06:12 config_entries: micro-optimize storage of multivars Multivars are configuration entries that have many values for the same name; we can thus micro-optimize this case by just retaining the name of the first configuration entry and freeing all the others, letting them point to the string of the first entry. The attached test case is an extreme example that demonstrates this. It contains a section name that is approximately 500kB in size with 20.000 entries "a=b". Without the optimization, this would require at least 20000*500kB bytes, which is around 10GB. With this patch, it only requires 500kB+20000*1B=20500kB. The obvious culprit here is the section header, which we repeatedly include in each of the configuration entry's names. This makes it very easier for an adversary to provide a small configuration file that disproportionally blows up in memory during processing and is thus a feasible way for a denial-of-service attack. Unfortunately, we cannot fix the root cause by e.g. having a separate "section" field that may easily be deduplicated due to the `git_config_entry` structure being part of our public API. So this micro-optimization is the best we can do for now.
Patrick Steinhardt 62320860 2019-09-26T14:43:19 config_entries: only keep track of a single entry list Whenever adding a configuration entry to the config entries structure, we allocate two list heads: - The first list head is added to the global list of config entries in order to be able to iterate over configuration entries in the order they were originally added. - The second list head is added to the map of entries in order to efficiently look up an entry by its name. If no entry with the same name exists in the map, then we add the new entry to the map directly. Otherwise, we append the new entry's list head to the pre-existing entry's list in order to keep track of multivars. While the former usecase is perfectly sound, the second usecase can be optimized. The only reason why we keep track of multivar entries in another separate list is to be able to determine whether an entry is unique or not by seeing whether its `next` pointer is set. So we keep track of a complete list of multivar entries just to have a single bit of information of whether it has other multivar entries with the same entry name. We can completely get rid of this secondary list by just adding a `first` field to the list structure itself. When executing `git_config_entries_append`, we will then simply check whether the configuration map already has an entry with the same name -- if so, we will set the `first` to zero to indicate that it is not the initial entry anymore. Instead of a second list head in the map, we can thus now directly store the list head of the first global list inside of the map and just refer to that bit. Note that the more obvious solution would be to store a `unique` field instead of a `first` field. But as we will only ever inspect the `first` field of the _last_ entry that has been moved into the map, these are semantically equivalent in that case. Having a `first` field also allows for a minor optimization: for multivar values, we can free the `name` field of all entries that are _not_ first and have them point to the name of the first entry instead.
Patrick Steinhardt 8a88701e 2019-09-26T13:37:18 config_entries: mark local functions as static Some functions which are only used in "config_entries.c" are not marked as static, which is being fixed by this very commit.
Patrick Steinhardt 5d773a18 2019-11-05T13:04:10 Merge pull request #5282 from pks-t/pks/config-file-iterator-race config_file: fix race when creating an iterator
Patrick Steinhardt 56b203a5 2019-10-24T12:20:27 config_file: keep reference to config entries when creating iterator When creating a configuration file iterator, then we first refresh the backend and then afterwards duplicate all refreshed configuration entries into the iterator in order to avoid seeing any concurrent modifications of the entries while iterating. The duplication of entries is not guarded, though, as we do not increase the refcount of the entries that we duplicate right now. This opens us up for a race, as another thread may concurrently refresh the repository configuration and thus swap out the current set of entries. As we didn't increase the refcount, this may lead to the entries being free'd while we iterate over them in the first thread. Fix the issue by properly handling the lifecycle of the backend's entries via `config_file_entries_take` and `git_config_entries_free`, respectively.
Patrick Steinhardt 0927156a 2019-10-24T12:32:11 config_file: refactor taking entries ref to return an error code The function to take a reference to the config file's config entries currently returns the reference via return value. Due to this, it's harder than necessary to integrate into our typical coding style, as one needs to make sure that a proper error code is set before erroring out from the caller. This bites us in `config_file_delete`, where we call `goto out` directly when `config_file_entries_take` returns `NULL`, but we actually forget to set up the error code and thus return success. Fix the issue by refactoring the function to return an error code and pass the reference via an out-pointer.
Patrick Steinhardt db301087 2019-10-24T12:17:02 config_file: remove unused includes
Patrick Steinhardt c2749849 2019-10-24T12:00:11 config_file: rename function names As with the predecessing commit, this commit renames backend functions of the configuration file backend. This helps to clearly separate functionality and also to be able to see from backtraces which backend is currently in use.
Patrick Steinhardt b30b04a9 2019-11-05T12:34:14 config_snapshot: rename function names The configuration snapshot backend has been extracted from the old files backend back in 2bff84ba4 (config_file: separate out read-only backend, 2019-07-26). To keep code churn manageable, the local functions weren't renamed yet and thus still have references to the old diskfile backend. Rename them accordingly to make them easier to understand.
Patrick Steinhardt 82d7a114 2019-11-05T11:18:14 Merge pull request #5293 from csware/config_snapshot-snapshot Fix crash if snapshotting a config_snapshot
Patrick Steinhardt 45c8d3f4 2019-11-05T11:13:34 Merge pull request #5295 from romkatv/fix-diff-res fix a bug introduced in 8a23597b
romkatv 1886478d 2019-11-05T07:45:11 fix a bug introduced in 8a23597b
Edward Thomson bf2911d7 2019-11-02T07:30:32 Merge pull request #5275 from pks-t/pks/reflogs-with-newlines reflogs: fix behaviour around reflogs with newlines
Sven Strickroth dadbb33b 2019-11-01T18:55:54 Fix crash if snapshotting a config_snapshot Signed-off-by: Sven Strickroth <email@cs-ware.de>
Edward Thomson d5017a14 2019-11-01T07:00:16 Merge pull request #5289 from libgit2/cmn/create-with-signature-verification commit: verify objects exist in git_commit_with_signature
Carlos Martín Nieto 718f24ad 2019-10-30T20:39:03 commit: verify objects exist in git_commit_with_signature There can be a significant difference between the system where we created the buffer (if at all) and when the caller provides us with the contents of a commit. Verify that the commit we are being asked to create references objects which do exist in the target repository.
Carlos Martín Nieto 0974e02f 2019-10-30T20:35:48 commit: add failing tests for object checking for git_commit_with_signature There can be a significant difference between the system where we created the buffer (if at all) and when the caller provides us with the contents of a commit. Provide some test cases (we have to adapt the existing ones because they refer to trees and commits which do not exist).