/*

 * Copyright 2022 Google LLC

 *

 * Use of this source code is governed by a BSD-style license that can be

 * found in the LICENSE file.

 */

#include "include/core/SkTypes.h"

#include "src/core/SkTHash.h"

#include "src/sksl/SkSLContext.h"

#include "src/sksl/SkSLIntrinsicList.h"

#include "src/sksl/SkSLProgramSettings.h"

#include "src/sksl/analysis/SkSLProgramUsage.h"

#include "src/sksl/ir/SkSLFunctionDeclaration.h"

#include "src/sksl/ir/SkSLFunctionDefinition.h"

#include "src/sksl/ir/SkSLProgram.h"

#include "src/sksl/ir/SkSLSymbol.h"

#include "src/sksl/transform/SkSLTransform.h"

#include <algorithm>

#include <cstddef>

#include <memory>

#include <string>

#include <string_view>

#include <vector>

namespace SkSL {

class ProgramElement;

void Transform::FindAndDeclareBuiltinFunctions(Program& program) {

    ProgramUsage* usage = program.fUsage.get();

    Context& context = *program.fContext;

    std::vector<const FunctionDefinition*> addedBuiltins;

    for (;;) {

        // Find all the built-ins referenced by the program but not yet included in the code.

        size_t numBuiltinsAtStart = addedBuiltins.size();

        for (const auto& [symbol, count] : usage->fCallCounts) {

            const FunctionDeclaration& fn = symbol->as<FunctionDeclaration>();

            if (!fn.isBuiltin() || count == 0) {

                // Not a built-in; skip it.

                continue;

            }

            if (fn.intrinsicKind() == k_dFdy_IntrinsicKind) {

                // Programs that invoke the `dFdy` intrinsic will need the RTFlip input.

                if (!context.fConfig->fSettings.fForceNoRTFlip) {

                    program.fInterface.fRTFlipUniform |= Program::Interface::kRTFlip_Derivative;

                }

            }

            if (const FunctionDefinition* builtinDef = fn.definition()) {

                // Make sure we only add a built-in function once. We rarely add more than a handful

                // of builtin functions, so linear search here is good enough.

                if (std::find(addedBuiltins.begin(), addedBuiltins.end(), builtinDef) ==

                    addedBuiltins.end()) {

                    addedBuiltins.push_back(builtinDef);

                }

            }

        }

        if (addedBuiltins.size() == numBuiltinsAtStart) {

            // If we didn't reference any more built-in functions than before, we're done.

            break;

        }

        // Sort the referenced builtin functions into a consistent order; otherwise our output will

        // become non-deterministic. The exact order isn't particularly important; we sort backwards

        // because we add elements to the shared-elements in reverse order at the end.

        std::sort(addedBuiltins.begin() + numBuiltinsAtStart,

                  addedBuiltins.end(),

                  [](const FunctionDefinition* aDefinition, const FunctionDefinition* bDefinition) {

                      const FunctionDeclaration& a = aDefinition->declaration();

                      const FunctionDeclaration& b = bDefinition->declaration();

                      if (a.name() != b.name()) {

                          return a.name() > b.name();

                      }

                      return a.description() > b.description();

                  });

        // Update the ProgramUsage to track all these newly discovered functions.

        int usageCallCounts = usage->fCallCounts.count();

        for (size_t index = numBuiltinsAtStart; index < addedBuiltins.size(); ++index) {

            usage->add(*addedBuiltins[index]);

        }

        if (usage->fCallCounts.count() == usageCallCounts) {

            // If we aren't making any more unique function calls than before, we're done.

            break;

        }

    }

    // Insert the new functions into the program's shared elements, right at the front.

    // They are added in reverse so that the deepest dependencies are added to the top.

    program.fSharedElements.insert(program.fSharedElements.begin(),

                                   addedBuiltins.rbegin(), addedBuiltins.rend());

}

}  // namespace SkSL