src/deps_log_test.cc - platform/external/ninja - Git at Google

 // Copyright 2012 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #include "deps_log.h"

 #include <sys/stat.h>
 #ifndef _WIN32
 #include <unistd.h>
 #endif

 #include "graph.h"
 #include "util.h"
 #include "test.h"

 namespace {

 const char kTestFilename[] = "DepsLogTest-tempfile";

 struct DepsLogTest : public testing::Test {
   virtual void SetUp() {
     // In case a crashing test left a stale file behind.
     unlink(kTestFilename);
   }
   virtual void TearDown() {
     unlink(kTestFilename);
   }
 };

 TEST_F(DepsLogTest, WriteRead) {
   State state1;
   DepsLog log1;
   string err;
   VirtualFileSystem fs;
   EXPECT_TRUE(log1.OpenForWrite(kTestFilename, fs, &err));
   ASSERT_EQ("", err);

   {
     vector<Node*> deps;
     deps.push_back(state1.GetNode("foo.h", 0));
     deps.push_back(state1.GetNode("bar.h", 0));
     log1.RecordDeps(state1.GetNode("out.o", 0), 1, deps);

     deps.clear();
     deps.push_back(state1.GetNode("foo.h", 0));
     deps.push_back(state1.GetNode("bar2.h", 0));
     log1.RecordDeps(state1.GetNode("out2.o", 0), 2, deps);

     DepsLog::Deps* log_deps = log1.GetDeps(state1.GetNode("out.o", 0));
     ASSERT_TRUE(log_deps);
     ASSERT_EQ(1, log_deps->mtime);
     ASSERT_EQ(2, log_deps->node_count);
     ASSERT_EQ("foo.h", log_deps->nodes[0]->path());
     ASSERT_EQ("bar.h", log_deps->nodes[1]->path());
   }

   log1.Close();

   State state2;
   DepsLog log2;
   EXPECT_TRUE(log2.Load(kTestFilename, &state2, &err));
   ASSERT_EQ("", err);

   ASSERT_EQ(log1.nodes().size(), log2.nodes().size());
   for (int i = 0; i < (int)log1.nodes().size(); ++i) {
     Node* node1 = log1.nodes()[i];
     Node* node2 = log2.nodes()[i];
     ASSERT_EQ(i, node1->id());
     ASSERT_EQ(node1->id(), node2->id());
   }

   // Spot-check the entries in log2.
   DepsLog::Deps* log_deps = log2.GetDeps(state2.GetNode("out2.o", 0));
   ASSERT_TRUE(log_deps);
   ASSERT_EQ(2, log_deps->mtime);
   ASSERT_EQ(2, log_deps->node_count);
   ASSERT_EQ("foo.h", log_deps->nodes[0]->path());
   ASSERT_EQ("bar2.h", log_deps->nodes[1]->path());
 }

 TEST_F(DepsLogTest, LotsOfDeps) {
   const int kNumDeps = 100000;  // More than 64k.

   State state1;
   DepsLog log1;
   string err;
   VirtualFileSystem fs;
   EXPECT_TRUE(log1.OpenForWrite(kTestFilename, fs, &err));
   ASSERT_EQ("", err);

   // The paths_ concurrent hash table doesn't automatically resize itself, so
   // reserve space in advance before synthesizing paths.
   state1.paths_.reserve(kNumDeps);

   {
     vector<Node*> deps;
     for (int i = 0; i < kNumDeps; ++i) {
       char buf[32];
       sprintf(buf, "file%d.h", i);
       deps.push_back(state1.GetNode(buf, 0));
     }
     log1.RecordDeps(state1.GetNode("out.o", 0), 1, deps);

     DepsLog::Deps* log_deps = log1.GetDeps(state1.GetNode("out.o", 0));
     ASSERT_EQ(kNumDeps, log_deps->node_count);
   }

   log1.Close();

   State state2;
   DepsLog log2;
   EXPECT_TRUE(log2.Load(kTestFilename, &state2, &err));
   ASSERT_EQ("", err);

   DepsLog::Deps* log_deps = log2.GetDeps(state2.GetNode("out.o", 0));
   ASSERT_EQ(kNumDeps, log_deps->node_count);
 }

 // Verify that adding the same deps twice doesn't grow the file.
 TEST_F(DepsLogTest, DoubleEntry) {
   // Write some deps to the file and grab its size.
   int file_size;
   {
     State state;
     DepsLog log;
     string err;
     VirtualFileSystem fs;
     EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
     ASSERT_EQ("", err);

     vector<Node*> deps;
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar.h", 0));
     log.RecordDeps(state.GetNode("out.o", 0), 1, deps);
     log.Close();

     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
     file_size = (int)st.st_size;
     ASSERT_GT(file_size, 0);
   }

   // Now reload the file, and read the same deps.
   {
     State state;
     DepsLog log;
     string err;
     VirtualFileSystem fs;
     EXPECT_TRUE(log.Load(kTestFilename, &state, &err));

     EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
     ASSERT_EQ("", err);

     vector<Node*> deps;
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar.h", 0));
     log.RecordDeps(state.GetNode("out.o", 0), 1, deps);
     log.Close();

     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
     int file_size_2 = (int)st.st_size;
     ASSERT_EQ(file_size, file_size_2);
   }
 }

 // Verify that adding the new deps works and can be compacted away.
 TEST_F(DepsLogTest, Recompact) {
   const char kManifest[] =
 "rule cc\n"
 "  command = cc\n"
 "  deps = gcc\n"
 "build out.o: cc\n"
 "build other_out.o: cc\n";

   // Write some deps to the file and grab its size.
   int file_size;
   {
     State state;
     ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
     DepsLog log;
     string err;
     VirtualFileSystem fs;
     ASSERT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
     ASSERT_EQ("", err);

     vector<Node*> deps;
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar.h", 0));
     log.RecordDeps(state.GetNode("out.o", 0), 1, deps);

     deps.clear();
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("baz.h", 0));
     log.RecordDeps(state.GetNode("other_out.o", 0), 1, deps);

     log.Close();

     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
     file_size = (int)st.st_size;
     ASSERT_GT(file_size, 0);
   }

   // Now reload the file, and add slightly different deps.
   int file_size_2;
   {
     State state;
     ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
     DepsLog log;
     string err;
     VirtualFileSystem fs;
     ASSERT_TRUE(log.Load(kTestFilename, &state, &err));

     ASSERT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
     ASSERT_EQ("", err);

     vector<Node*> deps;
     deps.push_back(state.GetNode("foo.h", 0));
     log.RecordDeps(state.GetNode("out.o", 0), 1, deps);
     log.Close();

     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
     file_size_2 = (int)st.st_size;
     // The file should grow to record the new deps.
     ASSERT_GT(file_size_2, file_size);
   }

   // Now reload the file, verify the new deps have replaced the old, then
   // recompact.
   int file_size_3;
   {
     State state;
     ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
     DepsLog log;
     string err;
     ASSERT_TRUE(log.Load(kTestFilename, &state, &err));

     Node* out = state.GetNode("out.o", 0);
     DepsLog::Deps* deps = log.GetDeps(out);
     ASSERT_TRUE(deps);
     ASSERT_EQ(1, deps->mtime);
     ASSERT_EQ(1, deps->node_count);
     ASSERT_EQ("foo.h", deps->nodes[0]->path());

     Node* other_out = state.GetNode("other_out.o", 0);
     deps = log.GetDeps(other_out);
     ASSERT_TRUE(deps);
     ASSERT_EQ(1, deps->mtime);
     ASSERT_EQ(2, deps->node_count);
     ASSERT_EQ("foo.h", deps->nodes[0]->path());
     ASSERT_EQ("baz.h", deps->nodes[1]->path());

     VirtualFileSystem fs;
     ASSERT_TRUE(log.Recompact(kTestFilename, fs, &err));

     // The in-memory deps graph should still be valid after recompaction.
     deps = log.GetDeps(out);
     ASSERT_TRUE(deps);
     ASSERT_EQ(1, deps->mtime);
     ASSERT_EQ(1, deps->node_count);
     ASSERT_EQ("foo.h", deps->nodes[0]->path());
     ASSERT_EQ(out, log.nodes()[out->id()]);

     deps = log.GetDeps(other_out);
     ASSERT_TRUE(deps);
     ASSERT_EQ(1, deps->mtime);
     ASSERT_EQ(2, deps->node_count);
     ASSERT_EQ("foo.h", deps->nodes[0]->path());
     ASSERT_EQ("baz.h", deps->nodes[1]->path());
     ASSERT_EQ(other_out, log.nodes()[other_out->id()]);

     // The file should have shrunk a bit for the smaller deps.
     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
     file_size_3 = (int)st.st_size;
     ASSERT_LT(file_size_3, file_size_2);
   }

   // Now reload the file and recompact with an empty manifest. The previous
   // entries should be removed.
   {
     State state;
     // Intentionally not parsing kManifest here.
     DepsLog log;
     string err;
     ASSERT_TRUE(log.Load(kTestFilename, &state, &err));

     Node* out = state.GetNode("out.o", 0);
     DepsLog::Deps* deps = log.GetDeps(out);
     ASSERT_TRUE(deps);
     ASSERT_EQ(1, deps->mtime);
     ASSERT_EQ(1, deps->node_count);
     ASSERT_EQ("foo.h", deps->nodes[0]->path());

     Node* other_out = state.GetNode("other_out.o", 0);
     deps = log.GetDeps(other_out);
     ASSERT_TRUE(deps);
     ASSERT_EQ(1, deps->mtime);
     ASSERT_EQ(2, deps->node_count);
     ASSERT_EQ("foo.h", deps->nodes[0]->path());
     ASSERT_EQ("baz.h", deps->nodes[1]->path());

     // Keep out.o dependencies.
     VirtualFileSystem fs;
     fs.Create("out.o", "");

     ASSERT_TRUE(log.Recompact(kTestFilename, fs, &err));

     deps = log.GetDeps(out);
     ASSERT_TRUE(deps);
     ASSERT_EQ(1, deps->mtime);
     ASSERT_EQ(1, deps->node_count);
     ASSERT_EQ("foo.h", deps->nodes[0]->path());
     ASSERT_EQ(out, log.nodes()[out->id()]);

     // The previous entries should have been removed.
     deps = log.GetDeps(other_out);
     ASSERT_FALSE(deps);

     //ASSERT_EQ(-1, state.LookupNode("foo.h")->id());
     // The .h files pulled in via deps should no longer have ids either.
     ASSERT_EQ(-1, state.LookupNode("baz.h")->id());

     // The file should have shrunk more.
     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
     int file_size_4 = (int)st.st_size;
     ASSERT_LT(file_size_4, file_size_3);
   }
 }

 // Verify that invalid file headers cause a new build.
 TEST_F(DepsLogTest, InvalidHeader) {
   const char *kInvalidHeaders[] = {
     "",                              // Empty file.
     "# ninjad",                      // Truncated first line.
     "# ninjadeps\n",                 // No version int.
     "# ninjadeps\n\001\002",         // Truncated version int.
     "# ninjadeps\n\001\002\003\004"  // Invalid version int.
   };
   for (size_t i = 0; i < sizeof(kInvalidHeaders) / sizeof(kInvalidHeaders[0]);
        ++i) {
     FILE* deps_log = fopen(kTestFilename, "wb");
     ASSERT_TRUE(deps_log != NULL);
     ASSERT_EQ(
         strlen(kInvalidHeaders[i]),
         fwrite(kInvalidHeaders[i], 1, strlen(kInvalidHeaders[i]), deps_log));
     ASSERT_EQ(0 ,fclose(deps_log));

     string err;
     DepsLog log;
     State state;
     ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
     EXPECT_EQ("bad deps log signature or version; starting over", err);
   }
 }

 // Simulate what happens when loading a truncated log file.
 TEST_F(DepsLogTest, Truncated) {
   // Create a file with some entries.
   {
     State state;
     DepsLog log;
     string err;
     VirtualFileSystem fs;
     EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
     ASSERT_EQ("", err);

     vector<Node*> deps;
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar.h", 0));
     log.RecordDeps(state.GetNode("out.o", 0), 1, deps);

     deps.clear();
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar2.h", 0));
     log.RecordDeps(state.GetNode("out2.o", 0), 2, deps);

     log.Close();
   }

   // Get the file size.
   struct stat st;
   ASSERT_EQ(0, stat(kTestFilename, &st));

   // Try reloading at truncated sizes.
   // Track how many nodes/deps were found; they should decrease with
   // smaller sizes.
   int node_count = 5;
   int deps_count = 2;
   for (int size = (int)st.st_size; size > 0; --size) {
     string err;
     ASSERT_TRUE(Truncate(kTestFilename, size, &err));

     State state;
     DepsLog log;
     EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
     if (!err.empty()) {
       // At some point the log will be so short as to be unparseable.
       break;
     }

     ASSERT_GE(node_count, (int)log.nodes().size());
     node_count = log.nodes().size();

     // Count how many non-NULL deps entries there are.
     int new_deps_count = 0;
     for (vector<DepsLog::Deps*>::const_iterator i = log.deps().begin();
          i != log.deps().end(); ++i) {
       if (*i)
         ++new_deps_count;
     }
     ASSERT_GE(deps_count, new_deps_count);
     deps_count = new_deps_count;
   }
 }

 // Run the truncation-recovery logic.
 TEST_F(DepsLogTest, TruncatedRecovery) {
   // Create a file with some entries.
   {
     State state;
     DepsLog log;
     string err;
     VirtualFileSystem fs;
     EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
     ASSERT_EQ("", err);

     vector<Node*> deps;
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar.h", 0));
     log.RecordDeps(state.GetNode("out.o", 0), 1, deps);

     deps.clear();
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar2.h", 0));
     log.RecordDeps(state.GetNode("out2.o", 0), 2, deps);

     log.Close();
   }

   // Shorten the file, corrupting the last record.
   {
     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
     string err;
     ASSERT_TRUE(Truncate(kTestFilename, st.st_size - 2, &err));
   }

   // Load the file again, add an entry.
   {
     State state;
     DepsLog log;
     string err;
     EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
     ASSERT_EQ("premature end of file; recovering", err);
     err.clear();

     // The truncated entry should've been discarded.
     EXPECT_EQ(NULL, log.GetDeps(state.GetNode("out2.o", 0)));

     VirtualFileSystem fs;
     EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
     ASSERT_EQ("", err);

     // Add a new entry.
     vector<Node*> deps;
     deps.push_back(state.GetNode("foo.h", 0));
     deps.push_back(state.GetNode("bar2.h", 0));
     log.RecordDeps(state.GetNode("out2.o", 0), 3, deps);

     log.Close();
   }

   // Load the file a third time to verify appending after a mangled
   // entry doesn't break things.
   {
     State state;
     DepsLog log;
     string err;
     EXPECT_TRUE(log.Load(kTestFilename, &state, &err));

     // The truncated entry should exist.
     DepsLog::Deps* deps = log.GetDeps(state.GetNode("out2.o", 0));
     ASSERT_TRUE(deps);
   }
 }

 template <typename Func>
 static void DoLoadInvalidLogTest(Func&& func) {
   State state;
   DepsLog log;
   std::string err;
   ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
   ASSERT_EQ("premature end of file; recovering", err);
   func(&state, &log);
 }

 TEST_F(DepsLogTest, LoadInvalidLog) {
   struct Item {
     Item(int num) : is_num(true), num(num) {}
     Item(const char* str) : is_num(false), str(str) {}

     bool is_num;
     uint32_t num;
     const char* str;
   };

   auto write_file = [](std::vector<Item> items) {
     FILE* fp = fopen(kTestFilename, "wb");
     for (const Item& item : items) {
       if (item.is_num) {
         ASSERT_EQ(1, fwrite(&item.num, sizeof(item.num), 1, fp));
       } else {
         ASSERT_EQ(strlen(item.str), fwrite(item.str, 1, strlen(item.str), fp));
       }
     }
     fclose(fp);
   };

   const int kCurrentVersion = 4;
   auto path_hdr = [](int path_len) -> int {
     return RoundUp(path_len, 4) + 4;
   };
   auto deps_hdr = [](int deps_cnt) -> int {
     return 0x80000000 | ((3 * sizeof(uint32_t)) + (deps_cnt * 4));
   };

   write_file({
     "# ninjadeps\n", kCurrentVersion,
     path_hdr(4), "foo0", ~0, // node #0
     path_hdr(4), "foo1", ~2, // invalid path ID
   });
   DoLoadInvalidLogTest([](State* state, DepsLog* log) {
     ASSERT_EQ(0, state->LookupNode("foo0")->id());
     ASSERT_EQ(nullptr, state->LookupNode("foo1"));
   });

   write_file({
     "# ninjadeps\n", kCurrentVersion,
     path_hdr(4), "foo0", ~0, // node #0
     deps_hdr(1), /*node*/0, /*mtime*/5, 0, /*node*/1, // invalid src ID
     path_hdr(4), "foo1", ~1, // node #1
   });
   DoLoadInvalidLogTest([](State* state, DepsLog* log) {
     ASSERT_EQ(0, state->LookupNode("foo0")->id());
     ASSERT_EQ(nullptr, log->GetDeps(state->LookupNode("foo0")));
     ASSERT_EQ(nullptr, state->LookupNode("foo1"));
   });

   write_file({
     "# ninjadeps\n", kCurrentVersion,
     path_hdr(4), "foo0", ~0, // node #0
     deps_hdr(1), /*node*/1, /*mtime*/5, 0, /*node*/0, // invalid out ID
     path_hdr(4), "foo1", ~1, // node #1
   });
   DoLoadInvalidLogTest([](State* state, DepsLog* log) {
     ASSERT_EQ(0, state->LookupNode("foo0")->id());
     ASSERT_EQ(nullptr, state->LookupNode("foo1"));
   });

   write_file({
     "# ninjadeps\n", kCurrentVersion,
     path_hdr(4), "foo0", ~0, // node #0
     path_hdr(4), "foo1", ~1, // node #1
     path_hdr(4), "foo2", ~2, // node #2
     deps_hdr(1), /*node*/2, /*mtime*/5, 0, /*node*/1,
     deps_hdr(1), /*node*/2, /*mtime*/6, 0, /*node*/3, // invalid src ID

     // No records after the invalid record are parsed.
     path_hdr(4), "foo3", ~3, // node #3
     deps_hdr(1), /*node*/3, /*mtime*/7, 0, /*node*/0,
     path_hdr(4), "foo4", ~4, // node #4
     deps_hdr(1), /*node*/4, /*mtime*/8, 0, /*node*/0,

     // Truncation must be handled before looking for the last deps record
     // that outputs a given node.
     deps_hdr(1), /*node*/2, /*mtime*/9, 0, /*node*/0,
     deps_hdr(1), /*node*/2, /*mtime*/9, 0, /*node*/3,
   });
   DoLoadInvalidLogTest([](State* state, DepsLog* log) {
     ASSERT_EQ(0, state->LookupNode("foo0")->id());
     ASSERT_EQ(1, state->LookupNode("foo1")->id());
     ASSERT_EQ(2, state->LookupNode("foo2")->id());
     ASSERT_EQ(nullptr, state->LookupNode("foo3"));
     ASSERT_EQ(nullptr, state->LookupNode("foo4"));

     ASSERT_EQ(nullptr, log->GetDeps(state->LookupNode("foo1")));

     DepsLog::Deps* deps = log->GetDeps(state->LookupNode("foo2"));
     ASSERT_EQ(5, deps->mtime);
     ASSERT_EQ(1, deps->node_count);
     ASSERT_EQ(1, deps->nodes[0]->id());
   });
 }

 TEST_F(DepsLogTest, MustBeDepsRecordHeader) {
   // Mark a word as a candidate.
   static constexpr uint64_t kCandidate = 0x100000000;

   // Verifies that MustBeDepsRecordHeader returns the expected value. Returns
   // true on success.
   auto do_test = [](std::vector<uint64_t> words) -> bool {
     std::vector<uint32_t> data;
     for (uint64_t word : words) {
       // Coerce from uint64_t to uint32_t to mask off the kCandidate flag.
       data.push_back(word);
     }
     DepsLogData log;
     log.words = data.data();
     log.size = data.size();
     for (size_t i = 0; i < words.size(); ++i) {
       const bool expected = (words[i] & kCandidate) == kCandidate;
       if (expected != MustBeDepsRecordHeader(log, i)) {
         printf("\n%s,%d: bad index: %zu\n", __FILE__, __LINE__, i);
         return false;
       }
     }
     return true;
   };

   // Two valid deps records with no dependencies. Each record's header is
   // recognized as the start of a deps record. The first record has an mtime_hi
   // from 2262.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x8000000c|kCandidate,  1,          2,          0x80000100,
     0x8000000c|kCandidate,  3,          4,          5,
   }));

   // The first record's mtime_lo is within a 524us window. The second record's
   // header looks like a potential mtime_lo for 0x8007fffc.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x8000000c|kCandidate,  1,          0x8007fffc, 2,
     0x8000000c,             3,          4,          5,
   }));

   // 0x80080000 is above the maximum record size, so it is rejected as a
   // possible header.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x8000000c|kCandidate,  1,          0x80080000, 2,
     0x8000000c|kCandidate,  3,          4,          5,
   }));

   // Two deps records with >16K inputs each. The header could be confused with a
   // path string containing control characters, so it's not a candidate.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x80010101,             1,          2,          3,    // input IDs elided...
     0x80010101,             4,          5,          6,    // input IDs elided...
   }));

   // The first record has a single dependency and an mtime_hi from 2262. The
   // second deps record's header looks like a potential mtime_lo for 0x80000100.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x80000010|kCandidate,  1,          2,          0x80000100, 3,
     0x8000000c,             4,          5,          6,
   }));

   // The first deps record's mtime_lo is within a 524us window, and the second
   // record's header looks like a potential mtime_hi for 0x80000100.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x80000010|kCandidate,  1,          0x80000100, 2,          3,
     0x8000000c,             4,          5,          6,
   }));

   // The first record has two dependencies, so its mtime_lo doesn't disqualify
   // the next record's header.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x80000014|kCandidate,  1,          0x80000100, 2,          3,          4,
     0x8000000c|kCandidate,  5,          6,          7,
   }));

   // The first deps record's mtime_hi is from 2262, and the second record's
   // header looks like a potential mtime_hi for 0x80000100.
   EXPECT_TRUE(do_test({
     // header               output_id   mtime_lo    mtime_hi
     0x80000014|kCandidate,  1,          2,          0x80000100, 3,          4,
     0x8000000c,             5,          6,          7,
   }));
 }

 }  // anonymous namespace
	// Copyright 2012 Google Inc. All Rights Reserved.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#include "deps_log.h"

	#include <sys/stat.h>
	#ifndef _WIN32
	#include <unistd.h>
	#endif

	#include "graph.h"
	#include "util.h"
	#include "test.h"

	namespace {

	const char kTestFilename[] = "DepsLogTest-tempfile";

	struct DepsLogTest : public testing::Test {
	virtual void SetUp() {
	// In case a crashing test left a stale file behind.
	unlink(kTestFilename);
	}
	virtual void TearDown() {
	unlink(kTestFilename);
	}
	};

	TEST_F(DepsLogTest, WriteRead) {
	State state1;
	DepsLog log1;
	string err;
	VirtualFileSystem fs;
	EXPECT_TRUE(log1.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	{
	vector<Node*> deps;
	deps.push_back(state1.GetNode("foo.h", 0));
	deps.push_back(state1.GetNode("bar.h", 0));
	log1.RecordDeps(state1.GetNode("out.o", 0), 1, deps);

	deps.clear();
	deps.push_back(state1.GetNode("foo.h", 0));
	deps.push_back(state1.GetNode("bar2.h", 0));
	log1.RecordDeps(state1.GetNode("out2.o", 0), 2, deps);

	DepsLog::Deps* log_deps = log1.GetDeps(state1.GetNode("out.o", 0));
	ASSERT_TRUE(log_deps);
	ASSERT_EQ(1, log_deps->mtime);
	ASSERT_EQ(2, log_deps->node_count);
	ASSERT_EQ("foo.h", log_deps->nodes[0]->path());
	ASSERT_EQ("bar.h", log_deps->nodes[1]->path());
	}

	log1.Close();

	State state2;
	DepsLog log2;
	EXPECT_TRUE(log2.Load(kTestFilename, &state2, &err));
	ASSERT_EQ("", err);

	ASSERT_EQ(log1.nodes().size(), log2.nodes().size());
	for (int i = 0; i < (int)log1.nodes().size(); ++i) {
	Node* node1 = log1.nodes()[i];
	Node* node2 = log2.nodes()[i];
	ASSERT_EQ(i, node1->id());
	ASSERT_EQ(node1->id(), node2->id());
	}

	// Spot-check the entries in log2.
	DepsLog::Deps* log_deps = log2.GetDeps(state2.GetNode("out2.o", 0));
	ASSERT_TRUE(log_deps);
	ASSERT_EQ(2, log_deps->mtime);
	ASSERT_EQ(2, log_deps->node_count);
	ASSERT_EQ("foo.h", log_deps->nodes[0]->path());
	ASSERT_EQ("bar2.h", log_deps->nodes[1]->path());
	}

	TEST_F(DepsLogTest, LotsOfDeps) {
	const int kNumDeps = 100000; // More than 64k.

	State state1;
	DepsLog log1;
	string err;
	VirtualFileSystem fs;
	EXPECT_TRUE(log1.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	// The paths_ concurrent hash table doesn't automatically resize itself, so
	// reserve space in advance before synthesizing paths.
	state1.paths_.reserve(kNumDeps);

	{
	vector<Node*> deps;
	for (int i = 0; i < kNumDeps; ++i) {
	char buf[32];
	sprintf(buf, "file%d.h", i);
	deps.push_back(state1.GetNode(buf, 0));
	}
	log1.RecordDeps(state1.GetNode("out.o", 0), 1, deps);

	DepsLog::Deps* log_deps = log1.GetDeps(state1.GetNode("out.o", 0));
	ASSERT_EQ(kNumDeps, log_deps->node_count);
	}

	log1.Close();

	State state2;
	DepsLog log2;
	EXPECT_TRUE(log2.Load(kTestFilename, &state2, &err));
	ASSERT_EQ("", err);

	DepsLog::Deps* log_deps = log2.GetDeps(state2.GetNode("out.o", 0));
	ASSERT_EQ(kNumDeps, log_deps->node_count);
	}

	// Verify that adding the same deps twice doesn't grow the file.
	TEST_F(DepsLogTest, DoubleEntry) {
	// Write some deps to the file and grab its size.
	int file_size;
	{
	State state;
	DepsLog log;
	string err;
	VirtualFileSystem fs;
	EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	vector<Node*> deps;
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar.h", 0));
	log.RecordDeps(state.GetNode("out.o", 0), 1, deps);
	log.Close();

	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));
	file_size = (int)st.st_size;
	ASSERT_GT(file_size, 0);
	}

	// Now reload the file, and read the same deps.
	{
	State state;
	DepsLog log;
	string err;
	VirtualFileSystem fs;
	EXPECT_TRUE(log.Load(kTestFilename, &state, &err));

	EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	vector<Node*> deps;
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar.h", 0));
	log.RecordDeps(state.GetNode("out.o", 0), 1, deps);
	log.Close();

	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));
	int file_size_2 = (int)st.st_size;
	ASSERT_EQ(file_size, file_size_2);
	}
	}

	// Verify that adding the new deps works and can be compacted away.
	TEST_F(DepsLogTest, Recompact) {
	const char kManifest[] =
	"rule cc\n"
	" command = cc\n"
	" deps = gcc\n"
	"build out.o: cc\n"
	"build other_out.o: cc\n";

	// Write some deps to the file and grab its size.
	int file_size;
	{
	State state;
	ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
	DepsLog log;
	string err;
	VirtualFileSystem fs;
	ASSERT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	vector<Node*> deps;
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar.h", 0));
	log.RecordDeps(state.GetNode("out.o", 0), 1, deps);

	deps.clear();
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("baz.h", 0));
	log.RecordDeps(state.GetNode("other_out.o", 0), 1, deps);

	log.Close();

	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));
	file_size = (int)st.st_size;
	ASSERT_GT(file_size, 0);
	}

	// Now reload the file, and add slightly different deps.
	int file_size_2;
	{
	State state;
	ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
	DepsLog log;
	string err;
	VirtualFileSystem fs;
	ASSERT_TRUE(log.Load(kTestFilename, &state, &err));

	ASSERT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	vector<Node*> deps;
	deps.push_back(state.GetNode("foo.h", 0));
	log.RecordDeps(state.GetNode("out.o", 0), 1, deps);
	log.Close();

	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));
	file_size_2 = (int)st.st_size;
	// The file should grow to record the new deps.
	ASSERT_GT(file_size_2, file_size);
	}

	// Now reload the file, verify the new deps have replaced the old, then
	// recompact.
	int file_size_3;
	{
	State state;
	ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
	DepsLog log;
	string err;
	ASSERT_TRUE(log.Load(kTestFilename, &state, &err));

	Node* out = state.GetNode("out.o", 0);
	DepsLog::Deps* deps = log.GetDeps(out);
	ASSERT_TRUE(deps);
	ASSERT_EQ(1, deps->mtime);
	ASSERT_EQ(1, deps->node_count);
	ASSERT_EQ("foo.h", deps->nodes[0]->path());

	Node* other_out = state.GetNode("other_out.o", 0);
	deps = log.GetDeps(other_out);
	ASSERT_TRUE(deps);
	ASSERT_EQ(1, deps->mtime);
	ASSERT_EQ(2, deps->node_count);
	ASSERT_EQ("foo.h", deps->nodes[0]->path());
	ASSERT_EQ("baz.h", deps->nodes[1]->path());

	VirtualFileSystem fs;
	ASSERT_TRUE(log.Recompact(kTestFilename, fs, &err));

	// The in-memory deps graph should still be valid after recompaction.
	deps = log.GetDeps(out);
	ASSERT_TRUE(deps);
	ASSERT_EQ(1, deps->mtime);
	ASSERT_EQ(1, deps->node_count);
	ASSERT_EQ("foo.h", deps->nodes[0]->path());
	ASSERT_EQ(out, log.nodes()[out->id()]);

	deps = log.GetDeps(other_out);
	ASSERT_TRUE(deps);
	ASSERT_EQ(1, deps->mtime);
	ASSERT_EQ(2, deps->node_count);
	ASSERT_EQ("foo.h", deps->nodes[0]->path());
	ASSERT_EQ("baz.h", deps->nodes[1]->path());
	ASSERT_EQ(other_out, log.nodes()[other_out->id()]);

	// The file should have shrunk a bit for the smaller deps.
	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));
	file_size_3 = (int)st.st_size;
	ASSERT_LT(file_size_3, file_size_2);
	}

	// Now reload the file and recompact with an empty manifest. The previous
	// entries should be removed.
	{
	State state;
	// Intentionally not parsing kManifest here.
	DepsLog log;
	string err;
	ASSERT_TRUE(log.Load(kTestFilename, &state, &err));

	Node* out = state.GetNode("out.o", 0);
	DepsLog::Deps* deps = log.GetDeps(out);
	ASSERT_TRUE(deps);
	ASSERT_EQ(1, deps->mtime);
	ASSERT_EQ(1, deps->node_count);
	ASSERT_EQ("foo.h", deps->nodes[0]->path());

	Node* other_out = state.GetNode("other_out.o", 0);
	deps = log.GetDeps(other_out);
	ASSERT_TRUE(deps);
	ASSERT_EQ(1, deps->mtime);
	ASSERT_EQ(2, deps->node_count);
	ASSERT_EQ("foo.h", deps->nodes[0]->path());
	ASSERT_EQ("baz.h", deps->nodes[1]->path());

	// Keep out.o dependencies.
	VirtualFileSystem fs;
	fs.Create("out.o", "");

	ASSERT_TRUE(log.Recompact(kTestFilename, fs, &err));

	deps = log.GetDeps(out);
	ASSERT_TRUE(deps);
	ASSERT_EQ(1, deps->mtime);
	ASSERT_EQ(1, deps->node_count);
	ASSERT_EQ("foo.h", deps->nodes[0]->path());
	ASSERT_EQ(out, log.nodes()[out->id()]);

	// The previous entries should have been removed.
	deps = log.GetDeps(other_out);
	ASSERT_FALSE(deps);

	//ASSERT_EQ(-1, state.LookupNode("foo.h")->id());
	// The .h files pulled in via deps should no longer have ids either.
	ASSERT_EQ(-1, state.LookupNode("baz.h")->id());

	// The file should have shrunk more.
	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));
	int file_size_4 = (int)st.st_size;
	ASSERT_LT(file_size_4, file_size_3);
	}
	}

	// Verify that invalid file headers cause a new build.
	TEST_F(DepsLogTest, InvalidHeader) {
	const char *kInvalidHeaders[] = {
	"", // Empty file.
	"# ninjad", // Truncated first line.
	"# ninjadeps\n", // No version int.
	"# ninjadeps\n\001\002", // Truncated version int.
	"# ninjadeps\n\001\002\003\004" // Invalid version int.
	};
	for (size_t i = 0; i < sizeof(kInvalidHeaders) / sizeof(kInvalidHeaders[0]);
	++i) {
	FILE* deps_log = fopen(kTestFilename, "wb");
	ASSERT_TRUE(deps_log != NULL);
	ASSERT_EQ(
	strlen(kInvalidHeaders[i]),
	fwrite(kInvalidHeaders[i], 1, strlen(kInvalidHeaders[i]), deps_log));
	ASSERT_EQ(0 ,fclose(deps_log));

	string err;
	DepsLog log;
	State state;
	ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
	EXPECT_EQ("bad deps log signature or version; starting over", err);
	}
	}

	// Simulate what happens when loading a truncated log file.
	TEST_F(DepsLogTest, Truncated) {
	// Create a file with some entries.
	{
	State state;
	DepsLog log;
	string err;
	VirtualFileSystem fs;
	EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	vector<Node*> deps;
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar.h", 0));
	log.RecordDeps(state.GetNode("out.o", 0), 1, deps);

	deps.clear();
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar2.h", 0));
	log.RecordDeps(state.GetNode("out2.o", 0), 2, deps);

	log.Close();
	}

	// Get the file size.
	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));

	// Try reloading at truncated sizes.
	// Track how many nodes/deps were found; they should decrease with
	// smaller sizes.
	int node_count = 5;
	int deps_count = 2;
	for (int size = (int)st.st_size; size > 0; --size) {
	string err;
	ASSERT_TRUE(Truncate(kTestFilename, size, &err));

	State state;
	DepsLog log;
	EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
	if (!err.empty()) {
	// At some point the log will be so short as to be unparseable.
	break;
	}

	ASSERT_GE(node_count, (int)log.nodes().size());
	node_count = log.nodes().size();

	// Count how many non-NULL deps entries there are.
	int new_deps_count = 0;
	for (vector<DepsLog::Deps*>::const_iterator i = log.deps().begin();
	i != log.deps().end(); ++i) {
	if (*i)
	++new_deps_count;
	}
	ASSERT_GE(deps_count, new_deps_count);
	deps_count = new_deps_count;
	}
	}

	// Run the truncation-recovery logic.
	TEST_F(DepsLogTest, TruncatedRecovery) {
	// Create a file with some entries.
	{
	State state;
	DepsLog log;
	string err;
	VirtualFileSystem fs;
	EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	vector<Node*> deps;
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar.h", 0));
	log.RecordDeps(state.GetNode("out.o", 0), 1, deps);

	deps.clear();
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar2.h", 0));
	log.RecordDeps(state.GetNode("out2.o", 0), 2, deps);

	log.Close();
	}

	// Shorten the file, corrupting the last record.
	{
	struct stat st;
	ASSERT_EQ(0, stat(kTestFilename, &st));
	string err;
	ASSERT_TRUE(Truncate(kTestFilename, st.st_size - 2, &err));
	}

	// Load the file again, add an entry.
	{
	State state;
	DepsLog log;
	string err;
	EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
	ASSERT_EQ("premature end of file; recovering", err);
	err.clear();

	// The truncated entry should've been discarded.
	EXPECT_EQ(NULL, log.GetDeps(state.GetNode("out2.o", 0)));

	VirtualFileSystem fs;
	EXPECT_TRUE(log.OpenForWrite(kTestFilename, fs, &err));
	ASSERT_EQ("", err);

	// Add a new entry.
	vector<Node*> deps;
	deps.push_back(state.GetNode("foo.h", 0));
	deps.push_back(state.GetNode("bar2.h", 0));
	log.RecordDeps(state.GetNode("out2.o", 0), 3, deps);

	log.Close();
	}

	// Load the file a third time to verify appending after a mangled
	// entry doesn't break things.
	{
	State state;
	DepsLog log;
	string err;
	EXPECT_TRUE(log.Load(kTestFilename, &state, &err));

	// The truncated entry should exist.
	DepsLog::Deps* deps = log.GetDeps(state.GetNode("out2.o", 0));
	ASSERT_TRUE(deps);
	}
	}

	template <typename Func>
	static void DoLoadInvalidLogTest(Func&& func) {
	State state;
	DepsLog log;
	std::string err;
	ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
	ASSERT_EQ("premature end of file; recovering", err);
	func(&state, &log);
	}

	TEST_F(DepsLogTest, LoadInvalidLog) {
	struct Item {
	Item(int num) : is_num(true), num(num) {}
	Item(const char* str) : is_num(false), str(str) {}

	bool is_num;
	uint32_t num;
	const char* str;
	};

	auto write_file = [](std::vector<Item> items) {
	FILE* fp = fopen(kTestFilename, "wb");
	for (const Item& item : items) {
	if (item.is_num) {
	ASSERT_EQ(1, fwrite(&item.num, sizeof(item.num), 1, fp));
	} else {
	ASSERT_EQ(strlen(item.str), fwrite(item.str, 1, strlen(item.str), fp));
	}
	}
	fclose(fp);
	};

	const int kCurrentVersion = 4;
	auto path_hdr = [](int path_len) -> int {
	return RoundUp(path_len, 4) + 4;
	};
	auto deps_hdr = [](int deps_cnt) -> int {
	return 0x80000000 \| ((3 * sizeof(uint32_t)) + (deps_cnt * 4));
	};

	write_file({
	"# ninjadeps\n", kCurrentVersion,
	path_hdr(4), "foo0", ~0, // node #0
	path_hdr(4), "foo1", ~2, // invalid path ID
	});
	DoLoadInvalidLogTest([](State* state, DepsLog* log) {
	ASSERT_EQ(0, state->LookupNode("foo0")->id());
	ASSERT_EQ(nullptr, state->LookupNode("foo1"));
	});

	write_file({
	"# ninjadeps\n", kCurrentVersion,
	path_hdr(4), "foo0", ~0, // node #0
	deps_hdr(1), /node/0, /mtime/5, 0, /node/1, // invalid src ID
	path_hdr(4), "foo1", ~1, // node #1
	});
	DoLoadInvalidLogTest([](State* state, DepsLog* log) {
	ASSERT_EQ(0, state->LookupNode("foo0")->id());
	ASSERT_EQ(nullptr, log->GetDeps(state->LookupNode("foo0")));
	ASSERT_EQ(nullptr, state->LookupNode("foo1"));
	});

	write_file({
	"# ninjadeps\n", kCurrentVersion,
	path_hdr(4), "foo0", ~0, // node #0
	deps_hdr(1), /node/1, /mtime/5, 0, /node/0, // invalid out ID
	path_hdr(4), "foo1", ~1, // node #1
	});
	DoLoadInvalidLogTest([](State* state, DepsLog* log) {
	ASSERT_EQ(0, state->LookupNode("foo0")->id());
	ASSERT_EQ(nullptr, state->LookupNode("foo1"));
	});

	write_file({
	"# ninjadeps\n", kCurrentVersion,
	path_hdr(4), "foo0", ~0, // node #0
	path_hdr(4), "foo1", ~1, // node #1
	path_hdr(4), "foo2", ~2, // node #2
	deps_hdr(1), /node/2, /mtime/5, 0, /node/1,
	deps_hdr(1), /node/2, /mtime/6, 0, /node/3, // invalid src ID

	// No records after the invalid record are parsed.
	path_hdr(4), "foo3", ~3, // node #3
	deps_hdr(1), /node/3, /mtime/7, 0, /node/0,
	path_hdr(4), "foo4", ~4, // node #4
	deps_hdr(1), /node/4, /mtime/8, 0, /node/0,

	// Truncation must be handled before looking for the last deps record
	// that outputs a given node.
	deps_hdr(1), /node/2, /mtime/9, 0, /node/0,
	deps_hdr(1), /node/2, /mtime/9, 0, /node/3,
	});
	DoLoadInvalidLogTest([](State* state, DepsLog* log) {
	ASSERT_EQ(0, state->LookupNode("foo0")->id());
	ASSERT_EQ(1, state->LookupNode("foo1")->id());
	ASSERT_EQ(2, state->LookupNode("foo2")->id());
	ASSERT_EQ(nullptr, state->LookupNode("foo3"));
	ASSERT_EQ(nullptr, state->LookupNode("foo4"));

	ASSERT_EQ(nullptr, log->GetDeps(state->LookupNode("foo1")));

	DepsLog::Deps* deps = log->GetDeps(state->LookupNode("foo2"));
	ASSERT_EQ(5, deps->mtime);
	ASSERT_EQ(1, deps->node_count);
	ASSERT_EQ(1, deps->nodes[0]->id());
	});
	}

	TEST_F(DepsLogTest, MustBeDepsRecordHeader) {
	// Mark a word as a candidate.
	static constexpr uint64_t kCandidate = 0x100000000;

	// Verifies that MustBeDepsRecordHeader returns the expected value. Returns
	// true on success.
	auto do_test = [](std::vector<uint64_t> words) -> bool {
	std::vector<uint32_t> data;
	for (uint64_t word : words) {
	// Coerce from uint64_t to uint32_t to mask off the kCandidate flag.
	data.push_back(word);
	}
	DepsLogData log;
	log.words = data.data();
	log.size = data.size();
	for (size_t i = 0; i < words.size(); ++i) {
	const bool expected = (words[i] & kCandidate) == kCandidate;
	if (expected != MustBeDepsRecordHeader(log, i)) {
	printf("\n%s,%d: bad index: %zu\n", __FILE__, __LINE__, i);
	return false;
	}
	}
	return true;
	};

	// Two valid deps records with no dependencies. Each record's header is
	// recognized as the start of a deps record. The first record has an mtime_hi
	// from 2262.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x8000000c\|kCandidate, 1, 2, 0x80000100,
	0x8000000c\|kCandidate, 3, 4, 5,
	}));

	// The first record's mtime_lo is within a 524us window. The second record's
	// header looks like a potential mtime_lo for 0x8007fffc.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x8000000c\|kCandidate, 1, 0x8007fffc, 2,
	0x8000000c, 3, 4, 5,
	}));

	// 0x80080000 is above the maximum record size, so it is rejected as a
	// possible header.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x8000000c\|kCandidate, 1, 0x80080000, 2,
	0x8000000c\|kCandidate, 3, 4, 5,
	}));

	// Two deps records with >16K inputs each. The header could be confused with a
	// path string containing control characters, so it's not a candidate.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x80010101, 1, 2, 3, // input IDs elided...
	0x80010101, 4, 5, 6, // input IDs elided...
	}));

	// The first record has a single dependency and an mtime_hi from 2262. The
	// second deps record's header looks like a potential mtime_lo for 0x80000100.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x80000010\|kCandidate, 1, 2, 0x80000100, 3,
	0x8000000c, 4, 5, 6,
	}));

	// The first deps record's mtime_lo is within a 524us window, and the second
	// record's header looks like a potential mtime_hi for 0x80000100.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x80000010\|kCandidate, 1, 0x80000100, 2, 3,
	0x8000000c, 4, 5, 6,
	}));

	// The first record has two dependencies, so its mtime_lo doesn't disqualify
	// the next record's header.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x80000014\|kCandidate, 1, 0x80000100, 2, 3, 4,
	0x8000000c\|kCandidate, 5, 6, 7,
	}));

	// The first deps record's mtime_hi is from 2262, and the second record's
	// header looks like a potential mtime_hi for 0x80000100.
	EXPECT_TRUE(do_test({
	// header output_id mtime_lo mtime_hi
	0x80000014\|kCandidate, 1, 2, 0x80000100, 3, 4,
	0x8000000c, 5, 6, 7,
	}));
	}

	} // anonymous namespace