Source

`stdlib/parsers/html/html.cpp`

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

3#include "html.hpp"

5#include <algorithm>

6#include <array>

7#include <cstdint>

8#include <string>

9#include <string_view>

10#include <unordered_map>

11#include <vector>

13namespace cheatah::parsers::html {

15namespace {

17// ASCII-lowercase a byte (tag/attr names; HTML is ASCII-case-insensitive there).

18char lower(char c) { return (c >= 'A' && c <= 'Z') ? static_cast<char>(c - 'A' + 'a') : c; }

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

21 if (cp <= 0x7F) {

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

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

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

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

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

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

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

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

30 } else {

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

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

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

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

35 }

36}

38// A focused table of the common named entities -> Unicode code point. Not the

39// full HTML5 set; unknown names are left verbatim by unescape().

40const std::unordered_map<std::string_view, std::uint32_t>& named_entities() {

41 static const std::unordered_map<std::string_view, std::uint32_t> kEntities = {

42 {"amp", 0x26}, {"lt", 0x3C}, {"gt", 0x3E}, {"quot", 0x22},

43 {"apos", 0x27}, {"nbsp", 0xA0}, {"copy", 0xA9}, {"reg", 0xAE},

44 {"trade", 0x2122},{"hellip", 0x2026},{"mdash", 0x2014}, {"ndash", 0x2013},

45 {"lsquo", 0x2018},{"rsquo", 0x2019}, {"ldquo", 0x201C}, {"rdquo", 0x201D},

46 {"deg", 0xB0}, {"plusmn", 0xB1}, {"times", 0xD7}, {"divide", 0xF7},

47 {"frac12", 0xBD}, {"frac14", 0xBC}, {"frac34", 0xBE}, {"euro", 0x20AC},

48 {"pound", 0xA3}, {"cent", 0xA2}, {"yen", 0xA5}, {"sect", 0xA7},

49 {"para", 0xB6}, {"middot", 0xB7}, {"laquo", 0xAB}, {"raquo", 0xBB},

50 {"bull", 0x2022}, {"dagger", 0x2020},{"permil", 0x2030},{"prime", 0x2032},

51 {"eacute", 0xE9}, {"egrave", 0xE8}, {"agrave", 0xE0}, {"ccedil", 0xE7},

52 {"auml", 0xE4}, {"ouml", 0xF6}, {"uuml", 0xFC}, {"szlig", 0xDF},

53 {"aelig", 0xE6}, {"oslash", 0xF8}, {"ntilde", 0xF1}, {"micro", 0xB5},

54 };

55 return kEntities;

56}

58// Decode the reference whose body (between '&' and the optional ';') is `body`.

59// Returns true and appends to `out` on success; false leaves it to the caller.

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

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

62 if (body.front() == '#') { // numeric: © or ©

63 std::uint32_t cp = 0;

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

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

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

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

68 const char c = body[i];

69 std::uint32_t digit = 0;

70 if (c >= '0' && c <= '9') {

71 digit = static_cast<std::uint32_t>(c - '0');

72 } else if (hex && c >= 'a' && c <= 'f') {

73 digit = static_cast<std::uint32_t>(c - 'a' + 10);

74 } else if (hex && c >= 'A' && c <= 'F') {

75 digit = static_cast<std::uint32_t>(c - 'A' + 10);

76 } else {

77 return false;

78 }

79 cp = cp * (hex ? 16 : 10) + digit;

80 if (cp > 0x10FFFF) return false; // beyond Unicode range

81 }

82 if (cp == 0) return false;

83 append_utf8(out, cp);

84 return true;

85 }

86 const auto& table = named_entities();

87 const auto it = table.find(body);

88 if (it == table.end()) return false;

89 append_utf8(out, it->second);

90 return true;

91}

93bool is_name_start(char c) {

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

95}

96bool is_name_char(char c) {

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

98}

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

100

101std::string lower_str(std::string_view s) {

102 std::string out;

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

104 for (const char c : s) out.push_back(lower(c));

105 return out;

106}

107

108// Case-insensitive check that s[at..] begins with `lit` (lit is lowercase).

109bool matches_ci(std::string_view s, std::size_t at, std::string_view lit) {

110 if (at + lit.size() > s.size()) return false;

111 for (std::size_t k = 0; k < lit.size(); ++k) {

112 if (lower(s[at + k]) != lit[k]) return false;

113 }

114 return true;

115}

116

117} // namespace

118

