From e5b08799613bf3387f52a50625e56adb0bdc9d84 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sat, 12 May 2018 22:44:36 +0200 Subject: 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. --- src/n3.c | 100 +++++++++++++++++++++++++++-------------------------------- src/reader.c | 27 +++++----------- src/reader.h | 4 +-- src/stack.h | 33 +++++++------------- 4 files changed, 66 insertions(+), 98 deletions(-) diff --git a/src/n3.c b/src/n3.c index 51cf49cb..880c3074 100644 --- a/src/n3.c +++ b/src/n3.c @@ -315,7 +315,7 @@ read_STRING_LITERAL_LONG(SerdReader* reader, SerdNodeFlags* flags, uint8_t q) read_UCHAR(reader, ref, &code)) { r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid escape `\\%c'\n", peek_byte(reader)); - return pop_node(reader, ref); + return NULL; } } else if (c == q) { eat_byte_safe(reader, q); @@ -348,14 +348,14 @@ read_STRING_LITERAL(SerdReader* reader, SerdNodeFlags* flags, uint8_t q) switch (c) { case '\n': case '\r': r_err(reader, SERD_ERR_BAD_SYNTAX, "line end in short string\n"); - return pop_node(reader, ref); + return NULL; case '\\': eat_byte_safe(reader, c); if (read_ECHAR(reader, ref, flags) && read_UCHAR(reader, ref, &code)) { r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid escape `\\%c'\n", peek_byte(reader)); - return pop_node(reader, ref); + return NULL; } break; default: @@ -373,11 +373,7 @@ read_STRING_LITERAL(SerdReader* reader, SerdNodeFlags* flags, uint8_t q) return NULL; } - if (!eat_byte_check(reader, q)) { - return pop_node(reader, ref); - } - - return ref; + return eat_byte_check(reader, q) ? ref : NULL; } static SerdNode* @@ -636,7 +632,7 @@ read_IRIREF(SerdReader* reader) TRY_RET(eat_byte_check(reader, '<')); SerdNode* ref = push_node(reader, SERD_URI, "", 0); if (!ref || (!fancy_syntax(reader) && !read_IRIREF_scheme(reader, ref))) { - return pop_node(reader, ref); + return NULL; } uint32_t code = 0; @@ -646,19 +642,19 @@ read_IRIREF(SerdReader* reader) case '"': case '<': case '^': case '`': case '{': case '|': case '}': r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid IRI character `%c'\n", c); - return pop_node(reader, ref); + return NULL; case '>': return ref; case '\\': if (read_UCHAR(reader, ref, &code)) { r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid IRI escape\n"); - return pop_node(reader, ref); + return NULL; } switch (code) { case 0: case ' ': case '<': case '>': r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid escaped IRI character %X %c\n", code, code); - return pop_node(reader, ref); + return NULL; } break; default: @@ -671,7 +667,7 @@ read_IRIREF(SerdReader* reader) "invalid IRI character (escape %%%02X)\n", c, c); } if (reader->strict) { - return pop_node(reader, ref); + return NULL; } reader->status = SERD_FAILURE; push_byte(reader, ref, c); @@ -679,13 +675,13 @@ read_IRIREF(SerdReader* reader) push_byte(reader, ref, c); } else if (read_utf8_character(reader, ref, c)) { if (reader->strict) { - return pop_node(reader, ref); + return NULL; } reader->status = SERD_FAILURE; } } } - return pop_node(reader, ref); + return NULL; } static bool @@ -781,8 +777,6 @@ read_number(SerdReader* reader, *dest = ref; return true; except: - pop_node(reader, *datatype); - pop_node(reader, ref); return r_err(reader, SERD_ERR_BAD_SYNTAX, "bad number syntax\n"); } @@ -830,15 +824,15 @@ read_literal(SerdReader* reader, *dest = str; return true; except: - *datatype = pop_node(reader, *datatype); - *lang = pop_node(reader, *lang); - pop_node(reader, str); + *datatype = NULL; + *lang = NULL; return r_err(reader, SERD_ERR_BAD_SYNTAX, "bad literal syntax\n"); } static bool read_verb(SerdReader* reader, SerdNode** dest) { + const size_t orig_stack_size = reader->stack.size; if (peek_byte(reader) == '<') { return (*dest = read_IRIREF(reader)); } @@ -857,12 +851,12 @@ read_verb(SerdReader* reader, SerdNode** dest) if (!st && node->n_bytes == 1 && serd_node_get_string(node)[0] == 'a' && next != ':' && !is_PN_CHARS_BASE(next)) { - pop_node(reader, *dest); + serd_stack_pop_to(&reader->stack, orig_stack_size); return (*dest = push_node(reader, SERD_URI, NS_RDF "type", 47)); } else if (st > SERD_FAILURE || !read_PrefixedName(reader, *dest, false, &ate_dot) || ate_dot) { - *dest = pop_node(reader, *dest); + *dest = NULL; return r_err(reader, SERD_ERR_BAD_SYNTAX, "bad verb\n"); } @@ -886,7 +880,7 @@ read_BLANK_NODE_LABEL(SerdReader* reader, bool* ate_dot) push_byte(reader, n, eat_byte_safe(reader, c)); } else if (read_PN_CHARS(reader, n)) { r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid name start character\n"); - return pop_node(reader, n); + return NULL; } while ((c = peek_byte(reader))) { // Middle: (PN_CHARS | '.')* @@ -913,7 +907,7 @@ read_BLANK_NODE_LABEL(SerdReader* reader, bool* ate_dot) } else if (reader->seen_genid && buf[reader->bprefix_len] == 'B') { r_err(reader, SERD_ERR_ID_CLASH, "found both `b' and `B' blank IDs, prefix required\n"); - return pop_node(reader, n); + return NULL; } } } @@ -990,9 +984,7 @@ read_object(SerdReader* reader, ReadContext* ctx, bool emit, bool* ate_dot) 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 bool ret = false; bool simple = (ctx->subject != 0); @@ -1071,9 +1063,7 @@ read_object(SerdReader* reader, ReadContext* ctx, bool emit, bool* ate_dot) } except: - 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 @@ -1098,11 +1088,13 @@ read_objectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) static bool read_predicateObjectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) { + const size_t orig_stack_size = reader->stack.size; + while (read_verb(reader, &ctx.predicate) && read_ws_star(reader) && 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 true; } @@ -1112,9 +1104,11 @@ read_predicateObjectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) read_ws_star(reader); switch (c = peek_byte(reader)) { case 0: + serd_stack_pop_to(&reader->stack, orig_stack_size); return r_err(reader, SERD_ERR_BAD_SYNTAX, "unexpected end of file\n"); case '.': case ']': case '}': + serd_stack_pop_to(&reader->stack, orig_stack_size); return true; case ';': eat_byte_safe(reader, c); @@ -1123,18 +1117,19 @@ read_predicateObjectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) } while (c == ';'); if (!ate_semi) { + serd_stack_pop_to(&reader->stack, orig_stack_size); return r_err(reader, SERD_ERR_BAD_SYNTAX, "missing ';' or '.'\n"); } } - return pop_node(reader, ctx.predicate); + serd_stack_pop_to(&reader->stack, orig_stack_size); + ctx.predicate = 0; + return false; } static bool -end_collection(SerdReader* reader, ReadContext ctx, SerdNode* n1, SerdNode* n2, bool ret) +end_collection(SerdReader* reader, ReadContext ctx, bool ret) { - pop_node(reader, n2); - pop_node(reader, n1); *ctx.flags &= ~SERD_LIST_CONT; return ret && (eat_byte_safe(reader, ')') == ')'); } @@ -1155,7 +1150,7 @@ read_collection(SerdReader* reader, ReadContext ctx, SerdNode** dest) } if (end) { - return end_collection(reader, ctx, 0, 0, true); + return end_collection(reader, ctx, true); } /* The order of node allocation here is necessarily not in stack order, @@ -1175,7 +1170,7 @@ read_collection(SerdReader* reader, ReadContext ctx, SerdNode** dest) ctx.predicate = reader->rdf_first; bool ate_dot = false; if (!read_object(reader, &ctx, true, &ate_dot) || ate_dot) { - return end_collection(reader, ctx, n1, n2, false); + return end_collection(reader, ctx, false); } if (!(end = peek_delim(reader, ')'))) { @@ -1198,7 +1193,7 @@ read_collection(SerdReader* reader, ReadContext ctx, SerdNode** dest) node = ctx.subject; // invariant } - return end_collection(reader, ctx, n1, n2, true); + return end_collection(reader, ctx, true); } static SerdNode* @@ -1218,7 +1213,7 @@ read_subject(SerdReader* reader, ReadContext ctx, SerdNode** dest, char* s_type) default: TRY_RET(read_iri(reader, dest, &ate_dot)); } - return ate_dot ? pop_node(reader, *dest) : *dest; + return ate_dot ? NULL : *dest; } static SerdNode* @@ -1273,7 +1268,6 @@ read_base(SerdReader* reader, bool sparql, bool token) } else if (reader->sink->base) { reader->sink->base(reader->sink->handle, uri); } - pop_node(reader, uri); read_ws_star(reader); if (!sparql) { @@ -1298,25 +1292,22 @@ read_prefixID(SerdReader* reader, bool sparql, bool token) if (!name) { return false; } else if (read_PN_PREFIX(reader, name) > SERD_FAILURE) { - return pop_node(reader, name); + return false; } if (eat_byte_check(reader, ':') != ':') { - return pop_node(reader, name); + return false; } read_ws_star(reader); const SerdNode* uri = read_IRIREF(reader); if (!uri) { - pop_node(reader, name); return false; } if (reader->sink->prefix) { ret = !reader->sink->prefix(reader->sink->handle, name, uri); } - pop_node(reader, uri); - pop_node(reader, name); if (!sparql) { read_ws_star(reader); return eat_byte_check(reader, '.'); @@ -1353,8 +1344,10 @@ read_wrappedGraph(SerdReader* reader, ReadContext* ctx) TRY_RET(eat_byte_check(reader, '{')); read_ws_star(reader); while (peek_byte(reader) != '}') { - bool ate_dot = false; - char s_type = 0; + const size_t orig_stack_size = reader->stack.size; + bool ate_dot = false; + char s_type = 0; + ctx->subject = 0; SerdNode* subj = read_subject(reader, *ctx, &ctx->subject, &s_type); if (!subj && ctx->subject) { @@ -1365,7 +1358,7 @@ read_wrappedGraph(SerdReader* reader, ReadContext* ctx) return r_err(reader, SERD_ERR_BAD_SYNTAX, "missing predicate object list\n"); } - pop_node(reader, subj); + serd_stack_pop_to(&reader->stack, orig_stack_size); read_ws_star(reader); if (peek_byte(reader) == '.') { eat_byte_safe(reader, '.'); @@ -1425,7 +1418,6 @@ read_n3_statement(SerdReader* reader) TRY_RET((ctx.graph = read_labelOrSubject(reader))); read_ws_star(reader); TRY_RET(read_wrappedGraph(reader, &ctx)); - pop_node(reader, ctx.graph); ctx.graph = 0; read_ws_star(reader); } else if (read_ws_star(reader) && peek_byte(reader) == '{') { @@ -1436,7 +1428,6 @@ read_n3_statement(SerdReader* reader) ctx.graph = subj; ctx.subject = subj = 0; TRY_RET(read_wrappedGraph(reader, &ctx)); - pop_node(reader, ctx.graph); read_ws_star(reader); } else if (!subj) { ret = r_err(reader, SERD_ERR_BAD_SYNTAX, "bad subject\n"); @@ -1449,7 +1440,6 @@ read_n3_statement(SerdReader* reader) read_ws_star(reader); ret = (eat_byte_check(reader, '.') == '.'); } - pop_node(reader, subj); break; } return ret; @@ -1467,13 +1457,16 @@ SerdStatus read_turtleTrigDoc(SerdReader* reader) { while (!reader->source.eof) { + const size_t orig_stack_size = reader->stack.size; if (!read_n3_statement(reader)) { if (reader->strict) { + serd_stack_pop_to(&reader->stack, orig_stack_size); return SERD_ERR_UNKNOWN; } skip_until(reader, '\n'); reader->status = SERD_SUCCESS; } + serd_stack_pop_to(&reader->stack, orig_stack_size); } return reader->status; } @@ -1482,6 +1475,8 @@ SerdStatus read_nquadsDoc(SerdReader* reader) { while (!reader->source.eof) { + const size_t orig_stack_size = reader->stack.size; + SerdStatementFlags flags = 0; ReadContext ctx = { 0, 0, 0, 0, 0, 0, &flags }; bool ate_dot = false; @@ -1528,10 +1523,7 @@ read_nquadsDoc(SerdReader* reader) break; } - pop_node(reader, ctx.graph); - pop_node(reader, ctx.lang); - pop_node(reader, ctx.datatype); - pop_node(reader, ctx.object); + serd_stack_pop_to(&reader->stack, orig_stack_size); } return reader->status; } diff --git a/src/reader.c b/src/reader.c index 6e784eea..e6629305 100644 --- a/src/reader.c +++ b/src/reader.c @@ -74,6 +74,13 @@ SerdNode* push_node_padded(SerdReader* reader, size_t maxlen, SerdType type, const char* str, size_t n_bytes) { + // 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)); @@ -93,7 +100,7 @@ push_node_padded(SerdReader* reader, size_t maxlen, #ifdef SERD_STACK_CHECK reader->allocs = realloc( reader->allocs, sizeof(reader->allocs) * (++reader->n_allocs)); - reader->allocs[reader->n_allocs - 1] = (mem - reader->stack.buf); + reader->allocs[reader->n_allocs - 1] = node; #endif return node; } @@ -104,21 +111,6 @@ push_node(SerdReader* reader, SerdType type, const char* str, size_t n_bytes) return push_node_padded(reader, n_bytes, type, str, n_bytes); } -SerdNode* -pop_node(SerdReader* reader, const SerdNode* 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, top - (char*)node); - } - return NULL; -} - bool emit_statement(SerdReader* reader, ReadContext ctx, SerdNode* o) { @@ -190,9 +182,6 @@ serd_reader_set_strict(SerdReader* reader, bool strict) void serd_reader_free(SerdReader* reader) { - pop_node(reader, reader->rdf_nil); - pop_node(reader, reader->rdf_rest); - pop_node(reader, reader->rdf_first); serd_node_free(reader->default_graph); #ifdef SERD_STACK_CHECK diff --git a/src/reader.h b/src/reader.h index 36d6da03..740f8d7c 100644 --- a/src/reader.h +++ b/src/reader.h @@ -87,8 +87,6 @@ size_t genid_size(SerdReader* reader); SerdNode* blank_id(SerdReader* reader); void set_blank_id(SerdReader* reader, SerdNode* node, size_t buf_size); -SerdNode* pop_node(SerdReader* reader, const SerdNode* node); - bool emit_statement(SerdReader* reader, ReadContext ctx, SerdNode* o); bool read_n3_statement(SerdReader* reader); @@ -146,7 +144,7 @@ eat_string(SerdReader* reader, const char* str, unsigned n) static inline SerdStatus push_byte(SerdReader* reader, SerdNode* node, const uint8_t c) { - SERD_STACK_ASSERT_TOP(reader, ref); + SERD_STACK_ASSERT_TOP(reader, node); char* const s = (char*)serd_stack_push(&reader->stack, 1); if (!s) { return SERD_ERR_OVERFLOW; diff --git a/src/stack.h b/src/stack.h index c066a75e..24641461 100644 --- a/src/stack.h +++ b/src/stack.h @@ -22,6 +22,7 @@ #include #include #include +#include /** An offset to start the stack at. Note 0 is reserved for NULL. */ #define SERD_STACK_BOTTOM sizeof(void*) @@ -77,40 +78,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 uint8_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] = 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 = stack->buf[stack->size - 1]; - - // Pop padding and pad count - serd_stack_pop(stack, pad + 1); -} - #endif // SERD_STACK_H -- cgit v1.2.1