path: root/pom.c

#include "pom.h"

#include <stdio.h> // still needed for sprintf, even if POM_NO_STDIO is defined.
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <limits.h>
#include <inttypes.h>
#include <assert.h>

#if __GNUC__ >= 6
#define ATTRIBUTE_PRINTF(fmt, args) __attribute__ ((format(printf, fmt, args)))
#else
#define ATTRIBUTE_PRINTF(fmt, args)
#endif

#if _MSC_VER >= 1600
#define PRINTF_FORMAT_STRING _Printf_format_string_
#else
#define PRINTF_FORMAT_STRING
#endif

#if __STDC_VERSION__ >= 201112 && !defined(__STDC_NO_ATOMICS__)
#define HAVE_ATOMICS 1
#include <stdatomic.h>
#endif

struct pom_error {
	const pom_error *next;
	const char *file;
	uint64_t line;
	const char *message;
};

struct conf_item {
	const char *key, *value, *file;
	uint64_t line;
	// whether key has been read or pom_conf_unread_keys
#if HAVE_ATOMICS
	atomic_bool read;
#else
	bool read;
#endif
};

// linked list of things we have to free when we free a configuration
struct to_free {
	struct to_free *next;
	// fool's max_align_t
	union {
		void *ptr;
		double d;
		uint64_t u64;
	} data[];
};

struct pom_conf {
	struct main_conf *main;
	// prefix length of keys which should be ignored.
	// (this is set by pom_conf_section(conf, section) to strlen(section) + 1)
	size_t prefix_len;
	// items in this configuration
	struct conf_item *items;
	size_t items_count;
	// sections/sub-sections of this configuration
	struct conf_section *sections;
	size_t sections_count;
};

struct conf_section {
	const char *key;
	struct pom_conf conf;
};

// holds the "root" of a configuration
struct main_conf {
	// stuff we have to free.
	struct to_free *to_free_head, *to_free_tail;
	// can return this from pom_conf_section when the section is mpety
	// (so we don't have to store empty sections)
	struct pom_conf empty_section;
};

struct pom_item_iter {
	const pom_conf *conf;
	const struct conf_item *conf_item;
	pom_item item;
};

struct pom_unread_key_iter {
	const pom_conf *conf;
	const struct conf_item *conf_item;
};

struct pom_key_iter {
	const pom_conf *conf;
	char *prev_key;
	const struct conf_item *conf_item;
};

// temporary error that is eventually converted to a pom_error
struct parser_error {
	uint64_t line;
	// index into parser->error_messages.array
	uint32_t message;
};

// type for parser::utf8_state
enum utf8_state {
	UTF8_STATE_DEFAULT = 0,
	// want 1 continuation byte
	UTF8_STATE_1CONT = 1,
	// want 2 continuation bytes
	UTF8_STATE_2CONT = 2,
	// want 3 continuation bytes
	UTF8_STATE_3CONT = 3,
	// want 2 continuation bytes, first one must be >=0xA0 (otherwise encoding is overlong)
	UTF8_STATE_2CONT_GTEQ_A0 = 4,
	// want 2 continuation bytes, first one must be <0xA0 (otherwise encodes a UTF-16 surrogate)
	UTF8_STATE_2CONT_LT_A0 = 5,
	// want 3 continuation bytes, first one must be >=0x90 (otherwise encodoing is overlong)
	UTF8_STATE_3CONT_GTEQ_90 = 6,
	// want 3 continuation bytes, first one must be <0x90 (otherwise encoding produces oversized code point)
	UTF8_STATE_3CONT_LT_90 = 7,
};

// temporary item that is eventually turned into a conf_item
struct parser_item {
	size_t key;
	size_t value;
	uint64_t line;
};

struct parser {
	const char *filename;
	uint64_t line_number;
	size_t (*read_func)(void *, char *, size_t);
	void *userdata;
	pom_error *out_of_memory_error;
	struct {
		char *array;
		size_t capacity;
	} line;
	struct {
		struct parser_error *array;
		size_t count, capacity;
	} errors;
	struct {
		char *array;
		size_t count, capacity;
	} error_messages;
	struct {
		char *array;
		size_t count, capacity;
	} string_data;
	struct {
		char *array;
		size_t capacity;
		size_t len;
	} current_section;
	struct {
		struct parser_item *array;
		size_t capacity;
		size_t count;
	} items;
	bool
		// last call to read_func returned <size
		short_read,
		// end-of-file reached
		eof,
		// memory allocation failed
		out_of_memory,
		// last call to read_func had a `\r` at the end
		leftover_cr;
	// see enum utf8_state -- starting state for future calls to `read_func`
	uint8_t utf8_state;
	// current position in `buf`
	uint16_t buf_pos;
	// number of bytes set in `buf`.
	uint16_t buf_count;
	// buffers data from `read_func`.
	char buf[4096];
};

#ifdef POM_NO_STDIO
#define fatal_error(...) abort()
#else
// fatal_error should only be called when the API is misused
// (e.g. `NULL` argument that shouldn't be `NULL`).
static void fatal_error(PRINTF_FORMAT_STRING const char *fmt, ...) ATTRIBUTE_PRINTF(1, 2);
static void
fatal_error(const char *fmt, ...) {
	va_list args;
	va_start(args, fmt);
	vfprintf(stderr, fmt, args);
	va_end(args);
	fprintf(stderr, "\n");
	abort();
}
#endif

