Add some Glossary terms, and extra renormalize information.

This short series looks to add the basics of the reachability bitmap and commit graph phrases to the glossary of terms. While these techniques are well known to their developers, for some, they are just magic phrases.

The first patch [1/4] is to show OBD as an abbreviation to avoid a UNA [0]

Patch [2/4] provides a basic statement for the Commit-Graph's purpose.

Patch [3/4] provides a similar statement for the reachability bitmaps.

These two patches maybe misses out on some linking information as to the benefits these have and the basics of their heuristic.

Patch [4/4] follows up on a bug report about the lack of idempotence for the `--renormalise' command. See commit message for details.

[0] UNA Un-Named Abbreviation.

Philip Oakley (4):
glossary: add Object DataBase (ODB) abbreviation
glossary: add commit graph description
glossary: add reachability bitmap description doc add: renormalize is not idempotent for CRCRLF

 Documentation/git-add.txt          |  3 ++-
 Documentation/glossary-content.txt | 15 ++++++++++++++-
 2 files changed, 16 insertions(+), 2 deletions(-)

base-commit: 30cc8d0f147546d4dd77bf497f4dec51e7265bd8
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1282%2FPhilipOakley%2FGlossary_terms-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1282/PhilipOakley/Glossary_terms-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1282

gitgitgadget

From: Philip Oakley <[email protected]>

ODB abbreviation is used in the technical section without expansion. Show the abbreviation in the Glossary.

---
 Documentation/glossary-content.txt | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index aa2f41f5e70..f3342a5ab69 100644
@@ -257,7 +257,7 @@ This commit is referred to as a "merge commit", or sometimes just a
 	<<def_SHA1,SHA-1>> of its contents. Consequently, an
 	object cannot be changed.
 
-[[def_object_database]]object database::
+[[def_object_database]]object database (ODB)::
 	Stores a set of "objects", and an individual <<def_object,object>> is
 	identified by its <<def_object_name,object name>>. The objects usually
 	live in `$GIT_DIR/objects/`.

gitgitgadget

From: Philip Oakley <[email protected]>

---
 Documentation/glossary-content.txt | 7 +++++++
 1 file changed, 7 insertions(+)

index f3342a5ab69..a9e69949a4e 100644
@@ -75,6 +75,13 @@ state in the Git history, by creating a new commit representing the current
 state of the <<def_index,index>> and advancing <<def_HEAD,HEAD>>
 to point at the new commit.
 
+[[def_commit_graph]]commit graph::
+	The commit-graph file is a supplemental data structure that
+	accelerates commit graph walks. The existing Object Data Base (ODB)
+	is the definitive commit graph. The "commit-graph" file is stored
+	either in the .git/objects/info directory or in the info directory
+	of an alternate object database.
+
 [[def_commit_object]]commit object::
 	An <<def_object,object>> which contains the information about a
 	particular <<def_revision,revision>>, such as <<def_parent,parents>>, committer,

gitgitgadget

From: Philip Oakley <[email protected]>

---
 Documentation/glossary-content.txt | 6 ++++++
 1 file changed, 6 insertions(+)

index a9e69949a4e..6302df90563 100644
@@ -500,6 +500,12 @@ exclude;;
 	<<def_tree_object,trees>> to the trees or <<def_blob_object,blobs>>
 	that they contain.
 
+[[def_reachability_bitmap]]reachability bitmaps::
+	Reachability bitmaps store information about the set of objects in
+	a packfile, or a multi-pack index (MIDX). A repository may have at
+	most one bitmap. The bitmap may belong to either one pack, or the
+	repository's multi-pack index (if it exists).
+
 [[def_rebase]]rebase::
 	To reapply a series of changes from a <<def_branch,branch>> to a
 	different base, and reset the <<def_head,head>> of that branch

gitgitgadget

From: Philip Oakley <[email protected]>

Bug report
https://lore.kernel.org/git/AM0PR02MB56357CC96B702244F3271014E8DC9@AM0PR02MB5635.eurprd02.prod.outlook.com/
noted that a file containing /r/r/n needed renormalising twice.

This is by design. Lone CR characters, not paired with an LF, are left unchanged. Note the lack of idempotentness of the "clean" filter in the documentation.

Renormalize was introduced at 9472935d81e (add: introduce "--renormalize", Torsten Bögershausen, 2017-11-16)

---
 Documentation/git-add.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index 11eb70f16c7..c4a5ad11a6b 100644
@@ -188,7 +188,8 @@ for "git add --no-all <pathspec>...", i.e. ignored removed files.
 	forcibly add them again to the index.  This is useful after
 	changing `core.autocrlf` configuration or the `text` attribute
 	in order to correct files added with wrong CRLF/LF line endings.
-	This option implies `-u`.
+	This option implies `-u`. Lone CR characters are untouched, so
+	cleaning not idempotent. A CRCRLF sequence cleans to CRLF.
 
 --chmod=(+|-)x::
 	Override the executable bit of the added files.  The executable

gitgitgadget

Did you mean backslash, not forward?

OK.

Does this need to be said "HERE", rather than leaving it to run "git blame" for those who became curious?

Avoiding unnecessary TLA is even better than avoiding. As I didn't see in the other three patches that we need to use the OBD acronym, perhaps we can omit this step?

This is all fine.

The clean filter is idempotent, I would claim, see below. You can run it, and re-run, and re-run, there will no other changes. CRLF in the worktree will become LF in the repo,
'lone CR' stay as they are.
In that sense, CRCRLF in the worktree will become CRLF in the repo. You can the renormalize again and again.

The "trick" is that the user has to decide what CRCRLF mean and what should happen in the repo:
CRCRLF in the worktree becomes one line ending (one LF in the repo) or
CRCRLF in the worktree becomes two line endings ( LFLF in the repo)

For a) you can use dos2unix twice.
Or run git add --renormalize followed by
rm git.bdf
git restore .

The thing is that we used a combination of different commands

$ git add --renormalize .
$ git commit -m "Renormalize bdf.txt"
$ rm git.bdf
$ git restore .
$ git add --renormalize .
$ git commit -m "Renormalize a second time bdf.txt"

... to clean up this very situation.

And, if CRCRLF should have become LFLF instead ? Probably a python script is needed to fix this.
(or some other script/program in the language of your choice)

We could argue that
git add --renormalize is idempotent, but a series of carefully crafted commands is not.
In short, what is missing is the documentation how CRCRLF is handled by Git.

Hi Junio,

This came from seeing ODB in a couple of tech docs (commit-graph and parallel-checkout) and an 'odb' option in pack-redundant, which I should have noted in the commit message.

I'll update the commit message to clarify that we are using that TLA, though we aren't always consistent in our distinctions between concepts and implementation in many places (e.g. Object Store vs Repository; Staging area..; etc.)

TLAs, UNAs, etc. have been a bug-bear of mine from doing large engineering collaborations.

--
Philip

(for completeness;-)
ODB Object Data Base.
TLA Three Letter Abbreviation.
UNA Un-Named Abbreviation.

Hi Junio,

I probably over-shortened the original text I was summarising (technical/commit-graph.txt intro).

.. of that graph. *nod*

I wasn't particularly thinking of that aspect .. Perhaps more that it accelerates commit graph walks..

I wanted to keepseparate from the graph file definition, the rather fuzzy relationship between the overall ODB (staging area, and loads of other stuff), and the way the DAG is generated, which also needs the selected refs to start the traverse..

In a wider context, it's not clear to me just how the commit graph file content is chosen relative to the full depth DAG from all local refs. The reachability bit maps have a similar info gap.

--
Philip

[sorry for erratic responses - currently isolating with covid]

Correct. Too many years of Windows.

It was a misguided reminder to cc Torsten about his recollection of the CRCRLF issue. I'll remove it. I see Torsten has also commented.

'^' It took me three re-reads to see my mistyping as my head knew what I'd meant to write, I've marked above as a note to self.
Aside: Are there any guides / suggestions / how-to's for on-line reviewing that you can recommend o

Ok. It's mainly used in the test directory, and fsmonitor.h, but not in the user docs.

Torsten had a shorter suggestion I'll also look at.

Philip

Sorry, but I do not know of any good "trick" to fight against our common tendency to easily miss trivial typoes and thinkos in what we ourselves wrote. We can be surprisingly blind to what a colleague can spot immediately, and that is why it helps to have a thorough read-through by a reviewer with fresh eyes. When I was a more prolific contributor, I sometimes tried to read aloud what I wrote to myself, both docs and code, and caught silly mistakes before sending them out to the list, but I do not recommend it to others.

Hi Tortsen,
Thanks for the reply and comments.

I'd disagree, on the basis that any second 'idempotent' cleaning should not change the file content at all. The need for a second clean was the surprise the user had.

So  the output isn't normalised, and warning messages ensue (if enabled, etc)

.. for which they should be forewarned of the issue.
In this case it was a large repository transfer of legacy data, so little knowledge of how the double CRs occured, but it was a real issue for them.

*nod*

That is probably sufficient. It drops the awkward 'idempotent'. And indicates this edge case, though doesn't highlight that the resultant CRLF still leaves the file only partially renormalised.

I'll reword.

Thanks. There does appear to be a lack of literature or articles in this area of on-list reviewing

I've not even seen an list of snippets collated from email advice. Other than the email etiquette's starter for ten on don't top post ;-)

--
Philip

It's been a few weeks since the last activity on this topic. Anything you guys need unblocked to move forward?

Thanks.

Not from my point of view. My understanding is, that the short version is OK for everybody:

This option implies -u. Lone CR characters are untouched. CRCRLF cleans to CRLF.

Is it OK to ask you for a local ammend to push this further ?

I've unfortunately had some family issue which prevented me doing any work.

If I haven't managed anything by the end of the week. I'd be happy if others took it forward.

I hope everything will be well on your side.

Thanks for letting us know.

That is sad to here. I hope that things are getting better in one way or another.

I can certainly have a look, after the weekend, and continue your work.

This was [PATCH 4/4] 'doc add: renormalize is not idempotent for CRCRLF' of a GitGitGadget series, which was split off into its own branch po/doc-add-renormalize

Since V1, remove the use of 'idempotent' which is unknown to many. Instead clarify the special case.

Philip Oakley (1):
doc add: renormalize is not idempotent for CRCRLF

 Documentation/git-add.txt | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

2.37.1.windows.1

Bug report
https://lore.kernel.org/git/AM0PR02MB56357CC96B702244F3271014E8DC9@AM0PR02MB5635.eurprd02.prod.outlook.com/
noted that a file containing /r/r/n needed renormalising twice.

This is by design. Lone CR characters, not paired with an LF, are left unchanged. Note this limitation of the "clean" filter in the documentation.

Renormalize was introduced at 9472935d81e (add: introduce "--renormalize", Torsten Bögershausen, 2017-11-16)

---
This is V2 of po/doc-add-renormalize, based on commit dc8c8deaa6 (Prepare for 2.36.2, 2022-06-07).
It was [PATCH 4/4] doc add: renormalize is not idempotent for CRCRLF.

git send-email \
    [email protected] \
    [email protected] \
    [email protected] \
    [email protected] \
    [email protected] \
    [email protected] \
    v2-00*
---
 Documentation/git-add.txt | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

index 11eb70f16c..9b37f35654 100644
@@ -188,7 +188,9 @@ for "git add --no-all <pathspec>...", i.e. ignored removed files.
 	forcibly add them again to the index.  This is useful after
 	changing `core.autocrlf` configuration or the `text` attribute
 	in order to correct files added with wrong CRLF/LF line endings.
-	This option implies `-u`.
+	This option implies `-u`. Lone CR characters are untouched, thus
+	while a CRLF cleans to LF, a CRCRLF sequence is only partially
+	cleaned to CRLF.
 
 --chmod=(+|-)x::
 	Override the executable bit of the added files.  The executable

2.37.1.windows.1

[]

I was looking to outline the concept and how, therefore, it is different from the reachability bitmaps, and also from the 'canonical' DAG of Git's commit objects.

I hope to have another go in a couple of weeks time.

Git has an additional "commit graph" capability that supplements the normal commit object's directed acylic graph (DAG). The supplemental commit graph file is designed for speed of access.

Describe the commit graph both from the normative DAG view point and from the commit graph file perspective.

Also, clarify the link between the branch ref and branch tip by linking to the ref glossary entry, matching this commit graph entry.

---
 Documentation/glossary-content.txt | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

index 947ac49606..97050826e5 100644
@@ -20,7 +20,7 @@
 [[def_branch]]branch::
 	A "branch" is a line of development.  The most recent
 	<<def_commit,commit>> on a branch is referred to as the tip of
-	that branch.  The tip of the branch is referenced by a branch
+	that branch.  The tip of the branch is <<def_ref,referenced>> by a branch
 	<<def_head,head>>, which moves forward as additional development
 	is done on the branch.  A single Git
 	<<def_repository,repository>> can track an arbitrary number of

@@ -75,6 +75,21 @@ state in the Git history, by creating a new commit representing the current
 state of the <<def_index,index>> and advancing <<def_HEAD,HEAD>>
 to point at the new commit.
 
+[[def_commit_graph_general]]commit graph concept, representations and usage::
+	A synonym for the <<def_DAG,DAG>> structure formed by
+	the commits in the object database, <<def_ref,referenced>> by branch tips,
+	using their <<def_chain,chain>> of linked commits.
+	This structure is the definitive commit graph. The
+	graph can be represented in other ways, e.g. the
+	<<def_commit_graph_file,commit graph file>>.
+
+[[def_commit_graph_file]]commit graph file::
+	The commit-graph file is a supplemental representation of
+	the <<def_commit_graph_general,commit graph>> which accelerates
+	commit graph walks. The "commit-graph" file is stored
+	either in the .git/objects/info directory or in the info directory
+	of an alternate object database.
+
 [[def_commit_object]]commit object::
 	An <<def_object,object>> which contains the information about a
 	particular <<def_revision,revision>>, such as <<def_parent,parents>>, committer,

2.38.1.windows.1

The abbreviation 'ODB' is used in the technical documentation sections for commit-graph and parallel-checkout, along with an 'odb' option in git-pack-redundant, without expansion.

Use 'object database' in full, in those entries. The text has not been reflowed to keep the changes minimal.

While in the glossary for object terms, add the commonoid abbreviation to its entry.

---
 Documentation/git-pack-redundant.txt          | 2 +-
 Documentation/glossary-content.txt            | 2 +-
 Documentation/technical/commit-graph.txt      | 2 +-
 Documentation/technical/parallel-checkout.txt | 2 +-
 4 files changed, 4 insertions(+), 4 deletions(-)

index ee7034b5e5..1132c73956 100644
@@ -34,7 +34,7 @@ OPTIONS
 
 --alt-odb::
 	Don't require objects present in packs from alternate object
-	directories to be present in local packs.
+	database (odb) directories to be present in local packs.
 
 --verbose::
 	Outputs some statistics to stderr. Has a small performance penalty.

index aa2f41f5e7..947ac49606 100644
@@ -262,7 +262,7 @@ This commit is referred to as a "merge commit", or sometimes just a
 	identified by its <<def_object_name,object name>>. The objects usually
 	live in `$GIT_DIR/objects/`.
 
-[[def_object_identifier]]object identifier::
+[[def_object_identifier]]object identifier (oid)::
 	Synonym for <<def_object_name,object name>>.
 
 [[def_object_name]]object name::

index f05e7bda1a..5a4e1eba8b 100644
@@ -17,7 +17,7 @@ There are two main costs here:
 
 The commit-graph file is a supplemental data structure that accelerates
 commit graph walks. If a user downgrades or disables the 'core.commitGraph'
-config setting, then the existing ODB is sufficient. The file is stored
+config setting, then the existing object database is sufficient. The file is stored
 as "commit-graph" either in the .git/objects/info directory or in the info
 directory of an alternate.
 

index e790258a1a..47c9b6183c 100644
@@ -56,7 +56,7 @@ Rejected Multi-Threaded Solution
 
 The most "straightforward" implementation would be to spread the set of
 to-be-updated cache entries across multiple threads. But due to the
-thread-unsafe functions in the ODB code, we would have to use locks to
+thread-unsafe functions in the object database code, we would have to use locks to
 coordinate the parallel operation. An early prototype of this solution
 showed that the multi-threaded checkout would bring performance
 improvements over the sequential code, but there was still too much lock

2.38.1.windows.1

Describe the purpose of the reachability bitmap.

---
 Documentation/glossary-content.txt | 8 ++++++++
 1 file changed, 8 insertions(+)

index 97050826e5..3d67b452aa 100644
@@ -508,6 +508,14 @@ exclude;;
 	<<def_tree_object,trees>> to the trees or <<def_blob_object,blobs>>
 	that they contain.
 
+[[def_reachability_bitmap]]reachability bitmaps::
+	Reachability bitmaps store information about the
+	<<def_reachable,reachability>> of a selected set of objects in
+	a packfile, or a multi-pack index (MIDX) to speed up object search.
+	A repository may have at
+	most one bitmap. The bitmap may belong to either one pack, or the
+	repository's multi-pack index (if it exists).
+
 [[def_rebase]]rebase::
 	To reapply a series of changes from a <<def_branch,branch>> to a
 	different base, and reset the <<def_head,head>> of that branch

2.38.1.windows.1

was GitGitGadget #1282,
(in reply to <[email protected]>)

This short series looks to add the basics of the reachability bitmap and commit graph phrases to the glossary of terms. While these techniques are well known to their developers, for some, they are just magic phrases.

[V2] .. since V1
Patch 4/4 has been taken upstream independently, and hence dropped here so we're now just [n/3].

Patch 1/3 Dropped the glossary addition in favour of changing the locations that used ODB (Junio's suggestion). Kept the git pack-redundant's --alt-odb but spelt out 'object database' in full in the man page. The only remaining odbs are within goodbye ;-).

While here, add the (oid) abbreviation to its adjacent entry.

Patch 2/3 Split the 'commit-graph' explanation into two parts to distinguish the speed-up option, from Git's core graph concept of object traversal. Included links to existing terms.

Patch 3/3 Added links to existing terms. Statement for the reachability bitmaps.

added cc: for Stolee (commit-graph) and Abhradeep Chakraborty (Bitmaps) review.

[V1] [GGG PR #1282]
https://lore.kernel.org/git/[email protected]/

The first patch [1/4] is to show OBD as an abbreviation to avoid a UNA [0]

Patch [2/4] provides a basic statement for the Commit-Graph's purpose.

Patch [3/4] provides a similar statement for the reachability bitmaps.

These two patches maybe misses out on some linking information as to the benefits these have and the basics of their heuristic.

Patch [4/4] follows up on a bug report about the lack of idempotence for the `--renormalise' command. See commit message for details.

