Repository snapshot objects - Revision history

StefanoZacchiroli: add pointer to relevant phabricator tasks

2016-09-15T14:38:31Z

add pointer to relevant phabricator tasks

← Older revision		Revision as of 14:38, 15 September 2016
Line 1:		Line 1:
	'''WARNING: work in progress blueprint'''		* '''WARNING: work in progress blueprint'''
			* '''INFO: the Software Heritage implementation of repository snapshot objects is tracked at [https://forge.softwareheritage.org/T565 T565]'''

	== Introduction ==		== Introduction ==

StefanoZacchiroli at 08:14, 18 August 2016

2016-08-18T08:14:00Z

@@ Line 38: / Line 38: @@
 Note: branch/ref names might contain arbitrary characters except the NULL byte itself.
-=== Serialization a-la Software Heritage ===
+== Implementation ==
 A repository object manifest is a list of entries, named and sorted by branch, where each entry is as follows:
@@ Line 48: / Line 59: @@
 # NULL byte "\0"
-=== Serialization a-la Git ===
+=== a-la Git ===
 A repository object manifest is a list of entries, named and sorted by ref, where each entry is as follows:

StefanoZacchiroli: /* Introduction */ comment about why we include the object type in snapshot entries (thanks Josh Triplett for the idea)

2016-08-16T07:35:51Z

Introduction: comment about why we include the object type in snapshot entries (thanks Josh Triplett for the idea)

