#!/usr/bin/env python3

# Copyright 2017 gRPC authors.
#
# 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.

from __future__ import print_function

import collections
import ctypes
import json
import math
import sys

import yaml

with open('src/core/lib/debug/stats_data.yaml') as f:
    attrs = yaml.load(f.read())

REQUIRED_FIELDS = ['name', 'doc']


def make_type(name, fields):
    return (collections.namedtuple(
        name, ' '.join(list(set(REQUIRED_FIELDS + fields)))), [])


def c_str(s, encoding='ascii'):
    if isinstance(s, str):
        s = s.encode(encoding)
    result = ''
    for c in s:
        c = chr(c) if isinstance(c, int) else c
        if not (32 <= ord(c) < 127) or c in ('\\', '"'):
            result += '\\%03o' % ord(c)
        else:
            result += c
    return '"' + result + '"'


types = (
    make_type('Counter', []),
    make_type('Histogram', ['max', 'buckets']),
)
Shape = collections.namedtuple('Shape', 'max buckets')

inst_map = dict((t[0].__name__, t[1]) for t in types)

stats = []

for attr in attrs:
    found = False
    for t, lst in types:
        t_name = t.__name__.lower()
        if t_name in attr:
            name = attr[t_name]
            del attr[t_name]
            lst.append(t(name=name, **attr))
            found = True
            break
    assert found, "Bad decl: %s" % attr


def dbl2u64(d):
    return ctypes.c_ulonglong.from_buffer(ctypes.c_double(d)).value


def u642dbl(d):
    return ctypes.c_double.from_buffer(ctypes.c_ulonglong(d)).value


def shift_works_until(mapped_bounds, shift_bits):
    for i, ab in enumerate(zip(mapped_bounds, mapped_bounds[1:])):
        a, b = ab
        if (a >> shift_bits) == (b >> shift_bits):
            return i
    return len(mapped_bounds)


def find_ideal_shift(mapped_bounds, max_size):
    best = None
    for shift_bits in reversed(list(range(0, 64))):
        n = shift_works_until(mapped_bounds, shift_bits)
        if n == 0:
            continue
        table_size = mapped_bounds[n - 1] >> shift_bits
        if table_size > max_size:
            continue
        if best is None:
            best = (shift_bits, n, table_size)
        elif best[1] < n:
            best = (shift_bits, n, table_size)
    return best


def gen_map_table(mapped_bounds, shift_data):
    #print("gen_map_table(%s, %s)" % (mapped_bounds, shift_data))
    tbl = []
    cur = 0
    mapped_bounds = [x >> shift_data[0] for x in mapped_bounds]
    for i in range(0, mapped_bounds[shift_data[1] - 1]):
        while i > mapped_bounds[cur]:
            cur += 1
        tbl.append(cur)
    return tbl


static_tables = []


def decl_static_table(values, type):
    global static_tables
    v = (type, values)
    for i, vp in enumerate(static_tables):
        if v == vp:
            return i
    r = len(static_tables)
    static_tables.append(v)
    return r


def type_for_uint_table(table):
    mv = max(table)
    if mv < 2**8:
        return 'uint8_t'
    elif mv < 2**16:
        return 'uint16_t'
    elif mv < 2**32:
        return 'uint32_t'
    else:
        return 'uint64_t'


def merge_cases(cases):
    l = len(cases)
    if l == 1:
        return cases[0][1]
    left_len = l // 2
    left = cases[0:left_len]
    right = cases[left_len:]
    return 'if (value < %d) {\n%s\n} else {\n%s\n}' % (
        left[-1][0], merge_cases(left), merge_cases(right))


