Subject: [Boost-commit] svn:boost r85368 - trunk/tools/quickbook/src
From: dnljms_at_[hidden]
Date: 2013-08-16 13:31:26
Author: danieljames
Date: 2013-08-16 13:31:26 EDT (Fri, 16 Aug 2013)
New Revision: 85368
URL: http://svn.boost.org/trac/boost/changeset/85368
Log:
Simpler, less efficient, id generation.
I noticed a bug for an edge case in the id generator. Wouldn't be too
hard to fix, but the implementation was too complicated with some really
pointless optimizations, so I rewrote it using a simpler brute force
method. Will be fine for now unless something has a lot of duplicate ids.
Text files modified:
trunk/tools/quickbook/src/id_generation.cpp | 338 ++++++++++++++++-----------------------
trunk/tools/quickbook/src/id_manager_impl.hpp | 3
2 files changed, 142 insertions(+), 199 deletions(-)
Modified: trunk/tools/quickbook/src/id_generation.cpp
==============================================================================
--- trunk/tools/quickbook/src/id_generation.cpp Fri Aug 16 13:31:08 2013 (r85367)
+++ trunk/tools/quickbook/src/id_generation.cpp 2013-08-16 13:31:26 EDT (Fri, 16 Aug 2013) (r85368)
@@ -25,90 +25,12 @@
static const std::size_t max_size = 32;
- //
- // Data used for generating placeholders that have duplicates.
- //
-
- struct id_generation_data
- {
- id_generation_data(boost::string_ref src_id)
- : child_start(src_id.rfind('.') + 1),
- id(normalize_id(src_id, child_start, max_size - 1)),
- // 'max_size - 1' leaves a character to append
- // a number.
- count(0)
- {
- if (std::isdigit(id[id.length() - 1]))
- {
- if (child_length() < max_size - 1)
- id += '_';
- else
- reduce_id();
- }
- }
-
- void reduce_id()
- {
- assert(id.length() > child_start);
- std::size_t length = id.length() - 1;
- while(length > child_start && std::isdigit(id[length - 1])) --length;
- id.erase(length);
- count = 0;
- }
-
- std::size_t child_length() const
- {
- return id.length() - child_start;
- }
-
- std::size_t child_start;
- std::string id;
- int count;
- };
-
- // Created for all desired ids, either when resolving an id or due to
- // generating a new id to avoid duplicates.
- struct id_data
- {
- id_data()
- : category(id_category::numbered),
- used(false),
- generation_data()
- {}
-
- void update_category(id_category c)
- {
- if (c.c > category.c) category = c;
- }
-
- id_category category; // The highest priority category of the
- // placeholders that want to use this id.
- bool used; // Whether this id has been used.
- boost::shared_ptr<id_generation_data> generation_data;
- // If a duplicates are found, this is
- // created to generate new ids.
- //
- // Many to one relationship, because truncation
- // can lead to different ids contending for the
- // same id prefix.
- };
-
- struct placeholder_generation_data
- {
- placeholder_generation_data() : resolved_id(), data(0) {}
-
- std::string resolved_id;
- id_data* data;
- };
-
- typedef boost::unordered_map<std::string, id_data> allocated_ids;
- typedef std::vector<placeholder_generation_data> placeholder_data;
typedef std::vector<id_placeholder const*> placeholder_index;
+ placeholder_index index_placeholders(id_state const&, boost::string_ref);
- placeholder_index index_placeholders(id_state const&, boost::string_ref xml);
- void resolve_id(id_placeholder const&, std::vector<std::string> const&,
- allocated_ids&, placeholder_data& data);
- std::string generate_id(id_placeholder const&, allocated_ids&, placeholder_data& data);
+ void generate_id_block(
+ placeholder_index::iterator, placeholder_index::iterator,
+ std::vector<std::string>& generated_ids);
std::vector<std::string> generate_ids(id_state const& state, boost::string_ref xml)
{
@@ -119,9 +41,7 @@
placeholder_index placeholders = index_placeholders(state, xml);
typedef std::vector<id_placeholder const*>::iterator iterator;
-
- iterator it = placeholders.begin(),
- end = placeholders.end();
+ iterator it = placeholders.begin(), end = placeholders.end();
while (it != end) {
// We process all the ids that have the same number of dots
@@ -134,21 +54,8 @@
while (group_end != end && (*group_end)->num_dots == (*it)->num_dots)
++group_end;
- // Used to find duplicate ids, and store required data about them.
- allocated_ids ids;
- placeholder_data data(state.placeholders.size());
-
- // First resolve ids by adding them to their parent's ids
- // (which have been fully processed in a previous iteration).
- for (it = group_begin; it != group_end; ++it) {
- resolve_id(**it, generated_ids, ids, data);
- }
-
- // Generate the final ids, taking into account any duplicates
- // found when resolving.
- for (it = group_begin; it != group_end; ++it) {
- generated_ids[(*it)->index] = generate_id(**it, ids, data);
- }
+ generate_id_block(group_begin, group_end, generated_ids);
+ it = group_end;
}
return generated_ids;
@@ -228,101 +135,146 @@
return sorted_placeholders;
}
- //
- // resolve_id
- //
- // Convert child ids to full ids, and add to the
- // allocated ids (although not yet set in stone because
- // there might be duplicates).
- //
- // Note that the parent ids has to be generated before resolving
- // the child id.
- //
+ // Resolve and generate ids.
- void resolve_id(id_placeholder const& p, std::vector<std::string> const& generated_ids,
- allocated_ids& ids, placeholder_data& data)
+ struct generate_id_block_type
{
- assert(!data[p.index].data);
+ // The ids which won't require duplicate handling.
+ typedef boost::unordered_map<std::string, id_placeholder const*>
+ chosen_id_map;
+ chosen_id_map chosen_ids;
+ std::vector<std::string>& generated_ids;
- std::string id = p.parent ?
- generated_ids[p.parent->index] + "." + p.id : p.id;
+ generate_id_block_type(std::vector<std::string>& generated_ids) :
+ generated_ids(generated_ids) {}
- id_data& data_ = ids.emplace(id, id_data()).first->second;
- data_.update_category(p.category);
+ void generate(placeholder_index::iterator begin,
+ placeholder_index::iterator end);
- data[p.index].data = &data_;
- data[p.index].resolved_id = id;
+ std::string resolve_id(id_placeholder const*);
+ std::string generate_id(id_placeholder const*, std::string const&);
+ };
+
+ void generate_id_block(placeholder_index::iterator begin,
+ placeholder_index::iterator end,
+ std::vector<std::string>& generated_ids)
+ {
+ generate_id_block_type impl(generated_ids);
+ impl.generate(begin, end);
}
- //
- // generate_id
- //
- // Finally generate the final id.
- //
+ void generate_id_block_type::generate(placeholder_index::iterator begin,
+ placeholder_index::iterator end)
+ {
+ std::vector<std::string> resolved_ids;
+
+ for (placeholder_index::iterator i = begin; i != end; ++i)
+ resolved_ids.push_back(resolve_id(*i));
- void register_generation_data(id_placeholder const&, allocated_ids&,
- placeholder_data& data);
+ unsigned index = 0;
+ for (placeholder_index::iterator i = begin; i != end; ++i, ++index)
+ {
+ generated_ids[(**i).index] =
+ generate_id(*i, resolved_ids[index]);
+ }
+ }
- std::string generate_id(id_placeholder const& p, allocated_ids& ids,
- placeholder_data& data)
+ std::string generate_id_block_type::resolve_id(id_placeholder const* p)
{
- assert(data[p.index].data);
+ std::string id = p->parent ?
+ generated_ids[p->parent->index] + "." + p->id :
+ p->id;
+
+ if (p->category.c > id_category::numbered) {
+ // Reserve the id if it isn't already reserved.
+ chosen_id_map::iterator pos = chosen_ids.emplace(id, p).first;
+
+ // If it was reserved by a placeholder with a lower category,
+ // then overwrite it.
+ if (p->category.c > pos->second->category.c)
+ pos->second = p;
+ }
+
+ return id;
+ }
- // If the placeholder id is available, then update data
- // and return.
- if (p.category == data[p.index].data->category &&
- !data[p.index].data->used &&
- p.category.c != id_category::numbered)
+ std::string generate_id_block_type::generate_id(id_placeholder const* p,
+ std::string const& resolved_id)
+ {
+ if (p->category.c > id_category::numbered &&
+ chosen_ids.at(resolved_id) == p)
{
- data[p.index].data->used = true;
- return data[p.index].resolved_id;
+ return resolved_id;
}
- if (!data[p.index].data->generation_data)
- {
- data[p.index].data->generation_data =
- boost::make_shared<id_generation_data>(data[p.index].resolved_id);
- register_generation_data(p, ids, data);
+ // Split the id into its parent part and child part.
+ //
+ // Note: can't just use the placeholder's parent, as the
+ // placeholder id might contain dots.
+ unsigned child_start = resolved_id.rfind('.');
+ std::string parent_id, base_id;
+
+ if (child_start == std::string::npos) {
+ base_id = normalize_id(resolved_id, max_size - 1);
+ }
+ else {
+ parent_id = resolved_id.substr(0, child_start + 1);
+ base_id = normalize_id(resolved_id.substr(child_start + 1),
+ max_size - 1);
}
- // Loop until an available id is found.
- for(;;)
- {
- id_generation_data& generation_data = *data[p.index].data->generation_data;
+ // Since we're adding digits, don't want an id that ends in
+ // a digit.
+
+ unsigned int length = base_id.size();
+ if (length > 0 && std::isdigit(base_id[length - 1])) {
+ if (length < max_size - 1) {
+ base_id += '_';
+ ++length;
+ }
+ else {
+ while (length > 0 && std::isdigit(base_id[length -1]))
+ --length;
+ base_id.erase(length);
+ }
+ }
+
+ unsigned count = 0;
+
+ while (true)
+ {
std::string postfix =
- boost::lexical_cast<std::string>(generation_data.count++);
+ boost::lexical_cast<std::string>(count++);
- if (generation_data.child_length() + postfix.length() > max_size) {
- // The resulting id is too long, so move to a shorter id.
- generation_data.reduce_id();
- register_generation_data(p, ids, data);
+ if ((base_id.size() + postfix.size()) > max_size) {
+ // The id is now too long, so reduce the length and
+ // start again.
+
+ // Would need a lot of ids to get this far....
+ if (length == 0) throw std::runtime_error("Too many ids");
+
+ // Trim a character.
+ --length;
+
+ // Trim any trailing digits.
+ while (length > 0 && std::isdigit(base_id[length -1]))
+ --length;
+
+ base_id.erase(length);
+ count = 0;
}
else {
- std::string id = generation_data.id + postfix;
+ // Try to reserve this id.
+ std::string generated_id = parent_id + base_id + postfix;
- if (ids.find(id) == ids.end()) return id;
+ if (chosen_ids.emplace(generated_id, p).second) {
+ return generated_id;
+ }
}
}
}
- // Every time the generation id is changed, this is called to
- // check if that id is already in use.
- void register_generation_data(id_placeholder const& p, allocated_ids& ids,
- placeholder_data& data)
- {
- std::string const& id = data[p.index].data->generation_data->id;
-
- id_data& new_data = ids.emplace(id, id_data()).first->second;
-
- // If there is already generation_data for the new id then use that.
- // Otherwise use the placeholder's existing generation_data.
- if (new_data.generation_data)
- data[p.index].data->generation_data = new_data.generation_data;
- else
- new_data.generation_data = data[p.index].data->generation_data;
- }
-
//
// replace_ids
//
@@ -387,47 +339,39 @@
std::string normalize_id(boost::string_ref src_id)
{
- return normalize_id(src_id, 0, max_size);
+ return normalize_id(src_id, max_size);
}
- std::string normalize_id(
- boost::string_ref src_id,
- std::size_t prefix = 0,
- std::size_t size = max_size)
+ std::string normalize_id(boost::string_ref src_id, std::size_t size)
{
std::string id(src_id.begin(), src_id.end());
- std::size_t src = prefix;
- std::size_t dst = prefix;
- size += prefix;
-
- if (src >= id.length()) {
- return id;
- }
+ std::size_t src = 0;
+ std::size_t dst = 0;
while (src < id.length() && id[src] == '_') {
++src;
}
- if (src >= id.length()) {
- id += '_';
- return id;
+ if (src == id.length()) {
+ id = "_";
}
-
- while (src < id.length() && dst < size) {
- if (id[src] == '_') {
- do {
- ++src;
- } while(src < id.length() && id[src] == '_');
-
- if (src < id.length()) id[dst++] = '_';
+ else {
+ while (src < id.length() && dst < size) {
+ if (id[src] == '_') {
+ do {
+ ++src;
+ } while(src < id.length() && id[src] == '_');
+
+ if (src < id.length()) id[dst++] = '_';
+ }
+ else {
+ id[dst++] = id[src++];
+ }
}
- else {
- id[dst++] = id[src++];
- }
- }
- id.erase(dst);
+ id.erase(dst);
+ }
return id;
}
Modified: trunk/tools/quickbook/src/id_manager_impl.hpp
==============================================================================
--- trunk/tools/quickbook/src/id_manager_impl.hpp Fri Aug 16 13:31:08 2013 (r85367)
+++ trunk/tools/quickbook/src/id_manager_impl.hpp 2013-08-16 13:31:26 EDT (Fri, 16 Aug 2013) (r85368)
@@ -113,8 +113,7 @@
std::vector<std::string> generate_ids(id_state const&, boost::string_ref);
std::string normalize_id(boost::string_ref src_id);
- std::string normalize_id(boost::string_ref src_id,
- std::size_t, std::size_t);
+ std::string normalize_id(boost::string_ref src_id, std::size_t);
//
// Xml subset parser used for finding id values.