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 <cstdint>

6#include <string>

7#include <string_view>

8#include <vector>

10namespace cheatah::parsers::xml {

12namespace {

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

16bool is_name_start(char c) {

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

18}

19bool is_name_char(char c) {

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

21}

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

24 if (cp <= 0x7F) {

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

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

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

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

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

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

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

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

33 } else {

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

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

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

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

38 }

39}

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

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

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

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

45 std::uint32_t cp = 0;

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

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

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

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

50 const char c = body[i];

51 std::uint32_t d;

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

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

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

55 else return false;

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

57 if (cp > 0x10FFFF) return false;

58 }

59 if (cp == 0) return false;

60 append_utf8(out, cp);

61 return true;

62 }

63 // The five XML predefined entities.

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

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

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

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

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

69 return false;

70}

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

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

74 std::string out;

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

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

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

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

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

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

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

82 i = semi + 1;

83 } else {

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

85 }

86 }

87 return out;

88}

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

91struct Parser {

92 std::string_view s;

93 std::size_t i = 0;

94 Document doc;

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

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

99 int add_child(Node&& n) {

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

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

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

103 return id;

104 }

105

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

107 if (to <= from) return;

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

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

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

111 bool has_nonspace = false;

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

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

114 Node n;

115 n.is_element = false;

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

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

118 }

119

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

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

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

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

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

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

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

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

128 const std::size_t an = i;

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

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

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

132 std::string value;

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

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

135 ++i;

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

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

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

139 const std::size_t vs = i;

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

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

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

143 } else {

144 const std::size_t vs = i;

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

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

147 }

148 }

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

150 }

151 }

152

153 void run() {

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

155 // The synthetic root.

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

157 doc.root = 0;

158 open.push_back(0);

159

160 std::size_t text_from = 0;

161 while (i < n) {

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

163 flush_text(text_from, i);

164

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

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

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

168 text_from = i;

169 continue;

170 }

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

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

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

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

175 Node t;

176 t.is_element = false;

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

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

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

180 text_from = i;

181 continue;

182 }

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

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

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

186 text_from = i;

187 continue;

188 }

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

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

191 std::size_t j = ns;

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

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

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

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

196 text_from = i;

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

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

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

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

201 open.resize(k);

202 break;

203 }

204 }

205 continue;

206 }

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

208 std::size_t j = i + 1;

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

210 Node el;

211 el.is_element = true;

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

213 i = j;

214 bool self_close = false;

215 parse_attrs(el, self_close);

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

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

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

219 text_from = i;

220 continue;

221 }

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

223 ++i;

224 }

225 flush_text(text_from, n);

226 }

227};

228

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

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

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

232}

233

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

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

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

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

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

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

240 std::vector<int> stack;

241 stack.push_back(id);

242 while (!stack.empty()) {

243 const int cur = stack.back();

244 stack.pop_back();

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

246 if (!n) continue;

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

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

249 }

250}

251

252} // namespace

253

254Document parse(std::string_view xml) {

255 Parser p;

256 p.s = xml;

257 p.run();

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

259}

260

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

262

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

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

265 return n && n->is_element;

266}

267

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

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

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

271}

272

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

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

275 if (!n) return "";

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

277 return "";

278}

279

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

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

282 if (!n) return false;

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

284 return false;

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