def gen_bucket_code(shape):
    bounds = [0, 1]
    done_trivial = False
    done_unmapped = False
    first_nontrivial = None
    first_unmapped = None
    while len(bounds) < shape.buckets + 1:
        if len(bounds) == shape.buckets:
            nextb = int(shape.max)
        else:
            mul = math.pow(
                float(shape.max) / bounds[-1],
                1.0 / (shape.buckets + 1 - len(bounds)))
            nextb = int(math.ceil(bounds[-1] * mul))
        if nextb <= bounds[-1] + 1:
            nextb = bounds[-1] + 1
        elif not done_trivial:
            done_trivial = True
            first_nontrivial = len(bounds)
        bounds.append(nextb)
    bounds_idx = decl_static_table(bounds, 'int')
    #print first_nontrivial, shift_data, bounds
    #if shift_data is not None: print [hex(x >> shift_data[0]) for x in code_bounds[first_nontrivial:]]
    if first_nontrivial is None:
        return ('return grpc_core::Clamp(value, 0, %d);\n' % shape.max,
                bounds_idx)
    cases = [(0, 'return 0;'), (first_nontrivial, 'return value;')]
    if done_trivial:
        first_nontrivial_code = dbl2u64(first_nontrivial)
        last_code = first_nontrivial_code
        while True:
            code = ''
            first_nontrivial = u642dbl(first_nontrivial_code)
            code_bounds_index = None
            for i, b in enumerate(bounds):
                if b > first_nontrivial:
                    code_bounds_index = i
                    break
            code_bounds = [dbl2u64(x) - first_nontrivial_code for x in bounds]
            shift_data = find_ideal_shift(code_bounds[code_bounds_index:],
                                          65536)
            if not shift_data:
                break
            map_table = gen_map_table(code_bounds[code_bounds_index:],
                                      shift_data)
            if not map_table:
                break
            if map_table[-1] < 5:
                break
            map_table_idx = decl_static_table(
                [x + code_bounds_index for x in map_table],
                type_for_uint_table(map_table))
            last_code = (
                (len(map_table) - 1) << shift_data[0]) + first_nontrivial_code
            code += 'DblUint val;\n'
            code += 'val.dbl = value;\n'
            code += 'const int bucket = '
            code += 'kStatsTable%d[((val.uint - %dull) >> %d)];\n' % (
                map_table_idx, first_nontrivial_code, shift_data[0])
            code += 'return bucket - (value < kStatsTable%d[bucket]);' % bounds_idx
            cases.append((int(u642dbl(last_code)) + 1, code))
            first_nontrivial_code = last_code
        last = u642dbl(last_code) + 1
        for i, b in enumerate(bounds[:-2]):
            if bounds[i + 1] < last:
                continue
            cases.append((bounds[i + 1], 'return %d;' % i))
    cases.append((None, 'return %d;' % (len(bounds) - 2)))
    return (merge_cases(cases), bounds_idx)


# utility: print a big comment block into a set of files
def put_banner(files, banner):
    for f in files:
        print('/*', file=f)
        for line in banner:
            print(' * %s' % line, file=f)
        print(' */', file=f)
        print(file=f)


shapes = set()
for histogram in inst_map['Histogram']:
    shapes.add(Shape(max=histogram.max, buckets=histogram.buckets))


def snake_to_pascal(name):
    return ''.join([x.capitalize() for x in name.split('_')])


