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

Archive Download this file

Branches

Tags

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