playlink/internal/engine/dupes.go

package engine

import (
	"context"
	"errors"
	"fmt"
	"io/fs"
	"math"
	"os"
	"path/filepath"
	"sort"
	"strings"
	"time"

	"github.com/cdnutter/playlink/internal/fsops"
	"github.com/cdnutter/playlink/internal/probe"
	"github.com/cdnutter/playlink/internal/store"
)

// Duplicates are the same song filed more than once in the slave library,
// typically a single next to the album version ("Song - Single/Song.mp3" and
// "Album/03 Song.flac"), or one song in two formats. They are found by the
// same title rules as approximate matching (track numbers and release labels
// such as "Single Version" ignored, live/remix/acoustic versions kept apart)
// within one top-level folder. One copy of each group is recommended to keep;
// removing the others needs the user's confirmation and moves them into the
// quarantine, so they can be restored from History.

// DupeFile is one copy of a duplicated song.
type DupeFile struct {
	Rel     string      `json:"rel"`
	Size    int64       `json:"size"`
	Release string      `json:"release"` // album, single or compilation (from the folder name)
	Linked  bool        `json:"linked"`  // a hardlink of a master file: it takes no extra space
	Probe   *probe.Info `json:"probe,omitempty"`
	Keep    bool        `json:"keep"` // the copy recommended to keep

	ino     uint64
	mtimeNs int64
	tracks  int // songs in its album folder
}

// DupeGroup is one song found more than once.
type DupeGroup struct {
	ID    string     `json:"id"`
	Title string     `json:"title"`
	Files []DupeFile `json:"files"`
	Notes []string   `json:"notes,omitempty"`
}

// DupeScan is the result of the latest duplicate search.
type DupeScan struct {
	CreatedAt int64       `json:"created_at"`
	Files     int         `json:"files"` // slave files checked
	Groups    []DupeGroup `json:"groups"`
	Probed    bool        `json:"probed"` // codec details and artist tags were available
}

// dupeKey groups songs: top-level folder (normally the artist), the cleaned
// title and its version words.
func dupeKey(rel string, ti titleInfo) string {
	if ti.norm == "" {
		return ""
	}
	vs := make([]string, 0, len(ti.versions))
	for v := range ti.versions {
		vs = append(vs, v)
	}
	sort.Strings(vs)
	return strings.ToLower(firstComponent(rel)) + "|" + ti.norm + "|" + strings.Join(vs, ",")
}

func releaseOf(ti titleInfo) string {
	switch {
	case ti.single:
		return "single"
	case ti.compilation:
		return "compilation"
	}
	return "album"
}

// normArtist reduces an artist tag to letters and digits.
func normArtist(s string) string {
	return strings.Join(words(s), "")
}

// sameArtist treats "Artist" and "Artist feat. Someone" as one artist.
func sameArtist(a, b string) bool {
	return a == b || strings.HasPrefix(a, b) || strings.HasPrefix(b, a)
}

// splitByArtist keeps files whose artist tags disagree apart, so a folder
// layout like Genre/Artist/Song doesn't group two artists' songs with the
// same title. Untagged files join the tagged ones only when there is no
// doubt which artist they belong to.
func splitByArtist(files []DupeFile) [][]DupeFile {
	var clusters [][]DupeFile
	var reps []string
	var untagged []DupeFile
	for _, f := range files {
		a := ""
		if f.Probe != nil && f.Probe.Error == "" {
			a = normArtist(f.Probe.Artist)
		}
		if a == "" {
			untagged = append(untagged, f)
			continue
		}
		placed := false
		for i, r := range reps {
			if sameArtist(a, r) {
				clusters[i] = append(clusters[i], f)
				placed = true
				break
			}
		}
		if !placed {
			reps = append(reps, a)
			clusters = append(clusters, []DupeFile{f})
		}
	}
	switch len(clusters) {
	case 0:
		return [][]DupeFile{untagged}
	case 1:
		clusters[0] = append(clusters[0], untagged...)
	}
	return clusters
}

