compiler/translator/gen_builtin_symbols.py

#!/usr/bin/env vpython3
#
# [VPYTHON:BEGIN]
# wheel: <
#   name: "infra/python/wheels/perfect-hash-py2_py3"
#   version: "version:0.2.1"
# >
# [VPYTHON:END]
#
# Copyright 2018 The ANGLE Project Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
#
# gen_builtin_symbols.py:
#  Code generation for the built-in symbol tables.
import sys

# Conditional import enables getting inputs/outputs with python3 instead of vpython3
if len(sys.argv) < 2:
    from perfect_hash import generate_hash, Hash2

from collections import OrderedDict
import argparse
import copy
import hashlib
import json
import re
import os
import random

template_immutablestring_cpp = """// GENERATED FILE - DO NOT EDIT.
// Generated by {script_name} using data from {variable_data_source_name} and
// {function_data_source_name}.
//
// Copyright 2020 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// ImmutableString_autogen.cpp: Wrapper for static or pool allocated char arrays, that are guaranteed to be
// valid and unchanged for the duration of the compilation.
// Implements mangledNameHash using perfect hash function from gen_builtin_symbols.py

#include "compiler/translator/ImmutableString.h"

namespace sh {{

std::ostream &operator<<(std::ostream &os, const ImmutableString &str)
{{
    return os.write(str.data(), str.length());
}}

}}

#if defined(_MSC_VER)
#    pragma warning(disable : 4309)  // truncation of constant value
#endif


namespace
{{

constexpr int mangledkT1[] = {{{mangled_S1}}};
constexpr int mangledkT2[] = {{{mangled_S2}}};
constexpr int mangledkG[] = {{{mangled_G}}};

int MangledHashG(const char *key, const int *T)
{{
    int sum = 0;

    for (int i = 0; key[i] != '\\0'; i++)
    {{
        sum += T[i] * key[i];
        sum %= {mangled_NG};
    }}
    return mangledkG[sum];
}}

int MangledPerfectHash(const char *key)
{{
    if (strlen(key) > {mangled_NS})
        return 0;

    return (MangledHashG(key, mangledkT1) + MangledHashG(key, mangledkT2)) % {mangled_NG};
}}

constexpr int unmangledkT1[] = {{{unmangled_S1}}};
constexpr int unmangledkT2[] = {{{unmangled_S2}}};
constexpr int unmangledkG[] = {{{unmangled_G}}};

int UnmangledHashG(const char *key, const int *T)
{{
    int sum = 0;

    for (int i = 0; key[i] != '\\0'; i++)
    {{
        sum += T[i] * key[i];
        sum %= {unmangled_NG};
    }}
    return unmangledkG[sum];
}}

int UnmangledPerfectHash(const char *key)
{{
    if (strlen(key) > {unmangled_NS})
        return 0;

    return (UnmangledHashG(key, unmangledkT1) + UnmangledHashG(key, unmangledkT2)) % {unmangled_NG};
}}

}}

namespace sh
{{

template <>
const size_t ImmutableString::FowlerNollVoHash<4>::kFnvPrime = 16777619u;

template <>
const size_t ImmutableString::FowlerNollVoHash<4>::kFnvOffsetBasis = 0x811c9dc5u;

template <>
const size_t ImmutableString::FowlerNollVoHash<8>::kFnvPrime =
    static_cast<size_t>(1099511628211ull);

template <>
const size_t ImmutableString::FowlerNollVoHash<8>::kFnvOffsetBasis =
    static_cast<size_t>(0xcbf29ce484222325ull);

uint32_t ImmutableString::mangledNameHash() const
{{
    return MangledPerfectHash(data());
}}

uint32_t ImmutableString::unmangledNameHash() const
{{
    return UnmangledPerfectHash(data());
}}

}}  // namespace sh
"""

template_immutablestringtest_cpp = """// GENERATED FILE - DO NOT EDIT.
// Generated by {script_name} using data from {function_data_source_name}.
//
// Copyright 2020 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// ImmutableString_test_autogen.cpp:
//   Tests for matching script-generated hashes with runtime computed hashes.

#include "compiler/translator/ImmutableString.h"
#include "gtest/gtest.h"

namespace sh
{{

TEST(ImmutableStringTest, ScriptGeneratedHashesMatch)
{{
{script_generated_hash_tests}
{unmangled_script_generated_hash_tests}
}}

}}  // namespace sh
"""

# The header file has a "get" function for each variable. They are used in traversers.
# It also declares id values of built-ins with human readable names, so they can be used to identify built-ins.
template_builtin_header = """// GENERATED FILE - DO NOT EDIT.
// Generated by {script_name} using data from {variable_data_source_name} and
// {function_data_source_name}.
//
// Copyright 2020 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// BuiltIn_autogen.h:
//   Compile-time initialized built-ins.

#ifndef COMPILER_TRANSLATOR_TREEUTIL_BUILTIN_AUTOGEN_H_
#define COMPILER_TRANSLATOR_TREEUTIL_BUILTIN_AUTOGEN_H_

#include "compiler/translator/SymbolUniqueId.h"

namespace sh
{{

class TVariable;

class BuiltInId
{{
public:

{builtin_id_declarations}

}};  // class BuiltInId

namespace BuiltInVariable
{{

{get_variable_declarations}

}}  // namespace BuiltInVariable

}}  // namespace sh

#endif  // COMPILER_TRANSLATOR_TREEUTIL_BUILTIN_AUTOGEN_H_
"""

template_symboltable_header = """// GENERATED FILE - DO NOT EDIT.
// Generated by {script_name} using data from {variable_data_source_name} and
// {function_data_source_name}.
//
// Copyright 2020 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// SymbolTable_autogen.h:
//   Autogenerated member variables of TSymbolTable.

#ifndef COMPILER_TRANSLATOR_SYMBOLTABLE_AUTOGEN_H_
#define COMPILER_TRANSLATOR_SYMBOLTABLE_AUTOGEN_H_

namespace sh
{{

class TSymbolTableBase
{{
  public:
    TSymbolTableBase() = default;
{declare_member_variables}
}};

}}  // namespace sh

#endif  // COMPILER_TRANSLATOR_SYMBOLTABLE_AUTOGEN_H_
"""

# By having the variables defined in a cpp file we ensure that there's just one instance of each of the declared variables.
template_symboltable_cpp = """// GENERATED FILE - DO NOT EDIT.
// Generated by {script_name} using data from {variable_data_source_name} and
// {function_data_source_name}.
//
// Copyright 2020 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// SymbolTable_autogen.cpp:
//   Compile-time initialized built-ins.

#include "compiler/translator/SymbolTable.h"

#include "angle_gl.h"
#include "compiler/translator/tree_util/BuiltIn.h"
#include "compiler/translator/ImmutableString.h"
#include "compiler/translator/StaticType.h"
#include "compiler/translator/Symbol.h"
#include "compiler/translator/SymbolTable.h"

namespace sh
{{
using Resources = ShBuiltInResources;
using TableBase = TSymbolTableBase;

struct SymbolIdChecker
{{
    static_assert(TSymbolTable::kFirstUserDefinedSymbolId > {last_builtin_id});
}};

namespace BuiltInName
{{

constexpr const ImmutableString _empty("");
{name_declarations}

}}  // namespace BuiltInName

// TODO(oetuaho): Would be nice to make this a class instead of a namespace so that we could friend
// this from TVariable. Now symbol constructors taking an id have to be public even though they're
// not supposed to be accessible from outside of here. http://anglebug.com/42261100
namespace BuiltInVariable
{{

{type_array_sizes_declarations}

{variable_declarations}

{get_variable_definitions}

}}  // namespace BuiltInVariable

namespace BuiltInParameters
{{

{parameter_declarations}

}}  // namespace BuiltInParameters

// TODO(oetuaho): Would be nice to make this a class instead of a namespace so that we could friend
// this from TFunction. Now symbol constructors taking an id have to be public even though they're
// not supposed to be accessible from outside of here. http://anglebug.com/42261100
namespace Func
{{

{function_declarations}

}}  // namespace Func

namespace BuiltInArray
{{
using namespace Func;
using Rule = SymbolRule;

// Rules used to initialize the mangled name array.
constexpr SymbolRule kRules[] = {{
{mangled_rules}
}};

// Flat array of all mangled names.
constexpr const char *kMangledNames[] = {{
{mangled_names_array}
}};

// Flat array of offsets from a symbol into the rules table.
constexpr uint16_t kMangledOffsets[] = {{
{mangled_offsets_array}
}};

using Ext = TExtension;

// Flat array of all unmangled name identifiers.
constexpr UnmangledEntry unmangled[] = {{
{unmangled_array}
}};

}}

void TSymbolTable::initializeBuiltInVariables(sh::GLenum shaderType,
                                              ShShaderSpec spec,
                                              const ShBuiltInResources &resources)
{{
    const TSourceLoc zeroSourceLoc = {{0, 0, 0, 0}};
{init_member_variables}
}}

namespace
{{
uint16_t GetNextRuleIndex(uint32_t nameHash)
{{
    if (nameHash == {num_mangled_names} - 1)
        return ArraySize(BuiltInArray::kRules);
    return BuiltInArray::kMangledOffsets[nameHash + 1];
}}
}}  // namespace

const TSymbol *TSymbolTable::findBuiltIn(const ImmutableString &name,
                                         int shaderVersion) const
{{
    if (name.length() > {max_mangled_name_length})
        return nullptr;

    uint32_t nameHash = name.mangledNameHash();
    if (nameHash >= {num_mangled_names})
        return nullptr;

    const char *actualName = BuiltInArray::kMangledNames[nameHash];
    if (name != actualName)
        return nullptr;

    uint16_t startIndex = BuiltInArray::kMangledOffsets[nameHash];
    uint16_t nextIndex = GetNextRuleIndex(nameHash);

    return FindMangledBuiltIn(mShaderSpec, shaderVersion, mShaderType, mResources, *this, BuiltInArray::kRules, startIndex, nextIndex);
}}

bool TSymbolTable::isUnmangledBuiltInName(const ImmutableString &name,
                                          int shaderVersion,
                                          const TExtensionBehavior &extensions) const
{{
    if (name.length() > {max_unmangled_name_length})
        return false;

    uint32_t nameHash = name.unmangledNameHash();
    if (nameHash >= {num_unmangled_names})
        return false;

    return BuiltInArray::unmangled[nameHash].matches(name, mShaderSpec, shaderVersion, mShaderType, extensions);
}}

}}  // namespace sh
"""

