package p.studio.compiler.workspaces.phases;

import p.studio.compiler.messages.BuildingIssueSink;
import p.studio.compiler.models.BuildStack;
import p.studio.compiler.models.DependencyContext;
import p.studio.compiler.models.ProjectInfoId;
import p.studio.compiler.source.identifiers.ProjectId;
import p.studio.compiler.workspaces.DependencyPhase;
import p.studio.utilities.structures.ReadOnlyList;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import static java.util.stream.Collectors.joining;

public final class StackPhase implements DependencyPhase {
    /**
     * Implements topological sort; detects dependency cycles; sets build stack
     */
    @Override
    public BuildingIssueSink run(final DependencyContext ctx) {
        final int n = ctx.projectTable.size();
        final int[] indeg = new int[n];
        for (int from = 0; from < n; from++) {
            for (final ProjectId to : ctx.dependenciesByProject.get(from)) {
                indeg[to.getIndex()]++;
            }
        }

        final Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) q.add(i);
        }

        final List<ProjectId> travesalOrder = new ArrayList<>(n);
        // Performs topological sort using Kahn's algorithm
        while (!q.isEmpty()) {
            final int u = q.removeFirst();
            //travesalOrder.add(ctx.projectDescriptors.get(u).getProjectId());
            travesalOrder.add(new ProjectId(u));
            for (final ProjectId v : ctx.dependenciesByProject.get(u)) {
                if (--indeg[v.getId()] == 0) {
                    q.addLast(v.getId());
                }
            }
        }

        if (travesalOrder.size() != n) {
            boolean[] stuck = new boolean[n];
            for (int i = 0; i < n; i++) stuck[i] = indeg[i] > 0;

            var tarjan = new TarjanScc(n, ctx.dependenciesByProject);
            final List<List<Integer>> sccs = tarjan.run(stuck);

            final List<List<ProjectId>> cycles = new ArrayList<>();
            for (var scc : sccs) {
                if (scc.size() > 1) {
                    final var cycle = scc.stream().map(ProjectId::new).toList();
                    cycles.add(cycle);
                } else {
                    // size==1: cycle only if self-loop exists
                    final var u = scc.getFirst();
                    final var projectId = new ProjectId(u);
                    boolean selfLoop = false;
                    for (final var pu : ctx.dependenciesByProject.get(u)) {
                        if (pu.getIndex() == u) {
                            selfLoop = true;
                            break;
                        }
                    }
                    if (selfLoop) {
                        cycles.add(List.of(projectId));
                    }
                }
            }

            final var msg = "[DEPS]: cycle(s) detected:\n" + cycles.stream()
                    .map(projectIds -> " * " + projectIds.stream()
                        .map(pId -> ctx.projectInfoTable.get(new ProjectInfoId(pId.getIndex())).manifest.name())
                        .collect(joining(" -> "))
                    )
                    .collect(joining("\n"));

            return BuildingIssueSink.empty()
                    .report(builder -> builder.error(true).message(msg));
        }

        ctx.stack = new BuildStack(ReadOnlyList.wrap(travesalOrder));

        return BuildingIssueSink.empty();
    }

    static final class TarjanScc {
        private final int n;
        private final List<List<ProjectId>> adj;

        private int time = 0;
        private final int[] disc;
        private final int[] low;
        private final boolean[] inStack;
        private final Deque<Integer> stack = new ArrayDeque<>();

        TarjanScc(int n, List<List<ProjectId>> adj) {
            this.n = n;
            this.adj = adj;
            this.disc = new int[n];
            this.low = new int[n];
            this.inStack = new boolean[n];
            java.util.Arrays.fill(disc, -1);
        }

        List<List<Integer>> run(boolean[] allowed) {
            List<List<Integer>> sccs = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (allowed[i] && disc[i] == -1) dfs(i, allowed, sccs);
            }
            return sccs;
        }

        private void dfs(int u, boolean[] allowed, List<List<Integer>> out) {
            disc[u] = low[u] = time++;
            stack.push(u);
            inStack[u] = true;

            for (ProjectId pid : adj.get(u)) {
                int v = pid.getIndex();
                if (!allowed[v]) continue;

                if (disc[v] == -1) {
                    dfs(v, allowed, out);
                    low[u] = Math.min(low[u], low[v]);
                } else if (inStack[v]) {
                    low[u] = Math.min(low[u], disc[v]);
                }
            }

            if (low[u] == disc[u]) {
                List<Integer> scc = new ArrayList<>();
                while (true) {
                    int w = stack.pop();
                    inStack[w] = false;
                    scc.add(w);
                    if (w == u) break;
                }
                out.add(scc);
            }
        }
    }
}
