/* vim:set ts=2 sw=2 sts=2 et: */
/**
 * \author     Marcus Holland-Moritz (github@mhxnet.de)
 * \copyright  Copyright (c) Marcus Holland-Moritz
 *
 * This file is part of dwarfs.
 *
 * dwarfs 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 3 of the License, or
 * (at your option) any later version.
 *
 * dwarfs 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 dwarfs.  If not, see <https://www.gnu.org/licenses/>.
 */

#include <gtest/gtest.h>

// TODO: this test should be autogenerated somehow...

#include <algorithm>
#include <cstring>
#include <map>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>

#include <folly/FileUtil.h>
#include <folly/String.h>
#include <folly/json.h>

#include "dwarfs/block_compressor.h"
#include "dwarfs/file_stat.h"
#include "dwarfs/filesystem_block_category_resolver.h"
#include "dwarfs/filesystem_extractor.h"
#include "dwarfs/filesystem_v2.h"
#include "dwarfs/filesystem_writer.h"
#include "dwarfs/logger.h"
#include "dwarfs/mmap.h"
#include "dwarfs/options.h"
#include "dwarfs/progress.h"
#include "dwarfs/vfs_stat.h"
#include "dwarfs/worker_group.h"

#include "mmap_mock.h"
#include "test_logger.h"

using namespace dwarfs;

