package fonts

import (
	"encoding/binary"
	"errors"
	"fmt"
	"sort"
	"sync"
)

// A minimal TrueType reader and subsetter — enough to measure text and
// to embed a face in a PDF, and deliberately not one byte more.
//
// It reads the six tables a CIDFontType2 embedding actually requires
// (head, hhea, maxp, hmtx, loca, glyf) plus cmap to find glyphs by
// rune, and post/OS2 for the two descriptor fields a PDF reader wants.
// It does not read GPOS, so it does not kern; text measured here is
// the sum of advance widths, which is what an unkerned browser layout
// of the same string also is. It does not read GSUB, so no ligatures
// and no complex-script shaping — a document in a script that needs
// shaping lays out wrongly here, which is the same limitation §11.1
// already records for the scripts outside the core set.
//
// # Why subsetting keeps the original glyph ids
//
// The usual subsetter renumbers glyphs densely and rewrites every
// reference to them. This one keeps every glyph id exactly where it
// was and simply empties the glyphs nothing uses: `loca` still has
// numGlyphs+1 entries, but an unused glyph's two entries are equal, so
// it occupies no bytes in `glyf`.
//
// That is a real subset — a document using eighty glyphs of Liberation
// Serif embeds about 25KB rather than 385KB — and it removes the two
// places renumbering goes wrong: composite glyphs referring to their
// components by id (no remapping needed, because ids do not move), and
// the PDF's CIDToGIDMap (Identity, because a CID *is* the glyph id).
// What it costs is `hmtx` and `loca`, which stay proportional to the
// font's full glyph count rather than the subset's. For a 2,500-glyph
// face that is about 15KB — worth paying to not have a subsetter whose
// failure mode is a document that renders with the wrong letters.

var (
	errShortTable = errors.New("fonts: truetype table is shorter than its own header claims")
	errNoTable    = errors.New("fonts: truetype table missing")
)

// Font is a parsed face.
type Font struct {
	data   []byte
	tables map[string][]byte

	UnitsPerEm uint16
	NumGlyphs  uint16

	// Ascender, Descender and LineGap are hhea's, in font units.
	// Descender is negative, as the table stores it.
	Ascender  int16
	Descender int16
	LineGap   int16

	// CapHeight and ItalicAngle are for the PDF font descriptor. Both
	// have defaults that are wrong-but-harmless if the source tables
	// are absent (a reader uses them for substitution decisions it
	// will never have to make, because the font is embedded).
	CapHeight   int16
	ItalicAngle float64
	BBox        [4]int16

	indexToLocFormat int16
	numberOfHMetrics uint16

	advances []uint16 // one per glyph id, font units
	cmap     map[rune]uint16
}

func be16(b []byte, off int) (uint16, bool) {
	if off < 0 || off+2 > len(b) {
		return 0, false
	}
	return binary.BigEndian.Uint16(b[off:]), true
}

func be32(b []byte, off int) (uint32, bool) {
	if off < 0 || off+4 > len(b) {
		return 0, false
	}
	return binary.BigEndian.Uint32(b[off:]), true
}

