git_tree_entry_byname fails apparently because of wrong sort order (in some cases)

git_tree_entry_byname returns NULL when it should not in some specific cases. Apparently
this is because the sort order of the tree is wrong, for instance with libgit2, within the 'include' folder, the entries are ordered this way:

git2.h
git2

While it should be the inverse, first the shortest string. And then bsearch fails (in function git_vector_bsearch2).

Below a test program that reproduces the problem. It prints "git2.h not found" while it should print "git2.h found".

#include <git2.h>
#include <stdio.h>

#define REPO "/home/jdavid/sandboxes/libgit2/.git"
#define TREE "693753506198e2d7832475975f6dc5ada3a502f3"
#define NAME "git2.h"

void main()
{
    int err;
    git_repository *repo;
    git_oid tree_id;
    git_object *tree;
    const git_tree_entry *entry;

    err = git_repository_open(&repo, REPO);
    err = git_oid_mkstr(&tree_id, TREE);
    err = git_object_lookup(&tree, repo, &tree_id, GIT_OBJ_TREE);
    entry = git_tree_entry_byname((git_tree*)tree, NAME);
    printf("%s %s\n", NAME, (entry == NULL ? "not found" : "found"));
}

I found the problem: git_tree.entries uses 2 different algos to sort the entries:

entry_search_cmp and entry_sort_cmp
entry_search_cmp makes an alphabetic sort, but entry_sort_cmp is more sophisticated (directories and files are not sorted the same way).

So i see 3 solutions:
1- We need to sort the list alphabetically before make the search (problem: git_vector_bsearch2 makes a sort)
2- We split entry_search_cmp into 2 functions: entry_search_file_cmp and entry_search_dir_cmp, we use gitfo_cmp_path and we search for a file and after for a directory.
3- Maybe we can always (everywhere) use an alphabetic sort???
4- An other better solution, ...

I made this patch:

versmisse@8ee19a2

to test the solution and it works fine with git_tree_entry_byname. But it is not very clean (i change a private member (_cmp)) and incomplete (we must find a solution for all bsearch2 in the code).

Test for the bug libgit2#127

also i encounterd this problem. i',m looking forward to fix that :)

I stumbled onto this also. I created a test case for this before kind souls pointed me towards this issue. Is anybody working on this? The fix in versmisse/libgit2@8ee19a2 corrects my test case sakari/libgit2@8af9b61. That also fixes my original failing case in haskell.

There is still one case using insert, remove and entry_byname which fails even with versmisses commit -- or then it is the late hour... if it turns out to be a real failure I turn it in to a test case for libgit2

Test for the bug libgit2#127

yes the other test failure I got is a result of the same problem but now with git_treebuilder_remove (test sakari/libgit2@30c1d26).

I had totally missed this. Fixing asap.

What's the status of this?

Last I heard about this was that tanoku was going to fix this asap. I
did not start work on it due to this. But maybe I should have as I
seem to recall that the problem is still present in 0.13 release and
it really bothers me.

Sakari

On Tue, Jul 12, 2011 at 6:45 PM, carlosmn
reply@reply.github.com
wrote:

What's the status of this?

Reply to this email directly or view it on GitHub:
#127 (comment)

Working on this now.

Paging everyone: does this fix make sense at all? I think I have trascended reality and the bytes no longer make sense to me.

761aa2a

libgit2 v0.14.0, "watermelon wheat"

Not yet fixed. A user has found a broken case with the Linux kernel Git repo, see libgit2/pygit2#38

I have translated it to C. Here is the test program:

#include <git2.h>
#include <stdio.h>

#define REPO "/home/jdavid/sandboxes/linux/.git"
#define TREE "bc18386d999a4f652df5dd61bf0ed5c38e698085"
#define NAME "i2c"

void main()
{
    int err;
    git_repository *repo;
    git_oid tree_id;
    git_object *tree;
    const git_tree_entry *entry;

    err = git_repository_open(&repo, REPO);
    err = git_oid_fromstr(&tree_id, TREE);
    err = git_object_lookup(&tree, repo, &tree_id, GIT_OBJ_TREE);
    entry = git_tree_entry_byname((git_tree*)tree, NAME);
    printf("%s %s\n", NAME, (entry == NULL ? "not found" : "found"));
}

How was the jump? :-)

@itroot

