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

Archive Download this file

Branches

Tags

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