8000 added optional quantifier support for array filter operator (#16315) · rnshah9/arangodb@2cb5f92 · GitHub
[go: up one dir, main page]
Skip to content

Commit 2cb5f92

Browse files
jsteemannjsteemann
authored
added optional quantifier support for array filter operator (arangodb#16315)
* added optional quantifier support for array filter operator * fixed behavior, added tests
1 parent 687708e commit 2cb5f92

File tree

9 files changed

+1295
-958
lines changed

9 files changed

+1295
-958
lines changed

‎arangod/Aql/Ast.cpp

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@
3838
#include "Aql/Function.h"
3939
#include "Aql/Graphs.h"
4040
#include "Aql/ModificationOptions.h"
41+
#include "Aql/Quantifier.h"
4142
#include "Aql/QueryContext.h"
4243
#include "Aql/AqlFunctionsInternalCache.h"
4344
#include "Basics/Exceptions.h"
@@ -1098,6 +1099,24 @@ AstNode* Ast::createNodeArrayLimit(AstNode const* offset,
10981099
return node;
10991100
}
11001101

1102+
/// @brief create an AST array limit node (quantifier, filter)
1103+
AstNode* Ast::createNodeArrayFilter(AstNode const* quantifier,
1104+
AstNode const* filter) {
1105+
AstNode* node = createNode(NODE_TYPE_ARRAY_FILTER);
1106+
node->reserve(2);
1107+
1108+
if (quantifier == nullptr) {
1109+
quantifier = createNodeNop();
1110+
}
1111+
1112+
TRI_ASSERT(filter != nullptr);
1113+
1114+
node->addMember(quantifier);
1115+
node->addMember(filter);
1116+
1117+
return node;
1118+
}
1119+
11011120
/// @brief create an AST boolean expansion node, with or without a filter
11021121
AstNode* Ast::createNodeBooleanExpansion(int64_t levels,
11031122
AstNode const* iterator,

‎arangod/Aql/Ast.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -320,6 +320,9 @@ class Ast {
320320
/// @brief create an AST array limit node (offset, count)
321321
AstNode* createNodeArrayLimit(AstNode const*, AstNode const*);
322322

323+
/// @brief create an AST array filter node (quantifier, filter)
324+
AstNode* createNodeArrayFilter(AstNode const*, AstNode const*);
325+
323326
/// @brief create an AST boolean expansion node
324327
AstNode* createNodeBooleanExpansion(int64_t, AstNode const*, AstNode const*,
325328
AstNode const*);

‎arangod/Aql/AstNode.cpp

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,7 @@ std::unordered_map<int, std::string const> const AstNode::TypeNames{
164164
{static_cast<int>(NODE_TYPE_VIEW), "view"},
165165
{static_cast<int>(NODE_TYPE_PARAMETER_DATASOURCE), "datasource parameter"},
166166
{static_cast<int>(NODE_TYPE_FOR_VIEW), "view enumeration"},
167+
{static_cast<int>(NODE_TYPE_ARRAY_FILTER), "array filter"},
167168
};
168169

169170
/// @brief names for AST node value types
@@ -603,6 +604,7 @@ AstNode::AstNode(Ast* ast, arangodb::velocypack::Slice slice)
603604
case NODE_TYPE_WITH:
604605
case NODE_TYPE_FOR_VIEW:
605606
case NODE_TYPE_WINDOW:
607+
case NODE_TYPE_ARRAY_FILTER:
606608
break;
607609
}
608610

@@ -1439,7 +1441,7 @@ bool AstNode::isSimple() const {
14391441

14401442
if (type == NODE_TYPE_ARRAY || type == NODE_TYPE_OBJECT ||
14411443
type == NODE_TYPE_EXPANSION || type == NODE_TYPE_ITERATOR ||
1442-
type == NODE_TYPE_ARRAY_LIMIT ||
1444+
type == NODE_TYPE_ARRAY_LIMIT || type == NODE_TYPE_ARRAY_FILTER ||
14431445
type == NODE_TYPE_CALCULATED_OBJECT_ELEMENT ||
14441446
type == NODE_TYPE_OPERATOR_TERNARY ||
14451447
type == NODE_TYPE_OPERATOR_NARY_AND ||
@@ -2068,6 +2070,16 @@ void AstNode::stringify(std::string& buffer, bool failIfLong) const {
20682070
return;
20692071
}
20702072

2073+
if (type == NODE_TYPE_ARRAY_FILTER) {
2074+
// not used by V8
2075+
buffer.append("_FILTER(");
2076+
getMember(0)->stringify(buffer, failIfLong);
2077+
buffer.push_back(',');
2078+
getMember(1)->stringify(buffer, failIfLong);
2079+
buffer.push_back(')');
2080+
return;
2081+
}
2082+
20712083
if (type == NODE_TYPE_EXPANSION) {
20722084
// not used by V8
20732085
buffer.append("_EXPANSION(");

‎arangod/Aql/AstNode.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -221,6 +221,7 @@ enum AstNodeType : uint32_t {
221221
NODE_TYPE_PARAMETER_DATASOURCE = 78,
222222
NODE_TYPE_FOR_VIEW = 79,
223223
NODE_TYPE_WINDOW = 80,
224+
NODE_TYPE_ARRAY_FILTER = 81,
224225
};
225226

226227
static_assert(NODE_TYPE_VALUE < NODE_TYPE_ARRAY, "incorrect node types order");

‎arangod/Aql/Expression.cpp

Lines changed: 79 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,8 @@
5555

5656
#include <v8.h>
5757

58+
#include <limits>
59+
5860
using namespace arangodb;
5961
using namespace arangodb::aql;
6062
using VelocyPackHelper = arangodb::basics::VelocyPackHelper;
@@ -1465,21 +1467,36 @@ AqlValue Expression::executeSimpleExpressionExpansion(ExpressionContext& ctx,
14651467
}
14661468
}
14671469

1468-
// FILTER
1469-
AstNode const* filterNode = node->getMember(2);
1470+
// quantifier and FILTER
1471+
AstNode const* quantifierAndFilterNode = node->getMember(2);
1472+
1473+
AstNode const* quantifierNode = nullptr;
1474+
AstNode const* filterNode = nullptr;
14701475

1471-
if (filterNode->type == NODE_TYPE_NOP) {
1476+
if (quantifierAndFilterNode == nullptr ||
1477+
quantifierAndFilterNode->type == NODE_TYPE_NOP) {
14721478
filterNode = nullptr;
1473-
} else if (filterNode->isConstant()) {
1474-
if (filterNode->isTrue()) {
1475-
// filter expression is always true
1476-
filterNode = nullptr;
1477-
} else {
1478-
// filter expression is always false
1479-
if (isBoolean) {
1480-
return AqlValue(AqlValueHintBool(false));
1479+
} else {
1480+
TRI_ASSERT(quantifierAndFilterNode->type == NODE_TYPE_ARRAY_FILTER);
1481+
TRI_ASSERT(quantifierAndFilterNode->numMembers() == 2);
1482+
1483+
quantifierNode = quantifierAndFilterNode->getMember(0);
1484+
TRI_ASSERT(quantifierNode != nullptr);
1485+
TRI_ASSERT(quantifierNode->type == NODE_TYPE_NOP ||
1486+
quantifierNode->isIntValue() ||
1487+
quantifierNode->type == NODE_TYPE_QUANTIFIER ||
1488+
quantifierNode->type == NODE_TYPE_RANGE);
1489+
1490+
filterNode = quantifierAndFilterNode->getMember(1);
1491+
1492+
if (!isBoolean && filterNode->isConstant()) {
1493+
if (filterNode->isTrue()) {
1494+
// filter expression is always true
1495+
filterNode = nullptr;
1496+
} else {
1497+
// filter expression is always false
1498+
return AqlValue(AqlValueHintEmptyArray());
14811499
}
1482-
return AqlValue(AqlValueHintEmptyArray());
14831500
}
14841501
}
14851502

@@ -1592,6 +1609,45 @@ AqlValue Expression::executeSimpleExpressionExpansion(ExpressionContext& ctx,
15921609
}
15931610

15941611
size_t const n = value.length();
1612+
1613+
// relevant only in case isBoolean = true
1614+
size_t minRequiredItems = 0;
1615+
size_t maxRequiredItems = 0;
1616+
size_t takenItems = 0;
1617+
1618+
if (quantifierNode == nullptr || quantifierNode->type == NODE_TYPE_NOP) {
1619+
// no quantifier. assume we need at least 1 item
1620+
minRequiredItems = 1;
1621+
maxRequiredItems = std::numeric_limits<decltype(maxRequiredItems)>::max();
1622+
} else {
1623+
// note: quantifierNode can be a NODE_TYPE_QUANTIFIER (ALL|ANY|NONE),
1624+
// a number (e.g. 3), or a range (e.g. 1..5)
1625+
if (quantifierNode->type == NODE_TYPE_QUANTIFIER) {
1626+
// ALL|ANY|NONE
1627+
std::tie(minRequiredItems, maxRequiredItems) =
1628+
Quantifier::requiredMatches(n, quantifierNode);
1629+
} else if (quantifierNode->type == NODE_TYPE_RANGE) {
1630+
// range
1631+
TRI_ASSERT(quantifierNode->numMembers() == 2);
1632+
TRI_ASSERT(quantifierNode->getMember(0)->isIntValue());
1633+
1634+
minRequiredItems =
1635+
static_cast<size_t>(quantifierNode->getMember(0)->getIntValue());
1636+
TRI_ASSERT(quantifierNode->getMember(1)->isIntValue());
1637+
maxRequiredItems =
1638+
static_cast<size_t>(quantifierNode->getMember(1)->getIntValue());
1639+
} else if (quantifierNode->isIntValue()) {
1640+
// exact value
1641+
minRequiredItems = maxRequiredItems =
1642+
static_cast<size_t>(quantifierNode->getIntValue());
1643+
} else {
1644+
// quantifier type was already validated before.
1645+
TRI_ASSERT(false);
1646+
}
1647+
}
1648+
1649+
TRI_ASSERT(minRequiredItems <= maxRequiredItems);
1650+
15951651
for (size_t i = 0; i < n; ++i) {
15961652
bool localMustDestroy;
15971653
AqlValue item = value.at(i, localMustDestroy, false);
@@ -1623,16 +1679,16 @@ AqlValue Expression::executeSimpleExpressionExpansion(ExpressionContext& ctx,
16231679
}
16241680

16251681
if (takeItem) {
1626-
if (isBoolean) {
1627-
return AqlValue(AqlValueHintBool(true));
1628-
}
1682+
++takenItems;
16291683

1630-
AqlValue sub = executeSimpleExpression(ctx, projectionNode,
1631-
localMustDestroy, false);
1632-
sub.toVelocyPack(&vopts, builder, /*resolveExternals*/ false,
1633-
/*allowUnindexed*/ false);
1634-
if (localMustDestroy) {
1635-
sub.destroy();
1684+
if (!isBoolean) {
1685+
AqlValue sub = executeSimpleExpression(ctx, projectionNode,
1686+
localMustDestroy, false);
1687+
sub.toVelocyPack(&vopts, builder, /*resolveExternals*/ false,
1688+
/*allowUnindexed*/ false);
1689+
if (localMustDestroy) {
1690+
sub.destroy();
1691+
}
16361692
}
16371693
}
16381694
ctx.clearVariable(variable);
@@ -1652,7 +1708,8 @@ AqlValue Expression::executeSimpleExpressionExpansion(ExpressionContext& ctx,
16521708
}
16531709

16541710
if (isBoolean) {
1655-
return AqlValue(AqlValueHintBool(false));
1711+
return AqlValue(AqlValueHintBool(takenItems >= minRequiredItems &&
1712+
takenItems <= maxRequiredItems));
16561713
}
16571714

16581715
builder.close();

0 commit comments

Comments
 (0)
0