libgit2 / libgit2/pygit2

algos to sort the entries:readme-edits

Open
#1,006 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
1.7k
Forks
408
Avg merge
2d 57m
Merged PRs (30d)
7

Description

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:

https://github.com/versmisse/libgit2/commit/8ee19a25ab4b54ff583bb46093610db0f53d2ab5

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).

Originally posted by @versmisse in https://github.com/libgit2/libgit2/issues/127#issuecomment-1038775

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with git_tree.entries, entry_search_cmp, entry_sort_cmp, and the git_vector_bsearch2 calls described in the issue. Compare the linked patch and determine a consistent search and sorting strategy for git_tree_entry_byname and the other bsearch2 uses; done means the entry lookup behavior is correct without changing a private member as a workaround.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
devtools
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.