okra | C99 URI parser library. |
| download: http://git.y1.nz/archives/okra.tar.gz | |
| README | Files | Log | Refs |
commit f33dccfc8ff065199c72fbeaf147b4fdf05c175f Author: Emma Weaver <emma@y1.nz> Date: Wed, 8 Jul 2026 11:09:12 -0500 Initial implementation of basic functionality Diffstat:
| A | .gitignore | 5 | +++++ |
| A | Makefile | 26 | ++++++++++++++++++++++++++ |
| A | README | 46 | ++++++++++++++++++++++++++++++++++++++++++++++ |
| A | TODO | 28 | ++++++++++++++++++++++++++++ |
| A | base.c | 787 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | config.mk | 4 | ++++ |
| A | merge.c | 249 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | okra.h | 60 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test/all | 11 | +++++++++++ |
| A | test/base.c | 99 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test/merge.c | 120 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test/okra.c | 75 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
12 files changed, 1510 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore @@ -0,0 +1,5 @@ +*.o +*.a +test/base +test/merge +okra diff --git a/Makefile b/Makefile @@ -0,0 +1,26 @@ +include config.mk + +all: okra.a tests + +okra.a: base.o merge.o + ar rcs okra.a *.o + +install: + cp okra.h $(PREFIX)/include + cp okra.a $(PREFIX)/lib/libokra.a + +tests: okra test/base test/merge +test/base: test/base.c okra.a + $(CC) test/base.c okra.a -o test/base +test/merge: test/merge.c okra.a + $(CC) test/merge.c okra.a -o test/merge +okra: test/okra.c okra.a + $(CC) test/okra.c okra.a -o okra + +base.o: base.c + $(CC) -c base.c -o base.o +merge.o: merge.c + $(CC) -c merge.c -o merge.o + +clean: + rm -f *.o okra.a test/base test/merge okra diff --git a/README b/README @@ -0,0 +1,46 @@ +OKRA - [RFC3986]-compliant URI Parser in pure C99 + +#### +# +# Okra is a [RFC3986]-compliant URI Parser, implemented as a single-header, pure +# C99 library with no outside dependencies. It was developed for use in various +# components of the [bro](http://git.y1.nz/bro) browser project: a browser that +# uses the base operating system, instead of building additional OS-shaped +# software on top of it. +# +#### + + Goals + - Conformant to [RFC3986] + - Robust and resilient to bad inputs + - A simple and easy-to-use API + - Lightweight, no outside dependencies + + Non-Goals + - Optimal execution speed. It's plenty fast by virtue of being written in C, + and using O(N) algorithms. + - Optimal memory usage. Other things are more important. + - Support for encodings other than ascii. It is the client's responsibility if + they want to use something else. + +### + + Build + First, update config.mk to reflect your system's configuration and your + preferences. Then, run `make` to build okra.a as well as the test binaries, + then `make install` with permissions necessary to install it on your system. + + Testing + After building them, you can run all the tests by calling `test/all`, or + by individually calling the test/* binaries. The build also produces + a program for manually playing with the library: `okra`, which you can call + with one URI (to parse it), or two URIs (to resolve the second reference + as relative to the first). + +### + + Contributing + There are probably plenty of easy-to-fix issues in this repo, as this project + is very recent. To contribute, send emails with patches to emma@y1.nz :) + "And if you use AI, you go to hell before you die." + --Mario Mario diff --git a/TODO b/TODO @@ -0,0 +1,28 @@ +Things that would improve this library: +[ ] Implement parsing of ipv6 hosts (skipped it bc lazy for min viable) + +[ ] Figure out how to (OR WHETHER TO) expose sub-component structure + as in, should an OkraUri object include: + - separated path segments? + - host/port/userinfo in addition to just Authority + Pro: It would improve the user experience, and keep the + responsibility for "parsing" internal to Okra. And the information + is already accessible, by nature of how parsing already works... + Con: it messies base.c, it incurs more complexity in merge/recompose, + it requires more-complex memory management... + +[ ] Use strcpy when possible over manually copying buffers + +[ ] Refactor the ABNF-based code to be less ad-hoc + +[ ] Use valgrind to find memory leaks (there definitely are some I think) + +[x] Add installation make targets + +[ ] Implement algorithms described in the spec: + [x] Merge relative into base URI (5.2) + [ ] Normalization/equivalence checks (6.2.2) + * is this one in-scope? + [x] Component recomposition (5.3) + +[ ] Add more extensive testing, cover more edge cases diff --git a/base.c b/base.c @@ -0,0 +1,787 @@ +/* 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; +} diff --git a/config.mk b/config.mk @@ -0,0 +1,4 @@ +# Edit this file to reflect your configuration. + +CC = cc -Wpedantic -Wextra -std=c99 +PREFIX = /usr/local diff --git a/merge.c b/merge.c @@ -0,0 +1,249 @@ +/* This file implements algorithms on already-parsed URIs. */ + +#include <string.h> /* strlen */ +#include <stdlib.h> /* malloc, calloc */ +#include <assert.h> /* assert */ + +#include "okra.h" + +/* takes any string and allocates a fresh copy of it. */ +char * +okra_strclone(const char *buffer) +{ + if (buffer == NULL) return NULL; + char *ret = malloc((strlen(buffer)+1) * sizeof(char)); + strcpy(ret, buffer); + return ret; +} + +/* described in section 5.2.3 */ +char * +okra_merge_paths(const OkraUri *base, const char *relative_path) +{ + char *ret; + int relative_length, i, last_slash_index = 0; + + relative_length = strlen(relative_path); + + if (base->authority != NULL && base->path[0] == '\0') { + ret = malloc((relative_length+1) * sizeof(char)); + ret[0] = '/'; + strcpy(ret+1, relative_path); + return ret; + } + + /* calculate the index of the right-most slash in base->path */ + i = 0; + for (;;) { + if (base->path[i] == '/') last_slash_index = i; + if (base->path[i] == '\0') break; + i++; + } + + ret = malloc((last_slash_index + relative_length + 1) * sizeof(char)); + for (i = 0; i <= last_slash_index; i++) + ret[i] = base->path[i]; + + strcpy(ret + last_slash_index + 1, relative_path); + + return ret; +} + +/* described in section 5.2.4 */ +#define IS_SEGEND(c) +char * +okra_remove_dot_segments(char *path) +{ + int length, i, ri; + int *starts, start_count = 0; + char *ret; + char ch, ch1, ch2, ch3; + + length = strlen(path); + starts = malloc((length+1) * sizeof(int)); + ret = calloc(1, (length+1) * sizeof(char)); + starts[start_count++] = path[0] == '/' ? 1 : 0; + + i = ri = 0; + ch = ch1 = ch2 = ch3 = '/'; + for (;;) { + ch3 = ch2; ch2 = ch1; ch1 = ch; + ch = path[i++]; + ret[ri++] = ch; + ret[ri] = '\0'; + + /* History looks like "/../" or "/..\0": */ + if ( + (ch == '/' || ch == '\0') && + ch1 == '.' && + ch2 == '.' && + ch3 == '/' + ) { + if (start_count > 1) start_count--; + ri = starts[start_count-1]; + ret[ri] = '\0'; + if (ch == '\0') break; + ch3 = ch2 = ch1 = ch = '/'; + continue; + } + + /* History looks like "/./" or "/.\0": */ + if ( + (ch == '/' || ch == '\0') && + ch1 == '.' && + ch2 == '/' + ) { + ri = starts[start_count-1]; + ret[ri] = '\0'; + if (ch == '\0') break; + ch3 = ch2 = ch1 = ch = '/'; + continue; + } + + if (ch == '/') starts[start_count++] = ri; + if (ch == '\0') break; + } + ret[ri] = '\0'; + free(starts); + return ret; +} + +/* refactored from psuedocode provided in section 5.2.2 */ +OkraUri * +okra_merge(const OkraUri *base, const OkraUri *ref) +{ + OkraUri *ret; + + assert(base != NULL); + assert(ref != NULL); + + ret = calloc(1, sizeof(OkraUri)); + ret->fragment = okra_strclone(ref->fragment); + + if (ref->scheme != NULL) { + ret->scheme = okra_strclone(ref->scheme); + + ret->authority = okra_strclone(ref->authority); + ret->host = okra_strclone(ref->host); + ret->port = okra_strclone(ref->port); + ret->userinfo = okra_strclone(ref->userinfo); + + ret->path = okra_strclone(ref->path); + ret->query = okra_strclone(ref->query); + goto finish_merge; + } + ret->scheme = okra_strclone(base->scheme); + + if (ref->authority != NULL) { + ret->authority = okra_strclone(ref->authority); + ret->host = okra_strclone(ref->host); + ret->port = okra_strclone(ref->port); + ret->userinfo = okra_strclone(ref->userinfo); + + ret->path = okra_remove_dot_segments(ref->path); + ret->query = okra_strclone(ref->query); + goto finish_merge; + } + ret->authority = okra_strclone(base->authority); + ret->host = okra_strclone(base->host); + ret->port = okra_strclone(base->port); + ret->userinfo = okra_strclone(base->userinfo); + + if (ref->path[0] == '\0') { + ret->path = okra_strclone(base->path); + ret->query = okra_strclone( + ref->query == NULL ? base->query : ref->query + ); + goto finish_merge; + } + + ret->query = okra_strclone(ref->query); + if (ref->path[0] == '/') { + ret->path = okra_remove_dot_segments(ref->path); + goto finish_merge; + } + + ret->path = okra_merge_paths(base, ref->path); + assert(ret->path != NULL); + ret->path = okra_remove_dot_segments(ret->path); + +finish_merge: + ret->uri = okra_recompose(ret); + return ret; +} + +/* Refactored from section 5.3 of [RFC3986]. */ +char * +okra_recompose(OkraUri *uri) +{ + char *ret, *cur; + int length = 0, i; + int scheme_length = 0; + int auth_length = 0; + int path_length = 0; + int query_length = 0; + int fragment_length = 0; + + /* calculate length */ + if (uri->scheme != NULL) { + scheme_length = strlen(uri->scheme) + 1; /* extra ":" */ + length += scheme_length; + } + if (uri->authority != NULL) { + auth_length = strlen(uri->authority) + 2; /* extra "//" */ + length += auth_length; + } + path_length = strlen(uri->path); + length += path_length; + if (uri->query != NULL) { + query_length = strlen(uri->query) + 1; /* extra "?" */ + length += query_length; + } + if (uri->fragment != NULL) { + fragment_length = strlen(uri->fragment) + 1; /* extra "#" */ + length += fragment_length; + } + + ret = malloc((length+1) * sizeof(char)); + cur = ret; + + /* populate the buffer... */ + if (uri->scheme != NULL) { + strcpy(cur, uri->scheme); + cur[scheme_length-1] = ':'; + cur += scheme_length; + } + if (uri->authority != NULL) { + cur[0] = cur[1] = '/'; + strcpy(cur+2, uri->authority); + cur += auth_length; + } + strcpy(cur, uri->path); + cur += path_length; + if (uri->query != NULL) { + cur[0] = '?'; + strcpy(cur+1, uri->query); + cur += query_length; + } + if (uri->fragment != NULL) { + cur[0] = '#'; + strcpy(cur+1, uri->fragment); + cur += fragment_length; + } + + return ret; +} + +void +okra_free(OkraUri *uri) +{ + if (uri->scheme == NULL) free(uri->scheme); + if (uri->authority == NULL) free(uri->authority); + if (uri->host == NULL) free(uri->host); + if (uri->userinfo == NULL) free(uri->userinfo); + if (uri->port == NULL) free(uri->port); + if (uri->path == NULL) free(uri->path); + if (uri->query == NULL) free(uri->query); + if (uri->fragment == NULL) free(uri->fragment); + free(uri); +} diff --git a/okra.h b/okra.h @@ -0,0 +1,60 @@ +#ifndef OKRA_OKRA_H_ +#define OKRA_OKRA_H_ + +/** + * A convenient API for accessing the internal structure of a URI. + * All char * members can be NULL. All member data is read-only and + * owned by the Okra library. + */ +typedef struct { + /** The URI, recomposed after parsing, stored in a fresh buffer. */ + char *uri; + + /** The scheme component of the URI according to section 3.1. */ + char *scheme; + + /** The authority component of the URI according to section 3.2. */ + char *authority; + + // TODO decide whether/how to include substructure like this + char *host; + char *userinfo; + char *port; + + /** The path component of the URI according to section 3.3. */ + char *path; + // TODO vector of path segments? + + /** The path component of the URI according to section 3.4. */ + char *query; + + /** The path component of the URI according to section 3.5. */ + char *fragment; +} OkraUri; + +/** + * Parse a string into an OkraUri struct. Returns NULL if the input + * is not a valid URI. The returned data should be considered read-only and must + * be freed using okra_free(). + */ +OkraUri *okra_parse(const char *input); + +/** + * Resolve a relative URI according to some base uri. Both arguments + * must be non-NULL. The returned data is independent of the + * arguments and must be freed using okra_free. + */ +OkraUri *okra_merge(const OkraUri *base, const OkraUri *ref); + +/** + * Returns a fresh string buffer containing the uri expressed + * as a string. The buffer is owned by the caller. + */ +char *okra_recompose(OkraUri *uri); + +/** + * Free all memory associated with an OkraUri. + */ +void okra_free(OkraUri *uri); + +#endif // OKRA_OKRA_H_ diff --git a/test/all b/test/all @@ -0,0 +1,11 @@ +#!/bin/sh + +# Simply, runs all the tests. + +cd test + +./base +echo "" + +./merge +echo "" diff --git a/test/base.c b/test/base.c @@ -0,0 +1,99 @@ +#include <stdio.h> /* printf */ +#include <stdlib.h> /* atoi */ + +#include "okra.h" + +int print = 0; + +#define CASE(uri_str, condition) { \ + print = 0; \ + \ + uri = okra_parse(uri_str); \ + if (condition) { \ + printf("\033[1;32m" " %d. pass" "\033[0m", test_index); \ + tests_passed++; \ + } else { \ + print = 1; \ + printf("\n"); \ + printf("\033[1;31m" " %d. fail" "\033[0m" "\n", test_index); \ + printf("%s" "\n", uri_str); \ + condition; \ + printf("\n"); \ + } \ + \ + okra_free(uri); \ + \ + test_index++; \ +} + +int +null(const void *arg) +{ + if (print) printf("[%lx] vs expected [(null)]", (unsigned long int) arg); + return arg == NULL; +} + +int +eq(const char *a, const char *b) +{ + if (print) printf("[%s] vs expected [%s] ", a, b); + + if (a == NULL || b == NULL) return 0; + + int i = 0; + for (;;) { + if (a[i] != b[i]) return 0; + if (a[i] == '\0') return 1; + i++; + } +} + +int +main(int argc, const char *argv[]) +{ + int test_index = 1; + int tests_passed = 0; + const char *str; + OkraUri *uri; + int target_index = argc == 1 ? 0 : atoi(argv[1]); + + printf("\033[1m" "Testing parser..." "\033[0m" "\n"); + + str = "http://google.com"; + CASE(str, eq(uri->scheme, "http")); + CASE(str, eq(uri->authority, "google.com")); + CASE(str, eq(uri->host, "google.com")); + + str = "mailto:user@mail.com"; + CASE(str, eq(uri->scheme, "mailto")); + CASE(str, eq(uri->path, "user@mail.com")); + CASE(str, null(uri->authority)); + + str = "foo://example.com:8042/over/there?name=ferret#nose"; + CASE(str, eq(uri->scheme, "foo")); + CASE(str, eq(uri->path, "/over/there")); + CASE(str, eq(uri->authority, "example.com:8042")); + CASE(str, eq(uri->host, "example.com")); + CASE(str, eq(uri->port, "8042")); + CASE(str, eq(uri->query, "name=ferret")); + CASE(str, eq(uri->fragment, "nose")); + + str = "urn:example:animal:ferret:nose"; + CASE(str, eq(uri->scheme, "urn")); + CASE(str, eq(uri->path, "example:animal:ferret:nose")); + + str = "example://a/b/c/%7Bfoo%7D"; + CASE(str, eq(uri->scheme, "example")); + CASE(str, eq(uri->path, "/b/c/%7Bfoo%7D")); + + str = "foo:this/is/the/path#nose/\?\?/./.a."; + CASE(str, eq(uri->scheme, "foo")); + CASE(str, eq(uri->path, "this/is/the/path")); + CASE(str, eq(uri->fragment, "nose/\?\?/./.a.")); + + printf( + "\n" "\033[1m" "Passed %d/%d" "\033[0m" "\n", + tests_passed, + test_index-1 + ); +} diff --git a/test/merge.c b/test/merge.c @@ -0,0 +1,120 @@ +#include <stdio.h> /* printf */ +#include <stdlib.h> /* atoi */ + +#include "okra.h" + +int print = 0; + +#define CASE(rel_str, condition) { \ + print = 0; \ + \ + if (target_index == 0 || target_index == test_index) { \ + ref = okra_parse(rel_str); \ + merged = okra_merge(base, ref); \ + result = okra_recompose(merged); \ + if (condition) { \ + printf("\033[1;32m" " %d. pass" "\033[0m", test_index); \ + tests_passed++; \ + } else { \ + printf("\033[1;31m" " %d. fail" "\033[0m", test_index); \ + print = 1; \ + condition; \ + printf("\n" "%10s\t\t%s" "\n", base_str, rel_str); \ + } \ + } \ + \ + okra_free(merged); \ + okra_free(ref); \ + \ + test_index++; \ +} + +int +null(const void *arg) +{ + if (print) printf("[%lx] vs expected [(null)]", (unsigned long int) arg); + return arg == NULL; +} + +int +eq(const char *a, const char *b) +{ + if (print) printf("[%s] vs expected [%s] ", a, b); + + if (a == NULL || b == NULL) return 0; + + int i = 0; + for (;;) { + if (a[i] != b[i]) return 0; + if (a[i] == '\0') return 1; + i++; + } +} + +int +main(int argc, const char *argv[]) +{ + int test_index = 1; + int tests_passed = 0; + OkraUri *ref, *uri, *merged; + char *result; + int target_index = argc == 1 ? 0 : atoi(argv[1]); + + const char *base_str = "http://a/b/c/d;p?q"; + OkraUri *base = okra_parse(base_str); + + printf("\033[1m" "Testing relative URI resolution..." "\033[0m" "\n"); + + /* "Normal Examples" from section 5.4.1 */ + CASE("g:h", eq(result, "g:h")); + CASE("g", eq(result, "http://a/b/c/g")); + CASE("./g", eq(result, "http://a/b/c/g")); + CASE("g/", eq(result, "http://a/b/c/g/")); + CASE("/g", eq(result, "http://a/g")); + CASE("//g", eq(result, "http://g")); + CASE("?y", eq(result, "http://a/b/c/d;p?y")); + CASE("g?y", eq(result, "http://a/b/c/g?y")); + CASE("#s", eq(result, "http://a/b/c/d;p?q#s")); + CASE("g#s", eq(result, "http://a/b/c/g#s")); + CASE("g?y#s", eq(result, "http://a/b/c/g?y#s")); + CASE(";x", eq(result, "http://a/b/c/;x")); + CASE("g;x", eq(result, "http://a/b/c/g;x")); + CASE("g;x?y#s", eq(result, "http://a/b/c/g;x?y#s")); + CASE("", eq(result, "http://a/b/c/d;p?q")); + CASE(".", eq(result, "http://a/b/c/")); + CASE("./", eq(result, "http://a/b/c/")); + CASE("..", eq(result, "http://a/b/")); + CASE("../", eq(result, "http://a/b/")); + CASE("../g", eq(result, "http://a/b/g")); + CASE("../..", eq(result, "http://a/")); + CASE("../../", eq(result, "http://a/")); + CASE("../../g", eq(result, "http://a/g")); + + /* "Abnormal Examples" from section 5.4.2 */ + CASE("../../../g", eq(result, "http://a/g")); + CASE("../../../../g", eq(result, "http://a/g")); + CASE("/./g", eq(result, "http://a/g")); + CASE("/../g", eq(result, "http://a/g")); + CASE("g.", eq(result, "http://a/b/c/g.")); + CASE(".g", eq(result, "http://a/b/c/.g")); + CASE("g..", eq(result, "http://a/b/c/g..")); + CASE("..g", eq(result, "http://a/b/c/..g")); + CASE("./../g", eq(result, "http://a/b/g")); + CASE("./g/.", eq(result, "http://a/b/c/g/")); + CASE("g/./h", eq(result, "http://a/b/c/g/h")); + CASE("g/../h", eq(result, "http://a/b/c/h")); + CASE("g;x=1/./y", eq(result, "http://a/b/c/g;x=1/y")); + CASE("g;x=1/../y", eq(result, "http://a/b/c/y")); + CASE("g?y/./x", eq(result, "http://a/b/c/g?y/./x")); + CASE("g?y/../x", eq(result, "http://a/b/c/g?y/../x")); + CASE("g#s/./x", eq(result, "http://a/b/c/g#s/./x")); + CASE("g#s/../x", eq(result, "http://a/b/c/g#s/../x")); + CASE("http:g", eq(result, "http:g")); + printf( + "\n" "\033[1m" "Passed %d/%d" "\033[0m" "\n", + tests_passed, + test_index-1 + ); + + free(base); +} diff --git a/test/okra.c b/test/okra.c @@ -0,0 +1,75 @@ +/** + * This provides a basic command-line interface for testing okra manually. + * Its purpose is to help developers get familiar with okra and how it + * works, and is not intended to be a useful command-line tool. It's not + * recommended, to pass URLs around raw via the command line. + */ + +#include <stdio.h> /* printf */ + +#include "okra.h" + +#define SAFE_PRINT(name, value) { \ + if (value != NULL) printf(name " [%s]" "\n", value); \ +} +#define PRINT_URI(u) { \ + SAFE_PRINT("uri ", u->uri); \ + SAFE_PRINT("scheme ", u->scheme); \ + SAFE_PRINT("authority ", u->authority); \ + SAFE_PRINT("> host ", u->host); \ + SAFE_PRINT("> userinfo", u->userinfo); \ + SAFE_PRINT("> port ", u->port); \ + SAFE_PRINT("path ", u->path); \ + SAFE_PRINT("query ", u->query); \ + SAFE_PRINT("fragment ", u->fragment); \ +} + +#define usage \ +"This is a basic program for using okra in the terminal." "\n" \ +"Usage: %s URI (parse)" "\n" \ +" %s BASE_URI REL_REF (resolve)" "\n" + +int +main(int argc, const char *argv[]) +{ + if (argc == 2) { + const char *buffer = argv[1]; + OkraUri *uri = okra_parse(argv[1]); + + if (uri == NULL) { + printf("Invalid URI :(" "\n"); + return 0; + } + PRINT_URI(uri); + okra_free(uri); + return 0; + } + + if (argc == 3) { + OkraUri *base = okra_parse(argv[1]); + OkraUri *ref = okra_parse(argv[2]); + OkraUri *result = okra_merge(base, ref); + if (base == NULL) { + printf("Invalid base URI :(" "\n"); + return 0; + } + if (ref == NULL) { + printf("Invalid ref URI :(" "\n"); + return 0; + } + printf( + " [%s]" "\n" + "+ [%s]" "\n" + "-------------------------------------" "\n", + base->uri, ref->uri + ); + PRINT_URI(result); + okra_free(base); + okra_free(ref); + okra_free(result); + return 0; + } + + printf(usage, argv[0], argv[0]); + return 1; +}
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.