template_operator_header = """// GENERATED FILE - DO NOT EDIT.
// Generated by {script_name} using data from {function_data_source_name}.
//
// Copyright 2021 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// Operator_autogen.h:
//   Operators used by the high-level (parse tree) representation.

#ifndef COMPILER_TRANSLATOR_OPERATOR_AUTOGEN_H_
#define COMPILER_TRANSLATOR_OPERATOR_AUTOGEN_H_

#include <stdint.h>

namespace sh
{{

enum TOperator : uint16_t
{{
    EOpNull,  // if in a node, should only mean a node is still being built

    // Call a function defined in the AST. This might be a user-defined function or a function
    // inserted by an AST transformation.
    EOpCallFunctionInAST,

    // Call an internal helper function with a raw implementation - the implementation can't be
    // subject to AST transformations. Raw functions have a few constraints to keep them compatible
    // with AST traversers:
    // * They should not return arrays.
    // * They should not have out parameters.
    //
    // DEPRECATED; DO NOT USE.  TODO: remove this.  http://anglebug.com/42264589
    //
    EOpCallInternalRawFunction,

    //
    // Branch (TIntermBranch)
    //

    EOpKill,  // Fragment only
    EOpReturn,
    EOpBreak,
    EOpContinue,

    //
    // Constructor (TIntermAggregate)
    //

    EOpConstruct,

    //
    // Unary operators with special GLSL syntax (TIntermUnary).
    //

    EOpNegative,
    EOpPositive,
    EOpLogicalNot,
    EOpBitwiseNot,

    EOpPostIncrement,
    EOpPostDecrement,
    EOpPreIncrement,
    EOpPreDecrement,

    EOpArrayLength,

    //
    // Binary operators with special GLSL syntax (TIntermBinary).
    //

    EOpAdd,
    EOpSub,
    EOpMul,
    EOpDiv,
    EOpIMod,

    EOpEqual,
    EOpNotEqual,
    EOpLessThan,
    EOpGreaterThan,
    EOpLessThanEqual,
    EOpGreaterThanEqual,

    EOpComma,

    EOpVectorTimesScalar,
    EOpVectorTimesMatrix,
    EOpMatrixTimesVector,
    EOpMatrixTimesScalar,
    EOpMatrixTimesMatrix,

    EOpLogicalOr,
    EOpLogicalXor,
    EOpLogicalAnd,

    EOpBitShiftLeft,
    EOpBitShiftRight,

    EOpBitwiseAnd,
    EOpBitwiseXor,
    EOpBitwiseOr,

    EOpIndexDirect,
    EOpIndexIndirect,
    EOpIndexDirectStruct,
    EOpIndexDirectInterfaceBlock,

    //
    // Moves (TIntermBinary)
    //

    EOpAssign,
    EOpInitialize,
    EOpAddAssign,
    EOpSubAssign,

    EOpMulAssign,
    EOpVectorTimesMatrixAssign,
    EOpVectorTimesScalarAssign,
    EOpMatrixTimesScalarAssign,
    EOpMatrixTimesMatrixAssign,

    EOpDivAssign,
    EOpIModAssign,
    EOpBitShiftLeftAssign,
    EOpBitShiftRightAssign,
    EOpBitwiseAndAssign,
    EOpBitwiseXorAssign,
    EOpBitwiseOrAssign,

    // Not an op, but a marker for the start of built-in ops.
    EOpLastNonBuiltIn = EOpBitwiseOrAssign,

    //
    // Built-in functions mapped to operators (either unary (TIntermUnary) or with multiple
    // parameters (TIntermAggregate))
    //
    {operator_enum_declarations}
}};

// Returns the string corresponding to the operator in GLSL.  For built-in functions use the
// function name directly.
const char *GetOperatorString(TOperator op);

// Say whether or not a binary or unary operation changes the value of a variable.
bool IsAssignment(TOperator op);

namespace BuiltInGroup
{{
static inline bool IsBuiltIn(TOperator op)
{{
    return op > EOpLastNonBuiltIn;
}}
{is_in_group_definitions}
}}  // namespace BuiltInGroup

}}  // namespace sh

#endif  // COMPILER_TRANSLATOR_OPERATOR_AUTOGEN_H_

"""

template_rule = """Rule::Get<{version}, {shaders}, {extension}>({symbol_or_var})"""

basic_types_enumeration = [
    'Void',
    'Float',
    'Int',
    'UInt',
    'Bool',
    'AtomicCounter',
    'YuvCscStandardEXT',
    'Sampler2D',
    'Sampler3D',
    'SamplerCube',
    'Sampler2DArray',
    'SamplerExternalOES',
    'SamplerExternal2DY2YEXT',
    'Sampler2DRect',
    'Sampler2DMS',
    'Sampler2DMSArray',
    'ISampler2D',
    'ISampler3D',
    'ISamplerCube',
    'ISampler2DArray',
    'ISampler2DMS',
    'ISampler2DMSArray',
    'USampler2D',
    'USampler3D',
    'USamplerCube',
    'USampler2DArray',
    'USampler2DMS',
    'USampler2DMSArray',
    'Sampler2DShadow',
    'SamplerCubeShadow',
    'Sampler2DArrayShadow',
    'SamplerBuffer',
    'SamplerCubeArray',
    'SamplerCubeArrayShadow',
    'Sampler2DRectShadow',
    'ISampler2DRect',
    'ISamplerBuffer',
    'ISamplerCubeArray',
    'USampler2DRect',
    'USamplerBuffer',
    'USamplerCubeArray',
    'SamplerVideoWEBGL',
    'Image2D',
    'Image3D',
    'Image2DArray',
    'ImageCube',
    'Image2DMS',
    'Image2DMSArray',
    'ImageCubeArray',
    'ImageRect',
    'ImageBuffer',
    'IImage2D',
    'IImage3D',
    'IImage2DArray',
    'IImageCube',
    'IImage2DMS',
    'IImage2DMSArray',
    'IImageCubeArray',
    'IImageRect',
    'IImageBuffer',
    'UImage2D',
    'UImage3D',
    'UImage2DArray',
    'UImageCube',
    'UImage2DMS',
    'UImage2DMSArray',
    'UImageCubeArray',
    'UImageRect',
    'UImageBuffer',
    'PixelLocalANGLE',
    'IPixelLocalANGLE',
    'UPixelLocalANGLE',
    'SubpassInput',
    'ISubpassInput',
    'USubpassInput',
]

id_counter = 0


def set_working_dir():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    os.chdir(script_dir)


def get_basic_mangled_name(basic):
    index = basic_types_enumeration.index(basic)
    if index < 26:
        return '0' + chr(ord('A') + index)
    if index < 52:
        return '0' + chr(ord('a') + index - 26)
    if index < 78:
        return '1' + chr(ord('A') + index - 52)
    return '1' + chr(ord('a') + index - 78)


essl_levels = [
    'ESSL3_2_BUILTINS', 'ESSL3_1_BUILTINS', 'ESSL3_BUILTINS', 'ESSL1_BUILTINS', 'COMMON_BUILTINS',
    'ESSL_INTERNAL_BACKEND_BUILTINS'
]


def generate_suffix_from_level(level):
    assert (level[:4] == 'ESSL')
    assert (level[-9:] == '_BUILTINS')

    # Turn XYSLN_M_BUILTINS to XYN_M
    return level[:2] + level[4:-9]


def get_essl_shader_version_for_level(level):
    if level == None:
        return '-1'
    elif level == 'ESSL_INTERNAL_BACKEND_BUILTINS':
        return 'kESSLInternalBackendBuiltIns'
    elif level == 'ESSL3_2_BUILTINS':
        return '320'
    elif level == 'ESSL3_1_BUILTINS':
        return '310'
    elif level == 'ESSL3_BUILTINS':
        return '300'
    elif level == 'ESSL1_BUILTINS':
        return '100'
    elif level == 'COMMON_BUILTINS':
        return '0'
    else:
        raise Exception('Unsupported symbol table level')


