cmark

My personal build of CMark ✏️

Commit: ade396db95e2fcfef4d1769850f4a322e175981b
Parent: 2994011ce13f3a437c637dcac6bc841b22d80b6c
Author: Nick Wellnhofer <wellnhofer@aevum.de>
Date: Tue, 9 Mar 2021 13:11:45 +0100

Fix quadratic behavior when parsing inlines

The inline parsing code would call cmark_node_append_child to append nodes. This public function has a sanity check which is linear in the depth of the tree. Repeated calls could show quadratic behavior in degenerate trees. Use a special function to append nodes without this check.

Fixes #373. Found by OSS-Fuzz.

Diffstat

1 file changed, 24 insertions, 4 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	src/inlines.c	28	24	4

diff --git a/src/inlines.c b/src/inlines.c
@@ -129,6 +129,24 @@ static cmark_node *make_str_with_entities(subject *subj,
   }
 }
 
+// Like cmark_node_append_child but without costly sanity checks.
+// Assumes that child was newly created.
+static void append_child(cmark_node *node, cmark_node *child) {
+  cmark_node *old_last_child = node->last_child;
+
+  child->next = NULL;
+  child->prev = old_last_child;
+  child->parent = node;
+  node->last_child = child;
+
+  if (old_last_child) {
+    old_last_child->next = child;
+  } else {
+    // Also set first_child if node previously had no children.
+    node->first_child = child;
+  }
+}
+
 // Duplicate a chunk by creating a copy of the buffer not by reusing the
 // buffer like cmark_chunk_dup does.
 static unsigned char *cmark_strdup(cmark_mem *mem, unsigned char *src) {
@@ -163,7 +181,7 @@ static CMARK_INLINE cmark_node *make_autolink(subject *subj,
   link->start_line = link->end_line = subj->line;
   link->start_column = start_column + 1;
   link->end_column = end_column + 1;
-  cmark_node_append_child(link, make_str_with_entities(subj, start_column + 1, end_column - 1, &url));
+  append_child(link, make_str_with_entities(subj, start_column + 1, end_column - 1, &url));
   return link;
 }
 
@@ -741,7 +759,8 @@ static delimiter *S_insert_emph(subject *subj, delimiter *opener,
   tmp = opener_inl->next;
   while (tmp && tmp != closer_inl) {
     tmpnext = tmp->next;
-    cmark_node_append_child(emph, tmp);
+    cmark_node_unlink(tmp);
+    append_child(emph, tmp);
     tmp = tmpnext;
   }
   cmark_node_insert_after(opener_inl, emph);
@@ -1121,7 +1140,8 @@ match:
   tmp = opener->inl_text->next;
   while (tmp) {
     tmpnext = tmp->next;
-    cmark_node_append_child(inl, tmp);
+    cmark_node_unlink(tmp);
+    append_child(inl, tmp);
     tmp = tmpnext;
   }
 
@@ -1289,7 +1309,7 @@ static int parse_inline(subject *subj, cmark_node *parent, int options) {
     new_inl = make_str(subj, startpos, endpos - 1, contents);
   }
   if (new_inl != NULL) {
-    cmark_node_append_child(parent, new_inl);
+    append_child(parent, new_inl);
   }
 
   return 1;