xref: /aosp_15_r20/external/toolchain-utils/cros_utils/tabulator.py (revision 760c253c1ed00ce9abd48f8546f08516e57485fe)

# -*- coding: utf-8 -*-
# Copyright 2013 The ChromiumOS Authors
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""Table generating, analyzing and printing functions.

This defines several classes that are used to generate, analyze and print
tables.

Example usage:

  from cros_utils import tabulator

  data = [["benchmark1", "33", "44"],["benchmark2", "44", "33"]]
  tabulator.GetSimpleTable(data)

You could also use it to generate more complex tables with analysis such as
p-values, custom colors, etc. Tables are generated by TableGenerator and
analyzed/formatted by TableFormatter. TableFormatter can take in a list of
columns with custom result computation and coloring, and will compare values in
each row according to taht scheme. Here is a complex example on printing a
table:

  from cros_utils import tabulator

  runs = [[{"k1": "10", "k2": "12", "k5": "40", "k6": "40",
            "ms_1": "20", "k7": "FAIL", "k8": "PASS", "k9": "PASS",
            "k10": "0"},
           {"k1": "13", "k2": "14", "k3": "15", "ms_1": "10", "k8": "PASS",
            "k9": "FAIL", "k10": "0"}],
          [{"k1": "50", "k2": "51", "k3": "52", "k4": "53", "k5": "35", "k6":
            "45", "ms_1": "200", "ms_2": "20", "k7": "FAIL", "k8": "PASS", "k9":
            "PASS"}]]
  labels = ["vanilla", "modified"]
  tg = TableGenerator(runs, labels, TableGenerator.SORT_BY_VALUES_DESC)
  table = tg.GetTable()
  columns = [Column(LiteralResult(),
                    Format(),
                    "Literal"),
             Column(AmeanResult(),
                    Format()),
             Column(StdResult(),
                    Format()),
             Column(CoeffVarResult(),
                    CoeffVarFormat()),
             Column(NonEmptyCountResult(),
                    Format()),
             Column(AmeanRatioResult(),
                    PercentFormat()),
             Column(AmeanRatioResult(),
                    RatioFormat()),
             Column(GmeanRatioResult(),
                    RatioFormat()),
             Column(PValueResult(),
                    PValueFormat()),
            ]
  tf = TableFormatter(table, columns)
  cell_table = tf.GetCellTable()
  tp = TablePrinter(cell_table, out_to)
  print tp.Print()
