monotone

monotone Mtn Source Tree

Root/annotate.cc

1// Copyright (C) 2005 Emile Snyder <emile@alumni.reed.edu>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#include <deque>
11#include <set>
12#include <sstream>
13#include <string>
14
15#include <boost/shared_ptr.hpp>
16
17#include "annotate.hh"
18#include "app_state.hh"
19#include "cert.hh"
20#include "constants.hh"
21#include "cset.hh"
22#include "interner.hh"
23#include "lcs.hh"
24#include "platform.hh"
25#include "revision.hh"
26#include "sanity.hh"
27#include "simplestring_xform.hh"
28#include "transforms.hh"
29#include "ui.hh"
30#include "vocab.hh"
31
32using std::auto_ptr;
33using std::back_insert_iterator;
34using std::back_inserter;
35using std::cout;
36using std::deque;
37using std::endl;
38using std::make_pair;
39using std::map;
40using std::min;
41using std::set;
42using std::string;
43using std::vector;
44
45using boost::shared_ptr;
46
47class annotate_lineage_mapping;
48
49
50class annotate_context
51{
52public:
53 annotate_context(file_id fid, app_state & app);
54
55 shared_ptr<annotate_lineage_mapping> initial_lineage() const;
56
57 /// credit any uncopied lines (as recorded in copied_lines) to
58 /// rev, and reset copied_lines.
59 void evaluate(revision_id rev);
60
61 void set_copied(int index);
62 void set_touched(int index);
63
64 void set_equivalent(int index, int index2);
65 void annotate_equivalent_lines();
66
67 /// return true if we have no more unassigned lines
68 bool is_complete() const;
69
70 void dump(app_state & app) const;
71
72 string get_line(int line_index) const
73 {
74 return file_lines[line_index];
75 }
76
77private:
78 void build_revisions_to_annotations(app_state & app,
79 map<revision_id, string> & r2a) const;
80
81 vector<string> file_lines;
82 vector<revision_id> annotations;
83
84 /// equivalent_lines[n] = m means that line n should be blamed to the same
85 /// revision as line m
86 map<int, int> equivalent_lines;
87
88 /// keep a count so we can tell quickly whether we can terminate
89 size_t annotated_lines_completed;
90
91 // elements of the set are indexes into the array of lines in the
92 // UDOI lineages add entries here when they notice that they copied
93 // a line from the UDOI
94 set<size_t> copied_lines;
95
96 // similarly, lineages add entries here for all the lines from the
97 // UDOI they know about that they didn't copy
98 set<size_t> touched_lines;
99};
100
101
102
103/*
104 An annotate_lineage_mapping tells you, for each line of a file,
105 where in the ultimate descendent of interest (UDOI) the line came
106 from (a line not present in the UDOI is represented as -1).
107*/
108class annotate_lineage_mapping
109{
110public:
111 annotate_lineage_mapping(file_data const & data);
112 annotate_lineage_mapping(vector<string> const & lines);
113
114 // debugging
115 //bool equal_interned (const annotate_lineage_mapping &rhs) const;
116
117 /// need a better name. does the work of setting copied bits in the
118 /// context object.
119 shared_ptr<annotate_lineage_mapping>
120 build_parent_lineage(shared_ptr<annotate_context> acp,
121 revision_id parent_rev,
122 file_data const & parent_data) const;
123
124 void merge(annotate_lineage_mapping const & other,
125 shared_ptr<annotate_context> const & acp);
126
127 void credit_mapped_lines(shared_ptr<annotate_context> acp) const;
128 void set_copied_all_mapped(shared_ptr<annotate_context> acp) const;
129
130private:
131 void init_with_lines(vector<string> const & lines);
132
133 static interner<long> in; // FIX, testing hack
134
135 vector<long, QA(long)> file_interned;
136
137 // maps an index into the vector of lines for our current version of
138 // the file into an index into the vector of lines of the UDOI:
139 // eg. if the line file_interned[i] will turn into line 4 in the
140 // UDOI, mapping[i] = 4
141 vector<int> mapping;
142};
143
144
145interner<long> annotate_lineage_mapping::in;
146
147
148/*
149 annotate_node_work encapsulates the input data needed to process
150 the annotations for a given childrev, considering all the
151 childrev -> parentrevN edges.
152*/
153struct annotate_node_work
154{
155 annotate_node_work(shared_ptr<annotate_context> annotations_,
156 shared_ptr<annotate_lineage_mapping> lineage_,
157 revision_id revision_, node_id fid_)
158 : annotations(annotations_),
159 lineage(lineage_),
160 revision(revision_),
161 fid(fid_)
162 {}
163
164 annotate_node_work(annotate_node_work const & w)
165 : annotations(w.annotations),
166 lineage(w.lineage),
167 revision(w.revision),
168 fid(w.fid)
169 {}
170
171 shared_ptr<annotate_context> annotations;
172 shared_ptr<annotate_lineage_mapping> lineage;
173 revision_id revision;
174 node_id fid;
175};
176
177
178class lineage_merge_node
179{
180public:
181 typedef shared_ptr<annotate_lineage_mapping> splm;
182
183 lineage_merge_node(lineage_merge_node const & m)
184 : work(m.work),
185 incoming_edges(m.incoming_edges),
186 completed_edges(m.completed_edges)
187 {}
188
189 lineage_merge_node(annotate_node_work wu, size_t incoming)
190 : work(wu),
191 incoming_edges(incoming),
192 completed_edges(1)
193 {}
194
195 void merge(splm incoming,
196 shared_ptr<annotate_context> const & acp)
197 {
198 work.lineage->merge(*incoming, acp); completed_edges++;
199 }
200
201 bool iscomplete() const
202 {
203 I(completed_edges <= incoming_edges);
204 return incoming_edges == completed_edges;
205 }
206
207 annotate_node_work get_work() const
208 {
209 I(iscomplete());
210 return work;
211 }
212
213private:
214 annotate_node_work work;
215 size_t incoming_edges;
216 size_t completed_edges;
217};
218
219
220
221
222
223annotate_context::annotate_context(file_id fid, app_state & app)
224 : annotated_lines_completed(0)
225{
226 // initialize file_lines
227 file_data fpacked;
228 app.db.get_file_version(fid, fpacked);
229 string encoding = constants::default_encoding; // FIXME
230 split_into_lines(fpacked.inner()(), encoding, file_lines);
231 L(FL("annotate_context::annotate_context initialized "
232 "with %d file lines\n") % file_lines.size());
233
234 // initialize annotations
235 revision_id nullid;
236 annotations.clear();
237 annotations.reserve(file_lines.size());
238 annotations.insert(annotations.begin(), file_lines.size(), nullid);
239 L(FL("annotate_context::annotate_context initialized "
240 "with %d entries in annotations\n") % annotations.size());
241
242 // initialize copied_lines and touched_lines
243 copied_lines.clear();
244 touched_lines.clear();
245}
246
247
248shared_ptr<annotate_lineage_mapping>
249annotate_context::initial_lineage() const
250{
251 shared_ptr<annotate_lineage_mapping>
252 res(new annotate_lineage_mapping(file_lines));
253 return res;
254}
255
256
257void
258annotate_context::evaluate(revision_id rev)
259{
260 revision_id nullid;
261 I(copied_lines.size() <= annotations.size());
262 I(touched_lines.size() <= annotations.size());
263
264 // Find the lines that we touched but that no other parent copied.
265 set<size_t> credit_lines;
266 set_difference(touched_lines.begin(), touched_lines.end(),
267 copied_lines.begin(), copied_lines.end(),
268 inserter(credit_lines, credit_lines.begin()));
269
270 set<size_t>::const_iterator i;
271 for (i = credit_lines.begin(); i != credit_lines.end(); i++)
272 {
273 I(*i < annotations.size());
274 if (annotations[*i] == nullid)
275{
276
277 // L(FL("evaluate setting annotations[%d] -> %s, since "
278 // "touched_lines contained %d, copied_lines didn't and "
279 // "annotations[%d] was nullid\n") % *i % rev % *i % *i);
280
281 annotations[*i] = rev;
282 annotated_lines_completed++;
283}
284 else
285{
286 //L(FL("evaluate LEAVING annotations[%d] -> %s")
287 // % *i % annotations[*i]);
288}
289 }
290
291 copied_lines.clear();
292 touched_lines.clear();
293}
294
295void
296annotate_context::set_copied(int index)
297{
298 //L(FL("annotate_context::set_copied %d") % index);
299
300 if (index == -1)
301 return;
302
303 I(index >= 0 && index < (int)file_lines.size());
304 copied_lines.insert(index);
305}
306
307void
308annotate_context::set_touched(int index)
309{
310 //L(FL("annotate_context::set_touched %d") % index);
311
312 if (index == -1)
313 return;
314
315 I(index >= 0 && index <= (int)file_lines.size());
316 touched_lines.insert(index);
317}
318
319void
320annotate_context::set_equivalent(int index, int index2)
321{
322 L(FL("annotate_context::set_equivalent "
323 "index %d index2 %d\n") % index % index2);
324 equivalent_lines[index] = index2;
325}
326
327void
328annotate_context::annotate_equivalent_lines()
329{
330 revision_id null_id;
331
332 for (size_t i=0; i<annotations.size(); i++)
333 {
334 if (annotations[i] == null_id)
335{
336 map<int, int>::const_iterator j = equivalent_lines.find(i);
337 if (j == equivalent_lines.end())
338 {
339 L(FL("annotate_equivalent_lines unable to find "
340 "equivalent for line %d\n") % i);
341 }
342 I(j != equivalent_lines.end());
343 annotations[i] = annotations[j->second];
344 annotated_lines_completed++;
345}
346 }
347}
348
349bool
350annotate_context::is_complete() const
351{
352 if (annotated_lines_completed == annotations.size())
353 return true;
354
355 I(annotated_lines_completed < annotations.size());
356 return false;
357}
358
359
360string cert_string_value(vector< revision<cert> > const & certs,
361 string const & name,
362 bool from_start, bool from_end,
363 string const & sep)
364{
365 for (vector< revision<cert> >::const_iterator i = certs.begin();
366 i != certs.end(); ++i)
367 {
368 if (i->inner().name() == name)
369 {
370 cert_value tv;
371 decode_base64 (i->inner().value, tv);
372 string::size_type f = 0;
373 string::size_type l = string::npos;
374 if (from_start)
375 l = tv ().find_first_of(sep);
376 if (from_end)
377 {
378 f = tv ().find_last_of(sep);
379 if (f == string::npos)
380 f = 0;
381 }
382 return tv().substr(f, l);
383 }
384 }
385
386 return "";
387}
388
389
390void
391annotate_context::build_revisions_to_annotations
392(app_state & app,
393 map<revision_id, string> & revs_to_notations) const
394{
395 I(annotations.size() == file_lines.size());
396
397 // build set of unique revisions present in annotations
398 set<revision_id> seen;
399 for (vector<revision_id>::const_iterator i = annotations.begin();
400 i != annotations.end(); i++)
401 {
402 seen.insert(*i);
403 }
404
405 size_t max_note_length = 0;
406
407 // build revision -> annotation string mapping
408 for (set<revision_id>::const_iterator i = seen.begin();
409 i != seen.end(); i++)
410 {
411 vector< revision<cert> > certs;
412 app.db.get_revision_certs(*i, certs);
413 erase_bogus_certs(certs, app);
414
415 string author(cert_string_value(certs, author_cert_name,
416 true, false, "@< "));
417
418 string date(cert_string_value(certs, date_cert_name,
419 true, false, "T"));
420
421 string result;
422 result.append((*i).inner ()().substr(0, 8));
423 result.append(".. by ");
424 result.append(author);
425 result.append(" ");
426 result.append(date);
427 result.append(": ");
428
429 max_note_length = ((result.size() > max_note_length)
430 ? result.size()
431 : max_note_length);
432 revs_to_notations[*i] = result;
433 }
434
435 // justify annotation strings
436 for (map<revision_id, string>::iterator i = revs_to_notations.begin();
437 i != revs_to_notations.end(); i++)
438 {
439 size_t l = i->second.size();
440 i->second.insert(string::size_type(0), max_note_length - l, ' ');
441 }
442}
443
444
445void
446annotate_context::dump(app_state & app) const
447{
448 revision_id nullid;
449 I(annotations.size() == file_lines.size());
450
451 map<revision_id, string> revs_to_notations;
452 string empty_note;
453 if (global_sanity.brief)
454 {
455 build_revisions_to_annotations(app, revs_to_notations);
456 size_t max_note_length = revs_to_notations.begin()->second.size();
457 empty_note.insert(string::size_type(0), max_note_length - 2, ' ');
458 }
459
460 revision_id lastid = nullid;
461 for (size_t i = 0; i < file_lines.size(); i++)
462 {
463 //I(! (annotations[i] == nullid) );
464 if (global_sanity.brief)
465 {
466 if (lastid == annotations[i])
467 cout << empty_note << ": "
468 << file_lines[i] << endl;
469 else
470 cout << revs_to_notations[annotations[i]]
471 << file_lines[i] << endl;
472 lastid = annotations[i];
473 }
474 else
475 cout << annotations[i] << ": "
476 << file_lines[i] << endl;
477 }
478}
479
480
481annotate_lineage_mapping::annotate_lineage_mapping(file_data const & data)
482{
483 // split into lines
484 vector<string> lines;
485 string encoding = constants::default_encoding; // FIXME
486 split_into_lines (data.inner()().data(), encoding, lines);
487
488 init_with_lines(lines);
489}
490
491annotate_lineage_mapping::annotate_lineage_mapping
492(vector<string> const & lines)
493{
494 init_with_lines(lines);
495}
496
497/*
498bool
499annotate_lineage_mapping::equal_interned
500(annotate_lineage_mapping const & rhs) const
501{
502 bool result = true;
503
504 if (file_interned.size() != rhs.file_interned.size()) {
505 L(FL("annotate_lineage_mapping::equal_interned "
506 "lhs size %d != rhs size %d\n")
507 % file_interned.size() % rhs.file_interned.size());
508 result = false;
509 }
510
511 size_t limit = min(file_interned.size(), rhs.file_interned.size());
512 for (size_t i=0; i<limit; i++)
513 {
514 if (file_interned[i] != rhs.file_interned[i])
515{
516 L(FL("annotate_lineage_mapping::equal_interned "
517 "lhs[%d]:%ld != rhs[%d]:%ld\n")
518 % i % file_interned[i] % i % rhs.file_interned[i]);
519 result = false;
520}
521 }
522
523 return result;
524}
525*/
526
527void
528annotate_lineage_mapping::init_with_lines(vector<string> const & lines)
529{
530 file_interned.clear();
531 file_interned.reserve(lines.size());
532 mapping.clear();
533 mapping.reserve(lines.size());
534
535 int count;
536 vector<string>::const_iterator i;
537 for (count=0, i = lines.begin(); i != lines.end(); i++, count++)
538 {
539 file_interned.push_back(in.intern(*i));
540 mapping.push_back(count);
541 }
542 L(FL("annotate_lineage_mapping::init_with_lines "
543 "ending with %d entries in mapping\n") % mapping.size());
544}
545
546
547shared_ptr<annotate_lineage_mapping>
548annotate_lineage_mapping::build_parent_lineage
549(shared_ptr<annotate_context> acp,
550 revision_id parent_rev,
551 file_data const & parent_data) const
552{
553 bool verbose = false;
554 shared_ptr<annotate_lineage_mapping>
555 parent_lineage(new annotate_lineage_mapping(parent_data));
556
557 vector<long, QA(long)> lcs;
558 back_insert_iterator< vector<long, QA(long)> > bii(lcs);
559 longest_common_subsequence(file_interned.begin(),
560 file_interned.end(),
561 parent_lineage->file_interned.begin(),
562 parent_lineage->file_interned.end(),
563 min(file_interned.size(),
564 parent_lineage->file_interned.size()),
565 back_inserter(lcs));
566
567 if (verbose)
568 L(FL("build_parent_lineage: "
569 "file_lines.size() == %d, "
570 "parent.file_lines.size() == %d, "
571 "lcs.size() == %d\n")
572 % file_interned.size()
573 % parent_lineage->file_interned.size()
574 % lcs.size());
575
576 // do the copied lines thing for our annotate_context
577 vector<long> lcs_src_lines;
578 lcs_src_lines.resize(lcs.size());
579 size_t i, j;
580 i = j = 0;
581 while (i < file_interned.size() && j < lcs.size())
582 {
583 //if (verbose)
584 if (file_interned[i] == 14)
585L(FL("%s file_interned[%d]: %ld\tlcs[%d]: %ld\tmapping[%d]: %ld")
586 % parent_rev % i % file_interned[i] % j % lcs[j] % i % mapping[i]);
587
588 if (file_interned[i] == lcs[j])
589{
590 acp->set_copied(mapping[i]);
591 lcs_src_lines[j] = mapping[i];
592 j++;
593}
594 else
595{
596 acp->set_touched(mapping[i]);
597}
598
599 i++;
600 }
601 if (verbose)
602 L(FL("loop ended with i: %d, j: %d, lcs.size(): %d")
603 % i % j % lcs.size());
604 I(j == lcs.size());
605
606 // set touched for the rest of the lines in the file
607 while (i < file_interned.size())
608 {
609 acp->set_touched(mapping[i]);
610 i++;
611 }
612
613 // determine the mapping for parent lineage
614 if (verbose)
615 L(FL("build_parent_lineage: building mapping now "
616 "for parent_rev %s\n") % parent_rev);
617
618 i = j = 0;
619
620 while (i < parent_lineage->file_interned.size() && j < lcs.size())
621 {
622 if (parent_lineage->file_interned[i] == lcs[j])
623{
624 parent_lineage->mapping[i] = lcs_src_lines[j];
625 j++;
626}
627 else
628{
629 parent_lineage->mapping[i] = -1;
630}
631 if (verbose)
632L(FL("mapping[%d] -> %d") % i % parent_lineage->mapping[i]);
633
634 i++;
635 }
636 I(j == lcs.size());
637 // set mapping for the rest of the lines in the file
638 while (i < parent_lineage->file_interned.size())
639 {
640 parent_lineage->mapping[i] = -1;
641 if (verbose)
642L(FL("mapping[%d] -> %d") % i % parent_lineage->mapping[i]);
643 i++;
644 }
645
646 return parent_lineage;
647}
648
649
650void
651annotate_lineage_mapping::merge(annotate_lineage_mapping const & other,
652 shared_ptr<annotate_context> const & acp)
653{
654 I(file_interned.size() == other.file_interned.size());
655 I(mapping.size() == other.mapping.size());
656 //I(equal_interned(other)); // expensive check
657
658 for (size_t i=0; i<mapping.size(); i++)
659 {
660 if (mapping[i] == -1 && other.mapping[i] >= 0)
661mapping[i] = other.mapping[i];
662
663 if (mapping[i] >= 0 && other.mapping[i] >= 0)
664{
665 //I(mapping[i] == other.mapping[i]);
666 if (mapping[i] != other.mapping[i])
667 {
668 // a given line in the current merged mapping will split
669 // and become multiple lines in the UDOI. so we have to
670 // remember that whenever we ultimately assign blame for
671 // mapping[i] we blame the same revision on
672 // other.mapping[i].
673 acp->set_equivalent(other.mapping[i], mapping[i]);
674 }
675}
676 }
677}
678
679void
680annotate_lineage_mapping::credit_mapped_lines
681(shared_ptr<annotate_context> acp) const
682{
683 vector<int>::const_iterator i;
684 for (i=mapping.begin(); i != mapping.end(); i++)
685 {
686 acp->set_touched(*i);
687 }
688}
689
690
691void
692annotate_lineage_mapping::set_copied_all_mapped
693(shared_ptr<annotate_context> acp) const
694{
695 vector<int>::const_iterator i;
696 for (i=mapping.begin(); i != mapping.end(); i++)
697 {
698 acp->set_copied(*i);
699 }
700}
701
702// privatish function to do a quick parse and extraction from the roster.
703bool
704roster_get_revision_fid_info(const roster_data &dat,
705 node_id const &file_id,
706 file_t &file,
707 marking_t &marks);
708static bool
709get_revision_fid_info(database &db,
710 revision_id const & rev_id,
711 node_id const &file_id,
712 file_id &file_content,
713 marking_t &marks)
714{
715 if (rev_id.inner()().empty()) {
716 return false;
717 }
718
719 file_t direct_file;
720 marking_t direct_marks;
721 bool direct_found;
722 {
723 roster_data dat;
724 roster_id ident;
725
726 db.get_roster_id_for_revision(rev_id, ident);
727 db.get_roster_version(ident, dat);
728 direct_found = roster_get_revision_fid_info(dat, file_id, direct_file, direct_marks);
729 }
730
731 static const bool regression_test = false;
732 if (!regression_test) {
733 if (!direct_found) {
734 return false;
735 }
736 file_content = direct_file->content;
737 marks = direct_marks;
738 return true;
739 } else {
740 marking_map markmap;
741 roster_t roster;
742 db.get_roster(rev_id, roster, markmap);
743
744 if (!roster.has_node(file_id)) {
745 I(!direct_found);
746 return false;
747 }
748 I(direct_found);
749 map<node_id, marking_t>::const_iterator mmi =
750 markmap.find(file_id);
751 I(mmi != markmap.end());
752 file_t file = downcast_to_file_t(roster.get_node(file_id));
753 file_content = file->content;
754 marks = mmi->second;
755 I(direct_file->content == file->content);
756 I(direct_marks == marks);
757 return true;
758 }
759}
760
761
762static void
763do_annotate_node
764(annotate_node_work const & work_unit,
765 app_state & app,
766 deque<annotate_node_work> & nodes_to_process,
767 set<revision_id> & nodes_complete,
768 map<revision_id, size_t> const & paths_to_nodes,
769 map<revision_id, lineage_merge_node> & pending_merge_nodes)
770{
771 L(FL("do_annotate_node for node %s") % work_unit.revision);
772 I(nodes_complete.find(work_unit.revision) == nodes_complete.end());
773 // nodes_seen.insert(make_pair(work_unit.revision, work_unit.lineage));
774
775 file_id file_in_child_content;
776 marking_t marks;
777 bool found = get_revision_fid_info(app.db,
778 work_unit.revision, work_unit.fid,
779 file_in_child_content, marks);
780 I(found);
781
782 if (marks.file_content.size() == 0)
783 {
784 L(FL("found empty content-mark set at rev %s")
785% work_unit.revision);
786 work_unit.lineage->credit_mapped_lines(work_unit.annotations);
787 work_unit.annotations->evaluate(work_unit.revision);
788 nodes_complete.insert(work_unit.revision);
789 return;
790 }
791
792 set<revision_id> parents;
793
794 // If we have content-marks which are *not* equal to the current
795 // rev, we can jump back to them directly. If we have only a
796 // content-mark equal to the current rev, it means we made a
797 // decision here, and we must move to the immediate parent revs.
798 //
799 // Unfortunately, while this algorithm *could* use the marking
800 // information as suggested above, it seems to work much better
801 // (especially wrt. merges) when it goes rev-by-rev, so we leave it
802 // that way for now.
803
804 // if (marks.file_content.size() == 1
805 // && *(marks.file_content.begin()) == work_unit.revision)
806
807 app.db.get_revision_parents(work_unit.revision, parents);
808
809 // else
810 // parents = marks.file_content;
811
812 size_t added_in_parent_count = 0;
813
814 for (set<revision_id>::const_iterator i = parents.begin();
815 i != parents.end(); i++)
816 {
817 revision_id parent_revision = *i;
818
819 L(FL("do_annotate_node processing edge from parent %s to child %s")
820 % parent_revision % work_unit.revision);
821
822 I(!(work_unit.revision == parent_revision));
823
824 file_id file_in_parent_content;
825 marking_t marks_in_parent;
826 bool in_parent = get_revision_fid_info(app.db,
827 parent_revision, work_unit.fid,
828 file_in_parent_content, marks_in_parent);
829
830 if (!in_parent)
831 {
832 L(FL("file added in %s, continuing") % work_unit.revision);
833 added_in_parent_count++;
834 continue;
835 }
836
837 // The node was live in the parent, so this represents a delta.
838
839 shared_ptr<annotate_lineage_mapping> parent_lineage;
840
841 if (file_in_parent_content == file_in_child_content)
842 {
843 L(FL("parent file identical, "
844 "set copied all mapped and copy lineage\n"));
845 parent_lineage = work_unit.lineage;
846 parent_lineage->set_copied_all_mapped(work_unit.annotations);
847 }
848 else
849 {
850 file_data data;
851 app.db.get_file_version(file_in_parent_content, data);
852 L(FL("building parent lineage for parent file %s")
853 % file_in_parent_content);
854 parent_lineage
855 = work_unit.lineage->build_parent_lineage(work_unit.annotations,
856 parent_revision,
857 data);
858 }
859
860 // If this parent has not yet been queued for processing, create the
861 // work unit for it.
862 map<revision_id, lineage_merge_node>::iterator lmn
863 = pending_merge_nodes.find(parent_revision);
864
865 if (lmn == pending_merge_nodes.end())
866 {
867 // Once we move on to processing the parent that this file was
868 // renamed from, we'll need the old name
869 annotate_node_work newunit(work_unit.annotations,
870 parent_lineage,
871 parent_revision,
872 work_unit.fid);
873
874 map<revision_id, size_t>::const_iterator ptn
875 = paths_to_nodes.find(parent_revision);
876
877 if (ptn->second > 1)
878 {
879 lineage_merge_node nmn(newunit, ptn->second);
880 pending_merge_nodes.insert(make_pair(parent_revision, nmn));
881 L(FL("put new merge node on pending_merge_nodes "
882 "for parent %s\n")
883 % parent_revision);
884 // just checking...
885 //(pending_merge_nodes.find(parent_revision))->second.dump();
886 }
887 else
888 {
889 L(FL("single path to node, just stick work on the queue "
890 "for parent %s\n")
891 % parent_revision);
892 nodes_to_process.push_back(newunit);
893 }
894 }
895 else
896 {
897 // Already a pending node, so we just have to merge the lineage
898 // and decide whether to move it over to the nodes_to_process
899 // queue.
900 L(FL("merging lineage from node %s to parent %s")
901 % work_unit.revision % parent_revision);
902 lmn->second.merge(parent_lineage, work_unit.annotations);
903 //L(FL("after merging from work revision %s to parent %s"
904 // " lineage_merge_node is:\n") % work_unit.revision
905 // % parent_revision); lmn->second.dump();
906 if (lmn->second.iscomplete())
907 {
908 nodes_to_process.push_back(lmn->second.get_work());
909 pending_merge_nodes.erase(lmn);
910 }
911 }
912 }
913
914 if (added_in_parent_count == parents.size())
915 {
916 work_unit.lineage->credit_mapped_lines(work_unit.annotations);
917 }
918
919 work_unit.annotations->evaluate(work_unit.revision);
920 nodes_complete.insert(work_unit.revision);
921}
922
923
924void
925find_ancestors(app_state & app,
926 revision_id rid,
927 map<revision_id, size_t> & paths_to_nodes)
928{
929 vector<revision_id> frontier;
930 frontier.push_back(rid);
931
932 while (!frontier.empty())
933 {
934 revision_id rid = frontier.back();
935 frontier.pop_back();
936 if(!null_id(rid)) {
937 set<revision_id> parents;
938 app.db.get_revision_parents(rid, parents);
939 for (set<revision_id>::const_iterator i = parents.begin();
940 i != parents.end(); ++i)
941 {
942 map<revision_id, size_t>::iterator found
943 = paths_to_nodes.find(*i);
944
945 if (found == paths_to_nodes.end())
946 {
947 frontier.push_back(*i);
948 paths_to_nodes.insert(make_pair(*i, 1));
949 }
950 else
951 {
952 (found->second)++;
953 }
954 }
955 }
956 }
957}
958
959void
960do_annotate (app_state &app, file_t file_node, revision_id rid)
961{
962 L(FL("annotating file %s with content %s in revision %s")
963 % file_node->self % file_node->content % rid);
964
965 shared_ptr<annotate_context>
966 acp(new annotate_context(file_node->content, app));
967
968 shared_ptr<annotate_lineage_mapping> lineage
969 = acp->initial_lineage();
970
971 set<revision_id> nodes_complete;
972 map<revision_id, size_t> paths_to_nodes;
973 map<revision_id, lineage_merge_node> pending_merge_nodes;
974 find_ancestors(app, rid, paths_to_nodes);
975
976 // build node work unit
977 deque<annotate_node_work> nodes_to_process;
978 annotate_node_work workunit(acp, lineage, rid, file_node->self);
979 nodes_to_process.push_back(workunit);
980
981 auto_ptr<ticker> revs_ticker(new ticker(N_("revs done"), "r", 1));
982 revs_ticker->set_total(paths_to_nodes.size() + 1);
983
984 while (nodes_to_process.size() && !acp->is_complete())
985 {
986 annotate_node_work work = nodes_to_process.front();
987 nodes_to_process.pop_front();
988 do_annotate_node(work, app, nodes_to_process, nodes_complete,
989 paths_to_nodes, pending_merge_nodes);
990 ++(*revs_ticker);
991 }
992
993 I(pending_merge_nodes.size() == 0);
994 acp->annotate_equivalent_lines();
995 I(acp->is_complete());
996
997 acp->dump(app);
998}
999
1000// Local Variables:
1001// mode: C++
1002// fill-column: 76
1003// c-file-style: "gnu"
1004// indent-tabs-mode: nil
1005// End:
1006// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status