scope-deconflict.ts

import type { Identifier, LocalIdentifier } from './estree.ts';

const isLocalIdentifier = (ident: Identifier | LocalIdentifier): ident is LocalIdentifier => {
	return 'preferredName' in ident;
};

interface RenameContext {
	usedNames: Set<string>;
}

export class Scope {
	readonly parent: Scope | undefined;
	readonly children: Scope[] = [];

	readonly declarations = new Set<Identifier>();
	readonly references = new Set<Identifier>();

	constructor(parent?: Scope) {
		if (parent) {
			this.parent = parent;
			parent.children.push(this);
		}
	}

	begin(): Scope {
		return new Scope(this);
	}

	end(): void {
		if (!this.parent) {
			const context: RenameContext = {
				usedNames: new Set(),
			};

			this.#rename(context);
		}
	}

	declare(identifier: Identifier): void {
		this.declarations.add(identifier);
	}

	reference(identifier: Identifier): void {
		this.references.add(identifier);
	}

	#rename(context: RenameContext): void {
		// Step 1: Reserve all global names
		this.#reserveGlobalNames(context);

		// Step 2: Group local identifiers by preferred name
		const groups = this.#groupLocalIdentifiers();

		// Step 3: Assign names to each group
		for (const [preferredName, identifiers] of groups) {
			this.#assignNames(context, preferredName, identifiers);
		}
	}

	#reserveGlobalNames(context: RenameContext): void {
		this.#walk((scope) => {
			// Check declarations
			for (const ident of scope.declarations) {
				if (!isLocalIdentifier(ident)) {
					context.usedNames.add(ident.name);
				}
			}
			// Check references
			for (const ident of scope.references) {
				if (!isLocalIdentifier(ident)) {
					context.usedNames.add(ident.name);
				}
			}
		});
	}

	#groupLocalIdentifiers(): Map<string, LocalIdentifier[]> {
		const groups = new Map<string, LocalIdentifier[]>();
		const seenIds = new Set<LocalIdentifier>();

		this.#walk((scope) => {
			// Check declarations
			for (const ident of scope.declarations) {
				if (isLocalIdentifier(ident) && !seenIds.has(ident)) {
					const key = ident.preferredName;
					const array = groups.get(key);

					if (!array) {
						groups.set(key, [ident]);
					} else {
						array.push(ident);
					}

					seenIds.add(ident);
				}
			}
			// Check references
			for (const ident of scope.references) {
				if (isLocalIdentifier(ident) && !seenIds.has(ident)) {
					const key = ident.preferredName;
					const array = groups.get(key);

					if (!array) {
						groups.set(key, [ident]);
					} else {
						array.push(ident);
					}

					seenIds.add(ident);
				}
			}
		});

		return groups;
	}

	#assignNames(context: RenameContext, preferredName: string, identifiers: LocalIdentifier[]): void {
		const hasGlobalConflict = context.usedNames.has(preferredName);
		const conflicts = this.#findConflicts(identifiers);

		if (conflicts.length === 0 && !hasGlobalConflict) {
			// No conflicts - all can use preferred name
			for (let idx = 0, len = identifiers.length; idx < len; idx++) {
				identifiers[idx].name = preferredName;
			}

			context.usedNames.add(preferredName);
		} else {
			// Has conflicts - prioritize declarations over references
			const declarations = identifiers.filter((id) => this.#isDeclaration(id));
			const references = identifiers.filter((id) => !this.#isDeclaration(id));

			let suffix = hasGlobalConflict ? 1 : 0;

			// Assign names to declarations first
			for (let idx = 0, len = declarations.length; idx < len; idx++) {
				const ident = declarations[idx];
				const name = suffix === 0 ? preferredName : `${preferredName}$${suffix}`;

				ident.name = name;
				context.usedNames.add(name);

				suffix++;
			}

			// Then assign names to references
			for (let idx = 0, len = references.length; idx < len; idx++) {
				const ident = references[idx];
				const name = suffix === 0 ? preferredName : `${preferredName}$${suffix}`;

				ident.name = name;
				context.usedNames.add(name);

				suffix++;
			}
		}
	}

	#isDeclaration(identifier: LocalIdentifier): boolean {
		return this.#walk((scope) => scope.declarations.has(identifier));
	}

	#findConflicts(identifiers: LocalIdentifier[]): [LocalIdentifier, LocalIdentifier][] {
		const conflicts: [LocalIdentifier, LocalIdentifier][] = [];

		// Build a map of scope -> set of identifiers present in that scope
		const scopeToIdentifiers = new Map<Scope, Set<LocalIdentifier>>();

		this.#walk((scope) => {
			const presentIds = new Set<LocalIdentifier>();

			for (let idx = 0, len = identifiers.length; idx < len; idx++) {
				const ident = identifiers[idx];

				if (scope.declarations.has(ident) || scope.references.has(ident)) {
					presentIds.add(ident);
				}
			}

			if (presentIds.size > 1) {
				scopeToIdentifiers.set(scope, presentIds);
			}
		});

		// Find conflicts from scopes that have multiple identifiers
		for (const presentIdents of scopeToIdentifiers.values()) {
			const idents = Array.from(presentIdents);

			for (let i = 0, l = idents.length; i < l; i++) {
				for (let j = i + 1; j < l; j++) {
					conflicts.push([idents[i], idents[j]]);
				}
			}
		}

		return conflicts;
	}

	#walk(fn: (scope: Scope) => boolean | void): boolean {
		if (fn(this)) {
			return true;
		}

		const children = this.children;
		for (let idx = 0, len = children.length; idx < len; idx++) {
			if (children[idx].#walk(fn)) {
				return true;
			}
		}

		return false;
	}
}