[0] UNA Un-Named Abbreviation.

Philip Oakley (3):
doc: use 'object database' not ODB or abbreviation
glossary: add "commit graph" description
glossary: add reachability bitmap description

 Documentation/git-pack-redundant.txt          |  2 +-
 Documentation/glossary-content.txt            | 27 +++++++++++++++++--
 Documentation/technical/commit-graph.txt      |  2 +-
 Documentation/technical/parallel-checkout.txt |  2 +-
 4 files changed, 28 insertions(+), 5 deletions(-)

Range-diff against v1:
1: 51b55828d5 ! 1: dc0d934b00 glossary: add Object DataBase (ODB) abbreviation
@@ Metadata
Author: Philip Oakley <[email protected]>

## Commit message ##
- glossary: add Object DataBase (ODB) abbreviation
+ doc: use 'object database' not ODB or abbreviation

- ODB abbreviation is used in the technical section without expansion.
- Show the abbreviation in the Glossary.
+ The abbreviation 'ODB' is used in the technical documentation
+ sections for commit-graph and parallel-checkout, along with an
+ 'odb' option in git-pack-redundant, without expansion.
+
+ Use 'object database' in full, in those entries. The text has not
+ been reflowed to keep the changes minimal.
+
+ While in the glossary for object terms, add the commonoid
+ abbreviation to its entry.

