// SPDX-License-Identifier: GPL-2.0
#include <inttypes.h>
#include <string.h>
#include <linux/zalloc.h>
#include <sys/ttydefaults.h>

#include "ui/browser.h"
#include "ui/helpline.h"
#include "ui/keysyms.h"
#include "ui/ui.h"
#include "util/annotate.h"
#include "util/annotate-data.h"
#include "util/evsel.h"
#include "util/evlist.h"
#include "util/sort.h"

#define FOLDED_SIGN  '+'
#define UNFOLD_SIGN  '-'
#define NOCHLD_SIGN  ' '

struct browser_entry {
	struct list_head node;
	struct annotated_member *data;
	struct type_hist_entry *hists;
	struct browser_entry *parent;
	struct list_head children;
	int indent;  /*indentation level, starts from 0 */
	int nr_entries; /* # of visible entries: self + descendents */
	bool folded;  /* only can be false when it has children */
};

struct annotated_data_browser {
	struct ui_browser b;
	struct list_head entries;
	struct browser_entry *curr;
	int nr_events;
};

static struct annotated_data_browser *get_browser(struct ui_browser *uib)
{
	return container_of(uib, struct annotated_data_browser, b);
}

static void update_hist_entry(struct type_hist_entry *dst,
			      struct type_hist_entry *src)
{
	dst->nr_samples += src->nr_samples;
	dst->period += src->period;
}

static int get_member_overhead(struct annotated_data_type *adt,
			       struct browser_entry *entry,
			       struct evsel *leader)
{
	struct annotated_member *member = entry->data;
	int i, k;

	for (i = 0; i < member->size; i++) {
		struct type_hist *h;
		struct evsel *evsel;
		int offset = member->offset + i;

		k = 0;
		for_each_group_evsel(evsel, leader) {
			if (symbol_conf.skip_empty &&
			    evsel__hists(evsel)->stats.nr_samples == 0)
				continue;

			h = adt->histograms[evsel->core.idx];
			update_hist_entry(&entry->hists[k++], &h->addr[offset]);
		}
	}
	return 0;
}

static int add_child_entries(struct annotated_data_browser *browser,
			     struct browser_entry *parent,
			     struct annotated_data_type *adt,
			     struct annotated_member *member,
			     struct evsel *evsel, int indent)
{
	struct annotated_member *pos;
	struct browser_entry *entry;
	struct list_head *parent_list;

	entry = zalloc(sizeof(*entry));
	if (entry == NULL)
		return -1;

	entry->hists = calloc(browser->nr_events, sizeof(*entry->hists));
	if (entry->hists == NULL) {
		free(entry);
		return -1;
	}

	entry->data = member;
	entry->parent = parent;
	entry->indent = indent;
	if (get_member_overhead(adt, entry, evsel) < 0) {
		free(entry);
		return -1;
	}

	INIT_LIST_HEAD(&entry->children);
	if (parent)
		parent_list = &parent->children;
	else
		parent_list = &browser->entries;

	list_add_tail(&entry->node, parent_list);

	list_for_each_entry(pos, &member->children, node) {
		int nr = add_child_entries(browser, entry, adt, pos, evsel,
					   indent + 1);
		if (nr < 0)
			return nr;
	}

	/* add an entry for the closing bracket ("}") */
	if (!list_empty(&member->children)) {
		struct browser_entry *bracket;

		bracket = zalloc(sizeof(*bracket));
		if (bracket == NULL)
			return -1;

		bracket->indent = indent;
		bracket->parent = entry;
		bracket->folded = true;
		bracket->nr_entries = 1;

		INIT_LIST_HEAD(&bracket->children);
		list_add_tail(&bracket->node, &entry->children);
	}

	/* fold child entries by default */
	entry->folded = true;
	entry->nr_entries = 1;
	return 0;
}

static u32 count_visible_entries(struct annotated_data_browser *browser)
{
	int nr = 0;
	struct browser_entry *entry;

	list_for_each_entry(entry, &browser->entries, node)
		nr += entry->nr_entries;

	return nr;
}

static int annotated_data_browser__collect_entries(struct annotated_data_browser *browser)
{
	struct hist_entry *he = browser->b.priv;
	struct annotated_data_type *adt = he->mem_type;
	struct evsel *evsel = hists_to_evsel(he->hists);

	INIT_LIST_HEAD(&browser->entries);

	add_child_entries(browser, /*parent=*/NULL, adt, &adt->self, evsel,
			  /*indent=*/0);

	browser->b.entries = &browser->entries;
	browser->b.nr_entries = count_visible_entries(browser);
	return 0;
}

