aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore5
-rw-r--r--LICENSE14
-rw-r--r--README.md1
-rw-r--r--include/HtmlParser.h54
-rw-r--r--project.conf5
-rw-r--r--src/HtmlParser.c434
-rw-r--r--tests/main.c6
7 files changed, 519 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..636c6b9
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,5 @@
+# Compiled sibs files
+sibs-build/
+compile_commands.json
+tests/sibs-build/
+tests/compile_commands.json
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..b27915c
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,14 @@
+Copyright (C) 2019 DEC05EBA
+
+This program is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program. If not, see <https://www.gnu.org/licenses/>.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..b90e48b
--- /dev/null
+++ b/README.md
@@ -0,0 +1 @@
+A small html parser written in C. The parser fixes broken html (missing end tags). The parser doesn't perform any dynamic allocations (heap) and only outputs the parsing result to a callback function rather than a dom tree.
diff --git a/include/HtmlParser.h b/include/HtmlParser.h
new file mode 100644
index 0000000..72de123
--- /dev/null
+++ b/include/HtmlParser.h
@@ -0,0 +1,54 @@
+#ifndef HTML_PARSER_H
+#define HTML_PARSER_H
+
+/*
+ A small html parser with no dependencies and doesn't dynamically allocate any memory
+ and can parse and repair broken html (just like web browsers)
+*/
+
+#include <stddef.h>
+
+typedef struct {
+ const char *data;
+ size_t size;
+} StringView;
+
+typedef struct HtmlParser HtmlParser;
+
+typedef enum{
+ HTML_PARSE_TAG_START,
+ HTML_PARSE_TAG_END,
+ HTML_PARSE_ATTRIBUTE,
+ HTML_PARSE_TEXT,
+ HTML_PARSE_JAVASCRIPT_CODE
+} HtmlParseType;
+
+typedef void (*HtmlParseCallback)(HtmlParser *html_parser, HtmlParseType parse_type, void *userdata);
+
+#define UNCLOSED_TAGS_SIZE 2048
+
+struct HtmlParser {
+ const char *source;
+ size_t source_len;
+ size_t offset;
+ HtmlParseCallback parse_callback;
+ void *callback_userdata;
+
+ StringView tag_name;
+ StringView attribute_key;
+ StringView attribute_value;
+ StringView text;
+
+ int is_tag_void;
+ int inside_script_tag;
+
+ size_t unclosed_tags_offset;
+ StringView unclosed_tags[UNCLOSED_TAGS_SIZE];
+};
+
+void html_parser_init(HtmlParser *self, const char *html_source, size_t len, HtmlParseCallback parse_callback, void *userdata);
+void html_parser_deinit(HtmlParser *self);
+
+void html_parser_parse(HtmlParser *self);
+
+#endif /* HTML_PARSER_H */ \ No newline at end of file
diff --git a/project.conf b/project.conf
new file mode 100644
index 0000000..84f91f0
--- /dev/null
+++ b/project.conf
@@ -0,0 +1,5 @@
+[package]
+name = "html-parser"
+type = "static"
+version = "0.1.0"
+platforms = ["any"]
diff --git a/src/HtmlParser.c b/src/HtmlParser.c
new file mode 100644
index 0000000..a1b62cd
--- /dev/null
+++ b/src/HtmlParser.c
@@ -0,0 +1,434 @@
+#include "../include/HtmlParser.h"
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+
+static StringView void_tags[] = {
+ {.data = "area", .size = 4},
+ {.data = "base", .size = 4},
+ {.data = "br", .size = 2},
+ {.data = "col", .size = 3},
+ {.data = "command", .size = 7},
+ {.data = "embed", .size = 5},
+ {.data = "hr", .size = 2},
+ {.data = "img", .size = 3},
+ {.data = "input", .size = 5},
+ {.data = "keygen", .size = 6},
+ {.data = "link", .size = 4},
+ {.data = "meta", .size = 4},
+ {.data = "param", .size = 5},
+ {.data = "source", .size = 6},
+ {.data = "track", .size = 5},
+ {.data = "wbr", .size = 3},
+ {.data = NULL, .size = 0}
+};
+
+static StringView script_tag = {.data = "script", .size = 6};
+
+static int string_view_equals(StringView *self, StringView *other) {
+ return self->size == other->size && memcmp(self->data, other->data, self->size) == 0;
+}
+
+static int is_whitespace(int c) {
+ switch(c) {
+ case ' ':
+ case '\n':
+ case '\r':
+ case '\t':
+ case '\v':
+ return 1;
+ default:
+ return 0;
+ }
+}
+
+static int is_newline(int c) {
+ return c == '\n' || c == '\r';
+}
+
+static void lstrip(const char *str, size_t size, const char **output_str, size_t *output_size, int(*strip_filter_func)(int)) {
+ size_t i = 0;
+ while(i < size && strip_filter_func(str[i])) {
+ ++i;
+ }
+ *output_str = str + i;
+ *output_size = size - i;
+}
+
+static void rstrip(const char *str, size_t size, size_t *output_size, int(*strip_filter_func)(int)) {
+ ssize_t i = size - 1;
+ while(i >= 0 && strip_filter_func(str[i])) {
+ --i;
+ }
+ *output_size = i + 1;
+}
+
+static void strip(const char *str, size_t size, const char **output_str, size_t *output_size, int(*strip_filter_func)(int)) {
+ lstrip(str, size, output_str, output_size, strip_filter_func);
+ rstrip(*output_str, *output_size, output_size, strip_filter_func);
+}
+
+static int is_void_tag(StringView *tag_name) {
+ StringView *tag_iter = &void_tags[0];
+ /* !DOCTYPE, !--, etc.... */
+ if(tag_name->size > 0 && tag_name->data[0] == '!')
+ return 1;
+ while(tag_iter->data) {
+ if(string_view_equals(tag_name, tag_iter))
+ return 1;
+ ++tag_iter;
+ }
+ return 0;
+}
+
+static void html_parser_reset(HtmlParser *self) {
+ self->offset = 0;
+ self->tag_name.data = NULL;
+ self->tag_name.size = 0;
+ self->attribute_key.data = NULL;
+ self->attribute_key.size = 0;
+ self->attribute_value.data = NULL;
+ self->attribute_value.size = 0;
+ self->text.data = NULL;
+ self->text.size = 0;
+ self->is_tag_void = 0;
+ self->inside_script_tag = 0;
+ self->unclosed_tags_offset = 0;
+}
+
+void html_parser_init(HtmlParser *self, const char *html_source, size_t len, HtmlParseCallback parse_callback, void *userdata) {
+ self->source = html_source;
+ self->source_len = len;
+ self->parse_callback = parse_callback;
+ self->callback_userdata = userdata;
+}
+
+void html_parser_deinit(HtmlParser *self) {
+
+}
+
+static char html_parser_next_char(HtmlParser *self) {
+ if(self->offset < self->source_len) {
+ char c = self->source[self->offset];
+ ++self->offset;
+ return c;
+ }
+ return '\0';
+}
+
+static char html_parser_peek_char(HtmlParser *self) {
+ if(self->offset < self->source_len) {
+ char c = self->source[self->offset];
+ return c;
+ }
+ return '\0';
+}
+
+static void html_parser_advance_char(HtmlParser *self) {
+ ++self->offset;
+}
+
+static int is_alpha(char c) {
+ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
+}
+
+static int is_digit(char c) {
+ return c >= '0' && c <= '9';
+}
+
+static int is_identifier_char(char c) {
+ return is_alpha(c) || is_digit(c) || c == '-' || c == '_' || c == '!';
+}
+
+static void html_parser_try_append_unclosed_tag(HtmlParser *self, const char *data, size_t size) {
+ if(self->unclosed_tags_offset == UNCLOSED_TAGS_SIZE) {
+ fprintf(stderr, "Reached the maximum number of unclosed tags! the html source is too broken\n");
+ return;
+ }
+ self->unclosed_tags[self->unclosed_tags_offset].data = data;
+ self->unclosed_tags[self->unclosed_tags_offset].size = size;
+ ++self->unclosed_tags_offset;
+}
+
+static void html_parser_pop_unclosed_tag(HtmlParser *self) {
+ assert(self->unclosed_tags_offset > 0);
+ --self->unclosed_tags_offset;
+}
+
+static void html_parser_try_pop_unclosed_tag(HtmlParser *self) {
+ if(self->unclosed_tags_offset > 0)
+ --self->unclosed_tags_offset;
+}
+
+static int html_parser_try_get_top_unclosed_tag(HtmlParser *self, StringView *result) {
+ if(self->unclosed_tags_offset > 0) {
+ *result = self->unclosed_tags[self->unclosed_tags_offset - 1];
+ return 1;
+ }
+ return 0;
+}
+
+static void html_parser_skip_whitespace(HtmlParser *self) {
+ for(;;) {
+ char c = html_parser_peek_char(self);
+ if(is_whitespace(c)) {
+ html_parser_advance_char(self);
+ } else {
+ break;
+ }
+ }
+}
+
+static int is_attribute_value_char(char c) {
+ switch(c) {
+ case '"':
+ case '\'':
+ case '`':
+ case '<':
+ case '>':
+ case '&':
+ return 0;
+ default:
+ return 1;
+ }
+}
+
+/* TODO: Unescape html characters in attribute value */
+static void html_parser_parse_attribute_value_quoted(HtmlParser *self, char quote_symbol) {
+ self->attribute_value.data = self->source + self->offset;
+ for(;;) {
+ char c = html_parser_peek_char(self);
+ if(c == quote_symbol) {
+ self->attribute_value.size = (self->source + self->offset) - self->attribute_value.data;
+ html_parser_advance_char(self);
+ break;
+ } else if(c == '\0') {
+ self->attribute_value.size = (self->source + self->offset) - self->attribute_value.data;
+ break;
+ } else {
+ html_parser_advance_char(self);
+ }
+ }
+ strip(self->attribute_value.data, self->attribute_value.size, &self->attribute_value.data, &self->attribute_value.size, is_newline);
+}
+
+static void html_parser_parse_attribute_value(HtmlParser *self) {
+ self->attribute_value.data = self->source + self->offset;
+ for(;;) {
+ char c = html_parser_peek_char(self);
+ if(!is_attribute_value_char(c) || c == '\0')
+ break;
+ else
+ html_parser_advance_char(self);
+ }
+ self->attribute_value.size = (self->source + self->offset) - self->attribute_value.data;
+}
+
+static void html_parser_goto_end_of_js_string(HtmlParser *self, char quote_symbol) {
+ int escape_quote = 0;
+ for(;;) {
+ char c = html_parser_next_char(self);
+ if(!escape_quote && c == quote_symbol) {
+ return;
+ } else if(c == '\\') {
+ escape_quote = !escape_quote;
+ } else if(c == '\0') {
+ return;
+ } else {
+ escape_quote = 0;
+ }
+ }
+}
+
+static void html_parser_goto_script_end_tag(HtmlParser *self) {
+ self->text.data = self->source + self->offset;
+ self->text.size = 0;
+ for(;;) {
+ char c = html_parser_peek_char(self);
+ if(c == '"' || c == '\'') {
+ html_parser_advance_char(self);
+ html_parser_goto_end_of_js_string(self, c);
+ } else if(c == '<' && self->offset + 7 < self->source_len && strncmp(self->source + self->offset + 1, "/script", 7) == 0) {
+ self->text.size = (self->source + self->offset) - self->text.data;
+ strip(self->text.data, self->text.size, &self->text.data, &self->text.size, is_whitespace);
+ self->offset += 7;
+ for(;;) {
+ c = html_parser_peek_char(self);
+ if(c == '>') {
+ html_parser_advance_char(self);
+ break;
+ } else if(c == '\0') {
+ break;
+ } else {
+ html_parser_advance_char(self);
+ }
+ }
+ break;
+ } else if(c == '\0') {
+ self->text.size = (self->source + self->offset) - self->text.data;
+ strip(self->text.data, self->text.size, &self->text.data, &self->text.size, is_whitespace);
+ break;
+ } else {
+ html_parser_advance_char(self);
+ }
+ }
+ if(self->text.size > 0)
+ self->parse_callback(self, HTML_PARSE_JAVASCRIPT_CODE, self->callback_userdata);
+}
+
+static void html_parser_parse_tag_start(HtmlParser *self) {
+ int tag_name_found = 0;
+ for(;;) {
+ char c = html_parser_next_char(self);
+ if(c == '>') {
+ if(self->is_tag_void)
+ self->parse_callback(self, HTML_PARSE_TAG_END, self->callback_userdata);
+ self->is_tag_void = 0;
+
+ if(self->inside_script_tag) {
+ self->inside_script_tag = 0;
+ /* <script> tags require special handling since they can have </script> inside a javascript string */
+ html_parser_goto_script_end_tag(self);
+ }
+ return;
+ } else if(c == '/') {
+ if(html_parser_peek_char(self) == '>') {
+ html_parser_advance_char(self);
+ if(tag_name_found) {
+ self->parse_callback(self, HTML_PARSE_TAG_END, self->callback_userdata);
+ if(!self->is_tag_void)
+ html_parser_try_pop_unclosed_tag(self);
+ }
+ self->is_tag_void = 0;
+ self->inside_script_tag = 0;
+ return;
+ }
+ } else if(is_identifier_char(c)) {
+ StringView identifier;
+ identifier.data = self->source + self->offset - 1;
+ for(;;) {
+ c = html_parser_peek_char(self);
+ if(is_identifier_char(c)) {
+ html_parser_advance_char(self);
+ } else {
+ break;
+ }
+ }
+ identifier.size = (self->source + self->offset) - identifier.data;
+ if(tag_name_found) {
+ /* attribute name */
+ self->attribute_key = identifier;
+ self->attribute_value.data = NULL;
+ self->attribute_value.size = 0;
+
+ html_parser_skip_whitespace(self);
+ c = html_parser_peek_char(self);
+ if(c == '=') {
+ html_parser_advance_char(self);
+ html_parser_skip_whitespace(self);
+ c = html_parser_peek_char(self);
+ if(c == '"' || c == '\'' || c == '`') {
+ html_parser_advance_char(self);
+ html_parser_parse_attribute_value_quoted(self, c);
+ } else if(is_attribute_value_char(c)) {
+ html_parser_advance_char(self);
+ html_parser_parse_attribute_value(self);
+ }
+ }
+ self->parse_callback(self, HTML_PARSE_ATTRIBUTE, self->callback_userdata);
+ } else {
+ /* tag name */
+ self->tag_name = identifier;
+ tag_name_found = 1;
+ self->is_tag_void = is_void_tag(&self->tag_name);
+ if(!self->is_tag_void) {
+ html_parser_try_append_unclosed_tag(self, self->tag_name.data, self->tag_name.size);
+ self->inside_script_tag = string_view_equals(&self->tag_name, &script_tag);
+ }
+ self->parse_callback(self, HTML_PARSE_TAG_START, self->callback_userdata);
+ }
+ } else if(c == '\0') {
+ return;
+ }
+ }
+}
+
+static void html_parser_parse_tag_end(HtmlParser *self) {
+ int tag_name_found = 0;
+ for(;;) {
+ char c = html_parser_peek_char(self);
+ if(c == '>') {
+ html_parser_advance_char(self);
+ return;
+ } else if(!tag_name_found && is_identifier_char(c)) {
+ StringView tag_end_name;
+ tag_end_name.data = self->source + self->offset;
+ html_parser_advance_char(self);
+ for(;;) {
+ c = html_parser_peek_char(self);
+ if(is_identifier_char(c)) {
+ html_parser_advance_char(self);
+ } else {
+ break;
+ }
+ }
+ tag_end_name.size = (self->source + self->offset) - tag_end_name.data;
+
+ /* void tags close themselves, this is probably invalid html but we choose to ignore it silently */
+ if(is_void_tag(&tag_end_name)) {
+ fprintf(stderr, "Warning: got end tag for void tag '%.*s'\n", tag_end_name.size, tag_end_name.data);
+ continue;
+ }
+
+ StringView top_unclosed_tag;
+ while(html_parser_try_get_top_unclosed_tag(self, &top_unclosed_tag)) {
+ self->tag_name = top_unclosed_tag;
+ self->parse_callback(self, HTML_PARSE_TAG_END, self->callback_userdata);
+ html_parser_pop_unclosed_tag(self);
+ if(string_view_equals(&top_unclosed_tag, &tag_end_name))
+ break;
+ }
+ } else if(c == '\0') {
+ return;
+ } else {
+ html_parser_advance_char(self);
+ }
+ }
+}
+
+void html_parser_parse(HtmlParser *self) {
+ html_parser_reset(self);
+ for(;;) {
+ char c = html_parser_next_char(self);
+ if(c == '<') {
+ if(html_parser_peek_char(self) == '/') {
+ html_parser_advance_char(self);
+ html_parser_parse_tag_end(self);
+ } else {
+ html_parser_parse_tag_start(self);
+ }
+ } else if(c == '\0') {
+ break;
+ } else {
+ self->text.data = (self->source + self->offset) - 1;
+ for(;;) {
+ c = html_parser_peek_char(self);
+ if(c == '<' || c == '\0')
+ break;
+ else
+ html_parser_advance_char(self);
+ }
+ self->text.size = (self->source + self->offset) - self->text.data;
+ strip(self->text.data, self->text.size, &self->text.data, &self->text.size, is_whitespace);
+ if(self->text.size > 0)
+ self->parse_callback(self, HTML_PARSE_TEXT, self->callback_userdata);
+ }
+ }
+
+ StringView top_unclosed_tag;
+ while(html_parser_try_get_top_unclosed_tag(self, &top_unclosed_tag)) {
+ self->tag_name = top_unclosed_tag;
+ self->parse_callback(self, HTML_PARSE_TAG_END, self->callback_userdata);
+ html_parser_pop_unclosed_tag(self);
+ }
+}
diff --git a/tests/main.c b/tests/main.c
new file mode 100644
index 0000000..ff1570b
--- /dev/null
+++ b/tests/main.c
@@ -0,0 +1,6 @@
+#include <stdio.h>
+
+int main(int argc, char **argv) {
+ printf("hello, world!\n");
+ return 0;
+}