// keepBetter reports whether a is the better copy to keep than b: an album
// release over a single or compilation, then one already linked to the
// master (it takes no extra space), then the better quality, then the fuller
// album, then the better format.
func keepBetter(a, b DupeFile) bool {
	if ra, rb := a.Release == "album", b.Release == "album"; ra != rb {
		return ra
	}
	if a.Release != b.Release {
		return a.Release == "single" // a single over a compilation
	}
	if a.Linked != b.Linked {
		return a.Linked
	}
	if a.Probe != nil && b.Probe != nil {
		sa, sb := probe.Score(*a.Probe), probe.Score(*b.Probe)
		if sa > 0 && sb > 0 && math.Abs(sa-sb) > 0.05*math.Max(sa, sb) {
			return sa > sb
		}
	}
	if a.tracks != b.tracks {
		return a.tracks > b.tracks
	}
	if ra, rb := extRank(a.Rel), extRank(b.Rel); ra != rb {
		return ra < rb
	}
	return a.Rel < b.Rel
}

func minSec(sec float64) string {
	s := int(sec + 0.5)
	return fmt.Sprintf("%d:%02d", s/60, s%60)
}

// findDupes groups the slave files that are the same song. linked holds the
// slave paths that are hardlinks of a master file; probeFn (optional)
// supplies codec details and tags for the files in a group, and only
// (optional) limits the search to those files.
func findDupes(ctx context.Context, files map[string]fsops.Info, linked, only map[string]bool, probeFn func(rel string) *probe.Info) ([]DupeGroup, error) {
	byKey := map[string][]string{}
	titles := map[string]titleInfo{}
	tracks := map[string]int{}
	for rel := range files {
		tracks[albumKey(rel)]++ // album sizes always count every file
		if only != nil && !only[rel] {
			continue
		}
		ti := parseTitle(rel)
		titles[rel] = ti
		if k := dupeKey(rel, ti); k != "" {
			byKey[k] = append(byKey[k], rel)
		}
	}
	keys := make([]string, 0, len(byKey))
	for k, rels := range byKey {
		if len(rels) > 1 {
			keys = append(keys, k)
		}
	}
	sort.Strings(keys)

	var groups []DupeGroup
	for _, k := range keys {
		if ctx.Err() != nil {
			return nil, ctx.Err()
		}
		var copies []DupeFile
		for _, rel := range byKey[k] {
			in := files[rel]
			f := DupeFile{Rel: rel, Size: in.Size, Release: releaseOf(titles[rel]), Linked: linked[rel],
				ino: in.Ino, mtimeNs: in.MtimeNs, tracks: tracks[albumKey(rel)]}
			if probeFn != nil {
				f.Probe = probeFn(rel)
			}
			copies = append(copies, f)
		}
		for _, c := range splitByArtist(copies) {
			if len(c) < 2 {
				continue
			}
			sort.Slice(c, func(i, j int) bool { return keepBetter(c[i], c[j]) })
			c[0].Keep = true
			g := DupeGroup{Files: c}
			name := filepath.Base(c[0].Rel)
			g.Title = strings.TrimSpace(trackNum.ReplaceAllString(strings.TrimSuffix(name, filepath.Ext(name)), ""))
			if g.Title == "" {
				g.Title = name
			}
			if top := firstComponent(c[0].Rel); top != "" {
				g.Title = top + " – " + g.Title
			}
			lo, hi := math.Inf(1), 0.0
			for _, f := range c {
				if f.Probe != nil && f.Probe.Duration > 0 {
					lo, hi = math.Min(lo, f.Probe.Duration), math.Max(hi, f.Probe.Duration)
				}
			}
			if hi-lo > 10 {
				g.Notes = append(g.Notes, fmt.Sprintf("Lengths differ by %s: one may be a radio edit or a different version. Listen before removing.", minSec(hi-lo)))
			}
			same := true
			for _, f := range c[1:] {
				same = same && f.ino == c[0].ino
			}
			if same {
				g.Notes = append(g.Notes, "All copies are the same file (hardlinks), so removing one frees no space, only the extra entry in your media server.")
			}
			groups = append(groups, g)
		}
	}
	for i := range groups {
		groups[i].ID = groups[i].Files[0].Rel
	}
	sort.Slice(groups, func(i, j int) bool { return strings.ToLower(groups[i].Title) < strings.ToLower(groups[j].Title) })
	if groups == nil {
		groups = []DupeGroup{}
	}
	return groups, nil
}

