Remove RcDom, use FlatDom for recursive format

hansihe · hansihe · commit f6743865c353 · 2019-12-03T08:55:55.000+01:00
* Recursive encoder is now iterative instead of recursive, preventing
stack overflows.
diff --git a/lib/html5ever.ex b/lib/html5ever.ex
@@ -17,18 +17,18 @@ defmodule Html5ever do
     flat_parse_sync(html)
   end
 
-  defp parse_async(html) do
-    Html5ever.Native.parse_async(html)
-    receive do
+  defp parse_sync(html) do
+    case Html5ever.Native.parse_sync(html) do
       {:html5ever_nif_result, :ok, result} ->
         {:ok, result}
       {:html5ever_nif_result, :error, err} ->
         {:error, err}
     end
   end
 
-  defp parse_sync(html) do
-    case Html5ever.Native.parse_sync(html) do
+  defp parse_async(html) do
+    :ok = Html5ever.Native.parse_async(html)
+    receive do
       {:html5ever_nif_result, :ok, result} ->
         {:ok, result}
       {:html5ever_nif_result, :error, err} ->
@@ -46,7 +46,8 @@ defmodule Html5ever do
   end
 
   defp flat_parse_async(html) do
-    case Html5ever.Native.flat_parse_sync(html) do
+    :ok = Html5ever.Native.flat_parse_async(html)
+    receive do
       {:html5ever_nif_result, :ok, result} ->
         {:ok, result}
       {:html5ever_nif_result, :error, err} ->
diff --git a/lib/html5ever/native.ex b/lib/html5ever/native.ex
@@ -5,9 +5,10 @@ end
 defmodule Html5ever.Native do
   use Rustler, otp_app: :html5ever, crate: "html5ever_nif"
 
-  def parse_async(_binary), do: err()
   def parse_sync(_binary), do: err()
+  def parse_async(_binary), do: err()
   def flat_parse_sync(_binary), do: err()
+  def flat_parse_async(_binary), do: err()
 
   defp err() do
     throw NifNotLoadedError
diff --git a/native/html5ever_nif/Cargo.toml b/native/html5ever_nif/Cargo.toml
@@ -12,8 +12,8 @@ crate-type = ["dylib"]
 [dependencies]
 rustler = "^0.21"
 
-html5ever = "0.22"
-markup5ever = "0.7"
+html5ever = "0.25"
+markup5ever = "0.10"
 
 tendril = "0.4"
 lazy_static = "1.4"
diff --git a/native/html5ever_nif/src/flat_dom.rs b/native/html5ever_nif/src/flat_dom.rs
@@ -31,7 +31,7 @@ impl Node {
     }
 }
 
-#[derive(Debug)]
+#[derive(Debug, PartialEq)]
 pub enum NodeData{
     Document,
     DocType {
@@ -77,6 +77,10 @@ impl FlatSink {
         sink
     }
 
+    pub fn root(&self) -> NodeHandle {
+        self.root
+    }
+
     pub fn node_mut<'a>(&'a mut self, handle: NodeHandle) -> &'a mut Node {
         &mut self.nodes[handle.0]
     }
@@ -309,7 +313,7 @@ mod atoms {
     }
 }
 
-pub fn flat_sink_to_term<'a>(env: Env<'a>, sink: &FlatSink) -> Term<'a> {
+pub fn flat_sink_to_flat_term<'a>(env: Env<'a>, sink: &FlatSink) -> Term<'a> {
     let nodes = sink.nodes.iter()
         .fold(rustler::types::map::map_new(env), |acc, node| {
             acc.map_put(node.id.encode(env), node.encode(env)).ok().unwrap()
@@ -319,3 +323,89 @@ pub fn flat_sink_to_term<'a>(env: Env<'a>, sink: &FlatSink) -> Term<'a> {
         .map_put(self::atoms::nodes().encode(env), nodes).ok().unwrap()
         .map_put(self::atoms::root().encode(env), sink.root.encode(env)).ok().unwrap()
 }
