odin-html

lex.odin (16447B)

---

 package html
 
 import "core:log"
 import "core:math/rand"
 import "core:os"
 import "core:path/filepath"
 import "core:strconv"
 import "core:strings"
 import "core:testing"
 import "core:time"
 import "core:unicode"
 
 DOCTYPE_LITERAL :: "<!DOCTYPE"
 
 // Token is a flat descriptor of a lexical token.
 //
 // `start` and `end` are inclusive byte offsets into the source string.
 // For atoms (single-character tokens) `end == start`.
 Token :: struct {
 	kind:  Token_Kind,
 	start: u32,
 	end:   u32,
 }
 
 Token_Kind :: enum u8 {
 	Open_Tag_Start,
 	Tag_End,
 	Close_Tag_Start,
 	Self_Closing_Tag_End,
 	Assign,
 	Comment_Start,
 	Comment_End,
 	Double_Quote_String_Literal,
 	Single_Quote_String_Literal,
 	Raw_Text,
 	Doctype,
 }
 
 Lexer :: struct {
 	cursor: u32,
 	source: string,
 }
 
 lexer_next :: proc(l: ^Lexer) -> (t: Token, ok: bool) {
 	if peek := lexer_peek(l, len(DOCTYPE_LITERAL)); peek == DOCTYPE_LITERAL {
 		start := l.cursor
 		if !lexer_advance_until(l, `>`) do return t, false
 		end := l.cursor
 		defer lexer_advance(l)
 		return Token{kind = .Doctype, start = start, end = end}, true
 	}
 
 	peek := lexer_peek(l)
 	if peek == "" {
 		return t, false
 	}
 
 	if t, ok := lex_token(l); ok {
 		return t, true
 	}
 
 	// Advance until we find an interesting token.
 	// The cursor is reset to undo the advancing that occurs within lex_token.
 	start := l.cursor
 	for {
 		if !lexer_advance(l) {
 			break
 		}
 
 		start := l.cursor
 		_, ok := lex_token(l)
 		l.cursor = start
 
 		if ok {
 			break
 		}
 	}
 	end := l.cursor - 1
 
 	return Token{kind = .Raw_Text, start = start, end = end}, true
 }
 
 @(private = "file")
 lex_token :: proc(l: ^Lexer) -> (t: Token, ok: bool) {
 	if peek := lexer_peek(l, 4); peek == "<!--" {
 		defer lexer_advance(l, 4)
 		return Token{kind = .Comment_Start, start = l.cursor, end = l.cursor + 3}, true
 	}
 
 	if peek := lexer_peek(l, 3); peek == "-->" {
 		defer lexer_advance(l, 3)
 		return Token{kind = .Comment_End, start = l.cursor, end = l.cursor + 2}, true
 	}
 
 	if peek := lexer_peek(l, 2); peek != "" && peek[0] == '<' && unicode.is_letter(rune(peek[1])) {
 		lexer_advance(l)
 		start := l.cursor
 		if !lexer_advance_while_letters(l) do return
 		end := l.cursor
 		defer lexer_advance(l)
 		return Token{kind = .Open_Tag_Start, start = start, end = end}, true
 	}
 
 	if peek := lexer_peek(l, 2); peek == "</" {
 		lexer_advance(l, 2)
 		start := l.cursor
 		if !lexer_advance_while_letters(l) do return
 		end := l.cursor
 		defer lexer_advance(l)
 		return Token{kind = .Close_Tag_Start, start = start, end = end}, true
 	}
 
 	if peek := lexer_peek(l, 2); peek == "/>" {
 		defer lexer_advance(l, 2)
 		return Token{kind = .Self_Closing_Tag_End, start = l.cursor, end = l.cursor + 1}, true
 	}
 
 	if peek := lexer_peek(l, 1); peek == ">" {
 		defer lexer_advance(l, 1)
 		return Token{kind = .Tag_End, start = l.cursor, end = l.cursor}, true
 	}
 
 	if peek := lexer_peek(l, 1); peek == "=" {
 		defer lexer_advance(l, 1)
 		return Token{kind = .Assign, start = l.cursor, end = l.cursor}, true
 	}
 
 	if peek := lexer_peek(l, 1); peek == `"` {
 		start := l.cursor
 		lexer_advance(l, 1)
 		if !lexer_advance_until(l, `"`) do return t, false
 		end := l.cursor
 		defer lexer_advance(l, 1)
 		return Token{kind = .Double_Quote_String_Literal, start = start, end = end}, true
 	}
 
 	if peek := lexer_peek(l, 1); peek == `'` {
 		start := l.cursor
 		lexer_advance(l, 1)
 		if !lexer_advance_until(l, `'`) do return t, false
 		end := l.cursor
 		defer lexer_advance(l, 1)
 		return Token{kind = .Single_Quote_String_Literal, start = start, end = end}, true
 	}
 
 	return
 
 }
 
 lexer_expect :: proc(l: ^Lexer, kind: Token_Kind) -> (t: Token, ok: bool) {
 	t = lexer_next(l) or_return
 	return t, token_kind(t) == kind
 }
 
 lexer_advance :: proc(l: ^Lexer, step: u32 = 1) -> (ok: bool) {
 	l.cursor += step
 	return l.cursor < u32(len(l.source))
 }
 
 // lexer_advance_until advances the cursor until the source at the cursor
 // matches `target`. Returns true if a match was found, false on EOF.
 lexer_advance_until :: proc(l: ^Lexer, target: string) -> bool {
 	for {
 		if lexer_peek(l, u32(len(target))) == target {
 			return true
 		}
 		if !lexer_advance(l) {
 			return false
 		}
 	}
 }
 
 // lexer_advance_while_letters advances the cursor while the byte at cursor+1
 // is a letter, hyphen, or underscore. Returns true if stopped at a non-identifier
 // byte, false on EOF.
 lexer_advance_while_letters :: proc(l: ^Lexer) -> bool {
 	for {
 		b, ok := lexer_peek_byte(l, 1)
 		if !ok {
 			return false
 		}
 		if !(unicode.is_letter(rune(b)) || b == '-' || b == '_') {
 			return true
 		}
 		if !lexer_advance(l) {
 			return false
 		}
 	}
 }
 
 // lexer_advance_until_space advances the cursor until the byte at cursor+1
 // is whitespace. Returns true if stopped, false on EOF.
 lexer_advance_until_space :: proc(l: ^Lexer) -> bool {
 	for {
 		b, ok := lexer_peek_byte(l, 1)
 		if !ok {
 			return false
 		}
 		if unicode.is_space(rune(b)) {
 			return true
 		}
 		if !lexer_advance(l) {
 			return false
 		}
 	}
 }
 
 // lexer_advance_until_space_or advances the cursor until the byte at cursor+1
 // is whitespace or equals `or`. Returns true if stopped, false on EOF.
 lexer_advance_until_space_or :: proc(l: ^Lexer, or: byte) -> bool {
 	for {
 		b, ok := lexer_peek_byte(l, 1)
 		if !ok {
 			return false
 		}
 		if unicode.is_space(rune(b)) || b == or {
 			return true
 		}
 		if !lexer_advance(l) {
 			return false
 		}
 	}
 }
 
 lexer_peek :: proc(l: ^Lexer, step: u32 = 1) -> (p: string) {
 	start := l.cursor
 	end := l.cursor + step
 
 	if end > u32(len(l.source)) {
 		return ""
 	}
 
 	return l.source[start:end]
 }
 
 // lexer_peek_byte returns the byte at cursor+offset without advancing.
 lexer_peek_byte :: proc(l: ^Lexer, offset: u32 = 0) -> (b: byte, ok: bool) {
 	pos := l.cursor + offset
 	if pos >= u32(len(l.source)) {
 		return 0, false
 	}
 	return l.source[pos], true
 }
 
 // lexer_peek_token returns the next token without advancing the lexer.
 lexer_peek_token :: proc(l: ^Lexer) -> (t: Token, ok: bool) {
 	start := l.cursor
 	defer l.cursor = start
 	return lexer_next(l)
 }
 
 lexer_skip_space :: proc(l: ^Lexer) {
 	for {
 		b, ok := lexer_peek_byte(l)
 		if !ok {
 			return
 		}
 		if !unicode.is_space(rune(b)) {
 			return
 		}
 		if !lexer_advance(l) {
 			return
 		}
 	}
 }
 
 // token_kind returns the kind for the token.
 token_kind :: proc(t: Token) -> Token_Kind {
 	return t.kind
 }
 
 // token_lookup returns the substring corresponding to the token.
 // For atoms (end == start) this is the single byte at `start`;
 // for spans it is the inclusive range [start, end].
 token_lookup :: proc(t: Token, text: string) -> string {
 	return text[t.start:t.end + 1]
 }
 
 @(private = "file")
 check_tokens :: proc(t: ^testing.T, source: string, want: []Token, loc := #caller_location) {
 	defer free_all()
 
 	lexer: Lexer
 	lexer.source = source
 
 	got: [dynamic]Token
 
 	defer if testing.failed(t) {
 		log.debugf("got: %v", got)
 	}
 
 	for ii := 0; true; ii += 1 {
 		token, ok := lexer_next(&lexer)
 		append(&got, token)
 
 		log.debugf("%d/%d: token %v %v", ii + 1, len(want), ok, token, location = loc)
 		log.debugf("lexer: %v", lexer, location = loc)
 
 		if !ok {
 			if ii <= len(want) - 1 {
 				log.errorf(
 					"short output: got %d tokens; (%v), want %d %v",
 					ii,
 					token,
 					len(want),
 					want,
 					location = loc,
 				)
 			}
 			break
 		}
 
 		if ii >= len(want) {
 			log.errorf("got more tokens than expected: %v", token, location = loc)
 		} else {
 			testing.expect_value(t, token, want[ii], loc = loc)
 		}
 	}
 }
 
 @(test)
 test_lex_comment :: proc(t: ^testing.T) {
 	source := "<!-- comment -->"
 	want := []Token {
 		Token{kind = .Comment_Start, start = 0, end = 3},
 		Token{kind = .Raw_Text, start = 4, end = 12},
 		Token{kind = .Comment_End, start = 13, end = 15},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_comment_2 :: proc(t: ^testing.T) {
 	source := "<!--comment-->"
 	want := []Token {
 		Token{kind = .Comment_Start, start = 0, end = 3},
 		Token{kind = .Raw_Text, start = 4, end = 10},
 		Token{kind = .Comment_End, start = 11, end = 13},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_comment_3 :: proc(t: ^testing.T) {
 	source := "<!-- \ncomment\n -->"
 	want := []Token {
 		Token{kind = .Comment_Start, start = 0, end = 3},
 		Token{kind = .Raw_Text, start = 4, end = 14},
 		Token{kind = .Comment_End, start = 15, end = 17},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_doctype :: proc(t: ^testing.T) {
 	source := "<!DOCTYPE html>"
 	want := []Token{Token{kind = .Doctype, start = 0, end = 14}}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_exotic_doctype :: proc(t: ^testing.T) {
 	source := "<!DOCTYPE foobar>"
 	want := []Token{Token{kind = .Doctype, start = 0, end = 16}}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_self_closing_tag :: proc(t: ^testing.T) {
 	source := `<tag />`
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Raw_Text, start = 4, end = 4},
 		Token{kind = .Self_Closing_Tag_End, start = 5, end = 6},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_self_closing_tag_2 :: proc(t: ^testing.T) {
 	source := `<tag/>`
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Self_Closing_Tag_End, start = 4, end = 5},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_open_tag :: proc(t: ^testing.T) {
 	source := "<tag>"
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Tag_End, start = 4, end = 4},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_close_tag :: proc(t: ^testing.T) {
 	source := "</tag>"
 	want := []Token {
 		Token{kind = .Close_Tag_Start, start = 2, end = 4},
 		Token{kind = .Tag_End, start = 5, end = 5},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_tag_pair :: proc(t: ^testing.T) {
 	source := "<tag></tag>"
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Tag_End, start = 4, end = 4},
 		Token{kind = .Close_Tag_Start, start = 7, end = 9},
 		Token{kind = .Tag_End, start = 10, end = 10},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_tag_pair_with_comment :: proc(t: ^testing.T) {
 	source := "<tag><!--comment--></tag>"
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Tag_End, start = 4, end = 4},
 		Token{kind = .Comment_Start, start = 5, end = 8},
 		Token{kind = .Raw_Text, start = 9, end = 15},
 		Token{kind = .Comment_End, start = 16, end = 18},
 		Token{kind = .Close_Tag_Start, start = 21, end = 23},
 		Token{kind = .Tag_End, start = 24, end = 24},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_open_tag_value_attribute :: proc(t: ^testing.T) {
 	source := `<tag class=".style">`
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Raw_Text, start = 4, end = 9},
 		Token{kind = .Assign, start = 10, end = 10},
 		Token{kind = .Double_Quote_String_Literal, start = 11, end = 18},
 		Token{kind = .Tag_End, start = 19, end = 19},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_open_tag_naked_attribute :: proc(t: ^testing.T) {
 	source := `<tag class=".style" foobar>`
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Raw_Text, start = 4, end = 9},
 		Token{kind = .Assign, start = 10, end = 10},
 		Token{kind = .Double_Quote_String_Literal, start = 11, end = 18},
 		Token{kind = .Raw_Text, start = 19, end = 25},
 		Token{kind = .Tag_End, start = 26, end = 26},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_nested_tags :: proc(t: ^testing.T) {
 	source := `<tag><ul><li>one</li><li>two</li></ul></tag>`
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Tag_End, start = 4, end = 4},
 		Token{kind = .Open_Tag_Start, start = 6, end = 7},
 		Token{kind = .Tag_End, start = 8, end = 8},
 		Token{kind = .Open_Tag_Start, start = 10, end = 11},
 		Token{kind = .Tag_End, start = 12, end = 12},
 		Token{kind = .Raw_Text, start = 13, end = 15},
 		Token{kind = .Close_Tag_Start, start = 18, end = 19},
 		Token{kind = .Tag_End, start = 20, end = 20},
 		Token{kind = .Open_Tag_Start, start = 22, end = 23},
 		Token{kind = .Tag_End, start = 24, end = 24},
 		Token{kind = .Raw_Text, start = 25, end = 27},
 		Token{kind = .Close_Tag_Start, start = 30, end = 31},
 		Token{kind = .Tag_End, start = 32, end = 32},
 		Token{kind = .Close_Tag_Start, start = 35, end = 36},
 		Token{kind = .Tag_End, start = 37, end = 37},
 		Token{kind = .Close_Tag_Start, start = 40, end = 42},
 		Token{kind = .Tag_End, start = 43, end = 43},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_raw_text_less_than :: proc(t: ^testing.T) {
 	source := `<tag> 1 < 2 </tag>`
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Tag_End, start = 4, end = 4},
 		Token{kind = .Raw_Text, start = 5, end = 11},
 		Token{kind = .Close_Tag_Start, start = 14, end = 16},
 		Token{kind = .Tag_End, start = 17, end = 17},
 	}
 	check_tokens(t, source, want)
 }
 
 @(test)
 test_lex_invalid_tag :: proc(t: ^testing.T) {
 	source := `<tag> one <two three </tag>`
 	want := []Token {
 		Token{kind = .Open_Tag_Start, start = 1, end = 3},
 		Token{kind = .Tag_End, start = 4, end = 4},
 		Token{kind = .Raw_Text, start = 5, end = 9},
 		Token{kind = .Open_Tag_Start, start = 11, end = 13},
 		Token{kind = .Raw_Text, start = 14, end = 20},
 		Token{kind = .Close_Tag_Start, start = 23, end = 25},
 		Token{kind = .Tag_End, start = 26, end = 26},
 	}
 	check_tokens(t, source, want)
 }
 
 FUZZ_ENABLED :: #config(FUZZ, false)
 FUZZ_RUN_FAILED :: #config(FUZZ_RUN_FAILED, false)
 
 @(test)
 @(disabled = !FUZZ_ENABLED)
 test_lex_fuzz_lexer :: proc(t: ^testing.T) {
 	if !FUZZ_ENABLED do return
 
 	target: string
 
 	// cleanup saves the failed fuzz target to a file.
 	testing.cleanup(t, proc(userdata: rawptr) {
 			target: ^string = auto_cast userdata
 
 			if target == nil || target^ == "" {
 				return
 			}
 
 			buf: [64]byte
 
 			name := strconv.write_int(buf[:], i64(time.time_to_unix(time.now())), 10)
 
 			if err := os.make_directory("fuzzdata"); err != nil && err != .Exist {
 				log.errorf("preparing fuzzdata directory: %w", err)
 			}
 
 			file_path, _ := filepath.join([]string{"fuzzdata", name})
 
 			if err := os.write_entire_file_from_string(file_path, target^); err != nil {
 				log.errorf("writing to fuzz corpus file: %v", err)
 			}
 
 		}, &target)
 
 	log.info("fuzzing ...")
 
 	// Run the known failed fuzz corpus.
 	if FUZZ_RUN_FAILED {
 		dir, err := os.open("fuzzdata")
 		if err != nil {
 			log.errorf("opening fuzzdata directory: %v", err)
 		}
 
 		defer os.close(dir)
 
 		entries, entries_err := os.read_directory(dir, -1, context.allocator)
 		if entries_err != nil {
 			log.errorf("reading fuzzdata entries: %v", err)
 		}
 
 		defer {
 			for entry in entries {
 				os.file_info_delete(entry, context.allocator)
 			}
 			delete(entries)
 		}
 
 		for entry in entries {
 			input, input_err := os.read_entire_file_from_path(entry.fullpath, context.allocator)
 			if input_err != nil {
 				log.errorf("reading fuzzdata entry: %v", err)
 				continue
 			}
 
 			l: Lexer
 			l.source = string(input)
 
 			log.debugf("%q", l.source)
 			lexer_print_tokens(&l)
 		}
 
 		return
 	}
 
 	// Explore new randomized inputs.
 
 	rand.reset(t.seed)
 
 	// Define the pool characters.
 	// Whitespace and angle brackets are weighted higher.
 	character_set :: "abcdefghijklmnopqrstuvwxyz        <<<<<>>>>>/=\"!"
 
 	for ii := 1; true; ii += 1 {
 		source := random_string(character_set, rand.int_max(100))
 		defer strings.builder_destroy(&source)
 
 		src := strings.to_string(source)
 		target = src
 
 		l: Lexer
 		l.source = src
 
 		for {
 			_, ok := lexer_next(&l)
 			if !ok {
 				break
 			}
 		}
 	}
 }
 
 lexer_print_tokens :: proc(l: ^Lexer) {
 	for token in lexer_next(l) {
 		context.allocator = context.temp_allocator
 		defer free_all()
 		if token.start == token.end {
 			log.debug(token)
 			log.debugf("\t: %q \t(%v)", rune(l.source[token.start]), token)
 			log.debugf("\t: %v", l.source)
 			log.debugf("\t: %v^", strings.repeat(" ", int(token.start)))
 		} else {
 			log.debugf("\t: %q \t(%v)", l.source[token.start:token.end + 1], token)
 			log.debugf("\t: %v", l.source)
 			padding := strings.repeat(" ", int(token.start))
 			underline := ""
 			if token.end - token.start - 1 >= 0 {
 				underline = strings.repeat("_", int(token.end - token.start - 1))
 			}
 			log.debugf("\t: %v^%v^", padding, underline)
 		}
 	}
 }
 
 random_string :: proc(char_set: string, length: int) -> strings.Builder {
 	b: strings.Builder
 
 	for ii in 0 ..< length {
 		strings.write_byte(&b, char_set[rand.int_max(len(char_set))])
 	}
 
 	return b
 }