diff options
Diffstat (limited to 'src')
26 files changed, 2661 insertions, 0 deletions
diff --git a/src/analyze.rs b/src/analyze.rs new file mode 100644 index 0000000..7debb0d --- /dev/null +++ b/src/analyze.rs @@ -0,0 +1,383 @@ +use std::{ + collections::HashMap, + sync::atomic::{AtomicUsize, Ordering::Relaxed}, +}; + +use bumpalo::Bump; + +use crate::{ + parse::{Attribute, Document, Element, Node}, + tokenize::{AttributeTokenType, TokenType}, +}; + +static NEXT_ID: AtomicUsize = AtomicUsize::new(0); + +pub struct SymbolTableSet<'a> { + symbol_tables: HashMap<SymbolTableId, ScopedSymbolTable<'a>>, +} + +pub struct ScopedSymbolTable<'a> { + pub modules: HashMap<ModuleSymbolId, ModuleSymbol<'a>>, + pub constants: HashMap<ConstantSymbolId, ConstantSymbol<'a>>, + pub heads: HashMap<HeadSymbolId, HeadSymbol<'a>>, + pub bodies: HashMap<HeadSymbolId, HeadSymbol<'a>>, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct SymbolTableId(pub usize); +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct ModuleSymbolId(pub usize); +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct ConstantSymbolId(pub usize); +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct HeadSymbolId(pub usize); + +pub struct ModuleSymbol<'a> { + pub id: ModuleSymbolId, + pub name: Option<&'a str>, + pub symbol_table: Option<&'a ScopedSymbolTable<'a>>, + pub definition_site: Option<Element<'a>>, +} + +pub struct ConstantSymbol<'a> { + pub id: ConstantSymbolId, + pub name: Option<&'a str>, + pub ty: Option<ConstantType<'a>>, + pub value: Option<ConstantExpression<'a>>, + pub definition_site: Option<Element<'a>>, +} + +pub struct HeadSymbol<'a> { + pub id: HeadSymbolId, + pub contents: Option<ConstantSymbolId>, + pub definition_site: Option<Element<'a>>, +} + +pub enum ConstantType<'a> { + String, + Block { + direct_children_tags: Option<&'a [&'a str]>, + transitive_children_tags: Option<&'a [&'a str]>, + }, +} + +pub enum ConstantValue<'a> { + String(&'a str), +} + +pub enum ConstantExpression<'a> { + Name(&'a str), + Value(ConstantValue<'a>), + Fragment(&'a [ConstantSymbolId]), + Block { + tag_name_lowercase: &'a str, + attributes: HashMap<&'a str, Option<ConstantSymbolId>>, + child: ConstantSymbolId, + }, +} + +fn next_id() -> usize { + NEXT_ID.fetch_add(1, Relaxed) +} + +fn element_attributes<'a>( + symbol_table: &mut ScopedSymbolTable<'a>, + element: &'a Element<'a>, +) -> HashMap<&'a str, Option<ConstantSymbolId>> { + let mut attributes = HashMap::new(); + for attribute in element.attributes { + let Some(name) = attribute.name_lowercase() else { + continue; + }; + let value = attribute.value_str(); + + let id = value.map(|value| { + let id = ConstantSymbolId(next_id()); + symbol_table.constants.insert( + id, + ConstantSymbol { + id, + name: None, + ty: Some(ConstantType::String), + value: Some(ConstantExpression::Value(ConstantValue::String(value))), + definition_site: None, + }, + ); + id + }); + attributes.insert(name, id); + } + attributes +} + +fn fragment<'a>( + arena: &'a Bump, + symbol_table: &mut ScopedSymbolTable<'a>, + children: &'a [Node<'a>], +) -> ConstantExpression<'a> { + let children = arena.alloc_slice_copy( + &children + .iter() + .filter_map(|node| node_to_constant(arena, symbol_table, node)) + .collect::<Box<_>>(), + ); + ConstantExpression::Fragment(children) +} + +fn node_to_constant<'a>( + arena: &'a Bump, + symbol_table: &mut ScopedSymbolTable<'a>, + node: &'a Node<'a>, +) -> Option<ConstantSymbolId> { + match node { + Node::CharacterData(token) => { + let id = ConstantSymbolId(next_id()); + let TokenType::Data(value) = token.ty else { + return None; + }; + symbol_table.constants.insert( + id, + ConstantSymbol { + id, + name: None, + ty: Some(ConstantType::String), + value: Some(ConstantExpression::Value(ConstantValue::String(value))), + definition_site: None, + }, + ); + Some(id) + } + Node::Element(element) if element.tag_name_lowercase() == Some("kuht-var") => { + let id = ConstantSymbolId(next_id()); + let name = element + .attribute("name") + .and_then(|attribute| attribute.value_str())?; + let fragment_id = ConstantSymbolId(next_id()); + let fragment = fragment(arena, symbol_table, element.children); + symbol_table.constants.insert( + fragment_id, + ConstantSymbol { + id, + name: None, + // TODO fragment type + ty: None, + value: Some(fragment), + definition_site: None, + }, + ); + + symbol_table.constants.insert( + id, + ConstantSymbol { + id, + name: None, + // TODO determine this type + ty: None, + value: Some(ConstantExpression::Name(name)), + // TODO we need some way to get where these come from + definition_site: None, + }, + ); + Some(id) + } + Node::Element(element) => { + let id = ConstantSymbolId(next_id()); + let tag_name_lowercase = element.tag_name_lowercase()?; + let attributes = element_attributes(symbol_table, element); + let fragment_id = ConstantSymbolId(next_id()); + let fragment = fragment(arena, symbol_table, element.children); + symbol_table.constants.insert( + fragment_id, + ConstantSymbol { + id, + name: None, + // TODO fragment type + ty: None, + value: Some(fragment), + definition_site: None, + }, + ); + + symbol_table.constants.insert( + id, + ConstantSymbol { + id, + name: None, + // TODO type here + ty: None, + value: Some(ConstantExpression::Block { + tag_name_lowercase, + attributes, + child: fragment_id, + }), + definition_site: None, + }, + ); + Some(id) + } + Node::StrayEndTag(_) | Node::Comment(_) => None, + } +} + +// TODO replace <import> with <module "base" file="../base.kuht" /> +// TODO support builtin modules +// TODO also support <import "foo::bar" as="baz" /> +fn add_import<'a>(symbol_table: &mut ScopedSymbolTable<'a>, element: &Element<'a>) { + let id = ModuleSymbolId(next_id()); + let name = if let Some(Attribute::PositionalArgument { value }) = element.attributes.first() + && let AttributeTokenType::String { value, .. } = value.ty + { + Some(value) + } else { + None + }; + let definition_site = Some(*element); + + symbol_table.modules.insert( + id, + ModuleSymbol { + id, + name, + symbol_table: None, + definition_site, + }, + ); +} + +fn add_constant<'a>(symbol_table: &mut ScopedSymbolTable<'a>, element: &'a Element<'a>) { + let id = ConstantSymbolId(next_id()); + let name = element.attribute("name").and_then(|attr| attr.value_str()); + let value = element.attribute("value").and_then(|attr| attr.value_str()); + symbol_table.constants.insert( + id, + ConstantSymbol { + id, + name, + ty: Some(ConstantType::String), + value: value.map(|value| ConstantExpression::Value(ConstantValue::String(value))), + definition_site: Some(*element), + }, + ); +} + +fn add_block<'a>( + arena: &'a Bump, + symbol_table: &mut ScopedSymbolTable<'a>, + element: &'a Element<'a>, +) { + let id = ConstantSymbolId(next_id()); + let name = element.attribute("name").and_then(|attr| attr.value_str()); + let fragment = fragment(arena, symbol_table, element.children); + symbol_table.constants.insert( + id, + ConstantSymbol { + id, + name, + // fill this in + ty: None, + value: Some(fragment), + definition_site: Some(*element), + }, + ); +} + +fn add_head<'a>( + arena: &'a Bump, + symbol_table: &mut ScopedSymbolTable<'a>, + element: &'a Element<'a>, +) { + let id = HeadSymbolId(next_id()); + let fragment_id = ConstantSymbolId(next_id()); + let fragment = fragment(arena, symbol_table, element.children); + symbol_table.constants.insert( + fragment_id, + ConstantSymbol { + id: fragment_id, + name: None, + ty: None, + value: Some(fragment), + definition_site: None, + }, + ); + symbol_table.heads.insert( + id, + HeadSymbol { + id, + contents: Some(fragment_id), + definition_site: Some(*element), + }, + ); +} + +fn add_body<'a>( + arena: &'a Bump, + symbol_table: &mut ScopedSymbolTable<'a>, + element: &'a Element<'a>, +) { + let id = HeadSymbolId(next_id()); + let fragment_id = ConstantSymbolId(next_id()); + let fragment = fragment(arena, symbol_table, element.children); + symbol_table.constants.insert( + fragment_id, + ConstantSymbol { + id: fragment_id, + name: None, + ty: None, + value: Some(fragment), + definition_site: None, + }, + ); + symbol_table.bodies.insert( + id, + HeadSymbol { + id, + contents: Some(fragment_id), + definition_site: Some(*element), + }, + ); +} + +pub fn symbol_table<'a>(arena: &'a Bump, document: Document<'a>) -> ScopedSymbolTable<'a> { + let mut symbol_table = ScopedSymbolTable { + modules: HashMap::new(), + constants: HashMap::new(), + heads: HashMap::new(), + bodies: HashMap::new(), + }; + + for node in document.children { + match node { + Node::Element(element) if element.tag_name_lowercase() == Some("import") => { + add_import(&mut symbol_table, element) + } + Node::Element(element) if element.tag_name_lowercase() == Some("const") => { + add_constant(&mut symbol_table, element) + } + Node::Element(element) if element.tag_name_lowercase() == Some("block") => { + add_block(arena, &mut symbol_table, element) + } + Node::Element(element) if element.tag_name_lowercase() == Some("head") => { + add_head(arena, &mut symbol_table, element) + } + Node::Element(element) if element.tag_name_lowercase() == Some("body") => { + add_body(arena, &mut symbol_table, element) + } + _ => {} + } + } + + symbol_table +} + +impl<'a> SymbolTableSet<'a> { + pub fn new() -> Self { + Self { + symbol_tables: HashMap::new(), + } + } + + pub fn add_document(&mut self, arena: &'a Bump, document: Document<'a>) { + self.symbol_tables + .insert(SymbolTableId(next_id()), symbol_table(arena, document)); + } +} diff --git a/src/compile.rs b/src/compile.rs new file mode 100644 index 0000000..ccbf6f0 --- /dev/null +++ b/src/compile.rs @@ -0,0 +1,140 @@ +use html_escape::{encode_double_quoted_attribute, encode_single_quoted_attribute}; + +use crate::analyze::{ConstantExpression, ConstantSymbolId, ConstantValue, ScopedSymbolTable}; + +fn symbol_table_from_path<'a>( + symbol_table: &'a ScopedSymbolTable<'a>, + path: &'a str, +) -> Option<&'a ScopedSymbolTable<'a>> { + let mut symbol_table = symbol_table; + for component in path.split("::") { + if let Some(module) = symbol_table + .modules + .values() + .find(|module| module.name == Some(component)) + .and_then(|module| module.symbol_table) + { + symbol_table = module; + } else { + return None; + } + } + + Some(symbol_table) +} + +fn compile_attribute_value<'a>( + buffer: &mut String, + symbol_table: &'a ScopedSymbolTable<'a>, + name: &'a str, + value: Option<ConstantSymbolId>, +) { + buffer.push(' '); + buffer.push_str(name); + let Some(value) = value else { + return; + }; + + buffer.push('='); + + let mut new_buffer = String::new(); + compile_constant(&mut new_buffer, symbol_table, value); + + let use_double_quotes = !new_buffer.contains('"') || new_buffer.contains('\''); + let delimiter = if !use_double_quotes { '\'' } else { '"' }; + let value = if use_double_quotes { + encode_double_quoted_attribute(&new_buffer) + } else { + encode_single_quoted_attribute(&new_buffer) + }; + + buffer.push(delimiter); + buffer.push_str(&value); + buffer.push(delimiter); +} + +fn compile_constant<'a>( + buffer: &mut String, + symbol_table: &'a ScopedSymbolTable<'a>, + id: ConstantSymbolId, +) { + let Some(constant) = symbol_table.constants.get(&id) else { + return; + }; + let Some(expression) = &constant.value else { + return; + }; + match expression { + ConstantExpression::Value(value) => match value { + ConstantValue::String(value) => buffer.push_str(value), + }, + ConstantExpression::Name(name) => { + let mut name = *name; + let mut symbol_table = symbol_table; + if let Some((path, item)) = name.rsplit_once("::") + && let Some(module) = symbol_table_from_path(symbol_table, path) + { + name = item; + symbol_table = module; + } + if let Some(id) = symbol_table + .constants + .values() + .find_map(|value| (value.name == Some(name)).then_some(value.id)) + { + compile_constant(buffer, symbol_table, id); + } + } + ConstantExpression::Fragment(constant_symbol_ids) => { + for constant in *constant_symbol_ids { + compile_constant(buffer, symbol_table, *constant); + } + } + ConstantExpression::Block { + tag_name_lowercase, + attributes, + child, + } => { + buffer.push('<'); + buffer.push_str(tag_name_lowercase); + for (name, value) in attributes { + compile_attribute_value(buffer, symbol_table, name, *value); + } + buffer.push('>'); + compile_constant(buffer, symbol_table, *child); + buffer.push_str("</"); + buffer.push_str(tag_name_lowercase); + buffer.push('>'); + } + } +} + +fn compile_head<'a>(buffer: &mut String, symbol_tables: &[ScopedSymbolTable<'a>]) { + for symbol_table in symbol_tables { + for head in symbol_table.heads.values().filter_map(|head| head.contents) { + compile_constant(buffer, symbol_table, head); + } + } +} + +fn compile_body<'a>(buffer: &mut String, symbol_tables: &[ScopedSymbolTable<'a>]) { + for symbol_table in symbol_tables { + for body in symbol_table + .bodies + .values() + .filter_map(|body| body.contents) + { + compile_constant(buffer, symbol_table, body); + } + } +} + +pub fn compile<'a>(symbol_tables: &[ScopedSymbolTable<'a>]) -> Box<str> { + let mut buffer = String::from("<!DOCTYPE html><html lang=\"en\"><head>"); + compile_head(&mut buffer, symbol_tables); + buffer.push_str("</head><body>"); + compile_body(&mut buffer, symbol_tables); + buffer.push_str("</body></html>"); + + buffer.into_boxed_str() +} diff --git a/src/diagnostics.rs b/src/diagnostics.rs new file mode 100644 index 0000000..514818a --- /dev/null +++ b/src/diagnostics.rs @@ -0,0 +1,217 @@ +use miette::{Diagnostic, Error}; +use thiserror::Error; + +use crate::{ + parse::{Attribute, Document, Element, Node}, + tokenize::{AttributeToken, Token, TokenType}, +}; + +mod duplicate_attribute_names; +mod empty_tag_name; +mod end_tag_with_attributes; +mod forbidden_top_level_tag; +mod html_tag; +mod image_tag; +mod non_alphabetic_attribute_name; +mod non_alphabetic_tag_name; +mod non_self_closing_void_tag; +mod non_void_self_closing_tag; +mod self_closing_end_tag; +mod stray_end_tag; +mod stray_equal_sign; +mod too_many_equal_signs; +mod top_level_character_data; +mod unclosed_start_tag; +mod unterminated_comment; +mod unterminated_tag; + +const VOID_TAGS: &[&str] = &[ + "area", "base", "br", "col", "embed", "hr", "img", "input", "link", "meta", "param", "source", + "track", "wbr", +]; +const ALLOWED_TOP_LEVEL_TAGS: &[&str] = &["import", "const", "block", "head", "body"]; + +pub struct DiagnosticsContext { + source_code: &'static str, +} + +trait TokenDiagnostic: Sized + Send + Sync + 'static { + fn handle_token(_: &Token<'_>) -> Option<Self> { + None + } + + fn handle_attribute_token(_: &AttributeToken<'_>) -> Option<Self> { + None + } +} + +trait AstDiagnostic: Sized + Send + Sync + 'static { + fn handle_document(_: &Document<'_>) -> Option<Self> { + None + } + + fn handle_node(_: &Node<'_>) -> Option<Self> { + None + } + + fn handle_element(_: &Element<'_>) -> Option<Self> { + None + } + + fn handle_attribute(_: &Attribute<'_>) -> Option<Self> { + None + } +} + +fn maybe_print_diagnostic<D: Diagnostic + Send + Sync + 'static>( + ctx: &DiagnosticsContext, + diagnostic: Option<D>, +) { + if let Some(diagnostic) = diagnostic { + eprintln!( + "{}", + Error::new(diagnostic).with_source_code(ctx.source_code) + ); + } +} + +#[derive(Debug, Error, Diagnostic)] +#[error("This file is not valid UTF-8")] +#[diagnostic(code(NonUtf8), severity(Error))] +struct NonUtf8; + +#[derive(Debug, Error, Diagnostic)] +#[error("Forbidden NUL character found")] +#[diagnostic(code(NonUtf8), severity(Error))] +struct NulCharacter { + #[label("Forbidden NUL byte found here")] + location: usize, +} + +#[derive(Debug, Error, Diagnostic)] +#[error("Forbidden control character found")] +#[diagnostic(code(NonUtf8), severity(Error))] +struct ControlCharacter { + #[label("Control character found")] + location: usize, +} + +pub fn run_character_diagnostics(source: &'static [u8]) -> Option<&'static str> { + let Ok(source) = str::from_utf8(source) else { + eprintln!("{}", Error::new(NonUtf8)); + return None; + }; + let ctx = DiagnosticsContext { + source_code: source, + }; + for (i, char) in source.char_indices() { + maybe_print_diagnostic(&ctx, (char == '\0').then_some(NulCharacter { location: i })); + maybe_print_diagnostic( + &ctx, + (char.is_control() && !char.is_ascii_whitespace()) + .then_some(ControlCharacter { location: i }), + ); + } + + Some(source) +} + +fn run_token_diagnostic<D: Diagnostic + TokenDiagnostic>( + ctx: &DiagnosticsContext, + tokens: &[Token<'_>], +) { + for token in tokens { + maybe_print_diagnostic(ctx, D::handle_token(token)); + + let TokenType::Tag { + attribute_tokens, .. + } = token.ty + else { + continue; + }; + + for token in attribute_tokens { + maybe_print_diagnostic(ctx, D::handle_attribute_token(token)); + } + } +} + +fn run_ast_diagnostic<D: AstDiagnostic + Diagnostic>( + ctx: &DiagnosticsContext, + document: &Document<'_>, +) { + maybe_print_diagnostic(ctx, D::handle_document(document)); + for node in document.children { + maybe_print_diagnostic(ctx, D::handle_node(node)); + + let Node::Element(element) = node else { + continue; + }; + maybe_print_diagnostic(ctx, D::handle_element(element)); + + for attribute in element.attributes { + maybe_print_diagnostic(ctx, D::handle_attribute(attribute)); + } + } +} + +pub fn run_token_diagnostics(ctx: &DiagnosticsContext, tokens: &[Token<'_>]) { + run_token_diagnostic::<non_void_self_closing_tag::NonVoidSelfClosingTag>(ctx, tokens); + run_token_diagnostic::<non_self_closing_void_tag::NonSelfClosingVoidTag>(ctx, tokens); + run_token_diagnostic::<end_tag_with_attributes::EndTagWithAttributes>(ctx, tokens); + run_token_diagnostic::<self_closing_end_tag::SelfClosingEndTag>(ctx, tokens); + run_token_diagnostic::<non_alphabetic_tag_name::NonAlphabeticTagName>(ctx, tokens); + run_token_diagnostic::<empty_tag_name::EmptyTagName>(ctx, tokens); + run_token_diagnostic::<unterminated_tag::UnterminatedTag>(ctx, tokens); + run_token_diagnostic::<unterminated_comment::UnterminatedComment>(ctx, tokens); + run_token_diagnostic::<non_alphabetic_attribute_name::NonAlphabeticAttributeName>(ctx, tokens); + // TODO invalid character reference +} + +pub fn run_ast_diagnostics(ctx: &DiagnosticsContext, document: &Document<'_>) { + run_ast_diagnostic::<stray_equal_sign::StrayEqualSign>(ctx, document); + run_ast_diagnostic::<too_many_equal_signs::TooManyEqualSigns>(ctx, document); + run_ast_diagnostic::<duplicate_attribute_names::DuplicateAttributeNames>(ctx, document); + run_ast_diagnostic::<top_level_character_data::TopLevelCharacterData>(ctx, document); + run_ast_diagnostic::<forbidden_top_level_tag::ForbiddenTopLevelTag>(ctx, document); + run_ast_diagnostic::<stray_end_tag::StrayEndTag>(ctx, document); + run_ast_diagnostic::<unclosed_start_tag::UnclosedStartTag>(ctx, document); + run_ast_diagnostic::<html_tag::HtmlTag>(ctx, document); + run_ast_diagnostic::<image_tag::ImageTag>(ctx, document); + // TODO invalid <kuht-var /> + // TODO invalid <import /> + // TODO invalid <const /> + // TODO invalid <block /> + // TODO deprecated tag + // TODO deprecated tag attribute + // + // TODO forbidden tag in noscript + // TODO head tag outside head + // TODO html tag in body + // TODO heading inside heading + // TODO form inside form + // TODO button inside button + // TODO anchor inside anchor + // TODO head inside body + // TODO caption, col, colgroup, tbody, tfoot, thead, tr outside table + // TODO table inside table + // TODO non-hidden input inside table + // TODO form inside table + // TODO body inside body + // TODO col, colgroup, tbody, tfoot, thead, tr inside caption + // TODO th, td outside tr + // TODO caption, col, colgroup, tr in tbody + // TODO caption, col, colgroup, tbody, td, tfoot, th, thead, tr inside table cell + // TODO select inside select + // TODO input, keygen, textarea inside select + // TODO caption, table, tbody, tfoot, thread, tr, td, th inside select + // + // TODO anchor with invalid href + // TODO dt or dd outside dl + // TODO li outside ul, ol, menu + // TODO invalid dl, ul, menu + // TODO invalid attribute values (see microsyntaxes) + // TODO aria tags don't match tag semantics + // TODO empty or missing image src + // TODO missing alt text for image (unless inside figure with caption, or has title, or meta name = "generator") +} diff --git a/src/diagnostics/duplicate_attribute_names.rs b/src/diagnostics/duplicate_attribute_names.rs new file mode 100644 index 0000000..542d8ec --- /dev/null +++ b/src/diagnostics/duplicate_attribute_names.rs @@ -0,0 +1,41 @@ +use std::collections::HashMap; + +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::AstDiagnostic, + parse::{Attribute, Element}, + tokenize::Span, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Multiple attributes have the same name")] +#[diagnostic(code(DuplicateAttributeNames), severity(Error))] +pub struct DuplicateAttributeNames { + #[label(collection)] + duplicates: Vec<Span>, +} + +impl AstDiagnostic for DuplicateAttributeNames { + fn handle_element(element: &Element<'_>) -> Option<Self> { + let mut seen_attributes = HashMap::<&str, Attribute<'_>>::new(); + for attribute in element.attributes { + let Some(name) = attribute.name_lowercase() else { + continue; + }; + if let Some(duplicate) = seen_attributes.get(name) { + return Some(Self { + duplicates: vec![ + duplicate.name_token().expect("a named attribute").span, + attribute.name_token().expect("a named attribute").span, + ], + }); + } + + seen_attributes.insert(name, *attribute); + } + + None + } +} diff --git a/src/diagnostics/empty_tag_name.rs b/src/diagnostics/empty_tag_name.rs new file mode 100644 index 0000000..e8fdb07 --- /dev/null +++ b/src/diagnostics/empty_tag_name.rs @@ -0,0 +1,32 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::TokenDiagnostic, + tokenize::{Span, Token, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Tag names must be alphabetic")] +#[diagnostic(code(EmptyTagName), severity(Error))] +pub struct EmptyTagName { + #[label(primary, "all tags must have a name")] + tag: Span, +} + +impl TokenDiagnostic for EmptyTagName { + fn handle_token(token: &Token<'_>) -> Option<Self> { + let TokenType::Tag { + lowercase_tag_name, .. + } = token.ty + else { + return None; + }; + + if !lowercase_tag_name.is_empty() { + return None; + } + + Some(Self { tag: token.span }) + } +} diff --git a/src/diagnostics/end_tag_with_attributes.rs b/src/diagnostics/end_tag_with_attributes.rs new file mode 100644 index 0000000..0631fb6 --- /dev/null +++ b/src/diagnostics/end_tag_with_attributes.rs @@ -0,0 +1,34 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::TokenDiagnostic, + tokenize::{Span, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("End tags cannot have attributes")] +#[diagnostic(code(EndTagWithAttributes), severity(Error))] +pub struct EndTagWithAttributes { + #[label(primary, "attributes are invalid for end tags")] + tag: Span, +} + +impl TokenDiagnostic for EndTagWithAttributes { + fn handle_token(token: &crate::tokenize::Token<'_>) -> Option<Self> { + let TokenType::Tag { + is_end, + attribute_tokens, + .. + } = token.ty + else { + return None; + }; + + if !is_end || attribute_tokens.is_empty() { + return None; + } + + Some(Self { tag: token.span }) + } +} diff --git a/src/diagnostics/forbidden_top_level_tag.rs b/src/diagnostics/forbidden_top_level_tag.rs new file mode 100644 index 0000000..8b5301e --- /dev/null +++ b/src/diagnostics/forbidden_top_level_tag.rs @@ -0,0 +1,42 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::{ALLOWED_TOP_LEVEL_TAGS, AstDiagnostic}, + parse::Node, + tokenize::Span, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Forbidden top-level tag is present")] +#[help("Permitted top level tags are: import, const, block, head, and body")] +#[diagnostic(code(TopLevelCharacterData), severity(Error))] +pub struct ForbiddenTopLevelTag { + #[label(collection, "These tags are not permitted at the top level in kuht")] + nodes: Vec<Span>, +} + +impl AstDiagnostic for ForbiddenTopLevelTag { + fn handle_document(document: &crate::parse::Document<'_>) -> Option<Self> { + let bad_nodes = document + .children + .iter() + .filter_map(|node| { + if let Node::Element(element) = node + && let Some(tag_name) = element.tag_name_lowercase() + && !ALLOWED_TOP_LEVEL_TAGS.contains(&tag_name) + { + Some(element.start_tag.span) + } else { + None + } + }) + .collect::<Vec<_>>(); + + if bad_nodes.is_empty() { + return None; + } + + Some(Self { nodes: bad_nodes }) + } +} diff --git a/src/diagnostics/html_tag.rs b/src/diagnostics/html_tag.rs new file mode 100644 index 0000000..8cf7eb0 --- /dev/null +++ b/src/diagnostics/html_tag.rs @@ -0,0 +1,34 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::AstDiagnostic, + tokenize::{Span, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("html tags is not allowed in kuht")] +#[diagnostic(code(HtmlTag), severity(Error))] +pub struct HtmlTag { + #[label(primary, "invalid html tag")] + tag: Span, +} + +impl AstDiagnostic for HtmlTag { + fn handle_element(element: &crate::parse::Element<'_>) -> Option<Self> { + let TokenType::Tag { + lowercase_tag_name, .. + } = element.start_tag.ty + else { + return None; + }; + + if lowercase_tag_name != "html" { + return None; + } + + Some(Self { + tag: element.start_tag.span, + }) + } +} diff --git a/src/diagnostics/image_tag.rs b/src/diagnostics/image_tag.rs new file mode 100644 index 0000000..dc5a633 --- /dev/null +++ b/src/diagnostics/image_tag.rs @@ -0,0 +1,34 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::AstDiagnostic, + tokenize::{Span, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("image tags is not allowed in kuht")] +#[diagnostic(code(ImageTag), severity(Error))] +pub struct ImageTag { + #[label(primary, "invalid image tag")] + tag: Span, +} + +impl AstDiagnostic for ImageTag { + fn handle_element(element: &crate::parse::Element<'_>) -> Option<Self> { + let TokenType::Tag { + lowercase_tag_name, .. + } = element.start_tag.ty + else { + return None; + }; + + if lowercase_tag_name != "image" { + return None; + } + + Some(Self { + tag: element.start_tag.span, + }) + } +} diff --git a/src/diagnostics/non_alphabetic_attribute_name.rs b/src/diagnostics/non_alphabetic_attribute_name.rs new file mode 100644 index 0000000..1cb31d9 --- /dev/null +++ b/src/diagnostics/non_alphabetic_attribute_name.rs @@ -0,0 +1,37 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::TokenDiagnostic, + tokenize::{AttributeToken, AttributeTokenType, Span}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Attribute names must be alphabetic")] +#[diagnostic(code(NonAlphabeticAttributeName), severity(Error))] +pub struct NonAlphabeticAttributeName { + #[label( + primary, + "attribute names must only contain uppercase and lowercase letters" + )] + attribute_name: Span, +} + +impl TokenDiagnostic for NonAlphabeticAttributeName { + fn handle_attribute_token(token: &AttributeToken<'_>) -> Option<Self> { + let AttributeTokenType::Identifier { lowercase_name, .. } = token.ty else { + return None; + }; + + if lowercase_name + .chars() + .all(|char| char.is_ascii_alphabetic()) + { + return None; + } + + Some(Self { + attribute_name: token.span, + }) + } +} diff --git a/src/diagnostics/non_alphabetic_tag_name.rs b/src/diagnostics/non_alphabetic_tag_name.rs new file mode 100644 index 0000000..b36cb75 --- /dev/null +++ b/src/diagnostics/non_alphabetic_tag_name.rs @@ -0,0 +1,38 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::TokenDiagnostic, + tokenize::{Span, Token, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Tag names must be alphabetic")] +#[diagnostic(code(NonAlphabeticTagName), severity(Error))] +pub struct NonAlphabeticTagName { + #[label(primary, "tag names must only contain uppercase and lowercase letters")] + tag: Span, +} + +impl TokenDiagnostic for NonAlphabeticTagName { + fn handle_token(token: &Token<'_>) -> Option<Self> { + let TokenType::Tag { + is_end, + lowercase_tag_name, + .. + } = token.ty + else { + return None; + }; + + if is_end + || lowercase_tag_name + .chars() + .all(|char| char.is_ascii_alphabetic()) + { + return None; + } + + Some(Self { tag: token.span }) + } +} diff --git a/src/diagnostics/non_self_closing_void_tag.rs b/src/diagnostics/non_self_closing_void_tag.rs new file mode 100644 index 0000000..bfff266 --- /dev/null +++ b/src/diagnostics/non_self_closing_void_tag.rs @@ -0,0 +1,35 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::{TokenDiagnostic, VOID_TAGS}, + tokenize::{Span, Token, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Void tags must be self-closed")] +#[diagnostic(code(NonSelfClosingVoidTag), severity(Error))] +pub struct NonSelfClosingVoidTag { + #[label(primary, "this is a void tag, which must be self-closed")] + tag: Span, +} + +impl TokenDiagnostic for NonSelfClosingVoidTag { + fn handle_token(token: &Token<'_>) -> Option<Self> { + let TokenType::Tag { + is_end, + lowercase_tag_name, + self_closing, + .. + } = token.ty + else { + return None; + }; + + if is_end || self_closing || !VOID_TAGS.contains(&lowercase_tag_name) { + return None; + } + + Some(Self { tag: token.span }) + } +} diff --git a/src/diagnostics/non_void_self_closing_tag.rs b/src/diagnostics/non_void_self_closing_tag.rs new file mode 100644 index 0000000..8a64be1 --- /dev/null +++ b/src/diagnostics/non_void_self_closing_tag.rs @@ -0,0 +1,35 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::{TokenDiagnostic, VOID_TAGS}, + tokenize::{Span, Token, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Non-void tags must not be self-closed")] +#[diagnostic(code(NonVoidSelfClosingTag), severity(Error))] +pub struct NonVoidSelfClosingTag { + #[label(primary, "this is not a void tag and thus cannot be self-closed")] + tag: Span, +} + +impl TokenDiagnostic for NonVoidSelfClosingTag { + fn handle_token(token: &Token<'_>) -> Option<Self> { + let TokenType::Tag { + is_end, + lowercase_tag_name, + self_closing, + .. + } = token.ty + else { + return None; + }; + + if is_end || !self_closing || VOID_TAGS.contains(&lowercase_tag_name) { + return None; + } + + Some(Self { tag: token.span }) + } +} diff --git a/src/diagnostics/self_closing_end_tag.rs b/src/diagnostics/self_closing_end_tag.rs new file mode 100644 index 0000000..5b5a680 --- /dev/null +++ b/src/diagnostics/self_closing_end_tag.rs @@ -0,0 +1,37 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::TokenDiagnostic, + tokenize::{Span, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("End tags cannot self-close")] +#[diagnostic(code(SelfClosingEndTag), severity(Error))] +pub struct SelfClosingEndTag { + #[label( + primary, + "this tag has a slash at both the beginning and the end, which is not allowed" + )] + tag: Span, +} + +impl TokenDiagnostic for SelfClosingEndTag { + fn handle_token(token: &crate::tokenize::Token<'_>) -> Option<Self> { + let TokenType::Tag { + is_end, + self_closing, + .. + } = token.ty + else { + return None; + }; + + if !is_end || !self_closing { + return None; + } + + Some(Self { tag: token.span }) + } +} diff --git a/src/diagnostics/stray_end_tag.rs b/src/diagnostics/stray_end_tag.rs new file mode 100644 index 0000000..fa4ca07 --- /dev/null +++ b/src/diagnostics/stray_end_tag.rs @@ -0,0 +1,22 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{diagnostics::AstDiagnostic, parse::Node, tokenize::Span}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Stray end tag")] +#[diagnostic(code(StrayEndTag), severity(Error))] +pub struct StrayEndTag { + #[label(primary)] + token: Span, +} + +impl AstDiagnostic for StrayEndTag { + fn handle_node(node: &Node<'_>) -> Option<Self> { + let Node::StrayEndTag(token) = node else { + return None; + }; + + Some(Self { token: token.span }) + } +} diff --git a/src/diagnostics/stray_equal_sign.rs b/src/diagnostics/stray_equal_sign.rs new file mode 100644 index 0000000..29674da --- /dev/null +++ b/src/diagnostics/stray_equal_sign.rs @@ -0,0 +1,22 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{diagnostics::AstDiagnostic, parse::Attribute, tokenize::Span}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Stray equal sign found not attached to any attributes")] +#[diagnostic(code(StrayEqualSign), severity(Error))] +pub struct StrayEqualSign { + #[label(primary, "An equal sign is not a valid attribute")] + token: Span, +} + +impl AstDiagnostic for StrayEqualSign { + fn handle_attribute(attribute: &crate::parse::Attribute<'_>) -> Option<Self> { + let Attribute::StrayEqualSign(token) = attribute else { + return None; + }; + + Some(Self { token: token.span }) + } +} diff --git a/src/diagnostics/too_many_equal_signs.rs b/src/diagnostics/too_many_equal_signs.rs new file mode 100644 index 0000000..b20cb83 --- /dev/null +++ b/src/diagnostics/too_many_equal_signs.rs @@ -0,0 +1,35 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{diagnostics::AstDiagnostic, parse::Attribute, tokenize::Span}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Multiple equal signs in a row")] +#[diagnostic(code(TooManyEqualSigns), severity(Error))] +pub struct TooManyEqualSigns { + #[label(primary, "only one equal sign should be present")] + token: Span, +} + +impl AstDiagnostic for TooManyEqualSigns { + fn handle_attribute(attribute: &crate::parse::Attribute<'_>) -> Option<Self> { + let Attribute::NamedArgumentWithTooManyEqualSigns { equal_signs, .. } = attribute else { + return None; + }; + + Some(Self { + token: Span { + start: equal_signs + .first() + .expect("at least two equal signs") + .span + .start, + end: equal_signs + .last() + .expect("at least two equal signs") + .span + .end, + }, + }) + } +} diff --git a/src/diagnostics/top_level_character_data.rs b/src/diagnostics/top_level_character_data.rs new file mode 100644 index 0000000..5deb595 --- /dev/null +++ b/src/diagnostics/top_level_character_data.rs @@ -0,0 +1,41 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::AstDiagnostic, + parse::Node, + tokenize::{Span, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Top-level character data is present")] +#[diagnostic(code(TopLevelCharacterData), severity(Error))] +pub struct TopLevelCharacterData { + #[label(collection)] + nodes: Vec<Span>, +} + +impl AstDiagnostic for TopLevelCharacterData { + fn handle_document(document: &crate::parse::Document<'_>) -> Option<Self> { + let cdata_nodes = document + .children + .iter() + .filter_map(|node| { + if let Node::CharacterData(token) = node + && let TokenType::Data(data) = token.ty + && data.chars().any(|c| !c.is_whitespace()) + { + Some(token.span) + } else { + None + } + }) + .collect::<Vec<_>>(); + + if cdata_nodes.is_empty() { + return None; + } + + Some(Self { nodes: cdata_nodes }) + } +} diff --git a/src/diagnostics/unclosed_start_tag.rs b/src/diagnostics/unclosed_start_tag.rs new file mode 100644 index 0000000..db7e3fb --- /dev/null +++ b/src/diagnostics/unclosed_start_tag.rs @@ -0,0 +1,24 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{diagnostics::AstDiagnostic, parse::Element, tokenize::Span}; + +#[derive(Error, Debug, Diagnostic)] +#[error("The start tag was not closed")] +#[diagnostic(code(UnclosedStartTag), severity(Error))] +pub struct UnclosedStartTag { + #[label("no matching end tag found")] + start_tag: Span, +} + +impl AstDiagnostic for UnclosedStartTag { + fn handle_element(element: &Element<'_>) -> Option<Self> { + if element.is_self_closing() || element.end_tag.is_some() { + return None; + } + + Some(Self { + start_tag: element.start_tag.span, + }) + } +} diff --git a/src/diagnostics/unterminated_comment.rs b/src/diagnostics/unterminated_comment.rs new file mode 100644 index 0000000..2c583a4 --- /dev/null +++ b/src/diagnostics/unterminated_comment.rs @@ -0,0 +1,31 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::TokenDiagnostic, + tokenize::{Span, Token, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Unterminated comment")] +#[diagnostic(code(UnterminatedComment), severity(Error))] +pub struct UnterminatedComment { + #[label(primary, "This comment is not terminated by a `-->` sequence")] + comment: Span, +} + +impl TokenDiagnostic for UnterminatedComment { + fn handle_token(token: &Token<'_>) -> Option<Self> { + let TokenType::Comment { terminated, .. } = token.ty else { + return None; + }; + + if terminated { + return None; + } + + Some(Self { + comment: token.span, + }) + } +} diff --git a/src/diagnostics/unterminated_tag.rs b/src/diagnostics/unterminated_tag.rs new file mode 100644 index 0000000..cab21f8 --- /dev/null +++ b/src/diagnostics/unterminated_tag.rs @@ -0,0 +1,33 @@ +use miette::Diagnostic; +use thiserror::Error; + +use crate::{ + diagnostics::TokenDiagnostic, + tokenize::{Span, Token, TokenType}, +}; + +#[derive(Error, Debug, Diagnostic)] +#[error("Unterminated tag")] +#[diagnostic(code(UnterminatedTag), severity(Error))] +pub struct UnterminatedTag { + #[label(primary, "This tag is not terminated by a greater-than sign (>)")] + tag: Span, +} + +impl TokenDiagnostic for UnterminatedTag { + fn handle_token(token: &Token<'_>) -> Option<Self> { + let TokenType::Tag { + greater_than_exists, + .. + } = token.ty + else { + return None; + }; + + if greater_than_exists { + return None; + } + + Some(Self { tag: token.span }) + } +} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..17d2c6d --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,5 @@ +pub mod analyze; +pub mod compile; +pub mod diagnostics; +pub mod parse; +pub mod tokenize; diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..1ac5a54 --- /dev/null +++ b/src/main.rs @@ -0,0 +1,62 @@ +use std::collections::HashMap; + +use bpaf::{Bpaf, Parser}; +use bumpalo::Bump; +use kuht::{analyze::symbol_table, compile::compile, parse::parse_document, tokenize::tokenize}; + +#[derive(Debug, Clone, Bpaf)] +struct Options { + /// Show any errors without compiling + #[bpaf(switch)] + dry: bool, + + // The location to place the resulting HTML file + #[bpaf(short)] + out: String, + + /// The files to compile to an HTML + #[bpaf(positional("FILES"))] + files: Vec<String>, +} + +fn main() { + let options = options().run(); + let sources = options + .files + .into_iter() + .map(|filename| { + let source = match std::fs::read_to_string(&filename) { + Ok(source) => source, + Err(error) => { + eprintln!("{error}"); + std::process::exit(1); + } + }; + (filename, source) + }) + .collect::<HashMap<_, _>>(); + + let arena = Bump::new(); + let tokens = sources + .into_iter() + .map(|(filename, source)| (filename, tokenize(&source, &arena))) + .collect::<HashMap<_, _>>(); + + let asts = tokens + .into_iter() + .map(|(filename, tokens)| (filename, parse_document(tokens, &arena))) + .collect::<HashMap<_, _>>(); + + let symbol_tables = asts + .into_iter() + .map(|(filename, document)| (filename, symbol_table(&arena, document))) + .collect::<HashMap<_, _>>(); + + if !options.dry { + let output = compile(&symbol_tables.into_values().collect::<Box<_>>()); + if let Err(e) = std::fs::write(options.out, output.as_bytes()) { + eprintln!("{e}"); + std::process::exit(1); + } + } +} diff --git a/src/old_tokenizer.rs b/src/old_tokenizer.rs new file mode 100644 index 0000000..9f9b79d --- /dev/null +++ b/src/old_tokenizer.rs @@ -0,0 +1,720 @@ +enum TokenizerState { + Data, + CharacterReferenceInData, + RcData, + CharacterReferenceInRcData, + RawText, + ScriptData, + PlainText, + TagOpen, + EndTagOpen, + TagName, + RcDataLessThan, + RcDataEndTagOpen, + RcDataEndTagName, + RawTextLessThanSign, + RawTextEndTagOpen, + RawTextEndTagName, + ScriptDataLessThanSign, + ScriptDataEndTagOpen, + ScriptDataEndTagName, + ScriptDataEscapeStart, + ScriptDataEscapeStartDash, + ScriptDataEscaped, + ScriptDataEscapedDash, + ScriptDataEscapedDashDash, + ScriptDataEscapedLessThanSign, + ScriptDataEscapedEndTagOpen, + ScriptDataEscapedEndTagName, + ScriptDataDoubleEscaped, + ScriptDataDoubleEscapedDash, + ScriptDataDoubleEscapedDashDash, + ScriptDataDoubleEscapedLessThanSign, + ScriptDataDoubleEscapeEnd, + BeforeAttributeName, + AttributeName, + AfterAttributeName, + BeforeAttributeValue, + AttributeValueDoubleQuoted, + AttributeValueSingleQuoted, + AttributeValueUnquoted, + CharacterReferenceInAttributeValue, + AfterAttributeValue, + SelfClosingStartTag, + BogusComment, + MarkupDeclarationOpen, + CommentStart, + CommentStartDash, + Comment, + CommentEndDash, + CommentEnd, + CommendEndBang, + DocType, + BeforeDocTypeName, + DocTypeName, + AfterDocTypeName, + AfterDocTypePublicKeyword, + DocTypePublicIdentifierDoubleQuoted, + DocTypePublicIdentifierSingleQuoted, + AfterDocTypePublicIdentifier, + BetweenDocTypePublicAndSystemIdentifiers, + AfterDocTypeSystemKeyword, + BeforeDocTypeSystemIdentifier, + DocTypeSystemIdentifierDoubleQuoted, + DocTypeSystemIdentifierSingleQuoted, + AfterDocTypeSystemIdentifier, + BogusDocType, + CdataSection, +} + +struct TagBuilder { + name: String, + self_closing: bool, + end_tag: bool, + attributes: Vec<(Option<String>, Option<String>)>, +} + +impl TagBuilder { + fn is_appropriate_end_tag(&self, last_start_tag: &Option<String>) -> bool { + last_start_tag + .as_ref() + .is_some_and(|name| name == &self.name) + } +} + +impl From<TagBuilder> for Token { + fn from(value: TagBuilder) -> Self { + let attributes = value + .attributes + .into_iter() + .map(|(key, value)| (key.map(Into::into), value.map(Into::into))) + .collect(); + if value.end_tag { + Token::EndTag { + tag_name: value.name.into(), + self_closing: value.self_closing, + attributes, + } + } else { + Token::StartTag { + tag_name: value.name.into(), + self_closing: value.self_closing, + attributes, + } + } + } +} + +fn consume_character_reference(chars: &mut Peekable<Chars<'_>>) -> Option<char> { + match chars.next() { + Some('\t' | '\u{000a}' | '\u{000c}' | ' ' | '<' | '&') | None => None, + Some('#') => match chars.peek() { + Some('x' | 'X') => { + chars.next(); + let mut digits = chars + .take_while(|c| c.is_ascii_hexdigit()) + .collect::<Box<str>>(); + if digits.is_empty() { + panic!("Parse error: no digits found after the hexadecimal specifier"); + return None; + } + if chars.next_if(|c| *c == ';').is_none() { + panic!("Parse error: expected a semicolon after escaped digits"); + } + + let number = u32::from_str_radix(&digits, 16).expect("only hexadecimal digits"); + if let Some(c) = match number { + 0x00 => Some('\u{fffd}'), + 0x0d => Some('\r'), + 0x80 => Some('\u{20ac}'), + 0x81 => Some('\u{0081}'), + 0x82 => Some('\u{201a}'), + 0x83 => Some('\u{0192}'), + 0x84 => Some('\u{201e}'), + 0x85 => Some('\u{2026}'), + 0x86 => Some('\u{2020}'), + 0x87 => Some('\u{2021}'), + 0x88 => Some('\u{02c6}'), + 0x89 => Some('\u{2030}'), + 0x8a => Some('\u{0160}'), + 0x8b => Some('\u{2039}'), + 0x8c => Some('\u{0152}'), + 0x8d => Some('\u{008d}'), + 0x8e => Some('\u{017d}'), + 0x8f => Some('\u{008f}'), + 0x90 => Some('\u{0090}'), + 0x91 => Some('\u{2018}'), + 0x92 => Some('\u{2019}'), + 0x93 => Some('\u{201c}'), + 0x94 => Some('\u{201d}'), + 0x95 => Some('\u{2022}'), + 0x96 => Some('\u{2013}'), + 0x97 => Some('\u{2014}'), + 0x98 => Some('\u{02dc}'), + 0x99 => Some('\u{2122}'), + 0x9a => Some('\u{0161}'), + 0x9b => Some('\u{203a}'), + 0x9c => Some('\u{0152}'), + 0x9d => Some('\u{009d}'), + 0x9e => Some('\u{017e}'), + 0x9f => Some('\u{0178}'), + _ => None, + } { + panic!("Parse error: invalid character"); + return Some(c); + } + + if (0xd800 < number && number < 0xdfff) || number > 0x10ffff { + panic!("Parse error: invalid character reference"); + return Some(char::REPLACEMENT_CHARACTER); + } + + match char::from_u32(number) { + Some(char) => Some(char), + None => panic!("Parse error: invalid character reference"), + } + } + _ => { + let mut digits = chars + .take_while(|c| c.is_ascii_digit()) + .collect::<Box<str>>(); + if digits.is_empty() { + panic!("Parse error: no digits found after the ampersand"); + return None; + } + if chars.next_if(|c| *c == ';').is_none() { + panic!("Parse error: expected a semicolon after escaped digits"); + } + + let number = u32::from_str_radix(&digits, 10).expect("only decimal digits"); + if let Some(c) = match number { + 0x00 => Some('\u{fffd}'), + 0x0d => Some('\r'), + 0x80 => Some('\u{20ac}'), + 0x81 => Some('\u{0081}'), + 0x82 => Some('\u{201a}'), + 0x83 => Some('\u{0192}'), + 0x84 => Some('\u{201e}'), + 0x85 => Some('\u{2026}'), + 0x86 => Some('\u{2020}'), + 0x87 => Some('\u{2021}'), + 0x88 => Some('\u{02c6}'), + 0x89 => Some('\u{2030}'), + 0x8a => Some('\u{0160}'), + 0x8b => Some('\u{2039}'), + 0x8c => Some('\u{0152}'), + 0x8d => Some('\u{008d}'), + 0x8e => Some('\u{017d}'), + 0x8f => Some('\u{008f}'), + 0x90 => Some('\u{0090}'), + 0x91 => Some('\u{2018}'), + 0x92 => Some('\u{2019}'), + 0x93 => Some('\u{201c}'), + 0x94 => Some('\u{201d}'), + 0x95 => Some('\u{2022}'), + 0x96 => Some('\u{2013}'), + 0x97 => Some('\u{2014}'), + 0x98 => Some('\u{02dc}'), + 0x99 => Some('\u{2122}'), + 0x9a => Some('\u{0161}'), + 0x9b => Some('\u{203a}'), + 0x9c => Some('\u{0152}'), + 0x9d => Some('\u{009d}'), + 0x9e => Some('\u{017e}'), + 0x9f => Some('\u{0178}'), + _ => None, + } { + panic!("Parse error: invalid character"); + return Some(c); + } + + if (0xd800 < number && number < 0xdfff) || number > 0x10ffff { + panic!("Parse error: invalid character reference"); + return Some(char::REPLACEMENT_CHARACTER); + } + + match char::from_u32(number) { + Some(char) => Some(char), + None => panic!("Parse error: invalid character reference"), + } + } + }, + _ => todo!("Parse named character reference"), + } +} + +fn tokenize(source: &str) -> Box<[Token]> { + let mut chars = source.chars().peekable(); + let mut tokens = Vec::new(); + let mut state = TokenizerState::Data; + let mut tag_builder = TagBuilder { + name: String::new(), + self_closing: false, + end_tag: false, + attributes: Vec::new(), + }; + let mut last_start_tag = None; + let mut temp_buffer = String::new(); + loop { + match state { + TokenizerState::Data => match chars.next() { + Some('&') => state = TokenizerState::CharacterReferenceInData, + Some('<') => state = TokenizerState::TagOpen, + Some('\0') => { + panic!("Parse error: NUL character"); + tokens.push(Token::Character('\0')); + } + None => break, + Some(c) => tokens.push(Token::Character(c)), + }, + TokenizerState::CharacterReferenceInData => { + tokens.push(Token::Character( + consume_character_reference(&mut chars).unwrap_or('&'), + )); + state = TokenizerState::Data; + } + TokenizerState::RcData => match chars.next() { + Some('&') => state = TokenizerState::CharacterReferenceInRcData, + Some('<') => state = TokenizerState::RcDataLessThan, + Some('\0') => { + panic!("Parse error: NUL character"); + tokens.push(Token::Character(char::REPLACEMENT_CHARACTER)); + } + None => break, + Some(c) => tokens.push(Token::Character(c)), + }, + TokenizerState::CharacterReferenceInRcData => { + tokens.push(Token::Character( + consume_character_reference(&mut chars).unwrap_or('&'), + )); + state = TokenizerState::RcData; + } + TokenizerState::RawText => match chars.next() { + Some('<') => state = TokenizerState::RawTextLessThanSign, + Some('\0') => { + panic!("Parse error: NUL character"); + tokens.push(Token::Character(char::REPLACEMENT_CHARACTER)); + } + None => break, + Some(c) => tokens.push(Token::Character(c)), + }, + TokenizerState::ScriptData => match chars.next() { + Some('<') => state = TokenizerState::ScriptDataLessThanSign, + Some('\0') => { + panic!("Parse error: NUL character"); + tokens.push(Token::Character(char::REPLACEMENT_CHARACTER)); + } + None => break, + Some(c) => tokens.push(Token::Character(c)), + }, + TokenizerState::PlainText => match chars.next() { + Some('\0') => { + panic!("Parse error: NUL character"); + tokens.push(Token::Character(char::REPLACEMENT_CHARACTER)); + } + None => break, + Some(c) => tokens.push(Token::Character(c)), + }, + TokenizerState::TagOpen => match chars.next() { + Some('!') => state = TokenizerState::MarkupDeclarationOpen, + Some('/') => state = TokenizerState::EndTagOpen, + Some(c) if c.is_ascii_uppercase() => { + state = TokenizerState::TagName; + tag_builder = TagBuilder { + name: String::from(c.to_ascii_lowercase()), + end_tag: false, + self_closing: false, + attributes: Vec::new(), + }; + } + Some(c) if c.is_ascii_lowercase() => { + state = TokenizerState::TagName; + tag_builder = TagBuilder { + name: c.to_string(), + end_tag: false, + self_closing: false, + attributes: Vec::new(), + } + } + Some('?') => { + panic!("Parse error: bogus comment"); + state = TokenizerState::BogusComment; + } + None => { + panic!("Parse error: unfinished tag"); + tokens.push(Token::Character('<')); + state = TokenizerState::Data; + } + _ => { + chars.next_back(); + panic!("Parse error: less than sign without a tag"); + tokens.push(Token::Character('<')); + state = TokenizerState::Data; + } + }, + TokenizerState::EndTagOpen => match chars.next() { + Some(c) if c.is_ascii_uppercase() => { + state = TokenizerState::TagName; + tag_builder = TagBuilder { + name: String::from(c.to_ascii_lowercase()), + end_tag: true, + self_closing: false, + attributes: Vec::new(), + } + } + Some(c) if c.is_ascii_lowercase() => { + state = TokenizerState::TagName; + tag_builder = TagBuilder { + name: c.to_string(), + end_tag: true, + self_closing: false, + attributes: Vec::new(), + } + } + Some('>') => { + panic!("Parse error: end tag with no name"); + state = TokenizerState::Data; + } + None => { + panic!("Parse error: unfinished end tag"); + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + state = TokenizerState::Data; + } + _ => { + chars.next_back(); + panic!("Parse error: less than sign without a tag"); + tokens.push(Token::Character('<')); + state = TokenizerState::Data; + } + }, + TokenizerState::TagName => match chars.next() { + Some('\t' | '\u{000a}' | '\u{000c}' | ' ') => { + state = TokenizerState::BeforeAttributeName + } + Some('/') => state = TokenizerState::SelfClosingStartTag, + Some('>') => { + state = TokenizerState::Data; + if !tag_builder.end_tag { + last_start_tag = Some(tag_builder.name.clone()); + } + tokens.push(tag_builder.into()); + } + Some(c) if c.is_ascii_uppercase() => tag_builder.name.push(c.to_ascii_lowercase()), + Some('\0') => { + panic!("Parse error: NUL character in tag name"); + tag_builder.name.push(char::REPLACEMENT_CHARACTER); + } + None => { + panic!("Parse error: unfinished tag"); + state = TokenizerState::Data; + } + Some(c) => tag_builder.name.push(c), + }, + TokenizerState::RcDataLessThan => match chars.next() { + Some('/') => { + temp_buffer.clear(); + state = TokenizerState::RcDataEndTagOpen; + } + _ => { + tokens.push(Token::Character('<')); + chars.next_back(); + state = TokenizerState::RcData; + } + }, + TokenizerState::RcDataEndTagOpen => match chars.next() { + Some(c) if c.is_ascii_uppercase() => { + tag_builder = TagBuilder { + end_tag: true, + name: c.to_ascii_lowercase().to_string(), + self_closing: false, + attributes: Vec::new(), + }; + temp_buffer = c.to_string(); + state = TokenizerState::RcDataEndTagName; + } + Some(c) if c.is_ascii_lowercase() => { + tag_builder = TagBuilder { + end_tag: true, + name: c.to_string(), + self_closing: false, + attributes: Vec::new(), + }; + temp_buffer = c.to_string(); + state = TokenizerState::RcDataEndTagName; + } + Some(c) => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + chars.next_back(); + state = TokenizerState::RcData; + } + None => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + state = TokenizerState::RcData; + } + }, + TokenizerState::RcDataEndTagName => match chars.next() { + Some('\t' | '\u{000a}' | '\u{000c}' | ' ') + if tag_builder.is_appropriate_end_tag(&last_start_tag) => + { + state = TokenizerState::BeforeAttributeName + } + + Some('/') if tag_builder.is_appropriate_end_tag(&last_start_tag) => { + state = TokenizerState::SelfClosingStartTag + } + Some('>') if tag_builder.is_appropriate_end_tag(&last_start_tag) => { + tokens.push(tag_builder.into()); + state = TokenizerState::Data; + } + Some(c) if c.is_ascii_uppercase() => { + tag_builder.name.push(c.to_ascii_lowercase()); + temp_buffer.push(c); + } + Some(c) if c.is_ascii_lowercase() => { + tag_builder.name.push(c); + temp_buffer.push(c); + } + None => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + for char in temp_buffer.chars() { + tokens.push(Token::Character(char)); + } + state = TokenizerState::RcData; + } + _ => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + for char in temp_buffer.chars() { + tokens.push(Token::Character(char)); + } + chars.next_back(); + state = TokenizerState::RcData; + } + }, + TokenizerState::RawTextLessThanSign => match chars.next() { + Some('/') => { + temp_buffer = String::new(); + state = TokenizerState::RawTextEndTagOpen; + } + None => { + tokens.push(Token::Character('<')); + state = TokenizerState::RawText; + } + _ => { + tokens.push(Token::Character('<')); + chars.next_back(); + state = TokenizerState::RawText; + } + }, + TokenizerState::RawTextEndTagOpen => match chars.next() { + Some(c) if c.is_ascii_uppercase() => { + tag_builder = TagBuilder { + name: c.to_ascii_lowercase().to_string(), + self_closing: false, + end_tag: true, + attributes: Vec::new(), + }; + temp_buffer.push(c); + state = TokenizerState::RawTextEndTagName; + } + Some(c) if c.is_ascii_lowercase() => { + tag_builder = TagBuilder { + name: c.to_string(), + self_closing: false, + end_tag: true, + attributes: Vec::new(), + }; + temp_buffer.push(c); + state = TokenizerState::RawTextEndTagName; + } + None => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + state = TokenizerState::RawText; + } + Some(_) => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + state = TokenizerState::RawText; + chars.next_back(); + } + }, + TokenizerState::RawTextEndTagName => match chars.next() { + Some('\t' | '\u{000a}' | '\u{000c}' | ' ') + if tag_builder.is_appropriate_end_tag(&last_start_tag) => + { + state = TokenizerState::BeforeAttributeName + } + + Some('/') if tag_builder.is_appropriate_end_tag(&last_start_tag) => { + state = TokenizerState::SelfClosingStartTag + } + Some('>') if tag_builder.is_appropriate_end_tag(&last_start_tag) => { + tokens.push(tag_builder.into()); + state = TokenizerState::Data; + } + Some(c) if c.is_ascii_uppercase() => { + tag_builder.name.push(c.to_ascii_lowercase()); + temp_buffer.push(c); + } + Some(c) if c.is_ascii_lowercase() => { + tag_builder.name.push(c); + temp_buffer.push(c); + } + None => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + for char in temp_buffer.chars() { + tokens.push(Token::Character(char)); + } + state = TokenizerState::RawText; + } + _ => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + for char in temp_buffer.chars() { + tokens.push(Token::Character(char)); + } + chars.next_back(); + state = TokenizerState::RawText; + } + }, + TokenizerState::ScriptDataLessThanSign => match chars.next() { + Some('/') => { + temp_buffer = String::new(); + state = TokenizerState::ScriptDataEndTagOpen; + } + Some('!') => { + state = TokenizerState::ScriptDataEscapeStart; + tokens.push(Token::Character('<')); + tokens.push(Token::Character('!')); + } + None => { + tokens.push(Token::Character('<')); + state = TokenizerState::ScriptData; + } + _ => { + tokens.push(Token::Character('<')); + state = TokenizerState::ScriptData; + chars.next_back(); + } + }, + TokenizerState::ScriptDataEndTagOpen => match chars.next() { + Some(c) if c.is_ascii_uppercase() => { + tag_builder = TagBuilder { + name: c.to_ascii_lowercase().to_string(), + self_closing: false, + end_tag: true, + attributes: Vec::new(), + }; + temp_buffer.push(c); + state = TokenizerState::ScriptDataEndTagName; + } + Some(c) if c.is_ascii_lowercase() => { + tag_builder = TagBuilder { + name: c.to_string(), + self_closing: false, + end_tag: true, + attributes: Vec::new(), + }; + temp_buffer.push(c); + state = TokenizerState::ScriptDataEndTagName; + } + None => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + state = TokenizerState::ScriptData; + } + _ => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + chars.next_back(); + state = TokenizerState::ScriptData; + } + }, + TokenizerState::ScriptDataEndTagName => match chars.next() { + Some('\t' | '\u{000a}' | '\u{000c}' | ' ') + if tag_builder.is_appropriate_end_tag(&last_start_tag) => + { + state = TokenizerState::BeforeAttributeName + } + + Some('/') if tag_builder.is_appropriate_end_tag(&last_start_tag) => { + state = TokenizerState::SelfClosingStartTag + } + Some('>') if tag_builder.is_appropriate_end_tag(&last_start_tag) => { + tokens.push(tag_builder.into()); + state = TokenizerState::Data; + } + Some(c) if c.is_ascii_uppercase() => { + tag_builder.name.push(c.to_ascii_lowercase()); + temp_buffer.push(c); + } + Some(c) if c.is_ascii_lowercase() => { + tag_builder.name.push(c); + temp_buffer.push(c); + } + None => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + for char in temp_buffer.chars() { + tokens.push(Token::Character(char)); + } + state = TokenizerState::ScriptData; + } + _ => { + tokens.push(Token::Character('<')); + tokens.push(Token::Character('/')); + for char in temp_buffer.chars() { + tokens.push(Token::Character(char)); + } + chars.next_back(); + state = TokenizerState::ScriptData; + } + }, + TokenizerState::ScriptDataEscapeStart => match chars.next() { + Some('-') => { + state = TokenizerState::ScriptDataEscapeStartDash; + tokens.push(Token::Character('-')); + } + None => state = TokenizerState::ScriptData, + _ => { + chars.next_back(); + state = TokenizerState::ScriptData; + } + }, + TokenizerState::ScriptDataEscapeStartDash => match chars.next() { + Some('-') => { + state = TokenizerState::ScriptDataEscapedDashDash; + tokens.push(Token::Character('-')); + } + None => state = TokenizerState::ScriptData, + _ => { + chars.next_back(); + state = TokenizerState::ScriptData; + } + }, + TokenizerState::ScriptDataEscaped => match chars.next() { + Some('-') => { + state = TokenizerState::ScriptDataEscapedDash; + tokens.push(Token::Character('-')); + } + Some('<') => state = TokenizerState::ScriptDataEscapedLessThanSign, + Some('\0') => { + panic!("Parse error: unexpected NUL character"); + tokens.push(Token::Character(char::REPLACEMENT_CHARACTER)); + } + None => { + panic!("Parse error: unexpected end of file") + } + Some(c) => tokens.push(Token::Character(c)), + }, + } + } + + tokens.into_boxed_slice() +} diff --git a/src/parse.rs b/src/parse.rs new file mode 100644 index 0000000..b2e5116 --- /dev/null +++ b/src/parse.rs @@ -0,0 +1,296 @@ +use std::iter::Peekable; + +use bumpalo::Bump; + +use crate::tokenize::{AttributeToken, AttributeTokenType, Token, TokenType}; + +#[derive(Debug, Clone, Copy)] +pub struct Document<'a> { + pub children: &'a [Node<'a>], +} + +#[derive(Debug, Clone, Copy)] +pub enum Node<'a> { + Element(Element<'a>), + CharacterData(Token<'a>), + Comment(Token<'a>), + StrayEndTag(Token<'a>), +} + +#[derive(Debug, Clone, Copy)] +pub struct Element<'a> { + pub start_tag: Token<'a>, + pub attributes: &'a [Attribute<'a>], + pub children: &'a [Node<'a>], + pub end_tag: Option<Token<'a>>, + pub end_tag_attributes: &'a [Attribute<'a>], +} + +#[derive(Debug, Clone, Copy)] +pub enum Attribute<'a> { + NameOnly { + name: AttributeToken<'a>, + }, + NamedArgument { + name: AttributeToken<'a>, + equal_sign: AttributeToken<'a>, + value: Option<AttributeToken<'a>>, + }, + PositionalArgument { + value: AttributeToken<'a>, + }, + StrayEqualSign(AttributeToken<'a>), + NamedArgumentWithTooManyEqualSigns { + name: AttributeToken<'a>, + equal_signs: &'a [AttributeToken<'a>], + value: Option<AttributeToken<'a>>, + }, +} + +impl<'a> Element<'a> { + pub fn is_self_closing(&self) -> bool { + matches!(self.start_tag.ty, TokenType::Tag { self_closing, .. } if self_closing) + } + + pub fn tag_name_lowercase(&self) -> Option<&str> { + let TokenType::Tag { + lowercase_tag_name, .. + } = self.start_tag.ty + else { + return None; + }; + Some(lowercase_tag_name) + } + + pub fn attribute(&self, name: &str) -> Option<&Attribute<'a>> { + self.attributes + .iter() + .find(|attribute| attribute.name_lowercase().is_some_and(|n| n == name)) + } +} + +impl<'a> Attribute<'a> { + pub fn name_token(&self) -> Option<&AttributeToken<'_>> { + match self { + Self::NamedArgument { name, .. } + | Attribute::NameOnly { name } + | Attribute::NamedArgumentWithTooManyEqualSigns { name, .. } => Some(name), + Self::PositionalArgument { .. } | Self::StrayEqualSign(_) => None, + } + } + + pub fn name_lowercase(&self) -> Option<&str> { + let name = self.name_token()?; + let AttributeTokenType::Identifier { lowercase_name, .. } = name.ty else { + return None; + }; + Some(lowercase_name) + } + + pub fn value_token(&self) -> Option<&AttributeToken<'a>> { + match self { + Self::NamedArgument { value, .. } + | Self::NamedArgumentWithTooManyEqualSigns { value, .. } => value.as_ref(), + Self::PositionalArgument { value } => Some(value), + Self::NameOnly { .. } | Self::StrayEqualSign(..) => None, + } + } + + pub fn value_str(&self) -> Option<&str> { + let value = self.value_token()?; + let AttributeTokenType::String { value, .. } = value.ty else { + return None; + }; + Some(value) + } +} + +fn parse_named_attribute<'a>( + attribute_tokens: &mut Peekable<impl Iterator<Item = &'a AttributeToken<'a>>>, + name: AttributeToken<'a>, + equal_sign: AttributeToken<'a>, + arena: &'a Bump, +) -> Attribute<'a> { + if let Some(equal_sign_2) = attribute_tokens + .next_if(|t| matches!(t.ty, AttributeTokenType::EqualSign)) + .copied() + { + let mut equal_signs = vec![equal_sign, equal_sign_2]; + while let Some(equal_sign) = attribute_tokens + .next_if(|t| matches!(t.ty, AttributeTokenType::EqualSign)) + .copied() + { + equal_signs.push(equal_sign); + } + let equal_signs = arena.alloc_slice_copy(&equal_signs); + + let value = attribute_tokens.next().copied(); + Attribute::NamedArgumentWithTooManyEqualSigns { + name, + equal_signs, + value, + } + } else { + let value = attribute_tokens.next().copied(); + Attribute::NamedArgument { + name, + equal_sign, + value, + } + } +} + +fn parse_attribute<'a>( + attribute_tokens: &mut Peekable<impl Iterator<Item = &'a AttributeToken<'a>>>, + arena: &'a Bump, +) -> Option<Attribute<'a>> { + let attribute_token = *attribute_tokens.next()?; + match attribute_token.ty { + AttributeTokenType::Identifier { .. } => { + let name = attribute_token; + if let Some(equal_sign) = attribute_tokens + .next_if(|t| matches!(t.ty, AttributeTokenType::EqualSign)) + .copied() + { + parse_named_attribute(attribute_tokens, name, equal_sign, arena) + } else { + Attribute::NameOnly { name } + } + } + AttributeTokenType::String { .. } => Attribute::PositionalArgument { + value: attribute_token, + }, + AttributeTokenType::EqualSign => Attribute::StrayEqualSign(attribute_token), + } + .into() +} + +fn parse_attributes<'a>( + attribute_tokens: &'a [AttributeToken<'a>], + arena: &'a Bump, +) -> &'a [Attribute<'a>] { + let mut attributes = Vec::new(); + let mut attribute_tokens = attribute_tokens.iter().peekable(); + while let Some(attribute) = parse_attribute(&mut attribute_tokens, arena) { + attributes.push(attribute); + } + arena.alloc_slice_copy(&attributes) +} + +fn parse_element<'a>( + tokens: &mut Peekable<impl Iterator<Item = &'a Token<'a>>>, + stack: &[&'a str], + arena: &'a Bump, +) -> Option<Node<'a>> { + let start_tag = *tokens.next()?; + let TokenType::Tag { + is_end, + lowercase_tag_name, + original_tag_name: _, + self_closing, + attribute_tokens, + greater_than_exists: _, + } = start_tag.ty + else { + return None; + }; + + if is_end { + return Some(Node::StrayEndTag(start_tag)); + } + + let attributes = parse_attributes(attribute_tokens, arena); + + if self_closing { + return Some(Node::Element(Element { + start_tag, + attributes, + children: &[], + end_tag: None, + end_tag_attributes: &[], + })); + } + + let mut children = Vec::new(); + let mut stack = Vec::from(stack); + stack.push(lowercase_tag_name); + + while let Some(token) = tokens.peek() { + match token.ty { + TokenType::Comment { .. } => { + let token = tokens.next().expect("a token"); + children.push(Node::Comment(*token)) + } + TokenType::Data(_) => { + let token = tokens.next().expect("a token"); + children.push(Node::CharacterData(*token)) + } + TokenType::Tag { + is_end, + lowercase_tag_name: end_tag_name, + attribute_tokens, + .. + } if is_end && end_tag_name == lowercase_tag_name => { + let token = tokens.next().expect("a token"); + let children = arena.alloc_slice_copy(&children); + let end_tag_attributes = parse_attributes(attribute_tokens, arena); + return Some(Node::Element(Element { + start_tag, + attributes, + children, + end_tag: Some(*token), + end_tag_attributes, + })); + } + TokenType::Tag { + is_end, + lowercase_tag_name, + .. + } if is_end && stack.contains(&lowercase_tag_name) => { + tokens.next().expect("a token"); + break; + } + TokenType::Tag { is_end, .. } if is_end => { + let token = tokens.next().expect("a token"); + children.push(Node::StrayEndTag(*token)) + } + TokenType::Tag { .. } => { + children.push(parse_element(tokens, &[], arena).expect("an element")); + } + } + } + + let children = arena.alloc_slice_copy(&children); + + Some(Node::Element(Element { + start_tag, + attributes, + children, + end_tag: None, + end_tag_attributes: &[], + })) +} + +pub fn parse_document<'a>(tokens: &'a [Token<'a>], arena: &'a Bump) -> Document<'a> { + let mut children = Vec::new(); + let mut tokens = tokens.iter().peekable(); + while let Some(token) = tokens.peek() { + match token.ty { + TokenType::Comment { .. } => { + let token = tokens.next().expect("we just saw a token from peeking"); + children.push(Node::Comment(*token)) + } + TokenType::Data(_) => { + let token = tokens.next().expect("we just saw a token from peeking"); + children.push(Node::CharacterData(*token)) + } + TokenType::Tag { .. } => { + children.push(parse_element(&mut tokens, &[], arena).expect("an element")); + } + } + } + + Document { + children: arena.alloc_slice_copy(&children), + } +} diff --git a/src/tokenize.rs b/src/tokenize.rs new file mode 100644 index 0000000..43ad305 --- /dev/null +++ b/src/tokenize.rs @@ -0,0 +1,231 @@ +use bumpalo::Bump; +use snob::csets::CharacterSet; + +#[derive(Debug, Clone, Copy)] +pub struct Token<'a> { + pub span: Span, + pub ty: TokenType<'a>, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct Span { + pub start: usize, + pub end: usize, +} + +#[derive(Debug, Clone, Copy)] +pub enum TokenType<'a> { + Tag { + is_end: bool, + original_tag_name: &'a str, + lowercase_tag_name: &'a str, + self_closing: bool, + attribute_tokens: &'a [AttributeToken<'a>], + greater_than_exists: bool, + }, + Comment { + terminated: bool, + data: &'a str, + }, + Data(&'a str), +} + +#[derive(Debug, Clone, Copy)] +pub struct AttributeToken<'a> { + pub span: Span, + pub ty: AttributeTokenType<'a>, +} + +#[derive(Debug, Clone, Copy)] +pub enum AttributeTokenType<'a> { + Identifier { + lowercase_name: &'a str, + original_name: &'a str, + }, + String { + double_quoted: bool, + terminated: bool, + value: &'a str, + }, + EqualSign, +} + +impl From<Span> for miette::SourceSpan { + fn from(value: Span) -> Self { + miette::SourceSpan::from((value.start, value.start - value.end)) + } +} + +fn advance_over_whitespace(scanner: &mut snob::Scanner) { + if let Some(position) = scanner.many(snob::csets::AsciiWhitespace) { + scanner.goto(position).expect("a valid position"); + } +} + +fn upto_str(scanner: &mut snob::Scanner, str: &str) -> Option<usize> { + let first_char = str + .chars() + .next() + .expect("Cannot use upto_str on an empty string"); + while let Some(position) = scanner.upto(first_char) { + if scanner.starts_with(str).is_some() { + return Some(position); + } + } + + None +} + +fn scan_attribute_token<'a>( + scanner: &mut snob::Scanner, + arena: &'a Bump, +) -> Option<AttributeToken<'a>> { + advance_over_whitespace(scanner); + let start = scanner.position(); + + if scanner.advance_if_starts_with("=").is_some() { + Some(AttributeToken { + span: Span { + start, + end: scanner.position(), + }, + ty: AttributeTokenType::EqualSign, + }) + } else if let Some(position) = scanner.any("'\"") { + let delimiter = scanner + .goto(position) + .expect("a valid position") + .chars() + .next() + .expect("one character, either double quote or single quote"); + let position = scanner.upto(delimiter).unwrap_or(scanner.len()); + let value = scanner.goto(position).expect("a valid position"); + let value = arena.alloc_str(&value); + let terminated = scanner + .advance_if_starts_with(delimiter.to_string()) + .is_some(); + Some(AttributeToken { + span: Span { + start, + end: scanner.position(), + }, + ty: AttributeTokenType::String { + double_quoted: delimiter == '"', + terminated, + value, + }, + }) + } else if let Some(position) = scanner.many(snob::csets::AsciiLetters) { + let value = scanner.goto(position).expect("a valid position"); + let value = arena.alloc_str(&value); + let lowercase_value = arena.alloc_str(value); + lowercase_value.make_ascii_lowercase(); + Some(AttributeToken { + span: Span { + start, + end: scanner.position(), + }, + ty: AttributeTokenType::Identifier { + original_name: value, + lowercase_name: value, + }, + }) + } else { + None + } +} + +fn scan_data<'a>(scanner: &mut snob::Scanner, arena: &'a Bump) -> &'a str { + let position = scanner.upto('<'); + let data = scanner + .goto(position.unwrap_or(scanner.len())) + .expect("valid position"); + arena.alloc_str(&data) +} + +fn scan_comment<'a>(scanner: &mut snob::Scanner, arena: &'a Bump) -> Option<TokenType<'a>> { + scanner.advance_if_starts_with("<!--")?; + + let Some(position) = upto_str(scanner, "-->") else { + let data = scanner.goto(scanner.len()).expect("a valid position"); + let data = arena.alloc_str(&data); + return Some(TokenType::Comment { + terminated: false, + data, + }); + }; + let data = scanner.goto(position).expect("a valid position"); + let data = arena.alloc_str(&data); + scanner + .advance_if_starts_with("-->") + .expect("an end to the comment"); + + Some(TokenType::Comment { + terminated: true, + data, + }) +} + +fn scan_tag<'a>(scanner: &mut snob::Scanner, arena: &'a Bump) -> Option<TokenType<'a>> { + scanner.advance_if_starts_with("<")?; + advance_over_whitespace(scanner); + + let is_end = scanner.advance_if_starts_with("/").is_some(); + advance_over_whitespace(scanner); + + let position = scanner + .upto(snob::csets::AsciiWhitespace.union("/>")) + .unwrap_or(scanner.len()); + let original_tag_name = scanner.goto(position).expect("a valid position"); + let original_tag_name = arena.alloc_str(&original_tag_name); + let lowercase_tag_name = arena.alloc_str(original_tag_name); + lowercase_tag_name.make_ascii_lowercase(); + advance_over_whitespace(scanner); + + let mut attribute_tokens = Vec::new(); + while let Some(attribute) = scan_attribute_token(scanner, arena) { + attribute_tokens.push(attribute); + advance_over_whitespace(scanner); + } + let attribute_tokens = arena.alloc_slice_copy(&attribute_tokens); + + let self_closing = scanner.advance_if_starts_with("/").is_some(); + advance_over_whitespace(scanner); + let greater_than_exists = scanner.advance_if_starts_with(">").is_some(); + + Some(TokenType::Tag { + is_end, + original_tag_name, + lowercase_tag_name, + self_closing, + attribute_tokens, + greater_than_exists, + }) +} + +pub fn tokenize<'a>(source: &str, arena: &'a Bump) -> &'a [Token<'a>] { + let mut scanner = snob::Scanner::new(source); + let mut tokens = Vec::new(); + loop { + if scanner.is_at_end() { + break; + } + + let start = scanner.position(); + let token = if scanner.starts_with("<!--").is_some() { + scan_comment(&mut scanner, arena).expect("a comment") + } else if scanner.starts_with("<").is_some() { + scan_tag(&mut scanner, arena).expect("a tag") + } else { + TokenType::Data(scan_data(&mut scanner, arena)) + }; + let end = scanner.position(); + + tokens.push(Token { + span: Span { start, end }, + ty: token, + }); + } + + arena.alloc_slice_copy(&tokens) +} |