namespace {

char const* reference_v0_2 = R"(
{
  "root": {
    "inode": 0,
    "inodes": [
      {
        "inode": 32,
        "mode": 33188,
        "modestring": "----rw-r--r--",
        "name": "bench.sh",
        "size": 1517,
        "type": "file"
      },
      {
        "inode": 1,
        "inodes": [],
        "mode": 16877,
        "modestring": "---drwxr-xr-x",
        "name": "dev",
        "type": "directory"
      },
      {
        "inode": 2,
        "inodes": [
          {
            "inode": 3,
            "inodes": [],
            "mode": 16877,
            "modestring": "---drwxr-xr-x",
            "name": "alsoempty",
            "type": "directory"
          }
        ],
        "mode": 16877,
        "modestring": "---drwxr-xr-x",
        "name": "empty",
        "type": "directory"
      },
      {
        "inode": 4,
        "inodes": [
          {
            "inode": 5,
            "inodes": [
              {
                "inode": 6,
                "inodes": [
                  {
                    "inode": 7,
                    "inodes": [
                      {
                        "inode": 8,
                        "inodes": [
                          {
                            "inode": 9,
                            "inodes": [
                              {
                                "inode": 10,
                                "inodes": [
                                  {
                                    "inode": 11,
                                    "inodes": [
                                      {
                                        "inode": 12,
                                        "inodes": [
                                          {
                                            "inode": 13,
                                            "inodes": [
                                              {
                                                "inode": 17,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "a",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 18,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "b",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 32,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "blubb",
                                                "size": 1517,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 19,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "c",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 20,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "d",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 21,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "e",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 22,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "f",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 23,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "g",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 24,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "h",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 25,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "i",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 26,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "j",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 27,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "k",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 28,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "l",
                                                "size": 2,
                                                "type": "file"
                                              }
                                            ],
                                            "mode": 16877,
                                            "modestring": "---drwxr-xr-x",
                                            "name": "9",
                                            "type": "directory"
                                          }
                                        ],
                                        "mode": 16877,
                                        "modestring": "---drwxr-xr-x",
                                        "name": "8",
                                        "type": "directory"
                                      }
                                    ],
                                    "mode": 16877,
                                    "modestring": "---drwxr-xr-x",
                                    "name": "7",
                                    "type": "directory"
                                  }
                                ],
                                "mode": 16877,
                                "modestring": "---drwxr-xr-x",
                                "name": "6",
                                "type": "directory"
                              },
                              {
                                "inode": 32,
                                "mode": 33188,
                                "modestring": "----rw-r--r--",
                                "name": "z",
                                "size": 1517,
                                "type": "file"
                              }
                            ],
                            "mode": 16877,
                            "modestring": "---drwxr-xr-x",
                            "name": "5",
                            "type": "directory"
                          },
                          {
                            "inode": 32,
                            "mode": 33188,
                            "modestring": "----rw-r--r--",
                            "name": "y",
                            "size": 1517,
                            "type": "file"
                          }
                        ],
                        "mode": 16877,
                        "modestring": "---drwxr-xr-x",
                        "name": "4",
                        "type": "directory"
                      },
                      {
                        "inode": 29,
                        "mode": 33261,
                        "modestring": "----rwxr-xr-x",
                        "name": "copy.sh",
                        "size": 94,
                        "type": "file"
                      },
                      {
                        "inode": 32,
                        "mode": 33188,
                        "modestring": "----rw-r--r--",
                        "name": "x",
                        "size": 1517,
                        "type": "file"
                      }
                    ],
                    "mode": 16877,
                    "modestring": "---drwxr-xr-x",
                    "name": "3",
                    "type": "directory"
                  },
                  {
                    "inode": 29,
                    "mode": 33261,
                    "modestring": "----rwxr-xr-x",
                    "name": "xxx.sh",
                    "size": 94,
                    "type": "file"
                  }
                ],
                "mode": 16877,
                "modestring": "---drwxr-xr-x",
                "name": "2",
                "type": "directory"
              },
              {
                "inode": 29,
                "mode": 33261,
                "modestring": "----rwxr-xr-x",
                "name": "fmt.sh",
                "size": 94,
                "type": "file"
              }
            ],
            "mode": 16877,
            "modestring": "---drwxr-xr-x",
            "name": "1",
            "type": "directory"
          },
          {
            "inode": 14,
            "mode": 41471,
            "modestring": "---lrwxrwxrwx",
            "name": "bad",
            "target": "../foo",
            "type": "link"
          },
          {
            "inode": 16,
            "mode": 33188,
            "modestring": "----rw-r--r--",
            "name": "bar",
            "size": 0,
            "type": "file"
          },
          {
            "inode": 32,
            "mode": 33188,
            "modestring": "----rw-r--r--",
            "name": "bla.sh",
            "size": 1517,
            "type": "file"
          }
        ],
        "mode": 16877,
        "modestring": "---drwxr-xr-x",
        "name": "foo",
        "type": "directory"
      },
      {
        "inode": 15,
        "mode": 41471,
        "modestring": "---lrwxrwxrwx",
        "name": "foobar",
        "target": "foo/bar",
        "type": "link"
      },
      {
        "inode": 29,
        "mode": 33261,
        "modestring": "----rwxr-xr-x",
        "name": "format.sh",
        "size": 94,
        "type": "file"
      },
      {
        "inode": 31,
        "mode": 33188,
        "modestring": "----rw-r--r--",
        "name": "perl-exec.sh",
        "size": 87,
        "type": "file"
      },
      {
        "inode": 30,
        "mode": 33188,
        "modestring": "----rw-r--r--",
        "name": "test.py",
        "size": 1012,
        "type": "file"
      }
    ],
    "mode": 16877,
    "modestring": "---drwxr-xr-x",
    "type": "directory"
  },
  "statvfs": {
    "f_blocks": 10614,
    "f_bsize": 1024,
    "f_files": 33
  }
}
)";

