/*

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or (at

 * your option) any later version.

 *

 * This program is distributed in the hope that it will be useful, but

 * WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307

 * USA

 */

// This program (Goduf) is a fast duplicate file finder.

// Use goduf --help to get the list of available options.

//

// Installation:

//

// % go get hg.lilotux.net/golang/mikael/goduf

package main

import (

	"crypto/sha1"

	"encoding/hex"

	"errors"

	"flag"

	"fmt"

	"io"

	"os"

	"path/filepath"

	"sort"

)

const medsumBytes = 128

const minSizePartialChecksum = 49152 // Should be > 3*medsumBytes

type sumType int

const (

	noChecksum sumType = iota

	fullChecksum

	partialChecksum

)

type fileObj struct {

	//Unique   bool

	FilePath string

	os.FileInfo

	PartialHash []byte

	Hash        []byte

	needHash    sumType

}

// FileObjList is only exported so that we can have a sort interface on inodes.

type FileObjList []*fileObj

type foListList []FileObjList

type dataT struct {

	totalSize   uint64

	cmpt        uint

	sizeGroups  map[int64]*FileObjList

	emptyFiles  FileObjList

	ignoreCount int

}

var data dataT

// Implement my own logger

var myLog myLogT

// visit is called for every file and directory.

// We check the file object is correct (regular, readable...) and add

// it to the data.sizeGroups hash.

func visit(path string, f os.FileInfo, err error) error {

	if err != nil {

		if f == nil {

			return err

		}

		if f.IsDir() {

			myLog.Println(-1, "Warning: cannot process directory:",

				path)

			return filepath.SkipDir

		}

		myLog.Println(-1, "Ignoring ", path, " - ", err)

		data.ignoreCount++

		return nil

	}

	if f.IsDir() {

		return nil

	}

	if mode := f.Mode(); mode&os.ModeType != 0 {

		if mode&os.ModeSymlink != 0 {

			myLog.Println(6, "Ignoring symbolic link", path)

		} else {

			myLog.Println(0, "Ignoring special file", path)

		}

		data.ignoreCount++

		return nil

	}

	data.cmpt++

	data.totalSize += uint64(f.Size())

	fo := &fileObj{FilePath: path, FileInfo: f}

	if _, ok := data.sizeGroups[f.Size()]; !ok {

		data.sizeGroups[f.Size()] = new(FileObjList)

	}

	*data.sizeGroups[f.Size()] = append(*data.sizeGroups[f.Size()], fo)

	return nil

}

// Checksum computes the file's complete SHA1 hash.

func (fo *fileObj) Checksum() error {

	file, err := os.Open(fo.FilePath)

	if err != nil {

		return err

	}

	defer file.Close()

	hash := sha1.New()

	if size, err := io.Copy(hash, file); size != fo.Size() || err != nil {

		if err == nil {

			return errors.New("failed to read the whole file: " +

				fo.FilePath)

		}

		return err

	}

	fo.Hash = hash.Sum(nil)

	return nil

}

// partialChecksum computes the file's partial SHA1 hash (first and last bytes).

func (fo *fileObj) partialChecksum() error {

	file, err := os.Open(fo.FilePath)

	if err != nil {

		return err

	}

	defer file.Close()

	hash := sha1.New()

	// Read first bytes and last bytes from file

	for i := 0; i < 2; i++ {

		if _, err := io.CopyN(hash, file, medsumBytes); err != nil {

			if err == nil {

				const errmsg = "failed to read bytes from file: "

				return errors.New(errmsg + fo.FilePath)

			}

			return err

		}

		if i == 0 { // Seek to end of file

			file.Seek(0-medsumBytes, 2)

		}

	}

	fo.PartialHash = hash.Sum(nil)

	return nil

}

// Sum computes the file's SHA1 hash, partial or full according to sType.

func (fo *fileObj) Sum(sType sumType) error {

	if sType == partialChecksum {

		return fo.partialChecksum()

	} else if sType == fullChecksum {

		return fo.Checksum()

	} else if sType == noChecksum {

		return nil

	}

	panic("Internal error: Invalid sType")

}

// dispCount display statistics to the user.

func (data *dataT) dispCount() { // It this still useful?

	if myLog.verbosity < 4 {

		return

	}

	var c1, c1b, c2 int

	var s1 string

	for _, scListP := range data.sizeGroups {

		c1 += len(*scListP)

		c2++

	}

	c1b = len(data.emptyFiles)

	if c1b > 0 {

		s1 = fmt.Sprintf("+%d", c1b)

	}

	myLog.Printf(4, "  Current countdown: %d  [%d%s/%d]\n",

		c1+c1b, c1, s1, c2)

}

// checksum returns the requested checksum as a string.

// If the checksum has not been pre-computed, it is calculated now.

func (fo fileObj) checksum(sType sumType) (string, error) {

	var hbytes []byte

	if sType == partialChecksum {

		hbytes = fo.PartialHash

	} else if sType == fullChecksum {

		hbytes = fo.Hash

	} else {

		panic("Internal error: Invalid sType")

	}

	if hbytes == nil {

		if err := fo.Sum(sType); err != nil {

			return "", err

		}

		if sType == partialChecksum {

			hbytes = fo.PartialHash

		} else if sType == fullChecksum {

			hbytes = fo.Hash

		}

	}

	return hex.EncodeToString(hbytes), nil

}

