Source

`stdlib/parsers/xml/xml.cpp`

2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.

3#include "xml.hpp"

5#include <algorithm>

6#include <cstdint>

7#include <string>

8#include <string_view>

9#include <vector>

11namespace cheatah::parsers::xml {

13namespace {

15bool is_space(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f'; }

17bool is_name_start(char c) {

18 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_' || c == ':';

19}

20bool is_name_char(char c) {

21 return is_name_start(c) || (c >= '0' && c <= '9') || c == '-' || c == '.';

22}

24void append_utf8(std::string& out, std::uint32_t cp) {

25 if (cp <= 0x7F) {

26 out.push_back(static_cast<char>(cp));

27 } else if (cp <= 0x7FF) {

28 out.push_back(static_cast<char>(0xC0 | (cp >> 6)));

29 out.push_back(static_cast<char>(0x80 | (cp & 0x3F)));

30 } else if (cp <= 0xFFFF) {

31 out.push_back(static_cast<char>(0xE0 | (cp >> 12)));

32 out.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3F)));

33 out.push_back(static_cast<char>(0x80 | (cp & 0x3F)));

34 } else {

35 out.push_back(static_cast<char>(0xF0 | (cp >> 18)));

36 out.push_back(static_cast<char>(0x80 | ((cp >> 12) & 0x3F)));

37 out.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3F)));

38 out.push_back(static_cast<char>(0x80 | (cp & 0x3F)));

39 }

40}

42// Decode a reference body (between '&' and ';'). true+append on success; false leaves it.

43bool decode_reference(std::string_view body, std::string& out) {

44 if (body.empty()) return false;

45 if (body.front() == '#') { // numeric © / ©

46 std::uint32_t cp = 0;

47 const bool hex = body.size() > 1 && (body[1] == 'x' || body[1] == 'X');

48 std::size_t i = hex ? 2 : 1;

49 if (i >= body.size()) return false;

50 for (; i < body.size(); ++i) {

51 const char c = body[i];

52 std::uint32_t d = 0;

53 if (c >= '0' && c <= '9') d = static_cast<std::uint32_t>(c - '0');

54 else if (hex && c >= 'a' && c <= 'f') d = static_cast<std::uint32_t>(c - 'a' + 10);

55 else if (hex && c >= 'A' && c <= 'F') d = static_cast<std::uint32_t>(c - 'A' + 10);

56 else return false;

57 cp = cp * (hex ? 16 : 10) + d;

58 if (cp > 0x10FFFF) return false;

59 }

60 if (cp == 0) return false;

61 append_utf8(out, cp);

62 return true;

63 }

64 // The five XML predefined entities.

65 if (body == "amp") { out.push_back('&'); return true; }

66 if (body == "lt") { out.push_back('<'); return true; }

67 if (body == "gt") { out.push_back('>'); return true; }

68 if (body == "quot") { out.push_back('"'); return true; }

69 if (body == "apos") { out.push_back('\''); return true; }

70 return false;

71}

73// Resolve character references in `s` (unknown refs are kept verbatim, like a lenient reader).

74std::string decode(std::string_view s) {

75 std::string out;

76 out.reserve(s.size());

77 for (std::size_t i = 0; i < s.size();) {

78 if (s[i] != '&') { out.push_back(s[i++]); continue; }

79 const std::size_t semi = s.find(';', i + 1);

80 const std::size_t limit = i + 1 + 32; // entity names are short

81 if (semi != std::string_view::npos && semi <= limit && semi > i + 1 &&

82 decode_reference(s.substr(i + 1, semi - i - 1), out)) {

83 i = semi + 1;

84 } else {

85 out.push_back(s[i++]);

86 }

87 }

88 return out;

89}

91// The parser: builds the slab DOM iteratively with an explicit open-element stack.