// StartDupeScan looks for songs that are in the slave library more than once.
func (e *Engine) StartDupeScan(pairID int64) (*Job, error) {
	return e.startJob(pairID, "find-duplicates", func(ctx context.Context, j *Job) error {
		l, err := e.loadPair(ctx, pairID)
		if err != nil {
			return err
		}
		j.phase("Listing the slave library", 0)
		files := map[string]fsops.Info{}
		if _, err := walk(ctx, l, l.slave, files); err != nil {
			return err
		}
		linked := map[string]bool{}
		if ms, err := e.st.AllMatches(ctx, pairID); err == nil {
			for rel, m := range ms {
				// Only trust the scan's verdict for the file it saw.
				if in, ok := files[rel]; ok && m.Status == store.StatusLinked && m.SlaveIno == in.Ino {
					linked[rel] = true
				}
			}
		}
		// Probe only files that share a title with another: a first pass
		// without tags finds them.
		cands, err := findDupes(ctx, files, linked, nil, nil)
		if err != nil {
			return err
		}
		var probeFn func(string) *probe.Info
		if e.prober.Bin != "" {
			n := 0
			for _, g := range cands {
				n += len(g.Files)
			}
			j.phase("Reading tags and codec details", int64(n))
			probes := map[string]*probe.Info{}
			for _, g := range cands {
				for _, f := range g.Files {
					if ctx.Err() != nil {
						return ctx.Err()
					}
					p := e.prober.Probe(ctx, filepath.Join(l.slave.Path, f.Rel))
					probes[f.Rel] = &p
					j.tick()
				}
			}
			probeFn = func(rel string) *probe.Info { return probes[rel] }
			only := map[string]bool{}
			for rel := range probes {
				only[rel] = true
			}
			// Again with tags: artists that differ are told apart.
			if cands, err = findDupes(ctx, files, linked, only, probeFn); err != nil {
				return err
			}
		}
		e.dupeMu.Lock()
		if e.dupes == nil {
			e.dupes = map[int64]*DupeScan{}
		}
		e.dupes[pairID] = &DupeScan{CreatedAt: time.Now().Unix(), Files: len(files), Groups: cands, Probed: probeFn != nil}
		e.dupeMu.Unlock()
		extra := 0
		for _, g := range cands {
			extra += len(g.Files) - 1
		}
		j.update(func(j *Job) {
			j.Message = fmt.Sprintf("%d songs are in the slave library more than once (%d extra copies)", len(cands), extra)
		})
		return nil
	})
}

// DupeResult returns the latest duplicate search.
func (e *Engine) DupeResult(pairID int64) *DupeScan {
	e.dupeMu.Lock()
	defer e.dupeMu.Unlock()
	return e.dupes[pairID]
}

// StartRemoveDupes moves the chosen copies of the latest duplicate search into
// the quarantine. Only files that search listed can be chosen, and at least
// one copy of every song must be kept.
func (e *Engine) StartRemoveDupes(pairID int64, rels []string) (*Job, error) {
	e.dupeMu.Lock()
	scan := e.dupes[pairID]
	e.dupeMu.Unlock()
	if scan == nil {
		return nil, fmt.Errorf("%w: look for duplicates first", ErrInvalidBulk)
	}
	type entry struct {
		f     DupeFile
		group int
	}
	listed := map[string]entry{}
	for gi, g := range scan.Groups {
		for _, f := range g.Files {
			listed[f.Rel] = entry{f, gi}
		}
	}
	chosen := map[string]bool{}
	var order []entry
	for _, r := range rels {
		en, ok := listed[r]
		if !ok {
			return nil, fmt.Errorf("%w: %q is not in the latest search", ErrInvalidBulk, r)
		}
		if !chosen[r] {
			chosen[r] = true
			order = append(order, en)
		}
	}
	if len(order) == 0 {
		return nil, fmt.Errorf("%w: no files selected", ErrInvalidBulk)
	}
	keepers := map[int][]string{}
	for gi, g := range scan.Groups {
		for _, f := range g.Files {
			if !chosen[f.Rel] {
				keepers[gi] = append(keepers[gi], f.Rel)
			}
		}
	}
	for _, en := range order {
		if len(keepers[en.group]) == 0 {
			return nil, fmt.Errorf("%w: every copy of %q is selected; keep at least one", ErrInvalidBulk, scan.Groups[en.group].Title)
		}
	}
	return e.startJob(pairID, "remove-duplicates", func(ctx context.Context, j *Job) error {
		l, err := e.loadPair(ctx, pairID)
		if err != nil {
			return err
		}
		j.phase("Moving duplicates to the quarantine", int64(len(order)))
		removed := map[string]bool{}
		for _, en := range order {
			if ctx.Err() != nil {
				return ctx.Err()
			}
			if err := e.removeDupe(ctx, l, en.f, keepers[en.group]); err != nil {
				j.skip(en.f.Rel + ": " + err.Error())
			} else if e.st.DryRun(ctx) {
				j.count("planned")
			} else {
				j.count("removed")
				removed[en.f.Rel] = true
			}
			j.tick()
		}
		e.dropFromDupeScan(pairID, scan, removed)
		return nil
	})
}

