From ba3e89199b78c33fc5b0dce6a4456096c71c2e19 Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Sat, 28 Dec 2013 21:25:20 +0000 Subject: [PATCH 1/1] Initial commit --- CMakeLists.txt | 47 +++++++ lexer.h | 336 +++++++++++++++++++++++++++++++++++++++++++++++++ lexer.l | 172 +++++++++++++++++++++++++ main.c | 215 +++++++++++++++++++++++++++++++ matcher.c | 267 +++++++++++++++++++++++++++++++++++++++ matcher.h | 34 +++++ parser.h | 116 +++++++++++++++++ parser.y | 231 ++++++++++++++++++++++++++++++++++ 8 files changed, 1418 insertions(+) create mode 100644 CMakeLists.txt create mode 100644 lexer.h create mode 100644 lexer.l create mode 100644 main.c create mode 100644 matcher.c create mode 100644 matcher.h create mode 100644 parser.h create mode 100644 parser.y diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..9b2fd50 --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1,47 @@ +cmake_minimum_required(VERSION 2.6) + +PROJECT(jsonpath C) +ADD_DEFINITIONS(-Os -Wall -Werror --std=gnu99 -Wmissing-declarations) + +SET(CMAKE_SHARED_LIBRARY_LINK_C_FLAGS "") + +IF(APPLE) + INCLUDE_DIRECTORIES(/opt/local/include) + LINK_DIRECTORIES(/opt/local/lib) +ENDIF() + +find_library(json NAMES json-c json) + +IF(DEBUG) + ADD_DEFINITIONS(-DDEBUG -g3) +ENDIF() + +INCLUDE(FindPkgConfig) +PKG_CHECK_MODULES(JSONC json-c json) +IF(JSONC_FOUND) + ADD_DEFINITIONS(-DJSONC) + INCLUDE_DIRECTORIES(${JSONC_INCLUDE_DIRS}) +ENDIF() + +FIND_PACKAGE(BISON REQUIRED) +IF(BISON_FOUND) + ADD_CUSTOM_COMMAND( + OUTPUT parser.c + COMMAND ${BISON_EXECUTABLE} parser.y + COMMENT "Generating parser.c" + ) +ENDIF() + +FIND_PACKAGE(FLEX REQUIRED) +IF(FLEX_FOUND) + ADD_CUSTOM_COMMAND( + OUTPUT lexer.c + COMMAND ${FLEX_EXECUTABLE} lexer.l + COMMENT "Generating lexer.c" + ) +ENDIF() + +ADD_EXECUTABLE(jsonpath main.c lexer.c parser.c matcher.c) +TARGET_LINK_LIBRARIES(jsonpath ubox ${json}) + +INSTALL(TARGETS jsonpath RUNTIME DESTINATION bin) diff --git a/lexer.h b/lexer.h new file mode 100644 index 0000000..c8b5bed --- /dev/null +++ b/lexer.h @@ -0,0 +1,336 @@ +#ifndef yyHEADER_H +#define yyHEADER_H 1 +#define yyIN_HEADER 1 + +#line 6 "lexer.h" + +#line 8 "lexer.h" + +#define YY_INT_ALIGNED short int + +/* A lexical scanner generated by flex */ + +#define FLEX_SCANNER +#define YY_FLEX_MAJOR_VERSION 2 +#define YY_FLEX_MINOR_VERSION 5 +#define YY_FLEX_SUBMINOR_VERSION 35 +#if YY_FLEX_SUBMINOR_VERSION > 0 +#define FLEX_BETA +#endif + +/* First, we deal with platform-specific or compiler-specific issues. */ + +/* begin standard C headers. */ +#include +#include +#include +#include + +/* end standard C headers. */ + +/* flex integer type definitions */ + +#ifndef FLEXINT_H +#define FLEXINT_H + +/* C99 systems have . Non-C99 systems may or may not. */ + +#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L + +/* C99 says to define __STDC_LIMIT_MACROS before including stdint.h, + * if you want the limit (max/min) macros for int types. + */ +#ifndef __STDC_LIMIT_MACROS +#define __STDC_LIMIT_MACROS 1 +#endif + +#include +typedef int8_t flex_int8_t; +typedef uint8_t flex_uint8_t; +typedef int16_t flex_int16_t; +typedef uint16_t flex_uint16_t; +typedef int32_t flex_int32_t; +typedef uint32_t flex_uint32_t; +#else +typedef signed char flex_int8_t; +typedef short int flex_int16_t; +typedef int flex_int32_t; +typedef unsigned char flex_uint8_t; +typedef unsigned short int flex_uint16_t; +typedef unsigned int flex_uint32_t; + +/* Limits of integral types. */ +#ifndef INT8_MIN +#define INT8_MIN (-128) +#endif +#ifndef INT16_MIN +#define INT16_MIN (-32767-1) +#endif +#ifndef INT32_MIN +#define INT32_MIN (-2147483647-1) +#endif +#ifndef INT8_MAX +#define INT8_MAX (127) +#endif +#ifndef INT16_MAX +#define INT16_MAX (32767) +#endif +#ifndef INT32_MAX +#define INT32_MAX (2147483647) +#endif +#ifndef UINT8_MAX +#define UINT8_MAX (255U) +#endif +#ifndef UINT16_MAX +#define UINT16_MAX (65535U) +#endif +#ifndef UINT32_MAX +#define UINT32_MAX (4294967295U) +#endif + +#endif /* ! C99 */ + +#endif /* ! FLEXINT_H */ + +#ifdef __cplusplus + +/* The "const" storage-class-modifier is valid. */ +#define YY_USE_CONST + +#else /* ! __cplusplus */ + +/* C99 requires __STDC__ to be defined as 1. */ +#if defined (__STDC__) + +#define YY_USE_CONST + +#endif /* defined (__STDC__) */ +#endif /* ! __cplusplus */ + +#ifdef YY_USE_CONST +#define yyconst const +#else +#define yyconst +#endif + +/* Size of default input buffer. */ +#ifndef YY_BUF_SIZE +#ifdef __ia64__ +/* On IA-64, the buffer size is 16k, not 8k. + * Moreover, YY_BUF_SIZE is 2*YY_READ_BUF_SIZE in the general case. + * Ditto for the __ia64__ case accordingly. + */ +#define YY_BUF_SIZE 32768 +#else +#define YY_BUF_SIZE 16384 +#endif /* __ia64__ */ +#endif + +#ifndef YY_TYPEDEF_YY_BUFFER_STATE +#define YY_TYPEDEF_YY_BUFFER_STATE +typedef struct yy_buffer_state *YY_BUFFER_STATE; +#endif + +extern int yyleng; + +extern FILE *yyin, *yyout; + +#ifndef YY_TYPEDEF_YY_SIZE_T +#define YY_TYPEDEF_YY_SIZE_T +typedef size_t yy_size_t; +#endif + +#ifndef YY_STRUCT_YY_BUFFER_STATE +#define YY_STRUCT_YY_BUFFER_STATE +struct yy_buffer_state + { + FILE *yy_input_file; + + char *yy_ch_buf; /* input buffer */ + char *yy_buf_pos; /* current position in input buffer */ + + /* Size of input buffer in bytes, not including room for EOB + * characters. + */ + yy_size_t yy_buf_size; + + /* Number of characters read into yy_ch_buf, not including EOB + * characters. + */ + int yy_n_chars; + + /* Whether we "own" the buffer - i.e., we know we created it, + * and can realloc() it to grow it, and should free() it to + * delete it. + */ + int yy_is_our_buffer; + + /* Whether this is an "interactive" input source; if so, and + * if we're using stdio for input, then we want to use getc() + * instead of fread(), to make sure we stop fetching input after + * each newline. + */ + int yy_is_interactive; + + /* Whether we're considered to be at the beginning of a line. + * If so, '^' rules will be active on the next match, otherwise + * not. + */ + int yy_at_bol; + + int yy_bs_lineno; /**< The line count. */ + int yy_bs_column; /**< The column count. */ + + /* Whether to try to fill the input buffer when we reach the + * end of it. + */ + int yy_fill_buffer; + + int yy_buffer_status; + + }; +#endif /* !YY_STRUCT_YY_BUFFER_STATE */ + +void yyrestart (FILE *input_file ); +void yy_switch_to_buffer (YY_BUFFER_STATE new_buffer ); +YY_BUFFER_STATE yy_create_buffer (FILE *file,int size ); +void yy_delete_buffer (YY_BUFFER_STATE b ); +void yy_flush_buffer (YY_BUFFER_STATE b ); +void yypush_buffer_state (YY_BUFFER_STATE new_buffer ); +void yypop_buffer_state (void ); + +YY_BUFFER_STATE yy_scan_buffer (char *base,yy_size_t size ); +YY_BUFFER_STATE yy_scan_string (yyconst char *yy_str ); +YY_BUFFER_STATE yy_scan_bytes (yyconst char *bytes,int len ); + +void *yyalloc (yy_size_t ); +void *yyrealloc (void *,yy_size_t ); +void yyfree (void * ); + +/* Begin user sect3 */ + +#define yywrap(n) 1 +#define YY_SKIP_YYWRAP + +extern int yylineno; + +extern char *yytext; +#define yytext_ptr yytext + +#ifdef YY_HEADER_EXPORT_START_CONDITIONS +#define INITIAL 0 +#define STRING 1 + +#endif + +#ifndef YY_NO_UNISTD_H +/* Special case for "unistd.h", since it is non-ANSI. We include it way + * down here because we want the user's section 1 to have been scanned first. + * The user has a chance to override it with an option. + */ +#include +#endif + +#ifndef YY_EXTRA_TYPE +#define YY_EXTRA_TYPE void * +#endif + +/* Accessor methods to globals. + These are made visible to non-reentrant scanners for convenience. */ + +int yylex_destroy (void ); + +int yyget_debug (void ); + +void yyset_debug (int debug_flag ); + +YY_EXTRA_TYPE yyget_extra (void ); + +void yyset_extra (YY_EXTRA_TYPE user_defined ); + +FILE *yyget_in (void ); + +void yyset_in (FILE * in_str ); + +FILE *yyget_out (void ); + +void yyset_out (FILE * out_str ); + +int yyget_leng (void ); + +char *yyget_text (void ); + +int yyget_lineno (void ); + +void yyset_lineno (int line_number ); + +/* Macros after this point can all be overridden by user definitions in + * section 1. + */ + +#ifndef YY_SKIP_YYWRAP +#ifdef __cplusplus +extern "C" int yywrap (void ); +#else +extern int yywrap (void ); +#endif +#endif + +#ifndef yytext_ptr +static void yy_flex_strncpy (char *,yyconst char *,int ); +#endif + +#ifdef YY_NEED_STRLEN +static int yy_flex_strlen (yyconst char * ); +#endif + +#ifndef YY_NO_INPUT + +#endif + +/* Amount of stuff to slurp up with each read. */ +#ifndef YY_READ_BUF_SIZE +#ifdef __ia64__ +/* On IA-64, the buffer size is 16k, not 8k */ +#define YY_READ_BUF_SIZE 16384 +#else +#define YY_READ_BUF_SIZE 8192 +#endif /* __ia64__ */ +#endif + +/* Number of entries by which start-condition stack grows. */ +#ifndef YY_START_STACK_INCR +#define YY_START_STACK_INCR 25 +#endif + +/* Default declaration of generated scanner - a define so the user can + * easily add parameters. + */ +#ifndef YY_DECL +#define YY_DECL_IS_OURS 1 + +extern int yylex (void); + +#define YY_DECL int yylex (void) +#endif /* !YY_DECL */ + +/* yy_get_previous_state - get the state just before the EOB char was reached */ + +#undef YY_NEW_FILE +#undef YY_FLUSH_BUFFER +#undef yy_set_bol +#undef yy_new_buffer +#undef yy_set_interactive +#undef YY_DO_BEFORE_ACTION + +#ifdef YY_DECL_IS_OURS +#undef YY_DECL_IS_OURS +#undef YY_DECL +#endif + +#line 172 "lexer.l" + + +#line 335 "lexer.h" +#undef yyIN_HEADER +#endif /* yyHEADER_H */ diff --git a/lexer.l b/lexer.l new file mode 100644 index 0000000..e3467bc --- /dev/null +++ b/lexer.l @@ -0,0 +1,172 @@ +%{ +/* + * Copyright (C) 2013 Jo-Philipp Wich + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#include "parser.h" + +static char *str_ptr; +static char str_buf[128]; + +static void +str_put(char c) +{ + if ((str_ptr - str_buf + 1) < sizeof(str_buf)) + *str_ptr++ = c; +} + +static void +str_decode(const char *input, int base) +{ + int code; + char *end; + + code = strtoul(input, &end, base); + + if (end == input || *end) + return; + + if (code > 0 && code <= 0x7F) + { + str_put(code); + } + else if (code > 0 && code <= 0x7FF) + { + str_put(((code >> 6) & 0x1F) | 0xC0); + str_put(( code & 0x3F) | 0x80); + } + else if (code > 0 && code <= 0xFFFF) + { + str_put(((code >> 12) & 0x0F) | 0xE0); + str_put(((code >> 6) & 0x3F) | 0x80); + str_put(( code & 0x3F) | 0x80); + } + else if (code > 0 && code <= 0x10FFFF) + { + str_put(((code >> 18) & 0x07) | 0xF0); + str_put(((code >> 12) & 0x3F) | 0x80); + str_put(((code >> 6) & 0x3F) | 0x80); + str_put(( code & 0x3F) | 0x80); + } +} + +%} + +%option outfile="lexer.c" header-file="lexer.h" +%option noyywrap nounput noinput + +DOT "." +LABEL [a-zA-Z_][a-zA-Z0-9_]* + +BROPEN "[" +BRCLOSE "]" +POPEN "(" +PCLOSE ")" + +ROOT "$" +THIS "@" + +LT "<" +LE "<=" +GT ">" +GE ">=" +NE "!=" +EQ "=" +NOT "!" +AND "&&" +OR "||" + +NUMBER -?[0-9]+ +WILDCARD "*" +BOOL (true|false) + +WS [ \t\n]* + +%x STRING + +%% + +\" { + str_ptr = str_buf; + memset(str_buf, 0, sizeof(str_buf)); + BEGIN(STRING); +} + +{ + \" { + BEGIN(INITIAL); + yylval.op = jp_alloc_op(T_STRING, 0, str_buf); + return T_STRING; + } + + \\([0-3][0-7]{1,2}|[0-7]{0,2}) { str_decode(yytext + 1, 8); } + \\x[A-Fa-f0-9]{2} { str_decode(yytext + 2, 16); } + \\u[A-Fa-f0-9]{4} { str_decode(yytext + 2, 16); } + \\a { str_put('\a'); } + \\b { str_put('\b'); } + \\e { str_put('\e'); } + \\f { str_put('\f'); } + \\n { str_put('\n'); } + \\r { str_put('\r'); } + \\t { str_put('\t'); } + \\v { str_put('\v'); } + \\. { str_put(*yytext); } + [^\\"]+ { while (*yytext) str_put(*yytext++); } +} + +{BOOL} { + yylval.op = jp_alloc_op(T_BOOL, (*yytext == 't'), NULL); + return T_BOOL; +} + +{NUMBER} { + yylval.op = jp_alloc_op(T_NUMBER, atoi(yytext), NULL); + return T_NUMBER; +} + +{LABEL} { + yylval.op = jp_alloc_op(T_LABEL, 0, yytext); + return T_LABEL; +} + +{WILDCARD} { + yylval.op = jp_alloc_op(T_WILDCARD, 0, NULL); + return T_WILDCARD; +} + +{DOT} { return T_DOT; } +{BROPEN} { return T_BROPEN; } +{BRCLOSE} { return T_BRCLOSE; } +{POPEN} { return T_POPEN; } +{PCLOSE} { return T_PCLOSE; } + +{ROOT} { return T_ROOT; } +{THIS} { return T_THIS; } + +{LT} { return T_LT; } +{LE} { return T_LE; } +{GT} { return T_GT; } +{GE} { return T_GE; } +{EQ} { return T_EQ; } +{NE} { return T_NE; } +{NOT} { return T_NOT; } +{AND} { return T_AND; } +{OR} { return T_OR; } + +{WS} { } + +%% diff --git a/main.c b/main.c new file mode 100644 index 0000000..7a19091 --- /dev/null +++ b/main.c @@ -0,0 +1,215 @@ +/* + * Copyright (C) 2013 Jo-Philipp Wich + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include +#include + +#ifdef JSONC + #include +#else + #include +#endif + +#include "lexer.h" +#include "parser.h" +#include "matcher.h" + +static struct json_object * +parse_json(FILE *fd) +{ + int len; + char buf[256]; + struct json_object *obj = NULL; + struct json_tokener *tok = json_tokener_new(); + enum json_tokener_error err = json_tokener_continue; + + if (!tok) + return NULL; + + while ((len = fread(buf, 1, sizeof(buf), fd)) > 0) + { + obj = json_tokener_parse_ex(tok, buf, len); + err = json_tokener_get_error(tok); + + if (!err || err != json_tokener_continue) + break; + } + + json_tokener_free(tok); + + return err ? NULL : obj; +} + +static void +print_string(const char *s) +{ + const char *p; + + printf("'"); + + for (p = s; *p; p++) + { + if (*p == '\'') + printf("'\"'\"'"); + else + printf("%c", *p); + } + + printf("'"); +} + +static void +export_json(struct json_object *jsobj, char *expr) +{ + bool first; + struct jp_opcode *tree; + struct json_object *res; + const char *error, *prefix; + + tree = jp_parse(expr, &error); + + if (error) + { + fprintf(stderr, "In expression '%s': %s\n", expr, error); + return; + } + + res = jp_match(tree, jsobj); + + if (tree->type == T_LABEL) + { + prefix = tree->str; + + switch (json_object_get_type(res)) + { + case json_type_object: + printf("export %s_TYPE=object; ", prefix); + + first = true; + printf("export %s_KEYS=", prefix); + json_object_object_foreach(res, key, val) + { + if (!val) + continue; + + if (!first) + printf("\\ "); + + print_string(key); + first = false; + } + printf("; "); + + //printf("export %s=", prefix); + //print_string(json_object_to_json_string(res)); + //printf("; "); + + break; + + case json_type_array: + printf("export %s_TYPE=array; ", prefix); + printf("export %s_LENGTH=%d; ", + prefix, json_object_array_length(res)); + + //printf("export %s=", prefix); + //print_string(json_object_to_json_string(res)); + //printf("; "); + break; + + case json_type_boolean: + printf("export %s_TYPE=bool; ", prefix); + printf("export %s=%d; ", prefix, json_object_get_boolean(res)); + break; + + case json_type_int: + printf("export %s_TYPE=int; ", prefix); + printf("export %s=%d; ", prefix, json_object_get_int(res)); + break; + + case json_type_double: + printf("export %s_TYPE=double; ", prefix); + printf("export %s=%f; ", prefix, json_object_get_double(res)); + break; + + case json_type_string: + printf("export %s_TYPE=string; ", prefix); + printf("export %s=", prefix); + print_string(json_object_get_string(res)); + printf("; "); + break; + + case json_type_null: + printf("unset %s %s_TYPE %s_LENGTH %s_KEYS; ", + prefix, prefix, prefix, prefix); + break; + } + } + else + { + printf("%s\n", json_object_to_json_string(res)); + } + + jp_free(); +} + +int main(int argc, char **argv) +{ + int opt; + FILE *input = stdin; + struct json_object *jsobj = NULL; + + while ((opt = getopt(argc, argv, "i:e:")) != -1) + { + switch (opt) + { + case 'i': + input = fopen(optarg, "r"); + + if (!input) + { + fprintf(stderr, "Failed to open %s: %s\n", + optarg, strerror(errno)); + + exit(1); + } + + break; + + case 'e': + if (!jsobj) + { + jsobj = parse_json(input); + + if (!jsobj) + { + fprintf(stderr, "Failed to parse json data\n"); + exit(2); + } + } + + export_json(jsobj, optarg); + break; + } + } + + if (jsobj) + json_object_put(jsobj); + + fclose(input); + + return 0; +} diff --git a/matcher.c b/matcher.c new file mode 100644 index 0000000..1a4a57d --- /dev/null +++ b/matcher.c @@ -0,0 +1,267 @@ +/* + * Copyright (C) 2013 Jo-Philipp Wich + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "matcher.h" + +static struct json_object * +jp_match_next(struct jp_opcode *ptr, + struct json_object *root, struct json_object *cur); + +static bool +jp_json_to_op(struct json_object *obj, struct jp_opcode *op) +{ + switch (json_object_get_type(obj)) + { + case json_type_boolean: + op->type = T_BOOL; + op->num = json_object_get_boolean(obj); + return true; + + case json_type_int: + op->type = T_NUMBER; + op->num = json_object_get_int(obj); + return true; + + case json_type_string: + op->type = T_STRING; + op->str = (char *)json_object_get_string(obj); + return true; + + default: + return false; + } +} + +static bool +jp_resolve(struct json_object *root, struct json_object *cur, + struct jp_opcode *op, struct jp_opcode *res) +{ + struct json_object *val; + + switch (op->type) + { + case T_THIS: + val = jp_match(op, cur); + + if (val) + return jp_json_to_op(val, res); + + return false; + + case T_ROOT: + val = jp_match(op, root); + + if (val) + return jp_json_to_op(val, res); + + return false; + + default: + *res = *op; + return true; + } +} + +static bool +jp_cmp(struct jp_opcode *op, struct json_object *root, struct json_object *cur) +{ + int delta; + struct jp_opcode left, right; + + if (!jp_resolve(root, cur, op->down, &left) || + !jp_resolve(root, cur, op->down->sibling, &right)) + return false; + + if (left.type != right.type) + return false; + + switch (left.type) + { + case T_BOOL: + case T_NUMBER: + delta = left.num - right.num; + break; + + case T_STRING: + delta = strcmp(left.str, right.str); + break; + + default: + return false; + } + + switch (op->type) + { + case T_EQ: + return (delta == 0); + + case T_LT: + return (delta < 0); + + case T_LE: + return (delta <= 0); + + case T_GT: + return (delta > 0); + + case T_GE: + return (delta >= 0); + + case T_NE: + return (delta != 0); + + default: + return false; + } +} + +static bool +jp_expr(struct jp_opcode *op, struct json_object *root, struct json_object *cur) +{ + struct jp_opcode *sop; + + switch (op->type) + { + case T_WILDCARD: + return true; + + case T_EQ: + case T_NE: + case T_LT: + case T_LE: + case T_GT: + case T_GE: + return jp_cmp(op, root, cur); + + case T_ROOT: + return !!jp_match(op, root); + + case T_THIS: + return !!jp_match(op, cur); + + case T_NOT: + return !jp_expr(op->down, root, cur); + + case T_AND: + for (sop = op->down; sop; sop = sop->sibling) + if (!jp_expr(sop, root, cur)) + return false; + return true; + + case T_OR: + for (sop = op->down; sop; sop = sop->sibling) + if (jp_expr(sop, root, cur)) + return true; + return false; + + default: + return false; + } +} + +static struct json_object * +jp_match_expr(struct jp_opcode *ptr, + struct json_object *root, struct json_object *cur) +{ + int idx, len; + struct json_object *tmp, *res = NULL; + + switch (json_object_get_type(cur)) + { + case json_type_object: + ; /* a label can only be part of a statement and a declaration is not a statement */ + json_object_object_foreach(cur, key, val) + { + if (!key) + continue; + + if (jp_expr(ptr, root, val)) + { + tmp = jp_match_next(ptr->sibling, root, val); + + if (tmp && !res) + res = tmp; + } + } + + break; + + case json_type_array: + len = json_object_array_length(cur); + + for (idx = 0; idx < len; idx++) + { + tmp = json_object_array_get_idx(cur, idx); + + if (jp_expr(ptr, root, tmp)) + { + tmp = jp_match_next(ptr->sibling, root, tmp); + + if (tmp && !res) + res = tmp; + } + } + + break; + + default: + break; + } + + return res; +} + +static struct json_object * +jp_match_next(struct jp_opcode *ptr, + struct json_object *root, struct json_object *cur) +{ + struct json_object *next; + + if (!ptr) + return cur; + + switch (ptr->type) + { + case T_STRING: + case T_LABEL: + if (json_object_object_get_ex(cur, ptr->str, &next)) + return jp_match_next(ptr->sibling, root, next); + + break; + + case T_NUMBER: + next = json_object_array_get_idx(cur, ptr->num); + + if (next) + return jp_match_next(ptr->sibling, root, next); + + break; + + default: + return jp_match_expr(ptr, root, cur); + } + + return NULL; +} + +struct json_object * +jp_match(struct jp_opcode *path, json_object *jsobj) +{ + if (path->type == T_LABEL) + path = path->down; + + return jp_match_next(path->down, jsobj, jsobj); +} diff --git a/matcher.h b/matcher.h new file mode 100644 index 0000000..4187241 --- /dev/null +++ b/matcher.h @@ -0,0 +1,34 @@ +/* + * Copyright (C) 2013 Jo-Philipp Wich + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef __MATCHER_H_ +#define __MATCHER_H_ + +#include +#include + +#ifdef JSONC + #include +#else + #include +#endif + +#include "parser.h" + +struct json_object * +jp_match(struct jp_opcode *path, struct json_object *jsobj); + +#endif diff --git a/parser.h b/parser.h new file mode 100644 index 0000000..a50bd50 --- /dev/null +++ b/parser.h @@ -0,0 +1,116 @@ +/* A Bison parser, made by GNU Bison 2.5. */ + +/* Bison interface for Yacc-like parsers in C + + Copyright (C) 1984, 1989-1990, 2000-2011 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +/* As a special exception, you may create a larger work that contains + part or all of the Bison parser skeleton and distribute that work + under terms of your choice, so long as that work isn't itself a + parser generator using the skeleton or a modified version thereof + as a parser skeleton. Alternatively, if you modify or redistribute + the parser skeleton itself, you may (at your option) remove this + special exception, which will cause the skeleton and the resulting + Bison output files to be licensed under the GNU General Public + License without this special exception. + + This special exception was added by the Free Software Foundation in + version 2.2 of Bison. */ + + +/* Tokens. */ +#ifndef YYTOKENTYPE +# define YYTOKENTYPE + /* Put the tokens into the symbol table, so that GDB and other debuggers + know about them. */ + enum yytokentype { + T_ROOT = 258, + T_THIS = 259, + T_DOT = 260, + T_BROPEN = 261, + T_BRCLOSE = 262, + T_OR = 263, + T_AND = 264, + T_LT = 265, + T_LE = 266, + T_GT = 267, + T_GE = 268, + T_EQ = 269, + T_NE = 270, + T_POPEN = 271, + T_PCLOSE = 272, + T_NOT = 273, + T_BOOL = 274, + T_NUMBER = 275, + T_STRING = 276, + T_LABEL = 277, + T_WILDCARD = 278 + }; +#endif + + + +#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED +typedef union YYSTYPE +{ + +/* Line 2068 of yacc.c */ +#line 60 "parser.y" + + struct jp_opcode *op; + + + +/* Line 2068 of yacc.c */ +#line 79 "parser.h" +} YYSTYPE; +# define YYSTYPE_IS_TRIVIAL 1 +# define yystype YYSTYPE /* obsolescent; will be withdrawn */ +# define YYSTYPE_IS_DECLARED 1 +#endif + +extern YYSTYPE yylval; + + +/* "%code provides" blocks. */ + +/* Line 2068 of yacc.c */ +#line 38 "parser.y" + + +#ifndef JP_OPCODE +# define JP_OPCODE + struct jp_opcode { + int type; + struct jp_opcode *next; + struct jp_opcode *down; + struct jp_opcode *sibling; + char *str; + int num; + }; +#endif + +struct jp_opcode *_jp_alloc_op(int type, int num, char *str, ...); +#define jp_alloc_op(type, num, str, ...) _jp_alloc_op(type, num, str, ##__VA_ARGS__, NULL) + +struct jp_opcode *jp_parse(const char *expr, const char **error); +void jp_free(void); + + + + +/* Line 2068 of yacc.c */ +#line 117 "parser.h" diff --git a/parser.y b/parser.y new file mode 100644 index 0000000..40b25f5 --- /dev/null +++ b/parser.y @@ -0,0 +1,231 @@ +%{ +/* + * Copyright (C) 2013 Jo-Philipp Wich + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include + +#include "lexer.h" +#include "parser.h" + +static struct jp_opcode *op_pool = NULL; +static struct jp_opcode *append_op(struct jp_opcode *a, struct jp_opcode *b); + +int yyparse(struct jp_opcode **tree, const char **error); +void yyerror(struct jp_opcode **expr, const char **error, const char *msg); + +%} + +%output "parser.c" +%defines "parser.h" + +%parse-param { struct jp_opcode **expr } +%parse-param { const char **error } + +%code provides { + +#ifndef JP_OPCODE +# define JP_OPCODE + struct jp_opcode { + int type; + struct jp_opcode *next; + struct jp_opcode *down; + struct jp_opcode *sibling; + char *str; + int num; + }; +#endif + +struct jp_opcode *_jp_alloc_op(int type, int num, char *str, ...); +#define jp_alloc_op(type, num, str, ...) _jp_alloc_op(type, num, str, ##__VA_ARGS__, NULL) + +struct jp_opcode *jp_parse(const char *expr, const char **error); +void jp_free(void); + +} + +%union { + struct jp_opcode *op; +} + + +%token T_ROOT T_THIS T_DOT T_BROPEN T_BRCLOSE +%token T_OR T_AND T_LT T_LE T_GT T_GE T_EQ T_NE T_POPEN T_PCLOSE T_NOT + +%token T_BOOL T_NUMBER T_STRING T_LABEL T_WILDCARD + +%type expr path segments segment or_exps or_exp and_exps and_exp cmp_exp unary_exp + +%error-verbose + +%% + +input + : expr { *expr = $1; } + ; + +expr + : T_LABEL T_EQ path { $1->down = $3; $$ = $1; } + | path { $$ = $1; } + ; + +path + : T_ROOT segments { $$ = jp_alloc_op(T_ROOT, 0, NULL, $2); } + | T_THIS segments { $$ = jp_alloc_op(T_THIS, 0, NULL, $2); } + ; + +segments + : segments segment { $$ = append_op($1, $2); } + | segment { $$ = $1; } + ; + +segment + : T_DOT T_LABEL { $$ = $2; } + | T_DOT T_WILDCARD { $$ = $2; } + | T_BROPEN or_exps T_BRCLOSE { $$ = $2; } + ; + +or_exps + : or_exp { $$ = $1->sibling ? jp_alloc_op(T_OR, 0, NULL, $1) : $1; } + ; + +or_exp + : or_exp T_OR and_exps { $$ = append_op($1, $3); } + | and_exps { $$ = $1; } + ; + +and_exps + : and_exp { $$ = $1->sibling ? jp_alloc_op(T_AND, 0, NULL, $1) : $1; } + ; + +and_exp + : and_exp T_AND cmp_exp { $$ = append_op($1, $3); } + | cmp_exp { $$ = $1; } + ; + +cmp_exp + : unary_exp T_LT unary_exp { $$ = jp_alloc_op(T_LT, 0, NULL, $1, $3); } + | unary_exp T_LE unary_exp { $$ = jp_alloc_op(T_LE, 0, NULL, $1, $3); } + | unary_exp T_GT unary_exp { $$ = jp_alloc_op(T_GT, 0, NULL, $1, $3); } + | unary_exp T_GE unary_exp { $$ = jp_alloc_op(T_GE, 0, NULL, $1, $3); } + | unary_exp T_EQ unary_exp { $$ = jp_alloc_op(T_EQ, 0, NULL, $1, $3); } + | unary_exp T_NE unary_exp { $$ = jp_alloc_op(T_NE, 0, NULL, $1, $3); } + | unary_exp { $$ = $1; } + ; + +unary_exp + : T_BOOL { $$ = $1; } + | T_NUMBER { $$ = $1; } + | T_STRING { $$ = $1; } + | T_WILDCARD { $$ = $1; } + | T_POPEN or_exps T_PCLOSE { $$ = $2; } + | T_NOT unary_exp { $$ = jp_alloc_op(T_NOT, 0, NULL, $2); } + | path { $$ = $1; } + ; + +%% + +void +yyerror(struct jp_opcode **expr, const char **error, const char *msg) +{ + *error = msg; + jp_free(); +} + +static struct jp_opcode * +append_op(struct jp_opcode *a, struct jp_opcode *b) +{ + struct jp_opcode *tail = a; + + while (tail->sibling) + tail = tail->sibling; + + tail->sibling = b; + + return a; +} + +struct jp_opcode * +_jp_alloc_op(int type, int num, char *str, ...) +{ + va_list ap; + char *ptr; + struct jp_opcode *newop, *child; + + newop = calloc_a(sizeof(*newop), + str ? &ptr : NULL, str ? strlen(str) + 1 : 0); + + if (!newop) + { + fprintf(stderr, "Out of memory\n"); + exit(1); + } + + newop->type = type; + newop->num = num; + + if (str) + newop->str = strcpy(ptr, str); + + va_start(ap, str); + + while ((child = va_arg(ap, void *)) != NULL) + if (!newop->down) + newop->down = child; + else + append_op(newop->down, child); + + va_end(ap); + + newop->next = op_pool; + op_pool = newop; + + return newop; +} + +struct jp_opcode * +jp_parse(const char *expr, const char **error) +{ + void *buf; + struct jp_opcode *tree; + + buf = yy_scan_string(expr); + + if (yyparse(&tree, error)) + tree = NULL; + else + *error = NULL; + + yy_delete_buffer(buf); + yylex_destroy(); + + return tree; +} + +void +jp_free(void) +{ + struct jp_opcode *op, *tmp; + + for (op = op_pool; op;) + { + tmp = op->next; + free(op); + op = tmp; + } + + op_pool = NULL; +} -- 2.25.1