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

Archive Download this file

Branches

Tags

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