+
+struct RecState<'a> {
+    node: NodeHandle,
+    child_n: usize,
+
+    children: Vec<Term<'a>>,
+}
+
+pub fn flat_sink_to_rec_term<'a>(env: Env<'a>, sink: &FlatSink) -> Term<'a> {
+    let mut stack: Vec<RecState> = vec![
+        RecState {
+            node: sink.root(),
+            child_n: 0,
+            children: Vec::new(),
+        },
+    ];
+
+    loop {
+        let mut top = stack.pop().unwrap();
+        let top_node = &sink.nodes[top.node.0];
+
+        if let Some(child_node) = top_node.children.get(top.child_n) {
+            // If we find another child, we recurse downwards
+
+            let child = RecState {
+                node: *child_node,
+                child_n: 0,
+                children: Vec::new(),
+            };
+            debug_assert!(sink.nodes[child_node.0].data != NodeData::Document);
+
+            top.child_n += 1;
+            stack.push(top);
+            stack.push(child);
+            continue;
+        } else {
+            // If there are no more children, we add the child to the parent
+            // (or we return if we are the root)
+
+            let term;
+
+            match &top_node.data {
+                NodeData::Document => {
+                    let term = top.children.encode(env);
+                    assert_eq!(stack.len(), 0);
+                    return term;
+                },
+                NodeData::DocType { name, public_id, system_id }  => {
+                    assert!(stack.len() > 0);
+                    assert!(top.children.len() == 0);
+
+                    term = (
+                        self::atoms::doctype(),
+                        STW(name),
+                        STW(public_id),
+                        STW(system_id),
+                    ).encode(env);
+                },
+                NodeData::Element { attrs, name, .. } => {
+                    assert!(stack.len() > 0);
+
+                    let attribute_terms: Vec<Term<'a>> = attrs.iter()
+                        .map(|a| (QNW(&a.name), STW(&a.value)).encode(env))
+                        .collect();
+                    term = (QNW(name), attribute_terms, top.children).encode(env);
+                },
+                NodeData::Text { contents } => {
+                    term = STW(contents).encode(env);
+                },
+                NodeData::Comment { .. } => continue,
+                _ => unimplemented!("{:?}", top_node),
+            }
+
+            stack.last_mut().unwrap().children.push(term);
+        }
+    }
+}
+
+
+
+
+
+
+
+
+
diff --git a/native/html5ever_nif/src/lib.rs b/native/html5ever_nif/src/lib.rs
@@ -6,12 +6,11 @@ use rustler::env::OwnedEnv;
 use rustler::types::binary::Binary;
 use rustler::{Decoder, Encoder, Env, Error, NifResult, Term, rustler_export_nifs};
 
-use html5ever::rcdom::RcDom;
+//use html5ever::rcdom::RcDom;
 use tendril::TendrilSink;
 
 mod common;
 mod flat_dom;
-mod rc_dom;
 
 mod atoms {
     rustler::rustler_atoms! {
@@ -56,6 +55,21 @@ lazy_static! {
     static ref POOL: scoped_pool::Pool = scoped_pool::Pool::new(4);
 }
 
+fn parse_sync<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
+    let binary: Binary = args[0].decode()?;
+    let sink = flat_dom::FlatSink::new();
+
+    // TODO: Use Parser.from_bytes instead?
+    let parser = html5ever::parse_document(sink, Default::default());
+    let result = parser.one(std::str::from_utf8(binary.as_slice()).unwrap());
+
+    // std::thread::sleep(std::time::Duration::from_millis(10));
+
+    let result_term = flat_dom::flat_sink_to_rec_term(env, &result);
+
+    Ok((atoms::html5ever_nif_result(), atoms::ok(), result_term).encode(env))
+}
+
 fn parse_async<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
     let mut owned_env = OwnedEnv::new();
 
@@ -78,17 +92,17 @@ fn parse_async<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
                     Err(_) => panic!("argument is not a binary"),
                 };
 
-                let sink = RcDom::default();
+                let sink = flat_dom::FlatSink::new();
 
                 // TODO: Use Parser.from_bytes instead?
                 let parser = html5ever::parse_document(sink, Default::default());
                 let result = parser.one(std::str::from_utf8(binary.as_slice()).unwrap());
 
-                let result_term = rc_dom::handle_to_term(inner_env, &result.document);
+                let result_term = flat_dom::flat_sink_to_rec_term(inner_env, &result);
                 (
                     atoms::html5ever_nif_result(),
                     atoms::ok(),
-                    result_term.unwrap(),
+                    result_term,
                 ).encode(inner_env)
             }) {
                 Ok(term) => term,
@@ -111,46 +125,83 @@ fn parse_async<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
     Ok(atoms::ok().encode(env))
 }
 