def get_shader_version_for_level(level):
    return get_essl_shader_version_for_level(level)


def get_extension_list(extensions):
    extension_list = [ext.strip() for ext in extensions.split(',')]
    extension_string = ', '.join(['TExtension::' + ext for ext in extension_list])
    return 'std::array<TExtension, ' + str(len(extension_list)) + 'u>{{' + extension_string + '}}'


class GroupedList:
    """"Class for storing a list of objects grouped by symbol table level and condition."""

    def __init__(self, hashfn, num_names):
        self.objs = OrderedDict()
        self.max_name_length = 0
        self.hashfn = hashfn
        self.num_names = num_names
        self.rule_offset = 0

    def add_entry(self, essl_level, shader_type, name, symbol, essl_extension,
                  script_generated_hash_tests):
        if essl_level not in essl_levels:
            raise Exception('Unexpected essl level: ' + str(essl_level))
        if len(name) > self.max_name_length:
            self.max_name_length = len(name)

        name_hash = mangledNameHash(name, self.hashfn, script_generated_hash_tests, False)
        if name_hash not in self.objs:
            self.objs[name_hash] = OrderedDict()

        self.objs[name_hash]['name'] = name

        if essl_extension == 'UNDEFINED':
            if 'symbol' in self.objs[name_hash] and self.objs[name_hash]['symbol'] != symbol:
                # Adding a variable that is part of two ESSL extensions that have become core
                if 'symbol2' not in self.objs[name_hash]:
                    self.objs[name_hash]['essl_level2'] = essl_level
                    self.objs[name_hash]['symbol2'] = symbol
                    self.objs[name_hash]['shader_type2'] = shader_type
                elif 'symbol3' not in self.objs[name_hash]:
                    self.objs[name_hash]['essl_level3'] = essl_level
                    self.objs[name_hash]['symbol3'] = symbol
                    self.objs[name_hash]['shader_type3'] = shader_type
                elif 'symbol4' not in self.objs[name_hash]:
                    self.objs[name_hash]['essl_level4'] = essl_level
                    self.objs[name_hash]['symbol4'] = symbol
                    self.objs[name_hash]['shader_type4'] = shader_type
                else:
                    assert (False)
            else:
                self.objs[name_hash]['essl_level'] = essl_level
                self.objs[name_hash]['symbol'] = symbol
                self.objs[name_hash]['shader_type'] = shader_type

        if essl_extension != 'UNDEFINED':
            if ('essl_ext_symbol' in self.objs[name_hash] and
                    self.objs[name_hash]['essl_ext_symbol'] != symbol):
                # Adding a variable that is part of two ESSL extensions
                if 'essl_ext_symbol2' not in self.objs[name_hash]:
                    self.objs[name_hash]['essl_extension2'] = essl_extension
                    self.objs[name_hash]['essl_ext_level2'] = essl_level
                    self.objs[name_hash]['essl_ext_symbol2'] = symbol
                    self.objs[name_hash]['essl_ext_shader_type2'] = shader_type
                elif 'essl_ext_symbol3' not in self.objs[name_hash]:
                    self.objs[name_hash]['essl_extension3'] = essl_extension
                    self.objs[name_hash]['essl_ext_level3'] = essl_level
                    self.objs[name_hash]['essl_ext_symbol3'] = symbol
                    self.objs[name_hash]['essl_ext_shader_type3'] = shader_type
                elif 'essl_ext_symbol4' not in self.objs[name_hash]:
                    self.objs[name_hash]['essl_extension4'] = essl_extension
                    self.objs[name_hash]['essl_ext_level4'] = essl_level
                    self.objs[name_hash]['essl_ext_symbol4'] = symbol
                    self.objs[name_hash]['essl_ext_shader_type4'] = shader_type
                else:
                    assert (False)
            else:
                self.objs[name_hash]['essl_extension'] = essl_extension
                self.objs[name_hash]['essl_ext_level'] = essl_level
                self.objs[name_hash]['essl_ext_symbol'] = symbol
                self.objs[name_hash]['essl_ext_shader_type'] = shader_type

    def get_max_name_length(self):
        return self.max_name_length

    def format_rule(self, rule):
        return template_rule.format(**rule)

    def format_rules(self, rules):
        return ", ".join([self.format_rule(rule) for rule in rules])

    def get_rules(self):
        return self.rules

    def get_names(self):
        return self.names

    def get_offsets(self):
        return self.offsets

    def update_arrays(self):

        def add_rule(rules, level, shaders, extension, symbol):
            var = ("&TableBase::%s" % symbol) if symbol.startswith("m_gl") else None

            extension_list = []
            versionField = get_shader_version_for_level(level)
            shadersField = "Shader::%s" % ("ALL" if shaders == "NONE" else shaders)
            symbolOrVarField = symbol.replace("Func::", "") if var is None else var
            if extension != None:
                extension_list = [ext.strip() for ext in extension.split(',')]
                for ext in extension_list:
                    rules.append({
                        "version": versionField,
                        "shaders": shadersField,
                        "extension": "0" if ext == None else "EXT_INDEX(%s)" % ext,
                        "symbol_or_var": symbolOrVarField
                    })
            else:
                rules.append({
                    "version": versionField,
                    "shaders": shadersField,
                    "extension": "0",
                    "symbol_or_var": symbolOrVarField
                })

        self.names = []
        self.offsets = []
        self.rules = []
        for hash_val in range(0, self.num_names):
            if hash_val in self.objs:
                data = self.objs[hash_val]

                rules = []

                if "symbol" in data and "essl_level" in data:
                    add_rule(rules, data['essl_level'], data['shader_type'], None, data["symbol"])

                if "symbol2" in data and "essl_level2" in data:
                    add_rule(rules, data['essl_level2'], data['shader_type2'], None,
                             data["symbol2"])

                if "symbol3" in data and "essl_level3" in data:
                    add_rule(rules, data['essl_level3'], data['shader_type3'], None,
                             data["symbol3"])

                if "symbol4" in data and "essl_level4" in data:
                    add_rule(rules, data['essl_level4'], data['shader_type4'], None,
                             data["symbol4"])

                if "essl_ext_symbol" in data:
                    add_rule(rules, data["essl_ext_level"], data["essl_ext_shader_type"],
                             data["essl_extension"], data["essl_ext_symbol"])

                if "essl_ext_symbol2" in data:
                    add_rule(rules, data["essl_ext_level2"], data["essl_ext_shader_type2"],
                             data["essl_extension2"], data["essl_ext_symbol2"])

                if "essl_ext_symbol3" in data:
                    add_rule(rules, data["essl_ext_level3"], data["essl_ext_shader_type3"],
                             data["essl_extension3"], data["essl_ext_symbol3"])

                if "essl_ext_symbol4" in data:
                    add_rule(rules, data["essl_ext_level4"], data["essl_ext_shader_type4"],
                             data["essl_extension4"], data["essl_ext_symbol4"])

                name = data['name']
                name_underscore = name.replace("(", "_")

                self.names.append('"%s"' % name)
                self.offsets.append("%d, // %s" % (self.rule_offset, name_underscore))
                self.rules.append("%s" % self.format_rules(rules))

                self.rule_offset += len(rules)

            else:
                self.names.append('""')
                self.offsets.append('%d, // Empty' % self.rule_offset)


class UnmangledGroupedList:
    """"Class for storing a list of unmangled objects grouped by symbol table level and condition."""

    def __init__(self, hashfn, num_names):
        self.objs = OrderedDict()
        self.max_name_length = 0
        self.hashfn = hashfn
        self.num_names = num_names

    def add_entry(self, essl_level, shader_type, name, essl_ext, essl_extension,
                  unmangled_script_generated_hash_tests):
        if essl_level not in essl_levels:
            raise Exception('Unexpected essl level: ' + str(essl_level))
        if len(name) > self.max_name_length:
            self.max_name_length = len(name)

        name_hash = mangledNameHash(name, self.hashfn, unmangled_script_generated_hash_tests, True)
        self.objs[name_hash] = OrderedDict()
        self.objs[name_hash]['name'] = name
        self.objs[name_hash]['essl_level'] = essl_level
        self.objs[name_hash]['shader_type'] = shader_type
        self.objs[name_hash]['essl_ext'] = essl_ext
        self.objs[name_hash]['essl_extension'] = essl_extension

    def has_key(self, essl_level, shader_type, name):
        name_hash = mangledNameHash(name, self.hashfn, None, True, False)
        if name_hash not in self.objs:
            return False
        entry = self.objs[name_hash]
        if entry['essl_level'] != essl_level:
            return False
        if entry['shader_type'] != shader_type:
            return False
        return True

    def get(self, essl_level, shader_type, name):
        if self.has_key(essl_level, shader_type, name):
            name_hash = mangledNameHash(name, self.hashfn, None, True, False)
            return self.objs[name_hash]
        return None

    def get_max_name_length(self):
        return self.max_name_length

    def get_array(self):
        code = []
        for hash_val in range(0, self.num_names):
            obj = self.objs[hash_val]
            essl_level = obj['essl_level']
            shader_type = 'Shader::' + obj['shader_type'] if obj[
                'shader_type'] != 'NONE' else 'Shader::ALL'
            data = []
            data.append('"{name}"'.format(name=obj['name']))
            essl_extensions = [ext.strip() for ext in obj['essl_extension'].split(',')]
            template_extensions = 'std::array<TExtension, {count}>{{{{{extensions}}}}}'
            data.append(
                template_extensions.format(
                    count=len(essl_extensions),
                    extensions=','.join(['Ext::' + ext for ext in essl_extensions])))
            data.append(get_essl_shader_version_for_level(essl_level))
            data.append(shader_type)

            code.append('{%s}' % ', '.join(data))
        return code


