Partial implementation of SQL/JSON path language

SQL 2016 standards among other things contains set of SQL/JSON features for
JSON processing inside of relational database.  The core of SQL/JSON is JSON
path language, allowing access parts of JSON documents and make computations
over them.  This commit implements partial support JSON path language as
separate datatype called "jsonpath".  The implementation is partial because
it's lacking datetime support and suppression of numeric errors.  Missing
features will be added later by separate commits.

Support of SQL/JSON features requires implementation of separate nodes, and it
will be considered in subsequent patches.  This commit includes following
set of plain functions, allowing to execute jsonpath over jsonb values:

 * jsonb_path_exists(jsonb, jsonpath[, jsonb, bool]),
 * jsonb_path_match(jsonb, jsonpath[, jsonb, bool]),
 * jsonb_path_query(jsonb, jsonpath[, jsonb, bool]),
 * jsonb_path_query_array(jsonb, jsonpath[, jsonb, bool]).
 * jsonb_path_query_first(jsonb, jsonpath[, jsonb, bool]).

This commit also implements "jsonb @? jsonpath" and "jsonb @@ jsonpath", which
are wrappers over jsonpath_exists(jsonb, jsonpath) and jsonpath_predicate(jsonb,
jsonpath) correspondingly.  These operators will have an index support
(implemented in subsequent patches).

Catversion bumped, to add new functions and operators.

Code was written by Nikita Glukhov and Teodor Sigaev, revised by me.
Documentation was written by Oleg Bartunov and Liudmila Mantrova.  The work
was inspired by Oleg Bartunov.

Discussion: https://postgr.es/m/fcc6fc6a-b497-f39a-923d-aa34d0c588e8%402ndQuadrant.com
Author: Nikita Glukhov, Teodor Sigaev, Alexander Korotkov, Oleg Bartunov, Liudmila Mantrova
Reviewed-by: Tomas Vondra, Andrew Dunstan, Pavel Stehule, Alexander Korotkov

1 files changed, 245 insertions, 0 deletions

