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

6#include <cstdint>

7#include <string>

8#include <string_view>

9#include <unordered_map>

10#include <vector>

12namespace cheatah::parsers::html {

14namespace {

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

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

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

20 if (cp <= 0x7F) {

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

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

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

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

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

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

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

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

29 } else {

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

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

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

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

34 }

35}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53 };

54 return kEntities;

55}

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

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

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

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

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

62 std::uint32_t cp = 0;

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

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

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

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

67 const char c = body[i];

68 std::uint32_t digit;

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

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

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

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

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

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

75 } else {

76 return false;

77 }

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

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

80 }

81 if (cp == 0) return false;

82 append_utf8(out, cp);

83 return true;

84 }

85 const auto& table = named_entities();

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

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

88 append_utf8(out, it->second);

89 return true;

90}

92bool is_name_start(char c) {

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

94}

95bool is_name_char(char c) {

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

97}

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

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

101 std::string out;

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

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

104 return out;

105}

106

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

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

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

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

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

112 }

113 return true;

114}

115

116} // namespace

117

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

119 std::string out;

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

121 for (const char c : s) {

122 switch (c) {

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

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

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

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

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

128 default: out.push_back(c);

129 }

130 }

131 return out;

132}

133

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

135 std::string out;

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

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

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

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

140 continue;

141 }

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

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

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

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

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

147 i = semi + 1;

148 } else {

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

150 }

151 }

152 return out;

153}

154

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

156 std::vector<Token> tokens;

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

158 std::size_t i = 0;

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

160

161 auto flush_text = [&] {

162 if (text.empty()) return;

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

164 text.clear();

165 };

166

167 while (i < n) {

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

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

170 continue;

171 }

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

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

174 flush_text();

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

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

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

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

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

180 continue;

181 }

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

183 flush_text();

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

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

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

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

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

189 continue;

190 }

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

192 flush_text();

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

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

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

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

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

198 continue;

199 }

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

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

202 std::size_t j = name_start;

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

204 if (j == name_start && !(j < n && is_name_start(html[j]))) {

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

206 }

207 if (j > name_start) {

208 flush_text();

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

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

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

212 continue;

213 }

214 // malformed: treat '<' as data

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

216 continue;

217 }

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

219 flush_text();

220 std::size_t j = i + 1;

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

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

223

224 std::vector<Attr> attrs;

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

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

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

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

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

230 // attribute name

231 const std::size_t an = j;

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

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

234 ++j;

235 }

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

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

238 std::string value;

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

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

241 ++j;

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

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

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

245 const std::size_t vs = j;

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

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

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

249 } else {

250 const std::size_t vs = j;

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

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

253 }

254 }

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

256 }

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

258 bool self_close = false;

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

260 std::size_t k = j;

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

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

263 }

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

265

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

267

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

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

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

271 std::size_t k = after;

272 while (k < n) {

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

274 ++k;

275 }

276 if (k > after) {

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

278 }

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

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

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

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

283 } else {

284 i = n;

285 }

286 continue;

287 }

288 i = after;

289 continue;

290 }

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

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

293 }

294 flush_text();

295 return tokens;

296}

297

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

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

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

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

302 }

303 return "";

304}

305

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

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

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

309 if (a.name == key) return true;

310 }

311 return false;

312}

313

314} // namespace cheatah::parsers::html