with open('src/core/lib/debug/stats_data.h', 'w') as H:
    # copy-paste copyright notice from this file
    with open(sys.argv[0]) as my_source:
        copyright = []
        for line in my_source:
            if line[0] != '#':
                break
        for line in my_source:
            if line[0] == '#':
                copyright.append(line)
                break
        for line in my_source:
            if line[0] != '#':
                break
            copyright.append(line)
        put_banner([H], [line[2:].rstrip() for line in copyright])

    put_banner(
        [H],
        ["Automatically generated by tools/codegen/core/gen_stats_data.py"])

    print("#ifndef GRPC_CORE_LIB_DEBUG_STATS_DATA_H", file=H)
    print("#define GRPC_CORE_LIB_DEBUG_STATS_DATA_H", file=H)
    print(file=H)
    print("#include <grpc/support/port_platform.h>", file=H)
    print("#include <atomic>", file=H)
    print("#include <memory>", file=H)
    print("#include <stdint.h>", file=H)
    print("#include \"src/core/lib/debug/histogram_view.h\"", file=H)
    print("#include \"absl/strings/string_view.h\"", file=H)
    print("#include \"src/core/lib/gprpp/per_cpu.h\"", file=H)
    print(file=H)
    print("namespace grpc_core {", file=H)

    for shape in shapes:
        print("class HistogramCollector_%d_%d;" % (shape.max, shape.buckets),
              file=H)
        print("class Histogram_%d_%d {" % (shape.max, shape.buckets), file=H)
        print(" public:", file=H)
        print("  static int BucketFor(int value);", file=H)
        print("  const uint64_t* buckets() const { return buckets_; }", file=H)
        print(
            "  friend Histogram_%d_%d operator-(const Histogram_%d_%d& left, const Histogram_%d_%d& right);"
            % (shape.max, shape.buckets, shape.max, shape.buckets, shape.max,
               shape.buckets),
            file=H)
        print(" private:", file=H)
        print("  friend class HistogramCollector_%d_%d;" %
              (shape.max, shape.buckets),
              file=H)
        print("  uint64_t buckets_[%d]{};" % shape.buckets, file=H)
        print("};", file=H)
        print("class HistogramCollector_%d_%d {" % (shape.max, shape.buckets),
              file=H)
        print(" public:", file=H)
        print("  void Increment(int value) {", file=H)
        print("    buckets_[Histogram_%d_%d::BucketFor(value)]" %
              (shape.max, shape.buckets),
              file=H)
        print("        .fetch_add(1, std::memory_order_relaxed);", file=H)
        print("  }", file=H)
        print("  void Collect(Histogram_%d_%d* result) const;" %
              (shape.max, shape.buckets),
              file=H)
        print(" private:", file=H)
        print("  std::atomic<uint64_t> buckets_[%d]{};" % shape.buckets, file=H)
        print("};", file=H)

    print("struct GlobalStats {", file=H)
    print("  enum class Counter {", file=H)
    for ctr in inst_map['Counter']:
        print("    k%s," % snake_to_pascal(ctr.name), file=H)
    print("    COUNT", file=H)
    print("  };", file=H)
    print("  enum class Histogram {", file=H)
    for ctr in inst_map['Histogram']:
        print("    k%s," % snake_to_pascal(ctr.name), file=H)
    print("    COUNT", file=H)
    print("  };", file=H)
    print("  GlobalStats();", file=H)
    print(
        "  static const absl::string_view counter_name[static_cast<int>(Counter::COUNT)];",
        file=H)
    print(
        "  static const absl::string_view histogram_name[static_cast<int>(Histogram::COUNT)];",
        file=H)
    print(
        "  static const absl::string_view counter_doc[static_cast<int>(Counter::COUNT)];",
        file=H)
    print(
        "  static const absl::string_view histogram_doc[static_cast<int>(Histogram::COUNT)];",
        file=H)
    print("  union {", file=H)
    print("    struct {", file=H)
    for ctr in inst_map['Counter']:
        print("    uint64_t %s;" % ctr.name, file=H)
    print("    };", file=H)
    print("    uint64_t counters[static_cast<int>(Counter::COUNT)];", file=H)
    print("  };", file=H)
    for ctr in inst_map['Histogram']:
        print("  Histogram_%d_%d %s;" % (ctr.max, ctr.buckets, ctr.name),
              file=H)
    print("  HistogramView histogram(Histogram which) const;", file=H)
    print(
        "  std::unique_ptr<GlobalStats> Diff(const GlobalStats& other) const;",
        file=H)
    print("};", file=H)
    print("class GlobalStatsCollector {", file=H)
    print(" public:", file=H)
    print("  std::unique_ptr<GlobalStats> Collect() const;", file=H)
    for ctr in inst_map['Counter']:
        print(
            "  void Increment%s() { data_.this_cpu().%s.fetch_add(1, std::memory_order_relaxed); }"
            % (snake_to_pascal(ctr.name), ctr.name),
            file=H)
    for ctr in inst_map['Histogram']:
        print(
            "  void Increment%s(int value) { data_.this_cpu().%s.Increment(value); }"
            % (snake_to_pascal(ctr.name), ctr.name),
            file=H)
    print(" private:", file=H)
    print("  struct Data {", file=H)
    for ctr in inst_map['Counter']:
        print("    std::atomic<uint64_t> %s{0};" % ctr.name, file=H)
    for ctr in inst_map['Histogram']:
        print("    HistogramCollector_%d_%d %s;" %
              (ctr.max, ctr.buckets, ctr.name),
              file=H)
    print("  };", file=H)
    print("  PerCpu<Data> data_;", file=H)
    print("};", file=H)
    print("}", file=H)

    print(file=H)
    print("#endif /* GRPC_CORE_LIB_DEBUG_STATS_DATA_H */", file=H)

