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

Archive Download this file

Branches

Tags

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