monotone

monotone Mtn Source Tree

Root/roster.hh

1#ifndef __ROSTER_HH__
2#define __ROSTER_HH__
3
4// Copyright (C) 2005 Nathaniel Smith <njs@pobox.com>
5//
6// This program is made available under the GNU GPL version 2.0 or
7// greater. See the accompanying file COPYING for details.
8//
9// This program is distributed WITHOUT ANY WARRANTY; without even the
10// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
11// PURPOSE.
12
13#include <map>
14
15#include <boost/shared_ptr.hpp>
16
17#include "cset.hh"
18#include "hybrid_map.hh"
19#include "numeric_vocab.hh"
20#include "paths.hh"
21#include "sanity.hh"
22#include "vocab.hh"
23
24struct node_id_source
25{
26 virtual node_id next() = 0;
27 virtual ~node_id_source() {}
28};
29
30///////////////////////////////////////////////////////////////////
31
32struct node;
33struct dir_node;
34struct file_node;
35typedef boost::shared_ptr<node> node_t;
36typedef boost::shared_ptr<file_node> file_t;
37typedef boost::shared_ptr<dir_node> dir_t;
38
39node_id const the_null_node = 0;
40
41inline bool
42null_node(node_id n)
43{
44 return n == the_null_node;
45}
46
47
48// (true, "val") or (false, "") are both valid attr values (for proper
49// merging, we have to widen the attr_value type to include a first-class
50// "undefined" value).
51typedef std::map<attr_key, std::pair<bool, attr_value> > full_attr_map_t;
52typedef std::map<path_component, node_t> dir_map;
53typedef hybrid_map<node_id, node_t> node_map;
54
55template <> void dump(full_attr_map_t const & val, std::string & out);
56
57
58struct node
59{
60 node();
61 node(node_id i);
62 node_id self;
63 node_id parent; // the_null_node iff this is a root dir
64 path_component name; // the_null_component iff this is a root dir
65 full_attr_map_t attrs;
66
67 // need a virtual function to make dynamic_cast work
68 virtual node_t clone() = 0;
69 virtual ~node() {}
70};
71
72
73struct dir_node
74 : public node
75{
76 dir_node();
77 dir_node(node_id i);
78 dir_map children;
79 bool has_child(path_component const & pc) const;
80 node_t get_child(path_component const & pc) const;
81 void attach_child(path_component const & pc, node_t child);
82 node_t detach_child(path_component const & pc);
83
84 // need a virtual function to make dynamic_cast work
85 virtual node_t clone();
86 virtual ~dir_node() {}
87};
88
89
90struct file_node
91 : public node
92{
93 file_node();
94 file_node(node_id i, file_id const & f);
95 file_id content;
96
97 // need a virtual function to make dynamic_cast work
98 virtual node_t clone();
99 virtual ~file_node() {}
100};
101
102inline bool
103is_dir_t(node_t n)
104{
105 dir_t d = boost::dynamic_pointer_cast<dir_node, node>(n);
106 return static_cast<bool>(d);
107}
108
109inline bool
110is_file_t(node_t n)
111{
112 file_t f = boost::dynamic_pointer_cast<file_node, node>(n);
113 return static_cast<bool>(f);
114}
115
116inline bool
117is_root_dir_t(node_t n)
118{
119 if (is_dir_t(n) && n->name.empty())
120 {
121 I(null_node(n->parent));
122 return true;
123 }
124
125 return false;
126}
127
128inline dir_t
129downcast_to_dir_t(node_t const n)
130{
131 dir_t d = boost::dynamic_pointer_cast<dir_node, node>(n);
132 I(static_cast<bool>(d));
133 return d;
134}
135
136
137inline file_t
138downcast_to_file_t(node_t const n)
139{
140 file_t f = boost::dynamic_pointer_cast<file_node, node>(n);
141 I(static_cast<bool>(f));
142 return f;
143}
144
145bool
146shallow_equal(node_t a, node_t b, bool shallow_compare_dir_children,
147 bool compare_file_contents = true);
148
149template <> void dump(node_t const & n, std::string & out);
150
151struct marking_t
152{
153 revision_id birth_revision;
154 std::set<revision_id> parent_name;
155 std::set<revision_id> file_content;
156 std::map<attr_key, std::set<revision_id> > attrs;
157 marking_t() {};
158 bool operator==(marking_t const & other) const
159 {
160 return birth_revision == other.birth_revision
161 && parent_name == other.parent_name
162 && file_content == other.file_content
163 && attrs == other.attrs;
164 }
165};
166
167typedef std::map<node_id, marking_t> marking_map;
168
169template <> void dump(std::set<revision_id> const & revids, std::string & out);
170template <> void dump(marking_t const & marking, std::string & out);
171template <> void dump(marking_map const & marking_map, std::string & out);
172
173namespace basic_io { struct printer; struct parser; }
174
175class roster_t
176{
177public:
178 roster_t() {}
179 roster_t(roster_t const & other);
180 roster_t & operator=(roster_t const & other);
181 bool has_root() const;
182 bool has_node(file_path const & sp) const;
183 bool has_node(node_id nid) const;
184 bool is_root(node_id nid) const;
185 node_t get_node(file_path const & sp) const;
186 node_t get_node(node_id nid) const;
187 void get_name(node_id nid, file_path & sp) const;
188 void replace_node_id(node_id from, node_id to);
189
190 // editable_tree operations
191 node_id detach_node(file_path const & src);
192 void drop_detached_node(node_id nid);
193 node_id create_dir_node(node_id_source & nis);
194 void create_dir_node(node_id nid);
195 node_id create_file_node(file_id const & content,
196 node_id_source & nis);
197 void create_file_node(file_id const & content,
198 node_id nid);
199 void insert_node(node_t n);
200 void attach_node(node_id nid, file_path const & dst);
201 void attach_node(node_id nid, node_id parent, path_component name);
202 void apply_delta(file_path const & pth,
203 file_id const & old_id,
204 file_id const & new_id);
205 void clear_attr(file_path const & pth,
206 attr_key const & name);
207 void set_attr(file_path const & pth,
208 attr_key const & name,
209 attr_value const & val);
210 void set_attr(file_path const & pth,
211 attr_key const & name,
212 std::pair<bool, attr_value> const & val);
213
214 // more direct, lower-level operations, for the use of roster_delta's
215 void detach_node(node_id nid);
216 void set_content(node_id nid,
217 file_id const & new_id);
218 void set_attr_unknown_to_dead_ok(node_id nid,
219 attr_key const & name,
220 std::pair<bool, attr_value> const & val);
221 void erase_attr(node_id nid,
222 attr_key const & name);
223
224 // misc.
225
226 bool get_attr(file_path const & pth,
227 attr_key const & key,
228 attr_value & val) const;
229
230 void extract_path_set(std::set<file_path> & paths) const;
231
232 node_map const & all_nodes() const
233 {
234 return nodes;
235 }
236
237 bool operator==(roster_t const & other) const;
238
239 friend bool equal_shapes(roster_t const & a, roster_t const & b);
240
241 void check_sane(bool temp_nodes_ok=false) const;
242
243 // verify that this roster is sane, and corresponds to the given
244 // marking map
245 void check_sane_against(marking_map const & marks, bool temp_nodes_ok=false) const;
246
247 void print_to(basic_io::printer & pr,
248 marking_map const & mm,
249 bool print_local_parts) const;
250
251 void parse_from(basic_io::parser & pa,
252 marking_map & mm);
253
254 dir_t const & root() const
255 {
256 return root_dir;
257 }
258
259private:
260 void do_deep_copy_from(roster_t const & other);
261 dir_t root_dir;
262 node_map nodes;
263 // This requires some explanation. There is a particular kind of
264 // nonsensical behavior which we wish to discourage -- when a node is
265 // detached from some location, and then re-attached at that same location
266 // (or similarly, if a new node is created, then immediately deleted -- this
267 // is like the previous case, if you think of "does not exist" as a
268 // location). In particular, we _must_ error out if a cset attempts to do
269 // this, because it indicates that the cset had something non-normalized,
270 // like "rename a a" in it, and that is illegal. There are two options for
271 // detecting this. The more natural approach, perhaps, is to keep a chunk
272 // of state around while performing any particular operation (like cset
273 // application) for which we wish to detect these kinds of redundant
274 // computations. The other option is to keep this state directly within the
275 // roster, at all times. In the first case, we explicitly turn on checking
276 // when we want it; the the latter, we must explicitly turn _off_ checking
277 // when we _don't_ want it. We choose the latter, because it is more
278 // conservative --- perhaps it will turn out that it is _too_ conservative
279 // and causes problems, in which case we should probably switch to the
280 // former.
281 //
282 // FIXME: This _is_ all a little nasty, because this can be a source of
283 // abstraction leak -- for instance, roster_merge's contract is that nodes
284 // involved in name-related conflicts will be detached in the roster it returns.
285 // Those nodes really should be allowed to be attached anywhere, or dropped,
286 // which is not actually expressible right now. Worse, whether or not they
287 // are in old_locations map is an implementation detail of roster_merge --
288 // it may temporarily attach and then detach the nodes it creates, but this
289 // is not deterministic or part of its interface. The main time this would
290 // be a _problem_ is if we add interactive resolution of tree rearrangement
291 // conflicts -- if someone resolves a rename conflict by saying that one
292 // side wins, or by deleting one of the conflicting nodes, and this all
293 // happens in memory, then it may trigger a spurious invariant failure here.
294 // If anyone ever decides to add this kind of functionality, then it would
295 // definitely make sense to move this checking into editable_tree. For now,
296 // though, no such functionality is planned, so we'll see what happens.
297 //
298 // The implementation itself uses the map old_locations. A node can be in
299 // the following states:
300 // -- attached, no entry in old_locations map
301 // -- detached, no entry in old_locations map
302 // -- create_dir_node, create_file_node put a node into this state
303 // -- a node in this state can be attached, anywhere, but may not be
304 // deleted.
305 // -- detached, an entry in old_locations map
306 // -- detach_node puts a node into this state
307 // -- a node in this state can be attached anywhere _except_ the
308 // (parent, basename) entry given in the map, or may be deleted.
309 std::map<node_id, std::pair<node_id, path_component> > old_locations;
310 template <typename T> friend void dump(T const & val, std::string & out);
311};
312
313struct temp_node_id_source
314 : public node_id_source
315{
316 temp_node_id_source();
317 virtual node_id next();
318 node_id curr;
319};
320
321template <> void dump(roster_t const & val, std::string & out);
322
323class app_state;
324class database;
325struct revision_t;
326
327// adaptor class to enable cset application on rosters.
328class editable_roster_base
329 : public editable_tree
330{
331public:
332 editable_roster_base(roster_t & r, node_id_source & nis);
333 virtual node_id detach_node(file_path const & src);
334 virtual void drop_detached_node(node_id nid);
335 virtual node_id create_dir_node();
336 virtual node_id create_file_node(file_id const & content);
337 virtual void attach_node(node_id nid, file_path const & dst);
338 virtual void apply_delta(file_path const & pth,
339 file_id const & old_id,
340 file_id const & new_id);
341 virtual void clear_attr(file_path const & pth,
342 attr_key const & name);
343 virtual void set_attr(file_path const & pth,
344 attr_key const & name,
345 attr_value const & val);
346 virtual void commit();
347protected:
348 roster_t & r;
349 node_id_source & nis;
350};
351
352
353void
354make_cset(roster_t const & from,
355 roster_t const & to,
356 cset & cs);
357
358bool
359equal_up_to_renumbering(roster_t const & a, marking_map const & a_markings,
360 roster_t const & b, marking_map const & b_markings);
361
362
363// various (circular?) dependencies prevent inclusion of restrictions.hh
364class node_restriction;
365
366void
367make_restricted_csets(roster_t const & from, roster_t const & to,
368 cset & included, cset & excluded,
369 node_restriction const & mask);
370
371void
372check_restricted_cset(roster_t const & roster, cset const & cs);
373
374void
375select_nodes_modified_by_cset(cset const & cs,
376 roster_t const & old_roster,
377 roster_t const & new_roster,
378 std::set<node_id> & nodes_modified);
379
380void
381get_content_paths(roster_t const & roster,
382 std::map<file_id, file_path> & paths);
383
384// These functions are for the use of things like 'update' or 'pluck', that
385// need to construct fake rosters and/or markings in-memory, to achieve
386// particular merge results.
387void
388mark_roster_with_no_parents(revision_id const & rid,
389 roster_t const & roster,
390 marking_map & markings);
391void
392mark_roster_with_one_parent(roster_t const & parent,
393 marking_map const & parent_markings,
394 revision_id const & child_rid,
395 roster_t const & child,
396 marking_map & child_markings);
397
398void
399mark_merge_roster(roster_t const & left_roster,
400 marking_map const & left_markings,
401 std::set<revision_id> const & left_uncommon_ancestors,
402 roster_t const & right_roster,
403 marking_map const & right_markings,
404 std::set<revision_id> const & right_uncommon_ancestors,
405 revision_id const & new_rid,
406 roster_t const & merge,
407 marking_map & new_markings);
408
409// This is for revisions that are being written to the db, only. It assigns
410// permanent node ids.
411void
412make_roster_for_revision(revision_t const & rev,
413 revision_id const & rid,
414 roster_t & result,
415 marking_map & marking,
416 app_state & app);
417
418// This is for revisions that are not necessarily going to be written to the
419// db; you can specify your own node_id_source.
420void
421make_roster_for_revision(revision_t const & rev,
422 revision_id const & rid,
423 roster_t & result,
424 marking_map & marking,
425 database & db,
426 node_id_source & nis);
427
428void
429read_roster_and_marking(roster_data const & dat,
430 roster_t & ros,
431 marking_map & mm);
432
433void
434write_roster_and_marking(roster_t const & ros,
435 marking_map const & mm,
436 roster_data & dat);
437
438void
439write_manifest_of_roster(roster_t const & ros,
440 manifest_data & dat);
441
442
443void calculate_ident(roster_t const & ros,
444 manifest_id & ident);
445
446namespace basic_io
447{
448 struct stanza;
449 struct parser;
450}
451
452// for roster_delta
453void push_marking(basic_io::stanza & st, bool is_file, marking_t const & mark);
454void parse_marking(basic_io::parser & pa, marking_t & marking);
455
456#ifdef BUILD_UNIT_TESTS
457
458struct testing_node_id_source
459 : public node_id_source
460{
461 testing_node_id_source();
462 virtual node_id next();
463 node_id curr;
464};
465
466#endif // BUILD_UNIT_TESTS
467
468// Local Variables:
469// mode: C++
470// fill-column: 76
471// c-file-style: "gnu"
472// indent-tabs-mode: nil
473// End:
474// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
475
476#endif
477

Archive Download this file

Branches

Tags

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