- Signed-off-by: Junio C Hamano <[email protected]>
+
+ ## Documentation/git-pack-redundant.txt ## +@@ Documentation/git-pack-redundant.txt: OPTIONS +
+ --alt-odb::
+ Don't require objects present in packs from alternate object
+- directories to be present in local packs.
++ database (odb) directories to be present in local packs.
+
+ --verbose::
+ Outputs some statistics to stderr. Has a small performance penalty.

## Documentation/glossary-content.txt ##
@@ Documentation/glossary-content.txt: This commit is referred to as a "merge commit", or sometimes just a
- <<def_SHA1,SHA-1>> of its contents. Consequently, an
- object cannot be changed.
-
--[[def_object_database]]object database::
-+[[def_object_database]]object database (ODB)::
- Stores a set of "objects", and an individual <<def_object,object>> is
identified by its <<def_object_name,object name>>. The objects usually
live in $GIT_DIR/objects/.
+
+-[[def_object_identifier]]object identifier::
++[[def_object_identifier]]object identifier (oid)::
+ Synonym for <<def_object_name,object name>>.
+
+ [[def_object_name]]object name::
+
+ ## Documentation/technical/commit-graph.txt ##
+@@ Documentation/technical/commit-graph.txt: There are two main costs here:
+
+ The commit-graph file is a supplemental data structure that accelerates
+ commit graph walks. If a user downgrades or disables the 'core.commitGraph'
+-config setting, then the existing ODB is sufficient. The file is stored
++config setting, then the existing object database is sufficient. The file is stored
+ as "commit-graph" either in the .git/objects/info directory or in the info
+ directory of an alternate.
+
+
+ ## Documentation/technical/parallel-checkout.txt ##
+@@ Documentation/technical/parallel-checkout.txt: Rejected Multi-Threaded Solution
+
+ The most "straightforward" implementation would be to spread the set of
+ to-be-updated cache entries across multiple threads. But due to the
+-thread-unsafe functions in the ODB code, we would have to use locks to
++thread-unsafe functions in the object database code, we would have to use locks to
+ coordinate the parallel operation. An early prototype of this solution
+ showed that the multi-threaded checkout would bring performance
+ improvements over the sequential code, but there was still too much lock
2: 6a88bdb7ed ! 2: 77fbf889a5 glossary: add commit graph description
@@ Metadata
Author: Philip Oakley <[email protected]>

