// Copyright (c) 2020, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

/// Classes for representing information about the program structure.
library vm_snapshot_analysis.program_info;

import 'package:vm_snapshot_analysis/v8_profile.dart';

/// Represents information about compiled program.
class ProgramInfo {
  static const int rootId = 0;
  static const int stubsId = 1;
  static const int unknownId = 2;

  final ProgramInfoNode root;
  final ProgramInfoNode stubs;
  final ProgramInfoNode unknown;
  int _nextId = 3;

  /// V8 snapshot profile if this [ProgramInfo] object was created from an
  /// output of `--write-v8-snapshot-profile-to=...` flag.
  SnapshotInfo? snapshotInfo;

  ProgramInfo._(this.root, this.stubs, this.unknown);

  factory ProgramInfo() {
    final ProgramInfoNode root = ProgramInfoNode._(
        id: rootId, name: '@shared', type: NodeType.libraryNode, parent: null);

    final ProgramInfoNode stubs = ProgramInfoNode._(
        id: stubsId, name: '@stubs', type: NodeType.libraryNode, parent: root);
    root.children[stubs.name] = stubs;

    final ProgramInfoNode unknown = ProgramInfoNode._(
        id: unknownId,
        name: '@unknown',
        type: NodeType.libraryNode,
        parent: root);
    root.children[unknown.name] = unknown;

    return ProgramInfo._(root, stubs, unknown);
  }

  ProgramInfoNode makeNode(
      {required String name,
      required ProgramInfoNode parent,
      required NodeType type}) {
    return parent.children.putIfAbsent(
        name,
        () => ProgramInfoNode._(
            id: _nextId++, name: name, parent: parent, type: type));
  }

  /// Recursively visit all function nodes, which have [FunctionInfo.info]
  /// populated.
  void visit(
      void Function(String? pkg, String lib, String? cls, String? fun,
              ProgramInfoNode n)
          callback) {
    final context = List<String?>.filled(NodeType.values.length, null);

    void recurse(ProgramInfoNode node) {
      final prevContext = context[node._type];
      if (prevContext != null && node._type == NodeType.functionNode.index) {
        context[node._type] = '${prevContext}.${node.name}';
      } else {
        context[node._type] = node.name;
      }

      final pkg = context[NodeType.packageNode.index];
      final lib = context[NodeType.libraryNode.index];
      final cls = context[NodeType.classNode.index];
      final mem = context[NodeType.functionNode.index];
      callback(pkg, lib!, cls, mem, node);

      for (var child in node.children.values) {
        recurse(child);
      }

      context[node._type] = prevContext;
    }

    recurse(root);
  }

  /// Total size of all the nodes in the program.
  int get totalSize => root.totalSize;

  /// Convert this program info to a JSON map using [infoToJson] to convert
  /// data attached to nodes into its JSON representation.
  Map<String, dynamic> toJson() => root.toJson();

  /// Lookup a node in the program given a path to it.
  ProgramInfoNode? lookup(List<String> path) {
    var n = root;
    for (var p in path) {
      final next = n.children[p];
      if (next == null) {
        return null;
      }
      n = next;
    }
    return n;
  }
}

enum NodeType {
  packageNode,
  libraryNode,
  classNode,
  functionNode,
  other,
}

String _typeToJson(NodeType type) => const {
      NodeType.packageNode: 'package',
      NodeType.libraryNode: 'library',
      NodeType.classNode: 'class',
      NodeType.functionNode: 'function',
      NodeType.other: 'other',
    }[type]!;

class ProgramInfoNode {
  final int id;
  final String name;
  final ProgramInfoNode? parent;
  final Map<String, ProgramInfoNode> children = {};
  final int _type;

  /// Number of bytes in the snapshot which can be attributed to this node.
  ///
  /// Note that this is neither a shallow size of the object that represents
  /// this node in the AOT snapshot, nor a cumulative size of its children.
  /// Instead this size is similar to _retained size_ used by heap profiling
  /// tools. Snapshot nodes corresponding to the info nodes are viewed as
  /// a dominator tree and all nodes in the snapshot are partitioned based
  /// on which node of this tree dominates them.
  ///
  /// Consider for example the following Dart code:
  ///
  ///     ```dart
  ///     class C {
  ///       void f() { use("something"); }
  ///       void g() { use("something"); }
  ///     }
  ///     ```
  ///
  /// Assuming that both `C.f` and `C.g` are included into AOT snapshot
  /// and string `"something"` does not occur anywhere else in the program
  /// then the size of `"something"` is going to be attributed to `C`.
  int? size;

