arangodb · mchacki · Mar 12, 2020 · Feb 29, 2020 · Feb 29, 2020 · Feb 29, 2020
diff --git a/arangod/Aql/AllRowsFetcher.cpp b/arangod/Aql/AllRowsFetcher.cpp
@@ -60,7 +60,7 @@ std::pair<ExecutionState, AqlItemMatrix const*> AllRowsFetcher::fetchAllRows() {
   return {ExecutionState::DONE, nullptr};
 }
 
-std::tuple<ExecutionState, size_t, AqlItemBlockInputMatrix> AllRowsFetcher::execute(AqlCallStack& stack) {
+std::tuple<ExecutionState, SkipResult, AqlItemBlockInputMatrix> AllRowsFetcher::execute(AqlCallStack& stack) {
   if (!stack.isRelevant()) {
     auto [state, skipped, block] = _dependencyProxy->execute(stack);
     return {state, skipped, AqlItemBlockInputMatrix{block}};
@@ -79,13 +79,14 @@ std::tuple<ExecutionState, size_t, AqlItemBlockInputMatrix> AllRowsFetcher::exec
   TRI_ASSERT(!_aqlItemMatrix->stoppedOnShadowRow());
   while (true) {
     auto [state, skipped, block] = _dependencyProxy->execute(stack);
-    TRI_ASSERT(skipped == 0);
+    TRI_ASSERT(skipped.getSkipCount() == 0);
 
     // we will either build a complete fetched AqlItemBlockInputMatrix or return an empty one
     if (state == ExecutionState::WAITING) {
+      TRI_ASSERT(skipped.nothingSkipped());
       TRI_ASSERT(block == nullptr);
       // On waiting we have nothing to return
-      return {state, 0, AqlItemBlockInputMatrix{ExecutorState::HASMORE}};
+      return {state, SkipResult{}, AqlItemBlockInputMatrix{ExecutorState::HASMORE}};
     }
     TRI_ASSERT(block != nullptr || state == ExecutionState::DONE);
 
@@ -97,10 +98,10 @@ std::tuple<ExecutionState, size_t, AqlItemBlockInputMatrix> AllRowsFetcher::exec
     // If we find a ShadowRow or ExecutionState == Done, we're done fetching.
     if (_aqlItemMatrix->stoppedOnShadowRow() || state == ExecutionState::DONE) {
       if (state == ExecutionState::HASMORE) {
-        return {state, 0,
+        return {state, skipped,
                 AqlItemBlockInputMatrix{ExecutorState::HASMORE, _aqlItemMatrix.get()}};
       }
-      return {state, 0,
+      return {state, skipped,
               AqlItemBlockInputMatrix{ExecutorState::DONE, _aqlItemMatrix.get()}};
     }
   }

diff --git a/arangod/Aql/AllRowsFetcher.h b/arangod/Aql/AllRowsFetcher.h
@@ -44,6 +44,7 @@ enum class ExecutionState;
 template <BlockPassthrough>
 class DependencyProxy;
 class ShadowAqlItemRow;
+class SkipResult;
 
 /**
  * @brief Interface for all AqlExecutors that do need all
@@ -110,7 +111,7 @@ class AllRowsFetcher {
    *   size_t => Amount of documents skipped
    *   DataRange => Resulting data
    */
-  std::tuple<ExecutionState, size_t, DataRange> execute(AqlCallStack& stack);
+  std::tuple<ExecutionState, SkipResult, DataRange> execute(AqlCallStack& stack);
 
   /**
    * @brief Fetch one new AqlItemRow from upstream.

diff --git a/arangod/Aql/AqlCallStack.cpp b/arangod/Aql/AqlCallStack.cpp
@@ -42,7 +42,7 @@ AqlCallStack::AqlCallStack(AqlCallStack const& other, AqlCall call)
   // We can only use this constructor on relevant levels
   // Alothers need to use passThrough constructor
   TRI_ASSERT(other._depth == 0);
-  _operations.push(std::move(call));
+  _operations.emplace_back(std::move(call));
   _compatibilityMode3_6 = other._compatibilityMode3_6;
 }
 
@@ -51,7 +51,7 @@ AqlCallStack::AqlCallStack(AqlCallStack const& other)
       _depth(other._depth),
       _compatibilityMode3_6(other._compatibilityMode3_6) {}
 
-AqlCallStack::AqlCallStack(std::stack<AqlCall>&& operations)
+AqlCallStack::AqlCallStack(std::vector<AqlCall>&& operations)
     : _operations(std::move(operations)) {}
 
 bool AqlCallStack::isRelevant() const { return _depth == 0; }
@@ -68,40 +68,41 @@ AqlCall AqlCallStack::popCall() {
     // to the upwards subquery.
     // => Simply put another fetchAll Call on the stack.
     // This code is to be removed in the next version after 3.7
-    _operations.push(AqlCall{});
+    _operations.emplace_back(AqlCall{});
   }
-  auto call = _operations.top();
-  _operations.pop();
+  auto call = _operations.back();
+  _operations.pop_back();
   return call;
 }
 
 AqlCall const& AqlCallStack::peek() const {
   TRI_ASSERT(isRelevant());
+  TRI_ASSERT(_compatibilityMode3_6 || !_operations.empty());
+  if (is36Compatible() && _operations.empty()) {
+    // This is only for compatibility with 3.6
+    // there we do not have the stack beeing passed-through
+    // in AQL, we only have a single call.
+    // We can only get into this state in the abscence of
+    // LIMIT => we always do an unlimted softLimit call
+    // to the upwards subquery.
+    // => Simply put another fetchAll Call on the stack.
+    // This code is to be removed in the next version after 3.7
+    _operations.emplace_back(AqlCall{});
+  }
   TRI_ASSERT(!_operations.empty());
-  return _operations.top();
+  return _operations.back();
 }
 
 void AqlCallStack::pushCall(AqlCall&& call) {
   // TODO is this correct on subqueries?
   TRI_ASSERT(isRelevant());
-  _operations.push(call);
+  _operations.emplace_back(std::move(call));
 }
 
 void AqlCallStack::pushCall(AqlCall const& call) {
   // TODO is this correct on subqueries?
   TRI_ASSERT(isRelevant());
-  _operations.push(call);
-}
-
-void AqlCallStack::stackUpMissingCalls() {
-  while (!isRelevant()) {
-    // For every depth, we add an additional default call.
-    // The default is to produce unlimited many results,
-    // using DefaultBatchSize each.
-    _operations.emplace(AqlCall{});
-    _depth--;
-  }
-  TRI_ASSERT(isRelevant());
+  _operations.emplace_back(call);
 }
 
 void AqlCallStack::pop() {
@@ -133,8 +134,9 @@ auto AqlCallStack::fromVelocyPack(velocypack::Slice const slice) -> ResultT<AqlC
                   "When deserializing AqlCallStack: stack is empty");
   }
 
-  auto stack = std::stack<AqlCall>{};
+  auto stack = std::vector<AqlCall>{};
   auto i = std::size_t{0};
+  stack.reserve(slice.length());
   for (auto const entry : VPackArrayIterator(slice)) {
     auto maybeAqlCall = AqlCall::fromVelocyPack(entry);
 
@@ -146,7 +148,7 @@ auto AqlCallStack::fromVelocyPack(velocypack::Slice const slice) -> ResultT<AqlC
       return Result(TRI_ERROR_TYPE_ERROR, std::move(message));
     }
 
-    stack.emplace(maybeAqlCall.get());
+    stack.emplace_back(maybeAqlCall.get());
 
     ++i;
   }
@@ -157,19 +159,8 @@ auto AqlCallStack::fromVelocyPack(velocypack::Slice const slice) -> ResultT<AqlC
 }
 
 void AqlCallStack::toVelocyPack(velocypack::Builder& builder) const {
-  auto reverseStack = std::vector<AqlCall>{};
-  reverseStack.reserve(_operations.size());
-  {
-    auto ops = _operations;
-    while (!ops.empty()) {
-      reverseStack.emplace_back(ops.top());
-      ops.pop();
-    }
-  }
-
   builder.openArray();
-  for (auto it = reverseStack.rbegin(); it != reverseStack.rend(); ++it) {
-    auto const& call = *it;
+  for (auto const& call : _operations) {
     call.toVelocyPack(builder);
   }
   builder.close();
@@ -178,19 +169,50 @@ void AqlCallStack::toVelocyPack(velocypack::Builder& builder) const {
 auto AqlCallStack::toString() const -> std::string {
   auto result = std::string{};
   result += "[";
-  auto ops = _operations;
-  if (!ops.empty()) {
-    auto op = ops.top();
-    ops.pop();
+  bool isFirst = true;
+  for (auto const& op : _operations) {
+    if (!isFirst) {
+      result += ",";
+    }
+    isFirst = false;
     result += " ";
     result += op.toString();
-    while (!ops.empty()) {
-      op = ops.top();
-      ops.pop();
-      result += ", ";
-      result += op.toString();
-    }
   }
   result += " ]";
   return result;
 }
+
+auto AqlCallStack::createEquivalentFetchAllShadowRowsStack() const -> AqlCallStack {
+  AqlCallStack res{*this};
+  std::replace_if(
+      res._operations.begin(), res._operations.end(),
+      [](auto const&) -> bool { return true; }, AqlCall{});
+  return res;
+}
+
+auto AqlCallStack::needToSkipSubquery() const noexcept -> bool {
+  return std::any_of(_operations.begin(), _operations.end(), [](AqlCall const& call) -> bool {
+    return call.needSkipMore() || call.hardLimit == 0;
+  });
+}
+
+auto AqlCallStack::shadowRowDepthToSkip() const -> size_t {
+  TRI_ASSERT(needToSkipSubquery());
+  for (size_t i = 0; i < _operations.size(); ++i) {
+    auto& call = _operations.at(i);
+    if (call.needSkipMore() || call.hardLimit == 0) {
+      return _operations.size() - i - 1;
+    }
+  }
+  // unreachable
+  TRI_ASSERT(false);
+  THROW_ARANGO_EXCEPTION(TRI_ERROR_INTERNAL_AQL);
+}
+
+auto AqlCallStack::modifyCallAtDepth(size_t depth) -> AqlCall& {
+  // depth 0 is back of vector
+  TRI_ASSERT(_operations.size() > depth);
+  // Take the depth-most from top of the vector.
+  auto& call = *(_operations.rbegin() + depth);
+  return call;
+}
diff --git a/arangod/Aql/AqlCallStack.h b/arangod/Aql/AqlCallStack.h
@@ -66,14 +66,6 @@ class AqlCallStack {
   // Put another call on top of the stack.
   void pushCall(AqlCall const& call);
 
-  // fill up all missing calls within this stack s.t. we reach depth == 0
-  // This needs to be called if an executor requires to be fully executed, even if skipped,
-  // even if the subquery it is located in is skipped.
-  // The default operations added here will correspond to produce all Rows, unlimitted.
-  // e.g. every Modification Executor needs to call this functionality, as modifictions need to be
-  // performed even if skipped.
-  void stackUpMissingCalls();
-
   // Pops one subquery level.
   // if this isRelevent it pops the top-most call from the stack.
   // if this is not revelent it reduces the depth by 1.
@@ -95,12 +87,58 @@ class AqlCallStack {
 
   void toVelocyPack(velocypack::Builder& builder) const;
 
+  auto is36Compatible() const noexcept -> bool { return _compatibilityMode3_6; }
+
+  /**
+   * @brief Create an equivalent call stack that does a full-produce
+   *        of all Subquery levels. This is required for blocks
+   *        that are not allowed to be bpassed.
+   *        The top-most call remains unmodified, as the Executor might
+   *        require some soft limit on it.
+   *
+   * @return AqlCallStack a stack of equivalent size, that does not skip
+   *         on any lower subquery.
+   */
+  auto createEquivalentFetchAllShadowRowsStack() const -> AqlCallStack;
+
+  /**
+   * @brief Check if we are in a subquery that is in-fact required to
+   *        be skipped. This is relevant for executors that have created
+   *        an equivalentFetchAllShadowRows stack, in order to decide if
+   *        the need to produce output or if they are skipped.
+   *
+   * @return true
+   * @return false
+   */
+  auto needToSkipSubquery() const noexcept -> bool;
+
+  /**
+   * @brief This is only valid if needToSkipSubquery is true.
+   *        It will resolve to the heighest subquery level
+   *        (outermost) that needs to be skipped.
+   *
+   *
+   * @return size_t Depth of the subquery that asks to be skipped.
+   */
+  auto shadowRowDepthToSkip() const -> size_t;
+
+  /**
+   * @brief Get a reference to the call at the given shadowRowDepth
+   *
+   * @param depth ShadowRow depth we need to work on
+   * @return AqlCall& reference to the call, can be modified.
+   */
+  auto modifyCallAtDepth(size_t depth) -> AqlCall&;
+
  private:
-  explicit AqlCallStack(std::stack<AqlCall>&& operations);
+  explicit AqlCallStack(std::vector<AqlCall>&& operations);
 
  private:
-  // The list of operations, stacked by depth (e.g. bottom element is from main query)
-  std::stack<AqlCall> _operations;
+  // The list of operations, stacked by depth (e.g. bottom element is from main
+  // query) NOTE: This is only mutable on 3.6 compatibility mode. We need to
+  // inject an additional call in any const operation here just to pretend we
+  // are not empty. Can be removed after 3.7.
+  mutable std::vector<AqlCall> _operations;
 
   // The depth of subqueries that have not issued calls into operations,
   // as they have been skipped.