// Make an error with no next-error.
static pom_error *make_error(PRINTF_FORMAT_STRING const char *file, uint64_t line, const char *fmt, ...) ATTRIBUTE_PRINTF(3, 4);
static pom_error *
make_error(const char *file, uint64_t line, const char *fmt, ...) {
	va_list args, args_copy;
	va_start(args, fmt);
	va_copy(args_copy, args);
	bool bad_fmt = false;
	int len = vsnprintf(NULL, 0, fmt, args);
	if (len < 0 || len > INT_MAX - sizeof(pom_error) - 1) {
		// Could technically happen if %s gets a really long string.
		// Just use fmt as the error in this case.
		bad_fmt = true;
		len = strlen(fmt);
	}
	pom_error *err = malloc(sizeof(pom_error) + len + 1);
	if (err) {
		char *message = (char *)(err + 1);
		if (bad_fmt) {
			strcpy(message, fmt);
		} else {
			vsnprintf(message, len + 1, fmt, args_copy);
		}
		err->file = file;
		err->line = line;
		err->message = message;
		err->next = NULL;
	}
	va_end(args_copy);
	return err;
}

const pom_error *
pom_error_next(const pom_error *error) {
	if (!error) return NULL;
	return error->next;
}

const char *
pom_error_file(const pom_error *error) {
	if (!error)
		fatal_error("%s called with NULL argument", __func__);
	return error->file;
}

uint64_t
pom_error_line(const pom_error *error) {
	if (!error)
		fatal_error("%s called with NULL argument", __func__);
	return error->line;
}

const char *
pom_error_message(const pom_error *error) {
	if (!error)
		fatal_error("%s called with NULL argument", __func__);
	return error->message;
}

#ifndef POM_NO_STDIO
void
pom_error_print(const pom_error *error) {
	if (!error) {
		fprintf(stderr, "No error.\n");
		return;
	}
	fprintf(stderr, "Error:\n");
	for (; error; error = pom_error_next(error)) {
		fprintf(stderr, "%s:%" PRIu64 ": %s\n", error->file, error->line, error->message);
	}
}
#endif

static void
parser_out_of_memory(struct parser *parser) {
	parser->out_of_memory = true;
}

static POM__MUST_USE_L bool parser_realloc_(struct parser *parser, void *ptr, size_t elem_size, size_t *pcapacity, size_t new_capacity) POM__MUST_USE_R;
static bool
parser_realloc_(struct parser *parser, void *ptr, size_t elem_size, size_t *pcapacity, size_t new_capacity) {
	size_t capacity = *pcapacity;
	if (new_capacity > capacity) {
		// this check is overly strict to avoid arithmetic overflow.
		if (new_capacity >= SIZE_MAX / 4 / elem_size) {
			parser_out_of_memory(parser);
			return false;
		}
		// this is bad if not all pointer types have the same representation.
		// I really hope we don't have to worry about that in 2025.
		void **parray = ptr;
		void *array = *parray;
		new_capacity = new_capacity * 3 / 2 + 2;
		array = realloc(array, new_capacity * elem_size);
		if (!array) {
			parser_out_of_memory(parser);
			return false;
		}
		*parray = array;
		*pcapacity = new_capacity;
	}
	return true;
}

// Strange resizing-array macro.


static void *
parser_append_(struct parser *parser, void *ptr, size_t elem_size, size_t *pcount, size_t *pcapacity,
	size_t need) {
	size_t old_count = *pcount;
	// ensure addition below doesn't overflow
	if (need >= SIZE_MAX / 8 - old_count) {
		parser_out_of_memory(parser);
		return NULL;
	}
	if (parser_realloc_(parser, ptr, elem_size, pcapacity, old_count + need)) {
		*pcount += need;
		return *(char **)ptr + elem_size * old_count;
	} else {
		return NULL;
	}
}

#if __STDC_VERSION__ >= 202311
#define SAFETY_CAST_TYPEOF(t) (typeof(t))
#elif __GNUC__ >= 4
#define SAFETY_CAST_TYPEOF(t) (__typeof__(t))
#else
#define SAFETY_CAST_TYPEOF(t)
#endif

#define parser_realloc(parser, field, new_capacity) \
	parser_realloc_(parser, &parser->field.array, sizeof parser->field.array[0], &parser->field.capacity, new_capacity)
// Adds room for `need` elements to the array `parser.field`,
// and returns a pointer to the first one.
#define parser_append(parser, field, need) \
	SAFETY_CAST_TYPEOF(parser->field.array) parser_append_(parser, &parser->field.array, sizeof parser->field.array[0], &parser->field.count, &parser->field.capacity, need)
#define parser_append_one(parser, field) \
	parser_append(parser, field, 1)

// append a character to parser->string_data
static void
parser_append_char(struct parser *parser, char c) {
	char *pc = parser_append_one(parser, string_data);
	if (pc) *pc = c;
}