static void annotated_data_browser__delete_entries(struct annotated_data_browser *browser)
{
	struct browser_entry *pos, *tmp;

	list_for_each_entry_safe(pos, tmp, &browser->entries, node) {
		list_del_init(&pos->node);
		zfree(&pos->hists);
		free(pos);
	}
}

static struct browser_entry *get_first_child(struct browser_entry *entry)
{
	if (list_empty(&entry->children))
		return NULL;

	return list_first_entry(&entry->children, struct browser_entry, node);
}

static struct browser_entry *get_last_child(struct browser_entry *entry)
{
	if (list_empty(&entry->children))
		return NULL;

	return list_last_entry(&entry->children, struct browser_entry, node);
}

static bool is_first_child(struct browser_entry *entry)
{
	/* This will be checked in a different way */
	if (entry->parent == NULL)
		return false;

	return get_first_child(entry->parent) == entry;
}

static bool is_last_child(struct browser_entry *entry)
{
	/* This will be checked in a different way */
	if (entry->parent == NULL)
		return false;

	return get_last_child(entry->parent) == entry;
}

static struct browser_entry *browser__prev_entry(struct ui_browser *uib,
						 struct browser_entry *entry)
{
	struct annotated_data_browser *browser = get_browser(uib);
	struct browser_entry *first;

	first = list_first_entry(&browser->entries, struct browser_entry, node);

	while (entry != first) {
		if (is_first_child(entry))
			entry = entry->parent;
		else {
			entry = list_prev_entry(entry, node);
			while (!entry->folded)
				entry = get_last_child(entry);
		}

		if (!uib->filter || !uib->filter(uib, &entry->node))
			return entry;
	}
	return first;
}

static struct browser_entry *browser__next_entry(struct ui_browser *uib,
						 struct browser_entry *entry)
{
	struct annotated_data_browser *browser = get_browser(uib);
	struct browser_entry *last;

	last = list_last_entry(&browser->entries, struct browser_entry, node);
	while (!last->folded)
		last = get_last_child(last);

	while (entry != last) {
		if (!entry->folded)
			entry = get_first_child(entry);
		else {
			while (is_last_child(entry))
				entry = entry->parent;

			entry = list_next_entry(entry, node);
		}

		if (!uib->filter || !uib->filter(uib, &entry->node))
			return entry;
	}
	return last;
}

static void browser__seek(struct ui_browser *uib, off_t offset, int whence)
{
	struct annotated_data_browser *browser = get_browser(uib);
	struct browser_entry *entry;

	if (uib->nr_entries == 0)
		return;

	switch (whence) {
	case SEEK_SET:
		entry = list_first_entry(&browser->entries, typeof(*entry), node);
		if (uib->filter && uib->filter(uib, &entry->node))
			entry = browser__next_entry(uib, entry);
		break;
	case SEEK_CUR:
		entry = list_entry(uib->top, typeof(*entry), node);
		break;
	case SEEK_END:
		entry = list_last_entry(&browser->entries, typeof(*entry), node);
		while (!entry->folded)
			entry = get_last_child(entry);
		if (uib->filter && uib->filter(uib, &entry->node))
			entry = browser__prev_entry(uib, entry);
		break;
	default:
		return;
	}

	assert(entry != NULL);

	if (offset > 0) {
		while (offset-- != 0)
			entry = browser__next_entry(uib, entry);
	} else {
		while (offset++ != 0)
			entry = browser__prev_entry(uib, entry);
	}

	uib->top = &entry->node;
}

static unsigned int browser__refresh(struct ui_browser *uib)
{
	struct annotated_data_browser *browser = get_browser(uib);
	struct browser_entry *entry, *next;
	int row = 0;

	if (uib->top == NULL || uib->top == uib->entries)
		browser__seek(uib, SEEK_SET, 0);

	entry = list_entry(uib->top, typeof(*entry), node);

	while (true) {
		if (!uib->filter || !uib->filter(uib, &entry->node)) {
			ui_browser__gotorc(uib, row, 0);
			uib->write(uib, entry, row);
			if (uib->top_idx + row == uib->index)
				browser->curr = entry;
			if (++row == uib->rows)
				break;
		}
		next = browser__next_entry(uib, entry);
		if (next == entry)
			break;

		entry = next;
	}

	return row;
}

