created_function.cc | Explore in Territory

/*
 * Copyright (C) 2019 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "src/trace_processor/perfetto_sql/engine/created_function.h"

#include <cstddef>
#include <queue>
#include <stack>

#include "perfetto/base/status.h"
#include "src/trace_processor/perfetto_sql/engine/function_util.h"
#include "src/trace_processor/perfetto_sql/engine/perfetto_sql_engine.h"
#include "src/trace_processor/sqlite/scoped_db.h"
#include "src/trace_processor/sqlite/sql_source.h"
#include "src/trace_processor/sqlite/sqlite_engine.h"
#include "src/trace_processor/sqlite/sqlite_utils.h"
#include "src/trace_processor/tp_metatrace.h"
#include "src/trace_processor/util/status_macros.h"

namespace perfetto {
namespace trace_processor {

namespace {

base::Status CheckNoMoreRows(sqlite3_stmt* stmt,
                             sqlite3* db,
                             const FunctionPrototype& prototype) { … }

// Note: if the returned type is string / bytes, it will be invalidated by the
// next call to SQLite, so the caller must take care to either copy or use the
// value before calling SQLite again.
base::StatusOr<SqlValue> EvaluateScalarStatement(
    sqlite3_stmt* stmt,
    sqlite3* db,
    const FunctionPrototype& prototype) { … }

base::Status BindArguments(sqlite3_stmt* stmt,
                           const FunctionPrototype& prototype,
                           size_t argc,
                           sqlite3_value** argv) { … }

struct StoredSqlValue { … };

class Memoizer { … };

// A helper to unroll recursive calls: to minimise the amount of stack space
// used, memoized recursive calls are evaluated using an on-heap queue.
//
// We compute the function in two passes:
// - In the first pass, we evaluate the statement to discover which recursive
//   calls it makes, returning null from recursive calls and ignoring the
//   result.
// - In the second pass, we evaluate the statement again, but this time we
//   memoize the result of each recursive call.
//
// We maintain a queue for scheduled "first pass" calls and a stack for the
// scheduled "second pass" calls, evaluating available first pass calls, then
// second pass calls. When we evaluate a first pass call, the further calls to
// CreatedFunction::Run will just add it to the "first pass" queue. The second
// pass, however, will evaluate the function normally, typically just using the
// memoized result for the dependent calls. However, if the recursive calls
// depend on the return value of the function, we will proceed with normal
// recursion.
//
// To make it more concrete, consider an following example.
// We have a function computing factorial (f) and we want to compute f(3).
//
// SELECT create_function('f(x INT)', 'INT',
// 'SELECT IIF($x = 0, 1, $x * f($x - 1))');
// SELECT experimental_memoize('f');
// SELECT f(3);
//
// - We start with a call to f(3). It executes the statement as normal, which
//   recursively calls f(2).
// - When f(2) is called, we detect that it is a recursive call and we start
//   unrolling it, entering RecursiveCallUnroller::Run.
// - We schedule first pass for 2 and the state of the unroller
//   is first_pass: [2], second_pass: [].
// - Then we compute the first pass for f(2). It calls f(1), which is ignored
//   due to OnFunctionCall returning kIgnoreDueToFirstPass and 1 is added to the
//   first pass queue. 2 is taked out of the first pass queue and moved to the
//   second pass stack. State: first_pass: [1], second_pass: [2].
// - Then we compute the first pass for 1. The similar thing happens: f(0) is
//   called and ignored, 0 is added to first_pass, 1 is added to second_pass.
//   State: first_pass: [0], second_pass: [2, 1].
// - Then we compute the first pass for 0. It doesn't make further calls, so
//   0 is moved to the second pass stack.
//   State: first_pass: [], second_pass: [2, 1, 0].
// - Then we compute the second pass for 0. It just returns 1.
//   State: first_pass: [], second_pass: [2, 1], results: {0: 1}.
// - Then we compute the second pass for 1. It calls f(0), which is memoized.
//   State: first_pass: [], second_pass: [2], results: {0: 1, 1: 1}.
// - Then we compute the second pass for 1. It calls f(1), which is memoized.
//   State: first_pass: [], second_pass: [], results: {0: 1, 1: 1, 2: 2}.
// - As both first_pass and second_pass are empty, we return from
//   RecursiveCallUnroller::Run.
// - Control is returned to CreatedFunction::Run for f(2), which returns
//   memoized value.
// - Then control is returned to CreatedFunction::Run for f(3), which completes
//   the computation.
class RecursiveCallUnroller { … };

}  // namespace

// This class is used to store the state of a CREATE_FUNCTION call.
// It is used to store the state of the function across multiple invocations
// of the function (e.g. when the function is called recursively).
class State : public CreatedFunction::Context { … };

State::~State() = default;

std::unique_ptr<CreatedFunction::Context> CreatedFunction::MakeContext(
    PerfettoSqlEngine* engine) { … }

bool CreatedFunction::IsValid(Context* ctx) { … }

void CreatedFunction::Reset(Context* ctx, PerfettoSqlEngine* engine) { … }

base::Status CreatedFunction::Run(CreatedFunction::Context* ctx,
                                  size_t argc,
                                  sqlite3_value** argv,
                                  SqlValue& out,
                                  Destructors&) { … }

void CreatedFunction::Cleanup(CreatedFunction::Context* ctx) { … }

base::Status CreatedFunction::VerifyPostConditions(
    CreatedFunction::Context* ctx) { … }

base::Status CreatedFunction::Prepare(CreatedFunction::Context* ctx,
                                      FunctionPrototype prototype,
                                      sql_argument::Type return_type,
                                      SqlSource source) { … }

base::Status CreatedFunction::EnableMemoization(Context* ctx) { … }

}  // namespace trace_processor
}  // namespace perfetto
chromium/third_party/perfetto/src/trace_processor/perfetto_sql/engine/created_function.cc
