]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
11fdf7f2 TL |
10 | #include <boost/lexical_cast.hpp> |
11 | #include <boost/make_shared.hpp> | |
92f5a8d4 | 12 | #include <boost/range/algorithm/sort.hpp> |
11fdf7f2 TL |
13 | #include <boost/unordered_map.hpp> |
14 | #include "document_state_impl.hpp" | |
92f5a8d4 | 15 | #include "for.hpp" |
7c673cae | 16 | |
11fdf7f2 TL |
17 | namespace quickbook |
18 | { | |
7c673cae FG |
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; | |
11fdf7f2 TL |
28 | placeholder_index index_placeholders( |
29 | document_state_impl const&, quickbook::string_view); | |
7c673cae FG |
30 | |
31 | void generate_id_block( | |
11fdf7f2 TL |
32 | placeholder_index::iterator, |
33 | placeholder_index::iterator, | |
34 | std::vector<std::string>& generated_ids); | |
7c673cae | 35 | |
11fdf7f2 TL |
36 | std::vector<std::string> generate_ids( |
37 | document_state_impl const& state, quickbook::string_view xml) | |
7c673cae FG |
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; | |
11fdf7f2 TL |
56 | while (group_end != end && |
57 | (*group_end)->num_dots == (*it)->num_dots) | |
7c673cae FG |
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 | ||
b32b8144 | 78 | placeholder_compare(std::vector<unsigned>& order_) : order(order_) {} |
7c673cae FG |
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 | ||
11fdf7f2 TL |
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]; | |
7c673cae FG |
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 | ||
11fdf7f2 TL |
103 | get_placeholder_order_callback( |
104 | document_state_impl const& state_, std::vector<unsigned>& order_) | |
105 | : state(state_), order(order_), count(0) | |
106 | { | |
107 | } | |
7c673cae | 108 | |
b32b8144 | 109 | void id_value(quickbook::string_view value) |
7c673cae FG |
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( | |
11fdf7f2 | 124 | document_state_impl const& state, quickbook::string_view xml) |
7c673cae FG |
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()); | |
92f5a8d4 | 135 | QUICKBOOK_FOR (id_placeholder const& p, state.placeholders) |
7c673cae FG |
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 | ||
11fdf7f2 TL |
152 | explicit generate_id_block_type( |
153 | std::vector<std::string>& generated_ids_) | |
154 | : generated_ids(generated_ids_) | |
155 | { | |
156 | } | |
7c673cae | 157 | |
11fdf7f2 TL |
158 | void generate( |
159 | placeholder_index::iterator begin, placeholder_index::iterator end); | |
7c673cae FG |
160 | |
161 | std::string resolve_id(id_placeholder const*); | |
162 | std::string generate_id(id_placeholder const*, std::string const&); | |
163 | }; | |
164 | ||
11fdf7f2 TL |
165 | void generate_id_block( |
166 | placeholder_index::iterator begin, | |
167 | placeholder_index::iterator end, | |
168 | std::vector<std::string>& generated_ids) | |
7c673cae FG |
169 | { |
170 | generate_id_block_type impl(generated_ids); | |
171 | impl.generate(begin, end); | |
172 | } | |
173 | ||
11fdf7f2 TL |
174 | void generate_id_block_type::generate( |
175 | placeholder_index::iterator begin, placeholder_index::iterator end) | |
7c673cae FG |
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; | |
11fdf7f2 TL |
183 | for (placeholder_index::iterator i = begin; i != end; ++i, ++index) { |
184 | generated_ids[(**i).index] = generate_id(*i, resolved_ids[index]); | |
7c673cae FG |
185 | } |
186 | } | |
187 | ||
188 | std::string generate_id_block_type::resolve_id(id_placeholder const* p) | |
189 | { | |
11fdf7f2 TL |
190 | std::string id = |
191 | p->parent ? generated_ids[p->parent->index] + "." + p->id : p->id; | |
7c673cae FG |
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. | |
11fdf7f2 | 199 | if (p->category.c > pos->second->category.c) pos->second = p; |
7c673cae FG |
200 | } |
201 | ||
202 | return id; | |
203 | } | |
204 | ||
11fdf7f2 TL |
205 | std::string generate_id_block_type::generate_id( |
206 | id_placeholder const* p, std::string const& resolved_id) | |
7c673cae FG |
207 | { |
208 | if (p->category.c > id_category::numbered && | |
11fdf7f2 | 209 | chosen_ids.at(resolved_id) == p) { |
7c673cae FG |
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); | |
11fdf7f2 TL |
225 | base_id = |
226 | normalize_id(resolved_id.substr(child_start + 1), max_size - 1); | |
7c673cae FG |
227 | } |
228 | ||
229 | // Since we're adding digits, don't want an id that ends in | |
230 | // a digit. | |
231 | ||
b32b8144 | 232 | std::string::size_type length = base_id.size(); |
7c673cae FG |
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 { | |
11fdf7f2 | 240 | while (length > 0 && std::isdigit(base_id[length - 1])) |
7c673cae FG |
241 | --length; |
242 | base_id.erase(length); | |
243 | } | |
244 | } | |
245 | ||
246 | unsigned count = 0; | |
247 | ||
11fdf7f2 TL |
248 | for (;;) { |
249 | std::string postfix = boost::lexical_cast<std::string>(count++); | |
7c673cae FG |
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. | |
11fdf7f2 | 262 | while (length > 0 && std::isdigit(base_id[length - 1])) |
7c673cae FG |
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; | |
b32b8144 | 290 | string_iterator source_pos; |
7c673cae FG |
291 | std::string result; |
292 | ||
11fdf7f2 TL |
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() | |
7c673cae | 297 | { |
7c673cae FG |
298 | } |
299 | ||
11fdf7f2 TL |
300 | void start(quickbook::string_view xml) { source_pos = xml.begin(); } |
301 | ||
b32b8144 | 302 | void id_value(quickbook::string_view value) |
7c673cae | 303 | { |
11fdf7f2 TL |
304 | if (id_placeholder const* p = state.get_placeholder(value)) { |
305 | quickbook::string_view id = | |
306 | ids ? (*ids)[p->index] : p->unresolved_id; | |
7c673cae FG |
307 | |
308 | result.append(source_pos, value.begin()); | |
309 | result.append(id.begin(), id.end()); | |
310 | source_pos = value.end(); | |
311 | } | |
312 | } | |
313 | ||
b32b8144 | 314 | void finish(quickbook::string_view xml) |
7c673cae FG |
315 | { |
316 | result.append(source_pos, xml.end()); | |
317 | source_pos = xml.end(); | |
318 | } | |
319 | }; | |
320 | ||
11fdf7f2 TL |
321 | std::string replace_ids( |
322 | document_state_impl const& state, | |
323 | quickbook::string_view xml, | |
324 | std::vector<std::string> const* ids) | |
7c673cae FG |
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 | ||
b32b8144 | 338 | std::string normalize_id(quickbook::string_view src_id) |
7c673cae FG |
339 | { |
340 | return normalize_id(src_id, max_size); | |
341 | } | |
342 | ||
b32b8144 | 343 | std::string normalize_id(quickbook::string_view src_id, std::size_t size) |
7c673cae FG |
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; | |
11fdf7f2 | 362 | } while (src < id.length() && id[src] == '_'); |
7c673cae FG |
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 | } |