static void parser_error(struct parser *parser, PRINTF_FORMAT_STRING const char *fmt, ...) ATTRIBUTE_PRINTF(2, 3);
static void
parser_error(struct parser *parser, const char *fmt, ...) {
	if (parser->out_of_memory) return;
	if (parser->errors.count >= 1000) return; // don't bother at this point.
	va_list args, args_copy;
	va_start(args, fmt);
	va_copy(args_copy, args);
	bool bad_fmt = false;
	int error_len = vsnprintf(NULL, 0, fmt, args);
	va_end(args);
	if (error_len < 0) {
		// could happen with a >INT_MAX-sized string, for example
		bad_fmt = true;
		error_len = strlen(fmt);
		va_end(args_copy);
	}
	if (error_len > 1000)
		error_len = 1000; // truncate very long errors
	char *message = parser_append(parser, error_messages, error_len + 1);
	if (!message) {
		if (!bad_fmt) va_end(args_copy);
		return;
	}
	uint32_t message_idx = message - parser->error_messages.array;
	if (bad_fmt) {
		// use fmt as error message
		strcpy(message, fmt);
	} else {
		vsnprintf(message, error_len + 1, fmt, args_copy);
	}
	struct parser_error *error = parser_append_one(parser, errors);
	if (!error) return;
	error->line = parser->line_number;
	error->message = message_idx;
}

// read more data into parser->buf. returns false on EOF.
static bool
parser_read_to_buf(struct parser *parser, bool skip_bom) {
	if (parser->eof) return false;
	uint8_t utf8_state = parser->utf8_state;
	if (parser->short_read) { // last read was short, so we're at EOF
		// EOF reached.
	eof:
		if (utf8_state) {
			parser_error(parser, "Invalid UTF-8 (want continuation byte, got EOF).");
		}
		parser->eof = true;
		return false;
	}
	char *buf = parser->buf;
	size_t read_count = parser->read_func(parser->userdata, buf, sizeof parser->buf - 1);
	parser->buf_pos = 0;
	if (read_count == 0)
		goto eof;
	if (read_count < sizeof parser->buf - 1)
		parser->short_read = true;
	if (parser->leftover_cr && buf[0] != '\n')
		parser_error(parser, "Carriage return with no newline after it.");
	size_t in = 0, out = 0;
	uint64_t original_line_number = parser->line_number;
	if (skip_bom && read_count >= 3
		&& (uint8_t)parser->buf[0] == 0xEF
		&& (uint8_t)parser->buf[1] == 0xBB
		&& (uint8_t)parser->buf[2] == 0xBF) {
		// skip byte-order mark
		in = 3;
	}
	for (; in < read_count; in++) {
		uint8_t byte = buf[in];
		if (utf8_state == 0) {
			if (byte < 0x80) {
				// ASCII
				if (byte == '\r') {
					if (in == read_count - 1) {
						parser->leftover_cr = true;
					} else if (buf[in + 1] != '\n') {
						parser_error(parser, "Carriage return with no newline after it.");
					}
					continue;
				} else if (byte == '\n') {
					parser->line_number++;
				} else if (byte >= 0 && byte < 32 && byte != '\t') {
					parser_error(parser, "Illegal control character (ASCII code %d)", byte);
					continue;
				}
			} else if (byte < 0xC2) {
			utf8_invalid_start_byte:
				parser_error(parser, "Invalid UTF-8 (invalid start byte 0x%02X)", byte);
				continue;
			} else if (byte < 0xE0) {
				// 2-byte sequence
				utf8_state = UTF8_STATE_1CONT;
			} else if (byte == 0xE0) {
				// 3-byte sequence; must check for overlongness
				utf8_state = UTF8_STATE_2CONT_GTEQ_A0;
			} else if (byte == 0xED) {
				// 3-byte sequence; must check for UTF-16 surrogate
				utf8_state = UTF8_STATE_2CONT_LT_A0;
			} else if (byte < 0xF0) {
				// 3-byte sequence
				utf8_state = UTF8_STATE_2CONT;
			} else if (byte == 0xF0) {
				// 4-byte sequence; must check for overlongness
				utf8_state = UTF8_STATE_3CONT_GTEQ_90;
			} else if (byte < 0xF4) {
				// 4-byte sequence
				utf8_state = UTF8_STATE_3CONT;
			} else if (byte == 0xF4) {
				// 4-byte sequence; must check for too-big code points
				utf8_state = UTF8_STATE_3CONT_LT_90;
			} else {
				goto utf8_invalid_start_byte;
			}
		} else if (utf8_state == UTF8_STATE_1CONT || utf8_state == UTF8_STATE_2CONT || utf8_state == UTF8_STATE_3CONT) {
			utf8_state -= 1;
			if ((byte & 0xC0) != 0x80) {
				parser_error(parser, "Invalid UTF-8 (want continuation byte, got 0x%02X)", byte);
				continue;
			}
		} else if (utf8_state == UTF8_STATE_2CONT_GTEQ_A0) {
			utf8_state = UTF8_STATE_1CONT;
			if (byte < 0xA0 || (byte & 0xC0) != 0x80) {
				parser_error(parser, "Invalid UTF-8 (want continuation byte >= 0xA0, got 0x%02X)", byte);
				continue;
			}
		} else if (utf8_state == UTF8_STATE_2CONT_LT_A0) {
			utf8_state = UTF8_STATE_1CONT;
			if (byte >= 0xA0 || (byte & 0xC0) != 0x80) {
				parser_error(parser, "Invalid UTF-8 (want continuation byte < 0xA0, got 0x%02X)", byte);
				continue;
			}
		} else if (utf8_state == UTF8_STATE_3CONT_GTEQ_90) {
			utf8_state = UTF8_STATE_2CONT;
			if (byte < 0x90 || (byte & 0xC0) != 0x80) {
				parser_error(parser, "Invalid UTF-8 (want continuation byte >= 0x90, got 0x%02X)", byte);
				continue;
			}
		} else if (utf8_state == UTF8_STATE_3CONT_LT_90) {
			utf8_state = UTF8_STATE_2CONT;
			if (byte >= 0x90 || (byte & 0xC0) != 0x80) {
				parser_error(parser, "Invalid UTF-8 (want continuation byte < 0x90, got 0x%02X)", byte);
				continue;
			}
		} else {
			abort(); // should be unreachable.
		}
		buf[out++] = byte;
	}
	parser->utf8_state = utf8_state;
	parser->line_number = original_line_number;
	parser->buf_count = out;
	return true;
}