Alright, after some more thought, I decided to go with @itroot's first solution: letting the library know what kind of object we're looking for. Instead of adding a explicit is_folder argument to the API, I've changed the search callback internally: if you're looking for an entry called i2c, and that entry is a folder, then just call git_tree_entry_byname(tree, "i2c/"). That should cut it.

I'm looking for some feedback, i.e. cases where you don't know beforehand if the entry you're looking for is a folder or a normal file. I think this would be extremely rare, and the only way to handle this would be the two binary searches, or probably a single linear search, which at first strikes me as more optimal on 90% of the cases...

I'm looking for some feedback, i.e. cases where you don't know beforehand if the entry you're looking for is a folder or a normal file. I think this would be extremely rare, and the only way to handle this would be the two binary searches, or probably a single linear search, which at first strikes me as more optimal on 90% of the cases...

I don't think that's so rare. I have that scenario right now and my workaround for this bug does a linear search when git_tree_entry_byname() doesn't find anything.

Can you give me some background on what are you trying to accomplish?

I'm writing an scm-independent library that uses libgit and the path strings are provided by the caller. My api does not require the user to supply an entity type.

Use case, Git:

$ git log foobar

That's the input provided by the user, an it must work whether foobar is a directory or a file.

The question is whether libgi2 should provide a function for this or whether it should be implemented at a higher level. In my opinion it's be better if there is a libgit2 function, otherwise we will find an implementation in every binding (rugged, pygit2, etc.)

Regarding implementation, I prefer two binary searches over a linear search, because it scales. Then it is about testing, you could for instance check the length of the tree object and choose one strategy or the other based on that.

What about something like this :

/* the caller knows it is a folder */
git_tree_entry_byname(tree, "foobar", GIT_DIR);
/* the caller knows it is a file */
git_tree_entry_byname(tree, "foobar", GIT_FILE);
/* the caller does not know */
git_tree_entry_byname(tree, "foobar", GIT_DIR | GIT_FILE);

So if the caller knows you get the best performance. If the caller does not know, it still works.

@erikvanzijst

Just would like to add. A linear search would be enough for me today, like @erikvanzijst that's my current workaround. The important thing is that it works.

So if the caller knows you get the best performance. If the caller does not know, it still works.

Often, the caller can't know that a particular path refers to a file. Not even if they look at the working tree. They can have a good idea, but not know. If the user says they're interested in "foobar/", you know they're only interested in a directory called foobar, so it won't match if it's a file, but the user only types "foobar", it needs to match whether it's a file for a directory.

I believe the best solution is to use two linear searches like this:

use the path as-is; return if found
if the path has a trailing slash
- return failure
Otherwise
- try to find a directory with that name.

28c1451

Check out this fix yo. Two-pass binary-linear hybrid. Nebody finding any issues?

@tanoku

Nebody finding any issues?

@tanoku Works very nicely from a binding angle!

The test programs work, bravo!

Most riveting! Looks like we can close this for good then...

Until it breaks again. :)

tree: Fix wrong sort order when querying entries

libgit2 v0.14.0, "watermelon wheat"

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Repository navigation

git_tree_entry_byname fails apparently because of wrong sort order (in some cases) #127

8 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Sunbelt Computer Software

PL/B Language Development and Support

git_tree_entry_byname fails apparently because of wrong sort order (in some cases) #127

Description

Activity

versmisse commented on Apr 21, 2011

chobie commented on May 15, 2011

sakari commented on May 28, 2011

sakari commented on May 30, 2011

vmg commented on Jun 4, 2011

carlosmn commented on Jul 12, 2011

sakari commented on Jul 12, 2011

vmg commented on Jul 13, 2011

vmg commented on Jul 13, 2011

jdavid commented on Aug 5, 2011

8 remaining items

itroot commented on Oct 14, 2011

vmg commented on Oct 18, 2011

erikvanzijst commented on Oct 19, 2011

vmg commented on Oct 19, 2011

erikvanzijst commented on Oct 19, 2011

jdavid commented on Oct 19, 2011

jdavid commented on Oct 19, 2011

carlosmn commented on Oct 19, 2011

vmg commented on Oct 20, 2011

nulltoken commented on Oct 20, 2011

jdavid commented on Oct 20, 2011

vmg commented on Oct 20, 2011

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions