Mercurial > jhg

comparison src/org/tmatesoft/hg/internal/FileAnnotation.java @ 557:b9e5ac26dd83

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Annotate: Line annotation needs true line position from merged blocks; test-annotate repo updated to show elements from both parents in the merged revision
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Sun, 24 Feb 2013 00:11:40 +0100
parents e55f17a7a195
children 154718ae23ed
comparison
equal deleted inserted replaced
556:e55f17a7a195 557:b9e5ac26dd83
14 * the terms of a license other than GNU General Public License 14 * the terms of a license other than GNU General Public License
15 * contact TMate Software at support@hg4j.com 15 * contact TMate Software at support@hg4j.com
16 */ 16 */
17 package org.tmatesoft.hg.internal; 17 package org.tmatesoft.hg.internal;
18 18
19 import java.util.LinkedList; 19 import java.util.Formatter;
20 20
21 import org.tmatesoft.hg.core.HgIterateDirection; 21 import org.tmatesoft.hg.core.HgIterateDirection;
22 import org.tmatesoft.hg.repo.HgBlameFacility; 22 import org.tmatesoft.hg.repo.HgBlameFacility;
23 import org.tmatesoft.hg.repo.HgInvalidStateException;
24 import org.tmatesoft.hg.repo.HgBlameFacility.AddBlock;
25 import org.tmatesoft.hg.repo.HgBlameFacility.BlockData;
26 import org.tmatesoft.hg.repo.HgBlameFacility.ChangeBlock;
27 import org.tmatesoft.hg.repo.HgBlameFacility.DeleteBlock;
28 import org.tmatesoft.hg.repo.HgBlameFacility.EqualBlock;
29 import org.tmatesoft.hg.repo.HgBlameFacility.RevisionDescriptor;
23 import org.tmatesoft.hg.repo.HgDataFile; 30 import org.tmatesoft.hg.repo.HgDataFile;
24 import org.tmatesoft.hg.repo.HgBlameFacility.*;
25 31
26 /** 32 /**
27 * Produce output like 'hg annotate' does 33 * Produce output like 'hg annotate' does
28 * 34 *
29 * @author Artem Tikhomirov 35 * @author Artem Tikhomirov
35 @Callback 41 @Callback
36 public interface LineInspector { 42 public interface LineInspector {
37 /** 43 /**
38 * Not necessarily invoked sequentially by line numbers 44 * Not necessarily invoked sequentially by line numbers
39 */ 45 */
40 void line(int lineNumber, int changesetRevIndex, LineDescriptor ld); 46 void line(int lineNumber, int changesetRevIndex, BlockData lineContent, LineDescriptor ld);
41 } 47 }
42 48
43 public interface LineDescriptor { 49 public interface LineDescriptor {
44 int totalLines(); 50 int totalLines();
45 } 51 }
54 FileAnnotation fa = new FileAnnotation(insp); 60 FileAnnotation fa = new FileAnnotation(insp);
55 HgBlameFacility af = new HgBlameFacility(); 61 HgBlameFacility af = new HgBlameFacility();
56 af.annotate(df, changelogRevisionIndex, fa, HgIterateDirection.NewToOld); 62 af.annotate(df, changelogRevisionIndex, fa, HgIterateDirection.NewToOld);
57 } 63 }
58 64
59 // blocks deleted in the target, as reported at the previous step 65 // keeps <startSeq1, startSeq2, len> of equal blocks, origin to target, from some previous step
60 private LinkedList<DeleteBlock> deleted = new LinkedList<DeleteBlock>(); 66 private RangeSeq activeEquals;
61 // blocks deleted in the origin, to become deletions in target at the next step
62 private LinkedList<DeleteBlock> newDeleted = new LinkedList<DeleteBlock>();
63 // keeps <startSeq1, startSeq2, len> of equal blocks, origin to target, from previous step
64 // XXX smth like IntSliceVector to access triples (or slices of any size, in fact)
65 // with easy indexing, e.g. #get(sliceIndex, indexWithinSlice)
66 // and vect.get(7,2) instead of vect.get(7*SIZEOF_SLICE+2)
67 private IntVector identical = new IntVector(20 * 3, 2 * 3);
68 // equal blocks of the current iteration, to be recalculated before next step 67 // equal blocks of the current iteration, to be recalculated before next step
69 // to track line number (current target to ultimate target) mapping 68 // to track line number (current target to ultimate target) mapping
70 private IntVector newIdentical = new IntVector(20 * 3, 2 * 3); 69 private RangeSeq intermediateEquals = new RangeSeq();
71 70
72 private boolean[] knownLines; 71 private boolean[] knownLines;
73 private final LineInspector delegate; 72 private final LineInspector delegate;
73 private RevisionDescriptor revisionDescriptor;
74 private BlockData lineContent;
75
76 private IntMap<RangeSeq> mergedRanges = new IntMap<RangeSeq>(10);
77 private IntMap<RangeSeq> equalRanges = new IntMap<RangeSeq>(10);
78 private boolean activeEqualsComesFromMerge = false;
74 79
75 public FileAnnotation(LineInspector lineInspector) { 80 public FileAnnotation(LineInspector lineInspector) {
76 delegate = lineInspector; 81 delegate = lineInspector;
77 } 82 }
78 83
79 public void start(RevisionDescriptor rd) { 84 public void start(RevisionDescriptor rd) {
85 revisionDescriptor = rd;
80 if (knownLines == null) { 86 if (knownLines == null) {
81 knownLines = new boolean[rd.target().elementCount()]; 87 lineContent = rd.target();
82 } 88 knownLines = new boolean[lineContent.elementCount()];
83 } 89 activeEquals = new RangeSeq();
84 90 activeEquals.add(0, 0, knownLines.length);
85 // private static void ppp(IntVector v) { 91 equalRanges.put(rd.targetChangesetIndex(), activeEquals);
86 // for (int i = 0; i < v.size(); i+= 3) { 92 } else {
87 // int len = v.get(i+2); 93 activeEquals = equalRanges.get(rd.targetChangesetIndex());
88 // System.out.printf("[%d..%d) == [%d..%d); ", v.get(i), v.get(i) + len, v.get(i+1), v.get(i+1) + len); 94 if (activeEquals == null) {
89 // } 95 // we didn't see this target revision as origin yet
90 // System.out.println(); 96 // the only way this may happen is that this revision was a merge parent
91 // } 97 activeEquals = mergedRanges.get(rd.targetChangesetIndex());
98 activeEqualsComesFromMerge = true;
99 if (activeEquals == null) {
100 throw new HgInvalidStateException(String.format("Can't find previously visited revision %d (while in %d->%1$d diff)", rd.targetChangesetIndex(), rd.originChangesetIndex()));
101 }
102 }
103 }
104 }
92 105
93 public void done(RevisionDescriptor rd) { 106 public void done(RevisionDescriptor rd) {
94 if (identical.size() > 0) { 107 // update line numbers of the intermediate target to point to ultimate target's line numbers
95 // update line numbers of the intermediate target to point to ultimate target's line numbers 108 RangeSeq v = intermediateEquals.intersect(activeEquals);
96 IntVector v = new IntVector(identical.size(), 2 * 3); 109 if (activeEqualsComesFromMerge) {
97 for (int i = 0; i < newIdentical.size(); i += 3) { 110 mergedRanges.put(rd.originChangesetIndex(), v);
98 int originLine = newIdentical.get(i); 111 } else {
99 int targetLine = newIdentical.get(i + 1); 112 equalRanges.put(rd.originChangesetIndex(), v);
100 int length = newIdentical.get(i + 2); 113 }
114 intermediateEquals.clear();
115 activeEquals = null;
116 activeEqualsComesFromMerge = false;
117 revisionDescriptor = null;
118 }
119
120 public void same(EqualBlock block) {
121 intermediateEquals.add(block.originStart(), block.targetStart(), block.length());
122 }
123
124 public void added(AddBlock block) {
125 RangeSeq rs = null;
126 if (revisionDescriptor.isMerge() && block.originChangesetIndex() == revisionDescriptor.mergeChangesetIndex()) {
127 rs = mergedRanges.get(revisionDescriptor.mergeChangesetIndex());
128 if (rs == null) {
129 mergedRanges.put(revisionDescriptor.mergeChangesetIndex(), rs = new RangeSeq());
130 }
131 }
132 if (activeEquals.size() == 0) {
133 return;
134 }
135 for (int i = 0, ln = block.firstAddedLine(), x = block.totalAddedLines(); i < x; i++, ln++) {
136 int lnInFinal = activeEquals.mapLineIndex(ln);
137 if (lnInFinal != -1/* && !knownLines[lnInFinal]*/) {
138 if (rs != null) {
139 rs.add(block.insertedAt() + i, lnInFinal, 1);
140 } else {
141 delegate.line(lnInFinal, block.targetChangesetIndex(), lineContent.elementAt(lnInFinal), new LineDescriptorImpl());
142 }
143 knownLines[lnInFinal] = true;
144 }
145 }
146 }
147
148 public void changed(ChangeBlock block) {
149 added(block);
150 }
151
152 public void deleted(DeleteBlock block) {
153 }
154
155 private final class LineDescriptorImpl implements LineDescriptor {
156 LineDescriptorImpl() {
157 }
158
159 public int totalLines() {
160 return FileAnnotation.this.knownLines.length;
161 }
162 }
163
164 private static class RangeSeq {
165 // XXX smth like IntSliceVector to access triples (or slices of any size, in fact)
166 // with easy indexing, e.g. #get(sliceIndex, indexWithinSlice)
167 // and vect.get(7,2) instead of vect.get(7*SIZEOF_SLICE+2)
168 private final IntVector ranges = new IntVector(3*10, 3*5);
169 private int count;
170
171 public void add(int start1, int start2, int length) {
172 if (count > 0) {
173 int lastIndex = 3 * (count-1);
174 int lastS1 = ranges.get(lastIndex);
175 int lastS2 = ranges.get(lastIndex + 1);
176 int lastLen = ranges.get(lastIndex + 2);
177 if (start1 == lastS1 + lastLen && start2 == lastS2 + lastLen) {
178 // new range continues the previous one - just increase the length
179 ranges.set(lastIndex + 2, lastLen + length);
180 return;
181 }
182 }
183 ranges.add(start1, start2, length);
184 count++;
185 }
186
187 public void clear() {
188 ranges.clear();
189 count = 0;
190 }
191
192 public int size() {
193 return count;
194 }
195
196 public int mapLineIndex(int ln) {
197 for (int i = 0; i < ranges.size(); i += 3) {
198 int s1 = ranges.get(i);
199 if (s1 > ln) {
200 return -1;
201 }
202 int l = ranges.get(i+2);
203 if (s1 + l > ln) {
204 int s2 = ranges.get(i + 1);
205 return s2 + (ln - s1);
206 }
207 }
208 return -1;
209 }
210
211 public RangeSeq intersect(RangeSeq target) {
212 RangeSeq v = new RangeSeq();
213 for (int i = 0; i < ranges.size(); i += 3) {
214 int originLine = ranges.get(i);
215 int targetLine = ranges.get(i + 1);
216 int length = ranges.get(i + 2);
101 int startTargetLine = -1, startOriginLine = -1, c = 0; 217 int startTargetLine = -1, startOriginLine = -1, c = 0;
102 for (int j = 0; j < length; j++) { 218 for (int j = 0; j < length; j++) {
103 int lnInFinal = mapLineIndex(targetLine + j); 219 int lnInFinal = target.mapLineIndex(targetLine + j);
104 if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) { 220 if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) {
105 // the line is not among "same" in ultimate origin 221 // the line is not among "same" in ultimate origin
106 // or belongs to another/next "same" chunk 222 // or belongs to another/next "same" chunk
107 if (startOriginLine == -1) { 223 if (startOriginLine == -1) {
108 continue; 224 continue;
109 } 225 }
110 v.add(startOriginLine); 226 v.add(startOriginLine, startTargetLine, c);
111 v.add(startTargetLine);
112 v.add(c);
113 c = 0; 227 c = 0;
114 startOriginLine = startTargetLine = -1; 228 startOriginLine = startTargetLine = -1;
115 // fall-through to check if it's not complete miss but a next chunk 229 // fall-through to check if it's not complete miss but a next chunk
116 } 230 }
117 if (lnInFinal != -1) { 231 if (lnInFinal != -1) {
118 if (startOriginLine == -1) { 232 if (startOriginLine == -1) {
119 startOriginLine = originLine + j; 233 startOriginLine = originLine + j;
120 startTargetLine = lnInFinal; 234 startTargetLine = lnInFinal;
121 c = 1; 235 c = 1;
122 } else { 236 } else {
237 // lnInFinal != startTargetLine + s is covered above
123 assert lnInFinal == startTargetLine + c; 238 assert lnInFinal == startTargetLine + c;
124 c++; 239 c++;
125 } 240 }
126 } 241 }
127 } 242 }
128 if (startOriginLine != -1) { 243 if (startOriginLine != -1) {
129 assert c > 0; 244 assert c > 0;
130 v.add(startOriginLine); 245 v.add(startOriginLine, startTargetLine, c);
131 v.add(startTargetLine); 246 }
132 v.add(c); 247 }
133 } 248 return v;
134 } 249 }
135 newIdentical.clear(); 250
136 identical = v; 251 @SuppressWarnings("unused")
137 } else { 252 public CharSequence dump() {
138 IntVector li = newIdentical; 253 StringBuilder sb = new StringBuilder();
139 newIdentical = identical; 254 Formatter f = new Formatter(sb);
140 identical = li; 255 for (int i = 0; i < ranges.size(); i += 3) {
141 } 256 int s1 = ranges.get(i);
142 LinkedList<DeleteBlock> ld = newDeleted; 257 int s2 = ranges.get(i + 1);
143 deleted.clear(); 258 int len = ranges.get(i + 2);
144 newDeleted = deleted; 259 f.format("[%d..%d) == [%d..%d); ", s1, s1 + len, s2, s2 + len);
145 deleted = ld; 260 }
146 } 261 return sb;
147 262 }
148 public void same(EqualBlock block) { 263
149 newIdentical.add(block.originStart()); 264 @Override
150 newIdentical.add(block.targetStart()); 265 public String toString() {
151 newIdentical.add(block.length()); 266 return String.format("RangeSeq[%d]:%s", count, dump());
152 }
153
154 public void added(AddBlock block) {
155 for (int i = 0, ln = block.firstAddedLine(), x = block.totalAddedLines(); i < x; i++, ln++) {
156 int lnInFinal = mapLineIndex(ln);
157 if (lnInFinal != -1 && !knownLines[lnInFinal]) {
158 delegate.line(lnInFinal, block.targetChangesetIndex(), new LineDescriptorImpl());
159 knownLines[lnInFinal] = true;
160 }
161 }
162 }
163
164 public void changed(ChangeBlock block) {
165 deleted(block);
166 added(block);
167 }
168
169 public void deleted(DeleteBlock block) {
170 newDeleted.add(block);
171 }
172
173 // line - index in the target
174 private boolean isDeleted(int line) {
175 for (DeleteBlock b : deleted) {
176 if (b.firstRemovedLine() > line) {
177 break;
178 }
179 // line >= b.firstRemovedLine
180 if (b.firstRemovedLine() + b.totalRemovedLines() > line) {
181 return true;
182 }
183 }
184 return false;
185 }
186
187 // map target lines to the lines of the revision being annotated (the one that came first)
188 private int mapLineIndex(int ln) {
189 if (isDeleted(ln)) {
190 return -1;
191 }
192 if (identical.isEmpty()) {
193 return ln;
194 }
195 for (int i = 0; i < identical.size(); i += 3) {
196 final int originStart = identical.get(i);
197 if (originStart > ln) {
198 // assert false;
199 return -1;
200 }
201 // ln >= b.originStart
202 final int length = identical.get(i + 2);
203 if (originStart + length > ln) {
204 int targetStart = identical.get(i + 1);
205 return targetStart + (ln - originStart);
206 }
207 }
208 // assert false;
209 return -1;
210 }
211
212 private final class LineDescriptorImpl implements LineDescriptor {
213 LineDescriptorImpl() {
214 }
215
216 public int totalLines() {
217 return FileAnnotation.this.knownLines.length;
218 } 267 }
219 } 268 }
220 } 269 }