import * as Schema from "effect/Schema";

import type { PluginDefinition } from "./contract.ts";

export interface PlannedComposition {
  readonly blocked: Readonly<Record<string, string>>;
  readonly definitions: ReadonlyArray<PluginDefinition>;
}

export class DuplicatePluginIdError extends Schema.TaggedErrorClass<DuplicatePluginIdError>()(
  "DuplicatePluginIdError",
  { pluginId: Schema.String },
) {
  override get message(): string {
    return `Duplicate plugin id: ${this.pluginId}`;
  }
}

export class DuplicateCapabilityError extends Schema.TaggedErrorClass<DuplicateCapabilityError>()(
  "DuplicateCapabilityError",
  {
    capability: Schema.String,
    pluginId: Schema.String,
    previousPluginId: Schema.String,
  },
) {
  override get message(): string {
    return `Duplicate capability ${this.capability} provided by ${this.previousPluginId} and ${this.pluginId}`;
  }
}

export class DependencyCycleError extends Schema.TaggedErrorClass<DependencyCycleError>()(
  "DependencyCycleError",
  { cycle: Schema.Array(Schema.String) },
) {
  override get message(): string {
    return `Dependency cycle: ${this.cycle.join(" -> ")}`;
  }
}

export const PluginPlanningError = Schema.Union([
  DuplicatePluginIdError,
  DuplicateCapabilityError,
  DependencyCycleError,
]);
export type PluginPlanningError = typeof PluginPlanningError.Type;

export const isPluginPlanningError = Schema.is(PluginPlanningError);

const createNullPrototypeRecord = <Value>(): Record<string, Value> =>
  Object.create(null) as Record<string, Value>;

export const planComposition = (
  definitions: ReadonlyArray<PluginDefinition>,
): PlannedComposition => {
  const definitionsById = new Map<string, PluginDefinition>();
  const providersByCapability = new Map<string, PluginDefinition>();

  for (const definition of definitions) {
    if (definitionsById.has(definition.id)) {
      throw new DuplicatePluginIdError({ pluginId: definition.id });
    }
    definitionsById.set(definition.id, definition);

    for (const capability of Object.keys(definition.provides ?? {})) {
      const previous = providersByCapability.get(capability);
      if (previous !== undefined) {
        throw new DuplicateCapabilityError({
          capability,
          pluginId: definition.id,
          previousPluginId: previous.id,
        });
      }
      providersByCapability.set(capability, definition);
    }
  }

  interface VisitFrame {
    readonly definition: PluginDefinition;
    requirementIndex: number;
    reason: string | undefined;
  }

  const states = new Map<string, "visiting" | "visited">();
  const path: Array<string> = [];
  const pathIndexes = new Map<string, number>();
  const ordered: Array<PluginDefinition> = [];
  const blocked = createNullPrototypeRecord<string>();

  for (const root of definitions) {
    if (states.has(root.id)) continue;

    const stack: Array<VisitFrame> = [{ definition: root, requirementIndex: 0, reason: undefined }];
    states.set(root.id, "visiting");
    pathIndexes.set(root.id, path.length);
    path.push(root.id);

    while (stack.length > 0) {
      const frame = stack.at(-1);
      if (frame === undefined) break;
      const requirements = frame.definition.requires ?? [];
      const capability = requirements[frame.requirementIndex];

      if (capability !== undefined) {
        const provider = providersByCapability.get(capability);
        if (provider === undefined) {
          frame.reason ??= `Missing dependency: ${capability}`;
          frame.requirementIndex += 1;
          continue;
        }

        const state = states.get(provider.id);
        if (state === "visiting") {
          const cycleStart = pathIndexes.get(provider.id);
          if (cycleStart === undefined) {
            throw new DependencyCycleError({ cycle: [provider.id, provider.id] });
          }
          throw new DependencyCycleError({ cycle: [...path.slice(cycleStart), provider.id] });
        }
        if (state === undefined) {
          stack.push({ definition: provider, requirementIndex: 0, reason: undefined });
          states.set(provider.id, "visiting");
          pathIndexes.set(provider.id, path.length);
          path.push(provider.id);
          continue;
        }

        if (Object.hasOwn(blocked, provider.id)) {
          frame.reason ??= `Dependency ${capability} is blocked: ${blocked[provider.id]}`;
        }
        frame.requirementIndex += 1;
        continue;
      }

      stack.pop();
      path.pop();
      pathIndexes.delete(frame.definition.id);
      states.set(frame.definition.id, "visited");
      if (frame.reason === undefined) {
        ordered.push(frame.definition);
      } else {
        blocked[frame.definition.id] = frame.reason;
      }
    }
  }

  return { blocked, definitions: ordered };
};

const sameStrings = (left: ReadonlyArray<string>, right: ReadonlyArray<string>): boolean => {
  if (left.length !== right.length) return false;
  const sortedLeft = [...left].sort();
  const sortedRight = [...right].sort();
  return sortedLeft.every((value, index) => value === sortedRight[index]);
};

const sameDefinition = (left: PluginDefinition, right: PluginDefinition): boolean => {
  if (
    left.id !== right.id ||
    left.version !== right.version ||
    !Object.is(left.activate, right.activate)
  ) {
    return false;
  }
  if (!sameStrings(left.requires ?? [], right.requires ?? [])) return false;

  const leftProvides = left.provides ?? {};
  const rightProvides = right.provides ?? {};
  const leftCapabilities = Object.keys(leftProvides);
  const rightCapabilities = Object.keys(rightProvides);
  return (
    leftCapabilities.length === rightCapabilities.length &&
    leftCapabilities.every(
      (capability) =>
        Object.hasOwn(rightProvides, capability) &&
        Object.is(leftProvides[capability], rightProvides[capability]),
    )
  );
};

const dependentsByPlugin = (definitions: ReadonlyArray<PluginDefinition>) => {
  const providers = new Map<string, string>();
  const dependents = new Map<string, Set<string>>();
  for (const definition of definitions) {
    for (const capability of Object.keys(definition.provides ?? {})) {
      providers.set(capability, definition.id);
    }
  }
  for (const definition of definitions) {
    for (const capability of definition.requires ?? []) {
      const providerId = providers.get(capability);
      if (providerId === undefined) continue;
      const values = dependents.get(providerId) ?? new Set<string>();
      values.add(definition.id);
      dependents.set(providerId, values);
    }
  }
  return dependents;
};

export const affectedPluginIds = (
  current: ReadonlyArray<PluginDefinition>,
  desired: ReadonlyArray<PluginDefinition>,
): ReadonlySet<string> => {
  const currentById = new Map(current.map((definition) => [definition.id, definition]));
  const desiredById = new Map(desired.map((definition) => [definition.id, definition]));
  const affected = new Set<string>();

  for (const definition of current) {
    const next = desiredById.get(definition.id);
    if (next === undefined || !sameDefinition(definition, next)) affected.add(definition.id);
  }
  for (const definition of desired) {
    const previous = currentById.get(definition.id);
    if (previous === undefined || !sameDefinition(previous, definition))
      affected.add(definition.id);
  }

  const currentDependents = dependentsByPlugin(current);
  const desiredDependents = dependentsByPlugin(desired);
  const queue = [...affected];
  for (let index = 0; index < queue.length; index += 1) {
    const pluginId = queue[index];
    if (pluginId === undefined) continue;
    for (const dependent of [
      ...(currentDependents.get(pluginId) ?? []),
      ...(desiredDependents.get(pluginId) ?? []),
    ]) {
      if (affected.has(dependent)) continue;
      affected.add(dependent);
      queue.push(dependent);
    }
  }

  return affected;
};