diff --git a/src/include/utils/jsonpath.h b/src/include/utils/jsonpath.h
new file mode 100644
index 00000000000..14f837e00d5
--- /dev/null
+++ b/src/include/utils/jsonpath.h
@@ -0,0 +1,245 @@
+/*-------------------------------------------------------------------------
+ *
+ * jsonpath.h
+ *	Definitions for jsonpath datatype
+ *
+ * Copyright (c) 2019, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	src/include/utils/jsonpath.h
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef JSONPATH_H
+#define JSONPATH_H
+
+#include "fmgr.h"
+#include "utils/jsonb.h"
+#include "nodes/pg_list.h"
+
+typedef struct
+{
+	int32		vl_len_;		/* varlena header (do not touch directly!) */
+	uint32		header;			/* version and flags (see below) */
+	char		data[FLEXIBLE_ARRAY_MEMBER];
+} JsonPath;
+
+#define JSONPATH_VERSION	(0x01)
+#define JSONPATH_LAX		(0x80000000)
+#define JSONPATH_HDRSZ		(offsetof(JsonPath, data))
+
+#define DatumGetJsonPathP(d)			((JsonPath *) DatumGetPointer(PG_DETOAST_DATUM(d)))
+#define DatumGetJsonPathPCopy(d)		((JsonPath *) DatumGetPointer(PG_DETOAST_DATUM_COPY(d)))
+#define PG_GETARG_JSONPATH_P(x)			DatumGetJsonPathP(PG_GETARG_DATUM(x))
+#define PG_GETARG_JSONPATH_P_COPY(x)	DatumGetJsonPathPCopy(PG_GETARG_DATUM(x))
+#define PG_RETURN_JSONPATH_P(p)			PG_RETURN_POINTER(p)
+
+/*
+ * All node's type of jsonpath expression
+ */
+typedef enum JsonPathItemType
+{
+	jpiNull = jbvNull,			/* NULL literal */
+	jpiString = jbvString,		/* string literal */
+	jpiNumeric = jbvNumeric,	/* numeric literal */
+	jpiBool = jbvBool,			/* boolean literal: TRUE or FALSE */
+	jpiAnd,						/* predicate && predicate */
+	jpiOr,						/* predicate || predicate */
+	jpiNot,						/* ! predicate */
+	jpiIsUnknown,				/* (predicate) IS UNKNOWN */
+	jpiEqual,					/* expr == expr */
+	jpiNotEqual,				/* expr != expr */
+	jpiLess,					/* expr < expr */
+	jpiGreater,					/* expr > expr */
+	jpiLessOrEqual,				/* expr <= expr */
+	jpiGreaterOrEqual,			/* expr >= expr */
+	jpiAdd,						/* expr + expr */
+	jpiSub,						/* expr - expr */
+	jpiMul,						/* expr * expr */
+	jpiDiv,						/* expr / expr */
+	jpiMod,						/* expr % expr */
+	jpiPlus,					/* + expr */
+	jpiMinus,					/* - expr */
+	jpiAnyArray,				/* [*] */
+	jpiAnyKey,					/* .* */
+	jpiIndexArray,				/* [subscript, ...] */
+	jpiAny,						/* .** */
+	jpiKey,						/* .key */
+	jpiCurrent,					/* @ */
+	jpiRoot,					/* $ */
+	jpiVariable,				/* $variable */
+	jpiFilter,					/* ? (predicate) */
+	jpiExists,					/* EXISTS (expr) predicate */
+	jpiType,					/* .type() item method */
+	jpiSize,					/* .size() item method */
+	jpiAbs,						/* .abs() item method */
+	jpiFloor,					/* .floor() item method */
+	jpiCeiling,					/* .ceiling() item method */
+	jpiDouble,					/* .double() item method */
+	jpiKeyValue,				/* .keyvalue() item method */
+	jpiSubscript,				/* array subscript: 'expr' or 'expr TO expr' */
+	jpiLast,					/* LAST array subscript */
+	jpiStartsWith,				/* STARTS WITH predicate */
+	jpiLikeRegex,				/* LIKE_REGEX predicate */
+} JsonPathItemType;
+
+/* XQuery regex mode flags for LIKE_REGEX predicate */
+#define JSP_REGEX_ICASE		0x01	/* i flag, case insensitive */
+#define JSP_REGEX_SLINE		0x02	/* s flag, single-line mode */
+#define JSP_REGEX_MLINE		0x04	/* m flag, multi-line mode */
+#define JSP_REGEX_WSPACE	0x08	/* x flag, expanded syntax */
+
+/*
+ * Support functions to parse/construct binary value.
+ * Unlike many other representation of expression the first/main
+ * node is not an operation but left operand of expression. That
+ * allows to implement cheep follow-path descending in jsonb
+ * structure and then execute operator with right operand
+ */
+
+typedef struct JsonPathItem
+{
+	JsonPathItemType type;
+
+	/* position form base to next node */
+	int32		nextPos;
+
+	/*
+	 * pointer into JsonPath value to current node, all positions of current
+	 * are relative to this base
+	 */
+	char	   *base;
+
+	union
+	{
+		/* classic operator with two operands: and, or etc */
+		struct
+		{
+			int32		left;
+			int32		right;
+		}			args;
+
+		/* any unary operation */
+		int32		arg;
+
+		/* storage for jpiIndexArray: indexes of array */
+		struct
+		{
+			int32		nelems;
+			struct
+			{
+				int32		from;
+				int32		to;
+			}		   *elems;
+		}			array;
+
+		/* jpiAny: levels */
+		struct
+		{
+			uint32		first;
+			uint32		last;
+		}			anybounds;
+
+		struct
+		{
+			char	   *data;	/* for bool, numeric and string/key */
+			int32		datalen;	/* filled only for string/key */
+		}			value;
+
+		struct
+		{
+			int32		expr;
+			char	   *pattern;
+			int32		patternlen;
+			uint32		flags;
+		}			like_regex;
+	}			content;
+} JsonPathItem;
+
+#define jspHasNext(jsp) ((jsp)->nextPos > 0)
+
+extern void jspInit(JsonPathItem *v, JsonPath *js);
+extern void jspInitByBuffer(JsonPathItem *v, char *base, int32 pos);
+extern bool jspGetNext(JsonPathItem *v, JsonPathItem *a);
+extern void jspGetArg(JsonPathItem *v, JsonPathItem *a);
+extern void jspGetLeftArg(JsonPathItem *v, JsonPathItem *a);
+extern void jspGetRightArg(JsonPathItem *v, JsonPathItem *a);
+extern Numeric jspGetNumeric(JsonPathItem *v);
+extern bool jspGetBool(JsonPathItem *v);
+extern char *jspGetString(JsonPathItem *v, int32 *len);
+extern bool jspGetArraySubscript(JsonPathItem *v, JsonPathItem *from,
+					 JsonPathItem *to, int i);
+
+extern const char *jspOperationName(JsonPathItemType type);
+
+/*
+ * Parsing support data structures.
+ */
+
+typedef struct JsonPathParseItem JsonPathParseItem;
+
+struct JsonPathParseItem
+{
+	JsonPathItemType type;
+	JsonPathParseItem *next;	/* next in path */
+
+	union
+	{
+
+		/* classic operator with two operands: and, or etc */
+		struct
+		{
+			JsonPathParseItem *left;
+			JsonPathParseItem *right;
+		}			args;
+
+		/* any unary operation */
+		JsonPathParseItem *arg;
+
+		/* storage for jpiIndexArray: indexes of array */
+		struct
+		{
+			int			nelems;
+			struct
+			{
+				JsonPathParseItem *from;
+				JsonPathParseItem *to;
+			}		   *elems;
+		}			array;
+
+		/* jpiAny: levels */
+		struct
+		{
+			uint32		first;
+			uint32		last;
+		}			anybounds;
+
+		struct
+		{
+			JsonPathParseItem *expr;
+			char	   *pattern;	/* could not be not null-terminated */
+			uint32		patternlen;
+			uint32		flags;
+		}			like_regex;
+
+		/* scalars */
+		Numeric numeric;
+		bool		boolean;
+		struct
+		{
+			uint32		len;
+			char	   *val;	/* could not be not null-terminated */
+		}			string;
+	}			value;
+};
+
+typedef struct JsonPathParseResult
+{
+	JsonPathParseItem *expr;
+	bool		lax;
+} JsonPathParseResult;
+
+extern JsonPathParseResult *parsejsonpath(const char *str, int len);
+
+#endif