## Commit message ##
- glossary: add commit graph description
+ glossary: add "commit graph" description
+
+ Git has an additional "commit graph" capability that supplements the
+ normal commit object's directed acylic graph (DAG). The supplemental
+ commit graph file is designed for speed of access.
+
+ Describe the commit graph both from the normative DAG view point and
+ from the commit graph file perspective.
+
+ Also, clarify the link between the branch ref and branch tip
+ by linking to the ref glossary entry, matching this commit graph
+ entry.

- Signed-off-by: Junio C Hamano <[email protected]>

## Documentation/glossary-content.txt ##
+@@
+ [[def_branch]]branch::
+ A "branch" is a line of development. The most recent
+ <<def_commit,commit>> on a branch is referred to as the tip of
+- that branch. The tip of the branch is referenced by a branch
++ that branch. The tip of the branch is <<def_ref,referenced>> by a branch
+ <<def_head,head>>, which moves forward as additional development
+ is done on the branch. A single Git
+ <<def_repository,repository>> can track an arbitrary number of
@@ Documentation/glossary-content.txt: state in the Git history, by creating a new commit representing the current
state of the <<def_index,index>> and advancing <<def_HEAD,HEAD>>
to point at the new commit.

-+[[def_commit_graph]]commit graph::
-+ The commit-graph file is a supplemental data structure that
-+ accelerates commit graph walks. The existing Object Data Base (ODB)
-+ is the definitive commit graph. The "commit-graph" file is stored
++[[def_commit_graph_general]]commit graph concept, representations and usage::
++ A synonym for the <<def_DAG,DAG>> structure formed by
++ the commits in the object database, <<def_ref,referenced>> by branch tips,
++ using their <<def_chain,chain>> of linked commits.
++ This structure is the definitive commit graph. The
++ graph can be represented in other ways, e.g. the
++ <<def_commit_graph_file,commit graph file>>.
++
++[[def_commit_graph_file]]commit graph file::
++ The commit-graph file is a supplemental representation of
++ the <<def_commit_graph_general,commit graph>> which accelerates
++ commit graph walks. The "commit-graph" file is stored
+ either in the .git/objects/info directory or in the info directory
+ of an alternate object database.
+
3: 564de4c68f ! 3: fde2c58153 glossary: add reachability bitmap description
@@ Metadata
## Commit message ##
glossary: add reachability bitmap description

