#!/usr/bin/env python
#
# Copyright 2016 Google Inc.  All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""A program for analyzing the Shaka compiled sources.

This can be used to find areas that can be removed if not needed.  This uses
the source map (i.e. shaka-player.compiled.debug.map) to find the compiled code
size, see:
    https://github.com/mattrobenolt/python-sourcemap
    http://www.html5rocks.com/en/tutorials/developertools/sourcemaps/

This script can output four different stats in two different formats:
- The size of functions and namespaces.
- The dependencies between types (in plain or DOT format).
- The dependencies between functions (in plain or DOT format).
- All tokens in the source map.

The dependencies can be outputted in DOT format which can be used with graph
programs to display a visual layout of the dependencies.
"""

import json
import logging
import math
import os
import string
import sys

import shakaBuildHelpers


# A Base64 VLQ digit can represent 5 bits, so it is Base32.
VLQ_BASE_SHIFT = 5
VLQ_BASE = 1 << VLQ_BASE_SHIFT

# A mask of bits for a VLQ digit (11111), 31 decimal
VLQ_BASE_MASK = VLQ_BASE - 1

# The continuation bit is the 6th bit
VLQ_CONTINUATION_BIT = VLQ_BASE

# Don't use Base64 lib since it is not a real Base64 string; it simply
# decodes each character to a single Base64 number.
B64 = dict((c, i) for i, c in
           enumerate('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
                     '0123456789+/'))


def from_vlq_signed(value):
  """Converts a VLQ number to a normal signed number.

  Args:
    value: A number decoded from a VLQ string.

  Returns:
    an integer.
  """
  negative = (value & 1) == 1
  value >>= 1
  return -value if negative else value


class Segment(object):
  """Defines an entry in the source map.

  Members:
    dst_col_offset - The offset of the destination column from the previous
      segment.
    name_offset - If not None, the offset of the name index from the previous
      segment.
  """

  def __init__(self, data):
    self.dst_col_offset = data[0]
    self.name_offset = data[4] if len(data) > 4 else None


def decode_segment(segment):
  """Decodes VLQ values from the given segment.

  Args:
    segment: A string containing the encoded segment text.

  Returns:
    the parsed Segment.
  """

  values = []
  cur, shift = 0, 0

  for c in segment:
    digit = B64[c]
    cont = (digit & VLQ_CONTINUATION_BIT) != 0
    digit &= VLQ_BASE_MASK
    cur += digit << shift
    shift += VLQ_BASE_SHIFT

    if not cont:
      values.append(from_vlq_signed(cur))
      cur, shift = 0, 0

  # A valid VLQ string should not have dangling bits.
  assert cur == 0
  assert shift == 0
  return Segment(values)


class Token(object):
  """A Token represents one JavaScript symbol.

  For example, this can be a variable or an equals sign.  If this is a variable
  or the keyword 'function' it will usually have a name which indicates what it
  originally was defined. But there are also tokens such as ; and ( which appear
  as tokens in the map but to not have explicit name (see isFunction).

  Members:
      dst_line - Line index in compiled code
      dst_col - Column index in compiled code
      name - Name of the token; or None
  """

  def __init__(self, dst_line, dst_col, name=None):
    self.dst_line = dst_line
    self.dst_col = dst_col
    self.name = name

  def __str__(self):
    return str(self.name)


def decode_mappings(line_data, names):
  """Decodes a mappings line of text.

  Args:
    line_data: A string containing the mapping line.
    names: An array of strings containing the names of the objects.

  Returns:
    a list of Tokens
  """

  tokens = []

  lines = line_data.split(';')
  name_id = 0
  for dst_line, line in enumerate(lines):
    dst_col = 0
    segments = line.split(',')
    for segment in segments:
      if not segment:
        continue

      segment = decode_segment(segment)
      dst_col += segment.dst_col_offset

      # segment.dst_col can be negative (more useful in names below); however
      # after applying a negative offset, the result must still be positive.
      assert dst_col >= 0

      name = None
      if segment.name_offset is not None:
        name_id += segment.name_offset
        assert name_id >= 0
        name = names[name_id]

      tokens.append(Token(dst_line, dst_col, name))

  return tokens


def is_function(token, lines):
  """Determines if the given token is the start of a function.

  All function definitions are assumed to have a name field and the token in
  the compiled source is the keyword 'function'. Sometimes the function is
  defined on the previous semicolon and sometimes that semicolon appears on
  the previous line.

  Args:
    token: The Token to check.
    lines: An array of compiled code lines.

  Returns:
    whether the token is a function.
  """

  # All functions have a name.
  if not token.name:
    return False

  # Sometimes a function token starts with the previous ;
  # Also sometimes the token starts on the ; that is on the previous
  # line.
  partial_line = lines[token.dst_line][token.dst_col:]
  if partial_line == ';\n':
    if len(lines) == token.dst_line + 1:
      return False
    else:
      return lines[token.dst_line + 1].startswith('function')
  else:
    return (partial_line.startswith('function') or
            partial_line.startswith(';function'))


def read_function(token_iter, prev, prev_index, lines, callback):