git.y1.nz

base.c

/* This file contains the core parser functionality, primarily */
/* translated from the ABNF given in appendix A of [RFC3986]. */

#include <stdlib.h> /* malloc/calloc */
#include <assert.h> /* assert */
#include <stdio.h> /* printf */
#include <string.h> /* strcpy, strlen */

#include "okra.h"

/* parser-internal data shapes */
typedef struct {
	int start;
	int end;
} OkraStringPiece;

typedef struct {
	OkraStringPiece *value;
	OkraStringPiece *userinfo;
	OkraStringPiece *host;
	OkraStringPiece *port;
} OkraAuthorityComponent;

typedef struct {
	OkraStringPiece *value;

	// TODO: this
	// OkraVector /* OkraStringPiece */ segments;
	// OkraStringPiece *segments[MAX_SEGMENT_COUNT];
} OkraPathComponent;

typedef struct {
	/* reference to the original input buffer. */
	const char *buffer;

	/* data that is populated as the URI is constructed, */
	/* all NULLable. */
	OkraStringPiece *value;
	OkraStringPiece *scheme;
	OkraAuthorityComponent *authority;
	OkraPathComponent *path;
	OkraStringPiece *query;
	OkraStringPiece *fragment;
} OkraRawUri;

typedef struct {
	OkraAuthorityComponent *authority;
	OkraPathComponent *path;
} OkraRelativePart;

#define DEF_SINGLE(name, cond)  \
int \
name(const char *s, int i) \
{ \
	return (cond) ? i+1 : -1; \
}

#define RANGE(lo, c, hi)  (lo <= c && c <= hi)
#define IS_DIGIT(c)  (c >= '0' && c <= '9')
#define IS_ALPHA(c)  (RANGE('a', c, 'z') || RANGE('A', c, 'Z'))
#define IS_HEXDIG(c)  (IS_DIGIT(c) || RANGE('a', c, 'f') || RANGE('A', c, 'F'))
#define IS_GEN_DELIM(c)   ( \
	s[i] == ':' || s[i] == '/' || s[i] == '?' || s[i] == '#' || \
	s[i] == '[' || s[i] == ']' || s[i] == '@' \
)
#define IS_SUB_DELIM(c)  ( \
	s[i] == '!' || s[i] == '$' || s[i] == '&' || s[i] == '\'' || \
	s[i] == '(' || s[i] == ')' || s[i] == '*' || s[i] == '+' || \
	s[i] == ',' || s[i] == ';' || s[i] == '=' \
)
#define IS_UNRESERVED(c)  ( \
	(s[i] == '-' || s[i] == '.' || s[i] == '_' || s[i] == '~') || \
	IS_ALPHA(s[i]) || IS_DIGIT(s[i]) \
)
#define IS_RESERVED(c)  (IS_GEN_DELIM(s[i]) || IS_SUB_DELIM(s[i]))

int okra_parse_digit(const char *s, int i) { return IS_DIGIT(s[i]) ? i+1 : -1; }
int okra_parse_alpha(const char *s, int i) { return IS_ALPHA(s[i]) ? i+1 : -1; }
int okra_parse_hexdig(const char *s, int i) { return IS_HEXDIG(s[i]) ? i+1 : -1; }
int okra_parse_gen_delim(const char *s, int i) {
	return IS_GEN_DELIM(s[i]) ? i+1 : -1;
}
int okra_parse_sub_delim(const char *s, int i) {
	return IS_SUB_DELIM(s[i]) ? i+1 : -1;
}

int okra_parse_unreserved(const char *s, int i) {
	return IS_UNRESERVED(s[i]) ? i+1 : -1;
}
int okra_parse_reserved(const char *s, int i) {
	return IS_RESERVED(s[i]) ? i+1 : -1;
}
int okra_parse_pct_encoded(const char *s, int i) {
	return (
		s[i] == '%' && IS_HEXDIG(s[i+1]) && IS_HEXDIG(s[i+2])
	) ? i+3 : -1;
}