class TType:

    def __init__(self, glsl_header_type):
        if isinstance(glsl_header_type, str):
            self.data = self.parse_type(glsl_header_type)
        else:
            self.data = glsl_header_type
        self.normalize()

    def normalize(self):
        # Note that this will set primarySize and secondarySize also on genTypes. In that case they
        # are overridden when the specific types are generated.
        if 'primarySize' not in self.data:
            if ('secondarySize' in self.data):
                raise Exception(
                    'Unexpected secondarySize on type that does not have primarySize set')
            self.data['primarySize'] = 1
        if 'secondarySize' not in self.data:
            self.data['secondarySize'] = 1
        if 'precision' not in self.data:
            self.data['precision'] = 'Undefined'
        if 'qualifier' not in self.data:
            self.data['qualifier'] = 'Global'

    def has_array_size(self):
        return 'arraySize' in self.data

    def get_statictype_string(self):
        template_type = 'StaticType::Get<Ebt{basic}, Ebp{precision}, Evq{qualifier}, {primarySize}, {secondarySize}>()'
        if self.has_array_size():
            template_type = 'StaticType::GetArray<Ebt{basic}, Ebp{precision}, Evq{qualifier}, {primarySize}, {secondarySize}, kArraySize{arraySize}, 1>()'
        return template_type.format(**self.data)

    def get_dynamic_type_string(self):
        template_type = 'new TType(Ebt{basic}, Ebp{precision}, Evq{qualifier}, {primarySize}, {secondarySize}'
        if self.has_array_size():
            template_type += ', TVector<unsigned int>{{{arraySize}}}'
        template_type += ')'
        return template_type.format(**self.data)

    def get_mangled_name(self):
        mangled_name = ''

        size_key = (self.data['secondarySize'] - 1) * 4 + self.data['primarySize'] - 1
        if size_key < 10:
            mangled_name += chr(ord('0') + size_key)
        else:
            mangled_name += chr(ord('A') + size_key - 10)
        mangled_name += get_basic_mangled_name(self.data['basic'])
        if self.has_array_size():
            mangled_name += 'x' + str(self.data['arraySize'])
        return mangled_name

    def get_human_readable_name(self):
        name = self.data['basic']
        if self.has_array_size():
            name = str(self.data['arraySize']) + 'x' + name
        name += str(self.data['primarySize'])
        if self.data['secondarySize'] > 1:
            name += 'x' + str(self.data['secondarySize'])
        return name

    def is_vector(self):
        return self.data['primarySize'] > 1 and self.data['secondarySize'] == 1

    def is_matrix(self):
        return self.data['secondarySize'] > 1

    def get_object_size(self):
        return self.data['primarySize'] * self.data['secondarySize']

    def specific_sampler_or_image_or_subpass_type(self, basic_type_prefix):
        if 'genType' in self.data and self.data['genType'] == 'sampler_or_image_or_subpass':
            type = {}
            if 'basic' not in self.data:
                type['basic'] = {'': 'Float', 'I': 'Int', 'U': 'UInt'}[basic_type_prefix]
                type['primarySize'] = self.data['primarySize']
            else:
                type['basic'] = basic_type_prefix + self.data['basic']
                type['primarySize'] = 1
            type['precision'] = 'Undefined'
            return TType(type)
        return self

    def specific_type(self, vec_size):
        type = {}
        if 'genType' in self.data:
            type['basic'] = self.data['basic']
            type['precision'] = self.data['precision']
            type['qualifier'] = self.data['qualifier']
            type['primarySize'] = vec_size
            type['secondarySize'] = 1
            return TType(type)
        return self

    def parse_type(self, glsl_header_type):
        # TODO(http://anglebug.com/42262477): handle readonly, writeonly qualifiers
        if glsl_header_type.startswith('readonly writeonly '):
            type_obj = self.parse_type(glsl_header_type[19:])
            type_obj['qualifier'] = 'Readonly Writeonly'
            return type_obj
        if glsl_header_type.startswith('readonly '):
            type_obj = self.parse_type(glsl_header_type[9:])
            type_obj['qualifier'] = 'Readonly'
            return type_obj
        if glsl_header_type.startswith('writeonly '):
            type_obj = self.parse_type(glsl_header_type[10:])
            type_obj['qualifier'] = 'Writeonly'
            return type_obj
        if glsl_header_type.startswith('out '):
            type_obj = self.parse_type(glsl_header_type[4:])
            type_obj['qualifier'] = 'ParamOut'
            return type_obj
        if glsl_header_type.startswith('inout '):
            type_obj = self.parse_type(glsl_header_type[6:])
            type_obj['qualifier'] = 'ParamInOut'
            return type_obj

        basic_type_map = {
            'float': 'Float',
            'int': 'Int',
            'uint': 'UInt',
            'bool': 'Bool',
            'void': 'Void',
            'atomic_uint': 'AtomicCounter',
            'yuvCscStandardEXT': 'YuvCscStandardEXT'
        }

        if glsl_header_type in basic_type_map:
            return {'basic': basic_type_map[glsl_header_type]}

        type_obj = {}

        basic_type_prefix_map = {'': 'Float', 'i': 'Int', 'u': 'UInt', 'b': 'Bool', 'v': 'Void'}

        vec_re = re.compile(r'^([iudb]?)vec([234]?)((\[[234]\])?)$')
        vec_match = vec_re.match(glsl_header_type)
        if vec_match:
            type_obj['basic'] = basic_type_prefix_map[vec_match.group(1)]
            if vec_match.group(2) == '':
                # Type like "ivec" that represents either ivec2, ivec3 or ivec4
                type_obj['genType'] = 'vec'
            else:
                # vec with specific size
                if vec_match.group(3) != '':
                    # vec array
                    type_obj['primarySize'] = int(vec_match.group(2))
                    type_obj['arraySize'] = int(vec_match.group(3)[1])
                else:
                    type_obj['primarySize'] = int(vec_match.group(2))
            return type_obj

        mat_re = re.compile(r'^mat([234])(x([234]))?$')
        mat_match = mat_re.match(glsl_header_type)
        if mat_match:
            type_obj['basic'] = 'Float'
            if len(glsl_header_type) == 4:
                mat_size = int(mat_match.group(1))
                type_obj['primarySize'] = mat_size
                type_obj['secondarySize'] = mat_size
            else:
                type_obj['primarySize'] = int(mat_match.group(1))
                type_obj['secondarySize'] = int(mat_match.group(3))
            return type_obj

        gen_re = re.compile(r'^gen([IUDB]?)Type$')
        gen_match = gen_re.match(glsl_header_type)
        if gen_match:
            type_obj['basic'] = basic_type_prefix_map[gen_match.group(1).lower()]
            type_obj['genType'] = 'yes'
            return type_obj

        if glsl_header_type.startswith('sampler'):
            type_obj['basic'] = glsl_header_type[0].upper() + glsl_header_type[1:]
            return type_obj

        if glsl_header_type.startswith('gsampler') or \
           glsl_header_type.startswith('gimage') or \
           glsl_header_type.startswith('gpixelLocal') or \
           glsl_header_type.startswith('gsubpassInput'):
            type_obj['basic'] = glsl_header_type[1].upper() + glsl_header_type[2:]
            type_obj['genType'] = 'sampler_or_image_or_subpass'
            return type_obj

        if glsl_header_type == 'gvec4':
            return {'primarySize': 4, 'genType': 'sampler_or_image_or_subpass'}
        if glsl_header_type == 'gvec3':
            return {'primarySize': 3, 'genType': 'sampler_or_image_or_subpass'}

        if glsl_header_type == 'IMAGE_PARAMS':
            return {'genType': 'image_params'}

        raise Exception('Unrecognized type: ' + str(glsl_header_type))


class SymbolsData:

    def __init__(self):

        # Declarations of symbol unique ids
        self.builtin_id_declarations = []

        # Declarations of name string variables
        self.name_declarations = set()

        # Code for testing that script-generated hashes match with runtime computed hashes.
        self.script_generated_hash_tests = OrderedDict()
        self.unmangled_script_generated_hash_tests = OrderedDict()


class VariablesData:

    def __init__(self):

        # Code for defining TVariables stored as members of TSymbolTable.
        self.declare_member_variables = []
        self.init_member_variables = []

        # Declarations of static array sizes if any builtin TVariable is array.
        self.type_array_sizes_declarations = set()

        # Declarations of builtin TVariables
        self.variable_declarations = []

        # Functions for querying the pointer to a specific TVariable.
        self.get_variable_declarations = []
        self.get_variable_definitions = []


