Hi,
I am very interested in the project 'Line-level history browser',
after some days consideration, now I made up a draft of my proposal, I
think it is helpful to send it to the list before submitting it. Could
you please give me some advise?
-----------------------------------------------
Draft proposal: Line-level History Browser
=====Purpose of this project=====
"git blame" can tell us who is responsible for a line of code, but it
can't help if we want to get the detail of how the lines of code have
evolved as what it is now.
This project will add a new utility for git called 'git line-log'. It
can trace the history of any line range of certain file at any
revision. For simplity, users can run the command like: ' git line-log
builtin/diff.c 6..8 ', he will get the change history of code between
line 6 and line 8 of the diff.c file. And for each history entry, it
will provide the commits, the diff block which contains changes of
users' interested lines.
This utility will trace all the modification history of interested
lines and stop until it finds the root of the lines, which is a point
where all the new code is added from scratch. Also, the users can
specify how deeply he wants this utility to trace. And this tool will
treat code move just like modification too, so it will follow the code
move inside one file.
Note that, the history may not always be a single thread of commits.
If there are more than one commit which produce the specified line
range, the thread of history will split. And this utility will stop
and provide all commits with its code changes to the user, let the
user to select which one to trace next.
=====Work and technical issues=====
==Command options==
This new tool should be used for exploring the history of changes for
certain line range of code in one file.
git line-log [options] <file> <line range>
Options:
1. Since it will output commit description, it will contain the option
used to control whether we should show the whole commit message or
just a short title.
2. Option whether we should display only the 'user interested lines'
diff block [default] or display the whole diff with the interested
area colorfully displayed.
3. The max depth we trace into the commit history.
4. The revision of the <file>. This is very useful when the current
interested line range is produced by more than one commit. The user
can use this option to specify the file revision and trace down from
that revision and the line range.
<line range>
Its format should be <start pos>..<end pos> or just a <line number>.
==Design and implementation==
Git store all the blobs instead of code delta, so we should traverse
the commit history and directly access the tree/blob objects to
compute the code delta and search for the diff which contains the
interested lines. Since git use libxdiff to format its diff file, we
should iterate through all xdiff's diff blocks and find what the code
looks like before the commit. Here, we will find a new line range
which is the origin code before this commit. And then start another
search from the current commit and the new line range. Recursively, we
can find all the modification history. We will stop when we find that
the current interested line range is added from scratch and is not
moved from other place of the file. We may also stop the traverse when
we reach the max search depth. Also, if the thread of change history
split into two or more commits, we stop and provide the users all the
related commits and corresponding line range.
For implementation related stuff, this tool heavily depends on
libxdiff. Because we will search our interested lines through xdiff's
output to find the right diff trunk to display and trace down. So, how
we search the xdiff's diff blocks is very important. After reading
some libxdiff document and code, I find that libxdiff output all the
diff blocks as string into a memory file. If we parse the diff block
string to find the changed lines, it is very inefficient. So, I
suggest changing xdiff's xdl_diff function to let it store some meta
data for each diff trunk. I think this will be very helpful for the
performance of this tool.
Generally,
1. xdiff/xdiffi.c will get changed to make xdl_diff store some desired
meta data and pass it to caller.
2. builtin/line-log.c will be added to complete most of the new
features, the most important function here may be cmd_linelog.
3. git.c will be changed to add this new utility to the front end.
4. Documents will be updated to introduce this new tool.
=====About me=====
I am Bo Yang, a Chinese graduate student majoring in Computer Science
of NanKai University. I have touched some open source software since 5
years ago and began to contribute code to open source community from
three years ago. I have contributed to Mozilla/Mingw/Netsurf.
Technically, I am experienced in C/Bash Shell. I have attended last
year's GSoC with Netsurf project. In that project, I have completed
most of a DOM library in C.
I begin to use git for source code revision from about two years ago.
I use Git for track my Mozilla trunk source code. Because updating
Mozilla code by CVS in my school is very slow. So, I write one script
to automatically updating the trunk with CVS at mid-night, when the
network flow is fast, on the server, and then use Git to maintain the
code. Then I use Git in my PC to clone/update the source code from my
local server and that is very fast. I use Git to track my changes to
the code and some bug fixes. It is an excellent tool for
branch/history, I think.
Git is my lovely daily tool for revision control. I have much
experience with it and have read "Git Internals" and also get some
basic knowledge about Git's code base. And I think the line-level
history explorer is really suitable for me and I can make a good start
with this project in Git community.
-----------------------------------------------
Any feedback from you will be appreciated very much, thanks a lot!
Regards!
Bo
--
My blog: http://blog.morebits.org
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:48:27
Hi,
On Sat, 20 Mar 2010, Bo Yang wrote:
I am very interested in the project 'Line-level history browser', after
some days consideration, now I made up a draft of my proposal, I think
it is helpful to send it to the list before submitting it. Could you
please give me some advise?
I like it very much already! You obviously put in a substantial amount of
time to learn intricate details about the way Git operates, and what is
already available.
And you also provided a patch (unrelated to line-level history browser),
so you proved that you actually cloned Git, and that you can actually
patch it and use Git itself to send a patch to this list.
Very good.
Just a few constructive criticisms (inlined):
This project will add a new utility for git called 'git line-log'. It
can trace the history of any line range of certain file at any revision.
I think that that might be good for starters, but one could imagine that
an integration into "git log" might be even better, so that gitk can use
this without any further changes.
For simplity, users can run the command like: ' git line-log
builtin/diff.c 6..8 ', he will get the change history of code between
line 6 and line 8 of the diff.c file.
It would be good if the code looked harder after failing with the simple
strategy, such as looking for code removed in other files, fuzzy matching
(optional), and looking for code duplication (i.e. literal copying, or
slightly modified copying).
The fuzzy matching might be necessary to catch things like a Java class
moving from one file into another (and changing its name): the first line
changes, but not completely.
After reading some libxdiff document and code, I find that libxdiff
output all the diff blocks as string into a memory file.
Almost.
Just have a look at the word-level diff (--color-words):
http://repo.or.cz/w/git/dscho.git/blob/bc1ed6aafd9ee4937559535c66c8bddf1864bec6:/diff.c#l382
You will see that there is a function fn_out_diff_words_aux(), which is
passed to xdi_diff_outf(). That latter function calls xdiff such that the
former function receives a complete line at a time. And this is what I
would suggest doing in the line-level log, too.
Ciao,
Dscho
I like it very much already! You obviously put in a substantial amount of
time to learn intricate details about the way Git operates, and what is
already available.
And you also provided a patch (unrelated to line-level history browser),
so you proved that you actually cloned Git, and that you can actually
patch it and use Git itself to send a patch to this list.
I am very happy you like it.
I think that that might be good for starters, but one could imagine that
an integration into "git log" might be even better, so that gitk can use
this without any further changes.
So, I think add some new options to 'git log' is preferred.
It would be good if the code looked harder after failing with the simple
strategy, such as looking for code removed in other files, fuzzy matching
(optional), and looking for code duplication (i.e. literal copying, or
slightly modified copying).
The fuzzy matching might be necessary to catch things like a Java class
moving from one file into another (and changing its name): the first line
changes, but not completely.
That's really a good idea.
So, when the program reach the end of the history thread of some
changes of line range, it should not stop immediately. It then should
make a harder code search and try to find whether the new add lines of
code is moved to there or just copied from other place to there. And
these kind of search should use fuzzy matching instead of exact string
matching.
But notice that, detect code movement in one commit is much efficient
than detecting code copy. So, I think we should add an option to
control whether we detect such kind of code copy. By default, we
detect code move but not code copy. How do you think about this?
Just have a look at the word-level diff (--color-words):
http://repo.or.cz/w/git/dscho.git/blob/bc1ed6aafd9ee4937559535c66c8bddf1864bec6:/diff.c#l382
You will see that there is a function fn_out_diff_words_aux(), which is
passed to xdi_diff_outf(). That latter function calls xdiff such that the
former function receives a complete line at a time. And this is what I
would suggest doing in the line-level log, too.
I have look over the function fn_out_diff_words_aux, this function
parse each line of a memory diff. We can use it to detect the diff
hunk head and find the line change. If you think the performance is
acceptable, I think using this callback mechanism is all right.
Regards!
Bo
--
My blog: http://blog.morebits.org
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:48:27
Hi,
[please do not cull the Cc: list]
On Sat, 20 Mar 2010, Bo Yang wrote:
I (Johannes) wrote:
quoted
I think that that might be good for starters, but one could imagine
that an integration into "git log" might be even better, so that gitk
can use this without any further changes.
So, I think add some new options to 'git log' is preferred.
Yes, I think that this should be the target for the user interface.
However, the logic should be different enough to merit a completely new
file for the code (think "git add --interactive").
quoted
It would be good if the code looked harder after failing with the
simple strategy, such as looking for code removed in other files,
fuzzy matching (optional), and looking for code duplication (i.e.
literal copying, or slightly modified copying).
The fuzzy matching might be necessary to catch things like a Java
class moving from one file into another (and changing its name): the
first line changes, but not completely.
That's really a good idea.
So, when the program reach the end of the history thread of some
changes of line range, it should not stop immediately. It then should
make a harder code search and try to find whether the new add lines of
code is moved to there or just copied from other place to there. And
these kind of search should use fuzzy matching instead of exact string
matching.
But notice that, detect code movement in one commit is much efficient
than detecting code copy. So, I think we should add an option to
control whether we detect such kind of code copy. By default, we
detect code move but not code copy. How do you think about this?
Yes, it is much more difficult, and it is more expensive. So: there are
several steps in the project (you could also call them "milestones"), and
fuzzy matching end lines would come later than simple code movement. And
still later than code movement between files.
quoted
Just have a look at the word-level diff (--color-words):
http://repo.or.cz/w/git/dscho.git/blob/bc1ed6aafd9ee4937559535c66c8bddf1864bec6:/diff.c#l382
You will see that there is a function fn_out_diff_words_aux(), which
is passed to xdi_diff_outf(). That latter function calls xdiff such
that the former function receives a complete line at a time. And this
is what I would suggest doing in the line-level log, too.
I have look over the function fn_out_diff_words_aux, this function parse
each line of a memory diff. We can use it to detect the diff hunk head
and find the line change. If you think the performance is acceptable, I
think using this callback mechanism is all right.
Yes, I think that the performance is alright there, it works well enough
for --color-words.
Thanks,
Dscho
From: Alex Riesen <hidden> Date: 2016-06-15 22:48:28
On Sat, Mar 20, 2010 at 10:18, Bo Yang [off-list ref] wrote:
<line range>
Its format should be <start pos>..<end pos> or just a <line number>.
You might want to reconsider the line range syntax. Exactly the same syntax
is already used to specify a commit range, so reusing it may lead to confusion.
From: A Large Angry SCM <hidden> Date: 2016-06-15 22:48:28
Alex Riesen wrote:
On Sat, Mar 20, 2010 at 10:18, Bo Yang [off-list ref] wrote:
quoted
<line range>
Its format should be <start pos>..<end pos> or just a <line number>.
You might want to reconsider the line range syntax. Exactly the same syntax
is already used to specify a commit range, so reusing it may lead to confusion.
I, actually, think the proposed line range syntax works because it uses
the same _range_ notation. The issue is how to differentiate the _line_
range(s) from the _commit_ range(s); and, yes, I would like multiple
ranges of each type as well as multiple files.
So, I think add some new options to 'git log' is preferred.
Yes, I think that this should be the target for the user interface.
However, the logic should be different enough to merit a completely new
file for the code (think "git add --interactive").
So, a new file builtin/line-level.c will be added.
Yes, it is much more difficult, and it is more expensive. So: there are
several steps in the project (you could also call them "milestones"), and
fuzzy matching end lines would come later than simple code movement. And
still later than code movement between files.
Ok, I will add some milestones on my next version proposal, thanks.
Regards!
Bo
On Sun, Mar 21, 2010 at 5:58 AM, A Large Angry SCM [off-list ref] wrote:
Alex Riesen wrote:
quoted
On Sat, Mar 20, 2010 at 10:18, Bo Yang [off-list ref] wrote:
quoted
<line range>
Its format should be <start pos>..<end pos> or just a <line number>.
You might want to reconsider the line range syntax. Exactly the same
syntax
is already used to specify a commit range, so reusing it may lead to
confusion.
I, actually, think the proposed line range syntax works because it uses the
same _range_ notation. The issue is how to differentiate the _line_ range(s)
from the _commit_ range(s); and, yes, I would like multiple ranges of each
type as well as multiple files.
As what I said in previous post, I think we should adopt 'git blame'
way. Use a '-L <start pos>,<end pos>' to specify the line range. It
support both line number and posix regex.
For multiple ranges stuff, I don't think it is very useful to support
it for a history browser. Anyway, our users can only focus on one line
of thread history. I am very willing to listen what is your use case
for a multiple ranges?
Thanks for your precious advice!
Regards!
Bo
From: A Large Angry SCM <hidden> Date: 2016-06-15 22:48:28
Bo Yang wrote:
[...]
For multiple ranges stuff, I don't think it is very useful to support
it for a history browser. Anyway, our users can only focus on one line
of thread history. I am very willing to listen what is your use case
for a multiple ranges?
More than one line range can be related and of interest to a
forensics/archeology task.
In a simple multi range case, you'd have 2 line ranges in the same file
that you want to see the history and graph of. Such as 2 related macro
definitions in a header file.
In a complex multi range case, you'd have many line ranges spread over
multiple blobs and some of the blobs have disjoint commit graphs.
The complex multi range case may be too much for a GSOC project, and the
simple multi range case may be also. However, the command syntax should
be general enough to handle them without being too ugly so that the
implementation could be improved and expanded later.
On Sun, Mar 21, 2010 at 9:19 PM, A Large Angry SCM [off-list ref] wrote:
Bo Yang wrote:
[...]
quoted
For multiple ranges stuff, I don't think it is very useful to support
it for a history browser. Anyway, our users can only focus on one line
of thread history. I am very willing to listen what is your use case
for a multiple ranges?
More than one line range can be related and of interest to a
forensics/archeology task.
In a simple multi range case, you'd have 2 line ranges in the same file that
you want to see the history and graph of. Such as 2 related macro
definitions in a header file.
In a complex multi range case, you'd have many line ranges spread over
multiple blobs and some of the blobs have disjoint commit graphs.
The complex multi range case may be too much for a GSOC project, and the
simple multi range case may be also. However, the command syntax should be
general enough to handle them without being too ugly so that the
implementation could be improved and expanded later.
Yeah, how do you think use the following syntax:
<file1>@<rev1>:<start pos>,<end pos> <file2>@<rev2>:<start pos>,<end pos>
Thanks!
Regards!
Bo
Hi all,
Thanks a lot for your precious advice and based on that, I have
prepared a new version of my proposal, generally it provide a detailed
options which I want to add to 'git log' and a new syntax for
supporting multi line ranges in any file at any revision. Also, this
version provide a milestones and timeline for this project. Thanks
again for your advice and I appreciate your feedback very much for
this version.
-----------------------------------------------------------------------
Draft proposal(v2): Line-level History Browser
=====Purpose of this project=====
"git blame" can tell us who is responsible for a line of code, but it
can't help if we want to get the detail of how the lines of code have
evolved as what it is now.
This project will add a new feature for 'git log' to display line
level history. It can trace the history of any line range of certain
file at any revision. For simplity, users can run the command like: '
git log -L builtin/diff.c:6,8 ', he will get the change history of
code between line 6 and line 8 of the diff.c file. And for each
history entry, it will provide the commits, the diff block which
contains changes of users' interested lines.
This utility will trace all the modification history of interested
lines and stop until it finds the root of the lines, which is a point
where all the new code is added from scratch. Also, the users can
specify how deeply he wants this utility to trace. And this tool will
treat code move just like modification too, so it will follow the code
move inside one commit.
Note that, the history may not always be a single thread of commits.
If there are more than one commit which produce the specified line
range, the thread of history will split. And this utility will stop
and provide all commits with its code changes to the user, let the
user to select which one to trace next.
=====Work and technical issues=====
==Command options==
This new feature should be used for exploring the history of changes
for certain line range of code in one file.
git log [-m<num>] [-I] [-d depth] [--fuzzy] -L file1@rev1:<start
pos>,<end pos> file2@rev2:<start pos>,<end pos>
Options:
1. -m<num>, option to control whether we should follow code movement.
If one -m is given, we follow code movement inside file, when more
than one '-m' is given, we follow the movement between files in one
commit. The <num> is used to specify the lower bound for the number of
lines of moved code. If it is not given, we set it as 1.
2. -I, option to control whether we should display only the 'user
interested lines' diff block [default] or display the whole diff with
the interested area colorfully displayed.
3. -d, option to control the max depth we trace into the commit history.
4. --fuzzy, option to control whether fuzzy code copy mathing is used.
5. '-L' to control whether we run a simple log or we want a line level log.
6. Files and lines. I propose to use such a syntax to specify the
files at revision and line range, <file>@<revision>:<start pos>,<end
pos>. This looks a little complex, but I think it is neccessary
because we will support multiple file at any version and any line
range finally. The revision can be any revision format of Git and the
<pos> can be a number, or a posix regex, just like what 'git blame'
do.
7. And we will support code copy detect, too. The option which control
whether we trace code copy does exist in current 'git log', which is
the option '-C'. Similiarly, one '-C' is used to trace code copy of
new added code inside one commit. Two '-C' will trace any code copy
inside commit tree.
==Design and implementation==
Git store all the blobs instead of code delta, so we should traverse
the commit history and directly access the tree/blob objects to
compute the code delta and search for the diff which contains the
interested lines. Since git use libxdiff to format its diff file, we
should iterate through all xdiff's diff blocks and find what the code
looks like before the commit. This will be done using the callback
mechanism. Here, we will find a new line range which is the origin
code before this commit. And then start another search from the
current commit and the new line range. Recursively, we can find all
the modification history. We will stop when we find that the current
interested line range is added from scratch and is not moved from
other place of the file. Here, if the user want to trace code copy,
more work will be done to find the possible code copy. We may also
stop the traverse when we reach the max search depth. Also, if the
thread of change history split into two or more commits, we stop and
provide the users all the related commits and corresponding line
range.
Generally,
1. New callback for xdi_diff to parse the diff hunk and store line
level history info.
2. builtin/line-log.c will be added to complete most of the new features.
3. builtin/log.c will be changed to add this new utility to the front end.
4. Documents will be updated to introduce this new tool.
=====Milestones and Timeline=====
In this summer, we will add support of line level history browser for
only one file. The multiple ranges support is currently not in this
project.
The milestones of the project are:
1. Simple modification change history.
2. Code movement inside one file detect.
3. Code movement inside one commit but not a file.
4. Code copy of modified file in one commit.
5. Code copy of any place in one commit tree.
6. Fuzzy matching support.
And the timeline will be:
April 26 - May 23: Catch up with Git code base and study the
implementation of blame.c and log.c thouroughly.
May 24 - June 21 : Complete a version which supports code
modifcation trace but without code movement and code copy support.
June 22 - June 29: Complete a version which supports code movement
inside one file.
June 30 - July 7: Complete a version which supports code movement
between files inside one commit.
July 8 - July 15: Complete a version which supports code copy of
modified file in one commit.
July 16 - July 23: Complete a version which supports code copy of
any file in one commit tree.
July 24 - August 7: Complete fuzzy matching of code movement and copy detect.
=====About me=====
I am Bo Yang, a Chinese graduate student majoring in Computer Science
of NanKai University. I have touched some open source software since 5
years ago and began to contribute code to open source community from
three years ago. I have contributed to Mozilla/Mingw/Netsurf.
Technically, I am experienced in C/Bash Shell. I have attended last
year's GSoC with Netsurf project. In that project, I have completed
most of a DOM library in C.
I begin to use git for source code revision from about two years ago.
I use Git for track my Mozilla trunk source code. Because updating
Mozilla code by CVS in my school is very slow. So, I write one script
to automatically updating the trunk with CVS at mid-night, when the
network flow is fast, on the server, and then use Git to maintain the
code. Then I use Git in my PC to clone/update the source code from my
local server and that is very fast. I use Git to track my changes to
the code and some bug fixes. It is an excellent tool for
branch/history, I think.
Git is my lovely daily tool for revision control. I have much
experience with it and have read "Git Internals" and also get some
basic knowledge about Git's code base. And I think the line-level
history explorer is really suitable for me and I can make a good start
with this project in Git community.
---------------------------------------------------
Thank you very much!
Regards!
Bo
From: Jakub Narebski <hidden> Date: 2016-06-15 22:48:28
Bo Yang [off-list ref] writes:
This project will add a new feature for 'git log' to display line
level history. It can trace the history of any line range of certain
file at any revision. For simplity, users can run the command like: '
git log -L builtin/diff.c:6,8 ', he will get the change history of
code between line 6 and line 8 of the diff.c file.
I think that, at least at first, line-level log should follow the
git-blame, i.e.
git log -L <begin>,<end> <revs> -- <file>
If we want (in the future) to follow history of some lines from one
file, and other lines from other file together, we do not need to use
-L <file>:<begin>,<end>
syntax. If parseopt allows, we can use posotion of parameters, i.e.
<file1> -L <m>,<n> <file2> -L <k>,<j>
And for each history entry, it will provide the commits, the diff
block which contains changes of users' interested lines.
The most important *new* algorithm you need to implement is, after
finding (blame-like) the commit that created given version of given
line, what was previous version of given line and which line that was.
You can probably find some heuristic in existing merge tools, like
emerge from GNU Emacs, or graphical diff tools.
--
Jakub Narebski
Poland
ShadeHawk on #git
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:48:29
Hi,
On Mon, 22 Mar 2010, Jakub Narebski wrote:
Bo Yang [off-list ref] writes:
quoted
This project will add a new feature for 'git log' to display line
level history. It can trace the history of any line range of certain
file at any revision. For simplity, users can run the command like: '
git log -L builtin/diff.c:6,8 ', he will get the change history of
code between line 6 and line 8 of the diff.c file.
I think that, at least at first, line-level log should follow the
git-blame, i.e.
git log -L <begin>,<end> <revs> -- <file>
If we want (in the future) to follow history of some lines from one
file, and other lines from other file together, we do not need to use
-L <file>:<begin>,<end>
syntax. If parseopt allows, we can use posotion of parameters, i.e.
<file1> -L <m>,<n> <file2> -L <k>,<j>
Oh, is it bikeshedding time already? /me might have missed the start
signal.
quoted
And for each history entry, it will provide the commits, the diff
block which contains changes of users' interested lines.
The most important *new* algorithm you need to implement is, after
finding (blame-like) the commit that created given version of given
line, what was previous version of given line and which line that was.
You can probably find some heuristic in existing merge tools, like
emerge from GNU Emacs, or graphical diff tools.
I do not think that these tools can help, as they never look further than
identical lines (and they mustn't, either).
More importantly, the first step really is about driving the libxdiff in
such a way that you can recognize the exact same lines.
(One point to note for the technical details: the algorithm has to expect
opposite code moves, i.e. it must cope well when the diff shows the code
in question removed in one hunk and added in another.)
We also should not get ahead of ourselves, but allow the student to get a
full understanding of the requirements, from which he can then make a
project plan (with milestones, Christian, no problem).
BTW by "requirements" I do not mean something as technical as the syntax,
but rather a definition what people should be able to expect to do with
this at the end of the summer.
As to fuzzy matching of lines that could not be attributed otherwise, I
think that that will require a lot of playing around with different ideas.
A simple Levenshtein-Damerau is highly unlikely to be enough.
Ciao,
Dscho
Heya,
On Mon, Mar 22, 2010 at 19:21, Johannes Schindelin
[off-list ref] wrote:
As to fuzzy matching of lines that could not be attributed otherwise, I
think that that will require a lot of playing around with different ideas.
A simple Levenshtein-Damerau is highly unlikely to be enough.
I'd recommend making this either the last milestone, or not a
milestone at all. As I noticed with git-stats such metrics might not
exist at all (or at least be too hard to find/implement), and it's
quite a bummer to not be able to implement your primary milestone ;).
--
Cheers,
Sverre Rabbelier
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:48:29
Hi,
On Mon, 22 Mar 2010, Bo Yang wrote:
Draft proposal(v2): Line-level History Browser
=====Purpose of this project=====
"git blame" can tell us who is responsible for a line of code, but it
can't help if we want to get the detail of how the lines of code have
evolved as what it is now.
This project will add a new feature for 'git log' to display line
level history. It can trace the history of any line range of certain
file at any revision. For simplity, users can run the command like: '
git log -L builtin/diff.c:6,8 ', he will get the change history of
code between line 6 and line 8 of the diff.c file. And for each
history entry, it will provide the commits, the diff block which
contains changes of users' interested lines.
I would not be too specific here about the exact syntax. I would rather
have an example where this might be useful.
In git.git, for example, you could point to pretty_print_commit() which
was split out from commit.c into pretty.c in 93fc05e(Split off the pretty
print stuff into its own file), and mention that it is hard to verify
without much hassle that the code split was really only a code split,
rather than a split with an evil change.
Or you could point to 691f1a2(replace direct calls to unlink(2) with
unlink_or_warn), where code was refactored, into a new function
(unfortunately in two commits, so it might be a case not covered by your
project) and it might be somebody's task to find out the original author
for that function.
Basically, I would like to have a structure in the proposal like this:
what? why? how? when?
This utility will trace all the modification history of interested
lines and stop until it finds the root of the lines, which is a point
where all the new code is added from scratch. Also, the users can
specify how deeply he wants this utility to trace. And this tool will
treat code move just like modification too, so it will follow the code
move inside one commit.
Note that, the history may not always be a single thread of commits.
If there are more than one commit which produce the specified line
range, the thread of history will split.
Do not forget the case where there are more than one source of a code
move. Think "refactoring".
=====Work and technical issues=====
==Command options==
This new feature should be used for exploring the history of changes
for certain line range of code in one file.
git log [-m<num>] [-I] [-d depth] [--fuzzy] -L file1@rev1:<start
pos>,<end pos> file2@rev2:<start pos>,<end pos>
I would like this not to be specified too much here. For example, we do
not know yet, whether the matching will be fuzzy, or whether we find
something cleverer than that.
So, I suggest to list not the command line options, but what you intend to
support. I.e.:
Options:
1. -m<num>, option to control whether we should follow code movement.
If one -m is given, we follow code movement inside file, when more
than one '-m' is given, we follow the movement between files in one
commit. The <num> is used to specify the lower bound for the number
of lines of moved code. If it is not given, we set it as 1.
Here you do not need to say that it is -m<num>, but that you want to
support following code movements both inside and between files, but only
optionally, for performance reasons (or some such).
In any case, this would probably just reuse the -M option.
2. -I, option to control whether we should display only the 'user
interested lines' diff block [default] or display the whole diff with
the interested area colorfully displayed.
It would be more in line with the diff options to use -U, but you do not
have to state that. Just talk about a configurable amount of context.
3. -d, option to control the max depth we trace into the commit history.
Again, there are better options for "git log" already, but you do not need
to be too explicit on the syntax side. Just say that you want to be able
to use as many of "git log"s options as make sense in the context of
line-level history.
4. --fuzzy, option to control whether fuzzy code copy mathing is used.
See above.
5. '-L' to control whether we run a simple log or we want a line level
log.
See above.
6. Files and lines. I propose to use such a syntax to specify the files
at revision and line range, <file>@<revision>:<start pos>,<end pos>.
This looks a little complex, but I think it is neccessary because we
will support multiple file at any version and any line range finally.
The revision can be any revision format of Git and the <pos> can be a
number, or a posix regex, just like what 'git blame' do.
See above.
7. And we will support code copy detect, too. The option which control
whether we trace code copy does exist in current 'git log', which is
the option '-C'. Similiarly, one '-C' is used to trace code copy of
new added code inside one commit. Two '-C' will trace any code copy
inside commit tree.
Again, do not be too specific about details that have to be fleshed out
while working on the project. For example, we do not know yet whether it
would make more sense to look for code movements automatically when we
detected a deletion, and maybe fall back automatically to detecting code
copies when we found an inter-file move.
==Design and implementation==
Git store all the blobs instead of code delta, so we should traverse
the commit history and directly access the tree/blob objects to
compute the code delta and search for the diff which contains the
interested lines.
s/ed/ing/
Since git use libxdiff to format its diff file, we should iterate
through all xdiff's diff blocks and find what the code looks like before
the commit. This will be done using the callback mechanism. Here, we
will find a new line range which is the origin code before this commit.
And then start another search from the current commit and the new line
range.
Recursively, we can find all the modification history. We will stop when
we find that the current interested line range is added from scratch and
is not moved from other place of the file. Here, if the user want to
trace code copy, more work will be done to find the possible code copy.
We may also stop the traverse when we reach the max search depth.
Also, if the thread of change history split into two or more commits, we
stop and provide the users all the related commits and corresponding
line range.
Good.
Generally,
1. New callback for xdi_diff to parse the diff hunk and store line
level history info.
2. builtin/line-log.c will be added to complete most of the new features.
3. builtin/log.c will be changed to add this new utility to the front end.
4. Documents will be updated to introduce this new tool.
Good.
=====Milestones and Timeline=====
In this summer, we will add support of line level history browser for
only one file. The multiple ranges support is currently not in this
project.
The milestones of the project are:
1. Simple modification change history.
IMHO this should be split into
1a) have an initial version which does nothing else than parse
git-log options and a single additional -L, requiring exactly
one file to be specified
1b) implement the xdiff callback and identify the commits touching
the line range (this is not completely trivial due to merges)
2. Code movement inside one file detect.
Again, this has to be split a little bit. Code can split, and it can also
unite. So, a single line range can easily become multiple ones.
3. Code movement inside one commit but not a file.
s/but not a file/between files/
4. Code copy of modified file in one commit.
You mean code copy from somewhere in the same file?
5. Code copy of any place in one commit tree.
6. Fuzzy matching support.
For fuzzy matching support, I would add some ideas, such as trying to
match alpha-numeric characters, or matching longest words or some such.
Also mention the possibility that this might be infeasible. In any case,
give an example what case this is trying to help with.
And the timeline will be:
April 26 - May 23: Catch up with Git code base and study the
implementation of blame.c and log.c thouroughly.
Hmm. Maybe it would be better to be more precise. Like: 1st week: follow
the bird's eye view on Git's source code. 2nd week, analyze the rev-list
machinery (probably first looking at the code of merge-base, for easier
understanding), 3rd week, have a look at builtin/log.c, 4th week,
understand blame.c
May 24 - June 21 : Complete a version which supports code
modifcation trace but without code movement and code copy support.
June 22 - June 29: Complete a version which supports code movement
inside one file.
June 30 - July 7: Complete a version which supports code movement
between files inside one commit.
July 8 - July 15: Complete a version which supports code copy of
modified file in one commit.
July 16 - July 23: Complete a version which supports code copy of
any file in one commit tree.
July 24 - August 7: Complete fuzzy matching of code movement and copy detect.
This should probably adjusted a bit to my suggestions above.
Ciao,
Dscho
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:48:29
Hi,
On Mon, 22 Mar 2010, Sverre Rabbelier wrote:
On Mon, Mar 22, 2010 at 19:21, Johannes Schindelin
[off-list ref] wrote:
quoted
As to fuzzy matching of lines that could not be attributed otherwise,
I think that that will require a lot of playing around with different
ideas. A simple Levenshtein-Damerau is highly unlikely to be enough.
I'd recommend making this either the last milestone, or not a milestone
at all. As I noticed with git-stats such metrics might not exist at all
(or at least be too hard to find/implement), and it's quite a bummer to
not be able to implement your primary milestone ;).
Indeed. TBH, I wanted to ask you to assist in that part of the project.
You probably can give a good overview over what does not work, and why.
Ciao,
Dscho
Heya,
On Mon, Mar 22, 2010 at 20:26, Johannes Schindelin
[off-list ref] wrote:
Indeed. TBH, I wanted to ask you to assist in that part of the project.
You probably can give a good overview over what does not work, and why.
Back then I think we even talked about teaching git log to find code
moves? I have some silly code online on repo.or.cz even. maybe.
Anyway, my main problem there was finding a heuristic that would give
a sensible answer both in small _and_ large moves. It might be worth
investigating two or more metrics instead, one that works for (very)
small chunks of code, and thus require an almost exact match, then
perhaps a somewhat linear function (the longer the block moved, the
more 'fuzz' you allow), and maybe after some size, say practical
full-file moves, use an algorithm similar to what rename detection
does. </brandump>
--
Cheers,
Sverre Rabbelier
Note that, the history may not always be a single thread of commits.
If there are more than one commit which produce the specified line
range, the thread of history will split.
Do not forget the case where there are more than one source of a code
move. Think "refactoring".
Yeah, I really ignore such a condition. Thanks a lot!
And any new added code can be moved/copied from multiple source. This
will really be a new problem for the fuzzy matching.
quoted
=====Work and technical issues=====
==Command options==
This new feature should be used for exploring the history of changes
for certain line range of code in one file.
git log [-m<num>] [-I] [-d depth] [--fuzzy] -L file1@rev1:<start
pos>,<end pos> file2@rev2:<start pos>,<end pos>
I would like this not to be specified too much here. For example, we do
not know yet, whether the matching will be fuzzy, or whether we find
something cleverer than that.
Ok, I will focus on express what I will support instead of command line options.
quoted
=====Milestones and Timeline=====
In this summer, we will add support of line level history browser for
only one file. The multiple ranges support is currently not in this
project.
The milestones of the project are:
1. Simple modification change history.
IMHO this should be split into
1a) have an initial version which does nothing else than parse
git-log options and a single additional -L, requiring exactly
one file to be specified
1b) implement the xdiff callback and identify the commits touching
the line range (this is not completely trivial due to merges)
I will make a more specified milestones and timeline, thanks!
Regards!
Bo
You mean code copy from somewhere in the same file?
I am sorry not. I mean, lines copied from other files that were
modified in the same commit. Just what 'blame' means with one '-C'
options.
quoted
5. Code copy of any place in one commit tree.
6. Fuzzy matching support.
For fuzzy matching support, I would add some ideas, such as trying to
match alpha-numeric characters, or matching longest words or some such.
Also mention the possibility that this might be infeasible. In any case,
give an example what case this is trying to help with.
I think fuzzy matching is used to track multiple lines of
copy/movement, even with little change of the source.
For example, one C function is moved from file1 to file2 and get
renamed. In this case, most of the origin code of function body will
remain unchanged except the function name. So, simply compare the new
added lines with original code line by line and permit some percent of
mismatch will help to find this kind of movement.
Regards!
Bo