int
okra_parse_pchar(const char *s, int i)
{
	int ret = okra_parse_unreserved(s, i);
	if (ret == -1) ret = okra_parse_pct_encoded(s, i);
	if (ret == -1) ret = okra_parse_sub_delim(s, i);
	if (ret == -1) ret = (s[i] == ':' || s[i] == '@') ? i+1 : -1;
	return ret;
}

OkraStringPiece *
okra_parse_fragment(const char *s, int i)
{
	OkraStringPiece *ret = NULL;

	int current = i, next;
	for (;;) {
		next = okra_parse_pchar(s, current);
		if (next == -1)
			next = (s[current] == '/' || s[current] == '?') ?
				current+1 :
				-1;

		if (next == -1) break;
		current = next;
	}

	ret = malloc(sizeof(OkraStringPiece));
	ret->start = i;
	ret->end = current;
	return ret;
}

OkraStringPiece *
okra_parse_query(const char *s, int i)
{
	return okra_parse_fragment(s, i);
}

int
okra_parse_segment_nz_nc(const char *s, int i)
{
	char c;
	int current = i, next;
	for (;;) {
		next = okra_parse_unreserved(s, current);
		if (next == -1) next = okra_parse_sub_delim(s, current);
		if (next == -1) next = s[current] == '@' ? current+1 : -1;
		if (next == -1) next = okra_parse_pct_encoded(s, current);

		if (next == -1) break;
		current = next;
	}
	if (current == i) return -1;
	return current;
}

int
okra_parse_segment_nz(const char *s, int i)
{
	int current = i, next;
	for (;;) {
		next = okra_parse_pchar(s, current);

		if (next == -1) break;
		current = next;
	}
	if (current == i) return -1;
	return current;
}

int
okra_parse_segment(const char *s, int i)
{
	int current = i, next;
	for (;;) {
		next = okra_parse_pchar(s, current);

		if (next == -1) break;
		current = next;
	}
	return current;
}

OkraPathComponent *
okra_parse_path_empty(const char *s, int i)
{
	OkraPathComponent *ret = NULL;
	int next = okra_parse_pchar(s, i);
	if (next != -1) return NULL;

	ret = calloc(1, sizeof(OkraPathComponent));
	ret->value = calloc(1, sizeof(OkraStringPiece));
	ret->value->start = ret->value->end = i;
	return ret;
}

OkraPathComponent *
okra_parse_path_abempty(const char *s, int i)
{
	OkraPathComponent *ret = calloc(1, sizeof(OkraPathComponent));
	int current = i, next;

	ret->value = calloc(1, sizeof(OkraStringPiece));
	ret->value->start = i;

	for (;;) {
		next = s[current] == '/' ? current+1 : -1;
		// TODO convert okra_parse_segment to return OkraStringPiece,
		// TODO insert them into ret->segments
		if (next != -1) next = okra_parse_segment(s, next);

		if (next == -1) break;
		current = next;
	}
	ret->value->end = current;
	return ret;
}

OkraPathComponent *
okra_parse_path_rootless(const char *s, int i)
{
	OkraPathComponent *ret = NULL;
	int current = i, next;
	next = okra_parse_segment_nz(s, current);
	if (next != -1) ret = okra_parse_path_abempty(s, next);
	if (ret == NULL) return NULL;

	// TODO pass the segment_nz to okra_parse_path_abempty...
	ret->value->start = i;

	return ret;
}

OkraPathComponent *
okra_parse_path_noscheme(const char *s, int i)
{
	OkraPathComponent *ret = NULL;
	int current = i, next;
	next = okra_parse_segment_nz_nc(s, current);
	if (next != -1) ret = okra_parse_path_abempty(s, next);
	if (ret == NULL) return NULL;
	
	ret->value->start = i;
	return ret;
}