class FunctionsData:

    def __init__(self):

        # Declarations of builtin TFunctions
        self.function_declarations = []

        # TOperator enum values (and grouping comments) for built-in functions.
        self.operator_list = dict()
        self.operator_enum_declarations = []

        # Functions for testing whether a builtin belongs in group.
        self.is_in_group_definitions = []

        # Declarations of parameter arrays for builtin TFunctions. Map from C++ variable name to the
        # full declaration.
        self.parameter_declarations = {}

        self.defined_function_variants = set()
        self.defined_parameter_names = set()

    def find_op(self, search_index, direction, limit_for_assertion):

        while True:
            # Make sure the group is not empty.  An "opSuffix" must be used to distinguish between
            # built-ins with the same name, but in different groups.
            assert (search_index != limit_for_assertion)

            line = self.operator_enum_declarations[search_index].lstrip()
            if line.startswith('EOp'):
                return line[:line.index(',')]
            search_index += direction


class HashFunction:

    def __init__(self, f1, f2, G):
        self.f1 = f1
        self.f2 = f2
        self.G = G

    def hash(self, key):
        return (self.G[self.f1(key)] + self.G[self.f2(key)]) % len(self.G)


def get_parsed_functions(functions_txt_filename):

    def parse_function_parameters(parameters):
        if parameters == '':
            return []
        parametersOut = []
        parameters = parameters.split(', ')
        for parameter in parameters:
            parametersOut.append(TType(parameter.strip()))
        return parametersOut

    lines = []
    with open(functions_txt_filename) as f:
        lines = f.readlines()
    lines = [
        line.strip() for line in lines if line.strip() != '' and not line.strip().startswith('//')
    ]

    fun_re = re.compile(r'^(\w+) (\w+)\((.*)\);$')

    parsed_functions = OrderedDict()
    group_stack = []
    default_metadata = {}

    for line in lines:
        if line.startswith('GROUP BEGIN '):
            group_rest = line[12:].strip()
            group_parts = group_rest.split(' ', 1)
            current_group = {'functions': [], 'name': group_parts[0], 'subgroups': {}}
            if len(group_parts) > 1:
                group_metadata = json.loads(group_parts[1])
                current_group.update(group_metadata)
            group_stack.append(current_group)
        elif line.startswith('GROUP END '):
            group_end_name = line[10:].strip()
            current_group = group_stack[-1]
            if current_group['name'] != group_end_name:
                raise Exception('GROUP END: Unexpected function group name "' + group_end_name +
                                '" was expecting "' + current_group['name'] + '"')
            group_stack.pop()
            is_top_level_group = (len(group_stack) == 0)
            if is_top_level_group:
                if current_group['name'] in parsed_functions:
                    raise Exception('GROUP END: Duplicate group name "%s"' % current_group['name'])
                parsed_functions[current_group['name']] = current_group
                default_metadata = {}
            else:
                super_group = group_stack[-1]
                super_group['subgroups'][current_group['name']] = current_group
        elif line.startswith('DEFAULT METADATA'):
            line_rest = line[16:].strip()
            default_metadata = json.loads(line_rest)
        else:
            fun_match = fun_re.match(line)
            if fun_match:
                return_type = fun_match.group(1)
                name = fun_match.group(2)
                parameters = fun_match.group(3)
                function_props = {
                    'name': name,
                    'returnType': TType(return_type),
                    'parameters': parse_function_parameters(parameters)
                }
                function_props.update(default_metadata)
                if 'essl_level' in function_props:
                    group_stack[-1]['functions'].append(function_props)
            else:
                raise Exception('Unexpected function input line: ' + line)

    return parsed_functions


def mangledNameHash(str, hashfn, script_generated_hash_tests, unmangled, save_test=True):
    hash = hashfn.hash(str)
    if save_test:
        confidence_check = ''
        if unmangled:
            confidence_check = '    ASSERT_EQ(0x{hash}u, ImmutableString("{str}").unmangledNameHash());'.format(
                hash=('%08x' % hash), str=str)
        else:
            confidence_check = '    ASSERT_EQ(0x{hash}u, ImmutableString("{str}").mangledNameHash());'.format(
                hash=('%08x' % hash), str=str)
        script_generated_hash_tests.update({confidence_check: None})
    return hash


def get_function_names(group, mangled_names, unmangled_names):
    if 'functions' in group:
        for function_props in group['functions']:
            function_name = function_props['name']
            unmangled_names.append(function_name)
            function_variants = gen_function_variants(function_props)
            for function_props in function_variants:
                parameters = get_parameters(function_props)
                mangled_names.append(get_function_mangled_name(function_name, parameters))
    if 'subgroups' in group:
        for subgroup_name, subgroup in group['subgroups'].items():
            get_function_names(subgroup, mangled_names, unmangled_names)


def get_variable_names(group, mangled_names):
    if 'variables' in group:
        for variable_name, props in group['variables'].items():
            mangled_names.append(variable_name)
    if 'subgroups' in group:
        for subgroup_name, subgroup in group['subgroups'].items():
            get_variable_names(subgroup, mangled_names)


def get_suffix(props):
    if 'suffix' in props:
        return props['suffix']
    return ''


def get_essl_extension(props):
    if 'essl_extension' in props:
        return props['essl_extension']
    return 'UNDEFINED'


def get_op(name, function_props, group_op_suffix):
    return 'EOp' + name[0].upper() + name[1:] + group_op_suffix + function_props.get(
        'opSuffix', '')


def get_known_to_not_have_side_effects(function_props):
    if 'hasSideEffects' in function_props:
        has_side_effects = function_props['hasSideEffects']
        if isinstance(has_side_effects, str):
            assert has_side_effects in ['true',
                                        'false'], 'Bad side effects value: ' + has_side_effects
            has_side_effects = has_side_effects == 'true'
        assert isinstance(has_side_effects, bool)
        return 'false' if has_side_effects else 'true'
    else:
        for param in get_parameters(function_props):
            if 'qualifier' in param.data and (param.data['qualifier'] == 'ParamOut' or
                                              param.data['qualifier'] == 'ParamInOut'):
                return 'false'
        return 'true'


def get_parameters(function_props):
    if 'parameters' in function_props:
        return function_props['parameters']
    return []


def get_function_mangled_name(function_name, parameters):
    mangled_name = function_name + '('
    for param in parameters:
        mangled_name += param.get_mangled_name()
    return mangled_name


def get_function_human_readable_name(function_name, parameters):
    name = function_name
    for param in parameters:
        name += '_' + param.get_human_readable_name()
    return name


def get_unique_identifier_name(function_name, parameters):
    unique_name = function_name + '_'
    for param in parameters:
        unique_name += param.get_mangled_name()
    return unique_name


def get_variable_name_to_store_parameter(param):
    unique_name = 'pt'
    if 'qualifier' in param.data:
        if param.data['qualifier'] == 'ParamOut':
            unique_name += '_o_'
        if param.data['qualifier'] == 'ParamInOut':
            unique_name += '_io_'
    unique_name += param.get_mangled_name()
    return unique_name


def get_variable_name_to_store_parameters(parameters):
    if len(parameters) == 0:
        return 'empty'
    unique_name = 'p'
    for param in parameters:
        if 'qualifier' in param.data:
            if param.data['qualifier'] == 'ParamOut':
                unique_name += '_o_'
            if param.data['qualifier'] == 'ParamInOut':
                unique_name += '_io_'
        unique_name += param.get_mangled_name()
    return unique_name


def define_constexpr_type_array_sizes(template_args, type_array_sizes_declarations):
    template_array_sizes_declaration = 'constexpr const unsigned int kArraySize{arraySize}[1] = {{{arraySize}}};'
    type_array_sizes_declarations.add(template_array_sizes_declaration.format(**template_args))


def define_constexpr_variable(template_args, variable_declarations):
    template_args['extension'] = get_extension_list(template_args['extension'])
    template_variable_declaration = 'constexpr const TVariable k{name_with_suffix}(BuiltInId::{name_with_suffix}, BuiltInName::{name}, SymbolType::BuiltIn, {extension}, {type});'

    variable_declarations.append(template_variable_declaration.format(**template_args))


