About the implementation of HTML parser

[byted-meow]

Implementation of HTML parser

• Start Date: 2022-07-25

Background

HTML Loader need a good way to parse user-created HTML and resolve its dependencies. A spec-compliant, performant, and multi-functional HTML parser is required.

None of webpack, vite or parcel are using html parser implemented in rust. So we need to do it ourselves.

We need to parse the html to AST and design a good API to operate on it which is used in the html loader and its plugin system.

HTML parser

Requirements

To load a html file as entry, we need a html parser that implements the following methods:

• parse html according specification
• allow a simple way to query elements by type & attributes
  • as it's hard to recognize deps like parcel in html
  • better DOMParser like API and support querySelector
• allow a simple way to manipulate them
  • at least support create, insert, modify attributes and delete elements
  • better parse once, run multi times instead of streaming operations
• allow minimize the generated HTML (with or without inline css / scripts support)

Parser Candidates

• lol_html

  • very good performance
  • backed by CloudFlare and used internally, most trustable
  • moderate manipulation API design
  • stream operations on HTML strings or buffer

• swc html parser

  • good performance
  • very newly created, backed by SWC with spec compliant test but not used internally
  • no documents
  • no build-in support for manipulate DOM
  • parsed result are cached in AST

• kuchiki based on html5ever

  • poorly documented
  • good build-in selector support
  • adequate performance
  • information loss on test

bench parsing document without change

test  tests::bench_lol      ...  bench:  27,566 ns/iter (+/- 15,184)
test  tests::bench_swc      ...  bench:  154,335  ns/iter  (+/-  25,644)
test  tests::bench_kuchiki  ...  bench:  10,691,699  ns/iter  (+/-  907,423)

Choice

I perfer to choose from between lol_html and swc_html

When compared, swc_html is:

• 👼 of same swc ecosystem
• 👼 build-in AST support, which makes it more performant when operates multiple times on the same document
• 👼 build-in minifier
• 👿 though support traverse the AST, not build-in method are supported to manipulate the document. no query selectors are supported
• 👿 must use together with swc_html, swc_common and swc_atoms
• 👿 no documents, and just finished recently, so we are likely to be the first user.

pub struct Selector {
  found: bool,
}

impl Selector {
  pub fn new() -> Selector {
      return Selector { found: false };
  }
}

pub fn create_element(name: &str) -> Element {
  return Element {
      span: Default::default(),
      namespace: Namespace::HTML,
      tag_name: JsWord::from(name.clone()),
      attributes: vec![],
      is_self_closing: false,
      children: vec![],
      content: None,
  };
}

pub fn create_attribute(name: &str, value: &str) -> Attribute {
  return Attribute {
      span: Default::default(),
      namespace: None,
      prefix: None,
      name: name.clone().into(),
      raw_name: None,
      value: Some(value.clone().into()),
      raw_value: None,
  };
}

pub fn create_text(content: &str) -> Text {
  return Text {
      span: Default::default(),
      data: content.clone().into(),
      raw: None,
  };
}

impl VisitMut for Selector {
  fn visit_mut_element(&mut self, n: &mut Element) {
      if self.found {
          return ();
      }
      if n.attributes
          .iter()
          .any(|p| p.name.eq("id") && p.value.as_ref().unwrap().eq("test"))
      {
          self.found = true;
          let mut a = create_element("a");
          a.attributes = vec![
              create_attribute("href", "https://www.bytedance.com/"),
              create_attribute("target", "_blank"),
          ];
          a.children = vec![Child::Text(create_text("enrich life"))];
          n.children.insert(0, Child::Element(a));
          return ();
      }
      n.visit_mut_children_with(self);
  }
}

fn swc_modifier<'a>(document: &'a mut Document) -> Result<(), Box<dyn Error>> {
  document.visit_mut_with(&mut Selector::new());
  Ok(())
}

fn swc_parse() -> Result<Document, Box<dyn Error>> {
  let cm = Lrc::new(SourceMap::new(FilePathMapping::empty()));
  let input = Path::new("input.html");
  let fm = cm.load_file(input).unwrap();

  let mut errors = vec![];
  let document = parse_file_as_document(
      &fm,
      ParserConfig {
          ..Default::default()
      },
      &mut errors,
  )
  .unwrap();

  for err in take(&mut errors) {
      eprintln!("{:?}", err);
  }

  Ok(document)
}

fn swc() -> Result<(), Box<dyn Error>> {
  let mut document = swc_parse()?;
  swc_modifier(&mut document)?;
  Ok(())
}

And lol_html is:

• 👼 backed by CloudFlare and used internally, most trustable
• 👼 DOM like manipulation API design with querySelector support, easy to use
• 👼 well-documented
• 👿 no AST support, from string to string. but we can either batch the operation or just run multiple times as the performance is good enough
• 👿 no minifier support

let input = read_file();
let input_str = String::from_utf8(input).unwrap();
let output = rewrite_str(
  &input_str,
  Settings {
      element_content_handlers: vec![element!("body", |el| {
          el.append(
              format!("<script src=\"!add_{i}\"></script>").as_str(),
              lol_html::html_content::ContentType::Html,
          );
          Ok(())
      })],
      ..Default::default()
  },
)
.unwrap()

Minimizer

Minimizer is not required as

• it usually creates not spec-complaint html.
• lots of website doesn't serve minified html.
• We don't need it to minify js or css code as they are handled in their own loader.

Candidates

• minify_html

  • good performance
  • operates on text

• swc_html_minifier

  • good performance
  • operates on the AST generated from swc_html, so we cannot use it standalone

minify with default option (as the result, minify-html is smaller in size)

test tests::bench_minify ... bench:     199,657 ns/iter (+/- 39,932)
test tests::bench_swc.   ... bench:     471,368 ns/iter (+/- 35,362)

Choice

If we choose swc_html, we can use swc_html_minifier together.

If we use lol_html, and we need a minifier, we can use minify_html.

API Design

Do we need to wrap detailed implementation to low level, and create an abstract layer to plugin user?

• 👼 If we future change the dependencies to another, no user code is need to update
• 😈 we need some extra work to create a compatible layer, actually, very hard, likely as hard as implementing query selector on top of swc_html

Core API

core api works with or without abstract layer

• modify_ast

  • directly hook into the parser / visitor.

• modify_text

  • directly receive the current HTML document as text
  • we create the text based on the current ast
  • ... and convert back to document after that

Shortcuts

shortcuts api works only with abstract layer, as we need to recreate element and their attribute presentation and implement the operation methods. Something like:

struct CustomElement {
    tag_name: String,
    attributes: HashMap<String, String>,
    children: Option<()>,
}

impl CustomElement {
    fn new() -> CustomElement {
        return CustomElement {
            tag_name: "xxx".into(),
            attributes: HashMap::new(),
            children: Some(()),
        };
    }
}

• for_each_scripts
• for_each_assets
• append_to_body
• append_to_head

Conclusion

• ? use swc_html or lol_html
• ? abstract the operation layer or not
• optionally support JS plugin to do template compile / inject runtime
• optionally support HTML minimization