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

Archive Download this file

Branches

Tags

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