// Reads into parser->line_buf.
static void
parser_read_line(struct parser *parser) {
	if (parser->eof) {
		parser->line.array[0] = 0;
		return;
	}
	parser->line_number += 1;
	size_t line_count = 0;
	while (true) {
		// NB: addition will not realistically overflow.
		if (!parser_realloc(parser, line, line_count + sizeof parser->buf + 1))
			return;
		char *line = parser->line.array;
		while (parser->buf_pos < parser->buf_count) {
			char c = parser->buf[parser->buf_pos++];
			if (c == '\n') {
				line[line_count] = 0;
				return;
			}
			line[line_count++] = c;
		}
		if (!parser_read_to_buf(parser, false)) {
			// reached EOF
			line[line_count] = 0;
			return;
		}
	}
}

static void
strip_leading_accepted_spaces(char *s) {
	size_t i;
	for (i = 0; s[i] == '\t' || s[i] == ' '; i++);
	memmove(s, s + i, strlen(s) + 1 - i);
}

static void
strip_trailing_accepted_spaces(char *s) {
	size_t i = strlen(s);
	while (i > 0) {
		i--;
		if (!(s[i] == '\t' || s[i] == ' ')) break;
		s[i] = 0;
	}
}

static void
check_valid_key(struct parser *parser, const char *key) {
	uint8_t c;
	if (key[0] == '.')
		parser_error(parser, "Key shouldn't begin with .: %s", key);
	for (size_t i = 0; (c = key[i]); i++) {
		bool bad = false;
		if (c < 64) {
			if (c == '.') {
				if (key[i+1] == 0) {
					parser_error(parser, "Key shouldn't end with .: %s", key);
				} else if (key[i+1] == '.') {
					parser_error(parser, "Key shouldn't contain ..: %s", key);
				}
			}
			// bitmask of disallowed ASCII characters 0-63
			bad = (0xfc001bffffffffffU >> c) & 1;
		} else if (c < 128) {
			// bitmask of disallowed ASCII characters 64-127
			bad = (0xfc0000017c000001U >> c) & 1;
		}
		if (bad) {
			parser_error(parser, "Invalid character in key: '%c' (ASCII %d)", c, c);
		}
	}
}

static int
parse_hex_digit(char c) {
	if (c < '0') return -1;
	if (c <= '9') return c - '0';
	c &= 0xdf;
	if (c < 'A') return -1;
	if (c <= 'F') return c - 'A' + 10;
	return -1;
}

// parse escape sequence in *p_str, advancing *p_str past it.
static void
parse_escape_sequence(struct parser *parser, const char **p_str) {
	const char *str = *p_str;
	switch (*str++) {
	invalid_sequence: {
		int len = (int)(str - *p_str);
		parser_error(parser, "Invalid escape sequence: \\%.*s", len, *p_str);
		return;
		} break;
	case 'n':
		parser_append_char(parser, '\n');
		break;
	case 't':
		parser_append_char(parser, '\t');
		break;
	case 'r':
		parser_append_char(parser, '\r');
		break;
	case '\\':
		parser_append_char(parser, '\\');
		break;
	case '"':
		parser_append_char(parser, '"');
		break;
	case '\'':
		parser_append_char(parser, '\'');
		break;
	case '`':
		parser_append_char(parser, '`');
		break;
	case ',':
		parser_append_char(parser, '\\');
		parser_append_char(parser, ',');
		break;
	case 'x': {
		int dig1 = parse_hex_digit(*str++);
		if (dig1 < 0) goto invalid_sequence;
		int dig2 = parse_hex_digit(*str++);
		if (dig2 < 0) goto invalid_sequence;
		int value = dig1 << 4 | dig2;
		if (value == 0 || value > 0x7f) goto invalid_sequence;
		parser_append_char(parser, value);
		} break;
	case 'u': {
		if (*str++ != '{') goto invalid_sequence;
		uint_fast32_t value = 0;
		char c;
		while ((c = *str++) != '}') {
			int digit = parse_hex_digit(c);
			if (digit < 0) goto invalid_sequence;
			value <<= 4;
			value |= digit;
			if (value > 0x10ffff) goto invalid_sequence;
		}
		if (value >= 0xd800 && value <= 0xdfff)
			goto invalid_sequence; // utf-16 surrogate
		if (value < 0x80) {
			// ASCII
			parser_append_char(parser, value);
		} else if (value < 0x800) {
			// two-byte sequence
			parser_append_char(parser, 0xc0 | value >> 6);
			parser_append_char(parser, 0x80 | (value & 63));
		} else if (value < 0x10000) {
			// three-byte sequence
			parser_append_char(parser, 0xe0 | value >> 12);
			parser_append_char(parser, 0x80 | ((value >> 6) & 63));
			parser_append_char(parser, 0x80 | (value & 63));
		} else {
			// four-byte sequence
			parser_append_char(parser, 0xf0 | value >> 18);
			parser_append_char(parser, 0x80 | ((value >> 12) & 63));
			parser_append_char(parser, 0x80 | ((value >> 6) & 63));
			parser_append_char(parser, 0x80 | (value & 63));
		}
		} break;
	default:
		goto invalid_sequence;
	}
	*p_str = str;
}