119std::string escape(std::string_view s, bool quote) {

120 std::string out;

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

122 for (const char c : s) {

123 switch (c) {

124 case '&': out += "&"; break;

125 case '<': out += "<"; break;

126 case '>': out += ">"; break;

127 case '"': out += quote ? """ : "\""; break;

128 case '\'': out += quote ? "'" : "'"; break;

129 default: out.push_back(c);

130 }

131 }

132 return out;

133}

134

135std::string unescape(std::string_view s) {

136 std::string out;

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

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

139 if (s[i] != '&') {

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

141 continue;

142 }

143 // Find the terminating ';' within a sane window (entity names are short).

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

145 const std::size_t limit = i + 1 + 32;

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

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

148 i = semi + 1;

149 } else {

150 out.push_back(s[i++]); // a bare '&' or unknown reference: keep verbatim

151 }

152 }

153 return out;

154}

155

156std::vector<Token> parse(std::string_view html) {

157 std::vector<Token> tokens;

158 const std::size_t n = html.size();

159 std::size_t i = 0;

160 std::string text; // accumulates a run of character data

161

162 auto flush_text = [&] {

163 if (text.empty()) return;

164 tokens.push_back({"data", "", unescape(text), {}});

165 text.clear();

166 };

167

168 while (i < n) {

169 if (html[i] != '<') {

170 text.push_back(html[i++]);

171 continue;

172 }

173 // Something starting with '<'. Decide what it is.

174 if (matches_ci(html, i, "<!--")) { // comment

175 flush_text();

176 const std::size_t start = i + 4;

177 std::size_t end = html.find("-->", start);

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

179 tokens.push_back({"comment", "", std::string(html.substr(start, stop - start)), {}});

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

181 continue;

182 }

183 if (i + 1 < n && html[i + 1] == '!') { // declaration <!DOCTYPE ...>

184 flush_text();

185 const std::size_t start = i + 2;

186 std::size_t end = html.find('>', start);

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

188 tokens.push_back({"decl", "", std::string(html.substr(start, stop - start)), {}});

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

190 continue;

191 }

192 if (i + 1 < n && html[i + 1] == '?') { // processing instruction <? ... >

193 flush_text();

194 const std::size_t start = i + 2;

195 std::size_t end = html.find('>', start);

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

197 tokens.push_back({"pi", "", std::string(html.substr(start, stop - start)), {}});

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

199 continue;

200 }

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

202 const std::size_t name_start = i + 2;

203 std::size_t j = name_start;

204 while (j < n && is_name_char(html[j])) ++j;

205 if (j == name_start && (j >= n || !is_name_start(html[j]))) {

206 // not a real name (e.g. "</ "): only a tag if name present

207 }

208 if (j > name_start) {

209 flush_text();

210 std::size_t end = html.find('>', j);

211 tokens.push_back({"endtag", lower_str(html.substr(name_start, j - name_start)), "", {}});

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

213 continue;

214 }

215 // malformed: treat '<' as data

216 text.push_back(html[i++]);

217 continue;

218 }

219 if (i + 1 < n && is_name_start(html[i + 1])) { // start tag <name ...>

220 flush_text();

221 std::size_t j = i + 1;

222 while (j < n && is_name_char(html[j])) ++j;

223 const std::string tag = lower_str(html.substr(i + 1, j - (i + 1)));

224

225 std::vector<Attr> attrs;

226 // Parse attributes until '>' or '/>' or end-of-input.

227 while (j < n && html[j] != '>') {

228 while (j < n && is_space(html[j])) ++j;

229 if (j < n && html[j] == '/') { ++j; continue; } // self-close marker

230 if (j >= n || html[j] == '>') break;

231 // attribute name

232 const std::size_t an = j;

233 while (j < n && !is_space(html[j]) && html[j] != '=' && html[j] != '>' &&

234 html[j] != '/') {

235 ++j;

236 }

237 if (j == an) { ++j; continue; } // stray char, skip

238 std::string name = lower_str(html.substr(an, j - an));

239 std::string value;

240 while (j < n && is_space(html[j])) ++j;

241 if (j < n && html[j] == '=') {

242 ++j;

243 while (j < n && is_space(html[j])) ++j;

244 if (j < n && (html[j] == '"' || html[j] == '\'')) {

245 const char q = html[j++];

246 const std::size_t vs = j;

247 while (j < n && html[j] != q) ++j;

248 value = unescape(html.substr(vs, j - vs));

249 if (j < n) ++j; // closing quote

250 } else {

251 const std::size_t vs = j;

252 while (j < n && !is_space(html[j]) && html[j] != '>') ++j;

253 value = unescape(html.substr(vs, j - vs));

254 }

255 }

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

257 }

258 // Detect self-closing: last non-space before '>' was '/'.

259 bool self_close = false;

260 if (j < n && html[j] == '>') {

261 std::size_t k = j;

262 while (k > i && is_space(html[k - 1])) --k;

263 if (k > i && html[k - 1] == '/') self_close = true;

264 }

265 const std::size_t after = (j < n) ? j + 1 : n;

266

267 tokens.push_back({self_close ? "startendtag" : "starttag", tag, "", std::move(attrs)});

268

269 // Raw-text elements: emit their body verbatim, then the end tag.

270 if (!self_close && (tag == "script" || tag == "style")) {

271 const std::string close = "</" + tag;

272 std::size_t k = after;

273 while (k < n) {

274 if (html[k] == '<' && matches_ci(html, k, close)) break;

275 ++k;

276 }

277 if (k > after) {

278 tokens.push_back({"data", "", std::string(html.substr(after, k - after)), {}});

279 }

280 if (k < n) { // consume the matching close tag

281 std::size_t end = html.find('>', k);

282 tokens.push_back({"endtag", tag, "", {}});

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

284 } else {

285 i = n;

286 }

287 continue;

288 }

289 i = after;

290 continue;

291 }

292 // A '<' that starts nothing recognizable -> literal data.

293 text.push_back(html[i++]);

294 }

295 flush_text();

296 return tokens;

297}

298

299std::string get_attr(const Token& t, std::string_view name) {

300 const std::string key = lower_str(name);

301 for (const Attr& a : t.attrs) {

302 if (a.name == key) return a.value;

303 }

304 return "";

305}

306

307bool has_attr(const Token& t, std::string_view name) {

308 const std::string key = lower_str(name);

309 return std::ranges::any_of(t.attrs, [&key](const Attr& a) { return a.name == key; });

310}

311

312} // namespace cheatah::parsers::html