OkraPathComponent *
okra_parse_path_absolute(const char *s, int i)
{
	OkraPathComponent *ret = NULL;
	int current = i, next;

	if (s[current] != '/') return NULL;
	current++;

	ret = okra_parse_path_rootless(s, current);
	if (ret != NULL) {
		ret->value->start = i;
		return ret;
	}

	ret = calloc(1, sizeof(OkraPathComponent));
	ret->value = calloc(1, sizeof(OkraStringPiece));
	ret->value->start = i;
	ret->value->end = i + 1;
	return ret;
}

OkraPathComponent *
okra_parse_path(const char *s, int i)
{
	OkraPathComponent *ret = NULL, *other;
	ret = okra_parse_path_abempty(s, i);
	if (ret == NULL) ret = okra_parse_path_absolute(s, i);
	if (ret == NULL) ret = okra_parse_path_noscheme(s, i);
	if (ret == NULL) ret = okra_parse_path_rootless(s, i);
	if (ret == NULL) ret = okra_parse_path_empty(s, i);
	return ret;
}

int
okra_parse_reg_name(const char *s, int i)
{
	int current = i, next;
	for (;;) {
		next = okra_parse_unreserved(s, current);
		if (next == -1) next = okra_parse_sub_delim(s, current);
		if (next == -1) next = okra_parse_pct_encoded(s, current);
		if (next == -1) break;
		current = next;
	}
	return current;
}

int
okra_parse_dec_octet(const char *s, int i)
{
	if (IS_DIGIT(s[i]) && !IS_DIGIT(s[i+1])) return i+1;
	if (s[i] >= '1' && s[i] <= '9' && IS_DIGIT(s[i+1])) return i+2;
	if (
		(s[i] == '1' && IS_DIGIT(s[i+1]) && IS_DIGIT(s[i+2])) ||
		(s[i] == '2' && RANGE('0', s[i+1], '4') && IS_DIGIT(s[i+2])) ||
		(s[i] == '2' && s[i+1] == '5' && RANGE('0', s[i+2], '5'))
	) return i+3;
	return -1;
}

int
okra_parse_ipv4_address(const char *s, int i)
{
	int next = i;
	next = okra_parse_dec_octet(s, next);
	if (next != -1) next = s[next] == '.' ? next+1 : -1;
	if (next != -1) next = okra_parse_dec_octet(s, next);
	if (next != -1) next = s[next] == '.' ? next+1 : -1;
	if (next != -1) next = okra_parse_dec_octet(s, next);
	if (next != -1) next = s[next] == '.' ? next+1 : -1;
	if (next != -1) next = okra_parse_dec_octet(s, next);
	return next;
}

int
okra_parse_h16(const char *s, int i)
{
	int matches = 0;
	int current = i, next;
	for (;;) {
		next = okra_parse_hexdig(s, current);
		if (next == -1) break;
		current = next;
		matches++;
		if (matches == 4) break;
	}
	if (current == i) return -1;
	return current;
}

int
okra_parse_ls32(const char *s, int i)
{
	int next = okra_parse_h16(s, i);
	if (next != -1) next = s[next] == ':' ? next+1 : -1;
	if (next != -1) next = okra_parse_h16(s, next);
	if (next != -1) return next;

	return okra_parse_ipv4_address(s, i);
}

int
okra_parse_ipv6_address(const char *s, int i)
{
	return -1; // TODO this rule is really ugly :(
}

int
okra_parse_ipvfuture(const char *s, int i)
{
	if (s[i] != 'v') return -1;
	i++;
	if (okra_parse_hexdig(s, i) == -1) return -1;
	i++;
	if (s[i] != '.') return -1;
	i++;
	
	int current = i, next;
	for (;;) {
		next = okra_parse_unreserved(s, next);
		if (next == -1) next = okra_parse_sub_delim(s, next);
		if (next == -1) next = s[next] == ':' ? next+1 : -1;
		if (next == -1) break;
		current = next;
	}
	if (current == i) return -1;
	return current;
}

int
okra_parse_ip_literal(const char *s, int i)
{
	int next;
	if (s[i] != '[') return -1;
	i++;

	next = okra_parse_ipv6_address(s, i);
	if (next == -1) next = okra_parse_ipvfuture(s, i);
	i = next;
	if (s[i] != ']') return -1;
	i++;
	return i;
}

