#!/bin/bash
# Classifies files by type and counts them across a project area.
#
# Usage: orient-files [-x|--list-unclassified] [PATH]
#   PATH defaults to the git toplevel of cwd, else cwd itself.
#
# Output: a bullet list, one row per type, sorted by count descending.
# Each row has three columns: type name, count, and a hint indicating
# which heuristic(s) matched.  Types with fewer than 3 files are lumped
# into a trailing "(other)" line so the output stays bounded.
#
# Example output:
#   - markdown:         25  (`.md`)
#   - typescript:     1241  (`.ts`)
#   - bash:             14  (shebang, `.bash`)
#   - image:           108  (`.png`, `.jpg`, `.gif`)
#   - unknown-shell:     7  (`.sh`)
#   - (other): 9 files across 5 kinds
#
# Type names are canonical (lowercased) language/format names, chosen
# for legibility when scanning.  Extensions without a mapping fall
# through to using the literal extension as the type name, so unfamiliar
# projects stay informative without needing the table to be exhaustive.
#
# Heuristics:
# - Extension: a small handwritten table mapping `.md` -> markdown etc.
# - Shebang: for executable regular files, the first 100 bytes are
#   read and the first line is matched against a known interpreter list
#   (bash, sh, zsh, dash, ksh, python, node, perl, ruby, lua, awk).
#   Shebang dominates extension when both produce a verdict: a `.sh`
#   file with `#!/usr/bin/env python3` counts as python.
#   The sniff is done in pure bash (no fork per file); it is capped in
#   total per run (see SHEBANG_CAP) because after a few hundred hits the
#   interpreter mix is well characterized and further sniffs are pure cost.
# The hint column lists which heuristics fired for a given type: it's
# a tally of "reasons we looked", not a derivation trace.
#
# Extensionless files (e.g. `LICENSE`, `Makefile`) and dotfiles whose
# name carries no further dot (`.gitignore`, `.editorconfig`) are folded
# into `(other)` along with files of rare extensions.
# With `-x`/`--list-unclassified`, every file that landed in `(other)`
# is itemized as nested bullets, grouped by type, so it's clear what
# the lump actually contains.  In practice this is a useful peek: the
# `(other)` bucket often hides dotfile-shaped config that's central to
# a project's identity.
#
# Silent (no output, exit 0) when no countable files are found.
#
# Bounded walk:
# - This script runs at session-launch time; a stall here delays every
#   subsequent tool call.  The traversal is bounded by a total budget of
#   "path handles" (each file or directory visited counts as 1), defaulting
#   to 20000 and overridable via COMPASS_MAX_FILES.
# - Sibling subtrees share the remaining budget by fair split at descent
#   time; a large subtree can't starve its neighbours.  When any subtree
#   hits its share, it's pruned and named in a truncation footer so the
#   partiality is visible.
# - Filesystem order is used as-is (no sort).  Sums are commutative, and
#   avoiding a sort avoids buffering a whole listing before descending.
#
# Filtering:
# - Dotdirs (`.git`, `.venv`, etc.) are pruned entirely.
# - A small list of well-known build/vendor dirs is also statically pruned
#   (`node_modules`, `target`, `dist`, `build`, `vendor`).
#   The bias is conservative: rather miss a real file under a misnamed
#   `vendor/` than have `node_modules` dominate every count.
# - Ecosystem-aware prunes: when a directory contains a recognized
#   ecosystem marker (`Cargo.toml`, `package.json`, `pyproject.toml`, ...),
#   that ecosystem's conventional build/cache dirs get pruned *when
#   descending through that directory*.  This picks up common heavy dirs
#   without needing the static list to enumerate every variant.

set -euo pipefail

list_unclassified=0
while [ $# -gt 0 ]; do
	case "$1" in
		-x|--list-unclassified) list_unclassified=1; shift ;;
		-h|--help)
			sed -n '2,/^$/p' "$0" | sed 's/^# \?//'
			exit 0 ;;
		--) shift; break ;;
		-*) >&2 echo "orient-files: unknown option: $1"; exit 2 ;;
		*) break ;;
	esac