with open('src/core/lib/debug/stats_data.cc', 'w') as C:
    # copy-paste copyright notice from this file
    with open(sys.argv[0]) as my_source:
        copyright = []
        for line in my_source:
            if line[0] != '#':
                break
        for line in my_source:
            if line[0] == '#':
                copyright.append(line)
                break
        for line in my_source:
            if line[0] != '#':
                break
            copyright.append(line)
        put_banner([C], [line[2:].rstrip() for line in copyright])

    put_banner(
        [C],
        ["Automatically generated by tools/codegen/core/gen_stats_data.py"])

    print("#include <grpc/support/port_platform.h>", file=C)
    print(file=C)
    print("#include \"src/core/lib/debug/stats_data.h\"", file=C)
    print("#include <stdint.h>", file=C)
    print("#include \"absl/memory/memory.h\"", file=C)
    print(file=C)

    histo_code = []
    histo_bucket_boundaries = {}
    for shape in shapes:
        code, bounds_idx = gen_bucket_code(shape)
        histo_bucket_boundaries[shape] = bounds_idx
        histo_code.append(code)

    print("namespace grpc_core {", file=C)
    print("namespace { union DblUint { double dbl; uint64_t uint; }; }", file=C)

    for shape in shapes:
        print(
            "void HistogramCollector_%d_%d::Collect(Histogram_%d_%d* result) const {"
            % (shape.max, shape.buckets, shape.max, shape.buckets),
            file=C)
        print("  for (int i=0; i<%d; i++) {" % shape.buckets, file=C)
        print(
            "    result->buckets_[i] += buckets_[i].load(std::memory_order_relaxed);",
            file=C)
        print("  }", file=C)
        print("}", file=C)
        print(
            "Histogram_%d_%d operator-(const Histogram_%d_%d& left, const Histogram_%d_%d& right) {"
            % (shape.max, shape.buckets, shape.max, shape.buckets, shape.max,
               shape.buckets),
            file=C)
        print("  Histogram_%d_%d result;" % (shape.max, shape.buckets), file=C)
        print("  for (int i=0; i<%d; i++) {" % shape.buckets, file=C)
        print("    result.buckets_[i] = left.buckets_[i] - right.buckets_[i];",
              file=C)
        print("  }", file=C)
        print("  return result;", file=C)
        print("}", file=C)

    for typename, instances in sorted(inst_map.items()):
        print(
            "const absl::string_view GlobalStats::%s_name[static_cast<int>(%s::COUNT)] = {"
            % (typename.lower(), typename),
            file=C)
        for inst in instances:
            print("  %s," % c_str(inst.name), file=C)
        print("};", file=C)
        print(
            "const absl::string_view GlobalStats::%s_doc[static_cast<int>(%s::COUNT)] = {"
            % (typename.lower(), typename),
            file=C)
        for inst in instances:
            print("  %s," % c_str(inst.doc), file=C)
        print("};", file=C)

    print("namespace {", file=C)
    for i, tbl in enumerate(static_tables):
        print("const %s kStatsTable%d[%d] = {%s};" %
              (tbl[0], i, len(tbl[1]), ','.join('%s' % x for x in tbl[1])),
              file=C)
    print("}  // namespace", file=C)

    for shape, code in zip(shapes, histo_code):
        print(("int Histogram_%d_%d::BucketFor(int value) {%s}") %
              (shape.max, shape.buckets, code),
              file=C)

    print("GlobalStats::GlobalStats() : %s {}" %
          ",".join("%s{0}" % ctr.name for ctr in inst_map['Counter']),
          file=C)

    print("HistogramView GlobalStats::histogram(Histogram which) const {",
          file=C)
    print("  switch (which) {", file=C)
    print("    default: GPR_UNREACHABLE_CODE(return HistogramView());", file=C)
    for inst in inst_map['Histogram']:
        print("    case Histogram::k%s:" % snake_to_pascal(inst.name), file=C)
        print(
            "      return HistogramView{&Histogram_%d_%d::BucketFor, kStatsTable%d, %d, %s.buckets()};"
            % (inst.max, inst.buckets, histo_bucket_boundaries[Shape(
                inst.max, inst.buckets)], inst.buckets, inst.name),
            file=C)
    print("  }", file=C)
    print("}", file=C)

    print(
        "std::unique_ptr<GlobalStats> GlobalStatsCollector::Collect() const {",
        file=C)
    print("  auto result = std::make_unique<GlobalStats>();", file=C)
    print("  for (const auto& data : data_) {", file=C)
    for ctr in inst_map['Counter']:
        print("    result->%s += data.%s.load(std::memory_order_relaxed);" %
              (ctr.name, ctr.name),
              file=C)
    for h in inst_map['Histogram']:
        print("    data.%s.Collect(&result->%s);" % (h.name, h.name), file=C)
    print("  }", file=C)
    print("  return result;", file=C)
    print("}", file=C)

    print(
        "std::unique_ptr<GlobalStats> GlobalStats::Diff(const GlobalStats& other) const {",
        file=C)
    print("  auto result = std::make_unique<GlobalStats>();", file=C)
    for ctr in inst_map['Counter']:
        print("  result->%s = %s - other.%s;" % (ctr.name, ctr.name, ctr.name),
              file=C)
    for h in inst_map['Histogram']:
        print("  result->%s = %s - other.%s;" % (h.name, h.name, h.name),
              file=C)
    print("  return result;", file=C)
    print("}", file=C)

    print("}", file=C)