// Parse reads the tables this package needs out of a TrueType file.
//
// Every read is bounds-checked even though the only fonts reaching it
// are the twelve embedded in this binary: a parser that is careful
// only about untrusted input is a parser nobody may ever point at
// untrusted input, and this one is one `//go:embed` away from being
// handed a font a person uploaded.
func Parse(data []byte) (*Font, error) {
	if len(data) < 12 {
		return nil, errShortTable
	}
	switch binary.BigEndian.Uint32(data) {
	case 0x00010000, 0x74727565: // 'true'
	default:
		return nil, fmt.Errorf("fonts: not a TrueType outline font (sfnt version %#x)", binary.BigEndian.Uint32(data))
	}
	numTables := int(binary.BigEndian.Uint16(data[4:]))
	tables := make(map[string][]byte, numTables)
	for i := 0; i < numTables; i++ {
		rec := 12 + i*16
		if rec+16 > len(data) {
			return nil, errShortTable
		}
		tag := string(data[rec : rec+4])
		off := int(binary.BigEndian.Uint32(data[rec+8:]))
		length := int(binary.BigEndian.Uint32(data[rec+12:]))
		if off < 0 || length < 0 || off+length > len(data) {
			return nil, fmt.Errorf("fonts: table %q runs past the end of the file", tag)
		}
		tables[tag] = data[off : off+length]
	}

	f := &Font{data: data, tables: tables}

	head, ok := tables["head"]
	if !ok || len(head) < 54 {
		return nil, fmt.Errorf("%w: head", errNoTable)
	}
	f.UnitsPerEm = binary.BigEndian.Uint16(head[18:])
	if f.UnitsPerEm == 0 {
		return nil, errors.New("fonts: head.unitsPerEm is zero")
	}
	for i := 0; i < 4; i++ {
		f.BBox[i] = int16(binary.BigEndian.Uint16(head[36+i*2:]))
	}
	f.indexToLocFormat = int16(binary.BigEndian.Uint16(head[50:]))

	hhea, ok := tables["hhea"]
	if !ok || len(hhea) < 36 {
		return nil, fmt.Errorf("%w: hhea", errNoTable)
	}
	f.Ascender = int16(binary.BigEndian.Uint16(hhea[4:]))
	f.Descender = int16(binary.BigEndian.Uint16(hhea[6:]))
	f.LineGap = int16(binary.BigEndian.Uint16(hhea[8:]))
	f.numberOfHMetrics = binary.BigEndian.Uint16(hhea[34:])

	maxp, ok := tables["maxp"]
	if !ok || len(maxp) < 6 {
		return nil, fmt.Errorf("%w: maxp", errNoTable)
	}
	f.NumGlyphs = binary.BigEndian.Uint16(maxp[4:])

	if os2, ok := tables["OS/2"]; ok && len(os2) >= 90 {
		f.CapHeight = int16(binary.BigEndian.Uint16(os2[88:]))
	}
	if f.CapHeight == 0 {
		// sCapHeight is only present from OS/2 version 2. The ascender
		// overstates cap height slightly; a PDF reader uses this for
		// substitution metrics it never needs for an embedded font.
		f.CapHeight = f.Ascender
	}
	if post, ok := tables["post"]; ok && len(post) >= 12 {
		// Fixed 16.16 signed.
		f.ItalicAngle = float64(int32(binary.BigEndian.Uint32(post[4:]))) / 65536.0
	}

	if err := f.parseHmtx(); err != nil {
		return nil, err
	}
	if err := f.parseCmap(); err != nil {
		return nil, err
	}
	return f, nil
}

func (f *Font) parseHmtx() error {
	hmtx, ok := f.tables["hmtx"]
	if !ok {
		return fmt.Errorf("%w: hmtx", errNoTable)
	}
	n := int(f.numberOfHMetrics)
	if n == 0 || n > int(f.NumGlyphs) {
		return errors.New("fonts: hhea.numberOfHMetrics disagrees with maxp.numGlyphs")
	}
	f.advances = make([]uint16, f.NumGlyphs)
	var last uint16
	for i := 0; i < int(f.NumGlyphs); i++ {
		if i < n {
			v, ok := be16(hmtx, i*4)
			if !ok {
				return errShortTable
			}
			last = v
		}
		// Past numberOfHMetrics every glyph repeats the last advance —
		// that is what the table's compressed tail means, not "no
		// advance".
		f.advances[i] = last
	}
	return nil
}

