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

Archive Download this file

Branches

Tags

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