  ProgramInfoNode._(
      {required this.id,
      required this.name,
      required this.parent,
      required NodeType type})
      : _type = type.index;

  NodeType get type => NodeType.values[_type];

  Map<String, dynamic> toJson() => {
        if (size != null) '#size': size,
        if (_type != NodeType.other.index) '#type': _typeToJson(type),
        if (children.isNotEmpty)
          for (var clo in children.entries) clo.key: clo.value.toJson()
      };

  /// Returns the name of this node prefixed by the [qualifiedName] of its
  /// [parent].
  String get qualifiedName {
    var prefix = '';
    // Do not include root name or package name (library uri already contains
    // package name).
    final p = parent;
    if (p != null && p.parent != null && p.type != NodeType.packageNode) {
      prefix = p.qualifiedName;
      if (p.type != NodeType.libraryNode) {
        prefix += '.';
      } else {
        prefix += '::';
      }
    }
    return '$prefix$name';
  }

  @override
  String toString() {
    return '${_typeToJson(type)} ${qualifiedName}';
  }

  /// Returns path to this node such that [ProgramInfo.lookup] would return
  /// this node given its [path].
  List<String> get path {
    final result = <String>[];
    var n = this;
    while (n.parent != null) {
      result.add(n.name);
      n = n.parent!;
    }
    return result.reversed.toList();
  }

  /// Cumulative size of this node and all of its children.
  int get totalSize {
    return (size ?? 0) +
        children.values.fold<int>(0, (s, n) => s + n.totalSize);
  }
}

/// Computes the size difference between two [ProgramInfo].
ProgramInfo computeDiff(ProgramInfo oldInfo, ProgramInfo newInfo) {
  final programDiff = ProgramInfo();

  var path = <Object>[];
  void recurse(ProgramInfoNode? oldNode, ProgramInfoNode? newNode) {
    if (oldNode?.size != newNode?.size) {
      var diffNode = programDiff.root;
      for (var i = 0; i < path.length; i += 2) {
        final name = path[i] as String;
        final type = path[i + 1] as NodeType;
        diffNode =
            programDiff.makeNode(name: name, parent: diffNode, type: type);
      }
      diffNode.size =
          (diffNode.size ?? 0) + (newNode?.size ?? 0) - (oldNode?.size ?? 0);
    }

    for (var key in _allKeys(newNode?.children, oldNode?.children)) {
      final newChildNode = newNode != null ? newNode.children[key] : null;
      final oldChildNode = oldNode != null ? oldNode.children[key] : null;
      path.add(key);
      path.add((oldChildNode?.type ?? newChildNode?.type)!);
      recurse(oldChildNode, newChildNode);
      path.removeLast();
      path.removeLast();
    }
  }

  recurse(oldInfo.root, newInfo.root);

  return programDiff;
}

Iterable<T> _allKeys<T>(Map<T, dynamic>? a, Map<T, dynamic>? b) {
  return <T>{...?a?.keys, ...?b?.keys};
}

class Histogram {
  /// Rule used to produce this histogram. Specifies how bucket names
  /// are constructed given (library-uri,class-name,function-name) tuples and
  /// how these bucket names can be deconstructed back into human readable form.
  final BucketInfo bucketInfo;

  /// Histogram buckets.
  final Map<String, int> buckets;

  /// Bucket names sorted by the size of the corresponding bucket in descending
  /// order.
  final List<String> bySize;

  final int totalSize;

  int get length => bySize.length;

  Histogram._(this.bucketInfo, this.buckets)
      : bySize = buckets.keys.toList(growable: false)
          ..sort((a, b) => buckets[b]! - buckets[a]!),
        totalSize = buckets.values.fold(0, (sum, size) => sum + size);

  static Histogram fromIterable<T>(
    Iterable<T> entries, {
    required int Function(T) sizeOf,
    required String Function(T) bucketFor,
    required BucketInfo bucketInfo,
  }) {
    final buckets = <String, int>{};

    for (var e in entries) {
      final bucket = bucketFor(e);
      final size = sizeOf(e);
      buckets[bucket] = (buckets[bucket] ?? 0) + size;
    }

    return Histogram._(bucketInfo, buckets);
  }

  /// Rebuckets the histogram given the new bucketing rule.
  Histogram map(String Function(String) bucketFor) {
    return Histogram.fromIterable(buckets.keys,
        sizeOf: (key) => buckets[key]!,
        bucketFor: bucketFor,
        bucketInfo: bucketInfo);
  }
}