def gen_function_variants(function_props):
    function_variants = []
    parameters = get_parameters(function_props)
    function_is_gen_type = False
    gen_type = set()
    image_params_index = 0
    for param in parameters + [function_props['returnType']]:
        if 'genType' in param.data:
            if param.data['genType'] not in [
                    'sampler_or_image_or_subpass', 'vec', 'yes', 'image_params'
            ]:
                raise Exception(
                    'Unexpected value of genType "' + str(param.data['genType']) +
                    '" should be "sampler_or_image_or_subpass", "vec", "yes", or "image_params"')
            gen_type.add(param.data['genType'])
            if param.data['genType'] == 'image_params':
                image_params_index = parameters.index(param)

    if len(gen_type) == 0:
        function_variants.append(function_props)
        return function_variants

    # If we have image_params then we're generating variants for 33 separate functions,
    # each for a different type of image variable
    if 'image_params' in gen_type:
        variants = [['gimage2D', 'ivec2'], ['gimage3D', 'ivec3'], ['gimageCube', 'ivec3'],
                    ['gimageBuffer', 'int'], ['gimage2DArray', 'ivec3'],
                    ['gimageCubeArray', 'ivec3'], ['gimageRect', 'ivec2'],
                    ['gimage2DMS', 'ivec2', 'int'], ['gimage2DMSArray', 'ivec3', 'int']]
        for variant in variants:
            image_variant_parameters = []
            for param in parameters:
                if parameters.index(param) == image_params_index:
                    for variant_param in variant:
                        image_variant_parameters.append(TType(variant_param))
                else:
                    image_variant_parameters.append(param)
            types = ['', 'I', 'U']
            for type in types:
                variant_props = function_props.copy()
                variant_parameters = []
                for param in image_variant_parameters:
                    variant_parameters.append(
                        param.specific_sampler_or_image_or_subpass_type(type))
                variant_props['parameters'] = variant_parameters
                variant_props['returnType'] = function_props[
                    'returnType'].specific_sampler_or_image_or_subpass_type(type)
                function_variants.append(variant_props)
        return function_variants

    # If we have a gsampler_or_image_or_subpass then we're generating variants for float, int and uint
    # samplers.
    if 'sampler_or_image_or_subpass' in gen_type:
        types = ['', 'I', 'U']
        for type in types:
            variant_props = function_props.copy()
            variant_parameters = []
            for param in parameters:
                variant_parameters.append(param.specific_sampler_or_image_or_subpass_type(type))
            variant_props['parameters'] = variant_parameters
            variant_props['returnType'] = function_props[
                'returnType'].specific_sampler_or_image_or_subpass_type(type)
            function_variants.append(variant_props)
        return function_variants

    # If we have a normal gentype then we're generating variants for different sizes of vectors.
    sizes = range(1, 5)
    if 'vec' in gen_type:
        sizes = range(2, 5)
    for size in sizes:
        variant_props = function_props.copy()
        variant_parameters = []
        for param in parameters:
            variant_parameters.append(param.specific_type(size))
        variant_props['parameters'] = variant_parameters
        variant_props['returnType'] = function_props['returnType'].specific_type(size)
        function_variants.append(variant_props)
    return function_variants


def process_single_function(shader_type, group_name, function_props, symbols, variables, functions,
                            group_op_suffix, unmangled_function_if_statements, mangled_builtins):
    global id_counter

    function_name = function_props['name']
    essl_level = function_props['essl_level'] if 'essl_level' in function_props else None
    essl_extension = get_essl_extension(function_props)
    op = get_op(function_name, function_props, group_op_suffix)
    template_args = {
        'name': function_name,
        'name_with_suffix': function_name + get_suffix(function_props),
        'essl_level': essl_level,
        'essl_extension': essl_extension,
        'extension': essl_extension,
        'op': op,
        'known_to_not_have_side_effects': get_known_to_not_have_side_effects(function_props)
    }

    function_variants = gen_function_variants(function_props)

    template_name_declaration = 'constexpr const ImmutableString {name_with_suffix}("{name}");'
    name_declaration = template_name_declaration.format(**template_args)
    if not name_declaration in symbols.name_declarations:
        symbols.name_declarations.add(name_declaration)

    essl_ext = '{essl_extension}'.format(**template_args)
    unmangled_builtin_no_shader_type = unmangled_function_if_statements.get(
        essl_level, 'NONE', function_name)
    if unmangled_builtin_no_shader_type != None and unmangled_builtin_no_shader_type[
            'essl_extension'] == 'UNDEFINED':
        # We already have this unmangled name without a shader type nor extension on the same level.
        # No need to add a duplicate with a type.
        pass
    elif (not unmangled_function_if_statements.has_key(essl_level, shader_type, function_name)
         ) or (unmangled_builtin_no_shader_type and
               (essl_extension == 'UNDEFINED' and
                unmangled_builtin_no_shader_type['essl_extension'] != 'UNDEFINED')):
        unmangled_function_if_statements.add_entry(essl_level, shader_type, function_name,
                                                   essl_ext, essl_extension,
                                                   symbols.unmangled_script_generated_hash_tests)

    extension_string = get_extension_list(template_args['extension'])

    if op not in functions.operator_list:
        functions.operator_list[op] = group_name
        is_unary = group_name.startswith('Math') and len(get_parameters(function_variants[0])) == 1
        assert (not is_unary or
                all([len(get_parameters(props)) == 1 for props in function_variants]))

        template_operator_enum = '    {op},{is_unary_comment}'
        template_args['is_unary_comment'] = '  // Unary' if is_unary else ''

        functions.operator_enum_declarations.append(template_operator_enum.format(**template_args))
    else:
        # Ensure that built-ins in different groups don't generate the same op.  The Is<Group> query
        # functions rely on this.
        previous_group_name = functions.operator_list[op]
        if group_name != previous_group_name:
            print('Op ' + op + ' found in group ' + group_name + ' but was previously in group ' +
                  previous_group_name)
        assert (group_name == previous_group_name)

    for function_props in function_variants:
        template_args['id'] = id_counter

        parameters = get_parameters(function_props)

        template_args['unique_name'] = get_unique_identifier_name(
            template_args['name_with_suffix'], parameters)
        template_args['param_count'] = len(parameters)
        template_args['return_type'] = function_props['returnType'].get_statictype_string()
        template_args['mangled_name'] = get_function_mangled_name(function_name, parameters)
        template_args['human_readable_name'] = get_function_human_readable_name(
            template_args['name_with_suffix'], parameters)
        template_args['mangled_name_length'] = len(template_args['mangled_name'])

        symbol = '&Func::{unique_name}'.format(**template_args)
        mangled_builtins.add_entry(essl_level, shader_type, template_args['mangled_name'], symbol,
                                   template_args['essl_extension'],
                                   symbols.script_generated_hash_tests)

        if template_args['unique_name'] in functions.defined_function_variants:
            continue
        functions.defined_function_variants.add(template_args['unique_name'])

        template_builtin_id_declaration = '    static constexpr const TSymbolUniqueId {human_readable_name} = TSymbolUniqueId({id});'
        symbols.builtin_id_declarations.append(
            template_builtin_id_declaration.format(**template_args))

        parameters_list = []
        for param in parameters:
            unique_param_name = get_variable_name_to_store_parameter(param)
            param_template_args = {
                'name': '_empty',
                'name_with_suffix': unique_param_name,
                'type': param.get_statictype_string(),
                'extension': 'UNDEFINED'
            }
            if unique_param_name not in functions.defined_parameter_names:
                id_counter += 1
                param_template_args['id'] = id_counter
                template_builtin_id_declaration = '    static constexpr const TSymbolUniqueId {name_with_suffix} = TSymbolUniqueId({id});'
                symbols.builtin_id_declarations.append(
                    template_builtin_id_declaration.format(**param_template_args))
                define_constexpr_variable(param_template_args, variables.variable_declarations)
                functions.defined_parameter_names.add(unique_param_name)
                if param.has_array_size():
                    array_size_template_args = {'arraySize': param.data['arraySize']}
                    define_constexpr_type_array_sizes(array_size_template_args,
                                                      variables.type_array_sizes_declarations)
            parameters_list.append(
                '&BuiltInVariable::k{name_with_suffix}'.format(**param_template_args))

        template_args['parameters_var_name'] = get_variable_name_to_store_parameters(parameters)
        if len(parameters) > 0:
            template_args['parameters_list'] = ', '.join(parameters_list)
            template_parameter_list_declaration = 'constexpr const TVariable *{parameters_var_name}[{param_count}] = {{ {parameters_list} }};'
            functions.parameter_declarations[
                template_args['parameters_var_name']] = template_parameter_list_declaration.format(
                    **template_args)
        else:
            template_parameter_list_declaration = 'constexpr const TVariable **{parameters_var_name} = nullptr;'
            functions.parameter_declarations[
                template_args['parameters_var_name']] = template_parameter_list_declaration.format(
                    **template_args)

        template_args['extension'] = extension_string
        template_function_declaration = 'constexpr const TFunction {unique_name}(BuiltInId::{human_readable_name}, BuiltInName::{name_with_suffix}, {extension}, BuiltInParameters::{parameters_var_name}, {param_count}, {return_type}, {op}, {known_to_not_have_side_effects});'
        functions.function_declarations.append(
            template_function_declaration.format(**template_args))

        id_counter += 1


def process_single_function_group(shader_type, group_name, group, symbols, variables, functions,
                                  group_op_suffix, unmangled_function_if_statements,
                                  mangled_builtins):

    if 'functions' not in group:
        return

    for function_props in group['functions']:
        process_single_function(shader_type, group_name, function_props, symbols, variables,
                                functions, group_op_suffix, unmangled_function_if_statements,
                                mangled_builtins)

        if 'essl_extension_becomes_core_in' in function_props:
            assert ('essl_extension' in function_props)

            core_props = copy.deepcopy(function_props)

            # Adjust the props by updating the level, removing extension and adding suffix
            core_level = function_props['essl_extension_becomes_core_in']
            core_props['essl_level'] = core_level
            del core_props['essl_extension']
            suffix = core_props['suffix'] if 'suffix' in core_props else ''
            suffix += generate_suffix_from_level(core_level)
            core_props['suffix'] = suffix

            process_single_function(shader_type, group_name, core_props, symbols, variables,
                                    functions, group_op_suffix, unmangled_function_if_statements,
                                    mangled_builtins)