char const* reference = R"(
{
  "root": {
    "inode": 0,
    "inodes": [
      {
        "inode": 32,
        "mode": 33188,
        "modestring": "----rw-r--r--",
        "name": "bench.sh",
        "size": 1517,
        "type": "file"
      },
      {
        "inode": 1,
        "inodes": [
          {
            "device_id": 259,
            "inode": 33,
            "mode": 8630,
            "modestring": "---crw-rw-rw-",
            "name": "null",
            "type": "chardev"
          },
          {
            "device_id": 261,
            "inode": 34,
            "mode": 8630,
            "modestring": "---crw-rw-rw-",
            "name": "zero",
            "type": "chardev"
          }
        ],
        "mode": 16877,
        "modestring": "---drwxr-xr-x",
        "name": "dev",
        "type": "directory"
      },
      {
        "inode": 2,
        "inodes": [
          {
            "inode": 3,
            "inodes": [],
            "mode": 16877,
            "modestring": "---drwxr-xr-x",
            "name": "alsoempty",
            "type": "directory"
          }
        ],
        "mode": 16877,
        "modestring": "---drwxr-xr-x",
        "name": "empty",
        "type": "directory"
      },
      {
        "inode": 4,
        "inodes": [
          {
            "inode": 5,
            "inodes": [
              {
                "inode": 6,
                "inodes": [
                  {
                    "inode": 7,
                    "inodes": [
                      {
                        "inode": 8,
                        "inodes": [
                          {
                            "inode": 9,
                            "inodes": [
                              {
                                "inode": 10,
                                "inodes": [
                                  {
                                    "inode": 11,
                                    "inodes": [
                                      {
                                        "inode": 12,
                                        "inodes": [
                                          {
                                            "inode": 13,
                                            "inodes": [
                                              {
                                                "inode": 17,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "a",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 18,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "b",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 32,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "blubb",
                                                "size": 1517,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 19,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "c",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 20,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "d",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 21,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "e",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 22,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "f",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 23,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "g",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 24,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "h",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 25,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "i",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 26,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "j",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 27,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "k",
                                                "size": 2,
                                                "type": "file"
                                              },
                                              {
                                                "inode": 28,
                                                "mode": 33188,
                                                "modestring": "----rw-r--r--",
                                                "name": "l",
                                                "size": 2,
                                                "type": "file"
                                              }
                                            ],
                                            "mode": 16877,
                                            "modestring": "---drwxr-xr-x",
                                            "name": "9",
                                            "type": "directory"
                                          }
                                        ],
                                        "mode": 16877,
                                        "modestring": "---drwxr-xr-x",
                                        "name": "8",
                                        "type": "directory"
                                      }
                                    ],
                                    "mode": 16877,
                                    "modestring": "---drwxr-xr-x",
                                    "name": "7",
                                    "type": "directory"
                                  }
                                ],
                                "mode": 16877,
                                "modestring": "---drwxr-xr-x",
                                "name": "6",
                                "type": "directory"
                              },
                              {
                                "inode": 32,
                                "mode": 33188,
                                "modestring": "----rw-r--r--",
                                "name": "z",
                                "size": 1517,
                                "type": "file"
                              }
                            ],
                            "mode": 16877,
                            "modestring": "---drwxr-xr-x",
                            "name": "5",
                            "type": "directory"
                          },
                          {
                            "inode": 32,
                            "mode": 33188,
                            "modestring": "----rw-r--r--",
                            "name": "y",
                            "size": 1517,
                            "type": "file"
                          }
                        ],
                        "mode": 16877,
                        "modestring": "---drwxr-xr-x",
                        "name": "4",
                        "type": "directory"
                      },
                      {
                        "inode": 29,
                        "mode": 33261,
                        "modestring": "----rwxr-xr-x",
                        "name": "copy.sh",
                        "size": 94,
                        "type": "file"
                      },
                      {
                        "inode": 32,
                        "mode": 33188,
                        "modestring": "----rw-r--r--",
                        "name": "x",
                        "size": 1517,
                        "type": "file"
                      }
                    ],
                    "mode": 16877,
                    "modestring": "---drwxr-xr-x",
                    "name": "3",
                    "type": "directory"
                  },
                  {
                    "inode": 29,
                    "mode": 33261,
                    "modestring": "----rwxr-xr-x",
                    "name": "xxx.sh",
                    "size": 94,
                    "type": "file"
                  }
                ],
                "mode": 16877,
                "modestring": "---drwxr-xr-x",
                "name": "2",
                "type": "directory"
              },
              {
                "inode": 29,
                "mode": 33261,
                "modestring": "----rwxr-xr-x",
                "name": "fmt.sh",
                "size": 94,
                "type": "file"
              }
            ],
            "mode": 16877,
            "modestring": "---drwxr-xr-x",
            "name": "1",
            "type": "directory"
          },
          {
            "inode": 14,
            "mode": 41471,
            "modestring": "---lrwxrwxrwx",
            "name": "bad",
            "target": "../foo",
            "type": "link"
          },
          {
            "inode": 16,
            "mode": 33188,
            "modestring": "----rw-r--r--",
            "name": "bar",
            "size": 0,
            "type": "file"
          },
          {
            "inode": 32,
            "mode": 33188,
            "modestring": "----rw-r--r--",
            "name": "bla.sh",
            "size": 1517,
            "type": "file"
          },
          {
            "inode": 35,
            "mode": 4516,
            "modestring": "---prw-r--r--",
            "name": "pipe",
            "type": "fifo"
          }
        ],
        "mode": 16877,
        "modestring": "---drwxr-xr-x",
        "name": "foo",
        "type": "directory"
      },
      {
        "inode": 15,
        "mode": 41471,
        "modestring": "---lrwxrwxrwx",
        "name": "foobar",
        "target": "foo/bar",
        "type": "link"
      },
      {
        "inode": 29,
        "mode": 33261,
        "modestring": "----rwxr-xr-x",
        "name": "format.sh",
        "size": 94,
        "type": "file"
      },
      {
        "inode": 31,
        "mode": 33188,
        "modestring": "----rw-r--r--",
        "name": "perl-exec.sh",
        "size": 87,
        "type": "file"
      },
      {
        "inode": 30,
        "mode": 33188,
        "modestring": "----rw-r--r--",
        "name": "test.py",
        "size": 1012,
        "type": "file"
      }
    ],
    "mode": 16877,
    "modestring": "---drwxr-xr-x",
    "type": "directory"
  },
  "statvfs": {
    "f_blocks": 10614,
    "f_bsize": 1024,
    "f_files": 36
  }
}
)";

std::vector<std::string> versions{
    "0.2.0", "0.2.3", "0.3.0", "0.4.0", "0.4.1",
};

std::string format_sh = R"(#!/bin/bash
find test/ src/ include/ -type f -name '*.[ch]*' | xargs -d $'\n' clang-format -i
)";

std::vector<std::string> headers{
    "D",
    "DWARFS",
    format_sh,
    "DWARFS" + format_sh,
    "DWARFS" + format_sh + "DWARDWAR",
};

std::vector<std::string> headers_v2{
    "DWARFS\x02",
    "DWARFS\x02" + format_sh,
    "DWARFS\x02" + format_sh + "DWARFS\x02",
};

file_stat make_stat(posix_file_type::value type, file_stat::perms_type perms,
                    file_stat::off_type size) {
  file_stat st;
  std::memset(&st, 0, sizeof(st));
  st.mode = type | perms;
  st.size = size;
  return st;
}

void check_compat(logger& lgr, filesystem_v2 const& fs,
                  std::string const& version) {
  bool has_devices = not(version == "0.2.0" or version == "0.2.3");
  bool has_ac_time = version == "0.2.0" or version == "0.2.3";

  vfs_stat vfsbuf;
  fs.statvfs(&vfsbuf);

  EXPECT_EQ(1024, vfsbuf.bsize);
  EXPECT_EQ(1, vfsbuf.frsize);
  EXPECT_EQ(10614, vfsbuf.blocks);
  EXPECT_EQ(33 + 3 * has_devices, vfsbuf.files);
  EXPECT_TRUE(vfsbuf.readonly);
  EXPECT_GT(vfsbuf.namemax, 0);

  auto json = fs.serialize_metadata_as_json(true);
  EXPECT_GT(json.size(), 1000) << json;

  std::ostringstream dumpss;
  fs.dump(dumpss, 9);
  EXPECT_GT(dumpss.str().size(), 1000) << dumpss.str();

  auto entry = fs.find("/format.sh");
  file_stat st;

  ASSERT_TRUE(entry);
  EXPECT_EQ(0, fs.getattr(*entry, &st));
  EXPECT_EQ(94, st.size);
  EXPECT_EQ(S_IFREG | 0755, st.mode);
  EXPECT_EQ(1000, st.uid);
  EXPECT_EQ(100, st.gid);
  EXPECT_EQ(1606256045, st.mtime);
  if (has_ac_time) {
    EXPECT_EQ(1616013831, st.atime);
    EXPECT_EQ(1616013816, st.ctime);
  }

  EXPECT_EQ(0, fs.access(*entry, R_OK, 1000, 0));

  auto inode = fs.open(*entry);
  EXPECT_GE(inode, 0);

  std::vector<char> buf(st.size);
  auto rv = fs.read(inode, &buf[0], st.size, 0);
  EXPECT_EQ(rv, st.size);
  EXPECT_EQ(format_sh, std::string(buf.begin(), buf.end()));

  entry = fs.find("/foo/bad");
  ASSERT_TRUE(entry);
  std::string link;
  EXPECT_EQ(fs.readlink(*entry, &link, readlink_mode::raw), 0);
  EXPECT_EQ(link, "../foo");

  entry = fs.find(0, "foo");
  ASSERT_TRUE(entry);

  auto dir = fs.opendir(*entry);
  ASSERT_TRUE(dir);
  EXPECT_EQ(6 + has_devices, fs.dirsize(*dir));

  std::vector<std::string> names;
  for (size_t i = 0; i < fs.dirsize(*dir); ++i) {
    auto r = fs.readdir(*dir, i);
    ASSERT_TRUE(r);
    auto [view, name] = *r;
    names.emplace_back(name);
  }

  std::vector<std::string> expected{
      ".", "..", "1", "bad", "bar", "bla.sh",
  };

  if (has_devices) {
    expected.push_back("pipe");
  }

  EXPECT_EQ(expected, names);

  std::map<std::string, file_stat> ref_entries{
      {"", make_stat(posix_file_type::directory, 0755, 8)},
      {"bench.sh", make_stat(posix_file_type::regular, 0644, 1517)},
      {"dev", make_stat(posix_file_type::directory, 0755, 2)},
      {"dev/null", make_stat(posix_file_type::character, 0666, 0)},
      {"dev/zero", make_stat(posix_file_type::character, 0666, 0)},
      {"empty", make_stat(posix_file_type::directory, 0755, 1)},
      {"empty/alsoempty", make_stat(posix_file_type::directory, 0755, 0)},
      {"foo", make_stat(posix_file_type::directory, 0755, 5)},
      {"foo/1", make_stat(posix_file_type::directory, 0755, 2)},
      {"foo/1/2", make_stat(posix_file_type::directory, 0755, 2)},
      {"foo/1/2/3", make_stat(posix_file_type::directory, 0755, 3)},
      {"foo/1/2/3/4", make_stat(posix_file_type::directory, 0755, 2)},
      {"foo/1/2/3/4/5", make_stat(posix_file_type::directory, 0755, 2)},
      {"foo/1/2/3/4/5/6", make_stat(posix_file_type::directory, 0755, 1)},
      {"foo/1/2/3/4/5/6/7", make_stat(posix_file_type::directory, 0755, 1)},
      {"foo/1/2/3/4/5/6/7/8", make_stat(posix_file_type::directory, 0755, 1)},
      {"foo/1/2/3/4/5/6/7/8/9",
       make_stat(posix_file_type::directory, 0755, 13)},
      {"foo/1/2/3/4/5/6/7/8/9/a", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/b", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/blubb",
       make_stat(posix_file_type::regular, 0644, 1517)},
      {"foo/1/2/3/4/5/6/7/8/9/c", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/d", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/e", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/f", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/g", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/h", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/i", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/j", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/k", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/6/7/8/9/l", make_stat(posix_file_type::regular, 0644, 2)},
      {"foo/1/2/3/4/5/z", make_stat(posix_file_type::regular, 0644, 1517)},
      {"foo/1/2/3/4/y", make_stat(posix_file_type::regular, 0644, 1517)},
      {"foo/1/2/3/copy.sh", make_stat(posix_file_type::regular, 0755, 94)},
      {"foo/1/2/3/x", make_stat(posix_file_type::regular, 0644, 1517)},
      {"foo/1/2/xxx.sh", make_stat(posix_file_type::regular, 0755, 94)},
      {"foo/1/fmt.sh", make_stat(posix_file_type::regular, 0755, 94)},
      {"foo/bad", make_stat(posix_file_type::symlink, 0777, 6)},
      {"foo/bar", make_stat(posix_file_type::regular, 0644, 0)},
      {"foo/bla.sh", make_stat(posix_file_type::regular, 0644, 1517)},
      {"foo/pipe", make_stat(posix_file_type::fifo, 0644, 0)},
      {"foobar", make_stat(posix_file_type::symlink, 0777, 7)},
      {"format.sh", make_stat(posix_file_type::regular, 0755, 94)},
      {"perl-exec.sh", make_stat(posix_file_type::regular, 0644, 87)},
      {"test.py", make_stat(posix_file_type::regular, 0644, 1012)},
  };

  if (!has_devices) {
    for (auto special : {"dev/null", "dev/zero", "foo/pipe"}) {
      ref_entries.erase(special);
    }
    ref_entries["dev"].size -= 2;
    ref_entries["foo"].size -= 1;
  }

  for (auto mp : {&filesystem_v2::walk, &filesystem_v2::walk_data_order}) {
    std::map<std::string, file_stat> entries;
    std::vector<int> inodes;

    (fs.*mp)([&](dir_entry_view e) {
      file_stat stbuf;
      ASSERT_EQ(0, fs.getattr(e.inode(), &stbuf));
      inodes.push_back(stbuf.ino);
      EXPECT_TRUE(entries.emplace(e.unix_path(), stbuf).second);
    });

    EXPECT_EQ(entries.size(), ref_entries.size());

    for (auto const& [p, st] : entries) {
      auto it = ref_entries.find(p);
      EXPECT_TRUE(it != ref_entries.end()) << p;
      if (it != ref_entries.end()) {
        EXPECT_EQ(it->second.mode, st.mode) << p;
        if (st.type() == posix_file_type::character) {
          EXPECT_EQ(0, st.uid) << p;
          EXPECT_EQ(0, st.gid) << p;
        } else {
          EXPECT_EQ(1000, st.uid) << p;
          EXPECT_EQ(100, st.gid) << p;
        }
        EXPECT_EQ(it->second.size, st.size) << p;
      }
    }
  }

  filesystem_extractor ext(lgr);
  std::ostringstream oss;

  EXPECT_NO_THROW(ext.open_stream(oss, "mtree"));
  EXPECT_NO_THROW(ext.extract(fs));
  EXPECT_NO_THROW(ext.close());

  std::istringstream iss(oss.str());
  std::string line;
  size_t num = 0;
  ref_entries.erase("");

  while (std::getline(iss, line, '\n')) {
    if (line == "#mtree") {
      continue;
    }

    std::vector<std::string> parts;
    folly::split(' ', line, parts);
    auto name = parts.front().substr(2);
    parts.erase(parts.begin());
    std::unordered_map<std::string, std::string> kv;

    for (auto const& p : parts) {
      std::string key, value;
      folly::split('=', p, key, value);
      kv[key] = value;
    }

    ++num;

    auto ri = ref_entries.find(name);
    EXPECT_FALSE(ri == ref_entries.end());

    if (ri != ref_entries.end()) {
      auto const& st = ri->second;

      EXPECT_EQ(kv["mode"], fmt::format("{0:o}", st.mode & 0777));
      EXPECT_EQ(std::stoi(kv["uid"]), kv["type"] == "char" ? 0 : 1000);
      EXPECT_EQ(std::stoi(kv["gid"]), kv["type"] == "char" ? 0 : 100);

      if (kv["type"] == "file") {
        EXPECT_EQ(std::stoi(kv["size"]), st.size);
      }
    }
  }

  EXPECT_EQ(ref_entries.size(), num);
}

} // namespace

class compat_metadata : public testing::TestWithParam<std::string> {};

void check_dynamic(std::string const& version, filesystem_v2 const& fs) {
  auto meta = fs.metadata_as_dynamic();
  folly::dynamic ref;
  if (version == "0.2.0" or version == "0.2.3") {
    ref = folly::parseJson(reference_v0_2);
  } else {
    ref = folly::parseJson(reference);
  }
  EXPECT_EQ(ref, meta);
}

TEST_P(compat_metadata, backwards_compat) {
  test::test_logger lgr;
  auto version = GetParam();
  auto filename = std::string(TEST_DATA_DIR "/compat-v") + version + ".dwarfs";
  filesystem_v2 fs(lgr, std::make_shared<mmap>(filename));
  check_dynamic(version, fs);
}

INSTANTIATE_TEST_SUITE_P(dwarfs, compat_metadata,
                         ::testing::ValuesIn(versions));

class compat_filesystem
    : public testing::TestWithParam<std::tuple<std::string, bool>> {};

TEST_P(compat_filesystem, backwards_compat) {
  auto [version, enable_nlink] = GetParam();

  test::test_logger lgr;
  auto filename = std::string(TEST_DATA_DIR "/compat-v") + version + ".dwarfs";

  filesystem_options opts;
  opts.metadata.enable_nlink = enable_nlink;
  opts.metadata.check_consistency = true;

  {
    filesystem_v2 fs(lgr, std::make_shared<mmap>(filename), opts);
    check_compat(lgr, fs, version);
  }

  opts.image_offset = filesystem_options::IMAGE_OFFSET_AUTO;

  std::string fsdata;
  ASSERT_TRUE(folly::readFile(filename.c_str(), fsdata));

  for (auto const& hdr : headers) {
    filesystem_v2 fs(lgr, std::make_shared<test::mmap_mock>(hdr + fsdata),
                     opts);
    check_compat(lgr, fs, version);
  }

  if (version != "0.2.0" and version != "0.2.3") {
    for (auto const& hdr : headers_v2) {
      filesystem_v2 fs(lgr, std::make_shared<test::mmap_mock>(hdr + fsdata),
                       opts);
      check_compat(lgr, fs, version);
    }
  }
}

INSTANTIATE_TEST_SUITE_P(dwarfs, compat_filesystem,
                         ::testing::Combine(::testing::ValuesIn(versions),
                                            ::testing::Bool()));

class rewrite
    : public testing::TestWithParam<std::tuple<std::string, bool, bool>> {};

TEST_P(rewrite, filesystem_rewrite) {
  auto [version, recompress_block, recompress_metadata] = GetParam();

  test::test_logger lgr;
  auto filename = std::string(TEST_DATA_DIR "/compat-v") + version + ".dwarfs";

  rewrite_options opts;
  opts.recompress_block = recompress_block;
  opts.recompress_metadata = recompress_metadata;

  worker_group wg("rewriter", 2);
  block_compressor bc("null");
  progress prog([](const progress&, bool) {}, 1000);
  std::ostringstream rewritten, idss;

  auto rewrite_fs = [&](auto& fsw, auto const& mm) {
    filesystem_options fsopts;
    fsopts.image_offset = filesystem_options::IMAGE_OFFSET_AUTO;
    filesystem_v2 fs(lgr, mm, fsopts);
    filesystem_block_category_resolver resolver(fs.get_all_block_categories());
    fs.rewrite(prog, fsw, resolver, opts);
  };

  {
    filesystem_writer fsw(rewritten, lgr, wg, prog, bc, bc, bc);
    fsw.add_default_compressor(bc);
    auto mm = std::make_shared<mmap>(filename);
    EXPECT_NO_THROW(filesystem_v2::identify(lgr, mm, idss));
    EXPECT_FALSE(filesystem_v2::header(mm));
    rewrite_fs(fsw, mm);
  }

  {
    auto mm = std::make_shared<test::mmap_mock>(rewritten.str());
    EXPECT_NO_THROW(filesystem_v2::identify(lgr, mm, idss));
    EXPECT_FALSE(filesystem_v2::header(mm));
    filesystem_v2 fs(lgr, mm);
    check_dynamic(version, fs);
  }

  rewritten.str(std::string());
  rewritten.clear();

  {
    std::istringstream hdr_iss(format_sh);
    filesystem_writer_options fsw_opts;
    filesystem_writer fsw(rewritten, lgr, wg, prog, bc, bc, bc, fsw_opts,
                          &hdr_iss);
    fsw.add_default_compressor(bc);
    rewrite_fs(fsw, std::make_shared<mmap>(filename));
  }

  {
    auto mm = std::make_shared<test::mmap_mock>(rewritten.str());
    EXPECT_NO_THROW(filesystem_v2::identify(
        lgr, mm, idss, 0, 1, false, filesystem_options::IMAGE_OFFSET_AUTO));
    auto hdr = filesystem_v2::header(mm);
    ASSERT_TRUE(hdr) << folly::hexDump(rewritten.str().data(),
                                       rewritten.str().size());
    EXPECT_EQ(format_sh, std::string(reinterpret_cast<char const*>(hdr->data()),
                                     hdr->size()));
    filesystem_options fsopts;
    fsopts.image_offset = filesystem_options::IMAGE_OFFSET_AUTO;
    filesystem_v2 fs(lgr, mm, fsopts);
    check_dynamic(version, fs);
  }

  std::ostringstream rewritten2;

  {
    std::istringstream hdr_iss("D");
    filesystem_writer_options fsw_opts;
    filesystem_writer fsw(rewritten2, lgr, wg, prog, bc, bc, bc, fsw_opts,
                          &hdr_iss);
    fsw.add_default_compressor(bc);
    rewrite_fs(fsw, std::make_shared<test::mmap_mock>(rewritten.str()));
  }

  {
    auto mm = std::make_shared<test::mmap_mock>(rewritten2.str());
    auto hdr = filesystem_v2::header(mm);
    ASSERT_TRUE(hdr) << folly::hexDump(rewritten2.str().data(),
                                       rewritten2.str().size());
    EXPECT_EQ("D", std::string(reinterpret_cast<char const*>(hdr->data()),
                               hdr->size()));
  }

  std::ostringstream rewritten3;

  {
    filesystem_writer fsw(rewritten3, lgr, wg, prog, bc, bc, bc);
    fsw.add_default_compressor(bc);
    rewrite_fs(fsw, std::make_shared<test::mmap_mock>(rewritten2.str()));
  }

  {
    auto mm = std::make_shared<test::mmap_mock>(rewritten3.str());
    auto hdr = filesystem_v2::header(mm);
    ASSERT_TRUE(hdr) << folly::hexDump(rewritten3.str().data(),
                                       rewritten3.str().size());
    EXPECT_EQ("D", std::string(reinterpret_cast<char const*>(hdr->data()),
                               hdr->size()));
  }

  std::ostringstream rewritten4;

  {
    filesystem_writer_options fsw_opts;
    fsw_opts.remove_header = true;
    filesystem_writer fsw(rewritten4, lgr, wg, prog, bc, bc, bc, fsw_opts);
    fsw.add_default_compressor(bc);
    rewrite_fs(fsw, std::make_shared<test::mmap_mock>(rewritten3.str()));
  }

  {
    auto mm = std::make_shared<test::mmap_mock>(rewritten4.str());
    EXPECT_NO_THROW(filesystem_v2::identify(lgr, mm, idss));
    EXPECT_FALSE(filesystem_v2::header(mm))
        << folly::hexDump(rewritten4.str().data(), rewritten4.str().size());
    filesystem_v2 fs(lgr, mm);
    check_dynamic(version, fs);
  }

  std::ostringstream rewritten5;

  {
    filesystem_writer_options fsw_opts;
    fsw_opts.no_section_index = true;
    filesystem_writer fsw(rewritten5, lgr, wg, prog, bc, bc, bc, fsw_opts);
    fsw.add_default_compressor(bc);
    rewrite_fs(fsw, std::make_shared<test::mmap_mock>(rewritten4.str()));
  }

  {
    auto mm = std::make_shared<test::mmap_mock>(rewritten5.str());
    EXPECT_NO_THROW(filesystem_v2::identify(lgr, mm, idss));
    EXPECT_FALSE(filesystem_v2::header(mm))
        << folly::hexDump(rewritten5.str().data(), rewritten5.str().size());
    filesystem_v2 fs(lgr, mm);
    check_dynamic(version, fs);
  }
}

INSTANTIATE_TEST_SUITE_P(dwarfs, rewrite,
                         ::testing::Combine(::testing::ValuesIn(versions),
                                            ::testing::Bool(),
                                            ::testing::Bool()));