static void
parse_quoted_value(struct parser *parser, const char *first_line) {
	const char *line = first_line;
	char delimiter = *line++;
	assert(delimiter == '"' || delimiter == '`');
	while (!parser->eof && !parser->out_of_memory) {
		char c;
		while ((c = *line++)) {
			if (c == delimiter)
				goto finish;
			if (c == '\\') {
				parse_escape_sequence(parser, &line);
			} else {
				parser_append_char(parser, c);
			}
		}
		parser_read_line(parser);
		char *newline = parser_append_one(parser, string_data);
		if (!newline) return;
		*newline = '\n';
		line = parser->line.array;
	}
finish:;
	parser_append_char(parser, 0);
}

static void
parse_line(struct parser *parser) {
	parser_read_line(parser);
	char *line = parser->line.array;
	if (!line) return; // OOM
	strip_leading_accepted_spaces(line);
	if (line[0] == 0 || line[0] == '#') {
		// blank line/comment
		return;
	}
	if (line[0] == '[') {
		strip_trailing_accepted_spaces(line);
		size_t len = strlen(line);
		if (line[len-1] != ']') {
			parser_error(parser, "Missing ] to match [");
			return;
		}
		line += 1;
		len -= 2;
		if (!parser_realloc(parser, current_section, len + 1))
			return;
		char *current_section = parser->current_section.array;
		memcpy(current_section, line, len);
		current_section[len] = 0;
		parser->current_section.len = len;
		if (len)
			check_valid_key(parser, current_section);
		return;
	}
	printf("%s|%s\n",parser->current_section.array,line);
	size_t equals_idx;
	for (size_t i = 0; ; i++) {
		if (line[i] == '=') {
			equals_idx = i;
			break;
		}
		if (line[i] == 0) {
			parser_error(parser, "Line should start with [ or contain an =");
			return;
		}
	}
	if (equals_idx == 0) {
		parser_error(parser, "Expected key name before =");
		return;
	}
	size_t key_idx = parser->string_data.count;
	{
		// Parse key
		char *key = parser_append(parser, string_data, parser->current_section.len + 1 + equals_idx + 1);
		char *p = key;
		if (parser->current_section.len) {
			memcpy(p, parser->current_section.array, parser->current_section.len);
			p += parser->current_section.len;
			*p++ = '.';
		}
		memcpy(p, line, equals_idx);
		p[equals_idx] = 0;
		strip_trailing_accepted_spaces(p);
		check_valid_key(parser, key);
	}
	size_t value_start_idx = equals_idx + 1;
	while (line[value_start_idx] == ' ' || line[value_start_idx] == '\t')
		value_start_idx++;
	size_t value_idx = parser->string_data.count;
	if (line[value_start_idx] == '"' || line[value_start_idx] == '`') {
		parse_quoted_value(parser, &line[value_start_idx]);
	} else {
		char *value = &line[value_start_idx];
		strip_trailing_accepted_spaces(value);
		size_t value_sz = strlen(value) + 1;
		char *value_out = parser_append(parser, string_data, value_sz);
		if (!value_out) return;
		memcpy(value_out, value, value_sz);
	}
	struct parser_item *item = parser_append_one(parser, items);
	if (!item) return;
	item->key = key_idx;
	item->value = value_idx;
	item->line = parser->line_number;
}

static void
set_error(pom_error **error, pom_error *e) {
	if (error) {
		*error = e;
	} else {
		free(e);
	}
}

static void conf_free_list_append(struct main_conf *conf, struct to_free *mem) {
	mem->next = NULL;
	if (conf->to_free_tail) {
		conf->to_free_tail->next = mem;
		conf->to_free_tail = mem;
	} else {
		conf->to_free_head = conf->to_free_tail = mem;
	}
}

static void *conf_calloc(struct main_conf *conf, size_t nmemb, size_t sz) {
	if (nmemb > SIZE_MAX / (2*sz)) return NULL;
	struct to_free *mem = calloc(1, sizeof(struct to_free) + nmemb * sz);
	if (!mem) return NULL;
	conf_free_list_append(conf, mem);
	return &mem->data[0];
}