-fn parse_sync<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
+fn flat_parse_sync<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
     let binary: Binary = args[0].decode()?;
-    let sink = RcDom::default();
+    let sink = flat_dom::FlatSink::new();
 
     // TODO: Use Parser.from_bytes instead?
     let parser = html5ever::parse_document(sink, Default::default());
     let result = parser.one(std::str::from_utf8(binary.as_slice()).unwrap());
 
     // std::thread::sleep(std::time::Duration::from_millis(10));
 
-    let result_term = rc_dom::handle_to_term(env, &result.document);
+    let result_term = flat_dom::flat_sink_to_flat_term(env, &result);
 
-    Ok((
-        atoms::html5ever_nif_result(),
-        atoms::ok(),
-        result_term.unwrap(),
-    ).encode(env))
+    Ok((atoms::html5ever_nif_result(), atoms::ok(), result_term).encode(env))
 }
 
-fn flat_parse_sync<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
-    let binary: Binary = args[0].decode()?;
-    let sink = flat_dom::FlatSink::new();
+fn flat_parse_async<'a>(env: Env<'a>, args: &[Term<'a>]) -> NifResult<Term<'a>> {
+    let mut owned_env = OwnedEnv::new();
 
-    // TODO: Use Parser.from_bytes instead?
-    let parser = html5ever::parse_document(sink, Default::default());
-    let result = parser.one(std::str::from_utf8(binary.as_slice()).unwrap());
+    // Copies the term into the inner env. Since this term is normally a large
+    // binary term, copying it over should be cheap, since the binary will be
+    // refcounted within the BEAM.
+    let input_term = owned_env.save(args[0]);
 
-    // std::thread::sleep(std::time::Duration::from_millis(10));
+    let return_pid = env.pid();
 
-    let result_term = flat_dom::flat_sink_to_term(env, &result);
+    // let config = term_to_configs(args[1]);
 
-    Ok((atoms::html5ever_nif_result(), atoms::ok(), result_term).encode(env))
+    POOL.spawn(move || {
+        owned_env.send_and_clear(&return_pid, |inner_env| {
+            // This should not really be done in user code. We (Rustler project)
+            // need to find a better abstraction that eliminates this.
+            match panic::catch_unwind(|| {
+                let binary: Binary = match input_term.load(inner_env).decode() {
+                    Ok(inner) => inner,
+                    Err(_) => panic!("argument is not a binary"),
+                };
+
+                let sink = flat_dom::FlatSink::new();
+
+                // TODO: Use Parser.from_bytes instead?
+                let parser = html5ever::parse_document(sink, Default::default());
+                let result = parser.one(std::str::from_utf8(binary.as_slice()).unwrap());
+
+                let result_term = flat_dom::flat_sink_to_flat_term(inner_env, &result);
+                (
+                    atoms::html5ever_nif_result(),
+                    atoms::ok(),
+                    result_term,
+                ).encode(inner_env)
+            }) {
+                Ok(term) => term,
+                Err(err) => {
+                    // Try to extract a panic reason and return that. If this
+                    // fails, fail generically.
+                    let reason = if let Some(s) = err.downcast_ref::<String>() {
+                        s.encode(inner_env)
+                    } else if let Some(&s) = err.downcast_ref::<&'static str>() {
+                        s.encode(inner_env)
+                    } else {
+                        atoms::nif_panic().encode(inner_env)
+                    };
+                    (atoms::html5ever_nif_result(), atoms::error(), reason).encode(inner_env)
+                }
+            }
+        });
+    });
+
+    Ok(atoms::ok().encode(env))
 }
 
 rustler_export_nifs!(
     "Elixir.Html5ever.Native",
     [
-        ("parse_async", 1, parse_async),
         ("parse_sync", 1, parse_sync),
-        ("flat_parse_sync", 1, flat_parse_sync)
+        ("parse_async", 1, parse_async),
+        ("flat_parse_sync", 1, flat_parse_sync),
+        ("flat_parse_async", 1, flat_parse_async)
     ],
     Some(on_load)
 );
diff --git a/native/html5ever_nif/src/rc_dom.rs b/native/html5ever_nif/src/rc_dom.rs
