monotone

monotone Mtn Source Tree

Root/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 "roster_delta.hh"
22#include "basic_io.hh"
23#include "paths.hh"
24
25using boost::lexical_cast;
26using std::pair;
27using std::make_pair;
28
29namespace
30{
31
32 struct roster_delta_t
33 {
34 typedef std::set<node_id> nodes_deleted_t;
35 typedef std::map<pair<node_id, path_component>,
36 node_id> dirs_added_t;
37 typedef std::map<pair<node_id, path_component>,
38 pair<node_id, file_id> > files_added_t;
39 typedef std::map<node_id,
40 pair<node_id, path_component> > nodes_renamed_t;
41 typedef std::map<node_id, file_id> deltas_applied_t;
42 typedef std::set<pair<node_id, attr_key> > attrs_cleared_t;
43 typedef std::set<pair<node_id,
44 pair<attr_key,
45 pair<bool, attr_value> > > > attrs_changed_t;
46 typedef std::map<node_id, marking_t> markings_changed_t;
47
48 nodes_deleted_t nodes_deleted;
49 dirs_added_t dirs_added;
50 files_added_t files_added;
51 nodes_renamed_t nodes_renamed;
52 deltas_applied_t deltas_applied;
53 attrs_cleared_t attrs_cleared;
54 attrs_changed_t attrs_changed;
55
56 // nodes_deleted are automatically removed from the marking_map; these are
57 // all markings that are new or changed
58 markings_changed_t markings_changed;
59
60 void
61 apply(roster_t & roster, marking_map & markings) const;
62 };
63
64 void
65 roster_delta_t::apply(roster_t & roster, marking_map & markings) const
66 {
67 // Detach everything that should be detached.
68 for (nodes_deleted_t::const_iterator
69 i = nodes_deleted.begin(); i != nodes_deleted.end(); ++i)
70 roster.detach_node(*i);
71 for (nodes_renamed_t::const_iterator
72 i = nodes_renamed.begin(); i != nodes_renamed.end(); ++i)
73 roster.detach_node(i->first);
74
75 // Delete the delete-able things.
76 for (nodes_deleted_t::const_iterator
77 i = nodes_deleted.begin(); i != nodes_deleted.end(); ++i)
78 roster.drop_detached_node(*i);
79
80 // Add the new things.
81 for (dirs_added_t::const_iterator
82 i = dirs_added.begin(); i != dirs_added.end(); ++i)
83 roster.create_dir_node(i->second);
84 for (files_added_t::const_iterator
85 i = files_added.begin(); i != files_added.end(); ++i)
86 roster.create_file_node(i->second.second, i->second.first);
87
88 // Attach everything.
89 for (dirs_added_t::const_iterator
90 i = dirs_added.begin(); i != dirs_added.end(); ++i)
91 roster.attach_node(i->second, i->first.first, i->first.second);
92 for (files_added_t::const_iterator
93 i = files_added.begin(); i != files_added.end(); ++i)
94 roster.attach_node(i->second.first, i->first.first, i->first.second);
95 for (nodes_renamed_t::const_iterator
96 i = nodes_renamed.begin(); i != nodes_renamed.end(); ++i)
97 roster.attach_node(i->first, i->second.first, i->second.second);
98
99 // Okay, all the tricky tree-rearranging is done, just have to do some
100 // individual node edits now.
101 for (deltas_applied_t::const_iterator
102 i = deltas_applied.begin(); i != deltas_applied.end(); ++i)
103 roster.set_content(i->first, i->second);
104
105 for (attrs_cleared_t::const_iterator
106 i = attrs_cleared.begin(); i != attrs_cleared.end(); ++i)
107 roster.erase_attr(i->first, i->second);
108
109 for (attrs_changed_t::const_iterator
110 i = attrs_changed.begin(); i != attrs_changed.end(); ++i)
111 roster.set_attr_unknown_to_dead_ok(i->first, i->second.first, i->second.second);
112
113 // And finally, update the marking map.
114 for (nodes_deleted_t::const_iterator
115 i = nodes_deleted.begin(); i != nodes_deleted.end(); ++i)
116 safe_erase(markings, *i);
117 for (markings_changed_t::const_iterator
118 i = markings_changed.begin(); i != markings_changed.end(); ++i)
119 markings[i->first] = i->second;
120 }
121
122 void
123 do_delta_for_node_only_in_dest(node_t new_n, roster_delta_t & d)
124 {
125 node_id nid = new_n->self;
126 pair<node_id, path_component> new_loc(new_n->parent, new_n->name);
127
128 if (is_dir_t(new_n))
129 safe_insert(d.dirs_added, make_pair(new_loc, nid));
130 else
131 {
132 file_id const & content = downcast_to_file_t(new_n)->content;
133 safe_insert(d.files_added, make_pair(new_loc,
134 make_pair(nid, content)));
135 }
136 for (full_attr_map_t::const_iterator i = new_n->attrs.begin();
137 i != new_n->attrs.end(); ++i)
138 safe_insert(d.attrs_changed, make_pair(nid, *i));
139 }
140
141 void
142 do_delta_for_node_in_both(node_t old_n, node_t new_n, roster_delta_t & d)
143 {
144 I(old_n->self == new_n->self);
145 node_id nid = old_n->self;
146 // rename?
147 {
148 pair<node_id, path_component> old_loc(old_n->parent, old_n->name);
149 pair<node_id, path_component> new_loc(new_n->parent, new_n->name);
150 if (old_loc != new_loc)
151 safe_insert(d.nodes_renamed, make_pair(nid, new_loc));
152 }
153 // delta?
154 if (is_file_t(old_n))
155 {
156 file_id const & old_content = downcast_to_file_t(old_n)->content;
157 file_id const & new_content = downcast_to_file_t(new_n)->content;
158 if (!(old_content == new_content))
159 safe_insert(d.deltas_applied, make_pair(nid, new_content));
160 }
161 // attrs?
162 {
163 parallel::iter<full_attr_map_t> i(old_n->attrs, new_n->attrs);
164 MM(i);
165 while (i.next())
166 {
167 switch (i.state())
168 {
169 case parallel::invalid:
170 I(false);
171
172 case parallel::in_left:
173 safe_insert(d.attrs_cleared, make_pair(nid, i.left_key()));
174 break;
175
176 case parallel::in_right:
177 safe_insert(d.attrs_changed, make_pair(nid, i.right_value()));
178 break;
179
180 case parallel::in_both:
181 if (i.left_data() != i.right_data())
182 safe_insert(d.attrs_changed, make_pair(nid, i.right_value()));
183 break;
184 }
185 }
186 }
187 }
188
189 void
190 make_roster_delta_t(roster_t const & from, marking_map const & from_markings,
191 roster_t const & to, marking_map const & to_markings,
192 roster_delta_t & d)
193 {
194 MM(from);
195 MM(from_markings);
196 MM(to);
197 MM(to_markings);
198 {
199 parallel::iter<node_map> i(from.all_nodes(), to.all_nodes());
200 MM(i);
201 while (i.next())
202 {
203 switch (i.state())
204 {
205 case parallel::invalid:
206 I(false);
207
208 case parallel::in_left:
209 // deleted
210 safe_insert(d.nodes_deleted, i.left_key());
211 break;
212
213 case parallel::in_right:
214 // added
215 do_delta_for_node_only_in_dest(i.right_data(), d);
216 break;
217
218 case parallel::in_both:
219 // moved/patched/attribute changes
220 do_delta_for_node_in_both(i.left_data(), i.right_data(), d);
221 break;
222 }
223 }
224 }
225 {
226 parallel::iter<marking_map> i(from_markings, to_markings);
227 MM(i);
228 while (i.next())
229 {
230 switch (i.state())
231 {
232 case parallel::invalid:
233 I(false);
234
235 case parallel::in_left:
236 // deleted; don't need to do anything (will be handled by
237 // nodes_deleted set
238 break;
239
240 case parallel::in_right:
241 // added
242 safe_insert(d.markings_changed, i.right_value());
243 break;
244
245 case parallel::in_both:
246 // maybe changed
247 if (!(i.left_data() == i.right_data()))
248 safe_insert(d.markings_changed, i.right_value());
249 break;
250 }
251 }
252 }
253 }
254
255 namespace syms
256 {
257 symbol const deleted("deleted");
258 symbol const rename("rename");
259 symbol const add_dir("add_dir");
260 symbol const add_file("add_file");
261 symbol const delta("delta");
262 symbol const attr_cleared("attr_cleared");
263 symbol const attr_changed("attr_changed");
264 symbol const marking("marking");
265
266 symbol const content("content");
267 symbol const location("location");
268 symbol const attr("attr");
269 symbol const value("value");
270 }
271
272 void
273 push_nid(symbol const & sym, node_id nid, basic_io::stanza & st)
274 {
275 st.push_str_pair(sym, lexical_cast<std::string>(nid));
276 }
277
278 static void
279 push_loc(pair<node_id, path_component> const & loc,
280 basic_io::stanza & st)
281 {
282 st.push_str_triple(syms::location,
283 lexical_cast<std::string>(loc.first),
284 loc.second());
285 }
286
287 void
288 print_roster_delta_t(basic_io::printer & printer,
289 roster_delta_t & d)
290 {
291 for (roster_delta_t::nodes_deleted_t::const_iterator
292 i = d.nodes_deleted.begin(); i != d.nodes_deleted.end(); ++i)
293 {
294 basic_io::stanza st;
295 push_nid(syms::deleted, *i, st);
296 printer.print_stanza(st);
297 }
298 for (roster_delta_t::nodes_renamed_t::const_iterator
299 i = d.nodes_renamed.begin(); i != d.nodes_renamed.end(); ++i)
300 {
301 basic_io::stanza st;
302 push_nid(syms::rename, i->first, st);
303 push_loc(i->second, st);
304 printer.print_stanza(st);
305 }
306 for (roster_delta_t::dirs_added_t::const_iterator
307 i = d.dirs_added.begin(); i != d.dirs_added.end(); ++i)
308 {
309 basic_io::stanza st;
310 push_nid(syms::add_dir, i->second, st);
311 push_loc(i->first, st);
312 printer.print_stanza(st);
313 }
314 for (roster_delta_t::files_added_t::const_iterator
315 i = d.files_added.begin(); i != d.files_added.end(); ++i)
316 {
317 basic_io::stanza st;
318 push_nid(syms::add_file, i->second.first, st);
319 push_loc(i->first, st);
320 st.push_hex_pair(syms::content, i->second.second.inner());
321 printer.print_stanza(st);
322 }
323 for (roster_delta_t::deltas_applied_t::const_iterator
324 i = d.deltas_applied.begin(); i != d.deltas_applied.end(); ++i)
325 {
326 basic_io::stanza st;
327 push_nid(syms::delta, i->first, st);
328 st.push_hex_pair(syms::content, i->second.inner());
329 printer.print_stanza(st);
330 }
331 for (roster_delta_t::attrs_cleared_t::const_iterator
332 i = d.attrs_cleared.begin(); i != d.attrs_cleared.end(); ++i)
333 {
334 basic_io::stanza st;
335 push_nid(syms::attr_cleared, i->first, st);
336 st.push_str_pair(syms::attr, i->second());
337 printer.print_stanza(st);
338 }
339 for (roster_delta_t::attrs_changed_t::const_iterator
340 i = d.attrs_changed.begin(); i != d.attrs_changed.end(); ++i)
341 {
342 basic_io::stanza st;
343 push_nid(syms::attr_changed, i->first, st);
344 st.push_str_pair(syms::attr, i->second.first());
345 st.push_str_triple(syms::value,
346 lexical_cast<std::string>(i->second.second.first),
347 i->second.second.second());
348 printer.print_stanza(st);
349 }
350 for (roster_delta_t::markings_changed_t::const_iterator
351 i = d.markings_changed.begin(); i != d.markings_changed.end(); ++i)
352 {
353 basic_io::stanza st;
354 push_nid(syms::marking, i->first, st);
355 // ...this second argument is a bit odd...
356 push_marking(st, !i->second.file_content.empty(), i->second);
357 printer.print_stanza(st);
358 }
359 }
360
361 node_id
362 parse_nid(basic_io::parser & parser)
363 {
364 std::string s;
365 parser.str(s);
366 return lexical_cast<node_id>(s);
367 }
368
369 void
370 parse_loc(basic_io::parser & parser,
371 pair<node_id, path_component> & loc)
372 {
373 parser.esym(syms::location);
374 loc.first = parse_nid(parser);
375 std::string name;
376 parser.str(name);
377 loc.second = path_component(name);
378 }
379
380 void
381 parse_roster_delta_t(basic_io::parser & parser, roster_delta_t & d)
382 {
383 while (parser.symp(syms::deleted))
384 {
385 parser.sym();
386 safe_insert(d.nodes_deleted, parse_nid(parser));
387 }
388 while (parser.symp(syms::rename))
389 {
390 parser.sym();
391 node_id nid = parse_nid(parser);
392 pair<node_id, path_component> loc;
393 parse_loc(parser, loc);
394 safe_insert(d.nodes_renamed, make_pair(nid, loc));
395 }
396 while (parser.symp(syms::add_dir))
397 {
398 parser.sym();
399 node_id nid = parse_nid(parser);
400 pair<node_id, path_component> loc;
401 parse_loc(parser, loc);
402 safe_insert(d.dirs_added, make_pair(loc, nid));
403 }
404 while (parser.symp(syms::add_file))
405 {
406 parser.sym();
407 node_id nid = parse_nid(parser);
408 pair<node_id, path_component> loc;
409 parse_loc(parser, loc);
410 parser.esym(syms::content);
411 std::string s;
412 parser.hex(s);
413 safe_insert(d.files_added,
414 make_pair(loc, make_pair(nid, file_id(s))));
415 }
416 while (parser.symp(syms::delta))
417 {
418 parser.sym();
419 node_id nid = parse_nid(parser);
420 parser.esym(syms::content);
421 std::string s;
422 parser.hex(s);
423 safe_insert(d.deltas_applied, make_pair(nid, file_id(s)));
424 }
425 while (parser.symp(syms::attr_cleared))
426 {
427 parser.sym();
428 node_id nid = parse_nid(parser);
429 parser.esym(syms::attr);
430 std::string key;
431 parser.str(key);
432 safe_insert(d.attrs_cleared, make_pair(nid, attr_key(key)));
433 }
434 while (parser.symp(syms::attr_changed))
435 {
436 parser.sym();
437 node_id nid = parse_nid(parser);
438 parser.esym(syms::attr);
439 std::string key;
440 parser.str(key);
441 parser.esym(syms::value);
442 std::string value_bool, value_value;
443 parser.str(value_bool);
444 parser.str(value_value);
445 pair<bool, attr_value> full_value(lexical_cast<bool>(value_bool),
446 attr_value(value_value));
447 safe_insert(d.attrs_changed,
448 make_pair(nid,
449 make_pair(attr_key(key), full_value)));
450 }
451 while (parser.symp(syms::marking))
452 {
453 parser.sym();
454 node_id nid = parse_nid(parser);
455 marking_t m;
456 parse_marking(parser, m);
457 safe_insert(d.markings_changed, make_pair(nid, m));
458 }
459 }
460
461} // end anonymous namespace
462
463void
464delta_rosters(roster_t const & from, marking_map const & from_markings,
465 roster_t const & to, marking_map const & to_markings,
466 roster_delta & del)
467{
468 MM(from);
469 MM(from_markings);
470 MM(to);
471 MM(to_markings);
472 roster_delta_t d;
473 make_roster_delta_t(from, from_markings, to, to_markings, d);
474 basic_io::printer printer;
475 print_roster_delta_t(printer, d);
476 del = roster_delta(printer.buf);
477}
478
479static
480void read_roster_delta(roster_delta const & del,
481 roster_delta_t & d)
482{
483 basic_io::input_source src(del.inner()(), "roster_delta");
484 basic_io::tokenizer tok(src);
485 basic_io::parser pars(tok);
486 parse_roster_delta_t(pars, d);
487}
488
489void
490apply_roster_delta(roster_delta const & del,
491 roster_t & roster, marking_map & markings)
492{
493 MM(del);
494 MM(roster);
495 MM(markings);
496
497 roster_delta_t d;
498 read_roster_delta(del, d);
499 d.apply(roster, markings);
500}
501
502// Extract the marking for one node from the roster delta, or return false
503// if they are not contained in that delta
504bool
505try_get_markings_from_roster_delta(roster_delta const & del,
506 node_id const & nid,
507 marking_t & markings)
508{
509 roster_delta_t d;
510 read_roster_delta(del, d);
511
512 std::map<node_id, marking_t>::iterator i = d.markings_changed.find(nid);
513 if (i != d.markings_changed.end())
514 {
515 markings = i->second;
516 return true;
517 }
518 else
519 {
520 return false;
521 }
522}
523
524// Extract the content hash for one node from the roster delta -- if it is
525// available. If we know what the file_id was, we return true and set
526// 'content' appropriately. If we can prove that the file did not exist in
527// this revision, we return true and set 'content' to a null id. If we
528// cannot determine anything about the file contents, then we return false
529// -- in this case content is left undefined.
530bool
531try_get_content_from_roster_delta(roster_delta const & del,
532 node_id const & nid,
533 file_id & content)
534{
535 roster_delta_t d;
536 read_roster_delta(del, d);
537
538 roster_delta_t::deltas_applied_t::const_iterator i = d.deltas_applied.find(nid);
539 if (i != d.deltas_applied.end())
540 {
541 content = i->second;
542 return true;
543 }
544
545 // special case 1: the node was deleted, so we know for sure it's not
546 // there anymore in this roster
547 if (d.nodes_deleted.find(nid) != d.nodes_deleted.end())
548 {
549 content = file_id();
550 return true;
551 }
552
553 // special case 2: the node was added, so we need to get the current
554 // content hash from the add stanza
555 for (roster_delta_t::files_added_t::const_iterator j = d.files_added.begin();
556 j != d.files_added.end(); ++j)
557 {
558 if (j->second.first == nid)
559 {
560 content = j->second.second;
561 return true;
562 }
563 }
564
565 return false;
566}
567
568#ifdef BUILD_UNIT_TESTS
569
570static void
571spin(roster_t const & from, marking_map const & from_marking,
572 roster_t const & to, marking_map const & to_marking)
573{
574 MM(from);
575 MM(from_marking);
576 MM(to);
577 MM(to_marking);
578 roster_delta del;
579 MM(del);
580 delta_rosters(from, from_marking, to, to_marking, del);
581
582 roster_t tmp(from);
583 MM(tmp);
584 marking_map tmp_marking(from_marking);
585 MM(tmp_marking);
586 apply_roster_delta(del, tmp, tmp_marking);
587 I(tmp == to);
588 I(tmp_marking == to_marking);
589
590 roster_delta del2;
591 delta_rosters(from, from_marking, tmp, tmp_marking, del2);
592 I(del == del2);
593}
594
595void test_roster_delta_on(roster_t const & a, marking_map const & a_marking,
596 roster_t const & b, marking_map const & b_marking)
597{
598 spin(a, a_marking, b, b_marking);
599 spin(b, b_marking, a, a_marking);
600}
601
602#endif // BUILD_UNIT_TESTS
603
604
605// Local Variables:
606// mode: C++
607// fill-column: 76
608// c-file-style: "gnu"
609// indent-tabs-mode: nil
610// End:
611// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
612

Archive Download this file

Branches

Tags

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