Filesystem.list() returns files in sorted order

sneha1702 · Jan 4, 2021 · aa16a71 · aa16a71
1 parent 6f98625
commit aa16a71
Show file tree

Hide file tree

Showing 10 changed files with 144 additions and 7 deletions.
diff --git a/okio-testing/src/commonMain/kotlin/okio/FakeFilesystem.kt b/okio-testing/src/commonMain/kotlin/okio/FakeFilesystem.kt
@@ -62,12 +62,13 @@ class FakeFilesystem(
   @get:JvmName("allPaths")
   val allPaths: Set<Path>
     get() {
-      val result = mutableSetOf<Path>()
+      val result = mutableListOf<Path>()
       for (path in elements.keys) {
         if (path.isRoot) continue
         result += path
       }
-      return result
+      result.sort()
+      return result.toSet()
     }
 
   /**
@@ -76,6 +77,8 @@ class FakeFilesystem(
    *
    * Note that this may contain paths not present in [allPaths]. This occurs if a file is deleted
    * while it is still open.
+   *
+   * The returned list is ordered by the order that the paths were opened.
    */
   @get:JvmName("openPaths")
   val openPaths: List<Path>
@@ -133,7 +136,9 @@ class FakeFilesystem(
     val element = requireDirectory(canonicalPath)
 
     element.access(now = clock.now())
-    return elements.keys.filter { it.parent == canonicalPath }
+    val paths = elements.keys.filterTo(mutableListOf()) { it.parent == canonicalPath }
+    paths.sort()
+    return paths
   }
 
   override fun source(file: Path): Source {

diff --git a/okio/src/commonMain/kotlin/okio/Filesystem.kt b/okio/src/commonMain/kotlin/okio/Filesystem.kt
@@ -135,7 +135,8 @@ abstract class Filesystem {
   }
 
   /**
-   * Returns the children of the directory identified by [dir].
+   * Returns the children of the directory identified by [dir]. The returned list is sorted using
+   * natural ordering.
    *
    * @throws IOException if [dir] does not exist, is not a directory, or cannot be read. A directory
    *     cannot be read if the current process doesn't have access to [dir], or if there's a loop of

diff --git a/okio/src/commonMain/kotlin/okio/ForwardingFilesystem.kt b/okio/src/commonMain/kotlin/okio/ForwardingFilesystem.kt
@@ -160,7 +160,9 @@ abstract class ForwardingFilesystem(
   override fun list(dir: Path): List<Path> {
     val dir = onPathParameter(dir, "list", "dir")
     val result = delegate.list(dir)
-    return result.map { onPathResult(it, "list") }
+    val paths = result.mapTo(mutableListOf()) { onPathResult(it, "list") }
+    paths.sort()
+    return paths
   }
 
   @Throws(IOException::class)

diff --git a/okio/src/commonMain/kotlin/okio/Path.kt b/okio/src/commonMain/kotlin/okio/Path.kt
@@ -87,6 +87,37 @@ import kotlin.jvm.JvmStatic
  *  * `.` is the name of the identity relative path (full path `.`).
  *  * `..` is the name of a path consisting of only `..` segments (such as `../../..`).
  *
+ * Comparing Paths
+ * ---------------
+ *
+ * Path implements [Comparable], [equals], and [hashCode]. If two paths are equal then they operate
+ * on the same file on the filesystem.
+ *
+ * Note that the converse is not true: **if two paths are non-equal, they may still resolve to the
+ * same file on the filesystem.** Here are some of the ways non-equal paths resolve to the same
+ * file:
+ *
+ *  * **Case differences.** The default file system on macOS is case-insensitive. The paths
+ *    `/Users/jesse/notes.txt` and `/USERS/JESSE/NOTES.TXT` are non-equal but these paths resolve to
+ *    the same file.
+ *  * **Mounting differences.** Volumes may be mounted at multiple paths. On macOS,
+ *    `/Users/jesse/notes.txt`  and `/Volumes/Macintosh HD/Users/jesse/notes.txt` typically resolve
+ *    to the same file. On Windows, `C:\project\notes.txt` and `\\localhost\c$\project\notes.txt`
+ *    typically resolve to the same file.
+ *  * **Hard links.** UNIX filesystems permit multiple paths to refer for same file. The paths may
+ *    be wildly different, like `/Users/jesse/bruce_wayne.vcard` and
+ *    `/Users/jesse/batman.vcard`, but changes via either path are reflected in both.
+ *  * **Symlinks.** Symlinks permit multiple paths and directories to refer to the same file. On
+ *     macOS `/tmp` is symlinked to `/private/tmp`, so `/tmp/notes.txt` and `/private/tmp/notes.txt`
+ *     resolve to the same file.
+ *
+ * To test whether two paths refer to the same file, try [Filesystem.canonicalize] first. This
+ * follows symlinks and looks up the preserved casing for case-insensitive case-preserved paths.
+ * **This method does not guarantee a unique result, however.** For example, each hard link to a
+ * file may return its own canonical path.
+ *
+ * Paths are sorted in case-sensitive order.
+ *
  * Sample Paths
  * ------------
  *
@@ -112,7 +143,7 @@ import kotlin.jvm.JvmStatic
 class Path private constructor(
   private val slash: ByteString,
   private val bytes: ByteString
-) {
+) : Comparable<Path> {
   init {
     require(slash == SLASH || slash == BACKSLASH)
   }
@@ -249,6 +280,12 @@ class Path private constructor(
     return buffer.toPath(directorySeparator = slash)
   }
 
+  override fun compareTo(other: Path): Int {
+    val bytesResult = bytes.compareTo(other.bytes)
+    if (bytesResult != 0) return bytesResult
+    return slash.compareTo(other.slash)
+  }
+
   override fun equals(other: Any?): Boolean {
     return other is Path && other.bytes == bytes && other.slash == slash
   }

diff --git a/okio/src/commonTest/kotlin/okio/AbstractFilesystemTest.kt b/okio/src/commonTest/kotlin/okio/AbstractFilesystemTest.kt
@@ -76,6 +76,24 @@ abstract class AbstractFilesystemTest(
     assertTrue(entries.toString()) { target in entries }
   }
 
+  @Test
+  fun listResultsAreSorted() {
+    val fileA = base / "a"
+    val fileB = base / "b"
+    val fileC = base / "c"
+    val fileD = base / "d"
+
+    // Create files in a different order than the sorted order, so a filesystem that returns files
+    // in creation-order or reverse-creation order won't pass by accident.
+    fileD.writeUtf8("fileD")
+    fileB.writeUtf8("fileB")
+    fileC.writeUtf8("fileC")
+    fileA.writeUtf8("fileA")
+
+    val entries = filesystem.list(base)
+    assertEquals(entries, listOf(fileA, fileB, fileC, fileD))
+  }
+
   @Test
   fun listNoSuchDirectory() {
     assertFailsWith<FileNotFoundException> {

diff --git a/okio/src/commonTest/kotlin/okio/FakeFilesystemTest.kt b/okio/src/commonTest/kotlin/okio/FakeFilesystemTest.kt
@@ -74,13 +74,60 @@ abstract class FakeFilesystemTest internal constructor(
     assertTrue(fakeFilesystem.openPaths.isEmpty())
   }
 
+  @Test
+  fun openPathsIsOpenOrder() {
+    val fileA = base / "a"
+    val fileB = base / "b"
+    val fileC = base / "c"
+    val fileD = base / "d"
+
+    assertEquals(fakeFilesystem.openPaths, listOf())
+    val sinkD = filesystem.sink(fileD)
+    assertEquals(fakeFilesystem.openPaths, listOf(fileD))
+    val sinkB = filesystem.sink(fileB)
+    assertEquals(fakeFilesystem.openPaths, listOf(fileD, fileB))
+    val sinkC = filesystem.sink(fileC)
+    assertEquals(fakeFilesystem.openPaths, listOf(fileD, fileB, fileC))
+    val sinkA = filesystem.sink(fileA)
+    assertEquals(fakeFilesystem.openPaths, listOf(fileD, fileB, fileC, fileA))
+    val sinkB2 = filesystem.sink(fileB)
+    assertEquals(fakeFilesystem.openPaths, listOf(fileD, fileB, fileC, fileA, fileB))
+    sinkD.close()
+    assertEquals(fakeFilesystem.openPaths, listOf(fileB, fileC, fileA, fileB))
+    sinkB2.close()
+    assertEquals(fakeFilesystem.openPaths, listOf(fileB, fileC, fileA))
+    sinkB.close()
+    assertEquals(fakeFilesystem.openPaths, listOf(fileC, fileA))
+    sinkC.close()
+    assertEquals(fakeFilesystem.openPaths, listOf(fileA))
+    sinkA.close()
+    assertEquals(fakeFilesystem.openPaths, listOf())
+  }
+
   @Test
   fun allPathsIncludesFile() {
     val file = base / "all-files-includes-file"
     file.writeUtf8("hello, world!")
     assertEquals(fakeFilesystem.allPaths, setOf(base, file))
   }
 
+  @Test
+  fun allPathsIsSorted() {
+    val fileA = base / "a"
+    val fileB = base / "b"
+    val fileC = base / "c"
+    val fileD = base / "d"
+
+    // Create files in a different order than the sorted order, so a filesystem that returns files
+    // in creation-order or reverse-creation order won't pass by accident.
+    fileD.writeUtf8("fileD")
+    fileB.writeUtf8("fileB")
+    fileC.writeUtf8("fileC")
+    fileA.writeUtf8("fileA")
+
+    assertEquals(fakeFilesystem.allPaths.toList(), listOf(base, fileA, fileB, fileC, fileD))
+  }
+
   @Test
   fun allPathsIncludesDirectory() {
     val dir = base / "all-files-includes-directory"

diff --git a/okio/src/commonTest/kotlin/okio/ForwardingFilesystemTest.kt b/okio/src/commonTest/kotlin/okio/ForwardingFilesystemTest.kt
@@ -92,6 +92,29 @@ class ForwardingFilesystemTest : AbstractFilesystemTest(
     assertEquals("hello, world!", target.readUtf8())
   }
 
+  /**
+   * Path mapping might impact the sort order. Confirm that list() returns elements in sorted order
+   * even if that order is different in the delegate file system.
+   */
+  @Test
+  fun pathMappingImpactedBySorting() {
+    val az = base / "az"
+    val by = base / "by"
+    val cx = base / "cx"
+    az.writeUtf8("az")
+    by.writeUtf8("by")
+    cx.writeUtf8("cx")
+
+    val forwardingFilesystem = object : ForwardingFilesystem(filesystem) {
+      override fun onPathResult(path: Path, functionName: String): Path {
+        return path.parent!! / path.name.reversed()
+      }
+    }
+
+    assertEquals(filesystem.list(base), listOf(base / "az", base / "by", base / "cx"))
+    assertEquals(forwardingFilesystem.list(base), listOf(base / "xc", base / "yb", base / "za"))
+  }
+
   @Test
   fun copyIsNotForwarded() {
     val log = mutableListOf<String>()

diff --git a/okio/src/jsMain/kotlin/okio/NodeJsSystemFilesystem.kt b/okio/src/jsMain/kotlin/okio/NodeJsSystemFilesystem.kt
@@ -76,6 +76,7 @@ internal object NodeJsSystemFilesystem : Filesystem() {
           val dirent = opendir.readSync() ?: break
           result += dir / dirent.name
         }
+        result.sort()
         return result
       } finally {
         opendir.closeSync()

diff --git a/okio/src/jvmMain/kotlin/okio/JvmSystemFilesystem.kt b/okio/src/jvmMain/kotlin/okio/JvmSystemFilesystem.kt
@@ -62,7 +62,9 @@ internal open class JvmSystemFilesystem : Filesystem() {
       if (!file.exists()) throw FileNotFoundException("no such file $dir")
       throw IOException("failed to list $dir")
     }
-    return entries.map { dir / it }
+    val result = entries.mapTo(mutableListOf()) { dir / it }
+    result.sort()
+    return result
   }
 
   override fun source(file: Path): Source {

diff --git a/okio/src/nativeMain/kotlin/okio/PosixSystemFilesystem.kt b/okio/src/nativeMain/kotlin/okio/PosixSystemFilesystem.kt
@@ -63,6 +63,7 @@ internal object PosixSystemFilesystem : Filesystem() {
 
       if (errno != 0) throw errnoToIOException(errno)
 
+      result.sort()
       return result
     } finally {
       closedir(opendir) // Ignore errno from closedir.