static int browser__show(struct ui_browser *uib)
{
	struct hist_entry *he = uib->priv;
	struct annotated_data_type *adt = he->mem_type;
	struct annotated_data_browser *browser = get_browser(uib);
	const char *help = "Press 'h' for help on key bindings";
	char title[256];

	snprintf(title, sizeof(title), "Annotate type: '%s' (%d samples)",
		 adt->self.type_name, he->stat.nr_events);

	if (ui_browser__show(uib, title, help) < 0)
		return -1;

	/* second line header */
	ui_browser__gotorc_title(uib, 0, 0);
	ui_browser__set_color(uib, HE_COLORSET_ROOT);

	if (symbol_conf.show_total_period)
		strcpy(title, "Period");
	else if (symbol_conf.show_nr_samples)
		strcpy(title, "Samples");
	else
		strcpy(title, "Percent");

	ui_browser__printf(uib, "%*s %10s %10s %10s  %s",
			   2 + 11 * (browser->nr_events - 1), "",
			   title, "Offset", "Size", "Field");
	ui_browser__write_nstring(uib, "", uib->width);
	return 0;
}

static void browser__write_overhead(struct ui_browser *uib,
				    struct type_hist *total,
				    struct type_hist_entry *hist, int row)
{
	u64 period = hist->period;
	double percent = total->period ? (100.0 * period / total->period) : 0;
	bool current = ui_browser__is_current_entry(uib, row);
	int nr_samples = 0;

	ui_browser__set_percent_color(uib, percent, current);

	if (symbol_conf.show_total_period)
		ui_browser__printf(uib, " %10" PRIu64, period);
	else if (symbol_conf.show_nr_samples)
		ui_browser__printf(uib, " %10d", nr_samples);
	else
		ui_browser__printf(uib, " %10.2f", percent);

	ui_browser__set_percent_color(uib, 0, current);
}

static void browser__write(struct ui_browser *uib, void *entry, int row)
{
	struct annotated_data_browser *browser = get_browser(uib);
	struct browser_entry *be = entry;
	struct annotated_member *member = be->data;
	struct hist_entry *he = uib->priv;
	struct annotated_data_type *adt = he->mem_type;
	struct evsel *leader = hists_to_evsel(he->hists);
	struct evsel *evsel;
	int idx = 0;
	bool current = ui_browser__is_current_entry(uib, row);

	if (member == NULL) {
		/* print the closing bracket */
		ui_browser__set_percent_color(uib, 0, current);
		ui_browser__printf(uib, "%c ", NOCHLD_SIGN);
		ui_browser__write_nstring(uib, "", 11 * browser->nr_events);
		ui_browser__printf(uib, " %10s %10s  %*s};",
				   "", "", be->indent * 4, "");
		ui_browser__write_nstring(uib, "", uib->width);
		return;
	}

	ui_browser__set_percent_color(uib, 0, current);

	if (!list_empty(&be->children))
		ui_browser__printf(uib, "%c ", be->folded ? FOLDED_SIGN : UNFOLD_SIGN);
	else
		ui_browser__printf(uib, "%c ", NOCHLD_SIGN);

	/* print the number */
	for_each_group_evsel(evsel, leader) {
		struct type_hist *h = adt->histograms[evsel->core.idx];

		if (symbol_conf.skip_empty &&
		    evsel__hists(evsel)->stats.nr_samples == 0)
			continue;

		browser__write_overhead(uib, h, &be->hists[idx++], row);
	}

	/* print type info */
	if (be->indent == 0 && !member->var_name) {
		ui_browser__printf(uib, " %#10x %#10x  %s%s",
				   member->offset, member->size,
				   member->type_name,
				   list_empty(&member->children) || be->folded? ";" : " {");
	} else {
		ui_browser__printf(uib, " %#10x %#10x  %*s%s\t%s%s",
				   member->offset, member->size,
				   be->indent * 4, "", member->type_name,
				   member->var_name ?: "",
				   list_empty(&member->children) || be->folded ? ";" : " {");
	}
	/* fill the rest */
	ui_browser__write_nstring(uib, "", uib->width);
}