OkraStringPiece *
okra_parse_port(const char *s, int i)
{
	OkraStringPiece *ret = NULL;
	int current = i, next;
	for (;;) {
		next = okra_parse_digit(s, current);
		if (next == -1) break;
		current = next;
	}
	ret = malloc(sizeof(OkraStringPiece));
	ret->start = i;
	ret->end = current;
	return ret;
}

OkraStringPiece *
okra_parse_host(const char *s, int i)
{
	OkraStringPiece *ret = NULL;
	int next = okra_parse_ip_literal(s, i);
	if (next == -1) next = okra_parse_ipv4_address(s, i);
	if (next == -1) next = okra_parse_reg_name(s, i);

	if (next != -1) {
		ret = malloc(sizeof(OkraStringPiece));
		ret->start = i;
		ret->end = next;
	}
	return ret;
}

OkraStringPiece *
okra_parse_userinfo(const char *s, int i)
{
	OkraStringPiece *ret = NULL;
	int current = i, next;
	for (;;) {
		next = okra_parse_unreserved(s, current);
		if (next == -1) next = okra_parse_pct_encoded(s, current);
		if (next == -1) next = okra_parse_sub_delim(s, current);
		if (next == -1) next = s[current] == ':' ? current+1 : -1;
		if (next == -1) break;
		current = next;
	}
	if (current == -1) return NULL;

	ret = malloc(sizeof(OkraStringPiece));
	ret->start = i;
	ret->end = current;
	return ret;
}

OkraAuthorityComponent *
okra_parse_authority(const char *s, int i)
{
	int i0 = i, next;
	OkraAuthorityComponent *ret = NULL;
	OkraStringPiece *userinfo = NULL;
	OkraStringPiece *host = NULL;
	OkraStringPiece *port = NULL;
	OkraStringPiece *value = NULL;

	// TODO clean this logic up...
	userinfo = okra_parse_userinfo(s, i);
	if (userinfo != NULL) {
		next = userinfo->end;
		next = s[next] == '@' ? next+1 : -1;
		if (next != -1) i = next;
		else {
			free(userinfo);
			userinfo = NULL;
		}
	}
	
	host = okra_parse_host(s, i);
	if (host == NULL) {
		if (userinfo != NULL) free(userinfo);
		return NULL;
	}
	i = host->end;

	if (s[i] == ':') {
		next = i+1;
		port = okra_parse_port(s, next);
		if (port != NULL) i = port->end;
	}

	value = malloc(sizeof(OkraStringPiece));
	value->start = i0;
	value->end = i;

	ret = malloc(sizeof(OkraAuthorityComponent));
	ret->userinfo = userinfo;
	ret->host = host;
	ret->port = port;
	ret->value = value;
	return ret;
}

OkraStringPiece *
okra_parse_scheme(const char *s, int i)
{
	OkraStringPiece *ret = NULL;
	int current = i, next = okra_parse_alpha(s, current);
	if (next == -1) return NULL;
	current = next;

	for (;;) {
		next = okra_parse_alpha(s, current);
		if (next == -1) next = okra_parse_digit(s, current);
		if (next == -1) next = (s[current] == '+' || s[current] == '-' || s[current] == '.') ? current+1 : -1;
		if (next == -1) break;
		current = next;
	}

	ret = malloc(sizeof(OkraStringPiece));
	ret->start = i;
	ret->end = current;
	return ret;
}