// dropFromDupeScan takes removed files out of the search result so the list
// stays current without searching again.
func (e *Engine) dropFromDupeScan(pairID int64, scan *DupeScan, removed map[string]bool) {
	if len(removed) == 0 {
		return
	}
	next := &DupeScan{CreatedAt: scan.CreatedAt, Files: scan.Files - len(removed), Probed: scan.Probed, Groups: []DupeGroup{}}
	for _, g := range scan.Groups {
		var left []DupeFile
		for _, f := range g.Files {
			if !removed[f.Rel] {
				left = append(left, f)
			}
		}
		if len(left) > 1 {
			g.Files = left
			next.Groups = append(next.Groups, g)
		}
	}
	e.dupeMu.Lock()
	if e.dupes[pairID] == scan {
		e.dupes[pairID] = next
	}
	e.dupeMu.Unlock()
}

// removeDupe moves one copy of a song into the quarantine, after checking it
// is still the file that was found and that a copy being kept still exists.
func (e *Engine) removeDupe(ctx context.Context, l *libs, f DupeFile, keepers []string) error {
	e.mu.Lock()
	defer e.mu.Unlock()
	abs, err := l.slave.Resolve(f.Rel)
	if err != nil {
		return err
	}
	si, err := fsops.RegularFile(abs)
	if err != nil {
		return err
	}
	if si.Ino != f.ino || !si.Unchanged(f.Size, f.mtimeNs) {
		return fsops.ErrChanged
	}
	kept := false
	for _, k := range keepers {
		if p, err := l.slave.Resolve(k); err == nil {
			if _, err := fsops.RegularFile(p); err == nil {
				kept = true
				break
			}
		}
	}
	if !kept {
		return errors.New("no other copy of this song is left in the slave library; skipped")
	}
	o := store.Operation{PairID: l.pair.ID, Action: store.ActRemoveDupe, RelSlave: f.Rel, QuarantineSide: SideSlave, Trigger: "manual"}
	// Remember the master pairing so an undo restores it.
	if m, err := e.st.MatchBySlave(ctx, l.pair.ID, f.Rel); err == nil && m.Kind != store.KindNone {
		o.RelMaster, o.MatchKind, o.MatchReason = m.RelMaster, m.Kind, m.Reason
	}
	if err := e.begin(ctx, &o); err != nil {
		return err
	}
	if o.DryRun {
		return nil
	}
	q := quarantinePath(l, o.ID, SideSlave, f.Rel)
	err = func() error {
		// Recorded first, so the file is always findable from History.
		if _, err := e.st.DB.ExecContext(ctx, `UPDATE operations SET quarantine_path = ? WHERE id = ?`, q, o.ID); err != nil {
			return err
		}
		if err := quarantine(abs, si, q); err != nil {
			return err
		}
		if err := removeOriginal(abs, si, q); err != nil {
			if stillQuarantined(abs, q) {
				dropQuarantine(l, q, si)
			}
			return err
		}
		return nil
	}()
	if err = e.finish(ctx, &o, err); err != nil {
		return err
	}
	pruneEmpty(filepath.Dir(abs), l.slave.Path)
	e.refresh(ctx, l, f.Rel)
	return nil
}

// undoRemoveDupe puts a removed duplicate back from the quarantine.
func (e *Engine) undoRemoveDupe(ctx context.Context, l *libs, o store.Operation) error {
	dst, err := l.slave.Resolve(o.RelSlave)
	if err != nil {
		return err
	}
	qi, err := e.quarantined(l, o.QuarantinePath)
	if err != nil {
		return err
	}
	if _, err := os.Lstat(dst); err == nil {
		return fmt.Errorf("%q exists again: %w", o.RelSlave, fsops.ErrExists)
	} else if !errors.Is(err, fs.ErrNotExist) {
		return err
	}
	if err := fsops.MkdirAllLike(filepath.Dir(dst)); err != nil {
		return err
	}
	if err := fsops.LinkNew(o.QuarantinePath, qi, dst); err != nil {
		return err
	}
	dropQuarantine(l, o.QuarantinePath, qi)
	e.refresh(ctx, l, o.RelSlave, store.Match{RelMaster: o.RelMaster, Kind: o.MatchKind, Reason: o.MatchReason})
	return nil
}