static void annotated_data_browser__fold(struct annotated_data_browser *browser,
					 struct browser_entry *entry,
					 bool recursive)
{
	struct browser_entry *child;

	if (list_empty(&entry->children))
		return;
	if (entry->folded && !recursive)
		return;

	if (recursive) {
		list_for_each_entry(child, &entry->children, node)
			annotated_data_browser__fold(browser, child, true);
	}

	entry->nr_entries = 1;
	entry->folded = true;
}

static void annotated_data_browser__unfold(struct annotated_data_browser *browser,
					   struct browser_entry *entry,
					   bool recursive)
{
	struct browser_entry *child;
	int nr_entries;

	if (list_empty(&entry->children))
		return;
	if (!entry->folded && !recursive)
		return;

	nr_entries = 1; /* for self */
	list_for_each_entry(child, &entry->children, node) {
		if (recursive)
			annotated_data_browser__unfold(browser, child, true);

		nr_entries += child->nr_entries;
	}

	entry->nr_entries = nr_entries;
	entry->folded = false;
}

static void annotated_data_browser__toggle_fold(struct annotated_data_browser *browser,
						bool recursive)
{
	struct browser_entry *curr = browser->curr;
	struct browser_entry *parent;

	parent = curr->parent;
	while (parent) {
		parent->nr_entries -= curr->nr_entries;
		parent = parent->parent;
	}
	browser->b.nr_entries -= curr->nr_entries;

	if (curr->folded)
		annotated_data_browser__unfold(browser, curr, recursive);
	else
		annotated_data_browser__fold(browser, curr, recursive);

	parent = curr->parent;
	while (parent) {
		parent->nr_entries += curr->nr_entries;
		parent = parent->parent;
	}
	browser->b.nr_entries += curr->nr_entries;

	assert(browser->b.nr_entries == count_visible_entries(browser));
}

static int annotated_data_browser__run(struct annotated_data_browser *browser,
				       struct evsel *evsel __maybe_unused,
				       struct hist_browser_timer *hbt)
{
	int delay_secs = hbt ? hbt->refresh : 0;
	int key;

	if (browser__show(&browser->b) < 0)
		return -1;

	while (1) {
		key = ui_browser__run(&browser->b, delay_secs);

		switch (key) {
		case K_TIMER:
			if (hbt)
				hbt->timer(hbt->arg);
			continue;
		case K_F1:
		case 'h':
			ui_browser__help_window(&browser->b,
		"UP/DOWN/PGUP\n"
		"PGDN/SPACE    Navigate\n"
		"</>           Move to prev/next symbol\n"
		"e             Expand/Collapse current entry\n"
		"E             Expand/Collapse all children of the current\n"
		"q/ESC/CTRL+C  Exit\n\n");
			continue;
		case 'e':
			annotated_data_browser__toggle_fold(browser,
							    /*recursive=*/false);
			break;
		case 'E':
			annotated_data_browser__toggle_fold(browser,
							    /*recursive=*/true);
			break;
		case K_LEFT:
		case '<':
		case '>':
		case K_ESC:
		case 'q':
		case CTRL('c'):
			goto out;
		default:
			continue;
		}
	}
out:
	ui_browser__hide(&browser->b);
	return key;
}

int hist_entry__annotate_data_tui(struct hist_entry *he, struct evsel *evsel,
				  struct hist_browser_timer *hbt)
{
	struct annotated_data_browser browser = {
		.b = {
			.refresh = browser__refresh,
			.seek	 = browser__seek,
			.write	 = browser__write,
			.priv	 = he,
			.extra_title_lines = 1,
		},
		.nr_events = 1,
	};
	int ret;

	ui_helpline__push("Press ESC to exit");

	if (evsel__is_group_event(evsel)) {
		struct evsel *pos;
		int nr = 0;

		for_each_group_evsel(pos, evsel) {
			if (!symbol_conf.skip_empty ||
			    evsel__hists(pos)->stats.nr_samples)
				nr++;
		}
		browser.nr_events = nr;
	}

	ret = annotated_data_browser__collect_entries(&browser);
	if (ret < 0)
		goto out;

	/* To get the top and current entry */
	browser__refresh(&browser.b);
	/* Show the first-level child entries by default */
	annotated_data_browser__toggle_fold(&browser, /*recursive=*/false);

	ret = annotated_data_browser__run(&browser, evsel, hbt);

out:
	annotated_data_browser__delete_entries(&browser);

	return ret;
}