Add verifier

Used to check if target files have the expected hash. Using a
memory cache to not have to read source each time but falls back
to reading source if needed.

5 files changed, 282 insertions, 7 deletions

diff --git a/libs/io/src/main/java/org/the_jk/cleversync/io/Hasher.kt b/libs/io/src/main/java/org/the_jk/cleversync/io/Hasher.kt
new file mode 100644
index 0000000..5d48a98
--- /dev/null
+++ b/libs/io/src/main/java/org/the_jk/cleversync/io/Hasher.kt
@@ -0,0 +1,113 @@
+package org.the_jk.cleversync.io
+
+import java.io.FilterOutputStream
+import java.io.IOException
+import java.io.InputStream
+import java.io.OutputStream
+import java.lang.ref.WeakReference
+import java.security.MessageDigest
+
+object Hasher {
+    val DEFAULT = Format.SHA256
+
+    fun hash(input: InputStream, format: Format = DEFAULT): String? {
+        val cache = digestCache.get()!!
+        val md = cache.acquire(format)
+        try {
+            val buffer = ByteArray(BUFFER_SIZE)
+            while (true) {
+                val got = input.read(buffer)
+                if (got == -1) break
+                md.update(buffer, 0, got)
+            }
+            return formatHash(md.digest())
+        } catch (_: IOException) {
+            return null
+        } finally {
+            cache.release(format, md)
+        }
+    }
+
+    fun wrap(outputStream: OutputStream, format: Format = DEFAULT): HashOutputStream {
+        return HashOutputStream(outputStream, format)
+    }
+
+    @Suppress("MagicNumber")
+    fun getFormat(hash: String): Format {
+        return when (hash.length) {
+            40 -> Format.SHA160
+            56 -> Format.SHA224
+            64 -> Format.SHA256
+            96 -> Format.SHA384
+            128 -> Format.SHA512
+            else -> throw IllegalArgumentException("Unknown hash length: ${hash.length}")
+        }
+    }
+
+    enum class Format(val algorithm: String) {
+        SHA160("SHA-1"),    // Supported API 1+
+        SHA224("SHA-224"),  // Supported API 22+
+        SHA256("SHA-256"),  // Supported API 1+
+        SHA384("SHA-384"),  // Supported API 1+
+        SHA512("SHA-512"),  // Supported API 1+
+    }
+
+    class HashOutputStream(wrapped: OutputStream, private val format: Format) : FilterOutputStream(wrapped) {
+        private val cache = digestCache.get()!!
+        private var digest: MessageDigest? = cache.acquire(format)
+        private var hash: ByteArray? = null
+
+        override fun write(b: Int) {
+            super.write(b)
+
+            digest!!.update(b.toByte())
+        }
+
+        override fun write(b: ByteArray?, off: Int, len: Int) {
+            out.write(b, off, len)
+            if (len > 0) {
+                digest!!.update(b!!, off, len)
+            }
+        }
+
+        override fun close() {
+            super.close()
+
+            if (digest == null) return
+            hash = digest!!.digest()
+            cache.release(format, digest!!)
+            digest = null
+        }
+
+        fun hash(): String {
+            return formatHash(hash ?: digest!!.digest())
+        }
+    }
+
+    private const val BUFFER_SIZE = 65536
+
+    private val digestCache = ThreadLocal.withInitial { DigestCache() }
+
+    @OptIn(ExperimentalStdlibApi::class)
+    private fun formatHash(data: ByteArray): String {
+        return data.toHexString()
+    }
+
+    private class DigestCache {
+        private val cache = mutableMapOf<Format, WeakReference<MessageDigest>>()
+
+        fun acquire(format: Format): MessageDigest {
+            val ref = cache.remove(format)
+            if (ref != null) {
+                val md = ref.get()
+                if (md != null) return md
+            }
+            return MessageDigest.getInstance(format.algorithm)
+        }
+
+        fun release(format: Format, digest: MessageDigest) {
+            digest.reset()
+            cache[format] = WeakReference(digest)
+        }
+    }
+}
diff --git a/libs/io/src/main/java/org/the_jk/cleversync/io/Modifier.kt b/libs/io/src/main/java/org/the_jk/cleversync/io/Modifier.kt
index 84881cd..f9235e4 100644
--- a/libs/io/src/main/java/org/the_jk/cleversync/io/Modifier.kt
+++ b/libs/io/src/main/java/org/the_jk/cleversync/io/Modifier.kt
@@ -4,9 +4,14 @@ import org.the_jk.cleversync.PathUtils
 import java.io.IOException
 
 object Modifier {
-    fun apply(target: ModifiableDirectory, source: Directory, actions: List<Action>): List<String> {
+    fun apply(
+        target: ModifiableDirectory,
+        source: Directory,
+        actions: List<Action>,
+        memory: Verifier.Memory? = null,
+    ): List<String> {
         val errors = mutableListOf<String>()
-        apply(target, source, actions, "", errors)
+        apply(target, source, actions, memory, "", errors)
         return errors
     }
 
@@ -14,6 +19,7 @@ object Modifier {
         target: ModifiableDirectory,
         source: Directory,
         actions: List<Action>,
+        memory: Verifier.Memory? = null,
         path: String,
         errors: MutableList<String>,
     ) {
@@ -47,6 +53,7 @@ object Modifier {
                                 targetDir,
                                 sourceDir,
                                 action.actions,
+                                memory,
                                 newPath,
                                 errors
                             )
@@ -70,12 +77,24 @@ object Modifier {
                         }?.let { targetFile ->
                             try {
                                 val buffer = ByteArray(BUFFER_SIZE)
-                                targetFile.write().use { output ->
-                                    sourceFile.read().use { input ->
-                                        val got = input.read(buffer)
-                                        output.write(buffer, 0, got)
+                                if (memory != null) {
+                                    val stream = Hasher.wrap(targetFile.write())
+                                    stream.use { output ->
+                                        sourceFile.read().use { input ->
+                                            val got = input.read(buffer)
+                                            output.write(buffer, 0, got)
+                                        }
+                                        output.flush()
+                                    }
+                                    memory.put("$path/${action.name}", stream.hash())
+                                } else {
+                                    targetFile.write().use { output ->
+                                        sourceFile.read().use { input ->
+                                            val got = input.read(buffer)
+                                            output.write(buffer, 0, got)
+                                        }
+                                        output.flush()
                                     }
-                                    output.flush()
                                 }
                             } catch (e: IOException) {
                                 errors.add("$path/${action.name}: Error writing file: ${e.message}")
diff --git a/libs/io/src/main/java/org/the_jk/cleversync/io/Verifier.kt b/libs/io/src/main/java/org/the_jk/cleversync/io/Verifier.kt
new file mode 100644
index 0000000..d1d85b9
--- /dev/null
+++ b/libs/io/src/main/java/org/the_jk/cleversync/io/Verifier.kt
@@ -0,0 +1,82 @@
+package org.the_jk.cleversync.io
+
+object Verifier {
+    fun calculate(target: Directory, source: Directory, memory: Memory): List<Action> {
+        return visit(target, source, Context(memory), "")
+    }
+
+    interface Memory {
+        fun get(path: String): String?
+        fun put(path: String, hash: String)
+    }
+
+    private fun visit(target: Directory, source: Directory, context: Context, path: String): List<Action> {
+        val targetContent = target.list()
+        return buildList {
+            for (targetDir in targetContent.directories) {
+                val sourceDir = source.openDir(targetDir.name)
+                if (sourceDir != null) {
+                    val actions = visit(targetDir, sourceDir, context, "$path/${targetDir.name}")
+                    if (actions.isNotEmpty()) {
+                        add(
+                            Action.ChangeDir(
+                                name = targetDir.name,
+                                actions = actions,
+                                create = false,
+                            ),
+                        )
+                    }
+                }
+            }
+            for (targetFile in targetContent.files) {
+                val sourceFile = source.openFile(targetFile.name)
+                if (sourceFile != null) {
+                    val storedHash = context.memory.get("$path/${targetFile.name}")
+                    if (storedHash == null) {
+                        // Can happen if hash setting has changed since the
+                        // merge that copied the file.
+                        val targetHash = hash(targetFile, Hasher.DEFAULT)
+                        val sourceHash = hash(sourceFile, Hasher.DEFAULT)
+                        if (sourceHash != null) {
+                            context.memory.put("$path/${targetFile.name}", sourceHash)
+                            if (sourceHash != targetHash) {
+                                add(
+                                    Action.Copy(
+                                        name = targetFile.name,
+                                        overwrite = true,
+                                    )
+                                )
+                            }
+                        } else {
+                            // No hash stored and unable to read source file,
+                            // really nothing we can do.
+                        }
+                    } else {
+                        val targetHash = hash(targetFile, Hasher.getFormat(storedHash))
+                        if (storedHash != targetHash) {
+                            add(
+                                Action.Copy(
+                                    name = targetFile.name,
+                                    overwrite = true,
+                                )
+                            )
+                        } else {
+                            // Hashes match, all is good.
+                        }
+                    }
+                }
+            }
+            // Ignoring links as they can only link to other files inside
+            // the same root or, if they point outside, we can't find a "source"
+            // so let them be.
+        }
+    }
+
+    private fun hash(file: File, format: Hasher.Format): String? {
+        return file.read().use { Hasher.hash(it, format) }
+    }
+
+    private data class Context(
+        val memory: Memory,
+    )
+}
diff --git a/libs/io/src/test/java/org/the_jk/cleversync/io/HasherTest.kt b/libs/io/src/test/java/org/the_jk/cleversync/io/HasherTest.kt
new file mode 100644
index 0000000..02fd79a
--- /dev/null
+++ b/libs/io/src/test/java/org/the_jk/cleversync/io/HasherTest.kt
@@ -0,0 +1,42 @@
+package org.the_jk.cleversync.io
+
+import com.google.common.truth.Truth.assertThat
+import org.junit.Test
+import java.io.ByteArrayOutputStream
+import java.nio.charset.Charset
+
+@Suppress("MaxLineLength")
+class HasherTest {
+    @Test
+    fun empty() {
+        check("", "da39a3ee5e6b4b0d3255bfef95601890afd80709")
+        check("", "d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f")
+        check("", "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855")
+        check("", "38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95b")
+        check("", "cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e")
+    }
+
+    @Test
+    fun known() {
+        check("The quick brown fox jumps over the lazy dog", "2fd4e1c67a2d28fced849ee1bb76e7391b93eb12")
+        check("The quick brown fox jumps over the lazy cog", "de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3")
+        check("The quick brown fox jumps over the lazy dog", "730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525")
+        check("The quick brown fox jumps over the lazy dog.", "619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c")
+    }
+
+    private companion object {
+        fun check(input: String, hash: String) {
+            val format = Hasher.getFormat(hash)
+            input.toByteArray().inputStream().use {
+                assertThat(Hasher.hash(it, format)).isEqualTo(hash)
+            }
+            val byteStream = ByteArrayOutputStream()
+            val hashStream = Hasher.wrap(byteStream, format)
+            hashStream.use {
+                it.write(input.toByteArray())
+            }
+            assertThat(hashStream.hash()).isEqualTo(hash)
+            assertThat(byteStream.toByteArray().toString(Charset.defaultCharset())).isEqualTo(input)
+        }
+    }
+}
diff --git a/libs/io/src/test/java/org/the_jk/cleversync/io/VerifierLocalTest.kt b/libs/io/src/test/java/org/the_jk/cleversync/io/VerifierLocalTest.kt
new file mode 100644
index 0000000..3576d15
--- /dev/null
+++ b/libs/io/src/test/java/org/the_jk/cleversync/io/VerifierLocalTest.kt
@@ -0,0 +1,19 @@
+package org.the_jk.cleversync.io
+
+import org.junit.Rule
+import org.junit.rules.TemporaryFolder
+import org.the_jk.cleversync.local.LocalTreeFactory
+
+class VerifierLocalTest : BaseVerifierTest() {
+    @Rule
+    @JvmField
+    val temp = TemporaryFolder()
+
+    override fun source(): ModifiableTree {
+        return LocalTreeFactory.modifiableTree(temp.newFolder("source").toPath())
+    }
+
+    override fun target(): ModifiableTree {
+        return LocalTreeFactory.modifiableTree(temp.newFolder("target").toPath())
+    }
+}