done

# Resolve the search root via the single source of truth.
# `find-project-root` is strict (git toplevel or exit 1); we add a cwd
# fallback here since classifying files outside a project is still useful.
self_dir=$(cd "$(dirname "$(readlink -f "$0")")" && pwd)
if [ $# -ge 1 ]; then
	root=$(cd "$1" && pwd)
elif root=$("$self_dir/find-project-root" 2>/dev/null); then
	:
else
	root="$PWD"
fi

# Extension -> canonical type name.
# Names roughly follow github-linguist's language list (consulted for
# inspiration, not pulled in as a dependency).
# `.sh` maps to `unknown-shell` rather than `bash`: the actual interpreter
# of a bare `.sh` file depends on the system `/bin/sh`, which varies by
# distro, so flagging that ambiguity is more honest than guessing.
# Shebang-based detection resolves specific shells for executable files.
declare -A ext_to_type=(
	[.md]=markdown        [.markdown]=markdown
	[.rs]=rust
	[.py]=python
	[.ts]=typescript      [.tsx]=typescript
	[.js]=javascript      [.mjs]=javascript    [.cjs]=javascript    [.jsx]=javascript
	[.go]=go
	[.v]=vlang
	[.c]=c                [.h]=c
	[.cpp]=cpp            [.cc]=cpp            [.cxx]=cpp           [.hpp]=cpp           [.hh]=cpp
	[.java]=java
	[.rb]=ruby
	[.php]=php
	[.cs]=csharp
	[.swift]=swift
	[.kt]=kotlin          [.kts]=kotlin
	[.lua]=lua
	[.zig]=zig
	[.dart]=dart
	[.scala]=scala
	[.ex]=elixir          [.exs]=elixir
	[.erl]=erlang
	[.hs]=haskell
	[.clj]=clojure        [.cljs]=clojure
	[.r]=r                [.R]=r
	[.jl]=julia
	[.pl]=perl            [.pm]=perl
	[.sql]=sql
	[.sh]=unknown-shell   [.bash]=bash
	[.nu]=nushell
	[.json]=json
	[.yaml]=yaml          [.yml]=yaml
	[.toml]=toml
	[.html]=html          [.htm]=html
	[.css]=css
	[.xml]=xml
	[.ini]=ini
	[.csv]=csv            [.tsv]=tsv
	[.png]=image          [.jpg]=image         [.jpeg]=image        [.gif]=image
	[.svg]=image          [.webp]=image
	[.txt]=text
	[.log]=log
)

# Interpreter name (as it appears in a shebang) -> canonical type name.
# Order in the regex matters only for completeness, not for precedence:
# any single file's shebang names one interpreter.
declare -A interp_to_type=(
	[bash]=bash
	[sh]=sh
	[zsh]=zsh
	[dash]=dash
	[ksh]=ksh
	[python]=python   [python2]=python   [python3]=python
	[node]=javascript [nodejs]=javascript
	[perl]=perl
	[ruby]=ruby
	[lua]=lua
	[awk]=awk         [gawk]=awk         [mawk]=awk
)

# Static prune list -- directory basenames we never descend into.
# Kept as an associative array for O(1) lookup during the walk.
# Dotdirs are pruned separately by pattern (".*") so they don't need entries here.
declare -A static_prune=(
	[node_modules]=1
	[target]=1
	[dist]=1
	[build]=1
	[vendor]=1
)

# Ecosystem marker table.
# Presence of the marker file in a directory adds the listed basenames to
# the prune set *for that directory's children only*.  This localizes the
# prune to where it's actually appropriate: a `target/` next to a Cargo.toml
# is a Rust build dir; a `target/` in some random directory might not be.
# Multiple markers accumulate.  Order within a value is irrelevant.
declare -A ecosystem_prunes=(
	[Cargo.toml]="target"
	[package.json]="node_modules .next .nuxt"
	[pyproject.toml]="__pycache__ .venv venv .tox .pytest_cache .mypy_cache .ruff_cache"
	[setup.py]="__pycache__ .venv venv .tox .pytest_cache .mypy_cache .ruff_cache"
	[mix.exs]="_build deps"
	[pom.xml]="target"
	[build.gradle]="build .gradle"
	[build.gradle.kts]="build .gradle"
	[CMakeLists.txt]="build"
	[MODULE.bazel]=""
	[WORKSPACE]=""
)
# `bazel-*` prunes are handled specially: they're a prefix pattern rather
# than exact names, and are triggered by any bazel marker.  Encoded below
# as a boolean the walker checks.

# --- Budget, collectors, & helpers ------------------------------------
#
# The walker is deliberately kept minimal: for each classifiable file it
# just emits one tab-separated record (`shebang_type\tname`) into the
# `records` global.  All the per-file classification math (extension
# lookup, per-type tallies, hint composition) happens in a single awk
# pass afterwards.
#
# We measured pure-bash classification-per-file at ~1ms/file on this
# machine -- dominated by function-call overhead and associative-array
# manipulation.  Awk chews the same records in a fraction of a second.
# The recursive walker itself is fine (~1s / 100k entries).
#
# Shebang sniffing has to happen during the walk (it reads bytes off the
# actual file), so it runs inline, is capped by SHEBANG_CAP, and its
# verdict is embedded in the record.

budget_max=${COMPASS_MAX_FILES:-20000}
budget_used=0

# Wallclock backstop.
# The budget above bounds *algorithmic* work; this backstop protects
# against pathological I/O (network mounts, symlink loops we missed,
# spinning rust with a huge cold cache).  Uses bash's `SECONDS` builtin,
# which auto-increments and is essentially free to read.
# Not configurable via env for now -- if this ever fires in normal use
# we have a real problem to fix, not a knob to tune.
WALLCLOCK_SECS=10
SECONDS=0
wallclock_hit=0

# Total shebang sniffs performed.  Capped because a few hundred is plenty
# to characterize the interpreter mix; beyond that we're just paying I/O.
shebang_sniffs=0
SHEBANG_CAP=200

# One record per classified file, tab-separated: `shebang_type\tname`.
# `shebang_type` is empty if the file wasn't sniffed or the sniff missed.
records=()

# Truncation records.  Each entry is "path\tcount", where count is how many
# path handles were spent in that subtree before it was cut off.
truncated=()

# sniff_shebang: identify a script's interpreter, in pure bash (no fork).
# Reads up to 100 bytes of the first line via bash `read`.  Echoes the
# canonical type name on a match, or nothing on a miss.
# Uses `interp_to_type` from the enclosing scope.
# Caveat: bash `read` silently discards NUL bytes, so a file starting with
# NULs then `#!` would false-positive; this is not a real shape for scripts.
sniff_shebang() {
	local path=$1
	local line tok base name
	IFS= read -r -n 100 line <"$path" || :
	[[ $line == '#!'* ]] || return 0
	line=${line#'#!'}
	for tok in $line; do
		[[ $tok == -* ]] && continue
		base=${tok##*/}
		[[ $base == env ]] && continue
		name=${interp_to_type[$base]:-}
		[ -n "$name" ] && printf '%s' "$name"
		return 0
	done
}

# walk_dir: recursively census one directory, respecting a local cap.
#
# @param dir absolute path to the directory
# @param cap  max path handles this subtree may consume (files + dirs)
#
# Consumes from and updates the global `budget_used`.  If either the
# subtree's cap or the global budget would be exceeded, the walk of this
# subtree is truncated and recorded in `truncated`.
#
# The count of "path handles" charges 1 per entry visited (file or dir),
# whether it ends up classified, pruned, or descended.  It's a proxy for
# how many path strings the walker touches -- close enough to real cost.
#
# @state (global) budget_used, type_counts, type_exts, type_shebang,
#                 ext_counts, type_files, truncated, shebang_sniffs
walk_dir() {
	local dir=$1 cap=$2
	local start=$budget_used

	# Enumerate depth-1 entries.  `dotglob` catches `.hidden` names (but
	# not `.`/`..`, which are excluded by bash regardless); `nullglob` makes
	# an empty dir yield an empty array rather than a literal `*`.
	# We use bash globbing rather than forking `find` per directory: for a
	# 20k-entry walk that's a few hundred to a few thousand directory reads,
	# and paying a fork each would dominate the runtime.
	local -a entries
	shopt -s dotglob nullglob
	entries=("$dir"/*)
	shopt -u dotglob nullglob

	# First pass: determine ecosystem-driven prunes for THIS directory.
	# We look at the entry names (not stat) so this pass is free.
	local -A local_prune=()
	local bazel_prune=0
	local entry base
	for entry in "${entries[@]}"; do
		base=${entry##*/}
		if [ -n "${ecosystem_prunes[$base]:-}" ]; then
			local p
			for p in ${ecosystem_prunes[$base]}; do
				local_prune[$p]=1
			done
		fi
		# Bazel markers (WORKSPACE, MODULE.bazel) trigger prefix pruning
		# of `bazel-*` symlinks Bazel creates at the workspace root.
		if [ "$base" = "WORKSPACE" ] || [ "$base" = "MODULE.bazel" ]; then
			bazel_prune=1
		fi
	done

	# Second pass: classify files, collect subdirs.
	local -a subdirs=()
	local is_dotdir
	for entry in "${entries[@]}"; do
		base=${entry##*/}

		# Charge one path handle per entry seen.
		budget_used=$((budget_used + 1))

		# Cap checks.  If we're over either cap, or past the wallclock
		# backstop, stop processing this directory entirely.  Any remaining
		# entries here (and their subtrees) are the truncation.
		if [ $((budget_used - start)) -gt "$cap" ] || [ "$budget_used" -ge "$budget_max" ]; then
			truncated+=("$dir"$'\t'"$((budget_used - start))")
			return 0
		fi
		if [ "$SECONDS" -ge "$WALLCLOCK_SECS" ]; then
			wallclock_hit=1
			truncated+=("$dir"$'\t'"$((budget_used - start))")
			return 0
		fi

		if [ -d "$entry" ] && [ ! -L "$entry" ]; then
			# Directory.  Apply prune rules; otherwise enqueue for descent.
			case "$base" in
				.*) continue ;;   # dotdir: prune
			esac
			if [ -n "${static_prune[$base]:-}" ]; then continue; fi
			if [ -n "${local_prune[$base]:-}" ]; then continue; fi
			if [ "$bazel_prune" -eq 1 ] && [[ $base == bazel-* ]]; then continue; fi
			subdirs+=("$entry")
		elif [ -f "$entry" ]; then
			# Regular file (also catches symlinks-to-files by virtue of -f).
			local shebang_type=""
			if [ -x "$entry" ] && [ "$shebang_sniffs" -lt "$SHEBANG_CAP" ]; then
				shebang_sniffs=$((shebang_sniffs + 1))
				shebang_type=$(sniff_shebang "$entry")
			fi
			records+=("${shebang_type}"$'\t'"${base}")
		fi
		# Other entry kinds (sockets, fifos, dangling symlinks) are silently ignored.
	done

	# Descend into subdirs with fair-share budgets.
	# At each step: share = min(remaining_local, remaining_global) / remaining_siblings.
	# Unspent share flows naturally back into the pool for later siblings
	# because we compute the divisor from what's left, each time.
	local n=${#subdirs[@]} i=0 sub share remaining_local remaining_global
	for sub in "${subdirs[@]}"; do
		remaining_local=$((cap - (budget_used - start)))
		remaining_global=$((budget_max - budget_used))
		if [ "$remaining_local" -le 0 ] || [ "$remaining_global" -le 0 ]; then
			# Record every remaining sibling as truncated at 0 -- they never got
			# a chance.  Distinct from "walked partially" so the report can show it.
			local j
			for (( j=i; j<n; j++ )); do
				truncated+=("${subdirs[$j]}"$'\t0')
			done
			return 0
		fi
		local siblings_left=$((n - i))
		local share_pool=$remaining_local
		[ "$remaining_global" -lt "$share_pool" ] && share_pool=$remaining_global
		share=$((share_pool / siblings_left))
		# Guarantee at least 1 handle so a subtree can at least be entered
		# (its own entry-visit cost).  If we can't even afford that, we're done.
		[ "$share" -lt 1 ] && share=1
		walk_dir "$sub" "$share"
		i=$((i + 1))
	done
}

# --- Drive the walk ---------------------------------------------------

walk_dir "$root" "$budget_max"

# Silent if nothing to report.
if [ ${#records[@]} -eq 0 ] && [ ${#truncated[@]} -eq 0 ]; then
	exit 0
fi

# --- Render -----------------------------------------------------------
#
# One awk pass consumes the records, does per-file classification,
# aggregates per-type tallies, and emits the final markdown fragment.
# The ext_to_type table is serialized into awk via a header block; same
# for the list_unclassified flag.
#
# Column layout for per-type rows:
# - Type name (with trailing colon) left-padded to 16 chars.
#   Wide enough for `unknown-shell:` (14 chars); types longer than that
#   simply push the count column rightward on their own row.
# - Count right-aligned in 5 chars.
# - Two spaces, then the hint in parentheses.
#
# Hint composition: `shebang` appears first if the shebang heuristic
# fired for this type, then the contributing extensions sorted by
# per-extension count descending (dominant variant first), then
# alphabetically.  Determinism matters because we don't want the row
# order changing between runs on the same tree.

{
	# Emit the ext_to_type table as a header awk can slurp.
	printf 'EXT\t%s\t%s\n' "__list_unclassified__" "$list_unclassified"
	for ext in "${!ext_to_type[@]}"; do
		printf 'EXT\t%s\t%s\n' "$ext" "${ext_to_type[$ext]}"
	done
	# Then the records.
	printf 'REC\n'
	for rec in "${records[@]}"; do
		printf '%s\n' "$rec"
	done
} | awk -F'\t' '
	BEGIN { in_records = 0 }

	/^EXT\t/ && !in_records {
		if ($2 == "__list_unclassified__") { list_unclassified = ($3 == "1"); next }
		ext_to_type[$2] = $3
		next
	}
	/^REC$/ { in_records = 1; next }

	# `classify_ext`: strip leading dot for classification purposes
	# (so `.gitignore` is treated as extensionless), then take everything
	# from the last remaining dot onward.  Returns "(none)" if no such dot.
	function classify_ext(name,   s, idx, n, i) {
		s = name
		if (substr(s, 1, 1) == ".") s = substr(s, 2)
		n = length(s)
		idx = 0
		for (i = n; i >= 1; i--) {
			if (substr(s, i, 1) == ".") { idx = i; break }
		}
		if (idx == 0 || idx == n) return "(none)"
		return "." substr(s, idx + 1)
	}

	in_records {
		shebang_type = $1
		name = $2
		ext = classify_ext(name)

		if (shebang_type != "") {
			type = shebang_type
			type_shebang[type] += 1
		} else if (ext == "(none)") {
			type = "extensionless"
		} else {
			type = (ext in ext_to_type) ? ext_to_type[ext] : ext
			ext_counts[ext] += 1
			if (!(type in type_exts)) {
				type_exts[type] = ext
			} else if (index(" " type_exts[type] " ", " " ext " ") == 0) {
				type_exts[type] = type_exts[type] " " ext
			}
		}
		type_counts[type] += 1
		if (list_unclassified) {
			if (!(type in type_files)) {
				type_files[type] = name
			} else {
				type_files[type] = type_files[type] "\n" name
			}
		}
	}

	# Comparator: count desc, name asc.  Emulated by inserting into a
	# sortable array of "NNNNNNNN\ttype" strings, then sorting via asort.
	END {
		if (length(type_counts) == 0) exit 0

		# Build sortable rows.
		n = 0
		for (t in type_counts) {
			n += 1
			rows[n] = sprintf("%08d\t%s", 99999999 - type_counts[t], t)
		}
		# Ascending sort of rows now yields our desired order (count desc, then name asc).
		asort(rows)

		# Split into shown (count >= 3) and other buckets.
		OTHER_THRESHOLD = 3
		shown_n = 0
		other_n = 0
		other_files_total = 0
		for (i = 1; i <= n; i++) {
			split(rows[i], parts, "\t")
			t = parts[2]
			c = type_counts[t]
			if (c >= OTHER_THRESHOLD) {
				shown_n += 1
				shown_type[shown_n] = t
				shown_count[shown_n] = c
			} else {
				other_n += 1
				other_type[other_n] = t
				other_files_total += c
			}
		}

		# Emit per-type rows.
		for (i = 1; i <= shown_n; i++) {
			t = shown_type[i]
			c = shown_count[i]
			hint = ""
			if (t in type_shebang) hint = "shebang"
			if (t in type_exts) {
				# Sort this types extensions by their per-ext count desc, name asc.
				split(type_exts[t], exts_arr, " ")
				em = 0
				delete ext_rows
				for (k in exts_arr) {
					em += 1
					ext_rows[em] = sprintf("%08d\t%s", 99999999 - ext_counts[exts_arr[k]], exts_arr[k])
				}
				asort(ext_rows)
				for (k = 1; k <= em; k++) {
					split(ext_rows[k], eparts, "\t")
					ext_name = eparts[2]
					if (hint == "") hint = "`" ext_name "`"
					else             hint = hint ", `" ext_name "`"
				}
			}
			printf "- %-16s %5d  (%s)\n", t ":", c, hint
		}

		# Emit the (other) summary line if anything landed there.
		if (other_n > 0) {
			fw = (other_files_total == 1) ? "file"  : "files"
			kw = (other_n == 1)           ? "kind"  : "kinds"
			printf "- (other): %d %s across %d %s\n", other_files_total, fw, other_n, kw
		}

		if (list_unclassified && other_n > 0) {
			for (i = 1; i <= other_n; i++) {
				t = other_type[i]
				printf "  - %s (%d):\n", t, type_counts[t]
				split(type_files[t], files_arr, "\n")
				fn = 0
				delete sorted_files
				for (k in files_arr) { fn += 1; sorted_files[fn] = files_arr[k] }
				asort(sorted_files)
				for (k = 1; k <= fn; k++) {
					printf "    - `%s`\n", sorted_files[k]
				}
			}
		}
	}
'

# Truncation footer.
#
# Naming every capped subtree gets very noisy fast (a wide monorepo can
# have hundreds of siblings all capped at ~equal shares).  Show the top
# 10 by budget spent, then summarize the rest with a count.  The top-10
# picks out the subtrees where the walker got farthest before giving up
# -- these are usually the more interesting/heavy ones to know about.
if [ ${#truncated[@]} -gt 0 ]; then
	if [ "$wallclock_hit" -eq 1 ]; then
		echo "- (truncated: wallclock ${WALLCLOCK_SECS}s reached; ${budget_used} path handles walked)"
	else
		echo "- (truncated: budget of ${budget_max} path handles exhausted; ${budget_used} spent)"
	fi
	TOP_N=10
	mapfile -t sorted_trunc < <(
		for entry in "${truncated[@]}"; do
			printf '%s\n' "$entry"
		done | sort -t$'\t' -k2,2rn
	)
	shown=0
	for entry in "${sorted_trunc[@]}"; do
		if [ "$shown" -ge "$TOP_N" ]; then break; fi
		sub_path=${entry%%$'\t'*}
		sub_count=${entry##*$'\t'}
		rel=${sub_path#"$root"/}
		[ "$rel" = "$sub_path" ] && rel=$sub_path
		echo "  - \`${rel}/\` capped at ${sub_count}"
		shown=$((shown + 1))
	done
	if [ ${#truncated[@]} -gt "$TOP_N" ]; then
		echo "  - ... ($((${#truncated[@]} - TOP_N)) more capped subtrees)"
	fi
fi