monotone

monotone Mtn Source Tree

Root/src/roster_delta.cc

1// Copyright (C) 2006 Nathaniel Smith <njs@pobox.com>
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// This file contains "diff"/"patch" code that operates directly on rosters
11// (with their associated markings).
12
13#include "base.hh"
14#include <set>
15#include <map>
16
17#include "lexical_cast.hh"
18
19#include "safe_map.hh"
20#include "parallel_iter.hh"
21#include "cset.hh"
22#include "roster.hh"
23#include "roster_delta.hh"
24#include "basic_io.hh"
25#include "paths.hh"
26#include "transforms.hh"
27
28using boost::lexical_cast;
29using std::pair;
30using std::make_pair;
31using std::string;
32
33namespace
34{
35
36 struct roster_delta_t
37 {
38 typedef std::set<node_id> nodes_deleted_t;
39 typedef std::map<pair<node_id, path_component>,
40 node_id> dirs_added_t;
41 typedef std::map<pair<node_id, path_component>,
42 pair<node_id, file_id> > files_added_t;
43 typedef std::map<node_id,
44 pair<node_id, path_component> > nodes_renamed_t;
45 typedef std::map<node_id, file_id> deltas_applied_t;
46 typedef std::set<pair<node_id, attr_key> > attrs_cleared_t;
47 typedef std::set<pair<node_id,
48 pair<attr_key,
49 pair<bool, attr_value> > > > attrs_changed_t;
50 typedef std::map<node_id, const_marking_t> markings_changed_t;
51
52 nodes_deleted_t nodes_deleted;
53 dirs_added_t dirs_added;
54 files_added_t files_added;
55 nodes_renamed_t nodes_renamed;
56 deltas_applied_t deltas_applied;
57 attrs_cleared_t attrs_cleared;
58 attrs_changed_t attrs_changed;
59
60 // nodes_deleted are automatically removed from the marking_map; these are
61 // all markings that are new or changed
62 markings_changed_t markings_changed;
63
64 void
65 apply(roster_t & roster, marking_map & markings) const;
66 };
67
68 void
69 roster_delta_t::apply(roster_t & roster, marking_map & markings) const
70 {
71 // Detach everything that should be detached.
72 for (nodes_deleted_t::const_iterator
73 i = nodes_deleted.begin(); i != nodes_deleted.end(); ++i)
74 roster.detach_node(*i);
75 for (nodes_renamed_t::const_iterator
76 i = nodes_renamed.begin(); i != nodes_renamed.end(); ++i)
77 roster.detach_node(i->first);
78
79 // Delete the delete-able things.
80 for (nodes_deleted_t::const_iterator
81 i = nodes_deleted.begin(); i != nodes_deleted.end(); ++i)
82 roster.drop_detached_node(*i);
83
84 // Add the new things.
85 for (dirs_added_t::const_iterator
86 i = dirs_added.begin(); i != dirs_added.end(); ++i)
87 roster.create_dir_node(i->second);
88 for (files_added_t::const_iterator
89 i = files_added.begin(); i != files_added.end(); ++i)
90 roster.create_file_node(i->second.second, i->second.first);
91
92 // Attach everything.
93 for (dirs_added_t::const_iterator
94 i = dirs_added.begin(); i != dirs_added.end(); ++i)
95 roster.attach_node(i->second, i->first.first, i->first.second);
96 for (files_added_t::const_iterator
97 i = files_added.begin(); i != files_added.end(); ++i)
98 roster.attach_node(i->second.first, i->first.first, i->first.second);
99 for (nodes_renamed_t::const_iterator
100 i = nodes_renamed.begin(); i != nodes_renamed.end(); ++i)
101 roster.attach_node(i->first, i->second.first, i->second.second);
102
103 // Okay, all the tricky tree-rearranging is done, just have to do some
104 // individual node edits now.
105 for (deltas_applied_t::const_iterator
106 i = deltas_applied.begin(); i != deltas_applied.end(); ++i)
107 roster.set_content(i->first, i->second);
108
109 for (attrs_cleared_t::const_iterator
110 i = attrs_cleared.begin(); i != attrs_cleared.end(); ++i)
111 roster.erase_attr(i->first, i->second);
112
113 for (attrs_changed_t::const_iterator
114 i = attrs_changed.begin(); i != attrs_changed.end(); ++i)
115 roster.set_attr_unknown_to_dead_ok(i->first, i->second.first, i->second.second);
116
117 // And finally, update the marking map.
118 for (nodes_deleted_t::const_iterator
119 i = nodes_deleted.begin(); i != nodes_deleted.end(); ++i)
120 {
121 markings.remove_marking(*i);
122 }
123 for (markings_changed_t::const_iterator
124 i = markings_changed.begin(); i != markings_changed.end(); ++i)
125 {
126 markings.put_or_replace_marking(i->first, i->second);
127 }
128 }
129
130 void
131 do_delta_for_node_only_in_dest(const_node_t new_n, roster_delta_t & d)
132 {
133 node_id nid = new_n->self;
134 pair<node_id, path_component> new_loc(new_n->parent, new_n->name);
135 MM(new_loc.first);
136 MM(new_loc.second);
137 MM(nid);
138
139 if (is_dir_t(new_n))
140 safe_insert(d.dirs_added, make_pair(new_loc, nid));
141 else
142 {
143 file_id const & content = downcast_to_file_t(new_n)->content;
144 safe_insert(d.files_added, make_pair(new_loc,
145 make_pair(nid, content)));
146 }
147 for (attr_map_t::const_iterator i = new_n->attrs.begin();
148 i != new_n->attrs.end(); ++i)
149 safe_insert(d.attrs_changed, make_pair(nid, *i));
150 }
151
152 void
153 do_delta_for_node_in_both(const_node_t old_n, const_node_t new_n, roster_delta_t & d)
154 {
155 I(old_n->self == new_n->self);
156 node_id nid = old_n->self;
157 // rename?
158 {
159 pair<node_id, path_component> old_loc(old_n->parent, old_n->name);
160 pair<node_id, path_component> new_loc(new_n->parent, new_n->name);
161 if (old_loc != new_loc)
162 safe_insert(d.nodes_renamed, make_pair(nid, new_loc));
163 }
164 // delta?
165 if (is_file_t(old_n))
166 {
167 file_id const & old_content = downcast_to_file_t(old_n)->content;
168 file_id const & new_content = downcast_to_file_t(new_n)->content;
169 if (!(old_content == new_content))
170 safe_insert(d.deltas_applied, make_pair(nid, new_content));
171 }
172 // attrs?
173 {
174 parallel::iter<attr_map_t> i(old_n->attrs, new_n->attrs);
175 MM(i);
176 while (i.next())
177 {
178 switch (i.state())
179 {
180 case parallel::invalid:
181 I(false);
182
183 case parallel::in_left:
184 safe_insert(d.attrs_cleared, make_pair(nid, i.left_key()));
185 break;
186
187 case parallel::in_right:
188 safe_insert(d.attrs_changed, make_pair(nid, i.right_value()));
189 break;
190
191 case parallel::in_both:
192 if (i.left_data() != i.right_data())
193 safe_insert(d.attrs_changed, make_pair(nid, i.right_value()));
194 break;
195 }
196 }
197 }
198 }
199
200 void
201 make_unconstrained_roster_delta_t(roster_t const & from,
202 marking_map const & from_markings,
203 roster_t const & to,
204 marking_map const & to_markings,
205 roster_delta_t & d)
206 {
207 MM(from);
208 MM(from_markings);
209 MM(to);
210 MM(to_markings);
211 {
212 parallel::iter<node_map> i(from.all_nodes(), to.all_nodes());
213 MM(i);
214 while (i.next())
215 {
216 switch (i.state())
217 {
218 case parallel::invalid:
219 I(false);
220
221 case parallel::in_left:
222 // deleted
223 safe_insert(d.nodes_deleted, i.left_key());
224 break;
225
226 case parallel::in_right:
227 // added
228 do_delta_for_node_only_in_dest(i.right_data(), d);
229 break;
230
231 case parallel::in_both:
232 // moved/patched/attribute changes
233 do_delta_for_node_in_both(i.left_data(), i.right_data(), d);
234 break;
235 }
236 }
237 }
238 {
239 parallel::iter<marking_map> i(from_markings, to_markings);
240 MM(i);
241 while (i.next())
242 {
243 switch (i.state())
244 {
245 case parallel::invalid:
246 I(false);
247
248 case parallel::in_left:
249 // deleted; don't need to do anything (will be handled by
250 // nodes_deleted set
251 break;
252
253 case parallel::in_right:
254 // added
255 safe_insert(d.markings_changed, i.right_value());
256 break;
257
258 case parallel::in_both:
259 // maybe changed
260 if (!(i.left_data() == i.right_data()) &&
261 !(*i.left_data() == *i.right_data()))
262 safe_insert(d.markings_changed, i.right_value());
263 break;
264 }
265 }
266 }
267 }
268
269 void
270 make_roster_delta_t(roster_t const & from, marking_map const & from_markings,
271 roster_t const & to, marking_map const & to_markings,
272 roster_delta_t & d, cset const * reverse_csp)
273 {
274 if (!reverse_csp)
275 {
276 make_unconstrained_roster_delta_t(from, from_markings,
277 to, to_markings,
278 d);
279 }
280 else
281 {
282 cset const & cs(*reverse_csp);
283 MM(cs);
284
285 typedef std::set<file_path>::const_iterator path_iter;
286 typedef std::map<file_path, file_id>::const_iterator path_id_iter;
287 typedef std::map<file_path, file_path>::const_iterator path_path_iter;
288 typedef std::map<file_path, std::pair<file_id, file_id> >::const_iterator del_iter;
289 typedef std::set<std::pair<file_path, attr_key> >::const_iterator attr_rm_iter;
290 typedef std::map<std::pair<file_path, attr_key>, attr_value>::const_iterator attr_del_iter;
291
292 // in to, or cset source
293 for (path_iter i = cs.nodes_deleted.begin();
294 i != cs.nodes_deleted.end(); ++i)
295 {
296 const_node_t n = to.get_node(*i);
297 do_delta_for_node_only_in_dest(n, d);
298 const_marking_t m = to_markings.get_marking(n->self);
299 safe_insert(d.markings_changed, make_pair(n->self, m));
300 }
301
302
303 class tracking_doer
304 {
305 roster_t const & lr;
306 roster_t const & rr;
307 marking_map const & lmm;
308 marking_map const & rmm;
309 roster_delta_t & d;
310 std::set<file_path> _done;
311 public:
312 tracking_doer(roster_t const & l, roster_t const & r,
313 marking_map const & lmm,
314 marking_map const & rmm,
315 roster_delta_t & d)
316 : lr(l), rr(r), lmm(lmm), rmm(rmm), d(d)
317 { }
318 void note(file_path const & p)
319 {
320 _done.insert(p);
321 }
322 bool try_do(file_path const & lp)
323 {
324 pair<path_iter, bool> x = _done.insert(lp);
325 if (!x.second)
326 return false;
327
328 const_node_t l = lr.get_node(lp);
329 const_node_t r = rr.get_node(l->self);
330 do_delta_for_node_in_both(l, r, d);
331
332 const_marking_t lm = lmm.get_marking(l->self);
333 const_marking_t rm = rmm.get_marking(r->self);
334
335 if (!(lm == rm) || !(*lm == *rm))
336 safe_insert(d.markings_changed, make_pair(r->self, rm));
337
338 return true;
339 }
340 };
341 tracking_doer doer(from, to, from_markings, to_markings, d);
342
343 // in from, or cset target
344 for (path_iter i = cs.dirs_added.begin();
345 i != cs.dirs_added.end(); ++i)
346 {
347 doer.note(*i);
348 safe_insert(d.nodes_deleted, from.get_node(*i)->self);
349 }
350 for (path_id_iter i = cs.files_added.begin();
351 i != cs.files_added.end(); ++i)
352 {
353 doer.note(i->first);
354 safe_insert(d.nodes_deleted, from.get_node(i->first)->self);
355 }
356
357 // in both
358 for (path_path_iter i = cs.nodes_renamed.begin();
359 i != cs.nodes_renamed.end(); ++i)
360 {
361 doer.try_do(i->second);
362 }
363 for (del_iter i = cs.deltas_applied.begin();
364 i != cs.deltas_applied.end(); ++i)
365 {
366 doer.try_do(i->first);
367 }
368 for (attr_rm_iter i = cs.attrs_cleared.begin();
369 i != cs.attrs_cleared.end(); ++i)
370 {
371 doer.try_do(i->first);
372 }
373 for (attr_del_iter i = cs.attrs_set.begin();
374 i != cs.attrs_set.end(); ++i)
375 {
376 doer.try_do(i->first.first);
377 }
378 }
379 }
380
381 namespace syms
382 {
383 symbol const deleted("deleted");
384 symbol const rename("rename");
385 symbol const add_dir("add_dir");
386 symbol const add_file("add_file");
387 symbol const delta("delta");
388 symbol const attr_cleared("attr_cleared");
389 symbol const attr_changed("attr_changed");
390 symbol const marking("marking");
391
392 symbol const content("content");
393 symbol const location("location");
394 symbol const attr("attr");
395 symbol const value("value");
396 }
397
398 void
399 push_nid(symbol const & sym, node_id nid, string & contents, int symbol_length)
400 {
401 contents.append(symbol_length - sym().size(), ' ');
402 contents.append(sym());
403 contents.append(" \"");
404 contents.append(lexical_cast<string>(nid));
405 contents.append("\"\n");
406 }
407
408 static void
409 push_loc(pair<node_id, path_component> const & loc,
410 string & contents, int symbol_length)
411 {
412 contents.append(symbol_length - 8, ' ');
413 contents.append("location \"");
414 contents.append(lexical_cast<string>(loc.first));
415 contents.append("\" \"");
416 append_with_escaped_quotes(contents, loc.second());
417 contents.append("\"\n");
418 }
419
420 void
421 print_roster_delta_t(data & dat,
422 roster_delta_t & d)
423 {
424 string contents;
425
426 for (roster_delta_t::nodes_deleted_t::const_iterator
427 i = d.nodes_deleted.begin(); i != d.nodes_deleted.end(); ++i)
428 {
429 push_nid(syms::deleted, *i, contents, 7);
430 contents += "\n";
431 }
432 for (roster_delta_t::nodes_renamed_t::const_iterator
433 i = d.nodes_renamed.begin(); i != d.nodes_renamed.end(); ++i)
434 {
435 push_nid(syms::rename, i->first, contents, 8);
436 push_loc(i->second, contents, 8);
437 contents += "\n";
438 }
439 for (roster_delta_t::dirs_added_t::const_iterator
440 i = d.dirs_added.begin(); i != d.dirs_added.end(); ++i)
441 {
442 push_nid(syms::add_dir, i->second, contents, 8);
443 push_loc(i->first, contents, 8);
444 contents += "\n";
445 }
446 for (roster_delta_t::files_added_t::const_iterator
447 i = d.files_added.begin(); i != d.files_added.end(); ++i)
448 {
449 push_nid(syms::add_file, i->second.first, contents, 8);
450 push_loc(i->first, contents, 8);
451 contents.append(" content [");
452 contents.append(encode_hexenc(i->second.second.inner()(), origin::internal));
453 contents.append("]\n\n");
454 }
455 for (roster_delta_t::deltas_applied_t::const_iterator
456 i = d.deltas_applied.begin(); i != d.deltas_applied.end(); ++i)
457 {
458 push_nid(syms::delta, i->first, contents, 7);
459 contents.append("content [");
460 contents.append(encode_hexenc(i->second.inner()(), origin::internal));
461 contents.append("]\n\n");
462 }
463 for (roster_delta_t::attrs_cleared_t::const_iterator
464 i = d.attrs_cleared.begin(); i != d.attrs_cleared.end(); ++i)
465 {
466 push_nid(syms::attr_cleared, i->first, contents, 12);
467 contents.append(" attr \"");
468 append_with_escaped_quotes(contents, i->second());
469 contents.append("\"\n\n");
470 }
471 for (roster_delta_t::attrs_changed_t::const_iterator
472 i = d.attrs_changed.begin(); i != d.attrs_changed.end(); ++i)
473 {
474 push_nid(syms::attr_changed, i->first, contents, 12);
475 contents.append(" attr \"");
476 append_with_escaped_quotes(contents, i->second.first());
477 contents.append("\"\n value \"");
478 contents.append(lexical_cast<string>(i->second.second.first));
479 contents.append("\" \"");
480 append_with_escaped_quotes(contents, i->second.second.second());
481 contents.append("\"\n\n");
482 }
483 for (roster_delta_t::markings_changed_t::const_iterator
484 i = d.markings_changed.begin(); i != d.markings_changed.end(); ++i)
485 {
486 bool is_file = !i->second->file_content.empty();
487 int symbol_length = (is_file ? 12 : 9);
488 push_nid(syms::marking, i->first, contents, symbol_length);
489 push_marking(contents, is_file, i->second, symbol_length);
490 contents.append("\n");
491 }
492 // I wouldn't think it should be possible to have empty contents here,
493 // but apparently it is.
494 if (!contents.empty())
495 {
496 contents.erase(contents.size() - 1); // drop last extra trailing newline
497 }
498 dat = data(contents, origin::internal);
499 }
500
501 node_id
502 parse_nid(basic_io::parser & parser)
503 {
504 std::string s;
505 parser.str(s);
506 return lexical_cast<node_id>(s);
507 }
508
509 void
510 parse_loc(basic_io::parser & parser,
511 pair<node_id, path_component> & loc)
512 {
513 parser.esym(syms::location);
514 loc.first = parse_nid(parser);
515 std::string name;
516 parser.str(name);
517 loc.second = path_component(name, parser.tok.in.made_from);
518 }
519
520 void
521 parse_roster_delta_t(basic_io::parser & parser, roster_delta_t & d)
522 {
523 while (parser.symp(syms::deleted))
524 {
525 parser.sym();
526 safe_insert(d.nodes_deleted, parse_nid(parser));
527 }
528 while (parser.symp(syms::rename))
529 {
530 parser.sym();
531 node_id nid = parse_nid(parser);
532 pair<node_id, path_component> loc;
533 parse_loc(parser, loc);
534 safe_insert(d.nodes_renamed, make_pair(nid, loc));
535 }
536 while (parser.symp(syms::add_dir))
537 {
538 parser.sym();
539 node_id nid = parse_nid(parser);
540 pair<node_id, path_component> loc;
541 parse_loc(parser, loc);
542 safe_insert(d.dirs_added, make_pair(loc, nid));
543 }
544 while (parser.symp(syms::add_file))
545 {
546 parser.sym();
547 node_id nid = parse_nid(parser);
548 pair<node_id, path_component> loc;
549 parse_loc(parser, loc);
550 parser.esym(syms::content);
551 std::string s;
552 parser.hex(s);
553 safe_insert(d.files_added,
554 make_pair(loc, make_pair(nid, decode_hexenc_as<file_id>(s, parser.tok.in.made_from))));
555 }
556 while (parser.symp(syms::delta))
557 {
558 parser.sym();
559 node_id nid = parse_nid(parser);
560 parser.esym(syms::content);
561 std::string s;
562 parser.hex(s);
563 safe_insert(d.deltas_applied, make_pair(nid, decode_hexenc_as<file_id>(s, parser.tok.in.made_from)));
564 }
565 while (parser.symp(syms::attr_cleared))
566 {
567 parser.sym();
568 node_id nid = parse_nid(parser);
569 parser.esym(syms::attr);
570 std::string key;
571 parser.str(key);
572 safe_insert(d.attrs_cleared, make_pair(nid, attr_key(key,
573 parser.tok.in.made_from)));
574 }
575 while (parser.symp(syms::attr_changed))
576 {
577 parser.sym();
578 node_id nid = parse_nid(parser);
579 parser.esym(syms::attr);
580 std::string key;
581 parser.str(key);
582 parser.esym(syms::value);
583 std::string value_bool, value_value;
584 parser.str(value_bool);
585 parser.str(value_value);
586 pair<bool, attr_value> full_value(lexical_cast<bool>(value_bool),
587 attr_value(value_value,
588 parser.tok.in.made_from));
589 safe_insert(d.attrs_changed,
590 make_pair(nid,
591 make_pair(attr_key(key, parser.tok.in.made_from),
592 full_value)));
593 }
594 while (parser.symp(syms::marking))
595 {
596 parser.sym();
597 node_id nid = parse_nid(parser);
598 marking_t m(new marking());
599 parse_marking(parser, m);
600 safe_insert(d.markings_changed, make_pair(nid, m));
601 }
602 }
603
604} // end anonymous namespace
605
606void
607delta_rosters(roster_t const & from, marking_map const & from_markings,
608 roster_t const & to, marking_map const & to_markings,
609 roster_delta & del,
610 cset const * reverse_cs)
611{
612 MM(from);
613 MM(from_markings);
614 MM(to);
615 MM(to_markings);
616 roster_delta_t d;
617 make_roster_delta_t(from, from_markings, to, to_markings, d, reverse_cs);
618 data dat;
619 print_roster_delta_t(dat, d);
620 del = roster_delta(dat(), origin::internal);
621}
622
623static
624void read_roster_delta(roster_delta const & del,
625 roster_delta_t & d)
626{
627 basic_io::input_source src(del.inner()(), "roster_delta");
628 basic_io::tokenizer tok(src);
629 basic_io::parser pars(tok);
630 parse_roster_delta_t(pars, d);
631}
632
633void
634apply_roster_delta(roster_delta const & del,
635 roster_t & roster, marking_map & markings)
636{
637 MM(del);
638 MM(roster);
639 MM(markings);
640
641 roster_delta_t d;
642 read_roster_delta(del, d);
643 d.apply(roster, markings);
644}
645
646// Extract the marking for one node from the roster delta, or return false
647// if they are not contained in that delta
648bool
649try_get_markings_from_roster_delta(roster_delta const & del,
650 node_id const & nid,
651 const_marking_t & markings)
652{
653 roster_delta_t d;
654 read_roster_delta(del, d);
655
656 std::map<node_id, const_marking_t>::iterator i = d.markings_changed.find(nid);
657 if (i != d.markings_changed.end())
658 {
659 markings = i->second;
660 return true;
661 }
662 else
663 {
664 return false;
665 }
666}
667
668// Extract the content hash for one node from the roster delta -- if it is
669// available. If we know what the file_id was, we return true and set
670// 'content' appropriately. If we can prove that the file did not exist in
671// this revision, we return true and set 'content' to a null id. If we
672// cannot determine anything about the file contents, then we return false
673// -- in this case content is left undefined.
674bool
675try_get_content_from_roster_delta(roster_delta const & del,
676 node_id const & nid,
677 file_id & content)
678{
679 roster_delta_t d;
680 read_roster_delta(del, d);
681
682 roster_delta_t::deltas_applied_t::const_iterator i = d.deltas_applied.find(nid);
683 if (i != d.deltas_applied.end())
684 {
685 content = i->second;
686 return true;
687 }
688
689 // special case 1: the node was deleted, so we know for sure it's not
690 // there anymore in this roster
691 if (d.nodes_deleted.find(nid) != d.nodes_deleted.end())
692 {
693 content = file_id();
694 return true;
695 }
696
697 // special case 2: the node was added, so we need to get the current
698 // content hash from the add stanza
699 for (roster_delta_t::files_added_t::const_iterator j = d.files_added.begin();
700 j != d.files_added.end(); ++j)
701 {
702 if (j->second.first == nid)
703 {
704 content = j->second.second;
705 return true;
706 }
707 }
708
709 return false;
710}
711
712// Local Variables:
713// mode: C++
714// fill-column: 76
715// c-file-style: "gnu"
716// indent-tabs-mode: nil
717// End:
718// 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