static void conf_free(struct main_conf *conf) {
	if (!conf) return;
	for (struct to_free *next, *f = conf->to_free_head; f; f = next) {
		next = f->next;
		free(f);
	}
	free(conf);
}

static int
conf_item_cmp_qsort(const void *va, const void *vb) {
	const struct conf_item *item_a = va;
	const struct conf_item *item_b = vb;
	return strcmp(item_a->key, item_b->key);
}

/*
// Returns true if `descendant` starts with `ancestor.`.
static bool
is_descendant(const char *ancestor, const char *descendant) {
	size_t ancestor_len = strlen(ancestor);
	return memcmp(ancestor, descendant, ancestor_len) == 0
		&& descendant[ancestor_len] == '.';
}
*/

static size_t
conf_binary_search(const pom_conf *conf, const char *key, char nxt_char, bool *found) {
	size_t lo = 0;
	size_t hi = conf->items_count;
	size_t key_len = strlen(key);
	while (lo < hi) {
		size_t mid = (lo + hi) / 2;
		const char *mid_key = conf->items[mid].key + conf->prefix_len;
		int cmp = memcmp(key, mid_key, key_len);
		if (cmp == 0)
			cmp = nxt_char - mid_key[key_len];
		if (cmp < 0) {
			hi = mid;
		} else if (cmp > 0) {
			lo = mid + 1;
		} else {
			if (found) *found = true;
			return mid;
		}
	}
	if (found) *found = false;
	return lo;
}

static size_t
conf_binary_search_sections(const pom_conf *conf, const char *key, char nxt_char, bool *found) {
	size_t lo = 0;
	size_t hi = conf->sections_count;
	size_t key_len = strlen(key);
	while (lo < hi) {
		size_t mid = (lo + hi) / 2;
		const char *mid_key = conf->sections[mid].key + conf->prefix_len;
		int cmp = memcmp(key, mid_key, key_len);
		if (cmp == 0)
			cmp = nxt_char - mid_key[key_len];
		if (cmp < 0) {
			hi = mid;
		} else if (cmp > 0) {
			lo = mid + 1;
		} else {
			if (found) *found = true;
			return mid;
		}
	}
	if (found) *found = false;
	return lo;
}

pom_conf *
parser_finish(struct parser *parser) {
	if (parser->out_of_memory || parser->errors.count) {
		return NULL;
	}
	struct main_conf *conf = calloc(1, sizeof *conf);
	if (!conf) {
		parser_out_of_memory(parser);
		return NULL;
	}
	conf->empty_section.main = conf;
	size_t items_count = parser->items.count;
	struct conf_item *items = conf_calloc(conf, items_count, sizeof(struct conf_item));
	char *filename = conf_calloc(conf, strlen(parser->filename) + 1, 1);
	if (!items || !filename) {
	out_of_memory:
		parser_out_of_memory(parser);
		conf_free(conf);
		return NULL;
	}
	strcpy(filename, parser->filename);
	// we made room for the to_free header in pom_load.
	struct to_free *string_data = (struct to_free *)parser->string_data.array;
	// stop this from getting freed
	parser->string_data.array = NULL;
	conf_free_list_append(conf, string_data);

	for (size_t i = 0; i < items_count; i++) {
		const struct parser_item *parser_item = &parser->items.array[i];
		struct conf_item *conf_item = &items[i];
		conf_item->file = filename;
		conf_item->line = parser_item->line;
		conf_item->key = ((char*)string_data->data) + (parser_item->key - sizeof(struct to_free));
		conf_item->value = ((char*)string_data->data) + (parser_item->value - sizeof(struct to_free));
#if HAVE_ATOMICS
		atomic_init(&conf_item->read, false);
#else
		conf_item->read = false;
#endif
	}
	qsort(items, items_count, sizeof *items, conf_item_cmp_qsort);
	// TODO: check for duplicates

	pom_conf *root = conf_calloc(conf, 1, sizeof *root);
	if (!root) goto out_of_memory;
	root->main = conf;
	root->prefix_len = 0;
	root->items = items;
	root->items_count = items_count;
	size_t sections_count = 0;
	for (size_t i = 0; i < items_count; i++) {
		struct conf_item *item = &items[i];
		for (const char *p = item->key; p; ) {
			const char *dot = strchr(p, '.');
			if (!dot) break;
			sections_count += i == 0
				|| strncmp(item->key, items[i-1].key, dot + 1 - item->key) != 0;
			p = dot + 1;
		}
	}
	struct conf_section *sections = conf_calloc(conf, sections_count, sizeof *sections);
	if (!sections) goto out_of_memory;
	root->sections = sections;
	root->sections_count = sections_count;
	struct conf_section *section = sections;
	for (size_t i = 0; i < items_count; i++) {
		struct conf_item *item = &items[i];
		for (const char *p = item->key, *dot; p; p = dot + 1) {
			dot = strchr(p, '.');
			if (!dot) break;
			size_t key_len = dot - item->key;
			if (i && strncmp(item->key, items[i-1].key, key_len + 1) == 0)
				continue; // section was already created
			// create section
			char *section_key = conf_calloc(conf, key_len + 1, 1);
			if (!section_key) {
				conf_free(conf);
				return NULL;
			}
			section->key = section_key;
			memcpy(section_key, item->key, key_len);
			section_key[key_len] = 0;
			//    Note: + (...) is to not include key foo.bar in section(conf, "foo.bar")
			size_t i_start = i + (item->key[key_len] == 0);
			size_t i_end = conf_binary_search(root, section_key, '.' + 1, NULL);
			section->conf.items = items + i_start;
			section->conf.items_count = i_end - i_start;
			section->conf.prefix_len = strlen(section_key) + 1/* dot */;
			section->conf.main = conf;
			section++;
		}
	}
	assert(section == sections + sections_count);
	for (size_t i = 0; i < sections_count; i++) {
		section = &sections[i];
		// set up sub-sections.
		section->conf.sections = section;
		section->conf.sections_count = conf_binary_search_sections(root, section->key, '.' + 1, NULL) - i;
	}
	return root;
}