// parseCmap picks the best Unicode subtable it understands and expands
// it into a map. Expanding eagerly rather than searching per lookup:
// a face has a few thousand mapped runes, a document has thousands of
// characters, and the map is built once per face per process.
func (f *Font) parseCmap() error {
	cm, ok := f.tables["cmap"]
	if !ok || len(cm) < 4 {
		// Not an error. A font whose glyphs are addressed by id rather
		// than by rune needs no cmap and is required to carry none —
		// which is exactly what Subset produces, since a PDF
		// CIDFontType2 under Identity-H looks glyphs up by id. Parse
		// has to be able to read its own output back, which is how the
		// subsetter is tested at all.
		//
		// The risk this accepts is a *primary* face arriving without a
		// usable cmap and measuring every character as .notdef in
		// silence. That is caught where it can actually be judged:
		// fonts_test.go's TestEveryFaceParses asserts each of the
		// twelve embedded faces resolves ordinary prose to real glyph
		// ids, which a cmap-less face cannot do.
		f.cmap = map[rune]uint16{}
		return nil
	}
	n := int(binary.BigEndian.Uint16(cm[2:]))

	// Preference order: a full-repertoire subtable first, then a BMP
	// one. (3,10) and (0,4)/(0,6) are format 12; (3,1) and (0,3) are
	// format 4.
	best, bestScore := -1, -1
	for i := 0; i < n; i++ {
		rec := 4 + i*8
		plat, ok1 := be16(cm, rec)
		enc, ok2 := be16(cm, rec+2)
		off, ok3 := be32(cm, rec+4)
		if !ok1 || !ok2 || !ok3 || int(off) >= len(cm) {
			continue
		}
		score := -1
		switch {
		case plat == 3 && enc == 10:
			score = 4
		case plat == 0 && (enc == 4 || enc == 6):
			score = 3
		case plat == 3 && enc == 1:
			score = 2
		case plat == 0:
			score = 1
		}
		if score > bestScore {
			best, bestScore = int(off), score
		}
	}
	if best < 0 {
		return errors.New("fonts: cmap has no Unicode subtable this build understands")
	}
	sub := cm[best:]
	format, ok := be16(sub, 0)
	if !ok {
		return errShortTable
	}
	f.cmap = make(map[rune]uint16, 1024)
	switch format {
	case 4:
		return f.parseCmap4(sub)
	case 12:
		return f.parseCmap12(sub)
	default:
		return fmt.Errorf("fonts: cmap subtable format %d is not supported", format)
	}
}

func (f *Font) parseCmap4(sub []byte) error {
	segX2, ok := be16(sub, 6)
	if !ok || segX2%2 != 0 {
		return errShortTable
	}
	seg := int(segX2 / 2)
	endBase := 14
	startBase := endBase + seg*2 + 2
	deltaBase := startBase + seg*2
	rangeBase := deltaBase + seg*2
	if rangeBase+seg*2 > len(sub) {
		return errShortTable
	}
	for i := 0; i < seg; i++ {
		end := binary.BigEndian.Uint16(sub[endBase+i*2:])
		start := binary.BigEndian.Uint16(sub[startBase+i*2:])
		delta := binary.BigEndian.Uint16(sub[deltaBase+i*2:])
		ro := binary.BigEndian.Uint16(sub[rangeBase+i*2:])
		if start > end {
			continue
		}
		for c := uint32(start); c <= uint32(end); c++ {
			if c == 0xFFFF {
				continue // the required terminating segment, not a character
			}
			var gid uint16
			if ro == 0 {
				gid = uint16(c) + delta
			} else {
				// The idRangeOffset trick: the offset is measured from
				// the address of the idRangeOffset entry itself.
				at := rangeBase + i*2 + int(ro) + int(c-uint32(start))*2
				g, ok := be16(sub, at)
				if !ok {
					continue
				}
				if g == 0 {
					continue
				}
				gid = g + delta
			}
			if gid != 0 && gid < f.NumGlyphs {
				f.cmap[rune(c)] = gid
			}
		}
	}
	return nil
}

func (f *Font) parseCmap12(sub []byte) error {
	nGroups, ok := be32(sub, 12)
	if !ok {
		return errShortTable
	}
	// A group table that does not fit is the end of the table, not a
	// row to skip: nGroups is a number from the file, and a hostile one
	// of four billion against a short table would otherwise spin four
	// billion no-op iterations. Bounded by the bytes actually present
	// rather than by the count the file claims.
	if max := (len(sub) - 16) / 12; max >= 0 && nGroups > uint32(max) {
		nGroups = uint32(max)
	}
	for i := uint32(0); i < nGroups; i++ {
		at := 16 + int(i)*12
		start, ok1 := be32(sub, at)
		end, ok2 := be32(sub, at+4)
		gid, ok3 := be32(sub, at+8)
		if !ok1 || !ok2 || !ok3 {
			break // the table ended mid-group; nothing after it is readable
		}
		if start > end {
			continue
		}
		// A pathological group spanning the whole of Unicode would
		// otherwise build a map with a million entries.
		if end-start > 0x10FFFF {
			continue
		}
		for c := start; c <= end; c++ {
			g := gid + (c - start)
			if g != 0 && g < uint32(f.NumGlyphs) {
				f.cmap[rune(c)] = uint16(g)
			}
		}
	}
	return nil
}