92struct Parser {

93 std::string_view s;

94 std::size_t i = 0;

95 Document doc;

96 std::vector<int> open; // stack of open element ids (open.back() is the current parent)

98 int current() const { return open.back(); }

100 int add_child(Node&& n) {

101 const int id = static_cast<int>(doc.nodes.size());

102 doc.nodes.push_back(std::move(n));

103 doc.nodes[static_cast<std::size_t>(current())].children.push_back(id);

104 return id;

105 }

106

107 void flush_text(std::size_t from, std::size_t to) {

108 if (to <= from) return;

109 std::string t = decode(s.substr(from, to - from));

110 // Keep only text that has non-whitespace, OR any text inside an element (preserves

111 // significant whitespace); drop pure-whitespace between top-level nodes.

112 bool has_nonspace = false;

113 for (const char c : t) if (!is_space(c)) { has_nonspace = true; break; }

114 if (!has_nonspace && open.size() == 1) return; // ignorable whitespace at document top

115 Node n;

116 n.is_element = false;

117 n.text = std::move(t);

118 add_child(std::move(n));

119 }

120

121 // Parse the attributes of a start tag beginning at s[i] (i points just past the name).

122 // Stops at '>' / '/>' / end-of-input. Sets self_close.

123 void parse_attrs(Node& el, bool& self_close) {

124 const std::size_t n = s.size();

125 while (i < n && s[i] != '>') {

126 while (i < n && is_space(s[i])) ++i;

127 if (i < n && s[i] == '/') { self_close = true; ++i; continue; }

128 if (i >= n || s[i] == '>') break;

129 const std::size_t an = i;

130 while (i < n && !is_space(s[i]) && s[i] != '=' && s[i] != '>' && s[i] != '/') ++i;

131 if (i == an) { ++i; continue; } // stray char

132 std::string name(s.substr(an, i - an));

133 std::string value;

134 while (i < n && is_space(s[i])) ++i;

135 if (i < n && s[i] == '=') {

136 ++i;

137 while (i < n && is_space(s[i])) ++i;

138 if (i < n && (s[i] == '"' || s[i] == '\'')) {

139 const char q = s[i++];

140 const std::size_t vs = i;

141 while (i < n && s[i] != q) ++i;

142 value = decode(s.substr(vs, i - vs));

143 if (i < n) ++i; // closing quote

144 } else {

145 const std::size_t vs = i;

146 while (i < n && !is_space(s[i]) && s[i] != '>' && s[i] != '/') ++i;

147 value = decode(s.substr(vs, i - vs));

148 }

149 }

150 el.attrs.push_back({std::move(name), std::move(value)});

151 }

152 }

153

154 void run() {

155 const std::size_t n = s.size();

156 // The synthetic root.

157 doc.nodes.push_back(Node{});

158 doc.root = 0;

159 open.push_back(0);

160

161 std::size_t text_from = 0;

162 while (i < n) {

163 if (s[i] != '<') { ++i; continue; }

164 flush_text(text_from, i);

165

166 if (s.compare(i, 4, "<!--") == 0) { // comment

167 const std::size_t end = s.find("-->", i + 4);

168 i = (end == std::string_view::npos) ? n : end + 3;

169 text_from = i;

170 continue;

171 }

172 if (s.compare(i, 9, "<![CDATA[") == 0) { // CDATA -> literal text (not decoded)

173 const std::size_t start = i + 9;

174 const std::size_t end = s.find("]]>", start);

175 const std::size_t stop = (end == std::string_view::npos) ? n : end;

176 Node t;

177 t.is_element = false;

178 t.text = std::string(s.substr(start, stop - start));

179 add_child(std::move(t));

180 i = (end == std::string_view::npos) ? n : end + 3;

181 text_from = i;

182 continue;

183 }

184 if (i + 1 < n && (s[i + 1] == '?' || s[i + 1] == '!')) { // prolog / PI / DOCTYPE

185 const std::size_t end = s.find('>', i + 2);

186 i = (end == std::string_view::npos) ? n : end + 1;

187 text_from = i;

188 continue;

189 }

190 if (i + 1 < n && s[i + 1] == '/') { // end tag </name>

191 const std::size_t ns = i + 2;

192 std::size_t j = ns;

193 while (j < n && is_name_char(s[j])) ++j;

194 const std::string_view name = s.substr(ns, j - ns);

195 std::size_t end = s.find('>', j);

196 i = (end == std::string_view::npos) ? n : end + 1;

197 text_from = i;

198 // Pop the matching open element (lenient: pop to it if found in the stack;

199 // ignore a stray close with no match).

200 for (std::size_t k = open.size(); k-- > 1;) {

201 if (doc.nodes[static_cast<std::size_t>(open[k])].tag == name) {

202 open.resize(k);

203 break;

204 }

205 }

206 continue;

207 }

208 if (i + 1 < n && is_name_start(s[i + 1])) { // start tag <name …>

209 std::size_t j = i + 1;

210 while (j < n && is_name_char(s[j])) ++j;

211 Node el;

212 el.is_element = true;

213 el.tag = std::string(s.substr(i + 1, j - (i + 1)));

214 i = j;

215 bool self_close = false;

216 parse_attrs(el, self_close);

217 const int id = add_child(std::move(el));

218 if (i < n && s[i] == '>') ++i;

219 if (!self_close) open.push_back(id);

220 text_from = i;

221 continue;

222 }

223 // A '<' that begins nothing recognizable: treat it as text.

224 ++i;

225 }

226 flush_text(text_from, n);

227 }

228};

