# # add_file "roster2.cc" # # add_file "roster2.hh" # # patch "roster.cc" # from [d690209507d81f4b27c69707b6be27549e74fec7] # to [f633208bbd0c1cb8cb7d3fb5b9b1243c1b4335ce] # # patch "roster.hh" # from [3d92b1db3b6656f771f61023ceb3ab690da6594e] # to [f2f0e70e50cea21bba4953d06b025ea9a93b0260] # # patch "roster2.cc" # from [] # to [ecee7d65972ac00a227890f8c2bfa90f6bc19eed] # # patch "roster2.hh" # from [] # to [3f708bc76899c06c0c54580d2624b7b7aa70bc2b] # ======================================================================== --- roster.cc d690209507d81f4b27c69707b6be27549e74fec7 +++ roster.cc f633208bbd0c1cb8cb7d3fb5b9b1243c1b4335ce @@ -27,11 +27,9 @@ // logic, wrt handling of null paths? element_soul -dir_tree::lookup(file_path const & fp) +dir_tree::lookup(element_soul parent, path_component child) { - split_path sp; - fp.split(sp); - return lookup(sp); + return get_existing_value(get_existing_value(children, parent), child); } element_soul dir_tree::lookup(split_path const & sp) @@ -39,17 +37,17 @@ element_soul es = roster.tree.root_dir; I(!null_soul(es)); for (split_path::const_iterator i = sp.begin(); i != sp.end(); ++i) - es = get_existing_value(get_existing_value(children, es), *i); + es = lookup(es, *i); return es; } - -bool is_root_dir(element_t const & element) +element_soul +dir_tree::lookup(file_path const & fp) { - return null_soul(element.parent); + split_path sp; + fp.split(sp); + return lookup(sp); } - - void get_name(roster_t const & roster, element_soul es, file_path & fp) { @@ -82,6 +80,11 @@ } } +bool is_root_dir(element_t const & element) +{ + return null_soul(element.parent); +} + dir_tree::dir_tree(element_map const & elements) { // first pass: find all directories and the unique root directory @@ -398,3 +401,190 @@ } } } + + + +struct parallel_roster_walker +{ + virtual void visit_left(roster_t & left, element_soul left_soul) = 0; + virtual void visit_right(roster_t & right, element_soul right_soul) = 0; + virtual void visit_both(roster_t & left, element_soul left_soul, + roster_t & right, element_soul right_soul); +}; + +void +parallel_walk_rosters_recurse_left(roster_t & left, element_soul & start, + parallel_roster_walker & walker) +{ + walker.visit_left(left, start); + std::map::const_iterator i = left.tree.children.find(start); + if (i != left.tree.children.end()) + for (dir_map::const_iterator j = i->second.begin(); j != i->second.end(); ++j) + parallel_walk_rosters_recurse_left(left, j->second, walker); +} + +void +parallel_walk_rosters_recurse_right(roster_t & right, element_soul start, + parallel_roster_walker & walker) +{ + walker.visit_right(right, start); + std::map::const_iterator i = right.tree.children.find(start); + if (i != right.tree.children.end()) + for (dir_map::const_iterator j = i->second.begin(); j != i->second.end(); ++j) + parallel_walk_rosters_recurse_right(right, j->second, walker); +} + +void +parallel_walk_rosters_recurse_both(roster_t & left, element_soul start_left, + roster_t & right, element_soul start_right, + parallel_roster_walker & walker) +{ + walker.visit_both(left, start_left, right, start_right); + std::map::const_iterator + li = left.tree.children.find(start_left); + std::map::const_iterator + ri = right.tree.children.find(start_left); + if (li == left.tree.children.end()) + { + I(ri == right.tree.children.end()); + return; + } + else + { + I(ri != right.tree.children.end()); + dir_map & ldir = li->second; + dir_map & rdir = ri->second; + dir_map::iterator lc = ldir.begin(); + dir_map::iterator rc = rdir.begin(); + while (lc != ldir.end() || rc != rdir.end()) + { + if (lc == ldir.end() || rc->first < lc->first) + { + parallel_walk_rosters_recurse_right(right, rc->second, walker); + ++rc; + } + else if (rc == rdir.end() || lc->first < rc->first) + { + parallel_walk_rosters_recurse_left(left, lc->second, walker); + ++lc; + } + else + { + I(lc->first == rc->first); + parallel_walk_rosters_recurse_both(left, lc->second, + right, rc->second, + walker); + ++lc; + ++rc; + } + } + } +} + +// FIXME: either make sure this is only passed non-loopy rosters, or add depth +// checking to this recursion +void +parallel_walk_rosters(roster_t & left, roster_t & right, + parallel_roster_walker & walker) +{ + parallel_walk_rosters_recurse_both(left, left.tree.root_dir, + right, right.tree.root_dir, + walker); +} + + +struct merge_id_fixer : parallel_roster_walker +{ + revision_id const & left_parent_id; + revision_id const & right_parent_id; + revision_id const & my_id; + std::set const & left_ancestors; + std::set const & right_ancestors; + marking_t & marking; + app_state & app; + merge_id_fixer(revision_id const & li, revision_id const & ri, + revision_id const & my_id, + std::set const & la, + std::set const & ra, + marking_t & marking, app_state & app) + : left_parent_id(li), right_parent_id(ri), my_id(my_id), left_ancestors(la), + right_ancestors(ra), marking(marking), app(app) + {} + virtual void visit_left(roster_t & left, element_soul left_soul); + virtual void visit_right(roster_t & right, element_soul right_soul); + virtual void visit_both(roster_t & left, element_soul left_soul, + roster_t & right, element_soul right_soul); +} + +void +merge_id_fixer::visit_left(roster_t & left, element_soul left_soul) +{ + I(false); +} +void +merge_id_fixer::visit_right(roster_t & right, element_soul right_soul) +{ + I(false); +} + +void +merge_id_fixer::visit_both(roster_t & left, element_soul left_soul, + roster_t & right, element_soul right_soul) +{ + element_t & left_element = get_existing_value(left.elements, left_soul); + element_t & right_elementt = get_existing_value(right.elements, right_soul); + I(left_element == right_element); + if (temp_soul(left_soul) && temp_soul(right_soul)) + { + // brand new element + element_soul new_soul = app.db.next_soul(); + left.resoul(left_soul, new_soul); + right.resoul(right_soul, new_soul); + mark_item mi; + mi.name_marks.insert(my_id); + mi.content + marking.insert(); + } + +} + +// the last step in generating a merge roster +static void +unify_rosters(roster_t & target, element_soul ts, + roster const & other, element_soul os, + revision_id const & new_rev, + app_state & app) +{ + element_t & telement = get_existing_value(target.elements, ts); + element_t & oelement = get_existing_value(other.elements, os); + if (temp_soul(ts) && temp_soul(os)) + { + element_soul new_soul = app.db.next_soul(); + target.resoul(ts, new_soul); + ts = new_soul; + telement.birth_revision = new_rev; + } + else if (temp_soul(ts) && !temp_soul(os)) + { + // not a new file -- picked it up from other + target.resoul(ts, os); + ts = os; + telement.birth_revision = oelement.birth_revision; + } + else if (temp_soul(ts) && !temp_soul(os)) + { + // not a new file -- we already have the right stuff + } + else if (!temp_soul(ts) && !temp_soul(os)) + { + // file existed in both parents -- we already have the right stuff + } + else + I(false); + I(telement == oelement); + if (telement.type == etype_dir) + { + dir_map & tdir = get_existing_value(target.tree.children, ts); + dir_map & odir = get_existing_value(other.tree.children, os); + +} ======================================================================== --- roster.hh 3d92b1db3b6656f771f61023ceb3ab690da6594e +++ roster.hh f2f0e70e50cea21bba4953d06b025ea9a93b0260 @@ -81,10 +81,11 @@ dir_tree(element_map const & elements) {}; element_soul lookup(file_path const & fp); element_soul lookup(split_path const & sp); + element_soul lookup(element_soul parent, path_component child); // returns the soul of the removed element - element_soul remove(split_path const & sp); - void add(split_path const & sp, element_soul es, etype type); - void add(element_soul parent, element_soul es, etype type); + element_soul detach(split_path const & sp); + void attach(split_path const & sp, element_soul es, etype type); + void attach(element_soul parent, element_soul es, etype type); private: std::map children; element_soul root_dir; ======================================================================== --- roster2.cc +++ roster2.cc ecee7d65972ac00a227890f8c2bfa90f6bc19eed @@ -0,0 +1,476 @@ +// copyright (C) 2005 nathaniel smith +// all rights reserved. +// licensed to the public under the terms of the GNU GPL (>= 2) +// see the file COPYING for details + +#include "roster2.hh" + +// FIXME: move this to a header somewhere +template +safe_erase(T & container, K const & key) +{ + I(container.erase(key)); +} +template +safe_insert(T & container, V const & val) +{ + I(container.insert(val).second); +} + +// FIXME: we assume split and join paths always start with a null component + +esoul +roster_t::lookup(file_path const & fp) const +{ + split_path sp; + fp.split(sp); + return lookup(sp); +} + +esoul +roster_t::lookup(split_path const & sp) const +{ + esoul es = the_null_soul; + for (split_path::const_iterator i = sp.begin(); i != sp.end(); ++i) + es = lookup(es, *i); + return es; +} + +esoul +roster_t::lookup(esoul parent, path_component child) const +{ + if (null_soul(parent)) + { + I(null_name(child)); + I(!null_soul(root_dir)); + return root_dir; + } + dir_map & dir = children(parent); + dir_map::const_iterator i = dir.find(child); + I(i != dir.end()); + return i->second; +} + +esoul +roster_t::get_name(esoul es, file_path & fp) +{ + split_path sp; + get_name(es, sp); + fp = file_path(sp); +} + +esoul +roster_t::get_name(esoul es, split_path & sp) +{ + sp.clear(); + while (!null_soul(es)) + { + element_t & e = element(es); + sp.push_back(es.name); + es = es.parent; + } + std::reverse(sp.begin(), sp.end()); +} + +dir_map & +roster_t::children(esoul es) +{ + std::map::iterator i = children_map.find(es); + I(i != children_map.end()); + return i->second; +} + +element_t & +roster_t::element(esoul es) +{ + std::map::iterator i = elements.find(es); + I(i != elements.end()); + return i->second; +} + +void +roster_t::resoul(esoul from, esoul to, element_t & element) +{ + // first move the element_t + { + std::map::iterator i = elements.find(from); + I(i != elements.end()); + safe_insert(elements, std::make_pair(to, i->second)); + elements.erase(i); + } + // then munge the containing directory + if (root_dir == from) + { + root_dir = to; + I(element.type == etype_dir); + } + else + { + dir_map & dir = children(element.parent); + dir_map::iterator i = dir.find(element.name); + I(i != dir.end()); + I(i->second == from); + i->second = to; + } + // then, for directories, munge the tree representation and the child layout + if (element.type == etype_dir) + { + std::map::iterator i = children_map.find(from); + I(i != children_map.end()); + for (dir_map::iterator j = i->second.begin(); j != i->second.end(); ++j) + { + element_t & child_e = element(j->second); + I(child_e.parent == from); + child_e.parent = to; + } + safe_insert(children_map, std::make_pair(to, i->second)); + children_map.erase(i); + } +} + +static inline void +dirname_basename(split_path const & sp, + split_path & dirname, path_component & basename) +{ + I(!sp.empty()); + split_path::const_iterator penultimate = sp.end(); + --penultimate; + dirname = split_path(sp.begin(), penultimate); + basename = *penultimate; +} + +// FIXME: we assume split and join paths always start with a null component +// split_path [] means the_null_component (which is the parent of the root dir) +// [""] means the root dir +// ["", "foo"] means root dir's sub-element "foo" +// etc. + +void +roster_t::attach(esoul es, split_path const & sp, element_t & e) +{ + split_path dirname; + path_component basename; + dirname_basename(sp, dirname, basename); + esoul parent = lookup(dirname); + e.parent = parent; + e.name = basename; + if (null_soul(parent)) + { + // this is the root dir + root_dir = es; + I(e.type == etype_dir); + } + else + safe_insert(children(parent), std::make_pair(basename, es)); + if (e.type == etype_dir) + safe_insert(children_map, std::make_pair(es, dir_map())); +} + +void +roster_t::detach(esoul es, etype type) +{ + // for now, the root dir can be created, but cannot be removed + I(es != root_dir); + element_t & e = element(es); + I(e.type == type); + esoul parent = e.parent; + safe_erase(children(parent), es); + e.parent = the_null_soul; + e.name = the_null_component; + if (e.type == etype_dir) + { + std::map::iterator i = children_map.find(es); + I(i != children_map.end()); + I(i->second.empty()); + children_map.erase(i); + } +} + +void +roster_t::remove(esoul es, etype type) +{ + detach(es, type); + safe_erase(elements, es); +} + +void +roster_t::add(esoul es, split_path const & sp, element_t const & element) +{ + safe_insert(elements, std::make_pair(es, element)); + attach(es, sp, element(es)); +} + +namespace +{ + struct change_task + { + virtual void go(roster_t & r, split_path const & target); + }; + struct delete_element : public change_task + { + etype type; + delete_element(etype type) : type(type) {} + virtual void go(roster_t & r, split_path const & target) + { + r.remove(r.lookup(target), type); + } + }; + struct rename_detach : public change_task + { + etype type; + } +} + +// FIXME: make apply_changeset apply to some sort of abstract mutable tree +// interface, rather than rosters -- that way we can use this same code for +// applying changes to the working copy. +// (or does this make sense?) +// (such an interface would be really handy for implementing rollback and undo +// on working copy operations...) + +namespace +{ + typedef enum + { remove_task, add_task, rename_start_task, rename_end_task } + task_type; + struct ctask + { + task_type task; + etype type; + file_path const & rename_target; + esoul rename_source; + ctask(task_type task, etype type) : task(task), type(type) + { I(task == remove_task || task == add_task); } + ctask(task_type task, etype type, file_path const & rename_target) + : task(task), type(type), rename_target(rename_target) + { I(task == rename_start_task); } + ctask(task_type task, etype type, esoul rename_source) + : task(task), type(type), rename_source(rename_source) + { I(task == rename_end_task); } + } + + inline void sched(std::vector > vec, + file_path const & fp, ctask const & ct) + { + split_path sp; + fp.split(sp); + vec.push_back(std::make_pair(sp, ct)); + } + + struct bu_comparator + { + bool operator()(std::pair const & a, + std::pair const & b) + { + return a.first.size() > b.first.size(); + } + }; + struct td_comparator + { + bool operator()(std::pair const & a, + std::pair const & b) + { + return a.first.size() < b.first.size(); + } + }; + +} + +void +roster_t::apply_changeset(changeset const & cs, + soul_source & ss, revision_id const & new_id, + std::set & new_souls, + std::set & touched_souls) +{ + typedef std::vector > schedvec; + schedvec bottom_up_tasks, top_down_tasks; + bottom_up_tasks.reserve(re.deleted_files.size() + + re.deleted_dirs.size() + + re.renamed_files.size() + + re.renamed_dirs.size()); + top_down_tasks.reserve(re.added_files.size() + + re.added_dirs.size() + + re.renamed_files.size() + + re.renamed_dirs.size()); + // first, we apply deletes and the first half of renames, in bottom-up order + changeset::path_rearrangement const & re = cs.rearrangement; + for (std::set::const_iterator i = re.deleted_files.begin(); + i != re.deleted_files.end(); ++i) + sched(bottom_up_tasks, *i, ctask(remove_task, etype_file)); + for (std::set::const_iterator i = re.deleted_dirs.begin(); + i != re.deleted_dirs.end(); ++i) + sched(bottom_up_tasks, *i, ctask(remove_task, etype_dir)); + for (std::map::const_iterator i = re.renamed_files.begin(); + i != re.renamed_files.end(); ++i) + sched(bottom_up_tasks, i->first, + ctask(rename_start_task, etype_file, i->second)); + for (std::map::const_iterator i = re.renamed_dirs.begin(); + i != re.renamed_dirs.end(); ++i) + sched(bottom_up_tasks, i->first, + ctask(rename_start_task, etype_dir, i->second)); + + std::sort(bottom_up_tasks.begin(), bottom_up_tasks.end(), bu_comparator()); + + for (schedvec::const_iterator i = bottom_up_tasks.begin(); + i != bottom_up_tasks.end(); ++i) + { + split_path const & sp = i->first; + ctask const & ct = i->second; + switch (ct.task) + { + case remove_task: + remove(lookup(sp), ct.type); + break; + case rename_start_task: + esoul es = lookup(sp); + detach(es, ct.type); + sched(top_down_tasks, ct.rename_target, + ctask(rename_end_task, ct.type, es)); + touched_souls.insert(es); + break; + case add_task: + case rename_end_task: + I(false); + } + } + // next, we apply adds and the second half of renames, in top-down order + // already scheduled renames, still need to schedule adds + for (std::set::const_iterator i = re.added_files.begin(); + i != re.added_files.end(); ++i) + sched(top_down_tasks, *i, ctask(add_task, etype_file)); + for (std::set::const_iterator i = re.added_dirs.begin(); + i != re.added_dirs.end(); ++i) + sched(top_down_tasks, *i, ctask(add_task, etype_dir)); + + std::sort(top_down_tasks.begin(), top_down_tasks.end(), td_comparator()); + + for (schedvec::const_iterator i = bottom_up_tasks.begin(); + i != bottom_up_tasks.end(); ++i) + { + split_path const & sp = i->first; + ctask const & ct = i->second; + switch (ct.task) + { + case add_task: + element_t element; + element.birth_revision = new_id; + esoul new_soul = ss.next(); + add(new_soul, sp, element); + new_souls.insert(new_soul); + break; + case rename_end_task: + attach(ct.rename_source, sp); + break; + case remove_task: + case rename_start_task: + I(false); + } + } + // finally, we apply content and attr changes + for (delta_map::const_iterator i = cs.deltas.begin(); i != cs.deltas.end(); ++i) + { + esoul es = lookup(delta_entry_path(i)); + element_t & e = element(es); + I(e.type == etype_file); + I(e.content == delta_entry_src(i)); + I(delta_entry_src(i) != delta_entry_dst(i)); + e.content = delta_entry_dst(i); + touched_souls.insert(es); + } + smap > modified; + for (attr_set_map::const_iterator i = cs.attr_sets.begin(); + i != cs.attr_sets.end(); ++i) + { + esoul es = lookup(attr_set_entry_path(i)); + element_t & e = element(es); + attr_map::const_iterator j = e.attrs.find(attr_set_entry_key(i)); + I(j == e.attrs.end() || j->second != attr_set_entry_value(i)); + e.attrs[attr_set_entry_key(i)] = attr_set_entry_value(i); + touched_souls.insert(es); + modified.insert(std::make_pair(attr_set_entry_path(i), + attr_set_entry_key(i))); + } + for (attr_clear_map::const_iterator i = cs.attr_clears.begin(); + i != cs.attr_clears.end(); ++i) + { + esoul es = lookup(attr_set_entry_path(i)); + element_t & e = element(es); + attr_map::iterator j = e.attrs.find(attr_set_entry_key(i)); + I(j != e.attrs.end()); + e.attrs.erase(j); + touched_souls.insert(es); + I(modified.find(std::make_pair(attr_set_entry_path(i), attr_set_entry_key(i))) + == modified.end()); + } +} + +namespace +{ + // this handles all the stuff in a_new + void unify_roster_oneway(roster_t & a, std::set & a_new, + roster_t & b, std::set & b_new, + std::set new_souls, + soul_source & ss) + { + for (std::set::const_iterator i = a_new.begin(); i != a_new.end(); ++i) + { + element_soul const as = *i; + split_path sp; + // FIXME: climb out only so far as is necessary to find a shared soul? + // possibly faster (since usually will get a hit immediately), but may + // not be worth the effort (since it doesn't take that long to get out + // in any case) + a.get_name(as, sp); + element_soul const bs = b.lookup(as); + if (temp_soul(bs)) + { + esoul new_soul = ss.next(); + a.resoul(ls, new_soul); + b.resoul(rs, new_soul); + new_souls.insert(new_soul); + b_new.erase(bs); + } + else + { + a.resoul(as, bs); + a.element(bs).birth_revision = b.element(bs).birth_revision; + } + } + } + + // after this, left should == right, and there should be no temporary ids + // destroys sets, because that's handy (it has to scan over both, but it can + // skip some double-scanning) + void + unify_rosters(roster_t & left, std::set & left_new, + roster_t & right, std::set & right_new, + // these new_souls all come from the given soul source + std::set new_souls, + soul_source & ss) + { + unify_roster_oneway(left, left_new, right, right_new, new_souls, ss); + unify_roster_oneway(right, right_new, left, left_new, new_souls, ss); + } + +} + + +void roster_for_revision(revision_id const & rid, revision_set const & rev, + roster_t & r, + app_state & app) +{ + // if the revision has 1 edge: get parent roster in r (or blank roster, if + // parent is null), apply the changeset to it, using a real soul source + // use the new_souls and touched_souls things to scan part of resulting + // roster and generate markings + + // if the revision has 2 edges: get two parent rosters. copy each, and + // apply relevant changeset to each copy. + // unify the two copies + // make sure the two unified copies are identical + // throw out one of the two identical copies + // get uncommon ancestors + // scan over new and touched pieces of new roster to generate markings + + // otherwise: I(false) +} ======================================================================== --- roster2.hh +++ roster2.hh 3f708bc76899c06c0c54580d2624b7b7aa70bc2b @@ -0,0 +1,117 @@ +#ifndef __ROSTER_HH__ +#define __ROSTER_HH__ + +// copyright (C) 2005 nathaniel smith +// all rights reserved. +// licensed to the public under the terms of the GNU GPL (>= 2) +// see the file COPYING for details + +#include +#include + +#include "vocab.hh" +#include "numeric_vocab.hh" +#include "paths.hh" +#include "changeset.hh" +#include "app_state.hh" + +// a persistent element id +// but "file_id" means something else... +// "element" terminology is stolen from clearcase, it means (file|directory) +// 32 bits should be sufficient; even with half of them temporary, 2 billion +// distinct files would use 2 terabytes of disk space, assuming each file +// requires only a single sqlite page. easy to change in a few years, in any +// case. +// FIXME: we have too many integer types. make them type-distinct. +typedef uint32_t esoul; + +const esoul the_null_soul = 0; +const uint32_t first_esoul = 1; + +inline bool null_soul(esoul es) +{ + return es = the_null_soul; +} + +const esoul first_temp_soul = 0x80000000; + +inline bool temp_soul(esoul es) +{ + return es & first_temp_soul; +} + +// returns either temp or real souls +struct soul_source +{ + virtual esoul next() = 0; +}; + +struct temp_soul_source : soul_source +{ + temp_soul_source() : curr(first_temp_soul) {} + esoul next() + { + esoul r = curr++; + I(temp_soul(r)); + return r; + } + esoul curr; +}; + +/////////////////////////////////////////////////////////////////// + +typedef enum { etype_dir, etype_file } etype; + +struct element_t +{ + etype type; + revision_id birth_revision; + // this is null iff this is a root dir + esoul parent; + // this is null iff this is a root dir + path_component name; + file_id content; + std::map attrs; + virtual ~element() {}; +}; + + +// FIXME: move this to paths.hh +typedef std::vector split_path; +typedef std::map dir_map; + +class roster_t +{ +public: + roster_t() : root_dir(the_null_soul) {} + esoul lookup(file_path const & fp) const; + esoul lookup(split_path const & sp) const; + esoul lookup(esoul parent, path_component child) const; + void get_name(esoul es, file_path & fp) const; + void get_name(esoul es, split_path & sp) const; + dir_map & children(esoul es); + element_t & element(esoul es); + void resoul(esoul from, esoul to); + void remove(esoul es); + void add(esoul es, split_path const & sp, element_t const & element); + void apply_changeset(changeset const & cs, soul_source & ss, + revision_id const & new_id, + // these are mutually exclusive sets + // the new_souls souls all come from the given + // soul_source + std::set & new_souls, + std::set & touched_souls); +private: + // sets parent to the parent attached to, sets name to the name given + void attach(esoul es, split_path const & sp); + // sets parent to the_null_soul, name to the_null_component + void detach(esoul es); + std::map elements; + std::map children_map; + esoul root_dir; +}; + +// FIXME: add marking stuff here +void roster_for_revision(revision_id const & rid, revision_set const & rev, + roster_t & r, + app_state & app);