densort.py

#!/usr/bin/env python3
"""
densort - Sort characters by pixel density for any font.

Requires: Pillow, fonttools
"""

from __future__ import annotations

import argparse
import shutil
import subprocess
import sys
import unicodedata
from dataclasses import dataclass
from operator import attrgetter
from pathlib import Path
from typing import TYPE_CHECKING, Final, TypeAlias

try:
    from PIL import Image, ImageDraw, ImageFont
except ImportError:
    sys.exit("Error: Pillow required. Install: pip install Pillow")

try:
    from fontTools.ttLib import TTFont  # type: ignore[import-untyped]
except ImportError:
    sys.exit("Error: fonttools required. Install: pip install fonttools")

if TYPE_CHECKING:
    from PIL.ImageFont import FreeTypeFont

UnsupportedChar: TypeAlias = tuple[str, str]

# Density measurement
CANVAS_SIZE: Final[int] = 256
FONT_SIZE: Final[int] = 200
TOTAL_PIXELS: Final[int] = CANVAS_SIZE * CANVAS_SIZE

# Bitmap rendering
BITMAP_RENDER_SCALE: Final[int] = 32
BITMAP_FONT_RATIO_DEFAULT: Final[float] = 0.95
DARK_THRESHOLD: Final[int] = 220
DARK_FILL_RATIO: Final[float] = 0.02


def _char_width(char: str) -> int:
    return 2 if unicodedata.east_asian_width(char) in ("F", "W") else 1


def _display_width(text: str) -> int:
    return sum(_char_width(c) for c in text if not unicodedata.category(c).startswith("M"))


def _split_graphemes(text: str) -> list[str]:
    """Split text into grapheme clusters (base char + combining marks)."""
    if not text:
        return []
    graphemes: list[str] = []
    current = ""
    for char in text:
        if char.isspace():
            if current:
                graphemes.append(current)
                current = ""
        elif unicodedata.category(char).startswith("M") and current:
            current += char
        else:
            if current:
                graphemes.append(current)
            current = char
    if current:
        graphemes.append(current)
    return graphemes


def _format_codepoints(text: str) -> str:
    """Format codepoints as U+XXXX or U+XXXX+U+XXXX for clusters."""
    if len(text) == 1:
        return f"U+{ord(text):04X}"
    return "+".join(f"U+{ord(c):04X}" for c in text)


class FontError(Exception):
    """Font loading or lookup failed."""


class InputError(Exception):
    """Input file reading failed."""


@dataclass(frozen=True, slots=True)
class CharacterDensity:
    char: str
    density: float
    filled_pixels: int

    @property
    def codepoint(self) -> str:
        return _format_codepoints(self.char)


def _fontconfig_lookup(font_name: str) -> str:
    if not shutil.which("fc-match"):
        raise FontError(
            "fontconfig (fc-match) not available.\n"
            "Provide full path to font file instead."
        )
    try:
        result = subprocess.run(
            ["fc-match", font_name, "--format=%{file}\n%{family}"],
            capture_output=True,
            text=True,
            timeout=10,
            check=False,
        )
    except subprocess.TimeoutExpired as exc:
        raise FontError(f"fontconfig timed out for '{font_name}'") from exc
    except OSError as exc:
        raise FontError(f"fontconfig execution failed: {exc}") from exc
    if result.returncode != 0:
        raise FontError(f"fontconfig error: {result.stderr.strip()}")
    lines = result.stdout.strip().split("\n")
    if len(lines) < 2 or not lines[0].strip():
        raise FontError(f"fontconfig returned no result for '{font_name}'")
    font_file, matched_family = lines[0].strip(), lines[1].strip()
    if not Path(font_file).exists():
        raise FontError(f"fontconfig path not found: {font_file}")

    req_norm = font_name.lower().replace("-", " ").replace("_", " ")
    match_norm = matched_family.lower().replace("-", " ").replace("_", " ")
    is_match = (
        req_norm in match_norm
        or match_norm in req_norm
        or req_norm.split()[0] in match_norm
    )
    if not is_match:
        raise FontError(
            f"Font '{font_name}' not found.\n"
            f"  fontconfig suggests: '{matched_family}' ({font_file})\n"
            f'  Use: fc-list | grep -i "{font_name}"'
        )
    return font_file