+ Describe the purpose of the reachability bitmap.
+

- Signed-off-by: Junio C Hamano <[email protected]>

## Documentation/glossary-content.txt ##
@@ Documentation/glossary-content.txt: exclude;;
@@ Documentation/glossary-content.txt: exclude;;
that they contain.

+[[def_reachability_bitmap]]reachability bitmaps::
-+ Reachability bitmaps store information about the set of objects in
-+ a packfile, or a multi-pack index (MIDX). A repository may have at
++ Reachability bitmaps store information about the
++ <<def_reachable,reachability>> of a selected set of objects in
++ a packfile, or a multi-pack index (MIDX) to speed up object search.
++ A repository may have at
+ most one bitmap. The bitmap may belong to either one pack, or the
+ repository's multi-pack index (if it exists).
+

2.38.1.windows.1

They all looked reasonable to me, but as you sensibly Cc'ed folks who worked on the areas the concepts explained in these patches are the most relevant, these patches would benefit from their inputs, so let's hear them first and then advance the patches to 'next'.

Thanks.

Hey Philip,
Glad that you're working on this :)

Sounds good to me. Or Philip's original can be tweaked minimally to say "... may have at most one bitmap file (which stores multiple bitmaps)".

Thanks.

Thanks both. I'll tweak the description in a day or so to allow Stolee to comment if required.
P.

One way to help keep the general term and the file separate is to use different notation. "commit graph" (with a space, no formatting) is the DAG. "commit-graph" (with a dash, code formatting) is the file (and its format).

I added my comments about the commit-graph file, and agree with Abhradeep's suggestions here.

Adding Taylor as a possible reviewer, too.

The one thing I will say is that there can be multiple .bitmap files, but Git will only use one of them. Not sure if that is worth being pedantic about here, though.

We'll need to keep this glossary section in mind in case things change (such as "at most one bitmap file").

Thanks,
-Stolee

That matches my understanding, but "can be" is less of the norm these days, no? "repack -b" would refuse without "-a" so we may have more than one by accident, or am I missing a common scenario that we do perfectly normal things and still end up with multiple?