// glyphData returns the bytes of one glyph's outline, or nil for a
// glyph with none (a space, or one this subsetter emptied).
func (f *Font) glyphData(gid uint16) []byte {
	loca, err := f.locaOffsets()
	if err != nil {
		return nil
	}
	glyf, ok := f.tables["glyf"]
	if !ok || int(gid)+1 >= len(loca) {
		return nil
	}
	start, end := loca[gid], loca[gid+1]
	if start >= end || int(end) > len(glyf) {
		return nil
	}
	return glyf[start:end]
}

// GlyphLen is how many bytes glyph gid occupies — zero for a glyph
// with no outline, which is what a subsetted-away glyph looks like.
func (f *Font) GlyphLen(gid uint16) int { return len(f.glyphData(gid)) }

// GlyphIsComposite reports whether gid is assembled from other glyphs.
func (f *Font) GlyphIsComposite(gid uint16) bool {
	g := f.glyphData(gid)
	return len(g) >= 2 && int16(binary.BigEndian.Uint16(g)) < 0
}

// GlyphIndex maps a rune to a glyph id, or 0 (.notdef) if the face has
// no glyph for it. Callers decide what a 0 means: internal/pdf reports
// it as a substitution in the export rather than silently drawing an
// empty box, which is §11.2's degrade-loudly rule.
func (f *Font) GlyphIndex(r rune) uint16 { return f.cmap[r] }

// Advance is the glyph's advance width in font units.
func (f *Font) Advance(gid uint16) uint16 {
	if int(gid) >= len(f.advances) {
		return 0
	}
	return f.advances[gid]
}

// WidthEm is the advance of a run of text as a multiple of the em, so
// a caller multiplies by a point size and gets points. Returns the
// glyph ids it used, so the caller can accumulate a subset without
// walking the string twice.
func (f *Font) WidthEm(s string) (width float64, gids []uint16) {
	upm := float64(f.UnitsPerEm)
	for _, r := range s {
		gid := f.GlyphIndex(r)
		gids = append(gids, gid)
		width += float64(f.Advance(gid)) / upm
	}
	return width, gids
}

// locaOffsets reads loca into a plain slice of byte offsets into glyf.
func (f *Font) locaOffsets() ([]uint32, error) {
	loca, ok := f.tables["loca"]
	if !ok {
		return nil, fmt.Errorf("%w: loca", errNoTable)
	}
	n := int(f.NumGlyphs) + 1
	out := make([]uint32, n)
	if f.indexToLocFormat == 0 {
		if len(loca) < n*2 {
			return nil, errShortTable
		}
		for i := 0; i < n; i++ {
			// The short format stores offset/2.
			out[i] = uint32(binary.BigEndian.Uint16(loca[i*2:])) * 2
		}
		return out, nil
	}
	if len(loca) < n*4 {
		return nil, errShortTable
	}
	for i := 0; i < n; i++ {
		out[i] = binary.BigEndian.Uint32(loca[i*4:])
	}
	return out, nil
}