/// Construct the histogram of specific [type] given a [ProgramInfo].
///
/// [filter] glob can be provided to skip some of the nodes in the [info]:
/// a string is created which contains library name, class name and function
/// name for the given node and if this string does not match the [filter]
/// glob then this node is ignored.
Histogram computeHistogram(ProgramInfo info, HistogramType type,
    {String? filter}) {
  bool Function(String, String?, String?) matchesFilter;

  if (filter != null) {
    final re = RegExp(filter.replaceAll('*', '.*'), caseSensitive: false);
    matchesFilter =
        (lib, cls, fun) => re.hasMatch("${lib}::${cls ?? ''}.${fun ?? ''}");
  } else {
    matchesFilter = (_, __, ___) => true;
  }

  if (type == HistogramType.byNodeType) {
    final Set<int> filteredNodes = {};
    if (filter != null) {
      info.visit((pkg, lib, cls, fun, node) {
        if (matchesFilter(lib, cls, fun)) {
          filteredNodes.add(node.id);
        }
      });
    }

    final snapshotInfo = info.snapshotInfo!;

    return Histogram.fromIterable<Node>(
        snapshotInfo.snapshot.nodes.where((n) =>
            filter == null ||
            filteredNodes.contains(snapshotInfo.ownerOf(n).id)),
        sizeOf: (n) {
          return n.selfSize;
        },
        bucketFor: (n) => n.type,
        bucketInfo: const BucketInfo(nameComponents: ['Type']));
  } else {
    final buckets = <String, int>{};
    final bucketing = Bucketing._forType[type]!;

    info.visit((pkg, lib, cls, fun, node) {
      final sz = node.size;
      if (sz == null || sz == 0) {
        return;
      }
      if (!matchesFilter(lib, cls, fun)) {
        return;
      }
      final bucket = bucketing.bucketFor(pkg, lib, cls, fun);
      buckets[bucket] = (buckets[bucket] ?? 0) + sz;
    });

    return Histogram._(bucketing, buckets);
  }
}

enum HistogramType {
  bySymbol,
  byClass,
  byLibrary,
  byPackage,
  byNodeType,
}

class BucketInfo {
  /// Specifies which human readable name components can be extracted from
  /// the bucket name.
  final List<String> nameComponents;

  /// Deconstructs bucket name into human readable components (the order matches
  /// one returned by [nameComponents]).
  List<String> namesFromBucket(String bucket) => [bucket];

  const BucketInfo({required this.nameComponents});
}

abstract class Bucketing extends BucketInfo {
  /// Constructs the bucket name from the given library name [lib], class name
  /// [cls] and function name [fun].
  String bucketFor(String? pkg, String lib, String? cls, String? fun);

  const Bucketing({required List<String> nameComponents})
      : super(nameComponents: nameComponents);

  static const _forType = {
    HistogramType.bySymbol: _BucketBySymbol(),
    HistogramType.byClass: _BucketByClass(),
    HistogramType.byLibrary: _BucketByLibrary(),
    HistogramType.byPackage: _BucketByPackage(),
  };
}

/// A combination of characters that is unlikely to occur in the symbol name.
const String _nameSeparator = ';;;';

class _BucketBySymbol extends Bucketing {
  @override
  String bucketFor(String? pkg, String lib, String? cls, String? fun) {
    if (fun == null) {
      return '@other${_nameSeparator}';
    }
    return '$lib${_nameSeparator}${cls ?? ''}${cls != '' && cls != null ? '.' : ''}${fun}';
  }

  @override
  List<String> namesFromBucket(String bucket) => bucket.split(_nameSeparator);

  const _BucketBySymbol() : super(nameComponents: const ['Library', 'Symbol']);
}

class _BucketByClass extends Bucketing {
  @override
  String bucketFor(String? pkg, String lib, String? cls, String? fun) {
    if (cls == null) {
      return '@other${_nameSeparator}';
    }
    return '$lib${_nameSeparator}${cls}';
  }

  @override
  List<String> namesFromBucket(String bucket) => bucket.split(_nameSeparator);

  const _BucketByClass() : super(nameComponents: const ['Library', 'Class']);
}

class _BucketByLibrary extends Bucketing {
  @override
  String bucketFor(String? pkg, String lib, String? cls, String? fun) => '$lib';

  const _BucketByLibrary() : super(nameComponents: const ['Library']);
}

class _BucketByPackage extends Bucketing {
  @override
  String bucketFor(String? pkg, String lib, String? cls, String? fun) =>
      pkg ?? lib;

  const _BucketByPackage() : super(nameComponents: const ['Package']);
}

String packageOf(String lib) {
  if (lib.startsWith('package:')) {
    final separatorPos = lib.indexOf('/');
    return lib.substring(0, separatorPos);
  } else {
    return lib;
  }
}