pom_conf *
pom_load(const char *filename,
	size_t (*read_func)(void *userdata, char *buf, size_t len),
	void *userdata, pom_error **error) {
	if (!filename)
		fatal_error("%s called with NULL file name", __func__);
	if (!read_func)
		fatal_error("%s called with NULL read function", __func__);
	if (error) *error = NULL;
	// Start by allocating out-of-memory error, so we can just return
	// it if we run out of memory.
	pom_error *out_of_memory = make_error(filename, 1, "Out of memory.");
	if (!out_of_memory) return NULL;
	char *current_section = calloc(1, 1);
	if (!current_section) {
		set_error(error, out_of_memory);
		return NULL;
	}
	struct parser *parser = calloc(1, sizeof *parser);
	if (!parser) {
		free(current_section);
		set_error(error, out_of_memory);
		return NULL;
	}
	parser->filename = filename;
	parser->out_of_memory_error = out_of_memory;
	parser->read_func = read_func;
	parser->userdata = userdata;
	parser->current_section.array = current_section;
	// make room for to_free header
	parser_append(parser, string_data, sizeof(struct to_free));
	// read into parser->buf, and skip initial BOM if present.
	parser_read_to_buf(parser, true);
	while (!(parser->eof || parser->out_of_memory))
		parse_line(parser);
	pom_conf *conf = parser_finish(parser);

	if (parser->out_of_memory) {
		set_error(error, out_of_memory);
	} else if (parser->errors.count) {
		if (error) {
			// shouldn't overflow
			size_t len = parser->errors.count * sizeof(pom_error) + parser->error_messages.count + strlen(filename) + 1;
			// convert parser_errors to pom_error.
			pom_error *errors = malloc(len);
			if (errors) {
				char *messages = (char *)(errors + parser->errors.count);
				memcpy(messages,
					parser->error_messages.array,
					parser->error_messages.count);
				char *filename = (char *)messages + parser->error_messages.count;
				strcpy(filename, parser->filename);
				for (size_t i = 0; i < parser->errors.count; i++) {
					const struct parser_error *parser_error = &parser->errors.array[i];
					errors[i].file = filename;
					errors[i].line = parser_error->line;
					errors[i].message = messages + parser_error->message;
					errors[i].next = i == parser->errors.count - 1 ? NULL : &errors[i+1];
				}
				*error = errors;
			} else {
				*error = parser->out_of_memory_error;
			}
		}
		free(parser->errors.array);
		free(parser->error_messages.array);
	}
	if (!error || *error != out_of_memory) {
		free(out_of_memory);
	}
	free(parser->line.array);
	free(parser->current_section.array);
	free(parser->string_data.array);
	free(parser->items.array);
	free(parser);
	return conf;
}

static size_t
read_string(void *vpstring, char *buf, size_t len) {
	const char **pstring = vpstring;
	const char *string = *pstring;
	size_t i;
	for (i = 0; i < len; i++, string++) {
		if (*string == 0) break;
		buf[i] = *string;
	}
	*pstring = string;
	return i;
}

pom_conf *
pom_load_string(const char *filename, const char *string, pom_error **error) {
	return pom_load(filename, read_string, &string, error);
}

#ifndef POM_NO_STDIO
static size_t
read_file(void *file, char *buf, size_t len) {
	return fread(buf, 1, len, file);
}

pom_conf *
pom_load_file(const char *filename, FILE *file, pom_error **error) {
	if (!filename)
		fatal_error("%s called with NULL file name", __func__);
	if (!file)
		fatal_error("%s called with NULL file", __func__);
	return pom_load(filename, read_file, file, error);
}

pom_conf *
pom_load_path(const char *path, pom_error **error) {
	if (!path)
		fatal_error("%s called with NULL file name", __func__);
	FILE *fp = fopen(path, "rb");
	if (!fp) {
		if (error) {
			const char *message = strerror(errno);
			*error = make_error(path, 1, "Couldn't open file: %s", message);
		}
		return NULL;
	}
	pom_conf *conf = pom_load_file(path, fp, error);
	fclose(fp);
	return conf;
}
#endif

void
pom_conf_free(pom_conf *conf) {
	conf_free(conf->main);
}

static void
check_conf_(const pom_conf *conf, const char *func) {
	if (!conf)
		fatal_error("NULL configuration passed to %s", func);
}
#define check_conf(conf) check_conf_(conf, __func__)

