monotone

monotone Mtn Source Tree

Root/src/cset.cc

1// Copyright (C) 2005 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#include "base.hh"
11#include <map>
12#include <set>
13
14#include "basic_io.hh"
15#include "cset.hh"
16#include "sanity.hh"
17#include "safe_map.hh"
18#include "transforms.hh"
19
20using std::set;
21using std::map;
22using std::pair;
23using std::string;
24using std::make_pair;
25
26static void
27check_normalized(cset const & cs)
28{
29 MM(cs);
30
31 // normalize:
32 //
33 // add_file foo@id1 + apply_delta id1->id2
34 // clear_attr foo:bar + set_attr foo:bar=baz
35 //
36 // possibly more?
37
38 // no file appears in both the "added" list and the "patched" list
39 {
40 map<file_path, file_id>::const_iterator a = cs.files_added.begin();
41 map<file_path, pair<file_id, file_id> >::const_iterator
42 d = cs.deltas_applied.begin();
43 while (a != cs.files_added.end() && d != cs.deltas_applied.end())
44 {
45 // SPEEDUP?: should this use lower_bound instead of ++? it should
46 // make this loop iterate about as many times as the shorter list,
47 // rather the sum of the two lists...
48 if (a->first < d->first)
49 ++a;
50 else if (d->first < a->first)
51 ++d;
52 else
53 I(false);
54 }
55 }
56
57 // no file+attr pair appears in both the "set" list and the "cleared" list
58 {
59 set<pair<file_path, attr_key> >::const_iterator c = cs.attrs_cleared.begin();
60 map<pair<file_path, attr_key>, attr_value>::const_iterator
61 s = cs.attrs_set.begin();
62 while (c != cs.attrs_cleared.end() && s != cs.attrs_set.end())
63 {
64 if (*c < s->first)
65 ++c;
66 else if (s->first < *c)
67 ++s;
68 else
69 I(false);
70 }
71 }
72}
73
74bool
75cset::empty() const
76{
77 return
78 nodes_deleted.empty()
79 && dirs_added.empty()
80 && files_added.empty()
81 && nodes_renamed.empty()
82 && deltas_applied.empty()
83 && attrs_cleared.empty()
84 && attrs_set.empty();
85}
86
87void
88cset::clear()
89{
90 nodes_deleted.clear();
91 dirs_added.clear();
92 files_added.clear();
93 nodes_renamed.clear();
94 deltas_applied.clear();
95 attrs_cleared.clear();
96 attrs_set.clear();
97}
98
99struct
100detach
101{
102 detach(file_path const & src)
103 : src_path(src),
104 reattach(false)
105 {}
106
107 detach(file_path const & src,
108 file_path const & dst)
109 : src_path(src),
110 reattach(true),
111 dst_path(dst)
112 {}
113
114 file_path src_path;
115 bool reattach;
116 file_path dst_path;
117
118 bool operator<(struct detach const & other) const
119 {
120 // We sort detach operations bottom-up by src path
121 // SPEEDUP?: simply sort by path.size() rather than full lexicographical
122 // comparison?
123 return other.src_path < src_path;
124 }
125};
126
127struct
128attach
129{
130 attach(node_id n,
131 file_path const & p)
132 : node(n), path(p)
133 {}
134
135 node_id node;
136 file_path path;
137
138 bool operator<(struct attach const & other) const
139 {
140 // We sort attach operations top-down by path
141 // SPEEDUP?: simply sort by path.size() rather than full lexicographical
142 // comparison?
143 return path < other.path;
144 }
145};
146
147void
148cset::apply_to(editable_tree & t) const
149{
150 // SPEEDUP?: use vectors and sort them once, instead of maintaining sorted
151 // sets?
152 set<detach> detaches;
153 set<attach> attaches;
154 set<node_id> drops;
155
156 MM(*this);
157
158 check_normalized(*this);
159
160 // Decompose all additions into a set of pending attachments to be
161 // executed top-down. We might as well do this first, to be sure we
162 // can form the new nodes -- such as in a filesystem -- before we do
163 // anything else potentially destructive. This should all be
164 // happening in a temp directory anyways.
165
166 // NB: it's very important we do safe_insert's here, because our comparison
167 // operator for attach and detach does not distinguish all nodes! the nodes
168 // that it does not distinguish are ones where we're attaching or detaching
169 // repeatedly from the same place, so they're impossible anyway, but we need
170 // to error out if someone tries to add them.
171
172 for (set<file_path>::const_iterator i = dirs_added.begin();
173 i != dirs_added.end(); ++i)
174 safe_insert(attaches, attach(t.create_dir_node(), *i));
175
176 for (map<file_path, file_id>::const_iterator i = files_added.begin();
177 i != files_added.end(); ++i)
178 safe_insert(attaches, attach(t.create_file_node(i->second), i->first));
179
180
181 // Decompose all path deletion and the first-half of renamings on
182 // existing paths into the set of pending detaches, to be executed
183 // bottom-up.
184
185 for (set<file_path>::const_iterator i = nodes_deleted.begin();
186 i != nodes_deleted.end(); ++i)
187 safe_insert(detaches, detach(*i));
188
189 for (map<file_path, file_path>::const_iterator i = nodes_renamed.begin();
190 i != nodes_renamed.end(); ++i)
191 safe_insert(detaches, detach(i->first, i->second));
192
193
194 // Execute all the detaches, rescheduling the results of each detach
195 // for either attaching or dropping.
196
197 for (set<detach>::const_iterator i = detaches.begin();
198 i != detaches.end(); ++i)
199 {
200 node_id n = t.detach_node(i->src_path);
201 if (i->reattach)
202 safe_insert(attaches, attach(n, i->dst_path));
203 else
204 safe_insert(drops, n);
205 }
206
207
208 // Execute all the attaches.
209
210 for (set<attach>::const_iterator i = attaches.begin(); i != attaches.end(); ++i)
211 t.attach_node(i->node, i->path);
212
213
214 // Execute all the drops.
215
216 for (set<node_id>::const_iterator i = drops.begin(); i != drops.end(); ++i)
217 t.drop_detached_node (*i);
218
219
220 // Execute all the in-place edits
221 for (map<file_path, pair<file_id, file_id> >::const_iterator i = deltas_applied.begin();
222 i != deltas_applied.end(); ++i)
223 t.apply_delta(i->first, i->second.first, i->second.second);
224
225 for (set<pair<file_path, attr_key> >::const_iterator i = attrs_cleared.begin();
226 i != attrs_cleared.end(); ++i)
227 t.clear_attr(i->first, i->second);
228
229 for (map<pair<file_path, attr_key>, attr_value>::const_iterator i = attrs_set.begin();
230 i != attrs_set.end(); ++i)
231 t.set_attr(i->first.first, i->first.second, i->second);
232
233 t.commit();
234}
235
236////////////////////////////////////////////////////////////////////
237// I/O routines
238////////////////////////////////////////////////////////////////////
239
240namespace
241{
242 namespace syms
243 {
244 // cset symbols
245 symbol const delete_node("delete");
246 symbol const rename_node("rename");
247 symbol const content("content");
248 symbol const add_file("add_file");
249 symbol const add_dir("add_dir");
250 symbol const patch("patch");
251 symbol const from("from");
252 symbol const to("to");
253 symbol const clear("clear");
254 symbol const set("set");
255 symbol const attr("attr");
256 symbol const value("value");
257 }
258}
259
260void
261print_cset(basic_io::printer & printer,
262 cset const & cs)
263{
264 for (set<file_path>::const_iterator i = cs.nodes_deleted.begin();
265 i != cs.nodes_deleted.end(); ++i)
266 {
267 basic_io::stanza st;
268 st.push_file_pair(syms::delete_node, *i);
269 printer.print_stanza(st);
270 }
271
272 for (map<file_path, file_path>::const_iterator i = cs.nodes_renamed.begin();
273 i != cs.nodes_renamed.end(); ++i)
274 {
275 basic_io::stanza st;
276 st.push_file_pair(syms::rename_node, i->first);
277 st.push_file_pair(syms::to, i->second);
278 printer.print_stanza(st);
279 }
280
281 for (set<file_path>::const_iterator i = cs.dirs_added.begin();
282 i != cs.dirs_added.end(); ++i)
283 {
284 basic_io::stanza st;
285 st.push_file_pair(syms::add_dir, *i);
286 printer.print_stanza(st);
287 }
288
289 for (map<file_path, file_id>::const_iterator i = cs.files_added.begin();
290 i != cs.files_added.end(); ++i)
291 {
292 basic_io::stanza st;
293 st.push_file_pair(syms::add_file, i->first);
294 st.push_binary_pair(syms::content, i->second.inner());
295 printer.print_stanza(st);
296 }
297
298 for (map<file_path, pair<file_id, file_id> >::const_iterator i = cs.deltas_applied.begin();
299 i != cs.deltas_applied.end(); ++i)
300 {
301 basic_io::stanza st;
302 st.push_file_pair(syms::patch, i->first);
303 st.push_binary_pair(syms::from, i->second.first.inner());
304 st.push_binary_pair(syms::to, i->second.second.inner());
305 printer.print_stanza(st);
306 }
307
308 for (set<pair<file_path, attr_key> >::const_iterator i = cs.attrs_cleared.begin();
309 i != cs.attrs_cleared.end(); ++i)
310 {
311 basic_io::stanza st;
312 st.push_file_pair(syms::clear, i->first);
313 st.push_str_pair(syms::attr, i->second());
314 printer.print_stanza(st);
315 }
316
317 for (map<pair<file_path, attr_key>, attr_value>::const_iterator i = cs.attrs_set.begin();
318 i != cs.attrs_set.end(); ++i)
319 {
320 basic_io::stanza st;
321 st.push_file_pair(syms::set, i->first.first);
322 st.push_str_pair(syms::attr, i->first.second());
323 st.push_str_pair(syms::value, i->second());
324 printer.print_stanza(st);
325 }
326}
327
328
329static inline void
330parse_path(basic_io::parser & parser, file_path & sp)
331{
332 string s;
333 parser.str(s);
334 sp = file_path_internal(s);
335}
336
337void
338parse_cset(basic_io::parser & parser,
339 cset & cs)
340{
341 cs.clear();
342 string t1, t2;
343 MM(t1);
344 MM(t2);
345 file_path p1, p2;
346 MM(p1);
347 MM(p2);
348
349 file_path prev_path;
350 MM(prev_path);
351 pair<file_path, attr_key> prev_pair;
352 MM(prev_pair.first);
353 MM(prev_pair.second);
354
355 // we make use of the fact that a valid file_path is never empty
356 prev_path.clear();
357 while (parser.symp(syms::delete_node))
358 {
359 parser.sym();
360 parse_path(parser, p1);
361 I(prev_path.empty() || prev_path < p1);
362 prev_path = p1;
363 safe_insert(cs.nodes_deleted, p1);
364 }
365
366 prev_path.clear();
367 while (parser.symp(syms::rename_node))
368 {
369 parser.sym();
370 parse_path(parser, p1);
371 I(prev_path.empty() || prev_path < p1);
372 prev_path = p1;
373 parser.esym(syms::to);
374 parse_path(parser, p2);
375 safe_insert(cs.nodes_renamed, make_pair(p1, p2));
376 }
377
378 prev_path.clear();
379 while (parser.symp(syms::add_dir))
380 {
381 parser.sym();
382 parse_path(parser, p1);
383 I(prev_path.empty() || prev_path < p1);
384 prev_path = p1;
385 safe_insert(cs.dirs_added, p1);
386 }
387
388 prev_path.clear();
389 while (parser.symp(syms::add_file))
390 {
391 parser.sym();
392 parse_path(parser, p1);
393 I(prev_path.empty() || prev_path < p1);
394 prev_path = p1;
395 parser.esym(syms::content);
396 parser.hex(t1);
397 safe_insert(cs.files_added,
398 make_pair(p1, decode_hexenc_as<file_id>(t1, parser.tok.in.made_from)));
399 }
400
401 prev_path.clear();
402 while (parser.symp(syms::patch))
403 {
404 parser.sym();
405 parse_path(parser, p1);
406 I(prev_path.empty() || prev_path < p1);
407 prev_path = p1;
408 parser.esym(syms::from);
409 parser.hex(t1);
410 parser.esym(syms::to);
411 parser.hex(t2);
412 safe_insert(cs.deltas_applied,
413 make_pair(p1, make_pair(decode_hexenc_as<file_id>(t1, parser.tok.in.made_from),
414 decode_hexenc_as<file_id>(t2, parser.tok.in.made_from))));
415 }
416
417 prev_pair.first.clear();
418 while (parser.symp(syms::clear))
419 {
420 parser.sym();
421 parse_path(parser, p1);
422 parser.esym(syms::attr);
423 parser.str(t1);
424 pair<file_path, attr_key> new_pair(p1, attr_key(t1, parser.tok.in.made_from));
425 I(prev_pair.first.empty() || new_pair > prev_pair);
426 prev_pair = new_pair;
427 safe_insert(cs.attrs_cleared, new_pair);
428 }
429
430 prev_pair.first.clear();
431 while (parser.symp(syms::set))
432 {
433 parser.sym();
434 parse_path(parser, p1);
435 parser.esym(syms::attr);
436 parser.str(t1);
437 pair<file_path, attr_key> new_pair(p1, attr_key(t1, parser.tok.in.made_from));
438 I(prev_pair.first.empty() || new_pair > prev_pair);
439 prev_pair = new_pair;
440 parser.esym(syms::value);
441 parser.str(t2);
442 safe_insert(cs.attrs_set, make_pair(new_pair, attr_value(t2, parser.tok.in.made_from)));
443 }
444}
445
446void
447write_cset(cset const & cs, data & dat)
448{
449 basic_io::printer pr;
450 print_cset(pr, cs);
451 dat = data(pr.buf, origin::internal);
452}
453
454void
455read_cset(data const & dat, cset & cs)
456{
457 MM(dat);
458 MM(cs);
459 basic_io::input_source src(dat(), "cset");
460 basic_io::tokenizer tok(src);
461 basic_io::parser pars(tok);
462 parse_cset(pars, cs);
463 I(src.lookahead == EOF);
464}
465
466template <> void
467dump(cset const & cs, string & out)
468{
469 data dat;
470 write_cset(cs, dat);
471 out = dat();
472}
473
474
475
476
477// Local Variables:
478// mode: C++
479// fill-column: 76
480// c-file-style: "gnu"
481// indent-tabs-mode: nil
482// End:
483// 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