Simplify stack management by popping in bulk at higher levels

Since all memory used by the reader is POD in the stack, there is no benefit to
forcing code to explicitly pop everything pushed to the stack, since any
function can record an offset and pop back down to it regardless of what its
callers pushed if it knows that it does not need those items.

This is slightly more efficient (due to avoiding many pop calls), but also more
resilient since "leaks" at deeper levels of recursion get nuked by some caller
regardless of what was pushed.  This should help prevent future regressions
like f6437f606 (Fix memory consumption when reading documents).

4 files changed, 55 insertions, 139 deletions

diff --git a/src/n3.c b/src/n3.c
index e35b8940..36f90c4f 100644
--- a/src/n3.c
+++ b/src/n3.c
@@ -740,7 +740,6 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
   *dest = push_node(reader, SERD_URI, "", 0);
 
   if (!fancy_syntax(reader) && read_IRIREF_scheme(reader, *dest)) {
-    *dest = pop_node(reader, *dest);
     return r_err(reader, SERD_BAD_SYNTAX, "expected IRI scheme\n");
   }
 
@@ -751,24 +750,18 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
     switch (c) {
     case '"':
     case '<':
-      *dest = pop_node(reader, *dest);
       return r_err(reader, SERD_BAD_SYNTAX, "invalid IRI character '%c'\n", c);
-
     case '>':
       return SERD_SUCCESS;
-
     case '\\':
       if (read_UCHAR(reader, *dest, &code)) {
-        *dest = pop_node(reader, *dest);
         return r_err(reader, SERD_BAD_SYNTAX, "invalid IRI escape\n");
       }
-
       switch (code) {
       case 0:
       case ' ':
       case '<':
       case '>':
-        *dest = pop_node(reader, *dest);
         return r_err(reader,
                      SERD_BAD_SYNTAX,
                      "invalid escaped IRI character U+%04X\n",
@@ -777,15 +770,12 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
         break;
       }
       break;
-
     case '^':
     case '`':
     case '{':
     case '|':
     case '}':
-      *dest = pop_node(reader, *dest);
       return r_err(reader, SERD_BAD_SYNTAX, "invalid IRI character '%c'\n", c);
-
     default:
       if (c <= 0x20) {
         st = r_err(reader,
@@ -802,14 +792,12 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
         push_byte(reader, *dest, c);
       } else if (read_utf8_character(reader, *dest, (uint8_t)c)) {
         if (reader->strict) {
-          *dest = pop_node(reader, *dest);
           return SERD_BAD_SYNTAX;
         }
       }
     }
   }
 
-  *dest = pop_node(reader, *dest);
   return st;
 }
 