const pom_item *
pom_conf_next_item(const pom_conf *conf, pom_item_iter **p_iter) {
	check_conf(conf);
	if (!p_iter) fatal_error("NULL iter passed to %s", __func__);
	if (!*p_iter) {
		*p_iter = calloc(1, sizeof **p_iter);
		if (!*p_iter) return NULL;
		(*p_iter)->conf = conf;
		(*p_iter)->conf_item = conf->items;
	}
	pom_item_iter *iter = *p_iter;
	if (iter->conf != conf)
		fatal_error("%s being called with inconsistent configurations for a single iterator", __func__);
	if (iter->conf_item >= conf->items + conf->items_count) {
		free(iter);
		*p_iter = NULL;
		return NULL;
	}
	iter->item.file = iter->conf_item->file;
	iter->item.line = iter->conf_item->line;
	iter->item.key = iter->conf_item->key + conf->prefix_len;
	iter->item.value = iter->conf_item->value;
	iter->conf_item++;
	return &iter->item;
}

const char *
pom_conf_next_unread_key(const pom_conf *conf, pom_unread_key_iter **p_iter) {
	check_conf(conf);
	if (!p_iter) fatal_error("NULL iter passed to %s", __func__);
	if (!*p_iter) {
		*p_iter = malloc(sizeof **p_iter);
		if (!*p_iter) return NULL;
		(*p_iter)->conf = conf;
		(*p_iter)->conf_item = conf->items;
	}
	pom_unread_key_iter *iter = *p_iter;
	if (iter->conf != conf)
		fatal_error("%s being called with inconsistent configurations for a single iterator", __func__);
	for (; iter->conf_item < conf->items + conf->items_count; iter->conf_item++) {
		if (!(
		#if HAVE_ATOMICS
			atomic_load_explicit(&iter->conf_item->read, memory_order_relaxed)
		#else
			iter->conf_item->read
		#endif
		)) {
			const char *key = iter->conf_item->key + conf->prefix_len;
			iter->conf_item++;
			return key;
		}
	}
	free(iter);
	*p_iter = NULL;
	return NULL;
}

const char *
pom_conf_next_key(const pom_conf *conf, pom_key_iter **p_iter) {
	check_conf(conf);
	if (!p_iter) fatal_error("NULL iter passed to %s", __func__);
	if (!*p_iter) {
		*p_iter = malloc(sizeof **p_iter);
		if (!*p_iter) return NULL;
		(*p_iter)->conf = conf;
		(*p_iter)->conf_item = conf->items;
		(*p_iter)->prev_key = NULL;
	}
	pom_key_iter *iter = *p_iter;
	if (iter->conf != conf)
		fatal_error("%s being called with inconsistent configurations for a single iterator", __func__);
	for (; iter->conf_item < conf->items + conf->items_count; iter->conf_item++) {
		const char *key = iter->conf_item->key + conf->prefix_len;
		size_t first_component_len = strcspn(key, ".");
		if (!iter->prev_key || strncmp(iter->prev_key, key, first_component_len) != 0) {
			// new first component
			char *first_component = realloc(iter->prev_key, first_component_len + 1);
			if (!first_component) return NULL;
			iter->prev_key = first_component;
			memcpy(first_component, key, first_component_len);
			first_component[first_component_len] = 0;
			iter->conf_item++;
			return first_component;
		}
	}
	free(iter->prev_key);
	free(iter);
	*p_iter = NULL;
	return NULL;
}

struct conf_item *
conf_get_item(const pom_conf *conf, const char *key, const char *func) {
	check_conf_(conf, func);
	if (!key)
		fatal_error("%s called with key = NULL", func);
	bool found;
	size_t i = conf_binary_search(conf, key, 0, &found);
	if (found)
		return &conf->items[i];
	else
		return NULL;
}
#define conf_get_item(conf, key) conf_get_item(conf, key, __func__)

const char *
pom_conf_get(const pom_conf *conf, const char *key) {
	struct conf_item *item = conf_get_item(conf, key);
	if (item) {
	#if HAVE_ATOMICS
		atomic_store_explicit(&item->read, true, memory_order_relaxed);
	#else
		item->read = true;
	#endif
		return item->value;
	} else {
		return NULL;
	}
}

const char *
pom_conf_get_or_default(const pom_conf *conf, const char *key, const char *dflt) {
	const char *value = pom_conf_get(conf, key);
	return value ? value : dflt;
}

bool
pom_conf_has(const pom_conf *conf, const char *key) {
	return conf_get_item(conf, key) != NULL;
}

bool
pom_conf_location(const pom_conf *conf, const char *key, const char **file, uint64_t *line) {
	struct conf_item *item = conf_get_item(conf, key);
	if (item) {
		if (file) *file = item->file;
		if (line) *line = item->line;
		return true;
	} else {
		if (file) *file = NULL;
		if (line) *line = 0;
		return false;
	}
}

const pom_conf *
pom_conf_section(const pom_conf *conf, const char *key) {
	bool found;
	size_t i = conf_binary_search_sections(conf, key, 0, &found);
	if (found)
		return &conf->sections[i].conf;
	else
		return &conf->main->empty_section;
}