I agree with you that it probably is a good idea to say there can be, so that the readers do not have to alarmed.

Only one '.bitmap' file (which stores multiple reachability bitmaps) per repository is used in a repository (note. it is not wrong to have more than one). The bitmap file may belong to either one pack, or the repository's multi-pack index (if it exists).

But then the readers who do have more than one would next think "how do I get rid of the ones that are not used? they are wasting my precious disk space". So I also am not sure if it helps to write more. "It is generally true that.." white lie may be better than technical correctness in this case.

True.

Thanks.

I did want to have separate entries to make clear the distinction at this level.

The use of the hyphenation is good, and there are only a few places where that isn't followed, so I'll specifically call out the use of hyphenation, and add a patch to update the few places that used the generic term inappropriately.
Using the code formatting for commit-graph would have been extensive.,

I've used some of that. Thanks.

Philip

I've gone with the phrase "at most one bitmap file in use." here.

The updated series should be sent shortly.

Philip.

The abbreviation 'ODB' is used in the technical documentation sections for commit-graph and parallel-checkout, along with an 'odb' option in git-pack-redundant, without expansion.

Use 'object database' in full, in those entries. The text has not been reflowed to keep the changes minimal.

While in the glossary for object terms, add the commonoid abbreviation to its entry.

---
 Documentation/git-pack-redundant.txt          | 2 +-
 Documentation/glossary-content.txt            | 2 +-
 Documentation/technical/commit-graph.txt      | 2 +-
 Documentation/technical/parallel-checkout.txt | 2 +-
 4 files changed, 4 insertions(+), 4 deletions(-)

index ee7034b5e5..1132c73956 100644
@@ -34,7 +34,7 @@ OPTIONS
 
 --alt-odb::
 	Don't require objects present in packs from alternate object
-	directories to be present in local packs.
+	database (odb) directories to be present in local packs.
 
 --verbose::
 	Outputs some statistics to stderr. Has a small performance penalty.

index aa2f41f5e7..947ac49606 100644
@@ -262,7 +262,7 @@ This commit is referred to as a "merge commit", or sometimes just a
 	identified by its <<def_object_name,object name>>. The objects usually
 	live in `$GIT_DIR/objects/`.
 
-[[def_object_identifier]]object identifier::
+[[def_object_identifier]]object identifier (oid)::
 	Synonym for <<def_object_name,object name>>.
 
 [[def_object_name]]object name::

index 90c9760c23..d2a6a13650 100644
@@ -17,7 +17,7 @@ There are two main costs here:
 
 The commit-graph file is a supplemental data structure that accelerates
 commit graph walks. If a user downgrades or disables the 'core.commitGraph'
-config setting, then the existing ODB is sufficient. The file is stored
+config setting, then the existing object database is sufficient. The file is stored
 as "commit-graph" either in the .git/objects/info directory or in the info
 directory of an alternate.
 

index e790258a1a..47c9b6183c 100644
@@ -56,7 +56,7 @@ Rejected Multi-Threaded Solution
 
 The most "straightforward" implementation would be to spread the set of
 to-be-updated cache entries across multiple threads. But due to the
-thread-unsafe functions in the ODB code, we would have to use locks to
+thread-unsafe functions in the object database code, we would have to use locks to
 coordinate the parallel operation. An early prototype of this solution
 showed that the multi-threaded checkout would bring performance
 improvements over the sequential code, but there was still too much lock

2.38.1.windows.1

Git has an additional "commit graph" capability that supplements the normal commit object's directed acyclic graph (DAG). The supplemental commit graph file is designed for speed of access.

Describe the commit graph both from the normative DAG view point and from the commit graph file perspective.

Also, clarify the link between the branch ref and branch tip by linking to the ref glossary entry, matching this commit graph entry.

The commit-graph file is also distinguished by its hyphenation.

Subsequent commit catches the few cases where the hyphenation of commit-graph was missing.

---
 Documentation/glossary-content.txt | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

index 947ac49606..a526710278 100644
@@ -20,7 +20,7 @@
 [[def_branch]]branch::
 	A "branch" is a line of development.  The most recent
 	<<def_commit,commit>> on a branch is referred to as the tip of
-	that branch.  The tip of the branch is referenced by a branch
+	that branch.  The tip of the branch is <<def_ref,referenced>> by a branch
 	<<def_head,head>>, which moves forward as additional development
 	is done on the branch.  A single Git
 	<<def_repository,repository>> can track an arbitrary number of

@@ -75,6 +75,21 @@ state in the Git history, by creating a new commit representing the current
 state of the <<def_index,index>> and advancing <<def_HEAD,HEAD>>
 to point at the new commit.
 
+[[def_commit_graph_general]]commit graph concept, representations and usage::
+	A synonym for the <<def_DAG,DAG>> structure formed by the commits
+	in the object database, <<def_ref,referenced>> by branch tips,
+	using their <<def_chain,chain>> of linked commits.
+	This structure is the definitive commit graph. The
+	graph can be represented in other ways, e.g. the
+	<<def_commit_graph_file,"commit-graph" file>>.
+
+[[def_commit_graph_file]]commit-graph file::
+	The "commit-graph" (normally hyphenated) file is a supplemental
+	representation of the <<def_commit_graph_general,commit graph>>
+	which accelerates commit graph walks. The "commit-graph" file is
+	stored either in the .git/objects/info directory or in the info
+	directory of an alternate object database.
+
 [[def_commit_object]]commit object::
 	An <<def_object,object>> which contains the information about a
 	particular <<def_revision,revision>>, such as <<def_parent,parents>>, committer,