← Older revision		Revision as of 07:35, 16 August 2016
Line 5:		Line 5:
	A repository snapshot object, or simply '''snapshot object''', is a [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG node used to capture the current state of a VCS repository.		A repository snapshot object, or simply '''snapshot object''', is a [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG node used to capture the current state of a VCS repository.

	Conceptually, a snapshot object is a complete map from repository entry points ("branches" in [[Software Heritage]] terminology, "refs" in Git) to other objects in the repository, including other snapshot objects if repository entry points point to them.<br>		Conceptually, a snapshot object is a complete map from repository entry points ("branches" in [[Software Heritage]] terminology, "refs" in Git) to other objects in the repository,
	Practically, the map is serialized into a '''manifest''' consisting of a list of triples ''<object type, object ID, branch name>''.		including other snapshot objects if repository entry points point to them.<br>
			Practically, the map is serialized into a '''manifest''' consisting of a list of triples ''<object type, object ID, branch name>''
			(specifying the object ''type'' would not be strictly needed, but it eases traversal, allows for better integrity checking, etc.).

	Entries in snapshots can point to the following object kinds:		Entries in snapshots can point to the following object kinds:

StefanoZacchiroli: /* Manifest */ prefer numbered lists over unordered lists where appropriate (markup)

2016-08-16T07:23:13Z

Manifest: prefer numbered lists over unordered lists where appropriate (markup)

← Older revision		Revision as of 07:23, 16 August 2016
Line 26:		Line 26:
	No matter the implementation of the manifest ''itself'', its '''object ID''' is obtained as follows:		No matter the implementation of the manifest ''itself'', its '''object ID''' is obtained as follows:
	* take the string obtained by concatenating:		* take the string obtained by concatenating:
	** the header string "snapshot " (without quotes)		# the header string "snapshot " (without quotes)
	** the length of the manifest serialized as a decimal integer in ASCII (e.g., "42")		# the length of the manifest serialized as a decimal integer in ASCII (e.g., "42")
	** the NULL byte "\0"		# the NULL byte "\0"
	** the manifest itself		# the manifest itself
	* compute the SHA1 checksum of the obtained string		* compute the SHA1 checksum of the obtained string
	This is equivalent to the current implementation of [https://git-scm.com/docs/git-hash-object git-hash-object(1)] with object type set to "snapshot"		This is equivalent to the current implementation of [https://git-scm.com/docs/git-hash-object git-hash-object(1)] with object type set to "snapshot"
Line 39:		Line 39:

	A repository object manifest is a list of entries, named and sorted by branch, where each entry is as follows:		A repository object manifest is a list of entries, named and sorted by branch, where each entry is as follows:
	* object kind (one of: "content", "directory", "release", "revision", "snapshot")		# object kind (one of: "content", "directory", "release", "revision", "snapshot")
	* ASCII space		# ASCII space
	* SHA1 of the target object serialized as a string of ASCII, lowercase hex digits (e.g., "585f6e27f540012af621a18d0155aae2a8ec0276")		# SHA1 of the target object serialized as a string of ASCII, lowercase hex digits (e.g., "585f6e27f540012af621a18d0155aae2a8ec0276")
	* ASCII space		# ASCII space
	* entry name as a sequence of bytes (e.g., "refs/heads/master")		# entry name as a sequence of bytes (e.g., "refs/heads/master")
	* NULL byte "\0"		# NULL byte "\0"

	=== Serialization a-la Git ===		=== Serialization a-la Git ===

	A repository object manifest is a list of entries, named and sorted by ref, where each entry is as follows:		A repository object manifest is a list of entries, named and sorted by ref, where each entry is as follows:
	* object kind (one of: "blob", "tree", "tag", "commit", "snapshot")		# object kind (one of: "blob", "tree", "tag", "commit", "snapshot")
	* ASCII space		# ASCII space
	* entry name as a sequence of bytes (e.g., "refs/heads/master")		# entry name as a sequence of bytes (e.g., "refs/heads/master")
	* NULL byte "\0"		# NULL byte "\0"
	* SHA1 of the target object serialized as 20 raw bytes		# SHA1 of the target object serialized as 20 raw bytes

	Notes:		Notes:

StefanoZacchiroli: /* Manifest */

2016-08-16T07:19:27Z

Manifest

← Older revision		Revision as of 07:19, 16 August 2016
Line 36:		Line 36:
	Note: branch/ref names might contain arbitrary characters except the NULL byte itself.		Note: branch/ref names might contain arbitrary characters except the NULL byte itself.

	=== a-la Software Heritage ===		=== Serialization a-la Software Heritage ===

	A repository object manifest is a list of entries, named and sorted by branch, where each entry is as follows:		A repository object manifest is a list of entries, named and sorted by branch, where each entry is as follows:
Line 46:		Line 46:
	* NULL byte "\0"		* NULL byte "\0"

	=== a-la Git ===		=== Serialization a-la Git ===

	A repository object manifest is a list of entries, named and sorted by ref, where each entry is as follows:		A repository object manifest is a list of entries, named and sorted by ref, where each entry is as follows:

StefanoZacchiroli: /* Manifest */ Git serialization format

2016-08-16T07:18:40Z

Manifest: Git serialization format

← Older revision		Revision as of 07:18, 16 August 2016
Line 33:		Line 33:
	This is equivalent to the current implementation of [https://git-scm.com/docs/git-hash-object git-hash-object(1)] with object type set to "snapshot"		This is equivalent to the current implementation of [https://git-scm.com/docs/git-hash-object git-hash-object(1)] with object type set to "snapshot"
	(note that to use it you will need to pass <tt>--literally</tt>, as "snapshot" is currently not a supported Git object type).		(note that to use it you will need to pass <tt>--literally</tt>, as "snapshot" is currently not a supported Git object type).

			Note: branch/ref names might contain arbitrary characters except the NULL byte itself.

	=== a-la Software Heritage ===		=== a-la Software Heritage ===

	A repository object manifest is a list of ~~lines~~, sorted by branch ~~(or ref) name~~, where each ~~line~~ is as follows:		A repository object manifest is a list of entries, named and sorted by branch, where each entry is as follows:
	* object kind (one of: "content", "directory", "release", "revision", "snapshot")		* object kind (one of: "content", "directory", "release", "revision", "snapshot")
	* space		* ASCII space
	* SHA1 of the target object serialized as a string of ASCII, lowercase hex digits (e.g., "585f6e27f540012af621a18d0155aae2a8ec0276")		* SHA1 of the target object serialized as a string of ASCII, lowercase hex digits (e.g., "585f6e27f540012af621a18d0155aae2a8ec0276")
	* space		* ASCII space
	* name ~~of the branch (ref)~~ as a sequence of bytes (e.g., "refs/heads/master")		* entry name as a sequence of bytes (e.g., "refs/heads/master")
	* ~~the~~ NULL byte "\0"		* NULL byte "\0"

	~~Note: branch/ref names might contain arbitrary characters except the NULL byte itself.~~

	=== a-la Git ===		=== a-la Git ===

	~~'''TODO'''~~		A repository object manifest is a list of entries, named and sorted by ref, where each entry is as follows:
			* object kind (one of: "blob", "tree", "tag", "commit", "snapshot")
	~~In the spirit~~ of ~~other [https://git-scm.com/book/en/v2/Git-Internals-Git-Objects Git objects]~~, ~~snapshot objects for Git repositories can be implemented~~ as follows.		* ASCII space
			* entry name as a sequence of bytes (e.g., "refs/heads/master")
	~~<pre>~~		* NULL byte "\0"
	~~# create repo with some commits~~, ~~branches~~, ~~and tags~~		* SHA1 of the target object serialized as 20 raw bytes
	~~$ git init test~~
	~~$ cd test/~~
	~~$ echo foo > foo.txt~~
	~~$ git add foo.txt~~
	~~$ git commit -m 'checkin foo'~~
	~~$ git branch foo~~
	~~$ echo bar >> foo.txt~~
	~~$ git commit -a -m 'add bar'~~
	~~$ git~~ tag ~~bar~~
	~~$ echo baz >> foo.txt~~
	~~$ git~~ commit ~~-a -m 'add baz'~~

	~~# ASSUMPTION: the output of git show-ref is sorted by ref~~ name ~~using~~
	~~# the usual Git sort algorithm for textual object manifests. This is~~
	~~# currently the case~~ as of ~~Git 2~~.8.1, ~~but it is not documented~~
	~~# behavior in git-show-ref(1).~~

	~~# repository object in full (the manifest)~~
	~~$ git show-ref \| \~~
	~~while read id ref ; do~~
	~~type=$(git cat-file -t $id)~~
	~~echo $type $id $ref~~
	~~done \~~
	~~> /tmp/snapshot-object.txt~~
	~~$ cat /tmp/snapshot-object.txt~~
	~~commit 585f6e27f540012af621a18d0155aae2a8ec0276 refs/heads/foo~~
	~~commit 6d976a397fe0b28a5bc59540e64f7f36a861af68~~ refs/heads/master
	~~commit 521cb6d728f9fa3d6c4d73ddd309c0796ddf6995 refs/tags/bar~~

	~~# repository object ID, as a Git~~ SHA1
	~~$ git hash-object -w --stdin --literally -t snapshot < /tmp/snapshot-object.txt~~
	~~470d2daa27715987685708b816bf2b52ba5a47c8~~

	~~# raw content~~ of the ~~repository~~ object~~, including Git header~~
	~~$ zlib-flate -uncompress < .git/objects/47/0d2daa27715987685708b816bf2b52ba5a47c8~~
	~~snapshot 191commit 585f6e27f540012af621a18d0155aae2a8ec0276 refs/heads/foo~~
	~~commit 6d976a397fe0b28a5bc59540e64f7f36a861af68 refs/heads/master~~
	~~commit 521cb6d728f9fa3d6c4d73ddd309c0796ddf6995 refs/tags/bar~~

	~~# i.e.~~, ~~a 191-byte long object of type "snapshot"~~		Notes:
	~~# (note~~ that a "\0" ~~before the first "commit" string has been stripped~~)		* there is no separator between entries
	~~</pre>~~		* the above is inspired by the compact serialization format of tree objects, but other variants are possible:
			** reorder the columns so that entry name comes last and "\0" acts as entry terminator
			** serialize SHA1 as ASCII instead of binary (it will take more space, but arguably snapshot objects will be less popular than tree objects)


	[[Category:Blueprint]]		[[Category:Blueprint]]

StefanoZacchiroli: /* Manifest */

2016-08-16T07:07:57Z

Manifest

← Older revision		Revision as of 07:07, 16 August 2016
Line 20:		Line 20:

	The manifest of a repository object is a '''canonical representation''' of it as a sequence of bytes.<br>		The manifest of a repository object is a '''canonical representation''' of it as a sequence of bytes.<br>
	Two ~~different~~ formats for such ~~a manifest~~ are proposed below:		Two alternative serialization formats for such manifests are proposed below:
	* ''a-la Software Heritage'': how we would implement on our own, not taking into account compatibility with/stylistic choices of other VCSs		* ''a-la Software Heritage'': how we would implement on our own, not taking into account compatibility with/stylistic choices of other VCSs
	* ''a-la Git'': manifest implementation similar to how Git implements manifests for other DAG objects		* ''a-la Git'': manifest implementation similar to how Git implements manifests for other DAG objects

StefanoZacchiroli: /* Manifest */ SWH serialization format

2016-08-16T07:07:29Z

Manifest: SWH serialization format

← Older revision		Revision as of 07:07, 16 August 2016
Line 36:		Line 36:
	=== a-la Software Heritage ===		=== a-la Software Heritage ===

	A repository object is		A repository object manifest is a list of lines, sorted by branch (or ref) name, where each line is as follows:
			* object kind (one of: "content", "directory", "release", "revision", "snapshot")
			* space
			* SHA1 of the target object serialized as a string of ASCII, lowercase hex digits (e.g., "585f6e27f540012af621a18d0155aae2a8ec0276")
			* space
			* name of the branch (ref) as a sequence of bytes (e.g., "refs/heads/master")
			* the NULL byte "\0"

	~~'''TODO'''~~		Note: branch/ref names might contain arbitrary characters except the NULL byte itself.

	=== a-la Git ===		=== a-la Git ===

StefanoZacchiroli at 07:03, 16 August 2016

2016-08-16T07:03:25Z

← Older revision		Revision as of 07:03, 16 August 2016
Line 15:		Line 15:
	* snapshots		* snapshots

	The ~~'''~~object ID~~'''~~ of a repository object is the cryptographic hash ~~(the same kind~~ of ~~hash used elsewhere~~ in the Merkle DAG~~) of its manifest~~.		The object ID of a repository object is the cryptographic hash of its manifest, computed in the usual way for the Merkle DAG.

	== Manifest ==		== Manifest ==

	The manifest of a repository object is a ''canonical'' ~~representation~~ of it as a sequence of bytes.<br>		The manifest of a repository object is a '''canonical representation''' of it as a sequence of bytes.<br>
	Two different formats for such a manifest are proposed below:		Two different formats for such a manifest are proposed below:
	* ''a-la Software Heritage'': how we would implement on our own, not taking into account compatibility with/stylistic choices of other VCSs		* ''a-la Software Heritage'': how we would implement on our own, not taking into account compatibility with/stylistic choices of other VCSs
	* ''a-la Git'': manifest implementation similar to how Git implements manifests for other DAG objects		* ''a-la Git'': manifest implementation similar to how Git implements manifests for other DAG objects

	No matter the implementation of the manifest ''itself'', its object ID is obtained as follows:		No matter the implementation of the manifest ''itself'', its '''object ID''' is obtained as follows:
	* take the string obtained by concatenating:		* take the string obtained by concatenating:
	** the header string "snapshot " (without quotes)		** the header string "snapshot " (without quotes)

StefanoZacchiroli: /* Manifest */ describe object ID computation

2016-08-16T07:02:22Z

Manifest: describe object ID computation

← Older revision		Revision as of 07:02, 16 August 2016
Line 23:		Line 23:
	* ''a-la Software Heritage'': how we would implement on our own, not taking into account compatibility with/stylistic choices of other VCSs		* ''a-la Software Heritage'': how we would implement on our own, not taking into account compatibility with/stylistic choices of other VCSs
	* ''a-la Git'': manifest implementation similar to how Git implements manifests for other DAG objects		* ''a-la Git'': manifest implementation similar to how Git implements manifests for other DAG objects

			No matter the implementation of the manifest ''itself'', its object ID is obtained as follows:
			* take the string obtained by concatenating:
			** the header string "snapshot " (without quotes)
			** the length of the manifest serialized as a decimal integer in ASCII (e.g., "42")
			** the NULL byte "\0"
			** the manifest itself
			* compute the SHA1 checksum of the obtained string
			This is equivalent to the current implementation of [https://git-scm.com/docs/git-hash-object git-hash-object(1)] with object type set to "snapshot"
			(note that to use it you will need to pass <tt>--literally</tt>, as "snapshot" is currently not a supported Git object type).

	=== a-la Software Heritage ===		=== a-la Software Heritage ===

			A repository object is

	'''TODO'''		'''TODO'''