// componentsOf returns the glyph ids a composite glyph is built from.
// A subset that keeps "é" but drops the "e" and the acute it is
// assembled from renders as nothing at all, which is the failure this
// exists to prevent.
func componentsOf(glyph []byte) []uint16 {
	if len(glyph) < 10 {
		return nil
	}
	if int16(binary.BigEndian.Uint16(glyph)) >= 0 {
		return nil // simple glyph, no components
	}
	var out []uint16
	at := 10
	for {
		flags, ok1 := be16(glyph, at)
		gid, ok2 := be16(glyph, at+2)
		if !ok1 || !ok2 {
			return out
		}
		out = append(out, gid)
		at += 4
		if flags&0x0001 != 0 { // ARG_1_AND_2_ARE_WORDS
			at += 4
		} else {
			at += 2
		}
		switch {
		case flags&0x0008 != 0: // WE_HAVE_A_SCALE
			at += 2
		case flags&0x0040 != 0: // WE_HAVE_AN_X_AND_Y_SCALE
			at += 4
		case flags&0x0080 != 0: // WE_HAVE_A_TWO_BY_TWO
			at += 8
		}
		if flags&0x0020 == 0 { // MORE_COMPONENTS
			return out
		}
	}
}

// Subset returns a TrueType file containing only the glyphs in keep
// (plus .notdef and, transitively, the components of any composite
// glyph kept). Glyph ids are unchanged — see this file's header for
// why that is the whole design.
func (f *Font) Subset(keep map[uint16]bool) ([]byte, error) {
	loca, err := f.locaOffsets()
	if err != nil {
		return nil, err
	}
	glyf, ok := f.tables["glyf"]
	if !ok {
		return nil, fmt.Errorf("%w: glyf", errNoTable)
	}

	glyphAt := func(gid uint16) []byte {
		if int(gid)+1 >= len(loca) {
			return nil
		}
		start, end := loca[gid], loca[gid+1]
		if start >= end || int(end) > len(glyf) {
			return nil // an empty glyph, e.g. the space
		}
		return glyf[start:end]
	}

	// Close over composites. A worklist rather than recursion: the
	// component graph in a hostile font can be cyclic, and `seen`
	// terminates either way.
	seen := map[uint16]bool{0: true} // .notdef always ships
	work := []uint16{0}
	for gid := range keep {
		if !seen[gid] {
			seen[gid] = true
			work = append(work, gid)
		}
	}
	for len(work) > 0 {
		gid := work[len(work)-1]
		work = work[:len(work)-1]
		for _, c := range componentsOf(glyphAt(gid)) {
			if !seen[c] && int(c) < int(f.NumGlyphs) {
				seen[c] = true
				work = append(work, c)
			}
		}
	}

	// Rebuild glyf and loca. Every glyph keeps its id; the ones not in
	// `seen` get a zero-length entry.
	var newGlyf []byte
	newLoca := make([]uint32, int(f.NumGlyphs)+1)
	for gid := 0; gid < int(f.NumGlyphs); gid++ {
		newLoca[gid] = uint32(len(newGlyf))
		if seen[uint16(gid)] {
			g := glyphAt(uint16(gid))
			newGlyf = append(newGlyf, g...)
			for len(newGlyf)%4 != 0 { // glyphs are 4-byte aligned
				newGlyf = append(newGlyf, 0)
			}
		}
	}
	newLoca[f.NumGlyphs] = uint32(len(newGlyf))

	// Long loca throughout: the short format cannot express an offset
	// above 131,070 and cannot express an odd one at all, and choosing
	// per-font would mean two code paths where one is barely exercised.
	locaBytes := make([]byte, len(newLoca)*4)
	for i, off := range newLoca {
		binary.BigEndian.PutUint32(locaBytes[i*4:], off)
	}

	head := append([]byte(nil), f.tables["head"]...)
	binary.BigEndian.PutUint16(head[50:], 1) // indexToLocFormat: long
	binary.BigEndian.PutUint32(head[8:], 0)  // checkSumAdjustment, set below

	out := map[string][]byte{
		"head": head,
		"hhea": f.tables["hhea"],
		"maxp": f.tables["maxp"],
		"hmtx": f.tables["hmtx"],
		"loca": locaBytes,
		"glyf": newGlyf,
	}

	// The hinting tables travel with the glyphs, when the font has
	// them. ISO 32000-1 §9.9 requires `cvt `, `fpgm` and `prep` to be
	// present when the glyph instructions need them, and Liberation's
	// do: every glyph here carries bytecode that calls functions
	// defined in `fpgm` and reads values out of `cvt `. Shipping the
	// outlines without them leaves a reader executing instructions
	// against definitions that are not in the file — most fall back to
	// unhinted rendering and it merely looks softer, but a strict
	// rasterizer or a printer RIP is entitled to do worse, and the
	// file is not conformant either way.
	//
	// About 15KB a face, which is the cheapest correctness in this
	// package. They are copied verbatim: they are indexed by nothing
	// this subsetter renumbers, because glyph ids do not move.
	for _, tag := range []string{"cvt ", "fpgm", "prep"} {
		if b, ok := f.tables[tag]; ok && len(b) > 0 {
			out[tag] = b
		}
	}
	for tag, b := range out {
		if b == nil {
			return nil, fmt.Errorf("%w: %s", errNoTable, tag)
		}
	}
	return buildSfnt(out), nil
}