@@ -952,7 +940,7 @@ read_literal(SerdReader* const    reader,
 
   SerdStatus st = read_String(reader, *dest, flags);
   if (st) {
-    *dest = pop_node(reader, *dest);
+    *dest = NULL;
     return st;
   }
 
@@ -961,10 +949,7 @@ read_literal(SerdReader* const    reader,
     skip_byte(reader, '@');
     *flags |= SERD_HAS_LANGUAGE;
     if ((st = read_LANGTAG(reader, lang))) {
-      *datatype = pop_node(reader, *datatype);
-      *lang     = pop_node(reader, *lang);
-      *dest     = pop_node(reader, *dest);
-      return r_err(reader, st, "bad language tag\n");
+      return r_err(reader, st, "bad literal\n");
     }
     break;
   case '^':
@@ -975,9 +960,6 @@ read_literal(SerdReader* const    reader,
 
     *flags |= SERD_HAS_DATATYPE;
     if ((st = read_iri(reader, datatype, ate_dot))) {
-      *datatype = pop_node(reader, *datatype);
-      *lang     = pop_node(reader, *lang);
-      *dest     = pop_node(reader, *dest);
       return r_err(reader, st, "bad datatype\n");
     }
     break;
@@ -988,6 +970,7 @@ read_literal(SerdReader* const    reader,
 static SerdStatus
 read_verb(SerdReader* const reader, SerdNode** const dest)
 {
+  const size_t orig_stack_size = reader->stack.size;
   if (peek_byte(reader) == '<') {
     return read_IRIREF(reader, dest);
   }
@@ -1005,14 +988,14 @@ read_verb(SerdReader* const reader, SerdNode** const dest)
   const int  next    = peek_byte(reader);
   if (!st && node->length == 1 && serd_node_string(node)[0] == 'a' &&
       next != ':' && !is_PN_CHARS_BASE((uint32_t)next)) {
-    pop_node(reader, *dest);
+    serd_stack_pop_to(&reader->stack, orig_stack_size);
     *dest = push_node(reader, SERD_URI, NS_RDF "type", 47);
     return SERD_SUCCESS;
   }
 
   if (st > SERD_FAILURE ||
       (st = read_PrefixedName(reader, *dest, false, &ate_dot)) || ate_dot) {
-    *dest = pop_node(reader, *dest);
+    *dest = NULL;
     st    = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
     return r_err(reader, st, "bad verb\n");
   }
@@ -1041,8 +1024,7 @@ read_BLANK_NODE_LABEL(SerdReader* const reader,
   if (is_digit(c) || c == '_') {
     push_byte(reader, n, eat_byte_safe(reader, c));
   } else if ((st = read_PN_CHARS(reader, n))) {
-    st    = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
-    *dest = pop_node(reader, n);
+    st = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
     return r_err(reader, st, "invalid name start\n");
   }
 
@@ -1072,7 +1054,6 @@ read_BLANK_NODE_LABEL(SerdReader* const reader,
         buf[reader->bprefix_len] = 'B'; // Prevent clash
         reader->seen_genid       = true;
       } else if (reader->seen_genid && buf[reader->bprefix_len] == 'B') {
-        *dest = pop_node(reader, n);
         return r_err(reader,
                      SERD_BAD_LABEL,
                      "found both 'b' and 'B' blank IDs, prefix required\n");
@@ -1145,9 +1126,7 @@ read_object(SerdReader* const  reader,
   static const char* const XSD_BOOLEAN     = NS_XSD "boolean";
   static const size_t      XSD_BOOLEAN_LEN = 40;
 
-#ifndef NDEBUG
   const size_t orig_stack_size = reader->stack.size;
-#endif
 
   SerdStatus st = SERD_FAILURE;
 
@@ -1227,7 +1206,6 @@ read_object(SerdReader* const  reader,
     } else {
       if ((st = read_PrefixedName(reader, o, false, ate_dot))) {
         st = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
-        pop_node(reader, o);
         return r_err(reader, st, "expected prefixed name\n");
       }
     }
@@ -1246,9 +1224,7 @@ read_object(SerdReader* const  reader,
     return SERD_SUCCESS;
   }
 
-  pop_node(reader, lang);
-  pop_node(reader, datatype);
-  pop_node(reader, o);
+  serd_stack_pop_to(&reader->stack, orig_stack_size);
 #ifndef NDEBUG
   assert(reader->stack.size == orig_stack_size);
 #endif
@@ -1277,11 +1253,13 @@ read_predicateObjectList(SerdReader* const reader,
                          ReadContext       ctx,
                          bool* const       ate_dot)
 {
+  const size_t orig_stack_size = reader->stack.size;
+
   SerdStatus st = SERD_SUCCESS;
   while (!(st = read_verb(reader, &ctx.predicate)) && read_ws_star(reader) &&
          !(st = read_objectList(reader, ctx, ate_dot))) {
-    ctx.predicate = pop_node(reader, ctx.predicate);
     if (*ate_dot) {
+      serd_stack_pop_to(&reader->stack, orig_stack_size);
       return SERD_SUCCESS;
     }
 
@@ -1291,10 +1269,12 @@ read_predicateObjectList(SerdReader* const reader,
       read_ws_star(reader);
       switch (c = peek_byte(reader)) {
       case EOF:
+        serd_stack_pop_to(&reader->stack, orig_stack_size);
         return r_err(reader, SERD_BAD_SYNTAX, "unexpected end of file\n");
       case '.':
       case ']':
       case '}':
+        serd_stack_pop_to(&reader->stack, orig_stack_size);
         return SERD_SUCCESS;
       case ';':
         skip_byte(reader, c);
@@ -1303,29 +1283,24 @@ read_predicateObjectList(SerdReader* const reader,
     } while (c == ';');
 
     if (!ate_semi) {
+      serd_stack_pop_to(&reader->stack, orig_stack_size);
       return r_err(reader, SERD_BAD_SYNTAX, "missing ';' or '.'\n");
     }
   }
 
-  ctx.predicate = pop_node(reader, ctx.predicate);
+  serd_stack_pop_to(&reader->stack, orig_stack_size);
+  ctx.predicate = 0;
   return st;
 }
 
 static SerdStatus
-end_collection(SerdReader* const reader,
-               const ReadContext ctx,
-               SerdNode* const   n1,
-               SerdNode* const   n2,
-               const SerdStatus  st)
+end_collection(SerdReader* const reader, ReadContext ctx, const SerdStatus st)
 {
-  pop_node(reader, n2);
-  pop_node(reader, n1);
   *ctx.flags &= ~(unsigned)SERD_LIST_CONT;
   if (!st) {
     return (eat_byte_check(reader, ')') == ')') ? SERD_SUCCESS
                                                 : SERD_BAD_SYNTAX;
   }
-
   return st;
 }
 
@@ -1351,14 +1326,13 @@ read_collection(SerdReader* const reader,
   }
 
   if (end) {
-    return end_collection(reader, ctx, 0, 0, st);
+    return end_collection(reader, ctx, st);
   }
 
   /* The order of node allocation here is necessarily not in stack order,
      so we create two nodes and recycle them throughout. */
   SerdNode* n1 =
     push_node_padded(reader, genid_size(reader), SERD_BLANK, "", 0);
-  SerdNode* n2   = 0;
   SerdNode* node = n1;
   SerdNode* rest = 0;
 
@@ -1372,14 +1346,14 @@ read_collection(SerdReader* const reader,
     ctx.predicate = reader->rdf_first;
     bool ate_dot  = false;
     if ((st = read_object(reader, &ctx, true, &ate_dot)) || ate_dot) {
-      return end_collection(reader, ctx, n1, n2, st);
+      return end_collection(reader, ctx, st);
     }
 
     if (!(end = peek_delim(reader, ')'))) {
       /* Give rest a new ID.  Done as late as possible to ensure it is
          used and > IDs generated by read_object above. */
       if (!rest) {
-        rest = n2 = blank_id(reader); // First pass, push
+        rest = blank_id(reader); // First pass, push
       } else {
         set_blank_id(reader, rest, genid_size(reader));
       }
@@ -1395,7 +1369,7 @@ read_collection(SerdReader* const reader,
     node        = ctx.subject; // invariant
   }
 
-  return end_collection(reader, ctx, n1, n2, st);
+  return end_collection(reader, ctx, st);
 }
 
 static SerdStatus
@@ -1421,7 +1395,6 @@ read_subject(SerdReader* const reader,
   }
 
   if (ate_dot) {
-    pop_node(reader, *dest);
     return r_err(reader, SERD_BAD_SYNTAX, "subject ends with '.'\n");
   }
 
@@ -1485,7 +1458,6 @@ read_base(SerdReader* const reader, const bool sparql, const bool token)
   SerdNode* uri = NULL;
   TRY(st, read_IRIREF(reader, &uri));
   TRY(st, serd_sink_write_base(reader->sink, uri));
-  pop_node(reader, uri);
 
   read_ws_star(reader);
   if (!sparql) {
@@ -1516,7 +1488,6 @@ read_prefixID(SerdReader* const reader, const bool sparql, const bool token)
   TRY_FAILING(st, read_PN_PREFIX(reader, name));
 
   if (eat_byte_check(reader, ':') != ':') {
-    pop_node(reader, name);
     return SERD_BAD_SYNTAX;
   }
 
@@ -1526,8 +1497,6 @@ read_prefixID(SerdReader* const reader, const bool sparql, const bool token)
 
   st = serd_sink_write_prefix(reader->sink, name, uri);
 
-  pop_node(reader, uri);
-  pop_node(reader, name);
   if (!sparql) {
     read_ws_star(reader);
     st = eat_byte_check(reader, '.') ? SERD_SUCCESS : SERD_BAD_SYNTAX;
@@ -1571,8 +1540,10 @@ read_wrappedGraph(SerdReader* const reader, ReadContext* const ctx)
 
   read_ws_star(reader);
   while (peek_byte(reader) != '}') {
-    bool ate_dot  = false;
-    int  s_type   = 0;
+    const size_t orig_stack_size = reader->stack.size;
+    bool         ate_dot         = false;
+    int          s_type          = 0;
+
     ctx->subject  = 0;
     SerdStatus st = read_subject(reader, *ctx, &ctx->subject, &s_type);
     if (st) {
@@ -1583,7 +1554,7 @@ read_wrappedGraph(SerdReader* const reader, ReadContext* const ctx)
       return r_err(reader, st, "bad predicate object list\n");
     }
 
-    ctx->subject = pop_node(reader, ctx->subject);
+    serd_stack_pop_to(&reader->stack, orig_stack_size);
     read_ws_star(reader);
     if (peek_byte(reader) == '.') {
       skip_byte(reader, '.');
@@ -1611,10 +1582,6 @@ tokcmp(SerdNode* const node, const char* const tok, const size_t n)
 SerdStatus
 read_n3_statement(SerdReader* const reader)
 {
-#ifndef NDEBUG
-  const size_t orig_stack_size = reader->stack.size;
-#endif
-
   SerdStatementFlags flags   = 0;
   ReadContext        ctx     = {0, 0, 0, 0, 0, 0, &flags};
   bool               ate_dot = false;
@@ -1651,12 +1618,11 @@ read_n3_statement(SerdReader* const reader)
     } else if (!tokcmp(ctx.subject, "prefix", 6)) {
       st = read_prefixID(reader, true, false);
     } else if (!tokcmp(ctx.subject, "graph", 5)) {
-      ctx.subject = pop_node(reader, ctx.subject);
+      ctx.subject = NULL;
       read_ws_star(reader);
       TRY(st, read_labelOrSubject(reader, &ctx.graph));
       read_ws_star(reader);
       TRY(st, read_wrappedGraph(reader, &ctx));
-      pop_node(reader, ctx.graph);
       ctx.graph = 0;
       read_ws_star(reader);
     } else if (!tokcmp(ctx.subject, "true", 4) ||
@@ -1667,9 +1633,8 @@ read_n3_statement(SerdReader* const reader)
         return r_err(reader, SERD_BAD_SYNTAX, "invalid graph name\n");
       }
       ctx.graph   = ctx.subject;
-      ctx.subject = 0;
+      ctx.subject = NULL;
       TRY(st, read_wrappedGraph(reader, &ctx));
-      pop_node(reader, ctx.graph);
       read_ws_star(reader);
     } else if ((st = read_triples(reader, ctx, &ate_dot))) {
       if (st == SERD_FAILURE && s_type == '[') {
@@ -1686,15 +1651,9 @@ read_n3_statement(SerdReader* const reader)
       st =
         (eat_byte_check(reader, '.') == '.') ? SERD_SUCCESS : SERD_BAD_SYNTAX;
     }
-
-    ctx.subject = pop_node(reader, ctx.subject);
     break;
   }
 
-#ifndef NDEBUG
-  assert(reader->stack.size == orig_stack_size);
-#endif
-
   return st;
 }
 
@@ -1715,13 +1674,18 @@ SerdStatus
 read_turtleTrigDoc(SerdReader* const reader)
 {
   while (!reader->source.eof) {
-    const SerdStatus st = read_n3_statement(reader);
+    const size_t     orig_stack_size = reader->stack.size;
+    const SerdStatus st              = read_n3_statement(reader);
+
     if (st > SERD_FAILURE) {
       if (reader->strict) {
+        serd_stack_pop_to(&reader->stack, orig_stack_size);
         return st;
       }
       serd_reader_skip_until_byte(reader, '\n');
     }
+
+    serd_stack_pop_to(&reader->stack, orig_stack_size);
   }
 
   return SERD_SUCCESS;
@@ -1775,11 +1739,6 @@ read_nquads_statement(SerdReader* const reader)
 
   TRY(st, emit_statement(reader, ctx, ctx.object));
 
-  pop_node(reader, ctx.graph);
-  pop_node(reader, ctx.lang);
-  pop_node(reader, ctx.datatype);
-  pop_node(reader, ctx.object);
-
   return SERD_SUCCESS;
 }
 
@@ -1789,7 +1748,11 @@ read_nquadsDoc(SerdReader* const reader)
   SerdStatus st = SERD_SUCCESS;
 
   while (!reader->source.eof && !st) {
+    const size_t orig_stack_size = reader->stack.size;
+
     st = read_nquads_statement(reader);
+
+    serd_stack_pop_to(&reader->stack, orig_stack_size);
   }
 
   return st;
diff --git a/src/reader.c b/src/reader.c
index 3b4dfd2b..ae50adab 100644
--- a/src/reader.c
+++ b/src/reader.c
@@ -69,6 +69,13 @@ push_node_padded(SerdReader* const  reader,
                  const char* const  str,
                  const size_t       length)
 {
+  // Push a null byte to ensure the previous node was null terminated
+  char* terminator = (char*)serd_stack_push(&reader->stack, 1);
+  if (!terminator) {
+    return NULL;
+  }
+  *terminator = 0;
+
   void* mem = serd_stack_push_aligned(
     &reader->stack, sizeof(SerdNode) + maxlen + 1, sizeof(SerdNode));
 
@@ -85,12 +92,6 @@ push_node_padded(SerdReader* const  reader,
   char* buf = (char*)(node + 1);
   memcpy(buf, str, length + 1);
 
-#ifdef SERD_STACK_CHECK
-  reader->allocs = (SerdNode**)realloc(
-    reader->allocs, sizeof(reader->allocs) * (++reader->n_allocs));
-  reader->allocs[reader->n_allocs - 1] =
-    (SerdNode*)((char*)mem - reader->stack.buf);
-#endif
   return node;
 }
 
@@ -103,21 +104,6 @@ push_node(SerdReader* const  reader,
   return push_node_padded(reader, length, type, str, length);
 }
 
-SerdNode*
-pop_node(SerdReader* const reader, const SerdNode* const node)
-{
-  if (node && node != reader->rdf_first && node != reader->rdf_rest &&
-      node != reader->rdf_nil) {
-#ifdef SERD_STACK_CHECK
-    SERD_STACK_ASSERT_TOP(reader, node);
-    --reader->n_allocs;
-#endif
-    char* const top = reader->stack.buf + reader->stack.size;
-    serd_stack_pop_aligned(&reader->stack, (size_t)(top - (char*)node));
-  }
-  return NULL;
-}
-
 SerdStatus
 emit_statement(SerdReader* const reader,
                const ReadContext ctx,
@@ -204,15 +190,9 @@ serd_reader_free(SerdReader* const reader)
     return;
   }
 
-  pop_node(reader, reader->rdf_nil);
-  pop_node(reader, reader->rdf_rest);
-  pop_node(reader, reader->rdf_first);
   serd_reader_finish(reader);
   serd_node_free(reader->default_graph);
 
-#ifdef SERD_STACK_CHECK
-  free(reader->allocs);
-#endif
   free(reader->stack.buf);
   free(reader->bprefix);
   free(reader);
diff --git a/src/reader.h b/src/reader.h
index a39fc278..d126aeaa 100644
--- a/src/reader.h
+++ b/src/reader.h
@@ -22,13 +22,6 @@
 #include <stdint.h>
 #include <stdio.h>
 
-#ifdef SERD_STACK_CHECK
-#  define SERD_STACK_ASSERT_TOP(reader, ref) \
-    assert(ref == reader->allocs[reader->n_allocs - 1]);
-#else
-#  define SERD_STACK_ASSERT_TOP(reader, ref)
-#endif
-
 typedef struct {
   SerdNode*           graph;
   SerdNode*           subject;
@@ -56,10 +49,6 @@ struct SerdReaderImpl {
   size_t          bprefix_len;
   bool            strict; ///< True iff strict parsing
   bool            seen_genid;
-#ifdef SERD_STACK_CHECK
-  SerdNode** allocs;   ///< Stack of push offsets
-  size_t     n_allocs; ///< Number of stack pushes
-#endif
 };
 
 SERD_LOG_FUNC(3, 4)
@@ -88,9 +77,6 @@ blank_id(SerdReader* reader);
 void
 set_blank_id(SerdReader* reader, SerdNode* node, size_t buf_size);
 
-SerdNode*
-pop_node(SerdReader* reader, const SerdNode* node);
-
 SerdStatus
 emit_statement(SerdReader* reader, ReadContext ctx, SerdNode* o);
 
@@ -161,7 +147,6 @@ static inline SerdStatus
 push_byte(SerdReader* reader, SerdNode* node, const int c)
 {
   assert(c != EOF);
-  SERD_STACK_ASSERT_TOP(reader, ref);
 
   char* const s = (char*)serd_stack_push(&reader->stack, 1);
   if (!s) {
diff --git a/src/stack.h b/src/stack.h
index e6e46372..4592705e 100644
--- a/src/stack.h
+++ b/src/stack.h
@@ -7,8 +7,8 @@
 #include <assert.h>
 #include <stdbool.h>
 #include <stddef.h>
-#include <stdint.h>
 #include <stdlib.h>
+#include <string.h>
 
 /** An offset to start the stack at. Note 0 is reserved for NULL. */
 #define SERD_STACK_BOTTOM sizeof(void*)
@@ -68,40 +68,28 @@ serd_stack_pop(SerdStack* stack, size_t n_bytes)
   stack->size -= n_bytes;
 }
 
+static inline void
+serd_stack_pop_to(SerdStack* stack, size_t n_bytes)
+{
+  assert(stack->size >= n_bytes);
+  stack->size = n_bytes;
+}
+
 static inline void*
 serd_stack_push_aligned(SerdStack* stack, size_t n_bytes, size_t align)
 {
-  // Push one byte to ensure space for a pad count
-  if (!serd_stack_push(stack, 1)) {
-    return NULL;
-  }
-
   // Push padding if necessary
   const size_t pad = align - stack->size % align;
   if (pad > 0) {
-    if (!serd_stack_push(stack, pad)) {
+    void* padding = serd_stack_push(stack, pad);
+    if (!padding) {
       return NULL;
     }
+    memset(padding, 0, pad);
   }
 
-  // Set top of stack to pad count so we can properly pop later
-  stack->buf[stack->size - 1] = (char)pad;
-
   // Push requested space at aligned location
   return serd_stack_push(stack, n_bytes);
 }
 
-static inline void
-serd_stack_pop_aligned(SerdStack* stack, size_t n_bytes)
-{
-  // Pop requested space down to aligned location
-  serd_stack_pop(stack, n_bytes);
-
-  // Get amount of padding from top of stack
-  const uint8_t pad = (uint8_t)stack->buf[stack->size - 1];
-
-  // Pop padding and pad count
-  serd_stack_pop(stack, pad + 1U);
-}
-
 #endif // SERD_SRC_STACK_H