def resolve_font_path(font_spec: str) -> str:
    """Resolve font path or family name to absolute file path."""
    if "/" in font_spec or font_spec.startswith("~"):
        path = Path(font_spec).expanduser()
        if not path.exists():
            raise FontError(f"Font file not found: {font_spec}")
        if not path.is_file():
            raise FontError(f"Not a file: {font_spec}")
        return str(path.absolute())
    return _fontconfig_lookup(font_spec)


def load_font(path: str, size: int = FONT_SIZE) -> FreeTypeFont:
    try:
        return ImageFont.truetype(path, size)
    except OSError as exc:
        raise FontError(f"Cannot load font '{path}': {exc}") from exc


def load_font_cmap(path: str) -> frozenset[int]:
    """Extract supported codepoints from font."""
    try:
        with TTFont(path) as ttfont:
            cmap = ttfont.getBestCmap()
    except OSError as exc:
        raise FontError(f"Cannot read font file: {exc}") from exc
    except Exception as exc:
        raise FontError(f"Cannot parse font cmap: {exc}") from exc
    if cmap is None:
        raise FontError(f"Font has no character map: {path}")
    return frozenset(cmap.keys())


def load_characters(file_path: str) -> list[str]:
    """Load grapheme clusters from input file."""
    path = Path(file_path)
    if not path.exists():
        raise InputError(f"File not found: {file_path}")
    if not path.is_file():
        raise InputError(f"Not a file: {file_path}")
    try:
        content = path.read_text(encoding="utf-8")
    except PermissionError as exc:
        raise InputError(f"Permission denied: {file_path}") from exc
    except UnicodeDecodeError as exc:
        raise InputError(f"Invalid UTF-8: {file_path} ({exc})") from exc
    except OSError as exc:
        raise InputError(f"Read failed: {exc}") from exc

    chars = list(dict.fromkeys(_split_graphemes(content)))
    if not chars:
        raise InputError(f"No characters found in: {file_path}")
    return chars


def _render_centered(char: str, font: FreeTypeFont, size: int) -> Image.Image:
    """Render glyph centered on grayscale canvas."""
    img = Image.new("L", (size, size), 255)
    draw = ImageDraw.Draw(img)
    bbox = draw.textbbox((0, 0), char, font=font)  # type: ignore[arg-type]
    width, height = bbox[2] - bbox[0], bbox[3] - bbox[1]
    if width <= 0 or height <= 0:
        raise ValueError("Zero-size glyph")
    x = (size - width) // 2 - bbox[0]
    y = (size - height) // 2 - bbox[1]
    draw.text((x, y), char, font=font, fill=0)  # type: ignore[arg-type]
    return img


def measure_density(char: str, font: FreeTypeFont) -> CharacterDensity:
    img = _render_centered(char, font, CANVAS_SIZE)
    pixels = img.tobytes()
    pixel_sum = sum(pixels)
    density = 1.0 - pixel_sum / (255 * TOTAL_PIXELS)
    return CharacterDensity(
        char=char,
        density=density,
        filled_pixels=int(density * TOTAL_PIXELS),
    )


