#!/usr/bin/env python
# Copyright 2014 The Chromium Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""Generate a spatial analysis against an arbitrary library.

To use, build the 'binary_size_tool' target. Then run this tool, passing
in the location of the library to be analyzed along with any other options
you desire.
"""

import collections
import json
import logging
import multiprocessing
import optparse
import os
import re
import shutil
import subprocess
import sys
import tempfile
import time

import binary_size_utils

# This path changee is not beautiful. Temporary (I hope) measure until
# the chromium project has figured out a proper way to organize the
# library of python tools. http://crbug.com/375725
elf_symbolizer_path = os.path.abspath(os.path.join(
    os.path.dirname(__file__),
    '..',
    '..',
    'build',
    'android',
    'pylib'))
sys.path.append(elf_symbolizer_path)
import symbols.elf_symbolizer as elf_symbolizer  # pylint: disable=F0401


# Node dictionary keys. These are output in json read by the webapp so
# keep them short to save file size.
# Note: If these change, the webapp must also change.
NODE_TYPE_KEY = 'k'
NODE_NAME_KEY = 'n'
NODE_CHILDREN_KEY = 'children'
NODE_SYMBOL_TYPE_KEY = 't'
NODE_SYMBOL_SIZE_KEY = 'value'
NODE_MAX_DEPTH_KEY = 'maxDepth'
NODE_LAST_PATH_ELEMENT_KEY = 'lastPathElement'

# The display name of the bucket where we put symbols without path.
NAME_NO_PATH_BUCKET = '(No Path)'

# Try to keep data buckets smaller than this to avoid killing the
# graphing lib.
BIG_BUCKET_LIMIT = 3000


# TODO(andrewhayden): Only used for legacy reports. Delete.
def FormatBytes(byte_count):
  """Pretty-print a number of bytes."""
  if byte_count > 1e6:
    byte_count = byte_count / 1.0e6
    return '%.1fm' % byte_count
  if byte_count > 1e3:
    byte_count = byte_count / 1.0e3
    return '%.1fk' % byte_count
  return str(byte_count)


# TODO(andrewhayden): Only used for legacy reports. Delete.
def SymbolTypeToHuman(symbol_type):
  """Convert a symbol type as printed by nm into a human-readable name."""
  return {'b': 'bss',
          'd': 'data',
          'r': 'read-only data',
          't': 'code',
          'w': 'weak symbol',
          'v': 'weak symbol'}[symbol_type]


def _MkChild(node, name):
  child = node[NODE_CHILDREN_KEY].get(name)
  if child is None:
    child = {NODE_NAME_KEY: name,
             NODE_CHILDREN_KEY: {}}
    node[NODE_CHILDREN_KEY][name] = child
  return child



def SplitNoPathBucket(node):
  """NAME_NO_PATH_BUCKET can be too large for the graphing lib to
  handle. Split it into sub-buckets in that case."""
  root_children = node[NODE_CHILDREN_KEY]
  if NAME_NO_PATH_BUCKET in root_children:
    no_path_bucket = root_children[NAME_NO_PATH_BUCKET]
    old_children = no_path_bucket[NODE_CHILDREN_KEY]
    count = 0
    for symbol_type, symbol_bucket in old_children.iteritems():
      count += len(symbol_bucket[NODE_CHILDREN_KEY])
    if count > BIG_BUCKET_LIMIT:
      new_children = {}
      no_path_bucket[NODE_CHILDREN_KEY] = new_children
      current_bucket = None
      index = 0
      for symbol_type, symbol_bucket in old_children.iteritems():
        for symbol_name, value in symbol_bucket[NODE_CHILDREN_KEY].iteritems():
          if index % BIG_BUCKET_LIMIT == 0:
            group_no = (index / BIG_BUCKET_LIMIT) + 1
            current_bucket = _MkChild(no_path_bucket,
                                      '%s subgroup %d' % (NAME_NO_PATH_BUCKET,
                                                          group_no))
            assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'p'
            node[NODE_TYPE_KEY] = 'p'  # p for path
          index += 1
          symbol_size = value[NODE_SYMBOL_SIZE_KEY]
          AddSymbolIntoFileNode(current_bucket, symbol_type,
                                symbol_name, symbol_size)


def MakeChildrenDictsIntoLists(node):
  largest_list_len = 0
  if NODE_CHILDREN_KEY in node:
    largest_list_len = len(node[NODE_CHILDREN_KEY])
    child_list = []
    for child in node[NODE_CHILDREN_KEY].itervalues():
      child_largest_list_len = MakeChildrenDictsIntoLists(child)
      if child_largest_list_len > largest_list_len:
        largest_list_len = child_largest_list_len
      child_list.append(child)
    node[NODE_CHILDREN_KEY] = child_list

  return largest_list_len


def AddSymbolIntoFileNode(node, symbol_type, symbol_name, symbol_size):
  """Puts symbol into the file path node |node|.
  Returns the number of added levels in tree. I.e. returns 2."""

  # 'node' is the file node and first step is to find its symbol-type bucket.
  node[NODE_LAST_PATH_ELEMENT_KEY] = True
  node = _MkChild(node, symbol_type)
  assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'b'
  node[NODE_SYMBOL_TYPE_KEY] = symbol_type
  node[NODE_TYPE_KEY] = 'b'  # b for bucket

  # 'node' is now the symbol-type bucket. Make the child entry.
  node = _MkChild(node, symbol_name)
  if NODE_CHILDREN_KEY in node:
    if node[NODE_CHILDREN_KEY]:
      logging.warning('A container node used as symbol for %s.' % symbol_name)
    # This is going to be used as a leaf so no use for child list.
    del node[NODE_CHILDREN_KEY]
  node[NODE_SYMBOL_SIZE_KEY] = symbol_size
  node[NODE_SYMBOL_TYPE_KEY] = symbol_type
  node[NODE_TYPE_KEY] = 's'  # s for symbol

  return 2  # Depth of the added subtree.


def MakeCompactTree(symbols):
  result = {NODE_NAME_KEY: '/',
            NODE_CHILDREN_KEY: {},
            NODE_TYPE_KEY: 'p',
            NODE_MAX_DEPTH_KEY: 0}
  seen_symbol_with_path = False
  for symbol_name, symbol_type, symbol_size, file_path in symbols:

    if 'vtable for ' in symbol_name:
      symbol_type = '@'  # hack to categorize these separately
    # Take path like '/foo/bar/baz', convert to ['foo', 'bar', 'baz']
    if file_path:
      file_path = os.path.normpath(file_path)
      seen_symbol_with_path = True
    else:
      file_path = NAME_NO_PATH_BUCKET

    if file_path.startswith('/'):
      file_path = file_path[1:]
    path_parts = file_path.split('/')

    # Find pre-existing node in tree, or update if it already exists
    node = result
    depth = 0
    while len(path_parts) > 0:
      path_part = path_parts.pop(0)
      if len(path_part) == 0:
        continue
      depth += 1
      node = _MkChild(node, path_part)
      assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'p'
      node[NODE_TYPE_KEY] = 'p'  # p for path

    depth += AddSymbolIntoFileNode(node, symbol_type, symbol_name, symbol_size)
    result[NODE_MAX_DEPTH_KEY] = max(result[NODE_MAX_DEPTH_KEY], depth)

  if not seen_symbol_with_path:
    logging.warning('Symbols lack paths. Data will not be structured.')

  # The (no path) bucket can be extremely large if we failed to get
  # path information. Split it into subgroups if needed.
  SplitNoPathBucket(result)

  largest_list_len = MakeChildrenDictsIntoLists(result)

  if largest_list_len > BIG_BUCKET_LIMIT:
    logging.warning('There are sections with %d nodes. '
                    'Results might be unusable.' % largest_list_len)
  return result


# TODO(andrewhayden): Only used for legacy reports. Delete.
def TreeifySymbols(symbols):
  """Convert symbols into a path-based tree, calculating size information