"""


import collections
import getpass
import math
import statistics
import sys
from typing import Tuple, Union

from cros_utils import misc
from cros_utils.email_sender import EmailSender
import numpy as np


def _ttest_ind(
    sample: Union[np.ndarray, list], baseline: Union[np.ndarray, list]
) -> Tuple[float, float]:
    """Independent, two-sided student's T test.

    Reimplementation of scipy.stats.ttest_ind.
    """
    if isinstance(sample, list):
        sample = np.asarray(sample)
    if isinstance(baseline, list):
        baseline = np.asarray(baseline)
    diff = np.mean(sample) - np.mean(baseline)
    diff_stderr = np.sqrt(sample.var(ddof=1) + baseline.var(ddof=1))
    t_value = np.mean(diff) / (diff_stderr / np.sqrt(len(sample)))
    samples = _sample_student_t(len(sample), 1000)
    # Assuming two-sided student's t
    if t_value < 0:
        # Lower tail
        return t_value, 2 * np.sum(samples < t_value) / len(samples)
    # Upper tail
    return t_value, 2 * np.sum(samples > t_value) / len(samples)


def _sample_student_t(
    dof: float, num_samples: int
) -> np.ndarray:
    # In theory this probably should be memoized. However,
    # that's a lot of data points to store in memory for
    # the lifetime of the program?
    sample_generator = np.random.default_rng()
    return sample_generator.standard_t(dof, num_samples)


def _AllFloat(values):
    return all([misc.IsFloat(v) for v in values])


def _GetFloats(values):
    return [float(v) for v in values]


def _StripNone(results):
    res = []
    for result in results:
        if result is not None:
            res.append(result)
    return res


def _RemoveMinMax(cell, values):
    if len(values) < 3:
        print(
            "WARNING: Values count is less than 3, not ignoring min/max values"
        )
        print("WARNING: Cell name:", cell.name, "Values:", values)
        return values

    values.remove(min(values))
    values.remove(max(values))
    return values


class TableGenerator(object):
    """Creates a table from a list of list of dicts.

    The main public function is called GetTable().
    """

    SORT_BY_KEYS = 0
    SORT_BY_KEYS_DESC = 1
    SORT_BY_VALUES = 2
    SORT_BY_VALUES_DESC = 3
    NO_SORT = 4

    MISSING_VALUE = "x"

    def __init__(self, d, l, sort=NO_SORT, key_name="keys"):
        self._runs = d
        self._labels = l
        self._sort = sort
        self._key_name = key_name

    def _AggregateKeys(self):
        keys = collections.OrderedDict()
        for run_list in self._runs:
            for run in run_list:
                keys.update(dict.fromkeys(run.keys()))
        return list(keys.keys())

    def _GetHighestValue(self, key):
        values = []
        for run_list in self._runs:
            for run in run_list:
                if key in run:
                    values.append(run[key])
        values = _StripNone(values)
        if _AllFloat(values):
            values = _GetFloats(values)
        values = [
            float(v)
            for v in values
            if isinstance(v, float)
            or isinstance(v, int)
            or v.lower() in ("nan", "inf")
        ]
        if not values:
            return float("nan")
        return max(values)

    def _GetLowestValue(self, key):
        values = []
        for run_list in self._runs:
            for run in run_list:
                if key in run:
                    values.append(run[key])
        values = _StripNone(values)
        if _AllFloat(values):
            values = _GetFloats(values)
        values = [
            float(v)
            for v in values
            if isinstance(v, float)
            or isinstance(v, int)
            or v.lower() in ("nan", "inf")
        ]
        if not values:
            return float("nan")
        return min(values)

    def _SortKeys(self, keys):
        if self._sort == self.SORT_BY_KEYS:
            return sorted(keys)
        elif self._sort == self.SORT_BY_VALUES:
            # pylint: disable=unnecessary-lambda
            return sorted(keys, key=lambda x: self._GetLowestValue(x))
        elif self._sort == self.SORT_BY_VALUES_DESC:
            # pylint: disable=unnecessary-lambda
            return sorted(
                keys, key=lambda x: self._GetHighestValue(x), reverse=True
            )
        elif self._sort == self.NO_SORT:
            return keys
        else:
            assert 0, "Unimplemented sort %s" % self._sort

    def _GetKeys(self):
        keys = self._AggregateKeys()
        return self._SortKeys(keys)

    def GetTable(self, number_of_rows=sys.maxsize):
        """Returns a table from a list of list of dicts.

        Examples:
          We have the following runs:
            [[{"k1": "v1", "k2": "v2"}, {"k1": "v3"}],
             [{"k1": "v4", "k4": "v5"}]]
          and the following labels:
            ["vanilla", "modified"]
          it will return:
            [["Key", "vanilla", "modified"]
             ["k1", ["v1", "v3"], ["v4"]]
             ["k2", ["v2"], []]
             ["k4", [], ["v5"]]]
          The returned table can then be processed further by other classes in this
          module.

        The list of list of dicts is passed into the constructor of TableGenerator.
        This method converts that into a canonical list of lists which represents a
        table of values.

        Args:
          number_of_rows: Maximum number of rows to return from the table.

        Returns:
          A list of lists which is the table.
        """
        keys = self._GetKeys()
        header = [self._key_name] + self._labels
        table = [header]
        rows = 0
        for k in keys:
            row = [k]
            unit = None
            for run_list in self._runs:
                v = []
                for run in run_list:
                    if k in run:
                        if isinstance(run[k], list):
                            val = run[k][0]
                            unit = run[k][1]
                        else:
                            val = run[k]
                        v.append(val)
                    else:
                        v.append(None)
                row.append(v)
            # If we got a 'unit' value, append the units name to the key name.
            if unit:
                keyname = row[0] + " (%s) " % unit
                row[0] = keyname
            table.append(row)
            rows += 1
            if rows == number_of_rows:
                break
        return table


class SamplesTableGenerator(TableGenerator):
    """Creates a table with only samples from the results

    The main public function is called GetTable().

    Different than TableGenerator, self._runs is now a dict of {benchmark: runs}
    We are expecting there is 'samples' in `runs`.
    """

    def __init__(self, run_keyvals, label_list, iter_counts, weights):
        TableGenerator.__init__(
            self, run_keyvals, label_list, key_name="Benchmarks"
        )
        self._iter_counts = iter_counts
        self._weights = weights

    def _GetKeys(self):
        keys = self._runs.keys()
        return self._SortKeys(keys)

    def GetTable(self, number_of_rows=sys.maxsize):
        """Returns a tuple, which contains three args:

          1) a table from a list of list of dicts.
          2) updated benchmark_results run_keyvals with composite benchmark
          3) updated benchmark_results iter_count with composite benchmark

        The dict of list of list of dicts is passed into the constructor of
        SamplesTableGenerator.
        This method converts that into a canonical list of lists which
        represents a table of values.

        Examples:
          We have the following runs:
            {bench1: [[{"samples": "v1"}, {"samples": "v2"}],
                      [{"samples": "v3"}, {"samples": "v4"}]]
             bench2: [[{"samples": "v21"}, None],
                      [{"samples": "v22"}, {"samples": "v23"}]]}
          and weights of benchmarks:
            {bench1: w1, bench2: w2}
          and the following labels:
            ["vanilla", "modified"]
          it will return:
            [["Benchmark", "Weights", "vanilla", "modified"]
             ["bench1", w1,
                ((2, 0), ["v1*w1", "v2*w1"]), ((2, 0), ["v3*w1", "v4*w1"])]
             ["bench2", w2,
                ((1, 1), ["v21*w2", None]), ((2, 0), ["v22*w2", "v23*w2"])]
             ["Composite Benchmark", N/A,
                ((1, 1), ["v1*w1+v21*w2", None]),
                ((2, 0), ["v3*w1+v22*w2", "v4*w1+ v23*w2"])]]
          The returned table can then be processed further by other classes in this
          module.

        Args:
          number_of_rows: Maximum number of rows to return from the table.

        Returns:
          A list of lists which is the table.
        """
        keys = self._GetKeys()
        header = [self._key_name, "Weights"] + self._labels
        table = [header]
        rows = 0
        iterations = 0

        for k in keys:
            bench_runs = self._runs[k]
            unit = None
            all_runs_empty = all(
                not dict for label in bench_runs for dict in label
            )
            if all_runs_empty:
                cell = Cell()
                cell.string_value = (
                    "Benchmark %s contains no result."
                    " Is the benchmark name valid?" % k
                )
                table.append([cell])
            else:
                row = [k]
                row.append(self._weights[k])
                for run_list in bench_runs:
                    run_pass = 0
                    run_fail = 0
                    v = []
                    for run in run_list:
                        if "samples" in run:
                            if isinstance(run["samples"], list):
                                val = run["samples"][0] * self._weights[k]
                                unit = run["samples"][1]
                            else:
                                val = run["samples"] * self._weights[k]
                            v.append(val)
                            run_pass += 1
                        else:
                            v.append(None)
                            run_fail += 1
                    one_tuple = ((run_pass, run_fail), v)
                    if iterations not in (0, run_pass + run_fail):
                        raise ValueError(
                            "Iterations of each benchmark run "
                            "are not the same"
                        )
                    iterations = run_pass + run_fail
                    row.append(one_tuple)
                if unit:
                    keyname = row[0] + " (%s) " % unit
                    row[0] = keyname
                table.append(row)
                rows += 1
                if rows == number_of_rows:
                    break

        k = "Composite Benchmark"
        if k in keys:
            raise RuntimeError("Composite benchmark already exists in results")

        # Create a new composite benchmark row at the bottom of the summary table
        # The new row will be like the format in example:
        # ["Composite Benchmark", N/A,
        #        ((1, 1), ["v1*w1+v21*w2", None]),
        #        ((2, 0), ["v3*w1+v22*w2", "v4*w1+ v23*w2"])]]
        # First we will create a row of [key, weight, [[0] * iterations] * labels]
        row = [None] * len(header)
        row[0] = "%s (samples)" % k
        row[1] = "N/A"
        for label_index in range(2, len(row)):
            row[label_index] = [0] * iterations

        for cur_row in table[1:]:
            # Iterate through each benchmark
            if len(cur_row) > 1:
                for label_index in range(2, len(cur_row)):
                    # Iterate through each run in a single benchmark
                    # each result should look like ((pass, fail), [values_list])
                    bench_runs = cur_row[label_index][1]
                    for index in range(iterations):
                        # Accumulate each run result to composite benchmark run
                        # If any run fails, then we set this run for composite benchmark
                        # to None so that we know it fails.
                        if (
                            bench_runs[index]
                            and row[label_index][index] is not None
                        ):
                            row[label_index][index] += bench_runs[index]
                        else:
                            row[label_index][index] = None
            else:
                # One benchmark totally fails, no valid data will be in final result
                for label_index in range(2, len(row)):
                    row[label_index] = [None] * iterations
                break
        # Calculate pass and fail count for composite benchmark
        for label_index in range(2, len(row)):
            run_pass = 0
            run_fail = 0
            for run in row[label_index]:
                if run:
                    run_pass += 1
                else:
                    run_fail += 1
            row[label_index] = ((run_pass, run_fail), row[label_index])
        table.append(row)

        # Now that we have the table genearted, we want to store this new composite
        # benchmark into the benchmark_result in ResultReport object.
        # This will be used to generate a full table which contains our composite
        # benchmark.
        # We need to create composite benchmark result and add it to keyvals in
        # benchmark_results.
        v = []
        for label in row[2:]:
            # each label's result looks like ((pass, fail), [values])
            benchmark_runs = label[1]
            # List of values of each label
            single_run_list = []
            for run in benchmark_runs:
                # Result of each run under the same label is a dict of keys.
                # Here the only key we will add for composite benchmark is the
                # weighted_samples we added up.
                one_dict = {}
                if run:
                    one_dict["weighted_samples"] = [run, "samples"]
                    one_dict["retval"] = 0
                else:
                    one_dict["retval"] = 1
                single_run_list.append(one_dict)
            v.append(single_run_list)

        self._runs[k] = v
        self._iter_counts[k] = iterations

        return (table, self._runs, self._iter_counts)


class Result(object):
    """A class that respresents a single result.

    This single result is obtained by condensing the information from a list of
    runs and a list of baseline runs.
    """

    def __init__(self):
        pass

    def _AllStringsSame(self, values):
        values_set = set(values)
        return len(values_set) == 1

    def NeedsBaseline(self):
        return False

    # pylint: disable=unused-argument
    def _Literal(self, cell, values, baseline_values):
        cell.value = " ".join([str(v) for v in values])

    def _ComputeFloat(self, cell, values, baseline_values):
        self._Literal(cell, values, baseline_values)

    def _ComputeString(self, cell, values, baseline_values):
        self._Literal(cell, values, baseline_values)

    def _InvertIfLowerIsBetter(self, cell):
        pass

    def _GetGmean(self, values):
        if not values:
            return float("nan")
        if any([v < 0 for v in values]):
            return float("nan")
        if any([v == 0 for v in values]):
            return 0.0
        log_list = [math.log(v) for v in values]
        gmean_log = sum(log_list) / len(log_list)
        return math.exp(gmean_log)

    def Compute(self, cell, values, baseline_values):
        """Compute the result given a list of values and baseline values.

        Args:
          cell: A cell data structure to populate.
          values: List of values.
          baseline_values: List of baseline values. Can be none if this is the
          baseline itself.
        """
        all_floats = True
        values = _StripNone(values)
        if not values:
            cell.value = ""
            return
        if _AllFloat(values):
            float_values = _GetFloats(values)
        else:
            all_floats = False
        if baseline_values:
            baseline_values = _StripNone(baseline_values)
        if baseline_values:
            if _AllFloat(baseline_values):
                float_baseline_values = _GetFloats(baseline_values)
            else:
                all_floats = False
        else:
            if self.NeedsBaseline():
                cell.value = ""
                return
            float_baseline_values = None
        if all_floats:
            self._ComputeFloat(cell, float_values, float_baseline_values)
            self._InvertIfLowerIsBetter(cell)
        else:
            self._ComputeString(cell, values, baseline_values)


class LiteralResult(Result):
    """A literal result."""

    def __init__(self, iteration=0):
        super(LiteralResult, self).__init__()
        self.iteration = iteration

    def Compute(self, cell, values, baseline_values):
        try:
            cell.value = values[self.iteration]
        except IndexError:
            cell.value = "-"


class NonEmptyCountResult(Result):
    """A class that counts the number of non-empty results.

    The number of non-empty values will be stored in the cell.
    """

    def Compute(self, cell, values, baseline_values):
        """Put the number of non-empty values in the cell result.

        Args:
          cell: Put the result in cell.value.
          values: A list of values for the row.
          baseline_values: A list of baseline values for the row.
        """
        cell.value = len(_StripNone(values))
        if not baseline_values:
            return
        base_value = len(_StripNone(baseline_values))
        if cell.value == base_value:
            return
        f = ColorBoxFormat()
        len_values = len(values)
        len_baseline_values = len(baseline_values)
        tmp_cell = Cell()
        tmp_cell.value = 1.0 + (
            float(cell.value - base_value)
            / (max(len_values, len_baseline_values))
        )
        f.Compute(tmp_cell)
        cell.bgcolor = tmp_cell.bgcolor


class StringMeanResult(Result):
    """Mean of string values."""

    def _ComputeString(self, cell, values, baseline_values):
        if self._AllStringsSame(values):
            cell.value = str(values[0])
        else:
            cell.value = "?"


class AmeanResult(StringMeanResult):
    """Arithmetic mean."""

    def __init__(self, ignore_min_max=False):
        super(AmeanResult, self).__init__()
        self.ignore_min_max = ignore_min_max

    def _ComputeFloat(self, cell, values, baseline_values):
        if self.ignore_min_max:
            values = _RemoveMinMax(cell, values)
        cell.value = statistics.mean(values)


class RawResult(Result):
    """Raw result."""


class IterationResult(Result):
    """Iteration result."""


class MinResult(Result):
    """Minimum."""

    def _ComputeFloat(self, cell, values, baseline_values):
        cell.value = min(values)

    def _ComputeString(self, cell, values, baseline_values):
        if values:
            cell.value = min(values)
        else:
            cell.value = ""


class MaxResult(Result):
    """Maximum."""

    def _ComputeFloat(self, cell, values, baseline_values):
        cell.value = max(values)

    def _ComputeString(self, cell, values, baseline_values):
        if values:
            cell.value = max(values)
        else:
            cell.value = ""


class NumericalResult(Result):
    """Numerical result."""

    def _ComputeString(self, cell, values, baseline_values):
        cell.value = "?"


class StdResult(NumericalResult):
    """Standard deviation."""

    def __init__(self, ignore_min_max=False):
        super(StdResult, self).__init__()
        self.ignore_min_max = ignore_min_max

    def _ComputeFloat(self, cell, values, baseline_values):
        if self.ignore_min_max:
            values = _RemoveMinMax(cell, values)
        cell.value = statistics.pstdev(values)


class CoeffVarResult(NumericalResult):
    """Standard deviation / Mean"""

    def __init__(self, ignore_min_max=False):
        super(CoeffVarResult, self).__init__()
        self.ignore_min_max = ignore_min_max

    def _ComputeFloat(self, cell, values, baseline_values):
        if self.ignore_min_max:
            values = _RemoveMinMax(cell, values)
        if statistics.mean(values) != 0.0:
            noise = abs(statistics.pstdev(values) / statistics.mean(values))
        else:
            noise = 0.0
        cell.value = noise


class ComparisonResult(Result):
    """Same or Different."""

    def NeedsBaseline(self):
        return True

    def _ComputeString(self, cell, values, baseline_values):
        value = None
        baseline_value = None
        if self._AllStringsSame(values):
            value = values[0]
        if self._AllStringsSame(baseline_values):
            baseline_value = baseline_values[0]
        if value is not None and baseline_value is not None:
            if value == baseline_value:
                cell.value = "SAME"
            else:
                cell.value = "DIFFERENT"
        else:
            cell.value = "?"


class PValueResult(ComparisonResult):
    """P-value."""

    def __init__(self, ignore_min_max=False):
        super(PValueResult, self).__init__()
        self.ignore_min_max = ignore_min_max

    def _ComputeFloat(self, cell, values, baseline_values):
        if self.ignore_min_max:
            values = _RemoveMinMax(cell, values)
            baseline_values = _RemoveMinMax(cell, baseline_values)
        if len(values) < 2 or len(baseline_values) < 2:
            cell.value = float("nan")
            return
        _, cell.value = _ttest_ind(values, baseline_values)

    def _ComputeString(self, cell, values, baseline_values):
        return float("nan")


class KeyAwareComparisonResult(ComparisonResult):
    """Automatic key aware comparison."""

    def _IsLowerBetter(self, key):
        # Units in histograms should include directions
        if "smallerIsBetter" in key:
            return True
        if "biggerIsBetter" in key:
            return False

        # For units in chartjson:
        # TODO(llozano): Trying to guess direction by looking at the name of the
        # test does not seem like a good idea. Test frameworks should provide this
        # info explicitly. I believe Telemetry has this info. Need to find it out.
        #
        # Below are some test names for which we are not sure what the
        # direction is.
        #
        # For these we dont know what the direction is. But, since we dont
        # specify anything, crosperf will assume higher is better:
        # --percent_impl_scrolled--percent_impl_scrolled--percent
        # --solid_color_tiles_analyzed--solid_color_tiles_analyzed--count
        # --total_image_cache_hit_count--total_image_cache_hit_count--count
        # --total_texture_upload_time_by_url
        #
        # About these we are doubtful but we made a guess:
        # --average_num_missing_tiles_by_url--*--units (low is good)
        # --experimental_mean_frame_time_by_url--*--units (low is good)
        # --experimental_median_frame_time_by_url--*--units (low is good)
        # --texture_upload_count--texture_upload_count--count (high is good)
        # --total_deferred_image_decode_count--count (low is good)
        # --total_tiles_analyzed--total_tiles_analyzed--count (high is good)
        lower_is_better_keys = [
            "milliseconds",
            "ms_",
            "seconds_",
            "KB",
            "rdbytes",
            "wrbytes",
            "dropped_percent",
            "(ms)",
            "(seconds)",
            "--ms",
            "--average_num_missing_tiles",
            "--experimental_jank",
            "--experimental_mean_frame",
            "--experimental_median_frame_time",
            "--total_deferred_image_decode_count",
            "--seconds",
            "samples",
            "bytes",
        ]

        return any([l in key for l in lower_is_better_keys])

    def _InvertIfLowerIsBetter(self, cell):
        if self._IsLowerBetter(cell.name):
            if cell.value:
                cell.value = 1.0 / cell.value


class AmeanRatioResult(KeyAwareComparisonResult):
    """Ratio of arithmetic means of values vs. baseline values."""

    def __init__(self, ignore_min_max=False):
        super(AmeanRatioResult, self).__init__()
        self.ignore_min_max = ignore_min_max

    def _ComputeFloat(self, cell, values, baseline_values):
        if self.ignore_min_max:
            values = _RemoveMinMax(cell, values)
            baseline_values = _RemoveMinMax(cell, baseline_values)

        baseline_mean = statistics.mean(baseline_values)
        values_mean = statistics.mean(values)
        if baseline_mean != 0:
            cell.value = values_mean / baseline_mean
        elif values_mean != 0:
            cell.value = 0.00
            # cell.value = 0 means the values and baseline_values have big difference
        else:
            cell.value = 1.00
            # no difference if both values and baseline_values are 0


class GmeanRatioResult(KeyAwareComparisonResult):
    """Ratio of geometric means of values vs. baseline values."""

    def __init__(self, ignore_min_max=False):
        super(GmeanRatioResult, self).__init__()
        self.ignore_min_max = ignore_min_max

    def _ComputeFloat(self, cell, values, baseline_values):
        if self.ignore_min_max:
            values = _RemoveMinMax(cell, values)
            baseline_values = _RemoveMinMax(cell, baseline_values)
        if self._GetGmean(baseline_values) != 0:
            cell.value = self._GetGmean(values) / self._GetGmean(
                baseline_values
            )
        elif self._GetGmean(values) != 0:
            cell.value = 0.00
        else:
            cell.value = 1.00


class Color(object):
    """Class that represents color in RGBA format."""

    def __init__(self, r=0, g=0, b=0, a=0):
        self.r = r
        self.g = g
        self.b = b
        self.a = a

    def __str__(self):
        return "r: %s g: %s: b: %s: a: %s" % (self.r, self.g, self.b, self.a)

    def Round(self):
        """Round RGBA values to the nearest integer."""
        self.r = int(self.r)
        self.g = int(self.g)
        self.b = int(self.b)
        self.a = int(self.a)

    def GetRGB(self):
        """Get a hex representation of the color."""
        return "%02x%02x%02x" % (self.r, self.g, self.b)

    @classmethod
    def Lerp(cls, ratio, a, b):
        """Perform linear interpolation between two colors.

        Args:
          ratio: The ratio to use for linear polation.
          a: The first color object (used when ratio is 0).
          b: The second color object (used when ratio is 1).

        Returns:
          Linearly interpolated color.
        """
        ret = cls()
        ret.r = (b.r - a.r) * ratio + a.r
        ret.g = (b.g - a.g) * ratio + a.g
        ret.b = (b.b - a.b) * ratio + a.b
        ret.a = (b.a - a.a) * ratio + a.a
        return ret


class Format(object):
    """A class that represents the format of a column."""

    def __init__(self):
        pass

    def Compute(self, cell):
        """Computes the attributes of a cell based on its value.

        Attributes typically are color, width, etc.

        Args:
          cell: The cell whose attributes are to be populated.
        """
        if cell.value is None:
            cell.string_value = ""
        if isinstance(cell.value, float):
            self._ComputeFloat(cell)
        else:
            self._ComputeString(cell)

    def _ComputeFloat(self, cell):
        cell.string_value = "{0:.2f}".format(cell.value)

    def _ComputeString(self, cell):
        cell.string_value = str(cell.value)

    def _GetColor(self, value, low, mid, high, power=6, mid_value=1.0):
        min_value = 0.0
        max_value = 2.0
        if math.isnan(value):
            return mid
        if value > mid_value:
            value = max_value - mid_value / value

        return self._GetColorBetweenRange(
            value, min_value, mid_value, max_value, low, mid, high, power
        )

    def _GetColorBetweenRange(
        self,
        value,
        min_value,
        mid_value,
        max_value,
        low_color,
        mid_color,
        high_color,
        power,
    ):
        assert value <= max_value
        assert value >= min_value
        if value > mid_value:
            value = (max_value - value) / (max_value - mid_value)
            value **= power
            ret = Color.Lerp(value, high_color, mid_color)
        else:
            value = (value - min_value) / (mid_value - min_value)
            value **= power
            ret = Color.Lerp(value, low_color, mid_color)
        ret.Round()
        return ret


class PValueFormat(Format):
    """Formatting for p-value."""

    def _ComputeFloat(self, cell):
        cell.string_value = "%0.2f" % float(cell.value)
        if float(cell.value) < 0.05:
            cell.bgcolor = self._GetColor(
                cell.value,
                Color(255, 255, 0, 0),
                Color(255, 255, 255, 0),
                Color(255, 255, 255, 0),
                mid_value=0.05,
                power=1,
            )


class WeightFormat(Format):
    """Formatting for weight in cwp mode."""

    def _ComputeFloat(self, cell):
        cell.string_value = "%0.4f" % float(cell.value)


class StorageFormat(Format):
    """Format the cell as a storage number.

    Examples:
      If the cell contains a value of 1024, the string_value will be 1.0K.
    """

    def _ComputeFloat(self, cell):
        base = 1024
        suffices = ["K", "M", "G"]
        v = float(cell.value)
        current = 0
        while v >= base ** (current + 1) and current < len(suffices):
            current += 1

        if current:
            divisor = base**current
            cell.string_value = "%1.1f%s" % (
                (v / divisor),
                suffices[current - 1],
            )
        else:
            cell.string_value = str(cell.value)


class CoeffVarFormat(Format):
    """Format the cell as a percent.

    Examples:
      If the cell contains a value of 1.5, the string_value will be +150%.
    """

    def _ComputeFloat(self, cell):
        cell.string_value = "%1.1f%%" % (float(cell.value) * 100)
        cell.color = self._GetColor(
            cell.value,
            Color(0, 255, 0, 0),
            Color(0, 0, 0, 0),
            Color(255, 0, 0, 0),
            mid_value=0.02,
            power=1,
        )


class PercentFormat(Format):
    """Format the cell as a percent.

    Examples:
      If the cell contains a value of 1.5, the string_value will be +50%.
    """

    def _ComputeFloat(self, cell):
        cell.string_value = "%+1.1f%%" % ((float(cell.value) - 1) * 100)
        cell.color = self._GetColor(
            cell.value,
            Color(255, 0, 0, 0),
            Color(0, 0, 0, 0),
            Color(0, 255, 0, 0),
        )


class RatioFormat(Format):
    """Format the cell as a ratio.

    Examples:
      If the cell contains a value of 1.5642, the string_value will be 1.56.
    """

    def _ComputeFloat(self, cell):
        cell.string_value = "%+1.1f%%" % ((cell.value - 1) * 100)
        cell.color = self._GetColor(
            cell.value,
            Color(255, 0, 0, 0),
            Color(0, 0, 0, 0),
            Color(0, 255, 0, 0),
        )


class ColorBoxFormat(Format):
    """Format the cell as a color box.

    Examples:
      If the cell contains a value of 1.5, it will get a green color.
      If the cell contains a value of 0.5, it will get a red color.
      The intensity of the green/red will be determined by how much above or below
      1.0 the value is.
    """

    def _ComputeFloat(self, cell):
        cell.string_value = "--"
        bgcolor = self._GetColor(
            cell.value,
            Color(255, 0, 0, 0),
            Color(255, 255, 255, 0),
            Color(0, 255, 0, 0),
        )
        cell.bgcolor = bgcolor
        cell.color = bgcolor


class Cell(object):
    """A class to represent a cell in a table.

    Attributes:
      value: The raw value of the cell.
      color: The color of the cell.
      bgcolor: The background color of the cell.
      string_value: The string value of the cell.
      suffix: A string suffix to be attached to the value when displaying.
      prefix: A string prefix to be attached to the value when displaying.
      color_row: Indicates whether the whole row is to inherit this cell's color.
      bgcolor_row: Indicates whether the whole row is to inherit this cell's
      bgcolor.
      width: Optional specifier to make a column narrower than the usual width.
      The usual width of a column is the max of all its cells widths.
      colspan: Set the colspan of the cell in the HTML table, this is used for
      table headers. Default value is 1.
      name: the test name of the cell.
      header: Whether this is a header in html.
    """

    def __init__(self):
        self.value = None
        self.color = None
        self.bgcolor = None
        self.string_value = None
        self.suffix = None
        self.prefix = None
        # Entire row inherits this color.
        self.color_row = False
        self.bgcolor_row = False
        self.width = 0
        self.colspan = 1
        self.name = None
        self.header = False

    def __str__(self):
        l = []
        l.append("value: %s" % self.value)
        l.append("string_value: %s" % self.string_value)
        return " ".join(l)


class Column(object):
    """Class representing a column in a table.

    Attributes:
      result: an object of the Result class.
      fmt: an object of the Format class.
    """

    def __init__(self, result, fmt, name=""):
        self.result = result
        self.fmt = fmt
        self.name = name


# Takes in:
# ["Key", "Label1", "Label2"]
# ["k", ["v", "v2"], [v3]]
# etc.
# Also takes in a format string.
# Returns a table like:
# ["Key", "Label1", "Label2"]
# ["k", avg("v", "v2"), stddev("v", "v2"), etc.]]
# according to format string
class TableFormatter(object):
    """Class to convert a plain table into a cell-table.

    This class takes in a table generated by TableGenerator and a list of column
    formats to apply to the table and returns a table of cells.
    """

    def __init__(self, table, columns, samples_table=False):
        """The constructor takes in a table and a list of columns.

        Args:
          table: A list of lists of values.
          columns: A list of column containing what to produce and how to format
                   it.
          samples_table: A flag to check whether we are generating a table of
                         samples in CWP apporximation mode.
        """
        self._table = table
        self._columns = columns
        self._samples_table = samples_table
        self._table_columns = []
        self._out_table = []

    def GenerateCellTable(self, table_type):
        row_index = 0
        all_failed = False

        for row in self._table[1:]:
            # If we are generating samples_table, the second value will be weight
            # rather than values.
            start_col = 2 if self._samples_table else 1
            # It does not make sense to put retval in the summary table.
            if str(row[0]) == "retval" and table_type == "summary":
                # Check to see if any runs passed, and update all_failed.
                all_failed = True
                for values in row[start_col:]:
                    if 0 in values:
                        all_failed = False
                continue
            key = Cell()
            key.string_value = str(row[0])
            out_row = [key]
            if self._samples_table:
                # Add one column for weight if in samples_table mode
                weight = Cell()
                weight.value = row[1]
                f = WeightFormat()
                f.Compute(weight)
                out_row.append(weight)
            baseline = None
            for results in row[start_col:]:
                column_start = 0
                values = None
                # If generating sample table, we will split a tuple of iterations info
                # from the results
                if isinstance(results, tuple):
                    it, values = results
                    column_start = 1
                    cell = Cell()
                    cell.string_value = "[%d: %d]" % (it[0], it[1])
                    out_row.append(cell)
                    if not row_index:
                        self._table_columns.append(self._columns[0])
                else:
                    values = results
                # Parse each column
                for column in self._columns[column_start:]:
                    cell = Cell()
                    cell.name = key.string_value
                    if (
                        not column.result.NeedsBaseline()
                        or baseline is not None
                    ):
                        column.result.Compute(cell, values, baseline)
                        column.fmt.Compute(cell)
                        out_row.append(cell)
                        if not row_index:
                            self._table_columns.append(column)

                if baseline is None:
                    baseline = values
            self._out_table.append(out_row)
            row_index += 1

        # If this is a summary table, and the only row in it is 'retval', and
        # all the test runs failed, we need to a 'Results' row to the output
        # table.
        if table_type == "summary" and all_failed and len(self._table) == 2:
            labels_row = self._table[0]
            key = Cell()
            key.string_value = "Results"
            out_row = [key]
            baseline = None
            for _ in labels_row[1:]:
                for column in self._columns:
                    cell = Cell()
                    cell.name = key.string_value
                    column.result.Compute(cell, ["Fail"], baseline)
                    column.fmt.Compute(cell)
                    out_row.append(cell)
                    if not row_index:
                        self._table_columns.append(column)
            self._out_table.append(out_row)

    def AddColumnName(self):
        """Generate Column name at the top of table."""
        key = Cell()
        key.header = True
        key.string_value = "Keys" if not self._samples_table else "Benchmarks"
        header = [key]
        if self._samples_table:
            weight = Cell()
            weight.header = True
            weight.string_value = "Weights"
            header.append(weight)
        for column in self._table_columns:
            cell = Cell()
            cell.header = True
            if column.name:
                cell.string_value = column.name
            else:
                result_name = column.result.__class__.__name__
                format_name = column.fmt.__class__.__name__

                cell.string_value = "%s %s" % (
                    result_name.replace("Result", ""),
                    format_name.replace("Format", ""),
                )

            header.append(cell)

        self._out_table = [header] + self._out_table

    def AddHeader(self, s):
        """Put additional string on the top of the table."""
        cell = Cell()
        cell.header = True
        cell.string_value = str(s)
        header = [cell]
        colspan = max(1, max(len(row) for row in self._table))
        cell.colspan = colspan
        self._out_table = [header] + self._out_table

    def GetPassesAndFails(self, values):
        passes = 0
        fails = 0
        for val in values:
            if val == 0:
                passes = passes + 1
            else:
                fails = fails + 1
        return passes, fails

    def AddLabelName(self):
        """Put label on the top of the table."""
        top_header = []
        base_colspan = len(
            [c for c in self._columns if not c.result.NeedsBaseline()]
        )
        compare_colspan = len(self._columns)
        # Find the row with the key 'retval', if it exists.  This
        # will be used to calculate the number of iterations that passed and
        # failed for each image label.
        retval_row = None
        for row in self._table:
            if row[0] == "retval":
                retval_row = row
        # The label is organized as follows
        # "keys" label_base, label_comparison1, label_comparison2
        # The first cell has colspan 1, the second is base_colspan
        # The others are compare_colspan
        column_position = 0
        for label in self._table[0]:
            cell = Cell()
            cell.header = True
            # Put the number of pass/fail iterations in the image label header.
            if column_position > 0 and retval_row:
                retval_values = retval_row[column_position]
                if isinstance(retval_values, list):
                    passes, fails = self.GetPassesAndFails(retval_values)
                    cell.string_value = str(label) + "  (pass:%d fail:%d)" % (
                        passes,
                        fails,
                    )
                else:
                    cell.string_value = str(label)
            else:
                cell.string_value = str(label)
            if top_header:
                if not self._samples_table or (
                    self._samples_table and len(top_header) == 2
                ):
                    cell.colspan = base_colspan
            if len(top_header) > 1:
                if not self._samples_table or (
                    self._samples_table and len(top_header) > 2
                ):
                    cell.colspan = compare_colspan
            top_header.append(cell)
            column_position = column_position + 1
        self._out_table = [top_header] + self._out_table

    def _PrintOutTable(self):
        o = ""
        for row in self._out_table:
            for cell in row:
                o += str(cell) + " "
            o += "\n"
        print(o)

    def GetCellTable(self, table_type="full", headers=True):
        """Function to return a table of cells.

        The table (list of lists) is converted into a table of cells by this
        function.

        Args:
          table_type: Can be 'full' or 'summary'
          headers: A boolean saying whether we want default headers

        Returns:
          A table of cells with each cell having the properties and string values as
          requiested by the columns passed in the constructor.
        """
        # Generate the cell table, creating a list of dynamic columns on the fly.
        if not self._out_table:
            self.GenerateCellTable(table_type)
        if headers:
            self.AddColumnName()
            self.AddLabelName()
        return self._out_table


class TablePrinter(object):
    """Class to print a cell table to the console, file or html."""

    PLAIN = 0
    CONSOLE = 1
    HTML = 2
    TSV = 3
    EMAIL = 4

    def __init__(self, table, output_type):
        """Constructor that stores the cell table and output type."""
        self._table = table
        self._output_type = output_type
        self._row_styles = []
        self._column_styles = []

    # Compute whole-table properties like max-size, etc.
    def _ComputeStyle(self):
        self._row_styles = []
        for row in self._table:
            row_style = Cell()
            for cell in row:
                if cell.color_row:
                    assert cell.color, "Cell color not set but color_row set!"
                    assert (
                        not row_style.color
                    ), "Multiple row_style.colors found!"
                    row_style.color = cell.color
                if cell.bgcolor_row:
                    assert (
                        cell.bgcolor
                    ), "Cell bgcolor not set but bgcolor_row set!"
                    assert (
                        not row_style.bgcolor
                    ), "Multiple row_style.bgcolors found!"
                    row_style.bgcolor = cell.bgcolor
            self._row_styles.append(row_style)

        self._column_styles = []
        if len(self._table) < 2:
            return

        for i in range(max(len(row) for row in self._table)):
            column_style = Cell()
            for row in self._table:
                if not any([cell.colspan != 1 for cell in row]):
                    column_style.width = max(
                        column_style.width, len(row[i].string_value)
                    )
            self._column_styles.append(column_style)

    def _GetBGColorFix(self, color):
        if self._output_type == self.CONSOLE:
            prefix = misc.rgb2short(color.r, color.g, color.b)
            # pylint: disable=anomalous-backslash-in-string
            prefix = "\033[48;5;%sm" % prefix
            suffix = "\033[0m"
        elif self._output_type in [self.EMAIL, self.HTML]:
            rgb = color.GetRGB()
            prefix = '<FONT style="BACKGROUND-COLOR:#{0}">'.format(rgb)
            suffix = "</FONT>"
        elif self._output_type in [self.PLAIN, self.TSV]:
            prefix = ""
            suffix = ""
        return prefix, suffix

    def _GetColorFix(self, color):
        if self._output_type == self.CONSOLE:
            prefix = misc.rgb2short(color.r, color.g, color.b)
            # pylint: disable=anomalous-backslash-in-string
            prefix = "\033[38;5;%sm" % prefix
            suffix = "\033[0m"
        elif self._output_type in [self.EMAIL, self.HTML]:
            rgb = color.GetRGB()
            prefix = "<FONT COLOR=#{0}>".format(rgb)
            suffix = "</FONT>"
        elif self._output_type in [self.PLAIN, self.TSV]:
            prefix = ""
            suffix = ""
        return prefix, suffix

    def Print(self):
        """Print the table to a console, html, etc.

        Returns:
          A string that contains the desired representation of the table.
        """
        self._ComputeStyle()
        return self._GetStringValue()

    def _GetCellValue(self, i, j):
        cell = self._table[i][j]
        out = cell.string_value
        raw_width = len(out)

        if cell.color:
            p, s = self._GetColorFix(cell.color)
            out = "%s%s%s" % (p, out, s)

        if cell.bgcolor:
            p, s = self._GetBGColorFix(cell.bgcolor)
            out = "%s%s%s" % (p, out, s)

        if self._output_type in [self.PLAIN, self.CONSOLE, self.EMAIL]:
            if cell.width:
                width = cell.width
            else:
                if self._column_styles:
                    width = self._column_styles[j].width
                else:
                    width = len(cell.string_value)
            if cell.colspan > 1:
                width = 0
                start = 0
                for k in range(j):
                    start += self._table[i][k].colspan
                for k in range(cell.colspan):
                    width += self._column_styles[start + k].width
            if width > raw_width:
                padding = ("%" + str(width - raw_width) + "s") % ""
                out = padding + out

        if self._output_type == self.HTML:
            if cell.header:
                tag = "th"
            else:
                tag = "td"
            out = '<{0} colspan = "{2}"> {1} </{0}>'.format(
                tag, out, cell.colspan
            )

        return out

    def _GetHorizontalSeparator(self):
        if self._output_type in [self.CONSOLE, self.PLAIN, self.EMAIL]:
            return " "
        if self._output_type == self.HTML:
            return ""
        if self._output_type == self.TSV:
            return "\t"

    def _GetVerticalSeparator(self):
        if self._output_type in [
            self.PLAIN,
            self.CONSOLE,
            self.TSV,
            self.EMAIL,
        ]:
            return "\n"
        if self._output_type == self.HTML:
            return "</tr>\n<tr>"

    def _GetPrefix(self):
        if self._output_type in [
            self.PLAIN,
            self.CONSOLE,
            self.TSV,
            self.EMAIL,
        ]:
            return ""
        if self._output_type == self.HTML:
            return '<p></p><table id="box-table-a">\n<tr>'

    def _GetSuffix(self):
        if self._output_type in [
            self.PLAIN,
            self.CONSOLE,
            self.TSV,
            self.EMAIL,
        ]:
            return ""
        if self._output_type == self.HTML:
            return "</tr>\n</table>"

    def _GetStringValue(self):
        o = ""
        o += self._GetPrefix()
        for i in range(len(self._table)):
            row = self._table[i]
            # Apply row color and bgcolor.
            p = s = bgp = bgs = ""
            if self._row_styles[i].bgcolor:
                bgp, bgs = self._GetBGColorFix(self._row_styles[i].bgcolor)
            if self._row_styles[i].color:
                p, s = self._GetColorFix(self._row_styles[i].color)
            o += p + bgp
            for j in range(len(row)):
                out = self._GetCellValue(i, j)
                o += out + self._GetHorizontalSeparator()
            o += s + bgs
            o += self._GetVerticalSeparator()
        o += self._GetSuffix()
        return o


# Some common drivers
def GetSimpleTable(table, out_to=TablePrinter.CONSOLE):
    """Prints a simple table.

    This is used by code that has a very simple list-of-lists and wants to
    produce a table with ameans, a percentage ratio of ameans and a colorbox.

    Examples:
      GetSimpleConsoleTable([["binary", "b1", "b2"],["size", "300", "400"]])
      will produce a colored table that can be printed to the console.

    Args:
      table: a list of lists.
      out_to: specify the fomat of output. Currently it supports HTML and CONSOLE.

    Returns:
      A string version of the table that can be printed to the console.
    """
    columns = [
        Column(AmeanResult(), Format()),
        Column(AmeanRatioResult(), PercentFormat()),
        Column(AmeanRatioResult(), ColorBoxFormat()),
    ]
    our_table = [table[0]]
    for row in table[1:]:
        our_row = [row[0]]
        for v in row[1:]:
            our_row.append([v])
        our_table.append(our_row)

    tf = TableFormatter(our_table, columns)
    cell_table = tf.GetCellTable()
    tp = TablePrinter(cell_table, out_to)
    return tp.Print()


# pylint: disable=redefined-outer-name
def GetComplexTable(runs, labels, out_to=TablePrinter.CONSOLE):
    """Prints a complex table.

    This can be used to generate a table with arithmetic mean, standard deviation,
    coefficient of variation, p-values, etc.

    Args:
      runs: A list of lists with data to tabulate.
      labels: A list of labels that correspond to the runs.
      out_to: specifies the format of the table (example CONSOLE or HTML).

    Returns:
      A string table that can be printed to the console or put in an HTML file.
    """
    tg = TableGenerator(runs, labels, TableGenerator.SORT_BY_VALUES_DESC)
    table = tg.GetTable()
    columns = [
        Column(LiteralResult(), Format(), "Literal"),
        Column(AmeanResult(), Format()),
        Column(StdResult(), Format()),
        Column(CoeffVarResult(), CoeffVarFormat()),
        Column(NonEmptyCountResult(), Format()),
        Column(AmeanRatioResult(), PercentFormat()),
        Column(AmeanRatioResult(), RatioFormat()),
        Column(GmeanRatioResult(), RatioFormat()),
        Column(PValueResult(), PValueFormat()),
    ]
    tf = TableFormatter(table, columns)
    cell_table = tf.GetCellTable()
    tp = TablePrinter(cell_table, out_to)
    return tp.Print()


if __name__ == "__main__":
    # Run a few small tests here.
    run1 = {
        "k1": "10",
        "k2": "12",
        "k5": "40",
        "k6": "40",
        "ms_1": "20",
        "k7": "FAIL",
        "k8": "PASS",
        "k9": "PASS",
        "k10": "0",
    }
    run2 = {
        "k1": "13",
        "k2": "14",
        "k3": "15",
        "ms_1": "10",
        "k8": "PASS",
        "k9": "FAIL",
        "k10": "0",
    }
    run3 = {
        "k1": "50",
        "k2": "51",
        "k3": "52",
        "k4": "53",
        "k5": "35",
        "k6": "45",
        "ms_1": "200",
        "ms_2": "20",
        "k7": "FAIL",
        "k8": "PASS",
        "k9": "PASS",
    }
    runs = [[run1, run2], [run3]]
    labels = ["vanilla", "modified"]
    t = GetComplexTable(runs, labels, TablePrinter.CONSOLE)
    print(t)
    email = GetComplexTable(runs, labels, TablePrinter.EMAIL)

    runs = [
        [{"k1": "1"}, {"k1": "1.1"}, {"k1": "1.2"}],
        [{"k1": "5"}, {"k1": "5.1"}, {"k1": "5.2"}],
    ]
    t = GetComplexTable(runs, labels, TablePrinter.CONSOLE)
    print(t)

    simple_table = [
        ["binary", "b1", "b2", "b3"],
        ["size", 100, 105, 108],
        ["rodata", 100, 80, 70],
        ["data", 100, 100, 100],
        ["debug", 100, 140, 60],
    ]
    t = GetSimpleTable(simple_table)
    print(t)
    email += GetSimpleTable(simple_table, TablePrinter.HTML)
    email_to = [getpass.getuser()]
    email = "<pre style='font-size: 13px'>%s</pre>" % email
    EmailSender().SendEmail(email_to, "SimpleTableTest", email, msg_type="html")