Optimise detection of rejection

Signed-off-by: Mattias Andrée <m@maandree.se>

1 files changed, 50 insertions, 13 deletions

diff --git a/libparser.c b/libparser.c
index 56ce703..eec9337 100644
--- a/libparser.c
+++ b/libparser.c
@@ -43,11 +43,17 @@ struct followup {
 
 	/**
 	 * Set if and only if `.unit` is non-`NULL`:
-	 * the
-	 * index of the node
+	 * the index of the node
 	 */
 	size_t unit_index;
 
+	/**
+	 * Set if and only if `.unit` is non-`NULL`:
+	 * the index of the node of the previous
+	 * rejection, `SIZE_MAX` if none
+	 */
+	size_t previous_rejection;
+
 	/* -- or -- */
 
 	/**
@@ -101,6 +107,12 @@ struct choice {
 	size_t unit_index;
 
 	/**
+	 * The value `.previous_rejection` of the `ctx`
+	 * argument `add_unit` was called with
+	 */
+	size_t previous_rejection;
+
+	/**
 	 * Save state of the follow-up stack
 	 */
 	struct {
@@ -202,6 +214,12 @@ struct context {
 	} units;
 
 	/**
+	 * The index of the node of the previous
+	 * rejection, `SIZE_MAX` if none
+	 */
+	size_t previous_rejection;
+
+	/**
 	 * The text being parsed
 	 */
 	const char *data;
@@ -296,10 +314,15 @@ print_state(struct context *ctx)
 		        ctx->choices.choices[i].position,
 		        sentence_type_string(ctx->choices.choices[i].sentence->type),
 		        ctx->choices.choices[i].rule);
-		if (ctx->choices.choices[i].choice == EXHAUSTED) {
-			fprintf(stderr, "choices EXHAUSTED\n");
+		if (ctx->choices.choices[i].choice == EXHAUSTED)
+			fprintf(stderr, "choices EXHAUSTED; ");
+		else
+			fprintf(stderr, "using choice %zu; ", ctx->choices.choices[i].choice);
+		if (ctx->choices.choices[i].previous_rejection == SIZE_MAX) {
+			fprintf(stderr, "no rejection stored\n");
 		} else {
-			fprintf(stderr, "using choice %zu\n", ctx->choices.choices[i].choice);
+			fprintf(stderr, "previous rejection: %zu\n",
+			        ctx->choices.choices[i].previous_rejection);
 		}
 	}
 
@@ -309,13 +332,19 @@ print_state(struct context *ctx)
 		if (IS_COMPLETION(ctx->followups.followups[i])) {
 			unit = ctx->followups.followups[i].unit;
 			sentence = unit->sentence;
-			fprintf(stderr, "    Completion: unit %zu: %s: %s%s%s [%zu, %zu)\n",
+			fprintf(stderr, "    Completion: unit %zu: %s: %s%s%s [%zu, %zu); ",
 			        ctx->followups.followups[i].unit_index,
 			        unit->rule, sentence_type_string(sentence->type),
 			        sentence->type == LIBPARSER_SENTENCE_TYPE_RULE ? " " : "",
 			        sentence->type == LIBPARSER_SENTENCE_TYPE_RULE
 			            ? sentence->rule.rule : "",
 			        unit->start, unit->end);
+			if (ctx->followups.followups[i].previous_rejection == SIZE_MAX) {
+				fprintf(stderr, "no rejection stored\n");
+			} else {
+				fprintf(stderr, "previous rejection: %zu\n",
+				        ctx->followups.followups[i].previous_rejection);
+			}
 		} else {
 			sentence = ctx->followups.followups[i].sentence;
 			fprintf(stderr, "    (%s, %s%s%s)\n",
@@ -661,6 +690,7 @@ incomplete(const char *rule, const union libparser_sentence *sentence, size_t st
 	}
 	followup->unit = unit;
 	followup->unit_index = ctx->units.count;
+	followup->previous_rejection = ctx->previous_rejection;
 
 #if PRINT_ACTIONS
 	fprintf(stderr, "Pushing follow-up completion for unit %zu: %s: %s\n",
@@ -724,6 +754,7 @@ braching(const char *rule, const union libparser_sentence *sentence, size_t star
 		choice->rule = rule;
 		choice->sentence = sentence;
 		choice->unit_index = ctx->units.count;
+		choice->previous_rejection = ctx->previous_rejection;
 		choice->followups.followups = NULL;
 		choice->followups.count = ctx->followups.count;
 		if (choice->followups.count) {
@@ -741,13 +772,19 @@ braching(const char *rule, const union libparser_sentence *sentence, size_t star
 		        sentence_type_string(sentence->type), rule, start);
 	} else {
 		fprintf(stderr, "Revisiting branching point %zu at %zu in text for unit %zu: "
-		                "%s: %s, at %zu in text; choice value: %zu\n",
+		                "%s: %s, at %zu in text; choice value: %zu; ",
 		        ctx->choices.next, start,
 		        ctx->choices.choices[ctx->choices.next].unit_index,
 		        sentence_type_string(ctx->choices.choices[ctx->choices.next].sentence->type),
 		        ctx->choices.choices[ctx->choices.next].rule,
 		        ctx->choices.choices[ctx->choices.next].position,
 		        ctx->choices.choices[ctx->choices.next].choice);
+		if (ctx->choices.choices[ctx->choices.next].previous_rejection == SIZE_MAX) {
+			fprintf(stderr, "no rejection stored\n");
+		} else {
+			fprintf(stderr, "previous rejection: %zu\n",
+			        ctx->choices.choices[ctx->choices.next].previous_rejection);
+		}
 #endif
 	}
 	*choice_out = ctx->choices.choices[ctx->choices.next++].choice;
@@ -842,6 +879,7 @@ add_unit(const char *rule, const union libparser_sentence *sentence, struct cont
 		if (incomplete(NULL, sentence, start, ctx) ||
 		    push(NULL, sentence->unary.sentence, ctx))
 			return -1;
+		ctx->previous_rejection = ctx->units.count - 1u;
 		return 1;
 
 	case LIBPARSER_SENTENCE_TYPE_RULE:
@@ -1080,12 +1118,8 @@ __attribute__((__pure__))
 static int
 choice_contains_rejection(struct context *ctx)
 {
-	/* TODO we should keep track of our rejections so we can do this in constant time */
-	size_t i = ctx->choices.choices[ctx->choices.count - 1u].unit_index;
-	for (i += 1u; i < ctx->units.count; i++)
-		if (ctx->units.units[i]->sentence->type == LIBPARSER_SENTENCE_TYPE_REJECTION)
-			return 1;
-	return 0;
+	size_t i = ctx->choices.choices[ctx->choices.count - 1u].previous_rejection;
+	return ctx->previous_rejection != i;
 }
 
 
@@ -1111,6 +1145,7 @@ libparser_parse_file(const struct libparser_rule *const rules[], const char *dat
 	ctx.units.size = 0;
 	ctx.units.count = 0;
 	ctx.unit_pool = NULL;
+	ctx.previous_rejection = SIZE_MAX;
 	ctx.data = data;
 	ctx.length = length;
 	ctx.position = 0;
@@ -1203,6 +1238,7 @@ followup:
 			fprintf(stderr, "Setting end of popped unit to %zu\n", ctx.position);
 #endif
 			unit->end = ctx.position;
+			ctx.previous_rejection = ctx.followups.followups[i].previous_rejection;
 		} else if (match) {
 			rule = ctx.followups.followups[i].rule;
 			sentence = ctx.followups.followups[i].sentence;
@@ -1231,6 +1267,7 @@ followup:
 			}
 			ctx.choices.choices[i].choice++;
 			ctx.position = ctx.choices.choices[i].position;
+			ctx.previous_rejection = ctx.choices.choices[i].previous_rejection;
 			rule = ctx.choices.choices[i].rule;
 			sentence = ctx.choices.choices[i].sentence;
 #if PRINT_ACTIONS