def process_function_group(group_name, group, symbols, variables, functions,
                           parent_group_op_suffix, unmangled_function_if_statements,
                           mangled_builtins):

    functions.operator_enum_declarations.append('')
    functions.operator_enum_declarations.append('    // Group ' + group_name)
    first_op_index = len(functions.operator_enum_declarations)

    shader_type = 'NONE'
    if 'shader_type' in group:
        shader_type = group['shader_type']

    group_op_suffix = parent_group_op_suffix + group.get('opSuffix', '')
    process_single_function_group(shader_type, group_name, group, symbols, variables, functions,
                                  group_op_suffix, unmangled_function_if_statements,
                                  mangled_builtins)

    if 'subgroups' in group:
        for subgroup_name, subgroup in group['subgroups'].items():
            process_function_group(group_name + subgroup_name, subgroup, symbols, variables,
                                   functions, group_op_suffix, unmangled_function_if_statements,
                                   mangled_builtins)

    if 'queryFunction' in group:
        last_op_index = len(functions.operator_enum_declarations) - 1

        first_op = functions.find_op(first_op_index, +1, last_op_index + 1)
        last_op = functions.find_op(last_op_index, -1, first_op_index - 1)

        template_args = {'first_op': first_op, 'last_op': last_op, 'group_name': group_name}
        template_is_in_group_definition = """static inline bool Is{group_name}(TOperator op)
{{
    return op >= {first_op} && op <= {last_op};
}}"""
        functions.is_in_group_definitions.append(
            template_is_in_group_definition.format(**template_args))


def prune_parameters_arrays(parameter_declarations, function_declarations):
    # We can share parameters arrays between functions in case one array is a subarray of another.
    parameter_variable_name_replacements = {}
    used_param_variable_names = set()
    for param_variable_name, param_declaration in sorted(
            parameter_declarations.items(), key=lambda item: -len(item[0])):
        replaced = False
        for used in sorted(used_param_variable_names):
            if used.startswith(param_variable_name):
                parameter_variable_name_replacements[param_variable_name] = used
                replaced = True
                break
        if not replaced:
            used_param_variable_names.add(param_variable_name)

    for i in range(len(function_declarations)):
        for replaced, replacement in parameter_variable_name_replacements.items():
            function_declarations[i] = function_declarations[i].replace(
                'BuiltInParameters::' + replaced + ',', 'BuiltInParameters::' + replacement + ',')

    return [
        value for key, value in parameter_declarations.items() if key in used_param_variable_names
    ]


def process_single_variable(shader_type, variable_name, props, symbols, variables,
                            mangled_builtins):
    global id_counter

    essl_level = props['essl_level'] if 'essl_level' in props else None
    template_args = {
        'id': id_counter,
        'name': variable_name,
        'name_with_suffix': variable_name + get_suffix(props),
        'essl_level': essl_level,
        'essl_extension': get_essl_extension(props),
        'extension': get_essl_extension(props),
        'class': 'TVariable'
    }

    template_builtin_id_declaration = '    static constexpr const TSymbolUniqueId {name_with_suffix} = TSymbolUniqueId({id});'
    symbols.builtin_id_declarations.append(template_builtin_id_declaration.format(**template_args))

    template_name_declaration = 'constexpr const ImmutableString {name}("{name}");'
    symbols.name_declarations.add(template_name_declaration.format(**template_args))

    is_member = True
    template_init_variable = ''

    extension_string = get_extension_list(template_args['extension'])

    if 'type' in props:
        if props['type']['basic'] != 'Bool' and 'precision' not in props['type']:
            raise Exception('Missing precision for variable ' + variable_name)
        template_args['type'] = TType(props['type']).get_statictype_string()

    if 'fields' in props:
        # Handle struct and interface block definitions.
        template_args['class'] = props['class']
        template_args['fields'] = 'fields_{name_with_suffix}'.format(**template_args)
        variables.init_member_variables.append(
            '    TFieldList *{fields} = new TFieldList();'.format(**template_args))
        for field_name, field_type in props['fields'].items():
            template_args['field_name'] = field_name
            template_args['field_type'] = TType(field_type).get_dynamic_type_string()
            template_name_declaration = 'constexpr const ImmutableString {field_name}("{field_name}");'
            symbols.name_declarations.add(template_name_declaration.format(**template_args))
            template_add_field = '    {fields}->push_back(new TField({field_type}, BuiltInName::{field_name}, zeroSourceLoc, SymbolType::BuiltIn));'
            variables.init_member_variables.append(template_add_field.format(**template_args))
        template_args['extension'] = extension_string
        template_init_temp_variable = '    {class} *{name_with_suffix} = new {class}(BuiltInId::{name_with_suffix}, BuiltInName::{name}, {extension}, {fields});'
        variables.init_member_variables.append(template_init_temp_variable.format(**template_args))
        if 'private' in props and props['private']:
            is_member = False
        else:
            template_init_variable = '    m_{name_with_suffix} = {name_with_suffix};'

    elif 'initDynamicType' in props:
        # Handle variables whose type can't be expressed as TStaticType
        # (type is a struct or has variable array size for example).
        template_args['type_name'] = 'type_{name_with_suffix}'.format(**template_args)
        template_args['type'] = template_args['type_name']
        template_args['ext_or_core_suffix'] = ''
        if 'essl_extension_becomes_core_in' in props and 'essl_extension' not in props:
            template_args['ext_or_core_suffix'] = generate_suffix_from_level(props['essl_level'])
        template_args['initDynamicType'] = props['initDynamicType'].format(**template_args)
        template_args['extension'] = extension_string
        template_init_variable = """    {initDynamicType}
{type_name}->realize();
m_{name_with_suffix} = new TVariable(BuiltInId::{name_with_suffix}, BuiltInName::{name}, SymbolType::BuiltIn, {extension}, {type});"""

    elif 'value' in props:
        # Handle variables with constant value, such as gl_MaxDrawBuffers.
        if props['value'] != 'resources':
            raise Exception('Unrecognized value source in variable properties: ' +
                            str(props['value']))
        resources_key = variable_name[3:]
        if 'valueKey' in props:
            resources_key = props['valueKey']
        template_args['value'] = 'resources.' + resources_key
        template_args['object_size'] = TType(props['type']).get_object_size()
        template_args['extension'] = extension_string
        template_init_variable = """    m_{name_with_suffix} = new TVariable(BuiltInId::{name_with_suffix}, BuiltInName::{name}, SymbolType::BuiltIn, {extension}, {type});
{{
    TConstantUnion *unionArray = new TConstantUnion[{object_size}];
    unionArray[0].setIConst({value});
    static_cast<TVariable *>(m_{name_with_suffix})->shareConstPointer(unionArray);
}}"""
        if template_args['object_size'] > 1:
            template_init_variable = """    m_{name_with_suffix} = new TVariable(BuiltInId::{name_with_suffix}, BuiltInName::{name}, SymbolType::BuiltIn, {extension}, {type});
{{
    TConstantUnion *unionArray = new TConstantUnion[{object_size}];
    for (size_t index = 0u; index < {object_size}; ++index)
    {{
        unionArray[index].setIConst({value}[index]);
    }}
    static_cast<TVariable *>(m_{name_with_suffix})->shareConstPointer(unionArray);
}}"""

    else:
        # Handle variables that can be stored as constexpr TVariable like
        # gl_Position, gl_FragColor etc.
        define_constexpr_variable(template_args, variables.variable_declarations)
        is_member = False

        template_get_variable_declaration = 'const TVariable *{name_with_suffix}();'
        variables.get_variable_declarations.append(
            template_get_variable_declaration.format(**template_args))

        template_get_variable_definition = """const TVariable *{name_with_suffix}()
{{
return &k{name_with_suffix};
}}
"""
        variables.get_variable_definitions.append(
            template_get_variable_definition.format(**template_args))

        obj = '&BuiltInVariable::k{name_with_suffix}'.format(**template_args)
        mangled_builtins.add_entry(essl_level, shader_type, template_args['name'], obj,
                                   template_args['essl_extension'],
                                   symbols.script_generated_hash_tests)

    if is_member:
        variables.init_member_variables.append(template_init_variable.format(**template_args))

        template_declare_member_variable = 'TSymbol *m_{name_with_suffix} = nullptr;'
        variables.declare_member_variables.append(
            template_declare_member_variable.format(**template_args))

        obj = 'm_{name_with_suffix}'.format(**template_args)

        mangled_builtins.add_entry(essl_level, shader_type, template_args['name'], obj,
                                   template_args['essl_extension'],
                                   symbols.script_generated_hash_tests)

    id_counter += 1


def process_single_variable_group(shader_type, group, symbols, variables, mangled_builtins):
    global id_counter
    if 'variables' not in group:
        return
    for variable_name, props in group['variables'].items():
        process_single_variable(shader_type, variable_name, props, symbols, variables,
                                mangled_builtins)

        if 'essl_extension_becomes_core_in' in props:
            assert ('essl_extension' in props)

            core_props = copy.deepcopy(props)

            # Adjust the props by updating the level, removing extension and adding suffix
            core_level = props['essl_extension_becomes_core_in']
            core_props['essl_level'] = core_level
            del core_props['essl_extension']
            suffix = core_props['suffix'] if 'suffix' in core_props else ''
            suffix += generate_suffix_from_level(core_level)
            core_props['suffix'] = suffix
            process_single_variable(shader_type, variable_name, core_props, symbols, variables,
                                    mangled_builtins)