def render_bitmap(char: str, font: FreeTypeFont, size: int = 8) -> list[int]:
    """Render character to 1-bit bitmap using area-based sampling."""
    render_size = size * BITMAP_RENDER_SCALE
    try:
        img = _render_centered(char, font, render_size)
    except ValueError:
        return [0] * size

    pixels = img.tobytes()
    cell_size = BITMAP_RENDER_SCALE
    threshold_count = max(1, int(cell_size * cell_size * DARK_FILL_RATIO))

    rows: list[int] = []
    for row_idx in range(size):
        row_value = 0
        for col_idx in range(size):
            dark_count = 0
            base_x = col_idx * cell_size
            base_y = row_idx * cell_size

            for cy in range(cell_size):
                row_offset = (base_y + cy) * render_size + base_x
                for cx in range(cell_size):
                    if pixels[row_offset + cx] < DARK_THRESHOLD:
                        dark_count += 1
                        if dark_count >= threshold_count:
                            break
                if dark_count >= threshold_count:
                    break

            if dark_count >= threshold_count:
                row_value |= 1 << (size - 1 - col_idx)

        rows.append(row_value)

    return rows


def process_characters(
    chars: list[str],
    font: FreeTypeFont,
    cmap: frozenset[int],
    *,
    descending: bool,
) -> tuple[list[CharacterDensity], list[UnsupportedChar]]:
    results: list[CharacterDensity] = []
    unsupported: list[UnsupportedChar] = []
    for char in chars:
        missing = [c for c in char if ord(c) not in cmap]
        if missing:
            unsupported.append((char, f"missing: {', '.join(_format_codepoints(c) for c in missing)}"))
            continue
        try:
            results.append(measure_density(char, font))
        except ValueError as exc:
            unsupported.append((char, str(exc)))
    if not results:
        raise ValueError("Font supports none of the input characters")
    results.sort(key=attrgetter("density"), reverse=descending)
    return results, unsupported


def _build_header(font_path: str, order: str, total: int, processed: int) -> list[str]:
    return [
        f"Font:      {font_path}",
        f"Order:     {order}",
        f"Input:     {total} characters",
        f"Processed: {processed} characters",
        "",
    ]


def _build_error_section(unsupported: list[UnsupportedChar]) -> list[str]:
    return [
        "",
        f"Unsupported ({len(unsupported)}):",
        *(f"  '{c}' ({_format_codepoints(c)}): {reason}" for c, reason in unsupported),
    ]


def _build_table(headers: list[str], rows: list[list[str]]) -> list[str]:
    widths = [
        max(_display_width(h), *(_display_width(row[i]) for row in rows)) + 2
        for i, h in enumerate(headers)
    ]

    def pad_center(text: str, width: int) -> str:
        padding = width - _display_width(text)
        left = padding // 2
        return " " * left + text + " " * (padding - left)

    def make_row(cells: list[str]) -> str:
        return "│" + "│".join(
            pad_center(c, w) for c, w in zip(cells, widths, strict=True)
        ) + "│"

    return [
        "┌" + "┬".join("─" * w for w in widths) + "┐",
        make_row(headers),
        "├" + "┼".join("─" * w for w in widths) + "┤",
        *(make_row(row) for row in rows),
        "└" + "┴".join("─" * w for w in widths) + "┘",
    ]


def format_table(
    results: list[CharacterDensity],
    unsupported: list[UnsupportedChar],
    font_path: str,
    order: str,
    total: int,
) -> str:
    lines = _build_header(font_path, order, total, len(results))
    headers = ["Char", "Density", "Pixels", "Unicode"]
    rows = [
        [r.char, f"{r.density:.6f}", f"{r.filled_pixels}/{TOTAL_PIXELS}", r.codepoint]
        for r in results
    ]
    lines.extend(_build_table(headers, rows))
    lines.extend(["", f"Density ramp ({order}):", "".join(r.char for r in results)])
    if unsupported:
        lines.extend(_build_error_section(unsupported))
    return "\n".join(lines)


