monotone

monotone Mtn Source Tree

Root/patch_set.cc

1// copyright (C) 2002, 2003 graydon hoare <graydon@pobox.com>
2// all rights reserved.
3// licensed to the public under the terms of the GNU GPL (>= 2)
4// see the file COPYING for details
5
6#include <sstream>
7
8#include "sanity.hh"
9#include "patch_set.hh"
10#include "file_io.hh"
11#include "transforms.hh"
12#include "packet.hh"
13
14//
15// a patch set is derived from a pair of manifests.
16//
17// for each addition between the manifests, we must decide if it represents
18// a "new" file or a change from an old file.
19//
20// the add is a change if any of these are true:
21// - there is a delete with an identical filename (a "true delta")
22// - there is a delete with an identical sha1 (a move)
23//
24// these are tried in order. logic for a deletion is symmetrical.
25//
26// for each true change, we calculate an rdiff and add it to the deltas
27// section of the patch set.
28//
29// for each non-change add, we insert its full data in the adds section of
30// the patch set.
31//
32// true deletes do not need to be explicitly mentionned outside of the
33// manifest delta since their status is implicit from the presence of
34// adds and deltas -- they are the only deletes not mentionned as deltas.
35//
36// we then packetize or summarize the data for our users
37//
38
39using namespace std;
40
41bool operator<(const patch_move & a,
42 const patch_move & b)
43{
44 return ((a.path_old < b.path_old)
45 || ((a.path_old == b.path_old) && (a.path_new < b.path_new)));
46}
47
48bool operator<(const patch_addition & a,
49 const patch_addition & b)
50{
51 return ((a.path < b.path) ||
52 ((a.path == b.path) && (a.ident < b.ident)));
53}
54
55bool operator<(const patch_delta & a,
56 const patch_delta & b)
57{
58 return
59 (a.path < b.path)
60 || ((a.path == b.path) && a.id_new < b.id_new)
61 || (((a.path == b.path) && a.id_new == b.id_new) && a.id_old < b.id_old);
62}
63
64patch_delta::patch_delta(file_id const & o,
65 file_id const & n,
66 file_path const & p)
67 : id_old(o), id_new(n), path(p)
68{}
69
70patch_addition::patch_addition(file_id const & i,
71 file_path const & p)
72 : ident(i), path(p)
73{}
74
75patch_move::patch_move(file_path const & o, file_path const & n)
76 : path_old(o), path_new(n)
77{}
78
79
80typedef set<entry>::const_iterator eci;
81
82struct path_id_bijection
83{
84 size_t size()
85 {
86 I(forward.size() == backward.size());
87 return forward.size();
88 }
89
90 void add(path_id_pair const & pip)
91 {
92 I(forward.size() == backward.size());
93 // nb: we preserve the bijective property of this map at the expense of
94 // possibly missing some add/delete matching cases. for example, if an
95 // identical file is deleted as one path name and added as two new path
96 // names, we will record it as an add + a move, rather than anything
97 // more clever.
98 if (exists(pip.path()) || exists(pip.ident()))
99 return;
100 forward.insert(make_pair(pip.path(), pip.ident()));
101 backward.insert(make_pair(pip.ident(), pip.path()));
102 I(forward.size() == backward.size());
103 }
104
105 void add(entry const & e)
106 {
107 add(path_id_pair(e));
108 }
109
110 void del(path_id_pair const & pip)
111 {
112 I(forward.size() > 0);
113 I(backward.size() > 0);
114 I(forward.size() == backward.size());
115 if (exists(pip.path()))
116 {
117file_id fid = get(pip.path());
118forward.erase(pip.path());
119backward.erase(fid);
120 }
121 else if (exists(pip.ident()))
122 {
123file_path pth = get(pip.ident());
124forward.erase(pth);
125backward.erase(pip.ident());
126 }
127 else
128 {
129I(false); // trip assert. you should not have done that.
130 }
131 I(forward.size() == backward.size());
132 }
133
134 void copy_to(set<patch_addition> & adds)
135 {
136 I(forward.size() == backward.size());
137 I(adds.size() == 0);
138 for (map<file_id, file_path>::const_iterator i = backward.begin();
139 i != backward.end(); ++i)
140 {
141adds.insert(patch_addition(i->first, i->second));
142 }
143 I(adds.size() == backward.size());
144 I(adds.size() == forward.size());
145 }
146
147 void del(entry const & e)
148 {
149 del(path_id_pair(e));
150 }
151
152 bool exists(file_path const & p)
153 {
154 I(forward.size() == backward.size());
155 return forward.find(p) != forward.end();
156 }
157
158 bool exists(file_id const & i)
159 {
160 I(forward.size() == backward.size());
161 return backward.find(i) != backward.end();
162 }
163
164 file_id const & get(file_path const & path)
165 {
166 I(exists(path));
167 return forward[path];
168 }
169
170 file_path const & get(file_id const & ident)
171 {
172 I(exists(ident));
173 return backward[ident];
174 }
175
176 map<file_path, file_id > forward;
177 map<file_id, file_path > backward;
178};
179
180
181static void index_adds(set<entry> const & adds,
182 path_id_bijection & mapping)
183{
184 for(eci i = adds.begin(); i != adds.end(); ++i)
185 {
186 L(F("indexing add: %s %s\n") % i->first % i->second);
187 I(i->first() != "");
188 I(i->second.inner()() != "");
189 mapping.add(*i);
190 }
191}
192
193static void classify_dels(set<entry> const & in_dels,
194 path_id_bijection & adds,
195 version_existence_check & vc,
196 set<file_path> & dels,
197 set<patch_move> & moves,
198 set<patch_delta> & deltas)
199{
200 size_t const initial_num_adds = adds.size();
201 size_t const initial_num_dels = in_dels.size();
202
203 for(eci i = in_dels.begin(); i != in_dels.end(); ++i)
204 {
205 I(adds.size() + moves.size() + deltas.size() == initial_num_adds);
206 I(dels.size() + moves.size() + deltas.size() <= initial_num_dels);
207
208 path_id_pair pip(*i);
209
210 if (adds.exists(pip.path()))
211{
212 // there is an add which matches this delete
213 if (vc.check(pip.ident()))
214 {
215 // this is a "true delta"
216 L(F("found true delta %s\n") % pip.path());
217 file_id new_id = adds.get(pip.path());
218 deltas.insert(patch_delta(pip.ident(), new_id, pip.path()));
219 adds.del(pip);
220 }
221 else
222 {
223 // this is a recoverable error: treat as a true delete
224 // (accompanied by a true insert)
225 L(F("found probable delta %s %s but no pre-version in database\n")
226% pip.path() % pip.ident());
227 dels.insert(pip.path());
228 }
229}
230 else if (adds.exists(pip.ident()))
231{
232 // there is a matching add of a file with the same id, so this is
233 // a "simple delta" (a move)
234 file_path dest = adds.get(pip.ident());
235 L(F("found move %s -> %s\n") % pip.path() % dest);
236 moves.insert(patch_move(pip.path(), dest));
237 adds.del(pip);
238}
239 else
240{
241 // this is a "true delete"
242 L(F("found delete %s\n") % pip.path());
243 dels.insert(pip.path());
244}
245 }
246}
247
248struct app_based_version_check :
249 public version_existence_check
250{
251 app_state & app;
252 app_based_version_check(app_state & a) : app(a) {}
253 virtual bool check(file_id i)
254 {
255 return app.db.file_version_exists(i);
256 }
257};
258
259void manifests_to_patch_set(manifest_map const & m_old,
260 manifest_map const & m_new,
261 app_state & app,
262 patch_set & ps)
263{
264 app_based_version_check abc(app);
265 manifests_to_patch_set(m_old, m_new, app, abc, ps);
266}
267
268void manifests_to_patch_set(manifest_map const & m_old,
269 manifest_map const & m_new,
270 rename_edge const & renames,
271 app_state & app,
272 patch_set & ps)
273{
274 app_based_version_check abc(app);
275 manifests_to_patch_set(m_old, m_new, renames, abc, ps);
276}
277
278void manifests_to_patch_set(manifest_map const & m_old,
279 manifest_map const & m_new,
280 app_state & app,
281 version_existence_check & vc,
282 patch_set & ps)
283{
284 rename_edge renames;
285 manifest_id old_id, new_id;
286 calculate_ident(m_old, old_id);
287 calculate_ident(m_new, new_id);
288 calculate_renames (old_id, new_id, app, renames);
289
290 if (renames.parent.inner()() == "")
291 renames.parent = old_id;
292 else
293 I(renames.parent == old_id);
294
295 if (renames.child.inner()() == "")
296 renames.child = new_id;
297 else
298 I(renames.child == new_id);
299
300 manifests_to_patch_set(m_old, m_new, renames, vc, ps);
301}
302
303void manifests_to_patch_set(manifest_map const & m_old,
304 manifest_map const & m_new,
305 rename_edge const & renames,
306 version_existence_check & vc,
307 patch_set & ps)
308
309{
310 ps.m_old = renames.parent;
311 ps.m_new = renames.child;
312 ps.map_old = m_old;
313 ps.map_new = m_new;
314 ps.f_adds.clear();
315 ps.f_deltas.clear();
316 ps.f_moves.clear();
317 ps.f_dels.clear();
318
319 I(renames.parent.inner()() != "");
320 I(renames.child.inner()() != "");
321
322 // calculate ids
323 L(F("building patch set %s -> %s\n") % ps.m_old % ps.m_new);
324
325 // calculate manifest_changes structure
326 manifest_changes changes;
327 calculate_manifest_changes(m_old, m_new, changes);
328 L(F("constructed manifest_changes (%d dels, %d adds)\n")
329 % changes.dels.size() % changes.adds.size());
330
331 // analyze adds and dels in manifest_changes
332 path_id_bijection add_mapping;
333 index_adds(changes.adds, add_mapping);
334 size_t num_add_candidates = add_mapping.size();
335 classify_dels(changes.dels, add_mapping, vc,
336ps.f_dels, ps.f_moves, ps.f_deltas);
337
338 size_t move_and_edits = 0;
339 // incorporate explicit renames we might have got
340 for (rename_set::const_iterator i = renames.mapping.begin();
341 i != renames.mapping.end(); ++i)
342 {
343 if (ps.f_dels.find(i->first) != ps.f_dels.end() &&
344 add_mapping.exists(i->second))
345{
346 ps.f_dels.erase (i->first);
347 file_id fid = add_mapping.get(i->second);
348 add_mapping.del (make_pair(i->second, fid));
349 ps.f_moves.insert (patch_move (i->first, i->second));
350 L(F("found explicit move %s -> %s\n") % i->first % i->second);
351 manifest_map::const_iterator old_entry = m_old.find(i->first);
352 I(old_entry != m_old.end());
353 file_id old_fid = old_entry->second;
354 if (! (old_fid == fid))
355 {
356 L(F("explicit move %s -> %s accompanied by delta %s -> %s\n")
357% i->first % i->second % old_fid % fid);
358 patch_delta delta(old_fid, fid, i->second);
359 I(ps.f_deltas.find(delta) == ps.f_deltas.end());
360 ps.f_deltas.insert(delta);
361 ++move_and_edits;
362 }
363}
364 }
365
366 // now copy any remaining unmatched adds into ps.f_adds
367 add_mapping.copy_to(ps.f_adds);
368
369 // all done, log and assert to be sure.
370 if (ps.f_adds.size() > 0)
371 L(F("found %d plain additions\n") % ps.f_adds.size());
372 if (ps.f_dels.size() > 0)
373 L(F("found %d plain deletes\n") % ps.f_dels.size());
374 if (ps.f_deltas.size() > 0)
375 L(F("matched %d del/add pairs as deltas\n") % ps.f_deltas.size());
376 if (ps.f_moves.size() > 0)
377 L(F("matched %d del/add pairs as moves\n") % ps.f_moves.size());
378 I(ps.f_dels.size() + ps.f_moves.size()
379 + ps.f_deltas.size() - move_and_edits == changes.dels.size());
380 I(ps.f_adds.size() + ps.f_moves.size()
381 + ps.f_deltas.size() - move_and_edits == num_add_candidates);
382}
383
384
385
386// this produces an imprecise, textual summary of the patch set
387void patch_set_to_text_summary(patch_set const & ps,
388 ostream & str)
389{
390 str << "Old manifest: " << ps.m_old.inner()() << endl;
391 str << "New manifest: " << ps.m_new.inner()() << endl;
392 str << "Summary of changes:" << endl;
393
394 if (ps.f_dels.empty() && ps.f_adds.empty()
395 && ps.f_moves.empty() && ps.f_deltas.empty())
396 {
397 str << " no changes" << endl;
398 return;
399 }
400
401 for (set<file_path>::const_iterator i = ps.f_dels.begin();
402 i != ps.f_dels.end(); ++i)
403 str << " delete " << (*i)() << endl;
404
405 for (set<patch_addition >::const_iterator i = ps.f_adds.begin();
406 i != ps.f_adds.end(); ++i)
407 str << " add " << i->path() << " as " << i->ident.inner()() << endl;
408
409 for (set<patch_move>::const_iterator i = ps.f_moves.begin();
410 i != ps.f_moves.end(); ++i)
411 str << " move " << i->path_old() << " -> " << i->path_new() << endl;
412
413 for (set<patch_delta>::const_iterator i = ps.f_deltas.begin();
414 i != ps.f_deltas.end(); ++i)
415 str << " patch " << i->path() << " " << i->id_old.inner()() << " -> " << i->id_new.inner()() << endl;
416}
417
418
419void patch_set_to_packets(patch_set const & ps,
420 app_state & app,
421 packet_consumer & cons)
422{
423
424 // manifest delta packet
425
426 I(app.db.manifest_version_exists(ps.m_new));
427
428 if (app.db.manifest_version_exists(ps.m_old))
429 {
430 base64< gzip<delta> > del;
431 diff(ps.map_old, ps.map_new, del);
432 cons.consume_manifest_delta(ps.m_old, ps.m_new, manifest_delta(del));
433 }
434 else
435 {
436 manifest_data m_new_data;
437 write_manifest_map(ps.map_new, m_new_data);
438 cons.consume_manifest_data(ps.m_new, m_new_data);
439 }
440
441 // new file packets
442 for (set<patch_addition>::const_iterator i = ps.f_adds.begin();
443 i != ps.f_adds.end(); ++i)
444 {
445 file_data dat;
446 app.db.get_file_version(i->ident, dat);
447 cons.consume_file_data(i->ident, dat);
448 }
449
450 // file delta packets
451 for (set<patch_delta>::const_iterator i = ps.f_deltas.begin();
452 i != ps.f_deltas.end(); ++i)
453 {
454 file_data old_data, new_data;
455 I(app.db.file_version_exists(i->id_new));
456 app.db.get_file_version(i->id_new, new_data);
457 if (app.db.file_version_exists(i->id_old))
458{
459 app.db.get_file_version(i->id_old, old_data);
460 base64< gzip<delta> > del;
461 diff(old_data.inner(), new_data.inner(), del);
462 cons.consume_file_delta(i->id_old, i->id_new, file_delta(del));
463}
464 else
465{
466 cons.consume_file_data(i->id_new, new_data);
467}
468 }
469}

Archive Download this file

Branches

Tags

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