* RE: Merge with git-pasky II.
From: Barry Silverman @ 2005-04-15 23:00 UTC (permalink / raw)
To: 'Linus Torvalds'; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0504151313450.7211@ppc970.osdl.org>
The issue I am trying to come to grips with in the current design, is
that the git repository of a number of interrelated projects will soon
become the logical OR of all blobs, commits, and trees in ALL the
projects.
This will involve horrendous amounts of replication, as developers end
interchanging objects that originated from third parties who are not
party to the merge (and which happen to be in the repository because of
previous merge activity).
It would be really nice if the repositories for each project stay
distinct (and maybe even living on different servers). Merges should the
one of the few points of contact where the state be exchanged between
the repositories.
>> If you don't keep track of the incremental merges, you end up with
one
>> really _difficult_ merge that may not be mergable at all. Not
>> automatically, and perhaps not even with help.
No argument from me.... In my example, I didn't intend A2,A3,A4 to be
considered hash's of points where you did a merge - rather they are
hashes of individual points where you did a commit BETWEEN the points
where you merged. A1 and A5 are the "merge points"!
It makes perfect sense to define some subset of commits as "merge-like"
commits, and only have those copied over from one repository to the
other. You could also only use merge-points in the common ancestor
calculation, and not worry about intermediate commits.
Only small changes to the existing logic are necessary to do a merge by
"distributing" out the merge algorithm to each repository. This involves
querying each repository, and communicating the results, followed by
copying over only those blob objects necessary for the merge.
After the merge, you would create a "merge-point commit" record that has
one of the parents pointing to a hash in the other repository!
But the BIG issue with this scheme, is that you will not be replicating
over any of the intermediate commits, trees, or blobs (not really needed
by the merge), but currently being traversed by various plumbing
components.
Hence my question....
-----Original Message-----
From: Linus Torvalds [mailto:torvalds@osdl.org]
Sent: Friday, April 15, 2005 4:31 PM
To: Barry Silverman
Cc: git@vger.kernel.org
Subject: RE: Merge with git-pasky II.
[ I'm cc'ing the git list even though Barry's question wasn't cc'd.
Because I think his question is interesting and astute per se, even
if I disagree with the proposal ]
On Fri, 15 Apr 2005, Barry Silverman wrote:
>
> If git is totally project based, and each commit represents total
state
> of the project, then how important is the intermediate commit
> information between two states.
You need it in order to do further merges.
> IE, Area maintainer has A1->A2->A3->A4->A5 in a repository with 5
> commits, and 5 comments. And I last synced with A1.
>
> A few days later I sync again. Couldn't I just pull the "diff-tree A5
> A1" and then commit to my tree just the record A1->A5. Why does MY
> repository need trees A2,A3,A4?
Because that second merge needs the first merge to work well. The first
merge might have had some small differences that ended up auto-merging
(or
even needing some manual help from you). The second time you sync, there
migth be some more automatic merging. And so on.
If you don't keep track of the incremental merges, you end up with one
really _difficult_ merge that may not be mergable at all. Not
automatically, and perhaps not even with help.
So in order to keep things mergable, you need to not diverge. And the
intermediate merges are the "anchor-points" for the next merge, keeping
the divergences minimal.
I'm personally convinced that one of the reasons CVS is a pain to merge
is
obviously that it doesn't do a good job of finding parents, but also
exactly _because_ it makes merges so painful that people wait longer to
do
them, so you never end up fixing the simple stuff. In contrast, if you
have all these small merges going on all the time, the hope is that
there's never any really painful nasty "final merge".
So you're right - the small merges do end up cluttering up the revision
history. But it's a small price to pay if it means that you avoid having
the painful ones.
> Isn't preserving the A1,A2,A3,A4,A5 a legacy of BK, which required all
> the changesets to be loaded in order, and so is a completely "file"
> driven concept?
Nope. In fact, to some degree git will need this even _more_, since the
git merger is likely to be _weaker_ than BK, and thus more easily
confused.
I do believe that BK has these things for the same reason.
Linus
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Junio C Hamano @ 2005-04-15 22:41 UTC (permalink / raw)
To: Petr Baudis; +Cc: Linus Torvalds, git
In-Reply-To: <20050415204033.GG7417@pasky.ji.cz>
>>>>> "PB" == Petr Baudis <pasky@ucw.cz> writes:
PB> I can't see the conflicts between what I want and what Linus wants.
PB> After all, Linus says that I can use the directory cache in any way I
PB> please (well, the user can, but I'm speaking for him ;-). So I'm doing
PB> so, and with your tool I would get into problems, since it is suddenly
PB> imposing a policy on what should be in the index.
I think our misunderstanding is coming from the use of the word
"merge tree". I think you have been assuming that I wanted you
to run "merge-trees -o ,,merge" --- which would certainly cause
me to muck with your dircache there. I totally agree with you
that that is a *BAD* *THING*. No question there.
However, my assumption has been different. I was assuming that
you would run "merge-trees -o merge~tree" (i.e. different from
your "merge tree"), so that you can get the merge results in a
form parsable by you. And then, using that information, you can
make your changes in ,,merge. After you are done with that
information, you can remove "merge~trees", of course.
The format I chose for the "merge result in a form parsable by
you" happens to be a dircache in "merge~tree", with minimum
number of files checked out when merge cannot be automatically
done safely. In the simplest case of not having any conflicting
merge between $C and $merged, Cogito can immediately run
write-tree in "merge~tree" (not ,,merge) to obtain its tree-ID
$T, so that it can feed it to diff-tree to compare it with
whatever tree state Cogito wants to apply the merges between $C
and $merged to.
I still do not understand what you do in ,,merge directory, but
here is one way you can update the user working directory
in-place without having a ,,merge directory [*2*]. You can run
your "git diff" between $C and $T [*1*]. The result is the diff
you need to apply on top of your user's working files. If the
user does not like the result of running that diff, it can
easily be reversed.
If a manual merge were needed between $C and $merged, Cogito
could guide the user through that manual edit in "merge~tree",
and run update-cache on those hand merged files in "merge~tree",
before running write-tree in "merge~tree" to obtain $T; after
that, everything else is the same.
You make interesting points in other parts of your message I
need to regurgitate for a while, so I would not comment on them
in this message.
[Footnote]
*1* I really like the convenience of being able to use tree-ID
and commit-ID interchangeably there. Thanks.
*2* I understand that this would change the user's "git-tools"
experience a bit. The user will not be told to "go to ,,merge
and commit there which will reflected back to your working tree"
anymore. Instead the merge happens in-place. Committing, not
committing, or further hand-fixing the merge is up to the user.
I suspect this change might even be for the better.
^ permalink raw reply
* Re: Re: Re: write-tree is pasky-0.4
From: Petr Baudis @ 2005-04-15 22:36 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0504151212160.7211@ppc970.osdl.org>
Dear diary, on Fri, Apr 15, 2005 at 10:13:21PM CEST, I got a letter
where Linus Torvalds <torvalds@osdl.org> told me that...
>
>
> On Fri, 15 Apr 2005, Petr Baudis wrote:
> >
> > So, I assume that you don't want to merge my "SCM layer" (which is
> > perfectly fine by me). However, I also apply plenty of patches
> > concerning the "core git" - be it portability, leak fixes, argument
> > parsing fixes and so on.
>
> I'm actually perfectly happy to merge your SCM layer too eventually, but
> I'm nervous at this point. Especially while people are discussing some
> SCM options that I'm personally very leery of, and think that may make
> sense for others, but that I personally distrust.
You mean the renames tracking and similar yet mostly theoretical
discussions? Or do you dislike something already implemented? I'd be
happy to hear about it in that case. (To argue about it and likely get
persuaded... ;-)
But otherwise it is great news to me. Actually, in that case, is it
worth renaming it to Cogito and using cg to invoke it? Wouldn't be that
actually more confusing after it gets merged? IOW, should I stick to
"git" or feel free to rename it to "cg"?
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* [PATCH 2/2] merge-trees script for Linus git
From: Junio C Hamano @ 2005-04-15 21:54 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <7vfyxrhfsw.fsf_-_@assigned-by-dhcp.cox.net>
Linus,
This is the '-q' option for show-diff.c to squelch complaints for
missing files. It is handy if you want to run it in the merge
temporary directory after running merge-trees with its minimum
checkout mode, which is the default, because you would not find any
files other than the ones that needs human validation after the merge
there.
It also fixes the argument parsing bug Paul Mackerras noticed in
<16991.42305.118284.139777@cargo.ozlabs.ibm.com> but slightly
differently.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
show-diff.c | 17 ++++++++++++-----
1 files changed, 12 insertions(+), 5 deletions(-)
show-diff.c: 3f7acd2a692a03026784a18f28521b9af322b71e
--- show-diff.c
+++ show-diff.c 2005-04-15 14:14:53.000000000 -0700
@@ -58,15 +58,20 @@
int main(int argc, char **argv)
{
int silent = 0;
+ int silent_on_nonexisting_files = 0;
int entries = read_cache();
int i;
- while (argc-- > 1) {
- if (!strcmp(argv[1], "-s")) {
- silent = 1;
+ for (i = 1; i < argc; i++) {
+ if (!strcmp(argv[i], "-s")) {
+ silent_on_nonexisting_files = silent = 1;
continue;
}
- usage("show-diff [-s]");
+ if (!strcmp(argv[i], "-q")) {
+ silent_on_nonexisting_files = 1;
+ continue;
+ }
+ usage("show-diff [-s] [-q]");
}
if (entries < 0) {
@@ -82,8 +87,10 @@
void *new;
if (stat(ce->name, &st) < 0) {
+ if (errno == ENOENT && silent_on_nonexisting_files)
+ continue;
printf("%s: %s\n", ce->name, strerror(errno));
- if (errno == ENOENT && !silent)
+ if (errno == ENOENT)
show_diff_empty(ce);
continue;
}
^ permalink raw reply
* [PATCH 1/2] merge-trees script for Linus git
From: Junio C Hamano @ 2005-04-15 21:48 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <7vmzrzhkd3.fsf@assigned-by-dhcp.cox.net>
Linus,
what you have in 461aef08823a18a6c69d472499ef5257f8c7f6c8 is fine
by me for the essential support for merge-trees (sorry for the
confusing name, but this is a stop-gap Q&D script until I do the real
merge-tree.c conversion).
This patch contains the merge-trees script itself and Makefile entry
for it. I have some more fixes to merge-trees in the works but that
will follow later.
I have an optional patch to add '-q' option to show-diff so that
complaints for missing files can be squelched, which I will be sending
you in a separate message.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
Makefile | 2
merge-trees | 302 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 303 insertions(+), 1 deletion(-)
Makefile: b39b4ea37586693dd707d1d0750a9b580350ec50
--- Makefile
+++ Makefile 2005-04-15 13:32:06.000000000 -0700
@@ -14,7 +14,7 @@
PROG= update-cache show-diff init-db write-tree read-tree commit-tree \
cat-file fsck-cache checkout-cache diff-tree rev-tree show-files \
- check-files ls-tree merge-tree
+ check-files ls-tree merge-tree merge-trees
all: $(PROG)
--- /dev/null 2005-03-19 15:28:25.000000000 -0800
+++ merge-trees 2005-04-15 13:32:20.000000000 -0700
@@ -0,0 +1,302 @@
+#!/usr/bin/perl -w
+
+use strict;
+use Cwd;
+use Getopt::Long;
+
+my $full_checkout = 0;
+my $partial_checkout = 0;
+my $output_directory = ',,merge~tree';
+
+GetOptions("full-checkout" => \$full_checkout,
+ "partial-checkout" => \$partial_checkout,
+ "output-directory=s" => \$output_directory)
+ or die;
+
+
+if (@ARGV != 3) {
+ die "Usage: $0 -o [output-directory] [-f] [-p] ancestor A B\n";
+}
+
+if ($full_checkout) {
+ $partial_checkout = 1;
+}
+
+################################################################
+# UI helper -- although it is encouraged to give tree ID,
+# it is OK to give commit ID.
+sub possibly_commit_to_tree {
+ my ($commit_or_tree_id) = @_;
+ my $type = read_cat_file_t($commit_or_tree_id);
+ if ($type eq 'tree') { return $commit_or_tree_id }
+ if ($type ne 'commit') {
+ die "Tree ID (or commit ID) required, given $type.";
+ }
+
+ my ($fhi);
+ open $fhi, '-|', 'cat-file', 'commit', $commit_or_tree_id
+ or die "$!: cat-file commit $commit_or_tree_id";
+ my ($tree) = <$fhi>;
+ close $fhi;
+ ($tree =~ s/^tree (.*)$/$1/)
+ or die "$tree: Linus says the first line is guaranteed to be tree.";
+ return $tree;
+}
+
+sub read_cat_file_t {
+ my ($id) = @_;
+ my ($fhi);
+ open $fhi, '-|', 'cat-file', '-t', $id
+ or die "$!: cat-file -t $id";
+ my ($t) = <$fhi>;
+ close $fhi;
+ chomp($t);
+ return $t;
+}
+
+################################################################
+# Reads diff-tree -r output and gives a hash that maps a path
+# to 4-tuple (old-mode new-mode old-oid new-oid).
+# When creating, old-* are undef. When removing, new-* are undef.
+
+sub OLD_MODE () { 0 }
+sub NEW_MODE () { 1 }
+sub OLD_OID () { 2 }
+sub NEW_OID () { 3 }
+
+sub read_diff_tree {
+ my (@tree) = @_;
+ my ($fhi);
+
+ # Regular expression piece for mode
+ my $reM = '[0-7]+';
+
+ # Regular expression piece for object ID.
+ # There is a talk about base-64 so better make it easier to modify...
+ my $reID = '[0-9a-f]{40}';
+
+ local ($_, $/);
+ $/ = "\0";
+ my %path;
+ open $fhi, '-|', 'diff-tree', '-r', @tree
+ or die "$!: diff-tree -r @tree";
+ while (<$fhi>) {
+ chomp;
+ if (/^\*($reM)->($reM)\tblob\t($reID)->($reID)\t(.*)$/so) {
+ $path{$5} = [$1, $2, $3, $4]; # modified
+ }
+ elsif (/^\+($reM)\tblob\t($reID)\t(.*)$/so) {
+ $path{$3} = [undef, $1, undef, $2]; # added
+ }
+ elsif (/^\-($reM)\tblob\t($reID)\t(.*)$/so) {
+ $path{$3} = [$1, undef, $2, undef]; # deleted
+ }
+ else {
+ die "cannot parse diff-tree output: $_";
+ }
+ }
+ close $fhi;
+ return %path;
+}
+
+################################################################
+# Read show-files output to figure out the set of files contained
+# in the tree. This is used to figure out what ancestor had.
+sub read_show_files {
+ my ($fhi);
+ local ($_, $/);
+ $/ = "\0";
+ open $fhi, '-|', 'show-files', '-z', '--cached'
+ or die "$!: show-files -z --cached";
+ my (@path) = map { chomp; $_ } <$fhi>;
+ close $fhi;
+ return @path;
+}
+
+################################################################
+# Given path and info (typically returned from read_diff_tree),
+# create the file in the working directory to match the NEW tree.
+# This does not touch dircache.
+sub checkout_file {
+ my ($path, $info) = @_;
+ my (@elt) = split(/\//, $path);
+ my $j = '';
+ my $tail = pop @elt;
+ my ($fhi, $fho);
+ for (@elt) {
+ mkdir "$j$_";
+ $j = "$j$_/";
+ }
+ open $fho, '>', "$path";
+ open $fhi, '-|', 'cat-file', 'blob', $info->[NEW_OID]
+ or die "$!: cat-file blob $info->[NEW_OID]";
+ while (<$fhi>) {
+ print $fho $_;
+ }
+ close $fhi;
+ close $fho;
+ chmod oct("0$info->[NEW_MODE]"), "$path";
+}
+
+################################################################
+# Given path and info record the file in the dircache without
+# affecting working directory.
+sub record_file {
+ my ($path, $info) = @_;
+ system ('update-cache', '--add', '--cacheinfo',
+ $info->[NEW_MODE], $info->[NEW_OID], $path);
+}
+
+################################################################
+# Merge info from two trees and leave it in path, without
+# affecting dircache.
+sub merge_tree {
+ my ($path, $infoA, $infoB) = @_;
+ checkout_file("$path~A~", $infoA);
+ checkout_file("$path~B~", $infoB);
+ system 'checkout-cache', $path;
+ rename $path, "$path~O~";
+ my ($fhi, $fho);
+ open $fhi, '-|', 'merge', '-p', "$path~A~", "$path~O~", "$path~B~";
+ open $fho, '>', $path;
+ local ($/);
+ while (<$fhi>) { print $fho $_; }
+ close $fhi;
+ close $fho;
+ # There is no reason to prefer infoA over infoB but
+ # we need to pick one.
+ chmod oct("0$infoA->[NEW_MODE]"), $path;
+}
+
+################################################################
+
+# O stands for "the original". A and B are being merged.
+my ($treeO, $treeA, $treeB) = map { possibly_commit_to_tree $_ } @ARGV;
+
+# Create a temporary directory and go there.
+system('rm', '-rf', $output_directory) == 0 &&
+system('mkdir', '-p', "$output_directory/.git") == 0 &&
+symlink(Cwd::getcwd . "/.git/objects", "$output_directory/.git/objects") &&
+chdir $output_directory &&
+system('read-tree', $treeO) == 0
+ or die "$!: Failed to set up merge working area $output_directory";
+
+# Find out edits done in each branch.
+my %treeA = read_diff_tree($treeO, $treeA);
+my %treeB = read_diff_tree($treeO, $treeB);
+
+# The list of files that was in the ancestor.
+my @ancestor_file = read_show_files();
+my %ancestor_file = map { $_ => 1 } @ancestor_file;
+
+# Report output is formated as follows:
+#
+# The first letter shows the origin of the result.
+# O - original
+# A - treeA
+# B - treeB
+# M - both treeA and treeB
+# * - treeA and treeB conflicts; needs human action.
+#
+# The second and third letter shows what each tree did.
+# . - no change
+# A - created
+# M - modified
+# D - deleted
+
+for (@ancestor_file) {
+ if (! exists $treeA{$_} && ! exists $treeB{$_}) {
+ if ($full_checkout) {
+ system 'checkout-cache', $_;
+ }
+ print STDERR "O.. $_\n"; # keep original
+ }
+}
+
+for my $set ([\%treeA, \%treeB, 'A'], [\%treeB, \%treeA, 'B']) {
+ my ($this, $other, $side) = @$set;
+ my $delete_sign = ($side eq 'A') ? 'D.' : '.D';
+ my $create_sign = ($side eq 'A') ? 'A.' : '.A';
+ my $modify_sign = ($side eq 'A') ? 'M.' : '.M';
+ while (my ($path, $info) = each %$this) {
+ # In this loop we do not deal with overlaps.
+ next if (exists $other->{$path});
+
+ if (! defined $info->[NEW_OID]) {
+ # deleted in this tree only.
+ unlink $path;
+ system 'update-cache', '--remove', $path;
+ print STDERR "${side}${delete_sign} $path\n";
+ }
+ else {
+ # modified or created in this tree only.
+ my $create_or_modify =
+ (! defined $info->[OLD_OID]) ? $create_sign : $modify_sign;
+ print STDERR "${side}${create_or_modify} $path\n";
+ if ($partial_checkout) {
+ checkout_file($path, $info);
+ system 'update-cache', '--add', $path;
+ } else {
+ record_file($path, $info);
+ }
+ }
+ }
+}
+
+my @warning = ();
+
+while (my ($path, $infoA) = each %treeA) {
+ # We need to deal only with overlaps.
+ next if (!exists $treeB{$path});
+
+ my $infoB = $treeB{$path};
+ if (! defined $infoA->[NEW_OID]) {
+ # Deleted in tree A.
+ if (! defined $infoB->[NEW_OID]) {
+ # Deleted in both trees (obvious).
+ print STDERR "MDD $path\n";
+ unlink $path;
+ system 'update-cache', '--remove', $path;
+ }
+ else {
+ # TreeA wants to remove but TreeB wants to modify it.
+ print STDERR "*DM $path\n";
+ checkout_file("$path~B~", $infoB);
+ push @warning, $path;
+ }
+ }
+ else {
+ # Modified or created in tree A
+ if (! defined $infoB->[NEW_OID]) {
+ # TreeA wants to modify but treeB wants to remove it.
+ print STDERR "*MD $path\n";
+ checkout_file("$path~A~", $infoA);
+ push @warning, $path;
+ }
+ else {
+ # Modified both in treeA and treeB.
+ # Are they modifying to the same contents?
+ if ($infoA->[NEW_OID] eq $infoB->[NEW_OID]) {
+ # No changes or just the mode.
+ # we prefer TreeA over TreeB for no particular reason.
+ print STDERR "MMM $path\n";
+ record_file($path, $infoA);
+ }
+ else {
+ # Modified in both. Needs merge.
+ print STDERR "*MM $path\n";
+ merge_tree($path, $infoA, $infoB);
+ }
+ }
+ }
+}
+
+if (@warning) {
+ print "\nThere are some files that were deleted in one branch and\n"
+ . "modified in another. Please examine them carefully:\n";
+ for (@warning) {
+ print "$_\n";
+ }
+}
+
+# system 'show-diff', '-q';
^ permalink raw reply
* Re: Re: write-tree is pasky-0.4
From: Petr Baudis @ 2005-04-15 21:22 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: Junio C Hamano, Linus Torvalds, git
In-Reply-To: <Pine.LNX.4.61.0504151617170.27637@cag.csail.mit.edu>
Dear diary, on Fri, Apr 15, 2005 at 10:58:10PM CEST, I got a letter
where "C. Scott Ananian" <cscott@cscott.net> told me that...
> On Fri, 15 Apr 2005, Junio C Hamano wrote:
>
> >to yours is no problem for me. Currently I see your HEAD is at
> >461aef08823a18a6c69d472499ef5257f8c7f6c8, so I will generate a
> >set of patches against it.
>
> Have you considered using an s/key-like system to make these hashes more
> human-readable? Using the S/Key translation (11-bit chunks map to a 1-4
> letter word), Linus' HEAD is at:
> WOW-SCAN-NAVE-AUK-JILL-BASH-HI-LACE-LID-RIDE-RUSE-LINE-GLEE-WICK-A
> ...which is a little longer, but speaking of branch "wow-scan" (which
> gives 22 bits of disambiguation) is probably less error-prone than
> discussing branch '461...' (only 12 bits).
>
> You could supercharge this algorithm by using (say)
> /usr/dict/american-english-large (>2^17 words; 160 bits of hash = 10
> dictionary words), or mixing upper and lower case (likely to reduce the 15
> word s/key phrase to ~11 words) to give something like
> RiDe-Rift-rIMe-rOSy-ScaR-sCat-ShiN-sIde-Sine-seeK-TIEd-TINT
> My personal feeling is that case is likely to be dropped in casual
> conversation, so speaking of branch 'wow', 'wow-scan', or 'wow-scan-nave'
> is likely to be significantly more useful than trying to pronounce
> mixed-cased versions of these.
>
> This is obviously a cogito issue, rather than a git-fs thing.
I kind of like it, the only thing I fear is possible conflict with
branch names; it is not very likely though, I think. I believe (at
least) the first three words should be used if possible.
I'm not sure in what cases do you think we should use those "verbal"
names, though. Of course we should accept them as IDs, but I don't think
we should ever show them automatically. Probably provide a trivial to
use tool to convert to them, and parameters for *-id tools to show them.
I assume we would have a custom tool for the translation?
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: write-tree is pasky-0.4
From: C. Scott Ananian @ 2005-04-15 20:58 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, Petr Baudis, git
In-Reply-To: <7vmzrzhkd3.fsf@assigned-by-dhcp.cox.net>
On Fri, 15 Apr 2005, Junio C Hamano wrote:
> to yours is no problem for me. Currently I see your HEAD is at
> 461aef08823a18a6c69d472499ef5257f8c7f6c8, so I will generate a
> set of patches against it.
Have you considered using an s/key-like system to make these hashes more
human-readable? Using the S/Key translation (11-bit chunks map to a 1-4
letter word), Linus' HEAD is at:
WOW-SCAN-NAVE-AUK-JILL-BASH-HI-LACE-LID-RIDE-RUSE-LINE-GLEE-WICK-A
...which is a little longer, but speaking of branch "wow-scan" (which
gives 22 bits of disambiguation) is probably less error-prone than
discussing branch '461...' (only 12 bits).
You could supercharge this algorithm by using (say)
/usr/dict/american-english-large (>2^17 words; 160 bits of hash = 10
dictionary words), or mixing upper and lower case (likely to reduce the 15
word s/key phrase to ~11 words) to give something like
RiDe-Rift-rIMe-rOSy-ScaR-sCat-ShiN-sIde-Sine-seeK-TIEd-TINT
My personal feeling is that case is likely to be dropped in casual
conversation, so speaking of branch 'wow', 'wow-scan', or 'wow-scan-nave'
is likely to be significantly more useful than trying to pronounce
mixed-cased versions of these.
This is obviously a cogito issue, rather than a git-fs thing.
--scott
[More info is in RFCs 2289 and 1760, although all I'm really using from
these is the word dictionary in the appendix.]
http://www.faqs.org/rfcs/rfc1760.html
http://www.faqs.org/rfcs/rfc2289.html
SKIMMER MKOFTEN Ft. Bragg Sabana Seca ESMERALDITE NORAD HTAUTOMAT
radar interception Pakistan BOND Kennedy postcard corporate globalization
( http://cscott.net/ )
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Linus Torvalds @ 2005-04-15 20:45 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Petr Baudis, Christopher Li, git
In-Reply-To: <7vr7hbhky9.fsf@assigned-by-dhcp.cox.net>
On Fri, 15 Apr 2005, Junio C Hamano wrote:
>
> I was looking at merge-tree.c last night to add recursive
> behaviour (my favorite these days ;-) to it [*1*].
>
> But then I started thinking.
Always good.
> LT> ... For each entry in the directory it says either
> LT> select <mode> <sha1> path
> LT> or
> LT> merge <mode>-><mode>,<mode> <sha1>-><sha1>,<sha1> path
> LT> depending on whether it could directly select the right object or not.
>
> Given that the case you are primarily interested in is the one
> that affects only small parts of a huge tree (i.e. common kernel
> merge pattern I understand from your previous messages), your
> "hacky version" [*2*], extended for recursive operation, would
> spit out 98% select and 2% merge, and probably the origin of
> these selects are distributed across ancestor=90%, his=4%,
> my=4%, or something similar. Am I misestimating grossly?
No. That's _exactly_ right. You do not want a recursive merge-tree.
The "diff-tree" thing is different, exactly because it prunes out all the
differences early on.
> I am thinking about:
>
> - adding recursive behaviour (I am almost done with this);
I think your suggestion sounds perfectly reasonable.
Linus
^ permalink raw reply
* Re: Re: Merge with git-pasky II.
From: Petr Baudis @ 2005-04-15 20:40 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, git
In-Reply-To: <7vwtr4ibkt.fsf@assigned-by-dhcp.cox.net>
Dear diary, on Fri, Apr 15, 2005 at 12:22:26PM CEST, I got a letter
where Junio C Hamano <junkio@cox.net> told me that...
> After I re-read [*R1*], in which Linus talks about dircache,
> especially this section:
>
> - The "current directory cache" describes some baseline. In particular,
> note the "some" part. It's not tied to any special baseline, and you
> can change your baseline any way you please.
>
> So it does NOT have to track any particular state in either the object
> database _or_ in your actual current working tree. In fact, all real
> interactions with "git" are really about updating this staging area one
> way or the other: you might check out the state from it into your
> working area (partially or fully), you can push your working area into
> the staging area (again, partially or fully).
>
> And if you want to, you can write the thing that the staging area
> represents as a "tree" into the object database, or you can merge a
> tree from the object database into the staging area.
>
> In other words: the staging area aka "current directory cache" is
> really how all interaction takes place. The object database never
> interacts directly with your working directory contents. ALL
> interactions go through the current directory cache.
>
> I started to have more doubts on the approach of *not*
> performing the merge in the dircache I set up specifically for
> merging, which is the direction in which you are pushing if I
> understand you correctly. Maybe I completely misunderstand what
> you want. This message is long but I need a clear understanding
> of what is expected to be useful to you, so please bear with me.
> PB> merge-tree.pl -b $base $(tree-id) $merged | parse-your-output
>
> Please help me understand this example you have given earlier.
> Here is my understanding of your assumption when the above
> pipeline takes place. Correct me if I am mistaken.
>
> * The user is in a working directory $W. It is controlled by
> git-tools and there are $W/.git/. directory and $W/.git/index
> dircache.
>
> * The dircache $W/.git/index started its life as a read-tree
> from some commit. The git-tools is keeping track of which
> commit it is somewhere, presumably in $W/.git/ directory.
> Let's call it $C (commit).
>
> ? Question. Is the $(tree-id) in your example the same as $C
> above?
Yes. Actually $(tree-id) returns ID of the tree object, not the commit
object; but that doesn't matter here, probably - let's ignore that
distinction for simplicity.
> * The user have run [*1*] (see Footnote below) checkout-cache
> on $W/.git/index some time in the past and $W is full of
> working files. Some of them may or may not have modified.
> There may be some additions or deletions. So the contents of
> the working directory may not match the tree associated with
> $C.
>
> * The user may or may not have run [*1*] update-cache in $W.
> The contents of the dircache $W/.git/index may not match the
> tree associated with $C.
>
> ? Question. Are you forbidding the user to run update-cache by
> hand, and keeping track of the changes yourself, to be
> applied all at once at "git commit" time, thereby
> guaranteeing the $W/.git/index to match the tree associated
> with $C all times? From the description of The "GIT toolkit"
> section in README, it is not clear to me which part of his
> repository an end user is not supposed to muck with himself.
Ideally, he shouldn't be using *any* of the low-level plumbing by now.
The only exception is update-cache --refresh, which he can do at will
(I'm yet thinking what to do with it :-).
The git-tools always assume that index basically contains the state as
of the last commit. (Actually the only time when this matters *now*
might be git diff - the user would get confused from the results.)
> * Now the user has some changes in his working directory and
> notices upstream or a side branch has notable changes
> desireble to be picked up. So he runs some git-tools command
> to cause the above quoted pipeline to run.
>
> ? Question. Does $merged in your example mean such an upstream
> or side branch? Is $base in your example the common ancestor
> between $C and $merged?
Correct.
*HOWEVER* what is not correct is that git-tools would let you merge in
your working directory while you have local changes there.
In the past, the merge would happen in your working tree, but git-tools
wouldn't let you go for it unless your working tree has no local
changes. It would complain loudly and refuse to, since it's *not* what
you want to do and it was most likely a mistake.
Currently, git merge just creates a ,,merge/ subdirectory sharing the
object database with your working tree, but with an independent checkout
of it; it will do the merge there, and when you commit it there, it will
update your working tree with the merged changes.
I'm describing both behaviors since I might revert back to the first
one, based on what (if anything) will Linus reply to my mail about
out-of-tree merges.
But either way, when a merge is about to happen upon us, the working
tree is "clean".
> Assuming that my above understanding of your model is correct,
> here are my "thinking aloud".
>
> - "merge-trees $base $C $merged" looks only at the git object
> database for those three trees named. The data structure of
> git object database is optimized to distinguish differences
> in those recorded trees (and hence recorded blobs they point
> at) without unpacking most of the files if the changes are
> small, because all the blobs involved are already hashed. It
> is not very good at comparing things in git object store and
> working files in random states, which would involve unpacking
> blobs and comparing, so "merge-trees" does not bother.
>
> - What can come out from merge-trees is therefore one of the
> following for each path from the union of paths contained in
> $base, $C, and $merged:
>
> (a) Neither $C nor $merged changed it --- merge result is what
> is in $C.
(Or in $base, if you don't want to give $C "unfair advantage", since it
does not matter. ;-)
> (b) $C changed it but $merged did not --- merge result is what
> is in $C.
>
> (c) Both $C and $merged changed it in the same way --- merge
> result is what is in $C.
>
> (d) $C did not change it but $merged did --- merge result is
> what is in $merged.
>
> (e) Both $C and $merged changed it differently --- merge is
> needed and automatically succeeds between $C and $merge.
>
> (f) Both $C and $merged changed it differently --- merge is
> needed but have conflicts.
>
> - Assuming we are dealing with the case where working files are
> dirty and do not match what is in $C, among the above,
> (a)-(c) can be ignored by SCM. What the user has in his
> working files is exactly what he would have got if he started
> working from the merge result, although in reality the work
> was started from $C.
Yes. Actually they can be ignored by git-tools in any case since what is
in the directory cache is $C. So it never needs to do any special
action.
> Handling (d), (e) and (f) from SCM's point of view would be
> the same. They all involve 3-way merges between the file in
> the working directory, and the file from $merged, pivoting on
> the file from $base. In order to help SCM, merge-trees
> therefore should output SHA1 of blobs for such a file from
> $base and $merged and expect SCM to run "cat-file blob" on
> them and then merge or diff3. Up to the point of giving
> those two SHA1 out is the business of merge-trees and after
> that it is up to SCM.
>
> That would work. So I should base the design of output from
> merge-trees on the above analysis, which probably needs to be
> extended to cover differences between creation, modification,
> and deletion.
Yes, it sounds sensible.
Actually, you don't even need to make $C more special than $merged; I
can filter out only the $merged changes on the SCM level. I guess that
would add no complexity to your tool and make it usable even for more
exotic kinds of merges (like the floating-in-the-void merge of two
"equally important" trees).
> - However, the above is quite different from the way Linus
> envisioned initially, on which my current implementation is
> based [*3*].
>
> My current implementation is to record the merge outcome in
> the temporary dircache $W/,,merge/.git/index for cases
> (a)-(e). The last case (f) is problematic and needs human
> validation [*2*], so it is not recorded in that temporary
> dircache, but the files to be merged are left in that
> temporary directory and merge-trees stops there. It is
> expected that the end-user or SCM would merge the resulting
> file and run update-cache to update $W/,,merge/.git/index.
> After that happens, $W/,,merge/.git/index has the tree
> representing the desired result of the merge. It is expected
> that the end-user or SCM would write-tree, commit-tree there
> in the temporary directory, creating a new commit $C1.
>
> Then, it is expected that the SCM would make a patch file
> between $C and the user working directory, checks out $C1
> (either in the user's working directory or another temporary
> directory; at this point merge-trees does not care because it
> has already done its job and exited), applies that patch to
> bring the user edits over to $C1. Then that directory would
> contain the desired merge of user edits.
>
> That is my understanding of how Linus originally wanted the
> tool to do his kernel work with to work. My hesitation to
> suggestions from you to change it not to keep its own merge
> dircache is coming from here. Not doing what I am currently
> doing to $W/,,merge/.git/index dircache would mean that SCM
> would have to do more, not less, to arrive at $C1 (the result
> of the clean $merge and $C merge pivoted at $base), where the
> real SCM merge begins.
Well. Currently, apart from the directory cache part, I do it like you
describe. I create a new directory, after commit I apply the diff back
to the original tree etc.
The only problem is really the dircache, and that's because it would be
done totally differently than in the original tree, and I would
unnecessarily have to introduce crowds of special cases to my tools in
order for them to be usable in the merge tree (I call the ",,merge"
temporary directory a "merge tree").
And the user would still lose the capability of easily seeing the
changes being committed. I admit that I'm using this largely as an
excuse and there *could* be a tool made which would compare the given
tree with the cache, but it would be clumsy to use, violate Linus' "ALL
interactions go through the current directory cache" paradigm (whew, the
first time in my life I used this word), and we could do just fine with
our current tools.
> Although I suspect I am misunderstanding what you want, your
> messages so far suggest that what you want might be quite
> different from what Linus wants. Please do not misunderstand
> what I mean by saying this. I am not saying that Linus is
> always right [*4*] and therefore you are wrong for wanting
> something else. It is just that, if what I started writing
> needs to support both of those quite different needs, I need to
> know what they are. I think I understand what Linus wants well
> enough [*5*], but I am not certain about yours.
I can't see the conflicts between what I want and what Linus wants.
After all, Linus says that I can use the directory cache in any way I
please (well, the user can, but I'm speaking for him ;-). So I'm doing
so, and with your tool I would get into problems, since it is suddenly
imposing a policy on what should be in the index.
..snip..
> *2* Strictly speaking, case (e) needs human validation as
> well, because successful textual merge does not guarantee
> sensible semantic merge.
..snip..
Actually, I think _all_ the caches should make the human validation
_possible_ (by showing the diff of what would be merged), and it is
trivial to do so by having pristine index.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* RE: Merge with git-pasky II.
From: Linus Torvalds @ 2005-04-15 20:31 UTC (permalink / raw)
To: Barry Silverman; +Cc: git
In-Reply-To: <000d01c541ed$32241fd0$6400a8c0@gandalf>
[ I'm cc'ing the git list even though Barry's question wasn't cc'd.
Because I think his question is interesting and astute per se, even
if I disagree with the proposal ]
On Fri, 15 Apr 2005, Barry Silverman wrote:
>
> If git is totally project based, and each commit represents total state
> of the project, then how important is the intermediate commit
> information between two states.
You need it in order to do further merges.
> IE, Area maintainer has A1->A2->A3->A4->A5 in a repository with 5
> commits, and 5 comments. And I last synced with A1.
>
> A few days later I sync again. Couldn't I just pull the "diff-tree A5
> A1" and then commit to my tree just the record A1->A5. Why does MY
> repository need trees A2,A3,A4?
Because that second merge needs the first merge to work well. The first
merge might have had some small differences that ended up auto-merging (or
even needing some manual help from you). The second time you sync, there
migth be some more automatic merging. And so on.
If you don't keep track of the incremental merges, you end up with one
really _difficult_ merge that may not be mergable at all. Not
automatically, and perhaps not even with help.
So in order to keep things mergable, you need to not diverge. And the
intermediate merges are the "anchor-points" for the next merge, keeping
the divergences minimal.
I'm personally convinced that one of the reasons CVS is a pain to merge is
obviously that it doesn't do a good job of finding parents, but also
exactly _because_ it makes merges so painful that people wait longer to do
them, so you never end up fixing the simple stuff. In contrast, if you
have all these small merges going on all the time, the hope is that
there's never any really painful nasty "final merge".
So you're right - the small merges do end up cluttering up the revision
history. But it's a small price to pay if it means that you avoid having
the painful ones.
> Isn't preserving the A1,A2,A3,A4,A5 a legacy of BK, which required all
> the changesets to be loaded in order, and so is a completely "file"
> driven concept?
Nope. In fact, to some degree git will need this even _more_, since the
git merger is likely to be _weaker_ than BK, and thus more easily
confused.
I do believe that BK has these things for the same reason.
Linus
^ permalink raw reply
* Re: fix various issues in gitapply.sh (basically did not handle add/del/cm at all)
From: Martin Schlemmer @ 2005-04-15 20:30 UTC (permalink / raw)
To: Petr Baudis; +Cc: GIT Mailing Lists
In-Reply-To: <20050415181526.GA7417@pasky.ji.cz>
[-- Attachment #1: Type: text/plain, Size: 2059 bytes --]
On Fri, 2005-04-15 at 20:15 +0200, Petr Baudis wrote:
> Dear diary, on Fri, Apr 15, 2005 at 11:28:38AM CEST, I got a letter
> where Martin Schlemmer <azarah@nosferatu.za.org> told me that...
> > Hi,
> >
> > The egrep regex should not escape the '{' and '}', and also add a check
> > for ' \t' so that we do not pickup stuff like '+----', etc. Fix typo in
> > assignment. Check if file exists in new tree before adding/removing
> > (might add support for this lowlevel to increase speed?). Fix typo in
> > line removing temp files.
> >
> > Signed-off-by: Martin Schlemmer <azarah@gentoo.org>
>
> Thanks for the merge and typo fixes. I can't imagine how, but it really
> appeared to work for me that time!
>
> I'm confused however what does the exits_in_cache() (what exits? exists?)
> gives us, apart of horribly-looking code. What bug does it fix?
>
My typo it seems - should be exists. Basically (especially for
gittrack.sh) it will add all files changed between the trees to either
the add or remove queue if this is not done. This is because it will
just add (say git track linus; git track pasky) the git*.sh files that
is missing in the linus tree (or gitrm.sh if in reverse) although they
are already present there. So we need to check if the file exists in
the destination tree before we git{add,rm}.sh it - if it do exists, then
its ok to gitrm.sh it, if it does not, it is ok to gitadd.sh it.
The other problem is also that if you keep switching, it will add each
file multiple times to the add/rm queue. This is a bug with
git{add,rm}.sh which do not check the queue if the file is already
there, and it also add a file even if it is already in the cache - so it
probably need the same type of fix. I will send a patch when we get how
we check if a file is already in the cache resolved.
Like I said in the patch, it might be better to add support low-level
side (don't know if we can have ls-tree return true/false on file basis,
else add a new tool?).
Thanks,
--
Martin Schlemmer
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* [PATCH] Fix typo in gitapply.sh
From: Art Haas @ 2005-04-15 20:22 UTC (permalink / raw)
To: git
Hi.
The variable is '$patchfifo', not '$pathfifo'. Adding the missing 'c'
will remove the stray pipes that have been left in /tmp.
Art Haas
gitapply.sh: 47b9346d2679b1bf34220fe4502f15c7d0737b0c
--- gitapply.sh
+++ gitapply.sh 2005-04-15 15:11:03.000000000 -0500
@@ -74,4 +74,4 @@
done
' padding
-rm $pathfifo $todo $gonefile
+rm $patchfifo $todo $gonefile
--
Man once surrendering his reason, has no remaining guard against absurdities
the most monstrous, and like a ship without rudder, is the sport of every wind.
-Thomas Jefferson to James Smith, 1822
----- End forwarded message -----
--
Man once surrendering his reason, has no remaining guard against absurdities
the most monstrous, and like a ship without rudder, is the sport of every wind.
-Thomas Jefferson to James Smith, 1822
^ permalink raw reply
* Re: Re: write-tree is pasky-0.4
From: Linus Torvalds @ 2005-04-15 20:13 UTC (permalink / raw)
To: Petr Baudis; +Cc: Junio C Hamano, git
In-Reply-To: <20050415185624.GB7417@pasky.ji.cz>
On Fri, 15 Apr 2005, Petr Baudis wrote:
>
> So, I assume that you don't want to merge my "SCM layer" (which is
> perfectly fine by me). However, I also apply plenty of patches
> concerning the "core git" - be it portability, leak fixes, argument
> parsing fixes and so on.
I'm actually perfectly happy to merge your SCM layer too eventually, but
I'm nervous at this point. Especially while people are discussing some
SCM options that I'm personally very leery of, and think that may make
sense for others, but that I personally distrust.
> BTW, just out of interest, are you personally planning to use Cogito for
> your kernel and sparse (and possibly even git) work, or will you stay
> with your lowlevel plumbing for that?
I'm really really hoping I'd use cogito, and that it ends up being just
one project. In particular, I'm hoping that in a few days, I'll have done
enough plumbing that I don't even care any more, and then I'd not even
maintain a tree of my own.
I'm really not that much of an SCM guy. I detest pretty much all SCM's out
there, and while it's been interesting to do 'git', I've done it because I
was forced to, and because I really wanted to put _my_ needs and opinions
first in an SCM, and see how that works. That's why I've been so adamant
about having a "philosophy", because otherwise I'd probably just end up
with yet another SCM that I'd despise.
So for me, the "optimal" situation really ends up that you guys end up as
the maintainers. I don't even _want_ to maintain it, although I'd be more
than happy to be part of the engineering team. I just want to mark out the
direction well enough and get it to a point where I can _use_ it, that I
feel like I'm done.
But before I can do that, I need to feel like I can live with the end
result. The only missing part is merges, and I think you and Junio are
getting pretty close (with Daniel's parent finder, Junio's merger etc).
Linus
^ permalink raw reply
* Re: write-tree is pasky-0.4
From: Junio C Hamano @ 2005-04-15 20:10 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
In-Reply-To: <Pine.LNX.4.58.0504151138490.7211@ppc970.osdl.org>
>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
LT> Hey, all the code I write is always perfect, of course ;)
And you are always right ;-) Liked that blast-from-the-past?
LT> That said, I'm having some trouble merging with your perfect code,
LT> especially since I decided that Russell's "always big-endian" thing was
LT> definitely the right way to go (but ended up doing it slightly
LT> differently).
LT> I did my own version of "upcate-cache --cacheinfo", although
LT> mine is a bit more anal, and if you add a new filename it
LT> wants that "--add" flag in there first (why? I really like
LT> to make sure that people who add or remove files from the
LT> cache say so explicitly, so that there are no surprises).
LT> Otherwise it should be compatible with yours.
Thanks. Not honoring "--add" was an oversight on my part.
LT> And I merged your "Add -z option to show-files", but you had
LT> based your other patches on Petr's tree which due to my
LT> other changes is not going to merge totally cleanly with
LT> mine, so I'm wondering if you might want to try to re-merge
LT> your mergepoint stuff against my current tree?
My pleasure. I am currently not that interested in toilet part
than I am interested in plumbing part, so rebasing my tree back
to yours is no problem for me. Currently I see your HEAD is at
461aef08823a18a6c69d472499ef5257f8c7f6c8, so I will generate a
set of patches against it.
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Junio C Hamano @ 2005-04-15 19:57 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, Christopher Li, git
In-Reply-To: <Pine.LNX.4.58.0504140051550.7211@ppc970.osdl.org>
>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
LT> In the meantime I wrote a very stupid "merge-tree" which
LT> does things slightly differently, but I really think your
LT> approach (aka my original approach) is actually a lot
LT> faster. I was just starting to worry that the ball didn't
LT> start, so I wrote an even hackier one.
LT> ... This "one directory at a time with very explicit output"
LT> thing is much more down-to-earth, but it's also likely
LT> slower because it will need script help more often.
I was looking at merge-tree.c last night to add recursive
behaviour (my favorite these days ;-) to it [*1*].
But then I started thinking.
LT> ... For each entry in the directory it says either
LT> select <mode> <sha1> path
LT> or
LT> merge <mode>-><mode>,<mode> <sha1>-><sha1>,<sha1> path
LT> depending on whether it could directly select the right object or not.
Given that the case you are primarily interested in is the one
that affects only small parts of a huge tree (i.e. common kernel
merge pattern I understand from your previous messages), your
"hacky version" [*2*], extended for recursive operation, would
spit out 98% select and 2% merge, and probably the origin of
these selects are distributed across ancestor=90%, his=4%,
my=4%, or something similar. Am I misestimating grossly?
Assuming I am correct in the above, this would not scale for a
huge project. We need to cut down the number of "90% select"
part of the output to make it manageable.
I am thinking about:
- adding recursive behaviour (I am almost done with this);
- adding another command line argument to merge-tree.c, to
tell "do not output anything for the path if the resulting
merge is the same as what is in this tree";
- adding another output type, "delete" to make the output type
repertoire these three:
delete path
select <mode> <sha1> path
merge <mode>-><mode>,<mode> <sha1>-><sha1>,<sha1> path
When the user of the output of
$ merge-tree <ancestor-sha1> <my-sha1> <his-sha1> <result-base-sha1>
want to get a dircache populated with the merged result, he can:
1. read-tree <result-base-sha1>
2. for each output:
a) "delete" -- delete path from dircache
b) "select" -- register mode-sha1 at path
c) "merge" -- do the 3-way merge and register result at path
Do you think this is sensible?
The reason I have the separate <result-base-sha1> instead of
always using <ancestor-sha1> is because the user may be thinking
of patching an existing base which is different from "my" or
"his" or "ancestor" and doing it in place. That way, probably
Pasky's SCM can use it to patch the dircache it creates in its
own ,,merge/ directory, which would most likely be initially
populated from the dircache in the user's working directory---
which may or may not match "my-sha1" if the user has uncommitted
update-cache there.
Pasky, do you think this is workable? If so do you think this
would make your life easier?
[Footnotes]
*1* That's how I found the S_IFDIR problem (not in your tree but
in the copy I had).
*2* I did not find it quite "hacky". It was a pleasant read.
Especially I liked "smaller()" part.
^ permalink raw reply
* Re: Re: Merge with git-pasky II.
From: Petr Baudis @ 2005-04-15 19:54 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, git
In-Reply-To: <7v7jj4q2j2.fsf@assigned-by-dhcp.cox.net>
Dear diary, on Fri, Apr 15, 2005 at 02:58:25AM CEST, I got a letter
where Junio C Hamano <junkio@cox.net> told me that...
> >>>>> "PB" == Petr Baudis <pasky@ucw.cz> writes:
> >> I think the above would result in what SCM person would call
> >> "merge upstream/sidestream changes into my working directory".
>
> PB> And that's exactly what I'm doing now with git merge. ;-) In fact,
> PB> ideally the whole change in my scripts when your script is finished
> PB> would be replacing
>
> PB> checkout-cache `diff-tree` # symbolic
> PB> git diff $base $merged | git apply
>
> PB> with
>
> PB> merge-tree.pl -b $base $(tree-id) $merged | parse-your-output
>
> In the above I presume by $merged you mean the tree ID (or
> commit ID) the user's working directory is based upon? Well,
> merge-trees (Linus has a single directory merge-tree already)
> looks at tree IDs (or commit IDs); it would never involve
> working files in random state that is not recorded as part of a
> tree (committed or not). Given that constraints I am not sure
> how well that would pan out. I have to think about this a bit.
No, $(tree-id) is the "destination branhc", what the user directory is
based upon; $merged is the branch you are merging now, relative to
$base. When I throw away the useless "-b" argument, in practice it would
look like
merge-trees abcd 1234 5678
for doing
/------ 1234 -+-
abcd < /
\------ 5678
(not that the order of 1234 and 5678 would actually really matter)
I fear I don't understand the rest of your paragraph. :-(
> I do like, however, the idea of separating the step of doing any
> checkout/merge etc. and actually doing them. So the command set
> of parse-your-output needs to be defined. Based on what I have
> done so far, it would consist of the following:
>
> - Result is this object $SHA1 with mode $mode at $path (takes
> one of the trees); you can do update-cache --cacheinfo (if
> you want to muck with dircache) or cat-file blob (if you want
> to get the file) or both.
>
> - Result is to delete $path.
>
> - Result is a merge between object $SHA1-1 and $SHA1-2 with
> mode $mode-1 or $mode-2 at $path.
>
> Would this be a good enough command set?
What about the conflicts? Like one tree deleting, other tree modifying?
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: space compression (again)
From: Ray Heasman @ 2005-04-15 19:33 UTC (permalink / raw)
To: git
For for this email not threading properly, I have been lurking on the
mail list archives and just had to reply to this message.
I was planning to ask exactly this question, and Scott beat me to to. I
even wanted to call them "chunks" too. :-)
It's probably worthwhile for anyone discussing this subject to read this
link: http://www.cs.bell-labs.com/sys/doc/venti/venti.pdf . I know it's
been posted before, but it really is worth reading. :-)
On Fri, 15 Apr 2005, Linus Torvalds wrote:
> On Fri, 15 Apr 2005, C. Scott Ananian wrote:
> >
> > Why are blobs per-file? [After all, Linus insists that files are an
> > illusion.] Why not just have 'chunks', and assemble *these*
> > into blobs (read, 'files')? A good chunk size would fit evenly into some
> > number of disk blocks (no wasted space!).
>
> I actually considered that. I ended up not doing it, because it's not
> obvious how to "block" things up (and even more so because while I like
> the notion, it flies in the face of the other issues I had: performance
> and simplicity).
I don't think it's as bad as you think.
Let's conceptually have two types of files - Pobs (Proxy Objects, or
Pointer Objects), and chunks. Both are stored and referenced by their
content hash, as usual. Pobs just contain a list of hashes referencing
the chunks in a file. When a file is initially stored, we chunk it so
each chunk fits comfortably in a block, but otherwise we aren't too
critical about sizes. When a file is changed (say, a single line edit),
we update the chunk that contains that line, hash it and store it with
its new name, and update the Pob, which we rehash and restore. If a
chunk grows to be very large (say > 2 disk blocks), we can rechunk it
and update the Pob to include the new chunks.
> The problem with chunking is:
> - it complicates a lot of the routines. Things like "is this file
> unchanged" suddenly become "is this file still the same set of chunks",
> which is just a _lot_ more code and a lot more likely to have bugs.
You're half right; it will be more complex, but I don't think it's as
bad as you think. Pobs are stored by hash just like anything else. If
some chunks are different, the pob is different, which means it has a
different hash. It's exactly the same as dealing with changed file now.
Sure, when you have to fetch the data, you have to read the pob and get
a list of chunks to concatenate and return, but your example given
doesn't change.
> - you have to find a blocking factor. I thought of just going it fixed
> chunks, and that just doesn't help at all.
Just use the block size of the filesystem. Some filesystems do tail
packing, so space isn't an issue, though speed can be. We don't actually
care how big a chunk is, except to make it easy on the filesystem.
Individual chunks can be any size.
> - we already have wasted space due to the low-level filesystem (as
> opposed to "git") usually being block-based, which means that space
> utilization for small objects tends to suck. So you really want to
> prefer objects that are several kB (compressed), and a small block just
> wastes tons of space.
If a chunk is smaller than a disk block, this is true. However, if we
size it right this is no worse than any other file. Small files (less
than a block) can't be made any larger, so they waste space anyway.
Large files end up wasting space in one block unless they are a perfect
multiple of the block size.
When we increase the size of a chunk, it will waste space, but we would
have created an entire new file, so we win there too.
Admittedly, Pobs will be wasting space too.
On the other hand, I use ReiserFS, so I don't care. ;-)
> - there _is_ a natural blocking factor already. That's what a file
> boundary really is within the project, and finding any other is really
> quite hard.
Nah. I think I've made a good case it isn't.
> So I'm personally 100% sure that it's not worth it. But I'm not opposed to
> the _concept_: it makes total sense in the "filesystem" view, and is 100%
> equivalent to having an inode with pointers to blocks. I just don't think
> the concept plays out well in reality.
Well, the reason I think this would be worth it is that you really win
when you have multiple parallel copies of a source tree, and changes are
cheaper too. If you store all the chunks for all your git repositories
in one place, and otherwise treat your trees of Pobs as the real
repository, your copied trees only cost you space for the Pobs.
Obviously this also applies for file updates within past revisions of a
tree, but I don't know how much it would save. It fits beautifully into
the current abstraction, and saves space without having to resort to
rolling hashes or xdeltas.
The _real_ reason why I am excited about git is that I have a vision of
using this as the filesystem (in a FUSE wrapper or something) for my
home directory. MP3s and AVIs aside, it will make actual work much
easier for me. I have a dream; a dream where I save files using the same
name, safe in the knowledge that I can get to any version I want. I will
live in a world of autosaves, deletes without confirmation, and /etcs
immune from the vagaries of my package management systems, not to
mention users not asking me leading questions about backups. *sigh*
*sniff* Excuse me, I think I have to go now.
-Ray
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Paul Jackson @ 2005-04-15 19:20 UTC (permalink / raw)
To: Linus Torvalds; +Cc: dwmw2, junkio, pasky, git
In-Reply-To: <Pine.LNX.4.58.0504150753440.7211@ppc970.osdl.org>
These notions that one can always best answer questions by looking at
the content, and that "Individual files DO NOT EXIST" seem over stated,
to me.
Granted, overstated for a good reason. A couple sticks of dynamite are
needed to shake loose some old SCM thinking habits.
===
Ingo has a point when he states:
> i believe the fundamental thing to think about is not file or line or
> namespace, but 'tracking developer intent'.
He too overstates - it's not _the_ (as in one and only) thing.
But it's useful. Given the traditional terseness of many engineers,
it's certainly not the _only_ thing. The code speaks too.
===
The above two are related in this way. Traditional SCM uses per
file (versioned controlled file, as in s.* or *,v files) metadata
to track 'developer intent'.
I'm afraid we are at risk for confusing baby (developer intent)
and bathwater (version controlled file structure of classic SCM's).
===
But we already have a pretty damn good way of tracking developer
intent that needs to fit naturally with whatever we build on top
of git.
Mr. McGuire: I just want to say one word to you - just one word.
Ben: Yes sir.
Mr. McGuire: Are you listening?
Ben: Yes I am.
Mr. McGuire: 'Patches.'
# the original word was 'Plastics' - The Graduate (1967)
Andrew and the other maintainers do a pretty good job of 'encouraging'
developers to provide useful statements of 'intent' in their patch
headers.
The patch series in something like *-mm, including per-patch
commentary, are a valuable part of this project.
===
I have not looked closely at what is being done here, on top of
git, for SCM like capabilities. Hopefully the next two questions
are not too stupid:
1) How do we track the patch header commentary?
2) Why can't we have a quilt like SCM, not bk/rcs/cvs/sccs/... like?
For (2), anyone publishing a Linux source would periodically announce an
<sha1> value, attached to some name suitable for public consumption.
For example, sometime in the next month or so, Linus would announce
that the <sha1> of 2.6.12 is so-and-so. That would identify the
result of applying a specific set of patches, resulting in a specific
source tree contents. He would announce a few 2.6.12-rc* <sha1>'s
between now and then.
Between now and then, Andrew would (if using these tools) have published
several <sha1> values, one each for various 2.6.12-rc*-mm* versions.
If you explode such a <sha1> all out into a working directory, you get
both the source contents in the appropriately named files, and the
quilt-style patches subdirectory, of the patch series that gets you
here, starting from some Time Zero for that series of published kernel
versions.
--
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <pj@engr.sgi.com> 1.650.933.1373, 1.925.600.0401
^ permalink raw reply
* Re: space compression (again)
From: Linus Torvalds @ 2005-04-15 19:11 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: git
In-Reply-To: <Pine.LNX.4.61.0504151437100.27637@cag.csail.mit.edu>
On Fri, 15 Apr 2005, C. Scott Ananian wrote:
>
> So I guess I'll have to implement this and find out, won't I? =)
The best way to shup somebody up is always to just do it, and say "hey, I
told you so". It's hard to argue with numbers.
Linus
^ permalink raw reply
* Re: space compression (again)
From: Derek Fawcus @ 2005-04-15 19:00 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.61.0504151437100.27637@cag.csail.mit.edu>
On Fri, Apr 15, 2005 at 02:45:55PM -0400, C. Scott Ananian wrote:
> > - we already have wasted space due to the low-level filesystem (as
> > opposed to "git") usually being block-based, which means that space
> > utilization for small objects tends to suck. So you really want to
> > prefer objects that are several kB (compressed), and a small block just
> > wastes tons of space.
>
> Not on (say) reiserfs, and not over the network. I'm proposing (at the
> moment) easy conversion from chunked to unchunked disk representation,
> so that you can leave things unchunked if (for example) you know you're
> running ext2 with a large block size.
Or if one does not care about space, and simply want's speed, add another
layer of indirection - a flattened container object which has hashses as
normal, then as it's content simply has the 'chunk list object' and the
'chunk objects' concatenated.
It's then a per user / database as to if the flattened objects, or the
heirarcal objects are storred locally.
DF
^ permalink raw reply
* Re: Re: write-tree is pasky-0.4
From: Petr Baudis @ 2005-04-15 18:56 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0504151138490.7211@ppc970.osdl.org>
Dear diary, on Fri, Apr 15, 2005 at 08:44:02PM CEST, I got a letter
where Linus Torvalds <torvalds@osdl.org> told me that...
> And I merged your "Add -z option to show-files", but you had based your
> other patches on Petr's tree which due to my other changes is not going to
> merge totally cleanly with mine, so I'm wondering if you might want to try
> to re-merge your mergepoint stuff against my current tree? That way I can
> continue to maintain a set of "core files", and Pasky can maintain the
> "usable interfaces" part..
Actually, I wanted to ask about this. :-)
So, I assume that you don't want to merge my "SCM layer" (which is
perfectly fine by me). However, I also apply plenty of patches
concerning the "core git" - be it portability, leak fixes, argument
parsing fixes and so on.
Would it be of any benefit if I maintained two trees, one with just your
core git but what I merge (I think I'd call this branch git-pb), and one
with my git-pasky (to be renamed to Cogito) layer. I'd then put the
"core git" changes to the git-pb branch and pull from it to the Cogito
branch regularily, but it should be safe for you to pull from it too.
In fact, in that case I might even end up entirely separating the Cogito
tools from the core git and distributing them independently.
BTW, just out of interest, are you personally planning to use Cogito for
your kernel and sparse (and possibly even git) work, or will you stay
with your lowlevel plumbing for that?
Thanks,
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: space compression (again)
From: Derek Fawcus @ 2005-04-15 18:50 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu>
On Fri, Apr 15, 2005 at 01:19:30PM -0400, C. Scott Ananian wrote:
> Why are blobs per-file? [After all, Linus insists that files are an
> illusion.] Why not just have 'chunks', and assemble *these*
> into blobs (read, 'files')? A good chunk size would fit evenly into some
> number of disk blocks (no wasted space!).
[ I've only been earwigging, not paying a lot of attention, however ...]
Funny I was just think of this having read Linus' discourse on
"files don't matter", the obvious chunking factor would be say
a function.
The problem being tending towards having very small files - I know
I tend to prefer small functions. Hmm - a underlying filesystem that
efficiently stores small files - why does that ring a bell :-)
However the simple answer is to have a preparser for a file / tree
checkin which split say a .c file into it's associated chunks, anf
represented it in git as a signed/hashed object. i.e. a automatically
created extra level of indirection (as I seem to recall was added
somewhere else?).
So say fred.c:
/*
* File boiler
*/
#include <guff>
#include <more guff>
/*
* Fn a boiler
*/
int fn_a(args) {
}
/*
* Fn b boiler
*/
long fn_b(args) {
}
Would be split into 4 parts within git, the 'file object' which simply
points to the content objects, and 3 contents objects, being the stuff
before 'Fn a boiler', fn_a and it's boiler, fn_b and it's boiler.
The interesting bit is needing a preprocessor which can roughly parse
the code - i.e. detect where to place the boiler blocks.
You would then do most of your tree operations upon the file objects,
but get the space savings from the content objects being shared.
I suspect that simply to prevent pathological conditions you'd have to
arrange that the contents objects have a minimal size, irrespective
of the number of desired chunks (functions) they would naturally
contain. i.e. for compresion efficiency, you may choose something like
2K as the minimal pre compression content object size.
DF
^ permalink raw reply
* Re: space compression (again)
From: C. Scott Ananian @ 2005-04-15 18:45 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0504151117360.7211@ppc970.osdl.org>
On Fri, 15 Apr 2005, Linus Torvalds wrote:
> The problem with chunking is:
> - it complicates a lot of the routines. Things like "is this file
> unchanged" suddenly become "is this file still the same set of chunks",
> which is just a _lot_ more code and a lot more likely to have bugs.
The blob still has the same hash; therefore the file is still the same.
Nothing looks inside blobs; they just want either the hash or the full
contents (if I understand the algorithms correctly).
I agree it's more code, but I think it can be nicely layered.
> - you have to find a blocking factor. I thought of just going it fixed
> chunks, and that just doesn't help at all.
rsync uses a fixed chunk size, but this chunk can start at any offset (ie,
not constrained to fixed boundaries). This means that adding a single
line to the file works like you'd expect, even though all the chunk
boundaries change. [I think this is what you're talking about.]
> - we already have wasted space due to the low-level filesystem (as
> opposed to "git") usually being block-based, which means that space
> utilization for small objects tends to suck. So you really want to
> prefer objects that are several kB (compressed), and a small block just
> wastes tons of space.
Not on (say) reiserfs, and not over the network. I'm proposing (at the
moment) easy conversion from chunked to unchunked disk representation,
so that you can leave things unchunked if (for example) you know you're
running ext2 with a large block size.
> - there _is_ a natural blocking factor already. That's what a file
> boundary really is within the project, and finding any other is really
> quite hard.
Well, yes, it may be nontrivial. But 'quite hard' depends on your
perspective, I guess. Given a cache of existing chunks, it's just a
few table lookups. =)
> So I'm personally 100% sure that it's not worth it. But I'm not opposed to
> the _concept_: it makes total sense in the "filesystem" view, and is 100%
> equivalent to having an inode with pointers to blocks. I just don't think
> the concept plays out well in reality.
So I guess I'll have to implement this and find out, won't I? =)
--scott
AMLASH overthrow SDI Suharto HBDRILL SMOTH SUMAC SYNCARP kibo Blair
Diplomat Kojarena CIA cracking counter-intelligence CABOUNCE anthrax
( http://cscott.net/ )
^ permalink raw reply
* Re: write-tree is pasky-0.4
From: Linus Torvalds @ 2005-04-15 18:44 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Petr Baudis, git
In-Reply-To: <7vaco0i3t9.fsf_-_@assigned-by-dhcp.cox.net>
On Fri, 15 Apr 2005, Junio C Hamano wrote:
>
> Linus, sorry for bothering you with a false alarm. The problem
> turns out to be introduced in pasky-0.4 and does not exist in
> your HEAD.
Hey, all the code I write is always perfect, of course ;)
That said, I'm having some trouble merging with your perfect code,
especially since I decided that Russell's "always big-endian" thing was
definitely the right way to go (but ended up doing it slightly
differently).
I did my own version of "upcate-cache --cacheinfo", although mine is a bit
more anal, and if you add a new filename it wants that "--add" flag in
there first (why? I really like to make sure that people who add or remove
files from the cache say so explicitly, so that there are no surprises).
Otherwise it should be compatible with yours.
And I merged your "Add -z option to show-files", but you had based your
other patches on Petr's tree which due to my other changes is not going to
merge totally cleanly with mine, so I'm wondering if you might want to try
to re-merge your mergepoint stuff against my current tree? That way I can
continue to maintain a set of "core files", and Pasky can maintain the
"usable interfaces" part..
Linus
^ permalink raw reply
* Re: space compression (again)
From: Linus Torvalds @ 2005-04-15 18:34 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: git
In-Reply-To: <Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu>
On Fri, 15 Apr 2005, C. Scott Ananian wrote:
>
> Why are blobs per-file? [After all, Linus insists that files are an
> illusion.] Why not just have 'chunks', and assemble *these*
> into blobs (read, 'files')? A good chunk size would fit evenly into some
> number of disk blocks (no wasted space!).
I actually considered that. I ended up not doing it, because it's not
obvious how to "block" things up (and even more so because while I like
the notion, it flies in the face of the other issues I had: performance
and simplicity).
The problem with chunking is:
- it complicates a lot of the routines. Things like "is this file
unchanged" suddenly become "is this file still the same set of chunks",
which is just a _lot_ more code and a lot more likely to have bugs.
- you have to find a blocking factor. I thought of just going it fixed
chunks, and that just doesn't help at all.
- we already have wasted space due to the low-level filesystem (as
opposed to "git") usually being block-based, which means that space
utilization for small objects tends to suck. So you really want to
prefer objects that are several kB (compressed), and a small block just
wastes tons of space.
- there _is_ a natural blocking factor already. That's what a file
boundary really is within the project, and finding any other is really
quite hard.
So I'm personally 100% sure that it's not worth it. But I'm not opposed to
the _concept_: it makes total sense in the "filesystem" view, and is 100%
equivalent to having an inode with pointers to blocks. I just don't think
the concept plays out well in reality.
Linus
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox