Filesystem: Replace GetFileList()

Instead of expecting callers to know how the size of directory file infos
relates to which files are in which directories, filesystems now offer a
GetRoot() method, and file infos offer a way to get their children. As
a bonus, m_FileInfoVector no longer has to be created and kept around
in RAM. Only the file info objects that actually are used are created.

11 files changed, 366 insertions, 260 deletions

diff --git a/Source/Core/Core/HW/DVD/FileMonitor.cpp b/Source/Core/Core/HW/DVD/FileMonitor.cpp
index 980bc5454f..cc50d0ef61 100644
--- a/Source/Core/Core/HW/DVD/FileMonitor.cpp
+++ b/Source/Core/Core/HW/DVD/FileMonitor.cpp
@@ -88,13 +88,13 @@ void Log(u64 offset, const DiscIO::Partition& partition)
   if (!s_filesystem)
     return;
 
-  const DiscIO::FileInfo* file_info = s_filesystem->FindFileInfo(offset);
+  const std::unique_ptr<DiscIO::FileInfo> file_info = s_filesystem->FindFileInfo(offset);
 
   // Do nothing if no file was found at that offset
   if (!file_info)
     return;
 
-  const std::string path = s_filesystem->GetPath(file_info->GetOffset());
+  const std::string path = file_info->GetPath();
 
   // Do nothing if we found the same file again
   if (s_previous_file == path)
diff --git a/Source/Core/DiscIO/DiscScrubber.cpp b/Source/Core/DiscIO/DiscScrubber.cpp
index 71d1fa16bc..009081cbb6 100644
--- a/Source/Core/DiscIO/DiscScrubber.cpp
+++ b/Source/Core/DiscIO/DiscScrubber.cpp
@@ -16,8 +16,6 @@
 #include "Common/Logging/Log.h"
 #include "DiscIO/DiscScrubber.h"
 #include "DiscIO/Filesystem.h"
-// TODO: eww
-#include "DiscIO/FileSystemGCWii.h"
 #include "DiscIO/Volume.h"
 
 namespace DiscIO
@@ -221,17 +219,21 @@ bool DiscScrubber::ParsePartitionData(const Partition& partition, PartitionHeade
   MarkAsUsedE(partition_data_offset, header->fst_offset, header->fst_size);
 
   // Go through the filesystem and mark entries as used
-  auto& file_list = filesystem->GetFileList();
-  for (size_t i = 0; i < file_list.size(); ++i)
-  {
-    const std::string path = filesystem->GetPathFromFSTOffset(i);
-    DEBUG_LOG(DISCIO, "%s", path.empty() ? "/" : path.c_str());
-    auto& file = file_list[i];
-    if (!file.IsDirectory())
-      MarkAsUsedE(partition_data_offset, file.GetOffset(), file.GetSize());
-  }
+  ParseFileSystemData(partition_data_offset, filesystem->GetRoot());
 
   return true;
 }
 
+void DiscScrubber::ParseFileSystemData(u64 partition_data_offset, const FileInfo& directory)
+{
+  for (const DiscIO::FileInfo& file_info : directory)
+  {
+    DEBUG_LOG(DISCIO, "Scrubbing %s", file_info.GetPath().c_str());
+    if (file_info.IsDirectory())
+      ParseFileSystemData(partition_data_offset, file_info);
+    else
+      MarkAsUsedE(partition_data_offset, file_info.GetOffset(), file_info.GetSize());
+  }
+}
+
 }  // namespace DiscIO
diff --git a/Source/Core/DiscIO/DiscScrubber.h b/Source/Core/DiscIO/DiscScrubber.h
index 0eda66da48..d61b8422da 100644
--- a/Source/Core/DiscIO/DiscScrubber.h
+++ b/Source/Core/DiscIO/DiscScrubber.h
@@ -25,6 +25,7 @@ class IOFile;
 
 namespace DiscIO
 {
+class FileInfo;
 class Volume;
 struct Partition;
 
@@ -64,6 +65,7 @@ private:
   bool ReadFromVolume(u64 offset, u64& buffer, const Partition& partition);
   bool ParseDisc();
   bool ParsePartitionData(const Partition& partition, PartitionHeader* header);
+  void ParseFileSystemData(u64 partition_data_offset, const FileInfo& directory);
 
   std::string m_filename;
   std::unique_ptr<Volume> m_disc;
diff --git a/Source/Core/DiscIO/FileSystemGCWii.cpp b/Source/Core/DiscIO/FileSystemGCWii.cpp
index 9280dbab16..54b7f6a0e2 100644
--- a/Source/Core/DiscIO/FileSystemGCWii.cpp
+++ b/Source/Core/DiscIO/FileSystemGCWii.cpp
@@ -6,6 +6,7 @@
 #include <cinttypes>
 #include <cstddef>
 #include <cstring>
+#include <memory>
 #include <optional>
 #include <string>
 #include <vector>
@@ -24,15 +25,60 @@ namespace DiscIO
 {
 constexpr u32 FST_ENTRY_SIZE = 4 * 3;  // An FST entry consists of three 32-bit integers
 
+// Set everything manually.
 FileInfoGCWii::FileInfoGCWii(const u8* fst, u8 offset_shift, u32 index, u32 total_file_infos)
     : m_fst(fst), m_offset_shift(offset_shift), m_index(index), m_total_file_infos(total_file_infos)
 {
 }
 
+// For the root object only.
+// m_fst and m_index must be correctly set before GetSize() is called!
+FileInfoGCWii::FileInfoGCWii(const u8* fst, u8 offset_shift)
+    : m_fst(fst), m_offset_shift(offset_shift), m_index(0), m_total_file_infos(GetSize())
+{
+}
+
+// Copy data that is common to the whole file system.
+FileInfoGCWii::FileInfoGCWii(const FileInfoGCWii& file_info, u32 index)
+    : FileInfoGCWii(file_info.m_fst, file_info.m_offset_shift, index, file_info.m_total_file_infos)
+{
+}
+
 FileInfoGCWii::~FileInfoGCWii()
 {
 }
 
+uintptr_t FileInfoGCWii::GetAddress() const
+{
+  return reinterpret_cast<uintptr_t>(m_fst + FST_ENTRY_SIZE * m_index);
+}
+
+u32 FileInfoGCWii::GetNextIndex() const
+{
+  return IsDirectory() ? GetSize() : m_index + 1;
+}
+
+FileInfo& FileInfoGCWii::operator++()
+{
+  m_index = GetNextIndex();
+  return *this;
+}
+
+std::unique_ptr<FileInfo> FileInfoGCWii::clone() const
+{
+  return std::make_unique<FileInfoGCWii>(*this);
+}
+
+FileInfo::const_iterator FileInfoGCWii::begin() const
+{
+  return const_iterator(std::make_unique<FileInfoGCWii>(*this, m_index + 1));
+}
+
+FileInfo::const_iterator FileInfoGCWii::end() const
+{
+  return const_iterator(std::make_unique<FileInfoGCWii>(*this, GetNextIndex()));
+}
+
 u32 FileInfoGCWii::Get(EntryProperty entry_property) const
 {
   return Common::swap32(m_fst + FST_ENTRY_SIZE * m_index +
@@ -41,12 +87,23 @@ u32 FileInfoGCWii::Get(EntryProperty entry_property) const
 
 u32 FileInfoGCWii::GetSize() const
 {
-  return Get(EntryProperty::FILE_SIZE);
+  u32 result = Get(EntryProperty::FILE_SIZE);
+
+  if (IsDirectory() && result <= m_index)
+  {
+    // For directories, GetSize is supposed to return the index of the next entry.
+    // If a file system is malformed and instead has an index that isn't after this one,
+    // we act as if the directory is empty to avoid strange behavior.
+    ERROR_LOG(DISCIO, "Invalid folder end in file system");
+    return m_index + 1;
+  }
+
+  return result;
 }
 
 u64 FileInfoGCWii::GetOffset() const
 {
-  return static_cast<u64>(Get(EntryProperty::FILE_OFFSET)) << (IsDirectory() ? 0 : m_offset_shift);
+  return static_cast<u64>(Get(EntryProperty::FILE_OFFSET)) << m_offset_shift;
 }
 
 bool FileInfoGCWii::IsDirectory() const
@@ -54,6 +111,11 @@ bool FileInfoGCWii::IsDirectory() const
   return (Get(EntryProperty::NAME_OFFSET) & 0xFF000000) != 0;
 }
 
+u32 FileInfoGCWii::GetTotalChildren() const
+{
+  return GetSize() - (m_index + 1);
+}
+
 std::string FileInfoGCWii::GetName() const
 {
   // TODO: Should we really always use SHIFT-JIS?
@@ -63,8 +125,48 @@ std::string FileInfoGCWii::GetName() const
   return SHIFTJISToUTF8(reinterpret_cast<const char*>(name));
 }
 
+std::string FileInfoGCWii::GetPath() const
+{
+  // The root entry doesn't have a name
+  if (m_index == 0)
+    return "";
+
+  if (IsDirectory())
+  {
+    u32 parent_directory_index = Get(EntryProperty::FILE_OFFSET);
+    if (parent_directory_index >= m_index)
+    {
+      // The index of the parent directory is supposed to be smaller than
+      // the current index. If an FST is malformed and breaks that rule,
+      // there's a risk that parent directory pointers form a loop.
+      // To avoid stack overflows, this method returns.
+      ERROR_LOG(DISCIO, "Invalid parent offset in file system");
+      return "";
+    }
+    return FileInfoGCWii(*this, parent_directory_index).GetPath() + GetName() + "/";
+  }
+  else
+  {
+    // The parent directory can be found by searching backwards
+    // for a directory that contains this file.
+
+    FileInfoGCWii potential_parent(*this, m_index - 1);
+    while (!(potential_parent.IsDirectory() && potential_parent.GetSize() > m_index))
+    {
+      if (potential_parent.m_index == 0)
+      {
+        // This can happen if an FST has a root with a size that's too small
+        ERROR_LOG(DISCIO, "The parent of %s couldn't be found", GetName().c_str());
+        return "";
+      }
+      potential_parent = FileInfoGCWii(*this, potential_parent.m_index - 1);
+    }
+    return potential_parent.GetPath() + GetName();
+  }
+}
+
 FileSystemGCWii::FileSystemGCWii(const Volume* _rVolume, const Partition& partition)
-    : FileSystem(_rVolume, partition), m_Valid(false), m_offset_shift(0)
+    : FileSystem(_rVolume, partition), m_Valid(false), m_offset_shift(0), m_root(nullptr, 0, 0, 0)
 {
   // Check if this is a GameCube or Wii disc
   if (m_rVolume->ReadSwapped<u32>(0x18, m_partition) == u32(0x5D1C9EA3))
@@ -81,7 +183,10 @@ FileSystemGCWii::FileSystemGCWii(const Volume* _rVolume, const Partition& partit
   const u64 fst_offset = static_cast<u64>(*fst_offset_unshifted) << m_offset_shift;
   const u64 fst_size = static_cast<u64>(*fst_size_unshifted) << m_offset_shift;
   if (fst_size < FST_ENTRY_SIZE)
+  {
+    ERROR_LOG(DISCIO, "File system is too small");
     return;
+  }
 
   // 128 MiB is more than the total amount of RAM in a Wii.
   // No file system should use anywhere near that much.
@@ -98,17 +203,18 @@ FileSystemGCWii::FileSystemGCWii(const Volume* _rVolume, const Partition& partit
   // Read the whole FST
   m_file_system_table.resize(fst_size);
   if (!m_rVolume->Read(fst_offset, fst_size, m_file_system_table.data(), m_partition))
+  {
+    ERROR_LOG(DISCIO, "Couldn't read file system table");
     return;
+  }
 
-  // Create all file info objects
-  u32 number_of_file_infos = Common::swap32(*((u32*)m_file_system_table.data() + 2));
-  const u8* fst_start = m_file_system_table.data();
-  const u8* name_table_start = fst_start + (FST_ENTRY_SIZE * number_of_file_infos);
-  const u8* name_table_end = fst_start + fst_size;
-  if (name_table_end < name_table_start)
+  // Create the root object
+  m_root = FileInfoGCWii(m_file_system_table.data(), m_offset_shift);
+  if (!m_root.IsDirectory())
+  {
+    ERROR_LOG(DISCIO, "File system root is not a directory");
     return;
-  for (u32 i = 0; i < number_of_file_infos; i++)
-    m_FileInfoVector.emplace_back(fst_start, m_offset_shift, i, number_of_file_infos);
+  }
 
   // If we haven't returned yet, everything succeeded
   m_Valid = true;
@@ -116,33 +222,32 @@ FileSystemGCWii::FileSystemGCWii(const Volume* _rVolume, const Partition& partit
 
 FileSystemGCWii::~FileSystemGCWii()
 {
-  m_FileInfoVector.clear();
 }
 
-const std::vector<FileInfoGCWii>& FileSystemGCWii::GetFileList() const
+const FileInfo& FileSystemGCWii::GetRoot() const
 {
-  return m_FileInfoVector;
+  return m_root;
 }
 
-const FileInfo* FileSystemGCWii::FindFileInfo(const std::string& path) const
+std::unique_ptr<FileInfo> FileSystemGCWii::FindFileInfo(const std::string& path) const
 {
-  if (m_FileInfoVector.empty())
+  if (!IsValid())
     return nullptr;
 
-  return FindFileInfo(path, 0);
+  return FindFileInfo(path, m_root);
 }
 
-const FileInfo* FileSystemGCWii::FindFileInfo(const std::string& path,
-                                              size_t search_start_offset) const
+std::unique_ptr<FileInfo> FileSystemGCWii::FindFileInfo(const std::string& path,
+                                                        const FileInfo& file_info) const
 {
   // Given a path like "directory1/directory2/fileA.bin", this function will
   // find directory1 and then call itself to search for "directory2/fileA.bin".
 
   if (path.empty() || path == "/")
-    return &m_FileInfoVector[search_start_offset];
+    return file_info.clone();
 
   // It's only possible to search in directories. Searching in a file is an error
-  if (!m_FileInfoVector[search_start_offset].IsDirectory())
+  if (!file_info.IsDirectory())
     return nullptr;
 
   size_t first_dir_separator = path.find('/');
@@ -150,113 +255,50 @@ const FileInfo* FileSystemGCWii::FindFileInfo(const std::string& path,
   const std::string rest_of_path =
       (first_dir_separator != std::string::npos) ? path.substr(first_dir_separator + 1) : "";
 
-  size_t search_end_offset = m_FileInfoVector[search_start_offset].GetSize();
-  search_start_offset++;
-  while (search_start_offset < search_end_offset)
+  for (const FileInfo& child : file_info)
   {
-    const FileInfoGCWii& file_info = m_FileInfoVector[search_start_offset];
-
-    if (file_info.GetName() == searching_for)
+    if (child.GetName() == searching_for)
     {
       // A match is found. The rest of the path is passed on to finish the search.
-      const FileInfo* result = FindFileInfo(rest_of_path, search_start_offset);
+      std::unique_ptr<FileInfo> result = FindFileInfo(rest_of_path, child);
 
       // If the search wasn't successful, the loop continues, just in case there's a second
       // file info that matches searching_for (which probably won't happen in practice)
       if (result)
         return result;
     }
-
-    if (file_info.IsDirectory())
-    {
-      // Skip a directory and everything that it contains
-
-      if (file_info.GetSize() <= search_start_offset)
-      {
-        // The next offset (obtained by GetSize) is supposed to be larger than
-        // the current offset. If an FST is malformed and breaks that rule,
-        // there's a risk that next offset pointers form a loop.
-        // To avoid infinite loops, this method returns.
-        ERROR_LOG(DISCIO, "Invalid next offset in file system");
-        return nullptr;
-      }
-
-      search_start_offset = file_info.GetSize();
-    }
-    else
-    {
-      // Skip a single file
-      search_start_offset++;
-    }
   }
 
   return nullptr;
 }
 
-const FileInfo* FileSystemGCWii::FindFileInfo(u64 disc_offset) const
+std::unique_ptr<FileInfo> FileSystemGCWii::FindFileInfo(u64 disc_offset) const
 {
-  for (auto& file_info : m_FileInfoVector)
-  {
-    if ((file_info.GetOffset() <= disc_offset) &&
-        ((file_info.GetOffset() + file_info.GetSize()) > disc_offset))
-    {
-      return &file_info;
-    }
-  }
+  if (!IsValid())
+    return nullptr;
 
-  return nullptr;
+  return FindFileInfo(disc_offset, m_root);
 }
 
-std::string FileSystemGCWii::GetPath(u64 _Address) const
+std::unique_ptr<FileInfo> FileSystemGCWii::FindFileInfo(u64 disc_offset,
+                                                        const FileInfo& file_info) const
 {
-  for (size_t i = 0; i < m_FileInfoVector.size(); ++i)
+  for (const FileInfo& child : file_info)
   {
-    const FileInfoGCWii& file_info = m_FileInfoVector[i];
-    if ((file_info.GetOffset() <= _Address) &&
-        ((file_info.GetOffset() + file_info.GetSize()) > _Address))
+    if (child.IsDirectory())
     {
-      return GetPathFromFSTOffset(i);
+      std::unique_ptr<FileInfo> result = FindFileInfo(disc_offset, child);
+      if (result)
+        return result;
     }
-  }
-
-  return "";
-}
-
-std::string FileSystemGCWii::GetPathFromFSTOffset(size_t file_info_offset) const
-{
-  // Root entry doesn't have a name
-  if (file_info_offset == 0)
-    return "";
-
-  const FileInfoGCWii& file_info = m_FileInfoVector[file_info_offset];
-  if (file_info.IsDirectory())
-  {
-    // The offset of the parent directory is stored in the current directory.
-
-    if (file_info.GetOffset() >= file_info_offset)
+    else if ((file_info.GetOffset() <= disc_offset) &&
+             ((file_info.GetOffset() + file_info.GetSize()) > disc_offset))
     {
-      // The offset of the parent directory is supposed to be smaller than
-      // the current offset. If an FST is malformed and breaks that rule,
-      // there's a risk that parent directory pointers form a loop.
-      // To avoid stack overflows, this method returns.
-      ERROR_LOG(DISCIO, "Invalid parent offset in file system");
-      return "";
+      return file_info.clone();
     }
-    return GetPathFromFSTOffset(file_info.GetOffset()) + file_info.GetName() + "/";
   }
-  else
-  {
-    // The parent directory can be found by searching backwards
-    // for a directory that contains this file.
 
-    size_t parent_offset = file_info_offset - 1;
-    while (!(m_FileInfoVector[parent_offset].IsDirectory() &&
-             m_FileInfoVector[parent_offset].GetSize() > file_info_offset))
-    {
-      parent_offset--;
-    }
-    return GetPathFromFSTOffset(parent_offset) + file_info.GetName();
-  }
+  return nullptr;
 }
 
 u64 FileSystemGCWii::ReadFile(const FileInfo* file_info, u8* _pBuffer, u64 _MaxBufferSize,
@@ -272,8 +314,8 @@ u64 FileSystemGCWii::ReadFile(const FileInfo* file_info, u8* _pBuffer, u64 _MaxB
 
   DEBUG_LOG(DISCIO, "Reading %" PRIx64 " bytes at %" PRIx64 " from file %s. Offset: %" PRIx64
                     " Size: %" PRIx32,
-            read_length, _OffsetInFile, GetPath(file_info->GetOffset()).c_str(),
-            file_info->GetOffset(), file_info->GetSize());
+            read_length, _OffsetInFile, file_info->GetPath().c_str(), file_info->GetOffset(),
+            file_info->GetSize());
 
   m_rVolume->Read(file_info->GetOffset() + _OffsetInFile, read_length, _pBuffer, m_partition);
   return read_length;
diff --git a/Source/Core/DiscIO/FileSystemGCWii.h b/Source/Core/DiscIO/FileSystemGCWii.h
index d4fb9dd90e..50782dacbf 100644
--- a/Source/Core/DiscIO/FileSystemGCWii.h
+++ b/Source/Core/DiscIO/FileSystemGCWii.h
@@ -5,6 +5,7 @@
 #pragma once
 
 #include <cstddef>
+#include <memory>
 #include <optional>
 #include <string>
 #include <vector>
@@ -20,30 +21,60 @@ struct Partition;
 class FileInfoGCWii : public FileInfo
 {
 public:
-  // Does not take ownership of pointers
+  // None of the constructors take ownership of FST pointers
+
+  // Set everything manually
   FileInfoGCWii(const u8* fst, u8 offset_shift, u32 index, u32 total_file_infos);
+  // For the root object only
+  FileInfoGCWii(const u8* fst, u8 offset_shift);
+  // Copy another object
+  FileInfoGCWii(const FileInfoGCWii& file_info) = default;
+  // Copy data that is common to the whole file system
+  FileInfoGCWii(const FileInfoGCWii& file_info, u32 index);
 
   ~FileInfoGCWii() override;
 
+  std::unique_ptr<FileInfo> clone() const override;
+  const_iterator begin() const override;
+  const_iterator end() const override;
+
   u64 GetOffset() const override;
   u32 GetSize() const override;
   bool IsDirectory() const override;
+  u32 GetTotalChildren() const override;
   std::string GetName() const override;
+  std::string GetPath() const override;
+
+protected:
+  uintptr_t GetAddress() const override;
+  FileInfo& operator++() override;
 
 private:
   enum class EntryProperty
   {
+    // NAME_OFFSET's lower 3 bytes are the name's offset within the name table.
+    // NAME_OFFSET's upper 1 byte is 1 for directories and 0 for files.
     NAME_OFFSET = 0,
+    // For files, FILE_OFFSET is the file offset in the partition,
+    // and for directories, it's the FST index of the parent directory.
+    // The root directory has its parent directory index set to 0.
     FILE_OFFSET = 1,
+    // For files, FILE_SIZE is the file size, and for directories,
+    // it's the FST index of the next entry that isn't in the directory.
     FILE_SIZE = 2
   };
 
+  // For files, returns the index of the next item. For directories,
+  // returns the index of the next item that isn't inside it.
+  u32 GetNextIndex() const;
+  // Returns one of the three properties of this FST entry.
+  // Read the comments in EntryProperty for details.
   u32 Get(EntryProperty entry_property) const;
 
-  const u8* const m_fst;
-  const u8 m_offset_shift;
-  const u32 m_index;
-  const u32 m_total_file_infos;
+  const u8* m_fst;
+  u8 m_offset_shift;
+  u32 m_index;
+  u32 m_total_file_infos;
 };
 
 class FileSystemGCWii : public FileSystem
@@ -51,12 +82,12 @@ class FileSystemGCWii : public FileSystem
 public:
   FileSystemGCWii(const Volume* _rVolume, const Partition& partition);
   ~FileSystemGCWii() override;
+
   bool IsValid() const override { return m_Valid; }
-  const std::vector<FileInfoGCWii>& GetFileList() const override;
-  const FileInfo* FindFileInfo(const std::string& path) const override;
-  const FileInfo* FindFileInfo(u64 disc_offset) const override;
-  std::string GetPath(u64 _Address) const override;
-  std::string GetPathFromFSTOffset(size_t file_info_offset) const override;
+  const FileInfo& GetRoot() const override;
+  std::unique_ptr<FileInfo> FindFileInfo(const std::string& path) const override;
+  std::unique_ptr<FileInfo> FindFileInfo(u64 disc_offset) const override;
+
   u64 ReadFile(const FileInfo* file_info, u8* _pBuffer, u64 _MaxBufferSize,
                u64 _OffsetInFile) const override;
   bool ExportFile(const FileInfo* file_info, const std::string& _rExportFilename) const override;
@@ -68,10 +99,11 @@ public:
 private:
   bool m_Valid;
   u32 m_offset_shift;
-  std::vector<FileInfoGCWii> m_FileInfoVector;
   std::vector<u8> m_file_system_table;
+  FileInfoGCWii m_root;
 
-  const FileInfo* FindFileInfo(const std::string& path, size_t search_start_offset) const;
+  std::unique_ptr<FileInfo> FindFileInfo(const std::string& path, const FileInfo& file_info) const;
+  std::unique_ptr<FileInfo> FindFileInfo(u64 disc_offset, const FileInfo& file_info) const;
 };
 
 }  // namespace
diff --git a/Source/Core/DiscIO/Filesystem.h b/Source/Core/DiscIO/Filesystem.h
index 2f1fe2c82d..363a57b385 100644
--- a/Source/Core/DiscIO/Filesystem.h
+++ b/Source/Core/DiscIO/Filesystem.h
@@ -4,6 +4,7 @@
 
 #pragma once
 
+#include <iterator>
 #include <memory>
 #include <optional>
 #include <string>
@@ -14,42 +15,116 @@
 
 namespace DiscIO
 {
-// TODO: eww
-class FileInfoGCWii;
-
 // file info of an FST entry
 class FileInfo
 {
+  friend class const_iterator;
+
 public:
+  class const_iterator final
+  {
+  public:
+    using iterator_category = std::forward_iterator_tag;
+    using value_type = const FileInfo;
+    using difference_type = std::ptrdiff_t;
+    using pointer = value_type*;
+    using reference = value_type&;
+
+    const_iterator() : m_file_info(nullptr) {}
+    const_iterator(std::unique_ptr<FileInfo> file_info) : m_file_info(std::move(file_info)) {}
+    const_iterator(const const_iterator& it) : m_file_info(it.m_file_info->clone()) {}
+    const_iterator(const_iterator&& it) : m_file_info(std::move(it.m_file_info)) {}
+    ~const_iterator() {}
+    const_iterator& operator=(const const_iterator& it)
+    {
+      m_file_info = it.m_file_info ? it.m_file_info->clone() : nullptr;
+      return *this;
+    }
+    const_iterator& operator=(const_iterator&& it)
+    {
+      m_file_info = std::move(it.m_file_info);
+      return *this;
+    }
+    const_iterator& operator++()
+    {
+      ++*m_file_info;
+      return *this;
+    }
+    const_iterator operator++(int)
+    {
+      const_iterator old = *this;
+      ++*m_file_info;
+      return old;
+    }
+    bool operator==(const const_iterator& it) const
+    {
+      return m_file_info ? (it.m_file_info && *m_file_info == *it.m_file_info) : (!it.m_file_info);
+    }
+    bool operator!=(const const_iterator& it) const { return !operator==(it); }
+    // Incrementing or destroying an iterator will invalidate its returned references and
+    // pointers, but will not invalidate copies of the iterator or file info object.
+    const FileInfo& operator*() const { return *m_file_info.get(); }
+    const FileInfo* operator->() const { return m_file_info.get(); }
+  private:
+    std::unique_ptr<FileInfo> m_file_info;
+  };
+
   virtual ~FileInfo();
 
-  // Not guaranteed to return a meaningful value for directories
+  bool operator==(const FileInfo& other) const { return GetAddress() == other.GetAddress(); }
+  bool operator!=(const FileInfo& other) const { return !operator==(other); }
+  virtual std::unique_ptr<FileInfo> clone() const = 0;
+  virtual const_iterator cbegin() const { return begin(); }
+  virtual const_iterator cend() const { return end(); }
+  virtual const_iterator begin() const = 0;
+  virtual const_iterator end() const = 0;
+
+  // The offset of a file on the disc (inside the partition, if there is one).
+  // Not guaranteed to return a meaningful value for directories.
   virtual u64 GetOffset() const = 0;
-  // Not guaranteed to return a meaningful value for directories
+  // The size of a file.
+  // Not guaranteed to return a meaningful value for directories.
   virtual u32 GetSize() const = 0;
   virtual bool IsDirectory() const = 0;
+  // The number of files and directories in a directory, including those in subdirectories.
+  // Not guaranteed to return a meaningful value for files.
+  virtual u32 GetTotalChildren() const = 0;
   virtual std::string GetName() const = 0;
+  // GetPath will find the parents of the current object and call GetName on them,
+  // so it's slower than other functions. If you're traversing through folders
+  // to get a file and its path, building the path while traversing is faster.
+  virtual std::string GetPath() const = 0;
+
+protected:
+  // Only used for comparisons with other file info objects
+  virtual uintptr_t GetAddress() const = 0;
+
+  // Called by iterators
+  virtual FileInfo& operator++() = 0;
 };
 
 class FileSystem
 {
 public:
   FileSystem(const Volume* _rVolume, const Partition& partition);
-
   virtual ~FileSystem();
+
+  // If IsValid is false, GetRoot must not be called. CreateFileSystem
+  // takes care of this automatically, so other code is recommended to use it.
   virtual bool IsValid() const = 0;
-  // TODO: Should only return FileInfo, not FileInfoGCWii
-  virtual const std::vector<FileInfoGCWii>& GetFileList() const = 0;
-  virtual const FileInfo* FindFileInfo(const std::string& path) const = 0;
-  virtual const FileInfo* FindFileInfo(u64 disc_offset) const = 0;
+  // The object returned by GetRoot and all objects created from it
+  // are only valid for as long as the file system object is valid.
+  virtual const FileInfo& GetRoot() const = 0;
+  // Returns nullptr if not found
+  virtual std::unique_ptr<FileInfo> FindFileInfo(const std::string& path) const = 0;
+  // Returns nullptr if not found
+  virtual std::unique_ptr<FileInfo> FindFileInfo(u64 disc_offset) const = 0;
+
   virtual u64 ReadFile(const FileInfo* file_info, u8* _pBuffer, u64 _MaxBufferSize,
                        u64 _OffsetInFile = 0) const = 0;
-  virtual bool ExportFile(const FileInfo* file_info,
-                          const std::string& _rExportFilename) const = 0;
+  virtual bool ExportFile(const FileInfo* file_info, const std::string& _rExportFilename) const = 0;
   virtual bool ExportApploader(const std::string& _rExportFolder) const = 0;
   virtual bool ExportDOL(const std::string& _rExportFolder) const = 0;
-  virtual std::string GetPath(u64 _Address) const = 0;
-  virtual std::string GetPathFromFSTOffset(size_t file_info_offset) const = 0;
   virtual std::optional<u64> GetBootDOLOffset() const = 0;
   virtual std::optional<u32> GetBootDOLSize(u64 dol_offset) const = 0;
 
@@ -59,6 +134,7 @@ protected:
   const Partition m_partition;
 };
 
+// Returns nullptr if a valid file system could not be created
 std::unique_ptr<FileSystem> CreateFileSystem(const Volume* volume, const Partition& partition);
 
 }  // namespace
diff --git a/Source/Core/DiscIO/VolumeGC.cpp b/Source/Core/DiscIO/VolumeGC.cpp
index 09f073d075..af4178682f 100644
--- a/Source/Core/DiscIO/VolumeGC.cpp
+++ b/Source/Core/DiscIO/VolumeGC.cpp
@@ -177,7 +177,7 @@ void VolumeGC::LoadBannerFile() const
   if (!file_system)
     return;
 
-  const FileInfo* file_info = file_system->FindFileInfo("opening.bnr");
+  std::unique_ptr<FileInfo> file_info = file_system->FindFileInfo("opening.bnr");
   if (!file_info)
     return;
 
@@ -190,7 +190,8 @@ void VolumeGC::LoadBannerFile() const
     return;
   }
 
-  if (file_size != file_system->ReadFile(file_info, reinterpret_cast<u8*>(&banner_file), file_size))
+  if (file_size !=
+      file_system->ReadFile(file_info.get(), reinterpret_cast<u8*>(&banner_file), file_size))
   {
     WARN_LOG(DISCIO, "Could not read opening.bnr.");
     return;
diff --git a/Source/Core/DiscIO/VolumeWii.cpp b/Source/Core/DiscIO/VolumeWii.cpp
index 6b1cf6dafa..b8215527a6 100644
--- a/Source/Core/DiscIO/VolumeWii.cpp
+++ b/Source/Core/DiscIO/VolumeWii.cpp
@@ -274,9 +274,9 @@ std::map<Language, std::string> VolumeWii::GetLongNames() const
     return {};
 
   std::vector<u8> opening_bnr(NAMES_TOTAL_BYTES);
-  const FileInfo* file_info = file_system->FindFileInfo("opening.bnr");
-  size_t size = file_system->ReadFile(file_info, opening_bnr.data(), opening_bnr.size(), 0x5C);
-  opening_bnr.resize(size);
+  std::unique_ptr<FileInfo> file_info = file_system->FindFileInfo("opening.bnr");
+  opening_bnr.resize(
+      file_system->ReadFile(file_info.get(), opening_bnr.data(), opening_bnr.size(), 0x5C));
   return ReadWiiNames(opening_bnr);
 }
 
diff --git a/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.cpp b/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.cpp
index cb4e3fd059..e13b96db07 100644
--- a/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.cpp
+++ b/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.cpp
@@ -5,6 +5,8 @@
 #include "DolphinWX/ISOProperties/FilesystemPanel.h"
 
 #include <array>
+#include <functional>
+#include <memory>
 #include <vector>
 
 #include <wx/bitmap.h>
@@ -23,8 +25,6 @@
 #include "Common/Logging/Log.h"
 #include "DiscIO/Enums.h"
 #include "DiscIO/Filesystem.h"
-// TODO: eww
-#include "DiscIO/FileSystemGCWii.h"
 #include "DiscIO/Volume.h"
 #include "DolphinWX/ISOFile.h"
 #include "DolphinWX/WxUtils.h"
@@ -85,41 +85,22 @@ wxImageList* LoadIconBitmaps(const wxWindow* context)
   return icon_list;
 }
 
-size_t CreateDirectoryTree(wxTreeCtrl* tree_ctrl, wxTreeItemId parent,
-                           const std::vector<DiscIO::FileInfoGCWii>& file_infos,
-                           const size_t first_index, const size_t last_index)
+void CreateDirectoryTree(wxTreeCtrl* tree_ctrl, wxTreeItemId parent,
+                         const DiscIO::FileInfo& directory)
 {
-  size_t current_index = first_index;
-
-  while (current_index < last_index)
+  for (const DiscIO::FileInfo& file_info : directory)
   {
-    const DiscIO::FileInfoGCWii& file_info = file_infos[current_index];
-
-    // check next index
+    const wxString name = StrToWxStr(file_info.GetName());
     if (file_info.IsDirectory())
     {
-      const wxTreeItemId item =
-          tree_ctrl->AppendItem(parent, StrToWxStr(file_info.GetName()), ICON_FOLDER);
-      current_index = CreateDirectoryTree(tree_ctrl, item, file_infos, current_index + 1,
-                                          static_cast<size_t>(file_info.GetSize()));
+      wxTreeItemId item = tree_ctrl->AppendItem(parent, name, ICON_FOLDER);
+      CreateDirectoryTree(tree_ctrl, item, file_info);
     }
     else
     {
-      tree_ctrl->AppendItem(parent, StrToWxStr(file_info.GetName()), ICON_FILE);
-      current_index++;
+      tree_ctrl->AppendItem(parent, name, ICON_FILE);
     }
   }
-
-  return current_index;
-}
-
-size_t CreateDirectoryTree(wxTreeCtrl* tree_ctrl, wxTreeItemId parent,
-                           const std::vector<DiscIO::FileInfoGCWii>& file_infos)
-{
-  if (file_infos.empty())
-    return 0;
-
-  return CreateDirectoryTree(tree_ctrl, parent, file_infos, 1, file_infos.at(0).GetSize());
 }
 
 WiiPartition* FindWiiPartition(wxTreeCtrl* tree_ctrl, const wxString& label)
@@ -201,7 +182,7 @@ bool FilesystemPanel::PopulateFileSystemTree()
         WiiPartition* const partition = new WiiPartition(std::move(file_system));
 
         m_tree_ctrl->SetItemData(partition_root, partition);
-        CreateDirectoryTree(m_tree_ctrl, partition_root, partition->filesystem->GetFileList());
+        CreateDirectoryTree(m_tree_ctrl, partition_root, partition->filesystem->GetRoot());
 
         if (partitions[i] == m_opened_iso->GetGamePartition())
           m_tree_ctrl->Expand(partition_root);
@@ -214,7 +195,7 @@ bool FilesystemPanel::PopulateFileSystemTree()
     if (!m_filesystem)
       return false;
 
-    CreateDirectoryTree(m_tree_ctrl, m_tree_ctrl->GetRootItem(), m_filesystem->GetFileList());
+    CreateDirectoryTree(m_tree_ctrl, m_tree_ctrl->GetRootItem(), m_filesystem->GetRoot());
   }
 
   return true;
@@ -382,13 +363,13 @@ void FilesystemPanel::ExtractAllFiles(const wxString& output_folder)
     while (item.IsOk())
     {
       const auto* const partition = static_cast<WiiPartition*>(m_tree_ctrl->GetItemData(item));
-      ExtractDirectories("", WxStrToStr(output_folder), partition->filesystem.get());
+      ExtractDirectories("", WxStrToStr(output_folder), *partition->filesystem);
       item = m_tree_ctrl->GetNextChild(root, cookie);
     }
   }
   else
   {
-    ExtractDirectories("", WxStrToStr(output_folder), m_filesystem.get());
+    ExtractDirectories("", WxStrToStr(output_folder), *m_filesystem);
   }
 }
 
@@ -406,12 +387,12 @@ void FilesystemPanel::ExtractSingleFile(const wxString& output_file_path) const
     selection_file_path.erase(0, slash_index + 1);
 
     partition->filesystem->ExportFile(
-        partition->filesystem->FindFileInfo(WxStrToStr(selection_file_path)),
+        partition->filesystem->FindFileInfo(WxStrToStr(selection_file_path)).get(),
         WxStrToStr(output_file_path));
   }
   else
   {
-    m_filesystem->ExportFile(m_filesystem->FindFileInfo(WxStrToStr(selection_file_path)),
+    m_filesystem->ExportFile(m_filesystem->FindFileInfo(WxStrToStr(selection_file_path)).get(),
                              WxStrToStr(output_file_path));
   }
 }
@@ -430,102 +411,71 @@ void FilesystemPanel::ExtractSingleDirectory(const wxString& output_folder)
     directory_path.erase(0, slash_index + 1);
 
     ExtractDirectories(WxStrToStr(directory_path), WxStrToStr(output_folder),
-                       partition->filesystem.get());
+                       *partition->filesystem);
   }
   else
   {
-    ExtractDirectories(WxStrToStr(directory_path), WxStrToStr(output_folder), m_filesystem.get());
+    ExtractDirectories(WxStrToStr(directory_path), WxStrToStr(output_folder), *m_filesystem);
   }
 }
 
-void FilesystemPanel::ExtractDirectories(const std::string& full_path,
-                                         const std::string& output_folder,
-                                         DiscIO::FileSystem* filesystem)
+void ExtractDir(const std::string& full_path, const std::string& output_folder,
+                const DiscIO::FileSystem& file_system, const DiscIO::FileInfo& directory,
+                const std::function<bool(const std::string& path)>& update_progress)
 {
-  const std::vector<DiscIO::FileInfoGCWii>& fst = filesystem->GetFileList();
+  for (const DiscIO::FileInfo& file_info : directory)
+  {
+    const std::string path = full_path + file_info.GetName() + (file_info.IsDirectory() ? "/" : "");
+    const std::string output_path = output_folder + DIR_SEP_CHR + path;
 
-  u32 index = 0;
-  u32 size = 0;
+    if (update_progress(path))
+      return;
 
-  // Extract all
-  if (full_path.empty())
-  {
-    size = static_cast<u32>(fst.size());
+    DEBUG_LOG(DISCIO, "%s", output_path.c_str());
 
-    filesystem->ExportApploader(output_folder);
-    filesystem->ExportDOL(output_folder);
-  }
-  else
-  {
-    // Look for the dir we are going to extract
-    // TODO: Make this more efficient
-    for (index = 0; index < fst.size(); ++index)
+    if (file_info.IsDirectory())
     {
-      if (filesystem->GetPathFromFSTOffset(index) == full_path)
-      {
-        INFO_LOG(DISCIO, "Found the directory at %u", index);
-        size = static_cast<u32>(fst[index].GetSize());
-        break;
-      }
+      File::CreateFullPath(output_path);
+      ExtractDir(path, output_folder, file_system, file_info, update_progress);
+    }
+    else
+    {
+      if (File::Exists(output_path))
+        NOTICE_LOG(DISCIO, "%s already exists", output_path.c_str());
+      else if (!file_system.ExportFile(&file_info, output_path))
+        ERROR_LOG(DISCIO, "Could not export %s", output_path.c_str());
     }
+  }
+}
 
-    INFO_LOG(DISCIO, "Directory found from %u to %u\nextracting to: %s", index, size,
-             output_folder.c_str());
+void FilesystemPanel::ExtractDirectories(const std::string& full_path,
+                                         const std::string& output_folder,
+                                         const DiscIO::FileSystem& filesystem)
+{
+  if (full_path.empty())  // Root
+  {
+    filesystem.ExportApploader(output_folder);
+    filesystem.ExportDOL(output_folder);
   }
 
-  const auto dialog_title = (index != 0) ? _("Extracting Directory") : _("Extracting All Files");
-  wxProgressDialog dialog(dialog_title, _("Extracting..."), static_cast<int>(size - 1), this,
+  std::unique_ptr<DiscIO::FileInfo> file_info = filesystem.FindFileInfo(full_path);
+  u32 size = file_info->GetTotalChildren();
+  u32 progress = 0;
+
+  wxString dialog_title = full_path.empty() ? _("Extracting All Files") : _("Extracting Directory");
+  wxProgressDialog dialog(dialog_title, _("Extracting..."), size, this,
                           wxPD_APP_MODAL | wxPD_AUTO_HIDE | wxPD_CAN_ABORT | wxPD_ELAPSED_TIME |
                               wxPD_ESTIMATED_TIME | wxPD_REMAINING_TIME | wxPD_SMOOTH);
 
-  // Extraction
-  for (u32 i = index; i < size; i++)
-  {
-    const std::string path = filesystem->GetPathFromFSTOffset(i);
+  File::CreateFullPath(output_folder + "/" + full_path);
+  ExtractDir(full_path, output_folder, filesystem, *file_info, [&](const std::string& path) {
     dialog.SetTitle(wxString::Format(
-        "%s : %u%%", dialog_title.c_str(),
-        static_cast<u32>((static_cast<float>(i - index) / static_cast<float>(size - index)) *
-                         100)));
-
-    dialog.Update(i, wxString::Format(_("Extracting %s"), StrToWxStr(path)));
-
-    if (dialog.WasCancelled())
-      break;
-
-    if (fst[i].IsDirectory())
-    {
-      const std::string export_name =
-          StringFromFormat("%s/%s/", output_folder.c_str(), path.c_str());
-      INFO_LOG(DISCIO, "%s", export_name.c_str());
-
-      if (!File::Exists(export_name) && !File::CreateFullPath(export_name))
-      {
-        ERROR_LOG(DISCIO, "Could not create the path %s", export_name.c_str());
-      }
-      else
-      {
-        if (!File::IsDirectory(export_name))
-          ERROR_LOG(DISCIO, "%s already exists and is not a directory", export_name.c_str());
-
-        ERROR_LOG(DISCIO, "Folder %s already exists", export_name.c_str());
-      }
-    }
-    else
-    {
-      const std::string export_name =
-          StringFromFormat("%s/%s", output_folder.c_str(), path.c_str());
-      INFO_LOG(DISCIO, "%s", export_name.c_str());
-
-      if (!File::Exists(export_name) && !filesystem->ExportFile(&fst[index], export_name))
-      {
-        ERROR_LOG(DISCIO, "Could not export %s", export_name.c_str());
-      }
-      else
-      {
-        ERROR_LOG(DISCIO, "%s already exists", export_name.c_str());
-      }
-    }
-  }
+        "%s : %d%%", dialog_title.c_str(),
+        static_cast<u32>((static_cast<float>(progress) / static_cast<float>(size)) * 100)));
+    dialog.Update(progress, wxString::Format(_("Extracting %s"), StrToWxStr(path)));
+    ++progress;
+    return dialog.WasCancelled();
+  });
 }
 
 wxString FilesystemPanel::BuildFilePathFromSelection() const
diff --git a/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.h b/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.h
index 969dde1dc4..ae898b8fd5 100644
--- a/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.h
+++ b/Source/Core/DolphinWX/ISOProperties/FilesystemPanel.h
@@ -51,7 +51,7 @@ private:
   void ExtractSingleFile(const wxString& output_file_path) const;
   void ExtractSingleDirectory(const wxString& output_folder);
   void ExtractDirectories(const std::string& full_path, const std::string& output_folder,
-                          DiscIO::FileSystem* filesystem);
+                          const DiscIO::FileSystem& filesystem);
 
   wxString BuildFilePathFromSelection() const;
   wxString BuildDirectoryPathFromSelection() const;
diff --git a/Source/Core/DolphinWX/ISOProperties/ISOProperties.h b/Source/Core/DolphinWX/ISOProperties/ISOProperties.h
index 8041b54adb..b3c6f15b00 100644
--- a/Source/Core/DolphinWX/ISOProperties/ISOProperties.h
+++ b/Source/Core/DolphinWX/ISOProperties/ISOProperties.h
@@ -5,6 +5,7 @@
 #pragma once
 
 #include <cstddef>
+#include <functional>
 #include <memory>
 #include <set>
 #include <string>