tools/quickbook/src/id_generation.cpp

   1 /*=============================================================================
   2     Copyright (c) 2011, 2013 Daniel James
   3
   4     Use, modification and distribution is subject to the Boost Software
   5     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt)
   7 =============================================================================*/
   8
   9 #include <cctype>
  10 #include <boost/lexical_cast.hpp>
  11 #include <boost/make_shared.hpp>
  12 #include <boost/range/algorithm/sort.hpp>
  13 #include <boost/unordered_map.hpp>
  14 #include "document_state_impl.hpp"
  15 #include "for.hpp"
  16
  17 namespace quickbook
  18 {
  19     //
  20     // The maximum size of a generated part of an id.
  21     //
  22     // Not a strict maximum, sometimes broken because the user
  23     // explicitly uses a longer id, or for backwards compatibility.
  24
  25     static const std::size_t max_size = 32;
  26
  27     typedef std::vector<id_placeholder const*> placeholder_index;
  28     placeholder_index index_placeholders(
  29         document_state_impl const&, quickbook::string_view);
  30
  31     void generate_id_block(
  32         placeholder_index::iterator,
  33         placeholder_index::iterator,
  34         std::vector<std::string>& generated_ids);
  35
  36     std::vector<std::string> generate_ids(
  37         document_state_impl const& state, quickbook::string_view xml)
  38     {
  39         std::vector<std::string> generated_ids(state.placeholders.size());
  40
  41         // Get a list of the placeholders in the order that we wish to
  42         // process them.
  43         placeholder_index placeholders = index_placeholders(state, xml);
  44
  45         typedef std::vector<id_placeholder const*>::iterator iterator;
  46         iterator it = placeholders.begin(), end = placeholders.end();
  47
  48         while (it != end) {
  49             // We process all the ids that have the same number of dots
  50             // together. Note that ids with different parents can clash, e.g.
  51             // because of old fashioned id generation or anchors containing
  52             // multiple dots.
  53             //
  54             // So find the group of placeholders with the same number of dots.
  55             iterator group_begin = it, group_end = it;
  56             while (group_end != end &&
  57                    (*group_end)->num_dots == (*it)->num_dots)
  58                 ++group_end;
  59
  60             generate_id_block(group_begin, group_end, generated_ids);
  61             it = group_end;
  62         }
  63
  64         return generated_ids;
  65     }
  66
  67     //
  68     // index_placeholders
  69     //
  70     // Create a sorted index of the placeholders, in order
  71     // to make numbering duplicates easy. A total order.
  72     //
  73
  74     struct placeholder_compare
  75     {
  76         std::vector<unsigned>& order;
  77
  78         placeholder_compare(std::vector<unsigned>& order_) : order(order_) {}
  79
  80         bool operator()(id_placeholder const* x, id_placeholder const* y) const
  81         {
  82             bool x_explicit = x->category.c >= id_category::explicit_id;
  83             bool y_explicit = y->category.c >= id_category::explicit_id;
  84
  85             return x->num_dots < y->num_dots
  86                        ? true
  87                        : x->num_dots > y->num_dots
  88                              ? false
  89                              : x_explicit > y_explicit
  90                                    ? true
  91                                    : x_explicit < y_explicit
  92                                          ? false
  93                                          : order[x->index] < order[y->index];
  94         }
  95     };
  96
  97     struct get_placeholder_order_callback : xml_processor::callback
  98     {
  99         document_state_impl const& state;
 100         std::vector<unsigned>& order;
 101         unsigned count;
 102
 103         get_placeholder_order_callback(
 104             document_state_impl const& state_, std::vector<unsigned>& order_)
 105             : state(state_), order(order_), count(0)
 106         {
 107         }
 108
 109         void id_value(quickbook::string_view value)
 110         {
 111             set_placeholder_order(state.get_placeholder(value));
 112         }
 113
 114         void set_placeholder_order(id_placeholder const* p)
 115         {
 116             if (p && !order[p->index]) {
 117                 set_placeholder_order(p->parent);
 118                 order[p->index] = ++count;
 119             }
 120         }
 121     };
 122
 123     placeholder_index index_placeholders(
 124         document_state_impl const& state, quickbook::string_view xml)
 125     {
 126         // The order that the placeholder appear in the xml source.
 127         std::vector<unsigned> order(state.placeholders.size());
 128
 129         xml_processor processor;
 130         get_placeholder_order_callback callback(state, order);
 131         processor.parse(xml, callback);
 132
 133         placeholder_index sorted_placeholders;
 134         sorted_placeholders.reserve(state.placeholders.size());
 135         QUICKBOOK_FOR (id_placeholder const& p, state.placeholders)
 136             if (order[p.index]) sorted_placeholders.push_back(&p);
 137         boost::sort(sorted_placeholders, placeholder_compare(order));
 138
 139         return sorted_placeholders;
 140     }
 141
 142     // Resolve and generate ids.
 143
 144     struct generate_id_block_type
 145     {
 146         // The ids which won't require duplicate handling.
 147         typedef boost::unordered_map<std::string, id_placeholder const*>
 148             chosen_id_map;
 149         chosen_id_map chosen_ids;
 150         std::vector<std::string>& generated_ids;
 151
 152         explicit generate_id_block_type(
 153             std::vector<std::string>& generated_ids_)
 154             : generated_ids(generated_ids_)
 155         {
 156         }
 157
 158         void generate(
 159             placeholder_index::iterator begin, placeholder_index::iterator end);
 160
 161         std::string resolve_id(id_placeholder const*);
 162         std::string generate_id(id_placeholder const*, std::string const&);
 163     };
 164
 165     void generate_id_block(
 166         placeholder_index::iterator begin,
 167         placeholder_index::iterator end,
 168         std::vector<std::string>& generated_ids)
 169     {
 170         generate_id_block_type impl(generated_ids);
 171         impl.generate(begin, end);
 172     }
 173
 174     void generate_id_block_type::generate(
 175         placeholder_index::iterator begin, placeholder_index::iterator end)
 176     {
 177         std::vector<std::string> resolved_ids;
 178
 179         for (placeholder_index::iterator i = begin; i != end; ++i)
 180             resolved_ids.push_back(resolve_id(*i));
 181
 182         unsigned index = 0;
 183         for (placeholder_index::iterator i = begin; i != end; ++i, ++index) {
 184             generated_ids[(**i).index] = generate_id(*i, resolved_ids[index]);
 185         }
 186     }
 187
 188     std::string generate_id_block_type::resolve_id(id_placeholder const* p)
 189     {
 190         std::string id =
 191             p->parent ? generated_ids[p->parent->index] + "." + p->id : p->id;
 192
 193         if (p->category.c > id_category::numbered) {
 194             // Reserve the id if it isn't already reserved.
 195             chosen_id_map::iterator pos = chosen_ids.emplace(id, p).first;
 196
 197             // If it was reserved by a placeholder with a lower category,
 198             // then overwrite it.
 199             if (p->category.c > pos->second->category.c) pos->second = p;
 200         }
 201
 202         return id;
 203     }
 204
 205     std::string generate_id_block_type::generate_id(
 206         id_placeholder const* p, std::string const& resolved_id)
 207     {
 208         if (p->category.c > id_category::numbered &&
 209             chosen_ids.at(resolved_id) == p) {
 210             return resolved_id;
 211         }
 212
 213         // Split the id into its parent part and child part.
 214         //
 215         // Note: can't just use the placeholder's parent, as the
 216         // placeholder id might contain dots.
 217         std::size_t child_start = resolved_id.rfind('.');
 218         std::string parent_id, base_id;
 219
 220         if (child_start == std::string::npos) {
 221             base_id = normalize_id(resolved_id, max_size - 1);
 222         }
 223         else {
 224             parent_id = resolved_id.substr(0, child_start + 1);
 225             base_id =
 226                 normalize_id(resolved_id.substr(child_start + 1), max_size - 1);
 227         }
 228
 229         // Since we're adding digits, don't want an id that ends in
 230         // a digit.
 231
 232         std::string::size_type length = base_id.size();
 233
 234         if (length > 0 && std::isdigit(base_id[length - 1])) {
 235             if (length < max_size - 1) {
 236                 base_id += '_';
 237                 ++length;
 238             }
 239             else {
 240                 while (length > 0 && std::isdigit(base_id[length - 1]))
 241                     --length;
 242                 base_id.erase(length);
 243             }
 244         }
 245
 246         unsigned count = 0;
 247
 248         for (;;) {
 249             std::string postfix = boost::lexical_cast<std::string>(count++);
 250
 251             if ((base_id.size() + postfix.size()) > max_size) {
 252                 // The id is now too long, so reduce the length and
 253                 // start again.
 254
 255                 // Would need a lot of ids to get this far....
 256                 if (length == 0) throw std::runtime_error("Too many ids");
 257
 258                 // Trim a character.
 259                 --length;
 260
 261                 // Trim any trailing digits.
 262                 while (length > 0 && std::isdigit(base_id[length - 1]))
 263                     --length;
 264
 265                 base_id.erase(length);
 266                 count = 0;
 267             }
 268             else {
 269                 // Try to reserve this id.
 270                 std::string generated_id = parent_id + base_id + postfix;
 271
 272                 if (chosen_ids.emplace(generated_id, p).second) {
 273                     return generated_id;
 274                 }
 275             }
 276         }
 277     }
 278
 279     //
 280     // replace_ids
 281     //
 282     // Return a copy of the xml with all the placeholders replaced by
 283     // generated_ids.
 284     //
 285
 286     struct replace_ids_callback : xml_processor::callback
 287     {
 288         document_state_impl const& state;
 289         std::vector<std::string> const* ids;
 290         string_iterator source_pos;
 291         std::string result;
 292
 293         replace_ids_callback(
 294             document_state_impl const& state_,
 295             std::vector<std::string> const* ids_)
 296             : state(state_), ids(ids_), source_pos(), result()
 297         {
 298         }
 299
 300         void start(quickbook::string_view xml) { source_pos = xml.begin(); }
 301
 302         void id_value(quickbook::string_view value)
 303         {
 304             if (id_placeholder const* p = state.get_placeholder(value)) {
 305                 quickbook::string_view id =
 306                     ids ? (*ids)[p->index] : p->unresolved_id;
 307
 308                 result.append(source_pos, value.begin());
 309                 result.append(id.begin(), id.end());
 310                 source_pos = value.end();
 311             }
 312         }
 313
 314         void finish(quickbook::string_view xml)
 315         {
 316             result.append(source_pos, xml.end());
 317             source_pos = xml.end();
 318         }
 319     };
 320
 321     std::string replace_ids(
 322         document_state_impl const& state,
 323         quickbook::string_view xml,
 324         std::vector<std::string> const* ids)
 325     {
 326         xml_processor processor;
 327         replace_ids_callback callback(state, ids);
 328         processor.parse(xml, callback);
 329         return callback.result;
 330     }
 331
 332     //
 333     // normalize_id
 334     //
 335     // Normalizes generated ids.
 336     //
 337
 338     std::string normalize_id(quickbook::string_view src_id)
 339     {
 340         return normalize_id(src_id, max_size);
 341     }
 342
 343     std::string normalize_id(quickbook::string_view src_id, std::size_t size)
 344     {
 345         std::string id(src_id.begin(), src_id.end());
 346
 347         std::size_t src = 0;
 348         std::size_t dst = 0;
 349
 350         while (src < id.length() && id[src] == '_') {
 351             ++src;
 352         }
 353
 354         if (src == id.length()) {
 355             id = "_";
 356         }
 357         else {
 358             while (src < id.length() && dst < size) {
 359                 if (id[src] == '_') {
 360                     do {
 361                         ++src;
 362                     } while (src < id.length() && id[src] == '_');
 363
 364                     if (src < id.length()) id[dst++] = '_';
 365                 }
 366                 else {
 367                     id[dst++] = id[src++];
 368                 }
 369             }
 370
 371             id.erase(dst);
 372         }
 373
 374         return id;
 375     }
 376 }