git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 1/3] revision: complicated pathspecs disable filters

From
Jakub Narębski <jnareb@gmail.com>
Date
Apr 15, 2020, 22:18 UTC
Message-ID
<CANQwDwdcM-hc+Nyc0nBnp79W0BuH2PfdgM6WLqET3sPn1GYc-A@mail.gmail.com>
In-Reply-To
<99e0ae2c-6b65-24e4-3d2b-1dff619a5daa@gmail.com>

On Wed, 15 Apr 2020 at 20:37, Derrick Stolee <stolee@gmail.com> wrote: [...]

Show 33 quoted lines
> -->8--
> From 89beb9598daabb19e3c896bbceeb0fc1b9ccc6ca Mon Sep 17 00:00:00 2001
> From: Derrick Stolee <dstolee@microsoft.com>
> Date: Wed, 15 Apr 2020 18:04:25 +0000
> Subject: [PATCH] bloom: compute all Bloom hashes from lowercase
>
> The changed-path Bloom filters currently hash path strings using
> the exact string for the path. This makes it difficult* to use the
> filters when restricting to case-insensitive pathspecs.
>
> * I say "difficult" because it is possible to generate all 2^n
>   options for the case of a path and test them all, but this is
>   a bad idea and should not be done. "Impossible" is an appropriate
>   alternative.
>
> THIS IS A BREAKING CHANGE. Commit-graph files with changed-path
> Bloom filters computed by a previous commit will not be compatible
> with the filters computed in this commit, nor will we get correct
> results when testing across these incompatible versions. Normally,
> this would be a completely unacceptable change, but the filters
> have not been released and hence are still possible to update
> before release.
>
> TODO: If we decide to move in this direction, then the following
> steps should be done (and some of them should be done anyway):
>
> * We need to document the Bloom filter format to specify exactly
>   how we compute the filter data. The details should be careful
>   enough that someone can reproduce the exact file format without
>   looking at the C code.
>
> * That document would include the tolower() transformation that is
>   being done here.

Why not modify the BDAT chunk to include version of case folding transformation or other collation algorithm (other transformation).that is done prior to computing the Bloom filter key? Though that might be unnecessary flexibility...

For example the value of 0x00 in such field of BDAT chunk header would mean no transformation, while the value of 0x01 would mean per-character tolower() or Unicode equivalent of it.

Best,
-- 
Jakub Narębski
Previous: Taylor BlauNext: Taylor Blau
Message 12 of 48 in “Integrate changed-path Bloom filters with 'git blame'”
  1. 0/3 Integrate changed-path Bloom filters with 'git blame'Derrick Stolee via GitGitGadget, Apr 11, 2020
  2. 1/3 revision: complicated pathspecs disable filtersDerrick Stolee via GitGitGadget, Apr 11, 2020
  3. Junio C HamanoApr 11, 2020
  4. Derrick StoleeApr 13, 2020
  5. Junio C HamanoApr 14, 2020
  6. Derrick StoleeApr 15, 2020
  7. Derrick StoleeApr 15, 2020
  8. Junio C HamanoApr 15, 2020
  9. Junio C HamanoApr 15, 2020
  10. Junio C HamanoApr 15, 2020
  11. Taylor BlauApr 16, 2020
  12. Jakub NarębskiApr 15, 2020
  13. Taylor BlauApr 16, 2020
  14. Derrick StoleeApr 16, 2020
  15. Taylor BlauApr 16, 2020
  16. Junio C HamanoApr 16, 2020
  17. Taylor BlauApr 12, 2020
  18. Junio C HamanoApr 12, 2020
  19. Taylor BlauApr 13, 2020
  20. Derrick StoleeApr 13, 2020
  21. 2/3 commit: write commit-graph with bloom filtersDerrick Stolee via GitGitGadget, Apr 11, 2020
  22. Junio C HamanoApr 11, 2020
  23. Taylor BlauApr 12, 2020
  24. Derrick StoleeApr 13, 2020
  25. Junio C HamanoApr 13, 2020
  26. 3/3 blame: use changed-path Bloom filtersDerrick Stolee via GitGitGadget, Apr 11, 2020
  27. Junio C HamanoApr 11, 2020
  28. Eric SunshineApr 12, 2020
  29. Junio C HamanoApr 11, 2020
  30. 0/4 Integrate changed-path Bloom filters with 'git blame'Derrick Stolee via GitGitGadget, Apr 13, 2020
  31. 1/4 revision: complicated pathspecs disable filtersDerrick Stolee via GitGitGadget, Apr 13, 2020
  32. Taylor BlauApr 13, 2020
  33. Junio C HamanoApr 13, 2020
  34. 2/4 commit: write commit-graph with Bloom filtersDerrick Stolee via GitGitGadget, Apr 13, 2020
  35. Taylor BlauApr 13, 2020
  36. Junio C HamanoApr 13, 2020
  37. Derrick StoleeApr 14, 2020
  38. Junio C HamanoApr 14, 2020
  39. Derrick StoleeApr 14, 2020
  40. Taylor BlauApr 15, 2020
  41. 3/4 commit-graph: write commit-graph in more testsDerrick Stolee via GitGitGadget, Apr 13, 2020
  42. 4/4 blame: use changed-path Bloom filtersDerrick Stolee via GitGitGadget, Apr 13, 2020
  43. Taylor BlauApr 13, 2020
  44. 0/3 Integrate changed-path Bloom filters with 'git blame'Derrick Stolee via GitGitGadget, Apr 16, 2020
  45. 1/3 revision: complicated pathspecs disable filtersDerrick Stolee via GitGitGadget, Apr 16, 2020
  46. SZEDER GáborJun 7, 2020
  47. 2/3 tests: write commit-graph with Bloom filtersDerrick Stolee via GitGitGadget, Apr 16, 2020
  48. 3/3 blame: use changed-path Bloom filtersDerrick Stolee via GitGitGadget, Apr 16, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.