Filter Expression parser
This commit implements a parser for $filter expressions, per the redfish
specification and odata specification. This is intended to be used to
support $filter query for collections.
For parsing libraries, this commit chooses boost spirit x3. It's chosen
because it doesn't require a new external dependency, and is done
entirely in the compiler, using C++ syntax. While the syntax is still
somewhat difficult to read, there's a slew of unit tests included to
make sure that at least the common things we expect to work will parse
correctly.
Tested: Unit tests pass (good coverage). Code not yet used.
Signed-off-by: Ed Tanous <edtanous@google.com>
Change-Id: I1b0ab615bc49064acab4dad47f0a8aa499557bfc
diff --git a/meson.build b/meson.build
index e1bbeeb..6ca861d 100644
--- a/meson.build
+++ b/meson.build
@@ -84,6 +84,7 @@
'-Wno-switch-enum',
'-Wno-unused-macros',
'-Wno-covered-switch-default',
+ '-Wno-disabled-macro-expansion',
language: 'cpp',
)
endif
@@ -169,6 +170,7 @@
'-DBOOST_EXCEPTION_DISABLE',
'-DBOOST_NO_EXCEPTIONS',
'-DBOOST_URL_NO_SOURCE_LOCATION',
+ '-DBOOST_SPIRIT_X3_NO_RTTI',
'-DJSON_NOEXCEPTION',
'-DOPENSSL_NO_FILENAMES',
'-DSDBUSPLUS_DISABLE_BOOST_COROUTINES',
@@ -256,7 +258,7 @@
opt = cmake.subproject_options()
opt.add_cmake_defines(
{
- 'BOOST_INCLUDE_LIBRARIES': 'asio;beast;callable_traits;headers;process;type_index;url;uuid',
+ 'BOOST_INCLUDE_LIBRARIES': 'asio;beast;callable_traits;headers;process;type_index;url;uuid;spirit',
'BUILD_SHARED_LIBS': 'OFF',
},
)
@@ -270,6 +272,7 @@
boost_type_index = boost.dependency('boost_type_index').as_system()
boost_url = boost.dependency('boost_url').as_system()
boost_uuid = boost.dependency('boost_uuid').as_system()
+ boost_spirit = boost.dependency('boost_spirit').as_system()
bmcweb_dependencies += [
boost_asio,
boost_beast,
@@ -279,6 +282,7 @@
boost_type_index,
boost_url,
boost_uuid,
+ boost_spirit,
]
endif
@@ -328,6 +332,7 @@
'redfish-core/src/error_messages.cpp',
# Begin large files, should be at the beginning
+ 'redfish-core/src/filter_expr_printer.cpp',
'redfish-core/src/redfish.cpp',
'redfish-core/src/registries.cpp',
'redfish-core/src/utils/dbus_utils.cpp',
@@ -388,6 +393,7 @@
'test/include/ssl_key_handler_test.cpp',
'test/include/str_utility_test.cpp',
'test/redfish-core/include/privileges_test.cpp',
+ 'test/redfish-core/include/filter_expr_parser_test.cpp',
'test/redfish-core/include/redfish_aggregator_test.cpp',
'test/redfish-core/include/registries_test.cpp',
'test/redfish-core/include/utils/dbus_utils.cpp',
diff --git a/redfish-core/include/filter_expr_parser_ast.hpp b/redfish-core/include/filter_expr_parser_ast.hpp
new file mode 100644
index 0000000..b27dbb4
--- /dev/null
+++ b/redfish-core/include/filter_expr_parser_ast.hpp
@@ -0,0 +1,80 @@
+#pragma once
+#include <boost/fusion/include/adapt_struct.hpp>
+#include <boost/spirit/home/x3.hpp>
+#include <boost/spirit/home/x3/support/ast/variant.hpp>
+
+#include <iostream>
+#include <list>
+#include <numeric>
+#include <optional>
+#include <string>
+
+namespace redfish
+{
+namespace filter_ast
+{
+
+namespace x3 = boost::spirit::x3;
+
+// Represents a string literal
+// (ie 'Enabled')
+struct QuotedString : std::string
+{};
+
+// Represents a string that matches an identifier
+// Looks similar to a json pointer
+struct UnquotedString : std::string
+{};
+
+// Because some program elements can reference BooleanOp recursively,
+// they need to be forward declared so that x3::forward_ast can be used
+struct LogicalAnd;
+struct Comparison;
+using BooleanOp =
+ x3::variant<x3::forward_ast<Comparison>, x3::forward_ast<LogicalAnd>>;
+
+enum class ComparisonOpEnum
+{
+ Invalid,
+ Equals,
+ NotEquals,
+ GreaterThan,
+ GreaterThanOrEqual,
+ LessThan,
+ LessThanOrEqual
+};
+
+// An expression that has been negated with not
+struct LogicalNot
+{
+ std::optional<char> isLogicalNot;
+ BooleanOp operand;
+};
+
+using Argument = x3::variant<int64_t, double, UnquotedString, QuotedString>;
+
+struct Comparison
+{
+ Argument left;
+ ComparisonOpEnum token = ComparisonOpEnum::Invalid;
+ Argument right;
+};
+
+struct LogicalOr
+{
+ LogicalNot first;
+ std::list<LogicalNot> rest;
+};
+struct LogicalAnd
+{
+ LogicalOr first;
+ std::list<LogicalOr> rest;
+};
+} // namespace filter_ast
+} // namespace redfish
+
+BOOST_FUSION_ADAPT_STRUCT(redfish::filter_ast::Comparison, left, token, right);
+BOOST_FUSION_ADAPT_STRUCT(redfish::filter_ast::LogicalNot, isLogicalNot,
+ operand);
+BOOST_FUSION_ADAPT_STRUCT(redfish::filter_ast::LogicalOr, first, rest);
+BOOST_FUSION_ADAPT_STRUCT(redfish::filter_ast::LogicalAnd, first, rest);
diff --git a/redfish-core/include/filter_expr_parser_grammar.hpp b/redfish-core/include/filter_expr_parser_grammar.hpp
new file mode 100644
index 0000000..7d71a0f
--- /dev/null
+++ b/redfish-core/include/filter_expr_parser_grammar.hpp
@@ -0,0 +1,112 @@
+#pragma once
+
+#include "filter_expr_parser_ast.hpp"
+
+#include <boost/spirit/home/x3.hpp>
+
+namespace redfish::filter_grammar
+{
+
+// The below rules very intentionally use the same naming as section 7.3.4 of
+// the redfish specification and are declared in the order of the precedence
+// that the standard requires.
+
+namespace details
+{
+using boost::spirit::x3::char_;
+using boost::spirit::x3::int64;
+using boost::spirit::x3::lit;
+using boost::spirit::x3::real_parser;
+using boost::spirit::x3::rule;
+using boost::spirit::x3::strict_real_policies;
+using boost::spirit::x3::symbols;
+
+using filter_ast::BooleanOp;
+using filter_ast::Comparison;
+using filter_ast::ComparisonOpEnum;
+using filter_ast::LogicalAnd;
+using filter_ast::LogicalNot;
+using filter_ast::LogicalOr;
+using filter_ast::QuotedString;
+using filter_ast::UnquotedString;
+
+// Clang format makes a mess of these rules and makes them hard to read
+// clang-format on
+
+// Basic argument types
+const rule<class QuotedStringId, QuotedString> quotedString("QuotedString");
+const rule<class UnquotedStrId, UnquotedString> unquotedString("UnquotedStr");
+
+// Value comparisons -> boolean (value eq value) (value lt number)
+const rule<class BooleanOpId, BooleanOp> booleanOp("BooleanOp");
+const rule<class ComparisonId, Comparison> comparison("Comparison");
+
+// Logical Comparisons (bool eq bool)
+const rule<class LogicalAndId, LogicalAnd> logicalAnd("LogicalAnd");
+const rule<class LogicalOrId, LogicalOr> logicalOr("LogicalOr");
+const rule<class LogicalNotId, LogicalNot> logicalNot("LogicalNot");
+
+///// BEGIN GRAMMAR
+
+// Two types of strings.
+const auto quotedString_def = '\'' >> *('\\' >> char_ | ~char_('\'')) >> '\'';
+const auto unquotedString_def = char_("a-zA-Z") >> *(char_("a-zA-Z0-9[]/"));
+
+// Spaces
+// Filter examples have unclear guidelines about between which arguments spaces
+// are allowed or disallowed. Specification is not clear, so in almost all
+// cases we allow zero or more
+const auto sp = *lit(' ');
+
+// Make sure we only parse true floating points as doubles
+// This requires we have a "." which causes 1 to parse as int64, and 1.0 to
+// parse as double
+constexpr const real_parser<double, strict_real_policies<double>> strictDouble;
+
+// Argument
+const auto arg = strictDouble | int64 | unquotedString | quotedString;
+
+// Note, unlike most other comparisons, spaces are required here (one or more)
+// to differentiate keys from values (ex Fooeq eq foo)
+const auto rsp = +lit(' ');
+
+// Greater Than/Less Than/Equals
+const symbols<ComparisonOpEnum> compare{
+ {"gt", ComparisonOpEnum::GreaterThan},
+ {"ge", ComparisonOpEnum::GreaterThanOrEqual},
+ {"lt", ComparisonOpEnum::LessThan},
+ {"le", ComparisonOpEnum::LessThanOrEqual},
+ {"ne", ComparisonOpEnum::NotEquals},
+ {"eq", ComparisonOpEnum::Equals}};
+
+const auto comparison_def = arg >> rsp >> compare >> rsp >> arg;
+
+// Parenthesis
+const auto parens = lit('(') >> sp >> logicalAnd >> sp >> lit(')');
+
+// Logical values
+const auto booleanOp_def = comparison | parens;
+
+// Not
+const auto logicalNot_def = -(char_('n') >> lit("ot") >> sp) >> booleanOp;
+
+// Or
+const auto logicalOr_def = logicalNot >> *(sp >> lit("or") >> sp >> logicalNot);
+
+// And
+const auto logicalAnd_def = logicalOr >> *(sp >> lit("and") >> sp >> logicalOr);
+
+BOOST_SPIRIT_DEFINE(booleanOp, logicalAnd, logicalNot, logicalOr, quotedString,
+ comparison, unquotedString);
+///// END GRAMMAR
+
+// Make the grammar and AST available outside of the system
+static constexpr auto& grammar = logicalAnd;
+using program = filter_ast::LogicalAnd;
+
+} // namespace details
+
+using details::grammar;
+using details::program;
+
+} // namespace redfish::filter_grammar
diff --git a/redfish-core/include/filter_expr_printer.hpp b/redfish-core/include/filter_expr_printer.hpp
new file mode 100644
index 0000000..904db7d
--- /dev/null
+++ b/redfish-core/include/filter_expr_printer.hpp
@@ -0,0 +1,26 @@
+#pragma once
+
+#include "filter_expr_parser_ast.hpp"
+
+#include <memory>
+#include <optional>
+#include <string_view>
+
+namespace redfish
+{
+struct FilterExpressionPrinter
+{
+ using result_type = std::string;
+ std::string operator()(double x) const;
+ std::string operator()(int64_t x) const;
+ std::string operator()(const filter_ast::QuotedString& x) const;
+ std::string operator()(const filter_ast::UnquotedString& x) const;
+ std::string operator()(const filter_ast::LogicalNot& x) const;
+ std::string operator()(const filter_ast::LogicalOr& x) const;
+ std::string operator()(const filter_ast::LogicalAnd& x) const;
+ std::string operator()(const filter_ast::Comparison& x) const;
+ std::string operator()(const filter_ast::BooleanOp& operation) const;
+};
+
+std::optional<filter_ast::LogicalAnd> parseFilter(std::string_view expr);
+} // namespace redfish
diff --git a/redfish-core/src/filter_expr_printer.cpp b/redfish-core/src/filter_expr_printer.cpp
new file mode 100644
index 0000000..abf1daa
--- /dev/null
+++ b/redfish-core/src/filter_expr_printer.cpp
@@ -0,0 +1,148 @@
+#include "filter_expr_printer.hpp"
+
+#include "filter_expr_parser_ast.hpp"
+#include "filter_expr_parser_grammar.hpp"
+#include "logging.hpp"
+
+#include <iostream>
+#include <list>
+#include <numeric>
+#include <optional>
+#include <string>
+
+namespace redfish
+{
+
+///////////////////////////////////////////////////////////////////////////
+// The AST Printer
+// Prints a $filter AST as a string to be compared, including explicit braces
+// around all operations to help debugging AST issues.
+///////////////////////////////////////////////////////////////////////////
+
+using result_type = std::string;
+std::string FilterExpressionPrinter::operator()(double x) const
+{
+ return std::format("double({})", x);
+}
+std::string FilterExpressionPrinter::operator()(int64_t x) const
+{
+ return std::format("int({})", x);
+}
+std::string
+ FilterExpressionPrinter::operator()(const filter_ast::QuotedString& x) const
+{
+ return std::format("quoted_string(\"{}\")", static_cast<std::string>(x));
+}
+std::string FilterExpressionPrinter::operator()(
+ const filter_ast::UnquotedString& x) const
+{
+ return std::format("unquoted_string(\"{}\")", static_cast<std::string>(x));
+}
+
+std::string
+ FilterExpressionPrinter::operator()(const filter_ast::LogicalNot& x) const
+{
+ std::string prefix;
+ std::string postfix;
+ if (x.isLogicalNot)
+ {
+ prefix = "not(";
+ postfix = ")";
+ }
+ return std::format("{}{}{}", prefix, (*this)(x.operand), postfix);
+}
+std::string
+ FilterExpressionPrinter::operator()(const filter_ast::LogicalOr& x) const
+{
+ std::string prefix;
+ std::string postfix;
+ if (!x.rest.empty())
+ {
+ prefix = "(";
+ postfix = ")";
+ }
+ std::string out = std::format("{}{}{}", prefix, (*this)(x.first), postfix);
+
+ for (const filter_ast::LogicalNot& oper : x.rest)
+ {
+ out += std::format(" or ({})", (*this)(oper));
+ }
+ return out;
+}
+
+std::string
+ FilterExpressionPrinter::operator()(const filter_ast::LogicalAnd& x) const
+{
+ std::string prefix;
+ std::string postfix;
+ if (!x.rest.empty())
+ {
+ prefix = "(";
+ postfix = ")";
+ }
+ std::string out = std::format("{}{}{}", prefix, (*this)(x.first), postfix);
+
+ for (const filter_ast::LogicalOr& oper : x.rest)
+ {
+ out += std::format(" and ({})", (*this)(oper));
+ }
+ return out;
+}
+
+static std::string toString(filter_ast::ComparisonOpEnum rel)
+{
+ switch (rel)
+ {
+ case filter_ast::ComparisonOpEnum::GreaterThan:
+ return "Greater Than";
+ case filter_ast::ComparisonOpEnum::GreaterThanOrEqual:
+ return "Greater Than Or Equal";
+ case filter_ast::ComparisonOpEnum::LessThan:
+ return "Less Than";
+ case filter_ast::ComparisonOpEnum::LessThanOrEqual:
+ return "Less Than Or Equal";
+ case filter_ast::ComparisonOpEnum::Equals:
+ return "Equals";
+ case filter_ast::ComparisonOpEnum::NotEquals:
+ return "Not Equal";
+ default:
+ return "Invalid";
+ }
+}
+
+std::string
+ FilterExpressionPrinter::operator()(const filter_ast::Comparison& x) const
+{
+ std::string left = boost::apply_visitor(*this, x.left);
+ std::string right = boost::apply_visitor(*this, x.right);
+
+ return std::format("{} {} {}", left, toString(x.token), right);
+}
+
+std::string FilterExpressionPrinter::operator()(
+ const filter_ast::BooleanOp& operation) const
+{
+ return boost::apply_visitor(*this, operation);
+}
+
+std::optional<filter_grammar::program> parseFilter(std::string_view expr)
+{
+ const auto& grammar = filter_grammar::grammar;
+ filter_grammar::program program;
+
+ std::string_view::iterator iter = expr.begin();
+ const std::string_view::iterator end = expr.end();
+ BMCWEB_LOG_DEBUG("Parsing input string \"{}\"", expr);
+ bool r = boost::spirit::x3::parse(iter, end, grammar, program);
+
+ if (!r)
+ {
+ std::string rest(iter, end);
+
+ BMCWEB_LOG_ERROR("Parsing failed stopped at \"{}\"", rest);
+ return std::nullopt;
+ }
+ BMCWEB_LOG_DEBUG("Parsed AST: \"{}\"", FilterExpressionPrinter()(program));
+ return {std::move(program)};
+}
+} // namespace redfish
diff --git a/test/redfish-core/include/filter_expr_parser_test.cpp b/test/redfish-core/include/filter_expr_parser_test.cpp
new file mode 100644
index 0000000..2e5df83
--- /dev/null
+++ b/test/redfish-core/include/filter_expr_parser_test.cpp
@@ -0,0 +1,122 @@
+#include "filter_expr_parser_ast.hpp"
+#include "filter_expr_printer.hpp"
+
+#include <optional>
+#include <string_view>
+
+#include "gmock/gmock.h"
+
+namespace redfish
+{
+
+static void parse(std::string_view filterExpression, std::string_view outputAst)
+{
+ std::optional<filter_ast::LogicalAnd> ast = parseFilter(filterExpression);
+ FilterExpressionPrinter pr;
+ EXPECT_TRUE(ast);
+ if (ast)
+ {
+ EXPECT_EQ(pr(*ast), outputAst);
+ }
+}
+
+TEST(FilterParser, SpecificationExamples)
+{
+ parse("ProcessorSummary/Count eq 2",
+ "unquoted_string(\"ProcessorSummary/Count\") Equals int(2)");
+ parse(
+ "ProcessorSummary/Count ge 2",
+ "unquoted_string(\"ProcessorSummary/Count\") Greater Than Or Equal int(2)");
+ parse("ProcessorSummary/Count gt 2",
+ "unquoted_string(\"ProcessorSummary/Count\") Greater Than int(2)");
+ parse(
+ "MemorySummary/TotalSystemMemoryGiB le 64",
+ "unquoted_string(\"MemorySummary/TotalSystemMemoryGiB\") Less Than Or Equal int(64)");
+ parse(
+ "MemorySummary/TotalSystemMemoryGiB lt 64",
+ "unquoted_string(\"MemorySummary/TotalSystemMemoryGiB\") Less Than int(64)");
+ parse(
+ "SystemType ne 'Physical'",
+ R"(unquoted_string("SystemType") Not Equal quoted_string("Physical"))");
+ parse(
+ "ProcessorSummary/Count eq 2 or ProcessorSummary/Count eq 4",
+ R"((unquoted_string("ProcessorSummary/Count") Equals int(2)) or (unquoted_string("ProcessorSummary/Count") Equals int(4)))");
+ parse("not ProcessorSummary/Count eq 2",
+ "not(unquoted_string(\"ProcessorSummary/Count\") Equals int(2))");
+ parse("not ProcessorSummary/Count eq -2",
+ "not(unquoted_string(\"ProcessorSummary/Count\") Equals int(-2))");
+ parse("Status/State eq 'Enabled')",
+ R"(unquoted_string("Status/State") Equals quoted_string("Enabled"))");
+ parse(
+ "ProcessorSummary/Count eq 2 and MemorySummary/TotalSystemMemoryGiB eq 64",
+ R"((unquoted_string("ProcessorSummary/Count") Equals int(2)) and (unquoted_string("MemorySummary/TotalSystemMemoryGiB") Equals int(64)))");
+ parse(
+ "Status/State eq 'Enabled' and Status/Health eq 'OK' or SystemType eq 'Physical'",
+ R"((unquoted_string("Status/State") Equals quoted_string("Enabled")) and ((unquoted_string("Status/Health") Equals quoted_string("OK")) or (unquoted_string("SystemType") Equals quoted_string("Physical"))))");
+ parse(
+ "(Status/State eq 'Enabled' and Status/Health eq 'OK') or SystemType eq 'Physical'",
+ R"(((unquoted_string("Status/State") Equals quoted_string("Enabled")) and (unquoted_string("Status/Health") Equals quoted_string("OK"))) or (unquoted_string("SystemType") Equals quoted_string("Physical")))");
+}
+
+TEST(FilterParser, BasicOperations)
+{
+ // Negation
+ EXPECT_TRUE(parseFilter("not(ProcessorSummary/Count eq 2)"));
+
+ // Negative numbers
+ EXPECT_TRUE(parseFilter("not(ProcessorSummary/Count eq -2)"));
+
+ // Empty strings
+ EXPECT_TRUE(parseFilter("(foo eq '')"));
+
+ // Identity
+ EXPECT_TRUE(parseFilter("1 eq 1"));
+ EXPECT_TRUE(parseFilter("'foo' eq 'foo'"));
+
+ // Inverted params
+ EXPECT_TRUE(parseFilter("2 eq ProcessorSummary/Count"));
+ EXPECT_TRUE(parseFilter("'OK' eq Status/Health"));
+
+ // Floating point
+ EXPECT_TRUE(parseFilter("Reading eq 4.0"));
+ EXPECT_TRUE(parseFilter("Reading eq 1e20"));
+ EXPECT_TRUE(parseFilter("Reading eq 1.575E1"));
+ EXPECT_TRUE(parseFilter("Reading eq -2.5E-3"));
+ EXPECT_TRUE(parseFilter("Reading eq 25E-4"));
+
+ // numeric operators
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count eq 2"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count ne 2"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count gt 2"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count ge 2"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count lt 2"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count le 2"));
+
+ // String comparison
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count eq 'foo'"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count ne 'foo'"));
+
+ // Future, datetime values are strings and need to be compared
+ // Make sure they parse
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count lt 'Physical'"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count le 'Physical'"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count gt 'Physical'"));
+ EXPECT_TRUE(parseFilter("ProcessorSummary/Count ge 'Physical'"));
+ EXPECT_TRUE(parseFilter("'Physical' lt ProcessorSummary/Count"));
+ EXPECT_TRUE(parseFilter("'Physical' le ProcessorSummary/Count"));
+ EXPECT_TRUE(parseFilter("'Physical' gt ProcessorSummary/Count"));
+ EXPECT_TRUE(parseFilter("'Physical' ge ProcessorSummary/Count"));
+}
+TEST(FilterParser, Failures)
+{
+ // Invalid expressions
+ EXPECT_FALSE(parseFilter("("));
+ EXPECT_FALSE(parseFilter(")"));
+ EXPECT_FALSE(parseFilter("()"));
+ EXPECT_FALSE(parseFilter(""));
+ EXPECT_FALSE(parseFilter(" "));
+ EXPECT_FALSE(parseFilter("ProcessorSummary/Count eq"));
+ EXPECT_FALSE(parseFilter("eq ProcessorSummary/Count"));
+ EXPECT_FALSE(parseFilter("not(ProcessorSummary/Count)"));
+}
+} // namespace redfish