monotone

monotone Mtn Source Tree

Root/src/roster.hh

1// Copyright (C) 2005 Nathaniel Smith <njs@pobox.com>
2// 2008 Stephen Leake <stephen_leake@stephe-leake.org>
3//
4// This program is made available under the GNU GPL version 2.0 or
5// greater. See the accompanying file COPYING for details.
6//
7// This program is distributed WITHOUT ANY WARRANTY; without even the
8// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
9// PURPOSE.
10
11#ifndef __ROSTER_HH__
12#define __ROSTER_HH__
13
14#include "hybrid_map.hh"
15#include "paths.hh"
16#include "rev_types.hh"
17#include "cset.hh" // need full definition of editable_tree
18
19#include <stack>
20
21struct node_id_source
22{
23 virtual node_id next() = 0;
24 virtual ~node_id_source() {}
25};
26
27///////////////////////////////////////////////////////////////////
28
29node_id const the_null_node = 0;
30
31inline bool
32null_node(node_id n)
33{
34 return n == the_null_node;
35}
36
37template <> void dump(attr_map_t const & val, std::string & out);
38
39enum roster_node_type { node_type_none, node_type_file, node_type_dir };
40
41struct dfs_iter
42{
43 const_dir_t root;
44 std::string curr_path;
45 bool return_root;
46 bool track_path;
47 std::stack< std::pair<const_dir_t, dir_map::const_iterator> > stk;
48
49 dfs_iter(const_dir_t r, bool t);
50 bool finished() const;
51 std::string const & path() const;
52 const_node_t operator*() const;
53 void operator++();
54
55private:
56 void advance_top();
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 attr_map_t attrs;
67 roster_node_type type;
68 u32 cow_version; // see roster_t::cow_version below
69
70 // need a virtual function to make dynamic_cast work
71 virtual node_t clone() = 0;
72 virtual ~node() {}
73};
74
75
76struct dir_node
77 : public node
78{
79 dir_node();
80 dir_node(node_id i);
81 dir_map children;
82 bool has_child(path_component const & pc) const;
83 node_t get_child(path_component const & pc) const;
84 void attach_child(path_component const & pc, node_t child);
85 node_t detach_child(path_component const & pc);
86
87 // need a virtual function to make dynamic_cast work
88 virtual node_t clone();
89 virtual ~dir_node() {}
90};
91
92
93struct file_node
94 : public node
95{
96 file_node();
97 file_node(node_id i, file_id const & f);
98 file_id content;
99
100 // need a virtual function to make dynamic_cast work
101 virtual node_t clone();
102 virtual ~file_node() {}
103};
104
105inline bool
106is_dir_t(const_node_t n)
107{
108 return n->type == node_type_dir;
109}
110
111inline bool
112is_file_t(const_node_t n)
113{
114 return n->type == node_type_file;
115}
116
117inline bool
118is_root_dir_t(node_t n)
119{
120 if (is_dir_t(n) && n->name.empty())
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
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
145inline const_dir_t
146downcast_to_dir_t(const_node_t const & n)
147{
148 const_dir_t d = boost::dynamic_pointer_cast<dir_node const, node const>(n);
149 I(static_cast<bool>(d));
150 return d;
151}
152
153inline const_file_t
154downcast_to_file_t(const_node_t const & n)
155{
156 const_file_t f = boost::dynamic_pointer_cast<file_node const, node const>(n);
157 I(static_cast<bool>(f));
158 return f;
159}
160
161bool
162shallow_equal(const_node_t a, const_node_t b,
163 bool shallow_compare_dir_children,
164 bool compare_file_contents = true);
165
166template <> void dump(node_t const & n, std::string & out);
167
168struct marking
169{
170 u32 cow_version;
171 revision_id birth_revision;
172 std::set<revision_id> parent_name;
173 std::set<revision_id> file_content;
174 std::map<attr_key, std::set<revision_id> > attrs;
175 marking();
176 marking(marking const & other);
177 marking const & operator=(marking const & other);
178 bool operator==(marking const & other) const
179 {
180 return birth_revision == other.birth_revision
181 && parent_name == other.parent_name
182 && file_content == other.file_content
183 && attrs == other.attrs;
184 }
185};
186
187class marking_map
188{
189 mutable u32 cow_version;
190 typedef cow_trie<node_id, marking_t, 8> map_type;
191 map_type _store;
192public:
193 typedef map_type::key_type key_type;
194 typedef map_type::value_type value_type;
195
196 marking_map();
197 marking_map(marking_map const & other);
198 marking_map const & operator=(marking_map const & other);
199 const_marking_t get_marking(node_id nid) const;
200 marking_t const & get_marking_for_update(node_id nid);
201 void put_marking(node_id nid, marking_t const & m);
202 void put_marking(node_id nid, const_marking_t const & m);
203
204 // for roster_delta
205 void put_or_replace_marking(node_id nid, const_marking_t const & m);
206
207 typedef map_type::const_iterator const_iterator;
208 const_iterator begin() const;
209 const_iterator end() const;
210 size_t size() const;
211 bool contains(node_id nid) const;
212 void clear();
213 void remove_marking(node_id nid);
214};
215
216template <> void dump(std::set<revision_id> const & revids, std::string & out);
217template <> void dump(marking_t const & marking, std::string & out);
218template <> void dump(marking_map const & marking_map, std::string & out);
219
220class roster_t
221{
222public:
223 roster_t();
224 roster_t(roster_t const & other);
225 roster_t & operator=(roster_t const & other);
226 bool has_root() const;
227 bool has_node(file_path const & sp) const;
228 bool has_node(node_id nid) const;
229 bool is_root(node_id nid) const;
230 bool is_attached(node_id nid) const;
231private:
232 node_t get_node_internal(file_path const & p) const;
233public:
234 const_node_t get_node(file_path const & sp) const;
235 const_node_t get_node(node_id nid) const;
236 node_t get_node_for_update(file_path const & sp);
237 node_t get_node_for_update(node_id nid);
238 void get_name(node_id nid, file_path & sp) const;
239 void unshare(node_t & n, bool is_in_node_map = true);
240 void replace_node_id(node_id from, node_id to);
241
242 // editable_tree operations
243 node_id detach_node(file_path const & src);
244 void drop_detached_node(node_id nid);
245 node_id create_dir_node(node_id_source & nis);
246 void create_dir_node(node_id nid);
247 node_id create_file_node(file_id const & content,
248 node_id_source & nis);
249 void create_file_node(file_id const & content,
250 node_id nid);
251 void attach_node(node_id nid, file_path const & dst);
252 void attach_node(node_id nid, node_id parent, path_component name);
253 void apply_delta(file_path const & pth,
254 file_id const & old_id,
255 file_id const & new_id);
256 void clear_attr(file_path const & path,
257 attr_key const & key);
258 void set_attr(file_path const & path,
259 attr_key const & key,
260 attr_value const & val);
261 void set_attr(file_path const & path,
262 attr_key const & key,
263 std::pair<bool, attr_value> const & val);
264
265 // more direct, lower-level operations, for the use of roster_delta's
266 void detach_node(node_id nid);
267 void set_content(node_id nid,
268 file_id const & new_id);
269 void set_attr_unknown_to_dead_ok(node_id nid,
270 attr_key const & name,
271 std::pair<bool, attr_value> const & val);
272 void erase_attr(node_id nid,
273 attr_key const & name);
274
275 // misc.
276
277 bool get_attr(file_path const & pth,
278 attr_key const & key,
279 attr_value & val) const;
280
281 void get_file_details(node_id nid,
282 file_id & fid,
283 file_path & pth) const;
284
285 void extract_path_set(std::set<file_path> & paths) const;
286
287 node_map const & all_nodes() const
288 {
289 return nodes;
290 }
291
292 bool operator==(roster_t const & other) const;
293
294 friend bool equal_shapes(roster_t const & a, roster_t const & b);
295
296 void check_sane(bool temp_nodes_ok=false) const;
297
298 // verify that this roster is sane, and corresponds to the given
299 // marking map
300 void check_sane_against(marking_map const & marks, bool temp_nodes_ok=false) const;
301
302 void print_to(data & dat,
303 marking_map const & mm,
304 bool print_local_parts) const;
305
306 void parse_from(basic_io::parser & pa,
307 marking_map & mm);
308
309 dir_t const & root() const
310 {
311 return root_dir;
312 }
313
314private:
315 //void do_deep_copy_from(roster_t const & other);
316 dir_t root_dir;
317 node_map nodes;
318 // This is set to a unique value when a roster is created or
319 // copied to/from another roster. If a node has the same version
320 // as the roster it's in, then it is not shared. Nodes with version
321 // zero are also not shared, since that means they haven't been added
322 // to a roster yet.
323 // A simple refcount isn't good enough, because everything that points
324 // to a node in question could also be shared.
325 mutable u32 cow_version;
326 // This requires some explanation. There is a particular kind of
327 // nonsensical behavior which we wish to discourage -- when a node is
328 // detached from some location, and then re-attached at that same location
329 // (or similarly, if a new node is created, then immediately deleted -- this
330 // is like the previous case, if you think of "does not exist" as a
331 // location). In particular, we _must_ error out if a cset attempts to do
332 // this, because it indicates that the cset had something non-normalized,
333 // like "rename a a" in it, and that is illegal. There are two options for
334 // detecting this. The more natural approach, perhaps, is to keep a chunk
335 // of state around while performing any particular operation (like cset
336 // application) for which we wish to detect these kinds of redundant
337 // computations. The other option is to keep this state directly within the
338 // roster, at all times. In the first case, we explicitly turn on checking
339 // when we want it; the the latter, we must explicitly turn _off_ checking
340 // when we _don't_ want it. We choose the latter, because it is more
341 // conservative --- perhaps it will turn out that it is _too_ conservative
342 // and causes problems, in which case we should probably switch to the
343 // former.
344 //
345 // The implementation itself uses the map old_locations. A node can be in
346 // the following states:
347 // -- attached, no entry in old_locations map
348 // -- detached, no entry in old_locations map
349 // -- create_dir_node, create_file_node put a node into this state
350 // -- a node in this state can be attached, anywhere, but may not be
351 // deleted.
352 // -- detached, an entry in old_locations map
353 // -- detach_node puts a node into this state
354 // -- a node in this state can be attached anywhere _except_ the
355 // (parent, basename) entry given in the map, or may be deleted.
356 std::map<node_id, std::pair<node_id, path_component> > old_locations;
357 template <typename T> friend void dump(T const & val, std::string & out);
358};
359
360struct temp_node_id_source
361 : public node_id_source
362{
363 temp_node_id_source();
364 virtual node_id next();
365 node_id curr;
366};
367
368template <> void dump(roster_t const & val, std::string & out);
369
370// adaptor class to enable cset application on rosters.
371class editable_roster_base
372 : public editable_tree
373{
374public:
375 editable_roster_base(roster_t & r, node_id_source & nis);
376 virtual node_id detach_node(file_path const & src);
377 virtual void drop_detached_node(node_id nid);
378 virtual node_id create_dir_node();
379 virtual node_id create_file_node(file_id const & content);
380 virtual void attach_node(node_id nid, file_path const & dst);
381 virtual void apply_delta(file_path const & pth,
382 file_id const & old_id,
383 file_id const & new_id);
384 virtual void clear_attr(file_path const & path,
385 attr_key const & key);
386 virtual void set_attr(file_path const & path,
387 attr_key const & key,
388 attr_value const & val);
389 virtual void commit();
390protected:
391 roster_t & r;
392 node_id_source & nis;
393};
394
395
396void
397make_cset(roster_t const & from,
398 roster_t const & to,
399 cset & cs);
400
401bool
402equal_up_to_renumbering(roster_t const & a, marking_map const & a_markings,
403 roster_t const & b, marking_map const & b_markings);
404
405
406// various (circular?) dependencies prevent inclusion of restrictions.hh
407class node_restriction;
408
409void
410make_restricted_roster(roster_t const & from, roster_t const & to,
411 roster_t & restricted,
412 node_restriction const & mask);
413
414void
415select_nodes_modified_by_cset(cset const & cs,
416 roster_t const & old_roster,
417 roster_t const & new_roster,
418 std::set<node_id> & nodes_modified);
419
420void
421get_content_paths(roster_t const & roster,
422 std::map<file_id, file_path> & paths);
423
424// These functions are for the use of things like 'update' or 'pluck', that
425// need to construct fake rosters and/or markings in-memory, to achieve
426// particular merge results.
427void
428mark_roster_with_no_parents(revision_id const & rid,
429 roster_t const & roster,
430 marking_map & markings);
431void
432mark_roster_with_one_parent(roster_t const & parent,
433 marking_map const & parent_markings,
434 revision_id const & child_rid,
435 roster_t const & child,
436 marking_map & child_markings);
437
438void
439mark_merge_roster(roster_t const & left_roster,
440 marking_map const & left_markings,
441 std::set<revision_id> const & left_uncommon_ancestors,
442 roster_t const & right_roster,
443 marking_map const & right_markings,
444 std::set<revision_id> const & right_uncommon_ancestors,
445 revision_id const & new_rid,
446 roster_t const & merge,
447 marking_map & new_markings);
448
449// These functions are an internal interface between ancestry.cc and
450// roster.cc; unless you know exactly what you're doing you probably want
451// something else.
452
453void
454make_roster_for_merge(revision_id const & left_rid,
455 roster_t const & left_roster,
456 marking_map const & left_markings,
457 cset const & left_cs,
458 std::set<revision_id> const & left_uncommon_ancestors,
459
460 revision_id const & right_rid,
461 roster_t const & right_roster,
462 marking_map const & right_markings,
463 cset const & right_cs,
464 std::set<revision_id> const & right_uncommon_ancestors,
465
466 revision_id const & new_rid,
467 roster_t & new_roster,
468 marking_map & new_markings,
469 node_id_source & nis);
470
471void
472make_roster_for_nonmerge(cset const & cs,
473 revision_id const & new_rid,
474 roster_t & new_roster, marking_map & new_markings,
475 node_id_source & nis);
476
477
478// This is for revisions that are being written to the db, only. It assigns
479// permanent node ids.
480void
481make_roster_for_revision(database & db,
482 revision_t const & rev,
483 revision_id const & rid,
484 roster_t & result,
485 marking_map & marking);
486
487// This is for revisions that are not necessarily going to be written to the
488// db; you can specify your own node_id_source.
489void
490make_roster_for_revision(database & db,
491 node_id_source & nis,
492 revision_t const & rev,
493 revision_id const & rid,
494 roster_t & result,
495 marking_map & marking);
496
497void
498read_roster_and_marking(roster_data const & dat,
499 roster_t & ros,
500 marking_map & mm);
501
502void
503write_roster_and_marking(roster_t const & ros,
504 marking_map const & mm,
505 roster_data & dat);
506
507void
508write_manifest_of_roster(roster_t const & ros,
509 manifest_data & dat,
510 bool do_sanity_check = true);
511
512
513void calculate_ident(roster_t const & ros,
514 manifest_id & ident,
515 bool do_sanity_check = true);
516
517// for roster_delta
518
519void append_with_escaped_quotes(std::string & collection,
520 std::string const & item);
521void push_marking(std::string & contents,
522 bool is_file, const_marking_t const & mark,
523 int symbol_length);
524void parse_marking(basic_io::parser & pa, marking_t & marking);
525
526// Parent maps are used in a number of places to keep track of all the
527// parent rosters of a given revision.
528
529inline revision_id const & parent_id(parent_entry const & p)
530{
531 return p.first;
532}
533
534inline revision_id const & parent_id(parent_map::const_iterator i)
535{
536 return i->first;
537}
538
539inline cached_roster const &
540parent_cached_roster(parent_entry const & p)
541{
542 return p.second;
543}
544
545inline cached_roster const &
546parent_cached_roster(parent_map::const_iterator i)
547{
548 return i->second;
549}
550
551inline roster_t const & parent_roster(parent_entry const & p)
552{
553 return *(p.second.first);
554}
555
556inline roster_t const & parent_roster(parent_map::const_iterator i)
557{
558 return *(i->second.first);
559}
560
561inline marking_map const & parent_marking(parent_entry const & p)
562{
563 return *(p.second.second);
564}
565
566inline marking_map const & parent_marking(parent_map::const_iterator i)
567{
568 return *(i->second.second);
569}
570
571#endif
572
573// Local Variables:
574// mode: C++
575// fill-column: 76
576// c-file-style: "gnu"
577// indent-tabs-mode: nil
578// End:
579// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

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