OkraRelativePart *
okra_parse_relative_part(const char *s, int i)
{
	OkraRelativePart *ret = NULL;
	OkraPathComponent *path = NULL;
	OkraAuthorityComponent *authority = NULL;
	int current = i, next;

	/* "//" authority path-abempty */
	next = (s[current] == '/' && s[current+1] == '/') ? current+2 : -1;
	if (next != -1) {
		authority = okra_parse_authority(s, next);
		next = authority == NULL ? -1 : authority->value->end;
	}
	if (next != -1) path = okra_parse_path_abempty(s, next);
	if (path != NULL) {
		ret = malloc(sizeof(OkraRelativePart));
		ret->authority = authority;
		ret->path = path;
		return ret;
	} else if (authority != NULL) free(authority); /* clean up */

	path = okra_parse_path_absolute(s, i);
	if (path == NULL) path = okra_parse_path_noscheme(s, i);
	if (path == NULL) path = okra_parse_path_empty(s, i);
	if (path == NULL) return NULL;

	ret = malloc(sizeof(OkraRelativePart));
	ret->authority = authority;
	ret->path = path;
	assert(ret->path != NULL);
	return ret;
}

#define SAFE_FREE(name)  if (name != NULL) free(name);
void
okra_free_raw_uri(OkraRawUri *raw)
{
	SAFE_FREE(raw->scheme);
	if (raw->authority != NULL) {
		SAFE_FREE(raw->authority->value);
		SAFE_FREE(raw->authority->userinfo);
		SAFE_FREE(raw->authority->host);
		SAFE_FREE(raw->authority->port);
		SAFE_FREE(raw->authority);
	}
	if (raw->path != NULL) {
		SAFE_FREE(raw->path->value);
		SAFE_FREE(raw->path);
		// TODO list of segments
	}
	if (raw->query != NULL) SAFE_FREE(raw->query);
	if (raw->fragment != NULL) SAFE_FREE(raw->fragment);
	SAFE_FREE(raw->value);
	free(raw);

}

OkraRawUri *
okra_parse_relative_ref(const char *s, int i)
{
	int i0 = i;
	OkraRawUri *ret = NULL;
	OkraStringPiece *query = NULL;
	OkraStringPiece *fragment = NULL;
	OkraRelativePart *rel_part = NULL;

	rel_part = okra_parse_relative_part(s, i);
	if (rel_part == NULL) return NULL;
	i = rel_part->path->value->end; /* end of path is always end of rel_path. */

	int next = i;
	next = s[next] == '?' ? next+1 : -1;
	if (next != -1) {
		query = okra_parse_query(s, next);
		next = query == NULL ? -1 : query->end;
	}
	if (next != -1) i = next; // TODO clean this up.. yuck...
	next = i;

	next = s[next] == '#' ? next+1 : -1;
	if (next != -1) {
		fragment = okra_parse_fragment(s, next);
		next = fragment == NULL ? -1 : fragment->end;
	}
	if (next != -1) i = next;

	ret = calloc(1, sizeof(OkraRawUri));
	ret->buffer = s;
	ret->authority = rel_part->authority;
	ret->path = rel_part->path;
	free(rel_part);
	ret->query = query;
	ret->fragment = fragment;
	ret->value = malloc(sizeof(OkraStringPiece));
	ret->value->start = i0;
	ret->value->end = i;
	return ret;
}

OkraRelativePart *
okra_parse_hier_part(const char *s, int i)
{
	OkraRelativePart *ret = NULL;
	OkraPathComponent *path = NULL;
	OkraAuthorityComponent *authority = NULL;
	int current = i, next;

	/* "//" authority path-abempty */
	next = (s[current] == '/' && s[current+1] == '/') ? current+2 : -1;
	if (next != -1) {
		authority = okra_parse_authority(s, next);
		next = authority == NULL ? -1 : authority->value->end;
	}
	if (next != -1) path = okra_parse_path_abempty(s, next);
	if (path != NULL) {
		ret = malloc(sizeof(OkraRelativePart));
		ret->authority = authority;
		ret->path = path;
		return ret;
	} else if (authority != NULL) free(authority); /* clean up */

	path = okra_parse_path_absolute(s, i);
	if (path == NULL) path = okra_parse_path_rootless(s, i);
	if (path == NULL) path = okra_parse_path_empty(s, i);
	if (path == NULL) return NULL;

	ret = malloc(sizeof(OkraRelativePart));
	ret->authority = authority;
	ret->path = path;
	assert(ret->path != NULL);
	return ret;
}