def process_variable_group(shader_type, group_name, group, symbols, variables, mangled_builtins):
    global id_counter

    if 'shader_type' in group:
        shader_type = group['shader_type']

    process_single_variable_group(shader_type, group, symbols, variables, mangled_builtins)

    if 'subgroups' in group:
        for subgroup_name, subgroup in group['subgroups'].items():
            process_variable_group(shader_type, subgroup_name, subgroup, symbols, variables,
                                   mangled_builtins)


def generate_files(args, functions_txt_filename, variables_json_filename,
                   immutablestring_cpp_filename, immutablestringtest_cpp_filename,
                   builtin_header_filename, symboltable_cpp_filename, operator_header_filename,
                   symboltable_header_filename):

    symbols = SymbolsData()
    variables = VariablesData()
    functions = FunctionsData()

    parsed_functions = get_parsed_functions(functions_txt_filename)

    if args.dump_intermediate_json:
        with open('builtin_functions_ESSL.json', 'w') as outfile:

            def serialize_obj(obj):
                if isinstance(obj, TType):
                    return obj.data
                else:
                    raise "Cannot serialize to JSON: " + str(obj)

            json.dump(
                parsed_functions, outfile, indent=4, separators=(',', ': '), default=serialize_obj)

    parsed_variables = None
    with open(variables_json_filename) as f:
        parsed_variables = json.load(f, object_pairs_hook=OrderedDict)

    # This script uses a perfect hash function to avoid dealing with collisions
    mangled_names = []
    unmangled_names = []
    for group_name, group in parsed_functions.items():
        get_function_names(group, mangled_names, unmangled_names)
    for group_name, group in parsed_variables.items():
        get_variable_names(group, mangled_names)

    # Hashing mangled names
    mangled_names = list(dict.fromkeys(mangled_names))
    num_mangled_names = len(mangled_names)
    mangled_names_dict = dict(zip(mangled_names, range(0, len(mangled_names))))
    # Generate the perfect hash function
    f1, f2, mangled_G = generate_hash(mangled_names_dict, Hash2)
    mangled_hashfn = HashFunction(f1, f2, mangled_G)
    mangled_S1 = f1.salt
    mangled_S2 = f2.salt
    # Array for querying mangled builtins
    mangled_builtins = GroupedList(mangled_hashfn, num_mangled_names)

    # Hashing unmangled names
    unmangled_names = list(dict.fromkeys(unmangled_names))
    num_unmangled_names = len(unmangled_names)
    unmangled_names_dict = dict(zip(unmangled_names, range(0, len(unmangled_names))))
    # Generate the perfect hash function
    f1, f2, unmangled_G = generate_hash(unmangled_names_dict, Hash2)
    unmangled_hashfn = HashFunction(f1, f2, unmangled_G)
    unmangled_S1 = f1.salt
    unmangled_S2 = f2.salt
    # Array for querying unmangled builtins
    unmangled_function_if_statements = UnmangledGroupedList(unmangled_hashfn, num_unmangled_names)

    for group_name, group in parsed_functions.items():
        process_function_group(group_name, group, symbols, variables, functions, '',
                               unmangled_function_if_statements, mangled_builtins)

    functions.parameter_declarations = prune_parameters_arrays(functions.parameter_declarations,
                                                               functions.function_declarations)

    for group_name, group in parsed_variables.items():
        process_variable_group('NONE', group_name, group, symbols, variables, mangled_builtins)

    mangled_builtins.update_arrays()

    output_strings = {
        'script_name':
            os.path.basename(__file__),
        'builtin_id_declarations':
            '\n'.join(symbols.builtin_id_declarations),
        'last_builtin_id':
            id_counter - 1,
        'name_declarations':
            '\n'.join(sorted(list(symbols.name_declarations))),
        'function_data_source_name':
            functions_txt_filename,
        'function_declarations':
            '\n'.join(functions.function_declarations),
        'parameter_declarations':
            '\n'.join(sorted(functions.parameter_declarations)),
        'operator_enum_declarations':
            '\n'.join(functions.operator_enum_declarations),
        'is_in_group_definitions':
            '\n'.join(functions.is_in_group_definitions),
        'variable_data_source_name':
            variables_json_filename,
        'type_array_sizes_declarations':
            '\n'.join(sorted(variables.type_array_sizes_declarations)),
        'variable_declarations':
            '\n'.join(sorted(variables.variable_declarations)),
        'get_variable_declarations':
            '\n'.join(sorted(variables.get_variable_declarations)),
        'get_variable_definitions':
            '\n'.join(sorted(variables.get_variable_definitions)),
        'declare_member_variables':
            '\n'.join(variables.declare_member_variables),
        'init_member_variables':
            '\n'.join(variables.init_member_variables),
        'mangled_names_array':
            ',\n'.join(mangled_builtins.get_names()),
        'mangled_offsets_array':
            '\n'.join(mangled_builtins.get_offsets()),
        'mangled_rules':
            ',\n'.join(mangled_builtins.get_rules()),
        'unmangled_array':
            ', '.join(unmangled_function_if_statements.get_array()),
        'max_unmangled_name_length':
            unmangled_function_if_statements.get_max_name_length(),
        'max_mangled_name_length':
            mangled_builtins.get_max_name_length(),
        'num_unmangled_names':
            num_unmangled_names,
        'num_mangled_names':
            num_mangled_names,
        'script_generated_hash_tests':
            '\n'.join(symbols.script_generated_hash_tests.keys()),
        'unmangled_script_generated_hash_tests':
            '\n'.join(symbols.unmangled_script_generated_hash_tests.keys()),
        'mangled_S1':
            str(mangled_S1).replace('[', ' ').replace(']', ' '),
        'mangled_S2':
            str(mangled_S2).replace('[', ' ').replace(']', ' '),
        'mangled_G':
            str(mangled_G).replace('[', ' ').replace(']', ' '),
        'mangled_NG':
            len(mangled_G),
        'mangled_NS':
            len(mangled_S1),
        'unmangled_S1':
            str(unmangled_S1).replace('[', ' ').replace(']', ' '),
        'unmangled_S2':
            str(unmangled_S2).replace('[', ' ').replace(']', ' '),
        'unmangled_G':
            str(unmangled_G).replace('[', ' ').replace(']', ' '),
        'unmangled_NG':
            len(unmangled_G),
        'unmangled_NS':
            len(unmangled_S1),
    }

    with open(immutablestring_cpp_filename, 'wt') as outfile_cpp:
        output_cpp = template_immutablestring_cpp.format(**output_strings)
        outfile_cpp.write(output_cpp)

    with open(immutablestringtest_cpp_filename, 'wt') as outfile_cpp:
        output_cpp = template_immutablestringtest_cpp.format(**output_strings)
        outfile_cpp.write(output_cpp)

    with open(builtin_header_filename, 'wt') as outfile_header:
        output_header = template_builtin_header.format(**output_strings)
        outfile_header.write(output_header)

    with open(symboltable_cpp_filename, 'wt') as outfile_cpp:
        output_cpp = template_symboltable_cpp.format(**output_strings)
        outfile_cpp.write(output_cpp)

    with open(operator_header_filename, 'wt') as outfile_header:
        output_header = template_operator_header.format(**output_strings)
        outfile_header.write(output_header)

    with open(symboltable_header_filename, 'wt') as outfile_h:
        output_h = template_symboltable_header.format(**output_strings)
        outfile_h.write(output_h)


def main():
    random.seed(0)
    set_working_dir()

    parser = argparse.ArgumentParser()
    parser.add_argument(
        '--dump-intermediate-json',
        help='Dump parsed function data as a JSON file builtin_functions.json',
        action="store_true")
    parser.add_argument('auto_script_command', nargs='?', default='')
    args = parser.parse_args()

    test_filename = '../../tests/compiler_tests/ImmutableString_test_autogen.cpp'
    variables_json_filename = 'builtin_variables.json'
    functions_txt_filename = 'builtin_function_declarations.txt'

    # auto_script parameters.
    if args.auto_script_command != '':
        inputs = [
            functions_txt_filename,
            variables_json_filename,
        ]
        outputs = [
            'Operator_autogen.h',
            'SymbolTable_autogen.h',
            test_filename,
            'ImmutableString_autogen.cpp',
            'SymbolTable_autogen.cpp',
            'tree_util/BuiltIn_autogen.h',
        ]

        if args.auto_script_command == 'inputs':
            print(','.join(inputs))
        elif args.auto_script_command == 'outputs':
            print(','.join(outputs))
        else:
            print('Invalid script parameters')
            return 1
        return 0

    # Generate files based on ESSL symbols
    generate_files(args, functions_txt_filename, variables_json_filename,
                   'ImmutableString_autogen.cpp', test_filename, 'tree_util/BuiltIn_autogen.h',
                   'SymbolTable_autogen.cpp', 'Operator_autogen.h', 'SymbolTable_autogen.h')

    return 0


if __name__ == '__main__':
    sys.exit(main())