You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
267 lines
7.1 KiB
267 lines
7.1 KiB
/**
|
|
* Copyright (c) 2019, The Linux Foundation. All rights reserved.
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions are
|
|
* met:
|
|
* * Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* * Redistributions in binary form must reproduce the above
|
|
* copyright notice, this list of conditions and the following
|
|
* disclaimer in the documentation and/or other materials provided
|
|
* with the distribution.
|
|
* * Neither the name of The Linux Foundation nor the names of its
|
|
* contributors may be used to endorse or promote products derived
|
|
* from this software without specific prior written permission.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
|
|
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
|
|
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
|
|
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
|
|
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
|
|
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
|
|
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
|
|
* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
|
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
|
|
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
|
|
* IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
#ifndef SBUF_PARSER_H
|
|
#define SBUF_PARSER_H
|
|
|
|
#include "sbuf.h"
|
|
|
|
/**
|
|
* Greedy Recursive Descent Parser in C
|
|
*
|
|
* Stop using strstr or regular expressions. This simple Recursive Descent Parser can be
|
|
* used to handle complex grammars.
|
|
*
|
|
* For example:
|
|
* parsing a query string form a uri
|
|
* input: "file:///foo/bar_far.so.1?_blah1&_bar=barval5&_barfar"
|
|
* expected output:
|
|
* parsed query: _blah1 =
|
|
* parsed query: _bar = barval5
|
|
* parsed query: _barfar =
|
|
*
|
|
* static int qmark(struct sbuf *buf) {
|
|
* return sbuf_char(buf, '?');
|
|
* }
|
|
* static int notandoreq(struct sbuf *buf) {
|
|
* return sbuf_notchars(buf, "&=");
|
|
* }
|
|
* static int notand(struct sbuf *buf) {
|
|
* return sbuf_notchar(buf, '&');
|
|
* }
|
|
*
|
|
* const char *name;
|
|
* int nameLen;
|
|
* const char *value;
|
|
* int valueLen;
|
|
* const char *data = "file:///foo/bar_far.so.1?_blah1&_bar=barval5&_barfar";
|
|
*
|
|
* //initialize
|
|
* sbuf_parser_init(&buf, data, strlen(data));
|
|
*
|
|
* //parse until question mark
|
|
* assert(sbuf_until(&buf, sbuf_any, qmark));
|
|
*
|
|
* //parse each query
|
|
* while(!sbuf_end(&buf)) {
|
|
* //record where the name starts
|
|
* name = sbuf_cur(&buf);
|
|
*
|
|
* //name is valid until '=' or '&'
|
|
* assert(sbuf_many1(&buf, notandoreq));
|
|
* nameLen = sbuf_cur(&buf) - name;
|
|
*
|
|
* value = 0;
|
|
* valueLen = 0;
|
|
* //if the next char is a '=' then we also get a value
|
|
* if(sbuf_char(&buf, '=')) {
|
|
* value = sbuf_cur(&buf);
|
|
*
|
|
* //value is until the next query that starts with '&'
|
|
* assert(sbuf_many1(&buf, notand));
|
|
* valueLen = sbuf_cur(&buf) - value;
|
|
* }
|
|
* //expect '&' or end
|
|
* sbuf_char(&buf, '&');
|
|
* printf("parsed query: %.*s = %.*s\n", nameLen, name, valueLen, value);
|
|
* }
|
|
*
|
|
*/
|
|
|
|
//! init
|
|
static __inline void sbuf_parser_init(struct sbuf* buf, const char *data, int dataLen) {
|
|
sbuf_init(buf, 0, (void*)data, dataLen);
|
|
}
|
|
|
|
//! current postiion
|
|
static __inline char *sbuf_cur(struct sbuf* buf) {
|
|
return (char*)sbuf_head(buf);
|
|
}
|
|
|
|
//! look at the next character if the buffer is still valid
|
|
static __inline int sbuf_peek(struct sbuf* buf, char* c) {
|
|
if(!sbuf_valid(buf)) {
|
|
return 0;
|
|
}
|
|
*c = *sbuf_cur(buf);
|
|
return 1;
|
|
}
|
|
|
|
//! returns true if the buffer is ended
|
|
static __inline int sbuf_end(struct sbuf* buf) {
|
|
return sbuf_left(buf) == 0;
|
|
}
|
|
|
|
//! consume 1 char if its in string chars
|
|
static __inline int sbuf_chars(struct sbuf *buf, const char *chars) {
|
|
int i = 0;
|
|
char c;
|
|
if(!sbuf_peek(buf, &c)) {
|
|
return 0;
|
|
}
|
|
for(i = 0; chars[i] != 0; ++i) {
|
|
if(c == chars[i]) {
|
|
sbuf_advance(buf, 1);
|
|
return 1;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
//! consume 1 char only if its not in string chars
|
|
static __inline int sbuf_notchars(struct sbuf *buf, const char *chars) {
|
|
int i = 0;
|
|
char c;
|
|
if(!sbuf_peek(buf, &c)) {
|
|
return 0;
|
|
}
|
|
for(i = 0; chars[i] != 0; ++i) {
|
|
if(c == chars[i]) {
|
|
return 0;
|
|
}
|
|
}
|
|
sbuf_advance(buf, 1);
|
|
return 1;
|
|
}
|
|
|
|
//! consume only char t
|
|
static __inline int sbuf_char(struct sbuf *buf, const char t) {
|
|
char str[2] = {t, 0};
|
|
return sbuf_chars(buf, str);
|
|
}
|
|
|
|
//! consume any char except for t
|
|
static __inline int sbuf_notchar(struct sbuf *buf, const char t) {
|
|
char str[2] = {t, 0};
|
|
return sbuf_notchars(buf, str);
|
|
}
|
|
|
|
/**
|
|
* consume any char
|
|
*/
|
|
static __inline int sbuf_any(struct sbuf* buf) {
|
|
return sbuf_notchars(buf, "");
|
|
}
|
|
|
|
|
|
/**
|
|
* range is pairs of characters
|
|
*
|
|
* pairs are inclusive, start must be less then or equal then the end
|
|
*
|
|
* for example: AZaz09--..
|
|
* matches uppercase and lowercase letters, numbers, dashes and dots
|
|
*
|
|
*/
|
|
static __inline int sbuf_range(struct sbuf *buf, const char *chars) {
|
|
int i, j;
|
|
char c;
|
|
if(!sbuf_peek(buf, &c)) {
|
|
return 0;
|
|
}
|
|
for(i = 0, j = 1; chars[i] != 0 && chars[j] != 0; i+=2,j+=2) {
|
|
if(c >= chars[i] && c <= chars[j]) {
|
|
sbuf_advance(buf, 1);
|
|
return 1;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
|
|
/**
|
|
* greedly consume and match the entire string
|
|
* empty string always succeeds without consuming any data
|
|
*/
|
|
static __inline int sbuf_string(struct sbuf *buf, const char *str) {
|
|
int i = 0;
|
|
for(i = 0; str[i] != 0; ++i) {
|
|
if(!sbuf_char(buf, str[i])) {
|
|
return 0;
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
/**
|
|
* consumes until fails
|
|
*/
|
|
static __inline int sbuf_many(struct sbuf *buf,
|
|
int(*consume)(struct sbuf *buf))
|
|
{
|
|
if(!sbuf_valid(buf)) {
|
|
return 0;
|
|
}
|
|
while(consume(buf)) {;}
|
|
return 1;
|
|
}
|
|
/**
|
|
* consumes until fails, must consume at least 1
|
|
*/
|
|
static __inline int sbuf_many1(struct sbuf *buf,
|
|
int(*consume)(struct sbuf *buf))
|
|
{
|
|
if(!consume(buf)) {
|
|
return 0;
|
|
}
|
|
sbuf_many(buf, consume);
|
|
return 1;
|
|
}
|
|
/**
|
|
* runs 'consume' until 'stop' succeeds
|
|
* 'stop' must fail in such a way that it doesn't consume any data
|
|
*/
|
|
static __inline int sbuf_until(struct sbuf *buf,
|
|
int(*consume)(struct sbuf *buf),
|
|
int(*stop)(struct sbuf *buf))
|
|
{
|
|
while(!stop(buf)) {
|
|
if(!consume(buf)) {
|
|
return 0;
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
/**
|
|
* allows for backtracking,
|
|
* @param parser, runs parser and only consume if it succeeds
|
|
*/
|
|
static __inline int sbuf_try(struct sbuf *buf, int(*parser)(struct sbuf *buf))
|
|
{
|
|
struct sbuf tryp;
|
|
sbuf_parser_init(&tryp, sbuf_cur(buf), sbuf_left(buf));
|
|
if(parser(&tryp)) {
|
|
sbuf_advance(buf, sbuf_cur(&tryp) - sbuf_cur(buf));
|
|
return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
#endif // SBUF_PARSER_H
|