From: Junio C Hamano <hidden> Date: 2017-10-01 03:27:12
Jeff Hostetler [off-list ref] writes:
On 9/29/2017 7:12 PM, Johannes Schindelin wrote:
quoted
Therefore, it would be good to have a way to tell Git about renames
explicitly so that it does not even need to use its heuristics.
Agreed.
It would be nice if every file (and tree) had a permanent GUID
associated with it. Then the filename/pathname becomes a property
of the GUIDs. Then you can exactly know about moves/renames with
minimal effort (and no guessing).
I actually like the idea to have a mechanism where the user can give
hint to influence, or instruction to dictate, how Git determines
"this old path moved to this new path" when comparing two trees. A
human would not consider a new file (e.g. header file) that begins
with a few dozen commonly-seen boilerplate lines (e.g. copyright
statement) followed by several lines unique to the new contents to
be a rename of a disappearing old file that begins with the same
boilerplate followed by several lines that are different from what
is in the new file, but Git's algorithm would give equal weight to
all of these lines when deciding how similar the new file is to the
old file, and can misidentify a new file to be a rename of an old
file that is unrelated. Even when Git can and does determine the
pairing correctly, it would be a win if we do not have to recompute
the same pairing every time. So both as hint and as cache, such a
mechanism would make sense [*1*].
But "file ID" does not have any place to contribute to such a
mechanism. Each of two developers working on the same project in a
disributed environment can grab the same gist and create a new file
in his or her tree, perhaps at the same path or at a different
path. At the time of such an addition, there is no way for each of
them to give these two files the same "file ID" (that is how the
world works in the distributed environment after all)---which "file
ID" should survive when their two histories finally meet and results
in a single file after a merge? A file with "file ID" may not be
renamed but may be copied and evolve separately and differently.
Which one should inherit its original "file ID" and how does having
"file ID" help us identify the other one is equally related to the
original file? These two are merely examples that "file ID"s would
cause while solving "only" what can be expressed in "git diff -M"
output (the latter illustrates that it does not even help showing
"git diff -C").
And when we stop limiting ourselves to the whole-file renames and
copies (which can be expressed in "git diff" output) but also want
to help finer-grained operation like "git blame", we'd want to have
something that helps in situations like a single file's contents
split into multiple files and multiple files' contents concatenated
into a single new file, both of which happens during code
refactoring. "file ID" would not contribute an iota in helping
these situations.
I've said this number of times, and I'll say this again, but one of
the most important message in our list archive is gmane:217 aka
https://public-inbox.org/git/Pine.LNX.4.58.0504150753440.7211@ppc970.osdl.org/
I'd encourge people to read and re-read that message until they can
recite it by heart.
Linus mentions "CVS annotate"; the message was written long before
we had "git blame", and it served as a guide when desiging how we
dig contents movement in various parts of the system.
[Footnote]
*1* There are many possible implementations; the most obvious would
be to record a pair of blob object names and instruct Git when
it seems one side of a pair disappearing and the other side of
the pair appearing, take the pair as a rename. And that would
be sufficient for "git log -M".
Such a cache/hint alone however would not help much in "git
merge" without further work, as we merge using only the tree
state of the three points in the history (i.e. the common
ancestor and two tips). merge-recursive needs to be taught to
find the renames at each commit it finds throughout the history
from the ancestor and each tip and carry its finding through if
it wants to take advantage of such hint/cache.
From: Stefan Beller <hidden> Date: 2017-10-02 17:41:47
quoted
It would be nice if every file (and tree) had a permanent GUID
associated with it. Then the filename/pathname becomes a property
of the GUIDs. Then you can exactly know about moves/renames with
minimal effort (and no guessing).
I have rethought about the idea of GUIDs as proposed by Jeff and wanted
to give a reply. After rereading this message, I think my thoughts are
already included via:
- you're doing the work at the wrong point for _another_ reason. You're
freezing your (crappy) algorithm at tree creation time, and basically
making it pointless to ever create something better later, because even
if hardware and software improves, you've codified that "we have to
have crappy information".
--
My design proposal for these "rename hints" would be a special trailer,
roughly:
Rename: LICENSE -> legal.txt
Rename: t/* -> tests/*
or more generally:
Rename: <pathspec> <delim> <pathspec>
This however has multiple issues due to potential
human inaccuracies:
(A) typos in the trailer key or in the pathspec
(resulting in different error modes)
(B) partial hints (We currently have a world of
completely missing hints, so I would not expect it to
be worse?)
(C) wrong hints. This ought to be no problem as Git would
take some CPU time to conclude the hint was bogus.
For (A), I would imagine we want a mechanism (e.g. notes)
to "correct" the hints. This is the similar issue as a typo in a
commit message, which we currently just ignore if the
commit has been merged to e.g. master.
So maybe we'd just design around that, giving the option
to give the correct hints via command line.
So if the commit has the typo'd hint
Remame: t/* -> tests/*
the human would see that (and also conclude that by
the commit message), and then invoke
git log -C -C-hint="t/* -> tests/*" ...
which would have the corrected hint and hence deliver
the best output.
Maybe the "-C-hint" flag is the best starting point when
going in that direction?
Thanks,
Stefan
From: Jeff Hostetler <hidden> Date: 2017-10-02 18:51:33
On 10/2/2017 1:41 PM, Stefan Beller wrote:
quoted
quoted
It would be nice if every file (and tree) had a permanent GUID
associated with it. Then the filename/pathname becomes a property
of the GUIDs. Then you can exactly know about moves/renames with
minimal effort (and no guessing).
I have rethought about the idea of GUIDs as proposed by Jeff and wanted
to give a reply. After rereading this message, I think my thoughts are
already included via:
- you're doing the work at the wrong point for _another_ reason. You're
freezing your (crappy) algorithm at tree creation time, and basically
making it pointless to ever create something better later, because even
if hardware and software improves, you've codified that "we have to
have crappy information".
--
My design proposal for these "rename hints" would be a special trailer,
roughly:
Rename: LICENSE -> legal.txt
Rename: t/* -> tests/*
or more generally:
Rename: <pathspec> <delim> <pathspec>
This however has multiple issues due to potential
human inaccuracies:
(A) typos in the trailer key or in the pathspec
(resulting in different error modes)
(B) partial hints (We currently have a world of
completely missing hints, so I would not expect it to
be worse?)
(C) wrong hints. This ought to be no problem as Git would
take some CPU time to conclude the hint was bogus.
For (A), I would imagine we want a mechanism (e.g. notes)
to "correct" the hints. This is the similar issue as a typo in a
commit message, which we currently just ignore if the
commit has been merged to e.g. master.
So maybe we'd just design around that, giving the option
to give the correct hints via command line.
So if the commit has the typo'd hint
Remame: t/* -> tests/*
the human would see that (and also conclude that by
the commit message), and then invoke
git log -C -C-hint="t/* -> tests/*" ...
which would have the corrected hint and hence deliver
the best output.
Maybe the "-C-hint" flag is the best starting point when
going in that direction?
Thanks,
Stefan
Sorry to re-re-...-re-stir up such an old topic.
I wasn't really thinking about commit-to-commit hints.
I think these have lots of problems. (If commit A->B does
"t/* -> tests/*" and commit B->C does "test/*.c -> xyx/*",
then you need a way to compute a transitive closure to see
the net-net hints for A->C. I think that quickly spirals
out of control.)
No, I was going in another direction. For example, if a
tree-entry contains { file-guid, file-name, file-sha, ... }
then when diffing any 2 commits, you can match up files
(and folders) by their guids. Renames pop out trivially when
their file-names don't match. File moves pop out when the
file-guids appear in different trees. Adds and deletes pop
out when file-guids don't have a peer. (I'm glossing over some
of the details, but you get the idea.) To address Junio's
question, independently added files with the same name will
have 2 different file-guids. We amend the merge rules to
handle this case and pick one of them (say, the one that
is sorts less than the other) as the winner and go on.
All-in-all the solution is not trivial (as there are a few
edge cases to deal with), but it better matches the (casual)
user's perception of what happened to their tree over time.
It also doesn't require expensive code to sniff for renames
on every command (which doesn't scale on really large repos).
But as I said before, that ship has passed...
Jeff
From: Stefan Beller <hidden> Date: 2017-10-02 19:19:05
On Mon, Oct 2, 2017 at 11:51 AM, Jeff Hostetler [off-list ref] wrote:
Sorry to re-re-...-re-stir up such an old topic.
I wasn't really thinking about commit-to-commit hints.
I think these have lots of problems. (If commit A->B does
"t/* -> tests/*" and commit B->C does "test/*.c -> xyx/*",
then you need a way to compute a transitive closure to see
the net-net hints for A->C. I think that quickly spirals
out of control.)
I agree. Though as a human I can still look at
A..C giving the hint that t/*.c and xyz/*.c ought to
be taken into account for rename detection.
(which is currently done with -M -C --find-copies-harder
as a generic "there are renamed things", and not the very
specific rule, that may be cheaper to examine compared to
these generic rules)
No, I was going in another direction. For example, if a
tree-entry contains { file-guid, file-name, file-sha, ... }
then when diffing any 2 commits, you can match up files
(and folders) by their guids. Renames pop out trivially when
their file-names don't match. File moves pop out when the
file-guids appear in different trees. Adds and deletes pop
out when file-guids don't have a peer. (I'm glossing over some
of the details, but you get the idea.)
How do you know when a guid needs adaption?
(c.f. origin/jt/packmigrate)
If a commit moves a function out of a file into a new file,
the ideal version control could notice that the function
was moved into a new file and still attribute the original
authors by ignoring the move commit.
Another series in flight could have modified that
function slightly (fixed a bug), such that it's hard to
reason about these things.
For guids I imagine the new file gets a new guid, such that
tracking the function becomes harder?
To address Junio's
question, independently added files with the same name will
have 2 different file-guids. We amend the merge rules to
handle this case and pick one of them (say, the one that
is sorts less than the other) as the winner and go on.
All-in-all the solution is not trivial (as there are a few
edge cases to deal with), but it better matches the (casual)
user's perception of what happened to their tree over time.
The GUID would be made up at creation time, I assume?
Is there any input other than the file itself? (I assumed so
initially, such that:
By having a GUID in the tree, we would divorce from the notion
of a "content addressable file system" quickly, as we both could
create the same tree locally (containing the same blobs) and
yet the trees would have different names due to having different
GUIDs in them
), which I'd find undesirable.
It also doesn't require expensive code to sniff for renames
on every command (which doesn't scale on really large repos).
I wonder if the rename detection could be offloaded to a server
(which scales) that provides a "hint file" to clients, such that the
clients can then cheaply make use of these specific hints.
From: Jeff Hostetler <hidden> Date: 2017-10-02 20:02:21
On 10/2/2017 3:18 PM, Stefan Beller wrote:
On Mon, Oct 2, 2017 at 11:51 AM, Jeff Hostetler [off-list ref] wrote:
quoted
Sorry to re-re-...-re-stir up such an old topic.
I wasn't really thinking about commit-to-commit hints.
I think these have lots of problems. (If commit A->B does
"t/* -> tests/*" and commit B->C does "test/*.c -> xyx/*",
then you need a way to compute a transitive closure to see
the net-net hints for A->C. I think that quickly spirals
out of control.)
I agree. Though as a human I can still look at
A..C giving the hint that t/*.c and xyz/*.c ought to
be taken into account for rename detection.
(which is currently done with -M -C --find-copies-harder
as a generic "there are renamed things", and not the very
specific rule, that may be cheaper to examine compared to
these generic rules)
quoted
No, I was going in another direction. For example, if a
tree-entry contains { file-guid, file-name, file-sha, ... }
then when diffing any 2 commits, you can match up files
(and folders) by their guids. Renames pop out trivially when
their file-names don't match. File moves pop out when the
file-guids appear in different trees. Adds and deletes pop
out when file-guids don't have a peer. (I'm glossing over some
of the details, but you get the idea.)
How do you know when a guid needs adaption?
I'm not sure I know what you mean by "adaption".
(c.f. origin/jt/packmigrate)
If a commit moves a function out of a file into a new file,
the ideal version control could notice that the function
was moved into a new file and still attribute the original
authors by ignoring the move commit.
I think that's an orthogonal problem. I could move a function
from one file to an existing file or to a new file it doesn't
matter. Attributing those lines back to the original author
(rather than the mover) is a bit of a pipe dream IMHO. And I
have to wonder if it is always the correct thing to do? I can
see scenarios where you'd want the mover.
I guess there's nothing from stopping the "ideal VC system"
doing all this line-based analysis, but that shouldn't make
file renames expensive to detect (since that is the granularity
that people and most tools expect the system to work with).
Another series in flight could have modified that
function slightly (fixed a bug), such that it's hard to
reason about these things.
For guids I imagine the new file gets a new guid, such that
tracking the function becomes harder?
Yeah, I'm not thinking about tracking individual functions.
quoted
To address Junio's
question, independently added files with the same name will
have 2 different file-guids. We amend the merge rules to
handle this case and pick one of them (say, the one that
is sorts less than the other) as the winner and go on.
All-in-all the solution is not trivial (as there are a few
edge cases to deal with), but it better matches the (casual)
user's perception of what happened to their tree over time.
The GUID would be made up at creation time, I assume?
Is there any input other than the file itself? (I assumed so
initially, such that:
By having a GUID in the tree, we would divorce from the notion
of a "content addressable file system" quickly, as we both could
create the same tree locally (containing the same blobs) and
yet the trees would have different names due to having different
GUIDs in them
), which I'd find undesirable.
Right. A real solution would store the guid data slightly
differently so we could preserve the existing SHA properties.
My example was more conceptual.
quoted
It also doesn't require expensive code to sniff for renames
on every command (which doesn't scale on really large repos).
I wonder if the rename detection could be offloaded to a server
(which scales) that provides a "hint file" to clients, such that the
clients can then cheaply make use of these specific hints.
I don't know. Might be easier to add that computation to the
occasional client-side housekeeping (somewhat like the commit
generation number computation we keep talking about).
Thanks
Jeff