2.38.1.windows.1

(in reply to <[email protected]>

This short series looks to add the basics of the reachability bitmap and commit graph phrases to the glossary of terms. While these techniques are well known to their developers, for some, they are just magic phrases.

[V3] .. since V2

1/4 Unchanged.
2/4 The distinction between the generic 'commit graph' of the DAG and the implementation specifics of 'commit-graph' file has been retained for the glossary.
However the deliberate hyphenation has been included, and a fourth patch added to maintain the consistency of 'commit-graph' in other documents.

3/4 Tweaks & links applied to Reachability patch.
4/4 New - maintain the consistency of 'commit-graph' in other documents.

[V2] .. since V1
was GitGitGadget #1282,
(in reply to <[email protected]>) Patch 4/4 has been taken upstream independently, and hence dropped here so we're now just [n/3].

Patch 1/3 Dropped the glossary addition in favour of changing the locations that used ODB (Junio's suggestion). Kept the git pack-redundant's --alt-odb but spelt out 'object database' in full in the man page. The only remaining odbs are within goodbye ;-).

While here, add the (oid) abbreviation to its adjacent entry.

Patch 2/3 Split the 'commit-graph' explanation into two parts to distinguish the speed-up option, from Git's core graph concept of object traversal. Included links to existing terms.

Patch 3/3 Added links to existing terms. Statement for the reachability bitmaps.

added cc: for Stolee (commit-graph) and Abhradeep Chakraborty (Bitmaps) review.

[V1] [GGG PR #1282]
https://lore.kernel.org/git/[email protected]/

The first patch [1/4] is to show OBD as an abbreviation to avoid a UNA [0]

Patch [2/4] provides a basic statement for the Commit-Graph's purpose.

Patch [3/4] provides a similar statement for the reachability bitmaps.

These two patches maybe misses out on some linking information as to the benefits these have and the basics of their heuristic.

Patch [4/4] follows up on a bug report about the lack of idempotence for the `--renormalise' command. See commit message for details.

[0] UNA Un-Named Abbreviation.

Philip Oakley (4):
doc: use 'object database' not ODB or abbreviation
glossary: add "commit graph" description
glossary: add reachability bitmap description
doc: use "commit-graph" hyphenation consistently

 Documentation/config/core.txt                 |  2 +-
 Documentation/git-pack-redundant.txt          |  2 +-
 Documentation/gitformat-commit-graph.txt      |  6 ++---
 Documentation/glossary-content.txt            | 27 +++++++++++++++++--
 Documentation/technical/commit-graph.txt      |  8 +++---
 Documentation/technical/parallel-checkout.txt |  2 +-
 6 files changed, 35 insertions(+), 12 deletions(-)

Range-diff against remotes/gitster/po/glossary-around-traversal (v2?):
1: de164ab78b ! 1: 748b15345e doc: use 'object database' not ODB or abbreviation
@@ Commit message
abbreviation to its entry.

- Signed-off-by: Junio C Hamano <[email protected]>

## Documentation/git-pack-redundant.txt ##
@@ Documentation/git-pack-redundant.txt: OPTIONS
2: f677d57699 ! 2: 052a9568e7 glossary: add "commit graph" description
@@ Commit message
glossary: add "commit graph" description

Git has an additional "commit graph" capability that supplements the
- normal commit object's directed acylic graph (DAG). The supplemental
+ normal commit object's directed acyclic graph (DAG). The supplemental
commit graph file is designed for speed of access.

Describe the commit graph both from the normative DAG view point and
@@ Commit message
by linking to the ref glossary entry, matching this commit graph entry.

+ The commit-graph file is also distinguished by its hyphenation.
+
+ Subsequent commit catches the few cases where the hyphenation of
+ commit-graph was missing.
+

- Signed-off-by: Junio C Hamano <[email protected]>

## Documentation/glossary-content.txt ##
@@
@@ Documentation/glossary-content.txt: state in the Git history, by creating a new
to point at the new commit.

+[[def_commit_graph_general]]commit graph concept, representations and usage::
-+ A synonym for the <<def_DAG,DAG>> structure formed by
-+ the commits in the object database, <<def_ref,referenced>> by branch tips,
++ A synonym for the <<def_DAG,DAG>> structure formed by the commits
++ in the object database, <<def_ref,referenced>> by branch tips,
+ using their <<def_chain,chain>> of linked commits.
+ This structure is the definitive commit graph. The
+ graph can be represented in other ways, e.g. the
-+ <<def_commit_graph_file,commit graph file>>.
++ <<def_commit_graph_file,"commit-graph" file>>.
+
-+[[def_commit_graph_file]]commit graph file::
-+ The commit-graph file is a supplemental representation of
-+ the <<def_commit_graph_general,commit graph>> which accelerates
-+ commit graph walks. The "commit-graph" file is stored
-+ either in the .git/objects/info directory or in the info directory
-+ of an alternate object database.
++[[def_commit_graph_file]]commit-graph file::
++ The "commit-graph" (normally hyphenated) file is a supplemental
++ representation of the <<def_commit_graph_general,commit graph>>
++ which accelerates commit graph walks. The "commit-graph" file is
++ stored either in the .git/objects/info directory or in the info
++ directory of an alternate object database.
+
[[def_commit_object]]commit object::
An <<def_object,object>> which contains the information about a
3: 39e9a282fc ! 3: d56234b70c glossary: add reachability bitmap description
@@ Commit message
Describe the purpose of the reachability bitmap.

- Signed-off-by: Junio C Hamano <[email protected]>

## Documentation/glossary-content.txt ##
@@ Documentation/glossary-content.txt: exclude;;
@@ Documentation/glossary-content.txt: exclude;;

+[[def_reachability_bitmap]]reachability bitmaps::
+ Reachability bitmaps store information about the
-+ <<def_reachable,reachability>> of a selected set of objects in
-+ a packfile, or a multi-pack index (MIDX) to speed up object search.
-+ A repository may have at
-+ most one bitmap. The bitmap may belong to either one pack, or the
-+ repository's multi-pack index (if it exists).
++ <<def_reachable,reachability>> of a selected set of commits in
++ a packfile, or a multi-pack index (MIDX), to speed up object search.
++ The bitmaps are stored in a ".bitmap" file. A repository may have at
++ most one bitmap file in use. The bitmap file may belong to either one
++ pack, or the repository's multi-pack index (if it exists).
+
[[def_rebase]]rebase::
To reapply a series of changes from a <<def_branch,branch>> to a
-: ---------- > 4: 87686e63f9 doc: use "commit-graph" hyphenation consistently

2.38.1.windows.1

Describe the purpose of the reachability bitmap.

---
 Documentation/glossary-content.txt | 8 ++++++++
 1 file changed, 8 insertions(+)

index a526710278..5a537268e2 100644
@@ -508,6 +508,14 @@ exclude;;
 	<<def_tree_object,trees>> to the trees or <<def_blob_object,blobs>>
 	that they contain.
 
+[[def_reachability_bitmap]]reachability bitmaps::
+	Reachability bitmaps store information about the
+	<<def_reachable,reachability>> of a selected set of commits in
+	a packfile, or a multi-pack index (MIDX), to speed up object search.
+	The bitmaps are stored in a ".bitmap" file. A repository may have at
+	most one bitmap file in use. The bitmap file may belong to either one
+	pack, or the repository's multi-pack index (if it exists).
+
 [[def_rebase]]rebase::
 	To reapply a series of changes from a <<def_branch,branch>> to a
 	different base, and reset the <<def_head,head>> of that branch

2.38.1.windows.1

Note, historical release notes have not been updated.

# Conflicts:
# Documentation/gitformat-commit-graph.txt

---
 Documentation/config/core.txt            | 2 +-
 Documentation/gitformat-commit-graph.txt | 6 +++---
 Documentation/technical/commit-graph.txt | 6 +++---
 3 files changed, 7 insertions(+), 7 deletions(-)

index 37afbaf5a4..dfbdaf00b8 100644
@@ -618,7 +618,7 @@ but risks losing recent work in the event of an unclean system shutdown.
 * `loose-object` hardens objects added to the repo in loose-object form.
 * `pack` hardens objects added to the repo in packfile form.
 * `pack-metadata` hardens packfile bitmaps and indexes.
-* `commit-graph` hardens the commit graph file.
+* `commit-graph` hardens the commit-graph file.
 * `index` hardens the index when it is modified.
 * `objects` is an aggregate option that is equivalent to
   `loose-object,pack`.

index 7324665716..31cad585e2 100644
@@ -3,7 +3,7 @@ gitformat-commit-graph(5)
 
 NAME
 ----
-gitformat-commit-graph - Git commit graph format
+gitformat-commit-graph - Git commit-graph format
 
 SYNOPSIS
 --------

@@ -14,7 +14,7 @@ $GIT_DIR/objects/info/commit-graphs/*
 DESCRIPTION
 -----------
 
-The Git commit graph stores a list of commit OIDs and some associated
+The Git commit-graph stores a list of commit OIDs and some associated
 metadata, including:
 
 - The generation number of the commit.

@@ -34,7 +34,7 @@ corresponding to the array position within the list of commit OIDs. Due
 to some special constants we use to track parents, we can store at most
 (1 << 30) + (1 << 29) + (1 << 28) - 1 (around 1.8 billion) commits.
 
-== Commit graph files have the following format:
+== Commit-graph files have the following format:
 
 In order to allow extensions that add extra data to the graph, we organize
 the body into "chunks" and provide a binary lookup table at the beginning

index d2a6a13650..86fed0de0f 100644
@@ -1,4 +1,4 @@
-Git Commit Graph Design Notes
+Git Commit-Graph Design Notes
 =============================
 
 Git walks the commit graph for many reasons, including:

@@ -95,7 +95,7 @@ with default order), but is not used when the topological order is
 required (such as merge base calculations, "git log --graph").
 
 In practice, we expect some commits to be created recently and not stored
-in the commit graph. We can treat these commits as having "infinite"
+in the commit-graph. We can treat these commits as having "infinite"
 generation number and walk until reaching commits with known generation
 number.
 

@@ -149,7 +149,7 @@ Design Details
   helpful for these clones, anyway. The commit-graph will not be read or
   written when shallow commits are present.
 
-Commit Graphs Chains
+Commit-Graphs Chains
 --------------------
 
 Typically, repos grow with near-constant velocity (commits per day). Over time,

2.38.1.windows.1

Thanks, the updated round looks good to me. I applied these on top of the tip of master instead of the existing merge base (which was dc8c8deaa6b (Prepare for 2.36.2, 2022-06-07)).

Will queue.

Thanks,
Taylor

Thanks!
Philip