// buildSfnt assembles a TrueType file from a tag→bytes map.
func buildSfnt(tables map[string][]byte) []byte {
	tags := make([]string, 0, len(tables))
	for t := range tables {
		tags = append(tags, t)
	}
	sort.Strings(tags) // the table directory must be in tag order

	n := len(tags)
	// searchRange/entrySelector/rangeShift are a binary-search hint a
	// modern reader ignores but a strict validator checks.
	entrySelector := 0
	for 1<<(entrySelector+1) <= n {
		entrySelector++
	}
	searchRange := 16 * (1 << entrySelector)
	rangeShift := 16*n - searchRange

	header := make([]byte, 12+16*n)
	binary.BigEndian.PutUint32(header, 0x00010000)
	binary.BigEndian.PutUint16(header[4:], uint16(n))
	binary.BigEndian.PutUint16(header[6:], uint16(searchRange))
	binary.BigEndian.PutUint16(header[8:], uint16(entrySelector))
	binary.BigEndian.PutUint16(header[10:], uint16(rangeShift))

	body := []byte{}
	offset := len(header)
	for i, tag := range tags {
		b := tables[tag]
		rec := 12 + i*16
		copy(header[rec:], tag)
		binary.BigEndian.PutUint32(header[rec+4:], tableChecksum(b))
		binary.BigEndian.PutUint32(header[rec+8:], uint32(offset+len(body)))
		binary.BigEndian.PutUint32(header[rec+12:], uint32(len(b)))
		body = append(body, b...)
		for len(body)%4 != 0 {
			body = append(body, 0)
		}
	}

	file := append(header, body...)

	// head.checkSumAdjustment: 0xB1B0AFBA minus the checksum of the
	// whole file computed with this field zeroed, which it is.
	for i, tag := range tags {
		if tag != "head" {
			continue
		}
		headOff := int(binary.BigEndian.Uint32(file[12+i*16+8:]))
		if headOff+12 <= len(file) {
			adj := 0xB1B0AFBA - tableChecksum(file)
			binary.BigEndian.PutUint32(file[headOff+8:], adj)
		}
	}
	return file
}

func tableChecksum(b []byte) uint32 {
	var sum uint32
	for i := 0; i+4 <= len(b); i += 4 {
		sum += binary.BigEndian.Uint32(b[i:])
	}
	// A table's length is padded to four bytes for checksum purposes
	// even when the bytes themselves are not present.
	if rem := len(b) % 4; rem != 0 {
		var tail [4]byte
		copy(tail[:], b[len(b)-rem:])
		sum += binary.BigEndian.Uint32(tail[:])
	}
	return sum
}

// --- parsed-face cache ---

var (
	parsedMu sync.Mutex
	parsed   = map[string]*Font{}
)

// Parsed returns this face's parsed font, cached per process. Parsing
// expands the cmap into a map of a few thousand entries, which is
// cheap once and pointless twelve times a request.
func (f Face) Parsed() (*Font, error) {
	parsedMu.Lock()
	defer parsedMu.Unlock()
	if font, ok := parsed[f.File]; ok {
		return font, nil
	}
	font, err := Parse(f.Data)
	if err != nil {
		return nil, fmt.Errorf("fonts: parse %s: %w", f.File, err)
	}
	parsed[f.File] = font
	return font, nil
}