1 /*=============================================================================
2 Copyright (c) 2011, 2013 Daniel James
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 =============================================================================*/
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"
20 // The maximum size of a generated part of an id.
22 // Not a strict maximum, sometimes broken because the user
23 // explicitly uses a longer id, or for backwards compatibility.
25 static const std::size_t max_size
= 32;
27 typedef std::vector
<id_placeholder
const*> placeholder_index
;
28 placeholder_index
index_placeholders(
29 document_state_impl
const&, quickbook::string_view
);
31 void generate_id_block(
32 placeholder_index::iterator
,
33 placeholder_index::iterator
,
34 std::vector
<std::string
>& generated_ids
);
36 std::vector
<std::string
> generate_ids(
37 document_state_impl
const& state
, quickbook::string_view xml
)
39 std::vector
<std::string
> generated_ids(state
.placeholders
.size());
41 // Get a list of the placeholders in the order that we wish to
43 placeholder_index placeholders
= index_placeholders(state
, xml
);
45 typedef std::vector
<id_placeholder
const*>::iterator iterator
;
46 iterator it
= placeholders
.begin(), end
= placeholders
.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
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
)
60 generate_id_block(group_begin
, group_end
, generated_ids
);
70 // Create a sorted index of the placeholders, in order
71 // to make numbering duplicates easy. A total order.
74 struct placeholder_compare
76 std::vector
<unsigned>& order
;
78 placeholder_compare(std::vector
<unsigned>& order_
) : order(order_
) {}
80 bool operator()(id_placeholder
const* x
, id_placeholder
const* y
) const
82 bool x_explicit
= x
->category
.c
>= id_category::explicit_id
;
83 bool y_explicit
= y
->category
.c
>= id_category::explicit_id
;
85 return x
->num_dots
< y
->num_dots
87 : x
->num_dots
> y
->num_dots
89 : x_explicit
> y_explicit
91 : x_explicit
< y_explicit
93 : order
[x
->index
] < order
[y
->index
];
97 struct get_placeholder_order_callback
: xml_processor::callback
99 document_state_impl
const& state
;
100 std::vector
<unsigned>& order
;
103 get_placeholder_order_callback(
104 document_state_impl
const& state_
, std::vector
<unsigned>& order_
)
105 : state(state_
), order(order_
), count(0)
109 void id_value(quickbook::string_view value
)
111 set_placeholder_order(state
.get_placeholder(value
));
114 void set_placeholder_order(id_placeholder
const* p
)
116 if (p
&& !order
[p
->index
]) {
117 set_placeholder_order(p
->parent
);
118 order
[p
->index
] = ++count
;
123 placeholder_index
index_placeholders(
124 document_state_impl
const& state
, quickbook::string_view xml
)
126 // The order that the placeholder appear in the xml source.
127 std::vector
<unsigned> order(state
.placeholders
.size());
129 xml_processor processor
;
130 get_placeholder_order_callback
callback(state
, order
);
131 processor
.parse(xml
, callback
);
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
));
139 return sorted_placeholders
;
142 // Resolve and generate ids.
144 struct generate_id_block_type
146 // The ids which won't require duplicate handling.
147 typedef boost::unordered_map
<std::string
, id_placeholder
const*>
149 chosen_id_map chosen_ids
;
150 std::vector
<std::string
>& generated_ids
;
152 explicit generate_id_block_type(
153 std::vector
<std::string
>& generated_ids_
)
154 : generated_ids(generated_ids_
)
159 placeholder_index::iterator begin
, placeholder_index::iterator end
);
161 std::string
resolve_id(id_placeholder
const*);
162 std::string
generate_id(id_placeholder
const*, std::string
const&);
165 void generate_id_block(
166 placeholder_index::iterator begin
,
167 placeholder_index::iterator end
,
168 std::vector
<std::string
>& generated_ids
)
170 generate_id_block_type
impl(generated_ids
);
171 impl
.generate(begin
, end
);
174 void generate_id_block_type::generate(
175 placeholder_index::iterator begin
, placeholder_index::iterator end
)
177 std::vector
<std::string
> resolved_ids
;
179 for (placeholder_index::iterator i
= begin
; i
!= end
; ++i
)
180 resolved_ids
.push_back(resolve_id(*i
));
183 for (placeholder_index::iterator i
= begin
; i
!= end
; ++i
, ++index
) {
184 generated_ids
[(**i
).index
] = generate_id(*i
, resolved_ids
[index
]);
188 std::string
generate_id_block_type::resolve_id(id_placeholder
const* p
)
191 p
->parent
? generated_ids
[p
->parent
->index
] + "." + p
->id
: p
->id
;
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
;
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
;
205 std::string
generate_id_block_type::generate_id(
206 id_placeholder
const* p
, std::string
const& resolved_id
)
208 if (p
->category
.c
> id_category::numbered
&&
209 chosen_ids
.at(resolved_id
) == p
) {
213 // Split the id into its parent part and child part.
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
;
220 if (child_start
== std::string::npos
) {
221 base_id
= normalize_id(resolved_id
, max_size
- 1);
224 parent_id
= resolved_id
.substr(0, child_start
+ 1);
226 normalize_id(resolved_id
.substr(child_start
+ 1), max_size
- 1);
229 // Since we're adding digits, don't want an id that ends in
232 std::string::size_type length
= base_id
.size();
234 if (length
> 0 && std::isdigit(base_id
[length
- 1])) {
235 if (length
< max_size
- 1) {
240 while (length
> 0 && std::isdigit(base_id
[length
- 1]))
242 base_id
.erase(length
);
249 std::string postfix
= boost::lexical_cast
<std::string
>(count
++);
251 if ((base_id
.size() + postfix
.size()) > max_size
) {
252 // The id is now too long, so reduce the length and
255 // Would need a lot of ids to get this far....
256 if (length
== 0) throw std::runtime_error("Too many ids");
261 // Trim any trailing digits.
262 while (length
> 0 && std::isdigit(base_id
[length
- 1]))
265 base_id
.erase(length
);
269 // Try to reserve this id.
270 std::string generated_id
= parent_id
+ base_id
+ postfix
;
272 if (chosen_ids
.emplace(generated_id
, p
).second
) {
282 // Return a copy of the xml with all the placeholders replaced by
286 struct replace_ids_callback
: xml_processor::callback
288 document_state_impl
const& state
;
289 std::vector
<std::string
> const* ids
;
290 string_iterator source_pos
;
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()
300 void start(quickbook::string_view xml
) { source_pos
= xml
.begin(); }
302 void id_value(quickbook::string_view value
)
304 if (id_placeholder
const* p
= state
.get_placeholder(value
)) {
305 quickbook::string_view id
=
306 ids
? (*ids
)[p
->index
] : p
->unresolved_id
;
308 result
.append(source_pos
, value
.begin());
309 result
.append(id
.begin(), id
.end());
310 source_pos
= value
.end();
314 void finish(quickbook::string_view xml
)
316 result
.append(source_pos
, xml
.end());
317 source_pos
= xml
.end();
321 std::string
replace_ids(
322 document_state_impl
const& state
,
323 quickbook::string_view xml
,
324 std::vector
<std::string
> const* ids
)
326 xml_processor processor
;
327 replace_ids_callback
callback(state
, ids
);
328 processor
.parse(xml
, callback
);
329 return callback
.result
;
335 // Normalizes generated ids.
338 std::string
normalize_id(quickbook::string_view src_id
)
340 return normalize_id(src_id
, max_size
);
343 std::string
normalize_id(quickbook::string_view src_id
, std::size_t size
)
345 std::string
id(src_id
.begin(), src_id
.end());
350 while (src
< id
.length() && id
[src
] == '_') {
354 if (src
== id
.length()) {
358 while (src
< id
.length() && dst
< size
) {
359 if (id
[src
] == '_') {
362 } while (src
< id
.length() && id
[src
] == '_');
364 if (src
< id
.length()) id
[dst
++] = '_';
367 id
[dst
++] = id
[src
++];