def format_bitmap(
    results: list[CharacterDensity],
    unsupported: list[UnsupportedChar],
    font_path: str,
    order: str,
    total: int,
    font_ratio: float = BITMAP_FONT_RATIO_DEFAULT,
) -> str:
    lines = _build_header(font_path, order, total, len(results))
    char_count = len(results)
    font_size_8 = int(8 * BITMAP_RENDER_SCALE * font_ratio)
    font_size_16 = int(16 * BITMAP_RENDER_SCALE * font_ratio)
    font_8 = load_font(font_path, font_size_8)
    font_16 = load_font(font_path, font_size_16)

    lines.extend(["", f"// 8x8 bitmap ({char_count} chars)", "{"])
    for r in results:
        bitmap = render_bitmap(r.char, font_8, 8)
        hex_str = ", ".join(f"0x{b:02X}" for b in bitmap)
        lines.append(f"    {{{hex_str}}}, // {r.char}")
    lines.append("};")

    lines.extend(["", f"// 16x16 bitmap ({char_count} chars)", "{"])
    for r in results:
        bitmap = render_bitmap(r.char, font_16, 16)
        hex_row1 = ", ".join(f"0x{b:04X}" for b in bitmap[:8])
        hex_row2 = ", ".join(f"0x{b:04X}" for b in bitmap[8:])
        lines.append(f"    {{{hex_row1},")
        lines.append(f"     {hex_row2}}}, // {r.char}")
    lines.append("};")

    lines.extend(["", f"Density ramp ({order}):", "".join(r.char for r in results)])
    if unsupported:
        lines.extend(_build_error_section(unsupported))
    return "\n".join(lines)


def main() -> int:
    parser = argparse.ArgumentParser(
        prog="densort",
        formatter_class=argparse.RawDescriptionHelpFormatter,
        epilog="""\
examples:
  python3 densort.py -f /usr/share/fonts/truetype/dejavu/DejaVuSansMono.ttf -i chars.txt
  python3 densort.py -f "Comic Sans MS" -i chars.txt -o asc -b
  python3 densort.py -f "Noto Sans Thai" -i chars.txt -b -r 0.8

list all fonts (Unix):
  fc-list
""",
    )
    parser.add_argument(
        "-i", "--input", required=True, metavar="FILE",
        help="Input file containing characters to analyze",
    )
    parser.add_argument(
        "-f", "--font", required=True, metavar="FONT",
        help="Font file path or family name",
    )
    parser.add_argument(
        "-o", "--order", choices=["desc", "asc"], default="desc",
        help="Sort order: desc=dense-first (default), asc=sparse-first",
    )
    parser.add_argument(
        "-b", "--bitmap", action="store_true",
        help="Output as C-style 8x8 and 16x16 bitmap arrays",
    )
    parser.add_argument(
        "-r", "--font-ratio", type=float, default=BITMAP_FONT_RATIO_DEFAULT, metavar="R",
        help="Font size ratio for bitmap rendering (0.5-0.99, default: 0.95).",
    )
    args = parser.parse_args()

    if not 0.5 <= args.font_ratio <= 0.99:
        print("Error: --font-ratio must be between 0.5 and 0.99", file=sys.stderr)
        return 1

    try:
        chars = load_characters(args.input)
    except InputError as exc:
        print(f"Error: {exc}", file=sys.stderr)
        return 1

    print("Loading font...", file=sys.stderr)
    try:
        font_path = resolve_font_path(args.font)
        font = load_font(font_path)
        cmap = load_font_cmap(font_path)
    except FontError as exc:
        print(f"Error: {exc}", file=sys.stderr)
        return 1
    print(f"Codepoints: {len(cmap):,}", file=sys.stderr)

    try:
        results, unsupported = process_characters(
            chars, font, cmap, descending=(args.order == "desc")
        )
    except ValueError as exc:
        print(f"Error: {exc}", file=sys.stderr)
        return 1

    if args.bitmap:
        output = format_bitmap(
            results, unsupported, font_path, args.order, len(chars), args.font_ratio
        )
    else:
        output = format_table(results, unsupported, font_path, args.order, len(chars))
    print(output)
    print(f"\nProcessed {len(results)}/{len(chars)} characters.", file=sys.stderr)
    if unsupported:
        print(f"WARNING: {len(unsupported)} unsupported character(s).", file=sys.stderr)
    return 0


if __name__ == "__main__":
    sys.exit(main())