#include "FilePoolCore.hh"
#include "File.hh"
#include "FileException.hh"
#include "ReadDir.hh"
#include "Date.hh"
#include "Timer.hh"
#include "one_of.hh"
#include "ranges.hh"
#include <fstream>
#include <optional>
#include <tuple>

using std::string;

namespace openmsx {

class CompareSha1 {
public:
	CompareSha1(const FilePoolCore::Pool& pool_) : pool(pool_) {}
	template<typename X, typename Y> bool operator()(const X& x, const Y& y) const {
		return get(x) < get(y);
	}
private:
	const Sha1Sum& get(const Sha1Sum& sum) const { return sum; }
	const Sha1Sum& get(FilePoolCore::Index idx) const { return pool[idx].sum; }
private:
	const FilePoolCore::Pool& pool;
};


FilePoolCore::FilePoolCore(string filecache_,
                           std::function<Directories()> getDirectories_,
                           std::function<void(const string&)> reportProgress_)
	: filecache(std::move(filecache_))
	, getDirectories(getDirectories_)
	, reportProgress(reportProgress_)
{
	try {
		readSha1sums();
	} catch (MSXException&) {
		// ignore, probably .filecache doesn't exist yet
	}
}

FilePoolCore::~FilePoolCore()
{
	if (needWrite) {
		writeSha1sums();
	}
}

void FilePoolCore::insert(const Sha1Sum& sum, time_t time, const string& filename)
{
	stringBuffer.push_back(filename);
	auto idx = pool.emplace(sum, time, stringBuffer.back()).idx;
	auto it = ranges::upper_bound(sha1Index, sum, CompareSha1(pool));
	sha1Index.insert(it, idx);
	filenameIndex.insert(idx);
	needWrite = true;
}

FilePoolCore::Sha1Index::iterator FilePoolCore::getSha1Iterator(Index idx, Entry& entry)
{
	// There can be multiple entries for the same sha1, look for the specific one.
	auto [b, e] = ranges::equal_range(sha1Index, entry.sum, CompareSha1(pool));
	while (b != e) {
		if (*b == idx) {
			return b;
		}
	}
	assert(false); return sha1Index.end();
}

void FilePoolCore::remove(Sha1Index::iterator it)
{
	auto idx = *it;
	filenameIndex.erase(idx);
	pool.remove(idx);
	sha1Index.erase(it);
	needWrite = true;
}

void FilePoolCore::remove(Index idx, Entry& entry)
{
	remove(getSha1Iterator(idx, entry));
}

void FilePoolCore::remove(Index idx)
{
	remove(idx, pool[idx]);
}

// Change the sha1sum of the element pointed to by 'it' into 'newSum'. Also
// re-arrange the items so that 'sha1Index' remains sorted on sha1sum.
// Internally this method doesn't actually sort, it merely rotates the
// elements.
// Returns false if the new position is before (or at) the old position.
// Returns true  if the new position is after          the old position.
bool FilePoolCore::adjustSha1(Sha1Index::iterator it, Entry& entry, const Sha1Sum& newSum)
{
	needWrite = true;
	auto newIt = ranges::upper_bound(sha1Index, newSum, CompareSha1(pool));
	entry.sum = newSum; // update sum
	if (newIt > it) {
		// move to back
		rotate(it, it + 1, newIt);
		return true;
	} else {
		if (newIt < it) {
			// move to front
			rotate(newIt, it, it + 1);
		} else {
			// (unlikely) sha1sum has changed, but after
			// resorting item would remain in the same
			// position
		}
		return false;
	}
}

bool FilePoolCore::adjustSha1(Index idx, Entry& entry, const Sha1Sum& newSum)
{
	return adjustSha1(getSha1Iterator(idx, entry), entry, newSum);
}

time_t FilePoolCore::Entry::getTime()
{
	if (time == time_t(-1)) {
		time = Date::fromString(timeStr);
	}
	return time;
}

void FilePoolCore::Entry::setTime(time_t t)
{
	time = t;
	timeStr = nullptr;
}

// returns: <sha1, time-string, filename>
static std::optional<std::tuple<Sha1Sum, const char*, std::string_view>> parse(
	char* line, char* line_end)
{
	if ((line_end - line) <= 68) return {}; // minumum length (only filename is variable)

	// only perform quick sanity check on date/time format
	if (line[40] != ' ') return {}; // two space between sha1sum and date
	if (line[41] != ' ') return {};
	if (line[45] != ' ') return {}; // space between day-of-week and month
	if (line[49] != ' ') return {}; // space between month and day of month
	if (line[52] != ' ') return {}; // space between day of month and hour
	if (line[55] != ':') return {}; // colon between hour and minutes
	if (line[58] != ':') return {}; // colon between minutes and seconds
	if (line[61] != ' ') return {}; // space between seconds and year
	if (line[66] != ' ') return {}; // two spaces between date and filename
	if (line[67] != ' ') return {};

	Sha1Sum sha1(Sha1Sum::UninitializedTag{});
	try {
		sha1.parse40(line);
	} catch (MSXException&) {
		return {};
	}

	const char* timeStr = line + 42; // not guaranteed to be a correct date/time
	line[66] = '\0'; // zero-terminate timeStr, so that it can be printed

	std::string_view filename(line + 68, line_end - (line + 68)); // TODO c++20 [begin, end)

	return std::tuple{sha1, timeStr, filename};
}

void FilePoolCore::readSha1sums()
{
	assert(sha1Index.empty());
	assert(fileMem.empty());

	File file(filecache);
	auto size = file.getSize();
	fileMem.resize(size + 1);
	file.read(fileMem.data(), size);
	fileMem[size] = '\n'; // ensure there's always a '\n' at the end

	// Process each line.
	// Assume lines are separated by "\n", "\r\n" or "\n\r" (but not "\r").
	char* data = fileMem.data();
	char* data_end = data + size + 1;
	while (data != data_end) {
		// memchr() seems better optimized than std::find_if()
		char* it = static_cast<char*>(memchr(data, '\n', data_end - data));
		if (it == nullptr) it = data_end;
		if ((it != data) && (it[-1] == '\r')) --it;

		if (auto r = parse(data, it)) {
			auto [sum, timeStr, filename] = *r;
			sha1Index.push_back(pool.emplace(sum, timeStr, filename).idx);
			// sha1Index not yet guaranteed sorted
		}

		data = std::find_if(it + 1, data_end, [](char c) {
			return c != one_of('\n', '\r');
		});
	}

	if (!ranges::is_sorted(sha1Index, CompareSha1(pool))) {
		// This should _rarely_ happen. In fact it should only happen
		// when .filecache was manually edited. Though because it's
		// very important that pool is indeed sorted I've added this
		// safety mechanism.
		ranges::sort(sha1Index, CompareSha1(pool));
	}

	// 'pool' is populated, 'sha1Index' is sorted, now build 'filenameIndex'
	auto n = sha1Index.size();
	filenameIndex.reserve(n);
	while (n != 0) { // sha1Index might change while iterating ...
		--n;
		Index idx = sha1Index[n]; // ... therefor use indices instead of iterators
		bool inserted = filenameIndex.insert(idx);
		if (!inserted) {
			// ERROR: there may not be multiple entries for the same filename
			// Should only happen when .filecache was manually edited.
			remove(idx);
		}
	}
}

void FilePoolCore::writeSha1sums()
{
	std::ofstream file;
	FileOperations::openofstream(file, filecache);
	if (!file.is_open()) {
		return;
	}
	for (auto idx : sha1Index) {
		const auto& entry = pool[idx];
		file << entry.sum.toString() << "  ";
		if (entry.timeStr) {
			file << entry.timeStr;
		} else {
			assert(entry.time != time_t(-1));
			file << Date::toString(entry.time);
		}
		file << "  " << entry.filename << '\n';
	}
}

File FilePoolCore::getFile(FileType fileType, const Sha1Sum& sha1sum)
{
	File result = getFromPool(sha1sum);
	if (result.is_open()) return result;

	// not found in cache, need to scan directories
	stop = false;
	ScanProgress progress;
	progress.lastTime = Timer::getTime();
	progress.amountScanned = 0;

	for (auto& [path, types] : getDirectories()) {
		if ((types & fileType) != FileType::NONE) {
			result = scanDirectory(sha1sum, FileOperations::expandTilde(path), path, progress);
			if (result.is_open()) return result;
		}
	}

	return result; // not found
}

Sha1Sum FilePoolCore::calcSha1sum(File& file)
{
	// Calculate sha1 in several steps so that we can show progress
	// information. We take a fixed step size for an efficient calculation.
	constexpr size_t STEP_SIZE = 1024 * 1024; // 1MB

	auto data = file.mmap();

	SHA1 sha1;
	size_t size = data.size();
	size_t done = 0;
	size_t remaining = size;
	auto lastShowedProgress = Timer::getTime();
	bool everShowedProgress = false;

	auto report = [&](size_t percentage) {
		reportProgress(strCat("Calculating SHA1 sum for ", file.getOriginalName(),
		                      "... ", percentage, '%'));
	};
	// Loop over all-but-the last blocks. For small files this loop is skipped.
	while (remaining > STEP_SIZE) {
		sha1.update(&data[done], STEP_SIZE);
		done += STEP_SIZE;
		remaining -= STEP_SIZE;

		auto now = Timer::getTime();
		if ((now - lastShowedProgress) > 250'000) { // 4Hz
			report((100 * done) / size);
			lastShowedProgress = now;
			everShowedProgress = true;
		}
	}
	// last block
	if (remaining) {
		sha1.update(&data[done], remaining);
	}
	if (everShowedProgress) {
		report(100);
	}
	return sha1.digest();
}

File FilePoolCore::getFromPool(const Sha1Sum& sha1sum)
{
	auto [b, e] = ranges::equal_range(sha1Index, sha1sum, CompareSha1(pool));
	// use indices instead of iterators
	auto i    = distance(begin(sha1Index), b);
	auto last = distance(begin(sha1Index), e);
	while (i != last) {
		auto it = begin(sha1Index) + i;
		auto& entry = pool[*it];
		if (entry.getTime() == time_t(-1)) {
			// Invalid time/date format. Remove from
			// database and continue searching.
			remove(it);
			--last;
			continue;
		}
		try {
			File file(entry.filename);
			auto newTime = file.getModificationDate();
			if (entry.getTime() == newTime) {
				// When modification time is unchanged, assume
				// sha1sum is also unchanged. So avoid
				// expensive sha1sum calculation.
				return file;
			}
			entry.setTime(newTime); // update timestamp
			needWrite = true;
			auto newSum = calcSha1sum(file);
			if (newSum == sha1sum) {
				// Modification time was changed, but
				// (recalculated) sha1sum is still the same.
				return file;
			}
			// Sha1sum has changed: update sha1sum, move entry to
			// new position new sum and continue searching.
			if (adjustSha1(it, entry, newSum)) {
				// after
				--last; // no ++i
			} else {
				// before (or at)
				++i;
			}
		} catch (FileException&) {
			// Error reading file: remove from db and continue
			// searching.
			remove(it);
			--last;
		}
	}
	return File(); // not found
}

File FilePoolCore::scanDirectory(
	const Sha1Sum& sha1sum, const string& directory, const string& poolPath,
	ScanProgress& progress)
{
	ReadDir dir(directory);
	while (dirent* d = dir.getEntry()) {
		if (stop) {
			// Scanning can take a long time. Allow to abort
			// the search when it takes too long. Stop scanning
			// by pretending that we didn't find the file.
			return File();
		}
		string file = d->d_name;
		string path = strCat(directory, '/', file);
		FileOperations::Stat st;
		if (FileOperations::getStat(path, st)) {
			File result;
			if (FileOperations::isRegularFile(st)) {
				result = scanFile(sha1sum, path, st, poolPath, progress);
			} else if (FileOperations::isDirectory(st)) {
				if (file != one_of(".", "..")) {
					result = scanDirectory(sha1sum, path, poolPath, progress);
				}
			}
			if (result.is_open()) return result;
		}
	}
	return File(); // not found
}

File FilePoolCore::scanFile(const Sha1Sum& sha1sum, const string& filename,
                            const FileOperations::Stat& st, const string& poolPath,
                            ScanProgress& progress)
{
	++progress.amountScanned;
	// Periodically send a progress message with the current filename
	auto now = Timer::getTime();
	if (now > (progress.lastTime + 250'000)) { // 4Hz
		progress.lastTime = now;
		reportProgress(strCat(
		        "Searching for file with sha1sum ", sha1sum.toString(),
		        "...\nIndexing filepool ", poolPath, ": [",
		        progress.amountScanned, "]: ",
		        std::string_view(filename).substr(poolPath.size())));
	}

	auto time = FileOperations::getModificationDate(st);
	auto [idx, entry] = findInDatabase(filename);
	if (idx == Index(-1)) {
		// not in pool
		try {
			File file(filename);
			auto sum = calcSha1sum(file);
			insert(sum, time, filename);
			if (sum == sha1sum) {
				return file;
			}
		} catch (FileException&) {
			// ignore
		}
	} else {
		// already in pool
		assert(filename == entry->filename);
		try {
			if (entry->getTime() == time) {
				// db is still up to date
				if (entry->sum == sha1sum) {
					return File(filename);
				}
			} else {
				// db outdated
				File file(filename);
				auto sum = calcSha1sum(file);
				entry->setTime(time);
				adjustSha1(idx, *entry, sum);
				if (sum == sha1sum) {
					return file;
				}
			}
		} catch (FileException&) {
			// error reading file, remove from db
			remove(idx, *entry);
		}
	}
	return File(); // not found
}

std::pair<FilePoolCore::Index, FilePoolCore::Entry*> FilePoolCore::findInDatabase(std::string_view filename)
{
	auto it = filenameIndex.find(filename);
	if (!it) return {Index(-1), nullptr};

	Index idx = *it;
	auto& entry = pool[idx];
	assert(entry.filename == filename);
	if (entry.getTime() == time_t(-1)) {
		// invalid date/time string, remove from db
		remove(idx, entry);
		return {Index(-1), nullptr};
	}
	return {idx, &entry};
}

Sha1Sum FilePoolCore::getSha1Sum(File& file)
{
	auto time = file.getModificationDate();
	const auto& filename = file.getURL();

	auto [idx, entry] = findInDatabase(filename);
	if (idx != Index(-1)) {
		if (entry->getTime() == time) {
			// in database and modification time matches,
			// assume sha1sum also matches
			return entry->sum;
		}
	}

	// not in database or timestamp mismatch
	auto sum = calcSha1sum(file);
	if (idx == Index(-1)) {
		// was not yet in database, insert new entry
		insert(sum, time, filename);
	} else {
		// was already in database, but with wrong timestamp (and sha1sum)
		entry->setTime(time);
		adjustSha1(idx, *entry, sum);
	}
	return sum;
}

} // namespace openmsx