OkraRawUri *
okra_parse_absolute_uri(const char *s, int i)
{
	int i0 = i;
	OkraRawUri *ret = NULL;
	OkraRelativePart *rel_part = NULL; 
	OkraStringPiece *scheme = NULL;
	OkraStringPiece *query = NULL;
	OkraStringPiece *value = NULL;

	scheme = okra_parse_scheme(s, i);
	if (scheme == NULL) return NULL;
	i = scheme->end;

	if (s[i] != ':') {
		free(scheme);
		return NULL;
	}
	i++;

	// TODO extract components from hier_part? ew...
	
	rel_part = okra_parse_hier_part(s, i);
	if (rel_part == NULL) {
		free(scheme);
		return NULL;
	}
	i = rel_part->path->value->end;

	if (s[i] == '?') {
		int next = i+1;
		query = okra_parse_query(s, next);
		if (query != NULL) i = query->end;
	}

	ret = calloc(1, sizeof(OkraRawUri));
	ret->buffer = s;
	ret->scheme = scheme;
	ret->query = query;

	value = malloc(sizeof(OkraStringPiece));
	value->start = i0;
	value->end = i;
	ret->value = value;

	assert(rel_part != NULL);
	ret->authority = rel_part->authority;
	ret->path = rel_part->path;
	free(rel_part);

	return ret;
}

OkraRawUri *
okra_parse_uri(const char *s, int i)
{
	OkraRawUri *ret = NULL;
	OkraStringPiece *fragment = NULL;
	ret = okra_parse_absolute_uri(s, i);
	if (ret == NULL) return NULL;
	assert(ret->value != NULL);
	i = ret->value->end;

	if (s[i] == '#') {
		int next = i+1;
		fragment = okra_parse_fragment(s, next);
		if (fragment != NULL) i = fragment->end;
	}

	// if (s[i] != '\0') return NULL;
	ret->fragment = fragment;
	ret->value->end = i;

	return ret;
}

OkraRawUri *
okra_parse_uri_ref(const char *s, int i)
{
	OkraRawUri *ret = NULL;

	ret = okra_parse_uri(s, i);
	if (ret != NULL && s[ret->value->end] != '\0') {
		okra_free_raw_uri(ret);
		ret = NULL;
	}
	if (ret != NULL) return ret;

	ret = okra_parse_relative_ref(s, i);
	if (ret != NULL)
		if (s[ret->value->end] != '\0') {
			okra_free_raw_uri(ret);
			ret = NULL;
		}

	return ret;
}

char *
okra_stralloc(OkraRawUri *uri, OkraStringPiece *piece)
{
	int length;
	char *ret;

	if (piece == NULL) return NULL;

	length = piece->end - piece->start;
	ret = malloc((length+1) * sizeof(char));
	for (int i = 0; i < length; i++)
		ret[i] = uri->buffer[piece->start + i];
	ret[length] = '\0';
	return ret;
}

OkraUri *
okra_parse(const char *s)
{
	OkraRawUri *raw = okra_parse_uri_ref(s, 0);
	OkraUri *ret;

	if (raw == NULL) return NULL;

	/* transfer raw data into freshly allocated buffers, free as we go */
	ret = calloc(1, sizeof(OkraUri));
	if (raw->scheme != NULL) ret->scheme = okra_stralloc(raw, raw->scheme);
	if (raw->authority != NULL) {
		ret->authority = okra_stralloc(raw, raw->authority->value);
		ret->userinfo = okra_stralloc(raw, raw->authority->userinfo);
		ret->host = okra_stralloc(raw, raw->authority->host);
		ret->port = okra_stralloc(raw, raw->authority->port);
	}
	if (raw->path != NULL) ret->path = okra_stralloc(raw, raw->path->value);
	if (raw->query != NULL) ret->query = okra_stralloc(raw, raw->query);
	if (raw->fragment != NULL) ret->fragment = okra_stralloc(raw, raw->fragment);
	okra_free_raw_uri(raw);

	/* recompose the uri into ret->uri */
	ret->uri = okra_recompose(ret);

	return ret;
}

This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.