Add `no_std + alloc`

22 files changed, 38 insertions, 3 deletions

diff --git a/readme.md b/readme.md
index caf447d..dc7e30f 100644
--- a/readme.md
+++ b/readme.md
@@ -24,7 +24,6 @@ Crate docs are currently at
 
 ### Misc
 
-- [ ] (3) `no_std`?
 - [ ] (?) Improve document performance (potential 50%)
 - [ ] (?) Improve paragraph performance (potential 15%)
 - [ ] (?) Improve label (link, image) performance (potential 7%)
diff --git a/src/compiler.rs b/src/compiler.rs
index a5b2bf5..bb08745 100644
--- a/src/compiler.rs
+++ b/src/compiler.rs
@@ -10,7 +10,13 @@ use crate::util::{
     slice::{Position, Slice},
 };
 use crate::{LineEnding, Options};
-use std::str;
+use alloc::{
+    format,
+    string::{String, ToString},
+    vec,
+    vec::Vec,
+};
+use core::str;
 
 /// Link or image, resource or reference.
 /// Reused for temporary definitions as well, in the first pass.
diff --git a/src/constant.rs b/src/constant.rs
index 45853a7..0c82378 100644
--- a/src/constant.rs
+++ b/src/constant.rs
@@ -2404,6 +2404,7 @@ pub const CHARACTER_REFERENCES: [(&str, &str); 2125] = [
 #[cfg(test)]
 mod tests {
     use super::*;
+    use alloc::format;
 
     #[test]
     fn constants() {
diff --git a/src/construct/attention.rs b/src/construct/attention.rs
index 21407b7..8df0f61 100644
--- a/src/construct/attention.rs
+++ b/src/construct/attention.rs
@@ -64,6 +64,7 @@ use crate::state::{Name as StateName, State};
 use crate::tokenizer::Tokenizer;
 use crate::unicode::PUNCTUATION;
 use crate::util::slice::Slice;
+use alloc::{string::String, vec, vec::Vec};
 
 /// Character code kinds.
 #[derive(Debug, PartialEq)]
diff --git a/src/construct/document.rs b/src/construct/document.rs
index 2cc170d..4ef6acc 100644
--- a/src/construct/document.rs
+++ b/src/construct/document.rs
@@ -13,6 +13,7 @@ use crate::state::{Name as StateName, State};
 use crate::subtokenize::divide_events;
 use crate::tokenizer::{Container, ContainerState, Tokenizer};
 use crate::util::skip;
+use alloc::{boxed::Box, vec::Vec};
 
 /// Phases where we can exit containers.
 #[derive(Debug, PartialEq)]
diff --git a/src/construct/heading_atx.rs b/src/construct/heading_atx.rs
index 960ae32..4ff0143 100644
--- a/src/construct/heading_atx.rs
+++ b/src/construct/heading_atx.rs
@@ -68,6 +68,7 @@ use crate::event::{Content, Event, Kind, Link, Name};
 use crate::resolve::Name as ResolveName;
 use crate::state::{Name as StateName, State};
 use crate::tokenizer::Tokenizer;
+use alloc::vec;
 
 /// Start of a heading (atx).
 ///
diff --git a/src/construct/heading_setext.rs b/src/construct/heading_setext.rs
index bad781c..3adeb38 100644
--- a/src/construct/heading_setext.rs
+++ b/src/construct/heading_setext.rs
@@ -76,6 +76,7 @@ use crate::resolve::Name as ResolveName;
 use crate::state::{Name as StateName, State};
 use crate::tokenizer::Tokenizer;
 use crate::util::skip::opt_back as skip_opt_back;
+use alloc::vec;
 
 /// At start of heading (setext) underline.
 ///
diff --git a/src/construct/label_end.rs b/src/construct/label_end.rs
index 5e31444..41f16d7 100644
--- a/src/construct/label_end.rs
+++ b/src/construct/label_end.rs
@@ -169,6 +169,7 @@ use crate::util::{
     skip,
     slice::{Position, Slice},
 };
+use alloc::vec;
 
 /// Start of label end.
 ///
diff --git a/src/construct/list_item.rs b/src/construct/list_item.rs
index 3e632fb..13c287a 100644
--- a/src/construct/list_item.rs
+++ b/src/construct/list_item.rs
@@ -68,6 +68,7 @@ use crate::util::{
     skip,
     slice::{Position, Slice},
 };
+use alloc::{vec, vec::Vec};
 
 /// Start of list item.
 ///
diff --git a/src/construct/paragraph.rs b/src/construct/paragraph.rs
index 0ddd0c4..9e20643 100644
--- a/src/construct/paragraph.rs
+++ b/src/construct/paragraph.rs
@@ -44,6 +44,7 @@ use crate::event::{Content, Kind, Link, Name};
 use crate::resolve::Name as ResolveName;
 use crate::state::{Name as StateName, State};
 use crate::tokenizer::Tokenizer;
+use alloc::vec;
 
 /// Before paragraph.
 ///
diff --git a/src/construct/partial_data.rs b/src/construct/partial_data.rs
index 19f5f3b..bc6d7f4 100644
--- a/src/construct/partial_data.rs
+++ b/src/construct/partial_data.rs
@@ -10,6 +10,7 @@ use crate::event::{Kind, Name};
 use crate::resolve::Name as ResolveName;
 use crate::state::{Name as StateName, State};
 use crate::tokenizer::Tokenizer;
+use alloc::vec;
 
 /// At beginning of data.
 ///
diff --git a/src/construct/partial_whitespace.rs b/src/construct/partial_whitespace.rs
index faaff73..707107d 100644
--- a/src/construct/partial_whitespace.rs
+++ b/src/construct/partial_whitespace.rs
@@ -61,6 +61,7 @@ use crate::constant::HARD_BREAK_PREFIX_SIZE_MIN;
 use crate::event::{Event, Kind, Name};
 use crate::tokenizer::Tokenizer;
 use crate::util::slice::{Position, Slice};
+use alloc::vec;
 
 /// Resolve whitespace.
 pub fn resolve_whitespace(tokenizer: &mut Tokenizer, hard_break: bool, trim_whole: bool) {
diff --git a/src/lib.rs b/src/lib.rs
index 428838a..00f1c5c 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -4,6 +4,10 @@
 //! `micromark` is a safe way to transform (untrusted?) markdown into HTML.
 //! `micromark_with_options` allows you to configure how markdown is turned into
 //! HTML, such as by allowing dangerous HTML when you trust it.
+#![no_std]
+
+extern crate alloc;
+
 mod compiler;
 mod constant;
 mod construct;
@@ -18,6 +22,7 @@ mod util;
 
 use crate::compiler::compile;
 use crate::parser::parse;
+use alloc::string::String;
 
 /// Type of line endings in markdown.
 #[derive(Clone, Debug, Default, Eq, PartialEq)]
diff --git a/src/parser.rs b/src/parser.rs
index 8b13d45..404fd0f 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -5,6 +5,7 @@ use crate::state::{Name as StateName, State};
 use crate::subtokenize::subtokenize;
 use crate::tokenizer::Tokenizer;
 use crate::{Constructs, Options};
+use alloc::{string::String, vec, vec::Vec};
 
 /// Info needed, in all content types, when parsing markdown.
 ///
diff --git a/src/subtokenize.rs b/src/subtokenize.rs
index a031e35..5932f11 100644
--- a/src/subtokenize.rs
+++ b/src/subtokenize.rs
@@ -22,6 +22,7 @@ use crate::parser::ParseState;
 use crate::state::{Name as StateName, State};
 use crate::tokenizer::Tokenizer;
 use crate::util::edit_map::EditMap;
+use alloc::{vec, vec::Vec};
 
 /// Link two [`Event`][]s.
 ///
diff --git a/src/tokenizer.rs b/src/tokenizer.rs
index 2edab03..1e99771 100644
--- a/src/tokenizer.rs
+++ b/src/tokenizer.rs
@@ -14,6 +14,7 @@ use crate::parser::ParseState;
 use crate::resolve::{call as call_resolve, Name as ResolveName};
 use crate::state::{call, State};
 use crate::util::edit_map::EditMap;
+use alloc::{boxed::Box, string::String, vec, vec::Vec};
 
 /// Containers.
 ///
diff --git a/src/util/decode_character_reference.rs b/src/util/decode_character_reference.rs
index 8ed32f4..30b7853 100644
--- a/src/util/decode_character_reference.rs
+++ b/src/util/decode_character_reference.rs
@@ -1,6 +1,7 @@
 //! Decode character references.
 
 use crate::constant::CHARACTER_REFERENCES;
+use alloc::string::{String, ToString};
 
 /// Decode named character references.
 ///
diff --git a/src/util/edit_map.rs b/src/util/edit_map.rs
index 33c5706..91c93d4 100644
--- a/src/util/edit_map.rs
+++ b/src/util/edit_map.rs
@@ -9,6 +9,7 @@
 //! through another tokenizer and inject the result.
 
 use crate::event::Event;
+use alloc::{vec, vec::Vec};
 
 /// Shift `previous` and `next` links according to `jumps`.
 ///
diff --git a/src/util/encode.rs b/src/util/encode.rs
index 6530011..98b3bcb 100644
--- a/src/util/encode.rs
+++ b/src/util/encode.rs
@@ -1,5 +1,7 @@
 //! Encode HTML.
 
+use alloc::string::String;
+
 /// Encode dangerous html characters.
 ///
 /// This ensures that certain characters which have special meaning in HTML are
diff --git a/src/util/normalize_identifier.rs b/src/util/normalize_identifier.rs
index ddc51f8..2f73bfa 100644
--- a/src/util/normalize_identifier.rs
+++ b/src/util/normalize_identifier.rs
@@ -1,5 +1,7 @@
 //! Normalize identifiers.
 
+use alloc::string::String;
+
 /// Normalize an identifier, as found in [references][label_end] and
 /// [definitions][definition], so it can be compared when matching.
 ///
diff --git a/src/util/sanitize_uri.rs b/src/util/sanitize_uri.rs
index 593a70e..969a4d8 100644
--- a/src/util/sanitize_uri.rs
+++ b/src/util/sanitize_uri.rs
@@ -1,6 +1,11 @@
 //! Make urls safe.
 
 use crate::util::encode::encode;
+use alloc::{
+    format,
+    string::{String, ToString},
+    vec::Vec,
+};
 
 /// Make a value safe for injection as a URL.
 ///
diff --git a/src/util/slice.rs b/src/util/slice.rs
index be2a381..5dcc352 100644
--- a/src/util/slice.rs
+++ b/src/util/slice.rs
@@ -2,7 +2,8 @@
 
 use crate::constant::TAB_SIZE;
 use crate::event::{Event, Kind, Point};
-use std::str;
+use alloc::string::String;
+use core::str;
 
 /// A range between two points.
 #[derive(Debug)]