229

230const Node* node_at(const Document& doc, int id) {

231 if (id < 0 || static_cast<std::size_t>(id) >= doc.nodes.size()) return nullptr;

232 return &doc.nodes[static_cast<std::size_t>(id)];

233}

234

235void collect_text(const Document& doc, int id, std::string& out) {

236 // Iterative pre-order walk with an explicit stack. The parser is iterative and imposes no

237 // nesting cap, so a deeply-nested element chain (`<a><a>…` to any depth) yields a depth-N tree;

238 // the old recursion here would then overflow the C++ call stack on a valid document. An explicit

239 // stack costs O(depth) heap instead. Children are pushed in REVERSE so they pop left-to-right,

240 // preserving the exact concatenation order of the recursive version.

241 std::vector<int> stack;

242 stack.push_back(id);

243 while (!stack.empty()) {

244 const int cur = stack.back();

245 stack.pop_back();

246 const Node* n = node_at(doc, cur);

247 if (!n) continue;

248 if (!n->is_element) { out += n->text; continue; }

249 for (std::size_t k = n->children.size(); k-- > 0;) stack.push_back(n->children[k]);

250 }

251}

252

253} // namespace

254

255Document parse(std::string_view xml) {

256 Parser p;

257 p.s = xml;

258 p.run();

259 return std::move(p.doc);

260}

261

262int root(const Document& doc) { return doc.root; }

263

264bool is_element(const Document& doc, int id) {

265 const Node* n = node_at(doc, id);

266 return (n != nullptr) && n->is_element;

267}

268

269std::string tag(const Document& doc, int id) {

270 const Node* n = node_at(doc, id);

271 return (n && n->is_element) ? n->tag : std::string();

272}

273

274std::string attr(const Document& doc, int id, std::string_view name) {

275 const Node* n = node_at(doc, id);

276 if (!n) return "";

277 for (const Attr& a : n->attrs) if (a.name == name) return a.value;

278 return "";

279}

280

281bool has_attr(const Document& doc, int id, std::string_view name) {

282 const Node* n = node_at(doc, id);

283 if (!n) return false;

284 return std::ranges::any_of(n->attrs, [name](const Attr& a) { return a.name == name; });

285}

286

287std::string text(const Document& doc, int id) {

288 std::string out;

289 collect_text(doc, id, out);

290 return out;

291}

292

293std::vector<int> children(const Document& doc, int id) {

294 const Node* n = node_at(doc, id);

295 return n ? n->children : std::vector<int>{};

296}

297

298int find(const Document& doc, int id, std::string_view tag) {

299 const Node* n = node_at(doc, id);

300 if (!n) return -1;

301 for (const int c : n->children) {

302 const Node* cn = node_at(doc, c);

303 if (cn && cn->is_element && cn->tag == tag) return c;

304 }

305 return -1;

306}

307

308std::vector<int> findall(const Document& doc, int id, std::string_view tag) {

309 std::vector<int> out;

310 const Node* n = node_at(doc, id);

311 if (!n) return out;

312 for (const int c : n->children) {

313 const Node* cn = node_at(doc, c);

314 if (cn && cn->is_element && cn->tag == tag) out.push_back(c);

315 }

316 return out;

317}

318

319std::vector<int> iter(const Document& doc, int id, std::string_view tag) {

320 std::vector<int> out;

321 if (!node_at(doc, id)) return out;

322 std::vector<int> stack{id};

323 while (!stack.empty()) {

324 const int cur = stack.back();

325 stack.pop_back();

326 const Node* n = node_at(doc, cur);

327 if (!n) continue;

328 if (n->is_element && n->tag == tag) out.push_back(cur);

329 // Push children in reverse so they pop in document order.

330 for (std::size_t k = n->children.size(); k-- > 0;) stack.push_back(n->children[k]);

331 }

332 return out;

333}

334

335} // namespace cheatah::parsers::xml