/**
 * @license
 * Copyright 2020 Google LLC. All Rights Reserved.
 * 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.
 * =============================================================================
 */
import { env, TopK, util } from '@tensorflow/tfjs-core';
import { topKImplCPU } from '../kernel_utils/shared';
import { MergeProgram, SwapProgram } from '../top_k_gpu';
import { fill } from './Fill';
import { gatherV2 } from './GatherV2';
import { reshape } from './Reshape';
import { slice } from './Slice';
function disposeIntermediateTensorInfoOrNull(backend, tensorInfo) {
    if (tensorInfo !== null) {
        backend.disposeIntermediateTensorInfo(tensorInfo);
    }
}
function roundUpToPow2(num) {
    let pow2 = 1;
    while (pow2 < num) {
        pow2 *= 2;
    }
    return pow2;
}
// Based on Algorithm 2 of Bitonic Top K, ref:
// https://anilshanbhag.in/static/papers/gputopk_sigmod18.pdf
export function topK(args) {
    const { inputs, backend, attrs } = args;
    const { x } = inputs;
    const { k, sorted } = attrs;
    // Empirically determined constant used to determine last dim threshold for
    // handing off execution to the CPU.
    const TOPK_LAST_DIM_CPU_HANDOFF_SIZE_THRESHOLD = env().getNumber('TOPK_LAST_DIM_CPU_HANDOFF_SIZE_THRESHOLD');
    // Empirically determined constant used to determine k threshold for handing
    // off execution to the CPU.
    const TOPK_K_CPU_HANDOFF_THRESHOLD = env().getNumber('TOPK_K_CPU_HANDOFF_THRESHOLD');
    const xShape = x.shape;
    const lastDim = xShape[xShape.length - 1];
    if (backend.shouldExecuteOnCPU([x]) ||
        lastDim < TOPK_LAST_DIM_CPU_HANDOFF_SIZE_THRESHOLD ||
        k > TOPK_K_CPU_HANDOFF_THRESHOLD) {
        const xVals = backend.readSync(x.dataId);
        const [allTopKVals, allTopKIndices] = topKImplCPU(xVals, xShape, x.dtype, k, sorted);
        return [
            backend.makeTensorInfo(allTopKVals.shape, allTopKVals.dtype, allTopKVals.values),
            backend.makeTensorInfo(allTopKIndices.shape, allTopKIndices.dtype, allTopKIndices.values)
        ];
    }
    if (k === 0) {
        xShape[xShape.length - 1] = 0;
        return [
            backend.makeTensorInfo(xShape, x.dtype, []),
            backend.makeTensorInfo(xShape, 'int32', [])
        ];
    }
    if (lastDim === 1 /* firstPass */) {
        return [
            x, fill({ attrs: { shape: xShape, dtype: 'int32', value: 0 }, backend })
        ];
    }
    // Eagerly unpack x input since it is passed in to all the shaders which
    // require unpacked inputs.
    const xtexData = backend.texData.get(x.dataId);
    const xIsPacked = xtexData !== null && xtexData.isPacked;
    const xUnPacked = xIsPacked ? backend.unpackTensor(x) : x;
    // Reshape into a 2d tensor [batch, lastDim] and compute topk along lastDim.
    const xSize = util.sizeFromShape(xShape);
    const batch = xSize / lastDim;
    const x2D = reshape({ inputs: { x: xUnPacked }, attrs: { shape: [batch, lastDim] }, backend });
    if (xIsPacked) {
        disposeIntermediateTensorInfoOrNull(backend, xUnPacked);
    }
    const kPow2 = roundUpToPow2(k);
    const lastDimPow2 = roundUpToPow2(lastDim);
    // Only the indices containing the top K are kept at every step to reduce
    // number of outputs in the GPU algorithms, so once the final set of indices
    // is computed then gather is used to grab the corresponding values
    // from the original input.
    let indices = null;
    // GPU algorithm always takes in an indices input but this input is not used
    // on the first run of a GPU algorithm, therefore if indices is null we simply
    // pass in x2D instead of it but the value will not actually be used
    const getInputs = () => indices === null ? [x2D, x2D] : [x2D, indices];
    const runSwap = (dir, inc, shape) => {
        const inputs = getInputs();
        const program = new SwapProgram(shape);
        const fistPass = indices === null ? 1 : 0;
        const customValues = [[lastDim], [fistPass], [Number.NEGATIVE_INFINITY], [dir], [inc]];
        const prevIndices = indices;
        indices = backend.runWebGLProgram(program, inputs, 'int32', customValues);
        disposeIntermediateTensorInfoOrNull(backend, prevIndices);
    };
    // Step 1: local sort
    for (let len = 1; len < kPow2; len *= 2) {
        const dir = len * 2;
        for (let inc = len; inc >= 1; inc /= 2) {
            runSwap(dir, inc, [batch, lastDimPow2]);
        }
    }
    // Step 2: merge
    for (let indicesSize = lastDimPow2; indicesSize > kPow2; indicesSize /= 2) {
        const inputs = getInputs();
        const mergeProgram = new MergeProgram([batch, indicesSize / 2]);
        const firstPass = indices === null ? 1 : 0;
        const customValues = [[lastDim], [firstPass], [kPow2]];
        const prevIndices = indices;
        indices =
            backend.runWebGLProgram(mergeProgram, inputs, 'int32', customValues);
        disposeIntermediateTensorInfoOrNull(backend, prevIndices);
        // Step 3: rebuild
        const len = kPow2 / 2;
        const dir = len * 2;
        for (let inc = len; inc >= 1; inc /= 2) {
            runSwap(dir, inc, indices.shape);
        }
    }
    // Keep only the requested top K results instead of kPow2
    let prevIndices = indices;
    indices = slice({ inputs: { x: indices }, backend, attrs: { begin: 0, size: [batch, k] } });
    disposeIntermediateTensorInfoOrNull(backend, prevIndices);
    // Gather values on last dimension
    let values = gatherV2({ inputs: { x: x2D, indices }, backend, attrs: { axis: 1, batchDims: 1 } });
    disposeIntermediateTensorInfoOrNull(backend, x2D);
    // Reshape back to the original input shape, except that the last
    // dimension is k.
    const newShape = xShape.slice(0, -1);
    newShape.push(k);
    prevIndices = indices;
    indices = reshape({ inputs: { x: indices }, attrs: { shape: newShape }, backend });
    disposeIntermediateTensorInfoOrNull(backend, prevIndices);
    const prevValues = values;
    values = reshape({ inputs: { x: values }, attrs: { shape: newShape }, backend });
    disposeIntermediateTensorInfoOrNull(backend, prevValues);
    return [values, indices];
}
export const topKConfig = {
    kernelName: TopK,
    backendName: 'webgl',
    kernelFunc: topK
};
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiVG9wSy5qcyIsInNvdXJjZVJvb3QiOiIiLCJzb3VyY2VzIjpbIi4uLy4uLy4uLy4uLy4uLy4uL3RmanMtYmFja2VuZC13ZWJnbC9zcmMva2VybmVscy9Ub3BLLnRzIl0sIm5hbWVzIjpbXSwibWFwcGluZ3MiOiJBQUFBOzs7Ozs7Ozs7Ozs7Ozs7R0FlRztBQUVILE9BQU8sRUFBQyxHQUFHLEVBQXlELElBQUksRUFBcUMsSUFBSSxFQUFDLE1BQU0sdUJBQXVCLENBQUM7QUFHaEosT0FBTyxFQUFDLFdBQVcsRUFBQyxNQUFNLHdCQUF3QixDQUFDO0FBQ25ELE9BQU8sRUFBQyxZQUFZLEVBQUUsV0FBVyxFQUFDLE1BQU0sY0FBYyxDQUFDO0FBQ3ZELE9BQU8sRUFBQyxJQUFJLEVBQUMsTUFBTSxRQUFRLENBQUM7QUFDNUIsT0FBTyxFQUFDLFFBQVEsRUFBQyxNQUFNLFlBQVksQ0FBQztBQUNwQyxPQUFPLEVBQUMsT0FBTyxFQUFDLE1BQU0sV0FBVyxDQUFDO0FBQ2xDLE9BQU8sRUFBQyxLQUFLLEVBQUMsTUFBTSxTQUFTLENBQUM7QUFFOUIsU0FBUyxtQ0FBbUMsQ0FDeEMsT0FBeUIsRUFBRSxVQUFzQjtJQUNuRCxJQUFJLFVBQVUsS0FBSyxJQUFJLEVBQUU7UUFDdkIsT0FBTyxDQUFDLDZCQUE2QixDQUFDLFVBQVUsQ0FBQyxDQUFDO0tBQ25EO0FBQ0gsQ0FBQztBQUVELFNBQVMsYUFBYSxDQUFDLEdBQVc7SUFDaEMsSUFBSSxJQUFJLEdBQUcsQ0FBQyxDQUFDO0lBQ2IsT0FBTyxJQUFJLEdBQUcsR0FBRyxFQUFFO1FBQ2pCLElBQUksSUFBSSxDQUFDLENBQUM7S0FDWDtJQUNELE9BQU8sSUFBSSxDQUFDO0FBQ2QsQ0FBQztBQUVELDhDQUE4QztBQUM5Qyw2REFBNkQ7QUFDN0QsTUFBTSxVQUFVLElBQUksQ0FDaEIsSUFBdUU7SUFFekUsTUFBTSxFQUFDLE1BQU0sRUFBRSxPQUFPLEVBQUUsS0FBSyxFQUFDLEdBQUcsSUFBSSxDQUFDO0lBQ3RDLE1BQU0sRUFBQyxDQUFDLEVBQUMsR0FBRyxNQUFNLENBQUM7SUFDbkIsTUFBTSxFQUFDLENBQUMsRUFBRSxNQUFNLEVBQUMsR0FBRyxLQUFLLENBQUM7SUFFMUIsMkVBQTJFO0lBQzNFLG9DQUFvQztJQUNwQyxNQUFNLHdDQUF3QyxHQUMxQyxHQUFHLEVBQUUsQ0FBQyxTQUFTLENBQUMsMENBQTBDLENBQUMsQ0FBQztJQUVoRSw0RUFBNEU7SUFDNUUsNEJBQTRCO0lBQzVCLE1BQU0sNEJBQTRCLEdBQzlCLEdBQUcsRUFBRSxDQUFDLFNBQVMsQ0FBQyw4QkFBOEIsQ0FBQyxDQUFDO0lBRXBELE1BQU0sTUFBTSxHQUFHLENBQUMsQ0FBQyxLQUFLLENBQUM7SUFDdkIsTUFBTSxPQUFPLEdBQUcsTUFBTSxDQUFDLE1BQU0sQ0FBQyxNQUFNLEdBQUcsQ0FBQyxDQUFDLENBQUM7SUFFMUMsSUFBSSxPQUFPLENBQUMsa0JBQWtCLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQztRQUMvQixPQUFPLEdBQUcsd0NBQXdDO1FBQ2xELENBQUMsR0FBRyw0QkFBNEIsRUFBRTtRQUNwQyxNQUFNLEtBQUssR0FBRyxPQUFPLENBQUMsUUFBUSxDQUFDLENBQUMsQ0FBQyxNQUFNLENBQWUsQ0FBQztRQUN2RCxNQUFNLENBQUMsV0FBVyxFQUFFLGNBQWMsQ0FBQyxHQUMvQixXQUFXLENBQUMsS0FBSyxFQUFFLE1BQU0sRUFBRSxDQUFDLENBQUMsS0FBd0IsRUFBRSxDQUFDLEVBQUUsTUFBTSxDQUFDLENBQUM7UUFFdEUsT0FBTztZQUNMLE9BQU8sQ0FBQyxjQUFjLENBQ2xCLFdBQVcsQ0FBQyxLQUFLLEVBQUUsV0FBVyxDQUFDLEtBQUssRUFBRSxXQUFXLENBQUMsTUFBTSxDQUFDO1lBQzdELE9BQU8sQ0FBQyxjQUFjLENBQ2xCLGNBQWMsQ0FBQyxLQUFLLEVBQUUsY0FBYyxDQUFDLEtBQUssRUFBRSxjQUFjLENBQUMsTUFBTSxDQUFDO1NBQ3ZFLENBQUM7S0FDSDtJQUVELElBQUksQ0FBQyxLQUFLLENBQUMsRUFBRTtRQUNYLE1BQU0sQ0FBQyxNQUFNLENBQUMsTUFBTSxHQUFHLENBQUMsQ0FBQyxHQUFHLENBQUMsQ0FBQztRQUM5QixPQUFPO1lBQ0wsT0FBTyxDQUFDLGNBQWMsQ0FBQyxNQUFNLEVBQUUsQ0FBQyxDQUFDLEtBQUssRUFBRSxFQUFFLENBQUM7WUFDM0MsT0FBTyxDQUFDLGNBQWMsQ0FBQyxNQUFNLEVBQUUsT0FBTyxFQUFFLEVBQUUsQ0FBQztTQUM1QyxDQUFDO0tBQ0g7SUFFRCxJQUFJLE9BQU8sS0FBSyxDQUFDLENBQUMsZUFBZSxFQUFFO1FBQ2pDLE9BQU87WUFDTCxDQUFDLEVBQUUsSUFBSSxDQUFDLEVBQUMsS0FBSyxFQUFFLEVBQUMsS0FBSyxFQUFFLE1BQU0sRUFBRSxLQUFLLEVBQUUsT0FBTyxFQUFFLEtBQUssRUFBRSxDQUFDLEVBQUMsRUFBRSxPQUFPLEVBQUMsQ0FBQztTQUNyRSxDQUFDO0tBQ0g7SUFFRCx3RUFBd0U7SUFDeEUsMkJBQTJCO0lBQzNCLE1BQU0sUUFBUSxHQUFHLE9BQU8sQ0FBQyxPQUFPLENBQUMsR0FBRyxDQUFDLENBQUMsQ0FBQyxNQUFNLENBQUMsQ0FBQztJQUMvQyxNQUFNLFNBQVMsR0FBRyxRQUFRLEtBQUssSUFBSSxJQUFJLFFBQVEsQ0FBQyxRQUFRLENBQUM7SUFDekQsTUFBTSxTQUFTLEdBQUcsU0FBUyxDQUFDLENBQUMsQ0FBQyxPQUFPLENBQUMsWUFBWSxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUM7SUFFMUQsNEVBQTRFO0lBQzVFLE1BQU0sS0FBSyxHQUFHLElBQUksQ0FBQyxhQUFhLENBQUMsTUFBTSxDQUFDLENBQUM7SUFDekMsTUFBTSxLQUFLLEdBQUcsS0FBSyxHQUFHLE9BQU8sQ0FBQztJQUM5QixNQUFNLEdBQUcsR0FBRyxPQUFPLENBQ2YsRUFBQyxNQUFNLEVBQUUsRUFBQyxDQUFDLEVBQUUsU0FBUyxFQUFDLEVBQUUsS0FBSyxFQUFFLEVBQUMsS0FBSyxFQUFFLENBQUMsS0FBSyxFQUFFLE9BQU8sQ0FBQyxFQUFDLEVBQUUsT0FBTyxFQUFDLENBQUMsQ0FBQztJQUV6RSxJQUFJLFNBQVMsRUFBRTtRQUNiLG1DQUFtQyxDQUFDLE9BQU8sRUFBRSxTQUFTLENBQUMsQ0FBQztLQUN6RDtJQUVELE1BQU0sS0FBSyxHQUFHLGFBQWEsQ0FBQyxDQUFDLENBQUMsQ0FBQztJQUMvQixNQUFNLFdBQVcsR0FBRyxhQUFhLENBQUMsT0FBTyxDQUFDLENBQUM7SUFFM0MseUVBQXlFO0lBQ3pFLDRFQUE0RTtJQUM1RSxtRUFBbUU7SUFDbkUsMkJBQTJCO0lBQzNCLElBQUksT0FBTyxHQUFlLElBQUksQ0FBQztJQUUvQiw0RUFBNEU7SUFDNUUsOEVBQThFO0lBQzlFLG9FQUFvRTtJQUNwRSxNQUFNLFNBQVMsR0FBRyxHQUFHLEVBQUUsQ0FBQyxPQUFPLEtBQUssSUFBSSxDQUFDLENBQUMsQ0FBQyxDQUFDLEdBQUcsRUFBRSxHQUFHLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxHQUFHLEVBQUUsT0FBTyxDQUFDLENBQUM7SUFFdkUsTUFBTSxPQUFPLEdBQUcsQ0FBQyxHQUFXLEVBQUUsR0FBVyxFQUFFLEtBQWUsRUFBRSxFQUFFO1FBQzVELE1BQU0sTUFBTSxHQUFHLFNBQVMsRUFBRSxDQUFDO1FBQzNCLE1BQU0sT0FBTyxHQUFHLElBQUksV0FBVyxDQUFDLEtBQUssQ0FBQyxDQUFDO1FBQ3ZDLE1BQU0sUUFBUSxHQUFHLE9BQU8sS0FBSyxJQUFJLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDO1FBQzFDLE1BQU0sWUFBWSxHQUNkLENBQUMsQ0FBQyxPQUFPLENBQUMsRUFBRSxDQUFDLFFBQVEsQ0FBQyxFQUFFLENBQUMsTUFBTSxDQUFDLGlCQUFpQixDQUFDLEVBQUUsQ0FBQyxHQUFHLENBQUMsRUFBRSxDQUFDLEdBQUcsQ0FBQyxDQUFDLENBQUM7UUFDdEUsTUFBTSxXQUFXLEdBQUcsT0FBTyxDQUFDO1FBQzVCLE9BQU8sR0FBRyxPQUFPLENBQUMsZUFBZSxDQUFDLE9BQU8sRUFBRSxNQUFNLEVBQUUsT0FBTyxFQUFFLFlBQVksQ0FBQyxDQUFDO1FBQzFFLG1DQUFtQyxDQUFDLE9BQU8sRUFBRSxXQUFXLENBQUMsQ0FBQztJQUM1RCxDQUFDLENBQUM7SUFFRixxQkFBcUI7SUFDckIsS0FBSyxJQUFJLEdBQUcsR0FBRyxDQUFDLEVBQUUsR0FBRyxHQUFHLEtBQUssRUFBRSxHQUFHLElBQUksQ0FBQyxFQUFFO1FBQ3ZDLE1BQU0sR0FBRyxHQUFHLEdBQUcsR0FBRyxDQUFDLENBQUM7UUFDcEIsS0FBSyxJQUFJLEdBQUcsR0FBRyxHQUFHLEVBQUUsR0FBRyxJQUFJLENBQUMsRUFBRSxHQUFHLElBQUksQ0FBQyxFQUFFO1lBQ3RDLE9BQU8sQ0FBQyxHQUFHLEVBQUUsR0FBRyxFQUFFLENBQUMsS0FBSyxFQUFFLFdBQVcsQ0FBQyxDQUFDLENBQUM7U0FDekM7S0FDRjtJQUVELGdCQUFnQjtJQUNoQixLQUFLLElBQUksV0FBVyxHQUFHLFdBQVcsRUFBRSxXQUFXLEdBQUcsS0FBSyxFQUFFLFdBQVcsSUFBSSxDQUFDLEVBQUU7UUFDekUsTUFBTSxNQUFNLEdBQUcsU0FBUyxFQUFFLENBQUM7UUFDM0IsTUFBTSxZQUFZLEdBQUcsSUFBSSxZQUFZLENBQUMsQ0FBQyxLQUFLLEVBQUUsV0FBVyxHQUFHLENBQUMsQ0FBQyxDQUFDLENBQUM7UUFDaEUsTUFBTSxTQUFTLEdBQUcsT0FBTyxLQUFLLElBQUksQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUM7UUFDM0MsTUFBTSxZQUFZLEdBQUcsQ0FBQyxDQUFDLE9BQU8sQ0FBQyxFQUFFLENBQUMsU0FBUyxDQUFDLEVBQUUsQ0FBQyxLQUFLLENBQUMsQ0FBQyxDQUFDO1FBQ3ZELE1BQU0sV0FBVyxHQUFHLE9BQU8sQ0FBQztRQUM1QixPQUFPO1lBQ0gsT0FBTyxDQUFDLGVBQWUsQ0FBQyxZQUFZLEVBQUUsTUFBTSxFQUFFLE9BQU8sRUFBRSxZQUFZLENBQUMsQ0FBQztRQUN6RSxtQ0FBbUMsQ0FBQyxPQUFPLEVBQUUsV0FBVyxDQUFDLENBQUM7UUFFMUQsa0JBQWtCO1FBQ2xCLE1BQU0sR0FBRyxHQUFHLEtBQUssR0FBRyxDQUFDLENBQUM7UUFDdEIsTUFBTSxHQUFHLEdBQUcsR0FBRyxHQUFHLENBQUMsQ0FBQztRQUNwQixLQUFLLElBQUksR0FBRyxHQUFHLEdBQUcsRUFBRSxHQUFHLElBQUksQ0FBQyxFQUFFLEdBQUcsSUFBSSxDQUFDLEVBQUU7WUFDdEMsT0FBTyxDQUFDLEdBQUcsRUFBRSxHQUFHLEVBQUUsT0FBTyxDQUFDLEtBQUssQ0FBQyxDQUFDO1NBQ2xDO0tBQ0Y7SUFFRCx5REFBeUQ7SUFDekQsSUFBSSxXQUFXLEdBQUcsT0FBTyxDQUFDO0lBQzFCLE9BQU8sR0FBRyxLQUFLLENBQ1gsRUFBQyxNQUFNLEVBQUUsRUFBQyxDQUFDLEVBQUUsT0FBTyxFQUFDLEVBQUUsT0FBTyxFQUFFLEtBQUssRUFBRSxFQUFDLEtBQUssRUFBRSxDQUFDLEVBQUUsSUFBSSxFQUFFLENBQUMsS0FBSyxFQUFFLENBQUMsQ0FBQyxFQUFDLEVBQUMsQ0FBQyxDQUFDO0lBQzFFLG1DQUFtQyxDQUFDLE9BQU8sRUFBRSxXQUFXLENBQUMsQ0FBQztJQUUxRCxrQ0FBa0M7SUFDbEMsSUFBSSxNQUFNLEdBQUcsUUFBUSxDQUNqQixFQUFDLE1BQU0sRUFBRSxFQUFDLENBQUMsRUFBRSxHQUFHLEVBQUUsT0FBTyxFQUFDLEVBQUUsT0FBTyxFQUFFLEtBQUssRUFBRSxFQUFDLElBQUksRUFBRSxDQUFDLEVBQUUsU0FBUyxFQUFFLENBQUMsRUFBQyxFQUFDLENBQUMsQ0FBQztJQUMxRSxtQ0FBbUMsQ0FBQyxPQUFPLEVBQUUsR0FBRyxDQUFDLENBQUM7SUFFbEQsaUVBQWlFO0lBQ2pFLGtCQUFrQjtJQUNsQixNQUFNLFFBQVEsR0FBRyxNQUFNLENBQUMsS0FBSyxDQUFDLENBQUMsRUFBRSxDQUFDLENBQUMsQ0FBQyxDQUFDO0lBQ3JDLFFBQVEsQ0FBQyxJQUFJLENBQUMsQ0FBQyxDQUFDLENBQUM7SUFFakIsV0FBVyxHQUFHLE9BQU8sQ0FBQztJQUN0QixPQUFPLEdBQUcsT0FBTyxDQUFDLEVBQUMsTUFBTSxFQUFFLEVBQUMsQ0FBQyxFQUFFLE9BQU8sRUFBQyxFQUFFLEtBQUssRUFBRSxFQUFDLEtBQUssRUFBRSxRQUFRLEVBQUMsRUFBRSxPQUFPLEVBQUMsQ0FBQyxDQUFDO0lBQzdFLG1DQUFtQyxDQUFDLE9BQU8sRUFBRSxXQUFXLENBQUMsQ0FBQztJQUUxRCxNQUFNLFVBQVUsR0FBRyxNQUFNLENBQUM7SUFDMUIsTUFBTSxHQUFHLE9BQU8sQ0FBQyxFQUFDLE1BQU0sRUFBRSxFQUFDLENBQUMsRUFBRSxNQUFNLEVBQUMsRUFBRSxLQUFLLEVBQUUsRUFBQyxLQUFLLEVBQUUsUUFBUSxFQUFDLEVBQUUsT0FBTyxFQUFDLENBQUMsQ0FBQztJQUMzRSxtQ0FBbUMsQ0FBQyxPQUFPLEVBQUUsVUFBVSxDQUFDLENBQUM7SUFFekQsT0FBTyxDQUFDLE1BQU0sRUFBRSxPQUFPLENBQUMsQ0FBQztBQUMzQixDQUFDO0FBRUQsTUFBTSxDQUFDLE1BQU0sVUFBVSxHQUFpQjtJQUN0QyxVQUFVLEVBQUUsSUFBSTtJQUNoQixXQUFXLEVBQUUsT0FBTztJQUNwQixVQUFVLEVBQUUsSUFBNkI7Q0FDMUMsQ0FBQyIsInNvdXJjZXNDb250ZW50IjpbIi8qKlxuICogQGxpY2Vuc2VcbiAqIENvcHlyaWdodCAyMDIwIEdvb2dsZSBMTEMuIEFsbCBSaWdodHMgUmVzZXJ2ZWQuXG4gKiBMaWNlbnNlZCB1bmRlciB0aGUgQXBhY2hlIExpY2Vuc2UsIFZlcnNpb24gMi4wICh0aGUgXCJMaWNlbnNlXCIpO1xuICogeW91IG1heSBub3QgdXNlIHRoaXMgZmlsZSBleGNlcHQgaW4gY29tcGxpYW5jZSB3aXRoIHRoZSBMaWNlbnNlLlxuICogWW91IG1heSBvYnRhaW4gYSBjb3B5IG9mIHRoZSBMaWNlbnNlIGF0XG4gKlxuICogaHR0cDovL3d3dy5hcGFjaGUub3JnL2xpY2Vuc2VzL0xJQ0VOU0UtMi4wXG4gKlxuICogVW5sZXNzIHJlcXVpcmVkIGJ5IGFwcGxpY2FibGUgbGF3IG9yIGFncmVlZCB0byBpbiB3cml0aW5nLCBzb2Z0d2FyZVxuICogZGlzdHJpYnV0ZWQgdW5kZXIgdGhlIExpY2Vuc2UgaXMgZGlzdHJpYnV0ZWQgb24gYW4gXCJBUyBJU1wiIEJBU0lTLFxuICogV0lUSE9VVCBXQVJSQU5USUVTIE9SIENPTkRJVElPTlMgT0YgQU5ZIEtJTkQsIGVpdGhlciBleHByZXNzIG9yIGltcGxpZWQuXG4gKiBTZWUgdGhlIExpY2Vuc2UgZm9yIHRoZSBzcGVjaWZpYyBsYW5ndWFnZSBnb3Zlcm5pbmcgcGVybWlzc2lvbnMgYW5kXG4gKiBsaW1pdGF0aW9ucyB1bmRlciB0aGUgTGljZW5zZS5cbiAqID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09XG4gKi9cblxuaW1wb3J0IHtlbnYsIEtlcm5lbENvbmZpZywgS2VybmVsRnVuYywgTnVtZXJpY0RhdGFUeXBlLCBUZW5zb3JJbmZvLCBUb3BLLCBUb3BLQXR0cnMsIFRvcEtJbnB1dHMsIFR5cGVkQXJyYXksIHV0aWx9IGZyb20gJ0B0ZW5zb3JmbG93L3RmanMtY29yZSc7XG5cbmltcG9ydCB7TWF0aEJhY2tlbmRXZWJHTH0gZnJvbSAnLi4vYmFja2VuZF93ZWJnbCc7XG5pbXBvcnQge3RvcEtJbXBsQ1BVfSBmcm9tICcuLi9rZXJuZWxfdXRpbHMvc2hhcmVkJztcbmltcG9ydCB7TWVyZ2VQcm9ncmFtLCBTd2FwUHJvZ3JhbX0gZnJvbSAnLi4vdG9wX2tfZ3B1JztcbmltcG9ydCB7ZmlsbH0gZnJvbSAnLi9GaWxsJztcbmltcG9ydCB7Z2F0aGVyVjJ9IGZyb20gJy4vR2F0aGVyVjInO1xuaW1wb3J0IHtyZXNoYXBlfSBmcm9tICcuL1Jlc2hhcGUnO1xuaW1wb3J0IHtzbGljZX0gZnJvbSAnLi9TbGljZSc7XG5cbmZ1bmN0aW9uIGRpc3Bvc2VJbnRlcm1lZGlhdGVUZW5zb3JJbmZvT3JOdWxsKFxuICAgIGJhY2tlbmQ6IE1hdGhCYWNrZW5kV2ViR0wsIHRlbnNvckluZm86IFRlbnNvckluZm8pIHtcbiAgaWYgKHRlbnNvckluZm8gIT09IG51bGwpIHtcbiAgICBiYWNrZW5kLmRpc3Bvc2VJbnRlcm1lZGlhdGVUZW5zb3JJbmZvKHRlbnNvckluZm8pO1xuICB9XG59XG5cbmZ1bmN0aW9uIHJvdW5kVXBUb1BvdzIobnVtOiBudW1iZXIpIHtcbiAgbGV0IHBvdzIgPSAxO1xuICB3aGlsZSAocG93MiA8IG51bSkge1xuICAgIHBvdzIgKj0gMjtcbiAgfVxuICByZXR1cm4gcG93Mjtcbn1cblxuLy8gQmFzZWQgb24gQWxnb3JpdGhtIDIgb2YgQml0b25pYyBUb3AgSywgcmVmOlxuLy8gaHR0cHM6Ly9hbmlsc2hhbmJoYWcuaW4vc3RhdGljL3BhcGVycy9ncHV0b3BrX3NpZ21vZDE4LnBkZlxuZXhwb3J0IGZ1bmN0aW9uIHRvcEsoXG4gICAgYXJnczoge2lucHV0czogVG9wS0lucHV0cywgYmFja2VuZDogTWF0aEJhY2tlbmRXZWJHTCwgYXR0cnM6IFRvcEtBdHRyc30pOlxuICAgIFRlbnNvckluZm9bXSB7XG4gIGNvbnN0IHtpbnB1dHMsIGJhY2tlbmQsIGF0dHJzfSA9IGFyZ3M7XG4gIGNvbnN0IHt4fSA9IGlucHV0cztcbiAgY29uc3Qge2ssIHNvcnRlZH0gPSBhdHRycztcblxuICAvLyBFbXBpcmljYWxseSBkZXRlcm1pbmVkIGNvbnN0YW50IHVzZWQgdG8gZGV0ZXJtaW5lIGxhc3QgZGltIHRocmVzaG9sZCBmb3JcbiAgLy8gaGFuZGluZyBvZmYgZXhlY3V0aW9uIHRvIHRoZSBDUFUuXG4gIGNvbnN0IFRPUEtfTEFTVF9ESU1fQ1BVX0hBTkRPRkZfU0laRV9USFJFU0hPTEQgPVxuICAgICAgZW52KCkuZ2V0TnVtYmVyKCdUT1BLX0xBU1RfRElNX0NQVV9IQU5ET0ZGX1NJWkVfVEhSRVNIT0xEJyk7XG5cbiAgLy8gRW1waXJpY2FsbHkgZGV0ZXJtaW5lZCBjb25zdGFudCB1c2VkIHRvIGRldGVybWluZSBrIHRocmVzaG9sZCBmb3IgaGFuZGluZ1xuICAvLyBvZmYgZXhlY3V0aW9uIHRvIHRoZSBDUFUuXG4gIGNvbnN0IFRPUEtfS19DUFVfSEFORE9GRl9USFJFU0hPTEQgPVxuICAgICAgZW52KCkuZ2V0TnVtYmVyKCdUT1BLX0tfQ1BVX0hBTkRPRkZfVEhSRVNIT0xEJyk7XG5cbiAgY29uc3QgeFNoYXBlID0geC5zaGFwZTtcbiAgY29uc3QgbGFzdERpbSA9IHhTaGFwZVt4U2hhcGUubGVuZ3RoIC0gMV07XG5cbiAgaWYgKGJhY2tlbmQuc2hvdWxkRXhlY3V0ZU9uQ1BVKFt4XSkgfHxcbiAgICAgIGxhc3REaW0gPCBUT1BLX0xBU1RfRElNX0NQVV9IQU5ET0ZGX1NJWkVfVEhSRVNIT0xEIHx8XG4gICAgICBrID4gVE9QS19LX0NQVV9IQU5ET0ZGX1RIUkVTSE9MRCkge1xuICAgIGNvbnN0IHhWYWxzID0gYmFja2VuZC5yZWFkU3luYyh4LmRhdGFJZCkgYXMgVHlwZWRBcnJheTtcbiAgICBjb25zdCBbYWxsVG9wS1ZhbHMsIGFsbFRvcEtJbmRpY2VzXSA9XG4gICAgICAgIHRvcEtJbXBsQ1BVKHhWYWxzLCB4U2hhcGUsIHguZHR5cGUgYXMgTnVtZXJpY0RhdGFUeXBlLCBrLCBzb3J0ZWQpO1xuXG4gICAgcmV0dXJuIFtcbiAgICAgIGJhY2tlbmQubWFrZVRlbnNvckluZm8oXG4gICAgICAgICAgYWxsVG9wS1ZhbHMuc2hhcGUsIGFsbFRvcEtWYWxzLmR0eXBlLCBhbGxUb3BLVmFscy52YWx1ZXMpLFxuICAgICAgYmFja2VuZC5tYWtlVGVuc29ySW5mbyhcbiAgICAgICAgICBhbGxUb3BLSW5kaWNlcy5zaGFwZSwgYWxsVG9wS0luZGljZXMuZHR5cGUsIGFsbFRvcEtJbmRpY2VzLnZhbHVlcylcbiAgICBdO1xuICB9XG5cbiAgaWYgKGsgPT09IDApIHtcbiAgICB4U2hhcGVbeFNoYXBlLmxlbmd0aCAtIDFdID0gMDtcbiAgICByZXR1cm4gW1xuICAgICAgYmFja2VuZC5tYWtlVGVuc29ySW5mbyh4U2hhcGUsIHguZHR5cGUsIFtdKSxcbiAgICAgIGJhY2tlbmQubWFrZVRlbnNvckluZm8oeFNoYXBlLCAnaW50MzInLCBbXSlcbiAgICBdO1xuICB9XG5cbiAgaWYgKGxhc3REaW0gPT09IDEgLyogZmlyc3RQYXNzICovKSB7XG4gICAgcmV0dXJuIFtcbiAgICAgIHgsIGZpbGwoe2F0dHJzOiB7c2hhcGU6IHhTaGFwZSwgZHR5cGU6ICdpbnQzMicsIHZhbHVlOiAwfSwgYmFja2VuZH0pXG4gICAgXTtcbiAgfVxuXG4gIC8vIEVhZ2VybHkgdW5wYWNrIHggaW5wdXQgc2luY2UgaXQgaXMgcGFzc2VkIGluIHRvIGFsbCB0aGUgc2hhZGVycyB3aGljaFxuICAvLyByZXF1aXJlIHVucGFja2VkIGlucHV0cy5cbiAgY29uc3QgeHRleERhdGEgPSBiYWNrZW5kLnRleERhdGEuZ2V0KHguZGF0YUlkKTtcbiAgY29uc3QgeElzUGFja2VkID0geHRleERhdGEgIT09IG51bGwgJiYgeHRleERhdGEuaXNQYWNrZWQ7XG4gIGNvbnN0IHhVblBhY2tlZCA9IHhJc1BhY2tlZCA/IGJhY2tlbmQudW5wYWNrVGVuc29yKHgpIDogeDtcblxuICAvLyBSZXNoYXBlIGludG8gYSAyZCB0ZW5zb3IgW2JhdGNoLCBsYXN0RGltXSBhbmQgY29tcHV0ZSB0b3BrIGFsb25nIGxhc3REaW0uXG4gIGNvbnN0IHhTaXplID0gdXRpbC5zaXplRnJvbVNoYXBlKHhTaGFwZSk7XG4gIGNvbnN0IGJhdGNoID0geFNpemUgLyBsYXN0RGltO1xuICBjb25zdCB4MkQgPSByZXNoYXBlKFxuICAgICAge2lucHV0czoge3g6IHhVblBhY2tlZH0sIGF0dHJzOiB7c2hhcGU6IFtiYXRjaCwgbGFzdERpbV19LCBiYWNrZW5kfSk7XG5cbiAgaWYgKHhJc1BhY2tlZCkge1xuICAgIGRpc3Bvc2VJbnRlcm1lZGlhdGVUZW5zb3JJbmZvT3JOdWxsKGJhY2tlbmQsIHhVblBhY2tlZCk7XG4gIH1cblxuICBjb25zdCBrUG93MiA9IHJvdW5kVXBUb1BvdzIoayk7XG4gIGNvbnN0IGxhc3REaW1Qb3cyID0gcm91bmRVcFRvUG93MihsYXN0RGltKTtcblxuICAvLyBPbmx5IHRoZSBpbmRpY2VzIGNvbnRhaW5pbmcgdGhlIHRvcCBLIGFyZSBrZXB0IGF0IGV2ZXJ5IHN0ZXAgdG8gcmVkdWNlXG4gIC8vIG51bWJlciBvZiBvdXRwdXRzIGluIHRoZSBHUFUgYWxnb3JpdGhtcywgc28gb25jZSB0aGUgZmluYWwgc2V0IG9mIGluZGljZXNcbiAgLy8gaXMgY29tcHV0ZWQgdGhlbiBnYXRoZXIgaXMgdXNlZCB0byBncmFiIHRoZSBjb3JyZXNwb25kaW5nIHZhbHVlc1xuICAvLyBmcm9tIHRoZSBvcmlnaW5hbCBpbnB1dC5cbiAgbGV0IGluZGljZXM6IFRlbnNvckluZm8gPSBudWxsO1xuXG4gIC8vIEdQVSBhbGdvcml0aG0gYWx3YXlzIHRha2VzIGluIGFuIGluZGljZXMgaW5wdXQgYnV0IHRoaXMgaW5wdXQgaXMgbm90IHVzZWRcbiAgLy8gb24gdGhlIGZpcnN0IHJ1biBvZiBhIEdQVSBhbGdvcml0aG0sIHRoZXJlZm9yZSBpZiBpbmRpY2VzIGlzIG51bGwgd2Ugc2ltcGx5XG4gIC8vIHBhc3MgaW4geDJEIGluc3RlYWQgb2YgaXQgYnV0IHRoZSB2YWx1ZSB3aWxsIG5vdCBhY3R1YWxseSBiZSB1c2VkXG4gIGNvbnN0IGdldElucHV0cyA9ICgpID0+IGluZGljZXMgPT09IG51bGwgPyBbeDJELCB4MkRdIDogW3gyRCwgaW5kaWNlc107XG5cbiAgY29uc3QgcnVuU3dhcCA9IChkaXI6IG51bWJlciwgaW5jOiBudW1iZXIsIHNoYXBlOiBudW1iZXJbXSkgPT4ge1xuICAgIGNvbnN0IGlucHV0cyA9IGdldElucHV0cygpO1xuICAgIGNvbnN0IHByb2dyYW0gPSBuZXcgU3dhcFByb2dyYW0oc2hhcGUpO1xuICAgIGNvbnN0IGZpc3RQYXNzID0gaW5kaWNlcyA9PT0gbnVsbCA/IDEgOiAwO1xuICAgIGNvbnN0IGN1c3RvbVZhbHVlcyA9XG4gICAgICAgIFtbbGFzdERpbV0sIFtmaXN0UGFzc10sIFtOdW1iZXIuTkVHQVRJVkVfSU5GSU5JVFldLCBbZGlyXSwgW2luY11dO1xuICAgIGNvbnN0IHByZXZJbmRpY2VzID0gaW5kaWNlcztcbiAgICBpbmRpY2VzID0gYmFja2VuZC5ydW5XZWJHTFByb2dyYW0ocHJvZ3JhbSwgaW5wdXRzLCAnaW50MzInLCBjdXN0b21WYWx1ZXMpO1xuICAgIGRpc3Bvc2VJbnRlcm1lZGlhdGVUZW5zb3JJbmZvT3JOdWxsKGJhY2tlbmQsIHByZXZJbmRpY2VzKTtcbiAgfTtcblxuICAvLyBTdGVwIDE6IGxvY2FsIHNvcnRcbiAgZm9yIChsZXQgbGVuID0gMTsgbGVuIDwga1BvdzI7IGxlbiAqPSAyKSB7XG4gICAgY29uc3QgZGlyID0gbGVuICogMjtcbiAgICBmb3IgKGxldCBpbmMgPSBsZW47IGluYyA+PSAxOyBpbmMgLz0gMikge1xuICAgICAgcnVuU3dhcChkaXIsIGluYywgW2JhdGNoLCBsYXN0RGltUG93Ml0pO1xuICAgIH1cbiAgfVxuXG4gIC8vIFN0ZXAgMjogbWVyZ2VcbiAgZm9yIChsZXQgaW5kaWNlc1NpemUgPSBsYXN0RGltUG93MjsgaW5kaWNlc1NpemUgPiBrUG93MjsgaW5kaWNlc1NpemUgLz0gMikge1xuICAgIGNvbnN0IGlucHV0cyA9IGdldElucHV0cygpO1xuICAgIGNvbnN0IG1lcmdlUHJvZ3JhbSA9IG5ldyBNZXJnZVByb2dyYW0oW2JhdGNoLCBpbmRpY2VzU2l6ZSAvIDJdKTtcbiAgICBjb25zdCBmaXJzdFBhc3MgPSBpbmRpY2VzID09PSBudWxsID8gMSA6IDA7XG4gICAgY29uc3QgY3VzdG9tVmFsdWVzID0gW1tsYXN0RGltXSwgW2ZpcnN0UGFzc10sIFtrUG93Ml1dO1xuICAgIGNvbnN0IHByZXZJbmRpY2VzID0gaW5kaWNlcztcbiAgICBpbmRpY2VzID1cbiAgICAgICAgYmFja2VuZC5ydW5XZWJHTFByb2dyYW0obWVyZ2VQcm9ncmFtLCBpbnB1dHMsICdpbnQzMicsIGN1c3RvbVZhbHVlcyk7XG4gICAgZGlzcG9zZUludGVybWVkaWF0ZVRlbnNvckluZm9Pck51bGwoYmFja2VuZCwgcHJldkluZGljZXMpO1xuXG4gICAgLy8gU3RlcCAzOiByZWJ1aWxkXG4gICAgY29uc3QgbGVuID0ga1BvdzIgLyAyO1xuICAgIGNvbnN0IGRpciA9IGxlbiAqIDI7XG4gICAgZm9yIChsZXQgaW5jID0gbGVuOyBpbmMgPj0gMTsgaW5jIC89IDIpIHtcbiAgICAgIHJ1blN3YXAoZGlyLCBpbmMsIGluZGljZXMuc2hhcGUpO1xuICAgIH1cbiAgfVxuXG4gIC8vIEtlZXAgb25seSB0aGUgcmVxdWVzdGVkIHRvcCBLIHJlc3VsdHMgaW5zdGVhZCBvZiBrUG93MlxuICBsZXQgcHJldkluZGljZXMgPSBpbmRpY2VzO1xuICBpbmRpY2VzID0gc2xpY2UoXG4gICAgICB7aW5wdXRzOiB7eDogaW5kaWNlc30sIGJhY2tlbmQsIGF0dHJzOiB7YmVnaW46IDAsIHNpemU6IFtiYXRjaCwga119fSk7XG4gIGRpc3Bvc2VJbnRlcm1lZGlhdGVUZW5zb3JJbmZvT3JOdWxsKGJhY2tlbmQsIHByZXZJbmRpY2VzKTtcblxuICAvLyBHYXRoZXIgdmFsdWVzIG9uIGxhc3QgZGltZW5zaW9uXG4gIGxldCB2YWx1ZXMgPSBnYXRoZXJWMihcbiAgICAgIHtpbnB1dHM6IHt4OiB4MkQsIGluZGljZXN9LCBiYWNrZW5kLCBhdHRyczoge2F4aXM6IDEsIGJhdGNoRGltczogMX19KTtcbiAgZGlzcG9zZUludGVybWVkaWF0ZVRlbnNvckluZm9Pck51bGwoYmFja2VuZCwgeDJEKTtcblxuICAvLyBSZXNoYXBlIGJhY2sgdG8gdGhlIG9yaWdpbmFsIGlucHV0IHNoYXBlLCBleGNlcHQgdGhhdCB0aGUgbGFzdFxuICAvLyBkaW1lbnNpb24gaXMgay5cbiAgY29uc3QgbmV3U2hhcGUgPSB4U2hhcGUuc2xpY2UoMCwgLTEpO1xuICBuZXdTaGFwZS5wdXNoKGspO1xuXG4gIHByZXZJbmRpY2VzID0gaW5kaWNlcztcbiAgaW5kaWNlcyA9IHJlc2hhcGUoe2lucHV0czoge3g6IGluZGljZXN9LCBhdHRyczoge3NoYXBlOiBuZXdTaGFwZX0sIGJhY2tlbmR9KTtcbiAgZGlzcG9zZUludGVybWVkaWF0ZVRlbnNvckluZm9Pck51bGwoYmFja2VuZCwgcHJldkluZGljZXMpO1xuXG4gIGNvbnN0IHByZXZWYWx1ZXMgPSB2YWx1ZXM7XG4gIHZhbHVlcyA9IHJlc2hhcGUoe2lucHV0czoge3g6IHZhbHVlc30sIGF0dHJzOiB7c2hhcGU6IG5ld1NoYXBlfSwgYmFja2VuZH0pO1xuICBkaXNwb3NlSW50ZXJtZWRpYXRlVGVuc29ySW5mb09yTnVsbChiYWNrZW5kLCBwcmV2VmFsdWVzKTtcblxuICByZXR1cm4gW3ZhbHVlcywgaW5kaWNlc107XG59XG5cbmV4cG9ydCBjb25zdCB0b3BLQ29uZmlnOiBLZXJuZWxDb25maWcgPSB7XG4gIGtlcm5lbE5hbWU6IFRvcEssXG4gIGJhY2tlbmROYW1lOiAnd2ViZ2wnLFxuICBrZXJuZWxGdW5jOiB0b3BLIGFzIHVua25vd24gYXMgS2VybmVsRnVuY1xufTtcbiJdfQ==