// computeSheduledChecksums calculates the checksums for all the files

// from the fileLists slice items (the kind of hash is taken from the

// needHash field).

func computeSheduledChecksums(fileLists ...foListList) {

	var bigFileList FileObjList

	// Merge the lists of FileObjList lists and create a unique list

	// of file objects.

	for _, foll := range fileLists {

		for _, fol := range foll {

			bigFileList = append(bigFileList, fol...)

		}

	}

	// Sort the list for better efficiency

	sort.Sort(ByInode(bigFileList))

	// Compute checksums

	for _, fo := range bigFileList {

		if err := fo.Sum(fo.needHash); err != nil {

			myLog.Println(0, "Error:", err)

		}

		fo.needHash = noChecksum

	}

}

func (fileList FileObjList) scheduleChecksum(sType sumType) {

	for _, fo := range fileList {

		fo.needHash = sType

	}

}

// findDupesChecksums splits the fileObj list into several lists with the

// same sType hash.

func (fileList FileObjList) findDupesChecksums(sType sumType, dryRun bool) foListList {

	var dupeList foListList

	var scheduleFull foListList

	hashes := make(map[string]FileObjList)

	// Sort the list for better efficiency

	sort.Sort(ByInode(fileList))

	if sType == fullChecksum && dryRun {

		fileList.scheduleChecksum(fullChecksum)

		return append(dupeList, fileList)

	}

	// Compute checksums

	for _, fo := range fileList {

		hash, err := fo.checksum(sType)

		if err != nil {

			myLog.Println(0, "Error:", err)

			continue

		}

		hashes[hash] = append(hashes[hash], fo)

	}

	// Let's de-dupe now...

	for _, l := range hashes {

		if len(l) < 2 {

			continue

		}

		if sType == partialChecksum {

			scheduleFull = append(scheduleFull, l)

		} else { // full checksums -> we're done

			dupeList = append(dupeList, l)

			myLog.Printf(5, "  . found %d new duplicates\n", len(l))

		}

	}

	if sType == partialChecksum && len(scheduleFull) > 0 {

		//computeSheduledChecksums(scheduleFull)

		for _, l := range scheduleFull {

			r := l.findDupesChecksums(fullChecksum, dryRun)

			dupeList = append(dupeList, r...)

		}

		if dryRun {

			return scheduleFull

		}

	}

	return dupeList

}

// findDupes() uses checksums to find file duplicates

func (data *dataT) findDupes(skipPartial bool) foListList {

	var dupeList foListList

	var schedulePartial foListList

	var schedulePartial2 foListList

	var scheduleFull foListList

	for size, sgListP := range data.sizeGroups {

		// We skip partial checksums for small files or if requested

		if size > minSizePartialChecksum && !skipPartial {

			sgListP.scheduleChecksum(partialChecksum)

			schedulePartial = append(schedulePartial, *sgListP)

		} else {

			sgListP.scheduleChecksum(fullChecksum)

			scheduleFull = append(scheduleFull, *sgListP)

		}

	}

	computeSheduledChecksums(schedulePartial, scheduleFull)

	for _, l := range schedulePartial {

		r := l.findDupesChecksums(partialChecksum, true) // dry-run

		schedulePartial2 = append(schedulePartial2, r...)

	}

	computeSheduledChecksums(schedulePartial2)

	for _, l := range schedulePartial {

		r := l.findDupesChecksums(partialChecksum, false)

		dupeList = append(dupeList, r...)

	}

	for _, l := range scheduleFull {

		r := l.findDupesChecksums(fullChecksum, false)

		dupeList = append(dupeList, r...)

	}

	return dupeList

}

// dropEmptyFiles removes the empty files from the main map, since we don't

// have to do any processing about them.

// If ignoreEmpty is false, the empty file list is saved in data.emptyFiles.

func (data *dataT) dropEmptyFiles(ignoreEmpty bool) (emptyCount int) {

	sgListP, ok := data.sizeGroups[0]

	if ok == false {

		return // no empty files

	}

	if !ignoreEmpty {

		if len(*sgListP) > 1 {

			data.emptyFiles = *sgListP

		}

		delete(data.sizeGroups, 0)

		return

	}

	emptyCount = len(*sgListP)

	delete(data.sizeGroups, 0)

	return

}

// initialCleanup() removes files with unique size as well as hard links

func (data *dataT) initialCleanup() (hardLinkCount, uniqueSizeCount int) {

	for s, sgListP := range data.sizeGroups {

		if len(*sgListP) < 2 {

			delete(data.sizeGroups, s)

			uniqueSizeCount++

			continue

		}

		// We can't look for hard links if the O.S. does not support

		// them...

		if !OSHasInodes() {

			continue

		}

		var hardlinksFound bool

		// Check for hard links

		// Remove unique dev/inodes

		// Instead of this loop, another way would be to use the field

		// "Unique" of the fileObj to mark them to be discarded

		// and remove them all at the end.

		// TODO: Should we also check for duplicate paths?

		for {

			type devinode struct{ dev, ino uint64 }

			devinodes := make(map[devinode]bool)

			var hardLinkIndex int

			for i, fo := range *sgListP {

				dev, ino := GetDevIno(fo)

				di := devinode{dev, ino}

				if _, hlink := devinodes[di]; hlink {

					hardLinkIndex = i

					hardLinkCount++

					hardlinksFound = true

					break

				} else {

					devinodes[di] = true

				}

			}